Penalising the biases in norm regularisation enforces sparsity
Authors: Etienne Boursier
Nicolas Flammarion
Venue: NeurIPS 2023 poster (2023)
Keywords: Neural networks
Min norm interpolators
Sparsity
Representational cost
TL;DR: For one hidden ReLU layer networks with unidimensional data, we characterise the parameters' norm required to represent a function, as well as the sparsity (in kinks) of min norm interpolators.

Abstract: Controlling the parameters' norm often yields good generalisation when training neural networks. Beyond simple intuitions, the relation between regularising parameters' norm and obtained estimators remains theoretically misunderstood. 
For one hidden ReLU layer networks with unidimensional data, this work shows the parameters' norm required to represent a function is given by the total variation of its second derivative, weighted by a $\sqrt{1+x^2}$ factor. Notably, this weighting factor disappears when the norm of bias terms is not regularised. The presence of this additional weighting factor is of utmost significance as it is shown to enforce the uniqueness and sparsity (in the number of kinks) of the minimal norm interpolator. Conversely, omitting the bias' norm  allows for non-sparse solutions.
Penalising the bias terms in the regularisation, either explicitly or implicitly, thus leads to sparse estimators.

Penalising the biases in norm regularisation enforces sparsity
Etienne Boursier INRIA CELESTE, LMO, Orsay, France etienne. boursier@inria.ft
Nicolas Flammarion TML Lab, EPFL, Switzerland nicolas, forllas.laamaaree flammarion@eplllccmmmmmmm
Abstract
Controlling the parameters' norm often yields good generalisation when training neural networks. Beyond simple intuitions, the relation between regularising parameters' norm and obtained estimators remains theoretically misunderstood. For one hidden ReLU layer networks with unidimensional data, this work shows the parameters' norm required to represent a function given by the total variation second derivative, weighted by v1 + x factor. Notably, this weighting factor disappears when the norm of bias terms is not regularised. The presence of this additional weighting factor is utmost significance as it is shown to enforce the uniqueness and sparsity (in the number of kinks) of the minimal norm interpolator. Conversely, omitting the bias" norm allows for non-sparse solutions. Penalising the bias terms in the regularisation, either explicitly or implicitly, thus leads to sparse estimators.
1 Introduction
Although modern neural networks not particularly limited in terms of their number of parameters. they still demonstrate remarkable generalisation capabilities when applied to real-world data [Belkin al. 2019 Zhang et al. 2021]. Intriguingly, both theoretical and empirical studies have indicated that the crucial factor determining the network's generalisation properties is not the sheer number of parameters, but rather the
of these parameters [Bartlet] 1996 Neyshabur et al.) 2014). This norm is typically controlled through a combination of explicit regularisation techniques, such as weight decay (Krogh and Hertz [991], and some form of implicit regularisation resulting from the training algorithm employed [Soudry et al.
2018 Lyu and Li 2019 Ji and Telgarsky 2019 Chizal
and Bach 2020].
Neural networks with a large number of parameters can approximate any continuous function on compact set [Barron [993]. Thus, without norm control, the space of estimated functions encompasses all continuous functions. In the parameter space, this implies considering neural networks with infinite width and unbounded weights (Neyshabur al. 2014). Yet, when weight control is enforced, the exact correspondence between the parameter space (i.e., the parameters 0 of the network) and the function space (i.c., the estimated function fe produced by the network's 's output) becomes unclear. Establishing this correspondence is pivotal for comprehending the generalisation properties of overparameterised neural networks. Two fundamental questions arise.
Question 1. What quantity in the function space, does the parameters' norm of neural network correspond to?
Question 2. What functions are learnt when fitting training data with minimal parameters' norm?
We study these questions in the context of one-hidden ReLU layer network with skip connec- tion. Previous research Kurková and Sanguineti 2001 Bach 2017] has examined generalisation guarantees for small representational cost functions, where the representational cost refers to the 37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

norm required to parameterise the function. However. it remains challenging to interpret this rep- resentational cost using classical analysis tools and identify the corresponding function space. To address this issue, Question[] seeks to determine whether this representational cost can be translated into a more interpretable functional (pseudo) norm. Note that Question | studies the parameters' norm required to fit function on an entire domain. In contrast, when training a neural network for regression task, we only fit finite number of points given by the training data. Question 2 arises to investigate the properties of the learned functions when minimising some empirical loss with regularisation of the parameters' norm regardless of whether it is done explicitly or implicitly.
In relation to our work. Savarese et al. [019]] Ongie et al. [2019] address Question for one- middhddeen layer ReLU neural networks, focusing on univariate and multivariate functions, respectively. For a comprehensive review of this line of work, we recommend consulting the survey of Parbi and
Nowak 2023]. On the other hand, Parhi and Nowak [021]. Debarre et al.] [2022]. J. Stewart et al. [2022] investigate Question specifically in the univariate case. Additionally, (annfrdd et al. [2022] 2
examine a particular multidimensional case. However, all of these existing studies overlook the bias parameters of the neural network when considering the &g regularisation term. By omitting the biases,
the analysis and solutions to these questions become simpler.
In sharp contrast, our work addresses both Questions D and 2 for univariate functions while also incorporating regularisation of the bias parameters. It may appear as minor detail is commonly believed that similar estimators are obtained whether or not the biases' norm is penalised [see e.g. Ng 201T. Nonetheless, our research demonstrates that penalising the bias terms enforce sparsity and uniqueness of the estimated function, which is not achieved without including the bias regularisation The practical similarity between these two explicit regularisations can be attributed to the presence of implicit regularisation, which considers the bias terms as well. The updates performed by first-order optimisation methods do not distinguish between bias and weight parameters, suggesting that they are subject to the same implicit regularisation. Consequently, while both regularisation approaches may yield similar estimators in practical settings, we contend that the theoretical estimators obtained with bias term regularisation capture the observed implicit regularisation effect. Hence, it is essential to investigate the implications of penalising the bias terms when addressing Questions] [ answers obtained in this scenario significantly differ from those without bias penalisation.
[add] 2
as the
also worth mentioning that Shevchenko et al. [022]] Safran et al. 2022 prove that gradient flow learns sparse estimators for networks with ReL.U activations. These sparsity guarantees are yet much weaker (larger number of activated directions) as they additionally deal with optimisation considerations (in opposition to directly considering the minimiser of the optimisation problem in both our work and the line of works mentioned above).
Contributions. After introducing the setting in Section 2 we address Question I in Section B Jusing similar analysis approach as Savarese et al. [2019]. The key result, Theorem I establishes that the representational cost of a function, when allowed a free skip connection, given by the weighted total variation of its second derivative, incorporating v1 + x² term. Notably, penalising the bias terms introduces a /1 + x² multiplicative weight in the total variation, contrasting with the absence of bias penalisation.
This weighting fundamentally impacts the answer Question In particular, it breaks the shift invariance property of the function's 's representational cost, rendering the analysis technique proposed cechniqueppooposed by Debarre al. [2022] i To address this issue, we delve in Sections 4 and into the computation and properties of solutions to the optimisation problem:
inf 11++222 z"
subject to Vi E [m], f(x)) = yc-
TV
In Section 4 analysis of the minimisation problem. Leveraging this dynamic program reformulation, Section establishes the uniqueness of the solution. Additionally, under certain data assumptions, demon- strate that the minimiser is among the sparest interpolators in terms of the number of kinks. It is
reformulate this problem continuous dynamic program, enabling a simpler
'Even though Goodfellow et al. 2016 Chapter 7] claim that penalising the biases might lead to underfitting, work does not focus the optimisation aspect and assumes interpolation occurs.
2 AAthouggh shift invariance is useful for analytical purposes, it is not necessarily desirable in practice. Notably, Nacson et al. 2202) show that dealing with uncentered data might be beneficial for learning relevant features, relying on the lack of shift invariance.

---

