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

We consider the problem of sampling from a log-concave distribution π(θ) ∝ e -f (θ) constrained to a polytope K := θ ∈ R d : Aθ ≤ b, where A ∈ R m×d and b ∈ R m . The fastest-known algorithm [25] 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. This result directly improves the runtime for applications that involve sampling from Gibbs distributions constrained to polytopes that arise in Bayesian statistics and private optimization.