TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 23351

Algorithms and Complexity for Continuous Problems

( Aug 27 – Sep 01, 2023 )

(Click in the middle of the image to enlarge)

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/23351

Organizers
  • Dmitriy Bilyk (University of Minnesota - Minneapolis, US)
  • Michael Gnewuch (Universität Osnabrück, DE)
  • Jan Vybíral (Czech Technical University - Prague, CZ)
  • Larisa Yaroslavtseva (Universität Graz, AT)

Contact

Shared Documents



Schedule

Summary

The goal of the Dagstuhl Seminar was to bring together researchers that work in various fields united by a common theme of complexity of continuous problems. In this context, complexity refers to the computational effort required to solve the problem approximately, up to a given error. For these, often high- or even infinite-dimensional, problems it is desirable to have theoretical bounds on the complexity as well as explicit constructions of (nearly) optimal algorithms. Their applications range over natural sciences, economics, statistics, engineering, computer science (including computer graphics, global optimization, and machine learning) and other areas of interest. The focus of the seminar was on the following highly interrelated topics:

Tractability analysis of high-dimensional problems. Tractability analysis has its roots in information-based complexity. It studies continuous problems, where the instances are typically d-variate functions. The focus is on how the problem complexity depends on the error tolerance and on d. Topics discussed during the seminar were the study of recent notions of tractability and of new problem settings.

Computational stochastics. The focus was on strong approximation and quadrature of stochastic differential equations (SDEs) with non-globally Lipschitz continuous coefficients. Systematic investigations on the numerical approximation of such SDEs have started in the last decade and are still in their infancy.

Infinite-variate problems: algorithms and complexity. Many applications rely on models with countably many variables. The complexity analysis of the resulting continuous problems may be viewed as the limit of tractability analysis for d-variate functions, where d tends to infinity. For many problems sharp complexity bounds have been proved with the help of generic types of algorithms, as multilevel algorithms and multivariate decomposition methods, but mainly in the case where the spaces of input functions are weighted reproducing kernel Hilbert spaces (RKHSs) based on product weights or RKHSs of increasing smoothness. A major question was how to tackle important function spaces, which exhibit a different underlying structure.

Well-distributed point configurations: discrepancy, quasi-Monte Carlo methods, dispersion. Many problems in approximation theory and complexity rely on the existence and construction of good (random or deterministic) point distributions with respect to discrepancy, integration errors, strength of cubature formulas, dispersion, or discrete energy. Numerous questions in this area are still open: in various regimes sharp bounds for discrepancy and dispersion still remain unknown and explicit efficient constructions are still lacking. These problems were intensely discussed during the seminar.

Linear and standard information in approximation theory. A classical problem of approximation theory, learning theory and data analysis is the approximation of an unknown multivariate function from incomplete information. The information can be given by a limited number of function evaluations (standard information) or by evaluating a finite number of arbitrary linear functionals (linear information). Even in the simplest setting of approximation in a norm of a Hilbert space, the relation between using standard information and linear information was understood only recently and there is still a number of challenging open questions in this area. In several seminar talks interesting ideas to tackle these questions and new results were presented.

During the seminar we had five overview talks of 60 minutes (incl. discussion; one for each of the main research topics) given by leading experts in the respective area to enable reseachers from different fields to follow the regular talks. The speakers and the titles of these lectures were (ordered according to the list of main research topics):

  1. Peter Kritzer (RICAM Linz), Tractability analysis.
  2. Thomas Müller-Gronbach (Unversität Passau), On the complexity of strong approximation of SDEs with a non-Lipschitz drift coefficient.
  3. Klaus Ritter (RPTU Kaiserslautern-Landau), Infinite-variate integration and L2-approximation.
  4. Stefan Steinerberger (University of Washington – Seattle), Well-distributed point configurations.
  5. Mario Ullrich (JKU Linz), On optimal approximation based on random samples.

These talks were delivered at the first three days of the seminar. Additionally, we had 24 regular talks of 30 minutes (incl. discussion), many of them presented by young researchers. Due to the time format, there was plenty of time for discussions and collaborations in smaller groups.

Originally we planned an additional poster session for the participants who do not present a talk. Since finally the number of time slots for talks was sufficient to ensure that everyone who wanted to present a talk could actually do so, there was no need for a poster session anymore.

On Wednesday morning we had a problem session to share interesting open problems and conjectures and to initiate further discussions. Several researchers used the opportunity to present interesting and challenging open problems.

One problem was even solved in a discussion of some participants directly after the problem session. The detailed problem formulations can be found at the end of the full report.
Copyright Michael Gnewuch,,Dmitriy Bilyk, Jan Vybíral, and Larisa Yaroslavtseva

Motivation

The goal of this Dagstuhl Seminar is to bring together researchers that work in various fields united by a common theme of complexity of continuous problems. In this context, complexity refers to the computational effort required to solve the problem approximately, up to a given error. For these, often high- or even infinite-dimensional, problems it is desirable to have theoretical bounds on the complexity as well as explicit constructions of (nearly) optimal algorithms. Their applications range over natural sciences, economics, statistics, engineering, computer science (including computer graphics, global optimization, and machine learning) and other areas of interest. The seminar covers the following highly interrelated topics:

Tractability analysis of high-dimensional problems: Tractability analysis has its roots in information-based complexity. It studies continuous problems, where the instances are typically d-variate functions. The focus is on how the problem complexity depends on the error tolerance and on d. Major topics will be the study of recent notions of tractability and of worst-case errors over non-convex and unbounded domains.

Computational stochastics: We focus on strong approximation and quadrature of stochastic differential equations (SDEs) with non-globally Lipschitz continuous coefficients. Systematic investigations on the numerical approximation of such SDEs have started in the last decade and are still in their infancy. Major topics will be complexity analysis and the potential of adaptive strategies.

Infinite-variate problems: algorithms and complexity: Many applications rely on models with countably many variables. The complexity analysis of the resulting continuous problems may be viewed as the limit of tractability analysis for d-variate functions, where d tends to infinity. For many problems sharp complexity bounds have been proved with the help of generic types of algorithms, as multilevel algorithms and multivariate decomposition methods, but mainly in the case where the spaces of input functions are weighted reproducing kernel Hilbert spaces (RKHSs) based on product weights or RKHSs of increasing smoothness. A major topic will be the analysis of more general function spaces as, e.g., general weighted RKHSs or reproducing kernel Banach spaces.

Well-distributed point configurations: discrepancy, quasi-Monte Carlo methods, dispersion: Many problems in approximation theory and complexity rely on the existence and construction of good (random or deterministic) point distributions with respect to discrepancy, integration errors, strength of cubature formulas, dispersion, or discrete energy. Numerous questions in this area are still open: in various regimes sharp bounds for discrepancy and dispersion still remain unknown and explicit efficient constructions are still lacking. Collective effort of experts in approximation, complexity, discrete mathematics, and probability may bring substantial progress in these problems.

Linear and standard information in approximation theory: A classical problem of approximation theory, learning theory and data analysis is the approximation of an unknown multivariate function from incomplete information. The information can be given by a limited number of function evaluations (standard information) or by evaluating a finite number of arbitrary linear functionals (linear information). Even in the simplest setting of approximation in a norm of a Hilbert space, the relation between using standard information and linear information was understood only recently and there is still a number of challenging open questions in this area

Copyright Dmitriy Bilyk, Michael Gnewuch, Jan Vybíral, and Larisa Yaroslavtseva

Participants

Related Seminars
  • Dagstuhl Seminar 9116: Algorithms and Complexity of Continuous Problems (1991-04-15 - 1991-04-19) (Details)
  • Dagstuhl Seminar 9242: Algorithms and Complexity for Continuous Problems (1992-10-12 - 1992-10-16) (Details)
  • Dagstuhl Seminar 9442: Algorithms and Complexity for Continuous Problems (1994-10-17 - 1994-10-21) (Details)
  • Dagstuhl Seminar 9643: Algorithms and Complexity for Continuous Problems (1996-10-21 - 1996-10-25) (Details)
  • Dagstuhl Seminar 98201: Algorithms and Complexity for Continuous Problems (1998-05-18 - 1998-05-22) (Details)
  • Dagstuhl Seminar 00391: Algorithms and Complexity for Continuous Problems (2000-09-24 - 2000-09-29) (Details)
  • Dagstuhl Seminar 02401: Algorithms and Complexity for Continuous Problems (2002-09-29 - 2002-10-04) (Details)
  • Dagstuhl Seminar 04401: Algorithms and Complexity for Continuous Problems (2004-09-26 - 2004-10-01) (Details)
  • Dagstuhl Seminar 06391: Algorithms and Complexity for Continuous Problems (2006-09-24 - 2006-09-29) (Details)
  • Dagstuhl Seminar 09391: Algorithms and Complexity for Continuous Problems (2009-09-20 - 2009-09-25) (Details)
  • Dagstuhl Seminar 12391: Algorithms and Complexity for Continuous Problems (2012-09-23 - 2012-09-28) (Details)
  • Dagstuhl Seminar 15391: Algorithms and Complexity for Continuous Problems (2015-09-20 - 2015-09-25) (Details)
  • Dagstuhl Seminar 19341: Algorithms and Complexity for Continuous Problems (2019-08-18 - 2019-08-23) (Details)

Classification
  • Computational Complexity
  • Data Structures and Algorithms
  • Numerical Analysis

Keywords
  • Tractability Analysis
  • Computational Stochastics
  • Infinite-Variate Problems
  • Quasi-Monte Carlo Methods
  • Sampling