PaperlayerView exact revision on arXiv

Source-linked AI summary

Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

Gautam Kamath

arXiv:2610.11145v1cs.DScs.ITmath.ITstat.ML

TL;DR

Testing equivalence asks whether two unknown distributions are equal or far apart, and prior non-adaptive conditional-sampling bounds left a gap between the known algorithm and lower bound. This paper establishes tight bounds for the problem, showing ˜Θ(log n) sample complexity and that one round of adaptivity extracts the full power of adaptive conditional samples.

  • Problem

    Prior NACOND algorithms for equivalence testing used O(log^12 n) samples, above the Ω(log n) lower bound, leaving its complexity unresolved.

    Source: §1 · p. 2

  • Method

    The proof bounds transcript total variation using a second-moment argument, then averages over random supports by analyzing query-set intersections.

    Source: §2.1 · p. 5

  • Results

    ˜Θ(log n) samples are necessary and sufficient for equivalence testing with NACOND.

    Source: §2 · pp. 2–3

  • Takeaways & Limitations

    For equivalence testing, a single round of adaptivity extracts the full power of adaptive conditional samples.

    Source: §2 · p. 3

    How many adaptivity rounds reduce equivalence testing from ˜O(log n) NACOND samples to ˜O(log log n) COND samples remains unclear.

    Source: §2 · p. 3

Abstract

from arXiv · show

We study distribution testing with access to non-adaptive conditional samples. Specifically, we give tight bounds for equivalence testing, determining whether two unknown distributions are equal to or $\varepsilon$-far from each other in total variation distance. Our algorithm and lower bound show that $\tilde \Theta\left(\frac{\log n}{\varepsilon^2}\right)$ queries are necessary and sufficient for this problem. These results demonstrate that the complexity of uniformity, identity, and equivalence testing with non-adaptive conditional samples are all $\tilde \Theta(\log n)$.

1 Introduction

Distribution testing asks whether an unknown distribution satisfies a property; conditional sampling lets an algorithm query a distribution restricted to a chosen set. The introduction contrasts the power of adaptive and non-adaptive conditional access and identifies a large gap between prior NACOND bounds for equivalence testing and its lower bound.

1 Introduction

  • Classical distribution-testing bounds can be strongly sublinear in domain size yet remain intractable for extremely large domains; uniformity testing on the d-dimensional Boolean hypercube requires Θ(2^(d/2)) samples.Conditional sampling was introduced to give algorithms stronger access than passive sampling [CFGM13].Source: §1 · pp. 1–2
  • COND samples from a distribution conditioned on a query set, while NACOND requires all query sets to be chosen before any responses are observed.The standard sampling oracle is denoted SAMP.Source: §1 · p. 2
  • Under COND, uniformity and identity testing require ˜Θ(1/ε^2) samples, while equivalence testing requires ˜Θ(log log n) samples [FJO+15] [ACK15b] [CCK24] [AFL26].The introduction contrasts these conditional-sampling costs with substantially larger sample requirements under standard sampling.Source: §1 · p. 2
  • Prior NACOND bounds were ˜O(log n) for uniformity, O(log^2 n) for identity, and O(log^12 n) for equivalence, despite an Ω(log n) lower bound for the latter [KT19] [ACK15b].A recent one-round adaptive COND algorithm for equivalence testing uses ˜O(log n) samples [CCKM24].Source: §1 · p. 2

2 Results and Discussion

The paper establishes necessary and sufficient sample bounds for equivalence testing with non-adaptive conditional samples; under NACOND, uniformity, identity, and equivalence testing each have ˜Θ(log n) complexity. Its techniques adapt discrepancy testing to non-adaptive queries and analyze transcript distances under randomized supports and perturbations.

2 Results and Discussion

  • Under NACOND, uniformity, identity, and equivalence testing each have ˜Θ(log n) complexity, and equivalence testing has necessary and sufficient sample bounds.The theorem distinguishes p = q from dTV(p, q) ≥ ε with probability at least 2/3.Source: §2 · pp. 2–3
  • For identity testing, one round of adaptivity attains the adaptive sample bound, while the number of rounds needed for equivalence testing remains unclear.The paper contrasts this with zero-round NACOND equivalence testing and the optimal COND complexity.Source: §2 · p. 3

