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.
Description
[1303.5976v1] On Learnability, Complexity and Stability
%0 Journal Article
%1 villa2013learnability
%A Villa, Silvia
%A Rosasco, Lorenzo
%A Poggio, Tomaso
%D 2013
%K complexity generalization learning probability readings stable stats theory
%T On Learnability, Complexity and Stability
%U http://arxiv.org/abs/1303.5976
%X 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.
@article{villa2013learnability,
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.},
added-at = {2019-05-24T11:50:23.000+0200},
author = {Villa, Silvia and Rosasco, Lorenzo and Poggio, Tomaso},
biburl = {https://www.bibsonomy.org/bibtex/2c559e1f65aa1ee69a9845bcf79da844a/kirk86},
description = {[1303.5976v1] On Learnability, Complexity and Stability},
interhash = {3561ce550c308244c2630e448918e1ce},
intrahash = {c559e1f65aa1ee69a9845bcf79da844a},
keywords = {complexity generalization learning probability readings stable stats theory},
note = {cite arxiv:1303.5976},
timestamp = {2019-11-16T01:28:16.000+0100},
title = {On Learnability, Complexity and Stability},
url = {http://arxiv.org/abs/1303.5976},
year = 2013
}