Structured Logconcave Sampling with a Restricted Gaussian Oracle

MaRDI QIDQ6350708arXivFDO

Authors Yin Tat Lee, Ruoqi Shen, Kevin Tian

Publication date 6 October 2020

Published in arXiv

arXiv classification

cs.DScs.LGmath.OCstat.COstat.ML

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}ightarrowmathbbR$, 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(kappadlo{g}^{3}frackappadepsilon)$, 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)=frac1nsu{m}_{iin[n]}{f}_i(x)$ has condition number $kappa$, we give a sampler querying $widetildeO(n+kappamax(d,sqrtnd))$ gradient oracles to ${f_i}_{iin[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(kappadlo{g}^{2}frackappadepsilon)$, 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.

Cited in

(1)

• Exact simulation of diffusions and improved algorithms for log-concave sampling

This page was built for publication: Structured Logconcave Sampling with a Restricted Gaussian Oracle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6350708)