acceptodds
Under review as a conference paper at ICLR 2027

A Spectral Analysis of Averaged Stochastic Gradient Methods

Abstract

Averaging is central to the statistical behavior of stochastic gradient methods, yet existing analyses often couple the optimization dynamics, the averaging rule, and the stochastic covariance recursion. Moreover, label noise is commonly summarized by a uniform relative-noise condition, which can obscure its distribution across spectral directions. We develop a modular spectral-readout theory for constant-stepsize stochastic gradient dynamics in least-squares regression. The framework separates an algorithm-dependent transfer kernel, a deterministic readout filter, and a second-moment feedback closure. For averaged SGD, we derive finite-time spectral bounds under a general positive trace-class label-noise covariance , without requiring , with matching feedback lower bounds after a noise-dependent warmup. The bounds retain the directional noise profile and identify convergent power-law regimes with no finite relative-noise constant. For stochastic heavy-ball, a direction-wise block closure exposes a self-damping mechanism and controls trace-class noise over the reference stepsize region. For full averaging, we further obtain matching risk bounds after warmup and under a fixed stability margin. Synthetic experiments and frozen-feature linear prediction corroborate the predicted filters and rates.

Primary area:
learning theory
Keywords:
Benign overfitting, SGD

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_K5V2OpenReview ↗
Rating
2
Confidence
1(−1)
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper analyzes SGD convergence rates for linear regression and examines how curvature, noise, and the choice of output rule (such as full averaging and tail averaging) affect prediction error. To show this, it does not require the gradient-noise covariance to be uniformly bounded relative to the curvature matrix. Instead, it assumes that this covariance has finite trace. It also provides experiments on synthetic data to validate its theoretical results.

Critical strengths

The paper extends prior convergence guarantees under a weaker noise covariance assumption, requiring a finite trace rather than uniform bounds relative to the curvature matrix.

Critical weaknesses
  • The core contribution feels a bit incremental. Since linear regression is already well studied, the main novelty here is proving a sharper characterization under a relaxed noise assumption. It would help to clarify what's new in the proof technique and why this broader assumption matters in practice. If the theory is somewhat incremental, demonstrating these ideas in more realistic settings would make a stronger case for their importance.

  • The presentation could be a bit clearer and easier to navigate. With the dense notation and shifts between definitions and assumptions, it takes some extra effort to follow the main thread. Adding more intuitive commentary and walking through how the results connect would really help improve the flow. Additionally, making the convergence rates more explicit would strengthen the takeaway. Because the current bounds rely heavily on auxiliary kernels and spectral functionals, readers may not immediately see how the rates improve as iterations progress.

Questions for authors

see weaknesses above

Reviewer_U7i6OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the prediction risk of constant-stepsize stochastic gradient methods for least-squares regression under different iterate-averaging rules. It organizes the analysis around deterministic readout filters and stochastic covariance feedback, retaining a general trace-class label-noise covariance Σ\Sigma rather than requiring Σ⪯σ2H\Sigma \preceq \sigma^2 H. For tail-averaged SGD, it derives directional variance bounds that distinguish directly injected label noise from noise generated by stochastic Hessian fluctuations, with matching lower bounds after a noise-dependent warmup. A power-law specialization identifies convergent regimes outside bounded relative noise, supported by an explicit compatible data distribution. The analysis also covers stochastic heavy-ball, providing a covariance upper bound for general linear readouts and matching noise-driven risk bounds for full averaging under additional stability and horizon conditions. Initialization effects are analyzed separately. Validation includes synthetic experiments comparing Monte Carlo estimates with exact second-moment recursions, power-law rate and filter checks, real covariates with controlled noise, and linear prediction on frozen ResNet-18 features.

Critical strengths

A concrete characterization beyond bounded relative noise. The paper retains the directional covariance Σ\Sigma and identifies regimes where prediction risk converges despite the absence of a finite constant satisfying Σ⪯σ2H\Sigma \preceq \sigma^2 H. Appendix G.1 constructs a joint data distribution realizing this regime while satisfying the required moment assumptions. This makes the broader-noise analysis consequential: it describes an admissible statistical setting where the usual scalar relative-noise bound is uninformative.

Matching bounds that distinguish direct noise from stochastic feedback. Under the lower fourth-moment assumption and after warmup, the lower bounds show that the feedback contribution cannot generally be discarded for the specified constant-stepsize dynamics. This supports the interpretation of the power-law rates as actual algorithmic behavior, rather than merely an artifact of an upper-bound analysis. The value lies in the explicit matching characterization, rather than in introducing a new feedback mechanism.

Critical weaknesses

