Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods

Autor(en): Kunsch, Robert J.
Stichwörter: COMPLEXITY; Computer Science; Computer Science, Theory & Methods; Curse of dimensionality; Hilbert spaces; INFORMATION; Information-based complexity; Linear information; Mathematics; Mathematics, Applied; Monte Carlo approximation; Polynomial tractability
Erscheinungsdatum: 2018
Herausgeber: ACADEMIC PRESS INC ELSEVIER SCIENCE
Journal: JOURNAL OF COMPLEXITY
Volumen: 48
Startseite: 15
Seitenende: 35
Zusammenfassung: 
We study the L-infinity-approximation of d-variate functions from Hilbert spaces via linear functionals as information. It is a common phenomenon in tractability studies that unweighted problems (with each dimension being equally important) suffer from the curse of dimensionality in the deterministic setting, that is, the number n(epsilon, d) of information needed in order to solve a problem within a given accuracy epsilon > 0 grows exponentially in d. We show that for certain approximation problems in periodic tensor product spaces, in particular Korobov spaces with smoothness r > 1/2, switching to the randomized setting can break the curse of dimensionality, now having polynomial tractability, namely n(epsilon, d) <= epsilon(-2) d (1 log d). Similar benefits from Monte Carlo methods in terms of tractability have only been known for integration problems so far. (C) 2018 Elsevier Inc. All rights reserved.
ISSN: 0885064X
DOI: 10.1016/j.jco.2018.04.002

Show full item record

Page view(s)

1
Last Week
0
Last month
0
checked on May 21, 2024

Google ScholarTM

Check

Altmetric