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

arXiv: https://arxiv.org/abs/2412.11303 · HTML: https://mlsanity.com/paper/2412.11303/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 70 references that are in the map.
- First posted on arXiv 15 Dec 2024.

## Builds on (most cited first, 4 of 4)

- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [Solving Linear Programs with Sqrt(rank) Linear System Solves](https://mlsanity.com/paper/1910.08033/) (2019)
- [Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing](https://mlsanity.com/paper/1612.01507/) (2016)
- [A Slightly Improved Bound for the KLS Constant](https://mlsanity.com/paper/2208.11644/) (2022)

## Built on by (most cited first, 2 of 2)

- [Beyond the d2.5-mixing bound for Dikin walks on polytopes](https://mlsanity.com/paper/2607.13943/) (2026)
- [On two proofs of d2 mixing of weighted Dikin walks](https://mlsanity.com/paper/2608.28566/) (2026)

## Abstract (arXiv)

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 kappa, truncated on a polytope in ℝn defined with m linear constraints, we prove that the soft-threshold Dikin walk mixes in widetildeO((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. Moreover, we introduce the regularized Dikin walk using Lewis weights for approximating the John ellipsoid. We show that it mixes in widetildeO((n2.5+kappa 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 widetildeO((m+kappa)n) upper bound to widetildeO(m + kappa n). Additionally, per-iteration complexity of regularized Dikin walk and ways to generate a warm initialization are discussed to facilitate practical implementation.