Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure

Overview§

This paper studies the per-instance Jaccard score (IoU) in multi-label classification with $s$ labels. The central question is: what dimensionality is required for a convex surrogate loss to be calibrated w.r.t. Jaccard, and what regret bounds can be achieved at polynomial dimension?

Core Results§

• The Jaccard loss matrix $L^{\mathrm{Jac}}_{y,\hat y}=1-\mathrm{Jac}(y,\hat y)$, its shifted version, and the ordinary loss matrix are nonsingular for all $s\ge 1$. The loss columns span an affine space of dimension $2^s-1$.
• The convex calibration dimension satisfies:

$$ 2^{s-1} \le \mathrm{CCdim}(L^{\mathrm{Jac}}) \le 2^s-1. $$ Thus any exactly calibrated convex surrogate needs exponentially many prediction coordinates in $s$.

• For additive regret tolerance $\alpha>0$:
• An $F_1$-to-Jaccard transfer yields a polynomial $(s^2+1)$-dimensional surrogate with asymptotic Jaccard regret $\le 3-2\sqrt2$.
• A MinHash square-loss surrogate has dimension $O((s^2+s\log(1/\rho))/\alpha^2)$.
• A signed variant has dimension $O((s+\log(1/\rho))/\alpha^2)$.

Both achieve Jaccard-regret floor $\alpha$ uniformly over arbitrary conditional label distributions.

Mathematical Methodology§

MinHash Gram Representation§

The key tool is a finite MinHash representation. For a set $A\subseteq[s]$, define a random permutation $\pi$ on $[s]$, and let the MinHash collision kernel be $$ K(A,B) = \Pr_{\pi}\left[\arg\min_{i\in A}\pi(i) = \arg\min_{j\in B}\pi(j)\right] = \mathrm{Jac}(A,B), $$ with the convention that the argmin of the empty set is a special symbol, so $\Pr[\emptyset=\emptyset]=1$. This Gram representation makes the loss $1-K(A,B)$ a kernel matrix. Boolean Möbius inversion over the subset lattice then proves the full rank and affine dimension statements.

Calibration Dimension Lower Bound§

The lower bound $2^{s-1} \le \mathrm{CCdim}(L^{\mathrm{Jac}})$ is proved by constructing a factorially weighted distribution over $2^{s-1}+1$ outcomes whose Bayes-optimal reports force any calibrated surrogate to separate all these points. Consequently, any exactly calibrated convex surrogate must have at least $2^{s-1}$ prediction coordinates.

Approximation Guarantees§

$F_1$-to-Jaccard Transfer§

Starting from an existing $F_1$-calibrated surrogate (with dimension $s^2+1$), the authors derive a transfer inequality: $$ \mathcal{R}_{\mathrm{Jac}}(f) \le (3-2\sqrt2) + \mathcal{R}_{F_1}(g), $$ binding Jaccard regret to $F_1$ regret.

MinHash Square-Loss Surrogate§

For a fixed error tolerance $\alpha$ and confidence $1-\rho$, sample $k$ random permutations. Each set $y$ is mapped to a $k$-tuple of min-hash indices: $$ \Phi(y) = \left[\mathrm{argmin}_{i\in y}\pi_t(i)\right]_{t=1}^k, $$ with a special symbol for the empty set. The surrogate loss is square loss $\ell(\hat y, y)=\|\hat y - \Phi(y)\|^2$ over a $k(s+1)$-dimensional (or a signed $O(k)$-dimensional) representation. The prediction rule is $$ \hat y(x) = \arg\max_{y'\subseteq[s]} \langle \Phi(y'), g(x)\rangle, $$ where $g(x)$ is a regressor trained on the embedded labels. Dimension bounds follow from choosing $k$ via concentration of MinHash estimates.

Code Snippet§

A minimal PyTorch illustration of training a MinHash square-loss surrogate:

import torch
import torch.nn as nn

s = 10       # number of labels
k = 128      # number of MinHash permutations

# Precompute random permutations
perms = torch.argsort(torch.randn(k, s), dim=1)  # k x s, each row a permutation

def minhash_embedding(labels):
    # labels: batch x s binary
    B = labels.shape[0]
    idx = torch.full((B, k), s, dtype=torch.long)  # special symbol s for empty set
    for t in range(k):
        order = perms[t]           # s
        mask = labels[:, order]    # B x s
        first = mask.argmax(dim=1, keepdim=True)  # B x 1
        valid = mask.any(dim=1)
        idx[valid, t] = order[first[valid]].squeeze()
    emb = torch.nn.functional.one_hot(idx, s+1).float()  # B x k x (s+1)
    return emb.reshape(B, -1)

class Surrogate(nn.Module):
    def __init__(self, input_dim, hidden=64):
        super().__init__()
        self.net = nn.Sequential(
            nn.Linear(input_dim, hidden),
            nn.ReLU(),
            nn.Linear(hidden, k*(s+1))
        )
    def forward(self, x):
        return self.net(x)

model = Surrogate(input_dim=50)
optimizer = torch.optim.Adam(model.parameters(), lr=1e-3)
loss_fn = nn.MSELoss()

for x, y in dataloader:          # y: binary labels
    target = minhash_embedding(y) # B x k*(s+1)
    pred = model(x)
    loss = loss_fn(pred, target)
    optimizer.zero_grad()
    loss.backward()
    optimizer.step()

The learned regressor $g(x)$ is then used to score label sets via the inner product $\langle \Phi(y'), g(x)\rangle$ at inference.

Key Takeaways§

• Exact calibration for Jaccard is provably expensive: exponential dimension is unavoidable for convex surrogates.
• If an additive regret tolerance is acceptable, polynomial dimension suffices via randomized MinHash embeddings.
• The MinHash square-loss surrogate is simple, practical, and dimension-efficient (especially the signed variant).