Tractability of $L_2$-approximation and integration over weighted Korobov spaces of increasing smoothness in the worst case setting

1.   Introduction

Solving multivariate continuous problems is a classical topic in applications, and there are thousands of papers to study this problem, usually for a fixed space of functions. Such problems can almost never be solved analytically. Since they must be solved numerically, they can only be solved approximately to within a threshold $\varepsilon$. To deal with these problems, we often use algorithms based on finitely many information evaluations, either from the class $\Lambda^{\rm all}$ of general linear information consisting of all continuous linear functionals, or from the class $\Lambda^{\rm std}$ of standard information consisting of function evaluations only. This motivates us to study the tractability of multivariate problems referring to $S = \{S_ {d}: F_ {d}\rightarrow G_ {d}\}$, where $F_d$ is a Banach space of functions and $G_d$ is another Banach space. For $\varepsilon \in (0, 1)$, the information complexity $n^X(\varepsilon, S_d, F_d; \Lambda)$, $X\in\{{\rm ABS}, {\rm NOR}\}$, can be defined as the least number of linear functionals that are sufficient to obtain an $\varepsilon$-approximation for the information class $\Lambda$ under the absolute error criterion (ABS) and normalized error criterion (NOR). Tractability describes how the information complexity $n^X(\varepsilon, S_d, F_d; \Lambda)$ behaves as a function of $d$ and $\varepsilon^{-1}$, which mainly includes strong polynomial tractability (SPT), polynomial tractability (PT), quasi-polynomial tractability (QPT), uniformly weak tractability (UWT), weak tractability (WT), and $(\sigma, \tau)$-weak tractability ($(\sigma, \tau)$-WT).

The two most important and widely studied such problems are multivariate approximation and multivariate integration (see e.g., ^[1,2,3]). In many applications, including the solution of important computational problems such as differential and integral equations, and problems in financial mathematics, people are particularly interested in Sobolev spaces. A variant of Sobolev spaces is the Korobov space, which is often called the Sobolev spaces of dominating mixed smoothness. Such spaces are probably the most important spaces for the study of computational problems for periodic smooth functions. Moreover, these spaces also have many interesting applications for non-periodic functions due to interesting relations and estimates between the complexity for the periodic and non-periodic computational problems, such as multivariate integration, see e.g., ^[2]. This paper is devoted to discussing the tractability of multivariate $L_2$-approximation

with ${\rm APP}_d (f) = f$, and multivariate integration

with ${\rm INT}_d(f) = \int_{[0, 1]^d} f({\bf x}){\rm d} {\bf x}$, for both $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ in the worst-case setting, where $\mathcal H(K_R)$ denotes a weighted Korobov space with increasing smoothness defined over $[0, 1]^d$ with Fourier weight $R\in\{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$ (see Section 2.2 for details). Here, $\boldsymbol\gamma = \{(1\ge)\gamma_1\ge\gamma_2\ge\dots\}$ is a positive weight sequence and $\boldsymbol\alpha = \{(1 < )\alpha_1\le \alpha_2\le \dots\}$ is an increasing smoothness sequence (see Section 2 for details). We remark that in our considered case the initial error is 1; therefore, the results under ABS and NOR coincide. The related problem has already been discussed in a large number papers, see e.g., ^[1,3,4,5,7]. Particularly, for $R = r_{d, \boldsymbol\alpha, \boldsymbol\gamma}$ with $1 < \alpha_1 = \alpha_2 = \dots$, the complete picture of multivariate $L_2$-approximation for $\Lambda\in\{\Lambda^{\rm all}, \Lambda^{\rm std}\}$ and multivariate integration was given in ^[8]. For $R = r_{d, \boldsymbol\alpha, \boldsymbol\gamma}$ with $1 < \alpha_1\le\alpha_2\le\dots$, the results on multivariate $L_2$-approximation for $\Lambda^{\rm all}$ were given in ^[9]. For a more general case, $R\in\{\psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$, some partial results of multivariate $L_2$-approximation for $\Lambda^{\rm all}$ were found in ^[10]. The related results will be formulated in Section 2.3. In this paper, our aim is to provide the conditions that are both sufficient and necessary for all tractability notions of multivariate $L_2$-approximation and multivariate integration for both information classes $\Lambda^{{\rm all}}$ and $\Lambda^{{\rm std}}$.

The remainder of this article is organized as follows. In Section 2 we recall some basic facts on tractability and weighted Korobov spaces, and briefly formulate previous results and the main results of the current paper. In Sections 3 and 4, we discuss the tractability of $L_2$-approximation and integration in the worst-case setting, respectively.

2.   Preliminaries and main results

In this section, we first introduce the fundamental concepts related to tractability in multivariate problems and weighted Korobov spaces, and then we recall the previous results on the tractability of $L_2$-approximation and integration. Finally, our results are summarized in a table.

2.1.   Tractability.

Let $\{F_d\}_{d\in \mathbb N}$, $\{G_d\}_{d\in \mathbb N}$ be two sequences of Hilbert spaces, and let $\{S_d:\, F_d\to G_d\}_{d\in\mathbb N}$ be a family of continuous linear operators. We will consider two special choices of $S$, namely:

● $L_2$-approximation of functions $f\in F_d$. In this case, we have $S_d(f) = f$ and $G_d = L_2([0, 1]^d)$.

● Integration of functions $f\in F_d$. In this case, we have $S_d(f) = \int_{[0, 1]^d}f({\bf x}){\rm d}{\bf x}$ and $G_d = \mathbb R$.

We approximate $S_d$ by algorithms $A_{n, d}$ of the form

where $g_i\in G_d$ and $L_i\in \Lambda$ for $i = 1, \cdots, n$. We will assume that the considered functionals $L_i$ belong to $\Lambda^{{\rm all}} = F_d^*$ or $\Lambda^{{\rm std}}$. The worst-case error for the algorithm $A_{n, d}$ of the form (2.1) is defined as

Then, the $n$-th minimal worst-case error is defined by

where the infimum is taken over all linear algorithms of the form (2.1). Particularly, for $n = 0$, the initial error of the problem $S_d$ in the worst-case setting is defined by

It is interesting to see how the worst-case errors of $A_{n, d}$ depend on the number $n$ and on the dimension $d$ under ABS or NOR. For this purpose, we introduce the so-called information complexity as

where

The following notions have been frequently studied. For more about tractability we refer to ^[1,2,3] by Novak and Woźniakowski.

Consider the multivariate problem $S: = \{S_d\}_{d\in\mathbb N}$ using the information class $\Lambda\in\{\Lambda^{\rm all}, \Lambda^{\rm std}\}$ under ABS or NOR. We say that $S$ is

$1)$ polynomially tractable (PT) if there are $C > 0$ and $\tau, \sigma\ge0$ satisfying

$2)$ strong polynomially tractable (SPT) if there are $C > 0$ and $\tau\ge0$ satisfying

The infimum of $\tau \ge 0$ for which the inequality (2.2) is satisfied for a certain $C > 0$ is referred to as the exponent of SPT, denoted by $\tau^{\ast}(\Lambda)$.

$3)$ quasi-polynomially tractable (QPT) if there are $t\ge0$ and $C > 0$ satisfying

The infimum of $t \ge 0$ for which the inequality (2.3) is satisfied for a certain $C > 0$ is referred to as the exponent of QPT, denoted by $\tau^{\ast}(\Lambda)$.

$4)$weak tractable (WT) if

$5)$ $(\sigma, \tau)$-weak tractable ($(\sigma, \tau)$ -WT) for $\sigma, \tau > 0$ if

$6)$uniform weak tractable (UWT) if $(\sigma, \tau)$-WT holds for all $\sigma, \tau > 0$.

It is evident that the following relationship holds:

Clearly, the notions of WT and $(1, 1)$-WT coincide.

2.2.   Weighted Korobov space $\mathcal H(K_R)$.

Now we briefly recall some facts on weighted Korobov spaces of increasing smoothness. Weighted Korobov spaces are special types of the reproducing kernel Hilbert spaces $\mathcal H(K_R)$ with a reproducing kernel of the form

for some summable function $R:\mathbb Z^d\to\mathbb (0, +\infty)$, i.e., $\sum_{{\bf k}\in\mathbb Z^d}R({\bf k}) < {+}\infty$, which is often called the Fourier weight, and the corresponding inner product

Here, the Fourier coefficients $\{\widehat{f}({\bf k})\}_{{\bf k}\in\mathbb Z^d}$ are given by

We remark that the reproducing kernel $K_R$ is well defined, since for all ${\bf x}, {\bf y} \in [0, 1]^d$,

We will consider three possible Fourier weights. Assume that $\boldsymbol\gamma = \{\gamma_j\}_{j \in\mathbb N}$ is a sequence of so-called product weights and $\boldsymbol\alpha = \{\alpha_j\}_{j \in\mathbb N}$ is the smoothness parameter sequence satisfying

$1)$ Weighted Korobov space.

In this case, we consider $R({\bf k})$ as

where

for $\gamma > 0, \alpha > 1$.

Furthermore, when $\alpha_j\in\mathbb N$ for all $j\in\mathbb N$, we define the norm

where $\partial_{\bf x}^{\boldsymbol\tau}: = \partial_{x_1}^{\tau_1}\dots\partial_{x_d}^{\tau_d}$ for $\boldsymbol\tau: = (\tau_1, \dots, \tau_d)\in\mathbb Z^d$. It can be checked that the norm $\|f\|_{\mathcal H(K_{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}})}$ is finite if and only if the norm $\|f\|_{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}}$ is finite with the existence of $\partial_{\bf x}^{\boldsymbol\tau}f$ for all $\boldsymbol\tau\le {\boldsymbol\alpha}: = (\alpha_1, \dots, \alpha_d)$. This also indicates a relation between smoothness and $\boldsymbol\alpha$.

$2)$ A first variant of the weighted Korobov space.

In this case, we consider $R({\bf k})$ as

where

for $\gamma > 0, \alpha > 1$.

$3)$ A second variant of the weighted Korobov space.

In this case, we consider $R({\bf k})$ as

where

for $\gamma > 0, \alpha > 1$.

Without loss of generality, we usually assume that the weights $\boldsymbol\gamma = \{\gamma_j\}_{j \in\mathbb N}$ are ordered by

Remark 1 ([^[10]]). Let $R_{\alpha_j, \gamma_j}\in\{r_{\alpha_j, \gamma_j}, \psi_{\alpha_j, \gamma_j}, \omega_{\alpha_j, \gamma_j}\}$ for all $j\in\mathbb N$. Then

Furthermore, we have the following proposition from ^[11] (also [10, Remark 4]).

Proposition 1 (^[10,11]). Let $\boldsymbol\alpha = \{\alpha_j\}_{j \in\mathbb N}$ be the smoothness parameter sequence satisfying (2.4) and let $\boldsymbol\gamma = \{\gamma_j\}_{j \in\mathbb N}$ be the weight sequence satisfying (2.5). Set $R_{d, \boldsymbol\alpha, \boldsymbol\gamma} = \{R_{\alpha_j, \gamma_j}\}_{j\ge1}\in\{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$. Then, for all $j\in\mathbb N$ and $k\in\mathbb Z$, we have

and

Hence, we obtain

which implies that for all ${\bf k}\in\mathbb Z^d$,

and

where $r_{d, \boldsymbol\alpha, \boldsymbol\gamma/3} = \prod_{j = 1}^dr_{\alpha_j, \gamma_j/3}$ and $r_{d, \alpha_1, \lceil\alpha_1\rceil^{\lceil\alpha_1\rceil}\boldsymbol\gamma} = \prod_{j = 1}^dr_{\alpha_1, \lceil\alpha_1\rceil^{\lceil\alpha_1\rceil}\gamma_j}$.

Remark 2. From the definition of $\mathcal H(K_R)$, we know that if $R_1, R_2: \mathbb Z^d \rightarrow (0, +\infty)$ are two Fourier weights for weighted Korobov spaces $\mathcal H(K_{R_1})$ and $\mathcal H(K_{R_2})$ with

then

That is, $\mathcal H(K_{R_1})$ is continuously embedded into $\mathcal H(K_{R_2})$, denoted by $\mathcal H(K_{R_1})\hookrightarrow \mathcal H(K_{R_2})$. Meanwhile, by (2.7), we have

and

which implies that

and

These also indicate a relation between smoothness and $\boldsymbol\alpha$.

2.3.   Results.

Let $\boldsymbol\gamma = \{\gamma_j\}_{j \in\mathbb N}$ be a sequence of product weights and let $\boldsymbol\alpha = \{\alpha_j\}_{j \in\mathbb N}$ be the smoothness parameter sequence satisfying $1 < \alpha_1\le\alpha_2\le\cdots$. For the weight space $\mathcal{H}(K_{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}})$ with $1 < \alpha_1 = \alpha_2 = \dots$, the complete picture of tractability of $L_2$-approximation ${{\rm{APP}}}$ for both $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$, and integration ${\rm INT}$, has been obtained in ^[12]. Besides, ^[5,10] obtained some partial results of weighted Korobov space $\mathcal{H}(K_R)$ with $R\in\{ r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$. The characterization of tractability will be given in terms of decay conditions on the weight sequence ${\boldsymbol\gamma} = \{\gamma_j\}_{j \in\mathbb N}$. Before presenting our findings, we will first outline some key notations. (We use the convention that $\inf \emptyset = \infty$.)

● The infimum of the sequence $\boldsymbol\gamma$ is denoted by

● The infimum of the sequence $(\ln\gamma_j^{-1}/\ln j)_{j\in\mathbb N}$ is denoted by

● The sum exponent $s_{\boldsymbol\gamma}$ is defined as

● The exponent $t_{\boldsymbol\gamma}$ is defined as

We summarize the above results in the following two tables (Tables 1 and 2).

Remark 3. We remark that the condition $\delta_{\boldsymbol\gamma} > 0$ is equivalent to the condition $s_{\boldsymbol\gamma} < \infty$ which can be seen from the condition $1 < \alpha = \alpha_1 = \alpha_2 = \cdots$ in Tables 1 and 2.

In this paper, we outline the conditions necessary for the tractability of $L_2$-approximation in $\mathcal{H}(K_R)$ for both $\Lambda^{\text{all}}$ and $\Lambda^{\text{std}}$, as demonstrated in Theorems 1 and 2. The results of our findings are presented in Table 3.

This paper also investigates the tractability of integration ${\rm INT}$. We obtain the sufficient and necessary conditions on all tractability notions, which are the same as for the tractability of the $L_2$-approximation ${\rm APP}$ for the class $\Lambda^{\rm all}$.

3.   $L_2$-approximation in $\mathcal{H}(K_R)$.

This section focuses on the tractability of $L_2$-approximation on the weighted Korobov space $\mathcal{H}(K_R)$. We will study this problem for the classes $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$, respectively.} More precisely, we want to approximate the embedding operators

in the worst-case setting. It can be seen that ${{\rm{APP}}}_d$ is the compact embedding from the weighted space $\mathcal{H}(K_R)$ to $L_2([0, 1]^d)$. To approximate ${{\rm{APP}}}_d$ with respect to the $L_2$-norm $\|\cdot\|_{L_2}$ over $[0, 1]^d$, it follows from ^[1,13] that it suffices to use linear algorithms $A_{n, d}^{\rm app}$ of the form

