Global Minimizers of $\ell^p$-Regularized Objectives Yield the Sparsest ReLU Neural Networks
Authors: Julia B Nakhleh
Robert D Nowak
Venue: NeurIPS 2025 poster ()
Keywords: neural networks
sparsity
path norm
min norm interpolators
representational cost
Primary area: theory
TL;DR: We propose a continuous, a.e. differentiable regularization objective, based on an $\ell^p$ quasinorm of the network weights for $0 < p < 1$, which provably yields sparsest single-hidden-layer ReLU interpolants of the data.

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.

Global Minimizers of
( Pe-Reuularized Objectives Yield the Sparsest ReLU Neural Networks
Julia Nakhleh
Robert D. Nowak
Department of Computer Science University of Wisconsin-Madison Madison, WI jnakhleh@visc.
Department of Electrical and Computer Engineering University
Madison, WI
rdnowak@sisc.edu
Abstract
Overparameterized neural networks can interpolate a given dataset in many dif- ferent 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 inter- polating 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 ap- proaches, we propose a continuous, almost-everywhere differentiable training objective whose global minima are guaranteed to correspond to the sparsest single- hiyden-layer ReLU networks that the data, This result marks a conceptual advance: it recasts the combinatorial problem of sparse interpolation as smooth optimization task, potentially enabling the use of gradient- based training methods. Our objective is based minimizing ! quasinorms of the weights for 0 < < 1, a classical sparsity-promottee applying these ideas to neural networks presents new challenges: the function class is ciinite-diimesiinal 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.
strategy in finite-dimensional settings. However,
Introduction
Highly overparameterized neural networks have become the workhorse modern machine learning. Because these networks interpolate given dataset in many different ways (see e.g. Figs. lb [c) explicit regularization frequently incorporated into the training procedure to favor solutions that are, in some sense, which yield sparse hangle-hidden-lyyee ReLU interpolating networks, which for our purposes are those with the fewest nonzero input weight/bias parameters among the active neurons Sparse models are particularly desirable for computational efficiency purposes, as they have lower storage requirements and computational overhead when deployed inference time, and may have other attractive properties in terms of generalization, interpretability, and robustness (Mozer and Smolensky (1988); Guo et al. (2018) Liao al. (2022) Liu et al. 2002), among many others).
regular desirable. In this work, foeus explicit regularizers
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
In the univariate innrrratte-ipuuttco case, this is equivalent to the count of active neurons.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

justifications for their use remain almost entirely heuristic and/or empirical. Furthermore, many such strategies rely on complex pruning
coopiiees--oosee of iterative magnitude thresholding. fine-tuning, and sensitivity maalsses-hiol are computationally costly, difficult to implement, and offer no theoretical guarantees terms of the resulting sparsity. In contrast, we propose a simple regularization objective, based on the ! quasinorm of the network weights for 0 < < 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 (?-norm minimization with < P < 1 has been studied in finiteddimensional linear problems (most extensively in the context of compressed sensing), where it is known guarantee sparsity under certain assumptions on the datu//measurements, its behavior in the context of neural networks whherei the features themselves are continuously parameterized and data- auta-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 ( er-reullrizeed networks. In |Sectiion 3] we prove that, for bingle-hidden-layer ReLU networks of input dimension one, minimizing the network's ' ! path norm (see (2) implicitly minimizes both its l' path norm (i.e., the total variation of its derivative) and, for sufficiently small p > O, its l path norm (total knot/neuron count). We show that for any 0 < p < 1, a minimum l path norm interpolant of N data points has no more than N active neurons. In contrast, e' path norm minimization alone is not guaranteed to implicitly minimize sparsity, and may yield solutions with arbitrarily many neurons Fig. Tap. Our result follows from reframing the network training problem as an optimiza- tion over continuous piecewise linear (CPWI.) functions which interpolate dataset with minimal p-variation O 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- !! solutions, and highlights
easily-verifiable condition on the data under which ( minimization for any 0 < p < 1 yields a sparsest interpolant (e" solution). Additionally, our analysis shows that the solution to the univariate & minimization problem is unique for almost every 0 < 1: in contrast, univariate 6 and E" solutions are both known to be non-unique in general (Debarre et al.
(202)); HHnnin (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 ! path norm can be recast as finite-dimen dinenssinnnii minimization of continuous, strictly concave function over a polytope Using this reformulation, we show that there always exists some data-dependent threshold p" below which l minimization recovers e (sparsest) solution, in terms of the count of nonzero parameters of the active neurons in the network. We also show that no E (for any 0 <p < 1) or go solutions has more than N active neurons and, if the data is in general position, any e solution has ((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 smooth e penalty for 0 p to obtain truly sparsest interpolating ReLU networks via gradient- gradient-based methods no pruning or complex post-hoc approaches required.
2 Related work
Sparsity via E minimization in finite-dimensional linear models: s penalties with 0 < p S 1 for linear constraint problems have been studied extensively in the compressed sensing literature, and have been shown to yield exact e 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 name bridge regression (Frank and Friedman (1993); Knight and Ful (2000): |aan and Li (200T). Existing theory in these areas is highly dependent on the fixed, fiite-dimensional nature of the linear constraint, and is not readily adaptable to the neural network context, wherein the features themselves are adaptively learned.
"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.
2

---

(a)
(b)
(c)
Fig. la shows several univariate min-E' 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. abd [c] two different ReLU network interpolants of the same 2D dataset with different numbers of active neurons and parameters. Fig. lb has 5 nonzero input weight/bias parameters (its e path norm as in P), while Fig. 1c has 16.
Figure 1:
e path norm regularization dingle-hidden-lyeee ReLU networks: Neyshabur et al. (2015)
showed that the Ed path norm of single-hidden-layer ReLU network controls its Rademacher complexity and thus its generalization gap, but do not directly address the question of sparsity. In the context of infinite-width ReLU networks, the problem of minimum-L" path norm interpolation is known to have solutions with no more active neurons than the number of data points (Parhi and Nowak 2021 2022); ; Shenouda et al. (2024 However, solutions to that problem are known to be non-unique, and generally include interpolating ReLU networks with arbitrarily many active neurons (Hanin ):22);; Debarre et al. ). Nakhleh et al. (2024) show that variant of l path norm minimization applied to univarite-input, multi-output networks always yields a solution with no more than N active neurons, but this solution rarely coincides with the sparsest solution unless the dataset is of a very particular form. Therefore, path norm regularization applied to lagle-hiddennllyer ReLU networks is not generally guaranteed produce sparsest solutions.
Empirical methods for training sparse neural networks: A large body of research has been dedicated pparsity-promoting neural network training schemes. Here we briefly summarize some of the most well-known strategies as well as some which resemble our proposed regularization approach; our list is by no means comprehensive. Earlier works suggested using e and &² penalties encourage small network weights (Ngl (2004); Hinton and Van Camp (1933) or applying post- trainini pruning approaches (LeCun et al. 1989); Hassibi et al. (1993)). More recent pruning schemes incorporate
pruning iteratively into training (Han et al. (2015); Guo et al. (2016); Frankle and Carbin (2018);
Zhang et al. (018); Zhou et al. (2019). Group lasso-type penalties to induce structured sparsity over neurons or channels have also been suggested (Wen et al. (0016); |Scardapane et al. (2017)
Other approaches include e approximation using explicit gating mechanisms (Louizos al. (2018) ;
Srinivas and Babu (2017) and variational dropout (Molchanov et al. (2017). Another line of research
uses reparameterization tricks to replace non-smooth sparsifying objectives with smooth versions that share the same local and global minimizers (Ziyin and Wang (2023); ; Kolb et al. (2023 2025))
Finally, a number of different algorithms for g &P-type regularization (p < in neural networks have been proposed and evaluated experimentally (Wu et al. (2014); Khan al. (2018): Tang al. (2023);
Outmezguine and Levi (2024); Di et al.] (2025). While these methods have demonstrated empirical success in training sparse networks, existing theory does not guarantee that any of them will find
sparsest solutions. Moreover, these approaches often require complex multi-stage pipelines and are computationally costly to implement.
Provable sparsest-recovery in specialized neural network settings: In the ID input case, (oursier and Flammarion (2023) show that, under certain assumptions the data-namely, that the data contains no more than three consecutive points on which the straight-line interpolant is strictly convex or concave-innt intevvv-nntttplaatiinn using a bias-penalized El path norm regularizer will select sparsest interpolant of the dataset. As we will see in Section 3 this assumption on the data is rather restrictive,
Forr input dimension greater than one, the et path norm Ek= |ve| /all///=lll studied in those works differs from the one consider in g which is equivalent Σ |ox || wx || for p 1.
3

---

and our analysis does not require it. Their proof is also not readily extendable to multivariate inputs. Debarre et al. (2022) characterize the sparsest min-(' path norm interpolants in the univariate case and provide an algorithm for explicitly constructing one such solution. |Ergen and Pilanci| (2021) show that t path norm minimization yields solutions with a minimal number of active neurons if the data dimension is greater than the number of samples (precluding the univariate-inper case) and the data satisfy special assumptions, such as whitened data. Fridovich- Keil and Pilanci (2025) show that an iterative hard thresholding algorithm applied to shallow ReLU networks recovers sparsest solutions with high probability the data is Gaussian. In contrast, our sparsity results do not require any assumptions on the data, and provide exact sparsity guarantees in arbitrary input dimension.
3 Univariate ("-regularized neural networks
Here we consider
R + R ReLU neural networks of the form
K
fa(x) = Uk (wwaz + bx)+ + ax +
(I)
where (+) == max(0, -} is the ReLU function, == { (fw,, bR: un k== a, c} is the collection of network parameters. and all parameters are R-valued, For given dataset (I1, y1)..... .... (IN, yN) e R x R. a fixed p E (0, 1]. and a fixed width K 2 N consider the following problem:
K
arg min
Lgeekl subject to fo(x;) yt, i =
(2)
We will refer to the quantity being minimized in 2 as the network's e path norm. Additionally, consider the "sparsifying" problem
K
arg min
L subject to fo(a;) = yi, i i= I
1=
where the e path norm Ex= k=1 40 which is equivalent to the limit of the ' path norm as p 4 O-counts the number of active neurons in the network.
In this section, we will analyze the relationship between solutions of (2) and 3 in terms of their represented functions, and show that these functions can be explicitly described in terms of the geometry of the data points. This characterization (Theorem 3.1) shows that solutions to (2) for any 0 x are necessarily also solutions for p 1, immediately implying data-dependent bounds on the network's parameters and Lipschitz constant. This description also allows problem (2) to be reduced to a minimization of a continuous, strictly concave function over polytope. From there, we show in Theorem 3.2) that solutions to (2) are unique (in terms of their represented functions) for Lebesgue-almost every 0 < p < and that, for small enough p, this unique optimal function is also a sparsest interpolant of the data (i.c., a solution to (3). Furthermore, if the data meets certain easily-veriffable geometric assumptions, solutions to for any < p 1 are solutions to the sparsest-interpolation problem
3.1 Variational reformulation of 2 and
We begin by showing that problems and can be equivalently expressed as a type of variational problem over the set continuous piecewise linear (CPWL) functions which interpolate the data. This equivalence is critical for the analysis in this section, since it allows solutions to 2 and (3) to be characterized geometrically in terms of their represented functions and their local behavior around data points. Here, let Sö.p (resp. Sb,u) denote the set of parameters of optimal neural networks which solve (resp. (3)) for given dataset, and let
Sp ( R + IR f fo, 0 E So
*Here and Section 4 we K 2 because interpolation in any dimension is possible with K .V neurons (Bubeck et al. (2020). Proposition 2). We will show that solution sets of the f and L path norm minimization problems for any input dimension are invariant to the selection of K as long as K 2 N Corollary 3.1.1 and Proposition

---

be the set of functions represented by neural networks with optimal parameters in Sp.p for any S p -
Proposition 3.1. For any 0 S p S 1, the set Sp is exactly the solution of arg min Vo(f), subject to f(zi) = Yo: = I...,N
(5)
where the optimization in 5 is taken over all f : I. which are continuous piecewise linear (CPWL) with at most K knots. For such CPWL.functions J, we define
Vi())= = [supp
- (f(z;)) sup, Exer (A))()),,
s (6)
number of knots of f,
ifp=
with the first sup taken over partitions P {ro <... Enp R, and the second sup taken over partitions of R into countably many disjoint (Borel) measurable subsets. In particular, St is non-empty.
Remark 1. For p E (0, 1), Vp(J) is the p-variation Dudley and Norvaiša 2006), Part 11.2) of the distributional derivative Df (in the sense of functions), equivalently of the second distributional derivative D2 f (in the sense of measures). In particular, for a CPWL function f with knots at U1..... uk and corresponding slope changes C1...... CK at those knots, so that f² E Ck we have
K
VOO)
Σ
cx
k=1
In the case p Vi(f) is exactly the total variation of Df (in the sense of functions) and of D2 (in the sense of measures), and the reformulation in Propositiin 3.7 equivalent to that of (aavaresse et al. (2019). For a neural network where by. wk by/ /ww for l + W),, Vp(J) is exactly the e path norm of f as defined above.
neurons "activate" at the same location (i.e.,
The proof in Appendix A.1.I Proposition 3.1 says that the set St of functions represented by solutions to (2) exactly the set of CPWL functions which interpolate the data with minimal sum of absolute slope changes, each taken the n" power. the case p 0, solutions to (3) represent CPWL functions which interpolate the data with the fewest possible knots. This reformulation also shows that problem (3) invariant the choice of network width K, as long as K is large enough to allow interpolation. As a consequence of Theorem 3.1 holds for problem
we will see that this same width-invan iidh-invvrriance
3.2 Geometric characterization of solutions to
Next, in Theorem 3.1. we describe set of geometric characteristics which any optimal network function E ST for < p must satisfy, and which at least one f E St satisfies. This characterization depends on the slopes s; 9i:1-M: of the straight lines &, connecting (I., -:+1-2;
and (1 11 11) The discrete curvature at a data point 2; refers to e; := sgn(s; - 81-1), which positive if the slope of the straight lines between consecutive data points increases at æi. and negative this slope decreases (with sgn(0) 0).
In words, Theorem 3.1 says that the behavior of any f e Sp for 0 < < 1 is uniquely determined everywhere except around sequences more than three consecutive data points
Zi+m with regions of potential ambiguity, solutions
the same discrete curvature. On these "constant-curvatur must be convex (resp. concave) if the curvature of the data positive (resp. negative), and can have at most m knots on any such region. Additionally, Theorem 3.1ssays that solutions to (5) for 0 < p < 1
have most N knots. Therefore, as in the case p O. we see that problem (2) invariant (in terms of represented functions) to the choice of network width K, long as K 2 -
Theorem 3.1. For 0 < < 1, solutions exist to (5) (hence to (2). For any such solution, its represented function
S7 is CPWL and obeys the following:
1. f is linear before 42 and after xx; between any three more consecutive collinear data points; and between any two consecutive points Is and Fi41 with opposite discrete curvature
6, + E441
5

---

22
89
87
U1
U2
1
22
3'
24
2'
26
27
Zg
200
11
(a) function satisfying the description in Theorem 3.1
7
88
U1 87 U22
8g
10
16
88
Zy
21u
211
(b) second possible function on [17, 210]
(c) A third possible function on (87,210))
Figure 2: Illustration of Theorem 3.1 By Theorem 3.1 any f Sp for 0 < p must agree with the function in Fig. 2a
(-00, 27] and Iio oo). The only possible ambiguity occurs between ry and Fi0. where all points have the same discrete curvature. Here the function behavior is described by
Theorem 3.1 2b Figs. 2b and show two other functions whose behavior [17, T10l also concurs
with Theorem 3.1
2b
2. On any maximal set of m consecutive data points Zi...., Fitm with the same discrete curvature (i.e., Ej-1 * Ex+1
Eitm # (x4m41):
(a) If then has a single knot between x; and 2441, with incoming/outgoing slopes 8i-1 at I; and 8i+1 al Ti+1-
(b) If m 2 2, then f has incoming slope 8:-1 at and outgoing slope St+m at Ti+-m- Between D; and Zy+mo f takes on at most - slopes uI....y Um distinct from 8:-1 and Sitm- Each uj is between 8itj-1 and 81tj, inclusive, and its corresponding segment passes through (Is+js Vits).
Furthermore, there is always some f E S which obeys the above description. (See illustration in Fig. 2
Corollary 3.1.1. Any minimum @ path norm interpolant of the data O < p < 1 is also a minimum EL path norm interpolant, and can be represented by network with no more than N neurons.
The set S of optimal neural network functions for has been fully characterized in previous work (Hanin (002)): Debarre al. (022)),, which showed that any interpolant obeying the description in Theorem 3.1 is in ST. Therefore, Theorem 3.1 shows that any solution to (5) (hence ( for 0 < 1 also a solution for p This result interesting because, our proof of Theorem 3.1 shows, problem (5) generally has multiple solutions for p 0, many of which are not solutions for p and may have arbitrarily large slope changes which cannot be bounded in terms of the data. Intuitively, the latter fact is unsurprising, since the objective Vo(f) depends only on the number of knots of f, not on the magnitudes of the corresponding slope changes. One might therefore expect that penalizing V,, for sufficiently small y could also produce solutions with arbitrarily large slope changes (corresponding to networks with arbitrarily large weights), particularly in light of the equivalence between V, and Vi penalization for sufficiently small p, we demonstrate in Section 3.3

---

However, Theorem 3.1 says that this is not the case. Therefore, in conjunction with Theorem 3.2 Theorem 3.1 says that for sufficiently small p. penalizing V,, effectively penalizes both Vo and V simultaneously: i.e., it selects a solution with the fewest possible knots (corresponding to network with the fewest possible neurons), and whose weights small in the sense that Σk=1 |1y,2r is minimal. In fact, [Theorem 3.1] immediately implies the following data-dependent bounds on the parameters and the network function's 's Lipschitz constant:
Corollary 3.1.2. Any solution 0 to 2 0 < < has maxk=1..... K [u
S
Σ K k=1 [ =
ΣM' |s+1 sal. and Lipschitz constant L < max (s:)-
Regarding the N 2 neuron bound in Corollaryy 3.1.1] we note that this bound applies to any minimum (" path norm solution for any 0 < p < 1. In contrast, there exist minimum E' path norm solutions with N 2 knots, but also solutions with arbitrarily many knots (Hanin 2022):[Debarte et al. (2022); see Fig. la| Solutions for 0 p < 1 are thus guaranteed certain level of sparsity which is not enforced by p- = 1 minimization alone. Sparsest (minimum (²) solutions- -whch we soon show will coincide with an e² path norm solution for small enough p-are known to have as many as N active neurons and as few as O(N/2) neurons, depending on the structure of data (Debarre et al. (2022).
The proof of Theorem 3.1 hinges mainly on two auxiliary results, detailed in Appendix 1.2 which describe the local behavior of any optimal f S between consecutive data points in terms of f's incoming and outgoing slopes at those points. This allows us to characterize when a knot can be removed from any interpolating function while maintaining interpolation and reducing its regularization cost Vp. The full proof is in Appendix A.1.3
3.3 Uniqueness and sparsity of solutions to (5) for 0 <p<1
unique for almost every 0 < p 1, and for sufficiently small 0 < < 1. correspond with globally sparsest interpolants (i.e., interpolants with the fewest total knots). Additionally, Theorem
Using Theorem 3.1
show that solutions to
Theoollyymeeeemmmmmmmmmm 3.1 shows that under easily-verifiable condition on the data, penalizing V, for any 0 < p < I yields a sparsest interpolant. In conjunction with Theorem 3.1. this result tells us that for univariate data, l" path norm minimization for sufficiently small p > 0 simultaneously minimizes both the fd and e path norms, producing a unique solution which is both maximally sparse and controlled in terms of its parameters' magnitudes. We note that almost-everywhert uniqueness of solutions to (5) occurs only in the 0 < p < case. In contrast, solutions for both p 0 and p- = 1 are non-unique general, and for p = 1, they may have infinitely many knots/neurons (Debarre et al. (2022), Hanin (2022))
Theorem 3.2. For all but finitely many 0 < < 1, the solution to is unique Furthermore, there is some dependen p" such that the unique solution for any 0 < p < p" is solution for p = O. If the data contains no more than two consecutive points with the same discrete curvature, then the solution to
5 for any < p 1 is also a solution for p 0.
The proof of Theorem 3.2 is in Appendix A. It relies on Theorem 3. in combination with the Bauer maximum principle (Aliprantis and Border (2006). Theorem 4.144, which states that any continuous, strictly concave function over a closed, convex set attains a minimum at an extreme point of that set. The main idea is that, using Theorem 3.I] we can recast the problem of finding the minimum-W V,, interpolant f E S' (where S' denotes the set of functions which meet the description in Theorem 3.1p as a minimization of a continuous, strictly concave function over the hypercube (0. 1p--1 This reformulation is possible because, by Theorem 3.1 the only place where these interpolants f E S may differ is around sequences of points æ,..... Fi+m (for m > 2) which all have the same nonzero discrete curvature. Using the description in Theorem 3. 2bb the slopes M1, Mm of any f E S on such an interval [xi, T.4m] can be expressed as convex combinations Uj := (1 - 0z) (s))s++j11 + aj8i-jj and any such solution f E S can be fully identified with its corresponding vector of the parameters [ai...., (1--1) T E [0. 1jm- Expressed in terms of these parameters [01....,aj-1] T 1]=- the cost V, is strictly concave. Therefore, by the Bauer
'I 'Uniqueness here and in the remainder of the discussion only in terms of functions which interpolate the data with the same set of absolute slope changes. If the data contains special symmetries, it may admit multiple distinct interpolating functions which have the same set of absolute slope changes (corresponding to interpolating networks with the same weights).
7

---

maximum principle, any f E S with minimal V for 0 < p < 1 must correspond to one of the finitely many vertices the cube [0, 1)m-1 Having restricted the set possible candidate solutions to this finite (which can be shown include least one sparsest solution), the theorem statement follows from standard analysis arguments.
In the next section, will show that this general line of reasoning- -recsst the neural network optimization as a minimization of a strictly concave function over a polytope, and apply the Bauer maximum principle- also be used to characterize the sparsity of & de-reuularized multivariate- input ReLU networks, although the machinery underlying the argument is very different.
4 Multivariate (erreularried neural networks
Here we consider figle-hiddennlaye R + ReLU neural networks of the form
(x
Σ
un (w x)
with output weights 2 IR, input weights ur E Rd+1, and E {x: 1]T augments the dimension
1K of the input æ to account for bias term. As before, 0 = {uk, wy k== is the collection of network parameters. For given dataset (I1, (1). ... (æ yN ) E I x R, and fixed constants K 2 N and p < consider the minimum 8 path norm interpolation problem
arg min
w subject to fo(x;) Y: i I....,N
(8)
O
We will prove that, for small enough any solution to ( also solves the "sparsifying" problem
K
arg min
He lo subject to fo(æ;) = yes I....,NN
The multivariate e path norm objective in ( counts the number of nonzero input weight/bias parameters of the active neuron in the network. We begin by upper bounding the sparsity of solutions to (9) and showing that, as in the univariate case, problems (8) and are invariant the selection of width K as long as K N.
Proposition 4.1. For any K 2 N and any 0 <<p< 1, solutions to { exist, and any such solution has at most active neurons. The same holds for (9) Furthermore, if the data æI,..., Ey are in general position then any solution to (9) has Σk | = O(N).
See proof in Appendix 1 for explicit constants various cases.
To show the equivalence of problems ( and 9 for sufficiently small we first show that both problems can be recast as finite- (albeit high-) dimensional optimizations over linear constraint set. This reformulation is heavily inspired by Theorem 1 in Pilanci and Ergen (2020). Here we denote element-wiss inequality for vectors a, b as a < b. Let X == [ ØNl E (d-1((11) be the
matrix of augmented data points I; == [ 1] = [y1.... .......... yN] E RNN be the vector of labels, and { {D, )/=1 be the collection of all N x N binary matrices of the form diag(1[Xx 2 0)) for some E Rd+11 It is known that < E 2 (Cover
Lemma 4.1. For any < p < and any K > N, let 0 (Uk, (uk,wa)k w2) be solution to Then there is another solution 0' = {1/ w K
l== to (8. which is reconstructed from solution
'A neuron + (w x)4 is active if vaws + 0: i.e., that neuron has a nonzero contribution to the network function.
"A set of points 2I,..., EN E Rd are in general (linear) position no of them lie in a k 2 dimensional affine subspace, for k = 2, 2,3, 2. d - 1. If N 2 d d 1, this is equivalent to the statement that no hyperplane contains more than d points.
8

---

which which necessarily satisfies H[j My + 0} + [6j w/ + Of S N to the problem
arg
1 || subject to
Σ Dj X -w,) = y
(10)
|=1
(2D, - 1) 2 0, (2D, 1)X 2 20, j 1,
(11)
as
(16))==1 K = (u//as 1 + 0 [w//BB #0}
(12)
(r/))=11 = {az +)} ( w/ + #0}
(13)
for any choice of on, fi,..., B,, > 0. Both solutions satisfy =k=1 K
//ulwllllo Ek= 11 u llo
K as well as Ek=1 | = Σmm ll w f for any < 9 < 1. The same statement holds for solutions O to with the objective in (TO) replaced by Σj=1 ||55loo |
The proof of Lemma 4.1 is in Appendix A.2.2 The main idea is that although there are uncountably many ways to choose the neurons' parameters, there are only J possible binary activation patterns, iee, vectors representing whether given neuron is active on each data point. By combining all neurons which induce the same activation pattern into two neurons (one with positive output weight and one with negative output weight), the network's 's output and ( path norm can be expressed as a sum over these J activation patterns. The equality constraint in (IO) reflects the data-fitting requirement, and the inequality constraints ensure that each Vi, W correspond appropriately to the activation pattern D, in order for the reconstruction formula 122 to hold. With this reformulation in hand, we are ready for the main result of this section:
forany Theorem 4.1. For any dataset, there is some data-dependent v" such that any solution to for any 0 <<p p < p" is a solution to
The proof, presented in Appendix A.2.3 follows the approaches of Yang al. (022a): Peng et al. (2015) in analyzing sparsity of solutions to ming:Az=y |> for an underdetermined linear system Az y, with modifications to account for the linear inequality constraints in (IO). The fundamental observation is that the linear constraints in (TO) determine a polytope, and the map + |=||| is strictly concave on each individual orthant and invariant to absolute values of vector elements. By projecting the constraint set of (TO) into the nonnegative orthant, the problem turns into minimization of a continuous, strictly concave function over polytope. By the Bauer maximum principle, any solution to this problem occurs at one of the finitely many vertices of that polytope, and by appropriately normalizing the vertices of this polytope, we are able demonstrate the desired result.
Although Theorem 4.1 applies to any input dimension, thus recovering part of the result of Theo rem 3.2, our multivariate analysis does not immediately recover the univariate results on functional structure uniqueness of solutions; nor does it demonstrate that solutions for 0 < p < 1 are always solutions for 1, as was shown in the univariate case (Corollary 3.1. Thus, although Theorem 4.1 guarantees exact sparsest recovery for sufficiently small p in arbitrary input dimensions, the multivariate problem leaves many interesting open questions, which we save for future work.
5 Experiments
We perform several simple experiments on synthetic data which suggest that our proposed E path norm lends itself to practical application, recovering far sparser solutions more quickly than unregularized or weight decay-regularized gradient- training. To implement our regularizer, we use a proximal gradient algorithm based on the iteratively reweighted el method of Candes et al. (2008); Figueeireo et al. (2007), the details of which are summarized in[Appendix A.3. Fig. 3|shows the sparsity over time of networks trained with our reweighted é' algorithm for three different values of p E (0.4, 1). as well as with unregularized Adam and AdamW weight decay, on two different synthetic datasets. For all values of p, the ( re-reaularized networks are much sparser much earlier training than the unregularized or weight decay regularized networks, with the p = 0.4 networks being the sparsest. For the univariate synthetic dataset, the p 0.4 regularized network recovers

---

sparsity over time: peakrplateau dataset =1
sparsity over time: = 10. d'= 50, datallablls Unif)-1.1]
10'
regulettratin Adamn
reweignted
reseiggfoe (p 0.7)
rowe gliegited f 0.7)
rewelghted
f'
30'
20000
40000 00000
80000
1000GD
20000
40000
00000
B0000
100000
spoch
opoch
Figure 3: Sparsity over time of networks trained to interpolation with reweighted e algorithm (see Appendix A.3.1) for path norm regularization, p E {0.4, 0.7, and of unregularized and weight decaa-regularized networks. Results the left are for synthetic univariate "peak/plateau" dataset, and results on the right are for high- digh-dimensional set random data and labels. The gray dashed lines reflect the true minimal sparsity (in the univariate case, left) and the upper bound on the minimal sparsity guaranteed by Prropssitonn 4.1 the multivariate case (right). For further details, results, and discussion, see Appendix A.3.2
the true sparsest solution, and for the multivariate synthetic dataset, all l regularized networks recover solutions which obey the sparsity upper bound guaranteed by PProposition 4.1] For further details, results, and discussion, see Appendix A.3.2 Code for these experiments is available
www.iaaaaaahhessppsssseee..e sparse_arseseeee patrrse_nns___
Conclusion and Discussion
We have introduced smooth, l path norm (0 1) regularization framework whose global minimizers provably coincide with the sparsest ReLU network interpolants for sufficiently small thus recasting the combinatorial ( minimization problem differentiable objective compatible with gradient descent. In the univariate case, we showed minimum & path norm interpolants are unique for almost every 0 < p < 1; never require more than - neurons; and also Ed minimizers, yielding explicit data-dependent parameter and Lipschitz bounds. In arbitrary dimensions, we demonstrate similar ("-g0) equivalence for sufficiently small p. Our proposed regularization objective offers principled, gradient-basee alternative to heuristic pruning methods for training truly sparse neural networks.
While we demonstrate the existence of small enough for ('/C2 minimization equivalence, our proofs do not yield efficient way compute the "critical threshold" p", although they do demonstrate that estimating this p" is in theory possible by enumerating an exponential number of vertices of data-dependent polytope. Whether not p" can be computed or estimated efficiently is open question of interest for future work. Other possible directions of interest are to extend our results here multi-output and deep architectures and to other notions of sparsity (such sparsity entire neurons vs. parameters in the muulti-dimensionall case).
References
C. D. Aliprantis and K. C. Border. Infinite dimensional analysis: a hitchhiker's guide. Springer Science & Business Media, 2006.
E. Boursier and N. Flammarion. Penalising the biases in norm regularisation enforces sparsity. Advances in Neural Informaiinn Processing Systems, 36:57795-57822 2023.
S. Bubeck, R. Eldan, Y. T. Lee, and D. Mikulincer. Network size and size of the weights in memorization with two-lsyers neural networks. Advances Neural Information Processing Systems, 33:4977-4986, 2020.
10

---

E. J. Candes and T. Tao. Decoding by linear programming. IEEE transactions on information theory, 51(12):4203-444 4215, 2005.
E. Candes, M. B. Wakin, and S. Boyd. Enhancing sparsity by reweighted é! minimization. Journal of Fourier analysis and applications, 14(5):877-905, 2008.
R. Chartrand. Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Processing Letters, 14(10):707-71, 2007.
R. Chartrand and V. Staneva. Restricted isometry properties and nonconvex compressive sensing. Inverse Problems, 24(3):035020, 2008.
T. M. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions on electronic computers, (3):326-33) -344, 2006.
Debarre, Q. Denoyelle, M. Unser, and J. Fageot. Sparsest piecewise-linear regression of one- dimensional data. Journal of Computational and Applied Mathematics, 406: 406:114000 14044, 2022.
R. M. Dudley and R. Norvaiša. Product integrals. young integrals and p-variation. Differentiability of Six Operators on Nonsmooth Functions and p- Variation, pages 73-208, 2006.
T. Ergen and M. Pilanci. Convex geometry and duality of over-parameterized neural networks. Journal of machine learning research, 22(212):1 2021.
J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American statistical Association, 1348-13333 2001.
M. A. Figueiredo, J. M. Bioucas-Dias, and R. D. Nowak. Majorization--inniizztiii algorithms for wavelet-based image restoration. IEEE Transactions on Image processing, 16(12):2900-2991 2007.
S. Foucart and M.-J. Lai. Sparsest solutions of underdetermined linear systems via (*-minimization for 0 < < 1. Applied and Computational Harmonic Analysis, 26(3):395-407, 2009.
L. E. Frank and J. H. Friedman. A statistical view some chemometrics regression tools. Techno- metrics, 35(2)109-1335 1993.
J. Frankle and M. Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2018.
S. Fridovich- Keil and M. Pilanci. A recovery guarantee for sparse neural networks. arXiv preprint arXhv:2509.20323 2025.
M. X. Goemans. 3. linear programming and polyhedral combinatorics. Massachusetts Inst. Technol., Cambridge, MA, USA, 2009.
Y. Guo, A. Yao, and Y. Chen. Dynamic network surgery for efficient dnns. Advances in neural information processing systems, 29, 2016.
Y. Guo, C. Zhang, C. Zhang, and Y. Chen. Sparse dnns with improved adversarial robustness. Advances in neural information processing systems, 31, 2018.
S. Han, J. Pool, J. Tran, and W. Dally, Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
B. Hanin. On the implicit bias of weight decay in shallow univariate ReLU networks. 2022.
B. Hassibi, D. G. Stork, and G. J. Wolff. Optimal brain surgeon and general network pruning. In IEEE international conference on neural networks, pages 293-299. IEEE, 1993.
G. E. Hinton and Van Camp. Keeping the neural networks simple by minimizing the description length of the weights. In Proceedings of the sixth annual conference Computational learning theory, pages 5-13, 1993.
G. Jameson. Counting zeros of generalised polynomials: Descartes' rule of signs and Laguerre's extensions. The Mathematical Gazette, (0(518):223-244 2006.

---

F. Ji, X. Chen, R. Chu, and B. Liu. Network slimming using Ip (p< 1) regularization. Pattern Recognition, page 111711, 2025.
N. Khan, J. Shah, and Stavness. Bridgeout: stochastic bridge regularization for deep neural networks. IEEE Access, 6:42961-42970, 2018.
K. Knight and W. Fu. Asymptotics for lasso-type estimators, Annals of statistics, pages 1356-1378. 2000.
C. Kolb, C. I.. Müller, B. Bischl, and D. Rügamer. Smoothing the edges: Smooth optimization for sparse regularization using hadamard overparametrization. arXiv preprint 2300::330..3371,, 2023.
C. Kolb, T. Weber, B. Bischl, and D. Rügamer. Deep weight factorization: Sparse learning through the lens of artificial symmetries. arXiv preprint arXiv:2502.02449, 2025.
Y. LeCun, J. Denker, and S. Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
N. Liao, S. Wang, L. Xiang, N. Ye, S. Shao, and P. Chu. Achieving adversarial robustness via sparsity. Machine Learning, pages 1-27, 2022.
Liu, Z. Zhu, Q Qu, and C. You. Robust training under label noise by wer-parameterization. In International Conference Machine Learning, pages 14153-14172. PMLR, 2022.
C. Louizos, M. Welling, and D. P. Kingma. Learning sparse neural networks through lo regularization.
In International Conference on Learning Representations (ICLR), 2018.
D. Molchanov, A. Ashukha, and D. Vetrov. Variational dropout sparsifies deep neural networks. In PMLR, 2017.
International conference on machine learning, pages
M. Mozer and Smolensky. Skeletonization: technique for trimming the fat from network via relevance assessment. Advances in neural information processing systems, 1988.
J. Nakhleh, J. Shenouda, and R. Nowak. A new neural kernel regime: The inductive bias of multi-task learning. Advances in Neural Information Processing Systems, 37: 37:140451-140477, 2024.
B. Neyshabur, R. Tomioka, and N. Srebro. Norm-based capacity control in neural networks. In Conference learning theory, pages 1376-1401. PMLR, 2015.
A. Y. Ng. Feature selection, 1 1 2 regularization, and rotational invariance. In Proceedings of the Iwenty-first international conference on Machine learning, page 78, 2004.
N. J. Outmezguine and N. Levi. Decoupled weight decay for any norm. arXiv preprint arXiv:2404. 100.24 2024.
R. Parhi and D. Nowak. Banach space representer theorems for neural networks and ridge splines. Journal of Machine Learning Research, 22(43):1 2021.
R. Parhi and R. D. Nowak. What kinds of functions do deep neural networks learn? insights from variational spline theory. SIAM Journal on Mathematics of Data Science, 4(2):44-488) 2022.
J. Peng. S. Yue, and H. Li. NP/CMP P equivalence: A phenomenon hidden among sparsity models lo minimization and 1p minimization for information processing. IEEE Transactions Information Theory, 61 (7))4022844033
2015.
M. Pilanci and T. Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. In International Conference on Machine Learning, pages 7695-7705. PMLR, 2020.
P. Savarese, I. Evron, D. Soudry, and N. Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667-2690. PMLR, 2019.
Scardapane, D. Comminiello, A. Hussain, and A. Uncini. Group sparse regularization for deep neural networks. Neurocomputing, 241:81-89, 2017.
12

---

J. Shenouda, R. Parhi, K. Lee, and R. D. Nowak. Variation spaces for multi- neural networks: Insights on multi-tass task learning and network compression. Journal of Machine Learning Research, 25(231):1-400 2024.
S. Srinivas and R. V. Babu. Training sparse neural networks. In IEEE Conference Computer Vision and Pattern Recognition Workshops (CVPRW), pages 138-145. IEEE, 2017.
A. Tang, L. Niu, J. Miao, and P. Zhang. Training compact dnns with 1/2 regularization. Pattern Recognition, 136:109220 109206, 2023.
W. Wen, C. Wu, Y. Wang, Y. Chen, and H. Li. Learning structured sparsity in deep neural networks. Advances in neural information processing systems, 29, 2016.
W. Wu, Q. Fan, J. M. Zurada. J. Wang, D. Yang, and Y. Liu. Batch gradient method with smoothing 1/22 regularization for training of feedforward neural networks. Neural Networks, 50:72-78, 2014.
L. Yang, X. Chen, and S. Xiang. Sparse solutions of class constrained optimization problems. Mathematics of Operations Research, 47(3):1932-13 1956, 2022a.
L. Yang, Zhang, Shenouda, D. Papailiopoulos, K. Lee, and R. D. Nowak. Pathprox: A proximal gradient algorithm for weight decay regularized deep neural networks. arXiv preprins arXiv:2210.03000 2022b.
T. Zhang. S. Ye, Zhang. J. Tang, W. Wen, M. Fardad, and Y. Wang. A systematic dnn weight pruning framework using alternating direction method of multipliers. In Proceedings of the European conference on computer vision (ECCV), pages 184-199, 2018.
H. Zhou, Lan, Liu, and Yosinski. Deconstructing lottery tickets: Zeros, signs, and the supermask. Advances in neural information processing systems, 32, 2019.
L. Ziyin and Z. Wang. spred: Solving 11 penalty with sgd. In International Conference Machine Learning, pages 43407-43422 PMLR, 2023.
13

---

A Proofs of main results
A.1
Univariate results
A.1.1 Proof ofPPropostioon 3.1
Proof. By homogeneity of the Rel.U-meaning that (axr) cx(x)- for any O-any ReLU neural network of the form (1) can have its parameters rescaled as eg + [w (0,, (wx, bR) + |uxl- by) without changing the network's represented function or its Ø path norm. Therefore, any S can be expressed as neural network of the form ① with |ww| = 1 for all k I, .,...,4, K. Additionally, any f Sp can be expressed as network where no two neurons "activate" at the same location, i.e., bx/wwx + by /ww whenever k o k'. To see this, consider a neural network So with unit-norm input weights which contains two distinct neurons k, k' with by. w//wx = bw/wwk. The sum of these neurons can be rewritten as
Uh uw bb)+ uw (www + bw))+ (ux + Uk Uw))( bx)+
(14)
wk Wk', or
Uy vg(Wax + bx)+ + us (ww. + bw)) - (ux U. ( - + bk)
(15)
W/ wwy. (The latter uses the identity x (c)+-(-z)a In either case, we see that the original
two neurons k k' can be replaced with single neuron and, in the latter case, an additive affine term.
Because the affine term does not contribute to !" path norm, and because |uk + ugrl" S J2% 1" + low for p E (0. 1], the resulting network represents the same function as the original one with no greater regularization cost.
Furthermore, any neural network of the form (T) with unit-norm input weights and active neurons, where
active neurons activate the same location, is CPWL function with K knots, where knot k is located at -ba/ux, and the slope change of the function at knot & is uk. Conversely, any uk and corresponding slope
IR CPWL function with K knots locations ui changes U1,..., UK can be expressed as
f(x) f(uo) (uo) un) Σ uk(x uk)=
(16)
for some arbitrary point un u1. Any such f has D Ex=1 Undug so that Vi(f) = and Vo(l) = Σx 1 K.
Ex=1 lu
These facts are sufficient to establish the equivalence of problems 2 and (5) Indeed, let 5% denote
the set of optimal parameters for a modified version of problem ( which imposes the additional
constraints that each |wxl = 1 and that by/ Ww * by/ Wyy whenever à & K. For some 0 E S let C* denote its f path norm. We have shown that Sp can be equivalently expressed
5 = (f : + B for 0 E Sp.p) [f : TR CPWL with K knots, v₂(f== f(:;) (,) N} (18)
(17)
which is exactly the set of minimizers of (5). Non-emptiness of S (and thus of Si) follows from non-emptiness of the fcasible set θ of (3) when K N, and the fact that the objective values of members of the feasible set lie in [1....,K,, on which a minimum is achieved.
A.1.2 Auxiliary lemmas: local behavior of f around same/opposite sign slope changes
Our proof of Theorem 3.1 relies strongly on the following two auxiliary lemmas, which describe the between consecutive data points. Here we denote the incoming and outgoing slopes of any interpolant f at a data point x; as sin (f, 2x.) and Sout (f. x.). respectively (sometimes dropping the explicit reference to f if it is clear from context), First, we show Lemma A. that for any optimal network function f E Sp. < p < 1, if the signs of 8: Sin (T,,,) and Som #1+1) 8; agree, then f connects (æt, Us) and (x Me+1) in a single
local behavior of any E E 5% for 0 S pp< <
"peak" (see Fig. 4a).
14

---

UJ-1
W2
M
uy-1
u1
Soal (2i+1)
8t
Sin (x:;)
Son (T)
8in (7:)
Ug
24
2++1
24:1
(a) Illustration Lemma A.1
(b) Illustationn of Lemma A.2
Figure 4: Left: Illustration of the case sgn (s, 6i x;)) sgn (Sout (ʃz T441) -;;) addressed
in Lemma A.I. Right: illustration of the case sgn (s; - $iu (f. m4)) * sgn (Sout (J. x1+1) - 8;) addressed in Lemma A.2 In both cases, the functions in black have strictly greater Vp for 0 $ p < than the functions in blue.
1 7
+
C
b
21
21+1
Figure 5: Base case of Lemma A.2 where consider the possibility that Sy for some 0 S
< 1
has single knot at some (Ni; 2;+1) where sgn(a + sgn(b c). Here 7 3:11-
a-
Lemma A.1 (Behavior of f E S around same-sign slope changes). For 0 S < 1, suppose that E Sp has sgn (s; sin Sin xi)) = sgn (Sout (f, xi+1) 8;) at consecutive data points 2i Ti+1. If both signs are zero, then linear on the interval I == [x; - 8, 5,34+1 + 8) surrounding [m,, Fit1]. for small 8 >> O. Otherwise, f has single knot on I, between x, and F4+11- (See Fige 4a
Proof. If both signs are zero, then f must be linear on I, since anything else would have nonzero Vf(fl) for 0 1 1. If both signs nonzero, observe that
1oou (ʃ, (1.441) (f, x1) < Sout ( -u
u1 +| 8in (J, (f)
for any . u. which are all distinct from each other and from sin (f,(fa))) and Sout f(+1). This is simple consequence of the inequality la + bl" < |a|* + 6b/, which holds for any a, b IR and any p and strict unless I has one or more intermediate slopes u1 ....... between I; and 1i+1 the result follows.
or b 0. Since any interpolant with more than one knot on
Next, Lemma A.2 says that if the signs of s; 8in (f, .r.) and Bout(f, - 8; an optimal f S 0 p < disagree, then is linear between æ; and zi+1-
Lemma A.2 (Behavior of f E 5 around opposite-sign slope changes). For O S < 1, suppose that f St has sgn (s; Sin sin(f, x;)) + sgn (Sout (f, xi+1) 1) 8i) at consecutive data points 2ú, Eitt- If 0 <<p < then is linear between Ri and F4411 If = O, then either linear between x; and 1, or il agrees outside of [xi, I++1] with some g E S which is linear between I; and T441- (See illustration Fig. 4b
Proof. First consider the base case illustrated in Fig. 5 where we suppose that f E Sp for some 0 < p < has single knot at some x E (x,, 1. To simplify the notation, we denote a == Sin (f.) b si. c = Sout (f, x4+1) and == -. and assume that sgn(a b) + sgn c). The intermediate slopes in and u2 can parameterized as 11 + and Uy = - for some 8 E R. Consider the cost vz()), of if on the interval I == (I, Z4+1 + e) (for some arbitrary
15

---

E >> 0) as a function C()) of the parameter ó. p = O. then clearly C(0) 2 v C()) E (2.3) for 8 + This shows that the function 9 whose slope b on [2,2241 has no greater cost than f. and
thus E Sg. In the case 0 < p < 1, we have
1
C = + +
all + (1- 7)0 -c b+
1- T 8|
(19)
and we will show that C(O) (6) for 8 * 0, contradicting the assumption that f Sp-
Note that C' is coercive and continuous on 5 E R. so it attains a minimizer (this follows from the Weierstrass extreme value theorem as applied to the compact sublevel sets of C). By Fermat's ' theorem, any minimizer of must occur at critical points, i.c., points where the derivative C" is zero or undefined. The three points where C" is undefined are 61
b, 82 0, and 63 (6 166--0 c). Assuming without loss of generality that 8, < 82 < 83. note that C' is strictly concave on the intervals (-o0, 61). 82). (62, 6z), and (dg, oc). This is because compositions of concave and affine functions are concave, and the function x + |ax| for p E (0, 1] is concave on any subinterval of R over which x does not change sign. Therefore, any point at which C" 0 will be local maximum rather than a minimum, and hence any minimum of C' can only occur at the critical points 6,, 62, d3. We have
C(6)) = (I 7)p
a - 6/"h +
let
T
a
1
61 P
(20)
1-
1
C(62) = |6 - alı + Icc - 61p
(21)
C(6a) 1 1- r
1
5 c p
bb - dp
(22)
7p
Now, for the variable & E [0, 1), define
t a
1
(t) = (1 - t)p la - 610 + cet
bl"
(23)
t t
and observe that h0) = C(2)) and hT( = C(5)). Its derivative is
M((1) (1 t)a+1
p la - b|p + pl c
1 1
0
1
1
b
sgn
c +
1
1 1- (1 t)2
1
b)
a --
(24)
p (1-t) t)p+I la - + + -|p
t
1
b18-1
b10
(1 -
f)(c (bc b) + +taaa - b)
a- b
sgn
1- 1
1-t
(1-t)²
(25)
Assuming that sgn(a- - b) * sgn(b c) with a # b (and thus 6n * 52), we see that (1) > 0 for all 1 E [0, 1). This is because the term inside the sgn above is positive if b (so that b < e) and
negative if a < 6 (so that 6 2 c). This shows that (0) = O(2)) < h1(T) = C(².). Similarly. define
h2(1) = 1 -
1-t c
al2
+
b cl
(26)
t
t
for t E (0, 1), so that = and hz(
=C(dz). Its derivative is
(t)))= = b
1
1-t
t c
-
al"
p-1
sgn
-b
t
1
1-t
t c- a
c- b
82
10+1
p
1616-00 cl
(27)
=|
1
1-t
1
al
8gn
t(b a) + (1 - t)(b
c)
c-b
12
1+41
P
1b
(28)
Assuming that sgn(a- - b) + sgn(b c) with a c (and thus 82 o 8g), we see that h2 > 0 for all t E (0, 1). This is because the term inside the sgn above is positive if > (so that a < b) and
negative if b < e (so that a 2 b). This shows that h2((T) = C(,a) < h2(1) = C(²)). Therefore, C(0)- C(6) for 8 of O, as desired.
Next, consider the general case, where we assume by contradiction that f E St for S p < 1 may have multiple knots inside (zi, 1144).. As before, in the case p- = 0. f can't have fewer knots than the function g whose slope is on [z4, 4441;; the only way for f to be in Sp is if it has single knot
16

---

U2
(2i)
Sout (1(11)
(1n(
Soul (2111)
Zi+1
21
Zi+1
(a) MJ are on the same side of S..
(b) and MJ can be connected, reducing Vy()).
Figure 6: General case of Lemma A.2. where outgoing line segment at IG and the incoming line segment at 4,+1 both lie on the same side of the straight line between (zi4, M/) and (24411 Mc+1). ). We can apply the argument in the proof of Lemma A.I connect these two segments single knot inside (Ir, x++1) and strictly reduce (f).
Soul (Z+11)
U2
Sout 12))1)
81
Up
Rin
(1,(),) (z,)
M
Zi+1
Zi41
(b) dag Uso and Uoo uy can be connected, reducing Vx(f).
(a) Un. are opposite sides of
M1
Bout (1:=-1
(x;)
81
Z++1
(c) uy and Sout (f, 1i41) can connected, reducing Vg(
Figure 7: General case of Lemma A.2. where the outgoing line segment i; and the incoming line segment at 2++1 lie on opposite sides of the straight line between (I;, 14) and (æş-1- Mi+1). We can apply the argument the proof Lemma t. connect the segments Uj and Uj, and Uj and uy- resulting in a function with two knots inside (æ,, 1s+1) and strictly reducing Vf(f). By the same argument, we can further reduce Vf) by connecting in and Sout (out(f, 14+1). resulting in a single knot inside (I;; 1111)
inside (z,, 11) and single knot at either I; or 2441, in which case we also have E Sã- In the case < p 1, u1,...,44 U. denote the slopes of f on [x,, Fi+1]. If the line segments with slopes M1 and u, lie on the same side of the line segment with slope 8;, then can apply the argument in the proof of Lemma to remove segments with slopes u2..... 4J-1 and connect the segments with and u, in single knot inside (æ,, xi+1 ); this strictly reduces (f), contradicting (See Fig. 6) If the line segments with slopes i and u, lie on opposite sides of the line segment with slope 5;, then either one of the intermediate segments, whose slope we call Ujo. crosses the segment with slope 8; or else one of the intermediate segments (again call its slope uljo) lies on one side of s,, and uj++1 lies the other side. In either case, the segments 2 and Ujo can be connected and the segments between them removed, as can the segments újo (or ugo+1) and u. (See Fig. 7) Again, by the logic in the proof of Lemma A. this strictly reduces V, Vy((), contradicting E Sp. If is already of the form in Fig. 7b] with only knots inside (æ,, #x41) opposite sides of the line 8;. then the second knot can be removed by directly connecting 41 and Sout (ff, 1;41) (see Fig. 7ch By the same logic, this strictly reduces (f), contradicting S.
S
17

---

Sent (22)
Sont (#2)
(21)
(11
21
22
(a) A function with knot inside w2).
(b) function which agrees with on (-o0, wa].
Figure 8: Behavior of f E Sp before 22 and after NN. A knot inside (#1, can be moved to I2, maintaining the same outgoing slope at 22, which strictly decreases the magnitude of the slope change at the knot.
A.1.3 Proof Theorem 3.1
Proof. We first use Theorem 3. and Lemmas A. and A.2 to show that any f Sp for < must obey the description in Theorem 3.1 and that there is always some f E Si which fits this description. Using this result, we argue non-emptiness of Sp. We break the proof into the following sections.
Linearity before 22 and after IN-1- We will prove the statement for (=0,, the proof for [cN-1, 00) is analogous. No / E Sy for 0 < S 1 can have a knot at or before 21 as this would strictly increase the cost (f( without affecting the ability of f to interpolate the data points. In the case 0 < p 1, assume by contradiction that some Sp has knot at some E
(I11 22) By
Lemma A.2, it must be the case that
sgn(s (f,22) x22 -1)). and by Lemma A.1 and 8in (f, 8ont Cout(..00 T2))
this knot is the only one inside (2), with 8in (in( = Sour (f, 21)
(See Fig. 8a) Assuming without loss of generality that sgn(s1 Sin (f,z1)
sgn(Sout (J: 1,222
81) - T, we have 8jn (1) > 81 > 8out (f, and therefore | (f. 8in (f,01) >
Sout 22) x2) s1|. But this shows that Vf,(f) Vg(g), where g & on (-o0, and is otherwise
identical to f. (See Fig. 8b) This contradicts f Sp.
In the case p- = 0, fix some ʃ E S6- As argued above, / has no knots on (-oo, 2.). If sgn(s) Sin xf)) # sgn(sout(f,
$1), then by Lemma A.2 either f l on [2] (hence it also must agree with l on (-00, or there is some E 5j which agrees with & on [21, 222 (hence also on (-00, since g must also not have any knots (1)0, If sgn(s1
(f.
(f, (22) 81) = 0. then by Lemma A.1 f= L on [I1,
and thus also on (-00, 21). If
sgn($1 Sin (Jn x1 sgn(Sout (f.
$1) are both nonzero, then by Lemma A.1 f has single knot inside (I1, x22) with Sma $1,(f,21 = Sout (f.z1) x1) and (i, x22 = Sout (f, (,2),,0 as in Fig. 8a Then
function depicted in Fig. 8 which agrees with & on [-00, and with on [22, oo), has the same
number of knots as SO E 5j.
Linearity between data points of opposite curvature. For < p 1, assume by contradiction
that some f E S does not agree with E, on an interval [r,, where sgn(s: - 1 j sgn (8i+1
8). By Lemmas A.I and A.2 it must be the case that sgn(s; (),((xx,,)) = sgn(s (f, (f. - 8) are both nonzero, and that Sin (f. = Sout 2x) and sin (fn x141) sout (f. and f has a single knot inside (z,, T4+1) where the incoming line at x; and the outgoing line at 2++1 meet. must be the case that sgn(s; s)-1) * sgu(s; Sin xf;( and/or that sgu(s1+1
8;) +
sgn(sout(f -++1)=s;))) si). Assume without loss of generality that sgn (s;+1-;;) sgn (f. f1+1)
s;) = 1. so that 8:+1 S s; < Sout (f, 2141)= = Sin (f, 2141). Then clearly 8:+1 * Sout f.2+11 (in other words, f does not agree with f.+1 on all of [1++1, 2)) so by Lemma A. and Lemma A.2 must be the case that -1 = sgn(s)+) - sin (f, (f,
sgu(soue[T, [[, 8 that / has Sout ((, (See Fig. 9a Therefore, sin (1+2)) Ront (J, (1,2) < 8:-1 S 8; < Sont (f, (141))) = (f(())i41). Furthermore, because
single knot inside (I:+1, 2142), and that 8mm (J,
1 sgn($out (f, x141) - 3t) sgn(ss sin x;), we have s (f, x4) < Sout (2141). On
18

---

Sma
8:-1
P (2)())
Bout (8:41)
Aia (2))
#1-1
Ma+1
Fi+2
21-2
(a) A function with knots inside (In, and (0+4::J442)
(b) function which agrees with & on [ar, m++1]-
Figure 9: Behavior of f E Sp between data points of opposite curvature. The knot inside (12, 21+1) on the left can be moved to 2,, and the knot inside (2,+1, 21+2) can be adjusted accordingly (right); this reduces the magnitudes of the slope changes of both knots.
I: [r:-1 e, 2:24 + for small é > 0, we thus have
vg(ll))) Sour (f, 1i+1) sin (f, x:)1 + |sout (1, Sout (fu xi+1)
(29)
ss sm sm x4) Sout (f. 2142) - s;|² =V
(30)
where agrees with f outside of 2142) agrees with E on [24, and has single knot inside 1,41, 2i+2] with Sout (g, 1i+1) = 8, and 8in (0, = Sout (g) 2x+2) = Sout (J; 2142). (See
Fig. 9b) ) This contradicts ʃ E S
For p = 0, consider some f E Sh- If 0g; - sin Sin x;)) & sgn($out (f, (.411 - 8;). then by Lemma A.2 there is some g Sj which agrees with If outside of [T, Ti+1] and agrees with & on 11+ By Lemma A. if sgn(s; sin (f, 2x)) sgn( (Sour (f. (f. Ii+1) 8.) O. then f = & on sgn(Sout (S, xi+1) - 9i) both nonzero, then by Lemma A.I (f,(f, = Sout (f. and sin (f. = Sout (f, fI44)), and f has single knot inside (Iz, z++1) where the incoming line at x; and the outgoing line at r:+1 meet. As before, it must be the case that sgn(s;-s;-1 # sgn(s;; (m,
[i+ If sgg(s;; Sin [ xx))
and/or that sgn($141188)) -s:1-ss) # sgn(s (f, ( Assume without loss of generality that sgn(81+1 - 8;) sgn(Sout (141)
8,) 1, so that 8.+1 S 8; < Sgn(Sout (f, (, - 8,) sgn(s; sin (f. we also have Sta (f, < &; < &oat (f, 2141) sgn(Sout (f, 2342) - 8.41) # sgn(s1+1 - Sin (1+11) (f,
Sout (f,
Sin 1144))) Because
-1, then by Lemma A.2 there is some g E Si which agrees with f outside [21+1, T442 and agrees with 4+ on Ti+ T+41. Then this g has Sout (g, xi+1) = 8; and (g, x; sin Sin (;)), so 8:) E (-,,0) and sgu(s; sin (g, x;)) = hence by Lemmma A.2 there is some E Sg which agrees with g outside of [2,, [d,, x1-1] and agrees with E, on [ [.,, On the other hand, sm (f11)
sgu(Soun(
-1- then by Lemma A.I f has single knot inside (I I142), and sin (f. (+)))))) = Sout (f-)) as in Fig. 9a This function has two knots on := [2,-1 r, +e] (for small >> 0). The function g depicted in Fig. 9b] which agrees with f outside of [r,, 224, agrees with l on [Is, #1+1], and has a single knot inside [1++1, Zi+2] with Sout (g, 1441) 8; and Sin Sin 2,42) = Sout (g, 2:42) Sont (f x142), also has two knots on T.
if sgn( (f. s141) sgn(
Therefore E Sh
Linearity between collinear data points. For 0 < < 1, fix f E Sy. If sin x.) = 8; = 85+1
4 on [x,, Fi4m). since any other function g would have (g(gg) > 0 = vp((l,) [)) on := [z; e, Zi+m + c] for small e 0. If sgn(s; - Snn xx)) # sgn(Sout (f, f.4mm s,), then the argument the proof of Lemma shows that ff must agree with f; =
814m-1 = Sour (f,, I, then f must agree with E; =
4+ on [x;, I. So we need only consider the case where sgn(s; Smn sm xx)) = sgn(s (Soue (f, I++m) s;) are both nonzero; say without loss of generality that they both equal 1, so that Sin (f,zz) < 8; < Sout Sout(f, (f, If
Ls on both [ar; Zi+1l and 11 mm then also must agree with f; on [ Pi+m-il (otherwise it would have Vf [m...tm]) 0), so assume by contradiction that f * L, on at least one of these intervals, say without loss of generality on [x; 2,41. Then by Lemmas A. and A.2 it must be the case that f has single knot inside (44, and that 8in (J, xx.) = Sout (F, < 8; < 8in (S, [1++1) = 8pnt (ʃ (,441) This implies that f also disagrees with E, on [2,, (11) so again by Lemmas A. and A.2 must
have a single knot inside (x 2i+2) with 8in (),(f, (+)) = Sout (f, 1.11)) 1) > 8 > 8in (J, 23+22) = Sout 21)). The same logic applies the remaining intervals up to and including [1+4m- 244m]
19

---

Ront (#++2)
Pou(Fi1s)
(un((
R113
8y+1
8in (2;)
Sout (Bi+1)
(t())
2++2
21
Riol
J242
x8-3
(a) A nonlinear function between m + 1 collinear points, m-even.
(b) A nonlinear function between m + 1 collinear points, m--dd.
Figure 10: Behavior of f E Sp between collinear points. If f E S is not a straight line between collinear points (Ii, Be),...,, (fi++ m)), it must look like Fig. 10a m is even) or Fig. 10b (if m is odd). In both cases, the sum of absolute slope changes of these functions is greater than the sum of absolute slope changes of the function g which agrees with f outside of [x,, F++m] and connects (a yt ye),..., (f V/+m) with straight line. Such a g has two knots, whereas functions of the form depicted here have m 2 2 knots.
(see Fig. 10
Note that if m is even, we will have sin Sin xi4m-1) =
Sout 2i4mm 1) > 8i4m-1
8 > 8in Ti+m) = Sout (f, Di Fi+m). contradicting the assumption that sgu( Sout (f, (itmm) - 8i) =
(see
Fi.
T0ap. If m is odd, as in Fig. 10b] we have
1or(l,) = Soue (J, 0.+1) 8in x;) + |outt ([,1)+2) - Sout (f;
(31)
+ .... + | (onu([,,000) (J, Sout (J, xi 1)
(32)
> |s - snn(f, xx.) P + I (f. Z++m) - 8i4m-11 (o(gl,)
(33)
where g is the function which agrees with f outside of [x,, 314m] and agrees with E, =... fi4m-l on [2t,, mm this contradicts f E Sp.
In the case 0, fix f E So- If sin (f.))) agree with E, =
8itm Sout (f, then f must 4++m-1 on [T,, F44m and if sgn(s; Sia (f,(),))) # (Sou (f, f. s,). then the proof of Lemma A.2 shows that there is some g S which agrees with f outside of [2i, [i+m]] and agrees with & on [zi, J. If sgn(s; - -ii--in (f, xx)) = sgn(s (f, )14m)= - s;) are both nonzero, then there must be at least one knot on [zt, Ti-m] in order for the slope to change from $in (m,(f 22) to Sout 2i+mm. It is impossible for f to interpolate the data with a single knot on [2;, 2z+m] where the slope changes from (f to Sout (f, Zi+m), since this would require at least two of the points (Iz, y4). ................................ (Ii+m- 3i+m) to both lie on either the incoming line at x, or the outgoing point Ti+mm but this is impossible because 8; F sin (), and 8; F Sour (J, mm)- Therefore, f must have at least two knots on Tet]. The function 9 which agrees with & on (wi, Ti and has 8in (z)) = 8mn (f, 244) and Sout (g, F.4m) Sout (ʃ, (f, f.+mm) interpolates the points (2,, V:),.., (I++m= Mi4m) with exactly two knots on [xq - Fi + c). and thus E Sj-
0 1, fix f Sp. If i == 2. then f = E on ao by Theorem 1 if > 2, then by assumption, sgn(s 81-2) sgn(s; - 8;-1), so by Theorem 3. / 4- on [x;-1, vi-- J- In either case, we have 8in 1, 8;-1- An analogous argument shows that Sout 2111) = 8 Similarly, Theorem 3.1 says that Similarty,Thhoormm
Single knot between two data points with the same curvature.
there is some g E Sg for which Sin x..) = 8;-1 and Sout (g. 11+1) = 8i+1- In both cases, the conclusion then follows from LeomLemmaa A.2
Characterization around 2 2 points with the same curvature. For < < 1, fix some f E S As in the proof of Theorem 3.1 2a above, the assumptions guarantee that s;-1 = (fn(fx:;) and 8i+m Sout (f, (.+m). Using this fact, we will proceed by (strong) induction, assuming without loss of generality that sgn(s; (8;- - 1;-1) = sgn($1+1 - -s))= =
sgn(si+m -i+m-1) =
In the base case m 2, first suppose that sgn(s; smn sin x:)) # sgn(Sout (f, x.+11 - s;). Since
Sin (f, 8:-1 < 8; by assumption, must be the case that sgg(Soont (J, 1 - 8)) E (0, 13.
sgn(Saue (ʃ, 11+1) 8;) -1, _1, A.2 impllmss that f = l, on [ri, 11 and thus sin 1i+11)
St. But then we have Sin ((41) = 8; < 8i+1 < 8out (J, (52))) = 8;42, so Lemma A.
it must be
the case that sia (f, x1+1) Sout (f, 2141), contradicting sgn(Sout (f. f111441)+ = (see
Fig. 12b).
20

---

#++2
S++2
8641
Mi
Ri+1
24-1
Fi+3 (a) 11
S1++1
(b) 3, M1
8
S1+2
34-1
22
Z4-3
(c) U4
Figure 11: Possible behavior of f E Sp between three consecutive data points of the same discrete curvature, All possibilities satisfy 8; u1 S 81+1-
4;-1
#1+2
4:12
8
Iinnn (Rits)
Ri-1
Fisl
2io5
Fi-1
21
Z4-3
(a) Sin (Ie41) Sout (Ie+1)
8441
(b) Sout (Te+1) a) < Sin (1041)
Figure 12: Behaviors which f E Sp for O < p < cannot exhibit around three consecutive points of the same discrete curvature. The case on the left violates Lemma A.2 and the case on the right violates Lemma A.I
If Sogn(Soni (J, Fi+1) 8:) = 0. then Lemma A.2 implies that / l, on [2,, 1i+ and therefore
Sin [[ Sout (o 11414 = 8,. Then 8in ( 8; < 8;+1 < Sout (ʃ, [;44) = 81+2, so by Lemma A.1 has single knot inside [2]411 2++2], with (n, 2(41) = Sout (f x1+1) 8; (as sout 2142) = 81-2. The conclusion then holds with 21 == s
already know) and
(see Fig. IIc..
On the other hand, still for the base case m 2, suppose that sgn(s; (fn x2)) sgn(Sout([ 1141) - si). Then by Lemma A.1. there is a single knot inside [r,, Fi41l, with Sout (f, 224) and Sin F++1) Sout I(41). It cannot be the case that Sout (J,I++) > 8,41, because if this were true, we would have -1 sgn(si+1 Sin Sin (1, + (gnn (J, x242) 81+1) = 1, and that would imply by Lemma A.2 = l4+1 on [1441, 22+2). contradicting 8ome (ʃ, 11+1) > 8i+1 (see Fig. 12a). Therefore, we must have Sout (f,)))1)
8;-1 Sin (f,x;))
8141- If Sout (f, xx+1) ) < 8141, then by Lemma A. there is single knot on [#441, 24+2). with sin (f. x141)
Sout (f, 21+1) (as we already knew) and Sin (f, -oout Sont x442) = 8142. The conclusion then
holds with i1 := sin (f, 1141) = Sout 24+1) (see Fig. 1lb
Sou x++1) $4+1, then
0 sgn(3;411 sin (f. 21+1) of sgn( Sout 2;42)
8
I, by Lemma A.2 f l
[01+1, 2. The conclusion then holds with U1 = 8:41 (see Fig. 11a).
Next, for the (strong) inductive step, fix some integer m 2 4 and assume the conclusion holds for all integers 2.... m 1. First suppose that Sout [ ((+m-1) >> 8i+m-2. Then by the inductive hypothesis, / has slopes u1. are distinct from Sin (f)))) = 8:-1 and Sout (J, ()+m-1)---
some of which may be equal to each other, but all of which
[ m-1 satisfying 814j-1 S
u, S sitj for all j L,..., 2. It cannot be the case that Sout (f, (f 1) > 8i4m-1, because
21

---

Rsim-1
Pin
Reu-1 (ispm((itta1))
Dpp-2
May-1
Pi-1 21
Xp+1
Mo-m-]
(a) m Mm-11
8i4m-1
(b) 1m
0m-1
8i+m-22
Figure 13: Possible behavior of f E S around m consecutive data points of the same discrete curvature. Assuming inductively that Theorem 3.1 2b holds for ....., 1, both satisfy Sitj-1 S My S 8itj for j ......177
Biim
4p-1
61-1
4
Na-1 (iuea(Rieree))
X
X
4u(Sise--1) > (an(-ie an Stees-3
(4 Piim-1
Riol
Zp-n-2
Rism-1
Biom
Rioms1
Spom-2
(a) 8i Sous (234mm1))) S. Sin Sin (1)4m-1)
(b) 8in Bi
Sout (Ti+4m
8i4mm-1
Figure 14: Behaviors which f Sp can and cannot exhibit between m consecutive points of the same discrete curvature. Assuming inductively that Theorem 3b holds for 2...., m 1, the case with the green check mark on the left satisfies 8t+j-1 U S $i+j for = m 1. The case with the red x on the left violates Lemma A.I. and the case on the right violates Lemma A.2
if this were true, we would have - sgn(si+m-2 (f+mm-)))) A (Sou (f, fi+mm.
8i4m-11 1) 1, and thus Lemma A.2 would imply that f = fi+m-1 on [Ti4m-1, Titml, contradicting
Sout (f, (1444m-1 > 814m-1 (see Ig. 12b). Therefore, must have Sout (f, 14+m11) S 85-m-1 If
Sout (ff, (1+4mm1) < 8i+m then by Lemma A.1 there is single knot inside [Zitm 11mm-111 2++m] and
Sin (f, ff1
Sout (f. m- and Sin (f
Sout ff. 3.+m) Si+m- The conclusion
then holds for m with um-1
= Sout (f, 244m-1) (see Fig. 13a). If Sout (f (f, = 8:-m-1,
then by [eemas A. and A.2
must be the case that (0. 11-1 1} sgn(s++m-1)
8in 8in (i
sgn(sout(] (J. /iitt
1. It is impossible that sgn(si+m-1
8in U. fitmm-1)
because by Lemmas 1.1
and A.2 for f to disagree with 4,-m-2 on [i+m-22 Fitm-1
must be the < Sout 2i+m-1)
case that Sin Ti+m
Sout (f, (i+mm1))) contradicting 8in (f xi+m-1)
814m-1 (see Fig. 14a, red). Therefore, in this case we have sin (f, T3+m
Sout (f, xi4m-1)
8i4m-1, and the conclusion holds for m with um-1 8i4m-1 (see Fig. 14a
green).
On the other hand, still for the (strong) inductive step, suppose that Sout (f, 11+m-11 S 8i+m m2 If Sout (f. = Si+m then by Lemmas A. and A.2 f has single knot inside [T Zs+m] Sout 2t++
with Sin (f This implies, again by Lemmas A. and A.2 that f litm-2
Si+m-2 and Sin (in(f
Sout x++mm
$ Si+m-
[Ti+m 2, fi+mm-1 By the (strong) inductive hypothesis, / has slopes M...... Um-3 on (xt, 22) all distinct from Sin (f, x4) 8;-1
and Saut (f, -2)m-2) = 8i+m-2, which satisfy 8itj-1 I Uj S 8it; for ...... conclusion then holds for m with um = um-1 : 8:4m-2 (see Fig. 13b). remains only to consider the case Sout (J, 1i4m-1) < 8i4m and show that this impossible for f E Sp. If Sout (f, 11)+m-1) < 8itm 22, then by Lemmas A. and A.2 there is single knot inside [xi+m-1- 3++m] and Sin (f, (14m-11 Sout
3. The
Fitm 1) and 8in (J.:+m) = Sout (ʃ, () 81mm- This in
turn implics, again by Lemmas A.I
and A.2 that there single knot inside [r++m-2 2++m-1] and
22

---

Rijre
Aspr-1
Abszue (Birva-s)
Maypel (iiee-)))
Pi-1 27
Mc-m-
Ri-1
(b) A function with sin (7i+mm-))
Sout (Zi+m-))
(a) function with Sout (3i4mm 864-m--
m
Figure 15: Possible behavior of S around m consecutive slope changes of the same discrete curvature. The magnitude of slope change each knot of the function on the left, which has Sout (f, (1.+m-1)) < 844m-2, is greater than that of the corresponding knot in the function on the right, which has iin (Im(Tmmm1)) Sout (2i+m11)
81-m-2.
Sin (fff = Sout (f, T1+mm2). (See Fig. 15a On the interval == [ri+m-2 E, Titm + for small > we thus have
vg(fll)) | (f: Fi+m-1) - sin (f x2+ P |sitm - Sout (f+
(34)
1814m-2 8in (f, xi+m-2)) 2)1 1814m 814m-21
(35)
where the incquality holds because Sout fz+m-1) 81+m-2 < 8itm and Sin (f F++m-2)
8i4m-2 >> Sout (f, (f The latter is exactly Vo(0ll), where g is the function which agrees with f outside of [4i4m- Ti+m]. agrees with fi+m-2 [1i4m- 2i4mm11 fi+m-11, 1]. and has single
knot [1)4m-1, 1, Ti+m] with 8in (in (f, Ti4m-1) = Sout (f, Fi+m-1) 8i4m-2 and 8 (J, Tz4m) =
Sout (J, (i,m) = 8i4m (See Fig. 15b)) This contradicts E Sp.
For the case p = O: again, as in the proof Theorem 3.1 2a, the assumptions guarantee that there is some f E Si for which (f,, 2T) = s and Sout (f, 1x+1) = 8,+1. The inductive argument above also shows the desired result in the p case, with each reference LoLemmm A.2 as well as the last portion of the inductive step instead justifying the existence of some g E SS which exhibits the desired local behavior and agrees with f elsewhere.
for 0 < p
Non-emptiness of S for 0 < 1 As noted in Appendix A.I.I restricting the input weights to |wy| = 1 in optimization 2 recovers the same set of optimal functions Sy. The geometric characterization proved above shows that any solution this modified ( must have no knots outside of [ 11). and thus its biases satisfy |by| < B == max([x2], |xN- Additionally, any such
solution has slopes absolutely bounded by C := max;=1.....N (scl. so that each [u = 0o S
2C, and thus its skip connection parameters can be bounded as
|a|
Σ Uk
S
a
Σ
Uk
1f = = la AA=
Σ |ol C
Wh
wy
(36)
and
V1
Uw bb)) 001
|el < 31 +
b (1=1
1bx
|arı|
(37)
1=1
A=
< Co | - 2KC( + B) + Jzz (C' + 2KC)
(38)
Therefore, any 57 is recovered by restricted version of 2 which requires that |wre = |bx s
B, [vs < 2C, Jal < A, le| S Co. For any fixed choice wi,..., wK {-1, this modified optimization (in the remaining variables) constitutes a minimization of continuous function over compact set, so by the Weierstrass extreme value theorem, solution exists. Taking the minimum over all such solutions for all possible choices of Wi...., WK {-1, 1]KK proves the result. D
23

---

A.1.4 Proof of Theorem 3.2)
Proof. If the data contain no more than two consecutive points with the same discrete curvature. there is only one interpolant f which fits the description in Theorem 3.1 By Theorem 4 in Debarre et al. (2022), this I E S.. Otherwise, if the data do contain some Fi, ........ Zi+m with the same discrete curvature for m 2 2, the slopes UI,.... Um-1 of any interpolant satisfying the description in Theorem 3.1 have 8,4j-1 Uj S Sitj for each = 1...., m 1. Indeed, any choice of U1...., um-1 satisfying 81+5-1 S Uj I S145 for each j defines an CPWL interpolant of the data, given by the pointwise maximum of 1.-1. li+m. and the lines Lj. each of which has slope uj and passes through (Ii+s. Bet5). Therefore, the set S of functions described by Theorem 3.1 2b on any such .i..... Bi+m can be fully associated with the set of numbers 11,-..:: : Unn satistying 8145-1 I U I 8itj for each j. Since any such "j = (1 -ay a3)8 + 09814j for a unique og E [0, 1]. we can equivalently identify S with the unit cube [0, 1| 1|m
Viewed as a function of its corresponding a [a1. [ ................................ am 11= E [0. 1|m-1, the regularization cost Vp(flr) (for 0 < p < 1) of any f E S on I == [x]-1 - 6, +1 + 6] for small o > 0 is
Vz(a) lun 8:-1 P
Mgj Uj-1 P 1844 um- Ip || clBB
(39)
where the rows a1,... am of A E 1. (m-1) and entries C1, .... Cm of c Th are
a1 [ii+1 8i, 0, ................................ 0]
C1 8, - Si-1
(40)
am [0.... 0, 8i+m-1 8i+ml
Ci Si+m
8 8itm-1
(41)
and
aj - [0...., 0,-00,,00000 (814j-1 8)-)-2), 8i+j 814j-1, 0, OJ, Cj 814j-1 8:43-2 (42) for ....., m 1, with the nonzero entries of a; in positions j 1 and j. By the assumption that 4 = .... = fitm are all nonzero, the rows a ....... am of A span m= and thus a + Aa + cs
injective. For any distinct a1, 02 E [0, 1|m=- we thus have Aa c + Aaz + c, and therefore
(2ttan + (1-t)a²) [|t(Aa, + cc + (1 - (A + c) t All + c + (1 A) + c|B
(43)
for any t E (0, 1) by strict concavity of 11 on 10 This shows that V, is strictly concave on [0, 1] By the Bauer maximum principle (Aliprantis and Border (2006). Theorem 4. 4.14).. Va((a)) thus attains minimum on [0, 1|m=~1 at an extreme point of [0, 1
Moreover, by strict concavity of Va), any minimum of (a) over [0, 1|n=1 must occur at an extreme point. Therefore, when searching for an f E S with minimal Vp, we may restrict our attention to those f corresponning to the 2 vertices (0, 1] 1 of the cube [0, 1|m-1
Among these 2 vertices, there is at least one corresponding to sparsest solution f E S n S. This is because, by Theorem in Debarre et al. (2022). ) any J E S n S has [m+]]] knots on 1, and there is one such f if m is odd, or uncountably many if m is even. If is odd, this unique ff corresponds to the vertex [1, O..,,....I 1, 0J E {0, 10.1) 1)mm-111------- 1; i.c., this f has U, = $445 for odd j and
Uj Sits-1 for even j. m even, there are multiple vertices a E f0, 1] pmm -1 which attain the minimal number m of knots on I: two examples are [1, 0, ............. 1. 1] E {0, 10 (see Fig. 16b) and I, 0, 1, 0)7 E [0,1),-11 (see Fig. 16a).
m-
For each of the 2 functions f E S corresponding to the vertices a E {0, 1]m-11 consider the associated "cost curves" Cp(p) :=
= 1f) which is simply the regularization cost (flr)) for that individual ff over I, viewed as function of the variable p E j0, 1]. Each Cy(p) is generalized Dirichlet polynomial x of the variable p. By the generalized Descartes rule of signs for Dirichlet polynomials (Jameson (2006), Theorem 3.1), any two cost curves (p)) C, (p) for distinct f.g can only intersect at finitely many E [0, 1). Therefore, for any given p E [0. 1] outside of that finite set (which has Lebesgue measure zero), a unique one of these 2m candidate solutions f has smaller
Generalized Dirichlet polynomials are functions of the form f(x) Ei a,b, where as x E R and bi 2 bn O.
24

---

9/14
Artt
Ug fii
Mt 9g ALL
2,13
2012
Pall
2410
(a) One sparsest interpolant, corresponding to 00, OJ.
(b) Another sparsest interpolant, corresponding to [1,0,1 1].
Figure 16: Illustration of two sparsest interpolants in the scenario of Theorem 3. 2b with 4. Both have m=+1 knots on [zg - 1, +m + 1]. consistent with Theorem Debarre al. (2022).
cost Cs(p) (f(rr) than the others. Furthermore, the sparsest of these 2 functions (i.e., the ones S ST) will necessarily have smaller C)(0) = Vo (f()z)) than the rest, and because of the cost curves Cy(p) are continuous, a unique one of these sparsest solutions will have smaller cost Cy (p) than the others for all p between 0 and p", which is the location of the first intersection of any two of these 2 candidate solutions' cost curves.
A.2 Multivariate results
A.2.1 Proof Proposiiio 4.1
Proof. We address the statements individually.
Existence of solutions to and Existence of solutions to (9) is simple consequence of
the fact that interpolation is possible whenever K 2 N, so the feasible set of (9) is non-empty, and objective values of (9) lie in (1....,Ki ('d 1)} on which a minimum is necessarily achieved.
To show existence of solutions to (8). recall that by homogeneity of the ReI.U, -1 Ug for any a 0
rescale the
input and output weights of any neural network as wa - ayW, and Uy 0g without changing the network's represented function its g or l path norms. Therefore, the optimal value (8) is equal to that of
K
arg min
juul. subject to fo(x:) = yi, i i= 1....,, N, welll =
K
(44)
Picking arbitrary feasible O' for (44), any solution to 44 must have
1/v
max
1
lua| 50
Σ 1u/1
(45)
I....
further recast
44
arg min Uk subject to fo(w;) = Uo. 1,..., N, || = 1, |ua| 5 C, k 1,..., K
(46)
Because the sets { w ||l||p 1) and {v. |u] C} are compact, so is their Cartesian product
{0 | 1, |ual < C. - 1,..,, K}. Since each O + fo(x,) ) is continuous, the preimage of the singleton sets {リ:} under those maps are closed, and so their finite intersection.
intersection of a closed set with compact set, the feasible set of (66) is compact. Problem (46) is
therefore minimization of continuous function over a compact set, so it attains solution by the Weierstrass extreme value thcorem.
25

---

Solutions to 8 and ( have no more than N active neurons. Assume by contradiction that K
Ko solution fok, we ] k==1 to (8) for K > N has Ko > N active neurons {ek, wy k= Because Ko > N, the vectors a = [ T T1)+, (wg EN IN)+I )+I", where I; := [x,, 11, are linearly dependent, meaning that there are constants Ciy...y CK. (not all zero) for which Σ ckaa O. Then for any real t:
Kg
Σ (ek + tox a
Σ a + t
Σ CLOs
Σ v = y
where y y== 1........ MN] In other words, the network with parameters {Uk + tck. w lates the data, for any real t.
Ko interpo-
In the case of (8) for any < p 1, choose t > 0 small enough that sgn(v; + tc.)) sgn (1k) for each k, and thus sgn((1y + tc;) (ex)wkks)) = sgn(",wwk. for each k; i. Then by strict concavity of |t|l +
on t E (-oo, 0) and t (0, 0o) we have
(uk + to + (vk- tcx)wsk
PP
[(uR to + I(ux tox)
(47)
2
for each i and each with ck + (if Cx = 0 the above holds with equality). Since eR + for at least one k; this implies that
Kg
Kg
Ko
Σ
[0 + tck (ow))okll 1 Σ
l1(uk tck wulll
(48)
but then least one of E [1(vx- to: ) or Ek=1 11(vx- - tcx) l must be strictly less than
Eke w.l... This contradicts optimality of {ek, J
In the case of (9). choose / = -ww/Cw for one of the cr
O. We then have
Ko
Ko llo
Σ
(1(ex + wlslo
(49)
strictly, because all of the 0g Wg are nonzero, whereas at least one of the (vy. tt,)ur on the left is zero (for l k'), and || lo 11( + (ex)) a llo whenever both wt and (w% + Ick u are nonzero. This again contradicts optimality of {w), w
Sparsity bound on solutions to 9
If the data are in general position and N 2 dd+L 1, then Bubeck al. (2020) show that there exists interpolating single-hidden-llyer ReLU network with N/d neurons. Any such network clearly has at most 4(d + 1)[ S 4(N + 1) + 4(N + 1)/d S
8(N + 1) ONN) nonzero input weight/bias parameters across those 4[N/d] neurons.
the data are general position and N & d+1, the points $I...., aN must be affinely independent, meaning that
N
Σ o5æ; and Σ a =0
a = aN =
(50)
Because this condition is equivalent to linear independence of the vectors æ, = [at_ 11] the general
position assumption ensures that augmented data matrix X = I......, FNl] E (x++1) has full rank N. Therefore, there exists a solution w Rd+1 to the system
Xw y lyi,....
(51)
with ||w||o = N. (To see this, choose N linearly independent columns of X, express y as a linear combination with respect this basis, and let be the vector of coefficients of this linear combination.) For any such w, (11) says that the affine function
f(x) w == (w 7)+
w
(52)
interpolates the data (recall T = ( [,T The term on the right a two-neuron ReLU network with e path norm of 2||w|| = 2N. Also note that if the labels y; are all nonnegative (resp. nonpositive), we may discard the second (resp. first) ReLU term (52). achieving interpolation with e path norm
of ||wloo N. Thus in all cases, the e path norm of any solution to is O(N).
O
26

---

A.2.2 Proof Lemma 4.1
Proof. We break the proof into the following steps.
Network output on data sum activation patterns. in problems and ( can be expressed in matrix form as
Note that the data-fitting constraint
K
2k xwx)+= y
(53)
recalling that X 11 Ei.... ........ EN E Nx(++1) is the matrix of augmented data points
[ar. 1] [V1: ... UN] E RR- is the vector of labels, and the ReLU (-)+ is applied element-wise.
Also recalling that Di.... DJ is the set of all possible N N binary "activation pattern" matrices of the form diag( [ u 2 0I) for u E Rd++1, must the case that the matrix [ 0))
is among the DI...., D,. For any wy whose corresponding activation pattern is D pattem(k)) we have
xwx)+ D pattem( Xwn
X w/ ww+++ + patterm (s) X kw
where W.g == U2 u.
For any j 1,..., J. let K2 [k patter((k) j} be the of neuron indices which share the same pattern Dj. Then the sum of those neurons can be rewritten as
Σ U = Σ D KEK,
Σ w w Dj- ww,)
kEK, where Uj and wj represent the positive and negative parts of the aggregate vector ΣNEK, ikk. respectively, i.e.
kEK,
Σ
Σ ug
Uj
KEK
keK
where KJ=- = (1: E Kj, Uk > 0} and Kj = (k E Kj, un < 0}. so that
Vj wj = Σ up + Σ
1H Σ W/
KEK
AEK,
REK,
Therefore, the entire network output can be written
Σ (X (ww)
-DI((v,-w,)) -wx)
1=1 with the understanding that, if the set K, is empty for some j, the vector V; wwy = ΣKEK, 2k the zero vector.
Objective achieves its lower bound with two neurons per activation pattern. notation above, the objectives of and can be rewritten as:
Following the
1p
Σ k=1
Σ KEK
+ Σ
|
KEK
Σ
|
l10
Σ
+
Σ
k=
kEK!
KEK
Observe that:
Σ
|
Σ
Wk
| p
Σ
|| 1
Σ
wk
|
11
(54)
KEK
KER
REK
KEK
Σ
l V
Σ
wk
Pylloo
Σ
|
Σ
W
||ا
1lo
(55)
KEKT
kEK
KEKj
kE
27

---

where in all cases, equality holds if and only if the supports of each vector in the sum (i.e., the set of indices at which each vector is nonzero) are disjoint. This follows from applying the inequality (a + b)P I n² + wh-which holds for any a, n, 2 0 if < p < and for any a, b E R if p 0 (defining 0 = 0), and in both cases is strict unless a or b = 0 coordinate wise.
At a global minimizer of either (8) or ( this lower bound will be achieved. To see this, note that it is always possible to replace a single one of the vectors Wy in each group Kj (resp. K5) with the vector Uj (resp. -wy), and set the remaining vectors in each group to zero. By definition vi = EbEK, wk and Wj = - -kEK, Wk. so clearly the network output
Σÿ=1 D2X (EtEky u. + EKEK, w6) = Eÿ D,X w,) on the data X remains un- changed by this modification. And with this modification, all inequalities (54) will clearly hold with equality. This shows that, for any solution to (8) or (9) all input weight vectors wn in any indi- vidual activation pattern group K or Kj will have disjoint supports (which is the only circumstance under which the lower bounds in (54) are achieved). In any such casc, the neurons in each individual positive/negative activation pattern groups can be merged into a single nonzero neuron containing their sum, without affecting either the network's s ability to interpolate the data or the value of the sums Σxex | or ΣveK | for any 0 < < 1. Note that, although this merging may alter the function represented by the neural network. it will preserve the values of Σ 1|u,,wwello and Σk= [| for any 0 < q < 1, which is the only thing required for the statement of the lemma Troviie 4.1] Therefore, positively-weighted weighted neuron v. w Vj and at most one grgatively-weightee neuron oj w w corresponding to any possiblé activation pattern on the data.
and its subsequent use in proving Theorem
may enforce that there is at most one
Constrain the variables v and wj to correspond to ReLU activation patterns. order for a particular binary pattern D, to actually correspond to an input weight/bias wk. it must be the case that (X mx)) 0 wherever (Dj)a and (X (w)) S 0 wherever (Dz)ıı 0. This is exactly the requirement that every entry of the vector (2D, - X) N is nonnegative, since
((2D) - 1) X)))::: = [ (Xur)i (-(X
if (D,)a= =1 if (D))a =0
When we re- re-parameterize as w = Uy u. and split the neuron indices K2 correponding to activation pattern D, into the groups K2- and Kj. the requirement that (2D, - -I)X 2 0 is equivalent to requiring that (2D;- ixx 2 0 A E KJ and (2D, f)X ww S 0 if k E KJ_ Because we enforce that there is at most one nonzero neuron WH My (resp. Ww -w;) in each activation
pattern group KJ+ (resp. K5) ), this condition is also clearly equivalent to (2D,- 1 X > 0 and 2 0.
Reconstruction of solutions to 8 and (9) from solutions to 1I0 By incorporating the above
constraints, we have fully reparameterized the neural network problems (8) and (9) as claimed the
lemma. Because we enforce that there is at most one nonzero neuron wh Vj (resp. w. = w
in each activation pattern group K2+ (resp. Kj), solutions to problem 8 can be recovered from
solutions to 10 as
K {w [
1/ aj
uj & 4 u
1
{
w
w #0}
(56)
{ux)k= = ua + 03 13 00}
(57)
for any constants a1, 31 ...,, a,,3, > O, the choice of which affects neither the network's 's represented
function, nor its value of >
k= | wx llo or Dk
km ||r 11 for any 0 < q < 1. Note that, if there
were solution to (10) with [j= v, # 0} + Ki w + [) > N, this would yield a solution
to (8) or (9) with = 16 Dj + 0} 10 w Proposition 4.1
* 0} > N active neurons, contradicting
28

---

A.2.3 Proof of Theorem 4.1
Proof. Problem 10 can be expressed more compactly in matrix form as
arg min =ER2
||=1||/ subject to Az y, G2 2 0
(58)
in the case 0 < < 1, or as
arg argmin min | subject to Az = y, G2 2 0 =ER
(59)
in the case p = 0, where
2 == |11 w ...., J. w 11 E 2
(60)
A = D
-D, E R Nx22/(411
(61)
G: == diag ((2: - (2D.---X... (2D, (.. (.,,,.,.D))),( (2D,
-IX
I) E 222Nx2(((+11
(62)
We proceed in the following steps, which employ arguments similar those of Yang al. 2022a)
(Theorem 2.1) and Peng et al. (2015) (Theorem 1), with minor modifications to account for the inequality constraint in (58). We note that the justification of p-independent 8o boundedness of
solutions given in Peng et al. (2015) appears to be incorrect, with Yang et al. (022a) presenting the correct justification that we follow here.
Solutions to (58) for any < p < 1 are contained in an e ball of p-independent radius C. We let supp(u (u) denote the set of nonzero indices of vector MM denotes the submatrix formed by restricting its columns to an index set S, and M1,s denotes restriction of the rows to an index set and columns to index set S.
Let z" be a solution (58) for arbitrary 0 < <<< 1. Let S supp(z*). Let I {i: (Gz*) ) = 0}.
<
We begin by showing that the matrix
A
As Gr,s]
E (N+
(63)
has full column rank (S). Assume by contradiction that rank rank(Ar,s)) < (S), and therefore A,,ses for some nonzero Cs E |sS Extending Cg to a vector e E (g2((+1) by zero-padding, we thus have Ac = Ar.scs = 0 and therefore A(2" = (c) = Az* = y for any 1 E R. Similarly, G rr,scg 0, and therefore G) + tc) G5z² 0 for any t E R. If > 0 is chosen small enough that sgn( (G(2² + tc));) = sgn( (Gz*),) ):) for i of I, we will thus have G(2* - tc) 2 0. so that 2" + te are both feasible for (58).
Now choose t small enough that, in addition to the previous sign requirement involving G, we also have sgn(2; + tc;)= sgn(2,) for each i S. By strict concavity of + |t| on f (-o0, 0) and t E (0, o0) we have
+ Los + + lcl12
(64)
2
for each E with & + 0 (if e = the above holds with equality). Since least one of the q / 0, this implies that
tteB + -|2" tcll3
| Ip
(65)
strictly. But then at least one of ||" + clB | || or ||= cll < ||=*|| holds strictly. Because
z" + Le are both feasible for (58). this contradicts optimality of
Having shown that Ar,s is full column rank, the rank-nullity theorem implies that ker(A,, = (0).
Therefore Ar,s is injective, and thus 2 is the unique solution to
A 0 う
(66)
This implies that z² lies in the finite set
Z = Ic (UN,,, (I,...,,. + 1)), rank(an Ay,s) = =1S), A1),, = -g =0
(67)
which clearly depends only on A, G. y and not on p. Therefore ||=*||>0 SC maxxez
where C' is independent of p.
29

---

Projection of the feasible set into the positive orthant. Define Ro := | do for an arbitrary
solution 20 to (59) with p 0. Let == max C, Ro for the C' defined above. The set
== { E ( A= = y. Gz 2 0, 1| - R]
(68)
is polytope. As shown above, any solution to 588 for any 0 < p 1 is attained on Q2 and by definition, at least one solution to (59 for 0 is attained on f2
The map > I|| is not concave on all of 2 but it is strictly concave on each individual orthant, so to apply the Bauer maximum principle as in the proof of Theorem 3.2 we will relate (58)
to an optimization over projection of the polytope Ω to the nonnegative orthant R. 2d((1)) To do so, note that the set
V = (2,2²) E R 2dd+1)))
x R
2d(++))
= E 22 1000 S <R
(69)
a polytope in the product space 2T(+)))) x R 2 (Here the module vector |z| is the vector of absolute values of entries of 2.) Because the coordinate projection of polytope is polytope (Goemans (2009),, the set
L' : (2'= R
23(++1)
|| S R. e |2| S s=)}
(70)
which is given by the coordinate projection of v/ onto the z' coordinate, is a polytope in R (d++1) Furthermore, minzen ||=1| = ming ||='||g- To see this, note that for any = E S its module vector |z| E O2', so minzen ||=|| 2 minger ||= If that inequality were strict, then there would be some 2 E f2 with |z| < x!, e arg min 2 lp.. but this would imply that mingen || < min ||
As polytope, Ω' is compact, convex, and has finitely many extreme points, the set of which denote Ext(S'). Let
r= min > 0 z' = ا((+)) T E Ex(()'))
(71)
be the smallest nonzero coordinate in any of the extreme points of S!'
Next, note that for < p < 1, the objective + ||=1| is continuous and strictly concave on the nonnegative orthant IR (d++1) and thus on L Therefore, by the Bauer maximum principle (Aliprantis and Border 2006). Theorem 4.104) a solution to arg ming/ece ||æ'I|ş exists at an extreme point of S2. In particular, by strict concavity of z + ||=|ß, any solution to arg min || [| must
be at an extreme point of ?! (Otherwise, if such a solution had z' = tta' + (1 - t)bb' for distinct
a', D' S and E (0, 1). then ||=||| ||laal13 || + (1 ()]l li > d||²'1 + (1 0)]l="| = || 1B which is impossible.)
Sparse recovery result. Putting everything together, fix an arbitrary 0 < p < 1 and let zp be solution to (58) for that p. The previous paragraph shows that [z, is a solution to arg ming'err || and therefore Ezpl E Ext())). Then:
[3p.s]
|1pp100~ = ||- ||=1lo =
lim 950
(72)
r
i=1
J
12p.sl
P
R
r
min z'Es'
||2 = -r
min *Ei
| =
min =E0
||
21
(73)
R
R
P
min =En
R -110
min =en
=|1
(74)
where the inequalities come from the fact that p + xF is decreasing for E (0, 1) and increasing for x > 1. Because ||0||o is a positive integer for any 2, and (59) attains at least one solution on Ω, the above shows that zp solves (59) for any p satisfying
R
P
min ||2||o min ||=|| + SEn
(75)
log Dog(mingen
|| + 1) log(minzen ||=11o)
p
(76)
log R log
30

---

r < R. or for any 0 0<pe lfr R. (Note that by definition of St', r S R always.)
Let 0, be solution (9) and 0, be solution to (8) for any p which obeys the inequality in (76).
and let 0g and 8, be the corresponding solutions- ollutioss-constructte from solutions and žn to (58) and (59). respectively stated in Lemma 4.1 We have shown that
0 110 llu || lppllo zollo
|1ó/lo ||oullo
(77)
which proves the result.
L
A.3
Experiments
All code for the experiments can found at http:://ggaaul.cc///alaaaaaaaaha nns 1p
A.3.1 Reweighted e algorithm
To implement our proposed @ path norm regularizer, we use the iteratively reweighted e algorithm of Candes et al. (2008) Figueiredo al. (2007). which summarize informally here. The principal motivation is the inequality
|x| < |x|ple|- (1 p)lyl"
(78)
which holds for all R. all y E R (0), and all < s with equality when p 1 and/or when y. Applied to = w we have
K
Uk W S
+ (1 p)lua.ll))
(79)
for any choice of constant yk.r E R {0}. The iteratively reweighted ll algorithm attempts to minimize the e path norm objective on the left hand side of (79) by minimizing its upper bound on the right. Because the choice of uk. Wk, which minimizes this upper bound is invariant to the additive constant (1 p) Utt, term, we can equivalently choose 0i ukk each iteration to minimize only
the first term C [ where Ck. =- plu..i p-11 Because the upper bound is tighter when yk,i is
closer to the optimal values of uy for this iteration f, we choose the constants yk,i as 1/k Wk,
(t-1) (t-1)
where 2/ (t-1) (t-1)
are the previous iterates, The regularization penalty thus becomes
ΣΣ Ck.lukwa.d
(80)
k=l 1=1
which is simply a separable weighted él penalty with weights Cr, This objective lends itself to standard é proximal gradient update algorithm, with each soft-thresholding step scaled appropriately according to the individual threshold Ck The full algorithm is summarized in Algorithm
Algorithm Iteratively reweighted el algorithm for l path norm minimization
Input: loss function L. sparsity parameter < p S 1, learning rate > 0, regularization parameter A 0, total number of iterations T'.
for = 1,..., do
(t-1), (t-1)pp1 Compute thresholds: Ck,i Xpl th Wki
Gradient update for input weights: ūk.s +- wk,
(t-1) > 02(0) (1-1)
Swe, 2
Gradient update for output weights: Un +- 1/ ((-1) > BC(()) (1
Doc 1
Reweighted e prox update: ui,i + Proxce.11 sgn (1ox Ck,
Update input weights: wkgi <- (ggn(1(()) we.s
(t)
Update output weights: (1) +- sgn( / |uulla
satisfies uy = (!!
end for
31

---

We note that there are infinitely many ways to choose the updated input/output weights (t) (t) Ok to satisfy uy = uk wn k.s due to homogeneity of the ReLU (meaning that (ax)+ = a(x)+ for (1)
wi, and
(t),
any a 2 0), any choice "egs <- cuu, and u/ 1/a for any > O would satisfy ug "/ w and produce the same neural network function. The particular choice described in Algorithm 1 additionally satisfies the balancing constraint || || = lu and we find that this selection tends to perform best in practice. We also note that, for univariate input dimension d = 1 and sparsity parameter p = 1, Algorithm iis equivalent to the PathProx algorithm of Yang et al. (2022b).
(1) (
A.3.2 Setup and results
We test our algorithm on two simple synthetic datasets. The first is univariate "peak/plateau" dataset, which consists of the data/label pairs:
(-2,0), (0. 1), (1, (2.0), (3,0)
(81)
For this dataset, the theory of Debarre et al. (0222) shows that the sparsest interpolant f is unique, and is represented using 3 ReLU neurons as
((x) = (= + 1)+ 2(x - 1/2)+ + (x - 2)+
(82)
Our theory in |Sectioon 3 alsso shows that this is a global -"-path norm minimizer for any < p S 1, and is the unique such minimizer for any 0 < < 1.
Fig. 17 shows the sparsity over time of our reweighted ll algorithm for three different values of p E 0.7, implemented in Py Torch using the Adam optimizer, along with that of Adam-only (no regularization) and Adam W weight decay. All networks share the same random initialization and are trained with MSE loss for 100,000 epochs with learning rate 0.01, regularization parameter 01.03 (except for unregularized Adam-only, which uses À 0), and hidden layer width K 80. All three values of in our reweighted el algorithm produce vastly sparser solutions carlier on in training than both Adam-only and AdamW; however, only p 0.4 eventually recovers the true sparsest solution f with 3 ReLU neurons (see Fig. 18).
Fig. shows the functions learned by all five networks throughout the course of training. We see that reweighted el with p E {0.4, 0.7, 1} all converge quickly to near-sparsest solutions, and then the small additional kinks inside [0, 1] disappear gradually throughout training, with only p 0.4 eliminating them completely (the final solutions for E {0.7. } have a single extraneous active neuron of small magnitude which activates just before x: 1/2).
For our second experiment, we consider N 10 data points of each data æ; point are drawn i.i.d. from Unif[ 1/ as are the labels 3/- As in the univariate case, we compare the sparsity over time of our reweighted in PoTccc using the Adam optimizer, against that of Adam-only (no explicit regularization) and Adam W weight decay. All networks are trained using MSE loss for 100,000 epochs with learning 0.005 (except for unregularized Adam-only, which uses
50 dimensions. The coordinates
algorithm for E {0.4, 0.7, 1), implemented
rate y 0.01, regularization parameter = 0), and hidden layer width K = 100. Fig. 20 shows that all values of p produce much sparser solutions than Adam-only and Adam weight decay, with p = 0.4 producing sparser solutions than E {0.7, 1). The solutions recovered by p E (0.4, 0.7, 1 } all obey the sparsity upper bound of 2N guaranteed by the proof of Propositiin 4.1
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims of Theorems 3.1 3.2 and 4.1 are supported with rigorous proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
32

---

sparsity over time: peak/plateau dataset in d 1
sparsity (active neuron count)
regularization
AdamW WD
reweighted gd (p 0.4)
reweighted 2 (p 0.7)
reweighted f (p 1)
101
true sparsest
20000
40000
60000
80000
100000
epoch
Figure 17: Sparsity over time of five networks trained to interpolation on the univariate peak-plateau dataset (8I). The reweighted L algorithm for ! path norm minimization AAlgriihhm I) recovers much sparser solutions earlier training than unregularized Adam or Adam weight decay regularization, with the smallest value 0.4 eventually recovering the sparsest possible interpolant (82).
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
we discuss limitations and possible future directions Section 6
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
33

---

no regularization
1.4 AdamW WD
reweighted f (p 0.4)
1.2
data
1.0
0.8
f(x)
0.6
0.4
0.2
0.0
-4
-3
-2
-1
3
Figure 18: Three interpolants of the peak-plateau dataset, learned after 100,000 epochs using unregularized Adam, AdamW weight decay, and reweighted L (Algorithm 1) with = 0.4. Only the latter recovers the true sparsest interpolant (2).
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: all necessary assumptions are made clear in the theorem statements, and full rigorous proofs are provided in the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
34

---

learned functions, epoch 20000
learned functions, epoch 40000
segulersation
regulerisation
Adamm WD
Adami WD
f
gitted 1l
ghotod
1.0. peoe ghttd El 11 dota
1.0
FMOM ghitd ip 31 d07a
0.6
0.0
02-
epoch
functions, spoch
regularzation
regularization Adomm VID
Adomi WD
1.4
rewe gited (- 0.4)
rewe ghttdd ( 0.4)
more ghteed ip 11
rewe gatted
data
201a
0.8
0.8
02
regelatization
Adamit
neoe ghted El D-4)
1.-
neve gli
dota
0.8
02
Figure 19: Learned network functions of five different algorithms throughout the course of training. Reweighted e with p E (0.4,0.7,1 converge to near-sparsest solutions early on training, with only p 0.4 eventually climinating all extraneous neurons recover the true sparsest solution
35

---

sparsity over time: N 10, d= 50, data/labels in Unif[-1,1]
103
Cearsii (Ex [ExllvawWllol
no regularization
AdamW WD
reweighted { (p 0.4)
reweighted f (p 0.7)
reweighted (p = 1)
10a
2N (upper bound on true min sparsity)
10
0
20000
40000
60000
80000
100000
epoch
Figure 20: Sparsity over time of five networks trained interpolation on N 10 uniform random data points in d = 50. The solutions obtained by the Lt algorithm Algorithm 1) for {0.4, 0.7,1) satisfy the sparsity upper bound of 2.V guaranteed by the proof of Proposition
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [NA]
Justification: no experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contríbution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully
36

---

might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: all code for the experiments is available publicly at the aforementioned https://githun: comm:julaanaktheh//paaar. _ns__ps_ppp
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
boblic/guides.. htti://guiiiee//eeuubbmeeeeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https htips.ccc/ubllcc/eeeccc htw.a//acguuuueeee/oooeebbbaaaaa
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
37

---

Answer: [Yes]
Justification: details of experiments are fully described in Appendix A.3
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: our experiments are performed only on synthetic data and are meant to illustrate the feasibility the regularizer proposed by our theory; as such, statistical significance tests are not necessary.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: our experiments small-scale and computationally light and can easily be run on almost any computational setup, so we do not feel the need to report specifics on the compute resources.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
38

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our paper has no social consequences.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper has no societal impacts.
Guidelines:
The answer NA means that there no socictal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: no risks of data or model misuse.
Guidelines:
The answer NA means that the paper poses such risks.
39

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: no of existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: no new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: no crowdsourcing human subject research.
40

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: no human subject research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs were used for writing/editing, literature review, and occasional assis- tance in proving theorems (mainly searching for related/relevant existing results), which we do not consider important, original, non-standard usage.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy for what should or should not be described.
41


Reviews:
[{"review_id": "zWir5UX8EO", "reviewer": "Reviewer_AdaJ", "summary": "This paper demonstrates that the lp path norm (0 < p < 1) can induce the sparsest neural networks (l0 minimization). The uniqueness of the global minimizer (in the functional space) and the equivalence of lp to the l0 minimization problem when p is small enough are proved first in a one-hidden-layer and single-input-single-output ReLU network, and then generalized to a multi-input-single-output setting.", "questions": "Could you please provide some numerical examples for lp path norm minimization?", "limitations": "The author has already mentioned some limitations in the conclusion part, including the two weaknesses I have raised.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n\n- The mathematical analysis appears to be well done. However, I didn't verify all the details in practice.\n- The theoretical implications are inspiring for designing neural networks.\n\n\nWeakness\n\n- Practitioners might look forward to more practical implications. For example, does the conclusion still hold for neural networks with ReLU networks with one hidden layer? At first glance, such neural networks also fall into the CPWL class, but I am unsure whether the technique can be generalized.\n- The hardness in optimization might prevent the practical application. I think the lp path norm is another non-convex term, which introduces more concerns in optimization. Maybe some numerical examples could be there to demonstrate the practical values of the conclusions.\n- Some references about empirical methods for training sparse neutral networks are missing. Specifically, I would like to mention the sparsity via the re-parametereization tricks [1] and its important follow up [2].\n\n[1] https://arxiv.org/abs/2210.01212\n[2] https://arxiv.org/abs/2307.03571", "was_revised": true, "final_justification": "My questions about the limitations and implementations are well discussed in the rebuttal period. I believe the authors are willing to include this part in the next revision, which will benefit many readers.", "rebuttal": "We thank the reviewer for their careful evaluation of our work and for their feedback. Below we address the questions and concerns individually.\n- **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: \n    - 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. \n    - 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. \n    \n    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.\n\n[1] Ergen and Pilanci. \"Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs.\" 2021.\n\n- **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.\n\n[2] Lyu et al. \"A comparison of typical $\\ell^p$ minimization algorithms.\" 2013.\n[3] Kolb et al. \"Deep Weight Factorization: Sparse Learning through the Lens of Artificial Symmetries.\" 2025.\n\n- **Additional references:** we thank the reviewer for the recommendation and will include the cited papers in our related work section."}, {"review_id": "O8ZYMXaIs2", "reviewer": "Reviewer_k9Kj", "summary": "This work introduces a continuous regularization objective for single-hidden-layer ReLU networks using the ℓ^p​ path norm for 0<p<1. The authors prove that global minimizers of this objective correspond to the sparsest possible interpolating networks. This work recasts the combinatorial ℓ^0​ minimization into a smooth optimization, offering a principled, gradient-based alternative to heuristic pruning methods for achieving guaranteed sparsity.", "questions": "- The theory relies on a data dependent threshold p. From a practical perspective, how should a user choose an appropriate p during training?\n- The analysis is confined to single-hidden-layer networks. What are the primary theoretical obstacles to extending these guarantees for ℓ^p/ℓ^0 equivalence to deep ReLU networks?\n-Your work focuses on creating the sparsest possible model for a given dataset, which is acceptable for model compression. But, have you also tested how well these highly sparse models perform on new, unseen data? I am wondering how their accuracy compares to models trained with more standard regularizers.", "limitations": "- The theoretical sparsity guarantees only hold for sufficiently small values of p in the ℓp norm. However, the work does not provide a practical method to compute or estimate the critical threshold p* below which sparsity is guaranteed.\n- The theoretical results are derived for shallow, single-hidden-layer ReLU networks. Although some results are extended to arbitrary input dimensions, the work does not address deeper architectures, which are more common in modern deep learning practice.\n- The paper focuses entirely on theoretical results, with no empirical experiments to validate the practical performance of the proposed regularization method.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "The work provides a rigorous theoretical guarantee that a continuous, almost-everywhere differentiable objective can produce the sparsest interpolating ReLU network. This transforms a difficult combinatorial ℓ^0 problem into a smooth optimization task and provide a principled alternative to heuristic, multi-stage pruning algorithms.\n \nThe analysis for the univariate case is strong and establishes not only sparsity but also the uniqueness of the solution for almost every p ∈ (0,1).\nThe authors successfully extend the core findings to the multivariate setting. By reformulating the optimization, they prove that for any dataset there exists a threshold p below that the ℓ^p​ minimizer is an ℓ^0​ (sparsest) solution.\nThe theoretical guarantees apply only to single-hidden-layer networks. Extending the analysis to deeper or convolutional architectures remains an open challenge, which limits the immediate applicability of the proposed objective.", "was_revised": true, "final_justification": "The score was adjusted based on the authors' rebuttal.", "rebuttal": "We thank the reviewer for their careful evaluation of our work and for their feedback. Below we address the questions and concerns individually.\n- **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: \n    - 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. \n    - 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. \n    \n    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.\n\n[1] Ergen and Pilanci. \"Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs.\" 2021.\n\n- **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.\n\n[2] Tillman and Pfetsch. \"The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing.\" 2013.\n\n\n\n- **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.\n\n[3] Kolb et al. \"Deep Weight Factorization: Sparse Learning through the Lens of Artificial Symmetries.\" 2025."}, {"review_id": "3usyuJ4p2r", "reviewer": "Reviewer_5Uw1", "summary": "This work proves that for sufficiently small $p$, miniming the $p$-path norm yields the sparsest shallow neural networks that interpolate the data.", "questions": "The results focus on min-norm interpolants. What can be said about solutions to the regularized problem $min Loss + \\lambda p\\text{-path norm}$? This paper is significantly more impactful if it can be said that minimizers of the regularized problem for sufficiently small $p$ correspond to \"sparsest\" solutions in some sense. Similarly, can anything be said about how close (S)GD, adam, etc.. run on the regularized objective gets to finding \"sparsest\" networks?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Theory is rigorous and insightful.\nRelationship to prior work is clear. It is clear that there is broad interest in finding sparse neural networks, and that prior work does not provide a way to find the *sparsest* solutions, nor does it provide a way to find sparse solutions very efficiently. This work does both.\n\nThe main weakness of this setting is the focus on exact min-norm interpolants. In practice, one would probably run an optimization method (SGD, adam, etc.) on the regularized objective to train the networks.\n\nThe univariate variational reformulation in Prop 3.1 seems closely related to \"How do infinite width bounded norm networks look in function space?\" by Savarese et al. (2019) and \"Noisy Interpolation Learning with Shallow Univariate ReLU Networks\" by Joshi et al. (2023) (though these works do not focus on finding sparsest solutions). Can you cite and compare to these papers?\n\n*Minor comments:*\n- Line 26: are purposes = our purposes\n- Line 308: is eq (48) the correct reference?", "was_revised": true, "final_justification": "This paper has strong theory on a problem of significant interest. My original concerns were about: \n\n1. The application to the regularized problem, which has been addressed.\n2. The lack of insight about optimization methods, which is a hard problem outside the scope of this paper\n3. Discussing a few missing pieces of related work, which has been addressed.\n\nTherefore I keep my positive score.", "rebuttal": "We thank the reviewer for their careful evaluation of our work and for their feedback. Below we address the questions and concerns individually.\n- **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).\n- **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.\n- **Minor comments:** we will fix the typo and the incorrect equation reference in line 308.\n\n[1] Boursier and Flammarion. \"Penalising the biases in norm regularisation enforces sparsity.\" 2023."}, {"review_id": "C7OCs9263M", "reviewer": "Reviewer_vc8p", "summary": "The paper introduces a smooth ℓₚ (0<p<1) path-norm regularizer for single-hidden-layer ReLU networks whose global minimizers provably coincide with the sparsest interpolating networks—i.e., those with the fewest nonzero neurons—thereby recasting the combinatorial ℓ₀ problem as a differentiable objective . In the univariate case, it additionally establishes uniqueness (for almost every p), explicit N–2 width and parameter bounds, and Lipschitz control, while in arbitrary dimensions it shows that for sufficiently small p any minimizer recovers an ℓ₀ solution via a finite-dimensional concave-over-polytope reformulation.", "questions": "1. How might the theory extend to deeper ReLU architectures—do global minimizers of the ℓₚ path‐norm still recover sparsest networks beyond one hidden layer?\n\n2. What practical guidelines can you offer for choosing “sufficiently small” p to balance sparsity recovery against numerical stability during optimization?\n\n3. Have you tested the concave‐over‐polytope reformulation empirically in moderate‐ to high‐dimensional settings, and if so, how does its computational cost scale?", "limitations": "None", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Overall Strengths\n\n* Provable Sparsity Guarantees: Establishes that global minimizers of the smooth ℓₚ path‐norm (0<p<1) exactly recover the sparsest ReLU networks, effectively bridging continuous optimization and combinatorial ℓ₀ minimization.\n\n* Rigorous Univariate Analysis: Provides uniqueness of minimizers (for almost every p), explicit width‐(N–2) and parameter bounds, plus Lipschitz control in the one‐dimensional case.\n\n* General‐Dimension Extension: Shows that for sufficiently small p, any minimizer corresponds to an ℓ₀ solution via a finite‐dimensional concave‐over‐polytope reformulation, highlighting broad applicability.\n\n\nOverall Weaknesses\n\n* Architectural Limitation: Analysis is confined to single‐hidden‐layer ReLU networks; it remains unclear how these results extend to deeper or more complex architectures.\n\n* Choice of p: Requires “sufficiently small” p < 1 for the general‐dimension result, but offers limited practical guidance on selecting p or managing numerical instability as p→0.\n\n* Computational Scalability: The concave‐over‐polytope reformulation, while elegant, may be intractable in high dimensions without further algorithmic development.", "was_revised": true, "final_justification": "In the light of authors' response, my concerns has been clarified to some extent so I increased my score.", "rebuttal": "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.\n- **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.\n- **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: \n    - 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. \n    - 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. \n    \n    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.\n\n[1] Ergen and Pilanci. \"Global Optimality Beyond Two Layers: Training Deep ReLU Networks via Convex Programs.\" 2021.\n\n- **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.\n\n[2] Tillman and Pfetsch. \"The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing.\" 2013.\n- **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."}]

Author rebuttal:

Meta-review: The main contribution of this paper is to show that minimizing $\ell_p$$ quasinorms of the weights of a 2-layer neural network (i.e. single-hidden-layer neural network) subject to an interpolation constraint corresponds to the sparsest possible interpolating network. The reviewers generally liked this insight and considered it to be a novel contribution to the mathematics of neural networks, despite some small limitations that were raised (e.g. limitation of the analysis to one hidden layer, the objective remaining nonconvex even when cast in continuous objective function form). The authors are highly recommended to include all of the detailed clarifications that they provided during the rebuttal phase in the camera-ready version.
Decision: Accept (poster)