Fenchel duality
Last time, we have mentioned that there exists a duality between strong convexity and Lipschitz continuous gradient. In this post, we will explore this duality, which is often called Fenchel duality.
This duality actually relates to the convex conjugate of a function. Thus, to begin with, we will first introduce the definition of conjugate function and some useful results.
The conjugate of a function \(f\) is
\[f^*(s) = \sup_{x \in \text{dom} f} (s^T x - f(x))\]Now, we will introduce several useful results on conjugate function.
Lemma Consider the following conditions:
\[\begin{align*} [1]~& f^*(s) = s^Tx - f(x)\\ [2]~& s \in \partial f(x)\\ [3]~& x \in \partial f^*(s) \end{align*}\]Then we have the following results:
(i) For a general \(f\), we have [1] \(\iff\) [2] \(\implies\) [3].
(ii) For a closed and convex \(f\), we have [1]-[3] are all equivalent.
(iii) For a closed and strictly convex \(f\), we have \(\nabla f^*(s) = \arg\!\max_x(s^T x - f(x))\).
Proof: Please refer to my notes here (page 40).
Now, we are well prepared to prove the following theorem. The proof is quite simple once you have a good understanding of my previous posts on strong convexity and Lipschitz continuous gradient.
Theorem
(i) If \(f\) is closed and strong convex with parameter \(\mu\), then \(f^*\) has a Lipschitz continuous gradient with parameter \(\frac{1}{\mu}\).
(ii) If \(f\) is convex and has a Lipschitz continuous gradient with parameter \(L\), then \(f^*\) is strong convex with parameter \(\frac{1}{L}\).
Proof:
(1): By implication of strong convexity shown in the previous post on strong convexity, we have
\[\begin{align*} \lVert s_x - s_y \rVert \ge \mu\lVert x-y \rVert ~\forall s_x\in \partial f(x), s_y\in \partial f(y) \end{align*}\]Based on the previous lemma, we have
\[\begin{align*} \lVert s_x - s_y\rVert \ge \mu\lVert \nabla f^*(s_x)- \nabla f^*(s_y) \rVert \end{align*}\]Hence, \(f^*\) has a Lipschitz continuous gradient with \(\frac{1}{\mu}\).
(2): By implication of Lipschitz continuous gradient for convex \(f\) shown in the post of Lipschitz continuous gradient, we have
\[\begin{align*} (\nabla f(x) - \nabla f(y)^T(x-y) \ge \frac{1}{L} \lVert \nabla f(x)-\nabla f(y)\rVert^2 \end{align*}\]which implies based on the previous lemma
\[\begin{align*} (s_x - s_y)^T (x-y) \ge \frac{1}{L} \lVert s_x - s_y \rVert^2~\forall x \in \partial f^*(s_x), y \in \partial f^*(s_y) \end{align*}\]Hence, \(f^*\) is strongly convex with parameter \(\frac{1}{L}\) according to the previous post on strong convexity. \(\tag*{$\Box$}\)
Citation
Recently, I have received a lot of emails from my dear readers that inquire about how to cite the content in my blog. I am quite surprised and also glad that my blog posts are more welcome than expected. Fortunately, I have an arXiv paper that summarizes all the results. Here is the citation form:
Zhou, Xingyu. “On the Fenchel Duality between Strong Convexity and Lipschitz Continuous Gradient.” arXiv preprint arXiv:1803.06573 (2018).
THE END
Now, it’s time to take a break by appreciating the masterpiece of Monet.
The Poppy Field near Argenteuil
courtesy of www.Claude-Monet.com