Block Coordinate Descent

Block coordinate descent updates a group of correlated variables jointly at each step, restoring efficiency when single-coordinate updates stall.

From single coordinates to blocks

Plain coordinate descent updates one scalar at a time, which is inefficient when variables are strongly coupled: fixing all but one leaves almost no room to move. Block coordinate descent partitions the variables into groups and minimizes over an entire block at once, treating the other blocks as constant. Each block subproblem is smaller than the full problem but large enough to capture the coupling within the group.

Update rules

A block can be updated by an exact minimization when the subproblem is tractable, or by a single proximal-gradient step on that block when it is not. The latter is block proximal gradient and only requires the objective to be smooth in each block plus a separable nonsmooth term. Block selection can be cyclic (Gauss-Seidel sweeps), randomized, or greedy by largest block gradient norm.

• Cyclic: predictable, simple, order can matter
• Randomized: clean expected-convergence guarantees
• Greedy (Gauss-Southwell): fewest iterations, costs a full gradient to pick the block

Where it appears

Alternating least squares for matrix and tensor factorization is block coordinate descent: fix one factor matrix, solve a linear least squares for the other, alternate. Training structured models, group-lasso regression, and many expectation-maximization schemes have the same skeleton. The blocks often correspond to physically or statistically meaningful groups of parameters.

import numpy as np

def als_matrix(M, rank, iters=50):
    m, n = M.shape
    U = np.random.randn(m, rank)
    V = np.random.randn(n, rank)
    for _ in range(iters):
        U = np.linalg.lstsq(V, M.T, rcond=None)[0].T  # fix V, solve U
        V = np.linalg.lstsq(U, M, rcond=None)[0].T     # fix U, solve V
    return U, V

Guarantees and caveats

For convex problems with separable nonsmooth terms, block coordinate descent converges to a global minimizer. For nonconvex problems such as matrix factorization it converges to a stationary point, and the alternating structure can cycle without care. Choosing block sizes trades per-iteration cost against progress per sweep: larger blocks make more progress but cost more to solve.