Nearly optimal central limit theorem and bootstrap approximations in high dimensions

Victor Chernozhukov, Denis Chetverikov, Yuta Koike

TL;DR

This paper provides new, near-optimal bounds for approximating the distribution of high-dimensional random vectors with a Gaussian distribution, particularly for sets shaped like rectangles. These bounds are crucial for statistical inference in high-dimensional settings and also extend to bootstrap approximations, offering practical tools for data analysis.

What Problem Does This Paper Address?

In statistics, a fundamental goal is to understand the distribution of complex data. The Central Limit Theorem (CLT) tells us that sums (or averages) of many independent random variables tend towards a Gaussian (normal) distribution. However, in high-dimensional settings (where the number of variables, $d$, is large, potentially much larger than the number of samples, $n$), this approximation can be slow and inaccurate, especially when we're interested in the probability of the data falling into specific regions (like rectangles). Existing bounds often depend too heavily on the dimension $d$ or the sample size $n$, limiting their practical use. This paper aims to derive tighter, near-optimal bounds for this Gaussian approximation in high dimensions, specifically for the class of rectangular sets, and to extend these results to bootstrap methods.

Methods

The authors employ a sophisticated blend of techniques to derive their bounds. A core method is the Slepian-Stein method, a powerful tool for approximating probability distributions. They introduce novel "mixed smoothing inequalities" which involve approximating indicator functions of rectangles with smooth functions, first by Lipschitz smoothing and then by convolution with a Gaussian distribution. This smoothing is key to achieving near-optimal dependence on the sample size $n$. They also leverage the exchangeable pair approach and Taylor expansions to analyze the error terms. For bootstrap approximations, they adapt these Gaussian approximation techniques to the bootstrap settings.

Datasets

Not discussed in the paper. The paper focuses on theoretical bounds for random vectors and does not involve empirical datasets.

Key Insights and Ideas

  • Near-Optimal Bounds for Rectangles: The paper achieves bounds that are nearly optimal in terms of sample size ($n$), dimension ($d$), and the "envelope constant" ($B_n$), which measures the magnitude of the random vectors. This is a significant improvement over previous results.
  • The Power of Smoothing: The introduction of "mixed smoothing inequalities" is a critical technical contribution, enabling the derivation of sharper bounds by making the problem analytically tractable.
  • Bootstrap Approximations are Nearly as Good: The paper demonstrates that similar near-optimal bounds can be achieved for both multiplier and empirical bootstrap approximations, making these methods reliable alternatives when the true distribution is unknown.
  • Handling Unbounded Variables: The authors extend their results to cases where the random vectors are not uniformly bounded, relying on moment conditions instead, which is more general.
  • Special Cases Offer Further Improvement: For specific scenarios like "smooth" distributions (with an additive Gaussian component) or distributions with zero skewness, the bounds can be further improved, sometimes removing logarithmic factors or achieving faster convergence rates.

Key Results

The paper derives a bound for the Kolmogorov distance $\rho$ between the distribution of the scaled average of $n$ independent $d$-dimensional random vectors $X_1, \dots, X_n$ and a Gaussian distribution. For bounded $X_i$'s, the bound takes the form:

$\rho \le C \left( B_n^2 \frac{\log^3 d}{n} \right)^{1/2} \log n$

where $d$ is the dimension, $n$ is the sample size, $B_n$ is the envelope constant, and $C$ is a universal constant. This bound is shown to be nearly optimal. Similar bounds are established for multiplier and empirical bootstrap approximations. The paper also provides bounds for unbounded random vectors and improved bounds for special cases.

Limitations and Future Work

The authors acknowledge that the derived bounds are "nearly optimal," meaning there might still be small logarithmic factors that could potentially be removed in certain cases. They suggest that further improvements might be possible by imposing stronger conditions on the random vectors, such as symmetry or specific moment constraints. The paper also opens avenues for applying these refined bounds to specific statistical problems in high-dimensional settings, such as hypothesis testing or model selection.

Summary updated

Abstract

In this paper, we derive new, nearly optimal bounds for the Gaussian approximation to scaled averages of $n$ independent high-dimensional centered random vectors $X_1,\dots,X_n$ over the class of rectangles in the case when the covariance matrix of the scaled average is non-degenerate. In the case of bounded $X_i$'s, the implied bound for the Kolmogorov distance between the distribution of the scaled average and the Gaussian vector takes the form $$C (B^2_n \log^3 d/n)^{1/2} \log n,$$ where $d$ is the dimension of the vectors and $B_n$ is a uniform envelope constant on components of $X_i$'s. This bound is sharp in terms of $d$ and $B_n$, and is nearly (up to $\log n$) sharp in terms of the sample size $n$. In addition, we show that similar bounds hold for the multiplier and empirical bootstrap approximations. Moreover, we establish bounds that allow for unbounded $X_i$'s, formulated solely in terms of moments of $X_i$'s. Finally, we demonstrate that the bounds can be further improved in some special smooth and zero-skewness cases.
BibTeX
@article{chernozhukov2020nearly,
  author = {Victor Chernozhukov and Denis Chetverikov and Yuta Koike},
  title = {{Nearly optimal central limit theorem and bootstrap approximations in high dimensions}},
  journal = {The Annals of Applied Probability},
  year = {2020},
}
Figure