Structured Logconcave Sampling with a Restricted Gaussian Oracle
Structured Logconcave Sampling with a Restricted Gaussian Oracle
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Y. Lee;Ruoqi Shen;Kevin Tian
中科院分区：
文献类型：
--
作者：
Y. Lee;Ruoqi Shen;Kevin Tian
我们给出了若干结构化对数凹族的高精度采样算法。我们进一步开发了一个约简框架，受凸优化中的近点方法的启发，该框架为正则化密度引导采样器，以改善对问题条件的依赖。我们框架中的一个关键成分是$g: \mathbb{R}^d \rightarrow \mathbb{R}$的“受限高斯oracle”（RGO）概念，它是一个采样器，其负对数似然和一个二次和$g$的分布。通过将我们的约简框架与我们的新采样器相结合，我们得到了抽样结构化分布到总变异距离$\epsilon$的以下界限。对于复合密度$\exp(-f(x) - g(x))$，其中$f$具有条件数$\kappa$，并且凸（但可能是非光滑的）$g$允许RGO，我们得到混合时间$O(\kappa d \log^3\frac{\kappa d}{\epsilon})$，匹配最先进的非复合边界；没有复合采样器比通用对数凹采样器更好的混合以前是已知的。对于对数凹有限和$\exp(-F(x))$，其中$F(x) = \frac{1}{n}\sum_{i \in [n]} f_i(x)$有条件数$\kappa$，我们给出一个采样器查询$\widetilde{O}(n + \kappa\max(d, \sqrt{nd}))$梯度oracle到$\{f_i\}_{i \in [n]}$；在此之前，还没有发现具有非平凡梯度查询复杂度的高精度采样器。对于条件数为$\kappa$的密度，我们给出了一种获得混合时间$O(\kappa d \log^2\frac{\kappa d}{\epsilon})$的算法，该算法通过对数因子改善了先前的状态，并且分析简单得多；我们还展示了实现相同查询复杂度的零阶算法。
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 $\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 $\widetilde{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.