Chaotic Dynamics are Intrinsic to Neural Network Training with SGD
Authors: Luis Herrmann
Maximilian Granz
Tim Landgraf
Venue: NeurIPS 2022 Accept (2022)
Keywords: Optimization
Deep Learning
Chaos
Neural Networks
Curvature
Seconder Order Optimization
SGD
Hessian

Abstract: With the advent of deep learning over the last decade, a considerable amount of effort has gone into better understanding and enhancing Stochastic Gradient Descent so as to improve the performance and stability of artificial neural network training. Active research fields in this area include exploiting second order information of the loss landscape and improving the understanding of chaotic dynamics in optimization. This paper exploits the theoretical connection between the curvature of the loss landscape and chaotic dynamics in neural network training to propose a modified SGD ensuring non-chaotic training dynamics to study the importance thereof in NN training. Building on this, we present empirical evidence suggesting that the negative eigenspectrum - and thus directions of local chaos - cannot be removed from SGD without hurting training performance. Extending our empirical analysis to long-term chaos dynamics, we challenge the widespread understanding of convergence against a confined region in parameter space. Our results show that although chaotic network behavior is mostly confined to the initial training phase, models perturbed upon initialization do diverge at a slow pace even after reaching top training performance, and that their divergence can be modelled through a composition of a random walk and a linear divergence. The tools and insights developed as part of our work contribute to improving the understanding of neural network training dynamics and provide a basis for future improvements of optimization methods.

Chaotic Dynamics are Intrinsic to Neural Network Training with SGD
Luis M. Herrmann
Maximilian Granz
Center for Digital Health AG Roland Eils
FU BioRobotics Lab
Berlin Institute of Health
Freie Universität Berlin
Kapelle- Ufer 2, 10117 Berlin
Arnimallee 7, 14195 Berlin maximiliame maximmllan.granz0fuu -erffuuberriceec
luis herrmann@charitte...
Tim Landgraf
FU BioRobotics Lab
Freie Universität Berlin
Arnimallee 7, 14195 Berlin tim. wwwdgaanddaftt.. www.effluuue..oeeeeeeeeee
Abstract
With the advent of deep learning over the last decade, a considerable amount effort has gone into better understanding and enhancing Stochastic Gradient Descent so as to improve the performance and stability of artificial neural net- work training. Active research fields in this area include exploiting second order information of the loss landscape and improving the understanding of chaotic dynamics in optimization. This paper exploits the theoretical connection between the curvature of the loss landscape and chaotic dynamics in neural network training to propose modified SGD ensuring non-chaotic training dynamics to study the importance thereof in NN training. Building on this, we present empirical evidence suggesting that the negative eigenspectrum and thus directions of local chaos cannot be removed from SGD without hurting training performance. Extending our empirical analysis to long-term chaos dynamics, we challenge the widespread understanding of convergence against confined region in parameter space. Our results show that although chaotic network behavior is mostly confined to the initial training phase, models perturbed upon initialization do diverge slow pace even after reaching top training performance, and that their divergence can be modelled through composition of random walk and linear divergence. The tools and insights developed as part of our work contribute to improving the understanding of neural network training dynamics and provide basis for future improvements optimization methods.
Introduction
In the last decade, the advent of Deep Learning has to an explosive development powerful machine learning models capable of solving ever more complex problems. However, while numerous different architectures have been developed,
underlying optimization procedure Stochastic
Gradient Descent (SGD) (Robbins) 2007) and its descendants (Duchi al. 2011: Kingma and Ba 2017) has largely remained the same, with many aspects its nature not being fully understood yet. The role of second order dynamics one of those aspects, are chaotic dynamics of Artificial Neural Network (ANN) training, both being notoriously difficult to investigate due to the high computational cost involved. In this paper, we establish connection between the two aspects and generate new
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

