Monte Carlo Seminar| Yuansi Chen| Regularized Dikin Walks for Sampling Truncated Logconcave Measures скачать в хорошем качестве

Monte Carlo Seminar| Yuansi Chen| Regularized Dikin Walks for Sampling Truncated Logconcave Measures

Brought to you by the Online Monte Carlo Seminar [sites.google.com/view/monte-carlo-seminar] Date: Tuesday, January 7, 2025 Speaker: Yuansi Chen (ETH Zurich) [Zoom Link] Title: Regularized Dikin Walks for Sampling Truncated Logconcave Measures, Mixed Isoperimetry and Beyond Worst-Case Analysis Abstract: 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)$.