Faster Logconcave Sampling from a Cold Start in High Dimension

We present a faster algorithm to generate a warm start for sampling an arbitrary logconcave density specified by an evaluation oracle, leading to the first sub-cubic sampling algorithms for inputs in (near-)isotropic position. A long line of prior work incurred a warm-start penalty of at least linear in the dimension, hitting a cubic barrier, even for the special case of uniform sampling from convex bodies.

Our improvement relies on two key ingredients of independent interest. (1) We show how to sample given a warm start in weaker notions of distance, in particular q-Rényi divergence for q = O(1), whereas previous analyses required stringent ∞-Rényi divergence (with the exception of Hit-and-Run, whose known mixing time is higher). This marks the first improvement in the required warmness since Lovász and Simonovits (1991). (2) We refine and generalize the log-Sobolev inequality of Lee and Vempala (2018), originally established for isotropic logconcave distributions in terms of the diameter of the support, to logconcave distributions in terms of a geometric average of the support diameter and the largest eigenvalue of the covariance matrix.

where S is any open subset of R n with smooth boundary, π(∂S) := lim inf ε↓0 π(Sε)-π(S) ε , and S ε = x : d(x, S) ≤ ε. The Ball walk requires O(n 2 C -2 Ch,d (π)) queries in expectation to reach a distribution that is ε-close to the target uniform distribution π over a convex body in TV-distance, starting from a R ∞ -warm start. We use the notation Ball walk : R ∞ → TV to indicate the required input warmness and output metric. Significant breakthroughs have refined the Cheeger bound [PW60, KLS95, Eld13, LV24, Che21, KL22, Kla23], leading to the current best bound C -2 Ch,d (π) ≲ ∥cov π∥ log n by Klartag [Kla23], where ∥cov π∥ denotes the largest eigenvalue of the covariance matrix of π.

A different sampler Hit-and-Run : R 2 → R 2 , studied in [Lov99, LV06b], was shown to mix using n 2 D 2 C -2

Ch,d K (π) queries, where d K is the cross-ratio distance. Unlike the Ball walk, since C Ch,d K ≤ 1 is tight, progress on the KLS conjecture does not lead to an improvement in its complexity. Since ∥cov π∥ < D 2 , the Ball walk has a better bound from a R ∞ -warm start.

Recently, Kook, Vempala, and Zhang [KVZ24] introduced In-and-Out (equivalently, the proximal sampler [LST21] for uniform distributions, referred to here as PS unif ), a refinement of the Ball walk. Its convergence rate can be directly related to the Poincaré constant for a target π:

Definition 1.1. A probability measure π on R n satisfies a Poincaré inequality with constant C PI (π) if for any locally Lipschitz function f : R n → R, PS unif : R c → R 2 under (PI), and this relaxes the requirement of stringent initial warmness R ∞ to R c without compromising query complexity. This result not only improves theoretical guarantees but also opens doors to more flexible algorithmic design for downstream tasks, as seen shortly.

Moreover, we show analogous improvements for the Proximal sampler for truncated Gaussian distributions πγ σ 2 (referred to as PS Gauss in [KZ25]), where π is the uniform distribution over K and γ σ 2 is a standard Gaussian with covariance σ 2 I n . This family of distributions plays an important role in annealing (e.g., Gaussian cooling). Specifically, we prove that the warmness requirement can also be relaxed from R ∞ to R c without deteriorating the previously established query complexity of n 2 C LSI (πγ σ 2 ) ≤ n 2 σ 2 (i.e., PS Gauss : R c → R 2 under (PI)).

Our discussion naturally prompts the question of how to quickly generate a warm start. The main idea is annealing [DFK91, KLS97, LV06c, CV18, KZ25]. It involves constructing a sequence µ i i∈[m] of distributions gradually approaching the target π, such that (i) µ 1 is easy to sample from (e.g., Gaussians), (ii) µ m is close to the target π, and (iii) a current distribution µ i provides a warm start to the next one µ i+1 .

Lovász and Vempala [LV06c] proposed an annealing scheme maintaining R 2 -warmness, with Hit-and-Run used to transition across annealing distributions. Due to the approximate nature of the distributions obtained during annealing, their analysis uses a coupling argument to account for this issue, providing guarantees for final samples in TV-distance. Hence, combined with Hit-and-Run, when R 2 = E π [∥•∥ 2 ], their final sampling algorithm has query complexity of n 3 R 2 for TV-guarantees.

Gaussian cooling [CV18] uses a sequence of truncated Gaussians πγ σ 2 , increasing the variance σ 2 from n -1 to R 2 according to a predetermined schedule, σ 2 ← σ 2 (1 + σ 2 /R 2 ). This scheme relays stronger R ∞ -warmness, thus being more 'conservative' than the Lovász-Vempala scheme, but benefits from the faster mixing of the Ball walk (for truncated Gaussian) compared to Hit-and-Run. Gaussian cooling has complexity of n 2 (n ∨ R 2 ) with TV-distance guarantees. Roughly, doubling σ 2 takes R 2 /σ 2 phases, and with the com