Learnability, Stability and Uniform Convergence I: A Problem Is Learnable if and only if It Admits a Uniform-RO Stable Universal AERMResearch Paper
In supervised binary classification, a hypothesis class is learnable if and only if it has uniform convergence, meaning that empirical risks converge to true risks uniformly over the class. When that holds, empirical risk minimisation (ERM) learns. This equivalence, due to Vapnik and Chervonenkis and extended to real-valued losses by Alon, Ben-David,…