Research map / Bandits and online learning / Online convex optimization and games
A General Online Algorithm for Optimizing Complex Performance Metrics
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes OMMA, a constant-memory online algorithm that maximizes non-decomposable confusion-matrix metrics by predicting with a linearized gradient objective over a conditional probability estimator, with O(ln n / n) regret for concave smooth metrics.
Problem
Online maximization of non-decomposable performance metrics (F-measure, G-mean, H-mean, precision@k, etc.) that are general functions of the confusion matrix, in binary, multi-class, multi-label and budgeted settings, where predictions must be made immediately without revision.
Approach
At each trial, predict the label vector maximizing the gradient of the metric at the current running confusion matrix dotted with the expected confusion matrix under the CPE's probability estimate; this reduces to thresholding or sorting linear functions of the estimated probabilities, needing only a constant-size confusion matrix in memory.
Key results
- OMMA matches Online Frank-Wolfe on most metrics while using less time and memory, and substantially outperforms it on macro precision@3 (e.g., 91.41 vs 54.52 on Ledgar-LexGlue).
- OMMA achieves O(ln n / n) regret for concave, smooth utilities up to CPE estimation error, and O(sqrt(ln n / n)) for non-smooth utilities via smoothing.
- The variant OMMA(eta-hat), which updates its internal confusion matrix with probability estimates instead of labels, often performs better on macro metrics, notably on datasets with many labels.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the OMMA linearized utility update rather than the online Frank-Wolfe update | Online multi-label classification · Most reported multi-label benchmarks | Performance across reported metrics | Mixed |
| Use OMMA for Macro Precision@3 instead of the compared online methods | Online multi-label classification · Multi-label benchmarks | Macro Precision@3 | Helped |
| Update the internal confusion matrix using estimated probabilities instead of observed labels (ablation) | OMMA · Benchmarks with many labels | Macro-averaged metrics | Helped |
| Update the internal confusion matrix using estimated probabilities instead of observed labels (ablation) | OMMA · Eurlex-LexGlue | Macro F1: 59.85 -> 59.84 | No clear effect |
| Update the internal confusion matrix using estimated probabilities instead of observed labels (ablation) | OMMA · AmazonCat | Macro F1: 43.04 -> 47.67 | Helped |
| Update the internal confusion matrix using estimated probabilities instead of observed labels (ablation) | OMMA · YouTube | Macro F1: 36.34 -> 36.47 | Helped |
| Update the internal confusion matrix using estimated probabilities instead of observed labels (ablation) | OMMA · Ledgar-LexGlue | Macro F1: 79.28 -> 79.34 | No clear effect |
| Update the internal confusion matrix using estimated probabilities instead of observed labels (ablation) | OMMA · Caltech-256 | Macro F1: 79.54 -> 79.66 | Helped |
Surprising findings
- Ignoring true label feedback and updating the internal confusion matrix with the CPE (OMMA(eta-hat)) often performs better on macro-averaged metrics with many labels, attributed to variance reduction.
- In the adversarial (non-i.i.d.) input setting, any algorithm suffers regret at least 1/36 - o(1), so a stochastic data assumption is necessary.
Limitations
- Regret analysis requires concavity and smoothness of the metric, excluding linear-fractional metrics such as binary or micro F-measure.
- Lipschitzness and smoothness are needed along the algorithm's path, which may fail under severe class imbalance; stabilization via epsilon and lambda regularization is heuristic.
- Bounds depend on the CPE estimation error; convergence for OMMA(eta-hat) with non-exact CPE is unclear.
Experimental setup
Datasets: News20 Ledgar-LexGlue Caltech-256 YouTube Flickr Eurlex-LexGlue Mediamill RCV1X AmazonCat
Benchmarks: News20 Ledgar-LexGlue Caltech-256 YouTube Flickr Eurlex-LexGlue Mediamill RCV1X AmazonCat
Metrics: micro F1 macro F1 macro F1@3 macro recall@3 macro precision@3 G-mean H-mean Q-mean
Baselines: Top-k OFO Greedy Online-FW Online-FW(eta-hat)
Builds on: Frank-Wolfe algorithm online F-measure optimization (OFO) cost-sensitive classification
Closest papers by meaning
- Online Maximization of Non-Decomposable Test and Population Utilities (NeurIPS 2026 · similarity 0.90)
- Consistent algorithms for multi-label classification with macro-at-$k$ metrics (ICLR 2024 · similarity 0.88)
- Principled Algorithms for Optimizing Generalized Metrics in Binary Classification (ICML 2025 · similarity 0.87)
- Optimizing Black-box Metrics with Iterative Example Weighting (ICML 2021 · similarity 0.87)
- Online Metric Learning for Multi-Label Classification (AAAI 2020 · similarity 0.87)
- Online Classification with Predictions (NeurIPS 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.