Adaptive and Self-Confident On-Line Learning Algorithms

By Peter Auer, Nicolò Cesa-Bianchi, Claudio Gentile. 2000

279 citations recorded by the source corpus.

Most of the performance bounds for on-line learning algorithms are proven assuming a constant learning rate. To optimize these bounds, the learning rate must be tuned based on quantities that are generally unknown, as they depend on the whole sequence of examples. In this paper we show that essentially the same optimized bounds can be obtained when the algorithms adaptively tune their learning rates as the examples in the sequence are progressively revealed. Our adaptive learning rates apply to a wide class of on-line algorithms, including p-norm algorithms for generalized linear regression and Weighted Majority for linear regression with absolute loss. We emphasize that our adaptive tunings are radically different from previous techniques, such as the so-called doubling trick. Whereas the doubling trick restarts the on-line algorithm several times using a constant learning rate for each run, our methods save information by changing the value of the learning rate very smoothly. In fact, for Weighted Majority over a finite set of experts our analysis provides a better leading constant than the doubling trick.

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

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

In Statistical Learning Theory

Citations in the corpus

Memory-Efficient Adaptive Optimization for Large-Scale Learning (2019, background): “1 Related work Adaptive learning rates in online and stochastic optimization date back at least to [4] and were popularized in [9, 14], the former of which introduced the well-known Adagrad algorithm.”
Riemannian Adaptive Optimization Methods (2018, unknown): “Lemma 8 ((Auer et al., 2002)) .”
Exploring compact reinforcement-learning representations with linear regression (2009, background): “Applications to restricted RL problems also exist [2], but with different types of bounds.”
Follow the leader if you can, hedge if you must (2013, background): “This also improves the best known result (Auer et al., 2002) by a factor of √ 2.”
Simultaneous Model Selection and Optimization through Parameter-free Stochastic Learning (2014, methodology): “On the other hand, using the tools to design self-tuning algorithms, e.g. [1, 13], it may be possible to design an ASGD-like algorithm, able to self-tune its step size in a data-dependent way.”
A Modern Introduction to Online Learning (2019, methodology): “So, I didn’t introduce the concept of Legendre functions at all, relying instead on (a minor modification of) OMD as described by Beck and Teboulle [2003]. The concept of local norm was introduced in Abernethy et al.”
Regret to the best vs. regret to the average (2007, methodology): “Related work Previous work by Auer et al. (2002) considered adapting the learning rate of expert algorithms gradually.”
Improved second-order bounds for prediction with expert advice (2005, unknown): “This is in the same spirit as the self-conﬁdent learning rates considered in Auer, Cesa-Bianchi, and Gentile (2002).”
A survey of Algorithms and Analysis for Adaptive Online Learning (2014, methodology): “For a proof see Auer et al. (2002) or Streeter and McMahan (2010, Lemma 1).”
Mirror Descent Meets Fixed Share (and feels no regret) (2012, background): “We show here how the trick of [11] of having these parameters vary over time can be extended to our setting.”
Follow the Leader with Dropout Perturbations (2014, methodology): “Much fancier tuning methods were introduced by Auer et al. (2002).”
From External to Internal Regret (2005, unknown): “Auer et al. (2002b) derive the external regret bound by taking the expectation with respect to the action distribution (which is identical to the selection distribution).”
A new look at shifting regret (2012, background): “We show here how the trick of Auer et al. (2002) of having these parameters vary over time can be extended to our setting.”
On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes (2018, methodology): “They were ﬁrst proposed in the online learning literature (Auer et al., 2002) and adopted into the stochastic optimization one later (Duchi et al., 2011).”