📊 statistics

Windowed thinning and query complexity for the bouncy particle and Zigzag samplers

This paper introduces windowed thinning, an exact simulation method for the bouncy particle and Zigzag samplers that achieves improved query complexity guarantees from a Gaussian cold start by dividing trajectories into deterministic windows with tractable local envelopes, resulting in $O(\kappa^{1/2}d(d\log\kappa+\log\frac1\varepsilon))$ gradient queries for the bouncy particle sampler and $O(\kappa d^{1/4}(d\log\kappa+\log\frac1\varepsilon))$ full-gradient equivalents for the Zigzag process.

Original authors: Jianfeng Lu, Yinchen Luo

Published 2026-07-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jianfeng Lu, Yinchen Luo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the lowest point in a vast, foggy mountain range. This isn't just a hiking trip; it's a mathematical quest to find the "sweet spot" of a complex system, whether that's training an artificial intelligence, modeling how proteins fold, or predicting weather patterns. In the world of computer science and statistics, this mountain range is called a "target distribution," and the fog represents the fact that we can't see the whole map at once. We can only peek at a tiny spot and ask, "Is the ground sloping up or down here?" This is the job of a sampler: a clever algorithm that wanders around this landscape, taking steps to eventually spend enough time in the low valleys to give us a perfect picture of the whole terrain.

The challenge is that the mountains can be tricky. Some are steep and narrow (like a deep canyon), while others are wide and flat. If your sampler is too clumsy, it might get stuck in a loop or take forever to cross a canyon. If it's too careful, it moves so slowly that you never finish the trip. The goal is to find a method that is both fast and accurate, using as few "peek-at-the-ground" checks (called gradient queries) as possible. This paper tackles two specific, high-tech hikers: the Bouncy Particle Sampler and the Zigzag Sampler. These aren't your average walkers; they are "event-driven," meaning they glide smoothly in straight lines until they hit a virtual wall or a sudden change in the landscape, at which point they instantly bounce or flip direction. Because they don't take tiny, clumsy steps like a drunkard's walk, they are theoretically perfect at avoiding the "fog" of approximation errors. But the big question remains: How many times do they have to peek at the ground to get the job done?

This paper introduces a new, smarter way to guide these high-speed hikers, proving that they can reach their destination with a surprisingly efficient number of checks. The authors, Jianfeng Lu and Yinchen Luo, propose a technique called Windowed Thinning. To understand why this is needed, imagine you are driving a car at high speed through a foggy forest, and you need to know exactly when to swerve to avoid a tree. You can't see the tree until you are right next to it, but you know the trees are somewhat predictable. A naive driver might check the map constantly, slowing down to a crawl. A reckless driver might guess and crash. The authors' solution is to divide the road into short, manageable "windows." At the start of each window, you check the map (the gradient) to get a rough idea of where the trees are. Then, you use the fact that trees don't move instantly to create a "safety envelope"—a zone where you are guaranteed to be safe. You drive fast within this zone, only stopping to check the map again if you get close to the edge of the envelope.

The paper proves that by balancing the length of these windows—making them short enough to be safe but long enough to keep moving fast—you can simulate these samplers perfectly without any approximation errors. The authors provide a mathematical guarantee on exactly how many "map checks" (queries) are needed to reach a specific level of accuracy, denoted by $\epsilon$ . They start the journey from a "cold start," meaning the hiker begins in a random spot far from the goal, rather than being given a helpful head start.

For the Bouncy Particle Sampler, which bounces off the landscape like a billiard ball, the authors show that the number of checks needed grows roughly with the square root of the condition number (a measure of how "twisted" the mountain is) and the dimension of the problem. Specifically, the cost is proportional to $\kappa^{1/2}d(d \log \kappa + \log \frac{1}{\epsilon})$ . For the Zigzag Sampler, which flips its direction coordinate by coordinate like a zigzagging lightning bolt, the cost is slightly different, scaling as $\kappa d^{1/4}(d \log \kappa + \log \frac{1}{\epsilon})$ when counting full map checks.

The paper is rigorous and mathematical, offering a "proof" rather than just a simulation. It explicitly rules out the idea that you need a "warm start" (a helpful initial guess) to get these good results; the method works even if you start from scratch. While the authors note that other methods like MALA (Metropolis-adjusted Langevin Algorithm) might have better performance in terms of the "twistiness" of the mountain ( $\kappa$ ), their method is superior in how it handles the sheer size of the problem (the dimension $d$ ) for these specific types of samplers. They also clarify that while some recent work suggests even faster methods using different mathematical tools, their approach is a solid, proven guarantee for these specific "event-driven" hikers.

In essence, this paper hands us a new set of instructions for our high-speed hikers. It tells us exactly how to pace our "map checks" so that we don't waste energy checking the ground too often, but also don't crash into the fog. By using these "windows," we can run these samplers exactly as nature intended, with a clear, mathematical promise of how long the trip will take and how many steps we need to take to get there. It's a victory for efficiency, showing that even in the most complex, high-dimensional landscapes, a little bit of smart planning can make the journey much faster.

Technical Summary: Windowed Thinning and Query Complexity for the Bouncy Particle and Zigzag Samplers

Problem Statement
The paper addresses the query complexity of exact simulation methods for sampling from a log-concave target measure $\mu(dx) \propto e^{-U(x)} dx$ on $\mathbb{R}^d$ , where $U$ is $m$ -strongly convex and $L$ -smooth. The condition number is denoted by $\kappa = L/m$ . The focus is on two Piecewise Deterministic Markov Processes (PDMPs): the Bouncy Particle Sampler (BPS) and the Zigzag sampler.

