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?
Best Answer
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)$.