##### Dagstuhl Seminar 23351

### Algorithms and Complexity for Continuous Problems

##### ( Aug 27 – Sep 01, 2023 )

##### Permalink

##### 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

- Andreas Dolzmann (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)

##### Shared Documents

- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)

##### Impacts

- Computable error bounds forquasi-Monte Carlo usingpoints with non-negativelocal discrepancy - Gnewuch, Michael; Kritzer, Peter; Owen, Art B.; Pan, Zexin - Linz : RICAM, 2023. - 25 pp. - (RICAM Reports ; 2023-25).
- Linear Monte Carlo quadrature with optimal confidence intervals : article - Kunsch, Robert J. - Cornell University : arXiv.org, 2023. - 22 pp..
- Diverse Diffusion : Enhancing Image Diversity in Text-to-Image Generation - Zameshina, Mariia; Teytaud, Olivier; Najman, Laurent - Cornell University : arXiv.org, 2023. - 47 pp..
- Improved bounds for the bracketing number of orthants or revisiting an algorithm of Thiémard to compute bounds for the star discrepancy : article - Gnewuch, Michael - Cornell University : arXiv.org, 2024. - 13 pp..
- Selected aspects of tractability analysis - Kritzer, Peter - Cornell University : arXiv.org, 2024. - 24 pp..

##### Schedule

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):

- Peter Kritzer (RICAM Linz), Tractability analysis.
- Thomas Müller-Gronbach (Unversität Passau), On the complexity of strong approximation of SDEs with a non-Lipschitz drift coefficient.
- Klaus Ritter (RPTU Kaiserslautern-Landau), Infinite-variate integration and
*L*^{2}-approximation. - Stefan Steinerberger (University of Washington – Seattle), Well-distributed point configurations.
- 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.

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

- Dmitriy Bilyk (University of Minnesota - Minneapolis, US) [dblp]
- François Clément (Sorbonne University - Paris, FR)
- Ronald Cools (KU Leuven, BE) [dblp]
- Steffen Dereich (Universität Münster, DE) [dblp]
- Benjamin Doerr (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Carola Doerr (Sorbonne University - Paris, FR) [dblp]
- Michael Giles (University of Oxford, GB) [dblp]
- Michael Gnewuch (Universität Osnabrück, DE) [dblp]
- Kumar Harsha (Universität Osnabrück, DE) [dblp]
- Stefan Heinrich (RPTU - Kaiserslautern, DE) [dblp]
- Alexander Keller (NVIDIA, DE) [dblp]
- David Krieg (Johannes Kepler Universität Linz, AT) [dblp]
- Peter Kritzer (Österreichische Akadamie der Wissenschaften - Linz, AT) [dblp]
- Thomas Kühn (Universität Leipzig, DE) [dblp]
- Robert J. Kunsch (RWTH Aachen, DE & TU Chemnitz, DE) [dblp]
- Frances Y. Kuo (UNSW Sydney, AU) [dblp]
- Laura Lippert (TU Chemnitz, DE)
- Alexander Litvak (University of Alberta - Edmonton, CA) [dblp]
- Michelle Mastrianni (University of Minnesota - Minneapolis, US) [dblp]
- Peter Mathé (Weierstraß Institut - Berlin, DE) [dblp]
- Weiwen Mo (KU Leuven, BE) [dblp]
- Thomas Müller-Gronbach (Universität Passau, DE) [dblp]
- Erich Novak (Friedrich-Schiller-Universität Jena, DE) [dblp]
- Dirk Nuyens (KU Leuven, BE) [dblp]
- Zexin Pan (Stanford University, US) [dblp]
- Kateryna Pozharska (National Academy of Sciences of Ukraine - Kiev, UA & TU Chemnitz, DE) [dblp]
- Pawel Przybylowicz (AGH Univ. of Science & Technology-Krakow, PL) [dblp]
- Klaus Ritter (RPTU - Kaiserslautern, DE) [dblp]
- Daniel Rudolf (Universität Passau, DE) [dblp]
- Robin Rüßmann (RPTU - Kaiserslautern, DE) [dblp]
- Mathias Sonnleitner (Universität Passau, DE) [dblp]
- Abirami Srikumar (UNSW Sydney, AU) [dblp]
- Stefan Steinerberger (University of Washington - Seattle, US) [dblp]
- Olivier Teytaud (Meta AI Research - Tournon-sur-Rhone, FR) [dblp]
- Mario Ullrich (Johannes Kepler Universität Linz, AT) [dblp]
- Tino Ullrich (TU Chemnitz, DE) [dblp]
- Jan Vybíral (Czech Technical University - Prague, CZ) [dblp]
- Christian Weiß (Hochschule Ruhr-West - Mülheim, DE)
- Laurence Wilkes (KU Leuven, BE) [dblp]
- Marcin Wnuk (Universität Osnabrück, DE) [dblp]

##### 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