# Global Minimizers of ℓp-Regularized Objectives Yield the Sparsest ReLU Neural Networks

arXiv: https://arxiv.org/abs/2505.21791 · HTML: https://mlsanity.com/paper/2505.21791/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 60 references that are in the map.
- First posted on arXiv 27 May 2025.

## Builds on (most cited first, 29 of 29)

- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Learning both Weights and Connections for Efficient Neural Networks](https://mlsanity.com/paper/1506.02626/) (2015)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Variational Dropout Sparsifies Deep Neural Networks](https://mlsanity.com/paper/1701.05369/) (2017)
- [Dynamic Network Surgery for Efficient DNNs](https://mlsanity.com/paper/1608.04493/) (2016)
- [Deconstructing Lottery Tickets: Zeros, Signs, and the Supermask](https://mlsanity.com/paper/1905.01067/) (2019)
- [A Systematic DNN Weight Pruning Framework using Alternating Direction Method of Multipliers](https://mlsanity.com/paper/1804.03294/) (2018)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networks](https://mlsanity.com/paper/2002.10553/) (2020)
- [Robust Training under Label Noise by Over-parameterization](https://mlsanity.com/paper/2202.14026/) (2022)
- [Group Sparse Regularization for Deep Neural Networks](https://mlsanity.com/paper/1607.00485/) (2016)
- [Training Sparse Neural Networks](https://mlsanity.com/paper/1611.06694/) (2016)
- [Sparse DNNs with Improved Adversarial Robustness](https://mlsanity.com/paper/1810.09619/) (2018)
- [What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory](https://mlsanity.com/paper/2105.03361/) (2021)
- [Convex Geometry and Duality of Over-parameterized Neural Networks](https://mlsanity.com/paper/2002.11219/) (2020)
- [Penalising the biases in norm regularisation enforces sparsity](https://mlsanity.com/paper/2303.01353/) (2023)
- [Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compression](https://mlsanity.com/paper/2305.16534/) (2023)
- [spred: Solving L1 Penalty with SGD](https://mlsanity.com/paper/2210.01212/) (2022)
- [Achieving Adversarial Robustness via Sparsity](https://mlsanity.com/paper/2009.05423/) (2020)
- [Deep Weight Factorization: Sparse Learning Through the Lens of Artificial Symmetries](https://mlsanity.com/paper/2502.02496/) (2025)
- [Sparsest Piecewise-Linear Regression of One-Dimensional Data](https://mlsanity.com/paper/2003.10112/) (2020)
- [Smoothing the Edges: Smooth Optimization for Sparse Regularization using Hadamard Overparametrization](https://mlsanity.com/paper/2307.03571/) (2023)
- [Bridgeout: stochastic bridge regularization for deep neural networks](https://mlsanity.com/paper/1804.08042/) (2018)
- [Decoupled Weight Decay for Any p Norm](https://mlsanity.com/paper/2404.10824/) (2024)
- [PathProx: A Proximal Gradient Algorithm for Weight Decay Regularized Deep Neural Networks](https://mlsanity.com/paper/2210.03069/) (2022)
- [Sparse Solutions of a Class of Constrained Optimization Problems](https://mlsanity.com/paper/1907.00880/) (2019)

## Abstract (arXiv)

Overparameterized neural networks can interpolate a given dataset in many different ways, prompting the fundamental question: which among these solutions should we prefer, and what explicit regularization strategies will provably yield these solutions? This paper addresses the challenge of finding the sparsest interpolating ReLU network--i.e., the network with the fewest nonzero parameters or neurons--a goal with wide-ranging implications for efficiency, generalization, interpretability, theory, and model compression. Unlike post hoc pruning approaches, we propose a continuous, almost-everywhere differentiable training objective whose global minima are guaranteed to correspond to the sparsest single-hidden-layer ReLU networks that fit the data. This result marks a conceptual advance: it recasts the combinatorial problem of sparse interpolation as a smooth optimization task, potentially enabling the use of gradient-based training methods. Our objective is based on minimizing ℓp quasinorms of the weights for 0 < p < 1, a classical sparsity-promoting strategy in finite-dimensional settings. However, applying these ideas to neural networks presents new challenges: the function class is infinite-dimensional, and the weights are learned using a highly nonconvex objective. We prove that, under our formulation, global minimizers correspond exactly to sparsest solutions. Our work lays a foundation for understanding when and how continuous sparsity-inducing objectives can be leveraged to recover sparse networks through training.