論文の概要: A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip

• arxiv url: http://arxiv.org/abs/2504.09792v1
• Date: Mon, 14 Apr 2025 01:34:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-15 16:50:32.280197
• Title: A Tale of Two Learning Algorithms: Multiple Stream Random Walk and Asynchronous Gossip
• Title（参考訳）: 2つの学習アルゴリズムの物語:マルチストリームランダムウォークと非同期ゴシップ
• Authors: Peyman Gholami, Hulya Seferoglu,
• Abstract要約: 我々はまず、複数のストリーム(ウォーク)を用いたランダムウォークベース学習アルゴリズムの設計と解析を行う。 本稿では,MW w.r.t (計算),ウォールクロック時間,通信の収束解析について述べる。 また、「非同期ゴシップ」に対する収束解析を行い、その収束の包括的解析が欠如していることに注目した。
• 参考スコア（独自算出の注目度）: 4.3707341422218215
• License:
• Abstract: Although gossip and random walk-based learning algorithms are widely known for decentralized learning, there has been limited theoretical and experimental analysis to understand their relative performance for different graph topologies and data heterogeneity. We first design and analyze a random walk-based learning algorithm with multiple streams (walks), which we name asynchronous "Multi-Walk (MW)". We provide a convergence analysis for MW w.r.t iteration (computation), wall-clock time, and communication. We also present a convergence analysis for "Asynchronous Gossip", noting the lack of a comprehensive analysis of its convergence, along with the computation and communication overhead, in the literature. Our results show that MW has better convergence in terms of iterations as compared to Asynchronous Gossip in graphs with large diameters (e.g., cycles), while its relative performance, as compared to Asynchronous Gossip, depends on the number of walks and the data heterogeneity in graphs with small diameters (e.g., complete graphs). In wall-clock time analysis, we observe a linear speed-up with the number of walks and nodes in MW and Asynchronous Gossip, respectively. Finally, we show that MW outperforms Asynchronous Gossip in communication overhead, except in small-diameter topologies with extreme data heterogeneity. These results highlight the effectiveness of each algorithm in different graph topologies and data heterogeneity. Our codes are available for reproducibility.
• Abstract（参考訳）: ゴシップとランダムウォークに基づく学習アルゴリズムは、分散学習で広く知られているが、異なるグラフトポロジとデータ不均一性に対する相対的性能を理解するための理論的および実験的分析は限られている。 まず,複数のストリーム(ウォーク)を用いてランダムなウォークベース学習アルゴリズムを設計,解析し,非同期な「Multi-Walk (MW)」と呼ぶ。 本稿では,MWw.r.t反復(計算),ウォールクロック時間,通信の収束解析を行う。 また,「非同期ゴシップ」に対する収束解析を行い,その収束の包括的解析の欠如と,計算と通信のオーバーヘッドについて述べる。 以上の結果から, MW は大径グラフ (例えば, サイクル) の非同期ゴシップと比較して, 繰り返しの収束度が良く, 相対的な性能は, 小径グラフ (例えば, 完全グラフ) の歩行数とデータ不均一性に依存することが明らかとなった。 壁面時間解析では,MW と Asynchronous Gossip の歩行数とノード数との線形スピードアップをそれぞれ観測する。 最後に,データヘテロジニティを持つ小径位相を除いて,通信オーバヘッドにおいて,MWが非同期ゴシップより優れていることを示す。 これらの結果は、異なるグラフトポロジとデータ不均一性における各アルゴリズムの有効性を浮き彫りにする。 私たちのコードは再現可能である。

関連論文リスト

• Online Proximal ADMM for Graph Learning from Streaming Smooth Signals [9.34612743192798]
  我々は,潜伏グラフ上でスムーズな観測ストリームを用いたオンライングラフ学習のための新しいアルゴリズムを開発した。 我々のモダス・オペランは、グラフ信号を逐次処理し、メモリと計算コストを抑えることです。 提案手法は,現在最先端のオンライングラフ学習ベースラインと比較して,(準最適性の観点から)追跡性能が向上することを示す。
  論文  参考訳（メタデータ） (2024-09-19T17:12:03Z)
• Asynchronous Local Computations in Distributed Bayesian Learning [8.516532665507835]
  本稿では,高速な計算と通信オーバヘッドを同時に低減するために,ゴシップに基づく通信を提案する。 我々は、特に低データ範囲において、より高速な初期収束と性能精度の向上を観察する。 UCI MLレポジトリのガンマ望遠鏡とmHealthデータセットで,それぞれ平均78%,90%以上の分類精度を達成した。
  論文  参考訳（メタデータ） (2023-11-06T20:11:41Z)
• AsGrad: A Sharp Unified Analysis of Asynchronous-SGD Algorithms [45.90015262911875]
  不均一な環境で分散SGDのための非同期型アルゴリズムを解析する。 また,本分析の副産物として,ランダムなきついSGDのような勾配型アルゴリズムの保証を示す。
  論文  参考訳（メタデータ） (2023-10-31T13:44:53Z)
• DIGEST: Fast and Communication Efficient Decentralized Learning with Local Updates [4.3707341422218215]
  広く検討されている分散学習アルゴリズムは、Gossipとランダムウォークベースの学習である。 高速で通信効率のよい非同期分散学習機構DIGESTを設計する。 我々は、ロジスティック回帰とディープニューラルネットワークResNet20のためのシングルストリームおよびマルチストリームDIGESTの性能を評価する。
  論文  参考訳（メタデータ） (2023-07-14T22:58:20Z)
• Personalized Decentralized Multi-Task Learning Over Dynamic Communication Graphs [59.96266198512243]
  本稿では,正と負の相関関係を持つタスクに対する分散・フェデレーション学習アルゴリズムを提案する。 本アルゴリズムでは,タスク間の相関関係を自動的に計算し,コミュニケーショングラフを動的に調整して相互に有益なタスクを接続し,互いに悪影響を及ぼす可能性のあるタスクを分離する。 合成ガウスデータセットと大規模セレブ属性(CelebA)データセットについて実験を行った。
  論文  参考訳（メタデータ） (2022-12-21T18:58:24Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  グラフの混合重みとノード間のデータ不均一性の関係に収束の依存性を特徴付ける。 グラフが現在の勾配を混合する能力を定量化する計量法を提案する。 そこで本研究では,パラメータを周期的かつ効率的に最適化する手法を提案する。
  論文  参考訳（メタデータ） (2022-04-13T15:54:35Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Correlation Clustering in Constant Many Parallel Rounds [42.10280805559555]
  相関クラスタリングは教師なし学習において中心的なトピックであり、MLやデータマイニングに多くの応用がある。 本研究では,従来よりもかなり高速な超並列計算(MPC)アルゴリズムを提案する。 我々のアルゴリズムは,ノード数にメモリサブリニアを持つマシンを使用し,一定回数のラウンドでのみ実行しながら,一定の近似を返す。
  論文  参考訳（メタデータ） (2021-06-15T21:45:45Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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