Improving Sampling Accuracy of Stochastic Gradient MCMC Methods via Non-uniform Subsampling of Gradients
Authors: Ruilin Li
Xin Wang
Hongyuan Zha
Molei Tao
Venue:  (2021)
Keywords: SG-MCMC
Non-uniform weight

Abstract: Common Stochastic Gradient MCMC methods approximate gradients by stochastic ones via uniformly subsampled data points. A non-uniform subsampling scheme, however, can reduce the variance introduced by the stochastic approximation and make the sampling of a target distribution more accurate. For this purpose, an exponentially weighted stochastic gradient approach (EWSG) is developed to match the transition kernel of a non-uniform-SG-MCMC method with that of a batch-gradient-MCMC method. If needed to be put in the importance sampling (IS) category, EWSG can be viewed as a way to extend the IS+SG approach successful for optimization to the sampling setup. EWSG works for a range of MCMC methods, and a demonstration on Stochastic-Gradient 2nd-order Langevin is provided. In our practical implementation of EWSG, the non-uniform subsampling is performed efficiently via a Metropolis-Hasting chain on the data index, which is coupled to the sampling algorithm. The fact that our method has reduced local variance with high probability is theoretically analyzed. A non-asymptotic global error analysis is also presented. As a practical implementation contains hyperparameters, numerical experiments based on both synthetic and real world data sets are provided, to both demonstrate the empirical performances and recommend hyperparameter choices. Notably, while statistical accuracy has improved, the speed of convergence, with appropriately chosen hyper-parameters, was empirically observed to be at least comparable to the uniform version, which renders EWSG a practically useful alternative to common variance reduction treatments.

Under review as a conference paper at ICLR 2021
IMPROVING SAMPLING ACCURACY OF STOCHASTIC GRADIENT MCMC METHODS VIA NON-UNIFORM SUBSAMPLING OF GRADIENTS
Anonymous authors Paper under double-bling brindd review
ABSTRACT
Common Stochastic Gradient MCMC methods approximate gradients by stochas- tic ones via uniformly subsampled data points. A non-uniform subsampling scheme, however, can reduce the variance introduced by the stochastic approx- imation and make the sampling of target distribution more accurate. For this purpose, an exponentially weighted stochastic gradient approach (EWSG) is de- veloped to match the transition kernel of Non-unnform-SG-MMMMC method with that of natch-gradient-MMMM sampling (IS) category, EWSG can be viewed as way extend the IS+SG ap- proach successful for optimization to the sampling setup. EWSG works for a range of MCMC methods, and a demonstration Langevin is provided. In our practical implementation of EWSG, the non- non-uniform subsampling is performed efficiently via Metropolis-Hasee index, which is coupled to the sampling algorithm. The fact that our method has reduced local variance with high probability theoretically analyzed. non- asymptotic global eπrоr analysis is also presented. As a practical implementation contains hyperparameters, numerical experiments based on both synthetic and real world data sets are provided, to both demonstrate the empirical performances and recommend hyperparameter choices. Notably, while statistical accuracy has im- proved, the speed of convergence, with appropriately chosen syper-parameters. was empirically observed to be at least comparable to the uniform version, which renders EWSG practically useful alternative to common variance reduction treat- ments.
method. needed to be put in the importance
Stochastic-Gradient 2nd-order
chain on the data
INTRODUCTION
Many MCMC methods use physics-inspine evolution such as Langevin dynamics (Brooks al., 2011) to utilize gradient information for exploring posterior distributions over continuous parameter space efficiently. However, gradient-based MCMC methods are often limited by the computational cost of computing the gradient on large data sets. Motivated by the great success of stochastic gradient methods for optimization, stochastic gradient MCMC methods (SG-MCMC) for sampling batch
have also been gaining increasing attention. When the accurate but sepensive-to-evaluee gradients in a MCMC method are replaced by computationally cheaper estimates based on a subset of the data, the method is turned to a stochastic gradient version. Classical examples include SG (overdamped) Langevin Dynamics (Welling & Teh, 201 1) and SG Hamiltonian Monte Carlo (Chen et al., 2014), all of which were designed for scalability suitable for machine learning tasks.
However, directly replacing the batch gradient by a (uniform) stochastic one without additional mitigation will generally cause MCMC method to sample from a statistical distribution different from the target, because the transition kernel of the MCMC method gets corrupted by the noise of subsampled gradient. In general, the additional noise is tolerable if the learning rate/step size is tiny or decreasing. However, when large steps are used for better efficiency, the extra noise non- negligible and undermines the performance of downstream applications such as Bayesian inference.
In this paper, we present a state-dependent non-uniform SG-MCMC algorithm termed Exponen- tially Weighted Stochastic Gradients method (EWSG), which continues the efforts of uniform SG-

---

