Know When You Know: Handling Adversarial Data by Abstaining
summary
Sequential prediction model where an oblivious stochastic stream is intermittently corrupted by arbitrarily many clean‑label adversarial insertions; algorithm may abstain at no cost on those rounds and still sees true labels when available. Main tool is estimating shattering probability (higher‑order disagreement) to decide when a label will reduce uncertainty; with access to the marginal distribution the learner gets misclassification ≲ O(d^2 log T) (improvable to O(d log T)) and ≲ O(d) abstentions for hypothesis class of VC‑dimension d. Computational and distribution‑free cases require much stronger structure or incur √T losses.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 0:44Motivation for abstaining
- 10:04Sequential prediction model
- 25:10Class example with abstention
- 37:35Algorithm using shattering probabilities
- 44:43Algorithm limitations
- 47:34Rectangle learner
- 52:56Open questions
- 54:18Q&A
related talks
38mBest of Both World Algorithms from I.I.D. to Adversarial Data
43mBeyond Worst Case: When Complex Feedback Can Improve the Label Complexity of Active Learning
58mLabeling a Data Set Using Sublinearly Many Queries
12mDistribution-Free Robustness
37mEfficient Algorithms for Reliable Machine Learning
33mOnline Multivalid Learning: Means, Moments, and Prediction Intervals
25mConfidence-Based Active Learning
49mA New Perspective on Adversarial Perturbations