Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi,

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|improve this question
add comment

1 Answer 1

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|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
add comment

Your Answer

 
discard

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.