Summary
This paper studies the convex calibration complexity of the per-instance Jaccard score (intersection over union) used in multi-label classification and binary segmentation. For s labels, the loss matrix has 2^s outcomes. Using a convention Jac(∅,∅)=1 and a finite MinHash Gram representation combined with Boolean Möbius inversion, the authors prove that the Jaccard, shifted-loss, and ordinary loss matrices are nonsingular and that their loss columns span an affine subspace of dimension 2^s − 1. For exact calibration, they bound the convex calibration dimension by 2^(s−1) ≤ CCdim(L^Jac) ≤ 2^s − 1, establishing an exponential lower bound via a factorially weighted distribution with 2^(s−1)+1 supported outcomes and Bayes-optimal reports. They further provide two polynomial-dimensional approximation guarantees with explicit regret transfers, including an F1-to-Jaccard transfer yielding asymptotic regret at most 3 − 2√2 and a MinHash square-loss surrogate with regret floor α and dimension O((s^2 + s log(1/ρ))/α^2), reduced to O((s + log(1/ρ))/α^2) by a signed variant. The work demonstrates that zero-regret calibration is exponentially hard while any fixed additive regret tolerance admits polynomial dimension.
Paper Overview
- Field: Machine Learning
- Author: Mingyuan Zhang
- arXiv: 2608.13549
Key Points
- Loss-matrix structure for Jaccard (IoU): With s labels the Jaccard loss matrix has 2^s outcomes and reports. Under the convention Jac(∅,∅)=1, the Jaccard, shifted-loss, and ordinary loss matrices are nonsingular, and their loss columns have affine dimension 2^s − 1. The proof relies on a finite MinHash Gram representation together with Boolean Möbius inversion.
- Exact calibration is exponential: The convex calibration dimension of the Jaccard loss satisfies
2^(s−1) ≤ CCdim(L^Jac) ≤ 2^s − 1.
The lower bound is obtained from a factorially weighted distribution with 2^(s−1)+1 supported outcomes and Bayes-optimal reports, showing that every exactly calibrated convex surrogate needs exponentially many prediction coordinates.
- Polynomial approximate calibration: Two approximation results give explicit regret transfers:
- F1-to-Jaccard transfer: An existing (s^2 + 1)-dimensional F1 surrogate yields a polynomial-time rule with asymptotic Jaccard regret at most 3 − 2√2 ≈ 0.1716.
- MinHash square-loss surrogate: For any α > 0 and 0 < ρ < 1, it attains Jaccard regret floor α uniformly over arbitrary conditional label distributions. With probability at least 1 − ρ:
- Direct construction dimension: O((s^2 + s log(1/ρ))/α^2)
- Signed variant dimension: O((s + log(1/ρ))/α^2).
- Main takeaway: Zero-regret calibration for Jaccard requires exponential prediction dimension, while every fixed additive regret tolerance admits polynomial prediction dimension. This sharp separation between exact and approximate calibration parallels known results for other discrete losses.
Source
arXiv:2608.13549 — https://arxiv.org/abs/2608.13549
This page is an English static mirror generated for search and AI citation.
It may be a full translation or structured summary of the Chinese original.
Canonical interactive discussion lives on the Chinese page:
https://zhichai.net/topic/178633499