Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

arXiv:2610.11145 · cs.DS, cs.IT, math.IT, stat.ML · Submitted 2026-10-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples".

Tom: The gist: The algorithm and lower bound show that Θ˜ log n ε 2 queries are necessary and sufficient for equivalence testing, demonstrating that the complexity of uniformity, identity,

Jane: First, who's behind it and why it matters.

Paper summary: Tom: Welcome back. We're looking at this paper today titled Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples by Gautam Kamath. Basically, they're looking at distribution testing and they give some really tight bounds for equivalence testing, which is figuring out if two unknown distributions are the same or very close to each other in total variation distance.

Jane: And what's interesting about this work is that their algorithm and their lower bound show that you need Theta of log n epsilon squared queries to solve this problem. They also point out that for uniformity, identity, and equivalence testing with non-adaptive conditional samples, the complexity is all Theta of log n.

Lu: That (n) result is quite significant because it means the query number doesn't grow exponentially with the size of the domain you're testing over, which is usually a major hurdle in these kinds of problems.

Meng: So, what does that mean for someone who might be trying to run this on a real system? Are we talking about something practical or just theoretical complexity?

Lalam: It suggests that even with non-adaptive conditional samples, the fundamental complexity is driven by the number of queries you make, not necessarily the size of the data itself.

Tom: Exactly. The abstract says these results demonstrate that uniformity, identity, and equivalence testing with non-adaptive conditional samples are all Theta of log n. This is a big statement about how much power those specific types of samples give us in this context.

Jane: And the paper gives us a very clear picture by comparing different sampling models. They look at SAMP, COND for adaptive conditional samples, and NACOND for non-adaptive ones like this one.

Meng: I see they compare it to other models too. For instance, equivalence testing under COND only needs Theta of log log n samples compared to Theta of max n root n epsilon squared or n two over three epsilon four over three o samples under SAMP. That's a big difference in how much data you need.

Lu: It shows that conditional access can dramatically reduce the sample complexity for certain problems, but this paper focuses on the non-adaptive side, NACOND, where they establish those tight bounds of Theta of log n epsilon squared queries.

Tom: And their lower bound construction is quite clever because it uses a Paninski style construction with two distributions sharing a random support D. They perturb half the symbols by one plus epsilon and the other half by one minus epsilon to make them hard to distinguish.

Jane: That construction leads to a final requirement that N must be greater than or equal to L times six zero C epsilon squared, which simplifies down to Omega of log n epsilon squared queries, which is exactly what they need for the lower bound.

Meng: So the necessary and sufficient number of queries is this specific term, Theta of log n epsilon squared. It feels concrete enough for an engineer to grasp when setting up a test pipeline.

Lu: And the paper also highlights a gap left by previous work regarding adaptivity, showing that a single round of adaptivity extracts all the power of adaptive conditional samples. This contrasts with NACOND, which still requires Theta of log n queries for equivalence testing.

Tom: It sounds like they're pointing towards how important that ability to choose your next query based on what you've seen is when you need the absolute best performance in these tests.

Jane: They also note a limitation in their analysis regarding adaptivity, suggesting that it remains unclear how many rounds of adaptivity are needed to get from Theta of log n queries down to Theta of log log n queries under the COND model.

Meng: So the real question for me is whether we can practically use this result to design efficient protocols when we only have non-adaptive access, or if we still need that adaptive power they mention.

Lu: The implication here is that for these specific tests under NACOND, the complexity settles at Theta of log n epsilon squared, which provides a strong theoretical benchmark for any future work in this area.

Tom: So to wrap up on this paper, "Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples" by Kamath et al., they show that both the algorithm and the lower bound require Theta of log n epsilon squared queries to distinguish between distributions that are either equal or epsilon far apart in total variation distance.

Jane: This tight understanding across uniformity, identity, and equivalence testing under NACOND is achieved by improving upon previous results for equivalence testing under NACOND from Theta of log twelve n epsilon squared to the near-optimal Theta of log n epsilon squared.

Meng: It’s a solid result for non-adaptive settings because it gives us a concrete query count, and we can use that as a baseline when designing our own tests.

