# Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 37 references that are in the map.
- First posted on arXiv 6 Sep 2024.

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

- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Sampling from a log-concave distribution with compact support with proximal Langevin Monte Carlo](https://mlsanity.com/paper/1705.08964/) (2017)
- [Convergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computation](https://mlsanity.com/paper/1710.06261/) (2017)
- [Efficient Inverse Maintenance and Faster Algorithms for Linear Programming](https://mlsanity.com/paper/1503.01752/) (2015)
- [Strong Self-Concordance and Sampling](https://mlsanity.com/paper/1911.05656/) (2019)
- [Efficient Sampling from Time-Varying Log-Concave Distributions](https://mlsanity.com/paper/1309.5977/) (2013)
- [Privately Solving Linear Programs](https://mlsanity.com/paper/1402.3631/) (2014)
- [Private Optimization Without Constraint Violations](https://mlsanity.com/paper/2007.01181/) (2020)
- [Singular values of Gaussian matrices and permanent estimators](https://mlsanity.com/paper/1301.6268/) (2013)
- [Approximating permanents and hafnians](https://mlsanity.com/paper/1601.07518/) (2016)
- [A quick estimate for the volume of a polyhedron](https://mlsanity.com/paper/2112.06322/) (2021)
- [Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk](https://mlsanity.com/paper/2206.09384/) (2022)

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

- [Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk](https://mlsanity.com/paper/2410.05700/) (2024)

## Abstract (arXiv)

We consider the problem of sampling from a log-concave distribution π(θ) propto e-f(θ) constrained to a polytope K:=θ ∈ ℝd: Aθ ≤ b, where A∈ ℝm× d and b ∈ ℝm.The fastest-known algorithm citemangoubi2022faster for the setting when f is O(1)-Lipschitz or O(1)-smooth runs in roughly O(md × mdω -1) arithmetic operations, where the mdω -1 term arises because each Markov chain step requires computing a matrix inversion and determinant (here ω ≈ 2.37 is the matrix multiplication constant). We present a nearly-optimal implementation of this Markov chain with per-step complexity which is roughly the number of non-zero entries of A while the number of Markov chain steps remains the same. The key technical ingredients are 1) to show that the matrices that arise in this Dikin walk change slowly, 2) to deploy efficient linear solvers that can leverage this slow change to speed up matrix inversion by using information computed in previous steps, and 3) to speed up the computation of the determinantal term in the Metropolis filter step via a randomized Taylor series-based estimator.