{"id":"a72e9e47-c4df-4b07-92ed-96d256d1c792","arxiv_id":"2608.10869","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"partial","parameter_count":0,"one_line_summary":"For multiclass PAC learning, the optimal excess risk at any fixed oracle error L* equals the square root of L* times the Natarajan dimension over n, plus the realizable DS-dimension rate, with matching upper and lower bounds.","lead":"Multiclass learning now has a single formula describing how much extra error a learner pays at every level of difficulty, from perfectly realizable data to fully noisy data. The proof closes an open gap in statistical learning theory and ships with machine-checked Lean 4 certificates for its main theorems.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The d_DS/n term in Theorem 3.1 rests on unformalized imported preprints; the unconditional Θ̃ characterization is not fully certified by the Lean formalization alone.","rationale":"The paper's internal logic appears sound: the selective-menu identity, the coefficient-one transfer, and the relative-compression theorem (Theorem 3.3) are coherent, and the three-block assembly correctly separates the d_DS coverage charge from the d_N localized fluctuation. The machine-checked lower bound is a strong positive. The remaining uncertainty is the conditional nature of the upper bound: the formalization treats the imported results from very recent preprints as hypotheses, so the unconditional claim in Theorem 3.1 is not fully certified. This is exactly the reader's weakest assumption. The lower bound's import of the BCD+22 separation family is less concerning because it is from a peer-reviewed source and is checked at D = 2, but it is still not formalized for arbitrary D. Since the reader already disclosed and weighed these caveats, my read does not change the verdict: the concern would only move the assessment if one of the imported lemmas were actually found to fail. The proposed check targets the most specific and load-bearing import, the fixed-menu compressor, whose correctness is essential to the d_N-localized term.","tokens_in":45907,"tokens_out":19229,"duration_ms":186319,"concrete_test":"Independently re-derive [CEH+26, Prop. 3.6] under the exact conventions used in Lemma A.5 (deterministic p-menu, ordered messages with repeated indices, p only an upper bound on menu width, empirical domination against every h in H under ℓ_μ), and verify the size bound C d_N log p log(eN) for every fixed p ≥ 2. If the source construction requires the exact menu supremum, or introduces an alphabet-dependent factor, then Lemma A.5 is inapplicable and the d_N-localized term of Theorem 3.1 is unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing soft spot is the unverified import chain behind Theorem 3.1. Appendix D states explicitly that the six imported results from [Pab26] and [CEH+26] enter the Lean formalization rmc_master as per-block hypotheses, not as proved facts. The realizable-order d_DS/n term depends on [Pab26, Cor. 1.1] through Lemma A.1; the correct-region cover and menu guarantees are imported as Lemmas A.3 and A.4; and the localized d_N term requires the fixed-menu compressor of Lemma A.5, whose size bound C d_N log p log(eN) and empirical-domination property are inherited from [CEH+26, Prop. 3.6]. Each of these is from a very recent source, and a convention mismatch would break the composition even though the relative-compression theorem and the assembly steps are machine-checked. The lower bound's Lemma 4.2 (pseudo-cube with Nat ≤ 1) is likewise only discharged at D = 2. Thus the unconditional two-parameter rate is not fully established by the formalization on its own.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves an optimistic-rate characterization for multiclass PAC learning. For a class with Natarajan dimension d_N and DS dimension d_DS, it gives a learner RMC whose excess risk over the oracle risk L* is Õ(√(L* d_N/n) + d_DS/n) at every fixed L*, with no knowledge of L* or δ (Theorem 3.1), and a matching lower bound forcing both terms simultaneously in one class and one distribution at every L* (Theorem 4.1). The upper bound is assembled from a compression cover, a learned menu, and a new comparator-facing relative compression theorem (Theorem 3.3) that compares an empirical-risk-dominating compression rule to a fixed comparator with coefficient one on the comparator risk, without a stability assumption. The lower bound combines a noisy pair-Assouad construction calibrated to L* with a fiber/leave-one-out argument on separation pseudo-cubes. Section 5 extends both directions to list learning, giving optimistic rates against the best r-tuple and a realizable list lower bound without the factor r. Appendices supply proof details, and Section D documents a Lean 4 formalization covering Theorem 3.3, the assembly behind Theorem 3.1 (with imported modules as hypotheses), and Theorem 4.1, except that Lemma 4.2 is fully discharged only at D = 2.","tokens_in":46063,"tokens_out":28693,"duration_ms":268794,"significance":"Assuming the imported results from [Pab26] and [CEH+26] are correct, this is a substantial contribution: it closes the interpolation gap between the known realizable and agnostic multiclass rates, and it does so with a parameter-free learner and explicit constants rather than fitted parameters. The conceptual separation of the DS dimension as a coverage cost and the Natarajan dimension as a localized fluctuation is clean and is certified by a lower bound that activates both dimensions under one distribution. The paper ships machine-checked proofs (no sorry, no ad-hoc axioms) for the relative compression theorem and the lower-bound assembly, and it is unusually transparent about which parts of the upper bound are formalized relative to imported statements. The list-learning extension and the removal of the factor r from the realizable list lower bound are interesting byproducts. The main caveat is dependency on very recent preprints, but the manuscript restates the imported modules with source locators and convention checks.","major_comments":[],"minor_comments":[{"comment":"The displayed bound for d_RE(H) is inconsistent with the substitution in its proof: using the source sample-size bound (9.64 d_DS + log(2/δ0))/ε0 with ε0 = δ0 = 1/(18e) gives d_RE(H) ≤ ⌈9.64(18e)d_DS + 18e log(36e)⌉, whereas the printed expression appears to decay in d_DS and would be false for d_DS ≥ 4. Please correct the display; the subsequent O(d_DS) conclusion is unaffected.","section":"Appendix A.1 (Lemma A.1)"},{"comment":"The phrase \"main theorems are machine-checked\" is stronger than the certificate: in the Lean formalization, rmc_master imports the six results from [Pab26] and [CEH+26] as per-block hypotheses, the final bookkeeping from (a1, a2, Γ) to the rate (3.1) is not formalized, and Lemma 4.2 is fully discharged only at D = 2. Section D already says this, but the abstract should not imply a fully unconditional formal certificate for Theorem 3.1.","section":"Abstract and Section D"},{"comment":"The notation (X, X) uses the same symbol for the input space and its sigma-algebra; please use a distinct symbol, for example (𝒳, Σ), to avoid confusion with the pointwise loss and the label notation.","section":"Section 2.1"},{"comment":"The lower-bound family's label alphabet grows with d_DS/d_N through the [BCD+22] separation family, so the quantification \"there are a finite label set [K]\" in Theorem 4.1 should state explicitly that K is allowed to depend on (d_N, d_DS); Remark 4.6 explains why this is necessary, but the theorem statement currently leaves the dependence implicit.","section":"Theorem 4.1 and Remark 4.6"}],"recommendation":"minor_revision","confidential_remarks":"The paper depends heavily on several very recent preprints ([Pab26], [CEH+26], and the separation result of [BCD+22]); the editor may wish to confirm that these are publicly available and stable before final acceptance. The formalization is a genuine strength, but it is conditional on those imports, and the authors have been transparent about this. I see no evidence of circular reasoning or fitted parameters; the disagreements with existing worst-case bounds are properly framed as interpolations rather than contradictions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper closes a real open gap—the optimistic multiclass rate at every fixed oracle risk L*—and backs it with a serious partial formalization. I'd send it out.\n\nWhat's new: the paper proves the optimal excess-risk scale Θ̃(√(L* d_N/n) + d_DS/n) uniformly in the alphabet size, interpolating between the known realizable d_DS/n and agnostic √(d_N/n)+d_DS/n endpoints. That interpolation was genuinely open, and the paper explains why the binary proof does not lift: the Boolean-cube geometry is replaced by a comparator-facing relative compression theorem that needs no stability. The lower bound is also a real step up: one class, one distribution forces both terms at every fixed L*, using a pair-Assouad construction plus a fiber argument on pseudo-cubes. The list-learning extension and the removal of the factor r in the realizable list lower bound are useful byproducts, though the list part is not formalized.\n\nWhat the paper does well beyond the math: it is unusually honest about what is imported. The Lean 4 formalization checks Theorem 4.1 end to end with no sorries, and Theorem 3.1 is checked conditional on six imported lemmas from [Pab26] and [CEH+26], which are stated explicitly as hypotheses in the formal development. The repo has no commit hash, but the disclosure is clear.\n\nThe soft spots are real but proportionate. The upper bound's d_DS term sits on very recent preprints that are not yet independently verified, and a convention mismatch in any one of those imports would break the composition even though the local assembly is machine-checked. The lower-bound separation pseudo-cube of [BCD+22] is also imported except at D=2. None of this is hidden, and none of it looks like a fatal flaw: the imported claims are plausible, the restated forms are precise, and the central rate is the natural answer. The unformalized list extension and missing commit hash are minor.\n\nWho is this for? Anyone working on multiclass sample complexity, compression-based bounds, or formalized learning theory. The relative compression theorem is a reusable tool even if the imported lemmas later need patching.\n\nRecommendation: send it to a serious referee. The referee should be asked to check the import chain from [CEH+26] and [Pab26] carefully, and to verify that the Lean statement of Theorem 3.1 really matches the prose when the imported hypotheses are discharged.","headline":"Resolves the open optimistic-rate interpolation for multiclass PAC learning with matching upper and lower bounds and a genuine partial Lean formalization; the main caveat is a disclosed dependence on very recent imported preprints.","tokens_in":46649,"tokens_out":1129,"would_cite":true,"duration_ms":14413,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes that at every fixed oracle risk $L^\\star$, the optimal excess risk for a multiclass class is $\\widetilde{\\Theta}(\\sqrt{L^\\star d_N/n}+d_{DS}/n)$, with both terms forced by one class and one distribution.","keywords":["multiclass PAC learning","optimistic rates","Natarajan dimension","DS dimension","sample compression","cover-menu-compression","list learning","lower bounds"],"falsifier":"Search for a finite class and a distribution with oracle risk exactly $L^\\star$ where a learner's expected excess risk is below $\\frac{1}{12}\\sqrt{L^\\star d_N/n}+\\frac{1}{15}\\min\\{d_{DS}/n,1/4\\}$ for infinitely many $n$, or demonstrate that one of the imported compression/cover lemmas fails on a concrete class; either observation would refute the claimed optimal rate.","tokens_in":45665,"feed_emoji":"🎯","tokens_out":12874,"duration_ms":104623,"temperature":0.7,"pith_summary":"Multiclass PAC learning is known at two extremes: realizable classes learn at $d_{DS}/n$, while fully agnostic classes pay $\\sqrt{d_N/n}+d_{DS}/n$. This paper closes the gap by showing that at every fixed oracle risk $L^\\star$ the optimal excess risk is $\\widetilde{\\Theta}(\\sqrt{L^\\star d_N/n}+d_{DS}/n)$, uniformly in the label alphabet size. The upper bound is attained by a parameter-free learner that knows neither $L^\\star$ nor the confidence level, and the lower bound forces both terms at once on one class and one distribution. If the result is correct, the interpolation is intrinsic: the DS dimension pays for making correct labels visible, while the Natarajan dimension controls fluctuations that shrink with the oracle error.","feed_headline":"One formula fixes optimal multiclass rates at every oracle risk","feed_subtitle":"No learner can beat this rate, and a single algorithm reaches it without knowing the oracle error or the confidence level.","key_machinery":"The load-bearing mechanism is a learned menu $\\mu$, a map from points to short lists of candidate labels, which converts multiclass prediction into a selective binary problem. The selective-menu decomposition $\\mathbf{L}_D(g)-\\mathbf{L}_D(h)\\le \\mathbf{L}_\\mu(g)-\\mathbf{L}_\\mu(h)+\\alpha_\\mu(h)$ separates the two error sources: $d_{DS}$ controls the probability that a correct label is missing from the menu, and $d_N$ controls the description length of the rule chosen inside the frozen menu. The new engine of the upper bound is the comparator-facing relative compression theorem: a deterministic size-$k$ rule that empirically dominates a fixed comparator $h$ has population risk at most $L(h)+O(\\sqrt{L(h)\\Gamma}+\\Gamma)$ with $\\Gamma=(k\\log n+\\log(1/\\delta))/n$, with no stability assumption. The lower bound is carried by a noisy pair-Assouad scheme calibrated to $L^\\star$ on a Natarajan cube and a fiber lemma that makes every unseen coordinate of a pseudo-cube ambiguous, forcing the $d_{DS}/n$ coverage term.","core_discovery":"The paper claims that multiclass classification has a single two-dimensional optimistic rate: for any class of Natarajan dimension $d_N$ and DS dimension $d_{DS}$, at every fixed oracle risk $L^\\star$ the optimal excess risk is $\\widetilde{\\Theta}(\\sqrt{L^\\star d_N/n}+d_{DS}/n)$, uniformly in the alphabet size. The upper bound is achieved by a three-block learner that constructs a compression cover of size roughly $d_{DS}\\log^2 n$, learns a menu of candidate labels, and then applies a new comparator-facing relative compression inequality; the learner does not know $L^\\star$ or $\\delta$. The matching lower bound produces one class and one distribution at every $L^\\star$ that force every learner to pay both terms, combining a noisy Natarajan cube with a Natarajan-free pseudo-cube. The same two engines extend to list learning, where they yield an optimistic rate against the best $r$-tuple of hypotheses and remove a factor $r$ from the known realizable list lower bound.","pith_inferences":["The relative compression theorem is modular: replacing the imported cover or menu bounds by sharper ones would immediately sharpen the final rate, so the theorem functions as an interface as much as a result.","The proof's uniformity in the alphabet size suggests the two-dimensional rate could survive very large label sets, provided a realizable learner with finite DS dimension exists; the paper explicitly leaves infinite alphabets open.","The calibration trick of padding a noisy lower-bound family with realizable mass so the oracle risk lands exactly on $L^\\star$ could be reused to build exact-fixed-risk lower bounds for other structured learning problems.","A cross-fitting variant of the three blocks might reduce the sample split, but the coefficient-one comparison relies on freezing the menu before the final sample, so any such variant would need new independence arguments."],"forward_implications":["At $L^\\star=0$ the formula collapses to the realizable rate $d_{DS}/n$; at constant $L^\\star$ it becomes $\\sqrt{d_N/n}+d_{DS}/n$, so both previously known endpoints are special cases of one bound.","A single learner, independent of $L^\\star$ and $\\delta$, attains the upper bound at every oracle level, so no meta-selection over error targets is needed.","The sample-complexity form $n=\\widetilde{O}(L^\\star(d_N+\\log(1/\\delta))/\\epsilon^2+(d_{DS}+\\log(1/\\delta))/\\epsilon)$ makes the allocation explicit: first resolve in-menu fluctuations at scale $L^\\star$, then make correct labels visible.","The matching lower bound shows both terms are unavoidable at every fixed $L^\\star$ on the same class and distribution, so the two-dimensional split is a property of multiclass learning and not an artifact of the analysis.","For list learners, the same architecture and lower-bound engines hold against the best $r$-tuple of hypotheses, with the same two-term shape and a factor-$r$ improvement in the realizable list lower bound."],"supporting_citations":[{"why":"Supplies the cover–menu–compression architecture, the finite-family menu algorithm, and the fixed-menu compressor that blocks 1–3 compose.","marker":"[CEH+26]"},{"why":"Provides the DS-to-realizable-dimension bridge (Corollary 1.1) that sharpens block 1 and sets the realizable end-point rate.","marker":"[Pab26]"},{"why":"Constructs the Natarajan-free pseudo-cube family used in Lemma 4.2 to force the DS coverage term.","marker":"[BCD+22]"},{"why":"Contributes the coefficient-one comparison principle that Theorem 3.3 transfers to multiclass menus without Boolean-cube geometry.","marker":"[MQZ26]"},{"why":"Supplies the realizable list lower bound with a factor r that Corollary 5.3 removes, and part of the endpoint context.","marker":"[HMZ24]"},{"why":"Characterizes list learnability and supplies the r-DS dimension framework used in the list extension.","marker":"[CP23]"},{"why":"Provides the binary pair-Assouad / fixed-risk lower-bound method that Lemma B.1 transplants to multiclass labels.","marker":"[DL95]"}],"fun_headline_variants":["Optimal multiclass rate at every oracle error","One formula fixes optimistic rates for all L*","Blind optimality: no L* or confidence needed","List learning too: optimistic rates, no factor r","Sharp optimistic bound: sqrt(L d_N)/n + d_DS/n"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The upper-bound proof leans on three recently claimed helper results about sample compression and menu construction; if any of those helpers is wrong or does not apply under the paper's conventions, the main upper bound fails even though the surrounding argument is machine-checked.","fun_headline_variants_meta":{"raw":{"variants":["Optimal multiclass rate at every oracle error","One formula fixes optimistic rates for all L*","Blind optimality: no L* or confidence needed","List learning too: optimistic rates, no factor r","Sharp optimistic bound: sqrt(L d_N)/n + d_DS/n"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000404,"raw_usage":{"total_tokens":2212,"prompt_tokens":1160,"completion_tokens":1052,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":776,"completion_tokens_details":{"reasoning_tokens":972}},"tokens_in":776,"tokens_out":1052,"duration_ms":10314,"temperature":1.0,"reasoning_tokens":972,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:23:50.400703+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search for a finite class and a distribution with oracle risk exactly $L^\\star$ where a learner's expected excess risk is below $\\frac{1}{12}\\sqrt{L^\\star d_N/n}+\\frac{1}{15}\\min\\{d_{DS}/n,1/4\\}$ for infinitely many $n$, or demonstrate that one of the imported compression/cover lemmas fails on a concrete class; either observation would refute the claimed optimal rate.","supporting_citations":[],"review_version":1}