Preasymptotic error analysis for function recovery problems in high dimensions

• Applicant: Professor Dr. Tino Ullrich
• Subject Area: Mathematics
• Term: from 2016 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 299251995

• Final Report Year: 2022

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
  
• “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
  
• “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
  
• “A new upper bound for sampling numbers”. In: Found. Comput. Math. (2021), 24 pp.
  N. Nagel, M. Schäfer, and T. Ullrich
  
• “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
  
• “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
  
• “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
  
• “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
  
• “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
  
• “A note on sampling recovery of multivariate functions in the uniform norm”. In: SIAM J. Num. Anal. (2022)
  K. Pozharska and T. Ullrich