When minimizing a high-dimensional objective function, standard gradient descent updates all parameters simultaneously. However, computing the full gradient can be prohibitively expensive when the number of dimensions is massive. Coordinate Descent (CD) offers an elegant alternative: update only one coordinate (or a small block of coordinates) at a time.
The central challenge of coordinate descent lies in its selection strategy: which coordinate should we update next? While traditional approaches rely on cyclic (round-robin) or randomized selection, a powerful paradigm focuses on greedy coordinate selection. By evaluating the optimization landscape at each step, greedy selection prioritizes the coordinates that promise the most significant progress toward the optimum, turning a blind search into a targeted, adaptive strategy.
The Core Intuition: The Gauss-Southwell Rule
The foundational mechanism behind greedy selection is the Gauss-Southwell rule. Instead of picking a coordinate at random, the algorithm computes or estimates the gradient vector and selects the coordinate $i$ with the largest absolute gradient component:
$$i = \arg\max_j |\nabla_j f(x)|$$
The intuition is straightforward: the coordinate with the largest gradient component represents the direction of steepest descent along the coordinate axes. Updating this specific coordinate yields the maximum possible reduction in the objective function for a single-variable step.
For many years, optimization theory suggested that randomized selection was competitive with greedy selection. However, Nutini et al. dismantled this pessimism in Coordinate Descent Converges Faster with the Gauss-Southwell Rule Than Random Selection. By analyzing coordinate descent through the lens of $\ell_1$-norm strong convexity, the authors proved that the Gauss-Southwell rule is theoretically guaranteed to converge faster than random selection—often by a factor equal to the total number of variables. They also introduced a variant that incorporates coordinate-specific Lipschitz constants to balance gradient magnitude with local smoothness, optimizing progress per step.
This principle extends naturally to ensemble learning and policy optimization. For instance, Ratsch et al. demonstrated in On the Convergence of Leveraging that ensemble methods like AdaBoost act as greedy coordinate selection algorithms, achieving linear convergence by identifying the weak learner (coordinate) with the largest absolute gradient. Similarly, in reinforcement learning, Papini et al. applied this to policy gradients in Adaptive Batch Size for Safe Policy Gradients, updating only the single parameter component with the largest absolute gradient to maximize the safe lower bound of performance improvement.
Measuring Greediness Beyond Simple Gradients
While the classic Gauss-Southwell rule relies on first-order gradient magnitudes, the concept of "greediness" adapts flexibly depending on the underlying problem structure.
1. Constraint Violations
In constrained optimization problems, such as optimal transport or Support Vector Machines (SVMs), coordinates are chosen based on how severely they violate optimality or marginal conditions.
In Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration, Altschuler et al. introduced GREENKHORN, a greedy variant of the Sinkhorn algorithm. Instead of updating all rows and columns simultaneously, GREENKHORN greedily selects the single row or column with the largest violation of marginal constraints, drastically reducing per-iteration computational costs. This concept was extended to multi-marginal transport by Salzo et al. in Batch Greenkhorn Algorithm for Entropic-Regularized Multimarginal Optimal Transport: Linear Rate of Convergence and Iteration Complexity, showing that prioritizing the most violated constraints yields strictly faster convergence than cyclic schedules.
For SVMs, Platt’s seminal Using Analytic QP and Sparseness to Speed Training of Support Vector Machines introduced Sequential Minimal Optimization (SMO), which uses heuristics to identify pairs of variables that heavily violate Karush-Kuhn-Tucker (KKT) conditions. This maximum violating pair selection strategy ensures that each local optimization step aligns with the steepest descent direction in the $\ell_1$-norm, as formalized by Simon et al. in SVM-Optimization and Steepest-Descent Line Search.
2. Duality Gaps and Stochastic Selection
Greediness does not have to be purely deterministic. In Faster Coordinate Descent via Adaptive Importance Sampling, Jaggi showed that the coordinate-wise duality gap can serve as a proxy for potential progress. By estimating each coordinate's contribution to the duality gap, the algorithm dynamically shifts its sampling distribution toward the most critical parameters, matching the changing optimization landscape.
3. Curvature and Basis Selection
In more complex geometries, greediness can incorporate second-order information or structural alignment. Vishwanathan et al. utilized a greedy second-order working set selection strategy in Multiple Kernel Learning and the SMO Algorithm to accelerate convergence.
For quasi-Newton methods, Nesterov showed in Greedy Quasi-Newton Methods with Explicit Superlinear Convergence that selecting update directions from a fixed basis to maximize the reduction in Hessian approximation error yields explicit, predictable convergence rates.
Mitigating the Search Overhead
The primary critique of greedy coordinate selection is its computational bottleneck: identifying the "best" coordinate requires scanning all coordinates, which can negate the per-step savings of coordinate descent. Researchers have developed several elegant strategies to bypass this bottleneck.
Theoretical Justification for Acceleration
Lu et al. addressed this trade-off in Accelerating Greedy Coordinate Descent Methods. They demonstrated that in real-world datasets, the most effective coordinate update often provides vastly more progress than the average update. This outsized contribution mathematically justifies the overhead of the greedy search, leading to a framework for accelerated greedy coordinate descent (AGCD) that achieves an $O(1/k^2)$ convergence rate.
Active Sets and Multilevel Hierarchies
Instead of scanning every variable at every iteration, algorithms can restrict their search to an "active set" of promising coordinates. Treister et al., in A Multilevel Framework for Sparse Optimization with Application to Inverse Covariance Estimation and Logistic Regression, proposed evaluating variables outside the active set via their gradients to selectively promote high-magnitude coordinates into the optimization hierarchy.
Similarly, Liu et al. leveraged this in Accelerating Coordinate Descent via Active Set Selection for Device Activity Detection for Multi-Cell Massive Random Access, using gradient violations as a proxy for uncertainty to update only the most critical dimensions.
Asynchronous Parallelism
To scale greedy selection to massive systems, You et al. introduced Asynchronous Parallel Greedy Coordinate Descent. This framework allows multiple processors to independently perform greedy updates without waiting for global synchronization, proving that the resulting progress toward the objective function justifies the additional concurrent overhead.
A Ubiquitous Tool Across Domains
The power of greedy coordinate selection is its versatility. It appears under different names across machine learning and numerical linear algebra:
- Matrix and Tensor Factorization: In Non-negative Matrix Factorization (NMF), Hsieh et al. showed in Fast coordinate descent methods with variable selection for non-negative matrix factorization that prioritizing updates via gradient information avoids redundant steps on stabilized variables. This logic was extended to Positive Semidefinite (PSD) factorization by Vandaele et al. in Algorithms for positive semidefinite factorization, proving that Gauss-Southwell selection provides superior robustness over cyclic updates in non-convex landscapes.
- Eigenvalue Problems: The classic power method can be accelerated via greedy coordinate selection. In Coordinate-wise Power Method, Lei et al. updated only the coordinates exhibiting the largest difference between current and projected values, drastically reducing redundant computations on large-scale graphs.
- Decentralized Networks: Even in networked environments where global information is unavailable, greedy selection can be applied locally. Costantini et al. demonstrated in Setwise Coordinate Descent for Dual Asynchronous Decentralized Optimization that nodes can accelerate convergence by greedily selecting communication partners with the largest local gradient magnitude.
Greedy coordinate selection works because it spends a small amount of computational budget to find where the error is largest, ensuring that every single update step counts.