Year: 2021

Abstract:
We study the generalization of noisy stochastic mini-batch based iterative algorithms based on the notion of stability. Recent years have seen key advances in data-dependent generalization bounds for noisy iterative learning algorithms such as stochastic gradient Langevin dynamics (SGLD) based on (Mou et al., 2018; Li et al., 2020) and related approaches (Negrea et al., 2019; Haghifam et al., 2020). In this paper, we unify and substantially generalize stability based generalization bounds and make three technical advances. First, we bound the generalization error of general noisy stochastic iterative algorithms (not necessarily gradient descent) in terms of expected stability, which in turn can be bounded by the expected Le Cam Style Divergence (LSD). Such bounds have aO(1/n) sample dependence unlike many existing bounds with O(1/ √ n) dependence. Second, we introduce Exponential Family Langevin Dynamics (EFLD) which is a substantial generalization of SGLD and which allows exponential family noise to be used with gradient descent. We establish data-dependent expected stability based generalization bounds for general EFLD. Third, we consider an important new special case of EFLD: noisy sign-SGD, which extends sign-SGD by using Bernoulli noise over {−1,+1}, and we establish optimization guarantees for the algorithm. Further, we present empirical results on benchmark datasets to illustrate the our bounds are non-vacuous and quantitatively much sharper than existing bounds.

text: √ n) dependence. Second, we introduce
Exponential Family Langevin Dynamics (EFLD) which is a substantial generalization of SGLD and which allows exponential family noise to be used with gradient descent. We establish data-dependent expected stability based generalization bounds for general EFLD. Third, we consider an important new special case of EFLD: noisy sign-SGD, which extends sign-SGD by using Bernoulli noise over {−1,+1}, and we establish optimization guarantees for the algorithm. Further, we present empirical results on benchmark datasets to illustrate the our bounds are non-vacuous and quantitatively much sharper than existing bounds.

