ArXiv

Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction

2026-08-06 · 16:54 UTC ·Zonghuan Xu ·1 min read
Authors
Zonghuan Xu
Categories
cs.LG, math.ST
arXiv
https://arxiv.org/abs/2608.06262v1
PDF
https://arxiv.org/pdf/2608.06262v1

Brief

The paper (Zonghuan Xu, arXiv 2026-08-06) studies hypothesis testing with conditional queries on a finite outcome space of size N, characterizing learnability by positive separation in pairwise conditional probabilities. If separation is zero the best worst-case error is 1/2. The author gives a simulator using O(N^2 (T+log(1/ρ))) non-adaptive pair queries to approximate any T-query adaptive policy within ρ TV, and matches this with a family proving a Θ_ε(N^2) adaptivity gap—interaction gives a quadratic, not exponential, query advantage.

Why it matters

Learnability in the conditional-query model on a finite outcome space X (|X| = N) holds iff the two distribution classes have positive separation in their pairwise conditional probabilities; if this separation is zero, the optimal worst-case error equals 1/2 for every finite query budget.

Key details

  • For any T-query adaptive policy and any ρ ∈ (0,1), there is a randomized non-adaptive simulator using O(N^2 (T + log(1/ρ))) predetermined pair queries whose transcript is within ρ in total variation of the adaptive transcript uniformly over the model; a matching family shows a constant-query adaptive test can require Ω_ε(N^2) non-adaptive queries, so the worst-case fixed-error adaptivity gap is Θ_ε(N^2).
Source evidence

Abstract

Model evaluations may fix all tests before observing any responses or select later tests using earlier responses. We study this choice in a conditional-query model on a finite outcome space $\mathcal{X}$ with $|\mathcal{X}|=N$. We first ask which pairs of distribution classes can be reliably distinguished. We then ask how many additional queries are required to match an adaptive tester when all queried events must be fixed in advance. We show that learnability holds if and only if the two classes have positive separation in their pairwise conditional probabilities. When this separation is zero, the optimal worst-case error is exactly $1/2$ at every finite query budget. For any $T$-query adaptive policy and any $ρ\in (0,1)$, we construct a randomized non-adaptive procedure using $O(N^2(T + \log(1/ρ)))$ pair queries chosen before any response is observed. Its simulated transcript is within $ρ$ in total variation of the adaptive transcript, uniformly over all distributions in the model. We also construct a matching family with constant adaptive query complexity and $Ω_\varepsilon(N^2)$ non-adaptive query complexity. Consequently, the worst-case fixed-error adaptivity gap is $Θ_\varepsilon(N^2)$. Thus interaction can reduce the required number of tests by a quadratic factor, but the apparent exponential branching of an interactive evaluation does not yield an exponential query advantage.

Comment: 18 pages