論文の概要: Federated Optimization Algorithms with Random Reshuffling and Gradient
Compression
- arxiv url: http://arxiv.org/abs/2206.07021v1
- Date: Tue, 14 Jun 2022 17:36:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-15 15:33:13.642121
- Title: Federated Optimization Algorithms with Random Reshuffling and Gradient
Compression
- Title(参考訳): ランダムリシャッフルと勾配圧縮を用いたフェデレーション最適化アルゴリズム
- Authors: Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov, Igor Sokolov,
Ahmed Khaled, Konstantin Burlachenko, Peter Richt\'arik
- Abstract要約: 勾配圧縮法と非置換サンプリング法を初めて解析する。
制御イテレートを用いて勾配量子化から生じる分散を減少させる方法を示す。
既存のアルゴリズムを改善するいくつかの設定について概説する。
- 参考スコア(独自算出の注目度): 2.7554288121906296
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Gradient compression is a popular technique for improving communication
complexity of stochastic first-order methods in distributed training of machine
learning models. However, the existing works consider only with-replacement
sampling of stochastic gradients. In contrast, it is well-known in practice and
recently confirmed in theory that stochastic methods based on
without-replacement sampling, e.g., Random Reshuffling (RR) method, perform
better than ones that sample the gradients with-replacement. In this work, we
close this gap in the literature and provide the first analysis of methods with
gradient compression and without-replacement sampling. We first develop a
distributed variant of random reshuffling with gradient compression (Q-RR), and
show how to reduce the variance coming from gradient quantization through the
use of control iterates. Next, to have a better fit to Federated Learning
applications, we incorporate local computation and propose a variant of Q-RR
called Q-NASTYA. Q-NASTYA uses local gradient steps and different local and
global stepsizes. Next, we show how to reduce compression variance in this
setting as well. Finally, we prove the convergence results for the proposed
methods and outline several settings in which they improve upon existing
algorithms.
- Abstract(参考訳): グラディエント圧縮は、機械学習モデルの分散トレーニングにおける確率的一階法の通信複雑性を改善するための一般的な手法である。
しかし、既存の研究は確率勾配の非置換サンプリングのみを考慮する。
対照的に、実際にはよく知られており、近年理論上は、非置換サンプリング(例えばランダムリシャッフル法(RR))に基づく確率的手法が、置換を伴う勾配をサンプリングする手法よりも優れていることが確認されている。
そこで本研究では,このギャップを文献に埋め込み,勾配圧縮法と無置換サンプリング法の最初の分析を行う。
まず、勾配圧縮(Q-RR)を用いたランダムリシャッフルの分散変種を開発し、制御イテレートを用いて勾配量子化から生じる分散を減少させる方法を示す。
次に,フェデレーション学習アプリケーションへの適合性を高めるため,局所計算を取り入れ,q-nastyaと呼ばれるq-rrの変種を提案する。
q-nastyaはローカル勾配ステップと異なるローカルステップとグローバルステップを使用する。
次に、この設定における圧縮のばらつきを低減する方法を示す。
最後に,提案手法の収束結果を証明し,既存のアルゴリズムを改良したいくつかの設定を概説する。
関連論文リスト
- Stochastic Gradient Descent for Gaussian Processes Done Right [41.76406324030368]
正方形損失を用いたガウス過程の回帰を最適化する。
この問題に対する最も一般的なアプローチは、共役最適化のような正確な解法を適用することや、問題の低次バージョンに直接適用することである。
近年, 深層学習の推進により, 勾配降下が代替手段として勢いを増していることが明らかとなった。
論文 参考訳(メタデータ) (2023-10-31T16:15:13Z) - Variance reduction techniques for stochastic proximal point algorithms [5.871583927216651]
本稿では,SVRG,SAGAの近位バージョンと,そのスムーズな凸関数に対する変種について紹介する。
数値実験により, 勾配法に対する近似分散低減法の利点を実証した。
論文 参考訳(メタデータ) (2023-08-18T05:11:50Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Communication-Efficient Federated Learning via Quantized Compressed
Sensing [82.10695943017907]
提案フレームワークは,無線機器の勾配圧縮とパラメータサーバの勾配再構成からなる。
勾配スペーシフィケーションと量子化により、我々の戦略は1ビット勾配圧縮よりも高い圧縮比を達成することができる。
圧縮を行わない場合とほぼ同じ性能を実現できることを示す。
論文 参考訳(メタデータ) (2021-11-30T02:13:54Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳(メタデータ) (2021-10-20T02:25:25Z) - Learning Sampling Policy for Faster Derivative Free Optimization [100.27518340593284]
ランダムサンプリングではなく,ZO最適化における摂動を生成するためのサンプリングポリシを学習する,新たな強化学習ベースのZOアルゴリズムを提案する。
その結果,ZO-RLアルゴリズムはサンプリングポリシを学習することでZO勾配の分散を効果的に低減し,既存のZOアルゴリズムよりも高速に収束できることが示唆された。
論文 参考訳(メタデータ) (2021-04-09T14:50:59Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳(メタデータ) (2020-12-21T17:29:58Z) - Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
本稿では,Tchakaloff と Carath'eodory の古典的な結果から着想を得た手法を提案する。
我々は、測定値の低減を行う降下ステップを適応的に選択する。
これをBlock Coordinate Descentと組み合わせることで、測定の削減を極めて安価に行えるようにします。
論文 参考訳(メタデータ) (2020-06-02T17:52:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。