PaperlayerView exact revision on arXiv

Source-linked AI summary

Equivalence Testing: The Power of Bounded Adaptivity

Diptarka Chakraborty, Sourav Chakraborty, Gunjan Kumar, Kuldeep S. Meel

arXiv:2403.04230v1cs.DS

TL;DR

Equivalence testing asks whether two unknown distributions are equal or far apart, but the query-efficient COND tester is sequential and known non-adaptive testers use Õ(log^12 n) queries. The paper presents a one-round adaptive tester with Õ(log n) sample complexity. Its conclusion also notes large constants and a worsened dependency on ε compared with.

  • Problem

    The query-optimal COND equivalence tester is sequential, while known non-adaptive testing requires Õ(log^12 n) queries.

    Source: §1 · p. 2, §3 · p. 3

  • Method

    EquivTester samples points and random subsets, estimates conditional probabilities and tail probabilities, and parallelizes the remaining conditional samples once subsets are fixed.

    Source: §4.2 · p. 5, §4.1 · p. 5

  • Results

    Õ(log n) sample complexity is achieved by a one-round adaptive tester, which rejects ε-far distributions with probability at least 2/3.

    Source: §4.3 · p. 8, §5 · p. 12

  • Takeaways & Limitations

    The paper concludes that limited adaptivity can significantly reduce sample/query complexity; a slight modification gives a fully adaptive Õ(log log n) algorithm matching the best bound in that setting.

    Source: §5 · p. 12

    The algorithm has large constants and a worsened dependency on ε compared with.

    Source: §5 · p. 12

Abstract

from arXiv · show

Equivalence testing, a fundamental problem in the field of distribution testing, seeks to infer if two unknown distributions on $[n]$ are the same or far apart in the total variation distance. Conditional sampling has emerged as a powerful query model and has been investigated by theoreticians and practitioners alike, leading to the design of optimal algorithms albeit in a sequential setting (also referred to as adaptive tester). Given the profound impact of parallel computing over the past decades, there has been a strong desire to design algorithms that enable high parallelization. Despite significant algorithmic advancements over the last decade, parallelizable techniques (also termed non-adaptive testers) have $\tilde{O}(\log^{12}n)$ query complexity, a prohibitively large complexity to be of practical usage. Therefore, the primary challenge is whether it is possible to design algorithms that enable high parallelization while achieving efficient query complexity. Our work provides an affirmative answer to the aforementioned challenge: we present a highly parallelizable tester with a query complexity of $\tilde{O}(\log n)$, achieved through a single round of adaptivity, marking a significant stride towards harmonizing parallelizability and efficiency in equivalence testing.

1 Introduction

The introduction frames equivalence testing as deciding whether two unknown distributions are equal or ε-far in total variation, and motivates conditional sampling as a more flexible query model. It studies bounded-round adaptivity as a way to balance query efficiency with parallelization.

1 Introduction

  • Conditional sampling allows queries conditioned on arbitrary domain subsets, addressing restrictions of ordinary sampling for some testing problems.The passage notes strong polynomial-in-domain-size sample-complexity lower bounds for some properties under SAMP.Source: §1 · p. 2
  • Equivalence testing asks whether two unknown distributions are equal or ε-far in total variation distance.The broader goal of distribution testing is to assess properties while minimizing queries.Source: §1 · p. 2
  • The known query-optimal COND tester is sequential, while non-adaptive testers can issue multiple queries simultaneously.A non-adaptive tester chooses queries from the domain size and internal randomness, not previous responses.Source: §1 · p. 2
  • The paper initiates bounded-round adaptivity for equivalence testing and presents a query-efficient one-round adaptive tester.The approach permits a limited number of adaptive stages or rounds.Source: §1 · p. 2

2 Notations and Preliminaries

The preliminaries establish the paper's domain and distribution notation, define conditional queries, and specify the guarantees and query count for a one-round adaptive tester. They also introduce concentration and distance terminology used in the analysis.