worth noting that similar results have been studied in the context of sparse spikes deconvolution [Candes and Femandeez 2014 Fernandez-Grane
2016 Poon al. 2019], and our problem
can be seen as generalisation of basis pursuit [Chen et al. 2001 to infinie-diimnsionall parameter spaces. However, classical techniques for sparse spikes deconvolution are ill-suited for addressing Question 2 the set of sparsest interpolators is infinite in our setting.
Finally, the significance of bias term regularisation in achieving sparser estimators during neural network training is illustrated on toy examples in Section 6 To ensure conciseness, only proof sketches are presented in the main paper, while the complete proofs can be found in the Appendix.
2 Infinite width networks
This section introduces the considered setting, representing unidimensional functions infinite width networks. Some precise mathematical arguments are omitted here, since this construction follows directly the lines of [Savarese al. (211)). Ongie al. (201).. This work considers unidimensional functions fo TR + parameterised by a one hidden layer neural networks with ReI.U activation as [o(x) -ド (uo + b;),
where (2) = max(0, 2) is the ReLU activation and 0 = (az. wy. Jemmm] E 3.3m are the parameters defining the neural network. The vector = (aj))e[m) stands for the weights of the last layer, while w and respectively stand for the weights and biases of the hidden layer. For any width m and parameters 0, the quantity of importance is the squared Euclidean norm of the parameters: ||0113 = ー az w3 +1z.
We recall that contrary to Savarese al. [2019), Ongie et al. 2019] the bias terms are included in the considered norm here. We now define the representational cost of a function f IR + R as
1
R()) inf 10112 such that So = f.
m RER
2
By homogeneity the parameterisation, a typical rescaling trick [see e.g. Neyshabur et al. 2014 Theorem I] allows to rewrite
R(f)= = inf ||a|| such that fo = and w² + b] = 1 for any j E [m]]
mm.
Note that R(f) is only finite when the function f is exactly described as finite width neural network. We aim at extending this definition to much larger functional space, i.e. any function that be arbitrarily well approximated by finite width networks, while keeping a (uniformly) bounded norm of the parameters. Despite approximating the function with finite width networks, the width necessarily grows to infinity when the approximation error goes to O. Similarly to tonnniie et al. [2019). define
R(f)
lim inf -
|00 such that (fo(z) - f(x) S E for any [-1/e, Val)
mm.ER
Note that the approximation has to be restricted to the compact set [-1/e, 1/s] to avoid problematic degenerate situations. The functional space for which R(()) finite much larger than for R. and in- cludes every compactly supported Lipschitz function, while coinciding with R when the latter is finite.
By rescaling argument again, can assume the hidden layer parameters (wj, by) are in S and instead consider the ε norm of the output layer weights. The parameters of network can then be seen discrete signed measure the unit sphere S,. When the width goes to infinity, limit is then properly defined and corresponds to a possibly continuous signed measure. Mathematically, define (S1) the space of signed measures μ on S with finite total variation || Following the typical construction of Bengio et al. [2005), Bach [2017]. an infinite width network is parameterised by a measure μ E MMS1) ag
fa : 1 Je, (wwz + b)dp(w, (w, b).
Similarly to Ongie et al. [2019] R() verifies the equality
R(()) inf ||ll|y such that f = Sp-
By abuse of notation, we write both fe and fr, as it is clear from context whether the subscript is a vector measure.
3

---

The right term defines the Fi norm Kurková and Sanguineti 2001 i.e. R(f) IIfll The Fi norm is intuited be major significance for the empirical success of neural networks. In particular. generalisation properties of small Fi norm estimators are derived by Kurková and Sanguineti [200]] Bach [017]. while many theoretical results support that training one hidden layer neural networks with gradient descent often yields an implicit regularisation on the Fi norm of the estimator (Lyu and Li 2019 Ji and Telgarsky| 2019] Chizat and Bach 2020 [oursier et al. 2022]. However, this implicit regularisation of the Fi norm is not systematic and some works support that different quantity can be implicitly regularised on specific examples [Razin and Cohen 2020 Vardi and Shamir 2021 Chistikov al.) 2023] Still, Fi norm seems to be closely connected to the implicit bias and its significance is the main motivation of this paper. While previous works also studied the representational costs of functions by neural networks (Savarese al., 2019 Ongie al., [019]] they did not penalise the bias term in the parameters" norm, studying a functional norm slightly differing from the Fi norm. This subtlety is the origin of different levels of sparsity between the obtained estimators with or without penalising the bias terms, as discussed in ( [ where sparsity of an estimator here refers to the minimal width required for network to represent the function (or similarly to the cardinality of the support of in Equation (I). This notion of sparsity is more meaningful than the sparsity of the parameters here, since different 0 (with different levels of sparsity) can represent the exact same estimated function.
2.1 Unpenalised skip connection
Our objective is now to characterise the Fi norm of unidimensional functions and minimal norm interpolators, which can be approximately obtained when training neural network with norm regularisation. The analysis and result yet remain complex despite the unidimensional setting. Allowing for an unpenalised affine term the neural network representation leads to a cleaner characterisation of the norm and description of minimal norm interpolators. As consequence, parameterise in the remaining of this work finite and infinite width networks as follows:
do + bo + fa(x), and fu where (ao, bo) E R.2 The affine part og + by actually corresponds to a free skip connection in the neural network architecture [He et al. (016) and allows to ignore the affine part in the representational cost of the function f. which we now define as
fe bo
dg + bo + fx(x),
(... inf E-0+
1 11101 such that 2
Ri(f)=
lim
Iff (x) f(x)] S E for any E [->//, 1/al
m,.0xa (ER?
The representational cost (f) is similar to R(f), but allows for a free affine term in the network architecture. Similarly to R(S), can be proven, following the lines of Savarese al. [2019] Ongie
al. 2019) that Rí (f) verifies
Ri(
inf |allyy such that f fn.ag.bu
(EM((.)
ao.6nER
The remaining of this work studies more closely the cost (f).. Theorem 1 in Section 3 can be directly extended to the cost R(f), i.e. without unpenalised skip connection. adapted version is given by Theorem in Appendix C for completeness.
Multiple works also consider free skip connections it allows for simpler analysis [e.g. Savarese et al.] 2019 Ongie et al. 2019 Deharre et al. 2002 [anfford et al. [002]. Since a skip connection can be represented by two ReL. neurons (2 (=) (()2)), it is commonly believed that considering a free skip connection does not alter the nature of the obtained results. This belief is further supported
by empirical evidence in Section 6 and Appendix B where our findings hold true both with and without free skip connections.
Representational cost
Theorem below characterises the representational cost Tt, (J) of any univariate function.
Theorem 1. For any Supschitzzuunction f :R IR
Ri(() = || IT = 1 x1
4

---

For any con-Lipschitt,uucttin R1(f) = oc.
In Theorem I f is the distributional second derivative of f. which is well defined for Lipschitz functions. Without penalisation of the bias terms, the representational cost is given by the total variation of l" [Savarese et al. 2019). Theorem [ states that penalising the biases adds a weight vI+ x² to f" This weighting favors sparser estimators when training neural networks, as shown in Section 5 Also, the space of functions that can be represented by infinite width neural networks with finite parameters' norm, when the bias terms are ignored, corresponds to functions with bounded total variation of their second derivative. When including these bias terms in the representational cost, second derivatives additionally require a light tail. Without a free affine term, Theorem 4 in Appendix C characterises R()), which yields additional term accounting for the affine part of ʃ.
We note that Remark 4.2 H: and Wojtowytsch [202T] and Theorem by Li et al. [2020b] are closely related to Theorems and 4 However, these results only establish equivalence between the norm R(f) and another norm that quantifies the total variation of vI /1++* + aside from the affine term.
Our result, on the other hand, provides an exact equality between both norms, which proves to be particularly useful in the analysis of minimal norm interpolators.
Example 1. If the function f is given by a finite width network f(x) = Ei= a:o(wa + b,) with ai Wh + O and pairwise different ;;; Theorem I yields Rı( Ei= lail ur by. This exactly
corresponds to half of the squared Eg norm of the vector (ceas, wi di oz c )i= when G₁ =
m 1
[0:1
This vector is thus minimal representation of the function f.
According to Theorem T the minimisation problem considered when training one hidden ReLU layer infinite width neural network with & regularisation is equivalent to the minimisation problem
inf Eu(G)) w.2² + V1+ x2
What types of functions do minimise this problem? Which solutions does the || و² regularisation term favor? These fundamental questions are studied in the following sections. We show that this regularisation favors functions that can be represented by small (finite) width neural networks. On the contrary, when the weight decay term does not penalise the biases of the neural network, such a sparsity is not particularly preferred as highlighted by Section
4 Computing minimal norm interpolator
To study the properties of solutions obtained by training data with either an implicit or explicit weight decay regularisation, we consider the minimal norm interpolator problem
inf } 110112 such that Vi E [n]] fa.an.by (x.,) yi:
1
(3)
0,0g.h0 2
where (I,, V))keenj that the observations 2, are ordered, i.c.. 21 < <x² <... Z,, Thanks to Theorem [ this problem equivalent, when allowing infinite width networks, to
2R2 is training set. Without loss of generality, we assume in the following
inf +
such that Vi E [n], f(x;) = yi-
(4)
Lemma I Tbelow actually makes these problems equivalent as soon as the width is larger than some threshold smaller than n 1. Equation 4 then corresponds Equation (2) when the regularisation parameter À is infinitely small.
Lemma 1. The problem in Equation 0}, any minimiser is of the form
admits a minimiser. Moreover, with in == min{i E [mi]a 2
f(x) ar b Σx=1 ai(x Ti)+ where Tú E (zi, 1:41) for any i E i1, - 2}. T E (Iig- Dio)) and T3 E [T,, x411) for any i E {io. .o....... 1).
Lemma T already provides a first guarantee on the sparsity of any minimiser of Equation 4 indeed includes at most n 1 kinks. In contrast, minimal norm interpolators with an infinite number
5

---

of kinks exist when the bias terms are not regularised [Debarre et al., 2022]. An even stronger sparse recovery result is given in Section 5 Lemma can be seen as a particular case of Theorem of Wang et al. [222]] In the multivariate case and without free skip connection, the latter states that the minimal norm interpolator has at most one kink (i.e. neuron) per activation cone of the weight and has no more than n + 1 kinks in total. The idea of our proof is that several kinks among a single activation cone could be merged into a single kink in the same cone, The resulting function then still interpolates, but has smaller representational cost.
Lemma | allows to only consider parameters for each interval (I,, 2y+1) (potentially closed at one end). Actually, the degree of freedom is only 1 on such intervals: choosing a, fixes Tj (or inversely) because of the interpolation constraint. Lemma below uses this idea recast the minimisation Problem 4 as a dynamic program with unidimensional state variables E IR for any E [n]].
Lemma 2. If æn < O and In 2 O, then we have for in = min(i E [vx] 20 2 0} the following equivalence of oppiiissatinn problems
|| V [v++23 8"
min
min Pig (Sior Sig 1) + Cio 18 + Cāo (8io) (8ig-1.811 EEA
(5)
where the set A and the functions 9i and c, defined in Equations O 8 below.
Let us describe the dynamic program defining the functions Ci, which characterises the minimal norm
interpolator thanks to Lemma First define for any i E [nz - 1], the slope 5, == 1+++ 2t, the function
I1+1
I-+1 (8:41, 8;) == V (1141 5.) 2s(s: 5,))² + (81+1 si)² for any (8141, 5:) R2;
(-o0, 6.] if > ó;
and the intervals St(s) = (5.) if ==s=6. 5;
for any E I.
Jō to0) if < di
The set A is then the union of three product spaces given by
A == (-o0, -1) x (5% +oo) U ((610-1, 1)) U (0 +00) x x(=xx=0 (-00, 0io
(7)
Finally, we define the functions c2 : R + R_ recursively as C1 = Cn = 0 and
C++1 8141
min 9i+1 (81+1, + (8:) #EES:(F111)
for any i E {I,...,uu 2}
(8)
G 8 min Di+ 88) + c (8:+1) for any E {io................. T1 1}. (1168,(s))
Equation 8 defines a dynamic program with a continuous state space. Intuitively for i 2 io. the variable 8; accounts for the left derivative at the point x;, The term gi+1 (8++1,8;) the minimal cost (in neuron norm) for reaching the point (Ii+1, (++1) with a slope 8141, knowing that the left slope 8; at the point (Ii, yt). Similarly, the interval (s;) gives the reachable slope at 11+1, knowing the slope in 2; is 8j. Finally, (s;) holds for the minimal cost of fitting all the points (1i+1, 11+1),..... (I', Dn) when the left derivative in (I., y1) is given by 8,, is defined recursively by minimising the sum of the cost for reaching the next point (I744 1, Vi4 with slope 8;4 i, given by Be+1(8+42 8 and the cost of fitting all the points after #++1, given by 6,41- This recursive definition is illustrated in Figure bellow. A symmetric definition holds for i << in-
The idea to derive Equation (6) to first use Lemma to get a finite representation of a minimal function f From there, the minimal cost for connecting the point (I:+1, )) with (I;, yi) is done by using a single kink in between. The restrictions given by s; and 8;41 then yield a unique possible kink. Minimizing its neuron norm then yields Equation (6)
Remark 1. Equation () actually considers the junction of two dynamic programs: first one corresponding to the points with negative values and a second one for positive values. This separation around x = O is not needed for Lemma 2 but allows for a cleaner analysis in Section 5 Lemmas 7 a hold for any arbitrary choice of ig In particular for in 1, Equation (5) would not consider the junction of two dynamic programs anymore, but a single one.
"See Equation (21
the Appendix for mathematical definition.
'Here, single kink is used in the interval [si, J.+1]. thanks to Lemma

---

kink of cost
1.25
(i+e( s))
1.00
9241
0.75
0.50
&
0.00
lotal cost.
0.25
c(())
total cost
00.00
0.0
0.2
0.4
0.6
1i+1 0.8
Figure 1: Recursive definition of the dynamic program for i 2 ig-
The assumption 21 < and In 2 O is not fundamental, but only required properly define the junction mentioned in Remark D If all the values are positive (or negative by symmetry), the analysis of the right term in Equation (5) simplified, since there is no junction to consider In particular, all the results from Section hold without this assumption. These results are proven in the hurdest case 31 < and In 2 Appendix from which other cases can be directly deferred.
Remark
Lemma 2 formulates the minimisation of the representational cost among the interpolating functions as a simpler dynamic program on the sequence slopes at each H₁. This equivalence is the key technical result of this work, from which Section S defers many properties on the minimiser(s) of Equation
5 Properties of minimal norm interpolator
Thanks the dynamic program formulation given by Lemma 2 this section derives key properties the interpolating functions minimal representational cost. In particular, shows that Equation (4) always admits unique minimum. Moreover, under some condition the training set, this minimising function has the smallest number of kinks among the set of interpolators.
Theorem 2. The following optimisation problem admits a unique minimiser:
inf V1+ x²
such that Vi E [ni] f(x;) yi-
The proof of Theorem Juses the correspondence between interpolating functions and sequences of slopes (5:) E S, where the set defined by Equation (23 Appendix D.2 In particular, we show that the following problem admits unique minimiser:
(9) We note in the following s* E S the unique minimiser of the problem in Equation From this sequence of slopes s", the unique minimising function of Equation (4) can be recovered. Moreover, s* minimises the dynamic program given by the functions o as follows:
millses Σ (141(8i4,
c++1(s141) ( (51+1,)7) + (s()) for any i E [80 - 2]
(3 (1:1 st) + c4+1($)+1 for any i E (io....,
1}.
Using simple properties of the functions e; given by Lemma in Appendix properties s* can be derived besides the uniqueness of the minimal norm interpolator. Lemma 3 below gives first intuitive property of this minimiser, which proves helpful in showing the main result of the section.
Lemma 3. For any i [n], s [minn(;-11.5) max (6, 6;)], where dg == 82 and 8n == 6n-1 by convention.
geometric interpretation of Lemma is that the optimal (left or right) slope in x; is between the line joining (0--1,9-1) with (z,, v:) and the line joining (I; ys) with (I++1, B1+1).
5.1 Recovering sparsest interpolator
We now aim characterising when the minimiser of Equation 4 is among the set of sparsest interpolators, in terms of number of kinks. Before describing the minimal number of kinks required
7

---

to fit the data in Lemma we partition [I) into intervals of the form [Inz Pme+1) where
and for any k 2 0 such that n <
1 min {j E (ng + ,..... 1} sign(ó; 6--1) + sign( 8)-2)) (n),
(10)
and sign(0) = 0 by convention. If we note fia the canonical piecewise linear interpolator, it is either convex, concave or affine on every interval 1,, Fn.-1) This partitioning thus splits the space into convex, concave and afine parts of flin, illustrated by Figure 2 on toy example. This partition is
crucial in describing the sparsest interpolators, thanks Lemma
fia
oonvex
DOBVEX
laffine
joobcave
12ng
Figure 2: Partition given by (mg)a on toy example.
Lemma 4. we denote by lo the cardinality of the support of the measure f",
min
11
Tk++1
7hk
18 186
2
#21
Lemma 4 proof idea is that for any interval [x Th+1) where fin is convex (resp. concave) non affine, any function requires at least one positive (resp. negative) kink to fit the three data points in this interval. The result then comes from counting the number of such disjoint intervals and showing that a specific interpolator exactly reaches this number.
The minimal number of kinks required to interpolate the data is given by Lemma 4 Before giving the main result of this section, we introduce the following assumption on the data (Tk Me Me)ke(n)
Assumption 1. For the sequence (nx)) defined in Equation (10
T&++1 Thg < 3 or 8 8mg-1 for any k 2 0.
Assumption D exxctll means there are no (or more) consecutive points Tk. Tk+5 such that füin is convex (without 3 aligned points) or concave on [x+5) This assumption depends lot on the structure of the true model function (if there is any). For example, it holds if the truth is given by piecewise linear function, while it may not if the truth is given by quadratic function. Theorem 3 below shows that under Assumption the minimal cost interpolator is amongst the sparsest interpolators, in number of its kinks.
Theorem 3. If Asssmpttoo 7 Tholds, then
argmin IIv1+ x3 f argmin l|
(11)
(.((=))
vi.((.))=..
Theorem states conditions under which the interpolating function f with the smallest representa- tional cost R₁ (f) also has the minimal number of kinks, i.c. ReLU hidden neurons, among the set of interpolators. It illustrates how norm regularisation, and in particular adding the biases' norm to the weight decay, favors estimators with a small number of neurons. While training neural networks with norm regularisation, the final estimator towards a few key directions. As a consequence, the obtained estimator is actually equivalent to a small width network, meaning they have the same output for every input R.
actually have many non-zero neurons, but they all align
Recall that such a sparsity does not hold when the bias terms are not regularised. More precisely, some sparsest interpolators have minimal representational cost in that case, but there are also minimal cost interpolators with an arbitrarily large (even infinite) number of kinks (Debarre et al. 2022). There is thus particular reason that the obtained estimator is sparse when minimising

---

the representational cost without penalising the bias terms. Section 6 empirically illustrates this difference of sparsity in the recovered estimators, depending on whether or not the bias parameters are penalised in the norm regularisation.
The generalisation benefit of this sparsity remains unclear. Indeed, generalisation bounds in the literature often rely on the parameters' norm rather than the network width (i.e.. sparsity level). The relation between sparsest and min norm interpolators is important to understand in the particular context of implicit regularisation. In particular, while Boursier et al. [022] conjectured that the implicit bias for regression problem was towards min norm interpolators, Chistikov al. [2023] recently proved that the implicit bias could sometimes instead lead to sparsest interpolators. Our result suggests that both min norm and sparsest interpolators often coincide, which could explain the prior belief of convergence towards min norm interpolators. Yet. Theorem and Chistikov et al.)
[2023] instead suggest that, at least in some situations, implicit bias favors sparsest interpolators, yielding different estimators
Remark 3. Theorem 3 states that sparse recovery, given by Equation 411 occurs if Assumption 7 holds. When nx+1 n2 2 4, i.e. there are convex regions of fuaa with at least 6 points, Appendix A gives a counterexample where Equation [1] does not hold. However, Equation (11) can still hold under weaker data assumptions than Assumption ! In particular, Appendix A gives necessary and sufficient condition for sparse recovery when there are convex regions with exactly 6 points. When we
allow for convex regions with at least" 7 points, it however becomes much harder to derive conditions where sparse recovery still occurs.
Remark 4. The counterexample presented in Appendix A reveals an unexpected outcome: minimal representational cost interpolators may not necessarily belong to the sparest interpolators. This finding is closely related to the idea that it may not be generally feasible feasibbl to characterize the implicit regularisation of gradient descent as minimising parameters norm (Vardi and Shamir 2021 Chistikov et al. 20233. In particular, Vardi and Shamir (202Ty, [histikoov et al. (2..3) rely on examples where minimal norm interpolators are not the sparsest ones; and the implicit regularisation instead favors the latter. We believe that this inherent limitation is one of the underlying reason for the different implicit regularization effects observed in other settings such as matrix factorizution (Gunasekar
el al. 2017 Razin and Cohen 2020
Li et al. 2020a
5.2 Application to classification
In the binary classification setting, max-margin classifiers, defined as the minimiser of the problem min R(f) such that Vi E (: 2 1,
(12)
are known to be the estimators of interest. Indeed, gradient descent on the cross entropy loss 1(g.v) log(1 [1 11++ by) converges in direction to such estimators [Lyu and Li 2019 Chizat and
Bach, 2020]. Theorem 3 can be used to characterise max- margin classifiers, leading to Corollary
Corollary 1.
argmin (i) C
argmin
||
Theorem 3 yields that the max-margin classifier is among the sparsest margin classifiers, when a free skip connection is allowed. We believe that the left minimisation problem admits unique solution. However, uniqueness cannot be directly derived from Theorem 3 but would instead require another thorough analysis, using an adapted dynamic programming reformulation. Since the uniqueness property is of minor interest, we here prefer to focus on a direct corollary of Theorem 3 We emphasise that no data assumptions are required for classification tasks, apart from being univariate.
6 Experiments
This section compares, through Figure 3 the estimators that are obtained with and without counting the bias terms in the regularisation, when training a one-hidden ReLU layer neural network. The code is made available at cot.
biases
'Note that this nuance only holds for regression tasks. Instead, it is known that implicit regularisation favors min norm interpolators in classification tasks [Chizat and Bach 2020). which always coincide with sparsest interpolators in that case (see Corollary I in Section 5.2) for univariate data.

---

For this experiment, we train neural networks by minimising the empirical loss, regularised with the lg norm of the parameters (either with or without the bias terms) with a regularisation factor À 10-3. 3. Each neural network has mn 200 hidden neurons and all parameters are initialised i.i.d. as centered Gaussian variables of variance 1/vm (similar results are observed for larger initialisation scales) There is no free skip connection here, which illustrates its benignity: the results that are expected by the above theory also happen without free skip connection. Experiments with a free skip connection are given in Appendix and yield similar observations.
05
00
0.5
164
0.5
[a(rr
0..1
0.2
040
-0.
005
-1.0
-12
022
-01
-1.
-15
-252
(b) Ignoring the bias terms in the &a regularisation. Figure 3: Final estimator when training one-hidden layer network with &g regularisation. The green dots correspond to the data and the green line is the estimated function. Each blue star represents a hidden neuron (wy, b,) of the network: its r-axis value is given by bby/wy, which coincides with the position of the kink of its associated ReLU; its y-axis value given by the output weight aj.
(a) Penalising bias terms the Eg regularisation.
As predicted by our theoretical study, penalising the bias terms in the bg regularisation enforces the sparsity of the final estimator. The estimator of Figure BaleeBaainnd Balindeed counts 2 kinks (the smallest number required to fit the data), while in Figure 3b the directions the estimator is almost smooth near = 0.5,, while the sparse estimator of Figure Ga clearly not differentiable this point. Also, the estimator of Figure Bbb includes a clear additional kink x Figure 3 thus illustrates that counting the bias terms in regularisation can lead to sparser estimators.
the neurons are scattered. More precisely,
7 Conclusion
This work studies the importance of parameters' norm for one hidden ReLU layer neural networks in the univariate case. In particular, the parameters' norm required to represent a function is given by ||vI+ 2² d"Il when allowing for a free skip connection. In comparison to weight decay, which omits the bias parameters in the norm, an additional vI+ weighting term appears in the representational cost. This weighting of crucial importance since implies uniqueness of the minimal norm interpolator. Moreover, it favors sparsity of this interpolator in number of kinks. Minimising the parameters' norm (with the biases), which can be either obtained by explicit or implicit regularisation when training neural networks, thus leads to sparse interpolators. We believe this sparsity a reason for the good generalisation properties of neural networks observed in practice.
Although these results provide some understanding of minimal norm interpolators, extending them to more general and difficult settings remains open. Even if the representational cost might be described in the multivariate case [as done by Ongie et al. [2019] without bias penalisation), characterising minimal norm interpolators seems very challenging in that case. Characterising minimal norm interpolators, with no free skip connection, also presents major challenge for future work.
For small initialisations, both methods yield sparse estimators, since implicit regularisation of the bias terms significant that case. Our goal only to illustrate the differences the minimisers of the two problems (with and without bias penalisation). without any optimisation consideration.
10

---

Acknowledgments and Disclosure of Funding
The authors thank Gal Vardi, for suggesting the proof of Corollary [ through a direct use of Theorem 3 The authors also thank Claire Boyer, Julien Fageot and Loucas Pillaud-Vive for very helpful discussions and feedback.
References
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681, 2017.
Andrew R Barron. Universal approximation bounds for superpositions of sigmoidal function. IEEE Transactions on Information theory, 39(3):30-994, 1993.
Peter Bartlett. For valid generalization the size of the weights is more important than the size of the network. Advances neural information processing systems, 9, 1996.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learnin practice and the classical varinnae trade-off. Proceedings of the National Academy of Sciences, 116(32)11884--1583 2019.
Yoshua Bengio, Nicolas Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. Advances in neural information processing systems, 18, 2005.
Etienne Boursier, Loucas Pillaud-Vivee Vivien, and Nicolas Flammarion. Gradient flow dynamics of shallow relu networks for square loss and orthogonal inputs. arXiv preprint arXiv:2206.00933 2022.
Emmanuel Candès and Carlos Bernandez-Grande Towards mathematical theory of super- resolution. Communications on pure and applied Mathematics, 67(())906 -966, 2014.
Scott Shaobing Chen, David I. Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM review, 43(1):129-159) 2001.
Dmitry Chistikov, Matthias Englert, and Ranko Lazic. Learning a neuron by shallow relu network: Dynamics and implicit bias for correlated inputs. arXiv preprint arXiv:2306.06479 2023.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on Learning Theory. pages 1305-1338. PMLR, 2020.
Thomas Debarre, Quentin Denoyelle, Michael Unser, and Julien Fageot. Sparsest piecewise- regression of one-dimensional data. Journal of Computational and Applied Mathematics, 406: 114044, 2022.
Weinan E and Stephan Wojtowytsch. Representation formulas and pointwise properties for barron functions, 2021.
Carlos Gamandez--raadaa Super-resolution of point sources via convex programming. Information and Inference: A Journal of the IMA, 5(3):251-303, 2016.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville, Deep Learning, MIT Press, 2016. http:
7/www www.deeepearniigbook..k org
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Ziwei and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Conference Learning Theory, pages 1772-1798. PMLR, 2019.

---

Anders Krogh and John Hertz. A simple weight decay can improve generalization. Advances in neural information processing systems, 4, 1991.
Vera Kurková and Marcello Sanguineti. Bounds on rates of variable- basis and approximation. IEEE Transactions on Information Theory, 47(()) 2001.
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. arXiv preprint arXiv:2012.09839 2020a.
Zhong Li, Chao Ma, and Lei Wu. Complexity measures for neural networks with general activation
functions using path-baset norms. arXiv preprint arXiv:2009.06112. 2020b.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2019.
Mor Shpigel Nacson, Kavya Ravichandran, Nathan Srebro, and Daniel Soudry. Implicit bias of the step size in linear diagonal neural networks. In International Conference Machine Learning, pages 16270-16295 PMLR, 2022.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint 141iv:1412.6611 2014.
Andrew Ng. Sparse autoencoder. CS294A Lecture notes, 72(2011):1-19) 2011.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. In International Conference on Learning Representations (ICLR 2020), 2019.
Rahul Parhi and Robert Nowak. Banach space representer theorems for neural networks and ridge splines. Journal of Machine Learning Research, 22(43):1-40) 2021.
Rahul Parhi and Robert D) Nowak. Deep learning meets sparse regularization: A signal processing perspective. arXiv preprint 23x 2023.
Clarice Poon, Nicolas Keriven, and Gabriel Peyré. Support localization and the fisher metric for off-the-grid sparse regularization. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1341-1350. PMLR, 2019.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms. Advances in neural information processing systems,
2020.
Itay Safran, Gal Vardi, and Jason D Lee. On the effective number of linear regions in shallow univariate relu networks: Convergence guarantees and implicit bias. Advances in Neural Information Processing Systems, 35:32667-32677 2022.
Clayton Sanford, Navid Ardeshir, and Daniel Hsu. Intrinsic dimensionality and generalization properties of the R-norm inductive bias. arXiv preprint arXiv:2206.05317. 2022.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667-2690. PMLR, 2019.
Alexander Shevchenko, Vyacheslav Kungurtsev, and Marco Mondelli. Mean-field analysis of piecewise linear solutions for wide relu networks. The Journal of Machine Learning Research, 23 (1):5660-5714 2022.
Daniel Soudry. Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Lawrence Stewart, Francis Bach, Quentin Berthet, and Jean-Philippe Vert. Regression classification: Influence of task formulation on neural network features. arXiv preprint arXiv:2211.05666 2022.
Gal Vardi and Ohad Shamir. Implicit regularization relu networks with the square loss. In Conference Learning Theory, pages 4224-423 4258. PMLR, 2021.
12

---

Yifei Wang, Jonathan Lacotte. and Mert Pilanci. The hidden convex optimization landscape of regularized two-layer relu networks: an exact characterization of optimal solutions. In International Conference on Learning Representations, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
13

---

A Discussing Assumption 1
Theorem 3 requires Assumption [ which assumes that there are no convex (or concave) regions of Jiin with least 6 data points. Actually, when there is convex (or concave) region with exactly data points, i.e. 11++11 = B& + 4, Theorem Saneem|]jer hoolds (for this region) if and only if for i - n + 1:
(u4 Wi 1) (1541, Wi+1)
(Us Wi w;-1)
(1++1, w
(us, u.+1) S V ||:|1
|1441 11
10
Wi+1
1
|| 1 1|
(13)
5, 83
8:-1 0i-2
where u; (ri 1);
Wi-1 6, 8;-2
(Eis 1)
0, --ò22
(Ii-11 1);
0(42 di+1
8,-1 - d;
and
Mi+1 (Zi41, 1);
Wi+1 8:-2 8;
(#i44 1)
(1i+1;
0; d;
The proof of this result (omitted here) shows that the problem
min
9c(8;; 1)-1) + 9x+1 (81+1,s; 9i+2 ( 81+1)
minimised for (si, $1+1) (6,. 6,) if and only if Equation 13 holds, which corresponds to the (unique) sparsest way to interpolate the data on this convex region. To show that the minimum
reached at that point, we can first notice that 8,- 6;-2 and 8 = 6,42. Then, it requires meticulous study of the directional derivatives of the (convex but non-differentiable) objective function at the point (ō:, 8.).
Figure 4 below illustrates a case of 6 data points, where the condition of Equation 13 does not hold. Clearly, the minimal norm interpolator differs from the (unique) sparsest interpolator in that case.
min
1.00
spaissed
0.70
0.50
0.25
0.00
-022
0.0
0.5
1.5
25
Figure 4: Case of difference between minimal norm interpolator and sparsest interpolator.
When considering more than points, studying the minimisation problem becomes cumbersome and no simple condition of sparse recovery be derived. When generating random data with large convex regions, e.g. 35 points, the minimal norm interpolator is rarely among the sparsest interpolators. Moreover, it seems that its number of kinks could be arbitrarily close 34, which is the trivial upper bound of the number of kinks given by Lemma 3 while the sparsest interpolators only have 17 kinks.
B Additional experiments
Figure 5 shows the minimiser of Equation (4) on the toy example of Figure 2 The minimising function is computed thanks to the dynamic program given by Lemma Although the variables of this dynamic program are continuous, we can efficiently solve by approximating the constraint space of each slope as discrete grid of [6;-1, thanks to Lemma 3 For the data used in Figure 5 Assumption T holds. is clear that the minimiser is very sparse, counting only 4 kinks. The partition given by Figure 2 then shows that this is indeed the smaller possible number of kinks, thanks to Lemma [ On the other hand, the canonical piecewise linear interpolator fiim counts kinks here.
as sparse and
14

---

Min norm interpolator
5-
3-
22
Figure 5: Minimiser of Equation (4 on toy data example.
F considers Considers the exact same setting as Figure in Section 6 The only difference is that we here allow a free skip connection in the neural network architecture, which represents the setting exactly described by Theorem
1.5
06
300
03-
101
0.2
(0(x))
110
-1.0
-1.
-15
(b) Final estimators when training one-hidden ReLU neural networks with & regularisation and free skip connection.
(a) Final estimator when penalising bias terms in the &a regularisation.
Figure 6: Final estimators when training one-hidden ReLU neural networks with & regularisation. The green dots correspond to the data, while the green line is the estimated function. Fach blue star represents hidden neuron (wy, by) of the network: its r-axis value is given by -by/wz, which coincides with the position of the kink of its associated ReLU; its y-axis value is given by the output layer weight aj.
Similar observations can be made: the obtained estimator when counting the bias terms in regular- isation only has 2 kinks, while the estimator obtained by omitting the biases in the regularisation is much smoother (and thus much less sparse in the number of kinks). The only difference is that the latter estimator here does not have clear kink = 0, but is instead even smoother on the interval [-0.5, Oj. This is explained by the presence of more scattered kinks in this interval. Despite this slight difference, the main observation remains unchanged: the estimator is sparsest one when counting the bias terms, while it counts a lot of kinks (and is even smooth) when omitting the biases.
C Proofs of Section 3
Theorem below extends the characterisation of the representational cost Ra (f) of Theorem Theorem 4. For any functiion f TR TR,
Ri(f) = V1 + x²2" rv - I
and R() 11 1+ x2 p"
+ +Dz,,
TV
15

---

where
( - - | (x](ff (x))
25
Cj { ((z)d xx(xx)df(xx) l =
D( Cf)
inf || 2z1l-
=EC,
For any non funttipiiiit,uuniionn, Rí (f) = R(f) = +00.
Proof. We only prove the equality on R(f) here. The other part of Theorem can be directly deduced from this proof. First assume that R(f) is finite. We can then consider some μt E M((S) such IR f(x) Js a (wx b)du(w, b). Note that f is necessarily Ilipshy-Lipschtzz, which proves the second part of Theorem 4 Without loss of generality, we can parameterise $ on 0 E I n 3n with r-1(()) = (cos 0, sin f). If we note = Ta the pushforward measure of 2
that for any
by T. we then have
f(x) = f
- o(r cos 0 + sin ())
(14)
Since the total variation of and thus is bounded, can derive under the integral sign:
((x) - f 2r
-(x)=
cos cos 020d(())))))))
Now note that cos s-n 0 and only if 0 E |- arctan (x), arctan since 0 E iee.
[--3
3r).
2
T arctan ot
f'(x)
cos 0dv(O).
arctan.
When deriving this expression over x, we finally get for the distribution f" (x) cos (π arctan(z)) dv (π (e)tann(x)) cos (- arctan(<)) dv arctan(z))
1 1 x2 (as((rctan(=)))(d (π arctan(x)) + du d=(- arctan(x)))
1+ x²
This equality is straightforward for continuous distributions v. Extending it to any distribution requires some extra work but can be obtained following the typical definition of distributional derivative.
Defining (0) v(0) u(π 0) for any 0 E [- 2- 7) and noting that cos arrrta vT+
Vr E R, 1 x2 (z) = dv4 (1 arctan(x))
1 1 x²
Or equivalently, for any 0 E (- 2: 7
ds" (- tan 0) cos du+ (0).
(15)
cos 0
Similarly to the proof of Savarese et al. 2019 f" fixes v- and the only degree of freedom is on
(0) = v(0) vIT + f). The proof now determines which valid vi minimises || = ||
Equation 14 implies the following condition on 1i1
1 f co + sin 0)d(u+ -2))(0) 2 a 1z sin O)d(() + +0) + 2
1
f(x)
1
(x: cos 0 + sin 0ld (0) {
Odv (0) / sin 0dv1 (0).
2
While M4 is given by f", Ty holds for affine part of f. The above equality directly leads to the following condition 11
{
[ cos 0 de (0) f+ + fo(
(16)
sin 0 du (0) ((0) 53 sin 0 du (0)
16

---

Now note that 2 1 = 112 + + + ||4 - -Valliv. so that R(f) is given by such that verifies Equation (16).
2R(J) = min 2- + lv + 1|+ lllv
Lemma 5 below then implies
R( || + Cy),
where z and C defined in Theorem 4 Equation [3 leads with simple change of variable when R()) is finite
R(f) V1 f2 of lly D1),,C().
Reciprocally, when ||vI+ 1 [|v is finite, we can define v4 as in Equation 15 and #1 as sum of Diracs in - and verifying Equation (T)). The corresponding μ is then of limite total variation, implying that R(f) is finite. This ends the proof of the first part of Theorem 4
R()) = V1+ x² 1" Ir
+ Df),,Cg)-
For (J),), the analysis is simpler since there is no constraint vi, whose optimal choice is then given by V1 =
Lemma 5. The minimisation program
[ d/v 1Tl
min 21
dlv+ + 1/1 +
(17)
(
n/
n/2
such that
Cos dv dvi(0), (0),
sin 1 dvl =(a,b)
-7/2
is equivalent to
| dlv + 2 min
2
(1(a, b) u/l,
NEC
(18)
{1) cos
L sin(0))(0)de+((0)) |1||l00 [111l=ss] $1).
where C
Proof. For any My in the constraint set of Equation where ||//|00 $ then comes pointwise
we can use a decomposition 11 =p/ 12
|M pal M+ M1l
2 2/u22 [(1 + v))4 + (1+
(19)
2 μ22
|+
As consequence, if note the infimum given by Equation 17
u US 2
dlv
min (P
d/p2l
where
and 1 (cos 0, sin (v(0)de+ dpz(0)) (p))))))) (a, b1}
r= (2))
|1
x/2
Moreover for a fixed V/,, we can choose
(ip, (22) as:
dei 11.
4 = sign de min
dv
1/2 V1 40
dei denotes by abuse of notation the Radon Nikonym derivative des with the Lebesgue where duy decomposition 11 14 + N4 with n4 < V4 and v, v4. For this choice, Equation (19) becomes an equality, which directly implies that
2 min / d/pa).
2
d dlu+I
'A change of variable also necessary observe that the min of Lemma is equal to D C,).
17

---

It now remains to prove that min [1(,b) - -ul2=
min 5 (A.7))r
d/ua)- Fix in the following such
weC
that |/ S 1 and note
x x= a l x/2
|// cos (00)du+ (0),
y y= b- -_ sin 0 (p)))
It now suffices to show that for any fixed yo:
min M22 s.L. (F.
d|p1 [((z,))]]
{ {12 |- (cos 0, sin 0) dpz(() (x, 5) Now define
The constraint is actually
sign(x)y V=² + y²
8"
aresin
and = sign(x)) v x² gg
where 56- is the Dirac distribution located 0". This definition is only valid if x: * 0, otherwise
choose 112 = -6
Note that 2 the constraint set and _ dluz (a v) i.e.
min M2 (9.2))r Now consider any #2 in the constraint set and decompose μs = 15 M2 with (4Σ e M+ 2: .)) Define
d| - (( v)ll
(1 C dp
(x+, =
sin duz
(x-,8-)
cos dj
sin 0 duz
By Cauchy-Schwarz inequality,
ʃ cos (8) duž (0) / dpp (0) 2 x²t,
[ (0)) (0) / /dp 2 2..
Summing these two inequalitics yields
/ dnt 2 V 12 + v..
Similarly, we have
/ d45 2 v x2 + y2.
Recall that dduu2l = f dut ʃ duz. By triangle inequality, this yields:
/
dlpzl 2 [1 + ||(x=1 y-)ll
(x-,ı--) -
-
As consequence:
min
d/p2| 2 [1(x,,))
na st ((.
We finally showed that
( cos ((0)dd=
/ sin ((0)dd())
2/
d p2l
(a.b)
-x/2
S.L. (2T
This leads Lemma 5 when taking the infimum over s.
18

---

D Proof of Section
D.1 Proof of Lemma]
We first need to show the existence of minimum. Using the definition of R1(f) and Theorem | Equation equivalent to inf ||ll| p,a,b
such that for any i [n], f..a.b(z))) ys-
(20)
Consider sequence (1g, dj by) l such that Jys.ag,b, (1x) ys for any and and || ll converges to the infimum of Equation (20). The sequence ||d is necessarily bounded. This also implies that
both (a,) and (by) are bounded 9 Since the space of finite signed measures on & is Banach space, there a subsequence converging weakly towards some (jt, a, b). By weak convergence, (μ, a, b) is in the constraints set of Equation (20) and ||l|Ty = limm || [|uyllyy- (1, b) is thus a minimiser of Equation (20). We thus proved the existence of a minimum for Equation (4). which reached for fu.a.b-
Define for the sake of the proof the activation cones C,
Co {0 R Vi I,.... (0, (z,, 1)) > 0}.
C {0 I=² (0, (1:+1:
(0, (z; 1))} for any I,..., 2,
Ci {0 E IR² (0, (rig 1)) > 0 (0, (ri 11, 1))]
(21)
C. = {0 E R (0, (I:+1. 1)) > 0 2 (0, (Tr, 1)) for any i = io....,
C {e E IR? {0} Vi = l,..., (0, (zx, 1)) S {
As the v; ordered, note that (Co, Ci -i,. Cn-1, C 1, C.,) forms partition of R.2. To prove Lemmal [ it remains to show that any minimiser (Na: b) of Equation (20) has a function Sn.a,b of the form
f,a,(I)) är + b+ Σ
á (z, 1))) where 6, E C..
Let f be minimiser of Equation
Let μz, a, be minimiser of Equation 20) such that fpaa b = f.
Define j., a, b as
du(()) + dp(-0)
for C, for any i ...... for E CC, for any = 1, 1,....
(0)
(d((0)
otherwise,
à a 0ıdp(0),
b= b Σ j=1
O2du(().
Thanks to the identity o(u) == ===o---) fu,,,b
f... Moreover, llällr S || so in U o C. In that case, for any =, 1..., n
assume w.l.o.g. that the support of μ is included
f(x;) = az, + +
(0, (I,, 1))
1=0
az, b+ Σ 0du(0), (z),
(22)
"To see that, we can first consider difference fay by (x1) Sng.ay, (x(2) show that (a,), bounded. This then leads to the boundedness of (b,), when considering fuy.a,, (21). We transform triple (14, a, b), but the corresponding function f remains unchanged.
19

---

First, the reduction
/ 01dp(0)
ā a+ Co
b+ / (2du((0)
Co
J MIUZzi
does not increase the total variation of μ and still interpolates the data. As a consequence, the support of μ is included in Ul=1 Ct. Now let = p+ p- be the Jordan decomposition of μr and define for
any E [n2 1]
04 - / 0dw+ (0) and B, = / 0d)-(00.
Note that a; and 3; are both in the positive convex cone C.. For 0; = as - -Bi, Equation
rewrites
i-1
f(z,) = az; + +
Σ
(0 (z,, 1)).
0, E U-- we can then define
1- MCC, 10,116
14,1
Thanks to Equation
(22 the function fā,., still interpolates the data and
løll $ || - || + ||0:ll.
By minimisation of ||l] this an equality. Moreover as fu is measure on the sphere,
/ Sc. 110ldd+(00 (0) { Jc. [10ldpp(00
|l
2 11/o 0001 + 1/c, odp (0)
= =Ilas|| + || Z |10:1..
By minimisation, all inequalities are equalities. Jensen's 's case of equality implies for the first inequality that both 14+ |C, and μe- |C, are Diracs, while the second inequality implies that either = 0 or 3 0. Overall, Mic; is at most single Dirac
Now if 0g E CC, assume first that (0,, (r.+1, 1)} > This implies (0., (z;, 1)) since
0, E C, U C This then implies that either a; E C, or 3r E C.. depending on whether 2 io or
i < io- Assume first that 84 E C (i 2 in) and define
= sup { [0, 1] l'a; - 3, E -C
By continuity, lo; - B, CC. Moreover / < 1, since 3, E C₁ and 0g & Cc: now define μ MIG, + (1 - 1) لاप
+ |lta; - 8, ca.-2e- [
The function Sūa. still interpolates the data. Similarly the case 0; E C; -C. the minimisation of [|иl| implies that μic, most a single Dirac
If or C₁ instead, similar arguments follow defining
= sup {t' E [o, 1] a a
Symmetric arguments also hold if (0,, (#:+1, 1)) < 0. In any case, MC is at most single Dirac. This holds for any 1..... 1, which finally leads Lemma
D.2 Proof of Lemma
Before proving Lemma let us show a one to one mapping from the parameterisation given by Lemma to parameterisation given by the sequences of slopes in the points I;, Let define the
20

---

sets
8 = (S(.....,))))) ,,) ER" V4 = ,,....io. 2,8, S,(s+11),
(23)
(io E and Vi = i....., 1,41 E Si(s;)
and
I = (a, b, (as, 7))== |Vj = 1,...,,,, azj +b+
Σ
a,(ay - -T,)+ = Mg To--1 E 1,,
1=1
Tz F++1
Ti
if a, =0, Vi [l...., in 2}.r8 Ta E (01,
and Vi .u 11, To [xy Tz41)
The condition 7 + if a; 0 in the definition of I is just avoid redundancy, any arbitrary value of т; would yield the same interpolating function. Lemma below gives one to one mapping between these two sets.
Lemma 6. The function
I I
v (ao: bo. (ai, Ti TT)==I...m-))+ + (Ej=0 aj)i=1_...-11
is a one to one mapping, Its inverse is given by
S +
(8i)iE(M) + (ao, bo (at, Te)Ee(-1))
where
ag 81;
bo
1/1 8131;
a= = 88
for any i E In 1]:
8 8:1
1it1 +
6-51 Is
ifst1 ts
1111-8
Ti
otherwise
Proof. For (ao, bo, (as, T()==I....-1)) 1) E I, let f be the associated interpolator:
f(x) = ag + bn + (a(x--T))
1=1
and let (8:)se(n) = ((a, bo, (a,, T.))). Given the definition of vb. it is straightforward to check that 8; corresponds to the left (resp. right) derivative of f at x; 2 0 (resp. n, < 0). We actually have the two following inequalities linking the parameters (ag. bo, (a,, Ti):) and (s,); for any i [n 1]:
8; + a, = 8++1,
3/4 + 3;(1141 x;)) a1(1:11 Ti) Wi+1-
The first equality comes from the (left right) derivatives of f in 24, while the second equality is due to the interpolation of the data by f. These two equalities imply that an interpolator with ReLU parameters in I (i.e., f) can be equivalently described by its (left or right) derivatives in each æ;- A straightforward computation then allows show that yb and s vb + Is and w
are well defined and indeed verify
Iz.
Using this bijection from I to we can now prove Lemma 2 Note for the remaining of the proof min
Jn /I + x dd (x)). Thanks to Lemma
we have first equivalence:
f(x)m),
min bo. (a) l....... JEZ
|a laly 1
For any (ao, bo, (as, Ti) T1) E I, can define thanks to Lemma (8)) (a bo. (a,, T.). S. We then have (as, bo. (as, Ti).) e ((s))). Morcover, by definition
21

---

of db we can easily check that
|a: y + 7, ot + (aiTs)²
V - 8,)2 + ((8441 0. + (s; dz),0,)
(8++1
(24)
As & is a one to one mapping, we have for any function h the equivalence min h(u) minses (s)) In particular, thanks to Equation (24
n-
min
a
1 T
min (e))
g++1(5(41,8))
(25)
(oo,bo (oo,bb.((ss) (Q:.
JEZ
From there, define for any 2 in.
di(s;)
min
Σ (5 5y);
(8) ES
and for any
(s(s))
min E gs+ (3)+,,,)1)8))) (8)EE
Obviously, we have from Equation (5) and the definition of S that
min Pio (8ig Sig 11) + 1 1) + di (s:a). (s 1 sng JEN
(26)
It now remains to show by induction that for any i that c; d₁. This is obviously the case for i Let us now consider E fio...... 1}. The definition of de leads to
n-
(s,) = min Σ (5+1(()-1188) (SyESS
j=1
min
(1+1( + (8) LL A,
min
Σ
9j (3,+1,,)
8141 (S((s)
j=i-1
841
min (s)
Ie+ (8141, +
min (3)
Σ -5-1 1 (3541,81,))))
(27)
s.t. 8:=8; j=1-
#4+1
Now note that for any 8;+1 E Ss(s),, we have the equality the sets
{())) ($) s.t. 5; = 8; and 6;+1 8+11 (5)))2 (8) E S s.t. 8:41 81+1
Since the last term in Equation 27 only depends on (šz)j28t1, this implies that
ds(s;) = min gi+ gi+1 (5 + st. 8441 1=1+1
min ES)ES
Σ (
(...)
min li+ (8:41, + d (81+1). Sq1ES((s))
By induction, it naturally comes from the definition of that de for any i2 ig. Symmetric arguments hold for any < ig. which finally gives e, = d, for any i [n). Equation (26 then yields Lemma 2
22

---

E Proof of Section 5
The proofs of this section are shown in the case where 21 < and on 2 When all the a are positive, i.e, 21 2 0, the adapted version of Lemma 2
would yield for = 1 the equivalencd !T]
min (=))=;
min Cig (8
Aig AI
The proofs of Appendix can then be easily adapted to this case (and similarly In < 0).
Appendix E.5 at the end of the section more precisely states how to adapt them to this case.
E.1 Proof of Theorem
Before proving Theorem 2 Lemma 7 below provides important properties verified by the functions defined in Equation
Lemma 7. For each E fio...., 1}, the function is convex, V x. Lipschitz on R and minimised for s; 65. Moreover, on both intervals (-o0, 8:] and [6;, +o0):
1. either ci(s;) /1 + z;|s; 8,1 c++1 (6:) for all in the considered interval, or ca is strictly convex on the considered interval;
2. lc,(s:) cx(s1)1
1+00011 st f.r all st, s in the considered interval.
v 1+0744
Similarly, for each E (1,...; iu - 2}. the function C+11 is convex, /1 11+,,,11 and minimised for 8141 64. Moreover, on both intervals (-o0, 8:] and (o;, +20):
x24, Lipschitz on and
1. either (++1(8++1) = v x2 |5+11 - del c(di) for all 8,41 the considered interval, c++1 is strictly convex the considered interval;
2. (++1($ - c+1(65441l
1+2,301 V1+x7
88+1 - s141 for all 8441, 8,41 in the considered
interval.
Proof. For any E (I...., in straightforward calculation give
21 we prove the result by (backward) induction. Since e, 0,
Cn-1(8n-1) V + 2 88-- 8n-1/
which gives the wanted properties for
Now consider (io, ..,, ( 23 such that c+ verifies all the properties in the first part of Lemma We first show the Lipschitz property of e; Let 81, of < 6, first. By inductive assumption, the function 8;41 + (1+1($11,.5) c+41($141) reaches minimum on +oo). Consider $,+1 5ş such that (s.))) = 1 (S si) + 1
Also by minimisation, (s() S g 1 st) + (5+41))1). For the vectors a (I 1) and (x,, 1), it then holds:
c(s))) (s:)) < gi+1 (si+1, 5/) g1+ 1 1
[|(8++1 6:)u (0/- 6z)u|l [|(s++] 8,)u (st 6z)ull
< [[(:: 8/)00= v1 +1++,lss A|]-
The first equality comes from the definition of gi+1 as norm and the second inequality comes from the triangle inequality. By symmetry, showed (c:(s;) cs(s)) I /1
s for s sy 8g.
Note that in that case eı Instead, eı defined through the recursion given Equation 8 Thiss calculation uses the fact that both - and v,, positive, which implies that the minimal in the
detinition of Cr-1 is 5n-1
23

---

Note that if 8; = òū. then 8i+1 = 6g and we show similarly that ci(s)) c((,) - v + zē10; -//-- Moreover,
c((s) -c(6;) = min |1(5/41 - 6,)uu - 6;)uil + (+1(((441) - c++1
of 26:
min 12
[1(s(+1 5.)u (6/- ||( 6,)ull
The first inequality comes from the Lipschitz property of Ge+1- The second from the fact that (s/+1 - 6,)u and (s: 6.)0 are negatively correlated, since z; and 2++1 are both positive. As a consequence, is +1 -iiisccciitz on (-oc, 8:]. Symmetrically, it is also +I+ x1==,-Lipschic on [8, +x), which finally implies is /I + x? Lipschitt on R. Moreover, the last calculation also shows that a; is minimised for 6;-
Let us now show that c; verifies the first point (-o0, By continuity, only have to show it on (-o0, 6.). Let 8, E (-00, 6,). we then have by definition
(s:)) min Ii+1 (S s:) c+1(5441).
#:4126:
If 11 S oū, note that both functions g:+1 (,, s;) and c are increasing [6., +00 thus reached for 81+1 = 6, and
The minimum
css:) = /1 1 - 6:1 + c (6:).
If 6,41 5, both functions (141(,,8;) and c++1 are increasing on 16+41, too). As consequence, we can then rewrite
ca(s:) min Di+ gi+1 84) + c++1(8111)..
(28)
#441E66,60411
Assume first that (8++1) = V x2 18-1 8141l + (+2((6++1 on [8,, 8.42). By triangle inequality, we actually have
9++1 (s141, 2 gi+1 (1+1(0141,85) v 2241 18441 8141/-
This leads for 8 (6,, 8++1] to
9i+1 (8i41, 8;) + ( 2 (1:1 8:) ci+2(0041).
The minimum in Equation (88 thus reached for 8++1 = 6,41, which finally gives for any 8; S (s(s)) = ( st) + c442(6
Since 8/41 o, is easy to check that gi+ (6)+1, is strictly convex on (-oc, 8:) and is c..
Let us now assume the last case, where G+1 is strictly convex on [6, 6,41]- By contradiction, assume that the first point on (-o0, 6,] does not hold. Note in the following h($;41, 8,) 9--1 ($141, s:) (++1(544)) For 8;, sf < 8,, by continuity of h, let 8141, 8441,5441 [6,, de41] be such that
(s.) = 81$+11,8) and c((s) = h(s/411
For any / 1), by convexity of h; (ts; + (1 - t)s()) < h(t((s+11 9:) + (1 - (s1+11. S th(8841, 8:) (1 ()) sf)
= ts;(ss) (1-)t)((ss)
is thus convex on (-x0, 6.). Moreover, the case of equality corresponds to the case of equality for
both gi+1 and c++1:
Gi+1 (1(5+41, s:) + (1 - ()841) 8:)) = (g: (814 st) + +(1 (1- (1-)))+41s0 (1 (8)41)88)
C++1 (181+1 + (1 - ()s(_)) = to 1 + (1 11--)ca 1
The former leads to the colinearity of the vectors (8++1 &, 8: 52) and (8/44 8r, 5z); the
latter gives 8,41 8/41 by strict convexity of C++1. Two cases are then possible
eitherr 8;+1 8 8/41
or s; s/c-
Here again, the fact that z; and ri+1 positive.

---

The former case then implies that (ss)) = -
Since c; (6;) c++1 c++1(6:), Cs
is v + Li-Lschchitz and convex (-o0, 6z], this leads to c²(s) / x 6; c++1 (6;) for any E (-o0, 6.]. This contradicts the assumption that the first point does not hold on (-oo, 6:]. Nec- essarily, have 8; s/c So c; strictly convex (-x,, 6:1. which leads another contradiction: the first point does hold on (-o0, 6z].
Finally, we just showed that in any case, G is either strictly convex or equal to 8; + 11+ 6, on (-oo, 6.]. Symmetric arguments yield the same on [d,, +ox). is thus minimised in d;, V x7- Lipschitz and verifies the first point on both intervals (-o0, 6,] and [o,, +o0). This directly implies that C₁ is convex on E.
now remains to show the second point on the two intervals. Let us show on (- 6.]: on (-o0, 6,) is actually sufficient by continuity. Consider 8; < s < 6; and 8:41 E [8,, +oo) such that e (s:) 9++1 (s 8:) + c++1($(+1).
By definition of C..
(s.) (s 2 (441 8:) gi+1 (8
Straightforward computations yield that the function
(-00 6:] + R+
h2
8 8 Di+1 (8++111+,
is convex and hō:)
1+2,2+1 Thus, 112 < l+rrrit which finally implies VI+02+1
VI+2(+1
ca(s)) - c((ss) 2 h(s;) - h(s))
+ 2,J1+1 (s/ -t).
V + x
The second point is thus verified on (-00, 6,) and on (-o0, 5e] by continuity. Symmetric arguments lead to the same property on [5., +o0).
By induction, this implies the first part of Lemma 7 Symmetric arguments lead the second part of Lemma 7 for S io 2.
We can now prove Theorem 2 Following the proof of Lemma 2 there is unique minimiser of Equation (4) if and only if the following problem admits unique minimiser:
1-1
min #ES
Σ
gi+1 (
(29)
We already know that the minimum is attained thanks to Lemma 1 By construction of the functions
Cr any minimum & of Equation (29) verifies
argmin 9i- (5 + ca(si) for any E (io 2]
(30)
(..41(
-1 ) E argmin Dio (Sio Sig - + Cio 1 (810-1) + Cip (8io)
(31)
81+1 E argmin g get1 (8 8;) + (+41 for any i (.))
now remains to show that all these problems admit unique minimisers. First assume Equation 31 admits different minimisers (Sio-1, 81g) and (1/ ( Note in the following hig-1 (s, s'
Pio (s, s') + (s') + c20 (s). By minimisation and convexity of the three functions Pio Cio fio-1. Cig for any t (0, 1):
h (1(8)) (1(%) Sin))
+ (1 - 1) (5), (kr)) S 1 81.) + t)h 1 16 (6.o)
(32)
= h (8 sin).
(33)
The whole segment joining ( 8ig) and (1/0-118%)) then minimiser. Without loss of gener- ality, we can thus assume that both si, and s/,,-1 are on the same side of 8 (e.g. smaller than dig-) and both 8i, and s/, are the same side of d.
Moreover, Equation (33) implies an equality on gio that leads to the colinearity of the vectors (s6-11 d4p-1, Sio 01o-1) and (5% 8 S d In particular, both S * s and
25

---

8i0 - S/ 1. Moreover, we have equality cases on both -i and Cip implying, thanks to the first
point of Lemmal
1 - Cio -1o / x 110 sio
(34)
(Skg) - Cio (5) / 2. Sip -siol
For u (1i0-1: 1) and (Nio 1), we have by (positive) colinearity of (sto-1 - 010-11, -o0
and (5 - - 0 1/ -1)
1gho (Nigr 810-1) 1) - gio (8%/n= 8// -11 = |1[(8io - 0ig-1)) ) - ( - 010-1))11 - 11(%% - -10-1)u - (5% 01n-1)ull
= 11(8io 5/2)) (8io-1 -
Since Stp * 5% and Sin-1 * 5%
the triangle inequality gives both strict inequalities
IV 1 + x2 8io -81yl + 10
1810-1 - - <
Dip (8ior 8io-1) Dio (6// 8%
V 22 1800
%/10
/1 2 11800-1111111 8/0-11
1|
Igio (8io Sio 8io-1) 91o (5 8 1)1-
Using this with Equation (34). this yields
Gio ( 9ko-1 9%. (5 - # csa (8%0) cio (5(1) + 1 Go 1
This contradicts the fact that ($ sin) and (5% (60)) both minimise Equation (31 Hence, Equation (31) admits a unique minimiser.
Also the minimisation problem
Di+1 (81+1, 82) + CC+1 (8 (1)
min
admits a unique minimiser for any fio...., n- 1}. Indeed, either 6; 6, in which case the constraint set is singleton, or the function 8;+1 + Ms+1 (5:41, 5,) is strictly convex for &, * 6,. A symmetric argument exists for the minimisation problem of Equation (28). It thus concludes the proof of Theorem 2
E.2 Proof of Lemma
Let i {io....., ................................ 1}. Recall that
41 argmin 91+1 8;)) + c++1(86+1).. se1 s(1E)((()))
= n- 1, the objective is obviously minimised for s ôn-1 as both In-1 and zn are positive. Otherwise, assume for example that st 8, Thanks Lemma 7 the objective is decreasing on (-00, min 0(+1)] and Sy(s;) = 16, +oo) which yields that , [min((; 8441),0, 6.] C [min(6, 81+1), max(6;; d(41), The case sf 8, is trivial and similar arguments hold for sf 6,.
Now consider = in - 1. Assume first that 5 > 01--1. then
argmin 9io ( 1 + cso (8to).
Sug <
Thanks to the last point of Lemma 7
+ Tip Vig (Sto - -1/
Cio (st.)
Cio (5%0) ) 2
for any sto < 5/ S 6i
(35)
/ + x2 22
Note that the function
(-00, 6ip + R2+
h:
8 + Dio (s, s
convex and verifies W (6 (6:g-1)
1
Since Fio-1 < < Fig comes
/1+27
+ D/o 11
+ +1igfiot11
S Dio <
1 x²
x3
Thanks to Equation 35 the function Si, + gin (Sin - + cip (8io) thus decreasing on (-oo, min(5 8i ) As above, this implies that 87 [ (8io (io-11 dto); max(5ig-1. 6 The case - = - 1 is trivial and similar arguments hold if - dio-1.
26

---

disjoint such intervals. Thus, f has at We showed 11 E [min(s, (6s, 64+1), max(o;, 65+1)] for any E (fo.....,n Symmetric arguments
hold for i [g 1]. This concludes the proof of Lemma 3
E.3 Proof of Lemma
Let us first prove that any sparsest interpolator f has at least a number of kinks given by the right sum. For that, we actually show that for k 1, on any interval (ung- 11, with 8n * 6ng
has least MR41-ng nng kinks, whose signs are given by sign(ón. -n.- Consider any k 2
2
such that ong- + 6n Assume w.l.ogg. that 8 < Ong. By the definition of Equation (10): > 1 for any j E {nk..... ; 7x+1 - 1}.
Obviously, f must count at least one positive kink on each interval of the form (1 for Note that we can build n -ne
any n S S Rk+1
least
PB11 1hi1-ng ng
positive kinks on (Ine 11,
The intervals of the form (Ing-11 Fny 1) with dny-1 quence, I' has total number of positive kinks at least
< Sny are disjoint by definition. As a conse-
n&+1 nk
1 - <6
2
Similarly, f has total number of negative kinks at least
784
7k
Bug 1 Buy
2
1
which leads to the first part of Lemma
nk++1
18k 2
min
2
1l 18uu 176622
(i.(())))
We now construct an interpolating function that has exactly the desired number of kinks. Note that the problem considered in Lemma is shift invariant (which is the case of Equation (4)). As consequence, we can assume without loss of generality that x 2 0. This simplifies the definition of the following sequence of slopes S::
81
8 if (s1-1 6 or n. for some k 2
and for any E (2,
n).
si & otherwise.
is easy to check that s S. We now consider the function f associated to the sequence of slopes by the mapping of 6 an interval [I kng41) with 8 * 8 By definition, 8n, 1p = -.2-+142p for any p such that nig + S n& - 1 2p < 11411 This implies that has no kink in the interval [In++1+ +on+++2pp.0 Fng -2 2-2p). From there, simple calculation shows that has at most
n6+1 -n2
kinks on [I :nnn1) )). Moreover, as 6,-1 if i f has no kink on intervals
2
Kngg Tnkl1)
when :nz-1 Ong. f is thus an interpolating function with at most
Σ
Bk+1 nk
16 18622
2
A21
kinks, which concludes the proof of Lemma
E,4 Proof of Theorem 3
Let be the minimiser of Equation
B separately shows that has exactly 1 11 1 kinks on each (Inz-1s Fneti). Fix the following 0.
The proof of Theorem
2
"Otherwise, the derivative would be weakly decreasing on the interval, contradicting interpolation.
27

---

Assume first that mnL-1 8ne. Then Lemma along with the definitions of ni and n directly imply that of Ong- for any N........ 1++1 This then implies that the associated interpolator, i.e. f has no kink on (1n4-11
Now assume that - o Ong. Without loss of generality, assume 8 < Ong. By the definition of Equation
6j > 6j-1 for any j E {TK..... n1+1 1}.
Moreover, by definition of nı: we have
either n2
/either nk+11 = 72
and
or 8 S 5nz-2
or 8pats S 8
Since 78411 S. Tig + 3 by Assumption
I Lemma
8
below states that for all the cases, f has exactly
RA+11 kinks on (1n=-1,
2
Symmetric arguments hold if m > 6nc In conclusion, f has exactly n
1 8m Foag
kinks each (iag-1,Fn441) This implies that f has at most
Σ
u&+1 72
I 18ng 1 16
2
kinks in total. This concludes the proof of Theorem 3 thanks Lemma
Lemma 8. For any O. if 8 8Rz then the minimiser of Equation
f has
kink on (Kng Tog .) if = 11k + 1;
2. kink on (In Fm m = n2 2:
3. 2 kinks on (Ing-1 Tna4s) if T1++1 n& + 3.
Lemmaßha written in this non-compact way since its proof shows separately (with similar arguments) the three cases.
Proof. 1) Consider Tk++1 = ni + 1. First assume that Ing 2 0. Lemma 3 implies that s +1 E
18n2+1, 8 and s E [8m--1, ]. In particular, S,, I 8ng- which implies that s
6ng-
Similarly, sh Ong-1, which implies that s = 6 Using the mapping from Lemma 6 both
values st and +1 yield that the associated function f has exactly one kink on (In--1s In)+1), which is located at Tng. Similar arguments hold if Ind < 0.
2) Consider now 71+11 71 + 2.
First assume that Tn < 0. Thanks to Lemma we can show similarly to the case 1) that $1 8m
Now assume that +2 2 Similarly to the case 1), shu+2 = 8ps+1- The minimisation problem of the slopes becomes 1 1 for i ni:
14 = argmin (8, + (6+2(6141.8),
where = Ss(})) if 2:41 2 0, and 5 {641) otherwise. Note that (s, sf) is / oHt1" Lipschitz in its first argument, while 01-2(5111:)) = V1+ 2. 6411.. Moreover, 8h E [6nz-1, 8, As a consequence, either Int+1 2 0 and s = Enz = shz-1 or s = 8
Symmetrically, when reasoning on the points Ene -1, Rne:
either st = -ny-1i
. or (Ing < 0 and 8 = 8n -8 87a+1)-
There are thus two possible cases in the end:
28

---

either (s = = and m1 dn
or (5 = On = +1 and Znz < <0 < Inc+1).
In the case where Inn < straightforward computation then yields smaller cost on the functions gi for the choice of slopes s., - and +1 dn
0 S Iny+1, we also have sn--1 8 and su++2 ing+1. A
As consequence. Sup Sn -1 and s1y11 6n in any case. The mapping of Lemma 6 then yields that has exactly one kink (n which is located in (Ing Tn&+1). Indeed, either have 0 or Tax-1 = 2mg-1i similarly either amg+1 or Tng+1 2na+2.
3) Consider now 74+1 + 3. Similarly to the case 2), we have both
either 52242 8na
(sm++1 Smu+1 8m and F +2 2 0)
Seither 8h dpu-1
and
or (8% = 6n = Shet1 and Fre <0)
When considering all the possible cases, the mapping of Lemma implies that f has exactly two kinks on f3)+3), which are located in [ Fnutel.
E.5 Adapted analysis for the case x1
This section explains how to adapt the analysis of this section to the easier case where all x are positive. Lemma under the exact terms (but its second part is useless) in that case. From there, the proof of Theorem consists in just showing the uniqueness of the minimisation problems for any 5 E S:
min Cio (5io) Sig ER
min 9s+1 ($1+1, 3,) + (++1(1111) for any i {io...., 1}. E
The unique solution of the first problem is 6,p thanks to Lemma while same arguments as in Appendix holloll for the second problem.
For proof of Lemma
3 the exact same arguments as Appendix hold for any 2 io + 1. For
i= io 1, it is obvious that case that sf 8j. leading Lemma
Finally, the proof of Theorem follows the same lines when x1
0.
E.6 Proof of Corollary
Proof of Corollary
7 For classification, the natural partition to define is the following:
such that n4 f1++1 = min (i E {nA + 1,...,n. You * リン} u 11.
nh and for any
(36)
This partition splits data so that for any k; yt has a the same value for i {nu, 76+1 1}. Denote K the number of n& defined in Equation (36), i.c., nk + 1. From there, by simply noting that any margin classifier has at least kink in Engg Inezi for [K 1
min
||5 = 2.
29

---

Similarly to the proof of Lemma consider f minimiser of
we can first show the existence of minimum
Let now
min (02)21
M x2"" TV
(37)
Define the
== [ E 1,, - 1 - 1 12...., K - 1}}.
By continuity of J. we can choose an alternative training set (i;, .i) satisfying: 34 [n 1: Fnel for any E {nk n
f(A)) for any i E S. Then, a direct application of Theorem yields that the minimisation problem
Vi
min
[i+ x
(38)
TV
admits a unique minimiser, that we denote freg. But also note that this unique minimiser is also in
the constraint of Equation (37) thanks Lemma
3
so that
reg
TV
However, since is in the constraint set of Equation 38 we actually have equality, and by unicity of the minimiser of Equation 38)
freg = f.
Moreover, it is easy to check that [ As consequence, Theorem implies that the minimiser Equation (38) is among the sparsest interpolators for the set (iisS) i.e. it exactly counts K 2 kinks. This then implies that [] 2, that
for the data (ă,, y/ Wi)sss with 7 = 2.
argmin Ri(f) C
argmin (f.))1
Il
(39)
Proovin that the sequence (a,, b2) bounded is here more tricky. Either the data is linearly separable, in which case the minimum is or the data not linearly separable. When the data is not linearly separable, then (a,, b,) is necessarily bounded, since (μy a, b;) would behave as a linear classifier for arbitrarily large (aj, b)).
30


Reviews:
[{"review_id": "dSHnqLvzg8", "reviewer": "Reviewer_ZvaF", "summary": "This paper theoretically investigates the effect of regularizing bias parameters’ norm, mostly ignored or omitted in previous analyses, for univariate one hidden layer ReLU networks. It turns out that minimizing $L_2$ norms for both weights and biases corresponds to regularizing a functional norm defined as the total variation of the second derivative of the function modeled by the neural network with a weight of $\\sqrt{1+x^2}$ factor, where the weight factor does not exist when regularizing only the weight norm. The minimal functional norm interpolator can be obtained from a proposed dynamic programming algorithm, and the uniqueness and sparsity properties of the interpolator are discussed.\n\n**Post rebuttal** I have increased my score to 5 from 4. I can appreciate the theoretical contribution, while the practical relevance still seems to be a weakness.", "questions": "In addition to the questions posed in the **Weaknesses** section, I have the following questions:\n- What would be the practical benefit of considering bias regularization? As far as I know, a common practice for applying weight decay in neural network training is only regularizing the weight norm. This method has already shown many empirical successes so far.\n\n**[Minor comments]**\n- How is the ‘activation cone’ defined in line 188?\n- Providing some explanations about deriving (5) would be helpful.\n- **Corollary 1** is corrected in **Appendix E.6**, and I think the corrected version should come to the main text.\n", "limitations": "The limitations of the results are discussed in **Conclusion** and **Appendix A**. For other possible limitations, please refer to the weaknesses and questions above.", "rating": 5, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The paper analyzes the effect of bias norm regularization, which has not been considered much before, showing novel and original results. The effect is not trivial, and the regularization problem is identified as minimizing a functional norm with a weight factor, which leads to interesting uniqueness and sparsity properties of minimum norm interpolators.\n- Proofs are provided for most of the theorems and lemmas in a mathematically sound way. It is especially ingenious to prove the uniqueness and sparsity properties of the minimum norm interpolator by using a dynamic programming algorithm that obtains the interpolator.\n", "weaknesses": "- The benefit of the considered sparsity regarding the number of a function’s kinks is unclear. Why would the number of kinks be important? Can it be used to explain generalization properties in any way? Also, the sparsity in terms of kinks seems quite different from the one considered in usual machine learning contexts, e.g., having zero values for most weights or representations except for a few. Maybe addressing these points and providing some intuitive explanations would be helpful to enforce the claim of the paper.\n- The condition for the minimum norm interpolator to be the sparsest interpolator is quite restrictive according to **Assumption 1**. Moreover, **Appendix A** provides an example of when the sparsest and minimal norm ones are largely different in the number of kinks. These points can lower the significance of the sparsity result.\n- Due to the weight factor of $\\sqrt{1+x^2}$ in evaluating $\\mathcal{F}_1$ norm from bias regularization, the shift invariance property of the norm disappears. Can this have any negative impact on using the function norm to explain the nature of a function? Also, the connection between this weight factor and the sparsity property regarding the number of kinks is not intuitive. Rather, it seems that containing this weight factor would make the location of kinks not far from zero.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the many insightful comments. We now answer the raised concerns. \n\n*Sparsity*\n===\nThe generalization benefit of the considered sparsity remains unclear in the literature. Indeed, generalization bounds rely on the parameters’ norm rather than the network width (ie sparsity level); and understanding the generalization properties of sparsest neural networks remains an ongoing research direction.\n\nHowever the primary objective of our work is not about the generalization of sparse networks but instead to fully characterize the min norm interpolators. These min norm interpolators are of crucial interest and happen to be linked with sparsity.  \n\nThis notion of sparsity is natural, as it corresponds to the minimal width necessary for a network to represent the function. Counting the number of non-zero weights is less relevant in that context, since networks with different weights can represent the same function. For instance in Figure 3a), a network with hundreds of non-zero weights is equivalent to a width 2 network.\n\nSpecifically, our notion of sparsity counts the minimal number of non-zero triplets $(a_j,b_j,w_j)$ required to represent the function. It thus quantifies the best possible level of sparsity *of the weights*. We emphasize that evaluating quantities based on the represented function, rather than the network weights, is more relevant since it is the genuine object of interest. \n\n *Assumption 1*\n===\nFinding that min norm interpolators are not always the sparsest ones came as a surprise to us. We previously held the belief that Theorem 3 would hold without any data condition. It was only after multiple experiments that we discovered the min-norm interpolator's inability to always be the sparsest. We still consider Theorem 3 to be of utmost importance, since it sheds light on unexpected behaviors, which were not initially apparent.\n\n  Furthermore, this discrepancy between min norm and sparsest is crucial in (Chistikov et al. 2023). The authors present a multidimensional example where the min norm interpolator is not the sparsest. On this example, the implicit bias of gradient flow does not favor the min norm interpolator, but instead leads to the sparsest one, contradicting some previously held beliefs. These findings are closely related to the works referenced by Rev. 3DUe, which also argue that the implicit bias does not consistently favor min norm interpolators. The ongoing exploration of these phenomena constitutes an intriguing and open research direction: perhaps the implicit bias is better captured by “sparsest interpolators” and instances where “sparsest $\\neq$ min norm” correspond to scenarios where the implicit bias does not lead to min norm interpolators.\n\n In summary, the intricate relationships between sparsest, min-norm interpolators and implicit bias are far from being fully comprehended. We believe that our work contributes to advancing their understanding.  \n\nNote however that for (binary) classification, Corollary 1 *always*  yields sparsest margin = min norm margin, which also aligns with the implicit bias.   \n\n*Shift invariance*\n===\nWhen counting the bias terms, the considered norm is indeed no longer shift invariant, which complexifies the analysis techniques. However, preserving strict shift invariance may not be crucial in practical applications, since centering the data is a common practice. Interestingly, Nacson et al. (2022) show that dealing with uncentered data might be beneficial for learning relevant features. The lack of shift invariance in this context can lead to improved performance, thanks to better feature learning. \n\n*Intuition on $\\sqrt{1+x^2}$ weighting*\n===\nThe initial intuition might indeed suggest that having kinks as close as possible to zero would be the best strategy. However, upon closer examination, such an approach results in larger amplitudes for subsequent kinks.\n\n Finding the right balance is not as straightforward: kinks near zero are favored by the direct cost component, while it also affects the amplitude of the next kink(s). This balance is highlighted by the dynamic program: $g$ takes into account the direct cost, encouraging kinks near zero, while $c$ reflects the influence of choosing the current kink on the next one, favoring smaller amplitudes in subsequent kinks.\n\n*Practical regularization of bias*\n===\nThere is limited investigation in the literature on the distinction between counting and non-counting bias terms. Our study is mainly theoretical and does not assert the superiority of any specific rule in practice. We believe that in practice, both schemes yield similar results, because of the presence of additional implicit regularization.  Omitting the bias terms might then be preferred as it reduces computation time. Also, omitting biases might be preferred for optimization reasons (see footnote 1), which is not the focus of our work.  \n\nThe influence of our work is mostly theoretical, as substantial theoretical distinctions may arise between the considered interpolators. This difference is due to a large gap between the worst-case min norm interpolator (omitting bias) and the unique min norm interpolator (counting bias). \n\nNevertheless in practical applications and owing to the implicit bias, the estimator obtained omitting bias does not represent the worst-case scenario but instead approximates the unique min norm interpolator (counting bias).\n\n   *Minor comments:*\n===\n* In 1D, the activation cones are defined line 521\n* The idea to derive Eq (5) is by first using Lemma 1. From then, the minimal cost for connecting $(x_{i+1}, y_{i+1})$ with $(x_i, y_i)$ is done by using a single kink in between. The conditions on $s_i$ and $s_{i+1}$ then yield a unique possible kink. Minimizing its neuron norm then yields Eq (5)  \n* We spotted an error in Corollary 1 after the main deadline and were only able to correct it in the supplementary material. It will of course be corrected in the revised version.   "}, {"review_id": "SflvoA3lhp", "reviewer": "Reviewer_fxbg", "summary": "The paper addresses two main questions: (1) Can the parameters' norm be understood in terms of a quantity that is more insightful from a functional analysis point of view? (2) What kind of functions are learned when minimizing the empirical loss, either with an explicit or implicit regularization of the parameters' norm? The paper provides an answer to these questions for univariate functions when the bias parameters are regularized. It shows that penalizing the bias terms enforces sparsity and uniqueness of the estimated function, which does not hold without penalization of the biases. The paper provides a theorem (see Theorem 1) that states the representational cost of a function is given by the total variation of its second derivative, weighted by an sqrt(1 + x^2) factor. This weighting does favor sparse estimators when training neural networks. ", "questions": "1. I wonder if there is anything special to the weight sqrt(1 + x^2) from a higher level and how particular this result is to the setup considered in the paper, e.g., Relu, Skip connection, 1D setup, and one hidden neural network. \n\n2. The definition of the parameter norm is the squared $\\ell_2$ norm of all the {a_j}, {b_j}, and {w_j}. While in 1D, we can consider them as 3 different vectors, but in higher dimensions, I am not sure about viewing them as vectors is the correct way of defining the parameter norm. Also, when it comes to sparsity, one would compute the number of its nonzero elements, an alternative of which is the \\ell_1 norm. Using the squared $\\ell_2$ norm as a sparsity measure is an uncommon choice since a neural network can be non-sparse at all but with a very small parameter squared $\\ell_2$ norm.\n\n3. It is not immediately clear from the paper what type of function f being considered in the main result. It was said that the second derivative of f, i.e., f'' should be understood in terms of distribution, which I assume that non-smooth 1D functions are considered. Based on the 2nd definition of \\bar{R}_1(f), f is restricted to those represented by a simple Relu NN.\n\n4. It is written that the two \\bar{R}_1(f) in Section 2.1 can be proven to be the same. Can the authors provide proof or pointing some references to it?", "limitations": "There are some comments on the future directions of this work in the conclusion, but I am not sure they are classified as limitations of this work.\n\nHere is the main limitation in my perspective of the paper:\n\n1. The analysis is restricted to a 1D setting with a very particular structure for the neural network. The weight sqrt(1 + x^2) is too particular, and I am not confident that one can return the same result with a slight change in the problem setup.\n\n2. The implication of minimizing the TV norm of sqrt(1 + x^2) f''(x) is not well understood, and its link to sparsity promoting is not so clear.\n\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- It is well-known that omitting the bias parameters of the NN makes the analysis easier. So, the fact that the bias terms are included is highly welcomed. There are interesting conclusions garnished from including the bias terms, such as the enforcement of sparsity. \n\n- The paper shows that the representational cost of a function is given by the total variation of its second derivative, weighted by an sqrt(1 + x^2) factor. \n\n", "weaknesses": "- The work is only for univariate functions, mainly for ReLU NNs with skip connections, penalization terms (that are not common in practice), and continuous dynamics for training. Therefore, the theoretical study here may say very little about the answers to the manuscript's two main questions for practical NNs.  However, I acknowledge that it may be extremely hard to do analysis when the setup is modified and the authors provide empirical evidence. \n\n- A skip connection is a useful architecture to make the analysis easier; however, whether it says anything about the NNs that are used in practice is unclear to me. The author says: \"Since a skip connection can be represented by two ReLU neurons, it is commonly believed that considering a free skip connection does not alter the nature of the obtained results.\"; however, I am not aware of a theoretical statement that makes it precise in this setting.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the many insightful comments. We now answer the raised concerns. \n\n*Restricting setting*\n===\nAs you rightly highlighted, analyzing any of these potential extensions is undoubtedly much more challenging. When conducting theoretical studies on neural networks, it is often difficult to fully grasp the complexities and general configurations encountered in practical applications. Consequently, we tend to concentrate on simpler settings where we can accurately describe and quantify already non-trivial phenomena.\n\nAdditionally, it is worth noting that the settings we have considered, such as shallow networks, skip connections and univariate setups are commonly encountered in the literature. These simplifications serve as valuable starting points for delving into the underlying principles and behaviors of neural networks.\n\n*Skip connection*\n===\nWe emphasize that skip connections are used in numerous state-of-the-art architectures. They were first popularized in ResNet models, which have maintained their competitiveness over time. Presently, many of the top-performing models are based on transformers, and these architectures also incorporate skip connections. \n\nFurthermore, a skip connection corresponds to a linear function $x\\mapsto ax +b$. Its equivalence with two ReLUs can be directly derived using the following identity: $ ax+b = \\sigma(ax+b) - \\sigma(-ax-b).$ \n\nAs a consequence, we believe that adding/removing a free skip connection does not impact much the sparsity (in the number of kinks) of the network, as a skip connection can be represented by only two neurons. This observation is confirmed by the experiments of Figure 3, as they were done without free skip connection. \n\n*Specific to the setup*\n===\nAs most of the literature, the results are indeed specific to the ReLU activation and single hidden layer architecture. The positive homogeneity property of ReLU activation is essential in deriving the equation provided after line 101. A single hidden layer on the other hand allows to give a nice separation in the neurons interactions (i.e; the output weight $a_j$ only interacts with the weights $w_j,b_j$).\n\nWhen either the homogeneity property is absent or the network has more layers, the correspondence between finite width networks and infinite width representations remains unknown. \n\nOn the other hand, there is hope that our results (or similar ones) may hold  beyond the 1D setup and skip connection. Nonetheless, the extensions proves to be challenging, as you already pointed out. \n\n*About the $\\sqrt{1+x^2}$ weight*\n===\nIt actually corresponds to the norm of the vector $(x,1)$. In the implicit bias literature, a common parameterization involves using lifted data $\\tilde{x}=(x,1)$ to account for the bias weights. This term thus accounts for the norm of the lifted data point. The origin of the $\\sqrt(1+x^2)$ term may appear puzzling, but is better understood when considering the representational cost of a single (or multiple) neuron(s) network. \n\nConsider the network $f(x)=a\\sigma(wx+b)$. A simple computation yields $f’’=aw \\delta_{\\frac{-b}{w}}$, were $\\delta_{x}$ is Dirac distribution located at $x$. Computing $||\\sqrt{1+x^2}f’'||$ then yields \n$||\\sqrt{1+x^2}f’’||=|a|\\sqrt{w^2+b^2},$  which also turns out to be the minimal representation cost of $f$ (e.g. using equation after line 101).\n\n*The $\\sqrt{1+x^2}$ weight is too particular*\n===\nWe note this weight is not chosen on purpose, but results from the setting. As explained above, the problem setup is indeed restricted to enable a manageable and tractable analysis. At present, we do not have a clear approach for tackling more challenging settings.\n\n*Sparsity measure*\n===\nThe $\\ell_2$ norm of the parameters is closely linked to sparsity in neural networks, owing to the $2$-homogeneity of the parameterization. This homogeneity allows the reformulation as an $\\ell_1$ norm of the output layer (see equation after line 101), which then draws parallels to the conventional Lasso estimator in linear regression.\n\n For a more comprehensive understanding of our concept of functional sparsity, defined as the number of kinks of the represented function, we recommend referring to our response to Reviewer ZvaF, where we provide further details. \n\nFinally, in cases involving multiple dimensions, the literature typically views the weights $w$ as a $d\\times m$ matrix, extending the analysis to higher-dimensional scenarios. \n\n*Considered function space*\n===\nThe paper considers *any* type of univariate function $f:\\mathbb{R}\\to\\mathbb{R}$. More precisely, Theorem 1 specifies that the equality only holds for Lipschitz functions (otherwise $\\bar{R}_1(f)$ is infinite).  As explained in the introduction, the second definition of $\\bar{R}_1(f)$ is for functions that can be represented as *infinite width* neural networks ($\\mu$ is a signed measure). This set is much larger than functions represented by a simple (finite) ReLU neural network. However, this definition is even more general and remains valid for any function: when a function cannot be represented by an infinite neural network, the infimum is taken over the empty set, resulting in $\\bar{R}_1(f)=+\\infty$. \n\n*Equality of the two $\\bar{R}_1(f)$*\n===\nAll results presented in Section 2, including this one, follow the same lines as the preliminary results from Savarese et al. (2019), Ongie et al. (2019). There are only minimal adjustments required to account for the norm of the bias terms, with no additional complexity introduced. \n\nOur work precisely aims to improve the understanding of the link between minimizing the TV norm and sparsity promoting, which is currently not well-established. In particular, we derive conditions under which the min TV norm interpolator corresponds to a sparsest interpolator. We also show that without such conditions, the min TV norm one might not be among the sparsest interpolators."}, {"review_id": "YHRgeqzaV9", "reviewer": "Reviewer_brcW", "summary": "This paper studies the representational cost of a toy ReLU MLP with a single hidden layer, and a scalar input. The main result of the paper is that, when regularizing both the weights and the biases, the minimum cost functions are min norm interpolators which are also sparse (defined in the paper as having the minimal number of kinks). When the bias is not regularized (as in the standard weight decay), the minimum cost functions are not necessarily sparse.", "questions": "Although the sparsest interpolator is not the only solution when the bias is not regularized, we do see (figure 3b) that standard weight decay does produce sparse (almost sparsest) interpolators. Is it possible that in practice the effect of regularizing the bias is not that pronounced? ", "limitations": "Limitations are adequately addressed ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Overall i enjoyed reading this paper. Its main strengths are:\n1. Very well written, and positioned relative to prior work.\n2. A rigorous, clean result, albeit on a very toyish model\n2. A novel result that is somewhat surprising and non-trivial. ", "weaknesses": "The main drawbacks of the paper are:\n1. The studied model is very simple, even for a theory paper (1D input)\n2. Its not clear whether the main conclusion of the paper has any bearing in practice. Therefore, its impact might be restricted to the theoretically inclined.\n\nThese drawbacks are somewhat nitpicky though, and i do not see a reason not to accept it.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. We now answer the raised concerns.\n\n\n  We agree with the weaknesses pointed out by the reviewer. As discussed in the paper, we indeed consider a simplified setting (1d, skip connection, etc.) as it allows for a tractable analysis. Studying a more general setting would be much harder, as pointed out by Reviewer fxbg and we believe that we lack the necessary  understanding and tools at the moment.  We also agree that the main interest of this work is theoretical. In particular, we believe it contributes to the understanding of implicit bias, min norm interpolators and their generalization properties. Actually, our work has already proven useful to show some catastrophic overfitting behavior of min norm interpolator in the presence of noise in the very recent paper [1].\n\n*Practical effect of regularizing the bias*\n===\nThe empirical effect of regularizing the bias indeed seems subtle in practice. We believe that this subtlety arises due to the influence of the implicit bias of the optimization algorithm which still regularizes the bias weights. Indeed, given the nature of the optimization updates, the implicit bias treats the bias weights exactly as the other weights. It is precisely because the implicit bias accounts for the bias term that we believe the true interpolator of interest does count the biases.  The primary objective of this work is thus to gain a deeper understanding and provide characterization of this particular interpolator, primarily from a theoretical standpoint. \n\n——————————————\n\n References.\n[1] Joshi, N., Vardi, G., & Srebro, N. (2023). Noisy Interpolation Learning with Shallow Univariate ReLU Networks."}, {"review_id": "oAcgd2y55M", "reviewer": "Reviewer_3DUe", "summary": "This work considers a single hidden layer ReLU network $f_\\theta: \\mathbb{R} \\rightarrow \\mathbb{R}$ with biases in the hidden layer as well as skip connections. In this context the representational cost $R(f)$ required to interpolate a function $f: \\mathbb{R} \\rightarrow \\mathbb{R}$ is studied, which is defined as the infinimum of the 2-norm of the network parameters such that $f_\\theta = f$. Following prior work and in order to consider the larger space of functions that can be approximated to an arbitrary degree by such finite width networks, (potentially) infinite width networks can be parameterized by a measure on the unit sphere, allowing the representation cost to be recast as the total variation of this measure such that $f_\\mu = f$. Unlike prior work, the the bias terms of the hidden layer are included in the norm penalty. As a result of this, for a univariate Lipschitz function $f$ the representation cost is the total variation of $\\sqrt{1-x^2}f''$ instead of just $f''$ when the bias terms are not included. Given a training sample $(x_i, y_i)_{i=1}^n$ the minimum-norm (with respect to the the total variation of $\\sqrt{1-x^2}f''$) of interpolators $f$ such that $f(x_i) = y_i$ are studied. In Theorem 2 it is shown that the minimum-norm interpolator in this context is unique, which is not necessarily the case when the bias terms are not included. Furthermore, assuming the data is such that the linear interpolation between any consecutive set of 6 points is neither convex or concave, then in Theorem 3 it is shown that the minimum norm interpolator has a minimal number of kinks.", "questions": "1. Does one observe learning a smoother function, i.e., one with less kinks or bumps experimentally when the bias term is included versus not included and how does this vary with say the regularization parameter as well as the smoothness of the target function?\n\n2. If one considers deeper networks or multivariate inputs or a different loss function etc. is there still evidence of a tendency towards learning a function with fewer bumps when bias terms are included in the penalty?\n\n3. Empirically simulating across a number of trials what is the distribution of the learned function look like? Does it concentrate around the minimum norm interpolator?\n\n3. In general how sensitive are the findings of this work to say to changes in network architecture (e.g., different activation function), moving to higher dimensional inputs, changing the loss function from squared error to cross-entropy say?\n", "limitations": "A brief discussion of limitations is provided in the conclusion avenues for future work are identified. I cannot foresee any negative societal outcomes from this work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This work builds on prior work by studying the impact of including the bias parameters in the 2-norm parameter regularization term. In particular, the min-norm interpolator in this context is unique and the results also suggest including the bias terms perhaps encourages the network towards finding sparser network solutions in terms of the number of kinks or bumps. The work appears technically sound however I did not thoroughly read the appendices. The paper is also well written and structured. The contribution appears tangible if somewhat incremental.", "weaknesses": "1. One of the key findings over prior works is that regularizing the bias terms encourages a simpler interpolating function with only a few kinks. However, this relationship is only proved in a restrictive data setting where the linear interpolation between a small number of consecutive points is neither convex or concave. This feels like quite a restriction, furthermore, from the discussion lines 427-432 of the supplementary material, it seems at least experimentally that when the data does contain convex or concave regions then the minimum norm interpolator and sparsest interpolators are not really related. Therefore I wonder whether this takeaway is really a general principle or more a quirk only exhibited in a highly specific setting. \n\n2. The setting, i.e., univariate data, the necessity for skip connections whose parameters are not included in the penalty is also restrictive, albeit  in line with other works. The focus on studying the min-norm interpolators also does not capture learning.\n\n3. Another minor comment I would have is that the statement to the effect of ``the most important factor behind generalization is the norm of the parameters\" in the introduction is a bit strong in my opinion. I would argue the jury is still out on this, in practice one can fairly often train a network with no explicit regularization and it can do fine and there is also a line of work suggesting implicit regularization cannot be explained in terms of norm minimization, see e.g., https://arxiv.org/pdf/2005.06398.pdf, https://arxiv.org/abs/2012.05156.pdf.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful comments. We now answer the concerns.\n\n*Incremental contribution*\n===\nIn the theory of NNs, the considered settings are often incremental wrt previous works. This incremental approach stems from the difficulty of the considered problems. Even relaxing a small condition can pose significant technical challenges. \n  The proof of Theorem 3, in particular, requires entirely new analyses and proof techniques. Thus, while the setting may be incremental, we firmly believe that Theorem 3 and the employed techniques, notably the dynamic program equivalence, extend well beyond an incremental scope.\n\n*Assumption 1*\n===\nPlease refer to our response to Rev. ZvaF for more details. The fact that min norm interpolators are not always the sparsest ones surprised us, as we had long believed that Theorem 3 would hold without any data condition. It was only after multiple experiments that we realized the min-norm interpolator may not be the sparsest. As a consequence, we still consider Theorem 3 to be significant. It sheds light on unexpected behaviors, which were not initially apparent.   \nWe believe that this discrepancy between min norm interpolators and sparsest interpolators also holds significance in gaining a better understanding of the implicit bias phenomenon (see our response to Rev. ZvaF and below). Additionally, it is worth noting that the result remains applicable for binary classification (Coro 1).\n\n  Whether this takeaway is a general principle remains an open question. We here only address this question within a simple and tractable setting. \n\n*Restrictive setting*\n===\nAs highlighted by Rev. fxbg, relaxing any of these conditions proves to be considerably more challenging. As often when studying NNs, comprehending the intricate and general setups used in practice remains elusive. Therefore, we focus on simpler settings that allow for precise quantification of already non-trivial phenomena. Please note that the considered simplifications (shallow networks, skip connections, univariate setups) are common in the literature. \n\nAs you pointed out, this work does not focus on optimization but rather on describing the min-norm interpolator. Both aspects are complementary and can be treated independently. Min-norm interpolators seem to play a pivotal role, given their close relation to various implicit bias works (on the optim aspect).\n\n*Parameters norm for generalization*\n===\nIn the NN literature, most generalization bounds rely on the parameters norm. The networks' ability to generalize, even without explicit regularization, is largely attributed to the implicit bias inherent to the optim algo. Although the implicit bias may not always favor the min-norm interpolator (see below), it generally guides the networks toward small-norm solutions (if not min-norm). \n\n*Implicit bias $\\neq$ min norm*\n===\nWe agree that implicit bias might not always lead to min-norm interpolators, although it appears to have a close association.\n\nBesides the mentioned references, a recent paper (Chistikov et al. 2023) presents a multidim example of data where the min-norm interpolator does not align with the sparsest interpolator. In this example, they demonstrate that the implicit bias instead leads to a sparsest interpolator (please see our answer to Rev. ZvaF for more details).  \n\nCharacterizing the exact criterion minimized by the implicit bias is an open research direction. Perhaps the implicit bias is better captured by “sparsest interpolator” and situations where “sparsest $\\neq$ min norm” correspond to cases where implicit bias does not lead to min-norm interpolators. Overall, the relationships between sparsest, min-norm interpolators and implicit bias remain misunderstood. We believe that our work contributes to advancing their understanding. \n\n*Smoothnes*\n===\nAs depicted in Figure 3, a smoother function is indeed learned when the biases are unpenalized.  This does not vary much with the regularization parameter. In fact, for larger values of this parameter, we may even observe fewer kinks, as the obtained estimator then does not overfit.  Unlike kernel regression settings, there is no target function here; only a finite dataset is considered.\n\n*Empirical evidence in harder cases*\n===\nConducting an empirical study on real data and architectures demands substantial effort and resources. Nevertheless, we believe the success of distillation is likely connected. For instance, the experiments conducted by Hinton et al. (2015) highlight that the learnt estimator  can be replicated by a smaller network. This aligns with our results, as the number of kinks is the number of neurons necessary to represent the function.\n\n*Sensitivity to the setting*\n===\nIn theory, the activation and single hidden layer play a critical role in obtaining the infinite width representation, as discussed with Rev. fxbg.  Analyzing higher dimensional inputs becomes considerably more intricate. An equivalent version of Theorem 1 has been proposed by Ongie et al. (2019) for the multidimensional case when biases are omitted. It might be possible to extend such a result when counting the biases, but seems much harder.\n\n On the other hand, deriving a multidimensional version of Theorem 3 remains even unknown when bias terms are omitted. \n\n*Other losses*\n===\nFor cross-entropy loss, Corollary 1 answers the question and shows that no data assumption is required for classification. These results are not influenced by the loss function, but rather by the setting (regression vs classif). In regression, the estimator of interest is the min-norm interpolator, applicable to most regression losses. Conversely for classif, the estimator of interest is the min-norm margin classifier, relevant for most classification losses. \n\n*Concentration around min norm*\n===\nIf we examine the distribution of the function learnt in Figure 3b) over multiple rounds, it won't concentrate around the function in Figure 3a). "}]

Author rebuttal:

Meta-review: This paper continues the study of minimum norm univariate networks, now showing a sparsity sensitivity. Reviewers are overall positive but have many comments, I urge the authors to revise appropriately during the camera ready phase.
Decision: Accept (poster)