論文の概要: Random Reshuffling Dominates Stochastic Gradient Descent

• arxiv url: http://arxiv.org/abs/2606.32005v1
• Date: Tue, 30 Jun 2026 17:38:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-01 18:27:19.330503
• Title: Random Reshuffling Dominates Stochastic Gradient Descent
• Title（参考訳）: ランダムリシャッフルは確率的グラディエント染みを支配
• Authors: Zijian Liu,
• Abstract要約: 我々はランダムリシャッフル(textsfRR$)が、有限個のエポックの後、任意の合理的なステップサイズの下で滑らかな凸最適化において$textsfSGD$を支配していることを示す。 有限個のエポックの後、任意の合理的なステップサイズの下で滑らかな凸最適化において、$textsfRR$が$textsfSGD$を支配していることも証明する。
• 参考スコア（独自算出の注目度）: 3.8357180714081327
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic Gradient Descent ($\textsf{SGD}$) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet the practical implementation of $\textsf{SGD}$ differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent ($\textsf{Shuffling SGD}$). A particularly popular strategy in $\textsf{Shuffling SGD}$ is Random Reshuffling ($\textsf{RR}$), which has achieved great empirical success across numerous experiments. Despite its strong performance, $\textsf{RR}$ has long been considered a heuristic due to a lack of theoretical support. Over the last decade, people have finally established provable convergence rates for $\textsf{RR}$, thus justifying its observed superiority. However, for smooth convex optimization, two clouds over the convergence theory of $\textsf{RR}$ remain to this day. More precisely, according to the current theory, $\textsf{Shuffling SGD}$ under $\textsf{RR}$ converges only when the stepsize is smaller than a threshold proportional to $1/n$, where $n$ is the number of summands in the objective (or the number of data points). Consequently, the optimally tuned theoretical rate of $\textsf{Shuffling SGD}$ under $\textsf{RR}$ is strictly worse than that of $\textsf{SGD}$ when the number of epochs is smaller than another threshold proportional to $n$. These two restrictions heavily limit the applicability of existing theories and leave a critical mismatch with practice. In this work, for the first time, we prove that $\textsf{RR}$ dominates $\textsf{SGD}$ in smooth convex optimization under any reasonable stepsize after any finite number of epochs, thereby addressing a longstanding open question.
• Abstract（参考訳）: Stochastic Gradient Descent ($\textsf{SGD}$) は、理論的な保証を持つ最も古典的な最適化アルゴリズムの1つであるが、$\textsf{SGD}$の実践的実装は、そのよく知られた形式とは微妙に異なり、Shuffling Stochastic Gradient Descent ($\textsf{Shuffling SGD}$) と呼ばれることが多い。 $\textsf{Shuffling SGD}$の特に一般的な戦略はランダムリシャッフル(\textsf{RR}$)である。 強い性能にもかかわらず、$\textsf{RR}$は理論的なサポートがないため、長い間ヒューリスティックと見なされてきた。 過去10年間で、人々はついに$\textsf{RR}$の証明可能な収束率を確立した。 しかし、滑らかな凸最適化のために、$\textsf{RR}$の収束理論上の2つの雲は今日まで残っている。 より正確には、現在の理論によれば、$\textsf{Shuffling SGD}$ under $\textsf{RR}$は、ステップサイズが1/n$に比例する閾値よりも小さい場合にのみ収束する。 したがって、最適に調整された理論率 $\textsf{Shuffling SGD}$ under $\textsf{RR}$ は $\textsf{SGD}$ よりも真に悪い。 この2つの制限は、既存の理論の適用性を厳しく制限し、実践と重大なミスマッチを残している。 この研究において、初めて $\textsf{RR}$ が滑らかな凸最適化において、有限個のエポックの後、任意の合理的なステップ化の下で $\textsf{SGD}$ を支配していることを証明する。

関連論文リスト

• Trade-off Functions for DP-SGD with Subsampling based on Random Shuffling: Tight Upper and Lower Bounds [7.787109481104569]
  ランダムシャッフルに基づくサブサンプリングによるDP-SGDのトレードオフ関数の厳密な解析を導出する。 Berry-Esseenの定理によって導かれる我々の具体的な境界は、証明フレームワーク内の定数要素に密着している。
  論文  参考訳（メタデータ） (2026-05-07T13:35:43Z)
• Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis [3.8357180714081327]
  単純だが効果的な操作である勾配クリッピングは、この新しい課題をうまく処理することが知られている。 我々の研究は2つの面で既存のアプローチを改善している: 重尾雑音下でのクリップ誤りに対するフリードマンの不等式とより微細な境界のより良い利用である。 この研究を補完するために、我々は高確率と非観測収束の両方のための新しい下界を確立する。
  論文  参考訳（メタデータ） (2025-12-29T03:35:53Z)
• On the $O(\frac{\sqrt{d}}{K^{1/4}})$ Convergence Rate of AdamW Measured by $\ell_1$ Norm [52.95596504632859]
  本稿では、$ell_1$ノルムで測定されたAdamWに対して、収束速度 $frac1Ksum_k=1KEleft[||nabla f(xk)||_1right]leq O(fracsqrtdCK1/4)$を確立する。 結果は、二重モーメント機構を用いたAdamW変種であるNAdamWに拡張し、同じ収束率を維持していることを示す。
  論文  参考訳（メタデータ） (2025-05-17T05:02:52Z)
• Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping [21.865728815935665]
  重み付き雑音下での最初の収束を提供するが、切断はしない。 また、テールインデックス$mathfrakp$が事前に不明な場合には、最初の$mathcalO(Tfrac1-mathfrakp3mathfrakp-2)$収束率も設定する。
  論文  参考訳（メタデータ） (2024-12-27T08:46:46Z)
• On the $O(\frac{\sqrt{d}}{T^{1/4}})$ Convergence Rate of RMSProp and Its Momentum Extension Measured by $\ell_1$ Norm [54.28350823319057]
  本稿では、RMSPropとその運動量拡張を考察し、$frac1Tsum_k=1Tの収束速度を確立する。 我々の収束率は、次元$d$を除くすべての係数に関して下界と一致する。 収束率は$frac1Tsum_k=1Tと類似していると考えられる。
  論文  参考訳（メタデータ） (2024-02-01T07:21:32Z)
• A Variance-Reduced Stochastic Accelerated Primal Dual Algorithm [3.2958527541557525]
  このような問題は、堅牢な経験的リスク最小化という文脈で機械学習で頻繁に発生する。 高速化された原始双対 (SAPD) アルゴリズムは勾配雑音に対する頑健な手法であると考えている。 提案手法は,SAPDの実践と理論の両方において改善されていることを示す。
  論文  参考訳（メタデータ） (2022-02-19T22:12:30Z)
• The Convergence Rate of SGD's Final Iterate: Analysis on Dimension Dependence [2.512827436728378]
  Gradient Descent (SGD) は最適化において最も単純で一般的な手法の一つである。 定次元設定におけるSGDの最終点収束を特徴付ける方法を示す。
  論文  参考訳（メタデータ） (2021-06-28T11:51:04Z)

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

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