Coordinate Descent Algorithms

Stephen J. Wright

Source-linked AI summary

Coordinate Descent Algorithms

Stephen J. Wright

arXiv:1502.04759v1Feb 17, 2015math.OC

TL;DR

Coordinate descent offers simple, useful methods for optimization problems arising in data analysis and machine learning, but its convergence behavior depends on objective structure and execution model. This paper develops core, accelerated, randomized, cyclic, and parallel variants, emphasizing efficient implementations for structured problems. The results characterize convergence properties while showing that coordinate coupling weakens bounds and that nonconvex cyclic methods can fail without additional assumptions.

Problem
Applications need coordinate-descent methods that exploit structured objectives while providing convergence understanding across convex, nonconvex, and parallel settings.
Method
The paper surveys coordinate-descent fundamentals and variants, analyzes convergence, develops accelerated implementations, and examines synchronous and asynchronous parallel execution.
Results
Larger coordinate coupling produces weaker convergence bounds, while computational behavior varies across randomized variants, step choices, and problem conditioning.
Takeaways & Limitations
Coordinate descent is an important optimization tool for machine learning and data analysis, particularly in big-data settings.
Takeaways & Limitations
Asynchronous convergence conclusions depend critically on an upper bound on delay, and inconsistent reading may violate a stronger iterate-consistency assumption.

Abstract

from arXiv · show

Coordinate descent algorithms solve optimization problems by successively performing approximate minimization along coordinate directions or coordinate hyperplanes. They have been used in applications for many years, and their popularity continues to grow because of their usefulness in data analysis, machine learning, and other areas of current interest. This paper describes the fundamentals of the coordinate descent approach, together with variants and extensions and their convergence properties, mostly with reference to convex objectives. We pay particular attention to a certain problem structure that arises frequently in machine learning applications, showing that efficient implementations of accelerated coordinate descent algorithms are possible for problems of this type. We also present some parallel variants and discuss their convergence properties under several models of parallel execution.

1 Introduction

Coordinate descent repeatedly solves simpler coordinate or block subproblems, making it useful for structured optimization in machine learning and data analysis. The paper introduces core formulations and update rules, including randomized and regularized variants.

Coordinate descent fundamentals: Each iteration fixes most components of x and approximately minimizes the objective over one coordinate or coordinate hyperplane.The resulting lower-dimensional subproblem is typically easier than minimizing the full objective.
Motivation and applications: Coordinate descent has become competitive in applications whose gradients are cheap to compute, accuracy requirements are modest, or objectives contain nonsmooth regularization.The methods can also accommodate a small number of equality constraints.
Regularized formulations: Separable regularizers include the ℓ1 norm and box constraints, while block-separable forms include group-sparse regularizers used in compressed sensing and model selection.These structures permit updates over individual coordinates or compatible coordinate blocks.
Problem classes: Coordinate descent also applies to empirical risk minimization and dual formulations, including least squares, logistic regression, and support vector machines.The dual formulation is particularly amenable when its summation term is separable.
Regularized formulations: Regularized coordinate descent linearizes the smooth term, adds quadratic damping, and handles the selected regularizer explicitly through a scalar subproblem.For choices such as Ω_i(·) = |·|, the update can use a closed-form shrink operation.
Randomized variants: Randomized coordinate descent is a special case of stochastic-gradient methods, but it guarantees descent at every iteration and its gradient-estimate variance vanishes at a solution.The contrast is that general stochastic-gradient estimates may remain nonzero at a solution.

2 Applications

Coordinate descent has been applied across signal processing, statistics, machine learning, imaging, scientific modeling, and network design. The surveyed examples include both single-coordinate and block-coordinate methods for convex and nonconvex objectives.

