Discounted Adaptive Online Learning: Towards Better Regularization

Understand

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.