做多标签分类调Jaccard的同学看看：精确校准要指数维度，但固定误差容忍度有多项式解法，MinHash思路挺巧。
该论文研究多标签分类中逐样本Jaccard分数（IoU）的校准维度。作者证明Jaccard损失、平移损失和普通损失矩阵均非奇异，损失列仿射维度为2^s−1。精确校准的凸校准维度满足2^{s−1} ≤ CCdim ≤ 2^s−1，因此任何精确校准的凸代理都需要指数多个预测坐标。针对固定误差容忍度，论文给出多项式维度近似：F1到Jaccard的转移在维度s^2+1下达到至多3−2√2的渐近遗憾；MinHash平方损失代理在维度O((s^2+s log(1/ρ))/α^2)下达到遗憾上界α。
Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure
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.