Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers

Abstract

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.

References in corpus (20)

• Understanding deep learning requires rethinking generalization
• A Mean Field View of the Landscape of Two-Layers Neural Networks
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Spectrally-normalized margin bounds for neural networks
• ResNet with one-neuron hidden layers is a Universal Approximator
• Understanding Deep Neural Networks with Rectified Linear Units
• Norm-Based Capacity Control in Neural Networks
• On the Turing Completeness of Modern Neural Network Architectures
• Optimization Landscape and Expressivity of Deep CNNs
• Universal approximations of permutation invariant/equivariant functions by deep neural networks
• On the ability of neural nets to express distributions
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
• Universal Approximation Property of Neural Ordinary Differential Equations
• On the Computational Power of RNNs
• Depth Separation for Neural Networks
• Memory capacity of neural networks with threshold and ReLU activations
• Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theorem
• Provable Memorization via Deep Neural Networks using Sub-linear Parameters
• The Connection Between Approximation, Depth Separation and Learnability in Neural Networks

Cited by in corpus (2)

• Q-Learning based system for path planning with unmanned aerial vehicles swarms in obstacle environments
• Inductive Biases and Variable Creation in Self-Attention Mechanisms