Year: 2020

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 Hardt et al. (2016). We show that the analysis of Hardt et al. (2016) 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 training using SGD with constant step size. In this vein, we propose the notion of a Hessian Contractive (HC) region, which quantifies the contractivity of regions containing local minima in 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 of deep neural networks.

heading: 1 INTRODUCTION
text: Stochastic gradient descent (SGD) has gained great popularity in solving machine learning optimization 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 of SGD have been thoroughly studied (Ge et al., 2015; Rakhlin et al., 2012; Reddi et al., 2018; Zhou & Gu, 2019; Carmon et 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., 2016) tackled the problem using the algorithmic stability of SGD, i.e., the progressive sensitivity of the trained model w.r.t. the replacement of a 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; Koltchinskii & Panchenko, 2000) or weight-based complexity theorems (Neyshabur et al., 2017; Bartlett et al., 2017; Arora 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 et 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 even 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
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 1: 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 1 that the analysis in (Hardt et al., 2016) is tight for convex and smooth objective functions; in other words, there is a convex loss function whose stability grows linearly with the number of training iterations, with constant step size (αt = α) 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 stab does not increase with t.
R3. In Theorem 3 we show that the analysis in (Hardt et al., 2016) for decreasing step size (αt = O(1/t)) is loose for non-convex objective functions by providing a 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 δt := E||wt − w ′ t||, where wt is the model trained on data set S and w ′
t is the model trained on a data set S′ that differs from S in exactly one sample. In Theorem 4 we provide evidence that our new upper bound in the non-convex case is tight, by showing a non-convex loss function whose divergence matches the upper bound for our divergence.
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 δt increases exponentially.
Thus the only functions whose stability provably does not increase with the number of iterations when a constant step-size during SGD is employed, are strongly convex functions. However, a) it 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, 2018; 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 strongerthan-convex, but weaker-than-strongly-convex assumption of the loss function can be made, at least near local minima. If we can show algorithmic stability near local minima, we can still show the stability using similar argument as (Du et al., 2019; Allen-Zhu et al., 2019).
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, is 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) a 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 is a reasonable condition for several loss functions. Empirically, we verify the Hessian Contractive condition near a 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 our second set of contributions:
R6. In Observation 1 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.
R7. In Theorem 6 we show that the Hessian Contractive condition will localize SGD iterates in a neighborhood of minima, which implies a constant stability bound for SGD near the local minima.

heading: 1.1 RELATED WORKS
text: Stability and generalization. The stability framework suggests that a stable machine learning algorithm results in models with good generalization performance (Kearns & Ron, 1999; Bousquet & Elisseeff, 2002; Elisseeff et al., 2005; Shalev-Shwartz et al., 2010; Devroye & Wagner, 1979a;b; Rogers & Wagner, 1978). It serves as a mechanism for provable learnability when uniform convergence fails (Shalev-Shwartz et 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 a single data point in the dataset is replaced. In (Hardt et al., 2016), 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 et al., 2018; Feldman & Vondrak, 2019; Chen et al., 2018). The worst case leave-one-out type bounds also closely connect uniform stability with differential private learning (Feldman et al., 2018; 2020; Dwork et al., 2006; Wu 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-dependent upper bounds on stability1. In this work, we report for the first time lower bounds on 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 generalization 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., 2016; Li et al., 2018). In (Chaudhari et al., 2019), the authors construct a local entropy-based objective function which converges to a solution with good generalization in a 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. In this paper, we 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.

heading: 2 PRELIMINARIES
text: 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 × {−1,+1}, let S = {z1, ..., zn} denote a set of n samples zi = (xi, yi) drawn i.i.d. from D. Let w ∈ Rd be the parameter(s) of a model that tries to predict y given x, and let f be a loss function where f(w; z) denotes the loss of the model with parameter w on sample z. Let f(w;S) denote the empirical risk f(w;S) = Ez∼S [f(w; z)] =
1While it is an interesting open problem to get data-dependent 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.
1 n ∑n i=1 f(w; zi) with corresponding population risk Ez∼D[f(w; z)]. The generalization error of the model with parameter w is defined as the difference between the empirical and population risks:
|Ez∼D[f(w; z)]− Ez∼S [f(w; z)]|.
Next we introduce the Stochastic Gradient Descent (SGD) method. We follow the setting of (Hardt et al., 2016), and starting with some initialization w0 ∈ Rd, consider the following SGD update step:
wt+1 = wt − αt∇wf(w; zit),
where it is drawn from [n] := {1, 2, · · · , n} uniformly and independently in each round. The analysis of SGD requires the following crucial properties of the loss function f(., z) at any fixed point z, viewed solely as a function of the parameter w:
Definition 1 (L-Lipschitz). A function f(w) is L-Lipschitz if ∀u, v ∈ Rd: |f(u)−f(v)| ≤ L‖u−v‖. Definition 2 (β-smooth). A function f(w) is β-smooth if ∀u, v ∈ Rd: |∇f(u)−∇f(v)| ≤ β‖u−v‖. Definition 3 (γ-strongly convex). A function f(w) is γ strongly convex if ∀u, v ∈ Rd:
f(u) > f(v) +∇f(v)>[u− v] + γ 2 ‖u− v‖2.
Algorithmic Stability Next we define the key concept of algorithmic stability, which was introduced 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 a 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′ are twin datasets if they differ at a single entry, i.e., S = {z1, ...zi, ..., zn} and S′ = {z1, ..., z′i, ..., zn}.
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{ε : sup z∈Z,S,S′ EA|f(A(S); z)− f(A(S′); z)| ≤ ε}.
Here EA denote expectation over the random coins of A. Also, for such an algorithm, one can define its expected generalization error as:
GE(A,n) := ES,A[Ez∼D[f(A(S); z)]− Ez∼S [f(A(S); z)]].
Stability and generalization: It was proved in (Hardt et al., 2016) that GE(A,n) ≤ εstab(A,n). Furthermore, the authors observed that an L-Lipschitz condition on the loss function f enforces a uniform upper bound: supz |f(w; z)− f(w′; z)| ≤ L‖w − w′‖. This implies that for Lipschitz loss, the algorithmic stability εstab(A,n) (and hence the generalization error GE(A,n)) can be bounded by obtaining bounds on ‖w − w′‖.
Let wT and w ′ T 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 δT := EA||wT − w ′
T ||. While (Hardt et al., 2016) reports upper bounds on δT with different types of loss functions, e.g., convex and non-convex loss functions, we investigate the tightness of those bounds.

