論文の概要: A Spectral Algorithm for List-Decodable Covariance Estimation in
Relative Frobenius Norm
- arxiv url: http://arxiv.org/abs/2305.00966v1
- Date: Mon, 1 May 2023 17:54:35 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-02 12:37:16.278124
- Title: A Spectral Algorithm for List-Decodable Covariance Estimation in
Relative Frobenius Norm
- Title(参考訳): 相対フロベニウスノルムにおけるリスト決定可能な共分散推定のためのスペクトルアルゴリズム
- Authors: Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Ankit Pensia,
Thanasis Pittas
- Abstract要約: 我々は、相対的なフロベニウスノルムにおいて、$Sigma$に近い仮説のリストを作成する。
結論として,ガウス混合モデルのロバストな部分クラスタリングのための効率的なスペクトルアルゴリズムを得る。
提案手法は, GMM を頑健に学習する最初の Sum-of-Squares-free アルゴリズムである。
- 参考スコア(独自算出の注目度): 41.03423042792559
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of list-decodable Gaussian covariance estimation. Given
a multiset $T$ of $n$ points in $\mathbb R^d$ such that an unknown $\alpha<1/2$
fraction of points in $T$ are i.i.d. samples from an unknown Gaussian
$\mathcal{N}(\mu, \Sigma)$, the goal is to output a list of $O(1/\alpha)$
hypotheses at least one of which is close to $\Sigma$ in relative Frobenius
norm. Our main result is a $\mathrm{poly}(d,1/\alpha)$ sample and time
algorithm for this task that guarantees relative Frobenius norm error of
$\mathrm{poly}(1/\alpha)$. Importantly, our algorithm relies purely on spectral
techniques. As a corollary, we obtain an efficient spectral algorithm for
robust partial clustering of Gaussian mixture models (GMMs) -- a key ingredient
in the recent work of [BDJ+22] on robustly learning arbitrary GMMs. Combined
with the other components of [BDJ+22], our new method yields the first
Sum-of-Squares-free algorithm for robustly learning GMMs. At the technical
level, we develop a novel multi-filtering method for list-decodable covariance
estimation that may be useful in other settings.
- Abstract(参考訳): リスト決定可能なガウス共分散推定の問題点について検討する。
a multiset $t$ of $n$ in $\mathbb r^d$, that that that that an unknown $\alpha<1/2$ fraction of points in $t$ is i.i.d. sample from an unknown gaussian $\mathcal{n}(\mu, \sigma)$ from an unknown gaussian $\mathcal{n}(\mu, \sigma)$, 目標は少なくとも$o(1/\alpha)$の仮定のリストを出力することである。
主な結果は、このタスクの$\mathrm{poly}(d,1/\alpha)$サンプルと時間アルゴリズムで、$\mathrm{poly}(1/\alpha)$の相対フロベニウスノルムエラーを保証します。
重要なことに、我々のアルゴリズムは純粋にスペクトル技術に依存している。
本研究では,任意のgmmをロバストに学習する[bdj+22]の最近の研究における重要な要素であるガウス混合モデル(gmms)のロバスト部分クラスタリングのための効率的なスペクトルアルゴリズムを提案する。
bdj+22]の他の成分と組み合わせることで,gmmsをロバストに学習する最初の2乗法を導出する。
技術的レベルでは、他の設定で有用かもしれないリスト分割可能な共分散推定のための新しいマルチフィルタ法を開発する。
関連論文リスト
- 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) - List-Decodable Covariance Estimation [1.9290392443571387]
共分散推定アルゴリズムを初めて提案する。
この結果から,リスト復号化可能な線形回帰と部分空間復元のための初となるエンフェクサクタクティックアルゴリズムが提案された。
論文 参考訳(メタデータ) (2022-06-22T09:38:06Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [48.07596965953344]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に,m = (klog(n))O(t)/alpha と m = (klog(n))O(t)/alpha と、m = (mnt)$ と、m = (klog(n))O(t)/alpha と、m = (1/alpha)O (1/t)$ の誤差を達成する。
論文 参考訳(メタデータ) (2022-06-10T17:38:18Z) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Robust Model Selection and Nearly-Proper Learning for GMMs [26.388358539260473]
学習理論では、データは有限混合モデルから生成されるという標準的な仮定がある。しかし、コンポーネントの数が事前に分かっていないときに何が起こるのか。
対数係数内の分布に適合するために必要な最小コンポーネント数を、およそ決定することができる。
論文 参考訳(メタデータ) (2021-06-05T01:58:40Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳(メタデータ) (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。