Stability based Generalization Bounds for Exponential Family Langevin Dynamics
Authors: Arindam Banerjee
Tiancong Chen
Xinyan Li
Yingxue Zhou
Venue: ICLR 2022 Submitted (2022)

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 a $O(1/n)$ sample dependence unlike many existing bounds with $O(1/\sqrt{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.

Under review as a conference paper at ICLR 2022
STABILITY BASED GENERALIZATION BOUNDS FOR EXPONENTIAL FAMILY LANGEVIN DYNAMICS
Anonymous authors Paper under double-blind review
ABSTRACT
We study the generalization of noisy stochastic mini-batch based iterative algo- rithms 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 al., 2020) and related approaches (Negrea al., 2019; Haghifam 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 de- scent) terms of expected stability, which turn can be bounded by the expected Le Cam Style Divergence (LSD). Such bounds have ((1/n) sample dependence unlike many existing bounds with O(1/ n dependence. Second, we introduce Exponential Family Langevin Dynamics (EFLD) which is substantial general- ization of SGLD and which allows exponential family noise to be used with gradi- ent 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 illustrate the our bounds are non-vacuous and quantitatively much sharper than existing bounds.
INTRODUCTION
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 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) estab- lished generalization bounds based on uniform stability (Hardt et al., 2016; Bousquet & Elisseeff, 2002), although the analysis needed rather small step sizes 1/- 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 of. In parallel, there has been key developments ization bounds applicable to SGLD type algorithms (Negrea et al., 2019; Haghifam et al., 2020; Xu & Raginsky, 2017: Russo Zou, 2016; Pensia et al., 2018).
related information-theorett general-
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 bound for SGLD of the form K VV, ni /o? which depends on K, the global Lipschitz constant for the loss, and with step size 7) < o In 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 o K, are too small. Mou et al. (2018) also presented another bound which addresses some of these issues, but gets an undesirable O(I)/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 estab- lished bounds for SGLD which have the desirable dependence the norm of gradient incoherence, ie., difference in gradients over different mini-batches, avoids dependence on Lipschitz constant K, and is applicable to unbounded nub-Gaussian losses, but have undesirable ((///)) sample
a

---

Under review as a conference paper at ICLR 2022
dependence. Haghifam et al. (2020) made further advances the problem from an information the- oretic perspective based on the conditional mutual information framework of Steinke & Zakynthinou (2020) and obtained generalization bounds based gradient incoherence with ((1/n) sample de- pendence, 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 bound of the form A V 1i ge (1)/oz for bounded losses, where ge (1) 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 az/ K.
In this paper, we build on the core strengths of such existing approaches, most notably the ((1/n) sample dependence of stability based bounds (Mou et al., 2018; Li et al., 2020) and the depen- dence on gradient incoherence for information theoretic bounds (Negrea et al., 2019; Haghifam et al., 2020), and develop 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 & Elissceff, 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 Li et al. (2020), we show that expected stability of general NSI algorithms can be bounded by the expected Le Cam Style Diver- gence with dependence on parameter distributions from mini-batches differing by one sample. In Section 3, we introduce Exponential Family Langevin Dynamics (EFLD), 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., 201 8a;b; Jin al., 2020; Alistarh et al., 20r7)Our main result provides an expected stability based generalization bound applicable to any EFLD algorithm with a O(1nn) sample dependence and 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 guaran- tees for EFLD and establish such results for noisy Sign-SGD and SGLD. Through experiments 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 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, information- theoretic 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 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 al. (2020); Rodríguez- Gálvez et al. (2021) prove data-dependent generalization bounds dropping dependence on the Lips- chitz constant. Further, tighter bounds (Haghifam et al., 2020; Zhou et al., 2021; Rodríguez-Gálve et al., 2021; Neu, 2021; Hellström & Durisi, 2021) 1) are proposed based on conditional mutual infor- mation (Steinke& & Zakynthinou, 2020; Grünwald et al., 2021; Hellström & Durisi, 2020). Due to space limitations, an extended discussion of the related work is deferred to Appendix A.
2 GENERALIZATION BOUNDS WITH EXPECTED STABILITY
In the setting of statistical learning, there is an instance space Z, a hypothesis space W, and a loss function E W x Z + R4, Let D be an unknown distribution of 2 and let S ~ D" be n i.i.d. draws from D. For any specific hypothesis w E W. the population and empirical loss are respectively given by [w) A E =)), and (s(w)) A n "" E(w, 21). For any distribution P over the hypothesis space, we respectively denote the expected population apd empirical loss as
and Ls(P) A 1 Σ Ew- p(((w,
LD (P) A ((ss,
(1)
Consider randomized algorithm A which works with s {,,,..,,,n) 2n) D and cre-
2

---

Under review as a conference paper at ICLR 2022
ates distribution over the hypothesis space W. For convenience, will denote the distribu- tion as A(S). The focus of the analysis is to bound the generalization error of defined as: gen(A(S)) _ [n(A( - (s()())) We will assume is permutation invariant, i.e., the or- dering 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 (s(L)((()) - Ls(A()))), and discuss high-probability bounds in the Appendix B.
2.1 BOUNDS BASED ON EXPECTED STABILITY
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(PI P*) = (vp(((W) - V/'(w)))dw.
Proposition 1. Let Sn Da and let S¹ be a dataset obtained by replacing in E S, with in D. Let A(Sn),A(S), respectively denote the distributions over the hypothesis space W obtained by running randomized algorithm A on Sy, Assume that for Sn D", Vz E 2, BwwA(s.)) (W), I co/2, co > O. With H(;)) denoting the Hellinger divergence, we have
DS,.-DILL(A(SS - (s(ssss)s))))) S DD (A..)
(2)
Remark 2.1. Proposition 1 does not need bounded losses. Just the second moment of ((W, 2), W ~ A(S,), Sn D" V2 E Z need be bounded. The assumption is satisfied by bounded losses. It instructive to compare the assumption to that in recent information theoretic bounds (Haghifam et al., 2020; Xu Raginsky, 2017), where one assumes E(w, 2), Z ~ D, Vw W to be nub-Gaussian.
Remark 2.2. The bound in Proposition is in terms of expected stability where we consider an important departure from bounds based on uniform stability (Elisseeff et al., 2005: Bousquet & Elisseeff, 2002; Mou et al., 2018; Bousquet al., 2020: Feldman & Vondrak, 2018; 2019) where one considers e |1S,5""" I..... Replacing sup by E makes the bounds distribution dependent, and arguably leads to quantitatively tighter bounds.
Es-D= E=
Note that the Hellinger divergence can be bounded by the KI. divergence.
Proposition 2. For any distributions P and P', (P, P*) S min [KL(P,P), / (KL(P,P'),
2.2 EXPECTED STABILITY OF NOISY STOCHASTIC ITERATIVE ALGORITHMS
We consider a general family of noisy stochastic iterative (NSI) algorithms. Given S ~ D", such iterative algorithms have two additional sources of randomness in each iteration t: (a) a stochastic mini-batch of samples Sg,, with |SB,1 = b, drawn uniformly at random with replacement from S; and (b) noise &, suitably included in the iterative update. Given trajectory of past iterates Woste1) = Wo:(t-1). the new iterate W, is drawn from a distribution PB..s:/wo. over W:
W. P BB.../oo (W).
We will drop the conditioning Wo: to avoid clutter in the sequel. Let Pr, Pj denote the marginal distributions over hypotheses w E W after T steps of the algorithm based on Sn, Sy respec- tively. Further, let Po-(t-1) denote the joint distribution over Wn:(t-1) = (Wo...., W(-1), and let Pa P compactly denote the conditional distribution on W, conditioned on the trajectory Wa:ft-1) W0.-1. Following (Negrea et al., 2019; Haghifam et al., 2020; Pensia et al., 2018), we use the following chain rule for KL-divergence: (L(Pr(IP() < |L
Et, PP [KL p/)]- Let S D and let Sn, S be size n subsets of S such that S. = (Z Zn-1. In} and 5% = [Z....., Zn-1, ZZ,, where Z% = Zn+1- Let So = mini-batch of size in each iteration uniformly
(Z,,... 7n The algorithms we consider
sampled from n samples. Let the set of all mini-batch index sets be denoted by G. Lett the set of all
mini-batch index sets A drawn from So be denoted by Gy. Note that |Go| = =(-=] (7=1). Let G1 denote
the set of all mini-batch index sets B which includes the last sample, viz. 2n for S with mini-batcher
and z for S.. Note that |G,| ( Also note that |Gol + |G ("5)) + (C-) (3) = |G].
Following Li et al. (2020), we can bound their conditional KL-divergences KL in terms of a Le Cam Style Divergence (LSDD). While the classical Le Cam divergence (Sason & Verdu,
3

---

Under review as a conference paper at ICLR 2022
2016) is LCD(P)IPP) - 2 dP+dPi (where dP denotes the density), our bounds in terms of (P A (d -d k. B, G1, A, Go. Note that PB, and P B..g. represent
dF
the distribution of W for Sn and S, respectively since the mini- Sg, of S, and Sy 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 6 S n2/2. Then, with C1 220 (with as in Proposition 1), we have
(P ddP' B.... )2
T Σ
b Ss, (LL((LL) (A(S.)) S C1 Es Ezi
E
dl
71
B
dPALE
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, =/ trajectories Wo:(t-1). and mini-batches Bt, A,. 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 Sec- tion 3, the expected LSD term has a f dependence for the Exponential Family Langevin dynamics (EFLD) models we introduce, the leading b is neutralized.
3 EXPONENTIAL FAMILY LANGEVIN DYNAMICS
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 example of NSI algorithms of the form (3), SGLD adds an isotropic Gaussian noise at every step of SGD: Wi+1 = wi nn Vê(w,, SB.) + N (0, of where Ve(W,, SB.) is the stochastic gradient on mini-batch Br, M) is the step size, and of is noise vairance.
In this paper, we introduce 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 being mathematical generalization of the popular SGLD, the pro- posed 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).
3.1 EXPONENTIAL FAMILY LANGEVIN DYNAMICS (EFLD)
Exponential families (Barndorff- 2014; Brown, I 1986; Wainwright & Jordan, 2008) consti- tute large family of parametric distributions which include Gaussian, Bernoulli, gamma, Pois- son, Dirichlet, etc., as special cases. Exponential families are typically represented in terms of natural parameters 0, and we consider component-wist independent distributions with scaled nat- ural parameter 0_ 0/a with scaling > 0, i.e., Pvs (g. fa) = exp( ( 0.) (6(0.) (T)()) mh exp(E,0ja - v (0 (E,,)))) where & is the sufficient statistic, to (0.) = Σ (0((a) the log-partition function, and TE( = Il To(E)) is the base measure. Note that a = 1 gives the canonical form of the exponential family distributions. For general scaling a > 0. for some cases the base measure To may depend on the scaling, i.e., No A scaling
0 is valid long as exp((E. 0a) is integrable, i.e., . ex.(((E. (a) < oc. Further, vi is smooth function by construction
2014; Banerjee et al., 2005; Wainwright & Jordan, 2008) and the smoothness of & implies V2 < czl.
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. particular, for mini-batch SB,, EFLD updates are as follows: with step size P: > +
W; W P.EE
t ~~ (E: 0 B.,a))
(5)
where
On,
V 10(w,,1, Sp.) (6)
Po (E: 0 = ) )
0 BB.o
04
0t
4

---

Under review as a conference paper at ICLR 2022
For EFLD, the natural parameter 8 .u at step i is simply scaled version of the mini-batch gradient V ). We first show that EFLD becomes SGLD when the exponential family is Gaussian, and becomes 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.I.
Example 3.1 (SGL.D). SGLD uses scaled Gaussian noise with (b()) 11011/2, = -Vat It
so that Pa ( o..).) = (0 aaT.)). By taking Pt = /nLor, the update (5) based on PaEt is distributed as (V p. PT) = Vi,,VV((, SR.): I.). Thus the EFLD update reduces to the SGLD update: W, = Wi-1 - 7) V SB.) + + (0, LL
Example 3.2 (Noisy Sign- By taking Pt. 7/, and component- Eg E (-1,1), To(E,)
1, (0) = log(exp(-0)) exp(6)) in exponential family update equation (5). the j-th component of exp(e, (...))))
exponential family distribution (E: 0 B.,a.) becomes p (E3) = exp(-08,, s)xxx(1 (exp((
Thus, the EFLD update reduces to noisy version of Sign-SGD: w, Wi- ne Etj
a ( E [d], where B,, = V((w:-1, SB,) //a is the scaled mini- gradient. L
3.2 EXPECTED STABILITY OF EXPONENTIAL FAMILY LANGEVIN DYNAMICS
From Lemma 1, conditioned on trajectory (o mini-batches SB SAL, we can get gener- alization bound by suitably bounding the Le Cam Style Divergence (LSD) given by: LA,.B, =
(dPone: -dr'n,,e dg.. For EFLD, the density functions d.B... are exponential family densi- Je. dPAL.E
ties p (B:0 in (5)-(6), and we have the following bound the per step LSD:
Theorem 1. For a given set 5 ~ D=-1 and Wi-1 at iteration (t - 1), let D. (5) = max,, || ( - VE (wi-1,2')llz Further, for a Cy-smooth reg-partition function ib, let the scaling at wt-1 be data detendependnnt such that affwi- 2 802 1 (Sm+1). (S Then, we have
B, I 502 1 B.... - 0 0B..0. 20 /w:
502
(WL1,,
VV (w
(7)
Note that SB, and SB only differ at samples on and 2/, The above bound can now be directly applied to Lemma 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 oz- co-smooth log- aa--artitionn function vb. Then, for mini batch size S n/2, with cov loy522 (with co as in Lemma 1) and og 2 Sc227 (Sa+1) (as in Theorem 1, with the conditioning on W hidden to avoid clutter), we have
1 Es (s(Ln(A(S)) - (s((()) < c- E
E 1 [IVe(w.1.22) -e (w. 2/)1
Σ 1=1 Wo:te-1)
S.11
(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 Th as the bound in Li et al. (2020). However, our bound is numerically sharper because we replace the gradient norms, i.c. E (K(we.2) in Li et al. (2020) and with gradient discrepancy [[((w,,)) which 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/.nn, which is worse than the 1/n dependence in our bound.
V((we, 2'Il,
Remark 3.2. EFLD can be extended
work with anisotropic noise by using OB.
V SB.) Ø a4 in (6) where ar E IR determines different scaling for each dimension and @ denotes Hadamard division. Theorems 1 and can be extended such anisotropic noise by using a-scaled norms for the gradient discrepancy, i.c., llg - g' g'llă... = Σ,(g - ([,0j-o))//a /a)"
O
Remark 3.3. The condition on ar 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 L./L. However, the step sizes in Theorem 2 need to be bounded by or/ o (S)). which is considerably more relaxed since (5) is much smaller than Lipschitz constant L. which is a uniform bound over the whole parameter space. Also, usually
would expect A, to decrease as training proceeds since the gradients shrink as the loss function being minimized. Thus, the constraint step size does not require the step sizes to be small as o./ L..
5

---

Under review as a conference paper at ICLR 2022
3.3 PROOF SKETCHES OF MAIN RESULTS: THEOREMS AND 2
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 When the density dP Pv(E; B,,)). ) by mean-value theorem,
for each &. we have (E; (,,)) Pe(E: (B; = (0 B, (E (),a), for some
BB = NeOB,a + (1-7<) where E [0, 1]. Then,
IA.B= {
de { (0 0B Vēg.o (E: 0B,)) ( (E: Pe(E:Os.a)
(polE:08,a) - poi (E: 0a)
dc
p=(E; OA.a)
since (E: exp( 0 B,a) vi ()(B,a))TO(EE)
Handling Distributional Dependence 0g. Note that we cannot proceed with the analysis with the density term depending on 0R,- since 0R.- depends on &. So, we first bound the density term depending on 0 in terms of exponential family densities with parameters B, and BB using og-smoothness of vb.
Lemma 2. For some ? E [0, 11. BB,a B, a + (1 -
(1->g)00 70)00 we have
(E, (R,)) - (0
exp
S exp [c2ll0B.a - 0B
max (exp [EE, OB,)) (0B,aa) exp (E, BB, (0 (a))
Bounding the Density Ratio. Next we focus on the density ratio p (E. B...8/p //pppppssf/// 0.,a). By Lemma 2, it suffices to focus on PÊ. (BB.)/Ppt (E: f.,a) the equivalent term for 0 aa We show that the density ratio can be bounded by another exponential family with parameters (20 OA,a).
Lemma 3. For any &, we have
exp (g. 2.) - (0((B.a)) I exp 220 OB O
12 exp (20 OA.a) -1520g,a 0A,a)l
exp (E. A.,)) (b)))a))
The analysis for the term (E 0B p AA,a) is exactly the same.
Bounding the Integral. Ignoring multiplicative terms which do depend on & for the moment, the analysis needs to bound an integral term of the form Se (n.n. O' BBB.a VEL(; OB,a)) Pc(E:20 - )d, and similar term with (E:20 OA.a). First, note that Vib(E; OR.)) an... the expectation parameter for (= PR,,) Wainwright & Jordan (2008); Banerjee et al. (2005). The integral, however, is with respect to Po (c: 20 0A,a)- We handle this discrepancy by using & - Vui(E; θB.a) = (E - -E] + (E - O and decomposing sum-of-squares. Quadratic form for the first term yields the covariance E[(E - (E E = 22 (02000n.--0... -...) < IzI, by smoothness. The second term de- pends on the difference of gradients V20(0BB,. 0A,a) Vu(θB, which, using smoothness and additional analysis, can be bounded by the norm of (0,.o - A,,)). All the pieces can be put together to get the bound Theorem 1, which when used Lemma 1 yields Theorem
3.4
OPTIMIZATION GUARANTEES FOR EFLD
We now establish optimization guarantees for two examples of EFLD, i.c., Noisy Sign-SGD with Bernoulli noise over (-1, +1} and SGLD with Gaussian noise.
Noisy Sign-SGD. For mini-batch B, and scaling ar, mini-batch Noisy Sign-SGD updates the pa- rameters as W, Wi-1 - T.E, where each component j E [d]
exp(xOn..os))
Eij ~ po (2) exp(-0B..) B.....)) + cxp(p (..))) x. E (-1,+1)
where OB.., a, V((w(-1, is the scaled mini-batch gradient. The full-batch version uses parameters En, 0 p...... = (Lw(w,-1) For the optimization analysis, we assume that the loss is smooth and mini-batel gradients unbiased, symmetric, and sub-Gaussian

---

Under review as a conference paper at ICLR 2022
Assumption 1. The loss function Lg satisfies: for all and w', for some non-negative constant K = [K1.... Ka), we have [s(w)) S I:s(w") (Iss(w)??(w w') + E, Ki(w; -w?)²
Assumption 2. Given Wt-1- the mini-batch gradient V SB,) is (a) unbiased, i.e., EB, w..1 Ve(we-1.SB. = VI.s(We-1); (b) symmetric, i.e, the density p(z) of I = Vi(W:-I.SB. is symmetric around its expectation Ls(W(-1): p(z) = || = 1, Br,/w, exp A(v, Ve(Wi-1,
and
(c) sub- Gaussian i.e., for any X > O. any
Vl.s(W;-1)) S exp(X2<2 /2) for some constant K₁ >
Based on the assumptions, we have the following optimization guarantee for mini batch noisy Sign- SGD. 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 = L/VT, ar satisfying 2 a4 2 max /oxx//KK,,
V (wi-))lo) we have for any S and any initialization
Wo
E
(VLLsw..)l S (Ls((w)) L E
4c
Ls(w") +22+211111 1
(10)
T
VT
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 and 2, with K; K, Vi [d], for any S, SGLD (EFLD with step size Pt V at
/ (e) [B,] and T)-
1 VT can achieve
1 +0 VT)
PI
11= Of + log
Σ LIV SO
(11)
VT
where the expectation is over the randomness of the algorithm.
The error rate of SGLD depends on the noise variance (g One can choose a decaying noise variance such as = 1/ to guarantee the convergence. Then the rate will become Ollog T T/vT). We note that similar to the optimization guarantees of DP-SGD, the convergence rate depends 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).
4 EXPERIMENTS
In this section, conduct series of experiments to evaluate 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-Gálvez presented in Rodríguez-Gail Gá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., 201 8a) and present the corresponding generalization bound Theorem 2.
al. (2021) for various datasets. Note that the bound
The details of our model architectures, learning rate scheduling. hyper- additional experimental results can be found Appendix E. We acknowledge that we did not achieve the state-of-the 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.
hyper-paramed parameter selections and
4.1 STOCHASTIC GRADIENT LANGEVIN DYNAMICS
Comparison with existing work. We have derived theoretical generalization error bounds that depend on the data-dependent quantity gradient discrepancy, i.e., || (wr, an) - Vi (w,,,, 2/)1i 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 (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 mainly due to the fact that we replace the squared gradient norm in Li al. (2020), the squared norm of
7

---

Under review as a conference paper at ICLR 2022
Than Errer
Test Eino Boura
Text Error
Swit bou
Test Erro Beurd
0.8
0.8
0.8
Neqq board
0.6
0.6
9.6
Sur Eectig Sen-Caloo
boand
0.
Emt
84
0.0
00
No: Epochs
No. Epochs
No.
No. Epochs
(a) MNIST, of z 0.1
(b) CIFAR-10, 10, af Ro 0.1
(c) Fashion, oi F2 0.1
(d) Fashion, of =2 0.01
Generohation Ernar Bouina
Genera toettom mrr Bouns
Gemera Bound
Uound
lmngnn of loaad
6.
8.
08
bound
tcaliguss octvez bound
0.6
0.6
08
0.4
024
8.4
04
022
03
0.0
230
500
0.0
20
0.0
20
Epochs
Epochs
No. Epochs
No. Epochs
MNIST, of R 0.1
(I) CIFAR-10, af R 0.1
(g)
Fashion, af R/ 0.1
(h) Fashion, of Re 0.01
Gredent (Dicrepanic))
Gradiont Norm (DSccropancc)
Grodiaat Norm (DScrupancc)
Gredient torm (Dicceepacc)
-00"
30F
1:3
20"
20P:
Crediett decrepancy
12"
20"
Two Sample frosherence
10-2.
Le-1
20-4
10-
10
10:4
20 No. Epochs
10
200 750
2000
10
40
20r4
40
No. Epochs
No. of Epochs
No. of Epochs
(i MNIST, of x 0.1
()) CIFAR-1O, of 0.1
(k) Fashion, of x 0.1
(l) Fashion, of x 0.01
Figure 1: Numerical results for training CNN using SGLD (o, = / (r) on MNIST, Fashion-
MNIST and CIFAR-10. X-axis shows the number of training epochs. (a)-(d) shows our bound is non-vacuous and can be used to bound the empirical test error. (e)-(h) compare our bound with the existing bounds and show the effect on of. (i)-(l show the key factors in each bound, i.e., the squared gradient norm in Li et al. (2020), the gradient incoherence in Negrea et al. (2019), the two-sample incoherence in Rodríguez-Gálvez al. (2021), and the gradient discrepancy in our bound. Our bounds are numerically sharper than existing bounds, and larger af leads to tighter generalization bounds which is consistent with the theoretical analysis.
gradient incoherence in Negrea al. (2019), and that of two-sa incoherence in Rodríguez- Gálvez et al. (2021) with the gradient discrepancy. Results in Figure 1 (e)-(h) show that our bounds much sharper than those of Li et al. (2020) because our gradient discrepancy (Figure (i)-()) 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-Gai Gålvezz et al. (2021) due to an improved dependence on from an order of 1// v to 1/n.. Note that, even though the gradient incoherence in Negrea et al. (2019) about to 2 order of magnitude smaller than the gradient discrepancy for simple problems such as MNIST and between the gradient incoherence and our gradient discrepancy reduces as the problem becomes harder (see results for CIFAR-10 in Figure (()).
the difference
Effeet 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/es error (Figure 2 (a) dashed lines). Our generalization bound also becomes larger as the randomness increases since the corresponding gradient discrepancy increases.
4.2 NOISY SIGN-SGD
Optimization. Figure 3 (a)-(d) show the training dynamics of Noisy Sign-SGD under various lections of az. As a; -+ O. 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 o increases, the probability of getting approaches 0.5, and & approximates a uniform distribution. As a result, the corresponding Noisy Sign-SGD still converges, but the generalization performance is much worse.
8

---

Under review as a conference paper at ICLR 2022
T044 Enteree (8s5hed)
Ip cul --ppp..... -oild
201
Rando
Bounded bole))
Traiting Eror
10-1
0.6
0.4
10m
500 750
1000
1000
1000
1000
No. Cpachs
No. Coochs
Epochs
Epocts
(a) Bounded Test Error
(b) Our Bound
(c) Gradient Discrepancy
(d) Training Error
Figure 2: Numerical results for training CNN using SGLD (a, = 0.2%)) on a subset of MNIST (n 10000) with different randomness on labels. (a) demonstrates that, as the randomness increases, the empirical test error (dashed lines) increases but still can be bounded by our generalization bound by combining the empirical training error (solid lines). (b) presents our bound Theorem 2. (c) shows the gradient discrepancy V[ (Wr, zn)
Vi (W,; 1 (d) plots the training error. The gradient discrepancy increases randomness increases, so does our generalization bound.
1.0
Sig-520 10
2.0
agy-50 10.00)
1.0
Sig 560 (E-
Sgy-500
10:25)
Training Ererr
0.8
Training Eroor
2.8
(914))
0.8
5.8
11
0-0000 (2.32)
0.6
Seay (001)
0-0000 8.601
Trainin
06
Training
6.6
64
6.
0.0
0.0
0.0
25
1.0
0.0
75
100
No of Lpochs
No. of Lpochs
No. of Lpochs
No. of Lppchs
(a) CNN, MNIST
(b) CNN, Fashion
(c) ResNet- 18, CIFARIO (d) ResNet-18, CIFARIOO
Taln Drer
The Ener
Eertrrer Bound
Tell Eree
Test Eiror Bound
Bound
9.4
64
No. spachs
No. toochs
No. tocchs
No. Epachs
(e) MNIST, at =1
(1) MNIST, ar = 0.01 (g) Fashion, Ct =
(h) Fashion, du = 0.01
Figure 3: (a)-(d) show the training dynamics of CNN on MNIST and Bishion-MNIST, and ResNet- 18 on CIFAR- 10 and CIFAR-100 using noisy sign-SGD with different scaling ay, Legends indicate the choice of a; and the numbers in brackets are test errors at convergence. As ag - 0, Nosiy sign-SGD matches both the optimization trajectory as well as the final test accuracy of the original sign-SGD (Bernstein et al., 2018a). (e)-(f) show that empirical test error can be bounded by our bound and the corresponding training error. The larger at is the sharper our bound is.
Generalization Bound. Figure 3(e)-(f) show that our bound successfully bounds the empirical test error. The larger ae is the sharper the upper bound is. However, larger ar would slow down and adversely affect the optimization, c.g., Figure (a)-(d) blue and orange lines. In practice, one needs to balance the optimization error and generalization by choosing a suitable scaling at.
5 CONCLUSIONS
Inspired by recent advances in stability based and information theoretic approaches to generalization bounds (Mou et al., 2018; Pensia al., 2018; Negrea et al., 2019; Li 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). 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 ((1/n) sample dependence and a dependence on gradient incoherence, rather than gradient norms. Further, have provided optimization guarantees for EFLD and establish such results for Noisy Sign 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 al., 2019).

---

Under review as a conference paper at ICLR 2022
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication-effiiennt sgd via gradient quantization and encoding. Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 1709-1720. Curran Associates, Inc., 2017.
Hilal Asi, John Duchi, Alireza Fallah, Omid Javidbakht, and Kunal Talwar. Private adaptive gradient methods for convex optimization. In International Conference on Machine Learning, pp. 383- 392. PMLR, 2021.
Arindam Banerjee, Srujana Merugu, Inderjit S Dhillon, and Joydeep Ghosh. Clustering with breg- man divergences. Journal of machine learning research, 6(10), 2005.
Ole Barndorff- Information and exponential families: in statistical theory. John Wiley & Sons, 2014.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 464-473, IEEE, 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 2019.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33, 2020.
Jeremy Bernstein, Yu-Xiang Wang. Kamyar Arizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. International Conference on Machine Learning, pp. 560-569, PMLR, 2018a.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority vote is communication efficient and fault tolerant. In International Conference on Learn- ing Representations, 2018b.
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymp- totic theory of independence. Oxford university press, 2013.
Olivier Bousquet and André Elisseeff. Stability and generalization. Journal of Machine Learning Research, 2:499-526, 2002.
Olivier Bousquet, Yegor Klochkov, and Nikita Zhivotovskiy. Sharper bounds for uniformly stable algorithms. In Conference on Learning Theory, pp. 610-626. PMLR, 2020.
Lawrence D Brown. Fundamentals statistical exponential families: with applications in statistical decision theory. Ims, 1986.
Yuheng Bu, Shaofeng Zou, and Venugopal Veeravalli. Tightening mutual information based bounds on generalization error. In 2019 IEEE International Symposium on Information Theory (ISIT), pp. 587-591. IEEE, 2019.
Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 74-86, 2018.
Clément L Canonne, Gautam Kamath, and Thomas Steinke. The discrete gaussian for differential privacy. In NeurlPS, 2020.
Xiangyi Chen, Tiancong Chen, Haoran Sun, Zhiwei Steven Wu, and Mingyi Hong. Distributed training with heterogeneous data: Bridging median-and mean- based algorithms. arXiv preprint arXiv: 190::9906.0336 2019.
10

---

Under review as a conference paper at ICLR 2022
Lue Devroye and Terry Wagner. Distribution-free inequalities for the deleted and holdout error estimates. IEEE Transactions on Information Theory, 25(2):202-207, 1979.
Andre Elisseeff, Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
Vitaly Feldman and Jan Vondrak. Generalization bounds for uniformly stable algorithms. In Pro- ceedings of the 32nd International Conference on Neural Information Processing Systems, pp- 9770-9780 2018
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable al- gorithms with nearly optimal rate. In Conference on Learning Theory, pp. 1270-1279. PMLR, 2019.
Peter Grünwald, Thomas Steinke, and Lydia Zakynthinou. Pac-bayes, mac-bayes and condi- tional mutual information: Fast rate bounds that handle general classes. arXiv preprint OrXiv:2/06.0900 2021.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. Advances in Neural Information Processing Systems, 2020.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, 2016.
Fredrik Hellström and Giuseppe Durisi. Generalization bounds via information density and condi- tional information density. IEEE Journal Selected Areas in Information Theory, 1(3):824-8835 2020.
Fredrik Hellström and Giuseppe Durisi. Fast-rate loss bounds via conditional information measures with applications neural networks. In 2021 IEEE International Symposium on Information Theory (ISIT), pp. 952 957. IEEE, 2021.
Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 2525- 2536. Curran Associates, Inc., 2018.
Chi Jin, Rong Ge, Praneeth Netrapalli, Sham M Kakade, and Michael Jordan. How to escape saddle points efficiently. In International Conference Machine Learning, pp. 1724-1732, 2017.
Chi Jin. Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. arXiv preprint (Et::1902.048111 2019.
Richeng Jin, Yufan Huang, Xiaofan He, Tianfu Wu, and Huaiyu Dai. Stochastic-sign sgd for feder- ated learning with theoretical guarantees. arXiv preprint arXiv:2002. 10940, 2020.
Peter Kairouz, Mónica Ribero, Keith Rush, and Abhradeep Thakurta. Dimension independence in unconstrained private erm via adaptive preconditioning. arXiv preprint arXiv:2008.0653 06570, 2020.
Alex Krizhevsky. Learning Multiple Layers of Features from Tiny Images. Technical Report Vol.
1, No. 4., University of Toronto, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, 86(11))2278-2324 1998.
Jian Li, Xuanyuan I Luo, and Mingda Qiao. On generalization emoo bounds of noisy gradient methods for non-convex learning. International Conference on Learning Representations, 2020. URI.
https cpwnreviewweeeeeeeeeeeeee .ne/ wwwpee.eeeoffruueeeeeeeeeeeeeeee forum? Six.iidxxiiiixxisee...
Wenlong Mou, Liwei Wang, Xiyu Zhai, and Kai Zheng. Generalization bounds of sgld for non- convex learning: Two theoretical viewpoints. Conference on Learning Theory, pp. 605-638. PMLR, 2018.
11

---

Under review as a conference paper at ICLR 2022
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. information-theoree generalization bounds for sgld via data-dependent estimates. In Advances in Neural Information Processing Systems, 2019.
Gergely Neu. Information-theorrtiec generalization bounds for stochastic gradient descent. arXiv preprint arXiv:2102.00993: 2021.
Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization enror bounds for noisy, iterative algo- rithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 546-550. IEEE, 2018.
David Pollard. A user's guide to measure theoretic probability. Number 8. Cambridge University Press, 2002.
Borja Rodríguez-Gálver Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. On random subset generalization error bounds and the stochastic gradient langevin dynamics algorithm. In 2020 JEEE Information Theory Workshop (ITW), pp. 1-5. IEEE, 2021.
William H Rogers and Terry J Wagner. A finite sample distribution-free performance bound for local discrimination rules. The Annals of Statistics, pp. 506-514, 1978.
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory.
In Artificial Intelligence and Statisties, pp. 1232-1240, PMLR, 2016.
Igal Sason and Sergio Verdu. f-divergence inequalities. IEEE Transactions on Information Theory, 62, 2016.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes. In International conference on machine learning, pp. 71-79. PMLR, 2013.
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, pp. 3437-3452. PMLR, 2020.
Alexandre B Tsybakov. Introduction nonparametric estimation. Springer Science & Business Media, 2008
Martin Wainwright and Michael Irwin Jordan. Graphical models, exponential families, and vari- ational inference. Now Publishers Inc, 2008
Di Wang and Jinhui Xu. Differentially private empirical risk minimization with smooth non-convex loss functions: A non-stationary view. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 33, pp. 1182-1189, 2019.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In International Conference Machine Learning, ICML '1L'"11, '1,, pp. 681-688, 2011.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms, 2017.
Aolin Xu and Maxim Raginsky. -heeoetion-theoretiic analysis of generalization capability of learn- ing algorithms. Advances in Neural Information Processing Systems, 2017:2525-2534, 2017.
Guandao Yang, Tianyi Zhang, Polina Kirichenko, Junwen Bai, Andrew Gordon Wilson, and Christo- pher De Sa. Swalp: Stochastic weight averaging in low-precision training. 36th International Conference on Machine Learning (ICML), 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL https: /ttp:///ppeeeeeeeee/m net/forum forummommm/////// SuddyyyyyyBB 9xx.
Huanyu Zhang, Ilya Mironov, and Meisam Hejazinia. Wide network learning with differential pri- vacy. arXiv preprint arXiv:2103.01229 2021.
12

---

Under review as a conference paper at ICLR 2022
Ruida Zhou, Chao Tian, and Tie Liu. Individually conditional individual mutual information bound on generalization error. 2021 IEEE International Symposium on Information Theory (ISIT), pp. 670-675. IEEE, 2021.
Yingxue Zhou, Steven Wu, and Arindam Banerjee. Bypassing the ambient dimension: Private sgd with gradient subspace identification. In International Conference on Learning Representations, 2020.
13


Reviews:
[{"review_id": "rMjey4IiCtk", "reviewer": "Reviewer_j8ws", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strength.\n1. The paper proves the generalization error of ''existing'' noisy stochastic iterative algorithms to have a $\\mathcal O(1/n)$ sample dependence. \n2. The exponential family noise is considered in the generalized SGD algorithms. The generalized error bound is based on expected stability, which seems to bring new ideas for general exponential family noise.  A thorough analysis of the error bound of exponential family noise SGD algorithms is provided. \n\nWeakness.\n\n1. The proposed algorithm does not show state-of-the-art performance.  The ultimate goal of the proposed algorithms is to achieve better performance on real data sets. Without strong support from the empirical study,  it is not convincible to believe why one bothers to study such more complicated cases. \n2. Adding to the above point, the paper only reviews the SGD in the literature, there have been very recent works based on Langevin dynamics, e.g. replica-exchange Langevin dynamic SGD, second-order Hamiltonian Langevin dynamics. Those algorithms achieve state-of-the-art performance. It is questionable to ask if the newly proposed algorithms in this paper could provide better performance if the model architectures are improved. ", "summary_of_the_paper": "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.", "summary_of_the_review": "The paper seems to provide a new family of SGD algorithms. The potential of the model seems to be broad. The theoretical analysis is recognized and deserves their own interest. However, the current state of the empirical study does not show promising performance. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "MWI834ppxky", "reviewer": "Reviewer_AX5S", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "There have been several works that generalize from gaussian settings to the more general exponential family, including the ones that are cited by the authors but also for example monotone retargetting and exponential family PCA. As such there are several tools for such an analysis that are pretty well known now. Other than that, the analysis follows closely with that of Li et al, with few minor but important differences. \n\nI am not sure if the extension to exponential family is a major contribution. It allows for analysis of signSGD. But given several other works of similar nature, I am not sure if the analysis and the major contribution as claimed, including in the title of the paper justifies a publication. \n\nIt seems, however, that proposing gradient discrepancy itself is a useful contribution. Can the authors highlight the difference in the analysis from Li et al explicitly that led to this difference in the bounds ? Why is this sidelined as a side-effect? Does this follow from the new exponential family based analysis proposed here (it does not seem to be so) ? The experiments are also conducted based on this contribution. As such the main message/contribution of the paper and the empirical section seems disconnected. I am happy to be corrected. ", "summary_of_the_paper": "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. \n\nThe 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. ", "summary_of_the_review": "The main contribution of exponential family dynamics seems not very significant. Gradient discrepancy is sidelined as a minor contribution but is focussed on a lot more in the empirical section, which makes the paper seems disconnected. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IWd6p2XDcFj", "reviewer": "Reviewer_4ShW", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "- Using the generalization bound in Theorem: In proposition 1, the authors provide a generalization bound based on the distributional stability in terms of Hellinger distance. However, in most of the results in the paper they mainly use the upper bound based on KL divergence (Prop. 2). Is that correct?  \n\n- The dependence of the learning rate on the optimization trajectory: In your bound alpha_t depends on the dataset and trajectory. It basically depends on some sort of Lipschitz constant of the loss function. For instance in SGLD, alpha_t depends on the learning rate and inverse temperatures. Therefore, I think it can limit us to use very small learning rates. Also, how did you make sure that this constraint is satisfied in your numerical studies?\n\n- The comparison with Rodríguez-Gálvez et al.: Your bound is very similar to the generalization bound in Haghifam et al'2020. As you mentioned the bound in Haghifam et al'2020 is stated for LD algorithm. Recently, the bound in Haghifam et al'2020 is extended to SGLD in [1]. The bound in Rodríguez-Gálvez et al has worse dependence on n (1/sqrt(n)), however, they have a decaying factor in their bound to compensate using of the chain rule. It would be nice to numerically compare your bound with the bound in [1]. \n\n- Applying your framework for analyzing SGD:  What are the roadblocks for applying your bound to analyzing SGD?\n\n- Surrogate loss: I think you should distinguish the loss function that we use to measure the generalization error with the loss function that is used for training. You should use different notations. \n\n\n[1] \"On random subset generalization error bounds and the stochastic gradient langevin dynamics algorithm\", Borja Rodríguez-Gálvez, Germán Bassi, Ragnar Thobaben, Mikael Skoglund\n", "summary_of_the_paper": "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. ", "summary_of_the_review": "Very interesting and solid contribution!", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CXZCJlJKm0y", "reviewer": "Reviewer_ipDu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "This paper provides several technical improvements to a recent line of work that I am not familiar with. Thus I can hardly review that relevance  and novelty of these improvements (and I am thus putting a low confidence score). I am concerned by the fact that the article is hard to read in a self-contained way. The authors largely comment the articulation of their work with similar works, but almost never comment the relevance of their work for a wider community. \n\nAnother concern is that the article provides two improvements listed above, but I could not perceive why it was coherent to present them in a common article. This might add some confusion to the paper. \n\nAs a naive question, I would like to ask why expected stability bounds are preferred. It seems that they involve expectations that are hard to compute analytically, at best one can approximate these expectations by sampling. How should these bounds be used in the end? In practice, to choose stopping criteria for algorithms, for instance? Or in theory, to analyze the performance of some algorithms?\n\nI found the generalization from Gaussian noise to exponential families novel and interesting.\n\nIn Section 2, I find difficult to determine what are your contributions and what was already known. For instance, Proposition 2 seems well-known right? Why not giving some references rather than proving it? Similarly, to what extent was Proposition 1 known?\n\nMinor comments:\n-  Section 2: \"D be an unknown distribution OVER Z\" (not \"of\")\n- Why do you introduce the notation W_{0:(t-1)} = w_{0:(t-1)}? I am under the impression that this is twice the same object, but I might misunderstand.\n- You sometimes use the notation KL(P,Q) and KL(P||Q).\n- Conflict of notation between S_0 and S_n (for n=0!).\n\n", "summary_of_the_paper": "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: \n- It proposes to use the notion of expected stability rather than uniform stability, which should to be tighter.\n- It generalizes the analysis to noises in an exponential family rather than Gaussian noise.\n", "summary_of_the_review": "I am not confident with my review as this paper is quite technical and I am not familiar with this line of work. I would appreciate having more insights about the application of the new techniques and the relevance of exposing them together in this paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper focuses on generalization bounds for exponential family Langevin dynamics, which extends related recent work for stochastic iterative algorithms such as SGLD in several ways. They derive expected stability bounds for a more general class of noisy stochastic iterative algorithms, leading to an exponential family variation of Langevin dynamics and a noisy version of the sign-SGD algorithm. The contributions are technical and quite positively received by one reviewer, while the others were not convinced to change their opinions during the author response as there were concerns on the limitation of the theoretical contributions and the extent to which these contributions have implications on achieving state of the art performance. While I find it valid that the scope of the paper focuses on generalization bounds and provide improvements over the existing literature, rather than on empirical benchmarks or on optimization-related aspects, the overall borderline impression of the reviewers on the whole suggests that a refined version of the paper that further clarifies the contributions and makes clear its impacts as well as limitations may make for a stronger and more impactful paper.
Decision: Reject