Optimizing Information-theoretical Generalization Bound via Anisotropic Noise of SGLD
Authors: Bohan Wang
Huishuai Zhang
Jieyu Zhang
Qi Meng
Wei Chen
Tie-Yan Liu
Venue: NeurIPS 2021 Poster (2021)
Keywords: Information-theoretical Bound
Optimal Noise Covariance
SGLD

Abstract: Recently, the information-theoretical framework has been proven to be able to obtain non-vacuous generalization bounds for large models trained by Stochastic Gradient Langevin Dynamics (SGLD) with isotropic noise.  In this paper, we optimize the information-theoretical generalization bound by manipulating the noise structure in SGLD. We prove that with constraint to guarantee low empirical risk, the optimal noise covariance is the square root of the expected gradient covariance if both the prior and the posterior are jointly optimized. This validates that the optimal noise is quite close to the empirical gradient covariance.  Technically, we develop a new information-theoretical bound that enables such an optimization analysis. We then apply matrix analysis to derive the form of optimal noise covariance. Presented constraint and results are validated by the empirical observations. 

Optimizing Information-theorrtiiaa Generalization Bounds via Anisotropic Noise in SGLD
Bohan Wang University of Science & Technology of China Microsoft Research Asia
Huishuai Zhang"
Microsoft Research Asia
Jieyu Zhang
Qi Meng Microsoft Research Asia
Wei Chen" Microsoft Research Asia
University of Washington Microsoft Research Asia
Tie- Yan Liu Microsoft Research Asia
Abstract
Recently, the information-theoreer framework has been proven to be able obtain non-vacuous generalization bounds for large models trained by Stochastic Gradient Langevin Dynamics (SGLD) with isotropic noise. In this paper, opti- mize the information-theorrtiicl generalization bound by manipulating the noise structure in SGLD. We prove that with constraint guarantee low empirical risk, the optimal noise covariance is the square root of the expected gradient covariance if both the prior and the posterior optimal noise is quite close to the empirical gradient covariance. Technically, we develop new
jointly optimized. This validates that the
-teeatttiooteeoeticcall bound that enables such an optimization anal- ysis. We then apply matrix analysis to derive the form of optimal noise covariance. Presented constraint and results are validated by the empirical observations.
1 Introduction
Generalization ability is one of the core questions learning theory [4], but remains unclear for deep learning models [17, 38]. Existing generalization bounds based on the capacity control become vacuous for practical deep learning models due to the over-parameteriizaton property [1, 26, 39).
From the information theoretical perspective, recent works [30, 37] bound the generalization error by the mutual information between the dataset and the learned parameters. This result reveals that good generalization occurs when the learned parameters do not depend on specific dataset too much, which is intuitively reasonable and closely related with the idea of algorithm stability iifformation-therree
[6, 15, 19, 24, 20] and differential privacy [8, 10]. Meanwhile, based metrics, one can analyze general classes of updates and models, e.g., stochastic iterative algorithms for non-convex objectives, hence applicable deep learning. It has been shown that the information theoretical bounds are non-vacuous and closely related with the real generalization error even deep learning [14, 26,9 39].
Notably, the information theoretical bound is realized in [28] via decomposing the mutual information across iterations. This framework can perform step-wise analysis of Stochastic Gradient Langevin Dynamics (SGLD) [33, 29], by evaluating the mutual information conditional on the previous learned
"Corresponding Author
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

parameters at each step. We note that the noise added in SGLD is critical for both the mutual information evaluation and the empirical risk minimization. Most existing work focus on SGLD with constant and isotropic noise covariance [22, 23, 14] due to the technical difficulty. However, it is observed that the test accuracy of SGLD with isotropic noise has considerable gap compared to that of the widely-used Stochastic Gradient Descent (SGD) [40]. This empirical gap motivates us to consider the following question:
Can we find the optimal noise added in SGLD in terms of generalization?
An affirmative answer will lead an algorithm imitating SGD better, which helps us better understand the generalization behavior of SGD.
Specifically, we propose to optimize the structure of the noise in SGLD such that the generalization bound is minimized while a low empirical risk is guaranteed. To this end, we first show that the trace of the noise covariance in SGLD is valid constraint that governs the empirical risk behavior both theoretically and empirically. Then we devise a new information theoretical generalization bound that are parallel those bounds in [25], but facilitate the derivation of the optimal noise. With these technical preparations, we prove that when jointly optimizing both the prior and the posterior, the optimal noise covariance is the square root of the expected gradient covariance, i.e., their eigenvectors are the same and the corresponding cigenvalues of the former are the square root of the latter, and the optimal prior recovers the prior [25]. This indicates the optimal noise covariance of SGLD would be quite close to the empirical gradient covariance, i.e., the noise covariance of SGD, because of the concentration of measure.
Our result lends support to the belief that the noise introduced by Stochastic Gradient Descent (SGD) is superior to the isotropic noise, which has been widely observed [18. 36, 40, 38). As illustrative example, we plot the generalization errors of SGD, SGLD with the isotropic noise and SGLD with the optimal noise in Figure 1, where their training curves hehave almost the same (do not show here).
We can see the optimal noise captures the behavior of SGD much better than the isotropic noise.
Specifically, our contribution can be summarized as follows:
SREC-SGLD
Iso- SGLD SGD
1. We formulate a problem of finding the optimal noise covari- ance by optimizing an ceammatioon-thooetiie bound;
2. We develop new information tthoooeticteertialllla bound to facilitate the analysis of the above optimization problem;
3. We obtain the optimal structure of the noise covariances, and demonstrate the similarity to empirical/expected gradient
0.13
10000
13000
1.20mm
190000
19006
covariance;
Figure 1: Generalization errors of SGD, SGLD with the isotropic noise (Iso-SGLD) and SGLD with the op- timal noise (SREC-SGLD),
1.1 Related Works
cntrmmationnthhoreetn bounds. Recently, researchers [37, 30, 28] propose to bound the gener- alization error by the mutual information between output hypothesis and input samples. Negrea et al. [25] further tighten the bound by designing a data-dependent prior. Following [25], Haghifam et al. [14] obtain comparable results through conditional mutual information [31]. Other related work
[2, 16, 5, 13] tightens the information theoretical generalization bounds from different perspectives.
There are also high probability generalization bound [24, 26, 21] obtained by combining information
theory [7] and PAC Bayesian framework [27,33)
Effects of the noise covariance. SGD achieves excellent performance in terms of generalization error in deep learning. In contrast, one recent work [40] demonstrates empirically that even with well-tuned scaling, isotropic SGLD still achieves much worse generalization error than mini-batch SGD. They obtain an optimal covariance matrix (low-rank approximation of Hessian) in terms of escaping efficiency at local minima. Furthermore, [34] show empirically large-batcl batge-bacch SGD with diagonal Fisher Gaussian noise can recover similar validation performance as small-batch SGD. However, both the noise covariance investigated by [40] and [34] has gap with that of SGD. It has also been proven [23] that the stationary distribution of state-dependent SGLD with the empirical loss approximated by quadratic function obeys the power law, and has a better escaping efficiency than SGLD with the isotropic noise.

