Q:

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

A:

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. 

A:

When $f$ is convex, even if it doesn't have a closed form, you can use search methods (on a bounded domain) to find a point as close as you'd like to the local minimum, which will also be the global minimum  -- this will work for finding the minimum of the sum, as the sum of convex functions is also convex.  
There are many other better numerical methods with varying guarantees (depending on the properties of the function) for optimizing convex functions -- this book is a good (and free!) reference.

