# On Learnability, Complexity and Stability

arXiv: https://arxiv.org/abs/1303.5976 · HTML: https://mlsanity.com/paper/1303.5976/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Mar 2013.

## Built on by (most cited first, 4 of 4)

- [Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stability](https://mlsanity.com/paper/2102.06589/) (2021)
- [Limits for Learning with Language Models](https://mlsanity.com/paper/2306.12213/) (2023)
- [Re-examining learning linear functions in context](https://mlsanity.com/paper/2411.11465/) (2024)
- [Stochastic Gradient Descent with Momentum is Algorithmically Stable](https://mlsanity.com/paper/2605.28517/) (2026)

## Abstract (arXiv)

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.