Abstract
This work is concerned with online learning from expert advice. Extensive work on this problem generated numerous “expert advice algorithms” whose total loss is provably bounded above in terms of the loss incurred by the best expert in hindsight. Such algorithms were devised for various problem variants corresponding to various loss functions. For some loss functions, such as the square, Hellinger and entropy losses, optimal algorithms are known. However, for two of the most widely used loss functions, namely the 0/1 and absolute loss, there are still gaps between the known lower and upper bounds.
In this paper we present two new expert advice algorithms and prove for them the best known 0/1 and absolute loss bounds. Given an expert advice algorithm ALG, the goal is to form an upper bound on the regret L ALG – L* of ALG, where L ALG is the loss of ALG and L* is the loss of the best expert in hindsight. Typically, regret bounds of a “canonical form” C · \(\sqrt {L^ * \ln N} \) are sought where N is the number of experts and C is a constant. So far, the best known constant for the absolute loss function is C = 2.83, which is achieved by the recent IAWM algorithm of Auer et al. (2002). For the 0/1 loss function no bounds of this canonical form are known and the best known regret bound is \(L_{ALG} - L* \leqslant L* + C_1 \ln N + C_2 \sqrt {L*\ln N + \frac{e}{4}\ln ^2 N} \), where C 1 = e − 2 and C 2 = 2\(\sqrt e \). This bound is achieved by a “P-norm” algorithm of Gentile and Littlestone (1999). Our first algorithm is a randomized extension of the “guess and double” algorithm of Cesa-Bianchi et al. (1997). While the guess and double algorithm achieves a canonical regret bound with C = 3.32, the expected regret of our randomized algorithm is canonically bounded with C = 2.49 for the absolute loss function. The algorithm utilizes one random choice at the start of the game. Like the deterministic guess and double algorithm, a deficiency of our algorithm is that it occasionally restarts itself and therefore “forgets” what it learned. Our second algorithm does not forget and enjoys the best known asymptotic performance guarantees for both the absolute and 0/1 loss functions. Specifically, in the case of the absolute loss, our algorithm is canonically bounded with C approaching \(\sqrt 2 \) and in the case of the 0/1 loss, with C approaching 3/\(\sqrt 2 \approx 2.12\). In the 0/1 loss case the algorithm is randomized and the bound is on the expected regret.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Auer, P., Cesa-Bianchi, N., & Gentile. C. (2002). Adaptive and self-confident on-line learning algorithms. Journal of Computer and System Sciences, 64:1, 48–75.
Blackwell, D. (1956). An analog of the minimax theorem for vector payoffs. Pacific J. Math., 6, 1–8.
Blum, A. (1996). On-line algorithms in machine learning. Dagstuhl workshop on On-Line algorithms.
Blum, A. (1997). Empirical support for winnow and weighted-majority algorithms: Results on a calendar scheduling domain. Machine Learning, 5–23.
Blum, A., & Burch, C. (1997). On-line learning and the metrical task system problem. In Proceedings of the IOth Annual Conference on Computational Learning Theoty (pp. 45–53).
Blum, A., Burch, C., & Kalai, A. (1989). Finely-competitive paging. FOCS.
Borodin, A., & El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press.
Cesa-Bianchi, N., Freund, Y., Haussler, D., Helmbold, D., Schapire, R., & Warmuth, M. (1997). How to use expert advice. Journal of the ACM, 44:3, 427–485
Chernoff, H. (1954). Rational selection of decision functions. Econometrica, 22, 422–443.
Cover, T. (1991). Universal portfolios. Mathematical Finance, 1:1, 1–29.
DeSantis, A., Markowsky, G., & Wegman, M. (1988). Learning probabilistic prediction functions. In FOCS (pp. 110–119).
Feder, M., Merhav, N., & Gutman, M. (1992). Universal prediction of individual sequences. IEEE Transactions on Information Theory, 38, 1258–1270.
Freund., Y., & Schapire R. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55:1, 119–139.
Gentile, C., & Littlestone, N. (1999). The robustness of the p-norm algorithms (pp. 1–11).
Haussler, D., Kivinen, J., & Warmuth, M. (1998). Sequential prediction of individual sequences under general loss functions. IEEE Transactions on Information Theory, 4:5, 1906–1925.
Helmbold, D., Long, D., & Sherrod, B. (1996). A dynamic disk spin-down technique for mobile computing. In Proceedings of the Second Annual ACM International Conference on Mobile Computing and Networking. ACM/IEEE.
Helnbold, D., & Schapire, R. (1995). Predicting nearly as well as the best pruning of a decision tree. In COLT.
Littlestone, N., & Warmuth, M. (1994). The weighted majority algorithm. Information and Computation, 108:2, 212–261.
Milnor, J. (1954). Games against nature. In R. Thrall, C. Coombs, & R. Davis (Eds.), Decision Processes (pp. 49–60). New York and London: Wiley and Chapman & Hall.
Sleator, D., & Tarjan, R. (1985). Amortized efficiency of list update and paging rules. 28:2, 202–208.
Vovk, V. (1990). Aggregating strategies. In Proceedings of the Third nnual Workshop on Computational Learning Theory (pp. 371–383).
Rights and permissions
About this article
Cite this article
Yaroshinsky, R., El-Yaniv, R. & Seiden, S.S. How to Better Use Expert Advice. Mach Learn 55, 271–309 (2004). https://doi.org/10.1023/B:MACH.0000027784.72823.e4
Issue Date:
DOI: https://doi.org/10.1023/B:MACH.0000027784.72823.e4