Under review as a conference paper at ICLR 2021
MCMC methods for better scalability. Our approach is based on designing the transition kernel of a SG-MCMC method to match the transition kernel of a cull-gradient- based MCMC method. This matching leads to non-uniform (in fact, exponential) weights that aim at capturing the entire state- variable distribution of the full-gradient-based MCMC method, rather than just providing unbiased gradient estimator reducing its variance. When focusing on the variance, the advantage of EWSG is the following: recall the stochasticity of a SG-MCMC method can be decomposed into the intrin- sic randomness of MCMC and the randomness introduced by gradient subsampling; in conventional uniform subsampling treatments, the latter randomness is independent of the former, and thus when they are coupled together, variances add up: EWSG, on the other hand, dynamically chooses the weight of each datum according to the current state of the MCMC, and thus the variances do not add up due to dependence. However, the gained accuracy is beyond reduced variance, as EWSG, when converged, samples from a distribution close to the invariant distribution of the full-gradient MCMC method (which has no variance of the 2nd type), because its transition kernel (of the corresponding Markov process) is close to that of the full-gradient-Ne MMMB-rrrrden-MMMMCCC method. This is how better sampling accuracy can be achieved.
Our main demonstration of EWSG is based on 2nd-order Langevin equations (a.k.a. inertial, kinetic, or underdamped Langevin), although it works for other MCMC methods too (e.g., Sec.F,G). To concentrate the role of non-uniform SG weights, fact that EWSG has locally reduced variance than its uniform counterpart is rigorously shown in Theorem 3, and a global non-asymptotic analysis of EWSG is given in Theorem 4 quantify its convergence properties and demonstrate the advantage over its uniform SG counterpart.
will work with constant step sizes only. The
A number of experiments on synthetic and real world data sets, across downstream tasks including Bayesian logistic regression and Bayesian neural networks, are conducted to validate our theoretical results and demonstrate the effectiveness of EWSG. In addition to improved accuracy, the conver- gence speed was empirically observed, in a fair comparison setup based on the same data pass, to be comparable to its uniform counterpart when vergence (per data pass) was also seen to be clearly faster than classical Variance Reduction (VR) approach (note: for sampling, not optimization), and EWSG hence provides a useful alternative to VR. Additional theoretical investigation of EWSG convergence speed is provided in Sec. I.
are appropriately chosen. The con-
Terminology-wir VV will be called the full/batch-gradient, VV, with random I will be called stochastic gradient (SG), and when I is uniform distributed it will be called a uniform SG/subsampling. otherwise non non-uniform. When uniform SG is used to approximate the batch- gradient in underdamped Langevin, the method will be referred to as (vanilla) stochastic gradient underdamped Langevin dynamics (SGULD/SGHMC)) and it serves as a baseline in experiments.
2 RELATED WORK
Stochastic Gradient MCMC Methods Since the seminal work of SGLD (Welling & Tch, 2011 D), much progress (Ahn et al., 2012; Patterson & Teh, 2013) has been made in the field of SG-MCMC. Teh et al. (2016) theoretically justified the convergence of SGLD and offered practical guidance on tuning step size. Li et al. (2016) introduced a preconditioner and improved stability of SGLD. We also refer to Maclaurin & Adams (2015) and Fu & Zhang (2017) which will be discussed in Sec.5. While these work were mostly based on Ist-order (overdamped) Langevin, other dynamics were considered too. For instance, Chen et al. (2014) proposed SGHMC, which is closely related to 2nd- order Langevin dynamies (Bou-Rabee & Sanz-Serna, 2018: Bou-Rabee et al., 2018), and Ma et al. (2015) put it in a more general framework. 2nd-order I Langevin was recently shown to be faster than the I st-order version in appropriate setups (Cheng et al., 201 8b;a) and began to gain more attention.
Variance Reduction For optimization, vanilla SG methods usually find approximate solutions quickly but the convergence slows down when an accurate solution is needed (Bach, 2013; Johnson & Zhang, 2013). SAG (Schmidt et al., 2017) improved the convergence speed of stochastic gradient methods to linear, which is the same as gradient descent methods with full gradient, at the expense of large memory overhead. SVRG (Johnson & Zhang, 2013) successfully reduced this memory over- head. SAGA (Defazio et al., 2014) furthers improved convergence speed over SAG and SVRG. For
SGGULD&E is the same as the well-known SGHMC with B 0, see (Chen et al., 2014, Eq (13) and section 3.3) for details. To he consistent with existing literature, we will refer SGULD SGHMC in the sequel.
2

---

Under review as a conference paper at ICLR 2021
sampling, Dubey et al. (2016) applied VR techniques to SGLD (see also (Baker et al., 2019; Chat- terji et al., 2018)). However, many VR methods have large memory overhead and/or periodically use the whole data set for gradient estimation calibration, and hence can be resource-demandiin
EWSG is derived based on matching transition kernels of MCMC and improves the accuracy of the entire distribution rather than just the variance. However, it does have consequence of variance reduction and thus can be implicitly regarded as a VR method. When compared to the classic work on VR for SG-MCMC (Dubey et al., 2016), EWSG converges faster when the same amount of data pass is used, although its sampling accuracy is below that of VR for Gaussian targets (but well above vanilla SG; Sec.5.1). In this sense, EWSG and VR suit different application domains: EWSG can replace vanilla SG for tasks in which the priority is speed and then accuracy, as it keeps the speed but improves the aceuracy; on the other hand, VR remains to be the heavy weapon for accuracy- demanding scenarios. Importantly, EWSG, as a generic way to improve SG-MCMC methods, can be combined with VR too (e.g., Sec.G); thus, they are not exclusive or competitors.
Importance Sampling (IS) IS employs nonuniform weights to improve SG methods for opti- mization. Traditional IS uses fixes weights that do not change along iterations, and the weight com- putation requires prior information of gradient terms, e.g., Lipschitz constants of gradient (Needell et al., 2014; Schmidt et al., 2015; Csiba & Richtárik, 2018), which are usually unknown or diffi- cult to estimate. Adaptive IS was also proposed in which the importance was re-evaluated at each iteration, whose computation usually required the entire data set per iteration and may also require information like the upper bound of gradient (Zhao & Zhang, 2015; Zhu, 2016).
For sampling, it is not easy to combine IS with SG (Fu & Zhang. 2017); the same paper is, to knowledge, the closest to this goal and will be compared with in Sec.5.3. EWSG can be viewed as a way to combine (adaptive) IS with SG for efficient sampling. It require oracle about the gradient, nor any evaluation over the full data set. Instead, an inner-loop Metropolis chain maintains a random index that approximates a state-dependent non-uniform distribution (i.e. the weights/importancee.
3 UNDERDAMPED LANGEVIN: THE BACKGROUND OF A MCMC METHOD
Underdamped Langevin Dynamics (ULD) is d0 =dtt
(1)
dr (VV(0) + dt adW
where 0,r r E Rd state and momentum variables, V is potential energy function which in our context (originated from cost minimization or Bayesian inference over many data) is the sum of many terms V()) Σ (i), Y is friction coefficient, is intrinsic noise ampli- tude, and W is standard d-dimensional Wiener process. Under mild assumptions on the po- tential V. (Pavliotis, 2014), Langevin dynamics admits unique invariant distribution T(0,)) r)
exp (V + = and is in many cases geometric ergodic. T is the temperature of system determined via the fluctuation dissipation theorem 6² 2-T (Kubo, 1966).
The main reason for considering ULD rather than overdamped one is that ULD can converge faster than overdamped Langevin, in particular in high-dimension space (e.g..Cheng al. (2018b;a); Tao & Ohsawa (2020)). Like the overdamped version, numerical integrators for ULD with well captured statistical properties of the continuous process have been extensively investigated (e.g, Roberts al. (1996); Bou-Rabee & Owhadi (2010)), and both the overdamped and underdamped integrators are friendly to derivations that will allow us to obtain explicit expressions of the non-uniform weights.
4
MAIN WORK
4.1
AN ILLUSTRATION OF NON-OPTIMALITY OF UNIFORM SUBSAMPLING
In many applications, cases where data size n is larger than dimension d are not uncommon. In such cases, (V%) C Rd are linearly dependent and hence it likely that there exist probability distributions ( an other than the uniform one such that the gradient estimate is unbiased. This opens up the door to develop non-uniform subsampling schemes (weights may be A dependent),
3

---

Under review as a conference paper at ICLR 2021
which can help reduce introduced additional variance while maintaining unbiasedness. In fact, in reasonable setup, it turns out an optimal way of subsampling gradients, is far from being uniform:
Theorem Suppose given 0 R&,, the errors of SG approximation b, nVV.()) VV)
i S n are Lidd absolutely continuous random vectors with possibly-O-deeeenden density p( Define p E R" as a sparse vector if the number of non-zero entries in p is no greater than d + 1. Then with probability 1, the optimal probability distribution p" that is unbiased and minimizes the trace of the covariance of NVVi(()) i.e. p' which solves the following, is a sparse vector.
min (r( s.t. Ei~plbr] = =0
(2)
Despite the sparsity of p", which seemingly suggests one only needs most d+ gradient terms per iteration when using SG methods, it is not practical because p' requires solving the linear program- ming problem (2) in Theorem I, for which an entire data pass is needed. Nevertheless, this result shows uniform SG can be far from optimal and motivates us to propose an exponentially weighted stochastic gradient method, which has reduced local variance with high probability and at the same time remains efficiently implementable without necessarily using all the data per parameter update.
4.2 EXPONENTIALLY WEIGHTED STOCHASTIC GRADIENT
MCMC methods or Markov processes in general are characterized by their transition kernels. In traditional SG-MCMC methods, uniform SG is used, which is completely independent of the in- trinsic randomness of MCMC methods (c.g. diffusion in ULD). as result, the transition kernel of SG-MCMC method can be quite different from that with full gradient. Therefore, it is natural to ask - it possible to couple these two originally independent randomness so that the transition kernels can be better matched and the sampling accuracy be hence improved?
Consider Euler- Mally-Maruyamaa (EM) discretization' of Equation (1):
0b++1 02 + rsh
(3)
[re+1 T (VV TTR) + +OVTE
where h is step size and E1+13s 's are i.i.d. d-dimensional standard Gaussian random variables. De- note the transition kernel of EM discretization with full gradient by pEM (0 Fa+1 [0,, rx)) If
(Ox))) is replaced by weighted SG SG (0x), where 4 is the index chosen to approximate full gradient and has p.m.f (I turns out that we can choose P; smartly to match the two transition kernels:
Pts denote the transition kernel by PEM (0k+1, Tk+1 0x, rk).
Pe+1 t and a; vEVV)(0.) If we set ovh
Theorem 2 Denote
x + E}=1 131?
| na, 1
Pi = 2- exp
(4)
2
2
where Z is a normalization constant, then the two transition kernels are identical, i.e.,
PEM (0s41, T Ox, rx) = P.M (0x+1, T Ok, (0krra rk)
We refer to this choice of p; Exponentially Weighted Stochastic Gradient (EWSG). Note the idea of designing non-uniform weights of SG-MCMC match the transition kernel of full gradient can be suitably applied to a wide class of muddient-based MCMC methods; for example, Sec.F shows how EWSG can be applied Langevin Monte Carlo (overdamped Langevin), and Sec.G shows how it can be combined with VR. Therefore, EWSG complements a wide range of SG-MCMC methods.
Thm.2 establishes the advantage of EWSG over vanilla SG, as this ideal version reproduces the dis- tribution of a full-gradient MCMC method. As special but commonly interested accuracy measure, the smaller variance of EWSG now shown with high probability
?M is not the most accurate or robust discretization, see e.g., (Roberts al.. 1996: Bou-Rabee & Owhadi, 2010), but since may still be the most used method, demonstrations in this artiele will he based on EM. The same idea of FWSG can easily apply to most other discretizations such as GLA (Bou- Rahee Owhadi, 2010).
With high probability' but not almost surely because Thm.3 is not tight it can handle more general weights, including only the ideal EWSG weights (4) hut also their appropriate approximations.
4

---

Under review as a conference paper at ICLR 2021
Theorem 3 Assume (VV:(0)) 1=1,2,,---..- are i.dd random vectors and [V. I R for some constant R almost surety. Denote the uniform distribution over [n] by p", the exponentially weighted distribution by p", and let A = (I(covi.-=((/VVV(())
covi-p" covi-pu/nVVii [NVV( If
O(vh), we have B[A] < 0, and 3C > 0 independent of n or h such thut for any > 0. P(IA - E| 2 <) S 2xxp
nCR!
It is not surprising that less non-intrinsic local variance correlates with better global statistical accu- racy, which will be made explicit and rigorous in Section 4.4.
4.3 PRACTICAL IMPLEMENTATION
In EWSG, the probability of each gradient term is p: = 2 exp
l > 0gll
| na.
2
Although the term || + Σラ= a,1l²/ /2 depends on the full data set, is shared by all p and can be absorbed into the normalization constant 2-1 (we still included it explicitly due the needs of analyses in proofs); unique to each p; is only the term || + n2,112/2, This motivates us to run a Sattooools-Hastinge chain over the possible indices i E {1,2 proposal of index is uniformly drawn, and then accepted with probability
.2): each inner-loop step,
P(i + min {
> + na,l 1|
x nax 11
1, exp
(5)
2
2
if accepted, the current index i will be replaced by j. When the chain converges, the index will follow the distribution given by pc. The advantage is, we avoid passing through the entire data sets to compute each pt, but yet the index will still sample from the non-uniform distribution efficiently.
In practice, we often only perform M = 1 step of the Metropolis index chain per integration step, especially if h is not too large. The rationale is, when f is small, the outer iteration evolves slower than the index chain, and as does not change much in, say, N outer steps, effectively N x M inner steps take place almost the same index chain, which makes the index r.v. equilibrate better. Regarding the larger case (where the efficacy of local variance reduction via non-unifone sub- sampling is more pronounced; see e.g., Thm.4), M 1 may no longer be the optimal choice, but improved sampling with large h and M = is still clearly observed in various experiments (Sec.5).
Another typeer-parameter is æ. because p: essentially depends on the future state ok+1 via æ, which we do not know, and yet we'd like to avoid expensive nonlinear solves. Therefore, in our experi- ments, we choose æ yTryr, That corresponds a deterministic maximum likelihood estimation of rR+1 = TR, which is sufficient (but not necessary) condition for mimicking the statistical equi- librium at which rk+11 and F are equal in distribution. This approximation turned out to be good one in all our experiments with medium / and M 1. Because it is only approximation, when is large, the method still introduces extra variance (smaller than that caused by vanilla stochastic gradient variant, though), and larger M may actually decrease the accuracy of sampling.
Sec.5.1 further investigates hyperparameters and they affect our non-asymptotic theory in Sec.4.4.
FWSG algorithm is summarized in Algorithm 1. For simplicity of notation, we restrict the descrip- tion to mini batch size b = 1, but an extension to 6 > 1 is straightforward. See Sec. E in appendix. EWSG has reduced variance but does not completely climinate the nonintrinsic noise created by stochastic gradient due to these approximations. A small bias was also created by these approxima- tions, but its effect is dominated by the variance effect (see Sec.4.4). In practice, if needed, one can combine EWSG with other variance reduction technique to further improve accuracy. We showcase how EWSG can be combined with SVRG in Sec.G of appendix.
4.4 NON-ASYMPTOTIC ERROR BOUND
The generator L of diffusion process (1) is L (r - (7r + VV + 77 Let X (0 TTTT 2d Given test function Φ(x)), its posterior average = f (()))<()))d)) and approximate it by time average of samples Øx = * EK o(xF). where x F. is the sample path given by EM integrator. A useful tool in weak convergence analysis for SG-MCMC is the Poisson
5

---

Under review as a conference paper at ICLR 2021
Algorithm EWSG
Input:
{the number of data terms n, gradient functions Vi(+), 1, ... ,, step size h, the number of data passes K, index chain length M, friction and noise coefficients y and o}
Initialize 0o, ro (arbitrarily, use informed guess)
for = 0, M+1
Kn do
< uniformly sampled from 1, ,,,,,,, compute and store n (0x)
I 5- i
for m = 1, .M do
j uniformly sampled from 1.... n, compute and store n (0s)
7 with probability in Equation 5
end for
Evaluate v(0)) (0x)
Update (0k+1, Pk+11 t TT) via one step of Buler-Maruyama integration using V(Ox)
end for
equation Lip c 3 (Mattingly et al., 2010; Vollmer et al., 2016; Chen et al., 2015). The solution & characterizes the difference between test function e and its posterior average Ø.
We now bound the error (in mean square distance between arbitrary test observables) for SG under- damped Langevin algorithms (the bound applies to both EWSG and other methods e.g.. SGHMC):
Theorem 4 Assume V 2014 < M1, & I1] < M2. VI = 1,2,... , 12, Vi 1.2,.... ,n and Vk 2 O. Assume the Poisson equation solution to and up to its 3rd-order derivatives are uniformly bounded [| Vlol < M3 1 = 0,1,2, 3. Then E constant C = C(M, M2) > 0, s.t.
h ETTiCVNCN FF)ll + +²²
(6)
K
where T= Kh is the corresponding time in the underlying continuous dynamics. Is is the index of the datum used to estimate gradient at k-th iteration, and cov(n (1, ) is the covariance of stochastic gradient at k-th iteration conditioned the current sigma algebra Fk in the filtration.
Remark: Mattingly et al. (2010) only discusses the batch gradient case, whereas our theory has
additional (non-uniform) stochastic gradient. Vollmer et al. (2016); Chen et al. (2015) studied the effect of stochastic gradient, but the SG considered there did not would destroy several martingales used in their proofs. In addition, our result incorporates the effeets of both local bias and local variance of SG approximation. Unlike in Mattingly et al. (2010) but like in Vollmer et al. (2016); Chen et al. (2015), our state space is not the compact torus but R.d. The time average Φk. to which our results apply, is commonly used estimator, particularly when simulating single Markov chain. Techniques in Cheng et al. (2018b); Dalalyan & Karagulyan (2017) might be useful to further bound difference between the law of X and the target distribution
dependent weights, which
Variance and bias of the SG approximation were reflected in the 2nd and 3rd term in the above bound, although the 3rd term also contains contribution from the numerical integration error. Note the 2nd term is generally larger than the 3rd due to its lower order in h, which means reducing local variance can improve sampling accuracy even if at the cost of introducing small bias. Since EWSG has a smaller local variance than uniform SG (Thm.3, as a special case of improved overall statistical accuracy), its global performance is also favorable.
EXPERIMENTS
In this section, the proposed EWSG algorithm will be compared with SGHMC, SGLD (Welling & Teh, 2011), as well as several recent popular SG-MCMC methods, including FlyMC (Maclaurin & Adams, 2015), PSGLD (Li et al., 2016), CP-SGHMC (Fu & Zhang, 2017) (closest method to IS for sampling by SG-MCMC) and SVRG-LD (Dubey al., 2016) (overdamped Langevin improved by VR). Sec. 5.1 is a detailed empirical study EWSG on simple models, with comparison and implication of two important hyper-parametedd M and æ, and verification of the non-asymptotic theory (Thm.4). Sec. 5.2 demonstrates the effectiveness of EWSG for Bayesian logistic regression on large-scale data set. Sec. 5.3 shows the performance of EWSG Bayesin Neural Network

---

Under review as a conference paper at ICLR 2021
(BNN) model. BNN only serves high- digensimensiona,, to compare Bayesian against non-
test case and we do not intend non-Bayesinn Bayesian neural nets. As FlyMC requires a tight lower bound of likelihood, known for only few cases, it will only be compared against in Sec. 5.2 where such a bound is obtainable. CP-SGHMC requires heavy tuning on the number of clusters which differs across data sets/algorithms, empirically found a good hyper parameter for MNIST (Fu & Zhang, 2017). SVRG-LD is only compared in Sec. 5.1, because SG-MCMC methods converge in one data pass in Sec. 5.2, rendering control- variate based VR technique inapplicable, and it was suggested that VR leads to poor results for deep models (e.g.. Sec.5.3) (Defazio & Bottou, 2019)
it will only be included in the BNN example, for which the authors
For fair comparison, all algorithms use constant step sizes and are allowed fixed computation budget, i.e., for I. data passes, all algorithms are only allowed to call gradient function n.. times. All experi- ments are conducted on machine with a 2.20GHz. Intel(R) Xeon(R) E5-2630 v4 CPU and an Nvidia GeForce GTX 1080 GPU. If not otherwise mentioned, a = /2y so only 7 needs specification, the length of the index chain is set M 1 for EWSG and the default values of two hyper-parameters required in PSGLD are set À = 10- and a = 0.99, as suggested in Li et al. (2016).
5.1 GAUSSIAN EXAMPLES
Consider sampling from a simple 2D Gaussian whose potential function is ( - Ei V
Σ 1 0 c; 12 We set n 20 and randomly sample c; from a two-dimensional standard normal 12). Due to the simplicity of (0), we can write the target density analytically and will use KL. divergence to measure the difference between the target distribution and generated samples.
(0,
For each algorithm, we generate 10000 independent realizations for empirical estimation. All algorithms are run for 30 data passes with minibatch size of 1. Step size is tuned from 5 X {10-1, 10-2, 10-3 10=1) and 5 x 10-3 chosen for SGLD and pSGLD, 5 x 10-2 for SGHMC for SVRG-LD. SGHMC and EWSG use 7 = 10. Results are shown in
and EWSG and 5 x 10-1 Fig. la and EWSG outperforms SGHMC, SGLD and pSGLD in terms of accuracy. Note SVRG-LD has the best accuracy* but the slowest convergence, and that is why EWSG is useful alternative to VR: its light-weight suits situations with limited computational resources better.
When simulating gradient-basse Markov chain, large step size generally reduces autocorrelation time", yet leads to large discretization error. Figure 1b shows at the same autocorrelation time, EWSG achieves smaller error than SGHMC, which demonstrates the effectiveness of EWSG.
Figure Ic shows the performance of several possible choices of the hyper-parameter x, including the proposed option æ Vhyrw/o, x = 0, æ = and x = (-1+ + ///////// (corresponds to setting Fx+1 0). The result shows that the proposed option performs significantly better than other alternatives and we suggest to use it by default.
Another important hyper-parameter in EWSG is M. As the length of index chain M increases, the distribution approaches the distribution given by Equation (4), which by Theorem 4 introduces some bias but also reduces variance. The tradeoff clearly manifested in Figure 1d and Ic. M. regarded as hyper-parameter controls this tradeoff and generally requires tuning to determine the best value.
The optimal value of M depends on the number of minibatches T. Large & implies each minibatch is relatively small, and suggests large variance in stochastic gradient estimation of each minibatch and hence strong need to reduce variance, see the illustration in Figure li. For example, if we increase the number of data in Gaussian example to n 50 or 100 and keep mini batch size b = 1, M that gives the best final accuracy increases to 19 in Figure Ig and 1h. In our experiments, we empirically observe the choice MM = 1 usually gives reasonably good performance and we fix it as the default choice. See Sec. H.3 for additional experiments on tuning M and the batch size.
In Figure 1a. we see EWSG converges slightly slower than uniform SG. This is because in each iter- ation, EWSG consumes M + times the data used by uniform SG, and hence in fair comparison with fixed computation budget, EWSG runs M times iterations fewer than uniform SG. However, EWSG can still achieve comparable speed of convergence with appropriately chosen hyper parame-
4 *For Gaussians, mean and variance completely determine the distrihution, so appropriately reduced variance leads to great accuracy for the entire distribution.
Autocorrelation time defined as 1 Σ Pe. where P. is the autocorrelation time lag 8.
7

---

Under review as a conference paper at ICLR 2021
10
0.4
SOULD EWSG
10
INttaa - 1
KL Divergence
KL Divergence
BNSGO
$2.LD
dasuags Abookza Sier Suguge
16
E960
BNSGG stath
10"
0.2
10"
0.1
10
20
30
0.0
0
10
20
30
Number of Data Pass
60
Number of Data Pass
Autocorrelation Time
(a) Sample quality in KL
(c) Performance for various æ
(b) Error covariance vs ACT
to
Standard Deviation
1d"
EWSG
EW5GR/M-1)
Divergence
10"
EWSG/M-9
EWSG/MF4)
EWSG(M-11
EWSG/MM4)
EWSC(MM11))
EWSDD/M-19)
Blas
10"
EMSG/M-13
EWSG/M-43
EMSG/M-B)
10
EWSG/M-19)
10"
10
20
30
10
0
10
20
30
20 Number Dala Pass
Number of Data Pass
Number of Dala Pass
(f) Performance for various M, with default n 20
How bias depends on .M
(e)
How std depends on M
EWSGIM=1)
EWSG(M=1)
KL Divergence
EWSG(M=4)
KL Divergends
EWSG(ME4)
large data set
EW8G/M-8)
EWSG(M-9)
10
EWSG/M-19)
EWSG/M-199
Varianco
Blas
10¹
10"
small data set
0
10
20
30
0
10
20
30
Number of Data Pass
Number of Data Pass
(g) Performance for various M; (h) Performance for various M;
Bias-variance tradcoff
data size increased
50
data size increased to 100
EWSG(M-1)
EWSG(M-1) Cyh + C2
EWSG/M-1)
10"
Oth?)
10
10"
10
E(
10"
10
0.0
2.5
5.0 T
7.5
10.0
10
10"
10"
h
(i) MSE against time T (1") term (k) MSE against step size h with (I) MSE against step size l with fixed finite T (2"d term Eq. (6) so (3 term Eq. (6))
in Eq. (6))
Figure 1: Sampling from Gaussian target
b ters; e.g., if uniform SG uses minibatch size b, then one can use smaller minibatch size (e.g. M4T for EWSG to ensure both algorithms consume the same number of gradient calls per iteration and hence run the same number of iterations. See Sec. H.3 for more empirical studies on this.
As approximations are used in Alg. it is natural to ask if Thm. still applies. We empirically investigate this question (using M and variance as the test function Φ). Eq.(6) in Thm.4 4 has nonasympiotic error bound consisting of three parts, namely an O(+) term corresponding to the convergence at the continuous limit, an (h/TT) term coming from the SG variance, and an Ohh2) term due to bias and numerical error. 1ig. plots the mean squared emror (MSE) against time T = Kh to confirm the 1st (and the 2nd) term. Fig. Ik plots the MSE against h in the small h regime (so that the 2nd term dominates the 3rd) to confirm that the 2nd term scales like O(h) with a fixed T. For the 3rd term in Eq. (6), we run sufficiently many iterations to ensure all chains well-mixer mixed, and Fig. confirms the final MSE to scale like ((h2) even for large h (as the 2nd
term vanishes due to T + oo). In this sense, despite the approximations introduced by the practical
8

---

Under review as a conference paper at ICLR 2021
Method
SGLD 75.282 +: 0.079
pSGLD 75.079 + 0.094
SGHMC
EWSG
FlyMC
Accuracy(%)
75.272 + 0.069
75.293 + 0.045
75. + 0.079
Log Likelihood
-0.525 + 0.000
-0.527 + 0.000
-0.525 + 0.000
-0.523 + 0.000
-0.523 + 0.001
Table 1: Accuracy and log likelihood of BLR on test data after one data pass (mean + std).
150
20
(80
mg
-25
SOULD
(AaLD
scu.D
Tel Error
CP-SSULD
FASG
CP-SCULD
FWSG
0.0
30.0
SaaD
100
SGJID
PSGLD
EW60
-67
BOULD
E960
00
Number
22 E4
30
30
-77
Number
03
Number Pana
Number of Data
(a) Test Accuracy
(b) Test Log Likelihood
MLP architecture
(b) CNN architecture
Figure 2: BLR learning curve
Figure 3: BNN learning curve. Shade: 1 std.
implementation, the performance of Algorithm 1 is still approximated by Theorem 4, even when M = 1, and Theorem 4 provides reasonable guidelines for practical use of the EWSG algorithm.
5.2 BAYESIAN LOGISTIC REGRESSION (BLR)
Consider binary classification based on probablistic model p(u = 1 2x. 0) = 1/(1 + exp(-0" ax)).. We set Gaussian prior (O0, 107a) for and experiment with the Covertype data set (581,012 data points, 54 features). We use 80% of data for training and the rest for testing.
ULD based algorithms use 7 50. After tuning, we set step sizes {1, 3, 0.02, 5, 5) 10-3 for SGHMC, EWSG, SGLD, PSGLD and FlyMC. All algorithms are run for one data pass, with minibatch size of 50. 200 independent samples are drawn from each algorithm to estimate statistics.
Results are in Fig. 2a and 2b and Table 1. EWSG outperforms others, except for log likelihood being comparable FlyMC, which is an exact MCMC method.
5.3 BAYESIAN NEURAL NETWORK (BNN)
Bayesian inference is compelling for deep learning (Wilson, 2020). Two popular architecture of neural nets are experimented multilayer perceptron (MLP) and convolutional neural nets (CNN). In MLP, hidden layer with 100 neurons followed by a softmax layer is used. In CNN, we use standard network configuration with 2 convolutional layers followed by 2 fully connected layers (Jarrett al., 2009). Both convolutional layers use 5 5 convolution kernel with 32 and 64 channels, 2 x 2 max pooling layers follow immediately after convolutional layer. The last two fully-connected layers each has 200 neurons. We set the standard normal as prior for all weights and bias.
We test algorithms on the MNIST data set, consisting of 60000 training data and 10000 test data, each datum is 28 28 gray-scale image with one of the ten possible labels (digits 0 ~ 9). For ULD based algorithms....... we set friction coefficient y = 1 in MLP and y = 1.0 in CNN. In MLP. the step sizes are set h { [4, 2, 2} 10 for EWSG. SGHMC and CP-SGHMC, and h {0.001, 1] x 10 for SGLD and pSGLD, via grid search. For CP-SGHMC we use K-means with 10 clusters to preprocess the data set. CNN, the step sizes are set h (4. 2, 2) 10-3 for EWSG, SGHMC and CP-SGHMC, and f {0.02, 8} x 10-6 for SGLD and pSGLD, via grid search. All algorithms use minibatch size of 100 and are run for 200 data passes. For each algorithm, we generate 100 independent samples to estimate posterior distributions and make prediction accordingly.
The learning curve of training accuracy is shown in Figure 3a and 3b. We find EWSG consis- tently improve over its uniform counterpart (i.e. SGHMC) and CP-SGHMC (an approximate IS SG-MCMC). Moreover, EWSG also outperforms two standard benchmarks SGLD and PSGLD. The improvement over baseline MNIST data is comparable to of the early works (Chen et al., 2014; Li et al., 2016). More results on this experiment can be found in Sec. H.2.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sungjin Ahn, Anoop Korattikara, and Max Welling. Bayesian posterior sampling via stochastic gradient fisher scoring. In 29th International Conference on Machine Learning, ICML 2012, pp. 1591-1598, 2012.
Francis Bach.
Stochastic gradient methods for machine learning.
Technical re-
port, 2013. URL http://Leaz wtt.:iaapp..eeppppl......... gargantua/s htt//ssides/bbbbaaea httpraachhgggggaaeeeeeeeoooo pdf.
Jack Baker, Paul Fearnhead, Emily B Fox, and Christopher Nemeth. Control variates for stochastic gradient meme. Statistics and Computing, 29(3):599-615, 2019.
Rémi Bardenet, Arnaud Doucet, and Chris Holmes. On markov chain monte carlo methods for tall data. The Journal of Machine Learning Research, 18(1):1515-155) 2017.
Vivek S Borkar and Sanjoy K. Mitter A strong approximation theorem for stochastic recursive algorithms. Journal of optimization theory and applications, 1006))499-513, 1999.
Nawaf Bou-Rabbee and Houman Owhadi. Long-run accuracy of variational integrators in the stochas- tic context. SIAM Journal Numerical Analysis, 48(1):278--2 2010.
Nawaf Bou-Rabee and Jesús María Sanz-Serna. Geometric integrators and the Hamiltonian Monte Carlo method. Acta Numerica, 27:1 13-206, 2018.
Nawaf Bou-Rabee, Andreas Eberle, and Raphael Zimmer. Coupling and convergence for Hamilto- nian Monte Carlo. arXiv preprint arXiv: 1805.0045, 2018.
Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng. Handbook of markov chain monte carlo. CRC press, 2011.
Niladri S Chatterji, Nicolas Flammarion, Yi-An Ma, Peter L Bartlett, and Michael I Jordan. On the theory of variance reduction for stochastic gradient monte carlo. ICMI., 2018.
Changyou Chen, Nan Ding, and Lawrence Carin. On the convergence stochastic gradient meme algorithms with high-order integrators. In Advances in Neural Information Processing Systems, pp. 2278-2286, 2015.
Tianqi Chen, Emily Fox, and Carlos Guestrin. Stochastic Gradient Hamiltonian Monte Carlo. International Conference Machine Learning, pp. (683-1691, 2014.
Xiang Cheng, Niladri S Chatterji, Yasin Abbasi-Yadkori. Peter L Bartlett. and Michael Jor- dan. Sharp convergence rates for langevin dynamics in the nonconvex setting. arXiv preprint 1805 2018a.
Xiang Cheng, Niladri Chatterji, Peter I. Bartlett, and Michael Jordan. Underdamped langevin mcme: A non-asymptotic analysis. Proceedings of the 3 31 Conference On Learning Theory, PMLR, 2018b.
Dominik Csiba and Peter Richtárik. Importance sampling for minibatches. The Journal of Machine Learning Research, (1119992-992, 2018.
Arnkk S Dalalyan and Avetik G Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient. arXiv preprint :Xiv:1710000095 2017.
Aaron Defazio and Léon Bottou. the ineffectiveness of variance reduced optimization for deep learning. In Advances in Neural Information Processing Systems, pp. 1755-1765, 2019,
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances neural information processing systems, pp. 1646-1654, 2014.
Kumar Avinava Dubey, Sashank Reddi, Sinead A Williamson, Barnabas Poczos, Alexander J Smola, and Eric Xing. Variance reduction in stochastic gradient langevin dynamics. In Advances in neural information processing systems, pp. 1 1154-1162, 2016.
10

---

Under review as a conference paper at ICLR 2021
Tianfan Fu and Zhihua Zhang. Cpsg-meme Clustering- based preprocessing method for stochastic gradient meme. In Artificial Intelligence and Statistics, pp. 841-850 2017.
Kevin Jarrett, Koray Kavukcuoglu, Marc Aurelio Ranzato, and Yann LeCun. What is the best multi-stage architecture for object recognition? In 2009 IEEE 12th international conference on computer vision, pp. 2146-214200111 2153. IEEE, 2009.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in neural information processing systems, pp. 315-323, 2013.
Rep Kubo. The fluctuation-dissipttion theorem. Reports on progress in physics, 29(1):255, 1966.
Chunyuan Li, Changyou Chen, David Carlson, and Lawrence Carin. Preconditioned stochastic gradient langevin dynamics for deep neural networks. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
Qianxiao Li, Cheng Tai, and E Weinan. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference on Machine Learning, pp. 2101-2110, 2017.
Moshe Lichman et al. UCI machine learning repository, 2013.
Yi-An Ma, Tianqi Chen, and Emily Fox. A complete recipe for stochastic gradient meme. In Advances in Neural Information Processing Systems, pp. 2917-2925, 2015.
Dougal Maclaurin and Ryan Prescott Adams. Firefty monte carlo: Exact meme with subsets of data. In Twenty- Fourth International Joint Conference on Artificial Intelligence, 2015.
Stephan Mandt, Matthew Hoffman, and David Blei. Stochastic gradient descent as approximate bayesian inference. The Journal of Machine Learning Research, 18(1):4873-490) 2017.
Jonathan C Mattingly, Andrew M Stuart, and Michael V Tretyakov. Convergence of numerical time- averaging and stationary measures via poisson equations. SIAM Journal on Numerical Analysis, 48(2):552-577, 2010.
Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. In Advances in Neural Information Processing Systems, pp. 1017-1025, 2014.
Sam Patterson and Yee Whye Teh. Stochastic gradient Riemannian Langevin dynamics on the probability simplex. Advances in Neural Information Processing Systems, pp. 3102-3110, 2013.
Grigorios Pavliotis. Stochastic processes and applications: diffusion processes, the Pekker-Plance and Langevin equations, volume 60. Springer, 2014.
Gareth O Roberts, Richard L Tweedie, et Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, 2(4):341-363, 1996.
Mark Schmidt, Reza Babanezhad, Mohamed Ahmed, Aaron Defazio, Ann Clifton, and Anoop Sarkar. Non-uniform stochastic average gradient method for training conditional random fields. In artificial intelligence and statistics, pp. 819-828, 2015.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162(1-2):33-112 2017.
Molei Tao and Tomoki Ohsawa. Variational optimization on lic groups, with examples of leading (generalized) eigenvalue problems. AISTATS, 2020.
Yee Whye Teh, Alexandre H Thiery, and Sebastian J Vollmr. Consistency and fluctuations for stochastic gradient langevin dynamics. The Journal of Machine Learning Research, 17(1):193- 225, 2016.
Sebastian J Vollmer, Konstantinos C Zygalakis, and Yee Whye Teh. Exploration of the (non-) asymptotic bias and variance stochastic gradient langevin dynamics. The Journal of Machine Learning Research, 17(1):50045554 2016.

---

Under review as a conference paper at ICLR 2021
Max Welling and Yee Whye Teh. Bayesian learning via stochastic gradient langevin dynamics. International Conference on Machine Learning, pp. 681-688, 2011.
Andrew Gordon Wilson. The case for bayesian deep learning. arXiv preprint arXi::2001.10999 2020.
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss minimization. In International Conference on Machine Learning, pp. 1-9, 2015.
Rong Zhu. Gradient-based sampling: An adaptive importance sampling for least-squares. In Ad- vances Neural Information Processing Systems, pp. 406-414, 2016.
12


Reviews:
[{"review_id": "q0sqwzv3bdo", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a non-uniform sampling method for stochastic gradient minibatches for SG-MCMC. By sampling the indices of the stochastic gradients according to a parameter-specific (exponentially weighted) non-uniform distribution, the paper shows that it exactly matches the transition kernel of full batch gradient MCMC (for underdamped langevin dynamics) in Theorem 2. Although this exponentially weight distribution is intractable, the paper presents an approximate sampler in Algorithm 1 (that both uses a 1-step Metropolis Hastings approximation and a deterministic approximation for the $x$ term $r_{k+1} = r_k$). Finally the paper compares Algorithm 1 with other SGMCMC methods in a small synthetic Gaussian example, bayesian logistic regression on Covertype data, and a Bayesian neural network on MNIST.  \n\nThe idea to non-uniformly sample the random stochastic gradient index to match SGULD is clever. The paper would benefit from additional editing: the notation and presentation of ideas is unclear + difficult to parse in some sections.   \n\nThis paper should be rejected. Although the particular non-uniform random sampling scheme is novel, it is not clear how the two approximations (MH and $x$) in Algorithm 1 affect the error of the sampler in practice. Although the experiments show some benefit of Algorithm 1 over vanilla SGMCMC, they are not strongly convincing or exhaustive and do not analyze the error introduced in Algorithm 1. I believe with significant editing and additional experiments, this paper would be more competitive, but as it stands, it should be rejected. \n  \nAlthough Theorems 1-4 may be interesting for the non-uniform sampling scheme for stochastic gradient indices (Eq 4), in practice, Algorithm 1 is different due to the two approximations. In particular, I am concerned about the approximation for $x$ (especially since the definition of $x$ seems circular). Although it may appear that the approximation $r_{k+1} = r_k$ works well for your experiments, this may not be the case in general. Clarity on when this approximation is justified and when it is not would help build confidence in this approximation. I would have liked to have seen how the performance of Algorithm 1 compared to the theory (Theorem 3 or 4) for the theoretical sampler using (Eq 4) or the full batch \"ground truth\" MCMC (Eq 3).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "SJ4_LiZHsXh", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##  Summary of the paper\nThe authors focused on the fact that there are two types of stochasticity in SG-MCMCs, one is the intrinsic randomness of MCMC and the other is the randomness introduced by gradient subsampling. Then the authors proposed coupling these randomnesses so that the final variance is reduced. Experimental results support that the proposed coupling seems promising.\n\n## Strong and weak points of the paper\n### Strong points\n- Provided a new connection between importance sampling and stochastic gradient.\n- Provided an asymptotic analysis for the variance reduction in Theorem 4, which seems novel variance analysis.\n\n### Weak points\n- I am not sure the approximations introduced in Sec 4.3 are valid theoretically and numerically. I commend these points in the below.\n\n## Rating\n- Clarity: Well written, easy to read, although I did not check the proof of Theorem 4.\n- Correctness: I did not check all the proof in detail.\n- Novelty: The idea seems very interesting and important in the community.\n\n## Comments and Questions\n- Q) the authors introduced several approximations, e.g., setting M=1,  setting x as the equibirum points, to implement the index sampling efficiently. How those approximations affect the final variance theoretically ? Especially, although the authors provided the variance analysis in Theorem 4, I think it is unclear how these approximations affect the upper bound of the variance in Eq.(6) explcitely.\n\n- Q) could you explain why the approximation of $r_{k+1}=r_k$ in Sec 4.3 is valid and when this approximation is not valid ? At first sight I thought that this equilibrium condition is definitely wrong at an early stage of the underdamped Langevin dynamics.\n\n- Q) In Fig 1.d to 1.f, the authors studied the impact of M. It seems that the larger M are, the worse results are obtained. Is this correct ? I thought that increasing M means increasing the number of Markov chains for the index sampling and it should improve the performance.", "extra_scores": {}, "extra_text": {}}, {"review_id": "OsiRjzDvdmP", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\n\nThe paper proposes an alternative to the uniform sampling scheme used for constructing mini-batches in stochastic gradient sampling algorithms. The proposed scheme, called Exponentially Weighted Stochastic Gradient (EWSG), is devised such its transition kernel matches that of the batch gradient descent. The proposed scheme is shown to achieve better results than the uniform sampling one.\n\n##########################################################################\nReason for score:\n\nI'm oscillating between accepting the paper and rejecting it. Overall there are good merits to the paper, however there are some aspects on which I would like to have some further clarifications from the authors.\n\n##########################################################################\nPros:\n\n1. The paper is overall well written with a proper formulation and justification of the problem it addresses. The proposed solution is analysed both theoretically and empirically and the results show the advantage of the proposed method with respect to the uniform sampling scheme.\n\n2. The subject the paper addresses is of importance to the ML community and I believe the advances brought by the paper are sufficient to warrant its acceptance. \n\n##########################################################################\nCons:\n\n1. I have some concerns regarding the practical implementation of the proposed scheme in general. Overall, I appreciated the discussion about the choice of the hyper-parameters. However, my concerns stems from the fact that you have two intertwining Markov chains, one for the quantity we wish to perform inference on and one for the indices. From figure 1(a) we can see that there is a slower convergence of the EWSG method with respect to the SGLD one, though this slower converge is compensated by the better accuracy. My question is whether in all practical situations I will eventually reach a better accuracy than SGLD within an acceptable computational budget?\nOn the same note, in the paper you deal only with the case of one item per mini-batch. You address in the appendix the extension to mini-batch sizes greater than one. However, when we consider mini-batch sizes different than one, for some mini-batch sizes the number of possible combinations is greater than the number of elements in the data set. The sampling over the indexes will lead to sampling the \"best\" mini-batches, however would the advantage of the proposed method still be retained within a fixed computational budget in such a scenario given that there are more possibilities that need exploring?  \n\n2. Another issue stems from the fact that the method requires access to the full dataset, or at least to be able to retrieve items from it. There are situations in which the full dataset is distributed across different computational nodes, thus on one node I would have only a limited subset of data. Assuming we can recombine the results from each node to get a global estimate, would it still be beneficial to run your proposed method on each node such that to improve accuracy or in such a case running SGLD would suffice? This question is related to the assumption that you make at the beginning of section 4.1 that n >> d and I'm just wondering if there are any advantages of using your proposed method when the number of data items is still greater than the dimension, but not significantly.\n\n3. I have a minor issue with the plots in figure 1: the values on the ordinate axis are sometimes very difficult to see and read, you could increase the font given that there still is space available before reaching the margins of the page.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper describes a non-uniformly weighted version of SGMCMC, combining aspects of SG methods and importance sampling. The idea is interesting and novel, but unfortunately the authors have not made a compelling case for the resulting algorithm being a practical addition to the literature. The experimental analysis is not particularly compelling, and there are key concerns raised about practical implementation, and about the validity of the approximations raised. I hope that the authors will continue along this interesting line of work and add additional explorations of the approximations and improved experimental analysis.
Decision: Reject