In this dissertation we study the information-based complexity for high-dimensional function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance the complexity grows exponentially with the dimension. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the uniform approximation of certain classes of smooth functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the uniform approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, whereas with randomized methods we achieve polynomial tractability. Chapter 4 deals with the approximation of monotone functions via function values. It is known that this problem suffers from the curse of dimensionality in the deterministic setting. A new upper bound shows that Monte Carlo methods do break the curse. Almost matching lower bounds are found as well, from which follows that randomization will not help significantly for small error tolerances.
Gegenstand dieser Dissertation ist die Informationskomplexität der Approximation hochdimensionaler Funktionen. Im deterministischen Fall unterliegen viele Probleme dem Fluch der Dimension, d.h. bei fester Fehlertoleranz wächst die Komplexität exponentiell mit der Dimension. Bei Integrationsproblemen kann man normalerweise dem Fluch mit der Standard Monte-Carlo-Methode begegnen. Für Funktionsapproximation waren vergleichbare Effekte von Randomisierung bisher unbekannt. Die Arbeit enthält Ergebnisse in drei mehr oder weniger für sich stehenden Kapiteln. Kapitel 2 behandelt untere Schranken für den Monte-Carlo-Fehler für allgemeine lineare Probleme mittels Bernstein-Zahlen. Dieses Relationen werden schließlich auf das Problem der gleichförmigen Approximation von gewissen Klassen analytischer Funktionen angewandt, wobei sich zeigt, dass Randomisierung in jenen Fällen die Komplexität nicht wesentlich verbessern kann. Kapitel 3 ist der gleichmäßigen Approximation von Hilbert-Raum-Funktionen gewidmet, wobei beliebige lineare Funktionale zur Informationsgewinnung zugelassen sind. Für gewisse ungewichtete periodische Tensorprodukträume, insbesondere Korobov-Räume, beobachten wir den Fluch der Dimension für deterministische Methoden, während im randomisierten Fall nur noch eine polynomielle Komplexität vorliegt. In Kapitel 4 wird die Approximation monotoner Funktionen mittels Funktionswerten untersucht. Der Fluch der Dimension ist im deterministischen bekannt. Eine neue obere Monte-Carlo-Schranke zeigt, dass Randomisierung den Fluch bricht. Dazu werden passende untere Schranken gezeigt, aus denen aber auch folgt, dass Randomisierung für kleine Fehlertoleranzen nicht mehr viel bringt. Die Arbeit ist in englischer Sprache abgefasst.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten