論文の概要: Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous
Decentralized Optimization
- arxiv url: http://arxiv.org/abs/2207.07543v1
- Date: Fri, 15 Jul 2022 15:37:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-18 16:30:23.682555
- Title: Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous
Decentralized Optimization
- Title（参考訳）: Pick your Nebor: 高速非同期分散最適化のためのローカルガウス・サウスウェルルール
- Authors: Marina Costantini, Nikolaos Liakopoulos, Panayotis Mertikopoulos,
Thrasyvoulos Spyropoulos
- Abstract要約: 分散最適化環境では、$n$最適化ノードのネットワーク内の各エージェント$i$は、プライベート関数$f_i$を持つ。
最適化対応の選択ルールを導入し、高い2倍のコスト改善で隣人を選択する。
提案したセットワイズGSルールは,ネットワークの最大次数による高速化を実現する。
- 参考スコア（独自算出の注目度）: 37.85806148420504
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In decentralized optimization environments, each agent $i$ in a network of
$n$ optimization nodes possesses a private function $f_i$, and nodes
communicate with their neighbors to cooperatively minimize the aggregate
objective $\sum_{i=1}^n f_i$. In this setting, synchronizing the nodes' updates
incurs significant communication overhead and computational costs, so much of
the recent literature has focused on the analysis and design of asynchronous
optimization algorithms where agents activate and communicate at arbitrary
times, without requiring a global synchronization enforcer. Nonetheless, in
most of the work on the topic, active nodes select a neighbor to contact based
on a fixed probability (e.g., uniformly at random), a choice that ignores the
optimization landscape at the moment of activation. Instead, in this work we
introduce an optimization-aware selection rule that chooses the neighbor with
the highest dual cost improvement (a quantity related to a consensus-based
dualization of the problem at hand). This scheme is related to the coordinate
descent (CD) method with a Gauss-Southwell (GS) rule for coordinate updates; in
our setting however, only a subset of coordinates is accessible at each
iteration (because each node is constrained to communicate only with its direct
neighbors), so the existing literature on GS methods does not apply. To
overcome this difficulty, we develop a new analytical framework for smooth and
strongly convex $f_i$ that covers the class of set-wise CD algorithms -- a
class that directly applies to decentralized scenarios, but is not limited to
them -- and we show that the proposed set-wise GS rule achieves a speedup by a
factor of up to the maximum degree in the network (which is of the order of
$\Theta(n)$ in highly connected graphs). The speedup predicted by our
theoretical analysis is subsequently validated in numerical experiments with
synthetic data.
- Abstract（参考訳）: 分散最適化環境では、n$最適化ノードのネットワーク内の各エージェント $i$ はプライベート関数 $f_i$ を持ち、ノードは隣人と通信し、集約対象 $\sum_{i=1}^n f_i$ を協調的に最小化する。
この設定では、ノードの更新の同期は重要な通信オーバーヘッドと計算コストを伴い、近年の文献の多くは、エージェントが任意のタイミングで起動し通信する非同期最適化アルゴリズムの分析と設計に焦点をあてている。
それでも、このトピックに関するほとんどの作業において、アクティブなノードは、アクティベーション時点の最適化のランドスケープを無視する選択肢である固定確率(例えば、ランダムにランダムに)に基づいて、隣人を選択する。
代わりに、我々は、最も高い双対コスト改善(目の前の問題のコンセンサスに基づく双対化に関連する量)で隣人を選択する最適化対応の選択ルールを導入する。
この方式は座標降下法(CD)とガウス・サウスウェル法(GS)による座標更新と関係があるが、我々の設定では、座標のサブセットは各繰り返しでのみアクセス可能である(各ノードが直接隣人としか通信できないため)ため、GS法に関する既存の文献は適用されない。
この難しさを克服するために、我々は、セットワイズcdアルゴリズムのクラス(分散化されたシナリオに直接適用されるが、それらに限定されないクラス)をカバーする、滑らかで強凸な$f_i$のための新しい分析フレームワークを開発し、提案されたセットワイズgsルールが、ネットワークの最大次数(高連結グラフでは$\theta(n)$のオーダー)の倍のスピードアップを達成することを示す。
理論解析によって予測される高速化は、合成データを用いた数値実験で検証される。
関連論文リスト
- Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization [8.670873561640903]
分散環境下での非平滑な非平滑な目的に対する(delta,,ilon$)-定常点の有限時間解析について検討する。
$Oは分散非滑らかな最適化のための最初の有限時間保証である。
論文 参考訳（メタデータ） (2024-06-03T16:09:34Z) - Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。
この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。
我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
論文 参考訳（メタデータ） (2024-05-28T10:28:45Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。
我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。
アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
論文 参考訳（メタデータ） (2022-10-31T17:59:29Z) - Decentralized Multi-Task Stochastic Optimization With Compressed
Communications [22.31884634659446]
本稿では,ノードにおけるローカル情報可用性の2つのモデルに対して,アルゴリズムを開発し,性能バウンダリを求める。
グローバルな最小値からの逸脱と制約の違反は$mathcalO(T-frac12)$と$mathcalO(T-frac14)$によって上界されることを示す。
論文 参考訳（メタデータ） (2021-12-23T05:54:42Z) - The Minimax Complexity of Distributed Optimization [0.0]
分散最適化に適用可能な古典的なオラクルフレームワークの拡張である「グラフオラクルモデル」を紹介します。
私は「間欠的コミュニケーション設定」の具体例に焦点をあてる
コンベックス設定におけるSGD(Local Descent)アルゴリズムの理論的特性を解析する。
論文 参考訳（メタデータ） (2021-09-01T15:18:33Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Decentralized Optimization with Heterogeneous Delays: a Continuous-Time
Approach [6.187780920448871]
非同期アルゴリズムを解析するための新しい連続時間フレームワークを提案する。
我々は,スムーズな凸関数と強い凸関数の和を最小化するために,完全に非同期な分散アルゴリズムを記述する。
論文 参考訳（メタデータ） (2021-06-07T13:09:25Z) - A hybrid variance-reduced method for decentralized stochastic non-convex
optimization [15.447966950703947]
textttGTHSGDアルゴリズムは、グローバルな勾配を追跡するためにネットワークを実装している。
textttGTHSGDは、必要なエラートレランス$epsilon$が十分小さいときに、ネットワークの複雑さを$O(n-1)$にします。
論文 参考訳（メタデータ） (2021-02-12T20:13:05Z) - The Min-Max Complexity of Distributed Stochastic Convex Optimization
with Intermittent Communication [61.60069865891783]
間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。
本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
論文 参考訳（メタデータ） (2021-02-02T16:18:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。