Optimal confidence for Monte Carlo integration of smooth functions

Abstract

We study the information-based complexity of approximating integrals of smooth functions at absolute precision ε > 0 with confidence level 1 − δ ∈ (0, 1) using function evaluations within randomized algorithms. The probabilistic error criterion is new in the context of integrating smooth functions. In previous research, Monte Carlo integration was studied in terms of the expected error (or the root mean squared error), for which linear methods achieve optimal rates of the error e(n) in terms of the number n of function evaluations. In our context, usually methods that provide optimal confidence properties exhibit non-linear features. The optimal probabilistic error rate e(n,δ) for multivariate functions from classical isotropic Sobolev spaces ${W_{p}^{r}}(G)$ with sufficient smoothness on bounded Lipschitz domains $G \subset {\mathbb R}^{d}$ is determined. It turns out that the integrability index p has an effect on the influence of the uncertainty δ in the complexity. In the limiting case p = 1, we see that deterministic methods cannot be improved by randomization. In general, higher smoothness reduces the additional effort for diminishing the uncertainty. Finally, we add a discussion about this problem for function spaces with mixed smoothness.

Appendices

Appendix A: Domains with Lipschitz boundary

From Novak and Triebel [21], we cite the following definition of a Lipschitz domain:

Definition 1

A bounded Lipschitz domain in ${\mathbb R}^{d}$, where d ≥ 2, is a non-empty bounded open connected set $G \subseteq {\mathbb R}^{d}$ such that its boundary ∂G can be covered by finitely many open balls $B_{1},\ldots ,B_{J} \subseteq {\mathbb R}^{d}$, each centered at ∂G, such that

$$ B_{j} \cap G = B_{j} \cap G_{j} \qquad \text{for}\ j=1,\ldots,J, $$

where G_j are suitable rotations of sets

$$ G_{j}^{\prime} := \left\{(\mathbf{x}^{\prime},x_{d}) \in {\mathbb R}^{d-1}\times{\mathbb R} \middle| x_{d} > h_{j}(\mathbf{x}^{\prime}) \right\} \subseteq {\mathbb R}^{d} $$

with Lipschitz continuous functions $h_{j}\colon {\mathbb R}^{d-1} \to {\mathbb R}$.

The boundary of $G_{j}^{\prime }$ is the graph of h_j, that is, $\partial G_{j}^{\prime } = \{(\mathbf {x}^{\prime },h_{j}(\mathbf {x}^{\prime })) \mid \mathbf {x}^{\prime } \in {\mathbb R}^{d-1}\}$. (The inclusion $\supseteq$ is obvious; further, the strict epigraph $G_{j}^{\prime }$ of h_j is an open set due to the Lipschitz continuity of h_j, and the same holds for the strict hypograph $\{(\mathbf {x}^{\prime },x_{d}) \in {\mathbb R}^{d-1}\times {\mathbb R} \mid x_{d} < h_{j}(\mathbf {x}^{\prime })\}$. In detail, if $\mathbf {x} = (\mathbf {x}^{\prime },x_{d}) \in {\mathbb R}^{d-1}\times {\mathbb R}$ with $x_{d} \not = h_{j}(\mathbf {x}^{\prime })$, then the Euclidean ball around x with radius $r := \frac {|h_{j}(\mathbf {x}^{\prime }) - x_{d}|}{2 \cdot \max \limits \{1,L_{j}\}}$, where L_j ≥ 0 is the Lipschitz constant of h_j, does not intersect with the graph of h_j.) By the integrability of h_j on bounded domains [− b,b]^d− 1, $b \in {\mathbb N}$, we have $\lambda ^{d}(\partial G_{j}) = \lambda ^{d}(\partial G_{j}^{\prime }) = 0$ for j = 1,…,J. Therefore, the boundary $\partial G = \bigcup _{j=1}^{J} (B_{j} \cap \partial G_{j})$ of a bounded Lipschitz domain G has Lebesgue measure λ^d(∂G) = 0. Hence, Sobolev spaces defined on the closure $\overline {G}$ coincide with the Sobolev spaces defined on G. For instance, the standard domain [0, 1]^d is closed, but since its interior (0, 1)^d is a Lipschitz domain, the closed unit cube [0, 1]^d very well belongs to the realm of admissible domains; its boundary is Lipschitz.

