Exponential Convex Calibration Dimension for the Multi-Label Jaccard Metric: Paper by Mingyuan Zhang

Forum topic · 小凯 · 2026-08-15

Summary

This paper (arXiv:2608.13549) by Mingyuan Zhang studies convex calibration of the per-instance Jaccard score (IoU), the standard metric in multi-label classification and binary segmentation. For s labels, the loss matrix has 2^s outcomes and reports. Under the convention Jac(∅,∅)=1, the author proves that the Jaccard, shifted-loss, and ordinary loss matrices are nonsingular with loss columns of affine dimension 2^s-1, using a finite MinHash Gram representation combined with Boolean Möbius inversion. For exact calibration, the convex calibration dimension satisfies 2^(s-1) ≤ CCdim(L^Jac) ≤ 2^s-1, implying every exactly calibrated convex surrogate needs exponentially many prediction coordinates. Two polynomial-dimensional approximation guarantees are also given: an F1-to-Jaccard regret transfer achieving asymptotic Jaccard regret at most 3-2√2, and MinHash square-loss surrogates attaining regret floor α with dimensions O((s^2+s log(1/ρ))/α²) and O((s+log(1/ρ))/α²). The takeaway: zero-regret calibration requires exponential dimension, while any fixed additive regret tolerance admits polynomial dimension.

Paper Overview

Field: Machine Learning Author: Mingyuan Zhang Published: 2026-08-13 arXiv: 2608.13549

Abstract

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 Jac(∅,∅)=1, the paper proves 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, the paper proves:

2^{s-1} \le \mathrm{CCdim}(L^{\mathrm{Jac}}) \le 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.

Approximation Guarantees

The paper also gives two polynomial-dimensional approximation guarantees with explicit regret transfers:

F1-to-Jaccard transfer: a new transfer turns an existing (s²+1)-dimensional F1 surrogate into a polynomial-time rule with asymptotic Jaccard regret at most 3-2√2.
MinHash square-loss surrogate: for any α>0 and 0<ρ<1, it attains a Jaccard-regret floor α uniformly over arbitrary conditional label distributions. With probability at least 1-ρ, the direct construction has dimension O((s² + s·log(1/ρ))/α²), while a signed variant has dimension O((s + log(1/ρ))/α²).

Key Takeaway

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