Global Non-convex Optimization with Discretized Diffusions

2018/10/29 by Murat A. Erdogdu, Lester Mackey, Erdogdu, Murat A. +3 · 2 citations
Computer Science · Mathematics · Medicine · #Advanced Neuroimaging Techniques and Applications #Computation (stat.CO) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1810.12361

openalex publication_date 2018/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

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

Cited by

• Restricted Spectral Gap Decomposition for Simulated Tempering Targeting Mixture Distributions
• Some models are useful, but how do we know which ones? Towards a unified Bayesian model taxonomy

Related

• Accelerating Convergence in Global Non-Convex Optimization with Reversible Diffusion
• Convergence Error Analysis of Reflected Gradient Langevin Dynamics for Globally Optimizing Non-Convex Constrained Problems
• Improved Bounds for Discretization of Langevin Diffusions: Near-Optimal Rates without Convexity
• Non-Convex Optimization via Non-Reversible Stochastic Gradient Langevin Dynamics
• Recent Theoretical Advances in Non-Convex Optimization