{"id":"83eb8cfa-e0c1-4d12-bbd5-2d3474800e18","arxiv_id":"2608.08399","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"The F1 loss matrix has rank s^2-s+2, and every convex calibrated surrogate for it requires at least Omega(s^2) prediction dimension.","lead":"This math paper pins down the exact rank of the multi-label F1 loss matrix and proves that any convex prediction rule for it needs a quadratic number of internal coordinates. It closes an open gap between known upper and lower bounds, showing that the quadratic size of such surrogates is unavoidable.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The central claims are the exact rank s^2-s+2 and the quadratic lower bound on CCdim. I read the full proof rather than only the abstract. The rank proof is solid: Lemma 4.1 is correct, Lemma 4.2 is a valid positive-definiteness argument, and the null-space computation for L in Step 3 of Theorem 4.3 checks, including the use of 1_+∈range(K) and the strict positivity of u^TKu. The affine-dimension argument via appending an all-ones row is also valid. The lower-bound construction is intricate but coherent: the witness distribution is well-defined because α_m,β_m lie in the relative interior of the hypersimplex; the Bayes-optimal face is exactly the supersets of T; the coefficient encoding Ψ is injective; the dimension count D=S⊕H is explicit and correct; and the conversion to the feasible subspace in Step 4 is exact, with the normalization vector 1_U shown independent of E. The only potentially load-bearing imported result is the feasible-subspace lower bound (6), and the paper applies it faithfully. The reader's weakest-assumption analysis correctly identifies this import as the place where a hidden hypothesis could matter, but no violation is apparent. The proof is parameter-free, the construction is falsifiable by small-s enumeration, and I see no reason to alter the ACCEPT verdict.","tokens_in":17088,"tokens_out":25958,"duration_ms":293909,"concrete_test":"Check the exact statement and proof of Theorem 16 in Ramaswamy and Agarwal (2016), confirming that it applies to a boundary point p with a non-unique Bayes-optimal set; if the theorem instead requires p in the relative interior of Q_B, recompute μ at such a point and see whether the lower bound survives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing concern identified. Theorem 4.3 is self-contained: the factorization K=P(C⊗I_s)P^T, the positive-middle rank identity, and the null-space argument for L all check. Theorem 5.1 is internally consistent: Step 1 produces a valid full-support mixture on U; Step 2 shows the Bayes-optimal reports are exactly the supersets of T; Steps 3a–3e compute the active-column affine dimension hn through the injective map Ψ and the direct decomposition D=S⊕H; Step 4 correctly identifies the two-sided feasible subspace as (E⊕span{1_U})^⊥, giving μ=R−hn−1. The only external dependency is Ramaswamy–Agarwal Theorem 16, and the use here matches its stated form for arbitrary p in the trigger set, including boundary points with multiple Bayes-optimal reports. I found no internal gap; the concern would only land if that theorem has hidden hypotheses, which the citation does not suggest.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper determines the exact rank and column-affine dimension of the instance-wise F1 loss matrix for multi-label classification with s labels, and proves a quadratic lower bound on the convex calibration dimension. Under the convention F1(∅,∅)=1, Theorem 4.3 shows rank(F)=rank(L−J)=rank(L)=s^2−s+2 and affdim(L)=s^2−s+1; the appendix factors the nonempty score block as P(C⊗I_s)P^T via subset-incidence matrices and a positive-definite Cauchy matrix. Theorem 5.1 constructs a conditional distribution whose Bayes-optimal reports are exactly all supersets of a fixed core set, shows the corresponding active loss columns restricted to the witness support have affine dimension hn with t=⌊s/3⌋, n=s−t, h=⌈√(st)⌉−1, and applies the feasible-subspace lower bound of Ramaswamy and Agarwal (2016) to obtain CCdim(L^{F1})≥(2/(3√3)−o(1))s^2. Combined with CCdim(L^{F1})≤affdim(L), this yields CCdim(L^{F1})=Θ(s^2). Remark 4.5 verifies the alternative empty-set convention.","tokens_in":17222,"tokens_out":26898,"duration_ms":273574,"significance":"This is a substantive contribution. The exact-rank result closes the gap left by the s^2+1 upper bounds of Nowak et al. (2019) and Zhang et al. (2020), and the lower bound is the first F1-specific quadratic lower bound on convex calibration dimension. The lower bound is genuinely Bayes-geometric rather than a corollary of rank, and the proof is carried out in full: the factorization, the injectivity of the coefficient map Ψ, the direct decomposition D=S⊕H, and the feasible-subspace count are all explicit. The construction is parameter-free up to the scale s, and the asymptotic constant is stated. The paper is also careful about the empty-set convention and explicitly acknowledges that the exact constant in the Θ(s^2) bound remains open.","major_comments":[],"minor_comments":[{"comment":"The feasible-subspace lower bound is applied to a trigger point p that lies on the boundary of the probability simplex and whose Bayes-optimal set is a face rather than a singleton. This is legitimate because Theorem 16 of Ramaswamy and Agarwal (2016) is stated for arbitrary p in the trigger set, but the paper would be easier to read if it said so explicitly in one sentence.","section":"Section 5, Step 4 (Eq. 6)"},{"comment":"In the definition of the swap space S, the condition Z_{·,O}1_O=0_h is compact; a sentence stating that the optional block of every row lies in W_swap would make the subsequent dimension count more immediately transparent.","section":"Section 5, Step 3c"},{"comment":"In the converse containment for ker L, the fact that 1_+^T z=0 for every z∈ker K is used; this follows from 1_+∈range(K) and symmetry of K, and stating it in the converse sentence would avoid a small ambiguity in the exposition.","section":"Section 4, Proof of Theorem 4.3, Step 3"}],"recommendation":"accept","confidential_remarks":"The paper is technically sound; I checked the key computations, including the Cauchy-determinant nonsingularity, the injectivity of Ψ, the direct decomposition D=S⊕H, and the ker L argument. The only external dependency is the standard feasible-subspace theorem, and the application to a boundary trigger point is faithful to its statement. The overlap with Zhang et al. (2020) is a natural continuation and is properly cited. I support publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a solid theory paper. It settles two open questions: the exact rank of the F1 loss matrix under the stated empty-set convention, and the first quadratic lower bound on convex calibration dimension for F1. I checked the rank proof and the lower-bound construction; both hold up.\n\nThe rank part is genuinely elegant. The nonempty score block factors through subset-incidence matrices and a positive-definite Cauchy matrix; the positive-middle rank identity gives the rank, and the all-ones shift is handled with a null-space argument. The affine-dimension count follows cleanly. The step where 1_{N-1} is shown to lie in range(K) is particularly careful.\n\nThe lower bound is the real contribution. The paper constructs a witness distribution where all supersets of a fixed core set are Bayes-optimal, shows the active loss columns restricted to the support have affine dimension hn, and then applies the Ramaswamy-Agarwal feasible-subspace bound. The decomposition into label-swap and cardinality-change directions is intricate but internally consistent. The Cauchy nonsingularity, the injectivity of Psi, and the direct sum S ⊕ H all check out on inspection. I found no circularity and no parameter fitting.\n\nThe only external load-bearing piece is Theorem 16 of Ramaswamy and Agarwal (2016), imported without proof. The use here matches the stated theorem for arbitrary trigger points, including boundary points with multiple Bayes-optimal reports, so I do not see a problem, but it is the one place a referee should re-read carefully. The self-citation to Zhang et al. (2020) is disclosed and is used for context and upper-bound comparison, not to prop up the new lower bound.\n\nMinor soft spots: the constant in the lower bound is far from the upper bound, so exact CCdim remains open; and the paper is purely mathematical, so there is no empirical component to evaluate. Neither affects the central claims. Also, the rank result depends on the convention F(∅,∅)=1, and the paper transparently reports what changes under the alternative convention.\n\nThis paper deserves a serious referee. If the referee confirms the external theorem's applicability, I would accept. I would cite it in my own work and would bring it to a reading group.","headline":"A rigorous theory paper that nails the exact rank and the first quadratic convex-calibration-dimension lower bound for multi-label F1; it deserves refereeing.","tokens_in":17774,"tokens_out":2300,"would_cite":true,"duration_ms":23951,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05","15A03"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper determines the exact rank of the multi-label F1 loss matrix and proves that every convex calibrated surrogate for it must have quadratic prediction dimension.","keywords":["multi-label classification","F1 loss","convex calibration dimension","loss-matrix rank","subset-incidence matrix","Cauchy matrix","Bayes-optimal prediction","surrogate dimension"],"falsifier":"For $s=3$, the rank formula predicts rank $8$ for the $8\\times 8$ $F_1$ score matrix; a direct symbolic rank computation returning any other value would refute the rank theorem. For the calibration bound (which gives $hn=2$ at $s=3$), exhibiting any convex calibrated surrogate with prediction dimension $1$ for the three-label $F_1$ loss would falsify the lower bound.","tokens_in":16863,"feed_emoji":"📐","tokens_out":9576,"duration_ms":88119,"temperature":0.7,"pith_summary":"This paper determines the exact linear-algebraic size of the instance-wise $F_1$ loss for multi-label classification with $s$ labels: under the convention $F_1(\\varnothing,\\varnothing)=1$, the score matrix, the shifted loss matrix, and the unshifted loss matrix all have rank $s^2-s+2$, and the loss columns have affine dimension $s^2-s+1$. It then proves that this quadratic size is not merely an upper bound: every convex calibrated surrogate for the $F_1$ loss must use prediction dimension at least $(s-\\lfloor s/3\\rfloor)(\\lceil\\sqrt{s\\lfloor s/3\\rfloor}\\rceil-1)$, which is $(2/(3\\sqrt{3})-o(1))s^2$. Together with the affine-dimension upper bound, this gives $\\operatorname{CCdim}(L^{F_1})=\\Theta(s^2)$, settling whether the earlier quadratic-dimensional convex surrogates could be beaten. A reader should care because $F_1$ is nondecomposable across labels: the result shows that any convex surrogate that preserves Bayes-optimal $F_1$ decisions must pay a quadratic cost in prediction dimension.","feed_headline":"Multi-label F1 loss provably needs quadratic-dimensional surrogates","feed_subtitle":"Exact rank and a new lower bound show every convex calibrated surrogate pays quadratic dimension.","key_machinery":"The load-bearing objects are the subset-incidence matrices $W_k$, whose rows are the $k$-subsets and whose columns are labels, and the positive-definite Cauchy matrix $C_{kk'}=2/(k+k')$; the score matrix factors as $K=P(C\\otimes I_s)P^{\\top}$, letting the rank calculation pass through the incidence matrices. For the calibration lower bound, the central mechanism is a witness distribution on layered outcome sizes whose Bayes-optimal reports are exactly the supersets of a fixed core set, creating tied loss columns whose difference span has dimension $hn$; the feasible-subspace lower bound then converts that local affine dimension into a lower bound applying to every convex calibrated surrogate.","core_discovery":"On the paper's own terms, the central discovery is two-fold. First, the $F_1$ score matrix on nonempty label sets factors as $K=P(C\\otimes I_s)P^{\\top}$, where $P$ is a block-diagonal matrix of subset-incidence matrices $W_k$ and $C$ is the positive-definite Cauchy matrix with entries $2/(k+k')$; the rank identity $\\operatorname{rank}(XMX^{\\top})=\\operatorname{rank}(X)$ for $M\\succ 0$ then forces $\\operatorname{rank}(K)=\\operatorname{rank}(P)=s^2-s+1$, and the isolated empty-set entry plus a null-space analysis of $L$ give $\\operatorname{rank}(F)=\\operatorname{rank}(L-J)=\\operatorname{rank}(L)=s^2-s+2$ and $\\operatorname{affdim}(L)=s^2-s+1$. Second, because exact rank alone cannot lower-bound arbitrary convex surrogates, the paper constructs a witness distribution supported on outcome-cardinality layers $1,\\dots,h$ whose Bayes-optimal predictions are exactly all supersets $T\\cup C$ of a fixed core set $T$ of size $\\lfloor s/3\\rfloor$; the active loss columns restricted to the support have affine dimension $hn$, where $n=s-\\lfloor s/3\\rfloor$ and $h=\\lceil\\sqrt{s\\lfloor s/3\\rfloor}\\rceil-1$. Applying the feasible-subspace lower bound for convex calibration dimension yields $\\operatorname{CCdim}(L^{F_1})\\ge hn=(2/(3\\sqrt{3})-o(1))s^2$, and with the upper bound this establishes $\\Theta(s^2)$.","pith_inferences":["The layered-core-set construction is a template: any set-similarity loss whose Bayes-optimal report is a simplex face with large active-column affine dimension should inherit a quadratic calibration-dimension lower bound.","The same factorization with a generalized Cauchy kernel may give exact-rank formulas for the asymmetric $F_\\beta$ family, a direction the paper mentions but does not pursue.","A testable extension is a trigger distribution with several interacting core sets, which could enlarge the active face beyond $hn$ and improve the constant factor toward the upper bound."],"forward_implications":["Any convex calibrated surrogate for the $s$-label $F_1$ loss must use $\\Theta(s^2)$ prediction dimensions, so the earlier $s^2+1$-coordinate constructions are essentially optimal in order.","The exact rank $s^2-s+2$ sharpens the previous $\\operatorname{rank}(L^{F_1}-J)\\le s^2+1$ and yields the affine-dimension upper bound $\\operatorname{CCdim}(L^{F_1})\\le s^2-s+1$.","Bayes-optimal $F_1$ prediction needs a quadratic number of degrees of freedom in the worst case, matching the quadratic sufficiency of plug-in statistics.","The lower bound is insensitive to the empty-set convention $F_1(\\varnothing,\\varnothing)=1$ versus $0$, because the witness distribution assigns no mass to the empty outcome.","The constant gap between $(2/(3\\sqrt{3})-o(1))s^2$ and $s^2-s+1$ remains open; the paper identifies harder trigger distributions or sub-affine surrogates as the two routes to closing it."],"supporting_citations":[{"why":"Supplies the affine-dimension upper bound and the feasible-subspace lower bound that the calibration-dimension argument invokes.","marker":"Ramaswamy and Agarwal, 2016"},{"why":"Establishes the prior shifted low-rank bound and constructs $s^2+1$-dimensional convex calibrated surrogates that the exact-rank theorem sharpens.","marker":"Zhang et al., 2020"},{"why":"Gives the $s^2+1$-coordinate affine decompositions and consistent least-squares surrogate whose optimality the new lower bound addresses.","marker":"Nowak et al., 2019"},{"why":"Shows Bayes-optimal $F_1$ prediction is computable from a quadratic number of conditional-distribution statistics, the sufficiency result the new necessity result complements.","marker":"Dembczyński et al., 2011"}],"fun_headline_variants":["F1 loss surrogates need quadratic dimension, proven","Exact rank shows F1 surrogate dimension is quadratic","Quadratic calibration dimension for F1 loss: new lower bound","F1 loss: exact rank and convex calibration dimension tight"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the imported feasible-subspace lower bound being valid for a witness distribution whose Bayes-optimal predictions are a large tied family (all supersets of a core set) rather than a unique report; if that bound requires a unique minimizer, the quadratic lower bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["F1 loss surrogates need quadratic dimension, proven","Exact rank shows F1 surrogate dimension is quadratic","Quadratic calibration dimension for F1 loss: new lower bound","F1 loss: exact rank and convex calibration dimension tight"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001075,"raw_usage":{"total_tokens":4649,"prompt_tokens":1242,"completion_tokens":3407,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":858,"completion_tokens_details":{"reasoning_tokens":3340}},"tokens_in":858,"tokens_out":3407,"duration_ms":26669,"temperature":1.0,"reasoning_tokens":3340,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:38:28.669119+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $s=3$, the rank formula predicts rank $8$ for the $8\\times 8$ $F_1$ score matrix; a direct symbolic rank computation returning any other value would refute the rank theorem. For the calibration bound (which gives $hn=2$ at $s=3$), exhibiting any convex calibrated surrogate with prediction dimension $1$ for the three-label $F_1$ loss would falsify the lower bound.","supporting_citations":[],"review_version":1}