In this dissertation we study the tractability of the information-based complexity $n(\varepsilon,d)$ for $d$ -variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $d$ . For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the $L_{\infty}$ -approximation of certain classes of $C^{\infty}$ -functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the $L_{\infty}$ -approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the $L_1$ -approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $\sqrt{d}$ only.In this dissertation we study the tractability of the information-based complexity $n(\varepsilon,d)$ for $d$-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $d$. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the $L_{\infty}$-approximation of certain classes of $C^{\infty}$-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the $L_{\infty}$-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the $L_1$-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance $\varepsilon>0$ the complexity $n(\varepsilon,d)$ grows exponentially in $\sqrt{d}$ only.

arXiv:1704.08213Apr 26, 20178 citations

Empirical Bernstein and betting confidence intervals for randomized quasi-Monte Carlo

Aadit Jain, Fred J. Hickernell, Art B. Owen +1 more

Abstract Randomized quasi-Monte Carlo (RQMC) methods estimate the mean of a random variable by sampling an integrand at $n$ equidistributed points. For scrambled digital nets, the resulting variance is typically $\tilde O(n^{-\theta })$ , where $\theta \in [1,3]$ depends on the smoothness of the integrand and $\tilde O$ neglects logarithmic factors. While RQMC can be far more accurate than plain Monte Carlo (MC), it remains difficult to get confidence intervals on RQMC estimates. We investigate some empirical Bernstein confidence intervals (EBCIs) and hedged betting confidence intervals (HBCIs), both from Waudby-Smith and Ramdas (2024, J. Roy. Statist. Soc. B, 86, 1–27), when the random variable of interest is subject to known bounds. When there are $N$ integrand evaluations partitioned into $R$ independent replicates of $n=N/R$ RQMC points, and the RQMC variance is $\varTheta (n^{-\theta })$ , then an oracle minimizing the width of a Bennett confidence interval would choose $n =\varTheta (N^{1/(\theta +1)})$ . The resulting intervals have a width $\varTheta (N^{-\theta /(\theta +1)})$ . Our empirical investigations had optimal values of $n$ grow slowly with $N$ , HBCI intervals that were usually narrower than the EBCI ones and optimal values of $n$ for HBCI that were equal to or smaller than the ones for the oracle.Abstract Randomized quasi-Monte Carlo (RQMC) methods estimate the mean of a random variable by sampling an integrand at $n$ equidistributed points. For scrambled digital nets, the resulting variance is typically $\tilde O(n^{-\theta })$, where $\theta \in [1,3]$ depends on the smoothness of the integrand and $\tilde O$ neglects logarithmic factors. While RQMC can be far more accurate than plain Monte Carlo (MC), it remains difficult to get confidence intervals on RQMC estimates. We investigate some empirical Bernstein confidence intervals (EBCIs) and hedged betting confidence intervals (HBCIs), both from Waudby-Smith and Ramdas (2024, J. Roy. Statist. Soc. B, 86, 1–27), when the random variable of interest is subject to known bounds. When there are $N$ integrand evaluations partitioned into $R$ independent replicates of $n=N/R$ RQMC points, and the RQMC variance is $\varTheta (n^{-\theta })$, then an oracle minimizing the width of a Bennett confidence interval would choose $n =\varTheta (N^{1/(\theta +1)})$. The resulting intervals have a width $\varTheta (N^{-\theta /(\theta +1)})$. Our empirical investigations had optimal values of $n$ grow slowly with $N$, HBCI intervals that were usually narrower than the EBCI ones and optimal values of $n$ for HBCI that were equal to or smaller than the ones for the oracle.

arXiv:2504.18677Information and Inference A Journal of the IMAFeb 6, 20260 citations

In this dissertation we study the tractability of the information-based complexity

n(\varepsilon,d)

for

d

-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance

\varepsilon>0

the complexity

n(\varepsilon,d)

grows exponentially in

d

. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the

L_{\infty}

-approximation of certain classes of

C^{\infty}

-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the

L_{\infty}

-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the

L_1

-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance

\varepsilon>0

the complexity

n(\varepsilon,d)

grows exponentially in

\sqrt{d}

only.

Abstract Randomized quasi-Monte Carlo (RQMC) methods estimate the mean of a random variable by sampling an integrand at

n

equidistributed points. For scrambled digital nets, the resulting variance is typically

\tilde O(n^{-\theta })

, where

\theta \in [1,3]

depends on the smoothness of the integrand and

\tilde O

neglects logarithmic factors. While RQMC can be far more accurate than plain Monte Carlo (MC), it remains difficult to get confidence intervals on RQMC estimates. We investigate some empirical Bernstein confidence intervals (EBCIs) and hedged betting confidence intervals (HBCIs), both from Waudby-Smith and Ramdas (2024, J. Roy. Statist. Soc. B, 86, 1–27), when the random variable of interest is subject to known bounds. When there are

N

integrand evaluations partitioned into

R

independent replicates of

n=N/R

RQMC points, and the RQMC variance is

\varTheta (n^{-\theta })

, then an oracle minimizing the width of a Bennett confidence interval would choose

n =\varTheta (N^{1/(\theta +1)})

. The resulting intervals have a width

\varTheta (N^{-\theta /(\theta +1)})

. Our empirical investigations had optimal values of

n

grow slowly with

N

, HBCI intervals that were usually narrower than the EBCI ones and optimal values of

n

for HBCI that were equal to or smaller than the ones for the oracle.