Coordinate descent is a family of iterative methods for mathematical optimization in which each update changes only one coordinate, or a selected block of coordinates, while holding the remaining variables fixed. Instead of solving a high-dimensional problem directly, it repeatedly solves smaller subproblems. The method is particularly effective when these subproblems have inexpensive solutions, when data are sparse, or when the objective function contains penalties that separate across coordinates. Important applications include large-scale regression, sparse statistical modeling, and matrix factorization.
Basic formulation
Consider the problem
Let denote the current iterate and the -th standard coordinate vector. An exact coordinate-descent update selects an index and computes
followed by
Only the selected coordinate changes. This formulation assumes that the one-dimensional subproblem has a minimizer; practical variants may instead use an approximate minimization or a step based on local derivative information.
For constraints of the form
the update restricts the selected variable to . Such a Cartesian-product structure is especially convenient because changing one coordinate does not alter the admissible ranges of the others.
If each subproblem is solved exactly and the current point remains admissible, then
This monotonic decrease does not, by itself, establish convergence to a minimizer.
A sweep or epoch usually means enough updates to visit every coordinate once. For randomized sampling with replacement, an epoch often denotes updates even though some coordinates may be selected repeatedly and others not at all.
Coordinate-selection rules
The choice of coordinate can substantially affect both computational cost and convergence.
Cyclic selection
Cyclic coordinate descent visits coordinates in a fixed order, such as
It is easy to implement and can exploit predictable memory access. However, a particular ordering may interact poorly with strongly coupled variables.
Randomized selection
Randomized coordinate descent selects coordinates according to a probability distribution. Common choices include uniform sampling and nonuniform sampling based on coordinate smoothness or estimated update costs.
Random selection often simplifies convergence analysis and avoids dependence on one fixed order. Sampling with replacement and randomly permuting all coordinates once per sweep are distinct procedures; guarantees for one do not automatically apply to the other.
Greedy selection
A greedy rule chooses a coordinate expected to produce a large improvement. For a differentiable objective, the Gauss–Southwell rule selects a coordinate having the largest absolute partial derivative:
If coordinate curvatures vary substantially, a curvature-adjusted score may be more informative. For example, minimizing a coordinate-wise quadratic upper bound suggests selecting the largest value of
where is a coordinate smoothness constant.
Greedy selection may reduce the number of updates, but finding the best coordinate can cost more than performing the update itself.
Exact, gradient, and proximal updates
Coordinate descent includes several related update mechanisms.
Exact coordinate minimization
Exact minimization solves the selected one-dimensional problem fully. This is attractive when the solution has a closed form, as in many quadratic and penalized least-squares problems.
For more complicated objectives, the subproblem may require an inner line search or another numerical solver. In such cases, exact minimization may be less economical than a controlled approximate step.
Coordinate gradient descent
Suppose is differentiable and its coordinate derivatives satisfy a coordinate-wise Lipschitz condition:
This gives the upper bound
Minimizing the bound yields
with all other coordinates unchanged.
Unlike full gradient descent, this update uses only one component of the gradient. Whether that is computationally advantageous depends on how cheaply the component and any required intermediate quantities can be evaluated.
Proximal coordinate descent
Many applications have a composite objective
where is smooth and each is a possibly nonsmooth penalty or constraint term.
A proximal coordinate update minimizes a local quadratic model:
For proper, lower-semicontinuous convex , this can be expressed using the proximal operator:
where
This construction accommodates separable absolute-value penalties and coordinate bounds without requiring the entire objective to be differentiable.
Quadratic objectives and linear systems
For the quadratic objective
where is symmetric and positive definite, exact minimization in coordinate gives
Equivalently,
using the most recently available values of the other coordinates.
A cyclic sweep therefore coincides with the Gauss–Seidel method applied to the linear system
This connection links coordinate descent to classical iterative methods in numerical linear algebra.
The example also illustrates a limitation: when the objective has long, narrow level sets that are poorly aligned with the coordinate axes, successive coordinate updates can make slow, zigzagging progress. Strong variable coupling and poor scaling can aggravate this behavior.
Example: lasso regression
A prominent application is lasso regression, which minimizes
Here is a data matrix with observations and predictors, is the response vector, and contains the regression coefficients.
Let denote column , and define the partial residual
For a nonzero column , the exact coordinate solution is
where the soft-thresholding function is
Soft thresholding makes some coefficients exactly zero, giving the method a natural fit with sparsity-inducing regularization. In an implementation, the full residual
can be maintained incrementally. If coordinate changes by , then
This avoids recomputing the full prediction vector after every update.
Related algorithms are widely used for ridge regression, elastic net, and regularized logistic regression. For logistic regression, coordinate subproblems usually require local approximations or numerical solution rather than the same closed-form least-squares update.
Convergence and optimality
Convergence depends on the objective, constraints, update accuracy, and coordinate-selection rule. Several different claims must be distinguished:
- Objective values converge.
- Every accumulation point satisfies an optimality condition.
- The full sequence of iterates converges.
- The limit is a global minimizer.
- A specified convergence rate holds.
None of these statements should be inferred solely from monotonic decrease.
Smooth convex problems
For differentiable objectives on an unconstrained space, a point that minimizes the objective along every coordinate has zero gradient. If the objective is a convex function, this implies global optimality.
Under suitable assumptions—such as coordinate-wise smoothness, bounded relevant level sets, and an appropriate selection rule—coordinate methods admit global convergence guarantees in convex optimization.
For illustration, suppose is -strongly convex in the Euclidean norm, each coordinate smoothness constant satisfies , and coordinates are selected uniformly and independently. The update
satisfies the representative bound
Here counts individual coordinate updates and denotes expectation over the coordinate choices.
For general smooth convex objectives without strong convexity, sublinear objective-gap bounds, often of order , are available under additional boundedness assumptions. The constants and interpretation depend on whether progress is measured per update, per sweep, or by elapsed computation.
Nonsmooth and constrained problems
Separability is important. For a smooth convex term plus separable convex penalties on a product domain, coordinate optimality can imply global optimality under standard regularity conditions.
For a general nonsmooth convex objective, coordinate-wise minimization need not be sufficient. Consider
At , no change in only one coordinate can decrease the objective. Yet
Improvement requires a simultaneous change in both coordinates.
Coupled constraints create a related obstruction. Under
holding one coordinate fixed forces the other to remain fixed. Single-coordinate feasible updates cannot move at all, even if the current point is not optimal.
Nonconvex problems
For nonconvex objectives, suitably designed coordinate methods may converge to stationary points or other coordinate-wise optimal points under additional assumptions. Such points need not be globally optimal, and coordinate-wise optimality need not imply a local minimum.
The uniqueness of block solutions, tie-breaking, step-size control, and regularity of the objective can matter. General cyclic exact minimization can fail to converge without suitable assumptions.
Block and parallel variants
Block coordinate descent updates groups of variables rather than individual scalar coordinates. For a selected block , an exact update has the form
Blocks can capture strongly coupled variables, preserve feasibility under certain coupled constraints, or match the structure of a model. A major application is alternating optimization for matrix factorization, where one factor is updated while another is held fixed.
Larger blocks may improve progress per iteration but make each subproblem more expensive. Proximal or approximate block updates are therefore common.
Parallel variants update several coordinates or blocks concurrently. Their behavior depends on interactions between the selected variables:
- Synchronous methods coordinate updates at shared iteration boundaries.
- Asynchronous methods may use delayed or stale information.
- Independent or weakly interacting blocks can permit greater parallelism.
Updates computed separately from the same old iterate can interfere when applied together. Consequently, parallel methods may require smaller steps, restrictions on simultaneous updates, or assumptions about sparsity and bounded delays.
Computational practice and limitations
Coordinate descent is most attractive when one update is much cheaper than a full-gradient step. With residual maintenance, a regression update can cost roughly the number of nonzero entries in the selected data column. This makes column-oriented storage and sparse matrix representations important.
Common implementation techniques include:
- Scaling: adjusting variables so that coordinate curvatures are less disparate. For penalized regression, scaling must be accompanied by an appropriate interpretation or transformation of penalty weights.
- Warm starts: initializing a related optimization problem from a previously computed solution, especially along a sequence of regularization parameters.
- Working sets: concentrating updates on a subset of potentially relevant variables while periodically checking excluded variables.
- Screening: excluding variables through mathematically justified tests; heuristic exclusions require later verification.
- Incremental state updates: maintaining residuals, predictions, or selected derivative information rather than recomputing them from scratch.
Stopping criteria should reflect optimality rather than only small changes in objective value. Depending on the problem, useful tests include the gradient norm, violations of the Karush–Kuhn–Tucker conditions, proximal-gradient residuals, or a primal–dual gap derived through Lagrangian duality. Small coordinate changes alone may indicate poor scaling or slow progress rather than proximity to a solution.
Coordinate descent is also sensitive to parameterization: rotating the coordinate system changes the update directions even when the underlying optimization problem is equivalent. Where evaluating a single partial derivative costs nearly as much as computing the full gradient, or where variables are tightly coupled, its inexpensive-looking updates may offer little advantage over full-gradient or second-order methods.