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

Abstract: We prove new generalization bounds for stochastic gradient descent for both the convex and non-convex case.  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 2021
STABILITY ANALYSIS OF SGD THROUGH THE NORMALIZED LOSS FUNCTION
Anonymous authors Paper under double-blind review
ABSTRACT
We prove new generalization bounds for stochastic gradient descent for both the convex and non-convex case. 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 data-dependent quan- tity 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.
INTRODUCTION
In the last few years, deep learning has succeeded in establishing state of the art performances in wide variety of tasks in fields like computer vision, natural language processing and bioinformatics
(LeCun al., 2015). 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. (2017) and Keskar et al. (2017) hint to 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 to 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) ctt 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 Harda et al. (2016) exploits this framework to study SGD for both the convex and non-convex case. 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 investigate a measure of distance respecting invariances in ReLu 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 high probability bound on the test error of the output of SGD. In the non-convex case, we propose an analysis directly targeted toward ReLu neural networks. We prove 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 our approach is that do not need to assume that the loss function is bounded. Indeed, even the loss function used for training is unbounded, the normalized loss is necessarily bounded.
Our main result for neural networks involves data-dependent quantity that we estimate during training in our numerical experiments. The quantity is the sum over each layer of the ratio between

---

Under review as a conference paper at ICLR 2021
the norm of the gradient for this layer and the norm of the parameters for the layer. We observe that increasing the learning rate can lead to a trajectory keeping this quantity smaller during training. Therefore, larger learning rates can lead to a better "actual" stability than what worst case anal- ysis from uniform stability would indicate. There are two ways to get our data-dependent quantity smaller during training. The first gradients). The second one is by increasing the weights of the network. If the weights are larger, the same magnitude for an update in weight space results in smaller change in angle. In our experiments, larger learning rates are favorable in both regards.
is by facilitating convergence (having smaller norm for the
2 RELATED WORK
Normalized loss functions have been considered before (Poggio et al. 2019). (Liao et al. 2018). 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.] (019) 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. (201 (018) showed that gradient descent converges to the max- margin solution for logistic regression and Lyu
& Li (019) provides and 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, few representative examples are Liu et al.)
London 2017). Yuan et al. (2019), Kuzborskij & Lampert (2018))
Since the work of Zhang et al. (2017) showing that currently used deep neural networks are so much 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 & Lamperi (2018). They develop data-dependent stability bounds for SGD by extending over the work of Hardt et al. 2016). Their results have a dependence on the risk of the initialization point and the curvature of the initialization. They have assume bound on the noise of the stochastic gradient. We do not make this assumption in our work. Furthermore, instead of having the bounds involve properties of the initialization (which can be useful to investigate transfer learning), we maintain instead in our bound for neural networks the properties after the "burn-in" period and therefore closer to the final output since we are interested in the effect of the learning rate on the trajectory. This is motivated by the empirical work of Jastrzebkki 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".
has been observed the early work Keskar al. (207)) that training with larger batch sizes can lead to deterioration in test accuracy. The simplest strategy to reduce (at least partially) the gap with small batch training is to increase the learning rate (He et al. 2019). (Smith & Le| 2018), (Hoffer et al. (017). (Goyal et al. 2017). We choose this scenario investigate empirically the relevance of our stability bound for SGD on neural networks. Remark that the results in Hardt et al. (2016) 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.
PRELIMINARIES
Let l(w, 2) be a non-negative loss function. Furthermore, let be a randomized algorithm and denote by ASS) the output of A when trained on training set S = {21,-.. ",,,, =n J ~ D", The true risk for a classifier w is given as
Lo(w)= = EEwDl(w,2)
and the empirical risk is given by
2

---

Under review as a conference paper at ICLR 2021
Ls(w) == 1i=11w,,22
When considering the 1 loss of classifier w. we will write I Furthermore, we will add superscript when the normalized losses 1at under consideration (these will be defined more clearly in the subsequent sections respectively for the convex case and the non-convex case). Our main interest is ensure small error and we to minimize surrogate loss upper bounding the 0 - loss. In this paper, we consider the algorithm stochastic gradient descent with different batch sizes minimize the empirical surrogate loss. The update rule of this algorithm for learning rates X and subset B, C S of size B is given by
bound (w). The usual approach is
W++1 = We Ae B
Σ 2
Vl(we; 22).
(1)
We assume sampling uniformly with replacement order form each batch of training exam- ples. In order to investigate generalization of this algorithm, consider the framework of stability (Bousquet Elisseeff 2002).
We now give the definitions for uniform stability and on-average stability (random pointwise hy- pothesis stability in Elisseeff et al. (2005)) for randomized algorithms (sce also Hardt et al. (2016) and Kuzborskij & Lampert (2018). The definitions can be formulated with respect any loss func- tion but since we will study stability with respect to the la losses, we write the definitions in the context of this special case.
Definition The algorithm said to be -niffornyyyyy stable for all i [I....,n.
E [A)( S
sup
< Cuns.
Here, the expectation is taken over the randomness of A. The notation S(i) means that we replace the tt example of S with z
Definition 2 The algorithm A is said to be cav -nn-uvverrge stable if for all i (1....,m.
E
(((()))))(( Saav
(3)
Here, the expectation is taken over S ~ D z ~ D and the randomness of A. The notation 5(0)
means that we replace the ith example of S with z.
In Hardt al. (2016), uniform stability with respect to the same loss the algorithm is executed on considered. This a natural choice, however if we are interested in the 0 loss, different set of parameters w, w' 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 also the case for Relu neural networks where we can rescale each layer without affecting the classifier. This is why we consider stability with respect normalized losses instead. Remark that we are still considering SGD executed on the original loss / (we do not change the algorithm A). The intuitive idea is to measure stability terms of angles (more precisely, we consider distances between normalized vectors) instead of standard euclidean distances (see Figure The proof in Hardt et al. (2016) consists in bounding E||w; - w/ll. where w; represents the weights at iteration when training on and wi represents the weights at iteration when training on modified training set 5((), We will instead bound
Elll |wal and g)
|w (or E[d(f.g) g)] for an appropriate measure of distance between neural networks
Throughout the paper. || 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.
3

---

Under review as a conference paper at ICLR 2021
(0.0)
Figure I: For the same magnitude of step taken (same ball radius), larger norm of parameters leads smaller change in angle.
4 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
1st (w,, = 1(a ||m| 2),
w
(4)
for a > 0.
In order state the main result of this section, we need common assumptions: L-Lipschitzness of as a function of w and -B-smoothness.
Definition The function Iww, 2) Lipschihi for all the domain (with respect to w) if for all w, w', z,
I[w, =) - 1(w' (()] S Ll w'll
(5)
Definition 4 The function lw, is B-smooth if for all w, w', [Vl(w, 2) Vl(w', 2)]l s Bl| w'll
(6)
We are now ready state the main result of this section.
Theorem Assume that 1( 2) is convex, 3-smooth and L Lipschitz for all Furthermore, assume that the initial point we satisfies || 2 K for some K such that K K-L X; for sequence of learning rates d; S 2/3. SGD is then run with batch size B on loss function 1(w, for T steps with the learning rates de starting from Wo Denote by eans the uniform stability of this algorithu with respect 1 Then,
2L T
S S a
Σ 1=0
A
nk
What is the difference between our bound and the bound in Hardt et al. (2016) (see theorem 6 in Appendix(A) ? Our bound says that it not enough to use small learning rate and small number of epochs to guarantee good stability (with respect to the normalized loss). We also need to take into account the norm the parameters (here the norm of the initialization) to make sure that the "effective" learning rate is small. As a side note, we also incorporated the batch size into the bound which is not present Hardt al. (006)) (only B is considered).
From this result, is possible to now 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 test error over the randomness of here the posterior distribution would be induced from the randomness of the algorithm A.
the bound. This is reminiscent
MCC-Bayes bounds where
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 do not converge to 0 when the size of the training set grows to infinity.
4

---

Under review as a conference paper at ICLR 2021
Theorem 2 Fix > O. Let Ma := sup(l(w, 2) s.t. ||l|| I aa ||||| - RJ. Then, for any > 1 and E (0, the following hold with probability greater or equal to over draws of training seis S:
In(1/6) 2n
EALL) BALG(A(S)) Euui + (2ne + Va)
The proof is application of McDiarmid's concentration bound. Remark 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 theorem 12 in Bousquet & Elisseeff (2002) and we do not replicate it here. Remark that we need to use that uniform stability implies generalization in expectation which proven for example in theorem 2.2 from Hardt et al. (2016).
Proof:
Furthermore, we can make the bound hold uniformly for all a's using standard techniques.
Theorem Let C > O. Assume that 1 (w. 2) is a convex function of a for all w, z and that Cuni non-decreasing function of a. Then, for any n 1 and 6 E (0, 1), the following hold with probability greater or equal to - 8 over draws of training sets S:
(AI--((((S)) s
inf aE(0,C)
EA max (L') 2 (A(S), (3(S))) + Cuni + (2nc +
2ln log2 C log, a)) In(1/8)
V
2n
In the next section, investigate the non-convex case (actually we target directly neural networks). We exploit on-av on-average stability to obtain data-dependent quantity in the bound. Remark that it is also argued in Kuzborskij & Lampert (2018) that the worst case analysis of uniform stability might not be appropriate for deep learning. Finally, observe that if we use only one layer we get linear classifier and so the results from the next section also applies to logistic regression for example.
NON-CONVEX CASE
We consider ReLu neural networks (although could easily extend other Lipschitz linearity) in the setup of multiclass classification. Write f(x) (xx) = Wi(a(... Wz(o(W)x))) where x an input the neural network, W; denotes the weight matrix layer and denotes the ReLu function. Consider non-negative loss function [(s, y) that receives a score vector & f(x) and label y as inputs. We require the loss function be L-Lipschitz for all y as function That is, for all s, v.
[(s. v) l(s', 3) S L||s s'Il.
For example, we can use the cross-entropy loss (softmax function with negative log likelihood). In this case, it is simple show by bounding the norm of the gradient of ((x, y) with respect to that can use v2. Remark that this slightly different from the Lipschitz assumption of the previous section (given with respect to the weights w).
Lemma Assume that |||||| < R. For S j S I, write = (W(((()))()))))) and &f Wo. (((o(W(2))), We have
W. is [Wll if }
||s: +|1 $ R Σ
||,. Will j=1
II
(10)
The previous lemma motivates measure of "distance" between neural networks.
Definition For neural networks I and g, where the weight matrices of f are given by W Wi and the weight matrices of g are given by Wt ... W define
W,
W! ||W|||
d(f.g) = Σ
(11)
||alll
1=1
5

---

Under review as a conference paper at ICLR 2021
Remark that this distance function is invariant to rescaling the weights of any layer. This is de- sirable property since a ReLu network such a reparametrization leaves the class predicted by the classifier unchanged for any input to the network.
Let 01, t.....ay at be positive real numbers. We define the 191.n0y losses as
Wi pa (f,z) == ( [iil (a(- 02 [|&ll
W2
W1 [Wi]] r)))) v),
(a(a)
(12)
where: z (x, y) and f is the neural network with weight matrix at layer given by W,. That is, we project the weight matrices to give the norm to layer i and then we evaluate the loss on this "normalized" network. For simplicity, we will only consider the case where all the aj are equal to say a and we will write 1 2J. From our definitions and lemma 1
we have that for all and
neural networks f and g.
(f, 1" (g, & LR LRo'd(J,9)) d().)).
(13)
In order to bound stability with respect to 1*, we will have to ensure that the two trajectories cannot diverge to much in terms of d(f.
We will make two main assumptions to prove our main result. The first one is a modification of the concept of 8-smooth functions for neural networks.
Definition Consider the gradient of the loss function with respect the parameters W for some training example 2. The vector containing only the partial derivatives for the weights of layer j will be denoted by V() 2). We define {55g 11 -1=1--ayerwis smoothness as the following property: For all j. 2, W- = (W1,'** - Wi) and W (WI,-- W().
([))) V(I("" =)]1 S 331lW, -Wjl-
(14)
We also let 3 max Remark that B3 is upper bounding the spectral norm of the bloc diagonal approximation of the Hessian.
Next, we introduce an assumption meaning informally that with high probability, the norm of pa- rameters of each layer is eventually non-decreasing.
Definition 7
Let O. The growing norms assumption (for this value of e) is defined as the
following: The distribution 'D satisftes the property that there exists tn E (0. 1.... B the probability over draws of training sets from D and over the randomness of of generating non-decreasing sequence ||W sal for all j is greater or equal to -
a such that
In Figure 2 we can see that on Cifar10 and Mnist this assumption makes sense (more details on experiments in section 6).
(a) C0
(b) Mnist
Figure 2: Norm of parameters for 3 different layers when training convolutional network Ci- farl0 and fully connected network on Mnist with SGD.
We are now ready to state the main theorem of this section.
Theorem Let e 2 0 and assume that the distribution D satisfies the growing norms assumption for this value of c. The notation to E (1,2,... will now mean implicitly also that to is large

---

Under review as a conference paper at ICLR 2021
enough that the sequence of norms is non-decreasing. Suppose that the loss function [s., y) is L--ipsshitza for all y. non non-negative and that 1 (f. 2) is bounded above by Ma. Furthermore, assume { smoothness and that ||=||| S R. Finally, let B denote the batch size. x the learning rates and T the number of iterations SGD is being run. Then,
Eav S
inf toE (1,2,,,
2BLRo
(T-1)
T-1
Σ t=
Blo Se + Ma
+ +0)
(15)
(n B)
where Si : =E E SA min ([W B W
| (W and? 3 max {31}.
Exploiting theorem 12 in Elisseeff et al. (205)) we can get a probabilistic bound on the test error (holding over the randomness in the training sets and the randomness in the algorithm).
Theorem 5 Fix a > 0. Then, for any n > 1 and ā E (0, 1), the following hold with probability greater or equal 6 over draws of training sets S and the randomness of the algorithm A:
(A(()) & L3(A(5)) + V())
2M + 12nMaca
(16)
6 EXPERIMENTS
6.1 LEARNING RATES AND Çe
In this section we conduct some experiments on the datasets C0far10 and Mnist. We consider the scenario where we try to reduce the performance gap 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.
Remark that the bound on stability for neural networks hold for learning rates satisfying X, S c/t. This is not very practical schedule for deep learning and so we use a global learning rate being de- cayed one time by factor of 10 instead in our experiments. We use no weight decay or momentum to stay closer to our theoretical analysis of SGD. Remark that in principle, the learning rate could be as large as we want during the inital burn-in period (before 40) without hurting stability. However, this burn-in period must be inside the first epoch in the theoretical result we presented. Since in practice we train for many epochs, it is not clear such a small burn-in period is long enough to be significant in current practice. We still think that the quantity Çe is relevant to investigate empirically.
We approximate its value on a training set S with the quantity (())) == Σ/= || I.' (W:)ll Instead of plotting the value for each iteration, average (5)) for each epoch. This leads to smoother curves.
[|,
We use 5-layers convolutional network consisting in 2 convolutional layers with maxpooling and then 3 fully connected layers with cross-entropy loss on Cifar10. We use also the cross-entropy loss on Mnist but the neural network is 6-layers fully connected network. In both cases, use batch-normalization to facilitate training. All the results in the figures are obtained when using a 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, we obtain test accuracy of 56.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.14%. This happened even if the training loss is reaching 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.52% (Ir = 0.05), 98.00 08.00% (Ir = 0.1) and 98.39% (Ir = 0.5). We plotted the values of (((S) during training in figure We
that it is better during all training when increasing the learning rate.
To compare with the analysis from Hardt et al. (211)). the quantity Ç. would be replace with a global Lipschitz constant which would not be affected by the actual trajectory of the a algorithm. Therefore,
7

---

Under review as a conference paper at ICLR 2021
in comparison 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 result to guarantee good stability. The quantity Çe can be improved by accelerating convergence because the numerator (norm of the gradients) but also by increasing the denominator (norm of the parameters). A larger learning rate help in both these regards (see figure 4 and figure 5). Remark 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 gradients and the norm of the parameters. A standard analysis of stability (without the normalized loss) similar Kuzborskij Lampert (2018) would benefit from the norm of the paramters.
0.5
03-
0--0
0-
33-
0x-
02-
02-
31.-
0.1
(a) C0
(b) Mnist
Figure 3: (S) when training convolutional network on Cifar10 and fully connected network on Mnist.
grudier nonn VND spoch
gruchers mOOH VNEG spoch
2.-
132
30
120
200
250
300
20
06
300
(a) Cifar10
(b) Mnist
Figure 4: Norm of the gradient when training a convolutional network on Cifar 10 and a fully con- nected network Mnist.
8

---

Under review as a conference paper at ICLR 2021
342
23
13
apack
opace
(a) Cifarl0
(b) Mnist
Figure 5: Norm of the parameters (layer 3) when training convolutional network Cifar 10 and
fully connected network on Mnist.
6.2 GENERALIZATION BOUND AND TEST ERROR
We show in this section the usefulness of considering the normalized loss for bounding the test enror. We evaluate the bound in theorem 5 and compare 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 upper bounded by the Lipschitz constant times the euclidean distance between the weights of the networks. The Lipschitz constant replaced by the largest norm of gradient obtained during training. For the normalized loss (our actual theorem 5), we upper bound C2p by LRa Ed(f, g) (see equation 13). We plot the test error, the upper bound for the normalized case with a 1.0 and the upper bound for the unnormalized case in figure 6
analogous version for the unnormalized
Generalization bounds and test error
10000
val errori
bound euclid
alpho_1don
4000
20
40
00
100
opoch
Figure 6: The bound obtained from the euclidean distance is much worst than the bound obtained from our normalized distance. The network is a 6-layer fully connected network and the training set is 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 clas- sifiers. 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-average stability with respect 1 losses for different optimization algorithms.

---

Under review as a conference paper at ICLR 2021
REFERENCES
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, Yangging Jia, and Kaiming He. Accurate, large minibatch SGD: training im- agenet in hour. CoRR, abs/1 706.02677, 2017. URL httt:://arxiv..or/abbbs.
02677
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. 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 httptttp:/pppoceeeinneee mlr., press/ v48/hardt.1 ht.l
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. 143--115.. 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 Szymezak, 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 n htte///orrmmii// wwa.mndddrrlg@1 lo
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017. URL. id Hloyyygyy
net forum?
Iija Kuzhorskij and Christoph H. Lampert. Data-dependent stability of stochastic gradient de- scent. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmüssan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 2820-2829. PMLR, 2018.
Yann LeCun, Yoshua Bengio, and Geoffrey E. Hinton. Deep learning. Nature, 521(7553))466 444, 2015. doi: 10. 10.18/8/nt 14539. URL /att:s:://oi..crr/11.11/////////
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.09654/ 2018.
URL http::ttp:/:tiilee org/ abs//bb///11 1807 1b0.1137009659 09659
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-2167. PMLR, 2017.
Ben London. A pac- bayesian analysis of randomized learning with application to stochastic gradi- ent 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 homogencous neural networks. CoRR, abs/1906 2019.
10

---

Under review as a conference paper at ICLR 2021
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent separable 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-3059 PMLR, 2019.
data:
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. In Advances in Neural Information Processing Systems 32: Annual Con- ference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pp. 11611 11611-1166 11222 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Proceedings of The 28th Conference on Learning Theory, COLT Paris, France, July 3-6, 2015, pp. 1376-1401, 2015. URL http: http:///poccceen..../e/o ml http://iinnnnm....rrsseeseseeeee press/v407
Tomaso A. Poggio, Andrzej Banburski, and Qianli Liao. Theoretical issues in deep networks: Approximation, optimization and generalization. CoRR, hts/1908.093755 2019, URL http:
09375
Samuel L. Smith and Quoc V. 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:
//openzeview. net wtt.:/foummmii de=oormmmiiBBiiBp.. 44yg02]
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, and Nathan Srebro. The implicit bias of gradient descent on separable data. In 6th International Conference Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings, 2018. URL httptttts///peeeeeeeee
net forum? id=rl
Zhuoning Yuan, Yan Yan, Rong Jin, and Tianbao Yang. Stagewise training accelerates conver- gence of testing error over SGD. In Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 De- cember 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. http:tttt:/:ppeeeeeeee
A APPENDIX: PROOFS FOR THE CONVEX CASE
We start by proving few lemmas.
Lemma 2 Let v, Rn and 0 < c min([|e]] [[=]]]]
Then,
The proof follows from basic linear algebra manipulations. We give it here for completeness since it important in what follows. We need to show that
Proof:
w.p
T
After some manipulations, one can that this is equivalent show that
||| + || 2c - 2(c2 ||е||]ыи| TeT
w WT 2 0.
w [|ll < Since c² - ||l|||aaa|| S 0. the proof will be From Cauchy-Schwar inequality, (|"1|1" completed by showing that
||a||2 ||wl|2 2- 20 2(2 |||||||||| 0.
11

---

Under review as a conference paper at ICLR 2021
But this is true since
||e|l2 + |w|l |||||||b||| - (lpll - -|wl))
Lemma Assume that the update rule is ry expansivv. Furthermore, assume that ||G(v)] and [[G(w]] are larger than Kmy. Then,
G(an)
G(v) [[[
[|o-w|l K
G[#)]
Proof: For v and satisfying the assumptions, we have
G(o)
G(w)
|[G())G((w]]
||o-w|l
[G(
Kn
K
Lemma Assume that the update rule is obbounded, that [|G(w) wil for all w. Further- more, assume that ||G(x)]] 2 K and ||G(w)]] 2 K. Then,
G(w) [
G(v)
[1--wil + 24 K
-
K
Lemma Assume that the initial point we satisfies ||wol| 2 K and that SGD is run with batch size B and sequence of learning rates dS on an L- Lipschitz loss function U(w, 2) for all z. Then, for all t 2 1
|well 2 K 1. A,
Proof:
B Ac-1
||wlll = ||
v((wa-1:
B j=1
|| |||
Xp-
11(
j=1
IW WWW
||
||
X A--L
||ol||
X
i=0
K
A
i=0
For case of comparison, we give the statement of theorem 3.8 in Hardt et al. (2016).
Theorem (Theorem 3.8 Hardi et al. (2016)) Assume that the loss function f(:; 2) 3-smooth, convex and L-Lipschitz for every Suppose that SGD with step sizes a4 2/ 3 for T steps. Then, SGD satisfies uniform stability with
21 T
Euni
a
71
We ready prove proposition) 1
Proof of theorem I The proof similar to Hardt et al. (2016). Let w; denotes the output of A after t steps on training set and w/ be the output of after t steps on training set S() for some i E {1, ..)... From convexity, the update rule is 1 1-expansive (see lemma 3.7 from Hardt et al. (2016)). Furthermore, it follows directly form our lemma 5 that the assumptions in both lemma 3 and lemma are satisfied (we can
L. iteration in lemma 4). Since the probability of
12

---

Under review as a conference paper at ICLR 2021
picking the example i in mini-batch of size B is smaller than & have
(sampling with replacement),
W++1
w/+1
E W4
w/ll
+2
L.dt
+
B
B u2x w/ll
Wettll
n
K
K
71
K
2BL
E Bl - will +
K
Remark that this true since (with a slight change to allow any batch size B), we have
Ell Ellwa-w'll
+2 + Lie.
From the result in Hardt et al. (2016)
K
K
B Bllwe - w/ll S 2BL Σ Az.
Therefore,
E
Wc+1 1ee+s
1h/1 The
28L nk
Ei X;
The result then follows from the inequality
Ma m T 2)
m/' 1(a
(wo [2] < Lail
[w
We finally prove theorem 3
Proof of theorem 3 To simplify the text, write c(a, 8) = ExL3(A(S)) + Coas + (2nc + 5 For any fixed i, we have For 2 1, let a, = 2(1-) and d; 27
Ma)
2n
(A(SAL) e(a,,, < 6,.
Therefore,
Ps(vi, BALD-(((S)) & E( 6:)
0-1 (A(S)) > E(a;; 6,)} 1- Ps(ii, E
20
1
L0- Ps 0-1 (A(S)) > c(a,, 8,))
1
8, 2 1
The last inequality follows from
8
n
8
5.
2
72
2
6
1=1
i=1
We want to show that the set
(S: Vi, EA (A(S)) S e(ax,
is contained in the set
{S: Va E (0,C), BALL-L(ASS)) 2
E max (A()) (3(A()))
Ctab (2nc Stb Ma) 221(V2(2+log, C-log, +l)
2n
13

---

Under review as a conference paper at ICLR 2021
Let S be such that Vi, ( z c(a,, Let (0, Cj.
Then, there exists such that
ag I a S 20s. We have
In(1/8.)
(A(5))(AS5))
< BATg5(A(5)) + Stab + (2ne ot Mo:)
2n
In(1 (6,)
s BAL' (A(S)) + Glab + (2mcstab Ma)
2n
2ln(v2(2 + log, log, a)) + In(1/0)
s (A(S) + + + (2ne = Ma)1
2n
The second inequality is true since both c stab and Ma are non decreasing functions of a and a, The last inequality is true since 21 I 2(2+log; Co-oo,a)² Finally, the proof is concluded by using the convexity of (A()) with respect to Indeed, since 2 S az a, must have
(A(S)) S max ( (A(S))))3((()()))
B APPENDIX: PROOFS FOR THE NON-CONVEX CASE
Proof of lemma 1 The proof is done by induction the number of layers 1. Suppose the result is true for - layers. Then we have,
||s: s/ll
[[ - W/o(s(-1)ll
([ (ooos_)))W((o(i-----oo-o---
[s - -/o(s--)l1--11/(((((11)--) o(--)))
|[ Will || -
|[;
1-1 W| Will | $|-1/1
i=
R|[W;
Will II
[-1
[[SI
|| R
I
Will
II jmlj
5
]
Will [
if 1
R Σ
w.
Will
II デ=
We exploited the fact that the ReLu non-linearity cannot increase the norm of a vector and also that 1-Lipschitz. The proof is finally concluded by observing that for one layer have, ||s sıll S
R| W. - Will-
Definition 8 Let us introduce some notations. Let (S, = 1|W - Wiall and (S,
E 2) Vk, (k) (S,z) = 0j. Here, Wj,, is obtained when training with S for iterations and W is obtained when training with 5(0) for iterations. The condition inside the expectation that after to iterations, the two networks are still exactly the same. Since we are interested in
distances after normalization, we consider (S,2) 11 Waa W
11 TW and ( (S,z) =
EA( (35) (S,2) (S, Vk. 0/20) (S. z) 0]. We will further need 8.2) (S,2): = ((.)).
and (1) (S)
(S,(
8 () (8, (S, 2) Vk, (/ (() (S, 0). where (()((S,) == min (lni IIW,
Before proving theorem 4 establish a lemma. Remark that the structure of the proof of the following lemma and of theorem 4 is similar to the corresponding results in Hardt et al. (2016) and in Kuzborskij & Lampert 2018
14

---

Under review as a conference paper at ICLR 2021
Lemma 6 Let O and assume that the distribution D satisfies the growing norms assumption for this value of e. The notation to E (0.1.2.... B will now mean implicitly also that to is large enough that the sequence of norms is non nec-dacrga,..g. Suppose that the loss function (s. y) is I.Ipipschitz for all non-negative and that ([, is bounded above by Ma Also, assume that ||-||| S R. Furthermore, let B denote the batch size and T the number of iterations SGD is being run. Then, for any to E 10, Bh. the on-average stability satisfies
Gon S LR Σ Bs,: BA (T
0/0 (S,
o0
+ Mal
Btg
+ c).
n
Proof: Since 1 (f, is bounded above by M,, and non-negative, we have
(f,)) 10 (g. =)1 S Mo.
Therefore, by adding term M& the bound, growing norm assumption is satisfied. We won't 't write that the expectation is then conditional on that assumption to lighten the statements. By similar line of reasoning,
then only consider the case where the
further condition inside the expectation with the property that after to iterations, the two networks are still exactly the same. To make this clearer, write the quantity (f, [" z)] the of (f. 2) (g, [Vkk, of*) (S, 2) = 0} and (}, - (9, [ / (5, + 0}. We bound the first term by using the fact that
(f. ( I.Ro'd(,.)) LRR Σ
30) 0f (S,
j=1
For the second term, we use that 1 (f, =) is bounded above by Ma and non-negative to write again (e, (g. Mo.
The result then follows from the fact that the probability of picking example i in to iterations is smaller than Blg
Proof of theorem From lemma always have (S, s (S, Therefore, from the previous lemma,
Blg + c).
c. S LRa' Σ Es.:
( + Ma
1=1
First remark that under our assumption,
0,2, (5)
30) (S,
(S,,
(S,
K (S,)
(S,)) AeIl A (O) (W))l
(S,
(S, + LB. (W,) v (W))
K(D)
Here, B, denotes the batch of samples at iteration when training on S and Bj denotes the batch of samples at iteration when training on 5(6), When B, B/. we will use 1 smoothness to bound || [ LB, (W,) v Lay (W/)I) Otherwise, we use simply the triangular inequality. Let p(B, n)) be the probability of picking the example in mini-batch of size B (this is smaller than 2). For > lo. have
15

---

Under review as a conference paper at ICLR 2021
(00:)))0-000 + (S)
|| 11 LB,
AEA
(8,
K, (8,2)
Define - := Es.: ( 2) and c = EA,S. LB, for any t. Taking the expectation over 5 and 2 on both side of the previous inequality, we get
(8,0)
1 S (1 - P(B, 33 A) + ((B + +
This is true since A,S,, Le, (8,)
I. (S,))
EAS,,
Rearranging terms and using
1 + x s exp(x), we get
A 0)
< [1 (1 (1--pp (BB + +2p(B, n))c (6)
141
exp((1 (333)))33) - 22((B,)
Developing the recursion, we get
T-1
T-1
c3j
S
Σ
2p( B, m)
(1)
II exp
(1-m(B,n)) (B, n²)
t=
h=t+1
T
T-1
2B
X (1) exp
(1- p(BBn))eBB
Σ
k=++1 k
t=
2B
Σ
( exp
(1 (i-p(B, log(
T T-1 1
n
2Bc
T-1
(1)
T
(1 (1-p(B.n))33}
t
t
2Bc
(1)
T
(1 (1-p(B,n))c
11
T
(1 (I-((B,n))a8-1
2Bc
(B) -
Σ
max
11 15SIST-1
t=to
2Bc
(c(0))
T (T' 1
(1 (1-P(B,n))c3
max
nc(1 p(BB n))33
S1515-
to
2B
T
max
(n - B)3 to -
65517
Therefore,
inf to (1.2........ 3] (n B)
2BLRa
T
c3
max
(c00) Ma
Blo
+
+c]
to
n
To complete the proof, we will use that max ((()))
I Et=to St and reverse the sum
T-
(
order. With the definition & = E/= (i) we then have
2BLRa'
(T T-11
T T-1
Btg
+ o)
inf 10,.1,
Σ t=
Ge + Ma
$} (n B)3 to -
n
16


Reviews:
[{"review_id": "lWIp8olLvty", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper develops new stability bounds for SGD. The main difference from the existing studies is that they consider stability bounds for normalized loss functions where the parameters are normalized to have a norm of $1$. This paper considers both convex and nonconvex cases. For the convex case, the authors develop uniform stability bounds and high-probability bounds. For the nonconvex case, the authors develop on-average stability bounds for neural networks. Experimental results are also given.\n\nComments:\n1. The motivation should be further clarified. In particular, it is not quite clear to me the advantage of considering normalized loss as compared to the standard loss. At least I can not see the advantages from the theoretical results.\n\n2. In Thm 1, the authors assume that the norm of the initial weight is larger than the summation of step sizes. I think this is a very strong assumption and can be violated if we run sufficient number of iterations. Furthermore, it seems that the argument is incremental. The analysis heavily uses the existing stability bounds in Hardt 2016. It seems that the authors do not introduce new techniques. The stability bounds grows as a linear function of the batch size. This dependency on the batch size is not desirable since it means that the generalization would decrease by a large amount if we increase the batch size.\n\n3. In the non-convex case, the authors consider RELU neural networks and assume the smoothness of loss functions. However, RELU networks are not smooth. Therefore, the smoothness assumption in the theoretical results is violated.\n\n4. In Thm 4, the authors assume a growing norm assumption: the norm of layer-wise weights are non-decreasing after some iterations. This is a very strong assumption and can be easily violated in practice. Although the authors give some examples to show this can happen, I still believe it is far from true in general.\n\n5. The stability bound in Thm 4 depends on $1/\\|w\\|$. If we encounter weights with very small norms, the bound would be very large. Furthermore, both the stability bound and the generalization bound involves $\\epsilon$, which is not decreasing w.r.t. either $T$ or $n$. This shows that the result is not converging which is a basic requirement in statistical learning theory.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Nn8K1GlJcLr", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper considers the generalization bound for stochastic gradient descent. The authors leverage normalized loss function to analyze the stability of SGD algorithms which further yields the generalization bound. They provide the on-average stability result for non-convex optimization under the ReLU neural network setting. The theoretical results deepen our understanding of the performance of the SGD algorithm and an experiment is provided to illustrate theoretical findings.  \n\nReasons for score: \n\nOverall, this paper is well-written, and the idea of using normalized loss function to assist the theoretical analysis is interesting. My major concerns are listed below. Hopefully, the authors can address them in the rebuttal period. \n\nHere are some comments:\n\n1) The idea of the normalized loss function should be discussed in detail. It is not very clear what is the motivation behind it and how this assists the theoretical analysis.\n\n2) In the experiment, the authors compare their analysis with the one in Hardt et al. (2016). However, I think they should compare it with the one in Kuzborskij & Lampert (2018). Throughout this paper, this comparison should also be provided in their theoretical results. \n\n3) Their main theoretical results seem to be direct corollaries following from Hardt et al. (2016) and Elisseeff et al. (2005). The proof is trivial and it is preferred to explain their technical innovation.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4RR6wJ9bMcQ", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper discusses the uniformly statbility and on average stability of SGD on convex and nonconvex optimization algorithms. With proper choice of step size, the stabilities can be theoretically bounded. The convex case extends from Hardt et al. For the nonconvex case, the result is concrete and can be applied to neural nets.\n\nA few questions/suggestions about writing. If they are addressed I'm glad to raise my rating.\n\n1. I'd like to see more discussions about the bound for non-convex theorem. The quantity in Thm4 is a bit hard to interpret. Perhaps some examples can be given in appendix, such as matrix factorization, neural networks, and compute $\\epsilon_{av}^\\alpha$ with respect to data and parameters.  \n2. I'd like to see more comparison with related literatures, specifically carefully compare to Hardt et al. Thm5 is kind of similar to Rademacher complexity which is widely used in other generalization type of papers, such as Du and Allen-Zhu's papers, so I'd like to see them as well.\n3. If the length is not limited for appendix, it's more clear to put Hardt et al proof in it. Even if the exact same procedures are used, the sequence of lemmas and critical ideas can be listed so readers know which thm is quoted/replaced for the scope of this paper. \n4. If possible I want to see an end-to-end result in appendix. Say we take an nn and train it with some algorithm, what is the time complexity, training error and generalization error, and what is the overall algorthm for this ml task and how to tradeoff, etc. \n5. Defs need more clarification. With $l(w,z)$ and $l^\\alpha(A(S),z)$, $S = \\{z_1,...,z_n\\}$, I feel that $z$ is the data. So $w$ and $A(S)$ are also data? When saying \"$A(S)$ is the output of $A$\", does it mean the algorithm recovers the parameter, and uses the model with this parameter to label the training set, and you observe the difference with true training labels? In Def. 2, is $z$ a single random sample or the set of samples $z_1,...,z_n$? Since $S= \\{z_1,...,z_n\\}$ also shows up, I guess that $z$ is another single random sample to avoid redundancy. In $l^\\alpha(A(S^i),z)$, $z$ replaces some data, and what about $l^\\alpha(A(S),z)$, why does $z$ appear here? And what does the superscript $\\alpha$ mean?\n\n===================== Update =====================\n\nRaised to 6. A theoretical calculation on 4. would be great, if it can be done before publication. NN can be simplified, say linear, or one hidden layer linear. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers generalization analysis of SGD using stability analysis. The authors argued the use of normalized version of the loss function, and angle-wise stability. However, the reviewers pointed out that both motivation and novelty of the current work are not strong enough for it to be accepted by ICLR.
Decision: Reject