--- kind: concept slug: coordinate-descent title: Coordinate descent summary: >- Minimising a function by updating one parameter (or one block) at a time with a scaled gradient step, clipped to non-negative values. Covers cyclic and sequential sweeps for Poisson regression and Poisson NMF, the no-line-search caveat, and extrapolation. One paper so far. tags: [optimization, matrix-factorization, topic-models] papers: ["2105.13440"] related: [expectation-maximization, topic-modelling] status: draft updated_at: 2026-11-08 --- ## 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 [arxiv: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 [arxiv: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 [arxiv:2105.13440 app. C]. Card: [Non-negative matrix factorization algorithms generally improve topic model fits](/papers/2105.13440). ### Cyclic coordinate descent (CCD) A second variant that, like SCD, takes the full step with α = 1 and no line search [arxiv: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 [arxiv:2105.13440 §3] for the exact order. Card: [Non-negative matrix factorization algorithms generally improve topic model fits](/papers/2105.13440). ### 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 [arxiv:2105.13440 app. B]. The authors follow an earlier extrapolation scheme and activate it from iteration 50 on the MCF-7 example [arxiv:2105.13440 §4] [app. B]. The paper does not give a fixed schedule for β [arxiv:2105.13440 app. B]. Card: [Non-negative matrix factorization algorithms generally improve topic model fits](/papers/2105.13440). ## When to use which | Situation | Use | Why | |---|---|---| | Fitting Poisson NMF, or a non-negative Poisson regression inside it | SCD sweeps as the inner solver | The paper's CD has a counterpart for Poisson NMF but none for the topic model [arxiv:2105.13440 §3] [tab. 1] | | Fitting the multinomial topic model itself (rows and columns sum to one) | EM, or fit Poisson NMF and map the result | CD has no topic-model counterpart; the paper maps Poisson NMF fits to topic models [arxiv:2105.13440 §2] [tab. 1] | | Early progress matters, far from the optimum | CD over EM | On MCF-7 with K = 3, 200 CD updates ended within 0.079 log-likelihood units of the MLE, while 200 EM updates were more than 150,000 away. This is one data set, and the figures are author-reported [arxiv:2105.13440 §4] [fig. 1] | | Plain CD is slow to finish the last steps | CD with extrapolation | On MCF-7, extrapolated CD reached the MLE with far fewer updates than plain CD. The paper gives no count [arxiv:2105.13440 §4] [fig. 1] | | Each step must not increase the objective | Add a line search, or run an EM update before each CD update | Full steps without a line search can raise the loss. The paper runs one EM update before each CD update to reduce failures [arxiv:2105.13440 app. B] | | Large sparse count matrices | Use sparse loss evaluation | The loss costs on the order of (N + n + m)K for N nonzeros, against nmK for dense data [arxiv:2105.13440 app. B] | | Many independent subproblems | Solve row subproblems in parallel | The row updates in each alternating half-step do not depend on each other [arxiv:2105.13440 §3] | 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. ```pseudocode # 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]: ```pseudocode # 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 [arxiv: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 [arxiv: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 [arxiv: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 [arxiv:2105.13440 §4] [fig. 2]. ## Papers - [Non-negative matrix factorization algorithms generally improve topic model fits](/papers/2105.13440): 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.