Function approximation with restricted information

Functions describe the dependence of a target variable upon one or several independent variables. These variables can be all sorts of measurable quantities like the maximum temperature in Vienna for tomorrow based on various weather data from today or the probability for skin cancer based on a picture of the skin. The precise dependency between the influential and the target quantity are usually unknown. We therefore want to learn the dependency with best possible accuracy, or in other words: We want to approximate the function. Based on our approximation, we can then make predictions of the target value in the future. To learn the dependency we have access to a certain kind of data. In some cases, we may collect the data actively and perform measurements that tell us as much as possible about the function. In other cases, our influence on the choice of the measurements is restricted or we have to cope with the data that is already at hand. This project deals with the question to what extent these restrictions lead to a worse prediction. For example, there are surprisingly many cases, where randomly obtained data is almost as good as data that is obtained from complicated and carefully selected measurements. This is one of the phenomena which we seek to understand. However, instead of specific examples like weather forecasts, we investigate the above research questions for abstract classes of functions that are as general as possible, so that the results are useful for a large variety of applications. The project therefore deals with the mathematical foundations and the models behind these phenomena.

Functions describe how a quantity of interest is determined by other quantities. In reality, the precise dependence is usually unknown and so we want to approximate the unknown function. This is done on the basis of model assumptions on the one hand and a finite amount of data on the other hand. The data can be acquired, e.g., by physical measurements or running a computer program. Often, one cannot choose the measurements freely and only a restricted type of information is available. The objective of this project was to study the power of restricted information in comparison with unrestricted information. We studied three types of restrictions: 1. The power of general linear measurements (like Fourier coefficients) is often well understood. In practice, we usually only have access to function values. How much is lost by this restriction? The answer depends on the notion of error. We settled the question in two important situations: The first is that the deviation is measured in the mean-square norm (small error on average) and the second is that the distance is measured in the maximum norm (small error at every single point). In both situations, we found a general criterion under which the restriction essentially causes no loss at all, while the loss can be dramatic if the criterion is not matched. We also bound from above the maximal loss in the case that the criterion is not matched and give partial answers for other error notions. 2. Sometimes, one cannot even choose the location of the function values and data can only be observed at random (iid) sites. We studied this situation and identified many situations where this kind of information is almost as powerful as function values at optimally chosen locations. Namely, with high probability, a logarithmic oversampling is enough to compensate for the restriction. The resulting approximation algorithms based on the iid points are sometimes even better than any other explicitly known algorithm, like Smolyak's algorithm. It turned out that this kind of information is even suitable to disprove the curse of dimensionality for a broad class of (unweighted) function approximation problems. 3. In general, it can be quite advantageous to choose the measurements adaptively depending on the already obtained data. On the other hand, this is not always possible and the same measurements have to be used for every input. We studied how much is lost by restricting from adaptive to non-adaptive information. In fact, we even bound the maximal loss of non-adaptive methods that are forbidden to use randomness compared to adaptive algorithms that are allowed to use random number generators. A crucial advance is also that our results do not require the input class to be symmetric.