Discounted Adaptive Online Learning: Towards Better Regularization
This work addresses the challenge of gracefully forgetting history in nonstationary online learning, offering incremental improvements in regularization and analysis for practitioners in machine learning.
The paper tackles the problem of online learning in adversarial nonstationary environments by proposing an adaptive FTRL-based algorithm that improves upon non-adaptive baselines like gradient descent with constant learning rates, showing better regularization in lifelong learning and instance-dependent guarantees in online conformal prediction.
We study online learning in adversarial nonstationary environments. Since the future can be 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 discounted regret in online convex optimization, and propose an adaptive (i.e., instance optimal), FTRL-based algorithm that improves the widespread non-adaptive baseline -- gradient descent with a constant learning rate. From a practical perspective, this refines the classical idea of regularization in lifelong learning: we show that designing good regularizers can be guided by the principled theory of adaptive online optimization. Complementing this result, we also consider the (Gibbs and Candès, 2021)-style online conformal prediction problem, where the goal is to sequentially predict the uncertainty sets of a black-box machine learning model. We show that the FTRL nature of our algorithm can simplify the conventional gradient-descent-based analysis, leading to instance-dependent performance guarantees.