Learning to Optimize Quasi-Newton Methods
Authors: Isaac Liao
Rumen Dangovski
Jakob Nicolaus Foerster
Marin Soljacic
Venue: Accepted by TMLR ()

Abstract: Fast gradient-based optimization algorithms have become increasingly essential for the computationally efficient training of machine learning models. One technique is to multiply the gradient by a preconditioner matrix to produce a step, but it is unclear what the best preconditioner matrix is. This paper introduces a novel machine learning optimizer called LODO, which tries to online meta-learn the best preconditioner during optimization. Specifically, our optimizer merges Learning to Optimize (L2O) techniques with quasi-Newton methods to learn preconditioners parameterized as neural networks; they are more flexible than preconditioners in other quasi-Newton methods. Unlike other L2O methods, LODO does not require any meta-training on a training task distribution, and instead learns to optimize on the fly while optimizing on the test task, adapting to the local characteristics of the loss landscape while traversing it. Theoretically, we show that our optimizer approximates the inverse Hessian in noisy loss landscapes and is capable of representing a wide range of inverse Hessians. We experimentally verify that our algorithm can optimize in noisy settings, and show that simpler alternatives for representing the inverse Hessians worsen performance. Lastly, we use our optimizer to train a semi-realistic deep neural network with 95k parameters at speeds comparable to those of standard neural network optimizers.

