L0 Regularization

L0 regularization is a regularization technique in machine learning and statistics that penalizes the number of nonzero parameters in a model, a quantity written $\lVert \theta \rVert_0$. Unlike L1 regularization (which penalizes the sum of absolute values) or L2 regularization (which penalizes the sum of squared values), L0 regularization directly counts how many parameters are active rather than shrinking their magnitudes. This makes it the most natural formulation for enforcing sparsity, but it also makes the resulting optimization problem NP-hard: for a model with p parameters there are $2^p$ candidate subsets of active parameters, and no algorithm is known that finds the sparsest solution in polynomial time for every instance.^[1] Because of this computational difficulty, researchers rely on approximate and relaxation-based methods, most notably the convex L1 (Lasso) relaxation for linear models^[2] and the differentiable "hard concrete" gates of Louizos, Welling, and Kingma (2018) for deep networks,^[8] with applications spanning neural network pruning, feature selection, best subset selection, and compressed sensing.

Explain like I'm 5 (ELI5)

Imagine you have a big box of crayons but you want to draw a picture using as few crayons as possible. L0 regularization is like a rule that says: "Every crayon you pick up costs you one point." So you try to draw the best picture you can while keeping the number of crayons small. The tricky part is that figuring out which exact set of crayons gives you the best picture with the fewest crayons is really, really hard, even for computers. So instead, people use clever tricks to get close to the best answer without checking every possible combination.

Mathematical definition

The L0 "norm"

For a vector $\mathbf{x} = (x_1, x_2, \ldots, x_p)$, the L0 "norm" is defined as:

$$\lVert \mathbf{x} \rVert_0 = \lvert \{ j : x_j \neq 0 \} \rvert$$

In other words, it is simply the count of nonzero entries in the vector. Despite being commonly referred to as a "norm," the L0 function is technically a pseudonorm because it violates one of the required properties of a true norm: positive homogeneity. For a true norm, scaling a vector by a positive constant k must scale the norm by k as well (i.e., $\lVert k\mathbf{x} \rVert = k \lVert \mathbf{x} \rVert$). The L0 function does not satisfy this property because multiplying all entries by a nonzero scalar does not change the count of nonzero entries. The L0 pseudonorm is also non-convex, which distinguishes it from the L1 and L2 norms.

Regularized objective

Given a dataset of n observations, a loss function $L(\theta)$, and a parameter vector $\theta$, the L0-regularized optimization problem is:

$$\text{minimize} \quad L(\theta) + \lambda \lVert \theta \rVert_0$$

where $\lambda > 0$ is the regularization strength that controls the tradeoff between fitting the data and keeping the model sparse. Larger values of λ encourage sparser solutions by imposing a heavier penalty for each additional nonzero parameter.

In the context of linear regression, this formulation is equivalent to the best subset selection problem, which seeks to find the subset of at most k features that minimizes the residual sum of squares.

Why is L0 regularization NP-hard?

The L0-regularized optimization problem is NP-hard, meaning there is no known algorithm that can solve it in polynomial time for all instances. This was formally established by Natarajan (1995), whose paper "Sparse approximate solutions to linear systems" proved that finding the sparsest solution to a system of linear equations is NP-hard.^[1]

The core difficulty is combinatorial in nature. For a model with p parameters, there are $2^p$ possible subsets of active parameters. Evaluating every subset to find the optimal one becomes computationally infeasible even for moderate values of p. For example, a model with just 50 features has $2^{50}$, roughly $1.13 \times 10^{15}$, possible subsets, which is more than a quadrillion candidate models.

This NP-hardness result has had a lasting impact on the field. For decades, the accepted view in statistics was that best subset selection was impractical beyond roughly 30 to 40 features. This motivated the development of computationally tractable alternatives, most notably L1 regularization (the Lasso).^[2]

How does L0 regularization differ from L1 (Lasso)?

The L1 norm is the tightest convex relaxation of the L0 pseudonorm on the unit hypercube $[-1, 1]^d$. This means that among all convex functions that lower-bound the L0 pseudonorm on that domain, the L1 norm is the largest. This mathematical relationship is why L1 regularization produces sparse solutions: it is the closest convex approximation to directly counting nonzero parameters.

