Randomized block coordinate descent ($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 giveFor 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/\epsilon ))$. Here ${\Delta }_0$ is the initial objective function gap, and the target is its expected gap at most $\epsilon$. A coordinate-based common bound is $\beta =m{\max }_i{L}_i$; actual constants can improve it.

Target: gradient-descent.bigb, under Gradient descent.