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