論文の概要: Permutation Compressors for Provably Faster Distributed Nonconvex Optimization

• arxiv url: http://arxiv.org/abs/2110.03300v1
• Date: Thu, 7 Oct 2021 09:38:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-08 15:54:18.963198
• Title: Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
• Title（参考訳）: 分散非凸最適化のための置換圧縮機
• Authors: Rafa{\l} Szlendak and Alexander Tyurin and Peter Richt\'arik
• Abstract要約: 本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。 MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
• 参考スコア（独自算出の注目度）: 68.8204255655161
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the MARINA method of Gorbunov et al (2021) -- the current state-of-the-art distributed non-convex optimization method in terms of theoretical communication complexity. Theoretical superiority of this method can be largely attributed to two sources: the use of a carefully engineered biased stochastic gradient estimator, which leads to a reduction in the number of communication rounds, and the reliance on {\em independent} stochastic communication compression operators, which leads to a reduction in the number of transmitted bits within each communication round. In this paper we i) extend the theory of MARINA to support a much wider class of potentially {\em correlated} compressors, extending the reach of the method beyond the classical independent compressors setting, ii) show that a new quantity, for which we coin the name {\em Hessian variance}, allows us to significantly refine the original analysis of MARINA without any additional assumptions, and iii) identify a special class of correlated compressors based on the idea of {\em random permutations}, for which we coin the term Perm$K$, the use of which leads to $O(\sqrt{n})$ (resp. $O(1 + d/\sqrt{n})$) improvement in the theoretical communication complexity of MARINA in the low Hessian variance regime when $d\geq n$ (resp. $d \leq n$), where $n$ is the number of workers and $d$ is the number of parameters describing the model we are learning. We corroborate our theoretical results with carefully engineered synthetic experiments with minimizing the average of nonconvex quadratics, and on autoencoder training with the MNIST dataset.
• Abstract（参考訳）: 本稿では,Gorbunov et al (2021) の MARINA 法について検討する。 この手法の理論的優位性は、慎重に設計されたバイアス付き確率勾配推定器を使用することで、通信ラウンドの数を減少させ、また、各通信ラウンド内の送信ビット数を減少させるような、独立な確率的通信圧縮演算子に依存するという2つの情報源に大きく寄与する。 本論文では, i)MARINAの理論を拡張して、従来からある独立した圧縮機の設定を超えて、より広い種類の潜在的に相関した圧縮機を支持する。 二 ヘシアン分散(em hessian variance)という名称で表される新しい量により、追加の仮定なしにマリーナの本来の分析を著しく洗練することができることを示すこと。 iii) "em random permutations} という概念に基づいて相関圧縮機の特殊クラスを特定し、ここでは "perm$k$" という用語をつくり、そこでは$o(\sqrt{n})$ (resp) となる。 O(1 + d/\sqrt{n})$)$d\geq n$ (resp) のとき、低ヘッセン分散状態におけるMARINAの理論的通信複雑性の改善。 $d \leq n$) ここで$n$はワーカーの数、$d$は私たちが学習しているモデルを記述するパラメータの数です。 我々は,非凸二次数の平均を最小化し,mnistデータセットを用いたオートエンコーダトレーニングを念入りに設計した合成実験を行い,理論結果を裏付ける。

関連論文リスト

• Theoretical Convergence Guarantees for Variational Autoencoders [2.8167997311962942]
  変分オートエンコーダ(VAE)は、複雑なデータ分布からサンプリングするために使われる一般的な生成モデルである。 本稿では, グラディエントDescentアルゴリズムとAdamアルゴリズムの両方を用いてトレーニングしたVAEに対して, 非漸近収束保証を提供することにより, このギャップを埋めることを目的とする。 我々の理論的分析は、Linear VAEとDeep Gaussian VAEの両方、および$beta$-VAEやIWAEを含むいくつかのVAEの変種に適用できる。
  論文  参考訳（メタデータ） (2024-10-22T07:12:38Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。 我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。 我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
  論文  参考訳（メタデータ） (2024-05-10T09:58:47Z)
• Improving the Worst-Case Bidirectional Communication Complexity for Nonconvex Distributed Optimization under Function Similarity [92.1840862558718]
  ダウンリンク圧縮のための新しい手法であるMARINA-Pを導入する。 置換圧縮機を用いたMARINA-Pは、作業者数に応じてサーバ間通信の複雑さを向上できることを示す。 本稿では,MARINA-Pとアップリンク圧縮とモーメントステップを組み合わせた手法であるM3を導入する。
  論文  参考訳（メタデータ） (2024-02-09T13:58:33Z)
• Correlated Quantization for Faster Nonconvex Distributed Optimization [1.2744523252873352]
  量子化 (starAli et al., 2017) は、各通信ラウンドにおける伝送ビットの体積を減少させる重要な(確率的な)圧縮技術である。 我々は、事前分散非最適化アルゴリズムMARINA(Gbunov et al., 2022)を解析する。 我々は、MARINAの理論的枠組みを拡張して、潜在的に相関のある圧縮機をかなり幅広い範囲に展開する。
  論文  参考訳（メタデータ） (2024-01-10T19:29:17Z)
• Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
  本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。 一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
  論文  参考訳（メタデータ） (2023-05-28T19:40:46Z)
• DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization [77.34726150561087]
  我々は,分散最適化問題に対する新しい手法であるDASHAを開発し,解析する。 MARINAとは異なり、新しいDASHAとDASHA-MVRは圧縮ベクターのみを送信し、ノードを同期しないため、学習をより実用的なものにしている。
  論文  参考訳（メタデータ） (2022-02-02T20:10:40Z)
• Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes [7.648784748888189]
  Selective Multiple Power Iterations (SMPI) はスパイクを回復する重要な問題に対処する新しいアルゴリズムである。 これらの予期せぬ性能は、ノイズが信号の回復に重要な役割を果たす強力なメカニズムに起因していることを示す。 これらの結果は、実用的および理論的応用の両方に強い影響を与える可能性がある。
  論文  参考訳（メタデータ） (2021-12-23T01:46:41Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。 目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。 この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
  論文  参考訳（メタデータ） (2020-06-26T09:05:58Z)
• On Biased Compression for Distributed Learning [55.89300593805943]
  バイアス圧縮機が単一ノードと分散設定の両方において線形収束率をもたらすことを初めて示す。 理論的保証と実用性能を期待できる新しいバイアス圧縮機を提案する。
  論文  参考訳（メタデータ） (2020-02-27T19:52:24Z)

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

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