  The computational cost of training with softmax cross entropy loss grows
linearly with the number of classes. For the settings where a large number of
classes are involved, a common method to speed up training is to sample a
subset of classes and utilize an estimate of the loss gradient based on these
classes, known as the sampled softmax method. However, the sampled softmax
provides a biased estimate of the gradient unless the samples are drawn from
the exact softmax distribution, which is again expensive to compute. Therefore,
a widely employed practical approach involves sampling from a simpler
distribution in the hope of approximating the exact softmax distribution. In
this paper, we develop the first theoretical understanding of the role that
different sampling distributions play in determining the quality of sampled
softmax. Motivated by our analysis and the work on kernel-based sampling, we
propose the Random Fourier 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. Furthermore, the cost of RF-softmax scales only
logarithmically with the number of classes.
