I need some help to follow the argument made here which says that $$ f(x_t) - f(x^*) \geq \frac{\alpha}{2}\|x_t-x^*\|^2 $$ if $f$ is $\alpha$ strongly convex and $x^*$ the minimizer of $f$.

From the definition of strong convexity we get \begin{align} f(x) -f(y) &\leq g_x^T(x-y)-\frac{\alpha}{2}\|x_t-x^*\|^2\\ f(y) -(x) &\geq g_x^T(y-x)+\frac{\alpha}{2}\|x_t-x^*\|^2 \end{align} for all $x,y$ and subgradient $g_x$ of $f$ at $x$. Especially for $x=x^*$.

Obviously we have to show that $g_{x^*}^T(y-x^*) \geq 0$.

If the $f$ is continuous then the set of subgradients is $\partial f(x) = \{\nabla f(x)\}$ and $g_{x^*} = \nabla f(x^*) = 0$ by optimiality of $x^*$. However I cannot see how this follows for non-continuous $f$.

  • $\begingroup$ For non-continuous function, you have to verify its convexity piecewisely. $\endgroup$
    – J. Yu
    Mar 10 '16 at 13:15
  • $\begingroup$ There is a definition of strong convexity which does not depend on continuity. $\endgroup$ Mar 10 '16 at 13:23
  • $\begingroup$ If $x^*$ is a minimizer of $f$, then by definition of subgradient $0 \in \partial f(x^*)$. $\endgroup$
    – p.s.
    Mar 11 '16 at 1:50
  • $\begingroup$ Yes, $0$ is one element in the set of subgradients. Can you elaborate on how $g_{x^*}^T(y-x^*) \geq 0$ follows for all $g_{x^*} \in \partial f(x^*)$? $\endgroup$ Mar 11 '16 at 6:46

One definition of strong convexity is that if $f$ is $\alpha$ strongly convex, then for all $y,x$ and for all $g \in \partial f(x)$. $$ f(y)-f(x) \ge g^T(y-x) + \frac{\alpha}{2}\|y-x\|^2 $$ The claimed statement is just a special case of the above equation. Note that if $x^*$ is a minimum of $f$, then $0 \in \partial f(x^*)$. So we can plug in $x=x^*$ and $g=0$ to the above and conclude that the following is true for all $y$: $$ f(y)-f(x^*) \ge \frac{\alpha}{2}\|y-x^*\|^2 $$ This is simply a weaker statement than strong convexity. I think you're getting confused by trying to prove that it's equivalent to strong convexity.

  • $\begingroup$ Isn't it necessary that the inequality holds for all $g$, not just the special case $g=0$? $g^T(y-x^*)$ could be negative for some $g \neq 0$ and the conclusion would be wrong. $\endgroup$ Mar 12 '16 at 18:26
  • $\begingroup$ The claim is just a special case. If you plugged in different subgradients you would get different conclusions. $\endgroup$
    – p.s.
    Mar 12 '16 at 18:50
  • $\begingroup$ Here's a simple abstract example. Suppose $P$ is some function of variables $a,b$ with the property that $P(a,b) \ge 0$ for all $a,b$. Further suppose that $Q$ is a function of $a$ where $Q(a) = P(a, 0)$. Then we can conclude $Q(a) \ge 0$ for all $a$. Then your objection is equivalent to saying that we haven't proved anything for all $b$, but that's irrelevant to the claim. $\endgroup$
    – p.s.
    Mar 12 '16 at 19:29
  • $\begingroup$ Good explanation. I was too focused to show it for all subgradients. $\endgroup$ Mar 13 '16 at 8:22

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.