通过高效线性求解器加速多面体上对数凹分布的采样，显著降低计算成本。
Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers
- 利用矩阵变化缓慢的特性，复用前步计算信息加速矩阵求逆。
- 在保持采样步数不变的前提下，将每步复杂度降至与矩阵非零元数量相当。
- 采用随机泰勒级数估计器加速马尔可夫链接受步骤中的行列式计算。
我们研究在多面体 $K:=\{θ\in \mathbb{R}^d: Aθ\leq b\}$ 约束下，从对数凹分布 $π(θ) \propto e^{-f(θ)}$ 中采样的问题，其中 $A\in \mathbb{R}^{m\times d}$，$b \in \mathbb{R}^m$。当 $f$ 为 $O(1)$-Lipschitz 或 $O(1)$-smooth 时，现有最快算法需约 $O(md \times md^{ω-1})$ 次算术运算，其中 $md^{ω-1}$ 项源于每步需计算矩阵逆和行列式（$ω\approx 2.37$ 为矩阵乘法常数）。本文提出一种近似最优实现：每步复杂度约为 $A$ 的非零元个数，而采样步数不变。关键技术包括：1）证明 Dikin walk 中出现的矩阵变化缓慢；2）使用可利用历史信息的高效线性求解器加速矩阵求逆；3）通过基于随机泰勒级数的估计器加速马尔可夫链中梅特罗波利斯滤波步骤的行列式计算。
原文摘要 · Abstract (English)
We consider the problem of sampling from a log-concave distribution $π(θ) \propto e^{-f(θ)}$ constrained to a polytope $K:=\{θ\in \mathbb{R}^d: Aθ\leq b\}$, where $A\in \mathbb{R}^{m\times d}$ and $b \in \mathbb{R}^m$.The fastest-known algorithm \cite{mangoubi2022faster} for the setting when $f$ is $O(1)$-Lipschitz or $O(1)$-smooth runs in roughly $O(md \times md^{ω-1})$ arithmetic operations, where the $md^{ω-1}$ term arises because each Markov chain step requires computing a matrix inversion and determinant (here $ω\approx 2.37$ is the matrix multiplication constant). We present a nearly-optimal implementation of this Markov chain with per-step complexity which is roughly the number of non-zero entries of $A$ while the number of Markov chain steps remains the same. The key technical ingredients are 1) to show that the matrices that arise in this Dikin walk change slowly, 2) to deploy efficient linear solvers that can leverage this slow change to speed up matrix inversion by using information computed in previous steps, and 3) to speed up the computation of the determinantal term in the Metropolis filter step via a randomized Taylor series-based estimator.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。