Lu: The future direction they suggest is exploring the trade-off between adaptivity and query complexity, specifically how many rounds of adaptivity are required to reach the optimal bounds under the COND model.

Tom: That's where we head next. We'll be looking at how that adaptivity interacts with the non-adaptive setting, which is a really interesting area for future research in this field.

Conclusion: Tom: So, we're wrapping up on these tight bounds for equivalence testing by Kamath and others. Essentially, they proved that for non-adaptive conditional samples, you need Theta of log n epsilon squared queries to tell if two distributions are equal or just a tiny bit different in total variation distance.

Jane: And what this really means is that for uniformity, identity and equivalence testing in these non-adaptive settings, the query complexity doesn't explode with the size of the problem. It stays at Theta of log n.

Lu: That of log n result is pretty interesting because it shows that even without adaptivity in this non-adaptive conditional setting, you don't need a huge number of queries to get a reliable answer.

Meng: So for someone building a real system, that means the cost scales quite nicely with the size of the distribution you're testing over. It's not hitting exponential walls just because n gets big.

Lalam: From my side, I see this as improving how we can efficiently check if two different models are actually describing the same underlying reality when we only get access to non-adaptive samples.

Tom: Exactly, Lalam. It’s about getting a reliable test with a manageable number of queries, and the numbers they put down for the lower bound construction are pretty solid.

Jane: And they did this by building a distribution where half the symbols are slightly pushed up and half are slightly pushed down to make them hard to tell apart.

Lu: That Paninski style construction is really clever because it directly shows how difficult it is to distinguish those two distributions with just a few queries.

Meng: It's interesting that this complexity holds for uniformity, identity, and equivalence testing all at once under the non-adaptive conditional access model. That’s quite a broad result for such a specific setting.

Lalam: It suggests that the structure of these samples allows us to get strong statistical results without needing to make decisions round by round based on what we've seen so far.

Tom: Yeah, and they did manage to tighten the bound for equivalence testing compared to previous work, moving from something worse down to Theta of log n epsilon squared. That’s a solid improvement on the theoretical side.

Jane: It really shows how much precision we can gain in these tests when we are restricted to non-adaptive conditional samples.

Lu: This result sets a new baseline for what's achievable in this area, and it opens up some interesting avenues for exploring what happens if you introduce adaptivity later on.

Meng: So, the main point is that for non-adaptive access, you have a clear query budget of Theta of log n epsilon squared to settle equivalence testing.

Lalam: And while this is good for non-adaptive work, it doesn't tell us as much about what happens if we get adaptive samples instead.

Tom: That’s the next big question, right? How much better can we do things if we let the AI make decisions based on its previous queries?

Gautam Kamath

cs.DS, cs.IT, math.IT, stat.ML

Submitted: 2026-10-08

Updated: 2026-10-08

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 89/100

The gist: The gist: The algorithm and lower bound show that Θ˜ log n ε 2 queries are necessary and sufficient for equivalence testing, demonstrating that the complexity of uniformity, identity, and

Key concepts

Equivalence Testing: This is a statistical test used to determine if two unknown distributions are either exactly the same or very close to each other, within a specified total variation distance ε. The goal is to decide if the distributions are equivalent or $\varepsilon$-far apart.
Non-Adaptive Conditional Samples (NACOND): This sampling model means that after observing some data, you can only access conditional samples based on that information, but you cannot change your sampling strategy based on the results of those previous queries. This constraint is what the paper analyzes to find the minimum number of queries needed.
Total Variation Distance (dTV): This is a metric used to measure how different two probability distributions are. A small dTV value indicates that the distributions are very similar, while a large value means they are quite distinct. The testing problem aims to distinguish between distributions based on this distance.
Sample Complexity: This refers to the minimum number of data points or queries required by an algorithm to solve a specific statistical problem with a desired level of accuracy. The paper determines that for equivalence testing under NACOND, this complexity is tightly bounded by Θ˜ log n ε 2.

Terminology

