# NDCG-Consistent Softmax Approximation with Accelerated Convergence

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 65 references that are in the map.
- First posted on arXiv 11 Jun 2025.

## Builds on (most cited first, 25 of 25)

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [SimCSE: Simple Contrastive Learning of Sentence Embeddings](https://mlsanity.com/paper/2104.08821/) (2021)
- [Self-Attentive Sequential Recommendation](https://mlsanity.com/paper/1808.09781/) (2018)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [BERT4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer](https://mlsanity.com/paper/1904.06690/) (2019)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification](https://mlsanity.com/paper/1602.02068/) (2016)
- [Variational Autoencoders for Collaborative Filtering](https://mlsanity.com/paper/1802.05814/) (2018)
- [Learning Fine-grained Image Similarity with Deep Ranking](https://mlsanity.com/paper/1404.4661/) (2014)
- [Non-convex Optimization for Machine Learning](https://mlsanity.com/paper/1712.07897/) (2017)
- [A no-regret generalization of hierarchical softmax to extreme multi-label classification](https://mlsanity.com/paper/1810.11671/) (2018)
- [On the Effectiveness of Sampled Softmax Loss for Item Recommendation](https://mlsanity.com/paper/2201.02327/) (2022)
- [On the Consistency of Top-k Surrogate Losses](https://mlsanity.com/paper/1901.11141/) (2019)
- [Revisiting the Performance of iALS on Item Recommendation Benchmarks](https://mlsanity.com/paper/2110.14037/) (2021)
- [Item Recommendation from Implicit Feedback](https://mlsanity.com/paper/2101.08769/) (2021)
- [An Alternative Cross Entropy Loss for Learning-to-Rank](https://mlsanity.com/paper/1911.09798/) (2019)
- [A Generic Coordinate Descent Framework for Learning from Implicit Feedback](https://mlsanity.com/paper/1611.04666/) (2016)
- [Efficient Training on Very Large Corpora via Gramian Estimation](https://mlsanity.com/paper/1807.07187/) (2018)
- [Learning Explicit User Interest Boundary for Recommendation](https://mlsanity.com/paper/2111.11026/) (2021)
- [Cooperative Retriever and Ranker in Deep Recommenders](https://mlsanity.com/paper/2206.14649/) (2022)

## Abstract (arXiv)

Ranking tasks constitute fundamental components of extreme similarity learning frameworks, where extremely large corpora of objects are modeled through relative similarity relationships adhering to predefined ordinal structures. Among various ranking surrogates, Softmax (SM) Loss has been widely adopted due to its natural capability to handle listwise ranking via global negative comparisons, along with its flexibility across diverse application scenarios. However, despite its effectiveness, SM Loss often suffers from significant computational overhead and scalability limitations when applied to large-scale object spaces. To address this challenge, we propose novel loss formulations that align directly with ranking metrics: the Ranking-Generalizable squared (RG2) Loss and the Ranking-Generalizable interactive (RG^×) Loss, both derived through Taylor expansions of the SM Loss. Notably, RG2 reveals the intrinsic mechanisms underlying weighted squared losses (WSL) in ranking methods and uncovers fundamental connections between sampling-based and non-sampling-based loss paradigms. Furthermore, we integrate the proposed RG losses with the highly efficient Alternating Least Squares (ALS) optimization method, providing both generalization guarantees and convergence rate analyses. Empirical evaluations on real-world datasets demonstrate that our approach achieves comparable or superior ranking performance relative to SM Loss, while significantly accelerating convergence. This framework offers the similarity learning community both theoretical insights and practically efficient tools, with methodologies applicable to a broad range of tasks where balancing ranking quality and computational efficiency is essential.