<p>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.  </p>

<p>There are many other better numerical methods with varying guarantees (depending on the properties of the function) for optimizing convex functions -- <a href="http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf">this book</a> is a good (and free!) reference.</p>

CC BY-SA 2.5
2010-09-20T01:25:30.667Z
An added note: square loss, logistic loss, and Bregman divergences (in their first argument) are convex.
Lev Reyzin
CC BY-SA 2.5
2010-09-22T16:15:55.550Z
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 (http://tinyurl.com/2dz8wky), this suggests that some practical convex optimization problems are hard
Yaroslav Bulatov
CC BY-SA 2.5
2010-09-22T17:11:51.757Z
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
CC BY-SA 2.5
2010-09-22T19:33:24.583Z
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
CC BY-SA 2.5
2010-09-20T01:19:46.630Z
2010-09-20T01:46:08.617Z
2010-09-20T01:46:08.617Z
Lev Reyzin
<p>You may already be aware of this, but if f is a <a href="http://en.wikipedia.org/wiki/Bregman_divergence">Bregman divergence</a>, 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</p>

<p>$$ \arg\min_a \sum_i f(x_i, a) $$</p>

<p>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)$$. </p>

<p>Another interesting case is when $f$ is the Euclidean norm (not squared). In that case, the arg min is the well known <a href="http://en.wikipedia.org/wiki/Geometric_median">Fermat-Weber point</a>, and has been extensively studied in operations research. There's a globally optimal iterative scheme to solve it, but no closed form expression. </p>

CC BY-SA 2.5
2010-08-24T20:40:47.457Z
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
CC BY-SA 2.5
2010-08-24T21:31:34.280Z
the derivation is very straightforward (basic calculus, combined with the Fenchel dual), but one reference is the JMLR paper by Banerjee et al: http://jmlr.csail.mit.edu/papers/v6/banerjee05b.html
Suresh Venkat
CC BY-SA 2.5
2010-08-24T19:01:19.993Z
2010-08-24T19:01:19.993Z
Suresh Venkat
<p>Suppose $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$ is some some continuous function</p>

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

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

<p>Are there some results on difficulty of this problem for various f?</p>

<p>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?</p>

<p>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.</p>

<p><b>Edit</b>: I just saw a related <a href="https://cstheory.stackexchange.com/questions/1811/complexity-of-exponential-function">question</a>, and it is in the spirit of what I was asking, for a particular choice of f</p>

<approximation-algorithms><machine-learning><st.statistics>
complexity of fitting models to data
Yaroslav Bulatov
# complexity of fitting models to data

(Asked by: username_0 on 2010-08-24)

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](https://cstheory.stackexchange.com/questions/1811/complexity-of-exponential-function), and it is in the spirit of what I was asking, for a particular choice of f

**Tags:** approximation-algorithms, machine-learning, st.statistics

---

## 2 answers

### Answer by username_1 on 2010-09-20. Score: 6 | Accepted answer

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](http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf) is a good (and free!) reference.

> **Comments:**
> **username_1**: An added note: square loss, logistic loss, and Bregman divergences (in their first argument) are convex.  
> **username_0**: 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 (http://tinyurl.com/2dz8wky), this suggests that some practical convex optimization problems are hard  
> **username_1**: 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.  
> **username_0**: 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)  

---

### Answer by username_2 on 2010-08-24. Score: 9

You may already be aware of this, but if f is a [Bregman divergence](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Geometric_median), and has been extensively studied in operations research. There's a globally optimal iterative scheme to solve it, but no closed form expression.

> **Comments:**
> **username_0**: 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  
> **username_2**: the derivation is very straightforward (basic calculus, combined with the Fenchel dual), but one reference is the JMLR paper by Banerjee et al: http://jmlr.csail.mit.edu/papers/v6/banerjee05b.html  

---

