Generalization and Optimization of SGD with Lookahead

Kangcheng Li, Yunwen LeiSubmission to ICLR 2026 · Withdrawn

TL;DR

While the Lookahead optimizer is widely used to boost deep learning performance, theoretical understanding of its generalization has lagged behind its optimization theory. This paper provides the first optimistic, on-average stability and generalization bounds for Lookahead with minibatch SGD across convex and strongly convex settings without assuming restrictive globally Lipschitz losses. The results explain how Lookahead's hyperparameters stabilize learning and prove that Lookahead achieves optimal excess risk rates, including linear batch size speedup in the convex regime.

What Problem Does This Paper Address?

The Lookahead optimizer works via a dual-weight mechanism: an inner loop updates "fast weights" using a standard optimizer (like SGD), while an outer loop slowly interpolates "slow weights" toward those fast weights. While empirically successful and well-analyzed regarding optimization (minimizing training loss), its generalization (performance on unseen test data) remains poorly understood.

Prior generalization theory for Lookahead (notably Zhou et al., 2021) suffered from key limitations:

  1. Unrealistic assumptions: It required loss functions to be globally $G$-Lipschitz, an assumption frequently violated in deep learning where gradients can be unbounded.
  2. Pessimistic bounds: Existing bounds relied on worst-case constants rather than adapting to the actual optimization trajectory.
  3. Missing minibatch effects: Prior stability analyses failed to show how minibatch size affects generalization.

Methods

The authors study Lookahead paired with minibatch SGD through the lens of algorithmic stability (specifically, $\ell_1$ and $\ell_2$ on-average model stability):

  • Bypassing Lipschitzness via Self-Bounding Properties: Instead of assuming bounded gradients, the authors rely solely on convexity, nonnegativity, and $L$-smoothness, leveraging the self-bounding property of smooth non-negative functions ($\|\nabla f(w; z)\|_2^2 \le 2L f(w; z)$).
  • Optimistic Bounds: By tying stability directly to the empirical training risk $\mathbb{E}[F_S(v)]$, the stability bound tightens progressively as the optimizer drives down training error.
  • Optimization-Generalization Decomposition: The excess risk $\mathbb{E}[F(\bar{v}_R) - F(w^*)]$ is decomposed into generalization error and empirical optimization error, enabling end-to-end excess risk analysis for convex and $\mu$-strongly convex problems.

Datasets

Not discussed in the paper. This is a purely theoretical paper and does not evaluate models on empirical datasets or introduce new benchmarks.

Key Insights and Ideas

  • Hyperparameters directly control stability:
  • Outer step size ($\alpha$): Stability bounds scale with $\alpha$. A smaller interpolation factor dampens the variance of volatile fast weights, mathematically justifying why the slow-weight mechanism prevents overfitting.
  • Inner loop steps ($k$): Stability degrades as $k$ increases, confirming that running inner optimization too long causes fast weights to overfit the training batch.
  • Batch size ($b$): The stability bounds scale with $1/(nb)$, proving that larger minibatches directly reduce stochastic variance and stabilize learning.
  • Two distinct generalization regimes (Convex Case):
  • Noisy regime ($F(w^*) \ge 1/n$): Lookahead achieves the standard $\mathcal{O}(1/\sqrt{n})$ excess risk with iteration complexity $\mathcal{O}(n/b)$, proving a linear speedup in batch size.
  • Low-noise / Interpolation regime ($F(w^*) < 1/n$): Lookahead achieves a fast $\mathcal{O}(1/n)$ excess risk rate without requiring batch scaling, demonstrating adaptability to low-noise settings.
  • Fast rates for strongly convex problems: Lookahead attains the minimax-optimal excess risk of $\mathcal{O}(1/(n\mu))$ in just $T \asymp \log(\mu n)$ outer iterations.

Key Results

  • Convex Excess Risk:
  • For $F(w^*) \ge 1/n$, Lookahead achieves an excess risk of $\mathcal{O}\left(\frac{L \sqrt{F(w^*)}}{\sqrt{n}} + \frac{L^2}{n}\right)$, which is substantially sharper than standard $\mathcal{O}(G^2/\sqrt{n})$ bounds when optimal loss is small.
  • For $F(w^*) < 1/n$, the excess risk improves to $\mathcal{O}\left(\frac{L}{n} + F(w^*)\right)$.
  • Strongly Convex Excess Risk:
  • By choosing $k = \frac{2L}{\alpha \mu}$ and inner learning rate $\eta = \frac{b\mu}{2L^2(b+1)}$, Lookahead achieves an excess risk of $\mathcal{O}\left(\frac{1}{n\mu}\right)$ in logarithmic outer steps $T \asymp \log(\mu n)$, adapting to interpolation via data-dependent terms.

Limitations and Future Work

  • Convexity Assumptions: The analysis is restricted to convex and strongly convex functions. Modern deep learning landscapes are highly non-convex, leaving non-convex generalization as an open challenge.
  • No Minibatch Linear Speedup for Strongly Convex Case: While the optimal statistical rate $\mathcal{O}(1/(n\mu))$ is achieved in the strongly convex setting, the current proof does not demonstrate linear computational speedup with respect to batch size $b$, unlike in the convex case. The authors suggest exploring alternate hyperparameter schedules to unlock this in future work.

Summary updated

Abstract

The Lookahead optimizer enhances deep learning models by employing a dual-weight update mechanism, which has been shown to improve the performance of underlying optimizers such as SGD. However, most theoretical studies focus on its convergence on training data, leaving its generalization capabilities less understood. Existing generalization analyses are often limited by restrictive assumptions, such as requiring the loss function to be globally Lipschitz continuous, and their bounds do not fully capture the relationship between optimization and generalization. In this paper, we address these issues by conducting a rigorous stability and generalization analysis of the Lookahead optimizer with minibatch SGD. We leverage on-average model stability to derive generalization bounds for both convex and strongly convex problems without the restrictive Lipschitzness assumption. Our analysis demonstrates a linear speedup with respect to the batch size in the convex setting.
BibTeX
@misc{li2025generalization,
  author = {Kangcheng Li and Yunwen Lei},
  title = {{Generalization and Optimization of SGD with Lookahead}},
  year = {2025},
  eprint = {2509.15776},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2509.15776},
}
Figure