論文の概要: Correlation Clustering in Constant Many Parallel Rounds
- arxiv url: http://arxiv.org/abs/2106.08448v1
- Date: Tue, 15 Jun 2021 21:45:45 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-18 09:55:19.042007
- Title: Correlation Clustering in Constant Many Parallel Rounds
- Title（参考訳）: 定数多並列ラウンドにおける相関クラスタリング
- Authors: Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovi\'c, Ashkan
Norouzi-Fard, Nikos Parotsidis, Jakub Tarnawski
- Abstract要約: 相関クラスタリングは教師なし学習において中心的なトピックであり、MLやデータマイニングに多くの応用がある。
本研究では,従来よりもかなり高速な超並列計算(MPC)アルゴリズムを提案する。
我々のアルゴリズムは,ノード数にメモリサブリニアを持つマシンを使用し,一定回数のラウンドでのみ実行しながら,一定の近似を返す。
- 参考スコア（独自算出の注目度）: 42.10280805559555
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Correlation clustering is a central topic in unsupervised learning, with many
applications in ML and data mining. In correlation clustering, one receives as
input a signed graph and the goal is to partition it to minimize the number of
disagreements. In this work we propose a massively parallel computation (MPC)
algorithm for this problem that is considerably faster than prior work. In
particular, our algorithm uses machines with memory sublinear in the number of
nodes in the graph and returns a constant approximation while running only for
a constant number of rounds. To the best of our knowledge, our algorithm is the
first that can provably approximate a clustering problem on graphs using only a
constant number of MPC rounds in the sublinear memory regime. We complement our
analysis with an experimental analysis of our techniques.
- Abstract（参考訳）: 相関クラスタリングは教師なし学習において中心的なトピックであり、MLやデータマイニングに多くの応用がある。
相関クラスタリングでは、符号付きグラフを入力として受信し、不一致の数を最小限に抑えるために分割する。
本研究では,従来よりもかなり高速な超並列計算(MPC)アルゴリズムを提案する。
特に,本アルゴリズムでは,グラフ内のノード数にメモリサブリニアを持つマシンを使用し,一定数のラウンドのみを実行しながら定数近似を返却する。
我々の知る限り、我々のアルゴリズムは、サブ線形メモリシステムにおいて、一定数のMPCラウンドのみを用いてグラフ上のクラスタリング問題を確実に近似できる最初のアルゴリズムである。
我々は、我々の技術の実験的な分析で分析を補完する。
関連論文リスト
- A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。
汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。
MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
論文 参考訳（メタデータ） (2024-07-19T08:29:12Z) - Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。
まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。
補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
論文 参考訳（メタデータ） (2024-04-24T18:39:18Z) - A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Massively-Parallel Heat Map Sorting and Applications To Explainable
Clustering [1.544681800932596]
我々は,クラスタ(ラベル)を保存しながら,点と次元を再順序付けし,マージする熱マップソート問題を導入する。
クラスタが接続されている場合、すなわち複数のクラスタに分割されず、2つのクラスタがマージされない場合、クラスタは保存される。
NP-hard特殊ケースに対する近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-14T07:53:52Z) - Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。
推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。
提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
論文 参考訳（メタデータ） (2023-03-30T15:48:26Z) - 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) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
カットベースの有向グラフ(グラフ)クラスタリングは、しばしばクラスタ内あるいはクラスタ間の疎結合を見つけることに焦点を当てる。
フローベースのクラスタリングでは、クラスタ間のエッジは一方向を向く傾向にあり、マイグレーションデータ、フードウェブ、トレーディングデータに見出されている。
論文 参考訳（メタデータ） (2022-03-02T20:07:04Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-11-30T05:40:14Z) - Differentially Private Clustering: Tight Approximation Ratios [57.89473217052714]
基本的なクラスタリング問題に対して,効率的な微分プライベートアルゴリズムを提案する。
この結果から,SampleとAggregateのプライバシーフレームワークのアルゴリズムの改善が示唆された。
1-Clusterアルゴリズムで使用されるツールの1つは、ClosestPairのより高速な量子アルゴリズムを適度な次元で得るために利用できる。
論文 参考訳（メタデータ） (2020-08-18T16:22:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。