Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning
2026-05-27 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study multi-label classification, where many labels can be predicted for each example, and focus on optimizing complex measures like the F-measure and Jaccard index. They create new loss functions that guarantee better learning performance even with limited data, improving upon previous methods that only worked well with very large samples. Their approach also runs efficiently, scaling linearly with the number of labels without sacrificing accuracy. Experiments on big datasets show their method performs better than existing approaches, combining strong theoretical foundations with practical results.
multi-label classificationF-measureJaccard indexEmpirical Utility MaximizationH-consistencysurrogate losslinear-fractional metricsscalabilitydeep learningMS-COCO
Authors
Mehryar Mohri, Yutao Zhong
Abstract
Many real-world classification tasks require predicting multiple labels per instance, necessitating the optimization of complex evaluation metrics such as the $F$-measure and Jaccard index. While the Empirical Utility Maximization (EUM) framework is natural for these population-level metrics, existing theoretical results are largely limited to asymptotic Bayes-consistency. In this paper, we develop principled learning algorithms for optimizing a broad class of generalized metrics within the EUM framework, grounded in the stronger notion of $H$-consistency. Our key contribution is the design of novel surrogate loss functions for multi-label learning that admit provable $H$-consistency bounds, enabling optimization with non-asymptotic guarantees tailored to the hypothesis class and finite samples. Crucially, we prove these combinatorially formulated surrogates decompose exactly, operating in strictly $O(l)$ time without approximations. Building on this foundation, we introduce MMO (Multi-Label Metric Optimization), a new family of algorithms for optimizing generalized linear-fractional metrics. We validate our approach through extensive experiments, demonstrating robust scalability and superior performance over state-of-the-art continuous baselines on large-scale datasets (MS-COCO, Reuters-21578) in high-sparsity, deep learning regimes. Our results offer both theoretical rigor and practical effectiveness for general multi-label metric optimization.