@inbook {218, title = {On Learnability, Complexity and Stability}, booktitle = {Empirical Inference}, year = {2013}, pages = {59 - 69}, publisher = {Springer Berlin Heidelberg}, organization = {Springer Berlin Heidelberg}, chapter = {7}, address = {Berlin, Heidelberg}, abstract = {

Empirical Inference, Chapter 7

Editors: Bernhard Sch{\"o}lkopf, Zhiyuan Luo and Vladimir Vovk

Abstract:

We consider the fundamental question of learnability of a hypothesis class in the supervised learning setting and in the general 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.

}, isbn = {978-3-642-41135-9}, doi = {10.1007/978-3-642-41136-610.1007/978-3-642-41136-6_7}, url = {http://link.springer.com/10.1007/978-3-642-41136-6}, author = {Villa, Silvia and Lorenzo Rosasco and Tomaso Poggio and Sch{\"o}lkopf, Bernhard and Luo, Zhiyuan and Vovk, Vladimir} }