Lecture Notes: Selected topics on robust statistical learning theory

Matthieu LeraslearXiv 2019 · arXiv

Introduction

Classical statistical learning theory is largely built upon the foundation of "sub-Gaussian" assumptions. These assumptions imply that the probability of encountering extreme values decays exponentially, similar to a normal distribution. While this framework allows for elegant proofs and the success of Empirical Risk Minimization (ERM), it often fails to account for the complexities of real-world data. This document explores a unified framework for robust statistical learning, designed to maintain high performance even when data exhibits heavy tails or has been subjected to adversarial corruption.

The Limitations of Empirical Risk Minimization

In standard machine learning, models are typically trained by minimizing the average loss over a dataset. This approach is highly effective when the data is well-behaved. However, in fields such as finance, network traffic analysis, and social media metrics, data often possesses "heavy tails"—where extreme outliers are far more frequent than a bell curve would suggest.

In these scenarios, the empirical mean becomes an unreliable estimator; a single extreme outlier can significantly bias the entire model. The core challenge addressed in these notes is the design of estimators that are "robust": they must achieve performance guarantees comparable to a theoretical "oracle" (the best possible model) even when the data only possesses a finite second moment (variance) or contains a percentage of malicious outliers, such as those described in Huber’s contamination model.

Robust Estimation Strategies

To overcome the sensitivity of the empirical mean, several key principles are introduced:

1. Median-of-Means (MOM)

The Median-of-Means principle is a fundamental alternative to simple averaging. The dataset is divided into $K$ disjoint blocks, the mean is calculated for each block, and the final estimate is the median of those means. This simple yet powerful modification allows for "sub-Gaussian" performance levels even when the underlying data is heavy-tailed, effectively neutralizing the impact of outliers in any single block.

2. The Minmax Tournament Principle

For more complex learning tasks, the author advocates for a minmax strategy. Rather than minimizing a global loss function, the estimator participates in a "tournament." It compares candidate models pairwise using robust tests to identify the candidate that is "least defeated" by its competitors. This framework provides a robust way to select models in high-dimensional spaces.

3. The Homogeneity Lemma

A significant theoretical contribution in these notes is the Homogeneity Lemma. This tool simplifies the analysis of complex minmax estimators by allowing researchers to prove accuracy based on the estimator's behavior in small, localized regions around the true target. This localization is critical for deriving tight error bounds.

Theoretical Foundations: The Small Ball Method

To prove that these robust models function correctly, the author utilizes the "Small Ball" approach. This method focuses on ensuring that the underlying data distribution is not too concentrated in any single area of the sample space. By satisfying the Small Ball Hypothesis, the robust estimator can effectively distinguish the true signal from noise or intentional corruption, ensuring that the resulting model remains close to the optimal "oracle" solution.

Computational Feasibility and Convex Relaxations

A historical barrier to robust statistics has been computational complexity; many robust estimators, such as Tukey’s Median, are NP-hard to compute in high dimensions. These notes bridge the gap between theory and practice by demonstrating how Semidefinite Programming (SDP) can be used to create convex relaxations of these estimators. These relaxations allow for the approximation of robust estimators in polynomial time, making them viable for modern, large-scale data applications.

Key Results and Oracle Inequalities

The framework established in these notes leads to several significant conclusions:

  • Oracle Inequalities: Robust minmax MOM estimators are shown to satisfy oracle inequalities, meaning their error is only a small constant factor larger than that of an ideal estimator with perfect knowledge of the distribution.
  • High-Dimensional Scaling: These methods maintain sub-Gaussian deviation rates even in multivariate settings where the dimension $d$ is large, proving their utility in high-dimensional regression and mean estimation.
  • Algorithmic Efficiency: The notes demonstrate that it is possible to construct algorithms that run in nearly linear time while maintaining optimal robust error rates.

Limitations and Future Directions

While the framework is robust, it is not without limitations. Some advanced M-estimators require prior knowledge or accurate estimates of noise variance, which may not be available in all practical settings. Additionally, while polynomial-time algorithms exist via SDP, they can still be computationally expensive compared to non-robust alternatives. Future research is directed toward refining these into even faster spectral algorithms and extending the theory to "misspecified" models where the true data-generating function lies outside the hypothesized model space.

Summary updated

Abstract

These notes gather recent results on robust statistical learning theory. The goal is to stress the main principles underlying the construction and theoretical analysis of these estimators rather than provide an exhaustive account on this rapidly growing field. The notes are the basis of lectures given at the conference StatMathAppli 2019.
BibTeX
@misc{lerasle2019lecture,
  author = {Matthieu Lerasle},
  title = {{Lecture Notes: Selected topics on robust statistical learning theory}},
  year = {2019},
  eprint = {1908.10761},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1908.10761},
}
Figure