論文の概要: Computationally efficient sparse clustering
- arxiv url: http://arxiv.org/abs/2005.10817v3
- Date: Mon, 22 Mar 2021 17:38:04 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-30 23:20:04.492064
- Title: Computationally efficient sparse clustering
- Title（参考訳）: 計算効率の良いスパースクラスタリング
- Authors: Matthias L\"offler, Alexander S. Wein, Afonso S. Bandeira
- Abstract要約: 我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
- 参考スコア（独自算出の注目度）: 67.95910835079825
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study statistical and computational limits of clustering when the means of
the centres are sparse and their dimension is possibly much larger than the
sample size. Our theoretical analysis focuses on the model $X_i = z_i \theta +
\varepsilon_i, ~z_i \in \{-1,1\}, ~\varepsilon_i \thicksim \mathcal{N}(0,I)$,
which has two clusters with centres $\theta$ and $-\theta$. We provide a finite
sample analysis of a new sparse clustering algorithm based on sparse PCA and
show that it achieves the minimax optimal misclustering rate in the regime
$\|\theta\| \rightarrow \infty$.
Our results require the sparsity to grow slower than the square root of the
sample size. Using a recent framework for computational lower bounds -- the
low-degree likelihood ratio -- we give evidence that this condition is
necessary for any polynomial-time clustering algorithm to succeed below the BBP
threshold. This complements existing evidence based on reductions and
statistical query lower bounds. Compared to these existing results, we cover a
wider set of parameter regimes and give a more precise understanding of the
runtime required and the misclustering error achievable. Our results imply that
a large class of tests based on low-degree polynomials fail to solve even the
weak testing task.
- Abstract（参考訳）: 中央の平均がスパースであり、その次元がサンプルサイズよりはるかに大きい場合のクラスタリングの統計的および計算的限界について検討する。
理論解析では、モデル $x_i = z_i \theta + \varepsilon_i, ~z_i \in \{-1,1\}, ~\varepsilon_i \thicksim \mathcal{n}(0,i)$ に焦点を当てた。
スパースpcaに基づく新しいスパースクラスタリングアルゴリズムの有限サンプル解析を行い,$\|\theta\| \rightarrow \infty$ というレジームにおいて,最小の最適クラスタレートを達成することを示す。
以上の結果から, 試料粒径の平方根よりも緩やかに成長することが示唆された。
計算下界(低度度度比)の最近のフレームワークを用いて、多項式時間クラスタリングアルゴリズムがBBP閾値以下で成功するためには、この条件が必要であることを示す。
これは、還元と統計クエリの下限に基づく既存の証拠を補完する。
これらの既存の結果と比較すると、より広いパラメータの集合をカバーし、必要なランタイムと誤クラスタングエラーのより正確な理解を提供する。
その結果,低次多項式に基づく大規模なテストでは,弱いテストタスクさえ解決できないことがわかった。
関連論文リスト
- Subspace clustering in high-dimensions: Phase transitions \&
Statistical-to-Computational gap [24.073221004661427]
部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。
広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
論文 参考訳（メタデータ） (2022-05-26T17:47:35Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳（メタデータ） (2022-02-23T02:39:04Z) - Recovering Unbalanced Communities in the Stochastic Block Model With
Application to Clustering with a Faulty Oracle [9.578056676899203]
オラクルブロックモデル(英: Oracle block model、SBM)は、ネットワークにおけるグラフクラスタリングやコミュニティ検出を研究するための基礎モデルである。
我々は,SBMのコミュニティを様々な大きさのコミュニティで復元する,シンプルなSVDベースのアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-02-17T08:51:19Z) - Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
論文 参考訳（メタデータ） (2021-12-07T18:50:17Z) - Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
本研究では,空間的に制約されたクラスタリング,統計的推論,アンサンブルを組み合わせ,複数のクラスタリング推論解を集約するアンサンブルクラスタリング推論アルゴリズムの特性について検討する。
アンサンブルクラスタ推論アルゴリズムは,最大クラスター径に等しい$delta$-FWERの標準仮定で$delta$-FWERを制御することを示す。
論文 参考訳（メタデータ） (2021-06-04T16:37:19Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Statistical power for cluster analysis [0.0]
クラスターアルゴリズムは、生物医学研究でますます人気がある。
シミュレーションにより,共通解析におけるパワーと精度を推定する。
我々は,大規模なサブグループ分離が期待される場合にのみ,クラスタ分析を適用することを推奨する。
論文 参考訳（メタデータ） (2020-03-01T02:43:15Z) - Structures of Spurious Local Minima in $k$-means [20.155509538529568]
我々は、$k$-means問題に対する急激な局所解の構造について検討する。
分離条件下では,この現象が唯一の局所的局所最小値であることを示す。
論文 参考訳（メタデータ） (2020-02-16T22:15:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。