Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss

• URL: http://arxiv.org/abs/2608.08399v1
• Date: Sun, 09 Aug 2026 01:26:56 GMT
• Title: Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss
• Abstract summary: 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_)=
• Score: 12.752262012085419
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The instance-wise $F_1$ measure is a central performance measure for multi-label classification. For a problem with $s$ labels, it defines a $2^s\times 2^s$ loss matrix. Previous work exhibited $s^2+1$-coordinate affine and shifted low-rank representations and used them to construct quadratic-dimensional convex calibrated surrogates. We determine the exact rank. Under the convention $F_1(\varnothing,\varnothing)=1$, the $F_1$ score matrix, the shifted loss matrix, and the unshifted loss matrix all have rank $s^2-s+2$, while the column-affine dimension of the loss is $s^2-s+1$. The proof factors the nonempty score matrix through subset-incidence matrices and a positive-definite Cauchy matrix. Exact rank does not, by itself, lower-bound the dimension of an arbitrary convex calibrated surrogate. We therefore analyze the Bayes geometry of $F_1$ directly. We construct a distribution for which precisely all supersets of a fixed core label set are Bayes optimal, and show that the corresponding active loss columns, restricted to the witness support, have affine dimension $hn$, where $n=s-\lfloor s/3\rfloor$ and $h=\lceil(s\lfloor s/3\rfloor)^{1/2}\rceil-1$. Applying the feasible-subspace lower bound for convex calibration dimension gives \[ \operatorname{CCdim}(L^{F_1}) \ge \left(\frac{2}{3\sqrt{3}}-o(1)\right)s^2. \] Together with the quadratic upper bound, this establishes $\operatorname{CCdim}(L^{F_1})=Θ(s^2)$.

Related papers

• Exponential Convex Calibration Dimension for the Multi-Label Jaccard Measure [12.752262012085419]
  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.
  arXiv  Detail & Related papers  (2026-08-13T17:59:17Z)
• Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
  We prove $c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$ with no sign, sparsity, or squareness restriction.<n>Within the pure-$varepsilon$-DP matrix-mechanism class, the optimized maximum and mean squared errors are both $(varepsilon-2log3(n+1))$.
  arXiv  Detail & Related papers  (2026-07-30T14:41:34Z)
• Phase Transition in Convex Relaxations for Graph Alignment [6.515592049126884]
  We study the graph alignment problem for correlated Gaussian Orthogonal Ensemble (GOE) matrices.<n>Our results precisely characterize that $|Xstar-star|_F2$ transitions from $o(n)$ for $= tildeo(n-1/2)$ to $(n)$ for $= tilde(n-1/2)$.
  arXiv  Detail & Related papers  (2026-06-14T03:47:45Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• Equality condition for a matrix inequality by partial transpose [4.115763274264731]
  We study the equality condition for a matrix inequality generated by partial transpose.<n>We show that $sumK_j=1 A_j otimes B_j$ is locally equivalent to an elegant block-diagonal form.
  arXiv  Detail & Related papers  (2025-08-26T03:42:46Z)
• 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)
• Efficient $1$-bit tensor approximations [1.104960878651584]
  Our algorithm yields efficient signed cut decompositions in $20$ lines of pseudocode. We approximate the weight matrices in the open textitMistral-7B-v0.1 Large Language Model to a $50%$ spatial compression.
  arXiv  Detail & Related papers  (2024-10-02T17:56:32Z)
• 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)
• Constant matters: Fine-grained Complexity of Differentially Private Continual Observation [10.624505781812385]
  We study fine-grained error bounds for differentially private algorithms for counting continual observation. We are the first to give concrete error bounds for various problems under continual observation.
  arXiv  Detail & Related papers  (2022-02-23T11:50:20Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• On the computational and statistical complexity of over-parameterized matrix sensing [30.785670369640872]
  We consider solving the low rank matrix sensing problem with Factorized Gradient Descend (FGD) method. By decomposing the factorized matrix $mathbfF$ into separate column spaces, we show that $|mathbfF_t - mathbfF_t - mathbfX*|_F2$ converges to a statistical error.
  arXiv  Detail & Related papers  (2021-01-27T04:23:49Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
  arXiv  Detail & Related papers  (2020-05-22T16:55:01Z)

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.