Year: 2021

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.

heading: 1 INTRODUCTION
text: In the last few years, deep learning has succeeded in establishing state-of-the-art performances in a wide variety of tasks in fields like computer vision, natural language processing and bioinformatics (LeCun et 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 a rich interplay between regularization and the optimization process of learning the weights of the network. The idea is that a 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 is particularly well suited to investigate learning algorithms directly is the framework of stability (Bousquet & Elisseeff, 2002), (Elisseeff et al., 2005). It 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 of Hardt et al. (2016) 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 a 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 to 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. In 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 our 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-dependent quantity that we estimate during training in our numerical experiments. The quantity is the sum over each layer of the ratio between
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 are two ways to get our 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 an update in weight space results in a smaller change in angle (see Figure 1). In our experiments, larger learning rates are seen to be more favorable in both regards.
Our main contributions are summarized as follows:

heading: 2 RELATED WORK
text: 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 is one motivation for our study. We might expect generalization bounds on the test error to be 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.
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. (2016). Their results have a dependence on the risk of the initialization point and the curvature of the initialization. They have to assume a bound on 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
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 Jastrzebski et al. (2020) arguing that in the early phase of training, the learning rate and batch size determine the properties of the trajectory after a “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. (2017) that training with larger batch sizes can lead to a 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., 2017), (Goyal et al., 2017). We choose this scenario to 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.

heading: 3 PRELIMINARIES
text: Let l(w, z) be a non-negative loss function. Furthermore, let A be a randomized algorithm and denote by A(S) the output of A when trained on training set S = {z1, · · · , zn} ∼ Dn. The true risk for a classifier w is given as
LD(w) := Ez∼Dl(w, z)
and the empirical risk is given by
LS(w) := 1 n ∑n i=1 l(w, zi).
When considering the 0− 1 loss of a classifier w, we will write L0−1D (w). Furthermore, we will add a superscript α when the normalized losses lα are 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 to ensure small test error and so we want to bound L0−1D (w). The usual approach is to minimize a 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 λt and a subset Bt ⊂ S of size B is given by
wt+1 = wt − λt 1
B ∑ zj∈Bt ∇l(wt, zj). (1)
We assume sampling uniformly with replacement in 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 hypothesis stability in Elisseeff et al. (2005)) for randomized algorithms (see also Hardt et al. (2016) and Kuzborskij & Lampert (2018)). The definitions can be formulated with respect to any loss function but since we will study stability with respect to the lα losses, we write the definitions in the context of this special case.
Definition 1 The algorithm A is said to be αuni-uniformly stable if for all i ∈ {1, . . . , n}
sup S,z′i,z
E [ |lα(A(S), z)− lα(A(S(i)), z)| ] ≤ αuni. (2)
Here, the expectation is taken over the randomness of A. The notation S(i) means that we replace the ith example of S with z′i.
Definition 2 The algorithm A is said to be αav-on-average stable if for all i ∈ {1, . . . , n} E [ |lα(A(S), z)− lα(A(S(i)), z)| ] ≤ αav. (3)
Here, the expectation is taken over S ∼ Dn, z ∼ D and the randomness of A. The notation S(i) means that we replace the ith example of S with z.
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.

