Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure

arXiv:2608.13549v1 Announce Type: new 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(arnothing,arnothing)=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 Mobius inversion. For exact calibration, we prove 2^{s-1} leq CCdim(L^{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-2sqrt{2}. For any alpha>0 and 0<rho<1, a MinHash square-loss surrogate attains Jaccard-regret floor alpha uniformly over arbitrary conditional label distributions. With probability at least 1-rho, the direct construction has dimension O((s^2+slog(1/rho))/alpha^2), while a signed variant has dimension O((s+log(1/rho))/alpha^2). Thus zero-regret calibration requires exponential dimension, whereas every fixed additive regret tolerance admits polynomial prediction dimension.

Related

• Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss
• High-Dimensional Calibration from Swap Regret
• Optimal and Provable Calibration in High-Dimensional Binary Classification: Angular Calibration and Platt Scaling

Source: arXiv cs.LG | 2026-08-14