Research map / Learning theory and algorithms / Sample complexity
Testing Self-Reducible Samplers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Presents CubeProbeEst, a subcube-conditioning-based estimator of total variation distance between a known and unknown self-reducible sampler, plus a tester built on it, and applies them to test linear-extension samplers built on CNF samplers.
Problem
Testing the correctness of samplers (e.g., linear-extension and perfect-matching samplers) beyond CNF samplers, where prior conditioning-based testers do not apply; a distance estimator for self-reducible samplers with practical sample complexity is needed.
Approach
Uses self-reducibility to simulate subcube conditioning access to an unknown sampler, estimates per-sample probability mass via a chain of conditional marginals each estimated with a Gamma-Bernoulli approximation scheme (GBAS), and averages max(0, 1 - Q(x)/P_hat(x)) to estimate TV distance; the tester thresholds this estimate.
Key results
- The estimator uses O~(n^2/zeta^4) subcube conditional samples and the tester O~(n^2/(eta-eps)^4), the first such distance-estimation bounds in the subcube model.
- Among 90 poset instances, LxtSTS was closest to uniform in 69 instances, while LxtQuickSampler had the largest TV distance in 48 instances.
- LxtQuickSampler's estimated TV distance reaches about 0.31 on bn_pigs_010_1 and is rejected, while LxtSTS is accepted on most instances.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use LxtSTS instead of LxtQuickSampler for linear-extension sampling | linear-extension samplers · 90 poset instances | estimated TV distance from uniform | Helped |
| Use LxtSTS instead of LxtCMSGen for linear-extension sampling | linear-extension samplers · 90 poset instances | estimated TV distance from uniform | Helped |
| Increase the instance dimension | LxtQuickSampler and LxtCMSGen · linear-extension sampling | estimated TV distance from uniform | Hurt |
| Increase the instance dimension | LxtSTS · linear-extension sampling | estimated TV distance from uniform | Mixed |
Surprising findings
- LxtSTS closely matches uniform on most instances, whereas LxtQuickSampler deviates more as dimension grows.
Limitations
- Sample complexity O~(n^2) is above the known Omega(n/log n) lower bound for tolerant testing with subcube conditioning.
- Applies only to self-reducible samplers and cannot handle non-self-reducible samplers.
- Prototype implementation in Python; experiments cover only linear-extension samplers on 90 instances.
Experimental setup
Datasets: poset instances from prior linear-extension sampler benchmarks (avgdeg, bipartite, Bayesian network posets)
Benchmarks: 90 poset instances (avgdeg, bipartite, bayesian network) for linear-extension samplers
Metrics: estimated total variation distance number of samples accept/reject decision
Baselines: Barbarik Teq Flash
Builds on: Barbarik Gamma Bernoulli Approximation Scheme subcube conditioning model
Closest papers by meaning
- Optimal Algorithms for Augmented Testing of Discrete Distributions (NeurIPS 2024 · similarity 0.84)
- Replicable Distribution Testing (NeurIPS 2025 · similarity 0.82)
- A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers (NeurIPS 2024 · similarity 0.82)
- Replicable Uniformity Testing (NeurIPS 2024 · similarity 0.82)
- Swift Sampler: Efficient Learning of Sampler by 10 Parameters (NeurIPS 2024 · similarity 0.81)
- Faster Diffusion Sampling with Randomized Midpoints: Sequential and Parallel (ICLR 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.