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

We thank the reviewer for their feedback, but we think there may be some important misunderstandings regarding the key elements of our paper. Below we address the questions and concerns individually.

• Role of the "concave-over-polytope" problem reformulation: the reviewer seems to severely misunderstand the role that our reformulation of the multivariate neural network training problem (as a concave minimization over a linear constraint set) plays in our analysis. We do not propose this reformulation as part of an algorithm for $\ell^p$ path norm neural network minimization problem; nowhere in the paper do we propose any algorithm. Rather, this reformulation is a proof technique for showing $\ell^p$ path norm minimization with neural networks recovers $\ell^0$ solutions for sufficiently small $p$. Therefore, this reformulation is not something which needs to be tested numerically.

• Extension to deeper networks: we agree that extending our results to deeper networks would be interesting and desirable. We conjecture that this is probably possible, but difficult, and would require different proof techniques than the ones used in our results. Specifically, the difficulties in extending our proofs to deep networks are the following:

  • Univariate deep networks: like shallow, these are CPWL functions, but the relationship between the knots in the function and the neurons is more complex than in the shallow case. Specifically, modifying a single neuron of a shallow univariate network only produces a local change in the represented function, but for deep univariate networks, modifying neurons in deeper layers can produce global changes in the represented function. This makes our proof approach for the univariate shallow case difficult to apply to deep networks.
  • Multivariate deep networks: although [1] develops a reformulation of three-layer ReLU network training as a linear constraint problem, similar to the two-layer formulation that inspires our proof approach, the resulting reformulated problem minimizes an $\ell^{2,p}$ group norm (rather than an $\ell^p$ norm) subject to a set of linear constraints. Unlike the $\ell^p$ norm, the $\ell^{2,p}$ group norm is neither convex nor concave, so our arguments here also do not readily extend to the deep case.

  Thus, any extension to deeper networks would likely require different proof strategies than those used in our paper. Nonetheless, we believe that our results for the shallow case are valuable, as they provide (to our knowledge) the first sparse recovery guarantee for neural networks with arbitrary data, and develop innovative proof techniques for analyzing $\ell^p$ minimization in the highly nonlinear, nonconvex neural network context.

[1] Ergen and Pilanci. "Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs." 2021.

• Computation of the critical threshold $p^*$: our proofs do highlight a possible approach for computing p*----in both the univariate and multivariate cases, this can be done by enumerating and searching over the extreme points of a polytope determined by data-dependent constraints. However, there may be an enormous number of these extreme points (exponential or super-exponential in the number of data points $N$), which makes computing this value impractical. We conjecture that this difficulty may be unavoidable, because even for the simpler linear problem $\min_x \\| x \\|_p^p \ \textrm{s.t.} \ Ax = b$ with $0 < p \leq 1$, computation of restricted isometry and null space constants (which play a similar role in determining sufficient conditions for this problem to recover $\ell^0$ minimizers) is known to be NP hard in general [2]. Nonetheless, we argue that showing the existence of this $p^*$ is a significant theoretical contribution, as it rigorously confirms the natural intuition that taking $p$ close enough to 0 will eventually recover an exact $\ell^0$ solution. In practice, a simple strategy could be to retrain several times with increasingly small (e.g. halved) values of $p$ and stop once no further sparsity gains are observed. Developing more refined approaches for selecting $p$ is of interest for future work.

[2] Tillman and Pfetsch. "The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing." 2013.

• Clarity: the reviewer rated the clarity of our submission as "1. poor." It would be helpful if the reviewer provided specific feedback on which parts were unclear so that we can further address any confusion and make any necessary changes to the paper.

As the discussion period is nearing its end, we would appreciate feedback from the reviewer on our rebuttal, and any other potential questions or points of confusion. Thank you!

We thank the reviewer for their careful evaluation of our work and for their feedback. Below we address the questions and concerns individually.

• Min-norm interpolation vs. regularized loss solutions: our sparse recovery results in the multivariate case also extend to the regularized loss problem $\min_{\\theta} \\mathcal{L}(y,f_{\\theta}(x)) + \lambda \sum_{k=1}^K \\| v_k w_k \\|\_p^p$ for any loss function $\mathcal{L}$ which is piecewise affine in its second argument. This includes the commonly-used hinge loss as well as the $L^1$ and $L^{\\infty}$ losses. This holds because the regularized loss problem can be recast as $\min_{\\theta} \sum_{k=1}^K \\| v_k w_k \\|\_p^p \\ \textrm{s.t.} \\ \\mathcal{L}(y,f_{\\theta}(x)) \leq C$ , and under the piecewise linearity assumption, constraint set $\\{ \theta: \mathcal{L}(y, f_{\theta}(x)) \leq C \\}$ will be a polytope under the reformulation discussed in the multivariate section. The rest of our multivariate argument then applies to this problem verbatim. Extensions to non-piecewise-affine losses such as MSE are less clear, although potentially attainable using other techniques. Rigorously characterizing the behavior of SGD/Adam with this $\ell^p$ objective would also be interesting, but would likely require a very different set of analytical tools, and is outside the scope of this paper. Nonetheless, it is indeed possible to relax the interpolation assumption and replace it with certain types of regularized loss; we can add this to the final version of the paper. Additionally, the interpolation regime itself is of practical relevance, since neural networks in practice very often are trained to interpolation (zero or near-zero training error).
• Relationship to prior work: for p = 1, our variational reformulation in the univariate case corresponds to that of Savarese et al. (2019). We will update the paper with this reference and make the relationship more explicit. The Joshi paper studies the generalization properties of sparse univariate ReLU network interpolants (sparsity here is obtained by regularizing the biases as shown in [1], which is only proven to enforce sparsity under some assumptions on the data) in comparison to the straight-line interpolant, and shows that these sparsest interpolants may or may not demonstrate either "tempered overfitting" or "catastrophic overfitting" depending on exactly how the error is measured. Although the question of generalization is somewhat separate from our focus in this work (which is on how to obtain guaranteed sparsest solutions, if these are known to desirable a priori), we can also mention this paper in our related work.
• Minor comments: we will fix the typo and the incorrect equation reference in line 308.

[1] Boursier and Flammarion. "Penalising the biases in norm regularisation enforces sparsity." 2023.

We thank the reviewer for their careful evaluation of our work and for their feedback. Below we address the questions and concerns individually.

• Extension to deeper networks: we agree that extending our results to deeper networks would be interesting and desirable. We conjecture that this is probably possible, but difficult, and would require different proof techniques than the ones used in our results. Specifically, the difficulties in extending our proofs to deep networks are the following:

  • Univariate deep networks: like shallow, these are CPWL functions, but the relationship between the knots in the function and the neurons is more complex than in the shallow case. Specifically, modifying a single neuron of a shallow univariate network only produces a local change in the represented function, but for deep univariate networks, modifying neurons in deeper layers can produce global changes in the represented function. This makes our proof approach for the univariate shallow case difficult to apply to deep networks.
  • Multivariate deep networks: although [1] develops a reformulation of three-layer ReLU network training as a linear constraint problem, similar to the two-layer formulation that inspires our proof approach, the resulting reformulated problem minimizes an $\ell^{2,p}$ group norm (rather than an $\ell^p$ norm) subject to a set of linear constraints. Unlike the $\ell^p$ norm, the $\ell^{2,p}$ group norm is neither convex nor concave, so our arguments here also do not readily extend to the deep case.

  Thus, any extension to deeper networks would likely require different proof strategies than those used in our paper. Nonetheless, we believe that our results for the shallow case are valuable, as they provide (to our knowledge) the first sparse recovery guarantee for neural networks with arbitrary data, and develop innovative proof techniques for analyzing $\ell^p$ minimization in the highly nonlinear, nonconvex neural network context.

[1] Ergen and Pilanci. "Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs." 2021.

• Computation of the critical threshold $p^*$: our proofs do highlight a possible approach for computing p*—in both the univariate and multivariate cases, this can be done by enumerating and searching over the extreme points of a polytope determined by data-dependent constraints. However, there may be an enormous number of these extreme points (exponential or super-exponential in the number of data points $N$), which makes computing this value impractical. We conjecture that this difficulty may be unavoidable, because even for the simpler linear problem $\min_x \\| x \\|_p^p \ \textrm{s.t.} \ Ax = b$ with $0 < p \leq 1$, computation of restricted isometry and null space constants (which play a similar role in determining sufficient conditions for this problem to recover $\ell^0$ minimizers) is known to be NP hard in general [2]. Nonetheless, we argue that showing the existence of this $p^*$ is a significant theoretical contribution, as it rigorously confirms the natural intuition that taking $p$ close enough to 0 will eventually recover an exact $\ell^0$ solution. In practice, a simple strategy could be to retrain several times with increasingly small (e.g. halved) values of $p$ and stop once no further sparsity gains are observed. Developing more refined approaches for selecting $p$ is of interest for future work.

