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

• URL: http://arxiv.org/abs/2608.06262v1
• Date: Thu, 06 Aug 2026 16:54:10 GMT
• Title: Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction
• Abstract summary: We show that learnability holds if and only if the two classes have positive separation in their pairwise conditional probabilities.<n>We construct a matching family with constant adaptive query complexity and $_varepsilon(N2)$ non-adaptive query complexity.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
  We study multicalibration for a sequence of $k$ properties in which each property is identifiable once the preceding properties are fixed.<n>Even with only polylogarithmically many binary groups, achieving multicalibration error $varepsilon$ requires $widetilde(varepsilon-(k+2))$ samples.
  arXiv  Detail & Related papers  (2026-08-04T23:38:54Z)
• Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation [14.106326180143666]
  We consider distributions on $mathbbR$ with mean in $[-,]$ and absolute $k$-th central moment at most $k$, where $k>1$ is fixed.<n>We show that this interaction can be avoided by constructing a randomized fully non-adaptive protocol.
  arXiv  Detail & Related papers  (2026-08-03T17:28:12Z)
• Is Randomness Necessary for Adaptive Data Analysis? [54.49386214602422]
  We show that randomness is strictly necessary to answer a non-trivial number of adaptive queries.<n>Despite a decade of work on ADA, this question remains open.
  arXiv  Detail & Related papers  (2026-07-08T07:17:35Z)
• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=1,..., n$, each assigned a positive weight.<n>A query specifies an admissible subset -- called a slate -- and the model chooses one item from that slate with probability proportional to its weight.<n>This query model is also known as the Plackett-Luce model or conditional sampling oracle in the literature.
  arXiv  Detail & Related papers  (2026-01-07T22:07:44Z)
• Active Learning of General Halfspaces: Label Queries vs Membership Queries [35.41111301965335]
  We show that any active learner requires label complexity of $tildeOmega(d/(log(m)epsilon))$, where $m$ is the number of unlabeled examples.<n>We give a computationally efficient learner with query complexity of $tildeO(min1/p, 1/epsilon + dcdot polylog (1/epsilon))$ achieving error guarantee of $O(opt)+epsilon$.
  arXiv  Detail & Related papers  (2024-12-31T15:40:48Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  We propose two algorithms that enjoy provable scaling laws for the test-time compute of large language models.<n>One is a two-stage knockout-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.<n>The other is a two-stage league-style algorithm, where each candidate is evaluated by its average win rate against multiple opponents.
  arXiv  Detail & Related papers  (2024-11-29T05:29:47Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• On the Optimal Bounds for Noisy Computing [17.56584950469176]
  We revisit the problem of computing with noisy information considered in Feige et al. 1994. For $K$ given elements, the goal is to correctly recover the desired function with probability at least $1-delta$ when the outcome of each query is flipped with probability $p$. We consider both the adaptive sampling setting where each query can be adaptively designed based on past outcomes, and the non-adaptive sampling setting where the query cannot depend on past outcomes.
  arXiv  Detail & Related papers  (2023-06-21T00:31:23Z)
• The Projected Covariance Measure for assumption-lean variable significance testing [3.8936058127056357]
  A simple but common approach is to specify a linear model, and then test whether the regression coefficient for $X$ is non-zero. We study the problem of testing the model-free null of conditional mean independence, i.e. that the conditional mean of $Y$ given $X$ and $Z$ does not depend on $X$. We propose a simple and general framework that can leverage flexible nonparametric or machine learning methods, such as additive models or random forests.
  arXiv  Detail & Related papers  (2022-11-03T17:55:50Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  We study the problem of testing discrete distributions with a focus on the high probability regime. We provide the first algorithms for closeness and independence testing that are sample-optimal, within constant factors.
  arXiv  Detail & Related papers  (2020-09-14T16:09:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.