A Chaos Theory Approach to Understand Neural Network Optimization
Authors: Michele Sasdelli
Thalaiyasingam Ajanthan
Tat-Jun Chin
Gustavo Carneiro
Venue:  (2021)
Keywords: learning theory
stochastic gradient descent
deep learning
neural networks
dynamical systems
chaos theory
Lyapunov exponents

Abstract: Despite the complicated structure of modern deep neural network architectures, they are still optimized with algorithms based on Stochastic Gradient Descent (SGD). However, the reason behind the effectiveness of SGD is not well understood, making its study an active research area. In this paper, we formulate deep neural network optimization as a dynamical system and show that the rigorous theory developed to study chaotic systems can be useful to understand SGD and its variants. In particular, we first observe that the inverse of the instability timescale of SGD optimization, represented by the largest Lyapunov exponent, corresponds to the most negative eigenvalue of the Hessian of the loss. This observation enables the introduction of an efficient method to estimate the largest eigenvalue of the Hessian. Then, we empirically show that for a large range of learning rates, SGD traverses the loss landscape across regions with largest eigenvalue of the Hessian similar to the inverse of the learning rate. This explains why effective learning rates can be found to be within a large range of values and shows that SGD implicitly uses the largest eigenvalue of the Hessian while traversing the loss landscape. This sheds some light on the effectiveness of SGD over more sophisticated second-order methods. We also propose a quasi-Newton method that dynamically estimates an optimal learning rate for the optimization of deep learning models. We demonstrate that our observations and methods are robust across different architectures and loss functions on CIFAR-10 dataset.

Under review as a conference paper at ICLR 2021
A CHAOS THEORY APPROACH TO UNDERSTAND NEURAL NETWORK OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Despite the complicated structure of modern deep neural network architectures, they are still optimized with algorithms based on Stochastic Gradient Descent (SGD). However, the reason behind the effectiveness of SGD is not well under- stood, making its study an active research area. In this paper, we formulate deep neural network optimization as a dynamical system and show that the rigorous the- ory developed to study chaotic systems can be useful to understand SGD and its variants. In particular, we first observe that the inverse of the instability timescale of SGD optimization, represented by the largest Lyapunov exponent, corresponds to the most negative eigenvalue of the Hessian of the loss. This observation en- ables the introduction of an efficient method to estimate the largest eigenvalue the Hessian. Then, we empirically show that for a large range of learning rates, SGD Iraverses the loss landscupe across regions with largest eigenvalue of the Hessian similar to the inverse of the learning rate. This explains why effee- tive learning rates can be found to be within large range of values and shows that SGD implicitly uses the largest eigenvalue of the Hessian while traversing the loss landscape. This sheds some light the effectiveness of SGD more so- phisticated second-ordes methods. We also propose a quasi-Newton method that dynamically estimates an optimal learning rate for the optimization of deep learn- ing models. We demonstrate that our observations and methods are robust across different architectures and loss functions on CIFAR-10 dataset.
INTRODUCTION
An interesting observation from current deep learning research is that classification and regression accuracy gains seem to be achieved from the intricacy of the underlying models rather than the optimization algorithm used for their training. Actually, the facto choice for the optimization
algorithm is still the classic Stochastic Gradient Descent (SGD) algorithm (Robbins & Monro 1951)
with minor modifications (Duchi et al., 2011 Sutskever et al.) 2013] Kingma & Bal 2014). Even though several sophisticated second-order and quasi-Newton methods (Martens] [010 Martens & Grosse 2015 Berahas et al.) 2019) have been introduced, first-order methods remain popular and none of them seem to outperform SGD with carefully tuned learning rate schedule (Hardt et al.) 2016). This indicates that SGD (or in general first-order methods) probably has some intrinsic prop- erties that make it effective optimize over-parametrized deep neural networks. Despite various attempts to explain such phenomenon (Chaudhari & Soatto 2018 Keskar et al., 2016 Kleinberg al., 2018), little is understood about the effectiveness of SGD over sophisticated second-order optimization methods.
In this paper, we argue that chaos theory (Sprott Sproti 2003) a useful approach to understand the neural network optimization based on SGD. The basic idea is to view neural network optimization as a dynamical system where the SGD update equation maps from the space of learnable parameters to itself and describes the evolution of the system over time. Once the evolution is defined, the rich theory developed to study chaotic dynamical systems can be leveraged to analyze and understand SGD and its variants. In essence, chaos theory enables to study the evolution of the learnable parameters (i.e., the optimization trajectory) in order to understand the training behavior over large time scales (i.e., number of iterations).

---

Under review as a conference paper at ICLR 2021
In particular, we focus on understanding the influence of the learning rate the SGD optimization trajectory. First, by observing that the Lyapunov exponent of SGD is the most negative eigenvalue of the Hessian of the loss, introduce efficient and accurate method to estimate the loss curvature. Then, we empirically show that for a range of learning rate schedules, SGD traverses the optimization landscape across regions with largest eigenvalue of the Hessian similar to the inverse of the learning rate. This demonstrates that at a specific time step, performing SGD update is similar to performing a quasi-Newton step, considering only the largest eigenvalue of the Hessian of the loss. This, for the first time, sheds some light on the effectiveness of SGD over more sophisticated second-orde order methods and corroborates the observation that SGD robustly converges for variety of learning rate schedules (Sun 2019).
Furthermore, as pointed out in (LeCun et al., 1993), the inverse of the estimated curvature can be used as the learning rate when applying SGD to a new dataset or architecture. Hence, we can set up a "feedback" system where the quasi-Newton optimal learning rate calculated dynamically based on the current largest eigenvalue of the Hessian (curvature), and the learning rate is consequently adjusted during the training, allowing a "parameter free" stochastic gradient descent optimization. conducted on CIFAR-10 dataset to demonstrate that our observations across a variety of models, including a simple linear model regression and more modern deep neural network architectures, trained with both cross entropy and mean square error loss functions.
The experiments
robust
2 CHAOS THEORY FOR NEURAL NETWORK OPTIMIZATION
In recent years, several papers have used dynamical systems to study theoretical aspects of deep learning optimization (Liu & Theodorou 2019). Essentially, this is achieved by defining the opti- mization of deep neural networks as the evolution of parameters over time. In particular, a dynamical system progresses according to map function that describes how the system evolves in a specific time step. In the case of deep neural network optimization, this map function is defined from the space of parameters into itself. By describing the system evolution using such map function, is possible to leverage the mathematical machinery of dynamical systems. For instance, viewing SGD as discrete approximation of a continuous stochastic differential equations, allowed [Li et al. (217)) and An et al. (2018) to propose adaptive SGD algorithms. Furthermore, dynamical systems enabled LeCun et al. (1993) to relate learning rate with the inverse of the local Hessian in a quasi- Newton optimization framework. Our paper also uses dynamical systems to study deep learning optimization, but differently from all methods above, we rely on chaos theory.
Chaos theory (Sprott & Sprot, 2003) studies the evolution of dynamical systems over large time scales and can categorize systems into chaotic or non chaotic. Under some simplifying but still general assumptions, chaotic systems are bounded and have strong dependence on the initial con- ditions. This means that chaotic systems evolving from different starting points that are within a relatively small region around a particular reference point, will diverge exponentially during the evolution process, where the amount of time taken for this divergence to happen is defined as the chaotic timescale. This chaotic timescale imposes a limit on our ability to predict the future state distribution of dynamical system. In fact, the distribution of the future state, which have evolved for more than few times the chaotic timescale, cannot be distinguished from random distributions, even when the system is fully deterministic. We apply concepts from chaos theory to improve our current understanding of the optimization of deep neural networks.
More specifically, we describe how to use standard chaos theory techniques to efficiently calculate the leading (positive and negative) eigenvalues of the Hessian of the loss function. With these eigenvalues we measure, in turn, the loss function curvature, which can be used to study the behavior of first-order optimization methods, such as SGD (Robbins & Monro 1951). In particular, with this technique we formulate an explanation for the empirical robustness of SGD to the choice of learning rate and its scheduling function, and we investigate a method (based on quasi-Newtor second order method) for dynamically finding the optimal learning rate during the optimization of deep neural networks. Such automated and dynamic estimation of optimal learning rate can lift a significant burden from the manual definition of learning rate schedules in deep learning optimization.
2

