提出更稳健的Dikin走法，加速对凸体中对数凹分布的采样。
Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk
- 通过谱逼近障碍函数海森矩阵，设计改进型软阈值Dikin走法。
- 在多面体上采样混合时间降为 $\widetilde O(d^2 + dL^2R^2)$ 步，更快。
- 可推广至半定规划约束集，适用于高维结构化优化问题。
我们研究在包含于半径为 $R$ 的球内的凸体中，从 $d$ 维对数凹分布 $π(θ) \propto \exp(-f(θ))$ 中采样，其中 $f$ 是 $L$-利普希茨函数，且存在高效计算的自协调障碍函数，并以 $w$-warm 初值开始。本文提出一种鲁棒采样框架，在每一步中计算障碍函数的海森矩阵的谱近似。对于由 $n$ 个超平面描述的多面体，使用 Lee-Sidford 障碍函数时，采样混合时间仅为 $\widetilde O((d^2 + dL^2R^2)\log(w/δ))$，每步代价为 $\widetilde O(nd^{ω-1})$，其中 $ω \approx 2.37$ 为快速矩阵乘法指数。相比 Mangoubi 与 Vishnoi 的工作，本方法实现更优混合时间，因可构造超越对数障碍的广义软阈值 Dikin 走法。进一步扩展至 $d$ 维谱体（spectrahedron），即由 $\{x\in \mathbb{R}^d: \sum_{i=1}^d x_i A_i \succeq C\}$ 定义的半定规划约束集，其中 $A_1,\ldots,A_d, C$ 为 $n\times n$ 实对称矩阵。设计的新走法混合时间为 $\widetilde O((nd + dL^2R^2)\log(w/δ))$，单步开销为 $\widetilde O(n^ω + n^2d^{3ω-5})$。相比 Narayanan 与 Rakhlin 的最优前人结果（混合时间 $\widetilde O((n^2d^3 + n^2dL^2R^2)\log(w/δ))$），本方法显著提升效率。
原文摘要 · Abstract (English)
We consider the problem of sampling from a $d$-dimensional log-concave distribution $π(θ) \propto \exp(-f(θ))$ for $L$-Lipschitz $f$, constrained to a convex body with an efficiently computable self-concordant barrier function, contained in a ball of radius $R$ with a $w$-warm start. We propose a \emph{robust} sampling framework that computes spectral approximations to the Hessian of the barrier functions in each iteration. We prove that for polytopes that are described by $n$ hyperplanes, sampling with the Lee-Sidford barrier function mixes within $\widetilde O((d^2+dL^2R^2)\log(w/δ))$ steps with a per step cost of $\widetilde O(nd^{ω-1})$, where $ω\approx 2.37$ is the fast matrix multiplication exponent. Compared to the prior work of Mangoubi and Vishnoi, our approach gives faster mixing time as we are able to design a generalized soft-threshold Dikin walk beyond log-barrier. We further extend our result to show how to sample from a $d$-dimensional spectrahedron, the constrained set of a semidefinite program, specified by the set $\{x\in \mathbb{R}^d: \sum_{i=1}^d x_i A_i \succeq C \}$ where $A_1,\ldots,A_d, C$ are $n\times n$ real symmetric matrices. We design a walk that mixes in $\widetilde O((nd+dL^2R^2)\log(w/δ))$ steps with a per iteration cost of $\widetilde O(n^ω+n^2d^{3ω-5})$. We improve the mixing time bound of prior best Dikin walk due to Narayanan and Rakhlin that mixes in $\widetilde O((n^2d^3+n^2dL^2R^2)\log(w/δ))$ steps.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。