Global Non-convex Optimization with Discretized Diffusions

Abstract

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 and that different diffusions are suitable for optimizing different classes of convex and non-convex functions. This allows us to design diffusions suitable for globally optimizing convex and non-convex functions not covered by the existing Langevin theory. Our non-asymptotic analysis delivers computable optimization and integration error bounds based on easily accessed properties of the objective and chosen diffusion. Central to our approach are new explicit Stein factor bounds on the solutions of Poisson equations. We complement these results with improved optimization guarantees for targets other than the standard Gibbs measure.

arXiv comment19 pages, NeurIPS 2018 camera ready version

References in corpus (7)

• On the Poisson equation and diffusion approximation 3
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• On the Convergence of Stochastic Gradient MCMC Algorithms with High-Order Integrators
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• Exponential Contraction in Wasserstein Distances for Diffusion Semigroups with Negative Curvature

Cited by in corpus (2)

• Some models are useful, but how do we know which ones? Towards a unified Bayesian model taxonomy
• Higher Order Generalization Error for First Order Discretization of Langevin Diffusion