論文の概要: Escaping Saddle Points with Compressed SGD

• arxiv url: http://arxiv.org/abs/2105.10090v1
• Date: Fri, 21 May 2021 01:56:43 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-25 12:33:57.193391
• Title: Escaping Saddle Points with Compressed SGD
• Title（参考訳）: 圧縮SGDによるサドル点のエスケープ
• Authors: Dmitrii Avdiukhin, Grigory Yaroslavtsev
• Abstract要約: 勾配降下(SGD)は大規模分散機械学習の最適化手法である。 勾配圧縮によるSGD拡張は$varepsilon$1次定常点に収束することを示す。 勾配がリプシッツでないとき、RandomK圧縮機を持つSGDは、SGDと同じ数の反復数を持つ$varepsilon$-SOSPに収束する。
• 参考スコア（独自算出の注目度）: 8.014396597444296
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic gradient descent (SGD) is a prevalent optimization technique for large-scale distributed machine learning. While SGD computation can be efficiently divided between multiple machines, communication typically becomes a bottleneck in the distributed setting. Gradient compression methods can be used to alleviate this problem, and a recent line of work shows that SGD augmented with gradient compression converges to an $\varepsilon$-first-order stationary point. In this paper we extend these results to convergence to an $\varepsilon$-second-order stationary point ($\varepsilon$-SOSP), which is to the best of our knowledge the first result of this type. In addition, we show that, when the stochastic gradient is not Lipschitz, compressed SGD with RandomK compressor converges to an $\varepsilon$-SOSP with the same number of iterations as uncompressed SGD [Jin et al.,2021] (JACM), while improving the total communication by a factor of $\tilde \Theta(\sqrt{d} \varepsilon^{-3/4})$, where $d$ is the dimension of the optimization problem. We present additional results for the cases when the compressor is arbitrary and when the stochastic gradient is Lipschitz.
• Abstract（参考訳）: 確率勾配勾配(SGD)は大規模分散機械学習の最適化手法である。 SGD計算は複数のマシンに効率的に分割できるが、通信は通常分散環境でボトルネックとなる。 この問題を緩和するためにグラディエント圧縮法が利用可能であり、最近の研究は、勾配圧縮によるSGD拡張が$\varepsilon$-first-orderの定常点に収束することを示している。 本稿では,これらの結果から2次定常点である\varepsilon$-sosp (\varepsilon$-sosp) への収束まで拡張する。 さらに、確率勾配がリプシッツでない場合、RandomK圧縮機で圧縮されたSGDは、圧縮されていないSGD [Jin et al.,2021] (JACM)と同数の反復数を持つ$\varepsilon$-SOSPに収束する一方で、$\tilde \Theta(\sqrt{d} \varepsilon^{-3/4})$.d$は最適化問題の次元である。 コンプレッサーが任意の場合と確率勾配がリプシッツである場合について追加の結果を示す。

関連論文リスト

• Flattened one-bit stochastic gradient descent: compressed distributed optimization with controlled variance [55.01966743652196]
  パラメータ・サーバ・フレームワークにおける圧縮勾配通信を用いた分散勾配降下(SGD)のための新しいアルゴリズムを提案する。 平坦な1ビット勾配勾配勾配法(FO-SGD)は2つの単純なアルゴリズムの考え方に依存している。
  論文  参考訳（メタデータ） (2024-05-17T21:17:27Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  機械学習とネットワーク最適化では、ミスの数と優れたキャッシュを最小化するため、シャッフルSGDのようなアルゴリズムが人気である。 本稿では任意のデータ順序付けによる収束特性SGDアルゴリズムについて述べる。
  論文  参考訳（メタデータ） (2023-05-30T17:47:27Z)
• CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence [9.11726703830074]
  本稿では,通信制限条件下で分散最適化問題を解くことを検討する。 CEDASと呼ばれる圧縮精密拡散法について述べる。 特に、いつ時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時時
  論文  参考訳（メタデータ） (2023-01-14T09:49:15Z)
• ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
  本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。 我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-01-01T18:51:29Z)
• Stochastic Gradient Methods with Compressed Communication for Decentralized Saddle Point Problems [0.0]
  圧縮に基づく勾配アルゴリズムを2つ開発し,非滑らかな凸凸の強い凹凸点問題のクラスを解く。 最初のアルゴリズムは、一般的な設定のための圧縮(C-RDPSG)を用いたRestartベースの分散近似勾配法である。 次に,有限和設定のための圧縮 (C-DPSVRG) を用いた分散近似変数低減勾配アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-28T15:17:19Z)
• Communication-Efficient Federated Learning via Quantized Compressed Sensing [82.10695943017907]
  提案フレームワークは,無線機器の勾配圧縮とパラメータサーバの勾配再構成からなる。 勾配スペーシフィケーションと量子化により、我々の戦略は1ビット勾配圧縮よりも高い圧縮比を達成することができる。 圧縮を行わない場合とほぼ同じ性能を実現できることを示す。
  論文  参考訳（メタデータ） (2021-11-30T02:13:54Z)
• On the Benefits of Multiple Gossip Steps in Communication-Constrained Decentralized Optimization [29.42301299741866]
  ステップサイズが一定である$O(logfrac1epsilon)$の反復を$O(logfrac1epsilon)$とすることで、スムーズな非圧縮勾配目的に対する最適値の$epsilon$に収束できることを示す。 我々の知る限り、これは圧縮された通信圧縮パラメータの下での非最適化の収束結果を導出した最初の研究である。
  論文  参考訳（メタデータ） (2020-11-20T21:17:32Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• On Biased Compression for Distributed Learning [55.89300593805943]
  バイアス圧縮機が単一ノードと分散設定の両方において線形収束率をもたらすことを初めて示す。 理論的保証と実用性能を期待できる新しいバイアス圧縮機を提案する。
  論文  参考訳（メタデータ） (2020-02-27T19:52:24Z)

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

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