Global Minimizers of ℓ p \ell^{p} -Regularized Objectives Yield the Sparsest ReLU Neural Networks
Julia Nakhleh, Robert D. Nowak · 2025
Read Global Minimizers of ℓ p \ell^{p} -Regularized Objectives Yield the Sparsest ReLU Neural Networks by Julia Nakhleh, Robert D. Nowak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21791.txt.
Introduction
Julia Nakhleh and Robert Nowak wrote this paper in two thousand twenty-five. It proves that training a ReLU network with a sparsity-driving penalty, pushed to its global best, yields the sparsest network that fits the data.
Wide nets can fit a set in many ways, so which fit to pick is a real ask. Pruning after the fact is the usual tack. The authors give a smooth training goal based on small-power norms of the weights. Its global minima are shown to be exactly the sparsest one-hidden-layer ReLU nets that match the data. The combinatorial hunt for the sparsest fit thus turns into a smooth climb that gradient methods can walk.
Catalog record
| CREATOR | Julia Nakhleh, Robert D. Nowak |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 120 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21791
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Global Minimizers of ℓ p \ell^{p} -Regularized Objectives Yield the Sparsest ReLU Neural Networks Julia Nakhleh, Robert D. Nowak Abstract 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 \ell^{p} quasinorms of the weights for 0 < p < 1 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. 1 Introduction Highly overparameterized neural networks have become the workhorse of modern machine learning. Because these networks can interpolate a given dataset in many different ways (see e.g. Figs. 1(b) and 1(c) ), explicit regularization is frequently incorporated into the training procedure to favor solutions that are, in some sense, more regular or desirable. In this work, we focus on explicit regularizers which yield sparse single-hidden-layer ReLU interpolating networks, which for our purposes are those with the fewest nonzero input weight/bias parameters among the active neurons. 1 1 1 In the univariate-input case, this is equivalent to the count of active neurons. Sparse models are particularly desirable for computational efficiency purposes, as they have lower storage requirements and computational overhead when deployed at inference time, and may have other attractive properties in terms of generalization, interpretability, and robustness ( Mozer and Smolensky (1988) ; Guo et al. (2018) ; Liao et al. (2022) ; Liu et al. (2022) , among many others). Although a myriad of sparsity-inducing training schemes have been proposed in the neural network literature, almost none of them have actually been proven to yield true sparsest solutions, and the justifications for their use remain almost entirely heuristic and/or empirical. Furthermore, many such strategies rely on complex pruning pipelines—composed of iterative magnitude thresholding, fine-tuning, and sensitivity analyses—which are computationally costly, difficult to implement, and offer no theoretical guarantees in terms of the resulting sparsity. In contrast, we propose a simple regularization objective, based on the \ell^{p} quasinorm of the network weights for 0<p<1 , whose global minimizer is provably a sparsest interpolating ReLU network for sufficiently small p . This objective is continuous and differentiable away from zero, making it compatible with gradient descent. Although \ell^{p} -norm minimization with 0<p<1 has been studied in finite-dimensional linear problems (most extensively in the context of compressed sensing), where it is known to guarantee sparsity under certain assumptions on the data/measurements, its behavior in the context of neural networks—wherein the features themselves are continuously parameterized and data-adaptive—is challenging to characterize mathematically, and to our knowledge, we are the first to do so. Specifically, our contributions are the following: 1. Sparsity, uniqueness, and width/parameter bounds for univariate \ell^{p} -regularized networks. In Section 3 , we prove that, for single-hidden-layer ReLU networks of input dimension one, minimizing the network’s \ell^{p} path norm (see ( 2 )) implicitly minimizes both its \ell^{1} path norm (i.e., the total variation of its derivative) and, for sufficiently small p>0 , its \ell^{0} path norm (total knot/neuron count). We show that for any 0<p<1 , a minimum \ell^{p} path norm interpolant of N data points has no more than N-2 active neurons. In contrast, \ell^{1} path norm minimization alone is not guaranteed to implicitly minimize sparsity, and may yield solutions with arbitrarily many neurons ( Fig. 1(a) ). Our result follows from reframing the network training problem as an optimization over continuous piecewise linear (CPWL) functions which interpolate a dataset with minimal p -variation ( 6 ) of the derivative. Using this variational framework, we can explicitly describe the optimal functions’ behavior based on the geometry of the data points. This characterization provides data-dependent bounds on the sparsity and weight magnitudes of such minimum- \ell^{p} solutions, and highlights an easily-verifiable condition on the data under which \ell^{p} minimization for any 0<p<1 yields a sparsest interpolant ( \ell^{0} solution). Additionally, our analysis shows that the solution to the univariate \ell^{p} minimization problem is unique for almost every 0<p<1 ; in contrast, univariate \ell^{0} and \ell^{1} solutions are both known to be non-unique in general ( Debarre et al. (2022) ; Hanin (2022) ). 2. Exact sparsity in arbitrary input dimensions. In Section 4 , we show for networks of arbitrary input dimension that the problem of minimizing the network’s \ell^{p} path norm can be recast as a finite-dimensional minimization of a continuous, strictly concave function over a polytope. 2 2 2 We use polyhedron to refer to an intersection of finitely many closed halfspaces, and polytope to refer to a bounded polyhedron. Both are necessarily convex. Using this reformulation, we show that there always exists some data-dependent threshold p^{*} below which \ell^{p} minimization recovers an \ell^{0} (sparsest) solution, in terms of the count of nonzero parameters of the active neurons in the network. We also show that no \ell^{p} (for any 0<p<1 ) or \ell^{0} solutions has more than N active neurons and, if the data is in general position, any \ell^{0} solution has O(N) active input weight/bias parameters among these active neurons ( Proposition 4.1 ). 3. A principled, differentiable objective for sparse ReLU networks. Our theory provides the first rigorous justification for using a smooth \ell^{p} penalty for 0<p<1 to obtain truly sparsest interpolating ReLU networks via gradient-based methods—no pruning or complex post-hoc approaches required. (a) (b) (c) Figure 1 : Fig. 1(a) shows several univariate min- \ell^{1} path norm interpolants of a given dataset. Such solutions are generally non-unique, and always include at least one sparsest interpolant (black), but also include arbitrarily non-sparse interpolants (blue, red, green). Figs. 1(b) and 1(c) : two different ReLU network interpolants of the same 2D dataset with different numbers of active neurons and parameters. Fig. 1(b) has 5 nonzero input weight/bias parameters (its \ell^{0} path norm as in ( 9 )), while Fig. 1(c) has 16. 2 Related work Sparsity via \ell^{p} minimization in finite-dimensional linear models: \ell^{p} penalties with 0<p\leq 1 for linear constraint problems have been studied extensively in the compressed sensing literature, and have been shown to yield exact \ell^{0} minimizers under certain conditions (typically involving restricted isometry and/or null-space constants) on the measurement matrix ( Candes and Tao (2005) ; Chartrand (2007) ; Chartrand and Staneva (2008) ; Foucart and Lai (2009) ). Such penalties have also been studied in the statistics literature under the