SOLAR: Sparse Orthogonal Learned and Random Embeddings
  Dense embedding models are commonly deployed in commercial search engines,
wherein all the document vectors are pre-computed, and near-neighbor search
(NNS) is performed with the query vector to find relevant documents. However,
the bottleneck of indexing a large number of dense vectors and performing an
NNS hurts the query time and accuracy of these models. In this paper, we argue
that high-dimensional and ultra-sparse embedding is a significantly superior
alternative to dense low-dimensional embedding for both query efficiency and
accuracy. Extreme sparsity eliminates the need for NNS by replacing them with
simple lookups, while its high dimensionality ensures that the embeddings are
informative even when sparse. However, learning extremely high dimensional
embeddings leads to blow up in the model size. To make the training feasible,
we propose a partitioning algorithm that learns such high dimensional
embeddings across multiple GPUs without any communication. This is facilitated
by our novel asymmetric mixture of Sparse, Orthogonal, Learned and Random
(SOLAR) Embeddings. The label vectors are random, sparse, and near-orthogonal
by design, while the query vectors are learned and sparse. We theoretically
prove that our way of one-sided learning is equivalent to learning both query
and label embeddings. With these unique properties, we can successfully train
500K dimensional SOLAR embeddings for the tasks of searching through 1.6M books
and multi-label classification on the three largest public datasets. We achieve
superior precision and recall compared to the respective state-of-the-art
baselines for each of the tasks with up to 10 times faster speed.
