Beyond Worst Case: When Complex Feedback Can Improve the Label Complexity of Active Learning

on YouTube ↗43m

" summary

Combines a cheap but biased weak labeler and an expensive correct oracle by training a cost-sensitive difference classifier that enforces very low false negatives and is only learned over the current disagreement region, then runs epoched disagreement-based active learning and retrains the classifier as the region shrinks. Naive learning costs O(D' / ε) labels to learn differences; the proposed bound replaces a dominant O(d Θ ν^2 / ε^2) term with roughly D' Θ (ν+ε)/ε + d σ ν^2/ε^2, giving fewer expensive oracle queries. Also gives a modified binary search* for abstaining labelers with sample complexity O(ε^{-α}) versus O(ε^{-α-2β}) without abstentions.

AI-written summary · about

" chapters (28)

1. 0:00Intro
2. 0:46Classification
3. 1:23Challenge: Acquiring Labeled Data
4. 3:06Why Active Learning Helps?
5. 4:11Why is Agnostic Active Learning hard?
6. 5:30Talk Agenda
7. 7:59PAC Model: Realizable vs. Agnostic
8. 9:26Methods for Agnostic Active Learning
9. 10:16Disagreement-based Active Learning
10. 11:33Oracle and Weak Labeler
11. 11:49The Model
12. 13:45Formal Model Implications
13. 14:45Previous Work
14. 15:55Algorithm Outline
15. 19:32Solution
16. 20:59Key Observation 2
17. 22:30Full Algorithm
18. 23:10Label Complexity: Definitions
19. 24:38Label Complexity: Assumptions
20. 27:08Talk Outline
21. 30:01Example: Learning Thresholds
22. 32:10When can we exploit abstentions?
23. 33:27Basic Algorithm: Binary Search
24. 35:01Modified Binary Search
25. 36:26Performance Guarantees
26. 37:04Example: An Informative Response Model
27. 38:49Summary
28. 39:08Conclusion

" related talks

• 58mLabeling a Data Set Using Sublinearly Many QueriesSanjoy Dasgupta · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 31mInteractive Learning of Classifiers and Other StructuresSanjoy Dasgupta, Rob Nowak · Foundations of Machine Learning Boot Camp 2017
• 25mConfidence-Based Active LearningKamalika Chaudhuri · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 00mKnow When You Know: Handling Adversarial Data by AbstainingSurbhi Goel · Emerging Generalization Settings 2024
• 30mActive Learning and Human-in-the-Loop Machine LearningLukas Biewald · Data By the Bay 2016
• 17mSelf-Training Converts Weak Learners to Strong Learners in Mixture ModelsSpencer Frei · Deep Learning Theory Symposium 2021
• 51mEfficient Deep Learning with Humans in the LoopZachary Lipton · Emerging Challenges in Deep Learning (Simons Institute workshop, 2019)
• 49mOracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust LearningNika Haghtalab · Quantifying Uncertainty: Stochastic, Adversarial, and Beyond