2.1 Techniques

  • The algorithm replaces absolute-difference tests with relative discrepancies and searches across discrepancy magnitudes to distribute testing effort across scales.For non-adaptive queries, it chooses ρ randomly rather than estimating ρ_i first, then uses expected discrepancy and Levin’s economical work-investment strategy to obtain a sufficiently discrepant query set.Source: §2.1 · p. 4
  • The lower-bound construction randomizes both support size and perturbations, with the two sources contributing factors of log n and 1/ε^2, respectively.It uses a shared random support and, in the far case, a random balanced partition with opposite multiplicative perturbations for p and q.Source: §2.1 · p. 4
  • The transcript-distance proof controls correlations caused by averaging over one perturbation shared across queries, then averages over random supports to bound query contributions.Queries with |S ∩ D| of 0 or 1 have identical result distributions in the two cases; large intersections contribute relatively little, leaving intersections of constant size as the significant ones.Source: §2.1 · p. 5

AI Disclosure

  • The authors report that an AI model contributed to developing the algorithm and analysis, and that they revised attribution, lemma descriptions, and presentation while taking responsibility for the results.Source: AI Disclosure · p. 5

3 Preliminaries

The preliminaries define the distribution and conditional-sampling models used for equivalence testing, then introduce prior tools for detecting relative and tail-based discrepancies.

3 Preliminaries

  • A conditional sampling oracle returns an independent sample from the distribution conditioned on a queried set, with uniform output if that set has zero probability.Source: §3 · p. 5
  • NACOND requires all query sets to be chosen before responses are observed, unlike COND, whose queries may depend on earlier responses.Source: §3 · p. 6

3.1 Useful Tools from Previous Work

  • The FJOPS tools test relative differences between conditional probabilities and reduce discrete-distribution discrepancy detection to Bernoulli tests on indicators for observed symbols [FJO+15].Source: §3.1 · p. 6
  • The mixture weights w and rescaled differences v satisfy Σ_i w_i|v_i| = dTV(p, q), while tail quantities T and m describe mixture mass and rescaled difference in each tail [FJO+15].Source: §3.1 · p. 7

4 The Algorithm

The algorithm tests conditional distributions on randomly selected query sets, using a relative-discrepancy test and a loop over candidate discrepancy magnitudes. Its query sets are fixed without observing prior responses.

4 The Algorithm

  • Algorithm 1 repeatedly selects random query sets and tests whether the induced conditional distributions have a discrepancy, while all queries remain independent of earlier responses.Source: §4 · p. 7
  • Unlike Anaconda, the algorithm tests relative rather than absolute discrepancy and adds an outer loop over candidate discrepancy magnitudes [KT19].Source: §4 · p. 7
  • The algorithm uses a sequence of decreasing discrepancy thresholds, and its sample complexity depends on the number of thresholds and the threshold-specific repetitions and queries.Source: §4 · pp. 7–8
  • The algorithm chooses a random sampling scale and independently includes each domain element with probability 1/r before querying both distributions on the resulting set.Source: §4 · p. 8

5 Analysis of Algorithm 1

The analysis shows that when the distributions are ε-far, the algorithm samples a query set with sufficiently large discrepancy with probability at least 9/10. It builds this guarantee through a quadratic tail bound, an expected-discrepancy argument, and work investment across thresholds.

5 Analysis of Algorithm 1

  • With probability at least 9/10, some query set sampled by Algorithm 1 has discrepancy F(S) at least its tested threshold when dTV(p, q) ≥ ε.Source: §5 · p. 8

5.1 A Quadratic Tail-Discrepancy Lemma

  • The analysis converts FJOPS’s linear tail-discrepancy lemma into a quadratic version suited to the chi-squared-like test, while aggregating symbols too light for the algorithm’s minimum sampling probability.Source: §5.1 · p. 9

5.2 Expected Discrepancy under Random Restrictions

  • The random-restriction analysis seeks a large expected discrepancy over both the sampling probability and the selected set, then uses that expectation to establish a likely sufficiently discrepant set.Source: §5.2 · p. 10
  • For a symbol in a weight bucket, choosing its associated sampling probability gives probability at least ρ/4 that it is selected and is the heaviest selected symbol.Source: §5.2 · p. 10

5.3 Converting Expectation to Probability with Work Investment

  • Testing O(1/η) random sets separately at threshold η leads to a ˜O(1/η²) sample bound, the square of the target complexity.Source: §5.3 · p. 14
  • Levin’s work-investment strategy tries multiplicatively decreasing discrepancy thresholds with increasing samples per set, incurring only logarithmic overhead and yielding a set with F(S) ≥ t with probability greater than 9/10.Source: §5.3 · pp. 14–15

6 Lower Bound

The lower bound constructs equal and ε-far distributions on a shared random support, then bounds how much non-adaptive query transcripts distinguish them. Randomizing support size across log n scales makes each fixed query informative on only a few scales.

6.1 The Hard Input Distribution

  • The hard instance uses a shared random support: the null distributions are uniform there, while the alternative applies balanced, opposite ε-perturbations.Source: §6.1 · p. 15

6.2 Comparing Answers on a Fixed Support

  • For fixed support, queries intersecting it in 0 or 1 points have identical answer laws; larger overlaps contribute h(m)=1/√m to the transcript-distance bound.Source: §6.2 · p. 16

6.3 Averaging over the Support Size

  • Randomizing support size across log n scales limits how often any fixed query is informative, keeping transcript distance small unless enough queries are used.Source: §6.3 · p. 20

6.4 Completing the lower bound

  • The transcript-TV bound and the tester’s required 1/3 separation imply N = Ω(log n/ε²) queries for the non-adaptive lower bound.Source: §6.4 · p. 22

A.1 Test-equal Pseudocode

Test-equal uses Poissonized sampling to compare two Bernoulli distributions. Its analysis relies on independent symbol counts and accounts for the rare event that the sample budget is exceeded.

A.1 Test-equal Pseudocode

  • Poissonization draws a random Poi(m) sample count, making each symbol’s occurrence count independently distributed as Poi(mα).Source: §A.1 · p. 28
  • If Poissonization exceeds the fixed sample budget, the procedure answers arbitrarily and folds any resulting error into failure probability δ.Source: §A.1 · p. 28
  • The pseudocode draws independent Poi(m) counts for the two distributions, with m=O(1/t), then samples each distribution accordingly.Source: §A.1 · p. 28

A.2 Proof of Corollary 5

The corollary’s procedure samples both distributions, runs Test-equal on observed symbols with a shared fresh sample batch, and returns different if any symbol test does.

A.2 Proof of Corollary 5

  • The procedure runs Test-equal on each observed symbol, of which there are at most 2d, using parameters t and δ′=δ/(2d).Source: §A.2 · p. 28
  • A fresh batch of samples is reused across all symbol tests, and the procedure returns different if any test does.Source: §A.2 · p. 28
  • If p=q, a union bound gives correct output with probability at least 1−δ; under the alternative, the discrepant-symbol test returns different with probability at least 1−δ/2−δ/(2d).Source: §A.2 · p. 28

B A Moment Bound for Random Restrictions

The moment-bound proof rescales the random sum by ρ and expands its powers, grouping terms according to whether indices coincide.

B A Moment Bound for Random Restrictions

C A Moment Bound for Balanced Signs

The section proves a moment bound for balanced signs, where the balance constraint creates dependence; it handles that dependence by conditioning on a random perfect matching and applying the Khintchine inequality.

C A Moment Bound for Balanced Signs

  • The challenge in the lemma is dependence between signs introduced by the balance requirement; without that requirement, the bound would be recognizable as Khintchine’s inequality.The cited comparison is to independently sampled Rademacher signs.Source: C A Moment Bound for Balanced Signs · p. 30
  • A uniformly random perfect matching with independently assigned opposite signs to each pair produces a sign vector satisfying the lemma’s balanced-sign conditions.The construction reduces the proof to a Rademacher sum conditional on the matching.Source: C A Moment Bound for Balanced Signs · pp. 29–30
  • Conditional on a fixed matching, each pair contributes ±(a_u−a_v) with independent uniform sign, so the Khintchine inequality applies to the resulting sum.The signs are independent across pairs, not across all elements of D.Source: C A Moment Bound for Balanced Signs · p. 30
  • The proof raises the conditional moment bound to the kth power and notes that the bound holds pointwise for every matching.Source: C A Moment Bound for Balanced Signs · p. 30
Loading 2610.11145v1…