Best constant for Lipschitz continuous gradient function

Question

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?

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