Discounted Adaptive Online Prediction
Zhiyu Zhang David Bombara Heng Yang
Online learning is not always about memorizing everything. Since the future
can be statistically very different from the past, a critical challenge is to
gracefully forget the history while new data comes in. To formalize this
intuition, we revisit the classical notion of discounted regret using recently
developed techniques in adaptive online learning. Our main result is a new
algorithm that adapts to the complexity of both the loss sequence and the
comparator, improving the widespread non-adaptive algorithm - gradient descent
with a constant learning rate. In particular, our theoretical guarantee does
not require any structural assumption beyond convexity, and the algorithm is
provably robust to suboptimal hyperparameter tuning. We further demonstrate
such benefits through online conformal prediction, a downstream online learning
task with set-membership decisions.