Revisiting the Stability of Stochastic Gradient Descent: A Tightness Analysis
Authors: Yikai Zhang
Samuel Bald
wenjia Zhang
Vamsi Pritham Pingali
Chao Chen
Mayank Goswami
Venue:  (2021)
Keywords: SGD
Stability
Generalization
Deep Learning

Abstract: The technique of algorithmic stability has been used to capture the generalization power of several learning models, especially those trained with stochastic gradient descent (SGD). This paper investigates the tightness of the algorithmic stability bounds for SGD given by~\cite{hardt2016train}. We show that the analysis of~\cite{hardt2016train} is tight for convex objective functions, but loose for non-convex objective functions. In the non-convex case we provide a tighter upper bound on the stability (and hence generalization error), and provide evidence that it is asymptotically tight up to a constant factor. 
However, deep neural networks trained with SGD exhibit much better stability and generalization in practice than what is suggested by these (tight) bounds,
namely, linear or exponential degradation with time for SGD with constant step size. We aim towards characterizing deep learning loss functions with good generalization guarantees, despite being trained using SGD with constant step size.
 We propose the Hessian Contractive (HC) condition, which specifies the contractivity of regions containing local minima in the neural network loss landscape. We provide empirical evidence that this condition holds for several loss functions, and provide theoretical evidence that the known tight SGD stability bounds for convex and non-convex loss functions can be circumvented by HC loss functions, thus partially explaining the generalization of deep neural networks. 

Under review as a conference paper at ICLR 2020
REVISITING THE STABILITY OF STOCHASTIC GRADI- ENT DESCENT: A TIGHTNESS ANALYSIS
Anonymous authors
Paper under double-blind review
ABSTRACT
The technique of algorithmic stability has been used capture the generalization power of several learning models, especially those trained with stochastic gradient descent (SGD). This paper investigates the tightness of the algorithmic stability bounds for SGD given by Hardt et al. (2016). We show that the analysis of Hardt et al. ( is tight for convex objective funetions, but loose for non-convex objective functions. In the non-convex case we provide tighter upper bound on the stability (and hence generalization error), and provide evidence that it is asymptotically tight up to constant factor.
However, deep neural networks trained with SGD exhibit much better stability and generalization in practice than what is suggested by these (tight) bounds, namely, linear or exponential degradation with time for SGD with constant step size. We aim towards characterizing deep learning loss functions with good generalization guarantees, despite training using SGD with constant step size.
In this vein, we propose the notion of Hessian Contractive (HC) region, which quantifies the contractivity of regions containing local minima the neural network loss landscape. We provide empirical evidence that several loss functions exhibit HC characteristics, and provide theoretical evidence that the known tight SGD stability bounds for convex and non-convex loss functions can be circumvented by HC loss functions, thus partially explaining the generalization deep neural networks.
INTRODUCTION
Stochastic gradient descent (SGD) has gained great popularity in solving machine learning optimiza- tion problems (Kingma & Ba 2014 Johnson & Zhang 2013). SGD leverages the finite-sum structure of the objective function, avoids the expensive computation of exact gradients, and thus provides a
feasible and efficient optimization solution in large-scale settings (Bottou, 2012). The convergence and the optimality SGD have been thoroughly studied
(Ge et al. 2015 Rakhlin et al. 2012 Reddi let al. 2018 Zhou & Gu 2019 Carmon al. 2019a b Shamir & Zhang 2013).
In recent years, new research questions have been raised regarding SGD's impact on a model's generalization power. The seminal work (Hardt et al.) (016)) tackled the problem using the afgorithmic stability of SGD, i.e., the progressive sensitivity of the trained model w.r.t. the replacement of single (test) datum in the training set. The stability-based analysis of the generalization gap allows one to bypass classical model capacity theorems (Vapnik) 1998] Koltchinkki & Panchenko, (0000) or weight-based complexity theorems (Neyshabur et al. 2017] Bartlett al.) 2017]] |rora et al.) 2018). This framework also provides theoretical insights into many phenomena observed in practice, e.g., the "train faster, generalize better" phenomenon, the power of regularization techniques such as weight decay (Krogh & Hertz 1992), Dropout (Srivastava et al. 2014). and gradient clipping. Other works have applied the stability analysis to more sophisticated settings such as Stochastic Gradient Langevin Dynamics and momentum SGD (Mou al. 2018 Chaudhari et al. 2019 Chen et al. 2018).
Despite the promises of this stability-based analysis, it remains open whether this framework can explain the strong generalization performance of deep neural networks in practice. Existing theoretical upper bounds of the stability (and thus, generalization) (Hardt et al.) 2016) are ideal for strongly convex loss functions: the upper bound remains constant as the number of training iterations increases. However, the same bound deteriorates significantly when we relax to more general and realistic settings. In particular, for convex (but not strongly convex) and non-convex loss functions, if

---

Under review as a conference paper at ICLR 2020
SGD has constant step size, then the upper bound grows linearly and exponentially with the number of training iterations. This bound fails to match the superior generalization performance of deep neural networks, and leads to the following question:
Question I: Can we find a better stability upper bound for convex or non-convex loss functions?
In this paper, we first address the question above and investigate the tightness of the algorithmic stability analysis for stochastic gradient methods (SGM) proposed by (Hardt et al.) 2016).
R1. We show in Theorem I that the analysis in (Hardt et al., 2016) is tight for convex and smooth objective functions; other words, there convex loss function whose stability grows linearly with the number of training iterations, with constant step size (0:² a) in SGD.
R2. We show that in Theorem 2 that for linear models, the analysis in the convex case can be tightened to show that Estah does not increase with 6.
R3. In Theorem 3 we show that the analysis in (Hardt et al., 2016) for decreasing step size (ar = O(1(() is loose for non-convex objective functions by providing tighter upper bound on the stability (and hence generalization error).
R4. The bound on the stability of SGD by (Hardt et al. 2016) is achieved by bounding the divergence at time t, defined as 6, Bl will. where wy is the model trained on data set S and wi, is the model trained on a data set S' that differs from S in exactly one sample. In Theorem evidence that our new upper bound in the non-convex case is tight, by showing non-convex loss function whose divergence matches the upper bound for our divergence.
4 we provide
R5. Although it is not derived formally, the techniques in (Hardt et al. 2016) can be employed to show an exponential upper bound for non-convex loss functions minimized using SGD with constant-size step. In Theorem 5 we give evidence that this abysmal upper bound is likely tight for non-convex loss functions, by exhibiting a non-convex loss function for which the divergence ó, increases exponentially.
Thus the only functions whose stability provably does not increase with the number of iterations when a constant step-size during SGD employed, are strongly convex functions. However, a) has been empirically observed that for deep neural network loss, near the local minima, the Hessians are usually low rank (Chaudhari et al.] 2017 Yao et al.] 2019), and b) neural networks trained with constant step-size SGD do generalize well in practice (Lin & Jegelka 201 8 Huang et al.] 2017]] Smith et al. 2017). Combined with our lower bounds on convex and non-convex functions, we seem to hit an obstacle on the way to explaining generalization using the stability framework.
Question 2: What is it that makes constant-step SGD on deep learning loss function generalize well?
Realizing the limitation of the current state of stability analysis, we investigate whether a stronger- than-convex, but near local minima. If we can show algorithmic stability near local minima, we can still show the stability using similar argument (Du al. 2019 Allen-Zhu et al. 2019).
assumption of the loss function can be made, at least
Aiming towards a characterization of loss functions exhibiting good stability, we propose a new condition for loss near local minima. This condition, called Hessian contractive, slightly stronger than a general convex condition, but considerably weaker than strongly convex. Formally, the Hessian contractive condition stipulates that near any local minima, (1) the function is convex; and (2) data dependent Hessian is positive definite in the gradient direction. Theoretically, we show that such a condition is sufficient to guarantee a constant stability bound for SGD (constant step size) near the local minima, while allowing the Hessian to be low rank. We also provide examples showing Hessian Contractive a reasonable condition for several loss functions. Empirically, we verify the Hessian Contractive condition near local minima of the loss while training deep neural networks. We sample points from a neighborhood of current iterates by adding Gaussian noise and verify the HC condition locally by Hessian product approximation. Summarizing
second set of contributions:
R6. In Observation we show that the family of widely used (convex) linear model loss functions will satisfy the Hessian Contractive condition. One typical example of such linear model loss is the regression loss function. These observation suggests that Hessian Contractive is a condition satisfied by (potentially many) machine learning loss functions.
2

---

Under review as a conference paper at ICLR 2020
R7. In Theorem 6 we show that the Hessian Contractive condition will localize SGD iterates in neighborhood of minima, which implies a constant stability bound for SGD near the local minima.
Table 1: Current landscape of stability bounds. [H] indicates results in (Hardt et al., 2016), and * indicates results in this paper. Bounds without [H] or are trivial. / is the smoothness parameter.
SGD Step Size
Constant a2 = a/3
a2 = a/(3t
Constant Oz
Loss function
Strongly Con-
Convex
Non-Convex
Hessian Contrac- tive
vex
Upper Bound
O(1) [H]
O(aT/n) [H]
0 (T /n) [H]
Theorem 6
o (T (Tm/nIta)e
Lower Bound
111)
((TT/n)*
Open, evidence*
2(1)
1.1 RELATED WORKS
Stability and generalization. The stability framework suggests that stable machine learning al- gorithm results in models with good gencralization performance (Kearns & Ron 1999. Bousquet & Elisseeff 2002 Hlisseeff et al. 2005 Shalev-Shwartz al.,
& Wagner 1979a bj
Rogers & Wagner 1978). It serves as a mechanism for provable learnability when uniform conver- gence fails
al.; 2010 Nagarajan & Kolter 2019). The concept of uniform stability was introduced in order to derive high probability bounds on the generalization error (Bousquet & Elisseeff 2002). Uniform stability describes the worst case change in the loss of a model trained on an algorithm when single data point in the dataset is replaced. In (Hardt et al., (016), a uniform stability analysis for iterative algorithms is proposed to analyze SGD, generalizing the one-shot version in (Bousquet& & Elisseeff] 2002). Algorithmic uniform stability is widely used in analyzing the generalization performance of SGD (Mou al., 2018 |Feldman & Vondrak (2099] [hen et al. 2018). The worst case leave-onc-out type bounds also closely connect uniform stability with differential private learning (Feldman et al.) 2018|2020 Dwork et al., [2006] |uu et al. 2017b), where the uniform stability can lead to provable privacy guarantee. While the upper bounds of algorithmic stability of SGD have been extensively studied, the tightness of those bounds remains open. In addition to uniform stability, an average stability of the SGD is studied in Kuzborskij & Lampert (2018) where the authors provide data-dependenl upper bounds on stability In this work, we report for the first time lower bounds the uniform stability of SGD. Our tightness analysis suggests necessity of additional assumptions for analyzing the generalization of SGD on deep learning.
Geometry of local minima. The geometry of local minima plays an important role in the generaliza- tion performance of deep neural networks (Hochreiter & Schmidhuber 1995 Wu et al. 2017a). The flat minima, i.e., minima whose Hessians have a large portion of zero-valued eigenvalues, are believed to attain better generalization (Keskar et al. 20166 Li et al. 2018). In (Chaudhari et al. 2019), the authors construct a local entropy- based objective function which converges to solution with good generalization in flat region, where "flatness" means that the Hessian matrix has a large portion of nearly-zero eigenvalues. However, these observations have not been supported theoretically. paper, propose the Hessian contractive condition that is slight stronger than flat minima. Such condition suggests that the minima is sharp only in the gradient direction while remains flat in other directions, which unifies the geometrical interpretation of flat minima and uniform stability analysis.
this
PRELIMINARIES
In this section we introduce the notion of uniform stability and establish our notations. We first introduce the quantities Empirical and Population Risk and Generalization Gap. Given an unknown distribution D on labeled sample space Z = X x 1,1, +1}, let S = { ... 2n denote set of n samples 2; = (x; ys) drawn i.i.d. from D. Let w E IRd be the parameter(s) of a model that tries to predict y given x, and let f be loss function where f(w; 2) denotes the loss of the model with parameter w on sample 2. Let fw: S) denote the empirical risk fww; S) = E [f 2)] =
While it is an interesting open problem to get data- deteedeenndnn lower bounds by lower bounding the average stability, we construct lower bounds on the worst-case stability. Thus our lower bounds are general and not data-dependent.
3

---

Under review as a conference paper at ICLR 2020
Ei= f(w; 2,) with corresponding population risk Ex~ The generalization ervor of the model with parameter w defined as the difference between the empirical and population risks:
[E= z)] [==s(f(w;=)]]
Next we introduce the Stochastic Gradient Descent (SGD) method. We follow the setting of (Hardi ct al. 2016), and starting with some initialization wig Rdd, consider the following SGD update step:
W++1 =
at V f(;; 2.,),
where in is drawn from [n] == (1,2.... n uniformly and independently in each round. The analysis of SGD requires the following crucial properties the loss functiion f(.,, 2) at any fixed point 2. viewed solely a function of the parameter
Definition (Z--Lisccitz), A function f (ww is L-Lippshitz Vu, u Rd: [f(u) f(w) = L|Iu el| Definition (B-smooth). function (w) is B-smooth if, Rd: /V((u) Vf(() S B el].
Definition (7-strongly convex). A functio fw) is 7 strongly convex if Vu, v Rd:
f(u) > f(v) + Vf(() - 2) 2 2112.
Algorithmic Stability Next we define the key concept of algorithmic stability, which was intro- duced by (Bousquet & Elisseeff 2002) and adopted by (Hardt et al., 2016). Informally, an algorithm is stable if its output only varies slightly when we change single sample in the input dataset. When this stability is uniform over all datasets differing at a single point, this leads to an upper bound on the generalization gap. More formally:
Definition 4. Two sets of samples S,S' twin datasets if they differ a single entry, i.e., S {#1, .... Zn) and S' {21..... 24p...,,x.)
Consider a possibly randomized algorithm A that given a sample S of size n outputs a parameter A(S). Define the algorithmic stability parameter of A by:
Stab (A, n) = inf(s: sup *EZ.S,S'
- [
Here EA denote expectation the random coins of A. Also, for such algorithm, define its expected generalization eтror as:
GF(A, == (s- =)] Ez =)]]-
Stability and generalization: It was proved in (Hardt al. 2016) that GE(A, n) S Eaab Eaab(A, n). Furthermore, the authors observed that an I--Lipschitz condition on the loss function f enforces a uniform upper bound: sup, |f (w; 2) f(w;; = I T.Ilw w'll This implies that for Lipschitz loss, the algorithmic stability Sstab (A, n) (and hence the generalization error (A,A,n n)) can be bounded by obtaining bounds on w w'll w'll.
Let wr and wi be the parameters obtained by running SGD starting on twin datasets S and S" respectively. Throughout this paper we will focus on the divergence quantity &y := Eallwy - w While (Hardt et al.) 2016) reports upper bounds on ōr with different types of loss functions, e.g.. convex and non-convex loss functions, we investigate the tightness of those bounds.
TIGHTNESS OF EXISTING BOUNDS
In this section we report our main results. We first consider the convex case with constant step size, where we prove 1) that the existing bounds stating éstab & are tight, and 2) for linear models, the analysis can be tightened to show that Gua does not increase with t. Then we move on to the non-convex case, where a) for decreasing step size improve the existing upper bound, and give evidence that our new upper bound is tight, and b) for constant step size we give loss functions whose divergence 5, increases exponentially with t.
4

---

Under review as a conference paper at ICLR 2020
3.1 CONVEX CASE
In this section we analyze the stability of SGD when loss function is convex and smooth. We begin with construction which shows that Theorem 3.8 in (Hardt et al. 2016 is tight. Our lower bound analysis will require the following quadratic function:
1 w Aw yr JuTT 2
f(w; 2)
where A is a d x d matrix. In the construction of lower bounds, we carefully choose A and S so that the single data point replaced in twin data set will cause the instability of SGD.
Theorem 1. Let wa, wt, be the outputs of SGD twin datasets S,S' respectively. Let A, W/ w/ and og be the step size of SGD. There exists a function f which is convex, B-smooth, and L-Lipschitz on the domain of w, and twin datasets S, S such that:
L
T E
L.
Σ T
E|| B| 2
3n 1= at, and Estab 2 3n -== at.
ااnn which
The convex upper bound in Theorem 3.8 in (Hardt et al. 2016) states that || S. implies that the divergence increases throughout training. The lower bound in Theorem I suggests the tightness of the upper bound. However, in practice, such phenomenon is not commonly observed, i.e., for family of convex but not-strongly-comee cooonnly-coovxx..oo loss functions, the generalization performance does not deteriorate as the number of training iterations increases. This motivates us to investigate a weaker condition which still can enforce an O (1) stability, without strong convexity. In the next theorem, restrict ourselves to a family of linear model loss functions and show that the divergence will not increase unboundedly during training.
We shall need the following definition of É-self correlated data set. Essentially, a self-correlated dataset requires an average linear dependence of each æ. Recall that the i'th sample 2; = (I;, Ui).
Definition 5. A set S {Z1,..., 2n3 is E-self correlated ij E [m]] A -E xz)² 2 E 0.
Assuming that Vj E [n]. ||ا 2 r for some r > 0, definition 5 implies that S is at least n correlated. Thus the above condition holds for all datasets S not containing the zero-fcature vector. In our next theorem, we leverage on the Ç-self correlated condition to prove non-accumulate uniform stability bound for SGD on a loss function of Linear Models. We characterize a linear model by rewriting the loss function f fww; 2) in terms of fy(w "x) where fy(.) is a scalar function depending only on the inner product of the model parameter and the input feature
:" -elf
Theorem 2. Suppose a loss function fww, x) is of the form f(w, S) = 1 Sus (w æz), where fy(w r) satisfies (1) (f,()) T., (2) <<> S ())() 3, (3) ||||| R and (4) S,S' are E-self correlated, twin datasets. Let w, and w/ be the outputs of SGD on S and S' after steps, respectively. ALR Eyn
Let the divergence A w/= w/ and S Y/ be the step size of SGD. Then, E| Arll
Remark 1. In Hardt et al. 2016). an O
L2
stability bound is derived on loss function f(w, 2:)
which is strongly convex, i.e., V (w)( > I. In practice one can incorporate a strongly convex
regularizer to impose strong convexity, often resulting in improved generalization performance in practice (Shalev-Shaa Shalee--Shwatzzeo et al. 2010; Bousquet & Elisseeff 2002). The E-self correlated condition allows SGD to maintain a uniformly upper-bounder divergence guarantee for a family of widely used models for arbitrary long training without using strongly convex regularizer. The theorem suggests that if the dataset S is reasonably simple, e.g., every D; lies in a low dimensional subspace, the divergence of SGD is comparable with strongly convex loss function. This analysis suggests an alternative condition other can sirong convexity can empower SGD an O(1) stability which is data-dependent. This motivales us go beyond linear model and seek for generalized condition in Theorem 2 In section 4.1 we propose the Hessian Contractive condition for more general loss function driven by the observation on the linear model.
Example: Linear and logistic regression. Linear regression minimizes the quadratic loss on wr 1
f(w, S) = 2n En w y²)²² Note that the Hessian of an individual linear regression loss term is ur..r.] which is not strongly convex since it has rank 1. One cannot apply the strongly convex bound,
5

---

Under review as a conference paper at ICLR 2020
and the bound for convex suggests stability will increase linearly. However, can rewrite the loss function as fy x) where (.) = 1. Hence Thm. can be applied to give a non accumulative bound on SGD's stability. A similar result can be derived for the logistic regression loss.
3.2 NON-CONVEX CASE
In this section, construct non-convex loss function to analyze the tightness of the divergence bound (Hardt et al. 2016). We first focus on the case of decreasing step size.
Theorem 3. There exists a function f which non-convex and 3-smooth, twin datasets S, and constants s.t. the following holds: if SGD is using step size 04 0,993t for S tt < T, and
We; w/ are the ouiputs of SGD on and S', respectively, and D. == Wt - wy the divergence of SGD T
after rounds (T n) satisfies: |r] 2
3n
Comparison the bound in Theorem 3.12 (.12(Harde al., 2016) In (Hardt et al., 2016), an assump- tion is made on the non-convex loss function, namely that / [w. 2) < 1. We remark that our function used in proving the lower bound above does not obey this assumption. Thus for very large T, our lower bound may exceed the upper bound in (Hardt et al. 2016), and in general is incomparable due to the lack of this assumption.
Next one observes that in the range T S n, the upper bound in (Hardt et al. 2016), namely O(T /n)+ is larger than 1, weakening its importance, especially because of the assumption f(z, w) < 1, and the fact that when a is small, and one interested in training faster, smaller values 7 in the above range important. Our divergence lower bound motivates an investigation into the possible tightness of the analysis leading to the upper bound (Hardi et al.] 2016). In the following theorem prove righter upper bound for this range of T: it does not assume f(2, w) 1, and is non-trivial in the range when T S
Theorem 4. Assume f is 3-smooth and L-lipschitz. Running T (T n) iterations of SGD fw; S) with step size a₁ = Br. the stability of SGD satisfies: Estab I 2L2T0 nita
Dividing our bound with the one in Theorem 3.12 in Hardt et al. (201)), we obtain the ratio
Ω This factor is less than (and so we improve the upper bound) exactly when Tri= S n.
Note that this is potentially large range as a small and positive constant. We remark that our tight bound is for permutation SGD. The bound for SGD (see Appendix Theorem 4b) using sampling without replacement has an additional log(n) factor (which we conjecture can be removed), which nevertheless is also polynomial improvement over the known bounds.
4 DEEP LEARNING AND LIMITATIONS BOUNDS
While Theorem improves existing upper bounds on stability by an polynomial factor, it still explain the generalization performance of deep learning model. In particular, the analysis relies on a decreasing step size while training deep learning model, constant instead of decreasing step size is a common choice. In the next result, we adopt the same construction as in Theorem 3 but with a constant learning rate to show that, unfortunately, SGD may have an exponential divergence rate for general B smooth function.
Theorem 5. Let Wt, wi be the outputs of SGD on twin datasets S,S' and let D := wi- There exists a function f which is non-convex and 8-smooth, twin sets S, S' and constants a, such that the divergence of SGD after T rounds (T > n) using constant step size = a satisfies: 0.993
A||rr| 2 n.2 T/2
The above theorem implies that the generalization gap may deteriorate at an exponential rate SGD is run with constant step size for non-convex function. However, in Fig. la observe that the distance between the weights of two deep models trained on twin datasets (in other words, the divergence ōy stabilizes after 20 epochs of training. Fig. salgugsssss that the generalization gap for deep models may remain constant after sufficiently many training iterations. However, the analysis of (Hardt al. 2016) suggests that local minima of the loss landscape must be in strongly convex

---

Under review as a conference paper at ICLR 2020
regions in order to achieve this sort of stability. Indeed, strongly convex Hessians have been proven to be contractive, leading to the stability of SGD (Ge et al. 2015). On the other hand, it is known that the Hessians of the loss functions of common deep learning architectures have large fraction of eigenvalues which are close to zero (ao et al. 2019 Chaudhari et al., 2017). This phenomenon requires further investigation to close the gap between theory and practice. Next, we formalize condition requiring that local minima of deep learning loss landscapes lie in contractive regions, which aids in explaining why the generalization gap stabilizes. We then provide empirical evidence that this property does indeed hold.
4.1 GEOMETRY OF LOCAL MINIMA
In Theorems and we show that in general, divergence (and hence stability) may deteriorate at a linear exponential rate with the number of training iterations when the local minima are not in strongly convex regions. We introduce the following property to aid in understanding the stability of the training curve of SGD.
Definition 6. [Hessian Contractive] For a given set S = {zi,...Zn). a local minimum w" is in a (o, HHesssHn contractive region if Vw, w' with max(Ilw - w= ||w w0
and a E S.
V f(w, 2) Hew Vwf(w, 2) 2 f 21) where Hey Vif((u: ブドー f 21). When (o.n)--essiin) contractive holds for all and local minima w", we say f(w; S) is globally --Hessian contractive.
(3)
Hessian contractivity describes a region where the stochastic gradient will lie in the range a positive semi-definite Hessian matrix. Such a condition prevents the iterates of SGD from escaping from local minima in the sense that all gradient descent steps will be pulled back to the minima by the power of Hessian, which mimics the structure of a strongly convex loss function but with weaker assumption. To show that this class is nonempty, we observe the (not strongly convex) linear models loss functions in Theorem satissfy Hessian contractive condition globally.
Observation Suppose loss function J (wu; S) conditions in Theorem 2 i.e. [(w, S) =
Ej= Ju, (w" πz)) satisfies (1) [1,(0) S I,, (2) 7 S ()() S 8, (3) || S R and (4) S is E-self correlated, we have (wr S) is globally &
R² Hessian Contractive.
Dependence on dataset The Hessian Contractive condition states that the gradient of loss function evaluated on 2 can be regulated by Hessian evaluated on the whole dataset, which is a generalization of Ç-self correlated set condition. In the linear model case, the power of Hessian Contractive condition depends on the the average correlation between data points which indicates the effect of data complexity in generalization. We postulate that the value of in Hessian Contractive condition can be one complexity measurement of the data, which is believed to affect generalization power (Kawaguchi et al. 2017).
Next, we leverage on the Hessian contractive condition to show that once SGD hits a stationary point around w" in a (a, Hesssiin contractive region, it will be localized near the minima. The localization of SGD implies that the divergence curve will be stable eventually.
Theorem 6. Given set S and a 3-smooth and L-Liisshitzz loss funtion f, suppose SGD with o²
fixed step size a S Z4Lzz reaches point we which close to local minimum w" in a (a, -Hessiaa
contractive region: ||20- w'll S a with large enough radius so that o > 12L, then we have VT 2 1, ||w-- w'1l S
7
Theorem 6 states that once the iterate w of SGD encounters point in (a, 77.7) ( Heessian contractive region with large enough radius a, w will remain in this region. In terms of the stability of SGD, assuming SGD will bring w. into one of the local minima quickly (Ge al. 2015) Allen-Zhn Zhu et al. 2019), the divergence || - w will be uniformly bounded by the difference between two local minima w", wn of loss functions f(w;; S) and (w'; S') plus the a-radius of the Hessian contractive region. The above suggests that weaker condition than strong convexity is sufficient to explain the observation in Fig. Ta
4.2 EMPIRICAL SUPPORT FOR HESSIAN CONTRACTIVITY
In order to explain the stabilization of the generalization gap observed when training deep learning models via SGD, we hypothesize that local minima of deep loss landscapes found by SGD lie in Hes-
7

---

Under review as a conference paper at ICLR 2020
Natereto dulance
03397
0323
0.397
0.73
(a)
(b)
As in (Hardt et al. 2016). measure the normalized Euclidean distance between the parameters of two identical deep models (ResNer18) trained twin datasets (CTFARIO with random image removed). We plot the mean over twin datasets (variance shown).
Figure 1:
distance first increases stabilizes after 20 train epochs. The "all" curve is the distance between the full model parameter vectors; convi is the distance between first convolutional layer weights in the i-th "block" of ResNet18 [ contractivity. For both neural networks, the "mean" contractivity value each epoch averaged 100 perturbations 5 difffernn copies the network trained CIFARIO. Similarly "mean(min)", except the min of the 100 approximations after perturbing taken. Both quantities for both networks provide evidence that SGD converges to an increasingly contractive solution.
[b] Approximate normalized Hessian
sian contractive regions. We propose to empirically support this hypothesis by locally approximating the LHS of Eq. (6 normmazllee by f =)ll2-uuring the training of model, and showing that this quantity steadily increases training progresses. This indicates that SGD leads the training into regions of increasing contractivity.
now explain our approximation: For a model w*, we generate many random samples w from the unit sphere around w". For each w, we locally estimate a stochastic version of Hessian-gradient product to get the approximation
(w. ((())
V vwf(w- V f 2), =)] VV [ (4) 1)
where the gradients on the RHS approximation are taken with respect to a random minibatch of samples. For each perturbation úi normalize the corresponding approximation by / 2) and then take the mean and minimum over all of these quantities.
For our experiments, used the well-known CIFARIO dataset (Krizhevsky al. 2009) and two popular deep architectures: ResNet18, and DenseNet121 (Huang et al. 2017 Lin & Jegelka 2018). To match the settings in the theorems of this paper as much as possible and avoid any confounding factors, we avoided standard regularization (e.g. weight decay), data augmentation, and adaptive learning rates. We used SGD with a constant learning rate of 0.01 and momentum of 0.9. The models were trained for 200 epochs and batch size of 128. We trained five copies of each network and checkpointed the models every 8 epochs. For each checkpoint, we generated 100 random perturbations from the unit sphere around the checkpoint weights. We used r7 0.001 and batch size 128 for the approximation Eq. 4). We averaged over these 100 approximations and then further took the average the five networks. The results of these experiments shown in Fig. lb and indicate a clear increase in Hessian contractivity as training progresses.
CONCLUSION
In this paper, we studied the stability bound of SGD with regard different types of loss functions. We proved better upper bound and proved the tightness of various bounds. These tightness results suggest that existing stability bounds may not suffice in answering the generalization problem deep neural nets. We propose a new Hessian contractive condition that is slighly stronger than convex, but with (11) stability bound. We provide empirical evidence to support the hypothesis that deep learning loss function is Hessian contractive near local minima.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Zhang, Stronger generalization bounds for deep nets via compression approach. In Proceedings of the 35th International Conference on Machine Learning, ICML, 2018.
Peter L Bartlett, Dylan Foster, and Matus J Telgarsky, Spectrally normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
Léon Bottou. Stochastic gradient descent tricks. In Neural networks: Tricks of the trade, pp- 421-436. Springer, 2012.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of machine learning research, 2(Mar):499-526 2002.
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, pp. 1-50, 2019a.
Yair Carmon, John Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: First-order methods. Mathematical Programming, pp. 1-50, 2019b.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. In ICLR, 2017.
Pratik Chaudhari. Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi. Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124018, 2019.
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv: 2018.
Lue Devroye and Wagner. Distribution- performance bounds with the resubstitution error estimate (corresp.). IEEE Transactions Information Theory, 25(2):208-2) 1979a.
Luc Devroye and Terry Wagner. Distribution-free inequalities for the deleted and holdout error estimates. JEEE Transactions on Information Theory, 25(2):202-207, 1979b.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference Machine Learning, pp. 1675- 1685, 2019.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
Andre Elisseeff, Theodoros Evgeniou, and Massimiliano Pontil. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(Jan):55-79, 2005.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. arXiv preprint 102. 2019.
Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. Privacy amplification by iteration. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pp. 521-532. IEEE, 2018
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pp. 139-449, 2020.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points -ollss-nnieeeeee stochastic gradient for tensor decomposition. In Conference Learning Theory, pp. 797-842, 2015.

