📊 statistics

Establishing an $\Omega(\sqrt{d})$ complexity lower bound for PDMP samplers and how to break it: a sub- $\sqrt{d}$ algorithm for Gaussian-tailed targets

This paper establishes a fundamental $\Omega(\sqrt{d})$ complexity lower bound for standard Piecewise Deterministic Markov Process (PDMP) samplers and introduces a novel, locally adaptive scheme that bypasses this barrier to achieve sub- $\sqrt{d}$ complexity for Gaussian-tailed targets.

Original authors: Augustin Chevallier

Published 2026-06-19

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Augustin Chevallier

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 best spot to set up camp in a vast, foggy mountain range. You want to visit every interesting valley and peak with the right frequency, but you can't see the whole map at once. You have to take steps, look around, and decide where to go next.

In the world of computer science and statistics, this is called sampling. Computers use algorithms to "walk" through complex probability landscapes to find the most important areas.

This paper, written by Augustin Chevallier, tackles a specific type of computer walker called a PDMP sampler (Piecewise Deterministic Markov Process). Think of these as "bouncy" or "zig-zag" robots. Unlike traditional walkers that take small, hesitant steps, these robots zoom in straight lines until they hit an invisible wall (a mathematical boundary), then they bounce or flip direction instantly.

Here is the story of what the paper discovered and how it fixed a major problem.

1. The Problem: The "Bouncy" Wall

For a long time, scientists noticed something frustrating about these bouncy robots. As the mountain range gets wider (mathematically, as the number of dimensions, $d$ , increases), these robots get slower and slower.

The Old Rule: If you double the size of the map, a standard bouncy robot takes about $\sqrt{d}$ (the square root of the size) times longer to do its job.
The Competition: Other types of walkers (like the famous Hamiltonian Monte Carlo) are much faster in wide spaces. They scale much better, like $d^{1/4}$ or $d^{1/3}$ .

The author asked: Why are the bouncy robots stuck with this slow speed? Is it just a bad design, or is there a fundamental law of physics stopping them?

2. The Discovery: The "Perfect Invariance" Trap

The author proved that the slowness isn't a design flaw; it's a fundamental law.

Imagine a bouncy robot that is required to be perfectly balanced at every single instant of its journey. It must maintain a perfect "equilibrium" while zooming, bouncing, and turning. The paper proves that if a robot has to stay perfectly balanced at every continuous moment, it is mathematically impossible for it to move faster than the $\sqrt{d}$ limit.

It's like trying to drive a car that must be perfectly balanced on a tightrope at every millisecond. You can't speed up, or you'll fall off. The requirement to be "perfectly invariant" (balanced) at all times is the anchor dragging the robot down.

3. The Solution: The "Imperfect" Shortcut

So, how do you break this law? The author realized you have to stop trying to be perfect at every single moment.

The Analogy:
Imagine you are hiking a trail.

The Old Way: You must check your compass and ensure you are exactly on the path every single step. If you drift even a millimeter, you stop and correct. This is slow.
The New Way: You run fast, maybe you drift off the path a little bit, and you zig-zag wildly. But, at the end of your run, you look back at your entire path. You say, "Okay, I spent too much time in the swamp and not enough on the ridge. Let's re-weight my history." You essentially say, "I will pretend I was on the ridge more often than I actually was."

The author created a new algorithm that does exactly this:

Let it drift: The robot is allowed to move in a way that isn't perfectly balanced at every instant. It uses a "leapfrog" motion (similar to how other fast algorithms work) where energy fluctuates.
The "Re-weighting" Trick: Instead of forcing the robot to be perfect during the run, the algorithm waits until the run is over. It looks at the whole path and uses a clever math trick (Metropolis-Hastings) to re-calculate the probability. It essentially says, "Even though I drifted, if I look at the path through this specific lens, it looks like I was perfectly balanced."

4. The Result: Breaking the Speed Limit

By relaxing the rule that the robot must be perfect during the run, the author broke the $\sqrt{d}$ barrier.

The New Speed: For targets that look like a standard bell curve (Gaussian), the new algorithm scales incredibly fast. Instead of growing with the square root of the size ( $\sqrt{d}$ ), it grows much slower, roughly like $d^{0.2}$ to $d^{0.3}$ .
The Analogy: If the old robot took 100 steps to cross a small field, the new robot might only need 4 or 5 steps to cross a field 100 times bigger.

5. Why This Matters (According to the Paper)

The paper doesn't claim this will cure diseases or predict the stock market directly. Instead, it claims to have solved a theoretical bottleneck in how computers explore complex mathematical spaces.

Adaptability: The new robot is "locally adaptive." It can sense the shape of the terrain. If the ground is steep, it takes smaller steps; if it's flat, it zooms. It does this naturally without needing complex, pre-programmed strategies.
Robustness: The author tested this on different types of "mountains" (some with heavy tails, some with light tails). It worked well on the standard ones and remained stable even on the tricky ones, though it wasn't as fast on the non-standard ones.

Summary

The paper says: "We proved that the old 'bouncy' robots are stuck at a slow speed because they try too hard to be perfect at every moment. By letting them be imperfect during the run and fixing the math afterward, we created a new robot that is significantly faster in high-dimensional spaces."

It's a breakthrough in the theory of how computers move through data, showing that sometimes, to go faster, you have to stop trying to be perfect at every single step.

Technical Summary: Establishing an $\Omega(\sqrt{d})$ Complexity Lower Bound for PDMP Samplers and a Sub- $\sqrt{d}$ Algorithm for Gaussian-Tailed Targets

