Abstract
We study the complexity of approximating integrals of smooth functions at absolute precision ε > 0 with confidence level 1 − δ ∈ (0, 1). The optimal error rate for multivariate functions from classical isotropic Sobolev spaces W r p (G) with sufficient smoothness on bounded Lipschitz domains G ⊂ 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.
Introduction
We want to compute the integral
of f : G → R from the unit ball B W of a (semi-)normed linear space W of functions defined on a domain G ⊂ R d where we are only allowed to use function values as information within randomized algorithms. The focus lies on the (ε, δ)-complexity n MC prob (ε, δ, W), that is, the minimal number n of function values needed for randomized algorithms A n in order to approximate the integral (1) such that
where · W is the (semi-)norm of W. A method with this property of guaranteeing a small (absolute) error ε > 0 with confidence 1 − δ ∈ (0, 1) (or uncertainty δ) for inputs from the unit ball B W is called (ε, δ)-approximating in W, see also [16] . We also consider the n-th minimal probabilistic Monte Carlo error at uncertainty δ, defined by e MC prob (n, δ, W) := inf {ε > 0 | ∃ (ε, δ)-approximating algorithm A n in W} .
The probabilistic error criterion from above is less common in information-based complexity (IBC) where the standard notion of Monte Carlo error is some type of mean error. In general, for some ℓ ≥ 1 the n-th minimal ℓ-mean Monte Carlo error is given by e MC ℓ-mean (n, W) := inf
Here, the infimum is taken over all randomized algorithms which use at most n function values. Most frequently studied are the root mean squared error (RMSE), that is, e MC 2-mean , as well as the expected error e MC 1-mean . Accordingly, we define the ε-complexity n MC ℓ-mean (ε, W) as the minimal number of function values needed by a randomized algorithm that guarantees a worst case ℓ-mean error smaller than ε. For more details on IBC we refer to the books [22, 23, 24, 26] .
One might argue that the error criterion does not matter. However, this is not true. For example, using Markov's inequality it is always possible to construct (ε, δ)-approximating algorithms once we know methods which work for arbitrarily small mean errors. That way, however, the cost estimates are not optimal in terms of the δ-dependence, namely polynomial rather than logarithmic. In some situations this can be fixed by using more advanced inequalities such as Hoeffding bounds. In other situations commonly known algorithms may need to be modified which lead to more robust methods less prone to outliers. For this reason the probabilistic criterion is frequently used in statistics, see for example [8, 11, 12, 13] . Furthermore, there are numerical problems which can be solved with respect to the probabilistic (ε, δ)-criterion but the mean error is unbounded, see [16] . In other words, this criterion seems to be the right one for the concept of solvability.
In Section 2 we provide two generic lower bounds for the n-th minimal probabilistic Monte Carlo error based on bump functions. In Section 3 we discuss several approaches for deriving upper error bounds on Sobolev classes and discuss in which cases they lead to optimal rates. We mainly consider classical isotropic Sobolev spaces W r p (G) on domains G ⊆ R d . For integer smoothness r ∈ N 0 and integrability parameter 1 ≤ p ≤ ∞, these spaces are given by
with the usual modification for p = ∞ and the weak derivative
Note that for r = 0 we obtain the Lebesgue spaces L p (G).
Our main result is for spaces W r p (G) on bounded Lipschitz domains G ⊂ R d (see [21] for a definition), and with sufficient smoothness, rp > d. In asymptotic notation (see definitions below) it states
with q := min{p, 2}, or equivalently
see Theorem 2.3 and Theorem 3.6. The condition rp > d guarantees that the space W r p (G) is compactly embedded in the space of continuous functions, see for instance [1] . Only then function evaluations are well defined and there exist deterministic integration methods, which in this case provide error bounds with rate n −r/d . These worst case bounds come into play if we demand extremely high confidence 1 − δ close to 1. It also turns out that for p = 1 the uncertainty δ does not play any role, which shows that deterministic methods are optimal in that case. In the power of n, we recover the well known gain of 1 − 1/p for 1 < p < 2, and 1/2 for p ≥ 2, which Monte Carlo methods achieve compared to deterministic methods. The influence of the uncertainty δ grows with the gain in the error rate. In terms of the complexity (6) we observe that the higher the smoothness r the weaker the dependence on δ.
Asymptotic notation: For functions e, f : N×(0, 1) → R we use the notation e(n, δ) f (n, δ), meaning that there is some n 0 ∈ N and δ 0 ∈ (0, 1) such that e(n, δ) ≤ cf (n, δ) with some (possibly (d, r)-dependent) constant c > 0 for all n ≥ n 0 and δ ∈ (0, δ 0 ). Sometimes we add the restriction n log δ −1 , then e(n, δ) ≤ cf (n, δ) is only meant to hold for δ ∈ (0, δ 0 ) and n ≥ n 0 log δ −1 . Similarly we denote asymptotics for complexity functions n(ε, δ), describing a behaviour for small ε, δ > 0. Asymptotic equivalence e(n, δ) ≍ f (n, δ) is a shorthand for e(n, δ) f (n, δ) e(n, δ). The notion e(n, δ) ≺ f (n, δ) means "e(n, δ) f (n, δ) but not f (n, δ) e(n, δ)".
Lower bounds
We start with the lower bounds as these are easily obtained for the whole parameter range of the function spaces we consider.
Auxiliary lemmas
As before, let W be a space of functions defined on a domain G, equipped with a (semi-)norm · W . An abstract Monte Carlo algorithm defined for such functions is a family
with elements ω from a probability space (Ω, Σ, P), such that the error functional ω → |A
is the information we collect about a problem instance f , from which the output A ω n (f ) = φ ω (y) is generated. One might consider adaptive strategies to acquire information, that is, x ω i might depend on the previously obtained information y 1 , . . . , y i−1 . Our lower bounds do hold for this type of algorithms, but the upper bounds we present are based on non-adaptive methods. For simplicity, in this paper we restrict to methods with fixed cardinality n. In general, the number of function values an algorithm collects might be random and even depend on the input, see for instance [8, 12, 16] . Let us mention here that our auxiliary lemmas on lower bounds, Lemma 2.1 and 2.2, would then still hold with slightly worse constants.
In the spirit of Bakhvalov [4] , for proving lower bounds we switch to an average input setting with a discrete probability measure µ supported within the input set-which in our case is the unit ball B W of the space W-and make use of the relation
where the infimum is taken over all deterministic integration methods Q n that use n function values. (For fixed ω, the realisation A ω n of a given algorithm can be regarded as a deterministic algorithm.) In the proof of the lower bounds we use the implication
where e MC prob (A n , δ, W) is the infimum of all ε > 0 such that the algorithm A n is (ε, δ)-approximating in W.
Depending on the integrability index p of the Sobolev classes we choose different probability measures µ in order to obtain appropriate lower bounds. Similarly to [20, Proposition 1 and 2 in Section 2.2.4] we have the following two generic lemmas, now for the probabilistic instead of the root mean squared error. The first one applies for integrability 2 ≤ p ≤ ∞. Proof. Let µ be the uniform distribution on the finite set
Let Q n : F → R be a deterministic algorithm using n function values. Without loss of generality, we may assume that the algorithm computes function values
. . , n. Hence, from the i-th piece of information we learn whether s i = +1 or −1 for f = f s . Note that, given the information y = N(f ), there are still k := N − n unknown signs s i . The conditional distribution of INT(f ) given y can be represented as the distribution of g y + γX k where
s i , and
Since this is the situation for all information y = (s 1 , . . . , s n ), we obtain
At most k ′ := ⌊ε/γ⌋ + 1 terms are removed from the binomial sum, optimally the central ones, so we have
We employ Lemma A.1 twice, namely, for odd k with
as well as for even k with
In order to match the conditions of Lemma A.1, we restrict to ε/γ ≤ (k − 6)/4. Hence under that assumption we have
Note that k = N − n ≥ (5n + 6) − n = 4n + 6, so then the condition ε/γ ≤ n is sufficient for (9) to hold. The right-hand side of (9) can be further simplified via
, exploiting k > 4n and also n ≥ 17. For 0 < ε ≤ γn this leads to
By Bakhvalov's trick (7) this is a lower bound for the worst case uncertainty
Regarding the right-hand side of (10) as a given δ, the implication (8) finally provides the assertion. Pay attention that for too small δ, namely 0 < δ < 1 3
4
−n , isolating ε in (10) is misleading to delusive error bounds exceeding γn which, however, violates the conditions on ε. In this case we can only conclude that ε = γn is a lower bound for e MC prob (n, δ, W).
The following result will be useful for integrability 1 < p < 2.
Lemma 2.2. For n ∈ N and a natural number N ≥ 4n, assume that there are functions f i : G → R, with i = 1, . . . , N, satisfying the following conditions:
and INT(f i ) = γ for some γ > 0;
2. for I ⊂ {1, . . . , N} with #I = M for some given natural number M ≤ N, and for signs s i ∈ {±1}, the function f I,s :
Then, for any 0 < δ <
Proof. Let µ be the uniform distribution on the finite set
Let Q n : F → R be a deterministic algorithm using n function values. Without loss of generality, we may assume that the algorithm computes function values
. . , n. Hence, from the i-th piece of information we learn whether i ∈ I, and if so, whether s i = +1 or −1 within the representation
Let m(f ) := #(I ∩ {1, . . . , n}) denote the number of detected subdomains G i where the function f is non-zero. Under µ, the random variable m(·) is distributed according to a hypergeometric distribution with population of size N containing M ≤ N items of interest and admitting n < N draws without replacement. The expected value is
and using Markov's inequality we conclude
Given the information (f (x 1 ), . . . , f (x n )) = y with m(f ) = m, there are still k := M − m unknown s i for subdomains G i where the function does not vanish and the conditional distribution of INT(f ) is given similarly to the proof of Lemma 2.1 (only n is substituted by m). Hence, the conditional uncertainty can be quantified via a binomial sum. For 0 < ε ≤ Mγ, up to
M⌉ terms are removed, and we obtain
This bound is the same for all information outcomes y with the same number m(f ) = m of detected non-zero subdomains, and for k ≥ k ′ , by Lemma A.2, we further estimate
Note that m ≤ 1 2 (12) can be used under the condition formulated in (11) . Hence,
By Bakhvalov's trick (7) this is a lower bound for the worst case uncertainty sup f W ≤1 P{|A n (f ) − INT(f )| > ε}, and for 0 < δ < 
Lower bounds for Sobolev classes
The norms of classical Sobolev spaces W r p (G) with integrability index p possess the property that for any decomposition of the support of a function f ∈ W r p (G) into essentially disjoint sub-domains, say G 1 , . . . , G M , we have
The smoothness has an effect on scalings, namely for functions ϕ : R d → R and ψ(x) := ϕ(mx − i), with m > 0 and i ∈ R d , we have the following well known relation between the derivatives,
For m ≥ 1 this leads to the scaling property
If supp ϕ, supp ψ ⊆ G, then this relation holds also for the norms of the restricted space W r p (G). 
Proof. Since the interior of G is nonempty there exists a cubic subdomain. We restrict to functions which are supported within that rectangular subdomain, and by scaling, without loss of generality, we may assume (14) with M = N we have
If 1 ≤ p < 2, we restrict to 0 ≤ δ < 1/4 and choose m :
, and easily see that M ≤ 4n ≤ N is fulfilled. Here, put f i := m −r (N/M) 1/p ψ i , and note that by (13) and (14) we have
We have γ = INT f i = m −r−d+d/p M −1/p , and Lemma 2.2 implies
For small δ ∈ (0, 2 −2n−1 ), however, we may just choose M = 4n, and similarly we obtain e
which finishes the proof. 
, where 1 ≤ p < ∞, see for instance the book of Triebel [27, p. 36 ]. For such spaces the inequality (13) does not hold anymore. However, we can still construct fooling functions composed of bumps on disjoint subcubes with random sign, but we need to introduce an additional constant in order to take the non-local nature of fractional derivatives into account. Let us consider an easier example: Namely, classes of Hölder continuous functions with fractional smoothness 0 < β ≤ 1 (and integrability parameter p = ∞) given by
With the choice f i := 1 2 m −β ψ i , within the proof above, one can ensure (15) . Thus, loosing just a factor 1/2, we still have the same order as should be expected from generalizing the integer smoothness case,
This fits very well to the upper bounds of Theorem 3.9.
3 Upper Bounds
Probability amplification
One of the most elementary methods of 'probability amplification' is the so-called 'median trick', see Alon et al. [2] and Jerrum et al. [14] . The following proposition is a minor modification of [19, Proposition 2.1, in particular (2.6)] from Niemiro and Pokarowski, now adapted to the language of algorithms and IBC. As in Section 2.1, we consider a general function space W equipped with a (semi-)norm · W and take its unit ball B W as input set.
Proposition 3.1 (Median trick). For ε > 0 let A m be an arbitrary Monte Carlo algorithm such that
where 0 < α < 1/2. For an odd natural number k, define
as the median of k independent realisations of A m . Then
The previous proposition can be used to derive upper bounds for the probabilistic (ε, δ)-complexity n MC prob (ε, δ, W) in terms of the ℓ-mean error complexity n 
In particular, if e MC ℓ-mean (n, W) n −̺ for some ̺ > 0, then we have
Proof. Without loss of generality, we assume that n MC ℓ-mean (8 −1/ℓ ε, W) < ∞, otherwise the claimed inequality is trivial. Hence, there is an m ∈ N such that e 
Thus, for any f ∈ B W by Markov's inequality we have
Now we aim to apply Proposition 3.1 with k chosen as the smallest odd natural number that satisfies k ≥ 2 log 2 (2δ) −1 . (Note that k ≤ 2 log 2 δ −1 for 0 < δ ≤ 1/2.) Then we obtain the desired complexity bound
In terms of the error quantities, for fixed m and odd k ≥ 2 log 2 (2δ) −1 we can state
Assuming e MC ℓ-mean (m, W) ≤ C m −̺ for m ≥ m 0 ∈ N, and given an information budget n ≥ 2m 0 log 2 δ −1 , put m := ⌊n/(2 log 2 δ −1 )⌋ ≍ n/ log δ −1 . Then the assertion follows by the assumption with hidden constant 2 log 2
The lower bounds of Theorem 2.3 match the upper bounds from Theorem 3.2, iff the rate of convergence is related to the integrability index by ̺ = 1 − 1/q where q := min{p, 2}. This is only the case for smoothness r = 0, i.e., when L p -balls are the considered input sets. In that case,
Here we used estimates of the q-mean error for the standard i. Remark 3.4 (Alternatives to the median trick). Catoni [5] proposes an alternative scheme based on random samples of L p -functions, which suppresses outliers and (in contrast to the median trick) is symmetric in the sense that permuting the sample data does not change the result. Compare also Huber [13] where this approach is combined with the median trick. Unfortunately, their methods are not homogeneous and shift invariant, that is, for the algorithm, say A, in general A(af + b) = aA(f ) + b does not hold.
Separation of the main part
Separation of the main part, also known as control variates, is a well established technique of variance reduction which uses the approximation of functions with respect to an L q -norm in order to exploit the smoothness of the given input set. Within this section we assume that G ⊂ R d is a bounded Lipschitz domain, see [21] for details. For q ≥ 1 let L q (G) be the Lebesgue space equipped with the norm · Lq(G) . Let W ⊂ L q (G) be a normed linear space with corresponding unit ball B W and assume that function evaluations are continuous (well-defined) on W.
For the approximation step we only consider linear methods
with nodes x i ∈ G and functions g i ∈ L q (G), where G g i (x) dx is known for any i = 1, . . . , n. The minimal L q -approximation error of such methods is denoted by
and the ε-complexity n det (ε, W ֒→ L q ) is the minimal number of function evaluations needed in order to achieve an L q -approximation error smaller than ε. The idea is to apply a Monte Carlo integration method M n : L q → R to the difference f −g between approximating and original function, while the integral of g = A n (f ) is considered to be known. This approach leads to the following theorem.
Theorem 3.5 (Separation of the main part). For any n ∈ N we have
Proof. Let A n be a linear approximation method, see (19) , which guarantees for any f ∈ B W and some α > 0 that
Further, let M ω n be a Monte Carlo method which approximates INT h for inputs h ∈ L q . With this we define a new Monte Carlo method Q ω 2n (a randomized quadrature rule) as follows:
at nodes x 1 , . . . , x n ∈ G.
Return
Note that, the information y = (f (x 1 ) , . . . , f (x n ), f (X ω n+1 ), . . . , f (X ω 2n )) suffices to execute the algorithm, namely,
f (x i ) INT g i , and
Indeed, INT g i is assumed to be precomputed and computing function values of g i is considered to belong to the combinatorial cost, rather than the information cost of the algorithm. By writing ε = αε ′ , the uncertainty of the algorithm can be traced back to the uncertainty of
Optimal methods A n and M ω n lead to α → e det (n, W ֒→ L q ) and ε ′ → e MC prob (n, δ, L q ), while keeping the uncertainty bounded by δ, thus letting ε approach the stated error bound.
As long as function evaluations are continuous, it suffices to work with deterministic approximation methods of the form (19) . Note that for isotropic Sobolev spaces W r p (G) on bounded Lipschitz domains G ⊂ R d , this is the case iff rp > d. In this setting it is well known that with q := min{p, 2},
For G = [0, 1] d , this result can be achieved with piecewise polynomial interpolation, see for instance Heinrich [9, Proposition 5.1], technical details of approximation methods are contained in Ciarlet [6] . For the general case of bounded Lipschitz domains G ⊂ R d , see Novak and Triebel [21, Theorem 23] . From this we conclude optimal upper bounds. Proof. The lower bounds follow from Theorem 2.3. For n log δ −1 , we combine (18) with (21) For n ≺ log δ −1 we rely on deterministic quadrature. This problem is easier than approximation in the sense that if g ∈ L q (G) is an approximation of f , then
See also Novak [20, 1.3 .12] for a direct derivation on
Remark 3.7 (Lower smoothness). The condition rp > d is necessary to guarantee that the evaluation of functions on W r p (G) for 1 < p ≤ ∞ is well-defined. (For p = 1, the condition r = d is also sufficient, but then deterministic methods already provide the optimal error rates.) In the cases 1 < p < ∞ with rp ≤ d one can still use separation of the main part, but with a randomized approximation scheme, see Heinrich [10] for the case G = [0, 1] d . That way, for any 1 ≤ p ≤ ∞ and general r ∈ N we have
with q := min{p, 2}. Probability amplification, see Theorem 3.2, yields
The power of log δ −1 in this upper bound may exceed the power of the lower bound by r/d which can get close to 1 for p → 1. We conjecture that the influence of δ is smaller at least if one is close to the regime where functions are continuous.
Instead of deterministic algorithms of the form (19) one might also consider general randomized methods for the approximation of functions in W. For those let e MC prob (n, δ, W ֒→ L q ) be the smallest ε > 0, such that there exists a general randomized approximation algorithm satisfying
Similarly to Theorem 3.5 one can show that
Such an approach, however, seems to rely on complicated algorithms, since nonlinearity might be inevitable in order to suppress outliers. There might be easier implementable Monte Carlo methods for integration which achieve a better order of convergence without relying on the approximation of functions. Such methods are needed in spaces of mixed smoothness, see the discussion in Section 4. Anyway, studying Sobolev embeddings W r p (G) ֒→ L q (G) in terms of approximation with high confidence within the regime d(q − p) < rqp ≤ dq for general integrability parameters 1 ≤ p, q < ∞, is an interesting problem on its own, compare Heinrich [10] . 
Stratified sampling
d be a sequence of independent random variables with X i uniformly distributed in G i . Then, stratified sampling is given by
which uses m d function evaluations of f . Compared to the separation of the main part, stratified sampling is easier to implement. In some cases we show that it provides optimal results in terms of the (ε, δ)-complexity. Since the structure only depends on the information budget and not on δ (compare the median trick), we obtain a universal method in terms of the uncertainty.
We use Hoeffding's inequality which is, for the convenience of the reader, stated in the following proposition. 
First, we consider Hölder classes C β ([0, 1] d ) with smoothness β ∈ (0, 1], see (16) . Compare also [4] for the result in terms of the root mean squared error. 
This is guaranteed to be at most δ for
Given an information budget n ∈ N, we choose m := ⌊n Proof. We start with the one-dimensional case considering the method S 1 n , see (23) . Hence, the unit interval [0, 1] is split into intervals G 0 , . . . , G n−1 of length n −1 . For
Hence, on the ith interval G i we have
where we used Jensen's inequality. Furthermore
, exploiting q ≤ 2 in the last inequality. Applying Hoeffding's inequality, Proposition 3.
This is guaranteed to be at most δ for
which shows the assertion for d = 1.
. Namely, incorporating scaling we bound the spread of function values within G i by
with some constant C > 0 depending only on p and d. From this, with p > d ≥ 2, we conclude
compare (13) . Choosing m := ⌈n 1/d ⌉, we obtain the right order by applying Hoeffding's inequality similarly to the one-dimensional case.
Remark 3.11. The one-dimensional problem contains cases of small integrability 1 < p < 2 for which we do not obtain the optimal δ-dependence. It is not known to us whether this is a deficiency of the method or of the proof. In that case, we may use separation of the main part, which is equally simple as f may be approximated on G i by just one function value.
In the case of discontinuous functions, p < d, it remains challenging to find methods which detect and discourage outliers within stratified sampling. One idea might be to take several function values out of each subcube. This could improve also on the above mentioned case d = 1 and 1 < p < 2. Any result in that direction might offer reasonable alternatives to control variates, where the case of small smoothness is also open.
Challenges in mixed smoothness spaces
In the recent years spaces of dominating mixed smoothness gained a lot of interest in the study of high-dimensional problems. For a survey on this topic we refer to the paper of Dũng, Temlyakov, and Ullrich [7] .
For integer smoothness r ∈ N and integrability 1 ≤ p ≤ ∞, on domainswith q := min{p, 2}. Unfortunately, we do not achieve the optimal dependence on δ. The original algorithm alone does not possess desirable confidence guarantees, as the following one-dimensional counter example shows. This is not surprising as the number of random parameters is fixed by the dimension and thus we do not expect to observe concentration phenomena, which is in contrast to stratified sampling.
see [7, Theorem 8.14] . This catches the case n ≺ log δ −1 . It remains a challenging open problem to find randomized integration methods which have the right dependence on the uncertainty while fully exploiting the smoothness.
A Technical Proofs
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. ].
Proof. First, recall that k ⌊k/2⌋ < 2 k / π ⌈k/2⌉, which for even k follows from Stirling's formula and for odd k can be derived from k + 1 via Pascal's rule. Hence, .
Next, we use 1 − x ≥ 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 ≤

{'paper_id': '119598242', 'title': 'Optimal confidence for Monte Carlo integration of smooth functions', 's2_url': 'https://api.semanticscholar.org/CorpusID:119598242', 'source': 'S2ORC'}