insights by studying the intersection of these two through series of experiments conducted on small-sized models trained on natural datasets. Our main four contributions are follows:
1. By modeling ANN training with SGD as a time-discrete dynamical system, we propose a modified SGD algorithm ensuring non-chaotic training dynamics study the importance of chaos in ANN training.
2. We find empirical evidence suggesting that directions of negative curvature and thus local chaos cannot be removed without hurting the training performance of ANNs.
3. We show empirically that the network dynamics start out diverging exponentially at the beginning of the training but transition asymptotically against polynomial behaviour the model performance converges.
4. Elaborating on the previous aspect, we show that even the model training converges, the distance between similarly initialized models continues to grow at small pace, and that this behaviour can be modelled as sum of linear divergence and random walk.
2 Theoretical preliminaries
2.1 Definition of chaos
A popular saying characterizing the notion of chaos states that 'The flapping of a butterfly's wings can cause storm on the other side of the world., sometimes also briefly referenced as the butterfly effect. Formally, dynamical system is chaotic if it is (1) sensitive to initial conditions, (2) topologically transitive and (3) has periodic points of the system which are dense in state space (Skokos 2009, p.3, Def.1). Although complete analysis of chaos dynamics of dynamical system would encompass quantifying all three aforementioned properties, property (1) is the most relevant property for model optimization: Given a small deviation in the parameter state of a model at any point of the optimization, one should hope to obtain similar solution at the end of the optimization procedure, and by extension solution that performs similarly well both on training and validation data. Therefore, we use chaotic to refer to the sensitivity to initial conditions
2.2 Recap: Lyapunov Exponents
A common tool for characterizing chaos are Lyapunov exponents, which measure the evolution of displacement vectors over time. Consider dynamical system ((++1) f(o())), where g(t) the system state and f the dynamics function which determines how the system evolves over time. Given an initial, infinitesimally small displacement vector 50, s.t. 0/ = O, + 50,, the evolution of the displacement vector over time is given by the so-called tangent map. typically denoted du (() or (!) in matrix notation, satisfying
ag(t)
(0 = (1) (0)
() (0
(I)
where the matrix (9) is the Jacobian of the dynamics function at time I w.r.t. the state at the initial time step. When the state (()) depends only on the state the previous time point (tt-1) the action of the tangent map can be decomposed through application of the chain rule to
a
(+) = ( y(--))
(t-1)
(2)
(0((1))
with y being the Jacobian of the dynamics function at time step t. The Lyapunov exponents are defined as the eigenvalues (the Lyapunov spectrum) of the matrix
A (x) lim In (t) (() t-00
1
(3)
2t
which will refer to as Lyapunov matrix from now on. With this definition, we expect initial system perturbations AQ, to evolve according to
sl A A0,
'A more rigorous definition of chaos would require the system's 's invariant set be bounded.

---

where A1 is the maximum eigenvalue of the Lyapunov matrix, also called maximum Lyapunov Characteristic Exponent (mLCE). The respective eigenvector gives us the direction of maximum expansion of an initial displacement as the dynamic system evolves. Thus, the ml .CE can be used to characterize three different types of system dynamies:
1. 1 0: Nearby trajectories diverge exponentially (chaotic).
2. 21 0: Nearby trajectories diverge polynomially (edge-chaotic).
3. À < O: The distance of nearby trajectories upper-bounded.
Although the mLCE is sufficient to characterize the overall system dynamics, more fine-grained analysis can be obtained in natural manner by considering the full eigenvalue spectrum of the Lyapunov matrix, with the biggest eigenpair (λι, v1) giving us the "most chaotic" direction of the system evolution, (22, U2) the second- most chaotic, and so on assuming λ 2 λ N ... Av. Thus, for small initial perturbation (((0) ll") +eu, we expect the perturbation evolve approximately as dictated by the respective eigenpair as (t x exi Along any direction, we can expect the bound
e x - (t & xx10))=
(5)
to hold for sufficiently small s.t. the first order approximation
n (t) Y (sw)
(6)
of the training process at time step 4, where w is unit-length perturbation axis, is accurate.
2.3 Curvature and chaos
A neural network evolving according to SGD with learning rate 7 (without momentum) and trained with data batches (+)) at time step can be described by the equation
e () = glt 7g (g(0 2t-11))
(7)
where g (( (t-11) is the loss gradient w.r.t. to network parameters (tt-1) We show in Appendix A. and A.3 that the evolution of the tangent map without and with momentum can be described as
(++1) (I H (1) and (++ = - (Etn,gtt H (()).
(8)
respectively. This result shows that, discounting the effects of random batch sampling in SGD, the chaotic dynamics depend on the Hessian and thus the curvature of the loss landscape during training.
2.4 Local chaos and negative Hessian eigenvalue spectrum
Given the connections we established above, one could hope to improve the training performance of SGD by using second-order curvature information avoid/promote chaotic evolution of the system, assuming chaos to be detrimental/beneficaa for neural network training, e.g. by pruning the directions of maximum chaos from the gradient updates. Unfortunately, the Lyapunov matrix is practical for this purpose because it considers the chaos over the entire training up to the current time point, so can only inform us of chaotic evolution of the system a posteriori. To mitigate this problem, one can instead consider a greedy approach where at any given time step t, one looks at the finite-time Lyapunov matrix after a single time step, i.c.
A (L++1) In ( H
In In)
The eigenvalues of this matrix are called the Local Lyapunov Exponents (LLE) at time step t. Analogously the LCEs, we say the system is locally chaotic in the direction of eigenpair (A,, iff A; >> O. Using the fact that A (f,++1) has the same eigenvectors as H. we can relate the eigenspectrum of the Hessian to local chaotic dynamics follows:
3

---

Theorem 2.1. Given a neural network with N parameters. let H be the Hessian of the loss w.r.f.
network parameters, and let (), va);=1 be the Hessian's 's eigenpairs. Furthermore, let assume that the network is trained using SGD with learning rate r and no momentum. Then, the network's ss LLEs indicate locally chaotic training behaviour in the direction of vz if
X <<VV2,>> 2
(10)
7
For proof see Appendix A.5
Our result leads to the interesting observation that sufficiently large positive eigenvalues (as determined by the learning rate) imply locally chaotic training behaviour in SGD. More interestingly however, negative eigenvalues automatically lead to locally chaotic training behaviour.
2.5 Pruning chaotic updates
Since the eigenpairs (Ai, vz) of A (t,+11 give the directions of local chaos ordered by magnitude of the LLEs, we can remove the locally chaotic directions from the parameter updates in SGD by projecting the update vector onto non-locally-chane eigenvectors of A (t++1), More specifically:
Theorem 2.2. Given a neural network with Hessian H eigenpairs (A u. y of A (t,1+1) and
gradient updates A let there be k S N chaotic eigenpairs, i.e. A 2 ...Au > O. Suppose all chaotic components are removed through projection, leading to a modified update vector
Aō (V(((
V - - of (0)
(11)
Then, for training with SGD without momentum, the updated training dynamics are given by
(())) (t) g(
y(++) = -I- (0) (
(12)
and for sufficiently small variations of the initial parameters, the system is guaranteed not to have exponentially diverging orbits.
Proof is provided in Appendix A.7
3 Related Work
Since the full Lyapunov eigenspectrum is very expensive to calculate, previous work analyzing chaotic dynamics has so far mostly been limited either small networks or the largest mLCE, as investigated for instance by Das et al. 2000). Several investigations of chaos in feedforward ANNs such as those by Li 2019); Feng et al. (2019); Zhang et al. (202T) have focused on sensitivity of outputs w.r.t. the inputs rather than w.r.t. the training dynamics. modelling the network function itself as a discrete dynamical system. Recently, Vogt al. (0200) have calculated approximations of the Lyapunov exponents in RNNs and found correlations between better generalization (through lower validation loss) and smaller mLCE. To our knowledge, (Sasdelli et al. (202T) are the only ones to have investigated chaos dynamics in ANN training by SGD, but interestingly, they model ANN training by SGD as an approximately time-continuous dynamical system and not more accurately as a time-discrete dynamical system, thus arriving at slightly different theoretical results. While their theoretical work also links the biggest Lyapunov exponent to the most negative eigenpair of the network Hessian, positive eigenpairs which is not the case for time-discrete SGD without further assumptions. Unfortunately, they do not investigate how the directions of chaotic evolution in general and negative curvature in particular affect the training process.
indicators of chaos disappear in their considerations,
There is a considerable body of work on the eigenvalue spectra of ANN Hessians that can be tied into our theoretical findings, including an analysis of the full eigenvalue spectrum of a small 784-2-10 MLP for MNIST digit classification by (Sagun et al. (001)). Among other findings, the authors remark a two-phase distribution of eigenvalues with bulk centered around zero and large positive top eigenvalues (although not sufficiently big to satisfy X > 2/7).. as well as the presence of negative eigenvalues throughout the entire training. Further analysis of the negative spectrum by Alain et al. (2019) has indicated that individual negative eigenvalues average lead to the biggest improvement

---

of the loss in neural networks, but that current optimization algorithms appear not to be good at optimizing in directions of negative curvature. This finding was extended by Gur-An et al. (2018). who found that the gradient of the Hessian mostly resides in the space spanned by the top Hessian eigenvectors and does not mix with the bulk, suggesting a marginal importance of the negative Hessian eigenpairs for the training dynamics.
To the best of our knowledge, we are the first to use time-discrete modelling of training dynamics by SGD to derive predictions of how curvature affects chaotic dynamics, and the first to explore extensively using the full Hessian spectrum at every training step how directions of different curvature affect the dynamics of the training process. This extensive investigation provides us with empirical evidence allowing us to establish a novel connection between chaotic training dynamics and the training performance.
4 Experiments
Taking into account all aspects discussed so far, we can make the following claims:
1. Due to the presence of negative eigenvalues in all training steps and assuming the MLP for MNIST is representative model for Feedforward ANNs, ANNS can be expected to have positive LLEs at every training step.
2. Unless the positive top eigenvalues of the Hessian are sufficiently big to satisfy À 2/7 which was not the case for the MLP for MNIST investigated by [Sagun al. (2017) the chaotic behaviour of ANN training by SGD is exclusively determined by negative eigenvalues in the bulk.
What remains to be verified experimentally is whether the negative eigenspectrum has little or at worst detrimental effect the training performance, suggested by the findings of Alain et al. (2019) and Gur-Ari et al. (018)) or if it is actually benificial to the performance of ANN training.
Methods
The code for all our experiments is written in Python using the Pytorch framework Paszke et al. 2017), and available at GitHub P For the calculation the Hessians, we use O2Grad
(Anonymous) 2022). package on top of Pytorch that enables faster calculation of the Hessian of small ANNS using 2nd order backpropagation. As datasets, we use USPS (Hull 1994) and FashionMNIST (Xao al. 2017) (with images subsampled to 16 x 16 pixels), since these datasets contain sufficiently dow-dimensional, natural data to allow for the calculation of the Hessian and its cigenvalue decomposition every training step, both for 784-20-10 10 MLP and for small 2D CNN. To modify the parameter updates of the model as proposed in Theorem 2.2 we use the Pytorch implementation of SGD and alter it slightly implement an own class CGD (Chaos-sensitive Gradient Descent) with the ability to filter parts of the eigenvalue spectrum.
Our experiments were run single GPU nodes of a system featuring an AMD Ryzen Threadripper 1950X processor, 4x Nvidia GeForce RTX 2080 TI GPUs (IGG VRAM) and 64GB RAM, as well as on a second system featuring an Intel(R) Core(TM) i5-8600K, Nvidia GeForce GTX 1080 Ti (11GB VRAM) and an Nvidia Titan XP (12GB VRAM) and 32GB of RAM. Both systems run on Debian Debian GNU/Linux 11 (bullseye).
4.1 Local Chaos Investigation
Chaotic direction pruning deteriorates training performance In order to verify the impact of pruning different components on the training performance, we equipped CGD with the ability to filter (1.) chaotic eigenpairs, (2.) only negative eigenpairs and (3.) only positive eigenpairs, and out of those, filter only the & largest by absolute value or prune k at random. As our results for the MLP on USPS in Figure D show, models trained without pruning (i.e. regular SGD) reach high/low training accuracies/losses, while the models trained with CGD and pruning of chaotic eigenvalues get stuck at much lower/higher training accuracies/losses. The same phenomenon can be observed for validation losses/accuracies. and on the 2D CNN and FashionMNIST (see Appendix B.I. This is remarkable because seems to suggest that locally chaotic training behaviour is essential for ANN training in order to quickly achieve reasonable training performance and generalization, and that ANNs trained
5

---

1.0
0.8
2.0
Accuracy
0.6
1.5
0.2
0.5
0.0
0.0
5000
10000
15000 20000 25000 30000 35000
5000
10000
15000 20000 25000 30000 35000 Step
Step
mip 0.0
mip usps sgd
mip usps egd 0.0 chaotic
mip usps cgo 0.0 chaotic
mip usps cgd pos
mip usps cgo 0,0 pos
mip
mlp
(a)
(h)
Figure Line plots of the (a) accuracy and (b) loss curves for an MLP (relu activation) trained on the USPS dataset without momentum. The models trained with CGD use pruning of the full chaotic, negative or positive Hessian spectrum at every time step. The smoothed, solid lines are obtained through local averaging (window size 50) of the respective sequential data. Pruning of the full positive spectrum (red) only has a small effect on training performance, while negative and chaotic pruning strongly limits the network's ability to learn.
2.5
2.0
Accuracy
0.6
1.5
0.4
1.0
0.0
0.5
2500
5000
7500
15000
17500
5000
7500
17500
Step
mip - usps - -.d--.0-/
mlp - usps - sgo 0.0 usps
usps cgd
mip usps c.d.d.ddoo0 0.0 5k
mip usps egd 0.0 5k
mlp usps cgd 0.0 10k
mip usps cgd 10k
(b)
Figure 2: Line plots of the (a) accuracy and (b) loss curves for an MLP trained on the USPS dataset without momentum. We use sigmoid activation because this slows down convergence and makes the splitting of performance metrics better visible. The models trained with CGD use pruning of the full chaotic Hessian spectrum at every time step after the onset of pruning after 2k, Sk and 10k time steps. The smoothed, solid lines are obtained through local averaging (window size 50) of the respective sequential data). The accuracy and loss curves start diverging from the baseline curve when pruning starts.
by SGD are hardly able to learn in the absence of locally chaotic directions. To make sure this is not an effect occurring only in the early stages of training by SGD, we execute several runs where the pruning of locally chaotic directions starts later in the training. As we can see in Figure 2 training loss and accuracy start improving slower rate after the onset of pruning, suggesting that the models learn far more slowly as soon the pruning of chaotic directions is engaged.
Negative Hessian eigenspectrum drives training by SGD Interestingly, the number of positive chaotic eigenvalues of the Hessian is effectively throughout most of the training (see Appendix

---

This means that the chaotic directions pruned during the training come almost exclusively from the negative eigenpairs the Hessian, which is in line with our previously formulated expectation. However, the extent to which pruning of the negative eigenvalues hinders the training of the network suggests that the negative eigenspectrum of the Hessian is far more important to the training dynamics of neural networks than previously believed by Alain et al. (019). To better understand the role of the negative and positive eigenspectrum of the Hessian, we perform several runs where we prune (I.) the entire negative eigenspectrum and (2.) the entire positive eigenspectrum of the Hessian.
B.2
As expected, our results in Figure | for pruning the full negative eigenspectrum coincide with the results for pruning the full chaotic eigenspectrum of the Hessian: Models trained with pruning of the full negative eigenspectrum of the Hessian reach far lower training performance than models trained with regular SGD. However, pruning the full positive eigenspectrum of the Hessian only has a small impact on the training performance: Although the accuracy/loss reaches slightly lower/higher levels than for SGD without pruning. the ANNs trained in this way fare much better than their counterparts with negative pruning. We observe this behaviour across different datasets and models (see Appendix B.I.
These empirical results lead to the following conclusions:
1. The negative eigenvalue spectrum of the Hessian contains important information about the optimization problem since it cannot be discarded without hurting training performance.
2. The positive eigenvalue spectrum of the Hessian contains less important information about the optimization since discarding it has less impact on the training.
3. Since the negative eigenspectrum induces locally chaotic training dynamics, locally chaotic training dynamics are inevitable in SGD without hurting training performance.
These appear to contradict the findings of Gur-Ari et al. (018),, who observe that the overlap of the gradient is biggest with the positive eigenpairs of the Hessian observation that confirm in our experiments (see Appendix B.2). The apparent contradiction can be resolved through simplified model of ANN training by SGD, in which negative curvature precedes positive curvature: Directions of negative curvature indicate high potential for future loss improvement from moving along those axes, while directions of positive curvature indicate proximity a local minimum along said axes, and thus reduced potential for loss improvement (see Appendix B.3.II Removing the negative components of the Hessian from the gradient eliminates possibilities for big future improvements of the loss and may only allow the optimizer to finish converging in the directions where it was moving anyway, hence why the network is still able to decrease its loss even when the negative eigenspectrum is pruned, though at a smaller pace. This also matches our observation that the count of negative/possiive Hessian eigenvalues decreases/increases as the training proceeds (see Appendix B.
Note that this model does not explain why the gradient overlap with axes of positive curvature is greater than with axes of negative curvature, only why the former and a high importance of the negative eigenvalues can exist at the same time: Negative curvature important during an initial discovery phase, and positive curvature during a subsequent exploitation phase.
4.2 Global Chaos Investigation
Our experiments so far have relied on local quantification of chaos via the LLEs. Next, we extend our investigations to global chaos using finite-time Lyapunov exponents to quantify chaos over longer time spans.
Finite-time Lyapunov exponents In order to better understand long-term chaotic dynamics, we calculate the tangent maps from equation S at every time step t and apply eigenvalue decomposition
on the resulting finite-time Lyapunov matrix A (*) to end up with the corresponding finite-time Lyapunov eigenspectrum. The Lyapunov exponents are above
the beginning of the training and converge against 0 as training progresses (see C.T). suggesting the evolution is initially chaotic, but edge-chaotic in the time limits. Note that since the exponents do not drop below O, we should expect models with similar initializations to continue diverging even after they reach top performance.
7

---

Perturbation analysis The divergence behavior can be further explored by utilizing the Lyapunov eigenspace to perturb models along determined directions. As discussed in section 2.2, this space describes the global divergence directions locally around an initial set of parameters. In our perturba- tion experiments, we train a model A until convergence time Tome and calculate the Lyapunov eigenpairs. We then use those eigenpairs to apply initial perturbations onto several models BI.... B,, initialized with the same random seed as A, and observe how their parameters evolve compared to A along the perturbation axes. The latter are derived from the finite-time subspaces
Vehnosic (t) == {u E Eig(A X) X > 0},
V Vinn chaotic (t) = (o E Eig(A (9, A) <
according 5 perturbation strategies: We take (1) the top eigenvector of A (N), the maximally chaotic direction and (2) the bottom eigenvector as maximally non-chaotic direction. Further- more we consider linear combination of vectors sampled randomly from (3) Vehaotio (N) and (4) Vnon-chaoric (N) that describe random chaotic and random non-chaotic directions, respectively. Fi- nally, we also sample (5) completely random direction for comparison. The initial parameters are perturbed along the respective directions, where we test different magnitudes 61,...& for each direction to make sure we consider perturbation magnitudes that are in agreement with the locality required by our theoretical preliminaries (see equation (
Ghorbani al. 2019) finds that the loss landscape thus using the finite-time Lyapunov matrix at a time point t = Teome where the training sufficiently converged should provide an acceptable approximation. Therefore, the tangent map y() at the next time step > Teone + and its eigenspace would barely change.
local minimum is almost flat (H xs 0) and
(Tcomu++ +1) = =11==01--0 -H (Teone) ( (Tcomo) & (Teocc))
(13)
Although we also see a similar distribution of the Hessian eigenspectrum, we do not observe a full convergence of the Hessian to zero (see Appendix B.2). However, the subspaces of chaotic and
non-chaotic eigenvectors do stabilise towards the end of the training (see Appendix C.2) making a
finite-time analysis with the above perturbation strategies sound.
Distance results Figure 3 (a) shows the distance evolution of an MLP without momentum on USPS and FashionMNIST. For comparison between model architectures and analysis of momentum, see Appendix C33 In general, the maximal divergence (empirically s 1 in Figure 3 (a). up to 12 in further experiments in Appendix C.3) lies in range of the expected distance of standard initialized
models in Pytorch (LeCun et al. 2012 for the duration of our experiments:
Egi, 02, "..VE. (1 02112) R 6.38,
where k; are the number of input features of layer i (see Appendix A.S Still, surprising result that the distances do not seem to saturate for the duration of our experiments, which would be expected for a valley of finite size. In fact, we are still reaching similar performance with perturbations magnitudes up to E < 7.5, and only for 2 10 there seems to be a significant drop in performance (see Appendix
Theoretically, the observed distance evolution can be explained as composition of linear divergence and random walk. Suppose the gradients g (f), have distance components w (t), ut((t) with constant distance a := [mn (t) (2)
( w.( (1)
(14)
and noise components defined by n (t), (t) E (0, o²). Then the distance Al(t) between two sets of parameters o3 and o evolves as follows:
Al(t)= ~ E Ei w2(s)) + E' 72
n2(3))[]] = Val2 + 3t, (15)
with 3 := 2Do (see Appendix A.10). For smaller t, this term is still influenced by the random walk term 3t whereas for large the at term dominates and leads to linear divergence. We give examples of fitting this baseline the data in Figure bb).
Unfortunately, we were unable explore whether the model distances saturate for a sufficiently long time evolution, which should be the case if the models end up in bounded loss valley, whereas an
8

---

1.75
0.8
1.50
12-Distance
0.6
L2 2-Distance
1.25
1.00
0.4
0.75
0.50
0.0
0.00
2500
5000
7500
10000 Steps
12500 15000 17500
2500
5000
7500
10000 12500 15000 17500 Steps
mis
Imwatt
Hipp 0.00 E780s
Imreat 0.0-p-00---0000
baseline chats
US55 mepp -andom
frisst 0.0 random
baseline
uepe nic -.D--chas
frseet mip 2.D chase
beseline chass
u426 mig 0.D-mer me4 Shees
mim -.D- m.p-mux, chees
uup- D.0 me-
beselie chess
1... mp beasing comrargel
.... mil bruiiing convarged
0.0 bounds
Empirical perturbation evolution
(b) Theoretical modelling
Figure 3: Euclidean distance between baseline MLP and perturbed MLP trained with SGD (without momentum). We use 5 different strategies for computing initial perturbations of norm = 0.1 using the Lyapunov eigenspace of a model trained beyond convergence of training accuracy. Darker lines represent perturbation directions which we expect to lead to higher model divergence. The observed divergence in
USPS (green) and on FashionMNIST (blue) increases convergence of the training accuracy across all perturbation directions. As shown in (b) for the USPS curves, the divergence can be approximated through a function att + 3t (red) within the observed time range. The choice of for the trajectories in agreement with the theoretical bounds (purple) predicted by the maximum/minimuun LCE x (t)/Aw (t) calculated at every time step.
after
unbounded loss valley would allow for model divergence to be unbounded as well. A more conclusive analysis the matter will have to be provided by further studies. In any case, the evolution of training dynamics from chaotic to edge-chaotic in the parameter domain interesting given that ANNs transition from unchaotic to chaotic in the input domain (Feng al. 2019), suggesting there may be a complementary relation between the two.
Choice of perturbation length We present the experiments with perturbation length of : 0.1 as we do not find that the approximation holds for larger e. Surprisingly, we see a similar behavior for smaller perturbation lengths < 0.1: the smaller the differences get, the more randomly they behave. We argue that this phenomenon is caused by noise, probably induced by numerical error. For further analysis Appendix
Theoretical bounds In Figure (b). we present the theoretical bounds derived from the maximal
and minimal LCE (see equation 5 Both bounds hold for choice of 0.1 over the entirety of
our experiments where the lower bound converges always to zero (see Appendix C.5) The upper bound, the other hand, can be utilized without conducting the full scale of our experiment. Note that for this purpose, it suffices to calculate peapuuov--eecto-proouue which can be realized through a deesiaanvectoo-prrduee for which faster algorithms exist (Pearlmutter 1994..
measure of maximal divergence of single training
5 Discussion
Although we have done our best perform the pruning experiments on common datasets and model architectures, the experiments are currently difficult to extend to higher-dimensional datasets and Hessian at every training step. For similar reasons, we have not studied the effect of BatchNorm (Toffe and Szegedy 2015) and skip connections (He al. 2015) yet, although we intend to do this later time. The high computational cost also limits training time used in analysis and it could be that aspects don't apply for longer
models due to the high expense of calculating

---

training times, e.g. our model for perturbed network divergence (see (b)). In this context, it would also be interesting investigate possible connections between the edge-chaotic dynamics later in training and overfitting, but we mainly limited the scope of our analysis to training metrics. Another aspect requiring further inquiry why the model divergence not always ordered according to our expectations for different perturbation strategies.
In this paper, we have shown that chaotic dynamics of ANN training by SGD are linked negative curvature. We have found strong evidence that using negative curvature information is essential for training, and we have concluded that chaotic behaviour inherent to training by SGD. Although globally chaotic dynamics are mostly present at the beginning of the training behaviour and fade towards the end of training, we have shown that models with slightly different initializations continue to diverge linearly in parameter space and provided model for this behavior. Our work provides a theoretical starting point and tools for further investigations aiming to advance the understanding of chaos in ANN training. In this context, we especially recommend investigating the divergence of trajectories the end of the training and exploring possible connections to generalization capability (see A.I. as well as the relation between chaos in the input and in the parameter domain.
6 Acknowledgements
We are deeply thankful to Julius Upmeier zu Belzen and Roland Eils from the Berlin Institute of Health for providing the main author with the time and support to write the paper. We would also like to thank Leon Sixt from the Biorobotics Lab and Martin Aleksandrov from the Dahlem Center for Machine Learning and Roboties for giving us valuable advice for the preparation and rebuttal of the paper. Maximilian Granz was supported by the Selsa-Neuman-SShoolaa also grateful Nvidia for providing us with Titan Xp and to ZEDAT for granting their HPC system. Finally, we would like to thank the anonymous reviewers of our paper for taking their time to review our work and for supplying interesting points of discussion.
by the state of Berlin. We access
References
Alain, G., Roux, N. I.., and Manzagol, P.-A. (2019). Negative eigenvalues of the hessian in deep neural networks.
Anonymous (2022). O2Grad - A Pytorch Extension for 2nd Order Backpropagation. Draft attached in the Supplementary Material.
Das, A., Roy, A., and Das, P. (2000). Chaos in a three dimensional neural network. Applied Mathematical Modelling, 24(7):511-522
Duchi, J., Hazan, E., and Singer, Y. (2011). Adaptive subgradient methods for online learning and stochastic optimization. 12:2121-2159.
Feng, I.., Zhang, I.., and Lai, C. H. (2019). Optimal machine intelligence at the edge of chaos.
Ghorbani, B., Krishnan, S., and Xiao, Y. (2019). An investigation into neural net optimization via hessian eigenvalue density. CoRR, Abs/1990.10159,
Gur-Ari, G., Roberts, D. A., and Dyer, E. (2018). Gradient descent happens in a tiny subspace.
He, K., Zhang, X., Ren, S., and Sun, (2015). Deep residual learning for image recognition. CoRR, abs/1512.03385.
Hull, J. (1994). A database for handwritten text recognition research. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5):550-554.
loffe, S. and Szegedy, C. (2015). Batch normalization: Accelerating deep network training by reducing internal covariate shift. CoRR, abs/1502.03167.
Kingma, D. and Ba, J. (2017). Adam: method for stochastic optimization.
LeCun, A., Bottou, I.., Orr, G. B., and Müller, K.-R. (2012). Efficient BackProp, pages 9- Springer Berlin Heidelberg, Berlin, Heidelberg.
10

---

Li, H. (2019). Analysis on the nonlinear dynamics of deep neural networks: Topological entropy and chaos.
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A. (2017). Automatic differentiation in pytorch.
Pearlmutter, B. A. (1994). Fast Exact Multiplication by the Hessian. Neural Computation, 6(1):147- 160.
Robbins, H. H. (2007). A stochastic approximation method. Annals of Mathematical Statistics, 22:400-407.
Sagun, L., Bottou, L., and LeCun, (2017). Eigenvalues the hessian in deep learning: Singularity and beyond.
Sasdelli, M., Ajanthan, T., Chin, T.-J,, and Carneiro, G. (2021). A chaos theory approach to understand neural network optimization. 2021 Digital Image Computing: Techniques and Applications (DICTA), pages 1-10.
Skokos, C. (2009). The Iyapunov characteristic exponents and their computation. Lecture Notes in Physics, page 63-135.
Vogt, R., Touzel, M. P., Shlizerman, E., and Lajoic, G. (2020). On lyapunov exponents for rnns: Understanding information propagation using dynamical systems tools. CoRR, 1411/2006.14223.
Xiao, H., Rasul, K., and Vollgraf, R. (2017). Fashion-mnist: novel image dataset for benchmarking machine learning algorithms.
Zhang. L., Feng, L., Chen, K., and Lai, C. H. (2021). Edge of chaos as guiding principle for modern neural network training.


Reviews:
[{"review_id": "knFLnAhFGZY", "reviewer": "Reviewer_tUai", "summary": "This paper studies neural network training dynamics via the lens of the Hessian eigenspectrum. In particular, the authors show that the chaotic dynamics in neural network training are largely determined by the negative eigenvalue of the Hessian. Furthermore, the authors empirically demonstrate that the negative eigenvalue direction is important for making progress in training.", "questions": "See the weaknesses mentioned above.\n\nOther questions and suggestions:\n- I suggest the authors clarify the main advantages of Lyapunov exponent analysis over existing analyses. If I understand correctly, most results derived in section 2 can be obtained in a toy quadratic model.\n- To scale up to larger datasets, the authors could check out literature about the Lanczos algorithm and its stochastic version (see e.g. [1]).\n\n\n\nReferences:    \n1. An Investigation into Neural Net Optimization via Hessian Eigenvalue Density", "limitations": "The authors discussed the limitations at the end of the paper. I don't see any negative societal impact of this work as it is an \"understanding\" paper.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The discussion about the role of negative eigenspectrum in optimization is interesting. \n\nWeaknesses:\n- The theoretical model of Lyapunov exponent offers no further insights into the training dynamics compared to standard quadratic models or linearized models.\n- The fact that negative eigenvalues would lead to chaotic dynamics is well known in the optimization community. Basically, I feel the whole section 2 is just background and I don't really know what's the contribution of this work.\n- All experiments are done in very toy settings. The authors only conducted experiments on FashionMNIST and USPS, which I don't think very convincing.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "B_8VFvAVBpx", "reviewer": "Reviewer_yYv3", "summary": "The authors conduct a thorough hessian-related analysis of training dynamics in neural network training in several medium-sized tasks.  They analyze the eigenspectrum of the hessian throughout training, and investigate the effects of screening descent directions by various criteria related to properties of the hessian.  Additionally, they provide a bevy of theoretical results on their studied dynamics.", "questions": "There is a sense in which components of this work are somewhat tautological, and other results might be slightly overstated.  As an example, the authors state:\n\n```\nIn this paper, we have shown that chaotic dynamics of ANN training by SGD are linked to negative curvature.\n```\n\nThe authors seem to have _defined_ “presence of chaotic dynamics” to be “local hessian has negative eigenvalues”.  Consider the following alternative: it could be the case that essentially parabolic regions of the loss landscape are stitched together by a small number of hyperbolic descent directions.  Restricting oneself to only the strictly positive eigenvalues then somewhat definitionally traps the performance of a model to within some locally-minimum basin, whereas restricting oneself to the negative-hessian directions is more akin to a kind of truncated BFGS iteration, where descent to the lowest minima is never truly ruled out.\n\nIt is not, then, anything particularly “chaotic” about the presence of these negative eigenvalues—only that they’re conduits between more locally quadratic regions.  This would likewise explain why learning trajectories tend to correlate more with the positive curative directions.\n\nDo the authors have evidence that there is something more “chaotic” going on here, other than eigenvalues being negative?\n\nAs for the author’s definition of “chaos”:\n```\nGiven a small deviation in the parameter state of a model at any point of the optimization, one should hope to obtain a similar solution at the end of the optimization procedure, and by extension a solution that performs similarly well both on training and validation data. Therefore, we use chaotic to refer to the sensitivity to initial conditions.\n```\nIt might be that the community simply needs a different word to describe what is going on with neural network training.  A model whose training dynamics were purely diffusive would also seem to satisfy the author’s notion of “chaotic”.  I suppose we can identify “sensitive to initial conditions” with “chaotic”, but this might be overloading the word.\n\nRegardless, stepping back for a moment and taking a more thousand foot view, here: it seems that the author’s primary result is that “performance of neural networks degrades when we restrict neural networks to not be able to descend along directions with negative hessian eigenvalues”.  Do the authors agree with this characterization?  Do the authors agree that restricting learning dynamics to positive-semi-definite subspaces of the hessian traps the learning dynamics near a local minimum / saddle point?", "limitations": "Beyond the comments above, many of the training curves in the paper seem not to be fully converged, but given the extreme numerical expense of running this analysis, I don’t think it’s the end of the world.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: while studying hessian eigenspectra is not a _new_ idea, the approach considered by the authors does appear novel (i.e., screening of particular directions during training), and has yielded interesting results\nQuality/Clarity: The paper is quite high quality and clear\nSignificance: I expect this paper to be significant, as it gestures at negative components of the hessian being more important than folks otherwise suspected.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1PWKSMKVgfH", "reviewer": "Reviewer_LtWX", "summary": "This manuscript mainly investigates a theoretical link between the curvature of the loss function and (local) chaotic dynamics in neural networks training through demonstrating the negative eigenvalue spectrum of the Hessian. Their empirical evidence verifies that the negative eigenspectrum and so the directions of local chaos cannot be removed from SGD without hurting training performance. ", "questions": "Some effects of the local chaotic dynamics on the training performance is discussed through some experiments. However, I would like to see:  can the relation between local and long-term chaos be proven (mathematically) to demonstrate some problematic effects of local chaos on the training theoretically as well?\n", "limitations": "The authors have discussed the limitations of the work and there is no potential negative societal impact.\n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe main idea of the paper is interesting and it is nice to see a paper that is theoretically principled, and goes about formalizing some dynamical behavior arising in neural networks training. \n\n**Weaknesses**\n\n I checked most of the proofs in detail and spot some errors; for instance:\n\n1) It seems that Theorem 2.1 cannot hold in a general case (as is), and some assumptions on the Hessian of the loss ($H$) are required to be considered. More clear, in the proof of this theorem (Appendix A.5, line 522) it is mentioned that \"Since all eigenvalues of $(I − \\gamma H)^2$ are positive, the matrix is positive definite\". But, all eigenvalues of $(I − \\gamma H)^2$ are not necessarily positive; e.g. when $\\gamma H$ has some eigenvalues equal to $1$. I mean let $H $ be a matrix such that  $\\det(I − \\gamma H) = 0$, then $(I − \\gamma H)^2$ can have zero eigenvalues. For example, let $H= diag(\\frac{1}{\\gamma}, b, c)$, then $(I − \\gamma H)^2 $ obviously has at least one zero eigenvalue. This affects the rest of the proof.\n\n2)  Appendix A.1: In Eq. (19), from right to left, the second term should be \"$\\frac{\\partial \\theta_i^{(t)}}{\\partial \\theta_j^{(t)}}$\".\n\n3) Appendix A.2: It seems that Eq. (22) is written for $t=0$? So it needs to be modified for $t=1$. Also is there the assumption $v(0)=0$ for obtaining Eq. (22)?\n\nThere are also some minor issues and typos: \n\n- The definition of chaotic systems (line 47) is for \"smooth\" dynamical systems (DS), but (it is well known that) it is no longer true for \"non-smooth\" DS such as RNNs with ReLU activation function (as piecewise linear DS). Especially, since piecewise linear DS can observe a specific kind of chaos called \"Robust Chaos\" in the absence of periodic windows and coexisting attractors; please see for instance the paper by Banerjee, Yorke and Grebogi: https://doi.org/10.1103/PhysRevLett.80.3049.\n\n- Positive mLCE is a standard signature of chaos provided that the system's invariant set is **bounded** (as in this case two nearby orbits separate exponentially fast, but at the same time their mutual separation cannot go to infinity so that there are also folds). Otherwise a positive mLCE could be related to a diverging orbit which is not chaotic. Therefore, the authors should consider the assumption of \"boundedness\" and perhaps add it to Section 2.2.\n\n- Is the reference \" Robbins, H. E. (2007). A stochastic approximation method. Annals of Mathematical Statistics, 22:400–407\" (line 369) correct? I couldn't find such a reference. \n\n- Line 89, A.3 ---> A.2", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept