Liberating the dimension for function approximation

We study approximation of functions that may depend on infinitely many variables. We assume that such functions belong to a separable weighted Hilbert space that is the direct sum of tensor product Hilbert spaces of functions with finitely many variables. The weight sequence γ={γu} is used to moderate the influence of terms depending on finitely many variables from u. We consider algorithms that use finitely many arbitrary linear functionals. Each linear functional is an inner product whose cost depends on the number of active variables of the inner product generator. That is, if the generator has d active variables then the cost is $(d) for a given non-decreasing function $. The error of an algorithm is defined in the worst case setting in a norm given by weighted L2 norms for terms depending on finitely many variables. The ε-complexity is understood as the minimal cost among all algorithms with errors at most ε. We are especially interested in polynomial tractability, where the ε-complexity is bounded by a polynomial in ε−1, and weak tractability, where the ε-complexity is sub-exponential in ε−1. The results are as follows.