Search

We study the quasi-uniformity properties of digital nets, a class of quasi-Monte Carlo point sets. Quasi-uniformity is a space-filling property used for instance in experimental designs and radial basis function approximation. However, it has not been investigated so far whether common low-discrepancy digital nets are quasi-uniform, with the exception of the two-dimensional Sobol' sequence, which has recently been shown not to be quasi-uniform. In this paper, with the goal of constructing quasi-uniform low-discrepancy digital nets, we introduce the notion of \emph{well-separated} point sets and provide an algebraic criterion to determine whether a given digital net is well-separated. Using this criterion, we present an example of a two-dimensional digital net which has low-discrepancy and is quasi-uniform. Additionally, we provide several counterexamples of low-discrepancy digital nets that are not quasi-uniform. The quasi-uniformity properties of quasi-Monte Carlo lattice point sets and sequences will be studied in a forthcoming paper.

In this short note we report on a coincidence of two mathematical quantities that, at first glance, have little to do with each other. On the one hand, there are the Lebesgue constants of the Walsh function system that play an important role in approximation theory, and on the other hand there is the star discrepancy of the van der Corput sequence that plays a prominent role in uniform distribution theory. Over the decades, these two quantities have been examined in great detail independently of each other and important results have been proven. Work in these areas has been carried out independently, but as we show here, they actually coincide. Interestingly, many theorems have been discovered in both areas independently, but some results have only been known in one area but not in the other.

In this paper, we present some new (in-)tractability results related to the integration problem in subspaces of the Wiener algebra over the $d$-dimensional unit cube. We show that intractability holds for multivariate integration in the standard Wiener algebra in the deterministic setting, in contrast to polynomial tractability in an unweighted subspace of the Wiener algebra recently shown by Goda (2023). Moreover, we prove that multivariate integration in the subspace of the Wiener algebra introduced by Goda is strongly polynomially tractable if we switch to the randomized setting. We also identify subspaces in which multivariate integration in the deterministic setting are (strongly) polynomially tractable and we compare these results with the bound which can be obtained via Hoeffding's inequality., Comment: 16 pages

We study the integration problem over the $s$-dimensional unit cube on four types of Banach spaces of integrands. First we consider Haar wavelet spaces, consisting of functions whose Haar wavelet coefficients exhibit a certain decay behavior measured by a parameter $\alpha >0$. We study the worst case error of integration over the norm unit ball and provide upper error bounds for quasi-Monte Carlo (QMC) cubature rules based on arbitrary $(t,m,s)$-nets as well as matching lower error bounds for arbitrary cubature rules. These results show that using arbitrary $(t,m,s)$-nets as sample points yields the best possible rate of convergence. Afterwards we study spaces of integrands of fractional smoothness $\alpha \in (0,1)$ and state a sharp Koksma-Hlawka-type inequality. More precisely, we show that on those spaces the worst case error of integration is equal to the corresponding fractional discrepancy. Those spaces can be continuously embedded into tensor product Bessel potential spaces, also known as Sobolev spaces of dominated mixed smoothness, with the same set of parameters. The latter spaces can be embedded into suitable Besov spaces of dominating mixed smoothness $\alpha$, which in turn can be embedded into the Haar wavelet spaces with the same set of parameters. Therefore our upper error bounds on Haar wavelet spaces for QMC cubatures based on $(t,m,s)$-nets transfer (with possibly different constants) to the corresponding spaces of integrands of fractional smoothness and to Sobolev and Besov spaces of dominating mixed smoothness. Moreover, known lower error bounds for periodic Sobolev and Besov spaces of dominating mixed smoothness show that QMC integration based on arbitrary $(t,m,s)$-nets yields the best possible convergence rate on periodic as well as on non-periodic Sobolev and Besov spaces of dominating smoothness., Comment: 56 pages

In this work, we explore a time-fractional diffusion equation of order $\alpha \in (0,1)$ with a stochastic diffusivity parameter. We focus on efficient estimation of the expected values (considered as an infinite dimensional integral on the parametric space corresponding to the random coefficients) of linear functionals acting on the solution of our model problem. To estimate the expected value computationally, the infinite expansions of the random parameter need to be truncated. Then we approximate the high-dimensional integral over the random field using a high-order quasi-Monte Carlo method. This follows by approximating the deterministic solution over the space-time domain via a second-order accurate time-stepping scheme in combination with a spatial discretization by Galerkin finite elements. Under reasonable regularity assumptions on the given data, we show some regularity properties of the continuous solution and investigate the errors from estimating the expected value. We report on numerical experiments that complement the theoretical results.

We investigate a second-order accurate time-stepping scheme for solving a time-fractional diffusion equation with a Caputo derivative of order~$\alpha \in (0,1)$. The basic idea of our scheme is based on local integration followed by linear interpolation. It reduces to the standard Crank--Nicolson scheme in the classical diffusion case, that is, as $\alpha\to 1$. Using a novel approach, we show that the proposed scheme is $\alpha$-robust and second-order accurate in the $L^2(L^2)$-norm, assuming a suitable time-graded mesh. For completeness, we use the Galerkin finite element method for the spatial discretization and discuss the error analysis under reasonable regularity assumptions on the given data. Some numerical results are presented at the end.

We show convergence rates for a sparse grid approximation of the distribution of solutions of the stochastic Landau-Lifshitz-Gilbert equation. Beyond being a frequently studied equation in engineering and physics, the stochastic Landau-Lifshitz-Gilbert equation poses many interesting challenges that do not appear simultaneously in previous works on uncertainty quantification: The equation is strongly non-linear, time-dependent, and has a non-convex side constraint. Moreover, the parametrization of the stochastic noise features countably many unbounded parameters and low regularity compared to other elliptic and parabolic problems studied in uncertainty quantification. We use a novel technique to establish uniform holomorphic regularity of the parameter-to-solution map based on a Gronwall-type estimate and the implicit function theorem. This method is very general and based on a set of abstract assumptions. Thus, it can be applied beyond the Landau-Lifshitz-Gilbert equation as well. We demonstrate numerically the feasibility of approximating with sparse grid and show a clear advantage of a multi-level sparse grid scheme., Comment: 36 pages, 4 figures

We study the approximation of integrals $\int_D f(\boldsymbol{x}^\top A) \mathrm{d} \mu(\boldsymbol{x})$, where $A$ is a matrix, by quasi-Monte Carlo (QMC) rules $N^{-1} \sum_{k=0}^{N-1} f(\boldsymbol{x}_k^\top A)$. We are interested in cases where the main cost arises from calculating the products $\boldsymbol{x}_k^\top A$. We design QMC rules for which the computation of $\boldsymbol{x}_k^\top A$, $k = 0, 1, \ldots, N-1$, can be done fast, and for which the error of the QMC rule is similar to the standard QMC error. We do not require that $A$ has any particular structure. For instance, this approach can be used when approximating the expected value of a function with a multivariate normal random variable with a given covariance matrix, or when approximating the expected value of the solution of a PDE with random coefficients. The speed-up of the computation time is sometimes better and sometimes worse than the fast QMC matrix-vector product from [Dick, Kuo, Le Gia, and Schwab, Fast QMC Matrix-Vector Multiplication, SIAM J. Sci. Comput. 37 (2015)]. As in that paper, our approach applies to (polynomial) lattice point sets, but also to digital nets (we are currently not aware of any approach which allows one to apply the fast method from the aforementioned paper of Dick, Kuo, Le Gia, and Schwab to digital nets). Our method does not use FFT, instead we use repeated values in the quadrature points to derive a reduction in the computation time. This arises from the reduced CBC construction of lattice rules and polynomial lattice rules. The reduced CBC construction has been shown to reduce the computation time for the CBC construction. Here we show that it can also be used to also reduce the computation time of the QMC rule.

We study numerical integration over bounded regions in $\mathbb{R}^s, s\ge1$ with respect to some probability measure. We replace random sampling with quasi-Monte Carlo methods, where the underlying point set is derived from deterministic constructions that aim to fill the space more evenly than random points. Such quasi-Monte Carlo point sets are ordinarily designed for the uniform measure, and the theory only works for product measures when a coordinate-wise transformation is applied. Going beyond this setting, we first consider the case where the target density is a mixture distribution where each term in the mixture comes from a product distribution. Next we consider target densities which can be approximated with such mixture distributions. We require the approximation to be a sum of coordinate-wise products and the approximation to be positive everywhere (so that they can be re-scaled to probability density functions). We use tensor product hat function approximations for this purpose here, since a hat function approximation of a positive function is itself positive. We also study more complex algorithms, where we first approximate the target density with a general Gaussian mixture distribution and approximate the mixtures with an adaptive hat function approximation on rotated intervals. The Gaussian mixture approximation allows us to locate the essential parts of the target density, whereas the adaptive hat function approximation allows us to approximate the finer structure of the target density. We prove convergence rates for each of the integration techniques based on quasi-Monte Carlo sampling for integrands with bounded partial mixed derivatives. The employed algorithms are based on digital $(t,s)$-sequences over the finite field $\mathbb{F}_2$ and an inversion method. Numerical examples illustrate the performance of the algorithms for some target densities and integrands.

We study a randomized quadrature algorithm to approximate the integral of periodic functions defined over the high-dimensional unit cube. Recent work by Kritzer, Kuo, Nuyens and Ullrich (2019) shows that rank-1 lattice rules with a randomly chosen number of points and good generating vector achieve almost the optimal order of the randomized error in weighted Korobov spaces, and moreover, that the error is bounded independently of the dimension if the weight parameters, $\gamma_j$, satisfy the summability condition $\sum_{j=1}^{\infty}\gamma_j^{1/\alpha}<\infty$, where $\alpha$ is a smoothness parameter. The argument is based on the existence result that at least half of the possible generating vectors yield almost the optimal order of the worst-case error in the same function spaces. In this paper we provide a component-by-component construction algorithm of such randomized rank-1 lattice rules, without any need to check whether the constructed generating vectors satisfy a desired worst-case error bound. Similarly to the above-mentioned work, we prove that our algorithm achieves almost the optimal order of the randomized error and that the error bound is independent of the dimension if the same condition $\sum_{j=1}^{\infty}\gamma_j^{1/\alpha}<\infty$ holds. We also provide analogous results for tent-transformed lattice rules for weighted half-period cosine spaces and for polynomial lattice rules in weighted Walsh spaces, respectively., Comment: major revision, 29 pages, 3 figures

Quasi-Monte Carlo (QMC) methods are equal weight quadrature rules to approximate integrals over the unit cube with respect to the uniform measure. In this paper we discuss QMC integration with respect to general product measures defined on an arbitrary cube. We only require that the cumulative distribution function is invertible. We develop a worst-case error bound and study the dependence of the error on the number of points and the dimension for digital nets and sequences as well as polynomial lattice point sets, which are mapped to the domain using the inverse cumulative distribution function. We do not require any smoothness properties of the probability density function and the worst-case error does not depend on the particular choice of density function and its smoothness. The component-by-component construction of polynomial lattice rules is based on a criterion which depends only on the size of the cube but is otherwise independent of the product measure.

We introduce an algorithm to reduce large data sets using so-called digital nets, which are well distributed point sets in the unit cube. These point sets together with weights, which depend on the data set, are used to represent the data. We show that this can be used to reduce the computational effort needed in finding good parameters in machine learning algorithms. To illustrate our method we provide some numerical examples for neural networks.

Motivated mainly by applications to partial differential equations with random coefficients, we introduce a new class of Monte Carlo estimators, called Toeplitz Monte Carlo (TMC) estimator for approximating the integral of a multivariate function with respect to the direct product of an identical univariate probability measure. The TMC estimator generates a sequence $x_1,x_2,\ldots$ of i.i.d. samples for one random variable, and then uses $(x_{n+s-1},x_{n+s-2}\ldots,x_n)$ with $n=1,2,\ldots$ as quadrature points, where $s$ denotes the dimension. Although consecutive points have some dependency, the concatenation of all quadrature nodes is represented by a Toeplitz matrix, which allows for a fast matrix-vector multiplication. In this paper we study the variance of the TMC estimator and its dependence on the dimension $s$. Numerical experiments confirm the considerable efficiency improvement over the standard Monte Carlo estimator for applications to partial differential equations with random coefficients, particularly when the dimension $s$ is large.

The transparent cornea is the window of the eye, facilitating the entry of light rays and controlling focusing the movement of the light within the eye. The cornea is critical, contributing to 75% of the refractive power of the eye. Keratoconus is a progressive and multifactorial corneal degenerative disease affecting 1 in 2000 individuals worldwide. Currently, there is no cure for keratoconus other than corneal transplantation for advanced stage keratoconus or corneal cross-linking, which can only halt KC progression. The ability to accurately identify subtle KC or KC progression is of vital clinical significance. To date, there has been little consensus on a useful model to classify KC patients, which therefore inhibits the ability to predict disease progression accurately. In this paper, we utilised machine learning to analyse data from 124 KC patients, including topographical and clinical variables. Both supervised multilayer perceptron and unsupervised variational autoencoder models were used to classify KC patients with reference to the existing Amsler-Krumeich (A-K) classification system. Both methods result in high accuracy, with the unsupervised method showing better performance. The result showed that the unsupervised method with a selection of 29 variables could be a powerful tool to provide an automatic classification tool for clinicians. These outcomes provide a platform for additional analysis for the progression and treatment of keratoconus., Comment: 7 pages, 8 figures, 3 tables

We study the periodic $L_2$-discrepancy of point sets in the $d$-dimensional torus. This discrepancy is intimately connected with the root-mean-square $L_2$-discrepancy of shifted point sets, with the notion of diaphony, and with the worst case error of cubature formulas for the integration of periodic functions in Sobolev spaces of mixed smoothness. In discrepancy theory many results are based on averaging arguments. In order to make such results relevant for applications one requires explicit constructions of point sets with ``average'' discrepancy. In our main result we study Korobov's $p$-sets and show that this point sets have periodic $L_2$-discrepancy of average order. This result is related to an open question of Novak and Wo\'{z}niakowski.

We study quasi-Monte Carlo (QMC) methods for numerical integration of multivariate functions defined over the high-dimensional unit cube. Lattice rules and polynomial lattice rules, which are special classes of QMC methods, have been intensively studied and the so-called component-by-component (CBC) algorithm has been well-established to construct rules which achieve the almost optimal rate of convergence with good tractability properties for given smoothness and set of weights. Since the CBC algorithm constructs rules for given smoothness and weights, not much is known when such rules are used for function classes with different smoothness and/or weights. In this paper we prove that a lattice rule constructed by the CBC algorithm for the weighted Korobov space with given smoothness and weights achieves the almost optimal rate of convergence with good tractability properties for general classes of smoothness and weights which satisfy some summability conditions. Such a stability result also can be shown for polynomial lattice rules in weighted Walsh spaces. We further give bounds on the weighted star discrepancy and discuss the tractability properties for these QMC rules. The results are comparable to those obtained for Halton, Sobol and Niederreiter sequences.

We show that the minimal discrepancy of a point set in the $d$-dimensional unit cube with respect to Orlicz norms can exhibit both polynomial and weak tractability. In particular, we show that the $\psi_\alpha$-norms of exponential Orlicz spaces are polynomially tractable., Comment: 10 pages

To numerically approximate Borel probability measures by finite atomic measures, we study the spectral decomposition of discrepancy kernels when restricted to compact subsets of $\mathbb{R}^d$. For restrictions to the Euclidean ball in odd dimensions, to the rotation group $SO(3)$, and to the Grassmannian manifold $\mathcal{G}_{2,4}$, we compute the kernels' Fourier coefficients and determine their asymptotics. The $L_2$-discrepancy is then expressed in the Fourier domain that enables efficient numerical minimization based on the nonequispaced fast Fourier transform. For $SO(3)$, the nonequispaced fast Fourier transform is publicly available, and, for $\mathcal{G}_{2,4}$, the transform is derived here. We also provide numerical experiments for $SO(3)$ and $\mathcal{G}_{2,4}$.

Importance sampling Monte-Carlo methods are widely used for the approximation of expectations with respect to partially known probability measures. In this paper we study a deterministic version of such an estimator based on quasi-Monte Carlo. We obtain an explicit error bound in terms of the star-discrepancy for this method., Comment: 14 pages, 2 figures, shorter version of the manuscript accepted for publication in Stat. Probab. Lett. (for Section 3 see online supplementary material there)

We propose a multi-index algorithm for the Monte Carlo (MC) discretization of a linear, elliptic PDE with affine-parametric input. We prove an error vs. work analysis which allows a multi-level finite-element approximation in the physical domain, and apply the multi-index analysis with isotropic, unstructured mesh refinement in the physical domain for the solution of the forward problem, for the approximation of the random field, and for the Monte-Carlo quadrature error. Our approach allows Lipschitz domains and mesh hierarchies more general than tensor grids. The improvement in complexity over multi-level MC FEM is obtained from combining spacial discretization, dimension truncation and MC sampling in a multi-index fashion. Our analysis improves cost estimates compared to multi-level algorithms for similar problems and mathematically underpins the superior practical performance of multi-index algorithms for partial differential equations with random coefficients., Comment: revised version published in SINUM

Frolov's cubature formula on the unit hypercube has been considered important since it attains an optimal rate of convergence for various function spaces. Its integration nodes are given by shrinking a suitable full rank $\mathbb{Z}$-lattice in $\mathbb{R}^d$ and taking all points inside the unit cube. The main drawback of these nodes is that they are hard to find computationally, especially in high dimensions.In such situations, quasi-Monte Carlo (QMC) rules based on digital nets have proven to be successful. However, there is still no construction known that leads to QMC rules which are optimal in the same generality as Frolov's. In this paper we investigate a polynomial analog of Frolov's cubature formula, which we expect to be important in this respect. This analog is defined in a field of Laurent series with coefficients in a finite field. A similar approach was previously studied in [M.~B.~Levin. Adelic constructions of low discrepancy sequences. Online Journal of Analytic Combinatorics. Issue 5, 2010.]. We show that our construction is a $(t,m,d)$-net, which also implies bounds on its star-discrepancy and the error of the corresponding cubature rule. Moreover, we show that our cubature rule is a QMC rule, whereas Frolov's is not, and provide an algorithm to determine its integration nodes explicitly. To this end we need to extend the notion of $(t,m,d)$-nets to fit the situation that the points can have infinite digit expansion and develop a duality theory. Additionally, we adapt the notion of admissible lattices to our setting and prove its significance.

We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness $\alpha\geq 2$ defined over the $s$-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named \emph{extrapolated polynomial lattice rule}, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: i) construction of classical polynomial lattice rules over $\mathbb{F}_b$ with $\alpha$ consecutive sizes of nodes, $b^{m-\alpha+1},\ldots,b^{m}$, and ii) recursive application of Richardson extrapolation to a chain of $\alpha$ approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order $(s+\alpha)N\log N$, which improves the currently known result for interlaced polynomial lattice rule, that is of order $s\alpha N\log N$. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.

