論文の概要: Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures

• arxiv url: http://arxiv.org/abs/2411.12438v1
• Date: Tue, 19 Nov 2024 11:58:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-20 13:37:33.558633
• Title: Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures
• Title（参考訳）: 非球面混合に対する2乗法と改良クラスタリングアルゴリズムによる次元低減
• Authors: Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer,
• Abstract要約: 我々は,非球面(すなわち任意の成分共分散)ガウス混合モデルをサブルーチンでクラスタリングするための新しいアプローチを開発した。 本手法は特異値分解に基づく古典的次元減少の非球面アナログを与える。 我々のアルゴリズムは自然に任意の外れ値の次元非依存の分数に許容するように拡張する。
• 参考スコア（独自算出の注目度）: 5.668124846154999
• License:
• Abstract: We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine, based on the sum-of-squares method, that finds a low-dimensional separation-preserving projection of the input data. Our method gives a non-spherical analog of the classical dimension reduction, based on singular value decomposition, that forms a key component of the celebrated spherical clustering algorithm of Vempala and Wang [VW04] (in addition to several other applications). As applications, we obtain an algorithm to (1) cluster an arbitrary total-variation separated mixture of $k$ centered (i.e., zero-mean) Gaussians with $n\geq \operatorname{poly}(d) f(w_{\min}^{-1})$ samples and $\operatorname{poly}(n)$ time, and (2) cluster an arbitrary total-variation separated mixture of $k$ Gaussians with identical but arbitrary unknown covariance with $n \geq d^{O(\log w_{\min}^{-1})} f(w_{\min}^{-1})$ samples and $n^{O(\log w_{\min}^{-1})}$ time. Here, $w_{\min}$ is the minimum mixing weight of the input mixture, and $f$ does not depend on the dimension $d$. Our algorithms naturally extend to tolerating a dimension-independent fraction of arbitrary outliers. Before this work, the techniques in the state-of-the-art non-spherical clustering algorithms needed $d^{O(k)} f(w_{\min}^{-1})$ time and samples for clustering such mixtures. Our results may come as a surprise in the context of the $d^{\Omega(k)}$ statistical query lower bound [DKS17] for clustering non-spherical Gaussian mixtures. While this result is usually thought to rule out $d^{o(k)}$ cost algorithms for the problem, our results show that the lower bounds can in fact be circumvented for a remarkably general class of Gaussian mixtures.
• Abstract（参考訳）: 本研究では,非球面(すなわち任意の成分共分散)ガウス混合モデルをサブルーチンでクラスタリングする手法を開発した。 本手法は, 特異値分解に基づく古典的次元減少の非球面類似性を提供し, ベンパラとワングの有名な球面クラスタリングアルゴリズム(VW04)の鍵となる成分を形成する(他にもいくつかの応用がある)。 応用として、(1)$k$中心の任意の全変分混合(つまり、ゼロ平均)ガウスアンと$n\geq \operatorname{poly}(d) f(w_{\min}^{-1})$サンプルと$\operatorname{poly}(n)$時間と(2)同じだが任意の未知の共分散を持つ$k$ガウスアンの任意の全変分混合を$n \geq d^{O(\log w_{\min}^{-1}) f(w_{\min}^{-1})$サンプルと$n^{O(\log w_{\min}^{-1})$時間でクラスタするアルゴリズムを得る。 ここで、$w_{\min}$は入力混合物の最小混合重量であり、$f$は寸法$d$に依存しない。 我々のアルゴリズムは自然に任意の外れ値の次元非依存の分数に許容するように拡張する。 この研究に先立ち、最先端の非球面クラスタリングアルゴリズムの手法は、そのような混合物をクラスタリングするための時間とサンプルを$d^{O(k)} f(w_{\min}^{-1})$必要とした。 我々の結果は、非球面ガウス混合をクラスタリングするための、$d^{\Omega(k)}$ 統計的クエリローバウンド [DKS17] の文脈で驚くかもしれない。 この結果は、通常、この問題に対する$d^{o(k)}$コストのアルゴリズムを除外すると考えられているが、我々の結果は、ガウス混合の驚くほど一般的なクラスに対して、実際に下界を回避できることを示している。

関連論文リスト

• Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation [44.25945344950543]
  境界共分散分布の混合に対するクラスタリング問題について検討する。 このクラスタリングタスクに対して,最初のポリ時間アルゴリズムを提案する。 我々のアルゴリズムは、対数外乱の$Omega(alpha)$-fractionに対して堅牢である。
  論文  参考訳（メタデータ） (2023-12-19T01:01:53Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• 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)
• 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)
• 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)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• No-substitution k-means Clustering with Adversarial Order [8.706058694927613]
  任意の順序で到着するデータセットのクラスタリングの難しさを定量化する新しい複雑性尺度を提案する。 我々の新しいアルゴリズムは、$textpoly(klog(n))$centerのみを取り、$textpoly(k)$-approximationです。
  論文  参考訳（メタデータ） (2020-12-28T22:35:44Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。 理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。 我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
  論文  参考訳（メタデータ） (2020-05-13T16:44:12Z)
• Outlier-Robust Clustering of Non-Spherical Mixtures [5.863264019032882]
  統計的に分離されたd-次元ガウスアン(k-GMM)の混合をクラスタリングするための最初のアウトリー・ローバストアルゴリズムを与える。 この結果は、$d$次元単位球面上の均一分布の任意のアフィン変換のクラスタリング混合に拡張される。
  論文  参考訳（メタデータ） (2020-05-06T17:24:27Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。