論文の概要: Communication Acceleration of Local Gradient Methods via an Accelerated
Primal-Dual Algorithm with Inexact Prox
- arxiv url: http://arxiv.org/abs/2207.03957v1
- Date: Fri, 8 Jul 2022 15:24:13 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-11 15:30:26.052099
- Title: Communication Acceleration of Local Gradient Methods via an Accelerated
Primal-Dual Algorithm with Inexact Prox
- Title（参考訳）: inexact proxを用いた高速化原始双対アルゴリズムによる局所勾配法の通信高速化
- Authors: Abdurakhmon Sadiev and Dmitry Kovalev and Peter Richt\'arik
- Abstract要約: 我々はMishchenko et al (2022)と同じ通信加速度を得る代替アルゴリズムを提案する。
我々のアプローチはChambolle and Pock (2011) の有名な手法に基づいており、いくつかの非自明な修正を加えている。
提案手法は,ネットワーク上での最適化にも適用可能であり,理論的改善も得られている。
- 参考スコア（独自算出の注目度）: 11.564643329398438
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Inspired by a recent breakthrough of Mishchenko et al (2022), who for the
first time showed that local gradient steps can lead to provable communication
acceleration, we propose an alternative algorithm which obtains the same
communication acceleration as their method (ProxSkip). Our approach is very
different, however: it is based on the celebrated method of Chambolle and Pock
(2011), with several nontrivial modifications: i) we allow for an inexact
computation of the prox operator of a certain smooth strongly convex function
via a suitable gradient-based method (e.g., GD, Fast GD or FSFOM), ii) we
perform a careful modification of the dual update step in order to retain
linear convergence. Our general results offer the new state-of-the-art rates
for the class of strongly convex-concave saddle-point problems with bilinear
coupling characterized by the absence of smoothness in the dual function. When
applied to federated learning, we obtain a theoretically better alternative to
ProxSkip: our method requires fewer local steps ($O(\kappa^{1/3})$ or
$O(\kappa^{1/4})$, compared to $O(\kappa^{1/2})$ of ProxSkip), and performs a
deterministic number of local steps instead. Like ProxSkip, our method can be
applied to optimization over a connected network, and we obtain theoretical
improvements here as well.
- Abstract（参考訳）: Mishchenko et al (2022) の最近のブレークスルーに触発されて、局所的な勾配ステップが証明可能な通信加速をもたらすことを初めて示し、その手法と同じ通信加速度を得る代替アルゴリズム(ProxSkip)を提案する。
しかし、我々のアプローチは、非常に異なる:それは、いくつかの非自明な修正を含む、有名なchambolle and pock (2011)の方法に基づいている。
一 適度な勾配法(例えば、GD、Fast GD、FSFOM)により、ある滑らかな凸関数のprox演算子の不正確な計算を可能にする。
二) 線形収束を維持するために、二重更新ステップを注意深く修正する。
両関数の滑らかさの欠如を特徴とする双線型カップリングを伴う強凸凹サドル点問題に対して,本研究の一般的な結果が得られた。
フェデレートラーニングに適用すると、理論上より優れたProxSkipの代替手段が得られる:我々の手法は、より少ない局所ステップ(O(\kappa^{1/3})$または$O(\kappa^{1/4})$)を必要とし、代わりに$O(\kappa^{1/2})$のProxSkipに対して決定論的数を実行する。
ProxSkipと同様に、この手法はネットワーク上での最適化にも適用でき、理論的改善も得られる。
関連論文リスト
- Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。
特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
論文 参考訳（メタデータ） (2024-09-23T13:11:37Z) - Adaptive Proximal Gradient Method for Convex Optimization [18.681222155879656]
凸最適化における2つの基本的な一階法、すなわち勾配降下法(GD)と近位勾配法(ProxGD)について検討する。
我々の焦点は、スムーズな関数の局所曲率情報を活用することによって、これらのアルゴリズムを完全に適応させることである。
本稿では,GD と ProxGD の適応バージョンを提案する。
論文 参考訳（メタデータ） (2023-08-04T11:37:08Z) - FedDA: Faster Framework of Local Adaptive Gradient Methods via Restarted
Dual Averaging [104.41634756395545]
フェデレートラーニング(Federated Learning, FL)は、大規模な分散データに取り組むための新たな学習パラダイムである。
局所適応勾配法のための新しいフレームワークである textbfFedDA を提案する。
textbfFedDA-MVR は適応FLアルゴリズムとしては初めてこの速度を実現することを示す。
論文 参考訳（メタデータ） (2023-02-13T05:10:30Z) - Two Losses Are Better Than One: Faster Optimization Using a Cheaper
Proxy [6.170898159041277]
本稿では,関連関数をプロキシとして利用することにより,目的物を計算困難勾配で最小化するアルゴリズムを提案する。
我々のアルゴリズムは、$delta$-smooth目的の勾配降下に一致する速度で収束を保証する。
我々のアルゴリズムは機械学習に多くの可能性があり、合成データ、物理シミュレータ、混合公開データ、プライベートデータなどを活用するための原則化された手段を提供する。
論文 参考訳（メタデータ） (2023-02-07T15:50:49Z) - Min-Max Optimization Made Simple: Approximating the Proximal Point
Method via Contraction Maps [77.8999425439444]
本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。
我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
論文 参考訳（メタデータ） (2023-01-10T12:18:47Z) - GradSkip: Communication-Accelerated Local Gradient Methods with Better
Computational Complexity [3.222802562733787]
本研究では,クライアントが通信に先立って複数の局所勾配型訓練を行えるようにすることで,通信コストの低減を目的とした分散最適化アルゴリズムのクラスについて検討する。
我々は、GradSkipという名前が同じ仮定の下で線形に収束する修正法を証明した。
論文 参考訳（メタデータ） (2022-10-28T20:59:06Z) - Momentum-inspired Low-Rank Coordinate Descent for Diagonally Constrained
SDPs [12.7944665592057]
本稿では,制約付き半有限計画法(SDP)を高速化した非自明なプログラムを用いて大規模に解くための,新しい,実用的で証明可能なアプローチを提案する。
論文 参考訳（メタデータ） (2021-06-16T13:35:40Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Acceleration Methods [57.202881673406324]
まず2次最適化問題を用いて加速法を2つ導入する。
我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。
我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
論文 参考訳（メタデータ） (2021-01-23T17:58:25Z) - A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints [10.578409461429626]
本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
論文 参考訳（メタデータ） (2020-09-23T20:02:00Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。