A Tale of Two Efficient and Informative Negative Sampling Distributions
  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 costly from the computational and
energy perspective. There have been various 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 is no
sampling scheme that is provably adaptive and samples the negative classes
efficiently. 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 two classes of distributions where the sampling
scheme is truly adaptive and provably generates negative samples in
near-constant time. Our implementation in C++ on CPU is significantly superior,
both in terms of wall-clock time and accuracy, compared to the most optimized
TensorFlow implementations of other popular negative sampling approaches on
powerful NVIDIA V100 GPU.
