Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the convergence of SGD with momentum under linear regression with covariate shift. Data comes from $Y_i = <\theta^*, X_i> + \epsilon_i$ for a fixed $\theta^*$ and iid zero-mean noise $\epsilon_i$, but the distribution of $X_i$ varies over time ("covariate shift"), leading to non-iid samples. In this setting, the paper shows that the expected progress of SGD with momentum is a discretization of a second-order ODE. Then, the paper proceeds to show that if the covariate shift is periodic, the convergence/divergence of the ODE can be determined by looking at the spectral radius of a matrix called the monodromy matrix. The paper moves on to show experiments that test the theoretical characterizations and also investigate if different settings under relaxed assumptions show similar "resonance" behavior.

The keyword "resonance-driven divergence" in this paper can be understood as follows: divergence of SGD with momentum happens only at some specific frequency of covariate shift. Metaphorically, this is similar to breaking a wine glass with a sound wave tuned to the right frequency.

main_review: Strengths, weaknesses, and comments

1. I think the paper tackles an important question, namely the convergence of optimization methods under non-iid samples. I think the phenomenon that the paper identifies, i.e., divergence of SGD with momentum due to certain resonant frequencies in covariate shift, is an interesting observation.

2. However, my overall assessment of this paper is that the contributions are either limited or poorly presented. Proposition 1 is a result of rather straightforward and elementary calculations. The proof of Proposition 2 is very similar to Section 2.3 of (Muehlebach and Jordan, 2021) because they also use a forward Euler update of the momentum coordinates, and then use the newly computed momentum for the position update. The key difference that the ODE is time-varying is taken care of by existing results in numerical analysis (i.e., Faragó et al., 2011, as cited in the paper), so the paper's technical contribution looks somewhat weak to me. As mentioned in the paper, Theorem 1 also "relies heavily on the well-established mathematics of Floquet theory." To me it looks like a direct application of the results in (Halanay, 1966). 

3. Moreover, I believe that the presentation and discussion of Theorem 1 have big room for improvement. Theorem 1 is stated in terms of the fundamental solution matrix $\psi(t)$ and its spectral radius, and it is impossible to see how different quantities in the algorithm/data (e.g., $\mu$, $B(t)$, $T$) are related to them. When I read the paper for the first time, it wasn't obvious to me at all how Theorem 1 connects to the "resonance" behavior and why only some specific frequencies lead to divergence. Even the "Example" paragraph does not explain this resonance behavior, and it is left unclear why one gets the contours in Figure 2a. I think the solutions $\psi(t)$ are obtained numerically and it is hard to get any closed form solutions, but at least providing a more detailed explanation on the frequency responses and "peaks" should be helpful.

4. Also, I question if this paper is analyzing the "right" algorithm. The paper claims to analyze SGD with momentum, but the theoretical results only concern the version where *expected gradients* are used for the updates. By taking expectation over the joint distribution of $X_k$ and $Y_k$ at every step, the stochasticity in the data samples is essentially removed. I'm in doubt if this can really be considered "SGD"?

5. From Figure 2(a), it seems like choosing $\mu \leq 0.96$ can avoid the resonance. Also, Section 4.3 shows that the resonance is dampened when we sample less points. While the divergence phenomenon is interesting, these two facts make me think that the phenomenon might only occur in very limited settings (i.e., $\mu$ close to 1 and small noise in stochastic gradients) and hence not very relevant to practical situations.

6. Although Theorem 1 characterizes convergence and divergence of the continuous-time ODE, the discussion after Theorem 1 mentions that only the divergence part of Theorem 1 has implications for discrete-time SGDm. If our goal is to show only divergence in SGDm, I'm curious: wouldn't it be easier to analyze the (discrete-time) SGDm directly and show its divergence, rather than relying on its corresponding ODE?

Minor comments/questions

7. I believe there is a mismatch between Section 2 problem setting versus what is actually studied and tested. In Section 2 it is mentioned that the covariate $X_k$'s marginal distribution converges to some stationary distribution $\Pi$ over time. However, the ones studied later do not follow this setting. For example, the periodic covariate shift in Section 4.1 does not converge to a stationary distribution.

8. The sentence in the beginning of Section 3, "We show the parametric resonance conditions necessary to induce exponential divergence in SGDm," reads as if parametric resonance is a *necessary* condition for divergence in SGDm. However, I believe this is not the case; the paper is providing a sufficient condition for divergence.

