Strong uniform laws of large numbers for bootstrap means and other randomly weighted sums

The bootstrap (Efron and Tibshirani, 1994) and related resampling procedures such as bagging (Breiman, 1996), the Bayesian bootstrap (Rubin, 1981), and the jackknife (Efron, 1982) are widely used general-purpose tools for statistical inference. In addition to its original purpose of approximating sampling distributions of estimators (Efron, 1979), the bootstrap and its relatives have been applied to a variety of statistical tasks, including model averaging (Breiman, 1996), approximate Bayesian inference (Newton and Raftery, 1994), outlier detection (Singh and Xie, 2003), robust Bayesian inference (Huggins and Miller, 2019, 2022), and causal inference (Little and Badawy, 2019).

Due to its versatility, extensions of the bootstrap are frequently proposed to address new statistical questions. When establishing the properties of such methods, bootstrap versions of classical asymptotic results play a key role, such as the weak law of large numbers (Athreya et al., 1984, Theorem 1), the strong law of large numbers (Athreya et al., 1984, Theorem 2), and the central limit theorem (Singh, 1981) for bootstrap means.

Meanwhile, it is sometimes important to obtain convergence over an entire collection of random variables simultaneously, thus guaranteeing convergence for even the worst case in the collection. To this end, several authors have established uniform laws of large numbers for bootstrap means. Giné and Zinn (1990, Theorems 2.6 and 3.5) proved weak uniform laws of large numbers for the standard multinomial bootstrap, that is, with $\mathrm{Multinomial}\big{(}n,(1/n,\ldots,1/n))$ weights. Vaart and Wellner (1996, Theorem 3.6.16) proved an analogous result for exchangeably weighted sums such as the Bayesian bootstrap. As weak laws, these show convergence in probability, but often one needs almost sure convergence, that is, a strong law.

Strong uniform laws of large numbers for bootstrap means are provided by Kosorok (2008, Section 10.2) for weighted sums with independent and identically distributed (i.i.d.) weights, with weights obtained by normalizing $n$ i.i.d. random variables, and with $\mathrm{Multinomial}\big{(}n,(1/n,\ldots,1/n))$ weights (Theorem 10.13, Corollary 10.14, and Theorem 10.15, respectively). However, these results do not apply to more general schemes such as the jackknife, resampling without replacement, and $\mathrm{Multinomial}\big{(}m_{n},(p_{n1},\ldots,p_{nn}))$ weights.

In this article, we present new strong uniform laws of large numbers for randomly weighted sums, aiming to fill these gaps in the literature. Our first result applies to the case of $\mathrm{Multinomial}\big{(}m_{n},(1/n,\ldots,1/n))$ weights, known as the $m$-out-of-$n$ bootstrap. Our second and third results apply more generally to a large class of randomly weighted sums that involve negatively orthant dependent (NOD) weights. This covers a wide range of weighting schemes, including the Bayesian bootstrap (Rubin, 1981), various versions of the jackknife (Efron, 1982; Chatterjee and Bose, 2005), resampling without replacement (Bickel et al., 2012), simple random sampling with over-replacement (Antal and Tillé, 2011b), $\mathrm{Multinomial}\big{(}m_{n},(p_{n1},\ldots,p_{nn}))$ weights (Antal and Tillé, 2011a, Section 3), independent weights (Newton and Raftery, 1994), and even schemes involving negative weights such as multivariate Gaussian weights with non-positive correlations (Patak and Beaumont, 2009). All three theorems are flexible in terms of the effective bootstrap sample size $m_{n}$ (that is, the sum of the weights), for instance, allowing $m_{n}=o(n)$ which is of particular interest for certain applications (Bickel et al., 2012; Huggins and Miller, 2022).

The article is organized as follows. We present our main results in Section 2, Section  provides some examples of relevant re-weighting schemes, and the proofs of the main results are provided in Section 4.

We present three strong uniform laws of large numbers: Theorem 1 for the multinomial bootstrap, Theorem 2 for more general randomly weighted sums, and Theorem 3 which establishes faster convergence rates under stronger regularity and moment conditions than Theorem 2. All three results are obtained via extensions of the proof of the i.i.d. strong uniform law of large numbers presented by Ghosh and Ramamoorthi (2003). Specifically, our proof of Theorem 1 involves replacing the traditional strong law of large numbers with a strong law of large numbers for bootstrap means as presented by Arenal-Gutiérrez et al. (1996). Similarly, Theorems 2 and 3 rely on a strong law of large numbers for randomly weighted sums of random variables presented by Chen et al. (2019).

In Theorems 2 and 3, we generalize beyond the standard multinomial bootstrap to weighting schemes involving NOD random variables (Lehmann, 1966; Chen et al., 2019).

Any collection of independent random variables is NOD, and many commonly used multivariate distributions are NOD including the multinomial distribution, the Dirichlet distribution, the Dirichlet-multinomial distribution, the multivariate hypergeometric distribution, convolutions of multinomial distributions, and multivariate Gaussian distributions for which the correlations are all non-positive (Joag-Dev and Proschan, 1983).

In particular, if $n^{-1/p}\sum_{j=1}^{n}\mathbb{E}(W_{nj})\to 1$, then Equation 5 is analogous to Equation 2 with $n^{1/p}$ in place of $m_{n}$. While the moment condition on $H(\theta,X_{1})$ in Theorem 2 is slightly more stringent than in Theorem 1, it applies to a more general class of resampling procedures. For instance, the distribution of $W_{nj}$ can be different for each $n$ and $j$; in particular, there is no assumption that $W_{n1},\ldots,W_{nn}$ are exchangeable or even identically distributed. Further, the weights $W_{nj}$ are not restricted to being non-negative; thus, random weights taking positive and negative values are permitted.

