論文の概要: Robustly Learning Mixtures of $k$ Arbitrary Gaussians
- arxiv url: http://arxiv.org/abs/2012.02119v2
- Date: Thu, 31 Dec 2020 17:24:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-23 19:52:39.365830
- Title: Robustly Learning Mixtures of $k$ Arbitrary Gaussians
- Title（参考訳）: 任意ガウスの$kの混合を頑健に学習する
- Authors: Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K.
Kothari and Santosh S. Vempala
- Abstract要約: 任意の固定された$k$に対して$k$任意のガウスの混合を$mathbbRd$で頑健に推定する問題に対して、一定数の任意の汚職が存在する場合の時間アルゴリズムを与える。
本研究の主なツールは,2乗法に依拠する効率的な分節クラスタリングアルゴリズムと,Frobeniusノルムおよび低ランク項の誤りを許容する新しいテンソル分解アルゴリズムである。
- 参考スコア（独自算出の注目度）: 47.40835932474677
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give a polynomial-time algorithm for the problem of robustly estimating a
mixture of $k$ arbitrary Gaussians in $\mathbb{R}^d$, for any fixed $k$, in the
presence of a constant fraction of arbitrary corruptions. This resolves the
main open problem in several previous works on algorithmic robust statistics,
which addressed the special cases of robustly estimating (a) a single Gaussian,
(b) a mixture of TV-distance separated Gaussians, and (c) a uniform mixture of
two Gaussians. Our main tools are an efficient \emph{partial clustering}
algorithm that relies on the sum-of-squares method, and a novel tensor
decomposition algorithm that allows errors in both Frobenius norm and low-rank
terms.
- Abstract（参考訳）: 多項式時間アルゴリズムは、任意の破壊の一定分数の存在下において、任意のヤグシアンを$\mathbb{r}^d$ でロバストに推定する問題に対して、多項式時間アルゴリズムを与える。
このことは、アルゴリズム的ロバスト統計学に関するいくつかの過去の研究において、(a)1つのガウス、(b)テレビ距離分離ガウス、(c)2つのガウスの均一混合の特別なケースに対処する主要な開問題を解決している。
主なツールとしては,2乗法に依拠する効率の良い \emph{partial clustering} アルゴリズムと,Frobenius ノルムおよび低ランク項の誤りを許容する新しいテンソル分解アルゴリズムがある。
関連論文リスト
- Learning general Gaussian mixtures with efficient score matching [16.06356123715737]
我々は、$d$次元で$k$ガウシアンの混合を学習する問題を研究する。
我々は、下層の混合成分について分離を前提としない。
我々は、ターゲット混合物から$dmathrmpoly(k/varepsilon)$サンプルを抽出し、サンプル-ポリノミカル時間で実行し、サンプリング器を構築するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-29T17:30:36Z) - Learning Mixtures of Gaussians Using Diffusion Models [9.118706387430883]
テレビエラーに対して$k$ Gaussiansの混合を学習するための新しいアルゴリズムを提案する。
我々のアプローチは解析的であり、拡散モデルの枠組みに依存している。
論文 参考訳（メタデータ） (2024-04-29T17:00:20Z) - Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples [9.649879910148854]
差分プライバシー(DP)制約下におけるガウシアン混合量の推定問題について検討する。
主な結果は、$textpoly(k,d,1/alpha,1/varepsilon,log (1/delta))$サンプルが$k$ Gaussians in $mathbbRd$から$alpha$までを推定するのに十分であることです。
これは GMM の構造的仮定を一切含まない問題に対する最初の有限標本複雑性上界である。
論文 参考訳（メタデータ） (2023-09-07T17:02:32Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Clustering a Mixture of Gaussians with Unknown Covariance [4.821312633849745]
最大極大推定に基づくMax-Cut整数プログラムを導出する。
最適な速度を得るが、2次サンプルサイズを必要とする効率的なスペクトルアルゴリズムを開発する。
我々は Max-Cut プログラムを$k$-means プログラムに一般化する。
論文 参考訳（メタデータ） (2021-10-04T17:59:20Z) - Learning Gaussian Mixtures with Generalised Linear Models: Precise
Asymptotics in High-dimensions [79.35722941720734]
多クラス分類問題に対する一般化線形モデルは、現代の機械学習タスクの基本的な構成要素の1つである。
実験的リスク最小化による高次元推定器の精度を実証する。
合成データの範囲を超えて我々の理論をどのように適用できるかを論じる。
論文 参考訳（メタデータ） (2021-06-07T16:53:56Z) - 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) - Robust Learning of Mixtures of Gaussians [13.173307471333617]
我々は、$X$が任意の$d$-次元ガウス多様体の均等な重み付け混合であるときに、$poly(eps)$を総変量で誤りを犯すことを学ぶ。
特に、$X$ が 2 つの任意の$d$次元ガウス多様体の均等な重み付き混合であれば、$X$ a $eps$-fraction からサンプルにアクセスする時間アルゴリズムを考案する。
論文 参考訳（メタデータ） (2020-07-12T05:15:50Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。