研究交互式测试如何减少判断分布差异所需的查询次数。
Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction
- 通过条件查询模型分析可区分性，关键在两类分布的条件概率是否正分离。
- 非自适应测试需约 $N^2(T + /log(1/ρ))$ 次查询才能逼近自适应效果。
- 交互可节省至多平方级查询，但无指数级优势，适合理论验证场景。
模型评估可在观察任何响应前固定所有测试，或根据前期结果动态选择后续测试。本文研究在有限结果空间 $\\'mathcal{X}\\'$（$|\\'mathcal{X}\\'|=N$）上的条件查询模型中，这一选择的影响。首先探讨哪类分布对可被可靠区分；其次分析在所有查询事件必须预先固定时，需额外多少查询才能匹配自适应测试者。我们证明：当且仅当两类分布的成对条件概率存在正分离时，学习性成立。若分离为零，则在任意有限查询预算下，最优最坏情况错误率恒为 $1/2$。对于任意 $T$-查询自适应策略及任意 $ρ∈(0,1)$，我们构造出一种随机化非自适应过程，使用 $O(N^2(T + \log(1/ρ)))$ 对查询，这些查询在观测前即确定。其模拟的响应轨迹在总变差距离上与自适应轨迹相差不超过 $ρ$，对模型内所有分布均成立。此外，我们还构造出一类具有常数自适应查询复杂度、但非自适应复杂度为 $Ω_\\'varepsilon(N^2)$ 的匹配族。因此，最坏情况下的固定误差自适应差距为 $Θ_\\'varepsilon(N^2)$。这意味着交互可将查询数减少至平方级别，但交互带来的指数分支并未产生指数级查询优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。