Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning

• URL: http://arxiv.org/abs/2605.28767v1
• Date: Wed, 27 May 2026 17:23:58 GMT
• Title: Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning
• Abstract summary: We develop principled learning algorithms for optimizing a broad class of generalized metrics within the Empirical Utility Maximization framework.<n>Our key contribution is the design of novel surrogate loss functions for multi-label learning that provable $H$-consistency bounds.<n>Our results offer both theoretical rigor and practical effectiveness for general multi-label metric optimization.
• Score: 42.67092904252001
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Multiple-Prediction-Powered Inference [57.30769275944024]
  This work provides theoretical guarantees about the minimax optimality, finite-sample performance, and normality of the MultiPPI estimator.<n>We show that MultiPPI consistently achieves lower estimation error than existing baselines.
  arXiv  Detail & Related papers  (2026-03-28T21:24:00Z)
• Generalized Optimal Classification Trees: A Mixed-Integer Programming Approach [17.725629133949955]
  Mixed-integer programming (MIP) offers a high degree of modeling flexibility.<n>We propose a MIP-based framework for learning optimal classification trees under nonlinear performance metrics.<n>We evaluate the proposed approach on 50 benchmark datasets.
  arXiv  Detail & Related papers  (2026-02-02T14:46:01Z)
• Principled Algorithms for Optimizing Generalized Metrics in Binary Classification [53.604375124674796]
  We introduce principled algorithms for optimizing generalized metrics, supported by $H$-consistency and finite-sample generalization bounds.<n>Our approach reformulates metric optimization as a generalized cost-sensitive learning problem.<n>We develop new algorithms, METRO, with strong theoretical performance guarantees.
  arXiv  Detail & Related papers  (2025-12-29T01:33:42Z)
• NDCG-Consistent Softmax Approximation with Accelerated Convergence [67.10365329542365]
  We propose novel loss formulations that align directly with ranking metrics.<n>We integrate the proposed RG losses with the highly efficient Alternating Least Squares (ALS) optimization method.<n> Empirical evaluations on real-world datasets demonstrate that our approach achieves comparable or superior ranking performance.
  arXiv  Detail & Related papers  (2025-06-11T06:59:17Z)
• Adaptive Sampled Softmax with Inverted Multi-Index: Methods, Theory and Applications [79.53938312089308]
  The MIDX-Sampler is a novel adaptive sampling strategy based on an inverted multi-index approach.<n>Our method is backed by rigorous theoretical analysis, addressing key concerns such as sampling bias, gradient bias, convergence rates, and generalization error bounds.
  arXiv  Detail & Related papers  (2025-01-15T04:09:21Z)
• Stochastic interior-point methods for smooth conic optimization with applications [0.8519339317685906]
  We introduce an interior-point method for general conic optimization, along with four novel SIPM variants.<n>Under underdeveloped assumptions, we establish the complexity of our proposed SIPMs, which, up to a polylogarithmic factor, match the best-known results in unconstrained data streams.<n>Experiments on robust linear regression, multi-task relationship learning, and clustering data streams demonstrate the effectiveness of our approach.
  arXiv  Detail & Related papers  (2024-12-17T15:06:44Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• Online Metric Learning for Multi-Label Classification [22.484707213499714]
  We propose a novel online metric learning paradigm for multi-label classification. We first propose a new metric for multi-label classification based on $k$-Nearest Neighbour ($k$NN)
  arXiv  Detail & Related papers  (2020-06-12T11:33:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.