Learning with Monotone Adversarial Corruptions

1 Introduction

• An adaptive monotone adversary adds arbitrarily chosen points after observing n i.i.d. clean examples, labels every point with the ground-truth hypothesis, and evaluates learners on the clean distribution.The model preserves label correctness while breaking exchangeability between clean and added data.Source: §1 · p. 1

1.1 Our Contributions

• The OIG leave-one-out algorithm suffers expected error 1/4 with n clean and n corrupted points, even for VC dimension 1.This contrasts with the standard Θ(d/n) benchmark and shows constant error under monotone corruption.Source: §1 · p. 1, §1.1 · p. 2
• Any majority voting algorithm using subsets of size at least t can suffer Ω(d log(n/d)/n) error with 2n/t corrupted points; known optimal instances therefore fail under few corruptions.The three cited optimal majority-voting algorithms use t = Ω(n), so their lower bound applies with a constant number of corrupted samples.Source: §1.1 · p. 2
• Every ERM achieves expected error O(d log(n/d)/n) under any monotone adversary and arbitrary numbers of corrupted points.Because corrupted labels remain consistent with the ground truth, uniform convergence preserves this guarantee; a matching ERM lower bound already holds without corruptions.Source: §1.1 · p. 2
• When corruptions are oblivious to the clean sample, OIG recovers the optimal expected error O(d/n).This isolates adaptivity and the resulting loss of exchangeability as the obstacle to the optimal guarantee.Source: §1.1 · pp. 2–3

1.2 Future Directions

• The optimal expected error for binary VC classes under adaptive monotone corruption remains unresolved because no general lower bound rules out O(d/n) and no method removes ERM’s logarithmic factor.Further open problems concern Littlestone classes, partial or multiclass classes, and computationally efficient learning when VC dimension is unbounded.Source: §1.2 · pp. 3–4

1.3 Related Work

• The model differs from online and transfer-learning settings by targeting clean-distribution test error, while related offline corruption models allow corruptions to depend on the test point [GHMS23] [BHQS21] [HKM+22] [BHPS23].Its name connects to semirandom models in which seemingly helpful perturbations can nevertheless make recovery harder.Source: §1.3 · pp. 4–5

2.1 The Monotone Adversary

• The monotone adversary adaptively adds points to i.i.d. clean samples, labels every point using h⋆, and randomly permutes the combined dataset.The learner is evaluated by expected error on a new test point from D, while the added points break independence and exchangeability despite having honest labels.Source: §2.1 · p. 5

2.1.1 Oblivious Monotone Adversary

• An oblivious monotone adversary generates corrupted points independently of the clean sample while retaining knowledge of D, H, and h⋆.This is a weaker adversary than the adaptive model because it cannot inspect the clean points before generating additions.Source: §2.1.1 · p. 5

2.2 Learning Algorithms

• ERM outputs a hypothesis in H consistent with every labeled training example, providing the standard baseline for binary classes with VC dimension d.The textbook ERM guarantee cited here applies when the training inputs are i.i.d. from D.Source: §2.2 · p. 5
• Majority voters train multiple ERMs on selected subsamples and classify by majority vote, encompassing Hanneke’s algorithm, Bagging, and Majority-of-Three.Their subsample size is the parameter used to characterize the majority-voting lower bound later in the paper.Source: §2.2 · p. 6
• The One-inclusion Graph algorithm predicts through an orientation of hypothesis-induced label graphs, choosing the test label from the edge joining the two possible extensions.A structural theorem guarantees an orientation with maximum out-degree at most d for classes of VC dimension d.Source: §2.2 · p. 6

• The optimal achievable expected error remains O(d/n), matching the standard i.i.d. lower bound.Source: §3 · p. 6
• ERM achieves expected error O(d log(n/d)/n) under any monotone adversary, even with an arbitrary number of corrupted points.Source: §3 · p. 6
• For oblivious monotone adversaries, OIG achieves expected error O(d/n) because corrupted points are independent of the clean sample.Source: §3 · p. 7
• The OIG proof uses exchangeability of the clean points after conditioning on the permutation and corrupted data, then bounds the target vertex out-degree by d.Source: §3 · pp. 7–8
• The oblivious-adversary OIG guarantee holds for any orientation minimizing the one-inclusion graph's maximum out-degree.Source: §3 · p. 8

4 Lower Bounds

• The lower-bound constructions use coupon-collector behavior to leave many clean-domain points unseen, enabling monotone samples to induce incorrect predictions.Source: §4 · p. 8, §4.1 · p. 9

4.1 Lower Bounds against Majority Voting Strategies

• The majority-voting lower bound applies to both a deliberately adversarial ERM and a uniformly random consistent ERM, with the latter requiring only a constant number of corruptions.Source: §4.1 · pp. 8, 10
• Any majority voter using subsets of size at least t can be forced to incur expected error Ω(d log(n/d)/n) using m = 2n/t corrupted samples.Source: §4.1 · p. 9

4.2 Lower Bound against One-Inclusion Graph Algorithms

• OIG can suffer expected error 1/4 with n clean and n corrupted samples, even for VC dimension 1.Source: §4.2 · pp. 10–11
• With m = cn/log(n/k) corruptions, OIG suffers expected error Ω(k log(n/k)/n) for 1 ≤ k ≤ c^-1n.Source: §4.2 · pp. 10–11

• For r = cn/log(n/d), n uniform samples leave at least d of the r elements unseen with probability at least 1/2.Source: A Proofs of Auxiliary Results · pp. 13–14