From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression
Authors: Xuxing Chen
Krishna Balasubramanian
Promit Ghosal
Bhavya Kumar Agrawalla
Venue: Accepted by TMLR ()

Abstract: We conduct a comprehensive investigation into the dynamics of gradient descent using large-order constant step-sizes in the context of quadratic regression models. Within this framework, we reveal that the dynamics can be encapsulated by a specific cubic map, naturally parameterized by the step-size. Through a fine-grained bifurcation analysis concerning the step-size parameter, we delineate five distinct training phases: (1) monotonic, (2) catapult, (3) periodic, (4) chaotic, and (5) divergent, precisely demarcating the boundaries of each phase. As illustrations, we provide examples involving phase retrieval and two-layer neural networks employing quadratic activation functions and constant outer-layers, utilizing orthogonal training data. Our simulations indicate that these five phases also manifest with generic non-orthogonal data. We also empirically investigate the generalization performance when training in the various non-monotonic (and non-divergent) phases. In particular, we observe that performing an ergodic trajectory averaging stabilizes the test error in non-monotonic (and non-divergent) phases.

Published in Transactions on Machine Learning Research (04/2024)
From Stability to Chaos: Analyzing Gradient Descent Dy- namics in Quadratic Regression
Xuxing Chen
zwachen@radavis.comm edu
Deportment of Mathematics University of California, Davis.
Krishnakumar Balasubramanian
Sbalo@uucdavis edu
Department of Statistics University of California, Davis.
Promit Ghosal
promit@brandeis.cmmmm edu
Department of Mathematics
Brandeis University.
Bhavya Agrawalla
bhanyo @mit edu
Department of Mathematics
Massachusells Institute of Technology.
Reviewed on OpenReview: https: // openrevie.. net/ forum? id= W5klo5VpG7
Abstract
We conduct comprehensive investigation into the dynamics of gradient descent using large- order constant step-sizes in the context of quadratic regression models. Within this frame- work, we reveal that the dynamics can be encapsulated by a specific cubic map, naturally parameterized by the step-size. Through a fine-grained bifurcation analysis concerning the step-size parameter, we delineate five distinct training phases: (1) monotonic, (2) generalized catapult, (3) periodic, (4) chaotic, and (5) divergent, precisely demarcating the boundaries provide examples involving phase retrieval and two- layer neural networks employing quadratic activation functions and constant outer-layers, utilizing orthogonal training data. Our simulations indicate that these five phases also man- ifest with generic non-orthogonal data. We also empirically investigate the generalization performance when training the various non-monotonic (and non-divergent) phases. In particular, we observe that performing an ergodic trajectory averaging stabilizes the test error in non-monotonic (and non-divergent) phases.
of each phase. As illustrations,
1 Introduction
Iterative algorithms like the gradient descent and its stochastic variants are widely used to train deep neural networks. For a given step-size (or learning rate) parameter 7 > O, the gradient descent algorithm of the form [+++) (t) ()((((()) where the training objective function being minimized, which depends the loss function and the neural network architecture and the dataset. Classical optimization theory think of the gradient descent algorithm discretization of so-called gradient flow equation given by ni(t) VV((((()) ), which could be obtained from the gradient descent algorithm by letting + 0. Additionally, assuming that the objective function has gradients that are T-Lipschitz, selecting a step-size < 1/L. guarantees convergence to stationarity.
operates under small-order step-sizes. In this regime,
In stark contrast traditional optimization, recent empirical studics in deep learning have revealed that training deep neural networks with largo-order step-sizes yields superior generalization performance. Unlike the scenario with small step-sizes, where gradient descent dynamics follow monotonic pattern, larger step-

---

Published in Transactions on Machine Learning Research (04/2024)
sizes introduce more intricate behavior. Various patterns like catapult, (also related to edge of stability); periodicity and chaotic dynamics in neural network training with large step-sizes have been observed em- pirically, for example, by Lewkowycz et al. (2020), Jastrzebski et al. (2020), Cohen et al. (2021), Lobacheva ct al. 20211, Gilmer ct al. (2022) : Zhang et al. (2022). Kodryan et al. (2022). Herrmann et al. (2022). A recent work by Sohl-Dickstein (2024) also empirically observe that the boundary between stable and diver-
gent training behaviour, in terms of hyperparameters (including the step-size parameter), exhibits a fractal structure. Furthermore, the necessity for step-size schedules to include large-order step-sizes expedite convergence and the ensuing chaotic behavior has also been observed empirically outside the deep learning community by Van Den Doel & Ascher (012), much earlier.
Faster convergence of gradient descent with iteration-dependent step-size schedules that have specific patterns (including cyclic and fractal patterns) has been examined empirically by Lebedev & Finogenov [197]], Smith
(2017) Oymak (2021), J, Agarwal et al. (2021) Goujaud et al. (2022) and Grimmer (2023), with Altschuler &
Parrilo (2023) and Grimmer ct al. (2023) proving the state-of-the art remarkable results; see also Altschuler
& Parrilo (2023) Section 1.2) for historical overview. Notably, the stated faster convergence behavior of
gradient descent requires large order step-sizes, very much violating the classical case. More importantly,
the corresponding optimization trajectory, while being non-monotonic, exhibits intriguing patterns (Van
Den Doel & Ascher
2012).
Considering the aforementioned factors, gaining insight into the dynamics of gradient descent with large-order step-sizes emerges as a pivotal endeavor. A precise theoretical characterizing of the gradient descent dynamics in the large step-size regime for deep neural network, and other such non-convex models, is a formidably challenging problem. Existing findings (as detailed in Section 1.1] often rely strong assumptions, even when attempting to delineate a subset of the aforementioned patterns, and do not provide comprehensive account of the entire narrative underlying the training dynamics. Recent research, such as [Agarwala et al. (2023), Zhu et al. (2024). and Zhu et al. (2023b), has pivoted towards comprehending the dynamics of quadratic regression models based on a local analysis. These models offer a valuable testing ground due to their ability to provide tractable approximations for various machine learning models, including phase retrieval, matrix factorization, and two-layer neural networks, all of which exhibit unstable training dynamics. Despite their sceming simplicity, fino-grained understanding of their training dynamics is far from trivial. Building in this direction, the primary aim of our work is to attain a precise characterization of the training dynamics of gradient descent in quadratic models, thereby fostering a deeper comprehension of the diverse phases involved in the training process.
Contribution 1. We perform a fine-grained, global theoretical analysis of cubic-map- based dynam- ical system (see Equation 2.1j, and identify the precise boundaries of the following five phases: (i) monotonic, (ii) generalized catapult. (iii) periodic, (iv) Li-Yor chaotic, and (v) divergent. See Fig- ure for an illustration, and Definition aad Theorem 2.1 for formal results. We show in Theorem 3.2 and 3.3 that the dynamics of gradient descent for two non-convex statistical problems, namely phase retrieval and two-layer neural networks with constant outer layers and quadratic activation functions, with orthogonal training data is captured by the cubic-map-basee dynamical system. We provide empirical evidence of the presence of similar phases in training with non-orthogonal data.
We also empirically examine the effect of training models in the above-mentioned phases, in particular the non-monotonic ones, on the generalization error. Indeed, provable model-spocific statistical benefits
for training in catapult phase are studied in Lyu al. (2022) and Ahn al. (2022). Lim al. (2022)
proposed to induce controlled chaos in the training trajectory to obtain better generalization. Approaches
to explain generalization with chaotic behavior are examined in Chandramoorthy et al. (2022) based a
relaxed notion of statistical algorithmic stability. Although our focus is on gradient descent, related notions of generalization ion of stochastic gradient algorithms,, based on characterizing the fractal-like properties of the invariant measure they converge to (with larger-order constant step-size choices) have been explored, for example, in Birdal et al.] (2021). Camuto et al. (2021), Dupuis et al.] (2023), and Hodgkinson et al. (2022). Hence, we also conduct empirical investigations into the performance of generalization when training within the different non-monotonic (and non-divergent) phases and make the following contribution.
2

---

Published in Transactions on Machine Learning Research (04/2024)
14
1.4
32
3.0
2
1.0
64-
(a)
(b)
(c)
2270
2.016
3.0
1.5
(d)
(e)
Figure 1:
Phases of cubic-map based dynamical system in (2.1) parameterized by Sub-figure ((a) cor-
responds to the monotonic phases, where the dynamics monotonically decays to zero. Sub-figure l(b] corresponds to the generalized catapult phase where the dynamics decays to zero but is non mon-monot in a specific manner. Sub-figure [(c] corresponds to the periodic phase, where the dynamics decays and settles in period-2 orbit (i.e., shuttles between two points) but never decays to zero. Sub-figures [[d] and [(e)
correspond the chaotic phase (see Definition 1] and divergent phases, respectively. Note that the order of w-axis and y-axis in Sub-figures [(d) and (e) different. from the rest.
Contribution 2. We propose natural ergodic trajectory averaging based prediction mechanism (sce Section 4.2 to stabilize the predictions when operating in any non-monotonic (and non-divergent) phase.
1.1 Related works
General results. Lewkowycz et al. (202)) empirically examine the catapult phase particularly in neural networks with one hidden layer and lincar activations, the phase in which the linear approximation of the model becomes less informative. In this case, they observe that the loss does not have monotonie decrease but eventually converges when the curvature (maximum of the eigenvalue of the Neural Tangent Kernel (Jacot et al.) 2018)) stabilizes at a value less than 2/ 2/sste--size). Similar oscillations with convergence behavior have been also observed in Cohen et al. (2021) which empirically demonstrate that the sharpness (largest eigenvalue of the Hessian matrix the loss) in gradient descent on neural networks training hovers just above the value 2/sttp-sszze), indicating that gradient descent usually operates in the regime they call Edge of Stability (EoS). This is also formally studied in Ahn et al. (2022) Damian al. (2023) propose self-stabilization
phenomenological reason for the occurrence of catapults and EoS in gradient descent dynamics. Kreisler et al. (2023) investigate how gradient descent monotonically decreascs the sharpness of Gradient Flow solutions, specifically in one-dimensional deep neural networks. Although they do not formally prove the existence of chaos the dynamics, they conjecture its possibility. Arora et al.] (2022) and Lyu al. (2022) explore sharpness reduction flows, related the above findings. Andriushchenko et al. (2023) prove that large step-sizes in gradient descent can lead to the learning of sparse features. Wu et al. 2023 investigate the EoS phenomenon for logistic regression. Kong & Tao (0200) theoretically explore the
3

---

Published in Transactions on Machine Learning Research (04/2024)
chaotic dynamics (and related stochasticity) in gradient descent for minimizing multi-scale functions under additional assumptions. While being extremely insightful, their results are fairly qualitative and are not directly applicable to the cubic maps analyzed in our work. As we focus on specific models, our results are more precise and quantitative.
Specific Models. Zhuu et al. (2023)) and Chen & Bruna (2023) studied gradient descent dynamics for minimizing the functions f(u, v) = (u-o² - 1) and f(u)-
tu² 1)², respectively. Both works primarily focused on characterizing period-2 orbits and hint at the possibility of chaos without rigorous theoretical
justifications. Furthermore, their proofs are relatively ad-hoc and significantly different from ours. [Son & Yun (2024) provided empirical evidence of periodicity and chaos for training fully-connected neural network using gradient descent. However, their theoretical results are not applicable to quadratic regression models. Ahn et al. (2024) examined the Edge of Stability (EoS) between the monotonic and catapult phase for minimizing E(u, v) = I(wr), where is convex, even, and Lipschitz. Their analysis is not directly extendable to the quadratic regression models we consider in this work. See also the discussion below Theorem 2.1 for important technical comparisons. Wann et al. (2022) analyzed additional benefits (e.g., larning homogeneily) of gradient descent with large step-sizes for matrix factorization. Ziyin et al. (0222) also studied stochastic gradient descent with large step-sizes for the case when the loss function {(u) = au for a E R. Note in this case that the point 0 is the minimum when > O. However, when a < 0, the point 0 is a maximum. In this setup, Ziyin et al. (2022) precisely characterize the behaviour of SGD for converging to a minimum or a maximum, in terms of the step-size parameter, initialization and the noise distribution of the stochastic gradient.
Agarwala et al. 2023 explored gradient descent dynamics for class of quadratic regression models and identified the EoS. Zhu et al. (2023a also studied the catapult phase and EoS for a class of quadratic regression models. Agarwala & Dauphin (2023) examined the EoS in the context of Sharpness Aware Mini- mization for quadratic regression models. The above works are related to our work in terms of the model that they study. However, none of the above works characterize the five distinct phases (with precise boundarics) like we do, along with precise boundaries. Furthermore, our analysis is distinct (and is also global from the above works and is firmly grounded in the rich literature on dynamical systems.
Dynamical systems. Our results draw upon the rich literature available in the field of dynamical systems. We refer the interested reader to Alligodd et al. 1997 Lasota & Mackey (1998), Devaney (189 Ou 22002), and De Melo & Van Strien 2012)) for a book-level introduction. Birfurcation analysis of some classes of cubic maps has been studied, for example, by [kjooding et al. (1983). Rogers & Whitley (1983) Branner & Hubbard (1988) and MMinor 1992). Some of the above works are rather empirical, and the exact maps considered in the above works differ significantly from our case.
2 Analyzing a discrete dynamical system with cubic map
Notations and definitions. We say a sequence {r is increasing (decreasing), if 24+1 2 Ze (I2+1 S x1) for any f. Moreover, it is strictly increasing (decreasing) if the equalities never hold. For real-valued function f and a set S, define f(S) {f(z) x 5), and (z) == f(((k-1(xz) for any k E N+ with f()(x)) = z. The preimage of x under f on S is the set f=((z) (= {y E S: f() = =)). We say property P holds for almost every x E S or almost surely in S, if the subset far E 5 :property P does not hold for #} is Lebesgue measure zero. A critical point of f is a point x satisfying f'(x) = 0. We call To a period- k point of J, when (r)) = xo and (xo) * xo for any 0 S S k - 1. The orbit of a point xo denotes the sequence (f(*) (2o)) A point zo is called asymptotically periodic if there exists a periodic point to such that lim (2o) ((o) = 0. The stable set of a period-k point xp is defined W*(xo) := {x: lim (x) }
The stable set of the orbit of a periodic point To is the union of the stable sets of all points in the orbit of Z0- A point To is an aperiodic point if it is not an asymptotically periodic point and the orbit of vo is bounded. We say a fixed point Zy of f is stable if, for any é > O, there is a 8 > 0 such that for any x satislying [x zol < 6, we have (x)) - xol < for all n 2 0. The fixed point zo is said to be unstable
1 AAnalysis in Wang et al. 2022 and Chen Bruna 2023 also global, but not applicable our model.
4

---

Published in Transactions on Machine Learning Research (04/2024)
if it is not stable. The fixed point ze is asymptotically stable if it is stable and there is an 6 >> 0 such that -i (x)) = for all a satisfying - < 6. A period-p point zq and its associated periodic orbit are asymptotically stable if To is an asymptotically stable fixed point of f(v), A point To E R UU{+,, -oc is called an absorbing boundary point of S for f with period p, for some p E {1.2), if there exists an open set U S such that lim (y) + x for all y E.
We now introduce two quantities that are common in dynamical systems theory to study the stability properties. The Schwarzian derivative of three-times continuously differentiable function f is defined (at non-critical points) as
Sf(z) = (f)) - 1.5 (f"))) where f'(x #
It is widely used for its sign- preservation property under compositions; see, for example, De Melo & Van Strien (2012). Specifically, the stability of fixed point is related to the sign of the Schwarzian derivative at that point. Positive values may indicate instability, while negative values suggest stability. The Lyapunov exponent of a given orbit with initialization zo is defined as
Lf(ro) = lim 1 n-000
Σ log (z;)). 1=1
It is another related quantity associated with the stability properties of dynamical systems and is used to measure the sensitive dependence on imitial conditions (Strogatz 2018). Chaotic systems typically exhibit positive Lyapunov exponents, reflecting their sensitive dependence on initial conditions. Similarly, a negative Lyapunov exponent is characteristic of stable systems. Finally, we also define the sharpness a loss function is defined the maximum eigenvalue of the Hessian matrix of the loss.
Bifurcation analysis. Our main goal in this section is to undertake bifurcation analysis of the following discrete dynamics system defined by cubic map. For a > 0, first define the functions g and f, parameterized by a, as
(x(=) =² (a 2)z + 2a (= + a)(z - 2) +1 and fa(z) zga(z).
(2.1)
Next, consider the discrete dynamical system given by
2++1 = fa(z)) = (xt)
(2.2)
Note that for any a,e 0 and 20 2 + 20
e, will have lim |2el +00. Hence, we
only study the case when 2o E [[a,,2] 2]. We will show in Section that the dynamics of the training loss for several quadratic regression models could be captured by (2.2) The parameter a in (2.1] for the models will naturally correspond to the step-size of the gradient descent algorithm.
We next introduce the precise definitions of the five phase that arisc in the bifurcation analysis of (21). To do so, we need the following definition of chaos in the Li- Yorke sense (Li & Yorke 1975). Li-Yorke chaos is widely used in the study of dynamical systems and is also directly related to important measures of the complexity of dynamical systems, like the topological entropy (Adler et al. 1965 Franzová & Smital [991] We also refer to Aulbach & Kieninger (2001) and Kolyada (004)) for its relationship to other notions of chaos and related history.
Definition 1 (Li- Yorke Chaos Li & Yorke 1975 ). Suppose we are given a function f(x). If there exists
a compact interval such that f I, then it called LorYor chaotic (Li & Yorke 1975 Aulbach & Kieninger 2001) when it satisfies
For every k 1,2,... there is periodic point in I having period-k.
There is an uncountable set S C (containing no periodic points), which satisfies for any p, q E S with p + lim sup, (p) (() (g) > 0, lim inf (p) - (00()) 0, and for any E S and periodic
point e I, lim (p() - (()( >0. O.
To define the 5 phases in particular, we consider the orbit (f() generated by given function f defined over set T, in which the initial point belongs to.
5

---

Published in Transactions on Machine Learning Research (04/2024)
Bifurcation diagram
Lyapunov exponent
15-
01
10
05
-0.5
-1.0
-1.5
-4
-5
0.00
0.25
0.50
0.75
1.00
1.25
1.50
175
2.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
(a)
(b)
Figure 2: Bifurcation diagram and Lyapunov exponent. Initialization 20 = 0.1.
Definition 2. Given a function f(x) defined on a set I, we say the discrete dynamics is in the
Monotonic phase, when (z) is docrcasing and lim (f( (x) = 0 for almost every I.
Generalized catapult phase, when (()()) is not decreasing for any and lim ( (3))
0) for almost every E I. We say such sequences have catapults.
Periodic phase, when f is not Li-Yorke chaotic, (1)())
bounded and does not have a limit for
almost every I E I, and there exists period-2 points
Chaotic phase, when the function Li- Li-Yorke chaotic and (x)] is bounded for almost every
e I.
Divergent phasc when limn- (f (x)) too for almost every E
We emphasize here that our use of the word "phase" refers to the whole sequence (x)] and the calegorization is with respect to the different step-sizes. an illustration, Figure we plot the five phases for the parameterized function and its discrete dynamical system defined in (2.1 with initialization
1.9, ie., fa (xo), Hо = 1.9. We have the following main result for different phases of dynamics.
Theorem 2.1. Suppose fa(z) is defined in 2..1 Define z++1 = fa(z;) with zo sampled uniformly at random in 2). Then there exists a. E (1,2) such that the following holds.
Ifa (0,2/2 -), 2}, then almost surely lime Izel and [ is decreasing, and hence the dynamics is in the monotonic phose.
If (2v2- - 1], then almost surely lime | in the generolized catapult phase.
0 and |ze have calapulls, and hence the dynomics is
If a E <1,,a)), then there exists a period-2 point in (0, 1). 2 E (-a,2) 2) for all t. If there exists an asgmptotically stable periodic orbit, then the orbit of z0 is asymptotically periodic almost surely, and hence the dynamics is in the periodic phase.
Ifa E (a., 2), fa is Li- Yorke chaotic. 2t 2) for all there exists an asymptotically stable periodic orbit, then the orbit of is asymptotically periodic almost surely, and hence the dynamics is in the chaotic phase.
If to0), then lim |2a = +o0 almost surely, and hence the dynamics is in the divergent phase.
From a pure optimization perspective, Phase and are the most relevant, as training loss actually mini- mized. However, from generalization perspective, similar to other works (Lyu et al. 2022 Lim et al. 2022
Here, the term generalized to distinguish from Lewkowyez al. 2020 who consider the of single spike in the training loss. We do further sub-characterise divergent phase as it uninteresting.

---

Published in Transactions on Machine Learning Research (04/2024)
Chandramoorthy et al. 2022) we empirically observe that often times phases 2, 3 and 4 lead to comparatively improved generalization for various models.
Connections with sharpness and EoS. As we will see in Section 3 the training loss and sharpness of a special class of quadratic regression models can be written as functions of 2,, and hence their dynamics can be explicitly given by Theorem 2.1 As byproduct of our theory, we reveal that the EoS phenomenon happens in the catapult phase and quantify the limit that the sharpness eventually converges to, which matches the empirical observations in Cohen et al. (202]) and Ahn et al. (022)).
As direct application of Theorem 2.1 we have the following result. characterizing the dynamics generated by n different functions.
Corollary 1. Suppose fa(z) is defined in 2.1 and we are given 2n positive scalars 04 Pi for S i S n. Define 2, (I+1) fa.(2) L(z(), ΣE Pi(zi (0. Then for almost all 20) E {2 -a; S 21 S 2} we have
O < maxisicn at < 1, then lim (12 p) 0. Moreover, if < maxisisn at S 2v2 2, the sequence (T(2(0), p))_=0 is decreasing.
If < maxigign S 2, then (L(2(0, p) is bounded and does not converye to 0. If T/maxi > 2, then lim L(2(0), = to0.
We highlight here that even if we know from Theorem 2.1 the dynamics of each individual (0)) explicitly characterizing the phase of L(z(0, p) is not trivial. To see this, we provide one simple example as follows.
1 1 ) { 1, 2 2' " S2 = (s(")
{ 1 22 32" 42 f Ss = (S { 1
S1 : -=:= (
4'3'
where S3 is obtained by switching the (2i- 1)-th and 2i-th terms in ST. Sequences S₁ and S2 are decreasing to O, and S3 is in the catapult phase. We can verify that both +((") and (S/") + +.S(") are converging to 0 but the former is decreasing while the latter is in the generalized catapult phase. This implies that the summation of decreasing sequence and catapult sequence can be either decreasing or catapult, which makes analyzing the dynamics of the weighted summation L(*(t), p) non-obvious, As we will see in Section 3.1 the above result gives the training dynamics of gencralized phase retricval and a two-layer neural network with quadratic activation functions on n orthogonal data points.
In Figures ((a) and 2(b) we numerically plot a bifurcation diagram for a E (0, and Lyapunov exponent
scatter plot with initialization 20 0.1. The main ingredients in proving Theorem 2.1 are the following
Lemmas 2 and Note that by straightforward computations, we have
(0) = - 2a (-1,1) + a a (0,1).
This implies a asymptotically stable fixed point when a E (0. This type of local stability analysis is standard in dynamical systems literature (Hale & Koçak 2012 SSroggtzz 2018). and has been used in analyzing the training dynamics of gradient descent recently (Zhu et al. 2024 Song & Yun 2024 However, such results are limited to only local regions. In contrast, the following results provide a global convergence analysis.
Lemma 1. Suppose 0 < a S and -a -a S 20 S2. 2. Then we have
(i) -a S 2 S 2 for any 1, and Ja does not have a period-2 point on (-a, 2).
(1i) If 20 is chosen from [-a,2] 2] uniformly at random, then lim 2t = almost surely. Moreover, if 0 0<a= < 2/2-2, then almost surely [2141l S | for all t. 2f 2 < a < 2, then almost surely {(z()s has catapults.
a
Lemma Suppose < $ 2 and S 20 2. Then we have
(1) (i)-a a aassss for any t, and fa( has a period-2 point on [0, 1). (it) There exists a, (1,2) such that for any a E 2), fa is Li- Yorke chaotic, and for any E (1, al,)
Ja is not Li- Yorke chaotic.
7

---

Published in Transactions on Machine Learning Research (04/2024)
(Mii If there erists on asymptotically stable orbit and 2u is chosen from [-a, 2] uniformly at random, then the orbil. of is asymplotically periodic almost surely.
Lemma 3. Suppose 2. Zu is chosen from [-a, uniformly at random. Then lime-+oo |zel = +o0 almost surely.
In Lemma 2 part (iii); we assume the existence of an asymptotically stable periodic point. Note that such a point must have negative Lyapunov exponent (Strogatz 2018). It is possible to obtain particular values for a under which fa() has an asymptotically stable orbit. For example, a can be chosen such that I (g)) < 1, where p E (0, 1) is a period-2 point with fa(p) = q- In Figure 2(b) we plot the Lyapunov exponent of fa the orbit starting from 2p 0.1. It is interesting to explicitly characterize the set of a values in (1, 2) such that fa(=) has an asymplotically stable periodic orbit. Furthermore, we conjecture that
a, defined in Lemma 2 is the smallest number a (1, 2) such that (1 (1-24 22a)/3 is period-3 point. The above two problems are challenging and left as future work.
3 Applications to quadratic regression models
We now provide illustrative examples based on quadratic or sccond-order regression models, motivated by the works of Zhu et al.] (2024) and Agarwala et al. (2023). Specifically, we consider a generalized phase retrieval model and training bidden-layers of 2-layer neural networks with quadratic activation function as examples.
3.1 Example 1: Generalized phase retrieval
Single Data Point. Following Zhu et al. 2004), it instructive to study the dynamics with a single training sample. Consider the following optimization problem on a single data point (X,y):
min {E(w) 2 (9(w; -))} where g(u; X) w)) + c
(3.1)
2
where 7, e are arbitrary constants. The above model, with 7 = 2 and, = 0 corresponds to the classical phase retrieval model (also called as a single-index model with quadratic link function). We refer to Jaganathan ett al. 2016) and Fannjiang & Strohmer (2020) for an overview, importance and applications of the phase
retricval model. We would like to point out that the analysis of seemingly simple models is already non-
trivial and has been done in various ways. For example, single-data-point setting (Zhu et al. 2024 Song
& Yun. 2024), simple-model setting (Lobacheva et al.) [022] Ahn al., 2024 Kodryan al., 2022 Zhu
ct al.) 2023b Chen & Bruna 2023 Zhu ct al. 2023a), etc. Different from cxisting works that mostly focus
asymplotic or local analysis that only hold when certain quantities are sulficiently large small (small
step-sizes (Lobacheva et al.) 2021 Ahn et al.
2024 Zhu et al. 2023b), large network size. (Zhu et al.
2024
2023a)), in the following result we provide a refined global analysis on solving (3.1 that does not contain any big-O notation.
Theorem 3.1. Suppose we run gradient descent on 3.1 with step-size to be n, Define
2 =) 11 ( = (0; xX) y. 22 = m x e00) a= (L
(3.2)
Then we have (1) 2t+1 fz( and tluus Theorem 2.1 holds for Sa and zi (60) The sharpness is given by Amaz (V2l(w(())
32.
Comparison with existing results. An interesting conclusion from the above theorem is that, under certain cases the step-size n should depend on the model initialization. For example when c(0) > 0 then we should have vy7 || (0) = 20 < 2, since for 2p > 2 we have lim,-, | co (see, e.g., discussions under (2.2)). Note that Zhu et al. (2024) studied a related neural quadratic model (see their Eq. (3)). Here, we highlight that their results do not cover our case. Indood, defining Meii 2/ >max ( according their claim, catapults happen when Merit < 17 < Mera- In our notation, this condition is equivalent < 320 2a < 4. However this cannot. happen because if the initialization zo is sufficiently small, say
8

---

Published in Transactions on Machine Learning Research (04/2024)
20 =O(e), then know the previous condition become 1 - Occ) <a <a<3 < 2 However, according to Lemmas T and 2 we have that for < < 2 the training dynamics is in the periodic or the chaotic phase and 2, (and thus the loss function) will not converge to 0. Our theory (Lemma ! suggests that catapults for quadratic regression model happens for almost every 2n E (-a, provided that 2/2 - < a I 1. This intricate observation reveals that exlending the current results on the catapult phenomenon from the model
in Zhu et al. 2024) to our setting is not immediate and actually highly non-trivial.
Relationship with Sharpness and EoS. We also notice that, interestingly, in the monotonic and catapult phases (i..., 0 < a S 1), have the limiting sharpness satisfy lim, Amax ( (((((())) 2a/n (2 + [| particular, for the catapult phase (2v2- 2 < a S 1) the sharpuess converges to 2a E (4v2- l which theoretically and quantitatively explains the empirical observations of EoS in Cohen et al. 2021). More importantly, the notion of EoS only provides a coarse characterization of the oscillations sharpness al the interface of the monolonic and catapult phase. For the quadratic models that we study, the limiting sharpness exhibits a more nuanced behaviour as identify Theorem 3.1 while also recovering and extending existing results on EoS.
the limiting
Multiple Orthogonal Data Points. We now consider gradient descent quadratic regression multiple data points that are mutually orthogonal. Suppose we are given dataset {();, with ..... ,..,,....,, 1x, Similar orthogonality conditions are widely used in the literature sparse linear regression to understand the optimization or statistical properties (Tbb-
X (X1, ,,., X..) satisfying XX di
shirani 1996
Yuan & Lin 2006). Consider the optimization problem
a ((w) = 2n
min (w)
Σ i=1
(g(w; X.) - y1))
(3.3)
where ((w) and g(w; X.) are as defined in 3.1
Theorem 3.2. Define the following:
(X.) = c(Xi) + XX, " 3(x.) = yi + (o(Xi))²
27 kx(Xi) = By xX,
(x,) == = X.) y/s 20 = (x(())e(()) (X::): a, = 33(X)))
If we run gradient descent on solving 3.3 with step-size n, then we have (i) 2 (((11) sa (z)2) and thuss
Theorem 2. 1 hols for far and 2,00 (it) The sharpness Amax (w) = maxisisn 32 +200
For this sctup, the above theorem shows that the loss function is a summation of the loss on each individual data point. Recall that the training loss takes the form
10 n
((w(t)
2n (olw()) x.) v.)
2n
(X,)
2n ||
Setting P: = 2n,2 T we can deduce that the dynamics of f(w(!) is given by Corollary This leads Lo
the following Corollary.
Corollary 2. Under the setup in Theorem 3.2 for almost all 20)) {z: -0; S 2; S 2} we have
If0 < maxigiga a; 1, then limy (w)(t) = 0 Moreover, i < maxigign a; S 2 2, the sequence (((w)))) 1oo is decreasing.
If1 1 maxigisn 0; 2, then (E(w(())) bounded and does not converge 0.
If maxigisn a; > 2, then lim (w) +00.
Under the orthogonality assumption, the loss functions defined on each data point exhibit a non-intcracting behavior. Removing this orthogonality condition entirely is highly non-trivial. It would be interesting extend our setting to the nearly-orthogonal one in Frei al. 2022). and Kou et al. (023)
9

---

Published in Transactions on Machine Learning Research (04/2024)
3.2 Example 2: Neural network with quadratic activation
In this section, we consider the following two layer neural networks with its loss function on data point (Xt, 31) defined as:
ojo (1)))))) 4= (x),, - vi)2
gu, Xi)
mm
where the hidden-layer weights u, E R are be trained and outer-layer weights es are held constant, which corresponds to the feature-learning setting for neural networks. Also the width of the hidden layer and a is the activation function. Define U == (u11.-.. Um) When the activation function is quadratic
and = 1 for all i, the loss function becomes
min ((U) =
1 ((U)
1
Σ j=l
Σ i=1
(x u;)2 [XTTu))
v1)
(3.4)
2n
/md
We then have the following result As in the provious example, we assume XX diag(1 ...., 1x on the gradient descent dynamiis of the above problem. Theorem 3.3. Define the following:
2n |x,1| e
2n |xll y/ Vmdn
4 Vmnd (x.Tu Mir zi
Vmdn
If we run gradient descent on solving problem Theorem 2.1 and Corollory hold for E(U())).
3.4 with slep-size n, we have z; ((+1) = Say (2) and tvus
The orthogonal assumption that XX = X : ..... I3,, helps decouple the loss function across the samples and makes the evolution of the overall loss non-interacting (across the training samples). In order to relax this assumption, it is required to analyze bifurcation analysis of interacting dynamical systems, which is extremely challenging and not well-cxplored (Xu et al., 2021). In Scction C.2. we present empirical results showing that similar phases exists in the general non-orthogonal setting as well. Theoretically characterizing this is left open problem.
4 Experimental investigations
Before we proceed, we remark that the original PDF files for all the figures are provided as part of the supplementary material for the sake of casier visualization. The naming convention is as follows: (i) cach sub- folder correspond to the respective figure numbers and (ii) each file within a sub-folder is named according to matrix conventions. For e.g., file 1x3.pdf sub-folder Figure 1 corresponds to Figure 1(c) and file 1x1. xx1.pdf in sub-folder Figure corresponds to Figure 3
4.1 Gradient descent dynamics with orthogonal data for model
3.4
Experimental sctup, We now conduct experiments to evaluate the developed theory. We consider gradient descent. for training the hidden layers of lwo-layer neural net with orthogonal training data, described Section 3.2 Recall that d, m, and n represents the dimension, hidden-layer width, and number of data points rospectively. We set d = 100, E (5, 10, 25, n 80. We generate the ground-truth matrix U Rdxm where each entry is sampled from the standard normal distribution. The training data points collected in the data matrix, denoted as X E RRd are the first rows of a randomly generated orthogonal matrix. The labels are generated via the model in Section 3.2 i.e., yi = - E (X, uz)")) + where e; is scalar noise sampled from a zero-mean normal distribution, with variances equal to 0, 0.25, 1 in different experiments.
We the step-size 7) such that maxigisn 0; defined in Theorem 3.2 belongs to the intervals of the first four phases. In particular, we choose 0.3, 0.9, 1, 1.2, 1.8 for 5, 10 and 0.3, 0.9. 1, 1.2, 1.6 for m 25
10

---

Published in Transactions on Machine Learning Research (04/2024)
Testing Log
Testing Log Loss
Ergodic Testing Log Loss
Ergodic Testing Log Loss
Log Loss
1.0
0.5
0.0
0.5
25
50
1.00
125
150
175
200
Iterations
Figure 3: Test loss with and without averaging: The chaotic versions of purple and red lines correspond to the test error without averaging. The corresponding smooth versions refer to the lest error with averaging, The plot demonstrates the benefit of ergodic trajectory averaging based predictions (according to Definition 3 as the averaging based predictions become more stable across the iterations. Numbers 3, 4 denote different stepsize choices (see Section 4.2 for details).
(for each m, 0.9 and are both in the catapult phase, and we pick 1 since it is the largest step-size choice allowed in the catapult phase). The numbers 0, 2, 4 of the plot labels correspond to these step-size choices respectively. In Figure | we present the training loss curves in log scale and the sharpness curves for m 25. The horizontal axes denote the number of steps of gradient descent. In Section C.I we also provide additional simulation results for different hidden-layer widths. From the training loss curves (left column) and the sharpness curves (middle column) we can clearly observe the four phasee thereby confirming our theoretical results.
4.2 Prediction based on ergodic trajectory averaging
A main tako-away from our analysis and experiments so far is that gradient descent with large step-size effec- lively resembles a randomized gradient descent procedure with special type of noise, i.e., the randomness here is with respect to the orbit it converges to (in the non-monotonic phases) [ Recall that this viewpoint is also put-forward is several works, in particular Kong & Tao (2020). Hence, natural approach is to do perform ergodic trajectory averaging to reduce the fluctuations (see right column in Figure
Definition 3. For any given point X Rd, and any training iteration count the ergodic trajectory averaging based prediction, ÿ, for the point X is given by و f= 1 Ei= (f)(();;)) X), where w(() corresponds to the training trajectory of the gradient descent algorithm trained with step-size 1).
Another way to think about the above prediction stralegy is that the ergodic average approximates, in the limit, expectation with respect to the invariant distribution (supported on the orbit to which the trajectory converges to). In particular, Figure right column, for the orthogonal setup, we see that as the noise increases, training in the chaotic regime and performing ergodic trajectory averaging provides a fast decay of training loss. A disadvantage of the ergodic averaging based prediction strategy described above the test-time computational cost increases by O(t), per test point.
Figure 3 plots the testing loss for the model in (3.4), when trained with two values of large step-sizes (n 48, 60). We observe that the ergodic trajectory averaging prediction smooths out the more chaotic testing loss. However, we also remark that from the plots in Figure Id] operating with slightly smaller step-size choice (1) 36) achieves the best lesting error curves. See Section C.2 for additional observations.
"Here, do not plot the divergent phase here for simplicity.
"One way show this formally by connecting large step-size CD with slow-fast deterministic systems; sec, for ple, Chevyrey al. (2020): Lim et al. (2022.
Figure 10 provides detailed comparison across various step-sizes, for different noise variances.
11

---

Published in Transactions on Machine Learning Research (04/2024)
Fraxkr sokeellng aaggee
Freede breeec teo
MANDWAY WWw
Orpade Thiligup Lam
-25
Tarinng Log Late Log
Taning Lone
Thanding
Draadt: Thiiiig
14
Thanting Lave
Shere 7007
Draddt Thciing Lne
Thanding Laws
-25
Orgadi: Thiiiigg lom
0.0003
10
-35
11:0774
010010
Thand
Frewde Tree
Thanding Log
0.00/3
Dgadd: Triniig
Thanding Loss
Drgadi Trining Loa
-12
-34
-25
0.004
1.6
-15
90 50 70
Figure 4: Hidden layer width = 25, with orthogonal data points. Rows from top to bottom represent different levels of noise mean-zero normal distribution with variance 0, 0.25, respectively. The vertical axes are in log scale for the training loss curves. The second column is about the sharpness of the training loss functions. Numbers 0, 3, denote different stepsize choices (sce Section 4.1 for details).
In the literature, ways of artificially inducing controlled chaos in the gradient descent trajectory has been proposed to obtain improved testing accuracy; see, for example, Lim et al. (2022). We believe the ergodic trajectory averaging based prediction methodology discussed above may prove to be fruitful to stabilize the lesting loss in such cases as well. A detailed investigation of provable benefits of the ergodic trajectory averaging predictor, is beyond the scope of the current work, and we leave it as intriguing future work.
Additional Experiments. We also provide the following additional simulation results in the appendix: (i) Section C.2 corresponds to non-orthogonal training data. We also include testing loss plots, and (ii) Section corresponds to training the hidden-layer layer weights of two-layer neural network with ReLU activation functions and non-orthogonal inputs.
Take-away points from experiments. The main take-away points from the above experiments are the fol- lowing: (i) in the case of orthogonal data, the experiments confirm the theoretical results in Section 3 (ii) in the case of non-orthogonal data, the experiments show that similar phases (including the chaotic phasos) exists in the training dynamics, and (iii) ergodic averaging based prediction stabilizes the error along the GD trajectory.
12

---

Published in Transactions on Machine Learning Research (04/2024)
5 Conclusion
Unstable and chaotic behavior is frequently observed when training deep neural networks with large-order step-sizes. Motivated by this, we presented a fine-grained theoretical analysis of a cubic-map based dynamical system. We show that the gradient descent dynamics is fully captured by this dynamical system, when training the hidden layers of a two-layer ncural networks with quadratic activation functions with orthogonal training data, Our analysis shows that for this class of models, as the step-size of the gradient descent increases, the gradient descent trajectory has five distinct phases (from being monotonic to chaotic and eventually divergent). We also provide empirical evidence that show similar behavior occurs for generic non-orthogonal data. Our results also indicate subtle interplay the initialization provided to the gradient descent algorithm in terms determining which phase the training trajectory will operate in. Finally, we empirically examined the impact of training in the different phases, on the gencralization crror.
the relation between step-size and
Immediate future works include: (i) developing a theoretical characterization of the training dynamics with generic non-orthogonal training data, which involves undertaking non-trivial bifurcation analysis of interact- ing dynamical systems, (ii) moving beyond quadratic activation functions and two-layer neural networks, and (iii) developing tight generalization bounds when training with large-order step-sizes. Overall, our contribu- tions make concrete steps towards developing a fine-grained understanding of the gradient descent dynamics when training neural networks with iterative first-order optimization algorithms with large step-sizes.
References
Roy L Adler, Alan G Konheim, and M Harry McAndrew. Topological entropy. Transaclions of the American Mathematical Society, 114(2):309 319, 1965.
Naman Agarwal, Surbhi Goel, and Cyril Zhang. Acceleration via fractal learning rate schedules. In Proceed- ings of the 38th International Conference on Machine Learning, pp. 87 99, 2021.
Atish Agarwala and Yann Dauphin. SAM operates far from home: Eigenvalue regularization as a dynamical phenomenon. In Proceedings of the 40th International Conference on Machine Learning, pp. 152-168. PMLR, 2023.
Atish Agarwala, Fabian Pedregosa, and Jeffrey Pennington. Second-order regression models exhibit progres- sive sharpening to the edge of stability. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Kwangjun Ahn, Jingzhao Zhang, and Suvrit. Sra. Understanding the unstable convergence of gradient descent. In Proceedings of the 39th International Conference on Machine Learning, pp. 247-257. PMLR, 2022.
Kwangjun Ahn, Sébastien Bubeck, Sinho Chewi, Yin Tat Lee, Felipe Suarez, and Yi Zhang. Learning threshold neurons via edge of stability. Advances in Neural Information Processing Systems, 36, 2024.
Kathleen T Alligood, Tim D Sauer, and James A Yorke. Chaos: An introduction to dynamical systems., 1997.
Jason M Altschuler and Pablo A Parrilo. Acceleration by Stepsize Hedging Multi-Ster Step Descent and the Silver Stepsize Schedule. preprint arXiv:2309.07877 2023.
Maksym Andriushchenko, Aditya Vardhan Varre, Loucas Pillaud- Pillaud-Vivien, and Nicolas Flammarion. SGD with large step sizes learns sparse features. In Proceedings of the 40th International Conference on Machine Learning, pp. 003-925. PMLR, 2023.
Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on the edge of stability in deep learning. In Proceedings of the 39th International Conference on Machine Learning, pp. 948-1024. PMI.R, 2022.
13

---

Published in Transactions on Machine Learning Research (04/2024)
Bernd Aulbach and Bernd Kieninger. On three definitions of chaos. Nonlinear Dyn. Syst. Theory, 1(1): 23 23-37, 2001.
Tolga Birdal, Aaron Lou, Leonidas Guibas, and Umut Simsekli. Intrinsic dimension, persistent homology and generalization in neural networks. In Advances in Neural Information Processing Systems, 2021.
B Branner and J H Hubbard. The iteration of cubic polynomials. part 1: The global topology of parameter space. Acta mathematica, 160(3-4):143-22) 206, 1988.
Alexander Camuto, George Deligiannidis, Murat A Erdogdu, Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. Fractal structure and generalization properties of stochastic optimization algorithms. In Advances in Newral Information Processing Systems, 2021.
Nisha Chandramoorlhy, Andreas Loukas, Khashayar Galmiry, and Stefanie Jegelka. On the generalization of learning algorithms that do not converge. Advances in Neural Information Processing Systems, 35: 34241-34255 2022.
Lei Chen and Joan Bruna. Beyond the edge of stability via two-step gradient updates. Proceedings of the 40th International Conference on Machine Learning, 2023.
lyy Chevyrev, Peter K Friz, Alexey Korepanov, and lan Melbourne. Superdiffusive limits for deterministic must-slow dynamical systems. Probabilily theory and related fields, 178(3-4):735 770, 2020.
Jeremy Cohen, Simran Kaur, Yuanzhi Li, Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs the edge of stability. In The 9th International Conference on Learning Representations, 2021.
Alex Damian, Eshaan Nichani, and Jason D. Lee. Self-stabilization: The implicit bias of gradient descent at the edge of stability. The 1h International Conference on Learning Representations, 2023.
Welington De Melo and Sebastian Van Strien. One-dimensional dynamics, volume 25. Springer Science & Business Media, 2012.
R Devaney. An introduction to chaotic dynamical systems. An Intsoduction to Chaotic Dynamical Systems, 1989.
Benjamin Dupuis, George Deligiannidis, and Umut Simsekli. Generalization bounds using data-dependent fractal dimensions. In Proceedings of the 40th International Conference on Machine Learning, pp. 8922- 8968, 2023.
Albert Fannjiang and Thomas Strohmer. The numerics of phase retrieval. Acta Numerica, 29:125 228, 2020.
N Franzová and J Smital. Positive sequence topological entropy characterizes chaotic maps. Proceedings of the American Mathematical Society, pp. 1083-1086, 1991.
Spencer Frei, Gal Vardi, Peter L Bartlett, Nathan Srebro, and Wei Hu. Implicit bias in leaky relu networks trained on high-dimensional data. arXiv preprint arXio:2210.00 07082, 2022.
Justin Gilmer, Behrooz Ghorbani, Ankush Garg, Sneha Kudugunta, Behnam Neyshabur, David Cardoze, George Edward Dahl, Zachary Nado, and Orhan Firat. A loss curvature perspective training instabilities of deep learning models. In The 12th International Conference Learning Representations, 2022.
Baptiste Goujaud, Damien Scieur, Aymeric Dieuleveut, Adrien B Taylor, and Fabian Pedregosa. Super- acceleration with cyclical stop-sizes. In International Conference on Artificial Intelligence and Statistics, pp. 3028-3065. PMLR, 2022.
Benjamin Grimmer. Provably faster gradient descent via long steps. preprint arXiv:2307.0632. 2023.
Benjamin Grimmer, Kevin Shu, and Alex L Wang. Accelerated Gradient Descent via Long Steps preprint arXiv:2309.09961 2023.
14

---

Published in Transactions on Machine Learning Research (04/2024)
Jack K Hale and Hüseyin Koçak. Dynamics and bifurcations, volume 3. Springer Science & Business Media, 2012.
Luis Herrmann, Maximilian Granz, and Tim Landgraf. Chaotic dynamics are intrinsic to neural network training with SGD. In Advonces in Neural Information Processing Systems, 2022.
Liam Hodgkinson, Umut Simsekli,, Rajiv Khanna, and Michael Mahoney. Generalization bounds using lower tail exponents in stochastic optimizers. In Proceedings of the 39th International Conference on Machine Learning, pp. 8774 8795, 2022.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Kishore Jaganathan, Yonina C Eldar, and Babak Hassibi. Phase retrieval: An overview of recent develop- ments. Optical Compressive Imoging, pp. 279 312, 2016.
Stanislaw Jastrzebski, Maciej Szymczak, Stanislav Fort, Devansh Arpit, Jacek Tabor, Kyunghyun Cho, and Krzysztof Geras. The break-even point on optimization trajectorics of deep neural networks. The 8th International Conference on Leurning Representations, 2020.
Maxim Kodryan, Ekaterina Lobacheva, Maksim Nakhodnov, and Dmitry P Vetrov. Training scale-invarine neural networks on the sphere can happen in three regimes. Advances in Neural Information Processing Systems, 35:14058 35:14058-14070, 2022.
Sergin Kolyada. Yorke sensitivity and other concepts of chaos. Ukraindon Mathematical Journal, 56(8), 2004.
Lingkai Kong and Molei Tao. Stochasticity of deterministic gradient descent: Large learning rate for multi- scale objective function. Advances in Neural Information Processing Systems, 33:2625 2638, 2020.
Yiwen Kou, Zixiang Chen, and Quanquan Gu. Implicit bias of gradient descent for two-layer relu and leaky relu networks nearly-orthogonal data. arXie preprinl ar Xrx:::2310. 18935, 2023.
Itai Kreisler, Mor Shpigel Nacson, Daniel Soudry, and Yair Carmon. Gradient descent monotonically de- creases the sharpness of gradient flow solutions in scalar networks and beyond. In Proceedings of the 40th International Conference on Machine Learning, 2023.
Andrzej Lasota and Michael C Mackey. Chaos, fractals, and noise: stochastic aspects of dynamics, volume 97. Springer Science Business Media, 1998.
VI Lebedev and SA Finogenov. Ordering of the iterative parameters in the cyclical Chebyshev iterative method. USSR Computational Mathematics and Mathematical Physics, 11(2):155-170, 1971.
Aitor Lewkowyez, Yasaman Bahri, Ethan Dyer, Jascha Sohl- DicksDick,,,,n, and Guy Gur-Ari. The large learning rate phase of deep learning: The catapult mechanism. preprint arXiw:2003.022. 2020.
Tien-Yioe Li and James A Yorke. Period three implies chaos. The American Mathematical Monthly, 82(10): 085-992,100 1975.
Soon Hoe Lim, Yijun Wan, and Unut Simsekli. Chaotic regularization and heavy-tailed limits for determin- istic gradient descent. Advances in Newral Information Processing Systems, 35:26590 26602, 2022.
Ekaterina Lobacheva, Maxim Kodryan, Nadezhda Chirkova, Andrey Malinin, and Dmitry Vetrov. On the periodic bchavior of neural network training with batch normalization and weight decay. In Advances in Newral Information Processing Systems, 2021.
Kaifeng Lyu, Zhiyuan Li, and Sanjeev Arora. Understanding the generalization benefit of normalization layers: Sharpness reduction. Advances in Neural Information Processing Systems, 35:34689 3444689-34708, 2022.
John Milnor. Remarks iterated cubic maps. Enperimental Mathemalics, 1(1):5 24, 1992.
15

---

Published in Transactions on Machine Learning Research (04/2024)
Helena Engelina Nusse. Asymptotically periodic behaviour in the dynamics of chaotic mappings. SIAM Journal on Applied Mathemalics, (7(3):498-511) 1987.
Edward Ott. Chaos in dynomical systems. Cambridge university press, 2002.
Samet Oymak. Provable super-convergence with a large cyclical learning rate. IEFE Signal Processing Letters, 28:1645 1649, 2021.
Thomas D Rogers and David C Whitley, Chaos in the cubic mapping. Mathematical Modelling, 4(1):9 25, 1983.
David Singer. Stable orbits and bifurcation of maps of the interval. SIAM Journal on Applied Mathematics, 35(2):260-25) 267, 1978.
Henrik Skjolding, Bodil Bramner-Jargensen, Peter L Christiansen, and Helge E. Jensen. Bifurcations in discrete dynamical systems with cubic maps. SLAM Journal Applied Mathematics, 43(3):520 534, 1983.
Leslie N Smith. Cyclical learning rates for training neural networks. In 2017 IEEE winter conference on applications of computer vision (WACV), pp. 464-472. TEFE, 2017.
Jascha Sohl-Dickstein. The boundary of neural network trainability is fractal. arXiv preprint arXiv:2402.06184, 2024.
Minhak Song and Chulhee Yun. Trajectory aligument: Understanding the edge of stability phenomenon via bifurcation theory. Advances in Neural Information Processing Systems, 36, 2024.
Steven H Strogatz. Nonlinear dynamics and chaos: With applications to physics, biology, chemistry, and engineering. CRC press, 2018.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Sociely Series B: Statistical Methodology, 58(1)2267-288, 1996.
Kees Van Den Doel and Uri Ascher. The chaotic nature of faster gradient descent methods. Journal of Scienlific Computing, 51:560 581, 2012.
Yuqing Wang, Minshuo Chen, Tuo Zhao, and Molei Tao. Large learning rate lames homogeneity: Conver- gence and balancing effect. In The 10th International Conference on Learning Representations, 2022.
Jingfeng Wu, Vladimir Braverman, and Jason D Lee. Implicit bias of gradient descent for logistic regression at the edge of stability. preprint arXiv:2305. 11788, 2023.
Can Xu, Xuan Wang, Zhigang Zheng, and Zongkai Cai. Stability and bifurcation of collective dynamics phase oscillator populations with general coupling. Physical Review E, 103(3):032307, 2021.
Ming Yuan and Yi Lin. Model selection and estimation in regression with grouped variables. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68(1):49 67, 2006.
Jingzhao Zhang, Haochuan Li, Suvrit Sra, and Ali Jadbabaie. Neural network weights do not converge to stationary points: An invariant measure perspective. In Proceedings of the 39th International Conference on Machine Learning, pp. 26330 26346, 2022.
Libin Zhu, Chaoyue Liu, Adityanarayanan Radhakrishnan, and Mikhail Belkin. Calapults in SGD: Spikes in the training loss and their impact on generalization through feature learning. preprint arXiv:2306.00 04815, 2023a.
Libin Zhu, Chaoyue Liu, Adityanarayanan Radhakrishnan, and Mikhail Belkin. Quadratic models for under- standing neural network dynamics. In The Twelfth International Conference on Learning Representations, 2024. URL
16

---

Published in Transactions on Machine Learning Research (04/2024)
Xingyu Zhu, Zixuan Wang, Xiang Wang, Mo Zhou, and Rong Ge. Understanding edge-of-stability training dynamics with a minimalist example. In The 11th International Conference on Learning Represenlations, 2023b.
Liu Ziyin, Botao Li, James B Simon, and Masahito Ueda. SGD with Constant Large Learning Rate
Can Converge to Local Maxima. In International Conference on Learning Representations, 2022. URL
17

---

Published in Transactions on Machine Learning Research (04/2024)
Supplementary Material for "From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression"
A Proofs of Main Results
A.1 Proofs of results in Section 2
We first present several technical results required to prove our main results.
Lemma 4. Let f(x) be polynomial. If all the roots of (z) are real and distinct, then we have
(')(x) (x)
Sf(x) = fz) 2 f((x)
< 0 for all x E I with f'(x) # 0.
Proof. See, e.g,, the proof of Proposition 11.2 in Devaney 1989
Lemma 5. Suppose we are given a real-valued continuous function f(z) R + R and a bounded closed interval S It with To e Define I = (zo). If the sequence { is monotonic, then one of the following holds.
(am & I, i..,, there cvists De & I for some t.
(i) {Ex) S I, and lim (mo) exists and a fixed point of f(x in
Proof. If (i) holds, then the conclusion is true. When (i) does not hold, then {=e] I. Since this sequence is monotonic and included in bounded closed interval, we know its limit exists and is in J. Moreover, have
lim Ce lim T++1 lim f(z)) = f( lim xt); 1+000
2000
t-000
t-000
where the last equality holds since f is continuous. Clearly lime- Te is fixed point of f.
The following lemma characterizes the basic properties of the cubic function fa defined in 2.1 Lemma 6. Suppose
0. Then fa(z) has the following properties.
(i) The local minimum and marimum of fa(z) are at 2 = 1 and 2 1-2a respectively, and
fa(1) -a, fa (1-20)
2a
(2a 1)(2a² 7a 4) 4a 12a² 15a
3
27
27
(ii) fa(z) is monotonically increasing on [-a, 1-2a], monotonically decreasing on [2-2a 11, and monotonically increasing on [1,2]. 2].
(Mi) For any a S S 2, we have a S fa(z) max {fo (1-2²), .2]. Moreover, fa (1-2a) S 2 if and only if 2.
Proof. Note that have
f1(2) = 3= + 2(a 2(aaa22222) + (1- -a) = (z 1) + 2a 1).
(A.1)
which implies and 1-20 are critical points of fa(z). Moreover, by (=) 62 + 2a - we know f((1) > 0 3
and f ( (122) 0. Hence, they are local minimum and maximum respectively. The rest of (i) is true by
caleulation. (ii) is true by noticing the expression of (2( in AA.1 (iii) is direct conclusion of (i) and (ii)
since for < z < have
(1- 2a
min (fa(1),f( S fa(=) max Sa
Saa(2)
3
18

---

Published in Transactions on Machine Learning Research (04/2024)
By (i) and some calculation know
1 20
4a + 12a 15a
50
(2a + 5) 2)
Ja
2
3
27
27
This proves the rest of (iii).
Lemma 7. Suppose 2
< $ 1. Define five subintervals of 1-a, 2] as follows.
2
V 4a
2
12 + 4a
1
1
2
2
2 - +
Va²
+ 4a
2 + v + 4a
I3 0,.025)
Ia
0.25,
15
2
2
Then we have
fa(h) Sh 12, fa(T4) U1, fa(T) UUU..
(8) fa(b) la, fala 12
Proof. We first prove (i). By Lemma we know fa(z) is increasing on 1i, achieving its local minimum at on 1,, increasing on Is, then we know
2 V + 4a
fa(T))
fa( fa
=1-a,0]=h1u 12
2 - + va² + 4a
}
fa(1))
f1),,, max
(0.25), fa
[-a,00] 1.
2
2
+
V + 4a
fa(1s)
fa
fa(2)
[0,2] 17 UUU44UA
2
This completes the proof of (i).
To prove (ii); observe that when (2v2 2] we have
2-a- va"+40 1-2a < By Lemma we know
2
the local maximum of fo over 1/ = 2-0 --e-vo=+1g 0) is achieved at 1-20 this together with the fact that
3
Sa(0) = Ja (2 va 40 = 0 implies
(1 1 2a
4a + 12a²
15a +
fa (12)
fa), fo
0,
C [0,0.25],
3
27
where the last subset inclusion is true since
(4a + 12a. 15a + 4) = 12a² 24a 15 > 0, Va E (2v2 2,
This implies when E (2v2- - 2,1
4a 12a² 15a 4 (4a3 12a²
15a
4)
< 0.25.
27
27
27
On the other hand, we know from Lemma
6 that on Ig
10,
0..55
[1-2a .1])
: fa is decrcasing. Hence,
7
9
2
va 4a
(Is) [0..)) [0)
0
C
0 Iz-
16
16"
19

---

Published in Transactions on Machine Learning Research (04/2024)
where the last subset inclusion is true since
(0.25) = 16 a +
a
V va²
4a
Va E (2v2- -2 2.
16
2
This completes the proof of (ii).
See Figure (a for a visualization of the subintervals 1,,.. Is for a = 1 and an example of the orbit on it.
(a)
(b)
(c)
(d)
Figure From left to right: cubic function [1(=) with different regions diveded by subintervals and a trajectory of { cubic function f1,2(2) with two period-2 point, cubic function f1,(()) with a period- point, and cubic function (2) with a diverging orbit. We have the cubic curve and the identical mapping line the solid curves. We use four colored dashed lines in Figure (()) to represent the boundaries that are orthogonal to the endpoints of 12 and 44 defined in Lemma 7 respectively. The triangle markers represent some terins of a certain orbit, in which horizontal and vertical dotted lines visualize the transitioning trajectory between consecutive lerms in an orbit.
Lemma Suppose
and S z0 S Then we have
a S 2, S for any i, and fa does not have period-2 point on [-a, 2].
(G) If za is chosen from [-a.2] uniformly at random, then lim = 0 almost surely. Moreover,
if0 < a < 2v2 2, then almost surely |2e41l S |eel for all t. If 2f22 - 2 < S 2, then almost surely | has catapults.
Proof. The boundedness each iterate (i.e., 2t E [-a, 2)) can proved by using simple induction and Lemma
0 S 1, and -a zo S. 2. To prove the rest (i), by 22.1 we know a period-2 point is a
solution of
(1) = fa(2) #
which are equivalent to
ga(=)ga (a)=))a(ga)) (2ga (2)) = 1, 0,2.
(A.2)
Hence suffices to prove A.2 do not have a solution. Define
(=(2) = ga(=) - = (= + a)(= 2) < 0, Vz E (-a,2) 2).
We have
ga (((=)9o(29)())) -
=ha(2) + +4
=ha(2)(1 ho + h2(2)) 22 (12(()))))))))))))))))))))))))))
(2), 22 22 + (a 2)z +2).
(A.3)
20

