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:2110.06420

Where are the logs?

Art B. Owen, Zexin Pan

Published Oct 13, 2021• 0 citations
arXivHTMLPDF

Abstract

The commonly quoted error rates for QMC integration with an infinite low discrepancy sequence is $O(n^{-1}\log(n)^r)$ with $r=d$ for extensible sequences and $r=d-1$ otherwise. Such rates hold uniformly over all $d$ dimensional integrands of Hardy-Krause variation one when using $n$ evaluation points. Implicit in those bounds is that for any sequence of QMC points, the integrand can be chosen to depend on $n$. In this paper we show that rates with any $r1$ is needed. An example with $d=3$ and $n$ up to $2^{100}$ might possibly require $r>1$.

DOI
10.48550/arxiv.2110.06420

Related papers

Quasi-Monte Carlo Beyond Hardy-Krause II: $(1 + \varepsilon)n$ Samples Suffice

Ekene Ezeunala, Agastya Vibhuti Jha, Haotian Jiang

Numerical integration studies how well one can estimate the integral of a function $f$ over $[0,1)^d$ using $n$ sample points. The two classical methods, Monte Carlo (MC) and quasi-Monte Carlo (QMC), have complementary strengths and weaknesses, and a fundamental question is to design an approach that combines the benefits of both. Recently, building on the transference principle in discrepancy theory, Bansal and Jiang~\cite{BJ25a} gave a randomized QMC method that bridges MC and QMC guarantees using only i.i.d.\ samples. Their method also goes beyond the classical Koksma--Hlawka inequality: it achieves integration error $\widetilde{O}_d(σ_{\mathsf{SO}}(f)/n)$, where the smoothed-out variation $σ_{\mathsf{SO}}(f)$ can be substantially smaller than the Hardy--Krause variation that governs the classical bound. However, their algorithm requires $n^2$ i.i.d.\ samples as input, and this quadratic blowup is inherent to any method based on the transference principle. In this work, we bypass the quadratic blowup: for any constant $\varepsilon > 0$, we show that $(1+\varepsilon)n$ i.i.d.\ samples suffice to both obtain the beyond-Hardy--Krause guarantee of~\cite{BJ25a}, resolving an open problem posed there, and to produce low-discrepancy point sequences. Our algorithms are variants of the online Haar-thinning method of Dwivedi, Feldheim, Gurel-Gurevich, and Ramdas~\cite{DFG+19}.

arXiv:2609.10921•Sep 10, 2026•0 citations

Quasi-Monte Carlo Beyond Hardy-Krause

Nikhil Bansal, Haotian Jiang

We examine the problem of numerically estimating the integral of a function f. The classical approaches to this problem are Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC methods use random samples to evaluate f and have error , where σ(f ) is the standard deviation of f. QMC methods are based on evaluating f at explicit point sets with low discrepancy, and as given by the classical Koksma- Hlawka inequality, they have error Õ (σHK(f )/n ), where σΗΚ(f ) is the variation of f in the sense of Hardy and Krause. These two methods have distinctive advantages and shortcomings, and a fundamental question is to find a method that combines the advantages of both.

arXiv:2408.06475•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•2 citations

QMC integration errors and quasi-asymptotics

Ilya M. Sobol, Boris V. Shukhman

Abstract A crude Monte Carlo (MC) method allows to calculate integrals over a d-dimensional cube. As the number N of integration nodes becomes large, the rate of probable error of the MC method decreases as O ⁢ ( 1 / N ) {O(1/\sqrt{N})} . The use of quasi-random points instead of random points in the MC algorithm converts it to the quasi-Monte Carlo (QMC) method. The asymptotic error estimate of QMC integration of d-dimensional functions contains a multiplier 1 / N {1/N} . However, the multiplier ( ln ⁡ N ) d {(\ln N)^{d}} is also a part of the error estimate, which makes it virtually useless. We have proved that, in the general case, the QMC error estimate is not limited to the factor 1 / N {1/N} . However, our numerical experiments show that using quasi-random points of Sobol sequences with N = 2 m {N=2^{m}} with natural m makes the integration error approximately proportional to 1 / N {1/N} . In our numerical experiments, d ≤ 15 {d\leq 15} , and we used N ≤ 2 40 {N\leq 2^{40}} points generated by the SOBOLSEQ16384 code published in 2011. In this code, d ≤ 2 14 {d\leq 2^{14}} and N ≤ 2 63 {N\leq 2^{63}} .

Monte Carlo Methods and Applications•Jul 16, 2020•2 citations

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

Low discrepancy constructions in the triangle

Kinjal Basu, Art B. Owen

Most quasi-Monte Carlo research focuses on sampling from the unit cube. Many problems, especially in computer graphics, are defined via quadrature over the unit triangle. Quasi-Monte Carlo methods for the triangle have been developed by Pillands and Cools (2005) and by Brandolini et al. (2013). This paper presents two QMC constructions in the triangle with a vanishing discrepancy. The first is a version of the van der Corput sequence customized to the unit triangle. It is an extensible digital construction that attains a discrepancy below 12/sqrt(N). The second construction rotates an integer lattice through an angle whose tangent is a quadratic irrational number. It attains a discrepancy of O(log(N)/N) which is the best possible rate. Previous work strongly indicated that such a discrepancy was possible, but no constructions were available. Scrambling the digits of the first construction improves its accuracy for integration of smooth functions. Both constructions also yield convergent estimates for integrands that are Riemann integrable on the triangle without requiring bounded variation.

arXiv:1403.2649•Mar 11, 2014•5 citations

Numerical integration in $\log$-Korobov and $\log$-cosine spaces

Josef Dick, Peter Kritzer, Gunther Leobacher +1 more

QMC rules are equal weight quadrature rules for approximating integrals over $[0,1]^s$. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on $[0,1]^s$ with square integrable partial mixed derivatives of order $α$. Using Parseval's identity, this smoothness can be defined for all real numbers $α> 1/2$. This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with $α$ arbitrarily close to $1/2$. To obtain such estimates we introduce a $\log$-scale for functions with smoothness close to $1/2$, which we call $\log$-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order $\mathcal{O}(N^{-1/2} (\log N)^{-μ(1-λ)/2})$ for any $1/μ<λ\le 1$, where $μ>1$ is a power in the $\log$-scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights $(γ_j)_{j \in \mathbb{N}}$. It is known that if $\sum_{j=1}^\infty γ_j^τ< \infty$ for some $1/(2α) < τ\le 1$ one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where $τ$ is close to $1/(2 α)$, namely we show dimension independent error bounds under the condition that $\sum_{j=1}^\infty γ_j \max\{1, \log γ_j^{-1}\}^{μ(1-λ)} < \infty$ for some $1/μ< λ\le 1$. The essential tool in our analysis is a $\log$-scale Jensen's inequality. The results described above also apply to integration in $\log$-cosine spaces using tent-transformed lattice rules.

arXiv:1411.2715•Nov 11, 2014•0 citations
The commonly quoted error rates for QMC integration with an infinite low discrepancy sequence is O(n−1log⁡(n)r)O(n^{-1}\log(n)^r)O(n−1log(n)r) with r=dr=dr=d for extensible sequences and r=d−1r=d-1r=d−1 otherwise. Such rates hold uniformly over all ddd dimensional integrands of Hardy-Krause variation one when using nnn evaluation points. Implicit in those bounds is that for any sequence of QMC points, the integrand can be chosen to depend on nnn. In this paper we show that rates with any r1r1r1 is needed. An example with d=3d=3d=3 and nnn up to 21002^{100}2100 might possibly require r>1r>1r>1.
Quasi-Monte Carlo Beyond Hardy-Krause II: (1+ε)n(1 + \varepsilon)n(1+ε)n Samples Suffice
Numerical integration studies how well one can estimate the integral of a function fff over [0,1)d[0,1)^d[0,1)d using nnn sample points. The two classical methods, Monte Carlo (MC) and quasi-Monte Carlo (QMC), have complementary strengths and weaknesses, and a fundamental question is to design an approach that combines the benefits of both. Recently, building on the transference principle in discrepancy theory, Bansal and Jiang~\cite{BJ25a} gave a randomized QMC method that bridges MC and QMC guarantees using only i.i.d.\ samples. Their method also goes beyond the classical Koksma--Hlawka inequality: it achieves integration error O~d(σSO(f)/n)\widetilde{O}_d(σ_{\mathsf{SO}}(f)/n)Od​(σSO​(f)/n), where the smoothed-out variation σSO(f)σ_{\mathsf{SO}}(f)σSO​(f) can be substantially smaller than the Hardy--Krause variation that governs the classical bound. However, their algorithm requires n2n^2n2 i.i.d.\ samples as input, and this quadratic blowup is inherent to any method based on the transference principle. In this work, we bypass the quadratic blowup: for any constant ε>0\varepsilon > 0ε>0, we show that (1+ε)n(1+\varepsilon)n(1+ε)n i.i.d.\ samples suffice to both obtain the beyond-Hardy--Krause guarantee of~\cite{BJ25a}, resolving an open problem posed there, and to produce low-discrepancy point sequences. Our algorithms are variants of the online Haar-thinning method of Dwivedi, Feldheim, Gurel-Gurevich, and Ramdas~\cite{DFG+19}.
We examine the problem of numerically estimating the integral of a function f. The classical approaches to this problem are Monte Carlo (MC) and quasi-Monte Carlo (QMC) methods. MC methods use random samples to evaluate f and have error , where σ(f ) is the standard deviation of f. QMC methods are based on evaluating f at explicit point sets with low discrepancy, and as given by the classical Koksma- Hlawka inequality, they have error Õ (σHK(f )/n ), where σΗΚ(f ) is the variation of f in the sense of Hardy and Krause. These two methods have distinctive advantages and shortcomings, and a fundamental question is to find a method that combines the advantages of both.
Abstract A crude Monte Carlo (MC) method allows to calculate integrals over a d-dimensional cube. As the number N of integration nodes becomes large, the rate of probable error of the MC method decreases as O ⁢ ( 1 / N ) {O(1/\sqrt{N})} . The use of quasi-random points instead of random points in the MC algorithm converts it to the quasi-Monte Carlo (QMC) method. The asymptotic error estimate of QMC integration of d-dimensional functions contains a multiplier 1 / N {1/N} . However, the multiplier ( ln ⁡ N ) d {(\ln N)^{d}} is also a part of the error estimate, which makes it virtually useless. We have proved that, in the general case, the QMC error estimate is not limited to the factor 1 / N {1/N} . However, our numerical experiments show that using quasi-random points of Sobol sequences with N = 2 m {N=2^{m}} with natural m makes the integration error approximately proportional to 1 / N {1/N} . In our numerical experiments, d ≤ 15 {d\leq 15} , and we used N ≤ 2 40 {N\leq 2^{40}} points generated by the SOBOLSEQ16384 code published in 2011. In this code, d ≤ 2 14 {d\leq 2^{14}} and N ≤ 2 63 {N\leq 2^{63}} .
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.
Most quasi-Monte Carlo research focuses on sampling from the unit cube. Many problems, especially in computer graphics, are defined via quadrature over the unit triangle. Quasi-Monte Carlo methods for the triangle have been developed by Pillands and Cools (2005) and by Brandolini et al. (2013). This paper presents two QMC constructions in the triangle with a vanishing discrepancy. The first is a version of the van der Corput sequence customized to the unit triangle. It is an extensible digital construction that attains a discrepancy below 12/sqrt(N). The second construction rotates an integer lattice through an angle whose tangent is a quadratic irrational number. It attains a discrepancy of O(log(N)/N) which is the best possible rate. Previous work strongly indicated that such a discrepancy was possible, but no constructions were available. Scrambling the digits of the first construction improves its accuracy for integration of smooth functions. Both constructions also yield convergent estimates for integrands that are Riemann integrable on the triangle without requiring bounded variation.
Numerical integration in log⁡\loglog-Korobov and log⁡\loglog-cosine spaces
QMC rules are equal weight quadrature rules for approximating integrals over [0,1]s[0,1]^s[0,1]s. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on [0,1]s[0,1]^s[0,1]s with square integrable partial mixed derivatives of order ααα. Using Parseval's identity, this smoothness can be defined for all real numbers α>1/2α> 1/2α>1/2. This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with ααα arbitrarily close to 1/21/21/2. To obtain such estimates we introduce a log⁡\loglog-scale for functions with smoothness close to 1/21/21/2, which we call log⁡\loglog-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order O(N−1/2(log⁡N)−μ(1−λ)/2)\mathcal{O}(N^{-1/2} (\log N)^{-μ(1-λ)/2})O(N−1/2(logN)−μ(1−λ)/2) for any 1/μ<λ≤11/μ<λ\le 11/μ<λ≤1, where μ>1μ>1μ>1 is a power in the log⁡\loglog-scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights (γj)j∈N(γ_j)_{j \in \mathbb{N}}(γj​)j∈N​. It is known that if ∑j=1∞γjτ<∞\sum_{j=1}^\infty γ_j^τ< \infty∑j=1∞​γjτ​<∞ for some 1/(2α)<τ≤11/(2α) < τ\le 11/(2α)<τ≤1 one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where τττ is close to 1/(2α)1/(2 α)1/(2α), namely we show dimension independent error bounds under the condition that ∑j=1∞γjmax⁡{1,log⁡γj−1}μ(1−λ)<∞\sum_{j=1}^\infty γ_j \max\{1, \log γ_j^{-1}\}^{μ(1-λ)} < \infty∑j=1∞​γj​max{1,logγj−1​}μ(1−λ)<∞ for some 1/μ<λ≤11/μ< λ\le 11/μ<λ≤1. The essential tool in our analysis is a log⁡\loglog-scale Jensen's inequality. The results described above also apply to integration in log⁡\loglog-cosine spaces using tent-transformed lattice rules.