Coordinate descent

Coordinate descent minimizes an objective by repeatedly optimizing one coordinate, or one block of coordinates, while holding all others fixed. Exact coordinate minimization is especially simple for separable penalties and quadratic objectives.

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.

The orthogonal projection of the gradient onto the coordinate subspace indexed by $\mathcal{B}$. It is kept as a vector in the original Euclidean space, with zero coordinates outside the block. For a singleton block it is ${\partial }_{i}f(x)e_i$; for the full block it is $\nabla f(x)$.

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