Distribution-Free Robustness
summary
Provides an efficient algorithm that tolerates up to a 50% fraction of arbitrary corruptions and achieves near‑optimal clean mean squared error (up to log factors), proves convex losses like L1/Huber cannot reach these guarantees, and handles adaptively chosen covariates so it extends to the first linear contextual bandit tolerant to constant corruption with optimal regret up to logs. Core method is simple alternating minimization over weights and a guessed uncorrupted subset; experiments on UCI Adult show targeted subpopulation accuracy holds where logistic and other baselines collapse under 10% corrupted data.
AI-written summary · about
chapters (8)
- 0:00Start
- 1:57MODERN CHALLENGES
- 3:08HUBER-CONTAMINATED REGRESSION
- 5:15OUR RESULTS
- 6:08ITERATIVE REWEIGHING SCHEME
- 7:21CAN LACK OF ROBUSTNESS LEAD TO UNFAIR OUTCOMES?
- 9:59What is the minimum separation at which point sources of light become indistinguishable?
- 10:48QUESTIONS
related talks
41mEfficient Algorithms for Outlier-Robust Regression
46mCorruption-Robust Contextual Search
34mDistributional Robustness, Learning, and Empirical Likelihood
31mRealizing Robustness
01h 04mAlgorithmic High Dimensional Robust Statistics II
28mPrivacy versus Robustness in Federated Learning: Limits and Algorithms
01h 15mAn overview of classical robust statistics and generalizations to the future
29mCorruption Robust Exploration in Episodic Reinforcement Learning