Median QMC method for unbounded integrands over ℝ s \mathbb{R}^{s} in unanchored weighted Sobolev spaces
Ziyang Ye, Josef Dick, Xiaoqun Wang · 2025
Read Median QMC method for unbounded integrands over ℝ s \mathbb{R}^{s} in unanchored weighted Sobolev spaces by Ziyang Ye, Josef Dick, Xiaoqun Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-05334.txt.
Introduction
Ziyang Ye, Josef Dick, and Xiaoqun Wang sharpen a numerical integration method in a 2025 paper. Quasi-Monte Carlo methods estimate integrals over all of space for functions that can grow without bound, a setting where plain random sampling converges slowly. Their trick is to run several randomized estimators and take the median, extending an earlier construction-free rule into a weighted function space for unbounded domains.
They prove the median rule's average error shrinks at the same rate as carefully built lattice rules, without needing that construction or advance knowledge of the space's weights. The number of repeats only needs to grow with the log of the point count. Experiments matched the built-rule accuracy and beat plain Monte Carlo clearly.
Catalog record
| CREATOR | Ziyang Ye, Josef Dick, Xiaoqun Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-05334
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Median QMC method for unbounded integrands over ℝ s \mathbb{R}^{s} in unanchored weighted Sobolev spaces Thanks: Submitted to the editors DATE. Ziyang Ye, Josef Dick, Xiaoqun Wang Abstract This paper investigates quasi-Monte Carlo (QMC) integration of Lebesgue integrable functions with respect to a density function over ℝ s \mathbb{R}^{s} . We extend the construction-free median QMC rule [ 8 ] to the unanchored weighted Sobolev space of functions defined over ℝ s \mathbb{R}^{s} introduced in [ 17 ] . By taking the median of k = 𝒪 ( log N ) k=\mathcal{O}(\log N) independent randomized QMC estimators, we prove that for any ϵ ∈ ( 0 , r − 1 2 ] \epsilon\in(0,r-\frac{1}{2}] , our method achieves a mean absolute error bound of 𝒪 ( N − r + ϵ ) \mathcal{O}(N^{-r+\epsilon}) , where N N is the number of points and r > 1 2 r>\frac{1}{2} is a parameter determined by the function space. This rate matches that of the randomized lattice rules via component-by-component (CBC) construction, while our approach requires no specific CBC constructions or prior knowledge of the space’s weight structure. Numerical experiments demonstrate that our method attains accuracy comparable to the CBC method and outperforms the Monte Carlo method. keywords Numerical integration; quasi-Monte Carlo; randomized lattice rule; unanchored weighted Sobolev space; median Funding. The work of the first and third authors were supported by the National Science Foundation of China (No. 720711119). The second author was supported by the ARC grant DP220101811. † † runningheads: Median QMC method in unanchored weighted Sobolev spaces / Ziyang Ye, Josef Dick, Xiaoqun Wang MSC 65D30, 65D32, 41A55 1 Introduction Numerous practical applications can be formulated as high-dimensional integrals. In this paper, we focus on the integration in the form of I_{\bm{\phi}}(f)=\int_{\mathbb{R}^{s}}f(\bm{y})\bm{\phi}(\bm{y})d\bm{y}, (1) where f:\mathbb{R}^{s}\to\mathbb{R} is an integrable function and \bm{\phi} is a density function over \mathbb{R}^{s} . We assume that \bm{\phi}(\bm{y})=\prod_{j=1}^{s}\phi(y_{j}) for some univariate density function \phi over \mathbb{R} . Let \bm{\Phi} be the cumulative distribution function (CDF) corresponding to \bm{\phi} and let \bm{\Phi}^{-1} denote the inverse of \bm{\Phi} . By using the inverse transformation \bm{y}=\bm{\Phi}^{-1}(\bm{x}) , we have I_{\bm{\phi}}(f)=\int_{[0,1]^{s}}f\circ\bm{\Phi}^{-1}(\bm{x})d\bm{x}. (2) Such integrals arise from many practical problems, including option pricing in financial mathematics, e.g. [ 6 , 7 , 16 , 28 , 29 ] , and partial differential equations (PDEs) with random coefficients in uncertainty quantification, e.g. [ 10 , 11 , 13 , 14 , 27 ] . In these problems, the dimensionality s can be quite large, making the traditional methods infeasible due to the curse of dimensionality. The quasi-Monte Carlo (QMC) method is an effective quadrature method to evaluate the integrals on the unit cube [0,1]^{s} . This method approximates I_{\bm{\phi}}(f) by an equal-weight quadrature rule Q_{P}(f)=\frac{1}{N}\sum_{\bm{x}\in P}f\circ\bm{\Phi}^{-1}(\bm{x}), (3) where P\subset[0,1]^{s} is a pre-designed set of N points with low discrepancy. There are two main families of QMC point sets, namely digital nets [ 3 , 18 ] and lattice point sets [ 2 , 24 ] . In this paper, we focus on a special kind of lattice rule, namely a rank-1 lattice rule. The underlying quadrature points in an N points rank-1 lattice rule are generated by a suitable chosen generating vector \bm{z} , where each component of \bm{z} is an integer in \{1,2,\ldots,N-1\} . The lattice point sets often contain the origin \bm{0} , which can cause problems if \bm{\Phi}^{-1}(\bm{0}) is -\infty . Therefore, we use a randomized lattice rule to avoid the origin (with probability 1 ) by adding a random shift to each lattice point [ 15 , 17 ] . To analyze the QMC error for randomized lattice rules, the integrand is assumed to belong to a Banach space B . We consider the following shift-averaged worst-case error [ 15 , 17 , 25 ] e^{sh}(\bm{z};B)=\left(\int_{[0,1]^{s}}\sup_{f\in B,\|f\|_{B}\leq 1}|Q_{P_{\bm{z},\bm{\Delta}}}(f)-I_{\bm{\phi}}(f)|^{2}d\bm{\Delta}\right)^{\frac{1}{2}}, where \bm{z} is the generating vector and P_{\bm{z},\bm{\Delta}} is the randomly shifted lattice point set with random shift \bm{\Delta} . Selecting a good generating vector \bm{z} is crucial for obtaining small error e^{sh}(\bm{z};B) . A typical algorithm for searching for a suitable \bm{z} is the component-by-component (CBC) construction algorithm [ 12 , 26 ] . Nichols and Kuo [ 17 ] studied randomized lattice rules for numerical integration problem ( 1 ). They introduced the unanchored weighted Sobolev space \mathcal{F} with the norm \|f\|^{2}_{\mathcal{F}}=\sum_{u\subset\{1:s\}}\gamma_{u}^{-1}\int_{\mathbb{R}^{|u|}}\left(\int_{\mathbb{R}^{s-|u|}}\frac{\partial^{|u|}}{\partial\bm{y}_{u}}f(\bm{y})\prod_{j\in-u}\phi(y_{j})d\bm{y}_{-u}\right)^{2}\prod_{j\in u}\psi_{j}^{2}(y_{j})d\bm{y}_{u}. Here \{1:s\}=\{1,2,\ldots,s\} is a shorthand, \frac{\partial^{|u|}}{\partial\bm{y}_{u}}f denotes the mixed partial derivatives of f with respect to \bm{y}_{u}=(y_{j})_{j\in u} , -u denotes the complement of u in \{1:s\} , and \bm{y}_{-u}=(y_{j})_{j\in-u} . The function space is determined by the density function \phi:\mathbb{R}\to\mathbb{R} , the weight parameters \gamma_{u}>0 (with \gamma_{\emptyset}=1 ) and the weight functions \psi_{j}:\mathbb{R}\to\mathbb{R}_{+} . It is proven that by using the CBC construction, the QMC error bound is \mathcal{O}(N^{-r+\epsilon}) , where r is the decay rate of the Fourier coefficients of a function determined by \phi and \psi_{j} (see [ 17 , Theorem 7] for details). However, in practice, there are some limitations in the CBC construction. Firstly, to compute the shift-averaged worst-case error within a reasonable time, it is necessary to assume that the 2^{s}-1 weight parameters \gamma_{u} adhere to a certain structure, such as product weights, order dependent weights or product and order dependent (POD) weights [ 17 ] . Secondly, given an integrand f , the selection of the weight parameters and the weight functions is often quite challenging and requires a detailed analysis of the mixed partial derivatives of f (see for example [ 6 , 13 ] ). Thirdly, once the weight parameters and the weight functions are determined, one needs to run the CBC algorithm which finds a suitable generating vector. This involves the evaluation of (at least one) one-dimensional integrals over an unbounded domain, which contrasts with the scenario of integrands defined over [0,1]^{s} . We will elaborate on this distinction in detail in Section 2.2 . More recently, a series of median-based QMC methods for the evaluation of integrals over [0,1]^{s} have been developed in the works [ 8 , 9 , 21 , 22 ] . The median-based QMC methods use the median of several independent randomized QMC estimators as the final estimator of the integrand. For digital nets, the QMC points are randomized by a random linear scrambling [ 9 , 21 , 22 ] . For rank-1 lattice point sets, the QMC points are randomized by randomly choosing the generating vector [ 8 ] . The advantages of the median-based QMC methods lie in the computational convenience and the ability to achieve a nearly optimal convergence rate automatically without the need of prior knowledge of the weights or the smoothness properties of the integrands. However, these works are restricted to integrals over the unit cube [0,1]^{s} . In this paper, we investigate the integrals over \mathbb{R}^{s} within the framework of the unanchored weighted Sobolev space \mathcal{F} . The method studied in this paper is an extension of the construction-free median QMC rule in [ 8 ] to the unanchored weighted Sobolev space \mathcal{F} . Similar to the construction-free median QMC rule, our method does not require the knowledge about the weight parameters \gamma_{u} or the weight functions \psi_{j} . For an odd integer k>0 , we independently draw k random