# Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure

arXiv: https://arxiv.org/abs/2608.13549 · HTML: https://mlsanity.com/paper/2608.13549/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 13 Aug 2026.

## Builds on (most cited first, 8 of 8)

- [Convex Calibration Dimension for Multiclass Loss Matrices](https://mlsanity.com/paper/1408.2764/) (2014)
- [Convex Calibrated Surrogates for the Multi-Label F-Measure](https://mlsanity.com/paper/2009.07801/) (2020)
- [On the Bayes-optimality of F-measure maximizers](https://mlsanity.com/paper/1310.4849/) (2013)
- [Sharp Analysis of Learning with Discrete Losses](https://mlsanity.com/paper/1810.06839/) (2018)
- [Calibrated Surrogate Maximization of Linear-fractional Utility in Binary Classification](https://mlsanity.com/paper/1905.12511/) (2019)
- [The Structured Abstain Problem and the Lov'asz Hinge](https://mlsanity.com/paper/2203.08645/) (2022)
- [RankSEG: A Consistent Ranking-based Framework for Segmentation](https://mlsanity.com/paper/2206.13086/) (2022)
- [Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss](https://mlsanity.com/paper/2608.08399/) (2026)

## Abstract (arXiv)

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 2s outcomes and reports. Under the convention 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 2s-1. The proof combines a finite MinHash Gram representation with Boolean M"obius inversion. For exact calibration, we prove 2s-1 ≤ CCdim(LJac) ≤ 2s-1. The lower bound uses a factorially weighted distribution with 2s-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 F1-to-Jaccard transfer turns an existing (s2+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 Jaccard-regret floor α uniformly over arbitrary conditional label distributions. With probability at least 1-ρ, the direct construction has dimension O((s2+slog(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.