PaperlayerView exact revision on arXiv

Source-linked AI summary

Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection

Julie Nutini, Mark Schmidt, Issam H. Laradji, Michael Friedlander, Hoyt Koepke

arXiv:1506.00552v2math.OCcs.LGstat.COstat.ML

TL;DR

Randomized coordinate descent was theoretically shown to match Gauss-Southwell, despite Gauss-Southwell’s stronger empirical performance when selection costs are comparable. The paper tightens the Gauss-Southwell analysis and studies exact optimization, Lipschitz-aware, approximate, and proximal-gradient variants. Its analysis supports faster convergence outside restricted or extreme cases, while some generalizations impose additional computational or structural costs.

  • Problem

    Existing theory suggested that random coordinate selection matches Gauss-Southwell, although comparable-cost applications empirically show substantially better performance for Gauss-Southwell.

  • Method

    The paper develops tighter Gauss-Southwell analyses and examines exact coordinate optimization, Lipschitz-aware sampling, approximate rules, and proximal-gradient variants.

  • Results

    The refined analysis supports faster Gauss-Southwell convergence outside a restricted function class and identifies cases with up to a factor-n advantage over random selection.

  • Takeaways & Limitations

    Gauss-Southwell can be theoretically preferable when its exact or approximate selection cost is practical, with Lipschitz information offering an improved rule.

  • Takeaways & Limitations

    Some generalizations require extra computation or may update multiple variables, and approximate Gauss-Southwell requires errors that decrease to zero for the stated convergence guarantees.

Abstract

from arXiv · show

There has been significant recent work on the theory and application of randomized coordinate descent algorithms, beginning with the work of Nesterov [SIAM J. Optim., 22(2), 2012], who showed that a random-coordinate selection rule achieves the same convergence rate as the Gauss-Southwell selection rule. This result suggests that we should never use the Gauss-Southwell rule, as it is typically much more expensive than random selection. However, the empirical behaviours of these algorithms contradict this theoretical result: in applications where the computational costs of the selection rules are comparable, the Gauss-Southwell selection rule tends to perform substantially better than random coordinate selection. We give a simple analysis of the Gauss-Southwell rule showing that---except in extreme cases---its convergence rate is faster than choosing random coordinates. Further, in this work we (i) show that exact coordinate optimization improves the convergence rate for certain sparse problems, (ii) propose a Gauss-Southwell-Lipschitz rule that gives an even faster convergence rate given knowledge of the Lipschitz constants of the partial derivatives, (iii) analyze the effect of approximate Gauss-Southwell rules, and (iv) analyze proximal-gradient variants of the Gauss-Southwell rule.

1 Coordinate Descent Methods

The paper revisits the apparent equivalence between random coordinate selection and the more expensive Gauss-Southwell rule. It develops analyses and variants intended to explain why Gauss-Southwell often performs better in practice.

  • Nesterov’s analysis suggested that random coordinate selection and the “best” Gauss-Southwell update achieve the same convergence rate.This provides a rationale for randomized coordinate descent when Gauss-Southwell selection is expensive.
  • A tighter Gauss-Southwell analysis gives the randomized method’s rate only for a restricted function class and faster rates otherwise.The improvement can be substantial in some cases.
  • Exact coordinate optimization has a provably faster rate than constant step-size updates under a specified sparsity constraint.The paper presents this as the first theoretical result establishing a benefit for exact coordinate optimization.
  • The paper introduces Lipschitz-aware, approximate, and proximal-gradient variants of the Gauss-Southwell rule.The Lipschitz-aware variant uses coordinate-wise gradient Lipschitz constants, while approximate rules bridge randomized and exact selection.

2 Problems of Interest

Coordinate descent is useful for large convex problems when many coordinate updates cost about as much as one full-gradient iteration. The paper highlights structured problem families spanning machine learning, quadratic, graph, and matrix-based applications.

  • Coordinate descent can outperform gradient descent when n coordinate updates cost about as much as one full-gradient iteration.This is the computational regime motivating the method.
  • The first problem family contains smooth convex objectives built from a cheap function and coordinate-wise terms, including least squares, logistic regression, lasso, and dual SVMs.
  • The second family includes smooth convex graph- and matrix-structured objectives, such as quadratic functions and graph-based label propagation.It also includes continuous pairwise graphical-model assignment problems.
  • Graph sparsity can make exact Gauss-Southwell selection efficient through maintained gradients and a max-heap.With maximum degree d, the implementation cost is O(d log n).
  • For sparse matrix objectives, maintaining Ax and the gradient can implement Gauss-Southwell in O(cr log n) time.Nearest-neighbour methods can approximate the rule when the exact implementation is inefficient.

3 Existing Analysis

