acceptodds
Under review as a conference paper at ICLR 2027

Moment-Accurate Gaussian Mixtures for Constant-Step Stochastic Approximation

Abstract

Local Gaussian models of constant-step learning predict output variability and expected losses, but weak convergence alone does not justify these moment predictions. We establish moment-accurate Gaussian mixtures by matching stationary energy with local Ornstein–Uhlenbeck limits, ruling out quadratic tail mass invisible to weak convergence. For step size , the second-order Wasserstein error is , uniformly over invariant laws, using each law's actual root weights. The assumptions combine confinement, descent, finitely many hyperbolic equilibria and root continuity with finite-variance innovations. The result yields observable covariances, expected objective gaps and first-order mean shifts, while allowing singular covariances, compatible saddles and weights without a limit. For additive noise given by a fixed invertible transform of independent standardized Student coordinates, symmetry gives an order-sharp smooth-test bound. Numerical transport calculations demonstrate the value of root-specific covariances; controlled SGD studies assess observable predictions across step sizes, batch sizes and model geometries.

Primary area:
optimization
Keywords:
stochastic approximation, constant-step stochastic gradient descent, stationary distributions, Gaussian approximation, Wasserstein distance, moment convergence, nonconvex optimization

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_mmm2OpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper gives guarantees for constant stepsize SA under only assumptions of finite hyperbolic roots and second innovation moments. The previous known result on the distributional behavior of constant stepsize SGD was in the contractive setting, so this paper gives a generalization of that. The underlying is to argue that the distribution is characterized by a mixture of gaussians determined by fluctuations each root, which lines up with intuition on contractive SA.

Critical strengths

The paper gives a meaningful technical contribution to a important problem (constant stepsize SA). The previous best known work identified Gaussian fluctuations in the contractive setting, which is where the roots are unique. Here there are mutliple roots, so the technical ideas required to get around this are substantial and comprise of the bulk of the paper's contributions.

Critical weaknesses

The assumptions are quite technical and it is unclear why certain conditions are necessary and what role they play in the proof. Very little time is devoted to explaining why they are needed and outlining the proof itself, which made the paper a bit hard to read. Nevertheless, these are minor concerns and the paper itself is quite strong.

Questions for authors

Can the method be extended to other noise settings (e.g. Markovian or multiplicative noise)? Could you elaborate more on why certain assumptions are necessary? Where might such assumptions appear/not appear in practice?

Reviewer_N2jHOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the stationary laws of constant-step stochastic approximation X_{n+1} = X_n − a g(X_n) + a ξ(X_n, ζ_{n+1}), where the drift g has finitely many hyperbolic roots and the innovations have finite second moments. It shows that the rescaled deviation from the nearest root is asymptotically uniformly square integrable as a ↓ 0, uniformly over invariant laws (Theorem 3.2). The proof matches the stationary energy identity for a Lyapunov function with the moment equation of the local Ornstein–Uhlenbeck limit. Consequently, every invariant law is approximated in W₂ to order o(√a) by a Gaussian mixture with the law's own root weights (Theorem 3.3). This justifies, at the level of moments, the standard predictions for covariance, loss gap, and mean shift (Corollaries 4.1–4.2, Theorem 4.3). These formulas appear for a single center in Mandt et al. (2017), Yaida (2019), Liu et al. (2021), Dieuleveut et al. (2020), and Allmeier & Gast (2024). The experiments use low-dimensional models and networks with up to 1024 trained parameters.

Critical strengths

The main idea is simple and effective: matching the stationary Lyapunov identity with the OU moment equation gives uniform integrability of the rescaled iterates under second innovation moments, together with covariance growth and continuity of the covariance at the roots. The remaining results, including the extension to several roots uniformly over invariant laws, follow from it by standard arguments. The argument is short, correct, and covers compatible saddles and singular covariances.

The results hold uniformly over non-unique invariant laws and cover nongradient drift and state-dependent noise, which extends the single-center results of prior work.

The examples show the limits of the theory

Critical weaknesses
  1. Global occupation is a metastability problem the paper does not address. Theorem 3.3 gives the Gaussian shape of the invariant law within each basin, but the weight of each basin is the mass the invariant law itself assigns to it. Determining these weights is a metastability problem. If the iterates cannot leave their basin, any weights are possible (Proposition K.1). For light-tailed noise that permits transitions, Freidlin–Wentzell theory gives weights of order exp(−W_j/a), so as a ↓ 0 the mass generically concentrates on a single basin and the mixture reduces to one Gaussian; the conditional statements of Theorem 3.2, which require liminf w_{a,j} > 0, then apply to one root only. A nontrivial limiting mixture arises mainly for heavy-tailed noise, which the paper treats only through a one-jump proxy (Appendix L) and a scalar numerical check (Appendix S.2). Predictions of global quantities, such as the expected loss over several minima, therefore require weights from outside the theory, and the neural experiments, which seem to be local finite-horizon runs around a single fixed root (Appendix S.1), do not test this.

  2. The assumptions exclude typical neural-network training. The paper assumes a globally Lipschitz drift, global dissipativity, finitely many hyperbolic roots, and a global Lyapunov function for the flow ẋ = −g (Assumption 2.1(3)), which excludes cycling dynamics. For SGD the Lyapunov function is the loss itself, but the assumptions force a global error bound ‖∇F‖ ≳ dist(x, roots) (equation (32)) and a bounded Hessian, which typical network losses violate: overparameterized networks could have nonisolated minima, which the Discussion leaves to future work and Appendix S.1 excludes. For adaptive methods such as Adam, no Lyapunov function with the required descent property is available. The neural experiment adds ridge regularization, a random tilt, and noise dither to satisfy the assumptions; Table 6 shows that removing the tilt and dither leaves the small-step results unchanged, but that arm is not verified against the assumptions. The largest model has 1024 parameters.

