1

Suppose $f$ is twice differentiable and convex, if $\nabla^2 f\preceq LI$, how to prove the following inequality holds for all $x, y$ $$ f(y)\le f(x) + \nabla f(x)^T(y-x) + \frac{L}{2} \|y-x\|_2^2 $$

Nesterov gave a simple proof in his textbook, which I don't quite understand: $$ \begin{align} f(y) - f(x) - \langle \nabla f(x), y-x\rangle&=\int_0^1 \langle \nabla f(x + \tau(y-x))-\nabla f(x),y-x\rangle d\tau \\ &\le \int_0^1 L\tau \|y-x\|_2^2 \\ &=\frac{L}{2}\|y-x\|_2^2 \end{align} $$ Where does the integration come from? Is there any other proof without integration?

Jiangnan
  • 59
  • See this question https://math.stackexchange.com/questions/2663117/fundamental-theorem-of-calculus-in-descent-lemma – Jürgen Sukumaran Sep 29 '22 at 11:28
  • You can use the following equality, which from of Mean Value Theorem. $f(y)-f(x) -\langle f^{\prime}(x),y-x\rangle=\frac{1}{2}\langle f^{\prime \prime} (x +\alpha(y-x))(y-x),y-x\rangle $. – Zacarias89. Sep 29 '22 at 11:40

0 Answers0