Paper Overview
- Field: Machine Learning
- Author: Mingyuan Zhang
- Published: 2026-08-13
- arXiv: 2608.13549
- A new F1-to-Jaccard transfer turns an existing (s^2+1)-dimensional F1 surrogate into a polynomial-time rule with asymptotic Jaccard regret at most 3-2√2.
- For any α>0 and 0<ρ<1, a MinHash square-loss surrogate attains a 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).
Summary
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 author 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 Mobius inversion.
For exact calibration, the paper proves:
2^(s-1) ≤ CCdim(L^Jac) ≤ 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.
The paper also gives two polynomial-dimensional approximation guarantees with explicit regret transfers:
Key Takeaway
Zero-regret calibration requires exponential dimension, whereas every fixed additive regret tolerance admits polynomial prediction dimension.
Original abstract (via arXiv:2608.13549).