Tractability of approximation of ∞-variate functions with bounded mixed partial derivatives

We study the tractability of ω-weighted ^Ls approximation for γ-weighted Banach spaces of ∞-variate functions with mixed partial derivatives of order r bounded in a ψ-weighted ^Lp norm. Functions from such spaces have a natural decomposition f=∑_u ^fu, where the summation is with respect to finite subsets u∩^N+ and each ^fu depends only on variables listed in u. We derive corresponding multivariate decomposition methods and show that they lead to polynomial tractability under suitable assumptions concerning γ weights as well as the probability density functions ω and ψ. For instance, suppose that the cost of evaluating functions with d variables is at most exponential in d and the weights γ decay to zero sufficiently quickly. Then the cost of approximating such functions with the error at most ε is proportional to ε-^{1/(r+min(1/s-1/p,0))} ignoring logarithmic terms. This is a nearly-optimal result, since (once again ignoring logarithmic terms) it equals the complexity of the same approximation problem in the univariate case.