Sampling can be faster than optimization
From MaRDI portal
Publication:5218499
Computational methods in Markov chains (60J22) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Numerical optimization and variational techniques (65K10) Computational aspects of data analysis and big data (68T09) Nonconvex programming, global optimization (90C26) Abstract computational complexity for mathematical programming problems (90C60)
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.
Recommendations
- Analysis of Langevin Monte Carlo via convex optimization
- Non-asymptotic guarantees for sampling by stochastic gradient descent
- Stochastic gradient Hamiltonian Monte Carlo for non-convex learning
- Convexization in Markov chain Monte Carlo
- Is there an analog of Nesterov acceleration for gradient-based MCMC?
Cited in
(39)- On computational Poisson geometry. II. Numerical methods
- Is there an analog of Nesterov acceleration for gradient-based MCMC?
- Constrained minimum energy designs
- On stochastic mirror descent with interacting particles: convergence properties and variance reduction
- Unadjusted Langevin algorithm for sampling a mixture of weakly smooth potentials
- Improved bounds for discretization of Langevin diffusions: near-optimal rates without convexity
- User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
- Sampling from the complement of a polyhedron: an MCMC algorithm for data augmentation
- High-order Langevin diffusion yields an accelerated MCMC algorithm
- Online stochastic gradient descent on non-convex losses from high-dimensional inference
- Stochastic gradient descent and fast relaxation to thermodynamic equilibrium: a stochastic control approach
- Prior normalization for certified likelihood-informed subspace detection of Bayesian inverse problems
- Replica exchange for non-convex optimization
- Convexization in Markov chain Monte Carlo
- From Optimization to Sampling Through Gradient Flows
- Global Optimization via Schrödinger–Föllmer Diffusion
- On the Generalized Langevin Equation for Simulated Annealing
- Data augmentation for Bayesian deep learning
- Swarm gradient dynamics for global optimization: the mean-field limit case
- Distributed event-triggered unadjusted Langevin algorithm for Bayesian learning
- Tail probability estimates of continuous-time simulated annealing processes
- Multi-index antithetic stochastic gradient algorithm
- An entropic approach for Hamiltonian Monte Carlo: the idealized case
- Two-layer neural network on infinite-dimensional data: global optimization guarantee in the mean-field regime
- Discrete-time simulated annealing: a convergence analysis via the Eyring-Kramers law
- Application of Langevin dynamics to advance the quantum natural gradient optimization algorithm
- Bayesian penalized empirical likelihood and Markov chain Monte Carlo sampling
- Neural triangular map for density estimation and sampling with application to Bayesian inference
- Unadjusted Langevin algorithm for non-convex weakly smooth potentials
- Novel matrix hit and run for sampling polytopes and its GPU implementation
- Tensor train based sampling algorithms for approximating regularized Wasserstein proximal operators
- On mixing rates for Bayesian CART
- Taming under isoperimetry
- Inexact Laplace approximation and the use of posterior mean in Bayesian inference
- Stochastic gradient Langevin dynamics for (weakly) log-concave posterior distributions
- On the variance reduction of Hamiltonian Monte Carlo via an approximation scheme
- Reflection coupling for unadjusted generalized Hamiltonian Monte Carlo in the nonconvex stochastic gradient case
- A deterministic sampling method via maximum mean discrepancy flow with adaptive kernel
- New trends in the stability of Sinkhorn semigroups
This page was built for publication: Sampling can be faster than optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5218499)
