Strongly adaptive online learning improves discounted regret rates
Strongly Adaptive Online Learning Achieves Uniform Discounted Regret
Machine Learning
Summary
When machines learn from data that changes over time, it's important to care more about recent mistakes than older ones. The authors show how a technique called strongly adaptive learning helps machines keep this focus and perform better across different ways of weighing recent mistakes. They found simpler ways to get good results for different types of learning problems, including those with special mathematical properties. This work improves on earlier methods that were more limited.
What this means in practice
- •For financial algorithm designers: Create trading algorithms that adapt smoothly to market changes by effectively weighting recent losses over older ones.
- •For online advertising teams: Build ad placement strategies that adjust quickly to shifting user behavior with reliable performance guarantees across various discounting of past data.
Authors
Sifan Yang, Wenhao Yang, Lijun Zhang
Abstract
Discounted regret measures the performance of an online learner by assigning exponentially decaying weights to past losses, reflecting the greater importance of recent losses in non-stationary online learning. While previous work obtains uniform discounted regret bounds over a continuous range of discount factors using a specialized meta-algorithm, its results are limited to convex functions. In this paper, we demonstrate that strongly adaptive regret bounds can directly imply uniform discounted regret guarantees for convex, strongly convex, and exp-concave loss functions. Our key observation is that discounted regret against a fixed comparator admits an exact decomposition into a convex combination of interval regrets. For convex functions, this reduction yields an $O(\sqrt{\log T/(1-λ)})$ discounted regret bound for all discount factors $λ\in(0,1)$, matching the previous rate over a broader range of discount factors. For strongly convex and exp-concave functions, we provide regret bounds of $O\left(\log T\left(1+\log\frac{1}{1-λ}\right)\right)$.