Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case AnalysisOberseminar Stochastics

by Prof. Yuansi Chen (ETH Zürich)

Thursday May 8, 2025, 4:30 PM → 5:30 PM Europe/Berlin

Endenicher Allee 60/1-016 - Lipschitzsaal (Mathezentrum)

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. For a logconcave and log-smooth distribution with condition number $\kappa$, truncated on a polytope in $R^n$ defined with $m$ linear constraints, we prove that the soft-threshold Dikin walk mixes in $O((m+\kappa)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. Going beyond worst-case mixing time analysis, we demonstrate that the 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 $O((m+\kappa)n)$ upper bound to $O(m + \kappa n)$.

 

arXiv link: https://arxiv.org/abs/2412.11303