論文の概要: Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond

• arxiv url: http://arxiv.org/abs/2110.10342v1
• Date: Wed, 20 Oct 2021 02:25:25 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-22 16:23:51.852899
• Title: Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
• Title（参考訳）: シャッフル機能付きミニバッチ対ローカルSGD:タイトコンバージェンス境界を超えて
• Authors: Chulhee Yun, Shashank Rajput, Suvrit Sra
• Abstract要約: シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。 ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。 我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
• 参考スコア（独自算出の注目度）: 63.59034509960994
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In distributed learning, local SGD (also known as federated averaging) and its simple baseline minibatch SGD are widely studied optimization methods. Most existing analyses of these methods assume independent and unbiased gradient estimates obtained via with-replacement sampling. In contrast, we study shuffling-based variants: minibatch and local Random Reshuffling, which draw stochastic gradients without replacement and are thus closer to practice. For smooth functions satisfying the Polyak-{\L}ojasiewicz condition, we obtain convergence bounds (in the large epoch regime) which show that these shuffling-based variants converge faster than their with-replacement counterparts. Moreover, we prove matching lower bounds showing that our convergence analysis is tight. Finally, we propose an algorithmic modification called synchronized shuffling that leads to convergence rates faster than our lower bounds in near-homogeneous settings.
• Abstract（参考訳）: 分散学習では、局所SGD(フェデレート平均化とも呼ばれる)とその単純なベースラインミニバッチSGDが広く研究されている。 これらの手法の既存の分析のほとんどは、非依存で偏りのない勾配推定を with-replacement sampling によって得られる。 対照的に、我々はシャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について研究し、置換せずに確率勾配を描き、したがって実践に近づいた。 polyak-{\l}ojasiewicz条件を満たす滑らかな関数に対して、これらのシャッフルベースの変種は、それらの再配置条件よりも高速に収束することを示す収束境界(大きなエポック領域)を得る。 さらに, 収束解析が厳密であることを示す下界の一致を証明した。 最後に,ほぼ均質な設定において,下限よりも収束速度が速い同期シャッフリングと呼ばれるアルゴリズム修正を提案する。

関連論文リスト

• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  グラデーション、クリッピングは、優れた高確率保証を導き出すアルゴリズムの鍵となる要素の1つである。 クリッピングは、合成および分散最適化の一般的な方法の収束を損なう可能性がある。
  論文  参考訳（メタデータ） (2023-10-03T07:49:17Z)
• SGDA with shuffling: faster convergence for nonconvex-P{\L} minimax optimization [18.668531108219415]
  逐次降下勾配(SGDA)を用いた最小最適化問題に対する理論的アプローチを提案する。 我々は,ポリアック・ロジャシエヴィチ(PL)幾何を用いて,非凹凸対象に対するSGDA-LLの同時的および交互的目的を解析した。 我々のレートはミニバッチGDARRにも拡張され、完全な勾配勾配降下勾配 (GDA) の既知率はほとんど回復しない。 最後に, 2 時間スケール GDA の包括的下限について述べる。
  論文  参考訳（メタデータ） (2022-10-12T08:05:41Z)
• Sampling without Replacement Leads to Faster Rates in Finite-Sum Minimax Optimization [12.794526174053134]
  滑らかな有限サム最小値最適化のための勾配アルゴリズムの収束速度を解析する。 このようなアルゴリズムの多くは、置換のないサンプリングポイントが、置換したサンプリングよりも高速な収束をもたらすことを示している。
  論文  参考訳（メタデータ） (2022-06-07T00:37:37Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data [0.0]
  ストリーミングフレームワークは、時系列に現れる時間変化のミニバッチを使用して最適化問題を解決するのに類似している。 我々は、様々な勾配に基づくアルゴリズムの漸近収束率を提供する。 時間変化したミニバッチに応じて学習率を選択して収束を加速する方法を示す。
  論文  参考訳（メタデータ） (2021-09-15T06:58:23Z)
• Differentiable Annealed Importance Sampling and the Perils of Gradient Noise [68.44523807580438]
  Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。 差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。 我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
  論文  参考訳（メタデータ） (2021-07-21T17:10:14Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Incremental Without Replacement Sampling in Nonconvex Optimization [0.0]
  経験的リスクに対する最小限の分解法は、一般に近似設定で分析される。 一方、このような手法の現代的な実装は漸進的であり、それらは置換せずにサンプリングに依存しており、利用可能な分析は極めて少ない。 我々は、多変数な漸進勾配スキームを解析することにより、後者の変分に対する収束保証を提供する。
  論文  参考訳（メタデータ） (2020-07-15T09:17:29Z)
• Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization [15.82816385434718]
  本稿では、滑らかで凸な損失と凸正則化器を最小化するための勾配アルゴリズムの収束解析のための統一定理を提案する。 我々は、Gorbunov, Hanzely & Richt'arik (2020) の統一解析を拡張し、損失関数が強く凸であるという要求を下げる。 我々の統一解析は、近位SGD、分散還元法、量子化、およびいくつかの座標降下型法などの既存のアルゴリズムのホストに適用できる。
  論文  参考訳（メタデータ） (2020-06-20T13:40:27Z)

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

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