Silvia Villa, Lorenzo Rosasco, Tomaso Poggio
Published 2013-03-24Version 1
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.
Complexity of Linear Regions in Deep Networks
On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
On the Existence of a Complexity in Fixed Budget Bandit Identification
![QR code for arXiv:1303.5976 [stat.ML]](http://oss.arxitics.com/images/favicon.svg)