In practice, replacing the L0 penalty with an L1 penalty transforms the NP-hard problem into a convex optimization problem that can be solved efficiently.^[12] In the linear regression setting, this substitution yields the Lasso (Least Absolute Shrinkage and Selection Operator), introduced by Tibshirani in 1996.^[2] In signal processing, the same idea is known as basis pursuit.

However, the L1 relaxation is not without drawbacks. L1 regularization introduces shrinkage bias: it pushes all coefficient estimates toward zero, not just the irrelevant ones. This means that even the truly important features have their coefficients systematically underestimated. L0 regularization, by contrast, imposes no penalty on the magnitude of nonzero parameters. It only cares whether a parameter is zero or not, so the surviving coefficients are unbiased estimates.

Scroll sideways for more →

How does L0 regularization relate to AIC and BIC?

L0 regularization has a direct connection to classical model selection criteria from information theory. When the regularization parameter λ is set to specific values, the L0-penalized objective recovers well-known criteria.

Taking the loss L(θ) to be the negative log-likelihood, setting $\lambda = 1$ corresponds to the Akaike Information Criterion (AIC), which adds a fixed penalty of 2 per parameter to twice the negative log-likelihood (equivalently, a penalty of 1 per parameter to the negative log-likelihood). Setting $\lambda = \frac{1}{2} \log(n)$, where n is the sample size, corresponds to the Bayesian Information Criterion (BIC), whose per-parameter penalty grows with the sample size and therefore favors sparser models on large datasets.

This connection shows that AIC and BIC can be viewed as special cases of L0 regularization with particular choices of the penalty strength. The Louizos et al. (2018) paper on L0 regularization for neural networks made this explicit, stating that "AIC and BIC, well-known model selection criteria, are special cases of L0 regularization," and observing that their method with appropriate λ settings performs AIC- or BIC-style model selection over the network architecture.^[8]

Algorithms and approximate methods

Because exact L0 optimization is NP-hard, a variety of algorithms have been developed to find approximate solutions. These can be grouped into several families.

Greedy algorithms

Greedy methods build sparse solutions incrementally by adding or removing one feature at a time.

Forward stepwise selection starts with an empty model and adds the feature that most improves the objective at each step. Backward stepwise elimination starts with all features and removes the least useful one at each step. Matching pursuit and its variants (orthogonal matching pursuit, or OMP) iteratively select the dictionary atom most correlated with the current residual, making them particularly popular in signal processing and compressed sensing.^[12]

These methods are fast and simple to implement, but they provide no guarantee of finding the globally optimal solution. A feature added early on may not be optimal given features added later.

Iterative hard thresholding (IHT)

Iterative hard thresholding, introduced by Blumensath and Davies (2009), is a projected gradient descent method for L0-constrained problems.^[5] At each iteration, it takes a gradient step and then applies a hard thresholding operator that keeps only the k largest-magnitude components and sets the rest to zero.

The update rule is:

$$\theta^{(t+1)} = H_k(\theta^{(t)} - \eta \nabla L(\theta^{(t)}))$$

where $H_k$ denotes the hard thresholding operator that retains the top k entries and $\eta$ is the step size. IHT has convergence guarantees under the restricted isometry property (RIP), a condition commonly studied in compressed sensing.^[5] Hard thresholding pursuit (HTP) combines IHT with debiasing steps, improving recovery performance.

Smoothed L0 (SL0)

The smoothed L0 algorithm, proposed by Mohimani, Babaie-Zadeh, and Jutten (2009), approximates the L0 norm with a smooth function.^[6] Instead of counting the number of nonzero entries directly, it replaces the discontinuous indicator function with a family of Gaussian-based approximations parameterized by $\sigma$:

$$F_\sigma(\mathbf{x}) = \sum_j \left( 1 - \exp\left( -\frac{x_j^2}{2\sigma^2} \right) \right)$$

As $\sigma$ approaches zero, $F_\sigma$ converges to the L0 norm. The algorithm proceeds by gradually decreasing σ, solving a smooth optimization problem at each stage. The authors report that SL0 is "about two to three orders of magnitude faster than the state-of-the-art interior-point LP solvers, while providing the same (or better) accuracy," a large speedup over the linear programming approach used for L1 minimization.^[6]

Mixed integer programming (MIP)

