# Regularizing a Convex function with itself

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?

-

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

-
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