The main limitation of Theorem 2 is that whenever $p>1$, the condition that $\sum_{j=1}^{n}\mathbb{E}(|W_{nj}|)=O(n^{1/p})$ requires the weights to be getting smaller as $n$ increases. One can scale the weights up by a factor of $n^{1-1/p}$, but then the leading factor of $1/n^{1/p}$ in Equation 5 becomes $1/n$, effectively reverting back to the standard rate of convergence. In Theorem 3, we show that this condition can be dropped if we assume stronger regularity and moment conditions.

Condition 3 holds for any compact $\Theta\subset\mathbb{R}^{D}$; indeed, by Shalev-Shwartz and Ben-David (2014, Example 27.1), $N_{1}(r)\leq c_{1}r^{-D}$ where $N_{1}(r)$ is the number of $r$-balls needed to cover $\Theta$, centered at any points in $\mathbb{R}^{D}$, and it is straightforward to verify that $N(r)\leq N_{1}(r/2)$.

Note that as $p\to 1$ from above, the bound on the power $q$ approaches $2$.

A key condition of Theorems 2 and 3 is that the weights $W_{n1},\ldots,W_{nn}$ must be NOD. It turns out that most popular resampling techniques satisfy this condition.

For instance, the $m$-out-of-$n$ bootstrap corresponds to $\mathrm{Multinomial}\big{(}m_{n},(1/n,\ldots,1/n))$ weights, unequal probability with replacement corresponds to $\mathrm{Multinomial}\big{(}m_{n},(p_{n1},\ldots,p_{nn}))$ weights (Antal and Tillé, 2011a), the Bayesian bootstrap corresponds to Dirichlet weights, the delete-$d$ jackknife and resampling without replacement correspond to multivariate hypergeometric weights (Chatterjee and Bose, 2005), the weighted likelihood bootstrap is equivalent to using independent weights (Newton and Raftery, 1994), and the reweighting scheme of Patak and Beaumont (2009) employs multivariate Gaussian weights with non-positive correlations. All of these distributions satisfy the NOD requirement (Joag-Dev and Proschan, 1983).

The NOD requirement is also satisfied by less standard reweighting schemes such as the downweight-$d$ jackknife (Chatterjee and Bose, 2005) and simple random sampling with over-replacement (Antal and Tillé, 2011b). In the downweight-$d$ jackknife, $d$ indices $i_{1},\ldots,i_{d}$ are selected uniformly at random to be downweighted such that $W_{ni_{1}}=\cdots=W_{ni_{d}}=d/n$, whereas the remaining $n-d$ indices are upweighted to $1+d/n$. These weights can be viewed as a monotonic transformation of the multivariate hypergeometric weights corresponding to the delete-$d$ jackknife, and thus are NOD (Chen et al., 2019). For simple random sampling with over-replacement, the weights can be viewed as the conditional distribution of a sequence of $n$ independent geometric random variables, given that their sum equals $n$. Geometric random variables satisfy the conditions of Theorem 2.6 from Joag-Dev and Proschan (1983) according to Efron (1965, 3.1), implying that the resulting weights are NOD.

A general family of applicable NOD reweighting schemes can also be derived from the Farlie-Gumbel-Morgenstern (FGM) $n$-copula (Nelsen, 2006, page 108). For variables $u_{1},\ldots,u_{n}\in[0,1]$, an FGM copula is characterized by $2^{n}-n-1$ parameters—one for each subset of $\left\{1,\ldots,n\right\}$ that contains least two elements. Let $\theta_{1,2},\theta_{1,3},\ldots,\theta_{1,2,\ldots,n}\in[-1,1]$ denote these parameters. The density of the FGM copula is given by

where the $\theta$ values must adhere to the constraints

for all $(\epsilon_{1},\ldots,\epsilon_{n})\in\left\{-1,1\right\}^{n}$ to ensure non-negativity of the density function. It follows that each $u_{j}$ is marginally uniformly distributed, and for each $x\in[0,1]^{n}$,

Therefore, for any $x_{1},\ldots,x_{n}\in[0,1]$,

A FGM $n$-copula is thus NOD if and only if

for all $x_{1},\ldots,x_{n}\in[0,1]$. Because NOD is preserved under monotonic transformations, it follows that any multivariate distribution corresponding to such a FGM copula with $\theta$ satisfying the criteria in 12 and 13 will be NOD.

Finally, the condition that $\sum_{j=1}^{n}\mathbb{E}(|W_{nj}|^{q})=O(n)$ in Theorem 3 holds for all of the aforementioned reweighting procedures without any additional assumptions, except for a few cases. For the $\mathrm{Multinomial}\big{(}m_{n},(p_{n1},\ldots,p_{nn}))$ case, it holds as long as there exists a constant $\kappa>0$ such that $p_{nj}<\kappa/n$ for all $j$ and $n$. For the Gaussian reweighting scheme (Patak and Beaumont, 2009), it holds as long as $\sup_{n,j}\mathrm{Var}(W_{nj})<\infty$. For the independent weights and FGM copula cases, it holds when $\sup_{n,j}\mathbb{E}(|W_{nj}|^{q})<\infty$.

We begin by stating a strong law of large numbers of the bootstrap mean due to Arenal-Gutiérrez et al. (1996, Theorem 2.1). This lemma plays a key role in our proof of Theorem 1.

The following result, due to Chen et al. (2019), is a more general version of Lemma 1 that extends beyond the standard bootstrap to negatively orthant dependent (NOD) weights.