Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes
Authors: Dan Qiao
Kaiqi Zhang
Esha Singh
Daniel Soudry
Yu-Xiang Wang
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Generalization bound
minima stability
gradient descent
large learning rate
ReLU neural network
Primary area: optimization_for_deep_networks
TL;DR: We present a new theory of generalization for local minima that gradient descent with a constant learning rate can stably converge to.

Abstract: We study the generalization of two-layer ReLU neural networks in a univariate nonparametric regression problem with noisy labels. This is a problem where kernels (\emph{e.g.} NTK) are provably sub-optimal and benign overfitting does not happen, thus disqualifying existing theory for interpolating (0-loss, global optimal) solutions. We present a new theory of generalization for local minima that gradient descent with a constant learning rate can \emph{stably} converge to.  We show that gradient descent with a fixed learning rate $\eta$ can only find local minima that represent smooth functions with a certain weighted \emph{first order total variation} bounded by $1/\eta - 1/2 + \widetilde{O}(\sigma + \sqrt{\mathrm{MSE}})$ where $\sigma$ is the label noise level, $\mathrm{MSE}$ is short for mean squared error against the ground truth, and $\widetilde{O}(\cdot)$ hides a logarithmic factor. Under mild assumptions, we also prove a nearly-optimal MSE bound of $\widetilde{O}(n^{-4/5})$  within the strict interior of the support of the $n$ data points. Our theoretical results are validated by extensive simulation that demonstrates large learning rate training induces sparse linear spline fits. To the best of our knowledge, we are the first to obtain generalization bound via minima stability in the non-interpolation case and the first to show ReLU NNs without regularization can achieve near-optimal rates in nonparametric regression.

Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes
Dan Qiao
Kaiqi Zhang CS, UC Santa Barbara kzzhngg0@ucsb. edu
Esha Singh CSE, UC San Diego
CSE, UC San Diego
d2qiaoluesd.co edu
e3singh@uesd. edu
Daniel Soudry
Yu-Xiang Wang
Technion Israel Institute of Technology
Halıcoğlu Data Science Institute, UC San Diego
daniel.. soudry@gmail... com
yuxiangv@uced. edu
Abstract
We study the generalization of two-layer ReLU neural networks in a univariate nonparametric regression problem with noisy labels. This is a problem where kernels (e.g. NTK) are provably sub-optimal and benign overfitting does not happen, thus disqualifying existing theory for interpolating (O-loss, global optimal) solutions. We present a new theory of generalization for local minima that gradient descent with constant learning rate can stably converge to. We show that gradient descent with a fixed learning rate y) can only find local minima that represent smooth functions with certain weighted first order total variation bounded by 1/1 1/2 + Ö(σ + /MSE) where the label noise level, MSE short for mean squared error against the ground truth, and Ö(.) hides a logarithmic factor. Under mild assumptions, we also prove nearly-optimal MSE bound of Ö(n (4/5) within the strict interior the support of the n data points. Our theoretical results are validated by extensive simulation that demonstrates large learning rate training induces sparse linear spline fits. To the best of our knowledge, we are the first obtain generalization bound via minima stability in the non-interpolation case and the first to show ReLU NNs without regularization can achieve near-optimal rates in nonparametric regression.
1 Introduction
How do gradient descent-trained neural networks work? an intriguing question that depends on model architecture, data distri- bution, and optimization algorithms used for training [Zhang et al., 2021]. Specifically, in the overparameterizee regime with specific random initialization of the weights, it was shown that gradient de- scent finds global optimal (0-loss or interpolating) solutions despite the non-convex objective function [Jacot et al., 2018, Du et al.. 2018, Liu al., 2022]. It was also shown that among the (many) global op- timal solutions, the particular solutions that are selected by gradient descent often do not overfit despite having training error [Chizat et al., 2019, Arora et al., 2019, Mei et al., 2019], sometimes even the data is noisy - phenomenon known as "benign overfitting" [e.g., Belkin et al., 2019, Bartlett et al., 2020, Frei et al., 2022).
functions representable by Two-Layer ReLU NN
GD with small 7
Interpolating
GD with
Solutions
large y
Statie Minuine
noioy")
Braigg
unee uneefiniig
"Pidgr Stabiity
Figure 1: We show that "Large step size selects simple func- tions that generalize."
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

GD trtairadd ReLU step
upper Ama(Hlessian)
Loss and MSE different
10
0.35
fraring unstn - 2 (h0
13-
Nezin - 2000 Fool
0.25
0.20
0.5
0.15
True Functoo
10"
Meedl Hessian)
9=0.01
1/g 12 4 o- VRSE
-05
Notsy Labels
order Total Variation 16t
0.05
-04
-0.
0.0
0.2
0.4
10
107 10
Mn
Figure 2: Empirical evidence of our claim. Constant step size gradient descent-trained two-layer ReLU neural networks generalize because of minima stability. The left panel shows that with increasing step size, gradient descent finds smoother solutions (linear splines) with a smaller number of knots. The middle panel illustrates our theoretical result with numerically accurate upper bound using 1/n + Q(1) of the curvature and TV1 -compleexx of the smooth solution. The right panel shows that tuning 7) gives the classical U-shape bias-variance tradeoff for overparameterized NN.
What is less well-known is that interpolating solutions do overfit for ReLU neural networks (ranging from tempered to catastrophic) [Mallinar et al., 2022, Joshi et al., 2023, Haas al., 2023] and the generalization bounds in the kernel regime are provably suboptimal for certain univariate nonpara- metric regression problems [Suzuki, 2018, Zhang and Wang, 2022]. These "exceptions" significantly limit the abilities of the kernel theory or "benign overfitting" theory in predicting the performance of an overparameterrized neural network in practice.
In many learning problems with noisy data, the best solutions are simply not among those that interpolate the data. For example, no interpolating solutions can be consistent in a fixed-design nonparametric regression problem. Even interpolating solutions that satisfy benign overfitting can be found, they could be undesirable due their "spikiness" [Haas et al., 2023] and lack of robustness [Hao and Zhang, 2024]. In addition, it was reported that when the label is noisy, it takes much longer for gradient descent overfit [Zhang et al., 2021]. Most practical NN training would have entered the Edge-of-Stane -fttbbiiiyy regime [Cohen et al., 2020] or stopped before the interpolation regime kicks in.
These observations motivate to up with alternative theory for descent training of overparameterized neural networks that do not require interpolation.
1.1 Summary of Contributions
In this paper, we present a new theory of generalization for solutions that gradient descent (GD) with a fixed learning rate can stably converge to. Specifically:
1. We show that for ID nonparametric regression (n data points with noisy labels), the solutions that GD can stably converge to must be regular functions with small (weighted) first-order total variation (Theorem 4.1 and Corollary 4.2), thus promoting sparsity in the number of linear pieces. This generalizes the result of Mulayoff et al. [2021] by removing the "interpolation" assumption. We also show that in the noisy case, there is no "flat" interpolating solution and gradient descent cannot converge to them unless the learning rate is O(1/n² no matter how overparameterized the two-layer ReLU network is (Theorem 3.
2.
We show that such solutions (stable local minima that GD converges to) cannot overfit, in the sense that the generalization gap vanishes as n - oo inside the strict interior of the data support (Theorem 4.3). Moreover, under mild additional assumption on gradient descent finding solutions with training loss smaller than o², we prove that these solutions achieve near-oplimal rate for estimating (the strict interior of) first-order bounded variation functions (Theorem 4.4) provably faster than any kernel ridge regression estimators, including neural networks in the "kernel" regime.
We conduct extensive numerical experiments to demonstrate our theoretical predictions, validate our technical assumptions, and illustrate the functional form of the ReLU NNs as well as the

---

learned basis functions that gradient descent finds with different step sizes. These results reveal new insights into how gradient descent training aggressively learns representation and induces implicit sparsity.
To the best of our knowledge, these results are new to this paper. We emphasize that (1) the training objective function is not explicitly regularized: (2) we do not early-stop training in favor of algorithmic-stabilin and (3) the solutions that gradient descent converges to are not global optimal (interpolating) solutions unless the label noise O. Our approach is new in that we directly analyze the complexity of superset of solutions that gradient descent can stably converge to, which enables us to prove end-to-end generalization bounds that are near-optimal in nonparametris regression tasks.
Our analysis for gradient descent-training is categorically different from those in the "kernel" k.. "lazy") regime about interpolating solutions. Instead, we rigorously prove (and empirically demon- strate) that large step-size gradient descent do not behave this way and it does not converge to interpolating solutions. Our results fall into the non-kernel regime of neural network learning known as the "rich" (a.k.a. the "feature learning" or "sparse") regime [Chizat et al., 2019, Woodworth et al., 2020], in which the weights and biases can move arbitrarily far away from their initialization.
Technical novelty. The main technical innovation in our analysis is in handling the ! E, x fo(z;)) V (Ix)) term that arises in the minima stability analysis when it was previously handled by Mulayoff et al. [2021] using interpolation, i.e., yi = f(x,) V i E [n). It turns out in the noisy-lahel case, we can decompose the term into a certain Gaussian complexity measure and a self-bounding style MSE of that fe. A non-trivial step to bound the largest eigenvalue of V (-) by a constant which results in a uniform bound of both the Gaussian complexity and the MSE. These bounds themselves are vacuous in terms of the implied generalization error, but plugging them into the function- space constraint imposed by the noisy minima stability bound restricts the learned ReLU NN to be inside a weighted TVI function class (Details in Theorem 4.. This, in turn, allows us to amplisy a vacuous MSE bound into a new MSE bound that is nearly optimal in the strict interior of the data support. The main technique in the last step involves bounding the metric entropy of the weighted TV1 class and then carefully working out a self-bounding (square loss) version of the Dudley's 's chaining argument [Wainwright, 2019].
Disclaimers and limitations. It is important to note that while we analyze gradient descent training of overparameterized neural networks, the computational claim very different from those in the kernel regime. The analysis in the kernel regime ensures that gradient descent finds interpolating solutions efficiently. We do not have a comparable efficiency claim. While computational guarantees on stationary point (and local minima) convergence in non-convex optimization problems are well- understood [Ghadimi and Lan. 2013, Jin et al., 2017], we do not have guarantees on whether the solution that gradient descent finds satisfies our assumption on the training loss being ""optimized" (smaller than label noise r²). Instead, our results provide a generalization gap bound for any stable solutions (Theorem 4.3) and a near-optimal excess risk (MSE vs ground truth) bound (Theorem 4.4) when the solution that GD finds happens to satisfy the assumption (empirically it does!). This is a meaningful middle ground between classical learning theory which does not concern optimization at all and modern theory that is fully apiimization-depedeeen
While we focus on (full batch) gradient descent for a clean presentation, the minima stability for stochastic gradient descent is immediate under the stochastic definition of minima stability [Mulayoff et al., 2021]. The same reason applies to us focusing on univariate nonparametric regression. Our technique can be used to generalize the multivariate function space interpretation of minima stability from Nacson et al. [2022] to the noisy case, but it will take substantial effort to formalize the corresponding generalization bounds in the multivariate case, which we leave as a future work.
1.2 Related Work and Implications of Our Results
Generalization in Overparameterizeed NNs, Interpolation, and Benign Overfitting. Most existing theoretical work on understanding the generalization of overparameterized neural networks focuses on the interpolation regime [Cao and Gu, 2019, Frei et al., 2022, Kou et al., 2023, Buzaglo et al., 2024]. Handling label noise either requires explicit regularization [Hu et al., 2020, Zhang and Wang. 2022], algorithmic stability through early stopping [Hardt et al., 2016, Richards and Kuzborskij, 2021], or carefully crafted data distribution that leads to a phenomenon known as benign overfitting [Bartlett et al., 2020, Frei et al., 2022, Kou et al., 2023]. Benign overfitting could happen for nonparametric
3

---

good solution regression tasks [Belkin et al., 2019], but there is well-documented empirical and theoretical evidence that benign overfitting does not oceur for regression tasks with ReLU activation [Mallinar al.. 2022, Haas et al., 2023, Joshi et al., 2023] and that the excess risk is required to be proportional to the standard deviation of the label noise [Kornowski et al., 2024]. We are the first to go beyond the interpolation regime and show that gradient descent-traines neural networks generalize in noisy regression tasks without explicit regularization.
Implicit bias of gradient descent. The implicit bias of gradient descent training of overparameterized NN is well-studied. It was shown that among the many globally optimal (interpolating) solutions, gradient descent finds the ones with the smallest norm in certain Hilbert spaces [Arora et al., 2019, Mei et al., 2019], classifiers with largest- margin [Chizat and Bach, 2020], or the smoothest cubic spline interpolation [Jin and Montúfar, 2023]. None of these results, however, imply generalization bounds when the labels are noisy. Interestingly, our results show that gradient descent with large step size induces an implicit bias that resembles sparse I.1 --regullarzzttin rather than the dense 1.2 regularization from gradient flow [Jin and Montúfar, 2023].
Implicit bias of minima stability. The closest to our work is the line of work on the implicit bias of minima stability [Ma and Ying, 2021, Mulayoff et al., 2021, Wu and Su, 2023]. We build directly on top of the function-space interpretation of minima stability established by Mulayoff et al. [2021]. However. these works critically rely on the minima interpolating the data, which makes their results inapplicable to settings with label noise. Mulayoff et al. [2021] also did not establish formal generalization bounds. Ma and Ying [2021]. Wu and Su [2023] do have generalization bounds, but (again) their results require interpolation and thus do not apply to our settings.
Flat/Sharp Mínima and generalization. Our work is also connected the body of work the hy- pothesis that "flat local minima generalize better". Despite compelling empirical evidence [Hochreiter and Schmidhuber, 1997, Keskar et al., 2017], rigorous theoretical understanding of this hypothesis is still lacking [see, e.g., Wu and Su, 2023, and the references therein]. Our work contributes to this literature by formally proving that the hypothesis is real for two-layer ReLU NNs in noisy regression task.
Edge-of-Stability and Catapults. Empirical observations how large learning rate training of NN finds solutions with Hessian's is largest eigenvalue dancing around 2/1,, i.e., "edge of stability" regime [Cohen et al., 2020]; and that the loss may go up first before going down ("catapult") [Lewkowycz et al., 2020]. Existing theoretical understanding of these curious behaviors of GD training is still limited to toy-scale settings (e.g.. Arora et al. [2022], Ahn et al. [2023], Kreisler et al. (2023]). Our work is complementary in that we provide generalization bound to the final solution GD stabilizes on no matter how GD gets there. Outside the context of GD and neural networks, "edge of stability" and the implicit bias of large step-size were observed for forward stagewise regression [see, e.g. Tibshirani, 2015, 2014, Section 4.4 and Page 42] albeit only empirically. Our results may provide a theoretical handle in formally analyzing these observations.
Optimal rates of NNs in nonparametric regression. Finally, it was previously known that neural networks can achieve optimal rates for estimating TV1 functions [Suzuki, 2016 8, Liu et al., 2021, Parhi and Nowak, 2021, Zhang and Wang, 2022]. Specifically, Savarese et al. [2019], Ongie et al. [2020], Parhi and Nowak [, Zhang and Wang [2022] show that weight decay in ReLU networks connected to total variation regularization. However, these works assume one can solve an appropriately constrained or regularized empirical risk minimization problem. Our work is the first to show that the optimal rate is achievable with gradient descent without weight decay. In fact, it was pleasant surprise to us that both weight decay and large learning rate induce total variation- implicit regularization in the function space.
2 Notations and Problem Setup
Let us set up the problem formally. Throughout the paper, we use 0(+), Q(-) to absorb constants while Ö(-) suppresses logarithmic factors. Meanwhile, [n] = (1,,, ... ..))
Two-layer neural network. We consider two-layer (i.e. one-hidden-laye llyer) univariate ReLU networks,
( /R: {(x) = w Φ w
*
F F=
Σ
(2)
(1) x + +100)) 0f0) + ((2)
i=1
4

---

where the network consists of & hidden neurons and 6(-) denotes the ReLU activation function.
Training data and loss function. The training dataset is denoted by D {(rre, ) IR x IR, E [+]]- {xi)i=1 is assumed to be supported by [- TTaxx Fmax] for some constant Tmaax > 0. We focus on regression problems with square loss E(f, (z, 8)) = {f(()) y)². The training loss is defined as 2n Σ (f(z;) - y:)². Notice that f is parameterized by 0 [wisk: (1)) "isk b(2) E RR+++1 As a short hand, we define ((()) == {(e. (# 1²)) and (()) == #. ExEM) (0).
L(F) 1
Gradient descent. We focus on the Gradient descent (GD) learner, which iteratively updates A:
02+1 10-00170 V). L 0,
where v) > O the step size a.a learning rate) and 0g the initial parameter. Detailed calculation of gradient for two-layer ReLU networks is deferred to Appendix E. Below we define stability for local minima and discuss the conditions for a minimum to be stable.
Twice differentiable stable local minima. Similar to Mulayoff et al. [2021], we consider twice differentiable minima. According to Taylor's expansion around twice differentiable minimum #*,
2 - - (00)0 0*),
(()) R _(0)) + (0 "'''"""'"""""""""""""""" +
(3)
where V denotes the Hessian matrix and V=((0) = 0. Therefore, as 0r gets close to 0*, the update rule for GD (2) can be approximated as 0.+1 R 0- (VC((*) - (20( , 0*)). Such approximation motivates the definition of linear stability, which is first stated in Wu et al. [2018].
Definition 2.1 (Linear stability). With the update rule 0.+1 0,-n (VC(0*)= V=L(0)) (0; 0*)). a twice differentiable local minimum 0r of L said to be e linearly stable if for any 0g in the e-ball (0*), it holds that lim sup; 100, 0*l| S E.
Note that different from previous works [Wu et al., 2018, Mulayoff et al., 2021]. we remove the expectation before ||0, - 0* since under GD everything is deterministic. Intuitively speaking, linear from 8", we end up staying in the e-ball
stability requires that once we have arrived at a distance (f*). It is known that linear stability is connected to the flatness of the local minima.
Lemma 2.2. Consider the update rule in Definition for any > 0, local minimum 6* is an linearly stable minimum of L if and only if >max V(²)(()) "7"
The implication is that the set of stable minima is equivalent to the set of flat local minima whose largest eigenvalue of Hessian is smaller than 2/n. The proof is adapted from Mulayoff et al. [2021] and we state the proof Appendix for completeness. When the result does not depend on e (as above), we simply say "linearly stable". Throughout the paper, we overload the notation by calling function f fe linearly stable function 0 is linearly stable.
"Edge of Stability" regime. Extensive empirical and theoretical evidence (Cohen et al. [2020], Damian et al. [2024], and see Section 1.2) have shown that the threshold of linear stability (from Lemma 2.2) is quite significant in GD dynamics: GD iterations initially tend to exhibit "progressive sharpening" where Amax ( (V2 ((9,) is increasing, until finally GD reaches the "Edge of Stability", where Amax ((),)) == 2/n. We capture this phenomenon with the following definition.
Definition 2.3 (Below Edge of Stability). We say that a sequence of parameters {0t generated by gradient descent with step-size 7) is c-approximately there exists t* > 0 such that Amax ( 2 ((0))) < 2e for all t 2 t'. Any 0, with 2 t* is referred to as c- BBoS solution.
(BEoS) for >> 0 if
9
The BEoS regime provides a strong justification for the connection between the step size 7 and the largest eigenvalue of the Hessian matrix. It holds for all drice-differentiable solutions GD finds along the way - even if the GD does not converge to (local or global) minimum. Empirically, BEoS is valid for both the "progressive sharpening" phase and the oscillating EoS phase for small constant e.
Our goal this paper is to understand generalization for both (twice differentiable) stable local minima (Definition 2.1) and any other solutions satisfying e-BEoS (Definition 2.3), which are both subsets of
F(n, e, D) = {oo Amax V V²C(0)) <
2e
(4)
1
5

---

To simplify the presentation, we focus on the case with c = 0 w.l.o.g.' ! and unless otherwise specified, a "stable solution" refers to an element of F(n, D) in the remainder of the paper.
For the data generation process, we will consider two settings of interest: (1) the fixed design nonparametric regression setting (with noisy labels) (2) the agnostic statistical learning setting. They have different data assumptions and performance metrics to capture "generalization".
Nonparametric Regression with Noisy labels. In this setting, we assume fixed input " ... In and y/: = (z+) E for i E [m], where fo IR + R is the ground-truth (target) function and { are independent Gaussian noises (0, a) Our goal is find a ReLU NN using the dataset to minimize the mean squared error (MSE):
MSE(f) 1 " n Σ fo(=))
It is nonparametric because we do not require fo be described by smaller number of parameters, but rather satisfy certain regularity conditions. Specifically, we focus on estimating target functions inside the first order bounded variation class
So E (B, = {1= [ Fmax, Tmax]
max [xx)] S B, / I5" S Ci CoJ.
- IR.
-Emax
where f" denotes the second-orde order weak derivative of f and we define a short hand TV (maae (3))) |r., which we refer to as the TV(1) (semi)norm of f throughout the paper. We refer readers to a recent paper [Hu et al.. 2022, Section 1.2] for the historical importance and the challenges in estimating the BV functions. The complexity of such function class is discussed in Appendix D.
Agnostic statistical learning and generalization gap. In this setting, we assume the n data points {(rs, [= are drawn i.i.d. from an unknown distribution P defined on | -mmax Fmnax] x [-D, D]. The expected performance on new data points called "Risk", R(f) (e (f (x. u))] We define the absolute difference between training loss and the risk:
Gen(f) = GeneralizationGap((1 = [R(() L())-
We say that f generalizes if GeneralizationGaap(() + as n - oo with high probability.
3 Stable Solutions Cannot Interpolate Noisy Labels
A large portion of previous works studying minima stability assume the learned function interpolates the data. However, for various optimization problems, it is unclear whether there exists such an interpolating solution that is stable, especially when the number of samples n becomes large.
For the nonparametric regression problem with noisy labels, design example where any interpolating function can not be stable. Before presenting the example, we first define the function, which will be the weight function of the weighted TV(!) norm throughout the paper: for
Tmaxx mm g(x) min(g (z). (z)} with
g (x) p²(x < x) X|X < x1 [X < x))²
(6)
g (xx) pa(X > x) - x|X > x 2 (E|X) > x))²
where X is drawn from the empirical distribution of the data (a sample chosen uniformly from {zz}).
For various distributions of training data (e.g. Gaussian distribution, uniform distribution), most of g's mass is located at the center while y decays towards the extreme data points. The same g(x) is also applied as the weight function in Mulayoff et al. [2021]. where they derived an upper bound - [ff (z)))))) S lating. We generalize the same upper bound to all stable solutions in F(1,, 0, D) as in Theorem C.2. Below we construct a counter-example, where we can prove a contradicting lower bound of S Suuu (x))))9(zz)) dx for any interpolating f. thus disproving the assumption of interpolation.
assuming f is linearly stable (Definition 2.1) and interpo-
Counter-example. We fix x, 2rmard (n+1)aams for E [n]] and fo(x) = 0 for any æ, which implies that y 's are independent random variables from (0)
'To handle the when > 0, just replace n with -e in all bounds in the remainder of the paper.

---

Theorem 3.1. For the counter-example, with probability 1 - 6, for any interpolating function f,
(=")))a(z)dz= = 22 on n 24 log ())
(7)
where the randomness comes from the noises {Gi)- Under this high-probability event, when n. ? (v o log (t)) any stable solution f for GD with step size 1j will not interpolate the data, i.e.
2
F(n. O, D) f(x:)
yis V E [m]] = 0.
(8)
The proof of Theorem 3.1 deferred to Appendix due to space limit. This result, together with Mulayoff et al. [2021, Theorem 1]. implies that gradient descent cannot converge interpolating solutions unless 17 = O(1/n)). It also implies (when combined with Theorem 4.1) an intriguing geometric insight that all eiccreifferee interpolating solutions must be very sharp, i.e., its largest eigenvalue is larger than 2(n²) (see details in Appendix J Moreover, we highlight that the conclusion of Theorem 3.1 is consistent with our observation in Figure 2(a), where the learned function tends to be smoother and would not interpolate the data as 1j becomes larger. Therefore, in the following discussion, we consider the case without assuming interpolation.
4 Main Results
In this section, we present the main results about stable solutions for GD (functions F(1, O, D)) from three aspects. Section 4.1 describes the implicit bias of stable solutions of gradient descent with large learning rate in the function space. Section 4.2 and 4.3 derive concrete generalization bounds that leverage the implicit biases in the distribution--fee statistical learning setting and the non-parametric regnession setting respectively. An outline of the proof of our main theorems is given in Appendix B. The full proof details are deferred to the appendix.
4.1 Implicit Bias of Stable Solutions in the Function Space
We begin with characterizing the stable solutions for GD with step size 17 without the assumption of interpolation (there can be E [n] such that fxx) * y:). Similar to the interpolating case, the learned stable function enjoys (weighted) (V))) bound as below.
Theorem 4.1. For a function f = fo where the training (square) loss L is twice differentiable at 0,
BRax If" (()))(()))r===) s Amax (V.C(()
1 + xmaxx /2L(0).
(9)
2
2
where g(x) is defined as (6). Moreover, if we assume y: fu(x;) + G, for independent noise & NNO, 0²), then with probability 5 where the randomness is over the noises {
Amaz A (ViC(0)
TT min (1./A)
(())))((z)d
+ 2
+ Tmaa MSE.(f). (10)
2
In addition, f fo is stable solution of GD with step size n on dataset D, i.e fo E F(n.0,
as in (4), then we can replace Amazx (V)C()) with 7
in (9) and (10).
Theorem 4.1, which prove in Appendix G. associates the local curvature of the loss landscape at 0 with the smoothness of the function fo it represents measured in weighted TV()) norm. In short, it says that flat solutions are simple. The result is a strict generalization of Theorem 1 in Mulayoff et al. [2021] which requires interpolation, i.e., L()) 0. Observe that the number of neurons k does not appear in (9) and have no effect in (10) when > n, thus the result applies to arbitrarily overparameterized two-layer NNs. Under the standard nonparametric regression assumption, (10) is a stronger bound that asymptotically matches the bound under interpolation [Mulayoff et al., 2021, Theorem I] when & = o(n) and MSE(Ja) = o(1) as the number of data points - co.
Another interesting observation when combining (10) with Theorem 3.1 is that for interpolating solutions (observe that MSE(ff) = Ō w.h.p.)
Amax (()) 2(n²o) Ō(a).
W...o.g. assume that Fmax 2 1. If this does not hold, can directly replace Tmax in the bounds by 1.
7

---

To say it differently, all interpolating solutions are very sharp minima when the labels are noisy. This provides theoretical explanation of the empirical observation that noisy labels are harder to overfit using gradient training [Zhang et al., 2021].
Note that we leave the term (()) (or MSE(f) in the TV bound. Therefore, we can plug any upper bound for these terms into Theorem 4.1 for a concrete result, and below we instantiate the TV(1) bound with crude MSE bound under the assumption that f is "optimized".
Corollary 4.2. In the nonparametric regression problem with ground-truth function fo. for a stable solution fo of GD with step size y where L is twice differentiable at 8, assume that is optimized, i.e, the empirical loss of f is smaller than fo: 2n Li=1 (f(xz) - -y:)² - -. (fo(zz) -ya)² then with probability 1 - 8, the function I satisfies
(f)()))(z)d
I
7 + Ô (oTmax),
(11)
Tmaa
where the randomness is over the noises {ee} and O suppresses logarithmic terms of n, 1/5.
The assumption of optimized f is rather mild since, in practice, gradient-based optimizers commonly quite effective in loss minimization (see also our experiments). With such assumption, we can derive an MSE upper bound (with high probability) of order Ō(o²) (details in Lemma G.5), and thus the (V) bound above.
In some cases, we can decrease the MSE upper bound we assumed in Corollary 4.2, and use this to improve the resulting TV(1) bound (11). For instance, if the neural network is ander-parameterizen (i.e. l is smaller than nt), in Appendix G.2 we derive a (high-probabilityy) bound for MSE of order Ökk/n,, which implies that the last term in (11) becomes Ö v /k/n). The term vanishes if n/k is large enough, where the TV()) bound reduces to the noiseless and interpolating case.
4.2
GD on ReLU NN Does Not Overfit
Why would anyone care about the function space implications of stable solutions? The next theorem shows that these solutions cannot overfit (in the strict interior of the data support) without making strong assumptions on the shape of the data distribution.
Theorem 4.3. Let P be a joint distribution of (I. y) supported on [ [-Tmaxe Fmax x [-D, D). Assume the dataset ~ Pn i.i.d. For any fixed interval I C I-I Tmmax] and a universal constant e > such that with probability 1 - 5/2. g(x) 2 for all x E I. if the function f == fo is a stable solution of GD with step size such that C is twice differentiable at 0 and [[ < D, with probability 1 - (randomness over the dataset), the generalization gap restricted to I satisfies
Genz(f) = Br [(f(x)) -)
1 Σ (f(.)) va)² 50 ZLEZ
D3
Zmax
2 2:E D
(12)
where Ey means that (x. y) is new sample from the data distribution conditioned on I and nz is the number of data points in D such that x; E I.
The proof of Theorem 4.3 is deferred to Appendix H. Briefly speaking, we show that in the strict interior of the data support, the generalization gap will vanish the number of data points increases. This vanishing generalization gap further implies that the expected performance on new data points is close to the (observable) training loss, i.e., the output stable solutions do not overfit.
Regarding our assumptions, in addition to standard boundedness assumptions, we focus on the strict interior of the domain where g be lower bounded (i.e. interval Z). This is because for extreme data points, (xx) decays and thus imposes little constraint on the output function f. In Appendix H.I, we show that if the marginal distribution of x is the uniform distribution on [-I Tmaax), when
is sufficiently large, I can be chosen as 3 incorporates large portion of the data points and n = (n)). More illustrations about the choice of I under various data distributions deferred to Appendix H.2.
2imax
2xmax] In this case, with high probability, I
8

