= Coordinate derivative bound by Bregman divergence
{title2=$[\partial_i f(x)-\partial_i f(y)]^2\leq2L_iD_f(x,y)$}
Suppose $f$ is a <differentiable> <convex function> with <coordinate Lipschitz continuity> constant $L_i>0$. Put $\phi(u)=D_f(u,y)=f(u)-f(y)-\nabla f(y)^T(u-y)$, the <Bregman divergence> from the supporting <affine function> at $y$. The <subgradient inequality> gives $\phi\geq0$, and its coordinate <Lipschitz constant> is still $L_i$. The coordinate <descent lemma> with <step size> $1/L_i$ yields
$$
0\leq\phi\left(x-\frac{\partial_i\phi(x)}{L_i}e_i\right)\leq\phi(x)-\frac{[\partial_i\phi(x)]^2}{2L_i}.
$$
Since $\partial_i\phi(x)=\partial_i f(x)-\partial_i f(y)$, rearrangement proves the bound. Continuous <differentiability> suffices; a <Hessian matrix> is unnecessary.
``
Target: gradient-descent.bigb, under Lipschitz gradient.
``
Back to article page