---

Published in Transactions on Machine Learning Research (04/2024)
We have
+ (2 - 2)
=(2ga())+ +0)(s//((((()))+2))2)) + + + (a - 2) +2
+ (2 (a- + (a-22 +1 - 2a) - 22
+=)2++0)(2 - -)) (a (a-2)=+
=2 + (2a 4)2² + (a" 8a 7)2 (4a² 12a + 8)2² + (5a² - 10a + +)
-2aa 6a + 4) 2a
(02² + (a 1)2 1- (2 4 + (a - -- + (3 3a)²² + (2a 2) + 2).
(A.4)
Observe that
2² (a 1)2 + (1 a) (1 a) (a 1)2
(3 + a) a)
2 0, Va E (0,
(A.5)
The equalities hold if and only if : = 0, a = We also have
オ + (a - 3) + (3 -3))²² + (2a- 2) +2> 0, V2 E (0, 1,2)
24 + (a 3)2² + (3 330)= 3a)=² + (2a 2)2 +2
1
=2(= 1)(= 2) + + 2- 32 +
Vz & (0, 1,2).
For different we can verify the following inequalities via basic algebra or Young's inequality:
1
+ 1 <0,
z(= - 1)(c 2) 2) <0,
+ 2
+
< <1 2 +
1> E (1,2).
x2 33-32 32 +2
-025
1
1
z(2 - 1)(c - 2) > 0,
+ 2
-
+
> 0++1+1 ++1+1+0>1 0,
43 E (0,
82 -
32 +2
1
1
=(= 1)(c 2) < 0,
+ +
+
<1-1 1+ <0,
V> E (-a,0).
22 - 32 +2
2
Thus we may conclude that
x + (a 3)2² + (3 3a)2²² + (2a 2) +2> 0, V2 (-a,2).
(A.6)
By A..
A.5 a, 2).
A.6 we know ga ga (z)aa())((2)) - + 0 if $ {-a, 2}. Hence fa does not have a
period-2 point
To prove the first part in (ii) (the limit converges to 0 almost surely), we will prove
(1) lim 21 {-a, 0,2), (2) The set S such that the orbit with 20 S has measure 0.
(A.7)
We now consider two cases E (0,2/2 2 and E (2v2- 2,.
Case 1: a E (0,2v2 - 2). Note that we have
19. = 123 + (a - 2) + 1 1 2a| S max (19a( (l9a(-a)),laa()) 19a (1 (1-2) 1,
where the last equality holds since sa(-a) = (2) Hence, we know
and |ga (1 (1-3) () 2² < 1 for any E 20,2v2-2 2].
|z441| (xx)) (z)) S Izel. Ves E l-a,
(A.8)
21

---

Published in Transactions on Machine Learning Research (04/2024)
Hence lim |al exists.
lim
[x lim
lim
(x
(-000
2-900
Hence, we know
lim
|ze|
0, or
lim 1-00 11000
[ze| * O,
lim
[g
1-000
If lom [2e| + O, then we have two subcases
Sub-case 1: lime-soo & exists. We can verify that
lim 2t lim 2e-1 fa (((
lim 2r) t-000
and thus limy 2e is one of the fixed points of fa(z) E a-a, 0.
Sub-case 2: lim;-+o 2 does not exist. Since lim; 12el exists, know there exists an infinite subsequence (denoted A1) of { with some limit and the complement of the sequence, another infinite subsequence (denoted as A2), has limit -c for some constant e >>> 0. Hence, we can pick a sequence of the subscripts hn < K2 <... < kn <.. such that Σky 2k belong to A and -k1+1: ZR, +1, belong to Ag. Moreover, we have
c lim Zk: = lim 2h,+1 - lim (a,Ka(=k,)) cCa(c) 5-000
1-000
10000
This implies that ga(c) -1, i.,
2 (a 2)c + 2 -2a= =0
From its discriminant (a - 12)22aa) = a² + 4 -4- 0 for E (0,2v2 where equality holds
only at 2/2 2, we know = 2/2 2 and thus c = 2 - 22. However, we can apply the similar trick and pick another sequence h < h2 <... < kn < ... such that 2hg :...... 22,, belong to Ag and -1,-1: 2 +1..... belong to A₁. This implics
lim 2k. = lim 2k+1 = lim (a -(-c)ga(-
which gives
②² 2- (a 2)c + 2 2a =
This contradicts with 2-2 - and 6 c= V2. This means case 2 does not exist.
Hence, we know | is decreasing (not necessarily strictly) and lim 2, E a-a, 0,
Case 2: a E (2v2- 2, 1]. We divide the interval [-a, 2] into the following five parts:
2
a² + 4a
2
a + 4a
I
Ig
2
2
2 - + a
+ 4a
2 +
0 + 4a
1a [0.0.55. 4
0.25,
15
2 2
2
Recall that by Lemma 7 we have:
fl1 424 fa(12) S 13, fa(1s) S l, fa(4) U.2 fa(1s) = U04.
22

---

Published in Transactions on Machine Learning Research (04/2024)
We have the following conclusion. Observe that fa is continuous, and
2 - Va² + 4a
1++1 2t = [s((z)) - 22 + (= 2) 2 0, Vz, E/
-0,
2
- a + v a² +
+4a
2+1 = -a((z) 24 =2 + (z) - 2) S. A2 E T =
2
We know if the sequence {=) visits 1s, by Lemma 5 we know either lim = 2 or there exists M > 0 such that $ Is for any t 2 M. Then if the sequence visits I then by Lemma 3 either lim 2 -a or there exists M > M > 0 such that 2, E 12 1/ for any L 2 M, since fa(1) C 1 U1 and (12 C 12U13. Hence, the proof reduced to the case when 20 E I2UIz. For the case when 20 E LUUI = 2-a va*+ia 0..55 The key observation to show that in this interval
2
|2+2| S |2c/.
(A.9)
Recall that by Lemma (ii) we have
fo (I2) S Is, fa(Is) S Iz.
(A.10)
To prove A.9 we know it holds when 2 = 0. When o + 0, by A.10 we know f())(z)) and have the same sign provided 21 12
2-a V +4a 0.25 This together with
( (z) = (z(2ga(Ja(a)) = =ga (=)ga(=)((=))
implies that go (zg.) when
120- vo 2 0) (0,0.25) Thus know
| = | (a (Z (z+)) = (=.ga)))))
Thus to prove (A.9 it suffices to show ga (2(2ga (al.ga(ggga (2)) - < 0, which is true by combining A.3
(A.4
(A.5). and A.6 This completes the proof of (1) in A.7 To prove (2) in A..7) we first notice that
fa(z) = 2(2 + a)(= - 2) > for any 2 E (-a, 0), and thus 24+1 > 22 for any 2t near -a. Hence, lim 2t -a if and only if there exists t such that 2 Similarly, fa(=)
This implics that f( (2o) a for some t. < 0 for any E (0, 2), which implies 2141 Zt for any near 2. Hence, lim 2
if and only if 20 = 2. Define
x = (-a00)) 0=0
where - denotes the preimage of -a under (()) Clearly, each preimage is a finite set, and thus $ is countable. Hence, we know as long as zn E [-a, 2),,5, we have lim 2, = 0. Since S countable set and 20 is chosen uniformly at random, we know lim 2t 0 almost surely.
For the rest of (ii), have already proved in A.8) that (1 is docreasing when 0 < s 2 2. To see {1 has calapults when 2 - 2 < S 1, consider the following intervals
2 2-at a+ V + 4a
J1 = J2 min
.0.25
ls.
where we have a² + 4a - 4> 0 for a > 2 - 2 so J2 is well-defined. Notice that
0 0<2< - a a + 4a - 4
# (z(z) < 11, > 0.
23

---

Published in Transactions on Machine Learning Research (04/2024)
Hence we know for any 24 E J2, we will have
2441| (2)) > |2c/.
(A.11)
On the other hand, notice that 0 is in the orbit if and only if 20 $ So, where So is defined as
2
So U (
(0)
1==
where (z) denotes the set of preimage of under f( Note that each preimage is finite and thus So is
countable. Hence, we know almost surely the orbit will not contain 0, and recall that by Lemma 7 (ii) and lime-+oo 4 = 0, we know there are infinitely many such that E J2, and thus (A.11) holds for infinitely many 1 almost surely. By definition 2 know { has catapults almost surely.
The following theorem indicates that, fa is chaotic provided that a, where a, (1,2) and S za S 2. Then have
Lemma 9. Suppose
a S 2, 2 for any t, and fa(z) has period-2 point on [0, 1].
(8) There erists a. (1,2) such that for any E 2), Sa is Li- Yorke chaotic, and for ony a (1,a,), fa is not Li- Yorke chaotic.
(ii)) If there erists an asymptotically stable orbit and is chosen from [-a, 2] uniformly at random, then the orbit of 20 is asymptotically periodic almost surely.
Proof. The boundedness of 21 is direct result of Lemma (ii.). To prove the rest of (i), we notice that for a E (1,2)
Ia (0)g) (0)) (1 2a)²² > 9a (1))) = -
By contimuity of ga (a(gaa))) (2)) we know there exists a point 2u E (0, 1) such that ga (2og 1. This indicates that (20) = z0ga (z0ga (zo)) zo but clearly fa(=o) zo since (0, 1) does not contain any fixed point of fa-
To prove (ii), notice that
1 (1-2x1
5
< 1 <1<2=> f2 21-2 1-2x2 2
fi
27
By continuity of fa (1-22) (with respect to a) there exists E (1, such that
2c
(2c () 7c 1.
Sa
(A.12)
3
27
Moreover we have
1 1- 2c
1- 2c
1 1-20
fc(-c)= =-
fo
1
3
Hence by contimuity of fe(2), we can pick 2α E (-c,
1-26)
such that fc(20) = 1-2c
We have
3
1- 2c
-c 20
fc(2o).
(A.13)
3
By A.12).
A.13 and Lemma 6 (i), have
2c
(()) = ((2)
=f(11 -c 20.
(A.14)
3
1 1- 2c
fc(20)
< 1 = fc(1) (( (zo)
(A.15)
24

---

Published in Transactions on Machine Learning Research (04/2024)
Combining A.13
A.14
A.15
easily verify that
fc (zo) S 20 < fc(zo) < fc2 (z0).
By Theorem B.1 (i.e. Theorem 1 in Li & Yorke 1975 2,, we know
know So is Li-Yorke chaotic. Moreover, for any
2a
(2a 1)(2n² + Ta 4) (2c 1)(2c + Te 4) =
11-2c 2c
fa
3
27
3
which together with fa( < implies we can pick yo such that
1
< yo < 0, fa(v)) =
3
Similarly, we have
1 2a
1 (1-2) 2a
fa(-a) -0
yo fo
> 1 yo
3
which implies we can pick zo such that
1 2a
fa(zo) yo.
Now we know
(13) (mo) xD fa(xo)
By Theorem B.1 (i.e., Theorem 1 in Li & Yorke (975) ) we know fa Li- Yorke chaotic. Hence, we know c
defined in A.12 satisfies that for any E (c. 2], fa is Yorke chaotic. Hence, we know
= inf fa: fo is Li- Yorko chaotic for any b E 2). aE(1,2)
where the set not empty, since we have proven e belongs the above set. This completes the proof of (fi).
To prove (iii), notice that if f2) has asymptotically stable periodic orbit, by Theorem B.2 (i.e.,
Theorem 2.7 in Singer 1978 and the fact that fa(x) has negative Schwarzian derivative at non-critical points (Lemma and we know there exists a critical point of fa(z) such that the orbit of e converges to this asymptotically stable orbit. Notice that by Lemma 6 we know
or 1-2n c = can be excluded since (1) = aa, and -a is an unstable period-1 point. Hence, we know C = 1-24 asymptotically periodic. 3
By Theorems B.3 and B.4 (i.e., Theorem and Corollary Nusse (1887) we know almost surely 20 will not converge to any periodic orbit if 2u is chosen from [-a, 2 uniformly at random. This completes the proof.
Remarks:
See Figure 5(b) for a pair of period-2 points when a 1.2, and Figure 5(c) for a period-3 orbit when 1.6. The triangle markers denote the periodic points.
By Theorem B.2 (i.e., Theorem 2.7 in Singer (9788)) and the fact that is unstable period-1 point
we know f2) has at most asymptotically stable periodic orbit.
Lemma 10. Suppose a 2. 20 is chosen from [-a, uniformly at random. Then lim | +oo almost surely.
25

---

Published in Transactions on Machine Learning Research (04/2024)
Proof. Notice that by Lemma know
1 2a fa
4a + 12a² 15a + (4a + 12a² - 15a + 44)la=2 = 2, Va > 2,
3
27
27
where the incquality holds since 4a 12n - 15a is increasing (2, 00). Morcover, we have
fa(2) - 2(2 (= 2) 0, 42 (2,
Hence we know for the initialization at the critical point 20 --2 we have 21 > 2, and the whole sequence is inereasing. On the other hand, all fixed points of fa(=) are no greater than 2, we know 2; will diverge
+00. For another critical point 2g we know its orbit converges to the periodic orbit of 2g -O, which
is unstable period-1 point. Hence, we know from Theorem B.2 (i.e., Theorem 2.7 in Singer (1978) that
there does not exist an asymptotically stable periodic orbit, herwise the orbit of one critical point must converge to it. Hence, by Theorems B.3 and B.4 (i.c., Theorem B and Corollary in Nussc 1987] )) we know
lim;-sea | = +00 almost surely provided 2g uniformly chosen from (-a, 2), i.e., almost. all points [-a, 0, 2] converge to the absorbing boundary point +0c.
A.2 Proofs of results in Section 3
Proof of Theorem
3.1
Define
6² (1) = c c "0(0), 3: y
k:= 17 ||X1
27'
To prove (i), we observe that
V Vwg(w; w; X) = 7(x x))x
Let weights at time t be (t)), Thus, the gradient descent takes the form
w ((+1) = (t) ;); X) -y)(c 7 "x))x = w - 10 X.
Simple calculation gives
e (a(1))2
(A.16)
27
and
(1-1) = (1 (1- my> |||1| / )(0))a(()))) = (1 - (1)
Hence
(1+1) - c(()) (al++3))2((a = ((1-re(t)) (nl1)²
27
27
which together with A.16 implics
ke(t+)) = (ne() + Bk) (ne! 2) + kt(().
By definition of and 2, in 3.2 we know a 3K and 2 = (t()), We know (i) holds.
To compute the largest eigenvalue of the Hessain matrix (i.e., the sharpness defined in EoS literature) of the loss in (ii), notice that the gradient of the loss function takes the form
Ve(w)= (g(w; X) y) Vw.(w;;X) X).
26

---

Published in Transactions on Machine Learning Research (04/2024)
Hence
V+((w)= vig(w; X mn x)* + (z(w;)) y) Vig(w; X) = (a² + +
where we overload the notation and define
a = w, c = g(w:X) - y-
The sharpness is given by
Amax = ((a(1)) + |1x1 (3yelt) 2yy =||
3ze 2a
7
Proof of Theorem
3.2 The gradient descent takes the form
w (++1) = (0)
(l)(w(1)) = ((()) Σ 1=1
(2) (Xi)a (X.)x,
2m 1=1
Similarly to A.16). for each error term (X;) we have
(x.)) 3(X.),
(X,)
(A.17)
27
and
(Xi) (X,)
>xx, "x.TT((ti (++1)) + +c(xi)
(x)) (+) (X, (0)) (X,) X, )
8, ((w(()
+ +c(())
j=1
=a
yn
( (X,))) X,
n
j=1
(X,) 3(x))a X, x,
(X,)
m
27
j=1
We overload the notation and set
X =
#(X) ((x)))
V# (0,9,,00,,,0
We can obtain
(x)3 xx(x) 7x(
(++1) (X) = (x) 7 x
(A.18)
2
where @ denotes the Hadamard product.
As XXT = diag(([] ..... [x,,1 we can rewrite A.18 as the following non-interacting version for each
data point:
17 1|
(H+))( (X,))
(x') -2,8x))))
2n
=(1- mm |x el (X,) (x,))
n
27

---

Published in Transactions on Machine Learning Research (04/2024)
This together with A.17 implies
(x,) (x)) = 1 -xx=0(x))((((((x))))))
2y
27 [xell (x;) + 73 |Xill' (e! (e(( (dl)(()) + +(x))
n²
Kkn (X,)e) (Xi) (nn (x) -2) (x))
+
By definition of 2 and a, we know
(11) (111)= =z, 21 + +a)((,/-)
- -2) + 22 =
===0===0o fa. (z)"))
The sharpness is given by
VoE Vug(u((;; Xx,) Viog(((();;)) + (o(1o(0;;, xx) v)) ( x.))
+ (x) XXX;
(3) (X,,) +
+ + (X,T).
Therefore we know
V'l(w0 = (37e + 24y + (xx)) |x,1| x,, 32.") + 22, X1, for all 1 isis S n.
which means we find n eigenvalues and eigenvectors pairs (x X1 (2((w(()) is sum of rank-1 matrices, and we have found n orthogonal eigenvalues. Hence we know Amax (V((((())) = maxigien 3x +2a. This completes the proof.
(= +2a Xn). Note that 9
Proof of Theorem 3.3
Define
1
2m
9 X,X].
v /mn
j=1
Note that we have
(1
1
Σ
(
Vmd XX,XX U(O
2
mm
i=1
This implies that the gradient descent update takes the form
U U(o) -(0)
a ! n j=l
ve e00 (UI9) (U
U /mnn
2m
UIo. X,,] U = -(1 -() -
TW==
j=1
Also we have
m
0f
(1+1) (t)
e)
md Σ
(x] ui ((11))2 (tt (XJ (XJx(()) )())))
i=1
Vmd" x
(D - ((())T X,
28

---

Published in Transactions on Machine Learning Research (04/2024)
and
(1- --
(f =
2m
Σ
10 X, {
(1- /mn
[
2n
Σe c X
mdn
j=l
j=1
Hence we know
(0)
- Eg
1
(A
2xJ A (U XX,
Vidd
412
|X, X3 U (U(O)
4n
0/9 |x x/] ( xx)
/md
mdPn2
/mdn"
4ny²
||x
4n |X,|
00)) (c/) (9++vu))
md2n2 mmd2n2
vmd
where the second equality uses xx = diag( |1 11 ...., 1x) By definition of 2, and a, we know
2/ (++1) fa, (z)
Henco we know the training dynamics of this model can be captured by the cubic map as well.
Auxiliary results
Theorem B.1 (Theorem in
Yorke (1755). ) Let I be a compact interval and f + I be continuous. Assume there point a E I for which the points b b= f(a), c= (a) and (a) satisfy
d S < < < (or
Then f Li- Yorke chaotic.
Theorem B.2 (Theorem 2.7 Singer 1978)) ). Let be a compact interval and let f : + I be a three times continuously differentiable function. If the Schwarzian derivative of satisfies
(x)
3 (z) ((xx ('(x)
Sf(x)
<0 for all e with f'(x) +
Then the stable set of every asymptotically stable orbit of f contains a critical point of f- Theorem B.3 (Theorem Nusse (1987)) Let be an interval and let f 1 +
a three times continuously differentiable function having at least one aperiodic point on I and satisfying:
f has a nonpositive Schwarzian derivative, i.e.,
SS(x) 5'(
[x)
2
SO for all x E I with ('(x) #
f(xx) ('(x)
(i)) The set of poinls, whose orbils do not converge to an (or the) absorbing boundary point(s) of T for f is nonempty compact set.
(iii) The orbit of each critical point for f converges to an asymptotically stable periodic orbit of f or to an (or the) absorbing boundary point(s) of I for f.
(in) The fixed points of f(2) are isolated.
Then we have
.(1 The of points whose orbits do not converge an asymetotically stable periodic orbit of or an (or the) absorbing boundary psint(s) of for has Lebesgue measure
29

---

Published in Transactions on Machine Learning Research (04/2024)
(2) There crists positive integer p such that almost every point in I is asymptotically periodic with
(x) H, provided that S(T) is bounded.
Theorem B.4 (Corollary in Nusse 1987)). Assume that f : R. polynomial function having at least aperiodic point ond satisfying the following conditions:
(i) The orbit of each critical point of f converges to an asymptotically stable periodic orbit of f or to an (or the) absorbing boundary point(s) for f: (it) Each critical point of f is real.
Then I salisfies the ussumplions (i)-(ir) of Theorem B.3.
C Experimental investigations
C.1 Additional experiments for the orthogonal case
For this section, we follow the same experimental setup as described Section 4.1
Only the hidden-layer
width is changed. Specifically, Figures and 7 we plot the training loss, sharpness of training loss and the trajectory-averee training in various phases.
Franck: Telmelaa
Crenil Treki trs
Ggadi: Trikiig lag lee
Log
-320
Thanding Lop
Shere
Opadi: Tehl
Thantin Lowe
0.0012
Dgadk: Teining Lne
Diaad:
2.2
0.0000
-22
-125
-220
-2.5
2.0
03002.00
Tranding
Lans
-2.55
Dradi: Trekkg lnm
Uraad: Trakiigg
Tranding Lack
0.00300
-172
Ergadi Triniig Lag Lec
4.70
-0.75
-000
0.00/75
3.5
20
Figure 6: Hidden-layer width =5, with orthogonal data points. Rows from top to bottom represent different levels of noise mean-zero normal distribution with variance 0, 0.25, 1. The vertical axes are in log scale for the training loss curves. The second column is about the sharpness of the training loss functions. Numbers 0, 1, 2,3, 3,4 denote different stepsize choices (see Section 4.1 for details).
30

---

Published in Transactions on Machine Learning Research (04/2024)
0.900330
Dradi: Thiniig Lag Lom
Opadi:
-12
-31
0.00000
0.00005
12.
Frand Lass
Ergadi Trsiing lee
Opack
-22
Trand Lost
Ergadi Friiiig
-225
-220
1.0
-145
20
-0.70
0.302:00
-0.70
Dipadic Trining
4979
6.75
Freak: sapees
0.001:2
-0.0
Thanding
-170
Frewil busaiiin
Thanding
Freek wwseelapees
-6.55
0.00.00
10
20 43 30 80
70
33
70
Figure 7: Hidden-layer width =10, with orthogonal data points. Rows from top to bottom represent different levels of noise mean-zero normal distribution with variance 0, 0.2.25, The vertical axes are in log scale for the training loss curves. The second column is about the sharpness of the training loss functions. Numbers 0, 1, 2,3, 4 denote different stepsize choices (see Section 4.1 for details).
31

---

Published in Transactions on Machine Learning Research (04/2024)
C.2 Non-orthogonal data
We next investigate the case when orthogonality condition does not hold. The setup is the same described in Section 4.1 except that = 5000 and each entry of the data matrix X E Rn is now sampled from a standard normal distribution. We also generate 500 data points from the same distribution for testing, Note that our theory in this work only applicable for orthogonal data. hence, for these experiments with non-orthogonal data, we first tune the step-size to be as large as possible, say Tmax: so that the training does 0, ...,, Hence, the step-sizes for loss and sharpness curves 0, 0, 3, 4 are chosen to be 10, 20, 30, 40, 50 for 5, 10 and 12, 24, 36, 48, 60 for m 25.
not diverge and then run the experiments for 5 7/max with
In Figures g and 10 we plot the training loss and the testing loss (with and without ergodic trajectory averaging) in log scale. Notably different phases (including the periodic and catapult phases) characterized theoretically for the case of orthogonal data, also appear to be present for the non-orthogonal case. We also make the following intriguing conclusions:
As a general trend, training roughly in the generalized catapult phase and predicting without doing the ergodic trajectory averaging appears to have the best test error performance.
In some cases (especially the one with high noise variance), when testing after training in the periodic phase, the test error goes down rapidly in the initial few iterations. Correspondingly, ergodic trajectory averaging after training in the periodic phase, helps to obtain better test error decay compared to ergodic trajectory averaging after training in the catapult phase. However, as mentioned in the previous point, training roughly in the generalized catapult phase and predicting without doing the ergodic trajectory averaging performs the best.
As discussed in Lim al. (2022), in various cases, artificially infusing control chaos help to obtain better test accuracy. Given our empirical observations and the results in [im al.) (2022). it is interesting to design controlled chaos infusion in gradient descent and perform ergodic training averaging obtain stable and improved test error performance.
Obtaining theoretical results corroborating the above-mentioned observations is challenging future work.
Beya
20
32
05
Figure 8: Hidden-layer width=5, with non-orthogonal data points. Rows from top to bottom represent different levels of noise- mean-zero normal distribution with variance 0,0.25, 1. The vertical axes are in log scale for loss curves. Numbers 1,2,,, 4 denote different stepsize choices (sce Section C.2 for details).
32

---

Published in Transactions on Machine Learning Research (04/2024)
Figure 9: Hidden-layer width-10, with non-orthogonal data points. Rows from top to bottom represent different levels of noise- mean-zero normal distribution with variance 0, 0.25.,5, 1. The vertical axes are in log scale for loss curves. Numbers 0, 2, 3, denote different stepsize choices (see Section C.2 2 for details).
Figure 10: Hidden-layer width=25, with non-orthogonal data points. Rows from top to bottom represent different levels of noise- mean-zero normal distribution with variance 0, 0.25, 1. The vertical axes are in log scale for loss curves. Numbers 0, 1, 3, denote different stepsize choices (see Section C.2 for details).
33

---

Published in Transactions on Machine Learning Research (04/2024)
C.3 Two-layer Neural Network with ReLU
While our main focus in this work is for quadratic activation functions, it is also instructive examine the dynamics with other activation function, in particular the ReLU activation. Hence, we follow the experimental setup from Section C.2 except that the activation function is now ReLU and repeat our experiments. For this case, the step-sizes manually chosen to be 60, 120, 180, 240, 300 for loss loss/sharpness curves 0, 2, 4, respectively.
Figure 11: Hidden-laye layer width=5 with ReLU activation. Rows from top to bottom represent different levels of noise mean-zero normal distribution with variance 0, 0.25, 1. The vertical axes are in log scale for loss curves. The last column is about the sharpness the training loss functions. Numbers 0, 1, 2, 3, 4 denote different stepsize choices (see Section C.3 for details).
Figure 12: Hidden-layer width=10 with ReLU activation. Rows from top to bottom represent different levels of noise- mean-zer nero normal distribution with variance 0, 0.25, 1. The vertical axes are log scale for loss curves. The last column is about the sharpness of the training loss functions. Numbers 0, 2,2,,, denote different stepsize choices (see Section C.3 for details).
34

---

Published in Transactions on Machine Learning Research (04/2024)
From Figures 11 and 12 (in particular from the sharpness plots), we observe various non-monotonic patterns, roughly including periodic and chaotic patterns. Obtaining a precise theoretical characterization of the training dynamics for this setting is extremely interesting as future work.
35


Reviews:
[{"review_id": "L5sB1ON3d0", "reviewer": "Reviewer_bCt9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of the paper is the clarity of the analysis of the cubic map. All the concept are generally well introduced, and I believe that the proofs are correct as well. The general idea of using dynamical systems tools to analyze ML systems is a good one that is gaining popularity in the field.\n\nThe main weakness is the question of relevance to the audience of TMLR. One major issue is that the analysis is effectively one-dimensional. Even in the multi-datapoint setting, the model-input statistics are chosen such that the different datapoints have decoupled dynamics. This is very different from the case in typical machine learning settings. It is not clear if the 5 distinct phases are maintained in the more general setting. Generally practitioners find convergent, edge of stability, and divergent phases; the intricacies of the periodic and chaotic phases seem more like artifacts of the effectively low-dimensional nature of the system.\n\nThe order of presentation makes the paper hard to parse - since it starts with analysis of the universal form of the dynamical system, and then afterwards introduces the relationship to the ML models. Personally I would prefer some introduction of a machine learning model first, so that as a reader I can understand what $z$ and $a$ correspond to in the real system from the start. I am curious to think what other reviewers think of this point.\n\nThe claim in section 4.2 that SGD behaves like large stepsize GD is false; there is a large literature on how SGD with small batch size behaves qualitatively differently from full batch GD.\n\nThe utility of the ergodic trajectory averaging is not clear to me. In most modern ML systems, the loss trajectories become (relatively) smooth by the end of training; I'm not sure what one would hope to gain by averaging within a single model.\n\nEdit: changed relevance to \"yes\" after reading other reviews, responses and requested changes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors analyze the non-linear dynamics of full batch gradient descent using a quadratic regression model as well as a quadratic activation, one-hidden layer neural network, with orthogonal data. They show that these systems can be described by a universal cubic discrete dynamical system. They show that the universal system has 5 phases: monotonic, catapult, periodic, chaotic, divergent. They then show that a particular quadratic regression model inspired by the phase chase problem is described by the universal map, as is quadratic activation one-hidden layer network with orthogonal data. The different phases can then be linked to the combination of initialization and learning rate. Finally the authors show that in these models, averaging of trajectories in the chaotic phase can lead to predictors with lower loss.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It would be helpful to briefly describe the utility of the Lyapunov exponent and Shwarzian derivative when they are defined. TMLR readers may not be familiar with these concepts.\n\nThe name \"catapult phase\" feels misleading compared to how the concept is used in the literature. If I understand correctly, a damped oscillation of z about 0 would be considered to be in the catapult phase in this definition. However, in the original work of Lewkowycz et. al., it is used to describe an increase and then decrease in magnitude of the sharpness - with a single peak. Maybe \"non-monotonic convergent\" would be a better fit here?\n\nFigure 1 is too small - I'd recommend a 3 x 2 panel rather than a 5 x 1. This is one of the key figures in the paper so it should be easy to parse.\n\nIs there any way to analyze a coupled version of the system? Even 2 dimensions would be interesting to consider.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Z1QjqrMnuV", "reviewer": "Reviewer_BRxc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the work is the solid analysis of finite-step size gradient descent in a minimal solvable model. The identificaiton of precise phase boundaries lends it great interpretability\n\nThe main weakness is that the theory is not related so much to actual deep learning practice -- at least such relevance is insufficiently discussed. It would be great if the authors discuss in much more depth the machine learning relevance / implication of the theory, especially the five phases\n\nAlso, there are a few more specific problems that I would like to see addressed. See the requested changes section", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies the different optimization phases due to different learning rates in a minimal model. In particular, this work shows that there are 5 different phases, including the monotonic phase, catapult phase, periodic phase, chaotic phase, divergent phase", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. \"Notable,\" -> \"Notably\"\n\n2. Figure 1 is not quite visible. Please enlarge the figure and font sizes\n\n3. the citation is not correct English. For example, on page 2, the authors say \"Lyu (2022); Ahn (2022b)\", where the semicolon is not standard English. The authors should write \"Lyu (2022) and Ahn (2022b)\" instead.\n\n4. Page 10: \"A main take-away from our analysis and experiments so far is that gradient descent with large step-size behaves like stochastic gradient descent, except the randomness here is with respect to the orbit it converges to.\" I think the authors need to revise this sentence, which can be very misleading and confusing. In deep learning, stochastic gradient descent is more commonly used to refer to a special algorithm, where the randomness comes from the sampling of data points. Let me refer to this as the \"SGD.\" The authors did not show that GD is like SGD, but only that deterministic GD effectively resembles a gradient descent method with some special type of noise in it. This algorithm is definitely not SGD. Therefore, this sentence needs to be rewritten\n\n5. I think it greatly improves the manuscript if the authors discuss the related results in: https://arxiv.org/abs/2107.11774, where the authors solved for the phases and Lyapunov exponents of finite-step-size SGD in similar loss functions. How does the result here compare with the reference? Adding these discussion can be very nice", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yfEbR0UioJ", "reviewer": "Reviewer_Ja7a", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The introduction and section on related work is well-written and seems sufficiently complete. \n2. The theoretical results of Sections 2 and 3, and the underlying approach, is novel to the best of my knowledge and quite interesting as it shows that a wide array of behaviors can happen even for a simple model problem. \n\nWeaknesses: \n1. The experiments of Section 4, including all its figures, are often hard to follow and interpret. The captions of figures are sometimes very uninformative (e.g. Figure 3) and it is hard to keep track of what the plot labels 0, 1, 2, 3, 4 refer to, and which phases they belong to. In general, it is rather unclear what the main point is that the authors try to make here. \n2. From the introduction it seemed that there would be a big focus on the generalization performance when training in non-monotonic phases, but this seems almost completely absent in Section 4 (apart from a rather uninformative Figure 3). \n3. In general, I doubt that this paper in its current form will attract many readers from the broad ML community as the paper is not too accessible. It would benefit from some clear-cut recommendations and conclusions that can be read without going into all the notation and definitions introduced in Section 2. \n4. In Section 4.2 it is unclear whether ergodic trajectory averaging is an existing technique or a proposal. In addition, its definition is somewhat hidden in the middle of the text even though it is one of the two main contributions according to the introduction. \n5. Similarly, the connection with the EoS phenomenon is rather prominently announced in Section 2, yet rather hidden and succinct in Section 3. A clearer explanation of how sharpness and EoS are related to the experiments would be appreciated.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper investigates the dynamics of gradient descent (GD) in nonlinear problems, focusing on quadratic regression and quadratic activation neural networks. It proposes a simplified 1-dimensional model to analyze GD behavior with various step sizes. Results reveal five phases of GD dynamics: monotonic decrease, catapult, periodic oscillation, chaotic behavior, and divergence. The study integrates this analysis into specific regression models, including generalized phase retrieval and two-layer neural networks. Experimental evidence, both under orthogonal data assumptions and without, confirms the identified phases and the efficacy of ergodic trajectory averaging in stabilizing model performance. Overall, the paper contributes insights into GD behavior in nonlinear optimization problems and suggests directions for future research.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I recommend the authors to address the weaknesses above. The most important point being the presentation and results of the experiments in Section 4. Other than that, I invite the authors to proofread for typos such as 'catpults' (in multiple locations).", "broader_impact_concerns": "/", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes the dynamics of gradient descent on a quadratic regression model, revealing a discrete dynamical system whose behavior exhibits five distinct phases and whose properties are investigated in detail.

The reviewers are in agreement that the theoretical findings are technically sound. While there was some discussion about the significance of the findings and whether the narrow setting of analysis would be of interest to the community, ultimately the authors' response and the discussions led to the consensus that indeed the paper will be of significant interest. As such, I recommend acceptance.
Decision: Accept (poster)