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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references