heading: 1 INTRODUCTION
text: Recent years have seen renewed interest and advances in characterizing generalization performance of learning algorithms in terms of stability, which considers change in performance of a learning algorithm based on change of a single training point (Hardt et al., 2016; Bousquet & Elisseeff, 2002; Li et al., 2020; Mou et al., 2018). For stochastic gradient descent (SGD), Hardt et al. (2016) established generalization bounds based on uniform stability (Hardt et al., 2016; Bousquet & Elisseeff, 2002), although the analysis needed rather small step sizes ηt = 1/t which is not useful in practice. While improving the analysis for SGD has remained a challenge, advances have been made on noisy SGD algorithms, especially stochastic gradient Langevin dynamics (SGLD) (Welling & Teh, 2011; Mou et al., 2018; Li et al., 2020), which adds Gaussian noise to the stochastic gradients of marginal variance σ2t . In parallel, there has been key developments on related information-theoretic generalization bounds applicable to SGLD type algorithms (Negrea et al., 2019; Haghifam et al., 2020; Xu & Raginsky, 2017; Russo & Zou, 2016; Pensia et al., 2018).
While these developments have led to major advances in analyzing generalization of noisy SGD algorithms, they each have certain limitations which leave room for further improvements. Using uniform stability, Mou et al. (2018) established a bound for SGLD of the form Kn √∑ t η 2 t /σ 2 t which depends on K, the global Lipschitz constant for the loss, and with step size ηt ≤ σt ln 2/K. The bound has a desirable dependency of O(1/n) on the samples, but has an undesirable dependence on K, and the step sizes, bounded by σt/K, are too small. Mou et al. (2018) also presented another bound which addresses some of these issues, but gets an undesirable O(1/ √ n) sample dependence. By building on the developments of Russo & Zou (2016); Xu & Raginsky (2017); Pensia et al. (2018), Negrea et al. (2019) made advances from the information theoretic perspective and established bounds for SGLD which have the desirable dependence on the norm of gradient incoherence, i.e., difference in gradients over different mini-batches, avoids dependence on Lipschitz constant K, and is applicable to unbounded sub-Gaussian losses, but have an undesirable O(1/ √ n) sample
dependence. Haghifam et al. (2020) made further advances on the problem from an information theoretic perspective based on the conditional mutual information framework of Steinke & Zakynthinou (2020) and obtained generalization bounds based on gradient incoherence with O(1/n) sample dependence, but their analysis holds for full batch Langevin dynamics, not mini-batch SGLD. Li et al. (2020) made advances on such bounds based on the notion of Bayes-stability, by combining ideas from PAC-Bayes bounds into stability, and established a bound of the form cn √∑ t η 2 t ge(t)/σ 2 t for bounded losses, where ge(t) is the expected gradient norm square at step t. While the bound avoids dependency on the Lipschitz constant K, the dependence on the gradient norm makes such bounds much weaker than the information theoretic bounds of Negrea et al. (2019); Haghifam et al. (2020) which depend on the norm of gradient incoherence, which are typically orders of magnitude smaller. Further, the analysis of Li et al. (2020) still needs small step sizes, bounded by σt/K.
In this paper, we build on the core strengths of such existing approaches, most notably the O(1/n) sample dependence of stability based bounds (Mou et al., 2018; Li et al., 2020) and the dependence on gradient incoherence for information theoretic bounds (Negrea et al., 2019; Haghifam et al., 2020), and develop a framework (Section 2) for developing generalization bounds for noisy stochastic iterative (NSI) algorithms. Our framework considers generalization based on the concept of expected stability, rather than uniform stability (Hardt et al., 2016; Bousquet & Elisseeff, 2002; Bousquet et al., 2020; Mou et al., 2018), which yields distribution dependent generalization bounds and avoids the worst-case setting of uniform stability. Building on Li et al. (2020), we show that expected stability of general NSI algorithms can be bounded by the expected Le Cam Style Divergence with dependence on parameter distributions from mini-batches differing by one sample. In Section 3, we introduce Exponential Family Langevin Dynamics (EFLD), a family of noisy gradient descent algorithms based on exponential family noise. Special cases of EFLD include SGLD and noisy versions of Sign-SGD or quantized SGD algorithms widely used in practice (Bernstein et al., 2018a;b; Jin et al., 2020; Alistarh et al., 2017)Our main result provides an expected stability based generalization bound applicable to any EFLD algorithm with a O(1/n) sample dependence and a dependence on gradient incoherence, rather than gradient norms. Existing generalization bounds for SGLD (Li et al., 2020; Negrea et al., 2019) usually use properties of the Gaussian distribution, and our analysis on EFLD illustrates that this was unnecessary. We also consider optimization guarantees for EFLD and establish such results for noisy Sign-SGD and SGLD. Through experiments on benchmark datasets (Section 4), we illustrate that our bounds are non-vacuous and quantitatively much sharper than existing bounds (Li et al., 2020; Negrea et al., 2019).
Related work. Uniform stability has been a classical approach for bounding generalization error (Bousquet & Elisseeff, 2002; Bousquet et al., 2020; Feldman & Vondrak, 2018; 2019), pioneered by Rogers & Wagner (1978); Devroye & Wagner (1979). Beyond the aforementioned work, there has been recent work on differential privacy that analyzes the uniform stability of differentially private SGD (DP-SGD) (Hardt et al., 2016; Bassily et al., 2020). Beyond uniform stability, informationtheoretic approaches (Russo & Zou, 2016; Xu & Raginsky, 2017) that bounds the generalization error by the mutual information between the algorithm input S and the algorithm output w, have been used for deriving generalization bounds for noisy iterative algorithms (Pensia et al., 2018; Bu et al., 2019). Along this line of literature, Negrea et al. (2019); Haghifam et al. (2020); Rodrı́guezGálvez et al. (2021) prove data-dependent generalization bounds dropping dependence on the Lipschitz constant. Further, tighter bounds (Haghifam et al., 2020; Zhou et al., 2021; Rodrı́guez-Gálvez et al., 2021; Neu, 2021; Hellström & Durisi, 2021) are proposed based on conditional mutual information (Steinke & Zakynthinou, 2020; Grünwald et al., 2021; Hellström & Durisi, 2020). Due to space limitations, an extended discussion of the related work is deferred to Appendix A.

heading: 2 GENERALIZATION BOUNDS WITH EXPECTED STABILITY
text: In the setting of statistical learning, there is an instance space Z , a hypothesis spaceW , and a loss function ` :W×Z 7→ R+. LetD be an unknown distribution ofZ and let S ∼ Dn be n i.i.d. draws from D. For any specific hypothesis w ∈ W , the population and empirical loss are respectively given by LD(w) , Ez∼D[`(w, z)], and LS(w) , 1n ∑n i=1 `(w, zi). For any distribution P over the hypothesis space, we respectively denote the expected population and empirical loss as LD(P ) , Ez∼DEw∼P [`(w, z)] , and LS(P ) , 1
n n∑ i=1 Ew∼P [`(w, zi)] . (1)
Consider a randomized algorithm A which works with S = {z1, . . . , zn} ∼ Dn and cre-
ates a distribution over the hypothesis space W . For convenience, we will denote the distribution as A(S). The focus of the analysis is to bound the generalization error of A defined as: gen(A(S)) , LD(A(S)) − LS(A(S)) . We will assume A is permutation invariant, i.e., the ordering of samples in S do not modify A(S), an assumption satisfied by most learning algorithms. We will focus on developing bounds for the expectation ES [LD(A(S)) − LS(A(S))], and discuss high-probability bounds in the Appendix B.

heading: 2.1 BOUNDS BASED ON EXPECTED STABILITY
text: We start our analysis by noting that the expected generalization error can be upper bounded by expected stability based on the Hellinger divergence (Sason & Verdu, 2016; Li et al., 2020): H2(P‖P ′) = 12 ∫ w ( √ p(w)− √ p′(w))2dw. Proposition 1. Let Sn ∼ Dn and let S′n be a dataset obtained by replacing zn ∈ Sn with z′n ∼ D. Let A(Sn), A(S′n) respectively denote the distributions over the hypothesis space W obtained by running randomized algorithm A on Sn, S′n. Assume that for Sn ∼ Dn,∀z ∈ Z , EW∼A(Sn)[`2(W, z)] ≤ c0/2, c0 > 0. With H(·, ·) denoting the Hellinger divergence, we have
|ESn∼Dn [LD(A(Sn))− LS(A(Sn))]| ≤ c0ESn∼DnEz′n∼D √ 2H2 ( A(Sn), A(S′n) ) . (2)
Remark 2.1. Proposition 1 does not need bounded losses. Just the second moment of `(W, z),W ∼ A(Sn), Sn ∼ Dn,∀z ∈ Z need to be bounded. The assumption is satisfied by bounded losses. It is instructive to compare the assumption to that in recent information theoretic bounds (Haghifam et al., 2020; Xu & Raginsky, 2017), where one assumes `(w, Z), Z ∼ D,∀w ∈ W to be sub-Gaussian. Remark 2.2. The bound in Proposition 1 is in terms of expected stability where we consider ES∼DnEz′n∼D[· · · ], an important departure from bounds based on uniform stability (Elisseeff et al., 2005; Bousquet & Elisseeff, 2002; Mou et al., 2018; Bousquet et al., 2020; Feldman & Vondrak, 2018; 2019) where one considers supS,S′∈Zn,|S\S′|=1[· · · ]. Replacing sup by E makes the bounds distribution dependent, and arguably leads to quantitatively tighter bounds.
Note that the Hellinger divergence can be bounded by the KL divergence. Proposition 2. For any distributions P and P ′, 2H2(P, P ′) ≤ min { KL(P, P ′), √ 1 2KL(P, P ′) } .

heading: 2.2 EXPECTED STABILITY OF NOISY STOCHASTIC ITERATIVE ALGORITHMS
text: We consider a general family of noisy stochastic iterative (NSI) algorithms. Given S ∼ Dn, such iterative algorithms have two additional sources of randomness in each iteration t: (a) a stochastic mini-batch of samples SBt , with |SBt | = b, drawn uniformly at random with replacement from S; and (b) noise ξt suitably included in the iterative update. Given a trajectory of past iterates W0:(t−1) = w0:(t−1), the new iterate Wt is drawn from a distribution PBt,ξt|w0:(t−1) overW:
Wt ∼ PBt,ξt|w0:(t−1)(W ) . (3)
We will drop the conditioning w0:(t−1) to avoid clutter in the sequel. Let PT , P ′T denote the marginal distributions over hypotheses w ∈ W after T steps of the algorithm based on Sn, S′n respectively. Further, let P0:(t−1) denote the joint distribution over W0:(t−1) = (W0, . . . ,Wt−1), and let Pt| ≡ PBt,ξt|w0:(t−1) compactly denote the conditional distribution on Wt conditioned on the trajectory W0:(t−1) = w0:t−1. Following (Negrea et al., 2019; Haghifam et al., 2020; Pensia et al., 2018), we use the following chain rule for KL-divergence: KL(PT ‖P ′T ) ≤ KL(P0:T ‖P ′0:T ) =∑T t=1 EP0:(t−1) [KL(Pt|‖P ′t|)]. Let S̄ ∼ D
n+1, and let Sn, S′n be size n subsets of S̄ such that Sn = {Z1, . . . , Zn−1, Zn} and S′n = {Z1, . . . , Zn−1, Z ′n}, where Z ′n = Zn+1. Let S0 = {Z1, . . . , Zn−1}. The algorithms we consider use a mini-batch of size b in each iteration uniformly sampled from n samples. Let the set of all mini-batch index sets be denoted by G. Let the set of all mini-batch index sets A drawn from S0 be denoted by G0. Note that |G0| = ( n−1 b ) . Let G1 denote the set of all mini-batch index setsB which includes the last sample, viz. zn for S with mini-batches and z′n for S ′ n. Note that |G1| = ( n−1 b−1 ) . Also note that |G0|+ |G1| = ( n−1 b ) + ( n−1 b−1 ) = ( n b ) = |G|.
Following Li et al. (2020), we can bound their conditional KL-divergences KL(Pt|‖P ′t|) in terms of a Le Cam Style Divergence (LSD). While the classical Le Cam divergence (Sason & Verdu,
2016) is LCD(P‖P ′) , 12 ∫ (dP−dP ′)2 dP+dP ′ (where dP denotes the density), our bounds in terms of
LSD(Pt||‖P ′t|) , ∫ (dPBt,ξt−dP ′Bt,ξt )2 dPAt,ξt , Bt ∈ G1, At ∈ G0. Note that PBt,ξt and P ′Bt,ξt represent the distribution of Wt for Sn and S′n respectively since the mini-batch SBt of Sn and S ′ n differs in the n-th sample. Putting everything together, we have the following LSD based bound. Lemma 1. Consider a noisy stochastic iterative algorithms of the form (3) with mini-batch size b ≤ n/2. Then, with c1 = √ 2c0 (with c0 as in Proposition 1), we have
|ESn [LD(A(Sn))−LSn(A(Sn))]| ≤ c1 b
n ESnEz′n √√√√√√ T∑ t=1 E W0:(t−1) E Bt∈G1 E At∈G0  ∫
ξt
( dPBt,ξt − dP ′Bt,ξt )2 dPAt,ξt dξt  . (4)
Remark 2.3. Li et al. (2020) essentially has this result for SGLD and inspired our work. Our proofs are significantly simpler and, more importantly, illustrates applicability to general noisy iterative algorithms of the form (3), not just SGLD with Gaussian noise as in Li et al. (2020). Remark 2.4. Note that the bound does not assume the loss to be bounded, depends on expectations over samples Sn, z′n, trajectories w0:(t−1), and mini-batches Bt, At. Further, the bound depends on the distribution discrepancy as captured by the expected LSD. Remark 2.5. The bound seems to worsen with b, the size of the mini-batch. As we shown in Section 3, the expected LSD term has a 1b2 dependence for the Exponential Family Langevin dynamics (EFLD) models we introduce, so the leading b is neutralized.

