Multi- and Infinite-variate Integration and L 2 L^{2} -Approximation on Hilbert Spaces with Gaussian Kernels
M. Gnewuch, K. Ritter, R. Rüßmann · 2024
Read Multi- and Infinite-variate Integration and L 2 L^{2} -Approximation on Hilbert Spaces with Gaussian Kernels by M. Gnewuch, K. Ritter, R. Rüßmann (2024) 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-2412-05368.txt.
Introduction
Michael Gnewuch, Klaus Ritter, and Robin Rüßmann pinned down error rates for averaging and fitting functions of very many variables in a 2024 paper. The function spaces use Gaussian kernels, a standard smooth setting, and algorithms may only sample function values. In the hardest case the number of variables is infinite, which arises in models with endless inputs.
For both averaging and least-squares fitting, they prove matching upper and lower bounds on how fast the best possible error shrinks as samples grow. For finitely many variables they improve known tractability results for averaging. A key bridge shows each Gaussian problem mirrors a Hermite-space problem with matched settings, letting results transfer. The bounds tell practitioners when high-dimensional sampling can succeed.
Catalog record
| CREATOR | M. Gnewuch, K. Ritter, R. Rüßmann |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 81 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-05368
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi- and Infinite-variate Integration and L 2 L^{2} -Approximation on Hilbert Spaces with Gaussian Kernels M. Gnewuch, K. Ritter, R. Rüßmann Abstract . We study integration and L 2 L^{2} -approximation in the worst-case setting for deterministic linear algorithms based on function evaluations. The underlying function space is a reproducing kernel Hilbert space with a Gaussian kernel of tensor product form. In the infinite-variate case, for both computational problems, we establish matching upper and lower bounds for the polynomial convergence rate of the n n -th minimal error. In the multivariate case, we improve several tractability results for the integration problem. For the proofs, we establish the following transference result together with an explicit construction: Each of the computational problems on a space with a Gaussian kernel is equivalent on the level of algorithms to the same problem on a Hermite space with suitable parameters. 1. Introduction We consider integration and L^{2} -approximation of functions f\colon{\mathfrak{X}}\to{\mathbb{R}} of d variables in the cases d\in{\mathbb{N}} and d=\infty , where the underlying measure \mu is the d -fold product of the univariate standard normal distribution \mu_{0} . The functions f are assumed to be elements of a reproducing kernel Hilbert space H(M) with a reproducing kernel M of tensor product form with domain {\mathfrak{X}}:={\mathfrak{X}}(M) . For d\in{\mathbb{N}} the domain is given by {\mathfrak{X}}:={\mathbb{R}}^{d} (and \mu is the d -dimensional standard normal distribution), while for d=\infty the domain {\mathfrak{X}} is a proper subset of the sequence space {\mathbb{R}}^{\mathbb{N}} with \mu({\mathfrak{X}})=1 . This setting, with \mu_{0} as before or with \mu_{0} being the uniform distribution on [0,1] , is frequently studied in the literature on multivariate or infinite-variate integration and approximation. Throughout this paper, we use the following notation. We put J:=\{1,\dots,d\} if d\in{\mathbb{N}} and J:={\mathbb{N}} if d=\infty , and h_{\nu} denotes the univariate Hermite polynomial of degree \nu\in{\mathbb{N}}_{0} , normalized in L^{2}(\mu_{0}) . We study two particular kinds of reproducing kernels. Primarily, we are interested in Gaussian kernels L_{\boldsymbol{\sigma}}({\boldsymbol{x}},{\boldsymbol{y}}):=\prod_{j\in J}\exp\left(-\sigma_{j}^{2}\cdot(x_{j}-y_{j})^{2}\right) with {\boldsymbol{x}},{\boldsymbol{y}}\in{\mathfrak{X}}(L_{\boldsymbol{\sigma}}) , which are specified by sequences {\boldsymbol{\sigma}}:=(\sigma_{j})_{j\in J} of shape parameters \sigma_{j}>0 . Additionally, we consider Hermite kernels K_{\boldsymbol{\beta}}({\boldsymbol{x}},{\boldsymbol{y}}):=\prod_{j\in J}\Biggl(\,\sum_{\nu=0}^{\infty}\beta_{j}^{\nu}\cdot h_{\nu}(x_{j})\cdot h_{\nu}(y_{j})\Biggr) with {\boldsymbol{x}},{\boldsymbol{y}}\in{\mathfrak{X}}(K_{\boldsymbol{\beta}}) , which are specified by sequences {\boldsymbol{\beta}}:=(\beta_{j})_{j\in J} of base parameters 0<\beta_{j}<1 . See Section 2 for the study of the function spaces H(L_{\boldsymbol{\sigma}}) and H(K_{\boldsymbol{\beta}}) and, in the case d=\infty , of the corresponding domains {\mathfrak{X}}(L_{\boldsymbol{\sigma}}) and {\mathfrak{X}}(K_{\boldsymbol{\beta}}) . Here we only mention the following monotonicity properties: If {\boldsymbol{\sigma}}\leq{\boldsymbol{\sigma}}^{\prime} , then {\mathfrak{X}}(L_{{\boldsymbol{\sigma}}^{\prime}})\subseteq{\mathfrak{X}}(L_{{\boldsymbol{\sigma}}}) and the restriction f\mapsto f|_{{\mathfrak{X}}(L_{{\boldsymbol{\sigma}}^{\prime}})} defines a continuous mapping from H(L_{\boldsymbol{\sigma}}) to H(L_{{\boldsymbol{\sigma}}^{\prime}}) ; analogously, if {\boldsymbol{\beta}}\leq{\boldsymbol{\beta}}^{\prime} , then {\mathfrak{X}}(K_{{\boldsymbol{\beta}}^{\prime}})\subseteq{\mathfrak{X}}(K_{{\boldsymbol{\beta}}}) and the restriction f\mapsto f|_{{\mathfrak{X}}(K_{{\boldsymbol{\beta}}^{\prime}})} defines a continuous mapping from H(K_{\boldsymbol{\beta}}) to H(K_{{\boldsymbol{\beta}}^{\prime}}) . For both kernels, M:=L_{\boldsymbol{\sigma}} and M:=K_{\boldsymbol{\beta}} , and for both problems, integration and L^{2} -approximation, we analyze deterministic linear algorithms that are based on a fixed number of function evaluations in the worst-case setting on the unit ball in H(M) . Concerning the definition of cost we distinguish two cases: For finite d the cost per function evaluation at any point {\boldsymbol{x}}\in{\mathfrak{X}} is one, the most natural choice, so that the worst-case cost of an algorithm is equal to the number of function evaluations. For d=\infty it is widely accepted that the analogous definition of cost is too generous and non-predictive for computational practice. Therefore we employ the unrestricted subspace sampling model, which has been introduced in Kuo et al. (2010) to define the worst-case cost of algorithms for computational problems on spaces of functions of infinitely many variables. Accordingly, function evaluation is only permitted at points {\boldsymbol{x}}:=(x_{j})_{j\in J}\in{\mathfrak{X}} with finitely many non-zero components x_{j} , and \cost({\boldsymbol{x}}) , the cost for the evaluation at {\boldsymbol{x}} , depends non-decreasingly on the number of non-zero components. The worst-case setting is presented in detail in Section 3 . A key quantity in the analysis is the n -th minimal error e_{n}(M) for integration and for L^{2} -approximation, which is, roughly speaking, the smallest worst-case error on the unit ball in H(M) that can be achieved by any algorithm with worst-case cost at most n\in{\mathbb{N}} . In this framework integration and L^{2} -approximation on H(L_{\boldsymbol{\sigma}}) with d\in{\mathbb{N}} are studied in Fasshauer et al. (2012) , Kuo and Woźniakowski (2012) , Kuo et al. (2017) , Karvonen and Särkkä (2019) , and Karvonen et al. (2021) , see also Sloan and Woźniakowski (2018) . On H(K_{\boldsymbol{\beta}}) with d\in{\mathbb{N}} these problems are studied in Irrgeher et al. (2015) and in Irrgeher et al. (2016a) , see also Irrgeher et al. (2016b) . Actually, the kernels K_{\boldsymbol{\beta}} , which define spaces H(K_{\boldsymbol{\beta}}) of functions of infinite smoothness, are only particular elements of the broader class of Hermite kernels, which may also define spaces of functions of finite smoothness. Here we refer to Irrgeher and Leobacher (2015) , Dick et al. (2018) , and Leobacher et al. (2023) for results on integration and L^{2} -approximation with d\in{\mathbb{N}} . For d=\infty we are not aware of results on integration and L^{2} -approximation on spaces with Gaussian kernels, while spaces with Hermite kernels, including the kernels K_{\boldsymbol{\beta}} , have been studied for both problems in Gnewuch et al. (2024) . Numerous models in probability theory are ultimately based on a sequence of independent random variables, and in every such model expectations may be represented as integrals with respect to product measures. This motivates the study of integration of functions f defined on the sequence space {\mathbb{R}}^{\mathbb{N}} or subspaces thereof. Let us mention, for instance, the Lévy-Ciesielski (or Brownian bridge) representation of Brownian motion, which is based on an independent sequence of standard normally distributed random variables and thus leads to the measure \mu that is studied in this paper. In this setting, the results derived in this paper may potentially be used to compute expectations of smooth functionals of Brownian motion. In this paper we first of all establish a transference result for integration and a transference result for L^{2} -approximation, which yield for each of these problems and suitably related spaces H(L_{\boldsymbol{\sigma}}) and H(K_{\boldsymbol{\beta}}) the equivalence on the level of algorithms. The transference results only require that (1.1) \sum_{j\in J}\sigma_{j}^{2}<\infty, which is trivially satisfied in the case d\in{\mathbb{N}} . In the proofs we employ a particular isometric isomorphism between Hilbert spaces with Gaussian and with Hermite kernels, see Theorem 2.7 , which is due to Gnewuch et al. (2022) . For integration with any d the transference result reads as follows. Assume that the shape and base parameters are related by 1-\beta_{j}=\frac{1}{1+2\sigma_{j}^{2}} for every j\in J . Moreover, let e_{0}(M) denote the norm of the integration functional on H(M) . Then for every n\in{\mathbb{N}} there exists a bijection A\mapsto B on the set of all n -point quadrature formulas such that e(A,L_{{\boldsymbol{\sigma}}})=e_{0}(L_{\boldsymbol{\sigma}})\cdot e(B,K_{\boldsymbol{\beta}}) for the worst-case errors e(A,L_{\boldsymbol{\sigma}}) and e(B,K_{\boldsymbol{\beta}}) of A on the unit ball in H(L_{\boldsymbol{\sigma}}) and of B on the unit ball in H(K_{\boldsymbol{\beta}}) . See Theorem 4.3 . The bijection is given explicitly in Remark 4.4 , and the worst-case cost of A and B coincide also in the case d=\infty . Consequently, the minimal errors satisfy e_{n}(L_{{\boldsymbol{\sigma}}})=e_{0}(L_{\boldsymbol{\sigma}})\cdot e_{n}(K_{\boldsymbol{\beta}}) for every n\in{\mathbb{N}} . For L^{2} -approximation with any d an analogous transference result is established in Theorem 5.1 and Remark 5.2 , assuming that the