論文の概要: DASHA: Distributed Nonconvex Optimization with Communication
Compression, Optimal Oracle Complexity, and No Client Synchronization
- arxiv url: http://arxiv.org/abs/2202.01268v1
- Date: Wed, 2 Feb 2022 20:10:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-04 14:24:41.840306
- Title: DASHA: Distributed Nonconvex Optimization with Communication
Compression, Optimal Oracle Complexity, and No Client Synchronization
- Title（参考訳）: dasha: 通信圧縮、oracleの最適複雑さ、クライアント同期なしの分散非凸最適化
- Authors: Alexander Tyurin, Peter Richt\'arik
- Abstract要約: 我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。
MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
- 参考スコア（独自算出の注目度）: 77.34726150561087
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop and analyze DASHA: a new family of methods for nonconvex
distributed optimization problems. When the local functions at the nodes have a
finite-sum or an expectation form, our new methods, DASHA-PAGE and
DASHA-SYNC-MVR, improve the theoretical oracle and communication complexity of
the previous state-of-the-art method MARINA by Gorbunov et al. (2020). In
particular, to achieve an epsilon-stationary point, and considering the random
sparsifier RandK as an example, our methods compute the optimal number of
gradients $\mathcal{O}\left(\frac{\sqrt{m}}{\varepsilon\sqrt{n}}\right)$ and
$\mathcal{O}\left(\frac{\sigma}{\varepsilon^{3/2}n}\right)$ in finite-sum and
expectation form cases, respectively, while maintaining the SOTA communication
complexity $\mathcal{O}\left(\frac{d}{\varepsilon \sqrt{n}}\right)$.
Furthermore, unlike MARINA, the new methods DASHA, DASHA-PAGE and DASHA-MVR
send compressed vectors only and never synchronize the nodes, which makes them
more practical for federated learning. We extend our results to the case when
the functions satisfy the Polyak-Lojasiewicz condition. Finally, our theory is
corroborated in practice: we see a significant improvement in experiments with
nonconvex classification and training of deep learning models.
- Abstract（参考訳）: 非凸分散最適化問題に対する新しい手法であるDASHAを開発し解析する。
DASHA-PAGEとDASHA-SYNC-MVRは,ノードの局所関数が有限サムあるいは期待形式を持つ場合,Gorbunovらによる従来の最先端手法MARINA(2020)の理論的オラクルと通信複雑性を改善する。
特に、エプシロン定常点を達成するために、ランダムスペーサーRandKを例に挙げると、我々の手法は勾配の最適数を計算する$\mathcal{O}\left(\frac{\sqrt{m}}{\varepsilon\sqrt{n}}\right)$と$\mathcal{O}\left(\frac{\sigma}{\varepsilon^{3/2}n}\right)$を、SOTA通信複雑性を保ちながら、それぞれ有限サムおよび期待形式の場合で$\mathcal{O}\left(\frac{d}{\varepsilon \sqrt{n}}\right)$である。
さらに、MARINAとは異なり、新しいDASHA、DASHA-PAGE、DASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、フェデレーション学習においてより実用的である。
我々は、関数がpolyak-lojasiewicz条件を満たす場合に結果を拡張する。
最後に,本理論は,非凸分類実験や深層学習モデルの訓練において,大幅な改善が見られた。
関連論文リスト
- Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentum [30.01198677588252]
1次アルゴリズムは、$varepsilon-stationary pointを見つけるのに少なくとも$mathcalO(varepsilonepsilon-4)$ complexityを必要とする。
本稿では,高効率な変動複雑性を生かした新しい運動量アルゴリズムを提案する。
本手法の有効性は実世界のデータセットを用いてロジスティック回帰を用いて検証する。
論文 参考訳（メタデータ） (2024-06-18T20:14:52Z) - Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations [92.1840862558718]
実用的な分散システムでは、労働者は概して均質ではなく、非常に多様な処理時間を持つ。
本稿では、任意に遅い計算を扱うための新しい並列手法Freyaを提案する。
Freyaは従来の手法と比較して,複雑性の保証が大幅に向上していることを示す。
論文 参考訳（メタデータ） (2024-05-24T13:33:30Z) - Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
楽観的勾配法はミニマックス最適化問題に対処するのに有用である。
従来のバージョンでは大きなバッチサイズが必要であり,Samevareps-generativeOGOGと呼ばれる新しい定式化を導入,解析する。
論文 参考訳（メタデータ） (2024-01-26T01:16:59Z) - Stochastic Distributed Optimization under Average Second-order
Similarity: Algorithms and Analysis [36.646876613637325]
マスタノードと$n-1$ローカルノードを含む有限サム分散最適化問題について検討する。
本稿では,SVRSとAccSVRSの2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-15T08:18:47Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation
Constrained Optimization [88.0031283949404]
多くの実世界の問題は複雑な非機能的制約を持ち、多くのデータポイントを使用する。
提案手法は,従来最もよく知られた結果で既存手法よりも優れた性能を示す。
論文 参考訳（メタデータ） (2022-12-19T14:48:54Z) - Federated Minimax Optimization: Improved Convergence Analyses and
Algorithms [32.062312674333775]
我々は、最小限の最適化を考慮し、GANのようなモダンな機械学習アプリケーションの多くを普及させています。
我々は,既存の文献における収束通信の保証を改善する,新しい,より厳密な解析アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-03-09T16:21:31Z) - Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。
提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
論文 参考訳（メタデータ） (2020-03-30T15:37:50Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳（メタデータ） (2020-02-09T09:56:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。