Analyzing Generalization of Neural Networks through Loss Path Kernels
Authors: Yilan Chen
Wei Huang
Hao Wang
Charlotte Loh
Akash Srivastava
Lam M. Nguyen
Tsui-Wei Weng
Venue: NeurIPS 2023 poster (2023)
Keywords: generalization
deep learning theory
neural tangent kernel
neural architecture search
TL;DR: We derive tight generalization bounds for NNs trained by gradient flow through a connection between NN and kernel machine.

Abstract: Deep neural networks have been increasingly used in real-world applications, making it critical to ensure their ability to adapt to new, unseen data. In this paper, we study the generalization capability of neural networks trained with (stochastic) gradient flow. We establish a new connection between the loss dynamics of gradient flow and general kernel machines by proposing a new kernel, called loss path kernel. This kernel measures the similarity between two data points by evaluating the agreement between loss gradients along the path determined by the gradient flow. Based on this connection, we derive a new generalization upper bound that applies to general neural network architectures. This new bound is tight and strongly correlated with the true generalization error. We apply our results to guide the design of neural architecture search (NAS) and demonstrate favorable performance compared with state-of-the-art NAS algorithms through numerical experiments.

Analyzing Generalization of Neural Networks through Loss Path Kernels
Yilan Chen UCSD CSE yi yilan@ucsd. edu
Wei Huang RIEKN AIP wei fai.hhang.... vr@riken. jp
Hao Wang
MIT-IBM Watson Al Lab
hao0ibm com
Charlotte Loh MIT EECS
Akash Srivastava MIT-IBM Watson AI Lab akash.sriveee www.assaaaiiiiiaaaeeeae com
Lam M. Nguyen
IBM Research
cloh$mit edu
LamNguyen. Mimniguyen.MLTD@iibmm... WWw.DiLM..Comm
com
Tsui- Wei Weng" UCSD HDSI
lwengGucsd.eed
Abstract
Deep neural networks have been increasingly used in real-world applications, making it critical to ensure their ability to adapt to new, unseen data. In this paper, we study the generalization capability of neural networks trained with (stochastic) gradient flow. We establish a new connection between the loss dynamics of gradient flow and general kernel machines by proposing a new kernel, called loss path kernel. This kernel measures the similarity between two data points by evaluating the agreement between loss gradients along the path determined by the gradient flow. Based on this connection, we derive new generalization upper bound that applies to general neural network architectures. This new bound is tight and strongly correlated with the true generalization error. We apply our results guide the design of neural architecture search (NAS) and demonstrate favorable performance compared with state-of-the-a NAS algorithms through numerical experiments.
Introduction
Deep learning models have been increasingly used in applications with significant societal impact. Therefore, is crucial to ensure that these models perform well not only on the training data but also on the new and unseen data. Classical learning theory attributes the generalization ability of machine learning (ML) models to the small complexity of the hypothesis class [56]. However, modern ML models, such deep neural networks (NNs), have billions of parameters yet still exhibit strong generalization abilities [26, 9]. This is because various elements of the learning algorithms, including optimization methods, training data, and neural architectures, can all influence the inductive bias. which in turn shapes the generalization abilities of neural networks [29, 40]. While the overall hypothesis class may be large, the "effective domain" of this class, which ultimately determines the model's 's generalization abilities, is often much smaller [54, 24, 50, 15]. Hence, it is vital to develop algorithmic generalization bounds capture this effective domain of the hypothesis class.
There has been significant work investigating the generalization of neural networks in their infinite- width regime through kernel methods [28, 3, 32, 2, 11]. They showed that an infinite-width NN
CCoresponnence to: Yilan Chen and Tsui-Wei Weng.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table Comparison with existing NTK-based generalization bounds. C (X,, X) is the NTK on training samples and H is the NTK of the first layer. L represents the number of NN layers. We highlight some unique properties of our results in blue color. "During training" means our bound can be calculated at any time during training while existing NTK-hased bounds only hold for the NNs at convergence. "Multi-outputs" means our bound holds for NNs with multiple outputs.
Arora et al. [2)
Cao & Gu [11]
Ours
Bound
2Y 112-) YY
ÓLL ( "Y)
Theorem 3, Theorem 5
Model
Uldd two-layer FCNN
Ultra-wide FCNN
Generul continuously differentiable NN i..d. data
Data
i..d. data with ||=]]| =1
Lid. data with ||a]]| =1
Loss
Square loss
Logistic loss
Continuously differentiable & bounded loss Yes
During training
No
No
Multi-outputs
No
No
Yes (Stochastic) gradient flow
Training algorithm
GD
SGD
trained by gradient flow and squared loss is equivalent to kernel regression with neural tangent kernel (NTK) [28, 3J. Moreover, Arora et al. [2]. Cao & Gu [11] further characterized the generalization behaviors of such ultra-wide NNs by deriving data-dependent and NTKKbased generalization bounds. However, they only considered ultra-wide fully connected NNs with a square (or logistic) loss function. practice, NNs are usually not ultra-wide and have more complex architectures such as CNNs. Hence, it is crucial to establish generalization bounds that hold in a more general setting,
In this paper, we analyze the generalization capability of NNs trained using (stochastic) gradient flow across a wide range of NN architectures. Our key technical contribution is to establish a new connection between the loss dynamics of (stochastic) gradient flow and general kernel machines with a special kernel that we named the loss path kernel. This new kernel calculates the similarity between two data points by integrating the inner product of the loss gradient evaluated these points, along the path determined by the gradient flow. Based on this connection, we develop a novel generalization bound by analyzing the complexity of kernel machines induced by various training sets. Our generalization bound is tight and can be applied to a broad class of NN architectures, not restricted to ultra-wide NNs (see Table 1 for a comparison with existing results derived from NTK theory). Numerical experiments demonstrate that our bound maintains strong correlation with the true generalization error of NNs trained with gradient descent (GD) (see Figure and in Sec. 6 & 7). Given this observation, we use our generalization bound to guide the design of neural architecture search (NAS) and demonstrate through numerical experiments that our approach can achieve favorable performance compared with state-of-the-an -tee-art training-free free and cilimmum-triiiing NAS algorithms [37, 13, 39J. In summary, our contributions are:
In Sec. 4.1 and 5, show for the first time that the loss of NNs trained by (stochastic) gradient flow is equivalent to a general kernel machine. This result enables us to investigate the generalization capability of NNs from the perspective of kernel theory.
In Sec. 4.2 and 5, derive tight generalization bounds for NNs based on the aforementioned equivalence. Our result is very general as it holds for any continuously differentiable NN architec- tures including fnite-width and infinite-width NNs. Experiments demonstrate that bounds are tight (4690x tighter than existing norm- norm-based bounds and 55x tighter than existing based bounds shown in Appendix A.2) and highly correlated with the true generalization error.
In Sec. 6 and 7, apply our theory to study special cases including infinite- NNs, stable algorithms, and norm-constrained NNs. We apply our bound to guide the design of NAS. Numerical experiments demonstrate that approach achieves favorable performance compared with state- of of-the-art NAS algorithms on WAS-Bench-200 benchmark [19].
2 Related Work
Generalization theory in deep learning. Generalization is a crucial aspect of deep learning theory and various techniques have been proposed to study it. For example, Bartlett et al. [7] derived tight bounds for the VC dimension NNs with ReLU activation functions. There is also a line of work that measures the capacity of NNs based on different norms, margins [5, 41, 6, 44], and sharpness- measures [42, 43, 1] to explain the generalization behaviors of NNs. Additionally, there are theories studying the generalization of NNs from PAC-Bayes [35, 22] and information-theoree
approach
2

---

[48, 58]. For example, Dziugaite& & Roy [22] numerically evaluated and optimized the PAC-Bayes bound of stochastic NN and obtained a non-vacuous generalization bound. In contrast, we study the generalization of NNs by building a new connection between NNs and kernel machines. We refer readers to Valle-Pérez Louis [55] for a more comprehensive review of the generalization theory of NNs.
Neural tangent kernel (NTK). NTK was first introduced in Jacot et al. [28], where the authors demonstrated that a fully-trained, infinite-width NN follows kernel gradient descent in the function space with respect to the NTK. Under gradient flow and squared loss, the fully- trlynetrained anfinite-widde NN is equivalent to kernel regression with the NTK [28, 3]. Chen et al. [14] further established the equivalence between infinite-widd NNs and regularized kernel machines. Arora et al. [2] studied the generalization capacity of ultra-wide, two-layer NNs trained by GD and square loss, while Cao & Gu [11] examined the generalization of deep, ultra-wide NNs trained by stochastic gradient descent (SGD) and logistic loss. Both studies derived generalization bounds of converged NNs based on NTK. Besides, Huang et al. [27] studied the convergence and generalization of PAC-Bayesian learning for deep, ultra-wide NNs. Later, Domingos [17] showed that every model trained by gradient flow is "kernel machine" with the weights and bias as functions of input data, which however can be much more complex than a typical kernel machine and our general kernel machine in Definition 2. Chen et al. [14] showed that every NN trained by gradient flow is a general kernel machine but their kernel is valid only in very limited cases when the loss gradient of output is constant. Otherwise, the kernel is not symmetric and not valid. In this paper. we consider an equivalence between the loss of NNs and general kernel machines, which resolves the previous asymmetric problem of the kernel function and also makes the generalization analysis of multi-outputs easier.
Neural Architecture Search (NAS). NAS aims to automate the discovery of top- ho--pefformanc neural networks to reduce human efforts. However, most existing NAS algorithms require heavy training of a supernet or intensive architecture evaluations, suffering from heavy resource consumption [47, 34, 18, 33J. Thus, it is crucial to develop training-free or cisimmum-ttriinng NAS algorithms to reduce the computational cost and select the best architecture at the same time [37, 13, 39]. Since our generalization bound has a strong correlation with the true generalization error, we apply it to design minimum-traim training NAS algorithm. We demonstrate in Table 2 that with a simple random search algorithm, our approach can achieve a favorable performance compared with state-of-the. the-art training-free and minimum-traininn NAS algorithms.
3 Kernel Machine and Loss Path Kernel
In this section, we define notation, provide brief overview of kernel methods, and introduce the main concept of interest-the loss path kernel.
3.1 Preliminaries
Consider supervised learning problem where the task is to predict an output variable in y C RR* using vector of input variables in X C Rdd Let 2 & X' x y. We denote the training set by S A {21) with 2; A (x;, yv) E Z. We assume each point drawn i.i.d. from an underlying distribution Ju. Let
X [r.. m.,)" T R Y yy,.... yym"" E R.nk and = [X,Y] Rex(d+)),
We express neural network in a general form f(w, x) RP x Rd + 1 where E IRP represents its parameters and æ E IRd is an input variable. The goal of a learning algorithm is to find set of parameters that minimizes population risk (w)(
Ezza [f(w, x)] where f(w, 2) A f(f(w, 2). y) loss function. Throughout this paper, we assume that E(wr 2) [0,1] and continuously differentiable. In practice, the underlying distribution fa is unknown so the learning algorithm minimizes an empirical risk on the training set instead: Ls(w) + >" E(w,,2) The generalization gap is defined as (w) Ls(w). The loss gradient with respect to the parameters w is V w l z) = [w x) V fl( x), y) Rex1, Our analysis only requires that E(w, =) continuously differentiable w.r.t. w and z so ʃ can be either fully connected neural network or convolutional network residual network.
3

---

3.2 Kernel Method
Kernl methods [16, 51, 53] search for linear relations in high-dimensional feature space by using kernel functions. Rather than computing the coordinates in the feature space explicitly, they only need calculate the inner product between data pairs, making computationally easier.
kernel is a function K X x X' - R. such that for all æ, x' E X, K(x, x²) - (f) ((x)),
where Φ X F is a mapping from X' an (inner product) feature space F.
Proposition 1 (Shawe-Taylon et al. [53]). A function : X X + + R. which is either continuous or has a finite domain, is a kernel function if and only if is a symmetric function and, for any finite subset of X, 21," ... Bn E X, the matrix K (XX,X) is positive semi-definite, where K(X,X) is matrix whose (i, )-th entry is (.);
Definition (Kernel machine). Let H. be the reproducing kernel Hilbert space (RKHS) corresponding to kernel K K(x,, x²) (arx), ((x'))
))- A kernel machine g X IK is linear function in H such that its weight vector 33 can be expressed as a linear combination of the training points, i.e. g(m) (B, (x)) + >i=1 (3; K (2); 2) + b. where En= (x(()) and b is constant. The RKHS norm of g ||g|| EE a (x:) V /Ei, asag K( w.))
Next, we introduce general kernel machine, which generalizes the concept of kernel machine. Definition 2 (General kernel machine). A general kernel machine g X' - R with kernel K (z, x') is g(x) = Ei= a (z,, x) + ((x), where : X + R is a function of æ. When h(x)) is a constant, g(x) reduces kernel machine in Definition 1.
3.3 Neural Tangent Kernel and Loss Path Kernel
Neural tangent kernel (NTK) has been introduced by Jacot al. [28] to establish an equivalence
between infinite-width NNs and kernel regression. After then, there is a growing line of work applying NTK theory study properties of over- werrpaarameterized NNs, such as optimization convergence [21, 20] and generalization capability [2, 11]. The neural tangent kernel [28] associated with a NN f fww, x) at w is defined as Ó(w; xr, œ²) V / x) v v (w, x²" E R Under certain conditions, such as infinite width limit and NTK parameterization, the NTK converges to a deterministic limit kernel (xx, x²) I that remains constant during training: θ(w; x, x') - ((x, x') I,, where ((x,a) : Rd Rd + R a scalar kernel and I is a k identity matrix. Next, we introduce the main concepts of interest in this paper: the loss langent kernel and the loss puth kernel. They are central to characterizing the generalization behaviors of NNs trained by (stochastic) gradient flow.
Definition 3 (Loss Tangent Kernel (LTK) K). The loss tangent kernel associated with the loss function f(w, 2) is defined as K(w; 2, z²) = (V u w 2), V 2²)) E R.
The LTK K has a natural connection with the NTK Ô by applying the chain rule:
K(w; = V f( =) é(w; x, x' \'VV f((,, (')...).
Next, we introduce the loss path kernel, which integrates the LTK along given path of the parameters. Later, will characterize this path via the gradient flow dynamics.
Definition 4 (Loss Path Kernel (LPK) K2). Suppose the weights follow a continuous path w(t): [0. + Rp in their domain with a starting point w()) wD, where T is predetermined constant. This path is determined by the training set and the training time T. We define the loss path kernel
associated with the loss function (ww, z) along the path as (r z'; & f K(w(t); 2, z d')
In Appendix B, show LTK is Riemann integrable the integral in the above definition is well- defined. Intuitively, the LTK K(wr; 2, 2') measures the similarity between data points z and z' by comparing their loss gradients when evaluated using fixed neural network parameter w. The LPK Kr 2, S) measures the overall similarity during the entire training time.
3.4 Rademacher Complexity
Rademacher complexity [52] measures the complexity of hypothesis class. It takes into account the data distribution and is central concept in statistical learning theory. Next, we recall its definition and generalization upper bound via Rademacher complexity.

