We study the least-square regression problem with a two-layer fully-connected neural network, with ReLU activation function, trained by gradient flow. Our first result is a generalization result, that requires no assumptions on the underlying regression function or the noise other than that they are bounded. We operate in the neural tangent kernel regime, and our generalization result is developed via a decomposition of the excess risk into estimation and approximation errors, viewing gradient flow as an implicit regularizer. This decomposition in the context of neural networks is a novel perspective of gradient descent, and helps us avoid uniform convergence traps. In this work, we also establish that under the same setting, the trained network overfits to the data. Together, these results, establishes the first result on benign overfitting for finite-width ReLU networks for arbitrary regression functions.
Figures & tables
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Analytical
Sampled Weights
Network
n/a
fW:Rd→R
fW(x)=m1a⋅ϕ(Wx)
Network evaluation
n/a
fW∈Rn
fW=(fW(x1),...,fW(xn))⊺
Noise variable
n/a
ξW=y−fW(x):Ω→R
Noise vector
n/a
ξW=y−fW∈Rn
Appendix
Table 1: Our main notations. Bold symbols indicate evaluation on the samples {(xi,yi)}i=1n and the subscript W denotes dependence on the weights {wj}j=1m .
Population Trajectory
Empirical Trajectory
Network
ft=fW(t)
f^t=fW^(t)
Network Evaluation
ft=fW(t)
f^t=fW^(t)
Noise Function
ξt=ξW(t)
ξ^t=ξW^(t)
Noise vector
ξt=ξW(t)
ξ^t=ξW^(t)
Error function
ζt=ζW(t)
ζ^t=ζW^(t)
Error vector
ζt=ζW(t)
ζ^t=ζW^(t)
Appendix
Table 2: Objects from Section C.4 with time-dependence in gradient flow. As clear from the table entries, dependence on W(t) and W^(t) are denoted by subscript t and introduction of ^ for conciseness.
Top L eigenfunctions
Remaining eigenfunctions
Network
ftL=∑l=1L⟨ft,φl⟩2φl
f~tL=∑l=L+1∞⟨ft,φl⟩2φl
Error function
ζtL=∑l=1L⟨ζt,φl⟩2φl
ζ~tL=∑l=L+1∞⟨ζt,φl⟩2φl
Squared norm of
∥ζtL∥22=∑l=1L⟨ζt,φl⟩22
∥ζ~tL∥22=∑l=L+1∞⟨ζt,φl⟩22
error function
Gradient function
GtL=∇WftL
G~tL=∇Wf~tL
=∑l=1L⟨Gt,φl⟩2φl
=∑l=L+1∞⟨Gt,φl⟩2φl
Appendix
Table 3: Objects from Sections C.3 and C.4 that are projected onto different eigenspaces. The superscript L without ~ denotes that a function is projected onto the subspace of L2(ρd−1) spanned by the first L eigenfunctions of H , and ~ denotes that a function is projected onto the subspace of L2(ρd−1) spanned by all but the first L eigenfunctions of H .
Figure 1: In the third picture, the shaded region represents Gx,x′d=Hxd∩Hx′d , and thus contain those w such that gx,x′(w)=ϕ′(x⋅w)ϕ′(w⋅x′)=1 .
Figure 2: In the third picture, the regions of Sd−1 shaded in red are contained in Hwj(0)d△Hwj(t)d , and thus contain those x such that 1{ϕ′(wj(0)⋅x)=ϕ′(wj(t)⋅x)} .
Figure 3: Largest acute angle between wj(0) and wj(t) given a bound on ∥wj(0)−wj(t)∥2 .