Temporal variability in implicit online learning
Files
Date
2020-12-06
DOI
Authors
Campolongo, Nicolò
Orabona, Francesco
Version
OA Version
Published version
Citation
Nicolò Campolongo, Francesco Orabona. 2020. "Temporal Variability in Implicit Online Learning." Neural Information Processing Systems
Abstract
In the setting of online learning, Implicit algorithms turn out to be highly suc-cessful from a practical standpoint. However, the tightest regret analyses onlyshow marginal improvements over Online Mirror Descent. In this work, we shedlight on this behavior carrying out a careful regret analysis. We prove a novelstatic regret bound that depends on the temporal variability of the sequence ofloss functions, a quantity which is often encountered when considering dynamiccompetitors. We show, for example, that the regret can be constant if the tempo-ral variability is constant and the learning rate is tuned appropriately, without theneed of smooth losses. Moreover, we present an adaptive algorithm that achievesthis regret bound without prior knowledge of the temporal variability and prove amatching lower bound. Finally, we validate our theoretical findings on classifica-tion and regression datasets.