The difficulty of Monte Carlo approximation of multivariate monotone functions (Q1734615)

The paper considers the $L_1$-approximation of $d$-variate monotone functions based on information from $n$ function evaluations. Based on a decomposition of the function into tensorized Haar wavelets, the author presents an algorithm for the approximation of monotone functions on the unit cube, demonstrating that Monte Carlo reduces the dimension dependence of the complexity compared to deterministic methods. A lower bound is established which implies that the problem is not weakly tractable in the randomized setting.