Generalization error bounds for Neural Networks with ReLU activation
Authors: Harsh Pandey
Amitabha Bagchi
Srikanta J. Bedathur
Arindam Bhattacharya
Venue: Submitted to ICLR 2023 (2023)
Keywords: relu stability
sgd stability
non smooth neural network stability

Abstract: We show rigorous bounds on the generalization error for Neural Networks with ReLU activation under the condition that the network size doesn't grow with the training set size. In order to prove these bounds 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 proving that if an algorithm has low enough a.s. support stability its generalization error tends to 0 as the training set size increases. Further we show that for Stochastic Gradient Descent to be almost surely support stable we only need the loss function to be locally Lipschitz and locally smooth with probability 1, 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, thereby proving low generalization error. The caveat is that the size of NN must not grow with the size of the training set. Finally we present experimental evidence to validate our theoretical results.

Under review as a conference paper at ICLR 2023
GENERALIZATION ERROR BOUNDS FOR NEURAL NETWORKS WITH RELU ACTIVATION
Anonymous authors Paper under double-blind review
ABSTRACT
We show rigorous bounds on the generalization error for Neural Networks with ReLU activation under the condition that the network size doesn't grow with the training set size. In order to prove these bounds 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 proving that an algorithm has low enough a.s. support stability its generalization error tends to 0 as the training set size increases. Further we show that for Stochastic Gradient Descent to be almost surely support stable we only need the loss function to be locally Lipschitz and locally smooth with probability 1, 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, thereby proving low generalization error. The caveat is that the size of NN must not grow with the size of the training set. Finally we present experimental evidence to validate our theoretical results.
INTRODUCTION
Given the importance of the generalization error in machine learning there have been numerous theoretical approaches to bounding it, one of the most significant being the concept of algorithmic stability whose origins can be traced back to Vapnik & Chervonenkis (1974). In this paradigm the definition of uniform stability by [Bouqquet & Elisseeff (2002) was a landmark because allowed the authors to prove sharp concentration bounds showing that the generalization error for the algo- rithms that satisfy this property tends to 0 as the training set size increases. Thanks to the success of Bousquet& & Elisseeff (2002) on variety of nen-nl methods, when Hardt et al. (2016) showed that a learning function computed by optimizing certain loss functions through Stochastic Gradient Descent is uniformly stable under mild conditions on the loss function, this clearly raised the ex- pectation that the next step would be to show that Neural Network-based models are also uniformly stable and, hence, have a low generalization error. This analysis was then expected to corroborate the empirically observed fact that the generalization eтror is low for NN models (c.f., c.g., Krizhevsky cet al. (2012). Hinton et al.] (2012). .) Case closed. However, this triumphal march of algorithmic stability was rudely interrupted by Zhang al. (017), who showed explicit examples of distribu- tions that cannot be learned with low generalization error and yet can be learned with an NN of an appropriate size. Zhang et al. (2017) speculated that the problem arose from the fact that the concept of uniform stability was based only on properties of the algorithm and not on the properties of the unknown data distribution. While this was a reasonable speculation, it left open some questions: Is there reasonable definition of stability that incorporates distribution properties and leads to small generalization error? And can we show that NNs with non-linear activation functions such as ReLU at the neurons have this property?
In this paper we give a strongly affirmative answer to the first question and a partially affirmative answer to the second question. We define notion called almost sure (a.s.) support stability which is a probabilistic weakening of uniform stability. Unlike the data-dependent notions of stability defined in Kuzborskij & Lampert (2018). Lei & Ying (2020) that bound generalization error in expectation, a.s. support stability can be used to show high probability bounds on generalization error. This proof entails proving a mild generalization of McDiarmid's Inequality that could be of independent interest. The major contribution of our paper is that we show how to handle the non-linearity of ReLU in mathematically rigorous way by modifying result of Milne (2019) to show that ReI.U

---

