Efficient Tracking of Large Classes of Experts

Details Efficient Tracking of Large Classes of Experts Efficient Tracking of Large Classes of Experts

2011-10-12

arxiv.org/abs/1110.2755v2

Computer Science

Learning

26 pages

Scientific paper

In the framework for 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 derive a family of efficient tracking algorithms that, for any prediction algorithm $\A$ designed for the base class, can be implemented with time and space complexity $O(n^{\gamma} \log n)$ times larger than that of $\A$, where $n$ is the time horizon and $\gamma \ge 0$ is a parameter of the algorithm. With $\A$ properly chosen, our algorithm achieves a regret bound of optimal order for $\gamma>0$, and only $O(\log n)$ times larger than the optimal order for $\gamma=0$ for all typical regret bound types we examined. For example, for predicting binary sequences with switching parameters, our method achieves the optimal $O(\log n)$ regret rate with time complexity $O(n^{1+\gamma}\log n)$ for any $\gamma\in (0,1)$.

Affiliated with

Also associated with

No associations

Rating

Efficient Tracking of Large Classes of Experts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Tracking of Large Classes of Experts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Tracking of Large Classes of Experts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-634692