Learning Trajectories are Generalization Indicators
Authors: Jingwen Fu
Zhizheng Zhang
Dacheng Yin
Yan Lu
Nanning Zheng
Venue: NeurIPS 2023 poster (2023)
Keywords: Generalization
Learning Trajectory

Abstract: This paper explores the connection between learning trajectories of Deep Neural Networks (DNNs) and their generalization capabilities when optimized using (stochastic) gradient descent algorithms. 
Instead of concentrating solely on the generalization error of the DNN post-training, we present a novel perspective for analyzing generalization error by investigating the contribution of each update step to the change in generalization error. This perspective enable a more direct comprehension of how the learning trajectory influences generalization error. Building upon this analysis, we propose a new generalization bound that incorporates more extensive trajectory information.
Our proposed generalization bound depends on the complexity of learning trajectory and the ratio between the bias and diversity of training set. Experimental observations reveal that our method effectively captures the generalization error throughout the training process. Furthermore, our approach can also track changes in generalization error when adjustments are made to learning rates and label noise levels. These results demonstrate that learning trajectory information is a valuable indicator of a model's generalization capabilities.

Learning Trajectories are Generalization Indicators
Jingwen Fu'; Zhizheng Zhang2t, Dacheng Yin Yan Lu Nanning Zheng' fu1371252069 wtw.xjtu.edu.com (zhizzhang.>) yanlu @ @iicrosoft.com
ydc @ mail. uste edu.cn
nnzheng @ mail.xjtu.co euu..enduccnn
National Key Laboratory of Human-Machine Hybrid Augmented Intelligence, National Engineering Research Center for Visual Information and Applications. and Institute of Artificial Intelligence and Robotics, Xi' an Jiaotong University, Microsoft Research Asia, University of Science and Technology China
Abstract
This paper explores the connection between learning trajectories Deep Neu- ral Networks (DNNs) and their generalization capabilities when optimized using (stochastic) gradient descent algorithms. Instead of concentrating solely on the generalization error of the DNN post- training, present novel perspective for analyzing generalization error by investigating the contribution of each update step the change in generalization error. This perspective enable more direct com- prehension of how the learning trajectory influences generalization error. Building upon this analysis, propose new generalization bound that incorporates extensive trajectory information. Our proposed generalization bound depends on the complexity of learning trajectory and the ratio between the bias and diversity of training set. Experimental observations reveal that our method effectively captures the generalization error throughout the training process. Furthermore, our approach can also track changes in generalization error when adjustments are made to learn- ing rates and label noise levels. These results demonstrate that learning trajectory information is valuable indicator of model's 's generalization capabilities.
1 Introduction
The generalizability of Deep Neural Network (DNN) is a crucial research topic in the field of machine learning. Deep neural networks commonly trained with limited number of training samples while being tested on unseen samples. Depite the commonly used independent and identically distributed (i.i.d.) assumption between the training and testing sets, there often exists varying degree of discrepancy between them real-world applications. Generalization theories study the generalization of DNNs by modeling the gap between the empirical risk [37] and the popular risk [37]. Classical uniform convergence based methods [20] adopt the complexity of the function space analyze this generalization error. These theories discover that more complex function space results in larger generalization eπror [38]. However, they are not well applicable for DNNs [33, 22]. In deep learning, the double descent phenomenon [6] exists, which tells that larger complexity of function space may lead to smaller generalization error. This violates the aforementioned property in uniform convergence methods and imposes demands in studying the generalization of DNNs.
Although the function space of DNNs is vast, not all functions learning algorithms. Therefore, some representative works bound the generalization of DNNs based
within that space can be discovered by
Work done during internships at Microsoft Research Asia. Corresponning Authors
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

on the properties of the learning algorithm, e.g., stability of algorithm [11], information -etorrttccc analysis [40]. These works rely on the relation between the input (i.e.. training data) and output (weights of the model after training) of the learning algorithm to infer the generalization ability of the learned model. Here, the relation refers to how the change of one sample in the training data impacts the final weights of model in the stability of algorithms while referring to the mutual information between the weights and the training data in the cooommationtthooette analysis. Although some works [24, 11] leverage some information from training process to understand the properties of learning algorithm, there is limited trajectory information conveyed.
The purpose of this article is to enhance our theoretical comprehension of the relation between learning trajectory and generalization. While some recent experiments [9, 13, 29] have shown strong correlation between the information contained in learning trajectory and generalization, the theoretical understanding behind this is still underexplored. By investigating the contribution of each update step to the change in generalization error, we give new generalization bound with rich trajectory related information. Our work can serve as a starting point to understand those experimental discoveries.
1.1 Our Contribution
Our contributions can be summarized below:
We demonstrate that learning trajectory information serves as valuable indicator of gen- eralization abilities. With this motivation, we present a novel perspective for analyzing generalization error by investigating the contribution of each update step to the change in generalization error.
Utilizing the aforementioned modeling technique, we introduce novel generalization bound for deep neural networks (DNNs). Our proposed bound provides a greater depth of trajectory-related insights than existing methods.
Our method effectively captures the generalization error throughout the training process. And the assumption corresponding to this method is also confirmed by experiments. Furthermore, our approach can also track changes in generalization error when adjustments made to learning rates and label noise levels.
2
Related Work
Generalization Theories Existing works on studying the generalization of DNNs can be divided into three categories: the methods based on the complexity of function space, the methods based on learning algorithms, and the methods based on PAC Bayes The first category considers the generalization DNNs from the perspective of the complexity of the function space. Many methods for measuring the complexity of the function space have been proposed, e.g. VC dimension [39], Rademacher Complexity [4] and covering number [33]. These works fail in being applied to DNN models since the complexity of the function space of DNN model is too large deliver trivial result [41]. This thus motivates recent works to rethink the generalization of DNNs based on the accessible information in different learning algorithms such as stability of algorithm [11], information- theoretic analysis [40]. Among them, the stability of algorithm [7] measures how one sample change of training data impacts the model weights finally learned, and the information theory [30, 31, 40] based generalization bounds rely on the mutual information of the input (training data) and output (weights after training) of the learning algorithm. Another line PAC Bayes [19] based method, which bounds the expectation of the еттоr rates of classifier chosen from a posterior distribution in terms of the KL divergence from given prior distribution. Our research modifies the conventional Rademacher Complexity to calculate the complexity of the space explored by learning algorithm, which in turn helps derive the generalization bound. Our approach resembles the first category, as we also rely on the complexity of the function space. However, our method differs as we focus on the function space explored by the learning trajectory, rather than the entire function space. The novelty of our technique lies in addressing the issue of dependence between training data and the function space explored by the learning trajectory, a dependence that is not permitted by the original Rademacher Complexity Theory.

---

Generalization Analysis for SGD The optimization plays an nonnegligible role in the success of DNN. Therefore. there are many prior works studying the generalization of DNNs by exploring property of SGD, which could be summarized into two categories: stability of SGD and information- theoretic analysis. The most popular way of the former category to analyze the stability of the weights updating. Hardt et al. [11] is the first work to analyze the stability of SGD with the requirements of smooth and Lipschitz assumptions. Its follow-up works try to discard the smooth [5], or Lipschitz [25] assumptions towards getting more general bound. Information-theorcle methods leverage the chain rule of KL-divergence to calculate the mutual information between the learned model weights and the data. This kind of works is mainly applied for Stochastic Gradient Langevin Dynamics(SGLD)) i.e., SGD with noise injected in each step parameters updating [28]. Negrea et al. [23], Haghifam al. [10] improve the results using data-dependent priors. Neu et al. [24] construct an auxiliary iterative noisy process to adapt this method to the SGD scenario. In contrast to these studies, our approach utilizes more information related to learning trajectories. A more detailed comparison can be found in Table and Appendix B.
Generalization Bound
Let us consider supervised learning problem with instance space 2 and a parameter space W. The loss function can be defined as f W x 2 -> Th.. We denote the distribution of the instance space E as μ.. The n i.i.d samples draw from μr are denoted as S = [=1...., .... 2n) n². Given parameters w, the empirical risk and popular risk are denoted (s(w) 1 E. [(w, zi), and Fw(w) A (f,, []] respectively. Our work studies the generalization error of the learned model, Le. F2, (w) (w) - (w) For an optimizaiton process, the learning trajectory is represented as a function J : N + W. We use J, to denote the weights of model after times updating, where J. (t). The learning algorithm is defined as A: μ²" x R J. where the second input IR denotes all randomness in the algorithm A, including the randomness in initialization, batch sampling el al. We simply use A(S) to represent random choice for the second input term. Given two functions U, V. f, (t)) è Σ, (t 1) (t)) and use || to denote 7.2 norm. If S is a set, then |S] denotes the number of elements in S. E, denotes taking the expectiation conditioned on {Jili t).
Let mini-batch B be random subset sampled from dataset S, and we have B = b. The averaged function value of mini-batch B is denoted as Fs(w) & E=EB f(w, 2). The parameters updated with gradient descent can be formulated as:
Je+1 J. Ti FJ..).
(I)
where is the learning rate for the 1-th update. The parameter updating with stochastic gradient descent is:
Jt+1 = Jr nh (J......
(2)
Let <(w) A (w) (w) be the gradient noise in mini-batch updating, where w is the weights of DNN. Then can transform Equation (2) into:
J++1 = J, T V (J...) + (Je).
(3)
The covariance of the gradients over the entire dataset S can be calculated as:
[(w) A
2 T -F1--FFs(WW)) VFs(w))FFsw))
(4)
1=1
Therefore, the covariance of the gradient noise e(w) is:
A b
C(w)
b(n 1) I(w).
(5)
Since for any we have E[e(w))= O, we can represent e(w) C(w) where e' is random distribution whose mean is zero and covariance matrix is an identity matrix. Here, can be any distributions, including Guassian distribution [12] and SoS distribution [35].
The primary objective of our work is to suggest new generalization bound that incorporates more comprehensive trajectory-related information. The key aspects of this information are: 1) It should be adaptive and change according to different learning trajectories. 2) should not rely on the extra information from data distribution μ except from the training data S.
3

---

