AI Research Portal

This paper introduces the first instance-dependent testers for samplers, named toltest and ERtoltest, which operate in the interval conditioning model and are capable of testing samplers over natural numbers (infinite discrete domains). The core idea involves a novel distance estimation algorithm that leverages an interval conditioning framework and establishes a new connection with probability mass estimation of continuous distributions. The proposed method, implemented as Lachesis, demonstrates substantial practical gains, achieving up to 1000x speedup over state-of-the-art worst-case testers.

The paper addresses several bottlenecks in existing sampler verification methods:

Worst-case efficiency focus: Prior provably correct testers like Barbarik, Teq, Flash, and CubeProbe primarily focus on worst-case efficiency, which may not be optimal for all distributions.
Limited to finite domains: Existing testers do not support the verification of samplers over infinite discrete domains, which are frequently encountered in fields like Astronomy, Finance, and Network Security.

Design of the first tester of samplers with instance-dependent efficiency, allowing testing over natural numbers.
Development of tests via a novel distance estimation algorithm between an unknown and a known probability distribution using an interval conditioning framework.
Establishment of a new connection with probability mass estimation of a continuous distribution.
Introduction of toltest and ERtoltest, the first algorithms for identity testing of distributions in the interval conditioning model with instance-dependent bounds.
Development of the first practical realization of the interval conditioning oracle to test inverse transform samplers.
Demonstration of up to 1000x speedup over state-of-the-art worst-case algorithms.

The proposed method designs instance-dependent testers for samplers using an interval conditioning framework. It involves estimating the total variation distance between an unknown distribution P (from the sampler) and a known distribution Q.

Interval Conditioning: The method relies on an ICOND oracle, which takes an interval [i, j] and returns a sample drawn from P conditioned on x ∈ [i, j]. This is extended to a continuous setting with ICONDCont.

Convolution with Triangular Distribution: To bridge the gap between discrete P and continuous ICONDCont requirements, the discrete distribution P is convolved with a continuous Triangular distribution Tri to form PTri.