While these samplers offer exact continuous-time trajectories without time-discretization error, their practical implementation relies on generating event times (bounces or flips) from inhomogeneous Poisson processes. Since the event rates depend on the target gradient $\nabla U$ along the trajectory, and $\nabla U$ is accessed via an oracle, exact simulation requires "thinning" (Poisson thinning). This involves proposing candidate events from an upper envelope of the rate and accepting them with a probability proportional to the true rate. The central challenge is balancing the tightness of this envelope against the computational cost: a loose envelope generates many rejected proposals (wasting gradient queries), while a tight envelope requires frequent gradient evaluations to update the envelope. The authors aim to provide non-asymptotic query complexity guarantees for these methods starting from an explicit "cold start" (a Gaussian distribution centered at the minimizer $x^\star$ ), without assuming a warm start or stationarity.

Methodology
The core algorithmic contribution is Windowed Thinning. The authors propose dividing the simulation horizon into deterministic windows. At the beginning of each window, the gradient is evaluated at the current position (the "anchor"). Using the $L$ -Lipschitz continuity of $\nabla U$ , they construct a local, tractable upper envelope for the event rate based on the cumulative distance traveled from the anchor within that window.

BPS: The bounce rate is bounded by $(\langle v, G_k \rangle)_+ + L|v|D_s$ , where $G_k$ is the anchor gradient and $D_s$ is the distance traveled.
Zigzag: Coordinate-wise flip rates are bounded similarly, and the total rate is the sum of these coordinate-wise envelopes.

This construction allows the proposal times to be found by solving quadratic equations (since the envelope is affine in time and its integral is quadratic). The window length $\tau$ is chosen to balance the cost of anchor queries (frequent for short windows) against the cost of rejected proposals (high for long windows).

To establish complexity bounds, the authors combine:

Quantitative Mixing Estimates: They utilize recent $L^2$ -hypocoercivity results (specifically $\chi^2$ -contraction rates) by Lu and Wang to determine the necessary simulation horizon $T$ to achieve a target total-variation error $\epsilon$ .
Moment Estimates: They derive bounds on the expected number of events (bounces/flips) and rejected proposals. Crucially, they control these counts directly from the non-stationary Gaussian cold start. Instead of tracking individual events, they bound the expected total number of events via time-integrated squared event rates.
Dynkin Identities: They construct specific observables (e.g., $\langle x-x^\star, v \rangle$ for BPS and $v \cdot \nabla U(x)$ for Zigzag) to apply Dynkin's formula. This transforms the path-dependent counting problem into a moment estimation problem, leveraging the convexity and smoothness of $U$ and the properties of the Gaussian cold start.

Key Contributions and Results
The paper establishes explicit expected query counts (gradient evaluations) required to achieve a total-variation error of at most $\epsilon$ , starting from a Gaussian cold start $\mathcal{N}(x^\star, L^{-1}I) \otimes \mathcal{N}(0, I)$ .

Bouncy Particle Sampler (BPS): The expected number of full-gradient queries is $O(\kappa^{1/2} d (d \log \kappa + \log(1/\epsilon)))$ .
Zigzag Sampler: The expected number of coordinate-partial queries is $O(\kappa d^{5/4} (d \log \kappa + \log(1/\epsilon)))$ . Expressed in full-gradient equivalents (where $d$ partial queries count as one), the complexity is $O(\kappa d^{1/4} (d \log \kappa + \log(1/\epsilon)))$ .

These bounds are derived by optimizing the window length $\tau$ (specifically $\tau \approx (Ld)^{-1/2}$ for BPS and $\tau \approx L^{-1/2}d^{-1/4}$ for Zigzag) to minimize the sum of anchor and rejection costs over the mixing time.

Significance and Claims
The authors position their work as providing the first explicit, non-asymptotic query complexity guarantees for BPS and Zigzag samplers starting from a cold start, without relying on a warm-start phase.

Comparison to Existing Methods: The paper notes that while their BPS bound has a better dependence on the condition number $\kappa$ compared to Metropolis-adjusted Langevin algorithm (MALA) and Proximal samplers, it exhibits a worse dependence on dimension $d$ (specifically $d^2$ vs $d^{1/2}$ for MALA). For Zigzag, the complexity is $O(\kappa d^{5/4})$ in partial queries, which is an improvement over previous high-probability warm-start bounds in certain regimes, though the authors acknowledge that the dimension dependence remains a limitation compared to first-order methods.
Theoretical Novelty: The analysis relies on $L^2$ -hypocoercivity rather than relative-entropy contraction, as the latter is known to fail for BPS and Zigzag with standard Gaussian velocity laws. The use of windowed thinning to locally control the envelope error, combined with the specific moment bounds derived from the cold start, allows for a rigorous accounting of the "cost of simulation" alongside the "cost of convergence."
Limitations: The authors modestly note that their results provide expected complexity guarantees rather than high-probability bounds (unlike some warm-start analyses). They also mention that while coordinate-specific assumptions could further reduce Zigzag's complexity, such structural assumptions are not pursued in this work.

In summary, the paper provides a rigorous framework for analyzing the computational cost of exact PDMP samplers, demonstrating that windowed thinning yields tractable complexity bounds that explicitly account for the trade-off between envelope tightness and gradient evaluation frequency, even when starting far from equilibrium.

More like this