論文の概要: Sketch-and-Lift: Scalable Subsampled Semidefinite Program for $K$-means Clustering

• arxiv url: http://arxiv.org/abs/2201.08226v1
• Date: Thu, 20 Jan 2022 15:31:28 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-21 17:43:05.778768
• Title: Sketch-and-Lift: Scalable Subsampled Semidefinite Program for $K$-means Clustering
• Title（参考訳）: Sketch-and-Lift:$K$-meansクラスタリングのためのスケーラブルなサブサンプル半定プログラム
• Authors: Yubo Zhuang, Xiaohui Chen, Yun Yang
• Abstract要約: セミデフィニティプログラミング(SDP)はクラスタリングなどの幅広い計算困難問題に対処するための強力なツールである。 本稿では,SDP緩和した$K$-meansクラスタリングを近似する線形時間複雑性アルゴリズムを提案する。 シミュレーション実験により,提案手法の統計的精度は最先端の高速クラスタリングアルゴリズムより優れていることが示された。
• 参考スコア（独自算出の注目度）: 16.153709556346417
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Semidefinite programming (SDP) is a powerful tool for tackling a wide range of computationally hard problems such as clustering. Despite the high accuracy, semidefinite programs are often too slow in practice with poor scalability on large (or even moderate) datasets. In this paper, we introduce a linear time complexity algorithm for approximating an SDP relaxed $K$-means clustering. The proposed sketch-and-lift (SL) approach solves an SDP on a subsampled dataset and then propagates the solution to all data points by a nearest-centroid rounding procedure. It is shown that the SL approach enjoys a similar exact recovery threshold as the $K$-means SDP on the full dataset, which is known to be information-theoretically tight under the Gaussian mixture model. The SL method can be made adaptive with enhanced theoretic properties when the cluster sizes are unbalanced. Our simulation experiments demonstrate that the statistical accuracy of the proposed method outperforms state-of-the-art fast clustering algorithms without sacrificing too much computational efficiency, and is comparable to the original $K$-means SDP with substantially reduced runtime.
• Abstract（参考訳）: semidefinite programming (sdp) は、クラスタリングのような幅広い計算困難問題に取り組むための強力なツールである。 高い精度にもかかわらず、半定値プログラムは、大規模な(あるいは適度な)データセットのスケーラビリティが低すぎるため、実際は遅すぎることが多い。 本稿では,SDP緩和した$K$-meansクラスタリングを近似する線形時間複雑性アルゴリズムを提案する。 提案したスケッチ・アンド・リフト(SL)アプローチは,サブサンプルデータセット上のSDPを解き,最寄りのセントロイドラウンドリング手順で全データポイントへの解を伝搬する。 SLアプローチは,ガウス混合モデルの下で情報理論的にきついことが知られている全データセット上の$K$-means SDPと同様の精度の回復しきい値を持つことが示された。 SL法は,クラスタサイズが不均衡な場合に拡張理論特性に適応させることができる。 シミュレーション実験により,提案手法の統計的精度は,計算効率を犠牲にすることなく,最先端の高速クラスタリングアルゴリズムよりも優れており,実行時間を大幅に削減したオリジナルの$K$-means SDPに匹敵することを示した。

関連論文リスト

• Statistically Optimal K-means Clustering via Nonnegative Low-rank Semidefinite Programming [25.210724274471914]
  K$-meansクラスタリングは、大規模なデータセットのパターンを識別する機械学習手法として広く使用されている。 本稿では,非負の低ランクな$K$-means分解問題を解くNMFライクなアルゴリズムについて考察する。 提案アルゴリズムは,スケーラビリティを維持しつつ,既存の最先端技術と比較して,誤クラスタリングエラーを著しく小さくする。
  論文  参考訳（メタデータ） (2023-05-29T00:39:55Z)
• Sketch-and-solve approaches to k-means clustering by semidefinite programming [14.930208990741132]
  我々は,k-meansクラスタリングのPeng-Wei半定緩和を高速化するためのスケッチ・アンド・ソルジ手法を提案する。 データが適切に分離された場合、k平均の最適なクラスタリングを特定する。 そうでなければ、我々のアプローチは最適k-平均値に高信頼な下界を与える。
  論文  参考訳（メタデータ） (2022-11-28T19:51:30Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Data [16.153709556346417]
  クラスタリングは広くデプロイされた学習ツールである。 iLA-SDPはEMよりも感度が低く、高次元データでは安定である。
  論文  参考訳（メタデータ） (2022-09-29T21:03:13Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。 最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。 提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
  論文  参考訳（メタデータ） (2022-06-14T08:14:14Z)
• Subspace clustering in high-dimensions: Phase transitions \& Statistical-to-Computational gap [24.073221004661427]
  部分空間クラスタリングを研究するための単純なモデルは、高次元の$k$-ガウス混合モデルである。 広帯域な高次元状態における統計的に最適な再構成誤差を正確に評価する。
  論文  参考訳（メタデータ） (2022-05-26T17:47:35Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• An Exact Algorithm for Semi-supervised Minimum Sum-of-Squares Clustering [0.5801044612920815]
  半教師付きMSSCのための分岐結合アルゴリズムを提案する。 背景知識はペアワイズ・マスタリンクと結びつかない制約として組み込まれている。 提案したグローバル最適化アルゴリズムは,実世界のインスタンスを最大800個のデータポイントまで効率的に解決する。
  論文  参考訳（メタデータ） (2021-11-30T17:08:53Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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