2 Notations and Preliminaries

  • The paper uses [n] for the domain {1, 2, ..., n}, D(i) for point mass, and D(S) for mass on a subset; ε-far refers to variation distance exceeding ε.A ±γ estimate lies within γ of the target quantity.Source: §2 · p. 2
  • A COND query on S returns an element according to D conditioned on S when D(S)>0, and uniformly from S when D(S)=0.The notation for this query is COND_D(S).Source: §2 · p. 3
  • A one-round tester chooses its first query subsets before receiving answers, then chooses a second set of subsets based on first-round answers.It outputs after the two rounds of queries.Source: §2 · p. 3
  • The tester accepts identical distributions and rejects distributions at least ε apart, each with probability at least 2/3; its query complexity is 2(q1+q2).Source: §2 · p. 3
  • The analysis invokes an additive Chernoff bound for iid Boolean random variables with common expectation p.The passage states the setup but not the bound's inequality.Source: §2 · p. 3

3 Related Work

Prior work established query-efficient conditional testing but left a parallelization challenge for equivalence testing. The paper's one-round approach targets the gap between the high query complexity of non-adaptive testing and the sequential optimal tester.

3 Related Work

  • The COND model reduces equivalence testing to Õ(log log n) samples, a bound shown optimal, but the optimal tester is sequential.The sample bound is attributed to and its optimality to.Source: §3 · p. 3
  • [KT19] introduced a non-adaptive equivalence tester requiring Õ(log^12 n/ε^2) queries; the best-known lower bound for non-adaptive testers is Ω(log n).Source: §3 · pp. 3–4
  • Allowing one adaptive round brings the paper toward O(log n) query complexity for classical equivalence testing.Source: §3 · p. 4
  • Unlike 's subset-only comparisons, the paper uses tuples (i,S) as certificates of separation, reducing queries but making its adaptivity incomparable.The approaches share construction of sets of varying sizes, but differ in description and analysis.Source: §3 · p. 4

4 An Efficient One-Round Adaptive Algorithm

The section presents a one-round adaptive conditional-sampling tester for equivalence testing with O(log n) queries and outlines a proof that the sampled pair distinguishes the distributions with probability at least 4/5.

4 An Efficient One-Round Adaptive Algorithm

  • ˜O(log n) queries suffice for a one-round adaptive tester that distinguishes P = Q from dTV(P, Q) ≥ ε with probability at least 2/3.The tester uses COND access to P and Q.Source: §4 · p. 4

4.1 High-Level Overview

  • Geometrically scaled random sets provide a set whose P-mass is comparable to a sampled point’s mass; conditional-probability comparisons detect differences, while tail-probability estimates catch cases where set masses fail to concentrate.After the sets are fixed, the remaining conditional samples can be drawn in parallel.Source: §4.1 · p. 5

4.2 Algorithm Description

  • EquivTester samples O(1/ε) points from P, constructs random sets at inclusion probabilities from 1 to 1/n, and applies EstProb and EstTail to each point-set pair.To make the tester one-round adaptive, it makes the initial queries simultaneously, then makes all remaining conditional queries simultaneously using their outcomes.Source: §4.2 · pp. 5–6

4.3 Technical Analysis

  • P = Q is accepted with probability at least 1−o(1), and when dTV(P, Q) ≥ ε the tester rejects with probability at least 2/3.The analysis uses a union bound for the acceptance case and shows that a distinguisher causes rejection with high probability.Source: §4.3 · pp. 8–9

Proof of Lemma 4.9

  • For each sampled point i* in the set T, with probability at least 4/5 there is a set S* such that (i*, S*) distinguishes P and Q.The proof selects the set’s inclusion probability in terms of P(i*).Source: §4.3 · p. 9, Proof of Lemma 4.9 · p. 10
  • For S* formed by picking each element in [n] with probability t*, the text states the goal is to prove that (i*, S*) distinguishes P and Q with probability at least 4/5.Defining Good = Good1 ∧Good2, the text uses a union bound to obtain Pr[Good] ≥4/5.Source: Proof of Lemma 4.9 · pp. 10–11
  • The proof seeks concentration of R(D, i*, S*) and D(S*) for both distributions to derive concentration inequalities for TP(D, i*, S*).These concentration bounds form part of the Good event used in the proof.Source: Proof of Lemma 4.9 · p. 11
  • Assuming Good, the hypothesis that (i*, S*) is not a distinguisher implies Q(S*) > P(S*), which is used with Lemma 4.8 to obtain a contradiction.The proof therefore concludes that (i*, S*) is a distinguisher.Source: Proof of Lemma 4.9 · p. 11

5 Conclusion

The paper presents a one-round adaptive conditional-sampling tester for equivalence testing with sample complexity ˜O(log n), and reports a fully adaptive modification with complexity ˜O(log log n). It identifies large constants and worsened dependence on ε relative to as limitations.

5 Conclusion

  • ˜O(log n) sample complexity is achieved by a one-round adaptive equivalence tester in the conditional sampling model.The conclusion says limited adaptivity can significantly reduce sample/query complexity.Source: §5 · p. 12
  • A slight modification gives a fully adaptive tester with ˜O(log log n) sample complexity, matching the best bound in that setting.Source: §5 · p. 12
  • Large constants and worsened dependence on ε relative to limit the algorithm.Reducing ε-dependence while maintaining ˜O(log n) dependence on n is identified as an open direction.Source: §5 · p. 12

A MISSING PROOFS

These missing proofs invoke concentration bounds to analyze estimators and establish claims 4.10–4.12. They also state lower bounds for R(P, i*, [n]) and R(Q, i*, [n]).

A MISSING PROOFS

  • Additive Chernoff bounds are used to analyze EstProb and EstTail estimator outputs.The proof identifies the indicator variables for samples j_k=i as iid, with probability D(i).Source: A MISSING PROOFS · p. 16
  • The proof of Claims 4.10, 4.11, and 4.12 uses a concentration inequality derived from Bernstein’s inequality.Source: A MISSING PROOFS · pp. 16–17
  • The proof states that it will establish lower bounds for R(P, i*, [n]) and R(Q, i*, [n]).Source: A MISSING PROOFS · p. 16

Proof of Claim 4.10

The proof of Claim 4.10 uses indicator variables for membership in S* and applies a concentration lemma to bound the aggregate R values.

Proof of Claim 4.10

  • The proof represents membership of each j in S* with an indicator random variable.Source: Proof of Claim 4.10 · p. 17
  • With probability at least 1−1/e^100, the proof bounds each R(D, i*, j) by 2D(i*) before applying Lemma A.1.It applies the lemma with G=[n], r_j=R(D, i*, j), r_0=t*, r_max=2D(i*), and λ=1.Source: Proof of Claim 4.10 · p. 17
  • The final inequality uses Q(i*)<P(i*) and upper bounds on P(i*) involving t*ε^3/c^2 and 32ε^3/L.The proof specifies c=1000 and L=10^15.Source: Proof of Claim 4.10 · p. 17

Proof of Claim 4.11

The proof of Claim 4.11 applies a sampling concentration lemma to a set of elements whose P-mass is at most P(i*), then bounds the sampled masses under P and Q.

Proof of Claim 4.11

  • For G={j∈[n]: P(j)≤P(i*)}, the proof applies Lemma A.1 with sampling probability t*, maximum weight P(i*), and P(G)≤1.The proof states that the relevant mass is at least 3t*ε/10, citing Lemma 4.8.Source: Proof of Claim 4.11 · p. 17
  • The proof gives E[P(S*)]=E[Q(S*)]=t* for the sampled set S*.Source: Proof of Claim 4.11 · p. 17
  • Markov’s inequality bounds each probability Pr[P(S*)>200t*] and Pr[Q(S*)>200t*] by 1/200.A union bound is then used to conclude the claim.Source: Proof of Claim 4.11 · p. 17

Proof of Claim 4.12

The proof of Claim 4.12 proceeds by considering two cases and bounding differences between the distributions’ R quantities under the event Good.

Proof of Claim 4.12

  • Under Good, the proof bounds the difference between R(P, i*, S*) and R(Q, i*, S*) using the triangle inequality.The subsequent inequalities invoke Claim 4.10 and inequalities (2), (7), and (8).Source: Proof of Claim 4.12 · pp. 17–18
  • The proof recalls TP(D, i*, S*) = R(D, i*, S*)/D(S*) and divides the argument into two cases.Source: Proof of Claim 4.12 · p. 18
  • The argument concludes that P(S*) − Q(S*) < 90εP(S*)/c, using R(P, i*, [n]) ≥ ε/9.The bound follows from R(P, i*, S*) ≥ t*R(P, i*, [n])(1 − 8/c), together with the preceding inequalities.Source: Proof of Claim 4.12 · p. 19

B An ˜O(log log n)-query fully adaptive algorithm

A slight modification gives a fully adaptive algorithm with query complexity ˜O(log log n), matching the best-known bound in that setting. Binary search reduces the search over possible t values, but requires adaptivity at each iteration.

B An ˜O(log log n)-query fully adaptive algorithm

Loading 2403.04230v1…