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

We study the tractability of ωω-weighted LsLs approximation for γγ-weighted Banach spaces of ∞∞-variate functions with mixed partial derivatives of order rr bounded in a ψψ-weighted LpLp norm. Functions from such spaces have a natural decomposition f=∑ufuf=∑ufu, where the summation is with respect to finite subsets u⊂N+u⊂N+ and each fufu depends only on variables listed in uu. 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 dd variables is at most exponential in dd 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))ε−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.