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?


1 Answer 1


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\,. $$

  • $\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
    Commented Sep 19, 2017 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
    Commented Sep 19, 2017 at 12:42
  • $\begingroup$ roughly speaking Lipschitz continuous subdifferential is an extend definition of Lipschitz continuous gradient for nonsmooth function $\endgroup$
    – JKay
    Commented Sep 19, 2017 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
    Commented Sep 19, 2017 at 12:47
  • $\begingroup$ thank you. I will think more about it. just a curious question :) $\endgroup$
    – JKay
    Commented Sep 19, 2017 at 12:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .