Let $f \colon \mathbb{R}^{d} \to \mathbb{R}$ be a function with Lipschitz continuous gradient, that is there exists $L \geq 0$ such that: \begin{equation} \label{1}\tag{1} \left\lVert \nabla f (x) - \nabla f (y) \right\rVert \leq L \left\lVert x - y \right\rVert , \forall x , y \in \mathbb{R}^{d} . \end{equation} Find the smallest $\sigma \geq 0$ such that \begin{equation} \label{2}\tag{2} f(x) \geq f(y) + \left\langle x - y , \nabla f(y) \right\rangle - \dfrac{\sigma}{2} \left\lVert x - y \right\rVert ^{2} , \forall x , y \in \mathbb{R}^{d} . \end{equation}

(If $f$ is convex then $\sigma = 0$. However, we do not have this assumption here)

My attempt: Since $f$ is $L-$Lipschitz continuous gradient, then we have (see, for example Show that Lipschitz $\|\nabla f(x) - \nabla f(y)\| \leq L\|x - y\|$ is implied by $f(y) \leq f(x) + \nabla f(x)^T(y-x) + \dfrac{L}{2}\|y-x\|^2$): \begin{equation} f (y) \leq f (x) + \left\langle y - x , \nabla f(x) \right\rangle + \dfrac{L}{2} \left\lVert y - x \right\rVert ^{2} \end{equation} which implies: \begin{align*} f \left( x \right) & \geq f \left( y \right) + \left\langle x - y , \nabla f \left( x \right) \right\rangle - \dfrac{L}{2} \left\lVert x - y \right\rVert ^{2} \\ & = f \left( y \right) + \left\langle x - y , \nabla f \left( y \right) \right\rangle + \left\langle x - y , \nabla f \left( x \right) - \nabla f \left( y \right) \right\rangle - \dfrac{L}{2} \left\lVert x - y \right\rVert ^{2} \\ & \geq f \left( y \right) + \left\langle x - y , \nabla f \left( y \right) \right\rangle - \left\lVert x - y \right\rVert \left\lVert \nabla f \left( x \right) - \nabla f \left( y \right) \right\rVert - \dfrac{L}{2} \left\lVert x - y \right\rVert ^{2} \\ & \geq f \left( y \right) + \left\langle x - y , \nabla f \left( y \right) \right\rangle - \dfrac{3L}{2} \left\lVert x - y \right\rVert ^{2} \end{align*} where the second inequality I used the Cauchy - Schwarz inequality and the last one is by the Lipschitz continuity. So my constant is $\sigma = 3L$.

However, the best posible constant (again, without convexity assumption) should be $\sigma = L$. So where did I missed?


Let $x,y\in\mathbb{R}^n$, and let $x(t) := t x + (1-t)y$. We have that $$ \begin{split} f(x) - f(y) & = \int_0^1 \langle\nabla f(x(t)), x-y\rangle\, dt \\ & = \int_0^1 \langle\nabla f(x(t)) - \nabla f(y), x-y\rangle\, dt + \langle\nabla f(y), x-y\rangle. \end{split} $$ On the other hand $$ \begin{split} & \left|\int_0^1 \langle\nabla f(x(t)) - \nabla f(y), x-y\rangle\, dt\right| \leq \int_0^1 \| \nabla f(x(t)) - \nabla f(y)\| \, \|x-y\|\, dt \\ & \leq L \int_0^1 \|x(t) - y\|\, \|x-y\|\, dt = L \|x-y\|^2 \int_0^1 t\, dt = \frac{L}{2}\|x-y\|^2, \end{split} $$ so that $$ f(x) - f(y) \geq \langle\nabla f(y), x-y\rangle - \frac{L}{2}\|x-y\|^2\,. $$

| cite | improve this answer | |
  • $\begingroup$ thank you. but does it means that the best constant is $L$ only when the function is smooth? if the property is not Lipschitz continuous gradient but Lipschitz continuous subdifferential, that is, there exists $L \geq 0$ such that $$ \left\lVert \hat{\nabla} f (x) - \hat{\nabla} f (y) \right\rVert \leq L \left\lVert x - y \right\rVert , \forall x , y \in \mathbb{R}^{d} , \hat{\nabla} f (x) \in \partial f(x) \hat{\nabla} f (y) \in \partial f(y) $$ then your approach can not applied anymore? $\endgroup$ – JKay Sep 19 '17 at 12:39
  • 1
    $\begingroup$ What do you mean by Lipschitz continuous subdifferential? Anyway, condition (2) is shared by any semi-concave function (and, in that case, $\sigma$ is the so-called semiconcavity constant of the function). $\endgroup$ – Rigel Sep 19 '17 at 12:42
  • $\begingroup$ roughly speaking Lipschitz continuous subdifferential is an extend definition of Lipschitz continuous gradient for nonsmooth function $\endgroup$ – JKay Sep 19 '17 at 12:44
  • $\begingroup$ uhm. I think that, using any definition of subdifferential, the assumption of Lipschitz continuity implies that the subdifferential is single-valued and the function is of class $C^1$. $\endgroup$ – Rigel Sep 19 '17 at 12:47
  • $\begingroup$ thank you. I will think more about it. just a curious question :) $\endgroup$ – JKay Sep 19 '17 at 12:58

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.