3.1 Investigating generalization alone learning trajectory
As annotated before, the learning trajectory is represented by function N - W. which defines the relationship between the model weights and the training timesteps t. J, denotes the model weights after times updating. Note that J depends on S, because it comes from the equation J A(S) We simply use (J)) 2 - 2 to represent the function after (-times update. Our goal is to analyze the generalization error, i.e., (Jr) (J)Jr), where 7 represents the total training steps.
We reformulate the function corresponding to the finally obtained model as:
f(Jr) fJoo + - f(Je-1))
-
(6)
Therefore, the generalization emor can be rewritten as:
T [(FA())) - Fa((J-1)) (Fs(J.) - Fs(Jt-1))]
(J(JT) Fs(JT) = (Jo) - FJ(Jo)
(a)).
In this form, we divide the generalization error into two parts. (i) is the generalization error before the training. (ūi), the generalization error caused by t-step update.
Typically, there is independence between Jo and the data S. Therefore, we have IE()) = 0. Combining with this, we have:
- - = E Σ (i),.
(8)
t=1
Analyzing the generalization error after training can be transformed into analyzing the increase of generalization error for each update. This is straighforward and quite different way extract the information from learning trajectory compared with previous work. Here, we list two techniques that most used by previous works to extract the information from learning trajectory.
(TI), This method leverages the chaining rule of mutual informaton to calculate upper bound of the mutual information between JT and the training data S, i.e. J() s [(S:JesT) s Ei=o [[S:] I() is the value of concerning for their theory. (T2). This method assumes we have another data S', which is obtained by replacing one sample in data S with another sample drawing from distribution trajectory trained from data S' with same randomness value as J. Denote A. A | J and assume Ao = 0. Then, the value of concerning Ar. The upper bound of Ar is calculate by iterately apply the formular A I Ck- A + 6k-1-
J' is the learning
(TI) is commonly utilized in analyzing Stochastic Gradient Langevin Dynamics(SGLD) [18, 2, 28], while (T2) is frequently employed in stability-based works for analyzing SGD [11, 15, 5J. Our method offers several benefits, including: 1) We directly focus on the change in generalization error, rather than intermediate values such as A₁ and I(S; (((ce)) 2) The generalization error is equivalent to the sum of (di)s, while (T1) and (T2) takes the upper bound value of ((S:J) and Ar, and 3) From this perspective, We extract more in-depth rrajeed information. For (TI), the computation of Je primarily involves the information V F2 (J.), which inaccessible to us (Detail in Appendix D and Neu et al. [24]). (T2) faces the challenge that only the upper bounds of G and eg can be calculated. The upper bounds remain unchanged across various learning trajectories. Consequently, both (TI) and (T2) have difficulty conveying meaningful trajectory information.
3.2
A New Generalization Bound
In this section, introduce the generalization bound based aforementioned modeling. Let us start with the definition of commonly used assumptions. Definition 3.1. The function f is T.-Lipschitz, for all W1, Wa E and for z 2, wherein we have (1f( 2) f(w2, 2)]l < L|[w1 w2ll.

---

Definition 3.2. The function f is 3-smooth, if for all W1, W2 E W and for all & E 2, wherein we have [[ Vf(22. =)Il I Bl[w, w2ll-
Definition 3.3. The function f is convex, if for all W1, W2 W and for all a E Z, wherein we have
f(w1. 2) 2 f(w2,2) 2) + (w1 w W
Here, L-lipschitz assumption implies that the [V 2) - L holds. B-smooth assumption indicates the largest cignvalue of f(,, is smaller than B. The convexity indicates the smallest eigenvalue of V² 2w) are positive. These assumptions tell us the constraints of gradients and Hessian matrices of the training data and the unseen samples in the test set. Since the values of gradients and Hessian matrices in the training set are accessible, the key role of these assumptions to deliver knowledge about the unseen samples in the test set.
In the following, we introduce a new generalization bound. We give the assumption required by our new generalization bound in the following.
Assumption 3.4. There is a value 7, so that for all E {Je]c E NJ, we have ([VF(())] S >[)FF(())]l
Remark 3.5. Assumption 3.4 gives a restriction with the norm of popular gradient (w). This assumption is easily satisfied when n is large number, because we have lim [VF((w]] =
(w)), When the is not large enough, the assumption will hold before SGD enter the neighbourhood of convergent point. Under the case that SGD enters the neighbourhood of convergent point, we give relaxed assumption and its corresponding generalization bound in Appendix B. According to paper [42], this case will ununsually happen in real situation. Section gives experiments to explore the assumption.
Theorem 3.6. Under Assumption 3.4, given S ~ n², let J A(S), where A denoted the SGD or GD algorithm training with T steps, we have:
(J.(
Tr(E(J.)
- 4
(1m))
(9)
where V(()
[s()]]
V. m =
max V(J+).
7
Becell V (w)) (W))
max(1, 1, max Fe by and 7m & max
UCSI (J)))
Remark 3.7. Our generalization bound mainly relies the information from gradients. V(w) is related to the variance of the gradient. When the variance of the gradients across different samples in the training set S is large, then the value of V(w) is small, and vice versa. Note that we have |U|
due to U C S. Our bound will became trival if Eucs || L Fr((w) This rarely happens in real case, because it requires that for all U C. S, we have Vo (n - ) Fsyu(ww, We also give relaxed assumption version of this theorem in Appendix B. The generalization bound provides clear insight into how the reduction of training loss leads increase in generalization error.
n- U VS/uU (w))(w)]] = 0.
Proof Sketch proof.
The proof of this theorem is placed in Appendix A. Here, we give the sketch for this
Step Beginning with Equation (8), we decomposite the (2(JT) FJ(JT) into a linear part
(gen lin (Jr)) and nonlinear part(gen""(( We have "ix (Jr) -- ( where (ii) fnn &
(J, Jt-1 ) (J - Fs (J.- )). The nonlinear part is gen" gen ii (Jr). We takle these two parts differently. Here, we focus on analyzing im because
(J(JT) ([J])=-))) (s(JT)
dominates under small learning rate. Detail discussion gen (JT) is given in Appendix (Propositon
A.1 and Subsection C.3)
Step 2 We construct the addictive linear space Lais A (ET- w. TVf(J+) [|wel I A.). where A, P (i)+ill Then Elgen (JT)) & D.V where Rs(Cais) & E, sup ( E4 (;)()))). hE c
5

---

Table 1: Comparison of the generalization bounds with stability based method for SGD learning algorithms. T.R.T is an abbreviation for the term related to trajectory. T.R.T is defined as the term that 1) varies based on different learning trajectories, and 2) don't rely on the extra information of data distribution except from training data S. We can infer that the proposed bound incorporates greater amount of information pertaining to the trajectory. Other related works discussed in Appendix D.
B.mmah
Ciness
Small
Olber Caralaana
Hank dill [11]
E Phiis
LainTain Jeppy
Ztongetal [33]
Tonu
2ho [4]]
Mecel Rowwl/ Veedwil 1P
Besily et al. (5)
Pri Projsted SGD (
2x? V2 ae Li C Oli A1
Lai Yag
Ous (Therem.3.0 3.0)
Theorem 3.6
Step Finally, we compute the upper bound of Rs RS(Ls))), which follows same techniques used in Radermacher Complexity theory. By combining this with Proposition A.I, we establish the theorem.
Technical Novety Directly applying the Rademacher complexity calculate the generalization error bound fails because the large complexity of neural network's ' function space leads to trival bound[41]. In this work, we want calculate the complexity of the function space that can be explored during the training process, However, there are two challenges here. First, the trajectory of neural network solve this problem, we indroduce the addictive linear space Lass. This space contains the local information of learning trajectory, and can serve as the pseudo function space. Second, the function space LJis has a dependent on the sample set S, while the theory of Rademacher complexity requires that the function space is independent with training samples. To decouple this dependence, we adapt the Rademacher complexity and we obtain that Elgen (Jr)) s ERs Here, 7 is indroduced to decouple the dependent fact mentioned above.
"line", instead of function space that can be calculated the complexity. To
Next, in order to draw a clearer comparison with the stability-basee -based method, we present the following corollary. This corollary employs the 8-smooth assumption bound gen nd (J.r) and leverages similar learning rate setting to that found in stability based works.
Corollary 3.8. If function f(-) is 3-smooth, under Assumption 3.4 given S p., let J A(S). Me B(T+Ty. M2 max V (3)))) and Mt max EE- (Fs (cJ.)) where A denoted the SGD or GD algorithm training with T steps, we have:
(Jes
Tr(E(J)))
(JF) - Fs(JT) < 2
VIV (J+)
+222 m MR
B
dt
11 Tr(E(J.)
(10)
(1 + 1)4
(VFs(J.)
M2
2c
B
where V(w)
IV (V))))
Vn = max V(J.) and N
Bucsl V. (w)
V (w)ll
max(1, max
UCSa v[VFs().)] 1%

---

