Chefs' Random Tables: Non-Trigonometric Random Features
Authors: Valerii Likhosherstov
Krzysztof Marcin Choromanski
Kumar Avinava Dubey
Frederick Liu
Tamas Sarlos
Adrian Weller
Venue: NeurIPS 2022 Accept (2022)
Keywords: random features
gaussian kernel
attention
Transformers

Abstract: We introduce chefs' random tables (CRTs), a new class of non-trigonometric random features (RFs) to approximate Gaussian and softmax kernels. CRTs are an alternative to standard random kitchen sink (RKS) methods, which inherently rely on the trigonometric maps. We present variants of CRTs where RFs are positive, a key requirement for applications in recent low-rank Transformers. Further variance reduction is possible by leveraging statistics which are simple to compute. One instantiation of CRTs, the optimal positive random features (OPRFs), is to our knowledge the first RF method for unbiased softmax kernel estimation with positive and bounded RFs, resulting in exponentially small tails and much lower variance than its counterparts. As we show, orthogonal random features applied in OPRFs provide additional variance reduction for any dimensionality $d$ (not only asymptotically for sufficiently large $d$, as for RKS). We test CRTs on many tasks ranging from non-parametric classification to training Transformers for text, speech and image data, obtaining new state-of-the-art results for low-rank text Transformers, while providing linear space and time complexity.

