A Truly Constant-time Distribution-aware Negative Sampling
Authors: Shabnam Daghaghi
Tharun Medini
Beidi Chen
Mengnan Zhao
Anshumali Shrivastava
Venue:  (2021)

Abstract: 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. We demonstrate a negative sampling implementation that is significantly faster, in terms of wall clock time, compared to the most optimized TensorFlow implementations of standard softmax or other sampling approaches on the best available GPUs (V100s).

Under review as a conference paper at ICLR 2021
A TRULY CONSTANT-TIME DISTRIBUTION-AWRRE E NEGATIVE SAMPLING
Anonymous authors Paper under double-blind review
ABSTRACT
Softmax classifiers with 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 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 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 the adaptivity of samples per iteration, are adopted. In this paper, we show a class of distribution where the sampling scheme truly adaptive and provably generates negative samples in constant time. Our implementation in C++ on commodity CPU significantly faster, in terms of wall clock time, compared the most optimized TensorFlow implementations of standard softmax or other sampling approaches on modern GPUs (V100s).
INTRODUCTION
Neural Networks (NN) have successfully pushed the boundaries of many application tasks, such as image or text classification (Wang et al. 2017 Yao et al. 2019), speech recognition (Dong et al. 2018) and recommendation systems (Zhang al. Medini al. 2019) Many hard Al problems are currently modeled as massive multiclass or multilabel problems leading to drastic improvement over prior work. For example, popular NLP models predicts the best word, given the full context observed so far. Such models are becoming the sfte-of-theeart Recommendation systems and related Information Retrieval (IR) problems are classical examples of machine learning with outrageously large outputs (Medini et al., 2019 Jain al., 2019). In IR, given the user query, the task is predict few relevant documents (or products) from among hundreds of millions possible documents, a typical machine learning problem with massive output space.
Owing to the significance of the problem, machine learning with large output space or alternatively also known extreme classification is field in itself (Bengio al. 2019). A large number of classes naturally brings a new set of computational and memory challenge.
Fortunately, with access to our powerful Graphic Processing Unit (GPU) Owens et al. 2008). training processes of large models have been accelerated heavily. That is because GPUs have unique advantage for matrix multiplication, which usually requires cubic time algebraic operation (O(N²) and is the major and costly building block of NN computations. However, the number of concurrent operations required in large matrix multiplications for classification with extensive number of classes has reached a limit for further speedups even using GPUs.
1.1 NEGATIVE SAMPLING
The common approach to address this challenge is known as negative sampling (Pennington et al., 2014; Jean al. 2014 Rawat et al. 2019 Mikolov et al.) 2013b). In Negative Sampling, we only sample a small subset of classes for each input and compute the softmax and cross-entropy function. This subset usually includes the positive (true) and small set of negative (false) classes. Negative

---

Under review as a conference paper at ICLR 2021
sampling scales down the computations in the most cumbersome last layer, thereby making training efficient.
However, approximating full-softmax with small sub-sample results in poor convergence if the nega- tive samples are not chosen appropriately. For instance, let us take the example of a recommendation system (predicting products relevant a query) with large number of products. If the input query is 'Nike Running Shoes', the true loss concentrates on the specific small number of confusing ('hard") negative classes like 'Adidas Running Shoes'. Since the number of classes is huge, random sampling is unlikely to identify this hard negative class. Other heuristics like frequent class sampling as negative samples are also unlikely to find these hard negatives most of the time. Clearly, without discriminating between closely related negative samples, the classifier cannot achieve good accuracy. Our experiments on recommendations datasets clearly indicate this sub-optimality of current negative sampling heuristics.
If there exists way to sample the subset of confusing classes from the skewed distribution, the training progress would be largely accelerated. However, as evident from the example, such ground-truth distribution depends on the input sample and current model parameters. Moreover, this distribution varies significantly as training progresses. Consider the same query 'Nike Running Shoes', initially, when the network has not learned anything and has random weights, all classes are equally confusing. Thus, uniform sampling is optimal initially the network has just started to learn. As the training progresses, the network's belief starts getting more concentrated on a few classes; at this time, a negative sample of say 'baby toys' is not all useful because the network has already learned to tell them apart. The sampling distribution keeps changing, often drastically, as the training progresses.
To the best of our knowledge, there does not exist any statistical sampling scheme and implementation for adaptive Negative Sampling, where the cost of maintaining and updating the distribution, per iteration, ((1) (independent of the number of classes). This is because the input, current true class, and parameters update all the sampling weights in every iteration. It is widely assumed that there is no such sampling scheme, and hence several heuristic alternatives are proposed.
The first set of alternatives use a static distribution. The most popular ones, implemented in Tensor- Flow, assume a static distribution such as the distribution based on the frequency of classes. Uniform sampling is another popular choice.
Learning-bawee based alternatives are also proposed (Bamler Mandi 2020). where machine learning generator predicts (or generates) the negative samples. The sampler is solving the same hard problem, prediction over a large number of classes, as a sub-routine. Most importantly, since the sampling distribution for the same data point shifts drastically throughout training, ML models are likely to suffer.
Negative sampling alternatives try to balance the sampling cost with quality. So far, negative sampling methods, other than the ones based on static sampling, have failed to demonstrate any training time improvements over the optimized full softmax implementation over GPUs. Static sampling strategies are known to be fast but lead to poor accuracy. With current strategies, the cost of improving the quality with current alternatives does not seem worth it over the GPU acceleration of softmax.
In this paper, we change this. Our work provides a truly constant time adaptive sampling scheme utilizing the recent advances in Locality Sensitive Sampling (Charikar & Siminelakis/ 2017 (Spring & Shrivastaval 70). More impressively, we provide an efficient implementation of our proposal on CPU, which outperforms TensorFlow's implementation of softmax and other negative sampling strategies on some of the best available GPUs (V100) in terms of wall-clock training time.
Summary of Contributions:
1) We propose two efficient schemes for sampling 'hard' negatives where the negative sampling distribution provably adapts to changing parameters and the data instance. Furthermore, the sampling cost is provably constant (independent of the number of classes).
2) We show that our technique is not only provably adaptive but also practical. We provide an efficient CPU implementation, in C++, of our negative sampling approach. We demonstrate the effectiveness of a truly constant time negative sampler by showing that our implementation significantly outperforms standard TensorFlow on V100 GPU mall clock speed, while retaining the accuracy.
2

---

Under review as a conference paper at ICLR 2021
3) We provide rigorous evaluation of our proposal with its efficient implementation against full softmax and popular approximations like sampled softmax, frequency- sauueecc--bbeed sampled softmax, top-K activation softmax, differentiation softmax (D-Softmax), and Noise Contrastive Estimation(NCE)) We report the time-wise and iteration-wise precision on large recommendation datasets like Amazon- 670K, Wikil SH-325K, and popular natural language processing dataset Text8 corpus.
1.2 LSH BASED HASH TABLES
In this section, we briefly describe the recent development of using locality sensitive hashing for
sampling and estimation (Chen al. 2019b Spring & Shrivastava 2017a Charikar & Siminelakis,
2pring & Shrivastava 2017b). Locality Sensitive Hashing (Indyk & Motwani] 1998] Indyk Woodruff 2006) is widely used paradigm for large scale similarity search and nearest neighbor search. LSH is family of hash functions with unique property that vectors 'close' wrt some distance metric are more likely to have the same hash code as opposed to vectors that are 'far' from each other. Formally, one sufficient condition for hash family H to be a LSH family is that the collision probability (hx()(z) h(y)) monotonically increasing function of the similarity:
Pr h(v)) (Sim(zz,
where f is monotonically increasing function.
The idea is use the hash value of x, i.c., h(z), to generate key of x in the hash table. We first initialize L hash tables by constructing meta-LSH hash function using K independent hash functions for each of them. For details, see (Andoni Indyk 2004). There are three major steps:
Given a dataset of size we first insert all the data points into the hash tables using the meta-LSH formed by concatenating K independent LSH hash functions. We only store the index/pointer of the data point in the hash tables instead of the entire vector. The cost of addition is K x L hash computations followed by L insertions in the buckets.
Pre-processing Phase:
During the query phase, we use the same meta-LSH hash to compute the hash codes for the query. Then we probe the corresponding bucket of each table and retrieve samples from The union of candidates from all hash tables constitute the samples for the particular query.
Query Phase:
Update Phase: an existing element in the database is updated, we can delete from the hash table and re-add it. The cost is equivalent twice the insertion cost of an element which is 2 K L.
1.3 ADAPTIVE SAMPLING VIEW OF LSH
Denote Per be the probability of retrieving x from the datasets, when queried with given query 4. In (Indyk & Motwani 1998), it was shown that for (K, I.) parametrizze I.SH algo- rithm the precise form of Pчz = 1- (1(11-0 (1) where is the collision probability of query and x under the given LSH function, i.c. (h(x) = h(4))- Par is monotonic in which is further monotonic in the simi- larity between query q and the data element x. Note the similarity measure is dependent on the LSH function in use. See (Spring & Shrivastava 2017a) for details.
[pointers only)
20
12
11
h2
h; RP [0,1,
Figure 1: Schematic diagram of LSH. For an input, we compute hash codes and retrieve candidates from the corresponding buckets.
Constant Time Sampling: It should be noted
that the cost sampling is the cost querying, which is only K L. This sampling cost is independent of the number of elements in the data. Clearly, the probability Pęp is dependent on the query. and every element x in the data has a different sampling probability. Thus, even though our sampling scheme induces different sampling probabilities every time the query is changed, the sampling cost is independent of n, and in-fact is constant if K and L are small constants. All this is assuming one O(n) time preprocessing.
3

---

Under review as a conference paper at ICLR 2021
This efficient sampling view of LSH has been used in wide range of applications, such as deep neural networks (Spring & Shrivastava 2017b] Chen et al. 2019a), kernel density estimation (Charikar & Siminelakis 2017). (017).0. record linkage (Chen al. 2018). and optimization (Chen et al. 2019c).
Recent advances in fast inner product search using asymmetric LSH has made it possible to sample large inner products (Shrivastava & Li 2014). Effectively, given query q. it is possible sample an element x from the database with probability proportional to a monotonic function of inner product f(a x). Here f is monotonically increasing function.
2
OUR PROPOSAL: LOCALITY SENSITIVE NEGATIVE SAMPLING (LNS)
Query: True Label vector
Output Layer Tables
1
:
h
hp
Buckets
3
00
00
:
X1
01
10
Empty
12
11
Penultimate Layer
Output Layer
Figure 2: Schematic diagram of our proposal for LSH-label scheme. We first construct hash tables for the label vectors. The label vectors are the weights of the connections from label to the penultimate layer. the figure, e-g. label vectors for node (blue node) is a concatenation of its connection weights to the penultimate layer (blue lines). 2) For training sample, we query the LSH tables with the true label weights (red lines) and obtain negative samples (blue and green nodes). We call the retrieved samples 'hard' negatives because they are very similar to the 'true' ones but are supposed to be 'false'.
We will start by defining few vectors in the neural network setting illustrated in 2 We are large softmax settings. Here, we will use N to denote the total number of classes. Define vector w, RRd (class vectors) be the vector associated with class in the last layer of the neural network. We will use (I, y) to denote the current input sample to the neural network for which we
Notations:
generate negative samples. We will use Eg Rd (final impul embedding) to denote the vector of activation in the penultimate layer of the neural network when fed with input œ.
We first describe our sampling procedure, and later we argue why is distribution aware and constant time. Our approach, just like the LSH algorithm, has three phases. The first phase is a one time costly (O(N) prepossessing stage. The other two phases, sampling and update phase, are performed in each iteration, and both of them are constant-ting operation independent of N.
One time Preprocessing Phase during Initialization: We start with randomly initializing the neural network parameters. This automatically initializes all the class vectors w;. We now preprocess all these randomly initialized class vectors in (K, I.) parameterized L.SH hash tables, as described in Section 1.2 This is one-time operation during initialization.
Sampling Phase for every input (z, y): In this phase, we process input x to the penultimate layer and get the final input embedding E,. Now instead of processing all the N nodes in the last layer, we query the hash tables with either vector E,, (LSH Embedding) or with the vector corresponding to the true label y, i.e., Wy (LSH Label). This preciously describes our two sampling schemes. We can obviously mix and match, but we consider these two choices as two different methods for the simplicity of analysis and evaluations.
4

---

Under review as a conference paper at ICLR 2021
When query, generate small set of the sampled candidates, call them C, forming our negative samples. Thus, we only compute the activation of nodes belonging to U' in the last layer and treat others zero activation.
Update Hash Tables with Update in Weights: During backpropagation for imput (z. y). we only update C U y weights in the last layer. We update these changed weights in the LSH hash tables.
Next, we first argue why this sampling is distribution aware and adaptive with every parameter and input change. We will then argue that the sampling and update process is significantly efficient. It is constant-time operation that is easily parallelizable.
2.1
WHAT IS THE SAMPLING DISTRIBUTION? IS IT ADAPTIVE?
We start with two theorems that give the precise probability distribution of sampling a class as negative sample with LSH Label and LSH Embedding methods provided the input (rr y) and current parameters. We will use Pay as the collision probability of the LSH hash value of x and y.
Theorem LSH Label Distribution For an input (x, y) and LSH parameters (K, L), the probabil- ity of sampling a class + y as negative sampling with LSH Label method is given by
P. (1-1-(1-Pe)p
where Wy and wi are the weights associated with true class y and respectively. Furthermore, the probability of sampling class is more than any other class j. if and only if sim(Wy. we) > sim(w, Wz). Here sim is the underlying similarity function of the LSH.
Theorem LSH Embedding Distribution For an input (x, y) and LSH parameters (K, L), the probability of sampling a class + y as negative sampling with LSH Embedding method is given by
Ps x 1 - (1 (1-1-11 aal-pEA -E,,,)
where Eg is the embedding vector of input and w; is the weights associated with class i respectively. Furthermore, the probability of sampling class is more than any other class j. if and only if sim F.z, ws) > sim( w.)) Here sim is the underlying similarity function of the LSH.
The expressions of probability are immediate from the sampling view of LSH. The expressions 1 - (1 -p")² monotonically increasing in p. the collision probability, which in turn is monotonically increasing in the underlying similarity function sim. Clearly, the distribution is adaptive as they change with the input (I, y) as well as the parameters. or any change in the input change the sampling distribution completely. However, the sampling cost is constant and independent of the number of classes we are sampling from!
Comments:
any update the parameter
Intuition of LSH Label: Coming back to our example of class 'Nike Running Shoes'. Let us focus on L.S Label distribution. Initially, when all other labels have random weights, the similarity between the label 'Nike Running Shoes' and any other label will random. So initial negative sampling should be like uniform sampling. However, as the learning progress, it is likely that 'Nike Running Shoes' and 'Adidas Running Shoes' will likely get close enough. Their weights will have high similarity (high sim), at that time, the LSH Label sampling will select 'Adidas Running Shoes' as likely negative sample for 'Nike Running Shoes' class.
Intuition of LSH Embedding: The LSH Embedding method is also adaptive. Consider the similarity function as inner product. LSH embedding inner product with class vector is directly proportional to its activation. Thus, naturally selects classes which the classifier confused (high activation but incorrect) negative samples. Again, the distribution is adaptive.
2.2 COMPUTATIONAL COST FOR PROCESSING EACH INPUT
Given input (z, y), the cost of processing it without any negative sampling is O(N). With our proposed negative sampling the cost of sampling is the cost of query which K x L, a negligible number compared to N in practice.
5

---

Under review as a conference paper at ICLR 2021
LNS Target Uniform
Target
Figure 3: How the negative smapling distribution (target), uniform negative sampling and LNS adapts over iterations. Initially, when there is no learning all the sampling is close to uniform (Left Plots). During later states the sampling distribution is significantly different from uniform.
The cost of update is slightly more (IC) +1 K x T. because we have to update |C| weights. In negative sampling, C very small constant. Also, practice and L are small constants. Furthermore, we have choice to delay the hash table updates, it only changes the sampling probability of few elements.
2.3 ALGORITIIM AND IMPLEMENTATION DETAILS
First we construct K x L hash functions and initialize the weights of the network and L hash tables. The LSH hash code of weight vectors of the last layer are computed and the id of the corresponding neuron is saved into the hash buckets. During the feed-forward path in the last layer, we query whether the embedding vector (LSH-embedding scheme) or the label vector of true class (LSH-llbel scheme) and retrieve the classes from hash table which considered negative classes. Instead of computing the activation of all the output nodes (full softmax), we compute the activations of the true backpropagate
classes and the corresponding retrieved negative classes. For the backpropagation, the errors to calculate the gradient and update the weights for the active nodes. Please refer to Algorithm in the Appendix A.4
EXPERIMENTS
In this section, we will empirically evaluate the performance of our LSH Negative Sampling (LNS) approach against other sampling schemes that are conducive GPUs. The real advantage of LNS is noticeable with huge neural networks. The popular extreme classification challenges have models with more than 100 million parameters, which are ideal for our purpose. For these challenges, most of the heavy computations happen in the last layer.
3.1 DATASETS
We evaluate framework and other baselines three datasets. Amazon-670k and WikiLSH-3255 are two datasets from extreme classification repository (Bhatia et al.) 2016) and Text8 is a popular NLP dataset. The detailed statistics about the dimensions and samples sizes are included in Table [ in appendix A.
3.2 BASELINES
We benchmark our proposed framework against full-softmax, sampled-softmax, topK-softmax Trequency-based-ssotta. noise contrastive estimation and differentiated softmax (all explained below). All the baselines are implemented on TensorFlow-Gr U. To have fair comparison, the architecture, optimizer and size hidden layer are exactly the same for the methods on each dataset. Please note that proposal only uses CPU and yet outperforms the other methods.
Full-Softmax: Full-softmax updates the weights of the output neurons, which makes it com- putationally expensive and intractable for extreme classification framework. Sampled-Softman campled-softmalt draws negative samples based on log-uniform distribution and updates their corre- sponding weights plus the weights for the true classes. This approach alleviates the computational

---

Under review as a conference paper at ICLR 2021
0.40
0.60
0.50
6.50
0.49
Solmux
0.40
Togi Sotmax
Topk Softmu
Free Sofmax
Freq Softmax
Sample Softiax
0.50
Simple Sintlmas
NCB
NCB
1-Seftmax
Label
0.29
LSH Embeeddnng
Embedding
0.15
1.0
0.25
0.50
0.75
1,00
1.25
1.50
1.75
2,00
Theration
L05
Amazon 67CK
Amazon 670K
0.30
0.30
0.25
0.25
Topit
Sample Softmax
Frog Softmaa
Freq Softmax
NCE
0.15
NCE
D-Softmax
D-Sufmmar
0.10
LS1 Label
0.10
1SH Label
0.0
0.2
1.2
1.4
Time (sac)
1ec
Iteratoo
16t
Touts
Text8
0.350
0.350
0.325
0.525
0.300
0,300
0.275
0.275
Solimax
0.250
Topk Reflmw
0.230
Topk Soft max
Sample Soltmax
Preg Softinax
0.225
Frog Softnox
Sample Softmox
NCT
0.200
NCE
Softmax
D-Seelmmw
Label
Label
0.0
0.2
04
0.6
0.5
1.0
1.2
1.4
0.0
0.2
0.4
0.6
0.5
1.0
1.2
Timm (wxc)
165
Iteration
165
Figure 4: Comparison of our proposal LNS with two schemes (LSH label and LSH embedding) against full softmax, topK softmax, frequency based softmax, sampled softmax, NCE and D-softmax for all three datasets. Left Column: Precision@ I vs time, Right Column: Precision @ vs iteration,
Top Row: WikiLSH-325K dataset Middle Row: Amazon-670K dataset Bottom Row: Text8 dataset. The LSH methods closely mimics full softmax in iteration wise plots indicating the superiority of distribution aware sampling. The time plots clearly indicates the speed of sampling, where LSH sampling are the best performing ones.
bottleneck but degrades the performance in terms of accuracy. TopK-Softman TopK-softmar updates the weights of the output neurons with & highest activations (including the true classes), This framework maintains better accuracy than sampled-softmn but with a slower convergence rate due to the scoring and sorting all classes. Frequency-basee Saseee--baeddSSottasss
samples the classes in proportion to the frequency of their occurrence in the training data. Com- putationally, this is the same as Sampled-softman however samples negative classes from more frequent classes with higher probability. Miise-Contrastvve Estimation (NCE): NCE loss (Gutmann Hyvärinen] 2010) tackles multi-class classification problem as multiple binary classifiers instead. Each binary classifier is trained by logistic loss to distinguish between true classes and negative classes. Negative classes are sampled from a noise distribution which is typically log-uniform distri- bution based on class frequencies. Differentiated Softmax (D-Softmax): D-softmax (Chen et al.)

---

Under review as a conference paper at ICLR 2021
2015) defines softmax layer weight matrix sparse block diagonal matrix where the blocks constructed based on class frequencies, c.g. more frequent classes attains more parameters. LNS (our proposal): Our proposed negative sampling algorithm samples the classes from output distribution which is adaptive to the input, true class and model parameters. Our model utilizes LSH to sample the most confusing (the most similar but false) classes as the negative samples in constant time.
3.3 ARCHITTCCTRRE AND HYPERPARAMETERS
For Amazon-670K and WikiL-SH-322 we use a standard fully connected neural network with hidden layer size of 128, where both the input and output are multi-hot encoded vectors. For Text8, We utilize standard word2vec language model with hidden layer size of 200, where input and output are one-hot and multi-hot encoded vectors, respectively. In word2vec architecture we utilize skip-gram model introduced in Mikolov et al. (2) Skip-gram model aims to predict nearby words in a document by learning continuous representation of words. Particularly, given word, skip-grane -ra-gram model targets to predict the m left and m right neighbor words, where m is window size and is considered hyperparameter. We pick
2 for our experiments.
We performed hyperparameter tuning for all the baselines to maintain their best trade-off between convergence time and accuracy. The optimizer Adam with learning rate 0.0001 for all the experi- ments. The batch size for Amazon-670, WikiLSH-325 and Text8 is 1024, 256 and 512 respectively for all the experiments. We apply hash functions for the last layer where we have the computational bottleneck. In LSH literature, L denotes the number of hash tables and K denotes the number of bits in the hash code for each hash table (thereby having 2 buckets per hash table). We use DWTA hash function [A.] for Amazon-670K and WikiLSH-325K with K=6, L=400 and K=5, L=350 respectively. For Text8 we use Simhash hash function (A.2 with K=9 and L=50. We update the hash tables with an initial update period of 50 iterations and then exponentially decaying the updating frequency (as we need less updates near convergence). Our experiments are performed on a single machine with 28-core and 224-thread processors. All the baselines are on the state of the art NVIDIA V100 GPUs with 32 GB memory.
3.4 RESULTS
Figure 4 shows the plots comparing Precision@1 (denoted here-on by P@ 1) versus both wall-clock time and the number of iterations for our method and all the baselines. For WikiL.S--325K dataset, LSH-label and LSH-embedding are respectively 4x and 4.3x faster than TensorFlow full softmax on GPU in terms of wall-clock training time. Moreover, both of them outperform all other TensorFlow baselines GPU with significant margin. The same is true for Amazon where LSH-label and LSH-embedding are 10x and 9.6x faster than TensorFlow full softmax on GPU correspondingly. On Text8 dataset, all methods perform more less equally in terms of P@ 1 and our LSHH-Embedding is the second fastest negative sampling method after sampled softmax in terms of training time. According to iteration-wis plots, both LSH-label and P@ I among all other sampling methods for Amazon-670K and SikiLSH-325K datasets, and achieves pretty similar performance with other sampling methods on Text8 dataset. Therefore, both variations of our LNS method outperform almost all other TensorFlow baselines on all datasets while being very similar to full softmax iteration wise. This establishes the earlier statement that LNS does not compromise performance for speed-up. This is particularly noteworthy because our implementation of LNS uses only CPU while all other baselines run FeosorFlow-GGU on a V100.
schemes attain the highest
4 CONCLUSION
We proposed two provable, efficient and adaptive negative sampling schemes for neural networks with extreme number of classes. Our method samples negative classes in constant time, while adapts to the continuous change of the input, true class and network parameters. We efficiently implemented algorithm CPU in C++ and benchmarked it against standard TensorFlow implementation of six baselines on GPU, Our method on CPU outperforms almost all the TensorFlow baselines on GPU with significant margin three datasets.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alexandr Andoni and Piotr Indyk. E2lsh: Exact euclidean locality-sensitive hashing. Technical report, 2004.
Robert Bamler and Stephan Mandt. Extreme classification via adversarial softmax approximation. In International Conference on Learning Representations, 2020, URL hattps:
net Etw.:/ommmddddeeeeeeeeeee-
Samy Bengio, Krzysztof Dembczynski, Thorsten Joachims, Marius Kloft, and Manik Varma. Extreme classification (dagstuhl seminar 18. Schloss Degstubl-LcibnizzZZnttun fuer Informatik, 2019.
K. Bhatia, K. Dahiya, H. Jain, A. Mittal, Y. Prabhu, and M. Varma. The extreme classificattin reposi- tory: Multi-label datasets and code, 2016. URL http:://an..kvvmaaaaaa... http:///wi..aaaoo.oorooooooooaaa
XC/ CC/XMLRepositooo
html
Moses Charikar and Paris Siminelakis. Hashing- sions. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1032-1043. IEEE, 2017.
seettinn--aaed-ettte based-estimators for kernel density in high dimen-
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 380-388, 2002.
Beidi Chen and Anshumali Shrivastava. Densified winner take all (wta) hashing for sparse datasets. In Uncertainty artificial intelligence, 2018.
Beidi Chen, Anshumali Shrivastava, Rebecca C Steorts, et al. Unique entity estimation with applica- tion the syrian conflict. The Annals of Applied Staristics, 1039) 2018.
Beidi Chen, Tharun Medini, James Farwell, Sameh Gobriel, Charlie Tai, and Anshumali Shrivastava. Slide defense of smart algorithms over hardware acceleration for large-scale deep learning systems, 2019a.
Beidi Chen, Yingchen Xu, and Anshumali Shrivastava. Fast and accurate stochastic gradient estima- tion. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Achéé Buc, E. Fox, and R. Garnett (eds.), Curran Associates, Inc.,
Advances in Neural Information Processing Systems 32, pp. 2019b.
Beidi Chen, Yingehen Xu, and Anshumali Shrivastava. Fast and accurate stochastic gradient estima- tion. In Advances Neural Information Processing Systems, pp. 12339-12349, 2019c.
Welin Chen, David Grangier, and Michael Auli. Strategies for training large vocabulary neural language models. arXiv preprint
2015.
Linhao Dong, Shuang Xu, and Bo Xu. Speech-transformer:: a no-recurrence sequence-to-sequeee model for speech recognition. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5884-5888. IEEE, 2018.
Michel Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115 1145, 1995.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormalized statistical models. Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 297-304, Chia Laguna Resort, Sardinia, Italy, 13-15 15 May 2010. PMLR. U html
mlr www.:mwt...pmm..mm. pttpsp////ssse/eeeeepe qutmann1aa
Monika Henzinger. Finding near-duplicate web pages: large-scale evaluation of algorithms. In Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, pp. 284-291, 2006.

---

Under review as a conference paper at ICLR 2021
Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth anmual ACM symposium on Theory of computing. pp. 604-613, 1998.
Piotr Indyk and David Woodruff. Polylogarithmic private approximations and efficient matching. In Theory of Cryptography Conference, pp.
Springer, 2006.
Himanshu Jain, Venkatesh Balasubramanian, Bhanu Chunduri, and Manik Varma. Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, pp. 228-53,, 2019.
Sébastien Jean, Kyunghyun Cho, Roland Memisevic, and Yoshua Bengio. On using very large target vocabulary for neural machine translation. arXiv preprint arXiv: 1412:004 2014.
Tharun Kumar Reddy Medini, Qixuan Huang, Yiqiu Wang, Vijai Mohan, and Anshumali Shrivastava. Extreme classification in log memory using count-min sketch: A case study of amazon search with 50m products. Advances in Neural Information Processing Systems, pp. 13244-13254 2019.
Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation word representa- tions in vector space. arXiv preprint arXiv:1301.378: 2013a.
Tomas Mikolov, Ila Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pp. 3111-3119, 2013b.
John D Owens, Mike Houston, David Luebke, Simon Green, John Stone, and James C Phillips. Gpu computing. 2008
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Anand Rajaraman and Jeffrey D Ullman. Jure leskovec. 2010.
Ankit Singh Rawat, Jiecao Chen, Felix Xinnan X Yu, Ananda Theertha Suresh, and Sanjiv Kumar. Sampled softmax with random fourier features. Advances Neural Information Processing Systems, pp. 1o.1335 13834-13844, 2019.
Anshumali Shrivastava and Ping Li. Asymmetric Ish (alsh) for sublinear time maximum inner product search (mips). In Advances in Neural Information Processing Systems, pp. 2321-2329, 2014.
Ryan Spring and Anshumali Shrivastava. A new unbiased and efficient class of Ish-based sam- plers and estimators for partition function computation in log-linear models. arXiv preprint 1rXiv:1703.05 2017a.
Ryan Spring and Anshumali Shrivastava. Scalable and sustainable deep learning via randomized hashing. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 445-454, 2017b.
Fei Wang, Mengqing Jiang, Chen Qian, Shuo Yang. Cheng Li, Honggang Zhang, Xiaogang Wang, and Xiaoou Tang. Residual attention network for image classification. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3156-314 1364,316,,44 2017.
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 7370-7377, 2019.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In Advances in neural information processing systems, pp. 649-657, 2015.
10

---

Under review as a conference paper at ICLR 2021
Table
Statistics the datasets
Feature Dim
Feature Sparsity
Label Dim
Train Size
Test Size
Amazon-6700
135909
0.055 %
670091
490449
153025
WiKiLSHTC-325K
1617899
0.0026 %
325056
1778351
587084
Text8
253855
0.0004 %
253855
13604165
3401042
A APPENDIX
A.1 DATASET
Amazon-670K dataset is product recommendation dataset with 670K labels. Here, each input is a vector representation of a product, and the corresponding labels are other products (among 670K choices) that user might interested in purchase. This is an anonymized and aggregated behavior data from Amazon and poses significant challenge owing to a large number of classes.
WiKiLSHTC-325K is based on two main sources: Wikipedia and ODP web directory. Each instance in sparse vector format where the value of feature corresponds to the frequency and the label corresponds to the category of the instance.
Text8 is popular NLP dataset and preprocessed version of the first 100million tokens of English Wikipedia which contains 253K vocabulary. We utilized standard word2vec language model for text8 dataset, where input and output one-hot and multi-hot encoded vectors, respectively.
A.2 SIMHASH: SIGNED RANDOM PROJECTIONS
SimHash is popular LSH that originates from Signed Random Projections (SRP) (Charikar 2002 Rajaraman & Ullman 2010 [enzinger] (206) and preserves the cosine similarity measure. Given vector H, SRP generates random vector with each component generated from i.i.d. normal, W): ~ (0, 1), and only stores the sign of the projection. Formally SimHash is given by
h sign (x) =sig(w" x).
was shown in (oeemans& & Williamson 1995) that the collision probability under SRP satisfies the following formula:
0
Pr(h (x) haign (v)) =
where 0 cos-1
12-11ylaa
A.3 DWTA HASH: DENSIFIED WINNER TAKE ALL HASH
DWTA Chen & Shrivastava 2018) R hash transforms the data into the transformed space such that their hamming distance correlates with their rank similarity measure the original space. Densified WTA (DWTA) hash combines traditional WTA hashing and densification improve discriminative power over sparse datasets. DWTA hash generates KLm number of permutations and each permutation d
is split into bins where d is the input dimension and << d is a hyperparameter. DWTA loops through the nonzero indices the sparse input and updates the current maximum index of the corresponding bins according to the mapping in each permutation. It has been shown (Chen & Shrivastava 2018) that the collision probability of DWTA is precisely the collision probability of WTA hash for nonempty bins, irrespective of the sparsity.
Pr(hDwta is Duta (v)) = Pr(h
hwt (v)(0(x;) @ = Emply)
(4)
where ((r) is the set of random features of x with permutation e.
11

---

Under review as a conference paper at ICLR 2021
A.4 ALGORITHM
Algorithm Locality Sensitive Negative Sampling (LNS)
input Ex final input embedding, w, class vectors
output No set of active neurons of the last layer
Initialize weights wy for last layer
2: Create K x L hash functions and initialize L hash tables for the last layer
3: Compute fy (w)) for all output neurons
4: for i = 1 Tterations do
5: for Batch do
6: if LSH Embedding then
7: No= (E,), HT))
8: end if
9: LLS Label then
N₂ (w:r)(h((::),, HT)
11: end if
12: end for
13: end for
12


Reviews:
[{"review_id": "tzQPcaK895p", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "When the number of classes is very large, calculating softmax for classification (e.g., in backpropagation) is computationally costly. Approaches based on negative sampling have been used in literature to alleviate this problem. However, most of existing approaches are (argued to be) either inaccurate or computationally costly. This paper proposes to use the well-known LSH (locality sensitive hashing) method to address this problem. In particular, two variants, LSH label and LSH Embedding are showed to speed up the training in terms of time needed to converge compared with a number of baseline methods over three large scale datasets. \n\n+ The suggested approach is simple, making it potentially useful in practice. \n+ The methodological contribution of the paper is more or less an off-the-shelf use of LSH for negative sampling. This being said, the application of LSH in this context is (seemingly) new, and the two basic similarity measures are interesting.\n+ I would be cautious about calling the method \"A truly constant-time\" method. If we assume K and L are constant then yes; but theoretically in order to get good result we need to have larger values especially for L. Please elaborate on this.\n+ The two theorems offered in the paper are the theorems from the LSH literature. Since a proxy is being used for similarity (e.g., label or embedding) these do not translate into the final classification result. The authors can perhaps elaborate on this and also give clues on how large K and L should be set depending on the parameters of the dataset, etc.\n+ In intro we have \"We show that our technique is not only provable but ..\"; it is not clear what is exactly provable, and how it relates to the classification result. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "YcRFPgAaNI-", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies extreme classification, where the number of classes is very large.\n\nIn that case, previous work came up with a technique to subsample bad classes for each data point to approximate cross-entropy or other used loss. Prior work used uniform samples, but this paper proposes an approach based on locality-sensitive hashing. One particular challenge that the authors need to overcome is updating LSH tables during the backpropagation (where parameters get updated).\n\nThe experiments are very convincing and show that CPU C++ implementation that uses new sampling can outperform GPU-based approach based on uniform sampling.\n\nOne comment is that the writing is fairly sloppy and could use additional polishing.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q2drg7xo13t", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a neighbor search method for negative sampling in extreme classification. The core idea is to use hash tables to select neighbors of a query.\n\nI agree with the authors that:\ni) The proposed hashing method can quickly retrieve neighbors for arbitrary queries in nearly constant time.\nii) Selecting hash functions is important for potential gain.\n\nHowever, I think there are still missing pieces in this paper that need to clarify:\ni) How do you calibrate the negative sampling results?\nii) How do you tune K and L in your experiments. To my understanding, using either too large or too small K and L is suboptimal in your setup.\niii) You mentioned that you are using CPU or computation. But the CPU and GPU precisions may contribute to the final result. Have you studied that in your experiments?\n\nThere are still some points that I disagree with:\ni) There is no consensus that whether “easy negatives” or “hard negatives” should be selected in extreme classifications. For a recent survey on this topic, see “Embedding-based retrieval in Facebook search” by J. Huang et al. So I wonder if the hashing algorithm has the capacity to choose both easy and hard negatives?\n\nii) You claim you are using an O(1) algorithm independent of negative classes N. But this is simply not true and not reasonable because your K and L may need to increase when N grows in order to keep a constant collision probability.\n\niii) You mentioned you propose two schemes: “LSH Embedding” and “LSH Label”. But those two methods only differ in query representations. It would be interesting to compare these two carefully in experiments.\n\nOverall, I think this paper over-claim its contribution even though it proposes a tractable solution to extreme classification.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "HsMP679crn", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\nThe paper proposes a heuristic version of top-k negative sampling which is computationally effective. The main toolbox for this heuristic is locality sensitive hashing. The contribution is mainly algorithmic with an implementation. Experimental results support the effectiveness of the heuristic.\n\n### Strengths\n+ The use of LSH in machine learning applications is very promising, and this paper takes this trend to yet another direction where it can make a difference.\n+ The approach is simple to describe and implement.\n\n### Weaknesses\n- There are several claims that are mostly marketing, namely “adaptivity” and “distribution awareness”. Yes, the sampling depends on the updated weights. But exactly how and in what manner that relates to, say, approximating the true objective, are not treated. The best intuition we can get is by thinking of the new method as a heuristic to top-k negative sampling, leading to believe that maybe some of the latter’s statistical/optimization properties are inherited. But this relationship is not made at all.\n- The Theorems are mostly ornamental, they do not add anything new or relevant.\n- It’s true that the proposed algorithm is amenable to a CPU implementation. But the CPU on which the experiments are run is a behemoth (28 core, 224 thread). So it clearly still needs the added parallelism to be competitive.\n- The significance of the result are weakened when compared against one of the simplest alternatives, the sample softmax (orange curves in Figure 4). It is evident that in terms of reaching the vicinity of the ultimate accuracy, the sample softmax takes the same (if not less) time than the new method [the per-iteration plots are not very relevant, they demonstrate interim accuracy but have no bearing on ultimate accuracy and speed up].\nSo claims like “[these alternatives] fail to demonstrate any training time improvements” (page 2) are clearly false. Granted, sample softmax would be of order $O(\\log N)$, but in practice this clearly is not a handicap.\n- ~~For an application such as this, the details of LSH’s choices are critical, yet the paper only glosses over them. For example, the similarity metrics should differ between the “embedding” version and the “label” version, this is briefly alluded to in the experiments section without much explanation or references.~~ [Edit: thanks for clarifying this.]\n\n### Overall\nThe motivation and approach of the paper are very strong. But the results are not as strong as they are hyped up to be, since a simple alternative achieves the same practical accuracy/time benefits and no guarantees are given for the accuracy of the new heuristic sampling, not even in terms of approximation of another heuristic such as top-k. This means any potential adoption would be based merely on experimental evidence. The fact that the algorithm can be implemented on a (highly parallel) CPU is not a good enough selling point, especially when not pitted against an equivalent optimized CPU implementation of the simple alternative.\n\n_[Edit: The authors do not give any substantive feedback to my review, except for clarifying the hash choices. It is surprising that they object so vehemently to my intuitive description of their method as a heuristic to top-k, when they themselves write \"Our proposed negative sampling scheme is a proxy to topK-softmax. It selects the top-k classes via LSH [...]\". Also my reading of the sampled softmax is directly from their paper, showing a comparable accuracy-time tradeoff, but I was not refuted on this and instead was given other references claiming the inferiority of that method. I have updated my recommendation to reflect these shortcomings.]_\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that this paper is interesting, but needs improvement in order to be suitable for a highly competitive venue such as ICLR. Reviewer 3 is especially incisive and detailed, but other reviewers make similar points.
Decision: Reject