論文の概要: Robustly Learning any Clusterable Mixture of Gaussians
- arxiv url: http://arxiv.org/abs/2005.06417v1
- Date: Wed, 13 May 2020 16:44:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-03 12:58:07.384014
- Title: Robustly Learning any Clusterable Mixture of Gaussians
- Title（参考訳）: ガウスのクラスタブルな混合をロバストに学習する
- Authors: Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar
- Abstract要約: 本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
- 参考スコア（独自算出の注目度）: 55.41573600814391
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the efficient learnability of high-dimensional Gaussian mixtures in
the outlier-robust setting, where a small constant fraction of the data is
adversarially corrupted. We resolve the polynomial learnability of this problem
when the components are pairwise separated in total variation distance.
Specifically, we provide an algorithm that, for any constant number of
components $k$, runs in polynomial time and learns the components of an
$\epsilon$-corrupted $k$-mixture within information theoretically near-optimal
error of $\tilde{O}(\epsilon)$, under the assumption that the overlap between
any pair of components $P_i, P_j$ (i.e., the quantity $1-TV(P_i, P_j)$) is
bounded by $\mathrm{poly}(\epsilon)$.
Our separation condition is the qualitatively weakest assumption under which
accurate clustering of the samples is possible. In particular, it allows for
components with arbitrary covariances and for components with identical means,
as long as their covariances differ sufficiently. Ours is the first polynomial
time algorithm for this problem, even for $k=2$.
Our algorithm follows the Sum-of-Squares based proofs to algorithms approach.
Our main technical contribution is a new robust identifiability proof of
clusters from a Gaussian mixture, which can be captured by the constant-degree
Sum of Squares proof system. The key ingredients of this proof are a novel use
of SoS-certifiable anti-concentration and a new characterization of pairs of
Gaussians with small (dimension-independent) overlap in terms of their
parameter distance.
- Abstract（参考訳）: 本研究では,外乱条件下での高次元ガウス混合の効率的な学習性について検討する。
成分が全変動距離で相互に分離された場合、この問題の多項式学習可能性を解決する。
具体的には、任意の定数数に対して、$k$ が多項式時間で実行され、理論上は$\tilde{O}(\epsilon)$ に近い最適誤差である$\tilde{O}(\epsilon)$ の成分を学習するアルゴリズムを、任意のコンポーネントのペアである$P_i, P_j$(つまり、$-TV(P_i, P_j)$) の重なりが$\mathrm{poly}(\epsilon)$ で有界であるという仮定の下で提供する。
我々の分離条件は、試料の正確なクラスタリングが可能な定性的に弱い仮定である。
特に、任意の共分散を持つ成分と、その共分散が十分に異なる限り、同じ手段を持つ成分が可能である。
oursは、k=2$でもこの問題に対する最初の多項式時間アルゴリズムである。
アルゴリズムは二乗法に基づく証明からアルゴリズムへのアプローチに従っている。
我々の主な技術的貢献は、ガウス混合体からのクラスターの新たな堅牢な同定可能性証明であり、これは、一定の度合いの正方形証明システムによって捉えることができる。
この証明の鍵となる要素は、SOS検出可能なアンチ濃度の新規使用と、パラメータ距離が小さい(次元に依存しない)ガウスのペアの新たな特徴である。
関連論文リスト
- Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。
我々は、下層の混合成分について分離を前提としない。
我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-29T17:30:36Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - 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) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - Beyond Parallel Pancakes: Quasi-Polynomial Time Guarantees for
Non-Spherical Gaussian Mixtures [9.670578317106182]
kgeq 2$ Gaussian 成分と未知の手段と未知の共分散(すべての成分について同一視される)の混合を考える。
混合重量が指数関数的に小さい場合にのみこのような硬さが現れることを示す。
我々は,最小混合重量の時間準多項式を用いた2乗法に基づくアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-12-10T10:51:44Z) - Clustering Mixtures with Almost Optimal Separation in Polynomial Time [21.509452343745252]
高次元における平均分離ガウス多様体のクラスタリング混合問題について考察する。
Delta = Theta (sqrtlog k)$ の分離は必要であり、良いクラスタリングを回復するのに十分である。
我々は多くのサンプルと時間を要し、優れたクラスタリングをうまく回復できるアルゴリズムを提示する。
論文 参考訳（メタデータ） (2021-12-01T18:34:09Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - 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) - Outlier-Robust Clustering of Non-Spherical Mixtures [5.863264019032882]
統計的に分離されたd-次元ガウスアン(k-GMM)の混合をクラスタリングするための最初のアウトリー・ローバストアルゴリズムを与える。
この結果は、$d$次元単位球面上の均一分布の任意のアフィン変換のクラスタリング混合に拡張される。
論文 参考訳（メタデータ） (2020-05-06T17:24:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。