---

Meanwhile, the generalization gap bound has dependence 1 on the learning rate Therefore, we increase the learning rate (in reasonable range), the learned stable solution tends to be smoother, which further implies better generalization performances.
"
4.3 GD on ReLU NN Achieves Optimal Rate for Estimating (V(1) Functions
Finally, zoom into the nonparametric regression task that we described in Section 2 where J1.'. In are fixed and the noisy labels yi = fo, + (0, σ²) independently for i E [n] for a ground truth function fo in the first order bounded variation class (see Section 2 for details). Similar to Theorem 4.3, we focus on the strict interior I of [-Tmax: Tmax]] but instead of a generalization gap bound, prove MSE bound against fo on I that nearly matches the theoretical limit.
Theorem 4.4. Under the same conditions in Corollary 4.2, for any interval I C I-Immax Tmax and a universal constant с > such that g(x) 2 c for all x E and f is optimized over I, i.e. (f,er(((z;) y:)² Ezzez((f(aa)
ya)², if the output stable solution @ satisfies ||0]| S p (for some constant p > 0) and the ground truth fo E (kp? 1 1,00, + dTmma)), then with probability 1 6 (over the random noises (Gi)), the function fo satisfies
MSE (f) =
(f(x) - fo(x,)) 5o
((
0²2
Fiax
+ ox )).
$
(13)
11
17
Z:ET.
where ni is the number of data points in D such that T; I.
The proof of Theorem 4.4 is deferred to Appendix I. Below we discuss some interesting aspects of the result. First of all, Theorem 4.4 focuses In this way, we ignore the extreme data points and derive an MSE upper bound (restricted to Z) of order Ō(zz 4/55, which matches the minimax optimal rate for estimating BV()) functions [see, e.g.. Donoho and Johnstone, 1998, Theorem 1]. In contrast, it is well-known that neural networks in the kernel regime (and any other "linear smoothers") must incur strictly suboptimal worst-case MSE Q(uz -2/3) [Donoho et al., 1990, Suzuki, 2018). According to the discussions in Appendix H.I, if the data follows uniform distribution, the interval I can incorporate most of the data points where ng ((n).
interval I where g(x) can be lower bounded.
Mcanwhile, the MSE bound has dependence 2/55 on the learning rate 17. Such dependence is because with larger learning rate, the learned function f will have smaller TV(2) bound, and therefore the set of possible outpur functions will contain fewer non-smooth functions, which implies a tighter MSE bound. However, this does not mean that a larger learning rate is always better. When 7 is too large, GD may diverge, and even if it does not, the set of stable solutions cannot approximate the ground truth fo well if assumption. In our experiments,
1 (z) > en + dimmas, thus failing to satisfy the "optimized" verify the "'optimized" assumption numerically for wide range of 1) and demonstrate that by tuning learning rate 17, are adapting to the unknown TV() (fo)-
Zmax -
Lastly, we remark that Theorem 4.4 holds for arbitrary k. even the neural network is heavily over-paree wer-paaraeterizeed (k >> n). The dependence 7) + d'Emaxx on 17 results from the TV()) bound in Corollary 4.2, where the term will dominate if 1) o'max" which is the case if the step size is not large. Furthermore, if T. is sufficiently large, we improve the (V()) bound in Corollary 4.2 as in Appendix G.2, and improve the mean squared emror MSEx(f) to Ō
Pmaa
accordingly.
The assumptions and detailed statements for the improved MSE are deferred to Appendix I.I.
5 Experiments
In this section, we empirically validate our claims by training a two-layer fully connected neural network with ReLU activation using gradient descent (GD) with varying step sizes. We focus on fitting a mildly overparameterizee ReLU network to a simple nonparametric regression problem. The input dataset comprises of 30 equally spaced fixed design points {ara } where each x; E [-0.5, 0.5] (n = 30). Label y = fo(z))+N d²) with o = 0.5 and fo(z) (2x+ 1)1(x < -- +2 0).

