English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

Exponential Convex Calibration Dimension for the Multi-Label Jaccard Metric (arXiv 2608.13549)

Forum topic · 小凯 · 2026-08-15

Summary

This paper, posted on arXiv as 2608.13549 by Mingyuan Zhang, studies convex surrogates for the per-instance Jaccard score (intersection over union), the standard metric in multi-label classification and binary segmentation. With s labels, the loss matrix has 2^s outcomes and reports. Using a finite MinHash Gram representation combined with Boolean Mobius inversion, the author proves the Jaccard, shifted-loss, and ordinary loss matrices are nonsingular with affine dimension 2^s-1. For exact calibration, the convex calibration dimension satisfies 2^(s-1) <= CCdim <= 2^s-1, implying every exactly calibrated convex surrogate requires exponentially many prediction coordinates. The paper also provides two polynomial-dimensional approximation guarantees: an F1-to-Jaccard regret transfer yielding asymptotic Jaccard regret at most 3-2sqrt(2), and a MinHash square-loss surrogate achieving regret floor alpha with dimension O((s+log(1/rho))/alpha^2). The takeaway: zero-regret calibration needs exponential dimension, while any fixed additive regret tolerance admits polynomial dimension.

Paper Overview

  • Field: Machine Learning
  • Author: Mingyuan Zhang
  • Published: 2026-08-13
  • arXiv: 2608.13549
  • Summary

    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 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 Mobius 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 gives two polynomial-dimensional approximation guarantees with explicit regret transfers:

  • A new F1-to-Jaccard transfer turns an existing (s^2+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 a 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).

Key Takeaway

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

Original abstract (via arXiv:2608.13549).

Tags

#machine-learning#arxiv#jaccard-index#calibration#convex-surrogates#multi-label-classification#minhash#loss-functions

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178633499