Sampling Complexity of Deep Approximation Spaces
Ahmed Abdeljawad Philipp Grohs
While it is well-known that neural networks enjoy excellent approximation
capabilities, it remains a big challenge to compute such approximations from
point samples. Based on tools from Information-based complexity, recent work by
Grohs and Voigtlaender [Journal of the FoCM (2023)] developed a rigorous
framework for assessing this so-called "theory-to-practice gap". More
precisely, in that work it is shown that there exist functions that can be
approximated by neural networks with ReLU activation function at an arbitrary
rate while requiring an exponentially growing (in the input dimension) number
of samples for their numerical computation. The present study extends these
findings by showing analogous results for the ReQU activation function.