Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The author analyzes the dynamics of large batch stochastic gradient descent with momentum and shows that the dynamics of SGD+M converge to a deterministic discrete Volterra equation as dimension increases. The author also identifies a stability measurement, the implicit conditioning ratio (ICR), for the stability of SGD+M and gives explicit choices for the learning rate and momentum parameter.
strengths_and_weaknesses: Strengths:
1. The author provides a non-asymptotic comparison for the behavior of the training loss under SGD+M to a deterministic function $\psi$.
2. The exact loss trajectory gives a rigorous definition of the large batch and small batch regimes.
3. The author introduces a stability measurement that exactly captures the transition of SGD+M to an accelerated method.
4. The author finds that the dynamics of SGD+M and of SGD are truly non-equivalent.

Weaknesses
1. When the number of samples (n) is small, the function $\psi$ cannot accurately approximate the training loss.
2. Factors $R$ and $\tilde{R}$, should be predefined.

questions: 1. When do we say the number of samples (n) is large? n = 1000?
2. Why does the author add $P_k$ in Eq. (4)? 
3. Since the author uses the function $\psi$ to approximate the training loss trajectory, how do you select the factors, $R$ and $\tilde{R}$ such that $\psi$ can approximate the training loss trajectory accurately?

Typos

Line 86 used a -> used

Line 91 do -> does

Line 191 discussed -> are discussed

Line 211 a produce?

Line 303 benefit -> a benefit

Line 306 achieved -> be achieved

etc.

limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies large batch stochastic gradient descent with momentum, where the setting is specialized to the least square problem with large sample size and dimension. It is shown that the dynamics of SGD with momentum will converge to deterministic dynamics described by the discrete Volterra equation, as the sample size increases. Based on this, a quantity called implicit conditioning ratio is identified to characterize when SGD with momentum can achieve acceleration. This further yields suitable choices for the learning rate and momentum parameter.
strengths_and_weaknesses: This paper is clearly written and easy to follow. The problem setting and assumptions are clarified, and the discussion on the results yields interesting observations about the behavior of SGD with momentum. However, there is still a gap between the actual convergence of SGD with momentum and the presented equivalence between SGD with momentum and the discrete Volterra equation, which makes some claims a bit misleading. See details below.
questions: Some comments and questions are as follows:

1. The paper title suggests that the dimension $d$ is high, but this is not clear from the results. For example, in Theorem 1, is it true that the result holds for a fixed $d$ as $n$ goes to infinity? This also concerns the paragraph from line 220 to 225. When $d$ is fixed, it is an over-determined linear regression for large $n$. The same problem exists in the statement of Proposition 4. If $d$ is fixed and $n$ is large, then basically each SGD step corresponds to an over-determined linear regression?  I'd like the authors to clarify the relationship between $n$ and $d$.

2. In Theorem 1, it is said that Eq.(12) holds for sufficiently large $n$. What is the threshold for being 'sufficiently large'? Also, the definition/properties of the function $H$ in Eq.(13) should be specified in the theorem statement, otherwise it is not clear what is its dependence on the problem parameters.

3. What is $\mathcal{K}$ in Eq.(15) when translating Eq.(13) into the form of Eq.(15)?

4. Theorem 1 characterizes the closeness between the SGD+M iterates and the discrete Volterra equation iterates, but only for finite $T$ and the error does not decrease with $T$. This suggests that there is a gap between the convergence of SGD+M and that of $\psi$. Thus it is misleading to make claim about the convergence of SGD+M based on the convergence of $\psi$, as in Theorem 2. I'd like the authors to discuss how to resolve this gap, otherwise the claims about the convergence of SGD+M is problematic. 
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: In this paper, the authors analyzed the dynamics of stochastic gradient descent with momentum based on the linear regression (least-squares) problems. They used the deterministic discrete Volterra equation to approximate the dynamics of stochastic gradient descent with momentum. They provided proof of convergence of the iterates of stochastic gradient descent with momentum to the discrete Volterra equation in Theorem 1. They proposed the Implicit conditioning ratio (ICR) and claimed that there are two regimes. For large batch sizes, the SGD+M performance matches the performance of the heavy-ball algorithm with Polyak momentum parameters, while there is no gain in convergence rate by increasing the batch fraction. For small batch sizes, there is still a benefit in increasing the batch fraction.
strengths_and_weaknesses: Strengths:
1) The paper has solid mathematical proof and contributions.
2) The figures in the paper are well-presented.
3) The idea of the paper has been written in a clear and reader-friendly way.

