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.

提出了用于逼近 Gauss 核和 softmax 核的新型非三角随机特征 —— 厨师随机表 (CRTs)。CRT 是标准随机厨房水槽 (RKS) 方法的替代品。通过使用正随机特征 (RFs)，CRT 可以获得更少的方差和更小的尾部。此外， CRT 可以通过利用简单计算的统计数据进一步降低方差。在多项任务中测试 CRT，获得了最先进的结果。