Questions for authors

see above

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

From stochastic approximation (SA) theory, we know that stochastic gradient descent (SGD) with constant learning rate fluctuates around the trained solution/stationary point rather than converging towards it (as it would happen to SGD with decreasing learning rate). These fluctuations around the trained solutions are usually "approximated" in weak convergence by local Gaussian models. The point is that weak convergence to these approximations may not guarantee that the predictions of the second moment are accurate or the expected losses are accurate. This is because some rare large fluctuations can be present in these quantities and are not catch by weak convergence. The manuscript try to addrress this limitation in the SA theory and establish moment-accurate Gaussian mixture approximations. The main contribution of the manuscript is that it shows that the invariant distribution of a constant stepsize SA algorithm (eq. (1)) can be approximated in Wasserstein-2 distance by a Gaussian mixture whose weights are essentially the occupation probability of the root. This result is established asymptotically. This result is stronger than weak convergence and provide a guarantee for the accuracy of the second moments (since it is in W2W_2). In order to do so, the authors establish an asymptotic matching of the stationary energy of the SA constant step size algorithm with that of local Ornstein-Uhlenbeck limits, ruling out quadratic tail mass invisible to weak convergence. Another contribution is that the study is carried out for finitely many hyperbolic equilibria (including certain saddle points), rather than a single equilibrium. In addition, the authors also derive asymptotic formulas for observable covariances, losses, and systematic mean-shifts. Numerical experiments, in particular in a controlled neural network SGD framework, assess the accuracy of the theoretical approximations proposed.

Critical strengths

The main contribution is the establishment of moment accurate Gaussian mixtures approximation via matching stationary energy improving standard Gaussian approximation results based on weak convergence. This leads to an approximation in Wasserstein distance of order 2. This is a stronger convergence guarantee than weak convergence and is crucial for the improving the prediction of observable covariances and expected losses (in particular when the iterates move far away from equilibrium, i.e. rare large fluctuations phenomena).

Critical weaknesses
  1. The main results in Wasserstein-2 are asymptotic and no explicit non-asymptotic finite step error bound is provided. The accuracy provided by this approximation is difficult to verify in practice and it is not clear when this approximation is reliable. It's not clear how this approximation can be used for SGD in practice.

  2. The presentation and the overall quality of the writing are major weaknesses. Since the contribution of the manuscript is primarily theoretical, I was expecting that the assumptions, notations, and main theorem statements to be presented more clearly. Moreover, several derivations of the proof in the Appendix (Corollary 4.2,4.1, Theorem 3.2/3.3) are heavily summarized and making difficult for the reader to double check the derivations and understand how the main results stated in the main text follow from the intermediate and preliminary results stated in the appendix. Several quantities are not defined when they are introduced for the first time and only stated later in the text. More discussion should be given to the limitations as they are only briefly mentioned that the future work is provided in Section 7 Discussions. I feel that the results of this work would be of interest to the ML audience working in SGD but they way that they are presented are very difficult to accessible to practitioners. Since I think this will require substantial rewriting of the manuscript from its current submitted form, I am inclined to recommend weak rejection. I recognize the theoretical contribution but the presentation and derivation of the results needs to be more polished and accessible to the broad ML community.

Questions for authors
  1. Theorem 3.2. The Wasserstein-2 approximation is asymptotic. Can you provide the non-asymptotic bound in Wasserstein-2 distance in equation (12)? Do you need additional assumptions for this derivation? This is important for practitioners working with SGD.

  2. Since the contribution of the manuscript is primarily theoretical, can you provide a more clear high-level description for the key intermediate steps that lead you to the establish the results in Theorem 3.2 and 3.3? The proof of Corollary 4.1 and Corollary 4.2 in the appendix skips quite a lot of the derivation. A more explicit derivation of these results can help to explain how the results in Theorem 3.2 and 3.3 lead to observable covariances and prediction for losses. This would improve significantly the presentation.

  3. Theorem 3.1 (Existence and concentration) page 3, is the constant KK the same for all the three bounds in equation (6)? Does KK depend from some quantities? In Assumption 2.1, equation (3): Are the constants c0≥0c_0 \ge 0, c1>0c_1 >0? is b∈Rb \in \mathbb{R} in equation (4)? In equation (5), are the constants CU>0C_U>0 and LU>0L_U >0?

  4. (Suggestion) Most of the notation for different quantities is buried in the dense text and it takes significant time for the reader to track all the quantities which sometimes are defined later in the text. A small notation section would highly improve the presentation of the material.

  5. (Suggestion) High-level descriptions of the proof and their main steps/challenges in the main text for the important results (for instance for Theorem 3.1 (existence and concentration) would make the presentation more accessible.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.