3.3
Further Analysis
3.3.1 Interpreting the Generalization Bounds
We rewrite the obtained generalization bound here:
Divesiity Truting
(J) vn
Tr (E V (J+)
- - v
V m
2E
+ (mm)
Biss of Training Set
Complexity Learning Trajectory
(11)
The "Bias of Training Set" refers to the disparity between the characteristics of the training set and those the broader population. To measure this difference, we use the distance between the norm of the popular gradient and that of the training set gradient, specified in Assumption 3.4. The "Diversity of Training Set" can be understood as the variation among the samples in the training Training Set set, which in turn affects the quality of the training data. The ratio Diversity of Training Set gives us the property of information conveyed by the training set. It is important to consider the properties of the training set, as the data may contribute equally the generalization[36] The detail version of the equation can be found in Theorem 3.6.
3.3.2 Asymptotic Analysis
We will first analyze the dependent of n for V. The V is calculated as V(w) = Obviously, the gradient of individual sample is unrelated to the sample size n. And |U] n. Therefore, V O Similarly, we have (2))) As for the ((1)) term in Theorem 3.6, we have lim (mT)) = 0 according to Proposition A.1. We simply assume that O( = O (2,)). Therefore, n-+00
[VF](w]]
Bocs l| - Fe(()- - S. (
J. (F) Vn /1+ TI(J)
[J.)]l
our bound has O [m,]
3.3.3 Comparison with Stability- methods
We first compare our method with the stability-based methods in terms of the trajectory information. In Table 1, present a summary of stability-based methods, while other methods are outlined in Appendix D. We focus on generalization bounds from previous works that eliminate terms dependent extra information about data distribution f4, apart from the training data S, using assumptions such as smoothness or Lipschitz continuity. Analyzing Table 1 reveals that most prior works primarily depend the learning rate v) and the total number of training steps T. This suggests that we can achieve the same bound by using an identical learning rate schedule and total training steps, which does not align with our practical experience. Our proposed generalization bound considers the evolution of function values, gradient covariance, and gradient norms throughout the training process. As a result, our bounds encompass more comprehensive information about the learning trajectory.
Table 2: Detail comparison with Hardt et al. [11]. The 3 refers to the 8 smsohhhh assumption (see in Definition 3.2). S denotes the training set.
Unitorm Siability 11]
Ours
Assumpison Modelling Method SGD
VW E W
V7 [...
VW (Jeif N)
[E (w. [[W.,.
Epoch Structure
Foll Batch Gradient + Stoclastic Noisc
Batch Size Trajectory Information Bound Perspective
Learning and number of training step
Values in Trijectory (gradient and covariance) Complexity of Learning Trajectory
Stability of Algorithm
Next, we give a detail comparison with Hardt et al. [11] in Table 2. The concept of uniform stability is commonly used to evaluate the ability of SGD in generalizaton, by assessing its stability when single training sample is altered. Our primary point of comparison with Hardt et al. [11], as their work is considered the most representative in terms of analyzing the stability of SGD. We find that First, the assumption of Uniform Stability requires the gradient norm of all input samples for all weights being bounded by L, whereas assumption only limits the expectation of the gradients
7

---

for the weights during the learning trajectory. Secondly, Uniform Stability uses an epoch structure to model the stochastic gradient descent, whereas our approach regards each stochastic gradient descent as full batch gradient descent with added stochastic noise. The epoch structure complicates the modelling process because requires a consideration of sampling. As result, in Hardt et al. [11], the author only considers the setting with batch size 1. Thirdly, the bound of Uniform Stability only uses hyperparameters setting such as learning rate and number of training step. In contrast, our bound contains more trajectory-relant the Uniform Stability provides the generalization bound based on the stability of the algorithm. while our approach leverages the complexity of the learning trajectory. In summary, there are some notable differences between our approach and Uniform Stability, such as the assumptions made, the modelling process, the type of information used in the bound, and the perspectives.
information, such as the gradient norm and covariance. Finally,
4 Experiments
4.1 Tightness of Our Bounds
Table 3: Numeric comparison with stability-based work on toy examples. The reason for the value of Zhang et al. [43] is large is because that our and Hardt al. [11] has dependent on 4. while
Zhang et al. [43] depends on L L and /3 are usually large numbers.
Gen Error
Ours 3.62
Hardt et al. [11] Zhang et al. [43]
1.49
4.04
4417
In toy dataset setting, we compare our generalization bound with stability- -based methods.
Reasons for toy examples 1) Some values in the bounds are hard to be calculated. Calculating 3 (under the B-smooth assumption) and L (under the I--Lipschitz assumption) in stability- based work, as well as the values of V and y in our proposed bound, are challenging. 2) Stability-base methods require batch size of 1. The training is hard for batch size of I with learning rate setting ") in complex datasets.
Constuction of the toy examples In the following, we discuss the construction of the toy dataset used to compare the tightness of the generalization bounds. The training data is X,, = {mx ) All the data v; is sampled from Guassian distribution N(O, Ia). Sampling w ~ (0, La).the ground truth is generated by y: 1 if w TTz, > O else O. The weights for learning is denoted as w. The predict ÿ is calculated y; w wT,,, The loss for simple data point is = || w 4: l| The w
training loss is L Σー= 4, The test data is X.. (x()), where x o and & (0 Ia). We use 100 samples for training and 1,000 samples for evaluation. The model is trained using SGD for 200 epochs.
We evaluate the tightness of our bound by comparing our results with those in Hardt et al. [1]] and Zhang et al. [43] from the original paper. We set the learning rate t/e Our reasons for comparing with these two papers are: 1) Hardt et al. [11] is representative study, 2) Both papers have theorems using a learning rate setting of 7/. = O(}), which aligns with Corollary 3.8 in our paper, and 3) They do not assume convexity. The generalization bounds compare include Corollary 3.8 from our paper, Theorem 3.12 from Hardt et al. [11], and Theorem 5 from Zhang et al. [43].
Our results are given in Table 3. Our bound is tighter under this setting.
4.2
Capturing the trend of generalization error
In this section, 1) we conduct the deep learning experiment to verify Assumption 3.4 and 2) Verify whether our proposed generalization bound can capture the changes of generalization error. In this experiment, mainly consider the term C(J,) -2
dFs(J,) v / TH())))) We omit the term y and Vn. because all the trajectory related information that we want to explore is stored in C(J.). Capturing the trend of generalization error is regarded as an important problem in Nagarajan
(J
[21]. Unless further specified, we use the default setting of the experiments on CIFAR- 10 dataset [14]
8

---

Cifar10
Ci
SVHN
5.0
ww
50
100
25
50
100
25
50
75
100
Training Loss
2-
1-
100
25
100
100
Epoch
Epoch
Epoch
Figure I: Exploration of Assumption 3.4 for different dataset. The 5/e is stable before training loss reaches relative small value. Assumption holds the training stop before extremely overfitting. A relaxed assumption and its corresponding generalization bound are given in Appendix B for extremely overfitting situation
Fill)
dc AcUblldFFUel
(e
08
Full)
04-
08-
04-
00
4pp7
02-
1/
50
150
200
50
100
150
200
100
150
200
Epoch
Epoch
Epoch
The curve Fs. + C(J,) exhibits comparable Pattern with the curve Fs (Jt). Center: After the early stage, C(J,) and F (J.) (J,, have similar trend. Right: The value of aC(J,) alone the training process. 2Fs(Je)
Figure 2: Exploration of C(J.) during the training process. Left:
with the VGG13 [34] network. The experimental details for each figure can found Appendix C.2.
Our observations are:
Assumption 3.4 is valid when SGD is not exhibiting extreme overfitting.
The term of CJ++) depict how the generalization error varies along the training process. And can also track the changes in generalization error when adjustments are made to learnling rates and label noise levels
Exploring the assumption 3.4 for different dataset during the training process To explore the Assumption 3.4, we define " & (J+)ll and 7/2 A Fere(r P[V))l where is another data set i.i.d sampled from distribution μ.. Because S' is independent with S. we have 7e s Yt- We found that 7e stable around during the early stage training(Figure 1). When the training loss is reaching relative small value, 7t increases we continue training. This phenomenon remain consistant aross the Cifar 10 Cifar 100 and SVHN datasets. The y Assumption 3.4 can be assigned as ? max, "it- We can always find such y if the optimizer is not extreme overfitting. Under the extremely overfitting case, we can use the relaxed theorem in Appendix to bound the generalization error.
[[F]]]
The bound capturing the trend of generalization error during training process The generaliza- tion error and the C(J+) both changes as the training continues. Therefore, we want to verify whether they correlate with each other during the training process. Here, we use the term V FF (J,)- (163)-FFa (J.,) to approximate the generalization error. We find that (J. - V (J.)) has similar trend with C(J+) (Figure 2 Center). What's more, a comparable pattern with the curve Es (J+) (Figure 2 Left). To explore whether C(J,) reveals influence of the change of (J+.) to the generalization error, we plot dC(Je). (Figure 2 Right) during aFs(J.)
also find that the curve of V (J)e) + C(J,) exhibits

---

<go Fo Augel
12-
Fr Faglo
0.5
54
0.00 0.10
0.20
0.5
0.30
10-2
Noise
Learning Rate
Figure 3: C(JT) correlates with (J.) VJs(J.). Left: C(J+) and the generalization error under different label noise level. Right: C(J.) and the generalization error under learning rate. The C(J+) can capture the trend of generalization Appendix E provides proof that a large learning rate results a smaller proposed generalization bound. Further discussions why small learning rate leads to larger generalization error can be found in et al. [17], Barrett and Dherin [3].
cased by learning rate when learning rate is small.
the training process. dC(J.)
dFs(J,] increases slowly during the early stage of training, but surge rapidly
afterward. This discovery is aligned with our intuition about the overfitting.
The complexity of learning trajectory correlates with the generalization error In Figure 3, we earry experiments under various settings. Each data point in the figure represents the average of three repeated experiments. The results demonstrate that both the generalization error and C(J,) increase as the level of label noise is raised (Figure Left). The another experiments measure C(J,) and generalization error for different learning rate and discover that C(J,) can capture the trend generalization error. The reasons behind larger learning rate resulting in a smaller generalization error have been explored in Li et al. [17], Barrett and Dherin [3]. Additionally, Appendix E discusses why larger learning rate lead to smaller C(J,).
Limitation
The assumption of small learning rate is required by our method. But this assumption is also common use in previous works. For example, Hardt al. [11], Zhang et [43], Zhou et al. [44] explicitly requires that the learning rate should be small and is decayed with rate of O Some methods have no explict requirements about this but show that large learning rate pushes the generalization bounds to trivial point. For example, the generalization bounds in works [5, 16] have a term Σ 1/2 that not decayed as the data size n increases. The value of this term is unignorable when the learning rate is large. The small learning assumption widens the gap between theory and practice. Eliminating this assumption crucial for future work.
Conclusion
In this study, investigate the relation between learning trajectories and generalization capabilities of Deep Neural Networks (DNNs) from a unique standpoint. We show that learning trajectories serve reliable predictors for DNNs generalization performance. To understand the relation between learning trajectory and generalization error, we analyze how each update step impacts the generalization error. Based this, we propose novel generalization bound that encompasses extensive information related to the learning trajectory. The conducted experiments validate our newly proposed assumption. Experimental findings reveal that our method effectively captures the generalization error throughout the training process. Furthermore, our approach can also track changes in generalization error when adjustments made learning rates and the level of label noises.
7 Acknowledgement
We thank all the anonymous reviewers for their valuable comments. The work was supported in part with the National Natural Science Foundation of China (Grant No. 62088102).
10

---

