Suppose $f: \mathbb{R}^n \to \mathbb{R}$ is a differentiable convex function, I hope to prove that $\forall x, y, \lVert \nabla f(y) - \nabla f(x) \rVert_2 \ge m \lVert y - x \rVert_2 \Longrightarrow f$ is strongly convex with parameter $m$.

I have made the case by assuming $f\in C^2$, and proved that $\lVert \nabla f(y) - \nabla f(x) \rVert_2 \ge m \lVert y - x \rVert_2 \Longrightarrow \nabla^2 f \succeq m$, where the right side is a second-order statement of a strongly convex function. This proof is not hard.

However, I hope to find a proof without using the Hessian matrix, for example, to show that $\forall x, y, \lVert \nabla f(y) - \nabla f(x) \rVert_2 \ge m \lVert y - x \rVert_2 \Longrightarrow (\nabla f(y) - \nabla f(x))^T (y-x) \ge m \lVert y-x \rVert_2^2$, where the right side is a first-order statement of a strongly convex function.


Proof of the general case: it's known from the convex analysis that $\nabla^2 f$ exists almost everywhere. At any point $x$ where $\nabla^2 f(x)$ exists, the assumption implies that $\nabla^2 f(x)\succeq mI$. Now for any fixed $x,y$, we define $g_n(t)=n(y-x)^T (\nabla f(x+t(y-x)+(y-x)/n) - \nabla f(x+t(y-x))$ for $t\in [0,1-1/n]$, and $g_n(t)=0$ for $t\in(1-1/n,1]$. Note that $g_n\ge 0$, Fatou's lemma yields \begin{align*} m\|y-x\|_2^2 &\le \int_0^1 \liminf g_n(t) dt \le \liminf \int_0^1 g_n(t)dt \\ &= (y-x)^T(\nabla f(y)-\nabla f(x)) - \limsup \int_0^{\frac{1}{n}} n(y-x)^T(\nabla f(x+t(y-x)) - \nabla f(x))\\ &\le (y-x)^T(\nabla f(y) - \nabla f(x)) \end{align*} and we are done.

Actually, $C^2$ and convex functions behave quite similarly. For example, with the help of mollifiers and convolution, any convex function $f$ can be approximated by a sequence of convex $f_k\in C_c^\infty$, where the convergence $f_k\to f$ is uniform on any compact set. We can also treat the second-order derivative of a convex function as a positive Radon measure, e.g., in the $\mathbb{R}^1$ case, we can write \begin{align*} f(x) = a_Ix + b_I + \int_I \frac{1}{2}|x-a|\mu(da) \end{align*} where $I$ is an interval. In the multivariate case the Radon measure will be matrix-valued. This point of view will be sometimes useful: for example, in stochastic analysis, Ito's original formula holds only for $C^2$ functions, but following the preceding rationale it can be generalized to the difference of two convex functions (the so-called Ito-Tanaka formula). Moreover, the important notion of local time can then be defined.


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.