1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Tim
    May 8, 2013 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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