# Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 19 Jun 2022.

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

- [Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm](https://mlsanity.com/paper/1507.05021/) (2015)
- [Analysis of Langevin Monte Carlo via convex optimization](https://mlsanity.com/paper/1802.09188/) (2018)
- [Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem](https://mlsanity.com/paper/1802.08089/) (2018)
- [Log-concave sampling: Metropolis-Hastings algorithms are fast](https://mlsanity.com/paper/1801.02309/) (2018)
- [On sampling from a log-concave density using kinetic Langevin diffusions](https://mlsanity.com/paper/1807.09382/) (2018)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [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)
- [Faster Differentially Private Samplers via R'enyi Divergence Analysis of Discretized Langevin MCMC](https://mlsanity.com/paper/2010.14658/) (2020)
- [The entropic barrier: a simple and optimal universal self-concordant barrier](https://mlsanity.com/paper/1412.1587/) (2014)
- [Solving Linear Programs with Sqrt(rank) Linear System Solves](https://mlsanity.com/paper/1910.08033/) (2019)
- [Sampling from Log-Concave Distributions with Infinity-Distance Guarantees](https://mlsanity.com/paper/2111.04089/) (2021)
- [Efficient Sampling from Time-Varying Log-Concave Distributions](https://mlsanity.com/paper/1309.5977/) (2013)
- [The Mixing Time of the Dikin Walk in a Polytope - A Simple Proof](https://mlsanity.com/paper/1508.01977/) (2015)
- [Sampling Matrices from Harish-Chandra-Itzykson-Zuber Densities with Applications to Quantum Inference and Differential Privacy](https://mlsanity.com/paper/2011.05417/) (2020)
- [Efficient sampling from the Bingham distribution](https://mlsanity.com/paper/2010.00137/) (2020)

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

- [Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers](https://mlsanity.com/paper/2409.04320/) (2024)

## Abstract (arXiv)

Given a Lipschitz or smooth convex function , f:K → ℝ for a bounded polytope K subseteq ℝd defined by m inequalities, we consider the problem of sampling from the log-concave distribution π(θ) propto e-f(θ) constrained to K. Interest in this problem derives from its applications to Bayesian inference and differentially private learning. Our main result is a generalization of the Dikin walk Markov chain to this setting that requires at most O((md + d L2 R2) × mdω-1) log(fracwδ)) arithmetic operations to sample from π within error δ>0 in the total variation distance from a w-warm start. Here L is the Lipschitz-constant of f, K is contained in a ball of radius R and contains a ball of smaller radius r, and ω is the matrix-multiplication constant. Our algorithm improves on the running time of prior works for a range of parameter settings important for the aforementioned learning applications. Technically, we depart from previous Dikin walks by adding a "soft-threshold" regularizer derived from the Lipschitz or smoothness properties of f to the log-barrier function for K that allows our version of the Dikin walk to propose updates that have a high Metropolis acceptance ratio for f, while at the same time remaining inside the polytope K.