論文の概要: Lattice-Based Methods Surpass Sum-of-Squares in Clustering
- arxiv url: http://arxiv.org/abs/2112.03898v1
- Date: Tue, 7 Dec 2021 18:50:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-08 14:26:46.060764
- Title: Lattice-Based Methods Surpass Sum-of-Squares in Clustering
- Title（参考訳）: 格子に基づくクラスタリングにおける二乗和を超越する手法
- Authors: Ilias Zadik, Min Jae Song, Alexander S. Wein, Joan Bruna
- Abstract要約: クラスタリングは教師なし学習における基本的なプリミティブである。
最近の研究は、低次手法のクラスに対する低い境界を確立している。
意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
- 参考スコア（独自算出の注目度）: 98.46302040220395
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Clustering is a fundamental primitive in unsupervised learning which gives
rise to a rich class of computationally-challenging inference tasks. In this
work, we focus on the canonical task of clustering $d$-dimensional Gaussian
mixtures with unknown (and possibly degenerate) covariance. Recent works (Ghosh
et al.\ '20; Mao, Wein '21; Davis, Diaz, Wang '21) have established lower
bounds against the class of low-degree polynomial methods and the
sum-of-squares (SoS) hierarchy for recovering certain hidden structures planted
in Gaussian clustering instances. Prior work on many similar inference tasks
portends that such lower bounds strongly suggest the presence of an inherent
statistical-to-computational gap for clustering, that is, a parameter regime
where the clustering task is \textit{statistically} possible but no
\textit{polynomial-time} algorithm succeeds.
One special case of the clustering task we consider is equivalent to the
problem of finding a planted hypercube vector in an otherwise random subspace.
We show that, perhaps surprisingly, this particular clustering model
\textit{does not exhibit} a statistical-to-computational gap, even though the
aforementioned low-degree and SoS lower bounds continue to apply in this case.
To achieve this, we give a polynomial-time algorithm based on the
Lenstra--Lenstra--Lovasz lattice basis reduction method which achieves the
statistically-optimal sample complexity of $d+1$ samples. This result extends
the class of problems whose conjectured statistical-to-computational gaps can
be "closed" by "brittle" polynomial-time algorithms, highlighting the crucial
but subtle role of noise in the onset of statistical-to-computational gaps.
- Abstract（参考訳）: クラスタリングは教師なし学習において基本的なプリミティブであり、計算量の多い推論タスクのクラスを生み出します。
本研究では、未知の(そしておそらく退化)共分散を持つ$d$次元ガウス混合をクラスタリングする標準的なタスクに焦点を当てる。
最近の作品(Ghosh et al)。
\ '20; Mao, Wein '21; Davis, Diaz, Wang '21) は、ガウスのクラスタリングインスタンスに植えられた隠された構造を復元するための低次多項式法と総和二乗(SoS)階層に対する下界を確立した。
このような下位境界がクラスタリングに固有の統計的-計算的ギャップの存在を強く示唆する多くの類似した推論タスクに関する先行研究、すなわち、クラスタリングタスクが \textit{statistically} 可能であるが、 \textit{polynomial-time} アルゴリズムが成功するパラメータレシエーションが成功しない。
私たちが考えるクラスタリングタスクの特別なケースの1つは、無作為な部分空間に植えられた超キューブベクトルを見つける問題と等価である。
この場合、この特定のクラスタリングモデル \textit{does not exhibit} は、上述の低次およびsos下限が適用され続けているにもかかわらず、統計的-計算間ギャップであることを示している。
これを実現するために,Lenstra-Lenstra-Lovasz格子基底法に基づく多項式時間アルゴリズムを提案する。
この結果は、統計的-計算間ギャップが「脆い」多項式時間アルゴリズムによって「閉じる」ことができる問題のクラスを拡張し、統計-計算間ギャップの開始におけるノイズの重要かつ微妙な役割を強調する。
関連論文リスト
- Heteroskedastic Tensor Clustering [20.979358557219953]
我々は、$mathsfHightext-orderHeteroClustering$$mathsfHHC$という2段階の手法を提案する。
まず、$mathsfThresholdedDeflatedtext-HeteroPCA$と呼ばれる新しいスペクトルアルゴリズムを使ってテンソル部分空間の推定を行い、続いてクラスタノードを取得するためにおよそ$k$-meansを実行する。
我々のアルゴリズムは、SNRが計算限界を超える限り、正確なクラスタリングを確実に達成する。
論文 参考訳（メタデータ） (2023-11-04T02:50:40Z) - Gap-Free Clustering: Sensitivity and Robustness of SDP [6.996002801232415]
ブロックモデル(SBM)におけるグラフクラスタリングについて,大クラスタと小クラスタの両方の存在下で検討した。
以前の凸緩和アプローチは正確な回復を達成するため、$o(sqrtn)$の小さなクラスタを許可しないか、最小の回復クラスタと最大の非回復クラスタの間のサイズギャップを必要とする。
本研究では,これらの要求を除去し,クラスタサイズによらず,大規模クラスタを確実に復元する半定値プログラミング(SDP)に基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-29T21:27:21Z) - Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。
本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Simple and Scalable Sparse k-means Clustering via Feature Ranking [14.839931533868176]
直感的で実装が簡単で,最先端のアルゴリズムと競合する,スパースk平均クラスタリングのための新しいフレームワークを提案する。
本手法は,属性のサブセットのクラスタリングや部分的に観測されたデータ設定など,タスク固有のアルゴリズムに容易に一般化できる。
論文 参考訳（メタデータ） (2020-02-20T02:41:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。