論文の概要: Stabilized Proximal-Point Methods for Federated Optimization
- arxiv url: http://arxiv.org/abs/2407.07084v1
- Date: Tue, 9 Jul 2024 17:56:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-10 16:57:59.120759
- Title: Stabilized Proximal-Point Methods for Federated Optimization
- Title（参考訳）: フェデレーション最適化のための安定化近点法
- Authors: Xiaowen Jiang, Anton Rodomanov, Sebastian U. Stich,
- Abstract要約: 非加速アルゴリズムの通信複雑性は、分散近位点アルゴリズムであるDANEによって達成される。
ハイブリッド射影-近点法に着想を得て,新しい分散アルゴリズムS-DANEを提案する。
S-DANEは、S-DANEと同様の局所計算効率を向上し、分散凸最適化のためのすべての既存手法の中で最もよく知られた通信複雑性を実現する。
- 参考スコア（独自算出の注目度）: 20.30761752651984
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In developing efficient optimization algorithms, it is crucial to account for communication constraints -- a significant challenge in modern federated learning settings. The best-known communication complexity among non-accelerated algorithms is achieved by DANE, a distributed proximal-point algorithm that solves local subproblems in each iteration and that can exploit second-order similarity among individual functions. However, to achieve such communication efficiency, the accuracy requirement for solving the local subproblems is slightly sub-optimal. Inspired by the hybrid projection-proximal point method, in this work, we i) propose a novel distributed algorithm S-DANE. This method adopts a more stabilized prox-center in the proximal step compared with DANE, and matches its deterministic communication complexity. Moreover, the accuracy condition of the subproblem is milder, leading to enhanced local computation efficiency. Furthermore, it supports partial client participation and arbitrary stochastic local solvers, making it more attractive in practice. We further ii) accelerate S-DANE, and show that the resulting algorithm achieves the best-known communication complexity among all existing methods for distributed convex optimization, with the same improved local computation efficiency as S-DANE.
- Abstract（参考訳）: 効率的な最適化アルゴリズムを開発する際には、コミュニケーションの制約を考慮することが重要です。
非加速アルゴリズムで最もよく知られている通信複雑性は、各イテレーションで局所的なサブプロブレムを解く分散近点アルゴリズムであるDANEによって達成され、個々の関数間の二階類似性を利用することができる。
しかし、そのような通信効率を達成するために、局所的なサブプロブレムを解くための精度要件はわずかに準最適である。
ハイブリッド射影-近位点法に着想を得たこの研究で我々は
i)新しい分散アルゴリズムS-DANEを提案する。
本手法は, DANEと比較して近位段階においてより安定化されたプロキシ中心を採用し, 決定論的通信複雑性に適合する。
さらに、サブプロブレムの精度は軽度であり、局所的な計算効率が向上する。
さらに、部分的なクライアント参加と任意の確率的局所解法をサポートしており、実際はより魅力的である。
さらに
ii) S-DANE を高速化し,S-DANE と同等の局所計算効率を向上した分散凸最適化法において,提案アルゴリズムが既知の通信複雑性を実現することを示す。
関連論文リスト
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。
この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。
我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
論文 参考訳（メタデータ） (2024-05-28T10:28:45Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Decentralized Inexact Proximal Gradient Method With Network-Independent
Stepsizes for Convex Composite Optimization [39.352542703876104]
本稿では,非方向および接続ネットワーク上での分散凸複合最適化について考察する。
CTA(Combine-Then-Adapt)に基づく新しい分散アルゴリズムは、非協調的なネットワーク非依存の定数ステップサイズの下で提案される。
論文 参考訳（メタデータ） (2023-02-07T03:50:38Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD
for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
ローカル手法は通信時間を短縮する有望なアプローチの1つである。
局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
論文 参考訳（メタデータ） (2022-02-12T15:12:17Z) - 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) - On Accelerating Distributed Convex Optimizations [0.0]
本稿では,分散マルチエージェント凸最適化問題について検討する。
提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。
実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
論文 参考訳（メタデータ） (2021-08-19T13:19:54Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。
提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。
加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
論文 参考訳（メタデータ） (2020-06-11T18:49:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。