Stability analysis of SGD through the normalized loss function
Authors: Alexandre Lemire Paquin
Brahim Chaib-draa
Philippe Giguère
Venue: ICLR 2022 Submitted (2022)
Keywords: Generalization bounds
deep neural networks
stability

Abstract: We prove new generalization bounds for stochastic gradient descent for both the convex and non-convex cases. Our analysis is based on the stability framework. We analyze stability with respect to the normalized version of the loss function used for training. This leads to investigating a form of angle-wise stability instead of euclidean stability in weights. For neural networks, the measure of distance we consider is invariant to rescaling the weights of each layer. Furthermore, we exploit the notion of on-average stability in order to obtain a data-dependent quantity in the bound. This data-dependent quantity is seen to be more favorable when training with larger learning rates in our numerical experiments. This might help to shed some light on why larger learning rates can lead to better generalization in some practical scenarios.

Under review as a conference paper at ICLR 2022
STABILITY ANALYSIS OF SGD THROUGH THE NOR- MALIZED LOSS FUNCTION
Anonymous authors Paper under double-bling review
ABSTRACT
We prove new generalization bounds for stochastic gradient descent for both the convex and non-convex cases. Our analysis based on the stability framework. We analyze stability with respect to the normalized version of the loss function used for training. This leads to investigating a form of angle-wise stability instead of euclidean stability in weights. For neural networks, the measure of distance we consider invariant to rescaling the weights of each layer. Furthermore, we exploit the notion of on-average stability in order to obtain data-dependent quantity in the bound. This deta-dependent quantity is seen to be more favorable when training with larger learning rates in our numerical experiments. This might help to shed some light on why larger learning rates can lead to better generalization in some practical scenarios.
INTRODUCTION
In the last few years, deep learning has succeeded in establishing state-of-the thr---rrtttttttt performances in wide variety of tasks in fields like computer vision, natural language processing and bioinformatics (LeCun al. 2013). Understanding when and how these networks generalize better is important to keep improving their performance. Many works starting mainly from Neyshabur et al. (2015), Zhang et al. (017)) and Keskar et al. (2017) hint a rich interplay between regularization and the optimization process of learning the weights of the network. The idea is that form of inductive bias can be realized implicitly by the optimization algorithm. The most popular algorithm train neural networks is stochastic gradient descent (SGD). It is therefore of great interest to study the generalization properties of this algorithm. An approach that particularly well suited to investigate learning algorithms directly is the framework of stability (Bousquet & Elisseeff, 2002), (Elisseeff) ct al. 2005). is argued in Nagarajan & Kolter (2019) that generalization bounds based on uniform convergence might be condemned to be essentially vacuous for deep networks. Stability bounds offer a possible alternative by trying to bound directly the generalization error of the output of the algorithm. The seminal work Hardt al. (2166) exploits this framework to study SGD for both the convex and non-convex cases. The main intuitive idea is to look at how much changing one example in the training set can generate different trajectory when running SGD. If the two trajectories must remain close to each other then the algorithm has better stability.
This raises the question of how best measure the distance between two classifiers. Our work investigates a measure of distance respecting invariances in homogeneous neural networks (and linear classifiers) instead of the usual euclidean distance. The measure of distance we consider is directly related to analyzing stability with respect to the normalized loss function instead of the standard loss function used for training. In the convex case, we prove an upper bound on uniform stability with respect to the normalized loss function, which can then be used to prove a high probability bound on the test error of the output of SGD. the non-convex case, we propose an analysis directly targeted toward homogeneous neural networks. We prove an upper bound on the on-average stability with respect to the normalized loss function, which can then be used to give a generalization bound on the test error. One nice advantage coming with approach is that we do not need to assume that the loss function is bounded. Indeed, even if the loss function used for training is unbounded, the normalized loss is necessarily bounded.
Our main results for neural networks involve a data- deta-deppndent quantity that we estimate during training in our numerical experiments. The quantity is the over each layer of the ratio between

---

Under review as a conference paper at ICLR 2022
the norm of the gradient for this layer and the norm of the parameters for the layer. We observe that larger learning rates lead to trajectories in parameter space keeping this quantity smaller during training. There two ways get data-dependent quantity smaller during training. The first is by facilitating convergence (having smaller norms for the gradients). The second is by increasing the weights of the network. If the weights are larger, the same magnitude for update in weight space results in smaller change in angle (see Figure D In our experiments, larger learning rates are seen be more favorable in both regards.
Our main contributions are summarized as follows:
1) The first analysis of stability for SGD directly exploiting invariances in homogeneous neural networks (smooth and non-smooth cases).
2) Empirical observations suggesting that our data-dependent quantity is interesting in under- standing how larger learning rates can improve generalization.
3) An analysis of stability for the convex case naturally incorporating the norm of the initial point.
(0.0)
Figure I: For the same magnitude of step taken (same ball radius), larger norm of parameters leads to smaller change in angle.
2 RELATED WORK
Normalized loss functions have been considered before (Poggio et al. 2019). (Liao et al. (018)) In Liao et al. (2018), test error is seen to be well correlated with the normalized loss. This observation one motivation for our study. We might expect generalization bounds better by using the normalized surrogate loss in the analysis. (Poggio et al., 2019) writes down a generalization bound based on Rademacher complexity but motivated by the possible limitations of uniform convergence for deep learning (Nagarajan & Kolter 2019) we take the stability approach instead.
the test error to be
Generalization of SGD has been investigated before in a large body of literature, [Soudry et al. (2018) showed that gradient descent converges to the max-margin solution for logistic regression and Lyu
& Li (2019) provides an extension to deep non-linear homogeneous networks. Nacson et al. (2019)
gives similar results for stochastic gradient descent. From the point of view of stability, starting from
Hardt et al. (2016) without being exhaustive, a few representative examples are Bassily et al. 2020
Yuan et al. (2019). Kuzborskij & Lampert (2018) Liu et al.) (2017). London (2017).
Since the work of Zhang et al. (2017) showing that currently used deep neural networks are so overparameterized that they can easily fit random labels, taking properties of the data distribution into account seems necessary to understand generalization of deep networks. In the context of stability, this means moving from uniform stability to on-average stability. This is the main concern of the work of Kuzborskij & Lampert (2018). They develop data-dependent stability bounds for SGD by extending over the work of Hardt et al. (0016). Their results have a dependence on the risk of the initialization point and the curvature of the iniiialization. They have assume bound the noise of the stochastic gradient. We do not make this assumption in our work. Furthermore, we maintain in our bounds for neural networks the properties after the "burn-in" period and therefore closer to
2

---

Under review as a conference paper at ICLR 2022
the final output since are interested in the effect of the learning rate the trajectory. This is motivated by the empirical work of Jastrzzebbi et al. (2020) arguing that in the early phase of training, the learning rate and batch size determine the properties of the trajectory after "break-even point". Another work interested in on-average stability is /Zhou et al. (2021). Differently from our work, their approach makes the extra assumptions that the variance of the stochastic gradients is bounded and also that the loss is bounded. Furthermore, our analysis directly exploits the structure of neural networks and the properties following from using homogeneous non-linearities.
It has been observed in the early work of Keskar et al. (017) that training with larger batch sizes can lead deterioration in test accuracy. The simplest strategy reduce (at least partially) the gap with small batch training is to increase the learning rate (He et al. (2019), (Smith & Le 2018). (Hoffer jtt al. 2017). (Goyal et al. 2017). We choose this scenario investigate empirically the relevance of our stability bound for SGD on neural networks. Note that the results in Hardt et al. (2016) are more favorable to smaller learning rates. It seems therefore important in order to get theory closer to practice to understand better in what sense larger learning rates can improve stability.
3 PRELIMINARIES
Let l(w, 2) be non-negative loss function. Furthermore, let A be randomized algorithm and denote by A(S) the output of when trained on training set S 1. 2n} D The true risk for classifier w is given as
LD(W)= == EENDl(w,
and the empirical risk is given by
Ls(w) = 1 Σ I(W, zi).
When considering the 0 loss of a classifier w, we will write I.-'(ww) (w). Furthermore, we will add a superscript a when the normalized losses 1 are under considcration (these will be defined more clearly in the subsequent sections respectively for the convex case and the non-convex case). Our main interest to ensure small test error and so we want to bound L.g. (w)) The usual approach is to minimize surrogate loss upper bounding the 0 - 1 loss. In this paper, we consider stochastic gradient descent with different batch sizes to minimize the empirical surrogate loss. The update rule of this algorithm for learning rates A and subset B, CS of size B is given by
(wx).
Wt+1 Wt d1 B
Σ Vl(we, 2z). Z,En,
(1)
We assume sampling uniformly with replacement order to form each batch of training examples. In order to investigate generalization of this algorithm, we consider the framework of stability (Bousquet) & Elisseeff 2002).
We now give the definitions for uniform stability and on-average stability (random pointwise hypoth- esis stability in Elisseeff et al. (2005)) for randomized algorithms (see also Hardt et al. (2016) and Kuzborskij & Lampert (20p)) The definitions be formulated with respect any loss function but since we will study stability with respect to the !at losses, we write the definitions in the context of this special case.
Definition 1 The algorithm A is said to be -ui-forryyyy stable if for all i (1,....n)
sup
E (A(S), - ((((ss < E
(2)
S
Here, the expectation is taken over the randomness of A. The notation 5(0) means that we replace the 7th example of S with z/.
Definition 2 The algorithm A is said to be ca, -nn-avaaee stable if for all i f1....,,.]
E 1 (A(S), ( (A(S()))
S car
(3)
3

---

Under review as a conference paper at ICLR 2022
Here, the expectation is taken over S ~ D", D and the randomness of A. The notation S means that we replace the ith example of S with z.
Throughout the paper. |I-I| will denote the euclidean norm for vectors and the Frobenius norm for matrices. The proofs are given in Appendix A for the convex case and in Appendix B for the non-convex case.
CONVEX CASE: A FIRST STEP TOWARD THE NON-CONVEX CASE
Since the convex case easier to handle, can be seen as good preparation for the non-convex case. Consider linear classifier parameterized by either a vector of weights (binary case) or matrix of weights (multi-class case) that we denote by w both cases. The normalized losses are defined by
w
1 (w: 2) = I(a ||m|| 2),
(4)
for a: >
In order to state the main result of this section, need two common assumptions: L--Lpschitzness of as a function of w and 3-smoothness.
Definition 3 The function 1( 2) is L Lipschitz for all in the domain (with respect w) if for all w, w',
[[w, z) 1(w',=)) L|| w'll.
(5)
Definition 4 The function Uw, z) is 3-smooth for all w, w',
[V](w, v B||w w
(6)
We are now ready state the main result of this section.
Theorem Assume that 1w,, =) is convex, 3-smohth and L Lipishhhi for all z. Furthermore, assume that the initial point wi satisfies || |wol|> K for some K such that K K KK-LX L- T- X; 0 for a sequence of learning rates X S 2/3. SGD is then run with batch size B on loss function Iw z) for T steps with the learning rates d starting from wo. Denote by e the uniform stability of this algorithm with respect to 1 Then.
B
Cuni Sa
Σ A
n.K
1=0
What is the main difference between bound and the bound in Hardt et al. (2016) (see theorem 7 in Appendix A) ? Our bound takes into account the norm of the initialization. The meaning of the bound is that it is not enough to small learning rates and small number of epochs guarantee good stability (with respect to the normalized loss). We also need to take into account the norm of the parameters (here the norm of the initialization) make sure that the "effective" learning rates small. Note that all classifiers are contained in any ball around the origin even if the radius of the ball arbitrarily small. Therefore, all control over stability lost very close to the origin where even small step (in Euclidean distance) can lead to a drastic change in the classifier. The norm of the initialization must therefore large enough to ensure that the trajectory cannot get too close to origin (in worst case, since uniform stability is considered). An alternative if the conditions of the theorem are too strong in some practical scenarios is to use on-average stability (1 = 1 layer in the results of section 5). As side note, we also incorporated the batch size into the bound which is not present in Hardt et al. (0016) (only = is considered).
From this result, it is now possible obtain a high probability bound for the test error. The bound is over draws of training sets S but not over the randomness of A. So, we actually have the expected
It is possible to obtain bound holding over the randomness of A by exploiting the framework of Elisseeff al. (2005). However, the term involving p in their theorem 15 does not converge O when the size of the training set grows to infinity.
4

---

Under review as a conference paper at ICLR 2022
test error over the randomness of A in the bound. This is reminiscent of PAC-Bayes bounds where here the posterior distribution would be induced from the randomness of the algorithm A.
Theorem Fix a > O. Let M == (u =) s.t. Hwlls a, || R). Then, for any n >> and ò E (0, 1), the following hold with probability greater or equal 8 over draws of training sets S:
In(1/6) 2n
A EALS & BALg(A(S)) + Cuni + (2ncans + Ma)y
(8)
The proof is an application of McDiarmid's concentration bound. Note that we do not need the training loss to be bounded since we consider the normalized loss which is bounded. The proof follows the same line as theorem 12 in [Bousquet & Elisseefi (2002) and we do not replicate it here. Note that we need to use that uniform stability implies generalization in expectation which is proven for example in theorem 2.2 from Hardt al. (2016).
Proof:
Furthermore, a bound holding uniformly over all a's can be obtained using standard techniques.
Theorem 3 Let C' > O. Assume that (w, 2) is convex, function of a for all w, 2 and that E is non-decreasing function of Then, for any and ó E (0, 1), the following hold with probability greater or equal to 1 - 8 over draws of training sets S:
EA 1. BA (A(S)) < inf aE(0,C)
EA max (Lg (A(S), (3((5))) + cumi + (2ne uni +
2 22(2 + logg C logg a)) + In(1/8)
Va)
2n
In the next section, investigate the non-convex case. We exploit on-average stability to obtain data-dependent quantity in the bound. Note that it is also argued in Kuzborskij & Lampert (2018)
that the worst analysis of uniform stability might not be appropriate for deep learning.
NON-CONVEX CASE
We consider homogeneous neural networks in the setup of multiclass classification. Write f(z) Wi(a(... (o (()((()))))))) (z)))). where x is an input to the neural network, W2 denotes the weight matrix layer i and a denotes a homogeneous non-linearity (a(cz) = ct c for any constant c > 0). Examples for the non-linearity are the ReLU function (k: = 1), the quadratic function (k 2) and the identity function (k 1, leading to deep linear networks). Consider a non-negative loss function I(s, y) that receives a score vector fx) and label y inputs. We require the loss function to be L-Lipschitz for all y as function of s. That is, for all 8, 8,8',80 y/-
[1(s y) 1(s', .) L||s - s'll.
For example, we can the cross-entropy loss (softmax function with negative log likelihood). In this case, it is simple to show by bounding the norm of the gradient of 1(s, y) with respect to s that we can use L = 22. Note that this is slightly different from the Lipschitz assumption of the previous section (given with respect to the weights w).
In order to control the behaviour of the non-linearity, we assume that for any >> 0, there exist constants B, and Le such that for any x, y E 12d with ||]|| and ||ylا< e we have
||a(2)]| < Bd ( a (v) < Te | vl|-
(10)
(11)
Note that the con-ariny a is being applied component-win wise when the input is a vector as above. is easy to verify that, for the ReLU function, we have B. 1 and L. 1 for all c. Furthermore, for the quadratic function x?, we have B, = e and L, = 2c. The following lemma will be the starting point for analysis.
5

---

Under review as a conference paper at ICLR 2022
Lemma Assume that | R. Let o1.....y be positive real numbers and, for S j S I, denote W W3 TWST and W W
Write 8j - W(z))) and
8)y a, Wo a2 W (a W[a)))). Also, let oj be an upper bound on the norm of layer j (this will be constant depending on 01,, a. Og and RJ. Then, have
|| - كالls R
II aj 1=1
Σ
FellW: Will.
(12)
where Ti
II Ø=1
Bey Lo
is 1 121) if j }21)
The previous lemma motivates measure of "distance" between neural networks.
Definition 5 For neural networks f and 9. where the weight matrices of are given by W1 ... Wi and the weight matrices of g are given by W1- ... Wi, define
W.
W
a(..)) = Σ
(13)
Note that this distance function is invariant to rescaling the weights of any layer. This is desirable property since in homogeneous network such a reparametrization leaves the class predicted by the classifier unchanged for any input to the network.
Let 01,..-a be positive real numbers. We define the 1oi,-ar losses to be equal to
WL Mo Will
W₂ W
W [W x)))),,),
(a
02
(o(a)
(14)
where = (x, y) and I' the neural network with weight matrix layer given by W,, That is, project the weight matrices to give the norm a; to layer i and then we evaluate the loss on this "normalized" network. For simplicity, we will only consider the case where all the a 's are equal to say and will write ("(f2) 2). From our definitions and lemma [ networks f and g.
we have that for all and neural
Ir 2) -1 2)15 LRa' ((f.d((fg))
(15)
In order to bound stability with respect to 1", we will have to ensure that the two trajectories cannot diverge too much in terms of d(f.g).
We will consider two separate cases: the smooth case and the non-smooth case. When the activation function is smooth (for example x² for l 2 1), we will exploit the concept of layer-wise smoothness defined below.
Definition 6 Consider the gradient of the loss function with respect to the parameters W for some training example z. The vector containing only the partial derivatives for the weights of layer j will be denoted by (U)[(W,2) 2). We define {,3,1-11 -lyeewiiss smoothness as the following property: For all j. z, W = (W1,'* ",, Wi) and W = (W', " W().
(1 - -WW ; B,IlW, WIIl-
(16)
We also let 3 = max {31}. Note that 3 is upper bounding the spectral norm of the bloc diagonal approximation of the Hessian.
We ready state the main theorem of this section for the smooth case.

---

Under review as a conference paper at ICLR 2022
Theorem 4 Suppose that the loss function (ss v) is L-Lipschitz for all y, non-negative and that (f,xz) is bounded above by Ma. Furthermore, assume -lyYi=n- smoothnsss and that ||l|| R. Finally, let B denote the batch size, de S the learning rates and T the number of iterations SGD is being run. Then,
2BLRa
T
00
Blo
aav -
inf fo (1,2,... B3
Σ
Se + Ma
(17)
(n - B)B
to to
n
where B max {B3} and Ge = Ej= BA,, C,(S, 1 (willl
(S,))
K. (S,
with (S, min (WW, and C)(S,))
max BoSIgT-1
K (S,
To evaluate the bound, we need to find the best to. There is a tradeoff here between two quantities. A small to is better for the term M, Bto but is worse for the remaining term. This establishes the best - "burn in" period. The amount of "exploration" before to does not effect the generalization bound.
The amount of exploration measured by &e (and through the learning rate via the value of c) becomes important only after iteration lo- The bound will be better if can reach region in parameter space such that the classifier is then effectively not changing much. This is measured through the norm of
the gradient but also takes into account the norm of the parameters (via k(1) (S, 2)). When reach larger norms of parameters, stability (with respect to the normalized loss) is less negatively affected. The intuitive reason is the following: the same magnitude of step results in a smaller change in the classifier if the parameters are larger (see Figure D In Hoffer et al. (2017). it is observed that small batch training and larger learning rates (finding solutions generalizing better) are reaching larger norms of parameters (see also our Figure 3. Using standard Fuclidean distance in the analysis of stability would lead us to believe that this behaviour is highly undesirable. Our analysis shows that this behaviour can actually be favorable to the on-average stability with respect to the normalized loss. The quantity S. also involves the terms (S, 2) measuring how fast the norm of the parameters is growing from one iteration to the next. The value of CS,S, z) is better (smaller) if the norm of the parameters grows faster.
The non mooth case is also of great interest since the ReLU activation function is very common in practice.
Theorem Suppose that the loss Sunction Uss y) is L-Lipschitz for all y, non-negative and that (J, bounded above by Mo- Furthermore, assume || R. Finally, let B denote the batch size, d the learning rates and T the number of iterations SGD is being run. Then,
T-1
Btg
Egv <
inf toE (1,
2LRx
Σ
Ade + Mo
(18)
a
where Çi is defined as in theorem
Exploiting theorem 12 in Elisseeff al. 2005) it is then possible get probabilistic bound on the test error (holding over the randomness in the training sets and the randomness in the algorithm).
Theorem 6 Fix 0. Then, for any
and 8 E (0, 1), the following hold with probability greater or equal to - 8 over draws of training sets S and the randomness of the algorithm A:
(A(1() < (S(A(S)) + V(3 2M2 12nMa
(19)
n
EXPERIMENTS
6.1 LEARNING RATES AND Ce
In this section we conduct some experiments on the datasets 1IFAR10/KKizeeee (2009) and MNIST LeCun & Cortes (2010). We consider the scenario where try to reduce the performance gap
7

---

Under review as a conference paper at ICLR 2022
between small batch and large batch training by increasing the learning rate. We will give some evidence suggesting that the quantity Çe can be of interest to assess generalization in this case.
We use global learning rate being decayed one time by factor of 10 in our experiments. No weight decay or momentum is used to stay closer to our theoretical analysis of SGD. Note that in principle, the learning rate could be as large we want during the inital burn-in period (before tn) without hurting stability. However, this burn-in period must be inside the first epoch in the theoretical results we presented. Since in practice we train for many epochs, it is not clear if such small burn-in period is long enough to be significant in current practice. We still think that the quantity & relevant to investigate empirically. We approximate its value on a training set S with the quantity (() = E L (W+)ll, The quantities (,,5, 2) can be evaluated empirically to be very close to and so we neglect them in the expression for (S). Also note that 7j 1 for all j in the case of ReLU networks. Instead of plotting the value for each iteration, we average (S) for each epoch. This leads smoother curves.
[|a
We use a 5-layer convolutional Relu network consisting in 2 convolutional layers with maxpooling and then 3 fully connected layers with cross-entropy loss CIFARIO. We use also the cross-entropy loss on MNIST but the neural network is a G-layers fully connected network. In both cases, we use natch-oormalization to facilitate training. All the results in the figures are obtained when using batch size of 2048. We started by training with a smaller batch size of 256 and then tried to reduce the gap in performance between large batch and small batch training by increasing the learning rate. For example, on CIFAR10. 10, we obtain a test accuracy of 86. 23.23% when using a batch size of 256 and a learning rate of 0.5. When increasing the batch size to 2048 (and maintaining the learning rate to 0.5), the test accuracy dropped to 85. 15.14%. This happened even if the training loss reach approximately the same value in both cases (0.0123 for batch size 256 and 0.0167 for batch size 2048). We then increased the learning rate to 1.0 and then to 1.5 reaching 85.63% in both cases (not completely solving the gap but reducing it). A similar phenomenon happens for MNIST. Here, with batch size 256 we get 98.57% (Ir 0.05) of test accuracy and for batch size 2048, we get 97. 97.52% (Ir 0.05), 98.00% (Ir 0.1) and 39% (Ir 0.5). We plotted the values of (8) during training in Figure We can see that it is better during all training when increasing the learning rate.
To compare with the analysis from Hardt et al. (2016), the quantity Se would be replaced with a global Lipschitz constant which would not be affected by the actual trajectory of the algorithm. Therefore, in comparison our bound, the bound in Hardt et al. (2016) would be much more favorable to smaller learning rates. In other words, the worst case analysis of uniform convergence would require much smaller learning rates to be used than our result to guarantee good stability. The quantity &e can be improved by accelerating convergence because of the numerator (norm of the gradients) but also by increasing the denominator (norm of the parameters). A larger learning rate can help in both these regards (see Figure 33. Note also that considering only the norm of the gradients without the norm of the parameters would lead to a less favorable quantity compared to considering both the norm of the gradicnts and the norm of the parameters. A standard analysis of stability (without the normalized loss) similar to Kuzborskij & Lampert (0018) would not benefit from the norm of the parameters.
MEOLT
8.5
03.
0.55
36
100
174
200
250
300
20
30
epech
epch
(a) CIFAR10
(b) MNIST
Figure 2: ((()) when training a convolutional network on CIFAR10 and a fully connected network on MNIST.
8

---

Under review as a conference paper at ICLR 2022
paramstors nam Bager 1) s
150
150
300
300
150
(a) Norm of the parameters
(b) Norm of the gradient
Figure 3: Norm of the parameters (layer 3) and norm of the gradient when training convolutional
network on CIFAR10
6.2 GENERALIZATION BOUND AND TEST ERROR
We show in this section the usefulness considering the normalized loss for bounding the test error. We evaluate the bound in theorem and compare it analogous version for the unnormalized loss. For this analogous version, we replace the upper bound M on the loss function by the largest loss achieved during training. Furthermore, the quantity Eav is upper bounded the Lipschitz constant times the Euclidean distance between the weights of the networks. The Lipschitz constant is replaced by the largest norm of gradients obtained during training. For the normalized loss, we upper bound <a by A.RaEE ff g) (see equation 15). We plot the test error, the upper bound for the normalized case with a 1.0 and the upper bound for unnormalized case Figure 4 Further experiments (with label noise and comparison of Adam and SGD) are given in Appendix
Goneralizatio bounds and best errur
10032
val. cerort
suclid
0932
1dott
0022
300
sporch
Figure 4: The bound obtained from the Euclidean distance much worse than the bound obtained from normalized distance. However, the generalization bound is still vacuous. The network is 6-layer fully connected network trained on MNIST.
CONCLUSION
We investigated the stability (uniform and on-average) of SGD with respect to the normalized loss functions. This leads naturally to consider more meaningful measure of distance between classifiers. Our experimental results show that stability might not be as bad as expected when using larger learning rates in training deep neural networks. We hope that analysis will be helpful step in understanding generalization in deep learning. Future work could investigate the on-avert on-average stability with respect to jo losses for different optimization algorithms.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tiees Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Olivier Bousquet and André Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499-526, 2002.
André Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil. Stability of randomized learning algorithms. J. Mach. Learn. Res., 6:55-79, 2005.
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming Hc. Accurate, large minibatch SGD: training imagenet in 1 hour. CORR, abs/1 706.02677, 2017. URL.htt:://axxte http://.wrra/ab///////ee/// alss 706.. 02677
org/
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proceedings of the 33nd International Conference on Machine Learning, ICML. 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings. pp. 1225-1234, 2016. URL http:://prccedd ngs. ml press/ v48/ 1tt/hardt1.....
Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems 32, pp. 1143-1152, Curran Associates, Inc., 2019.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pp. 1731-1741, 2017.
Stanislaw Jastrzebski, Maciej Szymczak, Stanislav Fort, Devansh Arpit, Jacek Tabor, Kyunghyun Cho and Krzysztof Geras*. The break-even point on optimization trajectories of deep neural networks. In International Conference on Learning Representations, 2020. URL https:// openreview wetp://oooumdddd1g////ee.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings, 2017. htt.:tts::// wttps////ppeeeee...eooo net.iiewwweee/eeeeee.eeeeeeeeeee forum?? Pid- H1oyR1Ygg
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
IIja Kuzborskij and Christoph H. Lampert. Data-dependent stability of stochastic gradient descent. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stock- holmsmässan, Stockholm, Sweden, July 10-15, 2018 volume 80 of Proceedings of Machine Learning Research, pp. 2820-2829. PMLR, 2018.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http://yann
lecun. wtt.c/cccccc..ee hammmeexbbmmntn st/
Yann LeCun, Yoshua Bengio, and Geoffrey E, Hinton. Deep learning. Nature, 521(555))6667 ht htttt:::///oo..rg/1....o wttpe//./..///aatiiioo
2015. doi: 10. 10.1008/nature14455
Qianli Liao, Brando Miranda, Andrzej Banburski, Jack Hidary, and Tomaso A. Poggio. A surprising
linear relationship predicts test performance in deep networks. CoRR, abs/1807.09659 2018. URL
http: http://aaxvvv... www.wwwwwww...a......a. httpgggabs/18000
Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 2159-2161 PMLR, 2017.
10

---

Under review as a conference paper at ICLR 2022
Ben London. A pac-bayesian analysis of randomized learning with application to stochastic gradient descent. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA. pp. 2931-2940, 2017.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. CoRR, abs/1906. 9999000890, 2019. URL
05890
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry, Stochastic gradient descent on separable data:
Exact convergence with a fixed learning rate. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pp. 3051-3055 PMLR, 2019.
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain gener- alization in deep learning. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 11611-11622, 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Proceedings of The 28th Conference Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, pp. 1401, 2015. URL /att:://procedeinggs mlr. press/v40/ Neyshabur15.. hhtml
Tomaso A. Poggio, Andrzej Banburski, and Qianli Liao. Theoretical issues in deep networks: Approximation, optimization and generalization. CoRR, abs/1908.0973 09375,, 2019. URL http: 09375
/arxiv.org/abb.
Samuel L. Smith and Quoe Le. A bayesian perspective on generalization and stochastic gradient descent. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018. URL https 7/openreview net
Daniel Soudry, Flad Hoffer, Mor Shpigel Nacson, and Nathan Srebro. The implicit bias of gradient descent on separable data. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018. URL net. / forum? dedirdrrrg99
puttps:/copenrees
Zhuoning Yuan, Yan Yan, Rong Jin, and Tianbao Yang. Stagewise training accelerates convergence of testing error over SGI). In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 2604-2614, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Y. Zhou, Y. Liang, and H Zhang. Machine Learning, 2021.
sgd in nonconvex opariiizaoeoooiiiiizaaioooooo
A APPENDIX: PROOFS FOR THE CONVEX CASE
In Hardt et al. (2016), uniform stability with respect to the same loss the algorithm is executed on is considered. This is a natural choice, however we are interested the loss, different set of parameters w, w' can represent equivalent classifiers (that is, predict the same label for any input). This is the case for logistic regression since any rescaling of the parameters yields the same classifier (but they can have different training losses). This is also the case for homogeneous neural networks where we can rescale each layer without affecting the classifier. This is why we consider stability with respect to normalized losses instead. Note that we still considering SGD executed on the original loss (we do not change the algorithm A). The intuitive idea is to measure stability in terms of angles (more precisely, we consider distances between normalized vectors) instead of standard
11

---

Under review as a conference paper at ICLR 2022
euclidean distances (see Figure I..
The proofs in Hardt al. (2016) consist in bounding E| el w/ll where wy represents the weights at iteration t when training on and wy represents the weights at iteration when training on the modified training set S(6), We will instead bound I3] [w-ll (or [(d(J.9) for an appropriate measure of "distance" between neural networks. f and g).
w/
T
Lemma 2 Let v, w R" and 0 < min [|]l] Then,
v--ee
[00]
The proof follows from basic linear algebra manipulations. We give here for completeness since it is important in what follows, We need to show that
Proof:
After some manipulations, one can see that this is equivalent to show that
|| -2 + 2(c
||e|||/||\TTT Top 2 0.
From Cauchy-Schwar inequality, [Til || I 1. Since c² - |||||| |/ll|///////// O, the proof will be completed by showing that
||||2+||w||| 2e2 + 2(c² w|]) 2 0.
But this is true since
||||+||||| 2- 2 (1|||11|/=11))
Lemma 3 Assume that the initial point wo satisfies || |/ol/> K and that SGD is run with batch size
B and a sequence of learning rates x on an L-Lipschite loss function 1(w; 2) for all z. Then, for all 12 1,
| 11 K- -.E d,.
Proof:
|well
|r-1 Ac-1
j=1
1
|/ ||| d1 - B
V VI(Wa-1,,
IV w
Wr-1 - L
- 1 - Ac-
[-1
| - X
1=0
K
L
X
i=0
For of comparison, we give the statement of Theorem 3.8 in Hardt al. (2016).
Theorem (Theorem 3.8 in Hardt et al. (2016)) Assume that the loss function f(:;2) is 3-smooth. convex and L- Lipisschit for every z. Suppose that we run SGD with step sizes a, S 2/ B for steps. Then, SGD satisfies uniform stability with
12

---

Under review as a conference paper at ICLR 2022
Cuni 2L
T
O0
We are now ready prove Theorem
The proof is similar to Hardt et al. (2016). Let we denotes the output of A after steps on training set and wy be the output of A after steps on training set Sti) for some i (I,...n.. n). From convexity, the update rule 1-expansive (see lemma 3.7 from Hardt et al. 2016)). This property can be used when the example is not being picked at some iteration.
Proof of Theorem 1:
Otherwise, the triangular inequality is used. Since the probability of picking the example mini-batch of size B is smaller than B (sampling with replacement) and exploiting Lemma 2 and Lemma 3 we get
E
Wr+11
W/++
5
E
|10e+ - w1-1ll
110
K
B
+ (1-
B
S
E||100
E
100
w
ul will
K
n
2BLd>
Bllw
E
w/1l+
K
n
Note that this is true since Bl|wr wills | we have
w +T, Solving the recursion for Bl|l -w/l-
E
w.
wills
2BL E A
Therefore,
10 The
28L nk
Ei d
The result then follows from the inequality
I1a w [. ((]|ie))) 2)15 Lail
||ll
||w01]
We finally prove Theorem 3.
Proof of Theorem 3: To simplify the text, write e(a, = BALg(A(S)) + E + (2ne
stab
Va)y (n(1/8) 2n
For 2 1, let a, 2(2-i) and & z.. For any fixed i, we have
( c(a;; 6:)3 < 5,,
Therefore,
Ps(vi, BALD- E( 8:)}
1 Ps(i, 0-- EAL0-((A(S)) (A(S)) > e(a;, 8:)3
2 1
Ps L0 0-1 (A(S)) > c(a,, 6,)3
8, > 1-
The last inequality follows from
20
8
1
8 8
<
6.
12
2
1=1
We want show that the
13

---

Under review as a conference paper at ICLR 2022
{S: vi, EALD'(A(S)))) & c(ar,
is contained in the set
{S: Va E C, ( <
A max (A(S) Stab (2nc stab
Ma)v 21n 22nlv2(2+lng, C logg +l)+11((11)))))
2n
Let S be such that Vi, BA (A((S) S {((a,,)) 6,). Let E (0, (0,C). Then, there exists i such that
ag I a S 20s, We have
In(1/0g)
E BALD & BAL5 + Etab + (2ne stab + Ma.) )
2n
In(1/64)
I EALS (A(S)) + Geab + (2ab + MMa V
2n
< EAL' (A(S)) Ellab + (2ne stab + Ma))
2 1l((2((2 + log2 C' - logg a)) + ln(1/0)
2n
The second inequality is true since both Stab and M,, are non-decreasing functions of and a; S a. The last inequality is true since & 21² I 2(2+1oR; C-los, ai) Finally, the proof is concluded by using the convexity of (3((S) with respect to a. Indeed, since S a, S a, we must have
L (A(S)) max (LS (A(S)),
B APPENDIX: PROOFS FOR THE NON-CONVEX CASE
Proof of Lemma 1: The proof is done by induction on the number of layers 1. Suppose the result true for 1 - 1 layers. Then we have,
- ||sr-$11= anl (1o - (
= =aillWio(si-1) - (/ (
< [=]llWio(s)-1)- - http:///ooo///////////////////a0 (s))-))))))))))
- - [V/11//0000///HH000//////6666600
SaullWi ||] + ta ||18/_1111 - -
1-1
s Railli Will II
Be + ai La La- ||s/_1 - -8-1ll
a=1
(Be Bey if j < i
if j>i ]
SR
ag
W -W-ll
II Bey tapha-
R
aj
||; Will
II j=1.o
Ley_.
j=1
j=1
i=1
R
w
Will
Beg
is
j j>1 )
j <
Lej-1
if
1=1
j=1j#1
The proof is finally concluded by observing that for one layer we have, ||5/ - 8il1= Roill - Will
Definition Let us introduce some notations. Let : W,,el and (S, (M) (S, = 0). Here, W5, is obtained when training with S for iterations
E (S, 2) Vk, (/) and W dit is obtained when training with s(t) for t iterations. The condition inside the expectation is that after ta tterations, the two networks are still exactly the same. Since we are interested in
14

---

Under review as a conference paper at ICLR 2022
distances after normalization, we consider (( (S, = 11
Ws.
[W and (0) (5,z) =
W
IWalell
E (S, Vk, 0%- (S, 2) 0). We will further need 81:) (S,2)
(S.s)
and Á (1) (S,
(S.a)
(8, 8 (S, =) Vk, (S, 0}, where { -min ||ll and
K (S,
=)( LoS1ST-1 -1 KU] 141 (S,2)
max
Before proving Theorem 4, we establish a lemma. Note that the structure of the proof of the following Lemma and of Theorem is similar the corresponding results in Hardt et al.) (2016) and in Kuzborskij & Lampert (2018).
Lemma 4 Suppose that the loss functiin 1(8,8) is L-Liipschizz for all y, non-negative and that (f, 2) is bounded above by Ma- Also, assume that || R. Furthermore, let B denote the batch
size and TI the number of iterations SGD is being run. Then, for any to {0, 2, ...... B the on-average stability satisfies
(S. 1kk ( 01 + Ma B 2. S LR Σ Ts, (S
n
Proof: Write the quantity (I, - -10 (g, =)1 the sum of [I((), -1 10 T (
Of and (f) [1 ///² (S, *0}. We bound the first term by using the fact that
(f,) (g. LRo ((f.)) LRRo Σ T, (S,
For the second term, use that 1 (f, 2) is bounded above by Ma and non-negative to write
(f. 2) - (g. 2)15 Ma.
The result then follows from the fact that the probability of picking example in 4 iterations is smaller than Big
Proof of theorem 4: From Lemma previous Lemma,
2 we always have (S, 2) S (S, Therefore, from the
< LRaa
Σ
Ty
Bss
(S,+))
Ma
Blo
==1
First note that under our definitions,
(05 (S,z)
80) (S,))
K.), (S,
04+1 (S,z)
< 2S,
K. (S,2)
2)
(S, + + LR - A L LB (W)))
K. K (8,))
LB. (W:) - LB
(S, (() +X.C((S
(S,)(
15

---

Under review as a conference paper at ICLR 2022
Therefore,
C,(8,2) 822 (2 (S, s C,S,2) - (S,2) (S,, 2)T-1 (V Ln, (W.) - 4 L (W!)) (S,
Here, B, denotes the batch of samples at iteration when training on S and Bi denotes the batch of samples at iteration t when training 5t0), When B, By, we will use smoothness to bound [[ LB, (W) I.y (WIIl- Otherwise, we use simply the triangular inequality. Let p(B, n) be the probability of picking the example in a mini-batch of size B (this is smaller than 2). For 2 lo. we have
m) (S, (S, S (3
(EA[C;(S, 2) [ T.B, (Wa)l (S,
+ +C, -| L.p: (1))))))
(S,
Define A Eg, A (S, and
cl == EA.., 2)
T (| (Wa)l for any t. Taking the expectation over S and & on both (S.))
sides of the previous inequality, we get
A A 611 S (1 - p(, ()) + + ((( + 2
This is true since
S.,,.: CS x)T | LB, (Will (S.=)
(SS Lz
Rearranging terms and
(S,)
using 1 + S exp(x), we get
(
[1+ (1-11p(B)) P(B, + +2p(B,n)ArC) 1
111
exp((1 (BB()_=(( = 22(
Developing the recursion yields
A
2p m)d (1)
II exp k=
T-1
p(B, ni) (1-)((,,))
cBg
k
t=
T-1
T-1
<
2B
NeGt (f)
exp (1- (1-p(B,n))ck
Σ k) k=t+1
n1
T-1
2B
A (f)
(1 (1-p(B, n)) (1) t
log( T 1
exp
2Bc
(
T -
(1 (I)D(B
1
t=
2Bc
(f)
T 1
(1-p(B,x))c
t=
T
(1-p(Bn))00811
2Bc max
(G.) ()LL-p(B,n))e
n 1-515T-1
(1 PBBBn)))
2Bc
(c(00)
T -
max LoSIST
no(1 - p(B,n))
10
2B
(T-1) cB
(c(0))
< (n- - B)B
max
to
515
16

---

Under review as a conference paper at ICLR 2022
Therefore, Eap is upper bounded by
inf 2BLRR 11, 1 (n 3) to
(T -
Σ
((t
+ Ma Blo )
Tj max
SeST
To complete the proof, we will use that max 1 With the definition G. == Ej=1 Ty(( we then have
S 21= (( and reverse the sum order.
2BLRa T-11 (n B)3
08
Btg
@0 S
inf 61,
Σ t=
S + Ma
#1
to t--1)
Proof of Theorem
5: The beginning of the proof is the same as the proof of Theorem 4. However, in the case where smoothness is not assume (for example, ReLU neural networks), not possible to exploit the property of aayer-wise smoothness. Instead, only the triangular inequality is used to bound [| (W),) - v LB (WDII. This leads to the inequality
A S A + 22,
Solving the recursion then yields
A <2Σ 1
As consequence,
Bl
a <
inf t0, B
2LR
Σ t=to
Usse + Ma
where G. = Ejn1 T concluding the proof.
C APPENDIX: MORE EXPERIMENTS
Generalization bound versus epoch (label noise)
6000
5500
5000
4500
noise
noise ratio 0.2
4000
noise ratio 0.3
3000
2500
20
40
60
80
100
Epoch
Figure 5: The generalization bound from Theorem 6 (a = 1.0) when training with different amounts of label noise. The network is 6-layer fully connected network trained on MNIST with SGD. The final test accuracies are: 98.56% (label noise ratio = 0.0), 96. 96.06% (label noise ratio = 0.1), 91.28% (label noise ratio = 0.2) and 84.22 84.22% (label noise ratio = 0.3).
17

---

Under review as a conference paper at ICLR 2022
Zeta versus epoch (label noise)
0.6
noise ratio = 0.0
noise ratio 0.1
noise ratio 0.2
0.5
noise ratio 0.3
0.4
0.2
0.1
0.0
20
40
100
Epoch
Figure 6: (S) when training with different amounts of label noise. The network is a 6-layer fully connected network trained on MNIST with SGD.
Generalization bound versus epoch (Adam versus SGD)
7000
6000
5000
Adam, alpha 1.0
Adam, alpha 0.9
SGD, alpha
SGD, alpha
3000
2000
1000
Epoch
The generalization bound from theorem (a 1.0 and 0.9) estimated when training with Adam and SGD. The network is a 6-layer fully connected network trained on MNIST with 10% of label noise. For Adam the test accuracy is 95.38% and for SGD, the accuracy is 96. 96.06%. Those are the best test accuracies that could be obtained after tuning the learning rate for each respective algorithm.
Figure 7:
18


Reviews:
[{"review_id": "d7jBPK06yDX", "reviewer": "Reviewer_hQwz", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "My main concern about this paper is its motivation for considering/highlighting the normalized loss function. To me, it is a serious concern as all the analysis conducted in this paper is built upon the normalized loss. However, here the normalization, in my opinion, is more of a trick in the analysis. I read through the two papers, Poggio et al., 2019 and Liao et al., 2018, which, according to the authors, introduced normalized loss function. However, it seems that the normalization was used only to simplify the analysis and similar theoretical results could be obtained without normalization. Such comments may also apply to the present paper. In short, I cannot agree with the authors that it is the normalization operation that leads to the results developed in this paper. \n\nIn addition, in my opinion, the presentation of the paper needs to be greatly improved. For instance, the authors highlighted the normalized loss throughout, including the title. The notation of normalized loss is also used in Definitions 1 and 2 from Section 3. However, the definition of normalized loss function was only introduced in Section 4. I believe that the normalized loss is not something well-established in the literature. From the two papers mentioned by the authors, I failed to find an explicit definition of the normalized loss function. Therefore, I think the authors really need to define the loss before using the concept again and again. On the other hand, when stating the motivation and the origin of the normalized loss function, the authors only mentioned them in passing at the beginning of Section 2. It seems to me that the authors said a lot about the literature but were trying to avoid answering the question \"why this work\". I do think that the authors need to take care of this part more seriously.       ", "summary_of_the_paper": "This paper conducted a stability analysis of Stochastic Gradient Descent (SGD) for empirical risk minimization induced by the so-called normalized loss function. Here, the normalization is taken with respect to parameters involved in an individual loss; see (4) for the definition of the normalized loss function. The paper should be regarded as a theoretical paper. The main results are stability bounds of SGD for convex and nonconvex ERM schemes.   ", "summary_of_the_review": "Based on my comments above, I cannot recommend its acceptance. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "XKbs_v6u1yb", "reviewer": "Reviewer_WveE", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper is generally very well written. The idea of using normalized losses and angle-wise stability to analyze SGD is interesting and novel. One minor concern I have is the motivation/justification behind using angle-wise stability and overall applicability in neural network learning. Authors claim that in the framework of on-average stability and normalized losses, larger norms of parameters are beneficial to stability. However, it is known that this is probably not generally the case. Even though authors show some empirical evidence in Fig 3, this argument can be better motivated.", "summary_of_the_paper": "This paper provides new generalization bounds for SGD using the stability analysis framework for both convex and non-convex cases using a normalized loss function, stability as measured in the form of anglewise stability as supposed to standard euclidean distance.", "summary_of_the_review": "I feel the theoretical results are strong and the authors provide sufficiant empirical results to validate their theoretical findings.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NFAPDnyq5Dm", "reviewer": "Reviewer_MY7B", "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": "1- The definition of the stability is for normalized surrogate loss. For instance we might measure the performance with 0-1 loss but train using the cross-entropy loss. I could not find the result in the paper that relate the stability parameter of normalized surrogate loss to 0-1 loss? Note in the Hardt el al paper, we only have one loss function. For instance, in Theorem 2 of  Kuzborskij and Lampert, you can find a such a result.\n\n2- In general, I find it difficult to interpret the results in this paper. Theorem 2 implies that if the initialization point has a very large norm then it helps generalization. Could you please provide more intuition behind this result? Also, please compare your result with Theorem 3 of  Kuzborskij and Lampert, where their bound basically implies that if the distance between the initialization and the optimal point is small, then the sgd is stable for convex case. \n\n3-A technical question is can you provide more details to proof of Theorem 2. Specifically, how do you relate the normalized loss to 0-1 loss?\n\n4-  In the definition of zeta_t, what prevents the denominator to not be close to zero while the numerator be bounded away from zero?\n\n5-  The main quantity for the non-convex setting is the zeta. I could not find any intuition behind this term? Also, how can we compare it with Lipschitz constant?\n\n6- In your experiment you used the batch normalization. However, the theoretical result is obtained for vanilla SGD.\n\n7- In general the figures quality is not good. For instance in Figure 4, the legend and labels are not clear at all. \n\n8- In general, there are lots of \"proposal\" for the relevant complexity measure for generalization. It would be nice to compare your zeta with the proposals. Please check the Table 1 of \"Uniform convergence may be unable to explain generalization in deep learning\" by Nagarajan, Kolter to find a list of such measures. ", "summary_of_the_paper": "This paper considers the problem of understanding the generalization of SGD using the stability framework. The well-known result in this line of work is the paper by Hardt'16. In Hardt'16, the stability is measured using the difference between the \"actual\" weights of two copy of SGD which differ in a single data point. The main observation by the authors in this paper is that in many cases, the loss function is invariant to the scaling of weights. Then, they reformulate the stability analysis using the \"normalized loss function\" which is defined by  l^alpha(w,z) = loss(alpha*w/||w||,z) where alpha is a constant.\n\nTheir main results are the new stability analysis for this new notion for convex and non-convex settings. Specifically, for the convex case the analysis is very similar to the Hardt paper. For the non-convex the authors define a new measure for generalization \"zeta\" in Theorem 4 which governs the stability.", "summary_of_the_review": "Interesting motivation and direction however the paper is not well written and there is no discussion for the results. Also, the numerical results section can be improved greatly.", "strength_and_weaknesses": "", "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:

Meta-review: The paper focuses on providing generalization bounds for SGD for functions that are invariant under scaling. The paper's analysis is based on the stability framework but instead focuses on a metric that is based on the anglular distance as compared to the euclidean distance.

Overall the reviewers found the paper to be interesting and the results to be useful. However the reviewers found the paper to be significantly lacking in terms of its presentation. In particular a clear exposition of the central object of the paper, i.e. normalized loss function was missing as well as clear comparisons between the presented results and existing results. I recommend the authors to motivate their results better and contrast their presented results with existing results to fully highlight the impact of their presented result. Hopefully the suggestions made by the reviewers in terms of presentation will be helpful to the authors towards improving the paper.
Decision: Reject