---

Under review as a conference paper at ICLR 2020
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Interaational Conference on Machine Learning, pp. 1225-1234, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Simplifying neural nets by discovering flat minima. In Advances in neural information processing systems, pp. 529-536, 1995.
Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4700-4708, 2017.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315-323, 2013.
Kenji Kawaguchi, Leslie Pack Kaelbling, and Yoshua Bengio. Generalization in deep learning. arXiv preprint orXiv:1710.05468, 2017.
Michael Kearns and Dana Ron. Algorithmic stability and sanity-check bounds for leave-one-out cross-validation. Neural computation, 11(6):1427-1455 1999.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.044 2016.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2014.
Vladimir Koltchinskii and Dmitriy Panchenko. Rademacher processes and bounding the risk of function learning. In High dimensional probability II, pp. 443-457. Springer, 2000.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Anders Krogh and John Hertz. A simple weight decay improve generalization. In Advances in neural information processing systems, pp. 950-957, 1992.
Iaa Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 2815-2824. PMIR, 2018.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances in Neural Information Processing Systems, pp. 6389-6399, 2018.
Hongzhou Lin and Stefanie Jegelka. Resnet with one-neuron hidden layers is a universal approximator. In Advances Neural Information Processing Systems, pp. 6172-6181, 2018
Wenlong Mou, Liwei Wang. Xiyu Zhai, and Kai Zheng. Generalization bounds of sgid for non- convex learning: Two theoretical viewpoints. volume 75 of Proceedings of Machine Learning Research, pp. 605-638. PMLR, 06-09 Jul 2018. URL 1155/oul8a.hht..
ngs. ml p
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalizaain in deep learning. Advances in Neural Information Processing Systems, pp. 11615-11626, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956.
2017.
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1571-. Omnipress, 2012.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In ICLR, 2018.
William Rogers and Terry J Wagner. A finite sample distribution-fre free performance bound for local discrimination rules. The Annals of Statistics, pp. 506-514, 1978.
10

---

