Tractability results for integration in subspaces of the Wiener algebra
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916643876110336 |
|---|---|
| author | Dick, Josef Goda, Takashi Suzuki, Kosuke |
| author_facet | Dick, Josef Goda, Takashi Suzuki, Kosuke |
| contents | 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 $\varepsilon$-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_09060 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tractability results for integration in subspaces of the Wiener algebra Dick, Josef Goda, Takashi Suzuki, Kosuke Computational Complexity 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 $\varepsilon$-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. |
| title | Tractability results for integration in subspaces of the Wiener algebra |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2410.09060 |