= Block Lipschitz constant from coordinate smoothness
{title2=$L_{\mathcal B}\leq\sum_{i\in\mathcal B}L_i$}
For a continuously <differentiable> <convex function> on $\mathbb R^n$ with <coordinate Lipschitz continuity> constants $L_i$, its <block coordinate gradient> is <Lipschitz continuous> along each corresponding <coordinate subspace>, with constant at most $S_{\mathcal B}=\sum_{i\in\mathcal B}L_i$.
To prove this without assuming a <Hessian matrix>, put $\delta_{\mathcal B}=\nabla_{\mathcal B}f(x)-\nabla_{\mathcal B}f(y)$. Sum the <coordinate derivative bound by Bregman divergence> over the block, then repeat with $x,y$ interchanged and average:
$$
\|\delta_{\mathcal B}\|^2\leq S_{\mathcal B}\big(D_f(x,y)+D_f(y,x)\big)
=S_{\mathcal B}(\nabla f(x)-\nabla f(y))^T(x-y).
$$
If $x-y$ is supported in the block, the <dot product> uses only $\delta_{\mathcal B}$. The <Cauchy-Schwarz inequality> and cancellation of its <Euclidean norm> give the result, including the zero case separately. Taking the full block supplies a global <Lipschitz gradient> constant $\sum_iL_i$.
``
Target: convex-optimization.bigb, under Coordinate descent.
``
Back to article page