Under review as a conference paper at ICLR 2020
Shai Chalev-Shwarte Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635- 2010.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In International Conference on Machine Learning, pp. 71-79, 2013.
Samuel L Smith, Pieter-Jan Kindermans, Chris Ying, and Quoc V Le. Don't decay the learning rate, increase the batch size. arXiv preprint arXiv:1711.00459 2017.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, llya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15():1192--1988 2014.
Vladimir N Vapnik. Statistical learning theory. A Wiley-Interscience Publication, 1998.
Lei Wu, Zhanxing Zhu, et al. Towards understanding generalization of deep learning: Perspective of loss landscapes. arXiv preprint arXiv: 10239, 2017a.
Xi Wu, Fengan Li, Arun Kumar, Kamalika Chaudhuri, Somesh Jha, and Jeffrey Naughton. Bolt-on differential privacy for scalable stochastic gradient descent- based analytics. Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1307-1322, 2017b.
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael Mahoney. Pyhessian: Neural networks through the lens of the hessian. arXiv preprint arXiv: 1912.07155, 2019.
Dongrue Zhou and Quanquan Gu. Lower bounds for smooth nonconvex finite-sum optimization. arXiv preprint 1rXIv:1901.11222 2019.
A PROOFS
Lemma 1 (Dynamics of divergence). Let (w;xx) w TAw Aw an eigenvector of A where A|x; - x/1 = Xaw (x; x².]. Let D, be w. - wy at S \uz' be the step runs SGD on f(w, S) and f(w, where S, are twin datasets and x' Zj 0, x. xy 0, Vj # the dynamics of D, are given by:
ya. Suppose (xt - x1//1l>; x4
size of SGD and Ao 0. Suppose
E
A H1ll = =11 oz )E A
|| a/ll
(5)
Proof: In case the different entry 2i, 24 is not picked, the gradient difference of (w; and fww;
is
Vf(w, Vf(w', ,2) = A(w w'1
and in case different entry 24, 24 is picked,
(w, (
A(w w/| + [x; 2!]]
Since Ao O, one can inductively show A, = 0,(2; x²}] where 0g > O. Since SGD selects 2 2
with probability and a different entry with probability 1 we have the following dynamic:
(I AnJ)[ue w/]]
with prob. 1
A
(T 04 ArA)(we wi] + ou. - x[]]
with prob 1 1/n.
B A+11 ||
=E [|| A| Index not selected] P[Index is not selected]
E [||
S++1 ||
Index i is selected] P[Index i is selected)
1
= ||(T - A)(we - will + orl [2; - x!]] I[(T - A)(w, - willl + 1h
-(1
-(1 1
)1 and 0.|1=; 2 + - az + aulll x/Il
n
Ct ||: z''l
-(1 aadee |E|

---

Under review as a conference paper at ICLR 2020
Lemma (Lower bound on divergence), Let A be we - wy ar be the step size of SGD and Ap Suppose [et 2/1/ ||a; -اليl is an eigenvector of A where Ale; x'} Awx [r x.}. Running
SGD on fww S), we have:
Arll
2
Σ
II
an(1 ardar)
71
Proof: By Lemma
I we have
E B|ArT| = 1BI -T-
QT-1
[1t xiill
n1
= (1 - -a--1 E A + QT ||= - x411
T-1
= |1[r; - -
II T=H+1
(1
Cr )ww)
Theorem 1. Let we; wt, be the outputs of SGD on twin datasets S, S' respectively, De be wi w/ and Or be the step size of SGD. There exists a function f which is convex and 3-smooth, T--Lipschitz on domain of We, wi and twin datasets S, S' such that the divergence of the two SGD outputs satisfies:
2n - ats and Extab 2 2n D
E
T
E||AT|1 2
2 at-
(6)
Proof We set = 3, = 0.5, x vu 0.5. The proof is constructive. Let f(w, =)
Iw Aw - yz. The function is B smooth and convex by setting 8 || and u Au 2 0 for all
lie the range of A, where is PSD matrix which is not full-rank. We further set Tı to lie in the null space of A so that Av 0. The lower bound
u. We set S { 5' \ {=()
||lrr follows from Lemma 2 from the fact that An 0. Since w T Au w' Aw', Estob
sup, [ 2) - f(w/: =) 2 Ele [wy w411 2
1=1 Otg.
The last part show for any sequence Wi generated from stochastic gradient descent step using
data set will have a constant gradient thus the Lipshitzness will follow. Let U be the range of A (so any ((T-a,A)ure
U satisfy wau 0. Pick 7 that u. Au 2 y 0 holds for all
U. For all
[[w]41 uIll < [I(7- 04 A)w, u +oz u/l < -ar))ll?? u/l + This implies [|wo wll S 4. Now we
bound gradient fw 2)ll = A - =1| < |v Aw] + 1o yx)++ +/2+ [ + +|u yxr I 1+ 11+ 8 This implies that the function is L-Lipschitz with
+ n. By setting 3 2y the proof follows.
Theorem 2. Suppose loss function f(w, 2) of the form f(w,, S) 1 Ez= Jug (w
(wTxz) x.y) and fu(w") x)) satisfies (1) (5(() L, (2) < S fC() S 3, (3) ||-||| < and (4) S are Ê-self correlated. Let Wi, wt be the outputs of SGD on twin datasets S, S', A. == wi w/ and a S 1 is the step size of SGD. Then,
n
B|| 5 4LR
Eym
Proof: For simplicity we omit the dependence of f on Vj so that fø, (w Tx,) = f(w, 22). Note that the gradient of the loss function is V Sy (W. æz)) fú (w, æz)a and the Hessian is V Fuy (w. x;)
f (ww) x,) 1y)a,.] The stochastic gradient step of fv, (w. ary)
Wh+11 = w. -aff, (w, xz)2g.
The dynamics of the divergence can be described as:
E1 |
E1:A| n j
Σ A.
as 11 U, az)) fy, (w, 21)1,
(A. - are aol, ( (w)) x.) - (w, 2.)a
12

---

Under review as a conference paper at ICLR 2020
Note that (, az)) - Lu (we] (on[Tx))) sy)lay can be rewritten as S (we
03 3jj 23) A, where w
(1 0z)ur + 0, < 03 <
Similarly we can also rewrite Jy (w) xz)ars - (wl 2z) 2s)a4 as
Fw (w) 24 24)0;; (1y sa)oo
2 (P [w]] 21)0z for (w) x.)x
U& (w) 2/)a, fn lot 21)a')
+ 2 U (w)) x.) + fg. (w)) az))
2 (w) xt)) + fo:() (w) x!)}a²
2 F (w) o. 11)0,, D. + 2 (0 z1)aaaa D.
1
U (w) 2.) + fg. (w) xz)
2 S (w) 2)) + (w)) 21)
Thus equation equation can be written as
B1.++1 || EI. 11xl1([
at Σ
ys (w, T "x))sau )
2n
1=1
+
an
{f (w/ xz)) + Syy (w)) x;))<s
2n
at
Us
(w)
(.]xx() x/)) + fos (w') x1))=[|1
2n
By the E-self correlated assumption and letting H. 1 Ex,es 2z0 and Ht = Es 2z2J, have:
E A || S B]](1
(H + H')) at7
+
arL ||
+
arL
|
n
n
(9)
$ ar57 B + 20,
The first incquality follows from the fact that f'(-) 2 7 and 2yz s are all PSD. The second inequality follows from the fact that A, E Spanfæ1.... 2n }. Fix a, = a and the theorem follows.
Our next two lemmas are used in the proof of Theorem
Lemma 3. Suppose Nio O, Ø++1 sufficiently small constant.
1o H. have Ør 2 v( if > 0
Proof: In the proof following inequality:
< 1 +
< e
0.99
13

---

Under review as a conference paper at ICLR 2020
where >> 0 is a sufficiently small constant.
T
T
T II
UT
Σ
(1+
+ z0
(1
+
a
0.998
0.99$
1=
8=1+1
1=
T
Σ
Σ
1
exp
$
1=
8=t+1
T
y
exp
(a (T/))
(10)
t
t=t++1
y
1++a
t=fo+1
T
2
to
Lemma 4. There exists a function J which is non-convex and 3-smooth, twin datusets S' and
constant 0 such that the following holds: if (GD is run using step size 0.99 for 1 S 1 < T,
and We, w/ are the outputs of SGD on S and S', respectively, and A, Wt w/y then:
T
A1 < to < T. E 11 * #0]
(11)
2n to
Proof: Consider the function f in Equation and choose A to have positive and negative eigenvalues. We set the minimum eigenvalue of A equal to -3 and other eigenvalues with absolute value at most B. We select twin datasets for such A as follows. We set all elements in S \ {xa) = S' \ {x{}
to lie in the column space of A. Also, vj * i, choose Ij such that x] Ar, > 0, and choose any yj between and 1.
Let be such that v AA = 3 and ||a|| = 1. Finally, let U, 0.5, x = -u v/4 = 0.5.
In this setting, one observes that the divergence A, follows the following dynamic:
(1 (1- AAA
with prob. 1 1 1
A41==
(1-a [x; xf]
with prob 1/n.
We first observe that A, == w, w/ is of the form vO,, where O, 0. This be shown using
induction. Let r be the first time that H;, xa are picked, we have Ar+1 [ - a!] va The
iterative step of A++1 and A implies that A = 004+1 where 8.+1 = (1+ a,3)6, with probability
(1 - 4 and 0++1 = (1 + 3,3)6, + a with probability 1
The above construction then yields:
E1s+1 ||A A.. + 0] =E1
(1
(1-
1 |1(1 - a,A)), + --110-1 - - azvil
11
(1-2) n (1 an3)0 + - [(11 a,3)0 + +a0)
||:
(12)
= ||
[[1 + ac
+ at
n
a
F1a A, ||| A # 0) + Ct ||||
(1 + 0.990
Now apply Lemmal 3 with 2t | Aro + 0] and y
e|
This gives us that ør >
0.993n
alle|] (T/to)² 0.993n (T/ta)), since ||||| 1.
0.999n
Finally, the claimed bound follows by setting the minimum eigenvalue 9 0.99
14

---

Under review as a conference paper at ICLR 2020
Theorem 3.
There exists a function f which is non-convex and B-smooth, twin datasets S,S' and constants a s.t. the following holds: if SGD is run using step size 0x 0.99pt for 1 S < T, and we, w/ are the outputs of SGD on S and S', respectively, and A == Wt w,, the divergence of SGD after T rounds (T n) satisfies:
T
E B
(13)
3n
Proof:
The proof is based on Theorem plus the idea of a "burn-in" period. We have:
BI Arll = E|ll wt wif 1 = A = 0] |||l wy w/ I1lm + OJIPInn + 00]
M E|| Wt w// ll + [ + 0]
(1 (1---11 n ,
nlta ||= - 2111
7
(14)
7
1+0 | x''ll
Lemma 5. (Hardt et al. 2016) Assume f is 3-smooth and L-lipschitz. Let we, w/, be outputs of
SGD on twin datasets S² respectively after iterations and let A := [w, - will and 8, = E| A
Running SGD on f(w; S) with step size 042 satisfies the following conditions:
The SGD update rule is a (1 + a+ -expander and 20, L-bounded.
||]]A|||| S (1 + a,d) A + 2004.
E|||AT|IAr, 0]
22
Theorem 4 ( Permutation). Assume f is B-smooth and L-lipschitz. Running T (T n) iterations of a the stability of SGD satisfies:
SGD on fww; S) with step size at = Bt.
2LT
2L
E ATIl S
Estab
(15)
n I+a
1+a
Proof. Let t represents the event that the first time the SGD pick the different entry is at time
E B| = Ar H < n]P(H S n] + Ell Ar > n]P(H > nl
O(permutation))
1 n
BI
||| = 1)
71
1
Σ
2T.
(16)
12
2L
dt
n1
1
2TT
nlta
The inequality (*) derived by applying Lemma
Lemma 6. Let Wh, wi be outputs of SGD twin datasets S, S' respectively after t iterations and let A, = Wt w/. Suppose that t4 = ctx-1. Then the following conditions hold:
P(A4-11 11 # 0] n-te-1
P|A4-11
0
0 < (1 + :4)
E[||AT|
D
0j $
Au.
# #0 1) +
T
a2L
15

---

Under review as a conference paper at ICLR 2020
Proof. In the proof we will use the following inequality with 2 1:
n
S
-1-
n
n
n +
i):
PI 4/ = 0, Dr. *0]
P|A., 0/2,, *0|
PIAr. #
1- (1 - 1/mi//
-1 (/-
(17)
1 1/11/e
I (1 x/1)*x-1 <
n2
n2 + +
i):
P(A&, # 0, D12-1 #0]
PI 0/4 + 0]
PIA., + 0]
P[A # 0]
PI #
1 (1 -1/12)4-
(1 - 1/ne)e
(18)
atth
m-te
n
tk-1 (1 + tk
41
- -1 + tk
1
iii):
By applying i) and ti) in the decomposition of (E * 0] we have
|T|AA,, #0] s B|| ||| + - + 0/ #0]
B AT A.... 0 0/ #0]
4-1
(1+ 1/
E || || #
tx
T
2L
(19)
1--
nu + 1--1
tx
(1
+
B[ll 102 #0]
n
T
21
+
4-1
n tレ-1
where the last inequality uses the fact that E[||AT|| =0 S
T 12-1
26
Theorem4b (Uniformly Independent) Assume f is B-smooth and L-lipschitz. Running (T n)
iterations of SGD on (w; 5) with step size a4 = ae the stability of SGD satisfies:
To
T
E Ar || <
(
Extab S 16log(m) I
(20)
Ita
1+
Proof. We first decompose Ar as follows by selecting to nE:
E
Arll
E A. OJP = 0] ATII + OP #
(21)
21.7a (Lemma
Temm 2 <
lan(yya w11
16

---

Under review as a conference paper at ICLR 2020
Term is easily bounded by applying Lemma with ag 23. To bound Term 2, plug in P(AN. * 0] = 1- (1 1/n)** I is and recursively apply point (ii)) from Lemma by setting
4+1 dç. We get:
B L + 0
*0]
2L t
k-1
n
R-1
II
(1 +
ty+1 tr
1
-=++1
27.
T
1i+1
exp(
Σ
lrt1)
11
n
+ t;
n
T=it1
2cl.
c
4
crp
(22)
c- 1
2cLT
erp
n
c
n
2L loggg(
ca
exp
nite
logc
c-1 1
11gg nlto
In the second and third inequality we use the fact that 1 + x S exp(x) and 4,41 ct, to get
I1 (1 + bxtt) exp(E fr S exp (-))
The last inequality is derived by picking
c=4.
Theorem 5. Let we, wi be the outputs of SGD on twin datasets S. S', and let A. := wt w/. There exists a function which is non-convex and 3-smooth, twin sets S,S S' and constants a, such that the divergence of SGD after T rounds (T >> n.) using constant step size 0.994 satisfies:
E B|
2 n 2 02/2
(23)
Proof: The proof is similar Theorem
Since A Spanffx x/}, we have:
1 (1 a, ||= xzll
E A4tll (1
Suppose to is the hitting time when | || > 0 and A ||| = 0 .1 ||
||,, ||اا- c 3n
E Ar ||
w
A
[] 0]
[ wy
w/ ||
* #0]
B|[l 10, w
|l
A * 0]P(A, + 0]
| wr'll e2I/2)
(24)
||;
x''l nT//
n²
Theorem 6. Given set S and a 3-smooth and T-Liischitz loss funtion f. suppose SGD with fixed step size a S 2² contractive region: Iwo w' || E a with large enough radius so that o > 12L then we have VT 2 1, ||wr wo1 < a.
E4LT reaches point wo which close to local minimum wt in a (a, -Hessian
7
17

---

Under review as a conference paper at ICLR 2020
Proof: Let Hwi w 9 E 3, V ffru + (1 () We derive that:
|w++1 - woll
| V w (w. 2)
w woll² + a² v. fuc, 2)1 2 2a V vf ((r: 2) [wo wol
ww woll a² fw.,, 2) 2a w. w/ f(w,, S) [we wol
(25)
2a(Vwf 2) - [wf(wr, 5) [wo wol
Va(V.. f S) V wwo. S)]
[wo wol
w w + a 2 2a 2a/ wo]
Hw., . , wo] + GaLo ..., Vi (wf(w((1,,)), we have |w woll a²² r,2 2a wy wo]
Due to the fact that w² w/ E Span VV v (wo: ...,
Hur, . wu wo] + GaLo
(26)
S(1 2ary We - woll? + a L + GaLo
This implies | - woll & a for all t.
B EMPIRICAL SUPPORT FOR THEOREM 6
In order to empirically support Theorem 6 we ram the follow experiment: We started with a fully- trained model w², and generated random perturbations 인 =² + where v ~~ ~ o²). We then trained each v until convergence ú", and computed the normalized distance ||0" w" [||[[ ||. To match Theorem 6 this distance should be w after perturbing stay close to w", as in the conclusion of Theorem 6
than 2|| w0I] ="||/|[""|] [], i.e., the trained weights
For the above experiment, we first trained both ResNet18 and Densenet121 for 200 epochs, with constant learning rate of 0.01, a momentum of 0.9, and batch size of 128. We generated 20 Gaussian perturbations of the trained model weights w* and trained each for 50 more epochs, resulting in weights t" We used standard deviation E {0.01, 0.005} for the Gaussian perturbations. We then computed the normalized differences as explained in the previous paragraph. The results are shown in T Inspecting the table shows that the distances between the trained weights after perturbing are quite close to the distances before further training, with low variance. This indicates that the weights after training the perturbed model are well within the desired range as specified in Theorem 6
|| w w=|l/|
| w [ ||='
a = 0.01
0.549:::000009
0.557:10.0003
ResNet
0.005
0.274.10.00005
0.277-10.007
0.01
0.123:0000003
0.126:10.0004
DenseNet
σ 0.005
0.06240.00001
0.065+000033
Table 2: Pertubed SGD Results
18


Reviews:
[{"review_id": "lE4liCZv-b-", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "Summary:\n\nThe paper studies the stability of stochastic gradient descent (SGD), which is one of the framework used for explaining generalization. More specifically, the paper investigates the tightness of the algorithmic stability bounds for SGD given by Hardt et al. (2016). Furthermore, the authors propose the Hessian contractive condition, which characterizes deep learning loss functions with good generalization properties, when being trained with SGD.\n\nPros:\n\n1. The paper concerns the stability-based analysis, which is one of the approaches used for explaining the strong generalization performance of deep neural networks in practice.\n\n2. By investigating the tightness of the stability bound for various types of problem (convex, non-convex), the paper shows that in general, using stability framework seems to hit an obstacle on the way to explaining generalization. Hence, further conditions are needed to guarantee generalization. By this point, the authors propose Hessian contractive condition which is satisfied by potentially many machine learning loss functions and is sufficient to guarantee a better generalization properties.\n\n3. The paper provides empirical evidences / experiments which make the theoretical claims more comprehensible.\n\nCons:\n\nApart from the strong points, I still have one concern about the clarity of the paper:\n\n1. The lower bound in Theorem 1 is larger than the upper bound in Theorem 3.8 in Hardt et al. (2016) when the Lipschitz constant is smaller than 1. Can you explain this mismatch?\n\nI hope the authors can address my concern to improve the quality of the paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "b0OPmXmY-Kj", "reviewer": "AnonReviewer3", "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 considers the stability of the stochastic gradient decent algorithm under different conditions. They show a lower bound for the stability of SGD in the smooth and convex case, and show that the bound can be tightened for linear models. They give a tight bound for the stability of SGD with decreasing step size in the non-convex case.  Then they propose the Hessian Contractive condition, and under this condition a tight bound for the stability of SGD with constant step size is given. \n\npros: 1, They propose the Hessian Contractive condition which is weaker than strongly convex and show that the family of widely used (convex) linear model loss functions will satisfy the Hessian Contractive condition. \n\n2, They analyzed the stability of SGD and give the lower and upper bounds for the stability in many cases. \n\ncons: 1, In Theorem 3, they give a lower bound for the stability of SGD with decreasing step size in the non-convex case. However, this lower bound is larger than the upper bound in Hardt 2016 when T goes to infinity and the other parameters fixed. This contradiction implies that the results in Theorem 3 should be incorrect. \n\n2, They claim the O(1) uniform stability of SGD in under the Hessian Contractive condition. But the uniform bound of $||w^* - w^{*\\prime}||$ is not proved. \n\nAfter the rebuttal.\n\nThe authors partially addressed my concerns. I have read other reviewers' comments. I decide to remain the current score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "JD59_QNr_kf", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies stability of SGD which is a popular optimization algorithm. The authors aim to build a tight stability analysis. In particular, the authors show by constructing specific problems that the existing stability bounds for SGD applied to convex problems are tight within a constant factor. Then, the authors refine the stability analysis in non-convex case by presenting new bounds, and show the new bounds are tight. The authors also provide new conditions weaker than strongly convex assumption in both convex and non-convex case. The paper is clearly written and is easy to follow.\n\nComments:\n1. I have doubts in the proof of Lemma 1. It seems that the identity\n\\[\nE\\|\\triangle_{t+1}\\|=(1-\\alpha_t\\lambda)E[\\|\\triangle_t\\|]+\\frac{\\alpha_t}{n}\\|x_i-x_i'\\|\n\\]\nis not correct. The underlying reason is that we can not exchange the expectation and norm. As far as I can see, one can only show\n\\[\nE[\\|\\triangle_{t+1}\\|]=\\frac{(n-1)(1-\\alpha_t\\lambda)}{n}E[\\|\\triangle_t\\|]+\\frac{1}{n}E\\big\\|(1-\\alpha_t\\lambda)(w_t-w_t')-\\alpha_t(x_i-x_i')\\big\\|\n\\]\nTherefore, I think Lemma 1 may not be right. As a result, the lower bounds on the stability bounds may not be right.\n\n\n2. The self-corrected condition depends on the dataset S. However, for the uniform stability, one needs to consider all datasets S. Therefore, the divergence bound in Theorem 2 can not be used to get stability bounds. Furthermore, $\\xi$ should be zero if one considers all the dataset.\n\n3. In Theorem 4, $\\alpha_t=\\alpha/(\\beta n)$ should be $\\alpha_t=\\alpha/(\\beta t)$? Furthermore, I find it hard to follow the proof. For example, I cannot understand why the authors use the inequality $(1-1/n)^r\\leq n/(n-r)$. Is it clear that $(1-1/n)^r\\leq 1$? In eq (16), the last third term involves $t_{k-1}$ and $t_k$, while the last second inequality involves only $t_{k-1}$, which is not very meaningful. I also cannot understand well the deduction in eq (20).\n\n4. In the statement of Theorem 6, the authors indicate that $\\|w_T-w^\\star\\|\\leq\\sigma$. However, the authors only prove this result in expectation. Furthermore, if this inequality only holds in expectation, then one can not use the Definition 6 which requires $w_t$ to be close to $w^*$ almost surely.\n\nIn conclusion, although this paper considers a very interesting problem, there are some issues on the correctness of the deduction.", "extra_scores": {}, "extra_text": {}}, {"review_id": "44hRd56y2PF", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "1.\tIn my understanding, a learning algorithm is stable when a small perturbation in the training does not affect the outcome drastically. Based on this notion, in [Data-Dependent Stability of Stochastic Gradient Descent, Kuzborskij and Lampert, ICML 2018] used (Hardt et al., 2016) and extended them to the distribution-dependent stability setting for both convex and non-convex cases. I also understand that the bounds of (Hardt et al., 2016) are stated in terms of worst-case quantities, but Kuzborskij and Lampert revealed new connections to the data-dependent second-order information. First, among several important works that analyze the stability of SGD, you missed the work of Kuzborskij and Lampert. I suggest that you please include this work, discuss it, and show how you are similar or different than them and how tighter or relaxed your bounds are compared to them. Since both works are based on the seminal work of Hardt et al., 2016, in my opinion, without a proper comparison/discussion this work is incomplete. However, I consider this present manuscript is a fairly well-written manuscript but it is not complete yet. \n\n2.\tIn the context of uniform stability, [London, B. Generalization bounds for randomized learning with application to stochastic gradient descent, 2016], “partially” addressed how data-independent component such as step-size affects the stability. What is your input on that? Theorem 6 in your manuscript mentions about fixed stepsize but other than that I do not see any discussion on step-size which is in my understanding is an important component in the performance of SGD. \n\n3.\tPlease correct me if I am wrong: In the proof of Theorem 6 did you use the uniformly bounded gradient? But one can even strongly argue that this bound is actually $\\infty$. In my understanding, uniformly bounded gradient with strong convexity leads to a contradiction. That is a stronger argument can be made that the above assumption is in contrast with strong convexity. Please see [\"SGD and Hogwild! Convergence Without the Bounded Gradients Assumption\" by Nguyen et al.] as one of the instances. How about using more relaxed assumptions such as Strong growth condition on a stochastic gradient as in Assumption 4 of [Dutta et al. AAAI 2020, On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learning]? \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The AC and reviewers agree this is an important line of research. However, only one reviewer was initially positive, as the other reviewers raised some issues, and the rebuttal only partially addressed some of them (e.g., the reviewer is now OK with Lemma 1 being correct), but there are typos in the proofs, and there were other issues like the uniform bound that R3 brought up which was retracted in the revision, and such. These issues give us a bit of lack of confidence in the rigor of all the results.

In addition to the lack of carefulness in places, this paper (more than usual for an accepted paper) seemed to miss references in the literature. In addition to all the ones pointed out in the reviews (especially R3's, which I don't think was fully adequately discussed in the rebuttal), other tight lower bounds on uniform stability have been developed recently (see Thm 4.2 in Bassily et al. https://arxiv.org/pdf/2006.06914.pdf).  From the optimization point of view, it is undesirable to introduce new conditions unless really necessary, and often these new conditions are previously known under a different name; if they really are new, they should be compared to old conditions. In particular, then new "Hessian contractive condition" should be compared to standard non-convex conditions like strong growth, error bound, Polyak-Lojasiewicz, etc.

Finally, this is based off the Hardt/Recht/Singer 2016 paper, but there is a more recent Hard/Recht work that argues that algorithmic stability is not the right tool, because it cannot explain the fact that training error drops roughly the same with real data or with data with completely random labels -- so any generalization theory has to be data dependent. See: "Understanding deep learning requires rethinking generalization" (https://arxiv.org/abs/1611.03530) Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, Oriol Vinyals.  So this issue should be addressed as well.

Overall, this could be a promising paper and the AC recommends the reviewers make a substantial revision addressing these concerns.
Decision: Reject