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 asks how much prediction dimension is needed for calibrated convex surrogates for the nondecomposable multi-label Jaccard loss. It combines MinHash Gram representations, Boolean Möbius inversion, and calibration-dimension analysis to show that exact calibration requires exponentially many coordinates, while fixed-regret approximation admits polynomial dimension.

  • Problem

    Because Jaccard loss depends on entire predicted and true label sets, the paper studies calibration for this nondecomposable measure in the conditional decision-theoretic setting.

  • Method

    The paper combines finite MinHash Gram representations and Boolean Möbius inversion with factorially weighted witness distributions to analyze ranks and convex calibration dimension.

  • Results

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

  • Takeaways & Limitations

    Zero-regret calibration requires exponential prediction dimension, whereas every fixed additive regret tolerance admits polynomial prediction dimension.

  • Takeaways & Limitations

    The exact convex calibration dimension remains open within a factor of two, and the MinHash link may still search over 2^s reports.

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

The section establishes that multi-label Jaccard/IoU has exponential exact-calibration dimension despite its exponential output space, while fixed-regret approximation is achievable with polynomial prediction dimension. It proves full matrix rank and affine dimension results, then develops F1-based and MinHash-based approximation guarantees.

  • Exact structure: 2^s matrix rank and 2^s−1 affine dimension characterize the Jaccard score, shifted-loss, and ordinary loss matrices under the empty-set convention.The proof uses a finite MinHash Gram representation and Boolean Möbius inversion; the affine-dimension bound yields an exactly calibrated surrogate in 2^s−1 dimensions.
  • Exact calibration: 2^(s−1) ≤ CCdim(L^Jac) ≤ 2^s−1 gives exponential lower and upper bounds for exact calibration.The lower bound uses factorially weighted outcomes, tied Bayes-optimal reports, and a nonsingular principal score submatrix.
  • Polynomial approximation: O((s^2+s log(1/ρ))/α^2) is the direct MinHash construction’s prediction dimension for Jaccard-regret floor α with probability at least 1−ρ.Uniform MinHash approximation of the Jaccard score matrix combined with conditional feature-mean regression yields asymptotic Jaccard regret at most α.
  • Polynomial approximation: O((s+log(1/ρ))/α^2) is the signed MinHash variant’s prediction dimension under the same α and ρ conditions.This guarantee applies for every α > 0 and 0 < ρ < 1, with probability at least 1−ρ.

2 Setup and calibration background

This section establishes the multi-label Jaccard setup over 2^s outcomes and reports, defines the associated score and loss matrices, and introduces calibration terminology. It also specifies notation for supports, Bayes-optimal reports, affine dimensions, and convex calibration dimension.

  • Problem setup: The framework fixes s labels, yielding Y = 2^[s] with N = 2^s outcomes, while outcomes and reports are subsets A, B ∈ Y.The setup uses point masses, simplex distributions, and all-ones vectors indexed by the outcome space.
  • Problem setup: The Jaccard score matrix is S with entries S_A,B = Jac(A, B), and the Jaccard loss matrix satisfies L − U = −S.Here U is the all-ones matrix.
  • Notation: Affine dimension is defined for finite vector families and for matrix columns, while restrictions and submatrices provide notation for indexed vectors and matrices.For M = [m_1 · · · m_k], affdim(M) = affdim{m_1, . . . , m_k}.
  • Calibration background: For a distribution p, the conditional risk of report B is p^⊤L_·,B, with support supp(p) = {A ∈ Y : p_A > 0}.The section also introduces Bayes-optimal reports and their trigger probability set.
  • Calibration background: Convex calibration uses a convex domain, a surrogate ψ with convex coordinate functions, and a link pred, with CCdim(L) defined as the smallest prediction dimension supporting calibration.The section attributes this definition to Ramaswamy and Agarwal (2016).

3 Related work

The section situates the paper’s finite MinHash and Boolean Möbius proof within prior Jaccard-matrix, instance-wise prediction, surrogate-loss, and convex-calibration research. It distinguishes the studied instance-wise loss from population formulations and emphasizes the novelty of an exponential exact prediction-dimension lower bound.

  • Jaccard matrices and MinHash: Prior work linked MinHash collision probability to Jaccard similarity and established strict positive definiteness of the complete nonempty Jaccard index matrix.The paper instead gives a finite proof using MinHash and Boolean Möbius inversion.
  • Instance-wise Jaccard prediction: Jaccard-risk minimization from arbitrary conditional joint distributions is difficult, while empirical Bayes-optimal prediction is the computationally hard Jaccard-median problem.Prior work also provided approximation algorithms for the empirical problem.
  • Instance-wise Jaccard prediction: The studied loss averages outcome–report evaluations under a conditional distribution, unlike population-confusion or expected-utility formulations of micro- and instance-averaged linear-fractional metrics.Those alternative formulations admit threshold and calibrated-utility methods.
  • Convex surrogates for IoU: Lovász hinge and Lovász–Softmax offer tractable IoU-motivated objectives, but empirical usefulness does not establish calibration for the finite instance-wise loss.The Lovász hinge is inconsistent for its intended structured target unless the underlying set function is modular.
  • Prediction dimension: Convex calibration dimension was developed through trigger-set geometry; exact F1 prediction dimension is quadratic, whereas the paper’s Jaccard bounds are exponential.The paper applies a Jaccard-specific tied-Bayes-report family and reports no previous exponential lower bound for instance-wise Jaccard loss.

4 Exact rank and affine dimension

The Jaccard score, shifted-loss, and ordinary loss matrices are nonsingular, with score and loss columns both having affine dimension 2^s−1. These exact-rank results yield a calibration-dimension upper bound of 2^s−1 under the empty-set score convention Jac(∅,∅)=1.

  • Exact ranks: 2^s−1: The nonempty-set Jaccard score submatrix is positive definite and has rank 2^s−1.The proof represents it as a finite MinHash Gram matrix and applies Boolean Möbius inversion.
  • Exact ranks: 2^s: The full score matrix S and shifted-loss matrix L−U are nonsingular, while the ordinary loss matrix L is also nonsingular.Ordering the empty set first gives S = diag(1,K), and the loss kernel equations force every null vector to vanish.
  • Affine dimension: 2^s−1: The 2^s score columns and loss columns each have affine dimension 2^s−1.The score columns are linearly independent, and the invertible affine map x ↦ 1_N−x transfers the dimension to loss columns.
  • Calibration dimension: 2^s−1: The exact Jaccard calibration dimension is upper-bounded by 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.

5 An exponential calibration-dimension lower bound

The section proves that exact convex calibration for the multi-label Jaccard loss requires exponentially many prediction coordinates. A factorially weighted witness yields the lower bound, while the bounds remain within a factor of two and exclude polynomial-dimensional exactly calibrated surrogates.

  • Lower-bound witness: 2^{s−1}+1 Bayes-optimal reports are created by mixing a factorially weighted distribution with the empty outcome.Reports containing a fixed core label tie under the factorial distribution; the empty report is then made to tie through the mixture.
  • Theorem 5.2: 2^{s-1} ≤ CCdim(L^Jac) ≤ 2^s−1 for every s ≥ 1, so CCdim(L^Jac) = Θ(2^s).The lower bound comes from the factorial witness, and the upper bound follows from Corollary 4.3.
  • Lower-bound witness: 2^s−1 is the affine dimension of the active loss columns at the witness distribution, establishing the exponential lower bound.The active score submatrix is nonsingular, and the feasible-subspace argument leaves no nonzero two-sided feasible direction.
  • Gap and implication: Less than a factor of two separates the bounds, but the exact convex calibration dimension and improved constants remain open.The result rules out every polynomial-dimensional convex surrogate that is exactly calibrated uniformly over all conditional label distributions.
  • Alternative convention: 0 for Jac(∅,∅) leaves the exponential conclusion unchanged under the alternative empty-set convention.The same factorial witness applies without mixing in the empty outcome.

6 Polynomial-dimensional approximate surrogates

The section replaces exact-calibration requirements with a nonzero, distribution-free Jaccard-regret floor and develops polynomial-dimensional approximate surrogates. It transfers guarantees from an F1 surrogate and constructs direct and signed MinHash square-loss surrogates, while noting decoding and zero-floor limitations.

  • Approximate consistency: The approach combines a prior F1 surrogate and regret transfer with a new polynomial-dimensional MinHash surrogate for approximate Jaccard consistency.The guarantees target a nonzero, distribution-free regret floor rather than exact calibration.
  • F1-to-Jaccard transfer: 3 − 2√2 ≈ 0.1716 is the Jaccard-regret guarantee for an F1-Bayes classifier under the refined F1-to-Jaccard transfer.The transfer also applies to approximate F1 optimization, but F1- and Jaccard-optimal reports need not coincide.
  • MinHash construction: O((s^2+s log(1/ρ))/α^2) prediction dimension suffices for the direct MinHash construction to achieve α-approximate consistency with probability at least 1 − ρ.The construction uses finite-sample uniform MinHash approximation and admits a fixed deterministic feature map with the same guarantee.
  • MinHash construction: O((s+log(1/ρ))/α^2) dimension suffices for the Rademacher-compressed MinHash surrogate with probability at least 1 − ρ.Fixing ρ = 1/2 yields a deterministic pair of dimension O(s/α^2).
  • Limitations: For fixed α > 0, MinHash prediction dimension is polynomial, but exact decoding may still maximize over all 2^s reports and incurs no implicit polynomial-time decoding guarantee.The zero-floor lower bound is not contradicted because the displayed dimensions grow as α approaches zero.

7 Conclusion

The conclusion establishes that exact Jaccard calibration requires exponentially many prediction coordinates, while approximation achieves polynomial dimension at nonzero regret. The precise calibration dimension and efficient low-floor inference remain open.

  • Exact calibration: Exact calibration requires Θ(2^s) prediction coordinates, with the precise CCdim(L^Jac) remaining open within a factor of two.Maximal rank and affine dimension follow from a finite MinHash Gram representation and Boolean Möbius inversion.
  • Approximation: 3 − 2sqrt(2) is the asymptotic Jaccard-regret bound obtained by transferring an F1 surrogate through Zhang et al.’s polynomial-time decoder.This establishes a polynomial-dimensional approximation guarantee rather than exact calibration.
  • Approximation: O((s + log(1/ρ))/α^2) dimensions suffice for the signed MinHash square-loss surrogate to attain regret floor α with probability at least 1 − ρ.The guarantee holds for any α > 0 and 0 < ρ < 1.
  • Open problems: MinHash approximation does not resolve inference complexity because its link may still search over 2^s reports.Proposed next steps include efficient links with arbitrarily small floors, matching approximate-dimension lower bounds, and closing the CCdim factor-of-two gap.

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 matrix through a finite MinHash Gram representation and Boolean Möbius inversion. It shows that a zero quadratic form forces every coordinate to vanish.

  • A.1 Proof of Lemma 4.1: The proof starts from the MinHash identity for nonempty sets, relating Jaccard similarity to agreement of permutation-based minima.The first element of the union is uniform, and the minima agree exactly when it lies in the intersection.
  • A.1 Proof of Lemma 4.1: For each permutation and index, the proof defines column vectors whose pairwise products encode MinHash agreement.These vectors are indexed by pairs of nonempty sets through the associated construction.
  • A.1 Proof of Lemma 4.1: The resulting finite sum of outer products gives a Gram representation of the matrix K, implying K is positive semidefinite.The Gram representation follows because the sum over indices records whether the two MinHashes agree.
  • A.1 Proof of Lemma 4.1: If x⊤Kx = 0, every nonnegative square in the finite Gram sum must equal zero.Thus, the inner product of x with every constructed vector hπ,j vanishes.
  • A.1 Proof of Lemma 4.1: A tailored permutation places j between the elements outside T and those in T, identifying exactly the sets whose first element is j.For T ⊆ [s] \ {j}, these sets are {j} ∪ R with R ⊆ T.
  • A.1 Proof of Lemma 4.1: Boolean Möbius inversion then forces x_{\{j\}∪T} = 0 for every T.This applies to every j and T ⊆ [s] \ {j}.
  • A.1 Proof of Lemma 4.1: Because every nonempty set contains some j, all coordinates of x vanish, proving K ≻ 0.The nullspace is therefore trivial, upgrading positive semidefiniteness to positive definiteness.

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

The proof establishes nonsingularity and full affine dimension for the Jaccard loss matrix by exploiting score-column independence and an invertible affine transformation. It also proves the factorial balancing identity through subset decomposition, factorial-sum manipulation, and Vandermonde’s identity.

  • A.2 Proof of Theorem 4.2: rank(S) = rank(L − U) = N follows from Lemma 4.1, which makes S nonsingular.This establishes the required full rank for the shifted-loss matrix.
  • A.2 Proof of Theorem 4.2: The N score columns are linearly independent and therefore affinely independent, giving affdim(S) = N − 1.The proof orders the empty set first and uses its zero score with every nonempty set.
  • A.2 Proof of Theorem 4.2: Applying z 7→ 1_N − z to each score column preserves the corresponding affine structure and yields affdim(L) = N − 1.The map is invertible and sends score columns to loss columns.
  • B Proof of the factorial balancing identity: Every D ⊆ [n] is uniquely decomposed as D = I ⊔ E, with I = D ∩ C and E = D \ C.This decomposition separates contributions inside and outside C.
  • B Proof of the factorial balancing identity: Writing |C ∩ D| = i, |C ∪ D| = c + j, and |D| = i + j reduces the identity to sums indexed by i and j.For fixed i and j, the proof counts the corresponding choices for E.
  • B Proof of the factorial balancing identity: Factoring terms independent of i produces the factorial sum in equation (38), whose claim is verified after multiplication by c + j + 1.The verification uses c + j + 1 = (j + r + 1) + (c − r), then combines the resulting sums.
  • B Proof of the factorial balancing identity: Setting d = j + r makes the denominator (d + 1)!, while Vandermonde’s identity sums the binomial coefficients over admissible pairs.The new index ranges from 0 to n, and the resulting double sum equals the right-hand side of (6).

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

The lower-bound proof constructs a factorially weighted distribution whose Bayes-optimal reports include 2^(s−1)+1 outcomes, then establishes the required active-column independence. The approximation proofs derive a population Jaccard-regret transfer from F1 regret and a uniform MinHash concentration bound via Hoeffding’s inequality and a union bound.

  • C Proof of the exponential lower bound: A factorially weighted distribution is fixed around a core label, with the remaining labels forming the support construction.The proof sets the core label to 1, defines O = [s] \ {1}, and uses n = s − 1.
  • C Proof of the exponential lower bound: All reports in the constructed support tie under the factorial distribution, while reports outside it are strictly suboptimal.The empty report has score zero before it is tied separately, and nonempty reports omitting the core label have a strict score disadvantage.
  • C Proof of the exponential lower bound: After mixing in the empty outcome, the Bayes-optimal reports are exactly the empty report and the support U, totaling 2^(s−1)+1 outcomes.The constructed distribution gives the empty report and every report in U equal expected score, while all remaining reports score strictly lower.
  • C Proof of the exponential lower bound: The active score submatrix is nonsingular, so its |A| columns are linearly independent and have affine dimension |A| − 1.The lower-right block is a principal submatrix of a positive-definite matrix, which establishes nonsingularity.
  • C Proof of the exponential lower bound: The feasible two-sided perturbations are characterized by zero motion outside A, preserved normalization, and equality of all active comparisons.Strict inactive risk gaps remain strict under sufficiently small perturbations, while active equalities are preserved.
  • D.1 Proof of Proposition 6.1: The F1-to-Jaccard transfer is obtained by bounding conditional regret through a concave population-level function H and applying Jensen’s inequality.The conditional law pX and classifier h are substituted into the conditional inequality before Jensen’s inequality yields the population bound.
  • D.1 Proof of Proposition 6.1: For an F1-Bayes classifier, the population Jaccard regret is at most c⋆.The proof derives RegJac(h) ≤ H(0) = c⋆ from the conditional-to-population regret transfer.
  • D.2 Proof of Lemma 6.2: Hoeffding’s inequality controls each MinHash outcome–report pair, and a union bound over 4^s ordered pairs yields the concentration guarantee.The proof counts |Y|^2 = 4^s ordered pairs and solves the resulting bound for M.

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

Theorem 6.3 derives Jaccard-regret guarantees from uniform MinHash approximation and square-loss regret, establishing approximate consistency and a fixed feature-map realization with the stated dimension order. Corollary 6.4 extends the argument to signed features, while the alternative empty-set convention preserves full loss rank and yields a 2^s−1 calibration lower bound.

  • D.3 Proof of Theorem 6.3: D.3 Proof of Theorem 6.3: Uniform MinHash approximation converts score differences into feature-space distances, using Cauchy–Schwarz after selecting a Bayes-optimal report.The prediction b_B maximizes the feature inner product, and each block is a scaled standard basis vector.
  • D.3 Proof of Theorem 6.3: D.3 Proof of Theorem 6.3: Nonnegative feature coordinates imply the pairwise feature distance is bounded by 2.The bound follows from the norm expansion and nonnegative inner products.
  • D.3 Proof of Theorem 6.3: D.3 Proof of Theorem 6.3: The square-loss bias–variance identity shows conditional surrogate risk is minimized at u = µ_p, identifying the relevant distance with square-loss regret.The cross term vanishes after averaging, and the remaining term is independent of u.
  • D.3 Proof of Theorem 6.3: D.3 Proof of Theorem 6.3: Setting η = α/2 turns vanishing surrogate regret into approximate consistency and yields the theorem’s feature-dimension order.The proof takes a ceiling, multiplies by block size s + 1, and uses the positive-probability approximation event to fix one realization.
  • D.4 Proof of Corollary 6.4: D.4 Proof of Corollary 6.4: Signed MinHash features have expected inner product Jac(A, B), with Hoeffding’s inequality and a union bound providing uniform approximation.Conditional on each permutation, the sign product has expectation one for agreeing hashes and zero otherwise; summands lie in [−1, 1].
  • D.4 Proof of Corollary 6.4: D.4 Proof of Corollary 6.4: Theorem 6.3 applies unchanged to signed features after bounding feature distances by 2 and setting η = α/2.The resulting approximation and sample-size conditions are those stated in equations (32)–(33).
  • E The alternative empty-set convention: E The alternative empty-set convention: If Jac(∅, ∅) = 0, the score matrix has rank N − 1, affine dimension N − 1, while the loss matrix has rank N.The empty score column is zero, the remaining score columns are independent, and the loss-kernel argument forces the null vector to vanish.
  • E The alternative empty-set convention: E The alternative empty-set convention: Omitting the empty outcome from the factorial distribution gives calibration lower bound 2^s−1 −1, while the affine-dimension upper bound remains 2^s −1.The supported outcomes and exact Bayes-optimal reports both have size 2^s−1, and the restricted active score matrix is positive definite.
Loading 2608.13549v1…