# Strong Self-Concordance and Sampling

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2019.

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

- [The Mirror Langevin Algorithm Converges with Vanishing Bias](https://mlsanity.com/paper/2109.12077/) (2021)
- [When does Metropolized Hamiltonian Monte Carlo provably outperform Metropolis-adjusted Langevin algorithm?](https://mlsanity.com/paper/2304.04724/) (2023)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators](https://mlsanity.com/paper/2210.07219/) (2022)
- [Sampling with Barriers: Faster Mixing via Lewis Weights](https://mlsanity.com/paper/2303.00480/) (2023)
- [Tukey Depth Mechanisms for Practical Private Mean Estimation](https://mlsanity.com/paper/2502.18698/) (2025)
- [Beyond the d2.5-mixing bound for Dikin walks on polytopes](https://mlsanity.com/paper/2607.13943/) (2026)
- [Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers](https://mlsanity.com/paper/2409.04320/) (2024)
- [PolytopeWalk: Sparse MCMC Sampling over Polytopes](https://mlsanity.com/paper/2412.06629/) (2024)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)
- [On two proofs of d2 mixing of weighted Dikin walks](https://mlsanity.com/paper/2608.28566/) (2026)

## Abstract (arXiv)

Motivated by the Dikin walk, we develop aspects of an interior-point theory for sampling in high dimension. Specifically, we introduce a symmetric parameter and the notion of strong self-concordance. These properties imply that the corresponding Dikin walk mixes in tildeO(nbarnu) steps from a warm start in a convex body in ℝn using a strongly self-concordant barrier with symmetric self-concordance parameter barnu. For many natural barriers, barnu is roughly bounded by nu, the standard self-concordance parameter. We show that this property and strong self-concordance hold for the Lee-Sidford barrier. As a consequence, we obtain the first walk to mix in tildeO(n2) steps for an arbitrary polytope in ℝn. Strong self-concordance for other barriers leads to an interesting (and unexpected) connection -- for the universal and entropic barriers, it is implied by the KLS conjecture.