nips nips2010 nips2010-193 nips2010-193-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Alexander Rakhlin, Karthik Sridharan, Ambuj Tewari
Abstract: We develop a theory of online learning by defining several complexity measures. Among them are analogues of Rademacher complexity, covering numbers and fatshattering dimension from statistical learning theory. Relationship among these complexity measures, their connection to online learning, and tools for bounding them are provided. We apply these results to various learning problems. We provide a complete characterization of online learnability in the supervised setting. 1
[1] J. Abernethy, A. Agarwal, P. Bartlett, and A. Rakhlin. A stochastic view of optimal regret through minimax duality. In Proceedings of the 22nd Annual Conference on Learning Theory, 2009.
[2] J. Abernethy, P. L. Bartlett, A. Rakhlin, and A. Tewari. Optimal strategies and minimax lower bounds for online convex games. In COLT, pages 414–424, 2008.
[3] N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler. Scale-sensitive dimensions, uniform convergence, and learnability. Journal of the ACM, 44:615–631, 1997.
[4] N. Alon and J. Spencer. The Probabilistic Method. John Wiley & Sons, 2nd edition, 2000.
[5] P. L. Bartlett, P. M. Long, and R. C. Williamson. Fat-shattering and the learnability of real-valued functions. Journal of Computer and System Sciences, 52(3):434–452, 1996. (special issue on COLT‘94).
[6] P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities: risk bounds and structural results. J. Mach. Learn. Res., 3:463–482, 2003.
[7] S. Ben-David, D. Pal, and S. Shalev-Shwartz. Agnostic online learning. In COLT, 2009.
[8] N. Cesa-Bianchi and G. Lugosi. On prediction of individual sequences. A. of S., pages 1865–1895, 1999.
[9] N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
[10] R. M. Dudley. The sizes of compact subsets of Hilbert space and continuity of Gaussian processes. Journal of Functional Analysis, 1(3):290–330, 1967.
[11] R. M. Dudley. Uniform Central Limit Theorems. Cambridge University Press, 1999.
[12] E. Gin´ and J. Zinn. Some limit theorems for empirical processes. Ann. of Prob., 12(4):929–989, 1984. e
[13] J. Hannan. Approximation to Bayes risk in repeated play. Contr. to Theo. of Games, 3:97–139, 1957.
[14] D. Haussler. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100(1):78–150, 1992.
[15] S. M. Kakade and A. Kalai. From batch to transductive online learning. In NIPS, 2005.
[16] A. Tauman Kalai and R. Sastry. The isotron algorithm: High-dimensional isotonic regression. In Proceedings of the 22th Annual Conference on Learning Theory, 2009.
[17] M. J. Kearns and R. E. Schapire. Efficient distribution-free learning of probabilistic concepts. Journal of Computer and System Sciences, 48(3):464–497, 1994.
[18] V. Koltchinskii and D. Panchenko. Rademacher processes and bounding the risk of function learning. High Dimensional Probability II, 47:443–459, 2000.
[19] N. Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2(4):285–318, 04 1988.
[20] P. Massart. Some applications of concentration inequalities to statistics. Annales de la Facult´ des Scie ences de Toulouse, IX(2):245–303, 2000.
[21] S. Mendelson. A few notes on statistical learning theory. In MLSS 2002, pages 1–40. 2003.
[22] S. Mendelson and R. Vershynin. Entropy and the combinatorial dimension. Inventiones mathematicae, 152:37–55, 2003.
[23] D. Pollard. Empirical Processes: Theory and Applications, volume 2. Hayward, CA, 1990.
[24] N. Sauer. On the density of families of sets. J. Combinatorial Theory, 13:145–147, 1972.
[25] S. Shalev-Shwartz and Y. Singer. Convex repeated games and fenchel duality. In NIPS, pages 1265–1272. MIT Press, Cambridge, MA, 2007.
[26] S. Shelah. A combinatorial problem: Stability and order for models and theories in infinitary languages. Pac. J. Math, 4:247–261, 1972.
[27] K. Sridharan and A. Tewari. Convex games in banach spaces. In COLT, 2010.
[28] A. W. Van Der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes : With Applications to Statistics. Springer Series, March 1996.
[29] L. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.
[30] S.A. van de Geer. Empirical Processes in M-Estimation. Cambridge University Press, 2000.
[31] V. N. Vapnik. Estimation of Dependences Based on Empirical Data (Springer Series in Statistics). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1982.
[32] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264–280, 1971.
[33] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In ICML, pages 928–936, 2003. 9