Search papers, labs, and topics across Lattice.
This paper introduces a new family of algorithms, MMO (Multi-Label Metric Optimization), for optimizing generalized linear-fractional metrics like F-measure and Jaccard index in multi-label learning. The key innovation lies in developing novel, combinatorially formulated surrogate loss functions that admit provable H-consistency bounds, providing non-asymptotic guarantees. Experiments on large-scale datasets (MS-COCO, Reuters-21578) demonstrate MMO's superior performance and scalability compared to existing continuous baselines, particularly in high-sparsity, deep learning regimes.
Achieving provable, non-asymptotic guarantees for optimizing complex multi-label metrics like F-measure is now possible with a new family of algorithms that decompose exactly for $O(l)$ time complexity.
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.
Google Research