Faster Sampling from Log-Concave Distributions over Polytopes via a Soft-Threshold Dikin Walk
We consider the problem of sampling from a $d$-dimensional log-concave
distribution $\pi(\theta) \propto e^{-f(\theta)}$ constrained to a polytope $K$
defined by $m$ inequalities. Our main result is a "soft-threshold'' variant of
the Dikin walk Markov chain that requires at most $O((md + d L^2 R^2) \times
md^{\omega-1}) \log(\frac{w}{\delta}))$ arithmetic operations to sample from
$\pi$ within error $\delta>0$ in the total variation distance from a $w$-warm
start, where $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 $\omega$ is the
matrix-multiplication constant. When a warm start is not available, it implies
an improvement of $\tilde{O}(d^{3.5-\omega})$ arithmetic operations on the
previous best bound for sampling from $\pi$ within total variation error
$\delta$, which was obtained with the hit-and-run algorithm, in the setting
where $K$ is a polytope given by $m=O(d)$ inequalities and $LR = O(\sqrt{d})$.
When a warm start is available, our algorithm improves by a factor of $d^2$
arithmetic operations on the best previous bound in this setting, which was
obtained for a different version of the Dikin walk algorithm. Plugging our
Dikin walk Markov chain into the post-processing algorithm of Mangoubi and
Vishnoi (2021), we achieve further improvements in the dependence of the
running time for the problem of generating samples from $\pi$ with infinity
distance bounds in the special case when $K$ is a polytope.