"The difficulty of Monte Carlo approximation of multivariate monotone functions"
Kunsch, Robert J.We study the approximation of multivariate monotone functions based on information from function evaluations. It is known that this problem suffers from the curse of dimensionality in the deterministic setting, that is, the number of function evaluations needed in order to approximate an unknown monotone function within a given error threshold grows at least exponentially in the dimension. This is not the case in the randomized setting (Monte Carlo setting) where the complexity grows exponentially in the square-root of the dimension (modulo logarithmic terms) only. An algorithm exhibiting this complexity is presented. The algorithm is based on the Haar wavelet decomposition of monotone functions. Still, the problem remains difficult as best known methods are deterministic if the error threshold is comparably small. This inherent difficulty is confirmed by lower complexity bounds from which we deduce that the problem is not weakly tractable.