nips nips2005 nips2005-76 nips2005-76-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sham Kakade, Adam Tauman Kalai
Abstract: It is well-known that everything that is learnable in the difficult online setting, where an arbitrary sequences of examples must be labeled one at a time, is also learnable in the batch setting, where examples are drawn independently from a distribution. We show a result in the opposite direction. We give an efficient conversion algorithm from batch to online that is transductive: it uses future unlabeled data. This demonstrates the equivalence between what is properly and efficiently learnable in a batch model and a transductive online model.
[1] B. Awerbuch and R. Kleinberg. Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proc. of the 36th ACM Symposium on Theory of Computing, 2004.
[2] S. Ben-David, E. Kushilevitz, and Y. Mansour. Online learning versus offline learning. Machine Learning 29:45-63, 1997.
[3] A. Blum. Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain. SIAM Journal on Computing 23(5): 990-1000, 1994.
[4] A. Blum, J. Hartline. Near-Optimal Online Auctions. In Proceedings of the Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005.
[5] J. Hannan. Approximation to Bayes Risk in Repeated Plays. In M. Dresher, A. Tucker, and P. Wolfe editors, Contributions to the Theory of Games, Volume 3, p. 97-139, Princeton University Press, 1957.
[6] A. Kalai and S. Vempala. Efficient algorithms for the online decision problem. In Proceedings of the 16th Conference on Computational Learning Theory, 2003.
[7] M. Kearns, R. Schapire, and L. Sellie. Toward Efficient Agnostic Learning. Machine Learning, 17(2/3):115–141, 1994.
[8] N. Littlestone. From On-Line to Batch Learning. In Proceedings of the 2nd Workshop on Computational Learning Theory, p. 269-284, 1989.
[9] N. Littlestone and M. Warmuth. The Weighted Majority Algorithm. Information and Computation, 108:212-261, 1994.
[10] H. Brendan McMahan and Avrim Blum. Online Geometric Optimization in the Bandit Setting Against an Adaptive Adversary. In Proceedings of the 17th Annual Conference on Learning Theory, COLT 2004.
[11] N. Sauer. On the Densities of Families of Sets. Journal of Combinatorial Theory, Series A, 13, p 145-147, 1972.
[12] V. N. Vapnik. Estimation of Dependencies Based on Empirical Data, New York: Springer Verlag, 1982.
[13] V. N. Vapnik. Statistical Learning Theory, New York: Wiley Interscience, 1998.