Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel
Authors: Yilan Chen
Zhichao Wang
Wei Huang
Andi Han
Taiji Suzuki
Arya Mazumdar
Venue: NeurIPS 2025 poster ()
Keywords: Generalization bound
algorithm-dependent bound
data-dependent kernel
neural tangent kernel
Primary area: theory

Abstract: Gradient-based optimization methods have shown remarkable empirical success, yet their theoretical generalization properties remain only partially understood. In this paper, we establish a generalization bound for gradient flow that aligns with the classical Rademacher complexity bounds for kernel methods—specifically those based on the RKHS norm and kernel trace—through a data-dependent kernel called the loss path kernel (LPK). Unlike static kernels such as NTK, the LPK captures the entire training trajectory, adapting to both data and optimization dynamics, leading to tighter and more informative generalization guarantees. Moreover, the bound highlights how the norm of the training loss gradients along the optimization trajectory influences the final generalization performance. The key technical ingredients in our proof combine stability analysis of gradient flow with uniform convergence via Rademacher complexity. Our bound recovers existing kernel regression bounds for overparameterized neural networks and shows the feature learning capability of neural networks compared to kernel methods. Numerical experiments on real-world datasets validate that our bounds correlate well with the true generalization gap.

Generalization Bound of Gradient Flow through Training Trajectory and Data-dependent Kernel
Yilan Chen', Zhichao W Wei Huang 4.5 Andi Han Taiji Suzuki Arya Mazumdar* University of California San Diego University of California Berkeley
International Computer Science Institute RIKEN AIP
5 The Institute of Statistical Mathematics The University of Sydney The University of Tokyo
yic031@ucsd. edu; zhi zhac. waaaaawwwnbbbeeeegg. edd; wei huang vr@riken. jj; andi han@sydney edu. au; taiji@mist.. i. u-tokyo ac. jp; arya@ucsd. edu;
Abstract
Gradient-based optimization methods have shown remarkable empirical success, yet their theoretical generalization properties remain only partially understood. In this paper, we establish a generalization bound for gradient flow that aligns with the classical Rademacher complexity bounds for kernel methods-specifens based on the RKHS norm and kernel trace-through data dtta-dependent kernel called the loss path kernel (LPK). Unlike static kernels such as NTK, the LPK captures the entire training trajectory, adapting to both data and optimization dynamics, leading to tighter and more informative generalization guarantees. Moreover, the bound highlights how the norm of the training loss gradients along the optimization trajectory influences the final generalization performance. The key technical ingredients in our proof combine stability analysis of gradient flow with uniform convergence via Rademacher complexity. Our bound recovers existing kernel regression bounds for overparameterized neural networks and shows the feature learning capability of neural networks compared to kernel methods. Numerical experiments real-world datasets validate that our bounds correlate well with the true generalization gap.
those
Introduction
Gradient-based optimization lies at the heart of modern deep learning, yet the theoretical under- standing of why these methods generalize so well is still incomplete. Classical bounds attribute the generalization of machine learning (ML) models the complexity of the hypothesis class 62 which
fails to explain the power of deep neural networks (NNs) with billions of parameters [1 14] Recent
studies reveal that the training algorithm, data distribution, and network architecture together impose an implicit inductive bias, effectively restricting the vast parameter space to a much smaller "effective 59 21]. This observation motivates the need for algorithn--dppnnent generalization bounds ones that capture how gradient-based dynamics carve out the truly relevant portion of the hypothesis class during training.
region" " that improves the generalization ability [3 48 60
A variety of theoretical frameworks have been proposed to address this challenge. Algorithmic stability [66] bounds the generalization error by the stability of the learning algorithm. Hardt et al. 29 first proved the stability of stochastic gradient descent (SGD) for both convex and non- convex functions. However, these bounds are often data- indeeedddde,,,t,, require decaying step sizes for non-convex objectives, and grow linearly with training time. Moreover, for non-convex functions, full-batch gradient descent (GD) is typically considered not uniformly stable 29
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(a) Cross entropy loss
(b) Generalization gap & bound
2.5
2.00
Generolization
1.75
1.75
8
1.5
train loss
1,25
1.25
loss
1.0
0.75
0.75
0.50
0.5
0.0
0.00
0.00
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
0.0
2.5
5.0
7.5
10.0
12.5
25.0
17.5
20.0
Figure I: ResNet trained by SGD on full CIFAR-IO. (a) NN's training loss, test loss, and test error. (b) The generalization bound we derive in Theorem 5.4 correlates well with the true generalization gap.
Information- -heeoretict (IT) approaches [58 66 30 bound the expected generalization error with
the mutual information between training data and learned parameters. To control this, researchers introduce noise into the learning process, employing techniques like stochastic gradient Langevin
dynamies (SGL.D) (57 46 (4 or perturb parameters [47]. The PAC-Bayesian framework [39 [26
bounds the expected generalization error by the KI. divergence between the model's posterior and prior distributions. To establish
moorithmmddepndern bounds, they also consider gradient descent with continuous noise like SGLD 45 36), similar to the IT approach. But these noise-based approaches can diverge from SGD and their bounds can grow large when the noise variance is small.
In this work, we propose novel perspective that combines stability analysis of gradient flow with uniform convergence tools grounded Rademacher complexity. Specifically, we utilize a connection between loss dynamics and loss path kernel (LPK) proposed by Chen et al. (20. By studying the stability of gradient flow, we show the concentration of LPKSs trained with different datasets. This allows us to construct function class explored by gradient flow with high probability while being substantially smaller than the full function class, leading to a tighter generalization bound. We summarize main contributions follows.
We prove (1//n) stability for gradient flow on convex, strongly-convex, and non-convex losses, where n is the number of training samples, and show that, as a result, LPKs concentrate tightly, This localization dramatically shrinks the effective hypothesis class and leads tighter bound than the previous result of Chen et al. (20).
Using the above results, we derive generalization bound for gradient flow that parallels classical Rademacher complexity bounds for kernel methods -speciiiiisy those involving the RKHS norm and kernel trace [10]- -but adapts to the actual training trajectory. The generalization gap is controlled by an explicit term I, determined by the norm of the training loss gradients along the optimization trajectory. A similar bound is also proved for stochastic gradient flow.
Our bound recovers known results in the NTK regime and kernel ridge regression, and exposes the feature-learning advantage of NNs. Extensive experiments on real-world datasets show that our bound I correlates tightly with the true generalization gap (Fig.
2 Related Work
Generalization theory deep learning. Generalization has long been a central theme in deep learning theory, and various techniques have been proposed to study it. Beyond the algorithmic stability, PAC-Baycsian, and frameworks discussed carlier, Bartlett et al. [12] obtained tight bounds for the VC dimension of ReLU networks. Other works measure network capacity via norms, margins 10, 49 I (22. or sharpness-bast metrics [50]
to explain why deep NNs can generalize
despite their large parameter counts.
Agorrthmm-dependen generalization bound. PAC-Bayesian, stability-based and IT approaches can all yield algorithm-dependee bounds. Li et al. [36] combine PAC-Bayesiaa theory with algorithmic stability to derive an expected bound for SGLD that depends on the expected norm of the training loss gradient along the trajectory, which is similar our bound, yet the bound blows up as the injected noise vanishes. Neu al. [47 use mutualiinformation arguments to control the expected gap by the local gradient variance. Nikolakakis et al. (54) analyze the expected output stability to get an

---

expected generalization bound for full-batch GD on smooth loss that depends on the training loss gradient norm along the trajectory and the expected optimization error. In contrast, our result is high-probability miiforn-convergence bound whose leading term is not only tighter but is also straightforward to compute. Amir et al. 3 study generalization bounds for linear models trained by gradient descent on convex losses by constructing function class centered around the expected trajectory, whereas our approach handles more general losses and models.
Neural tangent kernel (NTK) and feature learning. There is a line of work showing that over- parameterized NNs trained by GD converge to a global minimum and the trained parameters are so-called NTK regime. Arora et al. [5] study the generalization capacity of ultra-wide two-layer NNs trained by GD and square loss, while Cao & Gu [17] examine the generalization of deep. ultra-wide NNs trained by SGD and logistic loss. Both establish generalization bounds of trained NNs, but NNs perform like a fixed kernel machine in this case. Going beyond the NTK regime, recent works 7 15 27 9
close to their initialization 33 25
24
2
6
23 43 have explored feature learning of NNs trained by GD for efficiently learning low-dimensional features which outperform the fixed kernel. Our approach is considerably more general and not restricted to overparameteriieed NNs. We present our bound in these two regimes as case studies in Sec.
3 Notation and Preliminaries
Consider a supervised learning problem where the task is to predict an output variable in y S Te
using vector of input variables in X' S Rd. Let 2 & X' x V. Denote the training set by { 2 |= with z; - (I,, y1) E Z. Assume each point is drawn i.i.d. from a distribution Let
S A
X [ [m,] E Rdd Y Wi .yn] E R***, and Z Y| E (dd-))xn.
We express a NN as f(w, x) R' x Rd + RA, where w are its trainable parameters and x is an input data. A learning algorithm A Z" + Rº takes training set S and returns trained parameters w. The ultimate goal is to minimize the population risk (,( _ Ezzz [(( =)] where f(w, 2) - {(s(wr, x), y) is loss function. We assume f(w, z) E [0, 1]. In practice, since the distribution μ is unknown, we instead minimize the empirical risk on the training set S: (sw A 1 >i. f(w, z.). The generalization gap is defined as (w) Ls(w),
Below, we recall the definition of Rademacher complexity and generalization upper bound.
Definition 3.1 (Empirical Rademacher complexity Rg( Let F be hypothesis class of functions from X to R* Let G be the set of loss functions associated with functions in F, defined by g = {g: (xr, y) + ((f(()) y), E F). The empirical Rademacher complexity of g with respect to sample S = {z1...., 2,, } is defined as (g) = E. [sup,es Ei (z))). where o = (o1....,o,,) is a sample of independent uniform random variables taking values in {+1, 1111.-1.-- and E. is the expectation over conditioned on all other random variables.
1},
Theorem 3.2 (Theorem 3.3 in [41). Let G be a family of functions mapping from Z to [0, 1]. Then for
any ò (0, 1), with probability at least 8 over the draw of an i.i.d. sample set S = [21, 2n).
the following holds for all E 9: Ez [9(x)] - 31
< (g) + 33
log(2/4)
2n
3.1 Kernel Method and Loss Path Kernel
Recall that a kernel is a function K : X x X + R for which there exists a mapping $ X -> H into a reproducing kernel Hilbert space (RKHS) H such that K K(x, x²) = (o(x), + (x)))x for all x, x E X. where (, denotes the inner product in H. A function K is a kernel if and only if it is symmetric and positive definite (Chapter 4 in (61). A kernel machine g X + R is linear function in H.and can be written as g(x) (,8, (xx)) + b, where its weight vector 3 is a linear combination of the training points B E a, (xx)) and b is constant bias. The RKHS norm of
g is ||gll n | (,,0(x)())) v Ev,s a,a, K (x, æ,)) The kernel machine with bounded RKHS norm has a classic Rademacher complexity bound as follows:
Lemma 3.3 (Lemma 22 in [00). Denote a function class F= (=(())== Eie a,K (x, 2;) n e
N, ar, X, Eig a,a, K K( v.y) S B²) for constant B > 0. Then its Rademacher complexity is bounded by Rs(F) < B Di=1 (x),
3

---

Next we introduce the loss path kernel, which calculates the inner product of loss gradients and integrates along a given parameter path governed by (stochastic) gradient flows. Previous NTK theory cannot fully capture the training dynamics of NNs since trained parameters could move far away from initialization. The loss path kernel addresses this limitation by capturing the entire training trajectory.
Definition 3.4 (Loss Path Kernel (LPK) Kr in (0]). Suppose the weights follow continuous path w(t) [0. T - IEP in their domain with a starting point (0) wo. where 7 is predetermined constant. This path determined by the learning algorithm A, the training set S, and the training time T, i.e. w(t)= As)) We define the loss path kernel associated with the loss function E(w,, 2) along the path as
S
(z z1;8) (2)
2 x')) dt.
LPK is a valid kernel by definition. Intuitively, it measures the similarity between data points 2 and z' by comparing their loss gradients and accumulating over the training trajectory.
3.2 Loss Dynamics of Gradient Flow (GF) and Its Equivalence with Kernel Machine
Consider the GF dynamics (gradient descent with infinitesimal step size):
(t) = v (iols((o(()
Σ v (wl((w()) 2.). 1=1
dl
Chen et al. (20) showed that the loss of the NN at certain fixed time is a kernel machine with LPK
plus the loss function at initialization: ((WT,=)
Σx= - (;;) f(wo, Here, the
LPK is a data-dependent kernel that depends on the training set S. Using this equivalence, define the following of LPKs and the function class of the loss function
Kr A (Kr():8')= S' supp(u ""),
Σ 4
Kr(tl $B))
B²),
n?
Gr a (((A)())))))
Σ K(z,2 S²) flwo. z) K(, E krr)
(1)
where B >> 0 is some constant, S' 3
= izi...., 3 8n is the joint distribution of n i.idd samples drawn from μu, Su) @n) is the support set of n and (S') the parameters obtained by GF algorithm at time T and trained with S'. Then Chen al. (20] derived the following generalization bound:
B sup Tr(K(Z, Z,8") Σ A 2z),
Rs(GT) <
where AZz,, zz) SuPK( K(2112z88) - inf ((=K((.- K(z;, Zyj ST). However, the above bound suffers from several limitations: 1) involves supremum over an infinite family of LPKs, making it intractable to compute in practice; 2) The term Σiş, A(zi, 2z) can be large as O(n²) the worst case, leading loose bound: 3) The bound must be evaluated on datasets distinct from the training set, limiting its practical applicability. In this paper, we use the stability property of GF substantially reduce the size of the function class, resulting generalization bound that depends only on the training set. Our new bound matches the classical kernel method bound in Lemma 3.3] but instead of relying on fixed kernel, it utilizes the data- dependent loss path kernel. Adapuig to the data and algorithm, this learned kernel can outperform static kernels in traditional methods, thereby achieving improved generalization performance.
significantly tighter
Uniform Stability of Gradient Flow and Concentration of LPKs
In this section, we show that GF is uniformly stable. This uniform stability property implies the LPK concentration and connects LPKs trained from different datasets. Instead of transforming the stability generalization bound directly, we then combine the stability analysis with uniform convergence via Rademacher complexity to get data-dependent bound in Sec.

---

4.1 Uniform Stability of Gradient Flow
Definition 4.1 (Uniform argument stability [6 13). A randomized algorithm A en -ninfooryll argument stable if for all datasets S, z" such that they differ by at most one data point, we have EA [[]-A(S) A(sto)]] S En, where the expectation is taken over the randomness of A.
Here we consider the uniform argument stability, which can be easily transformed to uniform stability with respect to loss if the loss function is Lipschitz. In this paper, we mainly consider full-batch GF so there is randomness in A. To analyze the GF dynamics and LPKs, we make the following standard assumptions.
Assumption 4.2. Assume f(w, is L- L-Lipschitz and 3-smooth with respect to w, that is, w w'll and || ww(ww.) V Vwl(w', ,-)l w| w'll.
[[((w,-) ((w',
Let and ( be two datasets that differ only in the i-th data point. We prove the following stability results of GF for convex, strongly convex (S.C.), and non-convex losses. Similar stability results of GD (for convex case) and SGD were proved
Lemma 4.3. Under Assumption 4.2 for any two data sets S and S(), let w: = As(S) and wo = )s((())) be the parameters trained from same initialization we = w/y then
2L yu
Ls(w) is y.S.C. Ls(w) is convex,
[w;, w//l S
2L1
(e 3n
1), Ls(w) non-conver.
For convex losses, uniform stability increases linearly with T. For strongly convex losses, it holds without increasing with training time. Unfortunately, for non-convex losses, the bound exponentially increases with time T in the worst case, leading to exponential stability generalization bound. Our
Theorem 5.2 5.2orremm522aaa avoids this case by combining stability analysis with Rademacher complexity.
For non-convex loss, Hardt et al. [29] obtain ((T/n) stability bound of SGD with decayed learning rate 7 c/t, which is equivalent to training eln time our case since Σ, e/t eln T. In our
case, using a learning rate of 1) = 1/3(1 1) will allow us to have ||uт - w/yll
21.
3n
4.2 Concentration of LPKs under Stability
We now derive useful concentration properties of LPKs using uniform stability. These properties will be used when defining the function class explored by GF and proving the generalization bound. First of all, one can show that the LPK concentrates for fixed pair of z, z'.
Lemma 4.4. Under Assumption 4.2 for any fixed z', with probability at least 1 - 5 over the randomness of S',
AL.ST
In Zn
Ls(w) is 7-S.C.,
(r(2,22'88) =T(
S
21. 3T2
In
Ls(w) is convex,
2n
BT
-3T
In 1)
Ls(w) is non-comex.
B
2n
Next, using stability argument and Chernoff bound, able to bound the difference between Ei= Kr(z,, 2, S²) and Σn= Kr (2i, S).
Lemma 4.5. Under Assumption 4.2 for two datasets S and S', with probability at least 8 over the randomness of S and S',
Ö(TV)). Ls(w) is s-C.. O(T² Ls(w) is conver, O vn), T.((w) is non-convex.
Kr(zi, 2;:
Σ KT(
5
'However, training with a decayed learning rate may not converge and requires to change the definition of the LPK. Therefore, stick to the constant learning rate.
5

---

Table The rate of in Theorem 5.2 under different training time T scales. Boldface indicates the cases where I' computed by 3 is the dominant term compared with e.
T
(
O vn)
O(vn)
O(n)
S.C.
(m-3//4)
Ó ((n-3/4)
Ö(n-1/1)
Convex
O(n-3/4) Ö(n 3/4)
Ö(n 3/4)
O(n
0(1)
Non-convex
Ö(n
((n-1/4)
0(1)
5 Main Results
5.1
Generalization Bound of Gradient Flow (GF)
With the above preparations, we are ready to prove our generalization bound. We define the loss function class Gr as in ① at time T by constraining the LPK class Kr as follows
Kr - (K)(;;))): n² Σ Kr 2/: S B², E E S supp(u &n), sup
S }}
where B, > 0 are some constants and S' is subset of supp( Note this function class includes E( (S)r(S)) if the conditions are satisfied on S. For example, the first condition is satisfied improve the Rademacher complexity
if 1/2 Σx, KT zy: S B². For this function class, below since the conditions in Kr significantly reduce the size of the function class.
Lemma 5.1. Recall Definition 3.1 for RG(GT), we have
B sup Kr(vs))E
Rs(9T) 5
(z; + 4&v 6n In 2n + 8A.
As we have shown above, the conditions in the function class are satisfied with B being some data- dependent quantity, and the trace we can prove our main result of the generalization bound for GF dynamics.
be bounded in Lemma 4.5 With covering argument,
Theorem 5.2.
Denote by r 3 E Σj= 2,;88 E Kr(z,, 8); Under As-
sumption 4. 4.2 with probability at least 1 over the randomness of S,
(A((A(S)) (is(Ar(S)) ( + In(4n/0)
(2)
2n
S.C.,
where e
min L
T
O
cOnvex,
min
non-conver.
We now study which term in (2) dominates the bound in Theorem 5.2 for different training scaling of T in Table T A rough analysis implies that the first term I in the bound can be upper bounded by O Sec. shows I' typically grows sub-linearly for T the training loss converges sufficiently fast. Remark 5.3 (Leading order for non-convex case). For the non-convex case, when T O(1), -3/44 and when T O(In /Ti, = 11221 In these cases, has faster-decreasing rate compared with other terms. When T 2(In vn), e O(VT/((/) which has rate similar to T. Especially, when the loss non-convex but satisfies the folyak-t.ojasiewice (PI.) condition with parameter o, L.s [s(w.: Ls(w=) I e (Ls(wa) Is(w")) )), T O In /n) is sufficient to achieve 0(1/ optimization error.
We summarize the rate of e
In many cases, I may not achieve this upper bound;

---

Our results show that the generalization ability of GF is mainly affected by the first term F, which can also be rewritten as
r 2 n
T V
Ls(wo) Ls (WT)
Σ
Vi dl,
(3)
due to the definition of LPK and dLs(w:) Vw (w..s(W,,TT dee: = - -IV Lis uz
This
d5
de
bound matches the Radamecher bound of the classic kernel methods in Lemma 3.3 In т,
V nt - (r, S): serves as the RKHS norm of the kernel, while Σ Kr S):S)
the trace of the kernel. The RKHS norm in setting remains below 1 due the bounded loss.
Unlike a kernel method with a fixed kernel, GF learns a data-dependent kernel LPK, thus adapting the underlying feature map to the training set. Consequently, our bound can surpass the fixed-kernel scenario because the gradient norms | (. Il V V.. f, 2,)] shrink during training- wheeres fixed kernel's bound remains static. Moreover, the RKHS norm here stays below in contrast to fixed-kernel methods, whose RKHS norm may grow with the sample size or dimensionality (see Corollary 6.2). Overall, our bound highlights that more favorable optimization landscape and faster convergence can promote stronger generalization.
5.2
Generalization Bound of Stochastic Gradient Flow (SGF)
Above, we derived a generalization bound for NNs trained from full-batch GF. Here we extend analysis SGF and derive corresponding generalization bound. To start with, recall the dynamics of SGF (SGD with infinitesimal step size):
dw; V w (wi))
Σ
Vell(ur. 21)
(4)
dt
iES,
where S, C (l,.... n is the indices of batch data used in time interval [t, t + 1] and |S,] = m is the = - (Vol(wr, z), Vww(w,, (',,,',,)))))))))))))))))))))( x²)) dt to be the LPK over time batch size. Define (z,4+1 x2; interval [t, t 1 1].
Theorem 5.4. Under Assumption 4.2 for fixed sequence Soy...,ST- with probability at least
1 - over the randomness of S, the generalization gap of SGF defined by (4) is upper bounded by
2
Kr,41 2); Ō T Σ
Ty (Ar(8)) - (s(AA(()) S
Σ iJES.
(Z,,
Similarly, we define the first term I' for the SGF case. When S. = S. SGF becomes GF and the bound becomes similar to (2). This bound can be extended to any random sampling algorithm by taking the expectation over the randomness of the algorithm.
6 Case Study
6.1 Overparameterizzed Neural Network under NTK Regime
The NTK associated with the NN f(w,x) at is defined by é(w; x. x')
Vw fww, Vw x'TT E R Since the LPK has natural connection with NTK, our bound
(3) 2 [s(ww)) Ls(wr) (WT) Ei=1 T
can be calculated using the NTK during the training: r
Vyl(w,, 2.) x.) ) V Vyl(w,, zi) When the output di- 1 Ilf( X) - ylll= as previous work 25 24 showed, as long as the smallest eigenvalue of NTK is lower bounded from the training loss
mension k = 1 and using a mean-square loss Ls(w)
2n
enjoys an exponential convergence, [ X)- - y < e
انmi [[ X) yll In this setting, the generalization can be upper bounded by the condition number of the NTK as follows.
Corollary 6.1. Suppose that Amax (Ó( X, X)) < Amaz and Amina Ô Ww; X, X)) Amin 0.for t E []. Then
2Amax (1 X) 211² (1
Amin 78
7

---

This bound shows that the generalization of overparameterized NNs depends on the condition number of the NTK. With a smaller condition number, the network converges faster and generalizes better. This bound is always upper-bounded even when 7 - oc. As n/T increases, the bound decreases. Since Ilf X) yll² = (n) for NTK initialization
and e
2h
2Amin"' our bound
( has a faster rate than O Amaax T/n). When Ann = O(1,, our bound has a rate of O
22
Aui
For overparameterized NNs, NTK does not change much from initialization, hence Amax and Amin can be specified using the Amax (Ō(wg; X.X) X)) and Aunn Amin (www;; X, X)), see [2 24
53
44
65
6.2 Kernel Ridge Regression
Given kernel K(x,, x²) (0(x)), (()))) where Φ Rd + RP, consider kernel ridge re- gression f(w, x) w T ((x)) with Ls(w)) 2n (x) T w - y 12 ||w/|² and f(w, z) = {w (xx) y)² + Σ ||ll1 where ((X) I2px and w IP. Denote the optimal solution as w* = (x) K X) + AIn) y. Then we have the following bound for the kernel regression.
Corollary 6.2. Suppose K K(xi, x3)) S Kmax for all i [n]] and K(X, X) is full-rank. We huve that
1 AVVKnn max 1w0 - -w ())) (wo w0)l when = 0, when 0, Wa O.
n 1. LLVKmas V U (K(X, x)) |By/l
(5)
Here (5) recovers the Rademacher complexity bound for kernel regression 15]. Compared with
the classic bound in Lemma 3.3 when ||l|| S vn, (5) is tighter since Kmax S Ee K(,,, x.). In the high-dimensional regime, if w" is standard Gaussian and wy = 0, 5 has a rate of 0 ((vp/n). Similar rates can be found in 37 38 for fixed kernel regression.
6.3 Feature Learning
Consider single-index model y = f-((0" =)) +G. where 0 E Sdd is fixed unit vector, data æ N(O0, La). f. is an unknown link function, and g ~ NO o0) is independent Gaussian noise. The sample complexity of this problem is usually (dd) 7 15 or (dd/22 23 where s is the information exponent of f., defined as the smallest nonzero coefficient of the Hermite expansion of fa. Bietti al. [15] trained two-layer NN with gradient flow to learn this single-index model. Specifically, the max(0, u} is the ReLU
N NN is f(0, x) J Ei= cola, (0, x) b,). where 0 E S ( activation function, bq- ~ 70) with r > 1 are random biases that are frozen during training, and 0, random Rademacher variables. Let Ls(0, c) = E>=(f( c, y1)² + |||| be regularized squared loss. The NN is trained by a two-stage gradient flow:
d0,
gd- (s((0,, ct),
de:
1(1 Vcs
dt
dt
where god is the Riemannian gradient on the unit sphere, To = (dd-11) and s is the information exponent. They show that n = ② (d+ Nddd is sufficient to guarantce weakly recovering the feature vector 0- Here compute our bound in their setting.
Corollary 6.3. Under the settings of Theorem 6.1 in Bietri et al. [15] (provided in Theorem G.2
0
(V
di+1
+ x2d
nx²
with high probability as n, - co. As long as x oa(1/ (1/// and (t(d(+2), r on,a(1). n )à, we have I' < ò (nd)+2/n)*)
Taking X 0( -
Our bound is compatible with the requirements of Õi(d + N)d=-1/2*) in Bietti al. 15]. The sample complexity of n +2) almost matches the correlational statistical query (CSQ) lower bound n {d))) 22 and outperforms the kernel methods that require n = (dP)) where p the degree of the polynomial of f. (s < p). Compared with Corollary 6.2 the bound of I in the feature learning case is vanishing, while the bound in (5) (1), indicating the benefits of feature learning from the generalization gap bound.
8

---

(a) Logistic loss
(b) Generalization and bound (log scale)
1.2
train loss
10a
1.0
test loss
10a
0.8
102
10
10a
Generalization
10-1
Norn-based bound
0.0
10
60
80
Figure 2: Experiment (I). Two-layer NN trained by gradient descent CIFAR-10 cat and dog. (a) shows NN's 's training loss, test loss, and test error. (b) shows that the complexity bound I in Theorem (5.2 captures the generalization gap (wr) (WTr) well. It first increases and then converges after sufficient training time.
7 Numerical Experiments
We conduct comprehensive numerical experiments to demonstrate that our generalization bounds correlate well with the generalization gap. For more simulations and details, the Appendix.
(I) Generalization bound of gradient flow in Theorem 5.2 Fig. 2 we use logistic loss to train a 4000 CIFAR-10 cat and dog (35) data by full-batch gradient descent and compute r, the main term in our bound. The integration in D is estimated with Riemann sum. After training, the norm-based bound Bartlett et al. 11 is 12557.3, which is much larger than our bound, as shown in the figure.
two-layer NN of 400 hidden nodes and Softplus activation function for binary classification
(II) Generalization bound of SGF in Theo- rem 5.4 In Fig. [ we train a randomly initial- ized ResNet 18 by SGD on full CIFAR-10 10
35
Gemeralization gap
and estimate in our bound. Fig. the Appendix show more experiments ResNet 34 and two-layer NNs. Our generalization bound characterizes the overfitting and feature unlearn- ing behavior 43 of overparameterized NNs af- ter long-term training (when T Onn) in Theo- rem (.2).
5 and in
2.0
0.0
0.2
0.4
0.6
0.8
10
(III) Generalization bound with label noise. We corrupt the labels the experiment (I) with ran- dom labels and plot the generalization gap and r in Fig. captures the generalization gap well and increases with the portion of label noise,
Portion label nosie
Figure 3: Generalization gap and our bound with label noise.
plaining the random label phenomenon (67). This behavior follows naturally: noisier labels force larger norm of loss gradients during training, which directly inflates T and generalization gap.
8 Conclusion and Future Work
In this paper, by combining the stability analysis and uniform convergence via Rademacher com- plexity, we derive a generalization bound for GF that parallels classical Rademacher complexity bounds for kernel methods by leveraging the data-dependent kernel LPK. Our results show that NNs trained by GF may outperform fixed kernel by learning data-dependent kernels. Our bound also shows how the norm of the training loss gradients along the optimization trajectory affects the generalization. Recently, Montanari & Urbani [43] applied dynamical mean-fiell theory (DMFT) to two-layer NNs and showed that GF exhibits three distinct phases-as an initial feature-learning regime
(T = (1)), )) a prolonged generalization plateau, and late overfitting phase (T O(n)) (Fig 2 Our bound (Theorem 5.2) reproduces similar qualitative behavior. Unlike the mean-field analysis, our approach applies to general architectures and data distributions. promising direction is integrate the DMFT's phase- thase-wise insights with our LPK framework obtain finer generalization guarantees.

---

For practice-relevatt applications, by monitoring the evolution of our bound I during training, one can predict the overfitting for overparameterized NNs and identify optimal stopping time for training without access test data 3. Our I can also serve as a proxy to compare model architectures in Neural
Architecture Search (NAS) [55
20
For future directions, extending the analysis to GD and SGD with large learning rates can bring the bound closer to practice. Second, our analysis uses function class larger than Gr when bounding the Rademacher complexity. Refining this step could further tighten the bound.
Acknowledgments
Yilan Chen and Arya Mazumdar supported by NSF TRIPODS Institute grant 2217058 (En- CORE) and NSF 221 7057 (TILOS). Zhichao Wang was supported by the NSF under Grant No. DMS-1928930, while he was in residence at the Simons Laufer Mathematical Sciences Institute in Berkeley, California, during the Spring 2025 semester. Wei Huang was supported by JSPS KAK- ENHI (24K20848) and JST BOOST (JPMJBY24GG) Taiji Suzuki partially supported by JSPS KAKENHI (24K02905) and JST CREST (JPMJCR2015).
References
[1] Abbe, E., Adsera, E. B., and Misiakiewicz, T. Sgd learning on neural networks: leap complexity and saddle-to-saddle dynamics. In The Thirty Sixth Annual Conference Learning Theory, pp. 2552-2623. PMLR, 2023.
[2] Allen-Zhu, Z., Li, Y., and Song. Z. convergence theory for deep learning via over- parameterization. In International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
[3] Amir, I,, Livni, R., and Srebro, N. Thinking outside the ball: Optimal learning with gradient descent for generalized linear stochastic convex optimization. Advances Neural Information Processing Systems, 35:23539-233 225550,, 2022.
[4] Arora, S., Ge, R., Neyshabur, B., and Zhang, Y. Stronger generalization bounds for deep nets via a compression approach. arXiv preprint 180.::180..05220 2018.
[5] Arora, S., Du, S., Hu, W., Li, Z., and Wang, Fine- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
[6] Arora, S., Du, S., Hu, W., Li, Z., Salakhutdinov, R., and Wang, On exact computation with an infinitely wide neural net. Advances in Neural Information Processing Systems, 32, 2019.
[7] Arous, G. B., Gheissari, R., and Jagannath, A. Online stochastic gradient descent non-convex losses from high-dimensional inference. Journal of Machine Learning Research, 22 22(106):1-51, 2021.
[8] Awasthi, P., Frank, N., and Mohri, M. On the rademacher complexity of linear hypothesis sets. arXiv preprint arXiv:2007.11045 2020.
[9] Ba, J., Erdogdu, M. A., Suzuki, T., Wang, Z., Wu, D., and Yang, G. High- nigh-dimenssonal asymptotics of feature learning: How one gradient step improves the representation. Advances Neural Information Processing Systems, 35:37932-37946, 2022.
[10] Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov)443-488, 2002.
[11] Bartlett, P. L.. Foster, D. J., and Telgarsky, M. Spectrally-normaalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
[12] Bartletr, P. L., Harvey, N., Liaw, C., and Mehrabian, A. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2255-2311 2019.
10

---

[13] Bassily, R., Feldman, V., Guzmán, C., and Talwar, K. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381 1-3391, 2020.
[14] Belkin, M., Hsu, D., Ma, S., and Mandal, S. Reconciling modern machine-learning practice and the classical biri-variance trade-off. Proceedings of the National Academy of Sciences, 116632):1584--15854, 2019.
[15] Bietti, A.. Bruna, J., Sanford, C.,, and Song, J. Learning single-index models with shallow neural networks. Advances in Neural Information Processing Systems, 35:9768 -7883, 2022.
[16] Bousquet, O. and Elisseeff, A. Stability and generalization. The Journal of Machine Learning Research, 1:499-526, 2002.
[17] Cao, Y. and Gu, Q. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.
[18] Charles, 7. and Papailiopoulos, D. Stability and generalization of learning algorithms that converge to global optima. In International conference on machine learning, pp. 745-754 PMLR, 2018.
[19] Chen, W., Gong, X., and Wang, Z. Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective. arXiv preprint arXiv:2102.11555. 2021.
[20] Chen, Y., Huang, W., Wang, H., Loh, C., Srivastava, A., Nguyen, L. M., and Weng, T.-W. Analyzing generalization of neural networks through loss path kernels. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL httpttt//ppeeereiiss. est//oorum?dd-Baa///
[21] Chizat, L. and Bach, F. Implicit bias of gradient descent for wide two-layer neural networks trained with the logistic loss. Conference on Learning Theory, pp. 1305-1338. PMLR, 2020.
[22] Damian, A., Lee, J., and Soltanolkotabi. M. Neural networks can learn representations with gradient descent. In Conference on Learning Theory, pp. 5413-5452. PMLR, 2022.
[23] Damian, A., Nichani, E., Ge, R., and Lee, J. D. Smoothing the landscape boosts the signal for sgd: Optimal sample complexity for learning single index models. Advances in Neural Information Processing Systems, 36, 2023.
[24] Du, S., Lee, J., Li, H., Wang, L., and Zhai, X. Gradient descent finds global minima of deep neural networks. In International conference machine learning, pp. 1675-1685. PMLR, 2019.
[25] Du, S. S., Zhai, X., Poczos, B., and Singh, A. Gradient descent provably optimizes 2018.
parameterized neural networks. arXiv preprint
[26] Dziugaite, G. K. and Roy, D. M. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: 1008, 2017.
[27] Frei, S., Chatterji, N. S., and Bartlett, P. L. Random feature amplification: Feature learning and generalization in neural networks, Journal of Machine Learning Research, 24(303):1-44 2023.
[28] Gunasekar, S., Lee, D., Soudry, D.,, and Srebro, N. Implicit bias of gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems, 31, 2018.
[29] Hardt, M., Recht, B., and Singer, Y. Train faster, generalize better: Stability of stochastic gradient descent. International conference on machine learning, pp. 1225-1234. PMLR, 2016.
[30] He, H. and Goldfeld, Z. information-theoredt generalization bounds for deep neural networks. arXiv preprint arX1v:2404.03176, 2024.

---

[31] He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778. 2016.
[32] Jacot, A., Gabriel, F,, and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
[33] Keskar, N. S., Mudigere. D., Nocedal, J., Smelyanskiy, M., and Tang. P. T. P. On large- batch training for deep learning: Generalization gap and sharp minima. arXiv preprini 1609: 04836, 2016.
[34] Krahmer, F., Mendelson, S., and Rauhut, H. Suprema of chaos processes and the restricted isometry property. Communications on Pure and Applied Mathematics, 67(11):1877-1900 2014.
[35] Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
[36] Li, J., Luo, X., and Qiao, M. On generalization error bounds of noisy gradient methods for non-convex learning, arXiv preprint 1etp:000200001111 2019.
[37] Liang, T. and Rakhlin, A. Just interpolate: Kernel "ridgeless" regression can generalize. 2020.
[38] Liang T., Rakhlin, A., and Zhai, X. On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels. In Conference Learning Theory, pp. 2683-2111 2711. PMLR, 2020.
[39] Maurer, A. A note the pac bayesian theorem, arXiv preprint cs/0411099, 2004.
[40]
Mellor, J., Turner, J., Storkey, A., and Crowley, E. J. Neural architecture search without training. In International Conference on Machine Learning, pp. 7588-7598. PMLR, 2021.
[41] Mohri, M., Rostamizadeh, A., and Talwalkar, A. Foundations of machine learning. MIT press, 2018.
[42] Mok, J.. Na. B., Kim, J.-H., Han, D., and Yoon, S. Demystifying the neural tangent kernel from a practical perspective: Can it be trusted for neural architecture search without training? In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp- 1 11861-11870, 2022.
[43] Montanari, A. and Urbani, P. Dynamical decoupling of generalization and overfitting in large two-layer networks. arXiv preprint arXiv:2502.22126. 2025.
[44] Montanari, A. and Zhong, Y. The interpolation phase transition in neural networks: Mem- orization and generalization under lazy training. The Annals of Statistics, 5065):2816-2847, 2022.
[45] Mou, W. Wang. L., Zhai, X., and Zheng, K. Generalization bounds of sgld for non-convex learning: Two theoretical viewpoints. In Conference on Learning Theoory pp. 605-638. PMLR, 2018.
[46] Negrea, J., Haghifam, M., Dziugaite, G. K., Khisti, A., and Roy, D. M. -nformation-thhorctiic generalization bounds for sgld via data-dependent estimates. Advances in Neural Information Processing Systems, 32, 2019.
[47] Neu, G., Dziugaite, G. K., Haghifam, M., and Roy, D. M. Information-theerrtic generalization bounds for stochastic gradient descent. In Conference on Learning Theory, pp. 3526-3545. PMLR, 2021.
[48] Neyshabur, B., Tomioka, R., and Srebro, N. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 14/2.6614 2014.
[49] Neyshabur, B., Tomioka, R., and Srebro, N. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLR, 2015.
12

---

[50] Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, deep learning, Advances in neural information processing systems, 30, 2017.
N. Exploring generalization in
[51] Neyshabur, B., Bhojanapalli, S., and Srebro, N. A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. arXiv preprint arXiv
2017.
[52] Neyshabur, B., Li, Z., Bhojanapalli, S., LeCun, Y., and Srebro, N. The role of over- parametrization generalization of neural networks. International Conference on Learning Representations, 2019. URL htttps://openrevieii: http::/:/pppaaeeeeeeeeeesrrrrrra ByggggghAA
[53] Nguyen, Q., Mondelli, M., and Montufar, G. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks. In International Conference on Machine Learning, pp. 8119-8129, PMLR, 2021.
[54] Nikolakakis, K. E.,, Haddadpour; F., Karbasi, A., and Kalogerias, D. Beyond lipschitz: Sharp generalization and excess risk bounds for full-batch gd. arXiv preprint arXiv:2204. /2446, 2022.
[55] Oymak, S., Li, M., and Soltanolkotabi, M. Generalization guarantees for neural architecture search with train-validation split. In International Conference on Machine Learning, pp. 8291-8301. PMLR, 2021.
[56] Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[57] Pensia, A., Jog, V., and Loh, P.-L. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 546-550. IEEE, 2018.
(58) Russo, D. and Zou, J. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pp. 1232-1240. PMLR, 2016.
[59] Savarese, P., Evron, I., Soudry, D., and Srebro, N. How do infinite width bounded norm networks look in function space? In Conference Learning Theory, pp. 2667-2690. PMLR, 2019.
[60] Soudry, D., Hoffer, E.,, Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 1981)22222-2878. 2018.
[61] Steinwart, I. and Christmann, A. Support vector machines. Springer Science & Business Media, 2008.
[62] Vapnik, V. and Chervonenkis, A. Y. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264, 1971.
[63] Vershynin, R. High-ddmenssonal probabiiity: An introduction with applications in data science, volume 47. Cambridge university press, 2018
[64] Wang, H., Gao, R., and Calmon, F. Generalization bounds for noisy iterative algorithms using properties of additive noise channels. J. Mach. Learn. Res., 24:26-1, 2023.
[65] Wang, Z. and Zhu, Y. Deformed semicircle law and concentration of nonlinear random matrices for ultra- wide neural networks. The Annals of Applied Probability, 34(2):1896-1947 2024.
[66] Xu, A. and Raginsky, M. Information-theerrtiic analysis generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 30, 2017.
[67] Zhang. C., Bengio, S., Hardt, M. Recht, B.,, and Vinyals, O. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 6473):107-115, 2021.
13

---

Appendices
Limitations and Impact Statement
Our analysis focuses on the generalization bound of the gradient flow algorithm. The behaviors of other algorithms, such as gradient descent (GD), stochastic gradient descent (SGD), and Adam, are still unclear. Extending the analysis to GD and SGD with large learning rates can bring the bound closer to practice.
This paper presents work whose goal is advance the field of Machine Learning. There many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
A Additional Experiments
In experiment (I), we train the two-layer NN with learning rate of 17 = 0.01 for 8000 steps. The training time is calculated by T x7x The integration in r (3) estimated by computing the gradient norm at each training step and summing over the steps. For experiment (II) and Fig. 4 train Resnet and Resnet 34 with a learning rate of 0.001 and batch size of 128 for 50 epochs. For Fig. [] we train two-layer NN of 1000 hidden nodes with learning rate of 0.01 and batch size 128 for 100 epochs. For Fig. 6 we train a two-layer NN of 1000 hidden nodes with a learning rate 0.1 and batch size 200 for 10 epochs. Experiments are implemented with Py Torch (56) on 24G A5000 and V100 GPUs.
Fig. 4 and Fig. have similar behavior with Fig. The models first learn the features, then overfit. Fig. has less overfitting. Our bound correlates well with the true generalization gap in both cases and for all models.
(a) Cross entropy loss
(b) Generalization gap bound
2.5
2.5
Generalization
0.8
Gene aeiietttoonnn cap
train
test loss
0.4
0.5
0.0
0.0
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
0.0
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
Figure 4: Experiment (II). ResNet 34 trained by SGD full CIFAR-10.
(a) Cross entropy Joss loss
(b) Generalization gap & bound
1.75-
Geperdiization cap
2.0
1.25
1.00
test loss
0.75
0.50
0.5
0.25
0.0
0.00
50
100
150
200
250
300
350
400
0
50
100
150
200
250
300
350
400
C
Figure 5: Experiment (II). Two-layer NN trained by SGD on full CIFAR-10.
14

---

(a) Cross Cross_entropy Joss loss
(b) Generalization gap & bound
train
Generalizaionn
2.0
NN test error
1.5
Generalizzaion
-
-1-
-0
0
50
100
150
200
250
300
50
100
150
200
230
300
Figure 6: Experiment (II). Two-layer NN trained by SGD on full MNIST.
B
Uniform Stability of Gradient Flow
Lemma 4.3 Under Assumption 4.2
for any two data sets S and StA,, let w; = A,(S) and be the parameters trained from same initialization we = w/s then
w A
Li((u)) 7-S.C., [.s(w) is convex,
12 w1/l -
2Ld
21.
(e
1), Ls(w) is non-convex.
An
Proof. Convex Case, Notice that
d lw, ww/l?
dt
0 0|w, wil2 d d(w; w()
O(w, - w//
dl
(wi w/)) T d (wv, w//)
dt
(w: w/)) T V wswss(w,) + V Lst (w())
(wo - w/)) T (- V w Lis (w.) + V Lst ( (w;) - V Lssw (wi) + vao Listr) (w,))
2 (w: w!) T (V x/{ Vwl(w, 2:)) 2 (w: w/) (w (w;) L (w())
n
2 (w: w!) T (V (Wwe(wrr z() - V Vwl(w,, 2;))
(convexity)
n
4h
ww w/ll-
<|| w. w|/12 |lum:
d| d||ww, ww/ll dt
Since also
un/ll
we have
de
d [|:, will
4L
2 2|/w, will
lww,
w/
dt
When [w; - w/ll = 0, the result already hold. When ||w. will > 0,
d www
will
2L
dl
Solve the differential equation, we have
100: wi'll S 2Lt
Thus, complete the proof of the convex case.
15

---

7-Strongly Convex Case. Notice that
d 1wo -will
dl
2 (wo - -w/) T d (wv; w)/
dl
2 2w.; - w/)) T (- V vm + V V LLs (w/))
(wr - w/)² T (- V wwws(w)) wi) + V (wi) - V VLLss ( (wi) + (w())
2 (w. w/) T (Vwl(wrr z Vwl(un zi)) 2 (w: w// (V Li (wx) V w Lusos (w,))
n
4L
ww will 2y |111 - will
n
22 ww will
(2) m
y llu, will
(6)
Now we prove l|w, will - time T' such that 1i w > 2L then there must be some 7" < T such that || w/y- 2L
2L by contradition. Recall ||w0 w/'l = O. Suppose that there is some nm
and || - wi/ll is increasing at some point between (T', T.. However, when ||w, -w/ll
21.
"ym
by dl w/'l"" < and lw,, wi'l must decrease. Therefore contradict and we must have
de 2L
(w;- will
Non-Convex Case. First of all, we have that
d 1w ww/l2
dl
2ww: - -w/) T d dww; w/)
dt
(wi - w/)) T (- (-VwLs + V V (w())
(wn: mn)) T (- V (is(,)))))))) + V Ls (wr) - V Lisss (wi) + V.o Lis (w/))
2 (w, w!) T (V (wwl(wr z() - V W 2:)) 2 (w: w/) (V w Ligo (w)) V L (w)))
n
2
||2, w/ll V w.w, 2/) - V Vwllwer z:)1l + 2 1|w; - ww/ll | (w.) V Ls (w))l
n
4L
w: will + 2/3 we - will?
n
d| n0 w/,l
d| w/
wwil
Since also
||w, - wi'l
we have
di
di
l| w
4L
wi'll
|lere wi'l
+ 2,3 Ilnr wx/11
dt
n
When |w;
w/ll 0, the result already hold. When l|w, w/ll > 0. d
||lu w. - -w/l
2L
+ 3 |2 w/1l
dt
From this have
d || w. w/1 ||
< 3dl.
2L
+ llw, will
ng
Solve the differential equation, we have
21 [w. w/ll 5
@t 1).
3n
16

