Efficient Tracking of Large Classes of Experts

By András György, Tamás Linder, Gábor Lugosi. 2011

78 citations recorded by the source corpus.

In the framework of prediction of individual sequences, sequential prediction methods are to be constructed that perform nearly as well as the best expert from a given class. We consider prediction strategies that compete with the class of switching strategies that can segment a given sequence into several blocks, and follow the advice of a different “base” expert in each block. As usual, the performance of the algorithm is measured by the regret defined as the excess loss relative to the best switching strategy selected in hindsight for the particular sequence to be predicted. In this paper, we construct prediction strategies of low computational cost for the case where the set of base experts is large. In particular, we provide a method that can transform any prediction algorithm A that is designed for the base class into a tracking algorithm. The resulting tracking algorithm can take advantage of the prediction performance and potential computational efficiency of A in the sense that it can be implemented with time and space complexity only O(nγ lnn) times larger than that of A, where n is the time horizon and γ ≥ 0 is a parameter of the algorithm. With A properly chosen, our algorithm achieves a regret bound of optimal order for γ >; 0, and only O(lnn) times larger than the optimal order for γ = 0 for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters under the logarithmic loss, our method achieves the optimal O(lnn) regret rate with time complexity O(n1+γlnn) for any γ ∈ (0,1).

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, 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 Electrical and Electronic Engineering

In Management Science and Operations Research

Citations in the corpus

Compress and Control (2014, background): “A promising line of investigation might be to consider the class of meta-algorithms given by György, Linder, and Lugosi (2012), that can convert any stationary coding distribution into its piece-wise stationary extension; efficient algorithms from this class have shown promise for data compression…”
Proximal Online Gradient Is Optimum for Dynamic Regret: A General Lower Bound (2021, background): “The result in [42], [48] implies an upper bound O (√ MT log(2) T ) for the shifting regret.”
Shifting Regret, Mirror Descent, and Matrices (2016, methodology): “…& Krom, 1997; Hazan & Seshadhri, 2009; György et al., 2012) whose computational complexity is almost linear in T and maintain the mild dependence on the size of the expert class, while only slightly deteriorating performance (see György et al. 2012 for an overview of tracking algorithms.)”
Online Convex Optimization in Dynamic Environments (2015, methodology): “For a thorough treatment of existing methods see [35].”
Online Optimization in Dynamic Environments (2013, methodology): “For a thorough treatment of existing methods see [34].”
Dynamical Models and tracking regret in online convex programming (2013, background): “Other algorithms can accommodate larger classes of experts, or not assume knowledge of the number of switches, but come at the price of higher regret or complexity as explained in (Gyorgy et al., 2012).”
Competing with Automata-based Expert Sequences (2018, background): “This work has subsequently been improved to account for broader expert classes [Gyorgy et al., 2012], to deal with unknown parameters [Monteleoni and Jaakkola, 2003], and has been further generalized [Vovk, 1999, Cesa-Bianchi et al.”
A Closer Look at Adaptive Regret (2012, background): “We refer to György et al. (2012) for an in-depth analysis.”
Improved Strongly Adaptive Online Learning using Coin Betting (2016, methodology): “Indeed, every study on m-shift regret with time O(NT log T ) results in suboptimal m-shift regret bounds [5, 8, 9], to our knowledge.”
Proximal Online Gradient is Optimum for Dynamic Regret (2018, background): “3 Shifting regret (or tracking regret) The M−shifting regret of an algorithm A ∈ A is defined by [6, 38, 40–47] R̃T := T ∑”
The Forget-me-not Process (2016, background): “Many variants have been proposed in the literature [20, 11, 10, 17], which trade off predictive accuracy for improved time and space complexity; in particular the Partition Tree Weighting meta-algorithm [17] has O(n log n) time and O(log n) space complexity, and has been shown empirically to exhibit”
Dynamic Regret of Strongly Adaptive Methods (2017, methodology): “We note that a similar strategy for deciding the ending time was proposed by György et al. (2012) in the study of “prediction with expert advice”.”
Efficient tracking of a growing number of experts (2017, background): “While our work belongs to the ﬁrst category, it should be possible to transport our regret bounds to the convex bounded case by using time-varying learning rates, as done e.g. by Hazan and Seshadhri (2009) and Gyorgy et al. (2012).”
Exploiting easy data in online optimization (2014, unknown): “, [19, 15]).”