Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure
2026-08-13 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study the Jaccard score, a common measure used in tasks where multiple labels are predicted at once. They show that to perfectly match (calibrate) the Jaccard score using convex surrogate losses, one needs an exponentially large number of prediction values, making exact calibration very complex. However, they also provide ways to approximate the Jaccard score with polynomial-sized models that keep the prediction error within a certain small range. Their work balances understanding the theoretical limits of exact calibration with practical approaches for approximate solutions.
Jaccard scoreintersection over unionmulti-label classificationconvex surrogate losscalibrationMinHashBoolean Möbius inversionregret boundsprediction dimensionexact calibration
Authors
Mingyuan Zhang
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 $\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.