We study the worst case integration error of combinations of quadrature rules in a reproducing kernel Hilbert space. We show that the error, with respect to the total number N of function evaluations used, cannot decrease faster than O(N^{-1}) in the case where several quasi-Monte Carlo rules are combined to a compound quasi-Monte Carlo rule. However, if the errors of the quadrature rules constituting the compound rule have an order of convergence O(N^{-a}) for a > 1 then, by introducing weights, this order of convergence can be shown to be recovered for the compound rule. We apply our results to the case of lattice sequences.
We study the worst case integration error of combinations of quadrature rules in a reproducing kernel Hilbert space. We show that the error, with respect to the total number N of function evaluations used, cannot decrease faster than O(N^{-1}) in the case where several quasi-Monte Carlo rules are combined to a compound quasi-Monte Carlo rule. However, if the errors of the quadrature rules constituting the compound rule have an order of convergence O(N^{-a}) for a > 1 then, by introducing weights, this order of convergence can be shown to be recovered for the compound rule. We apply our results to the case of lattice sequences.
We study the worst case integration error of combinations of quadrature rules in a reproducing kernel Hilbert space. We show that the error, with respect to the total number N of function evaluations used, cannot decrease faster than O(N−1) for an equal-weight rule. However, if the errors of the quadrature rules constituting a compound rule have an order of convergence O(N−α) for α>1 then, by introducing weights, this order of convergence can be shown to be recovered for the compound rule. The theory applies to lattice sequences as well as digital sequences.
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 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.
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.
This paper is a contemporary review of QMC (‘quasi-Monte Carlo’) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1] s , where s may be large, or even infinite. After a general introduction, the paper surveys recent developments in lattice methods, digital nets, and related themes. Among those recent developments are methods of construction of both lattices and digital nets, to yield QMC rules that have a prescribed rate of convergence for sufficiently smooth functions, and ideally also guaranteed slow growth (or no growth) of the worst-case error as s increases. A crucial role is played by parameters called ‘weights’, since a careful use of the weight parameters is needed to ensure that the worst-case errors in an appropriately weighted function space are bounded, or grow only slowly, as the dimension s increases. Important tools for the analysis are weighted function spaces, reproducing kernel Hilbert spaces, and discrepancy, all of which are discussed with an appropriate level of detail.
This paper is a contemporary review of quasi-Monte Carlo (QMC) methods, that is, equal-weight rules for the approximate evaluation of high-dimensional integrals over the unit cube [0,1]s. It first introduces the by-now standard setting of weighted Hilbert spaces of functions with square-integrable mixed first derivatives, and then indicates alternative settings, such as non-Hilbert spaces, that can sometimes be more suitable. Original contributions include the extension of the fast component-by-component (CBC) construction of lattice rules that achieve the optimal convergence order (a rate of almost 1/N, where N is the number of points, independently of dimension) to so-called “product and order dependent” (POD) weights, as seen in some recent applications. Although the paper has a strong focus on lattice rules, the function space settings are applicable to all QMC methods. Furthermore, the error analysis and construction of lattice rules can be adapted to polynomial lattice rules from the family of digital nets. doi:10.1017/S1446181112000077