Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper proposes a novel class of random features and provides concentration bounds on the approximation properties for the resulting kernel matrices. The main motivation is to have positive random features because the classical Fourier features have not been performing well in Transformers due the fact that they can take negative values. The latter insight comes from prior work and it could have been discussed in more details here.
strengths_and_weaknesses: #### - originality
The work builds on existing insights and aims at alleviating some issues in approximating self-attention operators in Transformers using random features. The theoretical results appear to be novel and original, though.

#### - quality
It is theoretically sound paper with bounds on the approximation properties of a novel class of random features. It is difficult to tell how sharp these bounds are, (e.g., Theorems 4.2 and 4.3) but the empirical results indicate significant performance improvements over baselines.
A detailed ablation study that would contrast classical random features to the proposed ones relative to a number of hyper-parameters would be useful and it is missing. For instance, I do not see why would one have more benign learning setting in linear regression with random features using the positive variant.

#### - clarity
The paper is mostly clear, but lacks more detailed references to results from prior work. It builds strongly on FAVOR+ algorithm and findings from that paper. However, the review of that work is limited and one would need to read it to completely grasp the motivation.

#### - significance
The approach can bring speeds up when computing self-attention mechanisms and appears to have better theoretical and empirical properties compared to prior FAVOR algorithm. However, this improvement is mostly incremental and is likely to have a limited impact on this class of models.

questions: lines 87-90: when reviewing the features for positive RFs, can you please comment on the resulting kernel that they approximate? The motivating example started with a Gaussian kernel but positive features do not appear to approximate it (or at least this is not trivial to see).

Is there any difference to approximation or numerical properties of random features from Eq. (4) for different values of constants? What is the significance of Theorem 3.1 in this regard?
 
In experiments for Figure 2, can you clarify how the variance is computed? Is this at the level of Gaussian kernel or the softmax kernel in Transformers?
 
 How numerically stable are features in Section 3.2.2 (geometric) given that there is factorial in the denominator? 
 
 Could you review arguments from prior work that would motivate positive random features? It is not trivial to comprehend why such a constraint would be instrumental for the approximation scheme?
 
 Why is FAVOR+ failing dramatically on "Uptraining", Figure 4?

limitations: No ethical concerns.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper aims at suggesting an effiecent and unbiased estimator of the softmax/Gaussian kernel with positive bounded random features.
Hence, they suggest a mechanism, namely, optimal positive random features (OPRFs)t, and a new set of random features (RF) mechanisms, namely chefs’ random tables, that do not apply trigonometric functions.

Theorems 3.1 and 3.2 by the authors show that they can give a significant variance reduction for Gaussian/softmax kernel estimation by computing the variance of OPRF-based estimators.  Theorem 4.2 by the authors use the boundedness of OPRFs to provide the first exponentially small upper bound for the tails of the Gaussian/softmax kernel estimators reliant on positive RFs.
As a result, the first uniform convergence findings for the softmax attention approximation with positive RFs utilizing OPRFs are given in Theorem 4.3.

In contrast to RKSs (Random Kitchen Sinks - techniques that rely on trigonometric nonlinear mappings to approximate shift-invariant), which only asymptotically reduce variance for sufficiently big dimensionality d, the authors demonstrate that orthogonal random projections paired with OPRFs provably reduce the variance of OPRFs for any dimensionality d (see Theorem 4.1). 

Experimental results are also provided.
strengths_and_weaknesses: Strengths
It seems to be a very novel work with a solid theory, the numerical part is also sufficient.

Weaknesses
My only comments are regarding the writing, as someone that is not an expert nor very familiar with the community it was not easy for me.

1. When you write a theoretical paper (or a paper with theorems and proofs), the theory must be fully detailed. Many derivations are not clearly explained, e.g., in equation 16 in the appendix, the authors should explain that the last derivation holds by opening the term (x+sy)^2 and another, what about the one before?
In (19)- part of Proof of Theorem 3.2, many details are missing explanation, it took so much time to understand why things hold, and still, some things are missing for me. Same for Proof of Theorem 3.5, Proof of Theorem 3.2, and others. 

2. The writing in general, is given to an expert in the field, with some additional intuitive explanations, and details - > as someone who is not an expert in this field, it took me too much to understand what is going on, with additional external reading.



questions: Please see my comment regarding the proofs in the appendix. It will be very helpful to explain the derivations done in the proofs.

As I wrote, my only comments are regarding the writing, as someone that is not an expert nor very familiar with the community it was not easy for me, and thus Im very eager to see the other reviewers' comments and authors' responses. 


limitations: I don't consider these as limitations but, as detailed by the authors, it is possible to expand on a few of the techniques discussed in this study, which might result in algorithms that are even more precise.
It is still unclear how to select the theoretically ideal settings for the Generalized exponential RFs system.
review_title: null

final_score: 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.
review_content: summary: The paper introduces Chefs' Random Tables (CRTs), a family of random features (RFs) for unbiased low-rank approximation of attention matrices in Transformer modules with the ultimate goal of overcoming the quadratic time complexity bottleneck associated to computing full-rank attention matrices. Previous random feature methods for this problem mentioned by the paper have either lacked:
- positiveness [2], resulting in numerical instabilities during the computation of the attention matrix normalization factor (the inverse of the row sums, line 102).
- boundedness or even possessing a finite moment-generating function [3], resulting in high variance estimators and inapplicability of Hoeffding or Chernoff-type inequalities for establishing tail-bounds.

These are the main desiderata that the paper sets out to achieve while maintaining unbiased approximation.

The proposed CRT family encompasses two new classes of random features: 

  1) Generalized Exponential Random Features (GERFs), which as the name says, generalizes previous random features defined using exponential functions and Gaussian random projections, and contains as a special case the trigonometric RFs of [1,2] (also often referred to as Random Fourier Features), and the positive RFs of [3] for approximating attention matrices;

2) Discretely Induced Random Features (DIRFs) that lift a discrete probability distribution to a random feature map by making use of the Taylor expansion of the exponential function. 

As a special case of 1), the authors introduce Optimal Positive Random Features (OPRFs) by minimizing the random feature variance with respect to the degrees of freedom of the GERF class over (a subset of) their domain. As an instantiation of 2), the authors propose Poisson Random Features (PoisRFs) and Geometric Random Features (GeomRFs).  Explicit formulas are given for computing the variances of each of these techniques.

Additional variance reduction is achieved by replacing the Gaussian random projections in 1) by block-orthogonal ensembles of random projections as done in [2] and [3]. When combining this technique with OPRFs for attention matrix estimation, the resulting methodology is called FAVOR++ for which a variance bound is established in Theorem 4.1.

Further on the theory side, exponential tail bounds are given for OPRFs both with i.i.d. and orthogonal random projections in Theorem 4.2. In Theorem 4.3 a uniform convergence result is given for the first time for approximating attention matrices with positive random features, specifically for the i.i.d. variant of OPRFs.

Experiments are carried out on:
- synthetic data, comparing the variance of the proposed random features with the previous techniques;
- UCI classification problems by using single attention layer as a mapping from input to class membership probability;
- NLP and speech modelling benchmarks;
- Vision Transformers for testing the performance on a long-range dataset.

The experiments overall demonstrate the benefit of some of the proposed features on these kinds of learning problems.

[1] Rahimi, Ali, and Benjamin Recht. "Random features for large-scale kernel machines." Advances in neural information processing systems 20 (2007).

[2] Choromanski, Krzysztof, et al. "Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers." arXiv preprint arXiv:2006.03555 (2020).

[3] Choromanski, Krzysztof Marcin, et al. "Rethinking Attention with Performers." International Conference on Learning Representations. 2020.

strengths_and_weaknesses: The writing of the paper is clear, and in my opinion it reads relatively well as being somewhat well-versed in both random feature kernel approximations and Transformer models. Although the core theme of the paper is not exactly novel, as it is an extension of previous works, the ideas presented are quite original and interesting.

The paper seems quite strong from a theoretical perspective with various results given for the proposed techniques, although I have not checked proofs in detail. The authors claim that so far no uniform guarantees have been established for positive RF based approximation of attention matrices, which according to my knowledge is true. This should make the paper an interesting contribution to theoretical research on attention layers and Transformer modules. Overall, the theoretical aspect is quite sound, although I do have some questions regarding the practicalities (see Questions).

The main weakness of the paper in my opinion is the range of experiments, such as choice of competing methods and lack of long-range datasets. A strong part of the experiments, however, is that it is demonstrated that the proposed RFs allow backwards compatibility for fine-tuning (uptraining) transformer models pretrained with full-rank attention, which should make it possible to scale and extend models pretrained on smaller datasets to much larger datasets by uptraining with the proposed low-rank technique.

To summarize, the paper is quite interesting theoretically, and the experiments support the benefits of the approach, but I do believe it would benefit from some further comparisons to make it more convincing for practitioners, see the Questions section for more details.
questions: Theory:
- In Theorem 3.3, the minimization problem is restricted to the range when $A$ is real and $s = +1$. The authors mention that this results in positive RFs. I wonder if it is possible to get positive RFs outside of this domain, and if so, do the authors think there could be any significantly lower variance estimators achieved by lifting the domain constraint (potentially highlighting future work)?
- If I understand correctly, the $\rho^\star$ computed in eq.(7) is not what is used in practice when a full matrix is required and not only a single kernel evaluation, but the various squared norm terms present in it are replaced with their expectations over the dataset. Does this affect the theoretical analysis given for the OPRFs in Section 4? In particular, if Theorems 4.1 and 4.2 still hold when $\rho$ is not chosen as being optimal for pairs $\mathbf{x}$ and $\mathbf{y}$? For Theorem 4.3, is it assumed that $\rho$ is chosen this way or some other way? 

Experiments:
- It was unclear to me which method GERF refers to in Section 5.1 and 5.2. According to Theorem 3.1 and the definition above it, it has two degrees of freedom, $A$ and $s$. Was it mentioned how these were chosen and why? 
- In Figure 2, does OPRF refer to the i.i.d. or the orthogonal variant? Regardless, it would be interesting to show both so as to see whether the orthogonal projections really do provide variance reduction in practice as justified theoretically by Theorem 4.1.
-  In Section 5.2, the prediction model used is an attention lookup over the one-hot encoded class labels of training data with testing input as query and training inputs as keys. I understand that the motivation for doing this is to stay within the theme of attention models. I do wonder though if it would be possible to have a proper kernel-based nonparametric model (e.g. SVM or KRR) to demonstrate whether the proposed RFs could be useful for approximating the Gaussian kernel in kernel-based learning tasks? As the theoretical aspect of the paper could be interesting for the wider kernel community, it might be helpful to have some experiments in this direction as well.
- In Sections 5.3.1, 5.3.2 and 5.3.3, I was somewhat missing more alternative methods, since only Performer variants are presented as linear Transformer baselines. There is a wide range of efficient Transformers, and it would be good in my opinion to compare against at least some of these. The optimal method may of course depend on the choice of dataset, see next.
- As it is demonstrated in Figure 4 (Right), full-rank attention is feasible until around 1000 steps, hence the main computational benefits of linear complexity methods only become apparent outside this range. However, although computations can still be feasible, such models can fail to retain long-range interactions. The Long Range Arena benchmark [4] seems to be popular in the community for testing linear complexity Transformers on long-range problems. It would probably increase the impact of the paper if potentially strong results can be achieved on these benchmarks. If it does not perform that well, this experiment could still be of value by potentially pointing out some practical drawbacks of the model, which could further be investigated and explained.

Remarks & typos:
-  Early on in the introduction it was mentioned that positive RFs are required for Transformers as in FAVOR+. The answer to why this is the case was only next provided at the end of page 3. I think it would be useful to have a sentence about why this is needed in the introduction being that it is one of the main motivating factors for the paper as discussed in lines 40-41.
- In Line 59, a $-$ sign is missing within the Gaussian kernel formula

