{"id":"75dea2d6-9458-4e6e-89ea-55c0ad958412","arxiv_id":"2607.19689","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"(ε, ε²)-recalibration is achievable in Θ(ε⁻³) rounds and this is optimal; the same rate gives simultaneous calibration and calibeating.","lead":"This paper gives an algorithm that recalibrates an online forecast stream, making it calibrated while increasing loss by only ε², in about 1/ε³ rounds, and proves this rate is optimal. It also uses this to achieve calibrated predictions that beat a reference forecaster, answering an open question in online learning.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound charging argument (Lemma 20) contains a false inequality as written; if unfixed, Theorem 13 does not follow.","rationale":"The reader's verdict ACCEPT with moderate confidence rests on the completeness of the lower-bound proof. The charging argument in Lemma 20 contains an inequality that is false as written, and this lemma is directly used to prove Theorem 13. The error appears to be a typo (floor should be ceiling), and the rate likely survives, but the proof as presented does not establish the claimed bound. A second constant error in Lemma 19 is minor and does not affect the asymptotic rate. These are concrete, checkable issues rather than a fundamental invalidation of the central claim; hence the verdict should be CONDITIONAL: accept only after the proof is corrected and the corrected chain is verified.","tokens_in":37604,"tokens_out":43514,"duration_ms":425805,"concrete_test":"Re-derive Lemma 20 with ceil: replace floor by ceil in the b_v lower bound and verify Σ_{i∈[a_v]} (ε ceil(i/(2L)))² ≥ ε² a_v²/(4L). Also re-check Lemma 19 with the correct constant ~1/111; if the T=Ω(ε^{-3}) conclusion survives with a smaller constant, the concern is limited to proof hygiene.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Section 8.2, the proof of Lemma 20 claims b_v ≥ Σ_{i∈[a_v]} (ε⌊i/(2L)⌋)² ≥ Σ_{i∈[a_v]} ε² i/(2L) ≥ ε² a_v²/(4L). The second inequality is false for floor: e.g., L=2, a_v=1 gives LHS=0 and RHS=ε²/4. The intended step likely uses ceiling, in which case the chain holds; but as written the proof of the upper bound (43) on Σν_v² fails. Since (43) is what converts the hardness (Lemma 19) into the T=Ω(ε^{-3}) lower bound (Theorem 13), this is a load-bearing gap in the optimality claim. A related constant slip occurs in Lemma 19, where the derivation yields E[|µ_v|] ≥ E[ν_v]^{3/2}/(~111√(...)) rather than /(48√(...)); this does not affect the rate.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online recalibration in the hinted sequential prediction model (Model 1): a learner observes arbitrary hint forecasts q_t and must output predictions p_t that are calibrated against labels y_t while incurring small excess proper loss relative to the hints. The main theorem (Theorem 5) gives an (ε, ε²)-recalibration algorithm for L-Lipschitz proper losses in T = O(L²/ε³) rounds, via an imbalanced simultaneous Blackwell approachability framework (Theorem 4) with an MLOO rederived from OKS24. A K2-calibration variant (Theorem 9) achieves the same tradeoff up to a logarithmic factor. These results are applied to simultaneous ε-calibration and ε²-calibeating for s-sparse hints (Theorems 6 and 10), with multi-hint extensions (Sections 6 and 7.4). The paper also proves a matching Ω(ε^{-3}) lower bound for the squared loss (Theorem 13) and reports experiments on CIFAR with distribution shift. The lower-bound proof has a repairable but currently incorrect inequality in Lemma 20.","tokens_in":37835,"tokens_out":31769,"duration_ms":301406,"significance":"If the results are correct, the paper settles the iteration complexity of (ε, ε²)-recalibration up to constants, improves the known rate for simultaneous calibration and calibeating from about ε^{-4} to roughly ε^{-3}, and answers an open question of CHJL26 for smooth proper losses. The paper is largely self-contained: Theorem 4 is proved in detail, the MLOO is derived explicitly, and the lower bound is a concrete counting argument. A particular strength is that no fitted parameters enter the derivation; all constants are analytical functions of ε, L, G, and s. The scope of the main application is narrower than the recalibration theorem, since calibeating requires sparsity (Remark 3) and smoothness (Assumption 2), but this is inherent to the problem. The empirical study is a reasonable sanity check.","major_comments":[{"comment":"The proof of (43) contains a false inequality. The displayed chain b_v ≥ Σ_{i∈[a_v]} (ε⌊i/(2L)⌋)² ≥ Σ_{i∈[a_v]} ε² i/(2L) ≥ ε² a_v²/(4L) does not hold as written: for L=2 and a_v=1, the middle inequality reads 0 ≥ ε²/4. Since (43) is the step that converts the per-bin hardness (Lemma 19) into the T=Ω(ε^{-3}) lower bound (Theorem 13), the lower-bound proof is incomplete. The fix appears local: for excess rounds q_t≠v and both q_t,r_t lie on the same ε-net, so |q_t-r_t|≥ε; sorting the a_v excess distances gives d_i ≥ ε⌈i/(2L)⌉, and the chain holds with ceiling instead of floor. Please correct the proof and re-verify the resulting constants.","section":"Section 8.2, Lemma 20"}],"minor_comments":[{"comment":"The displayed derivation gives E|μ_v| ≥ (3/16)^{3/2}/(9√(Eν_v²+1)) · E[ν_v]^{3/2} ≈ 0.0090·..., i.e. a denominator around 111 rather than 48. The rate is unaffected, but the constant should be corrected.","section":"Section 8.2, Lemma 19"},{"comment":"The sentence 'ε≥T/(32·1440²) is lower bounded by a constant' is terse. The intended argument seems to be that T≥1 forces ε to be bounded below by an absolute constant in the first case, so the Ω(ε^{-3}) conclusion is vacuous there; please rephrase for clarity.","section":"Section 8.2, Theorem 13"},{"comment":"'Union bound over the 2|N| sign vectors' should read 2^{|N|}; the subsequent |N| log 2 term shows the intended bound.","section":"Section 4.3, Lemma 7"},{"comment":"The proof of the pathwise guarantee is only a paragraph. Because the high-probability result is later used with nature's future play depending on the sampled p_t rather than the mixed a_t, it would help to spell out the pointwise/martingale argument in more detail.","section":"Section 4.3, Lemma 6"},{"comment":"The K2 algorithm appears to require O(N²T) expert evaluations per round (N bins × |F|·T experts). The paper does not state the per-round computational complexity; a brief note would be useful.","section":"Section 7"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the false inequality in Lemma 20, which is load-bearing for the lower bound but appears to be a local floor/ceiling typo. If the authors fix it and re-check the constants, I expect the paper to be acceptable. I recommend major revision rather than reject because the central framework and upper bounds are sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a real result. It improves the OKS24 recalibration rate from O(ε^-4) to Θ(ε^-3), proves a matching lower bound, and answers the CHJL26 calibeating+calibration question at the ε^-3 scale. I read the main theorems and their proofs; the imbalanced simultaneous Blackwell framework is coherent, the MLOO rederivation from OKS24 is correct, and the K2 quadratic-audit argument is self-contained. No fitted parameters, no circularity. The paper deserves a serious referee.\n\nWhere I disagree with the stress-test note: yes, Lemma 20 has a typo, but it is not the load-bearing failure the note claims. In the proof of Lemma 20 the chain b_v ≥ Σ_i (ε⌊i/(2L)⌋)^2 ≥ Σ_i ε² i/(2L) is false as written—floor is zero for small i and generally floor(x)^2 ≤ x. The intended packing argument obviously wants ceil(i/(2L)), and with that replacement the chain Σ_i (ε⌈i/(2L)⌉)^2 ≥ Σ_i ε² i/(2L) ≥ ε² a_v²/(4L) is immediate. So (43) and Theorem 13 survive. A referee should ask for the fix; nobody should desk-reject over it.\n\nTwo smaller items. Lemma 19's constant 48 looks like the wrong numeric constant (the displayed derivation gives roughly 111), though the rate is unaffected. And the main calibeating application requires sparse hint sequences—the authors say so in Remark 3, and it is a genuine scope restriction, not a hidden flaw. The multiclass experiment is explicitly outside the theory; nice to have, not evidence.\n\nWho this is for: anyone working on online calibration, calibeating, or Blackwell-approachability reductions. It settles the rate for the core recalibration problem and gives a clean framework for imbalanced objectives. I would cite it and I would send it to review.","headline":"Solid optimality result for (ε, ε²)-recalibration with a matching lower bound; the one notable blemish is a false floor-vs-ceil inequality in Lemma 20 that is a one-character fix, not a conceptual gap.","tokens_in":38336,"tokens_out":5728,"would_cite":true,"duration_ms":61559,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Online recalibration is achievable in T≈ε⁻³ rounds, and that is optimal.","keywords":["online recalibration","calibration error","proper losses","Blackwell approachability","calibeating","online learning","lower bounds","prediction refinement"],"falsifier":"Run the cyclic hard instance of Section 8 (q_t cycles through the ε-grid in [1/4, 3/4], y_t ~ Bern(q_t)) with T = c ε⁻³ for a small constant c and ε → 0; any algorithm that achieves expected K₁ ≤ ε and expected squared-loss excess ≤ ε² on all such instances at that horizon would refute Theorem 13.","tokens_in":37487,"feed_emoji":"🎯","tokens_out":6848,"duration_ms":61451,"temperature":0.7,"pith_summary":"This paper settles, up to constant factors, the number of rounds needed to recalibrate an online predictor: with T≈ε⁻³ timesteps, a learner can take any sequence of hint forecasts and replace them with forecasts that are ε-calibrated against the observed labels while increasing the loss by at most ε², under any Lipschitz proper loss such as squared loss. It also proves that for squared loss this is best possible: no algorithm can meet both targets in o(ε⁻³) rounds. The same machinery yields a K₂ variant (root-mean-square calibration) at the same rate up to log factors, and, by chaining recalibration with an online refinement step, gives simultaneous ε-calibration and ε²-calibeating for smooth proper losses on sparse hint sequences, answering an open question about matching the best separate rates for the two objectives. The paper also extends the guarantees to multiple competing hint sequences and reports experiments on drifted classification data.","feed_headline":"Recalibration is achievable in T≈ε⁻³ rounds, and that is optimal","feed_subtitle":"A single online procedure can make any proper-loss forecaster both calibrated and loss-safe at the optimal rate.","key_machinery":"The central object is an imbalanced simultaneous Blackwell approachability framework (Theorem 4), which lets a learner enforce m coupled vector-payoff constraints with different target accuracies by mixing m no-regret learners and a mixture linear optimization oracle (MLOO). For recalibration, the two payoffs are the calibration vector {a_s(s−y)} and the excess loss Σ a_s(ℓ(s,y)−ℓ(q,y)); the asymmetric tolerances are (ε, ε²). The load-bearing implementation is a geometric MLOO (Lemma 4) that, given any calibration distinguisher u and mixture weights, outputs a distribution over two neighboring grid points satisfying the coupled constraints with the right slacks. For the K₂ variant, the machi","core_discovery":"The paper's central claim is an optimal tradeoff: for recalibration, the calibration error and excess loss can both be driven to (ε, ε²) in T=Θ(ε⁻³) rounds, and for squared loss no algorithm can do better. The upper bound holds for all proper losses whose two label-conditional functions are L-Lipschitz, with horizon O(L²/ε³). The proof routes recalibration through an imbalanced version of simultaneous Blackwell approachability: one objective (calibration) is approached with tolerance ε, the other (excess loss) with tolerance ε², and a geometric oracle produces a distribution over a fine grid that satisfies the coupled halfspace constraints with the right asymmetric slacks. The lower bound us","pith_inferences":["Editorial: The Lipschitz condition on the loss is likely relaxable for the upper bound; a natural test is whether (ε, ε²)-recalibration rates persist for unbounded proper losses like untruncated logistic loss.","Editorial: The lower bound is proved only for squared loss; a plausible conjecture is that the same ε⁻³ barrier holds for any strictly proper Lipschitz loss, since the hard instance's bias-variance structure is generic.","Editorial: Because calibeating is impossible for dense hint sequences, a practical design principle is to aim for weaker excess-loss targets (e.g., (ε, ε)) or compare against a coarsened hint when sparsity fails.","Editorial: The experiments suggest recalibration can serve as a drop-in postprocessor for existing forecasters, but the multiclass evaluation relies on a projection step that goes beyond the paper's formal guarantees."],"forward_implications":["If the upper bound is right, any Lipschitz proper loss can be recalibrated to (ε, ε²) in O(ε⁻³) rounds, improving on prior O(ε⁻⁴) and O(ε⁻⁸) rates for squared loss.","If the lower bound is right, the ε⁻³ horizon is unavoidable for squared loss, so (ε, ε²)-recalibration is strictly harder than plain online calibration.","Combining recalibration with online refinement yields simultaneous ε-calibration and ε²-calibeating for smooth proper losses on sparse hints at the same asymptotic rate, answering the open question of whether the best separate rates can be achieved together.","The multi-sequence extension implies that with m hints, recalibration costs an additive O(ε⁻² log m) rounds, matching the necessity of hint compression.","The high-probability variant extends the guarantees from expectation to holding with probability 1−δ at a modest additional cost in the horizon."],"fun_headline_variants":["Optimal recalibration: (ε, ε²) tradeoff in T≈ε⁻³ rounds","Recalibration hits optimal rates: ε calibration, ε² loss in ε⁻³ rounds","Matching lower bound: recalibration needs T≈ε⁻³ for squared loss","Simultaneous calibration and calibeating at optimal rate, now proven"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The simultaneous calibration-plus-calibeating result assumes the hint forecasts take only O(1/ε) distinct values and the loss satisfies a smoothness bound; without such sparsity, ε²-calibeating is impossible, so the flagship application does not cover dense hint sequences or unbounded proper losses.","fun_headline_variants_meta":{"raw":{"variants":["Optimal recalibration: (ε, ε²) tradeoff in T≈ε⁻³ rounds","Recalibration hits optimal rates: ε calibration, ε² loss in ε⁻³ rounds","Matching lower bound: recalibration needs T≈ε⁻³ for squared loss","Simultaneous calibration and calibeating at optimal rate, now proven"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000913,"raw_usage":{"total_tokens":3788,"prompt_tokens":807,"completion_tokens":2981,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":551,"completion_tokens_details":{"reasoning_tokens":2890}},"tokens_in":551,"tokens_out":2981,"duration_ms":16862,"temperature":1.0,"reasoning_tokens":2890,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T11:59:16.928218+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the cyclic hard instance of Section 8 (q_t cycles through the ε-grid in [1/4, 3/4], y_t ~ Bern(q_t)) with T = c ε⁻³ for a small constant c and ε → 0; any algorithm that achieves expected K₁ ≤ ε and expected squared-loss excess ≤ ε² on all such instances at that horizon would refute Theorem 13.","supporting_citations":[],"review_version":1}