---

C Concentration of Loss Path Kernels under Stability
In the following, will only show the proofs for the convex case. The proofs for strongly convex and non-convex cases are similar.
Lemma C.1. Let S and ((t) be two datasets that only differ in i-th data point. Under Assumption 4.2 for any 2,
AL
when Li((w) is y-strongly convex, when Lg(w) is convex,
2T-
Kr (2,2':8) - Kr (2(2222:800)
Bn (e BT - 1), when Lg(w) is non-conver.
Proof. For convex loss, by (w((Ar(S), vw((A(((()), Kr(2,2':8) KT(2,2':800)
the smoothness and Lemma 3 (l(() Ac(S())] S gLL for all Then
4.3
we
have
(V (V 2). (.. (V v.) z1)
V.) dt
()) x²) - (V )), (,, V di
(v)((A()), Vo)((A)))) 2¹) Vo)((A(()))
(v)((A()) (V ),2), Vo((A((S1)) ,2)) xx)) dt
(A >)|| (=((A(()) (
),>' ),
+ (we((A()) 2) (.. 2) v ),
2Lt
2It Ldt
LB
+
n
2L 3T2
Similarly (r(2)z';8(0) Kr(2,2';8) s 21 Thus Kr(zz2';5) (r(2,2',5 s 2T
With this, we can show that (z, 2':
concentrate to its expectation. Lemma 4.4 Under Assumption 4.2 for any fixed z, z,z', with probability least 1 å over the randomness of S',
1L.ST
In 3
L.((u) is T-S.C.,
7
Kr(z,z';8') Kr(z, S
21 37
In
Ls(w) is convex,
2n
112
(T
3T V Ls(w) is non-convex.
Proof. We prove for the convex Strongly convex and non-convex cases similar. Let S' and (*(i) be two datasets that differ only in the i-th data point. By Lemma C.I ar? Then by McDiarmid's inequality, for any d (0, 1).
(KT(z - x' with probability at least 1 - 5,
In 2
(x(222'''') Kr(Z, 2')))
22223T2
2LL 37
2n
17

---

Similarly, we show that LPK on the training set concentrates its expectation.
Lemma C.2. Under Assumption 4.2
with probability at least 5 over the randomness of S,
(zi 21; -
Kr 21: 21: S)
L1T + 21225T)
2n log o.
(sw is y-strongly convex,
(I2T -22
/
2n log 8
Ls (w) is convex,
1LT + 26 3 (e
- 1))
2n log 3.
Ls (w) is non-convex.
Proof. For any fixed j E [m], let and sG) be two datasets that only differ in j-th data point.
(2 2,, Σ Kr 2/ (01)
Σ (KT 25. Kr 2,, ((o) (T(z), Kr(z), kr( S61)
$ Σ (4, (z s61) (T(z), 2f
ijj
When j Fi, by Lemma
C.I for convex loss
Kr(Zi, 21 S) Kr(Zi, 2, |w0) S 2L BT
BTT
n
When j i, by the definition of LPK, can be bound by the Lipschitz constant,
KT 25, KT 21,0)) s 2T.T.
Therefore
Kr 2) 21 -) Kr 1 (n 2TT2
+ 2L
n
21 3T + 2..T..
Then by McDiarmid's inequality, for any ō E (0, 1), with probability at least 1 ô over the randomness of S,
Σ 01;
Σ
$)
< (T.TT + (12T++2887)
/ 2n log 5
C.1 Bound the Trace Term
With the above results, we are able to bound the difference between Σ Kr (2,,,25;5)) and T
Kr 2;; 2;;S). S).
Lemma 4.5 Under Assumption 4.2 for datasets S and S', with probability at least 8 over the randomness of and St
when Ls(w) is y-stronggy convex, when Ls(w) is convex, when Ls(w) non-convex.
Kr(z,,2;;)) Σ
O(T2
Ô Vn),
18

---

Proof. For any x 0,
Re L, kr(
E e E. (n(2/14,800))
(replace 2, with 2/)
3
E L
2/ 2z, (T/z/; 24;1000 KT (2 z/; S) = 0. If 2 + 2s by Lemma C.1 for convex loss,
(2) 50)) - (2, 2/: 5) <
2L 3T Therefore,
E BE (1( 2 E E
e¹
E. Kr (2()
S
E e
Kr (=.. -242"
(exchange the name of S and S')
$ S
Hence, we have
a E, Kr(z...8))) S 221 g E. Kr(z,e0)))
EE 8
By Markov's inequality,
P
2;;))
(e> (r( 2 edr)
Es Est e E, Kr(
ed
Es Ese e (r(Enz)))) ed
Set the RHS as 8, we have at least 1 - 5 over the randomness of S and S'
Kr(zi, 2;;) S In E >E (r( In 1
[ 3T
Take À = 1, we have
1 8'
Σ (r, 2)) < In 2in (r(=))::)) +2L + In i=
By Lemma C.2 and K2, 2) S IPT in worst case, for any E (0, 1),
In E e Kr(s..2;5)) < In el (Es [> Kr (o
2n log ) nLL"
(IIT + L² V 2n log 2 8 Ky (1))
(1
8') 88)
Σ
+ 8'LLT
Take 8' = n²
In E MinEEink <
Kr Kr Zzi 21:
+ (I'T+ 123T22) log 2n I.T
Combing with the above, with probability at least 1 5,
1 8
K (2;
Σ (T()))2))) (I²T + 12 (2 / 22 log 2n ITT + 2L2 +n
By Lemma C.2 and a union bound, with probability at least 1 - 6,
n
4 (V2nlog 2n + 2n 8)
4
Kr 2;:
(2; (I'2T + L23T9)
L2T
-22288 In 2 g
Kr ž;: S) + S) Σ
19

---

Because of the symmetry between S and 8', we also have with probability at least 1 - 6,
D Proofs for the Generalization Bound
The following decoupling inequality is a slight variation of a result found for instance in Vershynin
63
Lemma D.1 (Decoupling (Theorem 2.4 in (34)), Let F be convex function, D a collection of matrices and o' be an independent copy of a, then
Σ Di i
S E sup 4 4 D iF
E sup DED
DED
Lemma D.2 (Hoeffding's inequality for Rademacher random variables (Theorem 2.2.5 in (3 Let 01..., be independent Rademacher random variables, and a = (a an) E R", then
P
Σ
a:0;
2t
S
2e
2101
Lemma 5.1 Recalling the Rademacher complexity in Desinition 3.
we have
Rs(GT) S
(;; + 4A 4Av6n 2n + 8A,
sup Kr 1=1
Kr
where GT and Kr are defined by and Section respectively.
Proof. Recall
9T {e(Ar()))z)= Σ 1 Kr(z, + f(wo, 2) KT(;,88) e Krr]
"
Kr [K(();8'): n Σ KT 24; S') B² S' Es' C Suup(("")) (T( (2, s sA).
2,z"
Suppose Kr(z, (0(2) = (0): &. (z')). Define
0 = (g(2) (B, ( -(wo, 2) || 3,KT(;;8 E KrT).
(7)
We first show GT C Gy. For V=(z) E GT.
g(z) Σ
Kr 2/15¹) + ((wb,z)
Σ
( (z), 2 (z/)) l(wo, 2)
n
1
( (z),
s (z/) n
f(wo, x)
(Bs & (2)) ((ww,, 2),
where we denote Bs
Σn 1 {
By definition of Gr. ||ss
1 Ei, 2/ < B Thus g(2) Grr Since Vg(2)) E Gr. g(z) Gr. Gr C Gr
20

---

J/ is strictly larger than Gr because 3s is a fixed vector for fixed "'") while 33 in F is a vector of any direction. Then by the property of Rademacher complexity, (TT(GT) Rs((g))
1 n
sup 99
1
I
sup
oi (13, (z)) + f(w00 2:])
n
(Kr(,;S")K
1
Σ oi (B, 2s (zi))
1
Σ o. o,e(wo zi)
sup (r(.:)")
sup
71
n
i=1
n
)
sup (r(
B,
o. (zi)
n
By the dual norm property, we have
B, Σ 0
sup
i=1
B sup Kr(s:S)E
EE
Σ 2 (z+)
T1
i=1
B
sup (r((-18)
Σ
o,o (T
71
B
sup KririS)ERr
ΣΣ
o.oo (Z,, 2z:)))
n
im j=
Then by Jensen's inequality,
oia KT,,,
sup Kr (r(r))))
1=1
B
sup
Σ o, Kr (Z (200))(2112)881))
(Jensen's 's inequality)
Kr(r yeKr i=1 j=1
(T )
E
sup
Σ
Σ igj
T1
Kr (5
E
sup Kr(w
Kr 2z: 24)
sup Kr(s in
Kr( 21: +E n Σ
sup ('
sup Kr(r itj
n
1=1
For the second term above, by the decoupling in Lemma
D.I
we can obtain that
Σ (r(,,(((
o Σ ojJK((z,2z:88))
E
sup
< E a.a"
sup Kr(t:S))K
Kr
t=1
21

---

Since 2); & A, by Lemma D.2. for any fixed i, with probability at least 8',
Σ
S SAV 2n In
By union bound, for all i E [n], we know that
I SAV2 2nln 2n
Conditioned on this, by Lemma D.2
with probability at least
(1-8")(1 -'))) 8¹),
2n
In 2 8' 8"
Σ
o
2z) S 2 In
jfi
For the left 1 - - -11-8)(( - 8') portion, in the worst case we have
o 2)) nnn 1)2.
Combining these two cases, we can bound the expectation
E sup KrKK
itj
<
E
sup (I((110)E
4
Σe
oz zy:8")
o.
i=1
1
2n
< (1 - (1 - 8')4A
2n In
+ (6' + 8" - )'n" - 1)4
8'
< 4Av 6n 2n + 8A
(take 8 8" 71
Therefore, in total we have
B sup Kr(tis))KR
Rs(Gr) S Rs((T) n
Σ
0,(2,,;;57) + 44A66n In 2n + 8A.
Theorem 5.2
Under Assumption 4.2
with probability at least 1 8 over the randomness of S,
2
In In(4n/0)
(AT(S))) - Ls <
(T(2,,2;;8)
Σ Kr(Z,, 21; + 33
c,
n²
2n
j=1
Ö T
S.C..
n²
where
min
Ō
0(
COnvex.
nt
min
Ō 7
0,0()
non-convex.
Proof. Since (2r(z, < L by the Lipschitz assumption, can take A L such that for (*),
all S' ")
sup Kr((2 < A.
x.z¹
22

---

By Lemma 4.5 we know with probability at least 1 ó over the randomness of S and S'
Σ (r( K -
+
for convex loss. Conditioned on this, we can find a set S' C Supp(u for dataset S' such that
sup Kr Kr( 1=1
Kr(z,, S K.
Also, take B² 3/2 Eis Ky (2,, 2z; Therefore, with probability at least 1 - 8, we have
((A 2) E GP, where Gi denotes Gr taking values of B, A, and
Note B² n²2 Ein (r S) = Jo' (. di (.so))) - Is(wr) S 1. Since
1
0 B < let B,
1
1. We have simultaneously for every B, that
ni
B: V
RSs (
Mnv6nnn 4A 8A.
Let B3 be the number such that
Kr 2jj -
2)(=)) B -
i=1 ==1
We have
R.
Bi
Bi
+
4Av 6n 2n + 8A
n
1
22
n
n
Kr(
Kr (r, 2))) O(TVm)
n
n
n
j=1
1
KT(z,, 21: +)
Kr 2): +
n
n
j=1
<
Kr (z., 2);
Σ Kr S) + Ō )
n
Since Kr(Z, < L by the Lipschitz assumption, we also have
Σ (rizz,z;;
- Σ (1; + 1T
Ky S1 EKT 2ml
From this, we can conclude that
R5 <
1
Kr (z 2z:1
Σ Kr, -0) T.
n2
Therefore,
T 0
Ri
Kr (i, 8):
Σ Kr (;; + min
O
n
n
i=1 1=1
23

---

By Theorem 3.2 and applying union bound over B; 1 n n.... 1, with probability at least 1 - over the randomness of S. for all B,
In(2n/6)
sup (L,(0) - Ls(g)) & (9) + +3V g
2n
Finally, taking a union bound, we know that with probability at least 1 - 26, for some B the following three conditions hold:
((AT(S), x) E T..
T (0
0
Rs(
Kr 2;; + min (r 2j:)) Σ
O
2
S
n2
[m(2//6)
- - s { (R ) 3/
sup
gEgz #
2n
These together imply that with probability least 8, we have
2
L,(Ar(5)) - ( -
Kr (21,
Σ
KT
(zi 2;; 2)
IIn(4n/0)
T
T
+ 3/
min
0
2n
n
E A lower bound of (g')
Here we give lower bound of RGT)) Similar lower bounds for linear model were proved in I1 without the supremum. Our lower bound matches the upper bound, which shows the bound is nearly optimal for RgT))) Theorem E.1. Recall the function class 9r defined in
We have
B
Rs( 2
Σ KT(21;2;;8)
sup V2n Kr
Proof. Recall
J = (g(2) = (B, 4 (2)) l(wo. 2) :1|11|111 S B, B,KT(::88) E Kr).
The Rademacher complexity of g/r is
RS(
E
sup
(ig(2z)
gE9 1=1
E sup
sup
Ji ((3, (z:)) + E(wo, (i))
Ky Kr(ssS')eRS
||| S ==1
Σ a.l(wo, zi)
E sup
sup Kr(ss8')EKT |
B
+
i=1
E. (rr(ysS)eKKr
sup
sup
B,
||
1=1
B sup
E
Σ R (z))
Kr(s:)")KKr
i=1
24

---

where in the last line we apply the dual norm property. Then by the subadditivity of the supremum, we have
Rs( = n Kr(sn'")ERr
sup
I
Σ o,
S
(zi)
2
sup n ('rrr
Σ i=1
o
1 S (2:)
(norm sub-additivity)
2 #
1)
sup (rrr
E
2
(z))l
(by the definition of 2-norm)
JEN+
2 $
2
sup n (r(ss
Σ
Σ
S
(z;)13
V2
JEN+
i=1
(Khintchine-Kahal inequality)
B
n
Σ JEN+
Σ
st (zi)13
sup V2n (r(vi))e
B
sup V2n (r(v:
Σ
s (2:)13
(rearrange the summations)
i=1 JEN+
B
Σ 1 (z:)112)
sup V2n kr(v:s))
B sup
(z(2; 21; 8%)
22n (r
Hence, we complete the proof of this theorem.
25

---

Stochastic Gradient Flow
In the previous section, we derived a generalization bound for NNs trained from full-batch gradient flow. Here we extend analysis to stochastic gradient flow and derive corresponding generalization bound. To start with, we recall the dynamics of stochastic gradient flow (SGD with infinitesimal step size).
dw; di
1
Σ SES.
V (ww(Wrr z.)
m
where S. S (I.......] be the indices batch data used time interval [t, L + 1] and |St] m be the batch size. Suppose each S, is uniformly sampled without replacement from {I...., n... We recall the connection between the loss dynamics of stochastic gradient flow and a general kernel machine in 10)
Theorem E.1 (Theorem 4 in (0)). Suppose w(T) wr is solution of stochastic gradient flow at time 7 E N with initialization w w() = Wo. Then for any 2 E 2,
T-1
E(WT, 2) Σ
Σ
(2, E(wo,, =);
m
iES,
where 11,41(2,2:33 = [ett] (Vwl(wr, 2), Vmllure 2:)) dl is the LPK over time interval [L, 1+ 1].
F1 Stability of Stochastic Gradient Flow (SGF)
Lemma F.2. Suppose Ls(w) is convex any S and Assumption 4.2 holds. For any two data sets S and 8(0), let w, Ac(S) and w/ )s((()) be the parameters trained with SGF from same initialization wo = w/y then
2Lt
Ilw, w/ll A.
E
where the expectation taken over the randomness of sampling the data batches St.
Proof. Notice that
d |u, will
dt
ww will" d(w; - w()
0uun; - un/)
dl
2 (w: - w/)) T (w: w')
dl
- w() T (-V + vo sto (w/)) 2 (w,
Since S, and S are uniformly sampled without replacement, the probability that S, and S are different is When S; = S( by convexity,
un -w T (- V Lis, + V Ls, (w))) S
Since also <|| w/ ||w,
w/ll a||,,e--/ we have
db
d klle - will
2 ww; - w/ll
< 0.
dl
Solve the differential equation for [T - 1, T], we have
- IW - w'rll < | w/--1l
26

---

When St and S differ with one data point,
2 (wi w/) T (- (wLLs + V 5(0 (20()
2 (w: - ww/) T (- V- (w)) V S (w²) VoLg(0 (w)) + V
Vu (wlss(((u))
(wi - w/)) (V Vun((w, z1) - V E(wr, zi)) - 2 (wr. - w/) (Vooligg (wes) - V
splosto sto sto (wo()
(wi w/)) T (Vil(wr, z1) Vwl((urz2z)
(convexity)
m
4L
ww w/ll
m
<| w. wwll
d| - will dt
Since also
ll
w/ll
we have
dt
will
4L
2 1/00,
will
|00,
- w//1
dt
When |w;
w/ll = 0, the result already hold. When lw,, will > 0,
d 1|e, will
2L
dt
Solve the differential equation for [T - 1, T), have
2L +
UTT w/ I
|1
w/
Therefore, considering the two cases that whether S₁ = S((0)
E
WT
w/r11 <
m
2L
+ (1
m
0 +
E
WT w/--1l
Ar
2L
w/
72 Ar
2LT
Thus, we complete the proof of this lemma.
The proof's for strongly convex and nonconvex cases analogous those of full-batch gradient flow. Consequently, we omit the proof for strongly convex and proceed directly with the proof for the nonconvex case.
Lemma F.3. Suppose Ls(w) is y-strongly convex for any S and Assumption 4.2 holds. For any two data sets and S(i), let wi A((S) and w. A((S(i)) be the parameters trained with SGF from same initialization we w/y then
2L
E
ww. w'll S 7m
A.
where the expectation is taken over the randomness of sampling the data batches S..
Lemma F.4. Suppose [.s(w) is non-convex for any S and Assumption 4.2 holds. For any two data sets S and S(i) let wi = AS) and w' = A,()())) be the parameters trained with SGF from same initialization wi = w/y then
2L
E l|w. w/ll - (E -1).
3n
where the expectation is taken over the randomness of sampling the data batches S..
27

---

Proof. Notice that
d Wi will
0 ww w/ll d (w. w!)
oww: w//)
dt
2 (wr w/)) T d ((w,- - -w()
dl
(w) - u/)) ooooo + V Vwli (0)00
When S, S by the smoothness,
2 (w. w() (- Ls (wi) + V L. (w/)) wt w/ll || - V w Lss (wx,) V L. (w))
23 ww - wo'll
di wi - wi ||"
d| w wil
Again, because of
W - will
we have
di
dt
ww will
< B w - will
dt
When St and St differ with one data point, by a similar argument as the full-batch gradient flow, we have
d ue will
4L m
2B l|1, w/l
dt
Combining the two cases, we get EA [w,, will dt
l|w, - w/ll
dt
S m
4T.
+ 23 E ww: -wwll
+ (1 (1- m.
33 E l|u, we!
m
4L
+ 23
E Ar
I|we - will
n
Solving the ODE, we get the result.
F22
Concentrations of LPKs under SGF
For SGF, we can prove similar concentrations LPKs as Lemma C.I Lemma 4.4 Lemma
and Lemma 4.5 The proofs are basically the same by simply replacing Kr(z, z': with
EAT K (z, z S). Hence, we only present the lemmas below. Note here we consider Kr,++1
instead of Ky (z, (1))
Lemma F.5. Let S and S(i) be two datasets that only differ in i-th data point. Under Assumption 4.2 for any 2,
ALP8
y-strongly convex,
E Ar
(2,ti - (,etn(z, -
21 8(2++1)
convex,
4L
(e
8t B), non-convex.
On
Lemma F6.. Under Assumption 4.2 for any fixed z,z', with probability at least 1 5 over the randomness of S',
41.38
In ?
y-strongly convex,
7
2n
(r,t1(z,2''87) ku,r12z,22881) 5 AT
21 212 + 1)1
convex,
112
(((+1)
B)
3
non-Convex.
28

---

Lemma F.7. Under Assumption 4.2
with probability at least 1 over the randomness of S.
E
Ke,t41 (1,41(22,,0 2;; 2)
(2,,
Ar
1=1
(
2L28 V 2n 22 G.
Ls (w) is y-strongly convex,
$
(L' + 323 1)) /2n log 3.
Ls (s) is convex,
(e e
B))
2n log 3.
Ls (w) is non-conver.
Lemma F.8. Under Assumption the randomness of S and S
4.2 for two datasets S and S', with probability at least 8 over
Ō(VT). Ó(VT), Ö(e' Vn),
?-strongly convex,
E
K1,41 (2,,
Ku 21: 5
convex, Ron-convex.
F.3 Generalization bound of SGF
Given sequence of So. 1, define the function class of SGF
Gr a (((A)()))
Σ
(2,
((wo, K((,;8") E Kr)
m
t= iES
where
Kr = ((unls)s8))
( :s' E supp(
Σ
(2/ S (3, 4}.
m
t,jES,
Lemma E.,, Given sequence of So. ... ST-11 we have
T-1
Rs(gT) 1
Σ
Be
Σ
+ 4nv6n 88
sup K(rr:S)Ekr
n
1=0
Proof. For l 0,1, ,T T let
G: = {g(2) = Σ (2,41(2,22:55)) K((::5)) e Krt.
iES.
Then have
GT C 0 4 GT @ {E(wn: =)}
Since the set on the RHS involves combinations of kerelss induced from distinct training set S', it is a strictly larger set than the LHS. Apply Lemma 5. bound for each G, on S,
B. sup (S)
Rs)
< n
KK z² + 4Av6n In 8A Σ
(8)
By the monotonicity and linear combination of Rademacher complexity and take in
R.s(Gr) < Rs(go @ Gi .... ... ④ (l(wo. =)))
R.(G.)
2))
B
Σ
Kutt 44 +84
sup
t=0
n
t=1
29

---

Theorem 5.4 Under Assumption 4.2 for fixed sequence Su...., Sr-1. with probability at least 1 over the randomness of the generalization gap of SGF defined by is upper bounded by
T
[x(((())) - Lss S
(26,
Σ Kat+ (Zi, 21;) + Ō
m
V1
i.JSS.
Proof. Let A 1,2 in Lemma
R9
Take B3
m Eijes, kr,++ (2i, 2j; I.s(ws))
Ls(W++)). Then ((Ar(S), z) E ST
B Pa Br where G. denotes Gr taking values of
Bu.... BT-1.
By Lipchitz assumption,
sup M(s:5')EKN i=1
Σ
S
Σ
Ke,+1(z; (2; + L2n.
1=1
Since S B, 1, let Bi
1
1, = o...., 1. We have simultaneously for every
n n
By ......, B that
T-1
B
Rs RS
(1,4122, + L + 4L3 6n 2n + 8L2.
1=0
Let Bi be the number such that
Σ
S Bir S
Σ
(2,,
V m² JJES,
m²
n
L.JES.
We have
Bi B,,.Bi-1)
(9
Σ
(21, +
Ke (2;,1(2;,;;000 2);5)
n
m
1=0
T-1
Σ i.ESS,
(22,
Σ 21;
m²
t=0
By Theorem 3.2 and applying a union bound over B probability at least 1 6, for all B
1 2
1, = ..... T 1. with
n n
(L,()) - Ls(g)} < 2Rs B Bj Bi 11- + 3/
Inn + ln(2/8)
sup
2n
et gEg,
These together imply that with probability at least 1 - 8,
2 Σ
Krt+i (2;, 21; Ö T
(Ar(S)) - Is(Ar(S)) <
(r,
Σ
i.ES.
30

---

G Proofs for Case Study
G.1
Overparameterized neural network under NTK regime
Recall the definition NTK ((w; x, x') V f x) V f x') Rx for neural network function f(w, x). We now prove our bound for the NTK case.
Corollary 6.1, Suppose that Amar )mar( X, x)) & Mmx and Amin (+ X, x)) 2 Amin 0 for t E [0, T). Then
2dmax
[ X)
yl1 (1 E
2A
Aminn
Proof. Notice by the chain rule,
V w Wwl(Wrr 2:)1
Σ v vel(wr, zi) 6(w;; x., V fl(W;, zi).
Therefore,
72 2 Ls(wn) Ls(WT) T= 71
vyl(wr, TT) y 2,)
Since the loss is bounded in 10. 1), (u( - ls((r)) $ 1.
When using a mean squre loss
Ls(w:) = 2n
1 [1f X) yll and ((w,z)= (f(w. - -y)
"
| lww 2:)l Σ iw, 2;) (f(w,, xx,) y;)²
max O(w; x.) [lf x) - y11
m
Amax (ima(O(Ww)))) X)) [|f X): yll
In the case that the smallest eigenvalue of NTK Amin (Ó(w;; X, X)) Amin over the training, the loss converges exponentially [[f X) - y1 <
2 [[ X) yll We can see from
d ( X) - yl? 2(S(w,, X) y of df(w,,
dt
dl
2(f(u, X) - yy Vwl(w; X) dw
dt
-2 ~f(ww, X) - "y Vwf(w, X) V
(f(wi, X) y)) T Vwf (w,, X X) w/ (w,, X) X)T (f(wr, X) y)
(S(w,, X) y) θ(m: X, X) (f(w: X) -)
2Amin [[f(w,, X) - ?
Solving the ODE, we get
I1(w, X) -y11 se 2nain [15(wo, X) - 2
Then we have
n
T I Vwl,, < (" Amax [1f(we; X) 2112a dt
2d Amare
" [lf 211 dt
[| X) y11
(1 23
2)min
31

---

Plugging this into our bound, we get
2Amax
[ X) y/1
2Amin T)
(1
22
G.2
Kernel Ridge Regression Case
Corollary 6.2. Suppose K (x;; vi) S Kmax for E [n]] and K(X,X) is full-rank,
v /max
WW w w01 (xx (wo
w=)l
n
When wo O, the bound simplifies
mm V UT (K(X, x)) y lvlll
r
(9)
Proof. The training loss gradient is
1 - (XX) (6(X) w0 -y) + Aww;
V (www)
1
(X)6(X)
wT n
-x()) Auni
n ()xX))(()) T + +2I) wt (X))y
from where we can calculate
w = - (=x())((X) + +1I)
6(X)y 1 =x(x) - o(X) + Al,
y.
Thus, we have
dw;; V Ls
1 (xx)) +XI)
1
wr =x(X)
n
(w: (wI)
I (x (X) +X1)
n n (X( +MI) o(Xig)
(X)o(X)
(X) T + +1I (wi - w")
Therefore,
w. n +e (100))((X) +AT)= (wo ww))
Calculate the norm of the gradient,
| (s =
o (X) + AI
wi x(X)y
x( T +AI)
(w= +e (e (10(0)0()) +ATT)+ (wo - -w')) xx))
n
(x) +A11
(HO()))( +AI)O (wo -w)
32

---

Suppose the sigen-decomposition of = Ei Amuuy then
Σ
u.u.
(2+ uu
(wo w=))
n
Σ
Xi + A
(*+ "
(200 20*)
p
X + +
e - -2(+++1) ueut;
(wo
w²)²
Σ
(wo- -w")
i==
d +
(2)) (z: (wo - w²))²²
A
A
e
1=1
Integrate the training loss gradient norm,
J. 1
dt
/
Σ
P
A
+1)
2
-2 -2( (w? (wo - w²')²
e
n2
i=1
1
p
Xi
+1 ) (1- - --2((++))) (u? (wo w²))
2
n
A
+1)
(u. (wo w²)) 2
n
2 (wo w")" T
1
Σ
p
Ai
+ +2) unu (wo - ww)
n
i=1
2 (wD w²)
1
(X)x(() + +AI) (2on w²"
72
The individual gradient is Vmllwre 2;) = (á(az)) w. - w:) ((x))) + Aw,, = ()(m))((a):)) + AI) w. - vi)((x))
Assume K( x.) S Kmax. When \ 0.
n
V (wee 2,)11²
[o(x))(<x.) ww - v1o(0;))
[(.=))((.:) (w" (000(w0w0 - " (wo - -w')) - vio(1e))
Σ (usb(ar)) - (aa)) -ex00)0000)) '((xx w²) vibb(a:) /| 1
((xx;) )(x:)) T 2X())(()) (wm - w/
n
< Kmaxx
(wp- T - (m))))(a;)) Te-tax))))-e t0(0)(()))) (wo - w²)
K (wo w²) -- -x(0))(0) ((())(X Te- -1000)00))) ((o))))"((wo- w²)
=Kmax (wo w²) Ase _ u (wo w²)
K
Ase Axs (u.. (wrp w w)))
33

---

Hence, we can obtain that
(
T
V w Vwl(w, 2i)1 di s
Kiax Σ Aue
2,t (u: (wo w))) dt
o
Σ 12
m ) (u, (wo w
Kmax
1 - e
2
==1
K max 12
|1000 - 20'1"
Therefore when 0,
K max Wwo
w" (X)
(wo w=))
12
When wo 0, plunging in the expression of w", the bound simplifies to
VKmax v TT (K(X, x)) y |/yl|
r s
n
G.3 Feature Learning Case
We state the assumptions and results of Bietti et al. [5] below. Assumption G.I (Regularity of f.). We consider f. T7())) with Hermite expansion S.
Ej aghy, where = :0, 1). Assume
1. fo is Lipschitz,
2. Σソ 1a,1 00,
3. (z) : E, VG++)(( + 1)a442h((2) in L*()).
Theorem G.2 (Theorem 6.1 in Bietti al. (15).. For 5 E (0,1/4) and f. satisfying Assump-
tion
G.1 suppose the following are true: (i) X O(1) and X = ((Vori))), where Derit
max
d+N ( (222/(22-11)
1),, (ii) O(max{ (d+N)d'' gia+33/2
x= }). (iii) N 20xxxxxx I) and
N = Ō(AAT)) (iv) No O(log })), (v)
O(VNN, (2+s) (72 + ANN/No) (vi) for T = To + Ti time steps
To = (dd//211), ), and (vii) Ti = 6( ). Then, we run Algorithm
for
with the ubove parameters, with probability at least 1 - 8 we huve
k0,00) = (x-1 max
d N d n1
n2
Algorithm 1 Gradient Flow
Require: No. To. Ti. N, and X.
Initialize (0) ~ Unif( c(0) ~ Unif( (c fCE R. ||c||2 = p, ||ello No)).
Run gradient flow (6.3 up to time T = To +T. Return ((T).c(T)
We recall the basic concentration properties of Gaussian random variables.
Lemma G.3 (Concentrations of Gaussian random variables). Let 8 E (0,1/4), N E N, and by be i..dd random variables drawn from (N Then there exists a universal constant
C" O such that the following two events hold simultaneously with probability at least 1 ô:
max [by| < C'TV/og(N/D),
Σ 69 <N + 7 max log(1/8), VN log (10)
34

---

1 - c0((;; (0.z) b,) = =c= x)), where we denote the feature vector of first layer as @ x)) = V (0, x) + b.)) We have the following bound for the
Recall f(0, c;)
NN
feature vector.
Lemma G.4 (f2-norm of random features, Corollary D.5 in Bietti al. [ Let 8 (0.1/4) and bi...., bx be i.idd random variables drawn from (0, =²). Then there exists a universal constant C² > O such that the following holds for all z E R with probability at least over the random features,
[
|2| + C'T(1+ Vlog(1/0)/N) - |z| + 20g/)//o((1/6).
We restate and prove our bound below.
Corollary 6.3. Under the settings of Theorem 6.1 in Bietti et al. (I5] (provided in Theorem G.2
(V
di+1
+ A2d
nd²
with high probability as n, - co. As long as X oa(1/vo) and (((d5+2), r on, Taking À O )å, have
dē+2 $
Proof. Recall
2 - (f0, Ls(Or, CT
T
r
V zi) 2:) dt.
We first calculate the order of the v (Ls co) - Ls(Or (0(,,rr))) Cr). Recall
Ls( = Σ (f(0, ax)) - y1)² + A||c|
Then one can claim that
Ls(Ou, cu) = Σ
(f co: x;) - y2)² + ||col
i=1
n
Σ
(f(Og. Coi x2 v/ 2y: Co: 21)) + X l|coll?
n
By Lemma G.3 p(a, (0. x.) + b.) ((((1) + 0(1) Ö(1). Since Ee, co:
Eco N Σi Gdo (0, mx) + b,)2 Ō(l1eg) ||ol!" 0 Ö(1), by Chebyshev's inequality
f(0,, Co: ) = 0(1). Since also y; = Ô(1) and A ||c/ 12 = Ô(1), one can verify (6 co) = Since Ls er) is non-inereasing in gradient Ó(1). Therefore Ls (0, co) cT) = Ó(1..
flow, )| Ō(1) during training.
Then calculate the Σ So Vwl((,, 11 dt. By Lemma G.4 the sample gradient for 0 and an upper bound for its E2 norm is given by
Vol(O, a, M.)
c_ N' (0, c TT ((((0x)))))
(0 vill ||||| (Lip(f), ||0|||| + |l@ + ||c|| (|<= C'T (To((1)))))) |
Ō([e]) I|=:
Similarly, the sample gradient for is
V l(, a. v)) = 20((0, an (c 4( (,)) - /-(10. mx) - Ex) |V a, wi)l = 2([|0ı|| + (ot///oo(///)((((
(| + C'T ('ov/og(1/0)
+ Lip(f), || + [l = Ó(I]e] 1|x;
35

---

As we have shown, ||e|| =x2)) and by Lemma G.3 max,
| O(ydlog(n/))) Therefore,
+ Vel(0, =1 Ō d2 12
V zi) 1| =
Then take T To + Ti, have
Σ 0 Vel ( Sn nn.onn 2.. 0((²)
(To + Ti)
12
1=1
S n 0
d2
(Q(d
+ A6 d'n
x2
d=N N
d2+1
n
x²dn)
12
Combining the results, we have
2 T
dô+1
Õ(1) n..n δ
+ 22
n
X2
(dbttt dd+1
=
+ x²d
nx²
As long À - oa(1/d) and = {2d I ol,) Optimizing the choice of À = (2)) have
Ō ( (d++2 $
Hence, we complete the proof.
36

---

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: Our abstract and introduction clearly state the theoretical contributions and empirical findings.
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.
It is fine to include aspirational goals motivation long it is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed the limitations and future works in the conclusion section.
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 separate "L "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-ter sreech-to-text system might 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.
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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide the full set of assumptions each theorem and complete proofs in the appendix.
37

---

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 proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors encouraged to provide short proof sketch to 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 be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification:
We provide the details of the experiment setup.
Guidelines:
The answer NA means that the paper does not include experiments.
the paper includes experiments, No answer 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 not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible 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, if the contribution is specific model and empirical evaluation, it may be necessary to either make it 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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (c.g., in the case of a large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how reproduce that algorithm.
(b) the contribution primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe 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.. to registered users). but it should be possible for other researchers 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 instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification:
We provide sufficient details to reproduce the experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
38

---

Please see the NeurIPS code and data submission guidelines Sttpas/CodSuuumsiiiic
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a 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 thttps://nigg httpp/////ip..ccpplliiic guides:/ooeeuubmi ssi www.bbbisssoooooooooooooo onsioniyl) 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 experimental results for the new proposed method and basclines. 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 in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
Experimental setting/details
Question: Does the paper specify all the training and test details (e.g.. data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide the training details the experiment section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
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: There no randomness in full-batch gradient descent. For SGD, we want to show the bound for one run.
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, confidence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1 1-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors 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 of range (e.g. negative error 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 in the text.
39

---

8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed reproduce the experi- ments?
Answer: [Yes]
Justification:
We provide the information on the computer resources in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as 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 't make into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http://pppppppooiaoo.//ocooooooa
Answer: [Yes]
Justification:
The research conducted in the paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consideration due to laws or regulations in 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]
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or 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.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to par- ticular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, improvement in the quality of generative models could be used generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
legitimate to point out that
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
40

---

If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse 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 restrictions access the model 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 a best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We properly credited the datasets and library used in the paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwppswippteeeeecapppppaapp..pae thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.
this information not available online, the authors are encouraged to reach out to the asset'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 assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions 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 used.
41

---

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, applicable, as well as 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 crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code Ethics, workers involved data collection, curation, or other labor should be paid 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 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 nor 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 adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applica- ble), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non- non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve L.LMs as any important, original, or non-standard components.
Please refer to our LLM policy (https://nentl htt.://ps.....oooeeeeeee/////eas for what should or should not be described.
42


Reviews:
[{"review_id": "SSlo6lxfGE", "reviewer": "Reviewer_R6uw", "summary": "This paper proposes a novel theoretical framework to derive algorithm-dependent generalization bounds for gradient flow (GF), grounded in Rademacher complexity and a data-dependent kernel—the loss path kernel (LPK). The authors leverage the dynamics of gradient flow to build a function class characterized by the LPK and provide uniform convergence bounds with high probability. Key contributions include tighter generalization bounds than prior works, extensions to stochastic gradient flow (SGF), and experimental evidence that the derived bounds correlate with the true generalization gap. The results also recover known bounds in NTK and kernel ridge regression regimes, while demonstrating the advantages of feature learning in neural networks.", "questions": "1. How robust is the LPK-based generalization bound to architectural variations? The experiments mainly focus on ResNets and two-layer NNs. It would be valuable to understand if the same correlation between the bound and generalization gap holds for transformers or larger language models.\n\n2. Can the authors extend the results to discrete-time gradient descent or SGD with fixed learning rate? The current analysis assumes gradient flow with infinitesimal steps. A more practical extension would improve relevance.\n\n3. What is the computational complexity of evaluating the LPK term? \n\n4. How sensitive is the bound to initialization? Since LPK integrates gradient information across the trajectory, the choice of initialization could significantly impact the generalization bound. Clarifying this would help with practical deployment.", "limitations": "Yes", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1. Theoretical Novelty and Depth: The paper offers a nontrivial integration of algorithmic stability and uniform convergence through a novel kernel—the LPK—capturing the full training trajectory. This provides a compelling alternative to static kernels like NTK.\n\n2. Unification and Generalization: The results unify classical kernel generalization bounds with modern deep learning training via gradient flow, while being applicable across convex, strongly convex, and non-convex regimes.\n\n3. Empirical Validation: Numerical results on CIFAR-10 with ResNet and two-layer NNs convincingly support the theoretical claims. The derived bounds track the generalization gap and explain overfitting dynamics and label noise effects.\n\nWeaknesses:\n\n1. Limited Practical Scope: Although insightful, the theoretical analysis is limited to full-batch gradient flow with infinitesimal step size, which does not align with practical stochastic optimization scenarios in deep learning.\n\n2. LPK Computation Complexity: Although discussed as “data-dependent,” computing LPK in practice may be computationally demanding, especially when integrating over long training trajectories.\n\n3. When training time T is large, the asymptotic generalization bound aligns with standard bounds via Radamacher complexity analysis and poorer than that via covering number analysis.", "was_revised": true, "final_justification": "After considering the rebuttal and discussion, I maintain my positive score.\n\nResolved issues:\n\n1. The authors clarified that their framework extends to stochastic gradient flow and provided empirical evidence with practical learning rates, supporting relevance beyond pure gradient flow.\n\n2. They explained that computing the loss path kernel (LPK) is tractable and can be approximated efficiently using mini-batch estimates.\n\n3. They addressed initialization sensitivity and showed stability of the bound across architectures of varying depth (e.g., ResNet-18 vs. ResNet-34).\n\nUnresolved issues:\n\n1. No full discrete-time theoretical extension to SGD with finite step sizes is yet provided; this remains an avenue for future work.\n\n2. Empirical validation is still limited to ResNets and two-layer networks; broader architectural coverage (e.g., transformers, large language models) is not demonstrated.\n\n3. For large training times 𝑇, the bound converges to weaker known forms, limiting novelty in that regime.\n\nWeighting:\n\n1. I assign high weight to the theoretical novelty, integration of algorithm-dependent generalization bounds with training dynamics, and the strong empirical correlation between the bound and generalization gap in tested settings.\n\n2. The remaining practical and empirical limitations temper the overall impact but do not diminish the significance of the core contribution.", "rebuttal": "We thank the reviewer for the positive feedback, thoughtful review, and for appreciating the merits of the work!\n\n---\n**Q1. The theoretical analysis is limited to full-batch gradient flow with infinitesimal step size, which does not align with practical stochastic optimization scenarios in deep learning.**\n\nA1. Although our analysis is based on gradient flow, our bound correlates well with the true generalization gap even for constant learning rates, as shown in our experiments. Also, we have the theory of stochastic gradient flow in section 5.2, which extends full-batch gradient flow to mini-batch stochastic gradient flow. In our simulation, the two-layer neural networks (NNs) and ResNets are trained with learning rates of 0.01 and 0.001, which are common learning rate setups in practice. These experimental results also show that our theory can be potentially extended to discrete SGD with a constant learning rate. We will leave this to future research work. We want to emphasize that using gradient flow to do theoretical analysis is easier and does not lose the general properties of the training dynamics for NNs. The gradient flow dynamics provides a clean, continuous-time model that captures the core features of neural-network training without sacrificing generality. Many qualitative phenomena observed under SGD (e.g., phases of feature learning, generalization plateaux, late overfitting) have been shown to persist in the gradient-flow regime. Moreover, even the training dynamic of gradient flow for two-layer NNs is still underexplored and an ongoing research direction currently, e.g., [43] (\"Dynamical decoupling of generalization and overfitting in large two-layer networks\") in our reference. Additionally, we want to mention that [1] shows that deep neural networks with homogeneous activations, gradient flow trajectories can be approximated by gradient descent, so we can potentially transfer our analysis of gradient flow for neural networks into a gradient descent training based on this result. We will have a further discussion of this limitation in the revision of our paper.\n\n[1] Continuous vs. Discrete Optimization of Deep Neural Networks. NeurIPS 2021.\n\n\n**Q2. Computing LPK in practice may be computationally demanding.**\n\nA2. The computation of our bound is tractable. In the $\\Gamma$ term (Eq. (3)), $L_S(w_0) - L_S(w_T)$ can be easily computed from the training loss. For $\\sum_{i=1}^n \\int_0^T ||\\nabla_w \\ell(w_t, z) ||^2 dt$, we can compute the per-sample gradients (which can be computed in parallel for all the samples) at each training step, calculate their 2-norm, and sum over the training steps. The computation cost of the bound is similar to that of gradient descent training of the model. For large datasets, we can estimate $\\sum_{i=1}^n \\int_0^T ||\\nabla_w \\ell(w_t, z) ||^2 dt$ with a subset of training samples, such as the batch data used at each training step in SGD. We will add a detailed discussion of the computational complexity of evaluating the LPK term $\\Gamma$.\n\n\n\n**Q3. When training time T is large, the asymptotic generalization bound aligns with standard bounds via Radamacher complexity analysis and poorer than that via covering number analysis.**\n\nA3. Standard bounds via Radamacher complexity and covering number analysis are usually based on the norm of the weight matrices [2, 3, 4, 5]. These bounds are independent of the algorithm and cannot capture the inductive bias of the learning algorithm. In contrast, our bound is data-dependent and algorithm-dependent. Empirically, our bound is also orders of magnitude tighter than [4], as shown in Fig. 2.\n\nWe would appreciate it if the reviewer could clarify which Rademacher complexity bound and covering number bound they are referring to.\n\n[2] Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR 2002.  \n[3] Neyshabur, B., Tomioka, R., and Srebro, N. Norm-based capacity control in neural networks. COLT 2015.  \n[4] Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. Spectrally-normalized margin bounds for neural networks. NeurIPS 2017.  \n[5] Neyshabur, B., Li, Z., Bhojanapalli, S., LeCun, Y., and Srebro, N. The role of over-parametrization in generalization of neural networks. ICLR 2019.  \n\n**Q4. How robust is the LPK-based generalization bound to architectural variations?**\n\nA4. Thanks for the question! We will test our bounds for transformers or larger language models later. Vision transformers (ViT) satisfy our theory. For language models, we can treat each sentence as a data point $x_i$ and its corresponding response as a label $y_i$. Our analysis does not require the output dimension of the model to be one dimension. The same bound will hold for the language model and ViT. As a remark, our LPK-based generalization bound exhibits intricate and multifaceted dependencies on the dataset, training dynamics, and the architecture. In Figures 1 and 4 (Appendix A), we compare the predicted bound against the actual generalization gap for ResNet-18 versus ResNet-34 on CIFAR-10.  Despite the difference in depth and width, the bound tracks the observed gap closely for both architectures, demonstrating its quantitative stability under architectural scaling.\n\n\n\n\n\n**Q5. Extend the results to discrete-time gradient descent or SGD with fixed learning rate**\n\nA5. Our results could be extended to discrete-time GD and SGD using an idea similar to [6], by considering the taylor expansion of GD at each time step: $\\ell(w_{t+1}, z) - \\ell(w_{t}, z) = \\nabla_w \\ell(w_{t}, z)^\\top (w_{t+1} - w_{t}) + O(||w_{t+1} - w_{t}||)$, where $\\nabla_w \\ell(w_{t}, z)^\\top (w_{t+1} - w_{t})$ can be analyzed like a linear function class and $O(||w_{t+1} - w_{t}||)$ can be controlled with learning rate. We defer this to future work, as it requires additional effort and lies beyond the scope of the present study.\n\n[6] Learning Trajectories are Generalization Indicators. NeurIPS 2023.\n\n\n**Q6. Computational complexity of evaluating the LPK term**\n\nA6. As we replied in Q2, the computational complexity of computing our bound is similar to the auto-gradient in GD training of the model. In our simulation, it won’t cost too much since we can compute the gradient at each step of the GD training and compute the LPK term along the training process. We will have a detailed discussion of the computational complexity in our revised paper.\n\n\n**Q7. How sensitive is the bound to initialization?**\n\nA7. Thanks for the insightful question! The choice of initialization could indeed influence the training trajectory and the generalization bound. Our analysis assumes a fixed random initialization. The final bound does not depend directly on the initialization, but rather indirectly through the training trajectory. It would be very interesting to consider the influence of the initialization on the bound, which may require more involved analysis of optimization. Intuitively, the initialization close to the stationary points may induce a smaller bound and better generalization ability. \n\nIn our case study of feature learning in Sec 6.3, we show that a mean-field type initialization enables feature learning and can obtain better sample complexity compared with NTK initialization from our generalization bound. This may indicate how initialization affects the generalization error. Our generalization bound captures this effect.\n\n---\n\nWe are happy to address any further questions and feedback."}, {"review_id": "mqUJlFObFe", "reviewer": "Reviewer_cwrL", "summary": "The paper presents a novel generalization bound for parametric models trained with gradient flow. It builds on a recent result showing that the loss at the end of training of any parametric model is a kernel machine for a certain data-dependent kernel called Loss Path Kernel (LPK). Therefore the class of models realizable by gradient flow could be enumerated by corresponding LPKs for all possible training datasets.\n\nIf there was a single kernel, one could use a classical bound for Rademacher complexity which scales as a square root of a kernel Gram matrix trace over the dataset size $n$. One could generalize this bound for a class of kernel machines realizable by a set of kernels, but such a bound does not generally decrease with $n$.\n\nThe main novelty of the present paper is a concentration result on LPKs: that is, as $n$ grows to infinity, all LPKs concentrate around their average over training datasets. This leads to a generalization gap bound whose main term is the classical Rademacher complexity bound mentioned above evaluated on the LPK on the training dataset.\n\nThe main term of the bound closely tracks the actual generalization gap times a constant. This constant is relatively small $(\\approx 3)$ for a binary CIFAR classification using a two-layer MLP, but much larger $(\\approx 1e5)$ when ResNet18 is considered.", "questions": "1. I haven't looked at the proof, but do you have any intuitive explanation why the epsilon term in your Theorem 5.2 is a minimum between two terms, not a maximum? Because naively when you construct an upper-bound, you have to take the largest between competing terms, not the smallest.\n2. Have you tried to compute your bound up to a number? How close is it to gamma on your experiments? Does it also track the actual generalization gap well?", "limitations": "I think the point I discuss above in Weaknesses has to be mentioned as a limitation.\nI will increase my score if the authors either (a) prove me wrong concerning this point, or (b) correct/remove the Numerical Experiments section and include the aforementioned point as a limitation.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. I believe, the concentration of LPKs is a natural, novel and generally useful result, closely related to algorithmic stability.\n2. The paper features a very nicely written background section which makes it easy to read and comprehend.\n3. The main term of the bound tracks the time evolution of the generalization gap really well, even in realistic scenarios like ResNet18 trained on CIFAR10, up to a multiplicative constant. Maybe, it could be useful for predicting the optimal early stopping time?\n\n**Weaknesses**\n\n1. The regularity assumption on the loss as a function of model weights (Assumption 4.2) looks too strong for me. While it is quite natural for some models, like Random Feature Model, it is too restrictive for neural networks with at least two trainable layers. Indeed, consider a two-layer MLP with a sigmoid activation function, no bias terms, and a bounded (say, also sigmoid) loss. Suppose the input layer weights are zeros, while the output layer weights are very large. Then even a very small change of input weights results in a finite change of the loss. This shows that the Lipschitz property is not satisfied even for this toy model. Having a non-bounded activation function, non-bounded loss, and more layers cannot make the situation better.\n2. If the above is correct, the bound cannot be applied to any of the scenarios considered in Section 7, Numerical Experiments.\n\n**Minor comments**\n\n1. The work [1] constructs a generalization bound for neural nets close to being linear; this is also a special case of algorithmic stability which heavily restricts the hypothesis class (i.e. only weights close to a linear network could be found), hence could be mentioned in the Related Work section.\n\n[1] https://openreview.net/pdf?id=tRpWaK3pWh", "was_revised": true, "final_justification": "The authors responded quite satisfactory to some of my concerns; for this reason, I raising my score from 3 to 4.", "rebuttal": "We appreciate the positive feedback, thoughtful review, and the reviewer’s appreciation for the work! We will add a limitation section, provide further discussion in the numerical experiments section, and address the points the reviewer mentioned in our revised paper. We also thank the reviewer for mentioning the paper, “A Generalization Bound for Nearly-Linear Networks”. We will have a discussion of this paper in our literature review.\n\n---\n**Q1. The Lipschitzness and smoothness assumptions.**\n\nA1. Thanks for the question and comments. The Lipschitzness and smoothness assumptions are standard assumptions in optimization and generalization error bound analysis of neural networks [1, 2, 4]. There is also considerable empirical evidence that neural networks are Lipschitz, and many efforts have been made to estimate the Lipschitz constant (see e.g. [3, 4]).  In practice, training with weight decay or early stopping confines the weights to a compact subset of parameter space, on which the loss is indeed (locally) Lipschitz. \n\nFor a two-layer network with smooth activation functions, as long as the norms of the weight matrices are bounded, there should be a finite Lipschitz constant. For the toy model the reviewer is concerned with, the Lipschitz constant could be large. But the Lipschitz constant will still be finite as long as the weight matrices are bounded and the activation function is Lipschitz. This is why in many previous generalization bound papers, the final bound is determined by the Frobenius norm of the weight matrices, e.g., [4, 5, 6, 7, 8]. However, this Lipschitz constant can be significantly large depending on the model’s size, although the trend is consistent with the true generalization gap. This is because, as the reviewer mentioned, the bound in the ResNet18 simulation is much larger.\n\nWe will add additional discussion about the limitations of Lipschitzness and smoothness assumptions in the conclusion section. In the simulations, we will also add an experiment to estimate the Lipschitz constant and weight matrix norm during training. This will enable us to ascertain that these terms do not exhibit explosive growth and are bounded by a constant. In the event that this is the case, it will provide empirical evidence of our simulation’s consistency with our theoretical framework. Furthermore, our simulations show that our $\\Gamma$ in the theorems has already served as a good bound of the generalization gap across diverse architectures and datasets.  Even when a network may not strictly satisfy the global Lipschitz or smoothness conditions, we find that our bound still tracks its behavior remarkably well. These results suggest that, with modest technical extensions, our theory could be broadened to cover a wider class of models. This is one of the reasons why various simulations on real-world data and various neural networks have been presented in this paper. We will conclude by outlining the challenges and potential strategies for relaxing these regularity assumptions in future work in the revision of our paper.\n\n\n[1] Hardt, M., Recht, B., and Singer, Y. Train faster, generalize better: Stability of stochastic gradient descent. ICML 2016.  \n[2] Optimization Methods for Large-Scale Machine Learning.   \n[3] Efficient and Accurate Estimation of Lipschitz Constants for Deep Neural Networks. NeurIPS 2019.  \n[4]  Generalization bounds of stochastic gradient descent for wide and deep neural networks. NeurIPS 2019.  \n[5] Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR 2002.   \n[6] Neyshabur, B., Tomioka, R., and Srebro, N. Norm-based capacity control in neural networks. COLT 2015.   \n[7] Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. Spectrally-normalized margin bounds for neural networks. NeurIPS 2017.   \n[8] Neyshabur, B., Li, Z., Bhojanapalli, S., LeCun, Y., and Srebro, N. The role of over-parametrization in generalization of neural networks. ICLR 2019.  \n\n**Q2. An intuitive explanation why the epsilon term in your Theorem 5.2 is a minimum between two terms, not a maximum.**\n\nA2. The epsilon term is the minimum between the two terms because the two bounds both hold at the same time, and we can take the minimum one. The mechanism is different from what the reviewer mentioned. Here we have two different methods for the epsilon term. So we take the minimum to get a sharper bound.\n\n\n**Q3. Have you tried to compute your bound up to a number? How close is it to gamma on your experiments? Does it also track the actual generalization gap well?**\n\nA3. Thanks for your suggestion! We have not tried to do that since estimating the Lipschitz/smoothness constant, and the constant in the big-O terms is hard. In the revision, we will numerically estimate our bound, including the $\\epsilon$ term for a two-layer neural network during training to see how it tracks or affects the generalization gap.\n\nHowever, as we have compared in Table 1, we want to emphasize that in many cases, $\\Gamma$ is the dominant term compared with $\\epsilon$. In these cases, $\\epsilon$ will be small compared with $\\Gamma$ as $n\\to\\infty$. Hence, we can use the $\\Gamma$ to represent our generalization bound. For large-scale simulations, our $\\Gamma$ can be applied to bound the generalization gap, and it empirically tracks the actual generalization gap well. Also, for future work, we hope to develop a new method to estimate our LPK term so that it could be useful for predicting the optimal early stopping time.\n\n\n**Q4. Missing related work.**\n\nA3. Thanks for the related work! We will add and discuss the paper in the revised version.\n\n---\n\nWe are happy to address any further questions and feedback."}, {"review_id": "GYxHYY7Icd", "reviewer": "Reviewer_xevc", "summary": "This paper establishes new generalization error bounds for the gradient flow algorithm. The method is an extension of the previous work of Chen et al. on loss path kernel. The authors integrate uniform stability and uniform convergence analysis with loss path kernel, leading to tighter generalization bounds. The results demonstrate that the generalization gap is highly dependent on the norm of the training loss gradients along the optimization trajectory. Further extension to stochastic gradient flow and several applications on the NTK regime and kernel ridge regression are discussed, and the results are empirically evaluated to show high correlation with the true generalization gap.", "questions": "* Can the authors elaborate more on the impact of the big O terms on the tightness and computational tractability of these bounds? How are these bounds empirically compared to the previous one by Chen et al?\n* Can these bounds provide some new insights for the design of learning algorithms? From eq. (3), what I can tell is that minimizing the norm of gradients may help, encouraging techniques like gradient clipping. The other part in eq. (3) looks like a fixed constant, as we always get something like $L_S(w_0) \\approx 0.5$ and $L_S(w_T) \\approx 0$ in case of binary classification. Are there any other insights we can tell from these results?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n* The paper addresses an important problem in learning theory. The authors improve the results of a previous work by Chen et al, tightening the bound and easing the computation in practice. Empirical results have shown the superiority of these results compared to some other bounds in the literature.\n\nWeakness:\n* To my understanding, using the method of uniform stability or uniform convergence requires additional assumptions like Lipschitzness and smoothness, while the previous one of Chen et al does not need such assumptions. While they are prevalent ones also seen in many generalization analysis papers, they are actually quite strong and make the bound computationally intractable, since the Lipschitz or smoothness parameters are hard to estimate in practice.\n* It is not directly clear how to compare the tightness between the bounds of this paper and the previous one by Chen et al. While the $\\Gamma$ part of the bound is improved as clearly seen, these new bounds also introduce some extra terms of stability constants. There perhaps also miss some comparison between these bounds and those ones derived solely based on stability or uniform convergence approaches. The authors claimed a tighter bound, but this is not directly clear to me.\n* For the same reason, the empirical comparison may not be sufficient since only the $\\Gamma$ part of the bound is computed and plotted. It is not clear if the bound is still tight when added with other stability or uniform convergence terms.", "was_revised": true, "final_justification": "My main concerns are fully addressed after the rebuttal. I believe this paper offers a solid improvement over the previous work of Chen et al. I'm maintaining my current rating.", "rebuttal": "We express our gratitude for the positive feedback, thoughtful review, and the reviewer’s appreciation for our work. In response to the reviewer’s suggestions and inquiries, we will incorporate a comparative analysis with the results of Chen et al. and provide a concise summary of the improvements made to our paper.\n\n---\n**Q1. The Liptichitzness and smoothness assumptions are quite strong and make the bound computationally intractable, since the Lipschitz or smoothness parameters are hard to estimate in practice.**\n\nA1. Thanks for the question. However, we would like to note that the $\\Gamma$ term in our bound does not depend on the Lipschitz or smoothness constant. As we have compared in Table 1, we conclude that in many cases, $\\Gamma$ is the dominant term compared with $\\epsilon$. In these cases, $\\epsilon$ will be small compared with $\\Gamma$ as $n\\to\\infty$. Hence, we can use the $\\Gamma$ to represent our generalization bound. For large-scale simulations, our $\\Gamma$ can be applied to bound the generalization gap, and it empirically tracks the actual generalization gap well. \n\nTo improve the results of Chen et al. and obtain a better LPK-type generalization bound, we need to include the Lipschitz and smoothness assumptions. Chen et al. do not require these assumptions because they did not perform any optimization analysis. Their bound calculates the supremum over an infinite set, which cannot be accurately estimated. Additionally, their bounds must be evaluated on (infinitely many) datasets different from the training set, which is impossible in practice. By explicitly enforcing Lipschitz and smoothness conditions, one transforms an intractable supremum‐based LPK guarantee into a finite-sample, data-dependent, and computationally verifiable bound. This modification not only tightens the theoretical rates but also aligns the analysis with the practical realities of deep‐network training. We will add a detailed comparison with Chen et al. in the revision of our paper.\n\n**Q2. Compare the tightness between the bounds of this paper and the previous one by Chen et al. Miss some comparison between these bounds and those ones derived solely based on stability or uniform convergence approaches.**\n\nA2. Our bound is clearly tighter than the previous one by Chen et al. Our bound has a rate of $O(\\sqrt{T/n})$ in the worst case, while the bound in Chen et al can be as large as $O(\\sqrt{T})$ since the $\\sum_i \\delta(z_i, z_j)$ term in their bound can be $O(L^2 T n^2)$.\n\nStability-based bounds are exponential with $T$ for non-convex loss with constant learning rate, as we showed in Lemma 4.3, while our bound is at most $O(\\sqrt{T/n})$ in the worst case. Uniform convergence bounds such as [1, 2, 3, 4] listed below are usually based on the norm of the weight matrices. These bounds are independent of the algorithm and cannot capture the inductive bias of the learning algorithm. In contrast, our bound is data-dependent and algorithm-dependent. Empirically, our bound is also orders of magnitude tighter than [3], as shown in Fig. 2.\n\n[1] Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. JMLR 2002. \n\n[2] Neyshabur, B., Tomioka, R., and Srebro, N. Norm-based capacity control in neural networks. COLT 2015. \n\n[3] Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. Spectrally-normalized margin bounds for neural networks. NeurIPS 2017. \n\n[4] Neyshabur, B., Li, Z., Bhojanapalli, S., LeCun, Y., and Srebro, N. The role of over-parametrization in generalization of neural networks. ICLR 2019.\n\n**Q3. Impact of the big O terms on the tightness and computational tractability of these bounds? How are these bounds empirically compared to the previous one by Chen et al?**\n\nA3. As we compared in Table 1, in many cases, $\\Gamma$ is the dominant term compared with $\\epsilon$. In these cases, the big-O terms are small as $n$ increases. Hence, we can use $\\Gamma$ to track the trend of the generalization error bound through different training dynamics.\n\nOur bound is tighter than the previous one by Chen et al. As we mentioned above in A2, our bound has a rate of $O(\\sqrt{T/n})$ in _the worst case_, while the bound in Chen et al can be as large as $O(\\sqrt{T})$. Numerically, we will add an empirical estimate of the big-O terms for the MNIST dataset and small neural networks, and compare our bound with Chen et al in the revised version. \n\n**Q4. Can these bounds provide some new insights for the design of learning algorithms?**\n\nA4. Thank you for the insightful question. The primary motivation of this paper is to investigate the generalization capabilities of neural networks. It would be more insightful if our theory could provide practical insights for training neural networks. We concur with the reviewer’s observation that our theory indicates gradient clipping. Moreover, by monitoring the evolution of our bound during training, we can potentially predict and analyze the overfitting for overparameterized NNs and identify optimal stopping time for training without access to test data. We could potentially utilize a smaller model and a smaller dataset to train and approximate our generalization bound. Subsequently, we can employ this bound to predict the generalization capability of larger models. Our bound can also be used as a regularization in the training. Moreover, our bound can also serve as a proxy to compare model architectures in Neural Architecture Search (NAS), e.g., [5, 6, 7, 8].\n\n[5] Mellor, J., Turner, J., Storkey, A., and Crowley, E. J. Neural architecture search without training. ICML 2021.\n\n[6] Chen, W., Gong, X., and Wang, Z. Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective. ICLR 2021.\n\n[7] Mok, J., Na, B., Kim, J.-H., Han, D., and Yoon, S. Demystifying the neural tangent kernel from a practical perspective: Can it be trusted for neural architecture search without training? CVPR 2022.\n\n[8] Chen, Y., Huang, W., Wang, H., Loh, C., Srivastava, A., Nguyen, L. M., and Weng, T.-W. Analyzing generalization of neural networks through loss path kernels. NeurIPS 2023.\n\n---\n\nWe are happy to address any further questions and feedback."}, {"review_id": "VV6FKLPiOx", "reviewer": "Reviewer_m74d", "summary": "This paper moves beyond the static NTK framework by using the Loss Path Kernel to capture training dynamics. It derives a novel generalization bound using Rademacher complexity, whose leading term is determined by the term $\\int_0^T \\| \\nabla_w l(w_t,z) \\|^2 dt$. This approach yields a tighter, data-dependent bound about $O(\\frac{1}{n})$ that directly links optimization dynamics to generalization, surpassing existing results.", "questions": "1、Do we have a way to bound the term $\\int_0^T \\| \\nabla_w l(w_t,z) \\|^2 dt$\n\n2、Do Gradient Descent and Gradient Flow have a difference in the order of the resulting bound?", "limitations": "The proposed bound $\\Gamma$ cannot be determined theoretically a priori. While the authors claim it can be used for monitoring and prediction in practice, they do not adequately discuss its high computational cost. This makes their claim impractical for large-scale applications.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths: This paper has enough technical contribution and beautiful results. It derives a tighter bound on the generalization error, and the theory is in line with many known phenomena, like why memorizing random labels hurts generalization. The authors also verified the bound on CIFAR-10 with ResNet, and the experiments are consistent with the theoretical results, which is a strong point.\n\nWeaknesses: My main concern is about the exact order of the upper bound. The main term, which is based on the integral of gradients $\\int_0^T \\| \\nabla_w l(w_t,z) \\|^2 dt$, can only be calculated after training is finished. This means the bound is a post-hoc analysis tool, and cannot be used to predict generalization or guide the training process beforehand. Also, computing this term is very expensive as it requires the full gradient history, making it hard to use in practice.", "was_revised": true, "final_justification": "I have no more questions and I will keep my original positive score.", "rebuttal": "We thank the reviewer for the positive feedback, thoughtful comments, and for appreciating the novelty and value of the work! In response to the reviewer’s inquiries, we present the following detailed explanation.\n\n---\n**Q1. The exact order of the upper bound.**  \nA1. A naive bound of $\\Gamma$ is $L\\sqrt{T/n}$ using the Lipschitz property based on our assumption. Combining with the $\\epsilon$ term, our bound is at most $O(\\sqrt{T/n})$ _in the worst case_. However, when the model converges fast, $\\Gamma$ may not increase with $\\sqrt{T}$, and the $\\epsilon$ can also achieve a faster rate of $O(n^{-3/4})$ when $T$ is small. Our Table 1 shows when $\\Gamma$ will dominate our generalization bound. For some special cases, e.g., NTK regime, we refer to Section 6 for more details.\n\n\n**Q2. The bound is a post-hoc analysis tool, and cannot be used to predict generalization or guide the training process beforehand.**\n\nA2. In the case studies in Section 6, we can predict the generalization before the training. See Corollary 6.1, 6.2, 6.3. In these case studies, we have made additional assumptions regarding the dataset, optimizer, and training dynamics. Consequently, we can further simplify our generalization error bound and obtain a more precise analysis of the leading $\\Gamma$ terms. If we do not have detailed assumptions about the learning dynamics, we may need to carry out the training process sufficiently to extract enough information to determine our generalization error bound. Potentially, a practical application of our framework is to train a model with a smaller size on a smaller dataset and then use its observed training trajectory to compute the LPK‐based generalization bound. This “mini‐experiment” provides an early, data‐driven estimate of how well the full‐scale model is likely to generalize without the computational cost of training a very large network.\n\nBy monitoring the evolution of our bound $\\Gamma$ during training, we can predict the overfitting for overparameterized NNs and identify optimal stopping time for training without access to test data. Our bound can also be used as a regularization in the training. Moreover, our bound can also serve as a proxy to compare model architectures in Neural Architecture Search (NAS), e.g., [1, 2, 3, 4].\n\n[1] Mellor, J., Turner, J., Storkey, A., and Crowley, E. J. Neural architecture search without training. ICML 2021.\n\n[2] Chen, W., Gong, X., and Wang, Z. Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective. ICLR 2021.\n\n[3] Mok, J., Na, B., Kim, J.-H., Han, D., and Yoon, S. Demystifying the neural tangent kernel from a practical perspective: Can it be trusted for neural architecture search without training? CVPR 2022.\n\n[4] Chen, Y., Huang, W., Wang, H., Loh, C., Srivastava, A., Nguyen, L. M., and Weng, T.-W. Analyzing generalization of neural networks through loss path kernels. NeurIPS 2023.\n\n\n**Q3. Computing this term is very expensive as it requires the full gradient history, making it hard to use in practice.**\n\nA3. The computation of our bound is tractable. In the $\\Gamma$ term (Eq. (3)), as Reviewer xevc,\n mentioned $L_S(w_0) - L_S(w_T)$ can be easily computed from the training loss. For $\\sum_{i=1}^n \\int_0^T ||\\nabla_w \\ell(w_t, z) ||^2 dt$, we can compute the per-sample gradients (which can be computed in parallel for all the samples) at each training step, calculate their 2-norm, and sum over the training steps. The computation cost of the bound is similar to that of gradient descent training of the model. For large datasets, we can estimate $\\sum_{i=1}^n \\int_0^T ||\\nabla_w \\ell(w_t, z) ||^2 dt$ with a subset of training samples, such as the batch data used at each training step in SGD. We will add a detailed discussion of the computational complexity of evaluating the LPK term $\\Gamma$.\n\n\n**Q4. Do we have a way to bound the term $\\int_0^T ||\\nabla_w \\ell(w_t, z)|| dt$?**\n\nA4. A naive bound of $\\int_0^T ||\\nabla_w \\ell(w_t, z)|| dt$ is $L^2 T$ using the Lipschitz property. It is hard to give a tighter bound for general cases. But for more specific models, such as the case studies in Sec 6, we can derive tighter bounds for this quantity. \n\nFor the NTK case, in line 730, we bound it by $\\sum_i^n \\int_0^T ||\\nabla_w \\ell(w_t, z_i)|| dt \\leq \\frac{n \\lambda_{max} \\|\\|f(w_0, X) - y\\|\\|^2 }{2 \\lambda_{min}}  ( 1 - e^{-\\frac{2 \\lambda_{min} T}{n}})$. \n\nFor the kernel regression, in line 744, we bound it by $\\sum_i^n \\int_0^T ||\\nabla_w \\ell(w_t, z_i)|| dt \\leq \\frac{K_{max} n}{2}||w_0 - w^*||^2$.\n\n**Q5. Do Gradient Descent and Gradient Flow have a difference in the order of the resulting bound?**\n\nA5. In the early phase of this paper, we computed the gradient flow and found that the difference between the gradient flow and gradient descent with a small learning rate is very small, as also shown in [5, 6]. Therefore, the bounds of gradient flow and GD should not differ much under certain conditions of the learning rate. We will present a simulation to control the difference between the GD and gradient flow dynamics for two-layer neural networks on a portion of the MNIST dataset.\n\nOur experimental findings demonstrate a strong correlation between our bound and gradient descent, particularly when employing reasonable learning rates. In our simulation, two-layer neural networks (NNs) and ResNets were trained with learning rates of 0.01 and 0.001, respectively, which are widely adopted learning rate settings in practical applications. These experimental results also suggest the potential extension of our theory to discrete SGD with a constant learning rate, which we intend to explore further in future research endeavors. Furthermore, it is noteworthy that [5] indicates that deep neural networks with homogeneous activations can be approximated by gradient descent. Consequently, we can potentially transfer our analysis of gradient flow for neural networks to a gradient descent training framework based on this observation. We will elaborate on this limitation in the revised version of our paper.\n\n\n[5] Continuous vs. Discrete Optimization of Deep Neural Networks. NeurIPS 2021.\n\n[6] Chen, Y., Huang, W., Wang, H., Loh, C., Srivastava, A., Nguyen, L. M., and Weng, T.-W. Analyzing generalization of neural\n networks through loss path kernels. NeurIPS 2023.\n\n---\nWe are happy to address any further questions and feedback."}]

Author rebuttal:

Meta-review: The paper investigates the theoretical generalization properties of gradient-based optimization. The authors present a generalization bound for gradient flow that parallels classical Rademacher complexity bounds known for kernel methods, with the key claimed innovation being a data-dependent kernel termed the loss path kernel (LPK). The authors claim that unlike static constructions such as the NTK, the LPK evolves with the optimization trajectory, capturing both data and training dynamics to yield sharper and more informative guarantees. The results presented by the authors emphasize the role of the gradient norms of the training loss throughout optimization in determining generalization performance. The bound recovers known kernel regression results for overparameterized neural networks, while also illustrating how neural networks enable feature learning beyond kernel methods. The authors also carry out some empirical evaluations to further support their theory.

Reviewers noted several strengths: the framework captures training trajectories in a novel way, unifies kernel-based generalization analysis with gradient dynamics, and is supported by experiments that show the proposed bounds track the generalization gap on datasets such as CIFAR with ResNets and two-layer networks. The work is also valued for its clear proofs and connections to feature learning. On the other hand the reviewers had some concerns that the analysis remains idealized, as it focuses on continuous-time gradient flow rather than the discrete SGD used in practice. Another concern was that the computation of LPK can be costly, and some of the technical assumptions, such as Lipschitzness and smoothness, may be restrictive. The authors addressed many of these concerns in their rebuttal. Overall, while some practical questions remain, the consensus is that the paper makes a meaningful theoretical advance, and I thus recommend acceptance.
Decision: Accept (poster)