Efficient Algorithms for Reliable Machine Learning
summary
Introduces a concrete proof system called testable learning where an algorithm either returns a classifier with error at most opt + ε or abstains, and must accept when Gaussian margins or specified noise models hold; uses low-degree moment-matching, L1 polynomial regression and a disagreement/band tester built from Chow-parameter-like checks; extends to adversarial contamination via iterated polynomial filtering, achieving the optimal 2η + ε error tolerance and polynomial-time bounds (samples/time scale like d^{O(1/ε^c)} in current analyses).
AI-written summary · about
chapters (7)
- 0:00Introduction
- 1:25Motivation for testable learning
- 12:17Testable learning model
- 17:15Testing noise assumptions
- 25:31Learning with contamination
- 31:32Concluding thoughts
- 32:15Q&A
related talks
59mTesting Assumptions of Learning Algorithms
35mTesting Noise Assumptions of Learning Algorithms
41mEfficient Algorithms for Outlier-Robust Regression
53mDesigning Robust Learners
17mEfficient Testable Agnostic Learning for Halfspaces
35mSublinear-Time Algorithms in Learning
31mRealizing Robustness
01h 12mRecent Progress in High-Dimensional Learning