heading: 3 EXPONENTIAL FAMILY LANGEVIN DYNAMICS
text: In recent years, considerable advances have been made in establishing generalization bounds for stochastic gradient Langevin dynamics (SGLD) (Li et al., 2020; Pensia et al., 2018; Negrea et al., 2019; Haghifam et al., 2020). As an example of NSI algorithms of the form (3), SGLD adds an isotropic Gaussian noise at every step of SGD: wt+1 = wt− ηt∇`(wt, SBt) +N ( 0, σ2t Id ) , where ∇`(wt, SBt) is the stochastic gradient on mini-batchBt, ηt is the step size, and σ2t is noise vairance. In this paper, we introduce a substantial generalization of SGLD called Exponential Family Langevin Dynamics (EFLD) which uses general exponential family noise in noisy iterative updates of the form (3). In addition to being a mathematical generalization of the popular SGLD, the proposed EFLD provides flexibility to use noise gradient algorithms with different representation of the gradient, e.g., Bernoulli noise for Sign-SGD, discrete distribution for quantized or finite precision SGD, etc. (Canonne et al., 2020; Alistarh et al., 2017; Jiang & Agrawal, 2018; Yang et al., 2019).

heading: 3.1 EXPONENTIAL FAMILY LANGEVIN DYNAMICS (EFLD)
text: Exponential families (Barndorff-Nielsen, 2014; Brown, 1986; Wainwright & Jordan, 2008) constitute a large family of parametric distributions which include Gaussian, Bernoulli, gamma, Poisson, Dirichlet, etc., as special cases. Exponential families are typically represented in terms of natural parameters θ, and we consider component-wise independent distributions with scaled natural parameter θα = θ/α with scaling α > 0, i.e., pψ(ξ,θα) = exp(〈ξ,θα〉 − ψ(θα))π0(ξ) =∏p j=1 exp(ξjθjα − ψj(θjα))π0(ξj) , where ξ is the sufficient statistic, ψ(θα) = ∑p j=1 ψj(θjα) is
the log-partition function, and π0(ξ) = ∏p j=1 π0(ξj) is the base measure. Note that α = 1 gives the canonical form of the exponential family distributions. For general scaling α > 0, for some cases the base measure π0 may depend on the scaling, i.e., π0,α. A scaling α > 0 is valid as long as exp(〈ξ,θα〉 is integrable, i.e., ∫ ξ
exp(〈ξ,θα〉π0(ξ)dξ < ∞. Further, ψ is a smooth function by construction (Barndorff-Nielsen, 2014; Banerjee et al., 2005; Wainwright & Jordan, 2008) and the smoothness of ψ implies∇2ψ(θα) ≤ c2I. Exponential family Langevin dynamics (EFLD) uses noisy stochastic gradient updates similar to SGLD, but using exponential family noise rather than Gaussian noise as in SGLD. In particular, for mini-batch SBt , EFLD updates are as follows: with step size ρt > 0
wt = wt−1 − ρtξt , ξt ∼ pψ(ξ;θBt,αt) , (5) where pψ(ξ;θBt,αt) = exp(〈ξ,θBt,αt〉−ψ(θBt,αt))π0(ξ) , θBt,αt ,
θBt αt = ∇`(wt−1, SBt) αt . (6)
For EFLD, the natural parameter θBt,αt at step t is simply a scaled version of the mini-batch gradient ∇`(wt−1, SBt). We first show that EFLD becomes SGLD when the exponential family is Gaussian, and becomes a noisy version of sign-SGD (Bernstein et al., 2018a;b) when the exponential family is Bernoulli over {−1,+1}. More details and examples are in Appendix C.1. Example 3.1 (SGLD). SGLD uses scaled Gaussian noise with ψ(θ) = ‖θ‖22/2, αt = √ σt/ηt, so that pψ(ξ;θBt,αt) = N (θBt , α2t Id). By taking ρt = √ ηtσt, the update (5) based on ρtξt is distributed as N (ρtθBt , ρ2tα2t Id) = N (ηt∇`(wt−1, SBt), σ2t Id). Thus the EFLD update reduces to the SGLD update: wt = wt−1 − ηt∇`(wt−1, SBt) +N ( 0, σ2t Id ) . Example 3.2 (Noisy Sign-SGD). By taking ρt = ηt and component-wise ξj ∈ {−1, 1}, π0(ξj) = 1, ψ(θ) = log(exp(−θ)+exp(θ)) in exponential family update equation (5), the j-th component of exponential family distribution pψ(ξ;θBt,αt) becomes pθBt,αt,j (ξj) = exp(ξjθBt,αt,j) exp(−θBt,αt,j)+exp(θBt,αt,j) . Thus, the EFLD update reduces to a noisy version of Sign-SGD: wt = wt−1 − ηtξt, ξt,j ∼ pθBt,αt,j (ξj), j ∈ [d], where θBt,αt = ∇`(wt−1, SBt)/αt is the scaled mini-batch gradient.

heading: 3.2 EXPECTED STABILITY OF EXPONENTIAL FAMILY LANGEVIN DYNAMICS
text: From Lemma 1, conditioned on a trajectory w0:(t−1), mini-batches SBt , SAt , we can get generalization bound by suitably bounding the Le Cam Style Divergence (LSD) given by: IAt,Bt =∫ ξt (dPBt,ξt−dP ′ Bt,ξt ) 2 dPAt,ξt dξt. For EFLD, the density functions dPBt,ξt are exponential family densities pψ(ξ;θBt,αt) as in (5)-(6), and we have the following bound on the per step LSD: Theorem 1. For a given set S̄ ∼ Dn+1 and wt−1 at iteration (t − 1), let ∆t|wt−1(S̄) = maxz,z′∈S̄ ‖∇` (wt−1, z)−∇` (wt−1, z′)‖2 . Further, for a c2-smooth log-partition function ψ, let the scaling αt|wt−1 be data-dependent such that α 2 t|wt−1 ≥ 8c2∆ 2 t|wt−1(Sn+1). Then, we have
IAt,Bt ≤ 5c2‖θBt,αt − θB′t,αt‖ 2 2 = 5c2 2α2t|wt−1 [∥∥∇` (wt−1, SBt)−∇` (wt−1, S′Bt)∥∥22] , (7) Note that SBt and S ′ Bt
only differ at samples zn and z′n. The above bound can now be directly applied to Lemma 1 to get expected stability based generalization bounds for any EFLD algorithm. Theorem 2. Consider an exponential family Langevin dynamics (EFLD) algorithm of the form (5)- (6) with a c2-smooth log-partition function ψ. Then, for mini-batch size b ≤ n/2, with c = c0 √ 5c2 (with c0 as in Lemma 1) and α2t| ≥ 8c2∆ 2 t|(Sn+1) (as in Theorem 1, with the conditioning on wt−1 hidden to avoid clutter), we have
|ES [LD(A(S))− LS(A(S))]| ≤ c 1
n E Sn+1 √√√√ T∑ t=1 E W0:(t−1) 1 α2t| [ ‖∇` (wt−1, zn)−∇` (wt−1, z′n)‖ 2 2 ] .
(8) Remark 3.1. Theorem 2 captures the generalization error of SGLD, which is a special case of EFLD. Our bound has the same dependence on n, T , step size ηt as the bound in Li et al. (2020). However, our bound is numerically sharper because we replace the gradient norms, i.e., 1 n ∑ z∈S ‖`(wt, z)‖ in Li et al. (2020) and with gradient discrepancy ‖∇`(wt, z) − ∇`(wt, z′)‖, which is quantitatively smaller than gradient norms as we show in the experiment section. The bound in Negrea et al. (2019) depends on gradient incoherence which is empirically smaller than gradient discrepancy as observed in the experiment section, their bound depends on 1/ √ n, which is worse than the 1/n dependence in our bound. Remark 3.2. EFLD can be extended to work with anisotropic noise by using θBt,αt = ∇`(wt−1, SBt) αt in (6) where αt ∈ Rp determines different scaling for each dimension and denotes Hadamard division. Theorems 1 and 2 can be extended to such anisotropic noise by using α-scaled norms for the gradient discrepancy, i.e., ‖g − g′‖22,α = ∑ j(gj − g′j)2/α2j . Remark 3.3. The condition on αt is a data-dependent quantity, which can be computed along the training process. It gives much more benign condition of the step size compared to those in the related work (Mou et al., 2018; Li et al., 2020, Hardt et al. 2016), which require step size being bounded by σt/L. However, the step sizes in Theorem 2 need to be bounded by σt/∆t(S̄), which is considerably more relaxed since ∆t(S̄) is much smaller than Lipschitz constant L, which is a uniform bound over the whole parameter space. Also, usually one would expect ∆t(S̄) to decrease as training proceeds since the gradients shrink as the loss function being minimized. Thus, the constraint on step size does not require the step sizes to be as small as σt/L.

heading: 3.3 PROOF SKETCHES OF MAIN RESULTS: THEOREMS 1 AND 2
text: We focus on Theorem 1. To avoid clutter, we drop the subscript t for the analysis and note that the analysis holds for any step t. When the density dPB,ξ = pψ(ξ;θB,α), by mean-value theorem, for each ξ, we have pψ(ξ;θB,α) − pψ(ξ;θB′,α) = 〈θB,α − θB,α,∇θ̃B,αpψ(ξ; θ̃B,α)〉, for some θ̃B,α = γξθB,α + (1− γξ)θ′B,α where γξ ∈ [0, 1]. Then,
IA,B = ∫ ξ ( pψ(ξ;θB,α)− pψ(ξ;θB′,α) )2 pψ(ξ;θA,α) dξ = ∫ ξ 〈θB,α − θ′B,α, ξ −∇θ̃B,αψ(ξ; θ̃B,α)〉 2 p2ψ(ξ; θ̃B,α) pψ(ξ;θA,α) dξ ,
since pψ(ξ; θ̃B,α) = exp(〈ξ, θ̃B,α〉 − ψ(θ̃B,α))π0(ξ).
Handling Distributional Dependence of θ̃B . Note that we cannot proceed with the analysis with the density term depending on θ̃B,α since θ̃B,α depends on ξ. So, we first bound the density term depending on θ̃B,α in terms of exponential family densities with parameters θB,α and θB,α using c2-smoothness of ψ.
Lemma 2. For some γξ ∈ [0, 1], θ̃B,α = γξθB,α + (1− γξ)θ′B,α, we have exp [ 〈ξ, θ̃B,α〉 − ψ(θ̃B,α) ] max ( exp [ 〈ξ,θB,α〉 − ψ(θB,α) ] , exp [〈ξ,θB′,α〉 − ψ(θB′,α)]
) ≤ exp [c2‖θB,α − θB′,α‖22] . Bounding the Density Ratio. Next we focus on the density ratio p2ψ(ξ, θ̃B,α)/pψ(ξ;θA,α). By Lemma 2, it suffices to focus on p2ψ(ξ,θB,α)/pψ(ξ;θA,α) or the equivalent term for θB′,α. We show that the density ratio can be bounded by another exponential family with parameters (2θB,α−θA,α). Lemma 3. For any ξ, we have exp [〈ξ, 2θB,α〉 − 2ψ(θB,α)] exp [〈ξ,θA,α〉 − ψ(θA,α)] ≤ exp [ 2c2‖θB,α − θA,α‖22 ] exp [〈ξ, (2θB,α − θA,α〉 − ψ(2θB,α − θA,α)] .
The analysis for the term p2ψ(ξ,θB′,α)/pψ(ξ;θA,α) is exactly the same.
Bounding the Integral. Ignoring multiplicative terms which do not depend on ξ for the moment, the analysis needs to bound an integral term of the form ∫ ξ 〈θB,α − θ′B,α, ξ − ∇ψ(ξ; θ̃B,α)〉2 pψ(ξ; 2θB,α − θA,α)dξ, and a similar term with p2ψ(ξ; 2θB′,α − θA,α). First, note that ∇ψ(ξ; θ̃B,α) = µ̃B,α, the expectation parameter for pψ(ξ; θ̃B,α) Wainwright & Jordan (2008); Banerjee et al. (2005). The integral, however, is with respect to pψ(ξ; 2θB,α − θA,α). We handle this discrepancy by using ξ − ∇ψ(ξ; θ̃B,α) = (ξ − E[ξ]) + (E[ξ] − ∇ψ(ξ; θ̃B,α)), and decomposing as sum-of-squares. Quadratic form for the first term yields the covariance E[(ξ − E[ξ])(ξ − E[ξ])T ] = ∇2ψ(θ2θB,α−θA,α) ≤ c2I, by smoothness. The second term depends on the difference of gradients∇ψ(2θB,α− θA,α)−∇ψ(θ̃B,α) which, using smoothness and additional analysis, can be bounded by the norm of (θB,α−θA,α). All the pieces can be put together to get the bound in Theorem 1, which when used in Lemma 1 yields Theorem 2.

heading: 3.4 OPTIMIZATION GUARANTEES FOR EFLD
text: We now establish optimization guarantees for two examples of EFLD, i.e., Noisy Sign-SGD with Bernoulli noise over {−1,+1} and SGLD with Gaussian noise. Noisy Sign-SGD. For mini-batch Bt and scaling αt, mini-batch Noisy Sign-SGD updates the parameters as wt = wt−1 − ηtξt, where each component j ∈ [d]
ξt,j ∼ pθBt,αt,j (x) = exp(xθBt,αt,j)
exp(−θBt,αt,j) + exp(θBt,αt,j) , x ∈ {−1,+1} (9)
where θBt,αt = ∇`(wt−1, SBt)/αt is the scaled mini-batch gradient. The full-batch version uses parameters EBt [θBt,αt ] = ∇LS(wt−1) For the optimization analysis, we assume that the loss is smooth and mini-batch gradients are unbiased, symmetric, and sub-Gaussian.
Assumption 1. The loss function LS satisfies: for all w and w′, for some non-negative constant ~K := [K1, . . . ,Kd], we have LS(w) ≤ LS(w′) +∇LS(w′)T (w −w′) + 12 ∑ iKi(wi −w′i)2. Assumption 2. Given wt−1, the mini-batch gradient ∇`(wt−1, SBt) is (a) unbiased, i.e., EBt|wt−1∇`(wt−1, SBt) = ∇LS(wt−1); (b) symmetric, i.e., the density p(x) of x ≡ ∇`(wt−1, SBt) is symmetric around its expectation LS(wt−1): p(x) = p(2∇LS(wt−1) − x) and (c) sub-Gaussian, i.e., for any λ > 0, any v s.t. ‖v‖2 = 1, EBt|wt−1 expλ〈v,∇`(wt−1, SBt) − ∇LS(wt−1)〉 ≤ exp(λ2κ2t/2) for some constant κt > 0. Based on the assumptions, we have the following optimization guarantee for mini-batch noisy SignSGD. We defer the optimization guarantee for full-batch noisy Sign-SGD to Appendix D. Theorem 3. Under Assumption 1 and 2, for mini-batch noisy Sign-SGD with step size ηt = 1/ √ T ,
αt satisfying c ≥ αt ≥ max[ √
2κt, 4‖∇LS(wt−1)‖∞], we have for any S and any initialization w0
E
[ 1
T T∑ t=1 ‖∇LS(wt)‖22
] ≤ 4c√
T
( LS(w0)− LS(w∗) + 1
2 ‖ ~K‖1
) , (10)
where the expectation is taken over the randomness of algorithm.
SGLD. We acknowledge that the following optimization result of SGLD exists in various forms, as noisy gradient descent algorithms have been studied in literature such as differential privacy, where SGLD can be viewed as DP-SGD (Bassily et al., 2014; Wang & Xu, 2019) and the proof technique boils down to bounding the stochastic variance of the noisy gradient (Shamir & Zhang, 2013). Theorem 4. Under Assumption 1 and 2, with Ki = K,∀i ∈ [d], for any S, SGLD (EFLD with step size ρt = √ ηtσt, αt = √ σt/ηt), |Bt| = b, and ηt = 1√T , can achieve
1
T T∑ t=1 E‖∇LS(wt)‖2 ≤ O ( 1√ T ) +O ( K p ∑T t=1 α 4 t + log T√ T ) , (11)
where the expectation is over the randomness of the algorithm.
The error rate of SGLD depends on the noise variance αt. One can choose a decaying noise variance such as αt = 1/ 4 √ t to guarantee the convergence. Then the rate will become O(log T/ √ T ). We note that similar to the optimization guarantees of DP-SGD, the convergence rate depends on the dimension of the gradient p due to the isotropic Gaussian noise. Special noise structures such as anisotropic noise that aligned with the gradient structure can reduce the dependence on dimension (Kairouz et al., 2020; Zhang et al., 2021; Asi et al., 2021; Zhou et al., 2020).

heading: 4 EXPERIMENTS
text: In this section, we conduct a series of experiments to evaluate our generalization error bounds. For SGLD, we aim to compare the proposed bound in Theorem 2 with existing bounds in Li et al. (2020), Negrea et al. (2019), and Rodrı́guez-Gálvez et al. (2021) for various datasets. Note that the bound presented in Rodrı́guez-Gálvez et al. (2021) is an extension of that in Haghifam et al. (2020) from full-batch setting to mini-batch setting . We also evaluate the optimization performance of proposed Noisy Sign-SGD by comparing it with the original sign-SGD (Bernstein et al., 2018a) and present the corresponding generalization bound in Theorem 2.
The details of our model architectures, learning rate scheduling, hyper-parameter selections and additional experimental results can be found in Appendix E. We acknowledge that we did not achieve the state-of-the art predictive performance, mainly due to the simplicity of our model architectures. With more complex model and further tuning, the prediction results could be improved.

heading: 4.1 STOCHASTIC GRADIENT LANGEVIN DYNAMICS
text: Comparison with existing work. We have derived theoretical generalization error bounds that depend on the data-dependent quantity gradient discrepancy, i.e., ‖∇` (wt, zn)−∇` (wt, z′n)‖ 2 2. Existing bounds in Li et al. (2020) and Negrea et al. (2019) have also improved the Lipschitz constant in Mou et al. (2018) to a data-dependent quantity. As shown in Figure 1 (a)-(d), by combining with the empirical training error, all four generalization error bounds can be used to bound the empirical test error, but our bound is able to generate a much tighter upper bound. Such difference is mainly due to the fact that we replace the squared gradient norm in Li et al. (2020), the squared norm of
gradient incoherence in Negrea et al. (2019), and that of two-sample incoherence in Rodrı́guezGálvez et al. (2021) with the gradient discrepancy. Results in Figure 1 (e)-(h) show that our bounds are much sharper than those of Li et al. (2020) because our gradient discrepancy (Figure 1 (i)-(l)) is usually 2-4 order of magnitude smaller than the squared gradient norms appeared in Li et al. (2020). Our bounds are also sharper than those of Negrea et al. (2019) and Rodrı́guez-Gálvez et al. (2021) due to an improved dependence on n from an order of 1/ √ n to 1/n. Note that, even though the gradient incoherence in Negrea et al. (2019) is about 1 to 2 order of magnitude smaller than the gradient discrepancy for simple problems such as MNIST and Fashion-MNIST, the difference between the gradient incoherence and our gradient discrepancy reduces as the problem becomes harder (see results for CIFAR-10 in Figure 1(j)).
Effect of Randomness. Motivated by Zhang et al. (2017), we train CNN with SGLD on a smaller subset of MNIST dataset (n = 10000) with randomly corrupted labels. The corruption fraction varies from 0% (without label corruption) to 60%. As shown in Figure 2 (d), for long enough training time, all experiments with different level of label randomness can achieve almost zero training error. However, the one with higher level of randomness has higher generalization/test error (Figure 2 (a) dashed lines). Our generalization bound also becomes larger as the randomness increases since the corresponding gradient discrepancy increases.

heading: 4.2 NOISY SIGN-SGD
text: Optimization. Figure 3 (a)-(d) show the training dynamics of Noisy Sign-SGD under various selections of αt. As αt → 0, Noisy Sign-SGD matches both the optimization trajectory as well as the final test accuracy of the original Sign-SGD (Bernstein et al., 2018a). However, as αt increases, the probability of getting 1 approaches 0.5, and ξt approximates a uniform distribution. As a result, the corresponding Noisy Sign-SGD still converges, but the generalization performance is much worse.
Generalization Bound. Figure 3(e)-(f) show that our bound successfully bounds the empirical test error. The larger αt is the sharper the upper bound is. However, larger αt would slow down and adversely affect the optimization, e.g., Figure 3 (a)-(d) blue and orange lines. In practice, one needs to balance the optimization error and generalization by choosing a suitable scaling αt.

heading: 5 CONCLUSIONS
text: Inspired by recent advances in stability based and information theoretic approaches to generalization bounds (Mou et al., 2018; Pensia et al., 2018; Negrea et al., 2019; Li et al., 2020; Haghifam et al., 2020), we have presented a framework for developing such bounds based on expected stability for noisy stochastic iterative (NSI) learning algorithms. We have also introduced Exponential Family Langevin Dynamics (EFLD), a family of noisy gradient descent algorithms based on exponential family noise, including SGLD and Noisy Sign-SGD as two special cases. We have developed an expected stability based generalization bound applicable to any EFLD algorithm with a O(1/n) sample dependence and a dependence on gradient incoherence, rather than gradient norms. Further, we have provided optimization guarantees for EFLD and establish such results for Noisy Sign-SGD and SGLD. Our experiments on various benchmarks illustrate that our bounds are non-vacuous and quantitatively much sharper than existing bounds (Li et al., 2020; Negrea et al., 2019).

Review summaries:
This paper studies the generalization of iterative noisy learning algorithms. First of all, the authors provide a new generalization bound based on the Hellinger distance. This bound is basically based on the Hellinger distance between the output of the algorithm when one of the points in the training set is replaced with a fresh sample. They they use this bound to provide a generalization error guarantee for a broad class of noisy iterative algorithm which is defined as W_t = W_{t-1} - eta_t, where eta_t conditioned on the past iterated follows an exponential family distribution which for instance include SGLD. For this broad class, they provide a unified generalization bound that includes SGLD and Noisy Sign-SGD. Finally, the authors provide numerical study of their bound for several benchmarks and show that their bound achieves better estimate of generalization error. 

This paper provides generalization guarantees for exponential family sgld which is a more general setup than standard gaussian noise langevin dynamics as it allows for noise settings from any member of the exponential family. The authors point out that the setup they consider is a strict generalization of the standard langevin dynamics, and give another explicit example of sign sgd based generalization.   The authors use and show gradient discrepancy as opposed to gradient norms as used by Li et al, and gradient incoherence as used by Negrea et al. but the latter have 1/\sqrt{n}. Overall, from useful empirical observations it seems that the bounds proposed by the authors are tighter than these other bounds. 

The paper under review considers the generalized SDLG algorithms with exponential family noise introduced to the mini-batch gradient descent. The analysis of the error bound is based on the control of the expected stability. Experiments are provided to support the proposed EFLD SGD algorithms.

This paper improves generalization bounds based on the notion of stability. The notion of stability measures the effect of resampling a data point to the output of the algorithm. The paper improves known analyses in two directions:  - It proposes to use the notion of expected stability rather than uniform stability, which should to be tighter. - It generalizes the analysis to noises in an exponential family rather than Gaussian noise.