The Interplay Between Stability and Regret in Online Learning

By Ankan Saha, Prateek Jain, Ambuj Tewari. 2012

16 citations recorded by the source corpus.

This paper considers the stability of online learning algorithms and its implications for learnability (bounded regret). We introduce a novel quantity called {\em forward regret} that intuitively measures how good an online learning algorithm is if it is allowed a one-step look-ahead into the future. We show that given stability, bounded forward regret is equivalent to bounded regret. We also show that the existence of an algorithm with bounded regret implies the existence of a stable algorithm with bounded regret and bounded forward regret. The equivalence results apply to general, possibly non-convex problems. To the best of our knowledge, our analysis provides the first general connection between stability and regret in the online setting that is not restricted to a particular class of algorithms. Our stability-regret connection provides a simple recipe for analyzing regret incurred by any online learning algorithm. Using our framework, we analyze several existing online learning algorithms as well as the "approximate" versions of algorithms like RDA that solve an optimization problem at each iteration. Our proofs are simpler than existing analysis for the respective algorithms, show a clear trade-off between stability and forward regret, and provide tighter regret bounds in some cases. Furthermore, using our recipe, we analyze "approximate" versions of several algorithms such as follow-the-regularized-leader (FTRL) that requires solving an optimization problem at each step.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Management Science and Operations Research

Citations in the corpus

Adaptive Gradient-Based Meta-Learning Methods (2019, methodology): “The proof slightly generalizes an argument in Saha et al. [48, Theorem 6].”
Reinforcement and Imitation Learning via Interactive No-Regret Learning (2014, methodology): “By understanding these methods as attempting to ensure both good performance and ro bust, stable learning across iterations [23, 27], they become a natural tool for understanding the dy namics of interleaving learning and execution when our primary concern is generalization perfo rmance.”
Online Learning via the Differential Privacy Lens (2017, unknown): “A few papers that attempt to connect stability and online learning are interestingly all unpublished and only available as preprints [32, 35, 36].”