Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities

Abstract

Sampling logconcave functions arising in statistics and machine learning has been a subject of intensive study. Recent developments include analyses for Langevin dynamics and Hamiltonian Monte Carlo (HMC). While both approaches have dimension-independent bounds for the underlying $continuous$ processes under sufficiently strong smoothness conditions, the resulting discrete algorithms have complexity and number of function evaluations growing with the dimension. Motivated by this problem, in this paper, we give a general algorithm for solving multivariate ordinary differential equations whose solution is close to the span of a known basis of functions (e.g., polynomials or piecewise polynomials). The resulting algorithm has polylogarithmic depth and essentially tight runtime - it is nearly linear in the size of the representation of the solution. We apply this to the sampling problem to obtain a nearly linear implementation of HMC for a broad class of smooth, strongly logconcave densities, with the number of iterations (parallel depth) and gradient evaluations being $polylogarithmic$ in the dimension (rather than polynomial as in previous work). This class includes the widely-used loss function for logistic regression with incoherent weight matrices and has been subject of much study recently. We also give a faster algorithm with $polylogarithmicdepth$ for the more general and standard class of strongly convex functions with Lipschitz gradient. These results are based on (1) an improved contraction bound for the exact HMC process and (2) logarithmic bounds on the degree of polynomials that approximate solutions of the differential equations arising in implementing HMC.

References in corpus (5)

• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC

Cited by in corpus (16)

• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• An Efficient Sampling Algorithm for Non-smooth Composite Potentials
• Logsmooth Gradient Concentration and Tighter Runtimes for Metropolized Hamiltonian Monte Carlo
• Truncated Log-concave Sampling with Reflective Hamiltonian Monte Carlo
• Complexity of zigzag sampling algorithm for strongly log-concave distributions
• Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature
• Composite Logconcave Sampling with a Restricted Gaussian Oracle
• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• Efficient Sampling from Feasible Sets of SDPs and Volume Approximation
• Unadjusted Hamiltonian MCMC with Stratified Monte Carlo Time Integration
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• Sampling for Bayesian Mixture Models: MCMC with Polynomial-Time Mixing