論文の概要: The Sample Complexity of Simple Binary Hypothesis Testing

• arxiv url: http://arxiv.org/abs/2403.16981v1
• Date: Mon, 25 Mar 2024 17:42:32 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-27 20:15:04.210340
• Title: The Sample Complexity of Simple Binary Hypothesis Testing
• Title（参考訳）: 単純二項仮説検査の複雑さ
• Authors: Ankit Pensia, Varun Jog, Po-Ling Loh,
• Abstract要約: 単純な二項仮説テストのサンプルの複雑さは、いずれの設定でも$p$と$q$の2つの分布を区別するのに必要となる最小のi.d.サンプルである。 この問題は、$alpha = beta$ (prior-free) または $alpha = 1/2$ (Bayesian) でのみ研究されている。
• 参考スコア（独自算出の注目度）: 7.127829790714167
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The sample complexity of simple binary hypothesis testing is the smallest number of i.i.d. samples required to distinguish between two distributions $p$ and $q$ in either: (i) the prior-free setting, with type-I error at most $\alpha$ and type-II error at most $\beta$; or (ii) the Bayesian setting, with Bayes error at most $\delta$ and prior distribution $(\alpha, 1-\alpha)$. This problem has only been studied when $\alpha = \beta$ (prior-free) or $\alpha = 1/2$ (Bayesian), and the sample complexity is known to be characterized by the Hellinger divergence between $p$ and $q$, up to multiplicative constants. In this paper, we derive a formula that characterizes the sample complexity (up to multiplicative constants that are independent of $p$, $q$, and all error parameters) for: (i) all $0 \le \alpha, \beta \le 1/8$ in the prior-free setting; and (ii) all $\delta \le \alpha/4$ in the Bayesian setting. In particular, the formula admits equivalent expressions in terms of certain divergences from the Jensen--Shannon and Hellinger families. The main technical result concerns an $f$-divergence inequality between members of the Jensen--Shannon and Hellinger families, which is proved by a combination of information-theoretic tools and case-by-case analyses. We explore applications of our results to robust and distributed (locally-private and communication-constrained) hypothesis testing.
• Abstract（参考訳）: 単純二項仮説検定のサンプル複雑性は、2つの分布を区別するのに必要となる最小のi.d.サンプル数である。 (i)type-Iエラーが最大$\alpha$、type-IIエラーが最大$\beta$;、または (ii)ベイズ誤差は最大$\delta$で、事前分布$(\alpha, 1-\alpha)$である。 この問題は、$\alpha = \beta$ (prior-free) または $\alpha = 1/2$ (Bayesian) でのみ研究され、サンプルの複雑さは、乗法定数まで、$p$ と $q$ の間のヘリンガーの発散によって特徴づけられることが知られている。 本稿では, サンプルの複雑さ($p$, $q$, and all error parameters)を特徴づける式を導出する。 (i)すべての$0 \le \alpha, \beta \le 1/8$ (ii)ベイズ設定ですべての$\delta \le \alpha/4$ 特に、式はジェンセン=シャノン家(英語版)とヘリンガー家(英語版)のある種の相違点の観点から等価な表現を認める。 主な技術的結果は、情報理論ツールとケース・バイ・ケース分析の組み合わせによって証明されたジェンセン=シャノン家とヘリンジャー家のメンバー間の$f$分割不等式に関するものである。 我々は、ロバストで分散された(ローカルにプライベートで、通信に制約のある)仮説テストへの結果の適用について検討する。

関連論文リスト

• Testing with Non-identically Distributed Samples [20.74768558932617]
  本研究では,サンプルが独立に分布するが同一に分布しない設定に対して,サブ線形サンプル特性試験と推定が適用範囲について検討する。 それぞれのディストリビューションから$Theta(k/varepsilon2)$サンプルをサンプリングしても、$textbfp_mathrmavg$は、テレビ距離で$textbfp_mathrmavg$をエラー$varepsilon$内で学習するのに十分である。
  論文  参考訳（メタデータ） (2023-11-19T01:25:50Z)
• Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
  一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。 1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。 衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
  論文  参考訳（メタデータ） (2022-06-21T20:43:53Z)
• The Sample Complexity of Robust Covariance Testing [56.98280399449707]
  i. i. d. 形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。 汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。 サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
  論文  参考訳（メタデータ） (2020-12-31T18:24:41Z)
• Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
  高確率状態に着目して離散分布を試験する問題について検討する。 一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-14T16:09:17Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Private Mean Estimation of Heavy-Tailed Distributions [10.176795938619417]
  差分的にプライベートな分布の平均推定におけるミニマックスサンプルの複雑さについて, 新たな上限値と下限値を与える。 $n = Thetaleft(frac1alpha2 + frac1alphafrack-1varepsilonright)$サンプルは必要で、$varepsilon$-differential privacyの下で$alpha$-accuracyと見積もるのに十分である。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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