조건부 질의를 이용한 가설 검정: 학습 가능성과 상호작용의 가치

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

모델 평가는 응답을 관찰하기 전에 모든 테스트를 고정하거나, 이전 응답을 사용하여 후속 테스트를 선택할 수 있습니다. 본 연구에서는 유한한 결과 공간 $\mathcal{X}$ (여기서 $|\mathcal{X}|=N$)에서 조건부 질의 모델을 사용하여 이 선택에 대해 분석합니다. 먼저, 어떤 분포 쌍이 안정적으로 구별될 수 있는지 질문합니다. 다음으로, 사전에 모든 테스트를 고정해야 하는 경우, 적응형 테스터와 일치하는 데 필요한 추가적인 질의 횟수는 몇 번인지 알아봅니다. 두 클래스가 쌍별 조건 확률에서 양의 분리를 가질 때만 학습 가능성이 존재한다는 것을 보여줍니다. 이러한 분리가 0인 경우, 모든 유한한 질의 예산에서 최적의 최악 성능 오류는 정확히 1/2입니다. 임의의 $T$-질의 적응형 정책과 임의의 $ρ ∈ (0,1)$에 대해, 응답이 관찰되기 전에 선택되는 $O(N^2(T + \log(1/ρ)))$ 쌍의 질의를 사용하는 무작위 비적응 절차를 구성합니다. 이 절차의 시뮬레이션된 결과는 모델 내 모든 분포에 대해 총 변동에서 $ρ$ 이내로 적응형 결과와 일치하며, 전체적으로 동일합니다. 또한, 상수 수준의 적응형 질의 복잡도를 가지면서 비적응형 질의 복잡도가 $\Omega_{\varepsilon}(N^2)$인 일치하는 계열을 구성합니다. 따라서 최악 성능의 고정 오류 적응성 격차는 $\Theta_{\varepsilon}(N^2)$입니다. 결과적으로, 상호작용은 필요한 테스트 횟수를 제곱 차수에 해당하는 비율로 줄일 수 있지만, 대화형 평가에서 보이는 것처럼 보이는 지수적인 분기 현상은 지수적인 질의 이점을 제공하지 않습니다.

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.