Realizable Learning is All You Need

Abstract

The equivalence of realizable and agnostic learnability is a fundamental phenomenon in learning theory. With variants ranging from classical settings like PAC learning and regression to recent trends such as adversarially robust learning, it's surprising that we still lack a unified theory; traditional proofs of the equivalence tend to be disparate, and rely on strong model-specific assumptions like uniform convergence and sample compression. In this work, we give the first model-independent framework explaining the equivalence of realizable and agnostic learnability: a three-line blackbox reduction that simplifies, unifies, and extends our understanding across a wide variety of settings. This includes models with no known characterization of learnability such as learning with arbitrary distributional assumptions and more general loss functions, as well as a host of other popular settings such as robust learning, partial learning, fair learning, and the statistical query model. More generally, we argue that the equivalence of realizable and agnostic learning is actually a special case of a broader phenomenon we call property generalization: any desirable property of a learning algorithm (e.g. noise tolerance, privacy, stability) that can be satisfied over finite hypothesis classes extends (possibly in some variation) to any learnable hypothesis class.

References in corpus (17)

• Synthesizing Robust Adversarial Examples
• Loss minimization and parameter estimation with heavy tails
• Uniform convergence may be unable to explain generalization in deep learning
• VC Classes are Adversarially Robustly Learnable, but Only Improperly
• Multiclass learnability and the ERM principle
• Probably Approximately Metric-Fair Learning
• Optimal Learners for Multiclass Problems
• Limits of Private Learning with Access to Public Data
• Private Query Release Assisted by Public Data
• Learning from Mixtures of Private and Public Populations
• PAC learning with stable and private predictions
• Closure Properties for Private Classification and Online Prediction
• Reducing Adversarially Robust Learning to Non-Robust PAC Learning
• A learning problem that is independent of the set theory ZFC axioms
• Adversarially Robust Learning with Unknown Perturbation Sets
• Robust learning under clean-label attack
• Impossibility of Characterizing Distribution Learning -- a simple solution to a long-standing problem