Hauptinhalt

Topinformationen

SS 2023

07.06.2023 um 17:15 Uhr in Raum 69/125

Prof. Dr. Michael Gnewuch (Universität Osnabrück)

High-Dimensional Integration and Approximation: Randomized Algorithms and
Their Analysis

Consider an integration or a function recovery problem where the input functions depend on a very large or even infinite number of variables and belong to some reproducing kernel Hilbert space. The following questions arise naturally:

1. What kind of structure of the functions or of the function space, respectively, avoids the curse of dimensionality and ensures that the problem is computationally tractable?

2. What kind of algorithms give us almost optimal convergence rates?

3. How does their analysis depend on the specific function space and its norm? In this talk we want to discuss these questions in the setting where we are allowed to use randomized algorithms, where the error criterion is given by the randomized worst-case error (i.e., the worst-case root mean square error over the norm unit ball of the function space), and where the cost of evaluating a function in some point x depends in a reasonable way on the number of “active variables” of x. In the course of the talk, we will see that the questions above may be answered in the following way:

Helpful concepts to lift the curse of dimensionality are tensor product spaces, weights that moderate the importance of different groups of variables or increasing smoothness of the input functions (where “increasing” is meant with respect to the ordered variables). Depending on the chosen cost model, multilevel algorithms or multivariate decomposition methods, based on good building block algorithms that take care of lower dimensional sub- problems, may achieve convergence rates arbitrarily close to the optimal order. Furthermore, we want to present an elaborate framework for the embedding of different (scales of) Hilbert spaces, which enables us to transfer tractability results from specific Hilbert spaces to larger classes of spaces.