Dagstuhl-Seminar 23351
Algorithms and Complexity for Continuous Problems
( 27. Aug – 01. Sep, 2023 )
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/23351
Organisatoren
- 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)
Kontakt
- Andreas Dolzmann (für wissenschaftliche Fragen)
- Susanne Bach-Bernhard (für administrative Fragen)
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
Creative Commons BY 4.0
Dmitriy Bilyk, Michael Gnewuch, Jan Vybíral, and Larisa Yaroslavtseva
Verwandte Seminare
- 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)
Klassifikation
- Computational Complexity
- Data Structures and Algorithms
- Numerical Analysis
Schlagworte
- Tractability Analysis
- Computational Stochastics
- Infinite-Variate Problems
- Quasi-Monte Carlo Methods
- Sampling
