A Mechanism of Implicit Regularization in Deep Learning
Authors: Masayoshi Kubo
Genki Sugiura
Kenta Shinzato
Momose Oyama
Venue:  (2020)
Keywords: Implicit Regularization
Generalization
Deep Neural Network
Low Complexity

Abstract: Despite a lot of theoretical efforts, very little is known about mechanisms of implicit regularization by which the low complexity contributes to generalization in deep learning. In particular, causality between the generalization performance, implicit regularization and nonlinearity of activation functions is one of the basic mysteries of deep neural networks (DNNs). In this work, we introduce a novel technique for DNNs called random walk analysis and reveal a mechanism of the implicit regularization caused by nonlinearity of ReLU activation. Surprisingly, our theoretical results suggest that the learned DNNs interpolate almost linearly between data points, which leads to the low complexity solutions in the over-parameterized regime. As a result, we prove that stochastic gradient descent can learn a class of continuously differentiable functions with generalization bounds of the order of $O(n^{-2})$ ($n$: the number of samples). Furthermore, our analysis is independent of the kernel methods, including neural tangent kernels.

Under review as a conference paper at ICLR 2020
A MECHANISM OF IMPLICIT REGULARIZATION IN DEEP LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Despite lot of theoretical efforts, very little is known about mechanisms of im- plicit regularization by which the low complexity contributes to generalization deep learning. In particular, causality between the generalization performance, implicit regularization and nonlinearity of activation functions is one of the ba- sic mysteries of deep neural networks (DNNs). In this work, we introduce a novel technique for DNNs called "random walk analysis" and reveal a mech- anism of the implicit regularization caused by nonlinearity of ReLU activation. Surprisingly, our theoretical results suggest that the learned DNNs interpolate al- most linearly between data points, which leads to the low complexity solutions in the over-parannn parraaettttteeed regime. As a result, we prove that stochastic gradient descent can learn class of continuously differentiable functions with generaliza- tion bounds of the order of O(n (n: the number of samples). Furthermore, our analysis is independent of the kernel methods, including neural tangent kernels.
INTRODUCTION
Deep Neural Networks (DNNs) have demonstrated dominating performance in numerous machine learning tasks, and it shows great generalization performance in the over- over-parameterizer regime. Theoretically, mechanisms of implicit regularization, which is considered as an important factor of such generalization performance in over aver-parameterized DNNs, still remain unknown (Zhang et al.) 2016 Neyshabur 2017). In the over-parameteriize regime, recent studies report that generalization bounds for DNNs can be obtained by replacing the neural network with its linear approximation model with respect to weight parameters at initialization. Most of these studies rely on the connec- tion between deep learning and neural tangent kernels (NTKs) (Daniely et al.] 2016 Jacot et al.] 2018 Arora al. 2019b), which characterizes the dynamics of network outputs throughout gra- dient descent training in the infinite width limit. However, source of implicit regularization in over-parameterizee DNNs has not been identified. Recent empirical and theoretical results indicate that generalization performance and implicit regularization of wer-paaameteriiee DNNs cannot be captured by NTK analysis (Wei et al.) 2018 Allen-Zhu & Li| 2019 Woodworth et al., 2019 Geiger et al. 2019). Understanding how implicit regularization properly controls the superfluous expres- sive power of over-pare wee-pparamterrized DNNs gives us new insights into the theoretical analysis in deep
learning. This leads to the first question:
Question 1. What kind of low complexity is caused by implicit regularization deep learning?
Linear networks without activation functions are important subject, and there are a number of theo- retical works on the implicit regularization in over-parameterized neural networks mainly focusing on linear models (Ji & Telgarsky (018) Gidel et al. 2019 Arora et al. (019a)). In contrast, whole properties of over- weer-paaameterized DNNs that may result from nonlinearity of activation functions cannot be captured by the approximated linear models, specifically, the kernel regression predictor using the NTK. However, some mechanisms of the implicit regularization can depend on nonlinear- ity. This leads to the next question:
Question 2. Can we identify a mechanism of implicit regularization that depends on nonlinearity of activation functions?
Now for optimization algorithms, the training dynamics of full batch gradient descent (GD) is better understood although GD is too expensive for most applications and one often uses stochastic gra-

---

