Sampled Softmax with Random Fourier Features

Motivated by our analysis and the work on kernel-based sampling, we propose the Random F ourier Softmax (RF-softmax) method that utilizes the powerful Random Fourier Features to enable more efficient and accurate sampling from an approximate softmax distribution. We show that RF-softmax leads to low bias in estimation in terms of both the full softmax distribution and the full softmax gradient.