論文の概要: Locally Adaptive Federated Learning via Stochastic Polyak Stepsizes
- arxiv url: http://arxiv.org/abs/2307.06306v1
- Date: Wed, 12 Jul 2023 17:02:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-13 12:11:54.314270
- Title: Locally Adaptive Federated Learning via Stochastic Polyak Stepsizes
- Title(参考訳): 確率的ポリークステップサイズによる局所適応型フェデレーション学習
- Authors: Sohom Mukherjee, Nicolas Loizou, Sebastian U. Stich
- Abstract要約: FedAvgのような最先端のフェデレーション学習アルゴリズムは、最高のパフォーマンスを達成するために、慎重に調整されたステップサイズを必要とする。
FedSPSとFedDecSPS(FedSPSとFedDecSPS)を新たに提案する。
我々は、幾何条件(過パラメトリゼーション)が満たされるとき、FedSPSが強い凸に線形に収束し、凸設定でサブ線形に収束することを証明し、一般の場合、解の近傍に収束する。
- 参考スコア(独自算出の注目度): 33.449007398247865
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: State-of-the-art federated learning algorithms such as FedAvg require
carefully tuned stepsizes to achieve their best performance. The improvements
proposed by existing adaptive federated methods involve tuning of additional
hyperparameters such as momentum parameters, and consider adaptivity only in
the server aggregation round, but not locally. These methods can be inefficient
in many practical scenarios because they require excessive tuning of
hyperparameters and do not capture local geometric information. In this work,
we extend the recently proposed stochastic Polyak stepsize (SPS) to the
federated learning setting, and propose new locally adaptive and nearly
parameter-free distributed SPS variants (FedSPS and FedDecSPS). We prove that
FedSPS converges linearly in strongly convex and sublinearly in convex settings
when the interpolation condition (overparametrization) is satisfied, and
converges to a neighborhood of the solution in the general case. We extend our
proposed method to a decreasing stepsize version FedDecSPS, that converges also
when the interpolation condition does not hold. We validate our theoretical
claims by performing illustrative convex experiments. Our proposed algorithms
match the optimization performance of FedAvg with the best tuned
hyperparameters in the i.i.d. case, and outperform FedAvg in the non-i.i.d.
case.
- Abstract(参考訳): fedavgのような最先端のフェデレーション学習アルゴリズムは、最高のパフォーマンスを達成するために注意深く調整されたステップを必要とする。
既存の適応フェデレーション手法によって提案された改善は、運動量パラメータなどの追加のハイパーパラメータのチューニングを含み、サーバアグリゲーションラウンドのみに適応性を考慮するが、局所的ではない。
これらの方法は、ハイパーパラメータの過度なチューニングを必要とし、局所的な幾何学的情報をキャプチャしないため、多くの実践シナリオでは非効率である。
本研究では,最近提案された確率的Polyak Stepize(SPS)をフェデレーション学習環境に拡張し,局所適応型でパラメータフリーに近い分散SPS変種(FedSPS,FedDecSPS)を提案する。
補間条件(オーバーパラメトリゼーション)が満たされた場合、FedSPSは強い凸に線形に収束し、凸設定でサブリニアに収束し、一般の場合、解の近傍に収束することを示す。
我々は提案手法を段階化バージョンであるFedDecSPSに拡張し、補間条件が保たない場合も収束する。
実測凸実験により理論的主張を検証した。
提案アルゴリズムは,FedAvgの最適化性能を,i.d.の場合で最高のチューニングハイパーパラメータと一致させ,i.d.の場合ではFedAvgより優れる。
関連論文リスト
- Moreau Envelope ADMM for Decentralized Weakly Convex Optimization [55.2289666758254]
本稿では,分散最適化のための乗算器の交互方向法(ADMM)の近位変種を提案する。
数値実験の結果,本手法は広く用いられている手法よりも高速かつ堅牢であることが示された。
論文 参考訳(メタデータ) (2023-08-31T14:16:30Z) - Adaptive SGD with Polyak stepsize and Line-search: Robust Convergence
and Variance Reduction [26.9632099249085]
AdaSPSとAdaSLSと呼ばれる2種類の新しいSPSとSLSを提案し、非補間条件における収束を保証する。
我々は, AdaSPS と AdaSLS に新しい分散低減技術を導入し, $smashwidetildemathcalO(n+1/epsilon)$グラデーション評価を必要とするアルゴリズムを得る。
論文 参考訳(メタデータ) (2023-08-11T10:17:29Z) - FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization [53.78643974257301]
多くの現代のML問題は、ミニマックスと合成最適化を仮定したネストされた双レベルプログラミングに該当する。
我々は、一般的なネスト問題に対処するフェデレーション付き交互勾配法を提案する。
論文 参考訳(メタデータ) (2022-05-04T17:48:55Z) - Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants
via the Mirror Stochastic Polyak Stepsize [20.376216873620763]
比較的滑らかで滑らかな凸最適化の下でのミラー降下(SMD)の収束について検討した。
我々は、新しい適応的なステップサイズスキーム、ミラーポリアクステップサイズ(mSPS)を提案する。
論文 参考訳(メタデータ) (2021-10-28T19:49:40Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳(メタデータ) (2021-10-20T02:25:25Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - The Role of Momentum Parameters in the Optimal Convergence of Adaptive
Polyak's Heavy-ball Methods [12.93796690939018]
適応型Polyak's Heavy-ball (HB) 法は最適な個人収束率を$O(frac1sqrtt)$とする。
新しい解析では,hb運動量とその時間的変動が凸最適化の高速化にどのように役立つかを示す。
論文 参考訳(メタデータ) (2021-02-15T02:57:14Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - FedSplit: An algorithmic framework for fast federated optimization [40.42352500741025]
本稿では,分散凸最小化を付加構造で解くアルゴリズムのクラスであるFedSplitを紹介する。
これらの手法は, 中間局所量の不正確な計算に対して, 確実に堅牢であることを示す。
論文 参考訳(メタデータ) (2020-05-11T16:30:09Z) - Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast
Convergence [30.393999722555154]
本稿では,古典的ポリアクステップサイズ (Polyak, 1987) の亜次法でよく用いられる変種を提案する。
The proposed Polyak step-size (SPS) is a attractive choice for set the learning rate for gradient descent。
論文 参考訳(メタデータ) (2020-02-24T20:57:23Z) - Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
適応性は現代最適化理論において重要であるが、研究されていない性質である。
提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
論文 参考訳(メタデータ) (2020-02-13T05:42:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。