Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD

• URL: http://arxiv.org/abs/2604.10373v1
• Date: Sat, 11 Apr 2026 22:59:26 GMT
• Title: Shuffling the Data, Stretching the Step-size: Sharper Bias in constant step-size SGD
• Abstract summary: We show that Random Reshuffling sharpens the mean-squared error (MSE) of the estimated solution, while Richardson-Romberg extrapolation acts as a second-order reduction in its bias.<n>Our work provides the first theoretical guarantees for such a synergy in structured non-monotone VIPs.
• Score: 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.

Related papers

• The Role of Gradient Modification in Heavy-Tailed Nonconvex Stochastic Min-Max Optimization [50.59470683896735]
  min-max optimization has attracted increasing attention due to its applications in modern machine learning.<n>We provide a comprehensive theoretical of gradient descent (SGDA)<n>We develop new clipping-free algorithms, i.e., Stoc-GDAM and Stoc-TRmax, and they both can achieve the optimal dependence on the target accuracy without using gradient clipping.
  arXiv  Detail & Related papers  (2026-09-05T12:49:28Z)
• Central Limit Theorem for Two-Time-Scale Approximate Distributionally Robust RL [8.809468023364703]
  Design of robust reinforcement learning algorithms poses fundamental challenges.<n>We propose an approximate DRRL framework based on a first-order expansion of the relevant robust functional.<n>To learn the fixed point of this approximate equation, we propose Mean-Variance Approximation (MVSA)
  arXiv  Detail & Related papers  (2026-05-08T19:24:28Z)
• Parameter-free non-ergodic extragradient algorithms for solving monotone variational inequalities [0.0]
  We develop parameter-free extragradient methods with non-asymptotic last-iterate guarantees for constrained monotone VIs.<n>We extend the framework to locally Lipschitz operators via backtracking line search and obtain the same rate while preserving parameter-freeness.
  arXiv  Detail & Related papers  (2026-04-09T00:02:30Z)
• Improved Convergence in Parameter-Agnostic Error Feedback through Momentum [49.163769734936295]
  We study normalized error feedback algorithms that combine EF with normalized updates, various momentum variants, and parameter-agnostic, time-varying stepsizes.<n>Our results hold with decreasing stepsizes and small mini-batches.
  arXiv  Detail & Related papers  (2025-11-18T13:47:08Z)
• Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits [53.773695219320125]
  We take a first step toward a theoretical understanding of second-order optimization under heavy-tailed noise.<n>We introduce a novel algorithm based on gradient and Hessian clipping, and prove high-probability upper bounds that nearly match the fundamental limits.
  arXiv  Detail & Related papers  (2025-10-12T16:36:54Z)
• A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression [22.917692982875025]
  We introduce a novel piecewise Lyapunov function that enables us to handle functions $f$ with only first-order differentiability.<n>We derive finite-time moment bounds under general diminishing stepsizes, as well as constant stepsizes.<n>Our results have wide applications, especially in online statistical methods.
  arXiv  Detail & Related papers  (2025-04-11T00:20:37Z)
• Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements [19.524063429548278]
  Extragradient (SEG) and Gradient Descent Ascent (SGDA) are preeminent algorithms for min-max optimization and variational inequalities problems. Our work endeavors to quantify and quantify the intrinsic structures intrinsic to these algorithms. By recasting the constant step-size SEG/SGDA as time-homogeneous Markov Chains, we establish a first-of-its-kind Law of Large Numbers and a Central Limit Theorem.
  arXiv  Detail & Related papers  (2023-06-28T18:50:07Z)
• Non-convex Bayesian Learning via Stochastic Gradient Markov Chain Monte Carlo [4.656426393230839]
  The rise of artificial intelligence (AI) hinges on efficient of modern deep neural networks (DNNs) for non-trips and uncertainty. In this thesis we propose a tool to handle the problem of Monte Carlo exploitation. We also propose two dynamic importance sampling algorithms for the underlying ordinary equation (ODE) system.
  arXiv  Detail & Related papers  (2023-05-30T18:25:11Z)
• Formal guarantees for heuristic optimization algorithms used in machine learning [6.978625807687497]
  Gradient Descent (SGD) and its variants have become the dominant methods in the large-scale optimization machine learning (ML) problems. We provide formal guarantees of a few convex optimization methods and proposing improved algorithms.
  arXiv  Detail & Related papers  (2022-07-31T19:41:22Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  We present an analysis of the ExtraGradient (SEG) method with constant step size, and present variations of the method that yield favorable convergence. We prove that when augmented with averaging, SEG provably converges to the Nash equilibrium, and such a rate is provably accelerated by incorporating a scheduled restarting procedure.
  arXiv  Detail & Related papers  (2021-06-30T17:51:36Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Stochastic Hamiltonian Gradient Methods for Smooth Games [51.47367707388402]
  We focus on the class of Hamiltonian methods and provide the first convergence guarantees for certain classes of smooth games. Using tools from the optimization literature we show that SHGD converges linearly to the neighbourhood of a gradient. Our results provide the first global non-asymotic last-rate convergence guarantees for the class of general games.
  arXiv  Detail & Related papers  (2020-07-08T15:42:13Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.