nips nips2003 nips2003-146 nips2003-146-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Claire Monteleoni, Tommi S. Jaakkola
Abstract: We consider an online learning scenario in which the learner can make predictions on the basis of a fixed set of experts. We derive upper and lower relative loss bounds for a class of universal learning algorithms involving a switching dynamics over the choice of the experts. On the basis of the performance bounds we provide the optimal a priori discretization for learning the parameter that governs the switching dynamics. We demonstrate the new algorithm in the context of wireless networks.
[1] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire. Gambling in a rigged casino: the adversarial multi-armed bandit problem. In Proc. of the 36th Annual Symposium on Foundations of Computer Science, pages 322–331, 1995.
[2] Berkeley. UC Berkeley home IP web traces. In http://ita.ee.lbl.gov/html/contrib/UCB.homeIP-HTTP.html, 1996.
[3] A. Blum, C. Burch, and A. Kalai. Finely-competitive paging. In IEEE 40th Annual Symposium on Foundations of Computer Science, page 450, New York, New York, October 1999.
[4] D. P. Foster and R. Vohra. Regret in the on-line decision problem. Games and Economic Behavior, 29:7–35, 1999.
[5] Y. Freund and R. Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79–103, 1999.
[6] D. Haussler, J. Kivinen, and M. K. Warmuth. Sequential prediction of individual sequences under general loss functions. IEEE Trans. on Information Theory, 44(5):1906–1925, 1998.
[7] D. P. Helmbold, R. E. Schapire, Y. Singer, and M. K. Warmuth. On-line portfolio selection using multiplicative updates. In International Conference on Machine Learning, pages 243– 251, 1996.
[8] M. Herbster and M. K. Warmuth. Tracking the best expert. Machine Learning, 32:151–178, 1998.
[9] IEEE. Computer society LAN MAN standards committee. In IEEE Std 802.11: Wireless LAN Medium Access Control and Physical Layer Specifications, August 1999.
[10] R. Krashinsky and H. Balakrishnan. Minimizing energy for wireless web access with bounded slowdown. In MobiCom 2002, Atlanta, GA, September 2002.
[11] R. Krichevsky and V. Trofimov. The performance of universal encoding. IEEE Trans. on Information Theory, 27(2):199–207, 1981.
[12] N. Littlestone and M. K. Warmuth. The weighted majority algorithm. In IEEE Symposium on Foundations of Computer Science, pages 256–261, 1989.
[13] C. Steinbach. A reinforcement-learning approach to power management. In AI Technical Report, M.Eng Thesis, Artificial Intelligence Laboratory, MIT, May 2002.
[14] V. Vovk. Derandomizing stochastic prediction strategies. Machine Learning, 35:247–282, 1999.