First-Order Preconditioning via Hypergradient Descent
Authors: Ted Moskovitz
Rui Wang
Janice Lan
Sanyam Kapoor
Thomas Miconi
Jason Yosinski
Aditya Rawal
Venue:  (2020)
Keywords: optimization
deep learning
hypgergradient

Abstract: Standard gradient-descent methods are susceptible to a range of issues that can impede training, such as high correlations and different scaling in parameter space. These difficulties can be addressed by second-order approaches that apply a preconditioning matrix to the gradient to improve convergence.  Unfortunately, such algorithms typically struggle to scale to high-dimensional problems, in part because the calculation of specific preconditioners such as the inverse Hessian or Fisher information matrix is highly expensive. We introduce first-order preconditioning (FOP), a fast, scalable approach that generalizes previous work on hypergradient descent (Almeida et al., 1998; Maclaurin et al., 2015; Baydin et al., 2017) to learn a preconditioning matrix that only makes use of first-order information. Experiments show that FOP is able to improve the performance of standard deep learning optimizers on several visual classification tasks with minimal computational overhead. We also investigate the properties of the learned preconditioning matrices and perform a preliminary theoretical analysis of the algorithm.

Under review as a conference paper at ICLR 2020
FIRST-ORDER PRECONDITIONING VIA HYPERGRADIENT DESCENT
Anonymous authors Paper under double-blind review
ABSTRACT
Standard gradient descent methods are susceptible to a range of issues that can im- pede training, such as high correlations and different scaling in parameter space. These difficulties can be addressed by second-order approaches that apply a pre- conditioning matrix to the gradient improve convergence. Unfortunately, such algorithms typically struggle to scale to high-dimensional problems, in part be- cause the calculation of specific preconditioners such as the inverse Hessian or Fisher information matrix is highly expensive. We introduce first-order precon- ditioning (FOP), a fast, scalable approach that generalizes previous work on hy- pergradient descent (Almeida et al., 1998; Maclaurin al. 2015 Baydin al., 2017) to learn preconditioning matrix that only makes use of first-order informa- tion. Experiments show that FOP is able improve the performance of standard deep learning optimizers on visual classification and reinforcement learning tasks with minimal computational overhead. We also investigate the properties of the learned preconditioning matrices and perform a preliminary theoretical analysis of the algorithm.
INTRODUCTION
High-dimensional nonlinear optimization problems often present a number of difficulties, such as strongly-correlated parameters and variable scaling along different directions in parameter space (Martens) (016)). Despite this, deep neural networks and other large-scale machine learning models applied to such problems typically rely on simple variations of gradient descent to train, which is known to be highly sensitive these difficulties. While this approach often works well in practice, addressing the underlying issues directly could provide stronger theoretical guarantees, accelerate training, and improve generalization.
Adaptive learning rate methods such as Adam (Kingma and Ba 2014), Adagrad (Duchi al. 2011 and RMSProp (Tieleman and Hinton 2012) provide some degree of higher-order approximation to re-scale updates based on per- per-parameter behavior. Newton-based methods make of the curvature of the loss surface to both re-scale and rotate the gradient in order to improve convergence. Natural gradient methods (Amari 1998) do the same in order enforce smoothness in the evolution of the model's conditional distribution. In each of the latter two cases, the focus is on computing a specific linear transformation of the gradient that improves the conditioning of the problem. This transformation is typically known as preconditioning, or curvature, matrix. In the case of quasi- Newton methods, the preconditioning matrix takes the form of the inverse Hessian, while for natural gradient methods it's the inverse Fisher information matrix. Computing these transformations is typically intractable for high- riggh-imenssonal problems, and while a number of approximate methods exist for both (e.g., (Byrd et al. 1996. Martens and Grosse 2015) Grosse and Martens (016)), they are often still too expensive for the performance gain they provide. These approaches also suffer from rigid inductive biases regarding the nature of the problems which they are applied in that they seek to compute or approximate specific transformations. However, in large, non-convex problems, the optimal gradient transformation may be less obvious, may change the course of training.
In this paper, address these issues through method we term first-order preconditioning (FOP). Unlike previous approaches, FOP doesn't attempt to compute a specific preconditioner, such as the inverse Hessian, but rather uses first-order hypergradient descent (Maclaurin et al. 2015) to learn

---

Under review as a conference paper at ICLR 2020
Algorithm Learned First-Order Preconditioning (FOP)
1: Require: model parameters 8, objective function J, FOP matrix M, learning rate c, hypergra-
dient learning rate p
2: for [= 1,2.... do
3:
Draw data (0)) (0) ~
4: Perform forward pass: g(t) = foco (z((1)
5:
Compute loss (v)(), g(())
6:
Update inference parameters O: g(e+ +- + cM V Voc
7:
Update preconditioning matrices:
M(++1) t ( + pe (Voco [Voce1))]] + Vocen IV Voon))" M
8: Cache J
adaptable transformation online directly from the task objective function. Our method adds minimal computational and memory cost to standard deep network training and results improved conver- gence speed and generalization compared to standard approaches. FOP can be flexibly applied to any gradient-basee basedd optimization problem, and we show that when used in conjunction with stan- dard optimizers, it improves their performance. To knowledge. this is also the first successful application of any hypergradient method to the ImageNet dataset (Deng et al. 2009).
2
FIRST ORDER PRECONDITIONING
2.1 THE BASIC APPROACH
Consider parameter vector and loss function J. A traditional gradient update with precondi- tioning matrix P can be written as
01++1) -eit)
V Pocn (().
Our goal is learn P. However, while we place other constraints to ensure that is positive semi-definite, and therefore does not reverse the direction of the gradient, we reparameterize P the product matrix M with itself, changing Equation[][ce
preconditioner, in order
@((+1) g( e (OT V Voco
Under reasonable assumptions, gradient descent is guaranteed to converge with the use of even random symmetric, positive-definite preconditioner, we show in Appendix A.3. Because g()) is function of (t-11), we can then backpropagate from the loss at iteration to the previous iteration's preconditioner via simple application of the chain rule:
a
a,(()) 20(1)
(3)
0M(-IJ
20 DM
By applying the chain and product rules to Equation 2 the gradient with respect to the preconditioner is then simply
(() = CreeVoorei Votcn V )(t- + ((tc-n((--1)
( (ooor)o) M0 (4)
We provide more detailed derivation in Appendix A.I Note that ideally would compute V J to update (t), but as don't have access to (t-1) yet, we follow the example of Almeida et al. (1998) and assume that J is smooth enough that this does not have an adverse effect on training. The basic approach is summarized in Algorithm We use supervised learning as an example, but the same method applies to any gradient-based optimization. The preconditioned gradient can then be passed to any standard optimizer produce update for M. For example,
2

---

Under review as a conference paper at ICLR 2020
booth function Co, e 2ymm
Hmmebbaaur function yi 0e e 133 yi
5GD
Adam
Adam
FOP
FOP
Figure 1: A comparison of FOP to common optimizers toy problems. The red dot indicates the initial position on the loss surface. The purpose these visualizations not to establish the su- periority of one optimizer over another, but rather to gain intuition for their qualitative behavior. (Left) Gradient descent on the Booth function. FOP converges 543 iterations, while SGD takes 832 steps and 6,221 for Adam. (Right) Gradient descent on Himmelbau's 's function. Adam, converg- ing in 5398 iterations, finds a different global minimum from FOP and SGD, which converge 289 and 386 steps, respectively. In both cases, we can see that FOP moves objective function surface compared to the other methods. The poor performance of Adam is likely attributable to the non-stochastic nature of these toy settings.
aggressively across the
describe the procedure for using FOP with momentum (Polyak 1964) in Section 2.3 For multi-
layer networks, order to make the simplest modification to normal backpropagation, we learn separate M for each layer, not global curvature matrix.
To get an intuition for the behavior of FOP compared to standard algorithms, we observed its tra- jectories on set of low www-dimensional optimization problems (Figure IT.. Interestingly, while FOP converged in fewer iterations than SGD and Adam (Kingma and Ba, 2014). it took more jagged paths along the objective function surface, suggesting that while it takes more aggressive steps, is perhaps also able to change direction more rapidly.
2.2 SPATIAL PRECONDITIONING FOR CONVOLUTIONAL NETWORKS
In order further reduce the computational cost of FOP convolutional networks (CNNs), we implemented layer-wise spatial preconditioners, sharing the matrices across both input and output channels (results shown Section 4.. More concretely, a convolutional layer has spatial kernels with shape & x k, can learn preconditioner that is A2 x k2, To implement this, when 0 is a 4- tensor of kernels of shape 1xxxIx00 where and are the input and output channels, respectively, reshape it to a matrix of size 1²2 IO, left- left-multiply it by the leamed curvature matrix, and then reshape it back to its original dimensions. When & is small, as is typically the case in deep CNNs, this preconditioner is small well, resulting in both computational and memory efficiency. For large fully-connected networks, we adopt a low-rank preconditioner to save computation. In Appendix A.4 we offer further details and show that FOP still effective even when the rank is very low.
2.3
FOP FOR MOMENTUM
FOP can be implemented alongside any standard optimizer, such as gradient descent with momen- tum (Polyak 1964). Given parameter vector 0 and a loss function J, basic momentum update with FOP matrix is typically expressed as two steps:
(1+1) = (t) + (1 (T) Vown
(5)
(1++) ((1) ((+1)
(6)
3

---

Under review as a conference paper at ICLR 2020
9-Layer CNN
momenium monentum PP-HD
0.8
monsentum FDP (mm
Methed
Test Actuney
Adil Params
Add. Time (9)
traniing bos
0.6
momonium FOP
momenium
B0. 0.1
0
0.0
S-HD
91.0++00 0.2
0.2
PP
91.5 1::11000
=.1.MM
5.9
91.3+
FOP
0.2
0.0
20000
10000 Torations
40000
50000
90200
ResNet-18
monormmm
monormum FDP nom
Method
Test Accuncy
Adtl Params
Adt. Time (16)
momenam POP
momentumm
BOL7 + 0.2
0
0.0
S-HD
60.7 1: 0.5
22
0.3
69.8
2737
7.1
FOP-aorm
69.9
197
2.1
FOP
CO0076
Figure Results on CIFAR-10 (top) and ImageNet (bottom), averaged over runs. All models are trained with momentum as the base optimizer. We can see that FOP converges more quickly than standard and baseline methods, with slightly superior generalization performance. Learning spatial curvature matrix adds negligible computational cost to the training process.
where v is the velocity term and a is the momentum parameter. Combining Equations 5 and 6 allows us write the full update
g(++1) = ((t) (tro(t) eM (() ( B.cc
If, as in Maclaurin et al. (201)), we were meta-learning M or only updating M after certain number iterations, we would then have to backpropagate through v to calculate the gradient for M. As we are updating M online, however, we only need to calculate V J. Therefore, the update is the same as for standard gradient descent. The experiments Section 4 were performed using this modification of momentum.
RELATED WORK
Almeida et al. (9988) introduced the idea of using gradients from the objective function to learn opti-
mization parameters such as the learning rate or a curvature matrix. However, their preconditioning matrix was strictly diagonal, amounting to approximate Newton algorithm (Martens 2016), and
they only tested their framework on simple optimization problems with either gradient descent or SGD. This is related to common deep learning optimizers such Adagrad (Duchi et al.) 2011 and Adam (Kingma and Ba 2014), which also learn adaptive per-parameter learning rates, but unlike FOP, do not induce rotation the gradient. As note in Section 2.3 an advantage of FOP is that it may also be used in conjunction with any such optimizer. More recently. Maclaurin et al. (2015) applied the backpropagation-zeee warpgattioo-ccoss---is across-iterations approach in neural network context, terming the process hypergradient descent. Their method backpropagates through multiple iterations of the training process of a relatively shallow network meta-learn a learning rate. However, this method can incur significant memory and computational cost for large models and long training times. Bay- din et al. (2017) instead proposed an online framework directly inherited from Almeida et al. (1998) that used hypergradient-based optimization in which the learning rate is updated after each itera- tion. Our method extends this idea to not only learn existing optimizer parameters (e.g.. learning rate, momentum), but to introduce novel ones in the form of -ia-diag,nal, layer-specific precon- ditioning matrix for the gradient. It's also important to discuss the relationship of FOP to other, non-hypergradient preconditioning methods for deep networks. These mostly be sorted into one
4

---

Under review as a conference paper at ICLR 2020
SGD + momentum
16a
38.0
10.3
17.9
671
10.3
0.5
16a
38.
161
35.3
18.
10.9
monerium
0.9
I60
224
36.8
565
37.1
872
60.1
68.5
220
00.3
0.99
26-7
41.
99.
043
8331
933
100
35.0
30
1003
1.0
63.9
13.
10.1
100
12.0
100
100
15.0
22.0
10.3
momentum
10C
0.5
163
214
259
$6.0
90.6
06.5
96.3
46.5
600
Adbri
learning
0.99
16.1
71.
33
1.0
66.6
714
982
12.0
628
100
16.0
220
603
16:05
06:08
2.2gg
0.0901
0.e0ar6
0.0122
0.01
0.066
fommnng rate
(a)
(b)
Figure 3: Adding FOP improves the hyperparameter robustness of standard optimizers. (a) The final test accuracy of 9-layer CNN trained on CIFAR-10 for different settings of SGD with momentum (top) and SGD with momentum and FOP (bottom), averaged over three runs. Settings in which adding FOP improves performance by at least one standard deviation are highlighted in blue. FOP appears be most useful for higher values of the learning rate and momentum parameters. The FOP matrices were trained with Adam with learning rate of 5 x 10-1, (b) The performance of Adam for a range of learning rates both with and without FOP, averaged over three runs. While performance is similar, the top performing models are improved by the addition of FOP. The FOP matrices were trained using the same settings as the models in (a).
of two categories, quasi-Newton algorithms and natural gradient approaches. Quasi-Newton meth- ods seek learn approximation of the inverse Hessian. L-BFGS, for example, does this through tracking the differences between gradients across iterations (Byrd et al.) 1996). This is significantly different from FOP, although the outer product of gradients used in the update for FOP can also be an approximation of the Hessian or Gauss-Newton matrices (Bottou et al. 2016). Natural gradient methods, such as K-FAC (Martens and Grosse 2015) and KFC (Grosse and Martens 2016). which approximate the inverse Fisher information matrix, bear much stronger resemblance to FOP. How- ever, there are notable differences. First, unlike FOP, these methods perform extra computation to ensure the invertibility of their curvature matrices. Second, the learning process for the precondi- tioner in these methods is completely different, as they do not backpropagate across iterations.
EXPERIMENTS
We measured the performance of FOP on visual classification and reinforcement learning tasks. In order to measure the importance of the rotation induced by the preconditioning matrices addition to the scaling, we also implemented hypergradient descent (HD) methods to learn scalar layer-wise wise learning rate (S-HD) and a per-pare parpparmettr (PP-HD) learning rate. The former is the same method implemented by [Baydin et al. (2017), and the latter is equivalent to a strictly diagonal curvature matrix. We also implement method we call normalized FOP (FOP-norm), in which we re-scale the preconditioning matrix to avoid any effect the learning rate and rely solely standard learning rate settings. Further details on this method can be found Appendix A.2 All experiments were implemented using the TensorFlow library (Abadi et al. 2015
!Code currently available at this link: https: //tr///ri/i
ve. ve. google. com/ fi 1 http////wwwxxx/aa///o/oaaaaaaaaa fxbuxa (awpbuxxaJJNPPGG. /tw. http:///a//eeaaasaaaaaa.nn
5

---

Under review as a conference paper at ICLR 2020
800
100
200
Soore
100
Score
-100
Momentum
Nomentum
Adam
Adam
Momentum
1000
2000
3000
4000
6020
1003
2003
5000
4000
0000
6003
7000
Number of PPO Sleps
Number of PPO Steps
(a)
(b)
Figure 4: Bipedal Walker on varying terrains. We plot the the median reward (of the best seen policy so far) per PPO step across 10 runs for (a) and runs for (b), respectively. The shading denotes the 95% bootstrapped confidence intervals. Momentum with FOP outperforms momentum alone significantly. both in speed of learning and final score, in addition beating Adam.
4.1 CIFAR-10
For CIFAR-10 (Krizhessky) 2009), an image dataset consisting of 50,000 training and 10,000 test 32 32 RGB images divided into 10 object classes, implemented 9 9-layer convolutional archi- tecture inspired by Springenberg et al. 2014). We trained each model for 150 epochs with a hatch size of 128 and initial learning rate 0.05, decaying the learning rate by factor of 10 after 80 epochs. For S-HD, PP-HD, and FOP, we use Adam as the hypergradient optimizer with learning rate of le-4. The results are plotted in Figure 2 FOP produces significant speed-up in training and im- proves final test accuracy compared to baseline methods, including FOP-norm, indicating that both the rotation and the scaling learned by FOP is useful for learning.
4.2 IMAGENET
The ImageNet dataset consists of 1,281,167 training and 50,000 validation 299 299 RGB images divided into 1,000 categories (Deng et al., 2009). Here, we trained a ResNet-18 (He et al., (015) model for 60 epochs with batch size of 256 and initial learning rate of 0. decaying by factor of 10 at the 25th and 50th epochs. A summary of our results is displayed in Figure 2 We can see that the improved convergence speed and performance observed on CIFAR- 1-10 is maintained on this deeper model and more difficult dataset.
4.3 HYPERPARAMETER ROBUSTNESS
In addition to measuring peak performance, we also tested the effect of FOP on the robustness of standard optimizers hyperparameter selection. [aadinn al. 2017) demonstrated the ability of scalar hypergradients to mitigate the effect the initial learning rate on performance. We therefore tested whether this benefit was preserved by FOP, as well as whether extended other hyperpa- rameter choices, such as the momentum coefficient. Our results, summarized in Figure B support this idea, showing that FOP can improve performance on wide array of optimizer settings. For momentum (Fig. 33), we see that the performance gap is greater for higher learning rates and mo- mentum values, and in several instances FOP is able to train successfully where pure SGD with momentum fails. For Adam, the difference is smaller, although in the highest-performance learning rate region adding FOP to Adam outperforms the standard method. We hypothesize that this smaller difference is in large part due to unanticipated effects that preconditioning the gradient has the adaptive moment estimation performed by Adam. We leave further investigation into this interaction for future work.

---

Under review as a conference paper at ICLR 2020
(a)
procondiboring matri aiganspactra
0.14
kayo
0.12
0% training
25% training
100% tralining
0510
byyer
layer
3.09
Maye
0.54
0.02
(b)
0.00
eggemvlue Index
(c)
Layer
Layer
Layer
Figure 5: Understanding the learned preconditioning matrices (M for CIFAR-10. (a) The evolution of an example preconditioning matrix throughout the training process from the ninth layer in a ResNet-18 model trained on ImageNet. Each layer learned a similar whitening structure. (b) The histograms of matrix values across layers during training. The training process is traced by going from back to front the plots. We can see that the convergence of the values of the matrix, corresponding
stronger decorrelation structure and reduced T.2 norm, is stronger in the higher layers of a network. (c) The sorted eigenvalues of the final learned preconditioning matrices for the first seven layers of 9-layer network trained on CIFAR-10 (the top two layers were 1 X 1 kernels). The distribution shifts downward and becomes more uniform in higher layers. This is interesting, as while a uniform distribution of eigenvalues is considered helpful in aiding convergence, the downward shift in values makes the matrix less invertible.
4.4 REINFORCEMENT LEARNING
Reinforcement learning (RL) tasks are often more challenging than supervised learning, since the rewards RI. are sparse and the loss-landscape frequently deceptive (Sutton and Barto 2018). We evaluated the performance of FOP on one such RI. task the training of 2D bipedal robot walker [Brockman et al. 2016 Klimov 2016) in two different terrains (see the inserts in Figures (a) and (b) for illustration). This 2D robotic domain has been used in recent literature a benchmark and for validation of new RL. algorithms (Ha 2017 2018 Song et al.) 2018 Wang et al. 2019). The agent is trained to move forward (from left to right) in given terrain, within time limit of maximum 2000 steps and without falling over. The controller for the agent consists of simple feedforward policy and value networks. Both the networks are trained using the Proximal Policy Optimization (PPO) algorithm (Schulman et al. 2017) (see Appendix A.5 for details).
Figures 4 (a) and (b) plot the bipedal walker scores obtained from training the controller in two dif- ferent terrains. For both terrains, FOP with momentum trains faster and achieves better asymptotic performance than baseline methods (SGD with momentum and Adam), thus demonstrating the ef- fectiveness of FOP in RL tasks. We hypothesize that FOP's advantage results in part from deceptive loss surfaces. since FOP's ability to quickly change direction (Figure [ may help avoid getting stuck in local optima (see Appendix A.5 for discussion of deceptiveness in this task).
5 WHAT IS FOP LEARNING?
By studying the learned preconditioning matrices, it's possible to gain an intuition for the effect FOP has on the training process. Interestingly, we found visual tasks induced similar structures in the preconditioning matrices across initializations and across layers. Visualizing the matrices (Figure 5)) shows that they develop decorrelating, or whitening, structure: each of the positions in the 3x3 convolutional filter sends strong positive weight to itself, and negative weights to its immediate neighbors, without wrapping over the corners the filter. This is interesting, as images are known to have a high degree of spatial autocorrelation (Barlow) 1961 1989). As mechanism for reducing redundant computation, whitening visual inputs is known to be beneficial for both retinal processing
in the brain (Atick and Redlich, 1992 Van Hateren 1992 and in artificial networks (Desjardins
jet al. 2013; Huang et al. 2018). However, it is more unusual to consider whitening of the learning signal, as observed in FOP, rather than the forward activities.
7

---

Under review as a conference paper at ICLR 2020
This learned pattern is accompanied by shift in the norm of the curvature matrix, as the diagonal elements, initialized to one, shrink in value, and the off-diagonal elements grow. This shift in dis- tribution is visualized in Figure Ep and grows stronger deeper in the network. It is possible that greater degree of decorrelation is helpful for kernels that must disentangle high-level representations.
We can also examine the eigenvalue spectra for the learned matrices across layers (Figure We can see that the basic requirement that in general preconditioning matrix must be positive semi- definite, so as not reverse the direction of the gradient, is met. However,the eigenvalues are very small in magnitude, indicating a near-zero determinant. This results in a matrix that is essentially non-invertible, an interesting property, as quasi-Newtor and natural gradient methods seek com- pute or approximate the inverse of either the Hessian or Fisher information matrix. The implications of this non-invertibility are avenues for future study. Furthermore, the eigenvalues grow smaller, and their distribution more uniform, higher in the network, in accordance with the pattern observed in Figure 5p. A uniform eigenspectrum seen as an attribute of an effective preconditioning matrix Li 2015 indicates an even convergence rate in parameter space.
6 CONVERGENCE
Our experiments indicate that the curvature matrices learned by FOP converge to relatively fixed norm roughly two-thirds of the way through training (Figure 5p). This is important, as it indicates that the effective learning rate induced by the preconditioners stabilizes. This allows us to perform a preliminary convergence analysis of the algorithm in a manner analogous to |aaddin al. (2017).
Consider a modification of FOP in which the symmetric, positive semi-definite preconditioning matrix p(t) .M (+) (O) is rescaled at each iteration to have a certain norm 7(1), such that ((()) so
|| when t small and (()) s p(zo) when t is large, where p(æ) is some chosen constant. Specifically, in Baydin al. (017)) set 7(00 ((() ||2 + (1 6(1))p(ee) where 6(1) is
some function that decays over time and starts training at (c.g.. 1/t²).
This formulation allows us to extend the convergence proof of Baydin al. 2017 FOP, under the same assumptions about the objective function J:
Theorem Suppose that convex and L-Lipschitz smooth with / < K for some fixed K and all model parameters 0. Then Og + 0" if pf < L/L and (ō(() + - co, where the O. are generated by (nonsttochastie) gradient descent.
Proof. We can write
||piil]] <
1
V
J]
Vo.
<
|+ Σ Vo / Vo < +ltpk?
where p is the hypergradient learning rate. Our assumptions about the limiting behavior of (ō()) then imply that {(t)] |(o] 0 and so (t) p(xx) as oc. For sufficiently large i, therefore have y(t)) E (2+1) 1) Note also that P is symmetric and positive semi-definite, it will not prevent the convergence of gradient descent (Appendix A.3) Moreover, preliminary investigation shows that the angle of rotation induced by the FOP matrices is significantly below 90% (Appendix Figure A.I. Lillicrap et (2116) showed that such rotation does not impede the convergence of gradient descent. Because standard SGD converges under these conditions (Karimi et al. 2016), FOP must well.
7 CONCLUSION
In this paper, we introduced a novel optimization technique, FOP, that learns preconditioning ma- trix online to improve convergence and generalization large-scale machine learning models. We tested FOP several problems and architectures, examined the nature of the learned transforma- tions, and provided preliminary analysis of FOP's convergence properties (Appendix (6). There are number of opportunities for future work, including learning transformations for other optimization parameters (c.g., the momentum parameter in case of the the momentum optimizer), expanding and generalizing our theoretical analysis, and testing FOP on wider variety of models and data sets.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
M. Abadi, A. Agarwal, P. Barham, E. Brevdo, 7. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. Goodfellow,
Harp, G. Irving, M. Isard, Y. Jia, R. Jozefow- icz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, J. Shlens, B. Steiner, Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Va- sudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL http: //tensorf ow. org/ Software available from tensorflow.org.
L. B. Almeida, T. Langlois, J. D. Amaral, and A. Plakhov. Parameter adaptation in stochastic optimization. In D. Saad, editor, On-line Learning in Neural Networks, pages 111-134. Cam-
bridge University Press, New York, NY, USA, 1998. ISBN 0-521-65263-4.
URL http:
//dl.acm. www. hww..acc..ogccctatiioccccccmmaaa wtt.::ioonmmmmmmdmmmmmmm 304730
S.-L. Amari. Natural gradient works efficiently in learning. Neural Comput., 10(2):251-276, Feb. 1998. ISSN 0899-7667. doi: 10. (00116/00099766630000077777 10. 00.116//03977693300000
URL http::/dx..o...ooo
J. Atick and A. N. Redlich. What does the retina know about natural scenes? Neural Computation, 4(2):196 210, 1992. doi:
neco 1992.4.2 196
H. Barlow. Possible principles underlying the transformations of sensory messages. Sensory Com- munication, 1, 01 1961. doi: 10.755 //ttppess/770002331120000.000000
H. Barlow. Unsupervised learning. Neural Computation, 1(3):295-311, 1989. doi: 10.1162/neco. 1.39.1... URL /RL.ttppa://ba..or////10..
19899....99..... 3.225
A. G. Baydin, R. Cornish, D. Martinez-Rubio, M. Schmidt, and F. D. Wood. Online learning rate adaptation with hypergradient descent. CoRR, abs/1703.04782, 2017. URL http://arxiv. 04782)
L. Bottou, F. E. Curtis, and J. Nocedal. Optimization Methods for Large-Scale Scale Machine Learning. arXiv e-prints, art. arXiv: htwi::66060488..5 Jun 2016.
G. Brockman, V. Cheung. L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. Openai gym. arXiv preprint
2016.
R. H. Byrd, J. Nocedal, and C. Zhu. Towards a discrete newton method with memory for large- scale optimization. Nonlinear Optimization and Applications, page 112, 1996. doi: 10. 978-1-4899-0289-441.
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In CVPRO9, 2009.
G. Desjardins, K. Simonyan, R. Pascanu, and K. Kavukcuoglu. Natural Neural Networks. arXiv e-prints, art. arXiv:1507.00211 Jul 2015.
Dhariwal, C. Hesse, O. Klimov, A. Nichol, M. M. Plappert, A. Radford, J. Schulman, S. Sidor, Y. Wu, and P. Zhokhov. Openai baselines. Gitllub, Gitllub repository, 2017.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. J. Mach. Learn. Res., 12:2121-2159, July 2011. ISSN 1532-4435. URL http:
ord.llecc...og..aaaaaao.....oone 2021006
R. Grosse and J. Martens. A Kronecker-factored approxxxatte Fisher matrix for convolution layers. arXiv e-prints, art. arXiv:1602.014077 Feb 2016.
D. Ha. Evolving stable strategies.
2017.
D. Ha. Reinforcement learning for improving agent design. arXiv preprint arXiv:1810.08:: 1810.03799 2018.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. CoRR, abs/1511.00388,, 2015. URL http:/ wttpaawwwwww....o/a//////// 1133./11111101155555

---

Under review as a conference paper at ICLR 2020
L. Huang, D. Yang. B. Lang, and J. Deng. Decorrelated Batch Normalization. arXiv e-prints, art. arXiv:1804.084555 Apr 2018.
H. Karimi, J. Nutini, and M. W. Schmidt. Linear convergence of gradient and proximal-gradient methods under the polyak-tojasiewiez condition. CoRR, abs/1608.0466 2016. URL http:
//arxiv. org/ abs/ / 608 04636
D. P. Kingma and J. Ba. Adam: A Method for Stochastic Optimization. arXiv e-prints, art. arXiv:1412.6980, Dec 2014.
O. Klimov. Bipedalwallkerhardcore-. v2. https://gym. openai. com 2016.
A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Y. LeCun and C. Cortes. MNIST handwritten digit database. 2010. URL http:tt//y//...eee han/exdb/mniin
X.-L. Li. Preconditioned Stochastic Gradient Descent, arXiv e-prints, art. arXiv:1512.04202, Dec 2015.
T. P. Lillicrap. D. Cownden, D. B. Tweed, and C. J. Akerman. Random synaptic feedhack weights support error backpropagation for deep learning. Nature Communications, 7(1):13276, 2016. doi: 10. 1038///ccmms// 13276. URL ltt thttps::// /tw.///oiio/o org /ttgg//c...
13276
D. Maclaurin, D. Duvenaud, and R. P. Adams. Gradient-based Hyperparameter Optimization through Reversible Learning. arXiv e-prints, art. 1rXiv:1502.03492, Feb 2015.
Martens. Second-Order Optimization for Neural Networks. PhD thesis, University of Toronto, 2016.
J. Martens and R. B. Grosse. Optimizing neural networks with kromecker-factorre approximate curvature. CoRR, abs/1503.05671, 2015. URL BtL.:tpp.//arxxv...rra/////....0
B. Polyak. Gradient methods for the minimisation of functionals. USSR Computational Mathematics and Mathematical Physics, 3(4)8864878, 1963. doi: 00.1016/0041-5553633)))))
B. Polyak. Some methods of speeding up the convergence of iteration methods. Ussr Computational Mathematics and Mathematical Physics, 4:1-17, 12 1964. doi: 10.101660041-553644990111
J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 770.066377 2017.
D. R. Song, C. Yang, C. McGreavy, and Z. Li. Recurrent deterministic policy gradient method for bipedal locomotion on rough terrain challenge. 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), pages 311-318. IEEE, 2018.
J. T. Springenberg, A. Dosovitskiy, T. Brox, and M. Riedmiller. Striving for Simplicity: The All Convolutional Net. arXiv e-prints, art. arXiv:1412.6806 Dec 2014.
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
html
Tieleman and G. Hinton. Lecture 6.5 RmspRms Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
J. H. Van Hateren. A theory of maximizing sensory information. Biological Cybernetics, 68(1): 2329, 1992. doi: 14.1007//000003344
R. Wang, Lehman, J. Clune, and K. O. Stanley. Paired open-ended trailblazer (poet): Endlessly generating increasingly complex and diverse learning environments and their solutions. arXiv preprint arXiv:1901.0775: 2019.
10

---

Under review as a conference paper at ICLR 2020
A SUPPLEMENTAL INFORMATION
A. DERIVATION OF UPDATE FOR M
Our update rule for the model parameter 0, given by Equation is
g(t) g(t-1) - (M ((1-),((-1)
(8)
Then by applying the the chain and product rules the update given by
1 Voco (-eM(t-llV (it
+ V(t) (-eVou (-eVou- M((-))T (v (ooos(c)
(9)
- (Vouo Volc- + ((ren))(-11)
') Mn0
(10)
A.2 NORMALIZED FOP
In order to control for the scaling induced by FOP and measure the effect of its rotation only, we introduce normalized FOP, which performs the following parameter update:
M(MM(1
0 0 -VV TVT IMOMOTI MOTT Voco
(1I)
[MO
where n is the first dimension of M. This update has the effect of normalizing the preconditioner ( M then re-scaling the update by /n to match the norm of gradient descent, | vn, where la is the identity matrix of size n.
A.3 CONVERGENCE OF PRECONDITIONED GRADIENT DESCENT
We demonstrate that given a random, symmetric positive semi-definite preconditioning matrix P. gradient descent will still converge linear rate, modeling our proof after that of Karimi et al. 2016).
Theorem Consider a convex, L-Lipschitz objective function f(0) with global minimum f which obeys the ollyak-Ljjssewwce, (PL) Inequality (Polyak I963).
funnttioo
1 | 2 -(F(0) f*), VO.
(12)
Then applying the gradient update method given by
0t+1
(13)
where P is a real, symmetric positive semi-definite matrix and p 2Amin Nauax is the step size, where Amin and Amax are the minimum and maximum eigenvalues of P, respectively, results in global linear convergence rate given by
f(Ox) f S (1- (p)))))(((0))) f*).
(14)
Proof. First, assume step-size of L/L. Given that is L-Lipschitz continuous, write f(0++1) 1 - f(x)) I (V 0k+1 0x) + T |6 0x11
where f.f f denotes Ve.f. Plugging in the gradient update equation gives
f(0+t)) - s (V.. 1 PV + ト -
1 PV fV
--1 PVF + 21 11
1
(15)
11

---

Under review as a conference paper at ICLR 2020
Let AQ P be the cigendecomposition of P. such that the columns of Q are the orthonormal eigenvectors and A is a diagonal matrix whose entries are the eigenvalues of P. which are all non- negative due to symmetric positive semi-definiteness of P. We then rewrite the first term of Equation 13 as
(VF)
We now change our basis, letting G = Q and define Amin min;{d}} and Amax max; (Ai), where A are the eigenvalues. Then we have
Q' G AG 7 GT - Amin
(16)
Examining the second term of Equation 13, we have
PV = (PV PVS
2L
2L
QQ AQQ AQVI
=
2L
A²G
2L
1
2
GTG
2L
A
(17)
2L
Combining the results of Equations 14 and 15 gives
1
1
5(0x+1) s(0k) - Ammil|/|]
+
> |G||
2L
= =- Amiia 1
1
|G|12
(18)
We can then revert to the original basis:
|| = = QV (V (V QV)=
giving us
1
12 mmxx
f(0x+1)-(((N) - - Amin
/f
(19)
2
By the PL inequality we have that || 2 2p(f((x) -f²) for some μ > Plugging this in gives
f(0x+1) - f(0x) v 11 (2Amin - (f(0x) - f*)
(20)
Then let p == + (2Amin )arax). We have
f(0x-1) f(Ox) -upf((x) + upf*
Rearranging and subtracting f from both sides gives
f(8x+1) fr < (1 (f(x) f().
(21)
Applying Equation
21 recursively gives the desired convergence:
f(0x+1) - - < (1 (1- f*).
(22)
Thus this preconditioned gradient descent converges with step size 2Amis - Standard gradient descent converges with a step size 1/L under these assumptions. We also note that even if P changes over the course of training, the required step-size will vary, but convergence will still oceur.
12

---

Under review as a conference paper at ICLR 2020
Layer angles, meanm44.0
Layer 2 angles,, 433.6
angle degggees
45.0
46-
46.5
My www.hoh
44-
46.0
M/
43.5
43.0
42.5
38
42.0
2500
5000
7500
10000
12500 15000 17500 20000
2500
5000
7500
10000
12500 15000 17500 20000
Layer angles, mean=42.51
Layer angles, mean=42.48
max runs)
48-
46-
-66
angle in Sojiee
MW
44-
40-
36-
2500 5000
17500
2500
10000 12500 15000 17500
Figure A.1: Angles in degrees between ( and (I + M for each layer of 4 layer fully connected network on MNIST. Values are averaged over runs and displayed every 200 iterations. Shaded areas represent the min and max values angle only varies slightly. Notice that the angle is usually slightly below 45,, indicating that the while FOP does induce a rotation, it is far from orthogonal to the vanilla learning signal.
all the runs, showing that the
A.4 LOW-RANK FOP
is an m x n matrix, and we only apply the preconditioning matrix over input dimensions (and share it across output dimensions), then full-rank M would necessarily be m. When is large, preconditioning the gradient becomes expensive. Instead, we can apply a rank-k M, with M m and & m. To ensure stable performance at the beginning of training. we initialize the preconditioning matrix as close as possible to the identity matrix, even for low rank M, so that the algorithm begins as straightforward gradient descent and learns depart from vanilla SGD over time. Thus, we set the preconditioner P to be
P Im + +.M
(23)
where Im is the x identity matrix and Mij NO, o²), where o² is small so that P starts out close to the identity matrix. This effectively decomposes the update into an isotropic scaling of gradient (multiplication by T,, scaled by the learning rate) and rotation (multiplication by M MMT) We tested the effect rank on a simple fully-connected network trained on the MNIST dataset (LeCun and Cortes 2010). The results, shown in Figure A.2 indicate that FOP is able accelerate training compared to standard SGD (with momentum 0.9) with all values of k and improve final test accuracy even with fairly low values of k.
A.5 EXPERIMENTAL SETUP FOR REINFORCEMENT LEARNING
Illustrated in the inserts of Figure (a) and (b), the bipedal robot is made of a hull and two legs, and each leg consists of a hip and knee controlled by motor joints, respectively. The action space therefore has 4 dimensions, each corresponding to the torque applied at each joint, respectively. The state space has 24 state variables, which includes readings from 10 LIDAR rangefinders and 14 other state variables about the robot itself, such the angle and angular velocity of the hull, horizontal and vertical speed of the body, position and angular speed joints, legs contact with ground, etc. The agent is trained move forward (from left to right) in given terrain, within
13

---

Under review as a conference paper at ICLR 2020
The effect rank on FOP
100.0
97.5
95.0
test accuracy
FOP rank 100
FOP rank 25
85.0
4
82.5
FOP rank momentum
80.0
10000
12500
15000
17500
20000
iterations
Figure A.2: FOP is able to improve training even with very low ranks. We plot the test accuracy the course of training for 4-layer fully-connected network with 100 units per layer trained MNIST for different FOP matrix ranks, averaged over 5 runs cach. The gradient was preconditioned by 4m MM where M was rank k. 784 is full rank for the first layer, and 100 full rank for all layers except for the first. The larger k is, the better the performance, both in terms of speed and final accuracy, compared vanilla SGD with momentum 0.9, For 4, final accuracy no longer better, but the initial training remains slightly faster. Final test accuracy of the full rank matrix is better than baseline test accuracy by 0.6% with p-value le-4.
time limit of maximum 2000 steps and without falling distance traveled forward in that step, with penalty terms that consist of applied torques and hull angle from horizontal axis. If the agent falls over, the reward for that step will be -100, and the episode terminates immediately. This asymmetry in positive and negative rewards makes the task deceptive, since the agents could learn move slowly or even move backward or stand still to avoid a large penalty from falling down. For each experiment in a given terrain, while the landscape remains fixed, both initial position of the agent and the initial force applied to its body are randomly initialized.
The reward at each time step is the
We adopt the Proximal Policy Optimization (PPO) algorithm (Schulman al. 2017), more specifi- cally, PPO-Clip, popular and competitive RL algorithm based on the implementation available in OpenAl Baselines (Dhariwal et al. 2017). The controller consists network. The policy network is llyer feedforward neural network with input size of 24, hidden size of 40 (tanh activation), and output size of (bounded between -1 and 1). The value network shares the input and the hidden layers with the policy network and it has separate fully-connected layer that connects to the value output. Note that we apply FOP with full rank to all the layers in- cluding both policy and value layers. We did hyperparamter search for the learning rate in the range of [le - 4. 1e 3] and minibatch size in the range of [8, 64] for each of FOP with momentum and the two bascline methods (SGD with momentum and Adam). The best hyperparameter setting for each method was adopted to run experiments and plot the results in Figure 4 Specifically, the best learning rate setting for FOP with momentum, Adam, and SGD with momentum were -4, 3e and 3.5e 4, respectively, and the best minibatch size setting was 32 for all three methods.
policy network and a value
14


Reviews:
[{"review_id": "rJxhtuoCYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies hypergradient descent for precondition matrices. The goal is to learn an adaptable preconditioning for the task while training. Specifically, they take the gradient of the loss wrt the precondition matrix and update the precondition matrix to decrease the loss. They reparametrize the precondition matrix to ensure it is positive-definite and provide low-rank approximations and they provide cheap approximations for CNNs.\n\nPros:\n- Figure 3 and 4 show promising results on cifar10 with a 9-layer cnn.\n- Figure 4 shows FOP can improve the accuracy for particular hyper-parameters. In cases improving by 2%.\n\nCons:\n- Results on imagnet are not particularly good. The improvement is not significant.\n- Why positive-definite precondition matrix rather than positive-semi-definite?\n- Section 5: why is a degenerate precondition matrix bad? Fisher and Hessian for deep networks can be highly ill-conditioned.\n- Theo 1 seems to have errors. The term M_t in the update rule should show up in the bound on P as an exponential term in the first upper bound.\n- Figure 2: On mnist after 20 epochs the model has not reached 1% test error. Not clear if we can make any conclusions from this figure.\n\nAfter rebuttal:\nI keep my rating as weak reject. I reiterate that results look promising. However, the quality and accuracy of the writing are not acceptable for a paper on optimization. In my original review I only named a few problematic statements. I have to clarify that I do not think fixing only those few is enough.\n\nI am also not convinced about the proof of Theorem 1. Basically, section 6 looks very much like section 5 from Baydin et al. 2018. Even the wording is mostly the same. Theorem 5.1 in Baydin et al. 2018 is based on their update rule in Eq 6 in the form of alpha_t = alpha_{t-1} - beta nabla^T nabla, where alpha does not appear in the second term. However, in this paper, the update rule on line 7 in Algorithm 1 is M_t = M_{t-1} + rho * eps *(.) M_{t-1}, where M_t appears in the second term. Hence, the first bound in Theorem 1 in this paper cannot simply be the same as in Baydin et al. 2018.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJxFSI0cKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an interesting optimization algorithm called first-order preconditioning (FOP). \nThe basic idea of FOP is updating the preconditioned matrix by its gradient, which avoid calculating or approximating the Hessian directly. To make the algorithms more practical, the authors also conduct the low-rank FOP and the momentum-type version. The empirical studies on CIFAR-10 and ImageNet validate the effectives of the proposed algorithms.\n\nMajor comments:\n\n1. Section 2.1 says “we follow the example of Almeida et al. (1998) and assume that J does not dramatically”. However, the goal of FOP is to encourage J reduce faster. Is there any conflict?\n\n2. In low-rank FOP, the initial preconditioner P contains the term I_m which does not exist in standard FOP (section 2.1). How does this term affect the update procedure? Can you provide some details?\n\n3. Theorem 2 provide a linear convergence of FOP under convex, Lipschitz and PL condition. The proof relaxes the preconditioner P into its minimum and maximum eigenvalues. Since P changes over the course of training, it is difficult to check weather the result of Theorem 2 is stronger than gradient descent method.\n\n4. Why the experimental results not include the other second order optimization algorithms such as K-FAC and KFC?\n\nMinor comment:\n\nThe notations M in (1) (2) and (5) are ambiguous. It is prefer to use another letter to present the preconditioner in (1).\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "BJlu-ffY5H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a first-order preconditioning (FOP) method to generalize previous work on hypergradient descent to learn a preconditioning matrix that only makes use of first-order information.\n\nPros:\nThis paper extends the idea of hypergradient descent in [Almeida et al., 1998; Maclaurin et al., 2015; Baydin et al., 2017] with a preconditioning method. A low-rank FOP is further proposed to lighten the computation burden for the preconditioning matrix. \n\nCons:\n1-\tThe novelty and contribution is not clear.\n2-\tThe ideas of approximating the preconditioning matrix or factorized approximate inverse have been well studied in the literature, which are not sufficiently cited in the paper, such as Adagrad (Duchi et al. 2011), review in Bottou et al. 2016, etc. \n3-\tDerivation of Eq.(4) seems to be missing. \n4-\tTypo errors such as “is can” in page 5. \n5-\tA mistaken derivation in A.1 Eq.(20). “k” should be “k+1”.\n\nTherefore, I tend to give this paper a Weak Reject score. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper has been assessed by three reviewers who scored it as 3/3/3, and they did not increase their scores after the rebuttal. The main criticism lies in novelty of the paper, lack of justification for MM^T formulation, speed compared to gradient descent (i.e. theoretical analysis plus timing). Other concerns point to overlaps with Baydin et al. 2015 and the question about the validity of Theorem 1. On balance, this paper requires further work and it cannot be accepted to ICLR2020.
Decision: Reject