Bertsimas, King, and Mazumder (2016) demonstrated that best subset selection can be formulated as a mixed integer optimization (MIO) problem and solved to provable global optimality using modern solvers.^[7] They observed that in the period 1991 to 2015, algorithmic advances in MIO combined with hardware improvements had produced "an astonishing 450 billion factor speedup in solving MIO problems," making exact L0 optimization feasible for problems with hundreds or even thousands of features.^[7] Their approach solves instances with n in the thousands and p in the hundreds to provable optimality in minutes.

Their method provides certificates of optimality (or bounded suboptimality if terminated early) and can incorporate additional constraints on the coefficients. This work challenged the prevailing assumption that best subset selection was impractical, though it remains computationally expensive for very large-scale problems.

Penalty decomposition and ADMM

Alternating direction method of multipliers (ADMM) and penalty decomposition methods reformulate the L0-regularized problem by introducing auxiliary variables and decomposing it into subproblems that are easier to solve individually. These methods alternate between updating the model parameters (using standard gradient-based methods) and applying a hard thresholding step to the auxiliary variables. They are particularly useful for structured sparsity problems where groups of parameters should be zeroed out together.

How is L0 regularization used in neural networks?

The Louizos, Welling, and Kingma method (2018)

The most influential approach to applying L0 regularization to deep learning was proposed by Louizos, Welling, and Kingma at ICLR 2018 in their paper "Learning Sparse Neural Networks through L0 Regularization."^[8] As the authors put it, "We propose a practical method for L0 norm regularization for neural networks: pruning the network during training by encouraging weights to become exactly zero."^[8] Their method addresses the fundamental challenge that the L0 norm is both non-differentiable and combinatorial, making it incompatible with standard stochastic gradient descent training.

Stochastic gates

The key idea is to introduce a learnable binary gate $z_j$ for each weight $\theta_j$ in the network. The effective weight becomes:

$$\theta_j^{(\text{eff})} = \theta_j z_j$$

where $z_j$ is either 0 (weight removed) or 1 (weight kept). If $z_j$ follows a Bernoulli distribution with parameter $\pi_j$, then the expected L0 norm is simply the sum of the gate probabilities:

$$\mathbb{E}[\lVert \theta^{(\text{eff})} \rVert_0] = \sum_j \pi_j$$

This expected L0 cost is differentiable with respect to the gate parameters $\pi_j$, allowing it to be optimized with gradient-based methods.

The hard concrete distribution

Sampling from Bernoulli distributions is not differentiable, so the authors use the reparameterization trick with a continuous relaxation called the hard concrete distribution. This distribution is, in the authors' words, "obtained by stretching a binary concrete distribution and then transforming its samples with a hard-sigmoid," and it is constructed in three steps:

1. Sample from a binary concrete (Gumbel-softmax) distribution: $s = \sigma\left( \frac{\log u - \log(1-u) + \log \alpha}{\beta} \right)$, where u is drawn from Uniform(0, 1), $\log \alpha$ is a learnable location parameter, and $\beta$ is a temperature parameter.

2. Stretch the samples beyond [0, 1]: $s' = s(\zeta - \gamma) + \gamma$, where $\gamma < 0$ and $\zeta > 1$ are constants that extend the support of the distribution to $(\gamma, \zeta)$.

