A note about exponential tractability of linear weighted tensor product problems in the worst-case setting
Zirong Liu, Heping Wang, Kai Wang · 2026
Read A note about exponential tractability of linear weighted tensor product problems in the worst-case setting by Zirong Liu, Heping Wang, Kai Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21007.txt.
Introduction
Liu and co-authors settle open questions on exponential tractability for linear weighted tensor product problems. They study algorithms that use finitely many evaluations of continuous linear functionals, in the worst case setting. They examine two forms of exponential weak tractability, under absolute or normalized error. By filling the remaining gaps, they obtain necessary and sufficient conditions for both notions. The results complete the picture of when such problems stay tractable at an exponential scale.
Catalog record
| CREATOR | Zirong Liu, Heping Wang, Kai Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44700 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.21007
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A note about exponential tractability of linear weighted tensor product problems in the worst-case setting Zirong Liu, Heping Wang, Kai Wang Abstract . This paper is devoted to discussing the weighted linear tensor product problems in the worst case setting. We consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We investigate exponential ( s , t ) (s,t) -weak tractability (EXP- ( s , t ) (s,t) -WT) with max ( s , t ) < 1 \max(s,t)<1 and exponential uniform weak tractability (EXP-UWT) under the absolute or normalized error criterion. We solve the problem by filling the remaining gaps left open on EXP-tractability. That is, we obtain necessary and sufficient conditions for EXP- ( s , t ) (s,t) -WT with max ( s , t ) < 1 \max(s,t)<1 and for EXP-UWT. 1. Introduction and main results We study d -variate linear problem S=\{S_{d}\}_{d\in{N}} , where S_{d} is a linear operator from a Banach function space H_{d} into another Banach function space G_{d} , d may be large even huge. We consider algorithms that use finitely many continuous linear functionals on H_{d} . The information complexity n(\varepsilon,S_{d}) is defined to be the minimal number of linear functionals needed to find an approximation of S_{d} to within an error threshold \varepsilon . Tractability is the study of how information complexity n(\varepsilon,S_{d}) depends on \varepsilon and d . There are two kinds of tractability based on polynomial convergence and exponential convergence. The algebraic tractability (ALG-tractability) describes how n(\varepsilon,d) behaves as a function of d and \varepsilon^{-1} , while the EXP-tractability does as one of d and (1+\ln\varepsilon^{-1}) . Recently the study of ALG-tractability and EXP-tractability has attracted much interest, and a great number of interesting results have been obtained (see [ 1 , 3 , 4 , 5 , 7 , 8 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 ] and the references therein). This paper is devoted to discussing EXP-tractability of linear weighted tensor product problems in the worst case setting. For unweighted linear tensor product problems, the results about the EXP-tractability were obtained in [ 6 , 13 , 14 ] . However, there are many negative results for exponential tractability. Hence the authors in [ 9 ] introduced weighted linear tensor product problems and obtained necessary and sufficient conditions for various notions of EXP-tractability on weights and univariate singular values. Note that in [ 9 ] the cases of EXP- (s,t) -weak tractability (EXP- (s,t) -WT) with \max(s,t)<1 and EXP-uniform weak tractability (EXP-UWT) were left open. In this paper we investigate EXP- (s,t) -WT with \max(s,t)<1 and EXP-UWT for the above weighted linear tensor product problems. We solve the problem by filling the remaining gaps left open on EXP-tractability. That is, we obtain necessary and sufficient conditions for EXP- (s,t) -WT with \max(s,t)<1 and EXP-UWT. 1.1. Weighted linear tensor product problems. Let H_{1} be a separable infinite-dimensional Hilbert space with inner product \langle\cdot,\cdot\rangle_{H_{1}} . We consider a compact linear operator S_{1}:H_{1}\to G_{1} , where G_{1} is also a Hilbert space. Then W_{1}:=S_{1}^{*}S_{1}:H_{1}\to H_{1} is a compact self-adjoint non-negative operator, where T^{*} is the adjoint operator of a linear operator T . Let \{(\lambda_{j},e_{j})\}_{j\in{N}} denote the eigenpairs of W_{1} , that is, W_{1}e_{j}=\lambda_{j}e_{j},\ e_{j}\in H_{1},\ \ \lambda_{1}\geq\lambda_{2}\geq\dots\geq 0, and \{e_{j}\}_{j\in{N}} is an orthonormal basis in H_{1} . Without loss of generality we assume that \lambda_{1}=1 and \lambda_{2}>0 in the sequel. Due to compactness of S_{1} we have \lim\limits_{j\to\infty}\lambda_{j}=0 . Denote H_{1,0}={\rm span}\,\{e_{1}\},\ \ H_{1,1}=H_{1,0}^{\bot}. Then H_{1}=H_{1,0}\oplus H_{1,1}. Hence for each f\in H_{1} , we have the unique orthogonal decomposition f=f_{0}+f_{1} , where f_{0}\in H_{1,0},\ f_{1}\in H_{1,1} . For \gamma>0 , we define the weighted Hilbert space H_{1,\gamma} to be the Hilbert space H_{1} with inner product \langle f,g\rangle_{H_{1,\gamma}}:=\langle f_{0},g_{0}\rangle_{H_{1}}+\gamma^{-1}\langle f_{1},g_{1}\rangle_{H_{1}}. And the weighted operator S_{1,\gamma} is defined to be the operator S_{1} from the weighted Hilbert space H_{1,\gamma} to G_{1} . It follows that the operator W_{1,\gamma}=S_{1,\gamma}^{*}S_{1,\gamma}:H_{1,\gamma}\to H_{1,\gamma} is a compact linear operator and the eigenpairs of the operator W_{1,\gamma} are \{(\lambda_{\gamma,j},e_{j})\}_{j\in{N}} , where (1.1) \lambda_{\gamma,j}=\left\{\begin{array}[]{ll}1,&\mbox{ if }j=1,\\ \gamma\lambda_{j},&\mbox{ if }j\geq 2.\end{array}\right. Let \boldsymbol{\gamma}=\{\gamma_{j}\}_{j\in{\mathbb{N}}} be a sequence of non-increasing positive reals, which we refer to as weights in the following. For simplicity we assume that \gamma_{j}\in(0,1] . For d\in{N} , the tensor product spaces H_{d,\boldsymbol{\gamma}} and G_{d} are denoted by H_{d,\boldsymbol{\gamma}}=H_{1,\gamma_{1}}\otimes H_{1,\gamma_{2}}\otimes\dots\otimes H_{1,\gamma_{d}},\ \ G_{d}=G_{1}\otimes\dots\otimes G_{1}, respectively, the tensor product operator S_{d,\boldsymbol{\gamma}}:H_{d,\boldsymbol{\gamma}}\to G_{d} is represented by S_{d,\boldsymbol{\gamma}}=S_{1,\gamma_{1}}\otimes\dots\otimes S_{1,\gamma_{d}}. Clearly, W_{d,\boldsymbol{\gamma}}:=S_{d,\boldsymbol{\gamma}}^{*}S_{d,\boldsymbol{\gamma}}:H_{d,\boldsymbol{\gamma}}\to H_{d,\boldsymbol{\gamma}} is a compact linear operator and the eigenpairs of W_{d,\boldsymbol{\gamma}} are \{(\lambda_{d,\boldsymbol{\gamma},{\bf j}},e_{{\bf j}})\}_{{\bf j}\in{N}^{d}} , where \lambda_{d,\boldsymbol{\gamma},{\bf j}}=\prod_{k=1}^{d}\lambda_{k,j_{k}},\ \ \ \ e_{{\bf j}}=e_{j_{1}}\otimes\cdots\otimes e_{j_{d}}. \lambda_{k,j_{k}}:=\lambda_{\gamma_{k},j_{k}} is defined as in ( 1.1 ). In the following, we write [d]:=\{1,2,\cdots,d\}. For {\bf j}=(j_{1},\cdots,j_{d})\in{\mathbb{N}}^{d} , define \mathfrak{u}({\bf j}):=\{k\in[d]:j_{k}\geq 2\}\ \ \ \mbox{ and }\ \ \ \lambda_{d,{\bf j}}:=\lambda_{j_{1}}\lambda_{j_{2}}\cdots\lambda_{j_{d}}. The eigenvalues of W_{d,\boldsymbol{\gamma}} can also be written as \lambda_{d,\boldsymbol{\gamma},{\bf j}}:=\gamma_{\mathfrak{u}({\bf j})}\lambda_{d,{\bf j}}=\left(\prod_{k=1\atop j_{k}\geq 2}^{d}\gamma_{k}\right)\lambda_{j_{1}}\cdots\lambda_{j_{d}}=\left(\prod_{k\in\mathfrak{u}({\bf j})}\gamma_{k}\right)\lambda_{d,{\bf j}}. See [ 10 , Section 5.3] or [ 9 ] . If \gamma_{j}\equiv 1 , the weighted tensor product space H_{d,\boldsymbol{\gamma}} recedes to the tensor product space H_{d}=H_{1}\otimes\cdots\otimes H_{1} , and the weighted linear tensor product operator S_{d,\boldsymbol{\gamma}} reduces to the linear tensor product operator S_{d}=S_{1}\otimes\cdots\otimes S_{1} . Now consider the linear weighted tensor product problem S_{\boldsymbol{\gamma}}=\{S_{d,\boldsymbol{\gamma}}\}_{d\in{\mathbb{N}}} . We want to approximate S_{d,\boldsymbol{\gamma}} by algorithms A_{d,n}(f) of the form (1.2) A_{d,n}(f)=\phi_{d,n}(L_{1}(f),L_{2}(f),\cdots,L_{n}(f)), where L_{1},\cdots,L_{n} belong to \Lambda_{d}^{\rm all}=H_{d,\boldsymbol{\gamma}}^{*} , the space consisting of all continuous linear functionals on H_{d,\boldsymbol{\gamma}} , and \phi_{d,n}:\mathbb{R}^{n}\to G_{d} is an arbitrary mapping. The choice of L_{j} can be adaptive, i.e., it may depend on the previously computed information L_{1}(f),L_{2}(f),\cdots,L_{j-1}(f) . The worst case error of an algorithm A_{d,n} is defined as e(A_{d,n})=\sup_{f\in H_{d,\boldsymbol{\gamma}}\atop\|f\|_{H_{d,\boldsymbol{\gamma}}}\leq 1}\|S_{d,\boldsymbol{\gamma}}(f)-A_{d,n}(f)\|_{G_{d}}. The n -th minimal worst-case error is defined by e(n,S_{d,\boldsymbol{\gamma}})=\inf_{A_{d,n}}e(A_{d,n}), where the infimum is taken over all algorithms of the form ( 1.2 ). When n=0 , the initial error e_{0} is denoted by e_{0}=\sup_{f\in H_{d,\boldsymbol{\gamma}}\atop\|f\|_{H_{d,\boldsymbol{\gamma}}}\leq 1}\|S_{d,\boldsymbol{\gamma}}(f)\|_{G_{d}}. Clearly, we have e_{0}=\|S_{d,\boldsymbol{\gamma}}\|=\|W_{d,\boldsymbol{\gamma}}\|^{1/2}=\max_{{\bf j}\in{\mathbb{N}}^{d}}(\lambda_{d,\boldsymbol{\gamma},{\bf j}})^{1/2}=1. Hence, the problem is well normalized for all d\in{\mathbb{N}} and all product weights \boldsymbol{\gamma} . The information complexity for the normalized or absolute error criterion is defined by n(\varepsilon,S_{d,\boldsymbol{\gamma}})=\min\{n\,:\,e(n,S_{d,\boldsymbol{\gamma}})\leq\varepsilon\}. It is known that for the class \Lambda_{d}^{\rm all} the information complexity is fully characterized in terms of the singular values of S_{d,\boldsymbol{\gamma}} , or equivalently, in terms of the eigenvalues of W_{d,\boldsymbol{\gamma}}=S_{d,\boldsymbol{\gamma}}^{*}S_{d,\boldsymbol{\gamma}} (see [ 10 ] ). Denote A_{\varepsilon,d}=\{(n_{1},\ldots,n_{d})\in{\mathbb{N}}^{d}:\lambda_{1,n_{1}}\cdots\lambda_{d,n_{d}}>\varepsilon^{2}\}. Then the information complexity can be rewritten as (1.3) n(\varepsilon,S_{d,\boldsymbol{\gamma}})=\bigg|\Big\{{\bf j}\in{\mathbb{N}}^{d}:\lambda_{d,\boldsymbol{\gamma},{\bf j}}=\prod_{k=1}^{d}\lambda_{k,j_{k}}=\lambda_{1,j_{1}}\cdots\lambda_{d,j_{d}}>\varepsilon^{2}\Big\}\bigg|=\big|A_{\varepsilon,d}\big|, where |A| denotes the number of the elements in a set A . Clearly, n(\varepsilon,S_{d,\boldsymbol{\gamma}})\leq n(\varepsilon_{1},S_{d_{1},\boldsymbol{\gamma}})\ \ \ \mbox{for all $\varepsilon_{1}\leq\varepsilon$ and $d_{1}\geq d$}. Hence, for decreasing \varepsilon and increasing d , the information complexity is non-increasing. 1.2. Various notions of EXP-tractability In this subsection we briefly recall the basic EXP-tractability notions. We are interested in the behavior of n(\varepsilon,S_{d,\boldsymbol{\gamma}}) when d+\ln\varepsilon^{-1} goes to infinity in an arbitrary way. We define various notions of EXP tractability. The problem S_{\boldsymbol{\gamma}}=\{S_{d,\boldsymbol{\gamma}}\} is said to be: • Exponentially strongly polynomially tractable (EXP-SPT) if there exist C,p\geq 0 such that (1.4) n(\varepsilon,S_{d,\boldsymbol{\gamma}})\leq C(1+\ln\varepsilon^{-1})^{p},\ \ \ \ \forall d\in{\mathbb{N}},\ \forall\varepsilon\in(0,1]. The infimum of all exponents p\geq 0 such that ( 1.4 ) holds for some C\geq 0 is called the