9. In Section 3.1, "regression with covariate shift and a stationary target distribution": why is target distribution stationary when the distribution of $X_k$ changes? Maybe the authors meant that the coefficient $\theta^*$ is fixed, and the distribution of $\epsilon_k$ is stationary?

10. In Assumption 1, can't there be a situation where the expectation of $X_{k_1}$ and $X_{k_2}$ are different and the covariance matrices also differ, but they both have the same matrix $B_{k_1} = B_{k_2}$ (eq. (2))?

11. Proof sketch of Theorem 1: what is $g(t, \theta(t))$?

12. Pages 20 & 21: In the recurrence relations for $\dot \theta$ and $v$, $\theta_k$'s should instead be $\theta_k - \theta^*$?

summary_of_the_review: Although the paper studies an interesting setting and identifies an interesting failure mode of momentum methods, I believe the theoretical contributions as well as implications to practice are not strong enough to grant acceptance (comments 2 & 5). There is room for improvement in terms of presentation (comment 3), and also the analysis is carried out only using the expected gradients which I find somewhat doubtful (comment 4).
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper analyses the phenomenon of resonance in momentum SGD (SGDm) under a time-dependent covariate shift. This setting is useful to depart from iid-sampling-based theory, and could have useful implications for continual learning and reinforcement learning.
In the paper, it is shown that such a setting corresponds to a _parametric_ oscillator of the parameters, which explains instability and divergence in a non-iid SGDm setting.
The authors then test their hypothesis empirically, first in a simple setting that respects all the assumptions of the theorem, and then progressively getting rid of more and more assumptions, which ends up in finding a similar (albeit heavily dampened) phenomenon in non-linear ReLU-MLPs using Adam.

main_review: I found the paper to be quite well written and exemplary in its scientific format. A hypothesis is proposed about a phenomenon, the relevant math is derived, and then tested empirically in various settings that help us assess the correctness of the hypothesis and the relevance of the concept when departing from restrictive assumptions about the setting.

I think a weakness of the paper is that more could have been done to display the oscillation behaviours of deep neural networks. Some analyses that hold up to larger problems and deeper networks which may detect oscillation include: gradient interference, mode connectivity, or simple parameter projections. That being said I do think the current empirical content of the paper is valuable.

I'm unfortunately unable to assess the novelty of this paper. In terms of impact, coming from deep RL, these feel like very valuable insights which might actually inform my research; it's still possible that these are new insights to me only because I'm not familiar with ODE and oscillator analogies of optimizers as they exist in the supervised learning literature.
summary_of_the_review: I recommend accepting this paper. The empirical results which I am able to evaluate are correct, useful and informative. I cannot attest to the mathematical validity of the paper, unfortunately.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the behavior of SGD with momentum when the training data are not iid. The authors consider a linear regression problem with covariance drift. In this case, they show that SGDm is the Euler's method for a second order ODE with a changing coefficient. Under the assumption of periodic covariance of the data, the authors identify a resonance phenomenon between the oscillation of data covariance and the oscillation of SGDm iterator. SGDm is proven to diverge when resonance happens. Though, when there is no resonance the authors are unable to prove the convergence of SGDm. 

Beside the theory, numerical experiments are conducted for cases covered and not covered by the theory. Numerical results show a dependence of the optimizer performance and the covariance pattern in much broader settings than linear regression, even including neural networks. 
main_review: This paper points out the influence of data distribution pattern to the performance of optimization algorithms when the data are not sampled iid. It is important in the fields of reinforcement learning, online learning, etc. Both theoretical and numerical investigation are made, providing strong evidence for the existence and universality of the problem. Yet, there may be space for improvement, especially in the theoretical part. The reviewer has some major comments listed below:

1. The authors mentioned that they cannot show the convergence of SGDm when the continuous dynamics converges, because as a numerical discretization of the continuous ODE the numerical error accumulates and cannot be controlled. There is no problem with the argument provided by the authors. However, it is still possible to prove the convergence of the discrete dynamics (the SGDm), because the dynamics is linear. Here, instead of looking at the eigenvalue of the coefficient matrix of the continuous dynamics, we can directly look at that of the discrete dynamics. Then, we may be able to characterize the convergence of SGDm, which makes the picture more complete. Hence, the reviewer suggests the authors to do this analysis.

2. The "Example" part from page 4 to page 5 provides little information, because all the results and derivations are put to the appendix, and only descriptive language is used. If the authors feel the results unimportant, then you can just delete this part. But I don't think it unimportant, because this is the quantitative description of resonance phenomenon that lies on the focus of this paper. So please add more concrete results here. For example, the values of \eta, \mu, and f that result in resonance. On the other hand, section 5 is too long and can be made shorter. 

3. The numerical results cover much more general cases than the theory, and show a general connection between performance of SGDm and data covariance shift. However, it is hard to say this connection, as shown by figures for nonlinear models like neural networks, originates from the same mechanism as the resonance. Is SGDm still shows an oscillating behavior in this case? Could the authors provide more evidence that the experimental results for neural networks are also caused by a match in oscillation frequencies? Are there other reasons for the change of SGDm performance?
summary_of_the_review: The paper studies the influence of data covariance shift to the performance of SGDm. It is important to some machine learning applications. The authors uncover a resonance effect as a mechanism behind this influence. The insight is novel, the numerical experiments are extensive, while the theoretical study can be improved.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper discusses conditions under which SGD with momentum (SGDm) would diverge. Specifically, training samples are assumed to be non-iid, connected through oscillations in first or second moments. For the specific Gaussian setting of linear regression with oscillatory covariate shift, a driven (with time-dependent parameters) linear oscillator ODE is formulated for the parameters under SGDm. This allows to derive conditions, related to the learning and momentum rates, under which parameters would con-/diverge. Theoretical predictions are tested empirically, and it is shown that the basic phenomenon (resonance or at least suboptimal convergence) is also present in setups with noise, non-harmonic oscillations, other optimizers (Adam), and nonlinear regression models (NN).
main_review: In general, I really like this study. It is very systematic and thorough, with theoretical considerations as a starting point, also very well written. I also like the comprehensive discussion of caveats and remaining construction sites. I believe the topic is important; iid sampling may be an idealization often difficult to achieve in practical settings. 

Yet the potential practical implications is also one of the major critiques that I would have: Although I would agree that dependency is sometimes hard to avoid, I’m not sure how often it takes this clear-cut oscillatory form with one (or a few) dominant peaks in the power spectrum. So in my mind the consideration of at least one empirical dataset where this problem clearly arises is the most important omission from this paper. I would guess that in reality power spectra are much broader with a much wider range of frequencies covered. Does resonance, or at least a clearly suboptimal range, occur under these conditions?

My feeling is that also training algos like Adam are by now way more popular than SGDm, so it may be good to stress even more how and where the analyses give insights into the training process itself, and ways to potentially improve it even if resonance is not a huge issue. In general, more insight into why resonance problems do not arise with Adam would be helpful, or for which class of  optimizers we would expect them and which strategies protect against them.   
Growing parameter oscillations that kick the algo out of local minima again are of course known for much longer, and not necessarily related to covariate shift but just too large learning rates or similar. Maybe it’s interesting to reflect on these connections here, as increasing \nu would be a major driver of instability here as well.

Some minor issues:
- Eq. 3 w/o time-dependent parameters would be a harmonic oscillator (for some param. settings). In addition it is assumed there are oscillations in the forcing input (in moments of X), which is the source of the resonance. This could be made a bit clearer; relates to the point about growing osc. above.
- Why is it necessary to assume in setting 4.2 that \phi_1 itself oscillates; the ARMA process already implements an oscillation?
- May be good to combine Fig. 3 & 4 just for layout.
- It’s shown (sect. 4.4) that the problem becomes more severe in higher dimensions. But couldn’t this be simply avoided by proper normalization of inputs, i.e. dividing by the whole vector norm prior to training?
- I missed whether 4.6 was performed with Adam or SGDm? I assume that even for high var. (0.4) the expected loss would go away for T → \infty?
summary_of_the_review: Great and thorough paper, but empirical example that clearly demonstrates relevance would be appreciated.
review_title: null

Meta-review: This paper studies online learning using SGD with momentum for nonstationary data. For the specific setting of linear regression with Gaussian noise and oscillatory covariate shift, a linear oscillator ODE is derived that describes the dynamics of the learned parameters. This then allows analysis of convergence/divergence of learning for different settings of the learning rate and momentum. The theoretical results are validated empirically, and are shown to generalize to other settings such as those with other optimizers (Adam) or other models (neural nets). The reviewers praise the clear writing and the rigorous and systematic analysis.

3 out of 4 reviewers recommend accepting the paper. The negative reviewer does not find the main contribution interesting and significant enough for acceptance. Although I think this is a reasonable objection, it is not shared by the other 3 reviewers. Since the negative reviewer does not point out any critical flaws in the paper, I think the positive opinions should outweight the negative one in this case. I therefore recommend accepting the paper.
Decision: Accept (Poster)