REVIEW 10 cited by
Sharp convergence rates for Langevin dynamics in the nonconvex setting
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
We study the problem of sampling from a distribution $p^*(x) \propto \exp\left(-U(x)\right)$, where the function $U$ is $L$-smooth everywhere and $m$-strongly convex outside a ball of radius $R$, but potentially nonconvex inside this ball. We study both overdamped and underdamped Langevin MCMC and establish upper bounds on the number of steps required to obtain a sample from a distribution that is within $\epsilon$ of $p^*$ in $1$-Wasserstein distance. For the first-order method (overdamped Langevin MCMC), the iteration complexity is $\tilde{\mathcal{O}}\left(e^{cLR^2}d/\epsilon^2\right)$, where $d$ is the dimension of the underlying space. For the second-order method (underdamped Langevin MCMC), the iteration complexity is $\tilde{\mathcal{O}}\left(e^{cLR^2}\sqrt{d}/\epsilon\right)$ for an explicit positive constant $c$. Surprisingly, the iteration complexity for both these algorithms is only polynomial in the dimension $d$ and the target accuracy $\epsilon$. It is exponential, however, in the problem parameter $LR^2$, which is a measure of non-log-concavity of the target distribution.
Forward citations
Cited by 10 Pith papers
-
Provable Quantum Speedups for Reaction-Rate Estimation in High-Dimensional Fokker-Planck Dynamics
A quantum algorithm estimates Fokker-Planck reaction rates with sublinear-time, polynomial-in-particle-number cost, giving an exponential-in-particle-number separation from the sharpest classical worst-case Langevin bounds.
-
High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
A third-order Langevin MCMC algorithm is proven to sample from smooth log-concave distributions in O(d^(1/4)/epsilon^(1/2)) iterations for generalized linear model potentials, improving on the earlier d^(1/3) barrier.
-
Mirror Langevin diffusions: Convergence rates and Markov chain approximations
Under simple growth conditions on the potential and mirror map, Mirror Langevin diffusions satisfy Poincaré or log-Sobolev inequalities, and a new exactly-stationary Gibbs sampler converges weakly to the diffusion and...
-
Generalization of Gibbs and Langevin Monte Carlo Algorithms in the Interpolation Regime
New PAC-Bayes bounds for the Gibbs posterior remain non-vacuous in the interpolation regime and can be approximated by Langevin Monte Carlo, but the tight experimental numbers rely on an unproved random-label calibrat...
-
Multimodal sampling via Schr\"odinger-F\"ollmer samplers with temperatures
Euler-discretized Schrödinger–Föllmer samplers with a temperature parameter provably converge at order O(h) in L2-Wasserstein distance, and high temperatures markedly improve multimodal sampling in experiments.
-
An explicit splitting SAV scheme for the kinetic Langevin dynamics
An explicit SSAV discretization of kinetic Langevin dynamics achieves order-one strong and weak convergence with error constants polynomial in time, even for superlinear-gradient potentials.
-
Regime-Switching Langevin Monte Carlo Algorithms
Regime-switching LMC and KLMC variants inherit Gibbs invariance and get W2 convergence bounds; the headline FRS-KLMC O(1/sqrt(epsilon)) complexity is not supported by the given proof.
-
High-Order Langevin Monte Carlo Algorithms
A higher-order Langevin Monte Carlo algorithm family is proposed with Wasserstein mixing time improving in the dynamics order, under a strong Condition H2 that the abstract does not disclose.
-
kTULA: A Langevin sampling algorithm with improved KL bounds under super-linear log-gradients
kTULA achieves a non-asymptotic KL convergence of order lambda^(2-epsilon) for non-log-concave targets with super-linear log-gradients under a Log-Sobolev inequality, improving prior order-lambda KL bounds.
-
Tamed Stochastic Gradient Hamiltonian Monte Carlo
tSGHMC provably samples from strongly convex targets with superlinear, discontinuous stochastic gradients at a λ^{1/4} Wasserstein-2 rate.
Discussion (0). Continue with ORCID to comment.