Under review as a conference paper at ICLR 2023
affects the smoothness of the gradients computed by Stochastic Gradient Descent with probability 0 for well-behaver distributions. To the best of our knowledge such a result has not been reported in the literature.
Clearly the question arises: What about the evidence presented by Zhang et al. (017) that there exist unknown distributions that can be learned by NN but will always have unbounded generalization error? To answer this we need to understand that our analysis of SGD presented requires the loss function to be smooth and Lipschitz in the parameter space (though with an appropriate probabilistic weakening of these properties.) Our analysis is able to demonstrate that these properties hold for NNs whose size doesn't i grow with the size of the training set. So, our specific answer that we have for the second question listed above: Almost support stability can be used to demonstrate that the generalization error for NNs with ReLU as long as the size of the NN doesn's It grow too fast with the training set size, and if the unknown distribution places probability 0 on sets of Lebesgue measure This leaves open the matter of a theoretical explanation for why certain heavily overparametrized NNs generalize well in practice. However, we do provide some directions on how our analytical framework may be used to prove such results.
In particular our contributions are:
Section 3 we define a new notion of stability called a.s. support stability and show in Theorem P that algorithms with a.s. support stability o(1/ log m) have generalization error tending to as + Do where is the size of the training set.
Section we show that if we run stochastic gradient descent on parametrized optimization function that is only locally Lipschitz and locally smooth in the parameter space and that too only on input points selected with probability 1, then the replace-one error is bounded even if the training is conducted for clog epochs. This implies (Corollary 7 that any learning algorithm trained this way has generalization error that goes to 0 as m + oo for learning rate at/t at step t for an appropriately selected value of og that does not depend on m.
In Section 5 we show that the output of an NN with ReLU activations when used with a doubly differentable loss function is locally Lipschitz and locally smooth in the parameter space for all inputs except those from a set of Lebesgue measure 0 (Theorem 9). This allows us to show a.s. support stability and generalization error bound for NNs with size that doesn't ' grow with m.
We experimentally verify our theoretical results in Section 6 showing that our bounded Lipschitz and bounded smoothness conditions hold in practice.
RELATED WORK
Several authors have that although NNs are known to generalize well in practice, many different the- oretical approaches have been tried without satifactorily explaining this phenomenon, c.f., Jin et al.
(2020); Chatterjee & Zielinski (2022). We refer the reader to the work of Jin et al. (0200) which presents a concise taxonomy of these different thcoretical approaches. There are also several works that seek to understand what good theory of generalization should look like, c.f. Kawaguchi et al. (017]; Chatterjee & Zielinski (2022). Our own work falls within the paradigm that seeks to use no- tions of algorithmic stability to bound generalization error that began with Vapnik & Chervonenkis 1974) but gathered steam with the publication of the work by Bousquet & Elisseeff (2002).
The applicability of the algorithmic stability paradigm to the study of generalization error in NNs was brought to light by Hardi et al. (2016) who showed that functions optimized via Stochastic Gradient Descent have the property of uniform stability defined by Bousquet Elisseeff (2002). implying that NNs should also have this property. Subsequently. there was renewed interest in uni- form 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. (2020). Some other works, e.g. Klochkov & Zhivotovskiy (202I). took this line for- ward by focussing on the relationship of uniform stability with the excess risk. However the work of Zhang et al. (017)) 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, (e.g. Charles & Papail- iopoulos (2018), to show lower bounds stability that ensure that uniform stability does not
2

---

Under review as a conference paper at ICLR 2023
exists, (e.g. Zhang al. (2022) ) The other strand of research, work falls in this category, fo- cuses on weakening the notion of uniform stability, specifically by making it data-dependent, thereby following the suggestion made by Zhang al. (0077). Kuzborskij & Lampert (2018) defined "on- average stability" which is weaker than our definition of a.s. support stability. Consequently, their definition leads weaker in-expectation bound the generalization error where the expectation is over the training set as well as the random choices of the algorithm. Our Theorem on the other hand, provides sharp concentration bound on the choice of training set. [ei & Ying (2020) de- fine an "on-average model stability" that requires the average replace-one error over all the training points be bounded 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 case of early stopping.
A.S. SUPPORT STABILITY AND GENERALIZATION
In this section we present a weakening of the notion of uniform stability defined by [Bousquet & Elisseeff (2002) and show that exponential concentration bounds the generalization error can be proved for learning algorithms that have this weaker form of stability.
3.1 TERMINOLOGY
Let X' and be the input and output spaces respectively. We assume we have a training set S z of size m where each point is chosen independently at random from an unknown distribution D over 2 C X' V. For z = (x. E we will use the notation æ= to denote x and y/ denote Let R. be the set of all finite strings on some finite alphabet, and let call the elements of R decision strings and let us assume that there is some probability distribution D, according which will select randomly from R. Further, let F be the set of all functions from X to Y In machine learning settings we typically compute a map from T R to F. We will denote the function computed by this map As.r. Since the choice of S and are both random, Ag,r is effectively random function and can also be thought of as a randomized algorithm.
Given bound M > O, assume that we are given bounded loss function é: 3 x y + [0, We define the risk of As as
R(A, = EI-D (((As,(( (12),,)))
where the expectation is over the random choice of point according to data distribution D. Note that the risk is a random variable since both S and r are randomly chosen. The empirical risk of As defined as
Re (A,
Σ (z2))) ZES
S
We interested in bounding the generalization error [R(A,S,)) - Re (A.
3.2 A WEAKENING OF UNIFORM STABILITY
Given S = EZi...., Zm} chosen randomly according to D we choose (Zi+m..... Z2mb also from nm independently from S and, for each E [m)) we define
S = [Zi.....
Zi+ms Zit1...., Zm}.
Definition 1 (Almost (Sure) Support Stability). We say an algorithm As.r has qaalmost support stability 3 with respect to the loss function f(.,.) for Zi...., Zzm chosen i.i.d. according to an unknown distribution D defined over Z,
Vi E [m]] Vz E supp (D): Er [I((As,-<xz) y=) - ((Ast,, (xz), y=]l] S with probability 7). If 1 then we say the algorithm has almost sure (a.s.) support stability 3.
We note that this notion weakens the notion of uniform stability introduced by Bousquet & Elisseeff 2002) by requiring the bound on the difference in losses to hold with a certain probability. 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 the support of D. These conditions make almost support stability data-dependent quantity the lines of the suggestion made by Zhang
3

---

Under review as a conference paper at ICLR 2023
et al. 2017). We also observe that almost support stability is comparable to but stronger than the hypothesis stability Kearns & Ron (999) as formulated by |Bousquet & Elisseeff (2002).
3.3 EXPONENTIAL CONVERGENCE OF GENERALIZATION ERROR
A.s. support stability can be used in place of uniform stability in conjunction with the techniques of Feldman & Vondrak (2019a) to give guarantees on generalization error. In particular we can
derive the following theorem.
Theorem 2.
Let Ag.r be algorithm that is symmetric in distribution and has a.s. stability /3 with respect to the loss function E(.,)) such that O I ((As.((2)) Us) I 1 for all S E 2"m, for all r E R and for all z (T,, ) E 2. Then, there is constant e > 0 s.t. for any m 2 1 and ö E (0, 1), with probability 1 0,
Er (R(S, Ra(S, s (log(m) log
m78 (8
log(1 (
+
m
Proof outline. We give high-level outline here. Feldman & Vondrak (2019b) used two steps to get a better generalization guarantees. The first step is range reduction, where the range of the loss function is reduced. For this they define a new clipping function in Lemma 3.1 Feldman & Vondrak (219a) 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 is done by applying McDiarmid's 's inequality to 3 sensitive functions. Here use a modification of McDiarmid's Inequality (Lemma [2 given in Appendix [A] to get bounds for a.s. support stability. The second step is dataset size reduction (as described in Section 3.3 Feldman & Vondrak (2019ah) which will remain the same for a.s. support stability as this only involves stating the result for smaller dataset and the probability, and then taking a union bound. Therefore both steps of the argument given in Feldman & Vondrak 2019a) go through for a.s. support stability.
4 A. S. SUPPORT STABILITY OF STOCHASTIC GRADIENT DESCENT
A large family of machine learning algorithms follow a paradigm in which the learned function is parametrized by vector
R for some 2 1, i.e., have some fixed function g : R" X - V. The training set is used to learn a suitable parameter vector w E R" such that the value g(w, xx, good estimate of y/ for all = E Z. This value of is learned by running Stochastic Gradient Descent (SGD) using a training set drawn from the unknown distribution. We will say that the size of the training set is m and the number of steps for which SGD trained is T with the parameter vector at step / being denoted un for 0 < & S T. Assuming that T is a multiple of m. the algorithm moves in epochs of m steps. 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..... z - i.e., the random initial parameter vector we from which SGD begin and the set of T/m random permutations used in the T m epochs.
4.1 SOME PROPERTIES OF PARAMETERIZED FUNCTION
In Hardt et al. (2066), proving that the learning algorithm derived by SGD is stable requires smooth- ness and Lipschitz properties of f. but only for partial derivatives taken on R", i.e., on the parameter space. The requirement there that every function in the family of functions =) = E 2) is smooth and has bounded Lipschitz constant. Our key insight is that this requirement is stronger than required. All we need that the functions induced by the data points that we pick to train SGD have these properties. We now present some definitions that encapsulate this idea.
Definition 3 (Almost Locally Parameter Lipschitz functions). Given a distribution D defined over Z. parametrized function f R" x Z + IR is said to be 3-almost Locally L; Lipschitz w.r.t D for some 3 (0, 1] if for any w E R. there exists constants L, > O and > 0 such that, with probubility 3 (over the choice of 2), for all w' E R.,, ||w w|ll < implies
[f(w 2) - f(w, z)] < Lillw' w|].
Note that L, can depend on z. If 3 = 1 then we say that f is almost surely locally L L-paammeter I Lipschitz (a.s. L.-L.PI. short).
4

---

Under review as a conference paper at ICLR 2023
Definition 4 (Almost Locally Parameter-Sme Smooth functions). Given distribution D defined over 2. a parametrized function f : R x 2 R is said to be "yaalmost Ky-Parameter Smooth w.r.t D for some (0, if for any w E I. there exist constants K₁ 0 and e > 0 such that, with probability 7y (over the choice of 2), for all w E IR", |/w' w|] < implies
V
V Vf(w, z) - Ki|/w' wll.
Note that K₁ can depend on 2. If 7 then we say that f almost surely locally K2- Ky-parameter smooth (a.s. Kj-LPS for short).
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:
Lemma 5. Given J : R + R we have that (1) if f is bounded and is locally Lipschitz at finite set of points A S IR", then there is a constant L such that for every pair w, w E AA
[f(w) f(w') | S Lll w')) and
2) if f is bounded and is locally smooth at a finite set of points A S R", then there is a constant K such that for every pair w, w' E A
[V](w) - V((w')) & K||w - w'll.
The proof is in Appendix B
4.2 A.S. SUPPORT STABILITY OF SGD
We now work towards the a.s. support stability of SGD. First state theorem that bounds the replace-one enror of SGD upto a certain number of epochs.
Theorem 6. Suppose we are given labelled data set Z and probability distribution D defined over it. Suppose we huve parametrized loss function J R² x Z - RR that is a.s. La-LPL and a.s. Ki- LPS w.r.t D. Suppose for some T > multiple of m, for each E [m] we run Stochastic Gradient Descent on the f for T/m epochs using training set S of size chosen i.i.d. according to D with random choices r and, parallely, with the same set of random choices v, on a set S wherein the i-th data point 2; of S has been replaced by another data point 2 chosen from D independent of all other random choices and with a decreasing learning rate of 04 S to. Then, for all t > O, we denote by w, and wi the parameter vectors obtained while training with S and St respectively, we have that with probability
LsLg F(T/m) Kg
(m -
E, [f fwwrr =]]
where F(T/m)= := (2T m) /T/L0 and Lg and Kg are the "global" Lipschitz and "global" smoothness constants we get from Lemma ] and Lg is data dependent Lipschitz constant which depends only on points picked according to the unknown distribution D.
Proof outline. The proof follows the lines of the argument presented by Hardt al. 2016) with the difference that we allow for probabilistic relaxation of the smoothness conditions in line with our definition of a.s. stability. Also, note that we have to account for an expectation over the random string r, and that we have been able to extend the argument to multiple epochs. The complete proof of Theorem is in Appendix
Data dependence and I.g. A key feature of the bound presented in equation I is that the dependence on the data is expressed through the data-dependent Lipschitz constant Ls. This constant depends on the training points and the replacement point 2 which is also picked from the data distribution. In general we expect that if the unknown distribution D has low variance then Lg will be small. Further, a line of research in the optimization literature has shown that the gradients associated with SGD decay as training proceeds, even for non-convex loss functions, c.f. Section 4 of Bottou et al.) 2018). Therefore we can conclude that the a.s. stability bound of equation D is closely connected to the data distribution and is likely to be useful for cases where SGD returns a meaningful solution and vacuous for bad cases like the one presented by Zhang et al.) (2017).
Corollary 7. For learning algorithm that is symmetric in distribution and trained described in the statement of Theorem 6 under the condition that Ly is a constant w.r.. m, there is a constant > O that depends on ogg and K, such that if it is trained for most e clog m epochs the expectation
5

---

Under review as a conference paper at ICLR 2023
the generalization error the algorithm taken over the random choices of the algorithm decreases as (m-(1-00)) (1-0gKg)) + m m1/2) with probability at least - -1/m over the choice of the training set
if on < g)))
Proof. It is easy to check from Theorem 6 that with the conditions given in the statement of Corol- lary 7 the learning algorithm has a.s. support stability 3 where 3 is o(1/m) if ag < 1/()))- We can therefore apply Theorem 2 with 5 1/m to get the result.
If we compare this corollary with Theorem 4 of Kuzborskij & Lampert (2018) we note that their analysis requires an ag that decreases with m whereas our analysis allows for a value of og that is constant. Importantly, their analysis bounds generalization error only up to the end of a single epoch whereas we can bound the error well beyond that. Kuzborskij & Lampert (2018) also require the Hessian to have bounded Lipschitz constant, i.e., the third derivative of the loss function has to be bounded. We do not need this constraint.
NEURAL NETWORKS WITH RELU ACTIVATION
The main result of this section presents the conditions required for low generalization error for Neural Networks with ReL.U activation:
Theorem 8. For neural network with ReLU activation and oulput neuron, trained on set S E D using SGD for T steps, where D is over TR x y, such that y is countable and for each y E y we get a countable set {xr Rdd PrD (lab(x) = 0} where lab(x)) is label of x. For doubly differentiable loss function with bounded first and second order derivatives and learning Su, If the data points of S and the spectral norms of weight matrices explored by SGD are bounded, and Lg and Kg are the "global" Lipschitz and smoothness constant and Ls is the date-depnndent Lipschitz constant then,
rate a +
E, E| (c( o
0 [Lsg (IsT, F(T (m) log(m)2
log(m) m
Kg ml-agk,
with probability at least 1 1/m, where F(T/m)= = (2T/m)ooks 27/m
The proof of the theorem is at the end of Section 5.1
First we will now establish that the theory of a.s. support stability applics to NNs under the condi- tions specified.
5.1 SUPPORT STABILITY OF NEURAL NETWORKS WITH RELU ACTIVATION
The key to showing the support stability of NNs with ReLU is to establish that they are parameter- Lipschitz and locally parameter-smn smooth We show that this happens with good probability.
Theorem 9. For every w E IR"", doubly differentiable loss function, E R X E. applied the output of a NN with ReLU activation is locally parameter-Lipschee and locally parameter-sman smooth for all x E Rdd except for a set of measure O.
Proof outline. The proof of this theorem is based on the argument that for a given w a point of discontinuity exists at given neuron if the input lies in the set of solutions to family of equations, i.e. in a lower dimensional subspace of Rd. This proof is an adaptions of an idea of Milne (2019) and can be found in Appendix C
Theorem 9 begs the question: How large are these Lipschitz and smoothness constants? We provide some general bounds that can be improved for specific architectures:
Proposition 10. Suppose we have a fully connected NN with ReLU activation at the inner nodes that has depth H + 1. Then, if the spectral norms of weight matrices are bounded for every layer Le.. [W'l,, |lo I 8s, Vi E [H), and size of each layers be ido....,dt then,
11 |
H
I.g S
Σ
(di-1 d.)
||c||
6

---

Under review as a conference paper at ICLR 2023
The proof of the proposition is in Appendix C The bound Lg should be compared to the bounds given in the context of Rademacher complexity by Bartlett et al. (2017) and Golowich et 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.
Proof of Theorem [ Theorem tells us that a NN with ReLU activations is locally parameter- Lipschitz and locally parameter-smmothh From Proposition T0
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 Lipschitz constants and smoothness constants associated with the NN's training are bounded w.r.t. m. With all these in place we can apply Theorem 6 to get the a.s. support stability followed by Theorem 2 get the desired result. The bound on the smoothness constant also tells us that the constraint on ag needed to apply Corollary / is not too stringent, i.e., og can be chosen be a value that is constant w.r.t. m.
5.2 DISCUSSION
Several of the constraints we have placed above are only for ease of exposition. We discuss which of these constraints can be removed.
Removing the fully connectedness constraint. Although Theorem g is stated for a fully connected network, it can be applied to networks like CNNs which have partially connected convolutional layers with intermediate pooling and normalization layers (e.g., LeNet, AlexNet, etc.). In such cases the symmetry distribution condition required for Theorem holds as long as the training set is chosen i..dd from the unknown distribution.
Adding regularization terms to the loss function. Several popular regularizers, the &g regularizer being a prominent example, are doubly differentiable and therefore Theorem 8 can be applied when such regularizers are used along with a doubly differentiable loss function.
Activation functions apart from ReLU. We present a comprehensive treatment of ReLU activation but that does not mean that our results are restricted this kind of activation. Non-linearities like max-pool can also be handled in our framework by proving that, like with ReLU, the points of discontinuity of such a non-linearity also lie in a set of Lebesgue measure 0.
The case of multiple outputs Although we state the Theorem X 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.
What about overparametrication? ? The question put by Zhang et al. (2017) as rearticulated by var- ious authors, including CCatterreee Zielinski (0022), can be put as follows: How do we speak theoretically about generalization in the overparametrized regime where NNs often generalize well even though they have enough parameters to overfit? (Chaterrje & Zielinski (2022) make the point that some property of the training is at play here, claim more specific than the general claim that there is some property of the data distribution that has been missed. These are related, of course, but it is our feeling that more fine-grained analysis of the growth in the replace-one error is required. We feel that it is possible to look at the local Lipschitz and local smoothness constants in greater detail taking both network structure and input point values in mind. We hope that the polynomial characterization of the NN presented in Section C.1.2 will help this process. We conjecture that it may be able show that for certain distributions the constants actually improve (decrease) as the training proceeds, and this could lead to proof of a.s. support stability in these cases.
6 EXPERIMENTS
In this section we will experimentally show that the Parameter Lipschitz and Parameter Smoothness constants that we reasoned with are indeed bounded, and that the thcoretical upper bound that we derived for the generalization error of neural network holds in practice.
Setup. For our experiments we use MNIST and FashionMNIST datasets. In both datasets, we randomly selected 20, 000 training and 1, 000 as test points. All experiments were conducted using a fully connected feed forward neural network with single hidden layer and ReLU activation. We train the model using SGD (batch size 1), with cross-entropy loss, starting with randomly
7

---

Under review as a conference paper at ICLR 2023
60
Parameter Lipschitz
100
Empinical Max
Parameter smoothnees
Max Max
80
80
Empirical
Parameter Lipschitz
30
Parameter smoothnness
20
10
20
2500
5000
7500
10000
12500
15000
17500
20000
2500
5000
7500
10000
12500
15000
17500
20000
Number of Datapoints
Number of Datapoints
(a) MNIST
(b) FashionMNIST
Figure I: Maximum of the Lipschitz and smoothness constants at every (= 20) interval of updates of SGD (we plot both the running average and the highest value found so far). Notice that these constants have clear upper bound throughout the training process.
initialized weights. As suggested in our analysis we use decreasing learning rate o₁ = ao In each epoch we consider random permutation of the training set. Ly and Kg are computed by calculating the norm of gradients and Hessian across the training steps and taking their max.
Experiment 1. Our first experiment is aimed towards establishing that the "global" Lipschitz (I,g) and smoothness (K₂) values estimated using local values at each step are bounded. Figure sum- marizes the results of these experiments over MNIST and FashionMNIST datasets (at- 0.001).
The plots contain the maximum of the local parameter Lipschitz and smoothness values obtained after running each experiment 10 times with random weight initialization. These results support Theorem [9] since the upper bound values quickly stabilize and do not grow with the size of train- ing set in both datasets. Similarly, the bounded smoothness constant supports constraint on the learning rate, Og S. TK." We find Lg to be 8.1174 (MNIST) & 12.5737 (FashionMNIST), and K₂ to be 58.185 (MNIST) and 7096 (FashionMNIST).
Experiment 2. We now turn our attention to the experiment to support our main result, i.e., the empirical generalization error estimated using validation set is upper bounded by our theoretical upper bound. We first split each dataset in 20:1 ratio into training and validation set, and train the model varying size of training set. We empirically compute the generalization eπrоr each training set size using the validation set. Figure 2 compares this empirical generalization error (in red) with the theoretical upper bound (in Flum) these results, decreases along with the generalization error thus empirically validating our reasoning.
see that our bound
7 CONCLUSION
We have devised a theoretical framework in this paper for using algorithmic stability to prove gen- eralization bounds for NNs with ReLU nonlinearities. We feel that possible prove stronger results in this framework than the ones we have presented here, and more widely applicable ones. Immediate lines of research that suggest themselves are apply our methods for CNNs and to investigate what other architectures can be approached with our method. It would be particularly
Generalization erroo
10a
Theoretical Upper Bound
Generalization error
Theoretical Upper Bound
109
Observed Ganeralzazion Bror
Observed Ganeralzazion Eroo
1.9
10-9
10-
20-1
10-9
10
2500
30209, 12009y2500,0000 yoont 17500 g00n0 Number of Datapoints
5000
5000 y2500 ysotf 175,00 p0250 Number of Datapoints
(a) MNIST
(b) FashionMNIST
Figure 2: Comparison of empirical generalization error (red) vs. theoretical upper bound (bluc) with varying training set size for different datasets.
8

---

Under review as a conference paper at ICLR 2023
interesting to see if there is some analog of polynomial characterisation for GNNs. Another clear challenge is the overparametrized case. We have not been able to tackle but we feel a more fine-grainee analysis in our framework may possibly lead to such a result.
REFERENCES
Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. neural networks. In Proc. Advances in Neural Information Processing Systems 30, pp. 6240-6249, 2017.
margin bounds for
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Rev. 60(2):221-477, 2018.
Olivier Bousquet and André Elissceff. Stability and Generalization. J. Mach. Learn. Res., 2(Mar): 499-526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. Proc. Machine Learming 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 Machine Learning, volume 80 of Proceedings of Machine Learn- ing Research, pp. 754. PMLR, 10-15 Jul 2018. URL https: settps://proceediingg mlrr. ctess/v80//carrlle
html
Satrajit Chatterjee and Piotr Zielinski. On the generalization mystery in Deep Learning. arXiv:2203.10036, 2022.
Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. In Ad- vances in Neural Information Processing Systems, 2018.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algo- rithms 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 2019a. URL https: ftttps://proceediime agg.iiigg... mmr.. pIess/v99/E0e amanlllmanlln 9a html
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algo- rithms with nearly optimal rate. In Alina Beygelzimer and Daniel Hsu (eds.), Proceedings of the Thirty-Second Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pp. 1279-1279. PMLR, 25 Jun 2019b. htt.::tt////// phttps:://rooceeigg..t press/ v99 feldman1 9a html Supplementary section.
N. Golowich, A. Rakhlin, and O. Shamir. Size-independent sample complexity of neural networks (extended abstract). Proc. Machine Learning Research, 75:1-3, 2018
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochas- tic gradient descent. In Maria Florina Balean and Kilian Q. Weinberger (eds.). Proceedings of The 33rd International Conference on Machine Learning. volume 48 of Proceedings of Machine Learning Research, pp. 1224-1234, New York, New York, USA, 20-22 Jun 2016. PMLR. URL https::/proceedingg mlr www.srresssseee w48/hardt16...e.
Geoffrey Hinton, Deng, Dong Yu, George E. Dahl, Abdel-rahman Mohamed, Navdeep Jaitly, Andrew Senior, Vincent Vanhoucke, Patrick Nguyen, Tara N. Sainath, and Brian Kingsbury. Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine, 29(6):82 97, 2012. doi: 10. 109//MP.2012..2555599.
Pengzhan Jin, Lu Lu, Yifa Tang, and George Em Karniadakis. Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness. Neural Networks, 130: 85 99, 2020. ISSN 0893-6080. doi: http:///liirrr/o...oo///oeoeemoa 7/www. cedeiii rect. com htt.e//cww....ccc.oooooaaaaaaaaa
URL hetps:

---

Under review as a conference paper at ICLR 2023
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. CoRR, abs/1770.05468,, 2017.
M. Kearns and D. Ron. Algorithmic stability and sanity-check bounds for leave-one-out cross- validation. Neural Computation, 11(6):1427-1553 114 1999.
Yegor Klochkov and Nikita Zhivotovskiy. Stability and deviation optimal risk bounds with conver- gence rate o(1/n). In Advances in Neural Information Processing Systems, 2021.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. berger (cds.), Advances in Neural Information Processing Systems, volume 25. Curran Asso- ciates, Inc., 2012. URL /tttps::/ppooceedngg... neurips http://sse..eaa.ooccocoop//////a cc/pp/////////2////1ee pdf
F. Pereira, C.J. Burges, L. Bottou, and K.Q. Wein-
Iia Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent.
In Jennifer Dy and Andreas Krause (eds.). Proceedings of the 35th International Confer- ence Machine Learning, volume 80 of Proceedings Machine Learning Research, pp.
2815-2824. PMLR. 10-15 Jul 2018. URL https: https: http::://prcccecings...m mlr wwt.mm.............
kuzborski 1 118a. html
Yunwen Lei and Yiming Ying. Fine-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 Proceeedings of Machine Learning Research, pp. 5809-5888 5819. PMLR, 13-18 Jul 2020. URL https::/ppoccedddi.iicee mlr ptess/v119/ lei20c. html
Tristan Milne. Piecewise strong convexity of neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL /ttpss//pproeeddagg... neurips. cc/ ht//paper/2099/11le/ (31230000003d0155191110222223223
pdf
Vladimir Vapnik and Alexey Chervonenkis. Theory of Pattern Recognition. Nauka, Moscow, 1974.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference on Learning Rep- resentations, 2017. URL htt.ttttss:////ttttt
/tctpp:://pperreviee http://pprr/////ee/ net. forum? F 6=Sy8gd59xx
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. httpst /pwnnevvewww..ceeooeepeepe.eeewe net. net/forum?
id=S1 @d=$1-2m00 151g
A MODIFICATION OF McDIARMID'S THEOREM
We first define a probabilistic weakening of Lipschitz functions.
Given 2m i.i.d. random variables XI,...y X2m drawn from some domain Z ac- cording some probability distribution for some 3 >> O and [0, 1}, function J 2m I is called 1) alamost
Definition 11.
3- B-Lischhit w.r.t. D if Xmm) (X1.... X,-1,
Vi E (1....,,.))......... mm : If with probability at least n7. In case т = we say that f is almost surely 3-Lipschitz w.r. D. When D is understood will omit and for the case n we will simply write that f is almost surely (or just a.s.) B-Lipschitz.
We now state a modified version of McDiarmid's theorem that holds for n-almost 3-Lipschitz func- tions.
10

---

Under review as a conference paper at ICLR 2023
Lemma 12. Let X1...., Xm be i.i.d. random variables. f is n-almost B-Lipschitz and takes values between and M, then,
-26
Pr( Xm) Elf(X Xm)l 2 e) S exp
7).
((1 11,3 Mn)
For simplicity, we adopt the notation A.j = A................ A, (i.e. with subscript (i.j) we represent j - i + 1 variables) and A; represents only one variable in the rest of the section. Before prove Theorem [2] we state and prove the following lemma:
Lemma 13. Let f z + I be function such that 0 S f(:) < M. Define V; Es+1. [f(X1.m) Emm m))) where Egg [ denotes Ex.... .x, H. Then, if is r-almost B-Lipschitz, then with probability 1 - T, Vi, Vi
n)B3 + n.M
Proof.
Vi 1,+1,m 1,m [f(Xi,m) mm I mm
ff... f(X1, M1 Dm
f(X1, Vi 1i+1. (dtt))ddd((+(111.
gi 11 Mo
[[XX,,
f(X1,) - Jdpaddd ydu(ys) dp((i+1.m)
9641 Mm
where μl is the measure associated with the random variables. Thus, V4, function of X1, is is an pectation over the random variables F6+1,m Thus, we can write V; = Egerr... [ 3im (x1.)
Now, let's define two sets follows:
S (x Z' By E mm ((x,)) S 33
S = (y zn 112 v) S 3}.
Then, since is mpalmost B- B-pischhit and renaming V/2 as v in 4, since they are i.i.d., for any x E Si, we have
Σ (v] B 1- 11 11-Ep(un pr( M,
E ([0 S
VES,
MES
and for any x & S, we have
E { /x| M.
We further note that E zES, Pr (r 1- 77, and Σves; Pr {y} 1-1), Therefore, applying these
bounds to Equation 2
get, with probability least 7),
V. 5 (1 7)3 + n.
Proof of Theorem We will use Azuma's inequality to prove the result. First we show that the sequence V1, V. is martingale difference sequence with respect to 11, To see this, we first notice that V, a function X1, Also, E [[]]]] is finite since is bounded. Finally, 1.m [E [f(X).m)] Eg,. [f [X,,]]
[V441|X1,
=0
Let E be the event that (f - E ( 2 c, and F the event that V; is bounded by 8(1 11 + m,M. We have.
Pr [E) < Pr (EF) (F) + Pr (F) Using Lemma 13 we have that with probability
(3)
for all i, V, is bounded by 3(1 n)) + r.M. Applying Azuma's inequality Pr FE.F). we have the result.
B A.S. SUPPORT STABILITY OF SGD PROVED
Proof of Lemma 3 If ff is locally Lipschitz at w E A, there an Eur > and an L, > 0 such that --wwll, w'll. So, let us turn attention
for all u' R with [ w/ll Ew, If(w) f(w')l T /w
11

---

Under review as a conference paper at ICLR 2023
to those w' A that lie outside the ball of radius Ew around w. Note that for such w if 0 the bound on f. we have that
[(()) - s(w')) 1| - w'll -
2B
Ew
Therefore the "global" Lipschitz constant for f within A is max TT 2B/Sw w E A} which bounded since is finite. This proves the first part of the lemma. The second part follows similarly.
Proof of Theorem For some E [m]] we couple the trajectory of SGD on S and S where 2; E S has been replaced with z/. Our random string in this case is a random choice of an initial parameter vector, Wo, and random set of T/m i.id permutations No. ........ #T/m-1 of [m] chosen uniformly random. We use these random choices for training both the algorithms with S and St. For 0 S j & T/m 1, we denote " (i) by Ij. i.e., 1 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
8. = ||,, wn/ll=
for 1 s T. If we can show that E, [Ør] bounded by some quantity B almost surely, we can invoke the fact that f is a.s. Li-LPL to say that |[ [f(w; z) - f(w), S Lg for all E supp (D), where Lg is the "global" Lipschitz constant we get from Lemma which is defined for all 2.
We argue differently for the first epoch and differently for later epochs. For the first epoch we note that for / < To. & O since SGD performs identical moves in both cases. At / = To +1 01,+1 = w a. V ffWw..
(w', -a V ffw',, 2 = au, lV.lVV 2,) f =|)ls where the second equality follows from the fact that w1. = w/ by the definition of Ig- Using Lemma 5 we say that 0 I 2a Ls almost surely. Notice here used data-dependent Lipschitz constant Ls which is only defined for points in set S unlike "global" Lipschitz constant. Now,
81++2 S - + a0.+1111VV f(wool 2.) V Vf(w
Here although the parameter vectors W1+t1 and w are not the same, 1xo(To+1) and z! *xo(To+)) are the same by the definition of To (assuming that Lo # m). Therefore we get that
81o+2 S 816+1 + 001++1 K5
with probability since, from Lemma 5 we have that f has a "global" smoothness property for the entire of most 27' parameter vectors that will be encountered during the coupled training of S and St. Noting that a similar recursion can be applied all the way to the end of the first epoch, ie. till get
8m < 20 Ls
II t=1++1
(1 + acKg)) S Lsj,Leepp
Σ
Kg
(4)
t= +=
with probability Moving on to the next epoch we note that we can make the argument above till the next point where the two training sequences differ, i.e., till the m + I1 + 1st step. At this point we have,
8mth++1 S 8m+H, + am+ | ff(Wwm,,, 24) - ff( +
Since neither the parameter vector nor the training points are the same in the second term, we have no option but use the almost data-depnndent Lipschitz constant to say that
im+li+1 S 8m+hi + am+ 2Ls.
Since a O. observing that our current bound for 6m-1, larger than am+1 2Lgg. There- fore
8 8 < 20m+
So, that in the second and subsequent epochs, for time step jm + + have the bound
1 1, T/m
8m 1,+1 & 20m
and for all t > + I,,t o I
11/m-1 we have, as before, by the smoothness property that d+1 (1 a441 Kg)-
12

---

Under review as a conference paper at ICLR 2023
Therefore, we have that
}
2T oo
m mo K
ôT S (2))) _h
exp Σ agKg CgLs2
(5)
(L 10) 1
dt=lo dt=lo+1
where, in the first inequality for ease of calculation we have retained the terms of the form (1 + a1, Kg,KK), 2 S j T/m /m in the product on the right although we can ignore them. In the second inequality we have substituted ag = on/t and used the fact that log n I H, I log 2n for the n-th Harmonic number Hn.
Finally, in order to compute E, [ōr] we observe that, since mo is uniformly drawn from the set of permutations of (m)) To is uniformly distributed on [m]] Summing up the last term of over lo E [m] and dividing further by we get the result.
C NEURAL NETWORKS: CHARACTERIZATION AND PROOFS
In order to prove Theorem we first need to describe a characterization of Neural Networks that allows us get better insight into their smoothness properties. We present the characterization in Section C.I and the proof Section C.2
C.I A BAAYNOMIAL-BASED CHARACTERIZATION NEURAL NETWORKS
C.1.1 NEURAL NETWORK TERMINOLOGY
Neural networks provide a family of parametrized functions of the form we have discussed in Sec- tion 4 The parameter vector w E R² is applied over a network structure with layers. In this case we specify Z to be Rd x R, i.c., the data points are from Rd and the label is from IR, i.c., the NN has single output. We will denote the depth of the network by H. The layers will be numbered O to H with layer O being the input layer. The number of neurons in layer i will be hj For this discussion we assume a fully connected network. We will denote by wi.k the weight of the edge from the j neuron of the ith layer to the kth neuron of the + 1st layer. For the NN with parameters w at point a E Rd we will denote the input into the jthh neuron of the ith layer by (ns.j(us æ) and its output by out,,
.²) These will be equal only if the former is non-negative. 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, æ). For each of exposition we will assume that out(w: (w, x) = 1 in nww x)) > 0 and 0 otherwise, i.e, there are only two labels in y
1.2 MULTIVARIATE POLYNOMIALS ASSOCIATED WITH A NEURAL NETWORK
Given a set of indeterminates x = Zi...., Ft, let P(x) be the set of multivariate polynomials on .1,..., 2t with real coefficients. For any polynomial p(æ), i,, ig [4] and any .i,.... : 0g E IR for some g < I, we will denote by p(æ) {s1, [i } the polynomial in P(x { ,.,. .r,,)) } that is obtained by setting all occurences of 2ı, ay in p(x)) ). In particular, p(z)) {a==0} is the polynomial p(xx) with all monomials containing x; removed, and p(x) (=.=1) } retains all the monomials of p(x) but those monomials that contain x; appear without the term 24.
Returning NNs. let us consider two sets of indeterminates: x { E [d]} and w {w < i H, 1 < j < k; < < k4t } and Kg = d. For a fully connected NN defined in Sec. C.I.1 we will say that it has the following polynomial associated with it:
Ao ky
ky
o w. x)
Σ j8-1=1
Iio w Jo
j1.d2
w
(H-1) 1.11
jo=1 j==1
Note that the output layer has only one neuron. We will refer this the base polynomial of the NN. The base polynomial associated with the jthh neuron in layer can be derived from the base polynomial of the network as follow
13

---

Under review as a conference paper at ICLR 2023
(1, xz) ((w,)) x) ful 20, www.
-=--1 k
Due to ReLU activations varying different points there is single polynomial that captures the output of the NN everywhere in Rn x Rd However, the following observation shows a way of defining polynomials that describe the output over certain subsets of the space.
R and + (0....,0) 0) E Rd, i [H] and j E [ky] such that 3n (w, x) o 0 for all $ h S i and all 1 S 12 I ki, there is a e > depending on w. a such that, for all w' with || w'll < E,
Observation 14. Given
in..j (w', a)) = o ..) = $1.5 (w', ..) {wigh o0t
11] and in mag (wn. co)
Proof. Since in (w,, ax) is strictly separated from 0 and there only finite number of neurons in the network, there must be a E small enough for which all open ReLU gates remain open and all closed gates remain closed. It is easy verify that the description of out(w', æ) given above is correct since it simply sets to 0 all the variables corresponding to weights originating in neurons whose ReLU gate closed.
C.2 PROOF OF THEOREM 9
Proof of Theorem ent purpose. From Observation 14 it follows that if we have * (o....,0) 0) E Rd such that ( x) # 0 for all S H and all 1 S S k2 then out(w, x) is, in fact, just the polynomial 6(wr,, , 2)) 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 x.
The idea behind this proof is due to Milne (2019) who used it for differ-
So now let us consider the set of points x for which is the smallest layer index such that in (w, x) 0. case there are two such indices, we break ties using the neuron index j. By Observation 14. in neighbourhood of w. (n.j(w, æ) is polynomial in w and æ for each æ.
Now, we consider two cases. In the first case, out;-1.j' (w, a²) for j' E [ki-1], i.e., all the ReLU gates from the previous layers are closed because in;- (me, .)) < 0 for all j' E [ In this case out(w', x) = everywhere in the neighbourhood guaranteed by Observation 14 and therefore ((ou((w' .x) lab(x)) is doubly differentiable in 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 it. We note that this argument is easily portable the case of more general label set y with the property described in the statement of Theorem g since in will be everywhere in a small neighbourhood.
In the second case we have some j' E [k;-]] such that out; o x) > 0. Let Ci2 S Rd be those = 0. Since we are working with a specific value of w, this simply becomes a polynomial in æ. In fact, inspecting the definition of base polynomials we note that when w is fixed (w, x) is simply a linear combination of 3i, ..., a- This implies that Ci. hyperplane in Rd. We note that this argument can also be made of the output node under the condition on the labelset given in the statement of Theorem because for (H.i(w, x) to give a value that lies on the boundary between two sets with different labels for a given w. x must be drawn from a set of Lebesgue measure 0.
for which this case holds. C.j contains the solutions to in:,j
Since the network size is finite the set of all possible values of for which case 2 occurs, i.e., Use(An.SE]kJ) Cr. is a finite union of hyperplanes in Idd and therefore a set of Lebesgue measure O.
Let us consider partial derivative w.r.t w For this let Th,, i be the matrix of size W such that all 14,,,111,44 = -1 and rest all entries are zero. So we can write the partial derivative as,
Proof of Proposition TO
De(w m)
WH WH-1 Wi+1 x T Wi-1 W
(1)
14

---

Under review as a conference paper at ICLR 2023
Although have scalar values both the side, take spectra norm (Il-Il>) on both the sides, and upper bound R.H.S by product of individual norms.
Öp(w. x) aw Now taking |/112 over gradient vector we get the desired result.
x ||
D REPLY OF REVIEWS
D.1 REVIEWER 1, UXNU
& the authors may need provide some examples to quantify how weak and how much im- provement we can get by using this weaker version of stability
The standard definition of stability cannot handle non-linearities. We are giving a much weaker version of stability to widen the usability of stability to more realistic frameworks. Specifically when non-linearitie, are used neural networks cannot be globally parameter Lipschitz and smooth, so in order to fit this assumption we used a.s. support stability allow for the absence of smoothness with small probability.
& What's the difference between Theorem 7 and the generalization results in [Hardt et al., 2016), if igmoring the difference in terms of the assumptions?
Yes, Theorem 7 and Generalization result of Hardt et al looks similar but this probabilistic approach widens the application of stability, we used the a.s. version with v) = O which allowed us to give generalization bound for neural networks with non-linearities like ReLU. Moreover support stability allows for data dependent assumptions over S and the replaced point z, Notice now have added more stronger generalization error bound for a.s. support stability in Theorem 4
&. It seems that the major goal of Section is (1) verify that Assumptions (Definitions 4 & 5) are satisfied. Then why Section 5.1.1 and Section 5.1.2 are necessary, at least in the main part of this paper?
We thank the reviewer for catching this. We have moved the material from Section 5.1 to Appendix.
? As claimed in the beginning of this paper, one potential advantage of the developed theoretical framework is to leverage the information of data distribution, or simply, the support of data distri- bution. However, I do not see this in the theorem or discussion after the theorems. I believe this should be key point of the new theory. so the authors may need to thoroughly discuss whether or how considering this point can give better generalization results.
We thank the reviewer for pointing this out. In fact our results had the potential for making a clearer connection with data dependence and we have now established it. The stability bound of Theorem now has data dependent Lipschitz constant I.g in it. We have added discussion below Theorem on how this allows us to argue that for "good" unknown distributions we expect our stability bound to be good. Here "good" can either mean that D has low variance can mean that it is distribution for which SGD converges.
? The definition of i.j(wx) needs more explanation, why this definition is useful and how to leverage
it should be particularly discussed.
? In Observation 10, why the results do not rely on the negativeness positiveness of ini,jww', x)?
& Novelty seems good, but it still lacks a thorough comparison with prior works.
D.2 REVIEWER 2, 8TFR
? This is because the paper's results are mostly based on the assumptions the local Lipschitzness and smoothness of the loss function, and there are very few assumptions on the data distribution which is the key the good generalization performance of deep convolutional nets image data
15

---

Under review as a conference paper at ICLR 2023
& the smoothness coefficient of standard deep neural networks could be extremely large in practice, which makes the generalization bound overly large for actual deep learning experiments.
? Theorem 9 is asymptotic convergence result and does not provide non-asymptotic generaliza- tion error bound that holds for finite training data.
i The paper's experiments use a one-layer neural network with ReLU activation (the width of the network is not specified in the text). This setting seems too simple for experimenting the gener- alization framework, and that would be better to include numerical results for more realistic deep learning problems, e.g. a deep CNN or ResNet applied to a more challenging image dataset.
D.3 REVIEWER 3, GUYV
& The authors are required to clarify why the "a.s." is helpful. Is designed match the zero- measure nonlinear points in the activation functions?
He has answered his own question! But we need to discuss further. Discuss example presented for UXNu.
& the paper needs a proof sketch in the main text. Based on the sketch, the authors need to elarify the significance and difficulty of the proofs.
& the authors are required to give more detailed discussion on the differences and advantages of the a.s. support stability with the many existing stability measures.
i To me, the proofs are quite straightforward: the relationship between the stability and the general- ization bound needs merely an additive decomposition on the probability compared with the existing results; the a.s. locally smooth and a.s. locally Lipschitz continuous are straightforward given the nonlinear points in ReLU are of zero measure; and the a.s. support stability of the whole ReLU net- work comes from (1) the stability of a single layer (linear mapping of the weight matrix + a.s. linear mapping of the ReI.U) and (2) composition of the multiple layers. These undermines the quality of this paper. Please correct me in the responses if was wrong.
Response: We request the reviewer take closer look at the proof of Theorem 11. The proof is more complicated than he thinks, it is not, in fact, a composition of stabilities across layers. It is deeper case analysis. Hopefully this will convince the reviewer that the mathematical content is non-trivial. We also request the reviewer to appreciate that from modifying McDiarmid's theorem to analysing SGD to showing the smoothness of ReLU, we have connected a number of different concepts. Often deep mathematics involves building a big structure out of a large number of small steps.
While the authors give estimates for these constants, the upper bounds grow as linear function of the number of parameters, and an exponential function on the depth. This implies these results can only apply to neural networks with small complexity. An advantage of stability analysis is that can imply dimension-independenn bounds. However, the results of this paper does not inherit this property.
& in the recent analysis generalization bounds for the order (llg((m) + 11/m) have been developed for 3-uniformly stable algorithms, which is much better than the bounds in Thm 3. While Thm 3 considers a relaxation of uniform stability, the results do not recover the existing bounds if 1) = 0.
HP: Our a.s. Support stability also be directly used in conjunction with Feldman and Von- drak's techniques. We have added a theorem stating this in Sec 3.4 and given a proof outline in the appendix.
? The upper bounds of Thm also seem to be suboptimal. For example, if 0=0 we expect the gen- eralization error to be O. However, in this case, the upper bounds there become O(L.g22T/m/(gmm)
We have fixed it thankyou for pointing it out.
? Furthermore, the step size is of the order O(1/t.. The step size decays very fast for which the training errors by SGD decay very slowly. Therefore, it is hard to find a good model with this step size scheme.
16

---

Under review as a conference paper at ICLR 2023
? If we combine Proposition 12 and Thm 7 together, the generalization bounds would involve O(n K2H), where n is the number of parameters and H is the depth. It seems that this approach does not show advantage over complexity-baseee approach. For example, size-independent generalization bounds have been derived based on Rademacher complexity analysis, see, e.g., Ref [1,2]. There- fore, it is not quite clear to me the usefulness of the support stability since there applications. would suggest the authors to make a detailed comparison between these bounds.
convincing
2. Section 4: In 3.1 should be in Section 3.1 i. Section 4: and and i Thm 9: what is the meaning of ab(x) ž Section 5.3: it is possible look ? Proof of Thm 7: you define t= - - wt']- According to the proof, it seems that t= wt' & Proof of Thm 3: "the concavity of the absolute value function" should be "the convexity of absolute value function"
17


Reviews:
[{"review_id": "wkQTNUPRnz5", "reviewer": "Reviewer_8Tfr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper attempts to prove algorithmic stability-based generalization error bounds for neural nets with ReLU activation functions. To do this, the modified definition of \"Almost (Sure) Support Stability\" is proposed, which weakens the standard uniform stability definition and requires it to hold with a certain probability over the support set of real data. Theorem 3 shows that a previously-known stability-based generalization bound can be modified using the new definition. Next, the paper defines almost locally Lipschitz and smooth functions, and Theorem 7 shows that assuming a bounded almost locally Lipschitz and smooth coefficients, a generalization guarantee will hold for the SGD optimizer where the number of epochs can be as large as $O(\\log(m))$ with $m$ being the number of training samples. Finally, Theorem 9 uses the notions of almost locally Lipschitz and smooth functions to prove an asymptotic convergence guarantee for ReLU-based neural nets.", "summary_of_the_review": "This paper aims to extend the algorithmic stability generalization analysis to ReLU-based neural networks by defining and analyzing the notion of almost (sure) support stability. While the paper is well written and the analysis takes some steps toward the goal of understanding the generalization of ReLU-based networks, I still think the paper's results are not sufficient to properly bound the generalization error of standard deep neural networks in practice.  ", "strength_and_weaknesses": "Strengths:\n\n1) The paper is well written, and the presentation is clear and satisfactory.\n\n2) The proposed theoretical framework seems useful for proving generalization error bounds for neural nets with non-smooth activation functions such as ReLU.\n\nWeaknesses:\n\n1) I do not find the paper's results adequate to answer the introduction question: \"Is there a reasonable definition of stability that incorporates distribution properties and leads to small generalization error?\" This is because the paper's results are mostly based on the assumptions on the local Lipschitzness and smoothness of the loss function, and there are very few assumptions on the data distribution which is the key to the good generalization performance of deep convolutional nets on image data. In addition, the smoothness coefficient of standard deep neural networks could be extremely large in practice, which makes the generalization bound overly large for actual deep learning experiments.\n\n2) Theorem 9 is an asymptotic convergence result and does not provide a non-asymptotic generalization error bound that holds for finite training data.\n\n3) The paper's experiments use a one-layer neural network with ReLU activation (the width of the network is not specified in the text). This setting seems too simple for experimenting the generalization framework, and that would be better to include numerical results for more realistic deep learning problems, e.g. a deep CNN or ResNet applied to a more challenging image dataset.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "fllvYM3lwX", "reviewer": "Reviewer_UXnu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to establish a sharp generalization error bound for NN with ReLU activation when the network size doesn’t grow with the training set size. This paper provides a weakened version of uniform stability and proves the generalization guarantees of SGD for training over locally Lipschitz and smooth objectives. Moreover, the authors apply the developed generalization analysis to prove the generalization bound of SGD for training NN with ReLU activations, which yields a vanishing generalization bound when the NN size doesn’t grow with the training sample size.", "summary_of_the_review": "Overall this paper gives some new notions and analyses for studying the generalization of SGD. However, I am not fully convinced by the novelty and contribution of this paper as some discussions and comparisons to prior works are missing.", "strength_and_weaknesses": "Strength:\n* This paper provides a new notion of algorithmic stability, which is weaker than prior works and can lead to a meaningful generalization error bound.\n* This paper proves the generalization of SGD under a new set of assumptions on the training objectives including “almost locally Lipschitz” and “almost locally smooth”.\n* This paper further establishes the generalization of SGD for training NN with ReLU activations by showing that the objective function satisfies the almost locally Lipschitz/smooth conditions with certain parameters.\n\nWeakness:\n* I can understand that involving the almost sure definition and considering the support of $D$ can certainly weaken the original definition of uniform stability. However, the authors may need to provide some examples to quantify how weak it is and how much improvement we can get by using this weaker version of stability.\n* What’s the difference between Theorem 7 and the generalization results in [Hardt et al., 2016], if ignoring the difference in terms of the assumptions?\n* The neural network terminology in Section 5.1 is confusing. It seems that the major goal of Section 5 is to (1) verify that Assumptions (Definitions 4 & 5) are satisfied. Then why Section 5.1.1 and Section 5.1.2 are necessary, at least in the main part of this paper?\n* As claimed in the beginning of this paper, one potential advantage of the developed theoretical framework is to leverage the information of data distribution, or simply, the support of data distribution. However, I do not see this in the theorem or discussion after the theorems. I believe this should be a key point of the new theory, so the authors may need to thoroughly discuss whether or how considering this point can give better generalization results.\n* The definition of $\\phi_{i,j}(w,x)$ needs more explanation, why this definition is useful and how to leverage it should be particularly discussed.\n* In Observation 10, why the results do not rely on the negativeness or positiveness of $in_{i,j}(w’,x)$?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cOs5emV6Dvp", "reviewer": "Reviewer_gUyv", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper designs a new notion “almost sure support stability (a.s. support stability)” to measure the learned model’s stability to the disturbance in the training data. The authors then give a generalization bound based on this stability measure. The authors also show that ReLU network is a.s. locally smooth and a.s. locally Lipschitz continuous, which then imply that that the network is a.s. support stability.", "summary_of_the_review": "Overall, I recommend \"5: marginally below the acceptance threshold.\" I need the authors to give more details in their responses, and if this paper is accepted, the draft needs a revision.", "strength_and_weaknesses": "This paper presents a relatively new notion on the stability. The generalization bound based on the stability is also novel but not seems not difficult. The authors are required to clarify why the “a.s.” is helpful. Is it designed to match the zero-measure nonlinear points in the activation functions? Also, the authors are required to give a more detailed discussion on the differences and advantages of the a.s. support stability with the many existing stability measures.\n\nThe paper gives detailed proofs in appendices. However, the paper needs a proof sketch in the main text. Based on the sketch, the authors need to clarify the significance and difficulty of the proofs. To me, the proofs are quite straightforward: the relationship between the stability and the generalization bound needs merely an additive decomposition on the probability compared with the existing results; the a.s. locally smooth and a.s. locally Lipschitz continuous are straightforward given the nonlinear points in ReLU are of zero measure; and the a.s. support stability of the whole ReLU network comes from (1) the stability of a single layer (linear mapping of the weight matrix + a.s. linear mapping of the ReLU) and (2) composition of the multiple layers. These undermines the quality of this paper. Please correct me in the responses if I was wrong.\n\nOverall, the authors are encouraged to address the issues above in the responses and the revised draft.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "3LV6TgoSYu", "reviewer": "Reviewer_omdi", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies generalization bounds for neural networks based on the algorithmic stability. To this aim, the paper first introduces a new stability called almost sure support stability, which relaxes the uniform stability by allowing the stability to be violated with some probability. The first result is an exponential bound on generalization gaps for algorithmic satisfying almost (sure) support stability. Then, the paper develops a.e. support stability bounds for SGD with locally Lipschitz/smooth functions. Finally, the authors develop bounds on the global Lipschitz/smoothness constants for neural networks with ReLU activation functions. Experimental results are also provided to verify the effectiveness of the theoretical results.", "summary_of_the_review": "The paper provides a new stability and apply it to problems with local Lipschitz/smooth problems, e.g., neural networks with activation functions. However, the upper bound is a linear function of the number of parameters and an exponential function of the depth. Therefore, it is not clear to me the advantage of this approach over the complexity-based approach.", "strength_and_weaknesses": "Strength:\n\nThe almost sure support stability is a relaxation of the uniform stability, and therefore can be applied to more general problems. The authors apply this stability to derive generalization bounds for neural networks with ReLU activations, which have not been studied by uniform stability.\n\nWeakness:\n\nThe generalization bounds depend on the global Lipschitz and global smoothness constants. While the authors give estimates for these constants, the upper bounds grow as a linear function of the number of parameters, and an exponential function on the depth. This implies these results can only apply to neural networks with small complexity. An advantage of stability analysis is that it can imply dimension-independent bounds. However, the results of this paper does not inherit this property. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject