Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning

Mehryar Mohri; Yutao Zhong

cs.LGMay 27, 2026

Principled Algorithms for Optimizing Generalized Metrics in Multi-Label Learning

Authors: Mehryar Mohri, Yutao Zhong

Organizations: Google Research & CIMS · New York, NY 10011 · Google Research

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.

Explore similar work

Aug 13, 2026cs.LG

Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure

The per-instance Jaccard score, or intersection over union (IoU), is standard in multi-label classification and binary segmentation. With

s

labels, its loss matrix has

2^s

outcomes and reports. Under the convention

\mathrm{Jac}(\varnothing,\varnothing)=1

, we prove that the Jaccard score, shifted-loss, and ordinary loss matrices are nonsingular and that the loss columns have affine dimension

2^s-1

. The proof combines a finite MinHash Gram representation with Boolean Möbius inversion. For exact calibration, we prove

2^{s-1} \leq \mathrm{CCdim}(L^{\mathrm{Jac}}) \leq 2^s-1

. The lower bound uses a factorially weighted distribution with

2^{s-1}+1

supported outcomes and Bayes-optimal reports. Consequently, every exactly calibrated convex surrogate requires exponentially many prediction coordinates. We also give two polynomial-dimensional approximation guarantees with explicit regret transfers. A new

F_1

-to-Jaccard transfer turns an existing

(s^2+1)

-dimensional

F_1

surrogate into a polynomial-time rule with asymptotic Jaccard regret at most

3-2\sqrt{2}

. For any

α>0

and

0<ρ<1

, a MinHash square-loss surrogate attains Jaccard-regret floor

α

uniformly over arbitrary conditional label distributions. With probability at least

1-ρ

, the direct construction has dimension

O((s^2+s\log(1/ρ))/α^2)

, while a signed variant has dimension

O((s+\log(1/ρ))/α^2)

. Thus zero-regret calibration requires exponential dimension, whereas every fixed additive regret tolerance admits polynomial prediction dimension.

Mingyuan Zhang

Weak Labels Multi-Label Classification Loss Function Optimal Sample Complexity Measures Semantic Similarity Metrics

Ask PDF

Aug 9, 2026cs.LG

Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss

The instance-wise

F_1

measure is a central performance measure for multi-label classification. For a problem with

s

labels, it defines a

2^s\times 2^s

loss matrix. Previous work exhibited

s^2+1

-coordinate affine and shifted low-rank representations and used them to construct quadratic-dimensional convex calibrated surrogates. We determine the exact rank. Under the convention

F_1(\varnothing,\varnothing)=1

, the

F_1

score matrix, the shifted loss matrix, and the unshifted loss matrix all have rank

s^2-s+2

, while the column-affine dimension of the loss is

s^2-s+1

. The proof factors the nonempty score matrix through subset-incidence matrices and a positive-definite Cauchy matrix. Exact rank does not, by itself, lower-bound the dimension of an arbitrary convex calibrated surrogate. We therefore analyze the Bayes geometry of

F_1

directly. We construct a distribution for which precisely all supersets of a fixed core label set are Bayes optimal, and show that the corresponding active loss columns, restricted to the witness support, have affine dimension

hn

, where

n=s-\lfloor s/3\rfloor

and

h=\lceil(s\lfloor s/3\rfloor)^{1/2}\rceil-1

. Applying the feasible-subspace lower bound for convex calibration dimension gives

\operatorname{CCdim}(L^{F_1}) \ge \left(\frac{2}{3\sqrt{3}}-o(1)\right)s^2.

Together with the quadratic upper bound, this establishes

\operatorname{CCdim}(L^{F_1})=Θ(s^2)

Mingyuan Zhang

Multi-Label Classification Loss Function Low-Rank Factorization Lower Bounds Ranking

Ask PDF

May 27, 2026cs.LG

Unification and Optimization of Robust Supervised Learning

The literature has proposed various robust alternatives to empirical risk minimisation to address failure modes such as distribution shift, label noise and finite-sample degeneracies. Examples include distributionally robust optimization, label smoothing, vicinal risk minimization, and Mixup. However, such approaches are typically developed in isolation, forcing practitioners to commit a priori to a single failure mode even when the dominant mode for the task is unclear. To address this, we organize a broad class of existing methods along three common design axes and derive a tractable training procedure that decomposes robust learning into sequential stages (reference distribution enrichment, input-space perturbation, label-space perturbation, and sample-level aggregation), each with a choice of stance (pessimistic, neutral, or optimistic). This results in a unified design space in which joint hyperparameter optimization can compose and configure robustness strategies suited to the task at hand. Across tabular, image, and reward modeling benchmarks, joint hyperparameter optimization is competitive with the best single-method baseline in each setting, offering a reliable default for practitioners who do not know a priori which failure mode dominates their task.

Jonas Hanselle, Valentin Margraf, Clemens Damke +1

Empirical Risk Minimization Hyperparameter Enrichment Failure Modes

Ask PDF