Data-Dependent Generalization Bounds for Neural Networks with ReLU
Authors: Harsh Pandey
Amitabha Bagchi
Srikanta J. Bedathur
Arindam Bhattacharya
Venue: Accepted by TMLR ()

Abstract: We try to establish that one of the correct data-dependent quantities to look at while trying to prove generalization bounds, even for overparameterized neural networks, are the gradients encountered by stochastic gradient descent while training the model. If these are small, then the model generalizes. To make this conclusion rigorous, we weaken the notion of uniform stability of a learning algorithm in a probabilistic way by positing the notion of almost sure (a.s.) support stability and showing that algorithms that have this form of stability have generalization error tending to 0 as the training set size increases. Further, we show that for Stochastic Gradient Descent to be a.s. support stable we only need the loss function to be a.s. locally Lipschitz and locally Smooth at the training points, thereby showing low generalization error with weaker conditions than have been used in the literature. We then show that Neural Networks with ReLU activation and a doubly differentiable loss function possess these properties. Our notion of stability is the first data-dependent notion to be able to show good generalization bounds for non-convex functions with learning rates strictly slower than $1/t$ at the $t$-th step. Finally, we present experimental evidence to validate our theoretical results.

Published in Transactions on Machine Learning Research (02/2024)
Data-Dependent Generalization Bounds for Neural Networks with ReLU
Harsh Pandey
bothorsh.@gmall.co com
Deportment of Computer Science
IT Delhi
New Delhi, India
Amitabha Bagchi
bagchi@cse.
Deportment of Computer Science
ITT Delhi
New Delhi, India
Srikanta Bedathur
WikantaaAcse.eee
Department of Computer Science
IT Delhi
New Delhi, India
Arindam Bhattacharya
Deportment of Computer Science
ITT Delhi
New Delhi, India
Reviewed on OpenReview: https: // openreview. net/ net/ forum? id- mHVGTeHHVKD
Abstract
We try to establish that one of the correct data-dependent quantities to look at while trying to prove generalization bounds, even for overparameterized neural networks, are the gradients encountered by stochastic gradient descent while training the model. If these are small, then the model generalizes. To make this conclusion rigorous, we weaken the notion of uniform stability of learning algorithm in probabilistic way by positing the notion of almost (a.s.) support stability and showing that algorithms that have this form of stability have generalization error tending to 0 as the training set size increases. Further, we show that for Stochastic Gradient Descent to be a.s. support stable we only need the loss function to be a.s. locally Lipschitz and locally Smooth at the training points, thereby showing low generalization error with weaker conditions than have been used in the literature. We then show that Neural Networks with ReLU activation and a doubly differentiable loss function possess these properties. Our notion of stability the first data-dependent notion to be able to show good generalization bounds for non-convex functions with learning rates strictly slower than 1/1 at the 1-th step. Finally, we present experimental evidence lo validate our theoretical results.
1 Introduction
Deep neural networks are known to perform well on unseen data (test data), c.f. e.g. Jin et al. (0020)), ), but theoretical explanations of this behaviour are still unsatisfactory. Under the assumption that the error on the training set (empirical error) is low, studying the gap between the empirical error and the population error is one route to investigating why this performance good. In this paper we look the gap between the population error (risk) and empirical error (empirical risk) [ Following works like Bousquet Elissceff (2002), the term generalization error for this quantity. Chatterjee & Zielinski (2022) articulated the

---

Published in Transactions on Machine Learning Research (02/2024)
Paper
Number of Epochs
Step Size
Neural Network Type
Key Assumptions
Hardt et al. 2016
O( 1/2
O(1/t)
No restrictions
No data-dependence.
Kuzborskij &
epoch
O(1/t)
No restrictions
Bounded Hessian
Lampert (0018)
Lei & Ying (020
O(1)
O(1/t)
No restrictions
Strongly convex objective but non convex loss function
Charles &
((m)
0(1)
l-layered networks with leaky ReLU or linear
PL and QG growth conditions
Papailiopoulos
2018
Lei et al.
(2022)
(mm)
0(1)
1-layered networks with smooth activation functions
Smooth loss function, Bound in expectation, lower bound on number of parameters
ta 0
Our Paper
O(log m)
O 1/t pl..
No restrictions
Bounded Spectral Complexity
c E (0.1)
Table 1: Recent related works addressing the question of generalization error and stability of neural networks in comparison to the results in this paper.
main quostion follows: why (or when) do neural networks generalize well when they have sufficient capacity to memorize their brwining sel? Although a number of formalisms have been used in an atlempt to derive
theoretical bounds on the generalization error, e.g., VC dimension (Vapnik 1998), Rademacher complexity [Bartlett & Mendelson 2003) and uniform stability (Bousquct & Elissooffi 2002) but, as /Zhang et al. (2017) showed, of these lail to resolve the conundrun thrown up by overly parameterized deep neural networks. One clear failing identified in /Zhang et al. (2017) was that many of these notions were dataa-nndependen. A simple counterexample provided by Zhang al. (2017) clearly established that data-independent notion was bound to fail to distinguish between data distributions
which deep NNs will generalize well and those on which they will not. Further, the paper also raised doubis on the possibility of proving so-called uniform convergence bounds for generalization error, iee. bounds that were independent of the the size of the training data. These doubts were concretized by Nagarajan & Kolter (2019) who constructed examples for which the best possible algorithms were shown to not have uniform convergence bounds. We do not directly address the issue of uniform convergence in this paper, instead focusing on the question that Chatterjee & Zielinski (2022) formulated follows: For neural network, is there a property of the dataset that controls the generalization eтror (assuming the size of the training set, architecture, learning rate, etc are held fized) ? We give affirmative answer to this question in one direction: We identify the data-dependent quantities, namely SMSTrG, WCTrG and TeG and show that if these are bounded, we can guarantec the generalization of neural nelworks. We show that the bound on these quantities depends on the difference between the initial value and optimal value the loss function and also do experiments to validate our results. Our techniques are able rigorously handle nonlincaritics like ReLU and work for non-convex loss functions, and this holds for classification case. We also allow for learning rate that asymptotically strictly slower than 0(1/t) the (-th step of SGD. All this holds for any bounded value loss function, which is twice differentiable.
2

---

Published in Transactions on Machine Learning Research (02/2024)
Name
Shorthand
Mathematical Notation
Worst Case Training Gradient Second Moment of Step Training Gradient Test Gradient Training Smoothness Constant
WCT:G
Lg
SMSTrG
0g
TeG
Lg
Kg
Table 2: These are the important random variables which are used in the paper. All these are defined in Section 4.1.1
Our work is within the theoretical paradigm of stability. We asked the question, Is there an appropriale version of stobility that is flezible enough to incorporate dataset properties and can also adapt to most neural networksy In a partial answer to this question, we introduce a notion called almost sure (a.s.) support stability which is data-dependent probabilistic weakening of uniform stability. Following the suggestions made by Zhang et al. (2017), data-dependent notions of stability were defined in (Kuzborskij & Lampert, 2018 Definition 2) and (Lei & Ying, 2020, Definition 4) as well. However, a.s. support stability is a more useful notion on three counts: it can handle SGD learning rates that are strictly slower than 0(1/t), its initial learning rate is much higher, and, while these past works bound generalization error in expectation, a.s. support stability can be used to show high probability bounds on generalization error. But, over and above these technical benefits, our main contribution here is the identification of the dala-dependent quantities as a key indicator of generalization. Which in turn connects the generalization of neural networks to the difference of initial and optimal loss values. A brief description of recent related works are summarized in table [
Earlier works for showing generalization (like Kuzborskij Lampert (2018)) have a global Lipschitz constant. and show generalization using some other parameter. More recent works like Lei & Ying (2020) try completely remove the role of Lipschitz constants by taking some other assumptions the loss function. We argue that the gradients are the correct quantities to look at for generalization.
the structure or
We show generalization bounds for neural networks via two paths. One path uses Worst Case Training Gradient (WCTrG) which is the the worst-case gradient across all steps of SGD and Test Gradient (TeG) which is a gradient computed at the final parameter vector computed by the training. The other path uses the Second Moment of Step Training Gradient (SMSTrG) which related the second moment of the gradients encountered during training and TeG. Using some results from Bottou et al. (2018) we show a bound SMSTrG in terms of the difference between the initial loss and optimal loss values. This directly bounds the generalization error of neural networks in terms of this difference and makes this bound more usable. We show examples of cases that take ad advantage of our bounds. We perform experiments to validate the results and also empirically show that for random label case, WCTrG grows unboundedly, and so we can't guarantee generalization in this case, which is as expected.
We note that although we can say that when the data-dependent quantitics are small, our results guarantee good generalization performance, we do not establish that this condition is necessary.
In particular, our contributions are:
In Section B we define new notion of stability called a.s. support stability and show in Theorem 3.2 that algorithms with a.s. support stability o(1/ log" m) have generalization error tending to O as m + oo where m is the size of the training set.
In Section we first define the data-dependent quantities. We run SGD for 7 epochs with the slowest learning rate of og/t! /g/tt--(r.m)) where p(T, m) = O(log log logm//log: log m))) for appropriate value of og- For reasonable values of m and 7, this marks significant slowing down of the learning rate from ((1/t). We use two different ways to show a.s. support stability of SGD and we also show bound on SMSTrG based on SGD properties.
Tn Section 4.1 define the data-dependent quantities and show their existence.
3

---

Published in Transactions on Machine Learning Research (02/2024)
In Section
4.2
show a.s. support stability of SGD using WCTrG and TeG. We show this for learning
rate of on/ 1 ((rmm)) where p(T, m) < 1 for reasonable size of training set (m) and epochs (r) proportional
to log(m).
In Section 4.3 we show a.s. support stability of SGD using SMSTIG and TeG where T = 1. This also enjoys the small learning rate of ag/tl-p(rmm)
In Section 1.4 we show a bound on SMSTrG based on properties of SGD and a very minor assumption (P1) as highlighted by Bottou et al. (2018). The main highlight of the bound on SMSTrG that this takes advantage of the fact that even for non-convex optimization the gradients of loss function decrease as shown by Bootoo al. (0018).
In Section 5 we combine results from Section g and f to show generalization error bound for neural
networks. We also translate these bound to the neural network setting. And show practical examples highlighting the advantages of our data-dependent constants.
In Section 5.1 using Section 4.2 we bound WCTrG by the spectral property (Proposition 5.3 and show generalization bounds based on these spoctral propertics.
In Section 5.2 using Sectoin and 1.4 we show generalization via SMSTrG and show bound on it which depends on the difference of initial loss and optimal loss values. The main advantage of this is that this is much more practical and easy to verify as compared to the spectral property.
Then, in Section we experimentally verify the results showing that the bounded condition holds and plot the generalization error. We also experimentally analyze the Test Gradient (TeG) for random labelling setting suggested by Zhang et al. (2018) and conclude the Test Gradient is actually not bounded and increases with the training set size. We relate this to the high variance of the loss function in random labelling case and hence provide an explanation of which this example cannot be proved incorrectly to generalize using our methods.
2 Related Work
Although NNs are known to generalize well in practice, many different theoretical approaches have been tried without satisfactorily explaining this phenomenon, c.f., Jii et al. (2020); Chatterjee & Zielinski (2022). We refer the reader the work of Jin et al. (2020) which presents concise taxonomy of these different theoretical approaches. Several works seek to understand what good theory of generalization should look like, c.f. KKwaguuhi et al. :017); Chatterjee & Zielinski (2022). Our own work falls within the paradign that seeks to use notions of algorithmic stability to bound generalization error that began with Vapnik & Chervonenkis [974] but gathered steam with the publication of the work by Bousquet & Elisseeff (2022).
The applicability of the algorithmic stability paradigm to the study of generalization error in NNs was brought to light by Hardt et al.] (2016), who showed that functions optimized via Stochastic Gradient Descent have the property of uniform stability defined by [ouuqquet & Elisseeff (2002), implying that NNs should also have this property. Subsequently, there was renewed interest in uniform stability, and sequence of papers emerged using improved probabilistic tools to give better generalization bounds for uniformly stable algorithms, e.g., Feldman & Vondrak (2018 2019a) and Bousquet et al. (020). Some other works, e.g. Klochkov & Zhivotovskiy (2021), took this line forward by focussing on the relationship of uniform stability with the excess risk. However, the work of Zhhng et al.
(2017) complicated the picture by pointing out examples where the theory suggests the opposite of what happens in practice. This led to two different. strands of research. In one thread, an attempt was made to either discover those cases where uniform stability fails (e.g. Charles& & Papailiopoulos (2018) or to show lower bounds on stability that ensure that uniform stability does not exist (e.g. [hhnng et al. (2022)). The other strand of research, category in which our work falls, focuses on weakening the notion of uniform stability, specifically by making it data-dependent, thereby following the suggestion made by /Zhang et al. (2017). (Kuzborskij & Lampert] 2018 Definition 2) defined "on-average stability" which is weaker than our definition of a.s. support stability. Consequently, their definition leads to a weaker in-expectation bound on the generalization error where the expectation is over the training set as well as the random choices of the algorithm. Our Theorem 3.2 on the other hand, provides sharp concentration bound on the choice of the training set..
[eii & Ying 2020 Definition 4)
4

---

Published in Transactions on Machine Learning Research (02/2024)
define "on-average model stability" that requires the average replace-one error over all the training points to be bounded in expectation. While their smoothness requirements are less stringent, the problem is that their generalization results are all relative to the optimal choice of the weight vector, which implies a high generalization error in case of carly stopping.
A key question the study of generalization in NNs is that of the possibility of proving uniform convergence bounds for cerm-bounded classes of NNs, a question that can be traced to Bartlett (1996). This question was answered negatively by Nagarajan & Kolter (2019) who showed that in general norm bounds deep networks show non-uniform growth, ie., they grow with the training set size. For further discussion on this question the reader is referred to Negrea et al. (2020a). Our current work is more focussed on identifying the relevant quantities that bound generalization error, postponing the question of the exact relationship of these quantities to the training set size to future study.
The role of the norm of gradients for bounding generalization error has been observed from a different angle by Negrea et al. (2020b) and also by Haghilam el al. (2020). Their work focuses on giving information--heorelii generalization bounds for Stochastic Gradient Langevin Dynamics (SGLD) and Langevin dynamics algorithm.
Although their setting and methods is different from ours, the general flavour is similar.
3 Almost Sure (a.s.) Support Stability and Generalization
In this section, we present a weakening of the notion of uniform stability defined by (Bousquet & Elisseell 2002, Definition 6) and show that exponential concentration bounds on the generalization error can be proved for learning algorithms that have this weaker form of stability.
3.1 Terminology
Let X' and y be the input and output spaces respectively. We assume have training set. S 2 of size where each point is chosen independently at random from unknown distribution D over Z C X x D. For = (I, y) E Z we will use the notation I2 to denote 2 and yz to denote Let R be the set of all finite strings on some finite alphabet, and let us call the elements of R decision strings and let us assume that there is some probability distribution D, according to which we will select r randomly from R. This random string abstracts the random choices of the algorithm. For example, in an NN trained with SGD it encapsulates the random initial parameter vector and the random permutation of the training set as seen by SGD. For an algorithm like Random Forest would abstract out the random points chosen to divide the space.
Further, let F be the set of all functions from X to y. In machine learning settings we typically compute a map from T x R to F. We will denote the function computed by this map as As,r. Since the choice of S and r are both random, As,r is effectively random function and can also be thought of as randomized algorithm.
Given a constant M O, we assume that we are given bounded loss function {:yx - [0, M). We define the risk of As,r as
R(As,)) = FIED
where the expectation is over the random choice of point according data distribution D. Note that the risk is a random variable since both S and are randomly chosen. The empirical risk of As.- is defined as
1 Σ
RA(Ast)
(12.)
S
ZES
We are interested in bounding the generalization error
R(As,)) - Re(As.))
(1)
When talking about SGD we omit and just use R(S.r) and R. (S, r) represent R(As,) and Re (As,))
respectively.
5

---

Published in Transactions on Machine Learning Research (02/2024)
About the loss function 1(:,)). When talk about the loss function we refer to the commonly used loss functions in machine learning, like cross-entropy, focal loss, mean squared error (for bounded inputs) etc. Our results are valid for any bounded value loss function which is doubly differentiable. In machine learning an implicit assumption is that the algorithm is able to successfully minimize the loss function chosen, i.c., a loss function used that can be minimized a reasonable value over a training set. We also work with this assumption.
3.2 A Weakening of Uniform Stability
Given S = (Zi...... Zm where all points are chosen randomly from D, we construct S' via replacing the i-th element of S by an independently generated element from D. To quote it formally we choose (Z14m..... 72m points such that all are chosen randomly from D such that they are independent from all points in S. For each E [m] we define
= = ..... Zi-1, Ziems Z441. Zm}
where [m] represents integer points from m..
Definition 3.1 (Almost Sure (a.s.) Support Stability). We say an algorithm As, has almost sure (0.8.) support stability 3 with respect to the loss function E(.,-) if for Zi...., Zzm chosen i.d. according to an unknown distribution defined over Z,
Vi [m] V2 E supp (D) E, [I.))s -
va)l SB
with probability 1 over the choice of points Zi,..., Zzm where Vi, Zi or in other words (Z),... Zzm} D2m
We note that this notion weakens the notion of uniform stability introduced by (Bousquet & Elisseeff 2002
Definition 6) by requiring the bound on the difference in losses to hold D almost everywhere. This probability is defined over the random choices of Zi...., Zzm Besides the condition the loss is required to hold only for those data points that lie in the support of D. These conditions make a.s. support stability a data-dependent quantity on the lines of the suggestion made by Zhang et al. (2017). We also observe that
a.s. support stability is comparable to but stronger than the hypothesis stability of Kearns & Ron 1999) as formulated by Bousquet & Elisseeff (2002).
While the quantification of 2, Lee, V2 supp (D) appears to be a very strong condition it is weakening of uniform stability. In (Bousquet. & Flisseeff 2002 Section 5) it was shown that uniform stability (which is Vz ~ D) holds for several classical machine learning algorithms like soft margin SVM, bounded SVM regression and regularized least square regression. Hence a.s. support stability also holds for these algorithms. As we will see ahead, the weakening helps us fulfil key technical requirements when it comes to the study of neural networks.
3.3 Exponential Convergence of Generalization Error
Almost Sure (a.s.) Support Stability can be used in place of uniform stability in conjunction with the techniques of (Feldman & Vondrak 2019a Theorem 1.1) to give guarantees on generalization error for algorithms that are symmetric in distribution. A function f(11,..., ((4 Zmm is called symmetric if f fæ for any permutation o But if we have function f which is not symmetric but the probability of choosing any permutation of a given set of elements is equal then we use the term symmetric in distribution to refer lo such a function along with the distribution by which its inputs are picked. In (Bousquet & Elisseeff 2002 Section 2.1) the term "symmetric algorithm" was used but it was potentially misleading since what they meant was symmetric in distribution in the sense that we have used it. Since SGD randomly permutes the training points it is clearly symmetric in distribution.
In particular, can derive the following theorem.
Theorem 3.2. Let As.r be an algorithm that is symmetric in distribution and has a.s. stability 3 with respect to the loss function ((.,)) such that O < (xAs,( y=) $ for all S 2m, for all r E R. and for all

---

Published in Transactions on Machine Learning Research (02/2024)
== (1)) Z. Then, there erists constant >> 0 independent of s.t. for any 2 1 and ö E (0,1), with probability 1 1-10 6,
m log 1/))
E. (R(S,r) (c) Sc [ (og((m) log
(
+
m
The constant e is independent. of m and, because our analysis is asymptotic in m, this sulficient for us.
Proof outline. We give a high-level outline here. Our proof extends the proof of Feldman and Vondrak ([eelmman & Vondrak 2019a Theorem 1.1)) to accommodate the generalization of McDiarmid's Lemma A.2 from (Combes] 2015 P Proposition 2). Feldman & Vondrak (2019b) used two steps to get a better generalization guarantee. The first step is range reduction, where the range of the loss function is reduced. For this, they define & new clipping function in Lemma 3.1 Feldman & Vondrak (2019a) which preserves uniform stability and hence it will also preserve a.s. support stability. They also use uniform stability in Lemma 3.2 Feldman & Vondrak (2019a) where they show the shifted and clipped function will still be stable which done by applying McDiarmid's inequality to B sensitive functions. Here use a modification of McDiarmid's inequality (Lemma A.2 given in Appendix [ to get bounds for a.s. support stability. The second step is dataset size reduction (as described in Section 3.3 Feldman & Vondrak (2019a)) which will remain the same for a.s. support stability as this only involves stating the result for a smaller dataset and the probability, and then laking a union bound. Therefore both steps of the argument given in Feldman & Vondrak (2019a) go through for a.s. support stability.
4 Almost Sure (a.s.) Support Stability of Stochastic Gradient Descent
In this section, we show how to bound the a.s. support stability of a model whose parameters are learned by performing Stochastic Gradient Descent (SGD) using a training set. We will see that the bounds on stability can be formulated in terms of the gradients encountered during training and the value of the gradient at the end of the training. Since these gradients are determined by both the training set and the random choices made by SGD, this scction shows that stability be understood not just by looking at the data distribution, but by going beyond that and looking more carefully al the training process.
This section is organized as follows:
Section 4.1 We define three quantities associated with SGD that will be used to bound a.s. support stability: Worst Case Training Gradient (WCTrG), the Test Gradient (TeG) and Second Moment of Step Training Gradient (SMSTrG). We will also show that these quantities are bounded under certain mild conditions in Section
Section 4.2
We will show bound on a.s. support stability that depends on WCT&G and TeG. This bound is weak in the sense that WCT& is related to the largest of the gradients encountered during training and strong in the sense that the stability bound decreases as m
Section 4.3
We will show bound on a.s. support stability that depends on SMSTrG and TeG for one epoch. This bound is stronger than the bound shown in Section 4.2 in the sense that SMSTrG is associated with averaging of the gradients encountered during training rather than the largest of the gradient. However, the bound is weaker in the sense that it decreases as m -1/2.
Section 4.4.
This section is devoted to making the bound presented in Section 4.3 more useable by bounding Second Moment of Step Training Gradient in terms of the initial and final values of the loss function.
Terminology. We assume that the learned function is parameterized by a vector w E R" for some n 2 1, i.c., we have some fixed function f R" x X + y. The training set is used learn a suitable parameter vector E R" such that the value f(w, .x)) a good estimate of ys for all 2 E Z. We assume that this value of un is learned by running SGD using training drawn from the unknown distribution. We will say that.
7

---

Published in Transactions on Machine Learning Research (02/2024)
the size of the training set is m, and the algorithm proceeds in epochs of steps each. The parameter vector at step i. is denoted by for 0 S / S m, where 7 is the total number of epochs during training.
To frame the learned function output by this algorithm in the terms defined in Section 3.1 the random decision string consists of the pair (Wo, π = (To..... ky-1)) which we also write as (Tiaa, Tp), i.e., the random initial parameter vector we (or Timit) from which SGD begins and the sequence
random permutations used the epochs. The weights encountered at step & using permutation will be represented wt, For the sake of brevity, except for Section 4.1.1 we omit the use of and only write w.
4.1 Some quantities associated with SGD gradients
4.1.1 Definitions
Definition 4.1. If II is the set of all permutations of S, then SGD as defined above has the following quantities associated with
1. Worst Case Training Gradient (WCTrG) L..
L max {
Ow flw, 2) |
Where the set A = UrEM (wi,,,..... Wrm-1 1, i.e. all the parameter vectors encountered across all time steps across all possible permutations of S. Ls max. which is a random variable depending on the choice of 5 and wo-
2. Training Smoothness Constant Ks.
If f'(w', ;20 w
K K
max w. EA? wfw
w/
Where the set = UreII (w........ w We will say that Ks = (axses(Ke,A)) Note that Ks is a random variable depending on the choice of S and wo-
3. Test Gradient (TeG) Lg.
[[[(w, 2) f(w', 2)1l || w'll
Lz.9
max
w,w EA?
Where the set A UrEIt- (Wrm,r) i.e. all parameter vectors encountered at the end of the training process across all possible permutation of S. We will say that L. = max ( Note that Lg is random variable depending on the choice of S and wn-
Second Moment of Step Training Gradient (SMSTrG) as- This is defined for T 1.
max WE
Fro s(w =)
m
Where the set A, Un (wr i.e. set of all possible parameter vectors encountered during training step of SGD across all permutations. We say that as max.es(oz). Note that as is random variable in S and wa.
Our stability analysis SGD will depend on these quantities. However, when we take this analysis and try apply it NNs with discontinuous activation functions like ReLU, Training Smoothness Constant and Test Gradient defined above are not guaranteed to be bounded. So, necessary to establish the conditions under which they bounded.

---

Published in Transactions on Machine Learning Research (02/2024)
4.1.2 Boundedness
We now present the property under which the quantities defined above will (almost surely) bounded.
Definition 4.2 (Almost surely Locally Parameter Lipschitzness of parametrized functions). parameterizod function ʃ R Z + I is said to be almost surely locally L-parameter Lápschilz w.r.t D if for a fixed TR" and for D there exist constants L > 0 and such that, with probability 1 (over the choice of
2); for all w' E R", l|w' - wwll implies
II =) f(w, 2) & L||w'' wnll-
We will use the abbreviation a.s. L-LPI. or simply a.8. LPL for a function that satisfies Definition 4.2 Since training is always run for a finite number steps it is easy to observe that if the loss function is a.s. LPL, then Lg and as are bounded..
If .t) satisfies Definition 4.2 we will call such function almost surely locally L-porameter Smooth or a.s. L-LPS for short. We now that these two properties imply the almost sure boundedness of the quantities defined in Section 4.1.1 The important insight is that if the function (or its gradient) is locally bounded, and, if we only look at this function at a finite number of points, we get a "global" property within this finite set of points. We state this as a lemma.
Lemma 4.3. 1f f: R" x Z + R is bounded and a.s. LI-LPL, and A is a finite subset of R", then with probability there an such that for every pair w, w' A, if ~ D, then
[1](w,=) f(w', ((ko,,z)) 2)]l s W|l - w'll,
The proof is in Appendix
Corollary 4.4. If R" z is a.s. L-LPL then Lg is almost surely bounded. Further, if f is a.s. K-LPS then Ks is almost surely bounded.
The corollary follows by observing that due to the finiteness of the training process, the parameters on which the slopes are computed in Definition 4.1 are all drawn from finite sets.
4.2 Almost Sure (a.s.) Support Stability of SGD with WC TG
We now work towards the a.s. support stability of SGD using WCTG and TeG. First, we state a theorem that bounds the replaco-one error of SGD up a cortain number of epochs. To make the theorem statement easier to read, we first separate out our assumptions.
S1. We are given a space Z X x y and probability distribution D defined over it. We have a parameterized loss function f R x Z R that is a.s. L,LPP w.r.t supp (D) and a.s. K,-LP w.r.t S.
S2. For training set S of size m for each i [m] chosen L.ddd according to D we run SGD on ʃ for т epochs with random decision string r. Parallelly, do the same for set St with the same set of random decision string For St, the i-th data point of S has been replaced by another data point z chosen from D independent of all other random choices.
S3. At step of SGD let the learning rate aa < (l-((m)) m) loglog Toggm and wo the parameter vectors obtained for the t-th step SGD while training with set and Si respectively.
Theorem 4.5. Given assumplions S1, S2 and S3, we have Li as WCTrG, by as TeG and Kg as Training Smoothness Constant. Let the random decision string r = (wo, mo), then with probability 1 over z we have,
E, [f([Wrmm21 2) f(w rm: 2)] 2 ag E, LsLy U(as, Ks, p(T, m))
(2)
(1- oggg m
where U(as, Ks, p(T, m)) s 1+ 1 and as ag 0, U Uao, Ks, p(T, m)) + +1+ p(r.m) p(T.m)
Ksao

---

Published in Transactions on Machine Learning Research (02/2024)
Here, the expectation is over for random variables Lg, Ly and Kg. Remember, the L.H.S. is still random variable in S and a.s. support stability is almost surely over this S.
Proof outline. The proof follows the lines of the argument presented by (Hardt et al. 2016 Theorem 3. 3.12) with the difference that we allow for a probabilistic relaxation of the smoothness conditions and more relaxed constraint on gradient bounds in line with our definition of a.s. stability. Also, note that we have to account for an expectation over the random string and that we have been able extend the argument to multiple epochs which was not possible in (Kuzborskij & Lampert 2018 Theorem 4). The complete proof of Theorem 1.5 is in Appendix B
Data-dependence with WCTrG and TeG. A key feature of the bound presented in equation 2 is that the dependence on the data is expressed through the data-dependent quantities WCTrG (Lş) and TeG (Lg)) The WCTrG depends on the gradients at training points and the replacement point z/1 which also picked from the data distribution, and TeG depends on the gradients of the trained network calculated at points from distribution. The advantage of splitting TeG and WCTrG instead of global bound that TeG could potentially be very small when the loss is converged as it's calculated at the end of training, And, WCTrG only depends on training points instead of the entire distribution.
Corollary 4.6. Given assumptions S1, S2 and S3, and under the condition that Ks is a constant, w.r.l. m, for all r, and Er [Lg is also constant w.r.t m, there is a constant с (0.1) that depends on ag and Ks such that the number of epochs T is at most c clog m epochs, the expectation of the generalization error of the algoritho taken over the random choices of the algorithm decreases as Ô (m miu(e.1/2)) (where tilde hides the logarithmic factors) with probability at least 1 1/m over the choice of the trainèng set if auKe, c clog2 < 1, p(1.m)
where =1 1-cllog2 2 p(.m)
Ks
Proof. Let us consider two cases. In the first case when > 1/2 (i.c. we get the usual rate 0(m-1/2)) this happens when ag < p(1.m) and we choose a small enough c. One the other hand for case where < 1/2 (i.e. rate of Ō(m=)) which allows for a larger learning rate p(l.m) 2Kg < ap < e(l.m)
2Kg
Ks (for small enough e). This clearly shows that a larger initial learning rate could be bad for generalization. It easy to check from Theorem 4.5 that with the conditions given in the stalement of Corollary [1. the learning algorithm has a.s.
support stability 8 where 3 is o(1/m²) if Ka + clog < 1. We can therefore apply Theorem 3.2 with pll.m
8=11 1/m to get the result.
4.3 Almost Sure (a.s.) Support Stability of SGD with SMSTrG
We present a more fine-grained analysis that provides an alternate bound of Theorem 4.5 by replacing the WCTrG (Worst Case Training Gradient), which was defined for all SGD steps, with the SMSTrG (Second Moment of Step Training Gradient). The significance of this is that this expected value could be substontially smaller than the worst case value in many cases, especially when the training converges rapidly from high value of the loss to a low value. We present the bounds using SMSTrG below.
Theorem 4.7. Given the assumplion S1, S2 and S3 for T 1, we have as as SMSTrG, Lg as TeG and Ks as Training Smoothness Constant. Let the random decision string r (wo, to), then with probability over z we have,
Lg oS (U Ks, m)
Fy [f(Wm, 2) - s f(w'm 2)] S Org Eun,
(3)
an flo m m
log log
Where (ao, Ks, m) 11+ Kg and as og 0 U'(o, Ks, m) + 1+
log(m)) Ing log m
Proof outline. The proof follows the proof of Theorem 4.5 but instead of using the WCT&G for bounding the gradients encountered at the step where the training points differ, we use the exact gradient at that step, i.e. f (w)o(()))) for every permutation To E II. Then, the proof continues till m steps. Finally, when taking the expectation over the permutations we apply Cauchy Schwarz to separate other random variables and obtain the SMSTrG (as). The complete proof of Theorem 4.7 is in Appendix B
10

---

Published in Transactions on Machine Learning Research (02/2024)
Although the bound in Theorem 4.7 looks weaker than the bound in Theorem 4.5 because of m term, the key part here is the use of SMSTrG instead of WCTrG. SMSTrG could potentially be lot smaller because it's averaged over the training steps. This will especially benefit the case when training converges fast and gradients quickly become small. We later in Section 4.4 show that we can bound SMSTrG by the decrease in loss during training under some very mild conditions assumption PI.
We now present the alternate version of Corollary 4.6 using Theorem 4.7
Corollary 4.8. Given assumption S1, S2 and S3 for =1, and under the condition that Kş is constant w.r.l. m for r (wu, and Ewo [Lg -asl is also constant w.r.l. m, the expectation of generalization error of algorilhm laken over the random choices of the algorillm decreases as O(m²) (were lilde hides the logarithmic factors) with probability at least 1 1/m over the choice of training set if 90 glogggooogooo m- 0.5, log log m
where = ao log log m
Proof. It's direct to see when we apply the conditions stated the above corollary Theorem the desired result.
4.7 wC get
4.4 Bound on SMSTrG
We now proceed to show the bound on SMSTrG (i.e. Second Moment of Step Training Gradient) along with the assumption required for the bound to hold. For this, it slightly to show a bound on the expectation of SMSTiG over S and wo- Although this is bound on expectation, we later show in the discussion of Section 5.2.2 that we can use this as a high probability bound. And this is sufficient because of the probabilistic form of a.s. support stability.
result from Bottou et al. (2018) and modify
First we define Fs(w)) = m Em f(w,, z,). Now, in order to bound the expectation of SMSTFG over the training set, we use the result from (Bottou et al. 2018 Theorem 4.10) and modify it to get the required bound. This theorem, combined with Assumption Pl, provides a bound on the expectation of SMSTIG over the training set (Corollary 4.10p. The bound is in terms of the initial and optimal (final) values of the loss function (and includes terms based on the learning rate), unless the initial loss is very bad, the bound will be useful. The theorem requires the following condition which is kind of version of bound the variance of the gradients encountered during training.
P1. (Assumption 4.3 (equation 4.9) of Bottou et al. (2018)). There exist constants M 2 0 and Mc 2 0 (independent of the size of the training set) such that,
[VS( 2]1? S M + MG [VFF((::)))
(4)
m SES
Theorem 4.9. Bollow el al., 2018 Theorem 4.10) Suppose we run SGD wader the assumplion that K is constant for all r and P1 holds, for M 2 0, MG 2 0. If wo is the initialization weight, w" is optimal value for (s( and Og is any diminishing step size then,
T Σ
T
a, [VF)( ((E[Fs(wo)] E [[Fs(w")I) E[Ks] M
Σ of
(5)
where Fs(un) = 1 - [w, =))
Now, using Theorem 4.9 and assumption P1 we can get a bound on the expectation of SMSTIG We state this in the next corollary.
Corollary 4.10. If we run SGD for 1 epoch under the assumption that Ks is constant for all r and P1 holds, for M 2 0, Ma 2 O, wi the initialization weight, w" is optimal value for Exes [f(w, =)], r = (wo, no) is the random string for SGD and an is any diminishing learning rate then,
T
Es [as] S M +2McE[((un) 2) -(w",, ,2)] + E[Ks] McM
Σ 1=0
(6)
OEp
11

---

Published in Transactions on Machine Learning Research (02/2024)
The proof of this theorem is in Appendix B B the end. The R.H.S of this equation is constant w.r.t. if Σ'= of is constant w.r.t. and in our analysis this is true (c.f. assumption S3). Hence, this corollary becomes useful for us since it shows that we can bound the expectation of SMSTrG under a mild assumption.
5 Neural Networks with ReLU Activation
We now proceed to show what the a.s. support stability bounds on SGD translates into for neural networks. This includes two generalivation bounds, one using WCTGG (i.e. Worst Case Training Gradient) in Section
5.1 and the other using SMSTrG (i.c. Second Moment of Step Training Gradient) in Section 5.2 We also emphasise on the conditions required for generalization bounds to hold and translate those conditions to more practical constraints.
5.1 Almost Sure (a.s.) Support Stability of Neural Networks with ReLU Activation: WCTrG
First, present the generalization bound of neural networks via support stability using WCTIG (Worst Case Training Gradient) in Section 5.1.1 We then, in Section 5.1.2 show the conditions required for the bounds to hold. We also present a discussion at the end highlighting an example where the actual data dimension is small, and our gradient bounds will be better.
5.1.1 Generalization Using WCTrG.
For of reading, we first state our assumptions and then, in Theorem 5.1 we present the bound.
N1. We have fully connected neural network with ReLU activation and 1 output neuron.
N2. The NN is trained on set S ~ D using SGD for epochs, where D is over Rd x y, such that y is countable and for each E y we get countable set {x E Id; Prp (lab(r) = #} > 0}. where lab(x) label of x.
N3. We have a doubly differentiable loss function with bounded first and second order derivatives and learning rate 04 on/ (g/t(l-p(rmm)), where p(T, m) log log and the data points of S and the log rgg
spectral norms of weight matrices explored by SGD are bounded
Theorem 5.1. If N1, N2 and N3 hold, then there is constant c 0 such that
E. (RR(S R.(S, ( ao E. (L Ulo, Ks Ks, m)) log(m)²
log(m)
20kg
m
m
with probubilily at lenst - 1-1/m 1/m, where Ulan Ks ((T. m((r.))
S
+ Kg and on
7
implies
U Uag, Ks. Ks.((T,m) + +1+ p(T,m)
The proof of the above thcorem is the end of Scction 5.1.2 before discussion. Note that for some e₁ log(m) epochs and with initial learning rale of ag such that aaKs + c1 log < 1, the RHS decreases increases. It is important to note that TeG (Ig) is the constant that depends on the actual distribution D and is calculated for a trained neural network (i.e. al Wym). This aligns with the notion that the nolw has reached a "good enough" minima, then the gradient values should be less; hence, this will show better generalization. Also, WCT&G (Ls) and Training Smoothness Constant (Ks) depend on the training set S. These are "global" over the data set in the sense that the expectation is for the entire training process over the (random) choice of initial parameters and the permutation that SGD chooses. For cases where SGD chooses a good set of initial parameters with good probability, these are likely to be small.
p[1m)
For Training Smoothness Constant (Ks), we are constrained in the sense that we need this value to be small throughout the training, even the beginning. Also is interesting to note that when Lss - and L.g -> the generalization error becomes zero, but when Kg O, have U U(a,, Ks, p(T, m)) 1 p(r.m)
mffr.m) which
12

---

Published in Transactions on Machine Learning Research (02/2024)
Although this still a decreasing function of m, this does not directly go to zero. This highlights that unlike Ls and Lgs just Kg 0 alone is insufficient for zero generalization error.
leads to generalization error behave like
log m
log me
The role of gradients in bounding generalization error that we identify has the same flavour, in a very different context, as the work (Negrea et al. 2020b Theorem 3.1) and (Haghifam et al. 2020 Theorem 4.2) where CitommttionThhorree
generalization bounds for SGLD (Stochastic Gradient Langevin Dynamics) are given in terms of gradient values of the loss function. Next in Scction 5..12 we first establish that the theory of a.s. support stability applies NNs under conditions specified, then we prove the Theorem 5. along with empirical validation.
5.1.2 Conditions on NNs for Generalization
The key to showing the a.s. support stability of NNs with ReLU is to establish that they are locally parameter-Lipschizz. and locally paramctor-smooth. First, we show the existence of these constants. Then we will show an upper bound under some reasonable assumptions and finally present an example in discussion.
Theorem 5.2. For every w R", doubly differentiable loss function, f R RR applied to the output of NN with ReLU activation is locally Ceemmeter-Liischen and locally poremeter-smooth for all x E Rd except for a set of measure 0.
Proof outline. The proof of this theorem is based the argument that for a given point of discontinuity exists at a given neuron if the input a lies in the set of solutions to a family of equations, i.c., in lower Lemma 1) and can be
dimensional subspace of Rdd This proof is an adaption of an idea of (Milne) 2019
found in Appendix C.2
Theorem 5.2 begs the question: How large are these WCT&G, TeG and Training Smoothness Constant? We provide some general bounds that can be improved for specific archilectures:
Proposition 5.3. Suppose we have a fully connected NN of depth H 1, with ReLU activation at the inner nodes. Then, if the spectral norms of weight matrices are bounded for every layer i.e., [|W'llo is bounded Vi E [H) and the size of each layer be fla...., ,,. and the distribution of dataset is normalized with || then,
H
Lg S
ll x A(M, wy
(7)
H
Ks S
II | A(M,W)
(8)
where
" A(M,W) Σ
|
1w1-1133
[/ |
where (hh element of matrir M (L, and where (I,),, is a matric such that (p, g)th Note that equation 7 holds for both WCT&G (Ls) and TeG (Lg).
element is M'(L,,, = w u+ 1) (1-1)
w 9,
The proof of the proposition is in Appendix C.2 Note that it's possible to give a tighter bound for the above theorem by not bounding the product of weight matrices (which we do after equation 19 in Appendix), but we keep the above equation because of its clarity. The bounds on these should be compared to the bounds given the context of Rademacher complexity by (Bartlett et al. 2017 Equation 1.2) and Golowich al. (2018). Our bound is related to the spectral complexity and can potentially be independent of the size of the network. We are now ready to prove our main theorem.
13

---

Published in Transactions on Machine Learning Research (02/2024)
Proof of Theorem 5.1 Theorem 5.2 tells that NN with ReLU activations is locally parameter- Lipschittt and locally parameter-smooth. From Proposition 5.3 we see that the boundedness of the first. and second derivatives of the loss function and the boundedness of the spectral norm of weight matrices and data points ensures that the gradient bound and smoothness constants associated with the NN's training are bounded w.r.t. m. With all these in place, we can apply Theorem 4.5 to get the a.s. support stability followed by Theorem 3.2 to get the desired result.
Discussion: An example showing the benefits of data-dependent gradient bounds. In general, data-dependent gradients (WCT&G and TeG) can be much smaller than the global Lipschitz constant of the space from which the data might appear. There are probably many scenarios in which this can be demonstrated, but we turn to well-appreciated scenario: data set that has much smaller dimensionality than the space in which it is embedded. We will now argue that in such scenarios, data-dependent gradients (WCTrG and TeG) can be significantly smaller.
Suppose we have data as x E R2, but the actual dimension of the data is D < d, a situation that is often seen in many cases, for example, image data. For simplicity of presentations, we assume that cach data point has 2i....,22 2D non-zero and the remaining coordinates are O. The arguments we make can be made even without this assumption by considering the data points with coordinates based on their projection onto basis of the subspace they are taken from.
Suppose we have neural network with 1 hidden layer of d1 neurons and a single output layer. Let W E Rd xd and 2 E Rixd1 be the weights of 1st and 2nd layer respectively and use w (1) to represent i, weight of
(th layer. For simplicity, let the output the neural network O(w, x) = w2W'z, Now, assuming MSE loss, we calculate the gradients and show that the effective upper bound of this could be smaller because of the fact that our WCT&G and TeG are caleulated only from S and supp(D). This under the assumption that the weights are upper bounded by some quantity B1. We will also assume that all data points have been re-scaled so that their norm is at most. 1.
Thcorem 5.4. If the aboue conditions holds then have bound on l norm of the gradients of the parameler vector w as;
|V (w. < Bi di D(1 + D)
Proof of the Theorem 5.4 is in Appendix
Here, we see that we obtain a bound on the norm of the gradients that are related D, which significantly smaller than d, whereas in general, we can expect the norm of the gradients to be of the order of d even under the assumptions of bounded weights and rescaled data points.
Note that we show here the value of WCTrG (I.s) and TeG (Igg), but for generalization, we actually need Er [4s Lg] to be bounded. Using Cauchy-Schwarz inequality we could see that we need bound on just the expectation of square (or the second moment) of each term. This means that when we select the initial weight parameter vector wo, we need the boundedness constraints on weights only, which a fairly mild constraint.
5.2 Almost Sure (a.s.) Support Stability of Neural Networks with ReLU Activation: SMSTIG
This Section focuses on stating the generalization bound of neural networks via a.s. support stability using the SMSTrG (i.c. Second Moment of Step Training Gradient). It's already shown in Bottou et al. (2018) that even for non-convex cases, the gradients of SGD decrease as the training proceeds. But earlier analysis and even Section 5.1 could not use this fact. So, we use the SMSTIG (i.e. Second Moment of Step Training Gradient), which will help us exploit this fact and provide a generalization bound for NNs. In Section 5.2.2 present the proof and discuss the conditions under which our bound holds. We also present a real-world example highlighting the applicability of our results.
5.2.1 Generalization Using SMSTrG
We use the same conditions as defined in Section 5.1.1 Now, applying this to NNs and using SMSTrG, we get a generalization bound, which is alternate version of Theorem 5.1 for the 1-epoch case.
14

---

Published in Transactions on Machine Learning Research (02/2024)
Theorem 5.5. If N1, N2 and N3 hold there is constant such that for all i E [m]
log(m)2
log(m) m
E, r)), (S,r s a0 Ews [gg Ewo [os] (a,,, Ks, S)
+
m ( no Ky (log -1
log log
with probability at least 1- 1/mm where U U'as. Kg. m)) & 1+ Ka
and ag +0, 0, U' Ks m)
1+
log(m)
log log m
Note the presence of SMST&G (as) the R.H.S here opposed to WCT&G (Ls) in the statement of Theorem 5.1 We propose this is a much more practical quantity to bound. We have already shown in Section 4.4 an expectation bound on SMST&G by the difference between the initial and optimal values of the loss function.
5.2.2 Conditions NNs to Hold for Generalization
Proof outline of Theorem 5.5 Using Corollary 4.10 we already have a bound on expectation of SMSTrG.
So instead of Proposition 5.3 we use this Corollary to achieve the result. Although note that the result is in expectation over the training set, we can simply apply Markov inequality as done in the discussion after Theorem 5.6 to get a probability bound. This is sufficient because of the probabilistic form of a.s. support stability. Also, the bound on the expectation of SMSTrG required only assumption (P1), which is relatively mild assumption.
It's important to nole that, like in the previous case (Section 5.1.2. matrices to be bounded, but it's a difficult condition to ensure while training neural network. On the other hand, the bound on the expectation of SMSTrG depends on the difference between the initial and optimal loss values, which very easy to ensure and verify. This means we get reasonable bound unless we have a very bad initial loss. Moreover, the assumption P1 in Section 4.4 also intuitive as a very bad training point could badly affect the training, so bounding the variance of gradients (that too with respect the average of gradients) restricts such bad points to be present in the distribution.
required the spectral norm of weight
We now move on to show the applicability of our bound for SMSTrG.
Applicability in Classification with Two Layer Neural Network. We now use Corollary 1.10 to establish generalization bound for the case of two-class classification with a two-layer Neural Network. For simplicity of exposition, we have assumed that the data points are taken from R², We fully specify the problem through the following assumptions:
Discussion:
X1. We have two class classification (Y = {-1,1}) in 2 dimension (ar = [x1, such that for expectations of centers we have [xily= = 1] E. [zrly = 1] 2 and E. [z] ly -1] = E. [xelly -1] -1, for
second moment for constant 0 have E [ E [ = o² and also for constant μlp 0 E| E [|=2|] Mp.
X2. We use a single hidden layer ferw-forward neural network, with as hidden layer size. Its parameters are initialized from why = (0, 1). The total number of parameter values are n = 2k + k. For a loss function f(w,, = y - O (,,, where O x) is the output of the neural network, VS(w, =) denotes the j-th partial derivative of function f and w whis be the associated weight. Let as be any diminishing step size at step t of SGD.
(!)
X3. We assume the ratio of absolute values of the weights of the Neural Network are bounded by where B >>1 1.
Theorem 5.6. If X1,X2,X3 hold, for r= (wo, To) we have,
16B* x² (T + 4ko² Hp))
Es.wo [os] <
(9)
(B 1)
15

---

Published in Transactions on Machine Learning Research (02/2024)
60
100
50
Empirical max
Empirical max
80
40
WCTrG
60
WCTrG
30
Training Smoothness constant
Training Smoothness constant
40
20
20
10
5000
10000 15000
20000
5000
10000
15000
20000
Number of Datapoints
Number of Datapoints
(a) MNIST
(b) Fashion
Figure 1: Experiment 1, Maximum of the Worst Case Training Gradient (WCTrG) and Training Smoothness Constant at every p 20) interval of updates of SGD (we plot both the running average and the highest value found so far). Notice that these constants have a clear upper bound throughout the training process.
The proof of this theorem is in Appendix probability bound. Assuming R.H.S of above is B", so we will have,
C.3
Now we can directly use Markov inequality to get high
16B o2 log m (ke + 4130 (o2pmp))
( log m
Prs
Ewg [os]
B - 1)²T
Since the distance between the centers of the two classes is fixed at 2, the bound presented here satisfies our intuition by showing that if the variances of the two classes are small, ie., the classes are well-separated, then the expectation SMSTrG is small, and hence the generalization bound of Theorem 5.5 small. It's important to note that since have a probability bound, we need apply the probabilistic version of support stability, although we show generalization only through a.s. support stability. The probability version can easily be derived using Theorem A.2 we discuss in Section 3.3
6 Experiments and Empirical Results
We now proceed to verify the results in real-world case empirically. First, perform the experiment to show that WCTrG, SMSTrG and TeG are bounded. We also show in the case of random labelling that our TeG are not bounded throughout the training, and hence, our results do not imply good generalization as expected.
6.1 Experimental Validation of Results
Here, we will experimentally show that the WCTGG (Ls), TeG (Lg) and Training Smoothness Constant (Ks) that we reasoned with are indoed bounded and that the theoretical upper bound that we derived for the generalization error of a neural network holds in practice. Note that Lgg bounded, then as will also be bounded. For simplicity in this experiment, we assume WCTrG to be good proxy for TeG (as general Lg Ls).
MNIST and FushionMNIST datasets. In both datasets, randomly selected 20, 000 training and 1, 000 test points. All experiments were conducted using fully connected feod forward neural network with a single hidden layer and ReLU activation. We train the model using SGD (batch size = 1), with cross-entropy loss, starting with randomly initialized weights. As suggested in our analysis we use a decreasing learning rate a, = = In each epoch, we consider a random permutation of the training set. WCTG and Training Smoothness Constant are computed by calculating the norm of gradients and Hessian across the training steps and taking their max.
Setup. For our experiments
16

---

Published in Transactions on Machine Learning Research (02/2024)
10a
10a
ceneralization error
via SMSTrG
Generalization error
via SMSTrG
10¹
via WCTrG
via WCTrG
Observed Generalization Error
Observed Generalization Error
10-1
10
10 3
10 2
10
10-7
5000
10000
15000
20000
5000
10000
15000
20000
Number of Datapoints
Number of Datapoints
(a) MNIST
(b) PashionMNIST
Figure 2: Experiment 2, comparison of empirical generalization error (in green) vs. thoorctical upper bound via WCT&G (in red) and via SMSTrG (in blue) with varying training set size for different. datasels.
Experiment 1. Our first experiment is aimed towards establishing that the WCTrG (Lg) and Training Smoothness Constant (Ks) values estimated using local values each step are bounded. Figure I summarizes the results of these experiments over MNIST and FashionMNIST datasets (ag- = 0.001). The plots contain the maximum of the gradients and smoothness values obtained after running each experiment 10 times with random weight initialization These results support our Theorem 5.2 since the upper bound values quickly stabilize and do not grow with the size of the training set in both datasets. Similarly, the bounded smoothness constant supports our constraint on the learning rate, ag I p(r.m) 8.1174 (MNIST)& & 12.5737 (FashionMNISTT) and Kg to be 58.185 (MNIST) and 102. 7096 (FashionMNISST),
lo Kg p(T,, m) = log 1 We find Ls to be
We now turn our attention to the experiment to support our main result, i.c., the empirical generalization error estimated using the validation set is upper bounded by our theoretical upper bound. We first split each datasct in a 20:1 ratio into training and validation sets and train the model at varying sizes of training sets. We empirically compule the generalization error at each training set size using the validation set. Figure 2 compares this empirical generalization error (in green) vs. the theoretical upper bound using WCTIG (in red) and using SMSTrG (in blue). From these results, we with the generalization error, thus empirically validating our reasoning. But clearly, the bound is not as tight as we would like it to be. We conjecture that this is because of the upper bounding of the U(.) term and the maximum which is taken across permutations of weights even for SMSTrG at t-th step.
Experiment 2.
that our bound decreases along
6.2 Random Labelling Case
In making their case against the applicability of uniform stability as tool for thcoretically establishing the good generalization properties of neural networks, Zhang al. (017) presented the following classification problem: Given points picked from Euclidean space using some well-behaved distribution, say a Gaussian, each point was assumed to have class label picked uniformly at random from finite set of labels independent of all other points. Clearly, any classification algorithm trained on a finite training set will have w(1) generalization error for this problem. We now demonstrate that our results do not imply good generalization for this problem. Specifically, we show empirically that the assumption of TeG (L,) being independent of m breaks in this case and this "constant" actually increases with m.
Setup. We pick images from the 0 and 1 label class of MNIST dataset. For random labelling case, we assign random labels to all the points. We then randomly sample a test set T (IT) = 50). We take a single hidden layer (128 neurons) fully connected neural network having ReLU activation in the hidden layer. We take the loss function as 1(g.v) v) Softmax(c- -. y) where e = 6. We use constant learning rate of 0.003, batch size of size 8.
17

---

Published in Transactions on Machine Learning Research (02/2024)
12
Test Gradient
60
Test Gradient
10-
50
40
30
250
500
750
1000 1250
250
500
750
1000
1250
Number of Datapoints
Number Datapoints
(a) Increasing Lg for random label MNIST
(b) Decreasing Ly for standard (non random) MNIST
Figure 3: Experiment 3, Test Gradient (Igg) plot as training set size increases.
Experiment The experiment proceeds by selecting initial random weights for a model say wo (we do this 10 times). Then for every initialization pick training set S from modified dataset (we do this for 5 times). Now for every training set, train the model either till accuracy is 98% or till 500 epochs whichever is reached first. Now we calculate the loss i.e. J'r, and the gradient (r, S, for all E T. For the TeG we do 4g ~ Vll fr, Sr =)]]}. In figure 3a we can clearly see that the TeG (Lg) scales as the size the training set (m) increases. On the contrary for the standard (non-random) datasct the TeG shows a decreasing trend with m see figure 3b Therefore we can expect that in the random labelling case, the upper bound in Theorem 5.1 becomes so large as to become vacuous.
Discussion. We note that the random labelling example has the property that the variance the choice of training sets of the loss of any algorithm, [Jr =)], is bound to be high. One possible direction for theoretically showing that this implies that the TeG are likely to be high is by using Poincare-type inequalities. This shows that the norm of the gradients of function of random vector lower bounded by the variance of the function. We do not pursue this direction further here, but we point out that may help develop a general theory for the limitations what can be learned using parametrized methods trained using gradient. descent methods.
7
Applicability and Conclusion
7.1 Discussion on the Applicability of Our Results
Removing the fully connectedness constraint. Although considered fully connected network for Theorem 5.2 and Proposition ion 5.3 our data-dependent quantities are independent of the architecture of Neural Networks. We only provide a bound on WCTGG and TeG using this. Note that even the bound on SMSTFG is independent of the architecture of the network. We conjecture that it can be applied to architectures like CNNs which have partially connected convolution layers with intermediate pooling, normalization and skip connections (e.g., ResNet, DenseNet, etc). Our work provides a framework which the study of the gradients obtained during training such networks can help guide our understanding of their generalization properties.
Adding regulorization terms to the loss function. Several popular regularizers, the ε regularizer being prominent example, are doubly differentiable and therefore Theorem 5.1 can be applied when such regularizers are used along with doubly differentiable loss function. Here as well mild addition for bound on derivative of regularization term in Theorem 5.3 may be able to help us prove results for this setting. However, it requires further investigation to establish such a result.
Activation functions aport from ReLU. We present a comprehensive treatment of ReLU activation but we conjecture that results not. restricted to this kind of activation. Non-linearities like max-pool can also be
18

---

Published in Transactions on Machine Learning Research (02/2024)
handled in our framework by proving that, like with RcLU, the points of discontimuity of such non-linearity also lie in a set of Lebesgue measure O. This provides a direction for future research in this area.
The case of multiple outputs Although we state the Theorem 5.1 and Theorem 5.5 for the case of a NN with a single output, it is not difficult to extend the technique to cover the case of multiple outputs. However, this requires a full treatment, which we postpone future work.
What about other distributions? The data-dependent gradient bounds (SMST&G, WCT&G and TeG) turn out to be the deciding factor of generalization error. However, analysis is limited to the bounds we derive for them. There is a requirement for a more fine-grained analysis of these gradient bounds and we believe that optimizing these data-dependent gradient bounds will be the right direction to proceed. This may be made possible by looking at the network structures, the data distribution and the training set in more detail. We hope that the polynomial characterization of the NN presented in Appendix C.1.2 will help this process. We conjecture that may be able to show that for certain distributions, the constants actually improve (decrease) w.r.t. training set size as the training proceeds, resulting in much slower decay of learning rate and this could lead to proof of a.s. support stability in these cases.
7.2 Conclusion
Using a.s. support stability, we derive the gencralization error bounds for neural networks. We most importantly identify the data-dependent quantities (WCT&G, SMSTrG, TeG) whose boundedness implies generalization of neural networks. We also show how to upper bound these quantities either in terms of spectral property or the initial loss and varionce of gradients of the neural network. So, this paper links the generalization of neural networks directly with the gradients and shows a guarantee of better generalization if we start with small (constant w.r.t. training size) initial value of loss function and descent (defined in assumption PI) value of variance of the gradient at each step of SGD. However, we feel it is possible to prove stronger and more widely applicable results in this framework than the ones we have presented here. Immediate lines of research are to apply our methods for CNNs and GNNs and to investigate what other architectures can be approached with our method and whether the gradient bounds play some significant role because of different network structure. Also, we do provide empirical evidence to support the example of the random labelling case but it lacks theoretically concrete statement.
References
Peter L. Bartlett. For valid generalization, the size of the weights is more important than the size of the network. In Proceedings of Advances in Newral Information Processing Systems, NewrIPS 1996, 1996.
Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. JMLR, 3:463 482, march 2003. ISSN 1532-4435.
Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normaalzze margin bounds for Neural Networks. In Proc. Advances in Newral Information Processing Systems 30, pp. 6240 6249, 2017.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for largo-scale machine learning. SIAM Rev., 60(2):2214487, 2018.
Olivier Bousquet and André Flisseeff. Stability and Generalization. J. Mach. Learn. Res., 2(Mar):499-522 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. Proc. Machine Learning Research, 125:1-17, 2020.
Zachary Charles and Dimitris Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Conference on Machine Learning, volume S0 of Proceedings of Machine Learning Research, pp. 745-754. PMLR, 10-15 Jul 2018. URL httpps:/pproceedngg.. mlr. wttpseswwww........eeeeeeeeeeeee ceta://eeecaaaaaa......e...
19

---

Published in Transactions on Machine Learning Research (02/2024)
Satrajit Chatterjee and Piotr Zielinski. On the generalization mystery in Deep Learning. arXiv:2203.10036, 2022.
Richard Combes. An extension of McDiarmid's inequality, 2015. URL
Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. In Advances in Neural Information Processing Systems, 2018
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thärty-Second Conference on Learning Theory, volume 99 of Proceedings of Mochine Learning Research, pp. 1270-1279. PMLR, 25 28 Jun 2019a. URL https::/pproceedee httppppo.eeennna.......raa/a////
mlr serres/v99/fele htt.99/feldmaa99.... html
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 1270-1279. PMLR, 25 28 Jun 2019b. URL section.
mlr arress/99/felddee 19a. html Supplementary
N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks (extended abstract). Proc. Machine Learning Research, 75:1-3, 2018.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M. Roy, and Gintare Karolina Dziugaite, Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms, 2020.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proceedings of The 35rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1225- 1234, New York, New York, USA, 20-22 Jun 2016. PMLR. URL httpps:/pproceddngs.. mlr. wwt.:/ssmm....rr.....m press/v48/ v hardt16.htm
Pongzhan Jin, Lu Lu, Yifa Tang, and George Em Karniadakis. Quantifying the gencralization error in deep learning in terms of data distribution and neural network smoothness. Neural Networks, 130:85-90 2020. ISSN 0893-6080. doi:
URL https://www.cceeneedree
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Gencralization in deep learning. CoRR, abs/1710.054668, 2017.
M. Kearns and D. Ron. Algorithmic stability and sanity-check bounds for leave-one-out cross- validation. Neural Computation, 1166):1427-1453, 1999.
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with convergence rate o11/n). In Advances in Newral Information Processing Systems, 2021.
Ija Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Mochine Learning Research, pp. 2815-2824. PMLR, 10-15 Jul 2018. URL html.
https://proceeddnng mlr pttpss//80//uzzoosskkkk..
Yunwen Lei and Yiming Ying. Fino-grained analysis of stability and generalization for stochastic gradient descent. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 5809-5819. PMI.R, 13-18 Jul 2020. URL https::/prooeeedingg wwwpeeddiiinn......eeeeeeeee mil..prees/v111/11e20.....
Yunwen Lei, Rong Jin, and Yiming Ying- Stability and generalization analysis of gradient methods for shallow neural networks. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Newral Information Processing Systems, 2022. URL. https:://openrreviir http::///ppppeeeeeeeeeeeeeerrn/a
GFCbL
20

---

Published in Transactions on Machine Learning Research (02/2024)
Tristan Milne. Piecewise strong convexity of neural networks. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d' Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Newral Information Processing Sys- tems, volume 32. Curran Associates, Inc., 2019. URL https://paperrs wnw.sniiiii............. mtpp..cc/paper//111//111 pdf.
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. In Proceedings of Advances in Neural Information Processing Systems, NewrIPS 2019, pp. 11611-11622, 2019. URL ittps://proceedingg. htt.://cggg..uauiigoocccc/p//ppp Abstract html
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel M. Roy. In defense of uniform convergence: general- ization via derandomization with an application to interpolating predictors. In Proceeding of ICML 2020, 2020a.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M. Roy. Information- theoretic generalization bounds for sgld via data-dependent estimates, 2020b. URL https://arxiv.org abs/1911.02151w3
Vladimir Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978-0-971-03003-4.
Vladimir Vapnik and Alexey Chervonenkis. Theory of Pattern Recognation. Nauka, Moscow, 1974.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
URL http:////ppppaeeieeeeeeeerrrrrrr
Chiyuan Zhang, Qianli Liao, Alexander Rakhlin, Brando Miranda, Noah Golowich, and Tomaso A. Poggio.
Theory of deep learning iib: Optimization properties of sgd. ArXiv, abs/ abs/1800.02254, .02254, 2018
Yikai Zhang, Wenjia Zhang, Sammy Bald, Vamsi Pritham Pingali, Chao Chen, and Mayank Goswami. Stability of SGD: Tightness analysis and improved bounds. In The 38th Conference on Uncertainty in Artificial Intelligence, 2022. URL atttps:/oppenreievt wwwppeewwww.eee/oorrreeeeeeeeeee 10
A Modification of McDiarmid's Theorem
We first define a probabilistic weakening of bounded difference property.
Definition A.1. Given 2m i.i.d. random variables X1...., Xam drawn from some domain Z according to some probability distribution D, for some 3 > 0 and r E [o, 1], a function f t + R is called vpaamoss 3- bounded difference w.r.t. D if
Vi E (1, .. m
X,m) - -
xm)) SB,
with probability at least - In case = 0 we say that f satisfies almost surely 8 3-bounded difference w.r.t D. When D is understood we will omit it.
We now state a modified version of McDiarmid's theorem that holds for rpalmost B bounded difference functions.
Lemma A.2. Let X1y..., Xm be i.i.d. random variables. If satisfies n- alamost 3- bounded difference and takes values between 0 and M, then,
-2e
Pr(f(X,,.... Xm) E[f(X,,..... X.n)l 2 cf S exp
+ +n.
(B + 2
Lemma A.2 follows directly from result shown in (Comees 2015
Proposition 2). Since the proof is available
in Combes 2015) omit it here.
21

---

Published in Transactions on Machine Learning Research (02/2024)
Symbol
Explanation
Symbol
Explanation
Ls
Worst Case Training Gradient. Second Moment of Step Training Gradient.
Total number of epochs, each epoch of m step, Wy the initial weight. a is some permulation of m points picked from of all possible permutation II.
La
Test Gradient.
Ks
Training Smoothness Constant. Input and output Space. Distribution over Z xy. Input point and label picked from distribution D defined over Z. random string from a random set to show randomness in an algorithm.
x.
Tsnit
Random initialization i.e. wo- A random permutation for m points. Random string having wo and (mi) i.e., for all epochs.
D
Tp
=
==
(1))
(Tinit, Tp)
rER
L
Local parameter Lipschitz constant. Local paramcter Smoothness constant. Weight matrix of I-th layer NN. The j-th row of I-th layer weight of NN.
K
s
Training set of size m.
W
S
Training set with 7th point replaced by another point picked i.id from D. Training Algorithm.
W).
As.r
(1)
Weight value I-th layer from 7th neuron of I-th layer j-th neuron of 1+ 1-th layer.
((5')
Bounded value Loss function with domain y x ) [0,
wij
R(As,)
Risk (Population error).
(a(As))
Empiriaal Risk (Training error).
T
Size of test set. Loss at t-th step of SGD computed on point
f(w)22)
w;
Weight of the parameterized function trained by SGD at 4h step.
S(),
Loss NN trained on set S and evaluated on point 2.
a
Learning rate t-th step of SGD. Spectral norm of matrix.
II-IIa
Table 3: Notation used in the body of the paper.
B Almost Sure (a.s.) Support Stability of SGD Proved
Proof of Lemma 4.3 Let f be the partial function of w (i.e., assuming 2 is already given) is locally Lipschitz
at w E A, there an Ew >> O and an Ta > 0 such that for all wt E Th with ||w -u--at w'll S Sw, [f(w) ( (ww') s L flllw - to|l So, let us turn our attention to those w' E A that lic outside the ball of radius Ew around w. Note that for such w', if
the bound on f, we have that
[(w)) - s(w') | will
2B
<
Ew
Therefore the "global" Lipschitz constant for f within max(Lw: 2B/=w w E A} which bounded since A finite. This valid for all the partial functions (i.c., for all E 22) and hence proves the theorem.
For some E [m]] we couple the trajectory SGD on S and St where 2; E S has been replaced with z/. Our random decision string r, this case, random choice an initial parameter vector, Wo. and a random set of F i.id permutations ug...., .T of [m] chosen uniformly random. We use these random choices for training both the algorithms with S and St. For 0 S < 1, we denote म. (i) by Lj, i.e,, I, is the (random) position where the ith training point is encountered in the jth training epoch. The key quantity we will track through the coupled training process will be
Proof of Theorem 4.5
8, = |w. w'll-
for SstS 7m. If we can show that E, [m,6 bounded by some quantity almost surely, we can invoke the fact that f is a.s. L,LLPL say that |,, [f(w,, 2) f(w,, < E, (Ly66ml s B for all E supp (D), where ly is the Test Gradient.
22

---

Published in Transactions on Machine Learning Research (02/2024)
We argue differently for the first epoch and differently for later epochs. For the first epoch, note that for s To, & = 0 since SGD performs identical moves in both cases. At L = To +
1,,1, a1 Vf(ws, 2i) (w', -a V +1II = a Vf(we, V Vf(w 2/Il
(10)
where the second equality follows from the fact that wt, = wto by the definition of To. Using Lemma 4.3 we can say that 01++1 S 20s,, Ls almost surely. Notice here we use data-dependent Worst Case Training Gradient Lg which is only defined for points in S, unlike Test Gradient. Now,
12+2 & || w/,+1 + 01 (Wrooo 2,) V V +1II
Here although the parameter vectors w1o+1 and w/o+1 not the same, 2 (Io+1) and 2 1x0(o+1)) by the definition To (assuming that To # m). Therefore we get that
the same
ö1o+2 S 81,+1 + a1ot1K581ot
with probability since from Lemma 4.3 have that f has "global" smoothness property for the entire
set of at most 2rm parameter vectors that will be encountered during the coupled training of S and S So we used Training Smoothness Constant (Ks). Noting that a similar recursion can be applied all the way to the end of the first epoch, ie. till = m we get
m
m Σ 1=lo+1
}
8m S 201 Ls II (1+ a,Ks) S 20,, L0 exp 1=1o+1
exp
a,Ks
(11)
with probability 1. Moving on to the next epoch, we note that we can make the argumentt above till the next. point where the two training sequences differ, ie., till the m 11 + 1st step. At this point we have,
t 5m+h 4 [V 11 24) V : +4)
Since neither the parameter vector the training points the same in the second term, we have option but to use the data-dependent Worst Case Training Gradient to say that,
8mth+1 S Sm + am+1, 2Ls.
Since 0m++7 < 0g observing that our current bound for 8m+1, is larger than Om 2Lg. Therefore
8m+1++1 S 28m+1,
So, we see that in the second and subsequent epochs, for time step jm + + +1, 1,,15, < we have the bound
6jm+l S 26jm+1zz
and for all t l,,t + I....., 1--1 we have, as before, by the smoothness property that
s411 S 51 Ks))
Therefore, we have that
Ko (rm))tr.m) - rrff.m))
6mm < (2) exp
Σ t=
akks /
an
19 [)p(r,m) exp
1
(12)
p(T,
where, in the first inequality for ease of calculation we have retained the terms of the form (1 + au, Ks), 2 j < in the product on the right although we can ignore them. In the second inequality, we have substituted a = ao/t ((((mm) and bound the summation using integration.
Finally, in order compute E, [Lyôr] remember there were two source of randomness first random initialization wh lets call it renit and random permutation lets call it Tp- Now because Finit and Tp are
23

---

Published in Transactions on Machine Learning Research (02/2024)
independent can write E, [Lg Braast [r, [Lgdrm [ Now in order to compute Br, Lgg note that lgg. Lss and Ks are constant.
Note that, since To is uniformly drawn from the set of permutations of [m]], lo is uniformly distributed on [m]. Summing up the last term 12 over To E [m] and dividing further by m we get
ay ((rm)o(rmm) -1 ro(rim)
Er, [Lg [ S 2" Dooggs x
Σ pl-plrm) exp 1o=1 1o
p(T, m)
Using integration bound the summation part and also using exp(-aalt K (T) S 1 we get the upper bound for the summation part as
aoKs (rm)
s U Ks Ks, exp
p(T,, m)
where
U (ow, Ks. p(T, = 1 exp( an Ko kymp(rm) (p(T,
agKs
we get
{ an (rm)p(rm)) p(r.))
exp
Er, (LnoseTimsll S 2" وي (ao, Ks, ((,
(13)
m
taking p(T, (() =
log logm m and expectation over Tinat we get the desired result. logr+log
We also present the proof of Thcorem 4.7 which is very similar to the proof of Theorem changes.
4.5 with some
Proof of Theorem 4.7 The proof of this is very similar the proof of Theorem 4.5 The main point is that
in the paragraph after Equation 10, we can actually use the exact gradient maxed over all permutation To-th step (lets call it Tg.1o) instead of Lag it's the gradient at To-th step. The rest of the steps follow similarly till equation
11
get
m Σ t-
8m S 281, exp
asKs
Now calculating E,, [m], note that earlier (in line 622) Lg constant w.r.t the permutation (rp) but here Ts1. depends the step, taking expectation permutation is equivalent to taking expectation over random variable lo which is picked uniformly from I to
E,, 1m [imie]] S ag Er,
exp
Σ
as
(=1++1
So using Cauchy Schwarz inequality to separate expectation over the random variable a
E., (rinnl I ag V Er, [o3,10
exp
Σ
20gKs
11
Upper bounding summation inside exponent by integration exactly like we did in equation second square-root terms
2
we get the
Iog Jog log
2anKs (m)
log m
log log log
exp
log log
1g
24

---

Published in Transactions on Machine Learning Research (02/2024)
Assuming p
log log log
to simplify the equation,
20m 2on Ks 20
}
20x0 K sI
Σ
exp
exp
(2-2p) exp
p
P
Io
Now, we use inlegration to bound the summalion term,
m
200 Ks To
m
2200 Ks
exp
x 2(1-p) exp
x
2 2p)
p
Substituting a = p, and in next step upper bounding (u ()-p)) by (as p < 1 and u- 2 limit) and then putting the limits.
throughout the
Σ 1==2
{
- 20g
Ks
mm/p
(u (l)p) exp f K
( 2p)
exp
p
u=
/p
$ 11'1/1 1/p
exp
f 22nkKu
u=1/p
1/11/1 exp
-
Ks
Using this and putting the value of and taking 1/1 we get,
UU" (ar, Ks, Ks. Er, Erp (Lggmlrmmde S anLo
[
(14)
on Kir tlus on
m
log log
where
1
U' U'(an, Ks, m)
Ks
and expoctation over rp for os. is just taking the average across SGD steps, get dg-
We also present the proof of Corollary 4.10
Proof of Corollary 4.10 get,
Writing assumption P1 averaged over steps and multiplying both side by ap
V ([,,,, )] < a Mo
ʃ (w: 2)
VTA
Now we take total expectation over the above equation and use Theorem 4.9 to bound the R.H.S of the equation. For L.H.S first, let the worst gradient (because permutation) at f-th step computed on point 2, is Lzgt = ma tm f(w, 21)}, where set A, Uneen (.) Keoping this in mind, we can write L.H.S as,
1
L.H.S =E
(15)
[=1
1=1
=
E E [2
(16)
(17)
Now note that because all 2; are identical (picked from the same distribution) so expectation over them will be equal. So max (Ez,z [I2,,])= = Ez,oz [22,]] and therefore we can replace the above with SMSTIG (i.e. as). Using this, get the statement of Corollary 4.10
25

---

Published in Transactions on Machine Learning Research (02/2024)
C
Neural Networks:
Characterization and Proofs
Symbol
Explanation
ki
Number of neurons in 1-th layer.
H
Depth of neural network.
(w,,(
Input to the i-th neuron of j-th layer.
out,, (w,,
Outpul of the i-th neuron of j-th layer. Is the label returned by the neural network.
outH,1 =
out(w, a)
((w,)) x)
Polynomial associated with fully connected NN.
Hr.((u, (,,(1,,0) x))
Base polynomial associated with j-th neuron of i-th layer.
Gw,
The set of weights need set zero, to apply all closed ReLU gate in NN (with ReLU).
6(w, ((wx))(u.a))
A neural network with ReLU activation with closed ReLU gates set to 0. Label of point x.
lab(z)
1
Position in permutation in j-th epoch when i-th training points (i.e. the replaced point.) encountered based on тj. Norm of difference between weights for and S at t-th step of SGD (i.e., ||w, -w/ w//l).
8:
Table 4: Notation used in section
In order to prove Theorem 5.2 we first need to describe characterization of neural networks that allows us to get a better insight into their smoothness properties. We present the characterization in Section C.1 and the proof in Section
C.2
After that, wC continue presenting the proof of Section
In Sections we also present the proof of
Theorem 5.1 Proposition 5.3 and Theorem 5.4 Then finally in Section C.3 we present the proofs of Section 5.2
C.1 A Polynomial-based Characterization Neural Networks
C.1.1 Neural Network Terminology
Neural networks provide a family of parameterized functions of the form we have discussed in Section The parameter vector w E R is applied over a network structure with layers. this case, we specify to be nd IR, i.e., the data points are from Ed and the label is from R, i.e, the NN has single output. We will denote the depth of the network by H. The layers will be numbered 0 to H with layer 0 being the input lager. assume fully connected network. We
The number of neurons in layer i will be kę For this discussion, will denote by w the weight of the edge from the j neuron of the ith layer to the kth neuron of the i + 1st layer. For the NN with parameters at point Rd we will denote the input into the jth neuron of the ith layer by (w,, z) and its output by (w,,) Further, we will assume that all neurons in all layers of the network except the input layer and the output layer have ReLU activation applied to them. In case the output of a node is 0 due to ReLU activation we will say the ReLU gate is closed otherwise we will say it is open. The label output by the network will be out = out(w, x... For each exposition, we will assume that out(w,, x) = 1 if in(w, x) > 0 and 0 otherwise, i.e., there are only two labels in V. For convenience we will denote this architecture as N.
C.1.2 Multivariate Polynomials Associated with a Neural Network
Given a set of indeterminates r = .i....,II, let P(x) be the set of multivariate polynomials on .i,..., with real coefficients. For any polynomial p(x), in i,,..., E [I] and any an,..., Otg E R for some S 1, we will denote by p(z) (ut,=ay } the polynomial in P(x (ar....,,
that obtained by setting all occurrences of nı to oj p(x). In particular, p(x) (a,=0] is the polynomial p(x) with all monomials containing 2; removed, and p²z) {a==1} retains all the monomials of p(x) but those monomials that contain 2; appear without the term z;-
26

---

Published in Transactions on Machine Learning Research (02/2024)
Returning to NNs, let consider two sets of indeterminates: x (z; : E [d] and {w S H, 1 S k,, & S k and ko d. Let consider N defined in Sec. C.1.1 and create version of it that replaced the ReLU activation at cach node with the identity activation function. We will call this the idenlily version of N and denote it I(V). We will say that I(N) has the following polynomial associated with it:
h
kH-1
6 (w x)
Ijo Wo.h Jo.n j1.z
(0)
(1)
(H-1) w jn
28-1=1
Note that the output layer has only one neuron. We will refer to this the buse polynomial of W. The base polynomial associated with the jth neuron in layer can be derived from the base polynomial of the network, we express this in figure and also write formally as follows
(1,( x) ((w, { (1) =0, (5) = ( ulsasllugseeeeee.
4.35
(18)
1pp K
Pid w 22)
j-th node
Pi.1
Pis( W,
i-th layer
(i + 1)-th layer
Figure The output of the j-th neuron of the i-th layer represented represented by the base polynomial. Here the weights along the dotted red lines set to zero and the weights along the green lines are set to one. The output of the neuron is represented by the values the connection. Notice that the output is scaled by the product of the number of intermediate nodes because of which we divide it later in 18
Also we could describe Network whose say ith layer jth neuron's gate is closed by ((w,)) 0, 44 E k-1), This is represented by the figure We will write Gw.z as the set of weights needed to be equated to zero for all closed ReLU gates. It's clearly visible that due to ReLU activations varying at different points, there no single polynomial that captures the output the NN everywhere R Rd. However, the following observation shows a way of defining polynomials that describe the output over certain subsets of space.
Observation C.1. Given w E R and x + (O...., 0) E Rd, i [ E [kj] and Φi., (w, (G = 0} the polynomial representing output and Gu, x the set of weights for closed ReLU gates as discussed above. For the case where int, (w, x) + O for all h i and all < l2 ki, there is O depending w,æ such that, for all w/ with w/w w'll <E,
( , (G 0} ( 0}
i.c. the polynomial remains same for un and
27

---

Published in Transactions on Machine Learning Research (02/2024)
j-th node
Φ w, x) =
(i 1) layer
i-th layer
Figure 5: For a neural network with ReLU, the i-th layers j-th neuron's ReLU gate is closed, this is represented by the base polynomial. Here the dotted red lines are to zero.
Proof. Since i σ) is strictly separated from and there are only a finite number of neurons in the network there must be an e small enough for which all open ReLU gates remain open and all closed gates remain closed. And because of this, we can use the same polynomial with new weights as no ReLU gate switches their state.
C.2 Proofs for Section 5
We use the NN characterization for the proof of Theorem 5.2
Proof of Theorem 5.2 The idea behind this proof is due to Milne 2019 Lemma 1) who used for a different purpose. From Observation C.1 it follows that if we have x * (0, .O.....4 E Rd such that in. x) F 0 for all isis < H and all S ki, then out(w, x) is, in fact, just the polynomial d(w', xx) ( 0} within a small neighbourhood of w. Therefore it is doubly differentiable. Since the loss function is also differentiable, we are done for all such values of æ.
So now let us consider the set points for which the smallest layer index such that in x)) 0. In case there are two such indices, we break using the neuron index j. By Observation C.T a neighbourhood of w, (w,
polynomial in w and for each x.
Now, consider two cases. In the first case, out;- (w, x²) 0 for all jr [kg-1], i.e., all the ReLU gates from the previous layers are closed because in;-1,y' (w, x) < 0 for all j' (k-)). In this case out(ur' xx) 0 everywhere in the neighbourhood guaranteed by Observation C.1 and therefore f(out(w',z), lab()(()) is doubly differentiable the parameter space at w for all such æ, where we assume that each data point has a label lab(x) E {0, 1} associated with We note that this argument, is easily portable to the case more general label set with the property described the statement of Theorem 5.1 since in will be everywhere in a small neighbourhood.
In the second case have some j' E [k--]] such that out; (w,z) > 0. Let Ct, S dd be those for which this case holds. Ci, contains the solutions to in. .2) O. Since we are working with specific value of w, this simply becomes a polynomial in æ. In fact, inspecting the definition of base polynomials we note that when w fixed (w, æ)) is simply a linear combination of 2i....,z4f This implies that C.2 is a hyperplane in Rd. We note that this argument can also be made of the output node under the condition on the label set given in the statement of Theorem 5.1 because for in (w, x)) to give a value that lies on the boundary between two sets with different labels for given w, must be drawn from set of Lebesgue measure 0.
28

---

Published in Transactions on Machine Learning Research (02/2024)
Since the network size is finite the set of all possible values of for which case 2 occurs, i... UlE(tT) Ci. is a finite union of hyperplanes in R and therefore a sct of Lebesgue mcasure 0.
Proof of Proposition 5.5 Let us consider the partial derivative w.r.t w/ For this let -.. and B B!l-1) be 3 matrices of size W w(+1) and W((-1) respectively such that / [8, i] = and reset all entries are 0, A 11+1) [k. = [k, ,), vk and rest all entries are O and (r k] ( kij. Ak and rest all entries are one. Using these matrices and the weight matrices we can compute the gradient as
(1) 0Ø(w, with ....2) AHt1) 1.9 B( wi-2... W!.
(19)
0
Let (1(,,,,)) be matrix such that
Mi,, = 4 (1+1) 1 B(t
Although we have scalar values taking spectral norm on both sides of eq
19 we get
Ow?y (1) 0o(w, x²)
I|Maa [ (1 |W
II k=1
[
||||||
Now lets define another matrix Mj such that (p, a)th element of matrix Mip, q) = || Now, the expression for 2,2 norm (Frobenius norm) of the gradient vector directly gives us the required expression for bound on gradients.
(1) We can give similar argument for bounding Ks, for some w wigh and wijj we have
(olw,x) (1a) (11)
[W( (Irra Mhh lla 1I (1w(1-1)
II k=1
-
|| lb.
||
[
|| (1) ||W(|=-1]]]
Note that the above equation is exactly if 4 + 2 < l2 or 4 2 > l2 and for the rest of the case we can use this as the upper bound this because for a matrix M spectral norm ||M]| upper bound for when we set except one row or column of matrix to zero and calculate the spectral norm. Now we take the 2, 2 norm (Frobenius norm) of the Hessian matrix we get the desired result.
We now show the proof of Theorem 5.4 present in the discussion of Section 5.1.2 where we bound the gradients encountered.
Proof of Theorem 5.4 We first write the &g norm of gradients of parameter vector as,
Vwwf(w 1)1 V|Vw f(w, x>13 VV x(w,
Calculating gradients norm for both layers, assuming for given Wo (i.e., weight at initialization, note that this is part of r randomness), we have a value of weights bounded above by B
0f(w, x)) Oml(²)
=(( j.s 12, Where W are the 8th row of W
B7 D
29

---

Published in Transactions on Machine Learning Research (02/2024)
The effective dimension of is D, so the above dot product dimension will also be bounded by D is in all other dimensions.
2
()w, (2)
luo! xzyl
@wlyy
Bi
So, summing up the squared partial derivatives across all parameters we gel,
fww x) - d1 D- B1 + +1 D² B²
BR d1 D(1 + D)
C.3 Proofs for Section 5.2
Proof of Theorem 5.6 First lets assume that assumption P1 holds so we need to show Ex [f(wo, 2)] is bounded, caleulating the value for this,
f(wo, 2) = ly - O(w, x)]
(1)
Wi
W
2 Z2
lul +
Σ
w W.
(2) (1)
11
+
Σ
w w 1,2 32
(2) (1)
Let 01 (www) = Σx= w/ w/ and o2(w)) = Σ
w
(2) (1)
for case of writing, then take expectation over
wo. we directly place Ews (llg(wo)) = Ewo [|or(wo)l] assumption ,i.e.,
2k because of half normal distribution and i.i.d
2ko²
Ewo [f( 2)] S |yl +
(1x1 + [x2)
Taking expectation over 2, we have
4ko² Up
Eus. [f(wo 2)] =
(20)
Now, we show the assumption P1 holds. Note that we ignore the case when weights are exactly zero weights become exactly equal to other weights to avoid zero in the denominator. We take M = 0 from assumption P1. Now we take the upper bound of H.H.S. of assumption P1 (without expectation).
V 2)11 < n max((V((W:))) =)3)
and we take the lower bound of R.H.S. using
mineE [Vf =).))² < |E (Vf(w, 2)] ||
Using the above two inequalities and taking M assumption Pl, we get,
Eres [max / (w, =)3}]
< Ma
mingen (Eees V (w, =),
30

---

Published in Transactions on Machine Learning Research (02/2024)
Now, calculating for numerator, we first write the max over the square of gradients,
{ (80(w)))
max( 2),)²} = max
max ((w 32 Ja7g)
(2)
if if J1 =
max((w) 12 + 22222)
(1)
(1)
Let Wh be the highest absolute value of weight(s) and wy be the lowest absolute value of weight(s). To easily calculate expectation, we take out the max weights across all, we get an upper bound for the numerator,
E EgeS max ((Vf(w, 2)}
o
(21)
Now lower bounding denominator, so square of expectation of partial derivative, i.e.,
80 x²)
1) Quiiids
2
ELes x) EEEs
= =(wle (2) [r;;]))
i1 = if i =
(w F. [x1] + u F
For i, = 2 term, after taking expectation, we could write it as,
E [11] w
(1) E
(1) W
(1)
Since we have B for all ratios of weights could use this to bound below the absolute difference between any pair of weights (i.c., luy- - wil wun/ B - wil), and we get
(m [ - E 2
So we can bound the whole denominator by:
wf(B - 1)2
w
min [BxES
>
min wi
(22)
4
B²
w
B 1)2
(23)
4B²
Using 21 and 22 we get,
8B'0²
M6
(24)
(B 1)2
And from 20 and 24 we get the theorem statement.
31


Reviews:
[{"review_id": "6kXwdWFUgJ", "reviewer": "Reviewer_2QBs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper manages to obtain good generalization bounds for SGD under a fairly realistic setting; in particular, it encompasses the multi-epoch regime, and the allowed decay of the learning rate in terms of both $m$ and $t$ seems much closer to what is actually used in practice.\n\nHowever, I am unconvinced regarding the applicability of the obtained results. Compared to similar data-dependent bounds such as the ones in (Hardt et al. 2016) or (Kuzborskij and Lampert 2018), the constants $L_S$, $K_S$ and $L_g$ have a very complicated dependence in the data distribution and the specifics of the SGD dynamics (which can be very hard to analyze). Further, it seems to me like those bounds can increase arbitrarily in $m$ (as in the random label example), and the conditions under which $L_S$, $K_S$ or $L_g$ are bounded seem very hard to verify compared to previous work.\n\nFurther, all of section 5.3 consists in unsubstantiated claims about extensions of the results to other settings, without much theoretical footing; either those are easy adaptations and the theorem statements could be adapted to include those changes, or there are significant challenges that should be underlined.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the notion of stability of learning algorithms, which usually implies good generalization bounds. It introduces the concept of *almost sure support stability*, and relates this concept to generalization bounds using a modified McDiarmid inequality.\nIt then shows that the SGD algorithm satisfies such support stability, with the bounds depending both on the data distribution and the weights encountered during the SGD training. Finally, the authors prove that for fully connected ReLU networks, those bounds are controlled by a spectral norm hypothesis on the weights of the network.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "In my opinion, the paper requires a much larger discussion on the scaling of the three constants $L_S$, $K_S$ or $L_g$; the ReLU network example still consists in a norm supremum over all possible trajectories of SGD, and thus is still very delicate to bound. Even a toy model for which those constants can be easily bounded could already be a good addition to the paper. \n\nAt the very least, a discussion on what those constants imply on the training procedure is in order. For example, the authors state that \"if the model can’t fit the training set properly then these values will be high and reflect a bad generalization\"; why would a high training loss imply high Lipschitz constants ? Regarding section 5.1.1, under which conditions can we expect that $L_S$ and $L_g$ are close ?\n\nMinor remarks:\n- I found the theorem statements quite heavy to read; a lot of the preambles are very similar, and should be broken down into separate assumptions. Less inline math should also be used.\n- the notion of \"symmetric in distribution\" is never defined", "broader_impact_concerns": "N.A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SKpWpb7L57", "reviewer": "Reviewer_d5U1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is overall well written and easy to follow in general, but some modifications can make reading easier, especially in the appendix. I have read both the main and the supplementary material.\n\n## Strengths\n\n- The area of generalization of neural networks is of capital interest to the machine learning community, and it is good to investigate it.\n  \n- Data-depending smoothness and Lipschitzness constants\n  \n- Proofs are provided for all of the theoretical claims. They are generally well written. A clear effort is made to facilitate reading and to convey the guiding idea for each proof.\n  \n- A good experimental evaluation.\n  \n\n## Weaknesses\n\n- A notion of stability holding with any probability is introduced, only for its particular case of holding with probability one to be used later. In this case, introducing the almost sure version directly makes the paper easier to follow.\n  \n- Unclarity in some parts:\n  \n  - The terms $L_l$-Lipschitzness and $K_l$ smoothness allude to constants $L_l$ and $K_l$, yet these constants might depend on $z$. Isn't it more convenient to consider $L_l$ and $K_l$ as functions rather than constants in this case ?\n- Several issues in Theorem 4.4:\n  \n  - Error in a claim: from the proof of the theorem, we have $U(\\alpha_0, K_S, \\rho(\\tau,m)) = 1 + \\cfrac{1-\\exp(-\\alpha_0K_Sm^{\\rho(\\tau,m)}/\\rho(\\tau,m))}{\\alpha_0 K_S} $, in which the second term converges to $\\cfrac{m^{\\rho(\\tau,m)}}{\\rho(\\tau,m)}$ rather than to 0. Also, due to the concavity of the numerator of the second term, one can bound U by $1+\\cfrac{m^{\\rho(\\tau,m)}}{\\rho(\\tau,m)}$ which is more informative than the bound in the paper, as it corresponds also to the limit for very small $\\alpha_0$.\n    \n  - Unsubstantiated claim: Just after the statement of Theorem 4.4, in the \"*Data dependence with Training Lipschitz constant and Test Lipschitz constant*\", there is the statement \"we expect that if the unknown distribution D has a low variance then the Lipschitz constants will be small\". Although this is a conjecture, some justification of motivation for it should be provided, experimentally at least (for example, by plotting the data-dependent Lipschitz constant bounds against the variance of a data set.\n    \n- Unsubstiantiated claim and unclarity on the behaviour of $\\beta$ after Corollary 4.5: it is mentioned that $\\beta = o(\\cfrac{1}{m})$ with the conditions of Theorem 4.4 and Corollary 4.5. However, applying that to Theorem 3.2, one would expect a behaviour that is $\\sqrt{\\cfrac{\\log m}{m}}$ as the second term in the generalization bounds dominates in this case. However, the bound given in the corollary still keeps a term growing in $\\cfrac{1}{m^{\\epsilon}}$. Also, I could not find the justification for this asymptotic behaviour of $\\beta$ in the appendix.\n  \n- Many improvements can be made in order to facilitate reading, please refer to the \"Requested changes\" section for details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors study the generalization of Rectified Linear Unit (ReLU) neural networks (NN) trained via stochastic gradient descent, through the lens of stability theory. First, they introduce a weakened notion of stability that holds with a certain probability and use its variation holding with probability one to derive generalization bounds for any algorithm satisfying their stability notion. Then they define a notion of data-dependent Lipschitzness and smoothness properties, which are later shown to hold for fully connected networks with ReLU activation functions. Bounds are provided for the constants of Lipschitzeness and smoothness in the case of a ReLU NN. Finally, experiments are run to corroborate the theoretical findings on two datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have tried to group the requested changes into different categories.\n\n## To facilitate reading\n\n- Unifying Lipschitzness and smoothness: Definitions 4.1 and 4.2 can be unified under the same definition of Lipschitzness of a vector-valued function. Then, local parameter-Lipschitzness and local parameter-smoothness can be stated as simple specializations of that definition to the function itself and to its gradient, respectively. The same holds for Lemma 4.3.\n  \n- Both adding some informal description of the mathematical quantities presented and adding a formal description for informal statements.\n  \n  - At the beginning of Section 3.2, the sentence \"Given the set $S$, we construct $S_i$ via replacing the $i-$th element of $S$ by an independently generated element from $D$\" would facilitate conveying the idea, along with the given formula.\n    \n  - In the discussion just after the statement of Lemma 4.3, the expressions \"set of weights encountered during training over all possible permutations\" and \"set of final parameter vectors produced by SGD for each of the possible permutations\" would be much clearer if a formal definition is provided for the set $A$ in each case. This definition can for example be only in the appendix, but I think it clarifies these quantities.\n    \n- Base polynomials\n  \n  - Adding interpretations:\n    \n    - Full NN: for example, \"output of a network with the identity activation function, i.e. fully linear\".\n      \n    - Specific neuron: obtained by setting... In this case, a figure illustrating the concerned neuron and the operation applied to obtain the polynomial can significantly quicken understanding.\n      \n  - provide references for the base polynomial (if any)\n    \n- Adding a notation table in the supplementary material\n  \n- Using the same letter to index layers, and neurons. I agree this is nitpicky, but I think it would facilitate reading more. For example, the index $l$ for layers (including $l_i$ where $i$ is any index).\n  \n- Specifying the exact source of inspiration for the proofs (precisely which results in the mentioned reference.)\n  \n- In the second point of the list of contributions, a number of epochs of $c\\log m$ is mentioned, but there is no explanation on the nature of constant $c$ (*e.g.* a universal constant, a constant depending on some parameters ...). Alternatively, if it is just the $\\log m$ growth rate that is to be highlighted, then for instance, writing \"for a number of epochs proportional to $\\log m$\" solves the issue.\n  \n- In Theorem 4.4\n  \n  - $F(\\tau)$ 's expression can be directly incorporated in the bound, *i.e.* without introducing $F(\\tau)$.\n- Avoiding long sentences, or adding commas at least:\n  \n  - Corollary 4.5: The first sentence is very long, and needs a comma after:\n    \n    - \"*Theorem 4.4*\"\n      \n    - \"*w.r.t.* $m$\": also the word \"then\" should be removed, as the structure is \"For an algorithm verifying conditions A, B, ..., there is a constant ...\".\n      \n    - $c\\log m$ *epochs*\n      \n- In proposition 5.3, it is written \"Note that this equation holds for both Training Lipschitz ...\". While It is understandable that the meant equation is the one providing a bound on $L_g$, attributing a number to it would be clearer.\n  \n- In the Definition $A.1$ in the appendix, the bounded differences property is called $\\beta-$Lipschitzness. However, Lipschitzness is a well-known property that is totally different from the bounded differences. This can be confusing for readers and I recommend calling it the bounded differences property.\n  \n\n## Notation and terms issues\n\n- No definition of the term \"symmetric in distribution\" was given before its first use in Theorem 3.2.\n  \n- It should be indicated whether constant $c$ in Theorem 3.2 is universal, and if not, what quantities it depends on.\n  \n- In Definitions 4.1 and 4.2, $z$ is used in the Lipschitzness condition for the first time, without being introduced. Only later it is specified that the constant $L_l$ or $K_l$ depends on $z$. This can be fixed by introducing $z$ at the moment when $\\bm w$ is introduced.\n  \n- The logarithm is denoted \"$\\log$\" in all of the paper except for the expression of $\\rho$. Homogeneity of notation is better.\n  \n\n## Other suggestions\n\n- Constructing a simple theoretical example in which data-dependent Lipschitz and smoothness constants are small or moderately large, but absolute ones are too large or even infinite.\n- Adding a discussion on the interaction between the two terms in the bound in Corollary 4.5. Indeed, the first term divided by the second yields $\\cfrac{(\\log m)^{\\cfrac{3}{2}}}{m^{\\epsilon-\\cfrac{1}{2}}}$, which means that one gets the \"usual\" rate of $\\tilde{O}\\left(\\cfrac{1}{\\sqrt{m}}\\right)$ whenever $\\epsilon\\geq\\cfrac{1}{2}$ (where the tilde hides the logarithmic factors), and will be slower if $\\epsilon<\\cfrac{1}{2}$. It would be interesting to analyze this behavior and to give an intuition of the slow rate, and when would it be beneficial to slow it for example. The overall rate can also be written as $\\tilde{O}\\left(m^{-\\min\\left(\\epsilon,\\cfrac{1}{2}\\right)}\\right)$.\n- In the proof of Proposition 5.3, the product of norms is used to bound the norm of products. I think it would have been fine to let the norm of the product of matrices without further bounding it. Indeed, besides the fact that it already only incorporates quantities that appear in the bound stated by the proposition, it would result in a much tighter bound.\n- The McDiarmid inequality for functions satisfying the bounded differences with high probability can be related to the result of [1].\n- In the discussion just after Theorem 5.1, it is written \"then these values will be high and reflect a bad generalization\", where \"these values\" refers to $L_S$ and $K_S$. While the right-hand side of the generalization inequality of the theorem vanishes as $L_S$ approaches $0$ (since $F(\\tau)$ is proportional to $L_S$), I do not think that seeing it holds for $K_S$ is straightforward. Indeed,on the one hand, when $K_S$ tends to 0, $m^{1-\\frac{\\alpha_0K_S}{\\rho(\\tau,m)}}$ tends to $m$. On the other one, we have $U(\\alpha_0, K_S, \\rho(\\tau,m)) = 1 + \\cfrac{1-\\exp(-\\alpha_0K_Sm^{\\rho(\\tau,m)}/\\rho(\\tau,m))}{\\alpha_0 K_S}$ converges to its upper bound $1+\\cfrac{m^{\\rho(\\tau,m)}}{\\rho(\\tau,m)} $ as $K_S$ vanishes. However, since $\\rho(\\tau,m) = \\cfrac{\\log\\log m}{\\log m + \\log \\tau}$, we have $m^{\\rho(\\tau,m)} = \\exp(\\cfrac{\\log m\\log\\log m}{\\log m + \\log \\tau})$ behaves as $\\log m$ as $m$ grows, hence the bound on $U$ behaves as $\\log m$. In the end, we would have a generalization bound that behaves as $O(\\cfrac{(\\log m)^3}{m} + \\sqrt{\\cfrac{\\log m}{m}}) = \\tilde O(\\sqrt{\\cfrac{1}{m}})$ . Hence, I think a more detailed explanation should be given.\n\n## Formatting\n\n- The title of Section 3 should not start with \"a.s.\". Rather, for example, \"Almost Sure (a.s.) Support Stability ...\"\n  \n- At the end of Corollary 4.5, one cannot write \"and $\\in$\" as the \"$\\in$\" operator needs a left-hand side. Instead, one can either write in full \"and belongs to (0,1)\" or, more shortly, $\\epsilon \\in (c,1)$.\n  \n\n## Grammar\n\n- At the beginning of section 4, the first part of the sentence \"The parameter vector at step t being ...\" does not have a conjugated verb. It should rather be \"The paraöeter vector at step t is denoted ...\"\n  \n- Section 4.1: \"required\" --> \"needed\" (to avoid repetition with \"requirement\").\n  \n\n## Typos\n\n- In the related work section \"our work falls in this category\" should be changed to, for instance, \"in which our work falls\" or \"a category in which our work falls\".\n- In Equation (7) of the appendix, the norm of x is to remove.\n- After Equation (7) in the appendix, \"M'(l,i,j)\" should be in latex math mode.\n- In Theorem 5.1, the \"$\\in$\" symbol in \"$S \\in D^m$\" should be $\\sim$, as $D^m$ is the distribution of $m$ samples drawn independently from $D$.\n\n### References\n\n[1] Combes, Richard. \"An extension of McDiarmid's inequality.\" *arXiv preprint arXiv:1511.05240* (2015).", "broader_impact_concerns": "This is a paper with solely theoretical claims. As such, its potential practical impacts largely depend on its applications. Thus, I do not see the need for any discussion of broader impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "tMMejuulRA", "reviewer": "Reviewer_FJNX", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The most outstanding weakness of this work is its writing style, unfortunately. Reading it has been so unpleasantly hard that I am motivated to focus on criticizing the submission, regardless of the positive aspects (strengths) it might have.\n\nThe write up is missing a clearly formulated target problem (neural network classification?) and explicitly formulated target question(s) corresponding to the problem (e.g. generalization). Note that targeting generalization requires explicit definitions such that it might be possible to judge the claims. For instance, I didn't see explicit description of the meaning of \"generalization error\" in the introduction. A short sentence saying that this is the gap between the expected (population) error and the empirical error rate would be sufficient to clarify what is meant, and better if a cross-reference to the formal definition in Section 3.1 is given, to avoid confusions.\n\nI flag for criticism the opening sentence \"The low generalization error of Deep neural networks is now a well known empirical result\" - if the meaning of generalization error is as I just described above, then this claim is unfounded. It might be that the authors (or the authors of the cited paper) are trying to refer in this claim to the gap between test error rate and training error rate. This needs clarification.\n\nThere are many other weaknesses that need attention, see my requested changes below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "As indicated in the abstract, the authors \"try to establish that one of the correct data dependent quantities to look at while trying to prove generalization bounds, even for overparameterized neural networks, are the gradients encountered by stochastic gradient descent while training the model. If these are small, then the model generalizes.\"", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "- Define formally the meaning of \"generalization\" such that readers may evaluate the claims regarding it.\n\n- Clarify the setting of this work by formulating explicitly the target problem, which I think it is neural network classification.\n\n- Accordingly, clearly restrict the loss function (s) under consideration. Is it not the cross-entropy as surrogate loss for training?\n\n- The role of the set $\\mathcal{R}$ and its elements (decision strings) is unclear. Needs discussion/illustration for adding clarity.\n\n- The meaning of \"loss function\" needs to be specified before defining risks and other things. At least some discussion of the typical loss functions that are considered, and that one of those is referred to when we read \"loss function\" in the sequel. \n\n- The notations $x_z$ and $y_z$ are unnecessary. Simply replace $z \\sim D$ with $(x,y) \\sim D$ and then you can write $\\ell(A_{S.r}(x),y)$ in the definition of risk. Similarly, replace $z \\in S$ with $(x,y) \\in S$ in the sums for the empirical risk.\n\n- Reading sometimes $A_{S,r}$ and sometimes $A_S$ or $A$ caused confusion. Can the relation between these things be declared? Perhaps a formal definition of each of these things would help to clear the confusion.\n\n- When declaring $S^{i}$, after the definition perhaps add comments to the effect that $S^{i}$ is formed by replacing the $i$th entry of $S$ with an independent copy (which is taken as the $i$th entry from the \"second set of size $m$\"). By the way, this reminds of the double sample argument, which goes back to classical literature on statistical learning, which might be good to cite.\n\n- Definition 3.1: Poor choices of terminology ($\\eta$-almost support stability, a.s. support stability) which don't add much clarity. I suggest reformulating these things. The way I see it, the main idea being defined is that of \"support stability\" corresponding to the displayed condition, which may hold with some probability $1-\\eta$ or with probability 1 (almost surely). Then you could reformulate this definition writing \"support stability $\\beta$ with probability $1-\\eta$\" and \"support stability $\\beta$ almost surely\" -- the latter formulations are way more clear in conveying the meaning of what's being defined.\n\n- I don't think the notation $[m]$ was declared. Just declare it somewhere before this definition.\n\n- If we choose a constant loss function $\\ell \\equiv 1$, then this satisfies support stability $\\beta$ for any $\\beta>0$? This perhaps shows one of the problems in not restricting the meaning of \"loss function\" from the start.\n\n- Also I'd like to flag the restriction \"$\\forall z \\in \\mathrm{supp}(D)$\" in this definition. It appears to contradict the statements \"with probability at least $1-\\eta$\" and \"almost surely\" so this needs clarification. \n\n- Actually, a few lines below it is stated that \"This probability is defined over the random choices of $Z_1, . . . , Z_{2m}$\" which then suggests that Definition 3.1 needs to be rewritten making this explicit. Since the distribution of the random sample (i.i.d. points) of size $2m$ is $D^{\\otimes 2m}$, this would be written saying \"$D^{\\otimes 2m}$-probability $1-\\eta$\" and \"$D^{\\otimes 2m}$-almost surely\"\n\n- Still, it is a very strong requirement that the inequality holds $\\forall z \\in \\mathrm{supp}(D)$ (and $\\forall i \\in [m]$). Could the authors give illustrative examples of cases for which it is possible to calculate or estimate this condition.\n\n- Theorem 3.2: Could the authors comment on the constant $c>0$ please. The exact value of this constant can make all the difference between the bound being useful or it being useless.\n\n- The meaning of \"symmetric in distribution\" needs to be specified (before Theorem 3.2).\n\n- Definitions 4.1 and 4.2: I don't know what meaning to map to \"Given a set $\\Omega$ defined over $\\mathcal{Z}$.\"\n\n- Theorem 4.4: Reading \"We are given a labelled data set $\\mathcal{Z}$\" is surprising. I thought $\\mathcal{Z}$ was reserved for the space of all possible instances and labels, i.e. $\\mathcal{Z} = \\mathcal{X}\\times\\mathcal{Y}$; while a \"labelled data set\" should be a finite sequence in this space.\n\n- The rest of the theorem statement is really (!) hard to parse. Could this be improved?\n\n- Similar comment for Theorem 5.1.\n\n- Note that Theorem 5.1 neglects many details of the neural network architecture. Does this mean that the theorem holds for any choice of architecture (e.g. any depth and and widths in the hidden layers) as long as the output layer is 1-dimensional?\n\n- Figure 2: The obvious question coming to mind is what is being plotted for \"generalizaion error\" here. If we take the definition stated earlier on in the paper that \"generalization error\" stands for the gap between risk and empirical risk, then I would ask how the authors obtained the values plotted here. Perhaps the plotted quantity is a proxy for the generalization error. I any case, this needs explanation.\n\n- Another observation regarding Figure 2: The bound values appear to be loose. Definitely they are not nearly the best bound values for neural network classifiers reported in the literature. This raises the question about what is the take-home message that readers could get from reading this paper. If not tightness of the bound values, then it must be something else, but currently unclear.\n\n- Bottom of page 11, bullet about NTK: I could not make sense of what's written here. Please elaborate and clarify.\n\n- I think \"data-dependent\" needs hyphenation (throughout the paper).", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers initially highlighted a considerable number of issues around clarity, definitions, and the overall framing of problems, which the authors acknowledged could be improved and addressed in their revisions. Specific technical concerns, such as the handling of "constants", the formulation of theorems, and the interpretation of results, were largely validated by the authors' detailed responses and revisions. Two of the reviewers were of the opinion that the reviews addressed their concerns. 

Some areas where authors disagreed or clarified concerns from reviewers were misconceptions or misunderstandings about their framework, especially regarding its applicability and the interpretation of certain constants and results as mentioned above. They disagreed with the notion that their approach was overly complicated or less applicable than previous works, providing additional examples and discussions to demonstrate its relevance and utility.

There are some aspects of the rebuttal that might still leave reviewers disappointed. Primarily, reviewers may be left wanting more concrete demonstrations or simpler explanations, especially in terms of the practical applicability of the theoretical framework.
The complexity of the constants and the bounds, although clarified, are still be a point of contention for reviewers looking for more straightforward or intuitive results.

In summary, the authors have made a concerted effort to address the reviewers' concerns, focusing on clarifying their theoretical framework, refining definitions and theorems, and providing additional context and examples to demonstrate the applicability of their work. While some issue remain that may ultimately make the work less impactful, I believe it is suitable for publication.
Decision: Accept (poster)