Top

Published in:

2013 | OriginalPaper | Chapter

7. On Learnability, Complexity and Stability

Authors : Silvia Villa, Lorenzo Rosasco, Tomaso Poggio

Published in: Empirical Inference

Publisher: Springer Berlin Heidelberg

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

search-config

AI-assisted search

Off

Abstract

We considerStability—( Learnability—( the fundamental question of learnability of a hypothesis class in the supervised learningSupervised learning setting and in the general learningGeneral learning setting introduced by Vladimir Vapnik. We survey classic results characterizing learnability in terms of suitable notions of complexity, as well as more recent results that establish the connection between learnability and stability of a learning algorithm.

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 On the Relations and Differences Between Popper Dimension, Exclusion Dimension and VC-Dimension

next chapter Loss Functions

ConsistencyConsistency can be defined with respect to other convergence notions for random variables. If the loss function is bounded, convergence in probability is equivalent to convergence in expectation.

We say that a learning algorithm A is symmetric if it does not depend on the order of the points in z _n.

Note that this construction is not possible in classification or in regression with the square loss.

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

Anthony, M., Bartlett, P.L.: Neural network learning: theoretical foundations. Cambridge University Press, Cambridge (1999)CrossRefMATH

Bartlett, P., Long, P., Williamson, R.: Fat-shattering and the learnability of real-valued functions. J. Comput. Syst. Sci. 52, 434–452 (1996)MathSciNetCrossRefMATH

Bousquet, O., Elisseeff, A.: Stability and generalization. J. Mach. Learn. Res. 2, 499–526 (2002)MathSciNetMATH

Daniely, A., Sabato, S., Ben-David, S., Shalev-Shwartz, S.: Multiclass learnability and the ERM principle. J. Mach. Learn. Res. Proc. Track 19, 207–232 (2011)

Devroye, L., Györfi, L., Lugosi, G.: A Probabilistic Theory of Pattern Recognition. Applications of Mathematics 31. Springer, New York (1996)

Dudley, R., Giné, E., Zinn, J.: Uniform and universal Glivenko-Cantelli classes. J. Theor. Prob. 4, 485–510 (1991)CrossRefMATH

Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Mathematics and Its Applications, vol. 375. Kluwer, Dordrecht (1996)

Kearns, M.J., Schapire, R.E.: Efficient distribution-free learning of probabilistic concepts. In: Computational Learning Theory and Natural Learning Systems. Bradford Books, vol. I, pp. 289–329. MIT, Cambridge (1994)

10.

Kutin, S., Niyogi, P.: Almost-everywhere algorithmic stability and generalization error. Technical report TR-2002-03, Department of Computer Science, The University of Chicago (2002)

11.

Mukherjee, S., Niyogi, P., Poggio, T., Rifkin, R.: Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization. Adv. Comput. Math. 25(1–3), 161–193 (2006)MathSciNetCrossRefMATH

12.

Poggio, T., Rifkin, R., Mukherjee, S., Niyogi, P.: General conditions for predictivity in learning theory. Nature 428, 419–422 (2004)CrossRef

13.

Rakhlin, A., Sridharan, K., Tewari, A.: Online learning: beyond regret. J. Mach. Learn. Res. Proc. Track 19, 559–594 (2011)

14.

Shalev-Shwartz, S., Shamir, O., Srebro, N., Sridharan, K.: Learnability, stability and uniform convergence. J. Mach. Learn. Res. 11, 2635–2670 (2010)MathSciNetMATH

15.

Steinwart, I., Christmann, A.: Support Vector Machines. Information Science and Statistics. Springer, New York (2008)MATH

16.

Vapnik, V.: The Nature of Statistical Learning Theory. Springer, New York (1995)CrossRefMATH

17.

Vapnik, V.N., Chervonenkis, A.Y.: Theory of uniform convergence of frequencies of events to their probabilities and problems of search for an optimal solution from empirical data. Avtomatika i Telemekhanika 2, 42–53 (1971)MathSciNet

Title: On Learnability, Complexity and Stability
Authors: Silvia Villa
Lorenzo Rosasco
Tomaso Poggio
Publisher: Springer Berlin Heidelberg
Book: Empirical Inference
Print ISBN: 978-3-642-41135-9

Electronic ISBN: 978-3-642-41136-6

Copyright Year: 2013
DOI: https://doi.org/10.1007/978-3-642-41136-6_7

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner