MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


This is a problem that has being bothering me the last few days.

Assume a convex function $f(x): {\mathbb R}^n \rightarrow {\mathbb R}$ with a unique minimizer $x^{\star}$. Now consider the problem of minimizing $(1-\gamma) f(x) + \gamma f(-x)$, for some small $0< \gamma < 1 $. Say that the minimizer of this (convex) problem is $x^{\star \star}$.

Do you see any apparent way of bounding the Euclidean distance between $x^{\star}$ and $x^{\star \star}$?
What are your thoughts on the matter?

share|cite|improve this question

It is clear that there is no meaningful bound from below except for $0$ (just take $f(x)=x^2$ for 1D case). As to the bound from above, the distance can be made arbitrary large. To see that take $\gamma=\frac{1}{2}$ and let $f$ to grow sufficiently fast for $x\ge 0$ and $f(0)=0.$ For $x\le 0,$ make $f=g$ to decrease very slowly and attain minimum at some point $x=x_0$ which is very far from the origin and $g(x)>-f(-x)$ for $x\ne 0.$ Then $f(x)+f(-x)\ge 0$ with the only minimum point $x=0.$

share|cite|improve this answer
Thanks, I am interested in an upper bound. I agree that it is easy to find a construction of $f$ such that the upper bound will be useless, and my question was not phrased properly. I should have been more specific, and I apologize. The specific function that I am interested in has no such properties (as the ones you describe above). It is simply the negative expected value of the logarithm of the normal CDF $f(x) = -{\mathbb E} \log \Phi (a^{\mathrm T}x)$, where the expectation is taken w.r.t $a$, a Gaussian random vector. You may assume that $\gamma$ is smaller than 1/2. – Tim May 8 '13 at 4:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.