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

Motivation

• The paper asks whether the F1 loss matrix has exact rank and whether every convex calibrated surrogate requires quadratic prediction dimension.Earlier work supplied s^2+1-coordinate affine or shifted representations and quadratic-dimensional surrogates, but left both questions open.Source: §1 · p. 1

Convex calibration lower bound

• Exact matrix rank alone cannot lower-bound arbitrary convex calibrated surrogate dimension because calibration need only preserve Bayes-optimal reports.The paper therefore uses feasible-subspace geometry rather than rank alone.Source: §1 · pp. 1–2
• A hard conditional distribution makes every superset of a fixed core label set Bayes-optimal, creating many simultaneously active loss directions.The optional labels and their cardinalities are tuned so all such supersets tie in expected F1 score.Source: §1 · p. 2

Contributions

• The shifted, ordinary, and column-affine loss dimensions are respectively s^2-s+2, s^2-s+2, and s^2-s+1.These results sharpen earlier s^2+1-dimensional representations.Source: §1 · p. 2
• Combining the quadratic lower bound with the affine-dimension upper bound establishes CCdim(L^F1)=Theta(s^2).The result supplies an F1-specific quadratic lower bound rather than only an upper bound from a particular surrogate construction.Source: §1 · pp. 1–2

Definitions

• Outcomes and predictions are subsets of [s], with F1 score 1 only for two empty sets and otherwise 2|A∩B|/(|A|+|B|).The corresponding loss is one minus the score.Source: §2 · p. 2

Decision-theoretic setting

• The paper studies an example-based loss that applies F1 to each true-predicted set pair before taking expectation under an arbitrary conditional distribution.This differs from micro- and macro-averaged objectives that aggregate counts before applying F1.Source: §2 · p. 2

Bayes risk

• The loss matrix L has one column per report, and a report is Bayes-optimal when it minimizes the conditional risk p^T L·,B.The setup indexes probabilities and supports by the 2^s possible label sets.Source: §2 · p. 2

Dimensions

• Column-affine dimension is the affine dimension of the loss columns, while convex calibration dimension is the smallest surrogate dimension admitting a calibrated convex surrogate and link.These dimensions are distinct objects used for upper and lower bounds.Source: §2 · pp. 2–3

Calibration framework

• The feasible-subspace framework supplies general upper and lower bounds for convex calibration dimension.The paper invokes the corresponding results of Ramaswamy and Agarwal (2016).Source: §2 · p. 3

Bayes-optimal prediction

• Prior decision-theoretic and plug-in methods showed that quadratic numbers of conditional-distribution statistics suffice for Bayes-optimal F1 prediction.These works did not claim that the quadratic number is necessary or compute the loss-matrix rank.Source: §3 · p. 3

Low-rank surrogates

• Nowak et al. (2019) gave s^2+1-coordinate affine decompositions, while Zhang et al. (2020) built s^2+1-dimensional convex calibrated surrogates from shifted low-rank structure.The present rank theorem sharpens Zhang et al. (2020) for beta=1 and identifies the exact affine dimension.Source: §3 · p. 3

Calibration dimension

• General calibration-dimension and elicitation frameworks provide affine-dimension and feasible-subspace bounds, but ordinary rank does not generally lower-bound arbitrary convex surrogate dimension.Nonlinear surrogates may preserve only Bayes decisions rather than reconstructing all conditional risks.Source: §3 · p. 3

Exact rank theorem

• Theorem 4.3 states that for every s ≥ 1, rank(F)=rank(L−J)=s2−s+1, rank(L)=s2−s+2, and affdim(L)=s2−s+1.Thus, rank(F) and rank(L−J) coincide, while affdim(L) is one smaller than rank(L).Source: §4 · p. 4

Proof mechanism

• On nonempty subsets, the score matrix factors as K=P(C⊗I_s)P^T, where subset-incidence blocks determine P and the Cauchy middle matrix is positive definite.The incidence rank is s^2-s+1, and positive definiteness preserves that rank through the factorization.Source: §4 · p. 4
• Adding the isolated empty-set entry increases the score rank by one, while the loss null-space analysis gives rank(L)=1+rank(K).The shifted identity follows from L-J=-F.Source: §4 · p. 4

Affine dimension

• The affine dimension follows because the all-ones vector lies in the score range, and the affine map x↦1−x transfers score-column affine dimension to loss columns.This yields affdim(L)=rank(F)-1.Source: §4 · p. 4

Implication

• The exact ranks improve the earlier surrogate upper bound under the empty-set convention.The result is presented as an improved surrogate upper bound following the rank calculation.Source: §4 · p. 4

• CCdim(LF1) ≥ 2s^2/9 for s ≥ 12, establishing an explicit quadratic lower bound.Source: §5 · p. 4
• A witness distribution makes exactly the reports containing a fixed core set T Bayes optimal, while reports missing any core label are strictly worse.The witness is supported on outcome layers 1 through h, with tuned inclusion marginals.Source: §5 · p. 5
• The tied active loss columns have affine dimension hn, yielding h(n−1) label-swap directions and h independent cardinality-change directions.Source: §5 · pp. 4–5
• The feasible-subspace theorem converts these simultaneously active loss differences into a lower bound for arbitrary convex calibrated surrogates, not merely linear reconstructions.Source: §5 · p. 5
• The lower bound is unchanged under the convention F(∅,∅)=0 because the witness assigns no probability to the empty outcome.Source: §5 · p. 5

• Every convex calibrated surrogate for the s-label F1 loss has prediction dimension Ω(s^2) under the standard distribution-free notion of L-calibration.Source: §6 · p. 5
• The shifted loss matrix has exact rank s^2−s+2, closing the gap left by the earlier s^2+1 upper bound.Source: §6 · p. 5
• The bounds establish CCdim(LF1)=Θ(s^2), but they do not determine the exact convex calibration dimension.Source: §6 · p. 5
• Closing the constant-factor gap may require a harder trigger distribution or a surrogate using less than the full affine dimension; extending the analysis to Fβ and Jaccard losses is another direction.Source: §6 · p. 5

• For 1 ≤ k ≤ s−1, any vector in ker(Wk) has equal coordinates, and the defining equations force that common value to zero.Source: §A.1 · p. 6
• Thus ker(Wk)={0} and rank(Wk)=s for every k<s.Source: §A.1 · p. 6
• When k=s, W_s consists of one nonzero all-ones row, so rank(W_s)=1.Source: §A.1 · p. 6

A.2 Proof of Lemma 4.2

• The Cauchy matrix C is positive definite because its quadratic form is an integral of a nonnegative function that is strictly positive for every nonzero vector.Source: §A.2 · pp. 6–7
• Equivalently, C is the L2(0,1) Gram matrix of linearly independent functions, which explains its nonsingularity.Source: §A.2 · p. 7

A.3 A positive-middle rank identity

• If M is positive definite and factors as GG^T with G invertible, then XMX^T=(XG)(XG)^T, so rank and column-space conclusions reduce to those for XG.Source: §A.3 · p. 7

A.4 Proof of Theorem 4.3

• The nonempty score matrix factors as K = P(C ⊗I_s)P⊤, where P groups subset-incidence blocks by cardinality and C ⊗I_s is positive definite.The block structure gives rank s to the first s−1 incidence blocks and rank 1 to the final block, yielding rank(P) = s^2 −s + 1.Source: §A.4 · pp. 7–8
• rank(F) = s^2 −s + 2 after the isolated empty-set score entry adds one to the nonempty block rank.The nonempty block has rank ρ = s^2 −s + 1, and the scalar empty-set block is disjoint from it.Source: §A.4 · p. 8
• rank(L) = s^2 −s + 2 because ker L = {0} × ker K, despite the rank-one shift from the score matrix to the loss matrix.The null-space calculation uses 1+ ∈ range(K) and shows that the added empty-set row and column increase rank by one.Source: §A.4 · p. 8
• The loss columns have affine dimension s^2 −s + 1, obtained by augmenting columns with a final coordinate and using the invertible score-to-loss affine map.Appending the all-ones row does not increase the relevant rank, and x 7→1_N −x preserves affine dimension.Source: §A.4 · p. 9

A.5 Proof of Corollary 4.4

• The CC-dimension bound follows directly from the feasible-subspace inequality and Theorem 4.3.Source: §A.5 · p. 9

A.6 Verification of Remark 4.5

• The cited result states that rank(F) = rank(K) = s^2 −s + 1, and since L −J = −F, L −J has the same rank.Source: §A.6 · p. 9
• Under the alternative convention, rank(L) remains s^2 −s + 2 because ker L = {0} × ker K.Source: §A.6 · p. 9
• The loss’s affine dimension under the alternative convention is s^2 −s + 1 because the zero score column lies in the family and the score-to-loss affine map is invertible.Source: §A.6 · p. 9

Step 1–2

• Bayes-optimal predictions are exactly B_C = T ∪ C for C ⊆ O: every prediction containing the core T ties, while omitting any core label is strictly worse.The witness distribution mixes positive-support outcomes from cardinality layers 1 through h, with inclusion marginals chosen to equalize scores across optional-label choices.Source: B Proof of the quadratic CC-dimension… · p. 11

Step 3b

• The score-column encoding Ψ is injective: a zero encoded vector forces all coefficients in every outcome-size row to vanish.Comparing m-subsets differing in one label first equalizes all label coefficients, and the positive subset size then forces their common value to zero.Source: B Proof of the quadratic CC-dimension… · pp. 12–13

Step 3c

• Label swaps generate a subspace S of dimension h(n−1), representing independent zero-sum exchanges among optional labels across the h outcome-cardinality layers.Pairwise optional-label differences span the zero-sum space, while the Cauchy matrix Γ is nonsingular and separates the h layer profiles.Source: B Proof of the quadratic CC-dimension… · pp. 13–14

Step 3d

• The proof next isolates cardinality-change directions by averaging coefficient matrices over all optional subsets of each size, eliminating label identities while retaining the cardinality profile.These averaged cardinality differences are shown to lie in the difference space D, setting up the remaining affine-dimension count.Source: B Proof of the quadratic CC-dimension… · pp. 14–15

Step 3e

• The active difference space decomposes directly as D = S ⊕ H, with dim D = h(n − 1) + h = hn.The cardinality-change directions H are linearly independent of the h(n − 1) label-swap directions in S, and the resulting loss-column affine dimension is also hn.Source: B Proof of the quadratic CC-dimension… · pp. 16–17

Step 4

• The two-sided feasible directions are exactly those supported on U, normalized to sum zero, and orthogonal to every restricted active loss difference.Inactive comparisons remain strict under sufficiently small perturbations, while active Bayes ties must remain equalities.Source: B Proof of the quadratic CC-dimension… · p. 17

Step 4(iii)

• The feasible-subspace dimension is B0(p) = R − dE − 1, where R = |U| and dE = hn.The active-difference constraints and the normalization constraint are independent, so their orthogonal complement has this dimension.Source: B Proof of the quadratic CC-dimension… · p. 18

Step 5

• For s ≥ 12, the cited passage states that t ≥s/4 and n ≥2s/3, as part of the proof of (9).Source: B Proof of the quadratic CC-dimension… · p. 18