arXiv:1502.01166

Tractability of Monte Carlo integration in Hermite spaces

Christian Irrgeher

Published Feb 4, 2015• 0 citations

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

International Journal of Wavelets Multiresolution and Information ProcessingMay 12, 20193 citations

Accelerating convergence and tractability of multivariate integration for infinitely differentiable functions

Kosuke Suzuki

May 8, 20152 citations

High-dimensional integration on $\mathbb{R}^d$, weighted Hermite spaces, and orthogonal transforms

Christian Irrgeher, Gunther Leobacher

arXiv:1409.6109Sep 22, 20142 citations

Tractability results for integration in subspaces of the Wiener algebra

Josef Dick, Takashi Goda, Kosuke Suzuki

arXiv:2410.09060Journal of ComplexityApr 16, 20254 citations

Tractability of multivariate analytic problems

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

arXiv:1407.1615De Gruyter eBooksJul 25, 201425 citations

Strong tractability of multivariate integration using quasi–Monte Carlo algorithms

Xiaoqun Wang

Mathematics of ComputationJun 25, 200256 citations

arXiv:1502.01166

Tractability of Monte Carlo integration in Hermite spaces

Christian Irrgeher

Published Feb 4, 2015• 0 citations

arXiv HTML PDF

Abstract

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.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 ProcessingMay 12, 20193 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.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, 20152 citations

High-dimensional integration on $\mathbb{R}^d$ , weighted Hermite spaces, and orthogonal transformsHigh-dimensional integration on $\mathbb{R}^d$, weighted Hermite spaces, and orthogonal transforms

Christian Irrgeher, Gunther Leobacher

It has been found empirically that quasi-Monte Carlo methods are often efficient for very high-dimensional problems, that is, with dimension in the hundreds or even thousands. The common explanation for this surprising fact is that those functions for which this holds true behave rather like low-dimensional functions in that only few of the coordinates have a size- able influence on its value. However, this statement may be true only after applying a suitable orthogonal transform to the input data, like utilizing the Brownian bridge construction or principal component analysis construction. We study the effect of general orthogonal transforms on functions on $\mathbb{R}^d$ which are ele- ments of certain weighted reproducing kernel Hilbert spaces. The notion of Hermite spaces is defined and it is shown that there are examples which admit tractability of integration. We translate the action of the orthogonal transform of $\mathbb{R}^d$ into an action on the Hermite coefficients and we give examples where orthogonal transforms have a dramatic effect on the weighted norm, thus providing an explanation for the efficiency of using suitable orthogonal transforms.It has been found empirically that quasi-Monte Carlo methods are often efficient for very high-dimensional problems, that is, with dimension in the hundreds or even thousands. The common explanation for this surprising fact is that those functions for which this holds true behave rather like low-dimensional functions in that only few of the coordinates have a size- able influence on its value. However, this statement may be true only after applying a suitable orthogonal transform to the input data, like utilizing the Brownian bridge construction or principal component analysis construction. We study the effect of general orthogonal transforms on functions on $\mathbb{R}^d$ which are ele- ments of certain weighted reproducing kernel Hilbert spaces. The notion of Hermite spaces is defined and it is shown that there are examples which admit tractability of integration. We translate the action of the orthogonal transform of $\mathbb{R}^d$ into an action on the Hermite coefficients and we give examples where orthogonal transforms have a dramatic effect on the weighted norm, thus providing an explanation for the efficiency of using suitable orthogonal transforms.

arXiv:1409.6109Sep 22, 20142 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.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.09060Journal of ComplexityApr 16, 20254 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.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.1615De Gruyter eBooksJul 25, 201425 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 })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 ComputationJun 25, 200256 citations

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.

High-dimensional integration on

\mathbb{R}^d

, weighted Hermite spaces, and orthogonal transforms

\mathbb{R}^d

which are ele- ments of certain weighted reproducing kernel Hilbert spaces. The notion of Hermite spaces is defined and it is shown that there are examples which admit tractability of integration. We translate the action of the orthogonal transform of

\mathbb{R}^d

into an action on the Hermite coefficients and we give examples where orthogonal transforms have a dramatic effect on the weighted norm, thus providing an explanation for the efficiency of using suitable orthogonal transforms.

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.