論文の概要: Beyond Exponential Graph: Communication-Efficient Topologies for
Decentralized Learning via Finite-time Convergence
- arxiv url: http://arxiv.org/abs/2305.11420v1
- Date: Fri, 19 May 2023 04:08:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-22 16:23:30.969253
- Title: Beyond Exponential Graph: Communication-Efficient Topologies for
Decentralized Learning via Finite-time Convergence
- Title（参考訳）: 指数グラフを超えて:有限時間収束による分散学習のための通信効率の高いトポロジー
- Authors: Yuki Takezawa, Ryoma Sato, Han Bao, Kenta Niwa, Makoto Yamada
- Abstract要約: 高速なコンセンサス率と最小の最大度を組み合わせた新しいトポロジーを提案する。
Base-$(k + 1)$ Graph は指数グラフよりも高速収束率と通信効率の高い分散 SGD (DSGD) を提供する。
- 参考スコア（独自算出の注目度）: 29.574154815338
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Decentralized learning has recently been attracting increasing attention for
its applications in parallel computation and privacy preservation. Many recent
studies stated that the underlying network topology with a faster consensus
rate (a.k.a. spectral gap) leads to a better convergence rate and accuracy for
decentralized learning. However, a topology with a fast consensus rate, e.g.,
the exponential graph, generally has a large maximum degree, which incurs
significant communication costs. Thus, seeking topologies with both a fast
consensus rate and small maximum degree is important. In this study, we propose
a novel topology combining both a fast consensus rate and small maximum degree
called the Base-$(k + 1)$ Graph. Unlike the existing topologies, the Base-$(k +
1)$ Graph enables all nodes to reach the exact consensus after a finite number
of iterations for any number of nodes and maximum degree k. Thanks to this
favorable property, the Base-$(k + 1)$ Graph endows Decentralized SGD (DSGD)
with both a faster convergence rate and more communication efficiency than the
exponential graph. We conducted experiments with various topologies,
demonstrating that the Base-$(k + 1)$ Graph enables various decentralized
learning methods to achieve higher accuracy with better communication
efficiency than the existing topologies.
- Abstract（参考訳）: 分散学習は、並列計算とプライバシ保護におけるその応用に注目が集まっている。
最近の多くの研究は、より高速なコンセンサス率(スペクトルギャップ)を持つネットワークトポロジーは、分散学習においてより良い収束率と精度をもたらすと述べている。
しかし、例えば指数グラフのような高速なコンセンサスレートを持つトポロジーは、一般的に大きな最大次数を持ち、大きな通信コストがかかる。
したがって、高速なコンセンサス率と小さい最大度の両方を持つ位相を求めることが重要である。
本研究では,高速なコンセンサス率とBase-$(k + 1)$ Graphと呼ばれる最小次を併用した新しいトポロジーを提案する。
既存のトポロジとは異なり、base-$(k + 1)$ graph は全てのノードが任意のノード数と最大次数 k に対して有限個の反復の後に正確なコンセンサスに達することができる。
この好ましい性質のおかげで、Base-$(k + 1)$ Graph は指数グラフよりも高速収束率と通信効率の高い分散 SGD (DSGD) を提供する。
そこで我々は,Base-$(k + 1)$ Graph を用いて様々なトポロジを用いた実験を行い,既存のトポロジよりも高い通信効率で,分散学習を実現できることを示した。
関連論文リスト
- Graph as a feature: improving node classification with non-neural graph-aware logistic regression [2.952177779219163]
Graph-aware Logistic Regression (GLR) はノード分類タスク用に設計された非神経モデルである。
GNNにアクセスできる情報のごく一部しか使わない従来のグラフアルゴリズムとは異なり、提案モデルではノードの特徴とエンティティ間の関係を同時に活用する。
論文 参考訳（メタデータ） (2024-11-19T08:32:14Z) - Strongly Topology-preserving GNNs for Brain Graph Super-resolution [5.563171090433323]
脳グラフ超解像(英: Brain graph super- resolution, SR)は、ネットワーク神経科学において研究されていないが、非常に関連性の高い課題である。
現在のSR手法では、グラフ構造化データセットを処理できるため、グラフニューラルネットワーク(GNN)を活用している。
我々は、低分解能(LR)脳グラフのエッジ空間から高分解能(HR)双対グラフのノード空間への効率的なマッピングを開発する。
論文 参考訳（メタデータ） (2024-11-01T03:29:04Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Beyond spectral gap (extended): The role of the topology in
decentralized learning [58.48291921602417]
機械学習モデルのデータ並列最適化では、労働者はモデルの推定値を改善するために協力する。
現在の理論では、コラボレーションはトレーニング単独よりも学習率が大きいことを説明していない。
本稿では,疎結合分散最適化の正確な図面を描くことを目的とする。
論文 参考訳（メタデータ） (2023-01-05T16:53:38Z) - Discovering the Representation Bottleneck of Graph Neural Networks from
Multi-order Interactions [51.597480162777074]
グラフニューラルネットワーク(GNN)は、ノード機能を伝搬し、インタラクションを構築するためにメッセージパッシングパラダイムに依存している。
最近の研究は、異なるグラフ学習タスクはノード間の異なる範囲の相互作用を必要とすることを指摘している。
科学領域における2つの共通グラフ構築法、すなわち、emphK-nearest neighbor(KNN)グラフとemphfully-connected(FC)グラフについて検討する。
論文 参考訳（メタデータ） (2022-05-15T11:38:14Z) - Effects of Graph Convolutions in Deep Networks [8.937905773981702]
多層ネットワークにおけるグラフ畳み込みの効果に関する厳密な理論的理解を示す。
単一のグラフ畳み込みは、多層ネットワークがデータを分類できる手段間の距離のレギュレーションを拡大することを示す。
ネットワーク層間の異なる組み合わせに配置されたグラフ畳み込みの性能に関する理論的および実証的な知見を提供する。
論文 参考訳（メタデータ） (2022-04-20T08:24:43Z) - Exponential Graph is Provably Efficient for Decentralized Deep Training [30.817705471352614]
いわゆる指数グラフでは、すべてのノードが$O(log(n)$ 隣り合っていて、$n$ はノードの総数である。
この研究は、そのようなグラフが高速通信と効果的な平均化の両方に同時に結びつくことを証明している。
また、各ノードが反復ごとに1つの隣接ノードと通信する$log(n)$ 1-peer指数グラフの列は、共に正確な平均化を達成することができる。
論文 参考訳（メタデータ） (2021-10-26T02:33:39Z) - ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network [72.16255675586089]
本稿では、入力グラフと下流タスクに基づいて最適な曲率を適応的に学習する適応曲率探索ハイパーボリックグラフニューラルネットワークACE-HGNNを提案する。
複数の実世界のグラフデータセットの実験は、競争性能と優れた一般化能力を備えたモデル品質において、顕著で一貫したパフォーマンス改善を示す。
論文 参考訳（メタデータ） (2021-10-15T07:18:57Z) - Multi-hop Graph Convolutional Network with High-order Chebyshev
Approximation for Text Reasoning [15.65069702939315]
我々は高次動的チェビシェフ近似(HDGCN)を用いてスペクトルグラフ畳み込みネットワークを定義する。
高次チェビシェフ近似の過度な平滑化を緩和するために、線形計算複雑性を持つマルチボイトベースのクロスアテンション(MVCAttn)も提案されている。
論文 参考訳（メタデータ） (2021-06-08T07:49:43Z) - Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。
高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。
このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
論文 参考訳（メタデータ） (2020-07-03T09:30:07Z) - Quantized Decentralized Stochastic Learning over Directed Graphs [52.94011236627326]
有向グラフ上で通信する計算ノード間でデータポイントが分散される分散学習問題を考える。
モデルのサイズが大きくなるにつれて、分散学習は、各ノードが隣人にメッセージ(モデル更新)を送信することによる通信負荷の大きなボトルネックに直面します。
本稿では,分散コンセンサス最適化におけるプッシュサムアルゴリズムに基づく有向グラフ上の量子化分散学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-23T18:25:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。