Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2101.03665

On the power of standard information for tractability for $L_2$-approximation in the randomized setting

Wanting Lu, Heping Wang

Published Jan 11, 2021• 2 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.2101.03665

Related papers

On the power of standard information for tractability for $L_\infty$ approximation of periodic functions in the worst case setting

Jiaxin Geng, Heping Wang

We study multivariate approximation of periodic function in the worst case setting with the error measured in the $L_\infty$ norm. We consider algorithms that use standard information $Λ^{\rm std}$ consisting of function values or general linear information $Λ^{\rm all}$ consisting of arbitrary continuous linear functionals. We investigate the equivalences of various notions of algebraic and exponential tractability for $Λ^{\rm std}$ and $Λ^{\rm all}$ under the absolute or normalized error criterion, and show that the power of $Λ^{\rm std}$ is the same as the one of $Λ^{\rm all}$ for some notions of algebraic and exponential tractability. Our result can be applied to weighted Korobov spaces and Korobov spaces with exponential weight. This gives a special solution to Open problem 145 as posed by Novak and Woźniakowski (2012).

arXiv:2304.14748•Apr 28, 2023•0 citations

The power of standard information for multivariate approximation in the randomized setting

G.W. Wasilkowski, H. Woźniakowski

We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted $L_2$-norm. We consider functions with an arbitrarily large number of variables, $d$, and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points. We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the $n$th minimal errors, i.e., of the minimal errors among all algorithms using $n$ function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting. We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor $\varepsilon$ is polynomial in $\varepsilon ^{-1}$ (strong tractability), and polynomial in $d$ and $\varepsilon ^{-1}$ (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check. We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of $d$, we prove that strong tractability is equivalent to tractability. We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.

Mathematics of Computation•Dec 13, 2006•34 citations

Tractability of $\mathbb{L}_2$-approximation in hybrid function spaces

Peter Kritzer, Helene Laimer, Friedrich Pillichshammer

We consider multivariate $\mathbb{L}_2$-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error $e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)$ of all algorithms that use $N$ information evaluations from the class $Λ$ in the $d$-dimensional case. The two classes $Λ$ considered in this paper are the class $Λ^{\rm all}$ consisting of all linear functionals and the class $Λ^{\rm std}$ consisting only of function evaluations. The focus lies on the dependence of $e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)$ on the dimension $d$. The main results are conditions for weak, polynomial, and strong polynomial tractability.

arXiv:1701.02910•Jan 11, 2017•0 citations

Tractability of $\mathbb{L}_2$-approximation in hybrid function spaces

Peter Kritzer, Helene Laimer, Friedrich Pillichshammer

We consider multivariate $\mathbb{L}_2$-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error $e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)$ of all algorithms that use $N$ information evaluations from the class $\Lambda$ in the $d$-dimensional case. The two classes $\Lambda$ considered in this paper are the class $\Lambda^{{\rm all}}$ consisting of all linear functionals and the class $\Lambda^{{\rm std}}$ consisting only of function evaluations. The focus lies on the dependence of $e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)$ on the dimension $d$. The main results are conditions for weak, polynomial, and strong polynomial tractability.

Functiones et Approximatio Commentarii Mathematici•May 4, 2017•1 citation

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

Jia Chen, Huichao Yan

We study the multivariate L2-approximation problem APPd 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 α={αj}j∈N and β={βj}j∈N with 1<α1≤α2≤⋯ and 1≥β1≥β2≥⋯>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 L2-approximation problem APP={APPd}d∈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 dt and ε−s for large dimension d and small threshold ε. In particular, for all s>0 and t∈(0,1), we find the matching sufficient and necessary condition on the parameter sequences α={αj}j∈N and β={βj}j∈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.

Symmetry•Nov 14, 2024•0 citations

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

Weiran Ding, Jiansong Li, Yumeng Jia +1 more

This paper is devoted to the study of tractability of the $ L_2 $-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class $ \Lambda^{\rm all} $, including all continuous linear functionals, and from the class $ \Lambda^{\rm std} $, including function evaluations. Necessary and sufficient conditions on the weights of the function space for strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability, weak tractability and $ (\sigma, \tau) $-weak tractability, are provided. Our results give a comprehensive picture of the weight conditions for all standard notions of algebraic tractability. It may be helpful to study the tractability of nonhomogeneous tensor product spaces.

