📊 statistics

Pliable rejection sampling

Pliable Rejection Sampling (PRS) is a new approach that uses a kernel estimator to learn a sampling proposal, providing a method that produces high-probability i.i.d. samples with a guaranteed number of accepted samples.

Original authors: Akram Erraqabi, Michal Valko, Alexandra Carpentier, Odalric-Ambrym Maillard

Published 2026-04-27

📖 3 min read☕ Coffee break read

CC BY 4.0

Original authors: Akram Erraqabi, Michal Valko, Alexandra Carpentier, Odalric-Ambrym Maillard

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 a professional treasure hunter, and your job is to find gold coins scattered across a massive, dark field. To find them, you have a "detector" (the function $f$ ) that tells you exactly how much gold is at any specific spot you point to.

The problem? Every time you use the detector, it costs you \ $100. If you point it at a patch of dirt and it says "zero gold," you’ve just wasted \$ 100.

The Old Ways: The "Blind Guess" and the "Strict Rules"

Before this paper, treasure hunters had two main ways to work:

Simple Rejection Sampling (The Blind Guess): You just walk around the field randomly, pointing your detector everywhere. Because most of the field is empty, you spend almost all your money pointing at dirt. You find a few coins, but you go broke very quickly.
Adaptive Rejection Sampling (The Strict Rules): This is like having a rulebook that says, "You can only look for gold if the field is shaped like a perfect smooth hill." If the field has two hills, or a weird jagged shape, the rulebook breaks, and you’re back to guessing blindly.

The New Way: Pliable Rejection Sampling (The "Smart Map")

The authors of this paper created Pliable Rejection Sampling (PRS). Instead of guessing blindly or following strict rules, PRS uses a "Smart Map" strategy.

Step 1: The Reconnaissance Mission
Instead of spending your whole budget looking for gold, you take a small portion of your money and do a quick, random sweep of the field. You aren't looking for gold yet; you're just trying to get a "vibe" for where the gold might be.

Step 2: Drawing the Sketch
You take the data from that quick sweep and use a mathematical tool (a "kernel estimator") to draw a rough sketch of the field. It’s not a perfect map, but it’s a great start. It shows you, "Hey, there seems to be a pile of gold over in that corner!"

Step 3: The "Pliable" Envelope
Now, instead of walking randomly, you create a "safety net" (an envelope) based on your sketch. This net is "pliable"—meaning it’s flexible. It follows the shape of your sketch but adds a little extra "padding" around the edges to make sure you don't accidentally miss a coin because your sketch was slightly off.

Step 4: The Efficient Hunt
Now you spend the rest of your money pointing your detector only inside that safety net. Because your net is shaped almost exactly like the gold piles, almost every time you point the detector, you find gold!

Why is this a big deal? (The "Guarantee")

The "magic" of this paper isn't just that it's faster; it's that the authors proved it mathematically.

In most methods, you hope you're being efficient. With PRS, the authors provide a guarantee: as you spend more money, the amount of "wasted" guesses (pointing at dirt) becomes almost zero. Eventually, almost every dollar you spend results in finding a gold coin.

Summary in a Nutshell

Old way: Throwing darts at a board in the dark.
PRS way: Turning on a dim light, sketching the board, and then throwing darts only at the bullseye.

It’s a way to sample from complex, "difficult" mathematical shapes without needing to know exactly what those shapes look like beforehand, and without wasting massive amounts of computing power.

Technical Summary: Pliable Rejection Sampling (PRS)

1. Problem Statement

Rejection sampling is a fundamental technique for sampling from a target density $f$ when direct sampling is intractable. It works by constructing an envelope $M_g$ (an upper bound) using a proposal distribution $g$ . However, traditional Rejection Sampling (SRS) suffers from extremely low efficiency if $g$ is not a tight fit for $f$ , leading to a high rejection rate and wasted computational resources (calls to $f$ ).

