論文の概要: Stabilized Proximal-Point Methods for Federated Optimization

• arxiv url: http://arxiv.org/abs/2407.07084v2
• Date: Sun, 3 Nov 2024 10:13:18 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-08 22:51:19.940633
• 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. The best-known communication complexity among non-accelerated algorithms is achieved by DANE, a distributed proximal-point algorithm that solves local subproblems at each iteration and that can exploit second-order similarity among individual functions. However, to achieve such communication efficiency, the algorithm requires solving local subproblems sufficiently accurately resulting in slightly sub-optimal local complexity. Inspired by the hybrid-projection proximal-point method, in this work, we propose a novel distributed algorithm S-DANE. Compared to DANE, this method uses an auxiliary sequence of prox-centers while maintaining the same deterministic communication complexity. Moreover, the accuracy condition for solving the subproblem is milder, leading to enhanced local computation efficiency. Furthermore, S-DANE supports partial client participation and arbitrary stochastic local solvers, making it attractive in practice. We further accelerate S-DANE and show that the resulting algorithm achieves the best-known communication complexity among all existing methods for distributed convex optimization while still enjoying good local computation efficiency as S-DANE. Finally, we propose adaptive variants of both methods using line search, obtaining the first provably efficient adaptive algorithms that could exploit local second-order similarity without the prior knowledge of any parameters.
• Abstract（参考訳）: 効率的な最適化アルゴリズムを開発する際には、コミュニケーションの制約を考慮することが重要です。 非加速アルゴリズムで最もよく知られている通信複雑性は、各イテレーションで局所的なサブプロブレムを解く分散近点アルゴリズムであるDANEによって達成され、個々の関数間の二階類似性を利用することができる。 しかし、そのような通信効率を達成するために、アルゴリズムは局所的なサブプロブレムを十分正確に解く必要がある。 本研究では,ハイブリッド射影近点法に着想を得て,新しい分散アルゴリズムS-DANEを提案する。 DANEと比較して、この方法は、同じ決定論的通信複雑性を維持しながら、プロキシ中心の補助シーケンスを使用する。 さらに、サブプロブレムを解くための精度条件は緩やかであり、局所的な計算効率が向上する。 さらに、S-DANEは部分的なクライアント参加と任意の確率的局所解法をサポートしており、実際は魅力的である。 さらに、S-DANEを高速化し、S-DANEとして良好な局所計算効率を保ちながら、分散凸最適化のためのすべての既存手法の中で最もよく知られた通信複雑性を実現することを示す。 最後に,線形探索を用いた2つの手法の適応的変種を提案し,パラメータの事前知識を使わずに,局所的な2階類似性を活用可能な適応アルゴリズムを初めて提案する。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• High-Speed Resource Allocation Algorithm Using a Coherent Ising Machine for NOMA Systems [3.6406488220483326]
  NOMA手法の有効性を十分に活用する上で重要な課題は、リソース割り当ての最適化である。 NOMAシステムにおけるチャネル割り当てのためのコヒーレントIsing Machine(CIM)に基づく最適化手法を提案する。 提案手法は, 高速化と最適解の両面において優れていることを示す。
  論文  参考訳（メタデータ） (2022-12-03T09:22:54Z)
• 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)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。 スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。 その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
  論文  参考訳（メタデータ） (2021-03-10T03:16:12Z)
• Optimal and Practical Algorithms for Smooth and Strongly Convex Decentralized Optimization [21.555331273873175]
  ネットワークのノードにまたがるスムーズな凸関数の和を分散化最小化する作業について検討する。 本稿では,この分散最適化問題に対する2つの新しいアルゴリズムを提案し,複雑性を保証する。
  論文  参考訳（メタデータ） (2020-06-21T11:23:20Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。 提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。 加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2020-06-11T18:49:06Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。