# Efficient Training on Very Large Corpora via Gramian Estimation

arXiv: https://arxiv.org/abs/1807.07187 · HTML: https://mlsanity.com/paper/1807.07187/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2018.

## Built on by (most cited first, 9 of 9)

- [DeepXML: A Deep Extreme Multi-Label Learning Framework Applied to Short Text Documents](https://mlsanity.com/paper/2111.06685/) (2021)
- [Item Recommendation from Implicit Feedback](https://mlsanity.com/paper/2101.08769/) (2021)
- [Evaluating Multi-label Classifiers with Noisy Labels](https://mlsanity.com/paper/2102.08427/) (2021)
- [ELM: Embedding and Logit Margins for Long-Tail Learning](https://mlsanity.com/paper/2204.13208/) (2022)
- [On Estimating Recommendation Evaluation Metrics under Sampling](https://mlsanity.com/paper/2103.01474/) (2021)
- [ALX: Large Scale Matrix Factorization on TPUs](https://mlsanity.com/paper/2112.02194/) (2021)
- [Safe Collaborative Filtering](https://mlsanity.com/paper/2306.05292/) (2023)
- [EfficientRec an unlimited user-item scale recommendation system based on clustering and users interaction embedding profile](https://mlsanity.com/paper/2401.09693/) (2024)
- [NDCG-Consistent Softmax Approximation with Accelerated Convergence](https://mlsanity.com/paper/2506.09454/) (2025)

## Abstract (arXiv)

We study the problem of learning similarity functions over very large corpora using neural network embedding models. These models are typically trained using SGD with sampling of random observed and unobserved pairs, with a number of samples that grows quadratically with the corpus size, making it expensive to scale to very large corpora. We propose new efficient methods to train these models without having to sample unobserved pairs. Inspired by matrix factorization, our approach relies on adding a global quadratic penalty to all pairs of examples and expressing this term as the matrix-inner-product of two generalized Gramians. We show that the gradient of this term can be efficiently computed by maintaining estimates of the Gramians, and develop variance reduction schemes to improve the quality of the estimates. We conduct large-scale experiments that show a significant improvement in training time and generalization quality compared to traditional sampling methods.