Adaptive sampling strategies for function approximation in high dimensions

Many problems in computational science and engineering can be cast as approximating a high-dimensional function from data. These types of problems involves at least three main challenges. First, the curse of dimensionality, which implies computational effort and the number of samples needed grows exponentially with the dimension for many standard approximation schemes. Second, the domain where the function is defined may be irregular and/or disconnected, and in some applications, it may be unknown in advance, and only accessible via a black box evaluation of the function. Third, obtaining samples is expensive. For example, each sample may require a costly PDE solve. In this work, we develop a series of novel methods for learning approximations to high-dimensional functions from limited data over arbitrary (known or unknown) domains. We present three main cases. First, we assume knowledge of the domain, along with a subspace in which the function is well approximated. We propose a weighted least-squares formulation and develop the Christoffel Sampling (CS) method. We theoretically analyze this method, and show that it leads to a stable and accurate approximation using only O(N log(N)) samples, where N is the dimension of the subspace. Next, we assume the domain is unknown. We extend CS to iteratively learn the domain and construct suitable sampling measures, a method we term Christoffel Adaptive Sampling for Unknown Domains (CAS4UD). Finally, we consider function approximation via Deep Learning (DL) and Deep Neural Networks (DNNs). Unlike the previous methods, in this case the approximation space is nonlinear. Here, we exploit the adaptive basis viewpoint of DL to develop an adaptive sampling strategy for function approximation via DL using CS. We term this method Christoffel Adaptive Sampling for Deep Learning (CAS4DL). We present a comprehensive set of numerical experiments, which compare our methods against standard techniques such as Monte Carlo sampling (MCS). In many cases, our methods achieve substantial savings in the number of samples required to obtain a given accuracy.