The existing analysis bounds progress under coordinate-wise smoothness for both uniform random selection and Gauss-Southwell selection. Although Gauss-Southwell is deterministic and can beat cyclic selection, the initial bound matches the randomized rate.

  • Coordinate-wise L-Lipschitz continuity supports a constant-step coordinate update and a per-iteration progress bound.For twice-differentiable functions, the assumption corresponds to bounded diagonal Hessian elements.
  • Uniform sampling chooses each coordinate with equal probability, whereas Gauss-Southwell chooses the coordinate with the largest directional derivative.
  • The analysis applies strong convexity to convert progress bounds into convergence guarantees.The objective is assumed to be μ-strongly convex.
  • The randomized convergence expression follows by conditioning on the history and taking expectations under uniform sampling.
  • The initial Gauss-Southwell rate is deterministic and faster than known cyclic-selection rates but equal to the randomized rate.The equality results from an inequality that loses information in the Gauss-Southwell analysis.

4 Refined Gauss-Southwell Analysis

The refined analysis measures strong convexity in the 1-norm to retain information discarded by the earlier Gauss-Southwell bound. The resulting rate matches uniform selection in an extreme case but can be up to n times faster in another.

  • 4 Refined Gauss-Southwell Analysis: Measuring strong convexity in the 1-norm avoids the information loss caused by the earlier Gauss-Southwell inequality.The new parameter is denoted μ1.
  • 4 Refined Gauss-Southwell Analysis: If μ1 = μ/n, the refined Gauss-Southwell and randomized rates are identical; if μ1 > μ/n, the refined rate is faster.
  • 4 Refined Gauss-Southwell Analysis: In the extreme case μ1 ≈ μ/n, Gauss-Southwell matches uniform selection, while μ1 ≈ μ permits a factor-n speedup.The paper identifies the latter as the case where one gradient component changes much more slowly than the others.
  • 4 Refined Gauss-Southwell Analysis: For separable diagonal quadratics with equal Hessian eigenvalues, μ = α and μ1 = α/n, so uniform selection matches Gauss-Southwell.
  • 4 Refined Gauss-Southwell Analysis: The parameter μ1 is tied to the harmonic mean of the Hessian eigenvalues divided by n, making small eigenvalues especially influential.
  • 4 Refined Gauss-Southwell Analysis: A linear-prediction problem with a weakly regularized bias variable has the favorable structure μ1 ≈ μ where Gauss-Southwell benefits most over random selection.

5 Rates with Different Lipschitz Constants

With coordinate-dependent Lipschitz constants, exact coordinate optimization and the Gauss-Southwell rule can yield faster convergence, especially when sparsity prevents repeatedly selecting the largest constants.

  • Coordinate-dependent step sizes yield a convergence rate that is faster whenever an iteration selects a coordinate with L_i < L.The bound can still be tight when every selected coordinate has L_i = L.
  • 5.1 Gauss-Southwell with Exact Optimization: Exact coordinate optimization preserves the convergence bound and can improve practical performance compared with a step size of 1/L_i.It can be implemented through a linesearch or closed-form update, including for nonquadratic objectives.
  • 5.1 Gauss-Southwell with Exact Optimization: Exact optimization makes the selected coordinate's next gradient zero, so Gauss-Southwell cannot select that coordinate again unless the solution is optimal.Thus, with distinct L_i, the resulting inequality is strict and exact optimization is faster.
  • 5.1 Gauss-Southwell with Exact Optimization: For sparse graph-structured problems, the updated coordinate remains zero-gradient until a neighboring coordinate is selected, limiting repeated choices among large L_i values.If the two largest L_i values are disconnected, Gauss-Southwell cannot simply alternate between them.
  • 5.1 Gauss-Southwell with Exact Optimization: For chain-structured graphs, the convergence rate depends on maximizers involving consecutive pairs and triples of nodes.The analysis suggests substantially better rates when large L_i values are separated by more than two graph edges.

6 Rules Depending on Lipschitz Constants

Known Lipschitz constants enable importance sampling and motivate the Gauss-Southwell-Lipschitz rule, which combines gradient magnitude with coordinate smoothness and can outperform both standard alternatives.

  • 6. Rules Depending on Lipschitz Constants: Sampling coordinates proportional to L_i gives a faster rate than uniform sampling whenever the L_i differ.This rate is a special case of Nesterov's randomized coordinate-descent analysis.
  • 6. Rules Depending on Lipschitz Constants: Lipschitz sampling and Gauss-Southwell do not dominate each other in general, motivating a combined selection strategy.In an extreme case, Lipschitz sampling can be nearly n times faster than Gauss-Southwell.
  • 6.2 Gauss-Southwell-Lipschitz Rule: The Gauss-Southwell-Lipschitz (GSL) rule selects the coordinate that minimizes the coordinate-wise convergence bound using the L_i values.Its analysis replaces the standard progress bound with the coordinate-dependent bound.
  • 6.2 Gauss-Southwell-Lipschitz Rule: The GSL rule is at least as fast as the faster of Gauss-Southwell and Lipschitz sampling.It can exceed Lipschitz sampling by more than a factor of n and depend on the minimum rather than maximum L_i.
  • 6.2 Gauss-Southwell-Lipschitz Rule: For quadratic functions, GSL is the optimal myopic coordinate update when both the coordinate and step size are chosen to maximize one-step decrease.Non-myopic strategies could still improve sequences across multiple iterations.
  • 6.2 Gauss-Southwell-Lipschitz Rule: For general f, the update in (15) is the maximum improvement rule, and the GSL analysis also applies to it.The GSL rule is cheaper and does not require special structure because the L_i can be estimated during optimization.
  • 6.2 Gauss-Southwell-Lipschitz Rule: When L_i = γ∥a_i∥^2, exact GSL selection can be formulated as a normalized nearest-neighbor-search problem.This removes the classic nearest-neighbor approximation's bias toward columns with smaller norms and does not require knowing γ.

7 Approximate Gauss-Southwell

Approximate Gauss-Southwell selection can preserve nearly the exact rule's rate under multiplicative errors, while additive errors require decay and may prevent convergence if persistent.

  • 7. Approximate Gauss-Southwell: Multiplicative-error Gauss-Southwell selection retains a progress bound scaled by (1 − ϵ_k)^2.The resulting rate degrades gracefully with ϵ_k.
  • 7. Approximate Gauss-Southwell: For small multiplicative errors, the convergence rate is nearly identical to exact Gauss-Southwell.Unlike gradient errors, the multiplicative selection error need not decrease to zero over time.
  • 7. Approximate Gauss-Southwell: With additive errors, convergence requires the errors ϵ_k to decrease to zero, and linear convergence follows when they decay linearly.If ϵ_k = O(ρ^k) for ρ < (1 − µ_1/L), the rate matches exact Gauss-Southwell.
  • 7. Approximate Gauss-Southwell: If additive errors do not decrease to zero, repeatedly selecting the same wrong coordinate can prevent convergence.The passage notes that switching coordinates could avoid this outcome.

8 Proximal-Gradient Gauss-Southwell

This section extends Gauss-Southwell coordinate selection to proximal-gradient settings with separable nonsmooth terms, comparing several generalized rules and their convergence properties.

  • Proximal-gradient setting: Proximal-gradient coordinate descent applies when f is smooth convex and each g_i is convex but possibly nonsmooth.The setting includes ℓ1-regularization and variable bounds.
  • Generalized selection rules: GS-s selects the coordinate with the most negative directional derivative, while GS-r selects the coordinate maximizing step length.GS-r can avoid arbitrarily small steps under the GS-s choice, but it ignores changes in the nonsmooth term.
  • Generalized selection rules: GS-q maximizes progress under a quadratic upper bound on f, and using coordinate Lipschitz constants yields the GSL-q strategy.The GSL-q strategy becomes the GSL rule when the nonsmooth terms are absent.
  • Rates depending on µ1: The GS-q rule matches randomized coordinate descent's convergence rate deterministically rather than only in expectation, whereas GS-s and GS-r do not satisfy that bound generally.Whether GS-q achieves the rate (1−µ1/L) in general remains open.
  • Rates depending on µ1: For linear g_i, GS-q has the same coordinate choice and smoothness parameters as applying GS to the combined objective.Thus, the smooth-case analysis transfers directly to this special nonsmooth setting.
  • Rates depending on µ1: For piecewise-linear g_i, active-set identification eventually confines the iterates to a region where the selected g_i are linear.After identification, GS-1 selects one coordinate like GS-q, and the GS-q analysis can use L instead of L1.

9 Experiments

Experiments compare coordinate-selection strategies on sparse and dense least-squares, logistic-regression, nonsmooth, and graph-based learning problems. Across the reported instances, GS often outperforms random selection, with the largest gap on the ℓ1-regularized problem.

  • Problem instances: The over-determined dense least-squares experiment uses an efficient approximate GS rule because the exact GS rule is not efficient at the chosen density.A balltree structure implements the approximation through a nearest-neighbour connection.
  • h1 experiments: GS substantially outperforms random and cyclic selection across the four h1 instances, while Lipschitz sampling narrows but does not eliminate the gap.The difference is most dramatic for the ℓ1-regularized problem, where GS focuses on nonzero variables.
  • h1 experiments: Exact coordinate optimization and the GSL rule provide modest but consistent improvements in the reported h1 experiments.The three nonsmooth GS-* rules perform nearly identically, while GSL-q outperforms them and GSL-r performs worse than cyclic and random strategies.
  • Runtime: Appendix I reports that the nonsmooth GS-* rules can also be advantageous when performance is measured by runtime rather than iteration count.The main experiments plot objective function divided by its initial value against iterations.
  • Graph-based semi-supervised learning: In graph-based semi-supervised learning, cyclic coordinate descent outperforms randomized selection, while GS and GSL perform even better.The GS and GSL rules perform similarly because the Lipschitz constants vary little in this problem.
  • Graph-based semi-supervised learning: The graph experiment uses 500 two-moons samples, five randomly labeled points, and five nearest-neighbour connections per node.This sparsity allows efficient implementation of the exact Gauss-Southwell rule and supports exact coordinate optimization.

