論文の概要: The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints

• arxiv url: http://arxiv.org/abs/2506.13686v1
• Date: Mon, 16 Jun 2025 16:50:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-18 17:34:59.115768
• Title: The Sample Complexity of Distributed Simple Binary Hypothesis Testing under Information Constraints
• Title（参考訳）: 情報制約下における分散単純二項仮説テストの複雑さ
• Authors: Hadi Kazemi, Ankit Pensia, Varun Jog,
• Abstract要約: 逐次的相互作用は、分散された単純二項仮説テストのサンプルの複雑さを低減するのに役立たないことを示す。 第2の問題は、通信に制約のある単純なバイナリ仮説テストのための既存のサンプル複雑性境界の締め付けを示唆している。
• 参考スコア（独自算出の注目度）: 7.10734752120062
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper resolves two open problems from a recent paper, arXiv:2403.16981, concerning the sample complexity of distributed simple binary hypothesis testing under information constraints. The first open problem asks whether interaction reduces the sample complexity of distributed simple binary hypothesis testing. In this paper, we show that sequential interaction does not help. The second problem suggests tightening existing sample complexity bounds for communication-constrained simple binary hypothesis testing. We derive optimally tight bounds for this setting and resolve this problem. Our main technical contributions are: (i) a one-shot lower bound on the Bayes error in simple binary hypothesis testing that satisfies a crucial tensorisation property; (ii) a streamlined proof of the formula for the sample complexity of simple binary hypothesis testing without constraints, first established in arXiv:2403.16981; and (iii) a reverse data-processing inequality for Hellinger-$\lambda$ divergences, generalising the results from arXiv:1812.03031 and arXiv:2206.02765.
• Abstract（参考訳）: 本稿では,情報制約下での分散単純二項仮説検定の複雑さについて,最近の論文arXiv:2403.16981から2つのオープンな問題を解く。 最初のオープンな問題は、相互作用が分散された単純二項仮説テストのサンプルの複雑さを減少させるかどうかを問うものである。 本稿では、逐次的相互作用が役に立たないことを示す。 第2の問題は、通信に制約のある単純なバイナリ仮説テストのための既存のサンプル複雑性境界の締め付けを示唆している。 この設定に対して最適に厳密な境界を導出し、この問題を解決する。 私たちの主な技術貢献は次のとおりです。 i) 決定的なテンソル化特性を満たす単純な二分仮説検定におけるベイズ誤差の1ショット下限 (ii)まずarXiv:2403.16981で確立された制約のない単純二項仮説検定のサンプル複雑性の公式の合理化証明 (iii) Hellinger-$\lambda$ divergencesの逆データ処理の不等式で、arXiv:1812.03031とarXiv:2206.02765の結果を一般化する。

関連論文リスト

• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities [8.010966370223985]
  通信制約下での単純な二項仮説テストのサンプルの複雑さは、少なくとも制約のない設定よりも大きい対数係数であることが示される。 我々のフレームワークは、分布が全変動距離で破壊されるような頑健な仮説テストにまで拡張する。
  論文  参考訳（メタデータ） (2022-06-06T17:42:11Z)
• Good Classifiers are Abundant in the Interpolating Regime [64.72044662855612]
  補間分類器間のテストエラーの完全な分布を正確に計算する手法を開発した。 テストエラーは、最悪の補間モデルのテストエラーから大きく逸脱する、小さな典型的な$varepsilon*$に集中する傾向にある。 以上の結果から,統計的学習理論における通常の解析手法は,実際に観測された優れた一般化性能を捉えるのに十分な粒度にはならない可能性が示唆された。
  論文  参考訳（メタデータ） (2020-06-22T21:12:31Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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