Subgradient inequality for strongly convex functions

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

• For non-continuous function, you have to verify its convexity piecewisely. Mar 10 '16 at 13:15
• There is a definition of strong convexity which does not depend on continuity. Mar 10 '16 at 13:23
• If $x^*$ is a minimizer of $f$, then by definition of subgradient $0 \in \partial f(x^*)$.
– p.s.
Mar 11 '16 at 1:50
• 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^*)$? 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.
• 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. Mar 12 '16 at 18:26
• 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.