Research map / Architectures and efficiency / RNNs and normalization
Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that minimizing the ℓ^p path norm (0<p<1) of single-hidden-layer ReLU networks yields sparsest interpolants for small p, with univariate uniqueness and N-2 neuron bounds, and reports small synthetic experiments with a reweighted ℓ1 proximal method.
Problem
Finding the sparsest (fewest active neurons / nonzero parameters) single-hidden-layer ReLU network that interpolates a dataset, a combinatorial ℓ0 problem, in a form amenable to gradient-based training.
Approach
Replace the ℓ0 path norm with the ℓp path norm (0<p<1), a continuous almost-everywhere differentiable penalty; show via a variational CPWL reformulation that its global minimizers are sparsest interpolants for sufficiently small p, and in the univariate case that they are also ℓ1 minimizers with at most N-2 neurons and unique for almost every p.
Key results
- For univariate data, the p=0.4 regularized network recovers the true sparsest solution, while Adam and AdamW do not.
- In the multivariate synthetic experiment, all ℓp-regularized networks obey the theoretical sparsity upper bound, with p=0.4 sparsest.
- Theory: for univariate data any minimum ℓp path norm interpolant (0<p<1) has at most N-2 active neurons and is also an ℓ1 minimizer.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ℓ^p path-norm regularization with sufficiently small p instead of minimizing the ℓ^0 path norm directly | Single-hidden-layer ReLU networks · Arbitrary-dimensional interpolation | sparsity | Helped |
| Use ℓ^p path-norm regularization for 0 < p < 1 instead of ℓ^1 path-norm regularization | Univariate single-hidden-layer ReLU networks · Univariate interpolation | maximum number of active neurons | Helped |
| Use ℓ^p path-norm regularization with sufficiently small p | ReLU networks trained with the reweighted ℓ^1 algorithm · Synthetic univariate peak/plateau dataset | sparsity | Helped |
| Use ℓ^p path-norm regularization instead of unregularized Adam or AdamW weight decay | ReLU networks trained with the reweighted ℓ^1 algorithm · Synthetic datasets | sparsity during training | Helped |
| Reduce p from 0.7 or 1 to 0.4 | ReLU networks trained with the reweighted ℓ^1 algorithm · Synthetic datasets | sparsity during training | Helped |
| Use ℓ^p path-norm regularization with p in {0.4, 0.7, 1} | ReLU networks trained with the reweighted ℓ^1 algorithm · High-dimensional synthetic data and labels | sparsity | Helped |
Surprising findings
- Minimum ℓ1 path norm interpolants are not guaranteed to be sparse and may have arbitrarily many neurons, unlike ℓp minimizers for p<1.
Limitations
- Critical threshold p* is not computable efficiently; proofs only show existence.
- Multivariate analysis does not recover univariate uniqueness or ℓ1-minimality results.
- Experiments are limited to simple synthetic data.
Experimental setup
Datasets: synthetic univariate peak/plateau dataset synthetic high-dimensional random data and labels
Benchmarks: synthetic univariate peak/plateau dataset synthetic high-dimensional random data
Metrics: number of nonzero parameters / active neurons over training
Baselines: Adam AdamW ℓ1 path norm (p=1)
Builds on: ℓ1 path norm minimization bridge regression iteratively reweighted ℓ1
Closest papers by meaning
- Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes (NeurIPS 2024 · similarity 0.90)
- Simplicity Bias and Optimization Threshold in Two-Layer ReLU Networks (ICML 2025 · similarity 0.90)
- Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.90)
- A Single-Step, Sharpness-Aware Minimization is All You Need to Achieve Efficient and Accurate Sparse Training (NeurIPS 2024 · similarity 0.89)
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time (ICML 2024 · similarity 0.89)
- Stable Minima of ReLU Neural Networks Suffer from the Curse of Dimensionality: The Neural Shattering Phenomenon (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.