Skip to main content
Back

UPenn and UW-Madison Cut SGD Bias From Linear to Cubic

New algorithm combines random reshuffling with step-size extrapolation to shrink SGD's constant-step bias from linear to cubic in the step size.

Pro

Paper, Full Access
  • New SGD variant combines random reshuffling with Richardson-Romberg extrapolation for cubic bias reduction in constant step-size training.
  • Bias drops from O(gamma) to O(gamma cubed), while MSE stays at O(gamma squared), all with the same condition number as vanilla SGDA.
  • Applies to variational inequalities: min-max optimization, GAN training, multi-agent RL, and Nash equilibrium computation.
  • Analysis uses continuous-state Markov chain theory and new spectral tensor bounds for biased reshuffling oracles.
  • Two parallel chains run at step sizes gamma and 2 gamma; combined endpoint at each epoch cancels leading bias.
  • Experiments on WGANs and quadratic games show it outperforms SGDA, RR alone, and extrapolation alone at similar wall-clock cost.

Anyone who has trained a model with a constant learning rate knows the drill: SGD makes fast early progress, then stalls in a noisy neighborhood around the solution. That residual gap, known as the bias, scales with the step size, and shrinking it usually means either decaying the learning rate or accepting the error. A new theoretical paper from UPenn and UW-Madison shows that two well-known tricks, when combined properly, cut that bias from linear to cubic in the step size while preserving the same mean-squared error guarantees.

The stubborn gap left by constant step sizes

The setting is broader than plain minimization. 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). A variational inequality generalizes the problem of finding a zero of a gradient field, covering saddle-point formulations, Nash equilibria, and GAN training. Stochastic gradient methods dominate here for the same reason they dominate everywhere else: they are simple and they scale.

The catch is well documented. Constant step-size SGD converges only up to a residual error term. For a step size gamma, both the mean-squared error and the bias sit at order gamma. Practitioners have layered on heuristics to fight this, and two in particular have solid empirical track records.

The first is Random Reshuffling (called RR1 in the paper), which is what deep learning frameworks do by default: shuffle the dataset once per epoch and visit each sample exactly once, rather than sampling with replacement. The second is