Testing Noise Assumptions of Learning Algorithms
summary
Claims an efficient procedure that tests noise assumptions and either outputs a classifier with a certificate of optimality or rejects; extends RV23 testable learning and gives a fully-polynomial time algorithm (runtime poly(d,1/ε)) for halfspaces under Gaussian marginals with Massart noise. Core tools are band testers, PSD moment matrices and low-degree polynomial moment checks; shows a separation: testable learning for RCN at η=1/2 is super-polynomial while classical learning remains trivial. The algorithms succeed under model assumptions and deliberately reject when data violate them.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:50Label noise setup
- 5:24Massart noise model
- 11:38Testing noise assumptions
- 15:41Algorithm overview
- 21:55Certifying noise assumptions
- 28:18Massart noise model extension
- 32:01Summary
related talks
59mTesting Assumptions of Learning Algorithms
37mEfficient Algorithms for Reliable Machine Learning
17mEfficient Testable Agnostic Learning for Halfspaces
01h 12mRecent Progress in High-Dimensional Learning
35mSublinear-Time Algorithms in Learning
48mPredicting from Noisy and Incomplete Data: Some Perspectives from Computational Learning Theory
31mSQ Lower Bounds for Learning Halfspaces with Massart Noise
01h 12mPedagogical Talk: Frameworks for Information-Computation Tradeoffs