Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper develops a theoretical framework to analysize the noise averged properties of  for mini-batch SGD with momentum (bSGDM) for the linear models when learning rate, mini-batch size and momentum parameter is fixed. To handle the noise terms appearing in the analysis, they approximate that variance term with specterally exprissible approximations. This approximation allows them to form a generative function for the loss function trajectory. Analysing this generating function 1- they specify the noise dominant and signal dominant phase in loss trajectory 2- when Hessian spectral distribution follows power low distribution, they analyze the stability of loss function and show when divergence and convergence happens 3- show that negative momentum sometimes can helps. They give some theoretical approximation for optimal parameter values and the phase transition times. Empirically they show that their analysis matches the practice for MNIST and some artificial data sets. 

strength_and_weaknesses: The major strength of the paper is that its analytical framework matches well enough with the empirical observation. 

The major weakness of the paper is that the provided framework is applicable for too limited cases due to their assumptions and approximations. Besides the paper is not well-written and easy to follow.

clarity,_quality,_novelty_and_reproducibility: Clarity: the problem and setting are explained well. However, the intuitions and motivation of the approximation they use is not explained enough. 

Quality: the mathematical equations are sound and look correct as much as I checked. 

Novelty: the major novelty of the paper is using the generating function to analyze the loss trajectory. 

summary_of_the_review: The major problem I have with the paper is its writing. I believe it is hard to understand and read the paper easily. Here are some examples: 

1- there isn’t any part in the paper to explains the notation and operations used in the formula. For example there U \in O(N) where U is a matrix. 

2- You claim that you drive exat loss asymptotics for bSGDM however you use a lot of approximations in your analysis. So making such a general claim is not accurate. 

3- You have some terms which are not defined explicitly. For example, \lambda_crit or regularization parameter is not defined anywhere. 

4-  The idea behind approximating eq 5 by eq 6 isn’t explained well. The paper says this is due to the existence of non-spectral details in eq 5 but this is not enough. It would be helpful to show these details and show how eq 7 would solve it. 

5- In eq 8 which is an approximate for eq 5, there are cross terms between feature maps of two different samples that don’t exist in eq 5 and it can remove the stochasticity from the dynamics. So the question is how good is this approximation i.e. the upper bound of the difference of these two eqs. 

6- For your approximation of L(t) in “Transitions between phases”, it adds eq 27a and eq 27b. However, depending on \zetta and \nu one of these equations can happen for L(t). So why the sum of them is also a good approx for L(t)? 

7- One of the claimed contributions is that “the optimal convergence rate can be achieved at negative momenta”. However, the analysis in the “negative momenta” section is hand-wavy and for a very limiting case.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work investigates stochastic gradient descent with momentum for the least squares problem at fixed design. In particular, it derives closed-form equations for the evolution of second moments of the weights and momentum parameters under a "spectrally expressible" (SE) approximation, which allow one to compute the trajectory of observables throughout the dynamics from the initial weight covariance matrix and covariance of the features (i.e. the Hessian). In particular, this approximation holds for translational invariant kernels in a grid and for Gaussian features, and Theorem 1 provides different equivalent characterisations of the proposed SE approximation. By rewriting the evolution and identifying it with an interacting gas of rank-one operators, the authors separate the contributions of the signal and sampling noise.  The authors study this evolution equations under the SE approximation and derive different regimes for the dynamics as a function of the learning rate, the momentum strength and the spectrum of the features covariance. In particular, it is observed that an unusual choice of small negative momentum can be desirable in the noise dominated phase.

strength_and_weaknesses: **Comments and Questions**:

**[Q1]**: A series of recent works have shown that the behaviour of one-pass SGD on small neural networks [Goldt et al. '20] and random features [Goldt et al. '22] as well as full-batch learning [Loureiro et al. '21] and mini-batch SGD [Bordelon, Pehlevan '21] on linear models trained on fixed feature maps are well approximated by an equivalent model with Gaussian features in the high-dimensional limit. As mentioned in the manuscript, in this case the "Spectrally expressible" approximation is exact. By the way, all of the aforementioned works contain experiments of Gaussian equivalence on MNIST, which is consistent with the authors observation that their SE approximatiom works well in this case. I wonder whether Gaussian equivalence is only sufficient for SE to hold or also necessary. In other words: do the authors have an example where the SE approximation holds but the phenomenology is different from having Gaussian features?

**[Q2]**: The sentence in the introduction:
> The goal of the present work is to derive explicit and easy-to-use analytic evolution laws for the SGD (1) applicable to modern deep neural networks trained on real world datasets.

is a huge overstating, not only given the theoretical setting considered in this work (least-squares regression) but also the lack of empirical evidence for that (i.e. checking the theory on MNIST). Moreover, the following sentence:

**[Q3]**: Moreover, in the next sentence in the introduction:
>First, in many (though not all) cases the nonlinear network training is reasonably well approximated (Lee et al., 2020) by the linearized NTK regime (Jacot et al., 2018), in which the loss L is quadratic with respect to parameters w.

Where in (Jacot et al., 2018) it is shown that NTK = square loss?

