---
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_1999; @maclaurin_2015; @hypergrad_2018] 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.'
author:
- |
    Ted Moskovitz[^1], Rui Wang, Janice Lan, Sanyam Kapoor,\
    **Thomas Miconi, Jason Yosinski, Aditya Rawal**\
    Uber AI\
    `{tmoskovitz, ruiwang, janlan, sanyam,`\
    `tmiconi, yosinski, aditya.rawal}@uber.com`
bibliography:
- 'iclr2020\_conference.bib'
title: |
    First-Order Preconditioning via\
    Hypergradient Descent
---

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_2016]. 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 to 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 models such as Adam [@adam_2014] and RMSProp [@rmsprop_2012] provide some degree of higher-order approximation to re-scale updates based on per-parameter behavior. Newton-based methods make use of the curvature of the loss surface to both re-scale and rotate the gradient in order to improve convergence. Natural gradient methods [@Amari_nat_grad_og] do the same in order to 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 a *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-dimensional problems, and while a number of approximate methods exist for both (e.g., [@byrd_nocedal_zhu_1996; @KFAC_2015; @KFC_2016]), 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 to 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, or may even change over the course of training.

In this paper, we attempt to address these issues through a method we term *first-order preconditioning* (FOP). FOP doesn’t attempt to compute a specific preconditioner, such as the inverse Hessian, but rather uses first-order hypergradient descent [@maclaurin_2015] to *learn* an adaptable transformation online directly from the task objective function. Our method adds minimal computational and memory cost to standard deep network training settings and results in improved convergence speed and generalization compared to standard approaches. FOP can flexibly be applied to any gradient-based optimization problem, and we show that when used in conjunction with standard optimizers, it improves their performance.

First Order Preconditioning
===========================

The Basic Approach
------------------

Consider a parameter vector $\theta$ and a loss function $J$. A traditional gradient update with a preconditioning matrix $M$ can be written as

$$\theta^{(t+1)} = \theta^{(t)} - \epsilon M^{(t)}\nabla_{\theta^{(t)}}J^{(t)}.$$

**Require:** model parameters $\theta$, objective function $J$, FOP matrix $M$, learning rate $\epsilon$, hypergradient learning rate $\rho$ **for** t = 1,2,... **do** Draw data $x^{(t)}, y^{(t)} \sim \mathcal{D}$ Perform forward pass: $\hat{y}^{(t)} = f_{\theta^{(t)}}(x^{(t)})$ Compute loss $J(y^{(t)}, \hat{y}^{(t)})$ Update inference parameters $\theta$: $\theta^{(t+1)} \gets \theta^{(t)} - \epsilon M^{(t)}M^{(t)\top} 
\nabla_{\theta^{(t)}} J$ Update preconditioning matrices: $$M^{(t+1)} \gets M^{(t)} + \rho \epsilon \left( 
\nabla_{\theta^{(t)}}J \left[ \nabla_{\theta^{(t-1)}}J\right]^{\top}
+ 
\nabla_{\theta^{(t-1)}}J \left[ \nabla_{\theta^{(t)}}J\right]^{\top}
\right)
M^{(t)}$$

Cache $\nabla_{\theta^{(t)}} J$

Our goal is to learn $M$. However, while we place no other constraints on our preconditioner, in order to ensure that it is positive definite, and therefore does not reverse the direction of the gradient, we replace Equation 1 with the following: $$\theta^{(t+1)} = \theta^{(t)} - \epsilon M^{(t)}M^{(t)\top} \nabla_{\theta^{(t)}}J^{(t)}.$$ Under reasonable assumptions, gradient descent is guaranteed to converge with the use of even a random symmetric, positive-definite preconditioner, as we show in Supplementary Section \[sect:pregd\]. Because $\theta^{(t)}$ is a function of $M^{(t-1)}$, we can then backpropagate from the loss at iteration $t$ to the previous iteration’s preconditioner via a simple application of the chain rule: $$\frac{\partial J^{(t)}}{\partial M^{(t-1)}} = \frac{\partial J^{(t)}}{\partial \theta^{(t)}} \frac{\partial \theta^{(t)}}{\partial M^{(t-1)}}.$$ The gradient with respect to the preconditioner is then simply $$\nabla_{M^{(t-1)}} J^{(t)} = -\epsilon \left( \nabla_{\theta^{(t)}} J^{(t)} \left[ \nabla_{\theta^{(t-1)}} J^{(t-1)}\right]^{\top} + 
\nabla_{\theta^{(t-1)}} J^{(t-1)} \left[ \nabla_{\theta^{(t)}} J^{(t)}\right]^{\top}
\right)M^{(t)}.$$

