A New Paradigm for Learning with Distribution Shift
summary
A new model called TDS learning requires an efficient test on training data that may reject or else outputs a classifier with provable low test error even without assumptions on the test distribution. Algorithms certify transfer by matching low-degree moments and fitting polynomials using sandwiching polynomials (degree O(log(1/ε)) or O(1/ε^2) in noisy cases), and use tools from pseudorandomness, property testing and sum of squares. Results give polynomial-time learners for halfspaces, intersections, tolerant variants and matching SQ lower bounds.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:07Generalization and distribution shift
- 2:53Protein engineering failure
- 8:11AI for health inevitability
- 11:27Introducing TDS learning
- 17:04Domain adaptation bounds impractical
- 23:50TDS vs PAC learning
- 27:06TDS learning for halfspaces
- 32:50Certifying classifier performance
- 39:52Sandwiching polynomials
- 41:22Fully polynomial algorithms
- 42:46Relaxing distribution assumptions
- 44:12Recent TDS advances
- 45:35Concluding thoughts
- 46:18Q&A
related talks
59mTesting Assumptions of Learning Algorithms
33mLearning and Testing Structured Distributions
35mSublinear-Time Algorithms in Learning
53mDesigning Robust Learners
35mTesting Noise Assumptions of Learning Algorithms
50mRobust Deep Learning Under Distribution Shift
37mEfficient Algorithms for Reliable Machine Learning
01h 28mMulti-Distribution Learning, for Robustness, Fairness, and Collaboration