Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks

• URL: http://arxiv.org/abs/2505.21791v1
• Date: Tue, 27 May 2025 21:46:27 GMT
• Title: Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks
• Authors: Julia Nakhleh, Robert D. Nowak,
• Abstract summary: We propose a continuous, almost-everywhere differentiable training objective whose global minima are guaranteed to correspond to sparsest networks.<n>We prove that, under our formulation, global minimizers correspond exactly to sparsest solutions.
• Score: 15.385743143648574
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\ell^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.

Related papers

• Universal Consistency of Wide and Deep ReLU Neural Networks and Minimax Optimal Convergence Rates for Kolmogorov-Donoho Optimal Function Classes [7.433327915285969]
  We prove the universal consistency of wide and deep ReLU neural network classifiers trained on the logistic loss. We also give sufficient conditions for a class of probability measures for which classifiers based on neural networks achieve minimax optimal rates of convergence.
  arXiv  Detail & Related papers  (2024-01-08T23:54:46Z)
• Fixing the NTK: From Neural Network Linearizations to Exact Convex Programs [63.768739279562105]
  We show that for a particular choice of mask weights that do not depend on the learning targets, this kernel is equivalent to the NTK of the gated ReLU network on the training data. A consequence of this lack of dependence on the targets is that the NTK cannot perform better than the optimal MKL kernel on the training set.
  arXiv  Detail & Related papers  (2023-09-26T17:42:52Z)
• Does a sparse ReLU network training problem always admit an optimum? [0.0]
  We show that the existence of an optimal solution is not always guaranteed, especially in the context of sparse ReLU neural networks. In particular, we first show that optimization problems involving deep networks with certain sparsity patterns do not always have optimal parameters.
  arXiv  Detail & Related papers  (2023-06-05T08:01:50Z)
• Globally Optimal Training of Neural Networks with Threshold Activation Functions [63.03759813952481]
  We study weight decay regularized training problems of deep neural networks with threshold activations. We derive a simplified convex optimization formulation when the dataset can be shattered at a certain layer of the network.
  arXiv  Detail & Related papers  (2023-03-06T18:59:13Z)
• On the Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  We show that gradient flow converges in direction when labels are determined by the sign of a target network with $r$ neurons. Our result may already hold for mild over- parameterization, where the width is $tildemathcalO(r)$ and independent of the sample size.
  arXiv  Detail & Related papers  (2022-05-18T16:57:10Z)
• Subquadratic Overparameterization for Shallow Neural Networks [60.721751363271146]
  We provide an analytical framework that allows us to adopt standard neural training strategies. We achieve the desiderata viaak-Lojasiewicz, smoothness, and standard assumptions.
  arXiv  Detail & Related papers  (2021-11-02T20:24:01Z)
• Edge Rewiring Goes Neural: Boosting Network Resilience via Policy Gradient [62.660451283548724]
  ResiNet is a reinforcement learning framework to discover resilient network topologies against various disasters and attacks. We show that ResiNet achieves a near-optimal resilience gain on multiple graphs while balancing the utility, with a large margin compared to existing approaches.
  arXiv  Detail & Related papers  (2021-10-18T06:14:28Z)
• A Geometric Analysis of Neural Collapse with Unconstrained Features [40.66585948844492]
  We provide the first global optimization landscape analysis of $Neural;Collapse$. This phenomenon arises in the last-layer classifiers and features of neural networks during the terminal phase of training.
  arXiv  Detail & Related papers  (2021-05-06T00:00:50Z)
• Modeling from Features: a Mean-field Framework for Over-parameterized Deep Neural Networks [54.27962244835622]
  This paper proposes a new mean-field framework for over- parameterized deep neural networks (DNNs) In this framework, a DNN is represented by probability measures and functions over its features in the continuous limit. We illustrate the framework via the standard DNN and the Residual Network (Res-Net) architectures.
  arXiv  Detail & Related papers  (2020-07-03T01:37:16Z)
• On Sparsity in Overparametrised Shallow ReLU Networks [42.33056643582297]
  We study the ability of different regularisation strategies to capture solutions requiring only a finite amount of neurons, even on the infinitely wide regime. We establish that both schemes are minimised by functions having only a finite number of neurons, irrespective of the amount of overparametrisation.
  arXiv  Detail & Related papers  (2020-06-18T01:35:26Z)
• Projection Neural Network for a Class of Sparse Regression Problems with Cardinality Penalty [9.698438188398434]
  We consider a class of sparse regression problems, whose objective function is the summation of a convex loss function and a cardinality penalty. By constructing a smoothing function for the cardinality function, we propose a projected neural network and design a correction method for solving this problem. The solution of the proposed neural network is unique, global existent, bounded and globally Lipschitz continuous.
  arXiv  Detail & Related papers  (2020-04-02T08:05:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.