The difficulty of Monte Carlo approximation of multivariate monotone functions (Q1734615)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The difficulty of Monte Carlo approximation of multivariate monotone functions |
scientific article |
Statements
The difficulty of Monte Carlo approximation of multivariate monotone functions (English)
0 references
27 March 2019
0 references
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.
0 references
Monte Carlo approximation
0 references
monotone functions
0 references
information-based complexity
0 references
standard information
0 references
intractable
0 references
curse of dimensionality
0 references
0 references