heading: 4 CONVEX CASE: A FIRST STEP TOWARD THE NON-CONVEX CASE
text: Since the convex case is easier to handle, it can be seen as a good preparation for the non-convex case. Consider a linear classifier parameterized by either a vector of weights (binary case) or a matrix of weights (multi-class case) that we denote by w in both cases. The normalized losses are defined by
lα(w, z) := l(α w
||w|| , z), (4)
for α > 0.
In order to state the main result of this section, we need two common assumptions: L-Lipschitzness of l as a function of w and β-smoothness.
Definition 3 The function l(w, z) is L−Lipschitz for all z in the domain (with respect to w) if for all w,w′, z,
|l(w, z)− l(w′, z)|≤ L||w − w′||. (5)
Definition 4 The function l(w, z) is β−smooth if for all w,w′, z, ||∇l(w, z)−∇l(w′, z)||≤ β||w − w′||. (6)
We are now ready to state the main result of this section.
Theorem 1 Assume that l(w, z) is convex, β−smooth and L−Lipschitz for all z. Furthermore, assume that the initial point w0 satisfies ||w0||≥ K for some K such that K̂ = K −L ∑T−1 i=0 λi > 0 for a sequence of learning rates λi ≤ 2/β. SGD is then run with batch size B on loss function l(w, z) for T steps with the learning rates λt starting from w0. Denote by αuni the uniform stability of this algorithm with respect to lα. Then,
αuni ≤ α 2L2B
nK̂ T−1∑ i=0 λi. (7)
What is the main difference between our 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 use small learning rates and a small number of epochs to 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) to make sure that the “effective” learning rates are small. Note that all classifiers are contained in any ball around the origin even if the radius of the ball is arbitrarily small. Therefore, all control over stability is lost very close to the origin where even a small step (in Euclidean distance) can lead to a drastic change in the classifier. The norm of the initialization must therefore be large enough to ensure that the trajectory cannot get too close to the 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 (l = 1 layer in the results of section 5). As a side note, we also incorporated the batch size into the bound which is not present in Hardt et al. (2016) (only B = 1 is considered).
From this result, it is now possible to 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. 1 So, we actually have the expected
1It is possible to obtain a bound holding over the randomness of A by exploiting the framework of Elisseeff et al. (2005). However, the term involving ρ in their theorem 15 does not converge to 0 when the size of the training set grows to infinity.
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 2 Fix α > 0. Let Mα := sup{l(w, z) s.t. ||w||≤ α, ||x||≤ R}. Then, for any n > 1 and δ ∈ (0, 1), the following hold with probability greater or equal to 1− δ over draws of training sets S:
(8)EAL0−1D (A(S)) ≤ EAL α S(A(S)) + α uni + (2n α uni +Mα)
√ ln(1/δ)
2n .
Proof: 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 & Elisseeff (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 et al. (2016).
Furthermore, a bound holding uniformly over all α’s can be obtained using standard techniques.
Theorem 3 Let C > 0. Assume that lα(w, z) is a convex function of α for all w, z and that αuni is a non-decreasing function of α. Then, for any n > 1 and δ ∈ (0, 1), the following hold with probability greater or equal to 1− δ over draws of training sets S:
EAL0−1D (A(S)) ≤ inf α∈(0,C]
{ EA max (Lα/2S (A(S)), L α S(A(S))) + α uni + (2n α uni +
Mα)
√ 2 ln( √
2(2 + log2 C − log2 α)) + ln(1/δ) 2n
} .
In the next section, we investigate the non-convex case. We exploit on-average stability to obtain a data-dependent quantity in the bound. Note that it is also argued in Kuzborskij & Lampert (2018) that the worst case analysis of uniform stability might not be appropriate for deep learning.

heading: 5 NON-CONVEX CASE
text: We consider homogeneous neural networks in the setup of multiclass classification. Write f(x) = Wl(σ(· · ·W2(σ(W1x)))), where x is an input to the neural network, Wi denotes the weight matrix at layer i and σ denotes a homogeneous non-linearity (σ(cx) = ckσ(x) 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 l(s, y) that receives a score vector s = f(x) and a label y as inputs. We require the loss function to be L-Lipschitz for all y as a function of s. That is, for all s, s′, y,
|l(s, y)− l(s′, y)|≤ L||s− s′||. (9)
For example, we can use 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 l(s, y) with respect to s that we can use L = √ 2. 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 c > 0, there exist constants Bc and Lc such that for any x, y ∈ Rd with ||x||≤ c and ||y||≤ c we have
||σ(x)|| ≤ Bc||x||, (10) ||σ(x)− σ(y)|| ≤ Lc||x− y||. (11)
Note that the non-linearity σ is being applied component-wise when the input is a vector as above. It is easy to verify that, for the ReLU function, we have Bc = 1 and Lc = 1 for all c. Furthermore, for the quadratic function x2, we have Bc = c and Lc = 2c. The following lemma will be the starting point for our analysis.
Lemma 1 Assume that ||x||≤ R. Let α1, · · ·αl be positive real numbers and, for 1 ≤ j ≤ l, denote W̃j :=
Wj ||Wj || and W̃ ′ j := W ′j ||W ′j || . Write sj = αjW̃j(σ(· · ·α2W̃2(σ(α1W̃1x)))) and
s′j = αjW̃ ′ j(σ(· · ·α2W̃ ′2(σ(α1W̃ ′1x)))). Also, let cj be an upper bound on the norm of layer j (this will be a constant depending on α1, · · ·αj and R). Then, we have
(12)||sl − s′l||≤ R ( l∏ j=1 αj ) l∑ i=1 τi||W̃i − W̃ ′i ||,
where τi = l∏
j=1,j 6=i
( Bcj if j < i Lcj−1 if j > i ) .
The previous lemma motivates a measure of “distance” between neural networks.
Definition 5 For neural networks f and g, where the weight matrices of f are given by W1 · · ·Wl and the weight matrices of g are given by W ′1 · · ·W ′l , define
d(f, g) := l∑ i=1 τi|| Wi ||Wi|| − W ′ i ||W ′i || ||. (13)
Note that this distance function is invariant to rescaling the weights of any layer. This is a desirable property since in a homogeneous network such a reparametrization leaves the class predicted by the classifier unchanged for any input to the network.
Let α1, · · ·αl be positive real numbers. We define the lα1,···αl(f, z) losses to be equal to
(14)l(αl Wl ||Wl|| (σ(· · ·α2 W2 ||W2|| (σ(α1 W1 ||W1|| x)))), y),
where z = (x, y) and f is the neural network with weight matrix at layer i given by Wi. That is, we project the weight matrices to give the norm αi to layer i and then we evaluate the loss l on this “normalized” network. For simplicity, we will only consider the case where all the αi’s are equal to say α and we will write lα(f, z). From our definitions and lemma 1, we have that for all z and neural networks f and g, |lα(f, z)− lα(g, z)|≤ LRαld(f, g). (15) In order to bound stability with respect to lα, 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 xk for k ≥ 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 ∇(j)l(W, z). We define {βj}lj=1-layerwise smoothness as the following property: For all j, z, W = (W1, · · · ,Wl) and W ′ = (W ′1, · · · ,W ′l ),
||∇(j)l(W, z)−∇(j)l(W ′, z)||≤ βj ||Wj −W ′j ||. (16)
We also let β := max{βj}. Note that β is upper bounding the spectral norm of the bloc diagonal approximation of the Hessian.
We are now ready to state the main theorem of this section for the smooth case.
Theorem 4 Suppose that the loss function l(s, y) is L-Lipschitz for all y, non-negative and that lα(f, z) is bounded above by Mα. Furthermore, assume {βj}lj=1-layerwise smoothness and that ||x||≤ R. Finally, let B denote the batch size, λt ≤ ct the learning rates and T the number of iterations SGD is being run. Then,
(17) αav ≤ inf t0∈{1,2,..., nB }
[ 2BLRαl
(n−B)β ( T − 1 t0 − 1 )cβ T−1∑ t=t0 ζt +Mα Bt0 n ] ,
where β = max{βj} and ζt := ∑l j=1 τjEA,S,z [ Cj(S, z) T−t ||∇ (j)LBt (Wt)|| K
(j) t (S,z)
] ,
with K(j)t (S, z) := min{||Wj,t||, ||W ′j,t||} and Cj(S, z) := max t0≤t≤T−1
K (j) t (S, z) K (j) t+1(S, z) .
To evaluate the bound, we need to find the best t0. There is a tradeoff here between two quantities. A small t0 is better for the term Mα Bt0n but is worse for the remaining term. This establishes the best “burn in” period. The amount of “exploration” before t0 does not effect the generalization bound. The amount of exploration measured by ζt (and through the learning rate via the value of c) becomes important only after iteration t0. The bound will be better if we can reach a 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(j)t (S, z)). When we 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 1). 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 Euclidean 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 ζt also involves the terms Cj(S, z) measuring how fast the norm of the parameters is growing from one iteration to the next. The value of Cj(S, z) is better (smaller) if the norm of the parameters grows faster.
The non-smooth case is also of great interest since the ReLU activation function is very common in practice.
Theorem 5 Suppose that the loss function l(s, y) is L-Lipschitz for all y, non-negative and that lα(f, z) is bounded above by Mα. Furthermore, assume ||x||≤ R. Finally, let B denote the batch size, λt the learning rates and T the number of iterations SGD is being run. Then,
(18) αav ≤ inf t0∈{1,2,..., nB }
[ 2LRαl T−1∑ t=t0 λtζt +Mα Bt0 n ] ,
where ζt is defined as in theorem 4.
Exploiting theorem 12 in Elisseeff et al. (2005), it is then possible to get a 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 n > 1 and δ ∈ (0, 1), the following hold with probability greater or equal to 1− δ over draws of training sets S and the randomness of the algorithm A:
L0−1D (A(S)) ≤ L α S(A(S)) +
√( 1
δ
) 2M2α + 12nMα α av
n . (19)

heading: 6 EXPERIMENTS
text: 6.1 LEARNING RATES AND ζt
In this section we conduct some experiments on the datasets CIFAR10 Krizhevsky (2009) and MNIST LeCun & Cortes (2010). 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 ζt can be of interest to assess generalization in this case.
We use a global learning rate being decayed one time by a 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 as we want during the inital burn-in period (before t0) 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 a small burn-in period is long enough to be significant in current practice. We still think that the quantity ζt is relevant to investigate empirically. We approximate its value on a training set S with the quantity ζ̂t(S) := ∑l j=1 ||∇jLBt (Wt)|| ||Wj,t|| . The quantities Cj(S, z) can be evaluated empirically to be very close
to 1 and so we neglect them in the expression for ζ̂t(S). Also note that τj = 1 for all j in the case of ReLU networks. Instead of plotting the value for each iteration, we average ζ̂t(S) for each epoch. This leads to smoother curves.
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 on CIFAR10. We use also the cross-entropy loss on MNIST but the neural network is a 6-layers fully connected network. In both cases, we 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 a test accuracy of 86.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 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% (lr = 0.05) of test accuracy and for batch size 2048, we get 97.52% (lr = 0.05), 98.00% (lr = 0.1) and 98.39% (lr = 0.5). We plotted the values of ζ̂t(S) during training in Figure 2. 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 ζt would be replaced with a global Lipschitz constant which would not be affected by the actual trajectory of the algorithm. Therefore, in comparison to 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 ζt 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 3). 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 gradients and the norm of the parameters. A standard analysis of stability (without the normalized loss) similar to Kuzborskij & Lampert (2018) would not benefit from the norm of the parameters.

