Learning to Optimize Quasi-Newton Methods
Authors: Isaac Liao
Rumen Dangovski
Jakob Nicolaus Foerster
Marin Soljacic
Venue: Submitted to ICLR 2023 (2023)
Keywords: meta-learning
learning to optimize
quasi-Newton
optimization
hypergradients

Abstract: We introduce a novel machine learning optimizer called LODO, which online meta-learns an implicit inverse Hessian of the loss as a subroutine of quasi-Newton optimization. Our optimizer merges Learning to Optimize (L2O) techniques with quasi-Newton methods to learn neural representations of symmetric matrix vector products, which are more flexible than those in other quasi-Newton methods. Unlike other L2O methods, ours 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 our algorithm's performance in the presence of noise, 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, and obtain competitive results against standard neural network optimizers.

Under review as a conference paper at ICLR 2023
LEARNING TO OPTIMIZE QUASI-NEWTON METHODS
Anonymous authors Paper under double-bling blind review
ABSTRACT
We introduce novel machine learning optimizer called LODO, which online meta-learns an implicit inverse Hessian of the loss as a subroutine of quasi-Newton optimization. Our optimizer merges Learning to Optimize (I.20) techniques with quasi-Newton methods to learn neural representations of symmetric matrix vector products, which are more flexible than those in other guasi-Newton methods. Un- like other L20 methods, ours does not require any meta-training on 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 wide range of inverse Hessians. We experimenaally verify our algorithm's performance the presence of noise, 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, and obtain competitive results against stan- dard neural network optimizers.
INTRODUCTION
Many optimization algorithms like stochastic gradient descent (SGD) (Rosenblat) 1958). and Adam (Kingma & Ba 2014) have been widespread and successful in the rapid training of deep neural networks. (Sun et al.] (019) Fundamentally, this is a problem of minimizing a loss which function of a large vector containing the weights of the network. The time it takes to optimize neural network is a bottleneck in machine learning, so the more quickly a network can be trained, the more computational resources saved, and therefore researchers have devoted great effort into
creating new, faster optimizers. (Jain & Kar 2017: Metz et al. 2020 Bernstein et al. 2020 Martens
& Grosse 2015a)
We present a novel algorithm drawing from the field of learning to optimize (L20) spearheaded by (Li & Malik 2016) and (Andrychowiez et al., (016).. Namely, line learn an implicit representation of the local inverse Hessian, which is used in a quasi-Newton method, without any 1.20 meta training time a training task distribution. Unlike other 1.20 al- gorithms which learn to optimize before optimization (Chen et al. 2021), our algorithm Learns to Optimize During Optimization (LODO). We intend for LODO be trained from scratch for each use case and then discarded. This way, LODO learns local features of the loss landscape at a specific point in training for specific task, instead of only characteristics shared throughout training trajec- tories for a set of training tasks. Our work targets the Hessian, which varies with both the task and the point along the trajectory. Our use of linear neural networks what imports the efficiency Newton method to our algorithm, while our use of a meta-optimizer like in L20 is what allows us to learn more powerful and general parameterizations optimizers.
meta-optimizer to on-
Our contributions are follows. We show theoretically and experimentally that a simplified version of LODO correctly learns the inverse Hessian a stochastic convex setting. We show theoretically that LODO's inverse Hessian representation is highly expressive, and experimentally that simpler alternatives perform worse. We finally demonstrate the use of LODO in a semi-realistic vision task. This paper serves as stepping stone in the development of meta-tran training- ffreenng--reeeee online L20.
The remainder of this paper is structured as follows. Section 2 discusses relevant background and contributions in optimization and I.20. Section 3 shows how LODO works. Section provides

---

Under review as a conference paper at ICLR 2023
theoretical justification for our design of LODO. Sections and 5.2 show experiments which explore what makes LODO work and why. Section 6 discusses and summarize our findings.
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 calculation of the first and/or second moments of the gradient (mean and variance) using exponential moving averages (EMAs). RMSprop (Hinton et al., 2012) and Adam use the variance to normalize the step size and the mean to induce momentum. LARS (You et al. 2017) and Yogi (Za-) heer et al. 2018) modify both modify the variance calculation, but for different reasons: normalize layer-wise and to control increases in effective learning rate in a slower manner, respectively.
Some of these methods such as the Newton method and natural gradient descent (Martens & Grosse 2015b] George et al.) 2018)) precondition the step with adaptive estimates of the inverse Hessian and the inverse Fisher information matrices, respectively. The Newton method converges quickly but is vulnerable to gradient noise and impractical to implement due to the resources spent in calculating and/or inverting the high dimensional Hessian. Many researchers have developed approximations called quasi-Newton methods-
reduce the Newton method's time and memory complexity, such as L-BFGS (Nocedal & Wrightt 1999) and variants (Schraudolph et al. 2007 Parker- Holder et al. 2020: Goldfarb 20220 Park & Oliva 2019) better suited to the stochasticity and struc- ture present in machine learning. The most related methods to our work are hypergradient methods, which online learn low-rank (Moskovizz al. 2019), diagonal (Amid et al. 2022 Baydin et al., 2017]. or Kronecker-factorizel (Bae et al., 2022) preconditioner matrices to transform the gradi- when choosing the step. We improve these methods by using more expressive class of preconditioners.
More recently, subfield of meta-learning known learning to optimize (L20) has shown that deep networks can themselves be trained to perform optimization, at a speed which exceeds that of pop- ular traditional optimizers. The aim of this effort leverage deep neural networks to learn faster optimizers, in hopes of further accelerating training procedures for other deep neural networks. Li Malik (2016) 2017) and /Andyychowiez et al. (2016) were among the first to successfully use back- propagation to train neural networks to map gradients to steps. 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 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 wide variety of machine learning models with speed. (Lv et al. 2017)
Two issues also prevent L20 optimizers from being rapidly developed experimentally. Firstly, carefully chosen "task distribution" for the optimizer to practice on is required for the meta-learning of the L20 optimizer, playing the role analogous the "dataset". These tasks difficult to curate because the issue of generalization error applies; we want the test task to be similar to the task distribution. Secondly, this meta-learning of the L20 optimizer prohibitively costly, in that involves nested training loops, where the inner loop takes a large amount of time and memory to evaluate and backpropagate through (Metz et al.) 2019). Altogether, the choice of task distribution and lengthy meta- tiita-trining has been a necessary burden in L20, and we overcome these with LODO.
3 How LODO WORKS
In a quasi-Newton method, the approximate solution a, E Fn is refined by T++1 for some learning rate á 0, where G, f(x)) inverse Hessian and g: = f E R is the gradient computed by backpropagation through the task f. ā = 1 produces the exact solution f is quadratic, so we set ā 1. Our algorithm approximates the inverse Hessian using matrix G(O,) E m parameterized by a vector O, of weights learned over time f, described later in this section. After every step t < + using the formula x++1 2, G( the loss f(*(+1) is computed. Then the new gradient V V f( in æt+1 is computed through backpropagation as usual, but we continue backpropagation into the step-choosing process until we find the "hypergradient" f in the optimizer weights 0.,
aG,g. Raxn is some approximation of the
2

---

Under review as a conference paper at ICLR 2023
Algorithm Learning to Optimize During Optimization (LODO)
Require: f IR I, 2g E _ Function minimize, initialization.
Require: a E R: Meta-learning rate (default 0.001),
Require: ag E R: Initial learning rate (default 1.0),
Require: 0 3 < 1: Momentum (default 0.9),
P. Start time Initialization for neural network. b Initialize EMAs
Oo +- random initialization
me <-
while not converged do
1++1 < Zt G( (,(0,,0)mm m
D Pick step with inverse Hessian model G' from Equation (T)
l+1 f(x++1)
Compute loss after step >> Update gradient EMAs Tune the model to choose better step b Increment time
ma-1 f 3m, + (1 3)Vx.-1 C++1
update O2 O241 using Adam with Vo, le+1
t 1 ++1
end while return A,
G(O)T
(())
P B(
p Bio pf B(ol B((
P.
B(g)))
P2
B
((O()))
Ps
n0
rand perm
rand
rand perm
rand
rand perm
rand
perm
perm
Figure I: Visualization of LODO's matrix structure of (()) from Equation for approximation of the inverse Hessian. Reduced depth of 3, block size 2, and size matrices for illustration.
which allows us to update them as well. Thus, 0 is trained such that the quasi-Newton method tries to minimize the loss upon taking a single step.
In the L20 interpretation, 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 al. 2019). As countermeasure, take inspiration from the Momentum modification to SGD, and replace gt by (1- before input into the step generation formula. This changes LODO's step generation formula to 2++1 = x (1 (0,) Σ ft-r 9- instead, for some decay parameter B3 This results in LODO, summarized in Algorithm
gg-
Our parameterization of G()) separates our work from other hypergradient methods; ours is in- spired by the FFT-style Efficient Unitary Neural Network (EUNN) (Jing et al., (017) designed for parameter-efficient representations of unitary matrices. We replace the FFT matrices the EUNN with fixed randomly chosen sparse matrices, and write G(0) be large product of matrices:
= =( (I 0) (( 1):
N
G(0) = II )(0
(1)
1=1
where on a fixed initial learning rate, P: are randomly selected permutation matrices, B(O()) are block-diagonal matrices whose contents are listed by 0 where 0 = (0(2),.. (())),..((())).......))))))))))) as illustrated in Figure [ Every block is size k x & for some chosen & (we use 4 for our setup), where the blocks' contents are listed by 0. The (I 0) and (I 0) matrices are
and ñ x n respectively, and ñ x n. where is some chosen integer larger than n. For our setup, choose n = [2n/k] /k Though G depends on both ag and 0, we omit the ag in writing for brevity. By initializing each block matrix in (() to a random orthogonal matrix, we initialize G(Ø) to a multiple of the identity, despite the input information diffusing and mixing with itself inside the
all other matrices
layers of the network. The initialization to the identity also allows us to make the depth N large without worrying about issues with gradient magnitudes, and for setup we choose N 16.
3

---

Under review as a conference paper at ICLR 2023
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. The random connections between neurons are intended to bring expander graph properties to the computation graph of the neural network, such that signals can diffuse and self-mix quickly without travelling long distances within the computation graph. Since wanted LODO to be repelled by saddle points, we chose G(Ø) to produce step which has guaranteed positive dot product with the gradient, so we parameterized G(O) in a way which guarantees be positive-semidefine semidefinite symmetric matrix. Furthermore, since any positive-semidefinie symmetric matrix can be eigendecomposed into U UDU (U/) (U for unitary U and positive- semidefinite diagonal D, chose G(0) represent the product of matrix with its transpose.
Since we expect the receptive field of output nodes to grow exponentially with depth, it takes (log n) layers for all of the inputs to interact with each other, so we intend the depth N to be some multiple of log n. Applying permutations and block diagonal matrices both cost O(n) time, so the inverse Hessian estimate G costs (n log n) time. This cost is small the task is to train an architecture with much more parameter reuse than log such CNN or transformer. The memory LODO needs On log since we have O(n log n) learnable parameters, though other 1.20 optimizers which cost ((n) may easily outstrip this cost via large enough constant factor, for example by storing and processing a long history of past gradients.
THEORETICAL PROPERTIES OF LODO
In this section, we illustrate LODO's behavior through its theoretical properties. To make our anal- ysis easier to show, this section only refers to LODO that is modified in the following ways: (?) We update 0g using SGD of learning rate a instead of Adam; and (ii) we use no momentum, / 0. We present two results about desirable inverse Hessian learning dynamics and expressiveness, and in Appendix D some further support from the literature for desirable properties of LODO's inverse Hessian approximation error.
4.1 HESSIAN LEARNING DYNAMICS (LODO CAN LEARN THE INVERSE HESSIAN)
In this section, we show that with certain assumptions and approximations, G(,,) converges to the inverse Hessian in stochastic setting. We restrict our analysis version of LODO simplified from Algorithm [ where the parameterization of G(O,) E Rax= is instead a rearrangement of the parameter vector O, E iga and is not necessarily symmetric, though the experiment of Section 5.1 supports similar findings for the original version of LODO as well. We also work in the limit of small learning rate The problem setup is of noisily moving quadratic bowl:
8, E RR,
8t S, S, Bjs = O, t7 = 87:
zid
(xx.)
- -x(=== -=;)) -
H(a: =
xx))
(2)
where H is a dositive-definite symmetric Hessian matrix and S is some light tailed distribution of zero mean, for example a multivariate normal distribution (s 0, E). Lastly, we assume that G (CO,HHH 1 for all f, that G(6.) never travels too far from H
Under these conditions, the gradient of loss with respect to both o, and O, can be solved for so LODO turns out to follow the training dynamics
A = A, - H by H²,
D = A.b. 8t,
where we define A, I H and b It 2ς be the errors in estimates of the inverse Hessian and the minimum, respectively. A full derivation is in appendix[A.I b, then exponentially decays fixed distribution, and the long term dynamics of A, should not be greatly affected by the quick compensating movement of b, 's distribution. Thus, to determine the movement of A,, we can approximate the dynamics along a short trajectory by fixing A, its value at to to study the settled distribution of b, Appendix A.2 gives more rigorous justification for this approximation-
We think of this phenomenon as similar to the adiabatic approximation of quantum mechanics. Ac. the fixed distribution of b,, and the actual distribution of b, play the roles of the Hamiltonian, the ground state, and the actual state, respectively.
4

---

Under review as a conference paper at ICLR 2023
keep the A++1 update but rewrite the bu+1 update as
b At, by 8t--
(4)
The total contribution of all s, for to S S t to the movement of A, in the infinite time horizon is then
8c A A
1 (A..) H²
a aHAr
Σ
(5)
with some extra terms multiplied with pairwise products between 8; and 8j (i * j), and other terms with b In the long term, the average contribution each 8, to the total then converges to
aH Ato
Σ A "E s (Ato ")² H
by law of large numbers, where any pairwise products s; and 8j for i + j have no effect due to independence and the mean of s, being zero, and the effect of b. vanishes due to small The expected error for this convergence decays to zero like (((- (n) -112 due to the light tailedness of iid 8, (eg. when 8, ~ (Nss;;; 0, E)) leading to the central limit theorem. Expression 6 is then the step direction for the Euler method for approximating the solution the differential equation
dA dt
= HA
E 88 (A H
n=0
which can be shown to cause A to flow towards zero such that G(O;)) converges to H Therefore, is reasonable believe that LODO learns the inverse Hessian over time, given small enough learn- ing rate. The Frobenius norm the error decays faster when magnitudes/norms of H and [ss"] 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 at as long as the approximations mentioned stay accurate. One interpretation of this is that when the noise s is zero a certain direction, the error in that direction quickly decays to zero so LODO no longer receives any data along that di- rection order learn that direction's curvature. Furthermore if the Hessian does not penalize deviation in some direction, then the training signal for that direction vanishes.
We may also produce another analysis for when H has a direction of negative curvature, show that LODO repels saddle points. Here, we instead choose to parameterize G(O,) as positive- definite symmetric matrix, and take the limit of small learning rate a such that G(O,) is effectively fixed. Then, GOO,) H has some negative eigenvalue À with eigenvector y (see Appendix B for proof). such that A = G(O,) H has an eigenvalue of norm greater than 1, meaning that the error vector b blows up exponentially in the y direction. Since Hy Xy, left multiplying by y G(0,)-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.2 REPRESENTARILLTY (LODO CAN BE EXPRESSIVE)
In this section, we seck to show that our parameterization of G(0) is highly expressive; LODO may represent a wider range of inverse Hessians than many other methods. In fact, we show that with
U where UU I. and using B = R AU, we can show that the norm of BD decreases over time,
A flows towards zero because by substituting eigendecomposition
BD BDD
d tr D D
(8)
df
dt.
2u
BB
B"
DB
B 88"
U(B")T
(9)
1/2
1
Σ
B"U
88 T
U
50
(10)
n=
where the strict equality is only satisfied for A
5

---

Under review as a conference paper at ICLR 2023
an increase in parameter count by only logarithmic factor, fixed parameterization of G(Ø) reproduce any possible parameterization G( FT F where vector multiplication with F computable with some sparse linear neural network. Our parameterization is thus capable of representing inverse Hessians from (Baydin al. 2017) and (Amid et al. 2022) with only Olog ñ) times more parameters, and (Moskovitz al. 2019) with only O(log* 7)) times more parameters. Definition I creates function to characterize the mixing rate of random transpositions when trying to shuffle lists, while Theorem | uses this function to lower bound the probability that the G(0) network in LODO can represent other linear neural networks.
Definition 1. Uniformly sample sequence of Na/2 transpositions of two out of â elements, for integers n/2 E N and N E N, with the condition that every successive block of n/2 transpo- sitions commutes internally (transpositions can be rearranged within block). We replace each transposition with the identity operation with probability 1/2, and then compose the sequence of transpositionsfidenttiss to form permutation. Then, we define the function e(Nñ/2, the expected entropy of this permutation, given the original sequence but not given the locations where identities were placed, is log n! e(N..22
/2,2 n) such that
Theorem 1. Uniformly sample permutations P. and create block-diagonal matrices B(0()) where every block is 2 x 2, and whose block contents are listed by the parameters g(0) Use these to construct the LODO subnetwork GO) as in Equation | with some depth N and hidden dimension n. Construct any linear neural network F with input dimension, output dimension, and number of weights per layer at most ñn at most incoming and at most ie outgoing weights for every neuron, depth d and any arrangement of weights. Then, there is a probability of at least
ON
1- i.N V
(11)
2"
4dl
loga h + 1)
that we can make G()) for some 0.
The proof is in Appendix C
We believe that random transpositions in the style of Definition D are a quick way to shuffle, since the Cayley graph the symmetric group generated by all transpositions has good expansion properties (Konstantinova & Kravchuk] (022). In other words, we hypothesize that for large N and n, we have e(NNi/2 n) ciñe Nu, for some positive constants e₁ and cz. This would imply that the probability that G()) can represent all possible F is at least approximately
G 2
C2NN
R!N
exp
(12)
4d llgg A +
which can be made to be above (n!)e for any constant c by using sufficient depth N which goes like N x d(log, k)) log n, due to Stirling's approximation. Thus believe that by only being O(logg k)) log in) times deeper than F, we make it very likely that our model G(f) can represent all possible F.
EXPERIMENTS WITH LODO
We present here a number of tasks which provide experimental evidence for the theoretical results we claim, though we test a variety of optimizers on these tasks. Appendix G presents an addi- tional experiment on the Rosenbrock function. Appendix (exepaiineexslaanss how we tuned each optimizer's hyperparameters for each task. Optimizers were used 8 times for every experiment to ensure repro- ducibility of results, unless otherwise stated.
5.1 NOISY QUADRATIC BOWL.
We use various optimizers track the minimum of 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 claimed in Section 4.1 The setup of the noisy quadratic bowl is the same

---

Under review as a conference paper at ICLR 2023
in Section 4.1 and details provided in Appendix F.I can maintain lower loss in the infinite step limit, since the error builds at a constant rate over time and the optimizer's 's role is to react and correct it quickly possible. We tested each optimizer by using it to track the minimum of the moving quadratic bowl over 100k steps. Learning curves in Figure2aand losses in Table Appendix [ show that LODO tracks the minimum more accurately than all other optimizers, and that an estimator of the inverse Hessian approximation error (((O,))T] ||²//m decays over time. Other optimizers underperform because their preconditioners 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 a higher loss.
We interpret optimizer to be better
hessian agproxinatton emor
0.82
40
0.80
RMSprop
training loss
30
Adam
0.78
Yogi
0.76
M W W/--
20
LODO
O-LBF GS
0.74
10
Newton method (theoretical)
0
25000
50000
75000
100000
25000
50000 75000
100600
step
step
Figure 2: Left: LODO's average inverse Hessian approximation enror o G(0))
the noisy quadratic bowl task of Section 5.1 r2 is measured by the unbiased estimator 100 ||(I G
with random independent unit vectors V.. Right: Average train- ing loss learning curves, smoothed by averaging over blocks of 200 steps each. The dotted line shows the theoretically best possible loss using Newton's 's method.
100
better optimizer maintains lower loss after infinite steps, since for this task, loss is introduced over time and the optimizer serves to quickly suppress it. Left Right: Error margins indicate + standard deviation between the performances of 8 optimizers at every step. The version of L-BFGS is with stochastic mod- ifications from (Schraudolph et al. 2007), instead the original from (Nocedal & Wright 1999).
5.2 IMAGE GENERATION
We design challenge for LODO autoregressive image generator for MNIST. We intend to demonstrate the effectiveness of LODO at scale when used to train semi-realistic neural network. The task is similar to training PixeICNN (Oord et al. 2016) to generate MNIST images (Lecun) et al. 1998), and fully described in Appendix F.2 We tested LODO alongside a variety optimizers for 300k steps, though could get any quasi-Newton methods to converge on this task. Learn- ing curves in Figures] 3 and losses in Table show that LODO trains at speed that is competitive against other optimizers. Figure 7 in Appendix F22 shows some MNIST digits we generated.
Negative log likelihoods in nats per pixel after training for 300k steps on the MNIST image generation task of Section 5.2 with every optimizer. Values averaged over the last 10% of training before the stated training milestone, with means and standard deviations produced across optimization with different randomization seeds. The top optimizers underlined for each metric. Our timing setup is described in Appendix H
Table 1:
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 + 0.014
0,931
0.899
7.10 + 0.02
Yogi
0.683 0.002
0.677 + 0.003
0.686
0,674
1 7.42
LARS You al. 2017)
0.701 = 0.006
0.702 + 0.006
0.688
0.688
5.89 - 0.02
LODO (ours)
0.696 0.004
0.698 1 0.005
0.689
0.689
5.64 1 0.02

---

Under review as a conference paper at ICLR 2023
traintng 1ras
0.9
traiting Baxe
0.9
validaion lces
RMSprop
Momentum
Adam
LARS
LODO
0.7
0.7
100000
200000
300000
30
step 300000
Figure 3: Average training loss learning curves over training runs on the MNIST image generation task of Section 5.2 Learning curves smoothed by averaging over blocks of 600 steps each. Error margins indicate =1 standard deviation between the performances of the optimizers at every step. Left: By step. Middle: By time. Our timing setup is described in Appendix H Right: Validataion loss by step, using a subset of 64 images excluded from the training data. Each image provides 784 pixel colors predict, the validation dataset effectively consists of 50176 samples.
Table 2:
Negative log likelihoods in nats per pixel after training for 300k steps on the MNIST image generation task of Section 5.2 with ablated versions of LODO from Section [5.2] Values are averaged over the last 10% of training, with means and standard deviations produced across 8 runs with different randomization seeds. Our timing setup is described in Appendix H *Setup is similar
to (Amid et al. 2022) ** B*yddii et al. 2017).
Training loss
Test loss
Optimizer
300k steps
50k sec. (~ 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
LODO-Diagonasl
Diverged
Diverged 0.919 + 0.139
Diverged
Diverged
9.92 = 0.09
LODO-Global**
0.770 0.035
0.747
0.801
9.92 + 0.03
LODOO-eesduaal
0.701 + 0.004
0.750 + 0.008
0.693
0.741
3.31 + 0.08
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 1 0.02
We study the contributions of various components of LODO to its performance by replacing com- ponents observe a performance change, detailed below. For example, replace the Adam meta-optimizer with SGD to form a new version of LODO (which we call "LODO-SGD"); its per- formance shown in Table 2 Other modifications are listed below.
5.2.1 EIGENDECOMPOSED ALTERNATE PARAMETERIZATTINN
We would like show that architecture LODO uses to choose the step is flexible. We modify the matrix decomposition in Section G(0) ao (I 0) D& (I 0)" by adding learned diagonal matrix D in the middle and changing (()) to a product of many weighted permutations each added to the identity matrix. The neural network which G(0) represents now has residual connections, and the initialization is modified accordingly. Losses in Table show that this version (which we call "LODO-Residuals") performs only slightly worse than LODO for the same number of steps, reflecting the flexibility in the design of LODO.
5.2.2 SIMPLER APPROXIMATE HESSIANS
We presumed that the representability result of Section 4.2 is only useful because LODO's strength comes from the flexibility that G(0)) gives in configuring pairwise interactions between parameters. We therefore expect that using simpler form of Hessian should hurt the performance of LODO. We test two simpler forms of G()): G(Ø) = andiagg (0) (which we call "LODO- "LODO-Diagoaa"""" for E R initialized to vector of ones, similar to (Amid et al. 2022 and the even simpler G(Ø) Ig (which we call "LODO-Global" for 0 E R. initialized to I, as in (Baydin et al. (007).. Losses in Table 2 show that the original version of LODO performs the best, verifying hypothesis.
8

---

Under review as a conference paper at ICLR 2023
5.2.3 EFFECTS OF USING EMAS OF GRADIENTS
Similarly to how momentum works for SGD, LODO's input gradients are preproccessed by ac- cumulation into EMAs. To test claim in Section g that momentum benefits LODO, try separate momentum decay rates in a logarithmic grid from no momentum to the optimal amount of momentum found (3 0.9343), and test each decay rate once. Figure 4 shows clear trend that at least up to the optimal decay rate, increasing the effect of momentum improves LODO, We also try removing momentum completely (we call the modified version "LODO-NC MaDDO-No-Momenttnee results are shown in Table 2
6 DISCUSSION
0.74
LODO is middle point between L20 methods and quasi-Newton methods, retaining significant advantages of both classes of optimizers. Via LODO, we bring ideas from both classes of optimization methods to offer poten- tial solutions to problems common the other side.
0.72
0.70
Relative to quasi-Newton methods, LODO offers advan- tages 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 finite history them. This allows LODO retain information about the inverse Hessian for much longer than other methods. This is use- ful if the gradients contain enough noise that useful sig- nals can only be obtained by accumulating information from many gradient samples. Our theory further shows that the linear neural network in LODO is optimal to certain extent: can probably represent all linear neural networks smaller by logarithmic factor allowing a huge class of inverse Hessians. Our image generation task demonstrates that LODO suc- ceeds in a semi-realistic stochastic nonconvex task where other quasi-Newton optimizers diverge. of L20, LODO also has flexibility in the design of its linear neural network, which
0.4
0.6 beta
0.8
Figure 4: LODO's training loss as a function of the momentum decay coef- ficient 3, averaged over the last 10% of 300k steps, for the image gener- ation task of Section [5.2 Momen- tum improves LODO. Error bars depict LODO's uncertainty from Table
Due to makes amenable to further research and refinement.
Relative to L2O, LODO offers advantages associated with the restructuring of the outer and inner loop into a 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 takes advantage of this sacrifice in resolving the need to compute second-order gradients. LODO still inherits issues of high memory usage and slow step computa- tion from 1,20 methodology though. Our theory offers some understanding of how LODO learns optimize, which is rare for L20 methods: 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 the Hessian. As shown in Section 4.2 LODO presents an efficient way of approximating subsets of the O(n²) possible pairwise parameter interactions O log n) time. Such interactions are commonly ig- nored in the design of L20 and more mainstream optimizers, yet our image generation task demon- strates their importance, as evidenced by the improved performance LODO over ablated versions well SGD.
Conelusion Through LODO, we provide new way of using L20 methods online without any meta-training to perform quasi-Newton optimization. We introduce the strengths and advantages of quasi-Newton methods and L20 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 as stepping stone for the further development and of 1.20 in quasi-Newton optimization and vice versa.

---

Under review as a conference paper at ICLR 2023
7 REPRODUCIBILITY OF RESULTS
We have described all the details of the construction of our optimizer in Section 3 and all its modified versions in Section 5.2 All the tasks used for experiments are introduced Section and are fully described in Appendices F.1 and F.2 To further ensure reproducibility, we have also listed all the hyperparameters found for each optimizer and task Appendix E All our training runs were repeated 8 times to verify that each measurement of empirical behavior is consistent, with low standard deviation. Furthermore, we will release the code for all our optimizers and experiments on Github for others to see.
REFERENCES
Ehsan Amid, Rohan Anil, Christopher Fifty, and Manfred K. Warmuth. Step-size adaptation using exponentiated gradient updates, 2022. URL https:
httl:httt://aaaeettt //tp///aavvvv//vaa/eaieeaaeaawia org/ abs/ 20bs/2200 2202. 00145
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in neural information processing systems, pp. 3981-3989, 2016.
Juhan Bae, Paul Vicol, Jeff Z. HaoChen, and Roger Grosse. Amortized proximal optimization, 2022.
URL
00089
Atilim Gunes Baydin, Robert Comish, David Martinez Rubio, Mark Schmidt, and Frank Wood. Online learning rate adaptation with hypergradient descent. 2017. doi: 10.48550ARXIV.110... 04782. URL htttpss:/aacxl..orrrass/////
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 ptattts://ariiyye wwtp://rgggb/bbbeb//ee/.o
03432]
Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: A primer and a benchmark, 2021. URL https:///ax::
hrg//bb/21033.. 12828
Thomas George, César Laurent, Xavier Bouthillier, Nicolas Ballas, and Pascal Vincent. Fast ap- proximate natural gradient descent in a kronecker-factored eigenbasis. In NeurIPS, 2018.
Donald Goldfarb, Yi Ren, and Achraf Bahamou. Practical quasi-newton methods for training deep neural networks. Advances Neural Information Processing Systems, 33:2386-2396, 2020.
Geoffrey Hinton, Nitish Srivastava, and Kevin Swersky. Neural networks for machine learning lecture 6e. http:/ /ww. toronto. edu/ -ti pets//ccc32///31cs//eecu s glides_lesse lec6_
pdf pdf 2012. Accessed: 2022-08-28.
Prateek Jain and Purushottam Kar. Non-convex optimization for machine learning. Foundations and Trends@ in Machine Learning, 10(3-4):142 363, 2017. ISSN 1935-8237. doi: 10.1561/ 2200000058. URL WtRI.ttp:://dtt //tt:://x... doi www./r////// 000 1561 02011/2200000055
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 Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1733-1741. PMLR, 06-11 Aug 2017. URL https: ptttp:://proceedingg .mr...m.r.eee. htt..
html
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
arXiv: (0tv::412.660 14/266980, 2014.
Günter Klambauer, Thomas Unterthiner, Andreas Mayr, and Sepp Hochreiter. Self-normalizing neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems. NIPS' 7, pp. 972-981, Red Hook, NY, USA, 2017, Curran Associates Inc.
ISBN 97815 0860964.
10

---

Under review as a conference paper at ICLR 2023
Elena V. Konstantinova and Artem Kravchuk. Spectrum of the transposition graph, 2022. URL https::/axxiv.orgg/ http://rg/bbb////eee//..// 031553
Thomas Laurent and James von Brecht. Deep linear networks with arbitrary loss: All local minima are global. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 2902-2907, PMLR, 10-15 Jul 2018. URL https: htttp:://proceedingg.. mlr wtt.:/mwww..pessseeeeeeeeee press/v8C/
laurent html
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recog- nition. Proceedings of the IEEE, 86(11 86(11):2278-2324, 1998. doi: 10. (0.1109/5.72679)
Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint arXiv: 2016.
Ke Li and Jitendra Malik. Learning to optimize neural nets. arXiv preprint arXiv: 703.00441,, 2017.
Rosanne Liu, Joel Lehman, Piero Molino, Felipe Petroski Such, Eric Frank, Alex Sergeev, and Ja- son Yosinski. An intriguing failing of convolutional neural networks and the coordconv solution. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicold Besa-Bianchh, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Con- ference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pp. 9628 9639, 2018. URL https: htttps::/proceeed.nngg neurips .cc/ cc/ html
paper/ 2tt///111//hhaa /tt.://..11111111.............1.
Kaifeng Lv, Shunhua Jiang, and Jian Li. Learning gradient descent: Better generalization and longer horizons. In Doina Precup and Yee Whye Teh (eds.). Proceedings of the 34th International Conference on Machine Learming, volume 70 of Proceedings of Machine Learning Research, pp.
2247-2255. PMLR, 06-11 Aug 2017. URL htttps://proceeete 1v1 7a.17a.1 I
ml wtt.ssrs...rrrr///...m
James Martens and Roger Grosse. neur curvature, 2015a. URL http::ss//a.....r///aaaaaa///
neural networks with kronecker-factored approximate
James Martens and Roger Grosse. Optimizing neural networks with kronecker-factored approxi- mate curvature. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pp. 1408-24117 Lille, France, 07-09 Jul 2015b. PMLR. URL html
mmlr.
ftess//33/martenn/
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, C. Daniel Freeman, and Jascha Sohl-Dickstein. Understanding and correcting pathologies in the training of learned optimizers, 2018. URL
https::/arrrv.oor//aae.. 10180
Luke Metz, Niru Maheswaranathan, Jeremy Nixon, Daniel Freeman, and Jascha Sohl-Dickstein. 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.
Ted Moskovitz, Rui Wang, Janice Lan, Sanyam Kapoor, Thomas Miconi, Jason Yosinski, and Aditya Rawal. First-order preconditioning via hypergradient descent, 2019. URL htttt://atxxiiii
hkg//bs//a /eabb//911... 08461
Jorge Nocedal and Stephen Wright (eds.). Large-Scale Quasi-Newton and Partially Separable Optimization, pp. 222 249. Springer New York, New York, NY, 1999. ISBN 978-0-387-22744-- doi: 10.1007/0-387 320177720-88722222-3333 9. URL

---

Under review as a conference paper at ICLR 2023
Aäron den Oord, Nal Kalchbrenner, Oriol Vinyals, Lasse Espeholt, Alex Graves, and Koray Kavukcuoglu. Conditional image generation with pixelenn decoders. Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS' 16, pp. 4797-4805, Red Hook, NY, USA, 2016, Curran Associates Inc. ISBN 9781510838819
Eunbyung Park and Junier B Oliva. Meta-curvature. Advances in Neural Information Processing Systems, 32, 2019.
Jack Holder, Luke Metz, Cinjon Resnick, Hengyuan Hu, Adam Lerer, Alistair Letcher, Alex Peysakhovich, Aldo Pacchiano, and Jakob Foerster. Ridge rider: Finding diverse solutions by fol- lowing eigenvectors of the hessian, 2020. httt::/:://aaat www. abs 2011. 06505
Frank Rosenblatt. The perceptron: a probabilistic model for information storage and organization in the brain. Psychological review, 65(6):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 (eds.), Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pp. 436 443, San Juan, Puerto Rico, 21 Mar 2007. PMLR. URL httpps:/pproceedinggg mlr www.s/pessssse..eee v2 hht.s/cchaadoooh01o p
html
Shiliang Sun, Zehui Cao, Han Zhu, and Jing Zhao. A survey of optimization methods from machine learning perspective, 2019. URL https: http:///wwwwwwwwoa///o///osss /906. 06821
Yang You, Igor Gitman, and Boris Ginshurg. Large batch training of convolutional networks, 2017.
URL https://axxiv wttp/bsggg///a///ee
abs//a//000 03888
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 Neural Information Processing Systems, NIPS' 18, pp. 182559 Red Hook, NY, USA, 2018
Curran Associates Inc.
12

---

Under review as a conference paper at ICLR 2023
A ELABORATION ON HESSIAN LEARNING DYNAMICS
A.1 DERIVATION OF TRAINING DYNAMICS
This section gives a derivation of the result that under the problem setup of Section 4.1 follows the Hessian learning dynamics
LODO
A++1 A. o.Hb+1bb H²
bi+1 A,b, St,
where A, - G(O,) H and b: = 24 2 as long as G(O,) is parameterized as a dense matrix filled with elements of 0, and no momentum is used.
We first let by be x x. The loss at time then
1 by Hb. &
(13)
2
The gradient is then computed to be
de
= Hb..
(14)
dæ.
The step taken then produces the next parameters:
I++1 = Hb..
(15)
Subtracting 2/41 = x. + 8t, we get the recurrence for bi.
0t+1 xi+1 =2, - x 8, Hb.
(16)
bi+1 =b; G(O,) 8t
(17)
=(1 - -G((;) H)b. St
(18)
A,,b; St.
The loss time + is computed to be
4+1
DT Hb++1
(19)
(A,, st) -s))
(20)
(II - - (II -st).
(21)
LODO also computes step of O, using the loss on the next step. Since the elements of 0, are just rearrangement of the elements of G(0,) in our derivation, an update of O, can be treated instead like an update of G00.). The gradient of l+41 with respect to G(O,) is then computed to
dli+1 dG(o,)
H((1 - G(0,) s H
(22)
H(A,b: - b.) H
(23)
=HHby
(24)
and the step of G(O,) is
=G(O.) oHHb H
(25)
resulting in the recurrence for A,:
A =I - G(O++))
(26)
=I - (G(O.) + a aHbbbb H)H
(27)
=A, oHHb 16 H².
13

---

Under review as a conference paper at ICLR 2023
A.2 VALIDITY OF APPROXIMATION ARGUMENT
This section gives justification for the approximation in Section 4.1 of the long term trajectory of the recurrence
A = -A,- a.Hb by H
(28)
Dz+1 =A,b, 8t.
(29)
by replacing with
A/ =A aHHb i+1 b²t H²
(30)
6/ = b, -8: 8,
(31)
when is small and the initial conditions at to are the same: A.. A and b = b/ = 0. We will work in the bounded noise case ||s:||2 oo, where ||6| 2 is upper bounded by some Al, ll
dependent constant bmux due to exponential decay in Equation 31 In the case where the noise is not bounded, a probabilistic analysis can be done instead, though we do not provide one.
To justify this approximation, we prove that the spectral norm of long term deviation corrected for learning rate small over short distances in the following theorem:
Theorem 2.
lim lim All - A Mo--r/ajlla =0. --
(32)
In other words, the local movement A rescaled for learning rate is unaffected by our approxima- tion when the learning rate a is small.
Proof. Our proof strategy is as follows:
1. We will first define variables to denote bounds the movement of A and the approxima- tion error in
2. We will show that these variables bound each other, and then we will combine these bounds to create single recursive bound on the movement of A.
3. We will characterize the bound's growth and it will turn out that A has a maximum move- ment 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 bounded rate.
5. Since approximation errors in A are an accumulation of errors in b, we will show that deviation between the true and approximate A trajectories is quadratic in the distance along the trajectory.
6. We conclude that the approximation emor vanishes for short trajectories and small learning rates.
First part.
We first define the maximum drift in A
max toSTStoAA
||A, A/o l22
(33)
up to time difference At for < At R/a for some chosen small constant trajectory length R > O. We will pick R later. We will also define the maximum error in b
6b,t+
|b, b-112
(34)
to
up the same time.
14

---

Under review as a conference paper at ICLR 2023
Second part. For the bound in direction, have that for all 7 such that to STS to At,
|lb,+1 - b' b/+1l12 = ||,,,, b, 8, (A b2 8,)112 = || b, A b2
(35)
(36)
A, A b, 2l2 + || by Ai,
(37)
< A,I,, 42,11211b,l1 + || 12 by
b1112
(38)
SeA.0+ |b.llllllbbll---e// + |, ||||b, by, 1l2
(39)
using the triangle inequality and sub-multiplicativity for the spectral norm 11-112. This is recurrence
in |b, - b1112: by induction we have that for to S T S to + At 1,
||b 6,112 SCA.
| 112
bb,
112
(40)
===
such that produce the bound
max +b.t+Ai41 ScA,t+&A
|| 11-11 |b,,
(41)
T1=t0
SEA,tt
max
| 112 1111-1111 (11b', 112
(b,00A0)
(42)
T1=
totAr Σ
SeA,toAr
||4 to
1 +
(bmax + (b,to+aa)
(43)
Cb + bmax
SeAlo+A
(44)
|///
EA,totAi0max
+b.t++it11 || A2
(45)
Now, we show a reverse bound: for all such that to ST to + At, we have
||Ar+1 A%11 112 =I|,, aHb, +1 6, H
Ale
(46)
A A/ol1a + all H b 1
(47)
A, Alo112 + a:l
12 + (000+ + +..00++41))
(48)
A, A% + a:l H || (bmaa + =040))
(49)
By induction we have for to S S to
At +
|| A 22 Sa||
H [T (bmax - -
(50)
such that we produce the reverse bound
CA.o+Ar+1 Sa H (At + (6 + co.0+A111)2
(51)
Third part. recurrence
Substituting the bound in Equation 45 into the bound in Equation 51
we produce the
2
AAtt+ArtT So H| max
(A 1)
EA,oo+Ar
(52)
1
| l| CA.to+At
1
||A/,112
=a = max
(D + 1)
(53)
1l212 AAo012
A
CA.tot
=f(EA.0+ar).
(54)
where
1 | Eo
f(z) =a
H 3822 man
(A++1)
(55)
1 ||,
ll2
15

---

Under review as a conference paper at ICLR 2023
To bound the movement of A, must use the fact that when
4 - | la
0 Ats
(56)
27 a H
| 12
the function maps the interval
0. 9 Aa = 0, 7 b mun
(at + 1)
lb
_ 0, (14-
(57)
to subset of itself. Since at At = 0 we have cA,t = E Tae. and we also have Tat S Tat+1, may deduce by induction on At that aA E Tai long as Equation 56 holds, and thus there is a bound
9 a H max
CA I
At (A++
1) 3
|| 112)
(58)
4
on the movement speed of A as long as Equation 56 holds.
Fourth part. Note that we have assumed that At R/a for some constant R which we have not yet picked. By choosing
A 12
R <
(59)
27
H
may always guarantee Equation [66] which implies Equation 58 Then when Equation 58
substituted into Equation 455 we create a small bound on the approximation error in b which begins and increases with time,
1 a
H
2
(D 1)
4b4++A++1 S
(60)
1 || 1o 112
fal H
322
max (At + 1)
abmax At + 1)
(61)
3R a(A/ 1)
for 0 A < R/a. This also holds trivially for At -1
cb.to-Art A141
0, we may
re-index to have
ab abmaax At
Eb
(62)
3R att
for 0 < At < R/a+1 1. Since the right side of Equation may bound by linear function with the same endpoints
62 is convex in At over At E [0, R/al, we
abmaxx
Cb.bo S
At
(63)
2R
for 0 < At S R/a.
Fifth part. Finally, we use this bound on approximation error in b to bound approximation error in A.
|| A| + H2 (Alotar
Alot441l12
aHb' 1 D
total
H
(64)
Alo+tt A + H
b' Aet
(65)
< Ato+Ar Abg-selk2 + H| (10bro
+ +1 by MootccillallBs
(66)
Al Alo--ulll + Eb.co
H | (26max + Eb.t0Ar11)
(67)
16

---

Under review as a conference paper at ICLR 2023
By induction, we find that the approximation enror of A is quadratic in time for short times 0 At S R/a,
At-1
|| A - Apotarlz
S
b.to A141 0t
H
(20max + 0,0++
(68)
Atm0
At-1
|||| $
(At + 1) (2+ 11 2
a
(d 11
(69)
max
2R
2R
At=0
A
2
122 H
Al (2+
a
A1)
(70)
max
2R
2R
At=1
a At
a
||| max
82
2
(71)
2R
2R
Sixth part. Now take At Lr/a], which for r + 0 is eventually & R/a as required. As we sought to prove, the learning rate rescaled approximation error of the local drift direction and speed goes to zero:
lim lim _ AtotLr/od a-30000 F
A Arot/r/alll
112
lim lim - ~00000 r
| | 1
a²
L²(r/aJ²
(2 2
a|r/a]
(72)
2R
2R
lim r00
H|| 3
r 2
r
(73)
max 2R
2R
0.
32
B PROOF THAT GOO) HAS NEGATIVE EIGENVALUE
This is true, because we can substitute A = G(O.) and B = H in following lemma:
Lemma 1. Let us A and B be symmetric,full-rant n x n matrices. Let A be positive-defiitte and B have at least one negative eigenvalue. Then, the product AB has at least one negative eigenvalue.
Proof. Let æ be an eigenvector of B with negative cigenvalue X. Then, we have
A 1/2x)) A 1/2
(A 1/2 0
(74)
meaning that the desitive-definite symmetric matrix 1/2 1/2 must have at least one negative eigenvalue X' with eigenvector x'. Then, have the eigenvalue equation
AB 1/2 1/122 1/2 BA x²'
(75)
=/221/2
(76)
which shows that AB has a negative eigenvalue X'.
L
C PROOF OF REPRESENTABILITY THEOREM
This section gives a proof of the representability theorem stated in Section 4.2
Theorem 1. Uniformly sample permutations P. and create block-diagond, matrices B(0 where every block is 2 x 2, and whose block contents listed by the parameters ( Use these to construct the LODO subnetwork G() as in Equation | with some depth N and hidden dimension n. Construct any linear neural network F with input dimension, output dimension, and nunber of
17

---

Under review as a conference paper at ICLR 2023
weights per layer most n., most l incoming and at most k outgoing weights for every neuron, depth d, and any arrangement of weights. Then, there a probability of at least
RIN 2
n. 4d([1ogg kl + 1)
(11)
that we can make G() F for some 0.
Proof. Our result comes two parts: the first shows that (()) can represent arbitrary permutations, and the second shows that we can pick these G(Ø) permutations and interleave them with block diagonal matrices to create deeper (())) 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 neuron, respectively.
First part. Assume we would like to apply a given target permutation to ñ elements using G(0) = I )(0())), consisting of N layers with randomly chosen permutations P. Our goal is to perform the target permutation given P. by controlling the block diagonal matrices B(0 The form of (0) from Section
is
N G( = II
B P.
1=1
which can be rewritten
G(0) -Q O B B
Qu
QN=P. Q:-1= P
(77)
[=1
with random independent uniform permutations Q; instead. For each block in the matrix ((0))),
we 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(0) is equivalent to repeatedly randomly pairing up indices for optional transposition instead, and then applying final permutation Qı. We will work under this new equivalent formulation, since is more amenable to analysis.
Let us choose to apply each transposition with probability 1/2. Then, the expected entropy of G()) given the whole sequence of pairings is at least log n! - e(N î) under Definition | In other words, the expected KL divergence of this distribution of G(0) from the uniform is at most c(N 2/n n). Then by Pinsker's inequality, the expected total variation distance from the uniform is then at most
(N
(78)
2
This guarantees that at most
1 - e N (N 2
πl
(79)
possible target permutations have probability density of zero, in expectation, which is then an upper bound on the number of inaccessible target permutations. This means the probability that all target permutations are accessible is then at least
1 - nl
(Nn/2
(80)
2
Note that the leftmost Q, in Equation| 77 merely introduces a bijection between target permutations, and does change how many accessible.
18

---

Under review as a conference paper at ICLR 2023
Ga B
G2
B2
G
B
2000
2000 o 100000
Figure 5: In this diagram, ń 8 and p 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 1 chained copies of G(0) 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 3, which is less than 2 4; all the fanins are 1.
Second part. Suppose would like to represent p target permutations using p independently generated G(0) networks each of depth M. Equation 80 lower bounds the probability that each network can represent its respective permutation. Then the probability that all of the target permu- tations are accessible by their respective copies of G(0) union bounded by
1- přoly (MM
(81)
where the union is over the probability that each copy fails to represent its target permutation. Given need to chain these permutations together with block diagonal matrices to
that this succeeds, represent arbitrary neural networks F, with Equation 81 lower bounding the probability of failure.
Suppose we are successful representing any combination of p target permutations using p distinct independently generated G0) networks of depth M. Then, since each G(0) network's final (left- most) operation is block diagonal matrix, applying additional block diagonal matrix afterward does not affect the operations that G(O) can represent, since the set of block diagonal matrices use is closed under matrix multiplication. Importantly, each block matrix can be used to copy a value from one index into two to add two values together leave one, creating fanin or fanout in the network. Then, interleaving p + 1 chained copies of (()) with block diagonal matrices left- multiplied for a total depth of (p + 1)M therefore creates an aggregate operation which can still be represented by a single G(0) network of depth (p + 1).. This aggregate operation has up to ñ arbitrary connections from input nodes output nodes, with either all fanin most and all fanout at most 2", or all fanout at most 1 and all fanin at most 2". This is done by building forest of fanin/fanout trees like illustrated on the right side of Figure
If we compose such G()) network of depth (p 1)M with fanout up 2 together with G()) network of depth (p 1)M with fanin up to 2", then we may represent any sparse matrix structure with at most nonzero weights and maximum fanin and fanout at most 2P, using a G(0) network of depth 2(p + 1)M. This construction is illustrated 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 most l can be represented by G(0)) of depth 2( 2[Tog,, A 1)M.
the left side of Figure We may
Then, any linear neural network of depth most d, at most ñ weights per layer, and maximum fanin and fanout of most & can be represented by G(Ø) network of depth 2M [log, k1 + 1), by composition of sparse matrices. The probability that all of this successful is merely the probability that all the p 2Md(log, k:] + 1) permutations can be represented, which by Equation [8 is at
19

---

Under review as a conference paper at ICLR 2023
least
1 2n!Md((log) k1 + (MM
(82)
Thus in summary, if we randomly generate a G())) network of depth N 2. k] + 1) for fixed constants k, d, and M, î neurons per layer, and block size f = 2, then there is probability of least
äN
1 1 2 (Mā/2, =1 RIN
i!N
(83)
4d log,
1)
that G()) can represent every possible linear neural network of input and output dimension depth d, at most ñ nonzero weights per layer, and max fanin/fanout of at most k.
S n.
D HESSIAN LEARNING LOCAL MINIMA (LODO CAN GENERALIZE)
Laurent & von Brecht (0118) gives theorem showing that for dense linear neural networks on convex losses where each layer is at least as wide the input or output layer, all local minima in the neural network weights are also global minima. we simplify LODO by approximating the inverse Hessian with full dense matrix G(O,), then this theorem applies to the Hessian approximation error ||I G which the rescaled error |BD used in Section 4.1 proxy for. Thus may expect that any inverse Hessian approximation which LODO could converge is of similar high quality to the best possible inverse Hessian approximation.
E HYPERPARAMETERS
In every experiment, we tuned the hyperparameters of cach optimizer using genetic algorithm of 10 generations and 32 individuals per generation. Each hyperparamter was rescaled using -> In if the hyperparameter was learning rate and z + 1 In(1 æ) if the hyperparameter was decay parameter, so that the genetic algorithm would operate a more well-behaved hyperparameter space. Starting from the default hyperparameters. each generation's mean hyperparameters were added to some Gaussian noise to create mutated hyperparameters for each individual, where the standard deviation of the noise individual performed generation-dependeee deepedddnn and followed specific schedule. Each number of steps of optimization, also according to a schedule. The next generation's 's mean hyperparameters of the better performing half of the previous generation, as judged by average training loss during the last 10% of training. We also halved all the learning rates (equiv. initial learning rates for LODO versions) after tuning for the image generation task because tests showed the loss to diverge training time horizons were longer than 8k steps. Since LODO is random optimizer, used different randomization seed for every individual. Table 3 lists the parameters of the tuning schedule for every task. The tuned hyperparameters can be found Table 4
chosen to be the mean hyperparameters
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 Section 5.1 This 100 parameter task consists of a quadratic bowl for its loss landscape. Using a random uniform orthogonal matrix U and 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 is set to H U and the center set to the origin. However, whenever the loss and gradient are evaluated, the center of the quadratic bowl is perturbed by an i.i.d. random standard normal offset in each dimension. The initialization for this task is set to the origin. Due to the random wandering of the center, the expected loss rises linearly over time unless the optimizer acts prevent this, driving the error towards a steady state distribution. The expected loss after infinitely many steps can then be taken measure of the quality of optimizer. The optimal solution for this task is select the currett.
20

---

Under review as a conference paper at ICLR 2023
Table 3: Noise and step number schedules for tuning the optimizers' hyperparameters using the genetic algorithm presented in Appendix
Generation
Noisy Quadratic Bowl
Rosenbrock Function
Image Generation
Noise stddev
steps
Noise stddev
steps
Noise stddev
# steps
1k
200
3
1
1k
200
3
lk
2
1k
200
3
1k
3
1k
2.5
200
3
1k
4
1 1.5k
200
2
1.5k
5
1.7
1.5k
1.5
200
1.7
1.5k
6
1.4
2k
1
200
1,4
2k
7
1.2
3k
0.75
200
1.2
8
0.9
5k
0.5
200
0.9
5k
9
0.6
8k
0.3
200
0.6
8k
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 a achieve nonzero loss which can be analytically calculated to be 7.412. Table shows various optimizers' performances after having taken many steps.
F.2 CNN IMAGE GENERATION TASK DETAILS
This section explains the CNN image generation task of Section 5.2 which is similar to the task of training a PixcICNN (Oord et al 2016). Like PixeICNN, CNN generates pixels row by and column by column, and classifies the brightness of each pixel into 256 classes with crossentropy loss. Our data preprocessing is follows. An MNIST image randomly selected, and 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 blackened. The input into the CNN consists of this partially masked/blackened image (divided by 256 for normalization), an image indicating which pixels are specifically masked/blackened (indicated by -1 and 1). another image indicating which pixels are left of the selected pixel (indicated by -1 and 1), an image of a linear gradient from -1 to 1 in the x 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 vision tasks involving collection of information from specific locations of an image specified by the data (Liu et al. 2018). The preprocessed data is visualized in Figure 6
pixel
The CNN architecture we use autoregression consists of:
5 input channels previously described.
Residual connection to Point A.
One pixel of zero padding, and convolution with 3 by 3 filters to 20 channels, with no activation.
Point A.
The following indented items are repeated 5 times.
The following indented items are repeated times.
* Residual connection to Point B.
Convolution with 1 by filters to 40 channels, with arctangent activation. We the aretangent to mitigate gradient norm issues.
One pixel of zero padding, and three different depthwise convolutions concate-
nated together, with by 3 filters to 120 channels, with arctangent activation.
Convolution with by 1 filters to 20 channels, with no activation.
Point B.
21

---

Under review as a conference paper at ICLR 2023
Table Hyperparameters used for the experiments in Section | after tuning hyperparameterss with a genetic algorithm as in Appendix B and halving the learning rates (equiv. initial learning rates for LODO variants) for the image generation task. / and 81 generally represent momentum decay rates while 32 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
Adam
Learning Rate
1.164
0.9704
0.0009554
81
0.465
0.864
0.9323
82
0.9884
0.99804
0.99505
Momentum
Learning Rate
1.394
0.09870
0.003411
8
0.529
0.9359
0.9640
RMSprop
Learning Rate
0.449
0,004318
4.167 x 10 -
0.04943
0.02836
0.002258
3
0.595
0.880
0.936
Yogi
Learning Rate
2.169
0.2991
0.0009340
31
0,4362
0.9273
0.9319
32
0.9999723
0.998787
0,999708
LARS
Learning Rate
0.0008552
3
0.9343
Weight Decay
4.839 x 10-5
L-BFGS
Learning Rate
1,204
23002
O-LBEGS
Learning Rate
1.050
36721
LODO
Meta-Learning Rate
0.009600
0.0001394
7.946 x 10
3
0.195
0.897
0.9343
Initial Learning Rate Meta-Learning Rate
0.270
0.2946
0.08459
LODOO-Dagoonal
0.0005196
8
0.9860
Initial Learning Rate Meta-Learning Rate
0.1325
LODO-Global
7.951 x 10
0.9525
Initial Learning Rate
0.05583
LODO-Residuals
Meta-Learning Rate
3.829 X 10-5
0.9301
Initial Learning Rate
0.02
LODO-SGD
Meta-Learning Rate
0.0007196
3
0.9499
Initial Learning Rate
0.1035
Average pooling of by 2 blocks to halve the image size, with a pixel of zero padding beforehand if the image size is odd.
Convolution with 1 by filters 256 channels, with softmax activation.
The loss is then the average crossentropy between true brightness of the query pixel and the distribu- tion given by the softmax output of this CNN, over batch size of 256 images. The whole CNN has about 94696 parameters, which are initialized with LeCun normal initialization (Klambauer et al. 2017). The task for the optimizer is to train these parameters minimize this loss.
Figure shows some imitation MNIST images generated using this CNN by sampling pixels one by one.
22

---

Under review as a conference paper at ICLR 2023
Table 5: Average tracking error of the quadratic bowl minimum the noisy quadratic bowl task of Section 5.1 Values are are averaged over the last 10% of training before the stated training milestone, with means and standard deviations produced across 8 optimization runs with different randomization seeds. The theoretical best possible loss using Newton's 's method is also listed. The version L-BFGS one with stochastic modifications from (Schraudolph al. 20077) instead of the original from (Nocedal & Wright 1999). Our timing setup is described in Appendix
Training loss
Optimizer
100k steps
300 sec.
Adam (Kingma & Ba 2014
15.28 1 0.07
15.26 1 0.08
Momentum
16.59 + 0.08
16.56 = 0.05
RMSprop (Hinton al.
2012
22.37 0.06
22.47
Yogi (Zahcor et al. 2018)
15.35 + 0.10
15.16=0.00 0.05
L-BFGS Schraudolph of al.
2007
19.30 1.04
40.60 = 1.40
O-LBFGS (Schraudolph al.
2007
13.96 + 0.08
10.80 0.17
LODO (ours)
8.99 + 0.05
10.05 0.22
Newton Method (Best Possihle)
7.41
E
AT
Figure 6: Batch of tensors of preprocessed MNIST images from the image generation task of Section 5.2, each as one of the rows of the image. Shown in each of 5 columns are the masked input, the jeft-of-selected-pixe. indicator, visible mask, and two gradient images. The images in each row are concatenated together into a 28 x 28 5 data tensor and then used input into the CNN.
G ROSENBROCK FUNCTION MINIMIZATION EXPERIMENT
We probe the behavior of LODO with small test task of finding the minimum of rescaled Rosen-
brock function fxx y) 0.01(x 1)² + (a² - - which has no local minima and one global minimum at (I, (1, 1). We initialized the optimizers at (xr y) (-0.5, 2) and gave them 200 steps to run. The trajectory taken by LODO, shown in Figure g is similar to the short timescale dynamics of other optimizers using momentum, in that it tends to overshoot and then correct itself
an oscillatory manner. Learning curves in Figure and losses in Table 6 show the performance of all the optimizers this task.
23

---

Under review as a conference paper at ICLR 2023
2
2
6
2
7
4
1
2
t
y
7
7
1
8
9
1
Figure 7: Grids of 16 imitated MNIST images generated the image generation CNN of Section 5.2 trained for 300k steps using RMSprop, Adam, Yogi, and LODO respectively.
Table 6: Mean losses between steps 180-200 while training on the Rosenbrock function minimiza- tion task, with various optimizers. The standard deviation calculated over 8 test runs of LODO because its G neural network architecture is randomly generated.
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
10
training loss
10-2
Momentum
RMSprop
Adam
10-3
Yogi
LODO
10
50
100
150
200
step
Figure 8: Log loss function of step, when using various optimizers the Rosenbrock function minimization task.
H TRAINING LOOP TIMING DETAILS
2.
13
Iniial cabion
Momontum RMSpprp
This section describes how we 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 2 Nvidia Volta V10 GPUs. Time reported includes all training time (forward and backward propagation, op- timizer computation, data loading, preprocessing. etc.) except it does not include time taken to evaluate metrics such as the Hessian approximation error and the valida- tion and test losses and accuracies.
Adam
855
Yog LODO
Minimum
-05
-35
Figure 9: 100 step trajectories of vari- ous optimizers on the Rosenbrock func- tion minimization task. The red star marks the initialization and the green star marks the location of the global minimum.
24


Reviews:
[{"review_id": "kJm7oEjXWK4", "reviewer": "Reviewer_w1wa", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors introduce a learn-to-optimize (L20)-based approach for quasi-Newton algorithms. The main idea is to learn on-the-fly an approximation of the inverse Hessian matrix modeled as the product of random permutation and block diagonal matrices. The proposed architecture called LODO consists of a linear neural network whose depth affects the representation power of the Hessian approximate. The authors provide a theoretical representability theorem showing that LODO can exactly represent the Hessian matix with high probability that increases with the depth of the linear neural network. They also provide simulated and an MNIST image generation experiment showing the promising performance of the proposed approach.", "summary_of_the_review": "The  paper introduces a L2O-based algorithm for quasi-Newton methods. The idea of approximating the inverse Hessian with linear neural networks whose parameters are learned on-the-fly is interesting. However, theoretical results are not presented clearly. Hence, it is hard to assess their significance and value the importance of the specific parametrization of the inverse Hessian introduced in the paper.\nMoreover, the organization of the experimental part could be improved.\n\n-----------------------------------------------------\nPost-Rebuttal Comment:\nI would like to thank the authors for their time and effort to address my comments/concerns.\nAt this time, I will my score unchanged.\n\n", "strength_and_weaknesses": "Strengths:\n\n1) Learn-to-optimize (L2O) algorithms leverage the power of deep neural networks to achieve better convergence rates for several problems over classical optimization algorithms. \n2) LODO builds on these ideas to come up with a novel L2O approach for quasi-Newton algorithms. \n3) The whole idea is quite attractive since it can lead to algorithms that will take advantage of Newton-type methods using the strengths of the L2O framework.   \n\nMain comments/ Weaknesses:\n1) It is hard to follow several parts of the paper. Specifically, Section 4 is poorly written. In Sect. 4.1 the authors describe the Hessian learning dynamics without giving the full details of the setup they consider. Hence it is hard to follow the ideas given later. \n2) In Section 4.2, Definition 1, the definition of function $\\epsilon$ is missing. Besides, it is hard to follow the text, which is densely written and not clear at all. \n3) The statement of Theorem 1 lacks clarity and important details are missing. How $G(\\theta)$ is sampled ? What is M? Also $\\epsilon()$ is not defined (see also above).\n4) In Section 5, Section 5.1., it is not clear why the training loss of other methods .e.g. RMSprop, Momentum etc. remains so much higher than LODO. \n5) Section 6 could merge with Section 5. \n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "e89yINh3o8W", "reviewer": "Reviewer_oyKA", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to meta-learn an optimizer to approximate Newton's method, namely to learn a pre-conditioner for gradient descent to approximate the inverse Hessian.\nIt proves that the method learns the inverse Hessian for quadratic loss functions, and that the proposed parameterization of the pre-conditioner is expressive under some circumstances.\nThe method is tested on autoregressive image generation for MNIST.\n\n", "summary_of_the_review": "The problem is interesting but some of the claims in this paper are wrong or obvious, and comparison with previous work is not appropriate.\n", "strength_and_weaknesses": "Strengths\n\n- Meta-learning optimizers is a promising area of research.\n\n\nWeaknesses\n\nSome of the claims in this paper are wrong or obvious, and comparison with previous work is not appropriate.\n\n- Section 4.1 is trivial. It is obvious that the method learns the inverse Hessian in the case of a quadratic loss, because it is known to be the best pre-conditioner in that case (it converges in one step from any initial condition).\nHowever, for non-quadratic loss functions the best pre-conditioner is not the inverse Hessian, and the proposed method will not learn the inverse Hessian.\nThis is particularly obvious for non-convex loss functions, where the inverse Hessian is not even positive definite and Newton's method would not even converge to a minimum of the loss (see e.g. https://arxiv.org/abs/1406.2572)\n\n- The statement \"the true inverse Hessian is guaranteed to be symmetric positive-definite\" is wrong, that is not true for non-convex losses. \nI assume that is the field of application of this method since the authors apply their method to non-convex losses in sections 5.2, 5.3.\nIf the authors refer to convex losses, then they should compare their method with other methods for convex optimization.\n\n- Related to the last point, for autoregressive image generation the authors report that \"we could not get any quasi-Newton methods to converge on this task.\"\nIt seems that authors are not aware that quasi-newton methods should not be expected to converge on non-convex problems, again because the Hessian is not positive definite.\n\n- Comparison with other methods is underwhelming and other, more powerful methods are not even considered.\nI do not even consider the quadratic problem because results in that case are trivial.\nFor the autoregressive image generation task, the proposed method does not perform significantly better than momentum.\nOther, more powerful methods are not even compared with (see e.g. https://arxiv.org/abs/2006.08877).\n\n- Even without all problems above, the method is not so novel. \nMany other studies have tried to learn pre-conditioner for neural networks, inclusing some that the authors do not cite (see e.g. https://arxiv.org/abs/1902.03356)\n\n\nMinor:\n- Even in the quadratic case, in Fig.3 (Left) it seems that the error does not converge to zero, meaning that the method fails to learn the inverse Hessian.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4tAE35FWRY", "reviewer": "Reviewer_XFBK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work proposes LODO, an L2O that performs quasi-Newton optimization without any meta-training. Specifically, LODO has a hypergradient optimization structure while the parameterization of the approximated inverse Hessian is chosen to be a linear neural network. The authors prove that under certain simplified situation, LODO learns the true inverse Hessian, and that the linear neural network construction is expressive in that it can represent all linear neural networks smaller by a logarithmic factor. Experiments are provided to evaluate the effectiveness of LODO.", "summary_of_the_review": "This work can be seen as an initial attempt for developing online L2O methods without any meta-training. However, the discussion of LODO in the current version is insufficient, see the main review.", "strength_and_weaknesses": "Strength:\n- The construction of LODO seems interesting, which could inspire future development on online L2O methods without any meta-training.\n- The theoretical discussion on the inverse Hessian approximation and the expressiveness seems solid. \n\nWeaknesses:\n- The empirical performance of LODO is not promising, and only limited experimental results are provided.\n- I believe that the theoretic discussion in section 4.1 requires the Hessian $H$ to be at least PSD, since $G(\\theta_t)$ is constructed to be PSD. But it is not clear to me which step of the proof relies on the PSDness. This needs to be clarified. \n- When the objective function is non-convex, such that $H$ is potentially not PSD, what will be learned by $G(\\theta_t)$? Will it capture all the positive curvature of the loss landscape and neglect the negative curvature?\n- I think more ablation study for the effect of each algorithmic component in LODO is necessary, such as comparing LODO without momentum, LODO, plain momentum, LODO using SGD to tune the model, etc.  \n\n-----------------------------------\nPost rebuttal: Thank the authors for the response and the additional experiments, which resolve some of my concerns. However, I still think the empirical performance of LODO is not strong enough, and I agree with reviewer oyKA that the comparison with other methods is underwhelming. Thus, I keep my assessment.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject