4
$\begingroup$

A function $f$ is said to be strongly convex with respect to a norm $\|\cdot\|$ at a point $y$ if $f(x) \geq f(y) + \nabla f(y)^T(x-y) + \frac{1}{2}\|x-y\|^2.$

It is said to be strongly smooth with respect to a norm $\|\cdot\|$ at a point $x$ if $f(y) \leq f(x) + \nabla f(x)^T (y-x) + \frac{1}{2} \|y-x\|^2$.

The Fenchel dual of a convex function $f: \mathbb{R}^n \to \mathbb{R} $ is defined as: $f^*(x) = \max_y x^T y - f(y)$.

Now, it's a general fact that if $f$ is strongly convex with respect to some norm $\|\cdot\|$ everywhere, then $f^*$ is strongly smooth with respect to the dual norm $\|\cdot\|^*$ everywhere.

However, I was wondering if it is also true pointwise. Specifically, if $f$ is strongly convex at its minimum $x_0$, can one say that $f^*$ is strongly smooth at 0?

$\endgroup$
  • $\begingroup$ Have you tried to adapt the proof to the pointwise situation? $\endgroup$ – gerw May 13 '15 at 7:55
  • $\begingroup$ Yeah, the one I've seen doesn't work, because it proves it by using strong convexity at multiple points. $\endgroup$ – user1736 May 13 '15 at 14:31
2
$\begingroup$

This is true. Notice that taking the dual reverses inequalities: $f\ge g$ implies $f^*\le g^*$.

Fix $x_0$ and let $y_0=\nabla f(x_0)$. Define $$g(x) = f(x_0) + y_0^T (x-x_0) + \frac{1}{2}\|x-x_0\|^2 \tag{1}$$ This is a convex quadratic function of $x$. Its dual is $$ g^*(y) = g(y_0)+x_0^T(y-y_0)+ \frac{1}{2}\|y-y_0\|^2 \tag{2} $$ (The derivation of $(2)$ is standard; included below for completeness.)

So, strong convexity of $f$ at $x_0$, expressed as $f\ge g$, implies $f^*\le g^*$, which is the strong smoothness of $f^*$ at $y_0$. Similarly the other way around.


Proof of $(2)$

Since $\nabla g(x) = x-x_0+y_0$, it follows that $\max_x (y^T x - g(x))$ is attained when $x-x_0+y_0=y$, which implies $$\begin{split} g^*(y) &= y^T(y-y_0+x_0) - \left(f(x_0) + y_0^T (y-y_0) + \frac{1}{2}\|y-y_0\|^2 \right) \\ &= (y-y_0)^T(y-y_0) +y^Tx_0 - f(x_0) - \frac{1}{2}\|y-y_0\|^2 \\ &= -f(x_0) + y^Tx_0 + \frac{1}{2}\|y-y_0\|^2 \end{split}$$ Since $g^*(y_0)=-f(x_0)+y_0^Tx_0$, the latter formula can be rewritten as $(2)$.

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