On The Implicit Bias of Weight Decay in Shallow Univariate ReLU Networks
Authors: Boris Hanin
Venue: Submitted to ICLR 2023 (2023)
Keywords: theory
implicit bias
generalization
interpolation
theoretical
shallow ReLU networks
ReLU networks
analysis of weight decay

Abstract: We give a complete characterization of the implicit bias of infinitesimal weight decay in the modest setting of univariate one layer ReLU networks. Our main result is a surprisingly simple geometric description of all one layer ReLU networks that exactly fit a dataset $\mathcal D= \set{(x_i,y_i)}$ with the minimum value of the $\ell_2$-norm of the neuron weights. Specifically, we prove that such functions must be either concave or convex between any two consecutive data sites $x_i$ and $x_{i+1}$. Our description implies that interpolating ReLU networks with weak $\ell_2$-regularization achieve the best possible generalization for learning $1d$ Lipschitz functions, up to universal constants. 

Under review as a conference paper at ICLR 2023
ON THE IMPLICIT BIAS OF WEIGHT DECAY IN SHAL- LOW UNIVARIATE RELU NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We give a complete characterization of the implicit bias of infinitesimal weight decay (i.e. an & penalty on network weights) in the modest setting of univariate one layer ReLU networks. Our main result is a surprisingly simple geometric de- scription of all one layer ReI.U networks that exactly fit dataset = ( vi)) with the minimum value of the f2-norm of the neuron weights. Specifically, we prove that such functions must be either concave or convex between any two con- secutive data sites z; and Ti+1. Our description implies that interpolating ReLU networks with weak (z-regularization achieve the best possible &o generalization error for learning 1d Lipschitz functions, up to universal constants.
INTRODUCTION
The ability of overparameterized neural networks to simultaneously fit training data (i.e. interpolate) and generalize unseen test data (i.e. extrapolate) is robust empirical finding that underpins the success of deep learning in computer vision He et al. (2016); Krizhevsky et al. (2012). natural language processing Brown et al. (2020), and reinforcement learning Jumper et al. (2021); Silver et al. (2016); Vinyals et al. (2019). This observation is surprising when viewed from the lens of traditional learning theory Bartlett & Mendelson (2002); Vapnik & Chervonenkis (1971), chiefly because such complexity- -ased methods are agnostic to the choice of optimizer and seek to predict generalization based solely on the complexity of the overall hypothesis class and how well learned model fits the training data.
In an overparameterized neural network, however, the quality of predictions at test time often varies dramatically across settings of trainable parameters (e.g. weights and biases) that exactly fit all training data Zhang et al. (2017). Which setting of parameters is learned depends crucially on the optimization procedure, and insightful analysis of generalization in the presence of overpa- rameterization must therefore combine properties the model class with the often subtle criteria according to which different minimizers of an empirical risk are selected by different optimizers.
This has led to a vibrant sub-field of deep learning theory that analyzes the implicit bias or implicit regularization of optimizers used in practice Arora et al. (2019); Blane et al. (2020); Gunasekar al. (2018); Hanin & Sun (2021): Jacot et al. (2020); Ma et al. (2018); Razin & Cohen (2020); Smith al. (2021). The high level goal of this line work is to explain how optimization hyperparameters such as initialization scheme, learning rate, batch size, data augmentation scheme, and choice of explicit regularizer influence which of the many global minima of the empirical risk are selected in the course of optimization.
A key difficulty in studying implicit bias is that it is unclear how to understand. coneretely in terms of the network function, the effect of particular optimization hyperparameters. For example, well- chosen initialization for gradient-hand based optimizers is key to ensuring good generalization properties of the resulting learned network He et al. (2015); Mishkin & Matas (2015); Xiao et al. (2018). However, the corresponding geometric or analytic properties of the learned network are often hard to pin down, obscuring understanding of what it is about the learned functions that encourages generalization.
In similar vein, is standard practice to experiment with explicit regularizers such an & penalty on network weights. While the effect of this choice is easy to describe in terms of model parameters (e.g. it tends to make them smaller), it is typically challenging to translate such description into

---

Under review as a conference paper at ICLR 2023
6
62
66
S7
63
86
81
22
85
53
84
6
65 =
T1
T2
33
Σ4
35
T6
27
I8
Figure 1: dataset with m 8 points. Shown are the "connect the dots" interpolant fo (dashed line), its slopes s; and the "discrete curvature" 6 at each 24.
properties of a learned non-linear model. In the simple setting of one layer ReLU networks there has been some relatively recent progress in this direction. Specifically, starting with an observation in Neyshabur et al. (2014) the articles Ongie et al. (2019); Parhi & Nowak (2020a;b; 2021); Savarese et al. (2019) explore and develop the fact that l2 regularization on parameters in this setting is provably equivalent to penalizing the total variation of the derivative of the network function (cf eg Theorem 1.3 from prior work below). These articles apply to networks with any input dimension. In this article, however, these prior results to give complete geometric answer to how interpolating ReLU networks with weak & penalty use training data make predictions unseen data. Our main results are:
consider the simplest case of input dimension 1 and significantly refine
1. We consider a dataset of the space of one layer ReLU networks with single linear unit which fit the data and, among all such interpolating networks, do so with the minimal l norm of the neuron weights. There are infinitely many such networks, and they described by the constraint that they the data with as few inflection points as possible (see Thms. 1.1, 1.2).
{(x;, yi) with F;. Vs R and give complete description
2.
The above description of the space of interpolants of D gives uniform control of the Lipschitz constant of any such interpolant and immediately yields sharp generalization bounds for learning 1d Lipschitz functions. This is stated in Corollary 1.1. Specifically, if the dataset D generated by setting yı = ff for f. j0, 1] + R Lipschitz function, then any one layer ReLU network with single linear unit which interpolates D but does so with minimal fo-m of the network parameters will generalize as well as possible to unseen data, up to small universal multiplicative constant. To the author's knowledge this the first time such generalization guarantees have been obtained.
1.1
SETUP AND INFORMAL STATEMENT OF RESULTS
Let us denote
[4 = ReLU(() max (0.1)
and consider one layer ReLU network
2(x) = =x= 2(2;0,n) ax + +b+
Σ
w
(2)
w (1)
x
(1)
(I)
2

---

Under review as a conference paper at ICLR 2023
with input and output dimensions equal to 1 and a single linear unit' and For given dataset
D = (T Ut), i l...... m) -0o 21 < ... < 2m 0o, yi E R,
if the number of datapoints m is smaller than the network width n. there are infinitely many choices of the parameter vector 0 for which 2(2; 8) interpolates (i.e. fits) the data:
2(x;;; 8) y/: Vi I,..., m.
Without further information about how 0 was selected, little can be said about the function <(2; 8) on intervals (I; zi+1) between two consecutive datapoints when n is much larger than m. This precludes useful generalization guarantees that hold uniformly over all 0 subject only to the interpolation condition equation 2.
In practice interpolants are not chosen arbitrary. Instead, they typically learned by some variant of gradient descent starting from a random initialization. For a given network architecture, initial- ization scheme, optimizer, data augmentation scheme, regularizer, and on, understanding how the learned network uses the known labels {yi, = I...., m) to extrapolate values of z(æ; 0) for æ in intervals (Ir; xi+1) away from the datapoints in D is an important open problem. To obtain non- trivial generalization estimates and make progress on this problem, a fruitful line of inquiry in prior work has been to search for additional complexity measures based on margins Wei al. (2018), PAC-Bayes estimates Dziugaite & Roy (2017: 2018); 8); Nagarajan & Kolter (2019), weight matrix norms Bartlett et al. (2017); Neyshabur et al. (2015), information theoretic compression estimates Arora et al. 20, Rachemacher complexity Golowich et al. (2018), etc that, while perhaps not ex- plicitly regularized, are hopefully small trained networks. The idea then that these complexity measures being small gives additional constrains on the capacity of the space of learned networks. We refer the interested reader to Jiang et al. (2019) for a review and empirically comparison of many such approaches.
In this article, we take a different approach to studying generalization. We do not seek general results that are valid for any network architecture. Instead, goal is describe completely, in concrete geometrical terms, the properties of one layer ReIJU networks =(2;; 0) that interpolate a dataset D the sense of equation with the minimal possible l2 penalty
C(Ø) = C(e, n) = Σ (1/0P+|//307
3=1
on the neuron weights. More precisely, we study the space of ridgeless ReLU interpolants RidgelessReLU(() of a dataset D, defined by
( R + R 30, n s.t. [(x) = =(<; 0) Vo E IR, =(x;00) = yı Vi = 1....,,.... C(0) = C.}
where
:= |C(0,n)|2(Enn))) 0.m
yt V(n, w+) E D}.
While we do not prove this directly here, a simple intuition for the elements of RidgelessReLLU that they are all univariate one layer ReL.U networks that minimize weakly penalized loss
((: D) + XC(0),
x<1
(4)
where L is an empirical loss, such as the mean squared еттог over D, and the strength À of the weight decay penalty C(0) is infinitesimal. There is an important subtlety in the definition of RetiellessReLU(D)
Namely, given 0, there exist infinitely many 0 such that =x;;0) =(x; Ō) for every æ. Thus, function belongs to RidgelessReLLU()) if ʃ interpolates the dataset D and 2xx; 0) f(z) for some setting of e that achieves the minimal value of C(0)) among all such interpolants.
It it plausible but by no means obvious that, with high probability, gradient descent from a random initialization and weight decay penalty whose strength decreases to zero over training converges to an element in RidgelossReLU (D). This article does not study optimization, and we therefore leave this as an interesting open problem. Our main result is simple description of RidgelessReLLU and can informally be stated as follows:
'The presence of the linear term ax b is not really standard in practice but is adopted in keeping with prior work Ongic et al. (2019); Parhi & Nowak (2020a); Savarese et al. (2019) since it leads cleaner mathematical formulation of results.
3

---

Under review as a conference paper at ICLR 2023
Theorem 1.1 (Informal Statement of Theorem 1.2). Fix dataset D {(2;, Be), i= 1,..., m} and define
$ = yi+1 y/i
6, =
sgn sgn - (i-)):
24+1 24
Note that is the slope of the line connecting (I', We) to (Ii+11 15+11 and that 6j is estimate for the sign of the local curvature of the function that generated the data (Figure 1). Among all contin- uous and piecewise linear functions f that interpolate D exactly, the ones in RidgelessReLU(D) are precisely those that:
Are linear (or more precisely asfine) on intervals (2i, F1+1) when neighboring datapoints disagree on the local curvalure in the sense that 6i-1 +
Are convex (resp. concave) on sequences of intervals (i+1) (1i+q-1, Ti+q) which datapoints ;.....,Zity agree the local curvature in the sense that 6, =...._ cs4g = 1 (resp. E = Ei+1 = -1). On such intervals f lies below (resp. above) the straight line interpolant of the data. See Figures 5 and 7.
Before giving precise statement our results, we mention that, as described in detail below, the space RidgelessReLU(() has been considered in a number of prior articles Ongic et al. (2019); Parhi & Nowak (2020a); Savarese al. (2019). Our starting point will be the useful but abstract characterization of RidgelossRel.UU they obtained in terms of the total variation of the derivative of 2 (2;; f) (see equation 5).
Let us also note that the conclusions of Theorem 1.1 (and Theorem 1.2) also hold under seemingly very different hypotheses from ours. Namely, instead of éz-regularization on the parameters, Blanc et al. (2020) considers SGD training for mean squared error with iid noise added to labels. Their Theorem 2 shows (modulo some assumptions about interpreting the derivative of the ReL.U) that, among all ReLU networks a linear unit that interpolate a dataset D, the only ones that minimize the implicit regularization induced by adding iid noise SGD are precisely those that satisfy the con- clusions of Theorem 1.1 and hence are exactly the networks in RidgelessReL. that our results hold under much more general conditions. would be interesting characterize them.
This suggests
Further, our characterization of RidgelessRel.U( in Theorem 1.2 immediately implies strong generalization guarantees uniformly over RidgelessRee.UUO We give representative example in Corollary 1.1, which shows that such ReLU networks achieve the best possible generalization error of Lipschitz functions, up constants.
Finally, note that we allow networks z(2; 0) of any width but that if the width is too small relative to the dataset size m, then the interpolation condition equation 2 cannot be satisfied. Also, we point out that in our formulation of the cost C(#) we have left both the linear term az + b and the neuron biases unregularized. This is not standard practice but seems yield the cleanest results.
1.2 STATEMENT OF RESULTS AND RELATION TO PRIOR WORK
Every ReLU network <xx; 8) a continuous and piecewise linear function from RR to IR with a finite number of affine pieces. Let us denote by PL the space of all such functions and define
PL(D) = {f E PL| f(x) = Vi = 1,..., m} to be the space of piecewise linear interpolants of D. Perhaps the most natural element in PL(D)
is the "connecttthee-ots interpolant" fD IR.. R given by
(1(x)),
x 322 34 < x < a4+1 1 1= 2...,, m
[D(x)
(x),
lm (1))
x > Im-1
where for i 1, 1,..., m-- -1, we've set
(x) = (x - 22)3; +
==
Dit1 Vi Li+1 T;
4

---

Under review as a conference paper at ICLR 2023
See Figure 1. In addition to fD, there many other elements in RidgelessReL((D)) Theorem 1.2 gives a complete description all of them phrased in terms of how they may behave on intervals (2), 2441) between consecutive datapoints. Our description is based on the signs
E; = sgn (s; - 8
2 S m
of the (discrete) second derivatives of fD at the inputs 2; from our dataset.
Theorem 1.2. The space Ridgeless(eLLU()) consists of those f E PL(D) satisfying:
1. f coincides with fD on the following intervals:
(1a) Near infinity, iee. on the intervals (-00, I2), (Im-1; oo)
(lb) Near datapoints that have zero discrete curvature, i.e. on intervals (#z-1, with i == ....., m - such that =.
(Ic) Between datapoints with opposite discrete curvature, i.e, on intervals (Ia, 1441) with i= = such that -4+1= -1.
2. f is convex (resp. concave) and bounded above (resp. below) by fo between any consec- utive datapoints which the discrete curvature is positive (resp. negative). Specifically, suppose for some 3 S i S i + S m
m - that D4 and Titq are consecutive discrete
inflection points in the sense that
6i+9:
6i4q # fitgt1-
c = (resp. 4; =-11, then restricted the interval (141 f is convex (resp. concave) and lies above (resp. below) the incoming and outgoing support lines and below (resp. above) fD:
G =1
max (x)- (xng())} S f(x) s fn(z) min (()-1(x), (+tg(()) (x)) 2 f(z) z fD(L)
G --1
for all x E (I4, Tztg)-
We prove Theorem 1.2 in $A. Before doing so, let us illustrate Theorem 1.2 as algorithm that, given the dataset D, describes all elements in RidgelessReLU(() (see Figures 5 and 7):
Step Linearly interpolate the endpoints: by property (1), f Re)))))ssseL..((D)) must agree with fD on (2)0, and (Im-1,
Step Compute discrete curvature: for i 2.... calculate the discrete curvature E; at the data point Z4.
Step Linearly interpolate on intervals with zero curvature: for all i= 2,...... , 1 which 6; property (I) guarantees that coincides with the I'D on (0i-1,24411)
Step Linearly interpolate on intervals with ambiguous curvature: for all = 2, 2,..., ....., at which 6 6++1 = -1 property (1) guarantees that f coincides with fD on (0,, T.41))
Step Determine convexity/concavityy
remaining points: all intervals (I;, zi+1) which has not yet been determined occur in sequences (Zi, Ii+ ..... (Ii 1, zitg) on which C+tj = or Cştj = 1 for all j = 0 O..... 9. c, = 1 (resp. e; = - 1), then ff is any convex (resp. concave) function bounded below (resp. above) by fo and above (resp. below) the support lines (x)), (x).
5

---

Under review as a conference paper at ICLR 2023
1 22
33
24
25
D6
37
27
Figure 2: Step 1
--
62
6
11 x2
23
F4
T5
T6
07
38
Figure 3: Step 2
|-
-1
95
59
= 1
=1
32
E3
T4
I5
Σ6
Σ7
D8
Figure 4: Step 3
Figure 5: Steps 1 - for generating RidgelessReLU(() from the dataset D.

---

Under review as a conference paper at ICLR 2023
62
66
T1
T4
26
Figure 6: Step 4
f6
0
65
F3
T4
28
3s
Figure 7: Step 5. One possible choice of convex interpolant (æa, 25) and of concave inter-
polant on (me, 277 is shown. Thin dashed lines are the supporting lines that bound all interpolants below (I4, 27) and above on (I),

---

Under review as a conference paper at ICLR 2023
The starting point for the proof of Theorem 1.2 comes from the prior articles Neyshabur et al. (2014); Ongie et al. (2019); Savarese et al. (2019), which obtained an insightful "function space" interpretation of RidgelessReLU( (D) as subset of PL(D). Specifically, a simple computation (cf e.g. Theorem 3.3 in Savarese et al. (2019) and also Lemma A.4 below) shows that ÍD achieves the smallest value of the total variation I[ TV for the derivative Df among all f PT.(D) (The function D f is piecewise constant and | TY is the sum of absolute values of its jumps.) Part of the content of the prior work Neyshabur al. (2014); Ongie et (2019); Savarese al. (2019) is the following result
Theorem 1.3 (ef Lemma in Ongic et al. (2019) and near eq, (17) Savarese et al. (2019) ) For any dataset D we have
RidgelessReLU(D) = (f PL(D)
= = IIDfbllrv)
(5)
Theorem 1.3 says that RidgelessReeLU()) is precisely the space of functions in PL(D) that achieve the minimal possible total variation norm for the derivative. Intuitively, functions in RidgclossReLL(()) are therefore averse oscillation in their slopes. The proof of this fact uses simple idea introduced in Theorem of Neyshabur et al. (2014) which leverages the homogeneity of the ReLU translate between the regularizer C(0), which is positively homogeneous of degree 2 in the network weights, and the penalty [|DSllrv. which is positively homogeneous of degree in the network function.
Theorem 1.2 yields strong generalization guarantees uniformly over RidgelessRel.U(D) To state representative example, suppose D is generated by a function f= [0, R:
Dj = fo (T;))
We then find the following
Corollary 1.1 (Sharp generalization on Lipschitz functions over compact set), Fix dataset D (1r,,,)) = I,..., m) with v, E [0. We have
sup ReltigellmReLL(()
IIfll S llp
(6)
Hence, if fa is L-Lipschitz and we denote by A == max; m-1 min i {x, - 2ÿ} the maximal dis- tance between consecutive training points (with 2g = 0, Im+1 1), then
sup /eRidgelesRoLU(i)
sup 1f(x) - f.(x)) - AL, =E(0,1]
which is the best generalization error possible, up multiplicative constants.
Proof. Observe that for any i = ., and x E (It, at which Df(x) exists we have
c s,) (Dff(z) s,) S c((441 -1).
Indeed, when = 0 the estimate equation 8 follows from property (Ib) in Theorem 1.2. Otherwise, equation follows immediately from the local convexity/ooncavity of f in property (2). Hence, combining equation 8 with property (Ia) shows that for each i 1,....
Df I max {|s:-1l, |s:]].
Again using property (1a) and taking the maximum over 2.... m we find
max |s;| ||fblllipp 1sism-1
To complete the proof of equation 6 observe that for every i I,..., m-1
|s: = 9i+1 yi
fa(xi+1)- (.
< ||
I| $ 11ff~
T,+1 24
T141 24
Given any x = [0, 1), let us write for its nearest neighbor in {ær, i = O, O...., m + 13. We find
fa(x)) (11/ + || 11.A |or - x'1 L.A Taking the supremum over f Redgg)lsssRel.U(DD) and [0, 1] proves equation 7.
- < 1f(x)
8

---

Under review as a conference paper at ICLR 2023
Corollary 1.1 gives the best possible generalization enror of Lipschitz functions, up to a universal multiplicative constant, in the sense that if all we knew about fx : [0, 1] + R was that it was L- Lipschitz and were given its values on {z,, i 1,..., m). then cannot recover f. in _ to accuracy that is better than a constant times LA. For m uniformly spaced points we have A = 1/m 1, while elassical results (e.g. Theorem 2.2. in Holst (1980) show that if x;- ~ UUif((O, 1]) are iid, then A is bounded above by a constant time log(m)/m with high probability.
1.3 OUTLINE OF PROOF OF THEOREM 1.2
In this section, we briefly outline the main steps in proving Theorem 1.2:
A "local straightening" result given in Proposition A.1. This shows that any element in RedggllessRel.U(D be either convex or concave on any interval of the form (#i, Ti+1) between two consecutive inputs in the training data. The main idea is that non-monotonicity of Df on such intervals can only increase ||Dflltv
A "lincarity at endpoints" result given in Proposition A.3. This shows that any element RidgelossReL.U( D) agrees with fo to the left of 22 and to the right of Im-1- The main idea is that, given restricted to (22, mm-1), linear extension of f to the complement of this interval can already interpolate the values at 1. at zero additional cost to || [ flrv-
A "left-right compatibility" result given in Propositions A.4, A.5, A.6. This gives con- straints, by dividing into cases, on the monotonicity of "incoming slopes" sin (2;, and "out- going slopes" Sout of any f E RidgelessReLLU D). The main idea is that the slope of on each interval (o4, Tz+1) must attain values that are both less than or equal and great than equal the slope 8; of the fD- This give constraints between 8;-1, S1, Sin (24), Sout (24)-
Combining the preceding results allows us to conclude that RidgelessReLJU(D a subset of the set of functions satisfying the conclusions of Theorem 1.2.
Finally, Proposition A.7 shows that the of functions satisfying the conclusions of Theo- rem 1.2 are a subset of RidgelessReLLU()
1.4 DISCUSSION OF LIMITATIONS AND FUTURE WORK
In this article, completely characterized all possible ReL.U networks that interpolate given dataset D in the simple setting of weakly lz-regularized one layer ReI.U networks with a single linear unit and input/output dimension Moreover, our characterization shows that, to assign labels to unseen data such networks simply "look at the curvature of the nearest neighboring datapoints on each side," " in way made precise in Theorem 1.2. This simple geometric description led to sharp generalization results for learning 1d Lipschitz functions in Corollary 1.1.
This opens many direction for future investigation. Theorem 1.2 shows, for instance, that there are infinitely many ridgeless ReLU interpolants of a given dataset D. It would be interesting to understand which ones are actually learned by gradient descent from random initialization and weak (or even decaying) f2-penalty in time. Further, 1.1, the conclusions of Theorem 1.2 appear to hold under very different kinds of regularization (e.g. Theorem 2 in Blanc et al. (2020)). This raises the question: what is the most general kind of regularizer that is equivalent to weight decay, at least in our simple setup?
already pointed out after the Theorem
Finally, it would also be quite natural to extend the results in this article ReLU networks with higher imput dimension, for which weight decay is known to correspond to regularization of a certain weighted Radon transform of the network function Ongie et al. (2019); Parhi & Nowak (2020a;b; 2021). Finally, extending the results in this article to deeper networks and beyond fully connected architectures are directions left to future work.
REFERENCES
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pp. 254-263, 2018

---

Under review as a conference paper at ICLR 2023
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, pp. 7413-7424, 2019.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
Peter L Bartlett, Dylan J Foster, and Matus Telgarsky. Spectrally
margin bounds for neural networks. In Advances in neural information processing systems, pp. 6240-6249, 2017.
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by an ornstein-uhlenbekk like process. Conference on learning theory, pp- 483-513. PMLR, 2020.
Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners arXiv preprint 20Xiv:2005. 2020.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. Uncertainty in 1008, 2017.
AI. 2017.
Gintare Karolina Dziugaite and Daniel M Roy. Data-dependent pac-bayes priors via differential privacy. NIPS 2018. arXiv:/802.09583 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 297-299, 2018
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Sre- bro. Implicit regularization in matrix factorization. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-10. IEBE, 2018.
Boris Hanin and Yi Sun. How data augmentation affects optimization for linear regression. Advances in Neural Information Processing Systems, 34, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-leve performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Lars Holst. On the lengths of the pieces of a stick broken at random. Journal of Applied Probability, 17(3):6236333 1980.
Arthur Jacot, Berfin Simsek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Implicit regularization of random feature models. In International Conference on Machine Learning, pp. 4631-4640 PMLR, 2020.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan. and Samy Bengio. Fantastic generalization measures and where to find them. ICLR 2020. 1rXiv:19/2.02/777 2019.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583--55) 2021.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Advances in neural information processing systems, pp. 1097-1105, 2012.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex sta- tistical estimation: Gradient descent converges linearly for phase retrieval and matrix completion. In International Conference on Machine Learning, pp. 3345-3354, PMLR, 2018.
10

---

Under review as a conference paper at ICLR 2023
Dmytro Mishkin and Jiri Matas. All you need is good init. ICLR. 2016. arXiv:1511.06422, 2015.
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalization bounds for deep networks via generalizing noise-resilience. ICLR 2019. (etp:/995.3344,, 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization deep learning. ICLR Workshop. arXiv: /412.6644, 2014.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLR, 2015.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. ICRL 2020. 19000009/00 2019.
Rahul Parhi and Robert D Nowak. Banach space representer theorems for neural networks and ridge splines. arXiv preprint (xXi::2006006666, 2020a.
Rahul Parhi and Robert Nowak. Neural networks, ridge splines, and regularization in the radon domain. arXiv e-prints, pp. arXiv-2006, 2020b.
Rahul Parhi and Robert D Nowak. What kinds of functions do deep neural networks learn? insights from variational spline theory. arXiv preprint orXiv:2105.03300 2021.
Noam Razin and Naday Cohen. Implicit regularization in deep learning may not be explainable by norms, Advances in neural information processing systems, 33:21 17,-1117788 2020.
Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? COLT arXiv:1902.05044 2019.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Samuel L Smith, Benoit Dherin, David GT Barrett, and Soham De. On the origin of implicit regu- larization in stochastic gradient descent. arXiv preprint arXi::2101.12176, 2021.
VN Vapnik and A Ya Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Measures of Complexity, 16(2):11, 1971.
Vinyals, I Babuschkin, J Chung, M Mathieu, M Jaderberg, Czarnecki, A Dudzik, A Huang, P Georgiev, R Powell, et al. Alphastar: Mastering the real-time strategy game starcraft ii, 2019.
Colin Wei, Jason Lee, Qiang Liu, and Tengyu Ma. On the margin theory of feedforward neural networks. 2018.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel S Schoenholz, and Jeffrey Penning- ton. Dynamical isometry and mean field theory of cnns: How train 10,000-layer vanilla convolutional neural networks. ICML and
2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Rep- resentations, (ICLR), 2017.


Reviews:
[{"review_id": "r9yjPhOWZW", "reviewer": "Reviewer_Y8Pp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the implicit bias of univariate one-hidden layer ReLU networks with infinitesimal weight decay. In this setting, the authors derive a geometric description for all the networks that interpolate some given training data and attain the minimal value of the $\\ell_2$ norm of the neuron’s weights. Then, the authors use this result to obtain a generalization guarantee for learning $1d$ Lipschitz functions.", "summary_of_the_review": "Overall, I think that the paper's contributions are not sufficient for acceptance, as discussed under “weaknesses”. Supplying some additional results, as suggested above, will significantly strengthen the paper.", "strength_and_weaknesses": "**Strengths:**\n- The paper is well written and explains clearly how the results relate to previous works.\n- The generalization guarantee for ReLU networks is an interesting and novel result, to the best of my knowledge.\n\n**Weaknesses:**\n* The main weakness is that the setting is quite restricted. The results only apply to univariate one hidden layer ReLU networks which interpolate the training data and minimize a $\\ell_2$ penalty. As the authors mention, the penalty does not regularize the linear terms in the ReLU network, which is not standard practice. I think that the results will be much stronger if the authors either:\n    + Supply some optimization result that motivates studying this setting.\n    + Extend the results to the multivariate setting using the results from Ongie et al (2019).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "cBDi4-XkoL", "reviewer": "Reviewer_LdBk", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers a one-layer ReLU network that only considers 1-D input. The authors study a set of solutions RidgelessReLU(D) that has the smallest norm of weights among all interpolators of the training samples. The authors show that the functions in such a set satisfy certain requirements by examining the second-order discrete derivative. Based on these requirements, this paper provides a generalization upper bound on Lipschitz functions when the 1-D input is uniformly spaced (deterministically) in [0, 1], and argues that a similar result also holds if the 1-D input is drawn independently at random from [0, 1].", "summary_of_the_review": "I don't think this paper will be helpful in understanding the performance of existing neural networks, because of 1) an oversimplified setup, and 2) no connection/similarity with the actual gradient descent with weight decay used in the neural network.", "strength_and_weaknesses": "Strength: The presentation is relatively clear.\nWeakness: The setup is too restrictive and not justified properly. See my comments below.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "cAiYTkJmQvr", "reviewer": "Reviewer_oSFb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper attempts to study the generalisation properties of one-dimensional ReLU networks directly, instead of via the usual VC-dimension or Rademacher complexity-type bounds. \n\nTo this end, they *geometrically* characterise the space of one-layer ReLU networks with a single linear unit, which *fit* a given dataset $D \\subset \\mathbb{R}^2$ *while achieving the minimum possible $\\ell_2$ norm among the neuron weights*.  \n\nMain Results: \nA geometric characterisation of all one-layer ReLU networks that exactly fit a univariate dataset $D \\subset \\mathbb R^2$. Since ReLU networks in this context are just piecewise linear functions, this turns out to be described by the constraint that the network fits the data while achieving as few inflection points as possible. \n\nCorollary: Interpolating ReLU networks with $\\ell_2$ regularisation achieve best possible $\\ell_\\infty$ generalisation error for one-dimensional Lipschitz functions. \n\nTheir work builds on the observation due to Neyshabur(2014) that $\\ell_2$ regularisation in the setting considered is equivalent to penalising the TV distance of the derivative of the network function. This observation applies to any dimension, but the complete characterisation in this paper is only for one-dimensional neural networks. \n", "summary_of_the_review": "This paper gives a complete characterisation of the $\\ell_2$ minimizing univariate ReLU network. \n\nI think this is a complete result for a simple setting that provides interesting insights into the generalisation as well as geometric properties of the minimiser, and vote to accept it. ", "strength_and_weaknesses": "Weaknesses:\n1. The paper does not study optimization, only the generalisation guarantees that are achieved by the minimiser. \n2. Only the one-dimensional setting is studied. \n\nStrengths: \n1. The authors describe an algorithm which is a consequence of the theorem, that allows them to describe all elements that might minimise the $\\ell_2$ norm of the weights while interpolating the dataset. \n2. I personally like the attempt at a geometric characterisation of the min-cost interpolating function, and generalisation guarantees that might arise from that. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "A8mKCfwfCy", "reviewer": "Reviewer_izUL", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper asks a very interesting question about implicit bias of neural training - in particular about interpolating depth 2 nets. Instead of trying to ask which of these interpolating nets would some training algorithm find, this paper tries to come up with a geometrical description of a subset of these nets which have a certain minimum norm condition on its parameters - when the input and the output dimension of the net is 1. \n\nAlso the paper chooses to work with an unconventional class of nets which have an additional linear unit. But then one is left to wonder why the authors' didn't frame it as a result about R -> R depth-2 ResNets - which is what this looks like. There are a few  more ambiguities like this which I shall point out in the later parts of the review.  ", "summary_of_the_review": "Its a very nice piece of work and I think it can lead to some very interesting further work. My main complaint is with the writing/organization of the main theorem's proof - and some claims which seem to have feet of clay - like the following line at the end of page 3,  \n\n\"The elements of RidgelessReLU(D) can intuitively be thought of as all univariate one layer ReLU networks that minimize a weakly penalized loss...and the strength lambda of the weight decay penalty is infinitesimal.\"\n\nEither this is a claim that the authors should be be able to put in the proof for - or they should formally state this as a conjecture. \nCurrently the wording is quite dodgy. ", "strength_and_weaknesses": "The framing of the question is quite interesting and its generalization implications are intriguing. The paper zones into a very special case and solves it in details. The approach is very appreciable.  \n\nThe weakness of the paper is in its organization of the main proof.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject