PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure

Mingyuan Zhang

arXiv:2608.13549v1cs.LGstat.ML

TL;DR

The paper studies the dimension required to calibrate the nondecomposable multi-label Jaccard loss. It proves exponential dimension for exact calibration while establishing polynomial-dimensional approximations with explicit regret floors.

  • Problem

    The paper addresses how prediction dimension affects exact and approximate calibration of the nondecomposable, set-valued Jaccard loss in multi-label classification.

    Source: §1 · p. 1

  • Method

    It combines finite MinHash Gram representations, Boolean Möbius inversion, factorially weighted witness distributions, and regret-transfer constructions.

    Source: §1 · p. 2, §5 · p. 5

  • Results

    Exact calibration requires Θ(2^s) prediction coordinates, while signed MinHash surrogates achieve O((s + log(1/ρ))/α^2) dimensions with probability at least 1 −ρ for regret floor α.

    Source: §7 · p. 8

  • Takeaways & Limitations

    Zero-regret calibration is exponentially dimensional, whereas every fixed additive regret tolerance admits polynomial prediction dimension.

    Source: §7 · p. 8

    The exact convex calibration dimension remains open within a factor of two, and the approximate constructions do not resolve inference complexity.

    Source: §5 · p. 5, §6.2 · p. 8, §7 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

This section establishes that Jaccard/IoU’s nondecomposable multi-label structure requires exponentially large prediction dimension for exact convex calibration, while polynomial-dimensional surrogates achieve controlled additive regret. It also characterizes the underlying loss matrices and develops F1- and MinHash-based approximation routes.

Motivation

  • Jaccard/IoU compares predicted and true label subsets through intersection over union, making the instance-wise loss nondecomposable across labels.The output space has 2^s sets, but exponential outputs alone do not determine the dimension required by calibrated convex surrogates.Source: §1 · p. 1

Matrix structure

  • All three Jaccard-related matrices have rank 2^s, while the loss columns have affine dimension 2^s − 1.The proof uses a finite MinHash Gram representation and Boolean Möbius inversion, yielding an exactly calibrated surrogate in 2^s − 1 dimensions.Source: §1 · pp. 1–2

Approximation guarantees

  • An F1-to-Jaccard regret transfer converts a quadratic-dimensional calibrated F1 surrogate into a polynomial-time rule with asymptotic Jaccard regret at most 3 − 2√2.Although Jac = F1/(2 − F1) pointwise, expectation does not commute with this nonlinear transformation, so F1- and Jaccard-optimal reports can differ.Source: §1 · p. 2
  • For α > 0 and 0 < ρ < 1, MinHash square-loss surrogates achieve asymptotic Jaccard regret at most α with probability at least 1 − ρ.The direct construction has dimension O((s^2 + s log(1/ρ))/α^2), while signed MinHash has dimension O((s + log(1/ρ))/α^2).Source: §1 · p. 2

2 Setup and calibration background

This section formalizes multi-label Jaccard scoring through finite outcome and report spaces, associated score and loss matrices, and affine-dimension notation. It also defines convex calibration dimension and introduces general results from Ramaswamy and Agarwal (2016).

Notation

  • The setup uses s labels, outcome/report space Y = 2^[s], and N = 2^s possible outcomes and reports.Outcomes and reports are denoted A, B ∈ Y.Source: §2 · p. 2

Jaccard score and loss

  • The Jaccard score matrix S has entries S_A,B = Jac(A, B), while the loss matrix satisfies L − U = −S.Here U is the all-ones matrix.Source: §2 · p. 2

Linear-algebra notation

  • The section defines restrictions, submatrices, matrix columns, and column-affine dimension for analyzing finite families of vectors.For M = [m_1 · · · m_k], affdim(M) is the affine dimension of its columns.Source: §2 · p. 2

Bayes risk

  • For p ∈ Δ_N, conditional risk is p^T L_·,B, with Bayes-optimal reports and their trigger probability set defined from these risks.The support is supp(p) = {A ∈ Y : p_A > 0}.Source: §2 · p. 2

Calibration background

  • Convex calibration uses a convex domain, convex coordinate functions, and a link pred to reports; CCdim(L) is the smallest prediction dimension achieving calibration (Ramaswamy and Agarwal, 2016).The cited work supplies the referenced general results and definitions.Source: §2 · p. 3

3 Related work

Prior work established MinHash–Jaccard connections, computational difficulty of instance-wise Jaccard prediction, and tractable IoU-motivated surrogates. This paper provides a finite MinHash–Möbius proof and places its exponential Jaccard prediction-dimension bounds against quadratic F1 results and existing calibration theory.

Jaccard matrices and MinHash

  • The paper replaces an infinite positive-semidefinite decomposition of the complete nonempty Jaccard matrix with a finite MinHash and Boolean Möbius inversion proof, then analyzes the associated loss matrix.The MinHash collision probability equals Jaccard similarity, while strict positive definiteness was previously shown by Bouchard et al. (2013), following Gower (1971).Source: §3 · p. 3

Instance-wise Jaccard prediction

  • Instance-wise Jaccard-risk minimization is difficult: empirical Bayes prediction is the computationally hard Jaccard-median problem, for which approximation algorithms are known.Dembczy´nski et al. (2012) studied decision-theoretic risk minimization for multi-label losses and highlighted the difficulty of exact Jaccard-risk minimization from arbitrary conditional joint distributions.Source: §3 · p. 3
  • The analyzed loss is instance-wise, averaging outcome–report losses under a conditional distribution, unlike population-confusion or expected-utility formulations that support threshold and calibrated-utility methods (Bao and Sugiyama, 2020).This distinction concerns micro- and instance-averaged linear-fractional metrics rather than the finite instance-wise loss studied here.Source: §3 · p. 3

Convex surrogates for IoU

  • Lovász hinge and Lovász–Softmax offer tractable IoU-motivated objectives, but empirical usefulness does not establish calibration, and the Lovász hinge is inconsistent unless the target set function is modular.These objectives are motivated by submodular losses and IoU and have been influential in segmentation.Source: §3 · p. 3

Prediction dimension

  • Unlike the quadratic F1 convex calibration dimension, the paper establishes exponential Jaccard prediction-dimension bounds and reports no prior exponential lower bound for instance-wise Jaccard loss.Convex calibration dimension was introduced by Ramaswamy and Agarwal (2012) and developed via trigger-set geometry by Ramaswamy and Agarwal (2016); Zhang (2026) proved CCdim(LF1) = Θ(s2) under the aligned empty-set convention. The Jaccard lower bound uses a Jaccard-specific family of tied Bayes reports and the feasible-subspace theorem, while exact calibration dimension does not itself lower-bound dimension for a fixed additive target-regret tolerance.Source: §3 · pp. 3–4

4 Exact rank and affine dimension

Under Jac(∅,∅)=1, the Jaccard score, shifted-loss, and ordinary loss matrices have exact ranks, while the loss columns have affine dimension 2^s−1. The proof combines a MinHash Gram representation with Boolean Möbius inversion and yields a 2^s−1 calibration-dimension upper bound.

Exact ranks and affine dimension

  • The nonempty-set score block K is strictly positive definite, so rank(K) = 2^s−1.The proof represents K as a MinHash Gram matrix and uses Boolean Möbius inversion to exclude nontrivial common null vectors.Source: §4 · p. 4
  • The loss matrix L is nonsingular because its block kernel equations force every null vector to vanish.The score columns are linearly independent, and the invertible affine map x → 1_N − x transfers their affine dimension to the loss columns.Source: §4 · p. 4

Calibration-dimension upper bound

  • Theorem 4.2 implies the calibration-dimension upper bound CCdim(L^Jac) ≤ 2^s−1.Equivalently, an arbitrary 2^s-class conditional distribution can be estimated in 2^s−1 coordinates and decoded by minimizing estimated Jaccard risk.Source: §4 · p. 4

Exact ranks and affine dimension

  • rank(S) = rank(L − U) = 2^s−1, rank(L) = 2^s, and affdim(L) = 2^s−1 under the stated empty-set convention.The score matrix is block diagonal with the empty-set entry 1 and the positive-definite nonempty-set block K; the affine dimension transfers from score to loss columns.Source: §4 · p. 4

5 An exponential calibration-dimension lower bound

The Jaccard loss has exponential convex calibration dimension: 2^(s-1) ≤ CCdim(L^Jac) ≤ 2^s−1, hence CCdim(L^Jac) = Θ(2^s). The lower bound follows from a factorially balanced witness distribution whose Bayes-optimal reports span an exponentially large affine space, ruling out uniformly exact polynomial-dimensional convex surrogates.

Lower-bound witness

  • A factorially weighted distribution makes 2^(s−1)+1 reports Bayes-optimal by balancing every report containing a fixed core label.Mixing this distribution with the empty outcome makes the empty report tie with all reports in the witness set.Source: §5 · pp. 4–5

Lower-bound proof

  • The active score submatrix is nonsingular, so the optimal columns have affine dimension 2^(s−1), yielding the exponential lower bound.At the witness distribution, their difference span fills the hyperplane orthogonal to the positive probability vector, leaving no nonzero feasible direction.Source: §5 · p. 5

Implication and gap

  • The result rules out every polynomial-dimensional convex surrogate that is exactly calibrated uniformly over all conditional label distributions.The exactness qualifier matters because later approximation guarantees avoid this exponential requirement.Source: §5 · p. 5

Alternative convention

  • Changing the convention to Jac(∅,∅) = 0 leaves the exponential conclusion unchanged.The same factorial witness works without mixing in the empty outcome.Source: §5 · p. 5

6 Polynomial-dimensional approximate surrogates

Allowing a nonzero distribution-free regret floor yields polynomial-dimensional approximate Jaccard surrogates. An F1 transfer gives a constant-floor guarantee, while MinHash constructions achieve arbitrary fixed floors with explicit dimension bounds.

F1-to-Jaccard transfer

  • An (s^2 + 1)-dimensional F1 surrogate and polynomial-time link become c⋆-approximately consistent for Jaccard, where c⋆ = 3 − 2√2 ≈ 0.1716.The transfer applies to every distribution and sequence of predictions, but retains a nonzero worst-case floor because F1- and Jaccard-optimal reports may differ.Source: §6.1 · p. 6

MinHash construction

  • The MinHash identity under Jac(∅, ∅) = 1 enables uniform finite-sample approximation and the resulting convex square-loss consistency guarantees.Uniform random permutations provide the identity, while the approximation event supports the conditional and population regret bounds.Source: §6.2 · pp. 6–7
  • The signed MinHash variant achieves the same α-approximate consistency in dimension O((s + log(1/ρ))/α^2), with deterministic existence in O(s/α^2).The result holds with probability at least 1 −ρ over feature construction, and fixing ρ = 1/2 yields the deterministic bound.Source: §6.2 · p. 8

Decoding and approximation

  • Polynomial prediction dimension does not imply polynomial-time decoding: the exact MinHash link maximizes over all 2^s reports, whereas the F1 proxy has polynomial-time decoding but a constant regret floor.Approximate decoding adds τ to the regret bounds, requiring kernel and decoding budgets satisfying 2η + τ ≤ α for overall floor α.Source: §6.2 · p. 8

7 Conclusion

The conclusion establishes an exponential prediction-dimension requirement for exactly calibrated multi-label Jaccard surrogates, while approximation enables polynomial dimension at a nonzero regret floor. The precise calibration dimension and efficient inference remain open.

Exact calibration

  • Exact Jaccard calibration requires Θ(2^s) prediction coordinates, with the precise dimension still unresolved within a factor of two.Maximal matrix rank and affine dimension follow from a finite MinHash Gram representation and Boolean Möbius inversion.Source: §7 · p. 8

Approximation

  • The F1 transfer with Zhang et al. (2020)'s polynomial-time decoder achieves asymptotic Jaccard regret at most 3 − 2√2.Source: §7 · p. 8
  • For any α > 0, signed MinHash square-loss surrogates achieve regret floor α in O((s + log(1/ρ))/α^2) dimensions with probability at least 1 − ρ.The MinHash link may still search over 2^s reports, so polynomial prediction dimension does not resolve inference complexity.Source: §7 · p. 8

A Proofs for the exact-rank results · A.1 Proof of Lemma 4.1

The proof establishes strict positive definiteness of the nonempty-set Jaccard kernel by combining a MinHash Gram representation with Boolean Möbius inversion. MinHash agreement yields a sum-of-squares quadratic form, whose zero case forces every coefficient to vanish.

A.1 Proof of Lemma 4.1

  • The MinHash identity represents Jaccard similarity as the probability that uniformly permuted minima of two nonempty sets agree.The first element of the union is uniformly distributed, and the minima agree exactly when it belongs to the intersection.Source: §A.1 · p. 9
  • For each permutation and index, the proof constructs column vectors whose pairwise products encode MinHash agreement.Summing over the index produces the indicator that the two MinHashes agree.Source: §A.1 · p. 9
  • This construction gives the kernel a Gram representation and therefore establishes K ⪰ 0.The representation expresses the quadratic form through a finite sum of nonnegative squares.Source: §A.1 · p. 9
  • If x⊤Kx = 0, every square in the finite sum must vanish, so each vector inner product h⊤π,jx equals zero.The argument reduces the nullspace question to constraints indexed by permutations and elements.Source: §A.1 · p. 9
  • Consequently, the kernel has trivial nullspace and is strictly positive definite: K ≻ 0.The proof combines the MinHash sum-of-squares representation with the inversion argument to obtain strictness.Source: §A.1 · p. 9
  • A carefully chosen permutation makes the sets whose first element is j exactly the sets {j} ∪ R with R ⊆ T.For fixed j and T, elements outside T ∪ {j} precede j, while elements of T follow it.Source: §A.1 · p. 9
  • Boolean Möbius inversion then forces x_{ {j} ∪ T } = 0 for every T.Because every nonempty set contains some j, all coordinates of x vanish.Source: §A.1 · p. 9

A.2 Proof of Theorem 4.2 · B Proof of the factorial balancing identity

Theorem 4.2 is proved by establishing full rank for the score and loss matrices, then transferring affine independence through an invertible affine map. The factorial balancing identity follows by decomposing subsets, regrouping factorial terms, and applying Vandermonde’s identity.

A.2 Proof of Theorem 4.2

  • The score matrix S is nonsingular, so rank(S) = rank(L − U) = N.Source: §A.2 · p. 9
  • The loss matrix L is also full rank, with rank(L) = N, after reducing its block-form nullspace equations using the invertibility of K.Source: §A.2 · p. 10
  • The N score columns are linearly and affinely independent, giving affdim(S) = N − 1.Source: §A.2 · p. 10
  • Applying the invertible affine map z 7→ 1_N − z to score columns preserves independence and yields affdim(L) = N − 1.Source: §A.2 · p. 10

B Proof of the factorial balancing identity

C Proof of the exponential lower bound … D.2 Proof of Lemma 6.2

The proofs construct a factorially weighted distribution forcing 2^(s−1)+1 active Bayes-optimal reports, establish the F1-to-Jaccard regret transfer, and derive MinHash concentration by Hoeffding’s inequality and a union bound.

