Sublinear-Time Algorithms in Learning
summary
Claims sublinear certification for distribution-dependent agnostic learning: tester-learner pair procedures certify use of agnostic learners for decision lists and halfspaces under uniform or Gaussian input with sample/runtime far below 2^{n/2} by testing only low-order moments via k-wise independence (k ≈ log(1/ε), sample cost n^{O(k)}). A separate line gives fully polynomial semi-agnostic testers and frameworks that detect or tolerate distribution shift. For proper learning of monotone functions the pipeline builds a local computation algorithms based corrector and achieves 2^{~√n} time, matching known lower bounds.
AI-written summary · about
chapters (10)
- 0:00Introduction to the workshop
- 1:14Testing distribution assumptions
- 6:48Challenges in agnostic learning
- 10:38Tester-learner pairs
- 13:25K-wise independence testing
- 17:11Recent advances and research
- 19:31Proper learning of monotone functions
- 22:38Local property correction
- 27:30Matching and local computation
- 30:27Conclusion and applications
related talks
59mTesting Assumptions of Learning Algorithms
17mEfficient Testable Agnostic Learning for Halfspaces
48mPredicting from Noisy and Incomplete Data: Some Perspectives from Computational Learning Theory
01h 06mAnalytic Methods for Supervised Learning III
37mEfficient Algorithms for Reliable Machine Learning
35mTesting Noise Assumptions of Learning Algorithms
44mSomething for Almost Nothing: Advances in Sub-Linear Time Algorithms
01h 30mAnalytic Methods for Supervised Learning IV