Problem Statement
Piecewise Deterministic Markov Process (PDMP) samplers, such as the Bouncy Particle Sampler (BPS) and the Zig-Zag process, offer a non-reversible alternative to traditional Markov Chain Monte Carlo (MCMC) methods. However, despite their theoretical appeal, no existing PDMP sampler has demonstrated computational complexity scaling better than $O(\sqrt{d})$ with respect to the target dimension $d$ . In contrast, gradient-based reversible methods like Hamiltonian Monte Carlo (HMC) and the Metropolis-Adjusted Langevin Algorithm (MALA) achieve superior scalings of $O(d^{1/4})$ and $O(d^{1/3})$ , respectively. The central question addressed by this work is whether the $O(\sqrt{d})$ barrier is an inherent limitation of the PDMP framework or merely a consequence of specific algorithmic designs.

Methodology
The paper employs a two-pronged approach: a theoretical lower bound proof and the construction of a novel algorithm that relaxes standard assumptions.

Theoretical Lower Bound:
The author establishes an $\Omega(\sqrt{d})$ lower bound on the computational complexity for a broad class of local PDMP samplers. The proof relies on several structural assumptions:
- Target Independence: The deterministic flow and auxiliary space do not depend on the specific target distribution $\pi$ .
- Local Jumps: The jump kernel changes the auxiliary variable but not the spatial position, ensuring absolutely continuous spatial trajectories.
- Invariance: The target distribution must remain invariant at all continuous times, not just at discrete sampling points.
By analyzing i.i.d. target distributions, the proof demonstrates that the expected jump rate $\mathbb{E}[\lambda]$ must scale as $\Omega(\sqrt{d})$ to satisfy the stationary equation $L^*\mu = 0$ . Since the distance between effectively independent samples grows as $\sqrt{d}$ , and the average speed is bounded, the total number of jumps required per independent sample scales as $\Omega(\sqrt{d})$ .
Algorithmic Innovation (Breaking the Barrier):
To bypass this limit, the paper proposes relaxing the assumption that the target density must be invariant at all continuous times. Instead, the algorithm allows the target to be invariant only at discrete sampling times, similar to standard MCMC.
- Framework: The method integrates the Metropolised NUTS-PDMP framework with a novel Oscillating PDMP dynamic inspired by HMC leapfrog integration.
- Dynamics: The process alternates between position updates ( $\dot{x} = v$ ) and velocity updates ( $\dot{v} = -\nabla U(x)$ ) at random continuous times, rather than fixed intervals.
- Path Re-weighting: Since the continuous trajectory does not strictly preserve the target measure, the algorithm employs a path-resampling strategy. It generates a trajectory using numerical approximations of event rates and then resamples a state from the trajectory based on a conditional probability density. This density re-weights states to correct for the Hamiltonian fluctuations along the path, ensuring the final output is an exact sample from the target distribution.
- Adaptivity: The algorithm utilizes the No-U-Turn (NUTS) criterion to adaptively determine trajectory lengths and employs locally adaptive step sizes for velocity updates, avoiding the need for complex global tuning strategies required by reversible HMC.

Key Contributions

Complexity Lower Bound: The paper provides a rigorous proof that standard PDMP samplers, which enforce continuous-time invariance, are fundamentally limited to $\Omega(\sqrt{d})$ complexity for i.i.d. targets.
Sub- $\sqrt{d}$ Algorithm: A novel Metropolised PDMP algorithm is introduced that forgoes continuous-time invariance. By utilizing path re-weighting and numerical approximations, it achieves a computational complexity of $O(d^\alpha)$ where $\alpha \in [0.2, 0.3]$ for Gaussian-tailed targets.
Local Adaptivity: The proposed framework naturally incorporates local adaptivity in both trajectory length and the distance between velocity updates, a feature that is difficult to implement in reversible HMC without complex strategies.

Empirical Results
The author presents empirical scaling results for dimensions $d \in \{2, \dots, 128\}$ across five target distributions:

Gaussian-Tailed Targets: For standard Gaussian, Bayesian Logistic Regression, and Gaussian Mixture targets, the number of events per Effective Sample Size (ESS) scales between $O(d^{0.22})$ and $O(d^{0.29})$ . The number of gradient evaluations scales between $O(d^{0.26})$ and $O(d^{0.31})$ . These results significantly outperform the $O(\sqrt{d})$ limit of traditional PDMPs and approach the theoretical scaling of HMC.
Non-Gaussian Targets: The algorithm demonstrates robustness on heavier-tailed (Logistic) and lighter-tailed (Quartic) distributions, though the scaling exponents are higher ( $O(d^{0.43})$ to $O(d^{0.64})$ ), reflecting the increased difficulty of these targets.

Significance and Claims
The paper claims to identify a fundamental limitation in the standard PDMP framework: the requirement for continuous-time invariance is the primary bottleneck preventing better dimensional scaling. By relaxing this constraint, the author demonstrates that PDMPs can achieve sub- $\sqrt{d}$ scaling, bridging the performance gap with HMC. The work suggests that the "sub- $\sqrt{d}$ " performance is not an artifact of a specific design but a consequence of allowing the sampler to operate with approximate invariance corrected via Metropolis-Hastings re-weighting. The author concludes that while the theoretical lower bound for standard PDMPs is established, the proposed algorithm offers a practical pathway to higher-dimensional efficiency, particularly for Gaussian-tailed targets, while maintaining the non-reversible advantages of PDMPs.