論文の概要: Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation
- arxiv url: http://arxiv.org/abs/2106.08537v1
- Date: Wed, 16 Jun 2021 03:34:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-18 07:27:43.868640
- Title: Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation
- Title（参考訳）: リストデコダブル平均推定による概日時混合モデルのクラスタリング
- Authors: Ilias Diakonikolas, Daniel M. Kane, Daniel Kongsgaard, Jerry Li, Kevin
Tian
- Abstract要約: 本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
- 参考スコア（独自算出の注目度）: 58.24280149662003
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of list-decodable mean estimation, where an adversary
can corrupt a majority of the dataset. Specifically, we are given a set $T$ of
$n$ points in $\mathbb{R}^d$ and a parameter $0< \alpha <\frac 1 2$ such that
an $\alpha$-fraction of the points in $T$ are i.i.d. samples from a
well-behaved distribution $\mathcal{D}$ and the remaining $(1-\alpha)$-fraction
of the points are arbitrary. The goal is to output a small list of vectors at
least one of which is close to the mean of $\mathcal{D}$. As our main
contribution, we develop new algorithms for list-decodable mean estimation,
achieving nearly-optimal statistical guarantees, with running time $n^{1 +
o(1)} d$. All prior algorithms for this problem had additional polynomial
factors in $\frac 1 \alpha$. As a corollary, we obtain the first almost-linear
time algorithms for clustering mixtures of $k$ separated well-behaved
distributions, nearly-matching the statistical guarantees of spectral methods.
Prior clustering algorithms inherently relied on an application of $k$-PCA,
thereby incurring runtimes of $\Omega(n d k)$. This marks the first runtime
improvement for this basic statistical problem in nearly two decades.
The starting point of our approach is a novel and simpler near-linear time
robust mean estimation algorithm in the $\alpha \to 1$ regime, based on a
one-shot matrix multiplicative weights-inspired potential decrease. We
crucially leverage this new algorithmic framework in the context of the
iterative multi-filtering technique of Diakonikolas et. al. '18, '20, providing
a method to simultaneously cluster and downsample points using one-dimensional
projections --- thus, bypassing the $k$-PCA subroutines required by prior
algorithms.
- Abstract（参考訳）: 本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
具体的には、$T$ of $n$ points in $\mathbb{R}^d$ とパラメータ $0< \alpha <\frac 1 2$ が与えられ、$T$ の点の $\alpha$-fraction が i.d となる。
よく知られた分布 $\mathcal{D}$ のサンプルと残りの点の $(1-\alpha)$-fraction は任意である。
目標は、少なくとも1つが$\mathcal{d}$の平均に近いベクトルの小さなリストを出力することである。
本研究の主な貢献として,n^{1 + o(1)} d$ のランニング時間を用いて,ほぼ最適統計保証を達成し,リストデコタブル平均推定のための新しいアルゴリズムを開発した。
この問題の全ての前のアルゴリズムは、$\frac 1 \alpha$ の多項式因子を付加していた。
結論として,スペクトル手法の統計的保証にほぼ適合する,$k$の分離された分布をクラスタリングするための,最初のほぼ線形時間アルゴリズムを得る。
以前のクラスタリングアルゴリズムは本質的に$k$-PCAのアプリケーションに依存しており、それによって$\Omega(n d k)$のランタイムが生成される。
これは、この基本的な統計問題にとって、ほぼ20年ぶりのランタイム改善となる。
提案手法の出発点は, 1ショットの行列乗算重みに着想を得たポテンシャル減少に基づく, $\alpha \to 1$ regime における新しい,より単純なニア線形時間ロバスト平均推定アルゴリズムである。
ダイアコニコラス等の反復的マルチフィルタ手法の文脈において,この新たなアルゴリズムフレームワークを重要活用する。
アル
つまり、以前のアルゴリズムが必要とする$k$-PCAサブルーチンをバイパスする。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Simple, Scalable and Effective Clustering via One-Dimensional
Projections [10.807367640692021]
クラスタリングは、教師なし機械学習における基本的な問題であり、データ分析に多くの応用がある。
任意の$k$に対して、期待時間$O(mathrmnnz(X) + nlog n)$で確実に動作する単純なランダム化クラスタリングアルゴリズムを導入する。
我々は,このアルゴリズムが$k$-means目的の任意の入力データセットに対して,近似比$smashwidetildeO(k4)$を達成することを証明した。
論文 参考訳（メタデータ） (2023-10-25T16:37:45Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Replicable Clustering [57.19013971737493]
我々は,統計学的な$k$-medians,統計学的な$k$-means,統計学的な$k$-centers問題のアルゴリズムをブラックボックス方式で近似ルーチンを用いて提案する。
理論的結果を検証するブラックボックスとしてsklearnの$k$-means++実装を用いた2次元合成分布の実験も行っている。
論文 参考訳（メタデータ） (2023-02-20T23:29:43Z) - 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 Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳（メタデータ） (2022-06-10T17:38:18Z) - List-Decodable Sparse Mean Estimation [7.594050968868919]
最近の研究関心の高まりは、$alpha in (0, frac12]$というリストデコザブルな設定に焦点が当てられ、目標平均を少なくとも1つ近似した有限個の見積もりを出力することが目的である。
本稿では,基礎となるターゲットが平均分布$k$,最初のコントリビューションが最初のサンプル$Obig(mathrmpoly(k, log dbig)$,すなわち次元の多元対数であると考えている。
論文 参考訳（メタデータ） (2022-05-28T05:13:45Z) - 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) - List-Decodable Mean Estimation via Iterative Multi-Filtering [44.805549762166926]
未知の$alpha$-fraction of points in $T$は未知の平均と有界な共分散分布$D$から引き出される。
仮説ベクトルの小さなリストを出力し、その中の少なくとも一方が$D$に近いようにする。
より詳しくは、本アルゴリズムはサンプリングと計算効率が良く、情報理論上の準最適誤差を実現する。
論文 参考訳（メタデータ） (2020-06-18T17:47:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。