# Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 60 references that are in the map.
- First posted on arXiv 24 Feb 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation](https://mlsanity.com/paper/2002.02126/) (2020)
- [Neural Collaborative Filtering](https://mlsanity.com/paper/1708.05031/) (2017)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Neural Graph Collaborative Filtering](https://mlsanity.com/paper/1905.08108/) (2019)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Approximation Methods for Bilevel Programming](https://mlsanity.com/paper/1802.02246/) (2018)
- [Introducing LETOR 4.0 Datasets](https://mlsanity.com/paper/1306.2597/) (2013)
- [Stochastic Optimization of Sorting Networks via Continuous Relaxations](https://mlsanity.com/paper/1903.08850/) (2019)
- [Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions](https://mlsanity.com/paper/1411.3803/) (2014)
- [A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton](https://mlsanity.com/paper/2006.04045/) (2020)
- [NAIS: Neural Attentive Item Similarity Model for Recommendation](https://mlsanity.com/paper/1809.07053/) (2018)
- [Solving Stochastic Compositional Optimization is Nearly as Easy as Solving Stochastic Optimization](https://mlsanity.com/paper/2008.10847/) (2020)
- [Biased Stochastic First-Order Methods for Conditional Stochastic Optimization and Applications in Meta Learning](https://mlsanity.com/paper/2002.10790/) (2020)
- [NeuralNDCG: Direct Optimisation of a Ranking Metric via Differentiable Relaxation of Sorting](https://mlsanity.com/paper/2102.07831/) (2021)
- [Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization](https://mlsanity.com/paper/2105.02266/) (2021)
- [TF-Ranking: Scalable TensorFlow Library for Learning-to-Rank](https://mlsanity.com/paper/1812.00073/) (2018)
- [PiRank: Scalable Learning To Rank via Differentiable Sorting](https://mlsanity.com/paper/2012.06731/) (2020)
- [Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates](https://mlsanity.com/paper/2008.10526/) (2020)
- [Learning Groupwise Multivariate Scoring Functions Using Deep Neural Networks](https://mlsanity.com/paper/1811.04415/) (2018)
- [Context-Aware Learning to Rank with Self-Attention](https://mlsanity.com/paper/2005.10084/) (2020)
- [Overcoming Data Sparsity in Group Recommendation](https://mlsanity.com/paper/2010.00813/) (2020)
- [RSG: Beating Subgradient Method without Smoothness and Strong Convexity](https://mlsanity.com/paper/1512.03107/) (2015)

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

- [LibAUC: A Deep Learning Library for X-Risk Optimization](https://mlsanity.com/paper/2306.03065/) (2023)
- [Contextual Stochastic Bilevel Optimization](https://mlsanity.com/paper/2310.18535/) (2023)
- [Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization](https://mlsanity.com/paper/2206.00260/) (2022)
- [FeDXL: Provable Federated Learning for Deep X-Risk Optimization](https://mlsanity.com/paper/2210.14396/) (2022)
- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [Lower-Left Partial AUC: An Effective and Efficient Optimization Metric for Recommendation](https://mlsanity.com/paper/2403.00844/) (2024)
- [Breaking the Top-K Barrier: Advancing Top-K Ranking Metrics Optimization in Recommender Systems](https://mlsanity.com/paper/2508.05673/) (2025)
- [Algorithmic Foundations of Empirical X-risk Minimization](https://mlsanity.com/paper/2206.00439/) (2022)
- [Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization](https://mlsanity.com/paper/2305.18730/) (2023)
- [A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization](https://mlsanity.com/paper/2312.02277/) (2023)
- [Efficient and Effective Implicit Dynamic Graph Neural Network](https://mlsanity.com/paper/2406.17894/) (2024)
- [Provable Optimization for Adversarial Fair Self-supervised Contrastive Learning](https://mlsanity.com/paper/2406.05686/) (2024)
- [SpatialRank: Urban Event Ranking with NDCG Optimization on Spatiotemporal Data](https://mlsanity.com/paper/2310.00270/) (2023)
- [Top-K Pairwise Ranking: Bridging the Gap Among Ranking-Based Measures for Multi-Label Classification](https://mlsanity.com/paper/2407.06709/) (2024)
- [Discovering Global False Negatives On the Fly for Self-supervised Contrastive Learning](https://mlsanity.com/paper/2502.20612/) (2025)
- [Iterative Sampling Methods for Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2512.12550/) (2025)
- [A Geometry-Aware Efficient Algorithm for Compositional Entropic Risk Minimization](https://mlsanity.com/paper/2602.02877/) (2026)
- [Learning to Rank with Top-K Fairness](https://mlsanity.com/paper/2509.18067/) (2025)
- [Is Softmax Loss All You Need? A Principled Analysis of Softmax-family Loss](https://mlsanity.com/paper/2601.22745/) (2026)
- [Decoupling Strategy and Execution in Task-Focused Dialogue via Goal-Oriented Preference Optimization](https://mlsanity.com/paper/2602.15854/) (2026)
- [PRISMR: Overcoming Parse Collapse in Multimodal Listwise Ranking via Parameterized Representation Internalization](https://mlsanity.com/paper/2606.12942/) (2026)
- [Learning What to Distill: Bilevel Top-K Token Selection for Self-Distillation in Large Language Models](https://mlsanity.com/paper/2610.07247/) (2026)

## Abstract (arXiv)

NDCG, namely Normalized Discounted Cumulative Gain, is a widely used ranking metric in information retrieval and machine learning. However, efficient and provable stochastic methods for maximizing NDCG are still lacking, especially for deep models. In this paper, we propose a principled approach to optimize NDCG and its top-K variant. First, we formulate a novel compositional optimization problem for optimizing the NDCG surrogate, and a novel bilevel compositional optimization problem for optimizing the top-K NDCG surrogate. Then, we develop efficient stochastic algorithms with provable convergence guarantees for the non-convex objectives. Different from existing NDCG optimization methods, the per-iteration complexity of our algorithms scales with the mini-batch size instead of the number of total items. To improve the effectiveness for deep learning, we further propose practical strategies by using initial warm-up and stop gradient operator. Experimental results on multiple datasets demonstrate that our methods outperform prior ranking approaches in terms of NDCG. To the best of our knowledge, this is the first time that stochastic algorithms are proposed to optimize NDCG with a provable convergence guarantee. Our proposed methods are implemented in the LibAUC library at https://libauc.org/.