---

2 Preliminaries
Notations. Here briefty introduce the notations which will be used throughout this paper.
(Set operation) For a positive integer N, we use [N] to denote the index set {1,2. ... N.
and use Virj to denote the set {Vi) For finite set S {z1,- = [8] is the cardinality of S, and S = ke. is a subset of S with indices in set J C [N].
(Probabilityy) S denotes that is uniformly sampled from the set S. For two random variables X and Y, we denote the conditional distribution of X given as TPY (X) and denote the conditional expectation of X given Y EY (X).
(Matrix) We use Laxd for the d x d identity matrix, abbreviated as when dimension is clear. For a differentiable function f, we denote the gradient of f at point W Vf(W). For positive semi-definite matrix A Rdxd, we say B = A E Raxd B =
Supervised Learning. In this paper, we focus on the supervised learning. conducts the empirical risk minimization (ERM) over training data: Minimizew (s) -
SS Exes {(: W), where W Rd is the parameter of the model, S is the training set with each data point i.id. sampled from a distribution D, is the (individual) loss function. A stochastic algorithm solves the ERM by outputting distribution Q of parameter W. The generalization error measures the gap between the population risk and the training risk as
Gerr _ Es.q= (Ro(W) - -Rs
SGD and SGLD. The update rule of Stochastic Gradient Descent (SGD) at step t is defined as
W: + W n VRsv (W,-1),
where V, is sampled uniformly without replacement from [N] with size b, Given Wi-1, W, is random with
N b aad E WWi = W VRs (W.-)), Cov [W. [W.] b. 1) W-.
- Covz-s VVR (W, is the covariance of VR, with single drawn from S. The superscript means "single draw". Similarly, we define the population covariance of gradient ypop e Cov DDD (R,(W), We define the Hessian of Rs (W) point W as H.sw
where add
S.W.
The Stochastic Gradient Langevine Dynamics (SGLD) is given by
W, + W 7h VRsv (W,-1) + (0, E, W,-1),,
(3)
where (S, W,-1) .))E E dd is positive semi-definite matrix with dependence on S and W, SGLD (Eq. 3) with (S, W,-) = e,ll where a, positive constant, is called isotropic SGLD, and SGLD with ES W,- dependent on W.- is called state-dependent SGLD.
Statistics for iterative algorithms. Both SGD and SGLD stochastic iterative algorithms [11]. Specifically, the update rule at step of a stochastic iterative algorithm AA can be generally characterized W. M, S, Vi). where V, is the auxiliary random variable at step e.g.. V. in (2) and (3). We use Q..Yrr to denote the joint distribution of (W:)T conditional on V(z;
(S. Vir V.1z to denote the joint distribution of (W.)_. conditional on (S, Vir ). and 2 Viz 1-1, S, Vin).
to denote the distribution of W, conditional on ( (W
Decomposition of KL divergence. The following Lemma is extensively used throughout this paper.
Lemma 1 (Proposition 2.6, [25]). Let Qoer and Po-r two probability measures (T++ with Qu Po. Then, the KL divergence between Que and Poer can be decomposed into
KL(Qo:1 (|Po.))
Σ BQ [KL (Qqjo- Pap--i))
Information theoretical generalization bound. Several existing information-theorriicii bounds [14, 25] share similar framework. We state one representative proposed in [25].
3

---

Proposition 1 (Theorem 2.5 in [25]). Let S be the data set i...d sampled from D, and let the loss function be (a,, 02) bounded. Let A be an algoritim with update rule
We +- M, S.),, Wo Wo-
Let B be another stochastic iterative optimizution algorithm with update rule
W. -
Vi, J), Wo Wo-
where J is sampled uniformly without replacement from [N] with size N - 1. Given S, J. and Vir. denote the joint distribution of (W:)==1 of A as QS. and the joint distribution of of (W) of B as Mm., Then, for any Mrrj. the generalization ervor of A can be bounded as:
S. (m))) RD (Qr (()) Rs (Qr
ES. V
a22 aa)²
RL (Q%.Vm) ().)
This proposition is used to obtain the generalization error bound for SGLD [25, Theorem 3.1] by further combing Lemma 1. As Mer can be arbitrarily picked, P works as an "Auxiliary Line" and called the prior distribution, while Q is the real distribution of parameters called the posterior distribution. In Section 3.2.1, we will argue the difficulty of applying Proposition to analyze the effect of noise structures.
3 Formulate the Problem: Proper Constraints and Optimization Target
In this part, we formulate the optimization problem, i.e., finding the optimal noise covariance of SGLD in terms of the information-theonm theoretical generalization bound, by selecting the proper optimization constraint and optimization target. Specifically, in Section 3.1, we argue that the trace of the noise covariance is proper constraint to ensure the same optimization error; in Section 3.2, we argue that existing generalization bounds are not proper candidates as the optimization target, and propose new information -ioommationtthooetiial bound parallel existing ones but easier to analyze.
3.1 Constraint on the Covariance Control the Empirical Risk
We first derive the constraint of noise covariance E, in Eq. (3) from the perspective of training performance, under which we optimize the generalization bounds in the rest of this paper.
Without any constraint on the noise covariance, optimizing generalization error is trivial but meaning- less: direct combination of Theorem 1 of [37] and Theorem 1 of [28] shows that for isotropic SGLD with Σ, o,Il, the generalization error after T' step satisfies Gerr O log(1 + 1/2) Therefore, as a; + do for i [Z']. we have Gerr + O. but then the update of SGLD is dominated arbitrary bad empirical risk. Hence, we need constraints on the covariance
by the noise, leading in order to control the empirical risk when minimizing the generalization error. Specifically, the expected decrease of the empirical risk for one iteration can be bounded as follows.
Lemma 2. Let empirical risk Rg(W] be B-smooth w.z.. W. Let W(r) be given by dependeen SGLD (Eq. (3)). Then,
( Rw())) S Bt
7111 VRg (wol
1644(N (N - 1)b. Zg.w, E.11 w.)
The proof can be obtained by standard analysis in optimization, and we defer it Appendix B. By Lemma 2, the noise covariance Σ, affects the upper bound of the empirical risk by its trace. Therefore, it is reasonable keep (S, Wi-1)) unchanged while seeking the optimal (,, to minimize the generalization eтror. The constraint is given formally as follows:
The trace of (S W.-1) is fixed when optimizing the generalization error. That is, there exist positive constants e, W.-1) depending S and W,-1, such that,
Constraint 1.
tr W,-1) = CS, W.-1).
We do not put any constraint on the value of e our latter analyses. Therefore, it also possible to manipulate e in order jointly optimize the empirical risk and the generalization bound, which

