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

International Journal of Numerical Analysis and Modeling

An Algorithm-Driven Approach to Error Analysis for Multidimensional Integration

Fred J. Hickernell, Josef Dick

Published May 1, 2008• 2 citations
Publisher

Abstract

Most error analyses for numerical integration algorithms specify the space of integrands and then determine the convergence rate for a particular algorithm or the optimal algorithm. This article takes a different perspective of specifying the convergence rate and then finding the largest space of integrands for which the algorithm gives that desired rate. Both worst-case and randomized error analyses are provided.

DOI
10.4208/ijnam.v5.n2.p167

Related papers

A simple universal algorithm for high-dimensional integration

Takashi Goda, David Krieg

Abstract We present a simple universal algorithm for high-dimensional integration which has the optimal error rate (independent of the dimension) in all weighted Korobov classes both in the randomized and the deterministic setting. Our theoretical findings are complemented by numerical tests.

arXiv:2411.19164•Numerische Mathematik•Dec 12, 2025•10 citations

Randomly shifted lattice rules with the optimal rate of convergence for unbounded integrands

Frances Y. Kuo, Ian H. Sloan, G.W. Wasilkowski +1 more

Journal of Complexity•Oct 26, 2009•55 citations

Quasi-Monte Carlo integration over Rs based on digital nets

Josef Dick, Friedrich Pillichshammer

This paper discusses φ -weighted integration of functions over the s -dimensional Euclidean space using quasi-Monte Carlo (QMC) rules combined with an inversion method, where the probability density function (PDF) φ is of product form, i.e., a product of uni-variate PDFs φ i for each coordinate i in { 1 , … , s } . The space of integrands is specified by means of a γ -weighted p -norm, p ≥ 1 , which involves coordinate weights γ , the partial derivatives of order up to one of the integrands as well as additional weight functions ψ i and the PDFs φ i . The coordinate weights γ model the importance of different coordinates or groups of coordinates in the sense of Sloan and Woźniakowski, and the weight functions ψ i are additional parameters of the space which describe the decay of the partial derivatives of the integrands. Fast decaying weights ψ i ( x ) for x → ± ∞ enlarge the space of functions with finite norm, but decrease the convergence rate of the worst-case error of the proposed algorithms. Our algorithms for integration use digitally shifted digital nets in combination with an inversion method. We study the (root) mean squared worst-case error with respect to random digital shifts. The obtained error bounds depend on the choice of weight functions ψ i and coordinate weights γ . Under certain conditions on γ , these bounds hold uniformly for all dimensions s . Numerical experiments demonstrate the effectiveness of the proposed algorithms.

Journal of Computational and Applied Mathematics•Dec 24, 2024•2 citations

A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with $0 < α\le 1/2$

Dirk Nuyens, Laurence Wilkes

In previous work (Kuo, Nuyens, Wilkes, 2023), we showed that a lattice rule with a pre-determined generating vector but random number of points can achieve the near optimal convergence of $O(n^{-α-1/2+ε})$, $ε> 0$, for the worst case expected error, commonly referred to as the randomised error, for numerical integration of high-dimensional functions in the Korobov space with smoothness $α> 1/2$. Compared to the optimal deterministic rate of $O(n^{-α+ε})$, $ε> 0$, such a randomised algorithm is capable of an extra half in the rate of convergence. In this paper, we show that a pre-determined generating vector also exists in the case of $0 < α\le 1/2$. Also here we obtain the near optimal convergence of $O(n^{-α-1/2+ε})$, $ε> 0$; or in more detail, we obtain $O(\sqrt{r} \, n^{-α-1/2+1/(2r)+ε'})$ which holds for any choices of $ε' > 0$ and $r \in \mathbb{N}$ with $r > 1/(2α)$.

arXiv:2308.03138•Aug 6, 2023•2 citations

Infinite-Dimensional Integration in Weighted Hilbert Spaces: Anchored Decompositions, Optimal Deterministic Algorithms, and Higher-Order Convergence

Josef Dick, Michael Gnewuch

arXiv:1210.4223•Foundations of Computational Mathematics•Apr 30, 2014•23 citations

Dimension-independent convergence rates of randomized nets using median-of-means

Zexin Pan

Recent advances in quasi-Monte Carlo integration demonstrate that the median of linearly scrambled digital net estimators achieves near-optimal convergence rates for high-dimensional integrals without requiring a priori knowledge of the integrand’s smoothness. Building on this framework, we prove that the median estimator attains dimension-independent convergence, a property known as strong tractability in complexity theory, under tractability conditions characterized by low effective dimensionality. Using a probabilistic, integrand-specific error criterion, our analysis establishes both faster and dimension-independent convergence under weaker assumptions than previously possible in the worst-case setting.

arXiv:2505.13815•Mathematics of Computation•Mar 5, 2026•1 citation
Most error analyses for numerical integration algorithms specify the space of integrands and then determine the convergence rate for a particular algorithm or the optimal algorithm. This article takes a different perspective of specifying the convergence rate and then finding the largest space of integrands for which the algorithm gives that desired rate. Both worst-case and randomized error analyses are provided.
This paper discusses φ -weighted integration of functions over the s -dimensional Euclidean space using quasi-Monte Carlo (QMC) rules combined with an inversion method, where the probability density function (PDF) φ is of product form, i.e., a product of uni-variate PDFs φ i for each coordinate i in { 1 , … , s } . The space of integrands is specified by means of a γ -weighted p -norm, p ≥ 1 , which involves coordinate weights γ , the partial derivatives of order up to one of the integrands as well as additional weight functions ψ i and the PDFs φ i . The coordinate weights γ model the importance of different coordinates or groups of coordinates in the sense of Sloan and Woźniakowski, and the weight functions ψ i are additional parameters of the space which describe the decay of the partial derivatives of the integrands. Fast decaying weights ψ i ( x ) for x → ± ∞ enlarge the space of functions with finite norm, but decrease the convergence rate of the worst-case error of the proposed algorithms. Our algorithms for integration use digitally shifted digital nets in combination with an inversion method. We study the (root) mean squared worst-case error with respect to random digital shifts. The obtained error bounds depend on the choice of weight functions ψ i and coordinate weights γ . Under certain conditions on γ , these bounds hold uniformly for all dimensions s . Numerical experiments demonstrate the effectiveness of the proposed algorithms.
A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with 0<α≤1/20 < α\le 1/20<α≤1/2
In previous work (Kuo, Nuyens, Wilkes, 2023), we showed that a lattice rule with a pre-determined generating vector but random number of points can achieve the near optimal convergence of O(n−α−1/2+ε)O(n^{-α-1/2+ε})O(n−α−1/2+ε), ε>0ε> 0ε>0, for the worst case expected error, commonly referred to as the randomised error, for numerical integration of high-dimensional functions in the Korobov space with smoothness α>1/2α> 1/2α>1/2. Compared to the optimal deterministic rate of O(n−α+ε)O(n^{-α+ε})O(n−α+ε), ε>0ε> 0ε>0, such a randomised algorithm is capable of an extra half in the rate of convergence. In this paper, we show that a pre-determined generating vector also exists in the case of 0<α≤1/20 < α\le 1/20<α≤1/2. Also here we obtain the near optimal convergence of O(n−α−1/2+ε)O(n^{-α-1/2+ε})O(n−α−1/2+ε), ε>0ε> 0ε>0; or in more detail, we obtain O(r n−α−1/2+1/(2r)+ε′)O(\sqrt{r} \, n^{-α-1/2+1/(2r)+ε'})O(r​n−α−1/2+1/(2r)+ε′) which holds for any choices of ε′>0ε' > 0ε′>0 and r∈Nr \in \mathbb{N}r∈N with r>1/(2α)r > 1/(2α)r>1/(2α).
Recent advances in quasi-Monte Carlo integration demonstrate that the median of linearly scrambled digital net estimators achieves near-optimal convergence rates for high-dimensional integrals without requiring a priori knowledge of the integrand’s smoothness. Building on this framework, we prove that the median estimator attains dimension-independent convergence, a property known as strong tractability in complexity theory, under tractability conditions characterized by low effective dimensionality. Using a probabilistic, integrand-specific error criterion, our analysis establishes both faster and dimension-independent convergence under weaker assumptions than previously possible in the worst-case setting.