---

Trained RelU NN with g-0.4
Learning Curvec G-04
Learned basid functions Igwe..4)
LOG5
15 buth
1.0
10P
0.5
0.0
Fundian
0.2
50
159
150
202
290
0.0
Trained ReLU NN n-0.01
Learring Ourves: go0.01
Learned functions (y=e0,
Furctin
1.5
Firse funciin
haley Leccl
2.5
1.0
Fined week
0.5-
Lett
1.0
-05
-2.4
-0.2
0.0
0.2 0.4
Telatorshh 1660)
-0.4 -0.2 0.0 0.2 0.4
Figure 3: Highlights of our numerical simulation for large step size (1= = 0.4, first row) and small
step size (1) = 0.01, second row) gradient descent training univariate ReLU NN with n = 30 noisy observations and k = 100 hidden neurons. From left to right, the three columns illustrate (a) Trained NN function (b) Learning curves (c) Learned basis functions (each of the 100 neurons).
The two-layer ReLU network is parameterized by 0 (see Section with k = 100 neurons per layer. The network uses standard parameterization (scale factor of 1) and parameters are initialized randomly (see Figure 7 for the initial basis functions).
Figure 2 (in the introduction) illustrates how changing the learning rate affects the learned ReLU NN that GD-training stabilizes The main take-aways are (a) large learning rate learns flatter minima which represent more regular functions (in TV()); (b) Our bound from Theorem 1 is a very accurate description of the curvature of the Hessian as well as a valid upper bound of the TV(1) (pseudo) norm; (c) When we tune learning rate 1). it is implicitly regularizing the complexity, which provides satisfying variance tradeoff explanation to how GD-training works.
Figure provides further details on the learning curves and representation learning. We note that the learned representation is very different from the initialization, thus our experiments are clearly describing phenomena not covered by the "kernel" regime. In addition, it seems that all solutions that GD finds after small number of iterations satisfy the "optimized" assumption as required in Theorem 4.4. In the appendix (Figure 8), we provide empirical justification for the other assumption we make about the wiice-iiferentiaabiity of the solutions. More experiments can be found in the appendix with more learning rate choices, as well as discussion on the catastrophic and tempered overfitting of interpolating solutions when we adjust k.
6 Conclusion
In this paper, we took new look into how gradient descent-trained two-layer ReLU neural networks generalize from a lens of minima stability (and the closely related Edge-of-Stabilit phenomena). We focused on univariate inputs with noisy labels and showed GD with typical choice of learning rate cannot interpolate the data. We also established that local smoothness of the training loss functions implies a first order total variation constraint on the function the neural network represents,
hence proving that all such solutions have vanishing generalization gap inside the strict interior of the data support. In addition, under mild assumption, we prove that these stable solutions achieve near-optimal rate for estimating first-order bounded variation functions. Future work includes generalization beyond 1D input, two-hidden layers, and understanding the choice of optimization algorithms.
10

---

Acknowledgments
The research is partially supported by NSF #2134214. DQ KZ, ES and YW's work was partially completed while they were with the Department of Computer Science at UCSB. The research of DS was Funded by the European Union (ERC, A-B-C-Deep. 101039436). Views and opinions expressed are however those of the author only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency (ERCEA). Neither the European Union nor the granting authority can be held responsible for them. DS also acknowledges the support of the Schmidt Career Advancement Chair in AI.
References
Kwangjun Ahn, Sébastien Bubeck, Sinho Chewi, Yin Tat Lee, Felipe Suarez, and Yi Zhang. Learning threshold neurons via edge of stability. Advances in Neural Information Processing Systems, 36, 2023.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on the edge of stability in deep learning. In International Conference on Machine Learning, pages -024. PMLR, 2022.
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117745))30063--0077 2020.
Mikhail Belkin, Alexander Rakhlin, and Alexandre Tsybakov. Does data interpolation contradict statistical optimality? ? In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1611-1619, PMLR, 2019.
Gon Buzaglo, Itamar Harel, Mor Shpigel Nacson, Alon Brutzkus, Nathan Srebro, and Daniel Soudry. How uniform random weights induce non-uniform bias: Typical interpolating neural networks generalize with narrow teachers. In International Conference on Machine Learning. 2024.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
Herman Chernoff. A measure of asymptotic efficiency for tests of hypothesis based the sum of observations. The Annals of Mathematical Statistics, pages 493-507, 1952.
Lenaic Chizat and Francis Bach. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. In Conference on learning theory, pages 1305-1338. PMLR, 2020.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training differentiable programming. Advances in neural information processing systems, 32, 2019.
Jeremy Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations, 2020.
Alex Damian, Eshaan Nichani, and Jason D Lee. Self-stabilizztion:: The implicit bias of gradient descent at the edge of stability. In International Conference on Learning Representations, 2024.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
Ronald A DeVore and George G Lorentz. Constructive approximation, volume 303. Springer Science & Business Media, 1993.
David I. Donoho and lain M Johnstone. Minimax estimation via wavelet shrinkage. The annals of Statistics, 26(3):879-99) 1998.

---

David L Donoho, Richard C Liu, and Brenda MacGibbon. Minimax risk over hyperrectangles, and implications. The Annals of Statisties, pages 1416-1437, 1990.
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes wwer-parameterized neural networks. In International Conference on Learning Representations. 2018.
David Eric Edmunds and Hans Triebel. Function spaces, entropy numbers, differential operators. (No Title), 1996.
Spencer Frei, Niladri S Chatterji, and Peter Bartlett, Benign overfitting without linearity: Neural network classifiers trained by gradient descent for noisy linear data. In Conference on Learning Theory, pages 2668-2703. PMLR, 2022.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):2341-236) 2013.
Moritz Haas. David Holzmüller, Ulrike Luxburg, and Ingo Steinwart. Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension. Advances in Neural Information Processing Systems, 36, 2023.
Yifan Hao and Tong Zhang. The surprising harmfulness of benign overfitting for adversarial robustness. arXiv preprint arXiv:2401.122368 2024.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference machine learning, pages 1225-1234. PMLR, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9(1::1-42, 1997.
Addison J Hu, Alden Green, and Ryan J Tibshirani. The voronoigram: Minimax estimation of bounded variation functions from scattered data. arXiv preprint arXiv:2212.44514 2022.
Wei Hu, Zhiyuan Li, and Dingli Yu. Simple and effective regularization methods for training on noisily labeled data with generalization guarantee. In International Conference on Learning Representations, 2020.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How escape saddle points efficiently. In International conference on machine learning, pages 1724-1732. PMLR, 2017.
Hui Jin and Guido Montúfar. Implicit bias of gradient descent for mean squared error regression with two-layer wide neural networks. Journal of Machine Learning Research, 24(137):1-97, 2023.
Nirmit Joshi, Gal Vardi, and Nathan Srebro. Noisy interpolation learning with shallow univariate relu networks. In International Conference on Learning Representations, 2023.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
Guy Kornowski, Gilad Yehudai, and Ohad Shamir. From tempered benign overfitting in relu neural networks. Advances in Neural Information Processing Systems, 36, 2024.
Yiwen Kou, Zixiang Chen, Yuanzhou Chen, and Quanquan Gu. Benign overfitting in two-layer relu convolutional neural networks. In International Conference on Machine Learning, pages 17615-17659, PMLR, 2023.
Itai Kreisler, Mor Shpigel Nacson, Daniel Soudry, and Yair Carmon. Gradient descent monotonically decreases the sharpness of gradient flow solutions in scalar networks and beyond. International Conference Machine Learning, pages 17684-17744, PMLR, 2023.
12

---

Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning; the catapult mechanism. arXiv preprint arXiv:2003.02218. 2020.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over-parameterizee non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59: 85-116, 2022.
Hao Liu, Minshuo Chen, Tuo Zhao, and Wenjing Liao. Besov function approximation and binary classification on low-dimensions manifolds using convolutional residual networks. In International Conference on Machine Learning, pages 6770-6780. PMLR, 2021.
Chao Ma and Lexing Ying. On linear stability of sgd and input-smoothness of neural networks. Advances in Neural Information Processing Systems, 34: 14:16805-168 2021.
Neil Mallinar, James Simon, Amirhesam Abedsoltan, Parthe Pandit, Misha Belkin, and Preetum Nakkiran. Benign, tempered, or catastrophic: Toward refined taxonomy of overfitting Advances in Neural Information Processing Systems, 35:1 1118--1995, 2022.
Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, pages 2388-2464. PMLR, 2019.
Rotem Mulayoff, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability: A view from function space. Advances in Neural Information Processing Systems, 11117779-1776111 2021.
Mor Shpigel Nacson, Rotem Mulayoff, Greg Ongie, Tomer Michaeli, and Daniel Soudry. The implicit bias of minima stability in multivariate shallow relu networks. In The Eleventh International Conference on Learning Representations, 2022.
Richard Nickl and Benedikt M Pötscher. Bracketing metric entropy rates and empirical central limit theorems for function classes of besov-and sobolev-type. Journal of Theoretical Probability, 20: 177-199, 2007.
Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro. A function space view of bounded norm infinite width relu nets: The multivariate case. In ICLR, 2020.
Rahul Parhi and Robert D Nowak. Banach space representer theorems for neural networks and ridge splines. Journal of Machine Learning Research, 22(43):1-40, 2021.
Dan Qiao and Yu-Xiang Wang. Near-optimal deployment efficiency in reward-free reinforcement learning with linear function approximation. In The Eleventh International Conference on Learning Representations, 2023a.
Dan Qiao and Yu-Xiang Wang. Near-optimal differentially private reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9914-9940. PMLR, 2023b.
Dan Qiao and Yu-Xiang Wang. Offline reinforcement learning with differential privacy. Advances in Neural Information Processing Systems, 36, 2023c.
Dan Qiao and Yu-Xiang Wang. Near-optimal reinforcement learning with self-play under adaptivity constraints. In International Conference on Machine Learning. 2024.
Dan Qiao, Ming Yin, Ming Min, and Yu-Xiang Wang. Sample-efficient reinforcement learning with loglog (t) switching cost. In International Conference on Machine Learning, pages 18031-18061. PMLR, 2022.
Dan Qiao, Ming Yin, and Yu-Xiang Wang. Logarithmic switching cost in reinforcement learning beyond linear mdps. arXiv preprint arXiv:2302. 12456, 2023.
Dominic Richards and Ilja Kuzborskij. Stability & generalisation of gradient descent for shallow neural networks without the neural tangent kernel. Advances neural information processing systems, -621,,9-8621, 2021.
13

---

Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro. How do infinite width bounded norm networks look in function space? In Conference on Learning Theory, pages 2667-2690. PMLR, 2019.
Karthik Sridharan. A gentle introduction to concentration inequalities. Dept. Comput. Sci., Cornell Univ. Tech. Rep, 2002.
Taiji Suzuki. Adaptivity of deep relu network for learning in besov and mixed smooth besov spaces: optimal rate and curse of dimensionality. arXiv preprint arXiv:///0008033. 2018.
Ryan Tibshirani. Fast stagewise algorithms for approximate regularization paths. https://www.
stat. berkeley. adu/"ryant /ttps/ttslls/ttttssseeeeeeeeeeee pdf, 2014.
Ryan J Tibshirani. A general framework for fast stagewise algorithms. J. Mach. Learn. Res., 16(1):
2543-2588, 2015.
Martin Wainwright. Hiigh-dimensional statistics; non-asymptotic viewpoint, volume 48, Cam- bridge university press, 2019.
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference Learning Theory, pages 3635-3673. PMLR, 2020.
Lei Wu and Weijie J Su. The implicit regularization of dynamical stability in stochastic gradient descent. In International Conference on Machine Learning, pages 37656-37684, PMLR, 2023,
Lei Wu, Chao Ma, and Weinan E. How sgd selects the global minima in over-parameterized learning: dynamical stability perspective. Advances Neural Information Processing Systems, 31, 2018.
Jianyu Xu, Dan Qiao, and Yu-Xiang Wang. Doubly fair dynamic pricing. International Conference on Artificial Intelligence and Statistics, pages 9941-9975. PMLR, 2023.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Kaiqi Zhang and Yu-Xiang Wang. Deep learning meets nonparametric regression: Are weight- decayed dnns locally adaptive? In International Conference on Learning Representations, 2022.
Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. Differentially private linear sketches: Efficient implementations and applications. Advances in Neural Information Processing Systems, 35: 12691-1217704 2022.
14

---

A Full Experimental Results
A.1
Stable Minima GD Converges and Learning Curves
Trained ReLU NN with 7 0.5
Learning Curves: n=
True Function
train Loss
Fitted function
MSE truth
Noisy Labels
Fitted Labels
Loss
10
0.5
-0.5
25
50
75
100
125
150
175
200
-0.4
-0.2
0.0
0.2
0.4
Iterations (In 100s)
Trained ReLU NN with 0.4
Learning Curves: z 0.4
train Loss
1.5
10a
Loss
0.0
True Function
Fitted function
10-1_
Noisy Labels
-0.5
Fitted tabels
50
100
150
200
250
-0.4
-0.2
0.2
Iterations (in 100s)
Trained ReLU NN with 0.
Learning Curves: 0=
train
MSE truth
10a.
1.0
Loss
True Function
10:1_
Fitted function
-0.5
Noisy
Fitted
100
150
200
250
300
-0.4
-0.2
0.0
0.2
0.4
Iterationn (In
Trained ReLU NN with y= 0-2.2
Learning Curves: n= 0.2
10a
train Loss
1.5
MSE vs truth
Loss
0.0
Function Fitted function
Noisy Labels
Fitted Labels
-1.0
100
300
500
-0.4
0.22
0.0
0.2
0.4
Iterations (in 100s)
Figure 4: Illustration of the solutions gradient descent with learning rate converges to (Part D), As decreases, the fitted function goes from simple complex. Any line below the x² line satisfies the "optimized" assumption from Corollary 4.2 and Theorem 4.4.
15

---

Trained ReLU NN with 0.
Learning Curves: n=
1.5
Loss
10-1
0.0
True Function
Fitted function
train Loss
MSE vs truth
Noisy Labels
-0.5
Fitted Labels
200
600
1000
-0.4
-0.2
Iterations (in 100s)
Trained ReLU NN with n 0.05
Learning Curves: 0.0.05
Fitted function
Noisy Labels
1.0
Fitted Labels
Loos
10-1
train Loss
-0.5
250
500
750
1000 1250
1500 1750 2000
-0.4
-0.2
0.2
Iterations (in 100s)
Trained ReLU NN with 0=0.02 0.02
Learning Curves: n=0.02
True Function
Filled function
Noisy Labels
1.0
Fitted Labels
0.5
10-1
train Loss
MSE truth
1000
3000
5000
-0.4
-0.2
0.0
0.2
0.4
Iterations (In 1005)
Trained ReLU NN with z= 0.01
Learning Curves: n=0.01
True Function Fitted function
Noisy Labels
Fitted Labels
LOBS
10-1
train Loss
MSE truth
d²
-0.5
4000
8000
10000
-0.4
-0.2
0.0
0.2
0.4
Iteratians (in 100s)
Figure 5: Illustration of the solutions gradient descent with learning rate converges to (Part II), As 7 decreases further, the fitted function starts to overfit to the noisy label.
A.2 Interpolating Solutions as the Number of Hidden Neurons Increases
In this section, we illustrate sequence of interpolating solutions that are the global optimal solutions, which is also the kernel limit in the "lazy" regime. The results obtained by randomly initializing
16

---

the weights, but solve the minimum norm solution by directly solving the least square problem (optimizing only the second layer weights.)
Interpolating Solution
Interpolating Solution
Funittion
1.5
Functtio Fitted function Labels
Fitee fanction
Noisy Labels
Fitted Labels
Fitted Labels
0.5
0.5
-0.5
-0.5
0.4
-0.4
0.0
0.2
Interpolating Solution
Interpolating
1.5
1.5
Fitted function
Fitted function
Noisy
Notsy
Fitted Labels
Fited Labels
0.5
0.5
-0.5
-0.5
-0.4
0.4
0.0
Interpolating Solution
500
Interpolating Solution = 1000
1.5
Furction Fitted function
1.5
True
Fitee functior
Noisy Labels
Noisy Labels
Fitted Labels
Fitted Labels
0.5
0.5
-0.5
-0.5
-0.4
0.4
0.0
Figure 6: Examples of global optimal (interpolating) solutions (fitting only second layer weights). Notice that the number of data points 30. When the model is barely able interpolate (k: 30), the fitted function experiences the catastrophic overfitting. When the number of neurons k increases the interpolation solution becomes smoother and enters the tempered overfitting regime.
17

---

A.3
Representation Learning of Large Learning Rate: Visualizing Learned Basis Functions.
In this section, we visualize the basis functions at initialization and after training with different learning rate.
Learned basis functions Igp0 4)
Random basis functions at initaaiizaiinn
(1w0.5)
0.8
0.6
0.6
0.00
0.4
-0.22
0.2
-0.04
0.0
0.0
0.4
-0.2
0.0
0.2
0.4
-0.4
-02
0.5
02
-0.4
-0.2
0.2
0.4
Learned basis fanctions 1g
Leamnd basis functions Lxpm0.2)
Learned basis functions 1rym0.3)
1.00
0.8
1.5
0.75
0.6
0.50
0.6
0.2
-0.
0.5
-5.2
LypmO
3.0
2.5
3.5
1.5
1.0
0.5
0.0
Figure 7: Illustration of the learned basis function with learning rate 17. It is clear from the figures that there were substantial representation learning and the number of active basis functions gets smaller as the learning rate gets bigger.
We make several observations about Figure 7. First, the learned basis functions are very different from initialization, so a of representation learning happening. comparison regime in which nearly no representation learning is happening. Second, as gets smaller, the number of learned basis functions increases, hence increasing the number of knots in the fitted function. Third, the learned basis function displays strong "clustering" effect in the sense that despite overparameteriiation many learned basis functions end up being the same on the data support. Interestingly, they not the same R, verified that they still different outside the data support, e.g., one of the learned basis function has a knot at x < 800.
"kernel"
A.4 Knots of the Learned ReLU NN (aka Linear Splines) and Their Coefficients
Recall that a linear spline is continuous piecewise linear function and two-layer ReLU NN with neurons span the class of all linear splines with most & knots. Figure 8, we visualize the locations of the knots of the linear spline that the learned ReLU neural networks represent.
18

