acceptodds
Under review as a conference paper at ICLR 2027

Optimal Rates for Learning with Monotone Adversaries

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 et al. (2026), who introduced this model, showed that empirical risk minimization attains expected error for classes of VC dimension , and that every known optimal learner can be pushed away from the rate, which is 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 and over known finite insertion budgets, the minimax expected error is at and for . The same rates hold with Littlestone dimension in place of , so the clean online-to-batch rate 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 hypotheses, which differ at a point of nonnegligible mass, produce the same sample.

Primary area:
learning theory
Keywords:
statistical learning theory, monotone adversaries, PAC learning, VC dimension, Littlestone dimension, minimax rates

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_gbyqOpenReview ↗
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 nn i.i.d. examples. The learner receives all these examples, without knowing which are clean or adversarial. For a hypothesis class with VC dimension dd, the empirical risk minimization rule solves this problem with an expected error rate of O((d/n)log⁡(n/d))O((d/n) \log (n/d)), larger than the O(d/n)O(d/n) bound in PAC learning by a factor log⁡(n/d)\log(n/d). The goal of this paper is to investigate whether this extra factor is necessary.

The main result is that for every 2≤d≪n2\le d \ll n, there exists a hypothesis class with VC dimension dd such that no learner can have an expected error better than Ω((d/n)log⁡(n/d))\Omega((d/n) \log (n/d)). Thus, the extra factor is unavoidable in general. The authors also propose an algorithm that achieves O(1/n)O(1/n) error when d=1d=1, indicating that this factor can be eliminated for classes with VC dimension one. The authors also prove analogous results with dd replaced by the Littlestone dimension.

Critical strengths
  1. 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.

  2. Separation: The results demonstrate two important separations. First, the lower bound for d≥2d\ge 2 shows a separation between PAC learning and learning with a monotone adversary: their error rates can differ by a factor of log⁡(n/d)\log(n/d) for some classes. Second, they separate d≥2d\ge 2 from the d=1d=1 case, by showing that a learner never pays the extra factor when d=1d=1.

Critical weaknesses
  1. 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 m≈n2m\approx n^2 examples. It is not a result for generic hypothesis classes.

  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.

Questions for authors

None

4 comments
AuthorsOpenReview ↗

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 dd have both VC and Littlestone dimension dd, but predicting one exactly at observed positive points gives expected error at most d/(n+1)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 dd of the n+1n+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≈n2m\approx n^2 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))m=n(2k-3)=\Theta(n^2/\log(en)) to exactly m=nm=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 mm between constant and linear budgets remains open.

AuthorsOpenReview ↗

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 kk points. The row target upu_p and the column target vLv_L of each flag f=(p,L)f=(p,L) (an incident point–line pair) disagree at exactly one point of their supports, cpLc_{pL} (Observation 3.8), and a fixed labeled set rules out every other target (Observation 3.6). With our choice of kk, some support point is missing from the clean sample with probability at least 2/32/3 (Lemma 3.9). The adversary then picks a missing point, say cpLc_{pL}, and adds correctly labeled examples so that upu_p and vLv_L 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 cpLc_{pL}, which has mass 1/k1/k, so every learner has conditional expected error at least 1/(2k)1/(2k), and hence expected error at least 1/(3k)≥log⁡(en)/(30n)1/(3k)\geq\log(en)/(30n). Products of disjoint copies give every dimension d≥3d\geq 3 (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 dd. 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.

AuthorsOpenReview ↗

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.

Reviewer_nXHtOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper shows optimal rates for learning under an adversary with cleanly labeled corruptions, mixed in with the training data. They show that the upper bounds of the prior work are tight, and that an additional logarithmic factor could not be removed. They also show a tight upper bound for the single dimensional case.

Critical strengths

The paper cleanly resolves questions provided in prior work, and is generally well written and human readable.

Critical weaknesses

The results, while clean, are somewhat limited in scope, and don't seem to provide novel techniques that might help with future results.

Questions for authors

Do you have thoughts on "the optimal dependence on m between the bounded-budget and worst-case regimes"?

Are there any other notable open questions left by this work?

4 comments
AuthorsOpenReview ↗

Response to Reviewer nXHt

Thank you for your positive assessment and for recognizing that the paper resolves the questions posed in prior work. We answer your questions below and hope you will retain your support for the paper.

“Do you have thoughts on ‘the optimal dependence on mm between the bounded-budget and worst-case regimes’?”

That is a good question. In our submission, we leave a gap between logarithmic and nearly quadratic budgets: for VC dimension d=2d=2, Remark 3.2 gives an upper bound of O((m+1)/n)O((m+1)/n) on the expected error, so m=Ω(log⁡n)m=\Omega(\log n) is necessary to force the full Θ(log⁡n/n)\Theta(\log n/n) rate, while our construction shows that m=Θ(n2/log⁡n)m=\Theta(n^2/\log n) suffices.

Using a different, slightly more involved argument, we can tighten this gap so that m=nm=n insertions suffice for the same lower bound. We give this argument in the technical follow-up below and will add it to the paper. We used the simpler construction in the submission because it suffices for the worst-case rate. The remaining gap is between logarithmic and linear budgets. Determining the smallest sufficient budget in this range, and more generally the optimal error as a function of mm, remains an interesting open question.

“Are there any other notable open questions left by this work?”

Yes, several questions remain open. For binary classes, these include the optimal dependence on the budget discussed above, optimal high-probability bounds, and which properties of a class determine its rate, since classes of the same dimension can have different rates (see our response to Reviewer gbyq). For multiclass and partial classes, Asilis, Dughmi, and Pabbaraju (2026), already cited in our introduction, show that monotone insertions can destroy learnability, and it remains open which classes stay learnable and at what rates. We would be happy to expand this discussion in the paper.

“The results, while clean, are somewhat limited in scope, and don't seem to provide novel techniques that might help with future results.”

We respectfully disagree. Our arguments are elementary, which we view as a strength, as it suggests that they may be useful beyond our results.

Moreover, the class behind our lower bound is not ad hoc: it comes from finite projective planes, classical examples of VC dimension two that have found several applications in prior work (see our response to Reviewer gbyq). Our proof uses a specific property of this construction: 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. In other simple examples where the clean rate holds (e.g., the one proposed by Reviewer kQLW), this property fails. As a result, we think that this property may hint at the right characterization of the rate of an individual class. We will include an expanded discussion of this property in the paper.

AuthorsOpenReview ↗

Technical follow-up to Reviewer nXHt: the refinement to m = n

This note supports our answer to your first question. Our response to Reviewer gbyq on the insertion budget also refers to it. It shows that the bound of Theorem 3.5 holds with exactly m=nm=n insertions, for the same class, prior, and choice of kk.

High-level idea. Recall how the lower bound works. For each flag f=(p,L)f=(p,L), the row target upu_p and the column target vLv_L disagree at exactly one point of their supports, cpLc_{pL} (Observation 3.8). When this point is missing from the clean sample, the adversary can add correctly labeled examples so that the two targets produce the same final sample with the same probability. The learner then cannot tell the targets apart, although they disagree at a point of mass 1/k1/k. In the submission, the adversary pads every point of the two supports other than cpLc_{pL} to multiplicity nn, so both targets produce the same fixed multiset. This costs Θ(n2/log⁡n)\Theta(n^2/\log n) insertions. The refinement instead appends one paired example for each clean observation: it fixes a bijection between the two supports with cpLc_{pL} removed and, for each clean point, appends the corresponding point of the other support. The two targets agree on all these points, so the insertions are correctly labeled, and paired clean samples produce the same final labeled multiset with the same probability.

Adversary. For a flag f=(p,L)f=(p,L), let RpR_p and CLC_L be the supports of DprowD^{\mathrm{row}}_p and DLcolD^{\mathrm{col}}_L. They share only the point cpLc_{pL} and both have kk points, so we can fix a bijection ϕf:Rp∖cpL→CL∖cpL\phi_f:R_p\setminus\\{c_{pL}\\}\to C_L\setminus\\{c_{pL}\\}. Under the target upu_p, if some point of RpR_p is missing from the clean sample, the adversary picks a missing point uniformly at random, say cpLc_{pL}, and appends ϕf(x)\phi_f(x) with label one for each of the nn clean points xx. Under the target vLv_L, it picks a missing point of CLC_L uniformly at random, say cpLc_{pL}, and appends ϕf−1(x)\phi_f^{-1}(x) with label zero for each clean point xx. By Observation 3.8, both targets assign these labels, so every appended example is correctly labeled. If no point is missing, the adversary appends nn copies of the first clean example.

Equal likelihoods. Fix ff and an ordered sequence ss of nn points of RpR_p that misses cpLc_{pL}, and let z(s)z(s) be the number of points of RpR_p that ss misses. Since ϕf\phi_f is a bijection, ϕf(s)\phi_f(s) misses exactly z(s)z(s) points of CLC_L, including cpLc_{pL}. Writing SS for the clean sample and FF for the selected flag,

Pr⁡S=s,,F=f∣h⋆=up=k−nz(s)=Pr⁡S=ϕf(s),,F=f∣h⋆=vL,.\Pr\\{S=s,\\,F=f\mid h^\star=u_p\\}=\frac{k^{-n}}{z(s)}=\Pr\\{S=\phi_f(s),\\,F=f\mid h^\star=v_L\\}\\,.

In both cases, the final labeled multiset consists of ss with label zero and ϕf(s)\phi_f(s) with label one. The two targets have equal prior mass and the shuffle is uniform, so given the learner's input, and even given ff, each target has posterior probability 1/21/2.

Lower bound. The two targets disagree at cpLc_{pL}, which has mass 1/k1/k under both distributions, so the conditional expected error is at least 1/(2k)1/(2k). With our choice of kk, some support point is missing with probability ρ≥2/3\rho\geq 2/3 (Lemma 3.9), so every learner has expected error at least ρ/(2k)≥log⁡(en)/(30n)\rho/(2k)\geq\log(en)/(30n), as in the proof of Theorem 3.5. Fixing the target, the distribution, and the adversary's random choices then gives a deterministic adversary.

Higher dimensions. In the product construction of Appendix A.3, if block ii receives NiN_i clean points, the adversary applies the same rule within block ii and appends NiN_i examples, so it appends ∑iNi=n\sum_iN_i=n examples in total. Conditional on the block counts, the identity above holds in every block with a missing point, and the rest of the proof of Theorem A.1 is unchanged. The classes are the same, so the Littlestone dimension calculation in Appendix A.4 also applies.

Thank you for your response.

With the additional intuition and overview for the lower bound being especially helpful and would make a strong addition to the paper (with some expansion as you mentioned in your response to gbyq). I also appreciate the additional discussion of related open questions. Based on the assumption that the promised additions to camera ready version will be added, I will raise my score.

AuthorsOpenReview ↗

Thank you for your follow-up

Thank you for your follow-up and continued support. We also appreciate your willingness to raise your score.

We are glad that the additional intuition and overview were helpful. We will incorporate the expanded technical overview, a map of the proof dependencies, and the discussion of open questions into the revised paper, as promised. We will also include the refinement to exactly m=nm=n insertions and its proof. Thank you again for your time and helpful suggestions.

Reviewer_kQLWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In this paper, the author investigates the optimal learning rates against monotone adversaries. Equivalently, if there is an adversary that can generate some redundant data with clean labels, how bad can the mistake bound be under this type of attack? This is a natural and interesting question to help us understand the robustness of our learning algorithms. This paper proves that for every natural number d≥2d \geq 2, there always exists a concept class with VC dimension dd, and there exists an adversary that forces any learning algorithm to have at least d/nlog⁡(n/d)d/n\log(n/d) error rate, which is a log⁡(n/d)\log(n/d) deterioration compared to the optimal PAC learner.

Critical strengths

This is an interesting problem in the robust learning area and helps us to understand the ability of clean-label attacks from the error-rate perspective.

Critical weaknesses

The writing of this paper is not in very good shape. First, the author provides insufficient intuition for the counterexample's construction. Second, the statement of the construction and its proof are a little hard to follow.

Questions for authors

If we change the construction to the following: for every n∈Nn\in \mathbb{N}, let k≈n/log⁡(n)k \approx n/\log(n) and X={1,…,k}\mathcal{X} = \lbrace1,\ldots,k\rbrace, H={hj:hj(i)=1(i=j)}∪{0}\mathcal{H} = \lbrace h_j: h_{j}(i) = 1(i=j)\rbrace \cup \lbrace 0 \rbrace, where 00 is the all-zero function. D\mathcal{D} is the uniform distribution on X\mathcal{X}. h∗h^* is uniformly randomly drawn from H\mathcal{H}. Which part of the proof breaks? I think this would be helpful for readers to understand the tricky part of the proof.

3 comments
AuthorsOpenReview ↗

Response to Reviewer kQLW

Thank you for your positive assessment and for recognizing that the problem helps to understand clean-label attacks. We answer your question and comment below and hope this clarifies the intuition behind our lower bound.

“If we change the construction to the following: for every n∈Nn\in\mathbb{N}, let k≈n/log⁡(n)k\approx n/\log(n) and X=1,…,k\mathcal{X}=\\{1,\ldots,k\\}, H=hj:hj(i)=1(i=j)∪0\mathcal{H}=\\{h_j:h_j(i)=1(i=j)\\}\cup\\{0\\}, where 00 is the all-zero function. D\mathcal{D} is the uniform distribution on X\mathcal{X}. h⋆h^\star is uniformly randomly drawn from H\mathcal{H}. Which part of the proof breaks? I think this would be helpful for readers to understand the tricky part of the proof.”

Thank you for this suggestion. In this example, the logarithmic lower bound does not hold because the learner can identify the target as soon as its “positive point” appears in the sample. Concretely, consider the learner that returns hjh_j if the sample contains (j,1)(j,1) and returns zero otherwise. Its expected error is at most 1/(n+1)1/(n+1), regardless of the insertion budget mm.

Indeed, for target hjh_j, it can make an error only if jj is absent from the clean sample. Writing pj=D(j)p_j=D(j), its expected error is at most pj(1−pj)n≤1/(n+1)p_j(1-p_j)^n\leq 1/(n+1). Correctly labeled insertions can only help this learner, and it makes no errors when the target is zero. For your uniform input distribution and a fixed nonzero target, the bound is (1/k)(1−1/k)n(1/k)(1-1/k)^n, or (1/(k+1))(1−1/k)n(1/(k+1))(1-1/k)^n after averaging over the uniform prior. The bound 1/(n+1)1/(n+1) is also a special case of Proposition 3.12: the above class has VC dimension one, and this learner is precisely the consensus rule in the proof of Proposition 3.12 with f≡0f\equiv 0.

For our lower-bound argument, we need a point that, roughly speaking, the clean sample misses and at which the learner cannot tell two targets apart (equation (2)). For a singleton target hjh_j, only the positive point jj can play this role. Since the target is fixed before sampling, this point is missing with probability only (1−1/k)n(1-1/k)^n, even when some point is missing with high probability. In our construction, every point in the support of the target's distribution can play this role, and this is a crucial property of our construction.

“First, the author provides insufficient intuition for the counterexample's construction. Second, the statement of the construction and its proof are a little hard to follow.”

We will add a short technical overview with the comparison above and a map of the proof dependencies. Our response to Reviewer gbyq (Weakness 2) gives a short version of the overview.

Thanks to the authors for their kind reply. This reply is exactly what I want to see in the paper. This will provide a more natural intuition for why this lower bound needs at least VC=2, given that the rough idea is also based on the fact that if we miss one point in the training data, we will make a mistake with a probability large enough.

I appreciate the author and will keep my positive evaluation.

AuthorsOpenReview ↗

Thank you for your follow-up

Thank you for your follow-up and continued support. We are glad that the comparison with your singleton example clarified the intuition behind the lower bound. We will include this comparison in the paper, together with the expanded technical overview, to explain the distinction between VC dimension one and two. Thank you again for suggesting this example and helping us improve the presentation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.