Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction
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 𝒳 with |𝒳|=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 ρ∈ (0,1), we construct a randomized non-adaptive procedure using O(N2(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 Ωε(N2) non-adaptive query complexity. Consequently, the worst-case fixed-error adaptivity gap is Θε(N2). 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.
Related
- Combinatorial Characterizations of the Learnability of Conditional Distributions
- Work in progress: A Lean-verified conditional reduction of periodic Navier-Stokes regularity on T^3 to a single integrability hypothesis
- A Model of Multiple Hypothesis Testing
- Principal-Agent Hypothesis Testing
- Manifold Hypothesis: Conditional Certificates and Consistent Intrinsic Dimension Estimation
BibTeX
@misc{xu2026hypothesis,
title = {{Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction}},
author = {Zonghuan Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.06262},
eprint = {2608.06262},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.06262},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction
AU - Zonghuan Xu
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2608.06262
UR - https://arxiv.org/abs/2608.06262
AB - 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 𝒳 with |𝒳|=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 ρ∈ (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 Ω_ε(N^2) non-adaptive query complexity. Consequently, the worst-case fixed-error adaptivity gap is Θ_ε(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.
ER -