{"id":"2d6120dc-b900-4eb1-bb9a-a7dbc18007b9","arxiv_id":"2602.23128","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"A disagreement-based certificate bounds any model's true risk by adding a concentration bound on unlabeled-data disagreement to a certified surrogate's risk.","lead":"This paper proves new bounds on how much a complex model's error can differ from a simpler 'surrogate' model's error, measured by how often the two disagree on unlabeled data. Because the simpler model can be certified with existing theory, the complex model inherits a practical, non-vacuous generalization certificate without being retrained.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Use case #2's 'simultaneously for all h' bound (Eq. 4) is not derivable by union bound over an infinite/continuous hypothesis class; as stated it has no valid uniform guarantee, so the distillation experiments in §4.2 are not covered by the theorems.","rationale":"The reader's weakest_assumption—the uniform 'all h∈H' step in Eq. (4)—is exactly the load-bearing point I would stress. The core Theorems 4–6 are, as far as I can see, correct for fixed f,h (or fixed Q), and Theorem 4's use of Langford's bound is standard. The advertised ability to certify a surrogate selected/trained on U depends on Eq. (4). But Eq. (4) is asserted with no complexity or prior term for the disagreement event, and the phrase 'union bound over all h∈H' does not work for continuous H. The paper's model-compression class HC is countable, so a repair with a code-length prior 2^{−l_C(h)} is plausible, but that repair is absent; as stated, Section 4.2's distillation certificates have no theorem. This is a correctness risk in the central claim, not just a looseness issue. I also note the independence problem flagged by the reader: §4.1 explicitly trains targets on the whole training set while U is carved from that set; this makes Tables 2–3 empirical certificates formally unsupported. That is a second, distinct reason the current manuscript is conditional. Because the core disagreement bounds and use case #1 appear sound, and both issues are fixable (hold out U before training; add a proper prior/countable-class union bound), the appropriate verdict remains CONDITIONAL, as the reader concluded. No adjustment needed.","tokens_in":31236,"tokens_out":11318,"duration_ms":106452,"concrete_test":"Independently re-derive Eq. (4) from Theorem 5 and Eq. (2) using a union bound, with H instantiated by all binary functions on [0,1] and D uniform; for f≡1 and any U of size m, choose h_U with h_U(x)=1 on U and h_U(x)=0 elsewhere. Then d_U(f,h_U)=0 but R_D(f)=0, R_D(h_U)=1/2, so the claimed uniform event fails for every U. Repeat with H restricted to a finite class or to the countable model-compression class HC with prior Q(h)∝2^{−l_C(h)} and confidence δQ(h); verify whether Eq. (4) becomes valid and whether the distillation bounds in Table 6 degrade accordingly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Equation (4) claims that, with probability at least 1−2δ over S and U, a single disagreement bound holds simultaneously for all h∈H, and says this follows 'by applying Eq. (1) with a union bound over all h∈H.' That step is only valid for a countable H equipped with a data-independent prior probability mass Q(h), with the confidence for h set to δQ(h) so the union bound sums to δ. The theorem states no such condition; H is the unrestricted hypothesis class of continuous-parameter networks. For uncountable H, the event 'Theorem 5 holds for h' does not have a well-defined union bound, and if H is the set of all binary classifiers, for any f and any U there exists h that agrees with f on U (so d_U=0) but has true disagreement 1/2 with f; hence the claimed simultaneous bound cannot hold with probability 1−δ. Since §4.2 trains/selects SubLoRA models on U (distillation), the selected h⋆ is not covered by the fixed-predictor Theorem 5; Eq. (4) was supposed to bridge this, but it is unsupported. Thus the model-distillation experiments are not covered by the stated theorems as written. (Separate protocol concern: §4.1 trains the target on the whole training set, including the carved-out U, so U is not independent of f; Tables 2–3 also rest on an unstated independence assumption.)","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a framework for bounding the true risk of an arbitrary target classifier f by combining (i) a risk bound for a 'surrogate' h that comes from an existing certification framework (sample compression, model compression, PAC-Bayes) and (ii) a concentration inequality on the disagreement between f and h measured on an unlabeled set U. Three disagreement bounds are stated: Theorem 4 for the 0-1 loss using Langford's binomial test-set bound; Theorem 5 for Lipschitz losses using a Chernoff/kl bound; and Theorem 6 for bounded non-Lipschitz losses using a labeled held-out set. The paper describes three use cases (fixed surrogate, surrogate selected/trained on U, and risk-gap certificate) and reports experiments on MNIST, CIFAR-10, and Amazon polarity, claiming tighter non-vacuous bounds than norm-based and partition-based baselines. The central claim is that the resulting certificates are fully computable, non-vacuous, and apply to any predictor without modifying its architecture or training procedure.","tokens_in":31658,"tokens_out":8574,"duration_ms":80122,"significance":"The decomposition idea is attractive and, if the technical gaps were repaired, would be a useful contribution: it decouples the complexity of the target from the certificate and reduces the problem to finding a close, certifiable surrogate. Theorems 4-6 are short, correct applications of standard concentration inequalities for a fixed surrogate independent of U, and the paper's breadth—three surrogate frameworks, three datasets, and released code—is a genuine strength. However, the invalid uniform bound in Eq. (4) and the unresolved independence of U from the target in Section 4.1 currently prevent the paper from substantiating its strongest claims. I regard these as fixable within the scope of a revision, not as fatal flaws.","major_comments":[{"comment":"The claimed 'simultaneously for all h∈H' bound is not derivable by the stated union bound. H is the unrestricted continuous-parameter hypothesis class of networks, and Theorem 5 contains no complexity, prior, or countable-cover term. A union bound requires a countable family or a data-independent prior Q(h) with ∑_h Q(h)≤1 and per-h failure probability δQ(h). As written, Eq. (4) is unsupported: for the class of all binary classifiers and a non-atomic D, for any f and any finite U there exists an h that agrees with f on U but has true disagreement 1/2, so the uniform statement cannot hold. Since §4.2 trains/selects the SubLoRA surrogate on U and relies on Eq. (4), the distillation results (Table 6, Table S4) are not covered by the stated theorems.","section":"§3, Use case #2, Eq. (4)"},{"comment":"The independence of U from f is not established. The text states the target models are 'trained on the whole training set', while the experimental protocol carves a validation set and a disagreement set out of the same training set. If U contains training examples of f, the events in Theorem 4 (and Theorem 6's labeled set L) are not sampled independently of f, and the high-probability guarantees do not apply. Theorem 6 explicitly requires L to be removed before training f. The authors must clarify the actual data split; if the target is trained on the complement of U and the validation set, the phrase 'whole training set' is wrong, and if it is not, Tables 2–5 are not covered. This is load-bearing for all Section 4.1 certificates.","section":"§4.1, experimental protocol"}],"minor_comments":[{"comment":"The left side of Eq. (2) should read L_D(h), not L_D(f). As printed, Eq. (2) would already bound the target's risk without any disagreement term, which contradicts the surrounding text.","section":"Eq. (2)"},{"comment":"The text says the cross-entropy loss is bounded by ln(10^3/C), approximately 9.21 for C=10; from Definition S2 the bound is ln(C/α)=ln(10^4)≈9.21 with α=10^-3. The displayed formula appears to contain a typo.","section":"Section 4, smoothed softmax bound"},{"comment":"Minor grammar: 'and evaluating our disagreement bound on an unlabeled dataset' should be 'and evaluate' or 'by evaluating'.","section":"Abstract"},{"comment":"The 'BOUND SKETCH' block is not a formal theorem; consider labeling it as an informal schematic to avoid confusion with Theorems 4–6.","section":"§3, Bound Sketch"},{"comment":"The notation δQ(h) is never defined. If Q is a distribution over H, clarify that Q(h) is a prior mass and that this requires a countable support or a prior measure; otherwise the notation is misleading.","section":"Eq. (4)"}],"recommendation":"major_revision","confidential_remarks":"The core Theorems 4–6 appear sound, and the paper has real potential. The main problem is the unsupported uniform bound in Eq. (4) and the unresolved train/U overlap in Section 4.1. Both are fixable: the authors could restrict use case #2 to a countable/prior-based selection procedure or add a complexity term, and they must clarify the data split. I do not see grounds for rejection, but the current version overclaims coverage of the distillation experiments."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: the fixed-surrogate disagreement bounds are real and the empirical numbers are strong. Theorem 4 in use case #1 — certify a target f through a surrogate h that has its own tight bound, plus a concentration-bounded disagreement on an unlabeled set U — is a simple, correct application of Yang et al.'s inequality and Langford's test set bound. The results (1.78% on MNIST, 17.4% on CIFAR-10 with a random coreset; 3.5%/35% with SubLoRA; 4.8%/28% with PAC-Bayes) are the tightest computable certificates I know of for unmodified targets, and the integration with sample compression, model compression and PAC-Bayes is a genuine new contribution. The authors also ship code, an honest limitations paragraph, and unusually detailed hyperparameter grids.\n\nThe second thing to know: the 'simultaneously for all h' step in Eq. (4), which is what lets them train the surrogate on U and then certify it on the same U, is not valid as written. There is no union bound over an uncountable class of continuous-parameter networks; no prior, no countability, no complexity term is supplied. Theorem 5's proof requires Q to be fixed before U is drawn, and the distillation experiments in Section 4.2 train SubLoRA on pseudo-labels for U and then use that same U for the disagreement term. So Table 6 and Table S4 do not carry the stated 1−δ guarantee. This is load-bearing for use case #2 though not for use case #1. The fix is either a proper PAC-Bayes treatment over a data-independent prior or an explicit complexity penalty for the model selected on U; as written, Section 4.2 is an empirical illustration in search of a theorem.\n\nOne protocol gap worth flagging: Section 4.1 says the target is 'trained on the whole training set' while U is carved out of that same training set. If f's training includes the inputs in U, the disagreement indicators are not fresh samples and Theorem 4's probability statement is void. I suspect the authors carved U out before training f; the text needs to say so explicitly.\n\nMinor issues: alpha = 1e-3 is chosen via an ablation on the same benchmarks; the hyperparameter grid searches over coreset sizes and methods are not union-bounded; '1−δ=0.99' does not say how the 1−2δ split is handled; Eq. (2) has a typo (L_D(f) should be L_D(h)).\n\nBottom line: the core is sound and deserves referee time. The paper overclaims the 'no assumptions, any predictor' generality in the abstract, but use case #1 alone is a solid contribution and the flaws are fixable. Send it out; a good referee will force the Eq. (4) repair and the protocol clarification.","headline":"Fixed-surrogate disagreement bounds are real, tight, and worth building on; the 'simultaneous over all h' step covering the distillation experiments is not valid as written, and the protocol needs to state clearly that U is independent of the target.","tokens_in":32095,"tokens_out":11872,"would_cite":true,"duration_ms":119057,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Disagreement on unlabeled data certifies any model's true risk","keywords":["disagreement bounds","generalization certificates","surrogate models","unlabeled data","PAC-Bayes","sample compression","model compression","zero-one loss"],"falsifier":"With a fixed unlabeled set U of size m, enumerate all 2^m labelings of U as candidate surrogates and train one to match the target's labels on U (zero disagreement). Equation (4)'s bound then certifies the target's risk with no complexity penalty; for any target with nontrivial true risk, some other labeling in the family will violate the certificate, showing that the simultaneous union bound cannot hold without a complexity term.","tokens_in":31131,"feed_emoji":"🎯","tokens_out":7461,"duration_ms":62124,"temperature":0.7,"pith_summary":"This paper claims that the true risk of any predictor can be bounded by the sum of a surrogate's certified risk and a computable disagreement penalty, measured on unlabeled data alone. The key result, Theorem 4, says that the risk gap between two classifiers is at most the inverted binomial tail of their empirical disagreement rate. Because the target model is never modified and no architectural assumptions enter, the bound applies to any deep network, transformer, or quantized model. Experiments show non-vacuous certificates on MNIST, CIFAR-10, and large language models, where classical norm- and partition-based bounds fail.","feed_headline":"Disagreement on unlabeled data certifies any model","feed_subtitle":"Pair any network with a simple surrogate; observed disagreement bounds its true risk with no architectural assumptions.","key_machinery":"The machinery is the disagreement measure d^{0-1}_U(f,h) = (1/m) Σ_i I[argmax f(x_i) ≠ argmax h(x_i)] paired with the binomial tail inversion Bin(k,m,δ). The load-bearing identity is |R_D(f)-R_D(h)| ≤ E_{(x,y)~D} I[argmax f(x) ≠ argmax h(x)], which converts an unobservable risk gap into an expectation of a bounded indicator; the sample analogue is exactly the disagreement rate. For Lipschitz losses, the same role is played by the L1 distance between softmax outputs, ‖σ(f(x))-σ(h(x))‖_1, with the Chernoff/kl^{-1} bound replacing the binomial inversion.","core_discovery":"The central discovery is a family of disagreement-based certificates. For the zero-one loss, Theorem 4 gives, with probability at least 1-δ over an i.i.d. unlabeled sample U, R_D(f) ≤ R_D(h) + Bin(m d^{0-1}_U(f,h), m, δ), where d^{0-1}_U is the empirical disagreement rate and Bin(k,m,δ) is the binomial tail inversion. This bound is derived from the identity |R_D(f)-R_D(h)| ≤ E[I[argmax f(x) ≠ argmax h(x)]], so the true risk gap is controlled by an expectation that a finite sample can pin down. The same scheme extends to Lipschitz losses (Theorem 5), using a Chernoff bound on the L1 difference of softmax outputs, and to general losses (Theorem 6) at the price of a labeled set. Combined with a","pith_inferences":["If the disagreement rate is the only quantity carrying the bound, one could design probe sets—fixed, public unlabeled pools—to certify models at deployment time without any training data, as long as the probe is representative of the data distribution.","The independence requirement suggests a practical safeguard: reserve a fresh unlabeled set before any training, or use guarantees on public data drawn separately, before applying the theorem.","The same disagreement identity could be extended to distribution-shift detection: a change in disagreement rate on a fixed probe set between two temporal snapshots of a model would give a computable upper bound on true-risk drift.","The bound's form allows targeted minimization: optimizing the surrogate to minimize the right-hand side directly, rather than test accuracy, could yield certificates that approach the test-set bound without needing a held-out labeled set."],"forward_implications":["Any target model—regardless of architecture, activation, loss, or optimizer—can receive a non-vacuous certificate once a close surrogate with a tight bound is available.","The certificate is closed-form and fully computable from an unlabeled sample and the two models' predictions; no norms, universal constants, or intractable complexity terms appear.","Quantized, distilled, or compressed variants of a model can be certified for deployment by bounding the true-risk gap against the original model.","The surrogate can be trained on unlabeled pseudo-labels to minimize disagreement, tightening the certificate (use case #2) for large language models.","The approach inherits the tightness of the surrogate's bound, so improving any single surrogate class immediately improves the target certificate."],"fun_headline_variants":["Unlabeled data certifies any model's true risk","Bound any network's risk with a simple surrogate","Disagreement yields risk bounds without touching your model","Tight risk certificates for any predictor via unlabeled samples","Certifiable risk bounds: pair any model with a surrogate"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The unlabeled set on which disagreement is measured must be sampled independently of both the target and the surrogate; when the disagreement set is carved from the same data that trained the target, the high-probability guarantee in the theorems does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Unlabeled data certifies any model's true risk","Bound any network's risk with a simple surrogate","Disagreement yields risk bounds without touching your model","Tight risk certificates for any predictor via unlabeled samples","Certifiable risk bounds: pair any model with a surrogate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000223,"raw_usage":{"total_tokens":1266,"prompt_tokens":690,"completion_tokens":576,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":434,"completion_tokens_details":{"reasoning_tokens":499}},"tokens_in":434,"tokens_out":576,"duration_ms":5320,"temperature":1.0,"reasoning_tokens":499,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T20:26:36.594893+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"With a fixed unlabeled set U of size m, enumerate all 2^m labelings of U as candidate surrogates and train one to match the target's labels on U (zero disagreement). Equation (4)'s bound then certifies the target's risk with no complexity penalty; for any target with nontrivial true risk, some other labeling in the family will violate the certificate, showing that the simultaneous union bound cannot hold without a complexity term.","supporting_citations":[],"review_version":1}