# Online and Stochastic Gradient Methods for Non-decomposable Loss Functions

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2014.

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

- [AUC Maximization in the Era of Big Data and AI: A Survey](https://mlsanity.com/paper/2203.15046/) (2022)
- [When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee](https://mlsanity.com/paper/2203.00176/) (2022)
- [Large-scale Optimization of Partial AUC in a Range of False Positive Rates](https://mlsanity.com/paper/2203.01505/) (2022)
- [Optimizing Two-way Partial AUC with an End-to-end Framework](https://mlsanity.com/paper/2206.11655/) (2022)
- [Training Over-parameterized Models with Non-decomposable Objectives](https://mlsanity.com/paper/2107.04641/) (2021)
- [Multi-block Min-max Bilevel Optimization with Applications in Multi-task Deep AUC Maximization](https://mlsanity.com/paper/2206.00260/) (2022)
- [Non-Smooth Weakly-Convex Finite-sum Coupled Compositional Optimization](https://mlsanity.com/paper/2310.03234/) (2023)
- [Implicit Rate-Constrained Optimization of Non-decomposable Objectives](https://mlsanity.com/paper/2107.10960/) (2021)
- [Optimizing Black-box Metrics with Iterative Example Weighting](https://mlsanity.com/paper/2102.09492/) (2021)
- [Deep AUC Maximization for Medical Image Classification: Challenges and Opportunities](https://mlsanity.com/paper/2111.02400/) (2021)
- [Principled Algorithms for Optimizing Generalized Metrics in Binary Classification](https://mlsanity.com/paper/2512.23133/) (2025)
- [A surrogate loss function for optimization of Fβ score in binary classification with imbalanced data](https://mlsanity.com/paper/2104.01459/) (2021)
- [Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm](https://mlsanity.com/paper/2210.03967/) (2022)
- [Counterfactual Learning To Rank for Utility-Maximizing Query Autocompletion](https://mlsanity.com/paper/2204.10936/) (2022)
- [A General Online Algorithm for Optimizing Complex Performance Metrics](https://mlsanity.com/paper/2406.14743/) (2024)
- [Simple Weak Coresets for Non-Decomposable Classification Measures](https://mlsanity.com/paper/2312.09885/) (2023)
- [Stochastic Primal-Dual Double Block-Coordinate for Two-way Partial AUC Maximization](https://mlsanity.com/paper/2505.21944/) (2025)
- [How Good are Low-Rank Approximations in Gaussian Process Regression?](https://mlsanity.com/paper/2112.06410/) (2021)
- [Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations](https://mlsanity.com/paper/2512.01213/) (2025)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)
- [Weighted Score-Oriented Losses for Temporally Localized Event Prediction](https://mlsanity.com/paper/2606.23145/) (2026)

## Abstract (arXiv)

Modern applications in sensitive domains such as biometrics and medicine frequently require the use of non-decomposable loss functions such as precision@k, F-measure etc. Compared to point loss functions such as hinge-loss, these offer much more fine grained control over prediction, but at the same time present novel challenges in terms of algorithm design and analysis. In this work we initiate a study of online learning techniques for such non-decomposable loss functions with an aim to enable incremental learning as well as design scalable solvers for batch problems. To this end, we propose an online learning framework for such loss functions. Our model enjoys several nice properties, chief amongst them being the existence of efficient online learning algorithms with sublinear regret and online to batch conversion bounds. Our model is a provable extension of existing online learning models for point loss functions. We instantiate two popular losses, prec@k and pAUC, in our model and prove sublinear regret bounds for both of them. Our proofs require a novel structural lemma over ranked lists which may be of independent interest. We then develop scalable stochastic gradient descent solvers for non-decomposable loss functions. We show that for a large family of loss functions satisfying a certain uniform convergence property (that includes prec@k, pAUC, and F-measure), our methods provably converge to the empirical risk minimizer. Such uniform convergence results were not known for these losses and we establish these using novel proof techniques. We then use extensive experimentation on real life and benchmark datasets to establish that our method can be orders of magnitude faster than a recently proposed cutting plane method.