Note that ideally, we would compute $\nabla_{M^{(t)}} J^{(t+1)}$ to update $M^{(t)}$, but as we don’t have access to $J^{(t+1)}$ yet, we follow the example of @Almeida_1999 and assume that $J$ does not dramatically change across a single iteration. The basic approach is summarized in Algorithm \[alg:fop\]. 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 to produce an update for $M$. For example, we describe the procedure for using FOP with momentum [@momentum_1964] in Section \[sect:momentum-deriv\]. For multi-layer networks, in order to make the simplest modification to normal backpropagation, we learn a separate $M$ for each layer, not a global curvature matrix.

To get an intuition for the behavior of FOP compared to standard algorithms, we observed its trajectories on a set of low-dimensional optimization problems (Figure \[fig:toy\]). Interestingly, while FOP converged in fewer iterations than SGD and Adam [@adam_2014], it took more jagged paths along the objective function surface, suggesting that while it takes more aggressive steps, it is perhaps also able to change direction more rapidly.

Low-Rank FOP {#sect:low-rank}
------------

If $\theta$ is an $m \times n$ matrix, and we only apply the preconditioning matrix over input dimensions (and share it across output dimensions), then a full-rank $M$ would necessarily be $m \times m$. When $m$ is large, preconditioning the gradient becomes expensive. Instead, we can apply a rank-$k$ $M$, with $M \in \mathbb{R}^{m \times k}$ and $k < 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 a low rank $M$, so that the algorithm begins as straightforward gradient descent and learns to depart from vanilla SGD over time. Thus, we set the preconditioner $P$ to be $$\label{eq:lo-rank}
    P = I_{m} + MM^{\top},$$ where $I_{m}$ is the $m \times m$ identity matrix and $M_{ij} \sim \mathcal{N}(0, \sigma^{2})$, where $\sigma^{2}$ is small so that $P$ starts out close to the identity matrix. We tested the effect of rank on a simple fully-connected network trained on the MNIST dataset [@lecun_mnist]. The results, shown in Figure \[fig:rank\], indicate that FOP is able to 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 comparison of FOP to common optimizers on toy problems. The red dot indicates the initial position on the loss surface. The purpose of these visualizations is not to establish the superiority of one optimizer over another, but rather to gain an intuition for their qualitative behavior. (Left) Gradient descent on the Booth function. FOP converges in 543 iterations, while SGD takes 832 steps and 6,221 for Adam. (Right) Gradient descent on Himmelbau’s function. Adam, converging in 5398 iterations, finds a different global minimum from FOP and SGD, which converge in 289 and 386 steps, respectively. In both cases, we can see that FOP moves more aggressively across the 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. []{data-label="fig:toy"}](figs/toy_new1.pdf){width="95.00000%"}