---

Definition (Empirical Rademacher complexity Rs( Let [f be hypothesis class. We denote G the set of loss functions associated with each function in F, defined as g = {g: (æ, y) (()()), y). F). The empirical Rademacher complexity of G with respect to sample set S is defined as: Rs(g)= x2 Eo supgeg Ei=1 0:g( (:9(z))], where (01,..., nn) and o, are independent uniform random variables taking values in {+1,
Theorem 1 (Theorem 3.3 in Mohri et al. [38]). Let be family of functions mapping from 2 to [0, 1). Then for any 8 E (0, 1), with probability at least 1 - over the draw of an i.i.d. sample set S =
(zi,...,Zzn) Zn), the following holds for all g E 9: IE: [9(2)] E g(z)) - 2Rs(9)+3V
(2/6)
2n
Gradient Flow
In this section, we establish a new connection between the loss dynamics of gradient flow and general kernel machine equipped with the LPK. Using this result, we introduce a new generalization bound by analyzing the complexity of the collection of kernel machines induced by all possible training sets. Our analysis applies to a wide range of neural network architectures, as long as they are continuously differentiable. Our numerical experiments validate the tightness of our bound and its strong correlation with the true generalization error.
4.1 Loss Dynamics of Gradient Flow and Its Equivalence with General Kernel Machine
Consider the gradient flow dynamics (gradient descent with infinitesimal step size):
dro(t) d/ V vwwl((((()
V (w)())),,
1=1
The above ODE is well-defined for wide variety of conditions, e.g. local
of the gradient or semi coni-convyxity the loss function [49, 23]. Next, we establish its connection with the general kernel machine (KM) in the following theorem.
Theorem 2 (Equivalence with general KM.). Suppose wT)) wr is solution of (1) time T with initialization w0))= = Wy. Then for any z E 2,
(WWT, 2)
Σ 1=1
1 Kr 2); E(wo, 2),
where Kr is defined in Definition 4.
The above theorem demonstrates that the loss of the NN at a certain fixed time is a general kernel machine. Herein, Ky is the LPK and we prove in Appendix C.I that it is a valid kernel. Unlike previous NTK works that establish the equivalence between infinite-wiin width NNs and kernel machines, our equivalence is much more general and holds for any NN that is continuously differentiable. Based on this equivalence, we characterize the generalization of NNs from the perspective of kernels. Note that Kr is a function and this property enables us to establish a data-dependent generalization bound shortly.
4.2 Generalization Bounds
We introduce the main result in this section: a generalization bound for NNs whose weights follow gradient flow in (1) at time T. We derive this bound by analyzing the Rademacher complexity of the function class of kernel machines induced by different training sets with constrained RKHS norms. Recall that each training set yields a distinct LPK. We define the collection of all such LPKs by
Kr A (Kr()55)) : supp( @a) 1 2/:)) S B²},
where some constant, S' = ( drawn from μ. and supp(u @n) is the support set of 4 on Recall that S {=1,..., 2n is the training
)/ ). / on the joint distribution of n i.i.d. samples
5

---

set. Note the set in (2) includes the case of S' = if 3 Ens 2,; S B². Then we introduce a class of general kernel machines, corresponding to all different kernels in Kr.
Gr 0(()) - " ((ll))=)
f(wwo 2) K(.,;;() E ka)
Note that g(²) E GT corresponds to ((wr, 2) trained from one possible dataset S' E supp(u Next, we compute the Rademacher complexity of GT and it to obtain generalization bound.
Theorem 3. RGTG I min(U1, U2}. Here
U1 B
sup K(.;S")ET
Tr(K(Z,2;8))
Σ AZz,, itj
2 2I
U2 inf
+
t>0
n
n
where G [g( = (g(z1), ..... g g(2n)) g GT). ( (97,e, IIII)) is the covering number of G with the &m-morm and
1
2zz,, =
K(zi, Zj:)')):'') inf K(-.:S))RRT
sup
2z;
The term U1 is composed by two components ''KK(r Tr(K Z; 8")) and AZz,, zz). The first component, according to the definition of LPK, quantifies the maximum magnitude the loss gradient in KT evaluated with the set S throughout the training trajectory. The second component assesses the range of variation of LPK within the set Kr. The term U2 is obtained from analyzing the covering number of Gr. It shows that if the variation of the loss dynamics of gradient flow with different training data is small. then the complexity of Gr will also be small. The norm constraint + Eis Kr (z/, S") < B balances tradeoff between the tightness of the bound and the expressiveness of the GT (the number of datasets covered). Combining these two bounds with Theorem 1, we obtain the following generalization bound.
Corollary 1 (Generalization bound for NN). Fix B O. Let Rgg (Gr) min (U1, U2) where U1 and U2 are defined in Theorem an i..dd. sample set S {zi) if A/ Eng (r(ze, 2): B², the following holds for E(WT, that trained from
3. For any 8 E (0, 1), with probability at least 1 - å over the draw of
1og(2/8)
La(Ar(S)) Ls 2R (Gr) + +3
2n
where wT AT(S) is the output from the gradient flow (1) at time T by using S as input.
Our result owns many compelling properties.
First, our bound holds in general setting as it does not hedge on a special NN architecture. In contrast, existing works [2, 11] only consider fully connected NNs and require NN to be ultra-wide.
Our bound depends the data distribution through the quantities in U1 and U2. This property not only sigmificantly tightens our bound but can also help explain some empirical observations of NNs. For example, different from classical generalization theory, e.g. VC dimension, our complexity bounds depend on the labels directly, which helps explain the random label phenomenon [59] as shown in Figure 3 in Sec. 7.
Our experiments in Sec. (Figure 2) demonstrate the tightness of the generalization bound. Intuitively, our bound is tight because (1) instead of considering the entire hypothesis class, we focus on the subset of interest characterized by running gradient flow from starting point wp; (2) we get the bound from equivalence between NNs and general kernel machines, whose generalization bounds are tighter. Finally, we compare our generalization bound with two existing NTK- bounds in Table 1.

---

Stochastic Gradient Flow
In the previous section, we derived a generalization bound for NNs trained from full-batch gradient flow. Here we extend our analysis stochastic gradient flow and derive corresponding generalization bound. To start with, we recall the dynamics of stochastic gradient flow (SGD with infinitesimal step size). Let S S (I....,7) be the batch size. We establish a new connection between the loss dynamics of stochastic gradient flow and general kernel machine. Then we investigate the complexity of the collection of such kernel machines that can be induced by various training sets.
,....,,7, n) be the indices of batch data used in time interval [t, t 1] and |S&] m
Theorem 4. Suppose (T) wr is solution of stochastic gradient flow time T E N with initialization w(() wy. Then for any 2 E 2,
T-1
K(wr, 2) = Σ
1 m
K,,41 (2, E(wp, +(
1= iES,
where (1,14( (2, = 1( ((w(t); dt with K defined in Definition 3.
The above theorem shows that the loss of the NN in stochastic gradient flow dynamics can be characterized by sum of general kernel machines. In particular, when we use the full batch each time interval (i.c., m = n)), the above result recovers Theorem 2. To study its generalization behavior, we introduce the class of kernel machines induced by different training sets S' E supp( with constrained RKHS norms. Specifically, given B, > for t 0,..., 1, we define
Kr = [(Ko.1..:38), ... ""r.,",,KK-i,,, S' E supp(u
Sm
Σ iJESS
Ke.+1 S BP}.
m2
Note this set includes the kernel induced by the training set S if it satisfies the constraints. Then f(wr, 2) trained from feasible S' E su form function class
t=0 iES, m Gr (ΣΣ-) CK-'KKuu12 (2,4112,, (2:)) E(wo, 2) K(: E Kr).
(3)
Next, we upper bound the Rademacher complexity of the function class Gr. This bound can naturally translate into generalization bound by equipping with Theorem 1.
Theorem 5. The Rademacher complexity of GT defined in (3) has upper bound:
T-1
B
Rs(GT) <
I + Σ Az(zi zz).
sup k
V
1=
where (, 2j) = (UPK(";)))E 1 infk(,,S))K,, Ke,t (Z 2z;
We assumed that mini mini-batches indices S, are chosen before training. However, our analysis can be extended to accommodate random mini-batch selections of any sampling strategy by enumerating all potential S, in KrT,
Case Study & Use Case
In the previous sections, we derived generalization bounds for NNs trained with (stochastic) gradient flow. These bounds may initially appear complex due to their dependence on the training process. Here we show that these bounds can be significantly simplified by applying them to infinite-width NNs (and stable algorithms Appendix E.2, norm-constraint NNs in Appendix E.3). Moreover, we demonstrate that our generalization bounds maintain a high correlation with the true generalization error. As result, we use them to guide the design of NAS, and our experimental results demonstrate that this approach has favorable performance compared with state-of-the art algorithms.
7

---

6.1 Infinite-width NN
In this subsection, we consider special case of -ndinite-width NNs trained by gradient flow and derive pre-computed generalization bounds. We focus on gradient flow to simplify the presentations but our results can be directly extended to stochastic gradient flow. For an infinite-width NN, under certain conditions, the neural tangent kernel keeps unchanged during training: θ(w,; æ æ') - O æ²). In- Consider a p-Lipschitz loss function, i.e. , =)l| S p. The Rademacher complexity in Theorem 3 can be bounded by Rg( S U00 where
pBVT U
Σ 4
(0(,,
n
In this infinite-width regime, our bound has no dependence on the initialization wo since the NTK converges to deterministic limit and has dependence the parameters. That means the bound holds for all possible wy of infinite-width NNs trained by gradient flow from initialization. Compared with the bound ( Y (e) (
in [11], U. has several advantages: (1) it has dependence on the number of layers L; (2) it holds for NNs with multiple outputs.
6.2 Correlation Analysis and NAS
As practical application, we apply generalization bounds to guide the design of NAS. We first introduce a quantity Usgd simplified from the bound in Theorem 5, defined as
T-1 Σ n
Usgd=
En
Σ i.jES,
(z,, (Z,23+
m²
Usgd can be computed along with training NN via SGD on a training set S. Combining it with the training loss, we define the following quantity as an estimate of the population loss:
Gene(w, (w, 8) Ls (w) + 20 sgd
(5)
We analyze the correlation between Gene(w, S) and the true generalization error by randomly sam-
Kendsll's tau 0.75
Kendsll's tau 0.17
pling 100 NN architectures from NAS-Bench-201
[19]. For each, we compute both Gene(w, S)
Tos or of CONVE
and the true generalization error. Since solving the gradient flow ODE is computationally infea- sible for the large NNs in 20S-Bench-201, we apply a trapezoidal rule to approximate the integra- tion in LPK K1,+1- This approximation enables us to compute UNU efficiently. Figure/ demon- strates the correlation between Gene(w, S) and the test error. The left figures plot the test error at epoch 2 against Gene(w, S) of the respective epochs, showing a strong positive correlation be- tween them. The right figures plot the test error at convergence against Gene w., S') at epoch or which also demonstrate positive correlation. The outlier is caused by some architecture with large loss gradients. This experiment shows that Gene(w, S) at the initial training stage can predict NNs at convergence. Based on this observation, we use Gene(w, S) as metric in NAS for selecting architectures at the initial training stage (see Table 2). This approach significantly reduces computational costs compared with training- based NAS algorithms [47, 34, 18, 33].
Geneiia 50 wt epech
Gerecia, S1 at epoch
200 Sm 2t comnec 1osoogen
Tost eprch
Genete.
Figure 1: Correlation between Gene(w, S) and the
test error on CIFAR- 100 at epoch I and epoch 2. Kendall's shows they have strong positive corre- lation.
the performance
8

---

Logistic loss training samples
(b) Logistic loss bound
(c) Rademacher complexity bound
0.8
gep
0.0
KffGc, zu 8
eetor
Ryoo-, 50
0.5
006
ky(rr Bouns, 100
0.05
Roiill 100 of
0.4
0.4
0.04
0.2
0.02
0.3
0.00
200
1000
600 500
1000
200 400
Figure 2: Experiment (I). (a) shows the dynamics of logistic loss for 5 randomly selected training samples for NN trained by gradient flow (NN GF). NN trained by GD (NN GD), and the equivalent general kernel machine (KM) in Theorem 2. The dynamics of NN GF and KM overlap and thus verify the equivalence Theorem 2. The dynamics of NN GF and NN GD are consistently close throughout the training process. (b) shows NN GF's training loss, test loss, test error, and upper bound for Ly (wr) in Corollary 1. (c) shows that the complexity bound R2g (Gr) in Corollary 1 captures the generalization gap (,((r) - LLsssr (wr) well. It first increases and then converges after sufficient training time.
7 Numerical Experiments
We conduct comprehensive numerical experiments to demonstrate our generalization bounds. We observe that our complexity bounds are tight with respect to the generalization gap and can capture how noisy label influences the generalization behaviors of NNs. Moreover, we apply Gene (w, S)
in (5) NAS and demonstrate favorable performance compared with state-of-the-art algorithms.
(I) Generalization bound in Corollary 1. In Figure 2 (more detailed in Figure A.4), we use a logistic
loss train a two-layer NN with 100 hidden nodes for binary classification MNIST and [31] by full-batch gradient flow and compute its generalization bound. Due to the computational cost of solving the gradient flow ODE and computing the kernel, we only train and calculate the bound on n = 1000 training samples. The bound would be tighter with more training samples. The NN is initialized using the NTK parameterization [28]. We use the Softplus activation function, defined as Softplus(z)- = 3 In(1 + e This function is continuously differentiable and serves as a smooth
approximation to the ReLU activation function. In our experiments, we set / 10. To train the NN via gradient flow, we solve the gradient flow ODE given by (1) decide the NN parameters. For the equivalent general KM, we compute the LTK using the NN parameters and integrate it to get the LPK Ky. These ODEs are computed with torchdiffeq [12]. To estimate the generalization bound, we train the NN on (20, 50, 100) independently sampled training sets S' to estimate the Krr and Gr, and the supremum
the bound U, is estimated by taking the maximum over the finite set Ky. For Ui. we compute an upper bound of it by setting
the largest & distance between any two g(Z) E G and N(GS, e. IIII) = 1 because in this case any (Z) E G.S. will satisfy as an e-cover. We each experiment five times and plot the mean and standard deviation. The numerical experiments demonstrate that our complexity bound is tight and can capture the generalization gap well. As the number of S' increases, our bound converges to the true supremum value. To estimate the true supremum value, we apply the extreme value theory in Appendix A.3 and show the gap between the finite maximum and supremum is small, validating using a finite maximum an estimate for bound.
We train the NN using GD with finite learning rate ry 10 to compare with the NN trained by gradient flow. The training time t = 17 x training steps. In Figure 2 (a) and Figure A.4 (a)(b), we observe that the loss of the NN trained by GD and that trained by gradient flow are consistently close throughout the entire training process. Consequently, while we established upper bounds for NNs trained by gradient flow, these results can serve as (approximate) upper bound for NNs trained by GD with a finite learning rate.
Notably, for the NN in this experiment, the VC dimension [7] is 55957.3, the norm- norm-based bound in [6] is 140.7 at T = 1000, and the NTK- bound for an ultra-wide NN [11] is 1.44, which are all vacuous (larger than 1), while our bound is tight (0.03 at T = 1000). See a detailed comparison in Appendix A.2. We also conduct an experiment of three-layer NN (3072-100- 100-01 trained on binary CIFAR- 10 (cat and dog) [30] in Figure A.5, where there is a larger generalization gap.
9

---

Table 2:
Experiment (II... Comparison with statc-of-the-art training free/minimum taraiiinnn NAS methods on NAS- MAS-Bench-201. Test accuracy with mean and deviation are reported. "Best" is the best accuracy over the four runs. "Optimal" indicates the best test accuracy achievable in NAS-Bench-201 search space. RS: ran- domly sample 100 architectures and select the one with the best metric value.
Generalization gao #ffice
0.2
CIFAR-10 Accuracy
CIFAR-100
Algorithm
Best
Accuracy
Best
0.1
Baselines
TENAS [133]
93.0810.115 93.64
93.25
70.37 69.77
73.16
0.0
0.2
0.4
0.6
0.8
10
RSALGA [39]
Portion labal noise
Ours
Figure 3: Experiment (II). Generalization
RS Gene(w, S),
93.68:1.112
93.84
72.02:1143
73.15
bound with label noise at T = 20000.
RS Gene S)
93.79-+0.18
94.02
0..36++0.33
73.15
Optimal
94.37
73.51
(II) Generalization bound with label noise. The settings are similar to Experiment (I) except we corrupt the labels with different portions of noise and calculate the bound after training NN until T' = 20000, We estimate the bound with 20 training sets S'. The results in Figure 3 show that our bound has strong correlation with the generalization gap and increases with the portion of label noise. Unlike classical generalization theory, e.g. VC dimension, our generalization bound can help explain the random label phenomenon [59].
(III) Neural architecture search (NAS). We apply Gene(w, S) in Eq. (5) to guide the design of NAS. The results shown in Table 2. We
simple random search (RS) with Gene(w, S), where 100 architectures are sampled from the search space for evaluation, and the architecture with smallest Gene(w w. S) is selected. Usgd is estimated with a batch of data of size 600. Build upon Sec. 6.2, we apply Gene (w S)1 and Gene w, S)2 (Gene(w w, S) after training and 2 epochs) to select NN architectures at the initial training stage in order reduce computational costs. We compare our method with state tfat--ofthhe-ar training-free/mininn free/mmnimumntrrannne We run the experiments four times with different random seeds and report the mean and standard deviation. We reproduce the results in Chen et al. [13] using their released code and directly adopt the results reported in Mok et al. [39] as they did not release the code. The results show our approach of RS + Gene(w,S) S) can achieve favorable performance compared with of-th-rf- NAS algorithms.
NAS algorithms [13, 39].
Conclusion and Future Work
In this paper, we establish a new connection between the loss dynamics of (stochastic) gradient flow and a general kernel machine. Building upon this result, we introduce generalization bounds for NNs trained from (stochastic) gradient flow. Our bounds hold for any continuously differentiable NN architectures (both finite-width and ultra-wide) and are generally tighter than existing bounds. Moreover, for infinite-width NNs, we obtain a pre-computed generalization bound for the whole training process. Finally, we apply our results to NAS and demonstrate favorable performance compared with state-of-the-art NAS algorithms.
There are several directions for future research. First, evaluating our generation bounds relies on the loss gradient, which may contain private and sensitive information. One potential fix would be accessing such information in differentially private manner and it would be interesting to investigate how this "noisy" observation of gradient information influences our generalization bounds. Second, is worth exploring how other optimization algorithms and different model architectures influence the generalization bounds. Finally, our bounds provide worst-case guarantees to the generalization of NNs and it would be interesting to extend our results obtain expected bounds for further sharpening the results.
10

---

Acknowledgement
We thank the anonymous reviewers for valuable suggestions to improve the paper. We also thank the San Diego Supercomputer Center and the MIT-IBM Watson AI Lab for computing resources. Y. Chen and T.-W. Weng are supported by National Science Foundation under Grant No. 2107189 and 2313105.
References
[1] Arora, S., Ge, R., Neyshabur, B., and Zhang, Y. Stronger generalization bounds for deep nets via a compression approach. arXiv preprint arXiv: 1802.0526,, 2018.
[2] Arora, S., Du, S., Hu, W., Li, Z., and Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
[3] Arora, S., Du, S. S., Hu, W., Li, Z., Salakhutdinov, R. R., and Wang, R. On exact computation with an infinitely wide neural net. Advances Neural Information Processing Systems, 32, 2019.
[4] Awasthi, P., Frank, N., and Mohri, M. On the rademacher complexity of linear hypothesis sets. arXiv preprint 2rXiv:2007.11044 2020.
[5] Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
[6] Bartlett, P. L.. Foster, D. J., and Telgarsky, M. J. Opectraaly-normalizza margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
[7] Bartlett, 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):2285-233 2019.
[8] Bassily, R., Feldman, V., Guzmán, C., and Talwar, K. Stability stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381-4391, 2020.
[9] Belkin, M., Hsu, D., Ma, S., and Mandal, S. Reconciling modern machine-learning practice and the classical barince trade-off. Proceedings of the National Academy of Sciences, 1 116632):1849--1554 2019.
[10] Boucheron, S., Lugosi, G., and Massart, P. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
[11] 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.
[12] Chen, R. T. Q. torchdiffeq. 2018. URL http::ttp////tt htw.at/pp//gggth....c////cc/c/ep
[13] Chen, W., Gong, X., and Wang, Neural architecture search on imagenet four gpu hours: A theoretically inspired perspective. arXiv preprint arXiv:2102.1153:: 2021.
[14] Chen, Y., Huang, W., Nguyen, L., and Weng, T.-W. On the equivalence between neural network and support vector machine. Advances in Neural Information Processing Systems, 34, 2021.
[15] 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.
[16] Cristianini, N., Shawe-Taylod J., et al. An introduction to support vector machines and other kernel-based learning methods. Cambridge university press, 2000.
[17] Domingos, P. Every model learned by gradient descent approximately a kernel machine. arXiv preprint arXiv:2012.00152. 2020.

---

[18] Dong, X. and Yang. Y. Searching for robust neural architecture in four gpu hours. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 1761-1770, 2019.
[19] Dong, X. and Yang, Y. Nas-bench-201: Extending the scope of reproducible neural architecture search. arXiv preprint arXiv:2001.0033 2020.
[20] Du, S., Lee, J., Li, H.. Wang, L., and Zhai, X. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pp. 1675-1685, PMLR, 2019.
[21] Du, S. S., Zhai, X., Poezos, B., and Singh, A. Gradient descent provably optimizes parameterized neural networks. arXiv preprint
2018.
[22] 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: 1703:/ 1008, 2017.
[23] Grant, C. P. Theory of ordinary differential equations. Brigham Young University, 2014.
[24] Gunasekar, S., Lee, J. D., Soudry, D., and Srebro, N. Implicit bias of gradient descent on linear convolutional networks. Advances in Neural Information Processing Systems, 31, 2018.
[25] Hardt, M., Recht, B., and Singer, Y. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning. pp. 1225-1234. PMLR, 2016.
[26] He, K., Zhang, X., Ren, S., and Sun, Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
[27] Huang, W., Liu, C., Chen, Y., Da Xu, R. Y., Zhang, M., and Weng, T.-W. Analyzing deep pac-bayesion learning with neural tangent kernel: Convergence, analytic generalization bound, and efficient hyperparameter selection. Transactions on Machine Learning Research, 2023.
[28] Jacot, A., Gabriel, F., and Hongler, C. Neural tangent kernel: Convergence and generalization neural networks. Advances neural information processing systems, 31, 2018.
[29] 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 preprint arXiv:1609.04833 04836, 2016.
[30] Krizhevsky, A., Hinton, G., et al. Learning multiple layers of features from tiny images. 2009.
[31] LeCun, Y., Bottou. L., Bengio. Y.. and Haffner, P. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 22244, 1998.
[32] Lee, J., Xiao, L., Schoenholz. S., Bahri, Y., Novak, R., Wide neural networks of any depth evolve linear models under gradient descent. Advances in neural information processing systems, 32, 2019.
J., and Pennington. J.
[33] Li, L. and Talwalkar, A. Random search and reproducibility for neural architecture search. In Uncertainty in artificial intelligence, pp. 367-377. PMLR, 2020.
[34] Liu, H., Simonyan, K., and Yang, Y. Darts: Differentiable architecture search. arXiv preprint arXiv:1806.0 100.000000000055 2018.
[35] Maurer, A. A note on the pac bayesian theorem. arXiv preprint cs/0411099, 2004.
[36] McDiarmid, C. et al. On the method of bounded differences. Surveys in combinatorics, 141(1): 148-188, 1989.
[37] Mellor, J., Turner, J., Storkey, A., and Crowley, F. J. Neural architecture search without training.
In International Conference on Machine Learning, pp. 7588-7598. PMLR, 2021.
12

---

[38] Mohri, M., Rostamizadeh, A., and Talwalkar, A. Foundations of machine learning. MIT press, 2018.
[39] 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 on Computer Vision and Pattern Recognition, pp. 11861-11870, 2022.
[40] 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: 1412.6614, 2014.
[41] Neyshabur, B., Tomioka, R., and Srebro, N. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLR, 2015.
[42] Neyshabur, B., Bhojanapalli,, S., McAllester, D., and Srebro, Exploring generalization in deep learning. Advances in neural information processing systems, 30, 2017.
[43] Neyshabur, B., Bhojanapalli, S., and Srebro, N. A pac-bayesian approach spectrally- normalized margin bounds for neural networks. arXiv preprint arXiv:/707.095660 2017.
[44] Neyshabur, B., Li, Z., Bhojanapalli, S., LeCun, Y., and Srebro, N. The role of over- parametrization in generalization of neural networks. In International Conference on Learning Representations, 2019. URL https: https: http:p/////peeeeeeeeeeeeeeeee www.:ewwweeeeforeeeeeeee id=ByggghAcYA.
[45] Novak, R., Xiao, L., Hron, J., Lee, J., Alemi, A. A., Sohl-Dickstein, J., and Schoenholz, S. S. Neural tangents: Fast and easy infinite neural networks python. In International Conference Learning Representations, 2020. URL https: htt///gttttu//////////// com/ cow/goog/ e/ wereeurlltanggeee
[46] 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- sesh-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[47] Pham, H., Guan, M., Zoph, B., Le, Q. and Dean, J. Efficient neural architecture search via parameters sharing. In International conference machine learning, pp. 4095-4104. PMLR, 2018.
[48] Russo, D. and Zou, J. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pp. 1232-1240. PMLR, 2016.
[49] Santambrogio. F. (Euclidean, metric, and Wasserstein] gradient flows: an overview. Bulletin of Mathematical Sciences, 7:87-154, 2017.
[50] 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. -667-2690. PMLR, 2019.
[51] Schölkopf, B., Smola, A. J., Bach, F., et al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
[52] Shalev-Shwartz, S. and Ben-David, S. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[53] Shawe-Taylor, J., Cristianini, N., et al. Kernel methods for pattern analysis. Cambridge university press, 2004.
[54] Soudry, D., Hoffer, F.,, Nacson, S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):282222878, 2018
[55] Valle-Pérez, G. and Louis, A. A. Generalization bounds for deep learning. arXiv preprint arXiv:20/2.041155 2020.
[56] Vapnik, V. and Chervonenkis, events to their probabilities. Theory of Probability and its Applications, 16(2):264, 1971.
the uniform convergence of relative frequencies of
13

---

[57] Weng, T.W.., Zhang, H., Chen, P.-Y.. Yi, J.. Su, D., Gao, Y., Hsieh, C.-J., and Daniel, L. Evalu- ating the robustness of neural networks: An extreme value theory approach. In International Conference on Learning Representations, 2018. URL https::/openrevieeeee www.//rruee/rrtr id=BkUH1MZOb.
[58] Xu, A. and Raginsky, M. Information-theoreti analysis generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 30, 2017.
[59] Zhang. C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
14

---

Appendices
A
Additional Experiments
Logistic for training samples
Difference of logistic loss
0.8
NN GF
0.0015
NN GF KM
0.7
0.6
0.0010
0.5
0.4
0.0005
0.3
0.2
0.0000
0.1
-0.0005
0.0
0
200
400
600
800
1000
200
400
600
800
1000
Logistic and bound
(d) Rademacher complexity bound
1.4
Generalization gap
1.2
0.5
20.20.5'
U1.50 S'
0.4
U2. 20 S'
0.8
NN test loss
U5. 5
0.6
Bound with U. 100
U,.
0.2
0.4
0.2
0.0
0 200
400
600 800
1000
200 400
600
800
1000
Figure A.4: Experiment (I). (a) shows the dynamics of logistic loss for 5 randomly selected training samples for NN trained by gradient flow (NN GF), NN trained by gradient descent (NN GD), and the equivalent general kernel machine (KM) in Theorem The dynamics of NN GF and KM overlap and verify the equivalence Theorem 2. The dynamics of NN GF and NN GD are consistently close throughout the training process. (b) shows the differences between NN GF and KM which verifies our equivalence in Theorem 2. The differences between NN GD and KMM are also estimated. error, and population loss bounds
small. (c) shows NN GF's training loss, test loss,
Bound with UU/U2 is the bound for (w) by applying U1/U₂ in Corollary 1. (d) shows U1 and U2 in Theorem 3 first increase then converge after sufficient training time. The numerical experiments demonstrate that our complexity bound is tight and can capture the generalization gap well. As the number of S' increases, our bound converges the true supremum value.
Experiments are implemented with PyTorch [46] on 24G A5000 and 32G V100 GPUs.
A.1 Computation Cost of Experiments
In Experiment (I), estimating the bound with 20 S' (solving 20 gradient flow ODE) costs 500s and training NN costs 0.29s. The GPU memory required by estimating the bound 2406MB and training NN requires 1044MB.
GPU hours
CIFAR-10
CIFAR-100
RS Gene(w, S) (Ours) Training one NN architecture to convergence
0.036
0.037
1.83
2.56
Table 3: Averaged computational cost (GPU hours) for one architecture in Experiment (III).
For Experiment (III), we report the averaged computational cost (GPU hours) of our approach for architecture and the computational cost of training one NN architecture convergence in
15

---

(a) Logistic loss for training samples
(b) Difference of logistic loss
0.8
0.00125
NN GD KM
0.7
0.00075
0.5
0.00050
0.4
0.00025
0.3
0,00000
NN GD
-0.90025
500
1000
1500
2000
2500
3000
500
1000
1500
2000
2500
3000
(c) Logistic loss and bound
(d) Rademacher complexity bound
Generalization cap
0.175
0.65
0.150
0.125
train loss
KM train loss
0.100
0.55
NN test
test error
0,075
0.50
0.45
0.025
1500
2000
3000
500
1000
2000
2500
3000
Figure A.5: Experiment (I) on CIFAR-10. Generalization bound for three-layer NN (3072- 100- 100-1) trained on binary CIFAR-10 10 (cat and dog). The experiment demonstrates that our complexity bound is tight and can capture the generalization gap well.
Table 3. Note our approach calculates Gene(w, w. S) only after training for 1 or 2 epochs, which saves computational cost lot.
A.2 Comparison with Existing Generalization Bounds
To make a stronger comparison with existing work, have conducted additional experiments below to show that our bound is much tighter than prior work on both finite-width NNs and infinite- width NNs.
(1) For the finite-width NN, we compare with previous uniform convergence bounds (VC dimension [7] and norm-based bounds [6]) as the NTK-based bounds [2, 11] are limited to infinite ultra-wide NNs. Note our bounds are also uniform convergence bounds. We follow the same setting in our Experiment I, and calculate the bound for two-layer NN with 100 hidden nodes (finite-widd training time T=1000 and sample size n=1000. Here L is the number of layers, p is the number of parameters, W is the weight matrix for the i-th layer, and m is the largest width of NN including the input dimension. Constants in big O are ignored in the calculation. The results in Table 4 show that bound much tighter than previous VC dimensions and norm-based bounds.
Finally, we remark that existing works have observed that VC dimension and norm-bor based bounds are mostly vacuous (see e.g., Figure 5 of [44] and Figure 4 in [1]) while our bound is non-vacuous as shown above and in Figure and Figure A.5.
(2) For the infinite-widhe NN we compare with the NTK- bound in Cao & Gu [11] in a similar setting as Experiment two-layer NN and binary MNIST (1 vs. 7) with 1000. Note that their bound only holds for an ultra-wide NN. We compute the infinite-wide NTK using Neural Tangents [45] and calculate their bound accordingly. For our bound, we train a two-layer NN with 1000 hidden nodes (to approximate an ultra-wide NN) and compute our bound at T = 1000 (almost convergence). Constants in big O are ignored the caleulation. The results Table show that our bound much tighter than previous ATK-based bounds.
16

---

Table Comparison with existing uniform convergence bounds (VC dimension [7] and norm-based bounds [6]). "Finite sample estimate": Bound estimated from 100 S". "Extreme value estimate": Bound estimated from extreme value theory. See more detail in Appendix A.3.
Method
Bound
Value
Tighter over [6]
VC dimension [7]
0
(plon(o)
55957.3
V/a
|
12:0
3/2
Norm-based bound [6]
I Vn
W
E
In(m)
140.7
Ours
Finite sample estimate
Rg (Gr) R (GT)
0.03
4690
Extreme value estimate
0.06
2345
Table 5: Comparison with NTK-based bounds [11].
Method
Bound
Value
Tighter over [11]
Cao & Gu [11]
Ö(L
1.44
Ours
Finite sample estimate
Rig (GT) R.d (9r)
0.026
55.38x
Extreme value estimate
0.08
18.00x
A.3 Estimate Supremum with Extreme Value Theory
In the all above experiments, estimate the supremum in the Rademacher bound in Theorem 3 with the maximum over finite set. To get the true supremum value of the bound. we apply the extreme value theory to estimate it, similar estimating the local Lipschitz of NN in [57]. We show the finite maximum is close to the true supremum value, validating using a finite maximum as an estimate for our bound. We first state the following result from extreme value theory and then explain how we can apply it to estimate our bounds.
Theorem 6 Kisser--Tipeett Tippett-Gnedenke Gnedenko theorem). Let 1, X2,... "e...."", Xm be a sequence of independent and ceentcclly-distribute random variables with cumulative distribution function F. Suppose that there exist two sequences of real numbers O. > 0 and bm E IR such that the following limits converge non-degenerate distribution function:
max (X1, X2, Xm3
Tim
TP(
S Sx) G(x).
bm
Then the limit distribution G belongs to either the Gumbel class (Type 1), the Fréchet class (Type II), or the Reverse Weibull class (Type III):
Gumbel class (Type I): G(x) exp { -exp
exp
aw
}
x R.
bw
0.
aws
Fréchet class (Type II):
G(x))
Ow
exp
by
T. 2 awey
Ca
Reverse Weibull class (Type III):
G(w)
exp
b
awey
1,
V. 2 awo
where aw E R. by. > 0 and cu. > 0 are the location, scale, and shape parameters, respectively.
Our bounds are finite as long as É(w, 2) is LipLihhciizz (will explain in detail later). Thus we are particularly interested in the reverse Weibull class, as its CDF has a finite right end-point (denoted as aw.. The right end-point reveals the upper limit of the distribution, known as the extreme value. In case, the extreme value is exactly the supermum want to estimate.
17

---

To compute U2 we compute an upper bound of it by setting as the largest L distance between any two g(Z) O7 and N99. e, (lll,)
1 because this case any ((Z) E g will satisfy as an e cover.
2 In N c, 111,)
! T1
U2
inf e>0
+
sup
11 (Z) 92 92(2))l
n
n
91. g1.
Denote the right hand side as U2. Since each K(2,, 2,: S LTT U2 S 2L
Note Z is fixed. Then for all 91, 92 E Gr, 11 (Z) - @z(Z)l are i.idd random variables, because
g E Gr are trained from i.i.d. S'. Consider a finite set ON C Gr with size Ng = |9x,1- As Ng oc,
02
(Z)) (2( & UN, N₂ 700
Then can apply extreme value theory to estimate Ug. We generate No batch of GN., compute their Ü2 and store them in a set. Then with these U, s, we perform a maximum likelihood estimation of reverse Weibull distribution parameters, and the location estimate Ou is used as estimate of the U2- To validate that reverse Weibull distribution a good fit for the empirical distribution of the 0 "s's, we conduct Solmogorov-Sminot goodness-of of-fit fit test (a.k.a. K-S test) to calculate the K-S test statistics D and corresponding p-values. The null hypothesis is that U2' 's follow reverse Weibull distribution.
We follow the same setting Experiment I and want to estimate U2 T 1000. Figure A.6 shows a result of estimating U/ with Nú, = 50 and N₂ = 1000. The estimated Už = 0.06 is quite close to the finite maximum, validating using finite maximum an estimate for our bound.
(Bh.. Da. Cn)m((.06,, 0.02, 6.23), pval 0.88, ks 0.08
fitted pdf
100
60
0.030
0.035
0.040
0.045
0.050
02
Figure A.6: Estimating U2 with N, = 50 finite maximum over sets of size N₂, 1000. The red line the fitted probability distribution function (PDF) of the reverse Weibull distribution. The small D D-statistics of K-S test (ks) and large p-values (pval) show the hypothesized reverse Weibull distribution fits the empirical distribution of U2 well. The estimated Už 0.06 is quite close the finite maximum, validating using a finite maximum as an estimate for our bound.
For U1.
B n
U1
sup ((xr
Tr(K(2, + Σ A(Z,, 2,)
where
1
A 23) = 2
sup
K(z,, K(Z),zz;'))
inf K(z,, Zf:)));)))) Kekr
K((.:S))rr
Tr(K Z: S')) and K(zi, 2j; 2;; S') for j E (n] are random variables that only depends on S'. For different S' S" E o) Tr(K S')) and (r( Z; 8")) are i...d. random variables. Similarly for S") i, E [x]. We assume the finite maximum of each random variable follows reverse Weibull distribution and estimate their supremum then sum them together to get
18

---

(9h. Ae: 6x1=(1166670, 1190.22, 20.24), pvvl 0.72, Ks 0.10
(Ph, Dco No..9k2::-1111,, 9,04, 5.22), pvel 0.97, ks 0.07
Sitel pd)
fitted pif
0.005
0.002
0.000
(a) Estimating S")KK Tr(K(Z, 8)). (h) Estimating (') K(z1, 2²)
Figure A.7: Estimating the components in U1 with No = 50 finite maximum over sets of size Ng 1000. The estimated extreme values are close the finite maximum, validating using finite maximum as an estimate for our bound.
22; U1- Figure A.7 shows estimating s Tr(K(Z, Z:S") and "S) K2 S*). The estimated extreme values are close the finite maximum, validating using a finite maximum as an estimate for our bound. Due to the computational cost of estimating n² extreme values, we leave estimating U₁ as future work.
19

---

B Integrability of Loss Tangent Kernel
By the assumption that the loss continuously differentiable, the loss gradient Vwl((n((), 2) is continuous w.r.t. wr()). Together with w(t) is continuous w.r.t. V (w((w()), 2) is continuous w.r.t After the inner product, the LTK K( ((w(tt;; 2, x') is still continuous w.r.t t. By the continuity of LTK on the compact set [0, 71, LTK is bounded and Riemann integrable on [0, T'. Therefore, the integral in LPK is well-defined.
For the full-batch gradient flow (1) we considered in this paper, w(t) is differentiable therefore continuous w.r.t. by the gradient flow equation. Hence, the integral LPK well-defined.
For stochastic gradient flow, the continuity of the path w(() can be argued as follows. For each time interval [1, + 1], we assume that the same batch of data is used. Within this time interval, w(() is continuous w.r.t. L. For the next time interval [t + 1, + 2). even if a different data batch is used, the gradient flow ODE initializes the w(t + 1) with the solution from the end point of the previous interval, [t, f + 1]. This ensures the continuity of wt) across distinct time intervals. In short, the continuity of (t) within each time interval, combined with the initialization of the ODE, will ensure the continuity of (t) in the entire time interval [0, T
C Complete Proofs for Gradient Flow
C.1 Proof of Theorem
Theorem 2. Suppose wT) = Wy is a solution of (1) at time T with initialization w(O) = Wi- Then for any Z,
1 Kr(Z, 2) + E(wa: 2),
E(WT, 2)
where Kr is defined Definition 4.
Proof. Consider the gradient flow:
dw:
Vw [s(()))))) = n Σ Vi Coll zi).
(6)
dt
For any differentiable loss function E(w, 2). by chain rule,
de(w,; = -vVul(we 2),
dwy,
(7)
dt
dt
Plug in the gradient flow expression of dt
in (6) into (7). We have
dl(w,: x)
(V w Wwlwwr z), - -wwLs(w:))
dl
n n
Euri z),
Wwl(we 2:)
(by definition of Ls(w:))
V w lww, 2), Vio (wws 2:))
(by the linearity of inner product)
K(w;; z, 2:).
(by Definition 3 of the LTK)
20

---

Integrate both sides from 0 to T over the path w(t) taken by the parameters during the gradient flow,
/
T
((WT, 2) - E(w0, 2)
K(w, 2, z,)dt
n
n
K(wn 2, z.)dl
(By linearity of integration)
71
(z, 2):
(By Definition 4 of LPK)
i=1
Thus have
((WT, 2) =
Σ
1 Kr (2, 2;; + E(wo, z).
Below, prove that (r(22='; = 2 I is valid kernel. We show (r S): is valid kernel by proving (2, S² is continuous and the kernel matrix K7 Z) E RR*x is positive semi-definite (PSD) for any finite subset of Z, 21. Fn Z [53]. By Definition of the loss path kernel,
())2,2':8)= = L' K(wiizz2) z')
= =/" (V 2), Vwl(w,,,2) dt.
Since E(w,, 2) is continuously differentiable for w, and z, V 2) is continuous for z, After the inner product and integration, it is still continuous function. Thus (z,,,''; 2); is continuous function for z.
Denote lx(2) V Vol(Wee 2). then by Definition 4 of the loss path kemel,
Kr 21))) /- K(we; 2, 2'
(Vwl(ws, z), V Vwl(wr,22) dt
// (B.(z), (x())) dt.
For Vu TR. and V {2,) C 2,
u KT,r(Z,, Z;Suu
Wa Kr Kri S)
i=1 ==
n
Uilli /' (Ib((zs), x((2,)) dt
Σ>
n
Uruy (2)( (z(2,)) dt
1=
Uc th (z)),
Σ (u)D((z))) dt
==1
Σ u. (
dt
2 0.
Thus the matrix (2, S) is PSD and Ky (z, z'; S) is therefore a valid kernel.
21

---

C.2 Proof of Theorem 3
Theorem 3. Rs(Gr) I min(U1,,s) Here
U1
sup K(.,:SSEET
+ (((K(Z,2,'))
A (zi, zj}, Σ bFj
a V
2 2 - +
U2 = inf
e>0
where g = [Z( = g(z))) 9 N IIII;) is the covering number of g
with the E -oorm and
1
sup K(r
K(zi, Zy: k(rr
inf
K(zi, K(Zi;
C.2.1
Proof of U1
Proof. Recall the definition of Gr.
GT = (9(2)= = Σ
1 K(z, 24:)) + + K(),,8") E Kr).
1=1
where
=== = (Kr(,;))) : supp(u 8n) 1
(r(()))))8)) B²}.
n 25
Suppose K(z,z':8') (2)) (z)))) Define
g = {g(2) = (G, s (z)) + l(wo, 2) ||8|| s B,K(, E KrT.
We first show GT C G For Vg(z) E Gr.
1
g(2)
K(z, S') + E(w0, x)
n
1
(2)) 4s (x/)) + ((wo, (by definition K(z,z';S') (z), 2s (s) (z')))
n
()((2) Σ
-
1
(2,)) + (((w..)) 2)
i=1
(1s (s:) E(wo,, 2)
(denote Bs = E - (z)))
(Bs:, &s (2)) E(wo, 2)
We know by definition of GT, ||Bs _| = Eng (z/1,25;0) S B². Thus g(z) E g4. Since Vg(z) Gr, 9(x) G Gr S gV But g is strietly larger than Gr because Bg is fixed vector for fixed K(.,;; S') while B in o is vector of any direction.
22

---

Then by the property of Rademacher complexity,
Rs(Gr) & Rs(
E sup
aig(2i)
T1
LEEGT
1=1
E
sup K(-r:1S))KT
oi (13, (z:)) + f(w00 zi))
= E
sup K(-r;S")EK,
Σ
oi (3, 2 (z:(2:))
1
E
sup
Σ
o, c,l(wo: zi)
K(---i)EK
i=1
i=1
E K(.::S)JER
B.
0 (zi)
1=1
E
sup K(--S'EE
Σ i=1
0, 2 (zi)
B
ΣΣ j=
sup K(.,:S)ERr
E
sup
o, (2;;());;;8))
i=1 1=1
Σ ,o,,K(zz 1
B
E
sup Sll:s''EKK
(Jensen's 's inequality)
s=1
Σ K(z,, 2.) + E0io,K(z..2333)) )1)
+
E
sup K(yrS")eKr
igj
K(z,,K(z 1) K(oy:SnEKT (
E
sup Sety:
K(z,, +
sup
Σ
1=1
Σ [oz0,K(21223;8)))) 1)
sup K(rr:S)eKr
Tr(K(Z, Zz +E
sup K(--SS)KK
ifj
The second term in the square root is
23

---

Σ
K
sup
K(rr 1#1
E
Σ
sup K(-HS)ERR
0,o, (
173
Σ B
sup K(.:S))Er
2(1,
-K(Z), (1)21)):88) 1)
Σ
P Plooo +1)
sup K(cySS)E
((Z1,
+P +P =-1)
sup Kl,,sheKT
itj
sup K(r:8")EK
K(z;;
inf KErr
K(Z1,2):3))
2
Σ サ
2z)
where we define Azz;,2)) [SuPK(,:STEER K(z,, Z5;8") inf ((. K(zi, K(z1, Thus in total.
B sup
(Rs()))
S n KhrrS)EKT
Tr((ZZ 2;8') + Σ AZzi 23)
{
C.2.2 Proof of U2
Proof. To simplify the notation, denote (s.(..)) En -s 2t{ l(wo, 2) for fixed Ks which is singleton hypothesis class. Then GT is union set of such function classes with different kernels,
Kr) Denote 9Kg (z)
{ 9kpz (z)=
Σ (z. 2/) + E(wu, 2) Ks E ko) U KsreKT
Gr
toKar (2)
n
Then we can rewrite g {9KSs (Z) (gKg) (21)......9. (2n)) Ks E Krr). Suppose Gj S 9 minimal 6-cover of g with ||||, Denote zkg (Z) (ūKgr (z1),..., .......,,,e, IKg. (zn)) E 9j as the
closest element to gkg. (Z) E G and 0Kgr (2) En Ks (2, 2/) + l(woo 2) = g (=) with Kg. Kr. Denote the set of all Ks KG.. Since one Tkgr corresponds to one Ks. |K; 9 = N IIll))
Based on the above, we can write the Rademacher complexity Gr as
1
n aigKer (zi) 2m1
Rs(Gr)
E n a
sup KstEkr
For any À > 0, by Jensen's inequality,
(Rx(Gr)
supkgreky Eis osokgr
<
A Eis (ai))
sup Kg EKr
(8)
24

---

Utilizing the definition of e-covering, the quantity on the exponent in Eq. (8) is
g st (zi)
π
Ti (gKsr (2i) - -sKs (zi) Tiks (zi))
n
1
OikKs gr (2,) +
0 (9K (z,) - (zi))
i=1
gr (z:) + Σ
19Ks (zi) - -iksi (zi)
11
i=1
gi9K (2:) + n
Iokg (Z) - IKor (2) 1|
n
1
JiKKgr
(zi)
(by the definition of the c-covering)
n
Substitute this inequality into Eq. (8). We have
(
Al 2 on (x.)+a]
S
sup Ks
A Ei= 0.98 0. (21)
sup Kg
(ūKs/ (zi) 9K (zi))
(
Ei= 0 (2i)
e
E
max Kk
Σ
0.5k g (21)
< n
E
(9)
where (i) because we only use the IKg instead of gk which corresponds Ks E KG instead of Ks Kr, so equivalent to take the maximum over Ks E K2 Denote E(o1,..., on) Ee= RigKg (z.). Note 9kg (z:) E [0, 1] for i [n]. Then for all i [n].
sup (( ". " " ,n)) E(aI,' ",, ",,""" ,n)l
2
sup 2
0.gK g (zi)
n
Thus E(. σ.)) satisfies the bounded difference property. Let n² sub-Gaussian variable and satisfies
By [36, 10], & is
< Σn=
of ARTE]
e 3m ARIE!
Since 9Kg is singleton function, Egg] = 1 E.
En 0:9K (zi)
0. Thus
E [(e20] S 2
Take this into Eq. (9), in total, we have
(Rr Se
Σ
t + |C
Rg
25

---

Take the logarithm on both sides of the equation.
(RT S de + +
X²
In |
2n
Divide À on both sides,
A
Rg( s
+
in |KT
2n
By taking À = 22 In Kr we get
Rg((T) < 6 + V
2l [Kp]
Take the infimum and note |K2
94
NN9 e, |III))
We get
2 N I1l
Rs( < inf
c
e>0
7
n
C.3 lower bound of (g(
Here we give lower bound of R. (9)).. Similar lower bounds for linear model were proved in [4, 6] without the supremum. Our lower bound match the trace term in the upper bound U1, which shows the upper bound U1 relatively tight.
Theorem 7.
Rs(GH)) 2 sup (T((Ks:ZZ,2) Z)).
22n kKrr
Proof. Recall
cf [g(x)) (B8, 2s (z)) + l(wo, z) 111]]| S Ks Kr).
26

---

The Rademacher complexity of G% is
R5( =
E
sup 9E 1=1
oig(zi)
E
sup
sup
Ti (x)))) + (uwo, (:))
||3|| i=1
E
sup
sup
B,
c: 0 (zi))
+ B
Σ
fll zi}
Kg EKiT ||
i=
E
sup
sup |
B,
Σ
0. (zi)) (zi)
Kg EKr
1=1
B
E
sup Kgr
0 (2,)
(dual norm property)
B
sup
E
0 2 S (2i)
KK
B
sup Kgr
E
o s (zi)
(norm sub-additivity)
2)
B
sup krr
Σ
S (2i)li]
(by the definition of 2-norm)
JEN_
1/
2
B
sup
Σ
V2
1
Σ
1
(2:))
-aintchine-Kahane inequality)
KgrEKr
JEN
i=
sup V2n Eki
o S (zi)3
JENI
sup V2n kg
s (2:)13
(rearrange the summations)
1= JEN+
Σ |1 ( (2:))1
sup V2n Kg
B sup V2n Kk
Ks zi)
Tr(Ks Z)).
sup V2n KK
C.4 Proof of Corollary
Corollary 1. Fix B > Let (eg(((()))
(Gr) = min (U1, U2) where U1 and U2 are defined in Theorem For any 8 (0,1), with probability at least 1 - 8 over the draw of an i.i.d. sample set S {2, ). S) < B², the following holds for ((wr, 2) that trained from S.
if 1 Eng
log(2/8)
LA(A(SS) Ls(Ar(8)) < 2R (GT) + +31
2n
27

---

where wT = (S) is the output from the gradient flow (1) at time T by using S as input.
Proof. Apply Theorem I to Gr and S, for all E Gr
1 Σ g(zi) - 2Rs(9r) + 3/
log(2/0)
E [z(2)]
2n
Since g(z) E Gr corresponds to ((4)(8"), 2) all S' E supp(u that # Ex, Kr (r(2), 2/:8)) S B², it holds for all these feasible S' su that
n Σ ((AT(S)). i=1
E [l((Ar
LA((A((')) - Ls(AA((S))
(by definition of (s(w) and (w))
1108(2/8)
22Rs(9r) + +3/
2n
From Theorem 3, we have Rs(Gr) I min U2). Define Rgg (Gr) = min (U1, U2) and take into above inequality,
log(2/6)
(=(Ar(S)) Ls < (Rr(gr) + +3V
2n
(oo((/0))
S 2R (9T) + +3
2n
Since above holds for all S' E Su that 1 Eig Kr 24: S B², and S is also in Sump(u@M), then if 1 n Ens (z(z,, 2j: S B2, we have
n²
log(2/8)
La(Ar(S)) Ls(Ar (8)) < 2R (Gr) +3
2n
D Complete Proofs for Stochastic Gradient Flow
D.1 Proof of Theorem 4
Theorem 4. Suppose w(T) = wT is solution of stochastic gradient flow at time T E N with initialization w(0) wa Then for any z E Z.
E(WT, 2)
Σ
1 m
Ke,ti (2, ((wo,, 2),
1=0 iES.
where (2,41(2,,2;8) = 1.+ k(w(t); 2, dt with K defined in Definition 3.
Proof. For each time interval [t, L 1] and data batch S,, Stochastic gradient flow can be treated as full-batch gradient flow. Applying Theorem for each [t, + 1] and data batch S,, we have
((w++1, = Σ Ket+1 (2, S) + elwr, 2),
(10)
tES,
where
r+1
(2, =
R(w,; z, 2i)
28

---

For time T E N.
T
E(WT, x) - -(wo, 2) =
El (w1+1122) 2) - E(20r, x)
10
1
(2,+1(2,,2,,0
(takes in Eq. (10))
m
1=0 iES,
D.2 Proof of Theorem 5
Theorem 5. The Rademacher complexity of 9T defined (3) has an upper bound:
T-1 Bt sup K(--1))E
Rs(Gr) - Σ
11,K,,-((2,2):333 + Σ
Ar(z,, Zz)
V
1=0
inf
where (1 2z)= (upK(,;))) 23) infk(.,.s)ek, (1;;
Proof. Recall,
T-1
= = Σ Σ (z,t1 + l(wo, z): k(()'8')) E Krr.
1
t=0 IES.
where
Kr ((Ko,1.;:;5)) ; S' E supp(u mm))
Σ
(e s B₁).
m²
i.ES
For = 0, 0,,,
T 1, let
G. [g(2) = Σ
1 Kr (2, K((:;8) E Kr},
iES.
Then have
GT C Go 0 .... GT + [l(wo =)}
Since the set on the RHS involves combinations of kernels induced from distinct training set S', is strictly larger than the LHS. Apply Theorem 3 bound U2 for each Ge on S,
B. sup n
Rs( S
Tr(K,,+1(2, + Σ (((())))))
23)
(11)
K(W9S")
(
where A,(,; 2,) = supk(.. (2, -nnki Kr (Z:, (z;, S*) By the monotonicity and linear combination of Rademacher complexity [38] and take in (11),
Rs(Gr) Rs e Gn @ ....e.rr -r- ① (l(w).
T-1 Σ
Ro(G)) Rs((E(wo,, 2)1)
T-1
B,
(2,K,,112,2):55) + Σ Ae(2,, 23) inj
sup S(Er
n
t=0
29

---

E
Complete Proofs for Case Study
E.1
Generalization bounds for Infinite-width NNs
E.1.1 Proof of Eq. (4)
Proof. We bound U1 in Theorem 3 for an infinite-widtt NN. For an infinite-width NN, the NTK keeps unchanged during training:
(ww; - 0(x, Ig.
Then for loss path kernel, for any 2, 2 and any (());8')) E Kr,
/'" R(we; 2'
1
K(z,2';5') =
Vyl(ur, 2) =)T (ww:; a, sl(w:, z') dl
(12)
!'" Vyl(ure 2) ((xxxx)) I V v,l(w,, z') dt
1-' Vyl(wr, 2) V fl(w,, z') dl.
= x')
Consider a p-Lipschitz loss function, i.e. IVV We(,( 2] I e.g. p = 1 for hinge loss and logistic loss, p = 22 for cross-entropy loss with one-hot labels. Then we have
p² S v fl(w,, V fl(w,, 2') S p²-
Thus
V 2') dt s p²T. pT < / V
Then by this inequality and Eq. (12),
-p²T (O x')| & ((z, 2':5") > p
Since ( xx)) 2 0 for E [n]. K(z,, 2,; S') s PT O 2,) and Tr(K Z): s Tr(p²T. ((XX)):
A A(zi,2))
sup
((z))) inf k(,ys))ek
K(zi, 25;"")
2
K()ee
1 'T (-pp)
2 (2;;, x3))
Take these terms into U1.
Rs(ST) <
sup K(.nS')e
(r(((,Z;8'))
Σ A(zi, 2j)
(
Tr(pPT - O(), + Σ
PT (0(x,
(13)
(F)
pBVT
(0(a,,
n
30

---

E.2
Generalization bound for stable algorithms
Let S" and Si be two datasets that only differ in one data point. We make the following stability assumption for gradient decent.
Assumption (uniform stability of GD.). Assume ||A[S") - A.(Il stant O. Assume f(w, =) is Le-Lipschitz and Sm-tmo for any Z. Then (Vwe(AA()") z) (w 2)|l _ Be [|((S') - (S1)l c
for some con-
This kind of stability results of GD and SGD are proved in [8, 25]. Under these stability and smoothness assumptions, probability and further bound the complexity based on Theorem 3.
can bound the deviation of g(z,) from its expectation with high
Theorem 8. For any ó E (0,1), let 9 C Gr be a 1 - subset of Gr, i.e. | (1 - 6) |9rl- Under Assumption 1, we have at least one of such Gg.
2 log( 2n
Rs( S (2LAT + cLeBITT)
This bound will naturally translate into generalization bound by equipping with Theorem 1. This bound has a convergence rate of ((1/V)). It shows that the complexity of NN trained by GD has polynomial dependence Lę, Be, and training time T.
Proof. Let G.S.S {g(Z) (g(2))).... g(Zn)) holds for G
:: : E G Then similar bound as U2 in Theorem
2 2 2 ss I1lla)
Rs(
S inf e>0
+
(14)
consider the covering of G and upper bound the right hand side. Without loss of generality, suppose S' and S/ differ in the first sample. That is S' = (2/,..., 2 and S { ................................ 2 For any fixed E [n] and gk gKgr Gr.
sk (zi) - 9kss (zi)
Ksi (zi, x/1)
1 ks (zi, 21 +
Ks (si 21)
Σ 3=2
ks (zi: 2/)
f=2
The first two terms are
1
1 - (Z,, 21))
= Ks (Zi, 21)
1
T
(Vwe(Ac(S)), 21), V=l(A((()),))) 1 1/" (V=((A((()))))) 21), (w(((()) E))
n
Jo
1
(V Vo.( 21)) 2.),
n
Jo
1 T
( IV +111 +V ((A(())) ())
11
Jo
1
<
T L7.dt
n
1
2L2T
31

---

The last two terms are
a
(2,, 2ÿ)
Σ
Kst (2,; (z))
n
jm2 n
1
Ks (Zi, 2/} - Ks (2,1 2/)
n
2=
z:), (.dd4)))))) - (V Vor((())) 21)) di
J=2
1
T
(Vul(A((")) V.)
(V))(A(()))) ( (..((())))))
1 (Vol(A v=) (V)((()))()))) voddA)()) =f))
+ ()) - 21), (.. 23)) dt (V).(A 21))
1 -
L' 2))
n
(V x.) vo)((A())) 21), (. dt
(w 21]| Voo 2/) (A, +3)1
+ II (A) 2.)
1
LeBt at + Iedl
(by Assumption 1)
n
1=
(1-
(1
!
cLa B T2
In total,
9kst (zi) -Kgr (Zi)
< 1 2LT + (1- CLeBi
T
11
n
2L² + (1- cI1
< n
(2L 2L
Similarly (zi) g; (z)) < (2I2T + cL)..T2). Thus 9Kgr (2:) 9k3; (zi)
S
1 (2L2T + CLe Then by McDiarmid's inequality, for any d E (0, 1), with probability at least 1 - 6,
log(
gKg (z.) - E [oKor (2:) S (2I2T + cl
V
2n
Then, by union bound, with probability at least 1 8, for all i E [m].
log 2z
gKgr (z:) - E [oks (z:)] < (2L2T + cL
2n
This means that with probability at least for all E [n].
log( 2z
log( 2n) 2n
IKg (z,)
E _ LoKa (zi) - (21TT + cLEB(T")
[9Kg (21) + (213T + cLeBETT)
2n
32

---

Use the gk in this range to construct the Gj. Then for any 91 (Z). E 97
91 (Z)
(2(
Σ 91 (zi) 92(2i))
log( 2n
- Σ 2 (2L cLe3(T2)
8
2n
(2L + cLeB3TT2) v 2 log(
2n
8
Take c as this value, then N IIll)) = 1. Take this into Eq. (14),
Rs(
inf
6 + V
c>0
n
2 logg( 2g)
s (2L +CLB3(T2)
72
E.3 Norm-constrained neural network
For simplicity, we consider the one-dimensional output in this subsection, i.e. 1, and assume the loss function is p-lipschitz for the model output, [[ y) E(g', y)ll I p(g g') for every 9, ğ' E IR. Consider one-layer NNs:
F= (f(w,x) w x w R. x Rd) Proposition 2. For the function class of one-layer NN defined above,
Tr(Ks: S pºT
x 11?
sup Kk
For this one-layer NN, we do not need norm constraint. For L-layer NNs with norm constraints:
F (=(( x) W (WL-1. o (W* x))
|| s B,, e [o,
where Whth E Rddxxd_- for [L] with d, 1, do d. is the element-wise activation function and is 1-lipschitz with (0) = 0. With these norm constraints of the parameters during the training, can further bound the trace term in U2 as follows.
Theorem 9, For the function class of L-layer NN defined above,
sup (t(Ks:(,,.) < 2T krr
B B
This bound shows that this quantity has linear relation with T. With finer constraint of |[[]| during the training, for example, [ < Bur,, E [t', 1' 1), we can get tighter bound. Although similar to previous bosed bounds that have polynomial dependence with the norms of the parameters, our bound has clear dependence on training time T, which is not achievable from previous approaches. But note these bounds can be very loose since they worse-case bounds.
33

---

E.3.1
Proof of Proposition 2
Proof.
(s 1/' W) (Je((')) V de
['" (()(i()) y') dt
/ ([(())) y) (()()))))) (a) (x) di
S p² (or, a T.
Thus
Tr(Ks (r(Ks((Z,))) ()) = Σ
Kr zi) 5
p
x
2
p²T
<
1=1
1=1
1=1 1
Since this holds for any Ks KT.
(T(Ks((Z.Z)) S T²T Σ
an: ||
sup
EKT
E.3.2
Proof of Theorem
Proof. Denote
(m(x) (x) (x) Rd- h he [Z]
Of(w. x)
= (x) (x) E Rdxxd--1
h E [4]
OWh
where
(²(x) { E (m( (Wh+1)T (-+ E Rd E Rdaxds,
h = I, h [L 1},
D*(x) =
he [L 1-]
Then for any h [T.). we can compute
0 0lww x) af(w,
oWh oWh
(M)))) (g- (1'("))))))))) (1-
(inner product matrices)
Tr 16
Tr (0 (10=
= ~9
where we have for the first term.
(2), --))))))()0)))
< - (لاما h-1
W ||>|||||| ||أاا||
34

---

The second term can be bounded as
(a)) 8 (z')) S [0* [10
(x)) ( _ اهمر (- (0) | (a (Woht)) 2 (a')
(x))] || (ا) ||")( llthvill (1011
W || 1 (1)x+t (-')|
II |wipe j=h+1
Thus in total,
(al(w, oWh
0s(w, x')
(0 (2x). (x')) (b (x), ba()))
owh
h
| ||=||
II
|
j=h+1
W |
|>|||||||||
||'||
1
Since the tangent kernel (w, V fwf(w,x))) = Eh== upper bound for the tangent kernel,
(8((w.))
0f(w.x)) aw
we obtain an
Dw
L 2
(Vwf x), (wf(w, S ||>||| |=|||
W
|
Thus
//" (T I'(s(un;, x)), (Swe,,
(z)(z)²))= =
x') )) v/) (V (wve, æt), Vw I x²)) dt
$ 1 p² |||||| ||'1||
II
||
dt
J=1
4=1
$ 1/''
L
L
p² |||||| ||x1||
II
B3
dt
B
J=1
h=1
TT
|0|||
B3
Σ
B
j=1
h=1
Thus,
(Z. < p²T) Σ
|
II
B
Since this holds for any Ks E KrT
L B3
Tr(Ks S ,TT) Σ
2
Σ
sup kgrEKr
By
1=1
j=1
h=1
35


Reviews:
[{"review_id": "tFNEVqTvVE", "reviewer": "Reviewer_Zsen", "summary": "The submission provides data-and-architecture-dependent Rademacher complexity generalization bounds for neural networks. Unlike previous work, the approach takes the evolution of the neural tangent kernel under gradient flow into account. First gradient flow under an evolving kernel is expressed as learning with a general kernel machine on a kernel named Loss Path Kernel. Second, a data-dependent complexity measure of the general kernel machine is computed that is finally used to compute the generalization bound.", "questions": "See weaknesses", "limitations": "See weaknesses", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "The approach is novel as far as I know, although the literature on this topic is vast and it is hard to assess novelty. While computing the bound requires access to the true data distribution and training the network, a heuristic approximation of it from the training data and a few epochs of training is shown to correlate with performance in the experiments. Background, relevant work, and the proposed method are brilliantly presented. I did not notice any glaring issues in the math although checking the long proofs in appendix in detail is not possible given the review workload. Altogether I'm leaning towards acceptance.", "weaknesses": "The major weaknesses of this work are the limited intuition it provides, an issue with the presentation of the experiments, and possibly high computation required to estimate the bound. I will elaborate on these points below. The second and the third point are critical and I ask the authors to improve them in the revision. \n\nW1. The results abstract away the details of training into a black-box evolving NTK and, although this improves the domain of applicability of the result, the obtained result does not give any insights about the role depth, width, or other choices of architecture on generalization. If theoretical connections between these choices and the evolution of NTK are known in the literature, this paper can be improved by theoretically studying the role of different architectural choices on the loss path kernel and its complexity.\n\nW2. The main motivation for the bound is that it is not limited to infinite-width or single output neural networks. A brief subsection 6.1 right before the experiments focuses on infinite-width neural networks to avoid the dependency on training. The subsection and its placement in the paper confused me about the following experiments. It seems like the experiments afterwards consider a finite-width neural network. If this is the case, I do not understand why this subsection is placed right before them and in the same section.\n\nW3. The experiments allude to intractability of a basic procedure to estimate the bound and computational speedups from approximation. The revision should report the computation or provide measures of complexity or at least clarify in the paper that estimating the bound is not as expensive as training the network. Otherwise one could perform architecture search by trying one or a few train/validation splits.\n\nMinor comment (did not influence score): \n\ni. If the Lipschitz constant is local, it can be influenced by the data or the trajectory of optimization in ways that are not captured in the analysis. This comment did not influence the score as it applies to previous work (Arora et al) as well and I believe fixing them is outside the scope of this work.\n\nii. Practical neural networks are typically trained with relatively large learning rates and especially the early evolution of NTK under large learning rate and gradient flow are known to be very different. This limits the significance of a study on gradient flow.\n\n------------\nPost-rebuttal: Raised the score to 7 since the revision will address W2 and W3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback, thoughtful review, and for appreciating the merits of the work!\n\n---\n**Q1. No insights about the role of depth, width, or other choices of architecture on generalization.**\n\nA1. Thank you for the insightful question! Please refer to Appendix D.3, where we have derived a norm-based bound by extending our analyses. Prior work has generally observed that wider neural networks tend to have smaller weight norms [see e.g., 1]. Therefore, our norm-based bound is expected to be smaller for such NNs. Nevertheless, we acknowledge that the exact influence of depth and width on our bound remains an active area of research that requires more exploration.\n\nBesides, our bound can be used to study the influence of width and depth empirically. We have conducted an additional experiment in the rebuttal to study the influence of width on our bound. With the same setting of Experiment (I), we train and compute our bound for NNs with widths 100 and 1000 at $T=10000$ (convergence). The 1000-width NN has a smaller bound of 0.024 compared with the 100-width NN whose bound is 0.032. This shows wider NN tends to have smaller values of our bounds and better generalization ability.\n\nBeyond depth and width, our bounds offer insights into how learning algorithms impact the generalization capabilities of neural networks. For instance, the bound $U_1$ presented in Theorem 3 suggests that the generalization gap could be influenced by the local Lipschitz constant along the training trajectory. This is because the loss path kernel can be upper bounded by the local Lipschitz constant. Meanwhile, $U_2$ indicates that generalization is contingent upon the variations in loss when trained using different data.\n\nFinally, we'd like to highlight that our results are general and can be applied to delve into various specific cases. As an illustration, we explored stable algorithms in Appendix D.2 and norm-constrained NNs in Appendix D.3. These investigations shed light on the roles of the Lipschitz constant, smoothness constant, and weight norm in neural network generalization — pivotal elements in generalization theory.\n\nWe will include the above discussion in the revision, which we believe will help the readers to gain more insights on our results. Thank you for the question! \n\n[1] Neyshabur, B., Li, Z., Bhojanapalli, S., LeCun, Y., and Srebro, N. The role of over-parametrization in generalization of neural networks. In International Conference on Learning Representations, 2019. \n\n---\n**Q2. Confusion about why subsection 6.1 of infinite-width NN is placed right before subsection 6.2 of NAS**\n\nA2. Subsection 6.1 of infinite-width NN is an application of our results in theory and subsection 6.2 of NAS is an empirical application. We include subsection 6.1 to apply our bound to infinite-width NN so that we can compare it with existing generalization bounds that are tailored to infinite-width NNs. \n\nIn response to your concerns, we will move this subsection to Appendix D, where we have discussed other applications of our generalization bounds to study stable algorithms and derive norm-based generalization bounds.\n\n---\n**Q3. Computation time of estimating the bound**\n\nA3. Thanks for your suggestion! In Experiment (I), estimating the bound with 20 $S’$ (solving 20 gradient flow ODE) costs 500s and training NN costs 0.29s. The GPU memory required by estimating the bound is 2406MB and training NN requires 1044MB. \n\nFor experiment (III), we report the averaged computational cost (GPU hours) of our approach for one architecture and the computational cost of training one NN architecture to convergence in the below table. Note our approach calculates Gene$(w, S)$ only after training for 1 or 2 epochs, which saves computational cost a lot.\n\n| GPU hours                                   | CIFAR-10 | CIFAR-100 |\n|---------------------------------------------|----------|-----------|\n| RS + Gene$(w, S)_2$ (Ours)                  | 0.036    | 0.037     |\n| Training one NN architecture to convergence | 1.83     | 2.56      |\n\nWe will report the above results in the revised paper.\n\n---\n**Q4. Local Lipschitz constant can be influenced by the data or the trajectory of optimization in ways that are not captured in the analysis.**\n\nA4. We thank the reviewer for this insightful point. Indeed, the local Lipschitz constant can be influenced by the training data. To clarify, the original formulation of our bounds does not directly depend on the local Lipschitz constant. The loss tangent kernel in our bounds captures the influence of training data and the trajectory of parameters in optimization to a certain extent. Nonetheless, we do agree with the reviewer that a thorough exploration of the relationship between our bounds and the local Lipschitz constant is beyond the scope of this work. We will include a discussion in the revision.\n\n---\n**Q5. Practical neural networks are typically trained with relatively large learning rates …**\n\nA5. Please refer to Q1 in the global response, where we have clarified that our experiments are conducted under practical scenarios and showed our results can be extended to the gradient descent with a finite learning rate setting.\n\n---\nWe hope our responses have addressed all your concerns. Please let us know if you have any further questions!"}, {"review_id": "V5LYYWoCry", "reviewer": "Reviewer_kZTv", "summary": "This paper introduces a new generalization bound based on dynamic NTK, called loss path kernel in the paper. The loss path kernel is a kernel based on the integration of a loss tangent kernel (NTK with loss function) so that the generalization bound can be determined by the training dataset and training trajectory of parameters. Theoretically, the paper provides the loss path kernel generalization bound guarantee and beats their bound over previous work. On the other hand, empirically, the authors verify their theorem with numerical experiments and plug their loss path kernel into NAS and get good results. ", "questions": "- Why do we need Definition 2? It seems that the analysis did not use the general kernel machine. \n- The loss path kernel needs to calculate integration, in GD or SGD. I wonder how to calculate them in practice, e.g., NAS, by math formulation or sampling. \n- The paper only considers gradient flow. Can we extend the results to normal gradient descent with a constant learning rate?\n", "limitations": "It seems that the analysis does not hold for the ReLU network as it is not continuously differentiable. \n\n======\n\nChange score from 6 to 7 on Aug 10.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper studies a very important question of the generalization gap of general neural networks. The definition of the loss path kernel is intuitive and straightforward. From my perspective, the new generalization bound based on the loss path kernel has its value. It considers the training trajectory in the bound rather than calculating the whole function hypothesis class so that the generalization bound can be tighter.\n\n- The paper provides numerical experiments to support their theorem. The numerical simulation and implementation in NAS show that their analysis can be used in practice and their theorem is not vacuous. \n", "weaknesses": "- The empirical part of writing is not clear enough. I cannot get the message between Theorem 3 and Figure 2 (c). Also, Figure 1 looks strange. The paper does not provide a convincing explanation for the outlier. The implementation of the NAS part is missing, e.g., the search space. The best architecture was not reported. \n\n- The NAS part can be stronger. The paper only considers the random sampling of 100 architectures. However, in practice, we do not use random sampling in NAS anymore because it is not efficient. There are many dynamic sampling ways in NAS, e.g., [1]. The paper may improve its results by using these methods.  \n\n[1] Guo, Zichao, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun. \"Single path one-shot neural architecture search with uniform sampling.\" In ECCV 2020.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive feedback, thoughtful comments, and for appreciating the novelty and value of the work! \n\n---\n**Q1. The empirical part of writing is not clear enough. I cannot get the message between Theorem 3 and Figure 2 (c). Also, Figure 1 looks strange. The paper does not provide a convincing explanation for the outlier. The implementation of the NAS part is missing, e.g., the search space. The best architecture was not reported.**\n\nA1. Thank you for the questions and suggestions! Please allow us to clarify them point by point.\n\n- As shown in Corollary 1, $\\hat{\\mathcal{R}}^{gd}\\_{\\mathcal{S}}(\\mathcal{G}\\_T)$ is an upper bound of the generalization gap $L_\\mu(w_T) - L_S(w_T)$. In Figure 2 (c), we plot both $\\hat{\\mathcal{R}}^{gd}\\_{\\mathcal{S}}(\\mathcal{G}\\_T)$ and the generalization gap to demonstrate that $\\hat{\\mathcal{R}}^{gd}\\_{\\mathcal{S}}(\\mathcal{G}\\_T)$ is a tight upper bound of the generalization gap.\n\n- Cause of the outlier: $U_{sgd}$ is calculated from the loss gradients along the training trajectory. NAS-Bench-201 is a NAS benchmark that contains 15625 NN architectures. When we randomly sample 100 architectures, there is a chance that we will get some “not-so-good” architectures, which have large loss gradients during training and cause a large $U_{sgd}$.\n\n- The implementation of our NAS algorithm is detailed in lines 336-357. The search space is NAS-Bench-201 [1], as indicated in line 275 and Table 2. We follow the same setting in this line of work (TENAS, LGA) for fair comparison. We will report the best architecture searched by our algorithm in the revised paper.\n\n[1] Dong, X. and Yang, Y. Nas-bench-201: Extending the scope of reproducible neural architecture search. arXiv preprint arXiv:2001.00326, 2020.\n\n---\n**Q2. The NAS part can be stronger with dynamic sampling**\n\nA2. Thank you for pointing out the reference and for your valuable suggestion. We will incorporate it into the updated paper and will also attempt to reproduce our results using dynamic sampling. Additionally, we would like to highlight that the performance of our approach (93.79 for CIFAR-10) is already close to the “optimal” (94.37 for CIFAR-10) in Experiment (III) Table 2, where the “optimal” means the best test accuracy achievable in the NAS-Bench-201 search space.\n\n---\n**Q3. Why do we need Definition 2? It seems that the analysis did not use the general kernel machine.**\n\nA3. We include Definition 2 for ease of reference. We use it in Theorem 2 and Theorem 4 whose results are either a general kernel machine or a sum of general kernel machines.\n\n---\n**Q4. How to calculate LPK in practice, e.g., NAS, by math formulation or sampling.**\n\nA4. For small models as those in Experiments (I) and (II), we can solve the gradient flow equation (Eq. (1), line 175) to get the model parameters and calculate the LTK accordingly. Then calculating the LPK just requires solving another ODE with the calculated LTK. These ODEs can be computed with torchdiffeq package. \n\nFor large models as in NAS Experiment (III), solving the gradient flow ODE is computationally infeasible. As explained in line 276-278, we applied a trapezoidal rule to approximate the integration, where  $\\mathsf{K}\\_{t, t+1}(z, z') = \\int_t^{t+1} \\left\\langle \\nabla_{w} \\ell(w(s), z), \\nabla_{w} \\ell(w(s), z') \\right\\rangle ds$ is approximated by $\\frac{\\eta}{2}[\\left\\langle \\nabla_{w} \\ell(w_{t}, z), \\nabla_{w} \\ell(w_{t}, z') \\right\\rangle + \\left\\langle \\nabla_{w} \\ell(w_{t+1}, z), \\nabla_{w} \\ell(w_{t+1}, z') \\right\\rangle]$.\n\n---\n**Q5. Can we extend the results to normal gradient descent with a constant learning rate?**\n\nA5. This is a great question! Please refer to Q1 in the global response, where we have clarified that our experiments are conducted under practical scenarios and showed our results can be extended to the gradient descent with a finite learning rate setting.\n\n\n---\n**Q6. The analysis does not hold for the ReLU network as it is not continuously differentiable.**\n\nA6. Our assumption of continuously differentiable NN is mainly for the loss path kernel to be a valid kernel. As a valid kernel, it needs to be continuous for its input (See Proposition 1 and lines 583-589). We believe with a finer analysis, our theory could be extended to non-smooth cases such as ReLU NNs. For example, finite input space does not have the continuity requirement according to Proposition 1. Another approach is writing the LPK explicitly as an inner product of feature mappings according to the definition of the kernel to verify its validity. \n\nFinally, we would like to highlight that our theory is very general as it holds for any continuously differentiable neural networks. In contrast, many prior work's analyses are tailored to ReLU networks and have other requirements, e.g. ultra-wide models and specific loss functions [2, 3].\n\n[2] Arora, S., Du, S., Hu, W., Li, Z., and Wang, R. Fine-grained analysis of optimization and\ngeneralization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322–332. PMLR, 2019.\n\n[3] 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.\n\n---\n**Summary**\n- In Q1, we clarified some confusion about our experiments.\n- In Q2, we will incorporate dynamic sampling to further improve the NAS algorithm in the revised paper.\n- In Q3, we clarified that Definition 2 is for ease of reference.\n- In Q4, we explained how to calculate LPK in practice.\n- In Q5, we clarified that our experiments are conducted under practical scenarios and showed our results can be extended to the gradient descent with a finite learning rate setting.\n- In Q6, we explained how to extend our theory to ReLU NNs.\n\nWe hope our responses have addressed all your concerns. Please let us know if you have any further questions!"}, {"review_id": "9PW0cGQbHt", "reviewer": "Reviewer_W7Wt", "summary": "The paper proposes a new complexity measure for neural networks based on tracking the changes of the weight vector of the entire model.  The work is rooted in theory by linking the proposed measure through the Neural Tangent Kernel framework to Rademacher complexity resulting in a new, meaningfully tight bounds on generalisation.\n", "questions": "As already stated, I didn't follow all the maths, but I wanted to verify my high level understanding of the work.  It seems to me, that the fundamental principle here is that while the hypothesis space of the network is immensely complex (hence very high VC dimension), that during training there is only a small subset of hypotheses \"visited\"...and for the purpose of generalisation guarantees, what matters is the set of hypotheses \"considered\" (when training), not the set of hypotheses available.  And the proposed loss path kernel measure is a measure of the complexity of the hypothesis space \"visited\".  Is this a fair high level summary?\n\nI am completely lost at what $\\mu^{\\otimes n}$ is - is it supposed to be obvious from the context?  And it all gets so complicated by Theorem 5...that I can't really tell from the math how tight the bound is.  Or, since this will always depend on the training path, the tightness of the bound can only be assessed empirically?  \n\n", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Explanation of the success of overparametrised neural network models using statistical learning theory is still very important problem we haven't solved, and this works seems like a significant development in that space.  \n\nThe proposed complexity measure is linked theoretically to a generalisation bound.\n\nThis looks like a significant amount work, extending and generalising existing theory in the Neural Tangent Kernel framework.\n\nEmpirical results, though shown on small examples, show that the derived generalisation bound is meaningfully tight (i.e. non-vacuous).\n\nFor the most part (with some exceptions mentioned below) the paper is very well written, and guides the reader well through very complicated subject matter.", "weaknesses": "The maths are very dense...and the 32 page supplement, while admirable, is way too much to get through in the time given for this reviewing period.  I didn't get through the maths, so I couldn't verify it.  It almost feels like this should be a journal rather than a conference paper.\n\nI did get lost a little bit in the maths of the main part of the paper.  It should be possible to follow this paper at high level, taking the proofs of theorems at face value, and for the most part authors do a great job of guiding the reader....but still, there are some things (see questions below) that I found confusing.\n\nThe proposed method is computationally very expensive, and so not that easy to use in practice...but approximations and computational improvements might come in the future, and the theory (assuming the proofs (which I couldn't verify) are solid) is sound and of great interest.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the kind comments and positive feedback!\n\n---------\n**Q1. The proposed method is computationally very expensive, and so not that easy to use in practice**\n\nA1. Thank you for raising the question about the computational cost of our method. For small models, our method is not computationally expensive. In Experiment (I), estimating the bound with 20 $S’$ (solving 20 gradient flow ODE) costs 500s and training NN costs 0.29s. The GPU memory required by estimating the bound is 2406MB and training NN requires 1044MB. \n\nFor large models, the computational cost of exactly calculating the bound might be expensive but the approximation we’ve proposed for NAS (i.e., $U_{sgd}$ in Eq. (4)) is computationally efficient. In the table below, for Experiment (III), we report the averaged computational cost (GPU hours) of our approach for one architecture and the computational cost of training one NN architecture to convergence. Note our approach calculates Gene$(w, S)$ only after training for 1 or 2 epochs, leading to significant savings in computational time.\n\n| GPU hours                                   | CIFAR-10 | CIFAR-100 |\n|---------------------------------------------|----------|-----------|\n| RS + Gene$(w, S)_2$ (Ours)                  | 0.036    | 0.037     |\n| Training one NN architecture to convergence | 1.83     | 2.56      |\n\nWe will include the above results in the revised paper.\n\n\n---------\n**Q2. Verify high-level understanding. It seems to me, that the fundamental principle here is that while the hypothesis space of the network is immensely complex (hence very high VC dimension), that during training there is only a small subset of hypotheses \"visited\"...and for the purpose of generalisation guarantees, what matters is the set of hypotheses \"considered\" (when training), not the set of hypotheses available. And the proposed loss path kernel measure is a measure of the complexity of the hypothesis space \"visited\". Is this a fair high level summary?**\n\nA2. We appreciate your careful read of our paper and, yes, this summary nicely describes our work! We will include the high-level summary and intuition in the revision for clarity. Thank you again!\n\n\n---------\n**Q3. Lost at what $\\mu^{\\otimes n}$ is. Can't really tell from the math how tight the bound is. Or, since this will always depend on the training path, the tightness of the bound can only be assessed empirically?**\n\nA3. \n- $\\mu^{\\otimes n}$ is the joint probability distribution of $n$ i.i.d. samples drawn from $\\mu$.\n- The tightness of our bound can be partly seen from the lower bound of the Rademacher complexity in Appendix B.3. Our lower bound matches the trace term in the upper bound $U_1$, which shows the bound is relatively tight. We also conducted experiments to demonstrate the tightness of our bounds, a standard practice adopted in generalization theory literature [e.g., 1, 2, 3].\n\n[1] Dziugaite, Gintare Karolina, and Daniel M. Roy. \"Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.\" arXiv preprint arXiv:1703.11008 (2017).\n\n[2] Zhou, Wenda, et al. \"Non-vacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach.\" arXiv preprint arXiv:1804.05862 (2018).\n\n[3] Jiang, Yiding, et al. \"Fantastic generalization measures and where to find them.\" The International Conference on Learning Representations, 2020.\n\n---------\n**Summary**\n- In Q1, we have clarified that our method is computationally efficient for small models, and for large models, the approximation we proposed for the NAS is computationally efficient.\n- In Q2, we acknowledged the reviewer’s high-level summary of the paper.\n- In Q3, we have explained the meaning of $\\mu^{\\otimes n}$ and the tightness of our bound.\n\nWe hope our responses have addressed all your concerns. Please let us know if you have any further questions!\n"}, {"review_id": "gQz7b3dZKb", "reviewer": "Reviewer_kz2v", "summary": "Thanks to authors for their submission. Their paper tackles generalization of neural network from neural tangent perspective applicable on gradient flow. The novelty of the paper stems from the new tangent kernel $\\overline{K}(w,z,z')$ proposed. It is defined as an inner product of loss gradients w.r.t. weights and evaluated at two data points $z$ and $z'$. This leads to Loss Path Kernel defined as a path integral w.r.t. $t$ of $\\overline{K}(w(t),z,z')$. After introduction and recollection of NTK theory the definitions are laid out. The paper continues with proving the gradient flow loss is general kernel machine followed up by Rademacher complexity bound derivation. The later section 5 extends these results to SGD. Finally results are used to design neural architecture search (NAS) and demonstrate favorable performance compared with state-of-the-art NAS algorithms through numerical experiments.\n\nPaper follows an interesting idea of generalising tangent kernels to path integrals. It is timely and potentially interesting contribution. Being theoretical work, however, it lacks the clarity in presentation, rigor in definitions and theorems and this strongly undermines its validity. The amendments are recommended int he bellow.", "questions": "Q0: Figure 2c, Fig A4,d) and same for Fig. A5, d) Generalization gap is close to zero from the beginning and increasing later on (overfitting). It suggests the scale is large and thus Rademarcher upper bound is really vacuous compared to a real generalization gap (blue line), despite it improved on previous bounds as reported. Could authors rescale, redo experiments so Figure is more convincing? This is to support the strong claim of the paper mentioned on lines l43 and l55 again and l92 again” …” strong correlation (of the hereby derived upper bound) with generalization error” … and …”highly correlated” … \n\nQ1: Could authors elaborate in detail on assumptions needed for Loss Path Kernel (LPK) $K_T(z,z')$ to be defined for arbitrary $T$? Or is $T$ limited (early stopping assumed)? See section Weaknesses for details.\n\nQ2: The same as Q1 just for stochastic gradient descent versions in Section 5. Also see Weaknesses [SGD, Section 5].\n\nQ3: Condition $\\frac{1}{n^2}\\sum_{i,j} K_T(z'_i, z'_j ; S') \\leq B^2$ on the line $192$ and later similarly for SGD kernels (definition on line 242): This condition limits the datasets $S'$ LTK and LPK can be considered over. How does this limit the applicability/generality of results? \n\nQ4: $\\textbf{Gradient flow vs. Realistic NNs}$ How does the bound deteriorate when practical scenarios, e.g., finite and not infinitesimal learning rate, noise etc., are considered?", "limitations": "I find missing assumptions and not stated limitations to be the main weakness of the otherwise very interesting paper. See leading questions: Q1, Q2, Q3 and eventually Q4: $\\textbf{Gradient flow vs. Realistic NNs}$", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "+ Well introduced paper with well stated contributions in Table1 presenting paper's contributions to NTK theory.\n\n+ Paper strives for applicability and results are used to design of neural architecture search (NAS) supported by (limited) numerical experiments.", "weaknesses": "- $\\textbf{[Definition of the Loss Path Kernel]}$ For instance the line 108:The Theorem 2 \"... shows that the loss of the NN at a certain fixed time ($T$) is a general kernel machine ...\". But is the limit (when $T \\rightarrow \\infty$ and/or $dt \\rightarrow 0$) also in RKHS? Under what conditions? The existence/convergence of the integral is not commented neither in the body nor in the appendices. I would urge authors to detail this out very thoroughly as assumptions needed for a definition to work would possibly limit the applicability of the results. For instance the Lipschitz gradients may be needed, because loss may be Lipschitz locally, but its norm may be growing with $t$, e.g., in case of overfitting, and the integral (LPK) may still diverge as $T \\rightarrow \\infty$. \n\n- I try to provide alternative view: In case of the gradient flow over whole training data set considered by paper, i.e., gradient descent with infinitesimal steps, as opposed to stochastic (mini-batch) gradient descent, the weight updates are locally diffeomorphisms (locally invertible smooth maps - that is what paper implicitly assumes by infinitesimal steps). Then the kernel (LTK) $\\overline{K}(z,z')$ (Definition 3) can be seen as a pull-back inner product used for instance in [Principles of riemannian geometry in neural networks, Hauser, Michael and Ray, Asok, Advances in neural information processing systems, vol=30,2017] and the crucial Loss Path Kernel (LPK) $K_T(z,z')$ (Definition 4) is defined as a length of the parameterised curve $f \\odot w(t)$ w.r.t. this inner product $\\textbf{if it exists}$! It does not in general unless inner products along the path \"behave nicely\".\n\n- Following up on the above, assumptions required by Corollary 1 should be listed thoroughly. Line 203 reads  ...\"assuming $\\ell({w},z)$ is $L_{\\ell}^2$-Lipschitz ... \". Is it needed? If so, is it enough for Definitions to be well defined (see above).\n\n- $\\textbf{[Corollary 1 (Generalization bound for NN)]}$ the lines 203-208 are very vague, using terms \"usually, often etc.\" which degrade validity of the Corollary 1 and thus the main result of the paper. I strongly advise authors to avoid such terms. Especially in connection to the most important result of the paper. Try to clarify what is assumed, what is already existing result (please cite sources, if so) and what is hypothesis. For instance: l: 203-205: \"... $\\textbf{assuming}$ the $\\ell(w, z)$ is $L_{\\ell}$-Lipschitz. The second component is $\\textbf{often}$ not the dominant term since GD is a stable algorithm when the training data are modified slightly [24, 8]. It $\\textbf{usually}$ decreases with $n$ since GD becomes more stable when $n$ grows. ...\"\n\n- $\\textbf{[ $1/n^2\\sum_{I,j}K_T(z'_i,z'_j;S′)≤B^2$ ,see l 192]}$ This condition limits the datasets $S'$ LTK and LPK can be considered over. How does this limit the applicability/generality of results? \n\n- $\\textbf{[SGD, Section 5]}$ This section generalizes the previous results (bounds) to stochastic gradient descent. The corresponding gradient flow remains utterly deterministic, however. As opposed to previous works, where SGD is related to Langevin dynamics, [Stochastic modified equations and adaptive stochastic gradient algorithms, Li, Qianxiao, Tai, Cheng, Weinan, E, International Conference on Machine Learning, 2017], where path integrals involve higher terms due to quadratic variation induced by stochasticity. The paper neglects this. To improve the impact of the paper extended argument why deterministic flow (ODE) applies and what are assumptions needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our paper and constructive comments!\n\n---\n**Q1. Definition of loss path kernel and the existence of the integral.**\n\nA1. Indeed, this is a great question. Please allow us to address your concerns point-by-point below [this discussion will be added to the updated paper]. \n\n- [Finite training time $T$]. Throughout this paper, we restrict our attention to a finite time $T$, where $T$ is bounded by a predetermined constant. We will mention this explicitly in the revised paper. We do not consider the asymptotic behavior of the loss function as $T \\rightarrow \\infty$. This is a practical setting since the training time for NNs typically has an upper limit to control computational expenses and prevent overfitting. \n\n- [Existence of gradient flow]. The existence of gradient flow (dt -> 0) and its integrals are implicitly assumed in previous NTK papers [1, 2, 3]. The gradient flow is well-defined for a wide variety of conditions on the function. For example, Lipschitz-continuity of the gradient or semi-convexity [4].\n\n- [Continuity of loss tangent kernel (LTK)]. By the assumption that the loss is continuously differentiable in line 107, the loss gradient $\\nabla_w \\ell(w(t), z)$ is continuous w.r.t. $w(t)$. Since $w(t)$ is differentiable (therefore continuous) w.r.t. $t$ by the gradient flow equation (Eq. (1), line 175), $\\nabla_w \\ell(w(t), z)$ is continuous w.r.t. $t$. After the inner product, the LTK $\\bar{\\mathsf{K}}(w(t); z, z')$ is still continuous w.r.t. $t$.\n\n- [Integrability of loss tangent kernel]. By the continuity of LTK on the compact set $[0, T]$, LTK is bounded and Riemann integrable on $[0, T]$. Therefore, the integral in LPK exists.\n\nIn short, the existence of gradient flow and continuously differentiable loss together with finite training time $T$ are enough to guarantee the existence of LPK. \n\nAs a side note, the validity of LPK as a kernel function is proved in Appendix B.1 lines 583-592.\n\n[1] Jacot, Arthur, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 2018.\n\n[2] Du, Simon S., et al. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint arXiv:1810.02054, 2018.\n\n[3] Arora, Sanjeev, et al. On exact computation with an infinitely wide neural net. Advances in neural information processing systems, 2019.\n\n[4] Filippo Santambrogio. {Euclidean, metric, and Wasserstein} gradient flows: an overview. Bulletin of Mathematical Sciences, 2017.\n\n---\n**Q2. Line 203 reads ...\"assuming $\\ell(w, z)$ is $L^2_\\ell$-Lipschitz ... \". Is it needed?**\n\nA2. Corollary 1 does not require the Lipschitz continuity of the loss function. This assumption is mentioned not as a requirement, but to provide insight into the scale of the term present in Theorem 3.\n\nAs a side note, continuously differentiable loss implies locally Lipschitz loss. Since $w(t): [0, T] \\rightarrow \\mathbb{R}^p$ is continuous on $[0, T]$, the path \\{$w(t): t \\in [0, T] $\\} is a compact set. Then together with the loss is continuously differentiable, the loss is Lipschitz on the path $w(t)$ considered. \n\n---\n**Q3. lines 203-208 are very vague, using terms \"usually, often etc.\"**\n\nA3. Thank you for the suggestion! We will rephrase the sentence to eliminate the vague terms and make the statement more precise and rigorous. Please find the revised sentence below: \n\n``The second term calculates the variation range of the LPK in the set $\\mathcal{K}_T$. It will decrease with sample size $n$ as GD becomes more stable when $n$ grows [24, 8].’’\n\n---\n**Q4 The norm constraint limits the datasets LTK and LPK can be considered over.**\n\nA4. Please refer to Q2 in the global response.\n\n---\n**Q5. SGD remains utterly deterministic.**\n\nA5. The only assumption we have imposed is that the mini-batch indices $S_t$ are specified before the algorithm is run (see line 230–232). Under this assumption, we were able to connect the trajectory of the weights updated by SGD with a deterministic flow. It is worth noting that this assumption is commonly used in generalization theory to eliminate the randomness in the selection of mini-batches [5, 6, 7]. Our findings can be extended to the scenarios involving random mini-batch selection by first conditioning on the $S_t$ and then taking an expectation over the randomness of $S_t$. We will include the above discussion in the revised paper.\n\n[5] Neu, Gergely, et al. \"Information-theoretic generalization bounds for stochastic gradient descent.\" Conference on Learning Theory. PMLR, 2021.\n\n[6] Wang, Ziqiao, and Yongyi Mao. \"On the generalization of models trained with SGD: Information-theoretic bounds and implications.\" International Conference on Learning Representations, 2022.\n\n[7] Wang, Hao, Rui Gao, and Flavio P. Calmon. \"Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels.\" J. Mach. Learn. Res. 24 (2023): 26-1.\n\n---\n**Q6. Figure 2c, Fig A4,d) and same for Fig. A5, d) Generalization gap is close to zero from the beginning and increasing later on (overfitting)…**\n\nA6. To clarify, in Fig. 2(c), Fig. A4 (d), and Fig. A5 (d), the generalization gap and Rademacher upper bound are plotted in the same scale. Our generalization bound is tight with respect to the generalization gap; for example, the bound is  $\\leq 0.08$ in Fig. 2(c). In contrast, existing generalization bounds are vacuous and much larger than 1 as shown in Table 3 and 4.\n\nIn response to your concerns, we will make the following changes to make our statements more precise. For Figure 2(c), Fig A4 (d), and Fig. A5 (d), we will say that the bound is “tight\" instead of \"maintaining a strong correlation\". The high correlation we meant is the correlation between Gene$(w, S)$ and the test error of different models shown in Figure 1.\n\n---\n**Q7. Gradient flow vs. Realistic NNs**\n\nA7. Please refer to Q1 in the global response."}]

Author rebuttal:
### **Global Response**

We would like to thank all the reviewers for taking the time and effort to review our paper! We are delighted to learn that our paper was positively received, and the reviewers found that: 
 - the background, relevant work, and the proposed method are brilliantly presented (Reviewer Zsen); 
- the new generalization bound based on the loss path kernel has its value and the numerical simulation and implementation in NAS show that their analysis can be used in practice and their theorem is not vacuous (Reviewer kZTv);
- this looks like a significant amount work, extending and generalising existing theory in the Neural Tangent Kernel framework (Reviewer W7Wt); 
- and paper follows an interesting idea of generalising tangent kernels to path integrals and it is timely and potentially interesting contribution (Reviewer kz2v). 

We also recognize that the reviewers are busy handling multiple papers, so their thoughtful feedback is even more appreciated. 

Below, we provide an answer to a common question shared by Reviewer Zsen, kZTv, and kz2v in this global response. We also address the concerns and questions raised by each reviewer and detail our plans for updating the paper. We will add the changes in the revision (both in the main text and appendix).

Please don’t hesitate to let us know if you have any additional feedback or questions regarding our response. We would be happy to address any remaining concerns with you in the discussion period if any. If our responses have addressed your concerns and questions, we would appreciate it if you could kindly let us know and consider raising your review score.

Thanks for your time and review!

---
**Q1. Extension to practical gradient descent with a finite learning rate.**

A1. We thank the reviewers for this important question. First, we would like to highlight that all our experiments have been conducted under practical scenarios. Specifically, in Experiments (I) and (II) (Section 7, line 306), we trained NNs with a relatively large learning rate (lr=10 for NTK parameterization), while the gradient flow and gradient descent overlapped well (see Fig. 2 (a)) and the bounds were non-vacuous (Fig. 2 (b) and (c), Fig. 3).

Following the reviewer’s suggestion, we show below that it is possible to extend our results to gradient descent with a finite learning rate setting. In this case, the loss path kernel will be defined as a summation instead of an integration over training trajectory as follows,

$$\mathsf{K}\_T(z, z') = \sum_{t=0}^{T-1}\left\langle \nabla_{w} \ell(w_{t}, z), \nabla_{w} \ell(w_{t}, z') \right\rangle.$$

Under the assumption that the loss $\ell(w, z)$ is $\beta_\ell$-smooth and convex, we can get a similar bound as the gradient flow one with an additional term that involves the learning rate $\eta$ and smoothness constant $\beta_\ell$:

$$\mathcal{E}(\mathcal{S}, \eta, T) = \frac{\beta_\ell \eta^2}{2 n^2} \sum_{i = 1}^{n}\sum_{j = 1}^{n} \mathsf{K}_T(w_t; z_i, z_j).$$ 

When $\eta \rightarrow 0$, $\mathcal{E}(\mathcal{S}, \eta, T) \rightarrow 0$. 


---
**Q2 The norm constraint [$\frac{1}{n^2} \sum_{i, j} \mathsf{K}_T(z_i', z_j';\mathcal{S}') \leq B^2$, line 192] limits the datasets $\mathcal{S}'$ LTK and LPK can be considered over. How does this limit the applicability/generality of results?**

A2. This norm constraint balances a tradeoff between the tightness of the bound and the expressiveness of the set $\mathcal{G}\_T$ (that is, the number of datasets $\mathcal{S}'$ over which LTK and LPK can be applied to). A small $B$ results in a tighter bound, whereas a large $B$ allows for more datasets to be covered. In an extreme case, we can choose $B^2 = \sup_{\mathcal{S}'} \frac{1}{n^2} \sum_{i, j} \mathsf{K}_T(z_i', z_j';\mathcal{S}') $ to encompass all possible $\mathcal{S}'$. 

Finally, it is worth noting that similar kinds of norm constraints have appeared in previous norm-based bounds [1, 2, 3, 4]. By applying a method akin to that found in [2, Lemma A.9], one can cover the parameter space and use a union bound to eliminate this norm constraint.

[1] Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463–482, 2002.

[2] Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. Spectrally-normalized margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.

[3] Neyshabur, Behnam, Ryota Tomioka, and Nathan Srebro. "Norm-based capacity control in neural networks." Conference on learning theory. PMLR, 2015.

[4] Neyshabur, B., Li, Z., Bhojanapalli, S., LeCun, Y., and Srebro, N. The role of over-parameterization in generalization of neural networks. In International Conference on Learning Representations, 2019. 

Meta-review: The authors propose a new kernel that is used for analyzing the generalization behavior of neural networks trained by gradient flow, called the loss path kernel.  They introduce a data- and path-dependent generalization bound based on this kernel with a Rademacher-complexity based analysis.  They show that there is relatively large correlation between the proposed generalization bound and observed generalization bounds in (gradient descent-) trained neural networks in some settings.   

The reviewers were largely supportive of this work.  One reviewer's main concern was the connection between the analysis for gradient flow and the applicability to finite-step gradient descent, but the authors' rebuttal largely addressed this concern.  

The other 3 reviewers expressed support for the novelty of the approach of a path-based generalization bound.  I concur with these reviewers and think this novel approach is worth publication and further investigation; I recommend acceptance.
Decision: Accept (poster)