用带亚指数尾部的随机梯度实现高精度对数凹采样
High-accuracy log-concave sampling with stochastic queries
- 基于亚指数尾部随机梯度设计高效采样算法
- 迭代复杂度仅需poly(log(1/δ))，远优于优化问题的poly(1/δ)
- 适用于对精度要求高的采样任务，尤其适合低方差场景
我们证明，使用具有亚指数尾部的随机梯度，可实现对数凹采样的高精度保证——迭代与查询复杂度仅随poly(log(1/δ))增长，其中δ为期望精度。这与凸优化形成显著分离：即使在梯度中加入高斯噪声，查询复杂度也需poly(1/δ)。我们还通过信息论论证表明，轻尾随机梯度是实现高精度的必要条件；例如，在有界方差情况下，最小最大最优查询复杂度为Θ(1/δ)。该框架还推广至随机零阶（函数值）查询，并给出了有限和势能采样的改进复杂度结果。
原文摘要 · Abstract (English)
We show that high-accuracy guarantees for log-concave sampling -- that is, iteration and query complexities which scale as $\mathrm{poly}\log(1/δ)$, where $δ$ is the desired target accuracy -- are achievable using stochastic gradients with subexponential tails. Notably, this exhibits a separation with the problem of convex optimization, where stochasticity (even additive Gaussian noise) in the gradient oracle incurs $\mathrm{poly}(1/δ)$ queries. We also give an information-theoretic argument that light-tailed stochastic gradients are necessary for high accuracy: for example, in the bounded variance case, we show that the minimax-optimal query complexity scales as $Θ(1/δ)$. Our framework also provides similar high accuracy guarantees under stochastic zeroth order (value) queries, and an improved complexity result for sampling from finite-sum potentials.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。