**[Q4]**: I am not very familiar with the related literature. But browsing some papers for this review I stumbled upon [Paquette, Paquette '21], who studies SGD with momentum in least squares with Gaussian random design. Their conclusion is that in the strong convex case momentum does not improve the performance of SGD, while in the non-strongly convex case it is possible to get considerable improvement. Is this consistent with taking a Marchenko-Pastur distribution for the Hessian matrix here? How does this conclusion changes as a function of the choice of feature map?

**References**:

[[Bordelon, Pehlevan '21]](https://arxiv.org/abs/2106.02713) B Bordelon, C Pehlevan. *Learning Curves for SGD on Structured Features*. arXiv: 2106.02713 [cs.LG]

[[Loureiro et al. '21]](https://proceedings.neurips.cc/paper/2021/hash/9704a4fc48ae88598dcbdcdf57f3fdef-Abstract.html) B Loureiro, C Gerbelot, H Cui, S Goldt, F Krzakala, M Mezard, L Zdeborová. *Learning curves of generic features maps for realistic datasets with a teacher-student model*. Part of Advances in Neural Information Processing Systems 34 (NeurIPS 2021).

[[Goldt et al. '20]](https://journals.aps.org/prx/abstract/10.1103/PhysRevX.10.041044) S Goldt, M Mézard, F Krzakala, L Zdeborová. *Modelling the influence of data structure on learning in neural networks: the hidden manifold model*. Phys. Rev. X 10, 041044 – Published 3 December 2020.

[[Goldt et al. '22]](https://proceedings.mlr.press/v145/goldt22a.html) S Goldt, B Loureiro, G Reeves, F Krzakala, M Mezard, L Zdeborova. *The Gaussian equivalence of generative models for learning with shallow neural networks*. Proceedings of the 2nd Mathematical and Scientific Machine Learning Conference, PMLR 145:426-471, 2022.

[[Paquette, Paquette '21]](https://papers.nips.cc/paper/2021/hash/4cf0ed8641cfcbbf46784e620a0316fb-Abstract.html) C Paquette, E Paquette. *Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Models*.  Part of Advances in Neural Information Processing Systems 34 (NeurIPS 2021).
clarity,_quality,_novelty_and_reproducibility: **Clarity and Quality**: As someone not familiar with this line of work, I personally found the manuscript dense and hard to parse. The focus of the manuscript is on the technical discussion, with the discussion reduced to enumerating the different regimes of the dynamics. The introduction largely overstates the importance of least squares.

**Novelty**: I am not familiar with the related literature, so I have limited myself to browsing some works on momentum for SGD on least squares.

**Reproducibility**: The appendix is well detailed, and code for reproducing the plots is provided by the authors.

summary_of_the_review: This work provides a characterisation of the SGD dynamics with momentum for the least squares problems with fixed design. The introduction overstates the importance of the studied setting. The manuscript is dense and hard to parse, and I feel that developing better the discussion and highlighting better the main contributions would improve the reading. For a non-expert, it is not very clear what are the challenges and the progress made the manuscript with regard to previous literature. Therefore, I believe this work could benefit from a revision.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work builds a new convergence analysis framework for SGD algorithm (with momentum). It proposes a special family functions of ”Spectrally Expressible” approximations, which provides a new perspective to understand the behavior of classical SGD. A specific senario where a negative momenta can be the optimal choice is constructed.
strength_and_weaknesses: ***Strenght***
This paper applies the generating function to analyze the higher moments of SGD noises. The new tool reveals the explicit stablility condition, which answer when SGD can converge and diverge. Most intersting part is that this paper introduces a situation where the negative momenta is better.  Also, the theoretical result perfectly explains the dynamic behavior of SGD over MNIST dataset.

***Weaknesses***
The loss function is relatively special, though I agree that this loss is widely used in modern machine learning tasks. 

clarity,_quality,_novelty_and_reproducibility: This work is well-written and completely new in this field (including both its technique and results). 
summary_of_the_review: I recommend to accept this paper as its results are impressive and really new to the community.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Summary: This paper develops a theoretical framework to analysize the noise averged properties of for mini-batch SGD with momentum (bSGDM) for the linear models when learning rate, mini-batch size and momentum parameter is fixed. To handle the noise terms appearing in the analysis, they approximate that variance term with specterally exprissible approximations. This approximation allows them to form a generative function for the loss function trajectory. Analysing this generating function 1- they specify the noise dominant and signal dominant phase in loss trajectory 2- when Hessian spectral distribution follows power low distribution, they analyze the stability of loss function and show when divergence and convergence happens 3- show that negative momentum sometimes can helps. They give some theoretical approximation for optimal parameter values and the phase transition times. Empirically they show that their analysis matches the practice for MNIST and some artificial data sets.

All reviewers agreed that this paper makes an interesting contribution to ICLR. Some concerns were expressed about the clarity of the writing in the original reviews, but the authors have addressed them nicely in a revision for which both reviewers LoFN and KUvw thought improved significantly the paper and updated their recommendation (after discussion) to acceptance.

justification_for_why_not_higher_score: None of the reviewers confidently wanted to highlight this paper.
justification_for_why_not_lower_score: All reviewers recommend acceptance.
Decision: Accept: poster