Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning

• Bayesian methods account for uncertainty in neural-network weight space while balancing model complexity and data fitting.Source: §1 · p. 1
• MCMC methods remain largely unused for modern deep neural networks despite their earlier strong performance with smaller networks.Source: §1 · p. 1
• Existing SG-MCMC methods face bounded estimation error under decreasing stepsizes and practical demands for effective inference in short training times.Source: §1 · p. 1
• The proposed cSG-MCMC uses warm restarts to combine local-density characterization with exploration of multimodal posterior distributions.Source: §1 · p. 2
• cSG-MCMC is reported to provide better limited-time mixing than traditional SG-MCMC and approximate parallel MCMC at a fraction of its cost.Source: §1 · p. 2
• The paper proves non-asymptotic convergence and reports experiments on Bayesian neural networks, uncertainty estimation, and challenging datasets including ImageNet.Source: §1 · p. 2

• SG-MCMC methods use minibatches to approximate the full-data potential energy when evaluating all datapoints is too expensive.Source: §2 · p. 3

SGLD & SGHMC

• SGLD updates posterior samples with stochastic gradients and Gaussian noise controlled by the stepsize.Source: §2 · p. 3
• SGHMC adds an auxiliary momentum variable and friction term to improve mixing while counteracting minibatch noise.Source: §2 · p. 3

• Asymptotic consistency requires decreasing stepsizes satisfying the stated summability conditions.Source: §2 · p. 3
• A typical schedule is α_k = a(b + k)^−γ with γ ∈ (0.5, 1] and positive constants a and b.Source: §2 · p. 3

• cSG-MCMC consists of exploration and sampling stages repeated across cycles.Source: §3 · p. 3
• The cyclical schedule starts each period with a large stepsize for aggressive exploration, then decreases it to examine local posterior regions.Source: §3 · p. 3
• Each new cycle restarts with a large stepsize, encouraging escape from the current mode and discovery of another posterior region.Source: §3 · p. 3, §3.2 · p. 4

3.1 EXPLORATION

• The method avoids collecting samples at overly large stepsizes because minibatch noise can distort the stationary distribution and make stochastic MH correction costly.Source: §3.1 · p. 4
• Exploration uses optimization-like behavior, while sampling begins at T = 1 when the cycle enters its later phase.Source: §3.1 · p. 4, §3.2 · p. 4

• The schedule is presented as combining large-step perturbation, faster within-cycle decay, and optimization’s super-convergence advantage.Source: §3.2 · p. 4

3.2 SAMPLING

• Compared with parallel MCMC, cSG-MCMC uses one training pass and has the cost of a single chain while estimating different posterior regions across cycles.Source: §3.2 · p. 5
• Repeated cycles collect samples from multiple modes, with a separate scheme provided for combining them during testing.Source: §3.2 · p. 5

Convergence analysis

• The analysis studies cSG-MCMC convergence through both test-function averages and Wasserstein distance.These provide complementary views of convergence behavior.Source: §4 · p. 5

Weak convergence

• For cSGLD, Theorem 1 bounds the bias and MSE of posterior-average estimates for smooth test functions.The estimates use generated samples to approximate the posterior average.Source: §4 · p. 5

Convergence under the Wasserstein distance

• The 2-Wasserstein analysis compares the algorithm’s sample distribution µK with the stationary distribution ν∞, which matches the target distribution.The Wasserstein distance is defined using joint distributions whose marginals are the compared distributions.Source: §4 · p. 5
• Theorem 2 provides a convergence bound for cSGLD with a cyclical stepsize sequence at iterations satisfying K mod M = 0.The bound uses constants independent of the stepsizes.Source: §4 · p. 6

Theoretical interpretation

• Under α0 = O(K^-β) for every β > 1, the analysis gives a stated specialized Wasserstein bound.The paper notes that the overall dependency on K has the same order as standard SGLD.Source: §4 · p. 6
• The convergence bound separates exact-process convergence to stationarity from numerical discretization error.The first term concerns convergence of the exact solution, while the second concerns the gap between the algorithm and the discretized process.Source: §4 · p. 6

Synthetic Multimodal Data

• cSGLD fully explored all 25 Gaussian modes, whereas traditional SGLD discovered only 4 using 200k samples.The cyclical schedule uses large steps to discover modes and small steps to characterize local modes.Source: Figure 2 · p. 6, §5.1 · p. 6

Bayesian Neural Networks

• cSG-MCMC significantly outperformed Snapshot ensembles and traditional SG-MCMC on image-classification test error.The comparison attributes the advantage to combining diverse-mode coverage with fine-scale characterization within modes.Source: §5.2 · p. 7, §5.3 · p. 9
• On CIFAR-100, cSG-MCMC samples formed 4 weight-space clusters, while traditional SG-MCMC samples formed one cluster.Interpolation spikes between cSG-MCMC samples further indicate that neighboring samples come from different modes.Source: §5.2 · p. 8
• A cyclical single chain performed best with half the computational cost of the compared parallel decreasing-schedule setup.The experiments identify warm restarts from the cyclical schedule as important for this result.Source: §5.2 · p. 9
• At a fixed number of cycles, cSG-MCMC achieved substantially lower test errors than Snapshot optimization.Snapshot provides one minimum per cycle, whereas cSG-MCMC collects more samples to characterize each mode.Source: §5.2 · p. 9

Uncertainty Evaluation

• cSGHMC obtained the lowest ImageNet testing NLL, while cSGLD and cSGHMC assigned lower probability to low-entropy predictions on notMNIST.The notMNIST result is linked to exploring multiple modes that provide differing predictions for out-of-distribution inputs.Source: §5.2 · p. 9, §5.3 · p. 9

Discussion

• Cyclical SG-MCMC explores complex multimodal distributions and captures diverse hypotheses corresponding to different parameter settings.The paper also reports more efficient exploration of unimodal distributions and improved uncertainty estimation.Source: §6 · p. 10
• 50K samples let cSGLD explore significantly more of a 25-Gaussian mixture, whereas traditional SGLD discovered only one mode.The comparison uses the non-parallel setting shown in Figure 5.Source: Figure 5 · p. 14
• Mode coverage is measured by counting a mode when at least 100 samples fall within radius 0.25 of its center, using 10 runs.This metric is used to quantify multimodal exploration.Source: §A.1 · p. 14
• In Bayesian logistic regression, cSG-MCMC dramatically outperforms SG-MCMC overall, while SGHMC and cSGHMC match on the simple Heart posterior.Higher-dimensional Australian and German settings show significantly higher ESS for cSG-MCMC.Source: §A.2 · pp. 14–15
• The analysis treats ψ as a Poisson-equation solution functional and assumes bounded derivatives together with dissipativity and gradient-noise conditions.These assumptions support the theoretical convergence analysis.Source: §B.1 · p. 15, §B.2 · p. 15

Proof of Theorem 1

• The general decreasing-step-size analysis assumes positive decreasing stepsizes whose sum diverges and whose limiting behavior satisfies the stated convergence conditions.These are the assumptions used for the general SG-MCMC theorem.Source: C PROOF OF THEOREM 1 · pp. 15–16
• The proof bounds the bias and mean-squared error by decomposing discretization and stochastic-gradient contributions.The supplied derivation states that one higher-order gradient-noise term is omitted from big-O notation.Source: C PROOF OF THEOREM 1 · p. 16
• Assumption 4 is needed only for asymptotic unbiasedness; without it, the resulting algorithm can remain biased, as in cSGLD.The lemma still applies without Assumption 4.Source: C PROOF OF THEOREM 1 · p. 16
• The proof derives Theorem 1 as a special case of a general SG-MCMC lemma for a first-order cSGLD integrator.The specialization sets the integrator order to N = 1.Source: C PROOF OF THEOREM 1 · pp. 15–16

Proof of Theorem 2

• The proof introduces an SDE whose stationary distribution is p(θ|D), then relates the discrete iterates to continuous-time distributions.The argument uses µk and νt for the corresponding discrete and continuous distributions.Source: D PROOF OF THEOREM 2 · pp. 16–17
• The analysis assumes unbiased stochastic gradients, bounded update-noise behavior, independence of updates, and additional regularity conditions.These assumptions are stated alongside the continuous-time interpolation and SDE analysis.Source: D PROOF OF THEOREM 2 · pp. 17, 19
• The proof bounds intermediate relative-entropy and moment terms before applying transport and auxiliary lemmas to obtain the Wasserstein convergence result.The final bound follows after combining these components and using monotonicity in the accumulated stepsize.Source: D PROOF OF THEOREM 2 · pp. 17–19
• The final derivation concludes that the relevant Wasserstein bound decreases with K under the stated assumptions.This is the convergence behavior used in the theorem.Source: D PROOF OF THEOREM 2 · p. 20

Relation with SGLD

• Standard SGLD uses a polynomially decaying stepsize, while cSGLD uses cyclical schedules with repeated exploration and sampling phases.The theoretical comparison contrasts their accumulated diffusion time and approximation errors.Source: E RELATION WITH SGLD · p. 20
• When α0 ≥ h0, cSGLD accumulates diffusion time faster than standard SGLD and therefore incurs less error for K iterations.The paper states that this yields faster convergence for cSGLD.Source: E RELATION WITH SGLD · p. 24
• Increasing standard SGLD’s initial stepsize to match cSGLD’s speed makes its approximation error much larger, again favoring cSGLD.The comparison reports h0 scaling as O(α0K/log K) and a larger error term for standard SGLD.Source: E RELATION WITH SGLD · p. 24
• Cyclical SG-MCMC combines samples from cycle-specific sub-posteriors to estimate the full posterior expectation.Each cycle characterizes a region Θm, and cycle weights are estimated with a harmonic-mean method.Source: F COMBINING SAMPLES · p. 24
• The cycle-combination estimator can be adapted to overlapping regions by replacing them with disjoint sub-regions.This preserves the estimator when the original cycle regions overlap.Source: F COMBINING SAMPLES · pp. 24–25
• The analysis assumes unbiased noisy gradients and independence between fresh update noise and previous gradient-noise variables.These assumptions support the stochastic-gradient convergence derivation.Source: G THEORETICAL ANALYSIS UNDER CONVEX… · p. 25

Theorem statement

• The convergence bounds use positive constants M, m, δ, and σ defined in Assumption 5.The supplied theorem excerpt identifies these constants but does not reproduce the full bounds.Source: §G.1 · p. 25

Stepsize conditions

• Under the stated stepsize construction, αk varies from α0 toward αmin while remaining within the required stability range.The proof states 0 < αk < min(2/M, 1/m) for every k > 0.Source: §G.2 · p. 26

Convergence proof

• The convergence proof applies Lemma 2 after bounding the contraction factors ρk across the cyclical stepsize sequence.The proof first establishes 0 < ρk < 1, then uses the lemma to complete the convergence argument.Source: §G.2 · p. 26

Case analysis

• When mαmin + Mα0 ≤ 2, the proof bounds ρk by 1 − mαmin for every k > 0.This case substitutes the bound into the preceding convergence inequality.Source: §G.2 · p. 26
• When mαmin + Mα0 > 2, the proof instead bounds ρk by Mα0 − 1 for every k > 0.This alternative bound yields the second convergence case.Source: §G.2 · p. 26

Practical settings

• The training budget creates a trade-off between the number of cycles M and cycle length, with β tuned so sampling begins after reaching a good region.For CIFAR-10, the text gives a 50-epoch cycle as an example and reports β should be selected by cross-validation.Source: §I.1 · p. 26, §I.2 · p. 27

Motivation

• Tempering reflects the belief that model capacity is misspecified and shapes the posterior used for prediction.The paper frames tempering as combining model-capacity beliefs with data to form a predictive distribution.Source: J TEMPERING IN BAYESIAN NEURAL NETWORKS · p. 27

Experimental setup

• The main neural-network experiments use the prescribed pSGLD temperature T ≈ 0.0045, while the sensitivity study evaluates seven temperatures.The evaluated values are T ∈ [1, 0.5, 0.1, 0.05, 0.01, 0.005, 0].Source: J TEMPERING IN BAYESIAN NEURAL NETWORKS · p. 27

Results

• Sampling from the tempered posterior outperforms optimization in both NLL and accuracy.The paper interprets this as finding a better predictive distribution for overparameterized neural networks.Source: J TEMPERING IN BAYESIAN NEURAL NETWORKS · p. 27

Temperature sensitivity

• On CIFAR-10 with cSGLD, the best performance for both NLL and error is achieved at T = 0.1.Figure 6 reports NLL and error (%) as functions of temperature.Source: Figure 6 · p. 27
• On CIFAR-100 with cSGLD, the best performance for both NLL and error is achieved at T = 0.01.Figure 7 reports NLL and error (%) as functions of temperature.Source: Figure 7 · p. 28

Experimental setup

• The reported cSGLD and cSGHMC settings include M = 100 and β = 0.01 for the listed datasets.The passage gives separate initial-step parameters for the two cyclical samplers and dataset-specific settings.Source: §K.1 · p. 28

Hyperparameter settings

• For both cSG-MCMC and Snapshot, M = 4; cSG-MCMC uses β = 0.8.The passage also specifies α0N = 0.01 for cSGLD and 0.008 for cSGHMC.Source: §K.3 · p. 28