Source-linked AI summary
On the Power of Conditional Samples in Distribution Testing
Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah
TL;DR
Testing properties of huge-domain distributions seeks a few-sample distinction between property members and distributions far in variation distance. This paper studies conditional sampling, finding poly(log n) tests for label-invariant properties but an Ω(n)-sample lower bound for some property.
Problem
For huge discrete domains, distribution-property testing seeks to distinguish property distributions from distributions far in variation distance using few samples.
Source: §1 · p. 2Method
The paper studies distribution-property testers using conditional samples and examines how adaptivity affects their power.
Source: §1 · pp. 2–3Results
Conditional-sample complexity ranges from poly(log n) for any label-invariant property to Ω(n) for a hard property; uniformity lacks a constant-sample non-adaptive test.
Source: §1 · p. 3Takeaways & Limitations
Conditional sampling is not equally powerful across properties, and adaptivity matters for uniformity testing.
Source: §1 · p. 3Reported upper bounds hide a log(δ^-1) factor, and lower bounds assume fixed, not very small, ε.
Source: §1.2 · p. 4
Abstract
from arXiv · showhide
In this paper we define and examine the power of the {\em conditional-sampling} oracle in the context of distribution-property testing. The conditional-sampling oracle for a discrete distribution $\mu$ takes as input a subset $S \subset [n]$ of the domain, and outputs a random sample $i \in S$ drawn according to $\mu$, conditioned on $S$ (and independently of all prior samples). The conditional-sampling oracle is a natural generalization of the ordinary sampling oracle in which $S$ always equals $[n]$. We show that with the conditional-sampling oracle, testing uniformity, testing identity to a known distribution, and testing any label-invariant property of distributions is easier than with the ordinary sampling oracle. On the other hand, we also show that for some distribution properties the sample-complexity remains near-maximal even with conditional sampling.
1 Introduction
Distribution-property testing asks whether samples come from a distribution with a property or one far in variation distance from every such distribution, while large domains make sublinear sample costs important. The paper studies subset-conditioned sampling and finds both polylogarithmic testing for all label-invariant properties and an Ω(n)-sample hard property, with adaptivity mattering for uniformity.
1 Introduction
- Distribution-property testing distinguishes distributions with a property from those far in variation distance from every distribution having it.The traditional model provides access only through independent samples, and the goal is to use as few as possible.Source: §1 · p. 2
- Testing properties on huge discrete domains motivates sublinear sample complexity, while prior ordinary-sampling requirements could still be very large.A stronger prior oracle also allowed exact probability-weight queries for domain elements.Source: §1 · p. 2
- The conditional-sampling oracle returns a sample from the unknown distribution conditioned on a specified subset of its domain.For an element in the subset, its conditional probability is its original probability divided by the total probability mass of the subset.Source: §1 · p. 2
- Any label-invariant property of distributions can be tested with poly(log n) conditional samples.The paper identifies this as its most general result.Source: §1 · p. 3
- Some distribution properties still require at least Ω(n) conditional samples to test.Source: §1 · p. 3
- Uniformity testing with conditional samples cannot be done non-adaptively with a constant number of samples.The introduction contrasts this with the much better sampling complexity possible using adaptive conditional sampling.Source: §1 · p. 3
1.1 Some motivating examples
The examples illustrate conditional sampling in lottery-machine testing, asymmetric communication, and political polling.
Lottery machines
- For lottery fairness, conditional sampling permits testing uniformity with O(1) activations when each ball’s drawing probability depends only on its physical characteristics.The number of activations has polynomial dependence on ε and logarithmic dependence on the confidence parameter; label-invariant properties can be tested with poly(log |B|) activations.Source: Lottery machines · pp. 3–4
Asymmetric communication scenarios
- When a data-holder can produce conditional samples, asymmetric communication can reduce the information sent from that holder for properties easier to test conditionally.The example assumes the data-holder has access to samples from the unknown distribution.Source: Asymmetric communication scenarios · p. 4
Political polls
- Political polling commonly samples separately from groups formed by shared traits before integrating the results.Source: Political polls · p. 4
1.2 Informal description of results
Conditional sampling supports efficient distribution testing, with adaptive and non-adaptive methods using different conditioning-set strategies. The results span uniformity and identity testing, general label-invariant properties, and lower bounds showing that adaptivity helps in some settings while some properties remain hard.
Conditioned upon sets
- Adaptive algorithms condition on constant-sized sets or intervals, whereas non-adaptive algorithms appear to require the full generality of conditioning sets.The stated upper bounds hide a log(δ^-1) factor, and the lower bounds assume fixed, not very small, ǫ.Source: Conditioned upon sets · p. 4, §1.2 · p. 4
Adaptive testing
- Adaptive tests handle uniformity and identity to distributions close to uniform in ℓ∞ with poly(ǫ^-1) conditional samples, and known-distribution identity with poly(log⋆n, ǫ^-1) samples.The known-distribution identity result combines uniformity testing, bucketing, and a recursive argument.Source: Adaptive testing · p. 5
- Adaptive conditional sampling tests any label-invariant property with poly(log n, ǫ^-1) samples and can reconstruct a distribution up to permutation using poly(log n, ǫ^-1, log(δ^-1)) samples.The methods also construct an explicit persistent sampler that simulates samples from a distribution close to the unknown one and supports exact probability queries.Source: Adaptive testing · p. 5
Non-adaptive testing
- Non-adaptive conditional sampling tests uniformity and identity to a known distribution with poly(log n, ǫ^-1) samples.For uniformity, the method uses bucketing and samples random sets intended to capture elements in a relatively equal-probability portion of the domain.Source: Non-adaptive testing · p. 5
Lower bounds
- Some properties still require Ω(n) conditional samples, while a label-invariant property requires Ω(√log log n) samples regardless of adaptivity.Non-adaptive uniformity testing also requires Ω(log log n) samples for some fixed ǫ > 0.Source: Lower bounds · pp. 5–6
About the gaps in the bounds
The authors identify unresolved gaps in several lower bounds and conjecture that non-adaptive uniformity testing has complexity closer to logarithmic in n.
About the gaps in the bounds
- The authors expect non-adaptive uniformity testing to require complexity closer to logarithmic in n than their lower bound establishes.They also believe the adaptive lower bound for general label-invariant properties is too low and suggest examining to find properties hard to test with ordinary samples.Source: About the gaps in the bounds · p. 6
1.3 Related work
The related work includes independent formulation of conditional distribution testing and overlapping results on uniformity and identity testing. Cannone et al. also study distance estimation and structured conditioning, including interval queries.
Related work
- Cannone et al. independently formulated distribution testing with conditional samples; some results overlap, while most emphasize different directions.Source: §1.3 · p. 6
Uniformity
- For uniformity, Cannone et al. give a ˜O(ǫ^-2) upper bound and an Ω(ǫ^-2) lower bound using sets of size 2.Source: §1.3 · p. 6
Identity to a known distribution
- For identity to a known distribution, their arbitrary-set upper bound is ˜O(ǫ^-4), while conditioning on pairs has a separate upper bound.The passage gives no value for the pair-conditioned upper bound.Source: §1.3 · p. 6
Identity between two unknown distributions
- For identity between two unknown distributions, Cannone et al. use an approximate EVAL oracle and report upper bounds of ˜O(ǫ^-4 log^5 n) for arbitrary sets and ˜O(ǫ^-21 log^6 n) for pairs.The approximate EVAL oracle estimates element probabilities but may fail on a small fixed subset.Source: §1.3 · pp. 6–7
Other conditional-sampling settings
- Cannone et al. estimate distance from uniformity with ˜O(ǫ^-20) pair-conditioned samples and study interval-conditioned testing, with upper bound ˜O(ǫ^-3 log^3 n) and a lower bound stated in the text.The paper notes that the distance-estimation problem is label-invariant and that their algorithm outperforms its general label-invariant tester; its persistent sampler uses dyadic intervals.Source: §1.3 · p. 7
2 Preliminaries
The preliminaries define conditional sampling and the testing criteria, then recall identity-testing and bucketing tools used in the paper. The model distinguishes adaptive from non-adaptive choice of conditioned sets.
2.1 The conditional distribution testing model
- A conditional oracle returns an independent sample from the unknown distribution conditioned on a submitted subset of the domain.For a set with zero probability mass, the model assumes the oracle returns a uniformly drawn member of that set.Source: §2.1 · p. 7
- A tester must accept distributions with the property and reject those ǫ-far in variation distance, each with probability at least 1 − δ.Non-adaptive testers choose all query sets before sampling; adaptive testers may base each set on earlier samples.Source: §2.1 · pp. 7–8
2.2 Tools from previous works
- The cited identity tester compares an unknown distribution with a known one using ordinary samples, with complexity ˜O(√n poly(ǫ^-1) log(δ^-1)).It accepts equality and rejects when the distributions are ǫ-far, with error probability at most δ.Source: §2.2 · p. 8
Bucketing
- Bucketing partitions a domain into classes where restrictions of the target distribution are nearly uniform, supporting comparisons within classes and across their coarsening.The cited lemma bounds the restricted distributions' ℓ∞ distance from uniform by ǫ/n; another lemma combines within-class and coarsened-distribution distances.Source: Bucketing · p. 9
- The preliminaries define restriction as conditioning with a changed domain and coarsening as assigning each partition block its total probability mass.Source: Bucketing · p. 9
3 Adaptive testing for uniformity and identity
Adaptive conditional sampling yields a uniformity tester whose sample complexity is independent of n, and an identity tester with complexity polynomial in log⋆ n, ǫ⁻¹, and log(δ⁻¹).
3.1 Testing uniformity
- poly(ǫ⁻¹, log(δ⁻¹)) conditional samples suffice to test uniformity independently of n.The near-uniformity result also tests identity to a known µ when ∥µ − U_n∥∞ < ǫ/100n.Source: §3.1 · pp. 10–11
- The uniformity tester samples from µ′ and chooses random domain indices, then checks identity on their union.It invokes a closeness tester on a set of size 2k, where k = (6/ǫ) log(δ⁻¹).Source: §3.1 · p. 10
3.2 Testing identity to a known distribution
- poly(log⋆ n, ǫ⁻¹, log(δ⁻¹)) conditional samples suffice for adaptive identity testing against a known distribution.The algorithm bounds recursion to at most 2 log⋆(n) levels.Source: §3.2 · pp. 11–12
4 Non-adaptive testing for uniformity and identity
The paper shows that non-adaptive conditional testers can still improve on testers without conditional sampling, giving poly(log n, ǫ⁻¹, log(δ⁻¹)) sample bounds for uniformity and identity testing.
4 Non-adaptive testing for uniformity and identity
- Non-adaptive conditional testers can still beat testers without conditional sampling, despite having to choose their conditioned sets in advance.The section establishes this for uniformity and identity testing.Source: §4 · p. 13
4.1 Testing uniformity
- poly(log n, ǫ⁻¹, log(δ⁻¹)) non-adaptive conditional samples suffice to test uniformity.The near-uniformity result extends to identity with known µ when ∥µ − U_n∥∞ < ǫ/8n.Source: §4.1 · pp. 13–14
4.2 Testing identity to a known distribution
- poly(log n, ǫ⁻¹, log(δ⁻¹)) non-adaptive conditional samples suffice to test identity to a known distribution.The identity tester combines bucket-level near-uniformity tests with an identity test on bucket masses.Source: §4.2 · pp. 15–16
5 Explicit persistent samplers
The paper uses conditional samples to build explicit persistent samplers that report sampled-point probabilities while simulating repeated samples from one close distribution.
5 Explicit persistent samplers
- The persistent sampler returns each sampled index with its probability under a single sampled distribution and simulates up to s independent samples from it.The constructed sampler uses adaptive conditional samples to produce a distribution close to µ.Source: §5 · p. 16
5.1 Ratio trees and reconstituted distributions
- A binary ratio tree estimates left-versus-right subtree mass at each split and reconstructs a distribution that is 4ǫ-close to µ.Each ratio estimate uses 2ǫ⁻² log(δ⁻¹) non-adaptive conditional samples.Source: §5.1 · pp. 16–18
5.2 Distribution samplers and learning
- The persistent sampler is valid for the (ǫ, δ/s log n)-condensation of µ and uses 25 · ǫ⁻⁴ log⁵ n · log(sδ⁻¹ log n) adaptive conditional samples.It supports s runs that simulate samples from the same distribution while reporting their probabilities.Source: §5.2 · p. 19
6 Testing any label-invariant property
Adaptive conditional sampling lets testers handle every label-invariant distribution property with poly(log n, ε^-1, log(δ^-1)) samples. The section derives this from learning a distribution up to relabeling, using bucket approximations and a trimming sampler.
6 Testing any label-invariant property
- Every label-invariant property can be tested adaptively with poly(log n, ε^-1, log(δ^-1)) conditional samples.The tester accepts distributions ε/2-close to the property and rejects those ε-far from it, each with probability at least 1−δ.Source: §6 · p. 20
- The learning result outputs a distribution that, with probability at least 1−δ, is ε-close to some permutation of the unknown distribution.It uses poly(log n, ε^-1, log(δ^-1)) adaptive conditional samples.Source: §6 · p. 20
- The same sample bound tests whether two unknown distributions are identical up to relabeling.Source: §6 · p. 20
6.1 Bucketing and approximations
- When exact bucket sizes are known, assigning tentative probabilities by bucket yields a distribution 2ε-close to some permutation of the original.The bucket sizes summarize how many domain elements fall into each probability range.Source: §6.1 · p. 21
- If estimated bucket weights satisfy the stated conditions, rounding their bucketization is well-defined and the resulting tentative distribution is within 4ε of the unrounded one, after permutation.Source: §6.1 · p. 21
6.2 From bucketing to learning
- Ordinary sampling does not estimate the needed bucket weights precisely enough, so the construction uses an explicit persistent sampler to simulate an approximate distribution.The section notes that the repetition strategy for logarithmic dependence on δ^-1 may not work when the goal is to obtain the distribution itself.Source: §6.1 · p. 22, §6.2 · p. 23
- The Distribution Approximation algorithm returns a distribution ε-close to a permutation of μ with probability at least 1−δ, using at most ˜O(ε^-8 log^7 n log^2(δ^-1)) conditional samples.Source: §6.2 · p. 23
7 Lower bounds for label invariant properties
This section develops lower bounds for label-invariant distribution testing with conditional samples, including non-adaptive uniformity testing and adaptive testing of label-invariant properties. It reduces testers to core forms and uses indistinguishability arguments based on closely matching acceptance probabilities.
7 Lower bounds for label invariant properties
- The section considers lower bounds for non-adaptive uniformity testing and adaptive testing of whether a distribution is uniform on a subset of a specified size.The opening identifies these as the section’s two lower-bound targets.Source: §7 · p. 24
7.1 Preliminary definitions
- Label-invariant non-adaptive and adaptive testers can each be converted to corresponding core testers with the same sample complexity.This reduction supports the lower-bound analysis by restricting attention to core algorithms.Source: §7.1 · pp. 25–26
7.2 Uniformity has no constant sample non-adaptive test
- Uniformity testing requires at least Ω(log log n) non-adaptive conditional samples for some fixed ε.The theorem establishes the lower bound for conditional sampling.Source: §7.2 · p. 27
- For a deterministic non-adaptive core algorithm, the even uniblock distribution induces a configuration distribution o(1)-close to the uniform distribution’s, so their acceptance probabilities are o(1)-close.Source: §7.2 · p. 29
7.3 A label-invariant property with no constant sample adaptive test
- Any adaptive tester for some label-invariant property requires Ω(√(log log n)) conditional samples for some ε.The property is being equal to a U-distribution that can arise from the even uniblock distribution over distributions.Source: §7.3 · p. 29
- With 2^√(log log n) conditional samples, testers cannot distinguish the even and odd uniblock distributions with success probability above o(1).The odd distribution’s outcomes are always 1/2-far from those of the even distribution.Source: §7.3 · p. 33
- The variation distance between the resulting leaf distributions bounds the difference in conditional probabilities of reaching an accepting leaf by o(1).This bound holds conditioned on a 1−o(1) probability event.Source: §7.3 · p. 33
- The unconditional probabilities of reaching an accepting leaf under μ and μ′ differ by only o(1).The conditional bound carries over because the conditioning event occurs with probability 1−o(1).Source: §7.3 · p. 33
- Thus, the algorithm cannot distinguish between the two corresponding distributions over distributions.Source: §7.3 · p. 33
8 A lower bound for testing general properties of distributions
Some distribution properties require Ω(n) conditional samples to test. The proof reduces hard binary-string properties to distribution properties and simulates conditional samples using a bounded-expected-query sampler.
8 A lower bound for testing general properties of distributions
- Some properties on [n] require Ω(n) conditional samples, via a reduction from hard n/2-bit string properties.Source: §8 · p. 34
8.1 The reduction lemma
- If ϵ-testing P requires q queries, then ϵ/2-testing P_P requires at least q/100 conditional samples.Source: §8.1 · p. 35
Sampler
- The sampler queries input bits to emulate conditional draws, with at most 3 expected rounds per draw and a query cap whose failure probability is below 1/15.Source: Sampler · p. 35