In Bayesian inference, we often need to sample from a posterior distribution $p(\theta | x) \propto \exp(-U(\theta))$, where $U(\theta)$ is a potential energy function. If $U(\theta)$ is convex (meaning the distribution is log-concave), sampling is relatively straightforward—it behaves much like convex optimization with added noise. However, modern machine learning, particularly deep learning, presents us with "non-convex" landscapes: distributions with multiple peaks, flat valleys, and complex geometries.
Recent research has focused on extending the theoretical and practical reach of sampling algorithms into these non-convex territories, moving beyond the restrictive assumption of log-concavity.
The Langevin Foundation and Its Limits
The workhorse of high-dimensional sampling is the Langevin Monte Carlo (LMC) algorithm and its stochastic variant, Stochastic Gradient Langevin Dynamics (SGLD). At its core, LMC is a gradient descent step followed by the injection of Gaussian noise. This noise prevents the algorithm from simply collapsing into a local minimum, allowing it to explore the probability landscape.
While SGLD is popular for "big data" because it uses mini-batches, Tigran Nagapetyan, Sebastian J. Vollmer, and colleagues pointed out in The True Cost of Stochastic Gradient Langevin Dynamics that standard subsampling doesn't actually reduce the total computational cost for a fixed accuracy. To make high-accuracy inference truly scalable, researchers have turned to variance reduction.
Accelerating with Momentum and Multilevels
To speed up convergence, researchers have borrowed two key ideas from the optimization world: momentum and multilevel schemes.
- Momentum (Underdamped Langevin): By introducing a "velocity" term, Underdamped Langevin Monte Carlo (ULMC) can traverse the landscape more efficiently. Matthew Zhang and Murat A. Erdogdu showed in Improved Discretization Analysis for Underdamped Langevin Monte Carlo that ULMC achieves superior dimension dependence ($d^{1/2}$) compared to standard Langevin methods, even without traditional "Hessian smoothness" assumptions.
- Multilevel Schemes: Michael B. Giles and Sebastian J. Vollmer introduced Multilevel SGLD (ML-SGLD) in Multilevel Monte Carlo for Scalable Bayesian Computations. This approach couples simulations at different step sizes to reduce variance, effectively closing the efficiency gap between stochastic methods and classic MCMC.
Variance Reduction for Big Data
When working with massive datasets, the noise from mini-batches can overwhelm the sampling signal. To combat this, researchers have integrated variance-reduction techniques like SVRG and SAGA into Langevin dynamics. Difan Zou and Quanquan Gu demonstrated in Stochastic Variance-Reduced Hamilton Monte Carlo Methods that reusing gradient information allows for significantly faster convergence in large-scale settings. Similarly, Chao Zhang proposed Aggregated Gradient Langevin Dynamics (AGLD) in Aggregated Gradient Langevin Dynamics to make MCMC practical for datasets that cannot fit in memory.
From Particles to Populations
A different philosophy for sampling involves using a "population" of particles that interact to map out the distribution. Stein Variational Gradient Descent (SVGD) is the primary example, but its theoretical guarantees were historically limited to log-concave targets.
Adil Salim and Peter Richtárik provided a breakthrough in A Convergence Theory for SVGD in the Population Limit under Talagrand's Inequality T1, offering the first complexity bounds for SVGD on non-logconcave distributions. To prevent the "particle collapse" often seen in deterministic methods, Changyou Chen and Jianyi Zhang introduced Stochastic Particle-Optimization Sampling (SPOS) in Stochastic Particle-Optimization Sampling and the Non-Asymptotic Convergence Theory, which uses controlled noise to improve exploration of multi-modal landscapes.
Breaking the Log-Concavity Barrier
The most significant theoretical shift in this field is the move away from strong log-concavity toward weaker functional inequalities like Poincaré and Log-Sobolev Inequalities (LSI). These inequalities allow for distributions that are "heavier-tailed" or have multiple modes, which are common in real-world data.
Rong Ge and Andrej Risteski provided some of the first provable guarantees for multi-modal sampling in Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo. By using Simulated Tempering, they showed how to transition between different "temperatures" of a distribution to jump between modes that would otherwise be isolated by high-energy barriers.
Furthermore, Murat A. Erdogdu and Matthew Zhang established rigorous convergence guarantees for LMC under these broader conditions in Analysis of Langevin Monte Carlo from Poincaré to Log-Sobolev, proving that these algorithms remain robust even when the underlying potential function is not convex.