Sample Complexity — 9× in this paper · explained in 20 episodes
Adaptivity — 8× in this paper · explained in 1 episode
Combinatorial Optimization — 4× in this paper · explained in 2 episodes
Query Complexity — 2× in this paper · explained in 2 episodes
Accuracy — 1× in this paper · explained in 1 episode
Core — 1× in this paper · explained in 2 episodes

Summary

The gist: The algorithm and lower bound show that Θ˜ log n ε 2 queries are necessary and sufficient for equivalence testing, demonstrating that the complexity of uniformity, identity, and equivalence testing with non-adaptive conditional samples are all Θ(log˜ n) in terms of sample complexity

Key Findings on Sample Complexity

The paper establishes tight bounds for equivalence testing with non-adaptive conditional samples, showing that Θ˜ log n ε 2 queries are both necessary and sufficient for this problem <ref:2610.11145#pg4>. This result implies that the sample complexity for uniformity, identity, and equivalence testing under NACOND is all Θ(log˜ n) <ref:2610.11145#pg4>. Specifically, the table shows that for NACOND, the sample complexity for Equivalence Testing is O˜ log n ε 2 <ref:2610.11145#pg4>.

Comparison Across Sampling Models

The paper compares the required sample complexity across different sampling models: SAMP, COND (adaptive conditional samples), and NACOND (non-adaptive conditional samples) <ref:2610.11145#pg4>. The bounds illustrate a significant reduction in complexity with the use of conditional access; for instance, equivalence testing under COND needs only Θ˜ log log n samples compared to Θ(max n √n ε 2, n 2/3 ε 4/3 o samples under SAMP <ref:2610.11145#pg4>. The paper also notes that NACOND remains exponentially stronger than SAMP for some problems, but the authors show that under NACOND, the sample complexities for uniformity, identity, and equivalence testing are all Θ˜ (log n) <ref:2610.11145#pg4>.

Algorithm Design and Analysis

The paper presents Algorithm 1, which is very similar to Anaconda of Kamath and Tzamos <ref:2610.11145#pg8>. This algorithm diverges by incorporating ideas from the adaptive algorithm for equivalence testing with conditional samples of FJOPS <ref:2610.11145#pg8>. The upper bound proof relies on Lemma 7, which states that if dTV(p, q) ≥ ε, there exists a query set St,l realizing discrepancy at least t with probability at least 9/10 <ref:2610.11145#pg9>. The analysis uses Levin’s work-investment strategy to convert the large expected discrepancy into a reasonable probability of selecting a sufficiently discrepant set <ref:2610.11145#pg10>.

Lower Bound Construction

The lower bound construction involves two distributions, p and q, sharing a random support D of random size <ref:2610.11145#pg7>. When dTV(p, q) ≥ ε, the distributions feature a Paninski-style construction where half of the symbols in p have their probabilities multiplicatively perturbed by 1 + ε and the other half are perturbed by 1 − ε <ref:2610.11145#pg7>. The lower bound proof involves bounding the total variation distance between transcripts, which is shown to be bounded by Cε2 Eω "X N i=1 h(Si(ω) ∩ D) <ref:2610.11145#pg23>. This leads to the final requirement that N ≥ L 60Cε2 = omega log n ε 2 <ref:2610.11145#pg4>.

Techniques Used

The analysis employs several technical tools, including a chi-squared-like discrepancy test derived from FJOPS <ref:2610.11145#pg7>, and a Tail-Discrepancy Lemma <ref:2610.11145#pg8>. The proof of the lower bound utilizes Lemma 3, which bounds the expected intersection size E[h(S ∩ D)] ≤ 20 L <ref:2610.11145#pg29>. Furthermore, the paper uses a moment bound for balanced signs (Lemma 14), which is derived by reducing to the Khintchine inequality. The final step in bounding the total variation distance involves relating it to the expected value of Z, where Eσ,σ′[Z k] ≤ C2 0 k.

Implications for Adaptivity

