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 is
Now, we will introduce several useful results on conjugate function.
Lemma Consider the following conditions:
Then we have the following results:
(i) For a general , we have   .
(ii) For a closed and convex , we have - are all equivalent.
(iii) For a closed and strictly convex , we have .
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.
(i) If is closed and strong convex with parameter , then has a Lipschitz continuous gradient with parameter .
(ii) If is convex and has a Lipschitz continuous gradient with parameter , then is strong convex with parameter .
(1): By implication of strong convexity shown in the previous post on strong convexity, we have
Based on the previous lemma, we have
Hence, has a Lipschitz continuous gradient with .
(2): By implication of Lipschitz continuous gradient for convex shown in the post of Lipschitz continuous gradient, we have
which implies based on the previous lemma
Hence, is strongly convex with parameter according to the previous post on strong convexity.
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).
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