論文の概要: Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities

• arxiv url: http://arxiv.org/abs/2206.02765v1
• Date: Mon, 6 Jun 2022 17:42:11 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-07 16:34:15.387136
• Title: Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities
• Title（参考訳）: 通信制約仮説テスト:最適性、堅牢性、逆データ処理の不等式
• Authors: Ankit Pensia, Varun Jog, Po-Ling Loh
• Abstract要約: 通信制約下での単純な二項仮説テストのサンプルの複雑さは、少なくとも制約のない設定よりも大きい対数係数であることが示される。 我々のフレームワークは、分布が全変動距離で破壊されるような頑健な仮説テストにまで拡張する。
• 参考スコア（独自算出の注目度）: 6.939768185086755
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study hypothesis testing under communication constraints, where each sample is quantized before being revealed to a statistician. Without communication constraints, it is well known that the sample complexity of simple binary hypothesis testing is characterized by the Hellinger distance between the distributions. We show that the sample complexity of simple binary hypothesis testing under communication constraints is at most a logarithmic factor larger than in the unconstrained setting and this bound is tight. We develop a polynomial-time algorithm that achieves the aforementioned sample complexity. Our framework extends to robust hypothesis testing, where the distributions are corrupted in the total variation distance. Our proofs rely on a new reverse data processing inequality and a reverse Markov inequality, which may be of independent interest. For simple $M$-ary hypothesis testing, the sample complexity in the absence of communication constraints has a logarithmic dependence on $M$. We show that communication constraints can cause an exponential blow-up leading to $\Omega(M)$ sample complexity even for adaptive algorithms.
• Abstract（参考訳）: コミュニケーション制約下で仮説検証を行い,各サンプルは統計学者に明かされる前に定量化される。 通信制約がなければ、単純な二分仮説テストのサンプル複雑性は分布間のヘルリンガー距離によって特徴づけられることが知られている。 通信制約下での単純な二項仮説テストのサンプル複雑性は、少なくとも制約のない設定よりも大きい対数係数であり、この境界は厳密であることを示す。 上記のサンプル複雑性を実現する多項式時間アルゴリズムを開発した。 我々のフレームワークは、分布が全変動距離で破壊される頑健な仮説テストにまで拡張される。 我々の証明は、新しい逆データ処理の不等式と、独立した関心を持つかもしれない逆マルコフ不等式に依存している。 単純な$M$-ary仮説テストでは、通信制約がない場合のサンプルの複雑さは$M$に対数依存する。 適応アルゴリズムにおいても,通信制約が指数的に爆発的に$\Omega(M)$サンプル複雑性を引き起こす可能性があることを示す。

関連論文リスト

• Controllable Generation via Locally Constrained Resampling [77.48624621592523]
  本研究では, ベイズ条件付けを行い, 制約条件下でサンプルを描画する, トラクタブルな確率的手法を提案する。 提案手法はシーケンス全体を考慮し,現行のグリード法よりも大域的に最適に制約された生成を導出する。 提案手法は, 有害な世代からモデル出力を分離し, 脱毒化に対する同様のアプローチより優れていることを示す。
  論文  参考訳（メタデータ） (2024-10-17T00:49:53Z)
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  CoT(Chain-of-Thought)の促進とその変種は、多段階推論問題を解決する効果的な方法として人気を集めている。 統計的推定の観点からCoTのプロンプトを解析し,その複雑さを包括的に評価する。
  論文  参考訳（メタデータ） (2024-08-25T04:07:18Z)
• Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests [5.3595271893779906]
  フェデレート学習は、さまざまな場所でデータが収集され分析される広範囲な設定で適用可能であることから、近年大きな注目を集めている。 分散差分プライバシー(DP)制約下でのホワイトノイズ・ウィズ・ドリフトモデルにおける非パラメトリック適合性試験について検討した。
  論文  参考訳（メタデータ） (2024-06-10T19:25:19Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
  本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。 線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
  論文  参考訳（メタデータ） (2023-11-01T04:41:16Z)
• Non-Stochastic CDF Estimation Using Threshold Queries [3.6576781735746513]
  実験的な分布を2つの課題で推定する問題に取り組む。 まず、アルゴリズムはデータを直接観察するのではなく、サンプルについて限られた数のしきい値クエリしか要求しない。 第二に、データは独立で同一の分散であると仮定されず、代わりにサンプルを生成する任意のプロセスが可能である。
  論文  参考訳（メタデータ） (2023-01-13T18:00:57Z)
• Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints [8.261182037130407]
  局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。 我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
  論文  参考訳（メタデータ） (2023-01-09T18:36:49Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

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

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