- Rating
- 2
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies the error rate of learning with a monotone adversary. In this problem, the adversary generates an arbitrary number of adversarially chosen examples after seeing a sample of i.i.d. examples. The learner receives all these examples, without knowing which are clean or adversarial. For a hypothesis class with VC dimension , the empirical risk minimization rule solves this problem with an expected error rate of , larger than the bound in PAC learning by a factor . The goal of this paper is to investigate whether this extra factor is necessary.
The main result is that for every , there exists a hypothesis class with VC dimension such that no learner can have an expected error better than . Thus, the extra factor is unavoidable in general. The authors also propose an algorithm that achieves error when , indicating that this factor can be eliminated for classes with VC dimension one. The authors also prove analogous results with replaced by the Littlestone dimension.
Critical strengths
-
Lower bound for unrestricted learners: Previous work only proved lower bounds for certain learning rules. In contrast, the lower bound in this work applies to any learner.
-
Separation: The results demonstrate two important separations. First, the lower bound for shows a separation between PAC learning and learning with a monotone adversary: their error rates can differ by a factor of for some classes. Second, they separate from the case, by showing that a learner never pays the extra factor when .
Critical weaknesses
-
The results do not look very significant. It only differs from PAC learning by a logarithmic factor. Moreover, the lower bound is proven for a deliberately constructed hypothesis class and requires appending examples. It is not a result for generic hypothesis classes.
-
I found the presentation of the paper, especially the proof, hard to follow. This makes it hard for me to understand the essential idea and verify the correctness of the proof. This can be substantially improved by incorporating a technical overview explaining the proof ideas and polishing the proof structure to make it more readable.
Questions for authors
None
4 comments
Response to Reviewer gbyq (2/2)
Weakness 2: “I found the presentation of the paper, especially the proof, hard to follow. This makes it hard for me to understand the essential idea and verify the correctness of the proof. This can be substantially improved by incorporating a technical overview explaining the proof ideas and polishing the proof structure to make it more readable.”
We are sorry to hear that the proof was hard to follow. Below is an overview of our lower-bound proof, which we will expand, together with the role of each lemma, and include in the final version.
In the dimension-two lower bound, each target comes with a uniform distribution on points. The row target and the column target of each flag (an incident point–line pair) disagree at exactly one point of their supports, (Observation 3.8), and a fixed labeled set rules out every other target (Observation 3.6). With our choice of , some support point is missing from the clean sample with probability at least (Lemma 3.9). The adversary then picks a missing point, say , and adds correctly labeled examples so that and produce the same final sample with equal probability (equation (2)). Since the two targets also have equal prior mass, they are equally likely given this sample. They disagree at , which has mass , so every learner has conditional expected error at least , and hence expected error at least . Products of disjoint copies give every dimension (Theorem A.1), and the same classes give the Littlestone lower bounds (Appendix A.4).
I remain unconvinced by the authors' response to weakness 1. Both Hanneke's and Larsen's results represent groundbreaking advancements in PAC learning. However, this does not necessarily imply that the contribution of this paper is equally significant. Their results characterize the exact sample complexity for every hypothesis class. In contrast, as I pointed out in my original review, the lower bound in this paper is established for a deliberately constructed hypothesis class. Therefore, the resulting rate is optimal only under the paper's definition of risk, which takes the supremum over all hypothesis classes with VC dimension . The result thus only shows that the logarithmic factor is necessary in the worst case, but does not answer when this factor is necessary. Therefore, my concern regarding the significance of the result remains.
That said, I appreciate the proof overview provided in the rebuttal, which helps clarify the overall proof strategy. I encourage the authors to incorporate a more detailed technical overview into the paper and to improve the organization of the proof in Section 3.1, for example, by breaking it down into separate lemmas rather than presenting the entire argument as a single proof.
In light of the improved clarity provided by the rebuttal, I will raise my score accordingly.
Thank you for your follow-up
Thank you for your follow-up, for reconsidering your assessment, and for your willingness to raise your score.
We will expand the proof overview in the paper and reorganize Section 3.1 into separate lemmas, as you suggest.
You are correct that our lower bound is worst-case over classes of a given dimension. Characterizing which individual classes incur the logarithmic penalty remains an interesting open question. Our comparison with Hanneke’s and Larsen’s results was meant to illustrate the importance of logarithmic factors in learning theory, rather than to equate the significance of the contributions. Our result answers the question posed by Larsen et al.: whether the clean rate can be recovered for every VC class under monotone insertions. We agree that it does not characterize the optimal rate for each individual class, as we also mention in the paper.
We are glad that the proof overview helped clarify the argument, and we appreciate your suggestions for improving its presentation in the paper.
Response to Reviewer gbyq (1/2)
Thank you for your review and for recognizing that the lower bound applies to every learner and gives two important separations. We address your comments below and hope these clarifications will strengthen your support for the paper.
Weakness 1: “The results do not look very significant. It only differs from PAC learning by a logarithmic factor.”
We agree that the difference is a logarithmic factor. That said, we respectfully disagree that this makes the results less significant. In classical PAC learning, the same factor separates a generic ERM from optimal learners, and removing it was a substantial research direction, including Hanneke's optimal sample-complexity result and Larsen's Bagging is an Optimal PAC Learner, which received the COLT 2023 Best Paper Award.
Under monotone insertions, prior lower bounds ruled out only particular algorithms, and Larsen et al. (2026) asked, as their first open question, whether a better learner could recover the clean rate. Our lower bound rules this out for all learners, including randomized and improper ones, and establishes that the generic ERM rate is worst-case optimal. The dimension-one upper bound identifies a sharp exception, while the Littlestone result shows that a finite online mistake bound does not restore the clean rate.
Weakness 1: “Moreover, the lower bound is proven for a deliberately constructed hypothesis class […]. It is not a result for generic hypothesis classes.”
The classes are indeed constructed for the lower bound. This is necessary because a logarithmic lower bound for every class of dimension at least two would be false. For example, indicators of subsets of size at most d have both VC and Littlestone dimension d, but predicting one exactly at observed positive points gives expected error at most d/(n+1), even after arbitrary correct insertions. This follows from the leave-one-out argument in the proof of Proposition 3.12, since this learner errs on at most d of the n+1 held-out points.
Our classes are based on finite projective planes, in which every two distinct points lie on a unique line and every two distinct lines meet at a unique point. As we note after Theorem 3.5, these are classical examples of range spaces of VC dimension two, and they have found several applications in prior work. Alon, Haussler, and Welzl (1987) used them to show limitations of partition methods in computational geometry. In learning theory, they have been used to prove embedding obstructions (Ben-David et al., 2002), sign-rank lower bounds (Alon et al., 2016), and results on list replicability (Blondal et al., 2026). We adapt the same incidence structure to our model, using incident point–line pairs as domain elements. This structure gives exactly the property our proof needs: every point in the support of a target's distribution can be flipped, that is, some other target of the same prior weight disagrees with it at that point and agrees with it on the rest of both supports. At the same time, the projective-plane axioms keep the VC dimension at two (Lemma 3.7). That our proof relies on this specific structure is itself informative, as it may hint at the right characterization of the rate of an individual class, which remains an interesting open question. We will include an expanded discussion of this property in the paper.
Weakness 1: “[The lower bound] requires appending m≈n2 examples.”
The model of Larsen et al. (2026) allows the adversary to append any finite number of examples, and our main theorem gives the optimal rate in the worst case over such budgets. Worst-case rates of this kind are standard in learning theory, one of ICLR's primary areas. Some growth of the budget is also necessary for a logarithmic penalty: Remark 3.2 shows that constant budgets retain the clean rate.
That said, we can improve the budget of our dimension-two construction from m=n(2k−3)=Θ(n2/log(en)) to exactly m=n, with the same lower bound, as we detail in our response and technical follow-up to Reviewer nXHt. The idea is to append one paired example for each clean observation so that the two possible targets produce the same labeled multiset with equal likelihood. The argument also covers the higher-dimensional and Littlestone lower bounds, and we will add it to the paper. The optimal dependence on m between constant and linear budgets remains open.