We prove the curse of dimensionality for multivariate integration of C r C^r functions: The number of needed function values to achieve an error ϵ \epsilon is larger than c r ( 1 + γ ) d c_r (1+\gamma )^d for ϵ ≤ ϵ 0 \epsilon \le \epsilon _0 , where c r , γ > 0 c_r,\gamma >0 . The proofs are based on volume estimates for r = 1 r=1 together with smoothing by convolution. This allows us to obtain smooth fooling functions for r > 1 r>1 .
We prove the curse of dimensionality for multivariate integration of C r C^r functions: The number of needed function values to achieve an error ϵ \epsilon is larger than c r ( 1 + γ ) d c_r (1+\gamma )^d for ϵ ≤ ϵ 0 \epsilon \le \epsilon _0 , where c r , γ > 0 c_r,\gamma >0 . The proofs are based on volume estimates for r = 1 r=1 together with smoothing by convolution. This allows us to obtain smooth fooling functions for r > 1 r>1 .
We study d-variate approximation for a weighted unanchored Sobolev space having smoothness m ≥ 1. Folk wisdom would lead us to believe that this problem should become easier as its smoothness increases. This is true if we are only concerned with asymptotic analysis: the nth minimal error is of order n^-(m-δ) for any δ > 0. However, it is unclear how long we need to wait before this asymptotic behavior kicks in. How does this waiting period depend on d and m? We prove that no matter how the weights are chosen, the waiting period is at least m^d, even if the error demand ε is arbitrarily close to 1. Hence, for m ≥ 2, this waiting period is exponential in d, so that the problem suffers from the curse of dimensionality and is intractable. In other words, the fact that the asymptotic behavior improves with m is irrelevant when d is large. So, we will be unable to vanquish the curse of dimensionality unless m = 1 , i.e., unless the smoothness is minimal. We then show that our problem can be tractable if m = 1. That is, we can find an ε-approximation using polynomially-many (in d and ε^-1) information operations, even if only function values are permitted. When m = 1, it is even possible for the problem to be strongly tractable, i.e., we can find an ε-approximation using polynomially-many (in ε^-1) information operations, independent of d. These positive results hold when the weights of the Sobolev space decay sufficiently quickly or are bounded finite-order weights, i.e., the d-variate functions we wish to approximate can be decomposed as sums of functions depending on at most ω variables, where ω is independent of d.
We are concerned with the numerical integration of functions from the Sobolev space Hr,mix([0,1]d) of dominating mixed smoothness r∈N over the d-dimensional unit cube. In 1976, K. K. Frolov introduced a deterministic quadrature rule whose worst case error has the order n−r(logn)(d−1)/2 with respect to the number n of function evaluations. This is known to be optimal. 39 years later, Erich Novak and me introduced a randomized version of this algorithm using d random dilations. We showed that its error is bounded above by a constant multiple of n−r−1/2(logn)(d−1)/2 in expectation and by n−r(logn)(d−1)/2 almost surely. The main term n−r−1/2 is again optimal and it turns out that the very same algorithm is also optimal for the isotropic Sobolev space Hs([0,1]d) of smoothness s>d/2. We also added a random shift to this algorithm to make it unbiased. Just recently, Mario Ullrich proved that the expected error of the resulting algorithm on Hr,mix([0,1]d) is even bounded above by n−r−1/2. This thesis is a review of the mentioned upper bounds and their proofs.
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.
This chapter introduces different notions of tractability and intractability. Most notably, the curse of dimensionality occurs when the solution of a multivariate problem would necessitate a number of observations growing exponentially with the number of variables involved. As illustrations, relying on reproducing-kernel techniques, it is shown on the one hand that the integration of trigonometric polynomials is an intractable problem, and on the other hand that integration in weighted Sobolev spaces is a tractable problem provided the weights decay fast enough.