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

Tractability of Monte Carlo integration in Hermite spaces

Christian Irrgeher

Published Feb 4, 2015• 0 citations
arXivHTMLPDF

Abstract

We consider multivariate integration in the randomized setting. The function spaces which we study are defined on R^s with respect to the Gaussian measure and the functions are characterized by the decay of their Hermite coefficients. We study tractability of Monte Carlo integration and give necessary and sufficient conditions to achieve tractability.

DOI
10.48550/arxiv.1502.01166

Related papers

Quasi-Monte Carlo tractability of integration problem in function spaces defined over products of balls

Jie Zhang, Yongping Liu

Recently, quasi-Monte Carlo (QMC) rules for multivariate integration in some weighted Sobolev spaces of functions defined over unit cubes [Formula: see text], products of [Formula: see text] copies of the simplex [Formula: see text] and products of [Formula: see text] copies of the unit sphere [Formula: see text] have been well-studied in the literature. In this paper, we consider QMC tractability of integrals of functions defined over product of [Formula: see text] copies of the ball [Formula: see text]. The space is a tensor product of [Formula: see text] reproducing kernel Hilbert spaces defined by positive and uniformly bounded weights [Formula: see text] for [Formula: see text]. We obtain matching necessary and sufficient conditions in terms of this weights for various notions of QMC tractability, including strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniformly weak tractability and [Formula: see text]-weak tractability.

International Journal of Wavelets Multiresolution and Information Processing•May 12, 2019•3 citations

Accelerating convergence and tractability of multivariate integration for infinitely differentiable functions

Kosuke Suzuki

We investigate multivariate integration for a space of infinitely differentiable functions $ \mathcal{F}_{s, \boldsymbol{u}} := \{f \in C^\infty [0,1]^s \mid \| f \|_{\mathcal{F}_{s, \boldsymbol{u}} } := \sup_{(\alpha_1, \dots, \alpha_s) \in \mathbb{N}_0^s} \|f^{(\alpha_1, \dots, \alpha_s)}\|_{L^1}/\prod_{j=1}^s u_j^{\alpha_j} 1$ such that $e(n,s) \in O(q^{(\log{n})^{p}})$ holds as $n$ goes to infinity, where $e(n,s)$ may depend on $s$ in an arbitrary way. We prove that accelerating convergence holds for $p=2$ for any $\boldsymbol{u}$ and $s$ considered. We also study a sufficient condition for accelerating convergence with strong tractability (AC-ST), which means that there exist constants $C>0$, $0 1$ independent of $s$ such that $e(n,s) \leq C q^{(\log{n})^{p}}$ holds for all $s$ and $n$. We prove that AC-ST holds if the weights $\boldsymbol{u}$ decay sufficiently fast. These results come from the convergence and tractability results for the Walsh space into which $\mathcal{F}_{s, \boldsymbol{u}}$ is embedded.

•May 8, 2015•2 citations

Tractability of multivariate analytic problems

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which $s$-variate problems can be approximated to within $\varepsilon$ by using, say, polynomially many in $s$ and $\varepsilon^{-1}$ function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with $\varepsilon^{-1}$ replaced by $1+\log \varepsilon^{-1}$. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of $s$ and $1+\log \varepsilon^{-1}$. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.

arXiv:1407.1615•De Gruyter eBooks•Jul 25, 2014•22 citations

Tractability results for integration in subspaces of the Wiener algebra

Josef Dick, Takashi Goda, Kosuke Suzuki

In this paper, we present some new (in-)tractability results related to the integration problem in subspaces of the Wiener algebra over the d -dimensional unit cube. We show that intractability holds for multivariate integration in the standard Wiener algebra in the deterministic setting, in contrast to polynomial tractability in an unweighted subspace of the Wiener algebra recently shown by Goda (2023). Moreover, we prove that multivariate integration in the subspace of the Wiener algebra introduced by Goda is strongly polynomially tractable if we switch to the randomized setting, where we obtain a better ε -exponent than the one implied by the standard Monte Carlo method . We also identify subspaces in which multivariate integration in the deterministic setting are (strongly) polynomially tractable and we compare these results with the bound which can be obtained via Hoeffding's inequality.

arXiv:2410.09060•Journal of Complexity•Apr 16, 2025•4 citations

Strong tractability of multivariate integration using quasi–Monte Carlo algorithms

Xiaoqun Wang

We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })

Mathematics of Computation•Jun 25, 2002•58 citations

Exponential convergence and tractability of multivariate integration for Korobov spaces

Josef Dick, Gerhard Larcher, Friedrich Pillichshammer +1 more

In this paper we study multivariate integration for a weighted Korobov space for which the Fourier coefficients of the functions decay exponentially fast. This implies that the functions of this space are infinitely times differentiable. Weights of the Korobov space monitor the influence of each variable and each group of variables. We show that there are numerical integration rules which achieve an exponential convergence of the worst-case integration error. We also investigate the dependence of the worst-case error on the number of variables s s , and show various tractability results under certain conditions on weights of the Korobov space. Tractability means that the dependence on s s is never exponential, and sometimes the dependence on s s is polynomial or there is no dependence on s s at all.

Mathematics of Computation•Nov 2, 2010•50 citations
We consider multivariate integration in the randomized setting. The function spaces which we study are defined on R^s with respect to the Gaussian measure and the functions are characterized by the decay of their Hermite coefficients. We study tractability of Monte Carlo integration and give necessary and sufficient conditions to achieve tractability.
Recently, quasi-Monte Carlo (QMC) rules for multivariate integration in some weighted Sobolev spaces of functions defined over unit cubes [Formula: see text], products of [Formula: see text] copies of the simplex [Formula: see text] and products of [Formula: see text] copies of the unit sphere [Formula: see text] have been well-studied in the literature. In this paper, we consider QMC tractability of integrals of functions defined over product of [Formula: see text] copies of the ball [Formula: see text]. The space is a tensor product of [Formula: see text] reproducing kernel Hilbert spaces defined by positive and uniformly bounded weights [Formula: see text] for [Formula: see text]. We obtain matching necessary and sufficient conditions in terms of this weights for various notions of QMC tractability, including strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniformly weak tractability and [Formula: see text]-weak tractability.
We investigate multivariate integration for a space of infinitely differentiable functions $ \mathcal{F}_{s, \boldsymbol{u}} := \{f \in C^\infty [0,1]^s \mid \| f \|_{\mathcal{F}_{s, \boldsymbol{u}} } := \sup_{(\alpha_1, \dots, \alpha_s) \in \mathbb{N}_0^s} \|f^{(\alpha_1, \dots, \alpha_s)}\|_{L^1}/\prod_{j=1}^s u_j^{\alpha_j} 1$ such that e(n,s)∈O(q(log⁡n)p)e(n,s) \in O(q^{(\log{n})^{p}})e(n,s)∈O(q(logn)p) holds as nnn goes to infinity, where e(n,s)e(n,s)e(n,s) may depend on sss in an arbitrary way. We prove that accelerating convergence holds for p=2p=2p=2 for any u\boldsymbol{u}u and sss considered. We also study a sufficient condition for accelerating convergence with strong tractability (AC-ST), which means that there exist constants C>0C>0C>0, 010 101 independent of sss such that e(n,s)≤Cq(log⁡n)pe(n,s) \leq C q^{(\log{n})^{p}}e(n,s)≤Cq(logn)p holds for all sss and nnn. We prove that AC-ST holds if the weights u\boldsymbol{u}u decay sufficiently fast. These results come from the convergence and tractability results for the Walsh space into which Fs,u\mathcal{F}_{s, \boldsymbol{u}}Fs,u​ is embedded.
In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which sss-variate problems can be approximated to within ε\varepsilonε by using, say, polynomially many in sss and ε−1\varepsilon^{-1}ε−1 function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with ε−1\varepsilon^{-1}ε−1 replaced by 1+log⁡ε−11+\log \varepsilon^{-1}1+logε−1. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of sss and 1+log⁡ε−11+\log \varepsilon^{-1}1+logε−1. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.
In this paper, we present some new (in-)tractability results related to the integration problem in subspaces of the Wiener algebra over the d -dimensional unit cube. We show that intractability holds for multivariate integration in the standard Wiener algebra in the deterministic setting, in contrast to polynomial tractability in an unweighted subspace of the Wiener algebra recently shown by Goda (2023). Moreover, we prove that multivariate integration in the subspace of the Wiener algebra introduced by Goda is strongly polynomially tractable if we switch to the randomized setting, where we obtain a better ε -exponent than the one implied by the standard Monte Carlo method . We also identify subspaces in which multivariate integration in the deterministic setting are (strongly) polynomially tractable and we compare these results with the bound which can be obtained via Hoeffding's inequality.
We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })
In this paper we study multivariate integration for a weighted Korobov space for which the Fourier coefficients of the functions decay exponentially fast. This implies that the functions of this space are infinitely times differentiable. Weights of the Korobov space monitor the influence of each variable and each group of variables. We show that there are numerical integration rules which achieve an exponential convergence of the worst-case integration error. We also investigate the dependence of the worst-case error on the number of variables s s , and show various tractability results under certain conditions on weights of the Korobov space. Tractability means that the dependence on s s is never exponential, and sometimes the dependence on s s is polynomial or there is no dependence on s s at all.