A unified complexity bound for logconcave sampling

This paper presents a simple, unified, and nearly tight convergence bound for sampling arbitrary logconcave distributions from a warm start using the In-and-Out algorithm with exponential lifting, achieved by establishing an improved Poincaré constant for the lifted distribution.

The Gist

Imagine you are trying to find a specific spot inside a giant, invisible, and slightly squishy cloud. This cloud represents a "logconcave distribution"—a mathematical shape that is popular in statistics and computer science because it's smooth and has a single peak (like a bell curve, but in many dimensions).

Your goal is to generate a random point that lands exactly where the cloud is thickest, following the cloud's natural shape. The problem is, the cloud is huge, and you can't see the whole thing at once. You only have a "flashlight" (an oracle) that tells you the height of the cloud at the specific spot you are standing on.

The Old Way: A Bumpy Ride

For a long time, computer scientists had an algorithm called "In-and-Out" (a fancy version of a random walk) to explore this cloud. They knew it worked, but the math predicting how fast it would work was a bit messy.

The old math said: "The time it takes depends on the size of the cloud, plus a weird, fixed penalty."
Think of it like driving a car. The old rule said: "Your travel time is the distance to your destination plus a mandatory 10-minute traffic jam, no matter how short the trip is."
This "mandatory 10 minutes" (the paper calls it the "∨1" term) made the algorithm seem slower than it actually was, especially for simple, well-behaved clouds. It created a split in the rules: one set of rules for simple clouds and a messier set for complex ones.

The New Discovery: A Smoother Path

The authors of this paper, Yunbum Kook and Santosh Vempala, found a way to remove that "mandatory 10-minute traffic jam." They proved that the algorithm is actually faster and more consistent than previously thought.

Here is how they did it, using a simple analogy:

1. The "Exponential Lifting" Trick
To make the random walk easier, the algorithm uses a trick called "exponential lifting." Imagine you are trying to walk on a flat, 2D map of a mountain (the cloud). It's hard to know the best path.
Instead, the algorithm lifts you into a 3D room where the mountain is now a solid, transparent block. The top of the block is flat. Walking on a flat surface is much easier than navigating a jagged mountain.
In math terms, they turn the complex shape into a simpler, higher-dimensional shape where the rules of movement are straightforward.

2. The "Varentropy" Insight
The old math was worried that this new 3D room might be too "wobbly" or unstable, which would slow down the walk. They estimated the wobble by looking at the "variance" (how much things shake).
The authors realized that the shaking in this new room is actually incredibly small. They used a concept called varentropy (which sounds scary but just means "how much the information content varies").
They found that the "shake" in their new 3D room is so tiny (specifically, it shrinks as the dimensions get bigger) that it doesn't add any extra delay to the journey.

The Result: One Rule for All

By proving that the "wobble" is negligible, they removed that annoying "plus 10 minutes" penalty from the equation.

• Before: Time = (Size of Cloud) + (Fixed Penalty).
• After: Time = (Size of Cloud).

This means the algorithm is now unified. Whether you are sampling from a simple, perfectly round cloud (a "well-conditioned" setting) or a weird, constrained shape (like a cloud trapped inside a box), the same simple rule applies. The algorithm is nearly as fast as theoretically possible for both cases.

Why This Matters (In Simple Terms)

Think of this like discovering that a universal key works for every lock in a building, not just the fancy ones.

• Efficiency: Computers can now generate these random samples faster and with fewer "flashlight" checks (queries).
• Simplicity: Researchers no longer need to use two different sets of math to explain why the algorithm works for different types of shapes. It's all the same story now.

In short, the authors took a complex, slightly broken map of how to navigate these mathematical clouds, fixed the measurement tool, and showed us that the journey is actually smoother and more direct than we ever realized.

Technical Summary

Technical Summary: A Unified Complexity Bound for Logconcave Sampling

Problem Statement

The paper addresses the problem of sampling from an arbitrary full-dimensional logconcave probability measure $\pi_X \propto e^{-V}$ on $\mathbb{R}^d$, where $V: \mathbb{R}^d \to \mathbb{R} \cup \{\infty\}$ is a convex function accessible only via an evaluation oracle. The goal is to determine the query complexity (number of evaluations of $V$) required to generate a sample $X^*$ such that its distribution is close to $\pi_X$ in terms of Rényi divergence, given a "warm start" initial distribution $\pi_0$.

A specific normalization is assumed: the "ground set" $L_g = \{x : V(x) - \inf V \le 10d\}$ contains the unit ball $B(0,1)$. This ensures the effective support of the distribution is not arbitrarily small.

Previous work on the In-and-Out algorithm (a proximal sampler adapted via exponential lifting) established convergence rates that included a term $\Lambda \vee 1$ (where $\Lambda = \|\text{cov } \pi_X\|_{op}$). In well-conditioned settings (e.g., strongly logconcave and smooth densities), this resulted in a complexity of roughly $\kappa d + d^2$, where $\kappa$ is the condition number. The $d^2$ term was an artifact of the analysis, specifically arising from a loose bound on the Poincaré constant of the lifted distribution. The paper asks whether this additive $d^2$ term is inevitable or merely an artifact of the proof technique.

Methodology

The authors utilize the In-and-Out algorithm (also known as the Proximal Sampler), which alternates between a forward Gaussian step and a backward step involving the target potential $V$. To implement the backward step using only a zeroth-order oracle, the algorithm employs exponential lifting.

1. Exponential Lifting: The distribution $\pi_X$ is lifted to a higher-dimensional space $\mathbb{R}^d \times \mathbb{R}$ via the measure $\pi_Z$ with density:
   $$\pi_Z(dx, dt) \propto e^{-dt} \mathbf{1}[V(x) \le dt] \, dx \, dt$$
   The marginal of $\pi_Z$ on the $x$-coordinates is exactly $\pi_X$. The support of $\pi_Z$ is convex, and its log-density is linear in the lifted coordinate $t$, simplifying the implementation of the backward step.

2. Convergence Analysis: The convergence rate of the sampler in $\chi^2$-divergence (and subsequently in Rényi divergence) is governed by the Poincaré constant $C_{PI}(\pi_Z)$ of the lifted distribution. Previous analyses relied on the bound $\|\text{cov } \pi_Z\| \lesssim \|\text{cov } \pi_X\| \vee 1$, which introduced the problematic $\vee 1$ term.

3. Key Technical Innovation: The paper improves the bound on the covariance of the lifted distribution $\pi_Z$.

   • The authors observe that if $X \sim \pi_X$ and $E \sim \text{Exp}(1)$ are independent, the lifted variable $T$ satisfies $T \stackrel{d}{=} (V(X) + E)/d$.
   • This implies $\text{Var}_{\pi_Z}(T) = \text{Var}_{\pi_X}(V(X))/d^2 + 1/d^2$.
   • Using the varentropy bound (the variance of the information content $-\log \pi_X(X)$), which states $\text{Var}_{\pi_X}(V(X)) \le d$ for logconcave densities, the authors derive:
     $$\text{Var}_{\pi_Z}(T) \le \frac{d}{d^2} + \frac{1}{d^2} = \frac{2}{d}$$
   • By applying the Cauchy-Schwarz inequality to the full covariance matrix, they prove:
     $$\|\text{cov } \pi_Z\| \le \|\text{cov } \pi_X\| + \frac{2}{d}$$
   • Under the ground-set normalization, it is shown that $1/d \lesssim \|\text{cov } \pi_X\|$, meaning the additive term is absorbed by the intrinsic scale of the covariance.

Key Contributions and Results

1. Improved Poincaré Constant Bound

The central theoretical contribution is Lemma 1.3, which establishes that the operator norm of the covariance of the lifted distribution satisfies $\|\text{cov } \pi_Z\| \le \|\text{cov } \pi_X\| + 2/d$. Consequently, the Poincaré constant of the lifted distribution scales as $C_{PI}(\pi_Z) \lesssim \|\text{cov } \pi_X\| \log d$, removing the additive constant that previously necessitated a $\vee 1$ term.

2. Unified Complexity Bounds (Theorem 1.1)

The improved covariance bound leads to a unified complexity result for zeroth-order logconcave sampling from a warm start:

• Rényi Divergence ($R_q$): For $q \ge 2$, the algorithm returns a sample with $R_q(\text{law } X^* \| \pi) \le \epsilon$ using $\tilde{O}(q d^2 \Lambda \log^3(1/\epsilon))$ queries in expectation.
• Rényi Infinity Divergence ($R_\infty$): If the initial distribution is $M_\infty$-warm, the algorithm returns a sample with $R_\infty(\text{law } X^* \| \pi) \le \epsilon$ using $\tilde{O}(d^2 R \Lambda^{1/2} \text{polylog}(1/\epsilon))$ queries, where $R = \mathbb{E}_\pi[\|X\|^2]$.

3. Recovery of Well-Conditioned Bounds (Corollary 1.2)

For well-conditioned distributions (where $V$ is $\alpha$-strongly logconcave and $\beta$-log smooth, with condition number $\kappa = \beta/\alpha$), the new bound recovers the optimal complexity of $\tilde{O}(q \kappa d \log^3(1/\epsilon))$.

• Significance: This eliminates the previous $d^2$ term (which appeared as $\kappa d + d^2$ in prior works like [KV25b, KV25a, KV25c]). The result demonstrates that the same algorithm and analysis framework apply seamlessly to both general logconcave settings and well-conditioned settings without needing separate analyses or suffering from an artificial penalty in the latter.

Significance and Claims

The paper claims to provide a simple, unified, and nearly tight bound for sampling arbitrary logconcave distributions.

• Unification: The primary significance is the unification of complexity guarantees. By removing the " $\vee 1$ " artifact, the authors show that the query complexity for general logconcave sampling is naturally governed by the covariance of the target distribution, just as it is for uniform sampling over convex bodies.
• Tightness: The bound is described as "nearly tight" for both constrained settings (e.g., Gaussian restricted to a convex body) and well-conditioned settings.
• Methodological Simplicity: The improvement is achieved not by changing the algorithm (In-and-Out remains the same) but by a refined analysis of the lifted distribution's geometry using varentropy bounds. This streamlines the theoretical guarantees established in previous literature.

The authors do not propose new experimental applications or future algorithmic directions beyond this theoretical unification, positioning the work as a foundational step toward a single, coherent complexity theory for logconcave sampling.