---

however, is beyond the scope of this paper and we defer it to future works. Similar constraint is also proposed by [40] from the standpoint of kinetic energy when analyzing the effect of noise structure on the escaping efficiency from saddle points.
We next verify this constraint empirically. We run SGLD with different covariances a four-layer neural network for the Fashion-MNIST classification problem. Concretely, the noise covariances are chosen respectively as D Es. w.,, ie., "EC-SGLD" Empirical Covariance SGLD) curve in S. ) i... the "IsD (C)" curve in Fig.2. is easy to verify that Fig.2, and > tr ad
tr( ir(2,-) = tr ), which exactly the Constraint We can see from Fig.2 that the convergence curves corresponding to x)(") and xx² almost coincide with each other, validating the Constraint 1.
In comparison, another quantity tr(Hss,,, Ex). the trace of the empirical risk's Hessian times the empirical covariance, has also been proposed to govern the convergence behavior [34, Theorem 4.1J. We plot the convergence curve of SGLD with noise covariance (3) = tr(Hs.w,,1 "..,: 1
EC-SGLD
Is0-SOLD [C]
Ise SGLD (H)
("Iso-SGLD (H)" in Fig.2). While
w.
(., = tr(Hs,w, ) there is a significant gap between curves of "EC-SGLD" and "Iso-SGLD (H)" in Fig.2. This implies that tr(Hs, w. E,) is not a good constraint for the empirical risk of SGLD, validating the Constraint I from another side.
Training errors of SGLD with different noise variances. The experiment is run on the Fashion- -NNITT dataset with a four-layer neural network (sce Appendix F).
Figure 2:
In the rest this paper, we will optimize the information informatiin-theorrtiiall bound under Constraint ensure low empirical risk.
3.2 New information--thereed Bounds as the Optimization Target
We first demonstrate that existing information -hteorrtiiattoeeicaallll bounds are not suitable for the optimization target in Section 3.2.1. Then we propose new coimaatioon-hhoretiin bound as the optimization target in Section 3.2.2.
3.2.1 Difficulties When Applying Traditional Information-theoreiica Bounds By Lemma 1, the generalization error bound in Proposition 1 can be rewritten as
(a2 -1)=
M KI. (0. (0-1) | p......o))) )
Es.
(4)
For Problem 1, there are two difficulties. For a fixed Q.. in order to obtain the optimal Pala-1) for any E [T], one would first calculate the outside expectation of Eq. (4) over S.= as pSu, Vin independent of Sy.. However, for each term Q, s. KL (Q.k--,) 1 si(o-1) where s E [T].
both the probability measure Q and the function KL d|(=-1) 1 p. has dependency on
Sy= which makes evaluating the generalization bound with respect pSu.Vri extremely hard. Furthermore, when we come to optimize the bound w.r.t. Eyr, for each E, where i [T' 1]. the Eq. (4) depends on E, via two terms and B, where
T
A = E Q
8. KL Viri S. B = (o
i((i-1)
Σ s=++1
Q M.Myo-n
KL (0 ( (
While the first term is easy to deal with as 0,S.V
Vir is irrelevant of E, the second term depends E; via the distribution --y for i+ 1, and can be very complex (please refer to Appendix C.1).
3.2.2 Inforrmation-theorettiall Generalization Bound for Identifying the Noise Effect
We then establish new information-theerrtiee. generalization bound as the optimization target that parallel to the results in [25] but more suitable for analyzing the effect of noise structure. The
5

---

basic idea is to reverse the order of prior and posterior in the KL divergence to let Σg only affect one term in the generalization bound for each when finding the optimal point. The formal theorem stated as follows:
Theorem 1. Let sample set S, mini-batch Viri random subset J. the posterior distribution Q output by Algorithm A with update rule M and the prior distribution P output by Algorithm B with update rule M be defined as Proposition Let [ai, 02) be the range of loss. Then, the generalization error of A can be bounded as
Gerr I Es. Esy.
(az
a1)²
KL (PJ.8 [|Q&.Mm).
Compared to Proposition 1, Theorem 1 can be viewed as a parallel version with the positions of the prior distribution P and the posterior distribution Q reversed. This reverse benefits the optimization of the generalization error bound with respect to the noise covariance under Constraint in two ways. First, by Lemma 1, the KL term in Eq. (5) can be further decomposed into
T
KL (p [|Q = Σ
E M..1 ==1
KL ( 1 (10
Pi
which only each KL term depends on each Σx, respectively. Secondly, for each summand in the above decomposition, only Qa((--1) depends on Syr, making it easy to compute the optimal prior in a "greedy" sense (see details in Section 4).
Hence in the rest of this paper, we study the optimal structure of Σ, in terms of the generalization bound in Theorem under the Constraint 1. Specifically, our ultimate goal can be stated as follows: Problem 1. What is the optimal structure of the noise covariance Σ(r) for SGLD in terms of the generalization bound in Theorem I under the Constraint 1?
In the rest of this paper, we focus on solving Problem 1 and its variants.
Obtain the Optimal Noise Covariance with the Greedy Prior
The generalization bound in Theorem depends both the prior distribution P and the posterior distribution Q (consequently on E(r)). Therefore it requires searching P and Eirj jointly to optimize the generalization error.
In this section, we solve Problem with greedily selected priors. Due to that the square root the bound Eq. (5) make the dependency Enr even more complex, we optimize a slightly different version of the bound by taking the expectation with respect to S into the square root, i.c.,
Geny Vm. (a2 ,1)² Es,. KL (pJ.Ss.M VIQ)..(:).
By Jensen's 's Inequality, Eq. (6) is still generalization bound, but allows the expectation with respect to S to interact with the KL divergence directly. One can easily observe that Geny is mapping from P and Q (and thus from P and E(r)) to a positive real. Therefore, we can reformulate Problem 1 mathematically the following optimization problem (P1):
(P1). min (P, subject to: Constraint 1. P.E
For simplicity, we restrict that the considered noise covariance Egr only depends the parameter W, and is independent of the sample S. By Lemma 1, the KI. term in the optimization target Gent can be decomposed into
KL (p..s.. [QS
Σ
E E.S.S KL p l P
(7)
Therefore, when optimizing Geny with respect to prior P, both KI s[(a-1) |1Q S.V. (e))) and
KI
P. M (i s) have dependence on V. Similar the discussion in Section 3.2.1.
={(a-1) pJ..s.V. can be very complex. Therefore, we the dependence of P. V.S.V with > on s|(s-1) approximate the optimal s|(s-1)
V. by the greedy prior which is defined as follows:

---

Definition (Greedy Prior). We say P is the optimal prior in the greedy sense. or the greedy prior for brevity, for any 1 S T and any SJ and Vin. el(x-1) = =ps. V,, as follows:
el(s-1) where P is defined
A p arg min
min Gen, (P. subject to: Constraint I. E/a
Intuitively, the conditional probability of P of the step is the optimal one if only consider the generalization bound for steps up to s, and a special case is that the step Ii' conditional probability of p agrees with the step I' conditional probability of pf which is the desired optimal prior. This is why we call p "greedy" and use it to approximate the optimal prior.
With the greedy prior, characterize the optimal noise covariance by the following theorem.
Theorem Let the iteration of SGLD with state state-dependen noise Q).V(z) be given as Eq.(3). Under Constraint I, the greedy optimal prior step is given by
W. W (IV [V
N [VI
VRD (WL-)) + (0,
VRsving (Wi-1)+
while the optimal covariance of noise jin for Gent with the greedy prior is given by (((
A(W (EWP)* (Vt E [T]), where (W) = c+((W)))))) tr (r(((W))))
As the sample size is large enough, we have S.W + " almost surely, which demonstrates the similarity between the solution of Problem and the noise covariance of SGD. Also, by the Law of Large Numbers, VRs, = VRD, and the mean of the greedy optimal prior recovers the mean of the prior used [25] (one can also refer to Eq. (10) in this paper for the form).
We briefly state the proof skeleton of Theorem 2, with the proof details deferred to Appendix D. To obtain the final optimal noise covariance Theorem 2, we need to first derive the greedy prior, iee, the optimal conditional distribution Pa](s-1) of the prior of step in terms of the generalization bound Gen,, which has the form
(a2 )2
2 E.S Σ
Esy. Mijid
E M.8 KT. (Piliee)) P
(8)
2
Typically, solving the optimal 1=((s-1) requires optimizing Gen, with respect to all Pa((e-) t and Ld which is still very complex. However, we can tackle this problem in a rather elegant way. We first investigate the optimal noise covariance in terms of single KL divergence term Geng.
Lemma 3. Under Constraint the optimal noise covariance of the following problem
min EsjonD KL (p..s ( 10115-1)) P...
min
(9)
is attained at (W), where (W) is defined as Theorem 2.
By Lemma 3, the optimal solution of Eq. (9) doesn't 't rely on J, S,, or Vía)- On the other hand, by Eq. (()nn)) SJ, Vis) are the only terms depending pJ.Ss.V. V,
(8), ED KL (.,. Q
=1(a-1)
and Σ., Therefore, the optimal Σ, is also X₂ (W) ) which is formally stated the following lemma.
Lemma 4. The optimal Eg and Paf(e-1) in terms Gen, are the same as Σ and P ([(a-1) given by
Theorem 2, respectively.
With the greedy prior derived, we apply it back to the generalization bound Geny. As Gony depends
on Σ, also through Eg KL, V. Theorem 2.
(((--1) ( by applying Lemma again, derive

---

Extension: Optimal Noise Covariance with Fixed Priors
In existing works [25, 12], the prior distribution is set be the SGLD with isotropic noise, which (with the notations Theorem 1) given by
M,(Wi-1, SJ, J)
[IVJ Vil
V VRs, (W--)) + + +N (0, (10) VRsynn (W--1) + [V]
Wi-1
where d, > is the noise scale of prior noise covariance. In our latter analysis, we generalize the prior by allowing depend on W,-1. The formal description of the iteration of the prior is deferred to Appendix E. for completeness.
Therefore, it is also interesting to see what the optimal noise covariance looks like if the prior is fixed the one commonly adopted in the existing analyses, e.g., Eq. (10). We still the optimization constraint the same as Section 4, but change the optimization target little to
(22
a2)² E KT. (PJ.Ss. [[Q.V..).. 2
GenT
Es
By Jensen's 's Inequality and Theorem Genr is still a generalization bound, but allows us to treat the expectation of the KL divergence with respect to V(2 and J for given S whole in optimization. Similar trick is also adopted in [25] to obtain the final generalization error of SGLD. The problem can be mathematically formulated the following optimization problem (P2):
(P2)
min Geur Egr)), subject to: Constraint 1, [
where given by the update rule Eq. (10). As S. is obtained by removing only one sample from the dataset S and the size of S is usually large in practice, it is reasonable to make the assumption that for any fixed Vizj and S, the prior distribution the same regardless of J.
Assumption 1. For any fixed dataset S and miniibatches ViTy. the distribution pJ, M is invariant of J.
We also restrict that (S, W) S da, in order to guarantee the noise scale of the prior comparable to that of the posterior. The optimal noise covariance with prior fixed can then be characterized by the following theorem.
Theorem Let prior and posterior be defined Eq.(10) and E3,(), respectively. Let Assumption I hold. Then, the solution (P2) is given by
(. w) = O'S, Diag(a S.W. S.W
S.W.
(OS.w)
where W.S.W 2 O E [d]) (the form is omitted here) and (Ost 5.w) is the orthogonal matrix that diagonalizes Dnd S.w as Dgeww Oad w any + W; 55
Diag(u, S.W
(Ost.) .Moreover for wid
S.W
S.W S.W and only if S.W S.W
w
The proof together with the the exact formula of S.S.W is deferred to Appendix 5. From Theorem 3, the optimal point (E;)T= is similar to the empirical gradient covariance matrix End in two ways: 1) (E) TT share the same eigenvectors with Ded, 2) the corresponding eigenvalues of Σ; has the same order End Though the value of w.S.W is not comparable to w. S.W because 27 is affected by the prior noise and the posterior noise covariance, which are freely chosen, it can be shown that the condition number of 27 is smaller than S,w (please refer to Appendix E.4 for details).
Theorem also reveals an interesting correlation between the noise covariance matrices of the prior and posterior. While the optimal noise covariance is affected by the prior noise covariance, it also depends on distance between the means of the prior and the posterior (see Lemma in Appendix E.2), which brings the information of empirical gradient covariance into the optimal noise structure. That being said, the optimal posterior noise covariance is biased to the empirical gradient covariance from prior covariance. We note that such analysis can be casily extended to arbitrary priors.

---

T-
SREC 1n0 0G5
to SOLD- 103 FIR NSS
SEEC 2010 tribiigg lose
tnklingg
SALD om
Is0-SGLD
SREC SGLD
(a) trace scale
(b) trace scale =5
Figure 3: The training loss and and the generalization error (test loss training loss) of the Iso-GGLD and SREC-SGLD. Traces of the noise covariance in (a) and (b) are and times of tr((Es, ( )²²), respectively.
Figure 4: Ratio of the 1st to the 500th largest eigenvalue of the empirical gradient covari- ance for two SGLDs.
Empirical Verification
In this section, support our theoretical findings with some experiments. We adopt the setting in [40] where a four-layer neural network with 11330 parameters used to conduct the classification task on the Fashion-MNIST except that We defer detailed settings of the experiments to Appendix F.
10000 training samples instead of 1200 used in [40].
We first verify if the empirical gradient covariance is far from isotropic Gaussian distribution. We plot the ratios of the 1st eigenvalue to the 500th largest eigenvalue of the empirical gradient covariance along the training trajectory of both SGD and Iso- in Figure 4. We can that throughout the training procedure, the ratios of empirical gradient covariance stay around 102 for both SGD and Iso- In constrast, for the isotropic Gaussian, the distribution of eigenvalues follows semi-circle law, and the ratio would be around 1.1 for dimension 11330. This demonstrates that the energy of empirical gradient covariance concentrates in very small subspace, less than 5% of the total 11330 dimensions. Hence the empirical gradient covariance is highly anisotropic.
We next verify our main claim Theorem 2 that under Constraint 1, the generalization error for SGLD with the optimal noise covariance is much smaller than that for Iso-SGLD, Specifically, we consider the SGLD with noise covariance equal to the (scaled) square root of the empirical gradient covariance, coined "SREC-SGLD". We compare the training loss and the generalization error of SREC-SGLD that
and SSDD under Constraint on the noise covariance trace. From Figure 3, we the generalization error of SREC-SGLD is smaller than Iso-SGLD for different noise trace scales, which supports Theorem 2. Moreover, if we look the training loss curves, the SREC-SGLD and Iso-GLLD behave almost the same for the same noise trace scale, which supports Lemma 2.
Finally though our analysis does not cover the generalization bound for SGD, we further empirically show how SREC-SGLD performs comparison with SGD and the Iso-SGLD in Figure 1. We can see that with the same noise trace scale, SREC indeed provides more accurate characterization of SGD compared to Iso-SGLD.
Conclusion and Future Direction
In this paper, study the optimal noise covariance of SGLD in terms of its generalization ability. Specifically, we first formulate the optimization problem both by deriving constraints from the optimization performance and proposing the optimization target by constructing new information theoretical bound. We then solve the problem with both greedy optimal prior and fixed prior. Interest- ingly, observe that the optimal noise covariance aligns with the empirical gradient covariance, which indicates the superiority of the noise covariance of SGD in terms of generalization.
Acknowledgement
The authors would like to thank Mr. Ziming Liu for helpful theoretical discussions.

---

References
[1] S. Arora, R. Ge, B. Neyshabur, and Y. Zhang. Stronger generalization bounds for deep nets via
a compression approach. In International Conference on Machine Learning, pages 254-263 PMLR, 2018.
[2] A. R. Asadi, E. Abbe, and S. Verdú. Chaining mutual information and tightening generalization bounds. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[3] S. Boucheron, G. Lugosi, and Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013.
[4] O. Bousquet, S. Boucheron, and G. Lugosi. Introduction to statistical learning theory. In Summer School on Machine Learning, pages 169 (69-207. Springer, 2003.
[5] Y. Bu, Zou, and V. Veeravalli. Tightening mutual information- bounds on generaliza- tion error. IFEE Journal on Selected Areas in Information Theory, 1(1):121-130, 2020.
[6] Z. Charles and D. Papailiopoulos. Stability and generalization of learning algorithms that converge to global optima. In International Conference on Machine Learning, pages 745-754. PMLR, 2018.
[7] T. M. Cover and J. A. Thomas. Elements of information theory. Wiley, 2001.
[8] C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth. Generalization in adaptive data analysis and holdout reuse. In Advances in Neural Information Processing Systems, 2015.
[9] G. K. Dziugaite and D. M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint 1rXiv:1703. 1008, 2017.
[10] V. Feldman and T. Steinke, Calibrating noise to variance in adaptive data analysis. In Conference
On Learning Theory, pages 535-544. PMLR, 2018.
[11] S. B. Gelfand and S. K. Mitter. Recursive stochastic algorithms for global optimization in r'd. SIAM Journal on Control and Optimization, (((5):999-1011)) 1991.
[12] N. Gergely, G. K. Dziugaite, M. Haghifam, and D. M. Roy. Information-theonee generalization bounds for stochastic gradient descent. In COLT, 2021.
[13] H. Hafez-Kolahi, Z. Golgooni, S. Kasaei, and M. Soleymani. Conditioning and processing: Techniques improve information-theoreete generalization bounds. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
[14] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite. Sharpened generalization bounds based conditional mutual information and application to noisy, iterative algorithms. arXiv preprint arXiv:2004. 12983, 2020.
[15] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference Machine Learning, pages 1225-1234. PMLR, 2016.
[16] I. Issa, A. R. Esposito, and M. Gastpar. Strengthened coummation-theorele bounds on the generalization error. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 582-586. IEEE, 2019.
[17] Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures and where to find them. In International Conference on Learning Representations, 2019.
[18) N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang. On large-batch train- ing for deep learning: Generalization gap and sharp minima. arXiv preprint 11Xiv.1609.04836 2016.
[19] I. Kuzborskij and C. Lampert. Data-dependent stability of stochastic gradient descent. In International Conference Machine Learning, pages 2815-2824, PMLR, 2018.
[20] Y. Lei and Y. Ying. Sharper generalization bounds for learning with gradient- doddintt-d objective functions. In International Conference on Learning Representations, 2021.
[21] Li, X. Luo, and M. Qiao. On generalization error bounds of noisy gradient methods for non-convex learning, In International Conference on Learning Representations, 2019.
10

---

[22] S. Mandt, M. D. Hoffman, and D. M. Blei. Stochastic gradient descent as approximate Bayesian inference. The Journal of Machine Learning Research, 18(1):4873-4901 2017.
[23] Q. Meng, S. Gong, W. Chen, Z.-M. Ma, and T.-Y. Liu. Dynamic of stochastic gradient descent with state-dependent noise. arXiv preprint arXiv:2006. 13719, 2020.
[24] W. Mou, L. Wang, X. Zhai, and K. Zheng. Generalization bounds of SGLD for non-convex learning: Two theoretical viewpoints. In Conference on Learning Theory, pages 605-638. PMLR, 2018.
[25] Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy. Information -hheoreti generalization bounds for SGLD via data-dependent estimates. arXiv preprint arXiv: 1911.0215, 2019.
[26] B. Neyshabur, S. Bhojanapalli, and N. Srebro. A PAC-Bayesian approach spectrally- normalized margin bounds for neural networks. In International Conference on Learning Representations, 2018.
[27] E. Harrado-Heránnder A. Ambroladze, J. Shawe-Taylor and S. Sun. PAC-Bayes bounds with data dependent priors. The Journal of Machine Learning Research, 13(1):3507-3331, 2012.
[28] A. Pensia, V. Jog, and P.-L.. Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550. IEEE, 2018.
[29] M. Raginsky, A. Rakhlin, and M. Telgarsky. Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis. In Conference on Learning Theory, pages 1674-1703. PMLR, 2017.
[30] D. Russo and J. Zou. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pages 1232-1240. PMLR, 2016.
[31] T. Steinke and L. Zakynthinou. Reasoning about generalization via conditional mutual informa- tion. In Conference on Learning Theory, pages 3437-3452. PMLR, 2020.
[32] G. Strang, G. Strang, G. Strang, and G. Strang. Introduction to linear algebra, volume 3. Welleslyy-Cambride Press Wellesley, MA, 1993.
[33] M. Welling and Y. W. Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference on machine learning (ICML-II), pages
681-688, Citeseer, 2011.
[34] Y. Wen, K. Luk, M. Gazeau, G. Zhang, H. Chan, and J. Ba. An empirical study of large-batch stochastic gradient descent with structured covariance noise, arXiv e-prints, pages arXiv-1902, 2019.
[35] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. arXiv preprint 170.:v::770.777200 2017.
[36] Z. Xie, I. Sato, and M. Sugiyama. diffusion theory for deep learning dynamics: Stochastic gra- dient descent escapes from sharp minima exponentially fast. arXiv preprint arXiv:2002.03499 2020.
[37] A. Xu and M. Raginsky. thformation-thhoreticc analysis of generalization capability of learning algorithms. arXiv preprint arXiv: 1 775.07889, 2017.
[38] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
[39] W. Zhou, V. Veitch, M. Austern, R. P. Adams, and P. Orbanz. Non-vacuous generalization bounds the imagenet scale: PAC-Bayesian compression approach. In International Confer- ence on Learning Representations, 2018
[40] Z. Zhu, J. Wu, B. Yu, L. Wu, and J. Ma. The anisotropic noise in stochastic gradient de- scent: Its behavior of escaping from sharp minima and regularization effects. arXiv preprint 18Xiv:1803.00 00195, 2018
11


Reviews:
[{"review_id": "sb4mVrBSzC3", "reviewer": "Reviewer_ha8D", "summary": "This interesting paper studies the connection between generalization abilities of of SGLD and the covariance structure of its noise term. It first proves that with constraint to guarantee low empirical risk and commonly used data-dependent priors, the optimal noise covariance of SGLD in terms of the bound is similar to the empirical gradient covariance. The paper further proves that if the generalization bound is jointly optimized with respect to both prior and posterior, the optimal noise covariance is the square root of the expected gradient covariance. These facts can be used to further support the belief of the superiority of SGD noise over isotropic noise.", "questions": "", "limitations": "", "rating": 7, "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": "This paper studies the connection between generalization abilities of of SGLD and the covariance structure of its noise term. It proves that with constraint to guarantee low empirical risk and commonly used data-dependent priors, the optimal noise covariance of SGLD in terms of the bound is similar to the empirical gradient covariance. The paper further proves that if the generalization bound is jointly optimized with respect to both prior and posterior, the optimal noise covariance is the square root of the expected gradient covariance. Overall, the concern of optimization methods with generalization abilties from the viewpoint of noise covariance structure is novel, interesting and important. It is important because these facts can be used to further support the belief of the superiority of SGD noise over isotropic noise, an important theme towards the understanding of implicit regularization of SGD.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "sTRlQKGG9b4", "reviewer": "Reviewer_TVaS", "summary": "This paper studies optimization of the information theoretical generalization bounds of Stochastic Gradient Langevin Dynamics (SGLD) with respect to the noise covariance. Here are the main findings:\n* When updating rule is fixed and only optimizing noise covariance under the constraint that the trace of the covariance is fixed, the noise covariance of SGLD is similar to the empirical gradient covariance\n* When both updating rule and the noise covariance are jointly minimized, the noise covariance of SGLD is the square root of the expected gradient covariance. \nThe two results can potentially be used to improve information theoretical generalization bounds obtained in the literature. The theoretical results are validated by some numerical experiments. \n", "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": "SGLD is a popular stochastic optimization algorithm used in practical training of neural networks. Its generalization property is an important issue and is worth to study. The present work aims (and manages) to improve information theoretical generalization bounds obtained in the literature (e.g. Refs [24,13]) by optimizing the noise covariance. However, I do have some concerns on the results.\n* My major concern is about the usefulness of the information theoretical generalization bounds. From my perspective, the generalization bound in Theorem 2 seems very brutal. The reason is that I would expect the generalization error to decrease or at least not increase with respect to the training time $T$, while the right hand side of Eqn (7) increases linearly in $T$ as it involves the relative entropy between two measures on the whole path space of trajectories. If the upper bound is brutal, then I do not see the point of optimizing the right hand side since it is not likely to improve the actual generalization error.\n* Speaking about the information theoretical bound, I would think of a lower bound (rather than upper bound) for the generalization error involving information quantities, such as relative entropy or mutual information. This is because it is the lower bound that reflects the fundamental information limit of a learning algorithm (SGLD in this case). \n* In Figure 2, I do not see why the generalization error could increase along the epoch. Is the figure showing the information theoretical upper bound or the actual generalization error? If it is the former, please specify this in the figure. \n* The improvement of SREGC-SGLD over IS-SGLD seems not convincing in Figure 2.c since all the curves are nearly aligned with each other.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48 hours"}, "extra_text": {}}, {"review_id": "rXoFnVEd9Mi", "reviewer": "Reviewer_Mhnz", "summary": "This paper considers the problem of understanding the generalization of the SGLD algorithms using information-theoretic techniques. This line of work initiates by [27],[24], and [13]. The goal in this paper is to \"modify\" the SGLD algorithms such that it has a good generalization properties and good performance on the training set. Basically, the modification that the authors considered is to make the covariance of the Gaussian noise in the SGLD update to depend on the trajectory. Note that in the usual setting the noise is isotropic. Then, authors claim that controlling the trace of the SGLD ensures we have good performance on training set and good generalization. Then the authors provide a generalization bound which uses reverse KL between posterior and the prior distribution. I think this bound is not true as stated in my review. Since this bound has been used in the paper, I think the authors should comment on the validity of the theorem.", "questions": "", "limitations": "", "rating": 6, "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": "- The presentation of the paper is not good.\n\n- Why the assumption 1 is a valid assumption? There is no discussion in the paper.\n\n- I think Theorem 2 in the paper is NOT CORRECT. I will provide a counterexample here. Assume that we have a finite hypothesis class $H= \\{ h_1,...,h_M \\} $. Assume the learner is an \"ERM\" so after receiving a training set it outputs a single hypothesis that minimizes the empirical error. Assume we have a consistent way to break the ties. For instance we choose the hypothesis with smallest index. Therefore the posterior distribution is $Q^{S}= \\delta_{h_{i^\\star}}$ where $h_{i^\\star}$ is the ERM classifier. Assume based on your generalization bound in Theorem 2, we choose the uniform prior over the set of hypothesis, i.e., $P(h_i)=\\frac{1}{M}$. Based on this theorem $KL(P||Q)=\\frac{1}{M}\\log \\frac{1}{M}$. Therefore we obtain   $EGE<\\sqrt{\\frac{1}{2}\\frac{1}{M}\\log \\frac{1}{M}}$. It implies that when $M\\to \\infty$, the generalization bound becomes smaller!!!  From the first part of \"Understanding machine learning: From theory to algorithms\" we know the expected generalization error is upper and lower bounded by $\\log(M)$. Therefore this example depicts that this bound can't be true. I also checked the proof and the proof also has error in Lines 584 and 585.  \n\nThe main reason is that similar to PAC-Bayesian bounds we can't have upper bound with \"revers KL\" between the posterior and prior.\n\n\nAs this bound is used all over the paper, I appreciate if the authors comment on how this theorem affects the paper's conclusion. Also if there is a misunderstanding by me, please let me know.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have some concern on the validity of one of the main results in the paper.", "review_text": "", "extra_scores": {"ethical_concerns": "There is no ethical concern with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "FsZC55P2zme", "reviewer": "Reviewer_Zcyu", "summary": "This paper study the interplay between generalization bound and the covariance of perturbed gradient descent. The authors invoke a recent (information-theoretic) bound for stochastic optimization methods. Then, they optimize the upper bound with respect to trace constraint on the covariance of noise in each step and experimentally show that this optimization may be effective for training neural networks. ", "questions": "", "limitations": "", "rating": 6, "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": "I could not follow the statement of theorems and theoretical results. Definitely, the paper requires refinement of notations and also writing. \n\nI can not understand the notations in Propostion1. In equation 4, what is exactly the risk for a joint distribution $Q_T^{S,V_T}$? The input of the risk has to be a parameter, not the joint distribution of a stochastic process. \n\nI am not sure whether I understood the statement of Proposition 1 and Theorem 1. Suppose that $T=0$, then the starting distribution is the same so the right side of equations 4 and 6 is zero. But the left side is $R_D(W_0) -R_S(W_0)$ which is not necessarily less than zero. Intuitively, if the algorithm is deterministic, still the generalization error is not zero. Should not use an absolute value for the left side of the generalization error? \n\nThe optimality is not defined well. The target objective is optimizing the divergence of test error from the training error under a trace constraint for the covariance of the noise, which is meaningless. The optimal algorithm requires to achieve the lowest level of the test error. Indeed, authors require to minimize $$ E [R_D(W_T)] $$  which I am not sure whether is possible. \n\nOne of the claims in the introduction is that the optimal covariance matrices found in this paper match the covariance of stochastic gradient descent. I saw in experiments there is one result indicating anti-isotropy of the noise of stochastic gradients which is a known fact in the literature. Is there any other result that shows the optimal covariance matrices extracted by the proposed algorithm is similar to the covariance structure of stochastic gradients during training? \n\n\n**Post Rebuttal**\n\n\nI thank the authors for their detailed responses that helped me to understand the results better. Now, I understand Lemma 2 and the role of the trace constraint in optimization. After a more careful study, I decided to increase my score. This paper is rather difficult to follow due to the use of complicated notations and I highly recommend the authors to improve the writing. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "A0l3212Lya-", "reviewer": "Reviewer_DUnn", "summary": "From usual isentropic noise to data-dependent priors, the authors extend the existing information-theoretic analysis of SGLD. Additionally, they identify the optimal choice of prior distribution covariance. Last but not least, the paper includes empirical observations to validate its technical findings.", "questions": "", "limitations": "", "rating": 6, "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": "I must admit that I am not an expert in this field. Nevertheless, the paper is very well-written, the literature review is extensive, and the technical contributions appear to be solid. Bellow you can find my comments.\n\n- Is there a regularity condition (such as having a full-rank matrix) for the covariance matrix \\Sigma_{S, W}^{sd}? \n\n- How do you compare the value of \\tilde \\sigma_{i}^{S, W} and \\sigma_{i}^{S, W}? Which one is larger, and can we conclude that the condition number of \\Sigma_t^\\star is larger than the condition number of \\Sigma_{S, W}^{sd}?\n\n- Does \\Sigma_t^\\star converge to a certain matrix as t tends to infinity?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "  ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the connection between the generalization ability of SGLD and the covariance structure of its noise term. The reviewers initially had a lot of concerns about the lack of clarity of the paper and some details in the derivation of the proofs. Most of these concerns were addressed by the authors in the rebuttal and some reviewers raised their scores as a result. Overall, the contribution made in the paper is seen as interesting and worthy of acceptance. However, many reviewers, and myself included, think that the writing in some sections of the paper and the clarity are poor. I strongly advise the authors to follow the suggestions made by the reviewers to improve the manuscript for the camera-ready version.
Decision: Accept (Poster)