= Randomized block coordinate descent
{title2=$X^{t+1}=X^t-\beta^{-1}\nabla_{\mathcal B_t}f(X^t)$}
A <coordinate descent> method that randomly selects a block and updates only its coordinates. Suppose each coordinate is selected with <probability> $1/\ell$, every block has <Lipschitz constant> at most $\beta$, and the <objective function> is a <strongly convex function> with modulus $\gamma>0$. The block <descent lemma> and the <strong convexity gradient inequality> give
$$
\mathbb E[f(X^{t+1})-f(x^*)\mid X^t]\leq\left(1-\frac\gamma{\ell\beta}\right)\big(f(X^t)-f(x^*)\big).
$$
For uniform blocks of size $m$ in $n=m\ell$ coordinates, $\ell$ updates constitute an <optimization epoch>, and the <epoch complexity> is $O((\beta/\gamma)\log(\Delta_0/\varepsilon))$. Here $\Delta_0$ is the initial <objective function> gap, and the target is its expected gap at most $\varepsilon$. A coordinate-based common bound is $\beta=m\max_iL_i$; actual constants can improve it.
``
Target: gradient-descent.bigb, under Gradient descent.
``
Back to article page
