論文の概要: Sum-of-squares lower bounds for Non-Gaussian Component Analysis
- arxiv url: http://arxiv.org/abs/2410.21426v1
- Date: Mon, 28 Oct 2024 18:19:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-30 13:41:45.388049
- Title: Sum-of-squares lower bounds for Non-Gaussian Component Analysis
- Title（参考訳）: 非ガウス成分分析のための2乗下界の最小化
- Authors: Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang, Aaron Potechin,
- Abstract要約: 非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。
本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
- 参考スコア（独自算出の注目度）: 33.80749804695003
- License:
- Abstract: Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian direction in a high-dimensional dataset. Specifically, given i.i.d.\ samples from a distribution $P^A_{v}$ on $\mathbb{R}^n$ that behaves like a known distribution $A$ in a hidden direction $v$ and like a standard Gaussian in the orthogonal complement, the goal is to approximate the hidden direction. The standard formulation posits that the first $k-1$ moments of $A$ match those of the standard Gaussian and the $k$-th moment differs. Under mild assumptions, this problem has sample complexity $O(n)$. On the other hand, all known efficient algorithms require $\Omega(n^{k/2})$ samples. Prior work developed sharp Statistical Query and low-degree testing lower bounds suggesting an information-computation tradeoff for this problem. Here we study the complexity of NGCA in the Sum-of-Squares (SoS) framework. Our main contribution is the first super-constant degree SoS lower bound for NGCA. Specifically, we show that if the non-Gaussian distribution $A$ matches the first $(k-1)$ moments of $\mathcal{N}(0, 1)$ and satisfies other mild conditions, then with fewer than $n^{(1 - \varepsilon)k/2}$ many samples from the normal distribution, with high probability, degree $(\log n)^{{1\over 2}-o_n(1)}$ SoS fails to refute the existence of such a direction $v$. Our result significantly strengthens prior work by establishing a super-polynomial information-computation tradeoff against a broader family of algorithms. As corollaries, we obtain SoS lower bounds for several problems in robust statistics and the learning of mixture models. Our SoS lower bound proof introduces a novel technique, that we believe may be of broader interest, and a number of refinements over existing methods.
- Abstract（参考訳）: 非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。
具体的には、分布 $P^A_{v}$ on $\mathbb{R}^n$ のサンプルが、既知の分布 $A$ in a hidden direction $v$, and as a standard Gaussian in the orthogonal complement のゴールは、隠れた方向を近似することである。
標準定式化は、$A$の最初の$k-1$モーメントが標準ガウスのモーメントと一致し、$k$-thモーメントが異なることを仮定する。
軽度の仮定では、この問題はサンプル複雑性$O(n)$である。
一方、すべての既知の効率的なアルゴリズムは$\Omega(n^{k/2})$サンプルを必要とする。
先行研究では、急激な統計的クエリと低次テストの低いバウンダリが開発され、この問題に対する情報計算のトレードオフが示唆された。
本稿では Sum-of-Squares (SoS) フレームワークにおけるNGCAの複雑さについて考察する。
我々の主な貢献はNGCAに対する最初の超定常等級 SoS 下限である。
具体的には、非ガウス分布の$A$が最初の$(k-1)$のモーメントと一致して$\mathcal{N}(0, 1)$が満たされ、他の穏やかな条件を満たすならば、通常の分布からの多くのサンプルは、高い確率で$(\log n)^{{1\over 2}-o_n(1)}$ SoSはそのような方向の存在を否定することができない。
この結果は,より広範なアルゴリズム群に対する超多項式情報計算のトレードオフを確立することによって,先行作業を大幅に強化する。
コーナリーとして、ロバスト統計学および混合モデルの学習におけるいくつかの問題に対して、SoSの下位境界を求める。
SoSの低い境界証明は、より広い関心を持つかもしれない新しいテクニックを導入し、既存の手法よりも多くの改良を加えています。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Identification of Mixtures of Discrete Product Distributions in
Near-Optimal Sample and Time Complexity [6.812247730094931]
任意の$ngeq 2k-1$に対して、サンプルの複雑さとランタイムの複雑さをどうやって達成するかを示す(1/zeta)O(k)$。
また、既知の$eOmega(k)$の下位境界を拡張して、より広い範囲の$zeta$と一致させる。
論文 参考訳（メタデータ） (2023-09-25T09:50:15Z) - A Spectral Algorithm for List-Decodable Covariance Estimation in
Relative Frobenius Norm [41.03423042792559]
我々は、相対的なフロベニウスノルムにおいて、$Sigma$に近い仮説のリストを作成する。
結論として,ガウス混合モデルのロバストな部分クラスタリングのための効率的なスペクトルアルゴリズムを得る。
提案手法は, GMM を頑健に学習する最初の Sum-of-Squares-free アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-01T17:54:35Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Gaussian Mean Testing Made Simple [46.03021473600576]
a distribution $p$ on $mathbbRd$ の i.d. サンプルを考えると、このタスクは以下のケースで高い確率で区別することである。
一ページ解析によるガウス平均検定の極めて単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-25T01:59:13Z) - Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳（メタデータ） (2022-06-07T16:49:54Z) - Non-Gaussian Component Analysis via Lattice Basis Reduction [56.98280399449707]
非ガウス成分分析(NGCA)は分布学習問題である。
我々は,NGCA に対して,$A$ が離散的あるいはほぼ離散的であるような効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-12-16T18:38:02Z) - 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) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳（メタデータ） (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。