Matrix-Free Preconditioning in Online Learning
  We provide an online convex optimization algorithm with regret that
interpolates between the regret of an algorithm using an optimal
preconditioning matrix and one using a diagonal preconditioning matrix. Our
regret bound is never worse than that obtained by diagonal preconditioning, and
in certain setting even surpasses that of algorithms with full-matrix
preconditioning. Importantly, our algorithm runs in the same time and space
complexity as online gradient descent. Along the way we incorporate new
techniques that mildly streamline and improve logarithmic factors in prior
regret analyses. We conclude by benchmarking our algorithm on synthetic data
and deep learning tasks.
