Official Review · NEURIPS 2024

This paper investigates the representational capabilities of transformers in regression tasks and their correlation with scaling laws. The authors present a novel analysis of the transformer's sample complexity on datasets with low intrinsic dimension $d$, or those residing on a $d$-dimensional manifold $\mathcal{M}$. Their findings yield a bound reminiscent of standard non-parametric regression results, with the key distinction that it depends on the intrinsic dimension rather than the actual data dimension. The analysis hinges on a specific transformer construction that performs approximation on subregions of $\mathcal{M}$. Notably, when the model is sufficiently wide and deep, this construction can approximate the target function to $\epsilon$ precision with a depth independent of $\epsilon$. This characteristic contrasts favorably with feedforward models using ReLU activation, which typically require $O(\epsilon^{-1})$ layers. Finally, the paper shows that if we estimate the intrinsic dimension of the data, the resulting estimate of the exponent can be informative of that predicted by the sample complexity from the theoretical result. As far as I know, the theoretical result of the paper is novel and highly non-trivial. To a certain degree, it sheds light on the fundamental difference between a transformer and simpler models like the feed-forward model. I foresee these results to be useful for future research into the statistical properties of transformers. The theoretical result is novel but I am not sure how insightful the bound of the construction is about what the model actually is doing and how the result is related to scaling law. There are several weaknesses in the paper which I will discuss below: Despite its novel theoretical contributions, this paper has several significant weaknesses that warrant discussion: 1. **Limited applicability to real-world scenarios**: The theoretical model presented in the paper assumes a regression or supervised learning task, which diverges significantly from how transformer models are typically used in practice. The input representation ($x$ as a $D$-dimensional vector with the sequence being a linear transformation of $x$) also appears overly simplistic and may not adequately capture the complexity of real-world data and tasks. This disconnect raises questions about how well the theoretical results translate to practical applications. 2. **Relevance of the proposed construction**: While the construction presented in the paper is mathematically interesting at a technical level, it's unclear whether it accurately represents the actual learning process of transformer models. The authors do not provide empirical evidence to support that their theoretical construction aligns with the internal representations or mechanisms developed by transformers during training. This lack of validation leaves a significant gap between theory and practice. I would be more than happy to be proven wrong with empirica