Year: 2019

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.

heading: 1 INTRODUCTION
text: Deep Neural Networks (DNNs) have demonstrated dominating performance in numerous machine learning tasks, and it shows great generalization performance in the over-parameterized regime. Theoretically, mechanisms of implicit regularization, which is considered as an important factor of such generalization performance in over-parameterized DNNs, still remain unknown (Zhang et al., 2016; Neyshabur, 2017). In the over-parameterized 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 connection between deep learning and neural tangent kernels (NTKs) (Daniely et al., 2016; Jacot et al., 2018; Arora et al., 2019b), which characterizes the dynamics of network outputs throughout gradient descent training in the infinite width limit. However, a source of implicit regularization in over-parameterized DNNs has not been identified. Recent empirical and theoretical results indicate that generalization performance and implicit regularization of over-parameterized 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 expressive power of over-parameterized 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 in deep learning?
Linear networks without activation functions are important subject, and there are a number of theoretical works on the implicit regularization in over-parameterized neural networks mainly focusing on linear models (Ji & Telgarsky, 2018; Gidel et al., 2019; Arora et al., 2019a). In contrast, whole properties of over-parameterized 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 nonlinearity. 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-
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-parameterized networks trained by SGD can learn C∞-class functions (Allen-Zhu et al., 2018a; Arora et al., 2019c). However, it is not clear the relation between generalization and implicit regularization for DNNs optimized by SGD. Towards this end, the following question is also unsolved:
Question 3. Is it possible to obtain provable generalization bounds based on the implicit regularization for DNNs optimized by SGD?
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-parameterized regime. Accordingly, we prove that SGD with random initialization can learn a class of continuously differentiable functions with generalization error bounds of the order of O(n−2) (n: the number of samples), which is independent of the NTK analysis.
In order to introduce our analysis for implicit regularization, let us focus on the DNN output on a one-dimensional linear path between training points. We define it as x(s) := (1 − s)x(p) + sx(q) (s ∈ [0, 1]), where x(p) and x(q) are training points. The corresponding function of the DNN with ReLU (ReLU DNN) is continuous piecewise linear on the linear path x(s). In the hidden layer, the corresponding function gl(x) of each unit in the l-th layer is also continuous piecewise linear on the linear path x(s), that is, a composite function (gl ◦x)(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 (gl ◦x)(s) is continuous piecewise linear, the gradient of (gl ◦x)(s) has gaps at the breakpoints, which we call gradient gaps. We focus on gradient gaps with respect to the parameter s.1 Our key finding is that the gradient gaps are a constant multiple of independent Gaussian random variables according to N (0, 2/m), where m is the number of units in the hidden layer. Since the gradient of the unit (gl ◦ x)(s) is the sum of the gradient gaps, it is a “Gaussian random walk”2 (see Step 2 in the proof of Lemma 3). The relation between the step size variance and 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 × the step size variance) ≤ O(1), the Gaussian random walk strolls little from the origin with high probability (see Figure 1). 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
1 It is worth pointing out that in this paper, each gradient is a derivative not with respect to weight parameters but with respect to input parameters.
2 If {Xi}αi=1 are independent Gaussian random variables, then {Yi}αi=1, where Yi := X1+X2+ · · ·+Xi, is called a Gaussian random walk.
is linear in the number of hidden units at initialization, and we also give a proof of an upper bound on the number of breakpoints even after training (see §3.1). In this work, we prove a priori generalization estimates, which is independent of the posterior data distribution, by analyzing the behavior of DNNs on the linear path x(s). 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 (gl ◦x)(s) is a “Gaussian random walk” and approximately equal to a straight line on the linear path x(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, our analysis idea is different from other previous work based on NTK. Our findings are some novel aspects as follows:
• The NTK is defined using the gradient of the DNN output with respect to weight parameter space. In contrast, the linear approximation (Lemma 3 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 over-parameterized ReLU DNNs interpolate almost linearly between the data points. For ReLU activation, since the NTK kernel mapping is not Lipschitz but 1/2-Hölder, it is difficult to obtain such a result in the NTK analysis without a tradeoff between smoothness and approximation (Bietti & Mairal, 2019).
Our Contributions. In this work, we consider an L-layer over-parameterized ReLU neural network with l2 regression task using SGD from random initialization. We show the constitutive relation 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 as follows:
• Our random walk analysis provides a priori estimates of low complexity in overparameterized 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 regularization in the over-parameterized regime.
• Our result suggests that implicit regularization is attributed to the nonlinearity of ReLU DNN, which is 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-dimensional input case, SGD with random initialization can learn C1-class functions. Our generalization estimates are based on the implicit regularization.

heading: 2 PRELIMINARIES AND NOTATION
text: Notation. For n ∈ N, we let [n] = {1, 2, . . . , n}. We use N (µ, σ2) to denote the Gaussian distribution of mean µ and variance σ2. We use ‖v‖2 to denote the Euclidean norm of a vector v, use ‖v‖F to denote the Frobenius norm of a vector v. When z is a sub-Gaussian random variable, we let ‖z‖ψ2 = inf{t > 0 | E[exp(z2/t2)] ≤ 2} to denote sub-Gaussian norm (Vershynin, 2018). For a vector v, we denote by [v]i or vi the i-th element of v. For a matrix M , we denote by [M ]i,j or Mi,j the entry in the i-th row and j-th column of M , and we denote by [M ]i the i-th row vector of M . We denote by 1{E} the indicator function for the event E. ReLU activation is given by φ(x) = max{0, x}, and for a vector a ∈ Rn, we define φ(a) = ( φ(a1), φ(a2), . . . , φ(an) ) .
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 : Rd → Rc. For input x ∈ Rd, unit output gl(x) of each layer l ∈ [L] and network output f(x) are given by the following functions:
g0(x) := Ax, gl(x) := Wlφ(gl−1(x)) (l ∈ [L]), f(x) := Bφ(gL(x)), (1)
where A ∈ Rm×d, Wl ∈ Rm×m (l ∈ L), and B ∈ Rc×m are weight matrices. We assume the following Gaussian initialization: Ai,j ∼ N (0, 2/m), Wli,j ∼ N (0, 2/m), and Bi,j ∼ N (0, 2/c). For input x and weight matrices −→ W := (W1,W2, . . . ,WL), the network output f(x) is also denoted by f( −→ W,x). In this work, we only update weights in −→ W and leave A and B at the random initialization. For input x ∈ Rd and l ∈ [L] , we denote by Gl(x) a diagonal matrix, which represents the activation pattern of the l-th layer, which we call an indicator matrix. More precisely, we define the i-th diagonal element as [ Gl(x) ] i,i
:= 1{gli(x)≥0}. Since the ReLU activation is positive homogeneous, we obtain the following equality: gl(x) = WlGl−1(x)gl−1(x).
Dataset and loss function. The data are generated from an unknown distribution D over (x,y) ∈ Rd × Rc, where x 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 x = (x1, . . . , xd), using additional coordinates (xd+1, xd+2), the replacement input x′′ := (x1, . . . , xd, xd+1, xd+2) is normalized so that ‖x′′‖2 = 1 and its last coordinate xd+2 = 1/ √ 2. 3 we also use x to denote the replacement input x′′ ∈ Rd+2. The training data Z := {(x(1),y(1)), . . . , (x(n),y(n))} is given as n i.i.d. samples from D. We define the minimum distance of the training data: δ := min{‖x(i)−x(j)‖2 : ∀i, j ∈ [n], i 6= j} > 0.
For the l2 regression loss `(ŷ,y) := 12‖ŷ − y‖ 2 2 and a subset of training data Z(τ) ⊂ Z, we define our regression objective as follows: LZ(τ)( −→ W) := E(x,y)∼Z(τ) [`(f( −→ W,x),y)].
Stochastic gradient descent with Gaussian initialization. We use mini-batch SGD to train the network with a constant learning rate η > 0, a batch size b and iteration number T . Let −→ W(0) := (W1,(0),W2,(0), . . . ,WL,(0)), A, B be weight matrices generated from the above Gaussian initialization. Suppose we start at −−−→ W(0) and for each l ∈ [L] and t = 0, 1, . . . , T − 1,
Wl,(t+1) = Wl,(t) − η · ∇WlLZ(t)( −→ W(t)), (2)
where Z(t) ⊂ Z is a mini-batch of size b. For input x, each layer l ∈ [L] and each step t ∈ [T ], we denote by gl,(t)(x) the unit output, f (t)(x) the network output, Wl,(t) the weight matrix, and Gl,(t)(x) the indicator matrix.
In the above setting, recent paper (Allen-Zhu et al., 2018b) shows that SGD can allow an overparameterized multi-layer network to attain arbitrarily low training error as follows:
Theorem 1 (Convergence of SGD (Allen-Zhu et al., 2018b)). For any ε ∈ (0, 1], δ ∈ (0, O(1/L)] and b ∈ [n], let m ≥ Ω̃
( poly(n,L,δ−1)d
b
) , η := Θ ( bδd
poly(n,L)m log2m
) , T =
Θ (
poly(n,L) log2m bδ2 log
( n logm
ε
)) , and −→ W(0),A,B are at random initialization. Then, it satisfies
with probability at least 1− e−Ω(log2m) over randomness of Z(1), . . . Z(T ): LZ( −→ W) ≤ ε, ‖Wl,(t) −Wl,(0)‖F ≤ O ( λ logm√
m
) , ‖[Wl,(t)]i − [Wl,(0)]i‖2 ≤ O ( λ logmm ) (∀t ∈ [T ]), where λ := n
3.5√c δ √ b .
Our results on generalization also crucially depend on this analysis.

heading: 3 RANDOM WALK ANALYSIS
text: 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 x(s) (s ∈ [0, 1]). In this section, for notational simplicity, we drop the superscript with respect to (t), which is the t-th iteration.
3Without loss of generality, one can rescale and assume ‖x‖2 ≤ 1/ √ 2 for every input x. Again, without loss of generality, one can pad each x by an additional coordinate xd+1 to ensure ‖x′‖2 = 1/ √ 2. Finally, without loss of generality, one can pad each x′ by an additional coordinate xd+2 to ensure ‖x′′‖2 = 1. This last coordinate xd+2 = 1/ √ 2 is equivalent to introducing a (random) bias term and this procedure is described in Allen-Zhu et al. (2018a).
Definition 3.1 (One-dimensional Linear Path). For each pair of data points x(p) and x(q) (p 6= q), We define x(s) := (1− s) x(p) + s x(q), s ∈ [0, 1], and denote by v := x(q) − x(p) the direction vector.
Note that the unit output gli(x(s)) and the network output fi(x(s)) are continuous piecewise linear functions on s ∈ [0, 1], and the network output can be expressed as follows:
f(x(s)) = BGL(x(s))WLGL−1(x(s))WL−1 · · ·G1(x(s))W1G0(x(s))Ax(s). (3)
Note that gli(x(s)) and fi(x(s)) have linear approximations at the point s = 0 as follows 4:
g̃li(s) := g l i(x(0)) + s ·
[ d
ds gli(x(s)) ] s=0 , f̃i(s) := fi(x(0)) + s · [ d ds fi(x(s)) ] s=0 . (4)
We prove that these piecewise linear functions are almost straight, which contributes to the generalization of NN. In other words, the unit output gli(x(s)) can be approximated by a linear function with high accuracy. Moreover, the small difference between gli(x(s)) and g̃ l i(s) indicates the low complexity of the unit output. Theorem 2 (A Priori Estimates for Implicit Regularization). Under the same setting as Theorem 1, with probability at least 1 − e−Ω(log2m), for every x(p), x(q) (p, q ∈ [n], p 6= q), t ∈ [T ], l ∈ [L], i ∈ [m] and j ∈ [c], we have
sup 0≤s≤1
∣∣∣gl,(t)i (x(s))− g̃l,(t)i (s)∣∣∣ ≤ O ( loglm√ m ) ‖v‖2, (5)
sup 0≤s≤1
∣∣∣f (t)j (x(s))− f̃ (t)j (s)∣∣∣ ≤ O ( logL+1m√ c ) ‖v‖2. (6)

heading: 3.1 INTUITION BEHIND IMPLICIT REGULARIZATION
text: To prove Theorem 2, we introduce our key analysis that the gradient of gl,(t)(x(s)) is “Gaussian random walk” and nearly equal to a straight line on 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. t = 0). All proofs are given in the Supplementary Material (including 0 ≤ t ≤ T ). To state our key Lemma, we define the following function: ğl(s) := Wlφ(g̃l−1(s)), which is an analogue of the unit output gl(x(s)) = Wlφ(gl−1(x(s))). In other words, ğl(s) is the one in which gl−1(x(s)) is replaced by g̃l−1(s). Next, Lemma 3 shows that each ğli can be well approximated by a linear function g̃li(s) with high probability. Lemma 3 (Linear Approximation Analogue). With probability at least 1 − e−Ω(log2m), for every x(p), x(q) (p, q ∈ [n], p 6= q), t ∈ [T ] and l ∈ [L], we have
sup 0≤s≤1 ∣∣∣ğl,(t)i (s)− g̃l,(t)i (s)∣∣∣ ≤ O( log2m√m ) ‖v‖2, (∀i ∈ [m]), (7)
sup 0≤s≤1 ∣∣∣f̆ (t)j (s)− f̃ (t)j (s)∣∣∣ ≤ O( log2m√c ) ‖v‖2, (∀j ∈ [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 ğli(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 ğli(s). We show that the gradient gaps are independent Gaussian random variables and the gradient of ğl(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.
4 Although the components of gl(s), f(s) are non-differentiable at breakpoints, with probability 1, the start point s = 0 is not a breakpoint.
Step 1. By the definition of ğl(s), we may write
ğ li (s) = m∑ j=1 [Wl]i,j φ(g̃ l−1 j (s)) . (9)
Note that the input to the above φ, that is g̃ l−1j (s), is a linear function on s ∈ [0, 1]. For each j ∈ [m], the linear equation g̃ l−1j (s) = 0 has at most one solution (s = s∗). If the solution s = s∗ satisfies 0 < s∗ < 1, then ğ li (s) has a breakpoint at s = s ∗. This shows that the number of breakpoints of ğ li (s) is bounded by the number of the linear equations {g̃ l−1 j (s) = 0}j∈[m], which is equal to m. We denote by 0 < s1 < s2 < · · · < sα < 1 breakpoints of ğ li (s), where α is the number of breakpoints. For β ∈ [α], we set an open interval of breakpoints Iβ := (sβ , sβ+1).
Step 2. To give an intuition that the gradient of ğli(s)− g̃ li (s) is “Gaussian random walk”, we fix some notation. For β ∈ [α], we define the gradient∇β :
∇β := d
ds
( ğli(s)− g̃li(s) )∣∣∣∣ s∈Iβ . (10)
Note that g̃ li (s) is a linear function, and there is no breakpoints for ğ l i(s) on Iβ . Note also that since ğli(s)− g̃ li (s) is linear on Iβ , the gradient is constant on Iβ . For β ∈ [α], we define a gradient gap: xβ := ∇β −∇β−1, and we have the following estimate with probability at least 1− e−Ω(log 2m):
xβ = Sωβ where ωβ ∼ N (0, 2/m), |S| ≤ logm√ m ‖v‖2. (11)
Note that ωβ is an element of the weight matrix Wl. Thus, {xβ} are independent Gaussian random variables, and∇β is the sum of xβ , that is
∇β = β∑ γ=1 xγ , (β ∈ [α]). (12)
This shows that the gradient ∇β is a “Gaussian random walk” and depends essentially on the number of breakpoints α and the variance of weights 2/m. Using the randomness of Wl and general Hoeffding’s inequality (Vershynin, 2018), we have
P [∣∣∣ β∑ γ=1 Sωγ ∣∣∣ ≤ ε] ≥ 1− e−Ω( m2ε2α‖v‖22 log2m). (13) According to Step 1, the number of breakpoints α is less than or equal to m. Thus, ∇β is bounded by log
2m√ m ‖v‖2 with probability at least 1 − e−Ω(log 2m). Therefore, with the same probability, we have ∣∣ d ds ( ğli(s)− g̃li(s) )∣∣ ≤ logm√ m ‖v‖2, (∀s ∈ [0, 1]). Thus, integrating this inequality from s = 0 to s = 1 shows the estimates of (7) in Lemma 3. Note that the proof of (8) in Lemma 3 is idential to the above proof, except the fact that each entry of B follows from N (0, 2/c) insted of N (0, 2/m). Note that as illustrated in Figure 1, for sufficiently large m, the gradient∇β can be made arbitrarily small, which means that the networks interpolate almost linearly between the data points.

heading: 3.2 PROOF THEOREM 2
text: The purpose of this subsection is to give the proof of Theorem 2. We proceed by induction on the layer l. Note that since g0(x(s)) = Ax(s) is linear and g̃0(s) = g0(x(s)), ğ1(s) is identically equal to g1(x(s)) = W1φ(Ax(s)). Thus, the case l = 1 is true. Assume the theorem holds for any layer l = k, and let us prove it for l = k + 1. Using the triangle inequality, we have∣∣gk+1i (x(s))− g̃k+1i (s)∣∣ ≤ ∣∣gk+1i (x(s))− ğk+1i (s)∣∣+ ∣∣ğk+1i (s)− g̃k+1i (s)∣∣ . (14)
By Proposition 11.3 of (Allen-Zhu et al., 2018b), for any y, ỹ ∈ Rm, there exists a diagonal matrix D ∈ Rm×m such that |Dj,j | ≤ 1 and φ(y) − φ(ỹ) = D(y − ỹ). Thus, for the first term on the RHS, we may write∣∣gk+1i (x(s))− ğk+1i (s)∣∣ = ∣∣∣[Wk+1φ(gk(x(s)))]i − [Wk+1φ(g̃k(s))]i∣∣∣ (15)
= ∣∣[Wk+1D(gk(x(s))− g̃k(s))]
i ∣∣ = ∣∣∣ m∑ ρ=1 [Wk]i,ρDρ,ρ ( gkρ(x(s))− g̃kρ(s) )∣∣∣ (16) ≤ ∥∥gk(x(s))− g̃k(s)∥∥
2 logm√ m . (17)
In the last inequality, we use general Hoeffding’s inequality (Vershynin, 2018), and this inequality holds with probability at least 1 − e−Ω(log2m). 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 f (t)j , we have∣∣∣f (t)j (x(s))− f̃ (t)j (s)∣∣∣ ≤ ∣∣∣f (t)j (x(s))− f̆ (t)j (s)∣∣∣+ ∣∣∣f̆ (t)j (s)− f̃ (t)j (s)∣∣∣ . (18) In a similar way, using the randomness of B (recall each entry of B follows from N (0, 2/c)), with probability at least 1− e−Ω(log2m), we have∣∣∣f (t)j (x(s))− f̆ (t)j (s)∣∣∣ ≤ ∥∥gL(x(s))− g̃L(s)∥∥2√mc logm ≤ O ( log3m√ c ) ‖v‖2. (19)
In the last inequality, we use (7) in Lemma 3. Thus, applying (8) in Lemma 3 to the second term on the RHS of (18) shows the estimates of (6) in Theorem 2. We complete the proof.

heading: 4 GENERALIZATION
text: In this section, considering the mechanism of implicit regularization revealed by random walk analysis, we provide a priori estimates for the generalization performance of over-parameterized deep neural networks, in an l2 regression task on a one-dimensional input-space. Since the network is over-parameterized, the expressive power of the network is rich enough to 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 all training data. We estimate the low complexity of over-parameterized deep networks and show that the error between a trained over-parameterized neural network and the target function can be uniformly bounded by an arbitrarily small positive number.
Setting. We propose a 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 onedimensional regression task on an interval [0, ν] ⊂ R. The training dataset { ( x(i),y(i) ) }i∈[n] 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, ν] → Rc is a C1- class function. This implies that y(i) = f∗(x(i)). Without loss of generality, we may assume that the input data {x(i)}i∈[n] follow a uniform distribution on [0, ν], and after relabeling, we may assume that the data points {x(1), . . . , x(n)} are ordered by index: 0 < x(1) < · · · < x(n) < ν. We define (x(0), y(0)) := (0, f∗(x(0))), (x(n+1), y(n+1)) := (ν, f∗(ν)) and T := supk∈[n+1] ( x(k) − x(k−1) ) . We denote by
f̂ : [0, ν]→ R the linear interpolation of the data points {( x(i), f∗(x(i)) )} i∈[n].
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-parameterized regime. This can be interpreted as the significant expressive power of over-parameterized neural networks is controlled by implicit regularization.
Theorem 4. Suppose f∗(x) is a C1- class function on [0, ν]. Under the same setting as Theorem 1, for δ ∈ (0, 1/2], then with probability at least 1− (δ + e−Ω(log2m)), we have
E(x,y)∼D [ ` ( f (T )(x),y )] ≤ O ( ν2c
n2δ2
) . (20)
Proof sketch of generalization. The purpose of this paragraph is to give an intuitive explanation of the proof of Theorem 4 for one-dimensional output c = 1. All proofs are given in the Supplementary Material.
To estimate E(x,y)∼D [ ` ( f (T )(x), y )] , we evaluate ∥∥f (T )(x)− f∗(x)∥∥ 2 , which we may write as∥∥∥f (T )(x)− f∗(x)∥∥∥ 2 ≤ ∣∣∣f (T )(x)− f̂(x)∣∣∣+ ∣∣∣f̂(x)− f∗(x)∣∣∣ (21)
The first term of the RHS of (21) represents an error between the trained network output f (T )(x) and the piecewise linear function f̂(x). 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 εf(T ) , is small in each interval [x(k−1), x(k)], and hence in each interval [x(k−1), x(k)], the difference between f (T )(x) and f̂(x) falls within the error εf(T ) . This suggests that the network output between adjacent training points is properly controlled by weight initialization and SGD to keep connecting the points almost straight, which results in low complexity of over-parameterized neural networks. This statement can be extended to the interval [0, ν]. Fix ε > 0, and suppose m ≥ Õ ( T 6/ε3 ) . Then with high probability at least 1− e−Ω(log2m), we have
sup x∈[0,ν] ∣∣∣f (T )(x)− f̂(x)∣∣∣ ≤√ε 2
(22)
The second term of RHS of (21) is the error of the piecewise linear approximation of f∗(x) by f̂(x) on the interval [0, ν]. Note that the error can be reduced by increasing n. Hence, for any fixed ε > 0, there exists δ > 0 such that if n ≥ O ( ν√ εδ ) , with probability at least 1 − δ, we have
supx∈[0,ν] |f̂(x)− f∗(x)| ≤ √ ε 2 . Thus, from (21), 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, ν] with probability at least 1− ( e−Ω(log 2m) + δ )
. This gives a priori estimates for the generalization performance of over-parameterized neural networks.

heading: 5 RELATED WORK
text: Implicit regularization in neural networks has recently become an active area of research in machine learning. A number of works have focused on the behavior of gradient descent on overparameterized neural networks (Neyshabur et al., 2014; Lin et al., 2016; Zhang et al., 2016; Soudry et al., 2018; Rahaman et al., 2018). In order to get a handle on implicit regularization in deep neural networks, the majority of theoretical attention has been devoted to linear neural networks (Ji & Telgarsky, 2018; Gidel et al., 2019; Arora et al., 2019a).
Many works try to explain generalization of over-parameterized neural networks. Recent works have shown that on sufficiently over-parameterized 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; AllenZhu 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 be analyzed via NTK and the reproducing kernel Hilbert space (RKHS) (Bietti & Mairal, 2019; Nakkiran et 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 of 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 et al., 2018a;
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).

heading: 6 CONCLUSION
text: In this work, probability estimates for the network output behavior (i.e. random walk analysis) provide a priori generalization estimates for l2 regression problems. We prove that even after training, network gradients between the data points are approximately Gaussian random walks, and the variation of the gradients between the data points is extremely small and depends essentially on the number of breakpoints and the variance of weights. To the best of our knowledge, this paper is 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-parameterized deep neural networks can learn C1- 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.

heading: A PROOFS
text: A.1 PROOF OF LEMMA 3
Lemma 3 (reshown, see §3.1). With probability at least 1−e−Ω(log2m), for every x(p), x(q) (p, q ∈ [n], p 6= q), t ∈ [T ] and l ∈ [L], we have
sup 0≤s≤1 ∣∣∣ğl,(t)i (s)− g̃l,(t)i (s)∣∣∣ ≤ O( log2m√m ) ‖v‖2, (∀i ∈ [m]), (23)
sup 0≤s≤1 ∣∣∣f̆ (t)j (s)− f̃ (t)j (s)∣∣∣ ≤ O( log2m√c ) ‖v‖2, (∀j ∈ [c]). (24)
Proof. We prove Lemma 3 for a fixed l ∈ [L] and t ∈ [T ] every pair of data points x(p), x(q) (p, q ∈ [n], p 6= q), because we can apply union bound at the end.
Recall the definition gl,(t)(x) (the unit output), Gl,(t)(x) (the indicator matrix function) and x(s) = (1−s)x(p) +sx(q), s ∈ [0, 1] (a linearly interpolating path between data points x(p), x(q)), we have
gl,(t)(x(s)) = Wl,(t)Gl−1,(t)(x(s))Wl−1,(t) · · ·W1,(t)G0,(t)(x(s))Ax(s). (25)
Using the definition of g̃ l,(t)(s) and ğ l,(t)(s), we also have
g̃ l,(t)(s) = Wl,(t)Gl−1,(t)(x(0))Wl−1,(t) · · ·W1,(t)G0,(t)(x(0))Ax(s), (26) (27)
ğ l,(t)(s) = Wl,(t)φ(g̃ l−1,(t)(s)) (28)
= Wl,(t)G̃l−1,(t)(s)Wl−1,(t)Gl−2,(t)(x(0))Wl−2,(t) · · ·W1,(t)G0,(t)(x(0))Ax(s), (29)
where G̃l−1,(t)(s) is an indicator diagonal matrix for s ∈ [0, 1] as follows:
[G̃ l−1,(t) (s)]i,i := 1{g̃ l−1,(t)i (s)≥0}, [G̃ l−1,(t) (s)]i,j := 0 (i 6= j). (30)
We begin by proving that the number of breakpoints of the function ğ l,(t)i (s) in the interval [0.1] is bounded by m. For fixed i ∈ [m], we have
ğ l,(t) i (s) = [W l,(t)φ(g̃ l−1,(t)(s))]i (31)
= m∑ j=1 [Wl,(t)]i,j φ(g̃ l−1,(t) j (s)) (32)
= m∑ j=1 [Wl,(t)]i,j g̃ l−1,(t) j (s)1 { g̃ l−1,(t) j (s)≥0
} (33) Note that the input to the above φ, that is g̃ l−1,(t)j (s), is a linear function on s ∈ [0, 1]. For each j ∈ [m], the linear equation g̃ l−1,(t)j (s) = 0 has at most one solution s = s∗.5 If the solution s = s∗ satisfies inequality 0 < s∗ < 1, then ğ l,(t)i (s) has a breakpoint at s = s ∗. This shows that the number of breakpoints of ğ l,(t)i (s) is bounded by the number of the linear equations
g̃ l−1,(t) j (s) = 0 (j ∈ [m]), (34)
which is clearly equal to m.
We denote by 0 < s1 < s2 < · · · < sα < 1 all breakpoints of ğ l,(t)i (s), where α is the number of breakpoints. For notational simplicity, we set s0 = 0 and sα+1 = 1. Note that, with probability 1,
5Otherwise, the linear function is identically zero (i.e. g̃ l−1,(t)j (s) ≡ 0), which does not affect the number of breakpoints.
breakpoints are all distinct from each other. Each breakpoint sβ (β ∈ [α]) corresponds to a linear equation g̃ l−1,(t)j (s) = 0 for some j ∈ [m]. In other words, for each breakpoint sβ (β ∈ [α]), there exists a unique element j ∈ [m] such that g̃ l−1,(t)j (s) = 0. Therefore, for s = sβ , we set j = jβ (β ∈ [α]) then we have g̃ l−1,(t)jβ (sβ) = 0.
It is easy to verify ddsx(s) = x (q) − x(p) =: v. Therefore,
d
ds g̃ l,(t)(s) = Wl,(t)Gl−1,(t)(x(0))Wl−1,(t)Gl−2,(t)(x(0))Wl−2,(t) · · ·W1,(t)G0,(t)(x(0))Av,
(35) d
ds ğ l,(t)(s) = Wl,(t)G̃l−1,(t)(s)Wl−1,(t)Gl−2,(t)(x(0))Wl−2,(t) · · ·W1,(t)G0,(t)(x(0))Av.
(36)
This implies,
d ds ğ l,(t)(s)− d ds g̃ l,(t)(s) (37)
= Wl,(t) ( G̃l−1,(t)(s)−Gl−1,(t)(x(0)) ) Wl−1,(t)Gl−2,(t)(x(0)) · · ·W1,(t)G0,(t)(x(0))Av.
(38)
Note that from the definition of the indicator matrix, [Gl−1,(t)(x(0))]i,i = 1{[gl−1,(t)(x(0))]i≥0}, and from the definition of the linear approximation, g̃ l−1,(t)(0) = gl−1,(t)(x(0)), which says that G̃l−1,(t)(0) equals Gl−1,(t)(x(0)).
For each i ∈ [m], we may write
d
ds ğ l,(t) i (s)−
d
ds g̃ l,(t) i (s) = m∑ j=1 [Wl,(t)]i,j [M(t)v]j λ̃j , (39)
where M(t) is a matrix:
M(t) := Wl−1,(t)Gl−2,(t)(x(0))Wl−2,(t) · · ·W1,(t)G0,(t)(x(0))A (40)
and λ̃j is the difference of indicator functions: λ̃j := 1{g̃ l−1,(t)j (s)≥0} − 1{g̃ l−1,(t)j (0)≥0}. (41) For β ∈ [α], we set an open interval of breakpoints Iβ := (sβ , sβ+1), and recall the notation of the gradient∇β
∇β := d
ds
( ğ l,(t) i (s)− g̃ l,(t) i (s) )∣∣∣∣ s∈Iβ , (42)
and the gradient gap xβ := ∇β −∇β−1. Note that since there is not a breakpoint in Iβ , the gradient ∇β is constant in Iβ . Hence, for β ∈ [α] and s ∈ Iβ , we may write
d
ds ğ l,(t) i (s)−
d
ds g̃ l,(t) i (s) = β∑ γ=1 xγ . (43)
Note that the gradient gap xγ (γ ∈ [α]) can be rewritten as
xγ = [Wl,(t)]ijγ [M (t)v]jγ ζ̃γ , (44)
where ζ̃γ is a difference of indicator functions:
ζ̃γ := 1{g̃ l−1,(t)jγ (dγ)≥0} − 1{g̃ l−1,(t)jγ (dγ−1)≥0}, ∀ dγ−1 ∈ Iγ−1 and ∀ dγ ∈ Iγ . (45)
Note that ζ̃γ is independent of the choice of dγ−1 and dγ . Note also that since the linear function g̃ l−1,(t) jγ (s) switches the sign at s = sγ , we have ζ̃γ = ±1.
We begin by proving the upper bound on ∑β γ=1 xγ . For notational simplicity, we use W
l to denote Wl,(0), and for l ∈ [L] we set
dWl := Wl,(t) −Wl,(0) = Wl,(t) −Wl, (46)
then we may write for γ ∈ [α],
[M(t)v]jγ = [W l−1,(t)Gl−2,(t)(x(0))Wl−2,(t) · · ·W1,(t)G0,(t)(x(0))Av]jγ (47)
= m∑ ρ=1 [Wl−1,(t)]jγ ,ρ[Nv]ρ (48)
= m∑ ρ=1 [Wl−1]jγ ,ρ[Nv]ρ + m∑ ρ=1 [dWl−1]jγ ,ρ[Nv]ρ (49)
=: hγ + dhγ , (50)
where N := Gl−2,(t)(x(0))Wl−2,(t) · · ·W1,(t)G0,(t)(x(0))A. Therefore, we have
xγ = ζ̃γ [Wl,(t)]i,jγ [M (t)v]jγ (51) = ζ̃γ ( [Wl]i,jγ + [dW l]i,jγ ) ( hγ + dhγ ) (52)
= ζ̃γ [W l]i,jγhγ + ζ̃γ [dW l]i,jγhγ + ζ̃γ [W l]i,jγdhγ + ζ̃γ [dW l]i,jγdhγ (53)
=: x(0)γ + x (1) γ + x (2) γ + x (3) γ . (54)
In order to estimate Nv, we use the following estimate (see Lemma 7.1 and Claim 11.2 in (AllenZhu et al., 2018b)): Lemma. If ε ∈ (0, 1], with probability at least 1 − e−Ω(mε2/L), for a fixed vector z and l ∈ [L], we have
‖Gl,(t)(x(0))Wl,(t) · · ·W1,(t)G0,(t)(x(0))Az‖2 ≤ (1 + ε)‖z‖2. (55)
This Lemma implies that with probability at least 1− e−Ω(m/L), we have
‖Nv‖2 = ‖Gl−2,(t)(x(0))Wl−2,(t) · · ·W1,(t)G0,(t)(x(0))Av‖2 ≤ 2‖v‖2. (56)
We will estimate the 1st term x(0)γ . Conditioning on this event (56) happens, using the randomness of Wl−1 and general Hoeffding’s inequality (Vershynin, 2018), for each fixed vector v, we have
P {|hγ | > τ} ≤ 2 exp ( − Cτ 2
(2/m)‖Nv‖22
) . (57)
Choose τ := logm√ m ‖Nv‖2. Then, with probability at least 1− e−Ω(log 2m), we have
|hγ | ≤ logm√ m ‖Nv‖2. (58)
We set u(0)γ := ζ̃γhγ and u(0) = (u (0) 1 , . . . , u (0) β ). Note that since ζ̃γ = ±1, we have ∣∣∣u(0)γ ∣∣∣ =∣∣∣ζ̃γhγ∣∣∣ ≤ logm√m ‖Nv‖2. The set of the gradient gaps {x(0)γ } = {u(0)γ [Wl]i,jγ} are a sequence of independent Gaussian random variables. Hence, ∑β γ=1 x (0) γ is a “Gaussian random walk” (12). Thus, using the randomness of Wl, conditioning on the above event (58), fixing any v, with probability at
least 1− e−Ω(log2m), we have∣∣∣∣∣ β∑ γ=1 x(0)γ ∣∣∣∣∣ ≤ logm√m ‖u(0)‖2 (59) ≤ logm√
m ( β∑ γ=1 ( logm√ m ‖Nv‖2 )2)1/2 (60)
≤ 2 log 2m√ m ‖v‖2. (61)
Therefore, we have the estimate of x(0)γ .
Next, we will estimate the 2nd term x(1)γ . By definition, we may write
β∑ γ=1 x(1)γ = β∑ γ=1 ζ̃γ [dWl]i,jγhγ . (62)
Note that we use Theorem 1 (the convergence theorem) to write
‖[dWl]i‖2 = ‖[Wl,(t)]i − [Wl]i‖2 ≤ O ( λ logm
m
) . (63)
Thus, applying the estimate of hγ to eq. (58), we have∣∣∣∣∣ β∑ γ=1 x(1)γ ∣∣∣∣∣ ≤ 2 β∑ γ=1 ( logm√ m ‖v‖2 ) [dWl]i,jγ (64)
≤ logm√ m ‖v‖2 ·
√ β ‖[dWl]i‖2 (65)
≤ Cλ log 2m
m ‖v‖2 ≤ log2m√ m ‖v‖2. (66)
The last inequality uses λ ≤ o( √ m), which is indicated by the result of Theorem 1, therefore we have the estimate of x(1)γ .
Next, we will estimate the 3rd term x(2)γ . By definition, we may write
β∑ γ=1 x(2)γ = β∑ γ=1 ζ̃γ [W l]i,jγdhγ . (67)
We set u(2)γ := ζ̃γdhγ and u(2) := (u (2) 1 , . . . , u (2) β ). Using the randomness of W l and general Hoeffding’s inequality (Vershynin, 2018), for each fixed vector v, we have
P {∣∣∣∣∣ β∑ γ=1 u(2)γ [W l]i,jγ ∣∣∣∣∣ > τ } ≤ 2 exp ( − Cτ 2 ‖u(2)‖22 max2γ ‖[Wl]i,jγ‖ψ2 ) (68)
≤ 2 exp ( − Cmτ 2
2‖u(2)‖22
) (69)
Note that
dhγ = m∑ ρ=1 [dWl−1]jγ ,ρ[Nv]ρ, (70)
and choose τ := logm√ m ‖u(2)‖2, with probability 1− e−Ω(log 2m), we have
∣∣∣∣∣ β∑ γ=1 x(2)γ ∣∣∣∣∣ ≤ logm√m ‖u(2)‖2 ≤ logm√m  β∑ γ=1 ( m∑ ρ=1 [dWl−1]jγ ,ρ[Nv]ρ )2 1/2
(71)
≤ logm√ m ( β∑ γ=1 ‖[dWl−1]jγ‖22‖v‖22 )1/2 ≤ logm√ m ‖dWl−1‖F ‖v‖2 (72)
≤ log 2m√ m ‖v‖2. (73)
The last inequality uses λ ≤ o( √ m) and the result of Theorem 1:
‖dWl−1‖F = ‖Wl−1,(t) −Wl−1‖F ≤ O ( λ
logm√ m
) . (74)
Therefore, we have the estimate of x(2)γ .
Next, we will estimate the last term x(3)γ . Note that since ζ̃γ = ±1, we have |ζ̃γ | = 1, and conditioning on this event (56) happens, we may write∣∣∣∣∣ β∑ γ=1 x(3)γ ∣∣∣∣∣ = ∣∣∣∣∣ β∑ γ=1 ζ̃γ [dWl]i,jγdhγ
∣∣∣∣∣ (75) ≤ ‖[dWl]i‖2
 β∑ γ=1 ( m∑ ρ=1 [dWl−1]jγ ,ρ[Nv]ρ )2 1/2
(76)
≤ ‖[dWl]i‖2 ( β∑ γ=1 ‖[dWl−1]jγ‖22‖v‖22 )1/2 (77)
≤ ‖[dWl]i‖2‖dWl−1‖F ‖v‖2 ≤ log2m√
m ‖v‖2. (78)
Putting this all together, with probability 1− e−Ω(log2m), we have∣∣∣∣ dds ğ li (s)− dds g̃ li (s) ∣∣∣∣ = ∣∣∣∣∣ β∑ γ=1 xγ ∣∣∣∣∣ ≤ 4 log2m√m ‖v‖2. (79) Therefore, we have ∣∣ğ li (s)− g̃ li (s)∣∣ ≤∫ s
0
∣∣∣∣ dds ğ li (s)− dds g̃ li (s) ∣∣∣∣ ds (80)
≤ 4s log 2m√ m ‖v‖2 (0 ≤ ∀s ≤ 1). (81)
This finishes the proof of (7) in Lemma 3. Finally, the proof of (8) in Lemma 3 is idential to the above proof, except the fact that each entry of B follows from N (0, 2/c) insted of N (0, 2/m). We complete the proof.
A.2 PROOF OF GENERALIZATION THEOREM
Theorem 2 (reshown, see §3). Under the same setting as Theorem 1, with probability at least 1 − e−Ω(log2m), for every x(p), x(q) (p, q ∈ [n] p 6= q), t ∈ [T ], l ∈ [L], i ∈ [m] and j ∈ [c], we
have
sup 0≤s≤1
∣∣∣gl,(t)i (x(s))− g̃l,(t)i (s)∣∣∣ ≤ O ( loglm√ m ) ‖v‖2, (82)
sup 0≤s≤1
∣∣∣f (t)j (x(s))− f̃ (t)j (s)∣∣∣ ≤ O ( logL+1m√ c ) ‖v‖2. (83)
In order to give provable guarantees for the generalization performance of over-parameterized deep networks in the l2 regression task on the one-dimensional input-space, we apply the above Theorem 2 to bound the error between the trained network output f (T )(x) and the piecewise linear function f̂(x). Note that if we apply Theorem 1 to this case (one-dimensional models), simple preprocessing is needed: It just consider a mapping [0, ν]→ S1+ (a half circle).
S1+ = {x = (x1, x2) ∈ R2 : ‖x‖2 = 1, x2 ≥ 1}
It is apparent that there exists a C∞ diffeomorphism from [0, ν] to S1+. Under this setting, the input from S1+ 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 = 1 but the case of d = 3 in Theorem 1. Lemma 5. Under the same setting as Theorem 1 and 2, for δ ∈ (0, 1/2], then with probability at least 1− (δ + e−Ω(log2m)), we have
sup x∈[0,ν]
∣∣∣f (T )j (x)− f̂j(x)∣∣∣ ≤ O ( logL+1m
m1/6 · ν nδ
) . (84)
Proof. Without loss of generality, we may assume that the entry of the weight matrix Bi,j ∼ N (0, 2/c), where c = Θ ( m1/3 ) .6
For k ∈ [n+ 1], we denote by |Ik| the length of the interval Ik = [ x(k−1), x(k) ] . We set c = c = m1/3 in Theorem 2, with probability at least 1− e−Ω(log2m), we have
sup x∈Ik ∣∣∣f (T )j (x)− f̃ (T )j (x)∣∣∣ ≤ Cj logL+1mm1/6 ( sup k∈[n+1] ∣∣∣x(k) − x(k−1)∣∣∣) = Cj logL+1m m1/6 T (85)
where Cj is a constant, and T := supk∈[n+1] ∣∣x(k) − x(k−1)∣∣. Here we set ε := Cj logL+1mm1/6 T .
Note that f (T )j (x (k−1)) = f̂j(x (k−1)) and f (T )j (x (k)) = f̂j(x (k)), by eq. (85) we have∣∣∣f̃ (T )j (x(k−1))− f̂j(x(k−1))∣∣∣ ≤ ε and ∣∣∣f̃ (T )j (x(k))− f̂j(x(k))∣∣∣ ≤ ε. (86) Note that the piecewise linear function f̂j linearly connects ( x(k−1), f̂j(x (k−1)) )
and( x(k), f̂j(x (k)) ) . Thus, the following inequality holds.
sup x∈Ik ∣∣∣f̃ (T )j (x)− f̂j(x)∣∣∣ ≤ ε (87) We use eq. (85) and eq. (87) to see that
sup x∈Ik ∣∣∣f (T )j (x)− f̂j(x)∣∣∣ ≤ sup x∈Ik ∣∣∣f (T )j (x)− f̃ (T )j (x)∣∣∣+ sup x∈Ik ∣∣∣f̃ (T )j (x)− f̂j(x)∣∣∣ ≤ 2ε. (88) Note that ε is not dependent on k. Thus, we have
sup x∈[0,ν] ∣∣∣f (T )j (x)− f̂j(x)∣∣∣ ≤ 2ε. (89) 6 For each output y = (y1, y2, · · · , yc), an additional coordinates (yc+1, yc+2, . . . , yc) = (0, 0, . . . , 0) can
always be padded to the output. We did not try hard to improve the exponent 1/3.
Next, we evaluate T = supk∈[n+1] ∣∣x(k) − x(k−1)∣∣ . Recall that the training dataset {x(k)}k∈[n] is generated from the uniform distribution in the interval [0, ν]. We denote by µ := n/ν the density of training samples. In this setting, it is well known that for every r > 0 (r < ν), the number of training samples in the interval [0, r] follows the Poisson distribution with mean µr, then the sequence of inter-sample distances is independent and identically distributed exponential random variables having mean 1/µ (= νn ) (Daley & Vere-Jones, 2007). Define ∆ to be the above exponential distribution having mean ν/n, which is the inter-sample distance. Then, using Markov’s inequality, for τ > 0, we have
P[∆ ≥ τ ] ≤ E[∆] τ = ν nτ . (90)
Thus, we can choose τ := νnτ , which implies that with probability at least 1− δ, we have
T ≤ ν nδ . (91)
Combining this with eq. (89), with probability at least 1− (δ + e−Ω(log2m)), we have
sup x∈[0,ν] ∣∣∣f (T )j (x)− f̂j(x)∣∣∣ ≤ 2Cj logL+1mm1/6 T ≤ 2Cj logL+1mm1/6 νnδ . (92) We complete the proof of the Lemma 5.
Lemma 6. Suppose f∗j (x) is a C1- class function on [0, ν] and f̂j(x) is the linear interpolation of the data points {( x(i), f∗j (x (i)) )} i∈[n]. For δ ∈ (0, 1/2], with probability at least 1− δ, we have
sup x∈[0,ν] ∣∣∣f̂j(x)− f∗j (x)∣∣∣ ≤ O ( νnδ) . (93) Proof. We use f∗′j (x) to denote the first derivative of f ∗ j (x). Since f ∗ j is a C
1- class function on the compact set [0, ν], f∗′j is a bounded function. Thus, we can define S(k) and S as follows:
S(k) := sup x∈Ik ∣∣f∗′j (x)∣∣ , S := sup k∈[n+1] S(k). (94)
Since f∗j (x) and f̂j(x) are continuous functions, there exists h (k) (0 ≤ h(k) ≤ x(k)−x(k−1)) such that sup x∈Ik ∣∣∣f∗j (x)− f̂j(x)∣∣∣ = ∣∣∣f∗j (x(k−1) + hk)− f̂j(x(k−1) + hk)∣∣∣ . (95) By the mean value theorem, there exists a real number c(k) ∈ Ik such that,
f̂j(x (k−1) + h(k)) = f∗′j (c (k))h(k) + f∗j (x (k−1)). (96)
Note that by the definition of f̂j , we have f∗j (x (k−1)) = f̂j(x (k−1)), therefore, we also have that∣∣∣f∗j (x(k−1) + h(k))− f̂j(x(k−1) + h(k))∣∣∣ = ∣∣∣f∗j (x(k−1) + h(k))− f∗j (x(k−1))− f∗′j (c(k))h(k)∣∣∣ (97)
≤ ∫ x(k−1)+h(k) x(k−1) ∣∣∣f∗′j (x)− f∗′j (c(k))∣∣∣ dx (98) ≤ 2h(k)S(k). (99)
By considering whole interval [0, ν], we have
sup x∈[0,ν] ∣∣∣f̂j(x)− f∗j (x)∣∣∣ = sup k∈[n+1] ( sup x∈Ik ∣∣∣f∗j (x)− f̂j(x)∣∣∣) ≤ 2T S (100) Now we apply the estimate of T from eq. (91). We may therefore rewrite eq. (100) as
sup x∈[0,ν] ∣∣∣f̂j(x)− f∗j (x)∣∣∣ ≤ O ( νnδ) . (101) We complete the proof of Lemma 6.
Proof of Theorem 4 (Generalization)
Proof. From eq. (89) and eq. (93), with probability at least 1− (δ+ e−Ω(log2m)), we have for every j = 1, 2, · · · , c, ∣∣∣f (T )j (x)− f∗j (x)∣∣∣ ≤ ∣∣∣f (T )j (x)− f̂j(x)∣∣∣+ ∣∣∣f̂j(x)− f∗j (x)∣∣∣
≤ Cj ν
nδ
( 1 + logL+1m
m1/6
) (∀x ∈ [0, ν]).
Using the triangle inequality, this gives
` ( f
(T ) j (x), y
) = 1
2 ∥∥∥f (T )(x)− f∗(x)∥∥∥2 2 = 1 2 c∑ j=1 ∥∥∥f (T )j (x)− f∗j (x)∥∥∥2
≤ 1 2 C ′2c
ν2
n2δ2
( 1 + logL+1m
m1/6
)2 (∀x ∈ [0, ν]).
where C ′ := maxj=1,··· ,c Cj .
Thus, we have the following estimate: With probability at least 1− (δ + e−Ω(log2m)), we have
E(x,y)∼D [ ` ( f (T )(x), y )] = 1
ν ∫ ν 0 1 2 ∥∥∥f (T )(x)− f∗(x)∥∥∥2 dx (102) ≤ 1
2 C ′2c
ν2
n2δ2
( 1 + logL+1m
m1/6
)2 . (103)
We complete the proof.

Review summaries:
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.