10 Discussion

The discussion consolidates efficient implementations and theoretical extensions of Gauss–Southwell coordinate descent, including sparse updates, norm relationships, exact optimization, and graph-structured convergence.

  • Discussion: The paper concludes that GS is not universally practical, but even approximate GS rules can have better convergence-rate bounds than fully randomized methods.It also motivates exact coordinate optimization, the improved GSL rule, and proximal variants.
  • Efficient GS for h2: For graph-structured problems with maximum degree d, GS can be implemented in O(d log n) time after O(n + |E|) initialization using maintained gradients and a max heap.The heap root identifies the selected coordinate in O(1), while updates modify only affected gradient entries.
  • Assumptions: The sparse implementation relies on the assumption that each component of ∇f(Ax) depends only on the corresponding row product a_j^T x.This includes least-squares and logistic-regression models, but excludes functions such as the product function.
  • Efficient GS for h1: For sparse matrix problems, GS requires O(z) preprocessing and O(cr log n) per update when columns have at most c nonzeros and rows at most r nonzeros.This implementation maintains Ax, ∇f(Ax), A^T∇f(Ax), and the gradient heap.
  • Norm relationships: The relationship between strong convexity constants depends on the norm: 2-norm strong convexity implies at least µ/n strong convexity in the 1-norm, while 1-norm strong convexity implies at least µ1 strong convexity in the 2-norm.These relationships support the paper’s convergence-rate comparisons.
  • Exact coordinate optimization: Exact coordinate optimization can yield faster GS convergence for sparse problems because the rate depends on the sequence of factors 1 − µ1/L_i.When large L_i values are separated in the graph, the rate can be substantially faster than alternating among the largest values.

G.3 Additive error bound in terms of L

This section develops convergence analysis for proximal coordinate-descent variants with additive errors and examines why different Gauss–Southwell rules can or cannot satisfy the resulting bounds.

  • Additive errors: The additive-error convergence expression involving L is typically smaller unless the coordinate errors ϵ_k are not small.This makes the L-based expression closer to the error-in-gradient regime when errors are substantial.
  • Proximal GS rules: The GS-q rule is analyzed for objectives with smooth f and potentially nonsmooth separable g_i, using a coordinate-wise quadratic upper bound.The rule selects the coordinate whose one-dimensional model predicts the greatest progress.
  • Convergence bound: The analysis establishes a convergence bound for coordinate descent using the GS-q rule under strong convexity.The proof combines the coordinate-progress inequality with strong convexity of the composite objective.
  • Counterexamples: The GS-s rule does not generally satisfy the rate bound 1 − µ/L_n, as shown by a constructed bound-constrained counterexample.In that example, GS-s updates coordinate 2 and sets it to zero, producing insufficient progress for the claimed bound.
  • Counterexamples: In contrast, GS-r and GS-q select coordinate 1 in the bound-constrained example, set it to zero, and satisfy both analyzed bounds.The resulting objective value is approximately 5.2 for the GS-r and GS-q update.

H.4 Lack of progress of the GS-r rule

This section constructs an ℓ1-regularized example showing that the GS-r rule can make insufficient progress, whereas GS-q satisfies the analyzed bounds by a substantial margin.

  • Problem setup: The ℓ1-regularized problem uses the same matrix A and therefore the same n, µ, L, and µ1 as the preceding example.The coordinate update uses the proximal operator of the absolute value function, namely soft-thresholding.
  • GS-r behavior: The GS-r rule selects coordinate 1 in this example, and the resulting function value is evaluated after that update.The section uses this update to assess the rule’s progress ratio against the theoretical bounds.
  • Comparison: The GS-r progress ratio fails to satisfy either analyzed bound, while GS-q obtains F(x1) ≈2.2 and satisfies both bounds by a substantial margin.A genetic-algorithm search found counterexamples for GS-s and GS-r but none for GS-q in the tested parameter setting.
  • Runtime experiment: Figure 3 compares coordinate-selection rules for ℓ2-regularized sparse least squares, plotting objective against runtime.The authors report runtime benefits for GS and GSL in their implementation and test hardware, while cautioning that runtimes depend strongly on implementation details.
Loading 1506.00552v2…