[2] Tillman and Pfetsch. "The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing." 2013.

• Experiments and practical performance: We have since conducted numerical experiments (not included in our initial submission) which demonstrate that for high-dimensional data, a reweighted $\ell^1$ algorithm for minimizing our proposed $\ell^p$ objective produces solutions which are significantly sparser than those obtained with weight decay or unregularized training. In low dimensions, simply adding the $\ell^p$ regularizer to the Adam loss also produces solutions which are significantly sparser than both weight decay and unregularized training. We are unable attach these experiments here due to the new response format rules prohibiting PDFs and links: however, we can include them in the final paper. We also note that other strategies for $\ell^p$ regularization with $0 < p \leq 1$ in neural networks have also been proposed and shown to be empirically successful, including the weight factorization/reparameterization trick (see [3], Section 5.3 "Compression Benchmark"). Thus, although algorithmic implementation is not the focus of our paper, this type of regularization has shown good empirical performance, and may be even further improved with continued research into training approaches. Regarding how well these maximally-sparse solutions generalize to unseen test data as compared to other non-sparse solutions: although this is interesting, it is outside the scope of our focus here, which is on how to obtain these maximally sparse solutions if they are known a priori to be desirable for a particular problem.

[3] Kolb et al. "Deep Weight Factorization: Sparse Learning through the Lens of Artificial Symmetries." 2025.

We thank the reviewer for their careful evaluation of our work and for their feedback. Below we address the questions and concerns individually.

• Extension to deeper networks: we agree that extending our results to deeper networks would be interesting and desirable. We conjecture that this is probably possible, but difficult, and would require different proof techniques than the ones used in our results. Specifically, the difficulties in extending our proofs to deep networks are the following:

  • Univariate deep networks: like shallow, these are CPWL functions, but the relationship between the knots in the function and the neurons is more complex than in the shallow case. Specifically, modifying a single neuron of a shallow univariate network only produces a local change in the represented function, but for deep univariate networks, modifying neurons in deeper layers can produce global changes in the represented function. This makes our proof approach for the univariate shallow case difficult to apply to deep networks.
  • Multivariate deep networks: although [1] develops a reformulation of three-layer ReLU network training as a linear constraint problem, similar to the two-layer formulation that inspires our proof approach, the resulting reformulated problem minimizes an $\ell^{2,p}$ group norm (rather than an $\ell^p$ norm) subject to a set of linear constraints. Unlike the $\ell^p$ norm, the $\ell^{2,p}$ group norm is neither convex nor concave, so our arguments here also do not readily extend to the deep case.

  Thus, any extension to deeper networks would likely require different proof strategies than those used in our paper. Nonetheless, we believe that our results for the shallow case are valuable, as they provide (to our knowledge) the first sparse recovery guarantee for neural networks with arbitrary data, and develop innovative proof techniques for analyzing $\ell^p$ minimization in the highly nonlinear, nonconvex neural network context.

[1] Ergen and Pilanci. "Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs." 2021.

• Hardness of optimization and numerical implementation/experiments: we argue that in principle, non-convexity of the $\ell^p$ regularizer is not a major obstacle since the neural network training objective is already non-convex. In linear problems, effective algorithms for non-convex $\ell^p$ minimization with $0 < p \leq 1$ have been developed and are used frequently in practice (see e.g. [2]). We have since conducted numerical experiments (not included in our initial submission) which demonstrate that for high-dimensional data, a reweighted $\ell^1$ algorithm for minimizing our proposed $\ell^p$ objective produces solutions which are significantly sparser than those obtained with weight decay or unregularized training. In low dimensions, simply adding the $\ell^p$ regularizer to the Adam loss also produces solutions which are significantly sparser than both weight decay and unregularized training. We are unable attach these experiments here due to the new response format rules prohibiting PDFs and links: however, we can include them in the final paper. We also note that other strategies for $\ell^p$ regularization with $0 < p \leq 1$ in neural networks have also been proposed and shown to be empirically successful, including the weight factorization/reparameterization trick (see [3], Section 5.3 "Compression Benchmark"). Thus, although algorithmic implementation is not the focus of our paper, this type of regularization has shown good empirical performance, and may be even further improved with continued research into training approaches.

[2] Lyu et al. "A comparison of typical $\ell^p$ minimization algorithms." 2013. [3] Kolb et al. "Deep Weight Factorization: Sparse Learning through the Lens of Artificial Symmetries." 2025.

• Additional references: we thank the reviewer for the recommendation and will include the cited papers in our related work section.