References
[1] K. Ahn, J. Zhang, and S. Sra. Understanding the unstable convergence of gradient descent. In International Conference Machine Learning, pages 247-257. PMLR, 2022.
[2] A. Banerjee, T. Chen, X. Li, and Y. Zhou. Stability based generalization bounds for exponential family langevin dynamics, arXiv preprint arXiv:2201.03006, 2022.
[3] D. G. Barrett and B. Dherin. Implicit gradient regularization. arXiv preprint arXiv:2009./1162,
2020.
[4] L.. Bartlett and S. Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
[5] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381-4391, 2020.
[6] M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-learning practice and the classical variane trade-off. Proceedings of the National Academy of Sciences, 116 152):15849-15854 2019.
[7] O. Bousquet and Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
[8] N. Chandramoorthy, A. Loukas, K. Gatmiry, and S. Jegelka, On the generalization of learning algorithms that do not converge. arXiv preprint (tti::2008.075552 2022.
[9] J. M. Cohen, S. Kaur, Y. Li, J. Z. Kolter, and A. Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. arXiv preprint arXiv: (tdi::2003.00066 2021.
[10] M. Haghifam, J. Negrea, Khisti, D. M. Roy, and G. K. Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms.
Advances in Neural Information Processing Systems, 33:9925 9935, 2020.
[11] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-1234. PMLR, 2016.
[12] S. Jastrzebski, Z. Kenton, D. Arpit, N. Ballas, A. Fischer, Y. Bengio, and A. Storkey. Three factors influencing minima in sgd, arXiv preprint arXiv:
2017.
[13] S. Jastrzebski, D. Arpit, O. Astrand, G. B. Kerg, H. Wang, C. Xiong, R. Socher, K. Cho, and
K. J. Geras. Catastrophic fisher explosion: Early phase fisher matrix impacts generalization. In International Conference on Machine Learning, pages 4784- PMLR, 2021.
[14] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[15] Y. Lei. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems. arXiv preprint 1iXiv:2206007085 2022.
[16] Y. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pages 5809-5819. PMLR, 2020.
[17] Y. Li, C. Wei, and T. Ma. Towards explaining the regularization effect of initial large learning rate in training ncural networks. Advances in Neural Information Processing Systems, 32, 2019.
[18] X. Luo, B. Luo, and J. Li. Generalization bounds for gradient methods via discrete and continuous prior. Advances in Neural Information Processing Systems, 15:10600110614, 2022.
[19] D. A. McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth annual conference on Computational learning theory, pages 164-170, 1999.
[20] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018.
[21] V. Nagarajan. Explaining generalization in deep learning: progress and fundamental limits. arXiv preprint arXiv:2110.0880 2021.
[22] V. Nagarajan and J. Z. Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
[23] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy. Information-then -tteorrtcc generalization bounds for sgld via data-dependent estimates. Advances in Neural Information Processing Systems, 32, 2019.

---

[24] G. Neu, G. K. Dziugaite, M. Haghifam, and D. M. Roy. Information-theowe generalization bounds for stochastic gradient descent. In Conference on Learning Theory, pages 3526-3545. PMLR, 2021.
[25] K. E. Nikolakakis, F. Haddadpour, A. Karbasi, and D. S. Kalogerias. Beyond lipschitz: Sharp generalization and excess risk bounds for full-batch gd. arXiv preprint arXiv:2204. 1etr22044./244,, 2022.
[26] B. Oksendal. Stochastic differential equations: introduction with applications. Springer Science & Business Media, 2013.
[27] Park, U. Simsekli, and M. A. Erdogdu. Generalization bounds for stochastic gradient descent via localized e-covers. Advances in Neural Information Processing Systems, 35:2790-2802, 2022.
[28] A. Pensia, V. Jog, and P.-L.. Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550. IEEE, 2018.
[29] Y. Ren, S. Guo. and J. J. Sutherland. Better supervisory signals by observing learning paths. arXiv preprint arXiv:2203.0244: 022455, 2022.
[30] D. Russo and J. Zou. Controlling bias adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pages 1232-1240. PMLR, 2016.
[31] D. Russo and J. Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302-323, 2019.
[32] L. Sagun, U. Evei, V. U. Guney, Y. Dauphin, and L. Bottou. Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint arXiv: 04454, 2017.
[33] S. Shalev-Shwartz and Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[34] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
[35] U. Simsekli, L. Sagun, and M. Gurbuzbalaban. tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pages 5827-5837. PMLR, 2019.
[36] B. Sorscher, R. Geirhos, S. Shekhar, S. Ganguli, and A. Morcos. Beyond neural scaling laws: beating power law scaling via data pruning. Advances in Neural Information Processing Systems, 35:19523-19536, 2022.
[37] V. Vapnik. Principles of risk minimization for learning theory. Advances in neural information processing systems, 4, 1991.
[38] V. Vapnik. The nature of statistical learning theory. Springer science & business media, 1999.
[39] V. N. Vapnik and A. Y. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Measures of complexity, pages 11-30. Springer, 2015.
[40] A. Xu and M. Raginsky. Information -hheoreticcc analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems, 30, 2017.
[41] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3): 2021.
[42] J. Zhang, H. Li, S. Sra, and A. Jadbabaic. Neural network weights do not converge to stationary points: An invariant measure perspective. In International Conference on Machine Learning, pages 26330-26346 PMLR, 2022.
[43] Y. Zhang, W. Zhang, S. Bald, V. Pingali, C. Chen, and M. Goswami. Stability of sgd: Tightness analysis and improved bounds. In Uncertainty Artificial Intelligence, pages 2364-2373. PMLR, 2022.
[44] Y. Zhou, Y. Liang, and H. Zhang. Understanding generalization error of sgd in nonconvex optimization. Machine Learning, 111ig,111111 111(1):345-37522 2022.
[45] Z. Zhu, J. Wu, B. Yu, L. Wu. and J. Ma. The anisotropic noise in stochastic gradient de- scent: Its behavior of escaping from sharp minima and regularization effects. arXiv preprint 10x3v: 0015, 2018
12

---

A Proof of Theorem 3.6
We rewrite the Equation (7) and Equation (8):
(J(TT) Fs(JT) (Jo Ps (J) + (F.(J.) (J( (Ps(J.) Fs(Jt-1)))
(s²)+
(12)
and
T - - = E
Σ (i))
(13)
1=1
Using Taylor expansion for the function f(-), we have:
f(J+) - f(J-1)) (Je VVJ= -
Jell
(14)
Therefore, we can define (#i) as:
(ii) (mn A (J, - J, J.-)) I VFs(Jt-1))
(15)
The (tt) can be decomposed as (di); (ii) (zt),', where (ti),² & (di), (10)
Then Equation 13 can be decomposited as:
(JF) (J([T)) E
(i)) E
(i))
(16)
gen Fin (Jrr)
(JTr)
Proposition A.1.
For the gradient descent or the stochastic gradient descent algorithm, we have:
Elgen Nin (JT))
E ne (L. -FF,
(17)
IfT = 0 7m
we have:
gen (Jr)) = (n)):
(18)
where 7m
A max and we have:
lim gen nl (Jr) (Jr) = 0.
(19)
Remark A.2. We give an experimental exploration of the gen"((JT) in Appendix C.3. We discover that if the optimizer doesn't 't enter the EoS (Edge of Stability) regime [9], we have gen" (JT) x 0.
Proof. Analyzing of gen tin (Jr)
Because e(w) = ((w) and B[E'] = (detail Equation (3) and Equation (5)d), we can get:
E (eT (VF, (J.) VFs(J.))
-
= BB==,((( -FF((J.) (20)
= 0.
Combining with Formula (3), we have
Efgen lin (JT)) E T-1
V. -VF,
(21)
13

---

Analyzing of gen" (Jr)
Here, we denote M - max (J).))) According to the definition of gen" (JT).
gen (JT)l FF - P (JT)l [s(JT)
- (JT))
Σ - J+ll Σ [(IJtt+1 Je
V
(22)
O M²)
1 Um M2)
O 7m
(1m)
Because all the elements of training set are sampled from distribution μa, we have lim VFs(w) = (ww,), Therefore:
n--00
lim (tt)
lim (J. (VF-)-)) -VF((J-)))
(23)
1-0000
12000
What's more, also have:
lim [F Fs(JT)] = 0.
(24)
Because (J(JT) Fs(JT) Σl (1)) + E (ii)gl we have:
T
lim n+0
ggen" "e (Jr))
lim
Σ
(1))al
lim n-000
Fa(Jr) Fs(JT) Σ (i))
10 0
n-+00
(25)
of Fals v((+))) TVV } as proxy for analyzing generalization error of the function trained using SGD or GD algorithm. The value of (Jr) is equal to the gen- eralization error of FJJs- To analyze FjJs. we construct an addictive linear space as LJis & (ET-) Wt [V)().) w|wll 6t), where 8, è Vls Here, we use J|S emphasize that J depends on S.
According the Equation (17), we analyze the generalization (Σ'-) w. TV))..) w. = 8,
Under Assumption 3.4 (that is introduced in the main paper), have the following lemma.
Lemma A.3. Under Assumption 3.4, given S n², let J A(S), we have:
E gen (Jr)] < 2 Em.ERs(Rs s),
(26)
where V(w)
V = max V(J, and of = Evcs (w)) (F)
[F]]
max(1, max UCSa
v[VFstJ.)]l 17
14

---

