0
$\begingroup$

Contraction is probably a bad term but I mean the following property: if $f(x)$ is $\lambda$-strongly convex and $x^*$ is its minimizer, then for all $x$ we have $\|x-x^*\|^2\leq \frac{2}{\lambda}(f(x)-f(x^*))$. What you get is that if the function value is close to the minimum, then the variables are also close.

I'm wondering what if $f(x,y)$ is strongly convex in $x$ and $y$, that is, for any $x$, $f(x,\cdot)$ is strongly convex and same hold for any fixed $y$ (but not necessarily jointly convex)? Say I find $x,y$ s.t $f(x,y)\leq f(x^*,y^*)+\epsilon$, where $(x^*,y^*)$ minimizes $f$. Can we say anything about $x$ being close to $x^*$ or $y$ being close to $y^*$? Thanks.

$\endgroup$
0
$\begingroup$

No. The contraction property is a direct consequence of strong convexity. Specifically, from the first order character of strongly convex functions: $$f(\mathbf{y})\geq f(\mathbf{x})+\partial f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})+\frac{\lambda}{2}\|\mathbf{y}-\mathbf{x}\|^2. $$ Without strong convexity, there is no contraction. Furthermore, convexity in individual coordinates might sound like a "nice" property, however it's almost meaningless from the perspective of convex analysis. Think of the function $$f(x,y) = x^22^{y^2+1}$$ which is strongly convex for $x,y$ separately, but is a completely messy function otherwise.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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