論文の概要: Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction

• arxiv url: http://arxiv.org/abs/2608.06262v1
• Date: Thu, 06 Aug 2026 16:54:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-07 17:43:06.808752
• Title: Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction
• Title（参考訳）: 条件付きクエリによる仮説テスト:学習可能性と相互作用の価値
• Authors: Zonghuan Xu,
• Abstract要約: 学習容易性は、2つのクラスが2つの条件付き確率で正の分離を持つ場合にのみ成立することを示す。 一定の適応的なクエリ複雑性と$_varepsilon(N2)$非適応的なクエリ複雑性を持つマッチングファミリを構築する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: モデル評価は、どんな反応も観察する前に全てのテストを修正したり、初期の反応を使って後でテストを選択したりすることができる。 有限結果空間 $\mathcal{X}$ と $|\mathcal{X}|=N$ の条件待ち行列モデルでこの選択を研究する。 まず、どの分散クラスを確実に区別できるかを問う。 次に、すべてのクエリイベントを事前に修正する必要がある場合に、アダプティブテスタにマッチするために追加のクエリがいくつ必要か尋ねます。 学習容易性は、2つのクラスが2つの条件付き確率で正の分離を持つ場合にのみ成立することを示す。 この分離がゼロの場合、最大の最悪のエラーは、全ての有限クエリ予算で正確に1/2ドルである。 任意の$T$-query適応ポリシーと任意の$ρ\in (0,1)$に対して、任意の応答が観測される前に選択された$O(N^2(T + \log(1/ρ)))$ペアクエリを用いてランダム化された非適応手順を構築する。 そのシミュレートされた文字起こしは、モデル内のすべての分布に対して、適応的な文字起こしの完全なバリエーションにおいて$ρ$以内である。 また、一定の適応的なクエリ複雑性と$Ω_\varepsilon(N^2)$非適応的なクエリ複雑性を持つマッチングファミリを構築する。 その結果、最悪の固定エラー適応率ギャップは、$ _\varepsilon(N^2)$である。 したがって、相互作用は2次因子によるテストの必要な回数を減らすことができるが、対話的な評価の明らかな指数的分岐は指数的クエリの優位性をもたらすものではない。

関連論文リスト

• Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
  我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。 多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
  論文  参考訳（メタデータ） (2026-08-04T23:38:54Z)
• Is Randomness Necessary for Adaptive Data Analysis? [54.49386214602422]
  非自明な数の適応クエリに答えるためには、ランダム性が厳密に必要であることを示す。 ADAに関する10年にわたる作業にもかかわらず、この問題は未解決のままである。
  論文  参考訳（メタデータ） (2026-07-08T07:17:35Z)
• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。 クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。 このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
  論文  参考訳（メタデータ） (2026-01-07T22:07:44Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• On the Optimal Bounds for Noisy Computing [17.56584950469176]
  Wevisit the problem of computing with noisy information considered in Feige et al. 1994。 与えられた要素に対して、目標は、各クエリの結果が確率$p$で反転されたときに、少なくとも1-delta$の確率で所望の関数を正しく回復することである。 本稿では、過去の結果に基づいて各クエリを適応的に設計できる適応型サンプリング設定と、過去の結果に依存しない非適応型サンプリング設定の両方について考察する。
  論文  参考訳（メタデータ） (2023-06-21T00:31:23Z)
• The Projected Covariance Measure for assumption-lean variable significance testing [3.8936058127056357]
  単純だが一般的なアプローチは、線形モデルを指定し、次に$X$の回帰係数が 0 でないかどうかをテストすることである。 条件付き平均独立性のモデルフリーなnullをテストする問題、すなわち条件付き平均の$Y$$$X$と$Z$は$X$に依存しない。 本稿では,加法モデルやランダムフォレストなど,柔軟な非パラメトリックあるいは機械学習手法を活用可能な,シンプルで汎用的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-11-03T17:55:50Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。