Resonance in Weight Space: Covariate Shift Can Drive Divergence of SGD with Momentum
Authors: Kirby Banman
Garnet Liam Peet-Pare
Nidhi Hegde
Alona Fyshe
Martha White
Venue: ICLR 2022 Poster (2022)
Keywords: optimization
momentum
stochastic gradient descent
non-iid sampling

Abstract: Most convergence guarantees for stochastic gradient descent with momentum (SGDm) rely on iid  sampling. Yet, SGDm is often used outside this regime, in settings with temporally correlated input samples such as continual learning and reinforcement learning. Existing work has shown that SGDm with a decaying step-size can converge under Markovian temporal correlation. In this work, we show that SGDm under covariate shift with a fixed step-size can be unstable and diverge. In particular, we show SGDm under covariate shift is a parametric oscillator, and so can suffer from a phenomenon known as resonance. We approximate the learning system as a time varying system of ordinary differential equations, and leverage existing theory to characterize the system's divergence/convergence as resonant/nonresonant modes. The theoretical result is limited to the linear setting with periodic covariate shift, so we empirically supplement this result to show that resonance phenomena persist even under non-periodic covariate shift, nonlinear dynamics with neural networks, and optimizers other than SGDm.

Published as a conference paper at ICLR 2022
RESONANCE IN WEIGHT SPACE: COVARIATE SHIFT CAN DRIVE DIVERGENCE OF SGD WITH MOMENTUM
Kirby Banman', Liam Peet-Pare', Nidhi Hegde', Alona Fyshe', Martha White' Department of Computing Science', Department of Mathematical and Statistical Sciences?
University of Alberta
Edmonton, AB T6G 2E8
(kdbanman, peetpare, nidhi .eedde, alona, whitem] @ualberta.co ca
ABSTRACT
Most convergence guarantees for stochastic gradient descent with momentum (SGDm) rely on iid sampling. Yet, SGDm is often used outside this regime, in settings with temporally correlated input samples such as continual learning and reinforcement learning. Existing work has shown that SGDm with decaying step- size can converge under Markovian temporal correlation. In this work, we show that SGDm under covariate shift with a fixed step-size can be unstable and diverge. In particular, we show SGDm under covariate shift is a parametric oscillator, and so can suffer from a phenomenon known as resonance. We approximate the learning system as a time varying system of ordinary differential equations, and leverage existing theory to characterize the system's 's divergence/convergence as resonant/nonresonant modes. The theoretical result is limited to the linear setting with periodic covariate shift, so we empirically supplement this result to show that resonance phenomena persist even under non-periodic covariate shift, nonlinear dynamics with neural networks, and optimizers other than SGDm.
INTRODUCTION
Stochastic gradient descent (SGD) (Robbins Monro 1951) and its variants such as Adagrad (Duchi et al. 2011), ADAM (Kingma & Ba 2014) and RMSprop (Hinton et al., 2012) are very widely used optimization algorithms across machine learning. SGD is conceptually straightforward, easy to implement, and often performs well in practice. Among the variants of SGD, accelerated versions based on Polyak's 's or Nesterov's acceleration (Polyak 1964; Nesterov] 1983), known generally as Stochastic Gradient Descent with Momentum (SGDm), are used widely due to the improvements in convergence rate they offer. SGDm can give up to a quadratic speedup to SGD on many functions, and is in fact optimal among all methods having only information about the gradient at consecutive iterates for convex and Lipschitz continuous optimization problems (Nesterov 2004 Goh 2017). SGDm has the same computational complexity SGD, but exhibits superior convergence rates under reasonable assumptions (Su et al. 2014)..
These convergence results for SGDm, however, rely on independent and identically distributed (iid) sampling. Little is known about the convergence properties of SGDm under non-iid sampling, yet the non-iid setting is critical. In many machine learning problems
expensive impossible to obtain iid samples. In online learning (Rakhlin et al. (0100) and reinforcement learning (RL) (Sutton Barto 2018), the data becomes available sequential order and there is temporal dependence among the samples. There is particularly strong temporal dependence in RL. where observed states are sampled according to the transition dynamies of the underlying Markov decision process (MDP).
Federated learning (Hsich et al. 2020) and time-series learning (Kuznetsov & Mohri 2014) provide further examples of when non-iid sampling is essential to the learning problem.
Without momentum, SGD's convergence rate has been examined under non-iid sampling with the stochastic approximation framework (Benveniste et al.] 2012 Kushner & Yin (003). and more recently under specific assumptions of ergodicity (Duchi et al. 2012 or Markovian sampling (Nagaraj ct al. 2020; Doan et al., 2020b) Sun et al., 2018). Convergence rates under Markovian sampling also known for ADAM-type algorithms when applied to policy gradient and temporal difference

---

Published as a conference paper at ICLR 2022
learning (Xiong al. 2020). To our knowledge, however, there has been little work providing convergence rates or guarantees for SGDm under non-iid sampling. In (Doan et al. 2020a), a progress bound is provided for SGDm under Markovian sampling based on mixing time the time required for a distribution's is convergence toward its stationary distribution-alon guarantee under decaying step-sizes. In this work, we assume fixed step-size, since it is common choice in the online setting, especially when the practitioner is unsure of mixing rate or stationarity.
with a convergence rate
There is broad literature using ordinary differential equations (ODEs) analyze gradient descent methods by approximating descent updates as continuous-time flows. Early work is comprehensively discussed in (Kushner Yin 2003] Benveniste et al. 2012). Despite the age and establishment of the linear setting, the gradient flow lens continues to reveal new insights (e.g. implicit rank reduction
(Arora et al. ))19)) and new perspectives on old insights (e-g. regularization of early stopping (Ali
et al. 2019)). Recent work has paid particular attention to the flow induced by momentum accelerated
methods (Su et 2014| Wibisono al.) 2016 Wilson al.] 2016 Scieur al. 2017 Muehlebach &
Jordan 2021
Diakonikolas & Orecchia 2019; Muchlebach & Jordan 2019: Li et al. 2017 Simsekli
ct al. 2020 Betancourt et al. 2018 Kovachki & Stuart 2019 Attouch et al. 20118) Shi et al. 2019
Siegel 2019: Zhang et al. 22118] Berthier et al. [202 Kovachki & Stuart 2021). In these works, it is demonstrated that linear regression under iid sampling with SGDm can be represented as an ODE
resembling harmonic oscillator, sometimes with a time-decaying damping coefficient.
Contributions: In this work, we show that non-iid sampling, due to covariate shift, induces a related system: the parametric oscillator, a harmonic oscillator having coefficients which vary over time in a manner capable of exponentially exciting the system (Mumford 1960; Csörgö & Hatvani 2010 Halanay 1966). We characterize the underlying maryvngying ODE, which requires novel approach to incorporate covariate shift, and develop specific conditions on covariate shift that lead to divergence in SGDm. We provide an empirical design, with synthetic data, to systematically test the response of the learning system to different covariate shift frequencies. We empirically validate that resonance- driven divergence occurs in a learning system which aligns well with theoretical assumptions, We follow with similar demonstrations on learning systems which progressively relax further and further away from our theoretical assumptions, including non-periodic covariate shift, learning with neural networks and optimizers other than SDGm. The implications of this work are that resonance can occur in learning systems with momentum, causing instability or poor accuracy, simply due to certain temporal correlations in the input sequence. Our results provide novel direction to better understand the properties of our learning systems for time varying paputs-naman beyond iid sampling and point to a gap in the robustness of our algorithms that merits further investigation.
2 PROBLEM SETTING
We investigate the effect of non-iid sampling on a model optimized us- ing SGDm. We assume labelled training data sampled from discrete- indexed, real-valued stochastic pro- cesses {Xe)keN and {Yx) keN such that hee has a unique stationary distribution 11. Ys is function of X₁ with zero-mean observation noise, Ys = f(x)) + cg. The learning al- gorithm does not have access iid samples from IT. Instead, the learning algorithm may only update parame-
R=1
MRR, of)
V4 Ke 0,
2=2
Ye n 1ixi
AR--,, o*)
X1 ~ MRR o²)
Figure 1: An example of the problem setting. ID regression (left), Gaussian covariates {X&} with shifting mean 2g over time (right).
ters 0g at time k using samples zạ (æg, yk), where X 's marginal over time converges to IL. The goal is to train a model with parameters 0 to minimize an objective function L(z; with respect to the stationary distribution II: 8" = arg mingers En 0) fa L(2; (x) An example of this problem setting is illustrated in Figure
This setting is identical to that explored in prior work Markovian sampling (Sun et al. 2018 Xiong et al. [2020] Nagaraj et al. 2020). but we do not require that our stochastic processes adhere to the Markov property. Note, also, that the underlying functional relationship between the inputs, Xt.
2

---

Published as a conference paper at ICLR 2022
and the targets, Yk, does not change over time. That is, the non-iid sampling is result of covariate shift rather than a changing relationship between the inputs and targets.
We consider Polyak's ' Heavy Ball method (Polyak 1964) with the formulation from Sutskever et al. (2013), namely SGD with momentum (SGDm)
1k+1 = μu vy oz 0%)
0 = 02 + 2k+1
(1)
where 7 2 O is the learning rate and μ E (0, 1) the momentum coefficient. Our goal is to understand the behavior of SGDm when learning on this non-iid sequence 2k-
COVARIATE SHIFT AS A DRIVING FORCE
In this section characterize SGDm discretization of a particular parametric oscillator in continuous time. A parametric oscillator resembles a harmonic oscillator ODE, but has time-varying system coefficients which are capable of driving the system. It well understood that parametric oscillators can suffer from global solution instability due to coefficients oscillating at particular frequencies (Halanay 1966), a condition known as parametric resonance. We show parametric resonance conditions sufficient to induce exponential divergence in SGDm. We provide proof sketches and defer complete proofs to Appendix [..e
Notation: Capital letters are matrices and random variables. {Xxa} } is stochastic process, shorthand for (Xx keN. l and index discrete and continuous time, respectively. When a discrete sequence and function approximate each other, they share the same symbol and are differentiated by subscript and function argument l, e.g. the sequence }0x. and the function (t). Pk is the joint distribution of X5 and Yg. For loss function L(2; 8) training pair 2 (z, y) and weights 8, we denote the time- varying expected gradient gl (0) == Ep, (2;((;)0)
3.1 COVARIATE SHIFT INDUCES A LINEAR TIME- VARYING EXPECTED GRADIENT
We begin by showing that linear least squares regression with covariate shift and fixed target induces a linear time-varying expected loss gradient. That is, the gradient function ga (0) B& (0 0*) for some matrix Bg that varies with time, due to covariate shift.
Assumption 1. The covariate generating process {X&]kEN is not identically distributed: Corr (K., Xx,) + Corr(XX2: Xkz) for some K1, k2 N. Assumption 2. The targets Ys are fixed linear function of X with iid zero-meat observation noise, 6g such that [[{x] = 0. That is, Y₁ = (0", Xx) + eg where 0" E &Rd is fixed for all k.
Proposition 1. Under Assumptions 1 2 linear model with weights Og making predictions Vs. (0s, Xx) with a mean squared error (MSE) objective will induce time-varying linear expected loss gradients ga (0x) = (0, - 0*) for all k E N, where B₁ E Idd and BR. & Bk, for some k1, k2-
Proof Sketch: We fix a time step i and take the expectation of the MSE loss over observation noise, and over the distribution of Xg. A time-varying expected loss surface remains, and the linear setting implies the loss gradient is linear function for all steps k. with BN depending on X
B 2Cor (X,, X²)) = 2Cov(X,, Xx) + p.p [X,] [X&]
(2)
3.2 ODE CORRESPONDENCE
Next, we show that the iterates }0x} generated by SGDm are a first order numerical integration of a particular ODE. The procedure is similar to (Muchlebach & Jordan| (021). but due to the time-varying loss gradient, we must pay specific attention to the conditions on the ODE necessary to have integration consistency, Let Btt) be mnatri--valued function, Lipschitz continuous in t, such that ( [Bx] are samples spaced / apart, iee. B = Blk)).. The existence and uniqueness of this B(t) ensured if we assume the {X₂} } are sampled from underlying continuous -immee X(t).
Proposition 2. The SGDm iterates {0k} numerically integrate the ODE system in equation with integration step f and first order consistency.
0(1) + 1- H4 0(1) + B())((()) - 0==
(3)
3

---

Published as a conference paper at ICLR 2022
Proof Sketch: First, the ODE in equation B is converted first order linear form, and split into sum of two separate systems. The sum's 's terms have implicit and explicit Euler integrations: using operator splitting, these can be composed into a consistent numerical integrator for linear vire-ig systems. Then, it is shown that the composed integrator is precisely equivalent to SGDm when the integration time step is VT.
The first order consistency guarantee in Proposition 2 means that when the step-size rj is small and initial conditions agree between continuous and discrete time, i.e. Oo = ((0), the continuous and discrete time trajectories approximate each other as 0s s /Tk) where the difference between them depends on the integration time step /1 (Hairer et al. 2006). Therefore, assuming 6 = @(0). the difference accrued in one step of k (local error) is 81 = (VT) + +17) and over arbitrarily many steps (global error) is 0g = O( (T)) + (nnk)
3.3 PARAMETRIC RESONANCE FOR ODE CONVERGENCE AND DIVERGENCE
The conditions sufficient for convergence and divergence in equation 3 may be shown using estab- lished dynamical systems theory. The conditions sufficient for divergence are precisely the conditions for parametric resonance, when (() is periodic. Note that periodicity in the first or second moment of { } is sufficient to induce periodicity in (I). As per elementary results in linear ODE theory, the system in equation can be transformed into linear time-varying first order form
(aax B())
Iaxd
((t) = (())
A(t)
V4 Taxx
(4)
where solution trajectories ((t) of equation 3 are embedded in solution trajectories E(t) of equation 4
Equation 4 admits a fundamental solution matrix]] [ (t) such that the spectral radius p of (T) characterizes ODE instability, which implies divergence for SGDm, in Theorem []
Theorem 1. When B(t) is periodic such that B(t) B(t for some T > the spectral radius
p of (T) characterizes the stability of solution trajectories of equation 3 Bas follows:
p >>1 = trivial solution O(t) = 0" is unstable. All other solutions diverge as 0(1) - 0o
exponentially with rate p.
p < = trivial solution is asymptotically stable, all other solutions converge as @(t) + l" exponentially with rate p.
Proof Sketch: ODE 3 stability depends on the relationship between the coefficient 1-# and the
vi
expected gradient signal because they determine the spectral radius of (T)). The spectral radius p is the convergence/divergenes rate per period T towards/away from the stationary point 0* O
The spectral radius conditions characterize when ODE solution trajectories O(t) will converge or diverge, and Proposition tells us that these solution trajectories are approximations of discrete time SGDm trajectories {0,} under identical initialization. But does convergence or divergence of (()) imply the same for SGDm? Experiment 4.1 empirically suggests that the approximation is sufficient, since the boundary at p = 1 in Figure 2a agrres with both continuous and discrete time. However, given Theorem and Proposition 2] we have theoretical guarantee of SGDm's 's divergence, but not its convergence. This is because the divergence rate of ((L) exponential, and Proposition provides bound on long tail behaviour as 0₂ ((vTk) ((p)). Since the approximation error lincar in time k. and the divergence rate is exponential, the divergence rate dominates, and we are guarantced that diverging ((t) corresponds to diverging (0x), ). However, the same argument does not imply that a convergent f(t) corresponds to a convergent {0x ). because the linear error bound technically permits the discrete trajectory escape 8* at linear rate. Empirically, we see agreement for both convergent and divergent cases, but we defer theoretical proof to future work.
Summary: There is chain of dependencies starting from the non-iid sampling in (Xx), and ending at the monodromy's spectral radius.
(X+) (() (()) A(t) (t) (T) P
In order, we have the discrete stochastic process {X,} from which training inputs are sampled, and its underlying continuous stochastic process X X(I.. If {Xx} and X(I) were iid, then the matrix B
A fundamental solution matrix for system equation
4 is any matrix-valued function of time (t()) whose
columns are linearly independent solutions to equation
We choose (f) such that (0) Tzdx2d-
4

---

Published as a conference paper at ICLR 2022
would be constant, but the non-iid nature means (t) is function of time. The matrix A(t) is the matrix describing SGDm's continuous time dynamics linear time-varying ODE = A(t) and the matrix (t)) is a simply a submatrix of (t). Since we have a linear ODE, the space of solution trajectories is spanned by the columns of the ODE's fundamental solution matrix (t).. Moreover, since we have a periodic A(t) with period T,, the stability of all solutions can be determined simply from the largest eigenvalue of (T), a.k.a. its spectral radius p.
The intuition behind p's importance comes from the following fact: after each elapsed period T, the phase space (including weight space) subject to the linear transformation (T'). So as time increases, say n. periods, the linear transformation is applied iteratively (T))", so it is clear that any eigenvalue larger than unity means all solutions eventually diverge exponentially. This precisely the parametric resonance condition. For detailed example of all these quantities characterizing the divergence a simple learning system, see Appendix A.I
There are two key novel technical contributions to obtain the results above. (1) The ODE correspondence for non-iid data in combination with momentum methods is new. The non-iid data, which induces time variation in ODE dynamics, is subtle to address, because elementary ODE correspondence (i.c. consistency guarantces) require time invariant ODE dynamics. Our proof specifically addresses this difficulty using operator splitting theory from recent numerical integration literature. (2) Once we have this ODE, is straightforward to recognize that is a parametric oscillator. The utility of this connection, however, is that it opens up entirely new avenues for analysis, since there is deeply established literature on the dynamics of these systems. The primary second technical novelty, therefore, is leverage this connection, and use Floquet theory give precise divergence conditions for given 1) and μ. under periodic covariate shift.
Technical Novelty:
4 VALIDATING THEORY & ABLATING TOWARDS CONDITIONS IN THE WILD
We now empirically evaluate the effect of resonance in learning problems. First, Experiment 4.1 validates the theoretical predictions by investigating the dynamics of learning problem which closely matches the theoretical assumptions in Section 3 Specifically, we assess whether or not the spectral radius P predicts optimizer convergence divergence. Then, the remaining Experiments 4.2 4.6 test for this phenomena in settings beyond our theory. Each experiment makes a single step away from a theoretical assumption, first relaxing the periodicity assumption, then using stochastic rather than expected gradients and then moving to nonlinear models (neural networks) and optimizers (ADAM).
Across all experiments, input samples at each training step are drawn from Gaussian distributions with diagonal covariance matrices, i.c. X₁ ~ (āx,, claxa), and we induce covariate shift by constructing a time-varyee vare-varying mean sequence { Each mean sequence designed such that (a) its frequency content can be swept with a single parameter f or T and (b) iid sampling is induced by setting f = 0 or T = O, so that each experiment has an iid baseline for comparison. The specification of & is provided in Table [ for each experiment. This empirical design allows us to systematically test response to different frequencies. See Appendix [A.3 specification of all experiment details, including visual depictions of all synthetic {X&} and their frequency content.
4.1 VALIDATING THEORY
We start in a setting as close as possible to the theoretical predictions, with linear regression for quadratic loss, and covariate shift such that the mean E E[X,] varies as strict sinusoid. We perform regression in two weights (i.e. inputs Xş and labels Y, are veluud))alued). We draw 20 samples from each XR. so that the loss gradient for each time step & is close to its expected value.
Since we have only two weights, the learning system's 's underlying ODE can be easily specified, such that the fundamental solution matrix can be numerically computed. As per Theorem we can use the spectral radius of the fundamental solution matrix evaluated at time T' to make theoretical predictions of where the system should converge or diverge. As depicted in Figure 2a the theory agrees very well with empirical results. This suggests that parametric resonance is indeed the dominant mechanism behind SGDm divergence under covariate shift. In the appendix, refer to example A. for the procedure used to compute the theoretical predictions (i.e. spectral radii p). and Figure ba for the full surface from which the contour lines in Figure 2a are rendered.
5

---

Published as a conference paper at ICLR 2022
Table 1: Covariate shift details for each experiment.
Experiment
Sweep Param.
Mean Sequence {Tx KENN
4.1
Validating Theory
f E [0,0.05]
Øy = 0.5 ( (2 TT 1/f
Fy = 01 + 02 + En
Ablating Periodicity
f E [0, 0.05)
Φ = 402(02 - 1) cos(2
22 εk. 31, 32 Table B
E
if
2k
0 mod 1
4.3
Ablating Expected Gradient
T E [0, 120]
if
2
mod
& ~ NO, Taxa) iid
k
3x & where
4.4
Ablating Periodicity Further
T E [0, 50]
T
5. ~ (0, vlaxa) iid
4.5
Ablating Optimizer Linearity
T' E [0, 100]
3g same as above.
4.6
Ablating Model Linearity
T E [0, 100)
3g same as above.
0.99
0.99
0.97
0.97
0.96
0.96
0.95
0.95
Inf
180
90
60
45
36
30
26 22 20
inf
180
90
60
45
36
30
26
22
20
Cov. shift period T
Peak freq. period T
(a) Resonance regions for sinusoidal Fe
(b) AR(2) Stochastic Mean
Figure 2: Empirical heatmap of momentum versus period T for SGDm for linear regression,
overlaid by contours of theoretical prediction. Each pixel is the distance |10, 1 0-]] averaged over the final 500 steps i and 10 runs. Dark pixels converge quickly and stably, bright pixels diverge exponentially. The contours show divergence predictions from Theorem T the white contour has 1, with p increasing with redness.
4.2 ABLATING PERIODICITY
We repeat Experiment 4.1 but with the mean of X₃ varying stochastically instead of deterministically, The result in Theorem ! assumes the expected gradient varies periodically over time given fixed weights 0. But even with aperiodic and/or stochastic time variation, our LTV system equation 4 might be similarly susceptible to instability; the theory does have periodicity as necessary condition of divergence. To test this, we replace our periodic covariate shift mean with mean that moves according to an AR(2) process. The AR(2) process is tuned have frequency peak exactly at the frequency of the sinusoidal covariate shift of Experiment 4.1 to change only the nature of the than the frequency.
shift aefftt-pprroiiitt---reeee
We can see from the heatmap in Figure that that under this setting we observe very similar resonance behaviour in the learning system, which aligns well with the identical predicted stability regions. Note that both theoretical and empirical results in Figures aajand 2b suggest that sufficiently low momentum values μ mitigate the resonance phenomenon, which agrees with the role it plays in the ODE system: decreasing μ increases damping. We also observe that resonance regions shrink as step size 7j is decreased; see the Appendix for plots demonstrating this trend. Analytically characterizing the bounds of stable n. v in terms of system properties is interesting future direction.

---

by Published as a conference paper at ICLR 2022
4.3 ABLATING EXPECTED GRADIENT
Here we perform linear regression with periodic mean covariate shift, and ablate the number of samples drawn from each Xx show the effect of increasing noise in the gradient signal. Linear regression is performed mapping R + I, with the weights learned via SGDm. The mean sequence I& oscillates with strict periodicity between =ē, where is a unit norm 5-vector randomly chosen for each run. i.e. the mean signal is square wave in R with period T. Linear regression implies a quadratic loss, and peri- odic covariate shift implies a loss with periodic time variation in expectation, so we are very near to the setting in which Theorem T is directly applicable. However, as we ablate from 5 samples to sample drawn from each Xx, we move further away from the expected gradient, towards the fully stochastic gradi- ent setting. As we can see in Figure resonance is dampened by stochasticity in the gradient signal, but nonetheless is still present. These findings are further supported in Appendix [A.3] where Experiments 1.1 4.2 are also ablated from expected to stochastic gradient signals.
10
per X per X2 per X 2 per X per X₃
110-0*11
10
10a
10a
100
Mean period T
Figure 3: Regression w/ periodic Fg. Each dot is avg. dist. ||0g 0"ll over final 500 steps. Each color has three peaks: the left peak exceeds y scale for all curves, the center peak is small enough to appear only for the black curve, and the right peak appears for all curves (vanishingly small for the black curve.) Resonance is dampened and decreasing samples per Xx.
4.4 ABLATING PERIODICITY FURTHER
We further depart from strictly periodic covariate shift by having piece-wise stationary means and non- smooth changes: we randomly sample a new mean from normal distribution N (0, x²) after every T update steps. We further investigate the impact of this covariate shift under (a) increasing variance ? and (b) increasing dimensionality of the inputs.
We observe divergence characteristic of the parametric resonance, with smaller T having a highly divergent response. In Figure 4a we can that higher variance results in much more instability, though even for smaller variance the distance to 8 is still on the order of 103. This results makes sense, as the variance is connected to the driving signal amplitude, on which parametric resonance has a strong dependence. We also observe a strong dependence on the number of input space dimensions, in Figure 4b This aligns with the fact that the expected norm of samples drawn from multivariate Gaussian increases with dimensionality, even with fixed covariance scale (of 0.1). This result suggests that resonance phenomena may actually be exacerbated for higher-dimensional inputs, which is the setting we expect to see in practice.
4.5 ABLATING OPTIMIZER LINEARITY
So far our experiments have ablated periodicity, input dimensionality, and gradient stochasticity. As per the conditions in Section 3 each of these ablated systems still corresponds to a discretization of an LTV ODE. We now ask whether resonance can be observed in systems which do not correspond to discretization of our ODE. To investigate this hypothesis, we replace SGDm with ADAM as an update rule for our learning algorithm. We no longer have the ODE representation of this learning system, but can empirically investigate the behaviour of the system under covariate shift.
We use the same stochastic mean switching problem as the previous experiment, where we regress from 5 dimensions to I with input samples. Again, measure the distance | -0"1, and vary the ADAM parameter 31. Similar to the SGDm optimizer, we can see in Figure 4c that there is a band of mean switching intervals T for which convergence is worse.
Unlike SGDm, there is no divergence. Proper parametric resonance induces exponential divergence, which is why the previous results were presented with Euclidean distances between weights on the order of 19 Note that in Figure 4c the frequency response in weight space distance is instead measured on the order of 10
7

---

Published as a conference paper at ICLR 2022
10a0
1000
Ry variance 0.4
inpul dimensions
||0-0%||
X, variance 0.3
||0-0*|1
input dimensions
& variance 0.2
Xx variance
Input dimenslons
10.0
Xy variance
1040
input dimensions
10a
10a
10a
10a
10
40 Mean shift interval T
50
10
20
30
50
Mean shift interval
(a) SGDm w/ stochastic Fk, variance sensitivity
(h) SGD w/ stochastic 7k. sensitivity to d
Figure Regression w/ stochastic Tg. Each marker is avg. distance ||0, 0-1 over final 500 steps (al and (D or 2000 steps (c). For SGDm, resonance very sensitive to the 2e signal variance (i.e. amplitude) in @ and the number of input dimensions (b). For ADAM in (c). convergence affected by specific frequency content (x-axis) but does not diverge, suggesting that the frequency re- sponse is significantly damped. Similar SGDm, response is higher for larger momen- tum parameters 31.
B = 0.99
B 0.975
8: -
10a
8.
||0-0*11
10
20
40
60
80
100
Mean shift interval T
(c) ADAM w/ stochastic æk. 31 sensitivity
4.6 ABLATING MODEL LINEARITY
Our final step away from ODE equation 3 abandons the quadratic loss surface. We fit nonlinear target function using a fully connected Rel.U network, reusing the previous covariate shift. In previous experiments, we measured the distance ||0,- 0* Now unique target is not guaranteed, so frequency response is in terms of loss. In order to amplify frequency response, samples were drawn from each Xş to reduce gradient signal noise.
Figure a band of mean switching intervals T which damage convergence, which is characteristic of resonance. Though we do not see divergence, the impact accuracy is problematic. In this case, models with loss > 0.3 fit extremely poorly, but those with < 0.05 perform well.
X variance 0.4
& varlance 0.3
R, variance 0.2
N variance 0.1
EnL
X variance 0.0
0.2
DISCUSSION
20 40 60
80 100
Mean shift interval T
This work first step towards understanding fre- quency response due to covariate shift. Here we discuss future directions, limitations, and practical- ity.
Figure 5: Training neural network with SGDm shows peak response in the loss around the band T 40). The y-axis is average test loss over the final 2000 training steps over 20 runs, with test set obtained via the stationary distribution of (X&). Shaded regions are 95% confidence intervals.
Limitations and Next Steps: our theoretical analysis, we take expectation over observation noise and over the distribution of inputs Xx. so the gradi- ent coefficient matrix Bt)) in the ODE equation 3 is deterministic. This allows rigorous characterization of resonance for periodic (t)). Experiments 4.2 and 4.4 demonstrate that resonance still drives divergence when B(t) is nondeterministic, so rigorous exploration in future work might employ stochastic differential equations. In particular, Experiment 4.2 aligns exactly with the theoretical predictions, suggesting that the resonance in response to the frequency content of X,, not its periodicity.
8

---

Published as a conference paper at ICLR 2022
For the sake of consistency across experiments, our non-iid sampling is always induced by Gaussian X3 with fixed diagonal covariance matrix. But Assumption [ is far more relaxed, suggesting resonance is possible with time-varying covariance and non-Gaussian distributions, which may be explored in future empirical work
When assessing a new phenomenon like covariate shift resonance, assessment on simple problems is a critical first step, and we have endeavored to be comprehensive in that assessment. But we only scratch the surface of more complex optimizers and nonlinear models. Similarly, for the sake of experimental control and interpretability, we assess resonance on synthetic data instead of real data. While it is obvious that many sources of real data have nontrivial frequency content (e.g. audio samples, machine sensors, etc.) it is not yet clear when realistic frequency content will resonate with the system trying to learn from Optimizers, models, and data all pose exciting future directions for this work: to extend into the frequency response of more complex optimizers and models, and into the frequency content of real data.
Finally, the theory in this work is for linear models. This is the correct setting to understand first, and is independent interest. Our theory applies to any linear models that are augmented with a nonlinear basis (such as a Fourier basis, polynomials or radial basis functions) by examining the frequency content of the basis output signal.
Practical Implications: One potential conclusion from results is that though resonance could potentially arise in our learning systems, may not be problematic. First, the heatmaps in Figures 2a and 2b indicate that SGDm converges much more often than it diverges, and that we can practically avoid resonance simply by reducing the momentum parameter μ.. As per Appendix [A.2 we find that sufficiently low f does mitigate resonance. Second, we may simply be able avoid covariate shift in the first place, by keeping buffers of data and shuffling samples.
[A.2
However, the reality is not so simple. Higher levels of momentum are typically more effective in practice. There is tension between the level of momentum and avoiding resonance, that cannot casily be addressed by simply picking low momentum by default. Instead, smarter approaches which recognize potential resonance and then reduce momentum may be much more effective way to guard against this issue: the development of such methods can leverage the insights in this work. addition, relying on rell-behaved or shuffled inputs may be impractical in certain settings. Algorithms in signal processing and the streaming literature often process data sequentially. Reinforcement learning approaches use sliding window buffers (in replay), where covariate shift may still persist across buffers. Further, it is even possible that adversarial attacks could be designed to exploit this weakness of SGDm, causing poor performance or even instability from attackers attempting to generate data that results in resonant behavior.
Our work also suggests avenues towards the development of diagnostic tools. Indeed, our experimental approach to investigate this phenomena mimics those in the modal analysis literature (Avitabile 2017). We treat the input sampling process vary the signal's frequency content across a wide band, and measure the learning system's output as a response across input frequencies. This is analogous oscillatory vibration within machine's 's engine compartment, sweeping across frequencies, and measuring the resulting vibration amplitude in the machine's 's housing.
input signal which is noisy and/or stochastic,
mechanical engineer triggering an
CONCLUSION
To our knowledge, this work is the first investigate SGDm under covariate shift from the ODE perspective. This perspective reveals new insights, in particular the revelation that SGDm under covariate shift numerically integrates a parametric oscillator, rather than the simple undriven harmonic oscillator induced by iid sampling. We leverage dynamical systems theory to analyze the stability of a learning system using SGDm under covariate shift, and are able to provide conditions for exponential divergence due entirely to the frequency content induced by this non-iid sampling. Despite its age and establishment, understanding SGDm is an ongoing process. We contribute to this process in a way that provides physical intuition, rather than merely algebraic proof. We hope that the connection we have drawn to parametric oscillation in dynamical systems theory will help to further propel understanding of non-iid sampling and SGDm.

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGEMENTS
We would like to thank Yurij Salmaniw and Ryan Thiessen for their discussions regarding Floquet theory and helping us makes sense of differential equations. We would also like thank Csaba Szepesvari for pointing us to excellent resources for numerical integration, algorithmic convergence, stochastic processes, and various future directions for this work.
ETHICS STATEMENT
Our work is theoretical and attempts provide greater understanding of an optimization algorithm. Due to the remoteness of this work from direct ethical concerns, it is difficult to reason about any ethical implications of the work. We hope that the insights into SGDm could help to make machine learning algorithm more robust, but beyond that we are not aware of any ethical concerns or implications of this work.
REPRODUCIBILITY STATEMENT
We have endeavored to be very clear and thorough in our explanation of the theoretical results, and all assumptions and proof's are explicitly stated and contained in either the main body of the paper or in the appendix. The code for all of the experiments is included the supplementary material and the instructions for reproduction are in the README file. The data used is synthetic and code to generate the data contained in the supplementary material. All the experimental details (e.g. hyperparameter selection) are contained in tables in the paper and appendix and the supplementary material. All of the experiments should be easily run on modest commodity hardware in the space of few days, at most.
REFERENCES
Alnur Ali, J Zico Kolter, and Ryan Tibshirani. A continuous-time view of early stopping for least squares regression. International Conference on Artificial Intelligence and Statistics, 2019.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Neural Information Processing Systems, 2019.
Hedy Attouch, Zaki Chbani, Juan Peypouquet, and Patrick Redont. Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Mathematical Programming, 2018.
Peter Avitabile. Modal Testing: A Practitioner's Guide. John Wiley & Sons, 2017.
Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive Algorithms and Stochastic Approximations. Springer Science & Business Media, 2012.
Raphaël Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, and Adrien Taylor. A con- tinuized view on nesterov acceleration. arXiv preprint (02i::21220060 2021.
Michael Betancourt, Michael Jordan, and Ashia C Wilson. On symplectic optimization. arXiv 2018.
preprint
Petra Csomós and István Faragó. Error analysis of the numerical solution of split differential equations. Mathematical and Computer Modelling, 2008.
Sándor Csörgö and László Hatvani. Stability properties of solutions of linear second order differential equations with random coefficients. Journal of Differential Equations, 2010.
Jelena Diakonikolas and Lorenzo Orecchia. The approximate duality gap technique: A unified theory of first-order methods. SIAM Journal Optimization, 2019.
Thinh T Doan, Lam M Nguyen, Nhan H Pham, and Justin Romberg. Convergence rates of ac- celerated markov gradient descent with applications in reinforcement learning. arXiv preprint arXiv:2002.0288 02873, 2020a.
10

---

Published as a conference paper at ICLR 2022
Thinh T Doan, Lam M Nguyen, Nhan H. Pham, and Justin Romberg. Finite-time analysis of stochastic gradient descent under markov randomness. arXiv preprint arXiv:2003. 2020b.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 2011.
John Duchi, Alekh Agarwal, Mikael Johansson, and Michael Jordan. Ergodic mirror descent.
SIAM Journal on Optimization, 2012.
István Faragó, Âgnes Havasi, and R. Horvath. On the order of operator splitting methods for time- dependent linear systems of differential equations. International Journal of Numerical Analysis and Modeling, 01 2011.
Gabriel Goh. Why momentum really works. Distill, 2017. doi: 10.23915/dissil..000 URL http://distill pub/2011 m
Ernst Hairer, Christian Lubich, and Gerhard Wanner. Geometric Numerical Integration: Structure- Preserving Algorithms for Ordinary Differential Equations. Springer Science Business Media, 2006.
Aristide Halanay. Stability Theory, chapter I, pp. 13-130. Elsevier, 1966.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Lecture 6a: Overview of mini-batch gradient descent. Neural Networks for Machine Learning, 2012.
Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-iid data quagmire of decentralized machine learning. International Conference on Machine Learning. 2020.
Arieh Iserles. Euler's Method and Beyond, chapter 1, pp. 3-18. Cambridge University Press, edition, 2008
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference Learning Representations, 2014.
Nikola B Kovachki and Andrew M Stuart. Analysis of momentum methods. arXiv preprint arXiv:1906.04280 2019.
Nikola B Kovachki and Andrew M Stuart. Continuous time analysis of momentum methods. Journal of Machine Learning Research, 2021.
Harold Kushner and George G Yin. Stochastic Approximation and Recursive Algorithms and Applications. Springer Science Business Media, 2003.
Vitaly Kuznetsov and Mehryar Mohri. Generalization bounds for time series prediction with non- stationary processes. International Conference Algorithmic Learning Theory, 2014.
Qianxiao Li, Cheng Tai, and E Weinan. Stochastic modified equations and adaptive stochastic gradient algorithms. International Conference on Machine Learning, 2017.
Michael Muehlebach and Michael Jordan. A dynamical systems perspective nesterov acceleration. International Conference on Machine Learning, 2019.
Michael Muchlebach and Michael Jordan. Optimization with momentum: Dynamical, control- theoretic, and symplectic perspectives. Journal of Machine Learning Research, 2021.
W. W. Mumford. Some notes on the history of parametric transducers. Proceedings of the Institute of Radio Engineers, 1960.
Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms. Neural Information Processing Systems, 2020.
Yurii Nesterov. A method for solving the convex programming problem with convergence rate o(1 ((1/k2). Proceedings of the USSR Academy of Sciences, 1983.
11

---

Published as a conference paper at ICLR 2022
Yurii Nesterov. Introductory Lectures Convex Optimization: A Basic Course. Kluwer Academic Publishers, Norwell, 2004.
Boris Polyak. Some methods of speeding up the convergence of iteration methods. USSR Computa- tional Mathematics and Mathematical Physics, 1964.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Random averages, combinatorial parameters, and learnability. Neural Information Processing Systems, 2010.
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathemati- cal Statistics, 1951.
Damien Scieur, Vincent Roulet, Francis Bach, and Alexandre d' Aspremont. Integration methods and optimization algorithms. Neural Information Processing Systems, 2017.
Bin Shi, Simon S Du, Weijie Su, and Michael Jordan. Acceleration via symplectic discretization of high-resolution differential equations. arXiv preprint arXiv: 1rXiv:1922.03694 2019.
Jonathan W Siegel. Accelerated first-order methods: Differential equations and Σyaрunov functions. 2019.
arXiv preprint
Umut Simsekli, Lingjiong Zhu, Yee Whye Teh, and Mert Gurbuzbalaban, Fractional underdamped langevin dynamics: Retargeting sgd with momentum under heavy-tailed gradient noise. Interna- tional Conference on Machine Learning, 2020.
Weijie Su, Stephen Boyd, and Emmanuel Candes. A differential equation for modeling nesterov's ss accelerated gradient method: Theory and insights. Neural Information Processing Systems, 2014.
Tao Sun, Yuejiao Sun, and Wotao Yin. On markov chain gradient descent. Neural Information Processing Systems, 2018.
Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. International Conference on Machine Learning, 2013.
Richard S Sutton and Andrew G Barto. Reinforcement Learning: An Introduction. MIT press, 2018.
Andre Wibisono, Ashia C Wilson, and Michael I Jordan. A variational perspective on accelerated methods optimization. Proceedings of the National Academy of Sciences, 2016.
Ashia Wilson, Benjamin Recht, and Michael I Jordan, A Iyapumov analysis momentum methods in optimization. arXiv preprint 1611 1.06635, 2016.
Huaqing Xiong, Tengyu Xu, Yingbin Liang, and Wei Zhang, Non-asymptotic convergence of adam-type reinforcement learning algorithms under markovian sampling. arXiv preprint 2622:22002.06286. 2020.
Jingzhao Zhang, Aryan Mokhtari, Suvrit Sra, and Ali Jadbabaie. Direct runge-kutta discretization achieves acceleration. Neural Information Processing Systems, 2018.
12

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 A PROCHDURE TO NUMERICALLY DETERMINE SYSTEM STABILITY
As reminder, we consider online linear least squares regression using SGDm with fixed 1). H under a periodic covariate shift. Data is sampled from the sequence of random variables {Xx, Y& heeN where Xg is normally distributed and shifts periodically in expectation. Yx is an unchanging linear function of Xx with zero-mean observation noise. For ease of exposition we consider the one dimensional regression problem with X3 E R and Y& F. however the theory applies to any learning system representable as an LTV ODE satisfying the assumptions required for Theorem !
Here we expand on the example given at the end of Section 3
Under this covaiate shift, 3y varies sinusoidally in I-a, a] with period T J. Note that although X is periodic in expectation it admits a stationary distribution. The full specification of the data generating process is as follows
X ~ N(xx. 1)
Fx = a (20(22
Y2 0ixx + 02 +
c~ 1((
where 0" =-=100 =0% 00] are the target weights.
We consider squared error loss function,
[==;0) = (ú - y))
[(0, x) -110" xx) + e)]
[(010 02) ~07,0 + 02 + +c]
Hence, taking gradients at time ls w.r.t. On we have
2x [0k, Tx + 0k2) (0% 2k + 07 e)]
Vo, (x))
2[(0,, IK + 0k2) (0% 2R 0 t)]
Taking expected gradients,
LE [[2 + -x
(0; +0
07
EE v Lizii 0w)
E Jh + 0k2, (0t,
0% +]]]
[2((k. (1 + x2) + -
(0%
4 + 0 3x + [x]]
21(0,, 2x + 0/2) (0), Tg. 0% + [()
[Om, (1 + x2) + + - (6%, (1+ 5
8% kk)
(0k, + 0k2) -07, 36 (
0k, (1 + x4) 0 (1 + x2) + 0k Fk
0 3
0k 0f 3k 0k2
0
(1
1k 0
k
I
1
Okg 0%
In the notation of Proposition 1 we can write this as
(Oa) = Bx(0x - 0-1T
with
Bs =
(1 + x2)
TA
It
If we let =(() = a cos(22)))) (2 +1), then we induce an X(1) from which {Xx} is sampled, as per
Section A.4.3 This results in By B( with the matrix-valued function B())
B(1) = 2 (1 + x(1)) a(t)
a(t)
13

---

Published as a conference paper at ICLR 2022
From Proposition| 2 we have that our learning system numerically integrates LTV of the form
0(1) + 1 1 0(1) + (())(((t) 0*) with (0(1) 0*) 0 (t) (t) (2 02 (1)
(5)
Note that (() piecewise continuous and periodic with period 7
This second order ODE can be represented as system of first order ODEs with the transformation
{ 01 0
2 = 02 02
{3 = 01
f 02
so that the equation equation 5
can be written in standard first order linear form & = A(t)::
0
{
0
0
0
1
&
E3 -2(1 + (t))
2z
n-1
0
E3
(6)
2tt(t)
-2
#-1
[
VT
The matrix (t)) is piecewise continuous and periodic, which implies the matrix A(t) also shares these properties. The ODE equation 5 satisfies all the assumptions needed make use of Theorem to determine the stability of solution trajectories. We can obtain a fundamental solution matrix, (b((). of equation 6 satisfying initial conditions (0) = T4x4 by numerical computation through the use of an ODE solver.
Once we have this matrix (t), we evaluate it at time = J to obtain the system's monodromy matrix. Now we only need to determine the spectral radius, p. of (T") to determine the stability of solution trajectories for the system. Details regarding why this true are given in the proof of Theorem
We repeat this process, sweeping over values of μ., 1,, and determine the stability of solution trajectories for systems to triples of fixed values for these hyperparameters. The results of this process are given in Figure 6 below.
A.2 REDUCING RESONANT RESPONSES
In experiments 4.1 and 4.2 we see that as the momentum parameter is reduced, the tendency to resonate is mitigated. This aligns with theoretical predictions, which (in the context of those particular experiments) suggest that sufficiently low y makes SGDm convergent across all frequencies in the band we evaluate. Intuitively, this aligns with the role plays in the ODE, as it appears in the following coefficient on the first order derivative of system equation (i.e. the system's 'damping" coefficient), repeated below with the damping coefficient a explicitly Tabelled:
((t) + at( + ((t) 8*) =
When a O, the system has damping (i.e. friction zero, in the physical analogue) so resonant responses are maximized. As increases, damping increases, and resonant responses are reduced. There two ways increase reduce y reduce r/.
A.2.1 REDUCING THE MOMENTUM PARAMETER
Figure ( shows the thcoretical heatmap across all possible momentum values, and across much wider band of frequencies, which suggests a trend: setting to a sufficiently low value will completely mitigate resonance, though setting y too low will worsen convergence rate. For now, will set aside the observation that too low worsens convergence rate, and we will now show that reducing μ will reliably dampen resonance across all other experiments.
In 4.5 ADAM's parameter 31 was varied, and we see that reducing 31 decreases the tendency to resonate. Since 3r is the nearest parameter f in SGDm, the desired trend has already been
14

---

Published as a conference paper at ICLR 2022
1.00
1.45
1.00
1.25
0.99
0.75
1.00
4
0
0
0.97
0.4
0.50
0.25
0.96
0.25
0.95
0.00
0.00
int 177
89
60
45
36
30
26
22
20
inf
41
20
10
7
5
Cov. shift period T
Cov. shift period T
(a) Spectral radius heatmap, 17 = 0.01
(b) Spectral radius heatmap, wide range, = 0.01
1.0
1.00
1.00
1.45
1.25
0.99
0.75
1.00
4
p
0
0.4
0.50
0.2
0.25
0.0
0.00
inf 177
60
45
36
30
26
22
Inf
41
Cov. shift period T
20
14
10
7
5
Cov. shift period T
(d) Spectral radius heatmap, wide range,
(c) Spectral radius heatmap, = 0.005
0.005
1.0
1.00
1.25
0.75
1.00
4
P
p
0.97
0.50
0.25
0.96
0.25
0.2
0.95
0.00
0.0
0.00
inf
30 Cov. shift period
36
Inf
41
20
14
10
7
5
Cov. shift period
(c) Spectral radius heatmap. 0.001
(f) Spectral radius heatmap, wide range, v 0.001
Figure 6: Spectral radii of the monodromy matrices induced by particular momentum μ and period T values (x and y pixel coordinates, respectively). Step-size 7) decreasing with each row. Each column shares the same range of μ., T. The right column shows the full range of momentum fa [0, and much wider range of periods than the left. The left column figures simply 'zoom in to the upper left corner of the figure to its right. aa corresponds to the μt, 17, T as Experiments 4.1 and 4.2 with contour lines identical to 2a 2b such that the white line separates the convergent region below from the divergent regions above. (b), with the extent of (a) indicated by dotted lines. The figures in the right column show horizontal band of minimum spectral radius (i.e. max convergence rate), which suggests that there exists least-resonating Abeu across nearly all frequencies, with only minor deviations toward the far left, where data approaches iid. Though the location of jhest clearly changes with step-size y) and likely depends upon other aspects specific learning problem.
15

---

Published as a conference paper at ICLR 2022
1.0
10a
J =
||0-0~|1
||0-0~||
0.925
0.9
0.6
Jl 0.875
10a
J 0.875
M 0.85
== 0.85
0.4
0.2
10a
20
40
60
80
100
120
Mean period T
Mean shift interval
(a) Regression w/ periodic 2x. samples per X
(b) Regression w/ stochastic Fx. 0.4 Fy variance
10a
= 0.95
0.6
== 0.95
||0-0*||
I 0.925
J - 0.925
0,9
== 0.9
10a
EnL
# - 0.875
0.85
==
10A
10a
0.0
0
10
20
30
40
50
20
40
60
80
100
Mean shift interval T
Mean shift interval T
(c) Regression w/ stochastic Jy.,
9
(d) Neural net w/ stochastic 2x. Ft. variance 0.4
Figure 7: Re-running with reduced momentum values for highest resonance configurations chosen from Experiments 4.3
(6) c) an6 (d). In all cases, reducing momentum significantly dampens resonant response, with μ 0.85 completely mitigating resonant response.
4.4
demonstrated. For the remainder of this section, we show the resonance-damping behaviour of
in the remaining experiments: 4.3 4.4, and 4.6 particular, from each experiment choose the configuration which had the highest tendency to resonate, and we modify the experiment by running them with several decreasing values momentum μ. See Figure for results. In Section [ these experiments used momentum μ 0.95, and here run with μ E [0885, 0.95), with all other experimental parameters identical.
A.2.2 REDUCING THE STEP-SIZE
Another way to reduce tendency to resonate is suggested by the damping coefficient equation 7
reducing step-size 7j. Here we repeat Experiments 4.1 and 4.2 including smaller step-sizes 1) empirically demonstrate that trend. Specifically, Figure 8 shows the resonance heatmap and spectral radius contour lines for regression in two weights with covariate shift, identically Experiments 4. 4.2 The left column shows sinusoidal covariate shift, and the right column the AR(2) covariate shift. Each row corresponds diverging regions are significantly reduced in size as step-size is decreased, with a narrower band of frequencies diverging, and minimum momentum j required for resonance increasing towards This trend is reflected in both the empirical heatmap results, as well as the theoretically predicted spectral radius contour lines.
fixed step-size 17 {0.01, 0.005, 0.001), and is clear that resonant,
A.3 EXPERIMENTS AND WITH STOCHASTIC GRADIENTS
Experiment serves as a simple setting, as close to the theory of Section 3 as possible. In
particular, each descent step made at time uses the gradients induced by 20 samples from each X,. so that the gradient signal is much closer to the expected gradient than the stochastic setting. Experiment 4.2 uses the same technique.
16

---

Published as a conference paper at ICLR 2022
0.99
0.99
0.96
0.96
0.95 inf
0.95
180
60
30
22
180
90
45
20
Cov. shift period
Peak freq. period
(a) Resonance regions, sinusoidal Zx. 1) 0.01
(b) Resonance regions, AR(2) zt. 1/ 0.01
0.99
0.99
μ4
μ
0.97
0.97
0.96
0.96
0.95 Inf
0.95
180
90
60
45
36
30
26
22
20
inf
180
90
60
45
36 30
26
22
20
Cov. shift period T
Peak freq. period T
(c) Resonance regions, sinusoidal 5x, 17 0.005
(d) Resonance regions, AR(2) Fs. 17 0.005
0.99
0.99
H
0.97
0.97
0.96
0.96
0.95
0.95
Inf
180
90
60
36
30
22
20
Inf
180
90
45
36
26
20
Cov. shift period
Peak freq. period
(c) Resonance regions, sinusoidal Fs. 17 = 0.001
(f) Resonance regions, AR(2) 5e. 77 = 0.001
Figure 8: Re-running with reduced step-size for Experiments 4.1 cases, reducing step-size significantly dampens resonant response.
and 4.2 In both
17

---

Published as a conference paper at ICLR 2022
0.99
0.99
0.97
0.97
0.96
0.96
0.95
0.95
Inf
180
90
60
45
36
30
26
22
20
inf
180
90
60
45
36
30
26
22
20
Cov. shift period T
Peak freq. period T
(a) Resonance regions, sinusoidal Σg.
0.01
(b) Resonance regions, AR(2) ãt, 17 0.01
0.99
0.99
0.97
0.97
0.96
0.96
0.95
0.95
Inf
180
90
60
36
30
22
20
Inf
180
90
45 30 26
22
20
Cov. shift period T
Peak freq. period T
(c) Resonance regions, sinusoidal Fx. 1j = 0.005
(d) Resonance regions, AR(2) Tt. 17 = 0.005
0.99
0.99
0.97
0.97
0.96
0.96
0.95
inf 180
60 45
36
30
26
22
20
inf
180
90
60
45
36
26 22 20
Cov. shift period
Peak freq. period
Resonance regions, sinusoidal 1) 0.001
(f) Resonance regions, AR(2) 24. 7/ 0.001
Figure 9: Re-running with fully stochastic gradients for Experiments all cases, increasing gradient variance significantly dampens resonant response, but does change it otherwise.
and
In
Here we repeat Experiments 4.1 and 4.2 but drawing only single sample from each Xx. so that the gradient signal is fully stochastic. That is, we significantly increase gradient signal's variance. As Figure 9 shows, the resonant response is significantly damped by increasing gradient signal variance. We observe no other change in the empirical heatmap: regions of instability are neither introduced removed, and the existing regions do not change shape location. Only the size of instability regions is affected, which most apparent under comparison to Figure g where the empirically observed instability regions expanded to closer match the theoretical predictions derived from expected gradients.
Also the bright band of instability in all subfigures of Figure are are wider than those of This aligns with intuition from the conventional setting with iid data, where increasing gradient variance reduces optimizer stability.
18

---

Published as a conference paper at ICLR 2022
A.4 PROOFS
A.4.1 ADDITIONAL NOTATION
Wherever we write the training input generating process {X&). it implicit that the last dimension is fixed at one wishes to describe linear models with bias term. In this way, the notation (0, Xx) accommodates linear models with without a bias term.
We use ç to denote the phase space coordinates of weights 0, meaning &
where vectors
0,0 0 I2d are stacked so that the resulting & E I2d We denote the d-dimensional zero vector as Oa- For an ODE system E(t) f(((t). t) with arbitrary solution trajectory E(t) approximated by sequence of iterates {, we denote the integration time step h, and the numerical flow as &h, which is the map such that fk+1 = (fxx(Ex). We denote the k-th discrete timestep as 4. which we always use to refer to the k-th multiple of integration time step h, i.e. is- hkk
Similar to the main body, when function of time O(t) approximated by a discrete time sequence (0x}, they are denoted with the same symbol, and distinguished by parenthetical argument t and subscript k, respectively. At the risk of abusing notation, we will adhere to this convention and use {d+} to be a discrete sequence approximating the function time (()), which refers to the time derivative of (t). This means the symbol 0g is the k-th iterate of a sequence approximating @(t).
We now restate Assumptions, Propositions, and the Theorem from Section providing complete proofs.
A.4.2 LINEAR TIME- VARYING EXPECTED GRADIENT VIA COVARIATE SHIFT
Assumption 1. The covariate generating process {XalkeN not identically distributed: Corr(Xa: Xx,) + Corr(Xk,: Xky) ) for some ki, l:2 N.
Assumption The targets Yn are a fixed linear function of Xx with iid zero-mean observation noise, Eg such that E[Ex] = 0. That is, Y₁ =(0", (x) + EN where 0" E IRd is fixed for all k.
Proposition 1. Under Assumptions 1 2 a linear model with weights 0g making predictions Ys. (0g, X&) with mean squared error (MSE) objective will induce time-varying linear expected loss gradients gr((2, = (0x - ) for all E N, where Bg E Rddxd and Bk, 7 Bkg for some ki, k2-
Proof. We will show that the gradient of MSE loss Vo, L(2;0,) pectation will take the linear form Bg(0g= 0²). We start with gradient for arbitrary time step k
02) is random variable whose ex-
Vo, L(Z:0s) Vo. Vo, (Pr 22)
MSE def'n n
Vo, Xx) - Y2)
Px def'n n from Prop. I
VoLl(10e, Xa) - -00", (x) + {
Ya def'n n from Ass.
2
Ve. 8", ((,)) + +
(5))) distributivity
-2((0x 8", X1) + Vo, No, 110x 110x- -0", xxx + tcl
chain rule
=2((0+ 8", X4) (x)x3
=2(0s 8" X Xx + 2xx
19

---

Published as a conference paper at ICLR 2022
Taking expectation with respect distribution Pa:
9& (0x) p,, Vo, [(Z;0x)
g def n
= E,,, [2(0x - Xx)xx) x + Xx)
by equation
pE [00g 0" [x) + +2Ep Ep, [Xx)
E linear, eg indep.
2Ep, 1i0x - ,X)xx
E = 0
2EA Xx(0x 0-, Xxa
scalar and vector commute
2E [xx (Xx, Og - 07)
(s commutative
2E,, (Xx (0x- 0))
(3) matrix form
=2Ep, xx 0*)
matrix mult. associative
= Ba (0x 0²)
In the last step, we have defined the matrix Bg as twice the expected outer product of X with itself, which is precisely the autocorrelation matrix, and function of X₃ first moments follows.
B₁ = [X,, 1
2-2ooT((x X1))
(Cov(X,,, Xx) + [x (x+l")
So if there exists ki, k2 E such that the autocorrelation matrices differ
: Xx,) * Corr(Xk2, Xk.)
then BR, + Big Assumption Proooideerrrsssss the necessary k1, K2, the proposition is proved.
A.4.3 ODE CORRESPONDENCE
In Section of of the main body, we defined (()). Lipschitz continuous in I, such that BN = B( T))). If we assume that {Xx} are sampled at intervals of / from an underlying continuous-time stochastic process (t) for which Ep(e) (X())) and Cov(X (t), X (t)) are Lipschitz continuous in t, this naturally induces a unique Lipschitz continuous Btt). Note P(t) is the distribution at time f, and we can extend equation 2 as follows.
B(t) = 2Cov(X()), x()) - P1p Pp)
(8)
This means that {B&) is sampled from continuous B(t), with subsequent B₁ spaced //1 apart. In essence, step-size acts scaling constant, such that tne unit of is discrete steps of k. (Exact when vi
is integer.)
Proposition 2. The SGDm iterates {0x} numerically integrate the ODE system equation with integration step VT and first order consistency.
1- 1-1000 ((O)((()) 0*) ((t) +
VT
Proof. The proof proceeds two parts. First derive first order operator-spliting integrator for the ODE equation 3 then we show that it is equivalent to SGDm equation
(Part 1: Operator-Splitting Integrator)
Let & R + ad be the vector valued function time whose first elements are (t)), and last elements are (t):
(((() 0-
{(t)
(9)
O(t)
20

---

Published as a conference paper at ICLR 2022
Le. & is a phase space transformation allowing to rewrite ODE equation the form of equation which can then be split into sum of separate systems flu, f|l as follows
É(()
(((()).)
(10)
Oaxd -B(t))
Laxd 1- v Laxd]
É(t)
{(t)
Oaxd
Taxd Odxd]
0dxd B(t)
Odxd -
É(t) Odxd
E(t) +
E(t)
v Taxd]
É(() (E)))(()) + ((((((())))))
Let be an integration time step, 1/, (Sx) be the implicit Euler numerical flow of (()((()))) (E(
1 (Ex) = Ex + h (e fx+1)
Ex + h
Oaxd Oaxx
Iaxa Oaxd]
(11) (Sx)
(11)
Let 6/ (5x) be explicit Euler numerical flow of (E()))
* (Ex) = Ea + h (Sx,
Oaxd
Odxd
=Ek + h
B(t+)
1- laxd
EK
(12)
The composed flow
0 hh.k Pi.k
(13)
a sequentially split operator, which has splitting error order because equation 10 time-varying linear system (Faragó et al. (2011). The operators being composed, implicit and explicit Euler, are both order consistent with their respective systems (Iserles) 2008). The overall order of consistency of split operator is the minimum of splitting error, and the orders of the composed flows (Csomós & Faragó 2008). So we have that equation| 13 aaproximmatss equation I0 with order consistency.
(Part 2: SGDm Equivalency)
will now show that equation 13 equivalent to SGDm when integration timestep /TI, where 77 is the SGDm step-size. We start with the definition of Ex+1 as the numerical flow of Ex:
E (Ex)
c (Ex))
by equation L
Oaxd
Iaxd Oaxd]
Ph (Ex)
h (1 (EE))
subst'n n from equation
Oaxd
oh (.l (Ex)
Oaxd
Iaxa] Odxd]
Ex+1
def of Ex+1
Oaxd
Öx+t1
ob (Ex)
matrix mult.
Oa
Oaxd
Oaxd
[b++1
Ev +
B(xx)
1- Laxd v
Ex + h
0.
subst'n 'n from equation 12
0d
1)
[0++1
Ex (1xx)(Ox 0r)
matrix mult.
v'
Oxt1
Ex+1 = Eい + h
(Ox 0*)
-G 0n
simplification
10: 8"
Recalling that Ex
the above immediately provides the following two recurrence
8%
relations:
O 0% + (B(())) -0') 1 /n
act1 = 02 + h0
02
21

---

Published as a conference paper at ICLR 2022
Now let integration time step h be the square root of SGDm step-size, h /T, and define u Vr8kk Substituting h, Uk. we proceed via elementary algebra:
Uk++
Uk+1
Uk
vn -B((t)0xx 1-
Uk
Ok+1 02 + vn
VTI
vi
v
2k+1 = Uk + (B((t))(0 - 00) (1 pb0kk
Ok+1 = 0x: + uK+1
uk+1 22 (tx) -0") (1- p.
Uk+1 Wul - (tt))) - -0")
Note that Btta) = Bk, and that B3 defines the time-varying gradients induced by covariate shift and linear regression to linear target (Proposition] Tp. Hence, under those conditions, we have arrived at The proof is complete.
SGDm equation] T
The reader may observe that, given solution {(t) to the system {(t) A()) the proof above shows that the SGDm iterates {0r} are precisely a first order numerical approximation of the first
dimensions E(t) Tt( 6* but the remaining dimensions are approximated only up
((t)
scale factor v by iterates {ux However, this is not an issue. Solutions ((t) to the system equation 3 are embedded within the first d dimensions of {tt), so the remaining d dimensions and iterates [Ok] } do not affect the result.
A.4.4 PARAMETRIC RESONANCE FOR ODE CONVERGENCE AND DIVERGENCE
Theorem 1. When B()) is periodic such that Btt) B(t T), the spectral radius p of (T) characterizes the stability of solution trajectories of equation follows:
p >>1 = trivial solution 6(t) 8" unstable. All other solutions diverge as 0(t) + co exponentially with rate
p < O(t) - 0 exponentially with rate p.
trivial solution is asymptotically stable, all other solutions converge as
Proof. The proof of this theorem relies heavily on the well-established mathematics of Floquet theory and the stability result is contained in Theorem 1.9 and Theorem 1.10 of (Halanay 1966). Theorem 1.10 states that for system of differential equations of the form
É A(t)
A A(t)
(14)
where A(t) is piecewise continuous, the stability of the trivial solution ((t) = 0 is determined by the spectral radius of the system's monodromy matrix M defined below
M (T)
where (t) (())
(Monodromy Matrix)
Matrix-valued valued functions (t) are the system's fundamental solution matrix, and elementary existence results for linear systems allow one to choose (t) such that (0) I so that the monodromy matrix simplifies as
M e (O)
(T)
= (T)
M (TT)
Below we denote the spectral radius of (T) (and hence of M) as (First Order Linear Form, Stability via Floquet)
22

---

Published as a conference paper at ICLR 2022
Below show that equation 3 can be transformed to the form equation 14 with A(t) continuous such that trivial solution stability of equation 14 is equivalent to stability of the solution 8(t) = 8*
Let E(t) be the phase space transformation of (tt), similarly to the proof of Proposition 2
{(t) = [((1) 0"
0(t)
so that for each I, (()) E I2d and E(I) E RRad This means equation (restated below)
8(t) + 1 1 1" ((t) ((t) 8-)
is equivalent to the following first order linear form
Oaxd BBtt)
Iaxa 1- Laxd
E(t) (())(())
where A(T)
Since (t) is periodic and continuous, which is stronger than the requisite piecewise continuity. Since all other submatrices of A(t) are constant, we have that A(t) is also periodic and (piecewise) continuous. Now Theorem 1.10 in (Halanay 1966) immediately provides the following
p p>> = trivial solution {(1) is unstable. All other solutions diverge as E(1) - 0o exponentially with rate p.
p < 1 trivial solution is asymptotically stable, all other solutions converge {(t) 0 exponentially with rate
Since E(t) = T((t)= - 07. 01: ((1)
The trivial solution E(t) = is equivalent to 0(t) = l"
{tt) > 0 is equivalent to {(t) -> 8"
{tt) + oo is equivalent to 0(t) +
The theorem proved.
A.5
DETAILED DESCRIPTIONS OF EXPERIMENTS
Below we provide details of the experiments from section the main body. The tables below contain details about the data generating process, learning algorithm and optimizer, and hyperparameter choices.
introduce new data generating processes (X²} via their mean sequences } For those experiments, a sample trajectory is visualized for several values of the process' frequency tuning parameter, either T. In addition to the sample trajectory, the frequency content of each process is shown in two ways: the power spectral density (PSD) of {X²} } estimated via long sample trajectory, as well as the PSD of the underlying mean sequence { As one would expect from the sampling relationship between X5 and Tg. the PSD of (X&} is simply the PSD of (Tx with noise floor.
Experiments 4.1
Experiments
4.5
4.6
reuse the process from experiment 4.4 so the visual depiction is elided.
23

---

Published as a conference paper at ICLR 2022
A.5.1
EXPERIMENT 4.1 DETAILS
Samples X₃
Means Xx
10
Samples X
Moans &
PSD (dB/Hz)
2
M www
-10-
-20
-2
40
0.0
0.2
0.4
0.6
0.8
1.0
100
150
200
250
300
Freq. (Hz)
Training Step
Sinusoidal mean {Xt) frequency content for
(a) Sinusoidal mean (Xt} sample trajectory
0.01
f = 0.01
Samples X
Means
10
Samples X
Means &
PSD (dB/Hz)
0-
2
www
0-
- 20
-30
0.0
0.2
0.4
0.6
0.8
1.0
50
100
150
200
250
300
Freq. (Hz)
Training Step k
(d) Sinusoidal mean { frequency content for 0.03
(c) Sinusoidal mean {Xe} sample trajectory for
0.03
Samples X
Means &;
10
Samples X
Means &
PSD (dB/Hz)
2
Mw
-10-
0-
-30
-2
-40
0.2
0.6
1.0
50
100
150
200
250
300
Freq. (Hz)
Training Step
(f) Sinusoidal mean {X,) frequency content for
(e) Sinusoidal mean { sample trajectory for 0.05
f 0.05
Figure 10: Sample trajectories (left) and power spectral densities (right) for Experiment 4.1 (Table 2 for three values of frequency tuning parameter f. The signal is a sinusoid, so we observe a single frequency peak translated left right by f.
24

---

Published as a conference paper at ICLR 2022
Table 2: Details for linear regression sinusoidal covariate shift problem.
Sinusoid Mean Frequency
f E 0.05)
Covariate Shift Mean
Fg 0.5 f27
Input Sampling
Xx (( 1)
Ys X₁ + 62
Target Function (Fixed Vi:)
07, 02 Uniform(-1,11
Ya = Xx + 0n,2
0,,1, 0.. Uniform 11 1]
Model and Optimizer
(0x)KEN <- SGDm(1. 11)
7 0.01, μ E [0.95, 0.999]
k [0, 104]
25

---

Published as a conference paper at ICLR 2022
A.5.2
EXPERIMENT 4.2 DETAILS
Samples X₃
Means Xx
10
Samples X
Moans &
PSD (dB/Hz)
2
-10
-20
-2
-40
0.0
0.2
0.4
0.6
0.8
1.0
100
150
200
250
300
Freq. (Hz)
Training Step
(b) AR(2) mean (Xt) frequency content for
(a) AR(2) mean [Xx] sample trajectory f
0.01
0.01
Samples X Means
10
Samples X
Means &
PSD (dB/Hz)
0-
2
0-
20
-30
0.0
0.2
0.4
0.6
0.8
1.0
50
100
150
200
250
300
Freq. (Hz)
Training Step k
(d) AR(2) mean {Xt} frequency content for f = 0.03
(c) AR(2) mean { sample trajectory for f
0.03
Samples X
Means &₁
10
Samples X
Means &
PSD (dB/Hz)
2
-10-
0
30--
-2
-40
0.2
0.6
1.0
50
100
150
200
250
300
Freq. (Hz)
Training Step
(f) AR(2) mean {Xx) frequency content for 0.05
(e) AR(2) mean {Xx) sample trajectory for f
0.05
Figure 11: Sample trajectories (left) and power spectral densities (right) for Experiment 4.2 (Table
3) for three values of frequency tuning parameter f. The signal a AR(2) process designed for single frequency peak, as observed. The process is stochastic, its frequency peak is widened by the imperfect correlation.
26

---

Published as a conference paper at ICLR 2022
Table 3: Details for linear regression sinusoidal covariate shift problem. Rather than choosing frequency and using it directly as Table 2 we use f together with the stationary distribution variance 0.1 to compute AR(2) coefficients Φ1, 02
Expected Dominant Freq. in ã
f E 0.05
Stationary Dist. (Fixed Vf)
P N'0 0.1)
Ig Φ1šk-1 Φ2 EN
& NO 10 5)
iid
31, T2 ~ P
Covariate Shift Mean
4dz
Φ
Φ cos(2 f)
Φ2 s.t. [ ãh-1 P|~ P
Remaining Parameters
XR, Yr, Vo, 0" 00, (0x (W))EN, tb p, same Table
27

---

Published as a conference paper at ICLR 2022
A.5.3
EXPERIMENT 4.3 DETAILS
Samples Xx
Samples X
Means Xx
Means &
PSD (dB/Hz)
10-
2
-10
Mar yww
-0
-2
40
0.0
0.2
0.6 Freq. (Hz)
0.8
1.0
100
150
200
250
300
Training Step
Periodic
(Xt) frequency content for
(a) Periodic mean {Xt} sample trajectory
T
50
Samples X
Samples X
Means
Means &
PSD (dB/Hz)
10
2-
0-
10
www mmw
-30
440
50
100
150
200
250
300
0.0
0.2
Freq. (Hz)
0.4
0.6
0.8
1.0
Training Step k
(d) Periodic mean {X+} frequency content for
(c) Periodic mean {Xx} sample trajectory for T
T = 100
100
Samples X
Samples X
Means &₁
Means &
PSD (dB/Hz)
10
2-
0-
0-
-20
-2
1.0
50
100
150
200
250
300
Freq. (Hz)
Training Step
(f) Periodic mean {Xa) frequency content for T 150
(e) Periodic mean } sample trajectory for T 150
Figure 12: Sample trajectories (left) and power spectral densities (right) for Experiment 4.3 (Table 4 for three values frequency tuning parameter T. The signal is a square wave in a single dimension for the figure, but is square wave randomly oriented in higher dimensions for the actual experiment. There are multiple frequency peaks, with the frequency domain contracted by changing T.
28

---

Published as a conference paper at ICLR 2022
Table 4: Details for linear regression square wave covariate shift problem.
Square Wave Mean Period
T E [0. 120
Input Dimensionality
d =
2k
mod
Fk
2
T
Covariate Shift Mean
if mod
2
E~ (O, Idxa) iid
Input Sampling
X2 (ãx, 0.25l
(0 Xa) + f241 EK 0r ~ NO0, cla+1xa+1) where c 0.25
Target Function (fixed for all k))
E A(O,0.1)
Y (0/1:)) Xx) + 04+1
0g ~ ((ox where 0.25 0.01, μ 0.95
Model and Optimizer
(Ox)REN < SGDm(1).))
k 10*
29

---

Published as a conference paper at ICLR 2022
A.5.4 EXPERIMENT 4.4 DETAILS
Table 5: Details for linear regression problem with stochastically switching covariate shift mean.
Mean Switching Interval
T [0,
Mean Switching Variance
0.25 for Figure 4b
[0, 0.44 for Figure 4a
Input Dimensionality
[1. [1.9] for Figure 4b
5 for Figure 4a
IR a where
Covariate Shift Mean
T
& ~ (O, vlaxa) iid
Remaining Parameters
Xk. Yk, Yj, 0% Go [ON)NEN p4 k same as Table
30

---

Published as a conference paper at ICLR 2022
Samples Xx
Samples
Means K
Means
PSD (dB/Hz)
10
2-
20-
-30
-2
40
0.2
0.4
0.6
1.0
50
100
150
200
250
300
Freq. (Hz)
Training Step
(b) Switching mean (Xx) frequency content for
(a) Switching mean {Xe} sample trajectory for
T = 10
10
Samples X
Samples X
Means Rx
Means &
PSD (dB/Hz)
10
2
-10-
-00
-30
-2
40
0.0
0.2
0.4
0.6
0.8
1.0
200
250
300
Freq, (Hz)
Training Step
(d) Switching mean {Xx} frequency content
(c) Switching mean {Xx} sample trajectory for
T = 30
T 30
Samples
Samples X
Means Xx
Means R
PSD (dB/Hz)
2
0:
-10
0
-20
-30
-2
0
50
100
150
200
250
300
0.0
0.2
Freq. (Hz)
0.6
1.0
Training Step k
(f) Switching mean {X frequency content for T 50
(e) Switching mean {X+} sample trajectory for 50
T
Figure 13: Sample trajectories (left) and power spectral densities (right) for Experiments 4.4 4.6 (Tables for three values of frequency tuning parameter T. The mean signal is essentially white noise stretched' according to T.. The signal is a single dimension for the figure, but is of higher dimensions for the actual experiment. The frequency content vertical reflection Figure T2 (right,) with frequency troughs instead of peaks. Note that the frequency content is the mildest of all settings, having the lowest and least-defined peaks, which aligns with intuition: there is nothing even remotely oscillatory in its definition. It is reasonable to expect that many 'natural" processes would have more aggressive frequency content.
31

---

Published as a conference paper at ICLR 2022
A.5.5 EXPERIMENT 4.5 DETAILS
For visual depiction, see Figure
Table 6:
Details for linear regression problem with stochastically switching covariate shift, optimized with ADAM instead of SGDm.
Mean Switching Interval
7' E [0, 100]
Mean Switching Variance
1.0
Input Dimensionality
d
Covariate Shift Mean
Fg identical to Table
Input Sampling
Xς ~ (Tg,, 0.1
Target Function (fixed for all k)
YR, , identical to Table 5
Model
Yx, du identical to Table
(0x (fx)eN < ADAM( 81, 52)
Optimizer
= 0.01, 31 E [0.9, 0.99), B2 = 0.999
k E [0, 10
A.5.6 EXPERIMENT 4.6 DETAILSS
For visual depiction, see Figure 13
Table 7: Details for neural network regression problem with stochastically switching covariate shift.
Mean Switching Interval
T E [0, 100]
Mean Switching Variance
[0, 0.4]
Input Dimensionality
d 2
Covariate Shift Mean
3g identical Table |
Input Sampling
X₁ (w 0.1laxd)
Y4 cos(t||Xx|I) +
Target Function (fixed for all k)
Ek \(0,, 0.1)
Y, f(x;; 0w) two hidden layers of 20 activations
Model
0. initialized as He et. al.
(0))ee + SGDm(1, u) = 0.01, μr = 0.95
Optimizer
A: E [0, 2 x 10*]
32


Reviews:
[{"review_id": "fdo5MY055Gm", "reviewer": "Reviewer_6uKo", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths, weaknesses, and comments\n\n1. 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.\n\n2. 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). \n\n3. 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.\n\n4. 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\"?\n\n5. 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.\n\n6. 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?\n\nMinor comments/questions\n\n7. 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.\n\n8. 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.\n\n9. 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?\n\n10. 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))?\n\n11. Proof sketch of Theorem 1: what is $g(t, \\theta(t))$?\n\n12. Pages 20 & 21: In the recurrence relations for $\\dot \\theta$ and $v$, $\\theta_k$'s should instead be $\\theta_k - \\theta^*$?\n", "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.\n\nThe 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.\n", "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).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TysxODi0SIi", "reviewer": "Reviewer_Z17i", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nI 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.\n\nI'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_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.\nIn 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.\nThe 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.\n", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "C8lJCnsuOxX", "reviewer": "Reviewer_Vijg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nYet 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?\n\nMy 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.   \nGrowing 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.\n\nSome minor issues:\n- 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.\n- Why is it necessary to assume in setting 4.2 that \\phi_1 itself oscillates; the ARMA process already implements an oscillation?\n- May be good to combine Fig. 3 & 4 just for layout.\n- 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?\n- 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_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).", "summary_of_the_review": "Great and thorough paper, but empirical example that clearly demonstrates relevance would be appreciated.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5HCIZdOkSDr", "reviewer": "Reviewer_Vbeb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n\n1. 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.\n\n2. 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. \n\n3. 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_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. \n\nBeside 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. ", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

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)