論文の概要: 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)$のオーダー)の倍のスピードアップを達成することを示す。
理論解析によって予測される高速化は、合成データを用いた数値実験で検証される。
関連論文リスト
- 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) - Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD
for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
ローカル手法は通信時間を短縮する有望なアプローチの1つである。
局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-02-12T15:12:17Z) - Decentralized Multi-Task Stochastic Optimization With Compressed
Communications [22.31884634659446]
本稿では,ノードにおけるローカル情報可用性の2つのモデルに対して,アルゴリズムを開発し,性能バウンダリを求める。
グローバルな最小値からの逸脱と制約の違反は$mathcalO(T-frac12)$と$mathcalO(T-frac14)$によって上界されることを示す。
論文 参考訳(メタデータ) (2021-12-23T05:54:42Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳(メタデータ) (2021-10-24T04:03:00Z) - DESTRESS: Computation-Optimal and Communication-Efficient Decentralized
Nonconvex Finite-Sum Optimization [43.31016937305845]
インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。
非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。
詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
論文 参考訳(メタデータ) (2021-10-04T03:17:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。