TL;DR
Stochastic Gradient Descent (SGD) implicitly biases models toward flatter minima by convolving the loss surface with gradient noise, but using a large learning rate to amplify this effect makes optimization unstable. This paper mathematically proves that tail-averaging SGD iterates (averaged SGD) resolves this bias–optimization trade-off, tightening convergence distance to the smoothed, flatness-regularized objective from $\mathcal{O}(\sqrt{\eta})$ down to $\mathcal{O}(\eta)$. This allows practitioners to run SGD stably with larger learning rates and find wider, better-generalizing valleys.
What Problem Does This Paper Address?
Deep learning models generalize best when they land in flat regions of the loss landscape rather than sharp crevices. SGD naturally possesses an implicit bias toward flat regions because stochastic gradient noise bounces iterates out of steep valleys. However, this creates a frustrating trade-off controlled by the step size $\eta$:
- Large step size: Enhances noise-induced smoothing (stronger bias toward flat minima), but causes massive oscillations and prevents accurate convergence.
- Small step size: Allows precise optimization, but weakens the noise effect, leaving models trapped in sharp valleys or on the steep edges of flat basins.
Empirical methods like Stochastic Weight Averaging (SWA) found that running SGD with a large learning rate and averaging weights yields superior generalization. Yet, a formal theoretical explanation for why weight averaging stabilizes this implicit bias in non-convex landscapes remained missing.
Methods
The authors build on the smoothed objective perspective: SGD implicitly minimizes a convolution of the loss $f$ with its gradient noise $\eta \epsilon$, which effectively acts as a penalized objective against high curvature: $$F(v) \approx f(v) + \frac{\eta^2}{2}\operatorname{Tr}\left(\nabla^2 f(v)\,\mathbb{E}[\epsilon'(v)\epsilon'(v)^\top]\right) + \mathcal{O}(\eta^3)$$
The core methodology comprises:
- Refined Non-Asymptotic Convergence Analysis: Using an auxiliary sequence $v_t = w_t - \eta \nabla f(w_t)$ (gradient-descent step from iterate $w_t$), they formalize an implicit SGD update rule. Under a localized one-point strong convexity assumption around the smoothed minimizer $v_*$, they bound the distance of both standard and averaged iterates to $v_*$.
- Tail-Averaging Scheme: Maintaining a running average over the final phase of training (similar to Polyak–Ruppert averaging and SWA) to cancel out the variance of zero-mean noise.
Datasets
- CIFAR-10 & CIFAR-100: Standard image classification benchmarks evaluated using ResNet-50, WideResNet (WRN-28-10), and deep PyramidNet-272.
- Fashion MNIST: Used with a convolutional neural network (CNN) to track the trace of the Hessian during training.
- Synthetic 1D Benchmarks: Handcrafted asymmetric valleys and mollified double-well objectives designed to visualize sharp-minimum avoidance and valley shifting.
Key Insights and Ideas
- $\mathcal{O}(\eta)$ vs. $\mathcal{O}(\sqrt{\eta})$ Optimization Precision: The paper proves that vanilla SGD using step size $\eta$ only gets within $\mathcal{O}(\sqrt{\eta})$ Euclidean distance of the smoothed objective’s minimizer $v_*$. In contrast, averaged SGD converges to within $\mathcal{O}(\eta)$ distance of $v_*$.
- Unlocking Larger Step Sizes: Because averaged SGD achieves an order-of-magnitude tighter dependence on $\eta$, it can tolerate much larger step sizes without diverging or failing to converge, fully reaping the benefits of noise-induced flatness regularization.
- Asymmetric Valley Shifting: In asymmetric valleys (which are common in deep networks), the minimizer of the smoothed objective shifts away from steep walls toward the wider, flat side. Vanilla SGD often gets stuck near the sharp edge, whereas averaged SGD safely targets the interior flat floor.
Key Results
- CIFAR-100 (Hard Task): Averaged SGD with a large step size schedule ('$l$') achieved dramatic improvements over standard SGD:
- ResNet-50: $80.83\% \to 82.87\%$ test accuracy.
- WRN-28-10: $81.81\% \to 84.23\%$ test accuracy.
-
PyramidNet: $81.43\% \to 85.12\%$ test accuracy. In this regime, standard SGD completely failed to converge and oscillated wildly, whereas averaging produced state-of-the-art results competitive with Sharpness-Aware Minimization (SAM: $84.59\%$ on PyramidNet).
-
Averaged SAM: Combining parameter averaging with SAM further boosted PyramidNet on CIFAR-100 from $84.59\%$ to $86.00\%$.
- Hessian Flatness: On Fashion MNIST, tracking $\operatorname{Tr}(\nabla^2 f(w))$ demonstrated that averaged SGD with a large step size consistently found solutions with lower Hessian trace (higher flatness) and lower test error than vanilla SGD.
Limitations and Future Work
- Convexity Assumptions on the Smoothed Surface: The proof requires local one-point strong convexity at the minimizer of the convolved function $F(v)$ and bounded third-order derivatives, which may not hold universally across complex neural loss surfaces.
- Regime Distinction from Edge of Stability: The analysis operates in the standard smoothness regime ($\eta \le 1/(2L)$). It does not directly cover the Edge of Stability regime ($\eta > 2/L$), where deterministic gradient descent itself exhibits non-monotonic behavior. Unifying noise-driven flatness bias with deterministic instability remains an open problem.
- Noise Structure: The theory abstracts gradient noise via uniform variance bounds ($\sigma_1, \sigma_2$); investigating how non-isotropic, batch-dependent label or gradient noise impacts generalization is left for future work.
Summary updated