論文の概要: Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems

• arxiv url: http://arxiv.org/abs/2506.04126v1
• Date: Wed, 04 Jun 2025 16:17:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 21:20:14.451765
• Title: Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
• Title（参考訳）: 小エポック数増分グラディエントDescenceは、意外にもIll-Conditioned問題で遅い
• Authors: Yujun Kim, Jaeyoung Cha, Chulhee Yun,
• Abstract要約: 滑らかな凸関数について, ナイーブ変種であるインクリメンタルグラディエントDescent (IGD) について検討した。 解析の結果,小エポック状態においては,低い関数が強く凸している場合にIGDが驚くほど現れることが明らかとなった。 置換に基づくSGDが、この小さなエポック状態においてより早く収束できるかどうかはまだ分かっていない。
• 参考スコア（独自算出の注目度）: 10.65078014704416
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent theoretical results demonstrate that the convergence rates of permutation-based SGD (e.g., random reshuffling SGD) are faster than uniform-sampling SGD; however, these studies focus mainly on the large epoch regime, where the number of epochs $K$ exceeds the condition number $\kappa$. In contrast, little is known when $K$ is smaller than $\kappa$, and it is still a challenging open question whether permutation-based SGD can converge faster in this small epoch regime (Safran and Shamir, 2021). As a step toward understanding this gap, we study the naive deterministic variant, Incremental Gradient Descent (IGD), on smooth and strongly convex functions. Our lower bounds reveal that for the small epoch regime, IGD can exhibit surprisingly slow convergence even when all component functions are strongly convex. Furthermore, when some component functions are allowed to be nonconvex, we prove that the optimality gap of IGD can be significantly worse throughout the small epoch regime. Our analyses reveal that the convergence properties of permutation-based SGD in the small epoch regime may vary drastically depending on the assumptions on component functions. Lastly, we supplement the paper with tight upper and lower bounds for IGD in the large epoch regime.
• Abstract（参考訳）: 最近の理論的結果は、置換に基づくSGD(例えば、ランダムリシャッフルSGD)の収束速度が一様サンプリングSGDよりも速いことを示しているが、これらの研究は主に、エポック数$K$が条件数$\kappa$を超える大規模なエポック状態に焦点を当てている。 対照的に、$K$が$\kappa$より小さいときはほとんど知られておらず、この小さなエポックな体制において置換に基づくSGDがより早く収束できるかどうかという挑戦的な未解決問題である(Safran and Shamir, 2021)。 このギャップを理解するためのステップとして、スムーズで強い凸関数について、単純決定論的変種であるインクリメンタルグラディエント・ディフレッシュ(IGD)について検討する。 我々の下限は、小さなエポック状態においては、IGDは、すべての成分関数が強く凸である場合でも驚くほど緩やかな収束を示すことを示している。 さらに、いくつかの成分関数が非凸であることが許された場合、IGDの最適性ギャップは、小エポック状態を通して著しく悪化する可能性があることを証明した。 解析の結果,小エポック状態における置換に基づくSGDの収束特性は,成分関数の仮定によって大きく異なることが明らかとなった。 最後に, 大規模エポック政権におけるIGDの高次・低次境界で補足する。

関連論文リスト

• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
  我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。 本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
  論文  参考訳（メタデータ） (2024-04-03T00:41:19Z)
• High-probability Convergence Bounds for Nonlinear Stochastic Gradient Descent Under Heavy-tailed Noise [59.25598762373543]
  重み付き雑音の存在下でのストリーミングデータにおける学習の精度保証について検討した。 解析的に、与えられた問題に対する設定の選択に$ta$を使うことができることを実証する。
  論文  参考訳（メタデータ） (2023-10-28T18:53:41Z)
• Demystifying the Myths and Legends of Nonconvex Convergence of SGD [17.445810977264067]
  勾配勾配勾配(SGD)とその変種は、大規模最適化問題の解法の主要な仕事場である。 分析として,勾配の非収束に関連する神話や伝説について考察した。
  論文  参考訳（メタデータ） (2023-10-19T17:58:59Z)
• 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)
• Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent [7.176107039687231]
  雑音に対して勾配降下(SGD)を適応させるステップサイズスキームを設計する。 我々は、Nesterov反復によるSGDの$T$反復がほぼ最適であることを示す。 他のステップサイズスキームと比較して、新しい指数的なステップサイズスキームの有効性を実証する。
  論文  参考訳（メタデータ） (2021-10-21T19:22:14Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• On Tight Convergence Rates of Without-replacement SGD [52.99237600875452]
  有限サム最適化問題を解くために、置換サンプリングのないSGDは、SGDより優れていることを実証的に示している。 本研究では, 時代によって異なるステップサイズを解析することによって, これらの制約を克服する。
  論文  参考訳（メタデータ） (2020-04-18T16:14:11Z)

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

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