Under review as a conference paper at ICLR 2020
10"
20-
10"
15-
random walk
10-
0.0
0.4 0.6 0.8 1.0
Figure 1: Random walks having step size distributed according to (0, 2/m) (m 10 after steps. The smaller the number of steps is, the more straight. For visibility, we transformed the random walk sequence {yr)i=o into {z, fi defined by Z; == (y; Yo) (i/a)(y. yo).
dient decent (SGD) instead. In most cases, the authors used GD to derive their results by the NTK analysis. Recent work showed that without any structural assumptions about the data distribution, two-layer or three-layer over-paree wver-parameterized networks trained by SGD can learn C* functions (Allen-Zhu et al.) 2018a| Arora et al., 2019c). However, it is not clear the relation between gener- alization and implicit regularization for DNNs optimized by SGD. Towards this end, the following question is also unsolved:
possible to obtain provable generalization bounds based on the implicit regular- ization for DNNs optimized by SGD?
Question 3.
To answer these questions, we introduce a novel analysis for DNNs and characterize a mechanism of implicit regularization that caused by nonlinearity of ReLU activation. Our results indicate that the DNNs (trained by SGD) interpolate almost linearly between data points, which leads to the low complexity solutions in the over-paree weer-parameterized regime. Accordingly, prove that SGD with random initialization can learn a class of continuously differentiable functions with generalization error bounds of the order of (n-=) (n: the number of samples), which is independent of the NTK analysis.
In order to introduce analysis for implicit regularization, let us focus the DNN output one-dimensional linear path between training points. We define it as x=s) == (1 ()x sz(()) (s E j0, 1), where (P)) and (9) are training points. The corresponding function of the DNN with ReLU (ReLU DNN) is continuous piecewise linear on the linear path x z(s). In the hidden layer, the corresponding function g' (a=) each unit in the I-th layer is also continuous piecewise linear on the linear path (=)), that is, a composite function (g' ox) (s) ) is continuous piecewise linear. Since DNN nonlinearity is linked to breakpoints, which is caused by ReLU activation, the set of the breakpoints plays a key role in the network behavior. These kind of breakpoints are also known as kinks or knots (Steinwart) 2019). Since (g' (s) is continuous piecewise linear, the gradient of (g' o 2) (s) has gaps at the breakpoints, which we call gradient gaps. We focus on gradient gaps with respect to the parameter Our key finding is that the gradient gaps are constant multiple of independent Gaussian random variables according to (0, 2/m). where m is the number of units in the hidden layer. Since the gradient of the unit (g' o x>) (s) is the sum of the gradient gaps, random walk the number of steps determines the Gaussian random walk behavior. In the corresponding function of the DNN, the step size variance is the variance of weights, and the number of steps is the number of breakpoints. In a regime where ( the number of steps x the step size variance) < O(1), the Gaussian random walk strolls little from the origin with high probability (see Figure D.. Our results show that the ReLU DNN is in the same regime and "simplicity" of the gradient depends crucially on the number of breakpoints. Hanin & Rolnick (2019) proves that the average number of breakpoints
a "Gaussian Step 2 in the proof of Lemma 3). The relation between the step size variance and
It worth pointing that in this paper, each gradient is derivative not with respect weight parameters with respect to imput parameters. If ( [X,]%_ are independent Gaussian random variables, then (Y) where Y, == X, + X2 + .... X., called Gaussian random walk.
2

---

Under review as a conference paper at ICLR 2020
is linear in the number of hidden units at initialization, and also give proof of an upper bound on the number of breakpoints even after training (see [3.Ip
In this work, prove priori generalization estimates, which is independent of the posterior data distribution, by analyzing the behavior of DNNs on the linear path æ($). In other words, we show that in Theorem 2, the difference between the network output function and its linear interpolation is evaluated only from the amount of the weight change. We note that in Theorem 2, we dose not use the properties of the trained neural networks. Our key analysis is that the gradient of unit (g' o xx) is a "Gaussian random walk" and approximately equal to a straight line on the linear path æ(s). which we call random walk analysis. Our technique is based on a priori estimates that variation of the gradients between data points is extremely small and depends essentially on the value of the number of breakpoints times the variance of weights.
Difference from NTK. Interestingly, analysis idea is different from other previous work based on NTK. Our findings are some novel aspects as follows:
The NTK defined using the gradient of the DNN output with respect to weight param- eter space. In contrast, the linear approximation (Lemma in this paper) is defined using the gradient of the DNN output with respect to input parameter space. In other words, the variables to be differentiated are different.
The random walk analysis indicates that peceparramtterieed ReLU DNNs interpolate al- most linearly between the data points. For ReLU activation, since the NTK kernel mapping is not Lipschitz but 1/2- 1/2-Hölder, it is difficult to obtain such a result in the NTK analysis without tradeoff between smoothness and approximation (Bietti & Mairal 2019).
Our Contributions. In this work, we consider an L-layer werrparameterized ReLU neural net- work with 12 regression task using SGD from random initialization. We show the constitutive rela- tion between implicit regularization and generalization, which enables us to provide new insights on the role of implicit regularization in deep learning. Our main contributions are follows:
Our random walk analysis provides priori estimates of low complexity in over- parameterized deep neural networks, and directly indicates that the unit output between data points is properly controlled by weight initialization and SGD to keep connecting the data points almost straight, which is one of the underlying mechanisms of implicit regular- ization in the wee-pparaeterizee regime.
Our result suggests that implicit regularization is attributed to the nonlinearity of ReLU DNN, which indicated by the fact that variance of weight and the number of breakpoints determine the Gaussian random walk behavior.
We also prove that in one-dimensione input case, SGD with random initialization can learn CC-csass functions. Our generalization estimates are based on the implicit regularization.
PRELIMINARIES AND NOTATION
Notation. For n E N, we let [n] (1,2..... We use N o²) to denote the Gaussian distribution of mean μ and variance o², We use || to denote the Euclidean norm of a vector v, random variable,
use ||>|| | to denote the Frobenius norm of a vector v. When Z is a sub-Gaussia inf (t 0 Elexp(z2//t)) S 2} denote sub-Gaussian norm /Vershynin 2018 For a vector v, we denote by [w]; or v; the i-th element of v. For a matrix M, we denote by M or Ma,; the entry in the i-th row and j-th column of M, and we denote by [M]; the i-th row vector of M. We denote by 1 the indicator function for the event E. ReLU activation is given by
we let ||z]|
((x) = m0 ). and for vector E R", we define ((a) (d((1), ((az)..... ((a.))
Network structure. In this work, an L-layer fully-connected feed-forward ReLU neural network with m units in each hidden layer is given by f gd RR For input æ E Rdd, unit output g' (x) of each layer / E [4] and network output f(x) are given by the following functions:
(x=) == Ax.
g'(x) = w o (1 [Z)),
f(x) = Bo(g)(x))) (1)
3

---

Under review as a conference paper at ICLR 2020
where A Rmxd, w E Rmx (1 E L), and B Re are weight matrices. We assume the Wis ~ (0,, 2/m), and B ~ (0, For imput æ and weight matrices W := (W', w ..... Wh), the network output f(x) is also denoted by f(W. æ). In this work, we only update weights in W and leave A and B at the random [L] we denote by G( diagonal matrix, which
following Gaussian initialization: A ~ 20 w!
initialization. For input represents the activation pattern of the 1-th layer, which we call an indicator matrix. More precisely, define the i-th diagonal element [G)),,,.
Ie and
1 {s((0))0)- Since the ReLU activation is positive homogeneous, we obtain the following equality: g' (ax)
(x)g'
Dataset and loss function. The data generated from an unknown distribution D over (a. y) Rd x Re, where æ is the input data point and y is the label associated with this data point. We assume without loss of generality that for each input æ (.1..... ................................ Td). using additional coordinates (E441,Td42) the replacement input x" == (I1,..., Id, Id+1, Id+2) is normalized so that || = 1 and its last coordinate Zd+2 = 1/v2.11 P we also use æ to denote the replacement input x" R242
The training data Z := {(x ()))
(x((), ( (")) is given as n i.i.d. samples from D. We
define the minimum distance of the training data: == min x Vi,j E [m], + > O.
For the 12 regression loss E(g. y) = 1 y1 and subset of training data Z C Z, we define our regression objective as follows: Cgr-) (W) == E (e. [e(f(W, ()) x)].
Stochastic gradient descent with Gaussian initialization. We use mini-batch SGD to train the network with a constant learning rate 77 > O, a batch size b and iteration number T. Let ( (WI.(0), w2.(0) WL.(0)), A, B be weight matrices generated from the above Gaus- sian initialization. Suppose we start at (0 and for each E [L] and t = 0, T
wl.(+1) wl.(1) 1 V Wi (W(())((()) (W()),
where g(() C E is mini-batch of size b. For input x, each layer 1 E [L] and each step & E [7]] we denote by (zx) the unit output, (x) the network output, wi.(t) the weight matrix, and (z) the indicator matrix.
In the above setting, recent paper (Allen-Zhu et al. 2018b) shows that SGD can allow an over- parameterized multi-layer network to attain arbitrarily low training error as follows:
Theorem (Convergence of SGD (Allen-Zhu et al. 2018b)). For any E E (0,1] 8 E (o, (1/L)) and b E [n], let m
Z Ω
poly(n.L.5 "jd"
= e poly(an F.m log" m
bdd
b
θ
poly(n.L) log² m log (alog m 682
and W (0) A. are at random initialization. Then, it satisfies
with probability at least 1 c Mllog? over randomness of _.. Z(T);
Le (W) S
||w1,(1- w1.100/
=0 (1 logm VT
[l,. [wl.0)) |:l12 S O (^ log m
(Vt E (T), where A A== n 3.6
Sv6
Our results on generalization also crucially depend on this analysis.
RANDOM WALK ANALYSIS
In this work, we consider the behavior of the unit output in each layer on a one-dimensional linear path between two data points, which we denote by ass) (s E [0, 1)). In this section, for notational simplicity, we drop the superscript with respect to (1), which is the (-th iteration.
'iitoout loss generality, one can rescale and assume ||=|||a Σ 1/v2 for every input æ. Again, without loss of generality,
pad each by an additional coordinate .a+1 to ensure ||æ l|2 = 1/v2. Finally, without loss of generality, one can pad each x' by an additional coordinate Ød+2 to ensure ||~ I|2 1. This
last coordinate 2 1 1/22 is equivalent to introducing (random) bias term and this procedure is described
in Allen-Zhu al. 2018a
4

---

Under review as a conference paper at ICLR 2020
Definition 3.1 (One-dimensional Linear Path). For each pair of data points x (()) and x(1) (p q), We define æ(s) ;= (1 s) x(p) s x(1), E [0, 1]. and denote by v x x()) the direction vector.
Note that the unit output gf (x)))) and the network output (s))))) are continuous piecewise linear functions on s E [0, 1], and the network output can be expressed as follows:
[(x(s)) = BG
W
W ................................ (...)(()()))))))))))))))) (((())) Ar(s).
(3)
Note that gf (x))) and f((x)s) have linear approximations at the point as follows
d Lds ((
d
d= = (0(()
+ (()))=)((z(())
f((s): f(()(0)) +
f((z(()) ds
(4)
==
We prove that these piecewise linear functions are almost straight, which contributes to the gener- alization of NN. In other words, the unit output (x())) can be approximated by a linear function with high accuracy. Moreover, the small difference between g(()(()) and (s) indicates the low complexity of the unit output.
Theorem (A Priori Estimates for Implicit Regularization). Under the same setting as Theorem 7 with probability at least 1 - c (loog m for every 2(0) x! (p. E [n]. P + a). (T]. 1 E [L].
i [m] and j E [c], we have
log' m
1.00) (a(s)) 9t (s) (s)
.1.00
sup 05
9i
S 0
Vm
(5)
log m)
sup
(()) (x(s)) (s) O
(s)
Vc |10122-
(6)
05.51
3.1 INTUITION BEHIND IMPLICIT REGULARIZATION
To prove Theorem we introduce our key analysis that the gradient of (z(()) is "Gaussian random walk" and nearly equal to straight line the linear path x=s), which we call random walk analysis. For simplicity, we explain the outline of the proof for the initial state of the network (i.e. - 0). All proofs are given in the Supplementary Material (including 0 Tt
To state our key Lemma, we define the following function: (s) == W w'd(g"-(ss)), which is an analogue of the unit output o' (=(s)) =
In other words, g' (s) is the one in which
(x(ss) is replaced by g (s). Next, Lemma shows that each j can be well approximated by a linear function (s) with high probability.
Lemma 3 (Linear Approximation Analogue). With probability at least 1 - -Stllg" m), for every (P)) (9) (p.g E [n]. p + 4), L E [T] and l E [L], we have
log² 2 Vm
sup 05451
94
(((()) (() (s)
0e 1.00)
(s)
0
|1
(Vi E [m]),
log" m Vc ||1|l2
sup 05a51
(s) - 7,0 0
(Vj E [c]).
(8)
The purpose of this subsection is to give an intuitive explanation of the proof of Lemma 3 which can be divided into two steps. The first step gives estimates of the number of breakpoints. We show that the number of breakpoints of the piecewise linear function (s) is less than or equal to the number of units in the layer (i.e. m).
The second step gives estimates of gradient gaps of (s). We show that the gradient gaps are independent Gaussian random variables and the gradient of g' (s) is the sum of the gradient gaps, which indicates that the gradient is a "Gaussian random walk". Note that in this setting, the number of breakpoints is equal to the total number of steps of the random walk.
Although the components of g (s), (s) are non-differemtiable at breakpoints, with prohability 1, the start point 0 is not breakpoint.
5

---

Under review as a conference paper at ICLR 2020
Step 1. By the definition of g'(s), we may write
(5( Σ W lis (0, (s))
Note that the input to the above Φ. that is 0j (s). is a linear function on E [0, 1]. For each has most one solution s*). the solution s s* satisfies 0 < 8* < 1, then 9, (s) has breakpoint at 8". This shows that the number of breakpoints of (s) is bounded by the number of the linear equations ( (s) = Se which 8 breakpoints of g (s), where is the number breakpoints. For B E [o], we set an open interval of breakpoints T = (83, 83+1)-
j E [m]] the linear equation 9, (s)
equal to m. We denote by 0 < 81 < 82
Step To give an intuition that the gradient of (s) - g, is "Gaussian random walk", we fix some notation. For 8 E [a], we define the gradient V/:
d di V = ds ( ( xl(3)
(10)
sEEp
Note that g, (s) is a linear function, and there is no breakpoints for (s) on 1g. Note also that since (s) 9. (s) is linear on II, the gradient is constant on llg. For 3 E [al, define gradient gap:
X3 = V3 V--1. and we have the following estimate with probability at least 1 - - -Qoog m);
log m
X3 = Swa where ws ~ (N(022/m) |S|
(11)
Note that w is an element of the weight matrix W Thus, {x,} are independent Gaussian random variables, and V is the sum of xg, that is
X (3 [a:).
(12)
This shows that the gradient V is "Gaussian random walk" and depends essentially on the num- ber of breakpoints a and the variance of weights 2/m. Using the randomness of W and general Hoeffding's 's inequality (Vershynim 2018), we have
- Swn Se 2 21
P
Σ
aclill lox?
(13)
According to Step 1, the number of breakpoints a is less than equal to m. Thus, V is bounded || with probability at least 1 - e- -R(og"" m). Therefore, with the same probability, we
by log" Vm
have de (i((s) - (s)) I log ||l|2, (Vs E [o, 1]). Thus, integrating this inequality from =
v
to shows the estimates of ( in Lemma 3 Note that the proof of ( in Lemmal 3 idential to
the above proof, except the fact that each entry of B follows from (0, 2/c) insted of NO 2/m).
Note that illustrated in Figure I for sufficiently large m. the gradient V can be made arbitrarily small, which means that the networks interpolate almost linearly between the data points.
3.2 PROOF THEOREM 2
The purpose of this subsection is to give the proof of Theorem 2 We proceed by induction on the
layer 1. Note that since gd (x(()) A is linear and ( 9 (x(x)), ÿ (s) identically equal to n² (x)()) W ( (Ax())). Thus, the case I = 1 is true. Assume the theorem holds for any layer k and let us prove for = & + 1. Using the triangle inequality, we have
o (ars)) - (s) | (a<(s) of +1)+ +10 11)+1(() +
(14)

---

Under review as a conference paper at ICLR 2020
By Proposition 11.3 of (Allen-Zha) et al. 2018b), for any y. y R", there exists diagonal matrix
D E R" R"** such that Dj.s I and ( ( = D - ÿ). Thus, for the first term on the RHS, we may write
l0 ++ (x(ss) - (5) [W 50 (x(ss)))]) - [ (o (s)]
(15)
m
-| ((g((((s) -
(()s))))(((s))) (0)))) Σ Wh' (s))
(16)
log m vm
- (
(17)
In the last inequality. we use general Hoeffding's inequality (Vershynim 2018), and this inequality
holds with probability at least 1 - ee - m), We can now apply our induction hypothesis to the
above estimate. Thus, applying 7 in Lemma 3 to the second term on the RHS of 14 shows the
estimates of 5 in Theorem
2 Next, Using the triangle inequality for 5!() we have
5 (x(s)) ()) s (x(s)) (s) +
-
(s)
(18)
In a similar way, using the randomness of B (recall each entry of B follows from (O, 2/c)), with probability least 1 -2olg m), we have
log (oogmm) Vc ( ||0|22-
(x(s)) 7 (s) - 1 (x(()) (s) 12
m log so
(19)
In the last incquality, we use 7 Lemma
Thus, applying 8 in Lemma to the second term on the RHS of (18) shows the estimates of Theorem We complete the proof.
3
GENERALIZATION
In this section, considering the mechanism of implicit regularization revealed by random walk anal- ysis, we provide priori estimates for the generalization performance of over-parameterized deep neural networks, in an 12 regression task on a one one-dimensional input-space. Since the network is wver-parameterized, the expressive power of the network is rich enough considerably overfit the data. Nevertheless, it is known empirically that properly initialized over-parameterized deep neural networks can achieve the good generalization performance while fitting training data. We esti- mate the low complexity of wertpparameterized deep networks and show that the error between trained over over-varameaeeee wee--aaameterizee neural network and the target function can be uniformly bounded by an arbitrarily small positive number.
Setting. We propose new type of generalization bounds (Theorem 4. and prove this theorem in models with one dimensional input: d = 1. In the following, we restrict ourselves to a one-
dimensional regression task on an interval [0, v] C IR. The training dataset ((x(0), () Jegju is given as n i.i.d. samples from some unknown distribution D. We assume that the corresponding target function for the regression task f" [0, v] + R is a class function. This implies that (i) = ())) Without loss of generality, we may assume that the input data (z( Jeeln] follow a uniform distribution on [0, v). and after relabeling, we may assume that the data points (oo(1,,.. (..,,.())))) are ordered by index: < (11) < ... < x(1) < v. We define (z((), ((()) = (0, fo (x(0))) (z)**+1,, f(*+1) == (v. (v)) and T = supRe(n+1] (zx()) - -((k-))). We denote by f: [0, v] + R the linear interpolation of the data points f(x(0))))))) (x())) }.em)]
A priori generalization bounds. Now, we introduce a novel approach for a priori generalization bounds, which is based on random walk analysis in the over wer-parameteriied regime. This can be interpreted as the significant expressive power of over parmperrmeeer neural networks is controlled by implicit regularization.
7

---

Under review as a conference paper at ICLR 2020
Theorem 4. Suppose (x) is class function on [0. v.. Under the same setting Theorem
for 5 (0, 1/2], then with probability at least (Ó + e e-Stloo m)), we have
ELEy (1T(W))))) 0
v²c
(20)
n2
Proof sketch of generalization. The purpose of this paragraph give an intuitive explanation of the proof of Theorem for one-dimensional output e = 1. All proofs are given in the Supplementary Material.
To estimate E(E,))D [ (() we evaluate (z) f (x)) which we may write as - (z) + f(x) - (())
(21)
The first term of the RHS of 21 represents an error between the trained network output (x) and the piecewise linear function fz)) We can use the results of random walk analysis to evaluate this critical term as follows. Theorem 2 provides that the linear approximation error of the network output, which we denote by y is small in each interval
and hence in each interval
(z.(k-1), [. J. the difference between (x)) and fxx) falls within the error e This suggests that the network output between adjacent training points is properly controlled by weight initial- ization and SGD keep connecting the points almost straight, which results in low complexity of
peer-parameterized neural networks. This statement can be extended to the interval [0, vj.. Fix e > 0,
and suppose 2 Ô (T% (=.). Then with high probability at least e 22log" m)) we have
E (z) - f(0) V2 sup zE[0.u]
(22)
The second term of RHS of (1 the error of the piecewise linear approximation of f*(x) by f(x) on the interval [0, v/. Note that the error can be reduced by increasing n. Hence, for any fixed
e 0, there exists 8 0 such that if 2 O w with probability least 1 8, we have
VEB
suPxe[u..) [f(z)= - (x)) s 2- Thus, from 21 b, for m and n sufficiently large, the error between the trained network output and the target function is uniformly bounded by on the interval [0, v] with probability at least (B=O(oos" m) + 6). This gives a priori estimates for the generalization performance of over- per-parrmeterized neural networks.
RELATED WORK
Implicit regularization in neural networks has recently become active area of research in ma- chine learning. A number of works have focused on the behavior of gradient descent on over- parameterized neural networks (Neyshabur et al. 2014 Lin et al.] 2016)] [Zhang al., 2016: Soudry et al. 2018 Rahaman et al. 2018). In order to get handle on implicit regularization in deep neu- ral networks, the majority of theoretical attention has been devoted linear neural networks (Ji &
Telgarsky 2018 Gidel et al. 2019 Arora et al. 201
Many works try explain generalization of oaere-araaeterriee neural networks. Recent works have shown that on sufficiently wer-pearaeterrized neural networks, the learning dynamics of gradient descent are governed by the NTK (Daniely et al. 2016)) Jacot et al.) 2018 Du et al., 2018 Allen
Zhu et al. 2018b; Lee et al. 2019 Arora et al. 2019b). In these settings, the implicit regularization and the generalization error of the resulting network can analyzed via NTK and the reproducing kernel Hilbert space (RKHS) (Bietti & Mairal 2019: Nakkiran al. 2019). To extend it to SGD, Hayou et al. (2019) introduce a stochastic differential equation dependent on the NTK. Closely related work Cao & Gu (2019) showed that the expected 0-1 loss of a wide enough ReLU network trained with SGD and random initialization can be bounded by the training loss a random feature model induced by the network gradient at initialization.
This contrasts with other recent results that show a provable separation between the generalization error obtained by neural networks and kernel methods (Wei et al., 2018 Allen-Zhu al. 2018a
8

---

Under review as a conference paper at ICLR 2020
Allen-Zhu & Li 2019). Several papers suggest that training deep models with gradient descent can behave differently from kernel methods, and have much richer implicit regularization (Chizat et al. 2019 Woodworth et al. 2019: Yehudai & Shamir 2019: Geiger et al. 2019).
CONCLUSION
In this work, probability estimates for the network output behavior (i.e. random walk analysis) pro- vide a priori generalization estimates for (2 regression problems. We prove that even after training, approximately Gaussian random walks, and the vari- network gradients between the data points ation the gradients between the data points extremely small and depends essentially on the number of breakpoints and the variance of weights. To the best of our knowledge, this paper the first to show a mechanism of implicit regularization and to prove the generalization bounds by using the implicit regularization for deep (three or more layer) neural networks with ReLU activation. As a result, we also show that over- wverparameterized deep neural networks can learn C' class functions. Importantly, our analysis is independent of the kernel generalization analysis, and the generalization bounds are different from the NTK inductive bias of the RKHS norm.
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? arXiv preprint a905v: 10337, 2019.
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization overparameter- ized neural networks, going beyond two layers. arXiv preprint arXiv:1811.04918 2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv: 181.:901 1.3962, 2018b.
Sanjeev Arora, Naday Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. arXiv preprint 1905.
2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. arXiv preprint 19t4::1994.19990 2019b.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901008584 2019c.
Alberto Bietti and Julien Mairal. On the inductive bias of neural tangent kernels. arXiv preprint arXiv: /2173, 2019.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. arXiv preprint 190.v:1955.132000 2019.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. arXiv preprint arXiv: 18/2.07956 2019.
Daryl Daley and David Vere-Jones. An introduction to the theory of poinl processes: volume II:
general theory and structure. Springer Science & Business Media, 2007.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks:
The power of initialization and dual view on expressivity. In Advances In Neural Information Processing Systems, pp. 2253-2261, 2016.
Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint 11X.v:1810.02054. 2018.
Mario Geiger, Stefano Spigler, Arthur Jacot, and Matthieu Wyart. Disentangling feature and lazy learning in deep neural networks: an empirical study. arXiv preprint arXiv:1906.0880 080344 2019.
Gauthier Gidel, Francis Bach, and Simon Lacoste- Julien. Implicit regullarzzoonnn of discrete gradient dynamics in deep linear neural networks, arXiv preprint arXiv: 19te::9994..1..2.... 2019.

---

Under review as a conference paper at ICLR 2020
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. arXiv preprint arXiv:1901.00021, 2019.
Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. Training dynamics of deep networks using stochastic gradient descent via neural tangent kernel. arXiv preprint 0rXiv:1905.1333 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Advances in neural information processing systems, pp. 8571- - 8580, 2018.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv: 18X0vv/8/0.00 10... 0200022 2018.
Jaehoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jef- frey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint 1KKi::9922.06200 2019.
Junhong Lin, Raffaello Camoriano, and Lorenzo Rosasco. Generalization properties and implicit regularization for multiple passes sgm. In International Conference on Machine Learning, pp- 2340-2344,, 2016.
Preetum Nakkiran, Gal Kaplun, Dimitris Kalimeris, Tristan Yang, Benjamin L Edelman, Fred Zhang, and Boaz Barak. Sgd on neural networks learns functions of increasing complexity. arXiv preprint arXiv: 1604, 2019.
Behnam Neyshabur. Implicit regularization in deep learning. arXiv preprint arXiv: 11Xiv:770900155. 2017.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1rXXiv:442.666 1412.6614.... 2014.
Nasim Rahaman, Devansh Arpit, Aristide Baratin, Felix Draxler, Min Lin, Fred A Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias deep neural networks. arXiv preprint 1806.0/800687344 2018.
Daniel Soudry, Elad Hoffer, Mor Shpigel Naeson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70), 2018.
Ingo Steinwart. sober look neural network initializations. arXiv preprint arXiv:190s 1482, 2019.
Roman Vershynin. High-dimenssionll probability: introduction with applications in data sci- ence. Number 47 in Cambridge series in statistical and probabilistic mathematics. Cambridge University Press, Cambridge, 2018. ISBN 978-1-108-4151944.
Colin Wei, Qiang Lee, Jason D.and Liu, and Tengyu Ma. Regularization matters: Generalization and optimization of neural nets v.s. their induced kernel. arXiv preprint (rXiv:1810.0536) 2018.
Blake Woodworth, Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Kernel and 2019.
deep regimes in overparametrized models. arXiv preprint arXiv:
Gilad Yehudai and Ohad Shamir. On the power and limitations of random features for understanding neural networks. arXiv preprint arXiv: 0968700687. 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530 2016.
10

---

Under review as a conference paper at ICLR 2020
A
PROOFS
A.1 PROOF OF LEMMA 3
Lemma (reshown, [m) + 4) & E [2] and E [L]. we have
3.1
With probability at least 1- e- -R(log f every alp), x(9) (p.ge E
log m Vm log" m ve
sup 0
((1)) (s) (s) 9i (s) 5
10l12.
(Vi E [m]),
(23)
sup
210 (s) - (s) 0
||
(vj e [c]).
(24)
0Se51
Proof. We prove Lemma for fixed [L] and [Z] every pair of data points a(P), x(9) (p, E [m], p # q). because we can apply union bound at the end.
Recall the definition (z) (the unit output), (z) (the indicator matrix function) and axs) = (1 - ())s))(())_) + sx()), 8 s [0, 1] (a linearly interpolating path between data points x æ(p), xl))), we have
g (n((s) (+) = w/.00 G'-1 ( w1-1.00... 1.............. (o (2)())
(25)
Using the definition of g (s) and ğ (s). we also have
g (s) w/i ( (x(0)
G
(26)
(27)
(s) w
(28)
W (z)) (1.00)()((( Ax(s),
(29)
where (s)),(((s) is an indicator diagonal matrix for s E [0, 1] as follows:
G 1.00 (s)]es
[G 1-10(
1 ( (2200
(s))e, = 0 (i
(30)
We begin by proving that the number of breakpoints of the function g. (s) in the interval [0.1] is bounded by m. For fixed i [mi) we have
g. 1.00 (s) = (w pT (1)10))))))
(31)
Σ w wi les oGoj" (1)()))s))
(32)
Σ Ww 99 (-1,(t) (s) (0) (0/- (1)00)
(33)
Note that the input to the above Φ, that is Ø 12_1,(( (s), a linear function on 8 E [0, 1]. For each j E [m]] the linear equation 71
='_1.(t) (s) = 0 has at most one solution s = s If the solution = s* satisfies inequality < 8* 1, then 9." (.00) (.00(s) (s) has a breakpoint at s s* This shows that the (((s) (s) is bounded by the number of the linear equations
number of breakpoints of q.
9 1-10(0 (s) = (j E [m)),
(34)
which is clearly equal to m.
We denote by 0 < 32 < breakpoints. For notational simplicity, we set Sg and sa+1 = 1. Note that, with probability 1,
Sa < 1 all breakpoints of 9, (.)))ss), (s). where is the number of
1.(1)
'Oteeriise, the linear function is identically zero (i.e. 3, (.(1.(()s)) (s) 0). which does not affect the number of breakpoints.
11

---

Under review as a conference paper at ICLR 2020
breakpoints are all distinct from each other. Each breakpoint sg (B E [a]) corresponds linear equation 0, 1 (s) = 0 for some j E [m]] In other words, for each breakpoint 83 (3 E [al), there exists a unique element j E [mm] such that 9, () = Therefore, for $ = 8g, we set j = ja (3 E [a)) then we have Ojs (-1.((0)sp) (sp) = 0.
is easy to verify de xxs) = x(1) x(() =: v. Therefore,
d (s) w..00 (2: - (2220000000)))))))))))))) 2,00 GLL0)% (a))))
ds
(35)
d (s) de
w Go.00 (zv)))
(36)
This implies,
d ds 9 (1000()) _g (s)
d
(37)
-w -G)
- G'' ('-1())0(0)) Gz ( (z(0))
(x())
(38)
Note that from the definition of the indicator matrix, and from the definition of the linear approximation, ğ ()) (x((((((x(()))))) which says that (i-1.(0)(0) equals (x))).
= 1 (lot 20)
For each i E [m], we may write
ds 9; (((t)
(s)
(s)
ds 91
d (.11) (s)
Σ wl.00 |
(39)
where (t) is matrix:
M wl- G1-2000) (2(0) 2.0).. ().00())))))
(40)
and XÚ is the difference of indicator functions:
X 1 33 (12- (2)00) 1 (00 (0120))
(41)
For B E (a). we set an open interval of breakpoints IB = (89, 88+1) ) and recall the notation of the
gradient V
g ds
d 1.00)
9:
(s)
.1((t) 9,
())()))))
(42)
and the gradient gap xg = V is constant in Llg.
8-1- Note that since there is not a breakpoint in Tg. the gradient
Hence, for 3 E [a] and E llg, we may write
ds 9
400
9
1.00 (s)
Σ
Xy.
(43)
ds
Note that the gradient gap x, (v E [a]) can be rewritten as
X, [w ol
(44)
where Ty is difference of indicator functions:
č : 1 1,,1111100
(d.)2)))))))) - 1 9/
1-1.1) (d--)00))
A dd-1 and V dd, E L.
(45)
12

