# Best constant for Lipschitz continuous gradient function

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: $$\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} .$$ Find the smallest $\sigma \geq 0$ such that $$\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} .$$

(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$): $$f (y) \leq f (x) + \left\langle y - x , \nabla f(x) \right\rangle + \dfrac{L}{2} \left\lVert y - x \right\rVert ^{2}$$ 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\,.$$
• 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? – mortal Sep 19 '17 at 12:39
• 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). – Rigel Sep 19 '17 at 12:42
• 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$. – Rigel Sep 19 '17 at 12:47