Understanding SGD with Exponential Moving Average: A Case Study in Linear Regression

Xuheng Li, Quanquan GuSubmission to ICLR 2026 · Rejected

TL;DR

Exponential moving average (EMA) of model weights is an essential practical tool in training modern deep learning systems (especially diffusion models and GANs), but its theoretical mechanisms have remained poorly understood. This paper establishes the first instance-dependent, dimension-free excess risk bounds for online SGD with EMA in overparameterized linear regression. The authors prove that EMA achieves the "best of both worlds": its bias error decays exponentially fast (unlike standard iterate averaging, which decays polynomially), while its variance error is drastically smaller than un-averaged SGD and matches tail averaging—without needing to know the training budget in advance.

What Problem Does This Paper Address?

Practitioners routinely maintain an exponential moving average of network weights during training because it stabilizes trajectories and improves test performance. Despite its empirical ubiquity, prior theoretical analyses of iterate averaging primarily focused on uniform iterate averaging (Polyak–Juditsky averaging) or tail averaging.

These existing theories leave a significant gap:

  1. Polyak–Juditsky averaging reduces gradient noise variance, but causes the bias error to contract slowly at a polynomial rate ($\mathcal{O}(1/N)$).
  2. Tail averaging can achieve exponential bias decay, but only if the averaging window $s$ is tuned to the total training horizon $N$ ahead of time.
  3. Prior theoretical works analyzing EMA specifically were largely confined to finite-dimensional settings, failing to capture the overparameterized, high-dimensional regimes typical of modern models.

This paper tackles this gap by analyzing online SGD with EMA on overparameterized linear regression, deriving sharp excess risk bounds that depend only on the data covariance spectrum, completely independent of ambient dimension $d$.

Methods

The authors analyze constant-stepsize ($\delta$) online SGD where the parameters are updated via $w_t = w_{t-1} + \delta(y_t - \langle w_{t-1}, x_t \rangle)x_t$, alongside an EMA shadow iterate: $$\overline{w}_t = \alpha \overline{w}_{t-1} + (1 - \alpha) w_{t-1}$$

To analyze this system:

  • Operator-Based Telescoping Framework: Standard analyses for uniform averaging rely on symmetric summations that fail when weights are non-uniform and geometric. The authors introduce a telescoping decomposition using the Kronecker-product operator $\widetilde{\mathcal{B}} = (I - \delta H) \otimes (I - \delta H)$ (where $H = \mathbb{E}[xx^\top]$ is the data covariance). This cleanly separates the bias and variance error dynamics.
  • Spectral Decomposition: They define two key effective dimensions:
  • $k^* := \max\{i : \lambda_i \ge (1-\alpha)/\delta\}$ (governed by the EMA parameter $\alpha$)
  • $k^\dagger := \max\{i : \lambda_i \ge 1/(N\delta)\}$ (governed by the iteration horizon $N$)
  • Generalization to Arbitrary Averaging: The proof machinery is formulated broadly enough to cover arbitrary time-dependent weight sequences $\beta_t$, unifying SGD without averaging, Polyak-Juditsky averaging, tail averaging, and EMA under a single framework.

Datasets

The theoretical results are validated empirically on synthetic benchmarks:

  • High-Dimensional Linear Regression: Synthetic data in dimension $d = 2000$ with Gaussian features $x \sim \mathcal{N}(0, H)$ following a power-law eigenvalue decay $\lambda_i = i^{-2}$, label noise $\sigma^2 = 1$, and initialization $w_0 - w_* \sim \mathcal{N}(0, I)$.
  • Single-Neuron ReLU Network: A non-linear single-neuron benchmark (Wu et al., 2023) tested in Appendix A to verify whether the qualitative behavior extends beyond linear models.
  • No real-world datasets were used in the paper.

Key Insights and Ideas

  • Exponential Bias Decay Across All Subspaces: Unlike Polyak–Juditsky averaging, where bias contracts at an $\mathcal{O}(1/N)$ rate, EMA maintains an exponential bias contraction in every eigen-subspace. Specifically, the bias decay factor $b_i$ exhibits a phase transition: it scales as $\sim \alpha^N$ in large eigenvalue subspaces ($\delta \lambda_i \gg 1-\alpha$) and as $\sim (1 - \delta \lambda_i)^N$ in small eigenvalue subspaces.
  • EMA as an "Anytime" Tail Averaging: Tail averaging over the last $N-s$ steps matches EMA's variance when $(1-\alpha)(N-s) = 1$. However, tail averaging requires setting $s = \Theta(N)$ in advance to preserve exponential bias decay. EMA achieves this decay automatically, making it ideal for open-ended or unknown training horizons.
  • Variance Suppression: In each subspace $i \le k^*$, the variance error is $\Theta(1-\alpha)$, significantly dampening stochastic noise compared to vanilla SGD.
  • Batch Size Scaling: Extending the analysis to mini-batch SGD reveals that because EMA's bias decays exponentially fast, its critical batch size is determined almost entirely by variance error, avoiding the bias-bottlenecks of uniform iterate averaging.

Key Results

  • Matching Bounds: The authors provide upper and lower bounds on excess risk $\mathbb{E}[L(\overline{w}_N)] - L(w_*)$. The variance upper bound and lower bound match up to universal constants: $$\text{Variance} \asymp \sigma^2 \left( (1-\alpha)k^* + \delta \sum_{i=k^*+1}^{k^\dagger} \lambda_i + N\delta^2 \sum_{i > k^\dagger} \lambda_i^2 \right)$$
  • Numerical Validation: On $d=2000, N=3000$ simulations, EMA ($\alpha = 0.995$) achieves variance reduction comparable to tail averaging ($s \in [100, 1000]$) while displaying a smooth, monotonic, and exponential decay in bias error, contrasting sharply with the noisy trajectories of vanilla SGD.

Limitations and Future Work

  • Theoretical Gap in Feature-Noise Bias: While the primary variance term (label noise $\sigma^2$) is tightly matched between upper and lower bounds, an $\mathcal{O}(\|w_0 - w_*\|^2)$ gap remains in the secondary variance component arising from feature randomness.
  • Linear/Single-Neuron Assumption: The theory strictly treats overparameterized linear regression (with empirical validation on a single ReLU neuron). Extending these dimension-free instance bounds to multi-layer non-linear deep architectures remains an open theoretical challenge.
  • Hyperparameter Stability: The analysis requires the step size to satisfy $\delta < 1/(\psi \operatorname{tr}(H))$, confirming empirically that exceeding this threshold leads to variance blowup.

Summary updated

Abstract

Exponential moving average (EMA) has recently gained significant popularity in training modern deep learning models. However, there have been few theoretical results explaining the effectiveness of EMA. In this paper, to better understand EMA, we establish the risk bound of online SGD with EMA by performing a case study on overparameterized linear regression, which is one of the simplest overparameterized learning tasks that shares similarities with neural networks. Our results indicate that (i) the variance error of SGD with EMA is always smaller than that of SGD without averaging, and (ii) unlike SGD with iterate averaging from the beginning, the bias error of SGD with EMA decays exponentially in every eigen-subspace of the data covariance matrix. Additionally, we develop proof techniques applicable to the analysis of a broad class of averaging schemes.
BibTeX
@misc{li2025understanding,
  author = {Xuheng Li and Quanquan Gu},
  title = {{Understanding SGD with Exponential Moving Average: A Case Study in Linear Regression}},
  year = {2025},
  eprint = {2502.14123},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.14123},
}

Loading related content...

Figure