Integral equations with Lipschitz kernels and right-hand sides are intractable for deterministic methods, the complexity increases exponentially in the dimension d . This is true even if we only want to compute a single function value of the solution. For this latter problem we study coin tossing algorithms (or restricted Monte Carlo methods), where only random bits are allowed. We construct a restricted Monte Carlo method with error ε that uses roughly ε −2 function values and only d log 2 ε random bits. The number of arithmetic operations is of the order ε −2 + d log 2 ε. Hence, the cost of our algorithm increases only mildly with the dimension d , we obtain the upper bound C · (ε −2 + d log 2 ε) for the complexity. In particular, the problem is tractable for coin tossing algorithms.
Integral equations with Lipschitz kernels and right-hand sides are intractable for deterministic methods, the complexity increases exponentially in the dimension d . This is true even if we only want to compute a single function value of the solution. For this latter problem we study coin tossing algorithms (or restricted Monte Carlo methods), where only random bits are allowed. We construct a restricted Monte Carlo method with error ε that uses roughly ε −2 function values and only d log 2 ε random bits. The number of arithmetic operations is of the order ε −2 + d log 2 ε. Hence, the cost of our algorithm increases only mildly with the dimension d , we obtain the upper bound C · (ε −2 + d log 2 ε) for the complexity. In particular, the problem is tractable for coin tossing algorithms.
Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.
In this dissertation we study the tractability of the information-based complexity n(ε,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 ε>0 the complexity n(ε,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∞-approximation of certain classes of C∞-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the L∞-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 L1-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 ε>0 the complexity n(ε,d) grows exponentially in d only.
Dimensionally unbounded problems are frequently encountered in practice, such as in simulations of stochastic processes, in particle and light transport problems and in the problems of mathematical finance. This paper considers quasi-Monte Carlo integration algorithms for weighted classes of functions of infinitely many variables, in which the dependence of functions on successive variables is increasingly limited. The dependence is modeled by a sequence of weights. The integrands belong to rather general reproducing kernel Hilbert spaces that can be decomposed as the direct sum of a series of their subspaces, each subspace containing functions of only a finite number of variables. The theory of reproducing kernels is used to derive a quadrature error bound, which is the product of two terms: the generalized discrepancy and the generalized variation. Tractability means that the minimal number of function evaluations needed to reduce the initial integration error by a factor ε \varepsilon is bounded by C ε − p C \varepsilon ^{-p} for some exponent p p and some positive constant C C . The ε \varepsilon -exponent of tractability is defined as the smallest power of ε − 1 \varepsilon ^{-1} in these bounds. It is shown by using Monte Carlo quadrature that the ε \varepsilon -exponent is no greater than 2 for these weighted classes of integrands. Under a somewhat stronger assumption on the weights and for a popular choice of the reproducing kernel it is shown constructively using the Halton sequence that the ε \varepsilon -exponent of tractability is 1, which implies that infinite dimensional integration is no harder than one-dimensional integration.
In this thesis we study a variant of the quadrature problem for stochastic differential equations (SDEs), namely the approximation of expectations E(f(X)), where X=(X(t))t∈[0,1] is the solution of an SDE and f:C([0,1],Rr)→R is a functional, mapping each realization of X into the real numbers. The distinctive feature in this work is that we consider randomized (Monte Carlo) algorithms with random bits as their only source of randomness, whereas the algorithms commonly studied in the literature are allowed to sample from the uniform distribution on the unit interval, i.e., they do have access to random numbers from [0,1]. By assumption, all further operations like, e.g., arithmetic operations, evaluations of elementary functions, and oracle calls to evaluate f are considered within the real number model of computation, i.e., they are carried out exactly. In the following, we provide a detailed description of the quadrature problem, namely we are interested in the approximation of \begin{align*} S(f) = \mathrm{E}(f(X)) \end{align*} for X being the r-dimensional solution of an autonomous SDE of the form \begin{align*} \mathrm{d}X(t) = a(X(t)) \, \mathrm{d}t + b(X(t)) \, \mathrm{d}W(t), \quad t \in [0,1], \end{align*} with deterministic initial value \begin{align*} X(0) = x_0 \in \mathbb{R}^r, \end{align*} and driven by a d-dimensional standard Brownian motion W. Furthermore, the drift coefficient a:Rr→Rr and the diffusion coefficient b:Rr→Rr×d are assumed to be globally Lipschitz continuous. For the function classes \begin{align*} F_{\infty} = \bigl\{f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R} \colon |f(x) - f(y)| \leq \|x-y\|_{\sup}\bigr\} \end{align*} and \begin{align*} F_p = \bigl\{f \colon C([0,1],\mathbb{R}^r) \to \mathbb{R} \colon |f(x) - f(y)| \leq \|x-y\|_{L_p}\bigr\}, \quad 1 \leq p < \infty. \end{align*} we have established the following. \[\] \(\textit{Theorem 1.}\) There exists a random bit multilevel Monte Carlo (MLMC) algorithm \(M\) using \[ L = L(\varepsilon,F) = \begin{cases}\lceil{\log_2(\varepsilon^{-2}}\rceil, &\text{if} \ F = F_p,\\ \lceil{\log_2(\varepsilon^{-2} + \log_2(\log_2(\varepsilon^{-1}))}\rceil, &\text{if} \ F = F_\infty \end{cases} \] and replication numbers Nℓ=Nℓ(ε,F)={⌈(L+1)⋅2−ℓ⋅ε−2⌉,⌈(L+1)⋅2−ℓ⋅max(ℓ,1)⋅ε−2⌉,ifF=Fp,ifF=f∞ for ℓ=0,…,L, for which exists a positive constant c such that \begin{align*} \mathrm{error}(M,F) = \sup_{f \in F} \bigl(\mathrm{E}(S(f) - M(f))^2\bigr)^{1/2} \leq c \cdot \varepsilon \end{align*} and \begin{align*} \mathrm{cost}(M,F) = \sup_{f \in F} \mathrm{E}(\mathrm{cost}(M,f)) \leq c \cdot \varepsilon^{-2} \cdot \begin{cases} (\ln(\varepsilon^{-1}))^2, &\text{if} \ F=F_p,\\ (\ln(\varepsilon^{-1}))^3, &\text{if} \ F=F_\infty \end{cases} \end{align*} for every ε∈]0,1/2[. \[\] Hence, in terms of the ε-complexity \begin{align*} \mathrm{comp}(\varepsilon,F) = \inf\bigl\{\mathrm{cost}(M,F) \colon M \ \text{is a random bit MC algorithm}, \mathrm{error}(M,F) \leq \varepsilon\bigr\} \end{align*} we have established the upper bound \begin{align*} \mathrm{comp}(\varepsilon,F) \leq c \cdot \varepsilon^{-2} \cdot \begin{cases} (\ln(\varepsilon^{-1}))^2, &\text{if} \ F=F_p,\\ (\ln(\varepsilon^{-1}))^3, &\text{if} \ F=F_\infty \end{cases} \end{align*} for some positive constant c. That is, we have shown the same weak asymptotic upper bound as in the case of random numbers from [0,1]. Hence, in this sense, random bits are almost as powerful as random numbers for our computational problem. Moreover, we present numerical results for a non-analyzed adaptive random bit MLMC Euler algorithm, in the particular cases of the Brownian motion, the geometric Brownian motion, the Ornstein-Uhlenbeck SDE and the Cox-Ingersoll-Ross SDE. We also provide a numerical comparison to the corresponding adaptive random number MLMC Euler method. A key challenge in the analysis of the algorithm in Theorem 1 is the approximation of probability distributions by means of random bits. A problem very closely related to the quantization problem, i.e., the optimal approximation of a given probability measure (on a separable Hilbert space) by means of a probability measure with finite support size. Though we have shown that the random bit approximation of the standard normal distribution is 'harder' than the corresponding quantization problem (lower weak rate of convergence), we have been able to establish the same weak rate of convergence as for the corresponding quantization problem in the case of the distribution of a Brownian bridge on L2([0,1]), the distribution of the solution of a scalar SDE on L2([0,1]), and the distribution of a centered Gaussian random element in a separable Hilbert space.
Recently, quasi-Monte Carlo methods have been successfully used for approximating multiple integrals in hundreds of dimensions in mathematical finance, and were significantly more efficient than Monte Carlo methods. To understand the apparent success of quasi-Monte Carlo methods for multiple integration, one popular approach is to study worst-case error bounds in weighted function spaces in which the importance of the variables is moderated by some sequences of weights. Ideally, a family of quasi-Monte Carlo methods in some weighted function space should be strongly tractable. Strong tractability means that the minimal number of quadrature points n needed to reduce the initial error by a factor of ε is bounded by a polynomial in ε⁻¹ independently of the dimension d. Several recent publications show the existence of lattice rules that satisfy the strong tractability error bounds in weighted Korobov spaces of periodic integrands and weighted Sobolev spaces of non-periodic integrands. However, those results were non-constructive and thus give no clues as to how to actually construct these lattice rules. In this thesis, we focus on the construction of quasi-Monte Carlo methods that are strongly tractable. We develop and justify algorithms for the construction of lattice rules that achieve strong tractability error bounds in weighted Korobov and Sobolev spaces. The parameters characterizing these lattice rules are found ‘component-by-component’: the (d + 1)-th components are obtained by successive 1-dimensional searches, with the previous d components kept unchanged. The cost of these algorithms vary from O(nd²) to O(n³d²) operations. With currently available technology, they allow construction of rules easily with values of n up to several million and dimensions d up to several hundred.
Abstract. We consider the problem of estimating the average of a huge set of values. That is, given oracle access to an arbitrary function f: {0, 1} n P −n → [0, 1], we wish to estimate 2 x∈{0,1} n f(x) upto an additive error of ǫ. We are allowed to employ a randomized algorithm that may err with probability at most δ. We survey known algorithms for this problem and focus on the ideas underlying their construction. In particular, we present an algorithm that makes O(ǫ −2 · log(1/δ)) queries and uses n + O(log(1/ǫ)) + O(log(1/δ)) coin tosses, both complexities being very close to the corresponding lower bounds.