heading: 3 TIGHTNESS OF EXISTING BOUNDS
text: 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 ∝ t are tight, and 2) for linear models, the analysis can be tightened to show that stab does not increase with t. Then we move on to the non-convex case, where a) for decreasing step size we 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 δt increases exponentially with t.

heading: 3.1 CONVEX CASE
text: In this section we analyze the stability of SGD when loss function is convex and smooth. We begin with a construction which shows that Theorem 3.8 in (Hardt et al., 2016) is tight. Our lower bound analysis will require the following quadratic function:
f(w; z) = 1
2 w>Aw − yx>w (1)
where A is a d× 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 wt, w′t be the outputs of SGD on twin datasets S, S′ respectively. Let ∆t = wt−w′t and αt be the step size of SGD. There exists a function f which is convex, β-smooth, and L-Lipschitz on the domain of w, and twin datasets S, S′ such that:
E‖∆T ‖ ≥ L
3n ∑T t=1 αt, and εstab ≥ L 3n ∑T t=1 αt. (2)
The convex upper bound in Theorem 3.8 in (Hardt et al., 2016) states that ‖∆T ‖ ≤ L ∑T i=1 αt n , which implies that the divergence increases throughout training. The lower bound in Theorem 1 suggests the tightness of the upper bound. However, in practice, such phenomenon is not commonly observed, i.e., for a family of convex but not-strongly-convex 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, we 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 a ξ-self correlated data set. Essentially, a self-correlated dataset requires an average linear dependence of each x. Recall that the i’th sample zi = (xi, yi). Definition 5. A set S = {z1, ..., zn} is ξ-self correlated if ∀j ∈ [n], 1n ∑n i=1(x > j xi) 2 ≥ ξ > 0.
Assuming that ∀j ∈ [n], ‖xj‖ ≥ r for some r > 0, definition 5 implies that S is at least r 2
n -self correlated. Thus the above condition holds for all datasets S not containing the zero-feature vector. In our next theorem, we leverage on the ξ-self correlated condition to prove a 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(w; z) in terms of fy(w>x) where fy(·) is a scalar function depending only on the inner product of the model parameter w and the input feature x. Theorem 2. Suppose a loss function f(w, z) is of the form f(w, S) = 1n ∑n j=1 fyj (w
>xj), where fy(w
>x) satisfies (1) |f ′y(·)| ≤ L , (2) 0 < γ ≤ f ′′y (·) ≤ β, (3) ‖x‖ ≤ R and (4) S, S′ are ξ-self correlated, twin datasets. Let wt and w′t be the outputs of SGD on S and S
′ after t steps, respectively. Let the divergence ∆t := wt − w′t and α ≤ 1β be the step size of SGD. Then, E‖∆T ‖ ≤ 4LR ξγn .
Remark 1. In (Hardt et al., 2016), an O ( L2
γn
) stability bound is derived on a loss function f(w, zi)
which is strongly convex, i.e., ∇2f(w) γI . In practice one can incorporate a strongly convex regularizer to impose strong convexity, often resulting in improved generalization performance in practice (Shalev-Shwartz et al., 2010; Bousquet & Elisseeff, 2002). The ξ-self correlated condition allows SGD to maintain a uniformly upper-bounded 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 xi lies in a low dimensional subspace, the divergence of SGD is comparable with a strongly convex loss function. This analysis suggests an alternative condition other can strong convexity can empower SGD an O(1) stability which is data-dependent. This motivates us to go beyond linear model and seek for a 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 w: f(w, S) = 12n ∑ xj∈S(x > j w−yj)2. Note that the Hessian of an individual linear regression loss term is xjx>j which is not strongly convex since it has rank 1. One cannot apply the strongly convex bound,
and the bound for convex suggests stability will increase linearly. However, one can rewrite the loss function as fy(w>x) where f ′′y (·) = 1. Hence Thm. 2 can be applied to give a non-accumulative bound on SGD’s stability. A similar result can be derived for the logistic regression loss.

heading: 3.2 NON-CONVEX CASE
text: In this section, we construct a non-convex loss function to analyze the tightness of the divergence bound in (Hardt et al., 2016). We first focus on the case of decreasing step size.
Theorem 3. There exists a function f which is non-convex and β-smooth, twin datasets S, S′ and constants a s.t. the following holds: if SGD is run using step size αt = a0.99βt for 1 ≤ t < T , and wt, w ′ t are the outputs of SGD on S and S
′, respectively, and ∆t := wt − w′t, the divergence of SGD after T rounds (T > n) satisfies: E‖∆T ‖ ≥ T a
3n1+a .
Comparison to the bound in Theorem 3.12(Hardt et al., 2016) In (Hardt et al., 2016), an assumption is made on the non-convex loss function, namely that f(w, z) < 1. We remark that our function f 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 a
1+a ≤ n, the upper bound in (Hardt et al., 2016), namely O(T a/n1+a) 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 is interested in training faster, smaller values of T in the above range are important. Our divergence lower bound motivates an investigation into the possible tightness of the analysis leading to the upper bound in (Hardt et al., 2016). In the following theorem we prove a tighter upper bound for this range of T : it does not assume f(z, w) < 1, and is non-trivial in the range when T a 1+a ≤ n.
Theorem 4. Assume f is β-smooth and L-lipschitz. Running T (T > n) iterations of SGD on f(w;S) with step size αt = aβn , the stability of SGD satisfies: εstab ≤ 2L2Ta n1+a .
Dividing our bound with the one in Theorem 3.12 in Hardt et al. (2016), we obtain the ratio
Ω
( T a2 1+a
na
) . This factor is less than 1 (and so we improve the upper bound) exactly when T a 1+a ≤ n.
Note that this is potentially a large range as a is 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 a polynomial improvement over the known bounds.

