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

DC FieldValueLanguage
dc.contributor.authorKunsch, Robert J.
dc.date.accessioned2021-12-23T16:01:34Z-
dc.date.available2021-12-23T16:01:34Z-
dc.date.issued2018
dc.identifier.issn0885064X
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/5040-
dc.description.abstractWe 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.
dc.description.sponsorshipDFG Research Training Group 1523; This paper is based on a chapter of the author's Ph.D. thesis [17], which has been financially supported by the DFG Research Training Group 1523. I wish to express my deepest gratitude to my Ph.D. supervisor Erich Novak for many valuable hints during my work on these results. I also wish to thank my colleagues David Krieg and Van Kien Nguyen for making me aware of the situations which have been discussed in Section 3.4.
dc.language.isoen
dc.publisherACADEMIC PRESS INC ELSEVIER SCIENCE
dc.relation.ispartofJOURNAL OF COMPLEXITY
dc.subjectCOMPLEXITY
dc.subjectComputer Science
dc.subjectComputer Science, Theory & Methods
dc.subjectCurse of dimensionality
dc.subjectHilbert spaces
dc.subjectINFORMATION
dc.subjectInformation-based complexity
dc.subjectLinear information
dc.subjectMathematics
dc.subjectMathematics, Applied
dc.subjectMonte Carlo approximation
dc.subjectPolynomial tractability
dc.titleBreaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods
dc.typejournal article
dc.identifier.doi10.1016/j.jco.2018.04.002
dc.identifier.isiISI:000441689300002
dc.description.volume48
dc.description.startpage15
dc.description.endpage35
dc.contributor.orcid0000-0003-0835-9870
dc.identifier.eissn10902708
dc.publisher.place525 B ST, STE 1900, SAN DIEGO, CA 92101-4495 USA
dcterms.isPartOf.abbreviationJ. Complex.
dcterms.oaStatusGreen Submitted
Show simple item record

Page view(s)

1
Last Week
0
Last month
0
checked on Apr 14, 2024

Google ScholarTM

Check

Altmetric