Less Regret via Online Conditioning

In the past few years, online algorithms have emerged as state-of-the-art techniques for solving large-scale machine learning problems [2, 13, 16]. In addition to their simplicity and generality, online algorithms are natural choices for problems where new data is constantly arriving and rapid adaptation is imporant. Compared to the study of convex optimization in the batch (offline) setting, the study of online convex optimization is relatively new. In light of this, it is not surprising that performance-improving techniques that are well known and widely used in the batch setting do not yet have online analogues. In particular, convergence rates in the batch setting can often be dramatically improved through the use of preconditioning. Yet, the online convex optimization literature provides no comparable method for improving regret(the online analogue of convergence rates).