We propose and analyze deterministic multilevel approximations for Bayesian inversion of operator equations with uncertain distributed parameters, subject to additive Gaussian measurement data. The algorithms use a multilevel (ML) approach based on deterministic, higher order quasi-Monte Carlo (HoQMC) quadrature for approximating the high-dimensional expectations, which arise in the Bayesian estimators, and a Petrov-Galerkin (PG) method for approximating the solution to the underlying partial differential equation (PDE). This extends the previous single-level approach from [J. Dick, R. N. Gantner, Q. T. Le Gia and Ch. Schwab, Higher order Quasi-Monte Carlo integration for Bayesian Estimation. Report 2016-13, Seminar for Applied Mathematics, ETH Z\"urich (in review)]. We obtain sufficient conditions which allow us to achieve arbitrarily high, algebraic convergence rates in terms of work, which are independent of the dimension of the parameter space. The convergence rates are limited only by the spatial regularity of the forward problem,the discretization order achieved by the Petrov Galerkin discretization, and by the sparsity of the uncertainty parametrization. We provide detailed numerical experiments for linear elliptic problems in two space dimensions, with $s=1024$ parameters characterizing the uncertain input, confirming the theory and showing that the ML HoQMC algorithms outperform, in terms of error vs.~computational work, both multilevel Monte Carlo (MLMC) methods and single-level (SL) HoQMC methods.

We prove upper bounds on the order of convergence of lattice based algorithms for numerical integration in function spaces of dominating mixed smoothness on the unit cube with homogeneous boundary condition. More precisely, we study worst-case integration errors for Besov spaces of dominating mixed smoothness $\mathring{\mathbf{B}}^s_{p,\theta}$, which also comprise the concept of Sobolev spaces of dominating mixed smoothness $\mathring{\mathbf{H}}^s_{p}$ as special cases. The considered algorithms are quasi-Monte Carlo rules with underlying nodes from $T_N(\mathbb{Z}^d) \cap [0,1)^d$, where $T_N$ is a real invertible generator matrix of size $d$. For such rules the worst-case error can be bounded in terms of the Zaremba index of the lattice $\mathbb{X}_N=T_N(\mathbb{Z}^d)$. We apply this result to Kronecker lattices and to rank-1 lattice point sets, which both lead to optimal error bounds up to $\log N$-factors for arbitrary smoothness $s$. The advantage of Kronecker lattices and classical lattice point sets is that the run-time of algorithms generating these point sets is very short., Comment: 19 pages

We study the numerical approximation of integrals over $\mathbb{R}^s$ with respect to the standard Gaussian measure for integrands which lie in certain Hermite spaces of functions. The decay rate of the associated sequence is specified by a single integer parameter which determines the smoothness classes and the inner product can be expressed via $L_2$ norms of the derivatives of the function. We map higher order digital nets from the unit cube to a suitable subcube of $\mathbb{R}^s$ via a linear transformation and show that such rules achieve, apart from powers of $\log N$, the optimal rate of convergence of the integration error., Comment: final version

The discrepancy function measures the deviation of the empirical distribution of a point set in $[0,1]^d$ from the uniform distribution. In this paper, we study the classical discrepancy function with respect to the BMO and exponential Orlicz norms, as well as Sobolev, Besov and Triebel-Lizorkin norms with dominating mixed smoothness. We give sharp bounds for the discrepancy function under such norms with respect to infinite sequences., Comment: A journal requested to split the first version of the paper arXiv:1601.07281 into two parts. This is the second part which contains the results on the BMO and exponential Orlicz norm of the discrepancy function. Further the discrepancy function in Sobolev-, Besov- and Triebel-Lizorkin spaces of dominating mixed smoothness is considered

We analyze combined Quasi-Monte Carlo quadrature and Finite Element approximations in Bayesian estimation of solutions to countably-parametric operator equations with holomorphic dependence on the parameters as considered in [Cl.~Schillings and Ch.~Schwab: Sparsity in Bayesian Inversion of Parametric Operator Equations. Inverse Problems, {\bf 30}, (2014)]. Such problems arise in numerical uncertainty quantification and in Bayesian inversion of operator equations with distributed uncertain inputs, such as uncertain coefficients, uncertain domains or uncertain source terms and boundary data. We show that the parametric Bayesian posterior densities belong to a class of weighted Bochner spaces of functions of countably many variables, with a particular structure of the QMC quadrature weights: up to a (problem-dependent, and possibly large) finite dimension $S$ product weights can be used, and beyond this dimension, weighted spaces with so-called SPOD weights are used to describe the solution regularity. We establish error bounds for higher order Quasi-Monte Carlo quadrature for the Bayesian estimation based on [J.~Dick, Q.T.~LeGia and Ch.~Schwab, Higher order Quasi-Monte Carlo integration for holomorphic, parametric operator equations, Report 2014-23, SAM, ETH Z\"urich]. It implies, in particular, regularity of the parametric solution and of the countably-parametric Bayesian posterior density in SPOD weighted spaces. This, in turn, implies that the Quasi-Monte Carlo quadrature methods in [J. Dick, F.Y.~Kuo, Q.T.~Le Gia, D.~Nuyens, Ch.~Schwab, Higher order QMC Galerkin discretization for parametric operator equations, SINUM (2014)] are applicable to these problem classes, with dimension-independent convergence rates $\calO(N^{-1/p})$ of $N$-point HoQMC approximated Bayesian estimates, where $0

We study multivariate integration over the $s$-dimensional unit cube in a weighted space of infinitely differentiable functions. It is known from a recent result by Suzuki that there exists a good quasi-Monte Carlo (QMC) rule which achieves a super-polynomial convergence of the worst-case error in this function space, and moreover, that this convergence behavior is independent of the dimension under a certain condition on the weights. In this paper we provide a constructive approach to finding a good QMC rule achieving such a dimension-independent super-polynomial convergence of the worst-case error. Specifically, we prove that interlaced polynomial lattice rules, with an interlacing factor chosen properly depending on the number of points $N$ and the weights, can be constructed using a fast component-by-component algorithm in at most $O(sN(\log N)^2)$ arithmetic operations to achieve a dimension-independent super-polynomial convergence. The key idea for the proof of the worst-case error bound is to use a variant of Jensen's inequality with a purposely-designed concave function.

The $L_p$-discrepancy is a quantitative measure for the irregularity of distribution modulo one of infinite sequences. In 1986 Proinov proved for all $p>1$ a lower bound for the $L_p$-discrepancy of general infinite sequences in the $d$-dimensional unit cube, but it remained an open question whether this lower bound is best possible in the order of magnitude until recently. In 2014 Dick and Pillichshammer gave a first construction of an infinite sequence whose order of $L_2$-discrepancy matches the lower bound of Proinov. Here we give a complete solution to this problem for all finite $p > 1$. We consider so-called order $2$ digital $(t,d)$-sequences over the finite field with two elements and show that such sequences achieve the optimal order of $L_p$-discrepancy simultaneously for all $p \in (1,\infty)$., Comment: A journal requested to split the paper into two parts. This is the first part which contains the results on the $L_p$ discrepancy