論文の概要: Decentralized Optimization in Time-Varying Networks with Arbitrary Delays

• arxiv url: http://arxiv.org/abs/2405.19513v1
• Date: Wed, 29 May 2024 20:51:38 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-31 19:06:28.639691
• Title: Decentralized Optimization in Time-Varying Networks with Arbitrary Delays
• Title（参考訳）: 任意遅延を伴う時間変数ネットワークにおける分散最適化
• Authors: Tomas Ortega, Hamid Jafarkhani,
• Abstract要約: 通信遅延によるネットワークの分散最適化問題を考察する。 そのようなネットワークの例としては、協調機械学習、センサーネットワーク、マルチエージェントシステムなどがある。 通信遅延を模倣するため、ネットワークに仮想非計算ノードを追加し、有向グラフを生成する。
• 参考スコア（独自算出の注目度）: 22.40154714677385
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We consider a decentralized optimization problem for networks affected by communication delays. Examples of such networks include collaborative machine learning, sensor networks, and multi-agent systems. To mimic communication delays, we add virtual non-computing nodes to the network, resulting in directed graphs. This motivates investigating decentralized optimization solutions on directed graphs. Existing solutions assume nodes know their out-degrees, resulting in limited applicability. To overcome this limitation, we introduce a novel gossip-based algorithm, called DT-GO, that does not need to know the out-degrees. The algorithm is applicable in general directed networks, for example networks with delays or limited acknowledgment capabilities. We derive convergence rates for both convex and non-convex objectives, showing that our algorithm achieves the same complexity order as centralized Stochastic Gradient Descent. In other words, the effects of the graph topology and delays are confined to higher-order terms. Additionally, we extend our analysis to accommodate time-varying network topologies. Numerical simulations are provided to support our theoretical findings.
• Abstract（参考訳）: 通信遅延によるネットワークの分散最適化問題を考察する。 そのようなネットワークの例としては、協調機械学習、センサーネットワーク、マルチエージェントシステムなどがある。 通信遅延を模倣するため、ネットワークに仮想非計算ノードを追加し、有向グラフを生成する。 このことは、有向グラフ上の分散最適化ソリューションの調査を動機付けている。 既存のソリューションでは、ノードはアウト学位を知っていると仮定し、適用性は制限される。 この制限を克服するために、DT-GOと呼ばれる新しいゴシップベースのアルゴリズムを導入する。 このアルゴリズムは一般的な有向ネットワーク、例えば遅延や限定的な認知能力を持つネットワークに適用できる。 我々は凸目標と非凸目標の両方に対して収束率を導出し、このアルゴリズムが集中確率勾配Descentと同じ複雑さのオーダーを達成することを示す。 言い換えれば、グラフ位相と遅延の影響は高次項に限られる。 さらに、時間変化のネットワークトポロジに対応するために分析を拡張します。 理論的知見を裏付ける数値シミュレーションが提案されている。

関連論文リスト

• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-28T10:28:45Z)
• Deploying Graph Neural Networks in Wireless Networks: A Link Stability Viewpoint [13.686715722390149]
  グラフニューラルネットワーク(GNN)は、幅広いグラフアプリケーションで有望なパフォーマンスを示している。 無線システムでは、ノード間の通信は通常、無線のフェードと受信機のノイズによりGNNが劣化する。
  論文  参考訳（メタデータ） (2024-05-09T14:37:08Z)
• Estimation Network Design framework for efficient distributed optimization [3.3148826359547514]
  本稿では,分散イテレーションの解析と設計のためのグラフ理論言語である推定ネットワーク設計(END)を紹介する。 ENDアルゴリズムは特定の問題インスタンスのスパーシ性を活用し、通信オーバーヘッドを低減し、冗長性を最小化するために調整することができる。 特に、ADMM、AugDGM、Push-Sum DGDなど、確立された多くのメソッドのスパーシティ対応バージョンについて検討する。
  論文  参考訳（メタデータ） (2024-04-23T17:59:09Z)
• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  時間グラフは連続時間を通してノード間の動的相互作用を示す。 本研究では,周辺地域全体と時間的グラフ畳み込みの新たな手法を提案する。 提案するTAP-GNNは,予測性能とオンライン推論遅延の両面で,既存の時間グラフ手法よりも優れた性能を示す。
  論文  参考訳（メタデータ） (2023-04-15T08:17:18Z)
• Graph Neural Networks for Power Allocation in Wireless Networks with Full Duplex Nodes [10.150768420975155]
  ユーザ間の相互干渉のため、無線ネットワークにおける電力割り当て問題はしばしば自明ではない。 グラフグラフニューラルネットワーク(GNN)は、これらの問題に対処するための有望なアプローチとして最近登場し、無線ネットワークの基盤となるトポロジを活用するアプローチである。
  論文  参考訳（メタデータ） (2023-03-27T10:59:09Z)
• Learning Cooperative Beamforming with Edge-Update Empowered Graph Neural Networks [29.23937571816269]
  グラフエッジ上での協調ビームフォーミングを学習するためのエッジグラフニューラルネットワーク(Edge-GNN)を提案する。 提案したEdge-GNNは、最先端の手法よりも計算時間をはるかに短くして、より高い和率を達成する。
  論文  参考訳（メタデータ） (2022-11-23T02:05:06Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• Decentralized Optimization with Heterogeneous Delays: a Continuous-Time Approach [6.187780920448871]
  非同期アルゴリズムを解析するための新しい連続時間フレームワークを提案する。 我々は,スムーズな凸関数と強い凸関数の和を最小化するために,完全に非同期な分散アルゴリズムを記述する。
  論文  参考訳（メタデータ） (2021-06-07T13:09:25Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  パケット遅延を最小限に抑えるため,制約付き待ち行列ネットワークにおけるスケジューリングの問題を考える。 我々は、利用可能な原子ポリシーよりも優れたスケジューラを生成するポリシー勾配に基づく強化学習アルゴリズムを使用する。
  論文  参考訳（メタデータ） (2021-05-01T10:18:34Z)
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks [124.33353902111939]
  本稿では,時間変動ネットワーク上の滑らかかつ強凸分散最適化のための高速化手法である adom を提案する。 ネットワーク構造のみに依存する一定の要因まで、その通信は加速されたNesterovメソッドのそれと同じです。
  論文  参考訳（メタデータ） (2021-02-18T09:37:20Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)

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

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