Introduction
Training high-quality embedding models often relies on Positive Unlabeled (PU) data, where only positive interactions (e.g., a user clicking a link) are observed, while the remaining vast pool of data is unlabeled. Traditional approaches like Negative Sampling (NS) provide efficiency but introduce noise and sampling bias. Conversely, standard Batch Gradient Descent (BGD) is computationally prohibitive for large-scale datasets. This paper introduces $f_{BGD}$, a fast and generic BGD optimizer that achieves the accuracy of full-batch learning with the efficiency of stochastic methods.
The Challenge of Positive Unlabeled Learning
In domains such as recommendation systems or natural language processing, we typically lack explicit negative signals. The industry standard, Negative Sampling, treats a subset of unlabeled data as negatives. While fast, this approach ignores most of the available data and leads to high gradient variance.
Full BGD considers every possible pair, but its complexity is $O(|X||Y|g)$, where $|X|$ and $|Y|$ are the number of entities and $g$ is the embedding dimension. For a million users and items, this results in a trillion calculations per iteration, making it unusable for large-scale applications.
The $f_{BGD}$ Framework
The authors propose two primary innovations to overcome these hurdles:
- Mathematical Acceleration: By exploiting the dot-product structure of models like Matrix Factorization, the loss function is reformulated. Instead of iterating over every unlabeled pair, the algorithm computes the loss over all possible pairs and subtracts the known positives. Through precomputing vector "caches," the complexity is reduced to $O((|X|+|Y|)g^2)$, making BGD as fast as NS-based stochastic gradient descent.
- Stabilizing Sparse Gradients: Sparse data often leads to gradient instability in BGD. Frequent features can cause gradients to explode, while rare ones cause them to vanish. The authors implemented a specialized adaptive learning rate (similar to AdaGrad) to stabilize training in the full-batch setting.
Experimental Evaluation
The $f_{BGD}$ framework was evaluated across five benchmark datasets in three domains:
- NLP: NewsIR and Text8 for word embeddings.
- Information Retrieval: Yahoo Music and Lastfm for collaborative filtering.
- Computer Vision: OpenImages for image classification.
Key Results and Insights
$f_{BGD}$ consistently outperformed state-of-the-art baselines, including Skip-gram (Word2Vec) and SVDFeature. The results demonstrate that the performance gap in modern embeddings is often due to sampling bias rather than model architecture. By utilizing 100% of the unlabeled data, $f_{BGD}$ finds superior optima.
As shown in the figure above, the "Improved fBGD" with an optimized learning rate significantly outperforms standard configurations, reaching higher NDCG@10 scores much faster. Furthermore, the training time remains competitive; on the NewsIR dataset, $f_{BGD}$ completed an iteration in nearly half the time required by a comparable Skip-gram setup.
Conclusion and Future Work
The $f_{BGD}$ framework proves that full-batch learning is not only viable but superior for large-scale sparse embedding tasks. While currently optimized for dot-product models, future research may extend these acceleration techniques to deep non-linear architectures like Transformers and explore more dynamic weighting schemes for unlabeled data.
Summary updated