Summary
The paper considers the representational and generalization properties single-layer scalar-valued transformer models with random key and query matrices and value vectors that can depend on those random matrices. They draw a comparison to the well-studied random-feature models for two-layer neural networks. Concretely:
* Theorem 1 proves that functions of the form $f_*(x_{0:N}) = \frac1N \sum_i F(x_0, x_i)$ can be efficiently represented under the random feature, with quadratic dependence on the input dimension $d$ and no dependence on the sequence length $N$.
* Theorem 2 extends this approximation-theoretic result to generalization by proving a generalization bound on the empirical risk-minimizing random feature transformer (among transformers with bounded value vectors) that fits a noiseless dataset. The proof follows from bounds on the Rademacher complexity of the family of functions that approximately represent the dataset.
* The paper gives several examples in Section 3.3 of functions of the above form and show that they admit much stronger learning rates for random feature attention models than for standard random feature models. Generally, standard random feature models have a substantial dependence on $N$, while random feature attention has no such dependence.
* Theorem 3 proves a generalization bound similar to Theorem 2, but in the regime where the random feature matrices (e.g. the product of the key and query matrices) is biased in favor of larger elements on the diagonal. (This is empirically motivated in the appendix by a finding that BERT weight matrices frequently concentrate mass on the diagonals.) They prove generalization bounds for a restricted family of target functions, where high-degree polynomials of $\langle x_0, x_i\rangle$ and low-degree polynomials of $x_0 \otimes x_i$ may be averaged together. They provide several examples showing how this model can reduce the error rates over the standard random feature attention model.
* Numerical experiments in Section 5 validate their theoretical results by comparing the error rates as a function of sample complexity of random feature MLPs, random feature attention, and biased random feature attention.
Strengths
The work is novel, interesting, and relevant to the growing study of the theoretical properties of transformers. The work formalizes some intuitive advantages that attention models hold over standard MLPs in their ability to compute and aggregate pairwise functions of sequential inputs. Theoretical results are presented cleanly and the proofs that I read appeared correct. The work is creative, and draws inspiration for Theorem 3 from empirical observations. There is interesting follow-up work to be done on understanding the strengths and limitations of this model, especially on the optimization front.
Weaknesses
While the bounds are interesting in their own right, the comparisons between random feature attention and MLP models focus on a few particular examples, whose generality is unclear. Moreover, the comparisons are between upper bounds for both models; ideally, the results would contrast with _lower_ bounds for random feature MLPs.
### Minor pointers
l244: "scaler" -> "scalar"
l657: $W$ in equation block should be $W_m$
Questions
Would you mind explaining if you expect that the $\delta^{-1}$ dependence in Theorem 1 could be improved? As far as I am aware, other random feature approximation papers can often achieve a $\sqrt{\log \delta^{-1}}$ dependence by employing concentration bounds over Hilbert spaces instead of Markov or Chebyshev, as is employed in the proof of Lemma B.1.
I would be interested to know why in particular you chose to focus on the diagonally-biased weight initializations, when the plots in Figure 5 appear to make similarly strong cases in favor of selecting random feature matrices $W$ from distributions that impose either sparsity or low rank. (I am okay with these regimes not being included in the paper; I am mostly just interested in the choice.)
Would it be possible to offer a more concrete comparison with the Rademacher complexity generalization bounds in this work and single-layer covering numbers-based bound of [Edelman et al](https://arxiv.org/abs/2110.10090)? While the regimes are different, I think the paper would benefit from a brief comparison of the advantages and disadvantages of each.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The work makes modeling assumptions with substantial differences from standard transformer architectures, notably the random weights, the use of a single layer, the lack of softmax, and scalar rather than sequential outputs. The work is upfront those limitations.
While the random features regime for 2-layer neural networks is interesting for studying the representational and generalization properties of certain training regimes, it's well-known that the method (as well as all other kernel-based approaches) fall short when learning even simple learning problems like single-index models. (Or as was argued in Example 1 of this paper, how standard random feature models fall short on sequential tasks whose inputs depend exclusively on $x_0$.) Are there similar illustrative examples that random feature attention units fail to efficiently approximate?
Moreover, when providing examples that separate random feature MLPs and attention models, it may be helpful to account for a particular examples of a target function where the random feature MLP model offers a better error bound, or to make an argument that RFA models will always have superior rates under certain sequential assumptions.