Sparsity Preserving Iterative Optimization

23 concepts20 papers2 proposals

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:

  1. 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.
  2. 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:

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:

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.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_matrix_vector_product_optimization_99e8f295,
  title = {matrix-vector product optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/matrix-vector-product-optimization/rdr_99e8f2954e0845aeafcfa9f8c9061196},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_matrix_vector_product_optimization_99e8f295_v1,
  title = {matrix-vector product optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/matrix-vector-product-optimization/rdr_99e8f2954e0845aeafcfa9f8c9061196/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake