Algorithmic High-Dimensional Robust Statistics

Introduction to Robust Statistics 1
1.1 Introduction 1
1.2 Contamination Model 2
1.3 Information-Theoretic Limits 9
1.4 One-Dimensional Robust Estimation 12
1.5 Higher-Dimensional Robust Mean Estimation 17
1.6 Connection with Breakdown Point 20
1.7 Exercises 22
1.8 Discussion and Related Work 27
2 Ecient High-Dimensional Robust Mean Estimation 29
2.1 Introduction 29
2.2 Stability and Robust Mean Estimation 32
2.3 The Unknown Convex Programming Method 41
2.4 The Filtering Method 43
2.5 Exercises 54
2.6 Discussion and Related Work 58
3 Algorithmic Refinements in Robust Mean Estimation 61
3.1 Introduction 61
3.2 Near-Optimal Sample Complexity of Stability 62
3.3 Robust Mean Estimation in Near-Linear Time 72
3.4 Robust Mean Estimation with Additive or Subtractive
Corruptions 81
3.5 Robust Estimation via Nonconvex Optimization 88
3.6 Robust Sparse Mean Estimation 91
vii
viii Contents
3.7 Exercises 95
3.8 Discussion and Related Work 98
4 Robust Covariance Estimation 100
4.1 Introduction 100
4.2 Ecient Algorithm for Robust Covariance Estimation 101
4.3 Applications to Concrete Distribution Families 110
4.4 Reduction to Zero-Mean Case 113
4.5 Exercises 115
4.6 Discussion and Related Work 117
5 List-Decodable Learning 119
5.1 Introduction 119
5.2 Information-Theoretic Limits of List-Decodable Learning 125
5.3 Ecient Algorithms for List-Decodable Mean Estimation 133
5.4 Application: Learning Mixture Models 154
5.5 Exercises 161
5.6 Discussion and Related Work 164
6 Robust Estimation via Higher Moments 166
6.1 Introduction 166
6.2 Leveraging Higher-Degree Moments in List-Decodable
Learning 167
6.3 List-Decodable Learning via Variance of Polynomials 170
6.4 List-Decodable Learning via Sum of Squares 179
6.5 Leveraging Higher Moments in Robust Mean Estimation 186
6.6 Clustering Mixture Models via Higher-Degree Moments 190
6.7 Exercises 199
6.8 Discussion and Related Work 201
7 Robust Supervised Learning 204
7.1 Introduction 204
7.2 Outlier-Robust Algorithms for Linear Regression 205
7.3 Robust Learning of Linear Separators 209
7.4 Robust Stochastic Optimization 217
7.5 Exercises 222
7.6 Discussion and Related Work 226
8 Information-Computation Trade-os in High-Dimensional
Robust Statistics 229
8.1 Introduction 229
8.2 Statistical Query Lower Bounds 230
8.3 Reduction-Based Computational Hardness 252
Contents ix
8.4 Exercises 259
8.5 Discussion and Related Work 263
Appendix Mathematical Background 265
A.1 Martingales 265
A.2 Hermite Polynomials 267
A.3 Probabilistic Inequalities 268
References 271
Index 282