論文の概要: 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)$サンプル複雑性を引き起こす可能性があることを示す。
関連論文リスト
- Optimal Multi-Distribution Learning [94.73322179348332]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では,$(d+k)/varepsilon2$の順に,サンプルの複雑さを伴って,$varepsilon$-optimal randomized hypothesisを生成するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - Precise Error Rates for Computationally Efficient Testing [75.63895690909241]
本稿では,計算複雑性に着目した単純な対数-単純仮説テストの問題を再考する。
線形スペクトル統計に基づく既存の試験は、I型とII型の誤差率の間の最良のトレードオフ曲線を達成する。
論文 参考訳(メタデータ) (2023-11-01T04:41:16Z) - On sample complexity of conditional independence testing with Von Mises
estimator with application to causal discovery [21.12645737093305]
条件付き独立テストは制約に基づく因果探索アルゴリズムにおいて不可欠なステップである。
我々は、最適パラメトリックレートを達成するVM-CIと呼ばれる推定器に基づいて、条件独立性の試験を設計する。
VM-CIは、時間またはサンプルの複雑さの観点から、他の一般的なCIテストよりも優れていることを実証的に示します。
論文 参考訳(メタデータ) (2023-10-20T14:52:25Z) - 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) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳(メタデータ) (2021-10-24T04:03:00Z) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳(メタデータ) (2020-09-14T16:09:17Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。