Approximation of Permutation Invariant Polynomials by Transformers: Efficient Construction in Column-Size
This provides theoretical validation for transformers' efficiency in handling symmetric structures, which is incremental to existing mathematical analyses.
The paper tackles the problem of approximating column-symmetric polynomials using transformers, establishing an explicit relationship between network size and approximation capability based on algebraic properties.
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.