Existing adaptive methods attempt to solve this but face significant limitations:

Adaptive Rejection Sampling (ARS): Requires the target density to be log-concave (unimodal), which is too restrictive for many real-world applications.
Adaptive Rejection Metropolis Sampling: Produces correlated samples (Markov chains) rather than independent and identically distributed (i.i.d.) samples.
$A^\star$ Sampling: Requires prior knowledge of a decomposition of $f$ (splitting it into a tractable part and a bounded part), which is often unavailable.

The core challenge identified by the authors is that while Adaptive Importance Sampling only requires a good estimator in terms of $L_2$ risk, Rejection Sampling requires a proposal that is a tight upper bound in terms of $L_\infty$ risk to maintain efficiency.

2. Methodology

The authors propose Pliable Rejection Sampling (PRS), a non-parametric approach that "bends" a uniform distribution into a tight proposal using kernel density estimation.

The PRS Algorithm follows three main stages:

Initial Sampling: Draw $N$ points uniformly at random from the domain $[0, A]^d$ and evaluate the target function $f$ at these points.
Density Estimation: Use a kernel regression method (specifically a product kernel, such as a Gaussian kernel) to estimate the target density $\hat{f}$ based on the $N$ collected samples.
Pliable Proposal Construction: Construct a "pliable" proposal $b_{g^\star}$ that acts as a tight upper bound. This is done by adding a uniform error bound $r_N$ (derived from theoretical convergence rates of kernel estimators) to the estimate $\hat{f}$ . This ensures that the proposal $g$ satisfies $M_g \geq f$ with high probability.

Key Mathematical Components:

Kernel Estimator: Uses a kernel $K$ to interpolate $f$ .
Uniform Bound: The method leverages recent advances in density estimation to provide a bound on the estimation error that holds uniformly across the entire domain with high probability ( $1-\delta$ ).
Complexity Optimization: The number of initial samples $N$ is optimized to balance the cost of estimation against the efficiency of the subsequent rejection sampling phase.

3. Key Contributions

Non-parametric Adaptivity: Unlike ARS, PRS does not assume log-concavity or unimodality; it only requires mild smoothness properties (Hölder continuity).
Theoretical Guarantees: The paper provides a formal guarantee on the number of accepted samples. Asymptotically, for a budget of $n$ calls to $f$ , the number of i.i.d. samples obtained is $n - o(n)$ , meaning the rejection rate becomes negligible as $n$ increases.
Perfect Sampling: Unlike MCMC-based adaptive methods, PRS produces true i.i.d. samples with high probability.
High-Dimensional Extension: The authors propose a localization strategy using convex optimization. If the density is convex outside its high-mass support, they show that the "initial sampling" phase can be made to scale polynomially with dimension $d$ rather than exponentially.

4. Results

The authors conducted numerical experiments comparing PRS against SRS and $A^\star$ sampling:

Peakiness Scaling: As the target distribution becomes more "peaky" (harder to sample), PRS maintains a higher acceptance rate than both SRS and $A^\star$ sampling.
2D Example: In a complex 2D trigonometric density, PRS achieved an acceptance rate comparable to the state-of-the-art $A^\star$ sampling but without requiring the $f(x) \propto \exp(\phi(x))$ decomposition.
Clutter Problem: In a bimodal, peaky posterior distribution (the "clutter problem"), $A^\star$ sampling performed slightly better, but PRS still significantly outperformed the baseline SRS.

5. Significance

PRS represents a significant step forward in sampling theory by bridging the gap between non-parametric density estimation and rejection sampling. Its primary significance lies in its efficiency-to-information ratio: it provides near-optimal sampling efficiency (approaching one sample per function evaluation) without requiring the user to provide structural assumptions (like log-concavity) or functional decompositions (like $A^\star$ sampling). This makes it a robust, "plug-and-play" tool for complex, low-to-moderate dimensional density sampling.