Triangular distribution Tri is defined for x ∈ [−1/2, 1/2] as: Tri(x) = { 4x + 2 if −1/2 ≤ x ≤ 0 { −4x + 2 if 0 ≤ x ≤ 1/2
Convolution operation of a discrete distribution P with Tri: PTri(x) = Σt∈[n] P(t) Tri(x - t) PTri is a continuous distribution.

Simulating ICONDCont: An algorithm (Algorithm 2) is introduced to simulate the ICONDCont oracle for PTri using the basic ICOND oracle for P and rejection sampling. It obtains a sample x from ICOND(P, [rnd(u), rnd(v)]) and a sample r from Tri. If (x + r) falls within [u, v], it's returned; otherwise, the process restarts.

Probability Mass Estimator (Est): A crucial subroutine, Est (Algorithm 3), estimates P(x) for any x ∈ Z using the Tootsie Pop Algorithm (TPA).

Tootsie Pop Algorithm (TPA): TPA (Algorithm 1) estimates the probability mass of a target interval within a continuous distribution by iteratively refining the interval. It takes PTri, an element x, number of iterations r, and parameters Thresh and δ.
Est Phases: Est operates in two phases. First, it calls TPA to get a coarse estimate λ. If successful, it computes a refined iteration bound r2 and makes a second TPA call. The final estimate of P(x) is e^-λ.

Distance Estimators (toltest and ERtoltest):

toltest (Algorithm 4): Given ICOND access to P and a known Q, it outputs Accept if dtv(P,Q) ≤ ε and Reject if dtv(P,Q) ≥ η. It samples from a mixture distribution P ◊ Q = (P+Q)/2, uses Est to estimate P(xi) for each sample xi, and computes a distance d.
ERtoltest (Algorithm 5): A modification of toltest that outputs Accept if l∞(P,Q) ≤ ε and Reject if dtv(P,Q) ≥ η. The key difference is that ERtoltest uses a sample-dependent threshold B for Est, allowing it to run faster by adaptively adjusting the threshold.

Key Equations:

Multiplicative distance: l∞(P,Q) = max x∈[n] |P(x)/Q(x) - 1|
Total variation distance: dtv(P,Q) = (1/2) Σx∈[n] |P(x) – Q(x)|
Expected ICOND queries for toltest: E(η – ε)⁻⁴ E x~P◊Q [tiltP◊Q(x) ⋅ log² (1 / P◊Q(x))]
Expected ICOND queries for ERtoltest: E(η – ε)⁻⁴ E x~P [min(tiltQ(x), K(x)) ⋅ log² (1 / P(x))] where K(x) = min(log² (P(x)/Q(x)), log² (Q(x)/P(x)))

Definitions:
- rnd(a): nearest integer of a positive real number a ∈ R+.
- [n]: set {1, 2, ..., n}.
- [a, b]: discrete interval {a, a+1, ..., b} for integers a, b ∈ [n].
- [u, v]: closed interval for real numbers u, v ∈ R.
- P(S): probability mass of set S under distribution P.
- P ◊ Q: mixture distribution (P+Q)/2.
ICOND Oracle: Takes an interval [i, j] ⊆ [n] and returns a sample drawn from P conditioned on x ∈ [i, j].
ICONDCont Oracle: Takes a distribution μ over R and an interval [u, v] ⊆ R, returning a sample from μ conditioned on x ∈ [u, v].
Algorithm 1 (TPA):
- Inputs: PTri, x, r, Thresh, δ, θ.
- Initial interval: [−n, 2n].
- Refinement: Samples from PTri conditioned on the current interval.
- Output: Estimate λ or ⊥ if it fails.
Algorithm 2 (ICONDCont Simulation):
- Inputs: PTri, u, v, δ, θ.
- Max attempts: T ← (2θ + 1) log(1/δ).
- Sampling: x ← ICOND(P, [rnd(u), rnd(v)]), r ← Tri.
- Condition: If (x + r) ∈ [u, v], return x+r.
- Failure: Return ⊥ after T attempts.
Algorithm 3 (Est):
- Inputs: P, x, ζ, δ, B, θ.
- Phase 1: Coarse estimate λ1 using TPA with r1 ← 2 log(2/δ) and Thresh1 ← B + log(2r1/δ) + √log²(2r1/δ) + 2B log(2r1/δ).
- Phase 2: Refined estimate λ using TPA with r2 ← 2(λ1 + √λ1 + 2 + log(1+ζ)) / log²(1+ζ) and Thresh2 ← B + log(2r2/δ) + √log²(2r2/δ) + 2B log(2r2/δ).
- Output: e^-λ or ⊥.
Algorithm 4 (toltest):
- Inputs: P, Q, ε, η, δ.
- Parameters: ε' ← ε/4, η' ← η/4, ζ ← (η'-ε')/(η'+ε'+2), k ← (8/(η'ε'))² log(1/δ), t' ← 3kt.
- Sampling: Multiset X = {x1, ..., xt'} from P ◊ Q.
- Threshold: B ← log(1/Qmin) + log(1+ε'), θ ← Qmin.
- Estimation: Px_i ← Est(P◊Q, xi, ζ, δ, B, θ).
- Decision: Based on d = Σx∈X max(0, 1 - Px_i / Q(xi)). If d > η'/4, Reject; else Accept.
Algorithm 5 (ERtoltest):
- Inputs: P, Q, ε, η, δ.
- Parameters: ζ ← (η-ε)/(η+ε), k ← (8/(ηε))² log(1/δ), t ← 3kt.
- Sampling: Multiset X = {x1, ..., xt} from P.
- Threshold: B ← log(1/Q(xi)) + log((1+ζ)/(1-ζ)) + tiltQ(xi).
- Estimation: Px_i ← Est(P, xi, ζ, δ, B, θ).
- Decision: Based on d = Σx∈X max(0, 1 - Px_i / Q(xi)). If d > η/2, Reject; else Accept.
Implementation: Prototype implemented in Python3. Lachesis is the name of the practical tester.

Datasets:
- Binomial samplers (n ranging from 1,000 to 600,000, p ranging from 0.01 to 0.5).
- Poisson samplers.
Metrics:
- Number of ICOND queries.
- Speedup factor.
Baselines:
- CubeProbe (Bhattacharyya et al. 2024), adapted for compatibility with inverse transform samplers.
Numeric Results:
- Lachesis (in toltest mode) achieves an average speedup of over 1000x compared to CubeProbe across nearly all benchmarks for Binomial samplers.
- For Binomial samplers, Lachesis (Accept) typically requires 46K-51K ICOND calls, while CubeProbe (Reject) requires 6611K-9874K calls for similar parameters.
- For Poisson samplers, Lachesis (Accept) typically requires 968K-1042K ICOND calls, while CubeProbe (Reject) requires 1797K-7739K calls for similar parameters.
- Parameters used for evaluation: ε = 0.01, η = 0.5, δ = 0.1 for both Lachesis and CubeProbe.
Runtime/Training Cost:
- Experiments conducted on a high performance computer cluster with Intel Xeon Gold 6148 CPUs.
- One CPU core and a 5GB memory limit allocated to each tester instance pair.

The query complexities of the algorithms depend on the tilt of the distributions to be tested.
The known lower bound of these problems is Ω(logn/log log n) in the worst case.
Finding a lower bound in terms of tilt of the distributions remains an intriguing open problem.

Method evidence: "In this work, we design the first tester of samplers with instance-dependent efficiency, allowing us to test samplers over natural numbers. Our tests are developed via a novel distance estimation algorithm between an unknown and a known probability distribution using an interval conditioning framework. The core technical contribution is a new connection with probability mass estimation of a continuous distribution." (section: Abstract)
Result evidence: "The practical gains are also substantial-our experiments establish up to 1000x speedup over state-of-the-art testers." (section: Abstract)
Limitation evidence: "The query complexities of our algorithms depend on the tilt of the distributions to be tested, whereas the known lower bound of these problems is Ω(logn/log log n) in the worst case (Canonne, Ron, and Servedio 2015). Finding a lower bound in terms of tilt of the distributions remains an intriguing open problem." (section: 7 Conclusion)

Instance Dependent Testing of Samplers Using Interval Conditioning

Summary

Problem

Key Contributions

Method

Technical Details

Results

Weaknesses / Limitations

Evidence

Additional Figures