Online Maximization of Non-Decomposable Test and Population Utilities

We study sequential learning for classification metrics that are non-decomposable across instances and are general functions of the confusion matrix, such as the Jaccard index and the $F$-measure. The learner observes instances sequentially, makes irrevocable predictions, and is evaluated by the final empirical performance metric, leading to an online-regret objective. After observing the sequence, the learner also returns a classifier for future population use, leading to a population-regret objective. This single protocol connects two central frameworks for optimizing non-decomposable metrics: Expected Test Utility (ETU) and Population Utility (PU). For smooth concave utilities of the confusion matrix, we show that the ETU benchmark is controlled, in expectation, by the population PU comparator, and that an algorithm with small online regret also yields PU guarantees by an online-to-batch conversion. We then turn to non-concave linear-fractional metrics. We devise a general stochastic Dinkelbach-root method that tracks the relevant metric parameter online and gives online and population regret of order $n^{-1/2}$, up to logarithmic factors, with explicit dependence on conditional-probability estimation error. Our empirical studies evaluate these methods on benchmark datasets.