When dealing with massive, high-dimensional datasets—such as those found in text processing, genomics, or recommendation systems—the underlying data matrices are almost always sparse. Intuitively, optimization should become faster when most entries are zero. However, classical optimization algorithms often inadvertently destroy this sparsity.
As Stephen Wright explains in Coordinate Descent Algorithms, traditional full-gradient or second-order methods require operations that scale with the total dimensionality of the parameter space, making them computationally prohibitive. The core issue manifests in two ways:
- Fill-in: Direct matrix factorizations (like Cholesky or LU decomposition) used to solve linear subproblems convert zero entries into non-zero entries, causing memory requirements to explode.
- Redundant Computation: Full-vector updates force the algorithm to modify every parameter at every step, even when a training example only contains a handful of active features.
Sparsity-preserving iterative optimization addresses these bottlenecks by redesigning algorithms to ensure that computational and memory costs scale with the number of non-zero elements ($NNZ$) rather than the total dimensionality ($D$).
Factorization-Free Optimization via Matrix-Vector Products
To prevent the catastrophic memory overhead of fill-in, a foundational strategy is to replace direct matrix inversions with iterative solvers that rely exclusively on matrix-vector products.
In early work, J. N. Holt et al. demonstrated in An inexact Levenberg-Marquardt method for large sparse nonlinear least squres that solving linear subproblems inexactly via iterative matrix-vector multiplications ensures memory scales linearly with the number of non-zero elements in the Jacobian. Because a matrix-vector product does not alter the matrix itself, the inherent sparsity structure is perfectly preserved throughout the optimization process.
This factorization-free paradigm allows algorithms to bypass dense intermediate bottlenecks across a variety of complex objectives:
- Spectral Problems: Rong Ge et al. applied this concept to Canonical Correlation Analysis and Generalized Eigenvector problems in Efficient Algorithms for Large-scale Generalized Eigenvector Computation and Canonical Correlation Analysis, avoiding dense intermediate matrices entirely by relying solely on matrix-vector products.
- Game-Theoretic Objectives: Jiali Wang et al. leveraged iterative matrix-vector operations in Solving Stackelberg Prediction Game with Least Squares Loss via Spherically Constrained Least Squares Reformulation to bypass expensive second-order cone programming, directly exploiting data sparsity to reduce memory requirements.
Coordinate-Wise Updates and NNZ Scaling
While matrix-vector products protect memory, we can further reduce computational cost by breaking full-vector operations down into coordinate-wise modifications. Instead of updating all parameters simultaneously, coordinate descent algorithms update a single variable (or a small block of variables) at a time while keeping the others fixed.
The mathematical intuition is elegant: updating a single coordinate requires accessing only a single column or row of the data matrix. As a result, the per-iteration cost scales strictly with the number of non-zero entries in that specific component, rather than the global dimensionality of the parameter space.
This mechanism allows algorithms to scale linearly with data sparsity across diverse domains:
- Linear Programming: Traditional solvers lose efficiency during matrix factorization. To counter this, Ian En-Hsu Yen et al. in Sparse Linear Programming via Primal and Dual Augmented Coordinate Descent and Sinong Wang et al. in A New Alternating Direction Method for Linear Programming utilized coordinate descent to solve quadratic subproblems arising from variable splitting, ensuring the computational cost remains proportional to the constraint matrix's non-zero elements.
- Non-negative Least Squares: Jelena Diakonikolas et al. showed in A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data that combining randomized coordinate updates with acceleration techniques keeps the iteration cost proportional to the data matrix's non-zero entries.
- Structured and Nonsmooth Problems: This scaling behavior is also exploited by Di Wang et al. for packing/covering problems in Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction, by Ahmet Alacaoglu et al. for nonsmooth optimization in Smooth Primal-Dual Coordinate Descent Algorithms for Nonsmooth Convex Optimization, by Le Song et al. for network recovery in Time-Varying Dynamic Bayesian Networks, and by Seong Jae Hwang et al. in A Projection Free Method for Generalized Eigenvalue Problem with a Nonsmooth Regularizer.
The Bookkeeping Trick: Tracking Active Support and Residuals
If coordinate descent is so efficient, why isn't it used everywhere? The catch lies in the global state. Many optimization algorithms require tracking global quantities—such as residual matrices, momentum vectors, or gradient histories. If updating a single coordinate requires a full-vector operation to refresh this global state, the computational advantage of the coordinate update is entirely lost.
To solve this, modern sparsity-preserving algorithms employ clever mathematical reformulations to lazily track or isolate updates to the active support of the features.
For example, in matrix factorization, computing a full residual matrix is prohibitively expensive. François Moutier et al. demonstrated in Off-diagonal symmetric nonnegative matrix factorization that coordinate descent can be implemented efficiently by updating only the specific components dictated by the sparse structure of the input, avoiding explicit dense residual calculations.
A similar challenge occurs with momentum. Standard momentum requires updating the velocity vector across all dimensions in every iteration. Nicolas Loizou et al. resolved this in Momentum and Stochastic Momentum for Stochastic Gradient, Newton, Proximal Point and Subspace Descent Methods by introducing Stochastic Momentum, which restricts the momentum update to a randomly selected subset of coordinates. This allows the per-iteration complexity to scale with the number of non-zero elements while maintaining global linear convergence.
Standard Momentum Update (Expensive):
[Update Velocity for All D Dimensions] -> [Touch Every Coordinate]
Stochastic Momentum Update (Sparsity-Aware):
[Identify Active/Selected Coordinates] -> [Update Velocity Only for Active Subset]
Furthermore, Jun Zhu et al. in Distributed Accelerated Proximal Coordinate Gradient Methods reformulated Nesterov's acceleration rules so that updates only modify specific coordinates rather than the entire parameter vector. In the context of projection-free methods, Edward Raff et al. showed in Scaling Up Differentially Private LASSO Regularized Logistic Regression via Faster Frank-Wolfe Iterations that replacing full-dimensional steps with coordinate-specific updates dramatically accelerates high-dimensional sparse training. Finally, Fabian Pedregosa et al. in Proximal Splitting Meets Variance Reduction utilized feature-support reweighting and coordinate-specific tracking to confine updates strictly to the active support of input features.
Naturally Decoupled Concurrency
Beyond single-core efficiency, data sparsity provides a massive structural advantage for distributed and asynchronous computing. In high-dimensional spaces where data vectors are sparse, the probability that two independent processing threads will attempt to update the exact same coordinate at the same time is incredibly low.
H. Brendan McMahan et al. analyzed this phenomenon in Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning. They showed that because feature overlap is rare in sparse regimes, coordinate-wise asynchronous updates can execute across thousands of concurrent threads with minimal synchronization overhead or conflict. Sparsity effectively acts as a natural partitioning mechanism, allowing distributed systems to achieve massive throughput without the bottleneck of centralized locking.
Key Foundational Work
An inexact Levenberg-Marquardt method for large sparse nonlinear least squres (1985) — contributed 2 concept elements to this direction.
Model Selection Through Sparse Maximum Likelihood Estimation for Multivariate Gaussian or Binary Data (2008) — contributed 1 concept elements to this direction.