Improved second-order bounds for prediction with expert advice

By Nicolò Cesa-Bianchi, Yishay Mansour, Gilles Stoltz. 2005

288 citations recorded by the source corpus.

This work studies external regret in sequential prediction games with both positive and negative payoffs. External regret measures the difference between the payoff obtained by the forecasting strategy and the payoff of the best action. In this setting, we derive new and sharper regret bounds for the well-known exponentially weighted average forecaster and for a second forecaster with a different multiplicative update rule. Our analysis has two main advantages: first, no preliminary knowledge about the payoff sequence is needed, not even its range; second, our bounds are expressed in terms of sums of squared payoffs, replacing larger first-order quantities appearing in previous bounds. In addition, our most refined bounds have the natural and desirable property of being stable under rescalings and general translations of the payoff sequence.

Subfields: Artificial Intelligence, 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 Management Science and Operations Research

Citations in the corpus

Semi-Cyclic Stochastic Gradient Descent (2019, methodology): “The proof (in Appendix A) is based on classic analysis of the PROD algorithm (Cesa-Bianchi et al., 2007; see also EvenDar et al., 2008; Sani et al., 2014).”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “Another direction was explored by Hazan and Kale [96] building on previous works in the full information setting — [64].”
Online Learning with Switching Costs and Other Adaptive Adversaries (2013, background): “Analyses of Hedge in settings where the loss range may vary over time have also been considered —see, e.g., [9].”
Prediction, learning, and games (2006, methodology): “8 are due to Cesa-Bianchi, Mansour, and Stoltz [57].”
Sharp Oracle Inequalities for Aggregation of Affine Estimators (2011, background): “Note also that the problem of competing against the best procedure in a given family has been extensively studied in the context of online learning and prediction with expert advice [18, 19, 40].”
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications (2012, methodology): “This algorithm has been studied before as the prod algorithm of Cesa-Bianchi, Mansour, and Stoltz [17], and Theorem 2.1 can be seen to follow from Lemma 2 in [17].”
Regret bounded by gradual variation for online convex optimization (2014, methodology): “the cost functions are chosen completely adversarially, is posed as an open problem in Bianchi et al. (2005). The concern is whether or not it is possible to derive a regret bound for an online optimization algorithm by the variation of the observed cost functions. Recently Hazan and Kale (2010) mad”
Competing with Automata-based Expert Sequences (2018, background): “This has led to a definition of regret against the best sequence of experts with k shifts in the seminal work of Herbster and Warmuth [1998] on tracking the best expert.”
Exploiting easy data in online optimization (2014, methodology): “P ROD , is based on the classic P ROD algorithm popularized by Cesa-Bianchi et al. [8] and builds on a variant of P ROD called D -”
Online Learning with Predictable Sequences (2012, methodology): “, xt−1) = 1 t−1 ∑ t−1 s=1 xs are known as variance bounds (see Cesa-Bianchi et al. (2007); Hazan and Kale (2009, 2010); Rakhlin et al. (2011)).”
Regret to the best vs. regret to the average (2007, methodology): “The proof is nearly identical to the proof of Lemma 2 of Cesa-Bianchi et al. (2007). Notice that when i = 0 (the special expert), the last term in the bound is 0.”
Adaptive Subgradient Methods for Online Learning and Stochastic Optimization (2011, methodology): “Tighter regret bounds using the variation of the cost functions f t were proposed by Cesa-Bianchi et al. (2007) and derived by Hazan and Kale (2008).”
Better Algorithms for Benign Bandits (2009, background): “The conjecture that the regret of online learning algorithms should be bounded in terms of the total variation was put forth by Cesa-Bianchi, Mansour and Stoltz [5] in the full information model (where the online player is allowed to observe the costs of actions she did not choose).”