Published in Transactions on Machine Learning Research (09/2023)
Learning to Optimize Quasi-Newton Methods
Isaac C. Liao
ilioo Ommil edu
Research Lab for Electronics MIT
Rumen R. Dangovski
rumenrd@mit.cmm edu
Research Lab for Electronics MIT
Jakob N. Foerster
Cecesstr@cs.torontee edu
Deportment of Engineering Science University of Oxford
Marin Soljačić
soljacio@mil. edu
Research Lab for Electronics
MIT
Reviewed on OpenReview: https: // wptp///eee.rvvee..emm/ee net/ hta//forur forum? id= 2ssxXAzudy
Abstract
Fast gradient-based optimization algorithms have become increasingly essential for the computationally efficient training machine learning models. One technique multiply the gradient by preconditioner matrix produce a step, but it is unclear what the best preconditioner matrix is. This paper introduces novel machine learning optimizer called LODO, which tries to online meta-learn the best preconditioner during optimization. Specifically, our optimizer merges Learning to Optimize (L20) techniques with quasi-Newton hoth to learn preconditioners parameterized as neural networks; they are more flexible than preconditioners in other quasi-Newter methods. Unlike other L20 methods, LODO does not require any votaatraining on training task distribution, and instead learns to optimize on the fly while optimizing on the lest task, adapting to the local characteristios of the loss landscape while traversing it. Theoretically, we show that our optimizer approximates the inverse Hessian in noisy loss landscapes and is capable of representing wide range of inverse Hessians. We experimentally verify that our algorithm can optimize in noisy settings, and show that simpler alternatives for representing the inverse Hessians worsen performance. Lastly, we use our optimizer to train a semi-realistic deep neural network with 95k parameters speeds comparable to those of standard neural network optimizers.
1 Introduction
Many optimization algorithms like stochastic gradient descent (SGD) (Rosenblatt) 1958 and Adam (Kingmal & Ba 2014) have been widespread and successful in the rapid training of deep neural networks (Sun al.
2019ah. Fundamentally, this problem of minimizing loss which is a function of large vector containing the weights of the network. The time it takes to optimize a neural network is a bottleneck in machine learning. The more quickly network can be trained, the more computational resources are saved, and therefore
researchers have devoted great effort into creating new and faster optimizers. (Jain & Kar 2017
Metz et al.
2020 Bernstein et al. 2020 Martens & Grosse 201 5a
Sun et al. 2019bb
We present a novel algorithm drawing from the field of learning optimize (L20) spearheaded by & Malik 2016) and (Andrychowicz al. 2016). Namely, we use meta-optimizer to online learn an optimization strategy which reaches lower losses with fewer steps. Our learned optimization strategy takes

---

Published in Transactions on Machine Learning Research (09/2023)
the form of an online learned neural network representation of the local inverse Hessian of the loss which is meanwhile being used as a gradient preconditioner for quasi-Newton optimization. Unlike in the Newton method, matrix-vector multiplication by the inverse Hessian estimate is cheap for our neural representation, allowing our optimizer to train much larger neural networks than the Newton method can. Unlike other L,0 algorithms which learn to optimize before optimization (Chen et al., 2021), our algorithm "learns to optimize during optimization" (LODO for short) without any L,20 meta training time on a curated training task distribution, and instead applied directly and immediately to the desired optimization problem with preparation. This way, LODO learns during training how to exploit any local curvatures of the loss landscape within each use case. Our work on LODO primarily aims to foster further study on the blending of quasi-Newton and L20 methodologies, specifically by combining the step efficiency of the Newton method with the gradient-based learning capabilities of neural represenlations of matrices. We present theoretical work to show that this blending gives rise to desirable optimization behavior nonlinear and stochastic problems, and experiments to support this theory. We target the problem of training model architectures with lots of parameter sharing, such as convolutional networks, where the time taken for inference within the training loop drastically outweighs the time taken by the optimizer.
Claims and Evidence. We show theoretically and experimentally that simplified version of LODO correctly learns the inverse Hessian in stochastic convex setting. Next, we show theoretically that LODO's inverse Hessian representation is highly expressive, and experimentally that simpler, less expressive alternatives perform worse. Finally, we demonstrate the use of LODO in an autoregressive image generation task and in image classification. This paper serves as a stepping stone in the development of meta- cesta-raannin--iie online L20.
The remainder of this paper is structured follows. Section 2 discusses relevant background and contributions in optimization and L20. Section 3 shows how LODO works. Section | provides theoretical justification for our design of LODO. Section 3 shows experiments which explore what makes LODO work and why. Section discusses our findings and Section summarizes them.
2
Related Work
Research into the construction of faster optimizers has mostly fallen under two branches of work. The older branch attempts to endow SGD with adaptive capabilities, often through modifications involving calculations of means and variances of the gradient using exponential moving averages (EMAs). These values are then combined to create a preconditioner matrix which is then multiplied by the gradient to choose step. RMSprop (Hinton et al. 2012) and Adam use the mean to induce momentum with a varianco-based diagonal preconditioner to normalize the step size. LARS (You et al., 2017) modifies the preconditioner calculation to normalize layer-wise, while Yogi (Zaheer et al. 2018) modifies the variance accumulation to control increases in effective learning rate in slower manner.
Some methods such as the Newton method and natural gradient descent (aartens & Grosse et al. 2018) precondition the gradient with adaptive estimates of the inverse Hessian and the inverse Fisher information matrices, respectively. These methods converge quickly but can be vulnerable to gradient noise and/or impractical to implement due to the resources spent in calculating and/or inverting the high dimensional matrices involved. For example, a prominent natural gradient based optimizer is K-FAC (Martens Grosso (015b),, which preconditions using a Kronocker-factoriag requires numerous expensive matrix inversions. For the Newton method, many researchers have developed approximations of the algorithm eagllethmccalldd quasi- Newtin methods-white have reduced time and memory complexity, such as L-BFGS (Nocedal & Wright
2015c George
inverse Fisher cstimator, and
1999) and variants better suited to the stochasticity and structure present in machine learning optimization problems (Schraudolph et al. 2007 Parker-Holder et al.,
2020 Goldfarb et al. 2020 Park & Oliva 2019 Yao el al. 2021).
In a quasi-Newton method, an approximate solution a, E R" refined by T441 = x, aG,g, for some learning rate ā 0, where G, = (V2, ((:))( e Rax= is some approximation of the inverse Hessian and 9: V E R is the gradient computed by backpropagation from the loss f IR" + R. G, is usually
2

---

Published in Transactions on Machine Learning Research (09/2023)
computed from a past history of ( pairs. â produces the exact solution for quadratic f, so we assume that ā = 1 from this point on.
The big difference which distinguishes LODO from other quasi-Newton methods is that its preconditioner is learned by a meta-optimizer through a method known as "hypergradient descent" " (Baydin et al.) 2017). J, rather
than estimated using a hardcoded formula like the methods listed above. While past hypergradient methods use low-rank Mookovvtz et al. 2019). ; diagonal (Amid et aJ. 2022 Baydin et al. 2017], or Kronecker-factorized [Bac et al. 2022 Goldfarb et al. 2020 preconditioners, LODO uses an entirely different, neural network-based
style of preconditioner, which is more expressive than low-rank and diagonal preconditioners while requiring lower time complexity than K-FAC. LODO is distinguished from the above methods in two aspects: the novel preconditioner, and the meta-learning approach for training the preconditioner. Our theory is focused on these two aspects of LODO. We present evidence of the theory in controlled experiments, of which (Amidl ct al. 2022: Baydin et al. 2017) are our ablations. We underscore that our objective not to compare against. all hypergradient methods but to focus on the theory of LODO and its validation in controlled experiments.
More recently, subfield of meta-learning known as learning to optimize (L20) has shown that deep networks can themselves be trained offline to perform optimization, at speed which exceeds that of popular traditional optimizers, in hopes of further accelerating training procedures for other deep neural networks. [ndrychhwicz let al. (2016) (whose optimizer we will call *I2I.BGDBDD") and Li & Malik 2016 2017) were among the first to successfully train neural networks to transform gradients into high quality steps, by backpropagating through unrolled and truncated training loops to tune the optimizer. Since then, many other variations of this idea have successfully produced optimizers exceeding the speed of common optimizers for narrow ranges of machine learning models (Metz et al., 2018), though theoretical analysis of these learned optimizers tends to be difficult and scarce. A major goal of L20 research is to learn a single optimizer which can generalize to be able to train a wide variety of machine learning models with speed. (Lv et al. 2017)
Two issues also prevent L20 optimizers from being rapidly developed experimentally. Firstly, a carefully chosen "task distribution" " for optimization practice is required for the meta-training of the L20 optimizer, playing the role analogous to the "dataset" " but for learning how to optimize rather than to classify or to predict. These tasks are difficult to curate because the issue of generalization error applies; we need the test task to be similar to the training task distribution. Secondly, meta-training is prohibitively costly in that it involves nested training loops, which run much slower than a single training loop like in traditional learning (Metz et al. 2019 While other L20 methods are burdened by choice of task distribution and lengthy meta-training, LODO avoids these issues by learning to optimize online directly on the test task.
3 How LODO Works
Our algorithm approximates the inverse Hessian in a quasi-Newton method using a matrix G. = G(O,) Rex* parameterized by a vector Og of weights learned over time i, described later in this section. After every step (-t+1 using the formula
0e+1 2; G(O.).
(1)
the loss le+1 = (*++1) is computed. Then the new gradient V in 2t+1 is computed through backpropagation as usual, but for LODO we continue backpropagation through Equation | until we find the "hypergradient" " Vo, &ot1 in the optimizer weights 6,, which allows us to update the optimization strategy as well. In this manner, 0g is trained such that the quasi-Newton method tries to minimize the loss upon taking a single step.
In the L20 interpretation of such an algorithm, this would be equivalent to unrolling the inner loop optimization for only one step, causing severe truncation bias; the optimizer learns to greedily optimize within too short of a time horizon, thus suffering in the long term (Metz et al. 2019). As a countermeasure, we take inspiration from the Momentum modification to SGD, and replace g: by a gradient EMA (1 (1-3) -r gg for use in Equation] [ This changes Equation to xt-1 = 2; - (1 ().) Σ 3t-Tg- some decay parameter 39 producing our LODO algorithm, summarized in Algorithm I While we do not theoretically analyze the effect of momentum accumulation on LODO, Section 5.3.2 shows experimentally
-g. instead, for
that momentum is beneficial in practice. We leave any theoretical analysis of momentum for future work.
3

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm Learning to Optimize During Optimization (LODO)
Require: f IR" + R: Function to minimize.
Require: 26 E R=: Initialization.
Require: a R: Meta-learning rate (default 0.001),
Require: 0g R: Initial learning rate (default 1.0),
Require: 0 $ 3 < 1: Momentum (default 0.9),
+-0 0
Start time
Oo f random initialization
> Initialization for G neural network b Initialize momentum
my +
while not converged do
Pt+1 f- 24 -
D. Pick a step using with Eqs. and (
4+1 + f(0141)
Compute loss after step
01+1 + 0 + (Ve
Tune the G model to pick better steps
m++1 <- Am: + (1 - V)
m14 l+11
D Update momentum
+-++1
> Increment time
end while return 0,
Our parameterization of G(0) is uniquely inspired by the FFT-style Efficient Unitary Neural Network (EUNN) (Jing et al. 2017) designed for paraieter-efficient representations of unitary matrices. We replace the fixed distance interactions by random interactions and force the result to be symmetrid by choosing G( to be the following product of many matrices:
G(0) = oa (I 0) G(O))((( (
N
G()) = II B 1
P.
1=1
where ag is a fixed initial learning rate, P. are randomly selected permutation matrices, and ((0()) are block-diagonal matrices whose block contents are listed in a subsection g(0) of the parameter vector illustrated in Figure 1 Every block is size k x k for chosen is (we use for
0 = (0(1)... ..... (.N),, setup). The (I 0) and (I 0)" matrices are n x ñ and ñ x respectively, where ñ is some integer chosen to be larger than (we use ñ = [2n/k]k for our setup), and all other matrices are ň x î. By initializing each block matrix in B(0()) to random orthogonal matrix, we ensure that G(0) and upon initialization, despite the input information diffusing and mixing with itself as more of the first N block matrices are applied (for our setup we choose 16), normalizing hypergradient magnitudes facilitate the initial meta-learning of O. In effect, this causes LODO to begin with the strategy of SGD with the same learning rate in all directions.
The product G(() intentionally resembles the operation performed by a deep neural network with N layers, millions of hidden neurons arranged in inverted bottleneck style, very sparse connections, and no activation functions. We intend for the random connections between neurons to bring expander graph properties to the computation graph of the neural network, such that input signals can diffuse and self-mix quickly without travelling long distances within the computation graph.
Since we expect the receptive field of output nodes to grow exponentially with depth, it takes Ologgn) layers for all of the inputs to interact with each other, than O(logn) n). Applying permutations and block diagonal matrices both require O(n) time and memory, so matrix-vector multiplication with the inverse Hcssian estimate G(Ø) costs (ng n) time and memory. We intend for LODO to be used to train machine learning architectures of high parameter reuse such as CNNs and transformers, such that this (n logn) cost of LODO is small in comparison to the forward and backward passes of the trained model itself.
intend for the depth N to be not much larger
This is because the true inverse Hessian also symmetric.
4

---

Published in Transactions on Machine Learning Research (09/2023)
G(O)T
G())
P
B( Ps B(O PT B(B " B(O PI
B(OR))
Pz
B(O())
P3
0n
I 0
rand perm
rand perm
rand perm
rand perm
rand perm
rand perm
Figure 1: Visualization of LODO's matrix structure of G from Equation 2 for the approximation of the inverse Hessian. Reduced to depth of 3, block size 2, and size n = 8 matrices for illustration.
4 Theoretical Properties of LODO
In this section, mainly present two theoretical results: in Section 4.1 about desirable preconditioner learning dynamics, and in Section 4.3 about preconditioner expressiveness; we also show that LODO repels saddle points in Section 4.2 and there is further analysis from the literature for the preconditioner approximation
error function in Appendix D
4.1 Inverse Hessian Learning Dynamics
We first motivate that under certain conditions, LODO learns the Hessian over time. This result allows LODO to come arbitrarily close to the true inverse Hessian despite noise, which makes LODO more noise-tolerant than most other quasi-Newton methods, whose preconditioners may vary wildly in the presence of noise. We assume that the loss function to minimize is quadratic with fixed positive-definite Hessian H, where the minimum x is perturbed by noise s; at every time step t,
4 = fe(a)) 2 (xt T
H(x, x;))
(3)
x/+1 x 8t-
(4)
The perturbations 8, i.i.d. from some light tailed distribution of zero mean, for example a multivariate normal distribution M(s,; 0, E).
For this section, we restrict our analysis to a simplified version of LODO, though the experiment of Section 5.1 supports similar findings for the full version of LODO as well. In our simplified version, the inverse Hessian approximated by a full dense matrix G(O,) rather than the compositionally sparse architecture of Equation 2 so this result is relevant to many hypergradient hods and not restricted to LODO. We will also update 0, using SGD of learning rate a instead of Adam; and we will feed the gradients directly into the G network using Equation [ rather than accumulating them into EMAs first, ic. B =.
Under these conditions, the gradient of loss with respect to both and O, can be explicitly solved for. LODO turns out to follow the training dynamics
A = A, ooHbb H2
(5)
6 = A,b,
(6)
with the change of variables to A, = H the inverse Hessian approximation error and b, = x; the quadratic minimum approximation error, to replace G(O,) and æ, in the analysis. A full derivation of Equations 5 and 0 is in Appendix [A.1] Assuming that the learning rate a is low enough and the error A, begins small enough to have spectral norm loss than 1, A, must evolve very slowly while b, comparatively quickly exponentially decays to a fixed distribution B, dependent on A, as determined by Equation 0 Furthermore, since A, moves slowly, B, Bi, so long as - to for some reference time is not too large.
5

---

Published in Transactions on Machine Learning Research (09/2023)
Thus, to determine the direction of slow movement of A, (we seek to show that it moves towards zero), we can use Equation as though by were sampled i.i.d. from Bg. Appendix A.2 gives more rigorous justification for this approximation. Mathematically, we keep Equation but approximate Equation i with
b A by 8t-
By recursively substituting Equation into itself and then into Equation 5. the total eventual contribution of all 8, for to T S t to the slow movement of A, is then
aH Ato
Σ
A n
Σ o (Alo") H² T=to
with some extra doubly summed terms for with pairwise products between 8n, and 87y (T1 * 72), and some singly summed terms for products between bt, and 8y. In the long term (but with low enough a to retain the approximation of Equation 7 the average contribution of cach 8, towards the total of Exprcssion S then converges to
aHAt
Σ A "E 8787 m==0
(Aea ") H²
(9)
where pairwise products of 8; and 8j for i + and other terms with bio negligible due to mutual independence and small a. Expression g is then the step direction for the Euler method for approximating the solution to the differential equation
dA dt
= HA A ATE 188
(A")TH?
(10)
n=0
which can be shown to cause A to flow towards zero as desired 2
One might ask how the approximation made by Equation 7 by taking A, & Ato continues to hold while A flows to zero. When given a time to, this approximation only necessary reach the conclusion that over short distances, A has the long- term flow rate/direction of Equation 10 After every Euler step on Equation 10 we may reinstantiate lo to the new value of t, such that the accuracy of the approximation A, RJ At, is fully restored for Equation 7 to be accurate, and Equation 10 can be reached once again so the next Euler step can be taken. It is in this way that the movement of A is described by Equation 10
The flow A towards zero implies that G(O,) approaches H meaning that the inverse Hessian approxi- mation improves over time. Therefore, it reasonable to believe that LODO learns better inverse Hessians over time, given small enough learning rate and good initialization. The Frobenius norm of the error decays faster when magnitudes/ norms of H and E. [ss"] are higher, indicating that both curvature of the Hessian and noisy movement of the quadratic bowl's minimum are good for learning the Hessian for fixed a, long as the approximations required for the above analysis stay accurate. An interpretation of this phenomenon is that the noise in every direction provides a training signal for LODO to learn that direction's curvature and is amplified by the Hessian H.
A flows towards zero because by substituting the eigendeccomposiiiion H U where UUT I, and using B UT AU, we can show that norm BD decreases over time,
BD dt
tr (D
B
(11)
dt
= 21r
B" DB
Σ
B"UBB sss
U(B
(12)
n=0
D
B 98
U(BOST
(13)
n=
<0
(14)
where the strict equality is only satisfied for

---

Published in Transactions on Machine Learning Research (09/2023)
4.2 Saddle Point Repulsion
We may also produce another analysis for quadratic loss functions of Hessian H with direction of negalive curvature, to show that LODO repels saddle points. Again, we restrict our analysis by omitting momentum as in Section 4.1 but here we keep the original architecture of G( from Equation 2 and the Adam meta-optimizer, and merely set the meta-learning rate a to be negligibly small. From Equation 2 G is a positive-definit symmetric matrix most cases of 0r, and effectively fixed due to small a. Then, G must have some negative eigenvalue with eigenvector y (see Appendix B for proof), such that the matrix x= from
A - - H has eigenvalue of norm greater than 1, meaning that the displacement b the center of the saddle x" blows up exponentially in the y direction. Since Hy xy, left multiplying by yd G(O,)-1 further shows that y Hy < 0, implying that the direction of saddle point repulsion is one of negative curvature, which decreases the loss.
4.3 Preconditioner Expressiveness
In this section, we seek to show that our parameterization of G is highly expressive; LODO may represent a wider range of inverse Hessians than many other mothods. In fact, we show that with an increase in parameter count by only a logarithmic factor in the task dimension, our fixed parameterization of G()) can exactly replicate any possible parameterizations F where vector multiplication with a matrix F is computable with almost any arbitrary sparse linear neural network of a given size. Our parameterization thus capable of replicating scalar and diagonal preconditioners from (Baydin et al. 2017) and (Amid et al.) 2022 with only (ñ log îi parameters, and low rank preconditioners (Moskovitz et al. 2019) with only O n) parameters. Definition 4.1 creates function e to characterize the mixing rate of random transpositions when trying to shuffle lists, while Theorem 4.2 uses this e function to lower bound the probability that the G())
network in LODO can represent other lincar neural networks when randomly sampling over the permutations
P. in Equation ?
Definition 4.1. Uniformly sample a sequence of Nn/2 transpositions of two out of elements, for integers n/2 e N and V e N, with the condition that every successive block of ñ/2 transpositions commutes internally (transpositions can be rearranged within a block). We replace each transposition with the identity operation with probability 1/2, and then compose the sequence of transpositions/ //dentiiiesss to form a permutation. Then, we define the function e(Nñ/2, fi) such that the expected entropy of this permutation, given the original sequence but not given the locations where identities were placed, is log n! ((Nn/2, f.).
Theorem 4.2. Uniformly sample permulations P. and create block- diagonaa malrices B(O()) where every block is 2 x 2, and whose block contents are listed by the parameters ((0)_ Use these to construct the LODO subnetwork G()) as in Equation 2 with some depth N and hidden dimension û. Construct any linear neural network F with input dimension, output dimension, number of connections per layer at most ñ. at most k incoming and at most i outgoing connections for every newron, depth d, and otherwise any arrangement of connections. Then, there is a probability of at least
nN
1 R.N
7
(15)
2
Add[loge di + 1)
that G(()= F for some O.
We provide constructive proof in Appendix
We believe that random transpositions in the style of Definition 4.1 are quick way to shuffie lists via transposition, since the Cayley graph over the symmetric group generated by all transpositions has good expansion properties [Konstantinvaa & Kravchuk 2022). In other words, we hypothesize that for large N and û, we have c( (NN/2,, z ciñe-rgNay? ogNa72 for some positive constants C₁ and c2. This would imply that the probability that (0)) can represent all possible is at least approximately
cıñ exp
-C Ad([logg k +1)
niN,
(16)
V
2
7

---

Published in Transactions on Machine Learning Research (09/2023)
hessian approximation errar
0.82
18
Momentum
16
0.80
training loss
Adam
14
LODO
0.78
TM
12
O-LBFGS
0.76
L2LBGD8GD
10-
Levenberg-Marquae
0.74
8-
Newton method (theoretical)
25000
50000 step
75000 100000
25000 50000 75000 100000
step
Figure 2: Left: LODO's average inverse Hessian approximation error o = I G on the noisy quadratic bowl task of Section 5.1 x² is measured by the unbiased estimator TOO
1 Ei= [I - G(O,) H)
with random independent unit vectors v;- a = 1 when G(O,)) is trivially zero and a = when G( = H
as desired. Ordinarily, Theorem 4.2 would dictate that G( = H is reachable for some 8t, but 8, is nowhere near overparameterivee enough for the theorem to apply, so we do not reach even close to a = 0. Despite this, a still decreases over time. Right: Average training loss learning curves. The dotted line shows the theoretically best possible loss using Newton's method. Better optimizers maintain lower losses after infinile steps, since for this task, loss is introduced over time and the optimizer serves to quickly suppress it. Solid lines indicate methods whose time complexities allow for scaling to large neural networks (ie. O(n n) or less,) while dotted lines indicate methods which are too expensive for this.
which can be made to be above 1 - (n!) for any constant e by using sufficient depth N which goes like N xc d(log, k) log ú, due to Stirling's s approximation. Thus we believe that by only being O(log, k) log n) times deeper than F, we can make it very likely that our model G()) can represent all possible F.
5 Experiments with LODO
We present here a number of tasks which provide experimental evidence for the thcorctical results we claim, though we test a variety of optimizers on these tasks. Appendix L explains how we tuned each optimizer's hyperparameters for each task. Optimizers were used 8 times for every experiment to ensure reproducibility of results by randomly sampling over the permutations P. in Equation 2 with different randomization seeds, unless otherwise stated. Error margins in Figures and intervals in tables indicate +1 standard deviation across the the 8 runs. Our timing setup is described in Appendix
5.1 Noisy Quadratic Bowl
In Figure 2 and Table D we use various optimizers to track the minimum of a quadratic bowl of fixed true Hessian H as its minimum is perturbed by noise at every step, to demonstrate that LODO correctly learns its inverse Hessian representation as claimed in Section 4.1 The setup of the noisy quadratic bowl is the same as in Section 4.1 and details are provided in Appendix F.1 We interpret an optimizer to be better if it can maintain lower loss in the infinite step limit, since the error builds at constant rate over time and the optimizer's role is to react and correct it as quickly as possible. We tested each optimizer by using it to track the minimum of the moving quadratic bowl over 100k steps. Learning curves in Figure 2 and losses in Table show that LODO tracks the minimum more accurately than other optimizers, and that an estimator of the decays over time. Other optimizers underperform
inverse Hessian approximation error | because their proconditioners are less expressive, being either diagonal or low-rank and thus unable to capture the off-diagonal elements or non-top-few singular values of the true inverse Hessian, leading to a higher loss.
Sensitivity to Noise. In Table 7 and Figure S of the Appendix, we test the performance of LODO in the presence of noise of isotropic variance v no longer fixed to 1. While some other optimizers' noise-rescaled training losses f/v (c.g. RMSProp, Yogi and Adam) are heavily dependent on the noise covariance v, LODO's noise-rescaled training loss does not, and LODO still consistently outperforms all the other optimizers for all We believe LODO is unaffected by noise magnitude because the mela-optimizer Adam has long term
8

---

Published in Transactions on Machine Learning Research (09/2023)
Table 1: Average tracking error of the quadratic bowl minimum on the noisy quadratic bowl task of Section
5.1 Values averaged over the last 10% of training before the stated training milestone. The theorctically best possible loss using Newton's method is also listed. The version of L-BFGS is one with stochastic
modifications from (Schraudolph et al.) 2007), instead of the original from (Nocedal & Wright 1999 Out of the optimizers with reasonable time complexity for scaling to large neural networks (ie. O P(nloogo n) or less,) LODO performs the best.
Training loss
Time complexity
Optimizer
100k steps
300 sec.
Adam Kingma & Ba 2014
15.28 + 0.07
15.26 + 0.08
Momentum
16.59 0.08
16.56 : 0.05
RMSprop (Hinton et al. 2012
22.37 + 0.06
22.47 = 0.13
O(n)
Yogi (Zaheer 2018
15.35 +
15.16 = 0.05
L-BFGS (Schraudolph) et al. 2007
49.30 1.04
40.60 = 1.40
O-LBFGS (chraudolph el al.
2007
13.96 0.08
10.80 =
L2L.RDDGDD [nnryychoiczz et al.
2016)
14.79 + 0.08
14.81 + 0.10
lognn))
LODO (ours)
8.99 + 0.05
10.05 + 0.22
BFGS BBoydeen 1970
diverged
diverged
2 O(n²)
Levenberg Marquardt Levenberg
1944
7.40 + 0.02
7.35 + 0.07
Newton Method (Optimal)
7.41
behavior invariant to gradient magnitudes (ignoring hyperparameter e), meaning LODO's step size behavior is equivariant to gradient magnitudes. This pairs well with the scaling properties of the noisy quadratic bowl problem, which then allow LODO to achieve identical noise-rescaled training loss regardless noise magnitude.
Pretrained and Frozen Preconditioner. To test the importance of LODO learning G(O,)) on the fly, we froze G(O,) after using LODO for 100k steps as before and then tried to use this "pre-trained" LODO on a new quadratic bowl. Within 10 steps, the loss diverged 4.997 1022, indicating that LODO is best trained the fly rather than beforehand task distribution.
5.2 Rosenbrock Function
2.0
We probe the behavior of LODO with a small test task of finding the minimum of a rescaled Rosen- brock function f(x,1) = 0.01 (- - 1)2 + (x² y) which has no local minima and one global minimum at (z, = 1). We initialized the optimizers at (x, = (-0.5, and gave them 200 steps to run. The trajectory taken by LODO, shown in Figure 3 is similar to the short timescale dynamics of other opti- mizers using momentum, in that tends to overshoot and then correct itself in an oscillatory manner, due to its initialization with the momentum optimization strategy. Learning curves in Figure II and losses in Table of Appendix G show the performance of all the optimizers on this task.
1.5
* Initialization
Momentum
RMSprop
Adam
0.5
Yogi
LODO
* Minimum
0.5
2.0
1.5
1.0
0.5
0.0
0.5
1.0
Figure 100 step trajectorics of various optimizers on the Rosenbrock function minimization task of Section
5.2 The red star marks the initialization and the green star marks the location of the global minimum.
5.3 Image Generation
We design a challenge for LODO-an an autoregressive image generator for MNIST. We intend demonstrate the effectiveness of LODO at scale when used to train a semi-realistic neural network with lots of parameter

---

Published in Transactions on Machine Learning Research (09/2023)
2016 to generate MNIST images Leeun et al., 1998), and is fully described in Appendix F.2 We tested LODO alongside variety optimizers for 300k steps, though we could not get any quasi-Newtor methods to converge on this task. We do not compare against K-FAC (Martens & Grosse 2015b) because this would require matrix inversions of time complexity much larger than the number of CNN weights. Learning curves in Figures and losses Table show that. LODO trains at speed that competitive against other optimizers. Figure 10 in Appendix some imitation MNIST images randomly sampled using this model.
sharing. The task is similar to training a PixelCNN (ord et al.
F.2 provides
Table 2: Negative log likelihoods in nats per pixel after training for 300k steps on the MNIST image generation task of Section 5.3 with every optimizer. Values are averaged over the last 10% of training before the stated training milestone. The top 3 optimizers are underlined for each metric.
Training loss
Test loss
Optimizer
300k steps
50k sec. (~ 14 h.)
300k steps
50k sec.
Steps / sec.
Adam
0.830 = 0.005
0.859 = 0.009
0.809
0.854
7.08 0.03
Momentum
0.708 + 0.005
0.698 + 0.005
0.689
0.685
7.10 0.03
RMSprop
0.917 + 0.010
0.920 1 0.014
0.931
0.899
7.10 1 0.02
Yogi
0.683 + 0.002
0.677 = 0.003
0.686
0.674
7.42 + 0.02
LARS You et al. 2017
0.701 + 0.006
0.702 + 0.006
0.688
0.688
5.89 + 0.02
LODO (ours)
0.696 1 0.004
0.698 + 0.005
0.689
0.689
5.64 +: 0.02
0.95
0.9
0.90
Momentum RMSprop Adam
training
0.8
training
0.8
0.80
Yogi
LARS
0.75
LODO
0.7
100000
200000 stop
300000
100
100000
200000
300000
time (h)
stop
Figure 4: Training loss learning curves on the MNIST image generation task of Section 5.3 Left: By step. Middle: By time. Our timing setup is described in Appendix H Right: Validation loss by step, using a subset of 64 images excluded from the training data. Each image provides 784 pixel colors to predict, so the validation datasel effectively consists of 50176 samples.
Using this setup, we also study the contributions of various components of LODO to its performance by replacing components to observe performance change, as detailed below. For example, we replace the Adam meta-optimizer with SGD to form a new version of LODO (which we call "LODO-SGD"); its performance is shown in Table 3 Other modifications are listed below.
5.3.1 Residual Connections
We would like to show that there exist opportunities to further develop the architecture of LODO. We modify the matrix decomposition in Section 3 G = opp (I 0) G(O)T DŌ(() (I 0)" by adding learned diagonal matrix D in the middle and changing (0)) to a product of many weighted permutations each added to the identity matrix. The neural network which G(Ø) represents now has residual connections, and the initialization is modified accordingly. Losses Table show that this version (which we call BLODOO-Reiduall performs only slightly worse than LODO, reflecting the potential for further development in the architecture design of LOOD..
10

---

Published in Transactions on Machine Learning Research (09/2023)
Table 3: Negative log likelihoods in nats per pixel after training for 300k steps on the MNIST image
generation task of Section 5.3 with ablated versions of LODO.
Training loss
Test loss
Optimizer
300k steps
50k (~ 14 h.)
300k steps
50k sec.
Steps
sec.
LODO
0.696 0.004
0.698
0.005
0.689
0.689
5.64 0.02
L.DOODiagonal (Amid et al.
2022
Diverged
Diverged
Diverged
Diverged
9.92 0.09
LODO-GGobal Baydin et al.
2017
0.770 + 0.035
0.919 + 0.139
0.747
0.801
9.92 +: 0.03
LODO-Residalls
0.701 0.004
0.750 0.008
0.693
0.741
3.31 0.03
LODO-No-Momentee
0.753 + 0.007
0.756 + 0.007
0.750
0.752
5.46 = 0.06
LODO-SGD
0.709 0.004
0.714 0.004
0.698
0.707
5.44 0.02
5.3.2 Simpler Approximate Hessians
We presumed that the representability result of Section 4.3 is only useful because LODO's strength comes from the flexibility that G(O) gives in configuring pairwise interactions between parameters. We therefore expect that using a simpler form of Hessian should hurt the performance of LODO. We test two simpler forms of G()): G(0) = andiag () (which we call "T.OOO-Diegonal)) for 0 E R initialized to vector of ones, similar to (Amid A initialized to in (Baydin et al., 2017 Losses in Table 3 show that the original version of LODO performs the best, verifying our hypothesis.
2022) and the even simpler G(0) ag01 (which we call "LODO-Global") for
5.3.3 Effects of Using EMAs of Gradients
Similarly to how momentum works for SGD, LODO's input gradients are preproccessed by accumulation into EMAs. To test our claim Section 3 that momentum benefits LODO, we try 8 separate momentum decay rates spaced in logarithmic grid from no momentum the optimal amount of momentum found (3 0.9343), and test each decay rate decay rate, increasing the effect of momentum improves LODO. We also try removing momentum completely (we call the modified version
Figure 5 shows clear trend that at least up to the optimal
results are shown in Table
5.4 Image Classification
0.74
We conduct an experiment on image classification with Resnet- 18 (He et al. 2016) CIFAR10 (Krizhevsky et al.) 2009). We use the standard Resnet setup CIFAR10 by replacing the 7x7 convolution with 3x3 one, and removing the maxpool in the first convolutional block. We use the standard data augmentation and a batch size 2048.
1055
0.72
0.70
In Figure and Table 4 we present more detailed view of the performance of the models, demonstrating the results of our experiment. We observe that LODO performs competitively with the best-performing optimizers (Adam, Yogi, Momentum, and LARS), and noticcably outperforms RMSProp. The "Z On"²)" family of optimizers cannol. be run on tasks of this scale. Since there are many crucial regularization techniques in computer vision, such as data augmentation and weight docay, a more in-depth study of how LODO interfaces with them fruitful direction for future work.
0.4
0.6
0.8
beta
Figure 5: LODO's training loss as a fune- tion of the momentum decay coefficient 3, averaged over the last 10% of 300k steps, for the image generation task of Section 5.3 Momentum improves LODO. Error bars de- pict LODO's uncertainty from Table 2
11

---

Published in Transactions on Machine Learning Research (09/2023)
1.0
validation accuracy
0.8
Momentum
training loss
RMSprop
0.6
Adam
training
LARS
0.4
Yogi
O-LBFGS
0.2
LODO
0.0
1000
3000
1000
2000
3000
stop
time (h)
stop
Figure 6: Training loss learning curves on the Resnet-18 CIFAR10 task of Section 5.4
Left: By step.
Middle: By time. Our timing sctup is described Appendix H Right: Validation accuracy by step.
Table 4: Training losses and test accuracies after training a Resnet-18 for 3000 steps (122.88 epochs) or 24k seconds (6.7 hours) on CIFAR10 classification task Section 5.4 with every optimizer. Values are averaged over the last 10% of training before the stated training milestone.
Training loss
Test accuracy
Optimizer
3000 steps
24k sec. (~ 6.7 h.)
3000 steps
24k sec.
Steps / sec.
Adamn
0.326 + 0.008
0.446 0.016
0.873 = 0.002
0.863 0.003
0.0793 + 0.0003
Momentum
0.386 + 0.010
0.563 = 0.031
0.881 0.006
0.864 + 0.008
0.0794 + 0.0002
RMSprop
2.380 = 0.375
2.077 = 0.191
0.434 = 0.043
0.466 0.040
0.0794 + 0.0001
Yogi
0.398 + 0.006
0.552 + 0.022
0.885 0.003
0.869 +: 0.005
0.0791 11 0.0004
LARS You et al. 2017
0.296 + 0.026
0.403 + 0.034
0.872 = 0.006
0.864 4 0.007
0.0788 1 0.0003
LODO (ours)
0.624 + 0.027
1.377 + 0.110
0.845 = 0.009
0.674 + 0.035
0.0316 + 0.0003
6
Discussion
LODO is a cross between L20 methods and quasi-Newton methods, retaining significant advantages of both classes of optimizers. With LODO, bring ideas from each class of optimization methods to the other.
Relative to quasi-Newton methods, LODO offers advantages associated with the use of meta-optimizer neural optimizer. Crucially, LODO determines its inverse Hessian estimate using all past gradients, whereas most other quasi-Newton methods use a finite history of them. This allows LODO to retain information about the inverse Hessian for much longer than other methods. This is useful if the gradients contain enough noise that useful signals can only be oblained by accumulating information from many gradient samples. Our theory further shows that the sparse linear neural network in LODÓ is optimal a certain extent: it can probably represent all sparse lincar neural networks smaller by logarithmic factor-allowe class of inverse Hessians. Our image generation task demonstrates that LODO succeeds in semi-realistic stochastic nonconvex task where other quasi-Newton optimizers diverge. Due to our use of L,20, LODO can be further developed in the design of its linear neural network, which makes it amenable to further research and refinement.
for huge
Relative to L220, LODO offers advantages associated with the restructuring of the outer and inner loop into single loop. Most importantly, our modification to L20 alleviates the requirement for meta-training time and the training task distribution. This is at the cost of increased inner loop unrolling truncation bias, but it takes advantage of this sacrifice by resolving the need to compute second-order gradients. LODO still inherits issues of high memory usage and slow step computation from L20 methodology though. Our theory offers some understanding of how LODO learns to optimize: the Hessian approximation error decays as learning progresses. We import the idea from quasi-Newton methods that the gradient of one parameter can affect the step for another, which comes from the presence of off-diagonal elements in the Hessian. As shown Section 4.3 LODO presents an efficient way of approximating subsets of the O(n²) possible pairwise parameter interactions in O(n log n) time. Such interactions completely ignored in the design of most.
12

---

Published in Transactions on Machine Learning Research (09/2023)
L2O and more mainstream optimizers, yet our image generation task demonstrates their importance, evidenced by the improved performance of LODO over ablated versions as well as SGD.
7 Conclusion
Through LODO, we provide a new way using L20 methods online without any meta-training to perform quasi-Newton optimization. We introduce the strengths and advantages of quasi-Newton methods and L,20 to each other and combine them in harmonious manner. LODO's abilities showcase the applicability of online L20 methods with nested optimizers to the training of modern neural networks. Our unique methodology serves stepping stone for the further development and use of L20 in quasi-Newton optimization and vice versa.
8 Acknowledgements
We would like to acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center for providing HPC resources that have contributed to the research results reported within this paper.
Research sponsored by the United States Air Force Research Laboratory and the United States Air Force Artificial Intelligence Accelerator and was accomplished under Cooperative Agreement Number FA8750-19-2-1000 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the United States Air Force or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.
This work also sponsored in part by the the National Science Foundation under Cooperative Agreement PHY-2019786 (The NSF AI Institute for Artificial Intelligence and Fundamental Interactions, http://iaifi org/
References
Ehsan Amid, Rohan Anil, Christopher Fifty, and Manfred K. Warmuth. Step-size adaptation using exponen- tiated gradient updates, 2022. URL httpps//arxxi. http://rxivv.or//aa///2222 00145
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthow W Hoffman, David Pfan, Tom Schaul, Brendan Shillingfod, and Nando De Freitas. Learning learn by gradient descent by gradient descent. In Advances neural information processing systems, pp. 3981-3989, 2016.
Juhan Bae, Paul Vicol, Jeff Z. HaoChen, and Roger Grosse. Amortized proximal optimization, 2022. URL https://arxiv.org/ abs////////// 00089
Atilim Gunes Baydin, Robert Cornish, David Martinez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. 2017. doi: 00.48550/ARXIV.111
URL
https://arxiv.. wttp:/www..r//ab//////////// 04782
Jeremy Bernstein, Arash Vahdat, Yisong Yue, and Ming- Yu Liu. On the distance between two neural networks and the stability of learning, 2020. URL http:://aarxxv..rr///////2222220
C. G. Broyden. The Convergence of Class Double-rank Minimization Algorithms 1. General Considerations. IMA Journal of Applied Mathematics, 6(1):76 -0776 03 1970. ISSN 0272-4960. doi: URL https: /tops:///oo..oo org/1000 1093/10amat//55
1aaaaat/.... 1..1.
Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin.
Learning to optimize: A primer and benchmark, 2021. URL http///awww...g//////////...1
13

---

Published in Transactions on Machine Learning Research (09/2023)
Thomas George, César Laurent, Xavier Bouthillier, Nicolas Ballas, and Pascal Vincent. Fast approximate natural gradient descent in a kronecker-factored eigenbasis. In NearIPS, 2018.
Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-newton methods for training deep neural networks. Advances in Newral Information Processing Systems, 53:2386-23310 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on compuler vision and pollern recognilion, pp- 770 770-778, 2016.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6e. htttp//www.cs. http:://wwwccs.oooooooooooooo... toronto. 2022 08-28.
siarrre__sid__dd_eeeeee___e pdf 2012. Accessed:
Prateek Jain and Purushottam Kar. Non-convex optimization for machine learning. Foundations and Trends0 in Machine Learning, 10(3-4):142-33 363, 2017. ISSN 1935-8237. doi: 0..16112200000000 URL http://dx.dee doi. www.pd/oooo.......ooooo///// 1561/2200000588
Li Jing, Yichen Shen, Tena. Dubcek, John Peurifoy, Scott Skirlo, Yann LeCun, Max Tegmark, and Marin Soljačíć. Tunable efficient unitary neural networks (EUNN) and their application to RNNs. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Reseorch, pp. 1733 1741. PMLR, 06 11 Aug 2017. URL petps://proceediie
mlr. press/v70/ jttr////ingaa..t...
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6800 69800 2014.
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. In Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS'17, pp. 972 981, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 9781510860964.
Elena V. Konstantinova and Artem Kravchuk. Spectrum of the transposition graph, 2022. URL https: 03153
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Thomas Laurent and James von Brecht. Deep linear networks with arbitrary loss: All local minima are global. In Jemnifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2902 2907. PMLR, 10 15 Jul 2018. URL sttps::/proceeeiinn
mlr,
html
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2) 2324, 1998. doi: 10.1109/5. 7.76791..
Kenneth Levenberg. A method for the solution of certain non-lincar problems in least squares. Quarterly of applied mathematics, 2(2):164-168, 1944.
Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint arXiw:1606.0188 01885, 2016.
Ke Li and Jitendra Malik. Learning to optimize neural nets. arXiv preprint arXiv: 1703. 1703000103 2017.
Rosanne Liu, Joel Lehman, Piero Molino, Felipe Petroski Such, Eric Frank, Alex Sergeev, and Jason Yosinski. An intriguing failing of convolutional neural networks and the coordeony solution. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cosa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annuul Conference on Neural Information Processing Systems 2018, NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 9628 9639, 2018. URL https Aww.raatt.t................ html
Kaifeng Lv, Shunhua Jiang, and Jian Li. Learning gradient descent: Better generalization and longer horizons. In Doina Precup and Yoe Whye Tch (ods.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 2247-2255. PMLR, 06-11 Aug 2017. URL https::/proceedingss pta.a/.pree///////.....tt
14

---

Published in Transactions on Machine Learning Research (09/2023)
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvature, 2015a. URL http:s//arxx..orrraa///0.0. wrg./bs////3......
05671
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approximate curvalure. In International conference on machine learning, pp. 2408 2417. PMLR, 2015b.
James Martens and Roger Grosse. Optimizing neural networks with Kronecker-factored approximate curvature. Tn Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 2408 2417, Lille, France, 07 09 Jul 2015c. PMLR. URL httpps://proceeedings mlr www.mmmrrrreerr.e.. pgress/v37/martess// html
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, C. Daniel Freeman, and Jascha Sohl-Dickstcin. Un- derstanding and correcting pathologies in the training of learned optimizers, 2018. URL https :
//arxtv.org//b//111// 10180
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha SohhlDicksteinn Understanding
and correcting pathologies in the training of learned optimizers. In Proceedings of the 36th International Conference on Machine Learning, ICML '19, pp. 4556-4565, Long Beach, CA, US, 2019.
Luke Metz, Niru Maheswaranathan, C. Daniel Freeman, Ben Poole, and Jascha Sohl-Dickstein. Tasks, stability, architecture, and compute: Training more effective learned optimizers, and using them to train themselves, 2020. URL htttp:://aax/:i http///axvv.orr/a///////// 11243
Ted Moskovitz, Rui Wang, Janice Lan, Sanyam Kapoor, Thomas Miconi, Jason Yosinski, and Aditya Rawal. First-order preconditioning via hypergradient descent, 2019. URL htttps://aaxav..rr//bbb.s
Jorge Nocodal and Stephen Wright (eds.). Large-Scale Quasi-Newton and Partially Separable Op- timization, pp. 222 249. Springer New York, New York, NY, 1999. ISBN 978-0-387-22744--. doi:
10.100770-387-2220 2274--3 9. URL https://doi.org// 1001000000000000022227700000
Aäron van den Oord, Nal Kalchbrenner, Oriol Vinyals, Lasse Espeholt, Alex Graves, and Koray Kavukcuoghu. Conditional image generation with pixelenn decoders. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS116 pp. 4797-4805, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 9781510838819.
Eunbyung Park and Junier B Oliva. Mela-curvature. Advances in Neural Information Processing Systems, 32, 2019.
Jack Parker- Holder, Luke Metz, Cinjon Resnick, Hengyuan Hu, Adam Lerer, Alistair Letcher, Alex Peysakhovich, Aldo Pacchiano, and Jakob Foerster. Ridge rider: Finding diverse solutions by following eigenvectors of the hessian, 2020. URL /cctpa//arxxv..oo http:///aaraavv.g///////././/// 06505
Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, (586))386, 1958.
Nicol N. Schraudolph, Jin Yu, and Simon Günter. A stochastic quasi-newton method for online convex optimization. In Marina Meila and Xiaotong Shen (ods.), Proceedings of the Eleventh International Conference on Arlificial Intelligence and Slatislios, volume 2 of Proceedings of Machine Learning Research, pp. 436 443, San Juan, Puerto Rico, 21 24 Mar 2007. PMLR. URL htttps:/pproceednng. mlr. mlr.press/ v2/schraudolph07a.u html
Shiliang Sun, Zehui Cao, Han Zhu, and Jing Zhao. A survey of optimization methods from a machine learning perspective, 2019a. URL httpee///aaii..orr//b/////6 wttp://////...//eeereer/
Shiliang Sun, Zehui Cao, Han Zhu, and Jing Zhao. A survey of optimization methods from a machine learning perspective. IEEE transactions on cybermetics, 50(8):3668 3681, 2019b.
Zhewei Yao, Amir Gholami, Sheng Shen, Mustafa Mustafa, Kurt Keutzer, and Michael Mahoncy. Adahessian: An adaptive second order optimizer for machine learning. In proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 10665- 2021.
15

---

Published in Transactions on Machine Learning Research (09/2023)
Yang You, Igor Gitman, and Boris Ginsburg. Large batch training of convolutional networks, 2017. URL httpss://ariiis
http:///aaxii..ooaa//////be www.orr////////ooo /108 038888
Manzil Zaheer, Sashank J. Reddi, Devendra Sachan, Satyen Kale, and Sanjiv Kumar. Adaptive methods for nonconvex optimization. In Proceedings of the 32nd International Conference on Newral Information Processing Systems, NIPS'18, pp. 9815 9825, Red Hook, NY, USA, 2018. Curran Associates Inc
A Elaboration on Hessian Learning Dynamics
A.1 Derivation of Training Dynamics
This section gives derivation of the result that under the problem setup of Section 4.1 LODO follows the Hessian learning dynamics
A4+1 A. D H²
bi+1 A.b. 8t.
6
where A, = - and b. = xz - zz as long as G(0+) is parameterized as a dense matrix filled with elements of 0,, and no momentum is used.
We first let b, be x; 27. Following Equation
3 the loss at time t is then
1 T Hb.
C
(17)
2
The gradient is then computed to be
df
Hb:
(18)
dæ,
The step taken then produces the next parameters:
F++1 =0; - Hb.. Subtracting 2!+1 = xx + 82, we get the recurrence for b..
(19)
I++1 2/+1 =I, x; 8, -(O,)
(20)
1i+1 =b; H(.,) St
(21)
=(1 C(O)))HH
(22)
A,b, 8t.
6
The loss at time + computed to be
b (+1 Hb++1
(23)
(A,b. - H - 8t)
(24)
2
(II G(O,) s,) ((II-(())H)), -s).
(25)
LODO also computes a step of 0, using the loss on the next step. Since the elements of 0, are just a rearrangement of the elements of G(O,) in our derivation, an update 6, can be treated instead like an update of G(O.). The gradient 44t1 with respect to G(O.) then computed to be
dh+t dG(O,) = H(A,b, 8, b. H
H(II - G(O,) s.), H
(26)
(27)
Hb.. H
(28)
16

---

Published in Transactions on Machine Learning Research (09/2023)
and the step of G(),) is
G(0+41)=G(())) +
(29)
resulting the recurrence for A::
A+11 =I G((0+1)
(30)
=I - (G(O,) + aHHbbt1b H
(31)
=A. aHH by H².
A.2 Validity of Approximation Argument
This section gives justification for the approximation in Section 4.1 of the long term trajectory the recurrence
A++1 = - - -aHb, a.Hbb+1,, H²
bi+1 = A.b, 81
by replacing with
A/41 A/ - --HH d² e H²
(32)
b/41 Al b, St
(33)
when a is small and the initial conditions at to are the same: A.,- = A% and b,, =, = 0. We will work in the bounded noise case ||s/||2 < 00, where ||bll|2 is upper bounded by some ||4;, ll dependent constant dmax due to exponential docay in Equation 33 In the case where the noise is not bounded, a probabllistic analysis be done instead, though do not provide one.
To justify this approximation, prove that the spectral norm of long term deviation corrected for learning rate is small over short distances r, in the following theorem:
Theorem A.1.
lim lim = Atottr/a Ar-ir//jll2 =0. 0
(34)
In other words, the local movement of A rescaled for learning rate is unaffected by our approximation when the learning rate is small.
Proof. Our proof strategy as follows:
1. We will first define variables to denote bounds the movement of A and the approximation error in b.
2. We will show that these variables bound each other, and then we will combine these bounds to create a single recursive bound on the movement of A.
We will characterize the bound's growth and will turn out that A has a maximum movement speed along any trajectory of sufficiently short length.
4. Due to the slow movement of A, we can deduce that the approximation error in b increases at bounded rate.
Since approximation errors in A are an accumulation errors in b, we will show that deviation between the true and approximate trajectories is quadratic the distance along the trajectory.
6. We conclude that the approximation vanishes for short trajectories and small learning rates.
17

---

Published in Transactions on Machine Learning Research (09/2023)
First part. We first define the maximum drift in A
max fo
||,, A% l12
(35)
up to time difference At for 0 S A R/a for some chosen small constant trajectory length R > 0. We will pick R later. We will also define the maximum error in
<b
max fo
|b, b1
(36)
up lo the same time.
Second part. For the bound in one direction, we have that for all T such that to S to + At,
||6,+1 6/+1/12 = ||A,b, 8, (Ai b', 8,)112
(37)
|| A, A b/12
(38)
< A,b, -A b- + + b- A by ll2
(39)
A, - A2211211b,11 + + 112l b, b1112
(40)
SeAmo+aellbrll + 11.4 1|211,, b4 ll
(41)
using the triangle inequality and sub-muliiplicativity for the spectral norm || 11.1. This is recurrence in ||, - -2,122 by induction we have that for to S S to At 1,
||b, - b', SEA.o+D
|
11-111
16, 112
(42)
TI to
such that we produce the bound
4b40+A411 SCA.O+
max
||44 117-1-11 |b,,11a
(43)
Ar4+
Ti=
SEA,totr fo Arr++
max
Σ Ti=to
|| 112 1 (116/ 112 + =b.00+0)
(44)
SCA.ooAi
| to
Hta Ae (Funx + (b.to+tt)
(45)
To
Co.o Ac+1 + bmax
SEA,otAr
(46)
1
A/o 12
EA. At maax
4b44+4441 || 6A,o0-1
(47)
Now, we show reverse bound: for all 7 such that to ST S 1o + Al, we have
|A 46,l2 = =I|A, aHb. + H² A/il12
(48)
SIA, A 112 H | b 1++1
(49)
A||A, A 1l2 + a
H [ ||2 (b.o+++++)(((((++ + =6.00+A4+1)
(50)
A||A, - A 1l2 + a H
1 (6max + =0.0++++1)
(51)
By induction we have for to < r < to + 11,
| A/e 1/2 Sal
H (T - (0max + +bb.o+4441)
(52)
such that we produce the reverse bound
AA
Sa
H ( 1) + Ab.to++t1))
(53)
18

---

Published in Transactions on Machine Learning Research (09/2023)
Third part. recurrence
Substituting the bound in Equation 47 into the bound in Equation 53
produce the
AAto+rr+1 Ia| H ( 1)
1
A
(54)
| 12 Eti
- 1|A4, 2
=a| H max
1 11
(55)
A 1l2 cA.ioAAl
=f(EAro+a)))
(56)
where
(1
1- A 12
f(z)=a| H (
(At
(57)
1 1|44 1122
bound the movement of A, we must use the fact that when
4 A ll
0 At
(58)
27
H
12
maxx
the function f maps the interval
Lac
0, a
max (t + 1)
0. [ 114 [12)
0.
(59)
subset of itself. Since at At 0 we have AA 0 Ian. and we also have Isc S Lac+1, we may deduce by induction on At that cA,ot Tai long Equation 58 holds, and thus there is a bound
1 (1 (1-11
CAtt+Ar S
812 max
(60)
the movement speed of A as long as Equation 58 holds.
Fourth part. Note that we have assumed that 0 S At S R/aa for some constant R which we have not yet picked. By choosing
1
A 112
R
(61)
27
H
we may always guarantee Equation 58 which implies Equation Then when Equation 60 is substituted into Equation 47. we create small bound on the approximation error b which begins at zero and increases with time,
9
313
max ( + 1)
0b,6+A111
||4 to
4
112
312 max (At +
(62)
0d // 1)
(63)
3R At + +1
for 0 < At < R/a. This also holds trivially for At = -
0b.1+A111 = 0, so we may re-index to have
Eb.to At 5 atmax At
(64)
3R -A
for 0 At S R/a++ + 1. Since the right side of Equation by a linear function with the same endpoints
64 convex in At over At E [0, R/a], we may bound
abmax At
(65)
2R
for Al < R/a.
19

---

Published in Transactions on Machine Learning Research (09/2023)
Fifth part. Finally, this bound approximation error in b to bound approximation error in A.
A A A A2+1l21
= =1|Alo- At aHb to b% to H H² - (4 aHb
b to A++1 to A
H
(66)
< A Ato-1t Alotarlle
H 3 (bbbo bottr by b
b to talll
(67)
A Alotall
+ (16b - b% -soll
+ +1 by 1leettlllllbbbttaa
(68)
AloA Aottrel2 + A111+ (26 + (b.0+
(69)
By induction, we find that the approximation error of A is quadratic in time for short times 0 s A S R/a,
Ar-1
||A+++ Alotall2
0 0 a a|| || (2bmax 6..0+
(70)
Ár=0
A1 1
A + 1) (2+ a
A A(+1))
(71)
max
2R
2R
Ar=0
a²
H 332
At (2+ At)
(72)
max
2R
2R
At=1
a A12
aAl)
62
2
(73)
2R
2R
Sixth part. Now take At [r/a], which for r - 0 is eventually S R/a required. As we sought prove, the learning rate rescaled approximation error of the local drift direction and speed goes to zero:
a² a²Lr/a]²
2 aLr/a]
lim lim - A2ottr/ad A 0-00000
Aoott/ojll2 lim lim
H
182
max
(74)
a0
2R
2R
lim r00
H
322
max
2
(75)
2R
2R.
-0.
B Proof that G(0,) has a Negative Eigenvalue
This is true, because we can substitute A = G(O.) and H in following lemma: Lemma B.1. Let A and B be symmetrie, full-rank at least one negative eigenvalue. Then, the product AB has at least one negative eigenvalue.
matrices. Let A be positive-deff definite and B have
Proof. Let x be an eigenvector of B with negative eigenvalue X. Then, we have
x T Ba (A-1/2x) T 11/2AA (A-1/2)) <0
(76)
meaning that the symmetric matrix 1 A1/2 cannot possibly be positiie-semidefnite, and must have at least one negative cigenvalue X' with cigenvector x'. Then, we have the cigenvalue equation
AB
1/2 -/2 2 A2 BA/2) x'
(77)
-/2
(78)
which shows that. AB has negative eigenvalue X
7
20

---

Published in Transactions on Machine Learning Research (09/2023)
C Proof of Representability Theorem
This section gives proof of the representability theorem stated in Section 4.3
Theorem 4.2. Uniformly sample permutations P. and create block-diagonal matrices B(0 where every block is 2 2, and whose block contents are listed by the parameters 0 Use these to construct the LODO subnelwork (()) as in Equalion & with some depth N and hidden dimension û. Construcl any linear neural network F with input dimension, output dimension, number of connections per layer at most n, at most k incoming and at most k outgoing connections for every newron, depth d, and otherwise any arrangement of connections. Then, there is a probability of at least
U. Add[og, kl 1)
1 - R.N
6 2"
7
(15)
that (())= - F for some 0.
Proof. Our result comes in two parts: the first shows that G( can represent arbitrary permutations, and the second shows that we can pick these G(O) permutations and interleave them with block diagonal matrices to create a deeper G()) network which manifests any desired neural network. We use the terms fanin and fanout to mean the number of incoming and outgoing weights into and out of a neuron, respectively.
First part. Assume we would like to apply a given larget permutation to elements using G()) II,", P( consisting of N layers with randomly chosen permutations P.. Our goal is perform the target permutation given P. by controlling the block diagonal matrices (() The form of G(0) from Section 3 is
N G())) = II B 1 )
P.
2
1=1
which can be rewritten as
N G(0) Q1 II O B( Qq
QN P., Qi-1= P
(79)
1=1
with random independent uniform permutations Q: instead. For each block in the matrix ((0))), may restrict ourselves to two options: to swap or to not swap the pair of indices. The conjugation by random permutation Q; then shuffles these pairings, such that applying G(O) is equivalent to repeatedly randomly pairing up indices for optional transposition instead, and then applying a final permutation Qi- We will work under this new equivalent formulation, since it is more amenable to analysis.
Let us choose to apply each transposition with probability 1/2. Then, the expected entropy of G(O) given the whole sequence of pairings is at least. log n! e(Nn/2, ū) under Definition 4.1 In other words, the expected KL divergence of this distribution of G()) from the uniform is at most e(Nn/2, n). Then by Pinsker's incquality, the expected total variation distance from the uniform is then at most
N (N
(80)
This guarantees that at most
1 6 (N 2
ily
(81)
possible target permutations have probability density of zero, in expectation, which is then upper bound the number of inaccessible target permutations. This means the probability that all target permutations are accessible is then at least
1 fll ((Nn/2
(82)
21

---

Published in Transactions on Machine Learning Research (09/2023)
B G2
B2
G.
B
00 000
000
2002 09000
Figure 7: In this diagram, á = 8 and p = 2, for illustrative purposes. Left: Visual depiction of how a fanout forest followed by a fanin forest can represent arbitrary sparse connections. Right: Visual depiction of how p+1 chained copies of G(O) networks left-multiplied by block matrices diagonal can manifest forest of fanout trees. G; are permutations implemented by G(0) networks allowing for arbitrary connections, and B, are block diagonal matrices which create the necessary fanouts. Data flows from left to right in the illustration, though successive operations are written out right to left when using mathematical notation. The largest fanout in this pattern of connections is 3, which is less than 2 = 4; all the fanins are 1.
Note that the leftmost Q1 in Equation 79 merely introduces bijection between target permutations, and does not change how many are accessible.
Second part. Suppose we would like to represent target permutations using p independently generated G(0) networks each of depth M. Equation 82 lower bounds the probability that each network can represent its respective permutation. Then the probability that all of the p target permutations are accessible by their respective copies of G()) union bounded by
1 1- pñly (MM/2.
(83)
2
where the union over the probability that each copy fails to represent its target permutation. Given that this succeeds, we now need chain these permutations together with block diagonal matrices to represent arbitrary neural networks F, with Equation 83 lower bounding the probability of failure.
Suppose we are successful in representing any combination of larget permulations using p distinct indepen- dently generated G()) networks of depth M. Then, since each G(0) network's final (leftmost) operation is a block diagonal matrix, applying an additional block diagonal matrix afterward does not affoct the operations that G(0) can represent, since the set of block diagonal matrices we use is closed under matrix multiplication. Importantly, each block matrix can be used to copy a value from one index into two or to add two values together to leave one, creating fanin or fanout in the network. Then, interleaving p chained copies of G(Ø) with block diagonal matrices feft-multiplcs for total depth of (p+ 1)M therefore creates an aggregate operation which can still be represented by a single (())) network of depth 1)M. This aggregate operation has up to ñ arbitrary connections from input nodes to output nodes, with either all fanin at most and all fanout at most 2P, or all fanout at most 1 and all fanin at most 2P. This is done by building a forest of fanin / trees like illustrated on the right side of Figure 7
If we compose such a G(0) network of depth (p + 1)M with fanout up to 2n together with a G(0) network of depth (p +p+11 1)M with fanin up to 2P, then we may represent any sparse matrix structure with at most ñ nonzero weights and maximum fanin and fanout at most 2", using G()) network of depth 2(p 1)M. This construction is illustrated on the left side of Figure 7 We may adjust the final (leftmost) block diagonal matrix on the fanout side to change the values of the ñ arbitrarily positioned weights in the desired sparse matrix. Therefore, any sparse matrix with at most ñ weights and max node indegree and outdegree at most. k can be represented by a G() of depth 2([log, k] + 1)M.
Then, any linear neural network of depth at most d, at most ñ weights per layer, and maximum fanin and fanout of at most k can be represented by (()) network of depth 2Md( k| 1), by composition
22

---

Published in Transactions on Machine Learning Research (09/2023)
of sparse matrices. The probability that all of this is successful is merely the probability that all the 22o k] + permutations can be represented, which by Equation 83 is at least
1 1- 25!Md((oog k1 + 1/ ( (M
(84)
Thus in summary, if we randomly generate a G()) network depth N = 2Md k] 11 for fixed constants k d, and M, ñ neurons per layer, and block size f = 2, then there a probability of at least
- (Mn/2, =1 R!N 1 2
nN
1 1 1- A!N
[d[ k +1) n
(85)
that (()) can represent every possible linear neural network of input and output dimension S n, depth d, at most ñ nonzero weights per layer, and max
of at most k.
D Hessian Learning Local Minima (LODO can Generalize)
Laurent & von Brecht 2018) gives a theorem showing that for dense lincar neural networks convex losses where each layer is at least wide the input output layer, all local minima in the neural network weights are also global minima. If we simplify LODO by approximating the inverse Hessian with a full dense matrix G(O:), then this theorem applies to the Hessian approximation error ||z - GI which the rescaled error [DB ||? used in Section 4.1 a proxy for. Thus we may expect that any inverse Hessian approximation which LODO could converge to of similar high quality to the best possible inverse Hessian approximation.
E
Hyperparameters
In every experiment, we tuned the hyperparameters each optimizer using a genetic algorithm of 10 generations and 32 individuals per generation (16 individuals per generation for the Resnet CIFAR10 task). Each hyperparamter was rescaled using x + In x if the hyperparameter was a learning rate and + In(1 - x) if the hyperparameter was decay parameter, so that the genetic algorithm would operate in more well-behaved hyperparameter space. Starting from the default hyperparameters, each generation's 's mean hyperparameters were added to some Gaussian noise to create mutated hyperparameters for each individual, where the standard deviation of the noise was generation-dependeet and followed specific schedule. Each individual performed a generation-dependent number of steps of optimization, also according to schedule. The next generation's 's mean hyperparameters were chosen to be the mean hyperparameters of the better performing half of the previous generation, as judged by the average training loss during the last 10% of training. We also halved all the learning rates (equiv. initial learning rales for LODO versions) after tuning for the image generation task because tests showed the loss to diverge if training time horizons were longer than 8k steps. Since LODO is a random optimizer, we used different randomization seed for every individual. Table 5 lists the paramcters of the tuning schedule for each task. The tuned hyperparameters can be found in Table
F
Task Setup Details
F.1 Noisy Quadratic Bowl Task Details
This section fully explains the details of the setup of the noisy quadratic bowl task of Scction 5.1 This 100 parameter lask consists of a quadratic bowl for its loss landscape. Using a random uniform orthogonal matrix U and a diagonal matrix D consisting of a geometric sequence of 100 values starting at 0.001 and ending at 1, the Hessian of the quadratic bowl set H UDUT and the center set to the origin. However, whenever the loss and gradient are evaluated, the center of the quadratic bowl is perturbed by a random offset. distributed as i.i.d. normal in each dimension, with mean and covariance vI for some > 0 which
23

---

Published in Transactions on Machine Learning Research (09/2023)
Table 5: Noise and step number schedules for tuning the optimizers' hyperparameters using the genetic algorithm presented in Appendix E
Iteration
Noisy Quadratic Bowl
Rosenbrock Function
Image Generation
Resnet-18 CIFARIO
Noise stddev
steps
Noise stddev
steps
Noise stddev
steps
Noisc stddev
steps
0
3
1k
3
200
1k
3
50
1
3
1k
3
200
3
1k
3
50
2
3
1k
3
200
1k
3
50
3
3
2.5
200
1k
3
50
4
2
1.5k
2
200
1.5k
2
50
5
1.7
1.5k
1.5
200
1.5k
1.7
6
1.4
2k
1
200
1.4
2k
1.4
100
7
1.2
3k
0.75
200
1.2
3k
1.2
200
8
0.9
5k
0.5
200
0.9
5k
0.9
300
9
0.6
8k
0.3
200
0.6
8k
0.6
500
defaults to 1. The initialization this task set to the origin. Due to the random wandering the center, the expected loss rises linearly over unne-unless the optimizer steady state distribution. The expected loss after infinitely many steps can then be taken as of the quality of optimizer. The optimal solution for this task is to select the current minimum of the quadratic bowl at every timestep (which is what the Newton method would do). Due to the movement of the minimum between steps and loss evaluations, we should still expect this strategy to achieve nonzero loss which can be analytically calculated to be 7.412v. Table | shows the long term performance of LODO comparison to other optimizers and the optimal solution of the Newton method. Table and Figure S show that the performance of LODO insensitive the noise variance, and that LODO outperforms competitors for all noise levels.
prevent this, driving the error towards
10
Momentum
RMSprap
loss ; best loss
Adam
loss
10a
Yogi
LODO
L-BFGS-nooinne-earcch
10a
O-LBFGS
Newton method (theoretical)
10a
10
10
noise variance
noise variance
Figure 8: Average tracking error of the quadratic bowl minimum on the noisy quadratic bowl task of Section 5.1 with various different noise variances v. Values are averaged over the last 10% of training up to 300k steps. The theoretically best possible loss using Newton's 's method is also listed. The version of L-BFGS is one with stochastic modifications from (Schraudolph et al., 2007), instead of the original from (Nocedal & Wright 1999). Left:: Tracking error on a log-log plot. Right: Ratio of tracking error to the thcoretically best possible tracking error by Newton's method, also on a log-log plot. Methods which choose steps that are equivariant to gradient scaling are insensitive to noise magnitude and show up as horizontal lines.
F.2 CNN Image Generation Task Details
This section explains the CNN image generation task of Section 5.3 which is similar to the task of training a PixelCNN (Oord et al. 2016 Like PixelCNN, our CNN generates pixels row by and column by column,
24

---

Published in Transactions on Machine Learning Research (09/2023)
Table Hyperparameters used for the experiments in Section after tuning hyperparameters with genetic
algorithm as in Appendix E and halving the learning rates (equiv. initial learning rates for LODO variants) for the image generation task. 3 and 31 generally represent momentum decay rates while 82 represent variance EMA decay rates, Dashes indicate that the optimizer was not used for that experiment.
Optimizer
Hyperparameter
Value
Noisy quadratic bowl
Rosenbrock function
Image generation
Resnet- -18 CIFAR10
Adam
Learning Rate
1.164
0.9704
0.0009554
0.0004295
$1
0,465
0.864
0.9323
0.9562
82
0.9884
0.99804
0.99505
0.99814 14
Momentum
Learning Rate
1.394
0.09870
0.003411
0.0099422
8
0.529
0.9359
0.9640
0.99409
RMSprop
Learning Rate
0.449
0.004318
4.167 x 10
9.877 x 10-6
0.04943
0.02836
0.002258
0.03338
3
0.595
0.880
0.936
0.9394
Yogi
Learning Rate
2.169
0.2991
0.0009340
0.001829
81
0.4362
0.9273
0.9319
0.9730
82
0.9999723
0.998787
0.999708
0.9828
LARS
Learning Rate
0.0008552
0.002516
8
0.9343
0.9385
Weight Decay Learning Rate
4.839 x 10-5
5.370 x 10
L-BFGS
1.204
23002
O-LBFGS
Learning Rate
1.050
36721
LODO
Meta-Learning Rate
0.0009600
0.0001394
7.946 10-6
0.0001134
8
0.195
0.897
0.9343
0.9490
Initial Learning Rate
0.270
0.2946
0.08459
0.1725
LODO- LODO-Diagonal
Meta- Meta-nearning Rate
0.0005196
0.9860
Initial Learning Rate Meta-Learning Rate
0.1325
LODO-Global
7.951 10
8
0.9525
Initial Learning Rate Meta-Learning Rate
0.05583
RosO-uesidulls
3.829 x 10
8
0.9301
Initial Learning Rate Meta-Learning Rate
0.02134
LODO-SGD
0.0007196
0.9499
Initial Learning Rate
0.1035
and classifies the brightness of each pixel into 256 classes with crossentropy loss. Our data preprocessing is follows. An MNIST image randomly selected, and one pixel location is chosen uniformly at random and blackened. All pixels below, or to the right of and in the same row as the selected pixel are blackencd. The image (divided by 256 for normalization).
input into the CNN consists of this partially masked/blackenn an image indicating which pixels are specifically masked/ blackened (indicated by -1 and 1), another image indicating which pixels are left of the selocted pixel (indicated by -1 and 1), an image of linear gradient from to in the direction, and the same for the y direction. The last three images are present purely to break horizontal and vertical translation symmetries in the data, which has been shown to be helpful in
25

---

Published in Transactions on Machine Learning Research (09/2023)
Table Average tracking error of the quadratic bowl minimum on the noisy quadratic bowl task of Section 5.1 with various different noise variances Values The theoretically best possible loss using Newton's s method is also listed. The version of L-BFGS is one with
averaged over the last 10% of training up to 100k steps.
stochastic modifications from (Schraudolph et al. 2007p, instead of the original from (Nocedal & Wright 1999). Upper: Loss values. Lower: LODO's 8 average inverse Hessian approximation ion error
VII G /
o² is measured by the unbiased estimator E || G( b l2 with random independent unit vectors vy Evidently, the ability of LOOO to learn the inverse Hessian does not depend on the amount of noise.
Noise variance V
0.01
0.1
10
100
loss at noise variance v
Adam Kingma & Ba
2014
2.03
2.95
15.23
314.05
18602.71
Momentum
0.17
1.67
16.52
164.95
1672.73
RMSprop Hinton al. 2012
1.44
3.20
22.50
1683.15 13
28973.22
Yogi (Zaheer et al. 2018
0.17
1.80
15.51
209.83
7002.78
L-BFGS (Schraudolph al.
2007
0.50
1.89
48.04
494.04
4962.88
O-LBFGS (Schraudolph et al.
2007
0.14
1.40
14.13
141.46
1405.51
LODO (ours)
0.09
0.89
8.94
89.54
887.94
Newton Method (Optimal)
0.07
0.74
7.41
74.12
741.18
at noise variance
LODO
0.7444
0.7421
0.7490
0.7479
0.7533
AAR
Figure 9: Batch lensors of preprocessed MNIST images from the image generation task of Section 5.3 each as one of the 5 rows of the image. Shown in each of 5 columns are the masked input, the left-of-selected pixel indicator, visible mask, and two gradient images. The images in each 28 x 28 x 5 data tensor and then used as input into the CNN.
concatenated together into
vision tasks involving collection of information from specific locations of an image specified by the data [Lu
et al. 2018 The preprocessed data is visualized in Figure
The CNN architecture we use for autoregression consists of:
input channels as previously described.
Residual connection to Point A.
One pixel of zero padding, and convolution with 3 by filters to 20 channels, with activation.
26

---

Published in Transactions on Machine Learning Research (09/2023)
Point A.
The following indented items are repeated times.
The following indented items are repeated 4 times.
Residual connection Point B.
Convolution with 1 by filters to 40 channels, with arclangent activation. We use the arctangent to mitigate gradient norm issues.
One pixel of zero padding, and three different depthwise convolutions concatenated logether, with 3 by 3 filters to 120 channels, with arctangent activation.
Convolution with 1 by filters to 20 channels, with activation.
Point B.
Average pooling of 2 by 2 blocks halve the image size, with a pixel of zero padding beforchand if the image size is odd.
Convolution with by 1 filters to 256 channels, with softmax activation.
The loss is then the average crossentropy between true brightness of the query pixel and the distribution given by the softmax output of this CNN, over a batch size of 256 images. The whole CNN has about 94696 parameters, which are initialized with LeCun normal initialization Klaambaner et al. 2017). The task for the optimizer is to train these parameters to minimize this loss.
Figure 10 shows some imitation MNIST images generated using this CNN by sampling pixels one by one, after training with various optimizers including ours. The generated images are lower in quality because training limited to 300k steps to best compare the efficiency of the optimizers.
7
7
4
q
o
5
y
t
[
9
9
(a) RMSprop
(b) Adam
(c) Yogi
(d) LODO
Figure 10: Grids of 16 imitated MNIST images generated the image generation CNN of Section for 300k steps using RMSprop, Adam, Yogi, and LODO.
5.3 trained
Table 8: Mean losses bet steps 180-200 while training on the Rosenbrock function minimization task, with various optimizers.
Optimizer
Mean loss between steps 180-200
Adam
0.00005342
RMSprop
0.0008967
Momentum
0.01397
Yogi
0.0007916
LODO (ours)
0.001040 + 0.00002140
27

---

Published in Transactions on Machine Learning Research (09/2023)
10-1
training loss
10
Momentum
RMSprop
Adam
10-3
Yogi
LODO
10
50
100 step
150
200
Figure 11: Log loss as a function of step, when using various optimizers on the Rosenbrock function minimization task.
G Rosenbrock Function Minimization Experiment
We probe the behavior of LODO with small test task of finding the minimum of a rescaled Rosenbrock function f(z, y) 0.01(x-1)++(0 - which has no local minima and one global minimum at (x. y) = (1, 1). We initialized the optimizers at y) = (-0.5, 2) and gave them 200 steps to run. The trajectory taken by LODO, shown Figure 8 is similar to the short timescale dynamics of other optimizers using momentum, in that it lends to overshoot and then correct itself in an oscillatory manner. Learning curves in Figure and losses in Table 8 show the performance of all the optimizers on this task.
H Training Loop Timing Details
This section describes how timed each optimizer to report performance at specified times and step per second training speeds. We performed all optimization runs in TensorFlow 2, each with 40 Intel Xeon Gold 6248 CPUs and Nvidia Volta V10 GPUs. Time reported includes all training time (forward and backward propagation, optimizer computation, data loading, preprocessing, etc.) except it does not include time taken to evaluate metrics such as the Hcssian approximation error and the validation and test losses and accuracies.
28


Reviews:
[{"review_id": "pJufkE7Fh5", "reviewer": "Reviewer_biMo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n1) The paper is well-motivated and easy to follow.\n2) It contains both theoretical analysis and empirical results, especially for the inverse Hessian problems.\n\n\nCons:\n1) Except for the synthetic data, the paper only works on image generalization applications on mnist dataset.\n2) Why is image generalization problem only? How about image classification? Can we have more experiments on more tasks?\n3) Can we do larger-scale experiments on datasets and networks? Like Cifar10 or ImageNet with some modern networks, like resnet or transformer. If we can't, why it is hard? It is due to the computation cost? It seems not that high to me.\n4) Does the performance boost come from the optimizer or does it work like some regularization? Can we have an experiment for fix the hyper networks (G(\\theta)), and only learn the model parameters?\n\nMy main concern is that why we would like to use this method as an optimizer as it lacks use cases.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a new optimizer that uses a meta-learning method to learn a pre-conditioner with a hypernetwork.  They theoretically show that the proposed optimizer approximates the inverse Hessian and empirically verifies it with synthetic data. The paper is well-motivated, and the empirical results show that the proposed method outperforms existing methods. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the weakness.", "broader_impact_concerns": "I do not have any broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "BCCoJaauFO", "reviewer": "Reviewer_ZQcU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n- Overall, I think investigating gradient-based adaptation of Hessian approximations (or more task-specific targets than simple estimation error) is a worthwhile avenue of investigation. \n- This paper shows the method can work, although the experiments do not show it outperforming simpler optimizers. \n- The theory is reasonable for backing up the method. \n\n## Weaknesses\n- While the authors present their method as a learned optimization/L2O/meta-optimization method, I think this is misleading in comparison to other learned optimizers, which are much more expressive. This method is more reasonably placed in the class of quasi-Newton methods, although the authors may define QN methods as only those which directly aim to minimize Hessian/inverse Hessian estimation error. \n- The authors should evaluate the performance of LODO on more standard neural network optimization problems. While I think the image generation model is interesting, evaluating the model on e.g. a standard resnet training would be much more valuable to the community. Ideally, I recommend the authors look at the MLCommons Algorithmic Efficiency benchmark: https://github.com/mlcommons/algorithmic-efficiency\n- The Hessian estimation on varying problems should be evaluated, and better comparisons should be made to other quasi-Newton methods. This is especially true as the Hessian approximation error in Fig 2 seems to remain quite large, and it would be valuable to see how classic QN methods perform. Moreover, the Hessian approximation error should be compared as a function of the noise covariance, which will likely have different impact for different QN methods. The authors should also compare, in addition to classical QN methods like BFGS, to standard Gauss-Newton Hessian estimation methods (eg Levenberg-Marquardt).\n- Section 5.3.1, in which alternative architectures are explored, is unclear and could be expanded. Generally, the biasing the permutation matrices toward the identity matrix seems like a reasonable approach that (slightly) improves performance; there are several extensions that could also be investigated, and potentially a more general class of preconditioner architectures can be presented. \n- The assumption of b_{t+1} = A_{t_0} b_t - s_t feels quite limiting, and undermines the theoretical results. However, I don't have a good suggestions for improving the theoretical development, so I am fine to keep it as is. That being said, the validity of the theoretical results in based on A_t updating slowly, and showing that the dynamics under an updated A and a non-updated A are similar would validate the claims of section 4. \n\nSome typos: \n- Lemma B.1: \"Let us A and B\"\n- Table 1 caption: \"Vales are are averaged\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a new optimizer (LODO) based on the following principles: \n- Parameterizing the preconditioner matrix inexpensively via EUNN parameterization\n- Compute the gradient of the loss with respect to the parameters of the preconditioner, and update via taking a gradient step (or using e.g. Adam) on these parameters\n\nThe authors show that under some (semi-reasonable) assumptions, this estimation scheme converges to the true inverse Hessian preconditioner on quadratics. \n\nOverall, I think this is a reasonable contribution to the world of quasi-Newton methods. There are a few issues which should be fixed before acceptance, however. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The most important change is to investigate LODO on more standard neural network training tasks. This will enable better comparison with other methods, and substantially broaden the appeal of the paper. I believe these experiments are critical for paper acceptance. \n- There are several small experiments recommended above (eg comparison on estimation to quasi-Newton/Gauss-Newton estimation algorithms) that will improve the paper. \n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EQI0bgSyPq", "reviewer": "Reviewer_4FcD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- It is a novel direction to extend the idea of \"learning to optimize\" to more complicated optimization algorithms, in particular quasi-Newton method in this paper.\n- A comprehensive and rigorous theoretical analysis of preconditioners parameterized as neural networks is presented in the paper, which has been rarely discussed in other relevant works.\n\nWeaknesses:\n- It was not clear to me what are the benefits of training a preconditioner on the fly. Normally, an optimizer which can generalize to different tasks is more desired. Training a specific optimizer for the target task would introduce much more computing. \n- Evaluation was not very complete. Currently all selected tasks are relatively small-scaled and it is not clear whether LODO still works under large-scale training. On the other hand, only traditional hand-design optimizers are compared, which is not fair. At least other neural optimizers that learn the whole update rule should be included to show advantages of only learning preconditioners.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposed a novel pipeline, learning to optimize during optimization (LODO), to leverage a neural network to online meta-learn the best preconditioner during optimization. Both theoretical analysis and empirical studies are provided to support the effectiveness of LODO.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- It would be good if the authors can provide some concrete examples to demonstrate why training on the fly is selected in the paper. For instance, comparing training on the flying and training an optimizer under some distribution.\n- Comparison with other neural optimizers are necessary. If possible, conducting some large-scale experiments like image classification on ImageNet would make the paper stronger.", "broader_impact_concerns": "This paper does not arouse any ethical concerns from my perspective.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a new optimizer (LODO) that learns a preconditioner during training. The reviewers generally agreed that the paper was easy to read, the topic was important, and that the theoretical results were sufficient for the type of problem studied. The empirical results were found to be less convincing, and the reviewers requested a number of additional experiments. The new additions to the manuscript thoroughly addressed the reviewers' major concerns.

There remain questions about whether LODO is likely to be of use in practice. However, the paper never makes that claim, and instead frames the contribution as a stepping stone towards developing meta-training-free learned optimizers. This and the other claims in the paper are clearly supported by the evidence presented and as such I recommend acceptance.
Decision: Accept (poster)