Strong tractability of integration using scrambled Niederreiter points

We study the randomized worst-case error and the randomized error of scrambled quasi-Monte Carlo (QMC) quadrature as proposed by Owen. The function spaces considered in this article are the weighted Hilbert spaces generated by Haar-like wavelets and the weighted Sobolev-Hilbert spaces. Conditions are found under which multivariate integration is strongly tractable in the randomized worst-case setting and the randomized setting, respectively. The -exponents of strong tractability are found for the scrambled Niederreiter nets and sequences. The sufficient conditions for strong tractability for Sobolev spaces are more lenient for scrambled QMC quadratures than those for deterministic QMC net quadratures.

     

Good Lattice Rules in Weighted Korobov Spaces with General Weights

We study the problem of multivariate integration and the construction of good lattice rules in weighted Korobov spaces with general weights. These spaces are not necessarily tensor products of spaces of univariate functions. Sufficient conditions for tractability and strong tractability of multivariate integration in such weighted function spaces are found. These conditions are also necessary if the weights are such that the reproducing kernel of the weighted Korobov space is pointwise non-negative. The existence of a lattice rule which achieves the nearly optimal convergence order is proven. A component-by-component (CBC) algorithm that constructs good lattice rules is presented. The resulting lattice rules achieve tractability or strong tractability error bounds and achieve nearly optimal convergence order for suitably decaying weights. We also study special weights such as finite-order and order-dependent weights. For these special weights, the cost of the CBC algorithm is polynomial. Numerical computations show that the lattice rules constructed by the CBC algorithm give much smaller worst-case errors than the mean worst-case errors over all quasi-Monte Carlo rules or over all lattice rules, and generally smaller worst-case errors than the best Korobov lattice rules in dimensions up to hundreds. Numerical results are provided to illustrate the efficiency of CBC lattice rules and Korobov lattice rules (with suitably chosen weights), in particular for high-dimensional finance problems.     

Lattice Algorithms for Multivariate L ∞ Approximation in the Worst-Case Setting

We approximate d-variate functions from weighted Korobov spaces with the error of approximation defined in the L _∞ sense. We study lattice algorithms and consider the worst-case setting in which the error is defined by its worst-case behavior over the unit ball of the space of functions. A lattice algorithm is specified by a generating (integer) vector. We propose three choices of such vectors, each corresponding to a different search criterion in the component-by-component construction. We present worst-case error bounds that go to zero polynomially with n ^?1, where n is the number of function values used by the lattice algorithm. Under some assumptions on the weights of the function space, the worst-case error bounds are also polynomial in d, in which case we have (polynomial) tractability, or even independent of d, in which case we have strong (polynomial) tractability. We discuss the exponents of n ^?1 and stress that we do not know if these exponents can be improved.     

Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration

In this paper we study quasi-Monte Carlo integration of smooth functions using digital nets. We fold digital nets over ${\mathbb{Z}}_b$ by means of the $b$-adic tent transformation, which has recently been introduced by the authors, and employ such folded digital nets as quadrature points. We first analyze the worst-case error of quasi-Monte Carlo rules using folded digital nets in reproducing kernel Hilbert spaces. Here we need to permit digital nets with “infinite digit expansions”, which are beyond the scope of the classical definition of digital nets. We overcome this issue by considering the infinite product of cyclic groups and the characters on it. We then give an explicit means of constructing good folded digital nets as follows: we use higher order polynomial lattice point sets for digital nets and show that the component-by-component construction can find good folded higher order polynomial lattice rules that achieve the optimal convergence rate of the worst-case error in certain Sobolev spaces of smoothness of arbitrarily high order.     

On the approximation of smooth functions using generalized digital nets

In this paper, we study an approximation algorithm which firstly approximates certain Walsh coefficients of the function under consideration and consequently uses a Walsh polynomial to approximate the function. A similar approach has previously been used for approximating periodic functions, using lattice rules (and Fourier polynomials), and for approximating functions in Walsh Korobov spaces, using digital nets. Here, the key ingredient is the use of generalized digital nets (which have recently been shown to achieve higher order convergence rates for the integration of smooth functions). This allows us to approximate functions with square integrable mixed partial derivatives of order α>1$\alpha >1$ in each variable. The approximation error is studied in the worst case setting in the _L2$L_2$ norm. We also discuss tractability of our proposed approximation algorithm, investigate its computational complexity, and present numerical examples.     

Constructions of general polynomial lattice rules based on the weighted star discrepancy

In this paper we study construction algorithms for polynomial lattice rules modulo arbitrary polynomials. Polynomial lattice rules are a special class of digital nets which yield well distributed point sets in the unit cube for numerical integration.Niederreiter obtained an existence result for polynomial lattice rules modulo arbitrary polynomials for which the underlying point set has a small star discrepancy and recently Dick, Leobacher and Pillichshammer introduced construction algorithms for polynomial lattice rules modulo an irreducible polynomial for which the underlying point set has a small (weighted) star discrepancy.In this work we provide construction algorithms for polynomial lattice rules modulo arbitrary polynomials, thereby generalizing the previously obtained results. More precisely we use a component-by-component algorithm and a Korobov-type algorithm. We show how the search space of the Korobov-type algorithm can be reduced without sacrificing the convergence rate, hence this algorithm is particularly fast. Our findings are based on a detailed analysis of quantities closely related to the (weighted) star discrepancy.     

Tractability of Integration in Non-periodic and Periodic Weighted Tensor Product Hilbert Spaces

We study strong tractability and tractability of multivariate integration in the worst case setting. This problem is considered in weighted tensor product reproducing kernel Hilbert spaces. We analyze three variants of the classical Sobolev space of non-periodic and periodic functions whose first mixed derivatives are square integrable. We obtain necessary and sufficient conditions on strong tractability and tractability in terms of the weights of the spaces. For the three Sobolev spaces periodicity has no significant effect on strong tractability and tractability. In contrast, for general reproducing kernel Hilbert spaces anything can happen: we may have strong tractability or tractability for the non-periodic case and intractability for the periodic one, or vice versa.     

Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules

In this paper we prove the existence of digitally shifted polynomial lattice rules which achieve strong tractability results for Sobolev spaces of arbitrary high smoothness. The convergence rate is shown to be the best possible up to a given degree of smoothness of the integrand. Indeed we even show the existence of polynomial lattice rules which automatically adjust themselves to the smoothness of the integrand up to a certain given degree.Further we show that strong tractability under certain conditions on the weights can be obtained and that polynomial lattice rules exist for which the worst-case error can be bounded independently of the dimension. These results hold independent of the smoothness.     

Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

We show how to obtain a fast component-by-component construction algorithm for higher order polynomial lattice rules. Such rules are useful for multivariate quadrature of high-dimensional smooth functions over the unit cube as they achieve the near optimal order of convergence. The main problem addressed in this paper is to find an efficient way of computing the worst-case error. A general algorithm is presented and explicit expressions for base 2 are given. To obtain an efficient component-by-component construction algorithm we exploit the structure of the underlying cyclic group. We compare our new higher order multivariate quadrature rules to existing quadrature rules based on higher order digital nets by computing their worst-case error. These numerical results show that the higher order polynomial lattice rules improve upon the known constructions of quasi-Monte Carlo rules based on higher order digital nets.     

Integration and approximation in arbitrary dimensions

We study multivariate integration and approximation for various classes of functions of d variables with arbitrary d. We consider algorithms that use function evaluations as the information about the function. We are mainly interested in verifying when integration and approximation are tractable and strongly tractable. Tractability means that the minimal number of function evaluations needed to reduce the initial error by a factor of ɛ is bounded by C(d)ɛ^−p for some exponent p independent of d and some function C(d). Strong tractability means that C(d) can be made independent of d. The ‐exponents of tractability and strong tractability are defined as the smallest powers of ɛ{^-1} in these bounds. We prove that integration is strongly tractable for some weighted Korobov and Sobolev spaces as well as for the Hilbert space whose reproducing kernel corresponds to the covariance function of the isotropic Wiener measure. We obtain bounds on the ‐exponents, and for some cases we find their exact values. For some weighted Korobov and Sobolev spaces, the strong ‐exponent is the same as the ‐exponent for d=1, whereas for the third space it is 2. For approximation we also consider algorithms that use general evaluations given by arbitrary continuous linear functionals as the information about the function. Our main result is that the ‐exponents are the same for general and function evaluations. This holds under the assumption that the orthonormal eigenfunctions of the covariance operator have uniformly bounded L∞ norms. This assumption holds for spaces with shift-invariant kernels. Examples of such spaces include weighted Korobov spaces. For a space with non‐shift‐invariant kernel, we construct the corresponding space with shift-invariant kernel and show that integration and approximation for the non-shift-invariant kernel are no harder than the corresponding problems with the shift-invariant kernel. If we apply this construction to a weighted Sobolev space, whose kernel is non-shift-invariant, then we obtain the corresponding Korobov space. This enables us to derive the results for weighted Sobolev spaces. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal Order Quadrature Error Bounds for Infinite-Dimensional Higher-Order Digital Sequences

Quasi-Monte Carlo (QMC) quadrature rules using higher-order digital nets and sequences have been shown to achieve the almost optimal rate of convergence of the worst-case error in Sobolev spaces of arbitrary fixed smoothness \(\alpha \in \mathbb {N}\), \(\alpha \ge 2\). In a recent paper by the authors, it was proved that randomly digitally shifted order \(2\alpha \) digital nets in prime base b achieve the best possible rate of convergence of the root mean square worst-case error of order \(N^{-\alpha }(\log N)^{(s-1)/2}\) for \(N=b^m\), where N and s denote the number of points and the dimension, respectively, which implies the existence of an optimal order QMC rule. More recently, the authors provided an explicit construction of such an optimal order QMC rule by using Chen–Skriganov’s digital nets in conjunction with Dick’s digit interlacing composition. These results were for fixed number of points. In this paper, we give a more general result on an explicit construction of optimal order QMC rules for arbitrary fixed smoothness \(\alpha \in \mathbb {N}\) including the endpoint case \(\alpha =1\). That is, we prove that the projection of any infinite-dimensional order \(2\alpha +1\) digital sequence in prime base b onto the first s coordinates achieves the best possible rate of convergence of the worst-case error of order \(N^{-\alpha }(\log N)^{(s-1)/2}\) for \(N=b^m\). The explicit construction presented in this paper is not only easy to implement but also extensible in both N and s.     

Multivariate approximation in the worst case setting over reproducing kernel Hilbert spaces

We study the worst case setting for approximation of d variate functions from a general reproducing kernel Hilbert space with the error measured in the L_∞ norm. We mainly consider algorithms that use n arbitrary continuous linear functionals. We look for algorithms with the minimal worst case errors and for their rates of convergence as n goes to infinity. Algorithms using n function values will be analyzed in a forthcoming paper.We show that the L_∞ approximation problem in the worst case setting is related to the weighted L₂ approximation problem in the average case setting with respect to a zero-mean Gaussian stochastic process whose covariance function is the same as the reproducing kernel of the Hilbert space. This relation enables us to find optimal algorithms and their rates of convergence for the weighted Korobov space with an arbitrary smoothness parameter α>1, and for the weighted Sobolev space whose reproducing kernel corresponds to the Wiener sheet measure. The optimal convergence rates are n^-(α-1)/2 and n^-1/2, respectively.We also study tractability of L_∞ approximation for the absolute and normalized error criteria, i.e., how the minimal worst case errors depend on the number of variables, d, especially when d is arbitrarily large. We provide necessary and sufficient conditions on tractability of L_∞ approximation in terms of tractability conditions of the weighted L₂ approximation in the average case setting. In particular, tractability holds in weighted Korobov and Sobolev spaces only for weights tending sufficiently fast to zero and does not hold for the classical unweighted spaces.     

Liberating the weights

A partial answer to why quasi-Monte Carlo (QMC) algorithms work well for multivariate integration was given in Sloan and Woźniakowski (J. Complexity 14 (1998) 1–33) by introducing weighted spaces. In these spaces the importance of successive coordinate directions is quantified by a sequence of weights. However, to be able to make use of weighted spaces for a particular application one has to make a choice of the weights.In this work, we take a more general view of the weights by allowing them to depend arbitrarily not only on the coordinates but also on the number of variables. Liberating the weights in this way allows us to give a recommendation for how to choose the weights in practice. This recommendation results from choosing the weights so as to minimize the error bound. We also consider how best to choose the underlying weighted Sobolev space within which to carry out the analysis.We revisit also lower bounds on the worst-case error, which change in many minor ways now, since the weights are allowed to depend on the number of variables, and we do not assume that the weights are uniformly bounded as has been assumed in previous papers. Necessary and sufficient conditions for QMC tractability and strong QMC tractability are obtained for the weighted Sobolev spaces with general weights.In the final section, we show that the analysis of variance decomposition of functions from one of the Sobolev spaces is equivalent to the decomposition of functions with respect to an orthogonal decomposition of this space.     

Weighted Tensor Product Algorithms for Linear Multivariate Problems

We study the ε-approximation of linear multivariate problems defined over weighted tensor product Hilbert spaces of functions f of d variables. A class of weighted tensor product (WTP) algorithms is defined which depends on a number of parameters. Two classes of permissible information are studied. Λ^all consists of all linear functionals while Λ^std consists of evaluations of f or its derivatives. We show that these multivariate problems are sometimes tractable even with a worst-case assurance. We study problem tractability by investigating when a WTP algorithm is a polynomial-time algorithm, that is, when the minimal number of information evaluations is a polynomial in 1/ε and d. For Λ^all we construct an optimal WTP algorithm and provide a necessary and sufficient condition for tractability in terms of the sequence of weights and the sequence of singular values for d=1. ForΛ^std we obtain a weaker result by constructing a WTP algorithm which is optimal only for some weight sequences.     

Tractability of Multivariate Integration for Periodic Functions

We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor ε for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in ε⁻¹ and d. Strong tractability means that we have only a polynomial dependence in ε⁻¹. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γ_j moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑^∞_j=1 γ_j<∞, whereas tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/ln d<∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity17 (2001), 388–441) concerning decomposable kernels.     

The Price of Pessimism for Multidimensional Quadrature

We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in ⁻¹ and d. Strong tractability means that we have only a polynomial dependence in ⁻¹. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γ_j moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑^∞_j=1 γ_j<∞, whereas tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/ln d<∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity17 (2001), 388–441) concerning decomposable kernels.     

Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights

We study the problem of constructing shifted rank-1 lattice rules for the approximation of high-dimensional integrals with a low weighted star discrepancy, for classes of functions having bounded weighted variation, where the weighted variation is defined as the weighted sum of Hardy–Krause variations over all lower-dimensional projections of the integrand. Under general conditions on the weights, we prove the existence of rank-1 lattice rules such that for any δ>0, the general weighted star discrepancy is O(n^−1+δ) for any number of points n>1 (not necessarily prime), any shift of the lattice, general (decreasing) weights, and uniformly in the dimension. We also show that these rules can be constructed by a component-by-component strategy. This implies in particular that a single infinite-dimensional generating vector can be used for integrals in any number of dimensions, and even for infinite-dimensional integrands when they have bounded weighted variation. These same lattices are also good with respect to the worst-case error in weighted Korobov spaces with the same types of general weights. Similar results were already available for various special cases, such as general weights and prime n, or arbitrary n and product weights, but not for the most general combination of n composite, general weights, arbitrary shift, and star discrepancy, considered here. Our results imply tractability or strong tractability of integration for classes of integrands with finite weighted variation when the weights satisfy the conditions we give. These classes are a strict superset of those covered by earlier sufficient tractability conditions.     

TRACTABILITY OF MULTIVARIATE INTEGRATION PROBLEM FOR PERIODIC CONTINUOUS FUNCTIONS

The authors study the tractability and strong tractability of a multivariate integration problem in the worst case setting for weighted l-periodic continuous functions spaces of d coordinates with absolutely convergent Fourier series.The authors reduce the initial error by a factor ε for functions from the unit ball of the weighted periodic contin- uous functions spaces.Tractability is the minimal number of function samples required to solve the problem in polynomial in ε~(-1)and d.and the strong tractability is the pres- ence of only a polynomial dependence in ε.This problem has been recently studied for quasi-Monte Carlo quadrature rules.quadrature rules with non-negative coefficients. and rules for which all quadrature weights are arbitrary for weighted Korobov spaces of smooth periodic functions of d variables.The authors show that the tractability and strong tractability of a multivariate integration problem in worst case setting hold for the weighted periodic continuous functions spaces with absolutely convergent Fourier series under the same assumptions as in Ref.[14]on the weights of the Korobov space for quasi-Monte Carlo rules and rules for which all quadrature weights are non-negative.The arguments are not constructive.