# 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

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.

• An added note: square loss, logistic loss, and Bregman divergences (in their first argument) are convex. – Lev Reyzin Sep 20 '10 at 1:25
• I thought all convex optimization was easy until I recently came across some convex objectives on which all numerical optimizers I tried (including Newton's method with exact Hessian). The problem was that objective was too flat. Solution was to use algebraic methods (tinyurl.com/2dz8wky), this suggests that some practical convex optimization problems are hard – Yaroslav Bulatov Sep 22 '10 at 16:15
• I guess it depends on the meaning of hard/easy. If you have a box constraint on the domain, you can always just do binary search. – Lev Reyzin Sep 22 '10 at 17:11
• OK, that's true. The reason this question was that it's surprising to me that you can take a models for which fitting is provably hard, do a small change in the measure of fit and get a model where fitting is easy. (ie, maximum likelihood vs. pseudolikelihood for dense graphical models, both are consistent estimators, but only one is tractable) – Yaroslav Bulatov Sep 22 '10 at 19:33

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.

• Interesting, didn't know this...do you have reference for the phi-mean formula? I'm wondering if this gives a faster way to fit logistic regression models – Yaroslav Bulatov Aug 24 '10 at 20:40
• the derivation is very straightforward (basic calculus, combined with the Fenchel dual), but one reference is the JMLR paper by Banerjee et al: jmlr.csail.mit.edu/papers/v6/banerjee05b.html – Suresh Venkat Aug 24 '10 at 21:31