From Stability to Chaos: Analyzing Gradient Descent Dynamics in Quadratic Regression

Overall, I have concerns about the applicability of the analysis to more general ML models, even those studied theoretically. It seems that the analysis relies heavily on both the factorizability of the specific models, as well as the quadratic activation function.

In addition, it's not clear to me which of the phases are relevant even for the training of the models discussed. Additional thoughts on this point are in the "Questions" section.

Most of the figures are hard to parse; more specifics can be found in the "Questions" section.

The discussion in Section 4.2 relating the dynamics to SGD are simply incorrect. See for example [1] for ways in which SGD in even a simple loss behaves quite differently from full batch GD.

[1] https://proceedings.neurips.cc/paper_files/paper/2022/hash/efcb76ac1df9231a24893a957fcb9001-Abstract-Conference.html

Although this paper could be interesting for specialist in dynamical system, its relevance in the context of machine learning could be limited:

• The dynamical system analyzed in the paper could be reduced from two problems, both with strong constraint (orthogonal data or fixed weights in the neural network). It appears to me that this is not the most representative problem in machine learning in general.
• It appears to me that the phases identified in this paper are related to the convergence of gradient descent. However, there is no comparison of the quantitative result in this paper to the ones in other papers studying the same problem using different methods (for example, papers surveyed in section 1.1, General results.) This makes the analysis in this paper isolated.
• The numerical experiment is performed using synthesized data instead of real ones.

Also, although the mathematical results in the main texts are clear, I find the experimental results hard to interpret. Notably:

• The performance of ergodic trajectory averaging is evaluated in synthesized data. It appears to me that this technique could be beneficial in realistic machine learning tasks. However, no such experiment is performed.
• I have problems interpreting Figure 4. I am not sure how I should interpret the legend in the figures, and I am not sure what message I should get from this figure.

I think this could be a strong submission, but its current message is somewhat unclear, specifically in its relation to other empirical work. My main concerns are about

• Its main message; the motivation for and the significance of the contribution for a general ML audience and empirical researchers
• And possibly related, the relationship between the submission and concepts originating from more empirical works, such as the edge of stability and catapults.

The paragraphs below provide specific examples of where I think the submission lacks in clarity, in the hope this feedback can help a revision to better convey the intended message of the submmission. I do not expect a detailled response to the points below. I would rather the discussion period focus on clarifying the motivation and significance aspects raised in the questions. If a revision adresses those issues, I will raise my score.

---

Motivation and significance for a more general audience

The introduction conveys the message that the dynamics of gradient descent on non-linear models are poorly understood, and that the quadratic model has been used in prior work. The related work seems sufficiently comprehensive. But I find it difficult to articulate what broader problem the submission is making progress towards.

The related work section focuses on highlighting the difference between existing work and this submission ("The result are not applicable to quadratic regression", do not "formally prove the existence of chaos", do not "characterize the 5 phases", "not applicable to the cubic map"). This does not show that the submission is "solving a problem", but rather presents a different analysis on a different settings. It might be an interesting mathematical result, but it is not clear what impact it would have on the broader ML community.

For example, from an optimization perspective, it is not clear that the later settings (periodic, chaotic and divergent) are relevant, as it's not converging regardless. Part of the broader goal might be the connections with unstable convergence, edge of stability and catapults, but if so those relationships are not clear after my reading.

Defining EOS and Catapults, specifying what is meant by similarity Places where the text states a similarity or relations between concepts, for example "Various patterns like catapult (also related to edge of stability)" (§1.1, pararagraph 2), would be improved by explicitly stating what the similarity/relation is. Is the wording referring to a specific relationship, or using it to convey the message that both exhibit non-monotonic behavior? It is not clear to me what the relation is, especially as those concepts come from empirical observations rather than formal definitions.

The working definition of catapult used by Lewkowycz et al. includes the idea that the sharpness decreases after a catapult. The definition of Edge of stability includes the idea that the sharpness rises to 2/step-size. To better place the submission in context and make specific claims, the submission should state such working definitions, as not every reader might hold the same understanding.

Such a working definition is somewhat implied by the use of the wording "catapult phase" for the convergent but non-monotonic phase, but I would encourage the more neutral non-monotonic phase. Although this phrasing mirrors the one used by Lewkowycz et al., it is implying that the defining behavior of this phase is the presence of catapults, which is not established. Calling it non-monotonic and stating that it this is the phase we can expect catapults to exist would be more accurate. Unless, of course, the point that the authors want to make is that this is the definition of catapults, but this does not appear to be the case from my reading.

Another point where what is meant by "relation" should be clarified is in"the chaotic dynamics (and related stochasticity)" (§1.1, par. General results) and "A main take-away from our analysis and experiments so far is that [GD] behaves like [SGD], except that the randomness here is with respect to the orbit it converges to" (§4.2) use "stochastic" and "random" in a way I do not recognise, as the mechanisms studied in the submission are deterministic.

Terminology The submission would benefit from being more careful in its choice of terminology. The two more noticeable examples were

• "large-order step-size", which is used in multiple places. The specific phrasing makes me think there might be a special definition of what "large-order" means, as opposed to the simpler "large", but no definition is provided. If there is no special meaning, I would suggest using "large".
• "Phase", which seems to refer to the behavior of the algorithm with different step-sizes. This might make sense to an audience coming from dynamical system or who have read the work of Lewkowycz et al. recently, but this term is overloaded. It is fine when used as in "phase transition", but in "training phase" it could be understood as referring to different times of one training procedure. I would suggest not using "training phase" and making this usage clear on first use for a more general ML audience.

Misc.

• The second and third paragraphs conflate two settings. The statements "Very much violating the classical case" (§1, paragraph 3) and "In fact, the necessity for larger step-sizes to expedite convergence and the ensuing chaotic behavior has also been observed empirically ... by Van Den Doel and Ascher (2012)" (§1.1, paragraph 2) appear misleading in the context of the submission, or should at least be modified to specify "the necessity for step-size schedules to include large step-sizes". As it stands, the statement applies to GD generally, including the setting studied in the paper, and it is not clear that observations in one setting transfer to the other(the two settings being [step-size schedules on (classes of functions such as smooth/strongly convex functions that include) quadratics leading to (almost) linear map updates] vs [non-linear maps with constant step-size]).
• The illustrations need improvements. The font size is too small to be readable. The figures with multiple lines (Fig. 3, 4) would benefit from having different line styles to be readable when printed.

In Section 3, the models they consider may be somewhat simplistic, and theirs further simplifying assumptions (orthogonality and quadratic activation functions) limit the introduction of complexity. For example, it would have been better if they have considered more “realistic” activation functions. It gives the impression that these examples are carefully taken to fit the model (cubic map).

I believe that this work has some merit, but I am unsure whether it exceeds the threshold for acceptance at ICLR.

The assumption of orthogonal data is an obvious weakness that weakens the theoretical contribution of the current paper. Even I believe it is reasonable to leave this as a future problem at the current stage, it is not clear that the technical barrier will not affect the results of dynamical systems in Theorem 2.1. Let me be specific.

The orthogonality assumption can be translated into following statement: let $F(**X**)$ be a mapping from $\mathbb{R}^{dn}$ to $\mathbb{R}^{\frac{n^2-n}{2}}$ defined by $F_1(**X**)=X_1^{\top}X_2$...$F_{\frac{n^2-n}{2}}(**X**)=X_{n-1}^{\top}X_n$ i.e., the upper triangle of $**X****X**^{\top}$ without diagonals. The orthogonality is equivalent to $**X**\in F^{-1}(0)$ where $0\in\mathbb{R}^{\frac{n^2-n}{2}}$. I have not found a detailed discussion on the relation between $d$ and $n$ (or I have missed it). Intuitively it is a crucial aspect to the results of this paper. Roughly speaking, let's say $dn>\frac{n^2-n}{2}$ (i.e. $d>\frac{n-1}{2}$), then what has been proved in Theorem 2.1 holds only if the data set is from a measure zero set ($F^{-1}(0)$ is a lower dimensional manifold, something like that, I did not check the regularity at $0$). I am not sure if we can perturb the current argument from a measure zero set, since analyzing interacting dynamics is a challenging and unexplored direction (Xu et al, 2022).

Therefore, from this perspective, we can only rigorously state: The main results holds if $d>\frac{n-1}{2}$ and the data matrix lies on a measure set, which is generically impossible.

More importantly, even we believe what is indicated in this paper, the requirement of $d>\frac{n-1}{2}$ is unnatural. The size of training set can be arbitrarily large and the dimension of data point is supposed to be fixed as long as the training task is determined. Thus the assumption of orthogonality is expected to capture the case of $n>>d$, but then there seems to be much more work ahead since the equations of defining $**X**\in F^{-1}(0)$ is over-determined and a careful analysis is needed. Unfortunately, this is completely ignored in this paper and the experiment does not capture this case since $d=100$ and $n=80$, or in the appendix, the non-orthogonal data set has not provided the choice of $d$.

Above observation is crucial in evaluating the importance of the results in this paper, from a machine learning perspective. Note that these concerns might be resolved or argued to be trivial, that will be great if true. The techniques used in this work is interesting and the paper has provided a profound connection between dynamical system and training process.