Direct Sparsity Optimization via L0 Regularization

40 concepts32 papers1 proposal

In machine learning, we often want models that are sparse—meaning they rely on only a small subset of available features. Traditionally, researchers have relied on the $L_1$ norm (Lasso) as a "proxy" for sparsity because it is convex and easy to optimize. However, a growing body of research argues that we should stop using proxies and instead optimize the $L_0$ norm—the actual count of non-zero elements—directly.

The Problem with Convex Proxies

The primary reason to move beyond $L_1$ regularization is a phenomenon known as shrinkage. Because the $L_1$ penalty is proportional to the absolute value of the weights, it doesn't just push irrelevant weights to zero; it also systematically underestimates the magnitude of the important ones.

Rajamanoharan et al. demonstrate that this magnitude distortion significantly harms reconstruction fidelity in models like sparse autoencoders. By switching to direct $L_0$ optimization, the authors show that models can preserve the original scale of activations, leading to a better Pareto frontier between sparsity and accuracy. Liu et al. further argue that this lack of shrinkage bias allows for more accurate representations of feature importance, which is critical for human-interpretable models.

Mechanics of Direct Sparsity

If $L_0$ is better, why haven't we always used it? The $L_0$ norm is non-convex and discontinuous, making it a combinatorial nightmare for standard gradient descent. Recent work, however, has developed several clever mechanisms to make this optimization tractable.

Hard Thresholding and Projections

Instead of "softly" shrinking weights toward zero, direct methods often use Hard Thresholding (HT). In this approach, the algorithm performs a standard gradient step and then "projects" the result back onto the space of sparse vectors by keeping only the top-$k$ largest values and setting the rest to exactly zero.

Xu and Xu show that these projections can often be computed in linear time, making them highly efficient for large-scale problems like index tracking in finance. Similarly, Zhang et al. utilize non-monotone iterative hard thresholding to achieve strictly sparse solutions in brain microstructure mapping, avoiding the suboptimality and re-weighting requirements of $L_1$ relaxations.

Discrete and Mixed-Integer Optimization

Another path to $L_0$ is treating sparsity as a discrete selection problem. Kamiya et al. utilize Mixed-Integer Optimization (MIO) to strictly limit the number of non-zero parameters to a predefined budget. This discrete approach ensures the model adheres to strict sparsity requirements without the need for post-hoc thresholding or heuristic ranking, which Guo et al. and Zhang et al. identify as a major source of noise in unsupervised feature selection.

Bridging the Gap with DC Programming

To handle the non-convexity of $L_0$ without falling into the traps of local minima, researchers have turned to Difference of Convex (DC) programming. This framework reformulates the $L_0$ constraint as the difference between two convex functions.

Thiao et al. show that this reformulation allows for exact sparsity optimization in eigenvalue problems, ensuring that solutions maintain physical properties like orthogonality that are often lost during convex relaxation. To speed this up, Yuan et al. propose block decomposition algorithms that perform exhaustive searches over small subsets of variables, finding "stronger" stationary points than simple coordinate descent.

Why Direct Optimization Works

The shift toward direct $L_0$ optimization works because it aligns the optimization objective with the actual goal of the researcher.

  1. Noise Robustness: In high-dimensional spaces filled with "distractor" features, $L_1$ often fails to produce exact zeros, leaving the model susceptible to noise. Gao et al. demonstrate that enforcing $L_0$ sparsity allows reinforcement learning agents to automatically filter out irrelevant observations, significantly outperforming standard baselines in noisy environments.
  2. Interpretability: For high-stakes domains like medicine or credit scoring, a model must be simple enough for a human to audit. McTavish et al. use $L_0$ regularization to constrain the cardinality of Generalized Additive Models, ensuring they remain sparse and interpretable even when dealing with complex missing data.
  3. Computational Efficiency: While $L_0$ was once considered computationally impossible, modern algorithms have changed the landscape. Liu et al. show that by discretizing the parameter space, $L_0$ can be incorporated directly as a unary potential in a graphical model, making principled feature selection a straightforward part of the training process.

By moving away from the "soft" approximations of the past, these direct methods provide a more precise, unbiased, and ultimately more interpretable way to navigate the curse of dimensionality.

Key Foundational Work

Zero Norm Least Squares Proximal SVR (2009) — contributed 1 concept elements to this direction.
Boosting Classifiers with Tightened L0-Relaxation Penalties (2010) — contributed 1 concept elements to this direction.
A DC Programming Approach for Sparse Eigenvalue Problem (2010) — 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_direct_sparsity_optimization_682efe8c,
  title = {direct sparsity optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/direct-sparsity-optimization/rdr_682efe8c34bc4de398155f82859dcacc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_direct_sparsity_optimization_682efe8c_v1,
  title = {direct sparsity optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/direct-sparsity-optimization/rdr_682efe8c34bc4de398155f82859dcacc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake