Average Case (s, t)-Weak Tractability of L₂-Approximation with Weighted Covariance Kernels

Abstract

We study the multivariate $L_2$-approximation problem ${\mathrm{APP}}_d$ defined over a Banach space in the average case setting. The space is equipped with a zero-mean Gaussian measure with a weighted covariance kernel, which depends on parameter sequences $\mathit{\alpha }={\left\{{\alpha }_j\right\}}_{j\in \mathbb{N}}$ and $\mathit{\beta }={\left\{{\beta }_j\right\}}_{j\in \mathbb{N}}$ with $1<{\alpha }_1\le {\alpha }_2\le \cdots$ and $1\ge {\beta }_1\ge {\beta }_2\ge \cdots >0$. In this paper, two interesting weighted covariance kernels are considered, which model the importance of the covariance kernels. Under the absolute error criterion or the normalized error criterion, we discuss $(s,t)$-weak tractability of the $L_2$-approximation problem $\mathrm{APP}={\left\{{\mathrm{APP}}_d\right\}}_{d\in \mathbb{N}}$ from a Banach space whose zero-mean Gaussian measure has the above two weighted covariance kernels for some positive numbers s and t in the average case setting. Here, $(s,t)$-weak tractability means how the information complexity behaves as a function of $d^t$ and ${\epsilon }^{-s}$ for large dimension d and small threshold $\epsilon$. In particular, for all $s>0$ and $t\in (0,1)$, we find the matching sufficient and necessary condition on the parameter sequences $\mathit{\alpha }={\left\{{\alpha }_j\right\}}_{j\in \mathbb{N}}$ and $\mathit{\beta }={\left\{{\beta }_j\right\}}_{j\in \mathbb{N}}$ to obtain $(s,t)$-weak tractability under the absolute error criterion or the normalized error criterion in the average case setting. We describe $(s,t)$-weak tractability by the matching sufficient and necessary condition, which reflects symmetry.

1. Introduction

This paper is devoted to studying d-variate problems $S_d$ with huge d. This is a hot topic in computational finance (see [1]) and computational chemistry (see [2]). We consider the multivariate problem $S={\{S_d:F_d\to G_d\}}_{d\in \mathbb{N}}$ in the average case setting, where $F_d$ is a Banach space with a zero-mean Gaussian measure ${\mu }_d$, and $G_d$ is a Hilbert space. We approximate $S_d$ by arbitrarily n continuous linear functionals. Let $\epsilon \in (0,1)$ and $d\in \mathbb{N}$. In the average case setting, for the absolute error criterion (ABS) or the normalized error criterion (NOR), information complexity $n^{\mathrm{X}}(\epsilon ,S_d)$ is defined as the minimal number of continuous linear functionals to approximate the multivariate problem $S_d$ with the threshold less than $\epsilon {\mathrm{CRI}}_d^{1/2}$, where $\mathrm{X}\in \{\mathrm{ABS},\mathrm{NOR}\}$ and

$${\mathrm{CRI}}_d:=\left\{\begin{array}{cc}\hfill 1,& \mathrm{for}\mathrm{X}=\mathrm{ABS},\hfill \\ \hfill {\int }_{F_d}{\parallel S_d\left(f\right)\parallel }_{G_d}^2{\mu }_d\left(df\right),& \mathrm{for}\mathrm{X}=\mathrm{NOR}.\hfill \end{array}\right.$$

In 1994, the notion of tractability was first introduced to describe the behavior of the information complexity $n^{\mathrm{X}}(\epsilon ,S_d)$ when d tends to infinity and $\epsilon$ tends to zero (see [3]). If the information complexity $n^{\mathrm{X}}(\epsilon ,S_d)$ behaves as a function of d and ${\epsilon }^{-1}$ for large d and small $\epsilon$, then the problem S is called algebraic tractability. In the average case setting, there are many papers discussing the algebraic tractability, such as strongly polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability and $(s,t)$-weak tractability; see [4,5,6].

Recently, some authors have been interested in algebraic tractability of multivariate approximation problems from Banach spaces equipped with zero-mean Gaussian measures with weighted covariance kernels in the average case setting. Weighted covariance kernels means that the covariance kernels are equipped with some weights; see [4]. The weights can model how important the covariance kernels are. Some special weights were investigated, such as analysis Korobov weights, Korobov weights, Euler weights, Wiener weights and Gaussian weights. In the average case setting, under ABS or NOR [7,8,9] the $L_2$-approximation problem defined over a Banach space whose covariance kernel has an analysis Korobov weight was discussed. The authors of [7] obtained the compete sufficient and necessary conditions for weak tractability, strongly polynomial tractability, polynomial tractability, quasi-polynomial tractability and uniform weak tractability; refs. [8,9] obtained the complete sufficient and necessary conditions for $(s,t)$-weak tractability. For the $L_2$-approximation problem from a Banach space whose covariance kernel has a Korobov weight, the matching sufficient and necessary conditions for weak tractability, strongly polynomial tractability and polynomial tractability under NOR in [10], quasi-polynomial tractability under NOR in [10,11], uniform weak tractability under ABS or NOR in [12], strongly polynomial tractability and polynomial tractability under ABS in [13] and $(s,t)$-weak tractability under ABS or NOR in [9] were studied in the average case setting. In the average case setting, for the $L_2$-approximation problem with a Euler covariance kernel and Wiener covariance kernel under NOR, the sufficient and necessary conditions for weak tractability, strongly polynomial tractability, polynomial tractability and quasi-polynomial tractability in [14], uniform weak tractability in [15] and $(s,t)$-weak tractability in [9,16] were obtained. For the $L_2$-approximation problem with a Gaussian covariance kernel under ABS or NOR, the matching necessary and sufficient conditions for strongly polynomial tractability and polynomial tractability in [17], and quasi-polynomial tractability in [18] were obtained in the average case setting.

It is interesting that different methods are used to solve $(s,t)$-weak tractability for different fixed s and t in the same article. Hence, in this paper, we study the $(s,t)$-weak tractability of multivariate $L_2$-approximation problems defined over Banach spaces with two different weighted covariance kernels in the average case setting. Those two weights come from the ideas of analysis Korobov weights (see [7,8,9]), Korobov weights (see [9,10,11,12,13]) and Gaussian ANOVA weights (see [19,20]). For ABS or NOR, we obtain a complete sufficient and necessary condition on $(s,t)$-weak tractability of the above two $L_2$-approximation problems with all $s>0$ and $t\in (0,1)$. This matching sufficient and necessary condition is equivalent to $(s,t)$-weak tractability, which implies symmetry.

We summarize the contents of this paper as follows. In Section 2, we present a general multivariate approximation problem equipped with a zero-mean Gaussian measure in the average case setting and give some definitions about algebraic tractability. Section 3 discusses $L_2$-approximation problems with weighted covariance kernels in the average case setting. Section 3.1 and Section 3.2 introduce a variant of the Korobov covariance kernel and a variant of the Gaussian ANOVA covariance kernel, respectively. In Section 4, we investigate sufficient and necessary conditions for $(s,t)$-weak tractability of the $L_2$-approximation problems with the above two weighted covariance kernels for all $s>0$ and $t\in (0,1)$ in the average case setting, and then the proof is given. Section 5 provides a summary of this paper.

2. Algebraic Tractability of Multivariate Approximation Problems in the Average Case Setting

First, some notions on the paper: we define $\mathbb{N}=\{1,2,\dots \}$, ${\mathbb{N}}_0=\{0,1,\dots \}$, ${ln}^{+}x=max\{1,lnx\}$, $\lceil a\rceil$ for the smallest integer not less than a.

We recall some concepts of multivariate approximation problems from functions defined over Banach spaces with zero-mean Gaussian measures in the average case setting; see [4].

We consider multivariate approximation problem $S_d:F_d\to G_d$ for each $d\in \mathbb{N}$, where $F_d$ is a Banach space equipped with a zero-mean Gaussian measure ${\mu }_d$, and $G_d$ is a Hilbert space with an inner product ${\langle ·,·\rangle }_{G_d}$. For every $f\in F_d$, we approximate $S_d\left(f\right)$ by an algorithm of the form

$$A_{n,d}\left(f\right)={\mathsf{\Phi }}_{n,d}(L_1\left(f\right),\dots ,L_n\left(f\right)),$$

(1)

where $L_1,L_2,\dots ,L_n$ are continuous linear functionals on $F_d$, and ${\mathsf{\Phi }}_{n,d}:{\mathbb{R}}^n\to G_d$ is an arbitrary mapping. We set $A_{0,d}=0.$

In this paper, we approximate $S_d$ in the average case setting. The average case error $e\left(A_{n,d}\right)$ of the algorithm $A_{n,d}$ is defined as

$$e\left(A_{n,d}\right):={\left(\underset{F_d}{\int }{\parallel S_d\left(f\right)-A_{n,d}\left(f\right)\parallel }_{G_d}{\mu }_d\left(df\right)\right)}^{{\displaystyle \frac{1}{2}}}.$$

For any $n\in {\mathbb{N}}_0$, the nth minimal average case error is defined to be

$$e(n,S_d):=\underset{A_{n,d}}{inf}e\left(A_{n,d}\right),$$

where the infimum is taken over all linear algorithms $A_{n,d}$ of the form (1). Then, for $n=0$, the error

$$e(0,S_d)={\left({\int }_{F_d}{\parallel S_d\left(f\right)\parallel }_{G_d}{\mu }_d\left(df\right)\right)}^{{\displaystyle \frac{1}{2}}}$$

is called the average case initial error. If there exists an algorithm $A_{n,d}^{\square }$ of the form (1) such that

$$e\left(A_{n,d}^{\square }\right)=e(n,S_d),$$

we call $A_{n,d}^{\square }$ the nth optimal algorithm of $S_d$.

Let $\epsilon \in (0,1)$ and $d\in \mathbb{N}$. Under the absolute error criterion (ABS) or the normalized error criterion (NOR), we define the information complexity $n^{\mathrm{X}}(\epsilon ,S_d)$ for $\mathrm{X}\in \{\mathrm{ABS},\mathrm{NOR}\}$ as

$$\begin{array}{cc}\hfill n^{\mathrm{X}}(\epsilon ,S_d)& :=min\left\{n\in {\mathbb{N}}_0:e(n,S_d)\le \epsilon {\mathrm{CRI}}_d^{1/2}\right\},\hfill \end{array}$$

where

$${\mathrm{CRI}}_d:=\left\{\begin{array}{cc}& 1,\mathrm{for}\mathrm{X}=\mathrm{ABS},\\ & e^2(0,S_d),\mathrm{for}\mathrm{X}=\mathrm{NOR}.\end{array}\right.$$

Let $S={\left\{S_d\right\}}_{d\in \mathbb{N}}$. If the information complexity $n^{\mathrm{X}}(\epsilon ,S_d)$ is the function of d and ${\epsilon }^{-1}$ for large d and small $\epsilon$, then the problem S is called algebraic tractability. Recall some definitions of algebraic tractability (see [4,5,6]). For $\mathrm{X}\in \{\mathrm{ABS},\mathrm{NOR}\}$, we say that

• S is strongly polynomially tractable iff there are non-negative numbers C and p such that

  $$n^{\mathrm{X}}(\epsilon ,S_d)\le C{\epsilon }^{-p}\mathrm{for}\mathrm{all}\epsilon \in (0,1),d=1,2,\dots .$$
• S is polynomially tractable iff there are non-negative numbers C, p and q such that

  $$n^{\mathrm{X}}(\epsilon ,S_d)\le C{d}^q{\epsilon }^{-p}\mathrm{for}\mathrm{all}\epsilon \in (0,1),d=1,2,\dots .$$
• S is quasi-polynomially tractable iff there are numbers $C>0$ and $t>0$ such that

  $$n^{\mathrm{X}}(\epsilon ,S_d)\le Cexp\left(t\left(1+lnd\left)\right(1+ln{\epsilon }^{-1}\right)\right)\mathrm{for}\mathrm{all}\epsilon \in (0,1),d=1,2,\dots .$$
• S is uniform weakly tractable iff for all $s,t>0$,

  $$\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}ln{n}^{\mathrm{X}}(\epsilon ,S_d)=0.$$
• S is weakly tractable iff

  $$\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-1}+d}}ln{n}^{\mathrm{X}}(\epsilon ,S_d)=0.$$
• S is $(s,t)$-weakly tractable for fixed $s>0$ and $t>0$ iff

  $$\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}ln{n}^{\mathrm{X}}(\epsilon ,S_d)=0.$$

Obviously, we have the relationships between the above algebraic tractability notions:

$$\begin{array}{cc}\hfill \mathrm{strongly}\mathrm{polynomial}\mathrm{tractability}& \Rightarrow \mathrm{polynomial}\mathrm{tractability}\hfill \\ \hfill & \Rightarrow \text{quasi-polynomial}\mathrm{tractability}\hfill \\ \hfill & \Rightarrow \mathrm{uniform}\mathrm{weak}\mathrm{tractability}\hfill \\ \hfill & \Rightarrow (s,t)\text{-weak}\mathrm{tractability}\mathrm{for}\mathrm{all}s,t>0,\hfill \end{array}$$

and

$$\begin{array}{c}\hfill \mathrm{weak}\mathrm{tractability}\iff (1,1)\text{-weak}\mathrm{tractability}.\end{array}$$

We will discuss the nth minimal average case error $e(n,S_d)$ and the information complexity $n^{\mathrm{X}}(\epsilon ,S_d)$ more explicitly; see ([4], Section 4.3).

Let $C_{{\mu }_d}:{\left(F_d\right)}^{\ast }\to F_d$ be the covariance operator of ${\mu }_d$ (see [4] (pp. 357–362)) and ${\nu }_d={\mu }_d{S}_d^{-1}$ be the induced measure of ${\mu }_d$. Then, the induced measure ${\nu }_d$ is a zero-mean Gaussian measure on the Borel sets of $G_d$ with covariance operator $C_{{\nu }_d}:G_d\to G_d$ given by

$$C_{{\nu }_d}=S_d{C}_{{\mu }_d}{\left(S_d\right)}^{\ast },$$

where ${\left(S_d\right)}^{\ast }$ is the operator dual to $S_d$; see [4] (pp. 357–362). The eigenpairs ${\left\{({\lambda }_{d,i},{\eta }_{d,i})\right\}}_{i\in \mathbb{N}}$ of $C_{{\nu }_d}$ satisfy

$$C_{{\nu }_d}{\eta }_{d,i}={\lambda }_{d,i}{\eta }_{d,i}\mathrm{with}{\lambda }_{d,1}\ge {\lambda }_{d,2}\ge \cdots \ge 0,$$

where ${\langle {\eta }_{d,i},{\eta }_{d,j}\rangle }_{G_d}={\delta }_{i,j},$ and

$${\delta }_{i,j}=\left\{\begin{array}{cc}\hfill 1,& \mathrm{for}i=j,\hfill \\ \hfill 0,& \mathrm{for}i\ne j.\hfill \end{array}\right.$$

Then, for $n\in {\mathbb{N}}_0$, we have that the nth optimal algorithm $A_{n,d}^{\square }$ of $S_d$ satisfies

$$A_{n,d}^{\square }={\displaystyle \sum _{i=1}^n}{\langle S_d\left(f\right),{\eta }_{d,i}\rangle }_{G_d}{\eta }_{d,i},$$

and the nth minimal average case error $e(n,S_d)$ has the form

$$e(n,S_d)=e\left(A_{n,d}^{\square }\right)={\left({\displaystyle \sum _{i=n+1}^{\infty }}{\lambda }_{d,i}\right)}^{{\displaystyle \frac{1}{2}}};$$

see ([4], Section 6.1). Hence, for the absolute error criterion (ABS) or the normalized error criterion (NOR), the information complexity has the form

$$\begin{array}{cc}\hfill n^{\mathrm{X}}(\epsilon ,S_d)& =min\left\{n\in {\mathbb{N}}_0:{\displaystyle \sum _{i=n+1}^{\infty }}{\lambda }_{d,i}\le {\epsilon }^2{\mathrm{CRI}}_d\right\},\hfill \end{array}$$

(2)

where

$${\mathrm{CRI}}_d=\left\{\begin{array}{ccc}& \hfill 1,& \mathrm{for}\mathrm{X}=\mathrm{ABS},\hfill \\ & \hfill {\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i},& \mathrm{for}\mathrm{X}=\mathrm{NOR}.\hfill \end{array}\right.$$

(3)

It is obvious that the algebraic tractability of $S=\left\{S_d\right\}$ depends on the behavior of the eigenvalues ${\left\{{\lambda }_{d,i}\right\}}_{i\in \mathbb{N}}$. Next, we present some relationships between the information complexity $n^{\mathrm{X}}(\epsilon ,S_d)$ and the eigenvalues ${\left\{{\lambda }_{d,i}\right\}}_{i\in \mathbb{N}}$ for ABS and NOR in the average setting.

For any $\tau \in (0,1)$, since

$${\lambda }_{d,j}\le {\left({\displaystyle \frac{1}{j}}\left({\displaystyle \sum _{i=1}^j}{\lambda }_{d,i}^{\tau }\right)\right)}^{{\displaystyle \frac{1}{\tau }}}\le {\left({\displaystyle \frac{1}{j}}\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{\tau }\right)\right)}^{{\displaystyle \frac{1}{\tau }}},$$

we have by (2) that

$$\begin{array}{cc}\hfill {\epsilon }^2{\mathrm{CRI}}_d& <{\displaystyle \sum _{j=n^{\mathrm{X}}(\epsilon ,S_d)}^{\infty }}{\lambda }_{d,j}\le {\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{\tau }\right)}^{{\displaystyle \frac{1}{\tau }}}{\displaystyle \sum _{j=n^{\mathrm{X}}(\epsilon ,S_d)}^{\infty }}{\displaystyle \frac{1}{j^{\frac{1}{\tau }}}}\hfill \\ \hfill & \le {\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{\tau }\right)}^{{\displaystyle \frac{1}{\tau }}}{\displaystyle \underset{n^{\mathrm{X}}(\epsilon ,S_d)-1}{\overset{\infty }{\int }}}{\displaystyle \frac{1}{x^{\frac{1}{\tau }}}}\hfill \\ \hfill & ={\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{\tau }\right)}^{{\displaystyle \frac{1}{\tau }}}{\displaystyle \frac{\tau }{(1-\tau ){(n^{\mathrm{X}}(\epsilon ,S_d)-1)}^{\frac{1-\tau }{\tau }}}}.\hfill \end{array}$$

It means

$$n^{\mathrm{X}}(\epsilon ,S_d)\le ⌈{\left({\displaystyle \frac{\tau }{1-\tau }}{\displaystyle \frac{{\left({\displaystyle {\displaystyle \sum _{i=1}^{\infty }}}{\lambda }_{d,i}^{\tau }\right)}^{\frac{1}{\tau }}}{{\mathrm{CRI}}_d}}\right)}^{{\displaystyle \frac{\tau }{1-\tau }}}{\epsilon }^{{\displaystyle \frac{-2\tau }{1-\tau }}}⌉.$$

(4)

We note that the fact $ln\lceil x\rceil \le \left|ln\left(2x\right)\right|$ holds for $x>0$. Indeed, we have $ln\lceil x\rceil <ln(x+1)\le ln\left(2x\right)$ for $x\ge 1$, and $ln\lceil x\rceil =0$ for $0<x<1$, which deduces $ln\lceil x\rceil \le \left|ln\left(2x\right)\right|$ for $x>0$. Combining the inequality (4) and the above fact, we have

$$\begin{array}{cc}\hfill ln{n}^{\mathrm{X}}(\epsilon ,S_d)& \le ln⌈{\left({\displaystyle \frac{\tau }{1-\tau }}{\displaystyle \frac{{\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{\tau }\right)}^{\frac{1}{\tau }}}{{\mathrm{CRI}}_d}}\right)}^{{\displaystyle \frac{\tau }{1-\tau }}}{\epsilon }^{{\displaystyle \frac{-2\tau }{1-\tau }}}⌉\hfill \\ \hfill & \le \left|ln\left(2{\left({\displaystyle \frac{\tau }{1-\tau }}{\displaystyle \frac{{\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{\tau }\right)}^{\frac{1}{\tau }}}{{\mathrm{CRI}}_d}}\right)}^{{\displaystyle \frac{\tau }{1-\tau }}}{\epsilon }^{{\displaystyle \frac{-2\tau }{1-\tau }}}\right)\right|\hfill \\ \hfill & =\left|{\displaystyle \frac{\tau }{1-\tau }}\left(ln{\displaystyle \frac{\tau }{1-\tau }}+ln\left({\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{\tau }\right)}^{{\displaystyle \frac{1}{\tau }}}/{\mathrm{CRI}}_d\right)+2ln\left({\epsilon }^{-1}\right)\right)+ln2\right|.\hfill \end{array}$$

(5)

3. $L_2$-Approximation with Weighted Covariance Kernels

Let $H_{d,\mathit{\alpha },\mathit{\beta }}\left({[0,1]}^d\right)$ be a Banach space equipped with a zero-mean Gaussian measure ${\mu }_d$ with weighted covariance kernel

$$\begin{array}{c}\hfill K_{W_{d,\mathit{\alpha },\mathit{\beta }}}(\mathit{x},\mathit{y})=\underset{H_{d,\mathit{\alpha },\mathit{\beta }}}{\int }f\left(\mathit{x}\right)f\left(\mathit{y}\right){\mu }_d\left(df\right)=\sum _{\mathit{h}\in {\mathbb{N}}_0^d}{W}_{d,\mathit{\alpha },\mathit{\beta }}\left(\mathit{h}\right)exp(2\pi i\mathit{h}·(\mathit{x}-\mathit{y}))\end{array}$$

(6)

for $\mathit{x},\mathit{y}\in {[0,1]}^d$, where $i=\sqrt{(-1)}$, $\mathit{h}=(h_1,\dots ,h_d)\in {\mathbb{N}}_0^d$, $\mathbf{u}·\mathbf{v}={\displaystyle \sum _{i=1}^d}{u}_i{v}_i$, $\mathbf{u}=(u_1,\dots ,u_d)\in {\mathbb{R}}^d$, $\mathbf{v}=(v_1,\dots ,v_d)\in {\mathbb{R}}^d$ and $W_{d,\mathit{\alpha },\mathit{\beta }}$ is the weight of the covariance kernel $K_{W_{d,\mathit{\alpha },\mathit{\beta }}}$. Here, $\mathit{\alpha }={\left\{{\alpha }_j\right\}}_{j\in \mathbb{N}}$ and $\mathit{\beta }={\left\{{\beta }_j\right\}}_{j\in \mathbb{N}}$ are parameter sequences satisfying

$$1<{\alpha }_1\le {\alpha }_2\le \cdots \mathrm{and}1\ge {\beta }_1\ge {\beta }_2\ge \cdots >0.$$

(7)

Then, the covariance operator of ${\mu }_d$ is given by $C_{{\mu }_d}:{\left(H_{d,\mathit{\alpha },\mathit{\beta }}\left({[0,1]}^d\right)\right)}^{\ast }\to H_{d,\mathit{\alpha },\mathit{\beta }}\left({[0,1]}^d\right)$.

In this paper, we discuss the $L_2$-approximation problem $\mathrm{APP}={\left\{{\mathrm{APP}}_d\right\}}_{d\in \mathbb{N}}$

$$\begin{array}{c}\hfill {\mathrm{APP}}_d:H_{d,\mathit{\alpha },\mathit{\beta }}\left({[0,1]}^d\right)\to L_2\left({[0,1]}^d\right)\mathrm{with}{\mathrm{APP}}_d\left(f\right)=f,\end{array}$$

(8)

for $f\in H_{d,\mathit{\alpha },\mathit{\beta }}\left({[0,1]}^d\right)$. Then, the covariance operator $C_{{\nu }_d}:L_2\left({[0,1]}^d\right)\to L_2\left({[0,1]}^d\right)$ of the induced measure ${\nu }_d={\mu }_d{\mathrm{APP}}_d^{-1}$ has the form

$$\left(C_{{\nu }_d}f\right)\left(\mathit{x}\right)=\underset{{[0,1]}^d}{\int }{K}_{W_{d,\mathit{\alpha },\mathit{\beta }}}(\mathit{x},\mathit{y})f\left(\mathit{y}\right)d\mathit{y}\mathrm{for}\mathit{x},\mathit{y}\in {[0,1]}^d.$$

(9)

By (6) and (9), we have that the eigenvalue sequence ${\left\{{\lambda }_{d,i}\right\}}_{i\in \mathbb{N}}$ with ${\lambda }_{d,1}\ge {\lambda }_{d,2}\ge \cdots \ge 0$ of $C_{{\nu }_d}$ is the sequence ${\left\{W_{d,\mathit{\alpha },\mathit{\beta }}\left(\mathit{h}\right)\right\}}_{\mathit{h}\in {\mathbb{N}}_0^d}$.

We will consider product weights

$$W_{d,\mathit{\alpha },\mathit{\beta }}\left(\mathit{h}\right)={\displaystyle \prod _{j=1}^d}{W}_{{\alpha }_j,{\beta }_j}\left(h_j\right)\mathrm{for}\mathit{h}=(h_1,\dots ,h_d)\in {\mathbb{N}}_0^d.$$

Then, for any $\tau >0$, we have

$${\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{\tau }=\sum _{\mathit{h}\in {\mathbb{N}}_0^d}{W}_{d,\mathit{\alpha },\mathit{\beta }}^{\tau }\left(\mathit{h}\right)=\sum _{\mathit{h}\in {\mathbb{N}}_0^d}{\displaystyle \prod _{j=1}^d}{W}_{{\alpha }_j,{\beta }_j}^{\tau }\left(h_j\right)={\displaystyle \prod _{j=1}^d}{\displaystyle \sum _{h=0}^{\infty }}{W}_{{\alpha }_j,{\beta }_j}^{\tau }\left(h\right).$$

(10)

We note that the weighted covariance kernels are restricted by their weights. So it is worth investigating the weights. There are many papers discussing the Korobov weights (see [9,10,11,12,13]), the analysis Korobov weights (see [7,8,9]) and the Gaussian ANOVA weights (see [19,20]). According to the ideas of the above weights, we introduce two weights, which have faster decay rates than the Korobov weights and the Gaussian ANOVA weights, respectively.

3.1. A Variant of the Korobov Covariance Kernel

In this subsection, we introduce a weighted covariance kernel $K_{W_{d,\mathit{\alpha },\mathit{\beta }}}$ with the weight $W_{d,\mathit{\alpha },\mathit{\beta }}$ given by a variant of the Korobov weight ${\rho }_{d,\mathit{\alpha },\mathit{\beta }}$, where $\mathit{\alpha }={\left\{{\alpha }_j\right\}}_{j\in \mathbb{N}}$ and $\mathit{\beta }={\left\{{\beta }_j\right\}}_{j\in \mathbb{N}}$ satisfy (7). The weight ${\rho }_{d,\mathit{\alpha },\mathit{\beta }}$ is given as the product form,

$${\rho }_{d,\mathit{\alpha },\mathit{\beta }}\left(\mathit{k}\right):={\displaystyle \prod _{j=1}^d}{\rho }_{{\alpha }_j,{\beta }_j}\left(k_j\right),\mathit{k}=(k_1,\dots ,k_d)\in {\mathbb{N}}_0^d,$$

where ${\rho }_{{\alpha }_j,{\beta }_j}\left(k_j\right)$ are univariate weights,

$${\rho }_{\alpha ,\beta }\left(k\right):=\left\{\begin{array}{ccc}& \hfill 1,& \mathrm{for}k=0,\hfill \\ & \hfill \beta A^{k^{\lceil \alpha \rceil }},& \mathrm{for}k\ge 1,\hfill \end{array}\right.$$

for fixed $A\in (0,1)$, $\alpha \in (1,+\infty )$ and $\beta \in (0,1]$. The idea of the weight ${\rho }_{d,\mathit{\alpha },\mathit{\beta }}$ comes from the Korobov weight (see [9,10,11,12,13]) and the analysis Korobov weight (see [7,8,9]).

The references [9,10,11,12,13] consider the $L_2$-approximation problem $\mathrm{APP}={\left\{{\mathrm{APP}}_d\right\}}_{d\in \mathbb{N}}$, satisfying (8) from the Banach space $H_{d,{\mathit{\alpha }}^{\left(1\right)},{\mathit{\beta }}^{\left(1\right)}}\left({[0,1]}^d\right)$, equipped with a zero-mean Gaussian measure whose weighted covariance kernel has the Kovobov weight $r_{d,{\mathit{\alpha }}^{\left(1\right)},{\mathit{\beta }}^{\left(1\right)}}$ of the form

$$r_{d,{\mathit{\alpha }}^{\left(1\right)},{\mathit{\beta }}^{\left(1\right)}}\left(\mathit{k}\right):={\displaystyle \prod _{j=1}^d}{r}_{{\alpha }_j^{\left(1\right)},{\beta }_j^{\left(1\right)}}\left(k_j\right),\mathit{k}=(k_1,\dots ,k_d)\in {\mathbb{N}}_0^d,$$

with

$$r_{{\alpha }^{\left(1\right)},{\beta }^{\left(1\right)}}\left(k\right):=\left\{\begin{array}{cc}& 1,\mathrm{for}k=0,\\ & {\displaystyle \frac{{\beta }^{\left(1\right)}}{k^{{\alpha }^{\left(1\right)}}}},\mathrm{for}k\ge 1,\end{array}\right.$$

for ${\alpha }^{\left(1\right)}\in (1,+\infty )$ and ${\beta }^{\left(1\right)}\in (0,1]$, where the parameter sequences ${\mathit{\alpha }}^{\left(1\right)}={\left\{{\alpha }_j^{\left(1\right)}\right\}}_{j\in \mathbb{N}}$ and ${\mathit{\beta }}^{\left(1\right)}={\left\{{\beta }_j^{\left(1\right)}\right\}}_{j\in \mathbb{N}}$ satisfy

$$1<{\alpha }_1^{\left(1\right)}\le {\alpha }_2^{\left(1\right)}\le \cdots \mathrm{and}1\ge {\beta }_1^{\left(1\right)}\ge {\beta }_2^{\left(1\right)}\ge \cdots >0.$$

Using ABS or NOR, the references [9,10,11,12,13] have solved the algebraic tractability of the above problem $\mathrm{APP}$ and obtained the following results:

• For ABS or NOR, strongly polynomial tractability holds iff

  $$\underset{k\to \infty }{lim\; inf}{\displaystyle \frac{ln\frac{1}{{\beta }_k^{\left(1\right)}}}{lnk}}>1.$$
• For NOR, quasi-polynomial tractability holds iff

  $$\underset{d\in \mathbb{N}}{sup}{\displaystyle \frac{1}{{ln}^{+}d}}{\displaystyle \sum _{k=1}^d}{\beta }_k^{\left(1\right)}{ln}^{+}{\displaystyle \frac{1}{{\beta }_k^{\left(1\right)}}}<\infty .$$
• For ABS or NOR, weak tractability holds iff

  $$\underset{k\to \infty }{lim}{\beta }_k^{\left(1\right)}=0.$$
• For ABS or NOR, uniform weak tractability holds iff

  $$\underset{k\to \infty }{lim}{\beta }_k^{\left(1\right)}{k}^p=0\mathrm{for}\mathrm{all}p\in (0,1).$$
• For ABS or NOR, $(s,t)$-weak tractability with $s>0$ and $t>1$ always holds.
• For ABS or NOR, $(s,t)$-weak tractability with $s>0$ and $t\in (0,1)$ holds iff

  $$\underset{k\to \infty }{lim}{k}^{1-t}{\beta }_k^{\left(1\right)}{ln}^{+}{\displaystyle \frac{1}{{\beta }_k^{\left(1\right)}}}=0.$$

Another covariance kernel is the analysis Korobov covariance kernel, which is famous for its fast exponentially decaying weight. The analysis Korobov weight is given as

$${\omega }_{d,{\mathit{\alpha }}^{\left(2\right)},{\mathit{\beta }}^{\left(2\right)}}\left(\mathit{k}\right):={\displaystyle \prod _{j=1}^d}{\omega }_{{\alpha }_j^{\left(2\right)},{\beta }_j^{\left(2\right)}}\left(k_j\right),\mathit{k}=(k_1,\dots ,k_d)\in {\mathbb{N}}_0^d,$$

with

$${\omega }_{{\alpha }^{\left(2\right)},{\beta }^{\left(2\right)}}\left(k\right):=\left\{\begin{array}{ccc}& \hfill 1,& \mathrm{for}k=0,\hfill \\ & \hfill {\omega }^{{\beta }^{\left(2\right)}{k}^{{\alpha }^{\left(2\right)}}},& \mathrm{for}k\ge 1,\hfill \end{array}\right.$$

for fixed $\omega \in (0,1)$, ${\alpha }^{\left(2\right)}>0$ and ${\beta }^{\left(2\right)}>0$, where the parameter sequences ${\mathit{\alpha }}^{\left(2\right)}={\left\{{\alpha }_j^{\left(2\right)}\right\}}_{j\in \mathbb{N}}$ and ${\mathit{\beta }}^{\left(2\right)}={\left\{{\beta }_j^{\left(2\right)}\right\}}_{j\in \mathbb{N}}$ satisfy

$$\underset{k\in \mathbb{N}}{inf}{\alpha }_k^{\left(2\right)}>0\mathrm{and}0<{\beta }_1^{\left(2\right)}\le {\beta }_2^{\left(2\right)}\le \cdots .$$

In the average case setting, the references [7,8,9] investigate the algebraic tractability of the $L_2$-approximation problem $\mathrm{APP}={\left\{{\mathrm{APP}}_d\right\}}_{d\in \mathbb{N}}$, satisfying (8) from the Banach space $H_{d,{\mathit{\alpha }}^{\left(2\right)},{\mathit{\beta }}^{\left(2\right)}}\left({[0,1]}^d\right)$ equipped with a zero-mean Gaussian measure, whose weighted covariance kernel has the analysis Korobov weight ${\omega }_{d,{\mathit{\alpha }}^{\left(2\right)},{\mathit{\beta }}^{\left(2\right)}}$. They obtained that (see [7,8,9]):

• For ABS or NOR, strongly polynomial tractability holds iff

  $$\underset{k\to \infty }{lim\; inf}{\displaystyle \frac{{\beta }_k^{\left(2\right)}}{lnk}}>{\displaystyle \frac{1}{ln{\omega }^{-1}}}.$$
• For ABS or NOR, weak tractability holds iff

  $$\underset{k\to \infty }{lim}{\beta }_k^{\left(2\right)}=\infty .$$
• For NOR, quasi-polynomial tractability holds iff

  $$\underset{d\in \mathbb{N}}{sup}{\displaystyle \frac{1}{{ln}^{+}d}}{\displaystyle \sum _{k=1}^d}{\beta }_k^{\left(2\right)}{\omega }^{{\beta }_k^{\left(2\right)}}<\infty .$$
• For ABS or NOR, uniform weak tractability holds iff

  $$\underset{k\to \infty }{lim}{\omega }^{{\beta }_k^{\left(2\right)}}{k}^p=0\mathrm{for}\mathrm{all}p\in (0,1).$$
• For ABS or NOR, $(s,t)$-weak tractability with $s>0$ and $t>1$ always holds.
• For ABS or NOR, $(s,t)$-weak tractability with $s>0$ and $t\in (0,1)$ holds iff

  $$\underset{k\to \infty }{lim}{k}^{1-t}{\beta }_k^{\left(2\right)}{\omega }^{{\beta }_k^{\left(2\right)}}=0.$$

Remark 1.

We note that the variant of the Korobov weight ${\rho }_{d,\mathit{\alpha },\mathit{\beta }}$ descends faster than the Korobov weight $r_{d,{\mathit{\alpha }}^{\left(1\right)},{\mathit{\beta }}^{\left(1\right)}}$ but slower than the analysis Korobov weight ${\omega }_{d,{\mathit{\alpha }}^{\left(2\right)},{\mathit{\beta }}^{\left(2\right)}}$.

3.2. A Variant of the Gaussian ANOVA Covariance Kernel

In this subsection, we present a weighted covariance kernel $K_{W_{d,\mathit{\alpha },\mathit{\beta }}}$ with the weight $W_{d,\mathit{\alpha },\mathit{\beta }}$ given as a variant of the Gaussian ANOVA weight ${\sigma }_{d,\mathit{\alpha },\mathit{\beta }}$, where $\mathit{\alpha }={\left\{{\alpha }_j\right\}}_{j\in \mathbb{N}}$ and $\mathit{\beta }={\left\{{\beta }_j\right\}}_{j\in \mathbb{N}}$ satisfy (7). The weight ${\sigma }_{d,\mathit{\alpha },\mathit{\beta }}$ is of product form and determined by

$${\sigma }_{d,\mathit{\alpha },\mathit{\beta }}\left(\mathit{k}\right):={\displaystyle \prod _{j=1}^d}{\sigma }_{{\alpha }_j,{\beta }_j}\left(k_j\right),$$

where ${\sigma }_{{\alpha }_j,{\beta }_j}\left(k_j\right)$ are univariate weights,

$${\sigma }_{\alpha ,\beta }\left(k\right):=\left\{\begin{array}{ccc}& \hfill 1,& \mathrm{for}k=0,\hfill \\ & \hfill \beta A^{k!},& \mathrm{for}1\le k<\lceil \alpha \rceil ,\hfill \\ & \hfill \beta A^{k!/(k-\lceil \alpha \rceil )!},& \mathrm{for}k\ge \lceil \alpha \rceil ,\hfill \end{array}\right.$$

for fixed $A\in (0,1)$, $\alpha \in (1,+\infty )$ and $\beta \in (0,1]$.

The weight ${\sigma }_{d,\mathit{\alpha },\mathit{\beta }}$ is similar but different with the Gaussian ANOVA weight ${\psi }_{d,{\mathit{\alpha }}^{\left(3\right)},{\mathit{\beta }}^{\left(3\right)}}$, given by

$${\psi }_{d,{\mathit{\alpha }}^{\left(3\right)},{\mathit{\beta }}^{\left(3\right)}}\left(\mathit{k}\right):={\displaystyle \prod _{j=1}^d}{\psi }_{{\alpha }_j^{\left(3\right)},{\beta }_j^{\left(3\right)}}\left(k_j\right)$$

with

$${\psi }_{{\alpha }^{\left(3\right)},{\beta }^{\left(3\right)}}\left(k\right):=\left\{\begin{array}{cc}\hfill 1,& \mathrm{for}k=0,\hfill \\ \hfill {\displaystyle \frac{{\beta }^{\left(3\right)}}{k!}},& \mathrm{for}1\le k<\lceil {\alpha }^{\left(3\right)}\rceil ,\hfill \\ \hfill {\displaystyle \frac{{\beta }^{\left(3\right)}(k-\lceil {\alpha }^{\left(3\right)}\rceil )!}{k!}},& \mathrm{for}k\ge \lceil {\alpha }^{\left(3\right)}\rceil ,\hfill \end{array}\right.$$

for ${\alpha }^{\left(3\right)}\in (1,+\infty )$ and ${\beta }^{\left(3\right)}\in (0,1]$, where ${\mathit{\alpha }}^{\left(3\right)}={\left\{{\alpha }_j^{\left(3\right)}\right\}}_{j\in \mathbb{N}}$ and ${\mathit{\beta }}^{\left(3\right)}={\left\{{\beta }_j^{\left(3\right)}\right\}}_{j\in \mathbb{N}}$ satisfy

$$1<{\alpha }_1^{\left(3\right)}\le {\alpha }_2^{\left(3\right)}\le \cdots \mathrm{and}1\ge {\beta }_1^{\left(3\right)}\ge {\beta }_2^{\left(3\right)}\ge \cdots >0,$$

which is studied in [20]. In the worst case setting, the reference [20] investigates the algebraic tractability of $\mathrm{APP}={\left\{{\mathrm{APP}}_d\right\}}_{d\in \mathbb{N}}$, satisfying (8) defined over the reproducing kernel Hilbert space $H_{d,{\mathit{\alpha }}^{\left(3\right)},{\mathit{\beta }}^{\left(3\right)}}$, where the reproducing kernel function has the Gaussian ANOVA weight ${\psi }_{d,{\mathit{\alpha }}^{\left(3\right)},{\mathit{\beta }}^{\left(3\right)}}$. But in the average case setting, there are no results about the algebraic tractability of the problem $\mathrm{APP}={\left\{{\mathrm{APP}}_d\right\}}_{d\in \mathbb{N}}$, satisfying (8) from the Banach space $H_{d,{\mathit{\alpha }}^{\left(3\right)},{\mathit{\beta }}^{\left(3\right)}}$ equipped with a zero-mean Gaussian measure with the Gaussian ANOVA covariance kernel or the variant of the Gaussian ANOVA covariance kernel.

Remark 2.

Note that the variant of the Gaussian ANOVA weight ${\sigma }_{d,\mathit{\alpha },\mathit{\beta }}$ has a faster decay rate than the Gaussian ANOVA weight ${\psi }_{d,{\mathit{\alpha }}^{\left(3\right)},{\mathit{\beta }}^{\left(3\right)}}$.

Lemma 1.

Set $W_{{\alpha }_j,{\beta }_j}\left(k\right)\in \{{\rho }_{{\alpha }_j,{\beta }_j}\left(k\right),{\sigma }_{{\alpha }_j,{\beta }_j}\left(k\right)\}$ for all $j\in \mathbb{N}$ and $k\in {\mathbb{N}}_0$. Then, we have

$$W_{{\alpha }_j,{\beta }_j}\left(k\right)\le {\beta }_j{A}^{{\displaystyle \frac{k^{\lceil {\alpha }_1\rceil }}{{\lceil {\alpha }_1\rceil }^{\lceil {\alpha }_1\rceil }}}}\mathrm{for}\mathrm{all}j,k\in \mathbb{N}.$$

Especially, we have $W_{{\alpha }_j,{\beta }_j}\left(0\right)=1$ for all $j\in \mathbb{N}$.

Proof. 

(1) Set $W_{{\alpha }_j,{\beta }_j}\left(k\right)={\rho }_{{\alpha }_j,{\beta }_j}\left(k\right)$ for all $j,k\in \mathbb{N}$. We have

$${\rho }_{{\alpha }_j,{\beta }_j}\left(k\right)\le {\rho }_{{\alpha }_1,{\beta }_j}\left(k\right)={\beta }_j{A}^{k^{\lceil {\alpha }_1\rceil }}\le {\beta }_j{A}^{{\displaystyle \frac{k^{\lceil {\alpha }_1\rceil }}{{\lceil {\alpha }_1\rceil }^{\lceil {\alpha }_1\rceil }}}}$$

for all $j,k\in \mathbb{N}$.

(2) Set $W_{{\alpha }_j,{\beta }_j}\left(k\right)={\sigma }_{{\alpha }_j,{\beta }_j}\left(k\right)$ for all $j,k\in \mathbb{N}$. For $1\le k<\lceil {\alpha }_j\rceil$ and $j\in \mathbb{N}$, we have

$${\sigma }_{{\alpha }_j,{\beta }_j}\left(k\right)={\beta }_j{A}^{k!}\le {\beta }_{j}A\le {\beta }_j{A}^{{({\displaystyle \frac{k}{\lceil {\alpha }_j\rceil }})}^{\lceil {\alpha }_j\rceil }}={\beta }_j{A}^{{\displaystyle \frac{k^{\lceil {\alpha }_j\rceil }}{{\lceil {\alpha }_j\rceil }^{\lceil {\alpha }_j\rceil }}}}.$$

On the other hand, for $k\ge \lceil {\alpha }_j\rceil$ and $j\in \mathbb{N}$, we obtain

$$\begin{array}{cc}\hfill {\sigma }_{{\alpha }_j,{\beta }_j}\left(k\right)& ={\beta }_j{A}^{k!/(k-\lceil {\alpha }_j\rceil )!}={\beta }_j{A}^{k(k-1)\cdots (k-\lceil {\alpha }_j\rceil +1)}\hfill \\ \hfill & \le {\beta }_j{A}^{{(k-\lceil {\alpha }_j\rceil +1)}^{\lceil {\alpha }_j\rceil }}={\beta }_j{A}^{k^{\lceil {\alpha }_j\rceil }{(1-{\displaystyle \frac{\lceil {\alpha }_j\rceil -1}{k}})}^{\lceil {\alpha }_j\rceil }}\hfill \\ \hfill & \le {\beta }_j{A}^{k^{\lceil {\alpha }_j\rceil }{(1-{\displaystyle \frac{\lceil {\alpha }_j\rceil -1}{\lceil {\alpha }_j\rceil }})}^{\lceil {\alpha }_j\rceil }}={\beta }_j{A}^{{\displaystyle \frac{k^{\lceil {\alpha }_j\rceil }}{{\lceil {\alpha }_j\rceil }^{\lceil {\alpha }_j\rceil }}}}.\hfill \end{array}$$

It follows that for all $j,k\in \mathbb{N}$

$${\sigma }_{{\alpha }_j,{\beta }_j}\left(k\right)\le {\beta }_j{A}^{{\displaystyle \frac{k^{\lceil {\alpha }_j\rceil }}{{\lceil {\alpha }_j\rceil }^{\lceil {\alpha }_j\rceil }}}}.$$

Since ${\sigma }_{{\alpha }_j,{\beta }_j}\left(k\right)\le {\sigma }_{{\alpha }_1,{\beta }_j}\left(k\right)$ for all $j,k\in \mathbb{N}$, we further obtain

$${\sigma }_{{\alpha }_j,{\beta }_j}\left(k\right)\le {\beta }_j{A}^{{\displaystyle \frac{k^{\lceil {\alpha }_1\rceil }}{{\lceil {\alpha }_1\rceil }^{\lceil {\alpha }_1\rceil }}}}.$$

Therefore, by (1) and (2), we have

$$W_{{\alpha }_j,{\beta }_j}\left(k\right)\le {\beta }_j{A}^{{\displaystyle \frac{k^{\lceil {\alpha }_1\rceil }}{{\lceil {\alpha }_1\rceil }^{\lceil {\alpha }_1\rceil }}}}$$

for $W_{{\alpha }_j,{\beta }_j}\left(k\right)\in \{{\rho }_{{\alpha }_j,{\beta }_j}\left(k\right),{\sigma }_{{\alpha }_j,{\beta }_j}\left(k\right)\}$ and all $j,k\in \mathbb{N}$.

(3) For all $j\in \mathbb{N}$, it is obvious from

$${\rho }_{{\alpha }_j,{\beta }_j}\left(0\right)={\sigma }_{{\alpha }_j,{\beta }_j}\left(0\right)=1$$

that $W_{{\alpha }_j,{\beta }_j}\left(0\right)=1$. □

Remark 3.

Set $W_{{\alpha }_j,{\beta }_j}\left(k\right)\in \{{\rho }_{{\alpha }_j,{\beta }_j}\left(k\right),{\sigma }_{{\alpha }_j,{\beta }_j}\left(k\right)\}$ for all $j\in \mathbb{N}$ and $k\in {\mathbb{N}}_0$. Then, for all $j\in \mathbb{N}$ due to ${\rho }_{{\alpha }_j,{\beta }_j}\left(1\right)={\sigma }_{{\alpha }_j,{\beta }_j}\left(1\right)={\beta }_{j}A$, we have $W_{{\alpha }_j,{\beta }_j}\left(1\right)={\beta }_{j}A$.

4. $(s,t)$-Weak Tractability of $L_2$-Approximation with the Two Weighted Covariance Kernels and the Main Result in the Average Case Setting

In this section, we consider $(s,t)$-weak tractability of the $L_2$-approximation $\mathrm{APP}={\left\{{\mathrm{APP}}_d\right\}}_{d\in \mathbb{N}}$, satisfying (8) defined over the Banach space $H_{d,\mathit{\alpha },\mathit{\beta }}\left({[0,1]}^d\right)$ with a zero-mean Gaussian measure ${\mu }_d$ in the average case setting. Here, the covariance kernel $K_{W_{d,\mathit{\alpha },\mathit{\beta }}}$ with weight $W_{d,\mathit{\alpha },\mathit{\beta }}$ of the measure ${\mu }_d$ is given by (6), and the parameter sequences $\mathit{\alpha }={\left\{{\alpha }_j\right\}}_{j\in \mathbb{N}}$ and $\mathit{\beta }={\left\{{\beta }_j\right\}}_{j\in \mathbb{N}}$ satisfy (7). In this paper, we consider two product weights: the variant of the Korobov weight ${\rho }_{d,\mathit{\alpha },\mathit{\beta }}$ and the variant of the Gaussian ANOVA weight ${\sigma }_{d,\mathit{\alpha },\mathit{\beta }}$.

Let $W_{d,\mathit{\alpha },\mathit{\beta }}={\displaystyle \prod _{j=1}^d}{W}_{{\alpha }_j,{\beta }_j}\left(h_j\right)$ with $W_{{\alpha }_j,{\beta }_j}\left(k\right)\in \{{\rho }_{{\alpha }_j,{\beta }_j}\left(k\right),{\sigma }_{{\alpha }_j,{\beta }_j}\left(k\right)\}$ for all $j\in \mathbb{N}$ and $k\in {\mathbb{N}}_0$. Then, from Lemma 1, we have

$$W_{{\alpha }_j,{\beta }_j}\left(0\right)=1\ge W_{{\alpha }_j,{\beta }_j}\left(k\right)\mathrm{for}\mathrm{all}j,k\in \mathbb{N},$$

(11)

which yields

$${\lambda }_{d,1}=W_{d,\mathit{\alpha },\mathit{\beta }}\left(\mathbf{0}\right)={\displaystyle \prod _{j=1}^d}{W}_{{\alpha }_j,{\beta }_j}\left(0\right)=1.$$

(12)

We conclude from (3), (10) with $\tau =1$ and (11) that

$${\mathrm{CRI}}_d=\left\{\begin{array}{cc}& 1,\mathrm{for}\mathrm{X}=\mathrm{ABS},\\ & {\displaystyle \prod _{j=1}^d}(1+{\displaystyle \sum _{k=1}^{\infty }}{W}_{{\alpha }_j,{\beta }_j}\left(k\right)),\mathrm{for}\mathrm{X}=\mathrm{NOR}.\end{array}\right.$$

(13)

By (2) and (13), we obtain

$$\begin{array}{c}\hfill n^{\mathrm{NOR}}(\epsilon ,{\mathrm{APP}}_d)\le n^{\mathrm{ABS}}(\epsilon ,{\mathrm{APP}}_d).\end{array}$$

(14)

Theorem 1.

Let the parameter sequences $\mathit{\alpha }={\left\{{\alpha }_j\right\}}_{j\in \mathbb{N}}$ and $\mathit{\beta }={\left\{{\beta }_j\right\}}_{j\in \mathbb{N}}$ satisfy (7). Consider the $L_2$-approximation APP from the space $H_{d,\mathit{\alpha },\mathit{\beta }}\left({[0,1]}^d\right)$ with the covariance weight $W_{d,\mathit{\alpha },\mathit{\beta }}\in \{{\rho }_{d,\mathit{\alpha },\mathit{\beta }},{\sigma }_{d,\mathit{\alpha },\mathit{\beta }}\}$ in the average case setting. For any $t\in (0,1)$ and $s>0$, $(s,t)$-weak tractability holds under ABS or NOR iff

$$\underset{j\to \infty }{lim}{\beta }_j{j}^{1-t}=0.$$

Proof. 

Necessity. Let $s>0$ and $t\in (0,1)$. Assume that $(s,t)$-weak tractability holds for ABS or NOR.

By the inequality (14), we only need to assume that $(s,t)$-weak tractability holds for NOR. Due to the definition of the information complexity (2) for NOR, we have

$${\mathrm{CRI}}_d-{\displaystyle \sum _{i=1}^{n^{\mathrm{NOR}}(\epsilon ,{\mathrm{APP}}_d)}}{\lambda }_{d,i}={\displaystyle \sum _{i=n^{\mathrm{NOR}}(\epsilon ,{\mathrm{APP}}_d)+1}^{\infty }}{\lambda }_{d,i}\le {\epsilon }^2{\mathrm{CRI}}_d,$$

which means

$$(1-{\epsilon }^2){\mathrm{CRI}}_d\le {\displaystyle \sum _{i=1}^{n^{\mathrm{NOR}}(\epsilon ,{\mathrm{APP}}_d)}}{\lambda }_{d,i}.$$

We further deduce from (13) and (12) that

$$\begin{array}{cc}\hfill (1-{\epsilon }^2){\displaystyle \prod _{j=1}^d}(1+{\displaystyle \sum _{k=1}^{\infty }}{W}_{{\alpha }_j,{\beta }_j}\left(k\right))& =(1-{\epsilon }^2){\mathrm{CRI}}_d\le {\displaystyle \sum _{i=1}^{n^{\mathrm{NOR}}(\epsilon ,{\mathrm{APP}}_d)}}{\lambda }_{d,i}\hfill \\ \hfill & \le n^{\mathrm{NOR}}(\epsilon ,{\mathrm{APP}}_d){\lambda }_{d,1}=n^{\mathrm{NOR}}(\epsilon ,{\mathrm{APP}}_d).\hfill \end{array}$$

(15)

From (15) we obtain

$$\begin{array}{c}\hfill ln{n}^{\mathrm{NOR}}(\epsilon ,{\mathrm{APP}}_d)\ge ln(1-{\epsilon }^2)+{\displaystyle \sum _{j=1}^d}ln(1+{\displaystyle \sum _{k=1}^{\infty }}{W}_{{\alpha }_j,{\beta }_j}\left(k\right)).\end{array}$$

(16)

Set $\epsilon ={\displaystyle \frac{1}{2}}$. It follows from the assumption, inequality (16) and Remark 3 that

$$\begin{array}{cc}\hfill 0=\underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}ln{n}^{\mathrm{NOR}}({\displaystyle \frac{1}{2}},{\mathrm{APP}}_d)& \ge \underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}\left(ln{\displaystyle \frac{3}{4}}+{\displaystyle \sum _{j=1}^d}ln(1+{\displaystyle \sum _{k=1}^{\infty }}{W}_{{\alpha }_j,{\beta }_j}\left(k\right))\right)\hfill \\ \hfill & \ge \underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}\left(ln{\displaystyle \frac{3}{4}}+{\displaystyle \sum _{j=1}^d}ln(1+W_{{\alpha }_j,{\beta }_j}\left(1\right))\right)\hfill \\ \hfill & =\underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}\left(ln{\displaystyle \frac{3}{4}}+{\displaystyle \sum _{j=1}^d}ln(1+{\beta }_{j}A)\right)\hfill \\ \hfill & =\underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t}}{\displaystyle \sum _{j=1}^d}ln(1+{\beta }_{j}A).\hfill \end{array}$$

Due to the fact $ln(1+x)>{\displaystyle \frac{x}{2}}$ for all $x\in (0,1)$, ${\beta }_{j}A\in (0,1)$ for all $j\in \mathbb{N}$ and Stolz theorem, we further have

$$\begin{array}{cc}\hfill 0=\underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}ln{n}^{\mathrm{NOR}}({\displaystyle \frac{1}{2}},{\mathrm{APP}}_d)& \ge \underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t}}{\displaystyle \sum _{j=1}^d}{\displaystyle \frac{{\beta }_{j}A}{2}}\hfill \\ \hfill & ={\displaystyle \frac{A}{2}}\underset{d\to \infty }{lim}{\displaystyle \frac{{\beta }_d}{d^t-{(d-1)}^t}}\hfill \\ \hfill & ={\displaystyle \frac{A}{2t}}\underset{d\to \infty }{lim}{\beta }_d{d}^{1-t}\ge 0.\hfill \end{array}$$

It yields $\underset{d\to \infty }{lim}{\beta }_d{d}^{1-t}=0$ for any $t\in (0,1)$.

Sufficiency. Assume that $\underset{d\to \infty }{lim}{\beta }_d{d}^{1-t}=0$ for any $t\in (0,1)$. We will prove that $(s,t)$-weak tractability holds for ABS or NOR.

By the inequality (14), we only need to prove that $(s,t)$-weak tractability holds for ABS. We set

$${\tau }_k=max\left\{{\displaystyle \frac{1}{{ln}^{+}\left({\beta }_k^{-1}\right)}},{\displaystyle \frac{1}{ln(2k+1)}}\right\}\mathrm{for}k\in \mathbb{N}.$$

(17)

Obviously, $\underset{k\to \infty }{lim}{\beta }_k=0$, and thus, $\underset{k\to \infty }{lim}{\tau }_k=0$, i.e., ${\tau }_k\in (0,1)$ for sufficiently large k. Set $\tau =1-{\tau }_d$. It follows from inequality (5) for ABS that

$$\begin{array}{cc}\hfill & \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}ln{n}^{\mathrm{ABS}}(\epsilon ,{\mathrm{APP}}_d)\hfill \\ \hfill & \le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1-{\tau }_d}{{\tau }_d}}\left(ln{\displaystyle \frac{1-{\tau }_d}{{\tau }_d}}+2ln\left({\epsilon }^{-1}\right)+{\displaystyle \frac{ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d}\right)}{1-{\tau }_d}}\right)+ln2\right|.\hfill \end{array}$$

(18)

Note that

$$\begin{array}{cc}\hfill & 0\le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1-{\tau }_d}{{\tau }_d}}\left(ln{\displaystyle \frac{1-{\tau }_d}{{\tau }_d}}+2ln\left({\epsilon }^{-1}\right)\right)+ln2\right|\hfill \\ \hfill & \le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|\left(ln(2d+1)-1\right)\left(ln\left(ln(2d+1)-1\right)+2ln\left({\epsilon }^{-1}\right)\right)+ln2\right|\hfill \\ \hfill & \le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t}}\left(ln(2d+1)-1\right)ln\left(ln(2d+1)-1\right)+\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{2}{{\epsilon }^{-s}+d^t}}\left(ln(2d+1)-1\right)ln\left({\epsilon }^{-1}\right)\hfill \\ \hfill & =\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{2}{{\epsilon }^{-s}+d^t}}\left(ln(2d+1)-1\right)ln\left({\epsilon }^{-1}\right)\hfill \\ \hfill & \le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left({\left(ln(2d+1)-1\right)}^2+{\left(ln\left({\epsilon }^{-1}\right)\right)}^2\right)\hfill \\ \hfill & \le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t}}{\left(ln(2d+1)-1\right)}^2+\underset{{\epsilon }^{-1}\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}}}{\left(ln\left({\epsilon }^{-1}\right)\right)}^2=0,\hfill \end{array}$$

and thus, in the inequality (18), we only need to prove

$$\begin{array}{c}\hfill \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1}{{\tau }_d}}ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d}\right)\right|=\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}{\displaystyle \frac{ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d}\right)}{{\tau }_d}}=0,\end{array}$$

(19)

where we used

$$ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d}\right)\ge ln{\lambda }_{d,1}^{1-{\tau }_d}=0$$

by (12).

From (10) with $\tau =1-{\tau }_d$ and Lemma 1, we have

$$\begin{array}{cc}\hfill ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d}\right)& =ln\left({\displaystyle \prod _{j=1}^d}\left(1+{\displaystyle \sum _{k=1}^{\infty }}{\left(W_{{\alpha }_j,{\beta }_j}\left(k\right)\right)}^{1-{\tau }_d}\right)\right)\hfill \\ \hfill & ={\displaystyle \sum _{j=1}^d}ln\left(1+{\displaystyle \sum _{k=1}^{\infty }}{\left(W_{{\alpha }_j,{\beta }_j}\left(k\right)\right)}^{1-{\tau }_d}\right)\hfill \\ \hfill & \le {\displaystyle \sum _{j=1}^d}ln\left(1+{\displaystyle \sum _{k=1}^{\infty }}{\beta }_j^{1-{\tau }_d}{A}^{{\displaystyle \frac{1}{{\lceil {\alpha }_1\rceil }^{\lceil {\alpha }_1\rceil }}}(1-{\tau }_d)k^{\lceil {\alpha }_1\rceil }}\right).\hfill \end{array}$$

(20)

Since $0<A^{{\displaystyle \frac{1}{{\lceil {\alpha }_1\rceil }^{\lceil {\alpha }_1\rceil }}}(1-{\tau }_d)k^{\lceil {\alpha }_1\rceil }}\le A^{{\displaystyle \frac{1}{{\lceil {\alpha }_1\rceil }^{\lceil {\alpha }_1\rceil }}}(1-{\tau }_1)k^{\lceil {\alpha }_1\rceil }}$, then ${\displaystyle \sum _{k=1}^{\infty }}{A}^{{\displaystyle \frac{1}{{\lceil {\alpha }_1\rceil }^{\lceil {\alpha }_1\rceil }}}(1-{\tau }_1)k^{\lceil {\alpha }_1\rceil }}$ is convergent. It means that there exists a constant $C>0$ such that

$${\displaystyle \sum _{k=1}^{\infty }}{A}^{{\displaystyle \frac{1}{{\lceil {\alpha }_1\rceil }^{\lceil {\alpha }_1\rceil }}}(1-{\tau }_d)k^{\lceil {\alpha }_1\rceil }}<C$$

(21)

for all $d\in \mathbb{N}$. By (20) and (21), we have

$$\begin{array}{c}\hfill ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d}\right)\le {\displaystyle \sum _{j=1}^d}ln\left(1+C{\beta }_j^{1-{\tau }_d}\right)\le C{\displaystyle \sum _{j=1}^d}{\beta }_j^{1-{\tau }_d},\end{array}$$

(22)

where in the last inequality we used, $ln(1+x)\le x$ for $x\ge 0$. Since (17), we have ${\tau }_j^{-1}\le {ln}^{+}{\beta }_j^{-1}\le 1+ln{\beta }_j^{-1}$ and thus ${\beta }_j\le e^{1-{\tau }_j^{-1}}$ for all $j\in \mathbb{N}$. We further obtain for all $1\le j\le d$ that

$$\begin{array}{c}\hfill {\beta }_j^{1-{\tau }_d}\le {\beta }_j^{1-{\tau }_j}\le e^{(1-{\tau }_j^{-1})(1-{\tau }_j)}=e^{1-{\tau }_j^{-1}}{e}^{-{\tau }_j(1-{\tau }_j^{-1})}.\end{array}$$

(23)

We note that

$$\begin{array}{cc}\hfill e^{1-{\tau }_j^{-1}}& =e{e}^{-{\tau }_j^{-1}}={\displaystyle \frac{e}{min\left\{e^{{ln}^{+}{\beta }_j^{-1}},e^{ln(2j+1)}\right\}}}\hfill \\ \hfill & \le {\displaystyle \frac{e}{min\left\{e^{ln{\beta }_j^{-1}},e^{ln(2j+1)}\right\}}}=emax\left\{{\beta }_j,{\displaystyle \frac{1}{2j+1}}\right\},\hfill \end{array}$$

(24)

and

$$\begin{array}{c}\hfill e^{-{\tau }_j(1-{\tau }_j^{-1})}=e^{-{\tau }_j+1}\le e.\end{array}$$

(25)

Combining (23), (24) and (25), we have

$${\displaystyle \sum _{j=1}^d}{\beta }_j^{1-{\tau }_d}\le e^2{\displaystyle \sum _{j=1}^d}max\left\{{\beta }_j,{\displaystyle \frac{1}{2j+1}}\right\}.$$

(26)

From (22) and (26), we have

$$\begin{array}{cc}\hfill 0& \le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}{\displaystyle \frac{ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d}\right)}{{\tau }_d}}\le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{{\tau }_d{d}^t}}ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d}\right)\hfill \\ \hfill & \le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{{\tau }_d{d}^t}}C{\displaystyle \sum _{j=1}^d}{\beta }_j^{1-{\tau }_d}\le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{{\tau }_d{d}^t}}C{e}^2{\displaystyle \sum _{j=1}^d}max\left\{{\beta }_j,{\displaystyle \frac{1}{2j+1}}\right\}.\hfill \end{array}$$

(27)

Next, we will prove

$$\underset{d\to \infty }{lim}{\displaystyle \frac{1}{{\tau }_d{d}^t}}{\displaystyle \sum _{j=1}^d}max\left\{{\beta }_j,{\displaystyle \frac{1}{2j+1}}\right\}=0.$$

It follows from (17) that

$$\begin{array}{c}\hfill 0\le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{{\tau }_d{d}^t}}{\displaystyle \sum _{j=1}^d}{\displaystyle \frac{1}{2j+1}}\le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{{\tau }_d{d}^t}}{\displaystyle \underset{j=0}{\overset{d}{\int }}}{\displaystyle \frac{1}{2x+1}}dx\le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{2d^t}}{ln}^2(2d+1)=0,\end{array}$$

i.e.,

$$\underset{d\to \infty }{lim}{\displaystyle \frac{1}{{\tau }_d{d}^t}}{\displaystyle \sum _{j=1}^d}{\displaystyle \frac{1}{2j+1}}=0.$$

(28)

Due to $\underset{d\to \infty }{lim}{d}^{1-t}{\beta }_d=0$ for any $t\in (0,1)$, we have $\underset{d\to \infty }{lim}{d}^{1-t/2}{\beta }_d=0$. This means that there exists a positive number $N\in \mathbb{N}$ such that ${\beta }_j\le j^{t/2-1}$ for all $j>N$. It follows that

$$\begin{array}{cc}\hfill {\displaystyle \sum _{j=1}^d}{\beta }_j& ={\displaystyle \sum _{j=1}^N}{\beta }_j+{\displaystyle \sum _{j=N+1}^d}{\beta }_j\le N+{\displaystyle \sum _{j=N+1}^d}{j}^{t/2-1}\hfill \\ \hfill & \le N+{\displaystyle \sum _{j=2}^d}{j}^{t/2-1}\le N+{\displaystyle \underset{1}{\overset{d}{\int }}}{x}^{t/2-1}dx\hfill \\ \hfill & =N+{\displaystyle \frac{2d^{t/2}-2}{t}}\le N+{\displaystyle \frac{2d^{t/2}}{t}}\hfill \end{array}$$

for sufficiently large d, which yields by (17) that

$$\begin{array}{cc}\hfill 0& \le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{{\tau }_d{d}^t}}{\displaystyle \sum _{j=1}^d}{\beta }_j\le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t}}ln(2d+1){\displaystyle \sum _{j=1}^d}{\beta }_j\hfill \\ \hfill & \le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t}}ln(2d+1)(N+{\displaystyle \frac{2d^{t/2}}{t}})\hfill \\ \hfill & =\underset{d\to \infty }{lim}{\displaystyle \frac{N}{d^t}}ln(2d+1)+\underset{d\to \infty }{lim}{\displaystyle \frac{2}{t{d}^t}}{d}^{t/2}ln(2d+1)\hfill \\ \hfill & =\underset{d\to \infty }{lim}{\displaystyle \frac{2}{t{d}^{t/2}}}ln(2d+1)=0,\hfill \end{array}$$

i.e.,

$$\underset{d\to \infty }{lim}{\displaystyle \frac{1}{{\tau }_d{d}^t}}{\displaystyle \sum _{j=1}^d}{\beta }_j=0.$$

(29)

We conclude from (28) and (29) that

$$\underset{d\to \infty }{lim}{\displaystyle \frac{1}{{\tau }_d{d}^t}}{\displaystyle \sum _{j=1}^d}max\left\{{\beta }_j,{\displaystyle \frac{1}{2j+1}}\right\}=0.$$

Then, by (27), we have that

$$\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}{\displaystyle \frac{ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d}\right)}{{\tau }_d}}=0,$$

and thus, (19) holds. Hence $(s,t)$-weak tractability holds for any $t\in (0,1)$ and $s>0$ for ABS or NOR. Therefore, we finish the proof. □

Example 1.

An example for $(s,t)$-weak tractability with $s>0$ and $t\in (0,1)$.

Assume that ${\alpha }_j=2j$ and ${\beta }_j={\displaystyle \frac{1}{j+2}}$ satisfy (7) for all $j\in \mathbb{N}$. Obviously, we have

$$\underset{j\to \infty }{lim}{\beta }_j{j}^{1-t}=\underset{j\to \infty }{lim}{\displaystyle \frac{j^{1-t}}{j+2}}=0.$$

Next, we will prove that the problem APP defined over the space $H_{d,\mathit{\alpha },\mathit{\beta }}\left({[0,1]}^d\right)$ with the covariance weight $W_{d,\mathit{\alpha },\mathit{\beta }}\in \{{\rho }_{d,\mathit{\alpha },\mathit{\beta }},{\sigma }_{d,\mathit{\alpha },\mathit{\beta }}\}$ is $(s,t)$-weakly tractable for $s>0$ and $t\in (0,1)$ under ABS or NOR. By the inequality (14), we only need to prove that $(s,t)$-weak tractability holds for $s>0$ and $t\in (0,1)$ under ABS.

Let $s>0$ and $t\in (0,1)$. Choose

$${\tau }_d^{\prime }={\displaystyle \frac{1}{ln(d+2)}},\mathit{for}d\in \mathbb{N}.$$

Set $\tau =1-{\tau }_d^{\prime }$ in the inequality (5) for ABS. Then, we have

$$\begin{array}{cc}\hfill 0& \le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}ln{n}^{\mathrm{ABS}}(\epsilon ,{\mathrm{APP}}_d)\hfill \\ \hfill & \le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1-{\tau }_d^{\prime }}{{\tau }_d^{\prime }}}\left(ln{\displaystyle \frac{1-{\tau }_d^{\prime }}{{\tau }_d^{\prime }}}+2ln\left({\epsilon }^{-1}\right)+{\displaystyle \frac{ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d^{\prime }}\right)}{1-{\tau }_d^{\prime }}}\right)+ln2\right|\hfill \\ \hfill & \le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1-{\tau }_d^{\prime }}{{\tau }_d^{\prime }}}\left(ln{\displaystyle \frac{1-{\tau }_d^{\prime }}{{\tau }_d^{\prime }}}+2ln\left({\epsilon }^{-1}\right)\right)+ln2\right|\hfill \\ \hfill & +\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1}{{\tau }_d^{\prime }}}ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d^{\prime }}\right)\right|.\hfill \end{array}$$

Since

$$\begin{array}{cc}\hfill & 0\le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1-{\tau }_d^{\prime }}{{\tau }_d^{\prime }}}\left(ln{\displaystyle \frac{1-{\tau }_d^{\prime }}{{\tau }_d^{\prime }}}+2ln\left({\epsilon }^{-1}\right)\right)+ln2\right|\hfill \\ \hfill & =\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|\left(ln(d+2)-1\right)\left(ln\left(ln(d+2)-1\right)+2ln\left({\epsilon }^{-1}\right)\right)+ln2\right|\hfill \\ \hfill & \le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t}}\left(\left(ln(d+2)-1\right)ln\left(ln(d+2)-1\right)+ln2\right)\hfill \\ \hfill & +\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{2}{{\epsilon }^{-s}+d^t}}\left(ln(d+2)-1\right)ln\left({\epsilon }^{-1}\right)\hfill \\ \hfill & =\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{2}{{\epsilon }^{-s}+d^t}}\left(ln(d+2)-1\right)ln\left({\epsilon }^{-1}\right)\hfill \\ \hfill & \le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left({\left(ln(d+2)-1\right)}^2+{\left(ln\left({\epsilon }^{-1}\right)\right)}^2\right)\hfill \\ \hfill & \le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t}}{\left(ln(d+2)-1\right)}^2+\underset{{\epsilon }^{-1}\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}}}{\left(ln\left({\epsilon }^{-1}\right)\right)}^2=0,\hfill \end{array}$$

i.e.,

$$\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1-{\tau }_d^{\prime }}{{\tau }_d^{\prime }}}\left(ln{\displaystyle \frac{1-{\tau }_d^{\prime }}{{\tau }_d^{\prime }}}+2ln\left({\epsilon }^{-1}\right)\right)+ln2\right|=0,$$

next, we only need to prove

$$\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1}{{\tau }_d^{\prime }}}ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d^{\prime }}\right)\right|=0.$$

It follows from (10) with $\tau =1-{\tau }_d^{\prime }$ and Lemma 1 that

$$\begin{array}{cc}\hfill ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d^{\prime }}\right)& =ln\left({\displaystyle \prod _{j=1}^d}\left(1+{\displaystyle \sum _{k=1}^{\infty }}{\left(W_{{\alpha }_j,{\beta }_j}\left(k\right)\right)}^{1-{\tau }_d^{\prime }}\right)\right)\hfill \\ \hfill & ={\displaystyle \sum _{j=1}^d}ln\left(1+{\displaystyle \sum _{k=1}^{\infty }}{\left(W_{{\alpha }_j,{\beta }_j}\left(k\right)\right)}^{1-{\tau }_d^{\prime }}\right)\hfill \\ \hfill & \le {\displaystyle \sum _{j=1}^d}ln\left(1+{\displaystyle \sum _{k=1}^{\infty }}{\beta }_j^{1-{\tau }_d^{\prime }}{A}^{{\displaystyle \frac{1}{{\lceil {\alpha }_1\rceil }^{\lceil {\alpha }_1\rceil }}}(1-{\tau }_d^{\prime })k^{\lceil {\alpha }_1\rceil }}\right)\hfill \\ \hfill & ={\displaystyle \sum _{j=1}^d}ln\left(1+{\displaystyle \frac{1}{{(j+2)}^{1-{\tau }_d^{\prime }}}}{\displaystyle \sum _{k=1}^{\infty }}{A}^{{\displaystyle \frac{(1-{\tau }_d^{\prime })k^2}{4}}}\right).\hfill \end{array}$$

(30)

We note that

$$A^{{\displaystyle \frac{(1-{\tau }_d^{\prime })k^2}{4}}}=A^{{\displaystyle \frac{\left(1-\frac{1}{ln(d+2)}\right)k^2}{4}}}\le A^{{\displaystyle \frac{\left(1-\frac{1}{ln3}\right)k^2}{4}}}$$

and ${\displaystyle \sum _{k=1}^{\infty }}{A}^{{\displaystyle \frac{\left(1-\frac{1}{ln3}\right)k^2}{4}}}$ is convergent. Then, there exists a constant $C>0$ such that

$${\displaystyle \sum _{k=1}^{\infty }}{A}^{{\displaystyle \frac{(1-{\tau }_d^{\prime })k^2}{4}}}\le {\displaystyle \sum _{k=1}^{\infty }}{A}^{{\displaystyle \frac{\left(1-\frac{1}{ln3}\right)k^2}{4}}}\le C.$$

We further obtain from (30) that

$$\begin{array}{cc}\hfill ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d^{\prime }}\right)& \le {\displaystyle \sum _{j=1}^d}ln\left(1+{\displaystyle \frac{C}{{(j+2)}^{1-{\tau }_d^{\prime }}}}\right)\le C{\displaystyle \sum _{j=1}^d}{\displaystyle \frac{1}{{(j+2)}^{1-{\tau }_d^{\prime }}}}\hfill \\ \hfill & =C{\displaystyle \sum _{j=1}^d}{\displaystyle \frac{1}{{(j+2)}^{1-\frac{1}{ln(d+2)}}}}=C{\displaystyle \sum _{j=1}^d}{\displaystyle \frac{{(j+2)}^{\frac{1}{ln(d+2)}}}{j+2}}\hfill \\ \hfill & \le C{\displaystyle \sum _{j=1}^d}{\displaystyle \frac{{(d+2)}^{\frac{1}{ln(d+2)}}}{j+2}}=Ce{\displaystyle \sum _{j=1}^d}{\displaystyle \frac{1}{j+2}}\hfill \\ \hfill & \le Ce\left({\displaystyle \underset{0}{\overset{d}{\int }}}{\displaystyle \frac{1}{x+2}}dx\right)=Ce\left(ln(d+2)-ln2\right),\hfill \end{array}$$

which conclude that

$$\begin{array}{cc}\hfill 0& \le \underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1}{{\tau }_d^{\prime }}}ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d^{\prime }}\right)\right|\hfill \\ \hfill & =\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|Celn(d+2)\left(ln(d+2)-ln2\right)\right|\hfill \\ \hfill & \le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t}}\left|Celn(d+2)\left(ln(d+2)-ln2\right)\right|\hfill \\ \hfill & \le \underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t}}\left|Celn(d+2)\left(ln(d+2)\right)\right|=0,\hfill \end{array}$$

i.e.,

$$\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}\left|{\displaystyle \frac{1}{{\tau }_d^{\prime }}}ln\left({\displaystyle \sum _{i=1}^{\infty }}{\lambda }_{d,i}^{1-{\tau }_d^{\prime }}\right)\right|=0.$$

Hence, we have

$$\underset{{\epsilon }^{-1}+d\to \infty }{lim}{\displaystyle \frac{1}{{\epsilon }^{-s}+d^t}}ln{n}^{\mathrm{ABS}}(\epsilon ,{\mathrm{APP}}_d)=0,$$

which yields that $(s,t)$-weak tractability holds for ABS. Therefore, APP is $(s,t)$-weakly tractable for any $s>0$ and $t\in (0,1)$ under ABS or NOR.

Example 2.

An example for not $(s,t)$-weak tractability with any $s>0$ and $t\in (0,1)$.

Assume that ${\alpha }_j=2^j$ and ${\beta }_j={\displaystyle \frac{1}{ln\left(3j\right)}}$ for all $j\in \mathbb{N}$. Obviously, we have

$$\underset{j\to \infty }{lim}{\beta }_j{j}^{1-t}=\underset{j\to \infty }{lim}{\displaystyle \frac{j^{1-t}}{ln\left(3j\right)}}=\infty .$$

Next, we will prove that the problem APP defined over the space $H_{d,\mathit{\alpha },\mathit{\beta }}\left({[0,1]}^d\right)$ with the covariance weight $W_{d,\mathit{\alpha },\mathit{\beta }}\in \{{\rho }_{d,\mathit{\alpha },\mathit{\beta }},{\sigma }_{d,\mathit{\alpha },\mathit{\beta }}\}$ is not $(s,t)$-weakly tractable for any $s>0$ and $t\in (0,1)$ under ABS or NOR. Due to the inequality (14), we only need to prove that $(s,t)$-weak tractability does not hold for any $s>0$ and $t\in (0,1)$ under NOR.

Let $s>0$ and $t\in (0,1)$. We conclude from inequality (16) with $\epsilon ={\displaystyle \frac{1}{2}}$ and Remark 3 that

$$\begin{array}{cc}\hfill \underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}ln{n}^{\mathrm{NOR}}({\displaystyle \frac{1}{2}},{\mathrm{APP}}_d)& \ge \underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}\left(ln{\displaystyle \frac{3}{4}}+{\displaystyle \sum _{j=1}^d}ln(1+{\displaystyle \sum _{k=1}^{\infty }}{W}_{{\alpha }_j,{\beta }_j}\left(k\right))\right)\hfill \\ \hfill & \ge \underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}\left(ln{\displaystyle \frac{3}{4}}+{\displaystyle \sum _{j=1}^d}ln(1+W_{{\alpha }_j,{\beta }_j}\left(1\right))\right)\hfill \\ \hfill & =\underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}\left(ln{\displaystyle \frac{3}{4}}+{\displaystyle \sum _{j=1}^d}ln(1+{\beta }_{j}A)\right)\hfill \\ \hfill & =\underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}{\displaystyle \sum _{j=1}^d}ln(1+{\beta }_{j}A)\hfill \\ \hfill & =\underset{d\to \infty }{lim}{\displaystyle \frac{1}{2^s+d^t}}{\displaystyle \sum _{j=1}^d}ln(1+{\displaystyle \frac{A}{ln\left(3j\right)}})\hfill \\ \hfill & =\underset{d\to \infty }{lim}{\displaystyle \frac{1}{d^t-{(d-1)}^t}}ln(1+{\displaystyle \frac{A}{ln\left(3d\right)}})\hfill \\ \hfill & =\underset{d\to \infty }{lim}{\displaystyle \frac{1}{t}}{d}^{1-t}ln(1+{\displaystyle \frac{A}{ln\left(3d\right)}})\hfill \\ \hfill & =\underset{d\to \infty }{lim}{\displaystyle \frac{A{d}^{1-t}}{tln\left(3d\right)}}=+\infty ,\hfill \end{array}$$

where, in the fourth equality, we used Stolz theorem. Hence, APP is not $(s,t)$-weak tractable for any $s>0$ and $t\in (0,1)$ under ABS or NOR.

5. Conclusions

In this paper, we study $(s,t)$-weak tractability with any $s>0$ and $t\in (0,1)$ for the $L_2$-approximation problem $\mathrm{APP}={\left\{{\mathrm{APP}}_d\right\}}_{d\in \mathbb{N}}$ from the Banach space $H_{d,\mathit{\alpha },\mathit{\beta }}$ equipped with a zero-mean Gaussian measure ${\mu }_d$ with the covariance kernel $K_{W_{d,\mathit{\alpha },\mathit{\beta }}}$ with weight $W_{d,\mathit{\alpha },\mathit{\beta }}$ in the average case setting, where $1<{\alpha }_1\le {\alpha }_2\le \cdots$ and $1\ge {\beta }_1\ge {\beta }_2\ge \cdots >0$ are parameters. We obtain a compete result for $W_{d,\mathit{\alpha },\mathit{\beta }}\in \{{\rho }_{d,\mathit{\alpha },\mathit{\beta }},{\sigma }_{d,\mathit{\alpha },\mathit{\beta }}\}$ that APP is $(s,t)$-weakly tractable under ABS or NOR for any $s>0$ and $t\in (0,1)$ iff

$$\underset{j\to \infty }{lim}{\beta }_j{j}^{1-t}=0.$$

We will further investigate other algebraic tractability notions about multivariate approximation problems from Banach spaces equipped with zero-mean Gaussian measures with other types of covariance kernels and hope to obtain more good results.