# Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 78 references that are in the map.
- First posted on arXiv 8 Oct 2024.

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

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1502.07645/) (2015)
- [The promises and pitfalls of Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/1811.10072/) (2018)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Sketching for Kronecker Product Regression and P-splines](https://mlsanity.com/paper/1712.09473/) (2017)
- [Optimal Sketching for Kronecker Product Regression and Low Rank Approximation](https://mlsanity.com/paper/1909.13384/) (2019)
- [A near-optimal algorithm for approximating the John Ellipsoid](https://mlsanity.com/paper/1905.11580/) (2019)
- [On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo](https://mlsanity.com/paper/1802.05431/) (2018)
- [Fast MCMC sampling algorithms on polytopes](https://mlsanity.com/paper/1710.08165/) (2017)
- [Solving Linear Programs with Sqrt(rank) Linear System Solves](https://mlsanity.com/paper/1910.08033/) (2019)
- [Stochastic Variance-Reduced Hamilton Monte Carlo Methods](https://mlsanity.com/paper/1802.04791/) (2018)
- [Langevin Monte Carlo: random coordinate descent and variance reduction](https://mlsanity.com/paper/2007.14209/) (2020)
- [Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy](https://mlsanity.com/paper/2310.14661/) (2023)
- [Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling](https://mlsanity.com/paper/2307.12943/) (2023)
- [Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers](https://mlsanity.com/paper/2409.04320/) (2024)

## 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)
- [A General Framework for Metropolis-Adjusted Dikin Walks: Dimension-Square Mixing on Polytopes and Log-Det Walks on Spectrahedra](https://mlsanity.com/paper/2608.25273/) (2026)

## Abstract (arXiv)

We consider the problem of sampling from a d-dimensional log-concave distribution π(θ) propto exp(-f(θ)) for L-Lipschitz f, constrained to a convex body with an efficiently computable self-concordant barrier function, contained in a ball of radius R with a w-warm start. We propose a robust sampling framework that computes spectral approximations to the Hessian of the barrier functions in each iteration. We prove that for polytopes that are described by n hyperplanes, sampling with the Lee-Sidford barrier function mixes within widetilde O((d2+dL2R2)log(w/δ)) steps with a per step cost of widetilde O(ndω-1), where ω≈ 2.37 is the fast matrix multiplication exponent. Compared to the prior work of Mangoubi and Vishnoi, our approach gives faster mixing time as we are able to design a generalized soft-threshold Dikin walk beyond log-barrier. We further extend our result to show how to sample from a d-dimensional spectrahedron, the constrained set of a semidefinite program, specified by the set x∈ ℝd: sumi=1d xi Ai succeq C  where A1,ldots,Ad, C are n× n real symmetric matrices. We design a walk that mixes in widetilde O((nd+dL2R2)log(w/δ)) steps with a per iteration cost of widetilde O(nω+n2d3ω-5). We improve the mixing time bound of prior best Dikin walk due to Narayanan and Rakhlin that mixes in widetilde O((n2d3+n2dL2R2)log(w/δ)) steps.