Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1611.00561

Approximation of Quasi-Monte Carlo worst case error in weighted spaces of infinitely times smooth functions

Makoto Matsumoto, Ryuichi Ohori, Takehito Yoshiki

Published Nov 2, 2016• 0 citations
arXivHTMLPDF

Abstract

In this paper, we consider Quasi-Monte Carlo (QMC) worst case error of weighted smooth function classes in $C^\infty[0,1]^s$ by a digital net over $\mathbb F_2$. We show that the ratio of the worst case error to the QMC integration error of an exponential function is bounded above and below by constants. This result provides us with a simple interpretation that a digital net with small QMC integration error for an exponential function also gives the small integration error for any function in this function space.

DOI
10.48550/arxiv.1611.00561

Related papers

High-dimensional integration: The quasi-Monte Carlo way

Josef Dick, Frances Y. Kuo, Ian H. Sloan

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.

Acta Numerica•Apr 2, 2013•615 citations

A Universal Median Quasi-Monte Carlo Integration

Takashi Goda, Kosuke Suzuki, Makoto Matsumoto

Abstract. We study quasi-Monte Carlo (QMC) integration over the multidimensional unit cube in several weighted function spaces with different smoothness classes. We consider approximating the integral of a function by the median of several integral estimates under independent and random choices of the underlying QMC point sets (either linearly scrambled digital nets or infinite-precision polynomial lattice point sets). Even though our approach does not require any information on the smoothness and weights of a target function space as an input, we can prove a probabilistic upper bound on the worst-case error for the respective weighted function space, where the failure probability converges to 0 exponentially fast as the number of estimates increases. Our obtained rates of convergence are nearly optimal for function spaces with finite smoothness, and we can attain a dimension-independent super-polynomial convergence for a class of infinitely differentiable functions. This implies that our median-based QMC rule is universal in the sense that it does not need to be adjusted to the smoothness and the weights of the function spaces and yet exhibits the nearly optimal rate of convergence. Numerical experiments support our theoretical results.

arXiv:2209.13186•SIAM Journal on Numerical Analysis•Feb 16, 2024•12 citations

Weighted integration over a cube based on digital nets and sequences

Josef Dick, Friedrich Pillichshammer

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.

arXiv:2009.06993•Sep 15, 2020•0 citations

Weighted integration over a hyperrectangle based on digital nets and sequences

Josef Dick, Friedrich Pillichshammer

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 hyperrectangle. 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 hyperrectangle but is otherwise independent of the product measure.

Journal of Computational and Applied Mathematics•Mar 7, 2021•3 citations

On quasi-Monte Carlo methods in weighted ANOVA spaces

Peter Kritzer, Friedrich Pillichshammer, G.W. Wasilkowski

In the present paper we study quasi-Monte Carlo rules for approximating integrals over the $d$-dimensional unit cube for functions from weighted Sobolev spaces of regularity one. While the properties of these rules are well understood for anchored Sobolev spaces, this is not the case for the ANOVA spaces, which are another very important type of reference spaces for quasi-Monte Carlo rules. Using a direct approach we provide a formula for the worst case error of quasi-Monte Carlo rules for functions from weighted ANOVA spaces. As a consequence we bound the worst case error from above in terms of weighted discrepancy of the employed integration nodes. On the other hand we also obtain a general lower bound in terms of the number $n$ of used integration nodes. For the one-dimensional case our results lead to the optimal integration rule and also in the two-dimensional case we provide rules yielding optimal convergence rates.

arXiv:2001.05765•Mathematics of Computation•Nov 18, 2020•1 citation

When Are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?

Ian H. Sloan, Henryk Woźniakowski

Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.

Journal of Complexity•Mar 1, 1998•605 citations
In this paper, we consider Quasi-Monte Carlo (QMC) worst case error of weighted smooth function classes in C∞[0,1]sC^\infty[0,1]^sC∞[0,1]s by a digital net over F2\mathbb F_2F2​. We show that the ratio of the worst case error to the QMC integration error of an exponential function is bounded above and below by constants. This result provides us with a simple interpretation that a digital net with small QMC integration error for an exponential function also gives the small integration error for any function in this function space.
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.
Abstract. We study quasi-Monte Carlo (QMC) integration over the multidimensional unit cube in several weighted function spaces with different smoothness classes. We consider approximating the integral of a function by the median of several integral estimates under independent and random choices of the underlying QMC point sets (either linearly scrambled digital nets or infinite-precision polynomial lattice point sets). Even though our approach does not require any information on the smoothness and weights of a target function space as an input, we can prove a probabilistic upper bound on the worst-case error for the respective weighted function space, where the failure probability converges to 0 exponentially fast as the number of estimates increases. Our obtained rates of convergence are nearly optimal for function spaces with finite smoothness, and we can attain a dimension-independent super-polynomial convergence for a class of infinitely differentiable functions. This implies that our median-based QMC rule is universal in the sense that it does not need to be adjusted to the smoothness and the weights of the function spaces and yet exhibits the nearly optimal rate of convergence. Numerical experiments support our theoretical results.
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.
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 hyperrectangle. 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 hyperrectangle but is otherwise independent of the product measure.
In the present paper we study quasi-Monte Carlo rules for approximating integrals over the ddd-dimensional unit cube for functions from weighted Sobolev spaces of regularity one. While the properties of these rules are well understood for anchored Sobolev spaces, this is not the case for the ANOVA spaces, which are another very important type of reference spaces for quasi-Monte Carlo rules. Using a direct approach we provide a formula for the worst case error of quasi-Monte Carlo rules for functions from weighted ANOVA spaces. As a consequence we bound the worst case error from above in terms of weighted discrepancy of the employed integration nodes. On the other hand we also obtain a general lower bound in terms of the number nnn of used integration nodes. For the one-dimensional case our results lead to the optimal integration rule and also in the two-dimensional case we provide rules yielding optimal convergence rates.
Recently, quasi-Monte Carlo algorithms have been successfully used for multivariate integration of high dimensiond, and were significantly more efficient than Monte Carlo algorithms. The existing theory of the worst case error bounds of quasi-Monte Carlo algorithms does not explain this phenomenon. This paper presents a partial answer to why quasi-Monte Carlo algorithms can work well for arbitrarily larged. It is done by identifying classes of functions for which the effect of the dimensiondis negligible. These areweightedclasses in which the behavior in the successive dimensions is moderated by a sequence of weights. We prove that the minimalworst caseerror of quasi-Monte Carlo algorithms does not depend on the dimensiondiff the sum of the weights is finite. We also prove that the minimal number of function values in the worst case setting needed to reduce the initial error by ε is bounded byCε−p, where the exponentp∈ [1, 2], andCdepends exponentially on the sum of weights. Hence, the relatively small sum of the weights makes some quasi-Monte Carlo algorithms strongly tractable. We show in a nonconstructive way that many quasi-Monte Carlo algorithms are strongly tractable. Even random selection of sample points (done once for the whole weighted class of functions and then the worst case error is established for that particular selection, in contrast to Monte Carlo where random selection of sample points is carried out for a fixed function) leads to strong tractable quasi-Monte Carlo algorithms. In this case the minimal number of function values in theworst casesetting is of order ε−pwith the exponentp= 2. The deterministic construction of strongly tractable quasi-Monte Carlo algorithms as well as the minimal exponentpis open.