Weaknesses:
1) The organization of the paper is not reader-friendly. The figures of experiments are located in different places on paper and the setting of the experiments is in the supplementary documents. It's quite hard to follow when reading the paper.
2) There are several functions in the paper, such as h_1, h_0, H_2, which are defined in the supplementary documents. But in the main text, the authors use the conclusion from the function that F(t)-\bigO(\lambda _{2,max}^t). This may confuse readers.
3) Since there are several constants in the paper, it may be better to have a table for the definition of constants.
4) There is not enough related work discussed in the related work section.
questions: 1) In Assumption 1.1, there is an assumption about the initialization x_0, which is not normal for the problems. It is hard to check this assumption since the signal \tilde{x} is not known in practice.
2) In the experiment part, Figures 4 and 6 are based on Gaussian random least squares problems. They are based on calculating the analytic expression for convergence rate. Is it possible to plot the figure based on an empirical experiment?
3) In section 4, the authors mentioned the two batch size regimes. Providing experiments comparing these two regimes will be great to validate this claim.
4) Figure 4 and 6 are based on least-squares problems, are there similar figures for MNIST experiments?
limitations: Yes
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Analysis and characterization of two regimes for SGD on quadratic problems. Large batch setting where accelerated rates occur and small batch setting where non-accelerated rates occur.
strengths_and_weaknesses: I generally like the approach this paper takes and the theoretical outcomes. The separation of the convergence rates into two regimes makes a lot of sense and matches my personal intuition about the behavior occurring in practice. Although momentum helps stochastic optimization in many practical settings, in my experience it doesn't appear to provide "acceleration", but rather robustness and generalization advantages, and I think the behavior in practice is very much what the theory in this paper describes in the small batch setting. I don't know of any papers using large-batch training where acceleration-like improvements are observed when using momentum, I wonder if the authors are aware of any?
I'm not familiar with discrete Volterra equations, as I expect would be the case for most readers. I'm still able to largely follow the arguments presented. The results are surprisingly precise regarding the $\zeta$ and its relation to the spectrum. Some further plots showing the behavior in and around the cross-over region would be nice.

The use of text-wrapped figures here doesn't make sense to me, given that in both cases two figures are stacked, they could easily be instead stacked side-by-side and floated at the top of the pages without losing any space, I would suggest the authors do that for the camera ready. It's more readable.
questions: It's confusing to use \kappa as a constant and capital kappa for kernel, the symbols are almost the same, perhaps change the notation for the kernel to just K? a lot of papers use that.

The beginning of section two doesn't make much sense without reading the appendix, it leaves too much out.

Are the eigenvalues of H $\sigma$ or $\sigma^{2}$? Using $\sigma^{2}$ is a little odd.
limitations: A theory paper is always limited by its assumptions. The assumptions are very very strong here, almost the strongest possible given the setting. However, the results are correspondingly concrete and specific, so strong assumptions are ok.
review_title: null

Meta-review: metareview: The paper analyses an SGD with Momentum (SGD+M) in a setting where the dimension and number of samples are large. The authors provide a theoretical justification for a least square problem. 
They identify two settings based on the implicit conditioning ratio (ICR). In one setting, the SGD+M achieves linear convergence, whereas, for smaller batch sizes, the convergence speed gets worse.

In general, the paper presents novel ideas that provide new insides to a well-known and heavily used algorithm such as SGD+M. For a camera-ready version, please try to incorporate the valuable suggestions from reviewers. Thanks



confidence: Certain
Decision: Accept