betaFeedback

WorksMathematics

High-Dimensional Gaussian and Bootstrap Approximation: Near 1/n1/\sqrt{n} Rates with General Covariance

Abstract

We consider Berry-Esseen bounds over rectangles for sums of nn random vectors in Rp\mathbb{R}^p that are i.i.d. A longstanding open question in high-dimensional probability and statistics is whether bounds of order 1/n1/\sqrt n are attainable up to factors of log⁡(pn)\log(pn) when the population covariance matrix is unrestricted. We answer this question affirmatively, provided that the random vectors have sub-Gaussian entries with non-zero variance. In addition, we provide analogous results for bootstrap approximation and Gaussian comparison, which make use of a special discrepancy measure between covariance matrices that enables improvement with respect to prior work. Taking an approach based on interpolation, the novel aspects of the proofs deal with bounding the interpolation derivatives in a way that is not sensitive to the covariance structure.

Introduction

A central topic in high-dimensional probability and statistics is to develop upper bounds on the distance

Dn=sup⁡A∈R∣P(Sn∈A)−P(G∈A)∣(1)D_n = \sup_{A \in\mathcal{R}} \left| \mathbb{P}(S_n \in A) - \mathbb{P}(G \in A) \right| \tag*{(1)}

where Sn=1n∑i=1nXiS_n = \frac{1}{\sqrt{n}}\sum_{i=1}^{n} X_i is a normalized sum of centered i.i.d. random vectors in Rp\mathbb{R}^p, GG is a centered Gaussian vector with covariance matrix E(X1X1⊤)\mathbb{E}(X_1X_1^\top), and R\mathcal{R} is the class of all rectangles in Rp\mathbb{R}^p. This measure of distance has attracted major interest because it strikes a special balance between theory and application. On one hand, it is known that accurate Gaussian approximation with respect to DnD_n is possible when p≫np \gg n, while on the other hand, a wide range of high-dimensional inference procedures can be analyzed in terms of probabilities of the form P(Sn∈A)\mathbb{P}(S_n \in A). We refer to [5, 9] (Chernozhukov et al. 2023) for overviews of these developments.

Prior work. Much of the contemporary interest in Berry-Esseen type bounds for DnD_n was initiated in Chernozhukov, Chetverikov and Kato [10], where it was shown that if R\mathcal{R} is replaced with a certain subclass of rectangles, and if the entries of X1X_1 have sufficiently light tails, then the corresponding distance is at most of order n−1/8log⁡7/8(pn)n^{-1/8}\log^{7/8}(pn). This bound was pathbreaking in two key respects, because it featured mild logarithmic dependence on the dimension pp, while also imposing no restriction on the off-diagonal entries of E(X1X1⊤)\mathbb{E}(X_1X_1^\top). Moreover, the paper included similar results for Gaussian comparison and bootstrap approximation, which are topics that will be discussed in § 2.

In the subsequent years, there was a cascade of theoretical advances seeking to extend and sharpen the results in Chernozhukov, Chetverikov and Kato [10]. However, before summarizing this line of work, a basic point to keep in mind is that for many years, there was not a clear consensus about whether near n−1/2n^{-1/2} rates of Gaussian approximation over rectangles are even possible in a general sense when p≫np \gg n. Indeed, at different times, conjectures were made that n−1/6n^{-1/6} or n−1/4n^{-1/4} rates of approximation may be optimal up to logarithmic

MSC2020 subject classifications. Primary 60F05; secondary 62E17, 62G09.

Keywords and phrases. high-dimensional central limit theorem, Berry–Esseen bound, Gaussian comparison, bootstrap, Gaussian surface measure. factors when Σ\Sigma is unrestricted. Also, many contributions were made in improving the initial rates from near n−1/8n^{-1/8} to near n−1/4n^{-1/4} ([12, 19, 30, 15]), as well as in identifying conditions for ensuring asymptotically consistent Gaussian approximation when p≫np \gg n ([17, 30, 27, 18]).

Broadly speaking, most of the progress that has been made in bounding DnD_n at faster than near n−1/4n^{-1/4} rates has been based on additional structural assumptions. For example, the paper ([20]) obtained near n−1/3n^{-1/3} rates when the smallest eigenvalue λmin⁡\lambda_{\min} of the correlation matrix of X1X_1 satisfies λmin⁡≳1\lambda_{\min} \gtrsim1, and showed that this can be improved to near n−1/2n^{-1/2} when X1X_1 also has a log-concave density. In turn, the achievability of n−1/2n^{-1/2} rates without a log-concave density when λmin⁡≳1\lambda_{\min} \gtrsim1 was shown in ([32, 31, 2] (Chernozhukov, Chetverikov and Koike 2023)). Furthermore, the paper ([22]) obtained a similar result when a non-degeneracy assumption is satisfied by all of the 3×33 \times3 correlation submatrices, and the paper ([28]) showed that Edgeworth-based approximations can yield near n−1n^{-1} rates when λmin⁡≳1\lambda_{\min} \gtrsim1 and X1X_1 has a Stein kernel. Meanwhile, it was shown in Fang and Koike [21] that a log-concave density for X1X_1 alone is sufficient to ensure near n−1/2n^{-1/2} rates for general covariance matrices. In a different direction, the papers ([33, 34]) allow for certain degenerate covariance matrices, but instead work with a subclass of rectangles and assume the entries of X1X_1 satisfy a weak variance decay condition. Lastly, and most recently, the paper ([23]) made progress without extra structure, showing that near n−1/3n^{-1/3} rates are achievable for general covariance matrices.

Summary of results. Despite all of the advances just described, the question of whether DnD_n can be bounded at near n−1/2n^{-1/2} rates for general covariance matrices has remained open, and the purpose of this work is to answer it affirmatively. More specifically, our first main result in Theorem 2.1 shows that if the entries of X1X_1 are normalized to have unit variance and if the sub-Gaussian condition ∥X1j∥ψ2≤B\lVert X_{1j}\rVert_{\psi_2} \le B holds for all j≤pj \le p, then DnD_n is at most of order Bn−1/2log⁡3(pn)log⁡(n)Bn^{-1/2}\log^3(pn)\log(n).

As an extension of our Gaussian approximation result, we consider the related problem of comparing pp-dimensional Gaussian vectors G~∼N(0,Σ~)\widetilde{G} \sim\mathcal{N}(0,\widetilde{\Sigma}) and G∼N(0,Σ)G \sim\mathcal{N}(0,\Sigma) over rectangles. Here, we show that the comparison can be controlled in terms of a special discrepancy measure d(Σ~,Σ)d(\widetilde{\Sigma},\Sigma), which is defined in (2) and allows for Σ~\widetilde{\Sigma} and Σ\Sigma to be degenerate. In this notation, our Gaussian comparison result in Theorem 2.2 shows that if the entries of GG are normalized to have unit variance, and if d(Σ~,Σ)≤δd(\widetilde{\Sigma},\Sigma) \le\delta, then the distance sup⁡A∈R∣P(G~∈A)−P(G∈A)∣\sup_{A \in\mathcal{R}} \left|\mathbb{P}(\widetilde{G} \in A) - \mathbb{P}(G \in A)\right| is at most of order δlog⁡(p)log⁡(1+1/δ)\delta\log(p)\log(1+1/\delta). To our knowledge, the discrepancy measure d(Σ~,Σ)d(\widetilde{\Sigma},\Sigma) is novel in this context, and it is an important technical ingredient that enables Theorem 2.2 to improve upon other recent Gaussian comparison results in high dimensions. (See the remarks after that result for further discussion.) Also, in handling degenerate covariance matrices, this result may be of particular interest in connection with discretized versions of continuous Gaussian processes.

Our last main result deals with approximations involving the Gaussian multiplier bootstrap procedure ([10]), which generates bootstrap samples of SnS_n defined by Sn∗=1n∑i=1nξi∗XiS_n^* = \frac{1}{\sqrt{n}}\sum_{i=1}^n \xi_i^*X_i, where ξ1∗,…,ξn∗\xi_1^*,\ldots,\xi_n^* are i.i.d. N(0,1)\mathcal{N}(0,1) random variables that are independent of X‾1,…,Xn\overline{X}_1,\ldots,X_n. If the entries of X1X_1 are normalized to have unit variance and satisfy a suitable sub-Gaussian type condition, then Theorem 2.3 shows that with high probability, the random distance sup⁡A∈R∣P∗(Sn∗∈A)−P(Sn∈A)∣\sup_{A \in\mathcal{R}} \left|\mathbb{P}^*(S_n^* \in A) - \mathbb{P}(S_n \in A)\right| satisfies a bound that is similar to the aforementioned one for DnD_n, where P∗\mathbb{P}^* denotes probability conditional on X1,…,XnX_1,\ldots,X_n. Likewise, Theorem 2.3 improves upon previous bootstrap approximation results in ways that are similar to the improvements of Theorem 2.1 in the Gaussian approximation context. (The bulk of comparable results on high-dimensional bootstrap approximation are analogous to the ones for Gaussian approximation, and are included in the works cited above.)

Proof techniques. The high-level framework of the proof is based on interpolation and induction, which have been foundational in previous work. If SnS_n and GG are as in eqn. (1), and N∼N(0,Ip)N \sim\mathcal{N}(0,I_p) is independent of them, then our interpolation is built from the “smoothed orthant indicator” gu(y)=P(y+uG+σN≤β)g_u(y) = \mathbb{P}(y + \sqrt{u}G + \sigma N \leq\beta), where y∈Rpy \in\mathbb{R}^p is viewed as the argument, β∈Rp\beta\in\mathbb{R}^p is the corner point of the orthant, σ>0\sigma> 0 is a small smoothing parameter, and u=u(t)=1−t+σ2u = u(t) = 1 - t + \sigma^2 for t∈[0,1]t \in[0,1]. Because σ\sigma will be chosen to be negligible, it follows that the function Ψ(t)=E(gu(tSn))\Psi(t) = \mathbb{E}(g_u(\sqrt{t}S_n)) satisfies Ψ(1)≈P(Sn≤β)\Psi(1) \approx\mathbb{P}(S_n \leq\beta) and Ψ(0)≈P(G≤β)\Psi(0) \approx\mathbb{P}(G \leq\beta). Thus, the primary substance of the proof consists in controlling the difference P(Sn≤β)−P(G≤β)≈∫01Ψ′(t)dt\mathbb{P}(S_n \leq\beta) - \mathbb{P}(G \leq\beta) \approx\int_0^1 \Psi'(t)dt through the derivatives of gu(y)g_u(y).

The essential difficulty in quantifying these derivatives is due to the unrestricted correlation structure of GG. To see this, note that gu(y)g_u(y) can be rewritten as the probability that a standard Gaussian vector hits a generic polyhedron with pp facets. In other words, the complexity of E(X1X1⊤)\mathbb{E}(X_1X_1^\top) translates into geometric complexity, which then appears in the derivatives of gu(y)g_u(y). Also, it should be emphasized that in the case when λmin⁡≳1\lambda_{\min} \gtrsim1, much of this complexity is concealed. Roughly speaking, this is because the function gu(y)g_u(y) can be effectively replaced with the distribution function of N(y,σ2Ip)\mathcal{N}(y,\sigma^2I_p), which has special structure in its higher-order derivatives that can be leveraged in a non-trivial way when pp is large [6, 1, 20, 32] (Chernozhukov, Chetverikov and Koike 2023).

In light of the complexity of high-dimensional polyhedra, much prior work has pursued techniques that circumvent it. Two recent works that have stood out by dealing with polyhedra in a relatively direct way are [22, 23], and our work is similar in this regard. Accordingly, some of the key objects in our analysis are what we call “facet functions” ψ1(y),…,ψp(y)\psi_1(y),\ldots,\psi_p(y) (see eqns. (10) and (13)), which are proportional to the standard Gaussian surface measures of the pp facets of a polyhedron P(y)P(y) parameterized by y∈Rpy \in\mathbb{R}^p. To a large extent, the problem of controlling Ψ′(t)\Psi'(t) when the matrix E(X1X1⊤)\mathbb{E}(X_1X_1^\top) is degenerate amounts to controlling the first several derivatives of ψ1,…,ψp\psi_1,\ldots,\psi_p. This connection is clarified by a quantity we call the “facet sensitivity” F(y)\mathcal{F}(y) of P(y)P(y), which is a global measure of the sensitivity of the functions log⁡ψ1,…,log⁡ψp\log\psi_1,\ldots,\log\psi_p to translations of P(y)P(y) (see eqns. (11) and (12) and Proposition 3.4). On this point, it should be noted that the upper bounds on F(y)\mathcal{F}(y) that we present in Proposition 3.5 make use of Lemmas 26 and 30 in Gao and Zhang [23]. However, our introduction of F(y)\mathcal{F}(y) as a way to unify the quantities needed for upper bounding ∣Ψ′(t)∣|\Psi'(t)| is a novel component of our work, and our interpolation is quite different from the two separate interpolations used in Gao and Zhang [23].

References

  1. [1]Anderson, N. H., Hall, P. and Titterington, D. M. (1998). Edgeworth expansions in very-high-dimensional problems. Journal of Statistical Planning and Inference 70 1–18.DOI
  2. [2]Aronow, P. M. and Lopatto, P. (2026). Optimal central limit theorem for bounded random variables in high dimensions. arXiv:2609.07067.arxiv.org/abs/2609.07067
  3. [3]Bakry, D., Gentil, I. and Ledoux, M. (2014). Analysis and Geometry of Markov Diffusion Operators. Springer.DOI
  4. [4]Barthe, F. and Cordero-Erausquin, D. (2013). Invariances in variance estimates. Proceedings of the London Mathematical Society 106 33–64.DOI
  5. [5]Belloni, A., Chernozhukov, V., Chetverikov, D., Hansen, C. and Kato, K. (2018). High-dimensional econometrics and regularized GMM. arXiv:1806.01888.arxiv.org/abs/1806.01888
  6. [6]Bentkus, V. (1990). Smooth approximations of the norm and differentiable functions with bounded support in Banach space l₁∞. Lithuanian Mathematical Journal 30 223–230.
  7. [7]Birnbaum, Z. W. (1942). An inequality for Mill’s ratio. Annals of Mathematical Statistics 13 245–246.DOI
  8. [8]Boucheron, S., Lugosi, G. and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press.
  9. [9]Chakraborty, N. and Lahiri, S. N. (2025). The central limit theorem in high dimensions and its applications. In Frontiers of Statistics and Data Science (S. Ghosal and A. Roy, eds.) 81–100. Springer.DOI
  10. [10]Chernozhukov, V., Chetverikov, D. and Kato, K. (2013). Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors. Annals of Statistics 41 2786–2819.
  11. [11]Chernozhukov, V., Chetverikov, D. and Kato, K. (2015). Comparison and anti-concentration bounds for maxima of Gaussian random vectors. Probability Theory and Related Fields 162 47–70.
  12. [12]Chernozhukov, V., Chetverikov, D. and Kato, K. (2017a). Central limit theorems and bootstrap in high dimensions. Annals of Probability 45 2309–2352.
  13. [13]Chernozhukov, V., Chetverikov, D. and Kato, K. (2017b). Detailed proof of Nazarov’s inequality. arXiv:1711.10696.arxiv.org/abs/1711.10696
  14. [15]Chernozhukov, V., Chetverikov, D., Kato, K. and Koike, Y. (2022). Improved central limit theorem and bootstrap approximations in high dimensions. Annals of Statistics 50 2562–2586.arxiv.org/abs/1912.10529
  15. [17]Das, D. and Lahiri, S. N. (2021). Central limit theorem in high dimensions: the optimal bound on dimension growth rate. Transactions of the American Mathematical Society 374 6991–7009.arxiv.org/abs/2008.04389
  16. [18]Das, D. and Lahiri, S. N. (2025). Necessary and sufficient conditions for high dimensional central limit theorem under moment conditions. arXiv:2512.22312.arxiv.org/abs/2512.22312
  17. [19]Deng, H. and Zhang, C. H. (2020). Beyond Gaussian approximation: bootstrap for maxima of sums of independent random vectors. Annals of Statistics 48 3643–3671.arxiv.org/abs/1705.09528
  18. [20]Fang, X. and Koike, Y. (2021). High-dimensional central limit theorems by Stein’s method. Annals of Applied Probability 31 1660–1686.arxiv.org/abs/2001.10917
  19. [21]Fang, X. and Koike, Y. (2024). Sharp high-dimensional central limit theorems for log-concave distributions. Annales de l’Institut Henri Poincaré Probabilités et Statistiques 60 2129–2156.arxiv.org/abs/2207.14536
  20. [22]Fang, X., Koike, Y., Liu, S. H. and Zhao, Y. K. (2023). High-dimensional central limit theorems by Stein’s method in the degenerate case. Annals of Applied Probability, to appear. arXiv:2305.17365.arxiv.org/abs/2305.17365
  21. [23]Gao, Z. and Zhang, W. (2026). Cubic-root Gaussian approximation under unrestricted covariance. arXiv:2608.30221.arxiv.org/abs/2608.30221
  22. [24]Gilbarg, D. and Trudinger, N. S. (2001). Elliptic Partial Differential Equations of Second Order. Springer.
  23. [25]Heckman, J. J. and Honoré, B. E. (1990). The empirical content of the Roy model. Econometrica 58 1121–1149.DOI
  24. [26]Helffer, B. and Sjöstrand, J. (1994). On the correlation for Kac-like models in the convex case. Journal of Statistical Physics 74 349–409.DOI
  25. [27]Kock, A. B. and Preinerstorfer, D. (2024). A remark on moment-dependent phase transitions in high-dimensional Gaussian approximations. Statistics & Probability Letters 211 110149.arxiv.org/abs/2310.12863
  26. [28]Koike, Y. (2026). High-dimensional bootstrap and asymptotic expansion. Probability Theory and Related Fields 195 1051–1125.arxiv.org/abs/2404.05006
  27. [29]Koltchinskii, V. and Lounici, K. (2017). Concentration inequalities and moment bounds for sample covariance operators. Bernoulli 23 110–133.arxiv.org/abs/1405.2468
  28. [30]Kuchibhotla, A. K., Mukherjee, S. and Banerjee, D. (2021). High-dimensional CLT: improvements, non-uniform extensions and large deviations. Bernoulli 27 192–217.arxiv.org/abs/1806.06153
  29. [31]Kuchibhotla, A. K. and Rinaldo, A. (2020). High-dimensional CLT for sums of non-degenerate random vectors: n−1/2-rate. arXiv:2009.13673.arxiv.org/abs/2009.13673
  30. [32]Lopes, M. E. (2022). Central limit theorem and bootstrap approximation in high dimensions: near 1/√n rates via implicit smoothing. Annals of Statistics 50 2492–2513.
  31. [33]Lopes, M. E., Lin, Z. and Müller, H. G. (2020). Bootstrapping max statistics in high dimensions: near-parametric rates under weak variance decay and application to functional and multinomial data. Annals of Statistics 48 1214–1229.arxiv.org/abs/1807.04429
  32. [34]Lopes, M. E. and Yao, J. (2022). A sharp lower-tail bound for Gaussian maxima with application to bootstrap methods in high dimensions. Electronic Journal of Statistics 16 58–83.arxiv.org/abs/1809.08539
  33. [35]Mackey, L. and Gorham, J. (2016). Multivariate Stein factors for a class of strongly log-concave distributions. Electronic Communications in Probability 21 56. Corrected version: arXiv:1512.07392v6.arxiv.org/abs/1512.07392
  34. [36]Nazarov, F. (2003). On the maximal perimeter of a convex set in ℝⁿ with respect to a Gaussian measure. In Geometric Aspects of Functional Analysis 169–187. Springer.DOI
  35. [37]Pavliotis, G. A. (2014). Stochastic Processes and Applications: Diffusion Processes, the Fokker–Planck and Langevin Equations. Springer.DOI
  36. [38]Prékopa, A. (1973). On logarithmic concave measures and functions. Acta Scientiarum Mathematicarum (Szeged) 34 335–343.
  37. [39]Talagrand, M. (2011). Mean Field Models for Spin Glasses, Vol. 1. Springer.
  38. [40]Vershynin, R. (2018). High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press.
  39. [41]Zhivotovskiy, N. (2024). Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle. Electronic Journal of Probability 29 1–28.arxiv.org/abs/2108.08198

Paper details

vlnc:W_cs8skcwa
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents