論文の概要: Gaussian Mean Testing Made Simple
- arxiv url: http://arxiv.org/abs/2210.13706v1
- Date: Tue, 25 Oct 2022 01:59:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-26 14:21:44.739922
- Title: Gaussian Mean Testing Made Simple
- Title(参考訳): ガウス平均テストはシンプルに
- Authors: Ilias Diakonikolas, Daniel M. Kane, Ankit Pensia
- Abstract要約: a distribution $p$ on $mathbbRd$ の i.d. サンプルを考えると、このタスクは以下のケースで高い確率で区別することである。
一ページ解析によるガウス平均検定の極めて単純なアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 46.03021473600576
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the following fundamental hypothesis testing problem, which we term
Gaussian mean testing. Given i.i.d. samples from a distribution $p$ on
$\mathbb{R}^d$, the task is to distinguish, with high probability, between the
following cases: (i) $p$ is the standard Gaussian distribution,
$\mathcal{N}(0,I_d)$, and (ii) $p$ is a Gaussian $\mathcal{N}(\mu,\Sigma)$ for
some unknown covariance $\Sigma$ and mean $\mu \in \mathbb{R}^d$ satisfying
$\|\mu\|_2 \geq \epsilon$. Recent work gave an algorithm for this testing
problem with the optimal sample complexity of $\Theta(\sqrt{d}/\epsilon^2)$.
Both the previous algorithm and its analysis are quite complicated. Here we
give an extremely simple algorithm for Gaussian mean testing with a one-page
analysis. Our algorithm is sample optimal and runs in sample linear time.
- Abstract(参考訳): ガウス平均検定(gaussian mean testing)と呼ぶ、以下の基本的な仮説検定問題を研究する。
分布 $p$ on $\mathbb{R}^d$ の i.d. サンプルを考えると、このタスクは次のケースの間で高い確率で区別することである。
(i) $p$ は標準ガウス分布、$\mathcal{n}(0,i_d)$、および
(ii)$p$ はガウスの $\mathcal{N}(\mu,\Sigma)$ であり、未知の共分散 $\Sigma$ に対して$\mu \in \mathbb{R}^d$ は $\|\mu\|_2 \geq \epsilon$ を満たす。
最近の研究は、このテスト問題のアルゴリズムに、$\theta(\sqrt{d}/\epsilon^2)$の最適なサンプル複雑性を与えた。
以前のアルゴリズムと解析はどちらも非常に複雑である。
ここでは1ページ解析によるガウス平均テストの極めて単純なアルゴリズムを提案する。
我々のアルゴリズムは標本最適であり、サンプル線形時間で動作する。
関連論文リスト
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。
適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
論文 参考訳(メタデータ) (2024-11-08T17:10:38Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。
本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文 参考訳(メタデータ) (2024-08-10T04:26:19Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Private High-Dimensional Hypothesis Testing [4.133655523622441]
我々は高次元分布の個人性テストのための改良された差分プライベートアルゴリズムを提供する。
具体的には、ある固定された$mu*$に対して$mathcalN(mu*, Sigma)$、または少なくとも$alpha$の総変動距離を持つ$mathcalN(mu*, Sigma)$に由来するかどうかをテストすることができる。
論文 参考訳(メタデータ) (2022-03-03T06:25:48Z) - 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 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。