Optimal Recovery from Observational Data: Theory and Applications

Abstract

Learning an unknown function from given noisy data observations is a main task in data science. The central problem is to use data observations and prior knowledge to construct an approximation for the unknown function. This kind of problem has been studied under different problem settings. The most popular one is called Statistical Learning, where we assume that the inputs and the observational errors are random. However, this statistical assumption is usually unrealistic when solving real problems.

In this thesis, we study the learning problem from the Optimal Recovery perspective, where we assume that the data are fixed entities and observational errors are bounded in some norm. Using data observations tied to an explicit model assumption made on the functions to be learned, our goal is to recover the unknown function or a quantity depending on the function. This is done by finding a recovery map which takes data observations as inputs and returns an approximation for the unknown function. The performance is measured by the worst-case error, central to Optimal Recovery. Optimal Recovery was an old problem from Approximation Theory. Its development slowed down and reached limitation due to the lack of computational emphasis. Exploring the full power of modern optimization theory, we are able to study the Optimal Recovery problem from a more computational point of view. We summarize some recent advances in computational Optimal Recovery in this thesis.

Assuming the unknown function belongs to a Hilbert space, we first study the optimal recovery problem from exact observations, i.e. there is no observational noise. We construct the optimal recovery map and develop a numerical way to compute the corresponding worst-case error. We also discuss the relationship between Optimal Recovery and kernel regression when the target function belongs to a reproducing kernel Hilbert space. The connection between Optimal Recovery and Gaussian process regression is also studied.

Then, we incorporate observational inaccuracies via additive errors bounded in ℓ2. Earlier works have demonstrated that regularization provides algorithms that are optimal in the sense that the worst-case error is minimized. However, the choice of regularization parameter was not given. We give an explicit way to compute the optimal regularization parameter under different problem setting. Applications in estimation theory and semi-supervised learning are also presented.

We also consider the setting where we assume that the additive errors are ℓ1 bounded. Numerical results indicate that there exists a linear optimal recovery map. A result on recovering a linear functional is restated. Then we generalize this result to recovering a linear quantity of interest when the approximation error is measured in ℓ∞ norm. We test the proposed optimal recovery method on the real world time series prediction problem.