论文标题
结构化的logconcave采样，带有受限的高斯甲骨文
Structured Logconcave Sampling with a Restricted Gaussian Oracle
论文作者
论文摘要
我们提供了用于对几个结构化logconcave家族进行采样的算法。我们进一步开发了一个还原框架，灵感来自凸优化中的近端方法，该方法为正则密度启动采样器，以改善对问题条件的依赖。我们框架中的一个关键要素是$ g：\ mathbb {r}^d \ rightarrow \ mathbb {r} $的“受限高斯甲骨文”（rgo）的概念，它是用于分布的样本，其负log-logikelihoodyhienyhienhoods of a fim-logikeLihoods of a fim-logikelihoods of a figratic sups a fipikratic sups a fipigratic and a fiepigratic and a figeDratic和$ g $。通过将还原框架与新的采样器相结合，我们获得了以下界限，以采样结构化分布到总变化距离$ε$。对于复合密度$ \ exp（-f（x） - g（x））$，其中$ f $的条件数字$κ$和convex和convex（但可能是非平滑的）$ g $允许RGO，我们获得了$ o（κD\ log^3 \ frac^\ frac {κD}ε）$的混合时间，与compitient unnon-compoitt fort the-bild-ford-and-Art-Art forn dy-bild-Art fort dy-Art fort dy-Art fort dy-Art;先前已知，没有比通用logconcave采样器更好混合的复合采样器。对于logconcave有限总和$ \ exp（-f（x））$，其中$ f（x）= \ frac {1} {n} {n} \ sum_ {i \ in [n]} f_i（x）$具有条件号$κ$ \ sqrt {nd}））$渐变oracles to $ \ {f_i \} _ {i \ in [n]} $;先前没有具有非平凡梯度查询复杂性的高临界样本。对于条件数$κ$的密度，我们给出了一种算法，以获得混合时间$ o（κD\ log^2 \ frac {κD}ε）$，通过对数因子进行了更简单的分析，从而改善了对数因子的先前最新因素；我们还显示一个零阶算法达到相同的查询复杂性。
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 \rightarrow \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 $ε$. For composite densities $\exp(-f(x) - g(x))$, where $f$ has condition number $κ$ and convex (but possibly non-smooth) $g$ admits an RGO, we obtain a mixing time of $O(κd \log^3\frac{κd}ε)$, 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 $κ$, we give a sampler querying $\widetilde{O}(n + κ\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 $κ$, we give an algorithm obtaining mixing time $O(κd \log^2\frac{κd}ε)$, 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.
