改进采样算法,让复杂分布采样更快更准。
Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis
- 用正则化迪金行走法处理截断对数凹分布采样。
- 混合时间从之前的O((m+κ)n)优化到O(m+κn),更快。
- 适合做贝叶斯推断中带指示变量的模型采样。
我们研究在多面体上截断的对数凹分布的采样问题,这源于带有指示变量的贝叶斯统计模型(如probit回归)中的计算挑战。基于内点法和均匀分布的迪金行走,分析了正则化迪金行走的混合时间。主要贡献有三:首先,对于条件数为κ、由m个线性约束定义在ℝⁿ上的对数凹且对数光滑分布,证明软阈值迪金行走从热初始化出发可在˜O((m+κ)n)次迭代内混合,优于以往要求多面体有界且依赖于有界区域半径的工作;同时引入使用Lewis权重近似John椭球的正则化迪金行走,其混合时间为˜O((n²·⁵+κn))。其次,将上述混合时间保证推广至具有有限协方差矩阵的弱对数凹分布。第三,超越最坏情况分析,发现当仅有少量约束与分布高概率质量区域相交时,软阈值迪金行走可显著加速,混合时间上限降至˜O(m+κn)。此外,讨论了正则化迪金行走的每步复杂度及热初始化生成方法,以促进实际应用。
原文摘要 · Abstract (English)
We study the problem of drawing samples from a logconcave distribution truncated on a polytope, motivated by computational challenges in Bayesian statistical models with indicator variables, such as probit regression. Building on interior point methods and the Dikin walk for sampling from uniform distributions, we analyze the mixing time of regularized Dikin walks. Our contributions are threefold. First, for a logconcave and log-smooth distribution with condition number $κ$, truncated on a polytope in $\mathbb{R}^n$ defined with $m$ linear constraints, we prove that the soft-threshold Dikin walk mixes in $\widetilde{O}((m+κ)n)$ iterations from a warm initialization. It improves upon prior work which required the polytope to be bounded and involved a bound dependent on the radius of the bounded region. Moreover, we introduce the regularized Dikin walk using Lewis weights for approximating the John ellipsoid. We show that it mixes in $\widetilde{O}((n^{2.5}+κn)$. Second, we extend the mixing time guarantees mentioned above to weakly log-concave distributions truncated on polytopes, provided that they have a finite covariance matrix. Third, going beyond worst-case mixing time analysis, we demonstrate that soft-threshold Dikin walk can mix significantly faster when only a limited number of constraints intersect the high-probability mass of the distribution, improving the $\widetilde{O}((m+κ)n)$ upper bound to $\widetilde{O}(m + κn)$. Additionally, per-iteration complexity of regularized Dikin walk and ways to generate a warm initialization are discussed to facilitate practical implementation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。