Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Chervonenkis’s Recollections Read chapter Read first chapter

2015 | OriginalPaper | Chapter

15. On Martingale Extensions of Vapnik–Chervonenkis Theory with Applications to Online Learning

Authors : Alexander Rakhlin, Karthik Sridharan

Published in: Measures of Complexity

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We review recent advances on uniform martingale laws of large numbers and the associated sequential complexity measures. These results may be considered as forming a non-i.i.d. generalization of Vapnik–Chervonenkis theory. We discuss applications to online learning, provide a recipe for designing online learning algorithms, and illustrate the techniques on the problem of online node classification. We outline connections to statistical learning theory and discuss inductive principles of stochastic approximation and empirical risk minimization.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Classes of Functions Related to VC Properties
next chapter Measuring the Capacity of Sets of Functions in the Analysis of ERM
Footnotes
1
We may also consider the absolute value of the average without any complications.
 
2
Issues of measurability can be addressed with the techniques in [15].
 
3
It is also possible to study an intermediate setting, where some knowledge about the sequence is available (see, e.g., [27]).
 
Literature
1.
Abernethy, J., Bartlett, P.L., Rakhlin, A., Tewari, A.: Optimal strategies and minimax lower bounds for online convex games. In: Proceedings of the 21st Annual Conference on Learning Theory, pp. 414–424. Omnipress (2008)
2.
Abernethy, J., Agarwal, A., Bartlett, P., Rakhlin, A.: A stochastic view of optimal regret through minimax duality. In: Proceedings of the 22th Annual Conference on Learning Theory (2009)
3.
Aizerman, M.A., Braverman, E.M., Rozonoer, L.I.: The probability problem of pattern recognition learning and the method of potential functions. Avtomatika i Telemekhanika 25, 1175–1193 (1964)
4.
Aizerman, M.A., Braverman, E.M., Rozonoer, L.I.: Theoretical foundations of the potential function method in pattern recognition learning. Avtomatika i Telemekhanika 25, 821–837 (1964)
5.
Aizerman, M.A., Braverman, E.M., Rozonoer, L.I.: The Method of Potential Functions in the Theory of Machine Learning. Nauka, Moscow (1970)
6.
Alon, N., Ben-David, S., Cesa-Bianchi, N., Haussler, D.: Scale-sensitive dimensions, uniform convergence, and learnability. J. ACM 44(4), 615–631 (1997)MathSciNetCrossRefMATH
7.
Audibert, J.: Progressive mixture rules are deviation suboptimal. Adv. Neural Inf. Process. Syst. 20(2), 41–48 (2007)MathSciNet
8.
Bartlett, P.L., Mendelson, S.: Rademacher and Gaussian complexities: risk bounds and structural results. J. Mach. Learn. Res. 3, 463–482 (2002)MathSciNet
9.
Bartlett, P.L., Long, P.M., Williamson, R.C.: Fat-shattering and the learnability of real-valued functions. J. Comput. Syst. Sci. 52(3), 434–452 (1996)MathSciNetCrossRefMATH
10.
Ben-David, S., Pál, D., Shalev-Shwartz, S.: Agnostic online learning. In: Proceedings of the 22th Annual Conference on Learning Theory (2009)
11.
Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press, Cambridge (2006)CrossRefMATH
12.
Cesa-Bianchi, N., Freund, Y., Haussler, D., Helmbold, D.P., Schapire, R.E., Warmuth, M.K.: How to use expert advice. J. ACM 44(3), 427–485 (1997)MathSciNetCrossRefMATH
13.
Cesa-Bianchi, N., Conconi, A., Gentile, C.: On the generalization ability of on-line learning algorithms. IEEE Trans. Inf. Theory 50(9), 2050–2057 (2004)MathSciNetCrossRefMATH
14.
Dudley, R.M.: A course on empirical processes. In: Hennequin, P.L. (ed.) École d’Été de Probabilités de Saint-Flour XII–1982. Lecture Notes in Mathematics, vol. 1097, pp. 2–142. Springer, Berlin (1984)
15.
16.
17.
Kearns, M.J., Schapire, R.E.: Efficient distribution-free learning of probabilistic concepts. J. Comput. Syst. Sci. 48(3), 464–497 (1994)MathSciNetCrossRefMATH
18.
Lecué, G., Mendelson, S.: Aggregation via empirical risk minimization. Probab. Theory Relat. Fields 145(3), 591–613 (2009)CrossRefMATH
19.
Lee, W.S., Bartlett, P.L., Williamson, R.C.: The importance of convexity in learning with squared loss. IEEE Trans. Inf. Theory 44(5), 1974–1980 (1998)MathSciNetCrossRefMATH
20.
Littlestone, N.: Learning quickly when irrelevant attributes abound: a new linear-threshold algorithm. Mach. Learn. 2(4), 285–318 (1988)
21.
22.
23.
24.
25.
Rakhlin, A., Sridharan, K.: Online nonparametric regression. In: The 27th Annual Conference on Learning Theory (2014)
26.
Rakhlin, A., Sridharan, K., Tewari, A.: Online learning: random averages, combinatorial parameters, and learnability. Adv. Neural Inf. Process. Syst. 23, 1984–1992 (2010)
27.
Rakhlin, A., Sridharan, K., Tewari, A.: Online learning: stochastic, constrained, and smoothed adversaries. In: Advances in Neural Information Processing Systems (2011)
28.
Rakhlin, A., Sridharan, K., Tewari, A.: Sequential complexities and uniform martingale laws of large numbers. Probab. Theory Relat. Fields (2014)
29.
Rakhlin, A., Sridharan, K., Tsybakov, A.: Empirical entropy, minimax regret and minimax risk. Bernoulli J. (2015). Forthcoming
30.
Rakhlin, A., Shamir, O., Sridharan, K.: Relax and randomize: from value to algorithms. Adv. Neural Inf. Process. Syst. 25, 2150–2158 (2012)
31.
32.
Sridharan, K., Tewari, A.: Convex games in Banach spaces. In: Proceedings of the 23nd Annual Conference on Learning Theory (2010)
33.
34.
Van de Geer, S.A.: Empirical Processes in M-Estimation. Cambridge University Press, Cambridge (2000)
35.
Van Der Vaart, A.W., Wellner, J.A.: Weak Convergence and Empirical Processes: With Applications to Statistics. Springer, New York (1996)CrossRefMATH
36.
37.
Vapnik, V.N., Chervonenkis, A.Y.: Algorithms with complete memory and recurrent algorithms in pattern recognition learning. Avtomatika i Telemekhanika 4, 95–106 (1968)
38.
Vapnik, V.N., Chervonenkis, A.Y.: Uniform convergence of frequencies of occurrence of events to their probabilities. Dokl. Akad. Nauk SSSR 181, 915–918 (1968)
39.
Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264–280 (1971) (This volume, Chap. 3)
40.
Vapnik, V.N., Chervonenkis, A.Y.: The necessary and sufficient conditions for the uniform convergence of averages to their expected values. Theory Probab. Appl. 26(3), 543–564 (1981)MathSciNetMATH
41.
Vovk, V.: Aggregating strategies. In: Proceedings of the Third Annual Workshop on Computational Learning Theory, pp. 371–386. Morgan Kaufmann, San Mateo (1990)
Metadata
Title
On Martingale Extensions of Vapnik–Chervonenkis Theory with Applications to Online Learning
Authors
Alexander Rakhlin
Karthik Sridharan
Copyright Year
2015
Book
Measures of Complexity

Print ISBN: 978-3-319-21851-9

Electronic ISBN: 978-3-319-21852-6

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-319-21852-6_15

Premium Partner

    Image Credits