11institutetext: K. Harsha •M. Gnewuch •M. Wnuk 22institutetext: Institute for
Mathematics, Osnabrück University, Albrechtraße 28a, 49074 Osnabrück, Germany
22email<EMAIL_ADDRESS>33institutetext: M. Gnewuch
44institutetext: 44email<EMAIL_ADDRESS>55institutetext:
M. Wnuk 66institutetext: 66email<EMAIL_ADDRESS>
# Infinite-Variate $L^{2}$-Approximation with Nested Subspace Sampling

Kumar Harsha  Michael Gnewuch  and Marcin Wnuk

###### Abstract

We consider $L^{2}$-approximation on weighted reproducing kernel Hilbert
spaces of functions depending on infinitely many variables. We focus on
unrestricted linear information, admitting evaluations of arbitrary continuous
linear functionals. We distinguish between ANOVA and non-ANOVA spaces, where,
by ANOVA spaces, we refer to function spaces whose norms are induced by an
underlying ANOVA function decomposition. In ANOVA spaces, we provide an
optimal algorithm to solve the approximation problem using linear information.
We determine the upper and lower error bounds on the polynomial convergence
rate of $n$-th minimal worst-case errors, which match if the weights decay
regularly. For non-ANOVA spaces, we also establish upper and lower error
bounds. Our analysis reveals that for weights with a regular and moderate
decay behavior, the convergence rate of $n$-th minimal errors is strictly
higher in ANOVA than in non-ANOVA spaces.

##  1 Introduction

We want to investigate $L^{2}$-approximation on weighted reproducing kernel
Hilbert spaces (RKHSs) of functions depending on infinitely many variables.
For each of those RKHSs, there is a family of weights and a function
decomposition, which determine the norm on the space. With the help of the
function decomposition, it is possible to represent an infinite-variate
function as an infinite sum of functions depending only on finitely many
variables.

In this paper, we focus on linear algorithms that may obtain information about
an input function $f$ by evaluating finitely many continuous linear
functionals in $f$. The information cost of such an algorithm is the sum of
the cost of all functional evaluations, which, in turn, depends on the
underlying function decomposition of the weighted RKHS we are working on. Such
a situation has already been studied in Was12 ; WW11a , where the considered
cost model is a generalization of the one introduced in KSWW10a  for
information consisting only of function evaluation (so-called standard
information). In WW11a , a rather specific approximation problem, called the
$\mathcal{G}$-approximation problem, is analyzed; there, the approximation
error is measured in some very special Hilbert space $\mathcal{G}$. In Was12 ,
$L^{2}$-approximation is investigated in full generality, apart from the case
that can be reduced to the $\mathcal{G}$-approximation problem. To describe
the results from Was12 ; WW11a  and from this paper in a more common language,
we distinguish two cases of weighted RKHSs: the ones whose underlying function
decomposition is an ANOVA decomposition are called ANOVA spaces, whereas the
remaining RKHSs are referred to as non-ANOVA spaces (for a rigorous
definition, see Section 2.1).

The case of ANOVA spaces was covered by Wasilkowski and Woźniakowski, who in
WW11a  exactly determined the polynomial convergence rates $r_{\infty}$ of
$n$-th minimal errors (for a definition, see Section 2.2). For the non-ANOVA
spaces, Wasilkowski derived in Was12  a lower bound for $r_{\infty}$; with the
help of auxiliary weights, he re-used the constructive results from WW11a . He
also proved a matching upper bound. Interestingly, it turns out that for
slowly decaying weights, the convergence rate in the ANOVA case is superior to
the one in the non-ANOVA case, while it stayed the same if the weights
decrease quickly enough.

The cost model used in Was12 ; WW11a  is unrestricted subspace sampling (see
Section 2.2). In this paper, we instead consider the nested subspace sampling
cost model, which is less generous than the unrestricted one. For the nested
subspace sampling cost model, we have derived lower and upper bounds on the
polynomial convergence rate $r_{\infty}$ of $n$-th minimal errors in the ANOVA
case, see Theorem 3.2, where the bounds match if the weights exhibit a regular
decay behavior. In the non-ANOVA case, we are able to provide upper and
constructive lower bounds on $r_{\infty}$, see Propositions 1 and 2. Although
these bounds do not match in general, they show that in some cases the
convergence rate in the ANOVA case is higher than the one in the non-ANOVA
case, cf. Corollary 2. The reason for that is mainly that the cost of an
algorithm may depend on what kind of function decomposition underlies the
function space it is defined on. This dependence, unfortunately, prevents us
from simply using the embedding machinery developed in HR13 ; GHHR17 ; GHHRW19
to transfer results for ANOVA spaces directly to spaces with a different
underlying function decomposition.

Notation For a set ${\bm{u}}$, we denote by $\left|{\bm{u}}\right|$ its
cardinality. We use the shorthand $[k]:=\\{1,\dots,k\\}$ for every
$k\in{\mathbb{N}}$.

For two non-negative functions $f,g:D\to{\mathbb{R}}$, we use $f\lesssim g$ to
denote that there exists a constant $C>0$ such that $f(x)\leq Cg(x)$ for all
$x\in D$. Likewise, we use $f\gtrsim g$ to denote that there exists $c>0$ such
that $f(x)\geq cg(x)$. Finally, we use $f\asymp g$ to denote that there exist
two constants $c_{1},c_{2}>0$ such that $c_{1}g(x)\leq f(x)\leq c_{2}g(x)$ for
all $x$. The notation also applies to sequences.

##  2 Function Spaces and Algorithms

For general results on reproducing kernel Hilbert spaces (RKHS) we refer to
Aro50 , and to GMR14  for results on the function spaces discussed below.

###  2.1 Weighted Function Spaces

Let $D\neq\emptyset$ be an arbitrary set, $\Sigma$ a $\sigma$-algebra on $D$,
and $\rho:\Sigma\to[0,1]$ a probability measure on $D$. Let $k:D\times
D\to{\mathbb{R}}$ be a reproducing kernel on $D$ such that

$H(1)\cap H(k)=\\{0\\};$

here and in the whole paper we follow the convention to denote by $H(k)$ the
uniquely determined Hilbert space with reproducing kernel $k$ and its norm by
$\|\cdot\|_{H(k)}$; in particular $H(1)$ is the space of all constant
functions on the corresponding domain $D$. Put

${\mathcal{U}}:=\\{{\bm{u}}\subset{\mathbb{N}}\,|\,\left|{\bm{u}}\right|<\infty\\},$

where $\left|{\bm{u}}\right|$ refers to the cardinality of ${\bm{u}}$. For
${\bm{u}}\in{\mathcal{U}}$ we define $k_{{\bm{u}}}:D^{\mathbb{N}}\times
D^{\mathbb{N}}\to{\mathbb{R}}$ by

$k_{{\bm{u}}}({\bm{x}},{\bm{y}}):=\prod_{j\in{\bm{u}}}k(x_{j},y_{j})\hskip
12.91663pt\text{for all ${\bm{x}},{\bm{y}}\in D^{\mathbb{N}}$.}$

Since $k_{{\bm{u}}}$ only depends on the variables $x_{j}$, $j\in{\bm{u}}$, we
may alternatively view it as a function on ${D^{{\bm{u}}}}$ by putting

$k_{{\bm{u}}}({\bm{x}}_{\bm{u}},{\bm{y}}_{\bm{u}}):=k_{{\bm{u}}}(\tilde{{\bm{x}}},\tilde{{\bm{y}}})$

for arbitrary $\tilde{{\bm{x}}},\tilde{{\bm{y}}}\in D^{\mathbb{N}}$ satisfying
$\tilde{{\bm{x}}}_{\bm{u}}={\bm{x}}_{\bm{u}}$,
$\tilde{{\bm{y}}}_{\bm{u}}={\bm{y}}_{\bm{u}}$, where
${\bm{x}}_{\bm{u}}:=\\{x_{j}\\}_{j\in{\bm{u}}}\in{D^{{\bm{u}}}}$. We use an
analogous convention for arbitrary functions on $D^{\mathbb{N}}$ that only
depend on variables $x_{j}$, $j\in{\bm{u}}$. We denote the RKHS with kernel
$k_{{\bm{u}}}$ by ${H_{{\bm{u}}}}:=H(k_{{\bm{u}}})$ and its norm by
$\|\cdot\|_{{H_{{\bm{u}}}}}$; in particular, we have $H_{\emptyset}=H(1)$ due
to the convention that an empty product is equal to $1$.

For a family
${\bm{\gamma}}=\\{\gamma_{{\bm{u}}}\\}_{{\bm{u}}\in{\mathcal{U}}}$ of non-
negative weights, we put

${\mathcal{U}}_{\bm{\gamma}}:=\\{{\bm{u}}\in{\mathcal{U}}\,|\,\gamma_{{\bm{u}}}>0\\}.$

We work with product weights which are given by a decreasing sequence of
weights $1\geq\gamma_{1}\geq\gamma_{2}\geq...\geq 0$ assigned to all the
variables. Then the weight (or importance) of an interacting set of variables
${\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}$ is given by
$\gamma_{\bm{u}}=\prod_{j\in{\bm{u}}}\gamma_{j}$. Moreover, we define

${\mathfrak{X}}:=\bigg{\\{}{\bm{x}}\in
D^{{\mathbb{N}}}\,\bigg{|}\,\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\gamma_{{\bm{u}}}k_{\bm{u}}({\bm{x}},{\bm{x}})<\infty\bigg{\\}}$

and the reproducing kernel
$K_{\bm{\gamma}}:{\mathfrak{X}}\times{\mathfrak{X}}\to{\mathbb{R}}$ by

$K_{\bm{\gamma}}({\bm{x}},{\bm{y}}):=\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\gamma_{{\bm{u}}}k_{{\bm{u}}}({\bm{x}},{\bm{y}})\hskip
8.61108pt{\bm{x}},{\bm{y}}\in{\mathfrak{X}}.$ (1)

We denote the corresponding RKHS by $H_{{\bm{\gamma}}}:=H(K_{\bm{\gamma}})$.
$H_{{\bm{\gamma}}}$ decomposes into an orthogonal sum of subspaces

$H_{{\bm{\gamma}}}=\bigoplus_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}H(\gamma_{{\bm{u}}}k_{\bm{u}}).$
(2)

Note that for ${\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}$ we have that
$H(\gamma_{{\bm{u}}}k_{{\bm{u}}})$ and ${H_{{\bm{u}}}}$ are equal as vector
spaces, but their norms differ by a factor $\gamma_{{\bm{u}}}^{-1/2}$. Hence,
the norm in $H_{{\bm{\gamma}}}$ is given by

$\left\|f\right\|_{H_{{\bm{\gamma}}}}^{2}=\sum_{{\bm{u}}\in{\mathcal{U}}_{\bm{\gamma}}}\gamma_{{\bm{u}}}^{-1}\left\|{f_{{\bm{u}}}}\right\|_{{H_{{\bm{u}}}}}^{2},$

where

$f=\sum_{{\bm{u}}\in{\mathcal{U}}_{\bm{\gamma}}}{f_{{\bm{u}}}},\hskip
12.91663pt{f_{{\bm{u}}}}\in{H_{{\bm{u}}}},$ (3)

is the uniquely defined function decomposition of $f$ in $H_{{\bm{\gamma}}}$.

We assume

$\int_{D}k(x,x)\,\textup{d}\rho(x)<\infty.$ (4)

It is well-known that (4) implies that $S:H(1+k)\to L^{2}(D,\rho)$ is a
compact operator. We denote the corresponding operator norm by
$\left\|S\right\|$. From this, we also get the compact mapping
${H_{{\bm{u}}}}\to L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}})$ for all
${\bm{u}}\in{\mathcal{U}}_{\bm{\gamma}}$. Furthermore, we assume

$\lim_{j\to\infty}\gamma_{{\bm{u}}_{j}}\left\|S\right\|^{2\left|{\bm{u}}_{j}\right|}=0,$
(5)

where $\\{{\bm{u}}_{j}\\}_{j\in{\mathbb{N}}}$ is some enumeration of the
elements of ${\mathcal{U}}_{{\bm{\gamma}}}$. It follows from (5) that the map
$H_{{\bm{\gamma}}}\to L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})$ is also
compact, see Wnuk22 [Theorem 2]. In particular, the _solution operator_ we
consider

$\mathcal{S}:H_{{\bm{\gamma}}}\to
L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})\,,\,f\mapsto f$

is well-defined and continuous.

######  Definition 1 (ANOVA kernels)

Let $k:D\times D\to{\mathbb{R}}$ be a reproducing kernel such that
$k(\cdot,x)\in L^{2}(D,\rho)$ for all $x\in D$. If the kernel satisfies the
_ANOVA condition_

$\int_{D}k(y,x)\textup{d}\rho(y)=0\quad\forall x\in D,$ (6)

then we call $k$ an _ANOVA kernel_. Otherwise, we call it a _non-ANOVA
kernel_.

###### Remark 1

  1. 1.

It is easily seen that under the assumptions of Definition 1, the ANOVA
condition (6) is equivalent to the condition that $\int_{D}f(y)\rho(y)=0$ for
all $f\in H(k)$.

  2. 2.

Consider the reproducing kernel as in (1) based on an ANOVA kernel $k:D\times
D\to{\mathbb{R}}$. Then for each $f\in H_{{\bm{\gamma}}}$, the function
decomposition as in (3) is the infinite-variate ANOVA decomposition, see
(BG14, , Remark 2.12). For instance, it implies that for each $f\in
H_{{\bm{\gamma}}}$, for all ${\bm{u}}\in{\mathcal{U}}$ and ${\bm{x}}\in
D^{{\mathbb{N}}}$

$\int_{D}{f_{{\bm{u}}}}({\bm{x}})\,\textup{d}\rho(x_{j})=0\hskip
12.91663pt\text{if $j\in u$.}$

Examples of ANOVA spaces include Korobov spaces, see e.g. (NW08, , Appendix
A.1) and unanchored Sobolev spaces, see e.g. (NW08, , Appendix
A.2.1,A.2.3),(BG14, , Section 5), and (DG14b, , Section 5). A notable example
of non-ANOVA spaces are anchored Sobolev spaces, see e.g. (NW08, , Appendix
A.2.2) or KSWW10a .

###  2.2 Algorithms, Cost Models, and Errors

#### Admissible algorithms and cost

We know that non-adaptive algorithms are as good as adaptive algorithms in the
class of all deterministic algorithms for linear problems $S:F\to G$ where $F$
is a pre-Hilbert space, see (NW08, , Theorem 4.5); for a precise definition of
deterministic algorithms, see TWW88 . Moreover, we know that linear algorithms
are optimal for the aforementioned linear problems, see (NW08, , Theorem 4.8).
Therefore, we may confine ourselves to linear algorithms using arbitrary
linear information of the form

$\mathcal{A}(f)=\sum_{j=1}^{n}L_{{\bm{u}}_{j}}(f)\cdot g_{j}$ (7)

for some $n\in{\mathbb{N}}$, $g_{j}\in
L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})$, index sets
${\bm{u}}_{j}\in{\mathcal{U}}_{{\bm{\gamma}}}$, and linear functionals
$L_{{\bm{u}}_{j}}\in H_{{\bm{\gamma}}}^{\ast}$ such that
$L_{{\bm{u}}_{j}}|_{{H_{{\bm{v}}}}}=0$ if ${\bm{v}}\nsubseteq{\bm{u}}_{j}$,
see TWW88 . Owing to the Riesz representation theorem, we can define the
linear functional $L_{{\bm{u}}_{j}}$ as inner product with a representer as

$L_{{\bm{u}}_{j}}(f):=\left\langle
f,\eta_{{\bm{u}}_{j}}\right\rangle_{H_{{\bm{\gamma}}}},\quad\text{where
}\eta_{{\bm{u}}_{j}}\in\bigoplus_{{\bm{v}}\subseteq{\bm{u}}_{j}}H_{{\bm{v}}}.$
(8)

The worst-case error of the algorithm $\mathcal{A}$ for $L^{2}$-approximation
with respect to $H_{{\bm{\gamma}}}$ is given as

$e(\mathcal{A},H_{{\bm{\gamma}}}):=e(\mathcal{A},\mathcal{S},H_{{\bm{\gamma}}}):=\sup_{\|f\|_{H_{{\bm{\gamma}}}}\leq
1}\|\mathcal{S}(f)-\mathcal{A}(f)\|_{L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})}.$

Let us fix a cost function $\$:{\mathbb{N}}_{0}\to[1,\infty)$ which is non-
decreasing. Consider a linear functional $L_{\bm{u}}$ given by
$L_{\bm{u}}:=\left\langle\cdot,\eta_{\bm{u}}\right\rangle_{H_{{\bm{\gamma}}}}$,
where $\eta_{\bm{u}}\in\bigoplus_{{\bm{v}}\subseteq{\bm{u}}}H_{{\bm{v}}}$ but
there exists no ${\bm{w}}\subsetneq{\bm{u}}$ such that
$\eta_{\bm{u}}\in\bigoplus_{{\bm{v}}\subseteq{\bm{w}}}H_{{\bm{v}}}$. Then the
cost of $L_{\bm{u}}$ in the _nested subspace sampling_ (NSS) model (c.f.
(GHHR17, , Sect. 5.1) or MR09 ; HMNR10 ; BG14 ; DG14a ) is given by

$\textup{cost}(L_{\bm{u}})=\$(\max{\bm{u}}),$

where, by convention, $\max\emptyset=0$. Furthermore, the cost of an algorithm
like (7) in the NSS model is given by

$\textup{cost}(\mathcal{A})=\sum_{j=1}^{n}\textup{cost}(L_{{\bm{u}}_{j}}).$

For comparison, the cost of evaluating a linear functional in the unrestricted
subspace sampling model as in WW11a ; Was12  depends on the number of "active
variables". More precisely, for the functional $L_{\bm{u}}$ considered above,
the corresponding cost is given by

$\textup{cost}^{\ast}(L_{\bm{u}})=\$(\left|{\bm{u}}\right|).$

#### Minimal errors and complexity

For the results in this paper, we work with the NSS cost model unless
specified otherwise. On that basis, we define the _$n$ -th minimal error_ for
$n\in{\mathbb{N}}$ as

$e(n,H_{{\bm{\gamma}}}):=\inf\\{e(\mathcal{A},H_{{\bm{\gamma}}})\ :\
\mathcal{A}\text{ as in \eqref{eq:lin_algo_all}}\text{ and
}\textup{cost}(\mathcal{A})\leq n\\}.$

The approximation problem is said to be _strongly tractable_ if and only if
there exist non-negative constants $c,\alpha>0$ such that for all
$n\in{\mathbb{N}}$, it holds that

$e(n,H_{{\bm{\gamma}}})\leq c\cdot n^{-\alpha}.$

In order to quantify convergence rates, we introduce the notion of decay
rates. The _lower polynomial decay rate_ of a null sequence of positive reals
${\bm{x}}:=\\{x_{j}\\}_{j\in{\mathbb{N}}}$ is given by

$\textup{d}^{\textup{low}}_{{\bm{x}}}:=\operatorname{decay}({\bm{x}})=\sup\left\\{\alpha\geq
0:\sum_{j\in{\mathbb{N}}}x_{j}^{1/\alpha}<\infty\right\\}.$ (9)

This leads to the definition of the _polynomial convergence rate of $n$-th
minimal errors_, c.f. (GHHR17, , Sec 4),

$r_{\infty}:=r_{\infty}(H_{{\bm{\gamma}}})=\operatorname{decay}(\\{e(n,H_{{\bm{\gamma}}})\\}_{n\in{\mathbb{N}}}),$
(10)

which is the quantity of interest in later sections. Since
$e(n,H_{{\bm{\gamma}}})$ forms a non-increasing sequence, the definition (10)
is equivalent to

$r_{\infty}(H_{{\bm{\gamma}}})=\sup\left\\{\alpha\geq
0:\lim_{n\to\infty}e(n,H_{{\bm{\gamma}}})n^{\alpha}=0\right\\},$

as mentioned without a proof in FHW12 ; for the reader’s convenience, we
present a proof in Lemma 7. We define the _upper polynomial decay rate_ of a
null sequence of positive reals $\\{x_{n}\\}_{n\in{\mathbb{N}}}$ as

$\textup{d}^{\textup{up}}_{{\bm{x}}}:=\inf\left\\{\alpha\geq
0:\inf_{n\in{\mathbb{N}}}x_{n}n^{\alpha}>0\right\\}.$ (11)

We show that
$\textup{d}^{\textup{low}}_{{\bm{x}}}\leq\textup{d}^{\textup{up}}_{{\bm{x}}}$
in general, see Lemma 8. Although one can construct sequences such that
$\textup{d}^{\textup{low}}_{{\bm{x}}}<\textup{d}^{\textup{up}}_{{\bm{x}}}$,
equality holds for most practical choices of sequences; confer Remark 3. In
any case, we highlight the difference in the lower and upper decay rates in
all results, except Corollary 2.

We now introduce complexity concepts which also appear in tractability studies
as another perspective on the minimal errors. Let $\varepsilon>0$ be the error
demand. The worst case _$\varepsilon$ -information complexity_, also referred
to as _$\varepsilon$ -complexity_ of function approximation is defined as,
c.f. WW11a ,

$\textup{comp}(\varepsilon,H_{{\bm{\gamma}}}):=\inf\left\\{\textup{cost}(\mathcal{A})\
:\ \mathcal{A}\text{ as in \eqref{eq:lin_algo_all}}\text{ and
}e(\mathcal{A},H_{{\bm{\gamma}}})\leq\varepsilon\right\\}.$

The approximation problem is strongly tractable if and only if there exist
non-negative constants $c,\alpha>0$ such that

$\textup{comp}(\varepsilon,H_{{\bm{\gamma}}})\leq
c\cdot\varepsilon^{-\alpha}.$

The _exponent of tractability_ is defined as

$p_{\infty}:=p_{\infty}(H_{{\bm{\gamma}}})=\inf\left\\{\alpha\geq 0:\exists
C_{\alpha}>0\forall\varepsilon\in(0,1)\
\textup{comp}(\varepsilon,H_{{\bm{\gamma}}})\leq
C_{\alpha}\varepsilon^{-\alpha}\right\\}.$ (12)

We can relate the exponent of tractability to the convergence rate of the
$n$-th minimal error as $r_{\infty}=1/p_{\infty}$.

#### Univariate and Multivariate $L^{2}$-Approximation

Consider the univariate solution operator $S:H(1+k)\to L^{2}(D,\rho),f\mapsto
f$. It follows from (4) that $S$ is compact. This means that the self-adjoint
operator $W:=S^{\ast}\circ S$ is compact and positive definite. Consequently,
$W$ has a null sequence of positive eigenvalues
${\bm{\lambda}}:=\\{\lambda_{j}\\}_{j\in{\mathbb{N}}}$ with a corresponding
set of eigenfunctions $\\{\eta_{j}\\}_{j\in{\mathbb{N}}}$ that form a complete
orthonormal system of $H(1+k)$ satisfying

$W(\eta_{j})=\lambda_{j}\eta_{j}.$ (13)

We assume that the eigenvalues are ordered, i.e.
$\lambda_{1}\geq\lambda_{2}\geq\dots$.

###### Remark 2

We provide three examples that exhibit a sharp decay rate for the eigenvalues
${\bm{\lambda}}$. For the approximation problem defined on a Korobov space of
smoothness $\alpha$, it can be checked that the eigenvalues behave as
$\lambda_{j}\asymp j^{-2\alpha}$; see (NW08, , p 341). On the classical
Sobolev space, the eigenvalues follow $\lambda_{j}\asymp j^{-2}$; see (WW11a,
, p 410). In both of these cases,
$\textup{d}^{\textup{up}}_{{\bm{\lambda}}}=\textup{d}^{\textup{low}}_{{\bm{\lambda}}}$.

Another example, which recently captured a lot of interest, is Hermite spaces
with the reproducing kernel
$k(x,y)=\sum_{\nu\in{\mathbb{N}}_{0}}\alpha_{\nu}^{-1}h_{\nu}(x)h_{\nu}(y)$
for $x,y\in{\mathbb{R}}$, where the Fourier weights $\alpha_{\nu}$ are
essentially of the form $\alpha_{\nu}:=(\nu+1)^{r}$ for some $r>1/2$ (PG), or
$\alpha_{\nu}:=2^{r\nu^{b}}$ for some $b,r>0$ (EG). Furthermore, $h_{\nu}$
denotes the $L^{2}$-normalized Hermite polynomial of degree $\nu$. The first
paper considering spaces of this type was IKP16 ; for more recent results, see
GHRR23  and the literature mentioned therein. Here, the eigenvalues are
$\lambda_{j}=\alpha_{j+1}^{-1}$ for $j\in{\mathbb{N}}$; see, e.g. (GHRR23, ,
Section 4.1.2). Hence, we have
$\textup{d}^{\textup{up}}_{\bm{\lambda}}=r=\textup{d}^{\textup{low}}_{\bm{\lambda}}$
in the case (PG) and
$\textup{d}^{\textup{up}}_{\bm{\lambda}}=\infty=\textup{d}^{\textup{low}}_{\bm{\lambda}}$
in the case (EG).

Let $\textup{d}^{\textup{low}}_{\bm{\lambda}}$ denote the lower decay rate of
the eigenvalues ${\bm{\lambda}}$ of $W$. We assume that
$\textup{d}^{\textup{low}}_{\bm{\lambda}}>1$ so that (4) is satisfied, since
$\int_{D}k(x,x)\,\textup{d}\rho(x)=\sum_{j\in{\mathbb{N}}}\lambda_{j}$.
Similarly, as in (9), we may define the convergence rate of the $n$-th minimal
errors of the univariate approximation problem as

$r_{1}:=r_{1}(H(1+k))=\operatorname{decay}(\\{e(n,H(1+k))\\}_{n\in{\mathbb{N}}}).$

We also know that $e(n,H(1+k))=\sqrt{\lambda_{n+1}}$, which means, c.f.
(Was12, , p 314),

$r_{1}=\textup{d}^{\textup{low}}_{\bm{\lambda}}/2.$

Let $S_{{\bm{u}}}:{H_{{\bm{u}}}}\to L^{2}(D^{{\bm{u}}},{\rho^{{\bm{u}}}})$ be
given by $S_{{\bm{u}}}(f)=f$ for all $f\in{H_{{\bm{u}}}}$. Owing to the tensor
product construction of spaces ${H_{{\bm{u}}}}$ for
${\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}$, the eigenpairs of the operator
${W_{{\bm{u}}}}:=S_{{\bm{u}}}^{\ast}\circ
S_{{\bm{u}}}:{H_{{\bm{u}}}}\to{H_{{\bm{u}}}}$ are of product form. In
particular, for ${\bm{u}}=\\{u_{1},u_{2},\dots,u_{k}\\}\in{\mathcal{U}}$ with
$k=\left|{\bm{u}}\right|$, and for all
${\bm{j}}=(j_{1},j_{2},\dots,j_{k})\in{\mathbb{N}}^{k}$, we define

$\lambda_{{\bm{u}},{\bm{j}}}:=\prod_{i=1}^{k}\lambda_{j_{i}}\quad\text{and}\quad\eta_{{\bm{u}},{\bm{j}}}({\bm{x}}):=\prod_{i=1}^{k}\eta_{j_{i}}(x_{u_{i}}),$

using the eigenvalues and eigenfunctions of the univariate operator as in
(13). Then

${W_{{\bm{u}}}}(\eta_{{\bm{u}},{\bm{j}}})=\lambda_{{\bm{u}},{\bm{j}}}\eta_{{\bm{u}},{\bm{j}}},$
(14)

and
$\left\langle\eta_{{\bm{u}},{\bm{i}}},\eta_{{\bm{u}},{\bm{j}}}\right\rangle_{{H_{{\bm{u}}}}}=\delta_{{\bm{i}},{\bm{j}}}$
for ${\bm{i}},{\bm{j}}\in{\mathbb{N}}^{k}$. Using the eigenpairs of
${W_{{\bm{u}}}}$, we can express the SVD of $S_{{\bm{u}}}$ as

$S_{{\bm{u}}}({f_{{\bm{u}}}})=\sum_{{\bm{j}}\in{\mathbb{N}}^{{\bm{u}}}}\sqrt{\lambda_{{\bm{u}},{\bm{j}}}}\left\langle{f_{{\bm{u}}}},\eta_{{\bm{u}},{\bm{j}}}\right\rangle_{{H_{{\bm{u}}}}}\cdot\bar{\eta}_{{\bm{u}},{\bm{j}}},$
(15)

where the

$\bar{\eta}_{{\bm{u}},{\bm{j}}}=S_{{\bm{u}}}(\eta_{{\bm{u}},{\bm{j}}})/\sqrt{\lambda_{{\bm{u}},{\bm{j}}}},\quad{\bm{j}}\in{\mathbb{N}}^{k},$
(16)

form an orthonormal system in $L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}})$. In
the same way as for the spaces ${H_{{\bm{u}}}}$, we now define a self-adjoint
operator for the infinite-variate setting

$\mathcal{W}:=\mathcal{S}^{\ast}\circ\mathcal{S}:H_{{\bm{\gamma}}}\to
H_{{\bm{\gamma}}}$

which is compact and positive definite.

##  3 ANOVA spaces

For notational clarity, we use $K_{\gamma}^{\textup{A}}$ and
$H_{{\bm{\gamma}}}^{\textup{A}}$ to refer to the infinite-variate ANOVA kernel
and the corresponding function space in this section. It is well known that in
ANOVA spaces we have, see, e.g. BG14 ,

$\left\langle{f_{{\bm{u}}}},{g_{{\bm{v}}}}\right\rangle_{L^{2}(D^{{\bm{u}}\cup{\bm{v}}},\rho^{{\bm{u}}\cup{\bm{v}}})}=0\quad\text{for
}{\bm{u}},{\bm{v}}\in{\mathcal{U}},{\bm{u}}\neq{\bm{v}},{f_{{\bm{u}}}}\in{H_{{\bm{u}}}},{g_{{\bm{v}}}}\in{H_{{\bm{v}}}}.$
(17)

###### Lemma 1

In the ANOVA setting, any linear continuous algorithm
$\mathcal{A}:H_{{\bm{\gamma}}}^{\textup{A}}\to
L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})$ satisfying
$\mathcal{A}({H_{{\bm{u}}}})\subseteq\mathcal{S}({H_{{\bm{u}}}})={H_{{\bm{u}}}}$
for all ${\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}$ also satisfies

$\left\|\mathcal{S}(f)-\mathcal{A}(f)\right\|_{L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})}^{2}=\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\left\|S_{{\bm{u}}}({f_{{\bm{u}}}})-A_{{\bm{u}}}({f_{{\bm{u}}}})\right\|_{L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}})}^{2},$

where ${A_{{\bm{u}}}}:{H_{{\bm{u}}}}\to
L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}})$ and
${A_{{\bm{u}}}}(f)=\mathcal{A}(f)$ for all $f\in{H_{{\bm{u}}}}$.

###### Proof

The statement follows directly from (3) and (17), using the fact that
$\mathcal{S}({f_{{\bm{u}}}})=S_{{\bm{u}}}({f_{{\bm{u}}}})$.

Analogous to WW11a , we define an approximation algorithm based on the SVD of
$S_{{\bm{u}}}$ from (15). Let $\delta\in(0,1)$ and define for
$f\in{H_{{\bm{u}}}}$

$A_{{\bm{u}},\delta}^{\ast}(f):=\sum_{{\bm{j}}\in
J(\delta,{\bm{u}})}\sqrt{\lambda_{{\bm{u}},{\bm{j}}}}\left\langle
f,\eta_{{\bm{u}},{\bm{j}}}\right\rangle_{{H_{{\bm{u}}}}}\cdot\bar{\eta}_{{\bm{u}},{\bm{j}}},$
(18)

where
$J(\delta,{\bm{u}}):=\\{{\bm{j}}:\sqrt{\lambda_{{\bm{u}},{\bm{j}}}}>\delta\\}$
and $\bar{\eta}_{{\bm{u}},{\bm{j}}}$ is given by (16). We want to combine all
the sub-algorithms $A_{{\bm{u}},\delta}^{\ast}:{H_{{\bm{u}}}}\to
L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}})$ for
${\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}$ to attack the approximation problem
on $H_{{\bm{\gamma}}}$. Let $\varepsilon\in(0,1)$ be the worst-case error
threshold for the infinite-variate problem, and define the set

$\displaystyle M_{{\bm{\gamma}}}(\varepsilon)$
$\displaystyle:=\bigcup_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\\{({\bm{u}},{\bm{j}}):{\bm{j}}\in
J(\varepsilon/\sqrt{\gamma_{{\bm{u}}}},{\bm{u}})\\}$ (19)
$\displaystyle=\left\\{({\bm{u}},{\bm{j}}):{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}},{\bm{j}}\in{\mathbb{N}}^{{\bm{u}}},\text{
and }\gamma_{{\bm{u}}}\lambda_{{\bm{u}},{\bm{j}}}>\varepsilon^{2}\right\\}.$

We now define the algorithm
$\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}}:H_{{\bm{\gamma}}}^{\textup{A}}\to
L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})$ as

$\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}}(f):=\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}A_{{\bm{u}},\varepsilon/\sqrt{\gamma_{{\bm{u}}}}}^{\ast}({f_{{\bm{u}}}})=\sum_{({\bm{u}},{\bm{j}})\in
M_{{\bm{\gamma}}}(\varepsilon)}\left\langle
f,\eta_{{\bm{u}},{\bm{j}}}\right\rangle_{{H_{{\bm{u}}}}}\cdot
S_{{\bm{u}}}(\eta_{{\bm{u}},{\bm{j}}}).$ (20)

###### Lemma 2

For any ${\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}$ and $\delta>0$, the
algorithm $A_{{\bm{u}},\delta}^{\ast}$ from (18) satisfies
$\left\|S_{{\bm{u}}}-A_{{\bm{u}},\delta}^{\ast}\right\|\leq\delta$.

###### Proof

Let $\delta\in(0,1)$. Then using (15) and Bessel’s inequality, we get

$\displaystyle\left\|S_{{\bm{u}}}(f)-A_{{\bm{u}},\delta}^{\ast}(f)\right\|^{2}_{L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}})}=\left\|\sum_{{\bm{j}}\notin
J(\delta,{\bm{u}})}\sqrt{\lambda_{{\bm{u}},{\bm{j}}}}\left\langle
f,\eta_{{\bm{u}},{\bm{j}}}\right\rangle_{{H_{{\bm{u}}}}}\cdot\bar{\eta}_{{\bm{u}},{\bm{j}}}\right\|^{2}_{L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}})}$
$\displaystyle=\sum_{{\bm{j}}\notin
J(\delta,{\bm{u}})}\lambda_{{\bm{u}},{\bm{j}}}\left|\left\langle
f,\eta_{{\bm{u}},{\bm{j}}}\right\rangle_{{H_{{\bm{u}}}}}\right|^{2}\left\|\bar{\eta}_{{\bm{u}},{\bm{j}}}\right\|^{2}_{L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}})}\leq\delta^{2}\sum_{{\bm{j}}\notin
J(\delta,{\bm{u}})}\left|\left\langle
f,\eta_{{\bm{u}},{\bm{j}}}\right\rangle_{{H_{{\bm{u}}}}}\right|^{2}\leq\delta^{2}\left\|f\right\|^{2}_{{H_{{\bm{u}}}}}.$

The result now follows by taking supremum over $f\in{H_{{\bm{u}}}}$ with
$\left\|f\right\|_{{H_{{\bm{u}}}}}=1$.

The next result is reformulated from (WW11a, , Theorem 1(i)), and has a
straightforward proof.

###### Corollary 1

In the ANOVA setting, the algorithm
$\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}}$ as in (20) achieves a
worst case error at most $\varepsilon$.

The following result was mentioned in WW11a  without a proof, therefore we
present it here for the reader’s convenience.

###### Lemma 3

The operator $\mathcal{W}=\mathcal{S}^{\ast}\mathcal{S}$ admits the following
decomposition over ANOVA spaces

$\mathcal{W}(f)=\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\gamma_{{\bm{u}}}{W_{{\bm{u}}}}({f_{{\bm{u}}}})\quad\forall
f\in H_{{\bm{\gamma}}}^{\textup{A}},\
f=\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}{f_{{\bm{u}}}}.$ (21)

###### Proof

The Definition 1 and the dominated convergence theorem imply that

$\displaystyle(\mathcal{W}f)({\bm{y}})$
$\displaystyle=\left\langle\mathcal{W}(f),K_{\gamma}(\cdot,{\bm{y}})\right\rangle_{H_{{\bm{\gamma}}}^{\textup{A}}}=\left\langle\mathcal{S}(f),\mathcal{S}(K_{\gamma}(\cdot,{\bm{y}}))\right\rangle_{L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})}$
$\displaystyle=\int_{{\mathfrak{X}}}K_{\gamma}({\bm{x}},{\bm{y}})f({\bm{x}})\textup{d}\rho^{{\mathbb{N}}}({\bm{x}})=\int_{{\mathfrak{X}}}\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\gamma_{{\bm{u}}}k_{{\bm{u}}}({\bm{x}}_{\bm{u}},{\bm{y}}_{\bm{u}})f({\bm{x}})\textup{d}\rho^{{\mathbb{N}}}({\bm{x}})$
$\displaystyle=\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\gamma_{{\bm{u}}}\int_{{D^{{\bm{u}}}}}k_{{\bm{u}}}({\bm{x}}_{\bm{u}},{\bm{y}}_{\bm{u}}){f_{{\bm{u}}}}({\bm{x}}_{\bm{u}})\textup{d}\rho^{{\bm{u}}}({\bm{x}}_{\bm{u}})=\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\gamma_{{\bm{u}}}({W_{{\bm{u}}}}{f_{{\bm{u}}}})({\bm{y}}_{\bm{u}}).$

The result now follows.

Using the eigenpairs from (14) and Lemma 3, we can conclude that the
eigenpairs of $\mathcal{W}$ with positive eigenvalues are

$\left\\{\left(\gamma_{{\bm{u}}}\lambda_{{\bm{u}},{\bm{j}}},\xi_{{\bm{u}},{\bm{j}}}\right):{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}},{\bm{j}}\in{\mathbb{N}}^{{\bm{u}}}\right\\},$
(22)

with eigenfunctions
$\xi_{{\bm{u}},{\bm{j}}}:=\sqrt{\gamma_{{\bm{u}}}}\eta_{{\bm{u}},{\bm{j}}}$
normalized in $H_{{\bm{\gamma}}}^{\textup{A}}$. We can now express the
solution operator $\mathcal{S}$ using its singular values and the orthonormal
system as

$\displaystyle\mathcal{S}(f)=\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\sum_{{\bm{j}}\in{\mathbb{N}}^{{\bm{u}}}}\left\langle
f,\eta_{{\bm{u}},{\bm{j}}}\right\rangle_{{H_{{\bm{u}}}}}\cdot\mathcal{S}(\eta_{{\bm{u}},{\bm{j}}})=\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\sum_{{\bm{j}}\in{\mathbb{N}}^{{\bm{u}}}}\sqrt{\gamma_{{\bm{u}}}\lambda_{{\bm{u}},{\bm{j}}}}\
\left\langle
f,\xi_{{\bm{u}},{\bm{j}}}\right\rangle_{H_{{\bm{\gamma}}}}\cdot\bar{\eta}_{{\bm{u}},{\bm{j}}},$

where $\bar{\eta}_{{\bm{u}},{\bm{j}}}$ is as defined in (16).

The next result is the analogue of (WW11a, , Theorem 1(iii)) where it was
proven for unrestricted subspace sampling. It can be checked that the proof
follows verbatim and the arguments hold irrespective of the cost model.

###### Theorem 3.1

In the nested subspace sampling model, the cost of the algorithm
$\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}}$ is minimal amongst
all algorithms that achieve a worst case error of at most $\varepsilon$.

Due to Theorem 3.1, $\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}}$
from (20) is the optimal algorithm for the approximation problem in ANOVA
function spaces. Therefore, it suffices to compute the cost of
$\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}}$ to determine the
$\varepsilon$-complexity. Let

$\displaystyle M(\varepsilon,k)$
$\displaystyle:=\left\\{({\bm{u}},{\bm{j}}):k\in{\bm{u}}\subseteq[k],{\bm{j}}\in{\mathbb{N}}^{{\bm{u}}},\gamma_{{\bm{u}}}\lambda_{{\bm{u}},{\bm{j}}}>\varepsilon^{2}\right\\},\quad\text{and}$
(23) $\displaystyle\quad n_{k}$
$\displaystyle:=\left|M(\varepsilon,k)\right|.$

In order to simplify the cost analysis later on, we can rewrite the optimal
algorithm from (20) in a multilevel fashion as

$\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}}(f)=\sum_{k=1}^{m_{\varepsilon}}\sum_{({\bm{u}},{\bm{j}})\in
M(\varepsilon,k)}\left\langle
f,\eta_{{\bm{u}},{\bm{j}}}\right\rangle_{{H_{{\bm{u}}}}}\cdot\mathcal{S}(\eta_{{\bm{u}},{\bm{j}}}),$
(24)

where $m_{\varepsilon}\in{\mathbb{N}}$ is the largest number $k$ such that
$n_{k}>0$.

###### Lemma 4

For an error threshold $\varepsilon>0$, the optimal algorithm
$\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}}$ samples from
$m_{\varepsilon}$ levels which can be estimated as

$m_{\varepsilon}\gtrsim\varepsilon^{-2/p_{1}}\quad\forall
p_{1}\in(\textup{d}^{\textup{up}}_{\bm{\gamma}},\infty),$

and

$m_{\varepsilon}\lesssim\varepsilon^{-2/p_{2}}\quad\forall
p_{2}\in(0,\textup{d}^{\textup{low}}_{\bm{\gamma}}).$

###### Proof

We have for all $p_{1}\in(\textup{d}^{\textup{up}}_{\bm{\gamma}},\infty)$ and
$p_{2}\in(0,\textup{d}^{\textup{low}}_{\bm{\gamma}})$

$\gamma_{j}\gtrsim j^{-p_{1}}\quad\text{and}\quad\gamma_{j}\lesssim
j^{-p_{2}},$ (25)

see Lemma 9. We have $(\\{m_{\varepsilon}+1\\},1)\notin
M_{{\bm{\gamma}}}(\varepsilon)$ which means
$\gamma_{m_{\varepsilon}+1}\lambda_{1}\leq\varepsilon^{2}$. Using the lower
bound from (25), we get for some $c_{1}>0$

$c_{1}\lambda_{1}(m_{\varepsilon}+1)^{-p_{1}}\leq\lambda_{1}\gamma_{m_{\varepsilon}+1}\leq\varepsilon^{2}\implies(c_{1}\lambda_{1})^{1/p_{1}}\varepsilon^{-2/p_{1}}\leq
m_{\varepsilon}+1.$

Therefore, we get

$m_{\varepsilon}\geq(c_{1}\lambda_{1})^{1/p_{1}}\varepsilon^{-2/p_{1}}-1,$
(26)

and the lower bound from the lemma follows.

To show the remaining upper bound from the lemma, we note that
$\bigl{(}\\{m_{\varepsilon}\\},1\bigr{)}\in M_{{\bm{\gamma}}}(\varepsilon)$
must hold, which is equivalent to the condition
$\lambda_{1}\gamma_{m_{\varepsilon}}>\varepsilon^{2}$. Then using (25) we get
for some constant $c_{2}>0$

$\varepsilon^{2}<\lambda_{1}\gamma_{m_{\varepsilon}}\leq
c_{2}\lambda_{1}m_{\varepsilon}^{-p_{2}}\implies
m_{\varepsilon}\leq(c_{2}\lambda_{1})^{1/p_{2}}\varepsilon^{-2/p_{2}},$ (27)

giving us the desired upper bound.

We now want to estimate the cardinality of $M(\varepsilon,k)$ as defined in
(23). Before we proceed, we introduce the following notation. Let
$({\bm{u}}_{1},{\bm{j}}_{1}),({\bm{u}}_{2},{\bm{j}}_{2})\in
M_{{\bm{\gamma}}}(\varepsilon)$ such that
${\bm{u}}_{1}\cap{\bm{u}}_{2}=\emptyset$,
$\left|{\bm{u}}_{1}\right|=k_{1},\left|{\bm{u}}_{2}\right|=k_{2}$ and
${\bm{j}}_{1}\in{\mathbb{N}}^{k_{1}},{\bm{j}}_{2}\in{\mathbb{N}}^{k_{2}}$.
Then, we define
$({\bm{u}}_{1},{\bm{j}}_{2})\times({\bm{u}}_{2},{\bm{j}}_{2})=({\bm{u}},{\bm{j}})$
with
${\bm{u}}={\bm{u}}_{1}\cup{\bm{u}}_{2},{\bm{j}}\in{\mathbb{N}}^{{\bm{u}}_{1}\cup{\bm{u}}_{2}}$
such that $j_{i}=j_{1,i}$ if $i\in{\bm{u}}_{1}$, and $j_{i}=j_{2,i}$ if
$i\in{\bm{u}}_{2}.$ Moreover, we define
$\overline{M}(\varepsilon,k):=\left\\{(k,j):j\in{\mathbb{N}},\gamma_{k}\lambda_{j}>\varepsilon^{2}\right\\}$,
and $\overline{n}_{k}:=\left|\overline{M}(\varepsilon,k)\right|$.

It is straightforward to show that for every
$\tau\in(0,\textup{d}^{\textup{low}}_{\bm{\gamma}})$ and every constant
$C_{\tau}>0$

$\sum_{k\in{\bm{u}}\subseteq[k]}\gamma_{{\bm{u}}}^{1/\tau}C_{\tau}^{\left|{\bm{u}}\right|}\asymp\gamma_{k}^{1/\tau};$
(28)

confer (DG14a, , Theorem 5 and Corollary 1) where the statement was proved for
more general weights.

###### Lemma 5

Let $\varepsilon\in(0,1)$ and $k\in[m_{\varepsilon}]$. Then for all
$q_{1}\in(\textup{d}^{\textup{up}}_{\bm{\lambda}},\infty)$ and
$q_{2}\in(1,\textup{d}^{\textup{low}}_{\bm{\lambda}})$ we have the following
properties.

  1. 1.

$M(\varepsilon,k+1)=\overline{M}(\varepsilon,k+1)\cup\bigcup_{\ell=1}^{k}\bigcup_{j\in{\mathbb{N}}}\left\\{(\\{k+1\\},j)\times
M\left(\frac{\varepsilon}{\sqrt{\gamma_{k+1}\lambda_{j}}},\ell\right)\right\\}$.

  2. 2.

$\left|M(\varepsilon,k+1)\right|=\left|\overline{M}(\varepsilon,k+1)\right|+\sum_{\ell=1}^{k}\sum_{j\in{\mathbb{N}}}\left|M\left(\frac{\varepsilon}{\sqrt{\gamma_{k+1}\lambda_{j}}},\ell\right)\right|$.

  3. 3.

$\left|\overline{M}(\varepsilon,k)\right|\gtrsim\gamma_{k}^{1/q_{1}}\varepsilon^{-2/q_{1}}$.

  4. 4.

$\left|\overline{M}(\varepsilon,k)\right|\lesssim\gamma_{k}^{1/q_{2}}\varepsilon^{-2/q_{2}}$.

  5. 5.

$\left|M(\varepsilon,k)\right|\lesssim\varepsilon^{-2/q_{2}}\sum_{k\in{\bm{u}}\subseteq[k]}\gamma_{{\bm{u}}}^{1/q_{2}}c({\bm{\lambda}},q_{2})^{\left|u\right|-1}$,
where
$c({\bm{\lambda}},q_{2})=\sum_{j\in{\mathbb{N}}}\lambda_{j}^{1/q_{2}}<\infty$.

  6. 6.

$\left|M(\varepsilon,k)\right|\lesssim\varepsilon^{-2/q_{2}}\gamma_{k}^{1/q_{2}}$,
if additionally
$q_{2}\in(1,\min\\{\textup{d}^{\textup{low}}_{\bm{\lambda}},\textup{d}^{\textup{low}}_{\bm{\gamma}}\\})$.

###### Proof

We have for all $q_{1}\in(\textup{d}^{\textup{up}}_{\bm{\lambda}},\infty)$ and
$q_{2}\in(1,\textup{d}^{\textup{low}}_{\bm{\lambda}})$ that

$\lambda_{j}\gtrsim j^{-q_{1}}\quad\text{and}\quad\lambda_{j}\lesssim
j^{-q_{2}}.$ (29)

Note that the set $M_{{\bm{\gamma}}}(\varepsilon)$ is non-empty since
$\varepsilon^{2}<1$.

  1. 1.

Let $({\bm{u}}\cup\\{k+1\\},({\bm{j}},j_{k+1}))\in M(\varepsilon,k+1)$ where
$\emptyset\neq{\bm{u}}\subseteq[k],{\bm{j}}\in{\mathbb{N}}^{{\bm{u}}}$ and
$j_{k+1}\in{\mathbb{N}}$. Since we have product weights, the definition (23)
requires that
$\gamma_{{\bm{u}}}\lambda_{{\bm{j}}}>\varepsilon^{2}/\gamma_{k+1}\lambda_{j_{k+1}}$.
Let $\ell=\max({\bm{u}})$, then $\ell\in{\bm{u}}\subseteq[\ell]$ and

$({\bm{u}},{\bm{j}})\in
M\left(\frac{\varepsilon}{\sqrt{\gamma_{k+1}\lambda_{j_{k+1}}}},\ell\right).$

  2. 2.

Note that the right-hand side in statement 1 is a union of disjoint sets.

  3. 3.

Using the lower bound from (29), and the definition of
$\overline{M}(\varepsilon,k)$, we get for some $c_{1}>0$ that

$c_{1}\gamma_{k}(\overline{n}_{k}+1)^{-q_{1}}\leq\lambda_{\overline{n}_{k}+1}\gamma_{k}\leq\varepsilon^{2}\implies\overline{n}_{k}\geq
c_{1}^{1/q_{1}}\gamma_{k}^{1/q_{1}}\varepsilon^{-2/q_{1}}-1.$

  4. 4.

Using the upper bound from (29), and the definition of
$\overline{M}(\varepsilon,k)$, we get for some $c_{2}>0$ that

$\varepsilon^{2}<\gamma_{k}\lambda_{\overline{n}_{k}}\leq
c_{2}\gamma_{k}\overline{n}_{k}^{-q_{2}}\implies\overline{n}_{k}\leq
c_{2}^{1/q_{2}}\gamma_{k}^{1/q_{2}}\varepsilon^{-2/q_{2}}.$

  5. 5.

We prove this result by induction. For $k=1$, we have due to statement 4

$n_{1}=\left|M(\varepsilon,1)\right|=\left|\overline{M}(\varepsilon,1)\right|\lesssim\gamma_{1}^{1/q_{2}}\varepsilon^{-2/q_{2}}.$

We suppose now that the bound is true for
$M(\varepsilon,1),\dots,M(\varepsilon,k)$. Using statements 2 and 4, we get
for some $c_{2}>0$

$\displaystyle\left|M(\varepsilon,k+1)\right|$
$\displaystyle=\left|\overline{M}(\varepsilon,k+1)\right|+\sum_{\ell=1}^{k}\sum_{j\in{\mathbb{N}}}\left|M\left(\frac{\varepsilon}{\sqrt{\gamma_{k+1}\lambda_{j}}},\ell\right)\right|$
$\displaystyle\leq
c_{2}\varepsilon^{-2/q_{2}}\gamma_{k+1}^{1/q_{2}}+c_{2}\sum_{\ell=1}^{k}\sum_{j\in{\mathbb{N}}}\left(\frac{\varepsilon}{\sqrt{\gamma_{k+1}\lambda_{j}}}\right)^{-2/q_{2}}\sum_{\ell\in{\bm{u}}\subseteq[\ell]}\gamma_{{\bm{u}}}^{1/q_{2}}c({\bm{\lambda}},q_{2})^{\left|u\right|-1}$
$\displaystyle=c_{2}\varepsilon^{-2/q_{2}}\gamma_{k+1}^{1/q_{2}}\left[1+\sum_{\ell=1}^{k}\sum_{\ell\in{\bm{u}}\subseteq[\ell]}\gamma_{{\bm{u}}}^{1/q_{2}}c({\bm{\lambda}},q_{2})^{\left|u\right|-1}\sum_{j\in{\mathbb{N}}}\lambda_{j}^{1/q_{2}}\right]$
$\displaystyle=c_{2}\varepsilon^{-2/q_{2}}\left[\gamma_{k+1}^{1/q_{2}}+\gamma_{k+1}^{1/q_{2}}\sum_{\emptyset\neq{\bm{u}}\subseteq[k]}\gamma_{{\bm{u}}}^{1/q_{2}}c({\bm{\lambda}},q_{2})^{\left|u\right|}\right]$
$\displaystyle=c_{2}\varepsilon^{-2/q_{2}}\sum_{k+1\in{\bm{u}}\subseteq[k+1]}\gamma_{{\bm{u}}}^{1/q_{2}}c({\bm{\lambda}},q_{2})^{\left|u\right|-1}.$

  6. 6.

The estimate follows directly by applying (28) to the formula in statement 5.

This completes the proof.

###### Theorem 3.2

Let
$\textup{d}^{\textup{low}}_{\bm{\gamma}},\textup{d}^{\textup{low}}_{\bm{\lambda}}>1$
and $\$(k)\asymp k^{s}$ for some $s>0$. Then the convergence rate of the
$n$-th minimal errors using the nested subspace sampling cost model in ANOVA
function spaces with product weights is bounded as follows

$\min\left\\{\frac{\textup{d}^{\textup{low}}_{\bm{\lambda}}}{2},\frac{\textup{d}^{\textup{low}}_{\bm{\gamma}}}{2(1+s)}\right\\}\leq
r_{\infty}^{A}\leq\min\left\\{\frac{\textup{d}^{\textup{low}}_{\bm{\lambda}}}{2},\frac{\textup{d}^{\textup{up}}_{\bm{\gamma}}}{2(1+s)}\right\\}.$

###### Proof

Let $\varepsilon$ be the desired worst case error, and $m_{\varepsilon}$ be
the highest level for our algorithm.

We first show
$r_{\infty}^{A}\leq\min\left\\{\frac{\textup{d}^{\textup{low}}_{\bm{\lambda}}}{2},\frac{\textup{d}^{\textup{up}}_{\bm{\gamma}}}{2(1+s)}\right\\}$
using $\$(k)\gtrsim k^{s}$. The inequality
$r_{\infty}\leq\textup{d}^{\textup{low}}_{\bm{\lambda}}/2$ holds since the
infinite-variate problem is at least as difficult as the univariate problem.
It only remains to consider the case when
$\textup{d}^{\textup{up}}_{\bm{\gamma}}/(1+s)<\textup{d}^{\textup{low}}_{\bm{\lambda}}\leq\textup{d}^{\textup{up}}_{\bm{\lambda}}$.
Since $\overline{M}(\varepsilon,k)\subset M(\varepsilon,k)$, we use the lower
bound on $\left|\overline{M}(\varepsilon,k)\right|$ from statement 3 of Lemma
5, and (25) to get

$\textup{cost}(\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}})\geq\sum_{k=1}^{m_{\varepsilon}}\left|\overline{M}(\varepsilon,k)\right|\cdot\$(k)\gtrsim\varepsilon^{-2/q_{1}}\sum_{k=1}^{m_{\varepsilon}}\gamma_{k}^{1/q_{1}}k^{s}\gtrsim\varepsilon^{-2/q_{1}}\sum_{k=1}^{m_{\varepsilon}}k^{s-p_{1}/q_{1}},$
(30)

where for $\delta>0$ arbitrarily small, we chose
$p_{1}=\textup{d}^{\textup{up}}_{\bm{\gamma}}(1+\delta)$ and
$q_{1}=\textup{d}^{\textup{up}}_{\bm{\lambda}}(1+\delta)$. Consequently, we
have $s-p_{1}/q_{1}>-1$, and we use Lemma 4 to estimate the sum in (30) as

$\sum_{k=1}^{m_{\varepsilon}}k^{s-p_{1}/q_{1}}\gtrsim(m_{\varepsilon})^{1-p_{1}/q_{1}+s}\gtrsim\varepsilon^{-2(1-p_{1}/q_{1}+s)/p_{1}},$

which implies that
$\textup{cost}(\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}})\gtrsim\varepsilon^{-2(1+s)/p_{1}}$.
As $\delta\to 0$, we have $p_{1}\to\textup{d}^{\textup{up}}_{\bm{\gamma}}$ and
$r_{\infty}^{A}\leq\textup{d}^{\textup{up}}_{\bm{\gamma}}/2(1+s)$.

We now show that
$r_{\infty}^{A}\geq\min\left\\{\frac{\textup{d}^{\textup{low}}_{\bm{\lambda}}}{2},\frac{\textup{d}^{\textup{low}}_{\bm{\gamma}}}{2(1+s)}\right\\}$
using $\$(k)\lesssim k^{s}$. We use (25) and statement 6 from Lemma 5 to get

$\displaystyle\textup{cost}(\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}})=\sum_{k=1}^{m_{\varepsilon}}\left|M(\varepsilon,k)\right|\cdot\$(k)\lesssim\varepsilon^{-2/q_{2}}\sum_{k=1}^{m_{\varepsilon}}\gamma_{k}^{1/q_{2}}k^{s}\lesssim\varepsilon^{-2/q_{2}}\sum_{k=1}^{m_{\varepsilon}}k^{s-p_{2}/q_{2}},$
(31)

where we choose $\delta>0$ arbitrarily small so that
$p_{2}=\textup{d}^{\textup{low}}_{\bm{\gamma}}(1-\delta)$ and
$q_{2}=\min\\{\textup{d}^{\textup{low}}_{\bm{\gamma}},\textup{d}^{\textup{low}}_{\bm{\lambda}}\\}(1-\delta)>1$.
We analyze the last expression in (31) in three cases.

  1. 1.

$\textup{d}^{\textup{low}}_{\bm{\gamma}}/(1+s)>\textup{d}^{\textup{low}}_{\bm{\lambda}}\implies
s-p_{2}/q_{2}<-1$: Then $\sum_{k=1}^{m_{\varepsilon}}k^{s-p_{2}/q_{2}}\lesssim
1$. Since $\textup{d}_{\bm{\gamma}}>\textup{d}^{\textup{low}}_{\bm{\lambda}}$
in this case, we have
$q_{2}=\textup{d}^{\textup{low}}_{\bm{\lambda}}(1-\delta)$. Therefore, as
$\delta\to 0$, we get $q_{2}\to\textup{d}^{\textup{low}}_{\bm{\lambda}}$ and
$r_{\infty}^{A}\geq\textup{d}^{\textup{low}}_{\bm{\lambda}}/2$.

  2. 2.

$\textup{d}^{\textup{low}}_{\bm{\gamma}}/(1+s)=\textup{d}^{\textup{low}}_{\bm{\lambda}}\implies
s-p_{2}/q_{2}=-1$: For this case, we get the estimate
$\sum_{k=1}^{m_{\varepsilon}}k^{-1}\lesssim 1+\ln(m_{\varepsilon})\lesssim
1+\frac{2}{p_{2}}\ln(1/\varepsilon)$, where we used Lemma 4 for the last
relation. We set $q_{2}=\textup{d}^{\textup{low}}_{\bm{\lambda}}(1-\delta)$
since
$\textup{d}^{\textup{low}}_{\bm{\gamma}}>\textup{d}^{\textup{low}}_{\bm{\lambda}}$.
Consequently, we have
$\textup{cost}(\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}})\lesssim\varepsilon^{-2/q_{2}}(1+\ln(1/\varepsilon))$.
We can ignore the logarithmic term as $\delta\to 0$ to get
$q_{2}\to\textup{d}^{\textup{low}}_{\bm{\lambda}}$ and
$r_{\infty}^{A}\geq\textup{d}^{\textup{low}}_{\bm{\lambda}}/2$.

  3. 3.

$\textup{d}^{\textup{low}}_{\bm{\gamma}}/(1+s)<\textup{d}^{\textup{low}}_{\bm{\lambda}}\implies
s-p_{2}/q_{2}>-1$: For an appropriate choice of $q_{2}$, and due to Lemma 4 we
get

$\sum_{k=1}^{m_{\varepsilon}}k^{-p_{2}/q_{2}+s}\lesssim
m_{\varepsilon}^{1-p_{2}/q_{2}+s}\lesssim\varepsilon^{-2(1-p_{2}/q_{2}+s)/p_{2}}.$

Consequently,
$\textup{cost}(\mathcal{A}_{\varepsilon,{\bm{\gamma}}}^{\textup{opt}})\lesssim\varepsilon^{-2(1+s)/p_{2}}$
which is independent of $q_{2}$. Hence, as $\delta\to 0$, we set
$p_{2}\to\textup{d}^{\textup{low}}_{\bm{\gamma}}$ to get
$r_{\infty}^{A}\geq\textup{d}^{\textup{low}}_{\bm{\gamma}}/2(1+s)$.

This completes the proof.

##  4 Non-ANOVA spaces

Let us now turn to the case where the underlying function decomposition of our
Hilbert space $H_{{\bm{\gamma}}}$ is not of ANOVA-type. In this section, we
assume that
$1<\textup{d}^{\textup{low}}_{\bm{\gamma}}\leq\textup{d}^{\textup{up}}_{\bm{\gamma}}<\infty$.
We start by proving an upper bound on the convergence rate of $n$-th minimal
errors.

###### Proposition 1

Let $\$(k)\gtrsim k^{s}$ for any $k\in{\mathbb{N}}$ and some $s>0$. Then the
optimal convergence rate for the algorithms defined as in (7) satisfy in non-
ANOVA function spaces

$r_{\infty}\leq\min\left\\{\frac{\textup{d}^{\textup{low}}_{\bm{\lambda}}}{2},\frac{\textup{d}^{\textup{up}}_{\bm{\gamma}}-1}{2s}\right\\}.$

###### Proof

The bound $r_{\infty}\leq\textup{d}^{\textup{low}}_{\bm{\lambda}}/2$ follows
from the rate of convergence for the univariate problem.

To show the other part, we adapt the proof strategy from (Was12, , Proposition
4). Let $\mathcal{A}_{N}$ be a linear algorithm using finitely many function
evaluations, such that $\textup{cost}(\mathcal{A}_{N})\leq N$. We now choose
$L:=\sup\left\\{k:\$(k)\leq N\right\\}.$ Due to this definition, $[L]$ is a
superset of all the indices that the algorithm $\mathcal{A}_{N}$ relies on.
Since we assumed that $\$(k)\gtrsim k^{s}$, there exists a constant $c>0$ such
that $k^{s}/c^{s}\leq\$(k)$, implying $L\leq cN^{1/s}$.

Consider a univariate function $h\in H(k)$ such that
$\left\|h\right\|_{H(k)}=1$ and $c_{1}:=\int_{D}h(x)\textup{d}\rho(x)\neq 0$,
cf. Remark 1. Then define $f^{\ast}\in H_{{\bm{\gamma}}}$ as

$f^{\ast}({\bm{x}}):=\frac{1}{\kappa}\sum_{j>L}\gamma_{j}h(x_{j}),\quad\text{with
}\kappa:=\sqrt{\sum_{j>L}\gamma_{j}}.$

Accordingly, we get $\mathcal{A}_{N}(f^{\ast})=0$ due to our choice of $L$ and
$f^{\ast}$, as shown in Was12 . Moreover,
$\left\|f^{\ast}\right\|_{H_{{\bm{\gamma}}}}=1$, and also

$\left\|f^{\ast}\right\|_{L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})}^{2}=\left(\left\|h\right\|_{L^{2}(D,\rho)}^{2}-c_{1}^{2}\right)\frac{\sum_{j>L}\gamma_{j}^{2}}{\sum_{j>L}\gamma_{j}}+c_{1}^{2}\sum_{j>L}\gamma_{j}.$

We need an estimate only for the second term in the equation above since the
first term is positive but much smaller. It follows from Lemma 9 that
$\sum_{j>L}\gamma_{j}\gtrsim
L^{1-\textup{d}^{\textup{up}}_{\bm{\gamma}}-\delta}\gtrsim
N^{(1-\textup{d}^{\textup{up}}_{\bm{\gamma}}-\delta)/s}$ for all $\delta>0$.
From the construction of $f^{\ast}$, we have for the error that

$e(\mathcal{A}_{N};H_{{\bm{\gamma}}})=\sup_{\left\|f\right\|_{H_{{\bm{\gamma}}}}=1}\left\|f-\mathcal{A}_{N}(f)\right\|_{L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})}\geq\left\|f^{\ast}\right\|_{L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})}\gtrsim
N^{(1-\textup{d}^{\textup{up}}_{\bm{\gamma}}-\delta)/2s}.$

This shows that $r_{\infty}\leq(\textup{d}^{\textup{up}}_{\bm{\gamma}}-1)/2s$,
and the result follows.

For non-ANOVA spaces, Lemma 3 does not hold in general, which means that we do
not know how to express the eigenpairs of $\mathcal{W}:H_{{\bm{\gamma}}}\to
H_{{\bm{\gamma}}}$ in terms of the eigenpairs of ${W_{{\bm{u}}}}$. For the
upper error bound, we use results from Was12  which are stated below for the
reader’s convenience.

###### Lemma 6

For all $c\in(1/\textup{d}^{\textup{low}}_{\bm{\gamma}},1)$ it holds that
$\sup_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\gamma_{{\bm{u}}}^{1-c}\left\|S\right\|^{2\left|{\bm{u}}\right|}<\infty.$

  1. 1.

For

$\widehat{{\bm{\gamma}}}_{c}=\\{\widehat{\gamma}_{{\bm{u}},c}\\}_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}},\quad{\widehat{\gamma}}_{{\bm{u}},c}:=\gamma_{{\bm{u}}}^{1-c},$

we define
$\phi:H_{{\bm{\gamma}}}\to{H_{\widehat{{\bm{\gamma}}}_{c}}},f\mapsto\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\gamma_{{\bm{u}}}^{-c/2}{f_{{\bm{u}}}}$.
Then $\phi$ is an isometric isomorphism between $H_{{\bm{\gamma}}}$ and
${H_{\widehat{{\bm{\gamma}}}_{c}}}$. Furthermore,
$H_{{\bm{\gamma}}}\subseteq{H_{\widehat{{\bm{\gamma}}}_{c}}}$.

  2. 2.

Let $\mathcal{A}$ be a linear continuous algorithm satisfying

$\mathcal{A}({H_{{\bm{u}}}})\subseteq
L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}}),$ (32)

for all ${\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}$. Then we get the upper
bound

$\left\|\mathcal{S}(f)-\mathcal{A}(f)\right\|_{L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})}^{2}\leq
C_{{\bm{\gamma}}}\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\left\|S_{{\bm{u}}}(\widehat{f}_{{\bm{u}}})-A_{{\bm{u}}}(\widehat{f}_{{\bm{u}}})\right\|^{2}_{L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}})}$
(33)

where
$C_{{\bm{\gamma}}}=\sum_{{\bm{v}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\gamma_{{\bm{v}}}^{c}$,
$\phi(f)=:\widehat{f}=\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\widehat{f}_{\bm{u}}$
for all $f\in H_{{\bm{\gamma}}}$, and ${A_{{\bm{u}}}}:{H_{{\bm{u}}}}\to
L^{2}({D^{{\bm{u}}}},{\rho^{{\bm{u}}}})$ such that
${A_{{\bm{u}}}}(f)=\mathcal{A}(f)$ for all $f\in{H_{{\bm{u}}}}$.

It is straightforward to check that $\phi$ defines an isometric isomorphism.
$H_{{\bm{\gamma}}}\subseteq{H_{\widehat{{\bm{\gamma}}}_{c}}}$ is due to
(Was12, , Lemma 2). The inequality (33) has been derived in the proof of
(Was12, , Lemma 2) for any algorithm $\mathcal{A}$ satisfying (32).

###### Proposition 2

For any $\varepsilon\in(0,1)$, define the set
$M_{\widehat{{\bm{\gamma}}}_{c}}(\varepsilon)$ as in (19) and also the
algorithm
$\mathcal{A}_{\varepsilon,\widehat{{\bm{\gamma}}}_{c}}^{\textup{opt}}:{H_{\widehat{{\bm{\gamma}}}_{c}}}\to
L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})$ as defined in (20). Then the
algorithm
$\mathcal{A}_{\varepsilon,\widehat{{\bm{\gamma}}}_{c}}^{\textup{opt}}$
satisfies (32) and
$e(\mathcal{A}_{\varepsilon,\widehat{{\bm{\gamma}}}_{c}}^{\textup{opt}},\mathcal{S},H_{{\bm{\gamma}}})\leq\varepsilon$.
The algorithm
$\mathcal{A}_{\varepsilon,\widehat{{\bm{\gamma}}}_{c}}^{\textup{opt}}$
establishes that

$r_{\infty}\geq\min\left\\{\frac{\textup{d}^{\textup{low}}_{\bm{\lambda}}}{2},\frac{\textup{d}^{\textup{low}}_{\bm{\gamma}}-1}{2(1+s)}\right\\}.$

###### Proof

Using Lemmas 6 and 2, we get

$\displaystyle\left\|\mathcal{S}(f)-\mathcal{A}_{\varepsilon,\widehat{{\bm{\gamma}}}_{c}}^{\textup{opt}}(f)\right\|_{L^{2}({\mathfrak{X}},\rho^{\mathbb{N}})}^{2}\lesssim\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\left\|S_{{\bm{u}}}(\widehat{f}_{{\bm{u}}})-A_{{\bm{u}},\varepsilon/\sqrt{{\widehat{\gamma}}_{{\bm{u}},c}}}^{\ast}(\widehat{f}_{{\bm{u}}})\right\|^{2}_{L^{2}(D^{{\bm{u}}},\rho^{{\bm{u}}})}$
$\displaystyle\leq\varepsilon^{2}\sum_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}\frac{1}{{\widehat{\gamma}}_{{\bm{u}},c}}\left\|\widehat{f}_{\bm{u}}\right\|^{2}_{{H_{{\bm{u}}}}}=\varepsilon^{2}\left\|\widehat{f}\right\|^{2}_{{H_{\widehat{{\bm{\gamma}}}_{c}}}}=\varepsilon^{2}\left\|f\right\|^{2}_{H_{{\bm{\gamma}}}}.$

Notice that
$\mathcal{A}_{\varepsilon,\widehat{{\bm{\gamma}}}_{c}}^{\textup{opt}}$ has the
same cost in ${H_{\widehat{{\bm{\gamma}}}_{c}}}$ and in its subspace
$H_{{\bm{\gamma}}}$, since the function space decomposition in both spaces
rely on the same family of subspaces
$({H_{{\bm{u}}}})_{{\bm{u}}\in{\mathcal{U}}_{{\bm{\gamma}}}}$. Let
$\textup{d}^{\textup{low}}_{\widehat{{\bm{\gamma}}}_{c}}$ denote the lower
decay rate of product weights $\widehat{{\bm{\gamma}}}_{c}$. Then from (31),
and the subsequent analysis in Theorem 3.2, we get

$r_{\infty}\geq\min\left\\{\frac{\textup{d}^{\textup{low}}_{\bm{\lambda}}}{2},\frac{\textup{d}^{\textup{low}}_{\widehat{{\bm{\gamma}}}_{c}}}{2(1+s)}\right\\}.$

Finally,
$\textup{d}^{\textup{low}}_{\widehat{{\bm{\gamma}}}_{c}}=\textup{d}^{\textup{low}}_{\bm{\gamma}}(1-c)\xrightarrow{c\to
1/\textup{d}^{\textup{low}}_{\bm{\gamma}}}\textup{d}^{\textup{low}}_{\bm{\gamma}}-1$.
This completes the proof.

###### Corollary 2

Assume that
$\textup{d}^{\textup{low}}_{\bm{\gamma}}=\textup{d}^{\textup{up}}_{\bm{\gamma}}=:\textup{d}_{\bm{\gamma}}$.
If $1<\textup{d}_{\bm{\gamma}}<1+s$, then the convergence rate of
$L^{2}$-approximation in ANOVA spaces is strictly larger than the one in non-
ANOVA spaces.

###### Proof

Note that due to $1<\textup{d}^{\textup{low}}_{\bm{\lambda}}$, the condition
$\textup{d}_{\bm{\gamma}}<1+s$ implies
$\textup{d}^{\textup{low}}_{\bm{\lambda}}>(\textup{d}_{\bm{\gamma}}-1)/s$.
Hence, under the given condition, the exact convergence rate of $n$-th minimal
errors in the ANOVA case from Theorem 3.2 is greater than the largest possible
convergence rate in the non-ANOVA case from Proposition 1, i.e.

$\min\left\\{\frac{\textup{d}^{\textup{low}}_{\bm{\lambda}}}{2},\frac{\textup{d}_{\bm{\gamma}}-1}{2s}\right\\}=\frac{\textup{d}_{\bm{\gamma}}-1}{2s}<\min\left\\{\frac{\textup{d}^{\textup{low}}_{\bm{\lambda}}}{2},\frac{\textup{d}_{\bm{\gamma}}}{2(1+s)}\right\\}=\frac{\textup{d}_{\bm{\gamma}}}{2(1+s)}.$

The statement is hence proved.

As we see from the analysis, there is a gap between the convergence rates in
the ANOVA and the non-ANOVA setting. Note that we can use the function
$f^{\ast}$ from Proposition 1 to obtain the same upper bound on the
convergence rate for the integration problem in the non-ANOVA setting,
$I:H_{{\bm{\gamma}}}\to{\mathbb{R}}$. More specifically, we have
$I(f^{\ast})=c_{1}\sqrt{\sum_{j>L}\gamma_{j}}\gtrsim
N^{(1-\textup{d}^{\textup{up}}_{\bm{\gamma}}-\delta)/2s}$, which implies that
the convergence rate is at most
$(\textup{d}^{\textup{up}}_{\bm{\gamma}}-1)/2s$. On the other hand, the
integration problem is trivial in the ANOVA setting. This provides some
intuition for the gap since we know that the function approximation problem
is, in general, not easier than the integration problem.

###### Acknowledgements.

We thank an anonymous referee for helpful comments, and for pointing out the
second example in Remark 3.

## Appendix

For a null sequence of positive reals
${\bm{x}}:=\\{x_{j}\\}_{j\in{\mathbb{N}}}$, set
$\textup{d}^{\textup{low}}_{1}:=\textup{d}^{\textup{low}}_{{\bm{x}}}$ as in
(9) and define the following quantities:

$\displaystyle\textup{d}^{\textup{low}}_{2}$ $\displaystyle:=$
$\displaystyle\sup\\{\alpha\geq
0:\lim_{n\to\infty}x_{n}n^{\alpha}=0\\},\quad\text{and}$ (34)
$\displaystyle\textup{d}^{\textup{low}}_{3}$ $\displaystyle:=$
$\displaystyle\sup\\{\alpha\geq
0:\sup_{n\in{\mathbb{N}}}x_{n}n^{\alpha}<\infty\\}.$ (35)

###### Lemma 7

If ${\bm{x}}$ is a non-increasing null sequence of positive reals, then we
have the following identity

$\textup{d}^{\textup{low}}_{1}=\textup{d}^{\textup{low}}_{2}=\textup{d}^{\textup{low}}_{3}.$

###### Proof

We first claim
$\textup{d}^{\textup{low}}_{1}\leq\textup{d}^{\textup{low}}_{3}$. Let
$\alpha<\textup{d}^{\textup{low}}_{1}$. Using the monotonicity of ${\bm{x}}$,
we get for all $N\in{\mathbb{N}}$

$Nx_{N}^{1/\alpha}\leq\sum_{n=1}^{N}x_{n}^{1/\alpha}\leq\sum_{n=1}^{\infty}x_{n}^{1/\alpha}=:c_{1}<\infty.$

Therefore, for all $N\in{\mathbb{N}}$, we have $x_{N}N^{\alpha}\leq
c_{1}^{\alpha}$, implying $\alpha\leq\textup{d}^{\textup{low}}_{3}$. As
$\alpha\to\textup{d}^{\textup{low}}_{1}$, we have the claim.

Next, we show
$\textup{d}^{\textup{low}}_{3}\leq\textup{d}^{\textup{low}}_{2}$. Let
$\alpha<\textup{d}^{\textup{low}}_{3}$. Then we know that
$\\{x_{n}n^{\alpha}\\}$ is bounded. Consequently, for every $\varepsilon>0$,
the sequence $\\{x_{n}n^{\alpha-\varepsilon}\\}$ converges to zero, and
$\alpha-\varepsilon\leq\textup{d}^{\textup{low}}_{2}$. In the limit as
$\varepsilon\to 0$ and $\alpha\to\textup{d}^{\textup{low}}_{3}$, we have the
result.

Finally, we prove
$\textup{d}^{\textup{low}}_{2}\leq\textup{d}^{\textup{low}}_{1}$. Let
$\alpha<\textup{d}^{\textup{low}}_{2}$ and $c_{2}>0$. From (34), we know that
there exists $N_{2}\in{\mathbb{N}}$ such that for all $n\geq N_{2}$, we have
$x_{n}\leq c_{2}n^{-\alpha}$. Then for all $\varepsilon>0$

$\sum_{n=1}^{\infty}x_{n}^{1/(\alpha-\varepsilon)}=\sum_{n=1}^{N_{2}-1}x_{n}^{1/(\alpha-\varepsilon)}+\sum_{n={N_{2}}}^{\infty}x_{n}^{1/(\alpha-\varepsilon)}\leq\sum_{n=1}^{N_{2}-1}x_{n}^{1/(\alpha-\varepsilon)}+c_{2}^{\frac{1}{\alpha-\varepsilon}}\sum_{n={N_{2}}}^{\infty}\frac{1}{n^{\frac{\alpha}{\alpha-\varepsilon}}}<\infty,$

which means $\alpha-\varepsilon\leq\textup{d}^{\textup{low}}_{1}$. The result
follows as $\varepsilon\to 0$ and $\alpha\to\textup{d}^{\textup{low}}_{2}$.

The identity is hence proved.

###### Lemma 8

Let $\textup{d}^{\textup{up}}_{{\bm{x}}}$ be defined as in (11). If ${\bm{x}}$
is a non-increasing null sequence of positive reals, then we have the
following inequality

$\textup{d}^{\textup{low}}_{\bm{x}}\leq\textup{d}^{\textup{up}}_{{\bm{x}}}.$

###### Proof

Due to Lemma 7, we know
$\textup{d}^{\textup{low}}_{\bm{x}}=\textup{d}^{\textup{low}}_{3}$. Let
$\alpha<\textup{d}^{\textup{low}}_{3}$. Then for all $\varepsilon>0$

$\sup_{n\in{\mathbb{N}}}x_{n}n^{\alpha}<\infty\implies\inf_{n\in{\mathbb{N}}}x_{n}n^{\alpha-\varepsilon}=0\implies\alpha-\varepsilon\leq\textup{d}^{\textup{up}}_{{\bm{x}}}.$

Taking the limit as $\varepsilon\to 0$ and
$\alpha\to\textup{d}^{\textup{low}}_{3}$, we get the desired inequality.

###### Remark 3

We provide two examples of sequences to show that the lower and upper decay
rates are equal in most relevant cases but can also differ significantly. As
first example, let $\\{x_{n}\\}_{n\in{\mathbb{N}}}$ behave as follows

$c_{1}n^{-\alpha}\ln(n+1)^{\beta_{1}}\leq x_{n}\leq
c_{2}n^{-\alpha}\ln(n+1)^{\beta_{2}},$

for $n$ large enough, where
$\alpha>0,c_{1},c_{2}>0,\beta_{1},\beta_{2}\in{\mathbb{R}}$ and
$\beta_{1}\leq\beta_{2}$. Then, we show
$\textup{d}^{\textup{low}}_{{\bm{x}}}=\textup{d}^{\textup{up}}_{{\bm{x}}}=\alpha$.
For all $\varepsilon>0$, we have

$\lim_{n\to\infty}x_{n}n^{\alpha-\varepsilon}\leq
c_{2}\lim_{n\to\infty}\frac{\ln(n+1)^{\beta_{2}}}{n^{\varepsilon}}=0.$

Since we consider only positive values for $x_{n}$, we actually get
$\lim_{n\to\infty}x_{n}n^{\alpha-\varepsilon}=0$. Hence, using (34), we get
$\textup{d}^{\textup{low}}_{{\bm{x}}}\geq\alpha$. Moreover, for all
$\varepsilon>0$, we also get

$\inf_{n\in{\mathbb{N}}}x_{n}n^{\alpha+\varepsilon}\geq
c_{1}\inf_{n\in{\mathbb{N}}}\ln(n+1)^{\beta_{1}}n^{\varepsilon}>0.$

Therefore, using (11), we have $\textup{d}^{\textup{up}}_{\bm{x}}\leq\alpha$.
From Lemma 8 follows
$\textup{d}^{\textup{low}}_{{\bm{x}}}=\alpha=\textup{d}^{\textup{up}}_{{\bm{x}}}$.

In contrast, define recursively $n_{1}=0$ and $n_{k+1}=2^{n_{k}}+1$ and
consider the sequence $y_{n}=2^{-n_{k}}$ for $n\in[n_{k},n_{k+1})$. In this
case, we show $\textup{d}^{\textup{low}}_{\bm{y}}=1$ and
$\textup{d}^{\textup{up}}_{\bm{y}}=\infty$. Let $0<\alpha<1$. Then

$\sum_{n\in{\mathbb{N}}}y_{n}^{1/\alpha}=\sum_{k\in{\mathbb{N}}}\sum_{n=n_{k}}^{n_{k+1}-1}2^{-n_{k}/\alpha}=\sum_{k\in{\mathbb{N}}}\frac{2^{n_{k}}-n_{k}}{2^{n_{k}/\alpha}}\leq\sum_{k\in{\mathbb{N}}}2^{-n_{k}(\frac{1}{\alpha}-1)}<\infty,$

which implies $\alpha\leq\textup{d}^{\textup{low}}_{\bm{y}}$ and hence
$\textup{d}^{\textup{low}}_{\bm{y}}\geq 1$. For $\alpha=1$, the series above
diverges. Therefore, we have $\textup{d}^{\textup{low}}_{\bm{y}}\leq 1$, and
altogether $\textup{d}^{\textup{low}}_{\bm{y}}=1$. On the other hand, we have
for all $\alpha>0$

$\inf_{n\in{\mathbb{N}}}y_{n}n^{\alpha}=\inf_{k\in{\mathbb{N}}}\min_{n\in[n_{k},n_{k+1})}y_{n}n^{\alpha}=\inf_{k\in{\mathbb{N}}}\min_{n\in[n_{k},n_{k+1})}\frac{n^{\alpha}}{2^{n_{k}}}=\inf_{n\in{\mathbb{N}}}\frac{n^{\alpha}}{2^{n}}=0.$

Consequently, $\textup{d}^{\textup{up}}_{\bm{y}}=\infty$.

###### Lemma 9

Let ${\bm{x}}$ be a non-increasing null sequence of positive reals with lower
and upper decay rates denoted by $\textup{d}^{\textup{low}}_{\bm{x}}$ and
$\textup{d}^{\textup{up}}_{\bm{x}}$. Then, for all
$p_{1}\in(\textup{d}^{\textup{up}}_{\bm{x}},\infty)$ and
$p_{2}\in(0,\textup{d}^{\textup{low}}_{\bm{x}})$

$n^{-p_{1}}\lesssim x_{n}\lesssim n^{-p_{2}}.$

###### Proof

From the definition in (11), we have
$c_{1}:=\inf_{n\in{\mathbb{N}}}x_{n}n^{p_{1}}>0$. Consequently, we have
$x_{n}n^{p_{1}}\geq c_{1}$ and hence $x_{n}\geq c_{1}n^{-p_{1}}$.

We have shown in Lemma 7 that
$\textup{d}^{\textup{low}}_{\bm{x}}=\textup{d}^{\textup{low}}_{3}$.
Accordingly, from the definition in (35), we have
$c_{2}:=\sup_{n\in{\mathbb{N}}}x_{n}n^{p_{2}}<\infty$. This implies that for
all $n\in{\mathbb{N}}$, $x_{n}n^{p_{2}}\leq c_{2}$ and hence $x_{n}\leq
c_{2}n^{-p_{2}}$.

## References

  * (1) N. Aronszajn.  Theory of reproducing kernels.  Trans. Amer. Math. Soc., 68:337–404, 1950.
  * (2) J. Baldeaux and M. Gnewuch.  Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition.  SIAM J. Numer. Anal., 52:1128–1155, 2014.
  * (3) J. Dick and M. Gnewuch.  Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher order convergence.  Found. Comput. Math., 14:1027–1077, 2014.
  * (4) J. Dick and M. Gnewuch.  Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition.  J. Approx. Theory, 184:111–145, 2014.
  * (5) G. E. Fasshauer, F. J. Hickernell, and H. Woźniakowski.  On dimension-independent rates of convergence for function approximation with Gaussian kernels.  SIAM Journal on Numerical Analysis, 50(1):247–271, 2012.
  * (6) M. Gnewuch, M. Hefter, A. Hinrichs, and K. Ritter.  Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration.  Journal of Approximation Theory, 222:8–39, 2017.
  * (7) M. Gnewuch, M. Hefter, A. Hinrichs, K. Ritter, and G. W. Wasilkowski.  Embeddings for infinite-dimensional integration and ${L}_{2}$-approximation with increasing smoothness.  J. Complexity, 54:101406, 2019.
  * (8) M. Gnewuch, A. Hinrichs, K. Ritter, and R. Rüßmann.  Infinite-dimensional integration and ${L}^{2}$-approximation on Hermite spaces.
  * (9) M. Gnewuch, S. Mayer, and K. Ritter.  On weighted Hilbert spaces and integration of functions of infinitely many variables.  J. Complexity, 30:29–47, 2014.
  * (10) M. Hefter and K. Ritter.  On embeddings of weighted tensor product Hilbert spaces.  J. Complexity, 31:405–423, 2015.
  * (11) F. J. Hickernell, T. Müller-Gronbach, B. Niu, and K. Ritter.  Multi-level Monte Carlo algorithms for infinite-dimensional integration on $\mathbb{R}^{{\mathbb{N}}}$.  J. Complexity, 26:229–254, 2010.
  * (12) C. Irrgeher, P. Kritzer, F. Pillichshammer, and H. Woźniakowski.  Approximation in Hermite spaces of smooth functions.  Journal of Approximation Theory, 207:98–126, 2016.  ISSN 0021-9045.
  * (13) F. Y. Kuo, I. H. Sloan, G. W. Wasilkowski, and H. Woźniakowski.  Liberating the dimension.  J. Complexity, 26:422–454, 2010.
  * (14) T. Müller-Gronbach and K. Ritter.  Variable subspace sampling and multi-level algorithms.  In P. L’Ecuyer and A. B. Owen, editors, Monte Carlo and Quasi-Monte Carlo Methods 2008. Springer, 2009.
  * (15) E. Novak and H. Woźniakowski.  Tractability of Multivariate Problems. Vol. 1: Linear Information.  EMS Tracts in Mathematics. European Mathematical Society (EMS), Zürich, 2008.
  * (16) J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski.  Information-Based Complexity.  Academic Press, New York, 1988.
  * (17) G. W. Wasilkowski.  Liberating the dimension for ${L}_{2}$-approximation.  J. Complexity, 28:304–319, 2012.
  * (18) G. W. Wasilkowski and H. Woźniakowski.  Liberating the dimension for function approximation.  J. Complexity, 27:86–110, 2011.
  * (19) M. Wnuk.  A short note on compact embeddings of reproducing kernel Hilbert spaces in ${L}^{2}$ for infinite-variate function approximation.  In A. Hinrichs, P. Kritzer, and F. Pillichshammer, editors, Monte Carlo and Quasi-Monte Carlo Methods 2022. Springer Verlag, 2022.