Scientific and engineering applications: Other applications include protein-structure determination through cyclic angle updates and traffic-demand recovery through alternating optimization over two variable blocks.The traffic model alternates between origin-destination demands and arc-assignment proportions.
Sparse and statistical learning: Applications include linear and logistic regression with nonconvex regularization, genetic association, gene expression studies, and sparse inverse covariance estimation.The graphical lasso cycles through matrix rows and columns while solving lasso subproblems.
Machine learning: Cyclic and stochastic coordinate descent solve squared-loss support vector machine objectives, while earlier SMO procedures address hinge-loss SVM formulations.These problems fit the empirical risk minimization framework.
Sparse and statistical learning: Coordinate descent supports sparse recovery and compressed sensing through lasso-equivalent formulations, including direct block updates on the primal problem.The basis-pursuit objective combines squared loss with an ℓ1 penalty.
Scientific and engineering applications: Block coordinate descent has been used for cellular-network transceiver design, tensor factorization, semantic basis discovery, and tomography.The surveyed tomography objectives include smooth convex terms with pairwise regularization penalties.
Related methods: Low-rank matrix completion and ADMM can be interpreted through coordinate-descent ideas, although that interpretation may not always clarify algorithm performance.ADMM alternates approximate minimization over primal-variable blocks and updates multiplier estimates.

3 Coordinate Descent: Algorithms, Convergence, Implementations

The paper develops coordinate-descent variants, convergence results, accelerated implementations, and parallel extensions, while highlighting important failures outside favorable assumptions. Powell’s example shows that cyclic coordinate descent can fail to converge for a nonconvex objective.

Algorithms and analysis: The paper presents fundamental coordinate-descent variants, convergence analyses, accelerated implementations, and parallel methods in an elementary framework.The treatment emphasizes essential algorithmic properties rather than the most general formulations.
Powell’s example: Powell’s nonconvex three-dimensional example demonstrates that cyclic coordinate descent can fail to converge to a stationary point.The figure documents this nonconvergence behavior.
Powell’s example: Exact cyclic minimization can cycle near six non-optimal cube vertices even though the function has minimizers at two opposite vertices.The behavior occurs for starts near, but just outside, another cube vertex.
Convergence scope: The example indicates that general convergence guarantees for nonconvex coordinate descent cannot be expected without additional assumptions.Results are available under conditions such as unique directional minimizers or the Kurdyka–Łojasiewicz property.

3.2 Assumptions and Notation

The paper analyzes unconstrained convex, Lipschitz continuously differentiable objectives, sometimes assuming strong convexity, and defines coordinate-specific smoothness quantities for its algorithms and convergence analysis.

Component Lipschitz constants Li control changes in individual gradient components along coordinate directions.
Lmax summarizes the largest coordinate Lipschitz constant, while L is the standard full-gradient Lipschitz constant.
The constants satisfy 1 ≤ L/Lmax ≤ n, with the upper bound attained for a fully coupled quadratic example.
The restricted Lipschitz constant Lres supports analysis of asynchronous parallel algorithms and reflects cross-coordinate Hessian coupling.
For separable objectives, the coupling measure Λ equals 1; stronger bounds arise when Hessian coupling is weak.
The main setting is an unconstrained problem with convex, uniformly Lipschitz continuously differentiable objective f, attained minimum, and bounded initial level set.

3.3 Randomized Algorithms

Randomized coordinate descent samples one coordinate per iteration and admits convergence guarantees under convexity and related conditions, including a linear rate for Kaczmarz without strong convexity.

Randomized coordinate descent selects each coordinate independently and uniformly, then updates only that coordinate using a chosen steplength.
The paper proves a convergence result for the simple constant steplength αk ≡ 1/Lmax.
The same convergence bounds extend to αk = 1/Lik and exact coordinate minimization, rather than only the conservative constant steplength.
Compared with full-gradient descent, coordinate updates can incur an additional factor n in the convergence bound when L and Lmax are comparable.
Sampling without replacement has been superior in several settings, but its theoretical explanation remains elusive.
Randomized Kaczmarz achieves an expected linear rate without strong convexity, allowing Aw = b to have multiple solutions.

3.4 Accelerated Randomized Algorithms

Accelerated randomized coordinate descent uses momentum and coordinate-wise smoothness information to improve convergence rates, while requiring stronger per-iteration computation than standard coordinate descent.

Algorithm 4 assumes estimates of strong-convexity modulus σ and component Lipschitz constants Li, or uses Lmax uniformly.
The acceleration approach is closely related to accelerated full-gradient methods through its use of momentum in the search step.
The accelerated method combines extrapolated vectors, a uniformly sampled coordinate gradient, and momentum updates for x and v.
In the strongly convex case, the conditioning measure σ/Lmax is effectively replaced by its square root, yielding a significantly faster linear rate.
A 1/k^2 sublinear bound replaces the standard 1/k bound, reducing the iteration requirement from O(1/ϵ) to O(1/√ϵ).

3.5 Efficient Implementation of the Accelerated Algorithm

The paper develops efficient implementations that preserve acceleration while reducing update costs, especially for sparse matrices where naïve accelerated Kaczmarz loses sparsity benefits.

Algorithm 5 applies accelerated randomized coordinate descent to Kaczmarz through the transformation w = ATx and normalized rows, giving Li ≡ 1.
For dense A, standard and accelerated Kaczmarz have comparable per-iteration workload of O(m + n).
For sparse A, standard Kaczmarz costs O(|Aik|) per iteration, whereas naïve acceleration requires O(n) manipulation of dense vectors.
The Lee-Sidford change of variables replaces dense accelerated vectors with alternative representations that can be updated in O(|Aik|) operations.
The alternative representation also computes Aik ỹk−bik efficiently from two vector products and two coefficients.
The efficient scheme extends to certain dual empirical-risk problems when the relevant gradient component remains efficiently evaluable after representation updates.

3.6 Cyclic Variants

The cyclic coordinate-descent variant has deterministic complexity bounds, but these can be weaker than randomized bounds, especially when coordinate coupling is strong. Step-size choices further affect the resulting guarantees.

3.6 Cyclic Variants: Theorem 3 establishes deterministic cyclic-coordinate complexity bounds at iterations k = n, 2n, 3n, . . . under Assumption 1 and αk ≡ 1/Lmax.The result is stated for the cyclic ordering of coordinates.
3.6 Cyclic Variants: In the strongly convex case, an additional cyclic convergence bound holds at multiples of n.The strong convexity condition is σ > 0.
3.6 Cyclic Variants: Cyclic bounds have an O(n^2) numerator versus O(n) for the corresponding randomized bound, while remaining deterministic rather than expected-nonoptimality guarantees.The comparison uses L ≥ Lmax in general.
3.6 Cyclic Variants: For convex quadratics, L/Lmax lies in [1, n]; larger ratios indicate stronger coordinate dependence and produce weaker cyclic bounds.The paper relates this weakening to the greater iteration burden of resolving coordinate coupling.
3.6 Cyclic Variants: Choosing Lmax = L yields a bound worse by approximately 2n^2 than full-step gradient descent.Larger Lmax values shorten the step αk = 1/Lmax and change the complexity expression.

3.7 Extension to Separable Regularized Case

The paper extends randomized coordinate descent to separable regularized objectives with smooth, strongly convex f and convex coordinate regularizers. Under these assumptions, a fixed-step convergence result follows from uniform coordinate sampling and recursive expectation arguments.

3.7 Extension to Separable Regularized Case: The extension treats separable regularized objectives with smooth, strongly convex f and convex functions Ωi.The section proves a result for a randomized version of Algorithm 2.
3.7 Extension to Separable Regularized Case: Assumption 2 requires uniformly Lipschitz continuously differentiable, strongly convex f, convex Ωi, and a unique minimizer of h.The strong-convexity modulus is σ > 0.
3.7 Extension to Separable Regularized Case: The analysis uses the coordinate Lipschitz constant Lmax for f, which also determines the fixed step αk ≡ 1/Lmax.The convexity modulus of f is also the modulus of convexity for h.
3.7 Extension to Separable Regularized Case: Theorem 4 assumes independently and uniformly sampled coordinates and establishes the stated convergence result for every k ≥ 0.The theorem applies the fixed step αk ≡ 1/Lmax.
3.7 Extension to Separable Regularized Case: The proof constructs a function separable in z whose minimum is attained at the coordinate update specified by Algorithm 2.It then minimizes the resulting inequality and takes expectation over the sampled coordinate.
3.7 Extension to Separable Regularized Case: For convex but not strongly convex f, a similar result is available, but technical complications lead the authors to refer to prior work for details.A related nonconvex extension gives stationary accumulation points and a sublinear 1/k decrease in an optimality measure.

