# Discounted Adaptive Online Learning: Towards Better Regularization

arXiv: https://arxiv.org/abs/2402.02720 · HTML: https://mlsanity.com/paper/2402.02720/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 62 references that are in the map.
- First posted on arXiv 5 Feb 2024.

## Builds on (most cited first, 30 of 39)

- [Gradient Episodic Memory for Continual Learning](https://mlsanity.com/paper/1706.08840/) (2017)
- [Efficient Lifelong Learning with A-GEM](https://mlsanity.com/paper/1812.00420/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [The Dormant Neuron Phenomenon in Deep Reinforcement Learning](https://mlsanity.com/paper/2302.12902/) (2023)
- [Understanding plasticity in neural networks](https://mlsanity.com/paper/2303.01486/) (2023)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Conformal Inference for Online Prediction with Arbitrary Distribution Shifts](https://mlsanity.com/paper/2208.08401/) (2022)
- [Black-Box Reductions for Parameter-free Online Learning in Banach Spaces](https://mlsanity.com/paper/1802.06293/) (2018)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [A Definition of Continual Reinforcement Learning](https://mlsanity.com/paper/2307.11046/) (2023)
- [Dynamic Regret of Convex and Smooth Functions](https://mlsanity.com/paper/2007.03479/) (2020)
- [Scale-Free Online Learning](https://mlsanity.com/paper/1601.01974/) (2016)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Improved Online Conformal Prediction via Strongly Adaptive Online Learning](https://mlsanity.com/paper/2302.07869/) (2023)
- [Solving Imperfect-Information Games via Discounted Regret Minimization](https://mlsanity.com/paper/1809.04040/) (2018)
- [Practical Adversarial Multivalid Conformal Prediction](https://mlsanity.com/paper/2206.01067/) (2022)
- [Lipschitz and Comparator-Norm Adaptivity in Online Learning](https://mlsanity.com/paper/2002.12242/) (2020)
- [RDumb: A simple approach that questions our progress in continual test-time adaptation](https://mlsanity.com/paper/2306.05401/) (2023)
- [Impossible Tuning Made Possible: A New Expert Algorithm and Its Applications](https://mlsanity.com/paper/2102.01046/) (2021)
- [Improved Strongly Adaptive Online Learning using Coin Betting](https://mlsanity.com/paper/1610.04578/) (2016)
- [Unconstrained Online Linear Learning in Hilbert Spaces: Minimax Algorithms and Normal Approximations](https://mlsanity.com/paper/1403.0628/) (2014)
- [Parameter-free Mirror Descent](https://mlsanity.com/paper/2203.00444/) (2022)
- [Optimal Stochastic Non-smooth Non-convex Optimization through Online-to-Non-convex Conversion](https://mlsanity.com/paper/2302.03775/) (2023)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Parameter-free Stochastic Optimization of Variationally Coherent Functions](https://mlsanity.com/paper/2102.00236/) (2021)

## Built on by (most cited first, 12 of 12)

- [Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learning](https://mlsanity.com/paper/2405.16642/) (2024)
- [On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning](https://mlsanity.com/paper/2505.22899/) (2025)
- [Advancing Investment Frontiers: Industry-grade Deep Reinforcement Learning for Portfolio Optimization](https://mlsanity.com/paper/2403.07916/) (2024)
- [Model-free Online Learning for the Kalman Filter: Forgetting Factor and Logarithmic Regret](https://mlsanity.com/paper/2505.08982/) (2025)
- [Dynamic Regret via Discounted-to-Dynamic Reduction with Applications to Curved Losses and Adam Optimizer](https://mlsanity.com/paper/2602.08372/) (2026)
- [The Benefit of Being Bayesian in Online Conformal Prediction](https://mlsanity.com/paper/2410.02561/) (2024)
- [Plasticine: Accelerating Research in Plasticity-Motivated Deep Reinforcement Learning](https://mlsanity.com/paper/2504.17490/) (2025)
- [Discounted Online Convex Optimization: Uniform Regret Across a Continuous Interval](https://mlsanity.com/paper/2505.19491/) (2025)
- [Elements of Conformal Prediction](https://mlsanity.com/paper/2603.23923/) (2026)
- [CONTINA: Confidence Interval for Traffic Demand Prediction with Coverage Guarantee](https://mlsanity.com/paper/2504.13961/) (2025)
- [Feature Fitted Online Conformal Prediction for Deep Time Series Forecasting Model](https://mlsanity.com/paper/2505.08158/) (2025)
- [Parameter-Free and Group Conditional Online Conformal Prediction](https://mlsanity.com/paper/2606.00419/) (2026)

## Abstract (arXiv)

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`es, 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.