heading: 6.2 GENERALIZATION BOUND AND TEST ERROR
text: We show in this section the usefulness of considering the normalized loss for bounding the test error. We evaluate the bound in theorem 6 and compare it to an 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 av is upper bounded by 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 αav by LRα
lEd(f, g) (see equation 15). We plot the test error, the upper bound for the normalized case with α = 1.0 and the upper bound for the unnormalized case in Figure 4. Further experiments (with label noise and a comparison of Adam and SGD) are given in Appendix C.

heading: 7 CONCLUSION
text: We investigated the stability (uniform and on-average) of SGD with respect to the normalized loss functions. This leads naturally to consider a 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 our analysis will be a helpful step in understanding generalization in deep learning. Future work could investigate the on-average stability with respect to lα losses for different optimization algorithms.

heading: A APPENDIX: PROOFS FOR THE CONVEX CASE
text: 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 if we are interested in the 0− 1 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 are still considering SGD executed on the original loss l (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
euclidean distances (see Figure 1). The proofs in Hardt et al. (2016) consist in bounding E||wt−w′t||, where wt represents the weights at iteration t when training on S and w′t represents the weights at iteration t when training on the modified training set S(i). We will instead bound E|| wt||wt|| − w′t ||w′t|| || (or E[d(f, g)] for an appropriate measure of “distance” d between neural networks f and g).
Lemma 2 Let v, w ∈ Rn and 0 < c ≤ min{||v||, ||w||}. Then,
|| v||v|| − w ||w|| ||≤ ||v−w|| c .
Proof: The proof follows from basic linear algebra manipulations. We give it here for completeness since it is important in what follows. We need to show that
〈 v||v|| − w ||w|| , v ||v|| − w ||w|| 〉 ≤ 〈v−w,v−w〉 c2 .
After some manipulations, one can see that this is equivalent to show that
||v||2+||w||2−2c2 + 2(c2 − ||v||||w||)〈 v||v|| , w ||w|| 〉 ≥ 0.
From Cauchy-Schwarz inequality, 〈 v||v|| , w ||w|| 〉 ≤ 1. Since c 2 − ||v||||w||≤ 0, the proof will be completed by showing that
||v||2+||w||2−2c2 + 2(c2 − ||v||||w||) ≥ 0.
But this is true since
||v||2+||w||2−2||v||||w||= (||v||−||w||)2.
Lemma 3 Assume that the initial point w0 satisfies ||w0||≥ K and that SGD is run with batch size B and a sequence of learning rates λt on an L−Lipschitz loss function l(w, z) for all z. Then, for all t ≥ 1,
||wt||≥ K − L ∑t−1 i=0 λi.
Proof:
||wt|| = ||wt−1 − λt−1 1
B B∑ j=1 ∇l(wt−1, zj)||
≥ ||wt−1||−λt−1 1 B || B∑ j=1 ∇l(wt−1, zj)||
≥ ||wt−1||−λt−1L ≥ ||wt−2||−λt−2L− λt−1L ≥ · · ·
≥ ||w0||−L t−1∑ i=0 λi
≥ K − L t−1∑ i=0 λi.
For ease of comparison, we give the statement of Theorem 3.8 in Hardt et al. (2016).
Theorem 7 (Theorem 3.8 in Hardt et al. (2016)) Assume that the loss function f(·; z) is β-smooth, convex and L−Lipschitz for every z. Suppose that we run SGD with step sizes αt ≤ 2/β for T steps. Then, SGD satisfies uniform stability with
uni ≤ 2L2
n T∑ t=1 αt.
We are now ready to prove Theorem 1.
Proof of Theorem 1: The proof is similar to Hardt et al. (2016). Let wt denotes the output of A after t steps on training set S and w′t be the output of A after t steps on training set S
(i) for some i ∈ {1, · · ·n}. From convexity, the update rule is 1−expansive (see lemma 3.7 from Hardt et al. (2016)). This property can be used when the example i is not being picked at some iteration. Otherwise, the triangular inequality is used. Since the probability of picking the example i in a mini-batch of size B is smaller than Bn (sampling with replacement) and exploiting Lemma 2 and Lemma 3, we get
E [ || wt+1 ||wt+1|| − w′t+1 ||w′t+1|| || ] ≤ 1 K̂ E [ ||wt+1 − w′t+1|| ] ≤ 1 K̂ [ B n ( E||wt − w′t||+2Lλt ) + ( 1− B n ) E||wt − w′t||
] = 1
K̂
( E||wt − w′t||+
2BLλt n
) .
Note that this is true since E||wt−w′t||≤ E||wt−w′t||+2Lλt. Solving the recursion for E||wt−w′t||, we have
E||wt − w′t||≤ 2BLn ∑t−1 i=0 λi.
Therefore,
E [ || wt+1||wt+1|| − w′t+1 ||w′t+1|| || ] ≤ 2BL nK̂ ∑t i=0 λi
The result then follows from the inequality
|l(α w||w|| , z)− l(α w′ ||w′|| , z)|≤ Lα|| w ||w|| − w′ ||w′|| ||.
We finally prove Theorem 3.
Proof of Theorem 3: To simplify the text, write (α, δ) := EALαS(A(S)) + αstab + (2n αstab + Mα) √ ln(1/δ) 2n . For i ≥ 1, let αi = 2 (1−i)C and δi = δ2i2 . For any fixed i, we have
PS{EAL0−1D (A(S)) > (αi, δi)} < δi.
Therefore,
PS{∀i, EAL0−1D (A(S)) ≤ (αi, δi)} = 1− PS{∃i, EAL0−1D (A(S)) > (αi, δi)}
≥ 1− ∞∑ i=1 PS{EAL0−1D (A(S)) > (αi, δi)}
≥ 1− ∞∑ i=1 δi ≥ 1− δ.
The last inequality follows from
∞∑ i=1 δi = δ 2 ∞∑ i=1 1 i2 = δ 2 π2 6 ≤ δ.
We want to show that the set
{S : ∀i, EAL0−1D (A(S)) ≤ (αi, δi)}
is contained in the set
{S : ∀α ∈ (0, C], EAL0−1D (A(S)) ≤ EA max (Lα/2S (A(S)), LαS(A(S))) + αstab + (2n αstab +Mα) √ 2 ln( √ 2(2+log2 C−log2 α))+ln(1/δ) 2n }.
Let S be such that ∀i, EAL0−1D (A(S)) ≤ (αi, δi). Let α ∈ (0, C]. Then, there exists i such that αi ≤ α ≤ 2αi. We have
EAL0−1D (A(S)) ≤ EAL αi S (A(S)) + αi stab + (2n αi stab +Mαi)
√ ln(1/δi)
2n
≤ EALαiS (A(S)) + α stab + (2n α stab +Mα)
√ ln(1/δi)
2n ≤ EALαiS (A(S)) + α stab + (2n
α stab +Mα)√
2 ln( √
2(2 + log2 C − log2 α)) + ln(1/δ) 2n
The second inequality is true since both αstab and Mα are non-decreasing functions of α and αi ≤ α. The last inequality is true since 1δi = 2i2 δ ≤ 2(2+log2 C−log2 α) 2
δ . Finally, the proof is concluded by using the convexity of LαS(A(S)) with respect to α. Indeed, since α 2 ≤ αi ≤ α, we must have
LαiS (A(S)) ≤ max (L α/2 S (A(S)), L α S(A(S))).

heading: B APPENDIX: PROOFS FOR THE NON-CONVEX CASE
text: Proof of Lemma 1: The proof is done by induction on the number of layers l. Suppose the result is true for l − 1 layers. Then we have,
||sl − s′l||= αl||W̃lσ(sl−1)− W̃ ′lσ(s′l−1)|| = αl||W̃lσ(sl−1)− W̃ ′lσ(sl−1)− W̃ ′l (σ(s′l−1)− σ(sl−1))|| ≤ αl||W̃lσ(sl−1)− W̃ ′lσ(sl−1)||+αl||W̃ ′l (σ(s′l−1)− σ(sl−1))|| ≤ αl||W̃l − W̃ ′l || ||σ(sl−1)||+αl||W̃ ′l || ||σ(s′l−1)− σ(sl−1)|| ≤ αl||W̃l − W̃ ′l || ||sl−1||Bcl−1 + αlLcl−1 ||s′l−1 − sl−1||
≤ Rαl||W̃l − W̃ ′l || l−1∏ j=1 Bcjαj + αl Lcl−1 ||s′l−1 − sl−1||
≤R l∏
j=1 αj ||W̃l−W̃ ′l || l−1∏ j=1 Bcj +αlLcl−1 R l−1∏ j=1 αj l−1∑ i=1 [ ||W̃i−W̃ ′i || l−1∏ j=1,j 6=i ( Bcj if j < i Lcj−1 if j > i )]
= R l∏ j=1 αj l∑ i=1 [ ||W̃i − W̃ ′i || l∏ j=1,j 6=i ( Bcj if j < i Lcj−1 if j > i )] .
The proof is finally concluded by observing that for one layer we have, ||s′1− s1||≤ Rα1||W̃1−W̃ ′1||.
Definition 7 Let us introduce some notations. Let δ(j)t (S, z) := ||Wj,t −W ′j,t|| and ∆ (j) t (S, z) := EA[δ(j)t (S, z) | ∀k, δ (k) t0 (S, z) = 0]. Here, Wj,t is obtained when training with S for t iterations and W ′j,t is obtained when training with S (i) for t iterations. The condition inside the expectation is that after t0 iterations, the two networks are still exactly the same. Since we are interested in
distances after normalization, we consider δ̃(j)t (S, z) := || Wj,t ||Wj,t|| − W ′j,t ||W ′j,t|| || and ∆̃(j)t (S, z) :=
EA[δ̃(j)t (S, z) | ∀k, δ (k) t0 (S, z) = 0]. We will further need δ̂ (j) t (S, z) :=
δ (j) t (S,z) K (j) t (S,z) and ∆̂(j)t (S, z) :=
EA[Cj(S, z)T−tδ̂(j)t (S, z) | ∀k, δ (k) t0 (S, z) = 0], where K (j) t (S, z) := min{||Wj,t||, ||W ′j,t||} and
Cj(S, z) := max t0≤t≤T−1
K (j) t (S, z) K (j) t+1(S, z) .
Before proving Theorem 4, we establish a lemma. Note 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).
Lemma 4 Suppose that the loss function l(s, y) is L-Lipschitz for all y, non-negative and that lα(f, z) is bounded above by Mα. Also, assume that ||x||≤ R. Furthermore, let B denote the batch size and T the number of iterations SGD is being run. Then, for any t0 ∈ {0, 1, 2, . . . , nB }, the on-average stability satisfies
αav ≤ LRαl l∑
j=1
τjES,z [ EA[δ̃(j)T (S, z) | ∀k, δ (k) t0 (S, z) = 0] ] +Mα( Bt0 n ).
Proof: Write the quantity |lα(f, z)− lα(g, z)| as the sum of |lα(f, z)− lα(g, z)|I{∀k, δ(k)t0 (S, z) = 0} and |lα(f, z)− lα(g, z)|I{∃k : δ(k)t0 (S, z) 6= 0}. We bound the first term by using the fact that
|lα(f, z)− lα(g, z)|≤ LRαld(f, g) = LRαl l∑
j=1
τj δ̃ (j) T (S, z).
For the second term, we use that lα(f, z) is bounded above by Mα and non-negative to write
|lα(f, z)− lα(g, z)|≤Mα.
The result then follows from the fact that the probability of picking example i in t0 iterations is smaller than Bt0n .
Proof of theorem 4: From Lemma 2, we always have δ̃(j)t (S, z) ≤ δ̂ (j) t (S, z). Therefore, from the previous Lemma,
αav ≤ LRαl l∑
j=1
τjES,z [ ∆̂ (j) T (S, z) ] +Mα(
Bt0 n ).
First note that under our definitions,
δ̂ (j) t+1(S, z) =
δ (j) t+1(S, z)
K (j) t+1(S, z)
≤ Cj(S, z) δ (j) t+1(S, z)
K (j) t (S, z)
≤ Cj(S, z) K
(j) t (S, z)
[ δ (j) t (S, z) + λt||∇(j)LBt(Wt)−∇(j)LB′t(W ′ t )|| ]
= Cj(S, z) δ̂ (j) t (S, z) + λtCj(S, z)
||∇(j)LBt(Wt)−∇(j)LB′t(W ′ t )||
K (j) t (S, z)
.
Therefore,
Cj(S, z) T−(t+1) δ̂ (j) t+1(S, z) ≤ Cj(S, z)T−t δ̂ (j) t (S, z)
+ λtCj(S, z) T−t ||∇ (j)LBt(Wt)−∇(j)LB′t(W ′ t )||
K (j) t (S, z)
.
Here, Bt denotes the batch of samples at iteration t when training on S and B′t denotes the batch of samples at iteration t when training on S(i). When Bt = B′t, we will use {βj}lj=1-layerwise smoothness to bound ||∇(j)LBt(Wt) − ∇(j)LB′t(W ′ t )||. Otherwise, we use simply the triangular inequality. Let p(B,n) be the probability of picking the example i in a mini-batch of size B (this is smaller than Bn ). For t ≥ t0, we have
∆̂ (j) t+1(S, z) ≤ (1− p(B,n))(1 + βjλt)∆̂ (j) t (S, z) + p(B,n)
( ∆̂
(j) t (S, z) +
λtEA[Cj(S, z)T−t ||∇(j)LBt(Wt)|| K
(j) t (S, z)
+ Cj(S, z) T−t ||∇ (j)LB′t(W ′ t )||
K (j) t (S, z)
] ) .
Define ∆̂(j)t := ES,z∆̂ (j) t (S, z) and ζ (j) t := EA,S,zCj(S, z)T−t ||∇(j)LBt (Wt)|| K
(j) t (S,z)
for any t. Taking the expectation over S and z on both
sides of the previous inequality, we get
∆̂ (j) t+1 ≤ (1− p(B,n))(1 + βjλt)∆̂ (j) t + p(B,n)(∆̂ (j) t + 2λtζ (j) t ).
This is true since EA,S,zCj(S, z)T−t ||∇(j)LBt (Wt)||
K (j) t (S,z)
= EA,S,zCj(S, z)T−t ||∇(j)LB′t (W ′ t )||
K (j) t (S,z)
. Rearranging terms and
using 1 + x ≤ exp(x), we get
∆̂ (j) t+1 ≤ [1 + (1− p(B,n))βjλt]∆̂ (j) t + 2p(B,n)λtζ (j) t
≤ exp((1− p(B,n))βjλt)∆̂(j)t + 2p(B,n)λtζ (j) t .
Developing the recursion yields
∆̂ (j) T ≤ T−1∑ t=t0 2p(B,n)λtζ (j) t T−1∏ k=t+1 exp ( (1− p(B,n))cβj k )
≤ 2B n T−1∑ t=t0 λtζ (j) t exp ( (1− p(B,n))cβj T−1∑ k=t+1 1 k )
≤ 2B n T−1∑ t=t0 λtζ (j) t exp ( (1− p(B,n))cβj log( T − 1 t ) )
≤ 2Bc n T−1∑ t=t0 ζ (j) t t ( T − 1 t )(1−p(B,n))cβj ≤ 2Bc
n T−1∑ t=t0 ζ (j) t t ( T − 1 t )(1−p(B,n))cβ
≤ 2Bc n max t0≤t≤T−1 {ζ(j)t }(T − 1)(1−p(B,n))cβ T−1∑ t=t0 ( 1 t )(1−p(B,n))cβ−1 ≤ 2Bc nc(1− p(B,n))β max t0≤t≤T−1 {ζ(j)t } ( T − 1 t0 − 1
)(1−p(B,n))cβ ≤ 2B
(n−B)β ( T − 1 t0 − 1 )cβ max t0≤t≤T−1 {ζ(j)t }.
Therefore, αav is upper bounded by
inf t0∈{1,2,..., nB }
[ 2BLRαl
(n−B)β ( T − 1 t0 − 1 )cβ l∑ j=1 τj max t0≤t≤T−1 {ζ(j)t }+Mα( Bt0 n ) ] .
To complete the proof, we will use that maxt0≤t≤T−1{ζ (j) t } ≤ ∑T−1 t=t0 ζ (j) t and reverse the sum order.
With the definition ζt := ∑l j=1 τjζ (j) t , we then have
αav ≤ inf t0∈{1,2,..., nB }
[ 2BLRαl
(n−B)β ( T − 1 t0 − 1 )cβ T−1∑ t=t0 ζt +Mα( Bt0 n ) ] .
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), it is not possible to exploit the property of layer-wise smoothness. Instead, only the triangular inequality is used to bound ||∇(j)LBt(Wt)−∇(j)LB′t(W ′ t )||. This leads to the inequality
∆̂ (j) t+1 ≤ ∆̂ (j) t + 2λtζ (j) t .
Solving the recursion then yields
∆̂ (j) T ≤ 2 ∑T−1 t=t0 λtζ (j) t .
As a consequence,
αav ≤ inf t0∈{1,2,..., nB }
[ 2LRαl T−1∑ t=t0 λtζt +Mα Bt0 n ] ,
where ζt = ∑l j=1 τjζ (j) t , concluding the proof.

heading: C APPENDIX: MORE EXPERIMENTS

Review summaries:
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.

This 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.  

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.   

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.  Their 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.