提出更快的高维对数凹分布采样冷启动方法，突破立方复杂度瓶颈。
Faster logconcave sampling from a cold start in high dimension
- 基于弱距离度量（如q-Rényi散度）实现更宽松的初始采样条件
- 首次实现近等向位置输入下的亚立方采样复杂度
- 适用于需要高效冷启动的高维概率采样场景
我们提出一种更快的算法，用于生成任意对数凹密度的温暖初始样本，该密度由评估预言机给出，从而实现了在（近）等向位置输入下的首个亚立方采样算法。以往长期工作在维度上至少存在线性温暖启动代价，导致无法突破立方复杂度壁垒，即使对于凸体上的均匀采样这一特例也是如此。我们的改进依赖于两个独立具有重要意义的关键要素：(1) 我们展示了如何在较弱的距离度量下（特别是q-Rényi散度，其中q=~O(1)）进行采样，而以往分析要求严格的∞-Rényi散度（除击中运行法外，其已知混合时间更高）。这是自Lovász和Simonovits（1991）以来首次在所需温暖度量上的改进。(2) 我们改进并推广了Lee和Vempala（2018）的对数-索博列夫不等式，该不等式最初针对等向对数凹分布，以支撑集直径为基准；现在推广至一般对数凹分布，以支撑集直径与协方差矩阵最大特征值的几何平均为基准。
原文摘要 · Abstract (English)
We present a faster algorithm to generate a warm start for sampling an arbitrary logconcave density specified by an evaluation oracle, leading to the first sub-cubic sampling algorithms for inputs in (near-)isotropic position. A long line of prior work incurred a warm-start penalty of at least linear in the dimension, hitting a cubic barrier, even for the special case of uniform sampling from convex bodies. Our improvement relies on two key ingredients of independent interest. (1) We show how to sample given a warm start in weaker notions of distance, in particular $q$-Rényi divergence for $q=\widetilde{\mathcal{O}}(1)$, whereas previous analyses required stringent $\infty$-Rényi divergence (with the exception of Hit-and-Run, whose known mixing time is higher). This marks the first improvement in the required warmness since Lovász and Simonovits (1991). (2) We refine and generalize the log-Sobolev inequality of Lee and Vempala (2018), originally established for isotropic logconcave distributions in terms of the diameter of the support, to logconcave distributions in terms of a geometric average of the support diameter and the largest eigenvalue of the covariance matrix.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。