Definition 2

A bounded measurable set $G \subseteq {\mathbb R}^{d}$ is said to have a Lipschitz boundary if its interior int(G) is a bounded Lipschitz domain and ∂G = ∂ int(G).

Appendix B: Estimates on binomial sums

In Section 2, we need the following two inequalities about binomial sums. The first lemma is a minor extension of [17, Proposition 7.3.2], holding also for odd k, and with slightly improved constants.

Lemma 3

For all$k \in {\mathbb N}$and$t \in {\mathbb N}_{0}$, we have

$$ \begin{array}{@{}rcl@{}} &&2^{-k} \sum\limits_{j=0}^{\lfloor k/2 \rfloor - t} \binom{k}{j} = 2^{-k} \sum\limits_{j=\lceil k/2 \rceil+t}^{k} \binom{k}{j} \\ &\geq& \frac{1}{2 + 4/\sqrt{\pi}} \left\{\begin{array}{lll} \displaystyle \exp\left( -\frac{16 (\log 2) t^{2}}{k } \right) \quad&\text{for odd}~\ k\ \text{and}\ t \in [0,\frac{k+3}{8}], \\ \displaystyle \exp\left( -\frac{16 (\log 2) (t-1/2)^{2}}{k } \right) \quad&\text{for even}~\ k\ \text{and}\ t \in [0,\frac{k+6}{8}]. \end{array}\right. \end{array} $$

Proof

First, recall that $\binom {k}{\lfloor k/2 \rfloor } < 2^{k} / \sqrt {\pi \lceil k/2 \rceil }$, which for even k follows from Stirling’s approximation, $\sqrt {2\pi } n^{n+1/2} \exp (-n) \exp \left (\frac {1}{12n+1}\right ) < n! < \sqrt {2\pi } n^{n+1/2}$$\exp (-n) \exp \left (\frac {1}{12n}\right )$ (see [25]), and for odd k can be derived from k + 1 via Pascal’s rule. Hence,

$$ \begin{array}{@{}rcl@{}} 2^{-k} \sum\limits_{j=0}^{\lfloor k/2 \rfloor - t} \binom{k}{j} & \geq \frac{1}{2} - 2^{-k} t \binom{k}{\lfloor k/2 \rfloor} > \frac{1}{2} - \frac{t}{\sqrt{\pi \lceil k/2 \rceil}} . \end{array} $$

For $0 \leq t \leq \sqrt {\lceil k/2 \rceil }/(1+2/\sqrt {\pi })$, this gives the absolute lower bound $\frac {1}{2 + 4/\sqrt {\pi }}$.

For larger t, we follow the approach of [17, Proposition 7.3.2]. Basic estimates yield

$$ \begin{array}{@{}rcl@{}} 2^{-k} \sum\limits_{j=0}^{\lfloor k/2 \rfloor - t} \binom{k}{j} &\geq& 2^{-k} \sum\limits_{j=\lfloor k/2 \rfloor - 2t + 1}^{\lfloor k/2 \rfloor - t} \binom{k}{j} \\ &\geq& 2^{-k} t \binom{k}{\lfloor k/2 \rfloor-2t+1} \\ &=& 2^{-k} t \binom{k}{\lfloor k/2 \rfloor} \prod\limits_{i=1}^{2t-1} \frac{\lfloor k/2 \rfloor - 2t + 1 + i}{\lceil k/2 \rceil + i}\\ &\geq& 2^{-k} t \binom{k}{\lfloor k/2 \rfloor} \left( \frac{\lfloor k/2 \rfloor - 2t + 2}{\lceil k/2 \rceil + 1} \right)^{2t-1} . \end{array} $$

Next, we use $1-x \geq \exp (-2 (\log 2) x)$ for 0 ≤ x ≤ 1/2. For odd k, we set x = 2t/(⌈k/2⌉ + 1), and for even k, we set x = (2t − 1)/(k/2 + 1). This is where t ≤ (k + 6)/8 for even k and t ≤ (k + 3)/8 for odd k come into play. Finally, we use $\binom {k}{\lceil k/2 \rceil } \geq 2^{k}/(2 \sqrt {\lceil k/2 \rceil })$ and obtain

$$ \begin{array}{@{}rcl@{}} 2^{-k} \sum\limits_{j=0}^{\lfloor k/2 \rfloor - t} \binom{k}{j} & \geq \frac{t}{2 \sqrt{\lceil k/2 \rceil}} \left\{\begin{array}{lll} \displaystyle \exp\Bigl[- \frac{8 (\log 2) t (t - 1/2) }{\lceil k/2 \rceil + 1} \Bigr] &&\quad\text{for odd}\ ~k,\\ \displaystyle \exp\Bigl[- \frac{8 (\log 2) (t-1/2)^{2} }{k/2 + 1} \Bigr] &&\quad\text{for even}~k. \end{array}\right. \end{array} $$

For $t \geq \sqrt {\lceil k/2 \rceil }/(1+2/\sqrt {\pi })$, the prefactor simplifies as stated in the claimed inequality.

Lemma 4

For all$k,k^{\prime }\in {\mathbb N}_{0}$with$k\geq k^{\prime }$, we have

$$ 2^{-k} \Biggl[\sum\limits_{j=0}^{\left\lfloor \frac{k-k^{\prime}}{2} \right\rfloor} \binom{k}{j} + \sum\limits_{j=\left\lceil \frac{k+k^{\prime}+1}{2} \right\rceil}^{k} \binom{k}{j} \Biggr] \geq 2^{-k^{\prime}} . $$

Proof

The proof follows by induction over $k\geq k^{\prime }$. A speciality here is that in the induction step, we assume the statement for k and prove it for k + 2, which is sufficient when the base case is verified for $k=k^{\prime }$ and $k=k^{\prime }+1$.

For $k=k^{\prime }$ and $k=k^{\prime }+1$, we have $2^{-k^{\prime }} \binom {k}{0}$ and $2^{-(k^{\prime }+1)}[\binom {k^{\prime }}{0}+\binom {k^{\prime }+1}{k^{\prime }+1}]$, respectively, which proves the inequality. (We even have equality.)

For the induction step from k to k + 2 where $k\geq k^{\prime }$, via Pascal’s rule, as well as using $\binom {k}{\left \lfloor \frac {k+2-k^{\prime }}{2} \right \rfloor } \geq \binom {k}{\left \lfloor \frac {k-k^{\prime }}{2} \right \rfloor }$, we obtain

$$ \sum\limits_{j=0}^{\left\lfloor \frac{k+2-k^{\prime}}{2}\right\rfloor}\binom{k+2}{j} = 4 \sum\limits_{j=0}^{\left\lfloor \frac{k-k^{\prime}}{2}\right\rfloor-1}\binom{k}{j} + 3 \binom{k}{\left\lfloor \frac{k-k^{\prime}}{2}\right\rfloor} + \binom{k}{\left\lfloor \frac{k+2-k^{\prime}}{2} \right\rfloor} \geq 4 \sum\limits_{j=0}^{\left\lfloor \frac{k-k^{\prime}}{2}\right\rfloor} \binom{k}{j} . $$

Similarly, with $\binom {k}{\left \lfloor \frac {k+k^{\prime }+1}{2} \right \rfloor } \geq \binom {k}{\left \lfloor \frac {k+k^{\prime }+3}{2} \right \rfloor }$, one can show

$$ \sum\limits_{j=\left\lceil \frac{k+k^{\prime}+3}{2} \right\rceil}^{k+2} \binom{k+2}{j} \geq 4 \sum\limits_{j=\left\lceil \frac{k+k^{\prime}+1}{2} \right\rceil}^{k} \binom{k}{j} . $$

Now, by the induction hypothesis, the assertion is proven.

Appendix C: Lower bounds for adaptive methods

We supplement the discussion of Section 2.1 by a brief theoretical treatment of adaptive methods without repeating notions that have already been explained there. All upper bounds within this paper rely on non-adaptive methods, most with fixed cardinality, some with varying cardinality. For lower bounds, it is desirable to extend them to as broad classes of algorithms as possible, hopefully showing that additional features such as adaptivity are not helpful, thus sticking to simple methods is justified.

An abstract adaptive Monte Carlo algorithm for functions from $\mathcal {W}$ is a family A = (A^ω)_ω∈Ω of mappings A^ω = ϕ^ω ∘ ι^ω, where $\iota ^{\omega } : \mathcal {W} \to c_{00} := \bigcup _{n \in {\mathbb N}_{0}} {\mathbb R}^{n}$ returns a terminating sequence $\mathbf {y} = \iota ^{\omega }(f) \in {\mathbb R}^{\widetilde {n}(\omega ,f)}$ of function values at sequentially selected nodes, with

$$ y_{1} = f(\mathbf{x}_{1}^{\omega}) , \qquad\text{and}\qquad y_{i} = f\bigl(\mathbf{x}_{i}^{\omega}(y_{1},\ldots,y_{i-1})\bigr) , \qquad\text{for} \ i=2,\ldots,\widetilde{n}(\omega,f). $$

Here, the input-dependent random cardinality $\text {card}(A,f): \omega \mapsto \widetilde {n}(\omega ,f)$ is determined by a stopping rule; that is, the decision whether or not to stop after n function evaluations only depends on the randomness and the function values collected up to that point, in detail, with a so-called termination functionT^ω : c₀₀ →{0, 1}. Taking the classical worst case perspective with respect to the input class, we aim to study the power of algorithms with a (possibly non-integer) bound $\bar {n} > 0$ on the worst expected cardinality,

$$ \overline{\text{card}}(A,\mathcal{W}) := \sup\limits_{\|f\|_{\mathcal{W}} \leq 1} {\mathbb{E}} \text{card}(A,f) , $$

(33)

i.e., the quantity of interest is

$$ \widetilde{e}_{\text{prob}}^{\text{MC-ada}}(\bar{n},\delta,\mathcal{W}) := \inf\limits_{A \colon \overline{\text{card}}(A,\mathcal{W}) \leq \bar{n}} e(A,\delta,\mathcal{W}) . $$

(34)

As in Section 2.1, we consider a discrete probability measure μ on the set of inputs. For fixed ω ∈Ω, we define the μ-average cardinality as

$$ \text{card}(A^{\omega},\mu) := \int_{\mathcal{B}_{\mathcal{W}}} \text{card}(A^{\omega},f) \text{d}\mu(f) . $$

(35)

A Fubini argument shows that $\overline {\text {card}}(A,\mathcal {W}) \geq {\mathbb {E}} \text {card}(A,\mu )$, and provided $\overline {\text {card}}(A,\mathcal {W}) \leq \bar {n}$, Markov’s inequality implies

$$ {\mathbb P}\{\text{card}(A,\mu) \leq 2\bar{n}\} \geq \frac{1}{2} . $$

(36)

Analogously to Eq. 11, we perform a trick in the spirit of Bakhvalov [4] and obtain

$$ \sup\limits_{\|f\|_{\mathcal{W}} \leq 1} {\mathbb P}\{|A(f) - \text{INT} f| > \varepsilon\} \geq \frac{1}{2} \inf\limits_{Q \colon \text{card}(Q,\mu) \leq 2\bar{n}} \mu\{f \colon |Q(f) - \text{INT} f| > \varepsilon\} , $$

(37)

where the infimum is taken over deterministic algorithms Q (for each fixed ω ∈Ω, we may consider A^ω to be deterministic).

How does Lemma 1 change if we allow for adaptive algorithms? Roughly speaking, our lower bounds on $e_{\text {prob}}^{\text {MC}}(n,\delta ,\mathcal {W})$, that is, with non-adaptive methods with fixed cardinality, hold for $\widetilde {e}_{\text {prob}}^{\text {MC-ada}}\bigl (\frac {n}{4},\frac {\delta }{4},\mathcal {W}\bigr )$ in the adaptive setting with varying cardinality.

Lemma 5

Let$\bar {n} \geq 17/4$and$N \in {\mathbb N}$with$N \geq 20\bar {n} + 6$, and letγ > 0. Assume that there are functions$f_{i} : G \to {\mathbb R}$, for i = 1,…,N, satisfying conditions 1 and 2 as in Lemma 1. Then, for any uncertainty level 0 < δ < 1/12, we have

$$ \widetilde{e}_{\text{prob}}^{\text{MC-ada}}(\bar{n},\delta,\mathcal{W}) \geq \gamma \min\left\{2 \bar{n}^{1/2} \sqrt{\log_{4} \frac{1}{12 \delta}}, 4\bar{n}\right\} $$

Proof

(idea) The μ-average input setting is as in Lemma 1; that is, we plug random function f_S into deterministic algorithms Q. Assuming $\text {card}(Q,\mu ) \leq 2\bar {n}$, by Markov’s inequality, it follows

$$ {\mathbb P}\{\text{card}(Q,f_{\mathbf{S}}) > 4\bar{n}\} \leq \frac{1}{2} . $$

Conditioning on $\text {card}(Q,f_{\mathbf {S}}) \leq 4\bar {n}$, thanks to the symmetry of the measure μ, also for adaptive methods Q, we end up with an estimate on binomial sums (compare proof of Lemma 1).

The changes for Lemma 2 are similar; our lower bounds on $e_{\text {prob}}^{\text {MC}}(n,\delta ,\mathcal {W})$ constitute lower bounds for $\widetilde {e}_{\text {prob}}^{\text {MC-ada}}\bigl (\frac {n}{9},\frac {\delta }{3},\mathcal {W}\bigr )$ as well.

Lemma 6

Let$\bar {n} > 0$and$N,M \in {\mathbb N}$with$N \geq \lfloor 36 \bar {n} \rfloor$andM ≤ N, and letγ > 0. Assume that there are functions$f_{i}: G \to {\mathbb R}$, fori = 1,…,N, satisfying conditions 1 and 2 as in Lemma 2. Then, for any uncertainty level$0 < \delta < \frac {1}{6} 2^{-\lceil M/2 \rceil }$, we have

$$ \widetilde{e}_{\text{prob}}^{\text{MC-ada}}(\bar{n},\delta,\mathcal{W}) \geq \frac{1}{2} \gamma M . $$

Proof

(idea) The μ-average setting is as in Lemma 2; that is, we plug random functions f_I,S into deterministic algorithms Q. Assuming $\text {card}(Q,\mu ) \leq 2\bar {n}$, by Markov’s inequality it follows

$$ {\mathbb P}\{\text{card}(Q,f_{I,\mathbf{S}}) > 6\bar{n}\} \leq \frac{1}{3} . $$

(38)

We aim to bound the expected number m(I,S) of subdomains detected by Q where the function f_I,S does not vanish. Let $Q^{\prime }$ be an algorithm that always uses $n^{\prime } = \lfloor 6\bar {n} \rfloor$ function values from $n^{\prime }$ different subdomains G_i and that computes the same function values f_I,S(x_i) as Q for $i=1,\ldots ,\min \limits \{\text {card}(Q,f_{I,\mathbf {S}}),n^{\prime }\}$. Let $m^{\prime }(I,\mathbf {S})$ denote the expected number of subdomains detected by $Q^{\prime }$ where the function f_I,S does not vanish. For this quantity, we have

$$ {\mathbb{E}} m^{\prime}(I,\mathbf{S}) = \frac{n^{\prime}}{N} M \leq \frac{1}{6} M , $$

and by Markov’s inequality, we conclude

$$ {\mathbb P}\{ m^{\prime}(I,\mathbf{S}) > {\frac{1}{2}} M \} \leq \frac{1}{3} . $$

(39)

Combining Eqs. 38 and 39, we bound

$$ {\mathbb P}\{m(I,\mathbf{S}) \leq {\textstyle\frac{1}{2}} M \} \geq {\mathbb P}\!\left\{\text{card}(Q,f_{I,\mathbf{S}}) \!\leq n^{\prime} \text{ and } m^{\prime}(I,\mathbf{S}) \!\leq\! \frac{1}{2} M \right\} \!\geq 1 - \frac{1}{3} - \frac{1}{3} = \frac{1}{3} . $$

The remaining part of the proof follows the lines of the proof of Lemma 2 after Eq. 15.