Sampling Can Be Faster Than Optimization

Abstract

Optimization algorithms and Monte Carlo sampling algorithms have provided the computational foundations for the rapid growth in applications of statistical machine learning in recent years. There is, however, limited theoretical understanding of the relationships between these two kinds of methodology, and limited understanding of relative strengths and weaknesses. Moreover, existing results have been obtained primarily in the setting of convex functions (for optimization) and log-concave functions (for sampling). In this setting, where local properties determine global properties, optimization algorithms are unsurprisingly more efficient computationally than sampling algorithms. We instead examine a class of nonconvex objective functions that arise in mixture modeling and multi-stable systems. In this nonconvex setting, we find that the computational complexity of sampling algorithms scales linearly with the model dimension while that of optimization algorithms scales exponentially.

References in corpus (5)

• Non-convex Optimization for Machine Learning
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Local Maxima in the Likelihood of Gaussian Mixture Models: Structural Results and Algorithmic Consequences
• Is There an Analog of Nesterov Acceleration for MCMC?

Cited by in corpus (30)

• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Is There an Analog of Nesterov Acceleration for MCMC?
• AdaSwarm: Augmenting Gradient-Based optimizers in Deep Learning with Swarm Intelligence
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Active Importance Sampling for Variational Objectives Dominated by Rare Events: Consequences for Optimization and Generalization
• CoolMomentum: A Method for Stochastic Optimization by Langevin Dynamics with Simulated Annealing
• A one-stop function for gravitational-wave detection, identification and inference
• Online stochastic gradient descent on non-convex losses from high-dimensional inference
• On Quantum Speedups for Nonconvex Optimization via Quantum Tunneling Walks
• Prior normalization for certified likelihood-informed subspace detection of Bayesian inverse problems
• On polynomial-time computation of high-dimensional posterior measures by Langevin-type algorithms
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
• On stochastic mirror descent with interacting particles: convergence properties and variance reduction
• Data Augmentation for Bayesian Deep Learning
• On the Generalised Langevin Equation for Simulated Annealing
• Replica Exchange for Non-Convex Optimization
• On Thompson Sampling with Langevin Algorithms
• Constrained Minimum Energy Designs
• Fast Convergence for Langevin Diffusion with Manifold Structure
• On Computational Poisson Geometry II: Numerical Methods
• Stochastic gradient descent and fast relaxation to thermodynamic equilibrium: a stochastic control approach
• Differentiable Visual Computing
• Hessian-Free High-Resolution Nesterov Acceleration for Sampling
• Variational Transport: A Convergent Particle-BasedAlgorithm for Distributional Optimization
• On the cost of Bayesian posterior mean strategy for log-concave models
• A Decentralized Approach to Bayesian Learning
• Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective
• Distribution-Dependent Analysis of Gibbs-ERM Principle
• On Mixing Times of Metropolized Algorithm With Optimization Step (MAO) : A New Framework