[4] Tay, Yi, et al. "Long Range Arena: A Benchmark for Efficient Transformers." International Conference on Learning Representations. 2020.
limitations: The authors have adequately discussed this.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: 
In this paper, the authors propose two alternative schemes of positive random features for Gaussian (Softmax) kernel approximation. i.e., the Generalized exponential RFs and the Discretely-induced RFs.  Variances for both approximations are given.  The authors further show the variance reduction of the OPRFs (a special case of GERF) with orthogonal samples holds for any $d>0$ instead of asymptotically only large $d$ in literature.  A uniform convergence result is proved for (low-rank transformer) attention approximation.
strengths_and_weaknesses: 
Pros.
1.  The proposed OPRF scheme seems promising for constructing positive and bounded random features, which may have the potential for accelerating Transformer while maintaining stable training.

2. In the experiments, the variance reduction is surprisingly significant (up to $e^{60} times). 

3.  The paper is well organized and well presented.

Cons. 
1.  It seems that the discretely-induced RFs are sensitive to outliers because the requirement $c_l= min_i min ( \boldsymbol{x}^{(i)} ,\boldsymbol{y}^{(i)}    ) - \epsilon $ in Line  181. Moreover, it is not rotation invariant, i.e. the approximation change when the data distribution ratotated.  Note that  Gaussian kernel and softmax kernel are rotation invariant.

2. Some symbols in Theorem are given without definition e.g., $C(\|\boldsymbol{x} + \boldsymbol{y} \|)$  in Theorem 4.1.
questions: 
1. Does the proposed OPRF and discretely-induced RF scheme still construct positve RFs for new data instead of the given data $\boldsymbol{X}$? Note that $\boldsymbol{c}$ and statistics computed from a given set $\boldsymbol{X}$.  They may change for a new data $\boldsymbol{z}$.  As $c_l= min_i min ( \boldsymbol{x}^{(i)} ,\boldsymbol{y}^{(i)}    ) - \epsilon $,  it may be more sensitive for the new data or distribution shift.

2. The variance reduction performance surprised me. However, the discussion in Section 5.1 is quite limited. Could the authors discuss more the experiment in Figure 2? Why the GERF achieves so significant gain?  It seems that the baselines in the top rows are different from that in the bottom.  Could the authors plot them together for better evaluation? Could the authors provide the comparison of variance w.r.t the number of features ($M$)?
limitations: NA
review_title: null

Meta-review: metareview: The primary motivation of the paper is the scalable training of transformers, particularly their efficient softmax-attention approximation (3). As a classical approach relying on trigonometric random Fourier features (RFF) does not guarantee positivity (which makes the training of transformers unstable), the authors consider non-trigonometric RFFs. Particularly, they propose a GERF (generalized exponential random features, specified in (4)) for the approximation of the Gaussian kernel (and the softmax kernel) which beyond the previously designed positivity of RFFs [15], can also ensure the boundedness of the random features. They analyze when these RFs give rise to unbiased kernel approximation (Theorem 3.1), establish their variance (Theorem 3.2 for fixed (x,y) inputs), and restricting its free parameters (A to be real, s = 1) they specialize the design to the minimum variance estimator referred to as OPRF (optimal positive random feature). They show tail bounds (Theorem 4.2) and attention approximation guarantees for OPRFs. They also present a DIRF (discretely-induced random features) construction with focus on the Poisson and Geometric designs, which with a shift (Section 3.2.3) can be turned to be positive. The resulting CRT (chefs' random tables) kernel approximation family is illustrated in classification (on UCI benchmarks) and in training transformers (in NLP, audio and image context).

Kernel methods are without doubt at the forefront of machine learning; developing new kernel approximation schemes is of significant interest to the NeurIPS community. As it was assessed by the reviewers, the authors present novel and valuable theoretical insights in this respect, with convincing numerical illustrations. As the reviewers pointed out the manuscript could be improved somewhat by (i) more detailed references to results from prior work, and (ii) making it more accessible to wider audience. Please incorporate these comments in the final version of the manuscript.
confidence: Certain
Decision: Accept