Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Size
Not on the map. Why?
Abstract (arXiv)
Transformers are a type of neural network that have demonstrated remarkable performance across various domains, particularly in natural language processing tasks. Motivated by this success, research on the theoretical understanding of transformers has garnered significant attention. A notable example is the mathematical analysis of their approximation power, which validates the empirical expressive capability of transformers. In this study, we investigate the ability of transformers to approximate column-symmetric polynomials, an extension of symmetric polynomials that take matrices as input. Consequently, we establish an explicit relationship between the size of the transformer network and its approximation capability, leveraging the parameter efficiency of transformers and their compatibility with symmetry by focusing on the algebraic properties of symmetric polynomials.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 27 of its 33 references that are in the map. First posted on arXiv 17 Feb 2025.
Builds on
27 of 33 references.
References · 27
- 2017Attention Is All You Needcited by 60,361
- 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,399
- 2020Language Models are Few-Shot Learnerscited by 32,419
- 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
- 2020Big Bird: Transformers for Longer Sequencescited by 1,684
- 2017Deep Setscited by 1,421
- 2016Error bounds for approximations with deep ReLU networkscited by 574
- 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
- 2019Are Transformers universal approximators of sequence-to-sequence functions?cited by 406
- 2017The Expressive Power of Neural Networks: A View from the Widthcited by 320
- 2017Optimal approximation of piecewise smooth functions using deep ReLU neural networkscited by 179
- 2020Deep Network Approximation for Smooth Functionscited by 164
15 more
- 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 162
- 2019On the Universality of Invariant Networkscited by 152
- 2018Universal approximations of invariant maps by neural networkscited by 127
- 2020Low-Rank Bottleneck in Multi-head Attention Modelscited by 89
- 2020O(n) Connections are Expressive Enough: Universal Approximability of Sparse Transformerscited by 83
- 2018Deep Neural Networks Learn Non-Smooth Functions Effectivelycited by 57
- 2021On the Expressive Power of Self-Attention Matricescited by 47
- 2023Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?cited by 47
- 2021On the Optimal Memorization Power of ReLU Neural Networkscited by 40
- 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
- 2021Universal Approximation Under Constraints is Possible with Transformerscited by 32
- 2023Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Inputcited by 32
- 2019Universal approximations of permutation invariant/equivariant functions by deep neural networkscited by 29
- 2019On the minimax optimality and superiority of deep neural network learning over sparse parameter spacescited by 24
- 2020Advantage of Deep Neural Networks for Estimating Functions with Singularity on Hypersurfacescited by 17
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.