Efficient Algorithms for Outlier-Robust Regression
Talkat Robust and High-Dimensional Statistics (Simons Institute workshop, 2018) · 2018-10-29..11-02·
summary
Provides a polynomial-time algorithm that tolerates an adversary corrupting an η fraction of training points and outputs a linear predictor whose square loss is at most (1+O(√η))·opt plus O(√η) times a fourth-moment term. It uses a sum-of-squares relaxation, computes a pseudo-expectation predictor (first pseudo-moment) and proves a robust-certifiability lemma to relate corrupted and clean errors. Requires certifiable hypercontractivity or condition-number bounds on X (Gaussians allow η up to ≈0.2).
AI-written summary · about
chapters (12)
- 0:00Start
- 0:32Efficient Algorithms for a Supervised Learning Problem
- 1:01Ordinary Least-Squares Regression
- 1:58The Agnostic Model of Learning
- 11:50Naive Strategy
- 13:51Structural Lemma
- 15:52Absolute Loss
- 28:14Objective Function
- 30:24Distribution over Feasible Solutions
- 31:30Properties Does a Pseudo Distribution Have
- 34:04Summary about Pseudo Expectations
- 38:18Extensions
related talks
12mDistribution-Free Robustness
37mEfficient Algorithms for Reliable Machine Learning
45mHigh Dimensional Robust Sparse Regression
17mTowards Practical Algorithms for Outlier-Robust Estimation
31mTowards Lower Bounds for Efficient Robust Estimation From Worst Case Assumptions
53mDesigning Robust Learners
01h 04mAlgorithmic High Dimensional Robust Statistics II
01h 15mAn overview of classical robust statistics and generalizations to the future