Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes
summary
Defines Comparative Learning and proves that the sample complexity is governed by the mutual VC dimension, not the individual VC dimensions; gives a construction mapping any source S and benchmark B to an agreement partial hypothesis class and reduces comparative learning to agnostic partial‑hypothesis learning to get matching upper and lower bounds. Shows ERM can fail (examples where each class has infinite VC but mutual VC is zero) and extends to real‑valued multiaccuracy/multicalibration via the mutual fat‑shattering dimension.
AI-written summary · about
chapters (5)
- 0:00Start
- 1:31A Classic Learning Task: Binary Classification
- 2:45Realizable and Agnostic PAC Learning
- 7:58When combined, learning becomes trivial.
- 19:13Proof of the Comparative Learning Characterization
related talks
46mEliciting and Enforcing Subjective Individual Fairness
01h 17mOverview of Statistical Learning Theory Part 1
47mUnprovability and Other Impossibility Results in Machine Learning
33mMachine Learning from Human Comparative Judgments
01h 03mOverview of Statistical Learning Theory Part 2
01h 11mA Theory of Multi-objective Machine Learning
53mGroups and Individuals in Fairness and Probability
48mPersonalized Collaborative Learning with Affinity-Based Variance Reduction