Coordinate descent

Overview

Coordinate descent (CD) improves an objective by updating one coordinate at a time while the others stay fixed. In the paper on this card, the coordinates are the non-negative coefficients b_k of an additive Poisson regression. Each update uses the first derivative g_k and a curvature term q_k of the negative log-likelihood, and is clipped at zero 2105.13440 §3. The paper uses CD as the inner solver of an alternating scheme for Poisson NMF, the model that the same paper relates to topic models 2105.13440 §2 alg. 1.

Only one card covers this concept so far. The variants below all come from that paper, so this page does not compare CD with other coordinate methods.

Variants

Sequential coordinate descent (SCD)

The coefficients are updated in sequence, each one using the update of the ones before it. The paper's "CD" is this sequential variant, which it takes from the NNLM package 2105.13440 app. C. Card: Non-negative matrix factorization algorithms generally improve topic model fits.

Cyclic coordinate descent (CCD)

A second variant that, like SCD, takes the full step with α = 1 and no line search 2105.13440 §3. The paper names CCD and SCD together for this property. How its update order differs from SCD's is not spelled out on this page; see 2105.13440 §3 for the exact order. Card: Non-negative matrix factorization algorithms generally improve topic model fits.

Coordinate descent with extrapolation

The paper adds an extrapolation step to the CD iterates. The new estimate is moved a further β times its last change and projected back onto the non-negative values, with β between 0 and 1 2105.13440 app. B. The authors follow an earlier extrapolation scheme and activate it from iteration 50 on the MCF-7 example 2105.13440 §4 app. B. The paper does not give a fixed schedule for β 2105.13440 app. B. Card: Non-negative matrix factorization algorithms generally improve topic model fits.

When to use which

Across four count data sets with K from 2 to 12, the paper reports that extrapolated CD was usually at least as fast as the other variants and often reached the best fit. The evidence is plotted, not tabulated [arxiv:2105.13440 §4] fig. 2.

Implementation sketch

The paper's core is one CD sweep for a non-negative regression. The extrapolation step wraps around the sweep. Shapes are in comments.

# One coordinate-descent sweep for additive Poisson regression  [§3]
# Input:  y (n,), A (n, K), b (K,) with b >= 0
# Output: b (K,), non-negative

def cd_sweep(y, A, b):
    for k in range(K):
        # Fitted means at the current b  [§3]
        mu = A @ b                             # (n,)
        # Gradient g_k and curvature q_k of the negative log-likelihood  [§3]
        g = (A[:, k] * (1 - y / mu)).sum()     # scalar
        q = (y * A[:, k] ** 2 / mu ** 2).sum() # scalar
        # Step of size alpha = 1, clipped at zero  [§3]
        b[k] = max(0.0, b[k] - g / q)
    return b

Extrapolation applied to the non-negative estimates app. B:

# Extrapolated update  [app. B]
# Input:  new (n, K), previous (n, K), beta in [0, 1]
# Output: extrapolated estimate (n, K), non-negative

def extrapolate(new, previous, beta):
    # Move beyond the new estimate by beta times its last change  [app. B]
    candidate = new + beta * (new - previous)   # (n, K)
    # Project onto the non-negative values  [app. B]
    return np.maximum(candidate, 0.0)           # (n, K)

Where the sweep sits in the outer loop: each half-step refits every row of one factor with the other held fixed 2105.13440 alg. 1. Divisions by the fitted mean μ_i need a floor against near-zero values. The paper sets estimates below 1e-15 to 1e-15 2105.13440 app. B.

Contradictions

None known. Only one card covers this concept, so no disagreement between papers can be checked. Within the paper, EM is slow in some regions but eventually reaches the same MLE after many more updates 2105.13440 §4. The paper therefore claims a speed advantage for CD, not a different final estimate. It also reports that extrapolated CD gave the best fit within the allowed time on some runs 2105.13440 §4 fig. 2.

Papers

• Non-negative matrix factorization algorithms generally improve topic model fits: derives the Poisson NMF to topic-model mapping, applies CD and extrapolation to the Poisson regression subproblems, and compares them with EM on four count data sets. Author-reported.