  We describe a framework for deriving and analyzing online optimization
algorithms that incorporate adaptive, data-dependent regularization, also
termed preconditioning. Such algorithms have been proven useful in stochastic
optimization by reshaping the gradients according to the geometry of the data.
Our framework captures and unifies much of the existing literature on adaptive
online methods, including the AdaGrad and Online Newton Step algorithms as well
as their diagonal versions. As a result, we obtain new convergence proofs for
these algorithms that are substantially simpler than previous analyses. Our
framework also exposes the rationale for the different preconditioned updates
used in common stochastic optimization methods.
