Table of Contents

Table of Contents:

Chapter 1 Introduction to Robust Statistics

1.1 Introduction

1.2 Contamination Model

1.3 Information-Theoretic Limits

1.4 One-Dimensional Robust Estimation

1.5 Higher-Dimensional Robust Mean Estimation

1.6 Connection with Breakdown Point

Exercises

1.7 Discussion and Related Work

Chapter 2 Robust Mean Estimation

2.1 Introduction

2.2 Stability and Robust Mean Estimation

2.3 The Unknown Convex Programming Method

2.4 The Filtering Method

Exercises

2.5 Discussion and Related Work

Chapter 3 Algorithmic Refinements in Robust Estimation

3.1 Introduction

3.2 Near-Optimal Sample Complexity of Stability

3.3 Robust Mean Estimation in Near-Linear Time

3.4 Robust Mean Estimation with Additive or Subtractive Corruptions

3.5 Robust Estimation via Non-Convex Optimization

3.6 Robust Sparse Mean Estimation

Exercises

3.7 Discussion and Related Work

Chapter 4 Robust Covariance Estimation

4.1 Introduction

4.2 Efficient Algorithm for Robust Covariance Estimation

4.3 Applications to Concrete Distribution Families

4.4 Reduction to Zero-Mean Case

Exercises

4.5 Discussion and Related Work

Chapter 5 List-Decodable Learning

5.1 Introduction

5.2 Information-Theoretic Limits of List-Decodable Learning

5.3 Efficient Algorithms for List-Decodable Mean Estimation

5.4 Application: Learning Mixture Models

Exercises

5.5 Discussion and Related Work

Chapter 6 Robust Estimation via Higher Moments

6.1 Introduction

6.2 Leveraging Higher-Degree Moments in List-Decodable Learning

6.3 List-Decodable Learning via Variance of Polynomials

6.4 List-Decodable Learning via Sum-of-Squares

6.5 Leveraging Higher Moments in Robust Mean Estimation

6.6 Clustering Mixture Models via Higher Degree Moments

Exercises

6.7 Discussion and Related Work

Chapter 7 Robust Supervised Learning

7.1 Introduction

7.2 Outlier-Robust Algorithms for Linear Regression

7.3 Robust Learning of Linear Separators

7.4 Robust Stochastic Optimization

Exercises

7.5 Discussion and Related Work

Chapter 8 Information-Computation Tradeoffs

8.1 Introduction

8.2 Statistical Query Lower Bounds

8.3 Reduction-based Computational Hardness

Exercises

8.4 Discussion and Related Work

Appendix Mathematical Background

A.1 Martingales

A.2 Hermite Polynomials

A.3 Probabilistic Inequalities