Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexity
We present an improved analysis of the Euler-Maruyama discretization of the Langevin diffusion. Our analysis does not require global contractivity, and yields polynomial dependence on the time horizon. Compared to existing approaches, we make an additional smoothness assumption, and improve the existing rate from $O(\eta)$ to $O(\eta^2)$ in terms of the KL divergence. This result matches the correct order for numerical SDEs, without suffering from exponential time dependence. When applied to algorithms for sampling and learning, this result simultaneously improves all those methods based on Dalayan's approach.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Global Non-convex Optimization with Discretized Diffusions
An Euler discretization of the Langevin diffusion is known to converge to the global minimizers of certain convex and non-convex optimization problems. We show that this property holds for any suitably smooth diffusion a…
Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincaré Inequality
Langevin diffusions are rapidly convergent under appropriate functional inequality assumptions. Hence, it is natural to expect that with additional smoothness conditions to handle the discretization errors, their discret…
Stochastic Zeroth-order Discretizations of Langevin Diffusions for Bayesian Inference
Discretizations of Langevin diffusions provide a powerful method for sampling and Bayesian inference. However, such discretizations require evaluation of the gradient of the potential function. In several real-world scen…
Bayesian InferenceStochastic OptimizationVariable SelectionOn sampling from a log-concave density using kinetic Langevin diffusions
Langevin diffusion processes and their discretizations are often used for sampling from a target density. The most convenient framework for assessing the quality of such a sampling scheme corresponds to smooth and strong…
Wasserstein Control of Mirror Langevin Monte Carlo
Discretized Langevin diffusions are efficient Monte Carlo methods for sampling from high dimensional target densities that are log-Lipschitz-smooth and (strongly) log-concave. In particular, the Euclidean Langevin Monte …