Upper bound on a function with holder continuous gradient.

Question

Let $f : \mathbb R^d \to \mathbb R$ be differentiable with Holder continuous gradient, ie, there exists $L < \infty$ and $\alpha \in [0, 1]$ such that

$$ \| \nabla f(x) - \nabla f(y)\| \le L \| x - y\|^\alpha \quad \forall x, y\in \mathbb R^d.$$

Then how to show that

$$f(y) \le f(x) + \langle \nabla f(x), y-x\rangle + \frac{L}{1 + \alpha} \|y-x\|^{1+\alpha} \quad \forall x, y \in \mathbb R^d.$$

Answer 1

The correct inequality should be \begin{equation}f(y) \le f(x) + \langle \nabla f(x), y-x\rangle + \frac{L}{1 + \alpha} \|y-x\|^{1+\alpha} \quad \forall x, y \in \mathbb R^d. \end{equation} Otherwise take $x^2$ as a counter-example.

The common trick to handle this kind of inequalities is to notice that \begin{equation}f(y) - f(x) = \int_0^1 \langle \nabla f(x + t(y-x)), y-x\rangle dt, \end{equation} and thus \begin{equation}f(y) - f(x) - \langle\nabla f(x), y-x\rangle= \int_0^1 \langle \nabla f(x + t(y-x)) - \nabla f(x), y-x\rangle dt, \end{equation} It should be simple enough for you from here, but just in case: \begin{align}|f(y) - f(x) - \langle\nabla f(x), y-x\rangle | &\le \int_0^1 |\langle \nabla f(x + t(y-x)) - \nabla f(x), y-x\rangle |dt \\ &\le \int_0^1 \|\nabla f(x + t(y-x)) - \nabla f(x)\| \|y-x\|dt \\ &\le \int_0^1 L\|t(y-x)\|^\alpha \|y-x\|dt \\ &= L\|y-x\|^{1+\alpha} \int_0^1 t^\alpha dt \\ &= \frac{L}{1+\alpha}\|y-x\|^{1+\alpha}. \end{align}