REVIEW 6 minor 1 cited by
Optimal Rates for Learning with Monotone Adversaries
T0 review · 0 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict Tight minimax rates under monotone adversaries, with clean lower-bound constructions and one honest caveat about growing budgets. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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)$.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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.
minor comments (6)
- [Section 2, Notation paragraph] The sentence 'All logarithms are have base e' contains a typo and should read 'All logarithms have base e.'
- [Section 3.1.2, proof of Theorem 3.5] 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 3.1.3, Lemma 3.11] 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 3.1.2, Lemma 3.7] 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.
- [Theorem 3.1 and Proposition 3.4] The notation '1/2e(n+1)' should be typeset as '1/(2e(n+1))' to avoid ambiguity.
- [Abstract and Section 1] 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).
Circularity Check
No significant circularity: the lower bounds are explicit minimax constructions and the upper bounds invoke external standard bounds.
full rationale
The derivation chain is self-contained against external benchmarks. The central rates in Theorem 3.1 are obtained from explicit constructions: the d=1 lower bound is a two-concept prior with an explicit insertion rule, and the d>=2 lower bounds are witnessed by finite projective-plane classes and Cartesian products with explicitly specified budgets and adversaries. The posterior calculations are derived by Bayes' rule from the stated prior and likelihoods, not assumed. Upper bounds use the standard realizable VC estimate (Theorem 2.2) and the external ERM bound of LPS26 for d>=2; LPS26 is prior work by different authors, so this is not a self-citation chain. The quantity R(n,d)=sup_m R(n,m,d) is defined as a worst case over finite budgets, and Theorem 3.1 states the d>=2 result only for that supremum, with the witnessing budget m_{n,d} explicitly disclosed; Remark 3.2 further notes that bounded budgets do not exhibit the logarithmic separation. This is a stated scope condition, not a circular step. No fitted parameter is renamed as a prediction, and no target rate is used as an input to its own derivation. Consequently, no specific reduction of a claimed result to its own inputs can be exhibited.
Assumptions & free parameters
assumptions (5)
- standard math Finite projective planes of prime order q exist for every prime q.
- standard math Bertrand's postulate: for every integer N>1 there is a prime p with N<p<2N.
- standard math Realizable VC generalization bound: for a class of VC dimension d, the expected error of any consistent hypothesis is O((min{d,n}/n) log(en/min{d,n})).
- standard math VC dimension is preserved under pointwise XOR with a fixed function.
- standard math Littlestone dimension is additive for products of classes on disjoint domains.
Cite this review
Pith. "Pith review of Optimal Rates for Learning with Monotone Adversaries." pith.science (2026). https://pith.science/paper/SH6SOAGM
@misc{pith2026260806337,
author = {Pith},
title = {Pith review of: Optimal Rates for Learning with Monotone Adversaries},
year = {2026},
howpublished = {\url{https://pith.science/paper/SH6SOAGM}},
note = {Machine review of arXiv:2608.06337}
}
abstract
A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable. Larsen, Pabbaraju, and Shetty, who introduced this model, showed that empirical risk minimization attains expected error $O((d/n)\log(n/d))$ for classes of VC dimension $d$, and that every known optimal learner can be pushed away from the $\Theta(d/n)$ rate, optimal for PAC learning. They asked whether the extra logarithm is an artifact of those particular algorithms or an inherent consequence of the lack of exchangeability. We show that this additional cost is inherent beyond VC dimension one. In the worst case over classes of VC dimension $d$ and over known finite insertion budgets, the minimax expected error is $\Theta(1/n)$ at $d=1$ and $\Theta((d/n)\log(n/d))$ for $d\geq 2$. The same rates hold with Littlestone dimension $d_{\mathrm L}$ in place of $d$, so the clean online-to-batch rate $O(d_{\mathrm L}/n)$ is unattainable as well. Thus, somewhat counterintuitively, adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning. The dimension-one upper bound is achieved by a simple improper learner whose analysis adapts the leave-one-out argument underlying the one-inclusion graph. All of our lower bounds are elementary and come from a single construction: an explicit class and prior on which two target hypothesis, which differ a point of nonnegligible mass, produce the same sample.
Forward citations
Cited by 1 Pith paper
-
Bagging Robustly Learns VC Classes with Linear Sample Complexity
Bagging robust ERMs achieves robust risk O(d/n) for VC classes with VC dimension d, and Ω(d*) RERM calls are necessary where d* is the dual VC dimension.
Reference graph
Works this paper leans on
-
[36]
The Optimal Sample Complexity of PAC Learning
2023, pp. 8027– 8047 (cit. on pp. 4, 17). [Han16] Steve Hanneke. “The Optimal Sample Complexity of PAC Learning”. In: Journal of Machine Learning Research 17.38 (2016), pp. 1–15 (cit. on pp. 2–4, 7). [Hir98] J. W. P . Hirschfeld.Projective Geometries over Finite Fields . 2nd ed. Oxford Mathematical Monographs. Oxford University Press, 1998 (cit. on p. 9)....
work page 2016
-
[49]
Proceedings of Machine Learning Research. PMLR, 2016, pp. 47–80 (cit. on p. 9). [Ben15] Shai Ben-David. 2 Notes on Classes with Vapnik–Chervonenkis Dimension
work page 2016
-
[134]
Learning in an Echo Chamber: Online Learning with Replay Adversary
Proceedings of Machine Learning Research. PMLR, 2021, pp. 591–634 (cit. on pp. 4, 17). [DFHS26] Daniil Dmitriev, Harald Eskelund Franck, Carolin Heinzler, and Amartya Sanyal. “Learning in an Echo Chamber: Online Learning with Replay Adversary”. In: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2026, pp. 6674–6695 (cit. on...
work page 1989
-
[195]
Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm
Proceedings of Machine Learning Research. PMLR, 2023, pp. 450–468 (cit. on pp. 2–4). [Lit88] Nick Littlestone. “Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm”. In: Machine Learning 2.4 (1988), pp. 285–318 (cit. on pp. 3, 4, 6, 21). [LPS26] Kasper Green Larsen, Chirag Pabbaraju, and Abhishek Shetty. “Learning with Mon...
work page 1988
-
[247]
Partitioning and Geometric Embedding of Range Spaces of Finite Vapnik–Chervonenkis Dimension
Proceedings of Machine Learning Research. PMLR, 2024, pp. 22–45 (cit. on pp. 2–4). [AHW87] Noga Alon, David Haussler, and Emo Welzl. “Partitioning and Geometric Embedding of Range Spaces of Finite Vapnik–Chervonenkis Dimension”. In: Proceedings of the Third Annual Symposium on Computational Geometry. ACM, 1987, pp. 331–340 (cit. on p. 9). [AMY16] Noga Alo...
work page 2024
-
[313]
How Robust are Reconstruction Thresholds for Community Detection?
Proceedings of Machine Learning Research. PMLR, 2026, pp. 1–18 (cit. on pp. 1–5, 7, 8, 18). [MPW16] Ankur Moitra, William Perry, and Alexander S. Wein. “How Robust are Reconstruction Thresholds for Community Detection?” In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing. ACM, 2016, pp. 828–841 (cit. on p. 5). [RST15] Alexander Rakhlin...
work page 2015
-
[2015]
Limitations of Learning Via Embeddings in Euclidean Half Spaces
URL: https://arxiv.org/ abs/1507.05307 (cit. on p. 17). [BES02] Shai Ben-David, Nadav Eiron, and Hans Ulrich Simon. “Limitations of Learning Via Embeddings in Euclidean Half Spaces”. In: Journal of Machine Learning Research 3 (2002), pp. 441–461 (cit. on p. 9). [BHHLT26] Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, and Sivan Tretiak. Sign-Rank,...
arXiv 2002
-
[2026]
Robust Learning under Clean-Label Attack
URL: https://arxiv.org/abs/2606. 18236v2 (cit. on p. 9). [BHK20] Avrim Blum, John Hopcroft, and Ravindran Kannan. Foundations of Data Science. Cambridge University Press, 2020 (cit. on p. 3). [BHQS21] Avrim Blum, Steve Hanneke, Jian Qian, and Han Shao. “Robust Learning under Clean-Label Attack”. In: Proceedings of Thirty Fourth Conference on Learning Theory. Vol
work page 2020
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.