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

The instance-wise F1 measure is a central performance measure for multi-label classification. For a problem with s labels, it defines a 2s× 2s loss matrix. Previous work exhibited s2+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 F1(varnothing,varnothing)=1, the F1 score matrix, the shifted loss matrix, and the unshifted loss matrix all have rank s2-s+2, while the column-affine dimension of the loss is s2-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 F1 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/3rfloor and h=lceil(slfloor s/3rfloor)1/2rceil-1. Applying the feasible-subspace lower bound for convex calibration dimension gives [ operatornameCCdim(LF1) ≥ left(frac23√3-o(1)right)s2. ] Together with the quadratic upper bound, this establishes operatornameCCdim(LF1)=Theta(s2).