Structured Logconcave Sampling with a Restricted Gaussian Oracle

Abstract

We give algorithms for sampling several structured logconcave families to high accuracy. We further develop a reduction framework, inspired by proximal point methods in convex optimization, which bootstraps samplers for regularized densities to improve dependences on problem conditioning. A key ingredient in our framework is the notion of a "restricted Gaussian oracle" (RGO) for $g:{\mathbb{R}}^d\to \mathbb{R}$, which is a sampler for distributions whose negative log-likelihood sums a quadratic and $g$. By combining our reduction framework with our new samplers, we obtain the following bounds for sampling structured distributions to total variation distance $\epsilon$. For composite densities $\exp (-f(x)-g(x))$, where $f$ has condition number $\kappa$ and convex (but possibly non-smooth) $g$ admits an RGO, we obtain a mixing time of $O(\kappa d{\log }^3\frac{\kappa d}{\epsilon })$, matching the state-of-the-art non-composite bound; no composite samplers with better mixing than general-purpose logconcave samplers were previously known. For logconcave finite sums $\exp (-F(x))$, where $F(x)=\frac{1}{n}{\sum }_{i\in [n]}{f}_i(x)$ has condition number $\kappa$, we give a sampler querying $\tilde{O}(n+\kappa \max (d,\sqrt{nd}))$ gradient oracles to $\{f_i{\}}_{i\in [n]}$; no high-accuracy samplers with nontrivial gradient query complexity were previously known. For densities with condition number $\kappa$, we give an algorithm obtaining mixing time $O(\kappa d{\log }^2\frac{\kappa d}{\epsilon })$, improving the prior state-of-the-art by a logarithmic factor with a significantly simpler analysis; we also show a zeroth-order algorithm attains the same query complexity.

arXiv comment58 pages. The results of Section 5 of this paper, as well as an empirical evaluation, appeared earlier as arXiv:2006.05976. This version fixes an error in the proof of Theorem 1, see Section 1.4

References in corpus (18)

• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• A Universal Catalyst for First-Order Optimization
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• The True Cost of Stochastic Gradient Langevin Dynamics
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• The Randomized Midpoint Method for Log-Concave Sampling
• Langevin Monte Carlo and JKO splitting
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions
• An Efficient Sampling Algorithm for Non-smooth Composite Potentials
• Proximal Langevin Algorithm: Rapid Convergence Under Isoperimetry
• Faster Convex Optimization: Simulated Annealing with an Efficient Universal Barrier
• A Convergence Analysis for A Class of Practical Variance-Reduction Stochastic Gradient MCMC
• Stochastic Proximal Langevin Algorithm: Potential Splitting and Nonasymptotic Rates
• On stochastic gradient Langevin dynamics with dependent data streams in the logconcave case
• Composite Logconcave Sampling with a Restricted Gaussian Oracle