heading: 4 DEEP LEARNING AND LIMITATIONS OF BOUNDS
text: While Theorem 4 improves existing upper bounds on stability by an polynomial factor, it still can not explain the generalization performance of deep learning model. In particular, the analysis relies on a decreasing step size while in training deep learning model, constant instead of a 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 β smooth function.
Theorem 5. Let wt, w′t be the outputs of SGD on twin datasets S, S′, and let ∆t := wt − w′t. There exists a function f which is non-convex and β-smooth, twin sets S, S′ and constants a, γ such that the divergence of SGD after T rounds (T > n) using constant step size α = a0.99β satisfies: E‖∆T ‖ ≥ 1n2 e aT/2.
The above theorem implies that the generalization gap may deteriorate at an exponential rate if SGD is run with a constant step size for a non-convex function. However, in Fig. 1a we observe that the distance between the weights of two deep models trained on twin datasets (in other words, the divergence δT stabilizes after≈ 20 epochs of training. Fig. 1a suggests that the generalization gap for deep models may remain constant after sufficiently many training iterations. However, the analysis of (Hardt et al., 2016) suggests that local minima of the loss landscape must be in strongly convex
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 a large fraction of eigenvalues which are close to zero (Yao et al., 2019; Chaudhari et al., 2017). This phenomenon requires further investigation to close the gap between theory and practice. Next, we formalize a 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.

heading: 4.1 GEOMETRY OF LOCAL MINIMA
text: In Theorems 1 and 5, we show that in general, divergence (and hence stability) may deteriorate at a linear or 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 = {z1, ...zn}, a local minimum w∗ is in a (σ, γ)-Hessian contractive region if ∀w,w′ with max(‖w′ − w∗‖, ‖w − w∗‖) ≤ σ and z ∈ S,
∇wf(w, z)>Hw′∇wf(w, z) ≥ γ‖∇wf(w, z)‖2 (3) whereHw′ = ∇2wf(w′;S) = 1n ∑n j=1∇2wf(w′, zj). When (σ, γ)-Hessian contractive holds for all
σ > 0 and local minima w∗, we say f(w;S) is globally γ-Hessian contractive.
Hessian contractivity describes a region where the stochastic gradient will lie in the range of a positive semi-definite Hessian matrix. Such a condition prevents the iterates of SGD from escaping from a 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 a weaker assumption. To show that this class is nonempty, we observe the (not strongly convex) linear models loss functions in Theorem 2 satisfy Hessian contractive condition globally. Observation 1. Suppose loss function f(w;S) conditions in Theorem 2, i.e., f(w, S) = 1 n ∑n j=1 fyj (w
>xj) satisfies (1) |f ′y(·)| ≤ L , (2) γ ≤ f ′′y (·) ≤ β, (3) ‖x‖ ≤ R and (4) S is ξ-self correlated, we have f(w;S) is globally ξγR2 Hessian Contractive.
Dependence on dataset The Hessian Contractive condition states that the gradient of loss function evaluated on z 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 (σ, γ)-Hessian 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 a set S and a β-smooth and L-Lipschitz loss funtion f , suppose SGD with a fixed step size α ≤ σ 2
2γL2 reaches point w0 which is close to a local minimum w ∗ in a (σ, γ)-Hessian
contractive region: ‖w0−w∗‖ ≤ σ with large enough radius so that σ > 12Lγ , then we have ∀T ≥ 1, ‖wT − w∗‖ ≤ σ.
Theorem 6 states that once the iterate w of SGD encounters a point in a (σ, γ)-Hessian contractive region with large enough radius σ, w will remain in this region. In terms of the stability of SGD, assuming SGD will bring wt into one of the local minima quickly (Ge et al., 2015; Allen-Zhu et al., 2019), the divergence ‖wt − w′t‖ will be uniformly bounded by the difference between two local minima w∗, w∗′ of loss functions f(w;S) and f(w′;S′) plus the σ-radius of the Hessian contractive region. The above suggests that a weaker condition than strong convexity is sufficient to explain the observation in Fig. 1a.

heading: 4.2 EMPIRICAL SUPPORT FOR HESSIAN CONTRACTIVITY
text: 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-
sian contractive regions. We propose to empirically support this hypothesis by locally approximating the LHS of Eq. (6)–normalized by ‖∇wf(w̃, z)‖2–during the training of a model, and showing that this quantity steadily increases as training progresses. This indicates that SGD leads the training into regions of increasing contractivity.
We 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
∇wf(w̃, z)>H(z)∇wf(w̃, z) ≈ 1
η [∇wf(w̃, z)−∇wf(w̃ − η∇wf(w̃, z), z)]>∇wf(w̃, z) (4)
where the gradients on the RHS approximation are taken with respect to a random minibatch of samples. For each perturbation w̃ we normalize the corresponding approximation by ‖∇wf(w̃, z)‖2, and then take the mean and minimum over all of these quantities.
For our experiments, we used the well-known CIFAR10 dataset (Krizhevsky et 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 η = 0.001 and batch size 128 for the approximation in Eq. (4). We averaged over these 100 approximations and then further took the average over the five networks. The results of these experiments are shown in Fig. 1b, and indicate a clear increase in Hessian contractivity as training progresses.

heading: 5 CONCLUSION
text: In this paper, we studied the stability bound of SGD with regard to different types of loss functions. We proved a 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 of deep neural nets. We propose a new Hessian contractive condition that is slighly stronger than convex, but with O(1) stability bound. We provide empirical evidence to support the hypothesis that deep learning loss function is Hessian contractive near local minima.

heading: A PROOFS
text: Lemma 1 (Dynamics of divergence). Let f(w;x) = 12w >Aw − yx. Suppose [xi − x′i]/‖xi − x′i‖ is an eigenvector of A where A[xi − x′i] = λxx′ [xi − x′i]. Let ∆t be wt − w′t, αt ≤ λxx′ be the step size of SGD and ∆0 = 0. Suppose one runs SGD on f(w, S) and f(w, S′) where S, S′ are twin datasets and x′>i xj = 0, x > i xj = 0, ∀j 6= i, the dynamics of ∆t are given by:
E‖∆t+1‖ = (1− αtλxx′)E‖∆t‖+ αt n ‖xi − x′i‖ (5)
Proof: In case the different entry zi, zi is not picked, the gradient difference of f(w; z) and f(w; z′) is ∇f(w, z)−∇f(w′, z′) = A[w − w′] and in case different entry zi, zi is picked, ∇f(w, z)−∇f(w′, z′) = A[w − w′] + [xi − x′i] Since ∆0 = 0, one can inductively show ∆t = θt[xi − x′i] where θt > 0. Since SGD selects zt = z′t with probability 1− 1n and a different entry with probability 1 n we have the following dynamic:
∆t+1 =  (I − αtA)[wt − w ′ t] with prob. 1− 1n
(I − αtA)[wt − w′t] + αt[xi − x′i] with prob 1/n.
E‖∆t+1‖ =E [‖∆t+1‖|Index i is not selected]P[Index i is not selected] + E [‖∆t+1‖|Index i is selected]P[Index i is selected]
=(1− 1 n )‖(I −A)[wt − w′t]‖+ 1 n ‖(I −A)[wt − w′t] + αt[xi − x′i]‖ =(1− 1 n )(1− αtλxx′)θt‖xi − x′i‖+ 1 n [1− αtλxx′θt + αt]‖xi − x′i‖ =(1− αtλxx′)E‖∆t‖+ αt n ‖xi − x′i‖
Lemma 2 (Lower bound on divergence). Let ∆t be wt−w′t, αt be the step size of SGD and ∆0 = 0. Suppose [xi − x′i]/‖xi − x′i‖ is an eigenvector of A where A[xi − x′i] = λxx′ [xi − x′i]. Running SGD on f(w, S), we have:
E‖∆T ‖ ≥ ‖xi − x′i‖
n
T−1∑ t=1 T−1∏ τ=t+1 αt(1− ατλxx′)
Proof: By Lemma 1 we have
E‖∆T ‖ = E‖(I − αT−1A)∆T−1 + αT−1 n [xi − x′i]‖
= (1− αT−1λxx′)E‖∆T−1‖+ αT−1 n ‖xi − x′i‖
= ‖[xi − x′i]‖ 1
n T−1∑ t=1 αt T−1∏ τ=t+1 (1− ατλxx′)
Theorem 1. Let wt, w′t be the outputs of SGD on twin datasets S, S′ respectively, ∆t be wt−w′t and αt be the step size of SGD. There exists a function f which is convex and β-smooth, L-Lipschitz on domain of wt, w′t and twin datasets S, S ′ such that the divergence of the two SGD outputs satisfies:
E‖∆T ‖ ≥ L
2n ∑T t=1 αt, and εstab ≥ L 2n ∑T t=1 αt. (6)
Proof We set xi = v, yi = 0.5, x′i = −v, y′i = 0.5. The proof is constructive. Let f(w, z) = 1 2w >Aw − yx. The function is β smooth and convex by setting β = ‖A‖ and u>Au ≥ 0 for all u. We set S \ {zi} = S′ \ {z′i} to lie in the range of A, where A is a PSD matrix which is not full-rank. We further set xi, x′i to lie in the null space of A so that Av = 0. The lower bound ‖∆‖T follows from Lemma 2 from the fact that ∆0 = 0. Since w>Aw = w′>Aw′, εstab = supz E|f(wT , z)− f(w′T , z)| ≥ E|v>[wT − w′T ]| ≥ 1n ∑T t=1 αt.
The last part we show for any sequence wt generated from stochastic gradient descent step using data set S will have a constant gradient thus the Lipshitzness will follow. Let U be the range of A (so any u ∈ U satisfy uAu > 0. Pick γ so that u>Au ≥ γ > 0 holds for all u ∈ U . For all u, ‖w>t+1u‖ ≤ ‖(I−αtA)w>t u+αz>u‖ ≤ (1−αtγ)‖w>t u‖+α. This implies ‖w>t u‖ ≤ 1γ . Now we bound gradient ‖∇fw(wt, z)‖ = ‖Awt−x‖ ≤ |v>Aw|+|v>yx|+|u>Aw|+|u>yx| ≤ 1+ βγ . This implies that the function is L-Lipschitz with L = 1 + βγ . By setting β = 2γ the proof follows.
Theorem 2. Suppose loss function f(w, z) of the form f(w, S) = 1n ∑n j=1 fyj (w
>xj) and fy(w>x) satisfies (1) |f ′y(·)| ≤ L , (2) 0 < γ ≤ f ′′y (·) ≤ β, (3) ‖x‖ ≤ R and (4) , S′ are ξ-self correlated. Let wt, w′t be the outputs of SGD on twin datasets S, S
′, ∆t := wt − w′t and α ≤ 1β is the step size of SGD. Then,
E‖∆T ‖ ≤ 4LR
ξγn
Proof: For simplicity we omit the dependence of f on yj so that fyj (w>xj) = f(w, zj). Note that the gradient of the loss function is∇fyj (w>t xj) = f ′yj (w > t xj)xj and the Hessian is∇2fyj (w>t xj) = f ′′yj (w > t xj)xjx > j . The stochastic gradient step of fyj (w > t xj) is
wt+1 = wt − αtf ′yj (w > t xj)xj .
The dynamics of the divergence can be described as:
E1:t+1‖∆t+1‖ = E1:t‖ 1
n ∑ j 6=i ∆t − αt[f ′yjyj(w > t xj)− f ′yj (w ′> t xj)]xj
1 n (∆t − αt[f ′yi(w > t xi)xi − f ′y′i(w ′> t xi)x ′ i])‖
(7)
Note that [f ′yjyj(w > t xj) − f ′yj (w ′> t xj)]xj can be rewritten as f ′′ yj (w θj t > xj)xjx > j ∆t where w θj = (1− θj)wt + θjw′t, 0 < θj < 1. Similarly we can also rewrite f ′yi(w > t xi)xi − f ′y′i(w ′> t xi)x ′ i as
f ′yi(w > t xi)xi − f ′y′i(w ′> t xi)x ′ i
= 1
2 {f ′yi(w > t xi)xi − f ′yi(w ′> t xi)xi}
+ 1
2 {f ′y′i(w > t x ′ i)x ′ i − fy′i(w ′> t x ′ i)x ′ i}
+ 1
2 {f ′yi(w ′> t xi) + f ′ yi(w > t xi)}xi
− 1 2 {f ′y′i(w > t x ′ i) + fy′i(w ′> t x ′ i)}x′i = 1
2 f ′′yi(w θi t
> xi)xix > i ∆t + 1
2 f ′′y′i(w θ′i t > x′i)x ′ ix ′ i > ∆t
+ 1
2 {f ′yi(w ′> t xi) + f ′ yi(w > t xi)}xi
− 1 2 {f ′y′i(w > t x ′ i) + fy′i(w ′> t x ′ i)}x′i
(8)
Thus equation equation 7 can be written as
E1:t+1‖∆t+1‖ = E1:t‖(I − αt 2n n∑ j=1 f ′′yj (w θi t > xi)xix > i )∆t
+ αt 2n {f ′yi(w ′> t xi) + f ′ yi(w > t xi)}xi − αt 2n {f ′y′i(w > t x ′ i) + fy′i(w ′> t x ′ i)}x′i‖
By the ξ-self correlated assumption and lettingH = 1n ∑ xj∈S xjx > j andH′ = 1n ∑ xj∈S′ xjx > j , we have:
E‖∆t+1‖ ≤ E‖(I − αtγ
2 {H+H′})∆t‖+
αtL
n ‖xi‖+
αtL
n ‖x′i‖
≤ (1− αtξγ 2 )E‖∆t‖+ 2αtLR n .
(9)
The first inequality follows from the fact that f ′′(·) ≥ γ and xjx>j s are all PSD. The second inequality follows from the fact that ∆t ∈ Span{x1, .., xn}. Fix αt = α and the theorem follows. Our next two lemmas are used in the proof of Theorem 3.
Lemma 3. Suppose xt0 ≥ 0, xt+1 = (1 + a0.99t )xt + y t , we have xT ≥ y( T t0 )a if a > 0 is a sufficiently small constant.
Proof: In the proof we use following inequality:
ea ≤ 1 + a 0.99 ≤ e a0.99
where a > 0 is a sufficiently small constant.
xT = T∑ t=t0+1 y t T∏ s=t+1 (1 + a 0.99s ) + x0 T∏ t=t0+1 (1 + a 0.99s )
≥ T∑
t=t0+1
y t exp
( a
T∑ s=t+1 1 s
)
≥ T∑
t=t0+1
y t exp (a log(T/t))
≥ yT a T∑
t=t0+1
1
t1+a ≥ y ( T
t0
)a
(10)
Lemma 4. There exists a function f which is non-convex and β-smooth, twin datasets S, S′ and constant a > 0 such that the following holds: if SGD is run using step size αt = a0.99βt for 1 ≤ t < T , and wt, w′t are the outputs of SGD on S and S ′, respectively, and ∆t := wt − w′t, then:
∀1 ≤ t0 ≤ T, E [‖∆T ‖|∆t0 6= 0] ≥ 1
2n
( T
t0
)a (11)
Proof: Consider the function f in Equation 1, and chooseA to have positive and negative eigenvalues. We set the minimum eigenvalue of A equal to −β and all other eigenvalues with absolute value at most β. We select twin datasets for such A as follows. We set all elements in S \ {xi} = S′ \ {x′i} to lie in the column space of A. Also, ∀j 6= i, choose xj such that x>j Axj > 0, and choose any yj between 0 and 1.
Let v be such that v>Av = −β and ‖v‖ = 1. Finally, let xi = v, yi = 0.5, x′i = −v, y′i = 0.5. In this setting, one observes that the divergence ∆t follows the following dynamic:
∆t+1 =  (I − αtA)∆t with prob. 1− 1 n
(I − αtA)∆t + αt2 [xi − x ′ i] with prob 1/n.  . We first observe that ∆t := wt − w′t is of the form vθt, where θt > 0. This can be shown using induction. Let τ be the first time that xi, x′i are picked, we have ∆τ+1 = αt 2 [xi − x ′ i] = vατ . The iterative step of ∆t+1 and ∆t implies that ∆t+1 = vθt+1 where θt+1 = (1 +αtβ)θt with probability (1− 1n ) and θt+1 = (1 + αtβ)θt + αt with probability 1 n .
The above construction then yields: E1:t+1 [‖∆t+1‖|∆t0 6= 0] =E1:t [(
1− 1 n
) ‖(I − αtA)∆t‖+ 1
n ‖(I − αtA)∆t + αtv‖ ] = ‖v‖E1:t [( 1− 1
n
) (1 + αtβ)θt + 1
n ((1 + αtβ)θt + αt) ] = ‖v‖E1:t [ [(1 + αtβ)θt] +
αt n ] = (1 + a
0.99t )E1:t[‖∆t‖|∆t0 6= 0] + αt n ‖v‖
(12)
Now apply Lemma 3, with xt = E[||∆t|||∆t0 6= 0] and y = a||v|| 0.99βn . This gives us that xT ≥
a||v|| 0.99βn (T/t0) a = a0.99βn (T/t0) a, since ||v|| = 1.
Finally, the claimed bound follows by setting the minimum eigenvalue β = a0.99 .
Theorem 3. There exists a function f which is non-convex and β-smooth, twin datasets S, S′ and constants a s.t. the following holds: if SGD is run using step size αt = a0.99βt for 1 ≤ t < T , and wt, w ′ t are the outputs of SGD on S and S
′, respectively, and ∆t := wt − w′t, the divergence of SGD after T rounds (T > n) satisfies:
E‖∆T ‖ ≥ T a
3n1+a (13)
Proof: The proof is based on Theorem 4 plus the idea of a “burn-in” period. We have:
E‖∆T ‖ = E[‖wt − w′t‖|∆n = 0]P[∆n = 0] + E[‖wt − w′t‖|∆n 6= 0]P[∆n 6= 0] ≥ E[‖wt − w′t‖|∆n 6= 0]P[∆n 6= 0]
= ( 1− ( 1− 1
n )n) T a n1+a ‖xi − x′i‖
≥ T a
3n1+a ‖xi − x′i‖
(14)
Lemma 5. (Hardt et al., 2016) Assume f is β-smooth and L-lipschitz. Let wt, w′t be outputs of SGD on twin datasets S, S′ respectively after t iterations and let ∆t := [wt − w′t] and δt = E‖∆t‖. Running SGD on f(w;S) with step size αt = aβt satisfies the following conditions:
• The SGD update rule is a (1 + αtβ)-expander and 2αtL-bounded.
• E[‖∆t‖|∆t−1] ≤ (1 + αtδ) ‖∆t−1‖+ 2αtLn .
• E[‖∆T ‖|∆tk = 0] ≤ ( T tk−1 )a 2L n .
Theorem 4 ( Permutation). Assume f is β-smooth and L-lipschitz. Running T (T > n) iterations of SGD on f(w;S) with step size αt = aβt , the stability of SGD satisfies:
E‖∆T ‖ ≤ 2LT a
n1+a , εstab ≤
2L2T a
n1+a (15)
Proof. Let H = t represents the event that the first time the SGD pick the different entry is at time t:
E‖∆T ‖ = E[‖∆T ‖|H ≤ n]P[H ≤ n] + E[‖∆T ‖|H > n]P[H > n]︸ ︷︷ ︸ 0(permutation)
≤ 1 n n∑ t=1 E[‖∆T ‖|H = t]
≤ ∗
1
n n∑ t=1 ( T t )a 2L n
≤ 2LT a
n2 ∫ n t=1 1 ta dt
≤ 2LT a
n1+a
(16)
The inequality (∗) derived by applying Lemma 5.
Lemma 6. Let wt, w′t be outputs of SGD on twin datasets S, S′ respectively after t iterations and let ∆t := wt − w′t. Suppose that tk = ctk−1. Then the following conditions hold:
• P[∆tk−1 = 0|∆tk 6= 0] ≤ nn+tk−1 .
• P[∆tk−1 6= 0|∆tk 6= 0] ≤ 1c ( 1 + tkn ) .
• E[‖∆T ‖|∆tk 6= 0] ≤ E[‖∆T ‖|∆tk−1 6= 0] 1c ( 1 + tkn ) + ( T tk−1 )a 2L n .
Proof. In the proof we will use the following inequality with r ≥ 1: n− r n ≤ (1− 1 n )r ≤ n n+ r
i):
P[∆tk−1 = 0|∆tk 6= 0] = P[∆tk−1 = 0,∆tk 6= 0]
P[∆tk 6= 0]
= (1− 1/n)tk−1 1− (1− 1/n) tk−tk−1
1− (1− 1/n)tk
≤ (1− 1/n)tk−1 ≤ n n+ tk−1
(17)
ii):
P[∆tk−1 6= 0|∆tk 6= 0] = P[∆tk 6= 0,∆tk−1 6= 0]
P[∆tk 6= 0]
= P[∆tk−1 6= 0] P[∆tk 6= 0] = 1− (1− 1/n)tk−1 1− (1− 1/n)tk
≤ 1− nn+tk−1 1− n−tkn ≤ tk−1 tk (1 + tk n ) = 1
c (1 + tk n )
(18)
iii): By applying i) and ii) in the decomposition of E[∆T |∆tk 6= 0] we have
E[‖∆T ‖|∆tk 6= 0] ≤ E[‖∆T ‖|∆tk−1 6= 0]P[∆tk−1 6= 0|∆tk 6= 0] + E[‖∆T ‖|∆tk−1 = 0]P[∆tk−1 = 0|∆tk 6= 0]
≤ E[‖∆T ‖|∆tk−1 6= 0] tk−1 tk (1 + tk n )
+ ( T
tk−1 )a
2L
n+ tk−1
= 1
c (1 + tk n )E[‖∆T ‖|∆tk−1 6= 0]
+ ( T
tk−1 )a
2L
n+ tk−1
(19)
where the last inequality uses the fact that E[‖∆T ‖|∆tk = 0] ≤ ( T tk−1 )a 2L n .
Theorem4b (Uniformly Independent) Assume f is β-smooth and L-lipschitz. Running T (T > n) iterations of SGD on f(w;S) with step size αt = aβt , the stability of SGD satisfies:
E‖∆T ‖ ≤ 16 log(n)L T a
n1+a ; εstab ≤ 16 log(n)L2
T a
n1+a (20)
Proof. We first decompose ∆T as follows by selecting tk = n:
E‖∆T ‖ =E[‖∆T ‖|∆tk = 0]P[∆tk = 0]︸ ︷︷ ︸ Term 1≤ 2LTa
n1+a (Lemma 5)
+E[‖∆T ‖|∆tk 6= 0]P[∆tk 6= 0]︸ ︷︷ ︸ Term 2≤ 11L log(n)T a
n1+a
(21)
Term 1 is easily bounded by applying Lemma 5 with αt = atβ . To bound Term 2, plug in P[∆tk 6= 0] = 1 − (1 − 1/n)tk ≤ tkn and recursively apply point (iii) from Lemma 6 by setting ti+1 = cti. We get:
E[‖∆T ‖|∆tk 6= 0]P[∆tk 6= 0]
≤ 2L n tk n k−1∑ i=1 ( T ti )a n n+ ti k−1∏ τ=i+1 (1 + tτ+1 n ) tτ tτ+1
≤ 2L n k−1∑ i=1 ( T ti )a ti+1 n+ ti exp( k−1∑ τ=i+1 tτ+1 n )
≤ 2cL n exp
( c
c− 1 ) k−1∑ i=1 ( T ti )a ti n+ ti
≤ 2cLT a
n exp
( c
c− 1 ) k−1∑ i=1 t1−ai n
≤ 2L log(n)T a n1+a ca log c exp
( c
c− 1 ) ≤ 11 log(n)LT a
n1+a
(22)
In the second and third inequality we use the fact that 1 + x ≤ exp(x) and ti+1 = cti to get∏k−1 τ=i+1(1 + tτ+1 n ) ≤ exp( ∑k−1 τ=i+1 tτ+1 n ) ≤ exp ( c c−1 ) . The last inequality is derived by picking c = 4 .
Theorem 5. Let wt, w′t be the outputs of SGD on twin datasets S, S′, and let ∆t := wt − w′t. There exists a function f which is non-convex and β-smooth, twin sets S, S′ and constants a, γ such that the divergence of SGD after T rounds (T > n) using constant step size α = a0.99γ satisfies:
E‖∆T ‖ ≥ 1
n2 eaT/2 (23)
Proof: The proof is similar to Theorem 3. Since ∆t ∈ Span{xi − x′i}, we have:
E‖∆t+1‖ ≥ (1− 1
n )(1 + αtβ)E‖∆t‖+ αt n ‖xi − xi‖
Suppose t0 is the hitting time when ‖∆t0‖ > 0 and ‖∆t0−1‖ = 0 ,‖∆T ‖ ≥ ‖xi−x′i‖ 3n e a(T−t0)/2.
E‖∆T ‖ = E[‖wt − w′t‖|∆1 = 0]P[∆1 = 0] + E[‖wt − w′t‖|∆1 6= 0]P[∆1 6= 0] ≥ E[‖wt − w′t‖|∆1 6= 0]P[∆1 6= 0]
= 1 n ( ‖xi − x′i‖ n eaT/2) = ‖xi − x′i‖
n2 eaT/2.
(24)
Theorem 6. Given a set S and a β-smooth and L-Lipschitz loss funtion f , suppose SGD with a fixed step size α ≤ σ 2
2γL2 reaches point w0 which is close to a local minimum w ∗ in a (σ, γ)-Hessian
contractive region: ‖w0−w∗‖ ≤ σ with large enough radius so that σ > 12Lγ , then we have ∀T ≥ 1, ‖wT − w∗‖ ≤ σ.
Proof: LetHwt,w∗,θ = 1n ∑ zj∈S ∇ 2 wf(θwt + (1− θ)w0, zj) We derive that:
‖wt+1 − w0‖2
=‖wt − w0 − α∇wf(w, z)‖2
=‖wt − w0‖2 + α2‖∇wf(ws, z)‖2 − 2α∇wf(wt, z)>[wt − w0] =‖wt − w0‖2 + α2‖∇wf(ws, z)‖2 − 2α∇wf(w0, S)>[wt − w0] − 2α[∇wf(wt, z)−∇wf(wt, S)]>[wt − w0] − 2α[∇wf(wt, S)−∇wf(w0, S)]>[wt − w0]
≤‖wt − w0‖2 + α2L2 − 2α[wt − w0]>Hwt,w∗,θ[wt − w0] + 6αLσ
(25)
Due to the fact that wt − w0 ∈ Span{∇wf(w0, z), ...,∇wf(wt−1, z)}, we have
‖wt − w0‖2 + α2L2 − 2α[wt − w0]>Hwt,w∗,θ[wt − w0] + 6αLσ ≤(1− 2αγ)‖wt − w0‖2 + α2L2 + 6αLσ
(26)
This implies ‖wt − w0‖ ≤ σ for all t.

heading: B EMPIRICAL SUPPORT FOR THEOREM 6
text: In order to empirically support Theorem 6, we ran the follow experiment: We started with a fullytrained model w∗, and generated random perturbations w̃ = w∗ + ν where ν ∼ N (0, σ2). We then trained each w̃ until convergence w̃∗, and computed the normalized distance ‖w̃∗ − w∗‖/‖w∗‖. To match Theorem 6, this distance should be no more than 2‖w̃∗ − w∗‖/‖w∗‖, i.e., the trained weights w̃∗ after perturbing stay close to w∗, as in the conclusion of Theorem 6.
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 w̃ of the trained model weights w∗ and trained each for 50 more epochs, resulting in weights w̃∗. We used standard deviation σ ∈ {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 Table 2. 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.

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

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.

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