Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning
Authors: Ruqi Zhang
Chunyuan Li
Jianyi Zhang
Changyou Chen
Andrew Gordon Wilson
Venue:  (2020)

Abstract: The posteriors over neural network weights are high dimensional and multimodal. Each mode typically characterizes a meaningfully different representation of the data. We develop Cyclical Stochastic Gradient MCMC (SG-MCMC) to automatically explore such distributions. In particular, we propose a cyclical stepsize schedule, where larger steps discover new modes, and smaller steps characterize each mode. We prove non-asymptotic convergence theory of our proposed algorithm. Moreover, we provide extensive experimental results, including ImageNet, to demonstrate the effectiveness of cyclical SG-MCMC in learning complex multimodal distributions, especially for fully Bayesian inference with modern deep neural networks.

Published as a conference paper at ICLR 2020
CYCLICAL STOCHASTIC GRADIENT MCMC FOR BAYESIAN DEEP LEARNING
Ruqi Zhang
Chunyuan Li Microsoft Research, Redmond chuny] @mi cmmocrosot.comm
Jianyi Zhang Duke University jz.31 8 Bdduke.eee.. edd
Cornell University r2297@cornel1.cm edu
Changyou Chen University at Buffalo, SUNY changyoubbuffalo.cm edu
Andrew Gordon Wilson
New York University
andrexgwecims nyy..iiiiiinn.....mmmmmmmm edu
ABSTRACT
The posteriors over neural network weights are high dimensional and multimodal. Each mode rypically characterizes meaningfully different representation of the data. We develop Cyclical Stochastic Gradient MCMC (SG-MCMC) to auto- matically explore such distributions. In particular, we propose cyclical step- size schedule, where larger steps discover new modes, and smaller steps charac- terize each mode. We prove non-asymptotic convergence of our proposed algo- rithm. Moreover, provide extensive experimental results, including ImageNet, to demonstrate the effectiveness cyclical SG-MCMC learning complex mul- timodal distributions, especially for fully Bayesian inference with modern deep neural networks.
INTRODUCTION
Deep neural networks are often trained with stochastic optimization methods such stochastic gra- dient decent (SGD) and its variants. Bayesian methods provide principled alternative, which ac- count for model uncertainty in weight space (MacKay, 1992; Neal, 1996), and achieve an automatic balance between model complexity and data fitting. Indeed, Bayesian methods have been shown to improve the generalization performance of DNNs (Hernández-Loobes et al., 2015; Li et al., 2016a; Maddox et al., 2019), while providing principled representation of uncertainty on predictions which crucial for decision making.
& Adams, 2015; Blundell
Approximate inference for Bayesian deep learning has typically focused deterministic ap- proaches, such as variational methods (Hernández--Lobtto Adams, 2015; Blundell et al., 2015). By contrast, MCMC methods
essentially unused for inference with modern deep neural networks, despite previously providing the gold standard of performance with smaller neural net- works (Neal, 1996). Stochastic gradient Markov Chain Monte Carlo (SG-MCMC) methods (Welling & Teh, 2011; Chen et al., 2014; Ding et al., 201 4; Li et al., 201 provide a promising direction for sampling based approach to inference in Bayesian deep learning. Indeed, it has been shown that stochastic methods, which use mini-batches of data, are crucial for finding weight parameters that provide good generalization in modern deep neural networks (Keskar al., 2016).
However, SG-MCMC algorithms for inference with modern neural networks face several challenges: (i) In theory, SG-MCMC asymptotically converges to target distributions via a decreasing stepsize scheme, but suffers from bounded estimation error in limited time (Tch et al., 2016; Chen et al., 2015). (ii) In practice, empirical successes have been reported by training DNNs in relatively short time (Li et al., 2016b; Chen et al., 2014; Gan et al., 2016; Neelakantan et al., 2016; Saatchi & Wilson, 2017). For example, Saatchi & Wilson (2017) apply SG-MCMC to generative adversarial networks (GANs) to solve the mode collapse problem and capture diverse generation styles. However, the loss surface for DNNs is highly multimodal (Auer et al., 1996; Choromanska et al., 2015). In order for MCMC to be effective for posterior inference in modern neural networks, crucial question remains: how do we make SG-MCMC efficiently explore a highly multimodal parameter space given a practical computational budget?

---

Published as a conference paper at ICLR 2020
Several attempts have been made to improve the sampling efficiency of SG-MCMC. Stochastic Gra- dient Hamiltonian Monte Carlo (SGHMC) (Chen et al., 2014) introduces momentum to Langevin dynamics. Preconditioned stochastic gradient Langevin dynamics (pSGLD) (Li et al., 2016a) adap- tively adjusts the sampler's step size according to the local geometry of parameter space. Though simple and promising, these methods are still inefficient at exploring multimodal distributions in practice. It is our contention that this limitation arises from difficulties escaping local modes when using the small stepsizes that SG-MCMC methods typically require. Note that the stepsize in SG- MCMC controls the sampler's ss behavior in two ways: the magnitude to deterministically drift to- wards high density regions wrz. the current stochastic gradient, and the level of injecting noise to randomly explore the parameter space. Therefore, small stepsize reduces both abilities, resulting large numbers iterations for the sampler to move across the modes.
In this paper, we propose to replace the traditional decreasing stepsize schedule in SG-MCMC with a cyclical variant. To note the distinction from traditional SG-MCMC, we refer to this method as Cyclical SG-MCMC (cSG-MCMC). The comparison is illustrated in Fig- ure 1. The blue curve is the traditional decay, while the red curve shows the proposed cyclical schedule. Cyclical SG-MCMC operates in two stages: (i) Exploration: when the stepsize is large (dashed red curves), we consider this stage as effective burn-in mechanism, encouraging the sampler to take large moves and leave the local mode using the stochastic gradient. (it) Sampling: when the stepsize is small (solid red curves). the sampler explores one local mode. We collect samples for local distribution estimation during this stage. Further, we propose two practical techniques improve estimation efficiency: (1) a system temperature for exploration and exploitation; (2) A weighted combination scheme for samples collected in different cycles to reflect their relative importance.
Exploration Slage
Sampling Stage
Decay Stepsize
0.10
0.00
0.06
0.34
0.32
0.00
75
100
125
150
175
200
Epochs
Figure 1: Illustration of the proposed cyclical stepsize schedule (red) and the traditional decreasing stepsize schedule (blue) for SG-MCMC algorithms.
This procedure can be viewed as SG-MCMC with warm restarts: the exploration stage provides the warm restarts for its following sampling stage. cSG-MCMC combines the advantages from (1) the traditional SG-MCMC to characterize the fine-scale local density of distribution and (2) the
cyclical schedule optimization to efficiently explore multimodal posterior distributions of the pa- rameter space. In limited time, cSG-MCMC is practical tool to provide significantly better mixing than the traditional SG-MCMC for complex distributions. cSG-MCMC can also be considered as an efficient approximation to parallel MCMC; cSG-MCMC can achieve similar performance to par- allel MCMC with only a fraction of cost (reciprocal to the number of chains) that parallel MCMC requires.
To support our proposal, we also prove the non-asymptotic convergence for the cyclical schedule. We note that this is the first convergence analysis of a cyclical stepsize algorithm (including work in optimization). Morcover, we provide extensive experimental results to demonstrate the advantages of cSG-MCMC in sampling from multimodal distributions, including Bayesian neural networks and uncertainty estimation on several large and challenging datasets such as ImageNet.
In short, cSG-MCMC provides simple and automatic approach to inference in modern Bayesian deep learning, with promising results, and theoretical support. This work is a step towards enabling MCMC approaches in Bayesian deep learning. We release code https: / thub. com/ ruqi zhang/ csgmemc.
PRELIMINARIES: SG-MCMC WITH A DECREASING STEPSIZE SCHEDULE
SG-MCMC is a family of scalable sampling methods that enables inference with mini-batches of data. For a dataset D ).N and a d-parameterized model, we have the likelihood p()))) and prior p(0). The posterior distribution is p(0 x exp(-U(()) where (8) is the potential energy given by (0)) = log log p(0)
2

---

Published as a conference paper at ICLR 2020
When D is too large. it is expensive evaluate ( for all the data points at each iteration. In- stead, SG-MCMC methods use a minibatch to approximate U+): (()) = N' Σ log p(a:)0) log (()), where N' < N is the size of minibatch. We recommend Ma et al. (2015) for general review of SG-MCMC algorithms. We describe two SG-MCMC algorithms considered in this paper.
SGLD & SGHMC Welling & Teh (2011) proposed Stochastic Gradient Langevin Dynamics (SGLD), which uses stochastic gradients with Gaussian noise. Posterior samples are updated at the k-th step as: 02- = 0-1 Vū + /20nes, where og is the stepsize and ég has a standard Gaussian distribution.
To improve mixing over SGLD, Stochastic Gradient Hamiltonian Monte Carlo (SGHMC) (Chen et al., 2014) introduces an auxiliary momentum variable v. SGHMC is built upon HMC, with an additional friction term to counteract the noise introduced by mini-batch. The update rule for posterior samples is: 0g 8x-1 + Uk-1, and 2/2 tk-1 ag VÙ (0x) M where 1 - is the momentum term and fy is the estimate of the noise.
- 9)
To guarantec asymptotic consistency with the true distribution, SG-MCMC requires that the step sizes satisfy the following assumption:
Assumption 1. The step sizes } are decreasing, i..,, 0 < 0-+11 < ag, with 1) Ei= ag = oo; and 2) Ex= of < oc.
Without decreasing step-size, the estimation error from numerical approximations asymptoti- cally biased. One typical decaying step-size schedule is ag = a(b + k)-?, with y E (0.5, 1] and (a, b) some positive constants (Welling & Teh, 2011).
CYCLICAL SG-MCMC
We now introduce our cyclical SG-MCMC (cSG-MCMC) algorithm. cSG-MCMC consists of two stages: exploration and sampling. In the following, we first introduce the eyclical step-size schedule, and then describe the exploration stage in Section 3.1 and the sampling stage in Section 3.2. We propose an approach to combining samples for testing in Section F.
Assumption guarantees the consistency of our estimation with the true distribution in the asymp- totic time. The approximation error in limited time is characterized as the risk of an estimator R = B² + V. where B is the bias and V is the variance. In the case of infinite computation time, the traditional SG-MCMC setting can reduce the bias and variance to zero. However, the time budget is often limited in practice, and there is always trade-off between bias and variance. We therefore decrease the overall approximation error R by reducing the variance through obtaining more effec- tive samples. The effective sample size can be increased if fewer correlated samples from different distribution modes are collected.
For deep neural networks, the parameter space is highly multimodal. In practice, SG-MCMC with the traditional decreasing stepsize schedule becomes trapped in a local mode, though injecting noise may help the sampler escape in the asymptotic regime (Zhang al., 2017). Inspired to improve the exploration of the multimodal posteriors for deep neural networks, with a simple and automatic approach, we propose the cyclical cosine stepsize schedule for SG-MCMC. The stepsize at iteration is defined as:
π mod(k: (k: - (,, -1.[//M)
On 2 cos
+
[K/M]
where ag is the initial stepsize, M is the number of cycles and K is the number of total iterations (Loshchilov & Hutter, 2016; Huang al., 2017).
The stepsize og varies periodically with k. In each period, 0g starts at ogg and gradually decreases to O. Within one period, SG-MCMC starts with large stepsize, resulting in aggressive exploration in the parameter space; as the stepsize is decreasing. SG-MCMC explores local regions. In the next period, the Markov chain restarts with a large stepsize, encouraging the sampler to escape from the current mode and explore a new area of the posterior.
Related work in optimization. In optimization. the cyclical cosine annealing stepsize schedule has been demonstrated to be able find diverse solutions in multimodal objectives, though not
3

---

Published as a conference paper at ICLR 2020
specifically different modes, using stochastic gradient methods (Loshchilov & Hutter, 2016; Huang et al.. 2017: Garipov et al., 2018; Fu et al., 2019). Alternatively, we adopt the technique to SG- MCMC effective scheme for sampling from multimodal distributions.
3.1 EXPLORATION
The first stage of cyclical SG-MCMC, exploration, discovers parameters near local modes of an objective function. Unfortunately, it is undesirable to directly apply the cyclical schedule in op- timization to SG-MCMC for collecting samples every step. SG-MCMC often requires small stepsize in order to control the error induced by the noise from using minibatch approximation. If the stepsize is too large, the stationary distribution of SG-MCMC might be far away from the true posterior distribution. To correct this error, it is possible to do stochastic Metropolis- (MH) (Korattikara et al., 2014; Bardenet et al., 2014; Chen et al., 2016b). However, stochastic MH correction is still computationally too expensive. Further, it is easy get rejected with aggressive large stepsize, and every rejection is a waste gradient computations.
To alleviate this problem, we propose to introduce system temperature T to control the sampler's behaviour: p(0 D) x exp(-U(0)/TT), Note that the setting T corresponds to sampling from the untempered posterior. When T 0, the posterior distribution becomes a point mass. Sam- (0) / is equivalent to minimizing U(0); in this context, SG-MCMC
pling from lim methods become stochastic gradient optimization methods.
One may increase the temperature T' from O to I when the step-size is decreasing. We simply consider T 0 and perform optimization the burn-in stage, when the completed proportion of cycle r(k) = mod (6-1,[K/M) is smaller than a given threshold: r(k) < B. Note that 3 E (0,
[K/M]
balances the proportion of the exploration and sampling stages in cSG-MCMC.
3.2 SAMPLING
Algorithm 1 Cyclical SG-MCMC.
The sampling stage corresponds to T = 1 of the exploration stage. When r(k) > B or step-sizes are sufficiently small, we ini- tiate SG-MCMC updates and collect sam- ples until this cycle ends.
Input: The initial stepsize on, number of cycles M, number of training iterations K and the proportion of exploration stage B
for k 1:K do 4 Or according to Eq equation 1.
if mod (k-1,[K/M) 3 then
SG-MCMC with Warm Restarts. One may consider the exploration stage as au- tomatically providing warm restarts for the sampling stage. Exploration alleviates the inefficient mixing and inability to traverse the multimodal distributions of the tradi- tional SG-MCMC methods. SG-MCMC with warm restarts explores different parts of the posterior distribution and captures multiple modes in single training procedure.
K//
% Exploration stage
0- - VVx
else
% Sampling stage
Collect samples using SG-MCMC methods
Output: Samples {6x}
In summary, the proposed cyclical SG-MCMC repeats the two stages, with three key advantages: (i) It restarts with large stepsize at the beginning of cycle which provides enough perturbation and encourages the model to escape from the current mode. (ii) The stepsize decreases more quickly inside one cycle than traditional schedule, making the sampler better characterize the density of the local regions. (ii)) This cyclical stepsize shares the advantage of the "super-coovergence" property discussed in Smith & Topin (2017): cSG-MCMC can accelerate convergence for DNNs by up an order of magnitude.
Connection the Santa algorithm. It is interesting to note that our approach inverts steps of the Santa algorithm (Chen et al., 2016a) for optimization. Santa is a optimization algorithm with an exploration stage when T' = 1, then gradually anneals T' + 0 in a refinement stage for global optimization. In contrast, distributions, thus we explore with T = and sample with T 1. Another fundamental difference
goal is to draw samples for multimodal is that Santa adopts the traditional stepsize decay, while
the cyclical schedule.
We visually compare the difference between cyclical and traditional step size schedules (described in Section 2) in Figure 1. The cyclical SG-MCMC algorithm is presented in Algorithm 1.
4

---

Published as a conference paper at ICLR 2020
Connection to Parallel MCMC. Running parallel Markov chains is natural and effective way to draw samples from multimodal distributions (VanDerwerken & Schmidler, 2013; Ahn et al., 2014). However, the training cost increases linearly with the number of chains. Cyclical SG-MCMC can be seen as an efficient way to approximate parallel MCMC. Each cycle effectively estimates a different region of posterior. Note eyclical SG-MCMC runs along single training pass. Therefore, its computational cost is the same as single chain SG-MCMC while significantly less than parallel MCMC.
Combining Samples. In cyclical SG-MCMC, obtain samples from multiple modes of a poste- rior distribution by running the cyclical step size schedule for many periods. We provide a sampling combination scheme to effectively the collected samples in Section F in the appendix.
THEORETICAL ANALYSIS
Our algorithm is based on the SDE characterizing the Langevin dynamics: d0, = VU )dt + v2dW, where W, E Rd d-dimensional Brownian motion. In this section, we prove non- asymptotic convergence rates for the proposed cSG-MCMC framework with cyclical stepsize quence {au} defined in equation 1. For simplicity, we do not consider the exploration stage in the analysis as that corresponds to stochastic optimization. Generally, there are two different ways to describe the convergence behaviours of SG-MCMC. One characterizes the sample average over particular test function (e.g., Chen et al. (2015); Vollmer et al. (2016)); the other is terms of the Wasserstein distance (e.g., Raginsky et al. (2017); Xu et al. (2017)). We study both in the following.
Weak convergence Following Chen et al. (2015) and Vollmer et al. (2016), we define the posterior average of an ergodic SDE as: Φ - Jx (()) for some test function ((0) of interest. For the the sample average a defined as = K Σx= (0²²) to approximate Φ. We prove weak convergence of cSGLD in terms of bias and MSE, as stated in Theorem
corresponding algorithm with generated samples (0+)
Theorem 1. Under Assumptions 2 in the appendix, for smooth test function 6, the bias and MSE of cSLDD are bounded as:
BIAS: E3 =0 Cook
( + oo).
MSE: E (6 (6-0) (6-0)= 00=00 (6-))==0(1} + añj
(2)
aao
Convergence under the Wasserstein distance Next, we consider the more general case of SGLD and characterize convergence rates in terms of a stronger metric of 2-Wasserstein distance, defined
as:
W = inf (
|0 -0000(1110000)
where I' I'(p,)) v) is the set of joint distributions over (0, 0') such that the two marginals equal μ and v, respectively.
Denote the distribution of 0, in the SDE v. According Chiang & Hwang (1987), the stationary distribution matches our target distribution. Let μa be the distribution of the sample from our proposed eSGLD algorithm at the K-th iteration. Our goal is derive convergence bound on (2( ). We adopt standard assumptions as in most existing work, which are detailed in Assumption the appendix. Theorem 2 summarizes our main theoretical result.
Theorem 2. Under Assumption 3 in the appendix, there exist constants (Co, C₁ C2,Ca) indepen- dent of the stepsizes such that the convergence rate of our proposed cSGLD with cyclical stepsize sequence equation I bounded for all K satisfying (K mod M =0), as W2(KK, vo0) S
Kao + 6+ C2Kao) 20
3a + +C
Kon 2 + (C1
3a
+ oCo Kaozt].
Cyexp(
[(C]
2
8
2
16
4
Particularty, if we further assume ag O(K for V3 1. We(uk.Moc
5 Css +
(6 R=-T)
Co (6 2Ca
& + Co }z
5

---

Published as a conference paper at ICLR 2020
32
* %
cSGHMC SGHMC cSGLD
<50HMC
<SGLD
BrapShot-SGe
SGHVC
23
Test Enro (%)
cSOLD
Test Error (%G
SGD
SGLD
SGLD
-00
Mixin confiitiont
Number Cycles
(a) MDS
(b) Interpolation
(c) Comparison
Figure 3: Results of cSG-MCMC with DNNs on the CIFAR-I00 dataset. (a) MDS visualization in
weight space: cSG-MCMC show larger distance than traditional schedules. (b) Testing errors (%)
on the path of two samples: cSG-MCMC shows more varied performance. (c) Testing errors (%) as function of the number of cycles M: eSGLD yields consistently lower errors.
The bound decomposed into two parts: the first part measures convergence speed of exact solution to the stationary distribution, ie., V to Vx: the second part measures the numerical error, ie., between J&K and Vx ou- ii) The overall bound offers a same order of depen- dency on K as standard SGLD (please see the bound for SGLDD Section of the appendix. See also Raginsky et al. (2017)). iii) If one imposes stricter assumptions such as in the comvex case, the bound can be further improved. Specific bounds are derived in the appendix. We did not consider this case due to the discrepancy from real applications.
Remark 1.
5 EXPERIMENTS
We demonstrate cSG-MCMC several tasks, including synthetic multimodal distribution (Sec- tion 5.1), image classification on Bayesian neural networks (Section 5.2) and uncertainty estimation in Section 5.3. We also demonstrate cSG-MCMC can improve the estimate efficiency for uni-modal distributions using Bayesian logistic regression in Section A.2 in the appendix. We choose SLGD and SGHMC the representative baseline algorithms. Their eyclical counterpart called eSGLD and cSGHMC, respectively.
5.1 SYNTHETIC MULTIMODAL DATA
We first demonstrate the ability of cSG-MCMC for sampling from a multi-modal distribution on 2D mixture of 25 Gaussians. Specifi- cally, we compare eSGLD with SGLD in two setting: (1) parallel running with 4 chains and (2) running with a single chain, respectively. Each chain runs for 50k iterations. The step- size schedule of SGLD is ag x 0.05k-00 0.55 In eSGLD, we set M size ag = 0.09. The proportion of exploration stage B = Fig 2 shows the estimated density using sampling results for SGLD and eSGLD in the parallel setting. We observed that SGLD gets trapped in the local modes, depending the initial position. In any practical time period, SGLD could only characterize partial distribution. In contrast, eSGLD is able find and character- ize all modes, regardless of the initial position. cSGLD leverages large step sizes to discover new mode, and small step sizes to explore local modes. This result suggests cSGLD can be a significantly favourable choice in the non-asymptotic setting, for example only 50k iterations this case. The single chain results and the quantitative results on mode coverage are reported in Section A. of the appendix.
(a) Target
(b) SGLD
(c) cSGLD
and the initial step-
Figure 2: Sampling from mixture of 25 Gaus- sians shown in (a) for the parallel setting. With budget of 50k 4 = 200k samples, traditional SGLD (b) has only discovered 4 of the 25 modes, while our eSGLD in (c) has fully explored the distribution.
5.2 BAYESIAN NEURAL NETWORKS
We demonstrate the effectiveness of cSG-MCMC Bayesian neural networks for classification CIFAR-10 and CIFAR- 100. We compare with (i) traditional SG-MCMC; (ii) traditional stochastic optimization methods, including stochastic gradient descent (SGD) and stochastic gradient descent

---

Published as a conference paper at ICLR 2020
with momentum (SGDM); and (iii) Snapshot: stochastic optimization ensemble method method with a the cyclical stepsize schedule (Huang et al., 2017). We use a ResNet-18 (He et al., 2016) and run all algorithms for 200 epochs. We report the test errors averaged over 3 runs, and the standard error (+) from the mean predictor.
We set M 4 and Ozp 0.5 for eSGLD, cSGHMC and Snapshot. The proportion syper-parameter 3 =0.8 and 0.94 for CIFAR-10 and CIFAR-100, respectively. We collect samples per cycle. In practice, we found that the collected samples share similarly high likelihood for DNNs, thus one may simply set the normalizing term w; in equation 33 to be the same for faster testing.
We found that tempering helps improve performance for Bayesian inference with neural networks. Tempering for SG-MCMC was first used by Li et al. (2016a) as a practical technique for neural network training for fast convergence in limited time'. We simply use the prescribed temperature of Li et al. (2016a) without tuning, but better results of the sampling methods can be achieved by tuning the temperature. More details are in Appendix We hypothesize that tempering helps due to the overparametrization of neural networks. Tempering enables one to leverage the inductive biases of the network, while representing the belief that the model capacity can misspecified. on Safe Bayes, also known as generalized and fractional Bayesian inference, tempered posteriors are well-known to help under misspecification (c.g., Barron & Cover, 1991; de Heide et al., 2019; Grünwald et al., 2017).
work
For the traditional SG-MCMC methods, we found that noise injection early in training hurts con- vergence. To make these baselines competitive as possible, we thus avoid noise injection for the first 150 epochs of training (corresponding to the zero temperature limit of SGLD and SGHMC), and resume SGMCMC as usual (with noise) for the last 50 epochs. This scheme is similar to the exploration and sampling stages within one cycle of cSG-MCMC. We collect 20 samples for the MCMC methods and average their predictions in testing.
Testing Performance for Image Classification We report the testing errors in Table to com- pare with the non-parallel algorithms. Snapshot and traditional SG-MCMC reduce the testing er- rors on both datasets. Performance variance for these methods is also relatively small, due the multiple networks in the Bayesian model av- erage. Further, cSG-MCMC significantly out- performs Snapshot ensembles and the traditional SG-MCMC, demonstrating the importance of (I) capturing diverse modes compared to traditional SG-MCMC, and (2) capturing fine-scale charac- teristics of the distribution compared with Snap- shot ensembles.
CIFAR-10
CIFAR-100
SGD
5,2910.15
23.6110.00
SGDM
5.1710.09
22.98:10.27
Snapshot-SChi
4,4610004
20.8310.01
Snapshot-SGIM
1.39110011
20.8111.110
SGLD
5.20+00.06
23.23+-0001
cSGLD
4,29+0.06
20.55+0006
SGHMC
4.93110.1
22.6010.117
cSGHMC
4.27110.33
20.5010.11
Table 1: Comparison of test error (%) between cSG-MCMC with non-parallel algorithms. cS- GLD and cSGHMC yields lower errors than their optimization counterparts, respectively.
Diversity in Weight Space. To further demonstrate our hypothesis that with a limited budget cSG- MCMC can find diverse modes, while traditional SG-MCMC cannot, we visualize the 12 samples we collect from cSG-MCMC and SG-MCMC on CIFAR-100 100 respectively using Multidimensional Scaling (MDS) in Figure (a). MDS uses a Euclidean distance metric between the weight of sam- ples. We see that the samples of cSG-MCMC form 4 clusters, which means they are from 4 different modes in weight space. However, all samples from SG-MCMC only form one cluster, which indi- cates traditional SG-MCMC gets trapped in one mode and only samples from that mode.
Diversity in Prediction. To further demonstrate the samples from different cycles of cSG-MCMC provide diverse predictions we choose one sample from each cycle and linearly interpolate between two of them (Goodfellow et al., 2014; Huang et al., 2017). Specifically, let (()) be the test error of sample with parameter 0. We compute the test error of the convex combination of two samples J [A0] + (1 - 2)02), where À E [o, 1].
We linearly interpolate between two samples from neighboring chains of cSG-MCMC since they are the most likely to be similar. We randomly select samples from SG-MCMC. If the samples from the same mode, the test error of the linear interpolation of parameters will be relatively
7

---

Published as a conference paper at ICLR 2020
Method
Cyclical+Parallel 200/800
Pecralsing+Parallel 200/800
Derrea
Synlic
Cost
100/400
200/200
Sampler
SGLD
SGHMC
SGLD
SGHMC
SGLD
SGHMC
SGLD
SGHMC
CIFAR-10
4.09
3.95
4.15
4.09
5.11
4.52
4.29
4.27
CIFAR-100
19.37
19.19
20.29
19.72
21.16
20.82
20.55
20.50
Table 2: Comparison of test error (%) between cSG-MCMC with parallel algorithm (M=4 chains) on CIFAR-10 10 and CIFAR-100, The method is reported in the format of "ste--size schedule (cyclical or decreasing) + single/parallel chain". The cost is reported in the format of "#epoch per chain / #epoch used in all chains". Note that a parallel algorithm with a single chain reduces to a non- parallel algorithm. Integration of the cyclical schedule with parallel algorithms provides lower test- ing errors.
smooth, while if the samples from different modes, the test error of the parameter interpolation will have a spike when is between and 1.
We show the results of interpolation for eSG-MCMC and SG-MCMC on CIFAR- in Figure 3 (b). We see a spike in the test error in each linear interpolation of parameters between two samples from neighboring chains in cSG-MCMC while the linear interpolation for samples of SG-MCMC is smooth. This result suggests that samples of cSG-MCMC from different chains are from different modes while samples of SG-MCMC are from the same mode.
Although the test error of a single sample of cSG-MCMC is worse than that of SG-MCMC shown in Figure 3 (c), the ensemble of these samples significantly improves the test error, indicating that samples from different modes provide different predictions and make mistakes on different data points. Thus these diverse samples can complement each other, resulting in lower test error, and demonstrating the advantage of exploring diverse modes using cSG-MCMC.
Comparison to Parallel MCMC. cSG-MCMC can be viewed as economical alternative to parallel MCMC. We verify how closely cSG-MCMC can approximate the performance parallel MCMC, but with more convenience and less computational expense. We also note that we can improve parallel MCMC with the proposed cyclical stepsize schedule.
We report the testing errors in Table 2 to compare multiple-chain results. (1) Four chains used, each runs 200 epochs (800 epochs in total), the results are shown in the first 4 columns (Cycli- Pal+Parallel vs Pecreasing+Parallee) We see that cSG-MCMC variants provide lower errors than plain SG-MCMC. (2) We reduce the number of epochs (#epoch) of parallel MCMC to 100 epoch each for decreasing stepsize schedule. The total cost is 400 epochs. We compare its performance with cyclical single chain (200 epochs in total) in the last 4 columns IDecreasing-Paraan cal+ein We see that the cyclical schedule running on a single chain performs best even with half the computational cost! All the results indicate the importance of warm re- starts using the proposed cyclical schedule. For a given total cost budget, the proposed cSGMCMC is preferable parallel sampling.
vs Cycli-
Comparison to Snapshot Optimization. We carefully compared with Snapshot, our cSG- MCMC can be viewed as the sampling counterpart of the Snapshot optimization method. We plot the test error wrr. various number of cycles M in Fig. 3. As M increases, cSG-MCMC and Snapshot both improve. However, given a fixed M, cSG-MCMC yields substantially lower test errors than Snapshot. This result is due to the ability of cSG-MCMC better characterize the local distribution of modes: Snapshot provides a singe minimum per cycle, while eSG-MCMC fully exploits the mode with more samples, which could provide weight uncertainty estimate and avoid over-fitting
Results on ImageNet. We further study dif- ferent learning algorithms on large-scale dataset, ImageNet. ResNet-50 is used as the ar- chitecture, and 120 epochs for each run. The results on the testing set are summarized in Ta- ble 3, including NLL, Topl and Top5 accuracy (%), respectively. 3 cycles are considered for both cSGHMC and Snapshot, and collect 3 samples per cycle. We see that cSGHMC yields the lowest testing NLL., indicating that the cy-
NLL
Top1 1
Top5 t
SGDM
0.9595
76.046
92.776
Snapshot-SGDD
0.8941
77.142
93.344
SGHMC
0.9308
76.274
92,994
eSGHMC 0.8882
77.114
93.524
Table 3: Comparison on the testing set of Ima- geNet. cSGHMC yields lower testing NLL than Snapshot and SGHMC.
8

---

Published as a conference paper at ICLR 2020
cle schedule is an effective technique explore the parameter space, and diversified samples can help prevent over werrfitting.
5.3 UNCERTAINTY EVALUATION
To demonstrate how predictive uncertainty ben- efits from exploring multiple modes in the pos- terior of neural network weights, we consider the task of uncertainty estimation for out-of- distribution samples (Lakshminarayanan et al.,
<SCHMC
:BGLD
Srapahol-GDDMM SGDWOM
Empirical CDF
Srapshol sad
2017). We train three-layer MLP model on the standard MNIST train dataset until convergence using different algorithms, and estimate the en- tropy of the predictive distribution NIST dataset (Bulatov, 2011) 1). Since the samples from the notMNIST dataset belong to the unseen classes, ideally the predictive distribution of the trained model should be uniform the notM- NIST digits, which gives the maximum entropy.
SGD
the notM-
Entropy
Figure 4: Empirical CDF for the entropy of the predictive distribution on notMNIST dataset. cSGLD and cSGHMC show lower probability for the low entropy estimate than other algo- rithms.
In Figure 4, plot the empirical CDF for the entropy of the predictive distributions on notM- NIST. We see that the uncertainty estimates from cSGHMC and cSGLD are better than the other methods, since the probability
low entropy prediction is overall lower. cSG-MCMC algorithms explore more modes in the weight space, each mode characterizes meaningfully different represen- tation of MNIST data. When testing on the out-of-distribution dataset (notMNIST), each mode can provide different predictions over the label space, leading more reasonable uncertainty estimates. Snapshot achieves less entropy than cSG-MCMC, since it represents each mode with a single point.
The traditional SG-MCMC methods also provide better uncertainty estimation compared to their optimization counterparts, because they characterize a local region the parameter space, rather than single point. cSG-MCMC can be regarded combination of these two worlds: wide coverage of many modes in Snapshot, and fine-scale characterization of local regions SG-MCMC.
DISCUSSION
We have proposed cyclical SG-MCMC methods to automatically explore complex multimodal dis- tributions. Our approach is particularly compelling for Bayesian deep learning, which involves rich multimodal parameter posteriors corresponding to meaningfully different representations. We have also shown that eyclical methods explore unimodal distributions more efficiently. These results are in accordance with theory we developed to show that cyclical SG-MCMC will converge faster to samples from stationary distribution in general settings. Moreover, show cyclical SG-MCMC methods provide more accurate uncertainty estimation, by capturing more diversity in the hypothesis space corresponding to settings of model parameters.
While MCMC was once the gold standard for inference with neural networks, it is now rarely used in modern deep learning. We hope that this paper will help renew interest in MCMC for posterior inference in deep learning. Indeed, MCMC is uniquely positioned to explore the rich multimodal posterior distributions of modern neural networks, which can lead improved accuracy, reliability, and uncertainty representation.
ACKNOWLEDGEMENTS
AGW was supported by an Amazon Research Award, Facebook Research, NSF 1-DISRE 193471, NIH RO1 DA048764-01A1, NSF IIS- 116-156887, and NSF 111-191
REFERENCES
Sungjin Ahn, Babak Shahbaba, and Max Welling. Distributed stochastic gradient MCMC, In ICML, 2014.

---

Published as a conference paper at ICLR 2020
Peter Auer, Mark Herbster, and Manfred K Warmuth. Exponentially many local minima for single neurons. In NIPS, 1996.
Rémi Bardenet, Arnaud Doucet, and Chris Holmes. Towards scaling up Markov Chain Monte Carlo: an adaptive subsampling approach. In ICML, 2014.
Andrew R Barron and Thomas M Cover. Minimum complexity density estimation. IEEE transac- fions on information theory, 37(4):034-1155, 1991.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in neural networks. ICMI., 2015.
François Bolley and Cédric Villani. Weighted to transportation inequalities. In Annales de la Faculte des sciences de Toulouse. Université Paul Sabatier, 2005.
inequalities and applications
Yaroslav Bulatov. Not MNIST Dataset. 2011. http://yarrslarrb.blospptt com/ 2011/09/ httt://ttiiitttatttesssee .ttall. .tml.
Changyou Chen, Nan Ding, and Lawrence Carin. On the convergence of stochastic gradient MCMC algorithms with high-order integrators. In NIPS, 2015.
Changyou Chen, David Carlson, Zhe Gan, Chunyuan Li, and Lawrence Carin. Bridging the gap between stochastic gradient MCMC and stochastic optimization. In Artificial Intelligence and Statistics, 2016a.
Changyou Chen, Ruiyi Zhang, Wenlin Wang, Bai Li, and Liqun Chen. A unified particle- optimization framework for scalable bayesian sampling. arXiv preprint arXiv:1800 1659,, 2018.
Haoyu Chen, Daniel Seita, Xinlei Pan, and John Canny. An efficient minibatch acceptance test for Metsopoliis-Hastings. arXiv preprint arXiv:1610.06844 2016b.
Tianqi Chen, Emily Fox, and Carlos Guestrin. Stochastic gradient Hamiltonian Monte Carlo. In ICMI., 2014.
Tzuu-Shuh Chiang and Chii-Ruey Hwang. Diffusion for global optimization in SIAM J. Control Optim., pp. 737-753, 1987. ISSN 0363-0129, doi: 10. 10.1137/0325042. URL http:// / http//xxoo////// doi. org/10.1137 13355422
Anna Choromanska, Mikael Henaff, Michael Mathieu, Gérard Ben Arous, and Yann LeCun. The loss surfaces of multilayer networks. In Artificial Intelligence and Statistics, 2015.
Arnak S. Dalalyan and Avetik Karagulyan. User-friendly guarantees for the langevin monte carlo with inaccurate gradient. Stochastic Processes and their Applications, 2019. ISSN 0304-4149. doi: http:://wo.ogg/lll.00.0.o.pppppp 0010000000000...2229990200.66660 URL http: http:///wwwww.cm www. www.wwwciinnedire......... com/ science/articles hit.enec//rrrceeee/////000111411
Rianne de Heide, Alisa Kirichenko, Nishant Mehta, and Peter Grünwald. Safe-bayesian generalized linear regression. arXiv preprint arXiv: 1xX0::9910.09227. 2019.
Nan Ding, Youhan Fang, Ryan Babbush, Changyou Chen, Robert D Skeel, and Hartmut Neven. Bayesian sampling using stochastic gradient thermostats.
NIPS, 2014.
Meire Fortunato, Charles Blundell, and Oriol Vinyals. Bayesian recurrent neural networks. arXiv preprint urXiv:1704.02777 2017.
Hao Fu, Chunyuan Li, Xiaodong Liu, Jianfeng Gao, Asli Celikyilmaz, and Lawrence Carin. Cyclical annealing schedule: A simple approach to mitigating KL vanishing. NAACL, 2019.
Zhe Gan, Chunyuan Li, Changyou Chen, Yunchen Pu, Qinliang Su, and Lawrence Carin. Scalable Bayesian learning of recurrent neural networks for language modeling. ACL, 2016.
Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of DNNs. In Advances in Neural Information Processing Systems, pp. 8789-8798, 2018.
10

---

Published as a conference paper at ICLR 2020
Ian J Goodfellow, Oriol Vinyals, and Andrew M Saxe. Qualitatively characterizing neural network optimization problems. arXiv preprint arXiv: 1412:1411.,554, 2014.
Peter J Green. Reversible jump MCMC computation and bayesian model determination. Biometrika, 82(4):711-732, 1995.
Peter Grünwald, Thijs Van Ommen, et al. Inconsistency of bayesian inference for misspecified linear models, and proposal for repairing it. Bayesian Analysis, 12(4):
2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR, 2016.
José Miguel Hernández-Lohate and Ryan Adams. Probabilistic backpropagation for scalable learn- ing of Bayesian neural networks. In ICML, 2015.
Matthew D Hoffman and Andrew Gelman. The no-u-turn sampler: adaptively setting path lengths in hamiltonian monte carlo. Journal of Machine Learning Research, 15(1)11933-162) 2014.
Gao Huang, Yixuan Li, Geoff Pleiss, Zhuang Liu, John E Hoperoft, and Kilian Q Weinberger. Snapshot ensembles: Train get for free. ICLR, 2017.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.048.00 2016.
Anoop Korattikara, Yutian Chen, and Max Welling, Austerity in MCMC land: Cutting the Satropolis-Hastting budget. In JCML, 2014.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In NIPS, 2017.
Chunyuan Li, Changyou Chen, David E Carlson, and Lawrence Carin. Preconditioned stochastic gradient Langevin dynamics for deep neural networks. In AAAI, 2016a.
Chunyuan Li, Andrew Stevens, Changyou Chen, Yunchen Pu, Zhe Gan, and Lawrence Carin. Learn- ing weight uncertainty with stochastic gradient MCMC for shape classification. In CVPR, 2016b.
Chang Liu, Jingwei Zhuo, and Jun Zhu. Understanding meme dynamics as flows on the wasserstein space. arXiv preprint
002200282. 2019.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. 2016.
Yi-An Ma, Tianqi Chen, and Emily Fox. A complete recipe for stochastic gradient MCMC. In NIPS, 2015.
David JC MacKay. practical bayesian framework for backpropagation networks. Neural compu- tation, 1992.
Wesley Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson A simple baseline for bayesian uncertainty in deep learning. In Advances in Neural Information Processing Systems, pp. 13132-13143, 2019.
J. C. Mattingly, A. M. Stuart, and M. V. Tretyakov. Construction of numerical time-average and stationary measures via Poisson equations. SIAM J. NUMER. ANAL,, 58(2):552-577, 2010.
Radford M Neal. Bayesian learning for neural networks. New York: Springer- Verlag, 1996.
Arvind Neelakantan, Luke Vilnis, Quoe V Le, Ilya Sutskever, Lukasz Kaiser, Karol Kurach, and James Martens. Adding gradient noise improves learning for very deep networks. ICLR workship, 2016.
Anh Nguyen, Jeff Clune, Yoshua Bengio, Alexey Dosovitskiy, and Jason Yosinski. Plug & play generative networks: Conditional iterative generation of images in latent space. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 4467-4477, 2017.

---

Published as a conference paper at ICLR 2020
Adrian E Raftery, Michael A Newton, Jaya M Satagopan, and Pavel N Krivitsky. Estimating the integrated likelihood via posterior simulation using the harmonic mean identity. 2006.
Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky. Non-convex learning via stochastic
gradient Langevin dynamics: nonasymptotic analysis. arXiv preprint arXiv:1702.03844 2017,
Yunus Saatchi and Andrew Gordon Wilson. Bayesian GAN. NIPS, 2017.
Filippo Santambrogio. (Euclidean, metric, and Wasserstein) gradient flows: an overview. Bulletin of Mathematical Sciences, 7(1):87-154, Apr 2017.
Leslie N Smith and Nicholay Topin. Super-convergence: Very fast training of residual networks
using large learning rates. arXiv preprint /78.001708..7/200, 2017.
Yee Whye Teh, Alexandre H Thiery, and Sebastian Vollmer. Consistency and fluctuations for stochastic gradient Langevin dynamics. The Journal of Machine Learning Research, 2016.
Douglas VanDerwerken and Scott Schmidler. Parallel Markov Chain Monte Carlo. arXiv preprint arXiv:1312.7479) 2013.
S. J. Vollmer, K. C. Zygalakis, and Y. W. Tch. (Nym-ttsympiotic properties of stochastic gradient Langevin dynamics. Technical Report 1501:1550000033,, University of Oxford, UK, January 2015. URL htt.ttt/taxii...../// abs 1111111111.00 00438.
Sebastian J. Vollmer, Konstantinos C. Zygalakis, and Yee Whye Tch. Exploration of the (non- Jasymptotic bias and variance of stochastic gradient langevin dynamics. Journal of Machine Learning Research, 17(159):1-48 2016.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient Langevin dynamics. In ICML, 2011.
Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of Langevin dynamics based algorithms for nonconvex optimization. arXiv preprini arXiv:1707.06616. 2017.
Jianyi Zhang, Ruiyi Zhang, and Changyou Chen. Stochastic Particle-Oplimizztion Sampling and the Aon-Asympootic Convergence Theory. arXiv e-prints, art. urXiv:1809.01299 Sep 2018.
Y. Zhang, Liang, and M. Charikar. hitting time analysis of stochastic gradient Langevin dy- namics. In COLT, 2017.
12

---

Published as a conference paper at ICLR 2020
A EXPERIMENTAL RESULTS
A.1 SYNTHETIC MULTIMODAL DISTRIBUTION
The density of the distribution is
25
F(x) = Σ 1=1
(2 2);
0.03 1 (-4, -2,0,,,,,, x (-,, 2,0,2,4),
where À = 23.
0.08
In Figure 5, show the estimated density for SGLDD and eSGLDD in the non-parallel setting.
(a) Target
(b) SGLD
(c) cSGLD
Figure 5: Sampling from mixture of 25 Gaussians in the non-parallel setting. With budget of 50K samples, traditional SGLD has only discovered one the 25 modes, while our proposed cSGLD has explored significantly more of the distribution.
To quantitatively show the ability of different algorithms to explore multi-modal distributions, we define the mode-coverage metrie: when the number of samples falling within the radius r of mode center is larger than a threshold ñ, we consider this mode covered. On this dataset, we choose 0.25 and 100. Table 4 shows the mode-coverage for several algorithms, based 10 different runs.
Algorithm SGLD
Mode coverage
1.810.13
eSGLD
6.7=0.52
Parallel SGLD
18:10.47
Parallel cSGLD
24.4+10.22
Table 4: Mode coverage over 10 different rums, + standard error.
A.2 BAYESIAN LOGISTIC REGRESSION
We consider Bayesian logistic regression (BLR) on three real-world datasets from the UCI repos- itory: Australion (15 covariates, 690 data points), German (25 covariates, 1000 data points) and Heart (14 covariates, 270 data points). For all experiments, we collect 5000 samples with 5000 burn-in iterations. Following the settings in Li et al. (2016a), we report median effective sample size (ESS) in T.ble 5.
Note that BLR is unimodal in parameter space. We use this experiment as adversarial situation for cSG-MCMC, which we primarily designed to explore multiple modes. note that even in the unimodal setting, cSG-MCMC more effectively explores the parameter space than popular altema- tives. We can also use these experiments to understand how samplers respond to varying parameter dimensionality and training sizes.
Overall, cCG-MCMC dramatically outperforms SG-MCMC, which demonstrates the fast mixing rate due the warm restarts. On the small dataset Heart, SGHMC and cSGHMC achieve the
13

---

Published as a conference paper at ICLR 2020
same results, because the posterior of BLR on this dataset is simple. However, in higher dimen- sional spaces (e.g., Australian and German), cSG-MCMC shows significantly higher ESS; this result means that each cycle in cSG-MCMC characterize different region of the posteriors, combin- ing multiple cycles yields more accurate overall approximation.
Australian
German
Heart
SGLD
1676
492
2199
cSGLD
2138
978
2541
SGHMC
1317
2007
5000
cSGHMC
4707
2436
5000
Table Effective sample size for samples for the unimodal posteriors in Bayesian linear regression, obtained using cyclical and traditional SG-MCMC algorithms,, respectively.
B ASSUMPTIONS
B.1 ASSUMPTIONS IN WEAK CONVERGENCE ANALYSIS
In the analysis, we define functional &b that solves the following Poisson Equation:
(v)(0)) (0x)) o, equivalently,
K Cv(OO) - -6
The solution functional (5((k)) characterizes the difference between o(0x) and the posterior average for every 4.. thus would typically possess unique solution. which is at least as smooth as á under the elliptic or hypoelliptic settings (Mattingly et al., 2010). Following Chen et al. (2015); Vollmer al. (2016), we make certain assumptions on the solution functional, th of the Poisson equation equation 3.
Assumption 2. zi and its up to 3rd-order derivatives, D are bounded by a function V, i.e,, ||"*>>ll < H& for k = (0, 2,2,), Hg,Pk O. Furthermore, the expectation of {0g) is bounded: sup, (fp( < co, and V is smooth such that supse(0.1) VP (s0 + (1 8) 00) S
CVP (0) + VP (0))), v0, 0', & [pp for some C > O.
B.2 ASSUMPTIONS IN CONVERGENCE UNDER THE WASSERSTEIN DISTANCE
Following existing work in Raginsky al. (2017), we adopt the following standard assumptions summarized in Assumption 3.
Assumption 3.
There exists some constants 2 0 and B Z 0. such that (0) < and
(U <. B.
The function U is Lu-smooth: [V)(w) VU(v)) Lu - el|-
The function U is (m.,, b) dissipative, which means for some me and b
(w, (U())) 2 myll
There exists some constant 8 E (0,1), such that E[IVVÜ(()) [U(w) s
20 wM 2 B²).
We can choose which satisfies the requirement: Kn == log ʃ elwlll po(w)dw < xc.
C PROOF OF THEOREM 1
To prove the theorem, we borrow tools developed by Chen et al. (2015); Vollmer al. (2015). We first rephrase the stepsize assumptions in general SG-MCMC in Assumption 4.
Assumption 4. The algorithı adopts an N-th order integrator. The step sizes {hx} are such that
0 < h841 < hr, and satisfy 1) E hx = oo; and 2) linn-
Σx-1 0.
14

---

Published as a conference paper at ICLR 2020
Our prove be derived by the following results from Chen et al. (2015).
Lemma (Chen et al. (2015)). Let SK - Ek=1 his Under Assumptions 2 and 4, for smooth test function 4, the bias and MSE of a searreusiingslep--iiee SG-MCMC with a Nth-order integrator at time S are bounded as:
1
Σx
N+1
BIAS: EØ =0
(4)
5K
SK
MSE: E δ)
S C
h
lAvill
1 SK
(EK
Ck=1
h +2 Sk
(5)
Sk
Note that Assumption 4 is only required if one wants to prove the asymptotically unbias of an algorithm. Lemma still applies even if Assumption is not satisfied. this case one would obtain a biased algorithm, which is the case of cSGLD.
Proof of Theorem I. Our results is actually a special case of Lemma 1. To see that, first note that our cSGLD adopts first order integrator, thus N = 1. To proceed, note that Sx = E 0g OaagK). and
Tmod(j 1, [.[K/M] 1)²
Σ 1=
04+1
0
cos
[K/M]
j=0
2 K-
Tmod(j - -1, K/MM 1)3
Σ
[cos?
K/M
j=0
a
K
M
3a
+ M) =
(6)
M
2
8
As result, for the bias, we have
1
Σ k=
NN41
3a K/j
E 0
+
+
SK
SK
anK
0
+
OooK
For the MSE, note the first term omitted in the big-O notation, ie.,
E,
42 E
AV 2 has a higher order than other terms, thus it
K
2 =
3a K/8K/8 )²)
E
+
anK
KgK
1
+ 2
+ao
Kg
This completes the proof.
D PROOF OF THEOREM 2
Proof of the bound for Wz W2(KK, in eSGLD. Firstly, we introduce the following SDE
d0, = - (O,))dt + 22d,,,
(7)
Let v4 denote the distribution of 0c, and the stationary distribution of equation 34 be p(ODD), which means Voc = D).
- 02 VūL(0))a44 + 22 Further, let μ4 denote the distribution of 0t..
(8)
Since
W2(UK, (oo) S W2(UK, "E an) + DK o W Moo)
need to give the bounds for these parts respectively.
15

---

Published as a conference paper at ICLR 2020
D.1 PEK
For the first part, Wa(KK, (IEK,,KK o our proof is based the proof of Lemma 3.6 in Raginsky et al. (2017) with some modifications. We first assume E(VÜ(w)) (U(w), Ve R which a general assumption according to the way we choose the minibatch. And we define p(t) which
will be used in the following proof:
k
k+1
p(t)
{k: E 2
Σ
t
a
(10)
Then we focus on the following continuous-ting interpolation of 0g:
p(a)
ds V2 I' aw!o
8(t) =0u-
VÙ
0
1 as) k=1
(11)
j
where VÙ = Vūn for EΣin 0ii E oi). And for each k, 0 as) and 0g have the
same probability law Ml.
Since ((t) is not a Markov process, we define the following process which has the same one-iime marginals as ((t)
V(I) = 0. - 1f G. (V(s)) v2 [ aw!!
(12)
with
q(t) 0
G.(x) = E
VÙ
2
ai) (0(1)
(13)
1=1
05 t) and according to the proof of Lemma 3.6 in Raginsky et al. (2017), we can derive similar result for the relative entropy of P and P
Let Pt = CV((s) :0 t) and P C (8(s)
/ dP' log dP dp
DKL
Pb) =
1 / E B|( - (VVV
1 1 EI/VU G. (ds
16

---

Published as a conference paper at ICLR 2020
The last line follows the fact that [(((s)) = ((V(s)), ss.
Then we will let Ek=1 a and we can use the martingale property of the integral derive:
D PK
EE
P L at)
V
K-1
Og
E
VU((()) - ([())))
i=0
K
ap
((s)
<
E VU(((s) - (U(
0:)l
2d
2
/=0
R=1
g(s)
a(s)
E
(
0.)
G
a3)l 2
2
13 K-1
((*)
BI(((s) 2
ai)
(14)
2
j=0
E111 ah
k=1
1 K-
7(s)
7(3) 01s) G.
E
VU(O
az)
ds
(15)
2
Et-1a au
jm0
For the first part (14), we consider some EE Ohe Ek+1 ox:); for which the following holds:
((s) 0
ock
k=
--
Ou VV)(W((( + V2(W(") Wold
(s VL) + (s (x)) (VU(() VūL(Oe)) + v2(W!" - -wid)
Eizi an
(16)
Thus, we can use Lemma 3.1 and 3.2 in Raginsky et al. (2017) for the following result:
E (() A
ax 11 < 3 B
(0,((1 6ay-1d
S 12a |1 B²) + 6aj+1d
Hence we can bound the first part, (choosing 1),
<(s)
BI(((s) 0
0 || 2d
2
1=
Eizr a4
L3 K
12a 3
1 10 + B²) + Ga f
2
1=
K-1
< 12
[6(1)- + B2) + +dd] Σ 05t5k-1
max
as+1)
1=0
3 K
max
66L 11 BB2 3d
(17)
0STSK-1
17

---

Published as a conference paper at ICLR 2020
The last line (17) follows from² equation 6. The second part (15) can be bounded as follows:
1 k
a(s)
g(s)
-k-1
BII
Σ
a.)-
G2(
a ds
2
Ei oR
j
K-1
aj+1 B VU(0,) Vū(0))12
2
j=0
K-1
+ (L, + B²)
Σ
S a max
aj+1
0sisk-1
j=U
1 0 max 0SISK-1
(L) + BB²)(
0g
K-1
(cos(
Tmod(j. K/M)
) + 1))
2
K/M
j=0
Koo
a max B1) + + B²)(
0SiSK-1
2
Due to the data-procees processing inequality for the relative entropy, we have
D DKL(Ex l I (P (PP))
K-1
1
on B10((s) - 0
((s)
$
Σ
a;
lss
2
j=0
ak
R=1
1 K-1
s(a)
a(a)
E
VU
a;) Go
az)l ds
2 ==0
1 ok
k=1
3aA
$ L max
1|2 B²)
+ 3d]
05isK-1
8
(1E,11,11 B²) Kao
max 0SisK1
According to the proof of Lemma 3.2 in Raginsky et al. (2017), we can bound the term 0|0x||
8 2 S (1 200+1 my + 4a Mt B 8x 2| + 20 + 4 B² 204+1d dd
Similar to the statement of Lemma 3.2 in Raginsky et al. (2017), we can fix on E (0, A
my
4Mg
Then, we can know that
E 1 & (1 20 my + 40mmn M& E| + 200b + 40 + 20nd
(18)
g
where ammin defined as Olmin
an 2
cos
mod [K/M] -1. (K/MM1
[K/M]
+ +1].
There are two cases to consider.
If 20 my + 4 min Mf < 0, then from equation it follows that
20yd
E 2 10 2| < 2agb 22
d 2B² + B)
E 1.l + 2(b +
If < 20mmm my + 4 M < then iterating equation 18 gives
and + 20 B² and
E 0|002 < (1 20 my
40 mim M3 AT11011
3
(19)
Omin 20 M
200 (b + 21 d. Mmmin
< 2 +
(20)
3
Note: we only focus the case when K mod M 0.
18

---

Published as a conference paper at ICLR 2020
Now, we have
10 B²)
0SiSK-1
(Ko + 2(1 A
)(b 2132 + d)) + B2) Co
mggmmn
Due to the expression of and we can derive
Co is independent of og. Then we denote the (Cg + d) as C₁
Omin
S C1( B
+ oCo( Kao
(K |I Disi 2
Then according to Proposition 3.1 in Bolley & Villani (2005) and Lemma 3.3 in Raginsky et al. (2017), if we denote Ko + 26 + 2d as C2. we can derive the following result:
We(px, VEK MEKK )N S (12 + C2( ox)) [KKL(KKIISSS ,,,)
à DKL(HK bluk d
C2K }
KoCoou +
3C1ag
KoCoaw )
S (12 +
2 I[
+
8
2
16 4
D.2 W2(2E Moo)
We can directly get the following results from (3.17) in Raginsky et al. (2017) that there exist some positive constants (O3, C1),
W2(UEx au: Mo0) S C3 expe(
Σ /2\Css)
k=1
Now combining the bounds for WE(KK.PEE ox) and We(WEK on Voo), substituting og ((/KK), and noting W2(2E a Moo) decreases w.r.t. K, we arrive at the bound stated in the theorem.
E RELATION WITH SGLD
For the standard polynomially-ddcaasstttsssssss SGLD, the convergence rate is bounded
W2 Moo) S W2 (ā "IK hn)) + W2 (2 h4 Moo)
(21)
where W2(K,, "EK, Ao) - (6 + ho k== R L
1Dihh 7² + Doho
K )
(Diho Do hu
6
16
2
1m
and W2( hy Moo) < C3 exp(
Ca
Proof of the bound of W2(K,, Moo) in the standard SGLD. Similar to the proof of W2(UK, Moc) in cSGLD, we get the following update rule for SGLD with the stepsize following a polynomial decay i.e., h4 bg.
Bx+1 = 0 (ūx(0)) + 22h4416441
(22)
Let ju denote the distribution of f..
Since
W Walkk Voc) S W2(0k, u my)) W2 Stsi Ny Voo) we need to give the bounds for these two parts respectively.
(23)
19

---

Published as a conference paper at ICLR 2020
E.1 Wa(kk, MEK mn)
We first assume ((Vū(w)) = Vu(w), Ve E R which is a general assumption according to the way choose the minibatch. Following the proof in Raginsky al. (2017) and the analysis of the SPOS method in Zhang et al. (2018), we define the following p(t) which will be used in the following proof:
p(t) = (k
E
Z
h1
< 1
h
(24)
Then we focus on the following contimuous-time interpolation of 0g:
((t) =00 - /.¹ VÙ
p(s)
ds + v2 f aw!!
0
h+)
(25)
R=1
(26)
where VÙ VÙ for , his E 1.). And for each k. e h2) and Og have the
probability law jug- Since ((t) is not a Markov process, we define the following process which has the same one-time marginals as ((t)
V(I) - 0. / G. (V(s)) ds v2 L' aw!
(27)
with
a(t)
G,(r) = E
V
0
Σ
hz) 10(t)
(28)
i=1
Let Pt = (V(ss) 0 < t) and P/ == C (0(s) 0 0 s t) and according to the proof of
Lemma 3.6 in Raginsky et al. (2017), we can derive the similar result for the relative entropy P and P
/ dP log
dP dp
DKL
Pb) =
1 f E B(V - (VV(s)))
1 1 E| ((s)) G. (ss
20

---

Published as a conference paper at ICLR 2020
The last line follows the fact that [(((s)) = ((V(s)), ss.
Then we will let Σ by and we can use the martingale property of integral derive:
D DKL(PT
D ha P
Mx)
K
Eit
BI(VU(((s) - G.(((s))))ds
4 )=
Diun hx
K
1
BI - VU( 7(5)
1
<
h2) ld
2
Eis he
/=
K-1
a(+)
{(s)
1
+ 2 1=0
O
h2)
G.
(0
h 9
ds
EL-1
1=1
k=1
K-1
a(a)
( 0
1
(29)
2
j=0
he
k=1
9(s) ha) Go(
1
EI (0
1
(30)
2
Ei=
For the first part (29), we consider some
km hR, E1t hx), the following equation holds:
((s) 01
= --
ha VL) V2(W!0 wild
Dimih 1x
=- Σ Vo))) (s Σ (VU(()) (ŪL()))) V2(W5") -Wald
Wold
(31)
k=1
Thus, we can use Lemma 3.1 and 3.2 in Raginsky al. (2017) for the following result:
B|(((s)
< R
VU VU (0, )1 + 34 + Vū,(0)11 -V 6hz+1d
$ 12h3 [10,) B²) + 6hj+1d
Hence bound the first part, (choosing ho - 1),
D K
h2 B(((s)
((s)
8
b ds
2
Eisr AE
LE
K-1
<
12h 3+1 (L 12 + B²) + 6h +1 d
2
K-1
< Li
[6(L)B]10,|1 + B²) + +3d ( 0SicK-
12
max
1=0
n² hg
< 12
max
[61T3 12 B2) + +d
(32)
0515K-1
6
where the last line follows from the fact that
K-1
K-1
22
Σ
$ Σ
G++
(i+ 1)2
(j +
1)2
6
=
1=
21

---

Published as a conference paper at ICLR 2020
The second part (30) can be bounded follows:
K
Et=1 bR
E V ((
a(*)
1
h₂)
Gb( >
h1)l dss
2
j
K-1
hy41 (UH1B) - Vū(0,)11
2
K-
S 0 max 0Sisk
(10,110011 + B²)
h++1
j=0
K + (h)
0 max 05 0Sisk-1
j=1
Due to the data processon inequality for the relative entropy, we have
DKL (jx |u >,= ne)
Dxz (PV
P)))
L
K-1
q(*)
$
A
Σ
h₂)
1ds
2
j=0
lk
K-1
a(s)
9(x)
1
VU
h4)
(0(
hill
2 5=
Σi=ı h2
k=1
n2
S L3
max
10, + B²)
3d]
6 h/
0SisK-1
K
10, B20
max
0SISK-1
5
Similar to the proof of cSGLD, we have
E10,11 + B²) S Do
max 0SisK-1
Then we denote the 672 (Do + d) as Dj and we can derive
2 6 + a Doho
K
DRIlĀKl And S D1
/=1
Then according to Proposition 3.1 in Bolley & Villani (2005) and Lemma 3.3 in Raginsky et al. (2017), if we denote No + 2b + 2d as D2, we can derive the following result,
(2 "EX m
$ [12 + D2
12 [[Ka(ax 12 + ( 2/2
K = [12 D2 Σ 1110 [(ri + Doho Σ }
K
y122 + (Dihi 2=²
K + D Σ
)1/9
12
j=1 2j
Now we derive the bound for W/ W2(nK, VSK n
E.2
W2(2EK Au (oo)
We can directly get the following results from (3.17) in Raginsky et al. (2017) that there exist some positive constants (Ca, C4).
W2(WEK he voo) S C3 exp(-
hx/Ca)
22

---

Published as a conference paper at ICLR 2020
Based on the convergence error bounds, discuss an informal comparison with standard SGLD. Consider the following two cases. We must emphasize that since the term W2(HK, VE* ou in the equation 9 increases w.r.t. K, our must be set small enough in practice. Hence, in this informal comparison, we also og small enough make W2(KK, "'E,, og)) less important.
i) If the initial stepsizes satisfy ao 2 ho. our algorithm cSGLD runs much faster than the standard SGLD in terms of the amount of "diffusion time" i.e., the "t" indexing 0₂ in the continuous-time SDE mentioned above. This result follows from Σk=1 Org Kao and Σ _k=1 hy Ek=1 x (ho log K) < Kga, In standard SGLD, since the error described by W2(UK, VEK_ by increases w.r.t K, ho needs to be set small enough in practice to reduce the error. Following the general analysis of SGL.D in Raginsky et al. (2017); Xu el. (2017), the dominant ferm in the decomposition equation 21 will be W2(2EK by P/s) since it decreases exponentially fast with the increase of t and W2(jk, "I he.
is small due to the setting of small hg- Since Σ Ogg increases much faster in our algorithm than the term Σ hg in standard SGLD, our algorithm thus endows less error for K iterations, L..., W2(WEK au 1/50 < W2(WEK Voo). Hence, our algorithm outperforms standard SGLD, as will be verified in our experiments.
fi) Instead of setting the hy small enough, may consider increasing hg make standard SGLD run as "fast" as our proposed algorithm, i.e., ΣK h& EK ag. Now the We(ps by Voe) in equation 21 is almost the same as the W2(1E hy Moo) in equation 9. However, in this case, it is worth noting that ho scales K/ log K). We can notice that he is much larger than the an and thus the W2(KK: M5 ha.) cannot be ignored. Now the hn term in W2(Rx, VSE m would scale as O K2 logg K), which makes W2(nk, "EK_ ax) equation 21 much larger than our W2( "IK ),,)) defined in equation since (a/K2/ (KKK"/log log" K) O)ağ Again, our algorithm eSGLD achieves a faster convergence rate than standard SGLD.
F COMBINING SAMPLES
In cyclical SG-MCMC, we obtain samples from multiple modes of posterior distribution by run- ning the cyclical step size schedule for many periods. We now show how to effectively utilize the col- lected samples. We consider each cycle exploring different part of the target distribution p(0[D) on a metric space Ô As we have M cycles in total, the mnth cycle characterizes local region Om C O defining the "sub-posterior" distribution: Pm. (0)D) p(oj2)Le..
with wm = -Se,, (D0() where Wm is normalizing constant. For testing function f0), we often interested in its true posterior = f (O))).) The sample-based estimation is
expectation f
M
1 Km
f f=
Σ Wm fm with fm
Σ f(ofm))
(33)
Km
where Km is the number of samples from the mith cycle, and ((()) E e@m-
The weight for each cycle w; is estimated using the harmonic mean method (Green, 1995; Raftery al., 2006): wmm 1 Σfnm m ]- This approach provides a simple and consistent es- timator, where the only additional cost is to traverse the training dataset to evaluate the likelihood p(D)o(()) for each sample (!m)) We evaluate the likelihood once off-line and store the result for testing.
bm are not disjoint, we can assume new sub-regions é, which are disjoint and compute the estimator following
M K f(0())) (m))))
fm
Tem m==1 j=1
23

---

Published as a conference paper at ICLR 2020
where
Km smm (0)mm)
mm
m==1=1
and 1 e (0(m)) equals only when m))) E mm. By doing so, our estimator still holds even i.. not disjoint.
G THEORETICAL ANALYSIS UNDER CONVEX ASSUMPTION
Firstly, we introduce the following SDE
d0, (O.)d + v2dW,
(34)
Let 14 denote the distribution of l,, and the stationary distribution of equation 34 be p())D), which means 6o (()
However, the exact evaluation of the gradient VU computationally expensive. Hence, we need to adopt noisy evaluations of VU. For simplicity, we assume that at any point 0s. observe the value
V (U,) + S*
where GN =00,,,22 is a sequence of random (noise) vectors. Then the algorithm is defined as:
0++1= 0₂ ax+1 VU, + 22ar+IE441
(35)
Further, let μi denote the distribution of 02.
Following the existing work in Dalalyan & Karagulyan (2019), we adopt the following standard assumptions summarized in Assumption 5,
Assumption 5.
For some positive constants m and M, holds
U(0) ((') VZ (e 0') 2 (m/2)|l0 - (U(() VU(6)]22 S M|le 6'
for any 0, 0' IRd
(bounded bias) [[[ (<)) 82d
(bounded variance) Bills: E(Cx (x) odd
(independence of updates) Ek+1 in equation 35 independent of (G1, C2,..., Sk)
G.1 THEOREM
Under Assumption 5 in the appendix and ag mad( [ /////1/ (K/MM) + 1
(0, A 2, if we define the amdn as derive the the following bounds.
[K/M]
If m0min + Moo S 2, then W50) 2
(1 (1-men (1-mammn)) W2(Hg, (1.65Mag 3/2 +
82 2/2d2//2
(36)
m0min
1.65Ma
1/2 + Vmammin
If maman + MMa then W2(HK41, 5
(1.65Mag
3/2 + 20
8 8aan
(1 - (2 MM
W2 Unx)
2 Moo
1.65Ma
1/2 +5 + V2- 12-M2ap
Man
(37)
where the M, m, 5, positive constants defined in Assumption 5
24

---

Published as a conference paper at ICLR 2020
G.2 PROOF
Proof. According to the equation 1, we can find that the stepsize aj varies from oo to Omiins K/AA1-11///M)) +1 When dg
where Omin is defined as Osnnn - do
cos
2
[K/M
min(2/M, 1/m,, easy for to know that aue < min(2/ 2/2 1/m) for every 0. Then Pk < Now according
we can derive that all the Pk: - max(1 mar: Maa - 1) will satisfy
to the Proposition 2 in Dalalyan & Karagulyan (2019), we can derive the result that
W2(k4 + 1, v2 & {pk+1 (2 Mze) + L. d) + ax+1ō + + 2 (38)
Then we will use another lemma derived from Dalalyan & Karagulyan (2019).
Lemma 2. If A.B.C. C are non non-negative numbers such that A E (0.1) and the sequence of non-negaiive
numbers Ye satisfies the following inequality
y S [(1 A)yR CJ2 B²
for every integer Then,
C
B A C+VAB
(1 (1
+
Using Lemma 2, finish our proof now.
If min + Maa S 2, the Pk will satisfy Pk S mAmin for every lo 0. Then the equation 38 will turn into
W2(H++1, V20) ) < {(1 minmm)mmmnlllee W22 W2 + 1.65. Vz0)
+ an + (8ogd"/2)3
for every k > 0. Then we can set A = m0min- C = 1.65M + 02 B = 8and and we can get the result.
If mamin + Maa > 2, the Ph: will satisfy I Man - for every k > 0. Then the equation will turn into
W2(14+1, )2 < {[1 (2 Man)) 1.65M a2 + (o)
for every h: 0. Then can set A 2 Ma 1.65.(a 12 B 1/2 and we can get the result.
H FUTURE DIRECTION FOR THE WASSERSTEIN GRADIENT FLOWS
We would like point out that the convergence theorems developed in the above several sections can be potentially applied to study the convergence of the Wasserstein gradient flows (Santambrogio, 2017), which can be regarded as a continuous-time MCMC (Chen al., 2018; Liu al., 2019). The theorems may shed some lights on the stepsize choice of the Wasserstein gradient flows which is less studied the literature. We leave it as an interesting future work.
I HYPERPARAMETERS SETTING
1.1 SENSITIVITY OF HYPERPARAMETERS
Compared to SG-MCMC, there are two additional hyperparameters in Algorithm 1: the number of cycles M and the proportion of exploration stage 3. We now study how sensitive they are when comparing to the parallel MCMC. With the same setup in Section 5.2, We compare with M cycles and L epochs per cycle with running M chains parallel MCMC for epochs. The training budget is 200 epochs. In Table 2, .M 4 and 3 0.8 CIFAR-10 10. We compare eSGLD and parallel SGLD with smaller and larger values M and 3. In Table 6, we see that the conclusion that cSG-MCMC is better than parallel SG-MCMC holds with different values of M and B.
method
25

---

Published as a conference paper at ICLR 2020
1.2 HYPERPARAMETERS SETTING IN PRACTICE
Given the training budget, there is trade-off between the number of cycles M and the cycle length. We find that it works well in practice by setting the cycle length such that the model with opti- mization methods will be close to a mode after running for that length. (e.g. the cycle length for CIFAR-10 is 50 epochs. The model optimized by SGD can achieve about 5% error after 50 epochs which means the model is close but not fully converge to mode after 50 epochs.) Once the cycle length is fixed, M is fixed. 3 needs tuning for different tasks by cross-va validdaaiat..n.. Generally, 8 needs to be tuned so that the sampler has enough time to reach good region before starting sampling.
M = 2, 0.8
= 5, 3 0.8
M = 4, 3 0.7
M = 4, 3 0.9
cSGLD Parallel SGLD
4.27
4.33
4.08
4.34
5.49
7.38
6.03
6.03
Table 6: Comparison of test error (%) between cSG-MCMC and parallel algorithm with varying values of hyperparameters on CIFAR-I0.
J TEMPERING IN BAYESIAN NEURAL NETWORKS
Tempering is common in modern Bayesian deep learning, for both variational inference and MCMC approaches (e.g., Li al., 2016a; Nguyen et al., 2017; Fortunato et al., 2017). In general, tempering reflects the belief that the model capacity is misspecified. This combination of beliefs with data is what shapes the posterior we want to use to form a good predictive distribution.
Although we use the prescribed temperature in PSGLD (Li et al., 2016a) for all neural network experiments the main text (T = 0.0045), we here investigate the effect of temperature T on performance. We show negative log-likelihood (NLL) and classification error as function of tem- perature on CIFAR- and CIFAR- using eSGLD with the same setup as Section 5.2. We consider T E [1, 0.5, 0.1, 0.05, 0.01, 0.005, 0]. Figure 6 and 7 show the results CIFAR-100, respectively. On CIFAR-10, the best performance is achieved at T = 0.1 with NLL 0.1331 and error 4.22%. On CIFAR-IOK the best performance is achieved at T 0.01 with NLL 0.7835 and error 20.53%. We find that the optimal temperature is often less than 1. We hypothesize that this result is due to the model misspecification common to neural networks.
CIFAR-10 and
Indeed, modern neural networks are particularly overparametrized. Tempering enables one to use model with similar inductive biases modern neural network, but with a more well calibrated capacity (which is especially important when we are doing Bayesian integration instead of optimiza- tion). Indeed, we show that by sampling from the tempered posterior, we outperform optimization. Learning the amount of tempering by cross-vaie cross-validation is principled way of aligning the tempering procedure with representing a reasonable posterior. We have shown that sampling with eSGMCMC with tempering helps in terms of both NLL and accuracy, which indicates that we are finding better predictive distribution.
0.24
0.065
0.22
0.060
0.20
Error
0.055
0.18
0.050
0.16
0.045
0.14
0.01
0.1
0
0.01
0.1
1
Temperature
Temperature
(a) Test negative logelikelihood
(b) Test еттог
Figure 6: NLL and error (%) as a function of temeprature on CIFAR-10 using cSGLD. The best performance of both NLL and error is achieved T = 0.1.
26

---

Published as a conference paper at ICLR 2020
1.05
0.25
1.00
0.24
Erer
0.23
0.90
0.22
0.85
0.21
0.80
0.01
0.01
0.1 Temperature
Temperature
(a) Test negative log-likelihood
(b) Test erгоr
Figure 7: NLL and error (%) as a function of temeprature on CIFAR-100 using eSGLD, The best performance of both NLL and error is achieved T 0.01.
K EXPERIMENTAL SETTING DETAILS
K. BAYESIAN LOGISTIC REGRESSION
For both eSGLD and eSGHMC, M 100, 3 0.01. For cSGLD, ag 1.2, 1.5 for Aus- trilian, German and Hear respectively. For cSGHMC an = 0.5, 0.3, 1.0 for Austrilian, German and Hear respectively. For SG-MCMC, the stepsize is for the first 5000 iterations and then switch to the decay schedule (2) with h = 0, 7 = 0.55. aN = 1.2, 0.5, 1.5 for Austrilian, German and Hear respectively for SGLD and a. 0.5, 0.3, 1.0 for Austrilian, German and Hear respectively for SGHMC. l = 0.5 in cSGHMC and SGHMC.
Assume that we collect (0m)m samples. Effective sample size (ESS) is computed by
B
ESS
1 1+2
B-
(1
B)ps
B
where is estimated by
B
P.
Σ
(0s i)) (
@ 8)
b=st1
Similar to Hoffman & Gelman (2014), 8² and p are obtained by running an independent sampler. We use HMC in this paper.
K.2 BAYESIAN NEURAL NETWORKS
For SG-MCMC, the stepsize decays from 0.1 to 0.001 for the first 150 epochs and then switch to the decay schedule (2) with a 0.01, and ? 0.5005. 17 0.9 eSGHMC, Snapshot-SGri SGDM and SGHMC.
K.3 UNCERTAINTY EVALUATION
For both cSG-MCMC and Snapshot, = = 0.8 in cGGMMCMC ag = 0.01 and 0.008 for cSGLD and cSGHMC respectively. For SG-MCMC, the stepsize is for the first 50 iterations and then switch to the decay schedule (2) with = 0, = 0.5005. aN = 0.01 for SGLD and aN 0.008 for SGHMC. 7 0.5 in eSGHMC, Snapshot-SGDM and SGHMC.
27


Reviews:
[{"review_id": "SJxD4x_TYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "The paper develops a cyclical stepsize schedule for choosing stepsize for Langevin dynamics. \nThe authors prove the non-asymptotic convergence theory of the proposed algorithm. Many experimental results, including ImageNet, are given to demonstrate the effectiveness of the proposed method. \n\nHere I suggest that authors also need to point out that the continuous-time MCMC is the Wasserstein gradient flow of KL divergence. The bound derived in this paper focus on the step size choice of gradient flows. This could be a good direction for combining gradient flows studies in optimal transport and MCMC convergence bound for the choice of step size. \n\nOverall, I think that the paper is well written with clear derivations. I strongly suggest the publication of this paper. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1eVwgy15B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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": "The paper propose a new MCMC scheme which is demonstrated to perform well for estimating Bayesian neural networks. The key idea is to not keep lowering the step sizes, but -- at pre-specified times -- go back to large step sizes.\n\nThe paper is timely, the proposed algorithm is novel, and the theoretical analysis also seem quite novel.\n\nMy key concern is that with MCMC sampling it is often quite difficult to tune parameters, and by introducing more parameters to tune when step sizes should increase, I fear that we end up in a \"tuning nightmare\". How sensitive is the algorithm to choice of parameters?\n\nI would expect that the proposed algorithm is quite similar to just running several MCMCs in parallel. The authors does a comparison to this and show that their approach is significantly faster due to \"warm restarts\". Here I wonder how sensitive this conclusion is to choice of parameters (see nightmare above) ? I would guess that opposite conclusions could be reached by tuning the algorithms differently -- is that a reasonable suspicion ?\n\nIt is argued that the cyclic nature of the algorithms gives a form of \"warm start\" that is beneficial for MCMC. My intuition dictate that this is only true of the modes of the posterior are reasonable close to each other; otherwise I do not see how this warm starting is helpful. I would appreciate learning more about why this intuition is apparently incorrect.\n\nMinor comments:\n* on page 4 it is stated that the proposed algorithm \"automatically\" provide the warm restarts -- but is it really automatic? Isn't this a priori determined by choice of parameters for the algorithm?\n\n* It would be good to use \\citet instead of \\cite at places, e.g. \"discussed in (Smith & Topin, 2017)\" should be \"discussed by Smith & Topin (2017)\". This would improve readability (which is generally very good).\n\n* For the empirical studies I think it would be good to report state-of-the-art results as well. I expect that the Bayesian nets still are subpar to non-Bayesian methods, and I think the paper should report this.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "HJlFucOe5S", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 article presents cyclical stochastic gradient MCMC for Bayesian deep learning for inference in posterior distributions of network weights of Bayesian NNs. The posteriors of Bayesian NN weights are highly multi-modal and present difficulty for standard stochastic gradient MCMC methods. The proposed cyclical version periodically warm start the SG-MCMC process such that it can explore the multimodal space more efficiently.\n\nThe proposed method as well as the empirical results intuitively make sense. The standard SG-MCMC basically has one longer stepsize schedule and is exploring the weight space more patiently, but only converges to one local mode. The cyclical SG-MCMC uses multiple shorter stepsize schedules, so each one is similar to a (stochastic) greedy search. Consequently, the cSG-MCMC can collect more diverse samples across the weight space, while the samples of SG-MCMC are more concentrated, but likely with better quality (as shown in Figure 3). \n\nPersonally I would like to see how Bayesian deep learning can be applied to real large-scale applications. Probabilistic inference is expensive; Bayesian model averaging is even more expensive. That's probably why recent literature focuses on variational inference or expectation propagation-based approaches. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel stochastic gradient Markov chain Monte Carlo method incorporating a cyclical step size schedule (cyclical SG-MCMC).  The authors argue that this step size schedule allows the sampler to cross modes (when the step size is large) and locally explore modes (when the step size is smaller).  SG-MCMC is a very promising method for Bayesian deep learning as it is both scalable and easily to incorporate into existing models.  However, the stochastic setting often leads to the sampler getting stuck in a local mode due to a requirement of a small step size (which itself is often due to leaving out the Metropolis-Hastings accept / reject step).   The cyclic learning rate intuitively helps the sampler escape local modes.  This property is demonstrated on synthetic problems in comparison to existing SG-MCMC baselines.  The authors demonstrate improved negative log likelihood on larger scale deep learning benchmarks, which is appreciated as the related literature often restricts experiments to small scale problems.  The reviewers all found the paper compelling and argued for acceptance and thus the recommendation is to accept.  Some questions remain for future work.  E.g. all experiments were performed using a very low temperature, which implies that the methods are not sampling from the true Bayesian posterior.  Why is such a low temperature needed for reasonable performance?  In any case a very nice paper.
Decision: Accept (Talk)