The paper highlights a significant algorithmic gap left by Kamath and Tzamos [KT19] regarding the power of rounds of adaptivity <ref:2610.11145#pg4>. The authors show that a single round of adaptivity extracts the full power of adaptive conditional samples, contrasting it with NACOND which requires Θ˜ (log n) samples for equivalence testing <ref:2610.11145#pg4>. This suggests that adaptivity is crucial for achieving the optimal complexity bounds in this model <ref:2610.11145#pg4>.

Conclusion on Equivalence Testing

The work concludes by showing that under NACOND, the sample complexities of testing uniformity, identity, and equivalence are all Θ˜ (log n) <ref:2610.11145#pg4>. This tight understanding across all three problems is achieved by improving upon previous results for equivalence testing under NACOND from O˜ log 12 n ε 2 to the near-optimal O˜ log n ε 2 <ref:2610.11145#pg4>. The overall result confirms that Θ˜ log n ε 2 samples are necessary and sufficient for equivalence testing <ref:2610.11145#pg4>.

Future Directions

The paper points out that it remains unclear how many rounds of adaptivity are required to reduce the sample complexity from O˜ log n (optimal under NACOND) to O˜ log log n (optimal under COND) <ref:2610.11145#pg4>. This suggests further investigation into the trade-off between adaptivity and query complexity <ref:2610.11145#pg4>. The analysis also shows that a single round of adaptivity extracts the full power of adaptive conditional samples, which is a key insight for future work <ref:2610.11145#pg4>. The paper also notes that the dependence on n arises under COND, contrasting with SAMP where the sample complexity increases by a poly(n) factor <ref:2610.11145#pg4>.

Testing Primitives

The section on Testing Primitives details Algorithm 2, Test-equal [FJO+15], which employs Poissonization for analysis <ref:2610.11145#pg29>. This algorithm uses a test of Corollary 5 to distinguish between p = q and the existence of a discrepant coordinate <ref:2610.11145#pg30>. The proof of Corollary 5 shows that the test requires O log(n/δ)t samples from each distribution <ref:2610.11145#pg29>. The analysis of the moment bound for random restrictions (Lemma 3) is crucial, as it shows E[h(S ∩ D)] ≤ 20 L. This result is fundamental to bounding the total variation distance between transcripts. The final conclusion on the lower bound shows N ≥ L 60Cε2 = omega log n ε 2 <ref:2610.11145#pg4>. This result is derived from Lemma 3, which bounds the total variation distance between transcripts to Cε2 Eω X N i=1 h(Si(ω) ∩ D). The final conclusion on the lower bound shows N ≥ L 60Cε2 = omega log n ε 2 <ref:2610.11145#pg4>. This result is derived from Lemma 3, which bounds the total variation distance between transcripts to Cε2 Eω X N i=1 h(Si(ω) ∩ D). The final conclusion on the lower bound shows N ≥ L 60Cε2 = omega log n ε 2 <ref:2610.11145#pg4>. This result is derived from Lemma 3, which bounds the total variation distance between transcripts to Cε2 Eω "X N i=1 h(Si(ω) ∩ D).

Improvements for AI systems

Improve equivalence testing in large domains by reducing sample complexity to Θ˜ (log n) samples under non-adaptive conditional sampling (NACOND). This allows AI systems to efficiently determine if two unknown probability distributions are equal or ε-far, a problem previously requiring Θ(max n √n/ε2, n 2/3ε4/3 o samples under SAMP.
Develop an equivalence testing algorithm that leverages the power of one round of adaptivity for conditional samples to achieve O˜ (log n) sample complexity instead of O˜ log12 n ε 2, effectively matching the lower bound derived from uniformity testing under NACOND.
Design a fast, non-adaptive conditional sampling query strategy based on the chi-squared-like discrepancy measure and search over the magnitude of discrepancy to achieve a sample complexity of O˜ log n ε 2 for equivalence testing with NACOND.
Create an AI system capable of efficiently testing uniformity on d-dimensional Boolean hypercubes by utilizing non-adaptive conditional samples, achieving a sample complexity of Θ(log n) samples, significantly faster than the previous exponential dependency on dimension.

Abstract

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 epsilon-far from each other in total variation distance. Our algorithm and lower bound show that Θ (n over epsilon squared) 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 Θ(n).