Chefs'
Random Tables: Non-Trigonometric Random Features
Valerii Likhosherstov
Krzysztof Choromanski Google Research & Columbia University kchoro@google.co com
Avinava Dubey Google Research
University of Cambridge v13040cam. ac.
Frederick Liu Google Research
Tamas Sarlos Google Research
Adrian Weller University of Cambridge & The Alan Turing Institute
Abstract
We introduce chefs' random tables (CRTs), a new class non-trigonometric random features (RFs) to approximate Gaussian and softmax-kernels. CRTs an alternative to standard random kitchen sink (RKS) methods, which inherently rely the trigonometric maps [46]. We present variants of CRTs where RFs positive, key requirement for applications in recent low-rank Transformers [15]. Further variance reduction is possible by leveraging statisties which are simple compute. One instantiation of CRTs, the optimal positive random features (OPRFs), is knowledge the first RF method for unbiased softmax-kent estimation with positive and bounded RFs, resulting in exponentially small tails and much lower variance than its counterparts. As we show, orthogonal random features applied in OPRFs provide additional variance reduction for any dimensionality d (not only asymptotically for sufficiently large d, as for RKS). We test CRTs on many tasks ranging from non non-parametric classification to training Transformers for text, speech and image data, obtaining new state-of of-the-art results for low-rank text Transformers, while providing linear space and time complexity of the attention.
1 Introduction & related work
The idea that nonlinear mappings of the random-weight linear combinations of data features can be used linearize various nonlinear similarity functions transformed kernel methods. This led to the development of Random Kitchen Sinks (RKSs) techniques; and the new field of scalable kernel was born. RKSs were subsequently used
algorithms, introduced in the paper trilogy 47
45
46),
in many applications, ranging from kernel and function-to-function regression [1] 33 41, SVM
algorithms [50] operator-valuee and semigroup kernels [36] 62], neural networks 25 61
27
and even differentially--rriatt ML algorithms control Random features (RFs) are subject of much theoretical analysis 34
[9]. as well as (very recently) nonparametric adaptive
63
51 48
To approximate shift invariant (c.g. Gaussian, Cauchy or Laplace) and softmax kernels, RKSs rely on the trigonometric nonlinear mappings provided directly by Bochner's Theorem (36) Trigonometric
RFs provide strong concentration results (e.g. uniform convergence, see Claim in 45 but suffer from weakness that noted recently they not guaranteed be positive. This makes them in scalable Transformers relying on implicit attention
unsuitable for approximating softmax-attenn via random features [15). As noted in (15), trigonometric features lead to unstable training, they yield poor approximations of the partition functions applied to renormalize attention and involving
Equal contribution
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

CRT
GERF
DIRF
-20
TrigRF
PosRF
OPRF
(
128
orthogonality
GeomRF(
256
312
Transformers
85
20
40
30 80
300
FAVOR
FAVOR FAVOR
Figure I: (left) A map of RF methods for the Gaussian kernel approximation. Existing RFs (Section 2.2 RFs proposed in this paper. (right) The utility function l (defined the logarithm of the ratio of the variance of OPRF and PosRF mechanisms for the Gaussian and softmax kemel cstimation) as function squared length the sum kernels' inputs | + y1 (smaller values imply larger gains coming from OPRF). Different curves correspond to different dimensionalities. Based on the plots, OPRF's have > d times smaller variance when d = 64, X y = 100 (configuration taken from the standard Transformer application).
several small softmax kernel values. To address this, 15 proposed a new method for unbiased softmax kernel estimation with positive RFs, the so-called FAVOR+ mechanism (Fast Attention Via Orthogonal Random Positive Features), as opposed to FAVOR using trigonometric RFs (as in 13 Positive random features guarantee that the denominator self-attention sum of positive numbers, hence it cannot be negative or too small.
Unfortunately FAVOR+ features not bounded, and worse, the moment generating function of the corresponding softmax kernel estimator is not finite. Consequently, no concentration results beyond those involving second moment methods (variance bounds) have been provided for FAVOR+. Despite active research on constructing new RFs for implicit attention in Transformers 12 I7]. the following questions of great practical importance remained open:
Does there exist an unbiased estimator of the softmax/Guusiaa kernel relying on positive and simultaneously bounded random features? Can it be efficiently constructed?
We answer both questions affirmatively in this paper, introducing new mechanism called optimal positive random features (OPRFs). We propose other RF methods that, as OPRFs, do not apply trigonometric functions and provide positivity. We call this new set of RF mechanisms chefs' random [ left). The new OPRF-based method for fast self-attention approximation, applying addition block Hotckoorthogonal random projections, referred to as FAVOR++.
tables (CRTs, see Figure
We compute the variance OPRF-based estimators (see Theorem 3.1 3.2 and show that they can provide e 60xx variance reduction for Gaussian/softmax kernel estimation (see Figure Tp. We give the first exponentially small upper bounds for tails of the Gaussian/softmar kernel estimators relying on positive RFs, leveraging boundedness of OPRFs (see Theorem 4.2 Consequently, using OPRFs we give the first uniform convergence results for softmax attention approximation with positive RFs (Theorem 4.3)) We show that orthogonal random projections combined with OPRFs (leading to FAVOR++) provably reduce the variance of OPRFs for any dimensionality (see Theorem (4.1) as opposed only asymptotically for large enough which is the case for RKSs. Finally, we provide extensive empirical evaluation in Section 5) for Transformers (text, image and speech domains), establishing new state-of-the-an th-the-art results for low-rank attention Transformers for text.
2 Prerequisites
2.1 The definition of random features
Let x, E Rd be real vectors and K yxx - be Gaussian kernel where || denotes the Lg-norm. By random features (RFs).oo the Gaussian kernel we denote two functions (w, (w. (ww, Rdd x Rd > C where w is random vector from some distribution p(w) on Rd. Functions f(-) (w,) x) satisfy the following:
K(x,y) Re (1))
for all x, E R where Re (.) denote the real part complex number (Im (.) for the imaginary part). The decomposition ! can be used for unbiased approximation of the linear operator

---

K= (K(((), y())) y L. E R L where x yyu) E R.
Such linear operators emerge in various
applications, e.g. kernel SVM 45,, kemel regression 38
59
or Transformers [T5]
(see Section 2.3
For any c E R2,, evaluating Kcc naively would result in ( time complexity which is prohibitively expensive for large L. Instead, can the Monte Carlo approximation: draw i.i.d. samples wi...,, WM ~ p(w), where M < L, and compute for 1 siss L:
M
(Kc); = Σ ((x ylinee
Re
(w()
(wims (wim.)())) Cj
M
/=1
17
M
1 M
Re
(w/ms
x
( (wmm
Therefore, ICc can be approximated by first precomputing {Σ/=1 (w), y (())))))))))))))))) jog JM m= and then evaluating 2 in O(dML) total time. Precision of this approximation can be theoretically bounded [45] [5] In this manuscript, we will use the variance Varp(w) (f (f()
f(2) (w.y)) of (I) to judge the precision of the Monte Carlo approximation. Since samples Wi..... WM are i.i.d., the num-
ber M of RFs controls the tradeoff between the total variance Var........ (...) = M Var (...) (inversely proportional to M) and number of computations (directly proportional to M).
The softmax kernel is defined as: Kstm y) exp(xTy). and can be easily derived from the Gaus- Thus, in particular, any RF mechanism for the Gaussian kernel immediately transfers to the corresponding one for the softmax kernel and vice versa. Thus from now on, unless explicitly stated otherwise, the estimators we consider are approximating the Gaussian kernel.
sian kernel K as follows: Katm (xfm(x.)) = exp( x /2) (x. y)
2.2 Existing trigonometric and positive random feature methods
Here we summarize existing RFs for Gaussian kernel estimation. Trigonometric RFs (TrigRFs), the core of RKSs 45 and FAVOR 13, are defined as follows: stng (w: x) = exp(iwTxx, [ (w. exp(-iw Ty), Perig(() (w) OO,,, [u) where denotes an imaginary unit (as opposed to the index
notation i), 0g E Fd is vector of zeros and Ld E dddd is an identity matrix. The variance of these Re (fuii (w, (.,x))((l y)) (1 (xx,))?)
RFs has the following form 11 Var (an)
[5] the key ingredient of the FAVOR+ mechanism, are defined as follows: pood (ws, x) = Spea (wi x) exp(w x ||x||²), Pwos(w) ~ (O,, Their name is due to the fact that spld (w., x), spos (w, y) are always positive real numbers. PosRF variance has the form 15
Positive RFs (PosRFs)
Var Varppoa(w>) good (w:, x) x)Sped (w:) exp(4x Ty) y(
2.3 Random features for scalable Transformers
One recent application of RFs is in the area of scalable Transformers for processing long sequences 15].
Let L be the length of the sequence. Interactions between elements in Transformers implemented via the self-artention mechanism. Given three matrices Q.K. attention mechanism returns the following result:
K, V E R RLxd the self-
Y softmax(d 1/2 Q2"K" V diag(Ke 12) Kotm V, Kstin (Kstm (x,, (x))
(3)
where 11 R is a vector of all ones, ( d-1//40 1 (i'th row of Q) and y(i) d 1/ K
1 < i.j & L. We deduce that computing (3) reduces to applying the linear operator Kalm to d +
vectors: It, V......, V.dd Hence, when 7, is large, RF approximation similar to (2) but for the
Ketm (---) kernel can reduce the computational complexity from Odd2² to O L).
Importantly, when the approximation (2) with the replacement + Kastm can take negative and/or near-zero values, training unstable since this approximation emerges in the denominator (inversed)
term diag(Kam I.) in (3). One way to address this is to restrict (1) (L0, x) and (2)) y) to always map into strictly positive numbers R+ This is where PosREs introduced in 2.2 are particularly
relevant.
3

---

3 Chefs' Random Tables
We are ready to present our mechanism of chefs' random tables. All proofs are in the Appendix.
3.1 Generalized exponential RFs (GERFs) & optimal positive RFs (OPRFs)
Our first goal will be to generalize both trigonometric and positive RFs. Then we will focus on one special case of this generalization, that will directly lead to the FAVOR+ mechanism.
We will be looking for RFs of the following generalized exponential form for par(w) ~ NO Ia):
[GE(W, x) D exp(A||w) + Bw x + 1))
(4)
(w) = D exp(AA| + sBw y + Clly
where A, B,C.C. C, E C and E (-1,+1]. It can be seen that = = 0, corresponds trigonometric RFs and A 0, I,
1, corresponds positive
RFs. The next theorem describes the conditions under which fog can be used to approximate the Gaussian kernel.
Theorem 3.1. (GE(w) and s(.) defined in (4) satisfy if
Re 1 4A) 00, B= B= 4A), C= -s + 1)/2,
D (V1 4A)4,
(5)
where V: and v denotes principal root if the argument is complex.
Hence, A and s can be treated as free parameters and B, C, D as dependent ones. The variance of these RFs can be expressed through A and follows:
Theorem 3.2. Let Re (1 - -A) > 0. The variance of ( using PGB (w), SGe is given as
(1) Var Varpae(w) Re [G (w. x) (w)))
1
exp (-(s (s + 1) (|xx||++||>1)) 11x1111)
2
x (Re an exp 02||x + uyll -xyl²) + 0r exp aalll + sy|( = y)
(6)
where α1
(V++
16,4 1-8A
02 (++ (s+ 0g (1+
a -RR
04 =
ا+211-14 2(I
While it is unclear how to find global minimum of the objective (6) with respect to A E C, Re (1 8A) restrict A to be a real number and fix -1.
and s E {-1,+1}, we observe that it's possible to find an optimum when we
Theorem 3.3 (Minimum variance). When s = +1, A is restricted to be a real number and y| 0, the variance
(6) is minimized when A = (1 - 1/p")/8 where 0 < p²
p² (V(2) (2] d)² + 8d][x + y/1² - 2||x + y11 -d) a) (411x
Note: One can show that A < 0 for x + -y thus the corresponding estimator is bounded since the term A A||w>| 1 prevails over linear terms Bw and sBw y in (4). When ||x +yIl + 0 then p" and thus A + O. Therefore for x = -y the mechanism reduces to PosRF described in Sec. 2.2 expected, since for yy PosRFs provide perfect estimation (variance equal to zero). Larger values of |x yyl lead to larger gains coming from the new mechanism.
From (5) it can be inferred that B, C, D are real when is real and s +1. Hence, f()) (w, x). f(2) (w, y) are positive real numbers in this case. Furthermore, s +1, 0 corresponds to positive RFs. Therefore, we refer to RFs with A defined according to ( as optimal positive RFs (OPRFs). Figure right illustrates the analytical variance reduction achieved via OPRFs.
In practice we are given sets {)) {y6)) instead of single pair x, y. For this reason, in
we can use the averages of ||2 (112, (|x(*) + sy instead of ||x||=. ||y 122 ||x + sy
This heuristic is based on the assumption that all (x and {y()) are homogencous and (x))

---

|1? ||x(1) + 11 are tightly concentrated around their mean. Computing averages of ||x || takes (LL) time. Using the formula below, the average of ||x( + sy can be computed with the same complexity:
x 132
Σ
x
2s L
x(())
Σ y(1)
by 10 (8)
D
The closed-fore solution for real A and s = +1 allows O(1)-time optimization of 66) after precom puting these statistics. In the general case to A E C and E { (-1, 1, +1}- Using precomputed statistics, each evaluation of (6) takes O(1) time. As long the total number of these evaluations is (L + n)), where is the number of K. or Kutm evaluations (n = + in Section 2.3 it does not affect the total complexity.
rely numerical optimization of (6 with respect
The next class of mechanisms, if implemented straightforwardly. does not give positive-valued RFs but, as we explain Section 3.2.3 can be easily transformed to variants providing positivity.
3.2 Discretely-nnuuced random features (DIRFs)
Take discrete probabilistic distribution p(w) where w1,.... Wa are i.i.d. with P(wy k) pk. 00
k = and pt: > 0 for & E {0} U.N. Note that, by Taylor series expansion of exp(-),
| 2
y
x Puk!
k(x,y) exp(
exp
exp(x y)
Pk
E
X
Yi
(9)
E=1
where x1= x pun = y² - Thus we can define discretely-induced random
features providing Gaussian kernel estimation as follows:
| 2
(w, = 507 (w, fDI(W, exp(
II x;" (wi!) 1=1
(wi!))+p=? +
(10)
Different instantiations of the above mechanism are given by difffernnt probabilistic distributions {P&]. We will consider two prominent special cases: (a) Poisson, and (b) geometric distributions.
3.2.1 Poisson random features (PoisRFs)
If (Pk) is Poisson distribution, i.e. Pk - (0) U, then the corresponding RFs defined as: ppuis (w, x) Speis fwo (w,x) x) = Spois (w, x) = e >d/2-11x1
I x A
x -
Theorem 3.4. Variance of (2) with Ppois fpois given
d Σ xiy? -|x1|2 ||x||=-|xx|** ||x/13
Var (w) (Spois (w, (ooss =exp (
-11x11)))K(xxx)) -x(x,))
(11)
The exp argument in 11 is convex function of À 0. By setting its derivative zero, find gives the minimum of
that d 1/2 (d x/2
When, instead of single pair x, y, sets (x!*). (5) are provided, we can use the same homogeneity assumption as in Section 3.1 and substitute the average of (x (yy)"))))))))))))))))))) over 1 < i,j s L
instead of Dd x7y?. This average can be computed efficiently in O(Ld) time as follows:
L d x
L-2
Σ
Σ
[xx1))
(12)
After computing this statistic, calculate X" in O(1) time using the analytic formula.
5

---

3.2.2 Geometric random features (GeomRFs)
If {ps} is geometric distribution, i.e. Pk p(1 - p)., h E {0} UUNNN N, for parameter 0 <
p 1, then the corresponding RFs are defined as: fgeom (o,om(wxx)) (w, Ig (ws, x) = Sgoam (w, x)
p=d/2e ||x]|//2 x pp) (w)=))
x
Theorem 3.5. The variance of (2) with Preom Sroom given as
d y)) de |xxl| [xxl(--Xx0 Iyll
Var Var Preco (w) (ggeom
-) (xxx))))) (13)
where To(-) is the modified Bessel function of the first kind of order O.
Again as for the previously described mechanisms, when sets (x("), {yli)} are given, we can use
(i) averages of [x] Yi S S d, instead of [xyy|| in (13 assuming homogeneity of x())ss and y())ss Each out of d averages can be computed in (()) time as follows:
L Σ
= L-
Σ xx
Σ
ly 10
(14)
After precomputation of these statistics, evaluation of takes ((d) time. A numerical optimization can be used to minimize (II) with respect to As long as the number of variance evaluations is O(L + n/d)), the total complexity estimate is not affected.
3.2.3 Making diseretely-indueed RFs positive
As can be inferred from Eq. 10 DIRFs are positive when all elements x and y are positive. this is not the case, and positive-valued RFs are needed, e.g. in applications involving scalable Transformers, one way to make them positive to take some vector Idd such that C₁ Xi,
An example of such a vector is given by = min; min(x) y where > 0 is small
constant. Next, define (+) = x") c. 5() y
Then, clearly, x -5(ر ( - -O),,
K ((((,, (0))= = ((x(9) (())) and RFs can be used on 2 fo(d) which have positive entries. We
refer these variants of PoisRFs and GeomRFs PoisRF+ and GeomRF+ respectively.
Additional theoretical results & FAVOR++
Interestingly, in the case of the PosRF mechanism from [15. OPRFs also benefit from applying
block-orthogonal ensembles of projections w (see Appendix 9.1 and [5] for the exact definition). (which is the We show below that orthogonal RFs reduce the variance of GERFs with A e R, case for OPRF) for any d >
Theorem 4.1 (Orthogonal OPRFs). Var M (x,y)) denotes the variance of the orthogonal GERF estimator Kort y) of the Gaussian kernel with A E E, s in (4) at x, E IRd using M RFs y)) is the analogous expression with i.i.d. samples, then for some C(Ixx + yll) 2
and Var K iid M
2 M d 2 c(I + +l))
Rud Var Roott (x, S Var Ri (x. y)) -
(15)
The analogous inequality can be obtained for TrigRFs only in the asymptotic sense (for large enough, see Theorem 3.8 in (14). One of the key properties used in the proof of Theorem 4.1 is positivity of RFs. We conclude that positive-valued RFs are particularly well suited for the quasi Monte-Carlo methods based the orthogonal ensembles. Analogously FAVOR+ (155), refer to the self-attention approximation mechanism based on orthogonal OPRFs as FAVOR++.
Note:
We now provide strong concentration results for the OPRF-based estimators critically relying the boundedness OPRFs. Boundedness of OPRFs is due to A = (1 1/p)// < even when |x + y is substituted by average (8) in 7 To the best of our knowledge, these are the first such results for positive-valued RFs. Denote by the Legendre Transform of the random variable Z = - (w, x) x) (w, y) for f() as in (4) with A, B, C, D E IR defining GERFs.

---

normal
sphere
heterogan
mnist
-2
-30
-50
Pelst
CEAF
ggr
-6
-100
-20
-100
GeamAF
-0
-130
10th
rorma pos-valued Rfs
sphere, pos. valued RFs
beceragen, p05 valued RFz
mriitt p35.va und RFs
40
-10
-100
Pols
-109
Goo 1RF
10
Figure 2: Log-variance of different RF mechanisms, mean and standard deviation. For each sampling method, we plot the results for non non-posiiee con-posiiive and positive RFs on separate plots for 0.1 S a
Theorem 4.2. Suppose A < 0. The following is true for any > 0: (/ - K y)) 2 c) I 2exp( Mr²
M
+1vl++ (11 4A)-4). Furthermore, for the orthogonal variant we have: S (xpp-MM(((xx))) +)) and (xK(x, + +)) > 0.
2 exp(
2A
( ((x))
Finally, below we provide the first result regarding uniform convergence for attention approximation the efficient low-rank Transformers (Section
Theorem 4.3 (Uniform convergence for attention approximation), Assume that rows of Q and
K from 3) come from the Lz-ball of radius R > O. Denote by Kaim the approximation of Katm via the GERF-mechanism with A < O using M independent random projections. Then Resttnllo oo with any constant probability when M 22( A (og((2)), where:
from 3
T=exp(
VdA p 22d y = - 4A))* /AT( Va d2) (for A as the OPRFs definition).
3n²
Experiments
We present an extensive empirical evaluation of CRTs. Additional details and results for each experiment can be found in the Appendix 9910
5.1 Comparing variance of CRTs for Gaussian kernel estimation
In this initial experiment, we sample synthetic pairs of vectors x, y and evaluate variance of CRTs based on the analytic formulas (6 13). Our goal is to check whether there are scenarios when the newly introduced RF mechanisms have smaller variance than existing TrigRF and PosRF methods. We set d = 64 which is standard in e.g. Transformer applications (Section 2.3). We use four different regimes for drawing x, y: normal corresponds to x.y sampled from A (O,, o LLa), sphere corre- sponds x, y sampled uniformly on sphere sdd- heterogen corresponds
x and y sampled from two heterogeneous distributions: (0,,, o IL))) and (oll,, o I²I)) and mnist corresponds to y being random images from MNIST dataset [19 resized x 8, scaled by a > 0 and flattened.
In many scenarios (see Figure 2 CRT's outperform TrigRF and PosRF baselines. Among other improvements, GERF gives more than 80 e_2 e0 times variance reduction compared to TrigRF in normal, heterogen and mnist when a = 1. OPRF and GeomRF+ give more than e 125 e times variance reduction compared PosRF in normal, heterogen and mnist when 1.
5.2 Comparing CRTs in the non-parametric classification
Our next experiment is a non-parametric classification where probabilities predicted by kernel
regression [38 59 with the Gaussian kernel. Training data consists of objects o!!) ..... (L) E I with corresponding one-hot encoded labels r (1) (T.) E I". The predicted label distribution for the new object o" is defined r" E K(oo", (00 / K K(oo", (1) where 0
7

---

Table Non-parametric classification, test accuracy (%). M
128.
The best result, second best.
Dataset
TrigRF
PosRF
GERF
PoisRF
GeomRF
OPRF
PoisRF+
GeomRF+
L
abalone 39
12.0
16.0
17.0
18.0
18.3
17.1
14.0
15.1
3758
banknote
22
66.2
83.4
92.4
84.4
94.5
92.6
80.1
85.6
1233
[
66.3
69.2
70.9
66.3
66.3
69.5
66.3
67.2
1554
yeast
29.7
34.4
42.9
36.9
35.9
44.4
29.7
31.0
1334
cmc 35
46.6
45.1
47.8
46.6
47.3
46.3
35.5
43.5
1324
nursery 40
31.3
77.4
63.8
77.1
77.1
78.9
77.3
71.0
11664
wifi 47
15.2
88.8
93.3
95.3
95.8
93.3
77.2
82.9
1799
chess 2
16.5
20.2
20.4
19.1
19.5
20.2
19.2
22.5
25249
Average
35.5
54.3
56.1
55.5
56.8
57.8
49.9
52.3
N/A
hyperparameter tuned on the validation set. Using the RF approximation for the kernel in (), we, with O(nLM) preprocessing, can approximate r* in (nnM) time per example instead of (nL) for the exact computation.
Since the predicted class argmax <I<. we can ignore the denominator term and, therefore, use non-positive RFs. We evaluate on classification benchmarks from UCI Repository (24) (Table [T]. The best results are achieved by new RF mechanisms, with GeomRF and OPRF performing particularly well. OPRF shows the best average performance, therefore our recommendation for practitioners is to opt for this method. For the same reason, we focus on the FAVOR+ variant (OPRF with orthogonal random projections for attention approximation) in our Transformer experiments below.
5.3 FAVOR+ in scalable Transformers
5.3.1 Natural language processing
In this setting, we different low-rank attention Transformers on the General Language Understand- ing Evaluation (GLUE) benchmark (57), consisting of 8 different natural language understanding tasks with the sequence length ranging from 32 to 128. We used the same training parameters as mentioned in [20] (see Appendix 9.13. for details). We compared FAVOR+ [15), ELU [31] and ReLU [T5 variants of the Performers 15] against a FAVOR++ variant and report the results in Table 2 We find that FAVOR+ outperforms all these low-rank Transformers in most GLUE tasks. In particular, FAVOR+ outperforms FAVOR+ on GL.UE tasks, demonstrating downstream effectiveness of the variance reduction of the softmax kernel estimation. Furthermore, warm-starting with pre-trained BERT-base model checkpoint [20] (Uptrain +AVOR+ in Table further improves performance demonstrating backward-compattiiltt of FAVOR+ with the exact softmax kernel.
5.3.2 Speech modelling
We compare FAVOR+ with FAVOR+ speech models with the LibriSpeech ASR corpus 42 We apply both to approximate attention blocks in the 17-layer Conformer-Tranee Transducer encoder (26) of only 4 attention heads and use the word error rate (WER) metric a standard way evaluate speech models. In both cases FAVOR+ outperforms FAVOR+, as shown in Figure 3 The WER
Table 2: GLUE Dev results base sized models. Number of training examples is reported below each task. MCC score is reported for CoLA, Fl score is reported for MRPC, Spearman correlation is
reported for STS-B, and accuracy scores are reported for the other tasks. The best result, second best.
System
MNLI
QQP
QNLI
SST-2
CoLA
STS-B
MRPC
RTE
392k
363k
108k
67k
8.5k
5.7k
3.5k
2.5k
FAVOR+ 15
80.26
89,53
87.13
90.58
53.17
85,07
83.82
67.59
ELUB1
80.72
90.05
89.09
91.51
48.43
86.68
85.05
68.59
ReLUIK
15
81.39
90.11
88.85
91.97
52.08
87.64
84.56
67.51
FAVOR+
81.25
90.15
89.8 19.58
92.00
54.95
85.62
85.78
67.87
Uptrain FAVOR+
82.29
90.43
89.73
92.20
58.85
85.90
88.73
67.63

---

Normalizes semaaizzed WER (x 10 2)
7
16
TAVOR+ +AVOR++
7
FAVOR+
TAVOR+
Normalizee lized WER
5.5
5.5
20
40
60
80
10
20
30
40
50
Number of Steps (x 10*)
Number of Steps 10*)
Figure 3: Comparison of the Conformer Transducer encoder with FAVOR+ and FAVOR+ attention on the LibriSpeoch 42
corpus for M = 16 and M = 8 RFs. We used common word error rate (WER) metric.
82.96%
8
Num. steps per second
MAVOR
78.29%
FAVOR+
77.48%
Softmax
Accuracy
Softmax OOMed >1600
70
2
FAVOR
FAVOR++
61.06%
60
500
1000
1500
2000
scratch
Uptraining
Sequence length
Figure 4: Image- Transforrafo experiments. Left: Accuracy of training FAVOR+ and FAVOR+ on ImageNet from scratch and fine-tuning from softmax MAE pre-trained weights (Uptraining). Right: Comparing sequence length number steps per second for FAVOR+, FAVOR+ and regular Transformer variant (Softmax).
improvement for FAVOR+ is substantial: 2.49% for M = 8 and 3.05% for M 16 with negligible (Ld) & (LMMd) overhead for computing 8 compared to FAVOR+.
5.3.3 Vision Transformers
To further showcase the need for more accurate softmax kernel approximation, we compare the performance FAVOR+ and FAVOR+ on ImageNet (188). We inject both mechanisms to the attention modules of Vision Transformers (VIT (21)). In Figure we show the results of training from scratch and uptraining from the MAE checkpoint [29]. We see that, as opposed to FAVOR+, FAVOR+ is more stable and is able to improve performance especially for uptraining, demonstrating backward-compatiblity with the exact softmax kernel.
Finally, we compare the computational complexity of FAVOR+ and FAVOR++ In Figure 4 the right plot shows the number steps per second as function of sequence length on the same hardware. We see that attention modules using FAVOR+ and FAVOR+* have very similar computation time (both provide linear attention). Moreover, for sequence lengths above 1000, training a regular ViT model became increasingly difficult due to out-of-memory errors.
Limitations of this work & broader impact
Several of the mechanisms proposed in this paper can be further extended, potentially leading to even more accurate algorithms. For instance, it remains an open question how to choose theoretically optimal parameters for GERF and GeomRF mechanisms. Furthermore, DIRFs can benefit from optimizing the discrete distributions defining them (to minimize variance of the estimation) rather than choosing them priori. Our methods should be used responsibly, given rising concerns regarding the carbon footprint of training massive Transformer models and other socictal issues [49
3 60

---

7 Conclusion
We presented a new class of RF mechanisms called chefs' random tables (CRTs) including methods providing positivity and boundedness of random features two key properties for new applications of RFs Transformer training. We provided comprehensive theoretical results and extensive empirical evaluation, resulting in particular in new state-of-the-art low-rank attention Transformers for text.
8 Acknowledgements
V. L. acknowledges support from the Cambridge Trust and DeepMind. V. L. was part-time employed by Google while a PhD student. W. acknowledges support from a Turing Al Fellowship under EPSRC grant FPP/V22579//1 The Alan Turing Institute, and the Leverhulme Trust via CFI.
References
[1] Haim Avron, Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker, and Amir Zandieh. Random Fourier features for kernel ridge regression: Approximation bounds and statistical guarantees. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 253- 353-262. PMLR, 2017.
[2] Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer, 2020.
[3] Emily M. Bender, Timnit Gebru, Angelina McMillan-Major and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big? Proceedings of the 2021 ACM Conference Fairness, Accountability, and Transparency, FAccT '21, page 610-623, New York, NY, USA, 2021. Association for Computing Machinery.
[4] Nicholas M. Boffi, Stephen Tu, and Jean-Jacques E. Slotine. Nonparametric adaptive control and prediction: Theory and randomized algorithms. In 60th IEEE Conference on Decision and Control, CDC 2021, Austin, TX, USA, December 14-17, 2021, pages 2935-2942. IEEE, 2021.
[5] Marko Bohanec and Vladislav Rajkovič. V.: Knowledge acquisition and explanation for multi-attribute decision. In Making, 8 th International Workshop "Expert Systems and Their Applications, 1988.
[6] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Bandderman-Milng and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018.
[7] Richard Brent. An algorithm with guaranteed convergence for finding zero of function. Comput. J., 14:422-223 425, 1971.
[8] Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voos Kather- ine Lee, Adam Roberts, Tom B. Brown, Dawn Song. Úlfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. CoRR, abs/2012.078855, 2020.
[9] Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. J. Mach. Learn. Res., 12:1069-1100 1109, 2011.
[10] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers, 2019.
[11] Youngmin Cho and Lawrence K. Saul. Kernel methods for deep learning. In Yoshua Bengio, Dale Schuurmans, John Lafferty, Christopher I. Williams, and Aron Culotta, editors, Advunces in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of meeting held 7-10 December 2009, Vancouver, British Columbia, Canada, pages 342-350. Curran Associates, Inc., 2009.
10

---

[12] Krzysziof Choromanski, Haoxian Chen, Han Lin, Yuanzhe Ma, Arijit Sehanobish, Deepali Jain, Michael S. Ryoo, Jake Varley, Andy Zeng, Valerii Likhosherstov, Dmitry Kalashnikov, Vikas Sindhwani, and Adrian Weller. Hybrid random features. In International Conference on Learning Representations (ICLR), 2022.
[13] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Jared Davis, Tamás Sarlós, David Belanger, Lucy J. Colwell, and Adrian Weller. Masked language modeling for proteins via linearly scalable long-context transformers. CoRR, (as/2006.03555. 2020.
[14] Krzysztof Choromanski, Mark Rowland, Tamás Sarlós, Vikas Sindhwani, Richard E. Turner, and Adrian Weller. The geometry of random features. In Amos J. Storkey and Fernando Pérez- Cruz, editors. International Conference on Artificial Intelligence and Statisties, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, volume 84 of Proceedings of Machine Learning Research, pages 1-9, PMLR, 2018.
[15] Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers. In International Conference on Learning Representations, 2021.
[16] Krzysztof Marcin Choromanski, Mark Rowland, and Adrian Weller. The unreasonable effec- tiveness of structured random orthogonal embeddings. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 219-228, 2017.
[17] Sankalan Pal Chowdhury, Adamos Solomou, Avinava Dubey, and Mrinmaya Sachan. On learning the transformer kernel. CoRR, abs/21 10.08323, 2021.
[18] Jia Deng, Wei Dong. Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hicrarchical image database. In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA, pages 248-255, IEEE Computer Society, 2009.
[19] Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 2946):141-14,, 2012.
[20] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint wrXiv:810.004005 2018.
[21] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint
arXiv:2010.11 19299, 2020.
[22] Dheeru Dua and Casey Graff. Banknote authentication data set, UCI machine learning repository, 2017.
[23] Dheeru Dua and Casey Graff. Chess (king-rook vs. king) data set, UCI machine learning repository, 2017.
[24] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[25] Lukas Gonon. Random feature neural networks learn Black-Scholes type PDEs without curse of dimensionality. CORR, abs/2106.08900 2021.
[26] Anmol Gulati, James Qin, Chung- Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang, Zhengdong Zhang, Yonghui Wu, and Ruoming Pang. Conformer: Convolution- augmented transformer for speech recognition. In Helen Meng, Bo Xu, and Thomas Fang Zheng, editors, Interspeech 2020, 2 Annual Conference of the International Speech Communication Association, Virtual Event, Shanghai, China, 25-29 October 2020, pages 5036-5040. ISCA, 2020.

---

[27] Insu Han, Haim Avron, Neta Shoham, Chaewon Kim, and Jinwoo Shin. Random features for the neural tangent kernel. CoRR. abs/2104.01351, 2021.
[28] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fer- nández del Río, Mark Wiehe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Array programming with NumPy. Nature, 585(7825):357-362. September 2020.
[29] Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick. Masked autoencoders are scalable vision learners. arXiv preprint arXiv: vrXiv:211..0333 1..6377, 2021.
[30] Paul Horton and Kenta Nakai. A probabilistic classification system for predicting the cellular lo- calization sites of proteins. In Proceedings of the Fourth International Conference on Intelligent Systems for Molecular Biology, page 109-115. AAAI Press, 1996.
[31] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are RNNs: Fast autoregressive transformers with linear attention. In Proceedings of the 37th International Conference on Machine Learning, 2020.
[32] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020.
[33] Valero Laparra, Diego Marcos Gonzalez, Devis Tuia, and Gustau Camps-Valls Large-scale random features for kernel regression. In 2015 IEEE International Geoscience and Remote Sensing Symposium (IGARSS), pages 17-20, 2015.
[34] Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic. Towards unified analysis of random Fourier features. Mach. Learn. Res., 22:
2021.
[35] TS Lim, Yin Loh, and Yu-Shan Shih. A comparison of prediction accuracy, complexity, and training time of thirty-three old and new classification algorithms, Machine Learning, 40:203-228, 09 2000.
[36] Ha Quang Minh. Operator-valued Bochner theorem, Fourier feature maps for operator-valued kernels, and vector-valued learning. CoRR, abs/ (166.000639) 2016.
[37] Kevin P. Murphy. Machine Learning: A Probabilistic Perspective. The MIT Press, 2012.
[38] E. A. Nadaraya. On estimating regression. Theory of Probubility & Its Applications, 9(1):111 142, 1964.
[39] Warwick J. Nash and Tasmania. The Population biology of abalone (Haliotis species) in Tasmania. 1, Blacklip abalone (H. rubra) the north coast and the islands of Bass Strait / Warwick J. Nash... ... (et al.). Sea Fisheries Division, Dept. of Primary Industry and Fisheries, Tasmania Hobart, 1994.
[40] Manuel Olave, Vladislav Rajkovic, and Marko Bohanec. An application for admission in public school systems. Expert Systems in Public Administration, 160,--60, 1989.
[41] Junier B. Oliva, Willie Neiswanger, Barnabás Póczos, Eric P. Xing, Hy Trac, Shirley Ho, and Jeff G. Schneider. Fast function to function regression. In Guy Lebanon and S. V. N. Vishwanathan, editors, Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2015, San Diego, California, USA, May 9-12, 2015, volume 38 of JMLR Workshop and Conference Proceedings. JMLR.org. 2015.
[42] Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: An ASR corpus based on public domain audio books. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2015, South Brishane, Queensland, Australia, April 19-24, 2015, pages 5206-5210. IEEE, 2015.
12

---

[43] Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pages 4055 4064, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
[44] A. Rahimi and B. Recht. Uniform approximation of functions with random bases. In 2008 46th Annual Allerton Conference on Communication Control, and Computing, Los Alamitos, CA, USA, sep 2008. IEEE Computer Society.
[45] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neurul Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
[46] Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimiza- tion with randomization in learning, In Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou, editors, Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Secone Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 8- 1, 2008, pages 1313-1320. Curran Associates, Inc., 2008.
[47] Jayant Rohra, Boominathan Perumal, Swathi J.N., Priya Thakur, and Rajen Bhatt. User Localization in an Indoor Environment Using Fuzzy Hybrid of Particle Swarm Optimization and Gravitational Search Algorithm with Neural Networks, pages 286-299 02 2017.
[48] Bharath K. Sriperumbudur and Zoltán Szabó. Optimal rates for random Fourier features. In Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett, editors, Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 1144-1152, 2015.
[49] Emma Strubell, Ananya Ganesh, and Andrew McCallum. Energy and policy considerations for deep learning in NLP. CoRR, abss/190.002444 02244,, 2019.
[50] Yitong Sun, Anna C. Gilbert, and Ambuj Tewari. But how does it work in theory? Linear SVM with random features. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 3383-3392. 2018
[51] Danica J. Sutherland and Jeff G. Schneider. On the error of random Fourier features. In Marina Meila and Tom Heskes, editors, Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, UAI 2015, July 12-16, 2015, Amsterdam, The Netherlands, pages 862-87 AUAI Press, 2015.
[52] Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng. Synthesizer: Rethinking self- attenionn transformer models, 2021.
[53] Yi Tay, Dara Bahri, Liu Yang. Donald Metzler, and Da- Da-Cheng Juan. Sparse sinkhorn attention. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9438 9447. PMLR, 13-18 Jul 2020.
[54] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena : A benchmark for efficient transformers. In International Conference on Learning Representations, 2021.
[55] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, Bengio, H. Wallach, Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, pages 1998-6008 Curran Associates, Inc., 2017.
[56] Guido Walz. Lexikon der Mathematik: Band 2: Eig bis Inn. Springer-Verlag. 2016.
13

---

[57] Alex Wang. Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv: 1804.0746,, 2018.
[58] Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity, 2020.
[59] Geoffrey S. Watson. Smooth regression analysis. Sankhyā: The Indian Journal of Statistics, Series A (1961-2002). 26(4):359-372, 1964.
[60] Laura Weidinger, John Mellor, Maribeth Rauh, Conor Griffin, Jonathan Uesato, Po-Sen Huang. Myra Cheng, Mia Glaese, Borja Balle, Atoosa Kasirzadeh, et al. Ethical and social risks of harm from language models. arXiv preprint arXiv:2112.043599 2021.
[61]
Jiaxuan Xie, Fanghui Liu, Kaijie Wang, and Xiaolin Huang. Deep kernel learning via random Fourier features. CORR, abs/1910.02660, 2019.
[62] Jiyan Yang, Vikas Sindhwani, Quanfu Fan, Haim Avron, and Michael W. Mahoney. Random laplace feature maps for semigroup kernels on histogramss In 2014 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014, Columbus, OH, USA, June 23-28, 2014, pages 971-977 IEEE Computer Society, 2014.
[63] Tianbao Yang, Yu-Feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi-Hua Zhou. Nyström method vs random Fourier features: theoretical and empirical comparison. In Peter L. Bartlett, Fernando C. N. Pereira, Christopher J. C. Burges, Léon Bottou, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pages 485-493, 2012.
[64] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, and Amr Ahmed. Big bird: Transformers for longer sequences. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33,
pages 17283-17297. Curran Associates, Inc., 2020.
[65] Ciyou Zhu, Richard H. Byrd, Peihuang Lu, and Jorge Nocedal. Algorithm 778: L-bfgs-b: Fortran subroutines for large-scale cound-oosttrained optimization. ACM Trans. Math. Softw., 23(4):550-566 1997.
[66] Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. In IEEE international conference on computer vision, pages 19-27, 2015.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See statements of Theorems
3.1
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendices 9.2
9.3
9.4
9.5
9.6
9.7 9.8 9.9
14

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material
URL)? [Yes] We include the part of the code that is not confidential, the core CRT variant: FAVOR+ mechanism.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section [ and Appendix (9.00
(c) Did you report error bars (c.g., with respect to the random seed after running experi-
ments multiple times)? [Yes] See Figure 2 and Table 3 in the Appendix.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We mention that in the Appendix 9.10 We don't report the total amount of compute, because that would violate internal policies of our organisation.
4. If you are using existing assets (e.g.. code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license the assets? [N/A] We use standard publicly available datasets and frameworks.
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] We only standard publicly available datasets.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A] We only standard publicly available datasets.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A] We didn't 't use crowdsourcing
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "zMG-0xCex9S", "reviewer": "Reviewer_xmB9", "summary": "\nIn 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.", "questions": "\n1. 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.\n\n2. 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", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nPros.\n1.  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.\n\n2. In the experiments, the variance reduction is surprisingly significant (up to $e^{60} times). \n\n3.  The paper is well organized and well presented.\n\nCons. \n1.  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.\n\n2. Some symbols in Theorem are given without definition e.g., $C(\\|\\boldsymbol{x} + \\boldsymbol{y} \\|)$  in Theorem 4.1.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "tyBA_IGN1hv", "reviewer": "Reviewer_JjGy", "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.", "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).\n\nIs 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?\n \nIn 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?\n \n How numerically stable are features in Section 3.2.2 (geometric) given that there is factorial in the denominator? \n \n 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?\n \n Why is FAVOR+ failing dramatically on \"Uptraining\", Figure 4?\n", "limitations": "No ethical concerns.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#### - originality\nThe 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.\n\n#### - quality\nIt 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.\nA 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.\n\n#### - clarity\nThe 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.\n\n#### - significance\nThe 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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QHPpS1KMXo", "reviewer": "Reviewer_sgSZ", "summary": "The paper aims at suggesting an effiecent and unbiased estimator of the softmax/Gaussian kernel with positive bounded random features.\nHence, 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.\n\nTheorems 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.\nAs a result, the first uniform convergence findings for the softmax attention approximation with positive RFs utilizing OPRFs are given in Theorem 4.3.\n\nIn 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). \n\nExperimental results are also provided.", "questions": "Please see my comment regarding the proofs in the appendix. It will be very helpful to explain the derivations done in the proofs.\n\nAs 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. \n\n", "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.\nIt is still unclear how to select the theoretically ideal settings for the Generalized exponential RFs system.\n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nIt seems to be a very novel work with a solid theory, the numerical part is also sufficient.\n\nWeaknesses\nMy 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.\n\n1. 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?\nIn (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. \n\n2. 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.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "FxNEp3oiRdN", "reviewer": "Reviewer_Csyw", "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:\n- positiveness [2], resulting in numerical instabilities during the computation of the attention matrix normalization factor (the inverse of the row sums, line 102).\n- 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.\n\nThese are the main desiderata that the paper sets out to achieve while maintaining unbiased approximation.\n\nThe proposed CRT family encompasses two new classes of random features: \n\n  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;\n\n2) 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. \n\nAs 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.\n\nAdditional 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.\n\nFurther 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.\n\nExperiments are carried out on:\n- synthetic data, comparing the variance of the proposed random features with the previous techniques;\n- UCI classification problems by using single attention layer as a mapping from input to class membership probability;\n- NLP and speech modelling benchmarks;\n- Vision Transformers for testing the performance on a long-range dataset.\n\nThe experiments overall demonstrate the benefit of some of the proposed features on these kinds of learning problems.\n\n[1] Rahimi, Ali, and Benjamin Recht. \"Random features for large-scale kernel machines.\" Advances in neural information processing systems 20 (2007).\n\n[2] Choromanski, Krzysztof, et al. \"Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers.\" arXiv preprint arXiv:2006.03555 (2020).\n\n[3] Choromanski, Krzysztof Marcin, et al. \"Rethinking Attention with Performers.\" International Conference on Learning Representations. 2020.\n", "questions": "Theory:\n- 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)?\n- 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? \n\nExperiments:\n- 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? \n- 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.\n-  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.\n- 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.\n- 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.\n\nRemarks & typos:\n-  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.\n- In Line 59, a $-$ sign is missing within the Gaussian kernel formula\n\n[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.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nThe 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).\n\nThe 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.\n\nTo 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept