论文标题
强烈的对数凸线分布的曲折采样算法的复杂性
Complexity of zigzag sampling algorithm for strongly log-concave distributions
论文作者
论文摘要
我们研究了曲折采样算法的计算复杂性，以实现强烈的对数符合分布。 Zigzag过程的优点是不需要时间离散以实施，并且每个提出的弹跳事件仅需要对电势的部分导数进行评估，而其收敛速率则独立于维度。使用这些属性，我们证明了曲折采样算法在卡方发散中达到$ \ varepsilon $错误，计算成本等于$ \ bigl（κ^2） d^\ frac {1} {2}（\ log \ frac {1} {\ varepsilon}） $ D $是尺寸。
We study the computational complexity of zigzag sampling algorithm for strongly log-concave distributions. The zigzag process has the advantage of not requiring time discretization for implementation, and that each proposed bouncing event requires only one evaluation of partial derivative of the potential, while its convergence rate is dimension independent. Using these properties, we prove that the zigzag sampling algorithm achieves $\varepsilon$ error in chi-square divergence with a computational cost equivalent to $O\bigl(κ^2 d^\frac{1}{2}(\log\frac{1}{\varepsilon})^{\frac{3}{2}}\bigr)$ gradient evaluations in the regime $κ\ll \frac{d}{\log d}$ under a warm start assumption, where $κ$ is the condition number and $d$ is the dimension.
