High-Dimensional Statistics

Philippe Rigollet, Jan-Christian HütterarXiv 2023 · DOI · arXiv

Abstract

These lecture notes were written for the course 18.657, High Dimensional Statistics at MIT. They build on a set of notes that was prepared at Princeton University in 2013-14 that was modified (and hopefully improved) over the years.

Introduction

Traditional statistical theory was built for the "low-dimensional" regime, where the number of samples ($n$) grows much faster than the number of variables ($d$). However, modern data—ranging from genomic sequences to high-frequency financial signals—is often "high-dimensional." In these cases, classical methods like Ordinary Least Squares (OLS) fail because the system is underdetermined; there are infinitely many ways to fit the noise perfectly without capturing the underlying signal.

The core challenge addressed in these notes is: How can we perform meaningful inference when $d \gg n$? By bridging the gap between parametric statistics and nonparametric statistics, the authors demonstrate that if the underlying signal possesses structure (e.g., sparsity), accurate recovery remains possible.

Mathematical Framework

The notes synthesize several key mathematical pillars of modern statistics. To navigate the complex proofs, a rigorous set of notation for functions, sets, vectors, and matrices is established.

Common notation for functions, sets, vectors, and matrices used throughout the notes.

A central tool is the Concentration of Measure. The authors use sub-Gaussian and sub-exponential random variable theory to prove that averages of high-dimensional noise stay close to their expectations with very high probability. This allows for the derivation of bounds that hold even as the dimension $d$ increases.

Regularization and Distributional Assumptions

Since standard Empirical Risk Minimization (ERM) overfits in high dimensions, the focus shifts to regularization. Key techniques include:

  • $\ell_1$ penalization (Lasso): Encourages sparsity and allows for convex optimization.
  • $\ell_0$ constraints (BIC): Provides a theoretical benchmark for the best possible sparse fit, though it is NP-hard to compute.
  • Slope Estimator: A sorted $\ell_1$ penalty that adapts better to unknown sparsity levels.

The analysis of these estimators requires a clear definition of the underlying probability distributions and the function spaces they inhabit, such as Sobolev classes.

Notation for univariate and multivariate distributions, including sub-Gaussian and sub-Exponential classes, and Sobolev function spaces.

Key Theoretical Results

The notes provide several landmark results in high-dimensional estimation:

  • Lasso Convergence: The authors prove that the Lasso achieves an error rate of $k \log d / n$ (where $k$ is the number of relevant features) under the "Restricted Eigenvalue Condition."
  • Minimax Optimality: Using information-theoretic tools like Fano’s Inequality and the Varshamov-Gilbert Lemma, they demonstrate that the rate $\sigma^2 \frac{k}{n} \log(ed/k)$ is the absolute best possible rate for sparse estimation in the Gaussian Sequence Model.
  • PCA Consistency: They provide bounds for the Davis-Kahan $\sin(\theta)$ theorem, showing exactly how much the estimated principal subspace deviates from the truth based on the "gap" between eigenvalues.

Insights and Limitations

A major insight is that the "statistical price" of not knowing which features are important is only logarithmic in the dimension ($\log d$). This allows for handling exponentially more features than samples, provided only a few are truly active. However, there is often a computation-statistics gap; for instance, the BIC estimator is statistically superior but computationally intractable compared to the Lasso.

Furthermore, many fast convergence rates rely on conditions like Incoherence or Restricted Eigenvalues, which are notoriously difficult to check for a given real-world design matrix. The theory also largely assumes independent and identically distributed (i.i.d.) data, leaving non-stationary high-dimensional data as a subject for future study.

Summary updated

Abstract

These lecture notes were written for the course 18.657, High Dimensional Statistics at MIT. They build on a set of notes that was prepared at Princeton University in 2013-14 that was modified (and hopefully improved) over the years.
BibTeX
@misc{rigollet2023high,
  author = {Philippe Rigollet and Jan-Christian Hütter},
  title = {{High-Dimensional Statistics}},
  year = {2023},
  eprint = {2310.19244},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.19244},
}
Figure