Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure

Author: Mingyuan Zhang (Independent Researcher)

arXiv: 2608.13549v1 [cs.LG] 13 Aug 2026

---

The paper studies the per-instance Jaccard score (intersection over union, IoU) in multi-label classification and binary segmentation. With s labels, the 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 Möbius 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 provides 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 + 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.

The paper addresses multi-label classification where outcomes and predictions are subsets of a ground set of s labels. The Jaccard score compares them by the size of their intersection divided by the size of their union, widely called intersection over union (IoU) in image segmentation. The dependence on the entire predicted and true sets makes the instance-wise loss nondecomposable across labels.

The output space contains 2 s sets, but an exponential output space alone does not determine the dimension required by a statistically consistent convex surrogate. Convex calibration dimension formalizes the smallest Euclidean dimension in which an exactly calibrated convex surrogate can exist (Ramaswamy and Agarwal, 2012, 2016).

The contributions are threefold:

1. Exact ranks: The paper determines the exact ranks of the Jaccard score, shifted-loss, and ordinary loss matrices, together with the affine dimension of the loss columns. Under the empty-set convention, all three matrix ranks equal 2 s, and the affine dimension is 2 s − 1.

2. Exponential bounds: The paper proves 2(s−1) ≤ CCdim(L Jac) ≤ 2 s − 1. For the lower bound, the author fixes one core label and assigns each outcome containing d optional labels weight proportional to 1/d!. A combinatorial identity makes all reports containing the core label tie, while adding the core label strictly improves every nonempty report that omits it. Hence the convex calibration dimension for exact calibration is Θ(2 s).

3. Polynomial-dimensional approximation guarantees: Two complementary approximation routes are given:

• Pointwise, Jac = F1/(2 − F1), but expectation does not commute with this nonlinear transformation. A regret transfer turns an F1 surrogate into a polynomial-time Jaccard rule with regret at most 3 − 2√2.

• A MinHash feature map uniformly approximates the entire Jaccard score matrix. Regressing the conditional feature mean with a convex square loss gives an α-approximately consistent surrogate.

Fix an integer s ≥ 1. Let [s] = 1,..., s, Y = 2[s], and N = Y = 2 s. Outcomes and reports are denoted by A, B ∈ Y. The Jaccard score is defined by:

Jac(A, B) = A ∩ B / A ∪ B, if A ∪ B ≠ ∅; Jac(∅, ∅) = 1.

Let S ∈ R(N×N) be the score matrix, S A,B = Jac(A, B), let U = 1 N 1 N T, and let L:= L Jac = U − S be the Jaccard loss matrix.

The conditional risk of report B is p T L·,B, and opt L(p) is the set of Bayes-optimal reports. The convex calibration dimension CCdim(L) is the smallest dimension d in which an exactly calibrated convex surrogate can exist.

Two general results are used:

• CCdim(L) ≤ affdim(L) (Theorem 12 of Ramaswamy and Agarwal, 2016)

• CCdim(L) ≥ ∥p∥0 − µ Q L B(p) − 1 (Theorem 16 of Ramaswamy and Agarwal, 2016)

The paper discusses:

• Jaccard matrices and MinHash: The collision probability underlying MinHash is the Jaccard similarity (Broder, 1997). Bouchard et al. (2013) proved strict positive definiteness of the complete nonempty Jaccard index matrix. The paper gives an alternative finite proof based on MinHash and Boolean Möbius inversion.

• Instance-wise Jaccard prediction: Dembczyński et al. (2012) studied decision-theoretic risk minimization. Chierichetti et al. (2010) established computational hardness of the Jaccard-median problem. Waegeman et al. (2014, Theorem 3) bound the Jaccard regret of an F1-optimal report by 1 − δ(P)/2.

• Convex surrogates for IoU: The Lovász hinge and Lovász–Softmax losses (Yu and Blaschko, 2015; Berman et al., 2018) are discussed. Finocchiaro et al. (2022) showed the Lovász hinge is inconsistent for its intended structured target unless the underlying set function is modular.

• Prediction dimension: Zhang (2026) proved that the F1 score has CCdim(L F1) = Θ(s2), whereas the Jaccard bounds proved here are exponential.

Lemma 4.1 (Strict positive definiteness): For every s ≥ 1, the matrix K (the score matrix restricted to nonempty sets) is positive definite. Consequently, rank(K) = 2 s − 1.

The proof writes K as a MinHash Gram matrix and uses Boolean Möbius inversion to show that the Gram features have no nontrivial common null vector.

Theorem 4.2 (Exact Jaccard ranks): For every s ≥ 1, under the convention in (1):

rank(S) = rank(L − U) = rank(L) = 2 s. Moreover, affdim(L) = 2 s − 1.

Corollary 4.3 (Calibration-dimension upper bound): For every s ≥ 1:

CCdim(L Jac) ≤ 2 s − 1.

Remark 4.4 (Alternative empty-set convention): If instead Jac(∅, ∅) = 0, then rank(S) = rank(L − U) = 2 s − 1, rank(L) = 2 s, affdim(L) = 2 s − 1.

Lemma 5.1 (Factorial balancing): For every C ⊆ [n]:

