complexity of fitting models to data Suppose $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$ is some some continuous function

$x_1 \ldots x_n$ is a set of real values, and we'd like to compute

$\text{argmin}_a \sum_i f(a,x_i)$ to prescribed accuracy

Are there some results on difficulty of this problem for various f?

For instance, suppose $f(m,x)=(m-x)^2$. The minimum of our problem is now the mean of x's, easy to compute. On other hand, suppose $f(m,x)=\log (1+\exp(-m x))$, there's no closed form solution, so it seems argmin is harder to compute...or is it?

Motivation: this minimization problem comes up when fitting models to data. First example of f is least-squares fit and second f is logistic regression.

Edit: I just saw a related question, and it is in the spirit of what I was asking, for a particular choice of f
You may already be aware of this, but if f is a Bregman divergence, then this arg min always has an easy solution. The specific form depends on the order of the parameters, but if the expression being minimized is

$$ \arg\min_a \sum_i f(x_i, a) $$

where $f$ is a Bregman divergence, then the answer is always the mean of the $x_i$. If the order of parameters is the other way around, then you can use the duality of Bregman divergences. Specifically, if $f$ is generated by a strictly convex function $\phi$, then the solution is the $\phi$-mean $c$ given by $$\nabla \phi(c) = (1/n)\sum_i \nabla \phi(x_i)$$. 

Another interesting case is when $f$ is the Euclidean norm (not squared). In that case, the arg min is the well known Fermat-Weber point, and has been extensively studied in operations research. There's a globally optimal iterative scheme to solve it, but no closed form expression.