論文の概要: 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（参考訳）: ランダムリシャッフルは確率的グラディエント染みを支配
• 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)
• Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization [62.48819955422706]
  大規模偏差理論のレンズによるSGD法における長期のテール崩壊について検討する。 我々は、テールが以前よりもはるかに早く崩壊する体制を発見し、個々のランニングに対してより強力な長期保証を提供する。
  論文  参考訳（メタデータ） (2026-02-05T13:41:13Z)
• Clipped Gradient Methods for Nonsmooth Convex Optimization under Heavy-Tailed Noise: A Refined Analysis [3.8357180714081327]
  単純だが効果的な操作である勾配クリッピングは、この新しい課題をうまく処理することが知られている。 我々の研究は2つの面で既存のアプローチを改善している: 重尾雑音下でのクリップ誤りに対するフリードマンの不等式とより微細な境界のより良い利用である。 この研究を補完するために、我々は高確率と非観測収束の両方のための新しい下界を確立する。
  論文  参考訳（メタデータ） (2025-12-29T03:35:53Z)
• Scale-Invariant Regret Matching and Online Learning with Optimal Convergence: Bridging Theory and Practice in Zero-Sum Games [60.871651115241406]
  ゼロサムゲームにおける理論と実践の間、何十年にもわたってかなりのシャズムが一階法によって浸食されてきた。 我々は、IREG-PRM$+$と呼ぶPRM$+$の新しいスケール不変かつパラメータフリーな変種を提案する。 ベンチマークゲームでは, PRM$+$と同等でありながら, 最適収束保証を$T-1/2$, $T-1$とする。
  論文  参考訳（メタデータ） (2025-10-06T00:33:20Z)
• Can SGD Handle Heavy-Tailed Noise? [6.111519084375339]
  Gradient Descent (SGD) は大規模最適化のための機械学習プロジェクトであるが、重尾雑音下での理論的挙動は理解されていない。 このような悪条件下でSGDが確実に成功できるかどうかを精査する。
  論文  参考訳（メタデータ） (2025-08-06T20:09:41Z)
• 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)
• Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
  我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。 我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
  論文  参考訳（メタデータ） (2024-08-21T20:14:54Z)
• Revisiting Step-Size Assumptions in Stochastic Approximation [1.3654846342364308]
  この仮定は、収束とより微細な結果には必要ないことが初めて示される。 標準アルゴリズムおよびPolyakとRuppertの平均化手法を用いて得られた推定値に対して収束率を求める。 数値実験の結果,乗法雑音とマルコフ記憶の組み合わせにより,$beta_theta$が大きくなる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-05-28T05:11:05Z)
• 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)
• Sharper Convergence Guarantees for Asynchronous SGD for Distributed and Federated Learning [77.22019100456595]
  通信周波数の異なる分散計算作業者のトレーニングアルゴリズムを示す。 本研究では,より厳密な収束率を$mathcalO!!(sigma2-2_avg!)とする。 また,不均一性の項は,作業者の平均遅延によっても影響されることを示した。
  論文  参考訳（メタデータ） (2022-06-16T17:10:57Z)
• 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)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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