# On a Central Limit Theorem and a Confidence Interval for Randomized Quasi-Monte Carlo Methods

Marvin Nakayama, Bruno Tuffin

<figure><img src="image_1.png" /></figure>

► To cite this version:

Marvin Nakayama, Bruno Tuffin. On a Central Limit Theorem and a Confidence Interval for Randomized Quasi-Monte Carlo Methods. Stochastic Numerics and Statistical Learning: Theory and Applications Workshop, KAUST, May 2022, Djeddah, Saudi Arabia. pp.1-34. hal-03678150

HAL Id: hal-03678150

https://inria.hal.science/hal-03678150

Submitted on 25 May 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# On a Central Limit Theorem and a Confidence Interval for Randomized Quasi-Monte Carlo Methods

Marvin K. Nakayama¹, and Bruno Tuffin²

¹New Jersey Institute of Technology

²Inria, Rennes, France

<figure><img src="image_3.png" /></figure>

New Jersey Institute
of Technology

<figure><img src="image_4.png" /></figure>

informatics mathematics

Stochastic Numerics and Statistical Learning workshop
May 2022
# Motivation

* Estimate $\mu$ and provide **computable measure of error**, where

$$ \mu = \int_{[0,1]^s} h(u) du = \mathbb{E}[h(U)], \quad U \sim \mathcal{U}[0,1]^s $$

* Monte Carlo (MC), Quasi-Monte Carlo (QMC),

Randomized QMC (RQMC)

<figure><img src="image_5.png" /></figure>

* Central limit theorem (CLT) not proven for many RQMC settings.

* Goal: General conditions for RQMC to ensure

* CLT

* Asymptotically valid confidence interval (AVCI)
# Table of contents

1. Review: MC, QMC, RQMC

2. RQMC CLT and AVCI

3. Corollaries Ensuring CLT and AVCI: Tradeoffs

4. Concluding Remarks
* MC: **random sampling** to estimate $\mu = E[h(U)]$

$$ \hat{\mu}_n^{\text{MC}} = \frac{1}{n} \sum_{i=1}^{n} h(U_i) $$

* $U_1, U_2, \dots, U_n$ i.i.d. $U[0, 1]^s$

<figure><img src="image_6.png" /></figure>
* MC estimator: $\hat{\mu}_n^{\text{MC}} = \frac{1}{n} \sum_{i=1}^n h(U_i)$

* CLT: If $\psi^2 \equiv \text{Var}[h(U)] \in (0, \infty)$, then [Billingsley 1995]

$$ \sqrt{\frac{n}{\psi^2}} [\hat{\mu}_n^{\text{MC}} - \mu] \Rightarrow \mathcal{N}(0, 1) \quad \text{as } n \to \infty $$

* Approximate 100$\gamma$% confidence interval (CI) for $\mu$:

$$ I_{n,\gamma}^{\text{MC}} \equiv \left[ \hat{\mu}_n^{\text{MC}} \pm z_{\gamma} \frac{\hat{\psi}_n}{\sqrt{n}} \right] $$

$$ \hat{\psi}_n^2 = \frac{1}{n-1} \sum_{i=1}^n [h(U_i) - \hat{\mu}_n^{\text{MC}}]^2 \quad \text{and} \quad \Phi(z_{\gamma}) = 1 - (1 - \gamma)/2. $$

* Asymptotically valid CI (AVCI):

$$ P(\mu \in I_{n,\gamma}^{\text{MC}}) \rightarrow \gamma, \quad \text{as } n \rightarrow \infty $$

* Root mean-squared error: $\text{RMSE}[\hat{\mu}_n^{\text{MC}}] = \frac{\psi}{\sqrt{n}}$
* QMC: deterministic points to estimate $\mu = \mathbb{E}[h(U)]$

$$ \hat{\mu}_n^Q = \frac{1}{n} \sum_{i=1}^n h(\xi_i) $$

* Low-discrepancy sequence $\Xi = (\xi_i : i = 1, 2, \dots)$

* $\Xi$ is deterministic and evenly fill $[0, 1]^s$

* lattices (e.g., Korobov, ...),

<figure><img src="image_7.png" /></figure>
* Digital nets/sequences (e.g., Sobol', Faure, ...)

<figure><img src="image_8.png" /></figure>

* Is this 16 points sequence well-distributed?
* Digital nets/sequences (e.g., Sobol', Faure, ...)

<figure><img src="image_9.png" /></figure>

* If we split $[0, 1]^2$, we get the right number of points in the rectangles.
* Digital nets/sequences (e.g., Sobol', Faure, ...)

<figure><img src="image_10.png" /></figure>

* If we split $[0, 1]^2$, we get the right number of points in the rectangles.
* Digital nets/sequences (e.g., Sobol', Faure, ...)

<figure><img src="image_11.png" /></figure>

* If we split $[0, 1]^2$, we get the right number of points in the rectangles.
* Digital nets/sequences (e.g., Sobol', Faure, ...)

<figure><img src="image_12.png" /></figure>

* If we split $[0, 1]^2$, we get the right number of points in the rectangles.
* Digital nets/sequences (e.g., Sobol', Faure, ...)

<figure><img src="image_13.png" /></figure>

* If we split $[0, 1]^2$, we get the right number of points in the rectangles.
* Digital nets/sequences (e.g., Sobol', Faure, ...)

<figure><img src="image_14.png" /></figure>

* If we split $[0, 1]^2$, we get the right number of points in the rectangles.
* Digital nets/sequences (e.g., Sobol', Faure, ...)

<figure><img src="image_15.png" /></figure>

* If we split $[0, 1]^2$, we get the right number of points in the rectangles.
* Digital nets/sequences (e.g., Sobol', Faure, ...)

<figure><img src="image_16.png" /></figure>

* If we split $[0, 1]^2$, we get the right number of points in the rectangles.
* QMC: deterministic points to estimate $\mu = \mathbb{E}[h(U)]$

$$ \hat{\mu}_n^Q = \frac{1}{n} \sum_{i=1}^n h(\xi_i), \quad \Xi = (\xi_i : i = 1, 2, \dots) $$

* Koksma-Hlawka (K-H) inequality [Niederreiter 1992]: for each $n > 1$,

$$ |\hat{\mu}_n^Q - \mu| \le V_{HK}(h) D_n^*(\Xi) $$

* Hardy-Krause variation $V_{HK}(h) \in [0, \infty)$: “roughness” of $h$

* Star-discrepancy $D_n^*(\Xi) \in [0, 1]$; how unevenly first $n$ points of $\Xi$ fill $[0, 1]^s$

$$ D_n^*(\Xi) = O(n^{-1}(\ln n)^s) \approx O(n^{-1}), \quad n \to \infty. $$

* If $V_{HK}(h) < \infty$ (BVHK), then K-H bound shrinks at faster rate than MC rate $\Theta(n^{-1/2})$

$$ |\hat{\mu}_n^Q - \mu| \approx O(n^{-1}). $$

* BVHK: “bounded variation in sense of Hardy and Krause”
Two components: $V_{HK}(h)$ and $D_n^*(\Xi)$.

* Variation

► Difficult to compute: sum of $2^s - 1$ variations in the sense of Vitali (each difficult to estimate).

► $V_{HK}(h) = \infty$ often, even for simple functions such as

$$h(x_1, x_2, x_3) = \min(x_1 + x_2 + x_3, 1)$$

for which QMC converges (faster than for MC).

* Discrepancy

► Expression $D_n^*(\Xi) = \sup_{x \in [0,1]^s} \left| \frac{\sum_{i=1}^n 1_{\Pi_{k=1}^s [0, x_k]} (\xi_i)}{n} - \Pi_{k=1}^s x_k \right|$.

► We only have bounds with asymptotic usefulness, not for practice use.

► Ex: bounds for the (0, s)-Niederreiter sequence (while we know $D_n^*(\Xi) < 1$!)

<table><thead><tr><th>n</th><th>10<sup>3</sup></th><th>10<sup>4</sup></th><th>10<sup>6</sup></th><th>10<sup>9</sup></th><th>10<sup>12</sup></th><th>10<sup>16</sup></th></tr></thead><tbody><tr><td>Bound</td><td>1.50</td><td>3.34 10<sup>-1</sup></td><td>2.14 10<sup>-2</sup></td><td>1.21 10<sup>-4</sup></td><td>5.83 10<sup>-7</sup></td><td>1.92 10<sup>-10</sup></td></tr></tbody></table>

<table><thead><tr><th>n</th><th>10<sup>3</sup></th><th>10<sup>9</sup></th><th>10<sup>15</sup></th><th>10<sup>21</sup></th><th>10<sup>35</sup></th></tr></thead><tbody><tr><td>Bound</td><td>2.88 10<sup>5</sup></td><td>1.11 10<sup>6</sup></td><td>2.46 10<sup>5</sup></td><td>5.22 10<sup>3</sup></td><td>1.62 10<sup>-3</sup></td></tr></tbody></table>

* Other bounds exist, in general with the same issues.
Review: Randomized Quasi-Monte Carlo (RQMC)

* i.i.d. randomizations of $\Xi = (\xi_i : i \ge 1)$, each yielding $\Xi' = (U'_i : i \ge 1)$

* Each $U'_i \sim \mathcal{U}[0, 1]^s$

* $\Xi'$ retains low-discrepancy properties of $\Xi$

* **Lattice:** random shift [Cranley & Patterson 1976]

<figure><img src="image_17.png" /></figure>

* **Digital net:** nested scrambling [Owen 1995], digital shift [L'Ecuyer & Lemieux 2002], ...
* RQMC computation budget of $n$ evaluations of $h$ (as for MC)

* allocation $(m_n, r_n)$ with $m_n \times r_n \approx n$

* $r_n = \# \text{i.i.d. randomizations}$

* $m_n = \# \text{points used from jth randomized sequence } \Xi'_j = (U'_{i,j} : i \ge 1), j = 1, 2, \dots, r_n$

* RQMC: $r_n \ge 2$ i.i.d. **randomizations** to estimate $\mu = \mathbb{E}[h(U)]$

$$ \hat{\mu}_{m_n, r_n}^{\text{RQ}} = \frac{1}{r_n} \sum_{j=1}^{r_n} X_{n,j}, \quad \text{where} \quad X_{n,j} = \frac{1}{m_n} \sum_{i=1}^{m_n} h(U'_{i,j}) $$

* $X_{n,1}, X_{n,2}, \dots, X_{n,r_n}$ i.i.d.: estimate $\sigma_{m_n}^2 \equiv \text{Var}[X_{n,1}]$ by

$$ \hat{\sigma}_{m_n, r_n}^2 = \frac{1}{r_n - 1} \sum_{j=1}^{r_n} (X_{n,j} - \hat{\mu}_{m_n, r_n}^{\text{RQ}})^2 . $$

* Approx $\gamma$-level CI for $\mu$

$$ I_{m_n, r_n, \gamma}^{\text{RQ}} \equiv \left[ \hat{\mu}_{m_n, r_n}^{\text{RQ}} \pm z_{\gamma} \frac{\hat{\sigma}_{m_n, r_n}}{\sqrt{r_n}} \right] $$

* $X_{n,1}, X_{n,2}, \dots, X_{n,r_n}$ i.i.d., but distn of each $X_{n,j}$ depends on $n$: **Triangular array**.
How to choose RQMC Allocation ($m_n, r_n$) with $m_n \times r_n \approx n$?

* **Heuristic:** For given budget $n$, choose $r_n$ small and $m_n \approx n/r_n$ large to exploit QMC.

* CI: $J_{m_n, r_n, \gamma}^{\text{RQ}} = [\hat{\mu}_{m_n, r_n}^{\text{RQ}} \pm z_{\gamma} \frac{\hat{\sigma}_{m_n, r_n}}{\sqrt{r_n}}]$

* $r_n = \# \text{i.i.d. randomizations}$

* $m_n = \# \text{ points used from each randomized sequence}$

* But heuristic lacks rigorous justification.
## How to choose RQMC Allocation ($m_n, r_n$) with $m_n \times r_n \approx n$?

* **Heuristic:** For given budget $n$, choose $r_n$ small and $m_n \approx n/r_n$ large to exploit QMC.

* CI: $I_{m_n, r_n, \gamma}^{\text{RQ}} \equiv [\hat{\mu}_{m_n, r_n}^{\text{RQ}} \pm z_{\gamma} \frac{\hat{\sigma}_{m_n, r_n}}{\sqrt{r_n}}]$

* $r_n = \# \text{i.i.d. randomizations}$

* $m_n = \# \text{points used from each randomized sequence}$

* But heuristic lacks rigorous justification.

## Question and Goal

* Is this heuristic theoretically valid?

* **Goal:** Obtain sufficient conditions to ensure CLT and AVCI (as $n \approx m_n \times r_n \to \infty$).
## How to choose RQMC Allocation ($m_n, r_n$) with $m_n \times r_n \approx n$ ?

* AVCI relies on CLT: **not established for many RQMC settings.**

* Nested scrambling of digital nets: CLT as $m_n = n \to \infty$, **fixed $r_n = 1$** [Loh 2003]

* Randomly shifted lattices: **no CLT as $m_n = n/r_n \to \infty$, fixed $r_n \ge 1$** [L'Ecuyer et al. 2010]
## How to choose RQMC Allocation ($m_n, r_n$) with $m_n \times r_n \approx n$?

*   **AVCI relies on CLT: not established for many RQMC settings.**

*   Nested scrambling of digital nets: CLT as $m_n = n \to \infty$, fixed $r_n = 1$ [Loh 2003]

*   Randomly shifted lattices: **no** CLT as $m_n = n/r_n \to \infty$, fixed $r_n \ge 1$ [L'Ecuyer et al. 2010]

*   **Assumption 1. On**

*   **Assumption 1.A:** $m_n r_n \le n$ for each $n \ge 1$, with $m_n r_n/n \to 1$ and $r_n \to \infty$ as $n \to \infty$.

*   **Assumption 1.B:** "Simple allocation": $(m_n, r_n) = (n^c, n^{1-c})$ for constant $c \in (0, 1)$.

*   **Main Issue:** How to choose $c$?

*   More general allocation ($m_n, r_n$): $r_n \to \infty$ with $m_n \times r_n \approx n$ as $n \to \infty$.

*   **Assumption 2.** $\sigma_{m_n}^2 \equiv \mathrm{Var}[X_{n,1}] > 0$ for all $n$ large enough.

*   Results based on CLT for triangular arrays. For a triabgular array, the $r_n$ variables within each row $n$ are independent, but variables in different rows may be dependent. Here:

$X_{n,1}, X_{n,2}, \dots, X_{n,r_n}$ are i.i.d., each with some distribution $F_n$.
## Theorem 1

If Assumptions 1 and 2 hold, then RQMC estimator $\hat{\mu}_{m_n, r_n}^{RQ}$ satisfies CLT

$$ \sqrt{\frac{r_n}{\sigma_{m_n}^2}} [\hat{\mu}_{m_n, r_n}^{RQ} - \mu] \Rightarrow \mathcal{N}(0, 1), \quad \text{as } n \to \infty $$

under either

Lindeberg condition: $$ \frac{\mathbb{E}[(X_{n,1} - \mu)^2; |X_{n,1} - \mu| > t \sqrt{r_n \sigma_{m_n}^2}]}{\mathbb{E}[(X_{n,1} - \mu)^2]} \to 0, \quad \text{as } n \to \infty, \forall t > 0; $$ or

Lyapounov condition: $$ \frac{\mathbb{E}[|X_{n,1} - \mu|^{2+b'}]}{r_n^{b'/2} \sigma_{m_n}^{2+b'}} \to 0, \quad \text{as } n \to \infty, \text{ for some } b' > 0. $$

• $\sigma_{m_n}^2 = \mathbb{E}[(X_{n,1} - \mu)^2] = \text{variance of estimator } X_{n,1} \text{ from single randomization of } m_n \text{ points.}$
# RQMC Asymptotically Valid CI (AVCI)

* **Recall Lyapounov condition:**

$$ \frac{\mathbb{E}\left[|X_{n,1} - \mu|^{2+b'}\right]}{r_n^{b'/2} \sigma_{m_n}^{2+b'}} \to 0, \quad \text{as } n \to \infty, \text{ for some } b' > 0. $$

* $\hat{\sigma}_{m_n, r_n}^2 = \frac{1}{r_n-1} \sum_{j=1}^{r_n} (X_{n,j} - \hat{\mu}_{m_n, r_n}^{\text{RQ}})^2$ is unbiased estimator of $\sigma_{m_n}^2 = \text{Var}[X_{n,1}]$.

* Approx. $\gamma$-level CI for $\mu$

$$ I_{m_n, r_n, \gamma}^{\text{RQ}} = \left[ \hat{\mu}_{m_n, r_n}^{\text{RQ}} \pm z_{\gamma} \frac{\hat{\sigma}_{m_n, r_n}}{\sqrt{r_n}} \right] $$

## Theorem 2

If Assumptions 1 and 2 hold, along with Lyapounov condition for $b' = 2$, then CLT

$$ \sqrt{\frac{r_n}{\hat{\sigma}_{m_n, r_n}^2}} [\hat{\mu}_{m_n, r_n}^{\text{RQ}} - \mu] \Rightarrow \mathcal{N}(0, 1), \quad \text{as } n \to \infty $$

and AVCI

$$ P(\mu \in I_{m_n, r_n, \gamma}^{\text{RQ}}) \to \gamma, \quad \text{as } n \to \infty. $$
Ensuring CLT (with $\sigma_m^2 > 0$)

Instead of condition (1), impose alternative conditions on integrand $h$

* **Assumption 3.A:** $V_{\text{HK}}(h) < \infty$ (BVHK)

* **Assumption 3.B:** $h$ is bounded

* **Assumption 3.C:** $\mathbb{E}[|h(U) - \mu|^{2+b}] < \infty$ for some $b > 0$, where $U \sim \mathcal{U}[0, 1]^s$.

**Proposition 1**

* Under Assumption 3.A, if $\exists \lambda \in (0, 1) \ r_n^{1-\lambda} \left( \frac{m_n \sigma_{m_n}}{(\ln m_n)^s} \right)^2 \to \infty \text{ as } n \to \infty,$

* Under Assumption 3.B, if $s_n^2 = r_n \sigma_{m_n}^2 \to \infty$ as $n \to \infty$,

* Under Assumption 3.C, if $r_n^{b/(2+b)} \sigma_{m_n}^2 \to \infty$ as $n \to \infty$,

then the CLT holds

**Proposition 2**

Assumption 3.A $\Rightarrow$ 3.B $\Rightarrow$ 3.C, leading reversely strict conditions in the above proposition.
Ensuring AVCI (with $\sigma_m^2 > 0$)

Instead of condition (1), impose alternative conditions on integrand $h$

* **Assumption 3.A:** $V_{\text{HK}}(h) < \infty$ (BVHK)

* **Assumption 3.B:** $h$ is bounded

* **Assumption 3.C:** $E[|h(U) - \mu|^{2+b}] < \infty$ for some $b > 0$, where $U \sim U[0, 1]^s$.

Under Assumption 1.A:

**Proposition 3**

* Under Assumption 3.A, if $r_n \left( \frac{m_n \sigma_{m_n}}{(\ln m_n)^s} \right)^4 \to \infty$ as $n \to \infty$,

* Under Assumption 3.C, if $\frac{E[|X_{m,1} - \mu|^{2+b'}]}{\sigma_m^{2+b'}} \le k_1$ with $b' = 2$, then AVCI holds
Corollaries Ensuring CLT or AVCI under Assumption 1.B
Assumption

For estimator $X_{n,1}$ from **single** randomization of $m_n$ points,

$$ \sigma_{m_n} \equiv \sqrt{\mathrm{Var}[X_{n,1}]} \approx \Theta(m_n^{-\alpha_*}) \quad \text{as } m_n \to \infty, \quad \text{where} \quad \alpha_* \equiv - \lim_{m_n \to \infty} \frac{\ln(\sigma_{m_n})}{\ln(m_n)} > \frac{1}{2} $$

* $\alpha_* \ge 1$ when $V_{\mathrm{HK}}(h) < \infty$ (BVHK).

* Under Assumption 1.B [$(m_n, r_n) = (n^c, n^{1-c}), c \in (0,1)$],

$$ \mathrm{RMSE} \left[ \hat{\mu}_{m_n, r_n}^{\mathrm{RQ}} \right] = \frac{\sigma_{m_n}}{\sqrt{r_n}} \approx \Theta \left( n^{-\nu(\alpha_*, c)} \right) \quad \text{as } n \to \infty, \text{ with } \nu(\alpha_*, c) = c \left[ \alpha_* - \frac{1}{2} \right] + \frac{1}{2}. $$
## Corollaries Ensuring CLT or AVCI under Assumption 1.B
### Assumption

For estimator $X_{n,1}$ from single randomization of $m_n$ points,

$$ \sigma_{m_n} \equiv \sqrt{\mathrm{Var}[X_{n,1}]} \approx \Theta(m_n^{-\alpha_*}) \quad \text{as } m_n \to \infty, \text{ where } \alpha_* \equiv - \lim_{m_n \to \infty} \frac{\ln(\sigma_{m_n})}{\ln(m_n)} > \frac{1}{2} $$

* $\alpha_* \ge 1$ when $V_{\mathrm{HK}}(h) < \infty$ (BVHK).

* Under Assumption 1.B $[ (m_n, r_n) = (n^c, n^{1-c}), c \in (0,1) ]$,

$$ \mathrm{RMSE} \left[ \hat{\mu}_{m_n, r_n}^{\mathrm{RQ}} \right] = \frac{\sigma_{m_n}}{\sqrt{r_n}} \approx \Theta \left( n^{-\nu(\alpha_*, c)} \right) \quad \text{as } n \to \infty, \text{ with } \nu(\alpha_*, c) \equiv c \left[ \alpha_* - \frac{1}{2} \right] + \frac{1}{2}. $$

* Corollary $k=1,2,\dots,6$: ensure CLT or AVCI under constraint $c < c_k(\alpha_*)$

* $c_k(\alpha_*) \in (0,1]$, sometimes $c_k(\alpha_*) = 1$.

* Optimal RMSE: take $c < c_k(\alpha_*)$ with $c \approx c_k(\alpha_*)$

$$ \mathrm{RMSE} \left[ \hat{\mu}_{m_n, r_n}^{\mathrm{RQ}} \right] \approx \Theta \left( n^{-\nu_k(\alpha_*)} \right) \quad \text{as } n \to \infty, \text{ with } \nu_k(\alpha_*, c) \equiv c_k(\alpha_*) \left[ \alpha_* - \frac{1}{2} \right] + \frac{1}{2} > \frac{1}{2} $$

⇒ **RQMC better than MC.**
# Corollaries Ensuring CLT or AVCI

## Corollary 1

Suppose that Assumptions 1 and 2 hold, and $∃ \ b' > 0 \ and \ k_1 ∈ (0, ∞)$ such that

$$ \frac{\mathbb{E}[|X_{n,1} - \mu|^{2+b'}]}{\sigma_{m_n}^{2+b'}} \le k_1 \quad \forall m_n \text{ sufficiently large.} \quad (1) $$

Then CLT holds for allocation $(m_n, r_n) = (n^c, n^{1-c})$ with any

$$ c < 1 \equiv c_1(\alpha_*) $$

and optimal RMSE $\approx \Theta(n^{-v_1(\alpha_*)})$ as $n \to \infty$ with

$$ v_1(\alpha_*) \equiv \alpha_* $$

If (1) holds for $b' = 2$, then AVCI holds for $c < c_1(\alpha_*)$, and RMSE rate exponent is $v_1(\alpha_*)$.

* CLT/AVCI with $r_n \to \infty$ since $c < 1$.

* RMSE rate same as $\sigma_{m_n} \approx \Theta(m_n^{-\alpha_*})$ for **single** randomization of $m_n = n$ points.
## Corollaries Ensuring CLT or AVCI: Tradeoffs

Impose again alternative conditions on integrand $h$

* **Assumption 3.A:** $V_{\text{HK}}(h) < \infty$ (BVHK)

* **Assumption 3.B:** $h$ is bounded

* **Assumption 3.C:** $E[|h(U) - \mu|^{2+b}] < \infty$ for some $b > 0$, where $U \sim U[0, 1]^s$.

## Proposition 4

* **Assumption 3.A** $\Rightarrow$ **3.B** $\Rightarrow$ **3.C**, leading to successively smaller $c_k(\alpha_*)$ for Corollaries $k$ (next slide).

* Under Assumption 3.x, for $c_k(\alpha_*)$ ensuring CLT and $c_{k'}(\alpha_*)$ ensuring AVCI,

$$c_k(\alpha_*) \ge c_{k'}(\alpha_*) \quad (\text{often} >).$$

* **Assumption 1:** $(m_n, r_n) = (n^c, n^{1-c})$, $c \in (0, 1)$

* Corollary $k$: $c < c_k(\alpha_*)$

* $\sigma_{m_n} \approx \Theta(m_n^{-\alpha_*})$, $\alpha_* > 1/2$
Corollaries CLT or AVCI: Tradeoffs

<table><thead><tr><th>Cor. k</th><th>Ensures</th><th>Assumption on h</th><th>c upper bd c<sub>k</sub>(α<sub>*</sub>)</th><th>RMSE rate exp v<sub>k</sub>(α<sub>*</sub>)</th></tr></thead><tbody><tr><td>2</td><td>CLT</td><td>3.A (BVHK)</td><td>1/(2α<sub>*</sub>-1) &gt;</td><td>1 &gt;</td></tr><tr><td>3</td><td>CLT</td><td>3.B (h bdd)</td><td>1/(2α<sub>*</sub>+1) &gt;</td><td>1/(2α<sub>*</sub>+1) &gt;</td></tr><tr><td>4</td><td>CLT</td><td>3.C (b &gt; 0)</td><td>1/(2α<sub>*</sub>(1+1/b)<sup>2</sup>+1) &isin; (0, 1/2)</td><td>1/(2α<sub>*</sub>(1+1/b)<sup>2</sup>+1) &gt; 1/2</td></tr><tr><td>5</td><td>AVCI</td><td>3.A (BVHK)</td><td>1/(4α<sub>*</sub>-3) &gt;</td><td>3α<sub>*</sub>-2/(4α<sub>*</sub>-3) &gt;</td></tr><tr><td>6</td><td>AVCI</td><td>3.C (b = 2)</td><td>1/(4α<sub>*</sub>+1) &isin; (0, 1/3)</td><td>3α<sub>*</sub>/(4α<sub>*</sub>+1) &gt; 1/2</td></tr></tbody></table>

$$ \bullet \text{ 3.A} \Rightarrow \text{ 3.B} \Rightarrow \text{ 3.C} $$

* **Assumption 3.A:** $V_{\text{HK}}(h) < \infty$ (BVHK: $\Rightarrow \alpha_* \ge 1$)

* **Assumption 3.B:** $h$ is bounded.

* **Assumption 3.C:** $E[|h(U) - \mu|^{2+b}] < \infty$ for some $b > 0$, where $U \sim U[0, 1]^s$.

* Comparisons for fixed $\alpha_* > 1/2$

* $(m_n, r_n) = (n^c, n^{1-c})$, $c < c_k(\alpha_*)$, opt RMSE $\approx \Theta(n^{-v_k(\alpha_*)})$.
<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

* All $c_k(\alpha_*) \downarrow$ as $\alpha_* \uparrow$

► Corollary k: $c < c_k(\alpha_*)$ in $(m_n, r_n) = (n^c, n^{1-c})$.

► $\sigma_{m_n} \approx \Theta(m_n^{-\alpha_*})$, $\alpha_* > 1/2$ ($\ge 1$ BVHK)

* Most $v_k(\alpha_*) \uparrow$ as $\alpha_* \uparrow$

► Optimal RMSE $\approx \Theta(n^{-v_k(\alpha_*)})$, $n \to \infty$

► Larger $\alpha_*$ usually yields better RQMC performance.
Concluding Remarks

Sufficient conditions for RQMC CLT and AVCI for $\mu = E[h(U)]$

► Corollary $k$: $c < c_k(\alpha_*)$ for allocation $(m_n, r_n) = (n^c, n^{1-c})$.

► Tradeoffs: Weaker conditions on integrand $h$ —→ stronger restrictions on $c$.

► AVCI imposes (often strictly) stronger restrictions on $c$ than CLT.

► RMSE: RQMC outperforms MC.

Current work

► Estimate $c_k(\alpha_*)$.

► Weaker conditions.

► CLT and AVCI for biased estimators, e.g., quantiles.

► Alternative Cls: Bootstrap-t, etc.

Thank you!