Improved Central Limit Theorem and bootstrap approximations in high dimensions

Improved Central Limit Theorem and Bootstrap Approximations in High Dimensions

Introduction

Let $X_1,\dots,X_n$ be independent random vectors in $\mathbb R^p$ such that ${\mathrm{E}}[X_{i j}] = \mu_{j}$ for all $i=1,\dots,n$ and $j=1,\dots,p$, where $X_{i j}$ denotes the $j$th component of the vector $X_i$. We are interested in approximating the distribution of the maximum coordinate of the centered sample mean of $X_{1},\dots,X_{n}$, i.e.,

The distribution of $T_n$ plays a particularly important role in many high-dimensional settings, where $p$ is potentially larger or much larger than $n$. For example, it appears in selecting the regularization parameters for the Lasso estimator and the Dantzig selector (CCK13), in carrying out reality checks for data snooping and testing superior predictive ability (W00,H05), in constructing model confidence sets (HLN11), in testing conditional and/or many unconditional moment inequalities (BSS19, C18, CCK19, KB19), in multiple testing with the family-wise error rate control (BCCHK18), in constructing simultaneous confidence intervals for high-dimensional parameters (BCCW18), in adaptive testing of regression and stochastic monotonicity (C19,CWK18), in carrying out inference on generalized instrumental variable models (CR19), and in constructing Lepski-type procedures for adaptive estimation and inference in nonparametric problems (CCK14); more references can be found in DZ17 and especially in BCCHK18. It is therefore of great interest to develop methods for obtaining feasible and accurate approximations to the distribution of $T_n$, allowing for the high-dimensional $p \gg n$ case.

Toward this goal, the first three authors of this paper obtained the following Gaussian approximation result in CCK13, CCK17. Let $G = (G_1,\dots,G_p)'$ be a Gaussian random vector in $\mathbb R^p$ with mean $\mu = (\mu_1,\dots,\mu_p)'$ and covariance matrix $n^{-1}\sum_{i=1}^n{\mathrm{E}}[(X_i - \mu)(X_i - \mu)']$ and let the critical value $c_{1-\alpha}$ be the $(1-\alpha)$th quantile of $\max_{1\leq j\leq p}G_j$. Then under mild regularity conditions,

where $C$ is a constant that is independent of $n$ and $p$. This result is important because the right-hand side of the bound (ref) depends on $p$ only via the logarithm of $p$, and hence it shows that the Gaussian approximation holds if $\log p = o(n^{1/7})$, which allows $p$ to be much larger than $n$. Besides, building upon this result, the same authors have proved bounds similar to ((ref)) for the critical values obtained by the Gaussian multiplier and empirical bootstraps in CCK17.

Gaussian approximation of the form ((ref)) allows us to develop powerful inference methods for high-dimensional data in applications discussed above and has stimulated further developments into dependent data ZW17,ZC17,CCK19, $U$-statistics C18,CK19a,CK19b, Malliavin calculus C19, and homogeneous sums K19a. Despite such rapid developments, the literature has left much to be desired on coherent understanding of sharpness of the bound ((ref)) for the Gaussian or bootstrap critical values since the first appearance of CCK17 in 2014 on arXiv. The problem can be decomposed into two parts: (i) sharpness of the bound in terms of dependence on $n$ and (ii) sharpness of the bound in terms of dependence on $p$.

There are two important developments toward the question of sharpness of the bound ((ref)) that should be mentioned. First, Deng and Zhang DZ17 considered direct bootstrap approximation without taking the root of Gaussian approximation, and proved the following bound for the critical value $c_{1-\alpha}$ obtained by the empirical or third-order matching (or Mammen's M93) multiplier bootstraps:

Their bound improves the power of the logs in the previous bound ((ref)), showing that the empirical and Mammen's bootstraps are consistent to approximate the distribution of $T_{n}$ if $\log p = o(n^{1/5})$ instead of $\log p = o(n^{1/7})$. Second, the recent preprint by the fourth author K19b shows that the same bound ((ref)) indeed holds for the Gaussian critical value as well.

In turn, in this paper, we show that in fact a much larger improvement is possible: under mild regularity conditions, we prove that

both for the Gaussian and bootstrap critical values $c_{1-\alpha}$. In comparison with the Gaussian approximation result (ref), our new bound improves not only the power of the logs but also the power of the sample size $n$. Moreover, regarding the bootstrap types, we allow for not only the empirical and third-order matching multiplier bootstrap methods, but also for general multiplier bootstrap methods (with i.i.d weights), which match only two moments of the data, such as the multiplier bootstrap methods with Gaussian and Rademacher weights.

We remark that several authors have recently pointed out that an additional structural assumption on the covariance matrices of $X_i$'s can improve the bound (ref). In particular, Fang and Koike FK20 showed that the right-hand side of (ref) can be improved to $C(\log^4(pn)/n)^{1/3}$ when the covariance matrices are non-degenerate and can be further improved to $C(\log^3(p)/n)^{1/2}\log n$ when we additionally assume that $X_i$'s have log-concave densities. The latter result is based on the fact that random vectors with log-concave densities admit Stein kernels with sub-Weibull entries, which is established by Fathi in Fa19. Moreover, building on the important results by Lopes in L20 and Kuchibhotla and Rinaldo in KR20, CCK20 showed that the bound $C(\log^3(p)/n)^{1/2}\log n$ can be achieved even without the assumption of log-concave densities (non-degenerate covariance matrices are still required; L20 and KR20 were the first to obtain dependence on $n$ via $1/\sqrt n$ in (ref) without requiring log-concave densities). In addition, Lopes, Lin and M\"uller LLM20 showed that the right-hand side of (ref) can be improved to $C n^{-1/2+\delta}$ for any $\delta>0$ when the coordinates of $X_i$'s have decaying variances. Compared to these results, our bound requires neither non-degenerate covariance matrices nor decaying variances.

In addition, we prove that if the distribution of the random vectors $X_1,\dots,X_n$ is symmetric around the mean, then even better approximation to the distribution of $T_n$ is possible:

as long as the critical value $c_{1-\alpha}$ is obtained via the multiplier bootstrap method with Rademacher weights. This new bound makes Rademacher weights particularly appealing in the high-dimensional settings, at least from a theoretical perspective.

We also consider bootstrap approximations with incremental factors, previously used by Andrews and Shi in AS13 in the context of testing conditional moment inequalities. Specifically, for a small but fixed constant $\eta > 0$, called an incremental factor, we derive the following bounds:

if $c_{1-\alpha}$ is obtained via either the empirical or the third-order matching multiplier bootstrap methods and

if $c_{1-\alpha}$ is obtained via general multiplier bootstrap methods, where the constant $C$ may depend on $\eta$. Even though these are one-sided bounds, they are useful because they show that in any test based on the statistic $T_n$, increasing the critical value $c_{1-\alpha}$ by an incremental factor $\eta$ may substantially reduce the sample complexity for over-rejection. Namely, assuming $\log p \gtrsim \log n$ for simplicity, for the over-rejection probability to be less than or equal to a given level $0 < \Delta < 1-\alpha$, the empirical bootstrap or multiplier bootstrap (without incremental factor) requires $n \gtrsim \Delta^{-4} \log^5 p$, while adding a constant incremental factor reduces the sample complexity to $n \gtrsim (\Delta^{-2} \log^3p) \vee \log^5 p$ if we use the empirical or third-order matching bootstrap. It is worth noting that, given that in high-dimensional settings, where $p$ is rapidly increasing together with $n$, $c_{1-\alpha}$ is typically also getting large as we increase $n$, adding an incremental factor $\eta$ may not have a large impact on the power properties of the test.

In fact, all our results apply to a more general version of the statistic $T_n$:

where $a=(a_1,\dots,a_p)'$ is a vector in $\mathbb R^p$, which reduces to (ref) if we set $a = 0_p$. In most applications mentioned above, the former version (ref) is sufficient but there are some applications where the more general version (ref) is required; for example, the latter was used by Bai, Shaikh, and Santos in BSS19 to extend the method of testing moment inequalities proposed in RSW14 for the case of a small number of inequalities to the case of a large number of inequalities. For the rest of the paper, we will therefore work with the more general version (ref) of the statistic $T_n$. In addition, we emphasize that our results can be equally applied with $$ T_n = \max_{1\leq j\leq p}\left|\frac{1}{\sqrt n}\sum_{i=1}^n(X_{i j} - \mu_j + a_j)\right| $$ by replacing the $p$-dimensional vectors $X_i - \mu + a$ with the $2p$-dimensional vectors whose first $p$ components are equal to $X_i - \mu + a$ and the last $p$ components are equal to $-(X_i - \mu + a)$.

To prove (ref), we develop a novel and iterative version of the randomized Lindeberg method. A key feature of our approach is that we carry out a careful analysis of the coefficients in the Taylor expansion underlying the Lindeberg method. In particular, we apply the Lindeberg method iteratively in combination with an anti-concentration inequality for maxima of Gaussian processes to bound these coefficients, which substantially improves upon the original randomized Lindeberg method proposed in DZ17. In addition, we sharpen the Gaussian approximation bounds for the multiplier processes developed in K19b using Stein's kernels. In turn, to prove (ref), we establish a new connection between the Rademacher bootstrap and the randomization tests, as discussed in LR05, using a recent result from the computer science literature on pseudo-random number generators by O'Donnell, Servedio, and Tan OST18, which provides an anti-concentration inequality for maxima of Rademacher processes. Finally, to prove error bounds (ref) and (ref), we apply the original randomized Lindeberg method as developed in DZ17.

Finally, we conduct a small scale simulation study. Our simulation study shows that (i) all bootstrap methods considered in this paper perform reasonably well in high dimensions; (ii) for asymmetric distributions, the empirical and the third-order matching multiplier bootstrap methods outperform the multiplier bootstrap methods with Gaussian and Rademacher weights; and (iii) for symmetric distributions, the multiplier bootstrap with Rademacher weights performs the best, which is consistent with Theorem (ref) ahead. See the Supplementary Material for details.

The rest of the paper is organized as follows. In the next section, we present our main results. In Section (ref), we develop the iterative randomized Lindeberg method, which is the first key component in deriving our main results. In Section (ref), we provide new bounds for the Gaussian approximations using Stein's kernels, which is the second key component in deriving our main results. In Section (ref), we give proofs of the main results. In the Supplemental Material, we collect additional derivations and conduct a small simulation study.

Notation

For any vectors $x,y\in\mathbb R^p$ and any scalar $c\in\mathbb R$, we write $x\leq y$ if $x_j \leq y_j$ for all $j=1,\dots,p$ and write $x + c$ to denote the vector in $\mathbb R^p$ whose $j$th component is $x_j + c$ for all $j = 1,\dots,p$. Also, for any sequences of scalars $\{a_n\}_{n\geq 1}$ and $\{b_n\}_{n\geq 1}$ we write $a_n\lesssim b_n$ if $a_n \leq C b_n$ for all $n\geq 1$ for some constant $C$. Recall that, for any random variable $T$ and a constant $\gamma\in(0,1)$, the $\gamma$th quantile of $T$ is defined as $\inf\{t\in\mathbb R\colon {\mathrm{P}}(T\leq t) \ge \gamma \}$. Finally, we use the notation $X_{1:n} = (X_1,\dots,X_n)$.

Main Results

In this section, we present our main results. We first formally define all the critical values $c_{1-\alpha}$ to be used throughout the paper. We then discuss the required regularity conditions and present the results.

Gaussian and Bootstrap Critical Values

First, define the Gaussian critical value $c_{1-\alpha}^G$ as the $(1-\alpha)$th quantile of

where $G$ is a centered Gaussian random vector in $\mathbb R^p$ with the covariance matrix

which coincides with the covariance matrix of $\sqrt{n}(\bar{X}_n-\mu)$. Second, define the bootstrap critical value $c_{1-\alpha}^B$ as the $(1-\alpha)$th quantile of the conditional distribution of

given the data $X_1,\dots,X_n$, where $X_1^*,\dots,X_n^*$ is a (not necessarily empirical) bootstrap sample. We consider the following types of the bootstrap:

For the multiplier bootstrap, we will assume throughout the paper that the weights $e_1,\dots,e_n$ are such that

Condition ((ref)) is mild and covers many commonly used weights, such as:

See Remark (ref) for further discussion on Condition ((ref)).

Occasionally, we will also consider the weights with unit third moment, namely,

The weights satisfying Condition ((ref)) correspond to the third-order matching multiplier bootstrap mentioned in the Introduction. We note that Mammen's weights satisfy both Conditions ((ref)) and ((ref)), but neither Rademacher nor Gaussian weights satisfy Condition (ref). See Lemma (ref) in the Supplemental Material, where we provide a more general class of distributions for the weights satisfying both Conditions (ref) and (ref).

Before proceeding to the regularity conditions, we also note that the multiplier bootstrap critical value $c_{1-\alpha}^B$ with Gaussian weights can be regarded as a feasible version of the Gaussian critical value $c_{1-\alpha}^G$. Indeed, it is easy to see that the former can be alternatively defined as the $(1-\alpha)$th quantile of the distribution of $$ T_n^{\hat G} = \max_{1\leq j\leq p}(\hat G_j + a_j),$$ where $ \hat G\sim N(0_p,\widehat\Sigma_n)$ and $\widehat \Sigma_{n}$ is the empirical covariance matrix

For brevity, we sometimes refer to both quantities as the Gaussian critical values.

Regularity Conditions

First, observe that given the construction of the statistic $T_n$ in (ref) and its Gaussian and bootstrap analogs in (ref) and (ref), it is without loss of generality to assume that $\mu_{j} = 0$ for all $j = 1,\dots,p$, which is what we do for the rest of the paper. Also, all our results follow immediately if $n= 2$, so we assume $n\geq 3$, which in particular implies $\log(p n)\geq 1$. In addition, since we are primarily interested in the case with large $p$, we assume $p\geq 2$.

Second, let $b_1$ and $b_2$ be some strictly positive constants such that $b_1\leq b_2$ and let $\{B_n\}_{n\geq 1}$ be a sequence of constants such that $B_n \geq 1$ for all $n\geq 1$. Here, the sequence $\{B_n\}_{n\geq 1}$ can diverge to infinity as the sample size $n$ increases.

{\bf Condition E:} {\em For all $i=1,\dots,n$ and $j = 1,\dots,p$, we have \[ {\mathrm{E}}[\exp(|X_{i j}|/B_n)]\leq 2. \] }

{\bf Condition M:} {\em For all $j=1,\dots,p$, we have $$ b_1^2\leq \frac{1}{n}\sum_{i=1}^n {\mathrm{E}}[X_{i j}^2]\quad\text{and}\quad \frac{1}{n}\sum_{i=1}^n {\mathrm{E}}[X_{i j}^4]\leq B_n^2 b_2^2. $$ }

{\bf Condition S:} {\em For all $i=1,\dots,n$, the distribution of $X_i$ is symmetric in the sense that $X_i$ and $-X_i$ are identically distributed.}

Condition E implies that the random variables $X_{i j}$ are sub-exponential with the Orlicz $\psi_1$-norm bounded by $B_n$; see V11 for details. The same sub-exponential condition was assumed in e.g. CCK17 and DZ17; see Condition (E.1) in CCK17 and (E.1) in DZ17. The first part of Condition M, which we refer to as the variance lower bound condition, requires that each component of the random vectors $X_i$ is scaled properly. The variance lower bound condition is needed to apply the anti-concentration inequalities (cf. Lemmas (ref) and (ref) in the Supplemental Material) but can be dropped in Theorem (ref) ahead. Also, at least for Theorems (ref) and (ref), it can be relaxed by using Theorem 10 in DZ17. However, to consistently state all the results, we work with the present assumption. Given the first part, the second part of Condition M holds if, for example, all random variables $X_{i j}$ are bounded by $B_n$ and $n^{-1}\sum_{i=1}^n{\mathrm{E}}[X_{ij}^2]\leq b_2^2$ for all $j=1,\dots,p$. Condition S means that the distribution of each $X_i$ is symmetric around the mean. Importantly, none of these conditions restrict the correlation matrices of $X_i$, and so our results do not follow from the classical results in empirical process theory.

In what follows, we will always maintain Conditions E and M and will assume Condition S only in Theorem (ref), which shows that imposing the symmetric distributions improves the approximation bound for the multiplier bootstrap with Rademacher weights.

Main Results

We first present a non-asymptotic bound on the error of the Gaussian approximation to the distribution of the statistic $T_n$:

This result improves upon the bound in K19b, who obtained a similar result with the rate $1/6$ instead of $1/4$. Since $a\in\mathbb R^p$ in the definition of $T_n$ in (ref) is arbitrary, the bound (ref) can be equivalently stated as $$ \sup_{A\in\mathcal A}\left|{\mathrm{P}}\left(\frac{1}{\sqrt n}\sum_{i=1}^n X_i \in A\right) - {\mathrm{P}}(G\in A)\right|\leq C\left(\frac{B_n^2\log^5(p n)}{n}\right)^{1/4}, $$ where $G\sim N(0_p,\Sigma_n)$ and $\mathcal A$ is the class of all hyper-rectangles in $\mathbb R^p$, i.e. sets of the form $$ A = \Big\{ w = (w_1,\dots,w_p)'\in\mathbb R^p\colon a_{lj} \leq w_j \leq a_{rj}\text{ for all }j=1,\dots,p \Big\}, $$ for some constants $-\infty\leq a_{lj} \leq a_{rj} \leq \infty$ with $j=1,\dots,p$. This gives a quantitative Central Limit Theorem (CLT) over the hyper-rectangles in high dimensions.

The proof of Theorem (ref), which is deferred to Section (ref), is fairly complicated and goes somewhat backward: (i) we first compare the conditional distribution of a third-order matching bootstrap statistic $T_n^*$ with that of the Gaussian multiplier bootstrap statistic $T_n^{\hat{G}}$, and then compare the conditional distribution of $T_n^{\hat{G}}$ with the distribution of $T_n^G$. These two comparisons rely on the Gaussian approximation via Stein kernel (Theorem (ref)). Then, (ii) we use the preceding comparison between $T_n^*$ and $T_n^{G}$ to verify the anti-concentration for $T_n^*$ to invoke Theorem (ref) and compare the conditional distribution of $T_n^*$ with the distribution of $T_n$. The proof of Theorem (ref) relies on a novel technique which we call the iterative randomized Lindeberg method. The conclusion of Theorem (ref) follows from combining the results in Steps (i) and (ii) and the triangle inequality.

Comparison of the the Gaussian multiplier bootstrap statistic $T_n^{\hat{G}}$ with $T_n^G$ relies on the following Gaussian-to-Gaussian comparison inequality, which can be of independent interest and whose proof is presented in Section (ref) as a consequence of Theorem (ref):

Comparison of the conditional distribution of the third-order matching bootstrap statistic $T_n^*$ with that of $T_n$ (Theorem (ref)) relies on the iterative randomized Lindeberg method. An intuition behind the iterative randomized Lindeberg method goes as follows. Recall that, for any smooth function $g\colon\mathbb R^p\to\mathbb R$ and any two sequences of independent random vectors $X_1,\dots,X_n$ and $Y_1,\dots,Y_n$ in $\mathbb R^p$, in order to approximate ${\mathrm{E}}[g(X_1+\dots+X_n)]$ by ${\mathrm{E}}[g(Y_1+\dots+Y_n)]$, the original Lindeberg method constructs an interpolation path from ${\mathrm{E}}[g(X_1+\dots+X_n)]$ to ${\mathrm{E}}[g(Y_1+\dots+Y_n)]$ by replacing $X_i$'s with $Y_i$'s one-by-one in a given order and uses Taylor's expansion to show that the change in the expectation at each step is sufficiently small; see C06 for example. The randomized Lindeberg method, introduced in DZ17, is similar to the original Lindeberg method but it replaces $X_i$'s with $Y_i$'s in a randomly selected order. It turns out that this randomization may bring substantial benefits to the final bound. In turn, to improve upon this version of the randomized Lindeberg method, we carry out a careful analysis of the coefficients in the Taylor's expansions underlying the method. In particular, given that $k$th order coefficients take the form of ${\mathrm{E}}[g^{(k)}(Z_1+\dots+Z_n)]$, up to some approximation error, where $g^{(k)}$ is a vector of the $k$th partial derivatives of $g$ and $Z_1,\dots,Z_n$ is a sequence such that some of its elements are given by $X_i$'s and others by $Y_i$, and using the fact that it is easier in our setting to bound ${\mathrm{E}}[g^{(k)}(Y_1+\dots+Y_n)]$, we apply the randomized Lindeberg method once again to approximate ${\mathrm{E}}[g^{(k)}(Z_1+\dots+Z_n)]$ by ${\mathrm{E}}[g^{(k)}(Y_1+\dots+Y_n)]$. Here, since a new application of the method will bring new Taylor's coefficients, we apply the same method over and over again until the approximation error becomes sufficiently small. We demonstrate that this iterative use of the randomized Lindeberg method gives further substantial benefits to the final bound. See also the discussion before Lemma (ref) concerning comparisons of the iterative randomized Lindeberg method with the randomized Lindeberg method used in DZ17 and the related Slepian-Stein method used in our earlier work CCK13,CCK17.

Our second main result gives a non-asymptotic bound on the deviation of the bootstrap rejection probabilities ${\mathrm{P}}(T_n > c_{1-\alpha}^B)$ from the nominal level $\alpha$ for the empirical and the multiplier bootstrap methods:

This theorem improves upon the bounds in DZ17, who obtained a similar result with the rate $1/6$ instead of $1/4$. In addition, we allow for a larger class of multiplier bootstrap methods. In particular, we do not require the weights $e_1,\dots,e_n$ to satisfy (ref). The proof of this theorem is given in Section (ref).

Our third main result gives a non-asymptotic bound on the deviation of the bootstrap rejection probabilities from the nominal level for the multiplier bootstrap method with Rademacher weights in the case of symmetric distributions:

This theorem implies that the multiplier bootstrap with Rademacher weights is very accurate in the symmetric case. To prove it, we note that under the assumption of symmetric distributions, one can construct the randomization critical value $c_{1-\alpha}^R$ such that ${\mathrm{P}}(T_n > c_{1-\alpha}^R) = \alpha$, up to possible mass points in the distribution of $T_n$. Thus, given that the critical value based on the multiplier bootstrap with Rademacher weights turns out to be a feasible version of this randomization critical value and the two are close to each other, (ref) follows if we can show that the distribution of $T_n$ is not too concentrated. To this end, we use an anti-concentration inequality for maxima of Rademacher processes derived in OST18. The proof of Theorem (ref) is given in Appendix (ref) of the Supplemental Material.

Our fourth and final result shows that one-sided bounds in the bootstrap approximation can be substantially improved if we allow for incremental factors:

Theorem (ref) allows $\eta$ to (slowly) decrease with $n$ and/or $p$. For example, if we choose $\eta \sim (\log n)^{-1}$, then the over-rejection probability is of order $n^{-1/2}$ in $n$ up to log factors, while only requiring $p$ to be $\log p = o\big(n^{1/3}/\text{polylog} (n)\big)$ in (i) and $\log p = o\big(n^{1/5}/\text{polylog}(n)\big)$ in (ii) provided that $B_n$ is bounded in $n$.

To prove this theorem, we use the randomized Lindeberg method but with an important simplification that the incremental factor $\eta$ now absorbs all the terms arising from smoothing the functions of the form $x\mapsto 1\{\max_{1\leq j\leq p}x_j > c\}$, which is used in the Lindeberg method. As discussed in the Introduction, Theorem (ref) is useful if one is concerned with the finite-sample over-rejection of tests based on the statistic $T_n$ as it says that adding an incremental factor $\eta$ to the critical value $c_{1-\alpha}^B$ may substantially reduce over-rejection, with a minimal effect on the power of the test. The proof of Theorem (ref) is given in Appendix (ref) of the Supplemental Material.

We conclude this section with a few remarks on cases with approximate sample means. In many applications (such as simultaneous inference for high-dimensional statistical models; cf. BCK15), the statistic $T_n$ can only be asymptotically approximated by the maximum coordinate of the sample mean of independent random vectors. Also, those random vectors, often corresponding to the influence functions, may not be directly observable but have to be estimated. We emphasize here that all our results can be extended to such approximate sample mean cases using the same arguments as those used in BCCHK18; however, we have opted not to carry out the extension here for brevity of the paper.

Gaussian and Bootstrap Approximations under Polynomial Moment Conditions

So far we have assumed the sub-exponential condition (Condition E) for $X_i$. It turns out that combining some elements of the proof of Lemma (ref) below and a truncation argument leads to analogs of the Gaussian and bootstrap approximation results under polynomial moment conditions, which are given next. The proofs of Theorems (ref) and (ref) can be found in Appendix (ref) in the Supplementary Material.

This theorem improves on the corresponding result obtained by K19b by the fourth author. For bootstrap approximation, we focus on the Gaussian multiplier and empirical bootstraps for simplicity.

This theorem improves on the error bound for the empirical bootstrap given in DZ17 under the polynomial moment condition.

Main Theoretical Arguments

Iterative Randomized Lindeberg Method

In this section, we derive a distributional approximation result, Theorem (ref), using a novel proof technique, which we call the iterative randomized Lindeberg method. We will use this result in Section (ref) to prove our main results on the Gaussian and bootstrap approximations in high dimensions, as stated in Section (ref).

Let $V_1,\dots,V_n, Z_1,\dots,Z_n$ be a sequence of independent random vectors in $\mathbb R^p$ such that ${\mathrm{E}}[V_{i j}] = {\mathrm{E}}[Z_{i j}] = 0$ for all $i = 1,\dots,n$ and $j = 1,\dots,p$, where $V_{i j}$ and $Z_{i j}$ denote the $j$th components of $V_{i j}$ and $Z_{i j}$, respectively. We will assume that these vectors obey the following conditions:

{\bf Condition V:} {\em There exists a constant $C_v>0$ such that for all $j = 1,\dots,p$, we have $$ \frac{1}{n}\sum_{i=1}^n{\mathrm{E}}\left[V_{i j}^4 + Z_{i j}^4\right] \leq C_v B_n^2. $$

} {\bf Condition P:} {\em There exists a constant $C_p\geq 1$ such that for all $i = 1,\dots,n$, we have $$ {\mathrm{P}}\Big(\|V_i\|_{\infty}\vee\|Z_i\|_{\infty} > C_p B_n\log(p n)\Big) \leq 1/n^4. $$

} {\bf Condition B:} {\em There exists a constant $C_b>0$ such that for all $i = 1,\dots,n$, we have $$ {\mathrm{E}}\Big[\|V_i\|_{\infty}^8 + \|Z_i\|_{\infty}^8\Big]\leq C_bB_n^8\log^8(p n). $$

} {\bf Condition A:} {\em There exist constants $C_a > 0$ and $\delta\geq0$ such that for all $(y,t)\in\mathbb R^p\times (0,\infty)$, we have $$ {\mathrm{P}}\left(\frac{1}{\sqrt n}\sum_{i=1}^n Z_i \leq y + t \right) - {\mathrm{P}}\left(\frac{1}{\sqrt n}\sum_{i=1}^n Z_i \leq y\right) \leq C_a\left(t\sqrt{\log p}+\delta\right). $$}

Note that the constants $C_v$, $C_p$, $C_b$, and $C_a$ appearing in these conditions are not supposed to be dependent on their indices, e.g. $C_p$ here is not allowed to change with $p$; the indices are introduced with the only goal to differentiate between the constants.

The following is the main result of this section:

To prove this result, we will need additional notation. For all $\epsilon\in\{0,1\}^n$, define

where $$ S_{n,\epsilon}^V = \frac{1}{\sqrt n}\sum_{i=1}^n (\epsilon_iV_i + (1 - \epsilon_i)Z_i)\quad\text{and}\quad S_n^Z = \frac{1}{\sqrt n}\sum_{i=1}^n Z_i. $$ We will replace $\epsilon$ with a certain sequence of random vectors $\epsilon^0,\dots,\epsilon^D \in \{ 0,1 \}^n$, independent of $V_1,\dots,V_n,Z_1,\dots,Z_n$, and derive recursive bounds for $\rho_{\epsilon^d}$ for $d=0,\dots,D$, which lead to the desired bound in Theorem (ref). Such a sequence of random vectors $\epsilon^0,\dots,\epsilon^D \in \{ 0,1 \}^n$ is constructed as follow:

It is not difficult to see that for each $d=1,\dots,D$, the random vector $\epsilon^d$ satisfies the following properties:

Indeed, to see that ((ref)) holds, observe that, conditional on $\epsilon^{d-1}$ and $U_d$, $\sum_{i \in I_{d-1}} \epsilon_i^d$ follows the binomial distribution with parameters $|I_{d-1}|$ and (success probability) $U_d$, so that \[

\] Also, two properties (i) and (ii) ensure that $S_{n,\epsilon^d}^V-n^{-1/2}\sum_{i\notin I_{d-1}}Z_i$ is the randomized Lindeberg interpolant between $n^{-1/2}\sum_{i\in I_{d-1}}V_i$ and $n^{-1/2}\sum_{i\in I_{d-1}}Z_i$; see Lemma (ref) and the discussion at the beginning of Step 1 of the proof of Lemma (ref).

Further, for all $i=1,\dots,n$ and $j,k,l = 1,\dots,p$, define $$ \mathcal E_{i, j k}^V = {\mathrm{E}}[V_{i j}V_{i k}], \ \mathcal E_{i, j k l}^V = {\mathrm{E}}[V_{i j} V_{i k}V_{i l}], $$ $$ \mathcal E_{i, j k}^Z = {\mathrm{E}}[Z_{i j}Z_{i k}], \ \mathcal E_{i, j k l}^Z = {\mathrm{E}}[Z_{i j} Z_{i k}Z_{i l}]. $$ For all $n\geq 1$ and $d = 0,\dots,D$, let $\mathcal B_{n,1,d}$ and $\mathcal B_{n,2,d}$ be some strictly positive constants, and define the event $\mathcal A_d$ by \[

\]

The proof of Theorem (ref) proceeds as follows. In Lemma (ref) and Corollary (ref), we establish a recursive inequality for ${\mathrm{E}}[\varrho_{\epsilon^d}1\{\mathcal A_d\}]$, $d=0,\dots,D$. Next, we show in Lemma (ref) that ${\mathrm{E}}[\varrho_{\epsilon^D}1\{\mathcal A_D\}]$ is bounded by $1/n$. Then, we use an induction argument backward to derive a bound for ${\mathrm{E}}[\varrho_{\epsilon^0}1\{\mathcal A_0\}]$. Since $\epsilon^0_i=1$ for all $i$, this gives the claim of the theorem once we appropriately choose the constants $\mathcal B_{n,1,d}$ and $\mathcal B_{n,2,d}$. The proof of Lemma (ref) is long and is given in Appendix (ref) of the Supplemental Material.

The derivation of the recursive inequality is based on connecting $S_{n,\epsilon^d}^V$ with $S_n^Z$ by the randomized Lindeberg method originally developed by DZ17. A similar approach was used in CCK13,CCK17 to connect $S_{n,\epsilon^0}^V$ with $G$, where the Slepian--Stein method was applied instead. Unlike the latter approach, the randomized Lindeberg method allows us to match the moments of $S_{n,\epsilon^d}^V$ and $S_n^Z$ up to the third order rather than the second order. This leads to improvement on the power of $\log(pn)$ factors. In addition, we incorporate a smoothing effect induced by $Z_i$ via Condition A into our argument. This along with the higher-order moment matching lead to improvement on the power of the sample size $n$.

Stein Kernels and Gaussian Approximation

Let $C_b^2(\mathbb R^p)$ be the class of twice continuously differentiable functions $\varphi$ on $\mathbb R^p$ such that $\varphi$ and all its partial derivatives up to the second order are bounded where $p\geq 2$. Let $V$ be a centered random vector in $\mathbb R^p$ and assume that there exists a measurable function $\tau:\mathbb R^p\to\mathbb R^{p\times p}$ such that $$ \sum_{j=1}^p{\mathrm{E}}[\partial_j \varphi(V)V_j] = \sum_{j,k=1}^p{\mathrm{E}}[\partial_{jk}\varphi(V)\tau_{jk}(V)] $$ for all $\varphi\in C_b^2(\mathbb R^p)$. This function $\tau$ is called a Stein kernel for the random vector $V$. Also, let $Z$ be a centered Gaussian random vector in $\mathbb R^p$ with covariance matrix $\Sigma$.

Theorem (ref) is proven in Appendix (ref) of the Supplemental Material. It has two important corollaries. The first is Proposition (ref), a sharp Gaussian-to-Gaussian comparison inequality stated in Section (ref):

Second, combining Theorem (ref) with Lemma 4.6 in K19b gives the following result:

Proofs of Theorems (ref) and (ref)

In this section, we provide proofs of Theorems (ref) and (ref). Proofs of Theorems (ref) and (ref) will be given in Appendices (ref) and (ref) of the Supplemental Material. To simplify notation, we write \[ \delta_n=\left(\frac{B_n^2\log^5(pn)}{n}\right)^{1/4}\quad\text{and}\quad \upsilon_n=\sqrt{\frac{B_n^2\log^3(pn)}{n}}. \]

Our proof strategy for Theorems (ref) and (ref) is summarized as follows. First, we consider the multiplier bootstrap statistic $T_n^*$ with the weights $e_i$ constructed from the standardized Beta($\alpha$,$\beta$) distribution and parameters $\alpha$ and $\beta$ chosen so that ${\mathrm{E}}[e_i^3] = 1$. Thanks to Corollary (ref) and Proposition (ref), we have Gaussian approximation to this statistic with the rate $\delta_n$. This implies that Condition A in Section (ref) is satisfied with $Z_i=e_i(X_i-\bar X_n)$ and $\delta=\delta_n$ due to the Gaussian anti-concentration inequality in Lemma (ref) of the Supplemental Material. In turn, the latter allows us to invoke Theorem (ref), which gives the approximation to $T_n$ by $T_n^*$ with the rate $\delta_n$. (Note that having ${\mathrm{E}}[e_i^3]=1$ is important here since otherwise Theorem (ref) would give a slower approximation rate.) Combining this result with the aforementioned Gaussian approximation for $T_n^*$, we obtain the Gaussian approximation for $T_n$ with the rate $\delta_n$. This is done in Lemma (ref) and gives Theorem (ref).

Second, we consider the empirical bootstrap statistic $T_n^*$. Since we now have the Gaussian approximation for $T_n$ with the rate $\delta_n$, it follows that Condition A is satisfied with $Z_i=X_i$ and $\delta=\delta_n$. Hence, applying Theorem (ref) with $V_i=X^*_i$ and $Z_i=X_i$, we can verify the empirical bootstrap approximation for $T_n$ with the rate $\delta_n$. This is done in Lemma (ref) and gives one part of Theorem (ref).

Third, we consider the multiplier bootstrap statistic $T_n^*$ with arbitrary weights $e_i$ satisfying (ref). By choosing parameters $\alpha$ and $\beta$ appropriately, we can match the first three moments of these weights by weights constructed from the standardized Beta($\alpha$,$\beta$) distribution. Thus, yet another application of Theorem (ref) allows us to link the distribution of any multiplier bootstrap statistic to the distribution of the multiplier bootstrap statistic with weights constructed from the standardized Beta($\alpha$,$\beta$) distribution and further, via Corollary (ref) and Proposition (ref), to the Gaussian distribution. This leads to the Gaussian approximation for the multiplier bootstrap statistic $T_n^*$ with the rate $\delta_n$. This is done in Lemma (ref) and gives the other part of Theorem (ref).

Before proceeding to the main body of the proofs, we present a few auxiliary results.

The proof of this lemma is rather standard but long, and so is deferred to Appendix (ref) of the Supplemental Material.

We are now in the position to prove the main results from Section (ref).

\centerline{{Supplementary Material}}