C Proof of the exponential lower bound

  • The factorial distribution yields 2^(s−1)+1 supported outcomes whose reports are exactly Bayes-optimal, while every other report is strictly suboptimal.The construction first ties the reports in U, then adjusts the empty-outcome mass to tie the empty report as well.Source: C Proof of the exponential lower bound · pp. 11–12
  • Two-sided feasible perturbations at the constructed distribution force zero motion outside the support, preserve normalization, and maintain every active comparison equality.Strict inactive risk gaps remain strict for sufficiently small perturbations, characterizing the local feasible subspace.Source: C Proof of the exponential lower bound · p. 12
  • The active constraints eliminate the lineality space, completing the lower-bound argument when combined with the active-support cardinality.The orthogonality condition makes the active perturbation proportional to p_A, while normalization forces the scalar to vanish.Source: C Proof of the exponential lower bound · p. 12

D Proofs for the polynomial-dimensional approximation results

  • The conditional transfer analyzes the function a: its maximum is c⋆ when the feasible interval contains z⋆, otherwise it occurs at the endpoint.This yields the piecewise bound used to control Jaccard regret from F1 regret.Source: §D.1 · p. 13

D.1 Proof of Proposition 6.1

  • The F1-to-Jaccard proof bounds conditional regret through a concave envelope H, then lifts the result to population regret using Jensen’s inequality.For an F1-Bayes classifier, the resulting Jaccard regret is at most H(0)=c⋆.Source: §D.1 · p. 13

D.2 Proof of Lemma 6.2

  • For each outcome–report pair, MinHash summands are independent Bernoulli variables with mean Jac(A,B); Hoeffding’s inequality and a union bound establish the uniform concentration guarantee.There are 4^s ordered pairs, and solving the resulting bound for M gives the required sample size.Source: §D.2 · p. 13

D.3 Proof of Theorem 6.3 · D.4 Proof of Corollary 6.4 · E The alternative empty-set convention

The proofs establish the MinHash square-loss regret guarantees through uniform kernel approximation and square-loss geometry, then extend them to signed features. Under Jac(∅,∅)=0, nonsingularity and calibration dimensions change in specific ways.

D.3 Proof of Theorem 6.3

  • Uniform MinHash approximation, score maximization, and Cauchy–Schwarz convert approximation error into a conditional Jaccard-regret bound.The proof identifies the relevant feature-map distance with square-loss regret via the bias–variance identity and the minimizer u = µp.Source: §D.3 · pp. 14–15
  • Applying the conditional inequality pointwise and averaging yields the population regret guarantee and approximate consistency when surrogate regret vanishes.The consistency step sets η = α/2 and uses the population bound.Source: §D.3 · p. 15
  • The resulting feature dimension follows by ceiling the sample bound and multiplying by the block size s + 1, with one fixed feature realization satisfying the guarantees.The uniform-approximation event has positive probability, so at least one realization meets all bounds.Source: §D.3 · p. 15

D.4 Proof of Corollary 6.4

  • Signed MinHash features remain unbiased for the Jaccard kernel, and Hoeffding’s inequality with a union bound supplies the required uniform approximation.The signed feature-map distance is bounded by 2, so the preceding proof applies with η = α/2.Source: §D.4 · p. 15

E The alternative empty-set convention

  • With Jac(∅,∅)=0, the score matrix has rank N − 1, while the loss matrix remains full rank N.The empty score column is zero, the remaining score columns are independent, and the loss rank follows from the displayed block equations.Source: E The alternative empty-set convention · p. 15
  • Under the alternative convention, the loss affine dimension is N − 1 and the calibration lower bound becomes 2^s−1 −1, while the upper bound remains 2^s −1.The lower bound uses the factorial distribution without the empty outcome, whose support and exact Bayes-optimal report set both have size 2^s−1.Source: E The alternative empty-set convention · p. 15
Loading 2608.13549v1…