  Softmax classifiers with a very large number of classes naturally occur in
many applications such as natural language processing and information
retrieval. The calculation of full-softmax is very expensive from the
computational and energy perspective. There have been a variety of sampling
approaches to overcome this challenge, popularly known as negative sampling
(NS). Ideally, NS should sample negative classes from a distribution that is
dependent on the input data, the current parameters, and the correct positive
class. Unfortunately, due to the dynamically updated parameters and data
samples, there does not exist any sampling scheme that is truly adaptive and
also samples the negative classes in constant time every iteration. Therefore,
alternative heuristics like random sampling, static frequency-based sampling,
or learning-based biased sampling, which primarily trade either the sampling
cost or the adaptivity of samples per iteration, are adopted. In this paper, we
show a class of distribution where the sampling scheme is truly adaptive and
provably generates negative samples in constant time. Our implementation in C++
on commodity CPU is significantly faster, in terms of wall clock time, compared
to the most optimized TensorFlow implementations of standard softmax or other
sampling approaches on modern GPUs (V100s).
