# A General Online Algorithm for Optimizing Complex Performance Metrics

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 51 references that are in the map.
- First posted on arXiv 20 Jun 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss](https://mlsanity.com/paper/1906.07413/) (2019)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [LexGLUE: A Benchmark Dataset for Legal Language Understanding in English](https://mlsanity.com/paper/2110.00976/) (2021)
- [DiSMEC - Distributed Sparse Machines for Extreme Multi-label Classification](https://mlsanity.com/paper/1609.02521/) (2016)
- [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016)
- [Online and Stochastic Gradient Methods for Non-decomposable Loss Functions](https://mlsanity.com/paper/1410.6776/) (2014)
- [Optimizing Non-decomposable Performance Measures: A Tale of Two Classes](https://mlsanity.com/paper/1505.06812/) (2015)
- [On the Bayes-optimality of F-measure maximizers](https://mlsanity.com/paper/1310.4849/) (2013)
- [Surrogate regret bounds for generalized classification performance metrics](https://mlsanity.com/paper/1504.07272/) (2015)
- [Generalized test utilities for long-tail performance in extreme multi-label classification](https://mlsanity.com/paper/2311.05081/) (2023)
- [Optimal Binary Classification Beyond Accuracy](https://mlsanity.com/paper/2107.01777/) (2021)
- [Consistent algorithms for multi-label classification with macro-at-k metrics](https://mlsanity.com/paper/2401.16594/) (2024)

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

- [Principled Algorithms for Optimizing Generalized Metrics in Binary Classification](https://mlsanity.com/paper/2512.23133/) (2025)
- [Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning](https://mlsanity.com/paper/2605.28767/) (2026)

## Abstract (arXiv)

We consider sequential maximization of performance metrics that are general functions of a confusion matrix of a classifier (such as precision, F-measure, or G-mean). Such metrics are, in general, non-decomposable over individual instances, making their optimization very challenging. While they have been extensively studied under different frameworks in the batch setting, their analysis in the online learning regime is very limited, with only a few distinguished exceptions. In this paper, we introduce and analyze a general online algorithm that can be used in a straightforward way with a variety of complex performance metrics in binary, multi-class, and multi-label classification problems. The algorithm's update and prediction rules are appealingly simple and computationally efficient without the need to store any past data. We show the algorithm attains O(fracln nn) regret for concave and smooth metrics and verify the efficiency of the proposed algorithm in empirical studies.