---

Quantiles of the Learned knots
Sparsity of the learned coefficients
3
0.05 quantile
400
L
0.25 quantile
350
Lp norm p 0.5
0.5 quantile
Lp norm p 0.2
0.75 quantile
300
location on input
1
0.95 quantile
Sparsity
250
200
-1
150
100
-2
50
-3
10
102
10a
10
1/n
1/n
Learned knots to the closest input knot
10a
Minimum
Distance to the closest input x
1st percentile Median
10-1
10-2
10-3
10-4
10-5
10-6
10a
10a
1/n
Figure 8: Illustration of the learned (steady-state) ReLU NN with different learning rate. Recall that all ReLU NNs are linear splines, therefore the location of the knots (i.e., the change points of the linear pieces) describes the representation learning that happens. Each basis function a ReLU function at the knot. The final ReLU NN is linear combination of these learned basis functions. In first panel, we plot the quantiles of the locations of the learned knots as the function of 1/1, In the second panel, we plot the sparsity of the learned coefficients in sparse L1 and Lp norm as the function of 1/1.. The third panel plots the distance of the learned knots from the closest input data points. This empirically verifies that the solution that gradient descent finds at the end is twice differentiable function w.r.. the parameters in the sense that not a single learned knot is exactly at the input data point, thus ensuring the applicability of our theorems.
In the first panel of Figure 8, we find for large learning rate, most of the location of the learned knot actually outside the data support on |-0.5, 0.5]. This is somewhat surprising finding in that the mechanism neural network learning may actually be "pushing the knot outside the data support" so they become inactive on the training data (and only the ReLU truncated Os are active). This is new (and very interesting) way to understand how sparsity arrives in gradient descent learning.
The second panel describes the sparsification effect of the implicit biases from large learning rate, which again, indicates that the weighted TVI constraint is indeed making the learned function sparse (in the coefficient vector). The third panel shows that despite that the learning rate gets small as le 2, none of the learned basis function actually have knots coinciding with any of the input data, thus empirically justifying assumptions the twice-differentiabbliy of the solutions GD finds.
19

---

B Proof Overview
In this section, we outline proof ideas for the main theorems in Section 4.
Proof overview of Theorem 4.1. According to direct calculation, the Hessian is given by
1 n n Σ
1 (fo(a.)) v. Vzf(()
Vi
Vofola + n
(14)
Let denote the unit eigenvector (I|v|12 of (Voooc..) with respect the largest eigenvalue, then it holds that
Amax (i((()) 2 x² V2C(0)v
1
2 Σ
>Amax n
((l(a))-))'V/(aaa (fo(z,) Vāf((z).
(15)
72
(#)
For the term (*), we connect the maximal eigenvalue at to the (weighted) TV()) norm of the corresponding I = So. Let g(x:) be defined as (6), Mulayoff al. [2021, Lemma 4] shows that (details in Lemma G.1):
(x) = Xmax
Σ i=1
2 21+2
Timax
(f))))((())
(16)
-Zmmx
For the term (#), we can bound by the training loss L()) using Cauchy-Schwaad inequality and somewhat surprising uniform upper bound of u (z,(z in Lemma E.1:
(#)1 K
(f(az))) v1)²
(u (VVVf(z))))= < 2m V 2C(().
(17)
The first conclusion (9) of Theorem 4.1 is derived by combining the inequalities above. For the second conclusion (10), note that the term (#) can be further decomposed as:
n
(#) Σ (folz:) - u: Vos(z.)
(folz:) - fo(z:)) Vif(a))) (18)
inequal- ity. Under the data-generating assumption yı fo = ~ N (00 o²) i.i.d., (i)) can be bounded by (xxz) certain empirical Gaussian complexity term sup, Σ, esho (arz) with ha( o² (xx()) The proof is complete by Lemma G.2 which bounds this Gaussian complexity term (w.h.p.) ) in two ways: (1) dimension-free bound of ((Txmax) and (2) Ö(axmax /k/n) n) for the mndee-parameterized case.
Similar to (#), the term (ii) can be bounded by max MSE(fe) fe) using
(æx)u.
Proof overview of Theorem 4.3. Under the boundedness assumption in Theorem 4.3, we can prove a constant upper bound for [ [f"(x))g(Z))) (Lemma H.1), which further implies another constant upper bound for Izz ( dr. Therefore, the metric entropy (logarithmic of c-covering number N,) of the possible output function class is of order -1/2 (Details Lemma H.2).
For fixed e-cover of the possible output function class, according to Hoeffding's 's inequality and a union bound, the uniform upper bound of Gfnz(f) can be bounded by Ó(vlog N./nz) =
Ö(e-ànz 1n ?) with high probability. Note that the approximation error is of order Ö(e), therefore Genz( can be uniformly bounded over the possible output function class by
Ō(c) ( - - Ō(n $).
(19)
where is chosen to minimize the bound. More details can found in the proof of Theorem H.3.
Proof overview of Theorem 4.4. Similar to Theorem 4.3, we can prove a constant upper bound for Jz (=)"(())dd which implies that the metric entropy of the possible output function class (4) is of order 112 (Details in Lemma I.2). Therefore, the critical radius is of order Ö(nz & which leads to (high probability) MSE upper bound of order Ö(n using self-bounding technique. More details about handling other parameters can be found in Appendix I.
20

---

C Some Optimization Results
Lemma C.1 (Restate Lemma 2.2). Consider the update rule in Definition 2.1, for any > local
minimum 6 is an e linearly stable minimum of C if and only if Amax V (()0)))) S
Proof of Lemma C.I. It holds that
0++1 - = 02 - 0- -
= - 8" - -) 8*)
(20)
= (I-n722((0)) (0, 00),
where the first equation is from the update rule in Definition 2.1. The second equation holds because 0r is a local minimum and therefore V=((0) = 0. As a result,
02 0 // ((0))) (0n - 07).
(21)
On one hand, if Xmax ( < 2, it holds that
1/'
0 |0: -
|| 1 >>>>>((0>> 100 - 11 s |10 8"
(22)
where the second inequality because all the eigenvalues of 1/ C(0*) is bounded between [-1, 1]. Therefore, 0" is linearly stable for any
is the top eigenvector of On the other hand, if 8" is e linearly stable, we choose 9g such that
0--0" 00 10--0~11
42 ((0)) and |10g 6*1 = c. Then we have
||0, 0*1 = Amax (VI<(0"))'
(23)
which implies that lim sup 1 mmmma which finishes the proof.
(V2 (V2 < 1, and therefore Amax (Vnxx())((0)))
2
"
The following Theorem C.2 is extension of the main result in Mulayoff et al. [2021]. Recall that stable solutions refer to the functions in F(1, 0, D) as defined in Section
Theorem C.2 (Extension of Theorem I in Mulayoff et al. [2021]). Let f = fo be stable solution for GD with step size r where the training loss L(f) = 0 and L is twice differentiable at 9. Then
1
(x))())()))
(24)
2
where g(x) min(g- (z),,9 (x:) for x E [-mmax Xmax] with
9 (x) (X
=lv++ (E|XIX < x:)²
(25)
(+xx)= P²
a) 1 (E|XIX > x))²
Here X is drawn from the empirical distribution of the data (a sample chosen uniformly from {I₂}).
Proof of Theorem C.2. The proof of Theorem in Mulayoff et al. [2021] first proves that
Amaxe 2 (()) < according to the assumption that f is linearly stable, and then proves the conclusion above. Therefore, the same conclusion directly follows for the stable solutions f = fa in F(1, 0, D) satisfying Amax ( 2 (()) "
Some discussions about the result. Mulayoff al. [2021] studied the problem assuming that the optimization converges to global minimum and the learned function interpolates the training data, i.e. C(f)= = 0. In this way, they link the Hessian matrix properties of the learned function and show that stable solutions of GD correspond to functions whose second order derivative has bounded weighted norm. Moreover, as the learning rate increases, the set of stable solutions contains less and less non-smooth functions. For fixed learning rate, according to the curve of g(x), stable solutions tend to be smoother for instances near the center of the data distribution, and less smooth for instances near the edges. More discussions can be found in Mulayoff et al. [2021].
21

---

D Bounded Variation Function Class and its Metric entropy
In this section, we first define the Besov function class. Then we recall the definition of bounded variation function class and discuss the connection between these two classes. Finally we bound the metric entropy bounded variation function class using analysis about Besov class.
D.1 Definition of Besoy Class
Let Ω2 be the domain of the function class (which we omit in the definition) and || ||ppp denote the cp norm. We first define the modulus of smoothness.
Definition D.1. For function f E (I( where 1 S S co, the r-th modulus of smoothness is defined by
(r.((ft) sup
(f)
(26)
hER4:1MM225t
where A defined as
ATC) = Ej=o () (1)))(((++)))) ff # a
(27)
0,
otherwise.
Then the norm of Besov space is defined as below.
Definition D.2. For 1 < p.q & co, a > 0.r r= = [o:] + 1, define
Ml
(t (t Wr (f, f)) 4
q 00;
(28)
sup Wrp (f,t). t),
=000 0c.
Then the norm of Besov space is defined as:
|f
Il + |fl
(29)
Finally, function f the Besov class p.o if I| finite. For more discussions and properties of Besov class, refer interesting readers Edmunds and Triebel [1996].
D.2 Definition of Bounded Variation Class and the Connection
For the same domain Ω recall that the bounded variation function class is defined
(B, = s max [f(x)) B,
(x)) S On
(30)
Zmaa
According to DeVore and Lorentz [1993]. bounded total variation class is closely connected the Besov class. Specifically, for any constant B, On. it holds that
BV C.) Bf.
(31)
D.3 Metric Entropy of Bounded Total Variation Function Class
Now we bound the complexity of (V()) 1), which will helpful for bounding the complexity of (B, Ca) in the future. We first define the metric entropy of metric space (T, p).
Definition D.3. For a set T with a corresponding metric p(-,),, ), let N T, p) denote the e-covering number of T under metric p. Then the metric entropy of with respect to p log (ee, T)
More details and examples about covering and metric entropy can be found in Chapter 5 of Wainwright [2019]. Next we bound the metric entropy of bounded subset of BV(1). Note that the foo metric over domain Q is (fo(f)) supzen (z) 9(x)), which we denote by || lloo for short.
22

---

={ f 11 I 1, If(x)) s and the
Lemma D.4. Assume the set 1
metric is the &o distance |loc, then there exists universal constant C > 0 such that for any c <> 0, the metric entropy of (Ti, (lx)) satisfies
log (e, Ti.ll 11o0) s SC
(32)
Proof of Lemma D.4. First of all, the domain = [-1, to De and Lorentz. [1993], we have (1 C Bi Therefore, T2 is a bounded subset of B7 (9t) with both o0 and &oo norm bounded by a universal constant.
1] is bounded set in R. Moreover, according
Therefore, the metric space (T || |lac) satisfies the assumptions (the second point) of Corollary 2 in Nickl and Pötscher [2007] with oo, d 1, 2. Then combining the conclusion of
Corollary in Nickl and Pötscher [2007] and the fact that the metric entropy is upper bounded by
bracketing metric entropy (Definition 4 in Nickl and Pötscher [2007]), finish the proof.
0
Remark D.5. For our purpose of bounding the metric entropy of BV(1), we only consider the case where Ω is bounded. For more results regarding the metric entropy of (weighted) Besov space, please refer to Nickl and Pötscher [2007].
E Calculation of Gradient and Hessian Matrix
In this section, we calculate the gradient and Hessian matrix of fa(x) with respect to f. Re- call that fz( Σ Ci (2)
w 1o+0 6(t)) + 6(2) where o(x) max(x, 0}. We denote
(1)
0 = (w] w 61 k w1 2k B(.))T.
(1)
(2)
E.1 Calculation of Gradient
According to direct calculation, for a given x E [- T-Fmaxx Fmax] we have
V fo(z) 2 1 (w.") x -b60 0) vie [k]
V voo)fo(x)= = wi (2) 1 W; x + (11) > ViE [R:] (1)
(33)
Jo(o) = Φi (w. x ((9) = mm) 1) + b(4) x + >0) Vie
(1)
foor 1
E.2
Calculation of the Hessian Matrix
fc(x) In this part, we calculate Vāff(z)) for given [- maxx Tmax]. Below we calculate
30,00,
First of all, if 0, = ((2) or 0 = b(2), a² fa(x)
8² fn)))
00,00, = 0. Then it remains to calculate
where
a6,00
i E [k] and B, E (wol)) (B1), w2)) }. It is obvious that if ø 8 fo(x)
36,00' = Therefore, we only
calculate the case when j = Let 8 denote the Dirac function, it holds that:
8 fo
w,!2),²
( + ((1)) ViE [
Om 1 "T
a² fa(z)
2² fa(x)
(2) 10 (1)
((9)
Vie
Om 1 (T
06! am
fo()
= wi w x + (11))
(2)
(1)
V [+]]
06. ag!
(34)
(arr)
0, Vie E [k]
au (2) Dwn
fa(r
fo(z)
(1) + 999 >0). Vie
(1) dwu
du! " 13) = rll
w
8 fo(z)
f
+ (000 > >0) Vie [k]
1 w
(6 Dwl
ow aa(
23

---

The gradient is generally not well-defined according to the existence of the Dirac function. However, under the assumption that fo is twice differentiable with respect (i.e. the knots of f do not coincide with x),, all the Dirac functions take the value O. In this case,
Ou (uill Ben! LI = 0, ViE [k]
fo(w)
fa(z)
8² fola)
O, ViE [M]
(35)
Ow (1) 86.21
a6.
8 fo()
0, V v [K]
06 0b
E.3 Upper Bound of Operator Norm
In this part, we upper bound the operator norm of the Hessian matrix. Equivalently, we upper bound ee 2 fo (z)ell under the constraint that ||o|| = 1. We have the following lemma.
Lemma E.1. Assume that fa(x) is twice differentiable with respect to 0 and x E [-Imaxx Tmax], for any v such that ||ll||
holds that
22 fo(z)ul S 22mxa Fmaxs 1}.
(36)
Proof of Lemma E.I. Assume (a1,
ark. 31. .kk. n.... The () 3 such that
E (o? + 83 { 2 Note that the Hessian matrix Vafo (x) follows the structure:
A (n Agco
A Agaaaa Apc1260)
A a0(2)
A (11000
Apcasce
Vifo(z)=
(37)
(010)
A
A,0 mn(2)
Age
Agcogenn
Agconee
where wi,,, A A m Agcngas; Ag R A AsCaE Amare RAx1, Apr Agcaaa (2 E Igik and Abe2n122) E R are all zero matrices. Meanwhile, (0) w Anti Auaga E k are all diagonal matrices whose non-zero elements between max Tmaxx 1), max 1}}. Therefore, it holds that:
22 fo()))) < m Xmax. 11
(larnl + (8rr))
(38)
max Fraxx 1}
Σ
a
maxxfmaxx.... 1).
where the second inequality holds because of Cauchh-SShwaal inequality. The last inequality results from x01 x) 1
Proof for the Counter-Example (Theorem 3.1)
Theorem F.1 (Restate Theorem 3.1). For the counter-example, with probability 1 - 5, for any interpolating function f.
Pennx
(z)) = (on n 24 log (1))
(39)
Z-mas
where the randomness comes from the noises {c:). Under this high-probabblity event, when n > S (v oq log (t) any stable solution f for GD with step size n will not interpolate the data, i.e.
Fln.0,D) f(x,) Yi, Vie [n]] = 0.
(40)
24

---

Proof of Theorem F.I. Consider any three consecutive points zjj, 2.421, 2342 where j [n - 2], note that their corresponding y are y,, 9/-1: Mi+2 which are i.i.d. Gaussian random variables N (0, o²). Then according Mean Value Theorem, there exists a E [zy. Tf+1l and 6 (1411 such that
f(()) = Uj+1 Vj n j++ - 2j 2xmax
(b)
Uj+2 Vj+1
n (y5+2 Uy+1). (41)
f2+2
2j+1
2m
Therefore, holds that
(" 2 f'(a)] 11 11 1y5+2 2yz+1 + Myl
T1
[W 6o (42)
2xmax
2fmax
22
where the last equation means that Vj+2 21 + yj follows the distribution (0, 6o²).
We focus on the interval in the middle. For any x E [In/4: /3n/a], we have
P²(X x)
1
X| x
maa
16'
(43)
p P x)
1
B[X
x X
x
Faxx
16'
Together with the definition of g(x) (6), we have for any E [In/4, //l g(x) 2 for any interpolating solutions f. holds that
Therefore,
Fon/4
1 n/6
(T))g(())) 2
Fmax
(x" 2
Zmax
n
Σ
(44)
64
64
2x 2a
where G 's are i.d samples from (N 2o
Assume the median of (0 1)I is > O, which is a universal constant. For any i E [g] define
H: { Voco, if |. 2 Voco,
(45)
0, otherwise.
Then we have H, = /Bea with probability 1.2 In addition, |Gi| 2 H;. According to Lemma K.1, with probability at least - 8,
n/6
n-1
.Vooo. n
logg (1)) c'on ( 24 log
)))
(=))))(()) 2 128
H.
128
24
Emax
(46)
for some universal constant d'
Together with the conclusion in Theorem C.2, for any interpolating and stable solution f. with probability 1 - 8,
1
1 ; )))
π 2 2 don n 24
(47)
which does not hold when 2 Ω (V om
log (1)
G Proof for the (V() Bound (Theorem 4.1)
We begin by calculating the gradient of empirical loss L at 0:
VoL(O) = Σ (f(x)) - Vofola))
(48)
where the detailed calculation of (ofo(z) can be found in Appendix E. Then the Hessian is given by
VzC(1)= 1 Σ Vols(z
Σ - v.)
(49)
n
25

---

where Vzf(z) is calculated in Appendix E. Let v denote the unit eigenvector (|e112 1) of Di= (Vofe(z)) with respect to the largest eigenvalue, it holds that
Amax (2L(O) 2 V
Amax
1 Σ
Σ (Fola;) vi)u" Vaf(x;)o
(#)
= Amax
1
Σ
Vefa(
(fo(z;) 1:)0"' Vof"vo
(50)
1=1
+
(fo(z,) - fo(:;)) V(f(z)u
For term (+), we connect the maximal eigenvalue at to the (weighted) TV() norm of the corre-
sponding f = fo- Let the weight function g(x:) be defined (6), then the lemma below holds.
Lemma G.1. Assume C is twice differentiable at and the corresponding function of is f. then
- [[volaas)) 2 21+2
Zmax
Amax
(z)))))())d,
(51)
where g(x) is defined as (6).
Proof of Lemma G.I. The proof of Lemma Mulayoff et al. [2021] directly proves the result for (z.))))))) which is the Amax (V,CC) in Lemma 4 of Mulayoff et al. [2021] when f an interpolating solution.
Amax
Σi Di=1
For the first inequality of Theorem 4.1, we directly handle the term (#) as below.
1 a (fo(a)) - y1)2 n
n
(#)
Σ
(2f())))) < 2m V 22(0),
(52)
n 1=1
where the first inequality results from Cauchy-Schware inequality. The second inequality is because of the uniform upper bound of o7 VV)((x)) (Lemma E.
For the second inequality of Theorem 4.1, we bound the two terms (i) and (ii). We begin with (6) 1 Σi of (ax()) eil. which is a weighted sum of noises {e:}.
Lemma G.2. Assume e, are independently sampled from N(0, o²) for some > 0, with probability
at least 8, uniformly over all 8 v such that twice differentiable at 9 and ||0|
1.
4n
k log
Vaf(x:oo- 4 max 1) min (
log
14
8
(53)
8
Proof of Lemma G.2. For the first part, according Lemma E.1, we have
n
(x:)u e < max (Fmax, 1} max([e:]).
(54)
n
Since e; 's are independently sampled from Gaussian distribution N N(0,, o²), according to concentration of Gaussian distribution and union bound, with probability 1 2. it holds that:
4n
max(le/] s 20 log
(55)
26

---

Under this sog--probability event, we have
72 7
1
Vof(zi)u c S 40 max(=max: 1) Byyog log (4m)
(n
[
(56)
For the second part, we bound the complexity of (u" (v" (xf((;))) j-1 Notice that 0 is function of the dataset, thus not independent to E,. Also, v is function of the dataset and Our strategy is to apply an e-net argument for both and (z)()) for = 1,
i=1'
We begin with considering the possibilities of (Vaf(z)) According to the detailed form Vzfo(z) in Appendix E, we have the set (Vāf(=))= is fully determined {I ww) (1) Di + +b/g
m. "im.."" Therefore it suffices cover all the possibilities of
by
1 ( 22 + -b0 0) })}²
= for all [k]. Without loss of generality, is also monotonic, which implies that there
assume that
an < 32 ... Un. and then ( ( + +b,0) b1))"
(=1
are 2(n + 1) possibilittis of {I
(1) 0 iml in total. As result, the product space wj x2 +b2
(1)
I1 ( 22 24 +b 0)} i5=11 (and also (v)s(²)) has N₁ (2n + 2) possibilities.
n.k
For fixed matrix M (xx( for some 0, x and v, of such that ||e||| S 1, /|22 I 1, ||00 -oo-vlll2 Se with E (0, 1), it holds that
o Mr (w')
$2 (u o/ + od) w')l
<2 |22l| 222MMMl2ll/// 12/l|11/122 + ||u - o'Ilall l12
(57)
< 44 max 1}e- + max 1}e²
max 3amax(mma (Xmax, 1)e,
where the third inequality results from the upper bound of operator norm of M (Lemma E.I). Therefore, the exact covering set (x;)(=;)); and an 6 [Fmu.. covering set of the unit Euclidean Ball with dimension 3k + (which is exactly the domain of v) together provides an e-cover of { [v" V (xx))) with respect to || lloo. Meanwhile, an mmax( with respect to ll2 of the unit Euclidean Ball with dimension 3k + 1 has cardinality bounded by 3k+1
according to Lemma K.2. Combining the two covering arguments, the e-covering set of { (v" (z)())))) } with respect to lleo has cardinality N, satisfying:
N2 (1
12 max
maxx(araas (1)
13n max maxxfmmax: 1)
log N, < log N1 + log No < 4k log
(58)
Consider a fixed stream (a:) in the covering set, we have |a,| S max (nax(=max: 1) for all i E [m]. Then according the concentration result of Gaussian distribution, with probability 6,
a3c S 4a max 1) log(2/8) Σ n2
1
(59)
n
With union bound over the c-covering set of { (() } and conditioned on the high probability event of (55), with probability 1 5. uniformly over all possible ||u||2 and 0,
1
4n
log (N
Vof(x:)
s $200//n log
+ 4o max Emaxx 1
(60)
4k log
13n max (m
4n + 40 maxx
<20r/ log
1
27

---

Finally, by choosing c
max/ max/#mmax #max.
vn we have
13m k klog
S
14o max(smax:
Do
(61)
71
Y2
Remark G.3. According to the Lemma G.2 above, there are two cases. When the neural network is parametraete,,,,,, we can derive a constant upper bound for term (i). Meanwhile, if the number of neurons is smaller than the sample complexity, we can derive a tighter bound for (i) by covering {o" ( | For k, n such that is polynomially smaller than (e.g. n'-a for some positive a), the term (i) will vanish if n converges to infinity.
Meanwhile, the term (ii) can be bounded by the mean squared error MSE(f)) using Sauchy-Schwan inequality and the uniform upper bound of v² Vas()) (Lemma E.
n n
n
[(1)] S
(Ja(x:)) - folx)))
Σ
2 (((())) S max m 1J (MS((s)).
(62)
Combining the results above, we state the following weighted TV()) bound of the learned function. We leave the training loss and mean squared error (MSE) in the bound, which will be handled later.
Theorem G.4 (Restate Theorem 4.1). For function f = fo where the training (square) loss L is twice differentiable at 6
& Amax (V((())
1 + Tmax / /2(()).
(63)
2
2
where g(x) is defined as (6), Moreover, if we assume y: = fo(æ;) + e, for independent noise & -N10 0²), then with probability where the randomness is over the noises {c,),
Funx (=()))o(z)d
Amax \ (V)L(0))
+ 02maa min { {
Imaa /MSE(f). (64)
2
In addition, if f = fo is stable solution of GD with step size on dataset D, ie., fo E F(n, as in (4), then we can replace Amaze CVC( with 1 in (9) and (10).
2
Proof of Theorem G.4. The first inequality results from plugging Lemma G.1 and (52) into (50). The second incquality holds by plugging Lemma G.I, Lemma G.2 and incquality (62) into (50). For the instantiation of Amax (()C()) the replacement holds due to the definition of F(n, 0, D) in (4). O
G.1 Crude Bound for MSE and the Instantiated TV()) Bound (Corollary 4.2)
Now we prove a crude upper bound for MSE, which could instantiate weighted TV(1) bound.
Lemma G.5. Assume that the function f is optimized, then with probability 1 - 8, we have
22n x
MSE()) Σ - Jo(z))) < 16o log
(65)
i=1
Proof of Lemma G.5. According to the assumption that optimized, holds that
n
Σ (f(a.) - y:)² -
(fo(xe) 11)
(66)
i=1
28

---

Then since (a b)2 - 2a² + 2b always holds (AM-GM inequality), we have
n
a
(J(a.) - Jo(oi)) Σ (f(zi) - yi + vs So(x;))
7
2
Σ
a
(f(wi) - -v:)² Σ (fo(zi) -11)² y11
(67)
"
Σ
4 max
Recall that G 's are independently sampled from NO o²), then according to the concentration of Gaussian distribution and a union bound, with probability --d. 8,
2n
max é S 40 log
(68)
Combining the two results, with probability 8 where the randomness is over the noises {f),
2n
MSF()) = (J(z,) Jo(z,)) & 16 log
(69)
Finally, Corollary 4.2 results from directly plugging Lemma G.5 into Theorem 4.1.
G.2 An Improved MSE Bound and the Corresponding TV()) Bound
In this part, we provide an improved upper bound of the mean squared error MSE(ff) and also the term (ii). We first make the assumption below that the parameters are from a bounded space.
Assumption G.6. There exists some constant p > O such that gradient descent converges to some local minimum 0 with |00||>> S In addition, we assume that /l S D where D 0 is some universal constant satisfying that D S kp2 (I'mx + 1).
Assumption G.6 ensures that the parameter space is bounded while the ground truth function fo can be approximated well by some possible output function. The assumption will surely hold for some large enough constants p, D, which is without loss of generality. In the following analysis, will replace D with its upper bound (xmax + 1) to reduce the parameters the logarithmic terms.
To handle the mean squared error MSE(fo), we begin with an analysis on the complex- ity of the function class of two-layer ReLU networks with bounded parameters F,
F:I-zmax: mmax] + f(z) w
w// W (1+++bb") + 6(2), 1101 S spj. Note that
here assume that the input is from i-I Fmax] and there exists upper bound p on the parameter (w(", ... ww b()), .... (1) (0)2) .... w b(2))T 13+++1
Lemma G.7. The e-covering number N. of function class F, with respect || Iloo satisfies
11 max {xmax 1 1}kp2
log N₂ S 4k log
(70)
Proof of Lemma G.7. We consider the discrete function class below
F = {1: 5: Tmaxx Fmmax] + R
{()=It at a (a:")) x+8 +6(3) st. 11:22-22)- JE[3++1]
(71)
where 0j is the j-th element of (w)))
w (1)
1
BOyT E B2 33 and
E Z is the set (ē i, E Z... Since for each element, the number of choices is bounded by 22 + the total cardinality of F: is bounded by ( + +1 36+1
29

---

For each function f E Fp with corresponding parameter 0 (1 I p), we choose function ff from F& with corresponding parameter & such that 10, 021 is minimized for all E [34- + 11. According to our definition of Fe, we have for all j E [3k + 11. 10 - 0z1 S. Therefore, it holds that
Il fllo 1
(2)
W;
(1)
T u _ x + ( 11 + 1/009) B(2)
i=1
(2)
w (1) + (1 m ( (w! (wf"
+ 65 bb)
(72)
(2) Φ wi
( x x +10) w 10 x + 81:h) ||1 +
Skē - pmmmax + 1) + kipxmmxx + 1)E+ <5max maxxs 1}kpē S,
where the last inequality is by choosing E 5 (" Hep Therefore, the e-covering number N₂ of function class Fp with respect to || ol satisfies
(1
10 maxx(maas 13kp²
3k+1
Ne < 1
(73)
which implies that
11 max [mma 1 1}pp
log N. S 4k log
(74)
Now we provide upper bound of MSE(fo) under the assumption that 0 is optimized, which means that the empirical error of fo is smaller than that of fo, i.e.
2m (fo(z,) v1)² S 2n Σ (folz;)) y²)²
1
(75)
Below we state the improved upper bound of mean squared error under such assumptions.
Lemma G.8. Assume e, 's are independently sampled from ((0,0") some a > O, if Assumption G.6 holds and So E Fo is optimized, then with probability at least 8, it holds that
22
max Emary knng
MSE(Jo) SO
(76)
11
Proof of Lemma G.8. Since 1 Em (fo(z:) v1)²² S 2n
En (folz:) - -v:)² we have
2n
MSE(Ja)
- 2n Σ (o(z)))
< Σ c (fo(x;)- - fo(r:))
(77)
For the optimized function fe, we choose function f from the e-covering set in Lemma G.7 such that f fe <
Due identical analysis as (55), with probability 1- max, (lei)) s 20 log (4m) Under this brob-brbbbyylityy event, it holds that
e (fo(a.) fo(zz))
Σ e ((xx))ff(zz)) + 200/ log
4n g
(78)
According to Lemma G.7, the e-covering number N, of function class F, with respect to || lloe satisfies log N₂ 5 4k log ma 1)4p2) Due to the concentration of Gaussian distribution and
30

---

union bound over the covering set, with probability
for all of in the covering set, é 2.
[NV.
c -o(x))) s 2a
Σ (f(x)) fo(x,)) log
(79)
Combining the two high high-probability events, with probability 1 6, have
n 6, (f(zi) -o(aa)) + 2 log
4n
MSE(Ja) S
2
72
20
Σ (f(zs) fo(x:)) log
<NN, + 2 log
4m
m
8
2a
Σ (f(xs) - fo(xz)) 4k log
max (Taxx 1 13/ip²
+ 200 log
4n
m
6d
2x
11 max max( (mmax- H:pp
Σ (folx;) fo(x;))² 10nkp² max xmax: 1
4k log
cô
4n 8
+ 20
log
00
A log
Imax (2mxx 13kp
MSE(Ja)
+ O akpl
maxxFmax, 1)e log
max 1 kpp
eb
ed
+ +0
11 (5)
oeg log
(80)
where the forth inequality results from Assumption G.6. Selecting solving the second order inequality, it holds that
p [aaxx_ 1) and
o2k log
max
Moup
MSE(fa) SO
(81)
Plugging in the upper bound for MSE (Lemma G.8) to Theorem 4.1, we have the corollary below. Corollary G.9 (Improved version of Corollary 4.2). For stable solution f fo of GD with step size n, where L is twice differentiable at 6, assume Assumption G.6 holds and f E F, is optimized, the function satisfies
with probability
k log
max max((mus I Jhnp
1 +0
(=)
TTmax
(82)
1
7
where the randomness is over the noises {E:} and g(x) is defined as (6).
Remark G.10. The additional term here δ @3mmx
improves over the constant additional
term in Corollary 4.2 if n. addition, if converges to infinity (e.g. nl-a for some and is sufficiently large), the additional term could vanish.
31

---

H Proof for the Generalization Gap Bound (Theorem 4.3)
Recall that the generalization gap of function f is defined
Gen(S) = E [1(()) -) -
EEC(()) (f(z)) - vi)²
(83)
where (x, v) is new sample from the data distribution. The generalization gap measures the difference the expected testing error and the training loss, and a small generalization gap implies that the model is not overfitting.
For stable solution f = fo GDD with step size v where L is twice differentiable at 0, we first derive a corresponding analysis for the weighted TV(1) bound. Recall that the empirical loss still defined as L())
i (f(x;) y1) Then using the same calculation as (50), we have
2 2 Amax Vic(O)) 2 of VBC(O)v
1
1 Σ -
=mmax
Vofe(z.)
+
V
1
2 Amax
(Vofolz:))
(folx.) -yi)2
V 22 (2:)u)2
i=1
(#)
(84)
where the last inequality results from Cauchy-Schwarz inequality. According to Lemma G.1, the term (*) satisfies
(+) = Amax
Σ (affiaa)) 2 1+2
FEmax
(f))))((z))
(85)
1=1
In addition, the term (#) satisfies (w.l.o.g, we assume Tmax 2 1)
(#) S 2x maxxx
[fo((z)) (fo(a;))-) -2
(86)
Under the assumption that the learned function = satisfies |l I and |yd S D for all i [n]], it further implies that
[(#)] S 4.
(87)
Combining the results, the following TV() bound holds.
Lemma H.1. Assume the data distribution satisfies that for all possible (x, y) from the distribution, fe is stable solution of GD with step size n such that twice differentiable at f and [| S D. then it holds that
[x| S Tmax and lyl < D, if the function
Fmax
1
())())((z)
< 7
2x D,
(88)
Tmax
where g(z) is defined as (6).
Note that we assume there exists some interval I C [-Imax #maxl and a universal constant e > 0 such that with probability 8/2 (randomness over the dataset), g(x) 2 e for all x (w.l.o.g. we assume < 1), which further implies that
1 ( c 2 + 20 D)
(
(89)
We base on the probabitohbiittyy event above in the following discussions. Next we bound the metric entropy of the possible output function class.
32

---

Lemma H.2. Define the Te { { Il SD, Jz (z) S 1 { - 2
then the metric entropy with respect || oo satisfies that
Imax ( 2 20x D
log (e, 13,11- 5o
(90)
where O also absorbs the constant
Proof of Lemma H.2. Define the set T4 as:
T4 = {1 [-Txax Tmax]
Franx
(-
|10 S D,
(")()) S c
2x
-Tmax
(91)
Note that the metric entropy T''s is bounded by that of T4, therefore we directly prove the upper bound of log (e, T4, lloo).
Let the set T1 = 1-1 + R
If S
[f(x) $1
(as in Lemma D.4). For
fixed >> 0, according to Lemma D.4, there exists
[ + = covering set of T1 with
respect to || llso. denoted as (h: (h;()))e[[)) whose cardinality N satisfies
2 + 2m D
Fmax
log N s CI\
(92)
We define (x(x) = - 2x max D) Tmax hil smaee for all i E [N]. Then gi's are all defined on [-xmax: mmax]. Obviously, we have (g.( (E)N) also has cardinality N.
For any f(x) E T4, we define g(x)
_(2 2---:t2mmmrrammmmmmm DJsmar f( Tmax) which is defined on [-1, 1].
We now show that g(x) E Tí. First of all, for any x E [-max mmax], we have
D
|o(x)) S
(93)
+ 2x D Fmax
17
Meanwhile, it holds that
S 1g (x)
mmax 15" Immx))
1
1 + 2x
2
Fmax
(94)
1
Fmmax (1" SI
1 + 20 D
-mmax
Combining the two results, have E Tí. Therefore, there exists some he such that ||g halloc 5 [(] +12- D) Jmaas Since f(x)= = 1 1 - + 2x D) 2maxg( =m llg: floo
(+ - max D) Fmaxll - glooo S.
In conclusion, (iihe is e-covering of T4 with respect to || Iloo Moreover, the cardinality of (9:)EN)) is N, which finishes the proof.
Now we provide our main result about the generalization gap (restricted to Z). Below we define the generalization gap restricted to I:
Genz()) = Ez [1(x)) w)²]
- - vt)²
(95)
nI 2:EZ
where Ez means that (ar, y) a new sample from the data distribution conditioned on and nz the number of data points in D such that E I.
33

---

Theorem H.3 (Restate Theorem 4.3). Let P be joint distribution of (z.y) supported on
Tmaxx Tmax x D). Assume the dataset D ~ P i.i.d For any fixed interval I C -mmax: Imax. and a universal constant > such that with probability 1-8./2, g(x) 2 for all x I. if the function twice differentiable at 0 and If S D, with probability 8 (randomness over the dataset), the generalization gap restricted to I satisfies
is is a stable solution of GD with step size nj such that L is
Tmax
2T
Genz(f) R. ((f(z) -
E((a)) yz) ZLEZ
SO D
(96)
where Ei means that (z. y) is a new sample from the data distribution conditioned on I and n-g is the number of data points in 'D such that D₁ E I.
Proof of Theorem H.3. We base on the following event that holds with probability 1 8//2:
J 11""tt)de 1 ( 17 2
1 + 2x
(97)
Then the output function f E T3 defined in Lemma H.2.
For fixed >> O, according to Lemma H.2, there exists an e-covering set of T3 (with respect to || (loe) whose cardinality N satisfies that
π Tmax 1 - 2 + 2a D
log N 50
(98)
For fixed function f in the covering set, since the data set {(1 Us) 22,zz is still i.i.d. from the data distribution conditioned on I, Hoeffding' inequality (Lemma K.3) implies that with probability 1 - 8, it holds that
Ex (f(z) [f)
((()))) - vi)² < <DD2
1 Σ (f(a))
log(2/5)
(99)
nI I
Together with union bound over the covering set, have with probability 1 8/2, for all the covering set,
1og(4N/6)
Ex (F(x)) - -y)²
Σ (f(x:) - y²)² s 4D2
nI
11
(100)
Tmax (
1 20 D)
log(1/0)
D
n
et
1
Under such high probability event, for any f E T3. let f be a function in the covering set such that |lʃ flloo I Then it holds that
Ex (f(x) - -1)
Σ (f(z)) y1)²
TI
Z.EZ
Eτ [F()))
Σ (f(xs) yi)²
O(De)
T&I
Z,EI
Emax
"9 (1_1 1 + 2x 2x.maxx D)
1og(1/07)
(101)
<O(De)+ +0 D².
n c/
Fmax (1 (1-1 2x 2x 1
00
D
"7
nz
34

---

where the last inequality results from selecting the that minimizes the objective.
H.1 Choice of the Interval Under Uniform Distribution
In this part, we discuss the choice of the interval I under the case that the marginal distribution of the uniform distribution on m-x Fmax] For simplicity, we assume that Tmax 1.
Lemma H.4. Assume that x ~ (nif([-1,1]] then we can choose I to be |- 3 31 In this way, with
probability 1 24e "6, for any æ E I, it holds that
g(a) 2 4320
(102)
As a result, when n 2 96 log (*) we can choose I =
[
2 21 and 4320
3: 3
Proof of Lemma H.4. Let the intervals A, be defined below: for all E [12].
7 1-6
A,
(103)
6 6
For fixed n, let P. denote the number of data points in A; which follows Binomial distribution with p - 12' Then for fixed i [12), according to Multiplicative Chernoff bound (Lemma K.4), with
probability 1 - 2e 56, it holds that
1 S
P n
(104)
2 12
12
Then according to a union bound, with probability 1-24e -4ee s6, the above inequality holds for all i [12). Under the case above, prove that ( min{g (x), (x)} 4320 for all E I.
Recall that 9 (z) (2 2)E(r x|
x (E| x])² where is drawn from
the empirical distribution of the data (a sample chosen uniformly from {zy}). Then for any 3
Pi P2
P2(X <
2
144'
1
(105)
B[r X|X < <x)
2
24
8
30'
24
V + ( < x2 1.
Combining the inequalities, we have (x) 2 4320 for all x E I. The result for (xx) can be proven similarly, which implies that with probability 1 - 24e मे g(x) 2 4320 for all x E I.
The implication can be proven by direct calculation.
Remark H.5. We only consider the case where the data is sampled from uniform distribution, while we remark that for various distributions that are not heavy-tailed (e.g. Gaussian distribution, Laplace distribution), a similar result can be derived. Some empirical illustrations are shown in Appendix H.2 below.
H.2 More Illustrations of the Choice of the Interval
In this part, we consider the choice of I and under different data distributions. More specifically, we consider the following four distributions of x.
Uniform distribution: x: Unif([-1,
Normal distribution: x ~ (0, 1).
Laplace distribution: x ~ Laplace(O, 1).
(-0.55. 0.25)
with probability ?
Gaussian mixture distribution: x
(0.5, 0.25) with probability 2
For each distribution, we sample = 1000 data points from distribution (conditional on a E [-1, II) and construct the g(x) function. Then we choose the interval I and the corresponding lower bound e of g(x) over From Figure 9, we find that for of the four distributions, with a constant > 0.002, the interval I can be chosen to incorporate large portion of the data (nz 0.65m).
35

---

Uniform distribution, c=0.005.m,
Normal distribution, C=0.002.n; 780
0.14
g(x) minio 9(x).9" (x))
e(x) minlo (x), (())
y- y=0.005
0.12
y-0.002
0.12
(-0.69)
(-0..44)
0.10
0.08
g0d
0.06
0.06
0.04
0.02
0.02
0.00
0.00
-1.00
-0.60
-0.250.00
0.25
0.60
1.00
-1.00
-0.60
-0.250.00
0.25
0.60
1.00
x
Laplace distribution, 0=0.02
797
Gaussian mixture distribution, c=0.002,n,
784
minig (X), (x))
g(x) miníg (x).
y-0.002
0.12
y=0.002
0.10
(-0.68)
(-0.33)
0.08
0.06
0.04
0.04
0.02
0.02
-1.00
-0.60
0.25
0.60
-1.00
-0.60
-0.250.00
1.00
x
Figure 9: Illustration of the choice of interval and the corresponding lower bound for gax).
I Proof for the Refined MSE Bound (Theorem 4.4)
In this part, we base on the same conditions in Corollary 4.2, which is the weighted TV(I) up- per bound. For an output stable solution f satisfying the conclusion of Corollary 4.2, we have -T ("()))g(z)dz < - + Ō(x#max) and we denote the right-hand side by S. In addition, according the assumption that g(x) 2 for any & E I, further have fz (x) do < S. Now we bound the complexity of the possible output function class.
According to the definition of two-layer ReLU network and our assumption that |00| it holds that:
(2) [f(0] = W Φ (b())
Σ
+ +122)
S kp² +
(106)
[F((0) <
W w!!
(2) (1)
< kpp
(107)
Define the set T ing the inequalities above, the possible output function (if restricted to I) belongs T. We begin with an analysis of the metric entropy of the intermediate function set T2.
[f()) < kp² +pp
[f()) < kpp, fr (x) S 9]. Accord-
Lemma I.1. Assume the sei T2 {s
[- [-Imaxx Fmax
R f(0) (0) 0, f f do C2
for some constant C2 0, and the metric is lox distance || Il,o, then there exists universal constant
36

---

C > O such that for any e >> O, the metric entropy of (T2, ll (ll)) satisfies
C2tmaxx
log (c, T2, 11=0)) S CiV
(108)
where C₁ can chosen as the same C₁ in Lemma D.4.
- Proof of Lemma I.I. Let the set Ti f= -R I 1") S 1, 15(x) <
(as in
Lemma D.4). For a fixed > O, according to Lemma D.4, there exists a Cammaax covering set of T with respect to || Iloa. denoted as [41()))E[N))) whose cardinality N satisfies
U2ax
log N &CIV
(109)
We define (x max Fman for all i E [V]. Then 9i 's are all defined on |- mmax Fmax Obviously, we have (x) kEENN also has cardinality N.
For any f(x) E T2, we define g(x) Taumar f(x Tmax) which is defined on [-1, We now show that g(x)) E TT. First of all, for any x E m-xxxx Tmax], we have [[(xx) S - (x) (x)) S Cz-
Therefore, for any E [-Imax Tmax], lf(xx) < C2 which implies that [g(x)) I 1 for any
[-1, Meanwhile, it holds that
[ 10" (x)ler
["
1
C24maax "maxls" (5" xmaa))
(110)
1
Zmmax
(z) 1
C2
Combining the two results, we have g T1. Therefore, there exists some h2 such that ||g hillo S 119. flloo C2 h, glooo S.
O2maaax Since f(x) = C2Imax Zmax
In conclusion, {us kejN is an e-covering of T2 with respect to Il Moreover, the cardinality of {9: HEIN is N, which finishes the proof.
With Lemma 1.1, we are ready bound the metric entropy of T. Lemma 1.2. Assume the metric foo distance
|| Iloe. then the metric entropy (T, || (lx)) satisfies
log Ne, [1x)) so Ximass
(vtmaass
(111)
where S is the right-hand side of Corollary 4.2 and O also absorbs the constant
Proof of Lemma 1.2. For any function f E T, can be written below:
f(x) f(0) + (0) g(xx,
(112)
where g(x) = f(x) f(0) - (() satisfies that (0) = g (0) 0 and = f")). Therefore, to cover T' to accuracy, it suffices to cover the three parts to & accuracy with respect to || |l respectively.
For (0)., since |s(0) < kp + p. the covering number's is bounded by
N₁ 6(kp² + p) 8kp²
(113)
For f'(0)z, since [ S kp?, the covering number is bounded by
N₂ < 1kp22max
(114)
37

---

Finally, for (x),, since ((x) E T2 with C2 = (g is extended linearly beyond the interval 2), the covering number is bounded according Lemma I.1 above.
max S
log N3 S Civy
(115)
Ce
Combining the three parts, the metric entropy is bounded by
Xmuxx
log (e, |I )l log N1 + log N2 + log N3 S S0
(116)
where O also absorbs c, which is the constant lower bound of g(z).
According to the metric entropy above, we are ready to provide a refined (high probability) bound for mean squared (restricted 2). Note that assume that the ground-truth function fo E T. which is necessary for the mean squared eπror to vanish.
Lemma 1.3. Under the same conditions in Corollary 4.2, for any interval I C [-Imaxx Tmax and a universal constant c > such that g(x) 2 for all x and optimized over I, i.e. E y1)² I Exjer(Jo
- y:)2, if the output stable solution 0 satisfies [10]lcc S and the ground truth fo T, then with probability - 8 (over the random noises {ci)), the function So satisfies
1 E
022
(I log ())
)
MSEI(f)
(((x)
<o 5o
(117)
VVT
117
Z,EZ
where nı is the number of data points in D such that I; E I.
Proof of Lemma 1.3, According to the assumption that f is optimized over I, we have
(f(())-)1' < Σ (folz)) - y1)²
(118)
FEET
Z.EZ
Similar to the calculation in Lemma G.8, it holds that
2nI Σ (f(x)) fo(z))) 1 Σ NI I
1
MSE+(F)
-
(119)
It is obvious that the function class T is convex, together with the assumption that fo E T, we have the function T T {fo} is star-shaped (details in Section 13 of Wainwright [2019]).
Note that the metric entropy of T satisfies that log N(e, T, - s o ( SmarS
According to
Corollary 13.7 of Wainwright [2019], the critical radius satisfies that
o²2
2 Iso
S)
(120)
nt
Finally, according to Theorem 13.5 of Wainwright [2019], we have with probability 1 - 5.
[-))
{
(Imax log {5 )))
MSE (f) 500
(121)
11
which finishes the proof.
Finally, Theorem 4.4 is derived by plugging in the definition of S.
38

---

Theorem L.4 (Restate Theorem 4.4), Under the same conditions in Corollary for any interval I C
[- mmxx mmax and a universal constant >> O such that g(x) 2 c all I and f optimized ) if the output stable solution 0 satisfies over I, i.e. (f y²)² 2 I Ez,ez((o((,)
[10|1>0 S p (for some constant p > 0) and the ground truth fo E BV (kip, ( + oTFmax)) )), then with probability ó (over the random noises {(1)), the function f = fo satisfies
0² $
MSEI(f)
1
- -
Immxx
OFFmax
(122)
TVI
11
1
J.EZ
where nt is the number of data points in D such that x; I.
Proof of Theorem 1.4. Note that BV (kp?; 201 JDmux)) is subset of T. Then the proof directly results from Lemma 1.3 and S = o.mmx)
I.1 The Improved Results for the Under-parameterized Case
We assume that n/k is large enough such that the additional term in the TV(1) bound vanishes.
Assumption 1.5, We assume that & is large enough such that the last term in (82) Ö(TTmax v k/n) S 2. which further implies that _ | (x))d +/- where g(x) is defined as (6).
Assumption I.5 requires that is larger than some constant, which naturally holds if & = n for some a > and n is sufficiently large. Under such assumption, we improve the MSE upper bound.
Theorem I.6. Under the same conditions in Corollary G.9, assume that Assumption 1.5 holds. For any interval I C [-Tmaxx Tmaxx and a universal constant e > O such that g(x) 2 for all x E and f is optimized over I, i.e. En vi)² 2 S Ex.er(oozz
v:) if the output stable solution O satisfies |10]|=> S (for some constant p > 0) and the ground truth fo E BV (kp?, mn). then with probability 1 (over the random noises (ti)). the function f == Io satisfies
MSE, (f)
1
E (f(x))
<ō Ō
0²
Zmax
(123)
TI
where ng the number of data points 'D such that x;
Proof of Theorem 1.6. The proof is identical to Theorem 14,, with S replaced by 4
Remark 1.7. Compared to Theorem 4.4, Theorem I.6 is better the dependence of by removing the additional term a=² maax Such improvement results from the improved (V) bound (Corollary G.9) and the fact that n/k is sufficiently large.
J
Interpolating Solution with Noisy Labels must be
"Sharp"
Recall that in the counter-example, we fix x; any æ. which implies that y 's are independent random variables from (0,
2imaaei n-1
(1 111
for E [n] and fo(Ø) = for
Proposition J.1. In the example above, assume f = fe is an interpolating solution where L is twice differentiable 0 then with probability 8. we have
53 1
Amax Cmnxx(V.. (V2C(0)) = Ω on 24 2og
(124)
Proof of Proposition J.I. According to Theorem 3.1, with probability 8, we have
("())lg(z)dz Ω on 24 log )
(125)
Zmax
39

---

where (zx) is defined in (6). Meanwhile, note that fo is an interpolating solution, and therefore
1 V2c(0) Voffla))( + Σ (folx.) y. V
n
(126)
(Vofa(=))(
Finally, combining the results and applying Lemma G.I, it holds that
Amax (j((()) Amax
(ofooz)))VVttttz))) n
(127)
(1)( 2 2 on 24 24 8 )
21 +
-Emax
which finishes the proof.
K
Technical Lemmas
Lemma K.1 (Lemma F.4 in Dann et al. [2017]). Let Fifor = 1.... be affittaaiinn and X1, ,
be sequence of Bernoulli random variables with P(X; 1|F(-1) P. with P. being F;-1- measurable and X, being F; measurable. It holds that
P
X
P./2- - W se-w.
1=1
Lemma K.2 (Covering Number Euclidean Ball [Wainwright, 2019I). For any > the c-covering number of the Euclidean ball in Rd with radius R 0 is upper bounded by (1 + 2
Lemma K.3 (Hoeffding's inequality [Sridharan, 2002]). Suppose X1, X2, ... Xn are a sequence of independent, identically distributed (i.i..)) random variables with mean Let Suppose that X, [-b, b] with probability 1, then with probability 1 8,
- X;.
2 1og(221))
X < 6
(128)
Lemma K.4 (Multiplicative Chernoff bound [Chernoff, 1952]). Let X be Binomial random variable with parameters p, n. Then for any å E [o, 1], holds that:
pm
X > (1 + 8)pm]]
(129)
P < 5m
(130)
The lemmas above are also applied in Qiao al. [2022], Qiao and Wang [2023a,c], Qiao et al. [2023],
Qiao and Wang [2023b, 2024], Zhao al. [2022], Xu al. [2023].
40

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please refer the "Disclaimers and limitations" part page
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
41

---

The assumptions are stated in the theorems while the proof is stated in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
The details can be found in Section 5.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
42

---

Answer: [Yes]
Justification:
We will release the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/nips. wwtppcccpccccceeccccccccccccclct httaa/cguiieeeeeeeeuniiieeee /Coo//eoomissssseeeee wwmiiissioooicyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
The details can be found in Section 5.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Since gradient descent, everything is deterministic once the initialization parameters finished.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
43

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All experiments are run on mac book.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https /tte:://neuurrpe httppppp....pbbllccccchccceeeeee
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is paper regarding theory of neural networks, where we believe there is no possible negative societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
44

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
45

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
46


Reviews:
[{"review_id": "ALE6surkSC", "reviewer": "Reviewer_2Lhx", "summary": "This paper studies the generalizability of stable local minima in univariate regression with shallow ReLU networks. Along the way, the authors provide a bound on a weighted total variation norm of networks corresponding to stable solutions which in turn provide a tighter generalization bound.", "questions": "In the context of theorem 4.3 and 4.4, should $n_I$ be the number of data points belonging to the interval $I \\subset [-x_{max}, x_{max}|$ instead of the length of the interval $|I|$? Otherwise, the RHS of the bound in theorem 4.4 seems to be non-vanishing as $x_{max} $ is at least on the order of the length of the interval $|I|$.  \n\nCan the authors also provide some intuition on how the weight function $g$ was chosen?", "limitations": "The authors have adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and provides a novel way to obtain generalization bounds using minima stability theory.", "weaknesses": "It is not clear to me why the experiments (e.g. figure 3) corroborate the theoretical results in the paper. \n\nTo illustrate my point, suppose for a given $\\eta > 0$, a solution $\\theta^*$ is linearly stable. \nNow suppose one trains a ReLU NN with a different learning rate $\\alpha > 0$ and it converges to $\\theta^*$. When considering the generalization gap of the solution $\\theta^*$ (e.g. theorem 4.4), only the constant $\\eta$ is relevant. The point is that the actual learning rate of GD that was used to find stable solutions is irrelevant to the generalizability of the solution (at least in the context of theorem 4.4) . Hence, I feel that more compelling experiments would study generalization errors of stable local minima that are stable for varying $\\eta$. \n\nIn this vein, I feel that the statement, “Meanwhile, the dependence $\\frac 1 {\\eta}$ ...” (line 296 -298) to be inexact as it is only supported by the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your high quality review and the positive score. Below we will reply to your comments.\n\n**It is not clear to me why the experiments (e.g. figure 3) corroborate the theoretical results in the paper.  ... The point is that the actual learning rate of GD that was used to find stable solutions is irrelevant to the generalizability of the solution (at least in the context of theorem 4.4).**\n\nThe reviewer is right that our generalization bounds work for all ``flat'' solutions when the sharpness is measured in terms of the $\\lambda_{\\max}$ of the Hessian, and it may appear to be slightly indirect to expose only the learning rate $\\eta$ in the theorems. \n\nThe sharpness and learning rate $\\eta$ is connected in two ways. First, from the linear stability-theory, gradient descent with learning rate $>\\eta$ cannot stably converge to solutions with $\\lambda_{\\max}$ larger than $2/\\eta$, thus ruling out those solutions at the steady-state of GD dynamics. Second, it has been observed that gradient descent training of neural networks finds solutions on the edge-of-stability.\n\nTo say it differently, the choice of learning rate $\\eta$ controls the maximum ``sharpness'' of the solutions that GD converges to --- an implicit constraint that helps with generalization. Figure 3 clearly demonstrates this effect. Also, see the middle panel of Figure 2. We believe these results do corroborate our theoretical findings.\n\nIn the example you gave, let $\\theta^*$ be a solution that GD with learning rate $\\eta$ converges to.  It is true that GD with an even smaller learning rate $\\alpha < \\eta$ can possibly converge to $\\theta^*$ too, there are many other lower-loss solutions that GD with the smaller learning rate $\\alpha$ can find more easily, thus do not converge to $\\theta^*$.\n\nNote that even if GD with learning rate $\\alpha$ does converge to $\\theta^*$, it does not invalidate our theorem (replacing $\\eta$ with $\\alpha$ makes the bound more relaxed).\n \n**In the context of theorem 4.3 and 4.4, should $n_I$\nbe the number of data points belonging to the interval $I\\subset[-x_{\\max},x_{\\max}]$ instead of the length of the interval $|I|$?**\n\nYes, you are correct. This is a typo we found after the submission of the draft. Indeed, $n_I$ should be the number of data points such that $x_i\\in I$. Therefore, the RHS is vanishing for a fixed $x_{\\max}$ and increasing number of data points. Thanks for pointing this out, we will correct this in the next version.\n\n**Can the authors also provide some intuition on how the weight function $g$ was chosen?**\n\nThe weight function $g(x)$ is inherited from [Mulayoff et al 2021] and its choice is mainly due to technical reasons.  Based on inequality (41), the key idea is to bound the TV(1) norm of the output function by $\\lambda_{\\max}(\\frac{1}{n} \\sum_{i=1}^n \\nabla_i \\nabla_i^T)$ (the term ($\\star$)). Therefore, the $g$ function is generated in the middle-step inequalities to lower bound the $\\lambda_{\\max}$ term by $\\int |f^{\\prime\\prime}(x)|g(x)dx$. For more proof details, please refer to our Lemma F.1 or Lemma 4 of [Mulayoff et al 2021]. \n\nNote that this is not an artifact of the proof. The weighting function $g$ correctly describes the implicit bias due to minima stability. The implicit smoothness regularity near the boundary of the distribution support is weaker than that in the center. \n\nThanks again for the high-quality review. We hope our response could address your main concerns and we are happy to answer any further questions.", "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": "", "extra_scores": {}}, {"review_id": "4OS5hNrT86", "reviewer": "Reviewer_qFzY", "summary": "The paper studies uni-variate regression with two layer networks and builds on the following observation: If the basin (derived form a quadratic approximation) around a given minimum is too narrow, gradient descent with a fixed step size $\\eta$ will escape it, only sufficiently wide basins can capture the iterates of GD with large step sizes. It is thus reasonable to restrict the function space attainable by GD to the set of functions that can be expressed by a minimum with a wide basin. By extending a previous result to the noisy-label setting, they show that the width of the basin (or the hessian of the loss) relates to a (weighted) measure of the TV norm of the function encoded by the minimum. The function space of interest thus becomes a space functions with low TV norm. By computing covering numbers of this space, uniform generalization bounds are derived for this restricted space of functions.", "questions": "The weight function $g$ is inherited from [Mulayoff et al 2021]  but would really benefit from some more clarifications, even for completeness. It is clear that the interval $\\mathcal{I}$ must be introduced to remove the weighing and allow the authors to use covering numbers for bounded TV norm spaces. Could the authors explain why it arises in theorem 4.1 ?", "limitations": "The limitations are discussed.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written. The proofs in the appendix section are also well written and easy to follow.  The minima studied are non-interpolating, unlike the minima studied by a large portion of prior literature (although this work is in the univariate setting). Moreover, although the fact that large stepsizes bias towards solutions with fewer knots appears in prior work, this paper explores this interesting fact further in the noisy-label setting. The paper provides some avenues to understanding generalization when over-fitting is not benign.", "weaknesses": "- *The \"optimized\" assumption*: This assumption which effectively assumes that there exists wide and low minima is somewhat justified in lines 267-270, but I believe it is reasonable to disagree with the statement that it is mild. The experiments provided as evidence for the assumption are conducted with really large noise levels sigmas that are of the same order as $f$. The authors empirical argument could be strengthened by considering noise levels that do not dwarf the signal. It seems difficult to believe that a smooth $f$ can attain a training loss that is lower than $f_0$ when no assumption on the smoothness of $f_0$ is made. The authors should clarify why a condition on $f_0$ is not necessary for this assumption to be mild.\n\n- The refined bounds with underparametrization: The bounds are refined by considering under parametrized settings with the width $k$ being smaller than the number of data points but the authors do not discuss its impact on the \"optimized\" assumption. Why would an underparametrized network be able to attain train losses smaller than a ground truth on which no assumptions are made ? I believe there are trade-offs between $\\eta$, the level of underparametrization and the attained train loss that are not mentioned sufficiently by the authors.\n\n- A final minor weakness: The work extends [Mulayoff et al 2021] in limited ways but does not exploit the added generalization to derive new conclusions. That stepsize affects the number of knots was explored before. There is now a sigma appearing in the smoothness bounds and an MSE term, yet there are no comments on what is added by their extension. The interplay between sigma and eta is not discussed, for instance, does having a large eta  but high noise means that stable functions need no have a low TV norm or is the upper bound loose?  I believe such discussions could strengthen their work as some results, namely Thm 4.3, are straightforward applications of generalization bounds for  spaces with known metric entropy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your high quality review and the positive score. Below we will reply to your comments.\n\n**Regarding the ''optimized'' assumption.**\n\nFirst of all, we politely point out that we actually made some assumptions on the smoothness of $f_0$. In line 312 of Theorem 4.4, we assume an upper bound on the TV(1) norm of $f_0$ (dependent on the learning rate $\\eta$), which further implies that $f_0$ is inside the possible output function class learned by GD. Therefore, the ''optimized'' assumption can be satisfied if GD finds some smooth function that is near-optimal (in training loss) inside the possible output function class. Lastly, we will conduct experiments with smaller noise scale to check the assumption. \n\n**Regarding the refined bounds with underparametrization.**\n\nThis is a very good point. Our generalization bound holds as well as the learned function is ''optimized'', while the result can be improved if a refined MSE bound could be derived. The case of underparametrization is therefore mentioned as an example for a refined MSE. In this case, the ''optimized'' assumption is not guaranteed, and we agree that it is harder for an underparameterized NN to perform better than the ground truth (compared to the overparameterized case). The relationship between whether the ''optimized'' assumption is satisfied and the number of neurons in the network is a very interesting problem, and we will think about experiments to showcase the relationship.\n\n**Regarding the interplay between $\\sigma$ and $\\eta$.**\n\nThanks for the comment mentioning the interplay between $\\sigma$ and $\\eta$. The current bound scales as $O(\\frac{1}{\\eta}+\\sigma)$, which means that either a small $\\eta$ or a large $\\sigma$ would lead to a larger TV(1) bound. The empirical evidence of such argument would require trying out different noise scales (similar to the first weakness you mentioned), and we leave these to the next version of the draft.\n\n**Regarding the weight function $g$.**\n\nThe choice of $g$ is mainly due to technical reasons.  Based on inequality (41), the key idea is to bound the TV(1) norm of the output function by $\\lambda_{\\max}(\\frac{1}{n} \\sum_{i=1}^n \\nabla_i \\nabla_i^T)$ (the term ($\\star$)). Therefore, the $g$ function is generated in the middle-step inequalities to lower bound the $\\lambda_{\\max}$ term by $\\int |f^{\\prime\\prime}(x)|g(x)dx$. For more proof details, please refer to our Lemma F.1 or Lemma 4 of [Mulayoff et al 2021]. Lastly, some properties of $g(x)$ and its implication on the learned function $f$ can be found in Appendix B.\n\nThanks again for the high-quality review. We hope our response could address your main concerns and we are happy to answer any further questions.", "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": "", "extra_scores": {}}, {"review_id": "WWP3hosUEU", "reviewer": "Reviewer_4Yyh", "summary": "This paper studies the generalization properties of two-layer ReLU neural networks in a univariate nonparametric regression problem with noisy labels. It proposes a new theory for local minima to which gradient descent (GD) with a fixed learning rate $\\eta$ stably converges. The paper shows that GD with a constant learning rate can only find stable local minima whose weighted TV(1) is bounded by $1/\\eta-1/2+\\tilde{O}(\\sigma+\\sqrt{\\mathrm{MSE}})$. With this property of local minimas, they prove the generalization bound for univariate nonparametric regression. The theoretical results are validated by extensive simulations demonstrating that large learning rate training induces sparse linear spline fits.", "questions": "How large is the family of target functions satisfying the BV(1) condition?", "limitations": "The authors have addressed some limitations of their work, acknowledging that their analysis is only for full batch gradient descent and univariate nonparamatric regression.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper gives an end-to-end analysis of the generalization of two layer ReLU networks on learning nonparametric univariate functions. The completeness of the work is significant. The theoretical analysis is solid and the proof is well-organized. The authors also present extensive experiments to support their theoretical findings. In general, it is a good paper.", "weaknesses": "1. The analysis in this paper has little focus on optimization. There is no rigorous theoretical evidence that GD will find the solutions that satisfies the assumptions (though I know this is an open problem in the literature).\n2. This paper is limited to univariate functions, which is not important in practice. The authors claims that the technique can be generated to multivariate functions but they did not show that.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your high quality review and the positive score. Below we will reply to your comments.\n\n**The analysis in this paper has little focus on optimization. There is no rigorous theoretical evidence that GD will find the solutions that satisfies the assumptions (though I know this is an open problem in the literature).**\n\nWe agree with your point. Line 94-105 in the paper was written with the hope of avoiding the confusion w.r.t. the optimization.\n\nOur results focus on the generalization of the neural nets GD can stably find. We do not have new computational guarantees on GD convergence. Convergence of GD for training a neural network in non-interpolating regime (to an ''optimized'' solution) is an open problem that would probably require additional assumptions. \n\nTo the defense of our paper, almost all statistical learning theory is about ERM or regularized ERM which does not deal with optimization at all. The interesting discovery from our paper is that we not only do not require ERM, we showed that ERMs are very bad. \n\nWhile we cannot show that GD finds good solutions, we proved that (1) GD cannot converge to interpolating solutions (unless the learning rate is tiny) (2) all solutions GD can converge to cannot overfit.  These are, in our opinion, strong and new theoretical results about ''optimization'' even though they are not about computation but rather about ''optimization-induced'' solutions.\n\nMoreover, we find that our bounds hold for a wider range of cases in the sense that the convergence of GD is not necessary. The weighted TV(1) bound of $f_\\theta$ is valid as well as the corresponding $\\theta$ has a flat landscape (i.e. the $\\lambda_{\\max}$ of Hessian is bounded by $\\frac{2}{\\eta}$). In this way, our results actually apply to all flat points found along the learning process of GD and the ''Edge of Stability'' regime. We will make this more general implication of our result clearer in the next version. \n\n**This paper is limited to univariate functions, which is not important in practice. The authors claims that the technique can be generated to multivariate functions but they did not show that.**\n\nSince this is the first paper to consider minima stability without the assumption of interpolation, we start with the univariate case. The generalization to multivariate functions includes deriving a similar weighted TV(1) bound (with $f^{\\prime\\prime}(x)$ replaced by the Laplacian $\\Delta(f)$). Based on the analysis for the multivariate case with interpolation [Nacson et al 2022], the additional term about approximation error needs to be handled as in this submission. With a TV(1) bound, the learned function belongs to a Radon TV class, and the remaining analysis is based on the metric entropy of such a function class. We believe this to be an interesting and promising future direction.\n\n**How large is the family of target functions satisfying the BV(1) condition?**\n\nThe BV(1) function class includes a wide range of well-known functions, including the more familiar first-order Holder class functions (functions with Lipschitz derivatives) and Sobolev class functions (functions where the second derivatives are square-integrable), but also cover more spatial heterogeneous functions such as linear splines with a small number of knots. For a few examples, see Fig. 2, Fig. 3 and Fig 4 of (Mammen and Van De Geer, 1997)\n\nIt is a natural function class that ReLU neural networks represent. It is also a well-studied function class in the non-parameteric regression literature (e.g., Mammen and Van De Geer, 1997;  Donoho and Johnstone, 1998). \n\nEnno Mammen and Sara van de Geer, Locally adaptive regression splines.\n\nDavid L. Donoho and Iain M. Johnstone, Minimax estimation via wavelet shrinkage.\n \nThanks again for the high-quality review. We hope our response could address your main concerns and we are happy to answer any further questions.", "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": "", "extra_scores": {}}, {"review_id": "mNbzpzB95r", "reviewer": "Reviewer_3THJ", "summary": "This paper studies the implicit regularization of large learning rates in gradient descent. The setting is univariate linear regression with two-layer ReLU neural networks. The authors show that, if GD converges to a local minimum, then the function implemented by the neural network at this local minimum has a bounded first-order total variation. This regularity avoids overfitting, as quantified by a generalization bound. Numerical experiments validate the results.", "questions": "Do the authors have any insight on the role of overparameterization in the setting they consider? It does not seem to have a large influence on the generalization bounds, but perhaps it would help the optimization (e.g., via a PL inequality)?\n\nMinor remarks:\n- lines 132: the connection between stepsize and L1/L2 regularization has been thoroughly analysed for diagonal linear networks in [2].\n- lines 147-153: a relevant theoretical paper on the Edge of Stability is [1].\n\n[1] Damin, Nichani, Lee, Self-Stabilization: The Implicit Bias of Gradient Descent at the Edge of Stability, ICLR 2023.\n\n[2] Even, Pesme, Gunasekar, Flammarion. (S)GD over Diagonal Linear Networks: Implicit Regularisation, Large Stepsizes and Edge of Stability. NeurIPS 2023.", "limitations": "Limitations are properly addressed.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Understanding the implicit regularization of optimization algorithms for deep learning is a key topic. This paper studies a fairly realistic setting, which does not necessitate interpolation. To my knowledge, the results are novel and go beyond what was already known on the impact of large learning rates (edge of stability, minima stability). Most previous works focus on parameter space and not function space. The interpretation in terms of function space proposed in the present paper is interesting. The paper is very clearly-written. While I have not read the proofs, the mathematical presentation of the results in the main text is very precise.", "weaknesses": "The paper considers a univariate case, some comments on the extension to the multivariate case are given at the end of Section 1.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your high quality review and the positive score. Below we will reply to your comments.\n\n**The paper considers a univariate case, some comments on the extension to the multivariate case are given at the end of Section 1.1.**\n\nSince this is the first paper to consider minima stability without the assumption of interpolation, we start with the univariate case. The generalization to multivariate functions includes deriving a similar weighted TV(1) bound (with $f^{\\prime\\prime}(x)$ replaced by the Laplacian $\\Delta(f)$). Based on the analysis for the multivariate case with interpolation [Nacson et al 2022], the additional term about approximation error needs to be handled as in this submission. With a TV(1) bound, the learned function belongs to a Radon TV class, and the remaining analysis is based on the metric entropy of such a function class. We believe this to be an interesting and promising future direction.\n\n**Do the authors have any insight on the role of overparameterization in the setting they consider? It does not seem to have a large influence on the generalization bounds, but perhaps it would help the optimization (e.g., via a PL inequality)?**\n\nThis is a very good question. \n\nOverparameterization ensures that the neural network is able to ''approximate'' the underlying function $f_0$, i.e., there exist neural networks such that the training loss can be smaller than $\\sigma^2$. It is also generally believed that overparameterization makes optimization easy.  In our numerical experiments, we found that underparameterized NNs (with just a few knots) are more likely to get stuck at solutions with knots in awkward locations. On the other hand, when the NNs are overparameterized, even at initialization, there are already candidate basis functions with \"knots\" near every input data point, thus making it much easier to find good solutions that are ''optimized''. This is a hypothesis that our experiments (in Figure 4,5) supports.\n\nOur generalization bounds work for both overparameterized and underparameterized NNs. The theoretical insight is that, when trained with GD, overparameterization does not cause overfitting, which offers new theoretical justifiction to how GD-trained overparameterized NN works even though there are more than enough parameters to overfit the noise. \n\nAs for the PL condition:  it will be very interesting if one can obtain PL condition (or any approximate variant of that). Existing work on the optimization of overparameterized NN focuses on the ''interpolation'' regime which does not apply to our problem.\n\n\n**Regarding the references.**\n\nThanks for pointing us to these references. We will add discussions about these papers in the next version.\n\nThanks again for the high-quality review. We hope our response could address your main concerns and we are happy to answer any further questions.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper provides new optimization and generalization results in an interesting univariate setting.  Reviewers are uniformly positive and this is an easy accept :)
Decision: Accept (spotlight)