The methodological contribution is narrower than the framework claims suggest. Important components of the upper-bound analysis have direct precedents: Zou et al.\ (2023)(https://arxiv.org/abs/2103.12692) provide general-source covariance bounds, while Li et al.\ (2024, Appendix F, Eq.~(F.9) https://arxiv.org/abs/2311.14222) already contain the SHB self-damping coefficient used here. The general-Σ\Sigma upper bounds largely follow by retaining the source covariance and sharpening existing calculations. The paper should more clearly isolate its added finite-time lower-bound arguments, warmup characterization, and realizability construction from this inherited machinery. The resulting advance is an incremental theoretical extension, which limits the strength of the claimed methodological contribution.

The authors cite and acknowledge the closest prior analyses, but the result-by-result distinction remains insufficiently precise. In particular, the claimed framework and SHB closure should be distinguished from existing identities, coefficients, and proof arguments.

The principal power-law experiment is insufficiently specified. Figure1 does not provide the truncation dimension, stepsize, initialization, exponent-fitting window, or precise construction of the finite-window predictor. Its caption also reports 512 Monte Carlo runs, whereas Appendix B.1 reports 128 trajectories. These details matter because truncation, fitting windows, and the relative magnitudes of direct noise and feedback can affect the observed decay exponent. Consequently, the experiment is difficult to reproduce and carries less evidential weight in validating the broader-noise regime.

Questions for authors
  1. Your related-work section acknowledges the closest analyses. Could you distinguish precisely which guarantees and proof steps extend them? In particular, please relate the general-source covariance bounds to Zou et al.\ (2023, the journal version of the cited 2021 paper), and the SHB self-damping coefficient to Li et al.\ (2024, Eq.~(F.9)). What additional arguments are required for the matching finite-time bounds under general trace-class Σ\Sigma? This distinction would help assess the size and significance of the theoretical extension.

  2. Please specify the truncation dimension, stepsize, initialization, exponent-fitting window, and formula used for the finite-window spectral prediction, including whether any constants were fitted to the observed curves. Please also resolve the discrepancy between 512 runs in Figure 1 and 128 trajectories in Appendix B.1, and explain how the displayed horizons relate to truncation and noise-dependent warmup. These details determine how strongly the experiment validates the predicted rates.

  3. Appendix I.4 claims that the coefficients representing ϕt\phi_t in the negative-real-root regime have total absolute mass at most two. However, μ=0.05\mu=0.05 and d=1.5<2(1−μ)d=1.5<2(1-\mu) give $ \phi_t=-5(-0.2)^t+6(-0.25)^t. $ Could you replace this step with a valid uniform envelope argument, including repeated-root limits, and confirm that it supports both Theorem 5.4 and the filter-retention argument used for Corollary 5.3?

Reviewer_RuBHOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors establish a modular spectral readout-theory for constant-stepsize stochastic gradient algorithms (SGD and stochastic heavy ball) in order to understand the finite-time prediction risk of these algorithms when solving least-square regression problems with quadratic objectives. The novel developed framework separate the effects of (a) the optimization dynamics, (b) readout rule, and (c) directional noise covariance/stochastic covariance feedback. The optimization dynamics tell us how errors propagate over time, the readout rule is informative on how averaging strategies assign different weights to errors and directional noise covariance is informative because it catches the covariance generated by the Hessian of the stochastic features and the error iterate. Therefore, a theory separating these three effects can reveal more information about the prediction error in the considered least-squares regression problems. An important contribution of this work is the relaxation within this theory of the uniform relative-noise assumption which is common in the literature, but it's very restrictive since it excludes trace-class noise covariances. This relaxation is significant as it allows to consider cases in which the averaged prediction risk can converge but the noise to feature covariance ratio is unbounded. The novel developed framework establish finite time spectral risk bounds for SGD and stochatic heavy ball (SHB) with matching bounds. Numerical experiments for a synthetic power-law model confirm the stochastic second moment recursion described by tailed SGD and the dependence predicted by the theory of the convergence rate on the noise spectrum. Different averaging schemes for SGD and SHB are compared on an experiment using frozen ImageNet pretrained Resnet-18 features of CIFAR-10.

Critical strengths
  1. The authors manage to show that averaged SGD can have a vanishing prediction error without assuming the uniform relative-noise condition typically assumed in the averaging/spectral risk analysis literature. This is derived under fourth moment conditions, assuming trace-class label noise and additional SGD stability conditions. This is a particular significant contribution as it allows to consider situations in which the noise is distributed across different spectral directions and is not anymore uniformly bounded by the feature covariance. This relaxed condition allows to cover the case of power-law models with convergent regimes which were not covered under the prior uniform relative-noise assumption .

  2. As mentioned in the summary section, the separation of the optimization dynamics, readout rule, directional noise covariance/stochastic covariance feedback in the newly developed modular spectral readout framework is itself an important strength of this work as it leads to finite time spectral risk bounds for several averaging schemes of SGD and stochatic heavy ball. The resulting matching bounds are helpful for explaining the influence on the covergence rate of the directional noise covariance.

  3. Even if it is not critical as the two points above, I would like to mention that the manuscript is overall well-written,and it provides.a good high-level description of the results making them accessible to ML audience/practitioners working with SGD.

Critical weaknesses
  1. It's not clear how much more informative this new modular spectral readout framework is in practice compared with current analyses of SGD and SHB, e.g. the CIFAR-10 experiment shows the behaviour of different averaging schemes but does not make a quantitative comparison with predicted directed noise and stochastic feedback contributions with measure excess risk. The practical significance of this framework for this more "refined" directional noise characterization remains unclear.
Questions for authors
  1. It is unclear how much more informative the new modular spectral readout framework is in practice compared with previous spectral risk analyses of averaged SGD (e.g. Zou el al[1] reference below ). I am referring in particular to the experiment in Section 6 "CIFAR-10 Frozen Features". Could you please quantify the direct noise, stochastic feedback contributions and compare the theoretical predictions with the obtained excess risk? In other words Can your new modular spectral readout framework give more informative predictions than exisisting risk bounds?

[1] Zou et al, Benign Overfitting of Constant-Stepsize SGD for Linear Regression, JMLR 2023

  1. Can you please provide some practical procedure on how to choose averaging windows, stepsizes or momentum using your spectral framework?

  2. Can you please provide either rule, expression, bound or some heuristics to understand how large the required warmup for tailed-averaged SGD and full averaged SHB needs to be? E.g., when the power law exponent qq in appendix G is close to one, the warmup for SGD can be very large. Is this large warmup in practice really necessary? Does this appear only due to the way you are proving the lower bound?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.