Spatial Preconditioning for Convolutional Networks {#sect:fop-cnn}
--------------------------------------------------

In order to further reduce the computational cost of FOP in convolutional networks (CNNs), we implemented layer-wise *spatial* preconditioners, sharing the matrices across both input and output channels (results shown in Section \[sec:experiments\]). More concretely, if a convolutional layer has spatial kernels with shape $k \times k$, we can learn a preconditioner that is $k^{2} \times k^{2}$. To implement this, when $\theta$ is a 4-tensor of kernels of shape $k \times k \times I \times  O$, where $I$ and $O$ are the input and output channels, respectively, we can reshape it to a matrix of size $k^{2} \times IO$, left-multiply it by the learned curvature matrix, and then reshape it back to its original dimensions. When $k$ is small, as is typically the case in deep CNNs, this preconditioner is small as well, resulting in both computational and memory efficiency.

FOP for Momentum {#sect:momentum-deriv}
----------------

FOP can be implemented alongside any standard optimizer, such as gradient descent with momentum [@momentum_1964]. Given a parameter vector $\theta$ and a loss function $J$, a basic momentum update with FOP matrix $M$ is typically expressed as two steps: $$\label{eq:mom1}
    v^{(t+1)} = \alpha v^{(t)} + M^{(t)}M^{(t)\top} \nabla_{\theta^{(t)}}J$$ $$\label{eq:mom2}
    \theta^{(t+1)} = \theta^{(t)} - \epsilon v^{(t+1)},$$ where $v$ is the velocity term and $\alpha$ is the momentum parameter. Combining Equations \[eq:mom1\] and \[eq:mom2\] allows us to write the full update as $$\theta^{(t+1)} = \theta^{(t)} - \epsilon \alpha v^{(t)} - \epsilon M^{(t)}M^{(t)\top} \nabla_{\theta^{(t)}}J.$$ If, as in @maclaurin_2015, we were meta-learning $M$ or only updating $M$ after a certain number of 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 $\nabla_{M^{(t)}}J$. Therefore, the update is the same as for standard gradient descent. The experiments in Section \[sec:experiments\] were performed using this modification of momentum.

![FOP is able to improve training even with very low ranks. We plot the test accuracy over the course of training for a 4-layer fully-connected network with 100 units per layer trained on MNIST for different FOP matrix ranks, averaged over 5 runs each. The gradient was preconditioned by $I_{m}  + MM^{\top}$, where $M$ was rank $k$. 784 is full rank for the first layer, and 100 is 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 to vanilla SGD with momentum 0.9. For $k < 4$, final accuracy is 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 $<$ 1e-4. []{data-label="fig:rank"}](figs/rank_const_beta.pdf){width="80.00000%"}

Related Work {#sect:rel_work}
============

@Almeida_1999 introduced the idea of using gradients from the objective function to learn optimization parameters such as the learning rate or a curvature matrix. However, their preconditioning matrix was strictly diagonal, amounting to an approximate Newton algorithm [@martens_2016], and they only tested their framework on simple optimization problems with either gradient descent or SGD. They also noted that a truly online stochastic update rule for the curvature matrix would involve a product of the gradients from the current iteration and the following, but to avoid the computational cost of producing an estimate for the next step’s gradient, they relied on the smoothness of the objective function and used the product of the current gradient and the previous gradient. FOP uses the same compromise. More recently, @maclaurin_2015 applied this approach in a neural network context, terming the process of backpropagating through iterations *hypergradient descent*. Their method backpropagates through multiple iterations of the training process of a relatively shallow network to meta-learn a learning rate. However, this method can incur significant memory and computational cost for large models and long training times. @hypergrad_2018 instead proposed an online framework directly inherited from @Almeida_1999 that used hypergradient-based optimization in which the learning rate is updated after each iteration. 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 a non-diagonal, layer-specific preconditioning matrix for the gradient.

![image](figs/cifar_curves.pdf){width="\textwidth"}

![image](figs/imagenet_curves.pdf){width="\textwidth"} \[fig:results\]

It’s also important to discuss the relationship of FOP to other, non-hypergradient preconditioning methods for deep networks. These mostly can be sorted into one of two categories, quasi-Newton algorithms and natural gradient approaches. Quasi-Newton methods seek to learn an approximation of the inverse Hessian. L-BFGS, for example, does this through tracking the differences between gradients across iterations [@byrd_nocedal_zhu_1996]. This is significantly different from FOP, although the outer product of gradients used in the update for FOP is can also be an approximation of the Hessian. Natural gradient methods, such as K-FAC [@KFAC_2015] and KFC [@KFC_2016], which approximate the inverse Fisher information matrix, bear a much stronger resemblance to FOP. However, 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 preconditioner in these methods is completely different, as they do not backpropagate across iterations.

![Adding FOP improves the hyperparameter robustness of standard optimizers. (a) The final test accuracy of a 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 . FOP appears to be most useful for higher values of the learning rate and momentum parameters. The FOP matrices were trained with Adam with a learning rate of $5\times 10^{-4}$. (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 setting as the models in (a).[]{data-label="fig:heatmaps"}](figs/heatmaps.pdf){width="98.00000%"}

Experiments {#sec:experiments}
===========

We measured the performance of FOP on several visual classification tasks. In order to measure the importance of the rotation induced by the preconditioning matrices in addition to the scaling, we also implemented hypgradient descent (HD) methods to learn a scalar layer-wise learning rate (S-HD) and a per-parameter (PP-HD) learning rate. The former is the same method implemented by @hypergrad_2018, and the latter is equivalent to a strictly diagonal curvature matrix. We also implement a method we call normalized FOP (FOP-norm), in which we rescale the preconditioning matrix to avoid any effect on the learning rate and rely solely on standard learning rate settings. Further details on this method can be found in Supplementary Section \[sect:norm-fop\]. All experiments were run using the TensorFlow library [@tensorflow2015-whitepaper][^2].

CIFAR-10
--------

For CIFAR-10 [@CIFAR10], an image dataset consisting of 50,000 training and 10,000 test $32 \times 32$ RGB images divided into 10 object classes, we implemented a 9-layer convolutional architecture inspired by @all_conv_2014. We trained each model for 150 epochs with a batch size of 128 and initial learning rate 0.05, decaying the learning rate by a factor of 10 after 80 epochs. For S-HD, PP-HD, and FOP, we use Adam as the hypergradient optimizer with a learning rate of 1e-4. The results are plotted in Figure \[fig:results\]. FOP produces a significant speed-up in training and improves 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.

ImageNet
--------

The ImageNet dataset consists of 1,281,167 training and 50,000 validation $299 \times 299$ RGB images divided into 1,000 categories [@imagenet_cvpr09]. Here, we trained a ResNet-18 [@resnet2015] model for 60 epochs with a batch size of 256 and an initial learning rate of 0.1, decaying by a factor of 10 at the 25th and 50th epochs. A summary of our results is displayed in Figure \[fig:results\]. We can see that the improved convergence speed and test performance observed on CIFAR-10 is maintained on this deeper model and more difficult dataset.

Hyperparameter Robustness {#sect:robustness}
-------------------------

In addition to measuring peak performance, we also tested the effect FOP had on the robustness of standard optimizers to hyperparameter selection. @hypergrad_2018 demonstrated the ability of scalar hypergradients to mitigate the effect of the initial learning rate on performance. We therefore tested whether this benefit was preserved by FOP, as well as whether it extended to other hyperparameter choices, such as the momentum coefficient. Our results, summarized in Figure \[fig:heatmaps\], support this idea, showing that FOP can improve performance on a wide array of optimizer settings. For momentum (Fig. \[fig:heatmaps\]a), we see that the performance gap is greater for higher learning rates and momentum 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 on the adaptive moment estimation performed by Adam. We leave further investigation into this interaction for future work.

![Understanding the learned preconditioning matrices ($MM^{\top}$) 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 in the plots. We can see that the convergence of the values of the matrix, corresponding to a stronger decorrelation structure and a reduced $L_{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 a 9-layer network trained on CIFAR-10 (the top two layers were $1\times 1$ kernels). We can see that 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. []{data-label="fig:what_learning"}](figs/pcm_viz_eig.pdf){width="95.00000%"}

What is FOP learning? {#sect:what_is_it_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 \[fig:what\_learning\]a) shows that they develop a decorrelating, or *whitening*, structure: each of the 9 positions in the 3x3 convolutional filter sends a strong positive weight to itself, and negative weights to its immediate neighbors, without wrapping over the corners of the filter. This is interesting, as images are known to have a high degree of spatial autocorrelation [@barlow_1961; @barlow_1989]. As a mechanism for reducing redundant computation, whitening visual inputs is known to be beneficial for both retinal processing in the brain [@attick_whitening_1992; @hateren_1992] and in artificial networks [@pascanu_naturalnets_2015; @whitened_batchnorm_2018]. However, it is more unusual to consider whitening of the learning signal, as observed in FOP, rather than the forward activation.

This learned pattern is accompanied by a shift in the norm of the curvature matrix, as the diagonal elements, initialized to ones, shrink in value, and the off-diagonal elements increase. This shift in distribution is visualized in Figure \[fig:what\_learning\]b, and grows stronger deeper in the network. It is possible that this indicates that standard gradient descent is more ill-conditioned in higher layers, or perhaps equivalently, that a greater degree of decorrelation is helpful for kernels disentangling higher-level representations.

We can also examine the eigenvalue spectra for the learned matrices across layers (Figure \[fig:what\_learning\]c). We can see that the basic requirement that in general a preconditioning matrix must be positive definite, so as not to reverse the direction of the gradient, is met. However, we also note that 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-Newton and natural gradient methods seek to compute 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 \[fig:what\_learning\]b. A uniform eigenspectrum is seen as an attribute of an effective preconditioning matrix [@precond_sgd_2015], as it indicates an even convergence rate in parameter space.

Convergence {#sect:convergence}
===========

Our experiments indicate that the curvature matrices learned by FOP converge to a relatively fixed norm roughly two-thirds of the way through training (Figure \[fig:what\_learning\]b). 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 @hypergrad_2018.

Consider a modification of FOP in which the symmetric, positive-definite preconditioning matrix $P^{(t)}$ is rescaled at each iteration to have a certain norm $\gamma^{(t)}$, such that $\gamma^{(t)} \approx ||P^{(t)}||_{2}$ when $t$ is small and $\gamma^{(t)} \approx p^{(\infty)}$ when $t$ is large, where $p^{(\infty)}$ is some chosen constant. Specifically, as in @hypergrad_2018, we set $\gamma^{(t)} = \delta(t)||P^{(t)}||_{2} + (1 - \delta(t))p^{(\infty)}$, where $\delta(t)$ is some function that decays over time and starts training at $1$ (e.g., $1/t^{2}$).

This formulation allows us to extend the convergence proof of @hypergrad_2018 to FOP, under the same assumptions about the objective function $J$:

Suppose that $J$ is convex and $L$-Lipschitz smooth with $\|\nabla_{\theta}J\| < K$ for some fixed $K$ and all model parameters $\theta$. Then $\theta_{t} \rightarrow \theta^{\ast}$ if $p^{(\infty)} < 1/L$ and $t\delta(t) \rightarrow 0$ as $t \rightarrow \infty$, where the $\theta_{t}$ are generated by (non-stochastic) gradient descent.

*Proof.* We can write $$\|P^{(t)}\| \leq \|P^{(0)}\| + 
\rho \sum_{i=0}^{t-1} \left| [\nabla_{\theta_{i+1}}J]^{\top} \nabla_{\theta_{i}}J \right| 
\leq 
\|P^{(0)}\| + 
\rho \sum_{i=0}^{t-1} \| \nabla_{\theta_{i+1}}J \| \|\nabla_{\theta_{i}}J \| 
\leq 
\|P^{(0)}\| +  t\rho K^{2},$$ where $\rho$ is the hypergradient learning rate. Our assumptions about the limiting behavior of $t\delta(t)$ then imply that $\delta(t)\|P^{(t)}\| \rightarrow 0$ and so $\gamma^{(t)} \rightarrow p^{(\infty)}$ as $t \rightarrow \infty$. For sufficiently large $t$, we therefore have $\gamma^{(t)} \in (\frac{1}{L+1}, \frac{1}{L})$. Note also that as $P$ is symmetric and positive definite, it will not prevent the convergence of gradient descent (Supplementary Section \[sect:pregd\]). Moreover, preliminary investigation showed that the angle of rotation induced by the FOP matrices is significantly below $90^\circ$ (Supplementary Figure \[fig:angles\]). Previous work by [@fa-2016] shows that such a rotation does not impede the convergence of gradient descent. Because standard SGD converges under these conditions [@karimi_convergence_2016], FOP must as well.

Conclusion
==========

In this paper, we introduced a novel optimization technique, FOP, that learns a preconditioning matrix online to improve convergence and generalization in large-scale machine learning models. We tested FOP on several problems and architectures, examined the nature of the learned transformations, and provided a preliminary analysis of FOP’s convergence properties (Supplementary Section \[sect:convergence\]). There are a number of opportunities for future work, including learning transformations for other optimization parameters (e.g., the momentum parameter in case of the the momentum optimizer), expanding and generalizing our theoretical analysis, and testing FOP on a wider variety of models and data sets.

### Acknowledgements {#acknowledgements .unnumbered}

We would like to thank Kenneth Stanley, Jeff Clune, Rosanne Liu, and members of the Horizons and Deep Collective research groups at Uber AI for useful feedback and discussions.

Supplemental Information
========================

Normalized FOP {#sect:norm-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: $$\theta^{(t+1)} = \theta^{(t)} - \epsilon \sqrt{n} \frac{M^{(t)}M^{(t)\top}}{\|M^{(t)}M^{(t)\top}\|} \nabla_{\theta^{(t)}}J,$$ where $n$ is the first dimension of $M$. This update has the effect of normalizing the preconditioner $M^{(t)}M^{(t)\top}$, then re-scaling the update by $\sqrt{n}$ to match the norm of gradient descent, as $\|I_{n}\|=\sqrt{n}$, where $I_{n}$ is the identity matrix of size $n$.

Convergence of Preconditioned Gradient Descent {#sect:pregd}
----------------------------------------------

We demonstrate that given a random, symmetric positive definite preconditioning matrix $P$, gradient descent will still converge at a linear rate, modeling our proof after that of @karimi_convergence_2016.

Consider a convex, $L$-Lipschitz objective function $f(\theta)$ with global minimum $f^{\ast}$ which obeys the Polyak-Łojasiewicz (PL) Inequality [@polyak_1963], $$\frac{1}{2}\|\nabla_{\theta} f\|^{2} \geq \mu (f(\theta) - f^{\ast}), \ \text{ } \ \forall \theta.$$ Then applying the gradient update method given by $$\theta_{k+1} = \theta_{k} - \rho P \nabla_{\theta_{k}} f,$$ where $P$ is a real, symmetric positive semi-definite matrix and $\rho = \frac{2\lambda_{\min} - \lambda_{\max}^{2}}{L}$ is the step size, where $\lambda_{\min}$ and $\lambda_{\max}$ are the minimum and maximum eigenvalues of $P$, respectively, results in a global linear convergence rate given by $$f(\theta_{k}) - f^{\ast} \leq (1 - \mu \rho)^{k} (f(\theta_{0}) - f^{\ast}).$$

*Proof.* First, assume a step-size of $1/L$. Given that $f$ is $L$-Lipschitz continuous, we can write $$f(\theta_{k+1}) - f(\theta_{k}) \leq \langle  \nabla f,  \theta_{k+1} - \theta_{k}\rangle + \frac{L}{2} \| \theta_{k+1} - \theta_{k} \|^{2}.$$ where $\nabla f$ denotes $\nabla_{\theta_{k}} f$. Plugging in the gradient update equation gives $$f(\theta_{k+1}) - f(\theta_{k}) \leq \langle  \nabla f, -\frac{1}{L} P \nabla f \rangle + \frac{L}{2} \|  -\frac{1}{L} P \nabla f \|^{2}$$ $$\label{eqn:prebasis}
 = -\frac{1}{L}  (\nabla f)^{\top} P \nabla f + \frac{1}{2L}  \| P \nabla f \|^{2}.$$ Let $Q^{\top}\Lambda Q = P$ be the eigendecomposition of $P$ , such that the columns of $Q$ are the orthonormal eigenvectors and $\Lambda$ 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 can then rewrite the first term of Equation 13 as $$-\frac{1}{L} (\nabla f)^{\top} Q^{\top}\Lambda Q \nabla f.$$ We now change our basis, letting $G = Q\nabla f$ and define $\lambda_{\min} = \min_{i} \{\lambda_{i}\}$ and $\lambda_{\max} = \max_{i} \{\lambda_{i}\}$, where $\lambda_{i}$ are the eigenvalues. Then we have $$-\frac{1}{L} (\nabla f)^{\top} Q^{\top}\Lambda Q \nabla f =  -\frac{1}{L}  G^{\top} \Lambda G \leq  -\frac{1}{L}  \lambda_{\min} G^{\top} G = -\frac{1}{L} \lambda_{\min} \|G\|^{2}.$$ Examining the second term of Equation 13, we have $$\frac{1}{2L}  \| P \nabla f \|^{2} = \frac{1}{2L} (P\nabla f)^{\top} P\nabla f$$ $$= \frac{1}{2L} (\nabla f)^{\top} Q^{\top} \Lambda Q Q^{\top} \Lambda Q \nabla f$$ $$= \frac{1}{2L} G^{\top} \Lambda^{2} G$$ $$\leq \frac{1}{2L} \lambda_{\max}^{2} G^{\top}G$$ $$= \frac{1}{2L} \lambda_{\max}^{2} \| G\|^{2}.$$ Combining the results of Equations 14 and 15 gives $$f(\theta_{k+1}) - f(\theta_{k}) \leq   -\frac{1}{L} \lambda_{\min} \|G\|^{2} +  \frac{1}{2L} \lambda_{\max}^{2} \| G\|^{2}$$ $$= -\frac{1}{L}\left( \lambda_{\min}- \frac{\lambda_{\max}^{2}}{2} \right) \| G\|^{2}.$$ We can then revert to the original basis: $$\|G\|^{2} = (Q \nabla f)^{\top} Q \nabla f = 
(\nabla f)^{\top} Q^{\top} Q \nabla f = (\nabla f)^{\top}\nabla f
= \|\nabla f\|^{2},$$ giving us $$f(\theta_{k+1}) - f(\theta_{k}) \leq  -\frac{1}{L}\left( \lambda_{\min}- \frac{\lambda_{\max}^{2}}{2} \right) \|\nabla f\|^{2}.$$ By the PL inequality we have that $ \| \nabla f\|^{2} \geq 2\mu ( f(\theta_{k}) - f^{\ast})$ for some $\mu > 0$. Plugging this in gives $$f(\theta_{k+1}) - f(\theta_{k}) \leq  -\frac{\mu}{L}\left(2\lambda_{\min} - \lambda_{\max}^{2} \right) ( f(\theta_{k}) - f^{\ast})$$ Then let $\rho =  \frac{1}{L}\left( 2\lambda_{\min} - \lambda_{\max}^{2} \right) $. We have $$f(\theta_{k+1}) - f(\theta_{k}) \leq - \mu \rho f(\theta_{k})  + \mu \rho f^{\ast}.$$ Rearranging and subtracting $f^{\ast}$ from both sides gives $$\label{eqn:conv1}
f(\theta_{k+1}) - f^{\ast} \leq (1 - \mu\rho) ( f(\theta_{k}) - f^{\ast}).$$ Applying Equation \[eqn:conv1\] recursively gives the desired convergence: $$f(\theta_{k+1}) - f^{\ast} \leq (1 - \mu\rho)^{k} ( f(\theta_{0}) - f^{\ast}).$$ Thus this preconditioned gradient descent converges with a step size $\frac{2\lambda_{\min} - \lambda_{\max}^{2}}{L}$. 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 occur.

![Angles in degrees between $\nabla J^{(t)}$ and $(I + M^{(t)}M^{(t)\top}) \nabla J^{(t)}$ for each layer of a 4 layer fully connected network on MNIST. Values are averaged over 5 runs and displayed every 200 iterations. Shaded areas represent the min and max values over all the runs, showing that the angle only varies slightly. Notice that the angle is usually slightly below $45^{\circ}$, indicating that the while FOP does induce a rotation, it is far from orthogonal to the vanilla learning signal.[]{data-label="fig:angles"}](figs/fc_angles_crop.pdf){width="80.00000%"}

[^1]: Work done while an intern at Uber. Ted can be reached at `ted@gatsby.ucl.ac.uk`.

[^2]: Code currently available at this link:\
    `https://drive.google.com/file/d/1vhB4fxDuxaYJcNP6ioEJQf4CLHxhy1ka/view?usp=sharing`.