---

Under review as a conference paper at ICLR 2021
2.1 LYAPUNOV EXPONENTS
In chaos theory, the Lyapunov exponents define the divergence rate of infinitesimally close trajecto- ries, and the inverse of the largest Lyapunov exponent is the timescale that corresponds to the onset of chaos into the system. Two arbitrarily close initial conditions generate two solutions that diverge with time. Under the assumption that the map function of the system is differentiable, one ob- serves this divergence for short time window, it grows exponentially. If the initial divergence (()) is made smaller, the time window can be made larger (t + oo). The largest Lyapunov exponent is measure of the growth of the divergence (t) in the direction (()) = q(0)/ (O)]I with the largest growth (max along the trajectory, as in
(t(())l
À max lim 4(0) 00 [q(()]] -00 [[([)]]
lim
log
In this paper, we rely on the local finite size Lyapunov exponent. In this context, local in time means that there is no limit to infinity for in equation D- instead, it is an average over a constant time window t. Finite size means keeping the difference in parameter space fixed as a small constant with |qlll = Aq (i.e., no limit ||q]] - 0 in equation I. Using finite size allows the study of the dynamic system at a specific spatial scale (for a comprehensive review, see (Cencini & Vulpiani, 2013)) corresponding to the eigenvalues of the Hessian of a spatially smoothed version of the loss (or equivalently, to the numerical second derivative with a finite delta). When this analysis is used to study the Hessian, this is equivalent to calculating the local numerical second derivative. We found empirically that the results do not depend on the Ag parameter within a large range of values.
We will show in Sec. 3 that this timescale (i.e., the Lyapunov exponent) corresponds to the most negative eigenvalue of the Hessian of the loss, when optimizing deep neural networks with SGD. Intuitively, small difference in the initial condition will amplify exponentially in the directions with negative second derivatives and will dampen in directions with positive second derivatives. Empirically, we find that the chaotic timescales in effective training of deep neural networks short (in the order of tens of iterations) when compared with the time of one epoch (i.e., the total number of iterations in one epoch). We also find that there are multiple unstable directions throughout the training. i.e., the system is hyper-chaotic.
2.2 LYAPUNOV EXPONENTS FOR GD AND SGD
In this section we derive the formula to compute the largest Lyapunov exponents for Gradient De- scent (GD) following (Sprott & Sprott 2003). We first show that the largest Lyapunov exponent corresponds to the most negative eigenvalue of the Hessian of the loss and provide an algorithm to efficiently compute it. This will be later extended to calculate the largest (or in general the top-k) eigenvalue of the Hessian in section 3 For simplicity of the exposition, in this section initially consider the non-stochastic setting. Also, for the results of this section to hold, we assume that the Hessian of the loss does not change quickly through time, and it does not change quickly along the optimization trajectory compared to the chaotic time scale. These assumptions can easily be checked a posteriori, and we will show how overcome this (potential) limitation in section 3
Let 0 be the vector of learnable parameters of the deep neural network, L(.) be the loss function, and a > 0 be the learning rate. The gradient descent step at iteration / is written as:
(L. 0, d0
0.11
where the update step A = -a dL/d0. In the limit of small steps the formulation is equivalent to a Partial Differential Equation (PDE)
d0 AL(O)
dt
00
Integrating equation 3 gives the evolution of the system, which is equivalent to training the neural network.
To compute the chaotic time scale (i.c. the inverse of the Lyapumov exponent), one needs to analyze the difference in evolution of GD at two arbitrarily close initial points. To this end, we consider
3

---

Under review as a conference paper at ICLR 2021
small perturbation qu added to the initial weights 0g. For this perturbed starting point 0u qu. the PDE becomes:
d q) = a
a
(4)
dt
d0
In the limit of small q, considering the first order Taylor approximation of the above equation and subtracting equation 3 we obtain:
(T(
dq
80
(5)
dt
00
Then, integrating equation [ obtain the evolution of the perturbation under GD:
q(t) = exp (aa 8 L(
9o
(6)
002
This remains true as long as q(t) remains small, where the definition of small depends on the prop- erties of L. We consider the decomposition of qu as a sum of its projections on the eigenspace the Hessian of the loss (with the Hessian being represented at the exponent of the formula in equation 6 In this space, the projection of qo along the direction corresponding one growing the fastest. Starting with a random Qo. the direction of q that becomes dominant after sufficient time aligned with the eigenvector of the largest eigenvalue of the matrix at the exponent, and the growth rate of is equal to the corresponding eigenvalue.
the largest eigenvalue the
Measuring this growth rate provides a simple and linear (in the number of parameters) method to measure the leading eigenvalue. This procedure represents the calculation of the largest Lyapunov exponent, i.e,, the largest eigenvalue (An) of the matrix -a- Due to the minus sign, this corresponds to the smallest eigenvalue (hx) of the Hessian of the loss (H L More precisely. the smallest eigenvalue of the Hessian and the largest Lyapunov exponent are related hn -No/a. o. For non-convex losses, hx is the most negative eigenvalue and the matching eigenvector corresponds to the most unstable direction of the optimization of the loss.
Once (t) is aligned with the largest eigenvector, equation 6
becomes
qt + At) exp(An (t)
The algorithm calculate Ån requires normalizing the length of q each step keep the increment "small". This reference distance is equivalent to the choice of the step size for the calculation of finite difference based second derivative. In dynamical systems terminology this is called calculating the finite-size Lyapunov exponent. Now, the largest Lyapunov exponent is obtained by iterating the following two steps:
(1q(t+ At)l
Ao +- log
/AI,
[[q(t)]
|(((()]
q At) + q(t + At)
1|g(t + At)l
where ||-|| denotes the L.2 norm and At denotes the time step. One could see that the computation of the largest Lyapunov exponent is analogous to the power method compute the largest eigenvalue of a given matrix. This idea can be easily extended to compute the top-k Lyapunov exponents following the idea of Benettin et al. (1980). Please refer the appendix C
SGD can be described with the same approach, with the loss function replaced by I.(O,w) w) where w random variables that describe which images are picked in each minibatch, the data augmentation used, and in principle any other random process engineered in the network. We note that chaos theory is fully applicable with equivalent results in such general stochastic setting (Arnold) 1988). In the subsequent analysis we will leverage this and work with SGD. Finally, we demonstrate how to extend the method explained in the current section to compute the Lyapunov exponent for SGD with momentum in Appendix B
3 CALCULATING THE LARGEST EIGENVALUE OF THE LOCAL HESSIAN
In section 2.2 we discussed how one can estimate the local largest Lyapumov exponent of the SGD map, which, under some common conditions, corresponds the most negative eigenvalue of the
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Computation of the largest eigenvalue of the Hessian
Input : L: loss function, D: training set, 0 E I point to compute the eigenvalue, b: batch size,
Aq: size for Lyapunov exponent
Output: ho: the largest eigenvalue of the Hessian of L at 0
To E R.W.
Qo Tooll
Small perturbation of size Aq
0g + 0. 01 + 0 + qu
3 4-1
Initialization
while not converged do
D2 ((x, yb )
D
Sample a mini-batch
Oo 0g + 8 Do)
Gradient ascent on Oo
80
0, + 0 + B 8OL , (a)
> Gradient ascent on 0
80
[1:0 - 0b)l
A - log
Lyapunov exponent iteration
Aq
8 +
b Re-scale the learning rate
0, + 0 + (0) - -0)
Ag
0. x
b Re-centering
T 11
end
ho
Eigenvalue from Lyapunov exponent
3
Hessian of the loss at the same point. While most negative cigenvalues can be used to analyze the existence of saddle points and training instability, in this paper we are interested in computing the largest eigenvalue of the Hessian. Note that the largest eigenvalue corresponds to a theoretical upper bound the usable learning rate, under quasi-Newton approximation (LeCun et al., [993). Therefore, by efficiently computing it, we intend to understand the relationship between the SGD optimization trajectory and the learning rate.
To compute the largest (or more generally, the top-k) eigenvalues, we need to redefine our map function. The idea is to eliminate the negative sign and use the gradient ascent equation. For this map, the largest Lyapunov exponent corresponds to the largest eigenvalue of the Hessian and the matching eigenvector corresponds to the direction of most instability. We would like to clarify that gradient ascent is used as map function to estimate the largest eigenvalue of the local Hessian particular point in the parameter space. This approach can be employed at any given point, especially at the points in the optimization trajectory, where any algorithm can be chosen for the optimization.
With gradient ascent map, the PDE corresponding to equation can be written as (note the missing minus sign):
dq 0t
L
= 002
where 3 > 0 the learning rate for gradient ascent (we use different notation to distinguish it from obtain an exponential form, where
the SGD learning rate a). Similarly, we can integrate equation 9 the dominating exponential corresponds to the largest eigenvalue. However, this time it corresponds to the largest eigenvalue of the Hessian of the loss denoted by hg-
Since we intend to estimate the Lyapunov exponent every point in the optimization trajectory, we now discuss how to accelerate the convergence of the Lyapunov exponent computation. To this end, we set up our chaotic map as a control problem, where we optimize the learning rate 3 used for our gradient ascent step such that the convergence of the eigenvector is the fastest but still stable. This obtained by setting 3 such that the corresponding Lyapunov exponent controlled to stay close to one. It does not need to be necessarily one, but it needs to be a value of the order of unity. In practice, the learning rate for the next step is re-scaled by the Lyapunov exponent computed in the current step and this numerical procedure ensures that the Lyapunov exponent quickly converges to one.
Our final algorithm to compute the largest eigenvalue of the Hessian a given point is summarized in Algorithm [ In practice, this algorithm converges within a couple of iterations and the conver- gence criterion checks the fluctuation in À around 1. As will be discussed in section 5 in comparison
5

---

Under review as a conference paper at ICLR 2021
to (LeCun al. 1993), algorithm automatically tunes the learning rate 3 to compute the largest eigenvalue quickly and effectively eliminates one parammer used in (LeCun et al., 1993). This enables to run Algorithm T at every step to understand the optimization trajectory of SGD and similarly to (LeCun et al. 1993), the largest eigenvalue can he used to automatically set the learning rate of SGD in the NewtinNewton framework.
3.1 QUASI-NEWTON METHOD
Quasi-Newtor method is an effective approach that utilizes approximate second-order information to improve gradient descent methods. The basic idea is to keep track of an estimate of the Hessian matrix and modify the gradient descent step (Nocedal Wright 2006). Formally, at iteration I, the quasi-Newton method can be written
1.-1 dl.
0++1 = 0, -,
-B,"
(10)
d0
where B, denotes the estimate of the Hessian matrix iteration t.
In this paper, we estimate the largest eigenvalue, so the matrix B, takes the form of h where h6 is the largest eigenvalue of the Hessian at O, and I is the identity matrix. This is the simplest form of quasi-Newton method which effectively uses 1/h as the learning rate at iteration t. This replaces hand-engineered learning rate schedules and could be beneficial when applying SGD to new problems. If top-k largest eigenvalues are estimated as discussed in the appendix, a more sophisticated quasi-Newton approach could be employed.
EXPERIMENTS
All experiments based on the CIFAR-10 dataset that has 10 classes with 5000 32x32 pixel training images per class, and 1000 32x32 pixel testing images per class. For all experiments, we use batch size of 512 and weight decay of 5 10-4 and standard data augmentation techniques. We use a difference of x 10 (Aq in Algorithm I in parameter space for calculating the Lyapunov exponent (results do not depend on changing this in a wide range of values). To show that the behavior of the method does not depend on particular loss functions, we run the experiments using the softmax crossentropy and mean square error loss functions. The following models are trained with the first two CIFAR-10 classes (planes and cars): 1) linear model with mean square error that is, a least square regression; 2) Multi-Layer Perceptron (MLP) with three hidden layers; 3) a LeNetl (LeCun et al. 1998) with relu activations; and 4) a small ResNet with two residual blocks. We also test the larger ResNet18 (He et al. (0166) using all ten CIFAR-10 classes. In all experiments, we SGD without momentum. One iteration is typically sufficient in the control algorithm to compute hn at each optimization step, however, noise À can be alleviated by running more than iteration for each step.
Figure ssoow the losses for the MLP training with fixed and cyclic (Smith & Topin 2019) learning rates. Notice how the inverse of the curvature (orange curve), measured with the controlled Lya- punov exponent, naturally adapts to both the fixed and cyclic learning rates. Since quasi-Newton methods would require the learning rate be equal or similar to the inverse of the second derivative, we speculate that this discovered behavior is useful to explain the successful training of deep neural networks using first-order methods, such as SGD.
Furthermore, we investigate hyper-paratt parameter free training based on the measured curvature in Figure 2 We first run our algorithm to measure the curvature on the initialization point, without training. This is to ensure convergence of the eigenvector and avoid a "cold" start. Then, when the starting curvature is known, we set the learning rate to this value and start the training. We keep a simple exponential running average of the curvature to remove noise (this is equivalent to choose At the calculation of the Lyapunov exponent), and set the learning rate (red curve in Fig. 2 to this value dynamically. Empirically. guaranteeing a decrease in the loss. We show extensive experiments with analogous results on other architectures in the Appendix
find that this "optimal" learning rate gradually decreases,

---

Under review as a conference paper at ICLR 2021
MLP crosse crossentropy
MLP crossentropy
MLP crossentropy
10
100
10"
10
k,
10.1
4x 10-1
3x
1..th.a
20-1
Ir. 1...m..
10-1
10
10
10-2
A
1/0g
1.0g
1/fte
loss
1055
10
10
107
10f
10f
10
107
10'
epachs
epochs
spochs
ResNetO crossentropy
ResNetO crossentropy
ResNeto crossentropy
10
109
100
10
1r, 15,20h33
3
-10-1
lnse
Ir 1..1h.1
10-4
Sr. 1.1.h.4.
10-3
10
10-4
10
10
3.8%
10--
1,0%
loss
loss
10-2
10-3
l0ss
10
20
10a
10
10
10
epochs
epochs
MLP mse
MLP mse
MLP mse
10
10011
10"1
1.011
A1
l0ss
l0ss
10
10-4
10-1
10
10-1
3/hg
17h
1/hgg
1005
1055
1055
10
107
10
100 101
100 10:
Figure 1: Lyapunov exponent À (blue), inverse curvature from leading eigenvalue 1/ho (orange), learning rate a (red), and loss (green) curves with cross entropy loss for MLP (top), tiny Reseee (middle) and MLP with mean squared error (bottom) on a two-class CIFARIO problem, with con- stant (0.1, 1, 0.3 first two columns, respectively) and cyclic (third column) learning rate schedules. The corresponding experiments on the other setups are in the appendix. Note that 1/ho closely follows a in all cases.
5 RELATED WORK
It is interesting how on one hand the design of neural network architectures became progressively more complicated over the years (LeCun al., 1990 Krizhevsky et al., 2012 Simonyan & Zisser- man 2014 He et al., 2016). But on the other hand, the most popular optimization strategies are still relatively simple and have not substantially changed (Bottou al. 2018). In fact, the most effec- tive approaches are still based SGD with minor variations (Ruder 2016). usually developed to increase their robustness or efficiency. Still, simple SGD often produces tfate-ofthhe-ee results that competitive and often even better (Hardt et al. 2016) than more advanced optimization tech- niques based on second-order methods or pseudo/quasi Newton approaches (Bordes et al.) 2009) Sohl-Dickstein et al., (0014) or on adaptive methods (Wilson et al. [2017). Another interesting point about first order methods is their robustness to learning rate choice and schedules (Sun) 2019). evi- denced by several methods that study efficient automatic learning rates for SGD (Schaul & LeCun 2013 Schaul et al., 2013 Li et al.) 2017). Hence, there should be some explanation for why simple first-order optimization methods (Ruder, 2016) work so well on large-scale problems with systems containing large number of parameters, such as deep neural networks.
similar question has been asked by LeCun al. (1993), who proposed a method to calculate the largest eigenvalue of the Hessian of the loss using the power method. To make it work along the SGD training, LeCun et al. (1993) designs a running average of the estimate of the eigenvector. Their idea similar to ours, but our approach has the advantage of being free of the scheduling of the parameter that characterizes the running average. This advantage stems from the Lyapumov exponents analysis presented in our paper, which is one of the first steps in the exploration of the intersection between chaos theory and deep learning. Furthermore, since the largest eigenvalue of the Hessian can be used estimate for the smoothness coefficient of the loss function, our approach could improve the
7

---

Under review as a conference paper at ICLR 2021
MLP crossentropy
LoNet_ like. relu crossentropy
ResNet18 crossentropy
100
10a
10
1: 1..hhaa
10.1
4x 10-1
10-1
10
10
It. 1...m.a
10-1
10
loss
10
2x 10
10
4 10
10-4
A
1/0g
1/0
1/fte
loss
logs
3x 10
10
10-3
10
10
10
10
10-
10'
10'
10a
epachs
epechs
MLP mse
LeNet_ like relu mse
ResNet1 8 mse
10
10a
10-4
1x10
1.ImA
10
10
10
loss
loss
2x10
10:
10-1
10-2
10
loss
10
100 10a 10
10-
1ccs
107
10
10-1
100
101
10a
cpochs
apachs
Figure 2: Lyapunov exponent (blue), inverse curvature from leading eigenvalue 1/ho (orange), learning rate a (red), and loss (green) curves for MLP (column 1), LeNetl (column 2). and ResNet18 (column 3) with softmax cross entropy loss (top) and mean squared loss (bottom) on CIFARIO trained using our quasi-Newton method, i.e., using the estimated 1/ho as the learning rate. While & is trained on the full CIFARIO other networks are trained on a two class CIFARIO prob- lem. The training begins once the estimation of ho at the initialization is stable. In all our experi- ments, the training is stable and loss decreases monotonically.
smoothness coefficient estimation (Santurkar et al. 2018 and help methods that rely on it (Zhang et al. 2019 Lee et al. 2020).
We believe that there are many other topics in this intersection that are worth exploring, such as the use of deep neural networks predict the behavior of chaotic dynamical systems (Pathak al.)
2018) or the exploration of neural networks as a dynamical system (Liu & Theodorou 9011 Schoen- holz et al. 2016). We align with works that view SGD as an approximation of stochastic differential equations Chaudhari & Soatto| 2018) or that improve the understanding of empirical and theoretical properties SGD (Ma al.] 2018 Keskar et al.) 2016 Bassily et al.) [220;; Kleinberg et al. [018]] Chaudhari & Soatto| (018). particularly regarding the influence of batch size and learning rate to generalization (He et al. 2019 Jastrzebski et al. 2017 Smith et al. (017))
6 DISCUSSION AND CONCLUSION
In this work, we chaos theory approach design of the largest cigenvalue ho of the Hessian of the loss function. Our proposed method is efficient because it is linear in the number of parameters and can be in parallel to the optimization. This efficiency allows us to study the dynamical evolution of ho during training and discover that 1 1/o converges the chosen learning rate a. Moreover, we noticed that we could assign a to large range of values and still have an effective training. Hence, setting the learning rate a with a quasi- Newton optimization largely superfluous for deep neural networks because of the convergence of 1 1/ho to a. This means that SGD traverses the loss function along a path that has the correct curvature according to second-order optimization. Finally, we have some indications that the convergence of 1/ho towards is necessary for a successful training. Therefore, our approach could be used to narrow down the initial range of usable learning rates or to design learning rates schedules on new problems.
method for the efficient estimation
Although we did not discuss generalization in this paper, we observe that for a fixed batch size, 1/ho follows the learning rate a. This means that if larger learning rate is used towards the convergence, a wider optimum will be attained, and wider minima are usually attributed to better generaliza- tion (Keskar et al. 2016). This corroborates with previous results that show that the ratio between batch size and learning rate has a negative correlation to generalization (He et al. 2019: Dastrzebski et al. 2017 Smith et al. 2017).
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Jing An, Jianfeng Lu, and Lexing Ying. Stochastic modified equations for the asynchronous stochas- tic gradient descent. Information and Inference: Journal of the IMA, 2018.
Ludwig Arnol. Lyapunov exponents of nonlinear stochastic systems. In Nonlinear Stochastic Dynamic Engineering Systems, pp. 181-201. Springer, 1988.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent nonsmooth convex losses. arXiv preprint arXiv:2006.06914 2020.
Giancarlo Benettin, Luigi Galgani, Antonio Giorgilli, and Jean-Maric Strelcyn. Lyapunov char- acteristic exponents for smooth dynamical systems and for hamiltonian systems; method for computing all of them. part 1: Theory. Meccanica, 15(1):9-20, 1980.
Albert S Berahas, Majid Jahani, and Martin Takáč. Quasi-newton methods for deep learning: Forget the past, just sample. arXiv preprint arXiv:1901.0999) 2019.
Antoine Bordes, Léon Bottou, and Patrick Gallinari. Sgd-qn: Careful quasi-newton stochastic gra- dient descent. 2009.
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311 2018.
Massimo Cencini and Angelo Vulpiani. Finite size Yуарunov exponent: review on applications. Journal of Physics A: Mathematical and Theoretical, 46(25):254019, 2013.
Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference, converges limit cycles for deep networks. In 2018 Information Theory and Applications Work- shop (ITA), pp. 1-10. IEEE, 2018.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1224-1234. PMLR, 2016.
Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems, pp. 1143-1152, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Stanistaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint 17X1::1711.04225 2017.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: /609, 04836 2016.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint arXiv:1412.6988 2014.
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? arXiv preprint
2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.

---

Under review as a conference paper at ICLR 2021
Yann LeCun, Bernhard E Boser, John Denker, Donnie Henderson, Richard E Howard, Wayne E Hubbard, and Lawrence Jackel. Handwritten digit recognition with a back-pree prop-patagttiion net- work. In Advances in neural information processing systems, pp. 396-404, 1990.
Yann LeCun, Patrice Simard, and Barak Pearlmutter. Automatic learning rate maximization by on-line estimation of the hessian's 's eigenvectors. In Advances in nearal information processing systems, pp. 156-163, 1993.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228--2224 1998.
Namhoon Lee, Thalaiyasingam Ajanthan, Philip HS Torr, and Martin Jaggi. Understanding the effects of data parallelism and sparsity on neural network training. CoRR, 2020.
Qianxiao Li, Cheng Tai, and Weinan. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference on Machine Learning, pp. 2101-2110, 2017.
Guan-Horng Liu and Evangelos Theodorou. Deep learning theory review: An optimal control and dynamical systems perspective. arXiv preprint arXiv: 2019.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effec-
tiveness of sgd in modern wer-parametrized learning. In International Conference on Machine Learning, pp. 3325-3334. PMLR, 2018.
James Martens. Deep learning via hessian-free optimization. In ICML, volume 27, pp. 735-742, 2010.
James Martens and Roger Grosse. Optimizing neural networks with krotecker-factored approximate curvature. In International conference on machine learning, pp. 2408-2417, 2015.
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science &amp; Business Media, 2006.
Jaideep Pathak, Alexander Wikner, Rebeckah Fussell, Sarthak Chandra, Brian Hunt, Michelle Girvan, and Edward Ott. Hybrid forecasting of chaotic processes: Using machine learning in conjunction with a knowledge-based model. Chaos: An Interdisciplinary Journal of Nonlinear Science, 28(4):041101, 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Sebastian Ruder. An overview of gradient descent optimization algorithms. arXiv preprint arXiv:1609.04777, 2016.
Shibani Santurkar, Dimitris Tsipras, Andrew llyas, and Aleksander Madry. How does batch malization help optimization? In Advances in Neural Information Processing Systems, pp. 2483- 2493, 2018.
Tom Schaul and Yann LeCun. Adaptive learning rates and parallelization for stochastic, sparse, non-smooth gradients. arXiv preprint arXiv: 2013.
Tom Schaul, Sixin Zhang, and Yann LeCun. No more pesky learning rates. In International Con- ference Machine Learning, pp. 343-351, 2013.
Samuel S Schoenholz, Justin Gilmer, Surya Ganguli, and Jascha Sohl-Dickstein. Deep information propagation. arXiv preprint arXiv: /6/ 1.01232, 2016.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXivv1409.1556 2014.
Leslie N Smith and Nicholay Topin. Super-convergence: Very fast training of neural networks using large learning rates. In Artificial Intelligence and Machine Learning for Multi Domain Operations Applications, volume 1 11006, pp. 1100612. International Society for Opties and Photonics, 2019.
10

---

Under review as a conference paper at ICLR 2021
Samuel L Smith, Pieter-Jan Kindermans, Chris Ying, and Quoc V Le. Don't decay the learning rate, increase the batch size. arXiv preprint arXiv:1711.00480 2017.
Jascha Sibl-Dickstein, Ben Poole, and Surya Ganguli. Fast scaeesccae optimization by unifying stochastic gradient and quasi-newton methods. In International Conference on Muchine Learning. pp. 604-612, 2014.
Julien Clinton Sprott and Julien Sprott. Chaos and time-series analysis, volume 69. Citeseer, 2003.
Ruoyu Sun. Optimization for deep learning: theory and algorithms. arXiv preprint
arXiv: 2019.
Iyya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International conference on machine learning, pp. 1139-1149 2013.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in neural information pro-
cessing systems, pp. 4148-4158, 2017.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelcrates training: A theoretical justification for adaptivity. arXiv preprint 1rXiv:1905.1188) 2019.
A
APPENDIX
B
SGD+MOMENTUM
With SGD+momentum the analysis is conceptually similar, but mathematically more complicated.
SGD+momentum:
0.41 ap:+1 + O.,
0L
Pe+1 mp: 00
We can rewrite:
0.11 0, api+l.
0L
Pe+1 Pt = -(1 m m)pp
00
In the limit of small steps:
00
ap.
Øt
0p
0L
(1 m p
Ot
00
Incidentally, in this formulation becomes clear that (1 m) is equivalent to a drag term particle of mass under the motion of potential L.
we define a vector length 2.V describing the phase space, where N is the dimension of the parameter space 0 (or p):
0 (0.p).
The phase space describes both the status of the network and the optimizer's accumulated gradients. We can rewrite the system of equations above in a compact form:
0
al
0
aL
-(1 m)
where 7 is the identity matrix of size N.

---

Under review as a conference paper at ICLR 2021
Just like in the case of SGD, we obtain the equation for the evolution of perturbation in the phase space (we call q(t)), and integrate it over which gives:
0
al
OL
-(1
m) qo
g(t) =
We need find the eigenvalues of the matrix at the exponent of the formula, hence we need solve an equation of the form A AI| = 0, where |-| represents the determinant:
8 80
-(1 m) - xI = 0.
Rewriting:
-XX
aI
L
(-(1 m)
A)I 0.
a02
A
B D
The Shur's determinant identity
DI| A- - -D- gives:
00
X--(1 m) A)I
0,
002
which is formula of the form H - hT 0. This means that the eigenvalues of the hessian of the loss (h) are related the Lyapunov exponents by the formula:
h 2 A(1 m)
a
Similarly the SGD) case, the largest À gives the smallest h. The final formula in this case becomes:
bN 13 + Ao m)
C LYAPUNOV EXPONENT SPECTRUM
Our curvature estimation idea can be easily extended estimate the top-k (negative or positive) eigenvalues of the Hessian. We calculate the first Lyapunov exponents using the orthogonalization procedure described by Benettin al. (1980). To calculate the second Lyapunov exponent, it is enough to keep track of second "small" increment vector (t) evolved in exactly the same way as (t), with an additional orthogonalization step (Benettin et al. 1980
(t + (t At) (2) + At) q(t + At)
11 A!)
to be done before the corresponding normalization step. The procedure easy to generalize to further eigenvalues.
The results typically show a shallow dependence of the value with eigenvalue number (Figure 3 If this holds true in general, calculating additional eigenvalues will be of limited usefulness for improving optimization.
D ADDITIONAL EXPERIMENTS
In this section we present additional experiments of the same type shown in section done with different architectures and loss functions. 4n rate. Figure 7 shows experiments with cyclic learning rate. And Figures X and 9 show the full set of experiments mentioning how it trains also with the linear model regression (Figure 9 upper-left). Figure IO shows experiments with the larger ResNet18 architecture and the 10 classes of CIFAR1O. The same behavior as in the main paper is consistently observed across different architectures/losses. It is possible to mitigate the noise in X, and consequently in 1/he. by increasing the number of iterations of Algorithm]] [ As explained in the main text, 1/ ho cannot follow a when it is too small (c.g. Fig that is, the curvature cannot go to infinity.
experiments with constant learning
two classes CIFAR10 with our quasi-newton method for SGD. It is worth
12

---

Under review as a conference paper at ICLR 2021
10.0
95
90
Figure 3: The first 14 cigenvalues of the Hessian of the loss averaged over the first epoch.
MLP crossentropy
LeNet like_relu relu crossentropy
100
10
10
10-1
6 10
10-1
Ir. 1/hhhh A
10-1
Ir. 1.1/hh
4 10
loss
loss
4 10
3x
10
10
1/ho
2x
1/hg
3 x 10-1
loss
loss
10-3
10-3
100
10
100
10
epochs
epochs MLP mse
ResNetO crossentropy
10
10
10-1
Ir, 1/h. A
10-1
1/1/hh
10-1
loss
loss
10-2
À
10-2
10-1
1/ho
1/ha
a
loss
10-2
a
loss
10-3
10º
10a
10"
101
epochs
epochs
LeNet like relu mse
ResNetO mse
100
10
10a
4 10-1
3 10-1
1/h1/hh A
10-1
Ir. 1/h, A
10-1
loss
100
loss
2 10-1
10-2
10-2
1/ho
17h0
10-1
a
loss
10-1
loss
10-3
10-3
10a
10
100
10
epochs
epochs
Figure 4: MLP, LeNet1, tinyResNet with square error and soft- max entropy loss trained on a two classes cifar10 with a constant learning rate (0.05). The linear model regression does not train in this setup.
13

---

Under review as a conference paper at ICLR 2021
MLP crossentropy
LeNet like_relu crossentropy
10
6 10-1
10
x 10-1
4 10-1
10-1
Ir. 1/1m ...
1001
3x 10-1
loss
4
loss
Ir.
10-2
À
2 10
10-2
x 10-1
1/ho
1/ho
loss
loss
10
10
10"
10
10
10a
epochs
epochs MLP mse
ResNetO crossentropy
10
10
100
10
10-1
Ir. 1/hh/ A
10-1
1/11/,
loss
loss
wwww
10-2
À
10
10
1/ho
10
1/ha
loss
loss
10-3
10
10"
10a
100
101
epochs
epochs
LeNet like_relu relu mse
ResNetO mse
10
100
4 10
10
3 10
10-1
Ir, 1/h//h A
10-1
1/h
loss
10a
loss
x 10-1
10-2
A
10
100
1/ho
1/ho
a
loss
10-1
loss
10-3
-0
10-1
10"
10
10"
101
epochs
epochs
Figure 5: MLP, LeNetl, tinyResNet with mean square error and soft-max entropy loss trained on a two classes cifar10 with a constant learning rate (0.1). The linear regression does not train in this setup.
14

---

Under review as a conference paper at ICLR 2021
MLP crossentropy
LeNet like relu crossentropy
10
10
10"
10-1
Ir. 1/h. A
10-1
loss
10
loss
10-2
À
10-2
x 10
1/ho
1/ho
10-1
loss
10
lass
10-3
10
xx10-1
10"
10a
10
10a
epochs
epochs
ResNetO crossentropy
MLP mse
10"
10
10
10
10
Ir. 1/hhh A
10-1
loss
Wmm
loss
10
10
10-2
À
10
1/ho
1/ho
loss
10-2
loss
10-3
10
10º
10a
10"
101
epochs
epochs
LeNet relu mse
10a
40-1
3 10
10
1/h,/
2 -0
loss
10-2
À
1/ho
10-1
0
loss
10-3
10a
10
epochs
Figure 6: MLP, LeNetl, tinyResNet with mean square error and soft-max cross entropy loss trained on a two classes cifar10 with a constant learning rate (0.3). The linear regression and the ResNet with MSE do not train with this setup.
15

---

Under review as a conference paper at ICLR 2021
MLP crossentropy
LeNet like relu crossentropy
10
10
2 10
10
10-1
Ir. 1/h. A
10-1
loss
100
loss
Ir.
10-2
À
10
1/ho
//g
x 10
loss
loss
10
10
10"
10a
100
10
epochs
epochs
ResNetO crossentropy
MLP mse
10
10
10
Ir, 1/hhh A
10
10-1
loss
loss
10-2
À
10
10-1
1/ho
1/ho
loss
loss
10
10-3
10-3
10
10
10a
epochs
epochs
LeNet like relu mse
ResNetO mse
100
10"
4 10-1
10a
3 10
10
Ir, 1/h. A
10
1/h,
loss
loss
2 10
10a
10-2
À
10-2
1/ho
3dbo
a
loss
10-1
a
loss
10
10-3
10"
10t
100
10a
epochs
epochs
Figure 7: MLP, LeNetl, tinyResNet with mean square error and soft-max cross entropy loss trained on two classes cifar10 with cyclic learning rate. The linear model regression does not train in this setup.
16

---

Under review as a conference paper at ICLR 2021
MLP crossentropy
LeNet like
like_relu relu crossentropy
10
10
6 60
10
4 40
10-1
Ir. 1/hh A
10-1
30-1
loss
loss
4 10
2 10
10-2
10
1/ho
1/ho
3 10
loss
loss
10-3
10-1
10
10
10a
100
10a
epochs
epochs
ResNetO crossentropy
ResNet18 crossentropy
109
10"
6 10
100
10-1
4 10-1
Ir, 1/h. A
10
1/h//,
loss
loss
3 10-1
10-2
À
10-2
1/ho
x 10
1/ho
α
loss
a
loss
10-3
10-3 3
10
10
101
10
10
10a
102
epochs
epochs
Figure 8: Lyapunov exponent (blue), inverse curvature from leading eigenvalue 1/ho (orange), learning rate (red), and loss (green) curves for MLP, LeNetl, tinyResNet trained with softmax- crossentropy loss on two-class CIFARIO problem; and ResNet18 trained on all ten CIFAR10 classes. All the trainings are with the quasi-Newton method based on method to calculate the largest eigenvalue of the Hessian of the loss.
17

---

Under review as a conference paper at ICLR 2021
Linear mse
MLP mse
10º
10
10
6 10-1
10-1
Ir. 1/hh A
10-1
loss
loss
4 x 10
10-2
À
3 10
10
1/ho
1/ho
10-1
a
loss
2x10-1
loss
10-3
10
10
10a
100
10a
epochs LeNet like relu mse
epochs
ResNetO mse
10
10"
4 x 10-1
3 10-1
10-1
Ir. 1/h. A
10-1
1/11/h,
loss
loss
2 10
10-2
À
10-2
1/ho
1/ho
10-1
loss
a
loss
10-1
10-3
10
10a
10a
10"
101
epochs
epochs
Figure 9: Lyapunov exponent (blue), inverse curvature from leading eigenvalue 1/ho (orange), learning rate a (red), and loss (green) curves for linear model, MLP, LeNetl, tinyResNet with mean square eггоr loss trained on the two-class CIFAR-10 problem with a quasi-Newton method based on method to calculate the largest eigenvalue of the Hessian of the loss. Notice how the linear least square regression can be successfully trained.
18

---

Under review as a conference paper at ICLR 2021
ResNet18 crossentropy
ResNet18 mse
10
10
10
100
10-1
Ir, 1/hh A
10
rr1/h,
loss
loss
10-2
À
10-2
1/ho
1/ho
10
a
loss
loss
10
10
10 10-3
10-1
100
101
102
10-1
10
10a
102
epochs
epochs
ResNet18 8 crossentropy
ResNet18 mse
10
10
10
10
Ir, 1/h//h A
10
1/h,
loss
loss
10
10-2
À
10
1/ho
10
1/ho
a
loss
a
loss
3
10
10"
101
10
10a
epochs
epochs
ResNet18 crossentropy
10
100
1/h, A
10-1
loss
10-1
10-2
À
1/ho
loss
10
10
10-1
100
101
102
epochs
Figure 10: ResNet18 with soft-max cross entropy loss trained on cifar10 with our quasi-newton method, cyclic and constant Ir of 0.05.
19


Reviews:
[{"review_id": "pYyn68tBBn4", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### 1. Brief summary\nThe authors use an insight from chaos theory to derive an efficient method of estimating the largest and smallest eigenvalues of the loss Hessian wrt the weights. To do that, they use nearby weight space positions, optimize for a bit (either gradient climbing or descending), check how quickly the points are departing from each other, and use that to estimate the extreme eigenvalues using a connection to Lyapunov coefficients in chaos theory. Then they use on the fly estimated largest eigenvalue to automatically tune the learning rate of SGD.\n\n### 2. Strengths\n* The paper makes a connection to chaos theory which typical members of the ML community are not familiar with\n* They derive an alternative to the usual top and bottom eigenvalue calculation methods that are employed\n* They try their automatic LR tuning in practice\n\n### 3. Weaknesses and points of confusion\n\n1) The only dataset tested was CIFAR-10. I am not saying you need to go directly to ImageNet, but a variety of datasets would be nice to see. You do try a bunch of architectures, so why not datasets as well. You could add MNIST, Fashion MNIST and SVHN relatively quickly and it would greatly strengthen the empirical conclusions.\n\n2) The simplest method for estimating the top eigenvalue -- the power method -- is also linear in the number of parameters. What advantage does your method have over that?\n\n3) The power method tends to be unstable (in its naive implementation) when used to get the less than highest eigenvalues. Does your method suffer from similar practical instabilities?\n\n4) The connection between the top negative eigenvalue and the rate of departure of nearby points in the weight space from each other (the same for gradient ascent and the top eigenvalue) does not seem very surprising to me. This might not be a valid point, but it seems that it is a simple consequence of optimizing in a quadratic well with a loss of the form 1/2 x H x^T, where H is the Hessian and the x is the minimum-centered position. The highest negative eigenvalue will be the one pushing you out as exp(|lambda| t). Why do I need chaos theory to see that? I might be wrong and I'm ready to be corrected, but it seems relatively simple to derive without much chaos-theoretic baggage attached to it.\n\n5) Almost every stability analysis of gradient-based algorithms will include the condition on the top eigenvalue being smaller than 2/LR and a very similar analysis to what you did using chaos theory here. I'm not sure what the new insight is here. Again, please correct me if I'm wrong.\n\n6) It seems that what you are describing with your adaptive optimization is very similar to some existing algorithms. [1] presents the lookahead optimizer that shares many features, and many variants of SGD (such as SGD+Momentum or Adam) likely do something very similar albeit implicitly.\n\n7) In Equation 10 you make the B a matrix, but it turns out to be an identity rescaled by the top eigenvalue -- a scalar. I get that this is the same, but it seems a bit misleading -- I got my hopes up for a proper matrix conditioning the LR but it turned out to be a scalar. This is a minor point, no need to address it.\n\n8) You argue that the 2/LR top eigenvalue selection by the optimizer somehow helps explain why DL works so well. But to me the more interesting questions remain: why are such places available, and how are they reacheable from init using gradient-based algorithms.\n\n### 4. Some papers that seem relevant\n[1] Lookahead Optimizer: k steps forward, 1 step back. Michael R. Zhang, James Lucas, Geoffrey Hinton, Jimmy Ba https://arxiv.org/abs/1907.08610 \n\n[2] Deep Ensembles: A Loss Landscape Perspective by Stanislav Fort, Huiyi Hu, Balaji Lakshminarayanan (https://arxiv.org/abs/1912.02757) studies how trajectories in the weight space diverge from different initializations.\n\n[3] Linear Mode Connectivity and the Lottery Ticket Hypothesis by Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, Michael Carbin (https://arxiv.org/abs/1912.05671) looks at how trajectories that start from a preoptimized point diverge with additional training.\n\n[4]  Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernel by Stanislav Fort, Gintare Karolina Dziugaite, Mansheej Paul, Sepideh Kharaghani, Daniel Roy, Surya Ganguli (https://arxiv.org/abs/2010.15110 and NeurIPS 2020) also looks at how trajectories from nearby points diverge. They also look at the sensitivity to initial conditions.\n\n[5] The large learning rate phase of deep learning: the catapult mechanism by Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, Guy Gur-Ari studies the stability of the training under finite step size and with SGD in quite some detail and it could be relevant. (https://arxiv.org/abs/2003.02218)\n\n[6] The Break-Even Point on Optimization Trajectories of Deep Neural Networks by Stanislaw Jastrzebski, Maciej Szymczak, Stanislav Fort, Devansh Arpit, Jacek Tabor, Kyunghyun Cho, Krzysztof Geras (https://arxiv.org/abs/2002.09572 and ICLR 2020) looks at the crucial effect of the early stages of training and the instability in it.\n\n### 5. Summary\nThis paper presents a nice new method for estimating the lowest and largest eigenvalues of the DNN loss Hessian wrt weights using the divergence of nearby points in the weight space under optimization. They do this by using a chaos-theoretic language. While those methods seem useful, I do not see why chaos theory was needed to derive them. I appreciate the link and believe that more good stuff could come out of it, but as is I don't think this paper provides much new to the field on its own. However, I am not an expert on this subfield and **I am ready to revise my score** if the authors convince me otherwise.", "extra_scores": {}, "extra_text": {}}, {"review_id": "GjfqpjX20du", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Interesting approach using ideas in chaos theory to deep learning but its merit is not clear yet. \n\nSummary:\n\nThis paper connects ideas in chaos theory to understand training dynamics of neural networks. In particular the paper uses Lyapunov exponent, divergence rate of infinitesimal close trajectory and connects them to Hessian eigenvalues. The authors show that the largest Lyapunov exponent corresponds to the most negative eigenvalue of the Hessian. Then the paper claims that this provides an efficient method to estimate the largest eigenvalue and connect to using learning rate related to largest eigenvalue.\n\nUsing this method, the paper claims SGD finds loss landscape regions where the largest eigenvalue of the Hessian is similar to the inverse of the learning rate. Lastly, the paper proposes a quasi-Newton method with dynamic estimation of optimal learning rate.\n\n \nReason for score:\n\nWhile connection between ideas in chaos theory and neural network optimization is interesting and worth pursuing, I believe current work is underdeveloped in the sense that comparison to well-known methods are not provided thoroughly. Proposed method of estimating largest eigenvalue of Hessian is presented without any comparison to well-known methods such as Lanczos and proposed quasi-Newton method’s utility is unproven as is. \n\n\nPros:\n\nThe paper proposes an interesting connection between analysis in chaos theory and neural network optimization.\n\nPaper is clearly written and exposition to chaos theory in section 2 is  a nice read. \n\nEmpirical observation that maximum eigenvalue of Hessian over training matching learning rate for various experimental settings is quite interesting. While I would have been interested to see similar observations for commonly used step learning rate schedules. \n\n\nCons:\n\nThe analysis is based on continuous time dynamics of SGD which is a fine toy-model but misses various interesting finite step dynamics in Neural Network training. For example [1] have shown that the largest learning rate based on eigenvalue estimation is not sufficient for explaining neural network training dynamics especially in the well-performant ones. \n \nOne major problem I see is missing comparison to well known literature. There are numerous analyses for studying Hessian of Neural Networks with various methods(e.g. [2, 3, 4] and references there-in), and it is hard to find why the proposed method using the Lyapunov exponent is either more interesting or useful.\n\nFor one thing there are various methods to estimate large eigenvalues of large matrices. For example, naively I would have used Lanczos to estimate the top few eigenvalues very efficiently using Hessian-Vector product. Why would a proposed method be better than this? \n\nAccording to discussion in Related work section, the benefit over power-iteration from (LeCun et al., 1993) is that it is free from choosing a running average hyperparameter, in which case the novelty of the proposed method itself does not seem significant especially with lack of analysis that directly compares one another. \n\nLastly, while the authors suggest that the method is efficient, most experiments are done in the toy-ish setting whereas [3] could study full Hessian spectral density of ImageNet-scale networks. \n\n\nProposed quasi-Newton does not have sufficient analysis that the idea works. There are numerous ideas for proposing new optimization and without careful, through comparison to baseline, well-known methods. I believe Figure 2 is testing that the optimization works. However it is not clear with the current set of experiments whether this optimization can be useful compared to simple Adam or SGD with momentum. \n\t\nWhile one could eliminate the learning rate schedule with this method, it is not clear whether the proposed quasi-Newton method provides benefit over used schedules. SGD works well without schedule, but typically schedule improves performance beyond constant learning rate. Does automatic determination of learning rate provide the benefit of custom learning rate schedule without any tuning procedure? I think this question needs to be answered for the proposed method to have impact on practitioners.  \n\n\n\nQuestions:\n\nAs far as I can see, the procedure for both top eigenvalue and top-k eigenvalue is very similar to how one would estimate them using simple power iteration or Lanczos algorithm(https://en.wikipedia.org/wiki/Lanczos_algorithm) used in e.g. [2,3,4]. Could you explain how they differ? At least stochastic estimation (not using full batch) has been utilized in [3] where they study dynamics of Hessian spectral density during Training and I believe few top value estimation is much simpler to extract.\n\nDo the authors believe chaos in parameter space is a relevant question to answer? In the end, one is interested in neural network function and even if the parameters diverge the function output may converge since many different parameter configurations can lead to the same or similar functions. \n\nIn section 6, suggestion for using larger learning rate towards the end of training seems to be against the typical practice for obtaining well performing models. I believe even suggested reference (Smith et al., 2017) suggests decaying the learning rate is a good idea for generalization and mimics the effect by increasing the batch size. \n\nWould be interesting to find out if the analysis in Appendix B can generalize to Adaptive optimization algorithms such as RMSProp or Adam. \n\n\n\nNits and additional feedback:\n\nThese are few nits and feedback to improve the paper which were not critical for evaluation:\n\nRef (Sprott & Sprott 2003) seems to be actually a single author book, I suspect bibtex is misconfigured. \n\nFor the experiments section (4), it is not clear what message the experiments are conveying. The experiment setup without knowing what motivates the analysis is hard to follow, so I suggest starting with a general goal for the experiments to help the readers.\n\nFor second-order methods in Neural Networks in the related works section, it is worth mentioning K-FAC papers [5,6,7]\n\nI am not sure if the statement “robustness to learning rate choice” is correct in Section 5. In most cases, choosing a proper learning rate for a first order method is quite important and probably the single most important hyperparameter to tune. If the learning rate is too small, convergence will be too slow, if it is too large SGD can diverge. Also there’s evidence that a very small range of learning rate is critical for improving performance [1].\n\nFigure 3 with x, y axis labels missing\n\nInconsistent use of cifar10, CIFAR10, CIFAR-10 across the paper\n\nUnderstandable for conference submission with deadlines; content in the Appendix needs more cleaning up. (e.g. wrong quotation marks, ‘newton’ instead of ‘Newton’ etc)\n\n\n[1] Lewkowycz et al., The large learning rate phase of deep learning: the catapult mechanism, arXiv:2003.02218\n[2] Gur-Ari et al., Gradient Descent Happens in a Tiny Subspace, arXiv:1812.04754\n[3] Ghorbani et al., An Investigation into Neural Net Optimization via Hessian Eigenvalue Density, ICML 2019\n[4] Jastrzebski et al., On the Relation Between the Sharpest Directions of DNN Loss and the SGD Step Length, ICLR 2019\n[5] Martens & Grosse, Optimizing Neural Networks with Kronecker-factored Approximate Curvature, ICML 2015\n[6] Grosse & Martens, A Kronecker-factored approximate Fisher matrix for convolution layers, ICML 2016\n[7] Ba et al.,  Distributed second-order optimization using Kronecker-factored approximations. ICLR 2017.", "extra_scores": {}, "extra_text": {}}, {"review_id": "8gIIjSDApkV", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Objective of the work: The paper uses the chaotic theory to study the dynamics of SGD. It provides algorithm to compute the most positive and the most negative eigenvalues of Hessian based on analyzing the Lyapunov exponents. The paper shows that the largest eigenvalue of the Hessian similar to the inverse of the learning rate.\n\nStrong points: The paper proposes an algorithm that can fast estimate the largest eigenvalues of the Hessian based on the analysis of the Lyapunov exponents. The technical derivation is sound. \n\nWeak points: \n1. Chaos theory provides a way of computing eigenvalues but does not give much understanding on the neural network optimization. For example, what does the timescale of the most negative eigenvalue mean for the NN optimization. \n\n2. There are several points the paper wants to present, however they are not logically connected: the most negative eigenvalue, the largest eigenvalue of the Hessian, the relation between the largest eigenvalue of Hessian and the learning rate.\nThe experiments show that the eigenvalues of the Hessian adapts to the learning rate, which indicates the learning rate sort of affects the Hessian, which indicates that we should not follow the largest Hessian eigenvalue if we want certain feature, i.e., large eigenvalue for a wide valley. However, the paper also propose setting the learning rate according to the Hessian leading eigenvalues. Is there first eigenvalue or first the learning rate. \n\n\n3. For computing the eigenvalues of Hessian, the paper does not give sufficient discussion or experiments of comparing the proposed algorithms with other existing approaches (Hessian vector product method, the density method [1]) to verify the efficiency and the difference. \n\nI would not recommend the acceptance for now.\n\n[1] Ghorbani et al. An Investigation into Neural Net Optimization via Hessian Eigenvalue Density, ICML 2019\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The Authors study the learning dynamics of deep neural networks through the lenses of chaos theory. 

The key weakness of the paper boils down to a lack of clarity and precision. Chaos theory seems to be mostly used to computing eigenvalues but is not used to derive meaningful insights about the learning dynamics. R2 noted, "Chaos theory provides a way of computing eigenvalues but does not give much understanding on the neural network optimization.". R4 noted, "The authors use an insight from chaos theory to derive an efficient method of estimating the largest and smallest eigenvalues of the loss Hessian wrt the weight". Hence, statements such as "the rigorous theory developed to study chaotic systems can be useful to understand SGD" seem unsubstantiated.

Reduced to its essence, the key contribution is (1) a method to compute the top and the smallest eigenvalue, (2) the observation that the spectral norm of the Hessian along SGD optimization trajectory is related to the inverse of the learning rate, and (3) a method to automatically tune the learning rate.

Let me discuss these three contributions:

* The significance of the first contribution is unclear, as pointed out by R2. Indeed there are other methods (e.g. power method, Lanczos) for computing these quantities that should achieve either a similar speed or similar stability. Given the rich history of developing estimators of these quantities, a much more detailed evaluation is warranted to substantiate this claim. 

* The core insight that the top eigenvalue of the Hessian in SGD is related to the inverse of the learning rate in the training of deep neural networks is nontrivial but is not fully novel. Closely related observations were also shown in the literature.
This precise statement however indeed was not stated in the literature. This contribution could be a basis for acceptance, but the paper is not sufficiently focused on it, and the evaluation of this claim is a bit narrow in scope.

* Finally, there is a range array of methods to tune the learning rate. As noted for example by R3, "There are numerous ideas for proposing new optimization and without careful, through comparison to baseline, well-known methods", the evaluation is too limited to treat this as a core contribution.

Based on the above, I have to recommend the rejection of the paper. At the same time, I would like to thank the Authors for submitting the work for consideration to ICLR. I hope the feedback will be useful for improving the work.
Decision: Reject