Learning smooth functions in high dimensions: from sparse polynomials to
  deep neural networks
Ben Adcock Simone Brugiapaglia Nick Dexter Sebastian Moraga
Learning approximations to smooth target functions of many variables from
finite sets of pointwise samples is an important task in scientific computing
and its many applications in computational science and engineering. Despite
well over half a century of research on high-dimensional approximation, this
remains a challenging problem. Yet, significant advances have been made in the
last decade towards efficient methods for doing this, commencing with so-called
sparse polynomial approximation methods and continuing most recently with
methods based on Deep Neural Networks (DNNs). In tandem, there have been
substantial advances in the relevant approximation theory and analysis of these
techniques. In this work, we survey this recent progress. We describe the
contemporary motivations for this problem, which stem from parametric models
and computational uncertainty quantification; the relevant function classes,
namely, classes of infinite-dimensional, Banach-valued, holomorphic functions;
fundamental limits of learnability from finite data for these classes; and
finally, sparse polynomial and DNN methods for efficiently learning such
functions from finite data. For the latter, there is currently a significant
gap between the approximation theory of DNNs and the practical performance of
deep learning. Aiming to narrow this gap, we develop the topic of practical
existence theory, which asserts the existence of dimension-independent DNN
architectures and training strategies that achieve provably near-optimal
generalization errors in terms of the amount of training data.