Preasymptotic error analysis for function recovery problems in high dimensions
Final Report Abstract
Many applications in engineering, science, and statistics require inter‐ or extrapolation from data. Mathematically speaking, the problem is to find a function fitting the data. This research project is concerned with the pre-asymptotic error analysis of such recovery problems for high‐dimensional data. The functions appearing in the studied recovery problems are subject to two different kinds of model assumptions: on the one hand, the boundedness of mixed derivatives and generalizations thereof, which naturally appear in the context of the electronic Schrödinger equation and sparse grid methods; on the other hand, assumptions of structured dependencies, which are significant in semiparametric statistics and machine learning. The main focus of the research project are pre-asymptotic bounds for worst‐case errors and the design of optimal algorithms given one of the previously mentioned model assumptions. Worst‐case error estimates are a central ingredient in the analysis of approximation and function recovery methods. They provide a priori error estimates which are most reliable given correct model assumptions. At the same time, worst‐case error estimates give insights into the fundamental limitations of approximation and recovery methods. For the considered problems, asymptotic error estimates are typically known for quite some time. In case of functions defined on high‐dimensional domains, however, asymptotic estimates often turn out to be useless. One reason is that they are only valid after investing a number of samples growing exponentially with the dimension. At this point, pre-asymptotics become crucial to obtain practically relevant error estimates. Pre-asymptotics are also important to precisely determine the level of tractability of a high‐dimensional approximation problem. In particular, pre-asymptotics allow to decide whether or not the curse of dimensionality is present. The rigorous analysis of pre-asymptotics in this research project will be based on fundamental concepts and results from approximation theory and functional analysis. The concept particularly worth mentioning is metric entropy. Metric entropy, respectively entropy numbers, is an essential ingredient in the context of Carl's inequality, concentration inequalities for empirical processes, and a new characterization method for worst‐case errors discovered by the applicant. All three will be important tools in the proofs of lower and upper bounds for worst‐case errors.
Publications
- “Counting via entropy: new preasymptotics for the approximation numbers of Sobolev embeddings”. In: SIAM Journ. on Numerical Analysis 54.6 (2016), pp. 3625–3647
T. Kühn, S. Mayer, and T. Ullrich
(See online at https://doi.org/10.1137/16m106580x) - “Optimal sampling recovery of mixed order Sobolev embeddings via discrete Littlewood-Paley type characterizations”. In: Anal. Math. 43.2 (2017), pp. 133–191. ISSN: 0133-3852
G. Byrenheid and T. Ullrich
(See online at https://doi.org/10.1007/s10476-017-0303-5) - “Monte Carlo methods for uniform approximation on periodic Sobolev spaces with mixed smoothness”. In: J. Complexity 46 (2018), pp. 90–102. ISSN: 0885-064X
G. Byrenheid, R. J. Kunsch, and V. K. Nguyen
(See online at https://doi.org/10.1016/j.jco.2017.12.002) - “A new upper bound for sampling numbers”. In: Found. Comput. Math. (2021), 24 pp.
N. Nagel, M. Schäfer, and T. Ullrich
(See online at https://doi.org/10.1007/s10208-021-09504-0) - “Entropy numbers of finite dimensional mixed-norm balls and function space embeddings with small mixed smoothness”. In: Constr. Approx. 53.2 (2021), pp. 249–279
S. Mayer and T. Ullrich
(See online at https://doi.org/10.1007/s00365-020-09510-5) - “How anisotropic mixed smoothness affects the decay ¨ of singular numbers for Sobolev embeddings”. In: J. Complexity 63 (2021), Paper No. 101523, 37. ISSN: 0885-064X
T. Kühn, W. Sickel, and T. Ullrich
(See online at https://doi.org/10.1016/j.jco.2020.101523) - “L2 -norm sampling discretization and recovery of functions from RKHS with finite trace”. In: Sampling Theory, Signal Processing, and Data Analysis 19.2 (July 2021), pp. 1–31
M. Moeller and T. Ullrich
(See online at https://doi.org/10.1007/s43670-021-00013-3) - “On the optimal constants in the two-sided Stechkin inequalities”. In: J. Approx. Theory 269 (2021), Paper No. 105607, 25. ISSN: 0021-9045
T. Jahn and T. Ullrich
(See online at https://doi.org/10.1016/j.jat.2021.105607) - “The recovery of ridge functions on the hypercube suffers from the curse of dimensionality”. In: J. Complexity 63 (2021), Paper No. 101521, 29. ISSN: 0885-064X
B. Doerr and S. Mayer
(See online at https://doi.org/10.1016/j.jco.2020.101521) - “A note on sampling recovery of multivariate functions in the uniform norm”. In: SIAM J. Num. Anal. (2022)
K. Pozharska and T. Ullrich
(See online at https://doi.org/10.48550/arXiv.2103.11124)
