The difficulty of Monte Carlo approximation of multivariate monotone functions

Autor(en): Kunsch, Robert J.
Stichwörter: Curse of dimensionality; Information-based complexity; Intractable; Mathematics; Monotone functions; Monte Carlo approximation; QUADRATURE-FORMULAS; Standard information
Erscheinungsdatum: 2019
Herausgeber: ACADEMIC PRESS INC ELSEVIER SCIENCE
Journal: JOURNAL OF APPROXIMATION THEORY
Volumen: 241
Startseite: 33
Seitenende: 56
Zusammenfassung: 
We study the L-1-approximation of d-variate monotone functions based on information from n function evaluations. It is known that this problem suffers from the curse of dimensionality in the deterministic setting, that is, the number n(epsilon, d) of function evaluations needed in order to approximate an unknown monotone function within a given error threshold epsilon grows at least exponentially in d. In the randomized setting (Monte Carlo setting) the complexity n(epsilon, d) grows exponentially in root d (modulo logarithmic terms) only. An algorithm exhibiting this complexity is presented. The problem remains difficult as best methods known are deterministic if epsilon is comparably small, namely epsilon <= 1 root d. This inherent difficulty is confirmed by lower complexity bounds which reveal a joint (epsilon, d)-dependence and from which we deduce that the problem is not weakly tractable. The lower bound proof also has implications on the complexity of learning Boolean monotone functions. (C) 2019 Elsevier Inc. All rights reserved.
ISSN: 00219045
DOI: 10.1016/j.jat.2019.01.003

Show full item record

Page view(s)

1
Last Week
0
Last month
0
checked on Feb 22, 2024

Google ScholarTM

Check

Altmetric