Some Problems of Robust High-dimensional Statistics
Talkat Robust and High-Dimensional Statistics (Simons Institute workshop, 2018) · 2018-10-29..11-02·
summary
Problem is robust subspace recovery with arbitrary adversarial outliers; adversary may place points anywhere and at any magnitude. Key claims: a RANSAC-type random subset procedure recovers the subspace if SNR ≥ C·d (exponential time otherwise), and a practical spherical geodesic gradient descent algorithm on the Grassmannian converges to the true subspace when initialized by PCA under a stability condition that depends on an empirical spherical condition number. Analysis gives linear convergence after modified steps and extends to Gaussian inlier/outlier models where SNR can vanish.
AI-written summary · about
chapters (22)
- 0:00Intro
- 1:30Robustness in Ancient Times of Science
- 1:46Robustness from Ancient Times of Science
- 3:08Theory of Robustness
- 5:28Outline
- 5:56The Robust Subspace Recovery (RSR) Problem
- 6:41Why should we care about RSR?
- 7:57General Approaches to RSR
- 8:49The RSR Formulation can be ill-defined
- 10:59More Clarification for RSR
- 15:14Theoretical Settings for RSR
- 21:46Motivating Questions
- 22:33Best SNR for Well-defined Formulation
- 26:20Best SNR for RANSAC
- 29:36Another Proposal for Adversarial Outliers
- 30:52Review of WTL & GGD
- 32:23Review of GGD
- 33:37Spherical GGD with Adversarial Outliers
- 36:22Table of Comparisons
- 38:01Open Directions in RSR
- 40:06Relevance to Other Problems
- 40:19Take-Home Message
related talks
45mHigh Dimensional Robust Sparse Regression
01h 04mAlgorithmic High Dimensional Robust Statistics II
01h 02mTheory and Big Data
01h 00mAlgorithmic High Dimensional Robust Statistics I
17mTowards Practical Algorithms for Outlier-Robust Estimation
01h 07mRecent Progress in High-Dimensional Learning
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
49mRobust PCA via Non-convex Methods: Provable Bounds