Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure

• URL: http://arxiv.org/abs/2608.13549v1
• Date: Thu, 13 Aug 2026 17:59:17 GMT
• Title: Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure
• Abstract summary: We prove that the Jaccard score, shifted-loss, and ordinary loss matrices are nonsingular and that the loss columns have affine dimension $2s-1$.<n>We also give two-dimensional approximation guarantees with explicit regret transfers.
• Score: 12.752262012085419
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Thompson Sampling for Non-Monotone Convex Ridge Bandits: Monotonicity Is Not Needed for Polynomial Regret [6.657272312990604]
  We prove that Thompson sampling (TS) has Bayesian regret $tilde O(d5/2sqrt n)$ for bandit convex optimisation with convex emphmonotone ridge losses.
  arXiv  Detail & Related papers  (2026-09-10T01:58:03Z)
• Schatten norms and determinants of linear combinations of matrix tensor powers via virtual representations [0.8594140167290097]
  Direct determinant of determinants or Schattenoretic norms of $X_n$ is exponential in $n$.<n>We give an exact representation of the computation method which, for fixed $d$ and $s$, computes $|X_n|_p$, $0pin$, and determinants in time in $n$.<n>For $d=3$, each irreducible contribution reduces to the difference of two explicitly computable symmetric-power terms, leading to an open-source implementation.
  arXiv  Detail & Related papers  (2026-09-03T18:08:23Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss [12.752262012085419]
  We analyze the Bayes geometry of $F_$ directly.<n>We show that the corresponding active loss columns, restricted to the witness support, have affine dimension $hn$.<n>Applying the feasible-subspace lower bound for convex dimension calibration gives [ operatornameCCdim(LF_) ge left(frac23sqrt3-o(1)right. ] Together with the quadratic upper bound, this establishes $operatornameCCdim(LF_)=
  arXiv  Detail & Related papers  (2026-08-09T01:26:56Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP)<n>For every fixed $in(0,1)$, there are constants $A_,c_>0$.<n>Unit-sphere MAX-IP matrix is an exact two-valued affine image of the DNF pattern matrix with gap of at least $8$.
  arXiv  Detail & Related papers  (2026-07-22T17:27:20Z)
• Logarithmic Density of Rank $\geq 1$ and Rank $\geq 2$ Genus-2 Jacobians and Applications to Hyperelliptic Curve Cryptography [0.0]
  We study existence results for genus-$2$ curves over $mathbbQ$ whose Jacobians have Mordell-Weil rank at least $1$ or $2$.<n>We present a large explicit subfamily where Jacobians have ranks $r geq 2$, yielding an unconditional logarithmic density of at least $5/7$.
  arXiv  Detail & Related papers  (2026-01-23T19:40:04Z)
• Quantitative Bounds for Sorting-Based Permutation-Invariant Embeddings [13.307069556587471]
  We study the sorting-based embedding $beta_mathbf A : mathbb Rn times d to mathbb Rn times D$, $mathbf X mapsto downarrow(mathbf X mathbf A)$, where $downarrow$ denotes column wise sorting of matrices.
  arXiv  Detail & Related papers  (2025-10-25T06:44:08Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  Worst-case minimax regret for sparse linear bandits is $widetildeThetaleft(sqrtdTright)$. In the benign setting where there is no noise and the action set is the unit sphere, one can use divide-and-conquer to achieve an $widetildemathcal O(1)$ regret. We develop a general framework that converts any variance-aware linear bandit algorithm to a variance-aware algorithm for sparse linear bandits.
  arXiv  Detail & Related papers  (2022-05-26T15:55:44Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  We show how to construct variance-aware confidence sets for linear bandits and linear mixture Decision Process (MDP) For linear bandits, we obtain an $widetildeO(mathrmpoly(d)sqrt1 + sum_i=1Ksigma_i2) regret bound, where $d is the feature dimension. For linear mixture MDP, we obtain an $widetildeO(mathrmpoly(d)sqrtK)$ regret bound, where
  arXiv  Detail & Related papers  (2021-01-29T18:57:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.