Σ D⊆[n] (1 + C ∩ D) / ((1 + C ∪ D) D!) = Σ d=0 n (n choose d) / (d + 1)!.

In particular, the left-hand side is independent of C.

Theorem 5.2 (Exponential CC-dimension bounds): For every s ≥ 1:

2(s−1) ≤ CCdim(L Jac) ≤ 2 s − 1. Consequently, CCdim(L Jac) = Θ(2 s).

The proof sketch: Fix a core label 1 and put O = [s] 1. Let U = 1 ∪ D: D ⊆ O. Define a full-support distribution q on U by assigning 1 ∪ D probability proportional to 1/D!. For a report 1 ∪ C, its expected score under q is the normalized left-hand side of (6); hence all 2(s−1) reports in U tie. Every nonempty report missing label 1 is pointwise improved by adding it. Mixing q with the empty outcome makes the empty report tie with every report in U. The support is A = ∅ ∪ U, A = 2(s−1) + 1. The active score submatrix indexed by A is nonsingular by Lemma 4.1. At the witness distribution, the difference span is the entire hyperplane orthogonal to the positive probability vector, leaving no nonzero two-sided feasible direction, so µ = 0. Substitution into (5) gives the lower bound.

Remark 5.3: The bounds in (7) differ by less than a factor of two. Determining the exact convex calibration dimension remains open.

Remark 5.4: Under Jac(∅, ∅) = 0, the same factorial witness without the empty-outcome mixture yields 2(s−1) − 1 ≤ CCdim(L Jac) ≤ 2 s − 1.

Define the instance-wise F1 score with the same empty-set convention:

F(A, B) = 2A ∩ B / (A + B), if A + B > 0; F(∅, ∅) = 1.

Pointwise, Jac(A, B) = g(F(A, B)), where g(t) = t/(2 − t).

Proposition 6.1 (F1-to-Jaccard regret transfer): Let c⋆ = 3 − 2√2 and define H: [0, 1] → [0, 1] by:

H(r) = c⋆ + r, for 0 ≤ r ≤ √2 − 1; H(r) = 2r/(1 + r), for √2 − 1 ≤ r ≤ 1.

Then, for every distribution D and every classifier h: X → Y:

Reg Jac(h) ≤ H(Reg F(h)) ≤ c⋆ + Reg F(h).

In particular, an F1-Bayes classifier has Jaccard regret at most c⋆ ≈ 0.1716.

The proof uses the fact that g is convex, Jensen's inequality, and a careful analysis of the function a(z) = z − g(z) = z(1 − z)/(2 − z), which increases on [0, z⋆] and decreases on [z⋆, 1], where z⋆ = 2 − √2 and a(z⋆) = c⋆.

This is a convention-matched refinement of Waegeman et al. (2014, Theorem 3). The paper notes: the proposition both sharpens the exact-optimizer guarantee and covers approximate F1 optimization; concavity of H supplies the population transfer used above.

Write a permutation of [s] as π = (π(1),..., π(s)). For every nonempty A ⊆ [s], its MinHash value is the first element of A in this order. Under the convention Jac(∅, ∅) = 1, a uniformly random permutation satisfies the MinHash identity for every A, B ∈ Y:

Jac(A, B) = Pr π(m π(A) = m π(B)).

Lemma 6.2 (Uniform finite-sample MinHash approximation): Let π1,..., π M be independent uniformly random permutations of [s], and define the feature map Φ(A) = (1/√M)(e m π1(A),..., e m π M(A)) ∈ R(M(s+1)). Then for every η > 0:

Pr(max A,B S̃(A, B) − Jac(A, B) > η) ≤ 2·4 s·exp(−2Mη2).

Consequently, for 0 < ρ < 1, the uniform error is at most η with probability at least 1 − ρ whenever M ≥ (2s log 2 + log(2/ρ)) / (2η2).

Theorem 6.3 (MinHash approximate consistency): On the uniform-approximation event, for every p ∈ Δ N and every u ∈ R(M(s+1)):

r Jac(p, pred M(u)) ≤ 2η + √(2·r Ψ M(p, u)).

The corresponding population guarantee is:

Reg Jac(pred M∘f) ≤ 2η + √(2·Reg Ψ M(f)).

In particular, for every α > 0, taking η = α/2 makes the pair α-approximately consistent. With probability at least 1 − ρ, this is achieved in dimension:

d MH = M(s + 1), where M = ⌈2(2s log 2 + log(2/ρ))/α2⌉,

and hence d MH = O((s2 + s log(1/ρ))/α2).

The proof uses the bias–variance identity for square loss: Σ A p A ∥u − Φ(A)∥22 = ∥u − µ p∥22 + Σ A p A ∥Φ(A) − µ p∥22, where µ p = Σ A p A Φ(A).

Corollary 6.4 (Rademacher-compressed approximate consistency): For every α > 0 and 0 < ρ < 1, take the random surrogate–link pair with d = d± = ⌈8(2s log 2 + log(2/ρ))/α2⌉. Then, with probability at least 1 − ρ over its feature construction, simultaneously for every distribution D and every measurable f:

Reg Jac(pred±∘f) ≤ α + √(2·Reg Ψ±(f)).

Thus the pair is α-approximately consistent in dimension O((s + log(1/ρ))/α2). Fixing ρ = 1/2 and any successful realization proves the deterministic existence of such a pair in dimension O(s/α2).

Remark 6.5 (Prediction dimension versus decoding): The MinHash construction has polynomial prediction dimension, but the exact link still maximizes over all 2 s reports. No polynomial-time decoding claim is implicit. If a decoder returns a report with error τ, the argument adds only τ to the regret bounds.

Remark 6.6 (Alternative empty-set convention): If Jac(∅, ∅) = 0, define a convention-matched F1 score with F(∅, ∅) = 0. Then (15) and Proposition 6.1 remain valid. For the MinHash construction, set Φ(∅) = 0 and use the ordinary nonempty-set features. All feature norms are then at most one, and the concentration and regret bounds remain unchanged.

The instance-wise multi-label Jaccard loss has maximal matrix rank and affine dimension. A finite MinHash Gram representation and Boolean Möbius inversion establish the rank results, while a factorially weighted family with a trivial two-sided feasible subspace yields 2(s−1) ≤ CCdim(L Jac) ≤ 2 s − 1. Thus exact calibration requires Θ(2 s) prediction coordinates, although the precise dimension remains open within a factor of two.

Approximation exposes an exactness–dimension tradeoff. The F1 transfer, combined with the polynomial-time decoder of Zhang et al. (2020), gives asymptotic Jaccard regret at most 3 − 2√2. For any α > 0, MinHash square-loss surrogates attain regret floor α in polynomial dimension; a signed variant achieves O((s + log(1/ρ))/α2) dimensions with probability at least 1 − ρ.

Natural next steps identified by the author include: efficient links with arbitrarily small floors, matching approximate-dimension lower bounds, and closing the factor-of-two gap in CCdim(L Jac).

multi-label classification · Jaccard loss · intersection over union · convex calibration dimension · loss-matrix rank · approximate consistency · MinHash random features · F-measure

Based on this paper, here are the specific improvements that can be made to AI systems:

• Improvement: AI systems can now know a priori that any convex surrogate for exact Jaccard/IoU optimization requires exponential (Θ(2 s)) prediction dimensions. This prevents wasted effort on polynomial-dimensional exact surrogates.

• What the improved system can do: Automatically reject or avoid designing convex surrogates for exact IoU optimization in multi-label settings with many labels, instead routing to approximate methods.

• Improvement: The MinHash random-feature construction provides an α-approximately consistent surrogate with dimension O((s + log(1/ρ))/α2) using signed features, or O((s2 + s log(1/ρ))/α2) with direct construction.

• What the improved system can do: For any user-specified regret tolerance α and confidence 1−ρ, automatically construct a convex surrogate with guaranteed regret ≤ α, using only polynomial prediction coordinates—even when the label space is exponentially large.

• Improvement: The explicit F1-to-Jaccard regret transfer (H(r) = c⋆ + r with c⋆ = 3 − 2√2 ≈ 0.1716) allows reuse of existing F1-optimized models.

• What the improved system can do: Take an existing F1-optimal classifier and immediately bound its Jaccard regret by 0.1716 without retraining. This enables cost-effective deployment of already-trained F1 systems for IoU-critical applications (e.g., medical image segmentation) with known worst-case performance.

• Improvement: The uniform finite-sample bound (error ≤ η with probability ≥ 1−ρ when M ≥ (2s log 2 + log(2/ρ))/(2η2)) gives explicit sample complexity.

• What the improved system can do: Given a label set size s, automatically compute the minimum number of random permutations M needed to achieve a desired approximation quality, then construct the feature map with guaranteed uniform approximation of the entire Jaccard matrix.

• Improvement: The signed variant reduces dimension from O(s2/α2) to O(s/α2) while preserving α-approximate consistency.

• What the improved system can do: For large-scale multi-label problems (e.g., s = 10,000 labels), reduce the prediction space from 108 to 104 dimensions while maintaining the same regret guarantee—enabling tractable training and inference.

• Improvement: The paper shows that if a decoder returns a report with error τ, the regret bound only increases additively by τ.

• What the improved system can do: Use approximate, polynomial-time decoders (rather than exact 2 s maximization) with explicit knowledge of the added regret. This enables practical deployment where exact decoding is computationally infeasible.

• Improvement: The paper provides explicit handling for both Jac(∅,∅)=1 and Jac(∅,∅)=0 conventions, with corresponding rank results and surrogate constructions.

• What the improved system can do: Automatically adapt its calibration guarantees and surrogate design based on the user's chosen empty-set convention, avoiding subtle inconsistencies that could invalidate regret bounds.

• Improvement: Knowing that CCdim ≥ 2(s−1) for exact calibration, systems can make informed trade-offs between prediction dimension and approximation tolerance.

• What the improved system can do: Given a computational budget, automatically determine whether exact calibration is feasible (if budget ≥ 2(s−1)) or whether to switch to an α-approximate surrogate with polynomial dimension, optimizing the achievable regret under resource constraints.