3. Apply a hard sigmoid: $z = \min(1, \max(0, s'))$, which clips the stretched samples to [0, 1], creating exact zeros and ones at the boundaries.

In all of their experiments the authors fix $\gamma = -0.1$ and $\zeta = 1.1$, and (following Maddison et al., 2016) set the temperature $\beta = 2/3$.^[8] The hard concrete distribution concentrates probability mass at exactly 0 and exactly 1, mimicking the discrete Bernoulli distribution while remaining differentiable. The expected L0 cost under this distribution has a closed-form expression involving a sigmoid function of the gate parameters.

Experimental results

Louizos et al. evaluated their method on MNIST (using LeNet-300-100 and LeNet-5 architectures) and CIFAR-10/CIFAR-100 (using Wide Residual Networks, WRN-28-10). On the CIFAR benchmarks the L0-regularized WRN used $\lambda = 0.001/N$, and the reported figures are the median test error over 5 runs after 200 epochs. Key findings included:

Scroll sideways for more →

On the CIFAR experiments, L0 regularization not only matched but slightly outperformed dropout-based regularization, while simultaneously reducing the number of floating-point operations during both training and inference.^[8] The method achieved substantial compression on the LeNet architectures with minimal loss in accuracy.

Continuous sparsification (2020)

Savarese, Silva, and Maire (NeurIPS 2020) proposed continuous sparsification, a deterministic alternative to the stochastic gates of Louizos et al.^[10] Their method constructs a smooth continuation path connecting a soft-gated L1-like objective to the intractable L0-regularized objective. A hyperparameter $\beta$ controls the hardness of the objective: as $\beta$ increases from 1 toward infinity, the objective transitions from L1 regularization to L0 regularization.

By gradually increasing $\beta$ during training, the method continuously sparsifies the network without requiring heuristic decisions about which parameters to remove or when to remove them. The authors report that continuous sparsification surpasses the previous state of the art on both network pruning and lottery-ticket ("winning ticket") search across VGG trained on CIFAR-10 and ResNet-50 trained on ImageNet, while enabling fast parallel ticket search.^[10]

Structured sparsity with L0

L0 regularization can be extended from individual weight pruning to structured pruning, where entire neurons, channels, or attention heads are removed together. This is more useful in practice because modern hardware (GPUs, TPUs) cannot easily exploit unstructured sparsity for speed gains.^[11] Structured L0 regularization applies gates at the level of groups rather than individual weights, enabling the removal of entire computational units and producing models that are genuinely faster on standard hardware.^[11]

How does L0 regularization relate to the lottery ticket hypothesis?

The lottery ticket hypothesis, proposed by Frankle and Carbin in the ICLR 2019 best-paper-award-winning "The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks," states that "dense, randomly-initialized, feed-forward networks contain subnetworks ('winning tickets') that, when trained in isolation, reach test accuracy comparable to the original network in a similar number of iterations."^[9] The paper opens by noting that "neural network pruning techniques can reduce the parameter counts of trained networks by over 90%," which motivates the search for these compact subnetworks.^[9]

L0 regularization provides a principled, optimization-based approach to finding such subnetworks. Rather than relying on the heuristic process of training, pruning by magnitude, rewinding to initial weights, and repeating (iterative magnitude pruning), L0 regularization learns which weights to keep and which to discard during a single training run by optimizing the gate parameters alongside the network weights.

Continuous sparsification methods based on L0 approximations have been shown to find winning tickets that are competitive with, and in several settings better than, those discovered by iterative magnitude pruning,^[10] suggesting that L0 regularization captures the same structural insights as the lottery ticket hypothesis but through a more direct optimization framework.^[9]

Applications

Compressed sensing

Compressed sensing is the field where L0 minimization has its deepest theoretical roots. The problem is to recover a sparse signal $\mathbf{x}$ from an underdetermined system of linear measurements $\mathbf{y} = A\mathbf{x}$, where A is a measurement matrix with fewer rows than columns. The ideal recovery algorithm would solve:

$$\text{minimize} \quad \lVert \mathbf{x} \rVert_0 \quad \text{subject to} \quad A\mathbf{x} = \mathbf{y}$$

Donoho (2006) and Candes, Romberg, and Tao (2006) proved that under certain conditions on the measurement matrix (the restricted isometry property), the L1 minimization problem recovers the same sparse solution as the L0 problem.^[3][4] This theoretical result provides the foundation for compressed sensing and has enabled applications in magnetic resonance imaging (MRI), where the technique allows faster acquisition by measuring fewer Fourier coefficients, and in radar, seismology, and astronomical imaging.^[3]

Feature selection

In statistical modeling, L0 regularization is the most direct formulation of the feature selection problem: select the smallest subset of features that adequately explains the response variable. Applications include genomics (identifying relevant genes from thousands of candidates), finance (selecting predictive factors for asset returns), and clinical research (finding diagnostic biomarkers from high-dimensional patient data).

Neural network compression

L0 regularization enables the training of sparse neural networks that require fewer parameters, less memory, and fewer computations at inference time.^[11] This is valuable for deploying models on resource-constrained devices such as mobile phones and embedded systems. By learning which weights (or entire neurons and channels) to remove during training, L0-based methods produce compressed models without a separate post-training pruning step.

Variable selection in graphical models

L0 penalties are used to learn the structure of graphical models, such as Gaussian graphical models and Bayesian networks, where the goal is to identify which edges (conditional dependencies) exist in the graph. The L0 penalty directly controls the number of edges, producing interpretable models with known sparsity levels.

What are the limitations of L0 regularization?

Despite its theoretical appeal, L0 regularization faces several practical challenges.

Computational cost. Even with approximate methods, L0 regularization is more expensive than L1 or L2 regularization. Stochastic gate methods introduce additional parameters (the gate distributions), and mixed integer programming approaches scale poorly to very large problems.

Non-convexity and local minima. The L0 objective is non-convex, meaning that gradient-based methods can converge to different solutions depending on initialization. There is no guarantee that the solution found is globally optimal, unlike L1 regularization, which has a unique global minimum (when the loss function is convex).

Hyperparameter sensitivity. The regularization strength λ, along with additional parameters introduced by relaxation methods (temperatures, stretch constants, etc.), must be carefully tuned. The performance of L0 methods can be sensitive to these choices.

Discrete-continuous gap. Continuous relaxations of the L0 norm (such as the hard concrete distribution) approximate the discrete counting function, but the gap between the relaxation and the true L0 objective can lead to solutions that are not perfectly sparse or that differ from the true L0 optimum.

Scalability to modern architectures. While L0 regularization has been demonstrated on moderately sized networks (LeNet, Wide Residual Networks), applying it to very large models with billions of parameters, such as modern large language models, remains an active research challenge. The additional memory and computation required for the gate parameters can be substantial at this scale.

Comparison of L0 optimization algorithms

Scroll sideways for more →

See also

• Regularization
• L1 regularization
• L2 regularization
• Sparsity
• Overfitting
• Feature engineering
• Dropout regularization
• Convex optimization
• Lottery ticket hypothesis
• Neural network

References

1. Natarajan, B. K. (1995). "Sparse approximate solutions to linear systems." *SIAM Journal on Computing*, 24(2), 227-234. doi:10.1137/S0097539792240406. ↩
2. Tibshirani, R. (1996). "Regression shrinkage and selection via the lasso." *Journal of the Royal Statistical Society: Series B*, 58(1), 267-288. ↩
3. Donoho, D. L. (2006). "Compressed sensing." *IEEE Transactions on Information Theory*, 52(4), 1289-1306. ↩
4. Candes, E. J., Romberg, J., & Tao, T. (2006). "Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information." *IEEE Transactions on Information Theory*, 52(2), 489-509. ↩
5. Blumensath, T., & Davies, M. E. (2009). "Iterative hard thresholding for compressed sensing." *Applied and Computational Harmonic Analysis*, 27(3), 265-274. doi:10.1016/j.acha.2009.04.002. ↩
6. Mohimani, H., Babaie-Zadeh, M., & Jutten, C. (2009). "A fast approach for overcomplete sparse decomposition based on smoothed L0 norm." *IEEE Transactions on Signal Processing*, 57(1), 289-301. ↩
7. Bertsimas, D., King, A., & Mazumder, R. (2016). "Best subset selection via a modern optimization lens." *The Annals of Statistics*, 44(2), 813-852. arXiv:1507.03133. ↩
8. Louizos, C., Welling, M., & Kingma, D. P. (2018). "Learning Sparse Neural Networks through L0 Regularization." *International Conference on Learning Representations (ICLR)*. arXiv:1712.01312. ↩
9. Frankle, J., & Carbin, M. (2019). "The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks." *International Conference on Learning Representations (ICLR)*, best paper award. arXiv:1803.03635. ↩
10. Savarese, P., Silva, H., & Maire, M. (2020). "Winning the Lottery with Continuous Sparsification." *Advances in Neural Information Processing Systems (NeurIPS)*. arXiv:1912.04427. ↩
11. Hoefler, T., Alistarh, D., Ben-Nun, T., Dryden, N., & Peste, A. (2021). "Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks." *Journal of Machine Learning Research*, 22(241), 1-124. ↩
12. Bach, F., Jenatton, R., Mairal, J., & Obozinski, G. (2012). "Optimization with Sparsity-Inducing Penalties." *Foundations and Trends in Machine Learning*, 4(1), 1-106. ↩