Statistically Meaningful Approximation: a Case Study on Approximating
  Turing Machines with Transformers
  A common lens to theoretically study neural net architectures is to analyze
the functions they can approximate. However, constructions from approximation
theory may be unrealistic and therefore less meaningful. For example, a common
unrealistic trick is to encode target function values using infinite precision.
To address these issues, this work proposes a formal definition of
statistically meaningful (SM) approximation which requires the approximating
network to exhibit good statistical learnability. We study SM approximation for
two function classes: boolean circuits and Turing machines. We show that
overparameterized feedforward neural nets can SM approximate boolean circuits
with sample complexity depending only polynomially on the circuit size, not the
size of the network. In addition, we show that transformers can SM approximate
Turing machines with computation time bounded by $T$ with sample complexity
polynomial in the alphabet size, state space size, and $\log (T)$. We also
introduce new tools for analyzing generalization which provide much tighter
sample complexities than the typical VC-dimension or norm-based bounds, which
may be of independent interest.