Proof. For a function h, we define that nn (E>ual(2)) and hy = E h(22). Given function space, the maximum generalization error of the space can be defined as: (SS, H) & beff
sup (h hg)
(|S)
sup (h2, - ht)
hemfs
sup (Bs his - hs)
heHIs
< Egr sup (ho: hs)
kENS
= Es sup hefls
Σ ( - h(2
(27)
n
EEso sup hEHIS
1
of (h((2,)))
Eg
KEHIS πi (h((t)))
sup 1 n
Σ
n
1 Σ
2 sup NEHSS
o. (h(2? )))
where S' is another i.i.d sample set drawn from n² and a denotes the Rademacher variable. The os 27 denotes 2? that belongs S if o; -1 2, E S. otherwise, 2!" E S'.
Rs (Sass) EE, sup
Σ a,h(2z))
hEC
= Eg sup
h(2) Σ h(z)))
(28)
hECJiS
=ES+
=ES_
Eg
dellgs, (Jt) - gs_ (J))l),
1=0
where S4 A {2: | of +1}
and S_ A {z/ 0i =11, and gw) & FS)WFs(W)
1 Σe (h(2)))))
Es. sup heFais
Es a sup (=
h(2))
Σ h(z)))
heFais
SES'
ZES_
T-1
(Jt)
Ess.
(g8) (J.) - gs (J.))
(29)
7
11s (J+))
1=0
T-1 1
(s(
Es
8r
(IS+ V (J+) 95_ (J+))
[J+([
where S¹ is subset of S' with [S] = |S4]. Defining & A 7/Vms
m. we have:
15

---

sup hECais
azh(2z)) Es sup
oi (+((z))))
heFais
T
gs (s(Je)
8:11ss (J+) 98 (J+)l) Est
8
(Je)] (gs; (Je) - gs (J+)))
n
9s (J+)
kBo
8ellas. (J+) 9s (J+)
6:
([++IVF((J)) -s_ (J+)))
11ss (J+)
(30)
kBo
8e 8ellgs_ (J+) 98_ (J+(
gs_ (J)()
1=0
Eg (lgs (J+) 9s (J+)l)
Σ fJ
Therefore, combining Equation (27) and (30), we have Efgen lin (JT)) s V (Rs(sRRsSss
Lemma A.4. Given J = A(S), the formula Rs (R(())))) can be upper bounded with:
Rs(La(s) S -E [FF((e))
Tr(S(w))
(31)
Vn
[F)(w)]l
Proof. Let us start with the calculation of Rs(wTV
n
Rs((w Rs((WVVf(J))llv
$6) E,
sup ||wi|
w T
o Vf 2i)
= E.
o, (J 2x)
12
Eg >
o VJ 2x)
(32)
12
E
oo V. 2;)
[ 21)1
where represents using the relation that for i,j satisfying i * j. we have Eo,o, 0.
16

---

Because is independent of w; if i # j. we have:
T-1
Rs(La|s) = Rs([)(Jo) +
Σ We (V(()),) || - {6,)) 1=
Rs([w: T (V](J)))l ||, $b.))
(33)
The covariance of gradient noise can be calculated as:
[r[x(w]] =
(34)
VV((, 2 PI [V)]
n
Taking Equation (33) and 6, -
11 (J into Equation (34), we have
T-1
Rs(Co)s)
VV =:)l
t=
5z
+
(35)
(J.)
[V
Vn
When nh is small, 8, ~ EE (J++1 J.) [vF((
EE
Fs(Jun)) (Fs
holds, therefore we have:
(J()))
T-1 dz
ERs(Lr s) S E
VJJ 2)11
n
T
FJ( FJ.
(wW) (36)
1+
Vn
VVF'( ww]l
1=0
dJFs(Jc) Vn.
Tr([(w)
E
[VFss
Theorem A.S. Under Assumption 3.4, given S ~ ,², let A(S), where A denotes the SGD or GD algorithm training with T steps, we have:
dJs(J.))
Tr(E(J.)) (J) + +(mm),
([F)(TT) - Fs(Jr)) V.
(37)
where V(w)
[w]]
Vm = max, V(J.) and N
Bucsll Fi. (w)
(w)]l
max(1, (1, max FI
n[VFs().)] }7
UCSa
17

---

Proof. We rewrite Equation 2 of the update of SGD with batchsize b here:
Jr Jt Ttt V (J + THEE
(38)
where we simplity the <(We) as Et, then we can expand the function at f(Jr) as:
T-1
(Ir) _ f(Jo)+ +
+
(39)
K-1
= f(Jo +
Σ Th 1=
(J.
Σ c (J))
Note that when the learning rate is small, we have f(Jr) ~ (JT)
The difference between the distributional value and the empirical value of the linear function can be calculated as:
T-1
(Jo) +
(e - -)) B[Ps(Jo) +
mTe V..))( + +e)
0
T-1
(J) (s(Jo) + Σ ()s +e)
V + ( (Fs(J.))
E
The (.. VPs((J))
& -
Te (L. VFs(J.))
1=0
S (s,))
(40)
where using the equation that (I - VFg(J.)) 0, according to Equation 20.
Because of (JT) Is (Jr) B (JT) + (JT) (m))) [[ (JT) Fgin (Jr) + (f).) Proposition A.1), by applying Lemma A.3 and Lemma A.4, the theorm is proved.
Corollary A.6. If function f(-) is B-smooth, under Assumption 3.4 given S ~ n², let J = A(S).
") B(F+Tj. M2 = max E.- 1 VF (J.) +(J)))(²) and M maa EE- (I) V (J,) +c(J,))l where A denoted the SGD or GD algorithm training with T steps, we have:
(J.) vn
(r.) (VFs(J.))))
(JF Fs(JT)) < 22 L.
22 m Mi IR.
dt
(1+
Tr(E(J.)
(41)
[JF)(J.)
2c M2
B
where V(w)
| [s() Bocs (w))
Vm max V(J+) and L
Fs (s)u(w)]]
max(1, 1, max UCS: Fss))l 1%
Proof. If f(-) is B-soohhh, we have:
1 f(J++1) f(J.) z -J) (F(())
81 J||
- J
(42)
2
f(J++z) - -f(,) 2 (J+11 -
Jell.. -
(43)
18

---

Combining the two equations, we obtain:
Ry (JT) (s(Jr)) $ (J(TT) - F (Jr)) + (T)(JT)
FF (Jr))
8 T-1
8 T-1
|Jt+1 - Jell?
Σ
J Jut1 J
(44)
T-1
Σ
|J+11 - Jel??
=
The generalization error can be divided into three parts:
(J)s(tt)
Tr(E(J+))
(JT) Fs(JT)] S 2 mB
Vni
('s
dF (Jt)
dFs((1.)
(r()(J))
2 V E
vn
(J.)(
(45)
(A)
T
+ BE
|Jt+1 Jell?
(B)
The ter"" is caused by using FJ(+++1) - FJ{ to replace (Jin(J++1)- - -F (J)) The term
"(B) "B))" is induced by gen" (Jr). Then, we want to give a upper bound of (A) using M1:
T
J.l12
Tr(E(J+))
(A) < V
E
-
1+
Vn
VVFs (J.)
(4)) S 2027/VmL E
VFs(J.)) EJJOI1
TT(E(J.)
B/n((+1))
T-1
(J. + {J))))
Tr(E(J.))
= 2m
B B +
(Fs(()))
(46)
(1))) < 202 m
E, (J.( + (l
T((E(J))
E, (1+
8ln(t 1)a
(J.)
Σ
MA
Tr(E(J.)
< 26 m
Ry-1
1+
Bni( + 1)d
(J)Fs
1=0
Tr(E(J.))
< 22c2g/Um.l m M2
E
1+
32n(t + 17d
(J.)l
t=0
19

---

where (+) is due to the Equation 44, (+*) is due to the update rule of Jr and (** is que to Hölder's inequality. In the following, we use M2 to give upper bound for (B):
(B)
S 3
(1+1)2
1+11
(++ 1)² M2
3
T-1
M2
Σ
(t + 1)2 M2
3
(47)
(
1+1 _
M2 Σ
M2
3
t=
2M3 - M3
$
3
< 2c M2
Taking the upper bound value of "(A)" and "(B)" into Equation 45, we obtain the result.
B Relaxed Assumption and Corresponding Bound
Assumption B.1. There is value y, To and ç, that for all (Jilt N A t < To}. have [V & (s))] and for all w E {Jelt E N A 2 To), we have VF, p (w)ll S F[ +
Theorem B.2. Under Assumption B. given S ~ n², let J A(S), where A denotes the SGD or GD algorithm training with T steps, we have:
(FFs(Je)
(r))(J.) 1 T
-(F 2
Σ nel (e))V :=To
Vn
(J.)
2
(48)
where V(w) = Rucell 1
Vm = max, V(J.) and N' =
Fo)(w) 10 (w)]
max(1, (1, max [Ull
UCStt ((),)l 1%
Proof. Most of the proofs in this part are the same as those in Appendix A, except for Equation 30.
The Equation 30 is replaced by:
20

---

Σ kEg sup heL
o,h(2i))
-s sup
(=
Σ
of
(h((z))))
π
heFsis
n2
T
(s(
kB
8el19s_(1, -gs_ Es
6
(95; (Jt) - -9- (Jt)))
[Je)
1
Is (Je)
kE
dellgs_ (J+) -s_ (J+)l
6.
(VF+)V)(())) Is_ (J+)))
(J,)
(49)
2 kEo
8e _ell9s_(Je 95_ (Jt)l
8e
gs_ (Jt)
1=0
k
&,E, (Jc) - -s_ (J+)l))
Σ
&n'IVFFs Σ
865
71
To
2
(J.]lls
2
T=
Remark B.3. Compared of Theorem 3.6, we have a extra term E 7el (Js here. Since the unrelaxed assumption F, (w)ll S [[[])s(()]] satisfied only when [[V]s())]] relative small, the term Σirr, V Fs (J+)ll is small value.
C Experiments
C.1 Calculation of C(J)
To reduce the calculation, we construct randomly sampled subset Sap {21p ...., z()) zP) C.S
(Js(
Tr
(Fs(
V [f[[, 2011
Li=l
Vn
Fs
(J.)
Vn.
| WVFs (Jt))
(Js(J.)
Rap i=
|V 24
>
1
Vn
nap
[V (J+)
Denote the weights after 1-epoch training as X.. We can roughly calculated C(J.)
T
(X,) Fs (X
Σ
VS(Xt: 2 >
Vn
Nap
IV (X.))
C.2 Experimental Details
Here, we give detail setting of the experiment for each figure.
Figure The learning rate is fixed 0.05 during all the training process. The batch size is 256. All experiments is trained with 100 epoch. The test accuracy for CIFAR-10, CIFAR-100, and SVHN are 87.64%, 55.08%, and 92.80%, respectively.
Figure The initial learning rate is set to 0.05 with the batch size of 1024. We use the Cosine Annealing LR Schedule adjust the learning rate during training.
Figure 3 Each point is average three repeated experiments. We stop training when the training loss is small than 0.2.
21

---

C.3 Experimental exploration of gen"
In this section, our aim is to investigate the conditions under which gen" (Jr) as 0. Since directly calculating the difference (Jr) Rg (Jr) is challenging. concentrate the upper bound
value (Jr) + (R))))
We conduct the experiment using difar10-51 dataset and fe-tanh network. following the setting of paper [9]. Cifarl0-5k[9] is subset of cifar dataset. Building upon the work of [1], we compute the Relative Progress Ratio (RP) and Test Relative Progress Ratio (TRP) throughout the training process. We initially consider the case of gradient descent. The definitions of RP and TRP for gradient descent follows:
RP(J,) & Fs(Ju+1) (J.
(50)
11 (Jst)ll
TR.( Fs (J++1) - (J.) (V, (VF
(51)
Therefore, we have:
T
T-1
Fs(Jo) + (J.(J) Fs(Jt-1)) - Fs(Jo) (
Σ
(Je - Jc-1) (Fs(-
t=
t=
[Fs(J+)) Fs((J--)) -J. Jt-1) (
(52)
Σ [(Fs(J,) 7
= Σ (
Following the same way, we have:
T-1
(J) + Σ (Fs (J.
-Fs
Σ (J. J.-1) VF
(53)
T Σ
Combining Equation (52) and Equation (53), we have:
gen" (JT))
Σ Wh [(1 (T ( (P (54)
T
Therefore, if we have for all (J.) -1 and TRP(J.) -1, then |gen nL (Jr) ~ 0.
From Figure we find that in stable regime, where the sharpness is below the 2
" we have TRP
RP -1 Under small learning rate, the gradient descent doesn't 't enter the regime of edge of stability and we have TRP ~ RP ~ -1 during whole training process and (Jn" R 0.
Next, consider the case of Stochastic Gradient Descent (SGD). Due the stochastic estimation of the gradient, we need to rely on some approximations. Let X represent the weights after the t-epoch and i-th iteration of training. We assume constant learning rate n for SGD. The gradient approximated as follows:
B (Fs(s R [(x. Xt+1) n
B n
(X:(X:),
(55)
22

---

Drant
2000
00/
8000
10/00
10:00
6000
1000
30000
1000
6000
18:00
20:00
6:80
100E
K000
thornees
17 = 0.01
77 = 0.05
Figure 4: Exploration of gen" agen"/( (JT) on Gradient deseent. Experiments is conducted on cifar lifar10-s 0055k dataset with eross entropy loss. The blue dash line fourth row denotes 2. Gradient descent enter the EoS regime when the sharpness is above 2. Both RP and TRP have values around -1 when sharpness below the
17"
and we appximate Fss (Xt) as:
(56)
Therefore, have:
RP(X.) ((F((X,+1) - FX(),))
(57)
Xt+1 Xell
Fsy (X++1) (Xi)
TRP(X.) R (X+ Xt+1) Fs:
(58)
2000
180
800
2000
1000
Papeen
300
2000
Rer 0.01
1ay = 0.05
Bay 0.1
Figure 5: Exploration of (JT) on SGD case. Here, the effective learning rate is defined as (JT) nef 2 n1. We still have (Jn" R 0 under small learning rate.
calculated the effect learning rate for SGD as Mef A n.. Figure 5 shows that the conclusions of SGD similar GD, except that the conditions of entering EoS are different.
23

---

Table 4: Comparison of trajectory based generalization bounds. Only our proposed method can
apply to the SGD with rich trajectory related information.
Method
Conditions
TRT
Nikolakakis et al. [25)
Gradient Descent, Ne S { S.S 3. 5.9-mooth
Ei Ih Ex [VV
SXI
Neu al. [24]
smooth, [WW] [F](w))]] i v. f(+) subguassian distribution
VTT T
Park et al. [27]
Weak Lipschitz contimuity, Piecewise 3 3mmsmothh, [() is bounded,
Ours
Small I Learning Rate, [.VF((w) ) S FsW))
J [dFa(Je) 1
D Other Related Work
This part compares the works that is not listed in Table 2. Table 4 gives other trajectory based general- ization bounds. [25] is a stability based work designed mainly for generalization of gradient descent. It removes the Lipschitz assumption, and replaced by the term Σ/= '/t Σ [V 2: 12 in the generalization bounds. This helps enrich the trajectory information in the bounds. The limitation of this work is that can only apply to the gradient descent and it is hard to extend to the stochastic gradient descent. Neu et al. [24] adapt the information- therettiall generalization bound to the stochas- tic gradient descent. The Theorem in Neu et al. [24] contains rich information about the learning trajectory, but most is about F (w), which is unavailable for us. Therefore, we mainly consider the result of Corollary 2 in Neu et al. [24], which removes the term F. (w) by the assumption listed in Table 4. For this Collorary, the remained information within trajectory is merely the TTn2². Althouth Neu et al. [24] dosen't It require the assumption of small learning rate, the bound contains the dimension of model, which is large for deep neural network. Compared with these work, proposed method has advantage in that it can both reveal rich information about learning trajectory and applied stochastic gradient descent.
Chandramoorthy et al. [8] analyzes the generalization behavior based on statistical algorithmic stability. The proposed generalization bound can be applied into algorithms that don't 't converge. Let (6) be the dataset obtained by replace zi in S with another sample z! draw from distribu- tion μ. The generalization bound relies on the stability measure m - s f()+(S,))
T E f(J,)S(), z)]l= 2, E [n]]- We don't directly compare with this method because the calculation of m relies ((1) which contains sample outside of S. Therefore, treat this result as intermediate results. More assumption is needed to remove this dependence of the information about the unseen samples, i.e., the samples outside set S.
E Effect of Learning Rate and Stochastic Noise
In this part, we want to analyze how learning rate and the stochastic noise jointly affect our pro- posed generalization bound. Specifically, denote Pe(w) the distribution of the J, during the
training with multiple training steps. Following the work [12], we consider the SDE function as an approximation, which shown as below:
dw FWW(W)d + (TC
(59)
The SDE can be regarded as the continuous counterpart of Equation(3) when sets the distribution of noise term e' in Equation(3) as Gaussian distribution. The influence of the noise e on Pe (w) is shown in the following theorem.
Theorem E.1. When the updating of the weight w follows Equation (59), the covariance matrix C is hessian matrix of function with scalar output, then we have:
d
Op((w) Ø
Σ
0 [Fs(W)).(w) - 7 Tr(C(w)) + C(w)V w log(p, (w) )) (w)]. (60)
Ow:
dampling factor
Remark E.2. Previous studies [45, 32, 12] tell that the covariance matrix C is proximately equal to the hessian matrix of the loss function with respect to the parameters of DNN. Thus, the above condition that the covariance matrix C' is a hessian matrix of function with scalar output is easy to be satisfied. (w) enlarge the probability of parameters being
Formula (60) contains three parts. The item Fs( (w() p (p(w)) located in the parameter space with low Fs(w). VTr(C(w)) and C(w) V (og(p((w)) ususally
24

---

contradict with each other. VTr(C(w)) enlarge the probability of parameters being located in the parameter space with low (w)) value, while C(w)V,, log(p, (w)) serves as a damping factor to prevent the probability from concentrating on a small space. Therefore, setting larger learning rate gives stronger force for the weight to the area with lower (r(C(w)) values. According to Equation we also have lower E(w). As result, large learning rate causes a small lower bound in Theorem 3.6
Proof. Based the condition described above, can infer that C(w) VVG(w), where G function with a scalar output.
We first prove that V .C(()= = V [r)) as below:
V C(w)ls V VVG(w)];
δ a a
Σ Sw; Ow; 3mg
G(w)
a a
(61)
G(w)
Ow,
Ow, Ow:
0 Tr(C(w))-
du,
So far, infer that V C VT((C.. According to Pokker-Planck equation( (26]), have:
@pe(w)
a [VF)())
a
a
[C(w)p:(w))
Ow:
2"
Owi
1=1
θ Ow:
Σ Owi
[VFD(W)p(()]]+
log
2"
VFD(W)p:(w)
2" V C(w) + Vow)V
Ow:
VFD(W)p:(w)
2" V (T(((w)) + (w)
dwi
(62)
Therefore, the theorem is proven.
25


Reviews:
[{"review_id": "RWtWIXCRty", "reviewer": "Reviewer_tZu2", "summary": "This paper studies the connection between the learning trajectories of DNNs and their generalization when optimized using SGD. Its main contribution is that it provides a good perspective for generalization error analysis by studying the contribution of the learning trajectory. Based on their analysis of the learning trajectory, a new generalization bound is provided for DNNs.", "questions": "1.\tCan the authors give an analysis and description of how tight the proposed generalization error bound is? Under what conditions does the generalization error inequality in Theorem 3.6 take the equal sign? Besides, how does the learning rate scheduler affect generalization error?\n2.\tEquation (11) in Corollary 3.8 is confusing. In this formula, both the integral of the variable t and the sum of t are included, which makes it unclear to the reader that the author regards the learning trajectory as a continuous variable (maybe the reason is that the learning rate is assumed to be sufficiently small?), or treat the trajectory as a discrete variable?\n3.\tCan the author describe in detail the insights Theorem 3.6 and Corollary 3.8 bring to the reader? What insights can these theorems bring to researchers about the optimization of neural network algorithms?\n4.\tCan the authors describe their experiments more specifically? For example, a more specific description of the neural network model used for different datasets.\n5.\tWhy didn't the author show the test accuracy of the trained neural network model on different datasets? Can the test accuracy be put in an appendix to show that the experimentally obtained accuracy is reasonable or acceptable?\n6.\tIs the proposed theorem (generalization error bound) also suitable for NLP tasks? The supporting material provided by the author contains the relevant code of WikiText2, but the relevant results do not seem to be shown in the paper. Can the authors show experimental results on the WikiText2 dataset?\n7.\tAuthors need to correct the full text. In some sentences, there is a missing space between the content of the paper and the index of the reference, such as \"experiments[9, 13] have\" in line 40 of the paper. Besides, Equation 38 is incomplete.\n8.\tWhy \\Delta FS (Jt)- \\Delta FS(Jt) (line 293 of the paper) can be used to approximate the generalization error? It is different from the generalization error in formula (10). What is the author's reason for using it instead of generalization error in Equation (10) in the experiments?\n9.\tThe symbols of L2 norm in the paper are not unified. Some formulas do have punctuation.\n", "limitations": "The authors describe their limitation as their method requiring small learning rates. How to eliminate this assumption is a direction worth studying in the future. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "On the whole, the theoretical analysis perspective and ideas of this paper have a certain value for the theoretical research work of deep neural networks. The main strengths are:\n1. It provides a perspective from the learning trajectory for the theoretical analysis of deep neural networks.\n2. The proposed generalization error bound track changes in adjustments of learning rate and noise level.\n", "weaknesses": "1.\tIt is unknown how tight the generalization error bounds given in the paper are. Furthermore, the impact of commonly used learning rate schedulers (e.g., exponential decay schedulers) on generalization error bounds has not been adequately analyzed.\n2.\tThe description of the insight of the theorem is not detailed enough. For example, the insight that Theorem 3.6 can bring to the reader is not presented in detail. In addition, what insights can Corollary 3.8 bring to readers?\n3.\tThe description of the experiment in the paper is not detailed enough. For example, the neural network models used for Cifar-100 and SVHN are not indicated.\n4.\tThe experiments done were not extensive enough. I'm curious to know whether the proposed theorem is also applicable to other commonly used neural network structures like ResNet, not just VGG.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Question 1 (Weakness 1): We provide a comparison on a toy dataset due to the challenges in calculating the bound, and the results are displayed in the overall response. Although we cannot currently determine the exact conditions for the equal sign, we will continue to investigate. Identifying such conditions is a difficult problem, even for widely accepted stability-based generalization bounds. In Appendix A.6, we analyze the influence of the learning rate on the generalization bound. A larger learning rate benefits generalization by pushing $\\mathbf{J_t}$ into a position where $\\operatorname{Tr}(\\Sigma(\\mathbf{J_t}))$ is small. In this regard, exponential decay schedulers may improve generalization compared to using a small learning rate throughout the training process. An initially larger learning rate can result in a relatively small $\\operatorname{Tr}(\\Sigma(\\mathbf{J_t}))$. In the later phase, even if $\\operatorname{Tr}(\\Sigma(\\mathbf{J_t}))$ becomes large due to the small learning rate, the term $d F_S(\\mathbf{J_t})$ is small at this stage. As a result, it will reduce the term $- 2 \\gamma' \\mathbb{V}_m \\mathbb{E}\\int _t \\frac{d F_S(\\mathbf{J_t})}{\\sqrt{n}} \\sqrt{1+\\frac{\\operatorname{Tr}(\\Sigma(\\mathbf{J_t}))}{\\Vert \\nabla F_S(\\mathbf{J_t}) \\Vert _ 2^2}}$ in our bound.\n\n\n\nQuestion 2: The trajectory is considered as a discrete variable due to the nature of the update method (SGD). The integral is merely a simplification of the symbol. We denote this in line 136. Indeed, it is confusing to use these two types of symbols. To unify them in the paper, we will rewrite\n$\\gamma' \\mathbb{V}_m M_4^2 \\sqrt{ \\mathbb{E} \\sum_t \\frac{1}{n \\beta^2  (t+1)^4} \\left(1+\\frac{\\operatorname{Tr}(\\Sigma(\\mathbf{J_t}))}{\\| \\nabla F_S(\\mathbf{J_t}) \\|_2^2}\\right)} $ in collary 3.8 as $\\gamma' \\mathbb{V}_m M_4^2 \\sqrt{ \\mathbb{E} \\int \\frac{1}{n \\beta^2  (t+1)^4} \\left(1+\\frac{\\operatorname{Tr}(\\Sigma(\\mathbf{J_t}))}{\\| \\nabla F_S(\\mathbf{J_t}) \\|_2^2}\\right) \\mathrm{d}t}$.\n\nQuestion 3 (Weakness 2): The primary insights of Theorem 3.6 are described in Section 1.1.1. Our generalization bound reveals the relationship between the \"Bias of Training Set,\" \"Diversity of Training Set,\" \"Complexity of Learning Trajectory,\" and generalization error. The \"complexity of learning trajectory\" is associated with the gradient norm, gradient covariance, and training loss during the learning trajectory. The placement of Section 1.1.1 is not ideal, so we plan to move its content to a position closer to Theorem 3.6 to make it more accessible to readers. Regarding Corollary 3.8, we aim to provide a comparison between our proposed method and the stability-based method by presenting the bound with the learning rate schedule used by the stability-based method. We will add the comparison result from question 1 in the overall response near this corollary.\n\nQuestion 4: The architecture used for CIFAR-10, CIFAR-100, and SVHN is VGG13. We will include these descriptions in Appendix A.5.\n\nQuestion 5 (Weakness 3): The test accuracy for CIFAR-10, CIFAR-100, and SVHN are 87.64%, 55.08%, and 92.80%, respectively. Thank you for pointing this out. We will add these details to the Appendix.\n\nQuestion 6 (Weakness 4): The results on WikiText-2 are provided in Figure C of the PDF of the overall response. Additionally, we have conducted experiments with ResNet-18 on CIFAR-10, which can be found in Figure B of the overall response. We will include these results in the Appendix. The training config of ResNet18 on Cifar10 is the same as the experiment of VGG. For the config on WikiText2, the Transformer is 2 layers, 2 head and 200 embedding size. The model trained using SGD with learning rate 0.001, batch size 20\n\nQuestion 7: Thanks for point out. I will fix it in the new version of paper.\n\nQuestion 8: Apologies for the unclear statement in the paper. Our focus is on analyzing the value of $F_{\\mu}(\\mathbf{J_T}) - F_S(\\mathbf{J_T})$. However, we cannot calculate $F_{\\mu}(\\mathbf{J_T})$ due to the unknown distribution $\\mu$. One approach to address this issue is to design an unbiased estimate in the experiment. Since $\\mathbf{J_t}$ is dependent on $S$, we can sample a new dataset $S'$, making $\\mathbf{J_t}$ independent of $S'$. Based on this, we have $\\mathbb{E}F_{S'}(\\mathbf{J_T}) = F_{\\mu}(\\mathbf{J_T})$, which implies that $F_{S'}(\\mathbf{J_T})$ is an unbiased estimate of $F_{\\mu}(\\mathbf{J_T})$. This aligns with the practical wisdom of using the gap between the performance on the test set and the performance on the training set as a measure for generalization behavior.\n\nQuestion 9: Thank you for bringing this to our attention. Indeed, there are some issues with the symbols in the paper. We will address and fix these errors."}, {"review_id": "vfjeMw8Zvt", "reviewer": "Reviewer_dakY", "summary": "This work proposed a novel generalisation error bound which takes the learning trajectory of neural networks into consideration.\nInstead of focusing on the post-trained neural networks, the proposed bound bases on the parameter updates during the learning of the neural networks.\nThe core proof of the bound relies on the assumption 3.4, as well as decomposing the difference between the updates on the true generative distribution and the training instances, i.e. $F\\_{\\mu}(\\mathbf{J}\\_{T}) - F\\_{S}(\\mathbf{J}\\_{T})$, into a linear part $\\mbox{gen}^{lin}(\\mathbf{J}\\_{T})$ and non-linear part $\\mbox{gen}^{nl}(\\mathbf{J}\\_{T})$.\nWith reasonable assumptions, the authors bound the non-linear part with $\\mathcal{O}(\\eta\\_{m})$.\nRegarding the upper bound of the linear part, it relies on the other assumptions introduced in Section 3.2.\n", "questions": "My questions are pretty much the same as the weakness I listed above.\n\nThe only suggestion I want to raise is to move Section 1.1 after Section 3.2.", "limitations": "Yes, the authors have explicitly and clearly pointed out the limitations of this work.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The main result, i.e. a generalisation bound that takes the learning trajectory information, is novel and interesting.\nPractical exploration also demonstrates that the learning trajectory information helps neural networks to obtain better generalisation performance.\nFor example, knowledge distillation [1] can be considered a method to update the original labels to incorporate the predictions from the teacher model.\nThere also exists works that directly modify the labels with learning trajectory information, e.g. [2], and they have shown that the learning trajectory information are indeed helpful for generalisation.\nSo, a theoretical work that can bound the generalisation errors with learning trajectory information is interesting to the community.\n\n2. The proof is well sketched, thus relatively straightforward to follow: not only the sketch from line 227 to line 238, also the formal proof in Appendix A.1.\n\n3. The authors have also provided empirical evidence to show that the core assumption 3.4 hold, as well as how the generalisation error varies during the learning of neural networks.\n\n4. The overall structure of the paper is clear, and the structure is also well-organised (excluding Section 1, my reasons are given below).\n\n[1] Hinton, Geoffrey, Oriol Vinyals, and Jeff Dean. \"Distilling the knowledge in a neural network.\" arXiv preprint arXiv:1503.02531 (2015).\n[2] Ren, Yi, Shangmin Guo, and Danica J. Sutherland. \"Better supervisory signals by observing learning paths.\" arXiv preprint arXiv:2203.02485 (2022).", "weaknesses": "### Major\n\n1. **Displaying the main result at the beginning**:\nThis is not a concern about the technical side of this work, but rather a comprehensibility issue.\nWithout reading Section 3, the meanings of the notations in Equation 1 are mysterious, and I cannot interpret it.\nFrom my perspective, the Section 1.1 does hinder the comprehensibility of this work.\n\n2. **Lack of necessary details of the experiments in Section 4**:\nAfter reading the supplementary materials, there are still some necessary details of the experiments in Section 4 I didn't find.\nFor example, in line 284, the authors specify $S'$ to be another data set.\nHowever, since the data distribution of CIFAR is unknown, I can only assume that both $S$ and $S'$ are subsets of CIFAR, whereas I'm not certain about that.\nTo fully reproduce these experiments, more details are necessary.\n\n3. **Experiment in line 271 on Gaussian data**:\nThe authors omit $\\gamma'$ due to the lack of the true data distribution in line 271.\nThis can be relatively easily solved by sampling training instances from a Gaussian distribution.\n\n### Minor\n\n1. The first $w$ in line 148 is not bold.\n\n2. The font size of all figures is too small.\n(I understand that the authors may want to save some space, but the texts are really too small to read.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback. Based on your suggestions, we propose the following improvements to the paper:\n\nMajor 1: Indeed, Section 1.1.1 may hinder the paper's understandability. We plan to move Section 1.1.1 to a location after Theorem 3.6 and Remark 3.7.\n\nMajor 2: We will provide additional details about the experiments. The $S$ and $S'$ represent the training set and test set of the dataset, respectively. We will include this information to enhance the paper's readability.\n\nMajor 3: We appreciate your advice. Conducting experiments on a Gaussian dataset is an excellent suggestion. We designed the experiments and discovered that the $\\gamma$ is linearly related to the generalization error, which aligns with our experimental findings. Additionally, we compared the tightness of our bound with previous stability-based bounds. The results are presented in the overall response.\n\nMinor 1: We will make the necessary revisions.\n\nMinor 2: Thank you for pointing this out. Indeed, the font is too small. We will modify all images in the figures to resemble the format used in Figure BC in the PDF of the overall response."}, {"review_id": "4mwxkGPbO1", "reviewer": "Reviewer_JRdZ", "summary": "This paper present a new generation bound with moderate realistic assumptions that incorporate new information from gradients and trajectory of learning. ", "questions": "see above. ", "limitations": "The paper address their limitation in their paper well. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1 - the paper is well written and easy to follow.\n2 - the paper does a great job comparing their results with previous literature on this topic. \n3 - their experiments shows a promising result. ", "weaknesses": "1- experiments are limited. This paper can definitely benefit from more experiments, however due to page limit, it is too much to ask. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review the paper.\n\nWe have included additional experiments in the overall response, featuring a toy dataset to compare tightness, as well as experiments on ResNet18 with CIFAR-10 and WikiText-2 datasets."}, {"review_id": "V2GfF0G6rs", "reviewer": "Reviewer_t8yd", "summary": "This paper studies the generalization of a general function class under the (S)GD algorithm with minimal assumptions.\nSpecifically, it gives a generalization (upper) bound based on several training trajectory characters during training: variance of the gradients, gradient norm,  training loss values and the learning rate. \nNumerical experiments are conducted to verify the assumption and the generalization bound.", "questions": "For Theorem 3.6, the optimal generalization bound one can get is $\\mathcal{O}(\\eta_m)$, where $\\eta_m = \\max_t \\eta_t$. \nThis means that to get a non-vacuous bound, $\\eta_m$ should decay to zero with respect to the sample size $n$, but the sample size dependent learning rate is not common in the practical setting, so why there is such a term?\nCompared with the uniform-stability based generalization bound $\\mathcal{O}\\(\\frac{\\sum_{t=1}^T \\eta_t}{n}\\)$ in *Hardt eta al.*,  we can see that as long as $T = o(n)$, constant step-size SGD is provably to having a non-vacuous bound, so what is the gap here?", "limitations": "This paper proposes a framework on the generalization analysis for a wide class of function, but more works are still needed to be done to show the superiority of this new method.\n\nAs mentioned in the weakness part, I think this paper can benefit from the following two aspects:\n* more asymptotic analysis on the generalization bound in common machine learning settings, such as linear regression, kernel regression and overparmeterized neural networks.\n* since the bound in this paper does not require that $f$ is a neural network model, I think it would be more convincing if the authors could add some examples to show the generalization of other non neural network models, such as gradient boosting.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The paper is written clearly and the ideas have been presented in the proper order.\n\n* This paper studies the generalization for a very general class function that not only includes for neural network models, which can provide more insights in other non neural network based scenarios.", "weaknesses": "The major weakness is that this paper does not go into detail about studying the asymptotic order of the generalization bound in Theorem 3.6. \nTo show the superiority of this new proposed method in this paper, it is very important to provide (at least) the asymptotic analysis on the generalization bound with respect to the sample size $n$.\n\nFor example, in which case does the model benign overfitting (generalization gap goes to zero as $n \\xrightarrow{} \\infty$)?\nCan this new generalization bound cover (or outperform) previous bounds in some specific settings, e.g., linear regression, kernel regression, or overparameterization neural networks?\n\nIn the current version of this paper, even though it provides a general framework for generalization analysis, I cannot see the potentiality of this generalization bound.\n\n---\n\nAnother weakness is for the Assumption 3.4. \nIn fact, this assumption is trivially hold for finite set $\\mathrm{w}$ because we can always take the supremum $\\sup_{w \\in \\mathrm{w}} \\|\\nabla F_{\\mu}(w)\\|$ and the infimum $\\inf_{w \\in \\mathrm{w}} \\|\\nabla F_{S}(w)\\|$ and then get $\\gamma$.\nHowever, once the set $\\mathrm{w}$ contains a point that is a stationary point of the empirical risk, i.e., $\\|\\nabla F_{S}(w^*)\\| = 0$ for some $w^* \\in \\mathrm{w}$, then Assumption 3.4 implies that $w^*$ is also a stationary point of the population risk $F_{\\mu}(w)$, which is a very restrictive property as the data distribution matters. \nIt is also shown in the Figure 1 that as the training loss goes to zero (epoch increases), the $\\tilde{\\gamma}_t$ may diverge.\n\nThat is to say, the relaxed Assumption A.7 is more reasonable.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time. The two points you raised (1. Analysis on machine learning settings and 2. Analysis on non-neural network models) are indeed interesting and beneficial for a deeper understanding of our proposed method.\n\n## Assumption:\n\nThe primary objective of our paper is to examine the generalization behavior of overparameterized neural networks trained using GD/SGD, which is a challenging issue. In the case of overparameterized neural networks, reaching a stationary point is a rare occurrence, as shown in reference [41] and validated in Figure 1. For general machine learning cases, this is a strong assumption. Consequently, we introduce the relaxed Assumption A.7 and **its corresponding bound (Theorem A.8)** in the Appendix.\n\n## Question:  \n\n1. For the bound in Hardt eta al, the batch size used in their proof is 1. This means that the $T$ is usually large in setting. If we use the learning rate as fixed $\\eta$ and training for $e$ epochs. Then $\\mathcal{O}(\\frac{\\sum_{t=1}^T \\eta_t}{n})=\\mathcal{O}(\\frac{e \\times n \\times  \\eta}{n})=\\mathcal{O}(e  \\eta )$. Actually we have $\\lim \\limits_{n\\to \\infty} \\mathcal{O}(\\eta_m)=0$ (Proposition A.1 in The appendix.). However, we cannot figure out a concrete form like $\\mathcal{O}(\\frac{1}{n^c})$. This is a limitation of our current work. \n\n\n2. The analysis of $n$. We will first analysis the dependent of $n$ for $\\mathbb{V}$. The $\\mathbb{V}$ is calculated as $\\mathbb{V}(\\mathbf{w})=\\frac{\\Vert \\nabla F_S(\\mathbf{w})\\Vert}{\\mathbb{E} _ {U \\subset S} \\Vert \\frac{|U|}{n} \\nabla F_U(\\mathbf{w})-\\frac{n-|U|}{n}\\nabla F_{S/U}(\\mathbf{w}) \\Vert}$. Obvious, the gradient of individual sample is unrelated to the sample size $n$. And $\\vert U \\vert \\sim n$. Therefore, $ \\mathbb{V}=\\mathcal{O}(1)$. Similarly, we have $\\mathbb{E} \\int_t \\frac{d F_S(\\mathbf{J_t})}{\\sqrt{n}} \\sqrt{1+\\frac{\\operatorname{Tr}(\\Sigma(\\mathbf{J_t}))}{\\| \\nabla F_S(\\mathbf{J_t}) \\|_2^2}}=\\mathcal{O}(\\frac{1}{\\sqrt{n}}) $.  As for the \n $\\mathcal{O}(\\eta_m)$ term in Theorem 3.6, we have $\\lim \\limits _ {n \\to \\infty} \\mathcal{O}(\\eta_m) =0$ according to Proposition A.1. We simply assume that $ \\mathcal{O}(\\eta_m)=\\mathcal{O}(\\frac{1}{n^c})$. Therefore, our bound has $\\mathcal{O}(\\frac{1}{n^{\\text{min}\\lbrace 0.5,c \\rbrace}})$\n\n## Two suggestions:\n\n#### 1 Linear Regression. \n\nWe observe that our methods in linear regression tend to degenerate to a form resembling the traditional Rademacher complexity method. This is understandable, as our approach originates from Rademacher complexity and is more adept at analyzing complex neural networks.\n\nWe denote the data as: $z_i \\triangleq \\lbrace x_i,y_i \\rbrace$ and $S=\\lbrace z_i \\rbrace_{i=1}^n$, \nwhere the $x_i \\in \\mathbb{R}^{in}$ is the data and $y_i \\in \\mathbb{R}$ is the corresponding label.\nAnd the matrix of all data and labels are denoted as $\\mathbf{x}\\in \\mathbb{R}^{in \\times n}$, $\\mathbf{y}\\in \\mathbb{R}^n$.\nThe function $f(\\cdot)$ is defined as $f(\\mathbf{w},z_i)=\\frac{1}{2}( y_i -\\mathbf{w}^{\\mathrm{T}} x_i ) ^2$. \nTherefore, we have $\\nabla f(\\mathbf{w},z_i)=(\\mathbf{w}^{\\mathrm{T}}x_i-y_i)x_i$. The weights after $t$-th update as $\\mathbf{w} _ t$.\n\nThe generalization error of our method has the form $\\mathcal{O}(\\int _ t  \\frac{\\Vert \\mathrm{d} \\mathbf{w} _ t \\Vert}{\\sqrt{n}}  \\sqrt{F _ S(\\mathbf{w} _ t) \\text{max} _ i(\\Vert x _ i\\Vert)}$. \n\nFor the Rademacher complexity, we have $\\mathcal{O}(\\frac{\\Vert \\mathbf{w}_T \\Vert}{\\sqrt{n}} \\sqrt{\\text{max}_t F_S(\\mathbf{w}_t)\\text{Tr}(\\frac{1}{n}\\mathbf{x}^{\\mathrm{T}} \\mathbf{x})})$.\n \nTherefore, on the linear regression, our bound is similar to that of Rademacher complexity.\n\n#### 2 Gradient boosting\n\nGradient boosting is **beyond the scope of our paper**, as it focuses on function space while our method requires updates in weight space. Nonetheless, we offer a preliminary study using our framework.\n\n$F^{(j)}: \\mathbb{R}^d \\to \\mathbb{R}$ is the ensemble of $j$ models. $l: \\mathbb{R} \\times \\mathbb{R} \\to \\mathbb{R} _ {+}$ is the loss function. We consider a distant measure $d(\\cdot,\\cdot)$. We choose the function $f^{(j)}:\\mathbb{R}^d \\to \\mathbb{R}$ from function space $\\mathcal{F}^{(j)}$. We have $F^{(j)}=\\sum _ {k=0}^{k=j-1} \\delta _ k f^{(k)}$. We denotes $S=\\lbrace(x _ i,y _ i)\\rbrace _ {i=1}^n$ as our training data and  $S' = \\lbrace( x' _ i,y' _ i)\\rbrace _ {i=1}^n$ as the test data. We simplify the notation that $F^{(j)} _ i=F^{(j)}(x _ i)$, $F'^{(j)} _ i=F'^{(j)}(x' _ i)$, $f^{(j)} _ i=f^{(j)}(x _ i)$ and $f'^{(j)} _ i=f'^{(j)}(x' _ i)$. In the gradient boosting, we choose the $f^{(j)}$ such that $\\sum _ i \\frac{1}{n} d(f^{(j)} _ i,-\\nabla l(F^{(j)} _ i,y _ i))$ is small. We define $\\mathcal{L}=\\sum _ {i,j} \\frac{1}{n} \\delta _ j d(f^{(j)} _ i,-\\nabla l(F^{(j)} _ i,y _ i))$ and $\\mathcal{L'}=\\sum _ {i,j} \\frac{1}{n} \\delta _ j d(f'^{(j)} _ i,-\\nabla l(F'^{(j)} _ i,y' _ i))$. Here we focus on analyzing the difference between $\\mathcal{L}$ and $\\mathcal{L}'$.\n\nWe denote $g_i(f^{(j)})=g_i^{+1}(f^{(j)})=d(f^{(j)}_i,-\\nabla l(F^{(j)}_i,y_i))$ and $g'_i(f^{(j)})=g_i^{-1}(f^{(j)})=d(f'^{(j)}_i,-\\nabla l(F'^{(j)}_i,y'_i))$.\n\nWe denfine two complexity measure of function space $\\mathcal{F}$ based the distance measure: $R^a _ S(\\mathcal{F})=\\mathbb{E} _ {\\sigma} \\sup _ {f \\in \\mathcal{F}} \\frac{1}{n} \\sum _ {i=1}^n\\sigma _ i g _ i $ and $R^b _ S(\\mathcal{F})=\\mathbb{E} _ {S,k}  \\inf _ {f \\in \\mathcal{F}} \\frac{1}{n} \\sum _ {i,\\sigma_i=-1} d(f _ i,f _ k)$.\nIf samples of $S$ and $S'$ follow a same distribution, we have the following conclusion:\n\n$$\\mathbb{E}[\\mathcal{L'}-\\mathcal{L}] < 2 \\sum_j  \\delta_j( R_S^a(\\mathcal{F}^{(j)})+R_S^b(\\mathcal{F}^{(j)})) + 2\\sum_{j} \\delta_j \\mathbb{E} d(\\nabla l(F_i^{(j)},y_i),\\nabla l(F'^{(j)}_i,y'_i)) + \\epsilon $$\n\nThe first term is the complexity of the function space and the second term is to measure how the $F^{(j)}$ depends on the set $S$. The dependence exsits because the choose of $f^{(j)}$ is related to the $S$. \n\n\n\n\n"}, {"review_id": "23QKkgI9YA", "reviewer": "Reviewer_pZNy", "summary": "The paper introduces a novel generalization bound that incorporates trajectory information, aimed at providing deeper insights than existing methods on generalization at different points during training. The key idea is to analyze the increase in generalization error at each point in training by linearizing the network. Experimental results confirm the effectiveness of the proposed approach in capturing generalization error throughout the training process, even with adjustments to learning rates and label noise levels.", "questions": "Is there some way to at least estimate $\\gamma'$ and $\\mathbb{V}_m$?\n\nRelatedly, how does the tightness of the bounds produced by this method compare to other practical generalization bounds?", "limitations": "Limitations are adequately addressed; the authors devote an entire section of the paper to limitations. No negative potential societal impacts.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "**Originality**\nAs far as I am aware, this is the first generalization bound of its kind; I'm not aware of any other that uses the approach used in this paper. A major strength of the paper is that the derivation of the bound and bound itself are simple to understand, but still seem relatively powerful.\n\n**Quality**\nThe theory in this paper appears solid. Experiments are also conducted well; testing on VGG13 trained on CIFAR-10 is a good choice. The authors experimentally validate the theoretical assumptions, which also is a major plus. I also view the fact that the bounds predict empirical generalization performance in Figure 3 as a major strength.\n\n**Clarity**\nGenerally speaking, the paper is understandable.\n\n**Significance**\nThe paper seems to take a relatively different approach than other works deriving generalization bounds for neural networks. Thus, I view the main significance of the paper as providing a new set of theoretical techniques. This paper is likely to be of significance to the field of developing practical generalization bounds for neural networks.", "weaknesses": "In my mind, the main drawback of the paper is that it's hard to establish the significance of the proven results without comparing the numerical generalization bounds implied by Theorem 3.6 with those proved by prior work. Table 2 is helpful, but it would also be good to establish the relative tightness of these bounds numerically if possible. Also, as the authors point out, the small learning rate assumption is restrictive, but also in line with some prior work.\n\nAlso, here are several issues with the writing throughout the paper. For instance, \n- \"Even though, the function space of DNN is large,\" in the introduction\n- \"studying the generalization of DNNs by exploring property of SGD,\" in related work\n- \" the value of concerning\" in section 3\n- \"restricttion\" in section 3\n- \"popular gradient\" in section 3\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your positive comment. \n\nIn the overall responce, we device a toy dataset to compare our results with previous works. We will check and fix the typos in the paper."}]

Author rebuttal:
We thank ACs, SACs, PCs, and reviewers for the efforts and time spent in handling our paper.

Figures in the pdf. A: Result of toy dataset for Question 2 below.  B: Results of ResNet18 on Cifar10. C: Results of Transformer on WikiText2.

The training config of ResNet18 on Cifar10 is the same as the experiment of VGG. For the config on WikiText2,  the Transformer is 2 layers, 2 head and 200 embedding size. The model trained using SGD with learning rate 0.001, batch size 20.


Question 1: Tightness of the proposed bound

In a toy dataset setting, we compare our generalization bound with stability-based methods. We choose a toy dataset because calculating $\beta$ (under the $\beta$-smooth assumption) and $L$ (under the $L$-Lipschitz assumption) in stability-based work, as well as the values of $\mathcal{V}$ and $\gamma$ in our proposed bound, is challenging. Additionally, stability-based methods require a batch size of 1. In the following, we discuss the construction of the toy dataset used to compare the tightness of the generalization bounds.

 The training data is $X_{tr}=\lbrace x_i \rbrace_{i=1}^n$. All the data $x_i$ is sampled from Guassian distribution $\mathcal{N}(0,\mathbf{I}_d)$. 

Sampling $\tilde{\mathbf{w}} \sim \mathcal{N}(0,\mathbf{I}_d)$,the ground truth is generated by $y_i=1 \ \ \text{if} \ \ \tilde{\mathbf{w}}^{\mathrm{T}} x_i>0 \ \ \text{else} \ \ 0$.

 The weights for learning is denoted as $\mathbf{w}$. The predict $\tilde{y}$ is calculated as $\tilde{y}_i =\mathbf{w}^{\mathrm{T}}x_i $.

 The loss for a simple data point is $l_i=\left\Vert y_i- \mathbf{w}^{\mathrm{T}}x_i \right\Vert_2$. The training loss is $\mathcal{L}=\sum_{i=1}^n l_i$. The test data is $X_{te}=\lbrace x'_i \rbrace$, where $x'_i= \tilde{x}'_i$ and $\tilde{x}'_i \sim \mathcal{N}(0,\mathbf{I}_d)$. 

We evaluate the tightness of our bound by comparing our results with those in references [11] and [42] from the original paper. We set the learning rate as $\eta_t=\frac{1}{\beta t}$. Our reasons for comparing with these two papers are: 1. [11] is a representative study, 2. Both papers have theorems using a learning rate setting of $\eta_t=\mathcal{O}(\frac{1}{t})$, which aligns with Corollary 3.8 in our paper, and 3. They do not assume convexity. We use 100 samples for training and 1,000 samples for evaluation. The model is trained using SGD for 200 epochs. The generalization bounds we compare include Corollary 3.8 from our paper, Theorem 3.12 from [11], and Theorem 5 from [42].

Our results are:

Gen Error | Ours | [11] | [42] 
|-------|-----|------|------|
1.49 | 3.62| 4.04 | 4417.00  



Our bound is tighter under this setting. The reason for the value of [42] is large is because that our and [11] has dependent on $\frac{L^2}{\beta}$, while [42] depends on $L^2$. $L$ and $\beta$ are usually large numbers. (Note that in corollary 3.8 of our works, we can replace $M_2$ and $M_4$ with $L$ because $M_2\leq L$ and $M_4 \leq L$ and $c$ in Theorem 3.12 of [11] is equal to $\frac{1}{\beta}$ with our setting.).

Question 2. Effect of $\gamma$ 

Under the aforementioned settings, we modify the variance of test data samples such that $\tilde{x}'_i \sim \mathcal{N}(0,\kappa \mathbf{I}_d)$. By using different values of $\kappa$, we obtain various values of $\gamma$ and discover a linear correlation between $\gamma$ and generalization error (Figure A in the rebuttal PDF). This finding is consistent with our theorem.

[11] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient 352 descent. In International conference on machine learning, pages 1225–1234. PMLR, 2016.

[41] J. Zhang, H. Li, S. Sra, and A. Jadbabaie. Neural network weights do not converge to stationary points: An invariant measure perspective. In International Conference on Machine Learning, pages 26330–26346. PMLR, 2022.

[42] Y. Zhang, W. Zhang, S. Bald, V. Pingali, C. Chen, and M. Goswami. Stability of sgd: Tightness analysis and improved bounds. In Uncertainty in Artificial Intelligence, pages 2364–2373. PMLR, 2022
   

Meta-review: This paper studies a novel generalization bound based on the complexity of the function space that can be explored during the training process. The primary motivation is to consider the trajectory information during training and use that to get tighter generalization results. The reviewers questioned whether the bound improves upon classical stability-based generalization results. The authors used a toy example to demonstrate the improvement. Reviewers also asked whether the bound can show the convergence of the generalization error when the number of samples goes to infinity. The author’s rebuttal also addresses this by analyzing the asymptotic rate of the generalization error.
Decision: Accept (poster)