Central Limit Theorems and Bootstrap in High Dimensions

Victor Chernozhukov, Denis Chetverikov, Kengo Kato

TL;DR

This paper develops new theoretical tools (Central Limit Theorems and bootstrap methods) to approximate probabilities involving sums of high-dimensional random vectors. The key innovation is showing these approximations remain accurate even when the dimension of the vectors ($p$) is much larger than the number of samples ($n$), a common scenario in modern data analysis.

What Problem Does This Paper Address?

In statistics and machine learning, we often deal with high-dimensional data, where the number of features ($p$) can be significantly larger than the number of observations ($n$). A fundamental question is how to understand the distribution of sums of random vectors in such settings. Specifically, this paper tackles the problem of approximating probabilities of the form $P(n^{-1/2}\sum_{i=1}^{n}X_{i}\in A)$, where $X_i$ are independent random vectors in $\mathbb{R}^p$ and $A$ is a set. Traditional methods often fail or provide poor approximations when $p$ is large. The authors aim to provide theoretical guarantees for these approximations, particularly for sets $A$ like hyperrectangles and more general "sparsely convex sets," which are relevant in statistical applications.

Methods

The paper's core contribution lies in deriving new Central Limit Theorems (CLTs) and bootstrap theorems for high-dimensional random vectors.

  • Central Limit Theorems (CLTs): The authors extend classical CLTs to high dimensions. They derive bounds on the difference between the true probability $P(n^{-1/2}\sum X_i \in A)$ and its Gaussian approximation $P(n^{-1/2}\sum Y_i \in A)$, where $Y_i$ are Gaussian random vectors with the same covariance as $X_i$. A key aspect is that these bounds hold even when $p \gg n$. The proofs rely on sophisticated techniques, including anti-concentration inequalities and Slepian-type interpolations.
  • Bootstrap Theorems: To address the practical challenge of unknown covariance matrices, the paper also develops multiplier bootstrap and empirical bootstrap theorems. These methods provide data-dependent approximations for the probabilities, allowing for estimation without knowing the true distribution of $X_i$.

The novelty lies in the ability to handle the high-dimensional regime ($p \gg n$) and the specific classes of sets considered (hyperrectangles and sparsely convex sets).

Datasets

Not discussed in the paper. The paper is theoretical and focuses on deriving general theorems and bounds.

Key Insights and Ideas

  • High-Dimensional Approximations are Possible: The most significant insight is that accurate Gaussian and bootstrap approximations for probabilities involving sums of random vectors are achievable even when the dimension $p$ is much larger than the sample size $n$. This is a crucial result for applying statistical methods in modern high-dimensional data settings.
  • Sparsely Convex Sets are Key: The paper introduces and analyzes "sparsely convex sets." These are sets defined by a limited number of constraints, making them computationally tractable and relevant for statistical models with sparse structures. The theoretical results extend to these sets, broadening their applicability.
  • Weakening Requirements on Dimension: The authors show that for hyperrectangles, the requirement on $p$ for the approximation error to vanish can be as mild as $p = O(e^{Cn^c})$, significantly relaxing previous conditions that often required $p$ to grow much slower than $n$.
  • Bootstrap for High Dimensions: The development of multiplier and empirical bootstrap theorems that work in high dimensions provides practical tools for inference when the underlying distribution is unknown.

Key Results

The paper presents several key theoretical results:

  • Theorem 2.1 (Abstract High Dimensional CLT for Hyperrectangles): Provides a bound on the approximation error for hyperrectangles, showing it converges to zero even when $p \gg n$.
  • Proposition 2.1 (High Dimensional CLT for Hyperrectangles): Derives more explicit bounds under specific moment conditions, demonstrating the convergence to zero for $p \gg n$.
  • Proposition 3.1 (High Dimensional CLT for Simple Convex Sets): Extends the CLT results to a broader class of "simple convex sets."
  • Proposition 3.2 (High Dimensional CLT for Sparsely Convex Sets): Extends the CLT results to "s-sparsely convex sets," which are relevant for sparse statistical models.
  • Theorem 4.1 (Abstract Multiplier Bootstrap Theorem): Provides a bound for the multiplier bootstrap approximation error for simple convex sets.
  • Theorem 4.2 (Abstract Empirical Bootstrap Theorem): Provides a bound for the empirical bootstrap approximation error for hyperrectangles.
  • Proposition 4.1 & 4.2: Derive explicit bounds for multiplier and empirical bootstrap for simple convex and sparsely convex sets, respectively.

The quantitative results are in the form of upper bounds on the approximation errors, often expressed in terms of $n$, $p$, and moments of the random vectors.

Limitations and Future Work

  • Dependence on Constants: The bounds derived involve constants that can depend on various parameters (e.g., $a, b, d, s, q$). The authors note that understanding the optimal dependence of these constants on parameters like $s$ (for sparsely convex sets) is an open question for future work.
  • Optimality of Rates: While the paper achieves significant improvements in the dependence on dimension $p$, the dependence on $n$ (e.g., $n^{-1/6}$) might not be optimal in all cases. The authors conjecture that certain rates might be optimal in a minimax sense.
  • Specific Applications: The paper provides theoretical foundations. Future work could focus on applying these results to specific statistical problems in high dimensions, such as hypothesis testing or estimation, and analyzing their practical performance.
  • Dimension-Free Anti-Concentration: The paper mentions that a dimension-free anti-concentration bound exists for max-hyperrectangles but is less sharp for general hyperrectangles. Investigating whether a dimension-free bound can be established for other classes of sets considered would be valuable.

Summary updated

Abstract

This paper derives central limit and bootstrap theorems for probabilities that sums of centered high-dimensional random vectors hit hyperrectangles and sparsely convex sets. Specifically, we derive Gaussian and bootstrap approximations for probabilities $\Pr(n^{-1/2}\sum_{i=1}^n X_i\in A)$ where $X_1,\dots,X_n$ are independent random vectors in $\mathbb{R}^p$ and $A$ is a hyperrectangle, or, more generally, a sparsely convex set, and show that the approximation error converges to zero even if $p=p_n\to \infty$ as $n \to \infty$ and $p \gg n$; in particular, $p$ can be as large as $O(e^{Cn^c})$ for some constants $c,C>0$. The result holds uniformly over all hyperrectangles, or more generally, sparsely convex sets, and does not require any restriction on the correlation structure among coordinates of $X_i$. Sparsely convex sets are sets that can be represented as intersections of many convex sets whose indicator functions depend only on a small subset of their arguments, with hyperrectangles being a special case.
BibTeX
@article{chernozhukov2014central,
  author = {Victor Chernozhukov and Denis Chetverikov and Kengo Kato},
  title = {{Central Limit Theorems and Bootstrap in High Dimensions}},
  journal = {The Annals of Probability},
  year = {2014},
}
Figure