The aim of this research is to develop algorithms to approximate the solutions of problems defined on spaces of d-variate functions, where d can be arbitrarily large. We study quasi-Monte Carlo methods, which in contrast to Monte Carlo methods, use deterministic point sets. These methods converge significantly faster with well chosen points that minimize deterministic error bounds. Additionally, we require that the computational hardness of these methods has only a moderate or no dependence on d. We study this using the information complexity n(d, epsilon), the minimal number of information operations required to achieve an approximation with an error of epsilon or less. If n(d, epsilon) grows exponentially in d, the problem is said to have the 'curse of dimension' and the goal is to vanquish this curse. Our research resulted in several contributions. We studied multivariate integration for a Hilbert space of functions that are invariant under permutations of the variables; this is inspired from the symmetry constraints induced on solutions of the Schrödinger equation for indistinguishable particles. We showed that there exist quasi-Monte Carlo methods that achieve a convergence rate of O(n^−1/2) with the implied constant depending only polynomially on d and under some conditions independent of d (and that shifted rank-1 lattice rules can attain the same). We then provided a construction algorithm for a shifted rank-1 lattice that obtains the (almost) optimal rate of convergence. Next, we extended the use of rank-1 lattice points, traditionally used for the cubature and approximation of periodic functions, to the non-periodic setting. We did this in the cosine space setting, where we extensively studied the use of tent-transformed lattice points for cubature and approximation of nonperiodic functions. We were able to reuse algorithms from the periodic setting by establishing relations between the cosine space and the Korobov space of periodic functions. Finally we studied some special cases of approximation in two dimensions. We derived explicit expressions for various degrees of exactness for the Fibonacci lattice points. We end the thesis with an insight on the Lebesgue constant of trigonometric interpolation using lattice points as interpolation nodes.
The aim of this research is to develop algorithms to approximate the solutions of problems defined on spaces of d-variate functions, where d can be arbitrarily large. We study quasi-Monte Carlo methods, which in contrast to Monte Carlo methods, use deterministic point sets. These methods converge significantly faster with well chosen points that minimize deterministic error bounds. Additionally, we require that the computational hardness of these methods has only a moderate or no dependence on d. We study this using the information complexity n(d, epsilon), the minimal number of information operations required to achieve an approximation with an error of epsilon or less. If n(d, epsilon) grows exponentially in d, the problem is said to have the 'curse of dimension' and the goal is to vanquish this curse. Our research resulted in several contributions. We studied multivariate integration for a Hilbert space of functions that are invariant under permutations of the variables; this is inspired from the symmetry constraints induced on solutions of the Schrödinger equation for indistinguishable particles. We showed that there exist quasi-Monte Carlo methods that achieve a convergence rate of O(n^−1/2) with the implied constant depending only polynomially on d and under some conditions independent of d (and that shifted rank-1 lattice rules can attain the same). We then provided a construction algorithm for a shifted rank-1 lattice that obtains the (almost) optimal rate of convergence. Next, we extended the use of rank-1 lattice points, traditionally used for the cubature and approximation of periodic functions, to the non-periodic setting. We did this in the cosine space setting, where we extensively studied the use of tent-transformed lattice points for cubature and approximation of nonperiodic functions. We were able to reuse algorithms from the periodic setting by establishing relations between the cosine space and the Korobov space of periodic functions. Finally we studied some special cases of approximation in two dimensions. We derived explicit expressions for various degrees of exactness for the Fibonacci lattice points. We end the thesis with an insight on the Lebesgue constant of trigonometric interpolation using lattice points as interpolation nodes.
In this talk I will show the beautiful simplicity of approximating high-dimensional integrals using lattice rules. In current engineering applications it is relatively easy to come up with very high and ultra high dimensional integrals, which might be expectations, that depend on hundreds, thousands, or even an infinite number of variables. As the minimal non-trivial tensor product rule, constructed from a 2-point rule, in 100 dimensions already uses 2^{100} = 1267650600228229401496703205376 ≈ 10^{30} function evaluations—which would take 10^{24} seconds at 1 function evaluation per microsecond and we remember the age of the universe to be only approximately 10^{17} seconds—we all know why to use Monte Carlo or quasi-Monte Carlo methods where we can freely choose the number of function evaluations independent of the number of dimensions. While plain vanilla Monte Carlo methods are very robust and easy to apply, in the case of quasi-Monte Carlo methods a lot more details can pop up. I will first introduce the most elegant—in my biased opinion, which I will defend—of all quasi-Monte Carlo methods: the rank-1 lattice rule. This method is defined by one single integer generating vector together with the total number of points in the rule. Approximating a multivariate integral by this method can be done in one line of Matlab code! As one is often interested in successive approximations I will next introduce a rank-1 lattice sequence. Maybe surprisingly, also here, one simple line of Matlab code is sufficient to calculate a segment of a lattice sequence (with a special property). While for Monte Carlo integration the usual assumption is L2 integrability, leading to an error bound of O(N^{−1/2}). For quasi-Monte Carlo methods we generally work with more involved function space settings, leading to error bounds of the form O(N^{−α}) with α ≥ 1/2. I will show the standard function space settings and dive into the weighted function spaces which are being used in current theory to be able to make the error bounds independent of the number of dimensions. We will gloss over the Korobov space of periodic smooth functions, the unanchored Sobolev space with first mixed derivatives, and the cosine space which is a special space of smooth non-periodic functions. All of which are spaces of so-called mixed dominating smoothness, which in terms of mixed derivatives would mean ∂^{k_1+···+k_s} /(∂x_1^{k_1} · · · ∂x_s^{k_s}) exists for all (k_1, . . . , k_s) ≤ (α, . . . , α). For non-periodic function spaces lattice rules and sequences can only reach O(N^{−1}) convergence. To arrive at higher-order convergence of O(N^{−α}) for non-periodic functions we dive into higher-order Sobolev spaces (of mixed dominating smoothness) in combination with digital nets, but here disguised as a lattice rule, namely polynomial lattice rules. Here, all arithmetic is over a finite field (we will choose the one of order 2) and our lattice rules now take the form of a lattice of polynomials which we map back to points in the unit cube. Higher order can now be obtained by means of the interlacing method from Josef Dick. Although more complicated, again, given the generating matrices of the digital net (as a bunch of integers), and two lines for a magical de Bruijn sequence, we can approximate an integral by such a digital sequence with a single line of (complicated) Matlab code. While Matlab/Octave one-liners might be fun, and somehow instructive, I will also point you to my online resources where code is available to (a) construct good lattice rules, lattice sequences and polynomial lattice rules (for product, order-dependent, product-and-order-dependent aka POD, and smoothness-driven product-and-order dependent aka SPOD) weighted spaces, and (b) generate points given the generating vector or matrices. Armed with this software you will be able to attack your own problems in no time. This talk is based upon the results of collaborations with many colleagues.
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.
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.
High-dimensional integrals arise in a variety of areas, including quantum physics, the physics and chemistry of molecules, statistical mechanics and more recently, in financial applications. In order to approximate multidimensional integrals, one may use Monte Carlo methods in which the quadrature points are generated randomly or quasi-Monte Carlo methods, in which points are generated deterministically. One particular class of quasi-Monte Carlo methods for multivariate integration is represented by lattice rules. Lattice rules constructed throughout this thesis allow good approximations to integrals of functions belonging to certain weighted function spaces. These function spaces were proposed as an explanation as to why integrals in many variables appear to be successfully approximated although the standard theory indicates that the number of quadrature points required for reasonable accuracy would be astronomical because of the large number of variables. The purpose of this thesis is to contribute to theoretical results regarding the construction of lattice rules for multiple integration. We consider both lattice rules for integrals over the unit cube and lattice rules suitable for integrals over Euclidean space. The research reported throughout the thesis is devoted to finding the generating vector required to produce lattice rules that have what is termed a low weighted discrepancy . In simple terms, the discrepancy is a measure of the uniformity of the distribution of the quadrature points or in other settings, a worst-case error. One of the assumptions used in these weighted function spaces is that variables are arranged in the decreasing order of their importance and the assignment of weights in this situation results in so-called product weights . In other applications it is rather the importance of group of variables that matters. This situation is modelled by using function spaces in which the weights are general . In the weighted settings mentioned above, the quality of the lattice rules is assessed by the weighted discrepancy mentioned earlier. Under appropriate conditions on the weights, the lattice rules constructed here produce a convergence rate of the error that ranges from O(n−1/2) to the (believed) optimal O(n−1+δ) for any δ gt 0, with the involved constant independent of the dimension.
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.
L2-Approximation Using Median Lattice Algorithms
Abstract In this paper, we study the problem of multivariate L2 L 2 -approximation of functions belonging to a weighted Korobov space. We propose and analyze a median lattice-based algorithm, inspired by median integration rules, which have attracted significant attention in the theory of quasi-Monte Carlo methods. Our algorithm approximates the Fourier coefficients associated with a suitably chosen frequency index set, where each coefficient is estimated by taking the median over approximations from randomly shifted rank-1 lattice rules with independently chosen generating vectors. We prove that the algorithm achieves, with high probability, a convergence rate of the L2 L 2 -approximation error that is arbitrarily close to optimal with respect to the number of function evaluations. Furthermore, we show that the error bound depends only polynomially on the dimension, or is even independent of the dimension, under certain summability conditions on the weights. Numerical experiments illustrate the performance of the proposed median lattice-based algorithm.