Electronic Research Archive•Jan 1, 2025•0 citations
On the power of standard information for tractability for L2L_2L2​-approximation in the randomized setting
We study approximation of multivariate functions from a separable Hilbert space in the randomized setting with the error measured in the weighted L2L_2L2​ norm. We consider algorithms that use standard information ΛstdΛ^{\rm std}Λstd consisting of function values or general linear information ΛallΛ^{\rm all}Λall consisting of arbitrary linear functionals. We use the weighted least squares regression algorithm to obtain the upper estimates of the minimal randomized error using ΛstdΛ^{\rm std}Λstd. We investigate the equivalences of various notions of algebraic and exponential tractability for ΛstdΛ^{\rm std}Λstd and ΛallΛ^{\rm all}Λall for the normalized or absolute error criterion. We show that in the randomized setting for the normalized or absolute error criterion, the power of ΛstdΛ^{\rm std}Λstd is the same as that of ΛallΛ^{\rm all}Λall for all notions of exponential and algebraic tractability without any condition. Specifically, we solve four Open Problems 98, 100-102 as posed by E.Novak and H.Woźniakowski in the book: Tractability of Multivariate Problems, Volume III: Standard Information for Operators, EMS Tracts in Mathematics, Zürich, 2012.
On the power of standard information for tractability for L∞L_\inftyL∞​ approximation of periodic functions in the worst case setting
We study multivariate approximation of periodic function in the worst case setting with the error measured in the L∞L_\inftyL∞​ norm. We consider algorithms that use standard information ΛstdΛ^{\rm std}Λstd consisting of function values or general linear information ΛallΛ^{\rm all}Λall consisting of arbitrary continuous linear functionals. We investigate the equivalences of various notions of algebraic and exponential tractability for ΛstdΛ^{\rm std}Λstd and ΛallΛ^{\rm all}Λall under the absolute or normalized error criterion, and show that the power of ΛstdΛ^{\rm std}Λstd is the same as the one of ΛallΛ^{\rm all}Λall for some notions of algebraic and exponential tractability. Our result can be applied to weighted Korobov spaces and Korobov spaces with exponential weight. This gives a special solution to Open problem 145 as posed by Novak and Woźniakowski (2012).
We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted L2L_2L2​-norm. We consider functions with an arbitrarily large number of variables, ddd, and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points. We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the nnnth minimal errors, i.e., of the minimal errors among all algorithms using nnn function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting. We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor ε\varepsilonε is polynomial in ε−1\varepsilon ^{-1}ε−1 (strong tractability), and polynomial in ddd and ε−1\varepsilon ^{-1}ε−1 (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check. We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of ddd, we prove that strong tractability is equivalent to tractability. We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.
Tractability of L2\mathbb{L}_2L2​-approximation in hybrid function spaces
We consider multivariate L2\mathbb{L}_2L2​-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)eL2​−app,Λ(N,d) of all algorithms that use NNN information evaluations from the class ΛΛΛ in the ddd-dimensional case. The two classes ΛΛΛ considered in this paper are the class ΛallΛ^{\rm all}Λall consisting of all linear functionals and the class ΛstdΛ^{\rm std}Λstd consisting only of function evaluations. The focus lies on the dependence of eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)eL2​−app,Λ(N,d) on the dimension ddd. The main results are conditions for weak, polynomial, and strong polynomial tractability.
Tractability of L2\mathbb{L}_2L2​-approximation in hybrid function spaces
We consider multivariate L2\mathbb{L}_2L2​-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)eL2​−app,Λ(N,d) of all algorithms that use NNN information evaluations from the class Λ\LambdaΛ in the ddd-dimensional case. The two classes Λ\LambdaΛ considered in this paper are the class Λall\Lambda^{{\rm all}}Λall consisting of all linear functionals and the class Λstd\Lambda^{{\rm std}}Λstd consisting only of function evaluations. The focus lies on the dependence of eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)eL2​−app,Λ(N,d) on the dimension ddd. The main results are conditions for weak, polynomial, and strong polynomial tractability.
We study the multivariate L2-approximation problem APPd 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 α={αj}j∈N and β={βj}j∈N with 1<α1≤α2≤⋯ and 1≥β1≥β2≥⋯>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 L2-approximation problem APP={APPd}d∈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 dt and ε−s for large dimension d and small threshold ε. In particular, for all s>0 and t∈(0,1), we find the matching sufficient and necessary condition on the parameter sequences α={αj}j∈N and β={βj}j∈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.
This paper is devoted to the study of tractability of the $ L_2 $-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class $ \Lambda^{\rm all} $, including all continuous linear functionals, and from the class $ \Lambda^{\rm std} $, including function evaluations. Necessary and sufficient conditions on the weights of the function space for strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability, weak tractability and $ (\sigma, \tau) $-weak tractability, are provided. Our results give a comprehensive picture of the weight conditions for all standard notions of algebraic tractability. It may be helpful to study the tractability of nonhomogeneous tensor product spaces.