On learnability, complexity and stability

DOI10.1007/978-3-642-41136-6_7MaRDI QIDQ5264089zbMATH OpenOpenAlexFDO

Authors Silvia Villa, Lorenzo Rosasco, T. Poggio

Publication date 20 July 2015

Published in Empirical Inference (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.5976

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) General nonlinear regression (62J02) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: We consider the fundamental question of learnability of a hypotheses class in the supervised learning setting and in the general learning setting introduced by Vladimir Vapnik. We survey classic results characterizing learnability in term of suitable notions of complexity, as well as more recent results that establish the connection between learnability and stability of a learning algorithm.

Recommendations

• A survey on learning theory. I: Stability and generalization
• Learnability, stability and uniform convergence
• STABILITY RESULTS IN LEARNING THEORY
• Learnability and the Vapnik-Chervonenkis dimension
• 10.1162/153244302760200704

Cited in

(9)

• Fluctuations, effective learnability and metastability in analysis
• On a general structure for adaptation/learning algorithms. -- Stability and performance issues
• A survey on learning theory. I: Stability and generalization
• A class of parameter choice rules for fractional Tikhonov regularization scheme in learning theory
• Measures of complexity in the theory of machine learning
• Control structures in hypothesis spaces: The influence on learning
• Learnability, stability and uniform convergence
• scientific article; zbMATH DE number 6001978 (Why is no real title available?)
• On the intrinsic complexity of learning

This page was built for publication: On learnability, complexity and stability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5264089)