with $g_i \in L_2([0, 1]^d)$ and $L_i \in \{\Lambda^{\rm all}, \Lambda^{\rm std}\}$ for $i = 1, \ldots, n$. Remember that $\mathcal{H}(K_R)$ is a reproducing kernel Hilbert space and $\Lambda^{{\rm std}}\subseteq\Lambda^{{\rm all}}$.

The $n$-th minimal worst-case error with respect to the information class $\Lambda$ is given by

where the infimum is extended over all algorithms of the form (3.1) with information from $\Lambda$. For $n = 0$, the initial approximation error is given by

In the following, we assume that $0 < R({\bf k})\le 1$ for all ${\bf k} \in \mathbb Z^d$, which implies that the norm of ${{\rm{APP}}}_d$ is 1, since for all $f \in \mathcal{H}(K_R)$,

and the above inequality is sharp if $f \equiv 1$. In the remaining part of this paper, we always assume that $0 < R({\bf k})\le 1$, which implies that there is no need to distinguish between ABS and NOR. For abbreviation, we write $n(\varepsilon, {{\rm{APP}}}_d, \mathcal{H}(K_R); \Lambda)\equiv n^{X}(\varepsilon, {{\rm{APP}}}_d, \mathcal{H}(K_R); \Lambda)$.

3.1.   The information class $\Lambda^{{ all}}$.

First we present the results on $L_2$-approximation in the weighted Korobov space $\mathcal{H}(K_R)$ for the information class $\Lambda^{{\rm all}}$.

Theorem 1. Let $\boldsymbol\alpha = \{\alpha_j\}_{j \in\mathbb N}$ be the smoothness parameter sequence satisfying (2.4) and let $\boldsymbol\gamma = \{\gamma_j\}_{j \in\mathbb N}$ be the weight sequence satisfying (2.5). Consider the $L_2$-approximation problem ${{\rm{APP}}} = \{ {{\rm{APP}}}_{d}\}_{d\in\mathbb N}$ for the weighted spaces $\mathcal{H}(K_R)$, $R\in\{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$ for the information class $\Lambda^{{\rm all}}$ under ABS and NOR. We have the following conditions:

(i) (Cf. ^[10]) SPT and PT are equivalent and hold iff $s_{\boldsymbol\gamma} < \infty$. In this case, the exponent of SPT is

(ii) QPT, UWT, WT, and $(\sigma, \tau)$-WT with $\sigma \in (0, 1]$, are are equivalent and hold iff $\boldsymbol\gamma_I < 1.$ In this case, the exponent of QPT satisfies

and the equality holds for $R\in\{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$. (In particular, if $\boldsymbol\gamma_I = 0$, then we set $(\ln \boldsymbol\gamma_I^{-1})^{-1}: = 0$ and we have that $t^{\ast}(\Lambda^{{\rm all}}) = 2/\alpha_1$.)

(iii) (Cf. ^[10]) For $\sigma > 1$, $(\sigma, \tau)$-WT always holds.

To obtain the above theorem, we recall some basic knowledge about $L_2$-approximation for the information class $\Lambda^{{\rm all}}$. It is well known, see e.g., ^[1], that the $n$-th minimal worst-case errors $e(n, {{\rm{APP}}}_d, \mathcal{H}(K_R); \Lambda^{\rm all})$ and the information complexity $n(\varepsilon, {{\rm{APP}}}_d, \mathcal{H}(K_R); \Lambda^{\rm all})$ depend on the eigenvalues of the continuous linear operator

Let $(\lambda_{d, j}, \boldsymbol\eta_{d, j})_{j\in\mathbb N}$ be the eigenpairs of $W_d$, i.e.,

where the eigenvalues $(\lambda_{d, j})$ are ordered by $\lambda_{d, 1}\ge \lambda_{d, 2}\ge \cdots \ge 0,$ and the eigenvectors $(\boldsymbol\eta_{d, j})_{j\in\mathbb N}$ are orthonormal,

Then, the $n$-th minimal error is obtained (see [1, Corollary 4.12]) for the algorithm

and

Hence, the information complexity is equal to

with $\varepsilon\in(0, 1)$ and $d\in\mathbb N$. Since it follows from ^[1] that the eigenpairs of the operator $W_d$ are $(R({\bf k}), e_{{\bf k}})$ with ${\bf k} \in \mathbb Z^d$, where

we have

Now we begin to prove Theorem 1.

Proof of Theorem 1. (ⅰ) and (ⅲ) have been proved in ^[10]. We include the proof of item (ⅰ) and (ⅱ) in a different way as a warm-up.

(ⅰ) From [1, Theorem 5.2], we know that ${{\rm{APP}}}$ is PT for $\Lambda^{\rm all}$ if and only if there exist $q\ge0$ and $\tau > 0$ such that

and $\tau^\ast(\Lambda^{\mathrm{all}}) = \inf\{2 \tau:\, \tau \text{ satisfies (3.4)}\}.$

Since SPT implies PT, it suffices to demonstrate the sufficiency of $s_{\boldsymbol\gamma} < \infty$ for SPT, and the necessary of $s_{\boldsymbol\gamma} < \infty$ for PT.

● Sufficiency of $s_{\boldsymbol\gamma} < \infty$ for SPT.

Now we assume that $s_{\boldsymbol\gamma} < \infty$. Then, for any $\tau > \max(s_{\boldsymbol\gamma}, \tfrac{1}{\alpha_1})$, we have $\sum_{j = 1}^\infty \gamma_j^\tau < \infty$. Using (2.10) and (2.8), we obtain

where we also used that $\ln(1+x)\le x$ for $x\ge0$ and $\zeta(\alpha_1 \tau) < \infty$ for $\tau > 1/\alpha_1$. This leads to $C_{\tau, q} < \infty$ for all $q\ge0$, thus we have SPT, PT and

● Necessity of $s_{\boldsymbol\gamma} < \infty$ for PT.

Now we assume that PT holds. Then there exists $\tau > 0$ such that (3.4) holds with $q = 0$. Clearly, we need $\tau > 1/{\alpha_1}$. Again using (2.8) and $\zeta(\alpha_j \tau) > 1$ for all $j$, we obtain

Meanwhile, (3.4) implies that $\sum_{j = 1}^\infty \gamma_j^\tau < \infty$ and hence $s_{\boldsymbol\gamma}\le \tau < \infty$. Combining both results yields that $\tau \ge \max(s_{\boldsymbol\gamma}, \frac{1}{\alpha_1})$ and hence also

Then (3.5) and (3.6) imply $\tau^\ast(\Lambda^{\mathrm{all}}) = 2 \max(s_{\boldsymbol\gamma}, \tfrac{1}{\alpha_1})$.

(ⅱ) From [3, Theorem 23.2] (see also ^[14]), we know that ${{\rm{APP}}}$ is QPT if and only if there exists a $\tau > 0$ such that

First, assume that $\boldsymbol\gamma_I < 1$. For $R\in\{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$, we have, by (2.7) and similar to the proof of [11, Theorem 14], that

In order that $\zeta_d: = \zeta(\alpha_1 \tau (1 + \ln d)) < \infty$ for all $d \in \mathbb{N}$, we need $\tau > 1/\alpha_1$. Next, we have

where $c_{\tau}: = 2+ 1/(2^{4\tau}-2^{3 \tau})$. This gives

where we used that $\ln(1+x) \le x$ for all $x \ge 0$. Using the inequality

we have

Then we obtain

Now we distinguish two cases:

● Case 1: $\boldsymbol\gamma_I = 0$. In this case, we have $\lim_{j \rightarrow \infty}\gamma_j = 0$ and hence, there is a $J\in\mathbb N$ such that $\gamma_j \le e^{-1/\tau}$ for all $j \ge J$. Then

Note that $J$ depends on $\tau$, and it is finite for any fixed $\tau$. Thus, if $\tau > 1/\alpha_1$ and $\boldsymbol\gamma_I = 0$ then

By the characterization in (3.7), this implies QPT.

● Case 2: $\boldsymbol\gamma_I \in (0, 1)$. In this case, for any $\gamma_{\ast} \in (\boldsymbol\gamma_I, 1)$, there exists a $j_0 \in \mathbb{N}$ such that $\gamma_j \le \gamma_{\ast} < 1$ for all $j > j_0$. Then for every $d \in \mathbb{N}$,

whenever $\tau \ge (\ln \gamma_\ast^{-1})^{-1}$. Thus, if $\tau > 1/\alpha_1$ and $\tau \ge (\ln \gamma_\ast^{-1})^{-1}$, then

Again, by the characterization in (3.7), this implies QPT.

Clearly, QPT implies UWT, WT, and $(\sigma, \tau)$-WT with $\sigma \in (0, 1]$. So it remains to prove that WT implies $\boldsymbol\gamma_I < 1$. To this end, we let $\boldsymbol\gamma_I = 1$, i.e., $\gamma_j\equiv1$. Then we derive from (2.6) that for ${\bf k}\in\{0, 1\}^d$,

which, by (3.3), implies that for any $\varepsilon\in(0, \sqrt{\eta})$,

This means that ${{\rm{APP}}}$ suffers from the curse of dimensionality, and thus, we cannot have $(\sigma, \tau)$-WT for any $\sigma\in(0, 1]$. This deduces that QPT, UWT, WT, and $(\sigma, \tau)$-WT with $\sigma \in (0, 1]$ are equivalent, and hold iff $\boldsymbol\gamma_I < 1$.

Now we turn to calculate the exponent of QPT. Again from [3], Theorem 23.2], we know that the exponent of QPT is

From the above part of the proof, it follows that $\tau$ satisfies (3.7) as long as $\tau > 1/\alpha_1$ and $\tau > (\ln \boldsymbol\gamma_I^{-1})^{-1}$, where we put $(\ln \boldsymbol\gamma_I^{-1})^{-1}: = 0$ whenever $\boldsymbol\gamma_I = 0$. Therefore,

Assume now that we have QPT for $R\in\{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$. Then, (3.7) holds true for some $\tau > 0$. Consideration of the special case $d = 1$ together with (3.7) yields that

where we used (2.10), and hence we must have $\tau > 1/\alpha_1$. This already implies the result $t^{\ast}(\Lambda^{{\rm all}}) = 2/{\alpha_1}$ whenever $\boldsymbol\gamma_I = 0$.

It remains to study the case $\boldsymbol\gamma_I > 0$. Now, again according to (3.7) and (2.10), there exists a $\tau > 1/\alpha_1$ such that for all $d \in \mathbb{N}$ we have

Taking the logarithm leads to

for all $d \in \mathbb{N}$. Since $\boldsymbol\gamma_I \in (0, 1)$ and since $\ln(1+x)\ge x \ln 2$ for all $x \in [0, 1]$, it follows that for all $d \in \mathbb{N}$ we have

which implies that $\tau \ge (\ln \boldsymbol\gamma_I^{-1})^{-1}$. Therefore, we will get

and the claimed result follows.

(ⅲ) The result for $(\sigma, \tau)$-weak tractability for $\sigma > 1$ for the class $\Lambda^{{\rm all}}$ follows from the corresponding result for the class $\Lambda^{{\rm std}}$ from Theorem 2.

The proof is completed. □

3.2.   The information class $\Lambda^{{ std}}$.

In the next theorem, we present the respective conditions for tractability of $L_2$-approximation in the weighted Korobov space $\mathcal{H}(K_R)$ for the information class $\Lambda^{{\rm std}}$.

Theorem 2. Let $\boldsymbol\alpha = \{\alpha_j\}_{j \in\mathbb N}$ be the smoothness parameter sequence satisfying (2.4) and let $\boldsymbol\gamma = \{\gamma_j\}_{j \in\mathbb N}$ be the weight sequence satisfying (2.5). Consider the $L_2$-approximation problem ${{\rm{APP}}} = \{ {{\rm{APP}}}_d\}_{d \in\mathbb N}$ for the weighted spaces $\mathcal{H}(K_R)$, $R\in\{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$ for the information class $\Lambda^{{\rm std}}$ under ABS and NOR. Then we have the following conditions:

(i) SPT holds iff

(which implies $s_{\boldsymbol\gamma} \le 1$). In this case, the exponent of SPT is

(ii) PT, QPT are equivalent and hold iff

(iii) WT holds iff

(iv) UWT holds iff

(v) For $\sigma \in (0, 1]$, $(\sigma, \tau)$-WT holds iff

For $\sigma > 1$, $(\sigma, \tau)$-WT always holds.

The proof of Theorem 2 is based on relations between the minimal errors of $\Lambda^{\text{std}}$ and $\Lambda^{\text{all}}$, in particular on [17, Theorem 1] and on [6, Theorem 1] (see also [3, Theorem 26.10]). These results provide that the trace of the operator $W_d = {{\rm{APP}}}_d^* {{\rm{APP}}}_d$ is finite. Recall that the trace of $W_d$ is given by the sum of its eigenvalues, i.e.,

Using (2.10), we obtain

and

Hence ${\rm trace}(W_d)$ is infinite if and only if $\alpha_1 = \alpha_2 = \dots = 1$. Note that in general there is no relation between the power of $\Lambda^{{\rm all}}$ and $\Lambda^{{\rm std}}$ whenever the trace of $W_d$ is infinite. For a discussion of this issue we refer to [3, Section 26.3].

In order to prove the sufficiency of PT for $\Lambda^{\rm std}$, we use a criterion from ^[3] as stated below.

Lemma 2. ([3, Theorem 26.13]). Consider multivariate approximation ${\rm APP} = \{{\rm APP}_d\}_{d\in\mathbb N}$ in the worst-case setting for ABS or NOR, where

and $F_d$ is a reproducing kernel Hilbert space continuously embedded in $G_d$. Assume that the trace of $W_d$ is finite for all $d$, and there are two constants $C, q\ge0$ such that

Then polynomial tractabilities of ${\rm APP}$ for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ are equivalent. Particularly, if $q = 0$, then strong polynomial tractabilities of ${\rm APP}$ for $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$ are equivalent. More precisely,

implies that there exists a constant $C^{{\rm std}}\ge0$ such that

where

Now we prove Theorem 2.

Proof of Theorem 2. It follows from (4.2) in Section 4 that necessary conditions of tractability for integration ${\rm INT}$ are also necessary for $L_2$ approximation ${\rm APP}$. Consequently, the necessity of the conditions outlined in items (ⅰ)–(ⅴ) is derived from Theorem 3. It is enough to examine whether the conditions in items (ⅰ)–(ⅴ) are sufficient.

(ⅰ) Clearly, $\alpha_1 > 1$ implies that ${\rm trace}(W_d)$ is finite for all $d \in \mathbb N$. Then according to [17, Theorem 1], there is a positive integer $c$ satisfying for all $n \in \mathbb N$

Now let $\sum_{j = 1}^{\infty} \gamma_j < \infty$. Then, the sum exponent $s_{\boldsymbol\gamma} \le 1$.

● First we consider $s_{\boldsymbol\gamma} < 1$. Then, using Theorem 1, we have SPT for $\Lambda^{{\rm all}}$ with exponent

Hence, for every $\tau > \tau^{\ast}(\Lambda^{{\rm all}})$ there is $C > 0$ such that

which yields that

Inserting into (3.13) gives

Hence, there exists a number $a_{\tau} > 0$ such that

which implies that

Hence, since $\tau > \tau^{\ast}(\Lambda^{{\rm std}})$ is arbitrary, we have SPT with

(Note that trivially $\tau^{\ast}(\Lambda^{{\rm std}}) \ge \tau^{\ast}(\Lambda^{{\rm all}}) = 2 \max(1/\alpha_1, s_{\boldsymbol\gamma})$.)

● Next we consider $s_{\boldsymbol\gamma} = 1$. From (3.13) and (3.2) we obtain

Since $\sum_{j = 1}^{\infty}\gamma_j < \infty$ and $\alpha_1 > 1$, we derive from (3.12) that

Hence, insertion into (3.14) gives

From this, we obtain in the same way as above SPT with

(ⅱ) Assume that (3.8) holds. This implies that there exists a constant $M > 0$ such that

Then, by (3.12) we have

Meanwhile, since the sequence $(\gamma_j)_{j\in\mathbb N}$ is non-increasing, we have

which implies that^* $\gamma_j = \mathcal{O}(j^{-1} \ln j)$ and $s_{\boldsymbol\gamma} = 1$. By Theorem 1 (this implies that ${{\rm{APP}}}$ is SPT for $\Lambda^{\text{all}}$, i.e., there exist two constants $C^{{\rm all}}, p^{{\rm all}}\ge0$ such that

Here, $A_j = \mathcal{O}(B_j)$ means that there exists a constant $C > 0$ independent of $j$ such that $A_j\le CB_j$.

Now Lemma 2 implies that there is a constant $C^{{\rm std}} > 0$ such that

where

Hence, we have PT and QPT for $\Lambda^{{\rm std}}$.

(ⅲ)–(ⅴ) If any of the three conditions (3.9), (3.10) or (3.11) holds, then this leads to $\boldsymbol\gamma_{I} < 1$, since otherwise, for every $\sigma \in (0, 1]$,

Therefore, we know from Theorem 1 that WT, UWT, and $(\sigma, \tau)$-WT with $\sigma \in (0, 1]$ hold for $\Lambda^{\text{all}}$.

We only prove the sufficiency of (3.11) for $(\sigma, \tau)$-WT with $\sigma \in (0, 1]$ since the other two weak tractabiliies can be deduced similarly. Thus, it suffices to show that (3.11) implies $(\sigma, \tau)$-WT with $\sigma \in (0, 1]$. Indeed, we observe from (3.12) that

where we used that $\ln(1+x) \le x$ for all $x \ge 0$. Thus (3.11) implies

Following the proof of [3, Theorem 26.11], we can obtain $(\sigma, \tau)$-WT with $\sigma \in (0, 1]$ for $\Lambda^{\text{std}}$.

The proof is completed. □

4.   Integration in $\mathcal{H}(K_R)$.

In this section, we investigate the tractability of integration operators defined on the weighted Korobov space $\mathcal{H}(K_R)$.} More precisely, we want to approximate the integral operators

in the worst-case setting. We approximate ${\rm INT}_d$ by means of linear algorithms $A_{n, d}^{{\rm int}}$ of the form

with nodes ${\bf x}_1, \ldots, {\bf x}_n \in [0, 1]^d$ and integration weights $\lambda_1, \ldots, \lambda_n \in \mathbb{R}$.

The $n$-th minimal error for integration in $\mathcal{H}(K_R)$ is defined as

where the infimum is taken over all algorithms of the form (4.1). For $n = 0$, the initial integration error is given by

In the following, we assume that $R(\boldsymbol0) = 1$, which leads to the norm of ${\rm INT}_d$ is $1$, since

and the upper bound can be attained by choosing $f = 1$. Therefore, there is no need to distinguish between ABS and NOR. For abbreviation, we write $n(\varepsilon, {\rm INT}_d, \mathcal{H}(K_R))\equiv n^{X}(\varepsilon, {\rm INT}_d, \mathcal{H}(K_R))$.

Obviously, we have

which implies

Now we formulate our result of the tractability of integration ${\rm INT}$ in the weighted Korobov space $\mathcal{H}(K_R)$ for $R\in \{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$.

Theorem 3. Let $\boldsymbol\alpha = \{\alpha_j\}_{j \in\mathbb N}$ be the smoothness parameter sequence satisfying (2.4), and let $\boldsymbol\gamma = \{\gamma_j\}_{j \in\mathbb N}$ be the weight sequence satisfying (2.5). Consider the integration problem ${\rm INT} = \{{\rm INT}_d\}_{d \in\mathbb N}$ for the weighted spaces $\mathcal{H}(K_R)$, $R\in \{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$. Then we have the following conditions:

(i) SPT holds iff

(which is equivalent to $s_{\boldsymbol\gamma} \le 1$). In this case the exponent of SPT satisfies

(ii) PT, QPT are equivalent and hold iff

(iii) WT holds iff

(iv) UWT holds iff

(v) For $\sigma\in (0, 1]$ $(\sigma, \tau)$-WT holds iff

For $\sigma > 1$, $(\sigma, \tau)$-WT always holds.

To verify Theorem 3, we shall give the lower bound of the $n$-th minimal error for INT in $\mathcal{H}(K_R)$. we will employ the subsequent proposition and lemma.

Proposition 3 (^[15]). For $j = 1, \dots, d$, let $\beta_j\in(0, 1]$ and let $H_j$ be a reproducing kernel space on $[0, 1]$ such that $(1, \beta_j\cos(2\pi x), \beta_j\sin(2\pi x))$ are orthonormal in $H_j$. Consider the integration problem ${\rm INT}$ for $f\in{\bf H}_d = H_1\otimes\dots\otimes H_d$. We have

Lemma 4. Let $\boldsymbol\alpha = \{\alpha_j\}_{j \in\mathbb N}$ be the smoothness parameter sequence satisfying (2.4), and let $\boldsymbol\gamma = \{\gamma_j\}_{j \in\mathbb N}$ be the weight sequence satisfying (2.5). Set $R\in\{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$. Then, for all $n \in \mathbb{N}$,

Proof. This can be deduced from Remark 2, (2.9), and the definition of the $n$-th minimal error for integration. □

Applying Proposition 3 and Lemma 4 to the weighted space $\mathcal{H}(K_{r_{d, \boldsymbol\alpha, \boldsymbol\gamma/3}})$, we obtain the lower bound of $e(n, {\rm INT}_d, \mathcal{H}(K_R))$ for $R\in \{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$.

Lemma 5. Let $\boldsymbol\alpha = \{\alpha_j\}_{j \in\mathbb N}$ be the smoothness parameter sequence satisfying (2.4), and let $\boldsymbol\gamma = \{\gamma_j\}_{j \in\mathbb N}$ be the weight sequence. Set $R\in \{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$. Then we have

This implies that for all $\varepsilon\in(0, 1)$,

Proof. Clearly, the weighted Korobov space $\mathcal{H}(K_{r_{d, \boldsymbol\alpha, \boldsymbol\gamma/3}})$ satisfies the conditions of Proposition 3 with $\beta_j = \sqrt{\gamma_j/3}$, $j = 1, \dots, d$, which, by Proposition 3 and Lemma 4, implies that for $R\in \{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}, \omega_{d, \boldsymbol\alpha, \boldsymbol\gamma}\}$,

which gives (4.3). For all $\varepsilon\in(0, 1)$, letting $e(n, {\rm INT}_d, \mathcal{H}(K_R))\le \varepsilon$, we will obtain (4.4). This completes the proof. □

Remark 4. We remark that for $R\in\{{r_{d, \boldsymbol\alpha, \boldsymbol\gamma}}, {\psi_{d, \boldsymbol\alpha, \boldsymbol\gamma}}\}$, the constant $1/3$ in (4.3) and (4.4) can be replaced by $1$. That is,

and for all $\varepsilon\in(0, 1)$,

Now we turn to give the proof of Theorem 3.

Proof of Theorem 3. According to (4.2), we know that the sufficient condition on the tractability of the $L_2$-approximation problem for $\Lambda^{{\rm std}}$ also works for the integration problem in $\mathcal{H}(K_R)$. Therefore, we only need to verify the necessary conditions.

First, we assert that $\lim_{j \rightarrow \infty} \gamma_j = 0$. If it does not hold, there would exist a constant $\gamma_* > 0$ such that $\gamma_j \geq \gamma_* > 0$ for every $j \in \mathbb{N}$. According to Lemma 5, it can be derived that

Thus $n(\varepsilon, {\rm INT}_d, \mathcal{H}(K_R))$ grows exponentially fast in $d$, which implies that ${\rm INT}$ suffers from the curse of dimensionality. This proves our claim.

Now we assume that $\sum_{j = 1}^{\infty}\gamma_j = \infty$. Then we can derive from $\lim_{j \rightarrow \infty}\gamma_j = 0$ and the inequality $x\ln 2\le \ln(1+x)\le x, x\in[0, 1]$ that^†

^†Here, $A_d = \Theta(B_d)$ means that there exsits a constant $C > 0$ independent of $d$ such that $C^{-1}B_d\le A_d\le CB_d$.

Then it follows from (4.4) and (4.5) that

which implies that ${\rm INT}$ cannot be SPT. Thus $\sum_{j = 1}^{\infty}\gamma_j < \infty$ is necessary for SPT.

Next assume that $\limsup_{d\rightarrow \infty} \frac1{\ln d} \sum_{j = 1}^d \gamma_j = \infty$. Then we can derive from $\lim_{j \rightarrow \infty}\gamma_j = 0$ that

Combining with (4.4), we obtain that $n(\varepsilon, {\rm INT}_d, \mathcal{H}(K_R))$ goes to infinity faster than any power of $d$, and ${\rm INT}$ cannot be PT. Thus, $\limsup_{d \rightarrow \infty} \frac1{\ln d} \sum_{j = 1}^d\gamma_j < \infty$ is necessary for PT.

Finally, assume that

Then we can derive from (4.4) and (4.5) that

This implies the condition is necessary for the three WT notions.

The proof is completed. □

5.   Concluding remarks

This paper gives a complete picture of the tractability of multivariate $L_2$-approximation for both $\Lambda^{\rm all}$ and $\Lambda^{\rm std}$, and multivariate integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. According to the results in ^[16], the corresponding tractability conditions of $L_2$-approximation in the randomized case setting are the same as in the worst-case setting. Moreover, our results may be helpful to study the tractability of nonhomogeneous tensor product spaces.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Conflict of interest

The authors declare there is no conflict of interest.