mlsanityData to 7 Oct 2026

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

arXiv 2107.13163 ↗First posted 28 Jul 2021cs.LG stat.MLcited by 101

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 101 papers in the map (data through 7 Oct 2026). Builds on 45 of its 78 references that are in the map. First posted on arXiv 28 Jul 2021.

Builds on

45 of 78 references.

References · 45

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  4. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  5. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  6. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  7. 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 404
  8. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  9. 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 304
  10. 2015Norm-Based Capacity Control in Neural Networkscited by 299
  11. 2017Size-Independent Sample Complexity of Neural Networkscited by 289
  12. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
33 more
  1. 2016Benefits of depth in neural networkscited by 248
  2. 2015The Power of Depth for Feedforward Neural Networkscited by 181
  3. 2018Universality of Deep Convolutional Neural Networkscited by 176
  4. 2018Regularization Matters: Generalization and Optimization of Neural Nets v.s. their Induced Kernelcited by 131
  5. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  6. 2018Universal approximations of invariant maps by neural networkscited by 127
  7. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  8. 2016Identity Matters in Deep Learningcited by 107
  9. 2015On the Expressive Power of Deep Learning: A Tensor Analysiscited by 97
  10. 2019Limitations of Lazy Training of Two-layers Neural Networkscited by 87
  11. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  12. 2018ResNet with one-neuron hidden layers is a Universal Approximatorcited by 78
  13. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
  14. 2019Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentationcited by 71
  15. 2020RNNs can generate bounded hierarchical languages with optimal memorycited by 59
  16. 2019Approximation Capabilities of Neural ODEs and Invertible Residual Networkscited by 56
  17. 2019Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margincited by 56
  18. 2019Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resiliencecited by 51
  19. 2017Depth Separation for Neural Networkscited by 46
  20. 2019On the Computational Power of RNNscited by 35
  21. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  22. 2016Convolutional Rectifier Networks as Generalized Tensor Decompositionscited by 32
  23. 2020Universal Approximation Property of Neural Ordinary Differential Equationscited by 32
  24. 2017Recurrent Neural Networks as Weighted Language Recognizerscited by 30
  25. 2019Neural tangent kernels, transportation mappings, and universal approximationcited by 30
  26. 2019Universal approximations of permutation invariant/equivariant functions by deep neural networkscited by 29
  27. 2017On the ability of neural nets to express distributionscited by 26
  28. 2021The Connection Between Approximation, Depth Separation and Learnability in Neural Networkscited by 19
  29. 2020Neural Networks with Small Weights and Depth-Separation Barrierscited by 17
  30. 2019Depth-Width Trade-offs for ReLU Networks via Sharkovsky's Theoremcited by 15
  31. 2020Memory capacity of neural networks with threshold and ReLU activationscited by 13
  32. 2020Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systemscited by 9
  33. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 6; 2023: 34; 2024: 31; 2025: 20; 2026: 9.

101 papers.

Sort:

By area:

  1. 2022What learning algorithm is in-context learning? Investigations with linear modelscited by 671
  2. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 293
  3. 2023Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selectioncited by 291
  4. 2023Transformers learn to implement preconditioned gradient descent for in-context learningcited by 274
  5. 2023Looped Transformers as Programmable Computerscited by 224
  6. 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
  7. 2023Representational Strengths and Limitations of Transformerscited by 132
  8. 2023Teaching Arithmetic to Small Transformerscited by 121
  9. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  10. 2023What and How does In-Context Learning Learn? Bayesian Model Averaging, Parameterization, and Generalizationcited by 112
  11. 2023Scan and Snap: Understanding Training Dynamics and Token Composition in 1-layer Transformercited by 101
  12. 2023Tracr: Compiled Transformers as a Laboratory for Interpretabilitycited by 99
38 more
  1. 2022Vision Transformers provably learn spatial structurecited by 92
  2. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 85
  3. 2022Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Modelscited by 84
  4. 2023Transformers as Decision Makers: Provable In-Context Reinforcement Learning via Supervised Pretrainingcited by 82
  5. 2023A Theoretical Understanding of Shallow Vision Transformers: Learning, Generalization, and Sample Complexitycited by 77
  6. 2024Transformers, parallel computation, and logarithmic depthcited by 75
  7. 2023Exposing Attention Glitches with Flip-Flop Language Modelingcited by 74
  8. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 65
  9. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 64
  10. 2023Transformers Implement Functional Gradient Descent to Learn Non-Linear Functions In Contextcited by 63
  11. 2024Can Looped Transformers Learn to Implement Multi-step Gradient Descent for In-context Learning?cited by 60
  12. 2023Do Transformers Parse while Predicting the Masked Word?cited by 48
  13. 2024LoRA Training in the NTK Regime has No Spurious Local Minimacited by 48
  14. 2023Memory Augmented Large Language Models are Computationally Universalcited by 45
  15. 2023An Over-parameterized Exponential Regressioncited by 45
  16. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  17. 2023The Closeness of In-Context Learning and Weight Shifting for Softmax Regressioncited by 41
  18. 2023Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalizationcited by 39
  19. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 39
  20. 2023Deep Networks as Denoising Algorithms: Sample-Efficient Learning of Diffusion Models in High-Dimensional Graphical Modelscited by 39
  21. 2024Attention with Markov: A Framework for Principled Analysis of Transformers via Markov Chainscited by 39
  22. 2023Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Inputcited by 32
  23. 2023Universality and Limitations of Prompt Tuningcited by 30
  24. 2023Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammarscited by 30
  25. 2024Understanding Scaling Laws with Statistical and Approximation Theory for Transformer Neural Networks on Intrinsically Low-dimensional Datacited by 30
  26. 2023A Mathematical Abstraction for Balancing the Trade-off Between Creativity and Reality in Large Language Modelscited by 29
  27. 2024Simulation of Graph Algorithms with Looped Transformerscited by 29
  28. 2023Sequence Length Independent Norm-Based Generalization Bounds for Transformerscited by 28
  29. 2024Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamicscited by 27
  30. 2024Transformers on Markov Data: Constant Depth Sufficescited by 26
  31. 2024Universal Length Generalization with Turing Programscited by 25
  32. 2024When Can Transformers Count to n?cited by 22
  33. 2024Provably learning a multi-head attention layercited by 21
  34. 2024Do Efficient Transformers Really Save Computation?cited by 20
  35. 2025A Theory of Learning with Autoregressive Chain of Thoughtcited by 20
  36. 2023Large Sequence Models for Sequential Decision-Making: A Surveycited by 19
  37. 2024Looped ReLU MLPs May Be All You Need as Practical Programmable Computerscited by 19
  38. 2023Trainable Transformer in Transformercited by 17

50 most cited of 101 All 101 (JSON)