{"id":"796a75f6-76f3-4f64-8094-6e739e62dd63","arxiv_id":"2608.06337","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For learning with monotone adversaries, the worst-case minimax expected error is Θ(1/n) in dimension one and Θ((d/n) log(n/d)) in dimension two or more.","lead":"This paper proves that when a helper can add correctly labeled examples chosen after seeing the original data, some concept classes of dimension two or more force every learning algorithm to pay an extra logarithmic error penalty. The result settles an open question and shows the slowdown is a real statistical barrier, not a quirk of particular algorithms.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the only soft spot is the budget-growth caveat, which the paper states and handles in Remark 3.2.","rationale":"The paper's Theorem 3.1 is the central claim; it resolves LPS26's first open question by showing sup_m R(n,m,d) = Θ((min{d,n}/n) log(en/min{d,n})) for d≥2. The main potential weakness identified by the reader is that the lower bound needs a budget growing with n. I agree this is the only substantive limitation, but it is not a correctness flaw: the theorem explicitly quantifies over all finite budgets and Remark 3.2 correctly demarcates the bounded-budget regime. I scrutinized the adversarial construction: the projective-plane class has VC dimension exactly 2, U_f is the unique final multiset forcing version space {u_p,v_L}, the two hypotheses have equal prior and likelihood, and the posterior remains 1/2 even for order-sensitive learners. The product construction preserves VC dimension and gives the d≥3 rates. Lemma 3.13's 'at most one leave-one-out error' statement is valid because two errors would realize four patterns on a pair, contradicting VC dimension 1. The Littlestone results follow by the same construction restricted to checkers. No step relies on an unstated assumption or circular reasoning. Thus the ACCEPT verdict stands.","tokens_in":19239,"tokens_out":25925,"duration_ms":339119,"concrete_test":"Recompute the key posterior step for a small instance of the projective-plane class (e.g., q=3, the Fano plane): enumerate all clean samples with a missing checker and all rankings, verify that every final multiset U_f has version space exactly {u_p,v_L}, that no other flag or Case-B multiset coincides with U_f, and that the posterior on u_p versus v_L is exactly 1/2 for every ordering. If any U_f is producible from another hypothesis or the posterior shifts, the d=2 lower bound collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of Theorem 3.1 is formally correct as stated: R(n,d) is defined as a supremum over all finite exact budgets, and for d≥2 the logarithmic lower bound is witnessed by a budget m_{n,d} that grows with n (in the projective-plane construction, m = n(|X_q|-1) with |X_q| roughly q^3 ≈ (n/log n)^3). For fixed or bounded budgets Remark 3.2 shows the clean Θ(min{1,d/n}) rate is achievable, so the logarithmic separation is a worst-case-over-budgets phenomenon, not a statement about every finite budget. I checked the lower-bound chain: the version space of U_f is exactly {u_p,v_L}; the two targets have equal prior mass and equal likelihood ρ/k; conditional on U_f the posterior is exactly 1/2; the selected checker has mass 1/k and opposite labels, giving the 1/(2k) contribution; the coupon-collector estimate gives ρ≥2/3 for the chosen q; and the d=1 upper bound via Lemma 3.13 appears valid even with adaptive insertions. I find no internal inconsistency or missing step that would invalidate the stated theorem.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies learning with a monotone adversary, a model introduced by Larsen, Pabbaraju, and Shetty in which an adversary sees a clean i.i.d. sample and appends a finite number of correctly labeled examples before the combined sample is shuffled. The paper's central results are Theorem 3.1 and Theorem 3.3: for binary classes of VC dimension d, the worst-case minimax expected error over all finite known insertion budgets is 0 for d=0, Theta(1/n) for d=1, and Theta((min{d,n}/n) log(en/min{d,n})) for d>=2; the same rates hold with Littlestone dimension in place of VC dimension. The upper bounds for d>=2 are inherited from the ERM analysis of Larsen, Pabbaraju, and Shetty, while the d=1 upper bound is a new improper learner based on a leave-one-out argument. The lower bounds come from a single projective-plane construction: two hypotheses that agree except at a point of nonnegligible mass are made exactly indistinguishable by correctly labeled insertions, and the construction is amplified by Cartesian products for larger dimensions. The paper explicitly notes that the lower-bound witness requires a budget that grows with n and that bounded budgets restore the clean rate (Remark 3.2).","tokens_in":19406,"tokens_out":30655,"duration_ms":363841,"significance":"If the results are correct, they settle both open questions posed by Larsen, Pabbaraju, and Shetty: the minimax error under monotone adversaries is determined up to constants by VC dimension, and finite Littlestone dimension does not restore the clean online-to-batch rate. For d>=2, the logarithmic separation from the clean rate is algorithm-independent, and ERM is shown to be optimal in the worst-case-over-budgets sense. The proofs are notable for being explicit and elementary: the lower bound is witnessed by an explicit finite class and prior, the VC-dimension computation is self-contained, the coupon-collector estimate is elementary, and the posterior-balancing argument is carried out pointwise over orderings, so it holds for order-sensitive learners. The d=1 upper bound gives a concrete improper learner. The paper also honestly discloses the main limitation, namely that the separating budget must grow with n, and it handles bounded budgets in Remark 3.2. I found no circularity: no free parameters are fitted and no step assumes the target rate.","major_comments":[],"minor_comments":[{"comment":"The sentence 'All logarithms are have base e' contains a typo and should read 'All logarithms have base e.'","section":"Section 2, Notation paragraph"},{"comment":"The adversary is only specified for clean samples lying in the support of D*; because Definition 1 defines a monotone adversary as a total map A: X^n -> X^m, please either add the off-support 'null' branch used in Theorem 3.10 or state explicitly that the adversary may be defined arbitrarily on off-support inputs.","section":"Section 3.1.2, proof of Theorem 3.5"},{"comment":"The proof of Lemma 3.11 is deferred as identical to Lemma 3.9, but the block count N_i is random (Binomial(n,1/r)); please add one sentence explaining that the coupon-collector calculation is done unconditionally with per-draw miss probability 1/(rk), so the same derivation applies despite the random block sizes.","section":"Section 3.1.3, Lemma 3.11"},{"comment":"The Case C argument for three collinear points is compressed; in particular, the subcase with more than one selector is not fully spelled out, so please expand the counting of missing traces to make the impossibility fully transparent.","section":"Section 3.1.2, Lemma 3.7"},{"comment":"The notation '1/2e(n+1)' should be typeset as '1/(2e(n+1))' to avoid ambiguity.","section":"Theorem 3.1 and Proposition 3.4"},{"comment":"The LPS26 ERM bound is written as log(n/d) in the abstract and as log n/d in Section 1; please standardize the notation, preferably as log(n/d) or log(en/d).","section":"Abstract and Section 1"}],"recommendation":"minor_revision","confidential_remarks":"This is a strong and carefully argued paper. The technical content appears correct, and the only issues I found are local presentation gaps: a missing off-support branch in one adversary definition, a deferred proof that is genuinely but tersely 'identical', and a few typos. The worst-case-over-budgets framing is unusual but is stated precisely and handled honestly in Remark 3.2, so I do not view it as a defect. I recommend minor revision rather than immediate acceptance only to allow these local issues to be cleaned up."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is the right answer to both LPS open questions, and the proof is checkable. The projective-plane posterior-balancing construction is genuinely new and does the heavy lifting; the d=1 leave-one-out consensus rule is a nice adaptation. The paper shows the log factor is inherent for d≥2, and ERM is optimal, reversing the classical picture. I believe the central claims are correct.\n\nWhat is actually new: algorithm-independent lower bounds in this model; matching upper via ERM; VC and Littlestone dimension both. The construction of two targets that produce exactly the same shuffled sample with only correctly-labeled insertions is clever. The posterior balancing goes through for every learner, including improper and randomized. The d=1 upper bound handles adaptive insertions by allowing different augmentation per leave-one-out sample; Lemma 3.13 is the key and seems right. The higher-dimensional products and Littlestone adaptation are routine but correct.\n\nSoft spots, in proportion. The logarithmic separation is worst-case over insertion budgets; for fixed m=O(1), the clean rate survives, stated in Remark 3.2. So the theorem answers the worst-case-over-budgets question, not the fixed-budget question. That is not a flaw in the theorem as stated, but it is the main scope caveat and should be kept visible. The paper does keep it visible. Minor: Lemma 3.11 is deferred as identical to Lemma 3.9; acceptable, since the replacement is just n → n/r. Also the lower bound uses a prior and then fixes target by averaging; standard minimax argument. I don't see a circular step or hidden parameter fitting.\n\nCitation pattern: builds on LPS and standard HLW/Hanneke/Larsen; self-citation not an issue here. The acknowledgments mention AI tool use; irrelevant to correctness.\n\nWho should read: anyone working on statistical learning under dependent or curated data, and the semirandom/TCS crowd. It deserves a serious referee; a careful referee should verify Lemma 3.7 and the posterior calculation, but they are explicit. Recommendation: engage; send to peer review.","headline":"Tight minimax rates under monotone adversaries, with clean lower-bound constructions and one honest caveat about growing budgets.","tokens_in":19968,"tokens_out":1603,"would_cite":true,"duration_ms":19712,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that under adaptive monotone insertions—extra examples that are always correctly labeled—the worst-case optimal error is $\\Theta((d/n)\\log(n/d))$ for classes of VC dimension $d\\ge 2$, a logarithmic factor above the i.i.d.","keywords":["monotone adversary","minimax expected error","VC dimension","Littlestone dimension","semirandom models","one-inclusion graph","projective plane","adversarial insertions"],"falsifier":"Take the projective-plane class of Theorem 3.5 with $q$ the prime between $4n/\\log(en)$ and $2n/\\log(en)$ and exact budget $m=n(|X_q|-1)$, and compute or simulate the minimax expected error over this class for finite $n$; a learner with error below $\\log(en)/(30n)$ would contradict the lower bound. More generally, any class of VC dimension two and any learner achieving $o((d/n)\\log(n/d))$ against all monotone adversaries with budgets that may grow with $n$ would falsify Theorem 3.1.","tokens_in":18984,"feed_emoji":"🎯","tokens_out":11830,"duration_ms":132188,"temperature":0.7,"pith_summary":"The paper sets out to determine whether the extra logarithmic factor that appears when an adversary appends correctly labeled examples is a quirk of particular algorithms or an inherent feature of the learning problem. It proves that the worst-case minimax expected error over classes of VC dimension $d$ and over all finite insertion budgets is $\\Theta(1/n)$ at $d=1$ and $\\Theta((\\min\\{d,n\\}/n)\\log(en/\\min\\{d,n\\}))$ for every $d\\ge 2$, with the same rates in the Littlestone dimension. If correct, this is the first algorithm-independent separation between learning from i.i.d. data and learning under monotone insertions: an adversary that adds only correctly labeled points can still make the optimal error a logarithmic factor larger than the clean rate $\\Theta(\\min\\{1,d/n\\})$. The result also shows that empirical risk minimization, which pays the logarithmic factor, is in fact minimax optimal in this model for $d\\ge 2$, while the dimension-one case is saved by a simple improper learner.","feed_headline":"Correctly labeled extra data can hurt learning by a log factor","feed_subtitle":"Worst-case error jumps from d/n to (d/n) log(n/d) for families of VC dimension two or more.","key_machinery":"For $d\\ge 2$, the load-bearing object is a concept class built from a finite projective plane of order $q$: concepts are indexed by points and lines, domain points are indexed by incidence pairs (called checkers and selectors), and each flag $(p,L)$ has the property that the version space of a carefully padded labeled multiset is exactly $\\{u_p,v_L\\}$, two hypotheses that disagree only at a checker of test mass $1/k$. The monotone adversary observes the clean sample, detects whether some support checker is missing, and pads the sample into that canonical multiset, making the two candidate targets equally likely; coupon-collector arguments show such an ambiguity occurs with constant probability, and Bertrand's postulate picks a prime $q$ so that $k=\\Theta(n/\\log n)$. For $d\\ge 3$ the class is amplified by Cartesian products of disjoint blocks. For $d=1$, the carrying mechanism is a leave-one-out lemma: if the proposed consensus rule erred on two held-out points, the consistent witnesses would shatter a two-point set, which is impossible for VC dimension one.","core_discovery":"The central claim is a complete minimax characterization of learning with a monotone adversary. Writing $R(n,d)$ for the supremum over all finite insertion budgets of the best achievable worst-case expected error over binary classes of VC dimension $d$, the paper proves $R(n,0)=0$, $R(n,1)=\\Theta(1/n)$, and $R(n,d)=\\Theta((\\min\\{d,n\\}/n)\\log(en/\\min\\{d,n\\}))$ for all $d\\ge 2$; identical rates hold when VC dimension is replaced by Littlestone dimension $d_{\\mathrm L}$. The lower bounds are algorithm-independent and come from a single construction in which two target hypotheses that differ at a point of nonnegligible test mass give rise, after the adversary pads the clean sample, to exactly the same final labeled multiset, so every learner faces a balanced posterior and must err with constant probability at that point. The dimension-one upper bound is achieved by an improper consensus learner whose analysis extends the leave-one-out argument underlying the one-inclusion graph; at $d\\ge 2$, ERM attains the matching upper bound.","pith_inferences":["Going beyond the paper: the lower-bound construction suggests that the fine-grained rate $R(n,m,d)$ for fixed budget $m$ is controlled by the maximum number of hypothesis pairs that can be padded to identical samples, an interpolation problem the paper leaves open.","The bounded-budget result implies that practical augmentation with a bounded number of correctly labeled points stays in the clean-rate regime; the paper does not identify where the transition to the logarithmic regime occurs as $m$ grows.","The same indistinguishability mechanism should transfer to other offline semirandom models where the adversary commits before the test point: any setting in which two hypotheses can be padded to the same multiset inherits a log-factor lower bound.","One could test the tightness of the constants by computing the exact minimax risk on the projective-plane class for small $n$ and comparing it with $\\log(en)/(30n)$."],"forward_implications":["No randomized or improper learner can beat $\\Theta((d/n)\\log(n/d))$ expected error in the worst case for any class of VC dimension $d\\ge 2$ when the insertion budget is allowed to grow with $n$.","Empirical risk minimization is minimax optimal in this model for $d\\ge 2$, reversing the classical picture in which ERM loses a logarithmic factor to sophisticated learners.","For Littlestone classes, the clean online-to-batch rate $O(d_{\\mathrm L}/n)$ is unattainable; the same logarithmic penalty applies even for a single fixed class with $d_{\\mathrm L}=2$.","If the insertion budget is fixed at $m=O(1)$, the clean rate $\\Theta(\\min\\{1,d/n\\})$ remains achievable, so the logarithmic gap is a worst-case-over-budgets phenomenon.","At dimension one the clean rate $\\Theta(1/n)$ survives every finite budget, and an improper learner attains it even where ERM would not."],"supporting_citations":[{"why":"Introduces the monotone-adversary model, proves the general ERM upper bound $O((d/n)\\log(n/d))$, establishes lower bounds against specific learners, and poses the open questions this paper resolves.","marker":"[LPS26]"},{"why":"Supplies the one-inclusion-graph learner and leave-one-out analysis whose clean $O(d/n)$ rate and dimension-one argument are adapted in the $d=1$ upper bound.","marker":"[HLW94]"},{"why":"Gives the optimal clean PAC learner used as a baseline and in the bounded-budget majority-vote construction of Remark 3.2.","marker":"[Han16]"},{"why":"Defines the Littlestone dimension and the online-to-batch conversion $O(d_{\\mathrm L}/n)$ that Theorem 3.3 shows is unattainable under monotone insertions.","marker":"[Lit88]"},{"why":"Establishes the clean minimax bound $\\Theta(\\min\\{1,d/n\\})$ that the logarithmic separation is measured against.","marker":"[EHKV89]"},{"why":"Provides the $f$-representation trick that relabels the class and is one of the two ingredients in the dimension-one upper bound.","marker":"[Ben15]"},{"why":"Guarantees existence of finite projective planes of prime order, the combinatorial substrate of the $d=2$ lower-bound class.","marker":"[Hir98]"},{"why":"Identifies majority-of-three as an optimal clean learner; the paper's lower bound shows such learners cannot beat the log-factor rate against monotone adversaries.","marker":"[AHLZ24]"}],"fun_headline_variants":["Monotone adversary makes correct labels cost a log factor","Log factor in learning is inherent for VC dimension two and beyond","Extra correct labels can worsen worst-case learning by log","Adversarial correct labels force a log penalty on learning","Learning with monotone adversary: log rate is minimax optimal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The logarithmic separation is a worst-case-over-budgets statement: the lower bounds are witnessed only by insertion budgets $m$ that grow with $n$, and for any fixed constant budget the clean rate remains achievable.","fun_headline_variants_meta":{"raw":{"variants":["Monotone adversary makes correct labels cost a log factor","Log factor in learning is inherent for VC dimension two and beyond","Extra correct labels can worsen worst-case learning by log","Adversarial correct labels force a log penalty on learning","Learning with monotone adversary: log rate is minimax optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000411,"raw_usage":{"total_tokens":2228,"prompt_tokens":1141,"completion_tokens":1087,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":757,"completion_tokens_details":{"reasoning_tokens":1005}},"tokens_in":757,"tokens_out":1087,"duration_ms":13239,"temperature":1.0,"reasoning_tokens":1005,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:04:38.402772+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the projective-plane class of Theorem 3.5 with $q$ the prime between $4n/\\log(en)$ and $2n/\\log(en)$ and exact budget $m=n(|X_q|-1)$, and compute or simulate the minimax expected error over this class for finite $n$; a learner with error below $\\log(en)/(30n)$ would contradict the lower bound. More generally, any class of VC dimension two and any learner achieving $o((d/n)\\log(n/d))$ against all monotone adversaries with budgets that may grow with $n$ would falsify Theorem 3.1.","supporting_citations":[],"review_version":1}