3.8 Computational Notes

The computational study compares six coordinate-descent variants on constructed convex quadratic problems. Convergence depends strongly on problem parameters, and stressed settings can make cyclic variants much slower than randomized ones.

3.8 Computational Notes: The paper does not provide a full computational comparison between coordinate-descent variants or against other methods.This comparison is explicitly outside the paper’s scope.
3.8 Computational Notes: The experiments minimize convex quadratic objectives with positive semidefinite Q, varying construction parameters to produce different convergence conditions.Q is normalized so its maximum diagonal, and thus Lmax, equals 1.
3.8 Computational Notes: Six variants combine CYCLIC, IID, and EPOCHS coordinate selection with fixed αk ≡ 1/Lmax or optimal αk = 1/Qik,ik steps.The starting point is random, and runs stop after a 10^-6 reduction in the objective from its initial value.
3.8 Computational Notes: Convergence speed varies widely with η, λ, and cond(Σ), while EPOCHS is usually faster than IID but rarely by more than a factor of two.The optimal step is usually better than the fixed step, sometimes requiring up to six times fewer iterations.
3.8 Computational Notes: In stressed settings, CYCLIC variants are much slower than randomized variants, by factors of 10 or more.The experiments report this as one of the general observations across the tested parameter regimes.

4 Parallel CD Algorithms

Parallel coordinate descent includes synchronous and asynchronous implementations, with convergence guarantees depending on synchronization, delays, update choices, and assumptions about stale information. Under suitable delay and coupling conditions, asynchronous methods can achieve convergence rates close to serial randomized coordinate descent and near-linear speedup.

Synchronous parallelism: Synchronous parallel CD partitions coordinate updates across processors and synchronizes frequently to maintain consistent information.Some implementations update disjoint coordinate subsets in parallel, while others synchronize after each parallel round.
Asynchronous parallelism: Asynchronous CD lets processors independently read and update shared x without coordinating or synchronizing with other processors.Each processor runs its own coordinate-descent process, using potentially stale components when evaluating gradient entries.
Partly asynchronous parallelism: An asynchronous linear-rate result requires stronger assumptions, including bounded delays and conditions such as Assumption 1 and condition (52).The bounded-delay model assumes no component of the evaluation vector is older than the maximum delay τ.
Parallel performance: Near-linear speedup can be expected because asynchronous convergence bounds closely resemble serial randomized CD, with limited total-work overhead.The comparison identifies a factor-of-2 steplength difference and an additional n denominator term in the sublinear rate as key differences.
Parallel performance: The allowable delay depends critically on component coupling: weak coupling permits delays of order n1/4, whereas strong coupling may restrict delays to values barely above 1.A more general result allows smaller step parameters to degrade convergence bounds gracefully when delays are tightly restricted.

5 Conclusion

The paper surveys coordinate descent fundamentals, extensions, and convergence results, emphasizing its role in machine learning and data analysis. It concludes that continued customization for problem structures and computing platforms is likely to drive further developments.

Conclusion: The paper surveys convergence of coordinate descent methods in elementary settings and for fundamental algorithms, while noting many extensions in the recent literature.The authors refer readers to the bibliography because new coordinate-descent work is appearing rapidly.
Conclusion: Coordinate descent has become an important optimization tool for machine learning and data analysis, particularly in big-data settings.The conclusion anticipates further adaptations to specific problem structures, computer platforms, and combinations with other optimization tools.
Conclusion: The paper acknowledges editorial and referee feedback that led to numerous improvements.This acknowledgement is separate from the paper’s technical conclusions.