Takashi Goda

Michael B. Giles, Takashi Goda

In this paper we develop a very efficient approach to the Monte Carlo estimation of the expected value of partial perfect information (EVPPI) that measures the average benefit of knowing the value of a subset of uncertain parameters involved in a decision model. The calculation of EVPPI is inherently a nested expectation problem, with an outer expectation with respect to one random variable $X$ and an inner conditional expectation with respect to the other random variable $Y$. We tackle this problem by using a Multilevel Monte Carlo (MLMC) method (Giles 2008) in which the number of inner samples for $Y$ increases geometrically with level, so that the accuracy of estimating the inner conditional expectation improves and the cost also increases with level. We construct an antithetic MLMC estimator and provide sufficient assumptions on a decision model under which the antithetic property of the estimator is well exploited, and consequently a root-mean-square accuracy of $\varepsilon$ can be achieved at a cost of $O(\varepsilon^{-2})$. Numerical results confirm the considerable computational savings compared to the standard, nested Monte Carlo method for some simple testcases and a more realistic medical application.

Takashi Goda, Josef Dick

Higher order scrambled digital nets are randomized quasi-Monte Carlo rules which have recently been introduced in [J. Dick, Ann. Statist., 39 (2011), 1372--1398] and shown to achieve the optimal rate of convergence of the root mean square error for numerical integration of smooth functions defined on the $s$-dimensional unit cube. The key ingredient there is a digit interlacing function applied to the components of a randomly scrambled digital net whose number of components is $ds$, where the integer $d$ is the so-called interlacing factor. In this paper, we replace the randomly scrambled digital nets by randomly scrambled polynomial lattice point sets, which allows us to obtain a better dependence on the dimension while still achieving the optimal rate of convergence. Our results apply to Owen's full scrambling scheme as well as the simplifications studied by Hickernell, Matoušek and Owen. We consider weighted function spaces with general weights, whose elements have square integrable partial mixed derivatives of order up to $α\ge 1$, and derive an upper bound on the variance of the estimator for higher order scrambled polynomial lattice rules. Employing our obtained bound as a quality criterion, we prove that the component-by-component construction can be used to obtain explicit constructions of good polynomial lattice point sets. By first constructing classical polynomial lattice point sets in base $b$ and dimension $ds$, to which we then apply the interlacing scheme of order $d$, we obtain a construction cost of the algorithm of order $\mathcal{O}(dsmb^m)$ operations using $\mathcal{O}(b^m)$ memory in case of product weights, where $b^m$ is the number of points in the polynomial lattice point set.

Josef Dick, Takashi Goda, Takehito Yoshiki

We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness $α\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 $α$ consecutive sizes of nodes, $b^{m-α+1},\ldots,b^{m}$, and ii) recursive application of Richardson extrapolation to a chain of $α$ 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+α)N\log N$, which improves the currently known result for interlaced polynomial lattice rule, that is of order $sα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.

Josef Dick, Takashi Goda, Kosuke Suzuki et al.

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.

Takashi Goda

Quadrature rules using higher order digital nets and sequences are known to exploit the smoothness of a function for numerical integration and to achieve an improved rate of convergence as compared to classical digital nets and sequences for smooth functions. A construction principle of higher order digital nets and sequences based on a digit interlacing function was introduced in [J. Dick, SIAM J. Numer. Anal., 45 (2007) pp.~2141--2176], which interlaces classical digital nets or sequences whose number of components is a multiple of the dimension. In this paper, we study the use of polynomial lattice point sets for interlaced components. We call quadrature rules using such point sets {\em interlaced polynomial lattice rules}. We consider weighted Walsh spaces containing smooth functions and derive two upper bounds on the worst-case error for interlaced polynomial lattice rules, both of which can be employed as a quality criterion for the construction of interlaced polynomial lattice rules. We investigate the component-by-component construction and the Korobov construction as a means of explicit constructions of good interlaced polynomial lattice rules that achieve the optimal rate of the worst-case error. Through this approach we are able to obtain a good dependence of the worst-case error bounds on the dimension under certain conditions on the weights, while significantly reducing the construction cost as compared to higher order polynomial lattice rules.

Takashi Goda, Kosuke Suzuki, Takehito Yoshiki

We investigate quasi-Monte Carlo (QMC) integration over the $s$-dimensional unit cube based on rank-1 lattice point sets in weighted non-periodic Sobolev spaces $\mathcal{H}(K_{α,\boldsymbolγ,s}^{\mathrm{sob}})$ and their subspaces of high order smoothness $α>1$, where $\boldsymbolγ$ denotes a set of the weights. A recent paper by Dick, Nuyens and Pillichshammer has studied QMC integration in half-period cosine spaces with smoothness parameter $α>1/2$ consisting of non-periodic smooth functions, denoted by $\mathcal{H}(K_{α,\boldsymbolγ,s}^{\mathrm{cos}})$, and also in the sum of half-period cosine spaces and Korobov spaces with common parameter $α$, denoted by $\mathcal{H}(K_{α,\boldsymbolγ,s}^{\mathrm{kor}+\mathrm{cos}})$. Motivated by the results shown there, we first study embeddings and norm equivalences on those function spaces. In particular, for an integer $α$, we provide their corresponding norm-equivalent subspaces of $\mathcal{H}(K_{α,\boldsymbolγ,s}^{\mathrm{sob}})$. This implies that $\mathcal{H}(K_{α,\boldsymbolγ,s}^{\mathrm{kor}+\mathrm{cos}})$ is strictly smaller than $\mathcal{H}(K_{α,\boldsymbolγ,s}^{\mathrm{sob}})$ as sets for $α\geq 2$, which solves an open problem by Dick, Nuyens and Pillichshammer. Then we study the worst-case error of tent-transformed lattice rules in $\mathcal{H}(K_{2,\boldsymbolγ,s}^{\mathrm{sob}})$ and also the worst-case error of symmetrized lattice rules in an intermediate space between $\mathcal{H}(K_{α,\boldsymbolγ,s}^{\mathrm{kor}+\mathrm{cos}})$ and $\mathcal{H}(K_{α,\boldsymbolγ,s}^{\mathrm{sob}})$. We show that the almost optimal rate of convergence can be achieved for both cases, while a weak dependence of the worst-case error bound on the dimension can be obtained for the former case.

Takashi Goda, Kosuke Suzuki, Takehito Yoshiki

We investigate quasi-Monte Carlo integration using higher order digital nets in weighted Sobolev spaces of arbitrary fixed smoothness $α\in \mathbb{N}$, $α\ge 2$, defined over the $s$-dimensional unit cube. We prove that randomly digitally shifted order $β$ digital nets can achieve the convergence of the root mean square worst-case error of order $N^{-α}(\log N)^{(s-1)/2}$ when $β\ge 2α$. The exponent of the logarithmic term, i.e., $(s-1)/2$, is improved compared to the known result by Baldeaux and Dick, in which the exponent is $sα/2$. Our result implies the existence of a digitally shifted order $β$ digital net achieving the convergence of the worst-case error of order $N^{-α}(\log N)^{(s-1)/2}$, which matches a lower bound on the convergence rate of the worst-case error for any cubature rule using $N$ function evaluations and thus is best possible.

Takashi Goda, Kosuke Suzuki, Takehito Yoshiki

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 $α\in \mathbb{N}$, $α\geq 2$. In a recent paper by the authors, it was proved that randomly-digitally-shifted order $2α$ digital nets in prime base $b$ achieve the best possible rate of convergence of the root mean square worst-case error of order $N^{-α}(\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 $α\in \mathbb{N}$ including the endpoint case $α=1$. That is, we prove that the projection of any infinite-dimensional order $2α+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^{-α}(\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$.

Takashi Goda, Kosuke Suzuki, Takehito Yoshiki

In a recent paper by the authors, it is shown that there exists a quasi-Monte Carlo (QMC) rule which achieves the best possible rate of convergence for numerical integration in a reproducing kernel Hilbert space consisting of smooth functions. In this paper we provide an explicit construction of such an optimal order QMC rule. Our approach is to exploit both the decay and the sparsity of the Walsh coefficients of the reproducing kernel simultaneously. This can be done by applying digit interlacing composition due to Dick to digital nets with large minimum Hamming and Niederreiter-Rosenbloom-Tsfasman metrics due to Chen and Skriganov. To our best knowledge, our construction gives the first QMC rule which achieves the best possible convergence in this function space.

Takashi Goda

Antithetic sampling, which goes back to the classical work by Hammersley and Morton (1956), is one of the well-known variance reduction techniques for Monte Carlo integration. In this paper we investigate its application to digital nets over $\mathbb{Z}_b$ for quasi-Monte Carlo (QMC) integration, a deterministic counterpart of Monte Carlo, of functions defined over the $s$-dimensional unit cube. By looking at antithetic sampling as a geometric technique in a compact totally disconnected abelian group, we first generalize the notion of antithetic sampling from base $2$ to an arbitrary base $b\ge 2$. Then we analyze the QMC integration error of digital nets over $\mathbb{Z}_b$ with $b$-adic antithetics. Moreover, for a prime $b$, we prove the existence of good higher order polynomial lattice point sets with $b$-adic antithetics for QMC integration of smooth functions in weighted Sobolev spaces. Numerical experiments based on Sobol' point sets up to $s=100$ show that the rate of convergence can be improved for smooth integrands by using antithetic sampling technique, which is quite encouraging beyond the reach of our theoretical result and motivates future work to address.

Takashi Goda

Separability of multivariate functions alleviates the difficulty in finding a minimum or maximum value of a function such that an optimal solution can be searched by solving several disjoint problems with lower dimensionalities. In most of practical problems, however, a function to be optimized is black-box and we hardly grasp its separability. In this study, we first describe a general separability condition which a function defined over an arbitrary domain satisfies if and only if the function is separable with respect to given disjoint subsets of variables. By introducing an alternative separability condition, we propose a Monte Carlo-based algorithm to estimate the separability of a function defined over unit cube with respect to given disjoint subsets of variables. Moreover, we extend our algorithm to estimate the number of disjoint subsets and the disjoint subsets such that a function is separable with respect to them. Computational complexity of our extended algorithm is function-dependent and varies from linear to exponential in the dimension.

Takashi Goda

Higher order digital nets are special classes of point sets for quasi-Monte Carlo rules which achieve the optimal convergence rate for numerical integration of smooth functions. An explicit construction of higher order digital nets was proposed by Dick, which is based on digitally interlacing in a certain way the components of classical digital nets whose number of components is a multiple $ds$ of the dimension $s$. In this paper we give a fast computer search algorithm to find good classical digital nets suitable for interlaced components by using polynomial lattice point sets. We consider certain weighted Sobolev spaces of smoothness of arbitrarily high order, and derive an upper bound on the mean square worst-case error for digitally shifted higher order digital nets. Employing this upper bound as a quality criterion, we prove that the component-by-component construction can be used efficiently to find good polynomial lattice point sets suitable for interlaced components. Through this approach we are able to get some tractability results under certain conditions on the weights. Fast construction using the fast Fourier transform requires the construction cost of $O(dsN \log N)$ operations using $O(N)$ memory, where $N$ is the number of points and $s$ is the dimension. This implies a significant reduction in the construction cost as compared to higher order polynomial lattice point sets. Numerical experiments confirm that the performance of our constructed point sets often outperforms those of higher order digital nets with Sobol' sequences and Niederreiter-Xing sequences used for interlaced components, indicating the usefulness of our algorithm.

Takashi Goda

We give an explicit construction of two-dimensional point sets whose $L_p$ discrepancy is of best possible order for all $1\le p\le \infty$. It is provided by folding Hammersley point sets in base $b$ by means of the $b$-adic baker's transformation which has been introduced by Hickernell (2002) for $b=2$ and Goda, Suzuki and Yoshiki (2013) for arbitrary $b\in \mathbb{N}$, $b\ge 2$. We prove that both the minimum Niederreiter-Rosenbloom-Tsfasman weight and the minimum Dick weight of folded Hammersley point sets are large enough to achieve the best possible order of $L_p$ discrepancy for all $1\le p\le \infty$.

Takashi Goda, Kosuke Suzuki, Takehito Yoshiki

We study quasi-Monte Carlo integration for twice differentiable functions defined over a triangle. We provide an explicit construction of infinite sequences of points including one by Basu and Owen (2015) as a special case, which achieves the integration error of order $N^{-1}(\log N)^3$ for any $N\geq 2$. Since a lower bound of order $N^{-1}$ on the integration error holds for any linear quadrature rule, the upper bound we obtain is best possible apart from the $\log N$ factor. The major ingredient in our proof of the upper bound is the dyadic Walsh analysis of twice differentiable functions over a triangle under a suitable recursive partitioning.

Takashi Goda

In this paper we investigate multivariate integration in weighted unanchored Sobolev spaces of smoothness of arbitrarily high order. As quadrature points we employ higher order polynomial lattice point sets over $\mathbb{F}_{2}$ which are randomly digitally shifted and then folded using the tent transformation. We first prove the existence of good higher order polynomial lattice rules which achieve the optimal rate of the mean square worst-case error, while reducing the required degree of modulus by half as compared to higher order polynomial lattice rules whose quadrature points are randomly digitally shifted but not folded using the tent transformation. Thus we are able to restrict the search space of generating vectors significantly. We then study the component-by-component construction as an explicit means of obtaining good higher order polynomial lattice rules. In a way analogous to [J. Baldeaux, J. Dick, G. Leobacher, D. Nuyens, F. Pillichshammer, Numer. Algorithms, 59 (2012) 403--431], we show how to calculate the quality criterion efficiently and how to obtain the fast component-by-component construction using the fast Fourier transform. Our result generalizes the previous result shown by [L.L. Cristea, J. Dick, G. Leobacher, F. Pillichshammer, Numer. Math., 105 (2007) 413--455], in which the degree of smoothness is fixed at 2 and classical polynomial lattice rules are considered.

Takashi Goda

We study numerical integration of smooth functions defined over the $s$-dimensional unit cube. A recent work by Dick et al. (2019) has introduced so-called extrapolated polynomial lattice rules, which achieve the almost optimal rate of convergence for numerical integration and can be constructed by the fast component-by-component search algorithm with smaller computational costs as compared to interlaced polynomial lattice rules. In this paper we prove that, instead of polynomial lattice point sets, truncated higher order digital nets and sequences can be used within the same algorithmic framework to explicitly construct good quadrature rules achieving the almost optimal rate of convergence. The major advantage of our new approach compared to original higher order digital nets is that we can significantly reduce the precision of points, i.e., the number of digits necessary to describe each quadrature node. This finding has a practically useful implication when either the number of points or the smoothness parameter is so large that original higher order digital nets require more than the available finite-precision floating point representations.

Takashi Goda

The $\mathcal{L}_2$ discrepancy is one of several well-known quantitative measures for the equidistribution properties of point sets in the high-dimensional unit cube. The concept of weights was introduced by Sloan and Woźniakowski to take into account the relative importance of the discrepancy of lower dimensional projections. As known under the name of quasi-Monte Carlo methods, point sets with small weighted $\mathcal{L}_2$ discrepancy are useful in numerical integration. This study investigates the component-by-component construction of polynomial lattice rules over the finite field $\mathbb{F}_2$ whose scrambled point sets have small mean square weighted $\mathcal{L}_2$ discrepancy. An upper bound on this discrepancy is proved, which converges at almost the best possible rate of $N^{-2+δ}$ for all $δ>0$, where $N$ denotes the number of points. Numerical experiments confirm that the performance of our constructed polynomial lattice point sets is comparable or even superior to that of Sobol' sequences.

Mou Cai, Takashi Goda

This paper studies the multivariate approximation of functions in weighted Korobov spaces using multiple rank-1 lattice rules. It has been shown by Kämmerer and Volkmer (2019) that algorithms based on multiple rank-1 lattices achieve the optimal convergence rate for the $L_{\infty}$ error in Wiener-type spaces, up to logarithmic factors. While this result was translated to weighted Korobov spaces in the recent monograph by Dick, Kritzer, and Pillichshammer (2022), the analysis requires the smoothness parameter $α$ to be greater than $1$ and is restricted to product weights. In this paper, we extend this result for multiple rank-1 lattice-based algorithms to the case where $1/2<α\le 1$ and for general weights, covering a broader range of periodic functions with low smoothness and general relative importance of variables. We also provide a summability condition on the weights to ensure strong polynomial tractability for any $α>1/2$. Furthermore, by incorporating random shifts into multiple rank-1 lattice-based algorithms, we prove that the resulting randomized algorithm achieves a nearly optimal convergence rate in terms of the worst-case root mean squared $L_2$ error, while retaining the same tractability property.

Yoshihito Kazashi, Yuya Suzuki, Takashi Goda

Optimality of several quasi-Monte Carlo methods and suboptimality of the sparse-grid quadrature based on the univariate Gauss--Hermite rule is proved in the Sobolev spaces of mixed dominating smoothness of order $α$, where the optimality is in the sense of worst-case convergence rate. For sparse-grid Gauss--Hermite quadrature, lower and upper bounds are established, with rates coinciding up to a logarithmic factor. The dominant rate is found to be only $N^{-α/2}$ with $N$ function evaluations, although the optimal rate is known to be $N^{-α}(\ln N)^{(d-1)/2}$. The lower bound is obtained by exploiting the structure of the Gauss--Hermite nodes and is independent of the quadrature weights; consequently, no modification of the weights can improve the rate $N^{-α/2}$. In contrast, several quasi-Monte Carlo methods with a change of variables are shown to achieve the optimal rate, some up to, and one including, the logarithmic factor.

Hengjun Xu, Takashi Goda

In this paper, we develop constructive algorithms for generating quasi-uniform point sets and sequences over arbitrary two-dimensional triangular domains. Our proposed method, called the \emph{Voronoi-guided greedy packing} algorithm, iteratively selects the point farthest from the current set among a finite candidate set determined by the Voronoi diagram of the triangle. Our main theoretical result shows that, after a finite number of iterations, the mesh ratio of the generated point set is at most~2, which is known to be optimal. We further analyze two existing triangular low-discrepancy point sets and prove that their mesh ratios are uniformly bounded, thereby establishing their quasi-uniformity. Finally, through a series of numerical experiments, we demonstrate that the proposed method provides an efficient and practical strategy for generating high-quality point sets on individual triangles.

Takashi Goda, Yang Liu, Raúl Tempone

This paper proposes a new randomized design of digital nets in which the generating matrices are chosen to be random Hankel matrices. Compared with previous randomized designs of digital nets, this approach simplifies the construction process and reduces the number of random variables required, while still achieving desirable convergence rates when combined with appropriate estimators. We analyze the properties of the proposed design, derive bounds for Walsh coefficients, and provide error analysis for both the median-of-means estimator and a newly proposed greedy selection estimator, i.e. the selection of the best design from a batch in terms of a worst-case error bound. Numerical experiments validate our theoretical findings and demonstrate the practical performance of the proposed methods.

Takashi Goda, Tomohiko Hironaka, Wataru Kitade et al.

In this paper we propose an efficient stochastic optimization algorithm to search for Bayesian experimental designs such that the expected information gain is maximized. The gradient of the expected information gain with respect to experimental design parameters is given by a nested expectation, for which the standard Monte Carlo method using a fixed number of inner samples yields a biased estimator. In this paper, applying the idea of randomized multilevel Monte Carlo (MLMC) methods, we introduce an unbiased Monte Carlo estimator for the gradient of the expected information gain with finite expected squared $\ell_2$-norm and finite expected computational cost per sample. Our unbiased estimator can be combined well with stochastic gradient descent algorithms, which results in our proposal of an optimization algorithm to search for an optimal Bayesian experimental design. Numerical experiments confirm that our proposed algorithm works well not only for a simple test problem but also for a more realistic pharmacokinetic problem.

Kei Ishikawa, Takashi Goda

In this paper, we propose a new stochastic optimization algorithm for Bayesian inference based on multilevel Monte Carlo (MLMC) methods. In Bayesian statistics, biased estimators of the model evidence have been often used as stochastic objectives because the existing debiasing techniques are computationally costly to apply. To overcome this issue, we apply an MLMC sampling technique to construct low-variance unbiased estimators both for the model evidence and its gradient. In the theoretical analysis, we show that the computational cost required for our proposed MLMC estimator to estimate the model evidence or its gradient with a given accuracy is an order of magnitude smaller than those of the previously known estimators. Our numerical experiments confirm considerable computational savings compared to the conventional estimators. Combining our MLMC estimator with gradient-based stochastic optimization results in a new scalable, efficient, debiased inference algorithm for Bayesian statistical models.

Takashi Goda, Kei Ishikawa

In this short note we provide an unbiased multilevel Monte Carlo estimator of the log marginal likelihood and discuss its application to variational Bayes.

Takashi Goda, Kosuke Suzuki

In this article we review some of recent results on higher order quasi-Monte Carlo (HoQMC) methods. After a seminal work by Dick (2007, 2008) who originally introduced the concept of HoQMC, there have been significant theoretical progresses on HoQMC in terms of discrepancy as well as multivariate numerical integration. Moreover, several successful and promising applications of HoQMC to partial differential equations with random coefficients and Bayesian estimation/inversion problems have been reported recently. In this article we start with standard quasi-Monte Carlo methods based on digital nets and sequences in the sense of Niederreiter, and then move onto their higher order version due to Dick. The Walsh analysis of smooth functions plays a crucial role in developing the theory of HoQMC, and the aim of this article is to provide a unified picture on how the Walsh analysis enables recent developments of HoQMC both for discrepancy and numerical integration.

Takashi Goda

The notion of symmetrization, also known as Davenport's reflection principle, is well known in the area of the discrepancy theory and quasi-Monte Carlo (QMC) integration. In this paper we consider applying a symmetrization technique to a certain class of QMC point sets called digital nets over $\mathbb{Z}_{b}$. Although symmetrization has been recognized as a geometric technique in the multi-dimensional unit cube, we give another look at symmetrization as a geometric technique in a compact totally disconnected abelian group with dyadic arithmetic operations. Based on this observation we generalize the notion of symmetrization from base 2 to an arbitrary base $b\in \mathbb{N}$, $b\ge 2$. Subsequently, we study the QMC integration error of symmetrized digital nets over $\mathbb{Z}_{b}$ in a reproducing kernel Hilbert space. The result can be applied to component-by-component construction or Korobov construction for finding good symmetrized (higher order) polynomial lattice rules which achieve high order convergence of the integration error for smooth integrands at the expense of an exponential growth of the number of points with the dimension. Moreover, we consider two-dimensional symmetrized Hammersley point sets in prime base $b$, and prove that the minimum Dick weight is large enough to achieve the best possible order of $L_p$ discrepancy for all $1\le p< \infty$.

Takashi Goda, Kosuke Suzuki, Takehito Yoshiki

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 \emph{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 \emph{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.

Takashi Goda, Ryuichi Ohori, Kosuke Suzuki et al.

In this paper, we study randomized quasi-Monte Carlo (QMC) integration using digitally shifted digital nets. We express the mean square QMC error of the $n$-th discrete approximation $f_n$ of a function $f\colon[0,1)^s\to \mathbb{R}$ for digitally shifted digital nets in terms of the Walsh coefficients of $f$. We then apply a bound on the Walsh coefficients for sufficiently smooth integrands to obtain a quality measure called Walsh figure of merit for root mean square error, which satisfies a Koksma-Hlawka type inequality on the root mean square error. Through two types of experiments, we confirm that our quality measure is of use for finding digital nets which show good convergence behaviors of the root mean square error for smooth integrands.

Takashi Goda, Kosuke Suzuki, Takehito Yoshiki

In this paper we investigate quasi-Monte Carlo (QMC) integration using digital nets over $\mathbb{Z}_b$ in reproducing kernel Hilbert spaces. The tent transformation, or the baker's transformation, was originally used for lattice rules by Hickernell (2002) to achieve higher order convergence of the integration error for smooth non-periodic integrands, and later, has been successfully applied to digital nets over $\mathbb{Z}_2$ by Cristea et al. (2007) and Goda (2014). The aim of this paper is to generalize the latter two results to digital nets over $\mathbb{Z}_b$ for an arbitrary prime $b$. For this purpose, we introduce the {\em $b$-adic tent transformation} for an arbitrary positive integer $b$ greater than 1, which is a generalization of the original (dyadic) tent transformation. Further, again for an arbitrary positive integer $b$ greater than 1, we analyze the mean square worst-case error of QMC rules using digital nets over $\mathbb{Z}_b$ which are randomly digitally shifted and then folded using the $b$-adic tent transformation in reproducing kernel Hilbert spaces. Using this result, for a prime $b$, we prove the existence of good higher order polynomial lattice rules over $\mathbb{Z}_b$ among the smaller number of candidates as compared to the result by Dick and Pillichshammer (2007), which achieve almost the optimal convergence rate of the mean square worst-case error in unanchored Sobolev spaces of smoothness of arbitrary high order.