---

Under review as a conference paper at ICLR 2020
Note that Sy is independent of the choice of dy-1 and dy. Note also that since the linear function 9jr 1-1,(0) (s) switches the sign at = 8n, we have S = +1.
We begin by proving the upper bound on Σ Xy, For notational simplicity, we use W to denote Wl.(0), and for lorl= E [Z] we set
dw WhO w w00 W
(46)
then we may write for y (a).
Ml | G G (2()) (=(0)
(47)
wl-11(1) 1 [No]p
(48)
m
Σ w 1n NNol [Nol + Law (yo0o" CsooNooo,
(49)
by + dhy;
(50)
where (z)2)0((((0) (1- (O.00)))))())))))
Therefore, we have
X, = (WW (M)))
(51)
2, [[W)]as + [dw') ((s,) (h,, db,)
(52)
"( + Jaw hy + ", db, + (d dh,
(53)
x + xx()) + x((2 + x())
(54)
In order to estimate Nv, we use the following estimate (see Lemma 7.1 and Claim 11.2 in (Allen-
Zhu al. 2018b)):
Lemma. If (0, 1], with probability at least 1 c e-(((m=)) IL), for fixed vector and I [L],
we have
(z()) w.1(0 (z()) (1+
(55)
This Lemma implies that with probability at least ((mmm/) we have
NNul2 = (0)) (z(0) w..0 g (2(())))) s 2|/1/22
(56)
We will estimate the 1st term x, Conditioning on this event 56) happens, using the randomness of Wi-1 and general Hoeffding's 's inequality (Vershynin, 2018), for each fixed vector n, we have
C+²
[lbb,| > > < 2 exx
(-2//²)|No
(57)
(2/m))
Choose = log m NN/12. Then, with probability at least 1 - c 221nng" m²) we have
log NNol22
|b. 1
(58)
m
We set (0) : T, and u (0)
(u (0)
( Note that since T, = +1, we have [
No The set of the gradient gaps (x!")) } = (u dependent Gaussian random variables. Hence, Σg x is a "Gaussian random walk" 12 Thus, using the randomness of W conditioning the above event (58). fixing any with probability
log m h, <
(0) (w'),,,) are a sequence of in-
/m
13

---

(1) Under review as a conference paper at ICLR 2020
least 1 e -2(0p m), we have
log
00)
|u (0)
ll2
(59)
v m
log m
Σ
3
log m
|Nol22
2
1/2
(60)
m
m
log" 2 m
< 2
Vm |0112-
(61)
(0) Therefore, we have the estimate of Xy
Next, we will estimate the 2nd term X By definition, we may write
8
Σ
S [dw" Jaj, by
(62)
Note that we use Theorem
1 (the convergence theorem) to write
||aw") [[[ [W')ella so (> log
(63)
m
Thus, applying the estimate of h, eq. (58). we have
9
log m
(1)
2
|101l
[aw'ks.
(64)
Vm
y=1
log
|0o|
(65)
Vm
log m
log" m vm
- CA
||lll
<
//1/2
(66)
m
The last inequality uses À < o(ym), which is indicated by the result of Theorem have the estimate of x
therefore we
Next, we will estimate the 3rd term x (2)
By definition, we may write
W Ii.j, dh.
(67)
Using the randomness of Wi and general Hoeffding's 's inequality Vershynin 2018), for each fixed vector we have
We set u = dh, and u (2) (u
(2)
Cr²
P
(2) w 1ist Σ
< 2exp
(68)
| max?
|| [ [ 11,
Cmr?
< 2cxp
(69)
21
Note that
dh, = Σ dw' (
(70)
14

---

Under review as a conference paper at ICLR 2020
and choose
log m v m2
[u 22, with probability - e -S((log" m), have
2 1/2
log m
log m
(2)
(2 12
Σ
Σ
dw
1sn Nolp
(71)
v m
1/2
log
log
||aw 1,,
dW |d
||1||1112
(72)
m
m
log" 2 |0/|2-
(73)
v'n
The last inequality uses E m and the result of Theorem 1
Idw ||- Wl-1.00 w s0lpsso
log m
(74)
v
(2) Therefore, have the estimate of X
Next, we will estimate the last term X Note that since C, 1,, we have |2,1 1, and condition- ing on this event (56) happens, may write
8
8
Σ (3)
=
So jaw la dh,
(75)
1=1
2
1/2
s ||
Σ
Σ jaw - Noi,
(76)
s || kil2
|[(ww- 11, 11 101
(77)
log² 2 m Vm
< [|
||0||2
(78)
Putting this all together, with probability 1 c e- 2R m)) we have
d 3. (s) ds
9. (s)
=
Σ
8
Xy
S 4
log²
Vm ||0|12.
2 m
(79)
ds
7=1
Therefore, have
< /- ds 91
d -
(0)(s) -+)s))7((s))
(s)
ds
(80)
ds
log 48
||0/2 (0 Vs 1).
(81)
m
This finishes the proof of 7 Lemma Finally, the proof of X in Lemma 3 is idential to the
above proof, except the fact that each entry of B follows from (0, 2/c) insted of M0 2/m). We complete the proof.
A.2 PROOF OF GENERALIZATION THEOREM
Theorem 2 (reshown, see
Under the same setting Theorem 7 with probability at least
1 Blogg m) for every P), ml4)) (p. [m) p 4),
[T), 1 [T]. i [m]] and [c].
15

---

Under review as a conference paper at ICLR 2020
have
log' m vm
sup
9i
1.00
(s) - (a(())
-%.
|1lll..
(82)
05451
log" r+l m)
sup 05
f (x(s)) (s)
S 0
vc
||0/2.
(83)
In order to give provable guarantees for the generalization performance of over-parameterizee deep networks in the 1 regression task on the one-dimensional input-space, we apply the above Theorem 2 to bound the error between the trained network output f (xx) and the piecewise linear function fx)) Note that if we apply Theorem to this case fone-dimension models), simple preprocessing needed: just consider a mapping [0, - $4 half circle).
= (Iı, E RR² || = 1, 2 1}
is apparent that there exists a C diffeomorphism from [0. to St. Under this setting, the input from S is the two-dimension. More precisely, the input needs another axis of coordinates to express the biases term. This procedure is written in the subsection of Dataset and loss function in the paper p.4. As a result, we deal with not the case of d = but the case of d
Theorem [ Lemma 5. Under the same setting Theorem 7 and for 8 (0, 1/2]. then with probability at least 1 (6 + e- e-A(log* m)), , we have
(x) (()) so log log't11 ++1 m m/ no
V
sup 2E[0,u]
(84)
Proof. Without loss of generality, we may assume that the entry of the weight matrix Big (0, 2/c), where = θ (m
For k [n + 1], we denote by [Is] the length of the interval 1l (ikk-1),x10 (1(k) We set =
m/3 in Theorem 2 with probability at least 1 eQ0lo? m), we have
(x) < SC log-+1
(N()) - - -ll--1/) =G
logut1 ++1
sup =EI,
1/6
sup [E(n+1]
m/66
T (85)
where Cj is constant, and T = supke(n+1] (x((k) - 111-11/ Here we set E Cj
log m T. m1/o
Note that f (1 = (2((-11) and f, (z = (z) by eq. 855 we have
1T7 --y--sssa (2(l0111)) Se and (x(()) - f Se.
(86)
Note that the piecewise linear function f linearly connects ((0,)(()))))) Thus, the following inequality holds.
and
sup
(x) - S
(87)
We use eq. 85 and eq.
87 to see that
sup #ei.
(T) (z)
(x)
< sup
(T) - (x)
sup zelx
(2) < 2e.
(88)
wet.
Note that E not dependent on Thus, we have
sup xE(0.r]
(x) < 25.
(89)
6 For each output y (y1, V2. Ve), additional coordinates (ye+1, Ve+2...., = (0,0.... can always be padded the output. We did not try hard to improve the exponent 1/3.
16

---

Under review as a conference paper at ICLR 2020
(x(*) - xx(-1)] Recall that the training dataset (2x(*) [Re[n] is generated from the uniform distribution in the interval [0, zj. We denote by pa= n/vv the density of training samples. In this setting, it is well known that for every r > 0 (r < v), the number of train- ing samples in the interval [0, r] follows the Poisson distribution with mean pr, then the sequence of inter-sample distances is independent and identically distributed exponential random variables having mean 1/ (= #) (Daley & Vere-Jones 2007). Define A to be the above exponential distri- bution having mean v/n, which is the inter-sample distance. Then, using Markov's inequality, for T > 0, we have
Next, evaluate T [n
P|
A
V
(90)
TRT
Thus, can choose :=
which implies that with probability at least 1 - 6, we have L or
(91)
nd
Combining this with eq.
(89 with probability at least (6 + e eQ m)), we have
log" ++1 m T S 20,
log*+1 m v
log ++1
sup [0
(x) ((t) s 20
m2/6
m/6 no
(92)
We complete the proof of the Lemma 5
Lemma 6. Suppose fz(z) is -l-sssss function on [0, v) and fz(2) is the linear interpolation of the data points {xx(0 S3 (x(01) rejn For 8 E (0, 1/2], with probubility at least 8, we have
(x( - (x) s So =E(0.0]
sup
(93)
no
Proof. We use (x)( denote the first derivative of (x)) Since fÿ is a C²- Cl-class function on the compact set [0, v], f3' is bounded function. Thus, we can define ((k) and S as follows:
S(k) := sup [x)) S sup S(K) kE[n+1]
(94)
xE
Since (z) and (z) are continuous functions, there exists ((()) (0 S (/(²) S xx(1) - 21(1)=(( (b(-1)) that
such
(z())- = |5 |1,0))=)]]a(a (z 1) + hb)) - (x + h*)
sup
(95)
By the mean value theorem, there exists real number (()) E I such that, fy( 1 (*) = ff (c()))
(K) + fj (xx(t1))
(96)
Note that by the definition of f,, we have f7 (x) -f (x((t-11)) therefore, we also have that [53 (x(tt11) + t0)) - (t + /( = (0(( + +b²(0) fj (z
F3" (c())) gf
(1)
(97)
-
- (6 dr
(98)
$ ((())
(99)
By considering whole interval [0, v/), we have sup =E
|0(0)- - (x) = sup
sup [5(x) f5())
< 2TS
(100)
kE[n+1]
Now we apply the estimate of T from eq. 91). We may therefore rewrite eq. 100) as
sup xE[0,0]
-x)))1(())) 0 nd
(101)
We complete the proof of Lemma
17

---

Under review as a conference paper at ICLR 2020
Proof of Theorem 4 (Generalization)
Proof. From eq. (89 and eq. 993
with probability at least 1- - - m)), we have for every
j = 1, .. C
(x) fz) & (x) + - (z)
log
CC nd
v
1+ (1
(Ve E (0,4))
1/16-
Using the triangle inequality, this gives
(1) 1 (z)
Σ
1 ( (x) (x) (T(]
2 j=1
$ 0²
1
u²
1+
log
1+1 m
(vx E (0,1]).
2 n²82
mn/6
where C = maxj=l,...e Cj. Thus, have the following estimate:
With probability least 1 - (6 + e -R(log m)), we have
BewN)~D [ ()()()))))
_
1
(0))
dr
(102)
v
Jo 2
v2
(
log ++ m
x
C² c n282
1
(103)
2
m m//6 1/6
We complete the proof.
18


Reviews:
[{"review_id": "SJl7uVgTKH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper suggests a new technique to analyze the implicit regularization caused by ReLU activations. They bound the generalization error by two terms: 1) one term that represents the distance between the trained network output and a piecewise linear function built based on the set of training points and 2) another term that represents the distance between the piecewise linear approximation and the desired target. The first term is bounded using a random walk type of analysis, which to the best of my knowledge is novel.\nI find this technique rather interesting and technically sound, although I do have a number of concerns and I'm at the moment more on the reject side, although I will re-consider my score if the authors can provide satisfactory answers.\n\nGeneralization to more complex activation functions\nIf I understand correctly, the interpolation technique between two points only works for ReLU functions. If one were to try to generalize the analysis to more complex non-linear functions by using a more complex interpolation schemes, wouldn’t you then have a random walk in high-dimensions? If so, wouldn’t that be a problem given the different properties of Brownian motion in high-dimensions?\n\nGeneralization to smooth activation functions\nAnother question related to the previous one is whether one could hope to generalize the analysis to smooth activation functions. I believe this is also a drawback of combinatorial techniques such as Hanin and Rolnick which have to rely on the discrete nature of the breakpoints.\n\nGeneralization bound is only derived for 1-d functions\nTheorem 2 is derived for each dimension independently while the generalization results in Theorem 4 are for 1-dimensional inputs. Where is the difficulty in generalizing these results to higher dimensions?\n\nPrior work on generalization of SGD\nI was really expecting a discussion about how the generalization bound derived in this paper compares to prior work, e.g.\nHardt, Moritz, Benjamin Recht, and Yoram Singer. \"Train faster, generalize better: Stability of stochastic gradient descent.\" arXiv preprint arXiv:1509.01240 (2015).\nKuzborskij, Ilja, and Christoph H. Lampert. \"Data-dependent stability of stochastic gradient descent.\" arXiv preprint arXiv:1703.01678 (2017).\nBrutzkus, Alon, et al. \"Sgd learns over-parameterized networks that provably generalize on linearly separable data.\" arXiv preprint arXiv:1710.10174 (2017).\nAnd many others…\nFor instance the bound derived in Hardt et al. is also of the order O(n^-2). The bounds in Kuzborskij are also data-dependent and so are yours since your generalization bound depends on the density of the training points. Can you comment on this? What specific insights do we gain your analysis?\n\nNoise SGD\nMy understanding is that the authors assume that the noise of SGD is Gaussian. Although this is commonly used when analyzing SGD, there is evidence that the noise is actually not Gaussian, see e.g.\nDaneshmand, Hadi, et al. \"Escaping saddles with stochastic gradients.\" arXiv preprint arXiv:1803.05999 (2018).\nSimsekli, Umut, Levent Sagun, and Mert Gurbuzbalaban. \"A tail-index analysis of stochastic gradient noise in deep neural networks.\" arXiv preprint arXiv:1901.06053 (2019).\nI feel this is worth pointing out and one could perhaps also extend this analysis to Heavy-tail noise. I would expect that the results would still hold in expectation but perhaps with a slightly worse probability.\n\nInfluence step size SGD\nUsing larger step sizes in the SGD updates increase the influence of the noise. I was expecting this to somehow be captured in your analysis but I fail to see where it appears. Can you comment on this? \n\nProof Lemma 3\nThe derivation of Eq. 10 does not seem completely justified in the proof in the appendix. The authors essentially prove that the length of the gradient gap is bounded by |S| but why is the coefficient \\omega distributed according to a normal distribution. It seems to me that you need the noise of SGD to be Gaussian for such statement to hold. Can you confirm this? If so, I think this needs to be clearly stated as an assumption since -- as pointed out above -- this is not necessarily true in practice.\n\nMinor: proof Theorem 2\nIt seems rather trivial but for completeness, you should write the proof of Eq. (6) in Theorem 2. \n\n“A priori estimates”\nThis is a terminology that is often used in the paper but never defined. What do you mean by “a priori” in this context?\n\nMinor comment\nI would move footnote 3 directly in the main step. I think it is important to point out that the steps of the random walk correspond to the breakpoints.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "HyxTMY0aKS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the implicit regularization in deep learning under the over-parameterized setting. In specific, the authors study the neural network outputs and “pre-activation values” on line segments connecting two training data inputs and characterize an implicit regularization based on it. I have the following concerns:\n\nFirst of all, it is not clear to me why Theorem 2 is relevant to “implicit regularization”. To my knowledge, implicit regularization or implicit bias statements in prior works cited in this paper are all about the convergence to a specific solution for underdetermined problems. For example, “among all solutions that fits the data, gradient descent converges to minimum distance solution to initialization (linear model square loss), maximum margin solution (linear model exponential loss), minimum nuclear norm solution (matrix sensing with small initialization)”. In comparison, Theorem 2 just gives some bounds that holds for every sgd iteration. I cannot see any connection between Theorem 2 and implicit regularization.\n\nMoreover, the authors’ claim “the implicit regularization in over-parameterized DNNs has not been identified” is not correct. As the authors mentioned,  the neural network is close to its linear approximation model with respect to weight parameters at initialization. Therefore the implicit bias of (stochastic) gradient descent for DNNs in the over-parameterized regime is essentially implicit bias of (stochastic) gradient descent for linear models (for square loss). In Arora et al., 2019b it has been proved that infinitely wide neural networks trained with gradient flow converges to the NTK-based kernel regression solution.  So at least for gradient flow with square loss, the implicit bias of DNNs has been well-studied. In fact in a missed reference [2], essentially the implicit bias for both gradient descent and stochastic gradient descent has been studied. The remark “in most cases, the authors used GD to derive their results by the NTK analysis” is also not convincing. Allen-Zhu et al., 2018a,b, Allen-Zhu & Li, 2019 and missed references [1,2,3,4] all studied SGD of over-parameterized neural networks, and some are not exactly in the so-called NTK regime. The authors should also compare their generalization bounds with existing results for SGD (Allen-Zhu et al., 2018a, Allen-Zhu & Li, 2019) and [3].\n\nFinally, Theorem 4 only considers one-dimensional models, which is not a very interesting problem setting. Its proof might also be flawed. In fact, the setting in Section 4 is not consistent with Theorem 1, since Theorem 1 requires that all inputs have unit norm and their last coordinate should be a constant. For one dimensional case, this means all inputs must be the same scalar! Even if we ignore the last coordinate assumption in Theorem 1, for 1D case all inputs are still reduced to +1 or -1’s. \n\n\n[1] Difan Zou, Yuan Cao, Dongruo Zhou, Quanquan Gu, Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks\n[2] Samet Oymak, Mahdi Soltanolkotabi, Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?\n[3] Yuan Cao, Quanquan Gu, Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks\n[4] Difan Zou, Quanquan Gu, An Improved Analysis of Training Over-parameterized Deep Neural Networks\n\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bklb9IfRtS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Review of \"A mechanism of ... deep learning\"\n\nThis paper studies the generalization performance and implicit regularization of deep learning. In particular, the authors propose a novel technique called \"random walk analysis\" to study the nonlinearity of the neural network with respect to the input data points. Moreover, the authors prove that for a class of 1-d continuously differentiable functions, SGD can achieve O(n^{-2}) generalization error bound.\n\nOverall this paper is well written and easy to follow. The linear approximation with respect to input parameter space is also interesting and seems to be useful in the generalization analysis. Besides, I have the following comments and concerns.\n\n1. I am a little bit confused by the definitions \"Priori generalization estimates\" and \"posterior data distribution\". I would like to see clearer description in the introduction.\n2. I would like to see more discussion on Theorem 2 in the surrounding text, it is quite unclear to me why Theorem 2 is important and how it can be related to the \"implicit regularization\".\n3. I do not see the proof of (6) in Section 3.2.\n4. It seems that the generalization results in this paper are difficult to be generalized to high-dimension regimes. For example, if you assume that each entry of the training data point is generated from the uniform distribution in the interval [0, v], the density of training sample would be \\mu = n/(v^d), and the resulting generalization bound would be O(v^d/(n\\delta)), which is extremely large.\n5. It seems that the generalization results hold for any data distribution. However, it is widely known that if the training data is randomly labeled, the neural network trained by SGD cannot achieve small population risk, which contradicts the result in Theorem 4.\n\n\n----------------------------\nAfter reading the authors' response, I still think that the generalization results in this paper are not significant and important, and how the theoretical results can be related to the implicit regularization. Thus I would like to keep my score.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes a mechanism of the implicit regularization caused by nonlinearity of ReLU activation, and suggests that the learned DNNs interpolate almost linearly between data points, which leads to the low complexity solutions in the over-parameterized regime. The main objections include (1) some claims in this paper are not appropriate; (2) lack of proper comparison with prior work; and many other issues in the presentation. I agree with the reviewers’ evaluation and encourage the authors to improve this paper and resubmit to future conference.

Decision: Reject