論文の概要: Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD

• arxiv url: http://arxiv.org/abs/2604.10373v1
• Date: Sat, 11 Apr 2026 22:59:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-14 20:13:15.981738
• Title: Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD
• Title（参考訳）: ステップサイズストレッチングによるデータシャッフル: 定常ステップサイズSGDにおけるシャーパーバイアス
• Authors: Konstantinos Emmanouilidis, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Rene Vidal,
• Abstract要約: 我々は、Random Reshufflingが推定解の平均二乗誤差(MSE)を鋭くし、Richardson-Romberg外挿はバイアスの2次低減として機能することを示した。 我々の研究は、構造化された非単トンVIPにおけるそのようなシナジーに対する最初の理論的保証を提供する。
• 参考スコア（独自算出の注目度）: 2.8104708182884046
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: From adversarial robustness to multi-agent learning, many machine learning tasks can be cast as finite-sum min-max optimization or, more generally, as variational inequality problems (VIPs). Owing to their simplicity and scalability, stochastic gradient methods with constant step size are widely used, despite the fact that they converge only up to a constant term. Among the many heuristics adopted in practice, two classical techniques have recently attracted attention to mitigate this issue: \emph{Random Reshuffling} of data and \emph{Richardson--Romberg extrapolation} across iterates. Random Reshuffling sharpens the mean-squared error (MSE) of the estimated solution, while Richardson-Romberg extrapolation acts orthogonally, providing a second-order reduction in its bias. In this work, we show that their composition is strictly better than both, not only maintaining the enhanced MSE guarantees but also yielding an even greater cubic refinement in the bias. To the best of our knowledge, our work provides the first theoretical guarantees for such a synergy in structured non-monotone VIPs. Our analysis proceeds in two steps: (i) we smooth the discrete noise induced by reshuffling and leverage tools from continuous-state Markov chain theory to establish a novel law of large numbers and a central limit theorem for its iterates; and (ii) we employ spectral tensor techniques to prove that extrapolation debiases and sharpens the asymptotic behavior even under the biased gradient oracle induced by reshuffling. Finally, extensive experiments validate our theory, consistently demonstrating substantial speedups in practice.
• Abstract（参考訳）: 逆の堅牢性からマルチエージェント学習に至るまで、多くの機械学習タスクは有限のmin-max最適化として、あるいはより一般的には変分不等式問題(VIP)として、キャストすることができる。 その単純さとスケーラビリティのため、一定のステップサイズを持つ確率勾配法は、一定項にしか収束しないにもかかわらず広く用いられている。 実際に採用されている多くのヒューリスティックのうち、2つの古典的手法がこの問題を緩和するために注目を集めている: データの \emph{Random Reshuffling} と、反復体をまたいだ \emph{Richardson--Romberg の外挿。 ランダムリシャッフルは推定解の平均二乗誤差(MSE)を鋭くし、リチャードソン・ロームバーグ外挿法は直交的に作用し、バイアスを二階減少させる。 本研究は,MSEの強化された保証を維持できるだけでなく,バイアスのさらに大きな3次改善をもたらすことにより,両者よりも厳密な構成が可能であることを示す。 我々の知識を最大限に活用するために、我々の研究は構造化された非単調VIPにおけるそのようなシナジーに対する最初の理論的保証を提供する。 私たちの分析は2つのステップで進みます。 i) 連続状態マルコフ連鎖理論の道具をリシャッリングし、活用することによって誘導される離散ノイズを円滑にし、大数の新しい法則とそのイテレートに対する中心極限定理を確立する。 (II) スペクトルテンソル法を用いて, リシャッフルによって引き起こされる偏りの勾配オラクルの下でも, 外挿脱臭が漸近挙動を鋭くすることを示す。 最後に、広範な実験が我々の理論を検証し、実践において実質的なスピードアップを一貫して証明した。

関連論文リスト

• Parameter-free non-ergodic extragradient algorithms for solving monotone variational inequalities [0.0]
  拘束単調なVIsに対する非漸近的最終定位保証を用いたパラメータフリーの指数分解法を開発した。 このフレームワークをバックトラックラインサーチによりローカルリプシッツ演算子に拡張し,パラメータ自由性を保ちながら同じレートを得る。
  論文  参考訳（メタデータ） (2026-04-09T00:02:30Z)
• Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits [53.773695219320125]
  重み付き雑音下での2階最適化の理論的理解に向けて第一歩を踏み出す。 勾配とヘッセン切断に基づく新しいアルゴリズムを導入し、基本限界にほぼ一致する高い確率上の境界を証明した。
  論文  参考訳（メタデータ） (2025-10-12T16:36:54Z)
• A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression [22.917692982875025]
  一階微分しか持たない関数を$f$で扱える新しいLyapunov関数を導入する。 一般の減少段数と定数段数の下で有限時間モーメント境界を導出する。 我々の結果は、特にオンライン統計手法に広く応用されている。
  論文  参考訳（メタデータ） (2025-04-11T00:20:37Z)
• Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements [19.524063429548278]
  Extragradient (SEG) と Gradient Descent Ascent (SGDA) は min-max 最適化と変分不等式問題に対する優越アルゴリズムである。 これらのアルゴリズムに固有の本質的な構造を定量化し定量化するための我々の取り組み。 定数のステップサイズSEG/SGDAを時間同質マルコフ連鎖として再キャストすることにより、大数の第一種法則と中心極限定理を確立する。
  論文  参考訳（メタデータ） (2023-06-28T18:50:07Z)
• Formal guarantees for heuristic optimization algorithms used in machine learning [6.978625807687497]
  グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。 本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
  論文  参考訳（メタデータ） (2022-07-31T19:41:22Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Stochastic Hamiltonian Gradient Methods for Smooth Games [51.47367707388402]
  ハミルトンの手法のクラスに焦点をあて、滑らかなゲームのあるクラスに対する最初の収束保証を提供する。 最適化文献からのツールを用いて、SHGDは勾配の近傍に直線的に収束することを示す。 この結果から,一般ゲームのクラスに対して,非漸近的でない最後の収束保証を初めて提供する。
  論文  参考訳（メタデータ） (2020-07-08T15:42:13Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)

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

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