Smoothness

Lemma 1 ( Bubeck ) Beta-Smoothness

Let $f$ be a $\beta$-smooth function. then for any $x,y$

$$| f(x) - f(y) - \nabla f(y)^T (x-y) | \leq \frac{\beta}{2} ||x-y||^2$$

Proof )

\begin{align} | f(x) - f(y) - \nabla f(y)^T (x-y) | &= |\int^1_0 \nabla f(y+t(x-y))^T(x-y) dt - \nabla f(y)^T (x-y) | \\ &\leq   | \int^1_0 ||\nabla f(y+t(x-y)) - \nabla f(y)^T|| ||(x-y)| |\\ &\leq \int^1_0 \beta t ||x-y||^2 \\ &= \frac{\beta}{2} ||x-y||^2\end{align}