# On the power of standard information for tractability for
$L_{2}$-approximation in the randomized setting

Wanting Lu  School of Mathematical Sciences, Capital Normal University,
Beijing 100048, China<EMAIL_ADDRESS>and  Heping Wang  School of
Mathematical Sciences, Capital Normal University, Beijing 100048, China.
<EMAIL_ADDRESS>
###### Abstract.

We study approximation of multivariate functions from a separable Hilbert
space in the randomized setting with the error measured in the weighted
$L_{2}$ norm. We consider algorithms that use standard information
$\Lambda^{\rm std}$ consisting of function values or general linear
information $\Lambda^{\rm all}$ consisting of arbitrary linear functionals. We
use the weighted least squares regression algorithm to obtain the upper
estimates of the minimal randomized error using $\Lambda^{\rm std}$. We
investigate the equivalences of various notions of algebraic and exponential
tractability for $\Lambda^{\rm std}$ and $\Lambda^{\rm all}$ for the
normalized or absolute error criterion. We show that in the randomized setting
for the normalized or absolute error criterion, the power of $\Lambda^{\rm
std}$ is the same as that of $\Lambda^{\rm all}$ for all notions of
exponential and algebraic tractability without any condition. Specifically, we
solve four Open Problems 98, 100-102 as posed by E.Novak and H.Woźniakowski in
the book: Tractability of Multivariate Problems, Volume III: Standard
Information for Operators, EMS Tracts in Mathematics, Zürich, 2012.

###### Key words and phrases:

Tractability, Standard information, general linear information, Randomized
setting

###### 2010 Mathematics Subject Classification:

41A63; 65C05; 65D15; 65Y20

##  1\. Introduction

We study multivariate approximation ${\rm APP}=\\{{\rm APP}_{d}\\}_{d\in{N}}$,
where

${{\rm APP}}_{d}:F_{d}\to G_{d}\ \ {\rm with}\ \ {\rm APP}_{d}\,f=f$

is the compact embedding operator, $F_{d}$ is a separable Hilbert function
space on $D_{d}$, $G_{d}$ is a weighted $L_{2}$ space on $D_{d}$,
$D_{d}\subset{R}^{d}$, and the dimension $d$ is large or even huge. We
consider algorithms that use finitely many information evaluations. Here
information evaluation means linear functional on $F_{d}$ (general linear
information) or function value at some point (standard information). We use
$\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ to denote the extended class of
all linear functionals (not necessarily continuous) and the extended class of
all function values (defined only almost everywhere), respectively.

For a given error threshold $\varepsilon\in(0,1)$, the information complexity
$n(\varepsilon,d)$ is defined to be the minimal number of information
evaluations for which the approximation error of some algorithm is at most
$\varepsilon$. Tractability is aimed at studying how the information
complexity $n(\varepsilon,d)$ depends on $\varepsilon$ and $d$. There are two
kinds of tractability based on polynomial convergence and exponential
convergence. The algebraic tractability (ALG-tractability) describes how the
information complexity $n(\varepsilon,d)$ behaves as a function of $d$ and
$\varepsilon^{-1}$, while the exponential tractability (EXP-tractability) does
as one of $d$ and $(1+\ln\varepsilon^{-1})$. The existing notions of
tractability mainly include strong polynomial tractability (SPT), polynomial
tractability (PT), quasi-polynomial tractability (QPT), weak tractability
(WT), $(s,t)$-weak tractability ($(s,t)$-WT), and uniform weak tractability
(UWT). In recent years the study of algebraic and exponential tractability has
attracted much interest, and a great number of interesting results have been
obtained (see [31, 32, 33, 43, 9, 44, 38, 39, 6, 5, 21, 36, 45, 15, 2, 26, 37]
and the references therein).

This paper is devoted to investigating the equivalences of various notions of
algebraic and exponential tractability for $\Lambda^{\rm std}$ and
$\Lambda^{\rm all}$ in the randomized setting (see [33, Chapter 22]). The
class $\Lambda^{\rm std}$ is much smaller and much more practical, and is much
more difficult to analyze than the class $\Lambda^{\rm all}$. Hence, it is
very important to study the power of $\Lambda^{\rm std}$ compared to
$\Lambda^{\rm all}$. There are many paper devoted to this field (see [33, 42,
23, 17, 11, 25, 47, 41, 24, 34, 35, 19, 20, 28, 12, 13, 18]).

In [42, 33] the authors obtained the equivalences of ALG-SPT, ALG-PT, ALG-QPT,
ALG-WT in the randomized setting for $\Lambda^{\rm std}$ and $\Lambda^{\rm
all}$ for the normalized error criterion without any condition. Meanwhile, for
the absolute error criterion under some conditions, the equivalences of ALG-
SPT, ALG-PT, ALG-QPT, ALG-WT were also obtained in [33].

In this paper, we obtain the remaining equivalences of all notions of
algebraic and exponential tractability in the randomized setting for
$\Lambda^{\rm std}$ and $\Lambda^{\rm all}$ for the normalized or absolute
error criterion without any condition. Our results particularly imply that for
the absolute error criterion the imposed conditions are not necessary. This
solves Open Problems 98, 101, 102 as posed by Novak and Woźniakowski in [33].
We also give an almost complete solution to Open Problem 100 in [33].

This paper is organized as follows. Section 2 contains 5 subsections. In
Subsections 2.1 and 2.2 we introduce the approximation problem in the worst
case and randomized settings. The various notions of algebraic and exponential
tractability are given in Subsection 2.3. Subsection 2.4 is devoted to give
the equivalences of tractability for $\Lambda^{\rm all}$ for the absolute or
normalized error criterion in the worst case and randomized settings. Our main
results, Theorems 2.2, 2.3, 2.5, and 2.6 are stated in Subsection 2.5. In
Section 3, we give the proofs of Theorems 2.2 and 2.3. After that, in Section
4, we establish the equivalence results for the notions of algebraic
tractability. The equivalence results for the notions of exponential
tractability are proved in Section 5.

##  2\. Preliminaries and Main Results

###  2.1. Deterministic worst case setting

For $d\in{N}$, let $F_{d}$ be a separable Hilbert space of $d$-variate
functions defined on $D_{d}\subset{R}^{d}$, $G_{d}=L_{2}(D_{d},\rho_{d}(x)dx)$
be a weighted $L_{2}$ space, where $D_{d}$ is a Borel measurable subset of
$\mathbb{R}^{d}$ with positive Lebesgue measure, $\rho_{d}$ is a probability
density function on $D_{d}$. We consider the multivariate approximation
problem ${\rm APP}=\\{{\rm APP}_{d}\\}_{d\in{N}}$ in the deterministic worst
case setting which is defined via the compact embedding operator

(2.1) ${{\rm APP}}_{d}:F_{d}\to G_{d}\ \ {\rm with}\ \ {\rm APP}_{d}\,f=f.$

We approximate ${\rm APP}_{d}f$ by algorithms $A_{n,d}f$ of the form

(2.2) $A_{n,d}f=\phi_{n,d}(L_{1}(f),L_{2}(f),\dots,L_{n}(f)),$

where $L_{1},L_{2},\dots,L_{n}$ are general linear functionals on $F_{d}$, and
$\phi_{n,d}:\;{R}^{n}\to G_{d}$ is an arbitrary measurable mapping. The worst
case approximation error for the algorithm $A_{n,d}$ of the form (2.2) is
defined as

$e^{\rm wor}(A_{n,d})=\sup_{f\in F_{d},\ \|f\|_{F_{d}}\leq 1}\|{\rm
APP}_{d}\,f-A_{n,d}f\|_{G_{d}}.$

The $n$th minimal worst case error is defined by

$e^{\rm wor}(n,d;\Lambda^{\rm all})=\inf_{A_{n,d}\ {\rm with}\
L_{i}\in\Lambda^{\rm all}}e^{\rm wor}(A_{n,d}),$

where the infimum is taken over all algorithms of the form (2.2).

For $n=0$, we use $A_{0,d}=0$. We obtain the so-called initial error $e^{\rm
wor}(0,d;\Lambda^{\rm all})$, defined by

$e^{\rm wor}(0,d;\Lambda^{\rm all})=\sup_{f\in F_{d},\ \|f\|_{F_{d}}\leq
1}\|{\rm APP}_{d}\,f\|_{G_{d}}.$

From [31, 14] we know that $e^{\rm wor}(n,d;\Lambda^{\rm all})$ depends on the
eigenpairs $\big{\\{}(\lambda_{k,d},e_{k,d})\big{\\}}_{k=1}^{\infty}$ of the
operator

$W_{d}={\rm APP}_{d}^{*}\,{\rm APP}_{d}\colon F_{d}\to F_{d},$

where ${\rm APP}_{d}$ is given by (2.1), ${\rm APP}_{d}^{*}$ is the adjoint
operator of ${\rm APP}_{d}$, and

$\lambda_{1,d}\geq\lambda_{2,d}\geq\dots\lambda_{n,d}\dots\geq 0.$

That is, $\\{e_{j,d}\\}_{j\in{N}}$ is an orthonormal basis in $F_{d}$, and

$W_{d}\,e_{j,d}=\lambda_{j,d}\,e_{j,d}.$

From [31, p. 118] we get that the $n$th minimal worst case error is

$e^{\rm wor}(n,d;\Lambda^{\rm all})=(\lambda_{n+1,d})^{1/2},$

and it is achieved by the optimal algorithm

$S_{n,d}^{*}f=\sum_{k=1}^{n}\langle f,e_{k,d}\rangle_{F_{d}}\,e_{k,d},$

that is,

(2.3) $e^{\rm wor}(n,d;\Lambda^{\rm all})=\sup_{f\in F_{d},\ \|f\|_{F_{d}}\leq
1}\|f-S_{n,d}^{*}f\|_{G_{d}}=(\lambda_{n+1,d})^{1/2}.$

Without loss of generality, we may assume that all the eigenvalues are
positive. We set

$\eta_{k,d}=\lambda_{k,d}^{-1/2}e_{k,d},\ \ k\in{N}.$

We remark that $\\{e_{k,d}\\}$ is an orthonormal basis in $F_{d}$,
$\\{\eta_{k,d}\\}$ is an orthonormal system in $G_{d}$, and for $f\in F_{d}$,

$\langle f,e_{k,d}\rangle_{{F_{d}}}\,e_{k,d}=\langle
f,\eta_{k,d}\rangle_{{G_{d}}}\,\eta_{k,d},$

and

(2.4) $S_{n,d}^{*}f=\sum_{k=1}^{n}\langle
f,\eta_{k,d}\rangle_{G_{d}}\,\eta_{k,d}$

###  2.2. Randomized setting

In the randomized setting, we consider randomized algorithms
$A_{n,d}^{\omega}$ of the form

(2.5)
$A_{n,d}^{\omega}(f)=\phi_{n,d,\omega}(L_{1,\omega}(f),\cdots,L_{n,\omega}(f)),\
L_{j,\omega}\in\Lambda,\ 1\leq j\leq n,$

where $\Lambda\in\\{\Lambda^{\rm all},\Lambda^{\rm std}\\}$,
$\phi_{n,d,\omega}$ and $L_{j,\omega}$ could be randomly selected according to
some probability space $(\Omega,\Sigma,\mathcal{P})$, for any fixed
$\omega\in\Omega$, $A_{n}^{\omega}$ is a deterministic method with cardinality
$n=n(f,\omega)$, the number $n=n(f,\omega)$ may be randomized and adaptively
depend on the input, and the cardinality of $(A_{n,d}^{\omega})$ is then
defined by

${\rm Card}(A_{n,d}^{\omega})=\sup_{f\in F_{d},\ \|f\|_{F_{d}}\leq
1}\mathbb{E}_{\omega}n(f,\omega).$

The randomized approximation error for the algorithm $A_{n,d}^{\omega}$ of the
form (2.5) is defined as

$e^{\rm ran}(A_{n,d}^{\omega})=\sup_{f\in F_{d},\ \|f\|_{F_{d}}\leq
1}\Big{(}\mathbb{E}_{\omega}\big{\|}{\rm
APP}_{d}\,f-A_{n,d}^{\omega}(f)\big{\|}^{2}_{G_{d}}\Big{)}^{1/2}.$

The $n$th minimal randomized error for $\Lambda\in\\{\Lambda^{\rm
all},\Lambda^{\rm std}\\}$ is defined by

$e^{\rm ran}(n,d;\Lambda)=\inf_{A_{n,d}^{\omega}\ {\rm with}\
L_{i,\omega}\in\Lambda}e^{\rm ran}(A_{n,d}^{\omega}),$

where the infimum is taken over all randomized algorithms $A_{n,d}^{\omega}$
of the form (2.5) with ${\rm Card}(A_{n,d}^{\omega})\leq n$.

For $n=0$, we use $A_{0,d}^{\omega}=0$. We have

$e^{\rm ran}(0,d;\Lambda)=e^{\rm wor}(0,d;\Lambda^{\rm
all})=(\lambda_{1,d})^{1/2}.$

There are many papers devoted to studying randomized approximation and
relations of $e^{\rm ran}(n,d;\Lambda)$ and $e^{\rm wor}(n,d;\Lambda)$ for
$\Lambda\in\\{\Lambda^{\rm all},\Lambda^{\rm std}\\}$ (see [1, 7, 8, 10, 17,
22, 23, 27, 29, 30, 31, 33, 40, 42]).

This paper is devoted to discussing the equivalence of tractability for
$\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ in the randomized settings. For
$\Lambda^{\rm std}$ the authors in [42, 33, 17] used simplified randomized
algorithms of the form

(2.6) $A_{n,\vec{t}}(f)=\sum_{j=1}^{n}f(t_{j})g_{j,\vec{t}},$

where $\vec{t}=[t_{1},\dots,t_{n}]$ for some random points $t_{1},\dots,t_{n}$
from $D_{d}$, which are independent, and each $t_{j}$ is distributed according
to some probability. The functions $g_{j,\vec{t}}\in G_{d}$ may depend on the
selected points $t_{j}$’s but are independent of $f$. For any $f$, we view
$A_{n,\cdot}(f)$ as a random process, and $A_{n,\vec{t}}(f)$ as its specific
realization.

We stress that algorithms of the form (2.6) belong to a restricted class of
all randomized algorithms, which are called randomized linear algorithms.
Indeed, we assume that $n$ is not randomized, and for a fixed $\vec{t}$ we
consider only linear algorithms in $f(t_{j})$. In this paper we also consider
algorithms of the form (2.6). However, in [42, 33, 17] $t_{j}$’s are assumed
to be independent, while in this paper we only assume that $\vec{t}$ is
distributed according to some probability, and do not assume that $t_{j}$’s
are independent.

The information complexity can be studied using either the absolute error
criterion (ABS) or the normalized error criterion (NOR). For
$\diamond\in\\{{\rm wor,ran}\\}$, $\star\in\\{{\rm ABS,\,NOR}\\}$, and
$\Lambda\in\\{\Lambda^{\rm all},\Lambda^{\rm std}\\}$, we define the
information complexity $n^{\diamond,\star}(\varepsilon,d;\Lambda)$ as

(2.7) $n^{\diamond,\star}(\varepsilon,d;\Lambda)=\inf\\{n\ \big{|}\
e^{\diamond}(n,d;\Lambda)\leq\varepsilon{\rm CRI}_{d}\\},$

where

${\rm CRI}_{d}=\left\\{\begin{split}&\ \ 1,\;\quad\qquad\text{for
$\star$=ABS,}\\\ &e^{\diamond}(0,d,\Lambda),\text{ for
$\star$=NOR}\end{split}\right.\ \ =\ \ \left\\{\begin{split}&\ 1,\;\qquad\ \ \
\qquad\text{ for $\star$=ABS,}\\\ &\big{(}\lambda_{1,j}\big{)}^{1/2},\
\qquad\text{ for $\star$=NOR.}\end{split}\right.$

We remark that

$e^{\rm wor}(0,d,\Lambda^{\rm all})=e^{\rm ran}(0,d,\Lambda^{\rm all})=e^{\rm
ran}(0,d,\Lambda^{\rm std}).$

Since $\Lambda^{\rm std}\subset\Lambda^{\rm all},$ we get

$e^{\rm ran}(n,d;\Lambda^{\rm all})\leq e^{\rm ran}(n,d;\Lambda^{\rm std}).$

It follows that for $\star\in\\{{\rm ABS,\,NOR}\\}$,

(2.8) $n^{{\rm ran},\star}(\varepsilon,d;\Lambda^{\rm all})\leq n^{{\rm
ran},\star}(\varepsilon,d;\Lambda^{\rm std}).$

###  2.3. Notions of tractability

In this subsection we briefly recall the various tractability notions. Let
${\rm APP}=\\{{\rm APP}_{d}\\}_{d\in{N}}$, $\diamond\in\\{{\rm wor,ran}\\}$,
$\star\in\\{{\rm ABS,\,NOR}\\}$, and $\Lambda\in\\{\Lambda^{\rm
all},\Lambda^{\rm std}\\}$. In the $\diamond$ setting for the class $\Lambda$,
and for error criterion $\star$, we say that ${\rm APP}$ is

$\bullet$ Algebraic strongly polynomially tractable (ALG-SPT) if there exist
$C>0$ and non-negative number $p$ such that

(2.9) $n^{\diamond,\star}(\varepsilon,d;\Lambda)\leq C\varepsilon^{-p},\
\text{for all}\ \varepsilon\in(0,1).$

The exponent ALG-$p^{\diamond,\star}(\Lambda)$ of ALG-SPT is defined as the
infimum of $p$ for which (2.9) holds;

$\bullet$ Algebraic polynomially tractable (ALG-PT) if there exist $C>0$ and
non-negative numbers $p,q$ such that

$n^{\diamond,\star}(\varepsilon,d;\Lambda)\leq Cd^{q}\varepsilon^{-p},\
\text{for all}\ d\in\mathbb{N},\ \varepsilon\in(0,1);$

$\bullet$ Algebraic quasi-polynomially tractable (ALG-QPT) if there exist
$C>0$ and non-negative number $t$ such that

(2.10) $n^{\diamond,\star}(\varepsilon,d;\Lambda)\leq
C\exp(t(1+\ln{d})(1+\ln{\varepsilon^{-1}})),\ \text{for all}\ d\in\mathbb{N},\
\varepsilon\in(0,1).$

The exponent ALG-$t^{\diamond,\star}(\Lambda)$ of ALG-QPT is defined as the
infimum of $t$ for which (2.10) holds;

$\bullet$ Algebraic uniformly weakly tractable (ALG-UWT) if

$\lim_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln
n^{\diamond,\star}(\varepsilon,d;\Lambda)}{\varepsilon^{-\alpha}+d^{\beta}}=0,\
\text{for all}\ \alpha,\beta>0;$

$\bullet$ Algebraic weakly tractable (ALG-WT) if

$\lim_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln
n^{\diamond,\star}(\varepsilon,d;\Lambda)}{\varepsilon^{-1}+d}=0;$

$\bullet$ Algebraic $(s,t)$-weakly tractable (ALG-$(s,t)$-WT) for fixed
$s,t>0$ if

$\lim_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln
n^{\diamond,\star}(\varepsilon,d;\Lambda)}{\varepsilon^{-s}+d^{t}}=0.$

Clearly, ALG-$(1,1)$-WT is the same as ALG-WT. If ${\rm APP}$ is not ALG-WT,
then ${\rm APP}$ is called intractable.

If the $n$th minimal error decays faster than any polynomial and is
exponentially convergent, then we should study tractability with
$\varepsilon^{-1}$ being replaced by $(1+\ln\frac{1}{\varepsilon})$, which is
called exponential tractability. Recently, there have been many papers
studying exponential tractability (see [6, 5, 46, 37, 21, 15, 2, 26]).

In the definitions of ALG-SPT, ALG-PT, ALG-QPT, ALG-UWT, ALG-WT, and
ALG-$(s,t)$-WT, if we replace $\frac{1}{\varepsilon}$ by
$(1+\ln\frac{1}{\varepsilon})$, we get the definitions of _exponential strong
polynomial tractability_ (EXP-SPT), _exponential polynomial tractability_
(EXP-PT), _exponential quasi-polynomial tractability_ (EXP-QPT), _exponential
uniform weak tractability_ (EXP-UWT), _exponential weak tractability_ (EXP-
WT), and _exponential $(s,t)$-weak tractability_ (EXP-$(s,t)$-WT),
respectively. We now give the above notions of exponential tractability in
detail.

Let ${\rm APP}=\\{{\rm APP}_{d}\\}_{d\in{N}}$, $\diamond\in\\{{\rm
wor,ran}\\}$, $\star\in\\{{\rm ABS,\,NOR}\\}$, and $\Lambda\in\\{\Lambda^{\rm
all},\Lambda^{\rm std}\\}$. In the $\diamond$ setting for the class $\Lambda$,
and for error criterion $\star$, we say that ${\rm APP}$ is

$\bullet$ Exponential strongly polynomially tractable (EXP-SPT) if there exist
$C>0$ and non-negative number $p$ such that

(2.11) $n^{\diamond,\star}(\varepsilon,d;\Lambda)\leq
C(\ln\varepsilon^{-1}+1)^{p},\ \text{for all}\ \varepsilon\in(0,1).$

The exponent EXP-$p^{\diamond,\star}(\Lambda)$ of EXP-SPT is defined as the
infimum of $p$ for which (2.11) holds;

$\bullet$ Exponential polynomially tractable (EXP-PT) if there exist $C>0$ and
non-negative numbers $p,q$ such that

$n^{\diamond,\star}(\varepsilon,d;\Lambda)\leq
Cd^{q}(\ln\varepsilon^{-1}+1)^{p},\ \text{for all}\ d\in\mathbb{N},\
\varepsilon\in(0,1);$

$\bullet$ Exponential quasi-polynomially tractable (EXP-QPT) if there exist
$C>0$ and non-negative number $t$ such that

(2.12) $n^{\diamond,\star}(\varepsilon,d;\Lambda)\leq
C\exp(t(1+\ln{d})(1+\ln(\ln\varepsilon^{-1}+1))),\ \text{for all}\
d\in\mathbb{N},\ \varepsilon\in(0,1).$

The exponent EXP-$t^{\diamond,\star}(\Lambda)$ of EXP-QPT is defined as the
infimum of $t$ for which (2.12) holds;

$\bullet$ Exponential uniformly weakly tractable (EXP-UWT) if

$\lim_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln
n^{\diamond,\star}(\varepsilon,d;\Lambda)}{(1+\ln\varepsilon^{-1})^{\alpha}+d^{\beta}}=0,\
\text{for all}\ \alpha,\beta>0;$

$\bullet$ Exponential weakly tractable (EXP-WT) if

$\lim_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln
n^{\diamond,\star}(\varepsilon,d;\Lambda)}{1+\ln\varepsilon^{-1}+d}=0;$

$\bullet$ Exponential $(s,t)$-weakly tractable (EXP-$(s,t)$-WT) for fixed
$s,t>0$ if

$\lim_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln
n^{\diamond,\star}(\varepsilon,d;\Lambda)}{(1+\ln\varepsilon^{-1})^{s}+d^{t}}=0.$

###  2.4. Equivalences of tractability for $\Lambda^{\rm all}$ in the worst
case and randomized settings

In this subsection, we introduce the equivalences of tractability for
$\Lambda^{\rm all}$ in the worst case and randomized settings. It follows from
[30], [31, p. 284] that

$\frac{1}{2}e^{\rm wor}(4n-1,d;\Lambda^{\rm all})\leq e^{\rm
ran}(n,d;\Lambda^{\rm all})\leq e^{\rm wor}(n,d;\Lambda^{\rm all}),$

which means that for $\star\in\\{{\rm ABS,NOR}\\}$ and $n^{\rm
ran,\star}(\varepsilon,d;\Lambda^{\rm all})\geq 1$,

(2.13) $\frac{1}{4}\left(n^{\rm wor,\star}(2\varepsilon,d;\Lambda^{\rm
all})+1\right)\leq n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm all})\leq
n^{\rm wor,\star}(\varepsilon,d;\Lambda^{\rm all}).$

From (2.13) we get the equivalences of tractability for $\Lambda^{\rm all}$ in
the worst case and randomized settings. Indeed, for the absolute or normalized
error criterion, [33, Corollaries 22.1 and 22.2] shows the equivalences of
ALG-SPT, ALG-PT, ALG-QPT, ALG-WT for $\Lambda^{\rm all}$ in the worst case and
randomized settings, and that the exponents of ALG-SPT and ALG-QPT in the
worst case and randomized settings are also same.

Using (2.13) and the same method as in the proof of [33, Corollaries 22.1 and
22.2], for the absolute or normalized error criterion we obtain the
equivalences of ALG-UWT, ALG-$(s,t)$-WT, EXP-SPT, EXP-PT, EXP-QPT, EXP-WT,
EXP-UWT, EXP-$(s,t)$-WT, for $\Lambda^{\rm all}$ in the worst case and
randomized settings, and that the exponents of EXP-SPT and EXP-QPT in the
worst case and randomized settings are also same.

We remark that in showing EXP-$t^{\rm ran,\star}(\Lambda^{\rm all})=$
EXP-$t^{\rm wor,\star}(\Lambda^{\rm all})$, we use the following inequalities
(see [33, p. 43]): for $\delta\in(0,1)$ and $n^{\rm
ran,\star}(\varepsilon,d;\Lambda^{\rm all})\geq 1$,

$\delta^{2}\Big{(}n^{\rm
wor,\star}(\frac{\varepsilon}{1-\delta},d;\Lambda^{\rm all})+1\Big{)}\leq
n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm all})\leq n^{\rm
wor,\star}(\varepsilon,d;\Lambda^{\rm all}),$

instead of (2.13). See the proof of Theorem 5.4.

We summarize these properties in the next corollary.

######  Corollary 2.1.

Consider the approximation problem ${\rm APP}=\\{{\rm APP}_{d}\\}_{d\in{N}}$
for the absolute or normalized error criterion in the randomized and worst
case settings for $\Lambda^{\rm all}$. Then

$\bullet$ $\rm ALG$-$\rm SPT$, $\rm ALG$-$\rm PT$, $\rm ALG$-$\rm QPT$, $\rm
ALG$-$\rm UWT$, $\rm ALG$-$\rm WT$, $\rm ALG$-$(s,t)$-$\rm WT$ in the
randomized setting is equivalent to $\rm ALG$-$\rm SPT$, $\rm ALG$-$\rm PT$,
$\rm ALG$-$\rm QPT$, $\rm ALG$-$\rm UWT$, $\rm ALG$-$\rm WT$, $\rm
ALG$-$(s,t)$-$\rm WT$ in the worst case setting;

$\bullet$ $\rm EXP$-$\rm SPT$, $\rm EXP$-$\rm PT$, $\rm EXP$-$\rm QPT$, $\rm
EXP$-$\rm UWT$, $\rm EXP$-$\rm WT$, $\rm EXP$-$(s,t)$-$\rm WT$ in the
randomized setting is equivalent to $\rm EXP$-$\rm SPT$, $\rm EXP$-$\rm PT$,
$\rm EXP$-$\rm QPT$, $\rm EXP$-$\rm UWT$, $\rm EXP$-$\rm WT$, $\rm
EXP$-$(s,t)$-$\rm WT$, $\rm ALG$-$\rm UWT$, $\rm ALG$-$(s,t)$-$\rm WT$ in the
worst case setting;

$\bullet$ the exponents of SPT and QPT are the same in the two settings, i.e.,
for $\star\in\\{{\rm ABS,NOR}\\}$,

$\displaystyle{\rm ALG}\\!-\\!p^{\rm wor,\star}(\Lambda^{\rm all})$
$\displaystyle={\rm ALG}\\!-\\!p^{\rm ran,\star}(\Lambda^{\rm all}),$
$\displaystyle{\rm ALG}\\!-\\!t^{\rm wor,\star}(\Lambda^{\rm all})$
$\displaystyle={\rm ALG}\\!-\\!t^{\rm ran,\star}(\Lambda^{\rm all}),$
$\displaystyle{\rm EXP}\\!-\\!p^{\rm wor,\star}(\Lambda^{\rm all})$
$\displaystyle={\rm EXP}\\!-\\!p^{\rm ran,\star}(\Lambda^{\rm all}),$
$\displaystyle{\rm EXP}\\!-\\!t^{\rm wor,\star}(\Lambda^{\rm all})$
$\displaystyle={\rm EXP}\\!-\\!t^{\rm ran,\star}(\Lambda^{\rm all}).$

###  2.5. Main results

We shall give main results of this paper in this subsection. The first
important progress about the relation between $e^{\rm ran}(n,d;\Lambda^{\rm
std})$ and $e^{\rm wor}(n,d;\Lambda^{\rm all})$ was obtained by Wasilkowski
and Woźniakowski in [42] by constructing iterated Monte Carlo methods. They
showed that the powers of $e^{\rm ran}(n,d;\Lambda^{\rm std})$ and $e^{\rm
wor}(n,d;\Lambda^{\rm all})$ are same, and obtained the equivalences of ALG-
SPT and ALG-PT for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ for the
normalized error criterion in the randomized setting. Novak and Woźniakowski
in [33] and Krieg in [17] refined the above randomized algorithms and showed
that $e^{\rm ran}(n,d;\Lambda^{\rm std})$ is asymptotically of the same order
as $e^{\rm wor}(n,d;\Lambda^{\rm all})$ given that $e^{\rm
wor}(n,d;\Lambda^{\rm all})$ is regularly decreasing. However, the obtained
relations are heavily dependent of the initial error, and are not sharp if
$e^{\rm wor}(n,d;\Lambda^{\rm all})$ is exponentially convergent.

If nodes ${\rm X}=(x^{1},\dots,x^{n})\in D_{d}^{n}$ are drawn independently
and identically distributed according to a probability measure, then the
samples on the nodes ${\rm X}$ is called the random information (see [12, 13,
18]). Using random information and the least squares method we can obtain the
relation between $e^{\rm ran}(n,d;\Lambda^{\rm std})$ and $e^{\rm
wor}(n,d;\Lambda^{\rm all})$ (see [3, 4]). The authors in [16] used random
information satisfying some condition and the least squares method to obtain
an inequality between $e^{\rm ran}(n,d;\Lambda^{\rm std})$ and $e^{\rm
wor}(n,d;\Lambda^{\rm all})$ (see [16, Theorem 6.1]). They remarked in [16,
Remark 6.3] that using the weighed least squares method can improve the above
inequality.

In this paper we use the method proposed in [16, Remark 6.3], i.e., combining
the proof of [16, Theorem 6.1] with the weighed least squares method used in
[4], to get an improved inequality between $e^{\rm ran}(n,d;\Lambda^{\rm
std})$ and $e^{\rm wor}(n,d;\Lambda^{\rm all})$. See the following theorem.
Compared with the results in [33, 17], our inequality does not depend on the
initial error, and are almost sharp if $e^{\rm wor}(n,d;\Lambda^{\rm all})$ is
exponentially convergent. However, if $e^{\rm wor}(n,d;\Lambda^{\rm all})$ is
regularly decreasing, then by our inequality we can only obtain that $e^{\rm
ran}(n,d;\Lambda^{\rm std})$ is at most asymptotically of the order of $e^{\rm
wor}(m,d;\Lambda^{\rm all})$, where $n$ is at least of order $m\ln m$.

######  Theorem 2.2.

Let $\delta\in(0,1)$, $m,n\in\mathbb{N}$ be such that

$m=\left\lfloor\frac{n}{48(\sqrt{2}\ln(2n)-\ln{\delta})}\right\rfloor.$

Then we have

(2.14) $e^{\rm ran}(n,d;\Lambda^{\rm
std})\leq\Big{(}1+\frac{4m}{n}\Big{)}^{\frac{1}{2}}\frac{1}{\sqrt{1-\delta}}\,e^{\rm
wor}(m,d;\Lambda^{\rm all}),$

where $\lfloor x\rfloor$ denotes the largest integer not exceeding $x$.

Based on Theorem 2.2, we obtain two relations between the information
complexities $n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})$ and $n^{\rm
wor,\star}(\varepsilon,d;\Lambda^{\rm all})$ for $\star\in\\{{\rm
ABS,\,NOR}\\}$.

######  Theorem 2.3.

For $\star\in\\{{\rm ABS,\,NOR}\\}$, we have

(2.15) $\displaystyle n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})\leq
96\sqrt{2}\Big{(}n^{\rm wor,\star}(\frac{\varepsilon}{4},d;\Lambda^{\rm
all})+1\Big{)}\Big{(}\ln\big{(}n^{\rm
wor,\star}(\frac{\varepsilon}{4},d;\Lambda^{\rm
all})+1\big{)}+\ln(192\sqrt{2})\Big{)}.$

Furthermore, for sufficiently small $\delta>0$, we have

(2.16) $\displaystyle n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})\leq
48\Big{(}4\big{(}\ln 48$
$\displaystyle+\ln\ln{\frac{1}{\delta}}+\ln\big{(}n^{\rm
wor,\star}(\frac{\varepsilon}{A_{\delta}},d;\Lambda^{\rm
all})+1\big{)}\big{)}$
$\displaystyle+\ln{\frac{1}{\delta}}\Big{)}\big{(}n^{\rm
wor,\star}(\frac{\varepsilon}{A_{\delta}},d;\Lambda^{\rm all})+1\big{)},$

where
$A_{\delta}:=\Big{(}1+\frac{1}{12\ln{\frac{1}{\delta}}}\Big{)}^{\frac{1}{2}}\frac{1}{\sqrt{1-\delta}}$.

It is easy to see that for any $\omega,\delta>0$,

(2.17) $\sup_{x\geq 1}\frac{96\sqrt{2}(\ln
x+\ln(192\sqrt{2}))}{x^{\omega}}=C_{\omega}<+\infty.$

and

(2.18) $\sup_{x\geq 1}\frac{48(4(\ln 48+\ln\ln{\frac{1}{\delta}}+\ln
x)+\ln{\frac{1}{\delta}})}{x^{\omega}}=C_{\omega,\delta}<+\infty.$

According to (2.15)-(2.18), we have the following corollary which gives two
useful inequalities between the information complexities $n^{\rm
ran,\star}(\varepsilon,d;\Lambda^{\rm std})$ and $n^{\rm
wor,\star}(\varepsilon,d;\Lambda^{\rm all})$ for $\star\in\\{{\rm
ABS,\,NOR}\\}$.

######  Corollary 2.4.

For $\star\in\\{{\rm ABS,\,NOR}\\}$ and $\omega>0$, we have

(2.19) $n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})\leq
C_{\omega}\Big{(}n^{\rm wor,\star}(\frac{\varepsilon}{4},d;\Lambda^{\rm
all})+1\Big{)}^{1+\omega}.$

Similarly, for sufficiently small $\omega,\delta>0$ and $\star\in\\{{\rm
ABS,\,NOR}\\}$, we have

(2.20) $n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})\leq
C_{\omega,\delta}\big{(}n^{\rm
wor,\star}(\frac{\varepsilon}{A_{\delta}},d;\Lambda^{\rm
all})+1\big{)}^{1+\omega},$

where
$A_{\delta}:=\Big{(}1+\frac{1}{12\ln{\frac{1}{\delta}}}\Big{)}^{\frac{1}{2}}\frac{1}{\sqrt{1-\delta}}$.

In the randomized setting, for the normalized error criterion, [33, Theorems
22.19, 22.21, and 22.5] gives the equivalences of ALG-PT (ALG-SPT), ALG-QPT,
ALG-WT for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$, and shows that the
exponents of ALG-SPT and ALG-QPT for $\Lambda^{\rm all}$ and $\Lambda^{\rm
std}$ are same. For the absolute error criterion, [33, Theorems 22.20, 22.22,
and 22.6] gives the equivalences of ALG-PT (ALG-SPT), ALG-QPT, ALG-WT for
$\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ under some conditions on the
initial error $\sqrt{\lambda_{1,d}}$. Novak and Woźniakowski posed Open
problems 98, 101, 102 in [33] which ask whether the above conditions are
necessary.

In this paper we obtain the equivalences of ALG-SPT, ALG-PT, ALG-QPT, ALG-WT
for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ for the absolute error
criterion without any condition, which means the above conditions are
unnecessary. This solves Open problems 98, 101, 102 in [33]. See the following
theorem.

######  Theorem 2.5.

Consider the problem ${\rm APP}=\\{{\rm APP}_{d}\\}_{d\in{N}}$ in the
randomized setting for the absolute error criterion. Then

$\bullet$ $\rm ALG$-$\rm SPT$, $\rm ALG$-$\rm PT$, $\rm ALG$-$\rm QPT$, $\rm
ALG$-$\rm WT$ for $\Lambda^{\rm all}$ is equivalent to $\rm ALG$-$\rm SPT$,
$\rm ALG$-$\rm PT$, $\rm ALG$-$\rm QPT$, $\rm ALG$-$\rm WT$ for $\Lambda^{\rm
std}$;

$\bullet$ The exponents $\rm ALG$-$p^{\rm ran,ABS}(\Lambda)$ of $\rm ALG$-$\rm
SPT$ for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ are same, and the
exponents $\rm ALG$-$t^{\rm ran,ABS}(\Lambda)$ of $\rm ALG$-$\rm QPT$ for
$\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ are also same.

In the randomized setting for the normalized or absolute error criterion, the
equivalences of ALG-UWT and ALG-$(s,t)$-WT, and the various notions of EXP-
tractability for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$, as far as we
know, have not been studied. In this paper, we investigate the problem and
obtain the following theorem which gives the above equivalences without any
condition.

######  Theorem 2.6.

Consider the problem ${\rm APP}=\\{{\rm APP}_{d}\\}_{d\in{N}}$ in the
randomized setting for the absolute or normalized error criterion. Then for
$\star\in\\{{\rm ABS,NOR}\\}$,

$\bullet$ $\rm EXP$-$\rm SPT$, $\rm EXP$-$\rm PT$, $\rm EXP$-$\rm QPT$, $\rm
EXP$-$\rm UWT$, $\rm EXP$-$\rm WT$, $\rm EXP$-$(s,t)$-$\rm WT$, $\rm ALG$-$\rm
UWT$, $\rm ALG$-$(s,t)$-$\rm WT$ for $\Lambda^{\rm all}$ is equivalent to $\rm
EXP$-$\rm SPT$, $\rm EXP$-$\rm PT$, $\rm EXP$-$\rm QPT$, $\rm EXP$-$\rm UWT$,
$\rm EXP$-$\rm WT$, $\rm EXP$-$(s,t)$-$\rm WT$, $\rm ALG$-$\rm UWT$, $\rm
ALG$-$(s,t)$-$\rm WT$ for $\Lambda^{\rm std}$;

$\bullet$ The exponents $\rm EXP$-$p^{\rm ran,\star}(\Lambda)$ of $\rm
EXP$-$\rm SPT$ for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ are same, and
the exponents $\rm EXP$-$t^{\rm ran,\star}(\Lambda)$ of $\rm EXP$-$\rm QPT$
for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ are also same.

Combining Corollary 2.1 with Theorems 2.5 and 2.6 we obtain the following
corollary.

######  Corollary 2.7.

Consider the approximation problem ${\rm APP}=\\{{\rm APP}_{d}\\}_{d\in{N}}$
for the absolute or normalized error criterion in the randomized and worst
case settings. Then

$\bullet$ $\rm ALG$-$\rm SPT$, $\rm ALG$-$\rm PT$, $\rm ALG$-$\rm QPT$, $\rm
ALG$-$\rm UWT$, $\rm ALG$-$\rm WT$, $\rm ALG$-$(s,t)$-$\rm WT$ in the worst
case setting for $\Lambda^{\rm all}$ is equivalent to $\rm ALG$-$\rm SPT$,
$\rm ALG$-$\rm PT$, $\rm ALG$-$\rm QPT$, $\rm ALG$-$\rm UWT$, $\rm ALG$-$\rm
WT$, $\rm ALG$-$(s,t)$-$\rm WT$ in the randomized setting for $\Lambda^{\rm
all}$ or for $\Lambda^{\rm std}$;

$\bullet$ $\rm EXP$-$\rm SPT$, $\rm EXP$-$\rm PT$, $\rm EXP$-$\rm QPT$, $\rm
EXP$-$\rm UWT$, $\rm EXP$-$\rm WT$, $\rm EXP$-$(s,t)$-$\rm WT$ in the worst
case setting for $\Lambda^{\rm all}$ is equivalent to $\rm EXP$-$\rm SPT$,
$\rm EXP$-$\rm PT$, $\rm EXP$-$\rm QPT$, $\rm EXP$-$\rm UWT$, $\rm EXP$-$\rm
WT$, $\rm EXP$-$(s,t)$-$\rm WT$ in the randomized setting for $\Lambda^{\rm
all}$ or for $\Lambda^{\rm std}$;

$\bullet$ the exponents of ${\rm SPT}$ and ${\rm QPT}$ are the same in the
worst case setting for $\Lambda^{\rm all}$ and in the randomized setting for
$\Lambda^{\rm all}$ and $\Lambda^{\rm std}$, i.e., for $\star\in\\{{\rm
ABS,NOR}\\}$,

$\displaystyle{\rm ALG}\\!-\\!p^{\rm wor,\star}(\Lambda^{\rm all})$
$\displaystyle={\rm ALG}\\!-\\!p^{\rm ran,\star}(\Lambda^{\rm all})={\rm
ALG}\\!-\\!p^{\rm ran,\star}(\Lambda^{\rm std}),$ $\displaystyle{\rm
ALG}\\!-\\!t^{\rm wor,\star}(\Lambda^{\rm all})$ $\displaystyle={\rm
ALG}\\!-\\!t^{\rm ran,\star}(\Lambda^{\rm all})={\rm ALG}\\!-\\!t^{\rm
ran,\star}(\Lambda^{\rm std}),$ $\displaystyle{\rm EXP}\\!-\\!p^{\rm
wor,\star}(\Lambda^{\rm all})$ $\displaystyle={\rm EXP}\\!-\\!p^{\rm
ran,\star}(\Lambda^{\rm all})={\rm EXP}\\!-\\!p^{\rm ran,\star}(\Lambda^{\rm
std}),$ $\displaystyle{\rm EXP}\\!-\\!t^{\rm wor,\star}(\Lambda^{\rm all})$
$\displaystyle={\rm EXP}\\!-\\!t^{\rm ran,\star}(\Lambda^{\rm all})={\rm
EXP}\\!-\\!t^{\rm ran,\star}(\Lambda^{\rm std}).$

##  3\. Proofs of Theorems 2.2 and 2.3

Let us keep the notation of Subsection 2.1. For any $m\in\mathbb{N}$, we
define the functions $h_{m,d}(x)$ and $\omega_{m,d}$ on $D_{d}$ by

$h_{m,d}(x):=\frac{1}{m}\sum_{j=1}^{m}|\eta_{j,d}(x)|^{2},\ \ \
\omega_{m,d}(x):=h_{m,d}(x)\,\rho_{d}(x),$

where $\\{\eta_{j,d}\\}_{j=1}^{\infty}$ is an orthonormal system in
$G_{d}=L_{2}(D_{d},\rho_{d}(x)dx)$. Then $\omega_{m,d}$ is a probability
density function on $D_{d}$, i.e., $\int_{D_{d}}\omega_{m,d}(x)\,dx=1$. We
define the corresponding probability measure $\mu_{m,d}$ by

$\mu_{m,d}(A)=\int_{A}\omega_{m,d}(x)\,dx,$

where $A$ is a Borel subset of $D_{d}$. We use the convention that
$\frac{0}{0}:=0$. Then $\\{\tilde{\eta}_{j,d}\\}_{j=1}^{\infty}$ is an
orthonormal system in $L_{2}(D_{d},\mu_{m,d})$, where

$\tilde{\eta}_{j,d}:=\frac{\eta_{j,d}}{\sqrt{h_{m,d}}}.$

For ${\rm X}=(x^{1},\dots,x^{n})\in D_{d}^{n}$, we use the following matrices

(3.1) $\mathaccent 869{L}_{m}=\mathaccent 869{L}_{m}({\rm
X})=\left(\begin{array}[]{cccc}\mathaccent 869{\eta}_{1,d}(x^{1})&\mathaccent
869{\eta}_{2,d}(x^{1})&\cdots&\mathaccent 869{\eta}_{m,d}(x^{1})\\\
\mathaccent 869{\eta}_{1,d}(x^{2})&\mathaccent
869{\eta}_{2,d}(x^{2})&\cdots&\mathaccent 869{\eta}_{m,d}(x^{2})\\\
\vdots&\vdots&&\vdots\\\ \mathaccent 869{\eta}_{1,d}(x^{n})&\mathaccent
869{\eta}_{2,d}(x^{n})&\cdots&\mathaccent 869{\eta}_{m,d}(x^{n})\\\
\end{array}\right)\ \ \ \ \ {\rm and}\ \ \ \ \ \mathaccent
869{H}_{m}=\frac{1}{n}\mathaccent 869{L}_{m}^{*}\mathaccent 869{L}_{m},$

where $A^{*}$ is the conjugate transpose of a matrix $A$. Note that

$\mathaccent 869{N}(m):=\sup\limits_{x\in
D_{d}}\sum\limits_{k=1}^{m}|\mathaccent 869{\eta}_{k,d}(x)|^{2}=m.$

According to [16, Propositions 5.1 and 3.1] we have the following results.

######  Lemma 3.1.

Let $n,m\in\mathbb{N}$. Let $x^{1},\ldots,x^{n}\in D_{d}$ be drawn
independently and identically distributed at random with respect to the
probability measure $\mu_{m,d}$. Then it holds for $0<t<1$ that

$\mathbb{P}(\|\mathaccent
869{H}_{m}-I_{m}\|>t)\leq(2n)^{\sqrt{2}}\exp\left(-\frac{nt^{2}}{12m}\right),$

where $\mathaccent 869{L}_{m},\ \mathaccent 869{H}_{m}$ are given by (3.1),
$I_{m}$ is the identity matrix of order $m$, and $\|L\|$ denotes the spectral
norm (i.e. the largest singular value) of a matrix $L$.

######  Lemma 3.2.

Let $n,m\in\mathbb{N}$, and let $\mathaccent 869{L}_{m},\ \mathaccent
869{H}_{m}$ be given by (3.1). If

$\|\mathaccent 869{H}_{m}-I_{m}\|\leq 1/2,$

then

(3.2) $\|(\mathaccent 869{L}^{*}_{m}\mathaccent
869{L}_{m})^{-1}\|\leq\frac{2}{n}.$

######  Remark 3.3.

From Lemma 3.1 we immediately obtain that the matrix $\mathaccent
869{H}_{m}\in{C}^{m\times m}$ has only eigenvalues larger than $t:=1/2$ and
satisfies

$\|\mathaccent 869{H}_{m}-I_{m}\|\leq 1/2$

with probability at least $1-\delta$ if

$\mathaccent 869{N}(m)=m\leq\frac{n}{48(\sqrt{2}\ln(2n)-\ln{\delta})}.$

Specifically, if

(3.3)
$m=\Big{\lfloor}\frac{n}{48(\sqrt{2}\ln(2n)-\ln{\delta})}\Big{\rfloor}\geq 1,$

then the matrix $\mathaccent 869{H}_{m}$ has only eigenvalues larger than
$1/2$ and satisfies

$\|\mathaccent 869{H}_{m}-I_{m}\|\leq 1/2$

with probability at least $1-\delta$, where $\lfloor x\rfloor$ denotes the
largest integer not exceeding $x$. It follows that

(3.4) $\mathbb{P}\big{(}\|\mathaccent 869{H}_{m}-I_{m}\|\leq 1/2\big{)}\geq
1-\delta$

holds given the condition (3.3).

Now let $m,n\in{N}$ satisfying (3.3), $x^{1},\dots,x^{n}$ be independent and
identically distributed sample points from $D_{d}$ that are distributed
according to the probability measure $\mu_{m,d}$, and $\mathaccent
869{L}_{m},\mathaccent 869{H}_{m}$ be given by (3.1). If the sample points
${\rm X}=(x^{1},\dots,x^{n})$ satisfy $\|\mathaccent 869{H}_{m}-I_{m}\|>1/2$,
then we discard these points and re-sample until the the re-sample points
satisfy $\|\mathaccent 869{H}_{m}-I_{m}\|\leq 1/2$. That is, we consider the
conditional distribution given the event $\|\mathaccent 869{H}_{m}-I_{m}\|\leq
1/2$ and the conditional expectation

${E}(X\,\big{|}\ \|\mathaccent 869{H}_{m}-I_{m}\|\leq
1/2)=\frac{\int_{\|\mathaccent 869{H}_{m}-I_{m}\|\leq
1/2}X(x^{1},\dots,x^{n})\,d\mu_{m,d}(x^{1})\dots
d\mu_{m,d}(x^{n})}{\mathbb{P}\big{(}\|\mathaccent 869{H}_{m}-I_{m}\|\leq
1/2\big{)}}$

of a random variable $X$.

If $\|\mathaccent 869{H}_{m}-I_{m}\|\leq 1/2$ for some ${\rm
X}=(x^{1},\dots,x^{n})\in D_{d}^{n}$, then $\mathaccent 869{L}_{m}=\mathaccent
869{L}_{m}({\rm X})$ has the full rank. The algorithm is a weighted least
squares estimator

(3.5) ${S}^{m}_{\rm X}\,f=\mathop{\arg\min}_{g\in
V_{m}}\frac{|f(x^{i})-g(x^{i})|^{2}}{h_{m,d}(x^{i})},$

where $V_{m}:={\rm span}\\{\eta_{1,d},\dots,\eta_{m,d}\\}$. It follows that
${S}^{m}_{\rm X}\,f=f$ whenever $f\in V_{m}$.

Algorithm Weighted least squares regression.
---
Input: | ${\rm X}=(x^{1},\dots,x^{n})\in D_{d}^{n}$ |  | set of distinct sampling nodes,
| $\tilde{\rm f}=\Big{(}\frac{f(x^{1})}{\sqrt{h_{m,d}(x^{1})}},\dots,\frac{f(x^{n})}{\sqrt{h_{m,d}(x^{n})}}\Big{)}^{T}$ |  | weighted samples of $f$ evaluted
|  |  | at the nodes from ${\rm X}$,
| $m\in{N}$ |  |  $m<n$ such that the matrix
|  |  |  $\mathaccent 869{L}_{m}:=\mathaccent 869{L}_{m}({\rm X})$ from (3.1) has
|  |  | full (column) rank.
Solve the over-determined linear system
$\mathaccent 869{L}_{m}(\mathaccent 869{c}_{1},\cdots,\mathaccent
869{c}_{m})^{T}=\tilde{\rm f}$
via least square, i.e., compute
$(\mathaccent 869{c}_{1},\cdots,\mathaccent 869{c}_{m})^{T}=(\mathaccent
869{L}^{*}_{m}\mathaccent 869{L}_{m})^{-1}\mathaccent 869{L}_{m}^{*}\
\tilde{\rm f}$.
Output: $\mathaccent 869{c}=(\mathaccent 869{c}_{1},\cdots,\mathaccent
869{c}_{m})^{T}\in{C}^{m}$ coefficients of the approximant $S_{\rm
X}^{m}(f):=\sum\limits_{k=1}^{m}\mathaccent 869{c}_{k}\eta_{k,d}$
which is the unique solution of (3.5).

Proof of Theorem 2.2.

We have

$(e^{\rm ran}(n,d;\Lambda^{\rm std}))^{2}\leq{E}(\|f-S_{\rm
X}^{m}(f)\|_{G_{d}}^{2}\ \big{|}\ \|\mathaccent 869{H}_{m}-I_{m}\|\leq 1/2),$

where $m,n\in{N}$ satisfy (3.3). We estimate $\|f-S_{\rm
X}^{m}(f)\|_{G_{d}}^{2}$. We set

$H_{d}=L_{2}(D_{d},\mu_{m,d}).$

We recall that $\\{e_{j,d}\\}_{j=1}^{\infty}$ is an orthonormal basis in
$F_{d}$, $\\{\eta_{j,d}\\}_{j=1}^{\infty}$ is an orthonormal system in
$G_{d}=L_{2}(D_{d},\rho_{d}(x)dx)$, and
$\\{\tilde{\eta}_{j,d}\\}_{j=1}^{\infty}$ is an orthonormal system in
$H_{d}=L_{2}(D_{d},\mu_{m,d})$, where

$\eta_{j,d}=\lambda_{j,d}^{-1/2}e_{j,d},\ \ \
\tilde{\eta}_{j,d}:=\frac{\eta_{j,d}}{\sqrt{h_{m,d}}}.$

For $f\in F_{d}$ with $\|f\|_{F_{d}}\leq 1$, we have

$f=\sum_{k=1}^{\infty}\langle
f,e_{k,d}\rangle_{F_{d}}\,e_{k,d}=\sum_{k=1}^{\infty}\langle
f,\eta_{k,d}\rangle_{G_{d}}\,\eta_{k,d},$

and

$\|f\|_{F_{d}}^{2}=\sum_{k=1}^{\infty}|\langle
f,e_{k,d}\rangle_{F_{d}}|^{2}=\sum_{k=1}^{\infty}\lambda_{k,d}^{-1}|\langle
f,\eta_{k,d}\rangle_{G_{d}}|^{2}.$

We note that $f-S_{m,d}^{*}(f)$ is orthogonal to the space $V_{m}$ with
respect to the inner product $\langle\cdot,\cdot\rangle_{G_{d}}$, and

$S_{m,d}^{*}(f)-S^{m}_{\rm X}(f)=S^{m}_{\rm X}(f-S_{m,d}^{*}(f))\in
V_{m}:={\rm span}\\{\eta_{1,d},\dots,\eta_{m,d}\\},$

where

$S_{m,d}^{*}(f)=\sum\limits_{k=1}^{m}\langle
f,\eta_{k,d}\rangle_{G_{d}}\eta_{k,d}.$

It follows that

$\displaystyle\|f-S_{\rm X}^{m}(f)\|_{G_{d}}^{2}$
$\displaystyle=\|f-S_{m,d}^{*}(f)\|_{G_{d}}^{2}+\|S_{\rm
X}^{m}(f-S_{m,d}^{*}(f))\|_{G_{d}}^{2}$
$\displaystyle=\|g\|_{G_{d}}^{2}+\|S_{\rm X}^{m}(g)\|_{G_{d}}^{2},$

where $g=f-S_{m,d}^{*}(f)$.

We recall that

$S_{\rm X}^{m}(g)=\sum_{k=1}^{m}\mathaccent 869{c}_{k}\eta_{k,d},\,\mathaccent
869{c}=(\mathaccent 869{c}_{1},\dots,\mathaccent 869{c}_{m})^{T}=((\mathaccent
869{L}_{m})^{*}\mathaccent 869{L}_{m})^{-1}(\mathaccent
869{L}_{m})^{*}\mathaccent 869{\rm g},$

where

$\mathaccent 869{\rm g}=(\mathaccent 869{g}(x^{1}),\cdots,\mathaccent
869{g}(x^{n}))^{T},\ \ \ \mathaccent 869{g}=\frac{g}{\sqrt{h_{m,d}}}.$

Since $\\{\eta_{k,d}\\}_{k=1}^{\infty}$ is an orthonormal system in $G_{d}$,
we get

$\displaystyle\|S_{\rm X}^{m}(g)\|_{G_{d}}^{2}=\|\mathaccent 869{c}\|_{2}^{2}$
$\displaystyle=\|((\mathaccent 869{L}_{m})^{*}\mathaccent
869{L}_{m})^{-1}(\mathaccent 869{L}_{m})^{*}\mathaccent 869{\rm g}\|_{2}^{2}$
$\displaystyle\leq\|((\mathaccent 869{L}_{m})^{*}\mathaccent
869{L}_{m})^{-1}\|\cdot\|(\mathaccent 869{L}_{m})^{*}\mathaccent 869{\rm
g}\|_{2}^{2}$ $\displaystyle\leq\frac{4}{n^{2}}\|(\mathaccent
869{L}_{m})^{*}\mathaccent 869{\rm g}\|_{2}^{2},$

where $\|\cdot\|_{2}$ is the Euclidean norm of a vector. We have

$\displaystyle\|(\mathaccent 869{L}_{m})^{*}\mathaccent 869{\rm g}\|_{2}^{2}$
$\displaystyle=\sum_{k=1}^{m}\Big{|}\sum_{j=1}^{n}\overline{\mathaccent
869{\eta}_{k,d}(x^{j})}\cdot\mathaccent 869{g}(x^{j})\Big{|}^{2}$
$\displaystyle=\sum_{k=1}^{m}\sum_{j=1}^{n}\sum_{i=1}^{n}\overline{\mathaccent
869{\eta}_{k,d}(x^{j})}\mathaccent 869{g}(x^{j})\mathaccent
869{\eta}_{k,d}(x^{i})\overline{\mathaccent 869{g}(x^{i})}.$

It follows that

$\displaystyle J$ $\displaystyle=\int_{\|\mathaccent
869{H}_{m}-I_{m}\|\leq\frac{1}{2}}\|(\mathaccent 869{L}_{m})^{*}\mathaccent
869{\rm g}\|_{2}^{2}\,d\mu_{m,d}(x^{1})\ldots d\mu_{m,d}(x^{n})$
$\displaystyle\leq\int_{D_{d}^{n}}\|(\mathaccent 869{L}_{m})^{*}\mathaccent
869{\rm g}\|_{2}^{2}\,d\mu_{m,d}(x^{1})\ldots d\mu_{m,d}(x^{n})$
$\displaystyle\leq\sum_{k=1}^{m}\sum_{i,j=1}^{n}\int_{D_{d}^{n}}\overline{\mathaccent
869{\eta}_{k,d}(x^{j})}\mathaccent 869{g}(x^{j})\mathaccent
869{\eta}_{k,d}(x^{i})\overline{\mathaccent
869{g}(x^{i})}\,d\mu_{m,d}(x^{1})\ldots d\mu_{m,d}(x^{n})$
$\displaystyle=\sum_{k=1}^{m}\sum_{i,j=1}^{n}J_{k,i,j},$

where

$J_{k,i,j}=\int_{D_{d}^{n}}\overline{\mathaccent
869{\eta}_{k,d}(x^{j})}\mathaccent 869{g}(x^{j})\mathaccent
869{\eta}_{k,d}(x^{i})\overline{\mathaccent
869{g}(x^{i})}\,d\mu_{m,d}(x^{1})\ldots d\mu_{m,d}(x^{n}).$

If $i\neq j$ and $1\leq k\leq m$, then

$J_{k,i,j}=|\langle\mathaccent 869{g},\mathaccent
869{\eta}_{k,d}\rangle_{H_{d}}|^{2}=|\langle
g,\eta_{k,d}\rangle_{G_{d}}|^{2}=0;$

If $i=j$, then

$J_{k,i,j}=\|\mathaccent 869{\eta}_{k,d}\cdot\mathaccent
869{g}\|_{H_{d}}^{2}.$

Since $h_{m,d}(x)=\frac{1}{m}\sum\limits_{k=1}^{m}|\eta_{k,d}(x)|^{2}$, we get

$\displaystyle J$
$\displaystyle\leq\sum_{k=1}^{m}\sum_{i=j=1}^{n}J_{k,i,j}=n\sum_{k=1}^{m}\|\mathaccent
869{\eta}_{k,d}\cdot\mathaccent 869{g}\|_{H_{d}}^{2}$
$\displaystyle=n\sum_{k=1}^{m}\int_{D_{d}^{n}}|\mathaccent
869{g}(x)\mathaccent 869{\eta}_{k,d}(x)|^{2}\rho_{d}(x)h_{m,d}(x)\,dx$
$\displaystyle=n\sum_{k=1}^{m}\int_{D_{d}^{n}}\frac{|g(x)\eta_{k,d}(x)|^{2}}{h_{m,d}(x)}\rho_{d}(x)\,dx$
$\displaystyle=n\int_{D_{d}^{n}}m|g(x)|^{2}\rho_{d}(x)\,dx$
$\displaystyle=nm\cdot\|g\|_{G_{d}}^{2}.$

Hence, by (2.3) we have

$\displaystyle\qquad\int_{\|\mathaccent
869{H}_{m}-I_{m}\|\leq\frac{1}{2}}\|f-S_{X}^{m}(f)\|_{G_{d}}^{2}\,d\mu_{m,d}(x^{1})\ldots
d\mu_{m,d}(x^{n})$
$\displaystyle\leq\|g\|_{G_{d}}^{2}+\frac{4}{n^{2}}J\leq(1+\frac{4m}{n})\|g\|_{G_{d}}^{2}\leq(1+\frac{4m}{n})(e^{\rm
wor}(m,d;\Lambda^{\rm all}))^{2}.$

We conclude that

$\mathbb{E}\left(\|f-S_{\rm X}^{m}(f)\|_{G_{d}}^{2}\ \Big{|}\ \|\mathaccent
869{H}_{m}-I_{m}\|\leq 1/2\right)$ $\displaystyle=\frac{\int_{\|\mathaccent
869{H}_{m}-I_{m}\|\leq\frac{1}{2}}\|f-S_{X}^{m}f\|^{2}_{G_{d}}d\mu_{m,d}(x^{1})\ldots
d\mu_{m,d}(x^{n})}{\mathbb{P}(\|\mathaccent
869{H}_{m}-I_{m}\|\leq\frac{1}{2})}$
$\displaystyle\leq\left(1+\frac{4m}{n}\right)\frac{1}{1-\delta}\,(e^{\rm
wor}(m,d;\Lambda^{\rm all}))^{2},$

where in the last inequality we used (3.4). This completes the proof of
Theorem 2.2. $\hfill\Box$

Proof of Theorem 2.3.

Applying Theorem 2.1 with $\delta=\frac{1}{2^{\sqrt{2}}}$, we obtain

(3.6) $e^{\rm ran}(n,d;\Lambda^{\rm
std})\leq\Big{(}1+\frac{4m}{n}\Big{)}^{\frac{1}{2}}\Big{(}\frac{2^{\sqrt{2}}}{2^{\sqrt{2}}-1}\Big{)}^{\frac{1}{2}}e^{\rm
wor}(m,d;\Lambda^{\rm all}),$

where $m,n\in{N}$, and

$m=\Big{\lfloor}\frac{n}{48\sqrt{2}\ln(4n)}\Big{\rfloor}.$

Since $1+\frac{4m}{n}\leq 1+\frac{1}{12\sqrt{2}\ln(4n)}\leq 2$, by (3.6) we
get

(3.7) $e^{\rm ran}(n,d;\Lambda^{\rm std})\leq 4e^{\rm wor}(m,d;\Lambda^{\rm
all}).$

It follows that

$\displaystyle n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})$
$\displaystyle=\min\big{\\{}n\,\big{|}\,e^{\rm ran}(n,d;\Lambda^{\rm
std})\leq\varepsilon{\rm CRI}_{d}\big{\\}}$
$\displaystyle\leq\min\big{\\{}n\,\big{|}\,4e^{\rm wor}(m,d;\Lambda^{\rm
all})\leq\varepsilon{\rm CRI}_{d}\big{\\}}$ (3.8)
$\displaystyle=\min\big{\\{}n\mid e^{\rm wor}(m,d;\Lambda^{\rm
all})\leq\frac{\varepsilon}{4}{\rm CRI}_{d}\big{\\}}.$

We note that

$m=\Big{\lfloor}\frac{n}{48\sqrt{2}\ln(4n)}\Big{\rfloor}\geq\frac{n}{48\sqrt{2}\ln(4n)}-1.$

This inequality is equivalent to

(3.9) $4n\leq 192\sqrt{2}(m+1)\ln(4n).$

Taking logarithm on both sides of (3.9), and using the inequality $\ln
x\leq\frac{1}{2}x$ for $x\geq 1$, we get

$\ln(4n)\leq\ln(m+1)+\ln(192\sqrt{2})+\ln\ln(4n),$

and

$\frac{1}{2}\ln(4n)\leq\ln(4n)-\ln\ln(4n)\leq\ln(m+1)+\ln(192\sqrt{2}).$

It follows from (3.9) that

(3.10) $n\leq 96\sqrt{2}(m+1)(\ln(m+1)+\ln(192\sqrt{2})).$

By (3.8) and (3.10) we obtain

$n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})\leq
96\sqrt{2}\Big{(}n^{\rm wor,\star}(\frac{\varepsilon}{4},d;\Lambda^{\rm
all})+1\Big{)}\Big{(}\ln\big{(}n^{\rm
wor,\star}(\frac{\varepsilon}{4},d;\Lambda^{\rm
all})+1\big{)}+\ln(192\sqrt{2})\Big{)},$

proving (2.15).

For sufficiently small $\delta>0$ and $m,n\in\mathbb{N}$ satisfying

$m=\left\lfloor\frac{n}{48(\sqrt{2}\ln(2n)-\ln{\delta})}\right\rfloor,$

by Theorem 2.2 we have

$\displaystyle e^{\rm ran}(n,d;\Lambda^{\rm std})$
$\displaystyle\leq\Big{(}1+\frac{4m}{n}\Big{)}^{\frac{1}{2}}\frac{1}{\sqrt{1-\delta}}\,e^{\rm
wor}(m,d;\Lambda^{\rm all})$
$\displaystyle\leq\Big{(}1+\frac{1}{12\big{(}\sqrt{2}\ln(2n)+\ln{\frac{1}{\delta}}\big{)}}\Big{)}^{\frac{1}{2}}\frac{1}{\sqrt{1-\delta}}\,e^{\rm
wor}(m,d;\Lambda^{\rm all})$
$\displaystyle\leq\Big{(}1+\frac{1}{12\ln{\frac{1}{\delta}}}\Big{)}^{\frac{1}{2}}\frac{1}{\sqrt{1-\delta}}\,e^{\rm
wor}(m,d;\Lambda^{\rm all})=A_{\delta}\,e^{\rm wor}(m,d;\Lambda^{\rm all}),$

where
$A_{\delta}=\Big{(}1+\frac{1}{12\ln{\frac{1}{\delta}}}\Big{)}^{\frac{1}{2}}\frac{1}{\sqrt{1-\delta}}$.

Using the same method used in the proof of (3.8), we have

$n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})\leq\min\big{\\{}n\mid
e^{\rm wor}(m,d;\Lambda^{\rm all})\leq\frac{\varepsilon}{A_{\delta}}{\rm
CRI}_{d}\big{\\}}.$

We note that

$n\leq 48\big{(}\sqrt{2}\ln(2n)+\ln{\frac{1}{\delta}}\big{)}(m+1).$

Taking logarithm on both sides, and using the inequalities $\ln
x\leq\frac{x}{4}$ for $x\geq 9$ and $a+b\leq ab$ for $a,b\geq 2$, we get

$\displaystyle\ln n$ $\displaystyle\leq\ln
48+\ln\big{(}\sqrt{2}\ln(2n)+\ln{\frac{1}{\delta}}\big{)}+\ln(m+1)$
$\displaystyle\leq\ln
48+\ln(\sqrt{2}\ln(2n))+\ln\ln{\frac{1}{\delta}}+\ln(m+1)$
$\displaystyle\leq\ln
48+\frac{\sqrt{2}}{4}\ln(2n)+\ln\ln{\frac{1}{\delta}}+\ln(m+1).$

Since

$\frac{\sqrt{2}}{4}\ln(2n)\leq\ln n-\frac{\sqrt{2}}{4}\ln(2n)\ \ \text{for}\ \
n\geq 9,$

we get

$\sqrt{2}\ln(2n)\leq 4\big{(}\ln 48+\ln\ln{\frac{1}{\delta}}+\ln(m+1)\big{)}.$

It follows that

$n\leq 48\big{(}4\big{(}\ln
48+\ln\ln{\frac{1}{\delta}}+\ln(m+1)\big{)}+\ln{\frac{1}{\delta}}\big{)}(m+1).$

We conclude that for sufficiently small $\delta>0$,

(3.11) $\displaystyle n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})\leq
48\Big{(}4\big{(}\ln 48$
$\displaystyle+\ln\ln{\frac{1}{\delta}}+\ln\big{(}n^{\rm
wor,\star}(\frac{\varepsilon}{A_{\delta}},d;\Lambda^{\rm
all})+1\big{)}\big{)}$
$\displaystyle+\ln{\frac{1}{\delta}}\Big{)}\big{(}n^{\rm
wor,\star}(\frac{\varepsilon}{A_{\delta}},d;\Lambda^{\rm all})+1\big{)},$

proving (2.16). Theorem 2.3 is proved. $\hfill\Box$

##  4\. Equivalence results of algebraic tractability

First we consider the equivalences of ALG-PT and ALG-SPT for $\Lambda^{\rm
std}$ and $\Lambda^{\rm all}$ in the randomized setting. The equivalent
results for the normalized error criterion can be found in [33, Theorem
22.19]. For the absolute error criterion, [33, Theorem 22.20] shows the
equivalence of ALG-PT under the condition

(4.1) $\lambda_{1,d}\leq C_{\lambda}d^{s_{\lambda}}\ \ {\rm for\ all}\
d\in{N},\ {\rm some}\ C_{\lambda}>0,\ {\rm and\ some}\ s_{\lambda}\geq 0,$

and the equivalence of ALG-SPT under the condition (4.1) with $s_{\lambda}=0$.

We obtain the following equivalent results of ALG-PT and ALG-SPT without any
condition. Hence, the condition (4.1) is unnecessary. This solves Open Problem
101 as posed by Novak and Woźniakowski in [33].

######  Theorem 4.1.

We consider the problem ${\rm APP}=\\{{\rm APP}_{d}\\}_{d\in{N}}$ in the
randomized setting for the absolute error criterion. Then,

$\bullet$ ${\rm ALG}$-${\rm PT}$ for $\Lambda^{\rm all}$ is equivalent to
${\rm ALG}$-${\rm PT}$ for $\Lambda^{\rm std}$ .

$\bullet$ ${\rm ALG}$-${\rm SPT}$ for $\Lambda^{\rm all}$ is equivalent to
${\rm ALG}$-${\rm SPT}$ for $\Lambda^{\rm std}$. In this case, the exponents
of ${\rm ALG}$-${\rm SPT}$ for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ are
the same.

###### Proof.

It follows from (2.8) that ALG-PT (ALG-SPT) for $\Lambda^{\rm std}$ means ALG-
PT (ALG-SPT) for $\Lambda^{\rm all}$ in the randomized setting. Since ALG-PT
(ALG-SPT) for $\Lambda^{\rm all}$ in the worst case setting is equivalent to
${\rm ALG}$-${\rm PT}$ (ALG-SPT) for $\Lambda^{\rm all}$ in the randomized
setting, it suffices to show that ALG-PT (ALG-SPT) for $\Lambda^{\rm all}$ in
the worst case setting means that ALG-PT (ALG-SPT) for $\Lambda^{\rm std}$ in
the randomized setting.

Suppose that ALG-PT holds for $\Lambda^{\rm all}$ in the worst case setting.
Then there exist $C\geq 1$ and non-negative $p,q$ such that

(4.2) $n^{\rm wor,ABS}(\varepsilon,d;\Lambda^{\rm all})\leq
Cd^{q}\varepsilon^{-p},\ \ \text{for all}\ \ d\in\mathbb{N},\
\varepsilon\in(0,1).$

It follows from (2.19) and (4.2) that

$\displaystyle n^{\rm ran,ABS}(\varepsilon,d;\Lambda^{\rm std})$
$\displaystyle\leq
C_{\omega}\Bigl{(}Cd^{q}(\frac{\varepsilon}{4})^{-p}+1\Bigr{)}^{1+\omega}$
$\displaystyle\leq
C_{\omega}(2C\,4^{p})^{1+\omega}d^{q(1+\omega)}\varepsilon^{-p(1+\omega)},$

which means that ALG-PT holds for $\Lambda^{\rm std}$ in the randomized
setting.

If ALG-SPT holds for $\Lambda^{\rm all}$ in the worst case setting, then (4.2)
holds with $q=0$. Using the same method we obtain

$n^{\rm ran,ABS}(\varepsilon,d;\Lambda^{\rm std})\leq
C_{\omega}(2C\,4^{p})^{1+\omega}\varepsilon^{-p(1+\omega)},$

which means that ALG-SPT holds for $\Lambda^{\rm std}$ in the randomized
setting. Furthermore, since $\omega$ can be arbitrary small, by Corollary 2.1
we have

$\displaystyle{\rm ALG\\!-\\!}p^{\rm ran,ABS}(\Lambda^{\rm std})$
$\displaystyle\leq{\rm ALG\\!-\\!}p^{\rm wor,ABS}(\Lambda^{\rm all})$
$\displaystyle={\rm ALG\\!-\\!}p^{\rm ran,ABS}(\Lambda^{\rm all})$
$\displaystyle\leq{\rm ALG\\!-\\!}p^{\rm ran,ABS}(\Lambda^{\rm std}),$

which means that the exponents of ${\rm ALG}$-${\rm SPT}$ for $\Lambda^{\rm
all}$ and $\Lambda^{\rm std}$ are the same. This completes the proof of
Theorem 4.1. ∎

Next we consider the equivalence of ALG-QPT for $\Lambda^{\rm std}$ and
$\Lambda^{\rm all}$ in the randomized setting. The result for the normalized
error criterion can be found in [33, Theorem 22.21]. For the absolute error
criterion, [33, Theorem 22.22] shows the equivalence of ALG-QPT under the
condition

(4.3) $\underset{d\to\infty}{\lim\sup}\ \lambda_{1,d}<\infty.$

We obtain the following equivalent result of ALG-QPT without any condition.
Hence, the condition (4.3) is unnecessary. This solves Open Problem 102 as
posed by Novak and Woźniakowski in [33].

######  Theorem 4.2.

We consider the problem $\rm APP=\\{APP_{d}\\}_{d\in\mathbb{N}}$ in the
randomized setting for the absolute error criterion. Then, ${\rm ALG}$-${\rm
QPT}$ for $\Lambda^{\rm all}$ is equivalent to ${\rm ALG}$-${\rm QPT}$ for
$\Lambda^{\rm std}$. In this case, the exponents of ${\rm ALG}$-${\rm QPT}$
for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ are the same.

###### Proof.

Similar to the proof of Theorem 4.1, it is enough to prove that ALG-QPT for
$\Lambda^{\rm all}$ in the worst case setting implies ALG-QPT for
$\Lambda^{\rm std}$ in the randomized setting.

Suppose that ALG-QPT holds for $\Lambda^{\rm all}$ in the worst case setting.
Then there exist $C\geq 1$ and non-negative $t$ such that

(4.4) $n^{\rm wor,ABS}(\varepsilon,d;\Lambda^{\rm all})\leq
C\exp(t(1+\ln{d})(1+\ln{\varepsilon^{-1}})),\ \text{for all}\ d\in\mathbb{N},\
\varepsilon\in(0,1).$

It follows from (2.19) and (4.4) that for $\omega>0$,

$\displaystyle n^{\rm ran,ABS}(\varepsilon,d;\Lambda^{\rm std})$
$\displaystyle\leq C_{\omega}\Bigl{(}n^{\rm
wor,ABS}(\varepsilon/4,d;\Lambda^{\rm all})+1\Bigr{)}^{1+\omega}$
$\displaystyle\leq
C_{\omega}\Bigl{(}C\exp\big{(}t(1+\ln{d})\big{(}1+\ln\big{(}\frac{\varepsilon}{4}\big{)}^{-1})\big{)}+1\Bigr{)}^{1+\omega}$
$\displaystyle\leq
C_{\omega}(2C)^{1+\omega}\exp\big{(}(1+\omega)t(1+\ln{d})(1+\ln
4+\ln\varepsilon^{-1})\big{)}$ $\displaystyle\leq
C_{\omega}(2C)^{1+\omega}\exp\big{(}t^{*}(1+\ln{d})(1+\ln\varepsilon^{-1})\big{)},$

where $t^{*}=(1+\omega)(1+\ln 4)t$. This implies that ALG-QPT holds for
$\Lambda^{\rm std}$ in the randomized setting.

Next we show that the exponents ALG-$t^{\rm ran,ABS}(\Lambda^{\rm all})$ and
ALG-$t^{\rm ran,ABS}(\Lambda^{\rm std})$ are equal if ALG-QPT holds for
$\Lambda^{\rm all}$ in the worst case setting. We have

$\displaystyle{\rm ALG\\!-\\!}t^{\rm wor,ABS}(\Lambda^{\rm all})={\rm
ALG\\!-\\!}t^{\rm ran,ABS}(\Lambda^{\rm all})\leq{\rm ALG\\!-\\!}t^{\rm
ran,ABS}(\Lambda^{\rm std}).$

It suffices to show that

${\rm ALG\\!-\\!}t^{\rm ran,ABS}(\Lambda^{\rm std})\leq{\rm ALG\\!-\\!}t^{\rm
wor,ABS}(\Lambda^{\rm all}).$

Note that using (2.19) we can only obtain that

${\rm ALG\\!-\\!}t^{\rm ran,ABS}(\Lambda^{\rm std})\leq(1+\ln 4)\cdot{\rm
ALG\\!-\\!}t^{\rm wor,ABS}(\Lambda^{\rm all}).$

Instead we use (2.20). For sufficiently small $\delta>0$ and $\omega>0$, it
follows from (2.20) and (4.4) that

$\displaystyle n^{\rm ran,ABS}(\varepsilon,d;\Lambda^{\rm std})$
$\displaystyle\leq C_{\omega,\delta}\big{(}n^{\rm
wor,ABS}(\frac{\varepsilon}{A_{\delta}},d;\Lambda^{\rm
all})+1\big{)}^{1+\omega}$ $\displaystyle\leq
C_{\omega,\delta}(2C)^{1+\omega}\exp\big{(}(1+\omega)t(1+\ln{d})(1+\ln
A_{\delta}+\ln\varepsilon^{-1})\big{)}$ $\displaystyle\leq
C_{\omega,\delta}(2C)^{1+\omega}\exp\big{(}(1+\omega)t(1+\ln
A_{\delta})(1+\ln{d})(1+\ln\varepsilon^{-1})\big{)},$

where
$A_{\delta}=\big{(}1+\frac{1}{12\ln{\frac{1}{\delta}}}\big{)}^{\frac{1}{2}}\frac{1}{\sqrt{1-\delta}}$.
Taking the infimum over $t$ for which (4.4) holds, and noting that
$\lim\limits_{(\delta,\omega)\to(0,0)}(1+\omega)(1+\ln A_{\delta})=1$, we get
that

$\displaystyle{\rm ALG\\!-\\!}t^{\rm ran,ABS}(\Lambda^{\rm std})\leq{\rm
ALG\\!-\\!}t^{\rm wor,ABS}(\Lambda^{\rm all}).$

This completes the proof of Theorem 4.2. ∎

Now we consider the equivalence of ALG-WT for $\Lambda^{\rm std}$ and
$\Lambda^{\rm all}$ in the randomized setting. The result for the normalized
error criterion can be found in [33, Theorem 22.5]. For the absolute error
criterion, [33, Theorem 22.6] shows the equivalence of ALG-WT under the
condition

(4.5) $\lim_{d\to\infty}\frac{\ln\max(\lambda_{1,d},1)}{d}=0.$

We obtain the following equivalent result of ALG-WT without any condition.
Hence, the condition (4.5) is unnecessary. This solves Open Problem 98 as
posed by Novak and Woźniakowski in [33].

######  Theorem 4.3.

We consider the problem $\rm APP=\\{APP_{d}\\}_{d\in\mathbb{N}}$ in the
randomized setting for the absolute error criterion. Then, ${\rm ALG}$-${\rm
WT}$ for $\Lambda^{\rm all}$ is equivalent to ${\rm ALG}$-${\rm WT}$ for
$\Lambda^{\rm std}$.

###### Proof.

The proof is identical to the proof of Theorem 4.4 with $s=t=1$ for the
absolute error criterion. We omit the details. ∎

Finally, we consider the equivalences of ALG-$(s,t)$-WT and ALG-UWT for
$\Lambda^{\rm std}$ and $\Lambda^{\rm all}$ in the randomized setting. As far
as we know, these equivalences have not been studied yet. We obtain the
following equivalent results of ALG-$(s,t)$-WT and ALG-UWT for the absolute or
normalized error criterion without any condition.

######  Theorem 4.4.

We consider the problem $\rm APP=\\{APP_{d}\\}_{d\in\mathbb{N}}$ in the
randomized setting for the absolute or normalized error criterion. Then for
fixed $s,t>0$, ${\rm ALG}$-$(s,t)$-${\rm WT}$ for $\Lambda^{\rm all}$ is
equivalent to ${\rm ALG}$-$(s,t)$-${\rm WT}$ for $\Lambda^{\rm std}$.

###### Proof.

Again it is enough to prove that ${\rm ALG}$-$(s,t)$-${\rm WT}$ for
$\Lambda^{\rm all}$ in the worst case setting implies ${\rm
ALG}$-$(s,t)$-${\rm WT}$ for $\Lambda^{\rm std}$ in the randomized setting.

Suppose that ${\rm ALG}$-$(s,t)$-${\rm WT}$ holds for $\Lambda^{\rm all}$ in
the worst case setting. Then we have for $\star\in\\{{\rm ABS,\,NOR}\\}$,

(4.6) $\lim_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln n^{\rm
wor,\star}(\varepsilon,d;\Lambda^{\rm all})}{\varepsilon^{-s}+d^{t}}=0.$

It follows from (2.19) that for $\omega>0$,

$\displaystyle\frac{\ln n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm
std})}{\varepsilon^{-s}+d^{t}}$
$\displaystyle\leq\frac{\ln\Big{(}C_{\omega}\big{(}n^{\rm
ran,\star}(\varepsilon/4,d;\Lambda^{\rm
all})+1\big{)}^{1+\omega}\Big{)}}{\varepsilon^{-s}+d^{t}}$
$\displaystyle\leq\frac{\ln(C_{\omega}2^{1+\omega})}{\varepsilon^{-s}+d^{t}}+\frac{4^{s}(1+\omega)\,\ln
n^{\rm wor,\star}(\varepsilon/4,d;\Lambda^{\rm
all})}{(\varepsilon/4)^{-s}+d^{t}}.$

Since $\varepsilon^{-1}+d\rightarrow\infty$ is equivalent to
$\varepsilon^{-s}+d^{t}\to\infty$, by (4.6) we get that

$\lim\limits_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln(C_{\omega}2^{1+\omega})}{\varepsilon^{-s}+d^{t}}=0\
\ \ {\rm and}\ \ \lim_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln n^{\rm
wor,\star}(\varepsilon/4,d;\Lambda^{\rm all})}{(\varepsilon/4)^{-s}+d^{t}}=0.$

We obtain

$\lim\limits_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln n^{\rm
ran,\star}(\varepsilon,d;\Lambda^{\rm std})}{\varepsilon^{-s}+d^{t}}=0,$

which implies that ${\rm ALG}$-$(s,t)$-${\rm WT}$ holds for $\Lambda^{\rm
std}$ in the randomized setting. This completes the proof of Theorem 4.4. ∎

######  Theorem 4.5.

We consider the problem $\rm APP=\\{APP_{d}\\}_{d\in\mathbb{N}}$ in the
randomized setting for the absolute or normalized error criterion. Then, ${\rm
ALG}$-${\rm UWT}$ for $\Lambda^{\rm all}$ is equivalent to ${\rm ALG}$-${\rm
UWT}$ for $\Lambda^{\rm std}$.

###### Proof.

By definition we know that ${\rm APP}$ is ALG-UWT if and only if ${\rm APP}$
is ALG-$(s,t)$-WT for all $s,t>0$. Then Theorem 4.5 follows from Theorem 4.4
immediately. ∎

Proof of Theorem 2.5.

Theorem 2.5 follows from Theorems 4.1-4.3 immediately. $\hfill\Box$

##  5\. Equivalence results of exponential tractability

First we consider exponential convergence. Assume that there exist two
constants $A\geq 1$ and $q\in(0,1)$ such that

(5.1) $e^{\rm wor}(n,d;\Lambda^{\rm all})\leq Aq^{n+1}\sqrt{\lambda_{1,d}}\,.$

Novak and Woźniakowski proved in [33, Theorem 22.18] that there exist two
constants $C_{1}\geq 1$ and $q_{1}\in(q,1)$ independent of $d$ and $n$ such
that

(5.2) $e^{\rm ran}(n,d;\Lambda^{\rm std})\leq
C_{1}A\,q_{1}^{\sqrt{n}}\,\sqrt{\lambda_{1,d}}\,.$

If $A,q$ in (5.1) are independent of $d$, then

$n^{\rm wor,NOR}(\varepsilon,d;\Lambda^{\rm all})\leq
C_{2}(\ln\varepsilon^{-1}+1),$

and

$n^{\rm ran,NOR}(\varepsilon,d;\Lambda^{\rm std})\leq
C_{3}(\ln\varepsilon^{-1}+1)^{2}.$

Novak and Woźniakowski posed Open Problem 100 which states

(1) Verify if the upper bound in (5.2) can be improved.

(2) Find the smallest $p$ for which there holds

$n^{\rm ran,NOR}(\varepsilon,d;\Lambda^{\rm std})\leq
C_{4}(\ln\varepsilon^{-1}+1)^{p}.$

We know that $p\leq 2$, and if (5.1) is sharp then $p\geq 1$.

The following theorem gives a confirmative solution to Open Problem 100 (1).
We improve enormously the upper bound $q_{1}^{\sqrt{n}}$ in (5.2) to
$q_{2}^{\frac{n}{\ln(4n)}}$ in (5.5), where $q_{1},q_{2}\in(q,1)$.

######  Theorem 5.1.

Let $m,n\in{N}$ and

(5.3) $m=\Big{\lfloor}\frac{n}{48\sqrt{2}\ln(4n)}\Big{\rfloor}.$

Then we have

(5.4) $e^{\rm ran}(n,d;\Lambda^{\rm std})\leq 4e^{\rm wor}(m,d;\Lambda^{\rm
all}).$

Specifically, if (5.1) holds, then we have

(5.5) $e^{\rm ran}(n,d;\Lambda^{\rm std})\leq
4Aq_{2}^{\frac{n}{\ln(4n)}}\sqrt{\lambda_{1,d}}\,,$

where $q_{2}=q^{\frac{1}{48\sqrt{2}}}\in(q,1)$.

###### Proof.

Inequality (5.4) is just (3.7), which has been proved. If (5.1) holds, then by
(5.3) and (5.4) we get

$e^{\rm ran}(n,d;\Lambda^{\rm std})\leq
4A\,q^{\big{\lfloor}\frac{n}{48\sqrt{2}\ln(4n)}\big{\rfloor}+1}\sqrt{\lambda_{1,d}}\,\leq
4Aq^{\frac{n}{48\sqrt{2}\ln(4n)}}\sqrt{\lambda_{1,d}}=4Aq_{2}^{\frac{n}{\ln(4n)}}\sqrt{\lambda_{1,d}}.$

This completes the proof of Theorem 5.1. ∎

Now we consider the equivalences of various notions of exponential
tractability for $\Lambda^{\rm std}$ and $\Lambda^{\rm all}$ in the randomized
setting. As far as we know, there is hardly any result for these equivalences.

First we consider the equivalences of EXP-PT and EXP-SPT for $\Lambda^{\rm
std}$ and $\Lambda^{\rm all}$ in the randomized setting. We obtain the
following equivalent results of ALG-PT and ALG-SPT without any condition.

######  Theorem 5.2.

We consider the problem $\rm APP=\\{APP_{d}\\}_{d\in\mathbb{N}}$ in the
randomized setting for the absolute or normalized error criterion. Then,

$\bullet$ ${\rm EXP}$-${\rm PT}$ for $\Lambda^{\rm all}$ is equivalent to
${\rm EXP}$-${\rm PT}$ for $\Lambda^{\rm std}$ .

$\bullet$ ${\rm EXP}$-${\rm SPT}$ for $\Lambda^{\rm all}$ is equivalent to
${\rm EXP}$-${\rm SPT}$ for $\Lambda^{\rm std}$. In this case, the exponents
of ${\rm EXP}$-${\rm SPT}$ for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ are
the same.

###### Proof.

Again, it is enough to prove that EXP-PT for $\Lambda^{\rm all}$ in the worst
case setting implies EXP-PT for $\Lambda^{\rm std}$ in the randomized setting.

Suppose that EXP-PT holds for $\Lambda^{\rm all}$ in the worst case setting.
Then there exist $C\geq 1$ and non-negative $p,q$, for $\star\in\\{{\rm
ABS,\,NOR}\\}$ such that

(5.6) $n^{\rm wor,\star}(\varepsilon,d;\Lambda^{\rm all})\leq
Cd^{q}(\ln\varepsilon^{-1}+1)^{p},\ \text{for all}\ d\in\mathbb{N},\
\varepsilon\in(0,1).$

It follows from (2.19) and (5.6) that

$\displaystyle n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})$
$\displaystyle\leq
C_{\omega}\Bigl{(}Cd^{q}(\ln(\frac{\varepsilon}{4})^{-1}+1)^{p}+1\Bigr{)}^{1+\omega}$
$\displaystyle\leq C_{\omega}(2C)^{1+\omega}(1+\ln
4)^{p(1+\omega)}d^{q(1+\omega)}(\ln\varepsilon^{-1}+1)^{p(1+\omega)},$

which means that EXP-PT holds for $\Lambda^{\rm std}$ in the randomized
setting.

If EXP-SPT holds for $\Lambda^{\rm all}$ in the worst case setting, then (5.6)
holds with $q=0$. We obtain

$n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})\leq
C_{\omega}(2C)^{1+\omega}(1+\ln
4)^{p(1+\omega)}(\ln\varepsilon^{-1}+1)^{p(1+\omega)},$

which means that EXP-SPT holds for $\Lambda^{\rm std}$ in the randomized
setting. Furthermore, in this case we have

$\displaystyle{\rm EXP\\!-\\!}p^{\rm ran,\star}(\Lambda^{\rm std})$
$\displaystyle\leq{\rm EXP\\!-\\!}p^{\rm wor,\star}(\Lambda^{\rm all})$
$\displaystyle={\rm EXP\\!-\\!}p^{\rm ran,\star}(\Lambda^{\rm all})$
$\displaystyle\leq{\rm EXP\\!-\\!}p^{\rm ran,\star}(\Lambda^{\rm std}),$

which means that the exponents of ${\rm EXP}$-${\rm SPT}$ for $\Lambda^{\rm
all}$ and $\Lambda^{\rm std}$ are the same. This completes the proof of
Theorem 5.2. ∎

######  Remark 5.3.

We remark that if (5.1) holds with $A,q$ independent of $d$, then the problem
APP is EXP-SPT for $\Lambda^{\rm all}$ in the randomized setting for the
normalized error criterion, and the exponent ${\rm EXP\\!-\\!}p^{\rm
wor,NOR}(\Lambda^{\rm all})\leq 1$. If (5.1) is sharp, then ${\rm
EXP\\!-\\!}p^{\rm wor,NOR}(\Lambda^{\rm all})=1$.

Open Problem 100 (2) is equivalent to finding the exponent ${\rm
EXP\\!-\\!}p^{\rm ran,NOR}(\Lambda^{\rm std})$ of ${\rm EXP}$-${\rm SPT}$. By
Theorem 5.2 we obtain that if (5.1) holds, then ${\rm EXP\\!-\\!}p^{\rm
ran,NOR}(\Lambda^{\rm std})\leq 1,$ and if (5.1) is sharp, then ${\rm
EXP\\!-\\!}p^{\rm ran,NOR}(\Lambda^{\rm std})=1$.

This solves Open Problem 100 (2) as posed by Novak and Woźniakowski in [33].

Next we consider the equivalence of EXP-QPT for $\Lambda^{\rm std}$ and
$\Lambda^{\rm all}$ in the randomized setting. We obtain the following
equivalent result of EXP-QPT without any condition.

######  Theorem 5.4.

We consider the problem $\rm APP=\\{APP_{d}\\}_{d\in\mathbb{N}}$ in the
randomized setting for the absolute or normalized error criterion. Then, ${\rm
EXP}$-${\rm QPT}$ for $\Lambda^{\rm all}$ is equivalent to ${\rm EXP}$-${\rm
QPT}$ for $\Lambda^{\rm std}$. In this case, the exponents of ${\rm
EXP}$-${\rm QPT}$ for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ are the
same.

###### Proof.

Again, it is enough to prove that EXP-QPT for $\Lambda^{\rm all}$ in the worst
case setting implies EXP-QPT for $\Lambda^{\rm std}$ in the randomized
setting.

Suppose that EXP-QPT holds for $\Lambda^{\rm all}$ in the worst case setting.
Then there exist $C\geq 1$ and non-negative $t$ such that

(5.7) $n^{\rm wor,\star}(\varepsilon,d;\Lambda)\leq
C\exp(t(1+\ln{d})(1+\ln(\ln\varepsilon^{-1}+1))),\ \text{for all}\
d\in\mathbb{N},\ \varepsilon\in(0,1).$

It follows from (2.19) and (5.7) that for $\omega>0$,

$\displaystyle\quad\ n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})$
$\displaystyle\leq C_{\omega}\Bigl{(}n^{\rm
wor,\star}(\varepsilon/4,d;\Lambda^{\rm all})+1\Bigr{)}^{1+\omega}$
$\displaystyle\leq
C_{\omega}\Bigl{(}C\exp\big{(}t(1+\ln{d})\big{(}1+\ln(\ln\varepsilon^{-1}+\ln
4+1))\big{)}+1\Bigr{)}^{1+\omega}$ $\displaystyle\leq
C_{\omega}(2C)^{1+\omega}\exp\big{(}(1+\omega)t(1+\ln{d})(1+\ln(\ln
4+1)+\ln(\ln\varepsilon^{-1}+1))\big{)}$ $\displaystyle\leq
C_{\omega}(2C)^{1+\omega}\exp\big{(}t^{*}(1+\ln{d})(1+\ln(\ln\varepsilon^{-1}+1))\big{)},$

where $t^{*}=(1+\omega)(1+\ln(\ln 4+1))t$, in the third inequality we used the
fact

$\ln(1+a+b)\leq\ln(1+a)+\ln(1+b),\ \ \ a,b\geq 0.$

This implies that EXP-QPT holds for $\Lambda^{\rm std}$ in the randomized
setting.

Next we show that the exponents EXP-$t^{\rm ran,\star}(\Lambda^{\rm all})$ and
EXP-$t^{\rm ran,\star}(\Lambda^{\rm std})$ are equal if EXP-QPT holds for
$\Lambda^{\rm all}$ in the worst case setting. We have

$\displaystyle{\rm EXP\\!-\\!}t^{\rm wor,\star}(\Lambda^{\rm all})={\rm
EXP\\!-\\!}t^{\rm ran,\star}(\Lambda^{\rm all})\leq{\rm EXP\\!-\\!}t^{\rm
ran,\star}(\Lambda^{\rm std}).$

It suffices to show that

${\rm EXP\\!-\\!}t^{\rm ran,\star}(\Lambda^{\rm std})\leq{\rm
EXP\\!-\\!}t^{\rm wor,\star}(\Lambda^{\rm all}).$

Note that using (2.19) we can only obtain that

${\rm EXP\\!-\\!}t^{\rm ran,\star}(\Lambda^{\rm std})\leq(1+\ln 4)\cdot{\rm
EXP\\!-\\!}t^{\rm wor,\star}(\Lambda^{\rm all}).$

Instead we use (2.20). For sufficiently small $\delta>0$ and $\omega>0$, it
follows from (2.20) and (5.7) that

$\displaystyle\quad\ n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm std})$
$\displaystyle\leq C_{\omega,\delta}\big{(}n^{\rm
wor,\star}(\frac{\varepsilon}{A_{\delta}},d;\Lambda^{\rm
all})+1\big{)}^{1+\omega}$ $\displaystyle\leq
C_{\omega,\delta}(2C)^{1+\omega}\exp\big{(}(1+\omega)t(1+\ln{d})(1+\ln(\ln
A_{\delta}+1)+\ln(\ln\varepsilon^{-1}+1))\big{)}$ $\displaystyle\leq
C_{\omega,\delta}(2C)^{1+\omega}\exp\big{(}(1+\omega)t(1+\ln(\ln
A_{\delta}+1))(1+\ln{d})(1+\ln(\ln\varepsilon^{-1}+1))\big{)},$

where
$A_{\delta}=\big{(}1+\frac{1}{12\ln{\frac{1}{\delta}}}\big{)}^{\frac{1}{2}}\frac{1}{\sqrt{1-\delta}}$.
Taking the infimum over $t$ for which (5.7) holds, and noting that
$\lim\limits_{(\delta,\omega)\to(0,0)}(1+\omega)(1+\ln(\ln A_{\delta}+1))=1$,
we get that

$\displaystyle{\rm EXP\\!-\\!}t^{\rm ran,\star}(\Lambda^{\rm std})\leq{\rm
EXP\\!-\\!}t^{\rm wor,\star}(\Lambda^{\rm all}).$

This completes the proof of Theorem 5.4. ∎

Finally, we consider the equivalences of EXP-$(s,t)$-WT (including EXP-WT) and
EXP-UWT for $\Lambda^{\rm std}$ and $\Lambda^{\rm all}$ in the randomized
setting. We obtain the following equivalent results of EXP-$(s,t)$-WT
(including EXP-WT) and EXP-UWT for the absolute or normalized error criterion
without any condition.

######  Theorem 5.5.

We consider the problem $\rm APP=\\{APP_{d}\\}_{d\in\mathbb{N}}$ in the
randomized setting for the absolute or normalized error criterion. Then for
fixed $s,t>0$, ${\rm EXP}$-$(s,t)$-${\rm WT}$ for $\Lambda^{\rm all}$ is
equivalent to ${\rm EXP}$-$(s,t)$-${\rm WT}$ for $\Lambda^{\rm std}$.
Specifically, ${\rm EXP}$-${\rm WT}$ for $\Lambda^{\rm all}$ is equivalent to
${\rm EXP}$-${\rm WT}$ for $\Lambda^{\rm std}$.

###### Proof.

Again, it is enough to prove that ${\rm EXP}$-$(s,t)$-${\rm WT}$ for
$\Lambda^{\rm all}$ in the worst case setting implies ${\rm
EXP}$-$(s,t)$-${\rm WT}$ for $\Lambda^{\rm std}$ in the randomized setting.

Suppose that ${\rm EXP}$-$(s,t)$-${\rm WT}$ holds for $\Lambda^{\rm all}$ in
the worst case setting. Then we have for $\star\in\\{{\rm ABS,\,NOR}\\}$,

(5.8) $\lim_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln n^{\rm
wor,\star}(\varepsilon,d;\Lambda^{\rm
all})}{(1+\ln\varepsilon^{-1})^{s}+d^{t}}=0.$

It follows from (2.19) that for $\omega>0$,

$\displaystyle\quad\ \frac{\ln n^{\rm ran,\star}(\varepsilon,d;\Lambda^{\rm
std})}{(1+\ln\varepsilon^{-1})^{s}+d^{t}}\leq\frac{\ln\Big{(}C_{\omega}\big{(}n^{\rm
ran,\star}(\varepsilon/4,d;\Lambda^{\rm
all})+1\big{)}^{1+\omega}\Big{)}}{(1+\ln\varepsilon^{-1})^{s}+d^{t}}$
$\displaystyle\leq\frac{\ln(C_{\omega}2^{1+\omega})}{(1+\ln\varepsilon^{-1})^{s}+d^{t}}+\frac{(1+\ln
4)^{s}(1+\omega)\,\ln n^{\rm wor,\star}(\varepsilon/4,d;\Lambda^{\rm
all})}{(1+\ln(\varepsilon/4)^{-1})^{s}+d^{t}}.$

Since $\varepsilon^{-1}+d\rightarrow\infty$ is equivalent to
$(1+\ln\varepsilon^{-1})^{s}+d^{t}\to\infty$, by (5.8) we get that

$\lim\limits_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln(C_{\omega}2^{1+\omega})}{(1+\ln\varepsilon^{-1})^{s}+d^{t}}=0\
\ \ {\rm and}\ \ \lim_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln n^{\rm
wor,\star}(\varepsilon/4,d;\Lambda^{\rm
all})}{(1+\ln(\varepsilon/4)^{-1})^{s}+d^{t}}=0.$

We obtain

$\lim\limits_{\varepsilon^{-1}+d\rightarrow\infty}\frac{\ln n^{\rm
ran,\star}(\varepsilon,d;\Lambda^{\rm
std})}{(\ln\varepsilon^{-1})^{s}+d^{t}}=0,$

which implies that ${\rm EXP}$-$(s,t)$-${\rm WT}$ holds for $\Lambda^{\rm
std}$ in the randomized setting.

Specifically, EXP-WT is just ${\rm EXP}$-$(s,t)$-${\rm WT}$ with $s=t=1$.

This completes the proof of Theorem 5.5. ∎

######  Theorem 5.6.

We consider the problem $\rm APP=\\{APP_{d}\\}_{d\in\mathbb{N}}$ in the
randomized setting for the absolute or normalized error criterion. Then, ${\rm
EXP}$-${\rm UWT}$ for $\Lambda^{\rm all}$ is equivalent to ${\rm EXP}$-${\rm
UWT}$ for $\Lambda^{\rm std}$.

###### Proof.

By definition we know that ${\rm APP}$ is EXP-UWT if and only if ${\rm APP}$
is EXP-$(s,t)$-WT for all $s,t>0$. Then Theorem 5.6 follows from Theorem 5.5
immediately. ∎

Proof of Theorem 2.6.

Theorem 2.6 follows from Theorems 4.4, 4.5, 5.2, and 5.4-5.6 immediately.
$\hfill\Box$

Acknowledgment This work was supported by the National Natural Science
Foundation of China (Project no. 11671271).

## References

  * [1] G. Byrenheid, R.J. Kunsch, V.K. Nguyen, Monte Carlo methods for the $L_{\infty}$-approximation on periodic Sobolev spaces with bounded mixed derivative, J. Complexity 46 (2018) 90-102.
  * [2] J. Chen, H. Wang, Average Case tractability of multivariate approximation with Gaussian kernels, J. Approx. Theory 239 (2019) 51-71.
  * [3] A. Cohen, M.A. Davenport, D. Leviatan, On the stability and accuracy of least squares approximations. Found. Comput. Math. 13 (2013) 819-834. (Correction in Found. Comput. Math. 19 (1) (2019) 239.)
  * [4] A. Cohen, G. Migliorati, Optimal weighted least-squares methods, SMAI J. Comput. Math. 3 (2017) 181-203.
  * [5] J. Dick, P. Kritzer, F. Pillichshammer, H. Woźniakowski, Approximation of analytic functions in Korobov spaces, J. Complexity 30 (2014) 2-28.
  * [6] J. Dick, G. Larcher, F. Pillichshammer, H. Woźniakowski, Exponential convergence and tractability of multivariate integration for Korobov spaces, Math. Comp. 80 (2011) 905-930.
  * [7] G. Fang, L. Duan, The complexity of function approximation on Sobolev spaces with bounded mixed derivative by linear Monte Carlo methods, J. Complexity 24 (2008), 398-409.
  * [8] G. Fang, L. Duan, The information-based complexity of approximation problem by adaptive Monte Carlo methods, Sci. China Series A: Math. 51(9) (2008) 1679-1689.
  * [9] M. Gnewuch, H. Woźniakowski, Quasi-polynomial tractability, J. Complexity 27 (2011) 312-330.
  * [10] S. Heinrich, Lower bounds for the complexity of Monte Carlo function approximation, J. Complexity 8(3) (1992) 277-300.
  * [11] F.J. Hickernell, G.W. Wasilkowski, H. Woźniakowski, Tractability of linear multivariate problems in the average case setting, in: A. Keller, S. Heinrich, H. Niederreiter (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2006, Springer, Berlin, 2008, pp. 461-494.
  * [12] A. Hinrichs, D. Krieg, E. Novak, J. Prochno, M. Ullrich, On the power of random information, in: F.J. Hickernell, P. Kritzer (Eds.), Multivariate Algorithms and Information-Based Complexity, De Gruyter, Berlin/Boston, 2020, pp. 43-64.
  * [13] A. Hinrichs, D. Krieg, E. Novak, J. Prochno, M. Ullrich, Random sections of ellipsoids and the power of random information, 2019, arXiv: 1901.06639vl.
  * [14] A. Hinrichs, E. Novak, H. Woźniakowski, Discontinuous information in the worst case and randomized settings, Math. Nachr. 286 (7) (2013) 679-690.
  * [15] C. Irrgeher, P. Kritzer, F. Pillichshammer, H. Woźniakowski, Tractability of multivariate approximation defined over Hilbert spaces with exponential weights, J. Approx. Theory 207 (2016) 301-338.
  * [16] L. Kämmerer, T. Ullrich, T. Volkmer, Worst-case recovery guarantees for least squares approximation using random samples, 2020, arXiv: 1911.10111v2.
  * [17] D. Krieg, Optimal Monte Carlo Methods for $L_{2}-$approximation, Constr. Approx. 49 (2019) 385-403.
  * [18] D. Krieg, M. Sonnleitner, Random points are optimal for the approximation of Sobolev functions, 2020, arXiv: 2009.11275vl.
  * [19] D. Krieg, M. Ullrich. Function values are enough for $L_{2}$-approximation, to appear in Found Comput Math (2021) http://dx.doi. org/10.1007/s10208-020-09481-w, in press.
  * [20] D. Krieg, M. Ullrich. Function values are enough for $L_{2}$-approximation, PART II, 2020, arXiv: 2011.01779vl.
  * [21] P. Kritzer, H. Woźniakowski, Simple characterizations of exponential tractability for linear multivariate problems, J. Complexity 51 (2019) 110-128.
  * [22] R.J. Kunsch, Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods, J. Complexity 48 (2018) 15-35.
  * [23] F. Y. Kuo, G. W. Wasilkowski, H. Woźniakowski, On the power of standard information for $L_{\infty}$ approximation in the randomized setting, BIT Numer. Math. 49 (2009) 543-564.
  * [24] F. Y. Kuo, G. W. Wasilkowski, H. Woźniakowski, On the power of standard information for multivariate approximation in the worst case setting. J. Approx. Theory, 158 (5) (2009): 97-125.
  * [25] M. Lifshits, M. Zani, Approximation of additive random fields based on standard information: Average case and probabilistic settings, J. Complexity 31 (2015) 659-674.
  * [26] Y. Liu, G. Xu, Average case tractability of a multivariate approximation problem, J. Comlexity 43 (2017) 76-102.
  * [27] P. Mathé, Random Approximation of Sobolev Embeddings, J. Complexity 7 (1991) 261-281.
  * [28] N. Nagel, M. Scháfer, T. Ullrich, A new upper bound for sampling numbers, 2020, arXiv: 2010.00327vl.
  * [29] E. Novak, Deterministic and Stochastic Error Bound in Numerical Analysis, in: Lecture Notes in Mathematics, Vol. 1349, Springer, Berlin, 1988.
  * [30] E. Novak, Optimal linear randomized methods for linear operators in Hilbert spaces, J. Complexity 8 (1992) 22-36.
  * [31] E. Novak, H. Woźniakowski, Tractablity of Multivariate Problems, Volume I: Linear Information, EMS, Zürich, 2008.
  * [32] E. Novak, H. Woźniakowski, Tractablity of Multivariate Problems, Volume II: Standard Information for Functionals, EMS, Zürich, 2010.
  * [33] E. Novak, H. Woźniakowski, Tractablity of Multivariate Problems, Volume III: Standard Information for Operators, EMS, Zürich, 2012.
  * [34] E. Novak, H. Woźniakowski, Tractablity of Multivariate Problems for standard ang linear information in the worst case setting: Part I, J.Approx. Theory 207(2016) 177-192.
  * [35] E. Novak, H. Woźniakowski, Tractablity of Multivariate Problems for standard ang linear information in the worst case setting: Part II, Contemporary computational mathematics–a celebration of the 80th birthday of Ian Sloan. Vol. 1, 2, 963-977, Springer, Cham, 2018.
  * [36] A. Papageorgiou, I. Petras, A new criterion for tractability of multivariate problems, J. Complexity 30 (2014) 604-619.
  * [37] A. Papageorgiou, I. Petras, G. Q. Xu, D. Yanqi, EC-$(s,t)-$weak tractability of multivariate linear problems in the average case setting, J. Complexity 55 (2019) 101425, 26 pp.
  * [38] P. Siedlecki, Uniform weak tractability, J. Complexity 29 (6) (2013) 438-453.
  * [39] P. Siedlecki, M. Weimar, Notes on $(s,t)$-weak tractability: a refined classification of problems with (sub)exponential information complexity, J. Approx. Theory 200 (2015) 227-258.
  * [40] J.F. Traub, G.W. Wasilkowski, H. Woźniakowski. Information-Based Complexity. Academic Press, New York, 1988.
  * [41] G.W. Wasilkowski, H. Woźniakowski, On the power of standard information for weighted approximation, Found. Comput. Math. 1 (2001) 417-434.
  * [42] G.W. Wasilkowski, H. Woźniakowski, The power of standard information for multivariate approximation in the randomized setting, Math. Comput. 76 (2007) 965-988.
  * [43] H. Woźniakowski, Tractability and strong tractability of linear multivariate problems, J. Complexity 10 (1994) 96-128.
  * [44] G. Xu, Quasi-polynomial tractability of linear problems in the average case setting, J. Complexity 30 (2014) 54-68.
  * [45] G. Xu, Tractability of linear problems defined over Hilbert spaces, J. Complexity 30 (2014) 735-749.
  * [46] G. Xu, Exponential convergence-tractability of general linear problems in the average case setting, J. Complexity 31 (2015) 617-636.
  * [47] G. Xu, On the power of standard information for $L_{2}$-approximation in the average case setting, J. Complexity 59 (2020) 101482, 20 pp.