Sampling Complexity of Deep Approximation Spaces
This is an incremental extension of prior work, addressing the theory-to-practice gap in deep learning for researchers in approximation theory.
The study tackles the challenge of computing neural network approximations from point samples, showing that functions approximated by ReQU activation networks at arbitrary rates require an exponentially growing number of samples in input dimension.
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.