All Random Features Representations are Equivalent
This resolves the arms race in random features development, providing a foundational solution for practitioners in kernel methods and nonlinear domains like KNNs and attention.
The paper tackled the problem of approximation error in random features representations by deriving an optimal sampling policy, showing that under this policy all representations achieve the same lowest possible error, allowing free choice of representation.
Random features are a powerful technique for rewriting positive-definite kernels as linear products. They bring linear tools to bear in important nonlinear domains like KNNs and attention. Unfortunately, practical implementations require approximating an expectation, usually via sampling. This has led to the development of increasingly elaborate representations with ever lower sample error. We resolve this arms race by deriving an optimal sampling policy. Under this policy all random features representations have the same approximation error, which we show is the lowest possible. This means that we are free to choose whatever representation we please, provided we sample optimally.