{"id":"6d4e6656-47c0-406a-bab7-ea73efb1cbe0","arxiv_id":"2608.13549","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Exact convex calibration of the multi-label Jaccard loss requires dimension exponential in the label count, while any fixed additive regret tolerance is achievable in polynomial dimension.","lead":"For the per-instance Jaccard (intersection-over-union) loss in multi-label classification, this paper proves that any exactly calibrated convex surrogate must use a number of prediction coordinates exponential in the number of labels. It also proves that allowing a small fixed error tolerance shrinks the required dimension to polynomial, via MinHash feature maps and a transfer from F1 surrogates.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the external Ramaswamy-Agarwal inequality is the only step worth re-checking, and the local feasible-subspace argument appears sound.","rationale":"The reader's weakest assumption correctly identifies the imported Ramaswamy-Agarwal inequality as the only non-internal support of the exponential lower bound. I agree that this is the step most worth checking, but I do not find a concrete violation: the constructed p clearly belongs to the trigger set, the active-column dimension argument is complete, and the lineality computation forces v = 0. The paper's other central components, Lemma 4.1, Theorem 4.2, the factorial balancing identity, and the MinHash approximation bounds, are internally consistent and I found no algebraic or logical error. The remaining gap between 2^(s-1) and 2^s-1 is explicitly disclosed and does not affect the Theta(2^s) conclusion. Section 6's approximation results are honestly scoped as polynomial-dimensional but not exact, with the decoding-complexity limitation stated. Since the only worry is a standard external citation rather than an internal inconsistency, the reader's ACCEPT verdict should stand unchanged.","tokens_in":14885,"tokens_out":17254,"duration_ms":189166,"concrete_test":"Check the statement and hypotheses of Theorem 16 in Ramaswamy and Agarwal (2016) word-for-word against the distribution p constructed in Appendix C, verifying that p is allowed to lie on the boundary of its trigger set Q_B^L and that the lineality dimension mu is the local tangent-cone lineality defined in the paper. If the theorem applies exactly as used in Eq. (5), the lower bound is sound; if an additional relative-interior or support condition is present, re-run the lower-bound proof under the corrected definition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 5.2, whose lower bound rests on the imported inequality CCdim(L) >= ||p||_0 - mu - 1 from Ramaswamy and Agarwal (2016). The paper does not re-prove that theorem, so this is the natural place for a hidden regularity condition to break the argument. I examined the one point where such a condition could matter, the computation of mu in Appendix C. The active score submatrix is nonsingular, so the active difference space E has dimension |A|-1 and, because all active reports tie at p, E = p_A^perp. Two-sided feasible directions must vanish on A^c, be orthogonal to E, and preserve total mass; these conditions force v_A in span(p_A) and then v_A = 0 by normalization. Hence mu = 0. The application of the external theorem is explicit, the citation is standard in this line of work, and no passage in the manuscript suggests a violated hypothesis. I therefore do not regard the external dependency as a substantive flaw, but it is the single step a referee should verify against the original source.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the convex calibration dimension (CCdim) of the per-instance multi-label Jaccard loss. It proves that, under the convention Jac(∅,∅)=1, the Jaccard score matrix, the shifted-loss matrix, and the ordinary loss matrix are all nonsingular and have affine dimension 2^s−1. The main result is Theorem 5.2: 2^{s−1} ≤ CCdim(L^{Jac}) ≤ 2^s−1, so exact convex calibration requires Θ(2^s) prediction coordinates. The lower bound is obtained from a factorially weighted distribution over sets containing a core label, mixed with the empty set, and a feasible-subspace argument that gives a trivial lineality space. The paper also provides two polynomial-dimensional approximation guarantees: an F1-to-Jaccard regret transfer with asymptotic regret floor 3−2√2, and MinHash-based square-loss surrogates that achieve any fixed additive regret floor α in dimension O((s+log(1/ρ))/α^2). The paper thus establishes an exactness–dimension tradeoff.","tokens_in":15029,"tokens_out":15658,"duration_ms":150417,"significance":"If the main theorem is correct, it is a significant contribution to the theory of convex calibration. It shows that the instance-wise Jaccard loss, despite having a simple closed-form score, is substantially harder to calibrate than the F1 measure (whose calibration dimension is Θ(s^2) in related work): no convex surrogate can be exactly calibrated unless it uses exponentially many coordinates. The paper also gives constructive, distribution-free approximate surrogates with explicit regret bounds and dimension guarantees, which is practically relevant. The proofs are detailed and mostly self-contained; the two external inputs—the Ramaswamy–Agarwal lower bound and the Zhang et al. F1 surrogate—are cited precisely and appear to be used correctly. The finite MinHash Gram representation and the factorial balancing identity are elegant tools that may be of independent interest.","major_comments":[],"minor_comments":[{"comment":"The derivation of the lineality space is compressed into a single sentence ('It follows directly from the simplex constraints and the active trigger inequalities'). Since this is the crux of the exponential lower bound, I recommend spelling out the three conditions: two-sided feasibility forces v_{A^c}=0; the normalization constraint gives 1_A^T v_A=0; and preserving the active ties requires v_A ⊥ E. Then using E=p_A^⊥ yields v_A=0. This would make the proof easier to verify.","section":"Appendix C, Eq. (46)"},{"comment":"The paper relies on the unpublished preprint Zhang (2026) for the F1 calibration dimension and as a comparison baseline. The authors should indicate its preprint status (and ideally update the reference if it has been published) and confirm that its empty-set convention aligns with the convention F(∅,∅)=1 used here.","section":"Section 3 and references"},{"comment":"The link rules in (25) and (31) are defined via argmax with 'any fixed rule to break ties.' The proofs are valid for any deterministic tie-breaking rule, but it would be clearer to state explicitly that the regret bounds hold uniformly over all tie-breaking rules, so that no hidden dependence on the tie-breaking rule is introduced.","section":"Section 6.2, Theorems 6.3 and 6.4"},{"comment":"There are several typographical issues with superscripts and spacing: for example, '2 s −1' should be '2^s − 1' in the abstract and elsewhere, and 'CCdim(L Jac)' should be 'CCdim(L^{Jac})'. A careful proofreading pass would improve readability.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically sound and the central results are correct as far as I can verify. The main external dependency is the Ramaswamy–Agarwal inequality; I found the application to the constructed witness distribution and the feasible-subspace computation to be correct, so this is not a substantive concern. One thing to watch is that the paper cites an unpublished arXiv preprint by the same author (Zhang 2026) for the F1 counterpart; this is not a fatal issue, but the editor may want to consider whether the comparison rests on sufficiently solid ground. Overall, the paper is a good fit for a machine learning theory journal and, after minor revisions addressing clarity and the status of the cited preprint, should be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — the headline is that this paper proves a clean exponential lower bound on the exact convex calibration dimension of the per-instance Jaccard loss: 2^{s-1} <= CCdim <= 2^s - 1. That's new and it's the main thing to know. The upper bound comes from affine dimension, while the lower bound uses a factorial witness distribution that forces 2^{s-1}+1 Bayes-optimal reports to tie, then shows the two-sided feasible subspace is trivial. I checked the balancing identity, the active-submatrix argument, and the mu = 0 computation; all hold. The paper also pins down the rank and affine dimension under the Jac(empty,empty)=1 convention via a MinHash Gram matrix plus Boolean Mobius inversion, which is a cleaner proof than the earlier infinite positive-definite decomposition. The two approximation results are genuinely useful context: an F1-to-Jaccard transfer with constant 3-2*sqrt(2), and MinHash square-loss surrogates with polynomial dimension for any fixed regret floor. The MinHash analysis is honest that the link still maximizes over 2^s reports, so this is a prediction-dimension theorem, not a tractable-inference one.\n\nSoft spots: the lower bound imports the Ramaswamy-Agarwal inequality CCdim(L) >= ||p||_0 - mu - 1, and the paper does not re-prove it. I don't see evidence that the theorem fails for this trigger set; the stress-test's local check of mu is sound. But a referee should verify the regularity conditions against the original source. Minor: the factor-of-two gap remains, and the exact value of CCdim is open; the authors say so. The F1-transfer result depends on the published Zhang-Ramaswamy-Agarwal surrogate, which is fine. The paper also cites a companion F1 paper (Zhang 2026) for the quadratic CCdim of F1; that seems appropriate, but a reviewer may want to confirm that result is real or in press.\n\nThe empty-set convention deserves attention: the exponential conclusion survives under Jac(empty,empty)=0, but the lower bound shifts to 2^{s-1}-1, so the headline constant depends on a convention choice. That's not a flaw, but it should be stated loudly, and it is in the appendix.\n\nVerdict: this is a real result with complete proofs, a clear related-work section, and no red flags in the citation pattern. The external dependency is the only thing I'd want a careful referee to check. I'd bring it to reading group and would cite it. Send it to peer review.","headline":"This paper's exponential lower bound on the exact convex calibration dimension of the Jaccard loss is new, well-proven, and worth refereeing carefully.","tokens_in":15588,"tokens_out":1813,"would_cite":true,"duration_ms":18000,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact convex calibration of the multi-label Jaccard loss requires exponentially many prediction coordinates.","keywords":["multi-label classification","Jaccard loss","intersection over union","convex calibration dimension","loss-matrix rank","approximate consistency","MinHash random features","F-measure"],"falsifier":"Evaluate the theorem for $s=2$, where it claims $2 \\leq \\mathrm{CCdim}(L^{\\mathrm{Jac}}) \\leq 3$ on a $4 \\times 4$ loss matrix: an exhaustive computer search over convex surrogate-link pairs in one real dimension would either find an exactly calibrated one-dimensional surrogate, refuting the lower bound, or confirm the bound. A cheaper check is to test whether the witness $p$ defined in Eq. (42) lies in the relative interior of its trigger set; the external lower-bound inequality used in the proof may require an interior point, and if $p$ lies on a face the $2^{s-1}$ claim collapses.","tokens_in":14634,"feed_emoji":"🎯","tokens_out":9826,"duration_ms":89774,"temperature":0.7,"pith_summary":"The paper studies the per-instance Jaccard score (intersection over union) as a multi-label loss and asks how many real-valued prediction coordinates a convex surrogate must have to be exactly calibrated over all conditional label distributions. Its main theorem states that this convex calibration dimension is exponential in the number of labels: $2^{s-1} \\leq \\mathrm{CCdim}(L^{\\mathrm{Jac}}) \\leq 2^s - 1$ for $s$ labels, under the convention $\\mathrm{Jac}(\\varnothing,\\varnothing)=1$. Along the way it proves that the Jaccard score, shifted-loss, and ordinary loss matrices have full rank $2^s$ and affine dimension $2^s - 1$. The paper also shows a sharp contrast: approximate prediction with any fixed additive regret tolerance is possible in polynomial dimension, via an $F_1$-to-Jaccard regret transfer and MinHash random-feature surrogates.","feed_headline":"Multi-label Jaccard exactness needs exponential coordinates","feed_subtitle":"A new theorem puts convex calibration dimension between 2^(s−1) and 2^s − 1, while fixed tolerance stays polynomial.","key_machinery":"The load-bearing construction is the factorially weighted witness distribution $q$ on the family $U = \\{\\{1\\}\\cup D : D \\subseteq [s]\\setminus\\{1\\}\\}$, assigning weight proportional to $1/|D|!$ to outcome $\\{1\\}\\cup D$. The factorial-balancing identity of Lemma 5.1 makes the expected Jaccard score of every report in $U$ equal to a common constant $\\kappa$; mixing $q$ with the empty outcome makes the empty report tie as well, producing a set $A$ of $2^{s-1}+1$ tied Bayes-optimal reports. The active score submatrix indexed by $A$ is $\\mathrm{diag}(1, S_{U,U})$, nonsingular by the MinHash Gram representation and Boolean Möbius inversion (which together prove the full Jaccard matrix is positive definite), so the relevant difference span is the whole orthogonal hyperplane and the two-sided feasible subspace is zero-dimensional; the lower-bound inequality then yields the exponential bound. The MinHash feature map $\\Phi(A)$, whose inner product is the empirical collision probability of random permutations, carries the approximation results.","core_discovery":"The central discovery is that exact convex calibration of the per-instance Jaccard loss is exponentially harder in terms of prediction dimension than its polynomial-sized output space might suggest. Every exactly calibrated convex surrogate must use at least $2^{s-1}$ real-valued coordinates, and an affine surrogate with $2^s - 1$ coordinates suffices, so $\\mathrm{CCdim}(L^{\\mathrm{Jac}}) = \\Theta(2^s)$. The proof constructs a factorially weighted distribution over the $2^{s-1}+1$ outcomes consisting of the empty set and all sets containing a fixed core label; a combinatorial identity makes all corresponding Bayes-optimal reports tie exactly, the active score submatrix is nonsingular, and the two-sided feasible subspace is trivial, triggering a known lower-bound inequality from convex calibration theory. The same paper establishes that the Jaccard score and loss matrices have maximal rank and column-affine dimension, and gives two polynomial-dimensional approximation routes: an $F_1$-to-Jaccard transfer yielding asymptotic regret at most $3-2\\sqrt{2}$, and MinHash square-loss surrogates that are $\\alpha$-approximately consistent in dimension $O((s^2 + s\\log(1/\\rho))/\\alpha^2)$ or $O((s + \\log(1/\\rho))/\\alpha^2)$.","pith_inferences":["The factor-of-two gap between the bounds suggests the true value of $\\mathrm{CCdim}(L^{\\mathrm{Jac}})$ may be $2^s - 1$, matching the affine-dimension upper bound; extending the factorial witness to a full-support distribution with zero lineality would close the gap.","The $O(s/\\alpha^2)$ dimension of the signed MinHash surrogate matches the parametric rate for estimating an $s$-dimensional structure, hinting that the $\\alpha$-approximate dimension may be $\\Omega(s/\\alpha^2)$ and that the exponential cost is an artifact of requiring exactly zero regret.","The factorial-balancing tie construction is a promising template for establishing exponential calibration dimension for other nondecomposable ratio losses, such as Dice or Tversky, whose loss matrices have similar combinatorial structure.","The MinHash surrogate's dimension bound is derived via uniform approximation of the entire score matrix; a data-dependent or Laplacian analysis could reduce the $\\log(1/\\rho)$ factor or the $4^s$ union-bound cost."],"forward_implications":["Every exactly calibrated convex surrogate for the per-instance Jaccard loss uses at least $2^{s-1}$ real-valued coordinates; in particular no polynomial-dimensional convex surrogate can be exactly calibrated over all conditional distributions.","The Jaccard score, shifted-loss, and ordinary loss matrices are nonsingular and the loss columns have affine dimension $2^s - 1$, so an affine surrogate in $2^s - 1$ dimensions achieves exact calibration.","An $F_1$-Bayes classifier has worst-case asymptotic Jaccard regret at most $3 - 2\\sqrt{2} \\approx 0.1716$, and any $F_1$-calibrated surrogate inherits this constant regret floor for Jaccard.","For any tolerance $\\alpha > 0$ and confidence $\\rho$, the MinHash square-loss surrogate is $\\alpha$-approximately consistent in dimension $O((s^2 + s\\log(1/\\rho))/\\alpha^2)$, and the signed variant in $O((s + \\log(1/\\rho))/\\alpha^2)$.","Zero-regret prediction requires exponential dimension, while every fixed additive regret tolerance admits polynomial dimension, so the exponential lower bound is specific to exact calibration."],"supporting_citations":[{"why":"Supplies the convex calibration dimension definition and the two inequalities that yield the upper bound and the exponential lower bound.","marker":"Ramaswamy and Agarwal (2016)"},{"why":"Gives the MinHash collision identity used to represent the Jaccard matrix as a Gram matrix and to build the random-feature surrogates.","marker":"Broder (1997)"},{"why":"Proved the strict positive definiteness of the Jaccard index matrix that the paper reproves finitely and uses for the rank and affine-dimension results.","marker":"Bouchard et al. (2013)"},{"why":"Provides the quadratic-dimensional convex calibrated $F_1$ surrogate and polynomial-time link that the $F_1$-to-Jaccard transfer turns into a constant-floor Jaccard rule.","marker":"Zhang et al. (2020)"},{"why":"Established the earlier $F_1$-to-Jaccard Bayes-optimality bound that Proposition 6.1 refines and matches to the aligned empty-set convention.","marker":"Waegeman et al. (2014)"},{"why":"Gives the $F_1$ loss rank and $\\Theta(s^2)$ calibration dimension, the quadratic comparison that sets off the exponential Jaccard result.","marker":"Zhang (2026)"}],"fun_headline_variants":["Exact Jaccard calibration is exponentially costly","Zero Jaccard regret requires 2^s dimensions, but epsilon is easy","Jaccard convex surrogates: exactness is exponential, tolerance is polynomial","Calibrating Jaccard: exponential dimension for exact, polynomial for approximate","Jaccard loss: exact calibration exponential, fixed error polynomial"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exponential lower bound depends on an external theorem that says the convex calibration dimension is at least the number of supported outcomes minus the dimension of two-sided feasible directions minus one; the paper applies that theorem to its factorial tied-report witness without re-proving it or checking its regularity hypotheses at that boundary point.","fun_headline_variants_meta":{"raw":{"variants":["Exact Jaccard calibration is exponentially costly","Zero Jaccard regret requires 2^s dimensions, but epsilon is easy","Jaccard convex surrogates: exactness is exponential, tolerance is polynomial","Calibrating Jaccard: exponential dimension for exact, polynomial for approximate","Jaccard loss: exact calibration exponential, fixed error polynomial"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000566,"raw_usage":{"total_tokens":2794,"prompt_tokens":1167,"completion_tokens":1627,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":783,"completion_tokens_details":{"reasoning_tokens":1533}},"tokens_in":783,"tokens_out":1627,"duration_ms":12584,"temperature":1.0,"reasoning_tokens":1533,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:22:11.364126+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Evaluate the theorem for $s=2$, where it claims $2 \\leq \\mathrm{CCdim}(L^{\\mathrm{Jac}}) \\leq 3$ on a $4 \\times 4$ loss matrix: an exhaustive computer search over convex surrogate-link pairs in one real dimension would either find an exactly calibrated one-dimensional surrogate, refuting the lower bound, or confirm the bound. A cheaper check is to test whether the witness $p$ defined in Eq. (42) lies in the relative interior of its trigger set; the external lower-bound inequality used in the proof may require an interior point, and if $p$ lies on a face the $2^{s-1}$ claim collapses.","supporting_citations":[{"cited_title":"A proof for the positive definiteness of the Jaccard index matrix","cited_arxiv_id":null,"evidence_quote":"Proved the strict positive definiteness of the Jaccard index matrix that the paper reproves finitely and uses for the rank and affine-dimension results."},{"cited_title":"Ramaswamy, and Shivani Agarwal","cited_arxiv_id":null,"evidence_quote":"Provides the quadratic-dimensional convex calibrated $F_1$ surrogate and polynomial-time link that the $F_1$-to-Jaccard transfer turns into a constant-floor Jaccard rule."},{"cited_title":"On the Bayes-optimality of F-measure maximizers","cited_arxiv_id":null,"evidence_quote":"Established the earlier $F_1$-to-Jaccard Bayes-optimality bound that Proposition 6.1 refines and matches to the aligned empty-set convention."},{"cited_title":"Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss","cited_arxiv_id":"2608.08399","evidence_quote":"Gives the $F_1$ loss rank and $\\Theta(s^2)$ calibration dimension, the quadratic comparison that sets off the exponential Jaccard result."}],"review_version":1}