On Learnability, Complexity and Stability
This is an incremental survey paper that synthesizes existing theoretical results on learnability for researchers in machine learning theory.
The paper surveys classic and recent results on the learnability of hypotheses classes in supervised and general learning settings, focusing on characterizations through complexity measures and connections to algorithm stability.
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.