論文の概要: 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条件を満たす場合に結果を拡張する。
最後に,本理論は,非凸分類実験や深層学習モデルの訓練において,大幅な改善が見られた。
関連論文リスト
- Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
楽観的勾配法はミニマックス最適化問題に対処するのに有用である。
従来のバージョンでは大きなバッチサイズが必要であり,Samevareps-generativeOGOGと呼ばれる新しい定式化を導入,解析する。
論文 参考訳(メタデータ) (2024-01-26T01:16:59Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Stochastic Distributed Optimization under Average Second-order
Similarity: Algorithms and Analysis [36.646876613637325]
マスタノードと$n-1$ローカルノードを含む有限サム分散最適化問題について検討する。
本稿では,SVRSとAccSVRSの2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-04-15T08:18:47Z) - Decentralized Weakly Convex Optimization Over the Stiefel Manifold [28.427697270742947]
我々は分散環境でスティーフェル多様体に焦点をあて、$nMn log-1)$のエージェントの連結ネットワークをテストする。
そこで本研究では,nMn log-1 以下の自然ステーションを強制的に強制する分散下位段階法 (DRSM)$ という手法を提案する。
論文 参考訳(メタデータ) (2023-03-31T02:56:23Z) - 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) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳(メタデータ) (2022-11-14T12:32:18Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。