PaperlayerView exact revision on arXiv

Source-linked AI summary

When Clean Data Hurts: Learning with Monotone Corruptions Beyond Binary Classification

Julian Asilis, Shaddin Dughmi, Chirag Pabbaraju

arXiv:2608.20480v1cs.LGstat.ML

TL;DR

Classical learners rely on clean i.i.d. data, but monotone corruption leaves the consequences for multiclass and partial binary learning unresolved. The paper constructs adaptive attacks that make learnable problems unlearnable and proves that sublinear additions preserve learnability, with further guarantees for restricted adversaries.

  • Problem

    The paper asks whether classically learnable multiclass and partial binary problems remain learnable when correctly labeled but otherwise arbitrary examples are added adversarially.

  • Method

    The paper analyzes adaptive, semi-adaptive, and oblivious monotone additions across multiclass, partial binary, proper-learning, and ERM settings.

  • Results

    Adaptive additions can destroy learnability in a DS-dimension-2 multiclass class and a partial binary class, while every o(n) adaptive budget preserves ordinary learnability.

  • Takeaways & Limitations

    The linear scale is a sharp threshold for adaptive additions, while constant-budget, semi-adaptive, and oblivious adversaries retain the classic multiclass rate in the stated settings.

  • Takeaways & Limitations

    Proper learning remains possible at fixed accuracy and confidence, but its sample complexity can deteriorate faster than any prescribed function; complete nonlearnability requires a separate construction.

Abstract

from arXiv · show

Optimal learners are tailored to exploit the i.i.d.\ data assumption underlying the classic PAC model. What if an i.i.d.\ training sample were corrupted with correctly labeled examples drawn from an otherwise unrelated, even adversarial source? This model of learning with monotone adversarial corruptions was recently introduced by Larsen et al. (2026), who demonstrated that all known optimal binary learners suffer increased error rates in this setting, from $O(d / n)$ in the PAC model to $Ω(d \log(n / d) / n)$ under monotone corruption. Mehrotra (2026) proved this logarithmic factor to be necessary for binary classification, but left open the consequences of corruption for more general learning settings, such as multiclass classification and partial binary concept classes. As our primary result, we demonstrate that monotone adversaries are frighteningly more powerful in each of these settings. We exhibit a learnable multiclass problem, of DS dimension only 2, that becomes altogether unlearnable under a monotone adversary, and show an analogous result for partial binary concept classes. These results are achieved by an adaptive adversary permitted to view the original i.i.d.\ training set $S$ and to insert $b < \infty$ corrupted datapoints into $S$. In the multiclass example, the adversary need only insert a linear number $b = |S| = n$ of datapoints. We complement these impossibility results by proving that every class remains learnable when the number of adaptive additions is $o(n)$, which our previous multiclass lower bound proves to be tight. We further observe that the classic multiclass error rate of $O(d_{\mathrm{DS}} / n)$ remains achievable against adaptive adversaries restricted to a known constant budget $b = O(1)$, against semi-adaptive adversaries viewing only a $p$-fraction of $S$ for $p \in (0, 1)$, and against oblivious adversaries that cannot view $S$.

1 Introduction

Monotone corruption appends correctly labeled but arbitrary examples to clean i.i.d. data, raising open questions beyond binary classification. This paper shows adaptive additions can destroy learnability in multiclass and partial binary settings, while restricted additions preserve important guarantees.

  • Problem: Monotone corruption appends correctly labeled, otherwise arbitrary examples to an i.i.d. sample and evaluates learners on the untouched data distribution.The adversary may view the clean sample, depending on its type, before adding examples.
  • Prior work: Binary optimal error worsens from O(d/n) to Ω(d log(n/d)/n) under monotone corruption, and the logarithmic penalty is necessary.These results complete the binary picture by making ERM optimal in the monotone setting.
  • Scope: Multiclass and partial binary learnability have combinatorial characterizations but can exceed the capabilities of proper learners and ERM.Their learnability is characterized by DS dimension and partial VC dimension, respectively.
  • Primary results: Adaptive additions destroy learnability for a multiclass class of DS dimension 2 and for a partial binary class of partial VC dimension at most 18.The multiclass adversary uses exactly n additions, while the partial-binary construction uses finitely many insertions.
  • Primary results: Every o(n) adaptive addition budget preserves ordinary learnability, establishing a sharp threshold between sublinear and linear-scale additions.The multiclass lower bound uses n additions, matching the threshold order.
  • Learner restrictions: Oblivious additions can increase proper-learning sample complexity by arbitrarily large amounts, while some ERM learners fail after linearly many oblivious additions.The paper leaves open whether proper multiclass learnability can be destroyed altogether by an oblivious adversary.

2 Preliminaries

The paper formalizes monotone corruption by appending correctly labeled examples to an i.i.d. clean sample and distinguishes adversaries by what they observe. Learnability and learner restrictions are measured using established multiclass and partial-binary dimensions.

  • Monotone model: A clean sample contains n i.i.d. examples labeled by a target h⋆, after which the adversary appends a finite labeled multiset and shuffles the union.The learner is evaluated on the untouched marginal distribution.
  • Learnability: Multiclass PAC learnability is characterized by DS dimension, while binary partial-concept learnability is characterized by partial VC dimension.The paper also distinguishes proper learners, which output members of H, from improper learners.
  • One-inclusion tool: If dDS(H)=d<∞, every finite projection of H admits a one-inclusion orientation whose nodes have outdegree at most d.This theorem is used as a black box in the paper's learning guarantees.
  • Adversary types: An adversary is oblivious, semi-adaptive, or fully adaptive according to whether it sees none, m selected clean positions, or all n clean examples.A budget-b adversary may insert at most b examples.
  • Partial concepts: For partial concepts, realizable distributions avoid undefined labels, and monotone adversaries may insert only nonstar examples.The domain of h consists of points labeled 0 or 1.

3 Destroying Learnability with Adaptive Adversaries

The paper shows that adaptive monotone adversaries can destroy learnability in multiclass and partial binary settings, while also deriving sharp constructions and lower bounds for restricted settings. The core mechanism is to make corrupted transcripts indistinguishable across targets that disagree on substantial test mass.

  • 3.1 Multiclass learnability can be destroyed: A multiclass class with DS dimension 2 is cleanly properly PAC learnable but becomes unlearnable after exactly n adaptive additions.The adversary appends one correctly labeled example per clean example and constructs identical corrupted transcripts for indistinguishable target worlds.
  • 3.1 Multiclass learnability can be destroyed: The lower bound pairs neighboring hypotheses whose corrupted transcripts are identical although they disagree on common points carrying half the test mass.The adversary selects a halfset avoiding observed tags, then mirrors each clean example under the neighboring target.
  • 3.2 Binary partial-concept learnability can be destroyed: A partial binary class with partial VC dimension at most 18 likewise becomes nonlearnable under a finite adaptive budget of nonstar insertions.The construction replaces a neighboring multiclass pair with a cyclic line of partial binary targets while preserving indistinguishable labeled transcripts.
  • 3.3 Price of adaptivity at DS dimension one: At DS dimension 1, adaptive corruption already raises multiclass risk from O(1/n) clean risk to Ω(log n/n), and d-fold products yield Ω(d log(1 + n/d)/n).A portal construction uses a missing color and one mirrored insertion per clean example; products preserve dimension d and amplify the lower bound.
  • Restricted adversaries: The resulting boundary is sharp for adaptive additions: every o(n) budget preserves ordinary PAC learnability, whereas linear additions can destroy it.Restricted adversaries and the multiclass lower bound identify the linear scale as the threshold for universal preservation versus impossibility.

4 When Monotone Additions Are Harmless

Monotone additions are harmless under oblivious or partially visible adversaries, and every sublinear adaptive budget preserves learnability. With a known budget, random thinning or partition-based aggregation provides explicit robustification guarantees.

  • Exchangeable clean reserves: d_DS/(r + 1) bounds expected error when r clean examples remain exchangeable with a fresh test point.The learner need not know which observed examples form this exchangeable reserve.
  • Oblivious adversaries: Arbitrarily many oblivious additions preserve the optimal multiclass rate because clean examples remain exchangeable with a fresh test point.This extends the binary result of Larsen et al. (2026) to multiclass learning.
  • Semi-adaptive adversaries: d_DS/(n −m + 1) bounds error against an m-semi-adaptive adversary, so finite-DS classes remain learnable with a hidden clean reserve.If the adversary observes at most a fixed p-fraction, p < 1, the O(d_DS/n) rate survives up to 1/(1 −p).
  • Sublinear adaptive additions: Every adaptive budget b_n = o(n) preserves ordinary PAC learnability, and preserves proper learnability whenever clean proper learning is achievable.Randomly retaining a small subsample works because the probability of selecting corrupted points vanishes with b_n/n.
  • Sharp threshold: n additions can force constant minimax error for a properly learnable multiclass class of DS dimension two, making the linear threshold sharp.Thus sublinear adaptive additions are universally harmless, while a linear budget can destroy learnability.
  • Known-budget robustification: O(d(b + 1)/(n + b)) bounds robust error when a known budget enables partitioning into 4b + 1 groups and plurality aggregation.At most b groups are contaminated, so plurality reduces robust risk to the ordinary risk of a clean-group learner up to a factor below four.

5 Proper Learning and ERM

Restricting learners to proper rules or ERM can make monotone corruption far more damaging than it is for unrestricted learning. The paper shows arbitrarily severe proper-learning degradation and sharp ERM failures while preserving some learnability guarantees.

  • Proper learning: Oblivious additions can make proper learning arbitrarily expensive even when unrestricted learning remains essentially unaffected.The witnessing classes are countable, closed, and have finite coordinatewise range.
  • Proper learning: F(1/δ) lower-bounds proper sample complexity for every nondecreasing F, while the constructed class remains properly PAC learnable against arbitrary adaptive additions.The degradation is quantitative rather than qualitative: fixed accuracy and confidence remain achievable.
  • Scope boundary: The proper-learning lower bound does not destroy learnability: complete destruction requires the separate masked-table construction.The theorem establishes unbounded sample-complexity deterioration, not a qualitative impossibility result.
  • ERM failures: Oblivious additions can force constant error for every ERM on a class with DS dimension one, despite ordinary proper ERM learnability.The adversary uses at most αn additions, with the lower bound of order e^−1/α.
  • ERM failures: A single adaptive positive example can eliminate the universally safe ERM output and expose tie-breaking, worsening error by the full logarithmic factor.ERM learnability survives under arbitrary adaptive additions, but the clean ERM rate need not.
  • ERM failures: One adaptive addition can force every randomized ERM to incur expected error Ω(log n/n) for infinitely many n on a binary class of VC dimension two.The construction uses incidence hypotheses on complete-graph edges and an isolated-vertex argument.

6 Conclusion

The paper shows that monotone corruption can destroy learnability beyond binary classification, while several weaker corruption regimes preserve learning. It identifies unresolved questions about error-rate dependence and combinatorial characterizations in the monotone model.

  • Adaptive monotone additions can make learnable multiclass and partial binary problems altogether unlearnable.Oblivious additions remain benign for general learners, although they can substantially increase proper-learning sample complexity.
  • The paper leaves the precise dependence of monotone error rates on budget b unresolved in both multiclass and partial binary learning.
  • Robust replacements for DS and partial VC dimensions that characterize monotone learnability remain open.Even useful sufficient conditions weaker than uniform convergence would be notable progress.

AI disclosure

The paper reports that ChatGPT 5.6 Pro and Sol Max contributed substantially to developing several results, including proving a theorem and generating counterexamples.

  • ChatGPT 5.6 Pro and Sol Max played a significant role in developing several results.Their contributions included proving Theorem 5.1 after modifying an author-designed construction and producing counterexamples for multiclass and partial binary settings.
  • The models were prompted to modify a poisoned first-Cantor construction and to produce counterexamples demonstrating destroyed learnability.
  • The first-Cantor construction used by the authors was itself based on the first Cantor class of Daniely and Shalev-Shwartz (2014).

Appendix A Proofs for Harmless Regimes

The appendix proves positive learning guarantees under several restricted corruption regimes by preserving exchangeability, recovering clean subsamples, or aggregating across mostly clean groups. These mechanisms yield vanishing risk for o(n) additions and explicit multiclass bounds for bounded budgets.

  • Exchangeable reserves: At most d leave-one-out predictions are incorrect, giving expected error at most d/(r + 1) under exchangeability.The argument applies the canonical one-inclusion rule after withholding each coordinate in turn.
  • Exchangeable reserves: Oblivious additions and partially revealed samples retain exchangeability among clean examples and a fresh test point, enabling the same one-inclusion guarantee.
  • o(n) adaptive additions preserve ordinary learnability, and this threshold is tight by the multiclass lower bound.A slowly growing subsample size balances clean risk and contamination probability; properness is preserved when the base learners are proper.
  • Partition-based aggregation: Random partitioning into r = 4b + 1 groups leaves at least r − b clean groups, which are combined through plurality aggregation.
  • Partition-based aggregation: O(d(b + 1)/(n + b)) risk is achieved for multiclass learning using partition-based aggregation.The bound follows from the ordinary one-inclusion rate O(d/(t + 1)) on clean groups.
  • List aggregation: A list learner achieves failure probability at most 2^-s with list size b + O(log(1/δ)) using O((d/ε)(b + log(1/δ))) clean examples.At least s groups are clean, and independent learner randomness makes their predictors independent.

Appendix B Multiclass Lower Bound

The appendix constructs a countable multiclass hypothesis class that is properly learnable from clean i.i.d. data but can be defeated by a monotone adversary. The class has DS dimension 2, and its hypotheses are organized by finite levels and neighboring label tuples.

  • A countable multiclass class is properly learnable with clean i.i.d. data but not learnable under monotone adversarial corruptions.
  • The adversary uses n adversarial samples alongside n clean samples to foil every learner.This applies to learners that may be improper and randomized.
  • The constructed class has DS dimension 2.
  • Class construction: The domain is built from finite levels X_r containing t-masked vectors indexed by halfsets of [r].The level and index tags are included as part of each domain tuple.
  • Class construction: Each hypothesis h_{r,k} usually outputs its own label tuple and deviates only on its own level when a visible discrepancy set is a singleton.Any resulting label tuple differs from (r, k) by Hamming distance at most one.
  • Class construction: The finite-level construction makes the domain, label space, and hypothesis class countable.

B.2 H is Properly Learnable with Clean Data

The construction gives a deterministic proper learner that selects a consistent hypothesis from a candidate list built from singleton and pairwise sample slots. Its class has DS dimension exactly 2, while adjacent target hypotheses create the key lower-bound ambiguity.

  • Candidate construction: |Γ| = n + 2 slots: one candidate for each example and two candidates for each pair of examples.The slots are ordered with singleton candidates first, followed by pairs lexicographically.
  • Candidate construction: Singleton slot i contains hri,ki, while pair slots are populated only when the two labels share a level and differ.The pair candidates correspond to the one or two intermediate vectors at distance one from both observed labels.
  • Learning guarantee: The learner returns the first candidate consistent with the sample, or a fixed default when no candidate is available, making it deterministic and proper.Every realizable sample has a consistent candidate in the list.
  • Learning guarantee: The candidate list generalizes by conditioning on anchor observations and applying union bounds to singleton and pairwise candidates.The remaining examples are independent after conditioning, yielding bounds of the form (1 − ε)^(n−1) or (1 − ε)^(n−2).
  • Dimension and clean learning: dDS(H) = 2: a 2 × 2 restriction grid exists, while any pseudo-cube of dimension at least 3 would induce an impossible double-star graph.The clean-data improper sample complexity is O((1 + log(1/δ))/ε).
  • Dimension and clean learning: Adjacent hypotheses incur total error at least 1 on their corresponding distributions because they require opposite labels on shared masked points.The shared points indexed by the differing coordinate carry enough mass to force the error trade-off.

B.4 The Monotone Adversary’s Goal

The adversary constructs a correctly labeled transcript with the same distribution under two adjacent target worlds, preventing any learner from reliably distinguishing them. It does so by adapting additions to the clean sample’s frequency vector.

  • Adversarial objective: The adversary appends correctly labeled examples so the final shuffled transcript has the same distribution under (Dk, hr,k) and (Dw, hr,w).The two targets are adjacent via w = k ⊕ eB.
  • Adversarial construction: The frequency-dependent set B = β(f) is chosen from unseen row indices, ensuring the appended examples remain correctly labeled by the target.Every observed index lies outside B, so the relevant endpoint agreement property applies.
  • Indistinguishability: Because the learner receives identically distributed transcripts in the two worlds, its randomized output can be analyzed as a deterministic predictor after conditioning on its randomness.The adjacent-world error inequality then supplies the lower bound.
  • Adversarial construction: Exactly n examples are appended, and the resulting unordered multiset is Tk⋆,F.The target k⋆ is fixed using a choice depending only on the learner and n, not the realized frequency vector.

B.6 Portal lower bounds

Portal constructions yield sharp monotone-corruption lower bounds while retaining small combinatorial dimensions. The multiclass and partial-binary designs use graph-based ambiguity and correctly labeled adaptive padding.

  • Multiclass portals: A q-regular C4-free incidence graph supplies q-colored stars and color-preserving bijections between adjacent stars.These graph properties organize the portal components used in the lower bounds.
  • Multiclass portals: 3/4 probability of an unseen color when N ≤ q log q/4 creates unresolved portals that force Ω(log n/n) error with one mirror insertion per clean example.The construction uses q ≍ n/log n.
  • Partial-binary portals: The DS-one portal class has dimension exactly one because two portals would force a cycle contradicting C4-freeness.Edge endpoints witness dimension at least one, and the graph obstruction gives the upper bound.
  • Multiclass portals: Ω(d log(1 + n/d)/n) error is obtained for DS dimension d, compared with the clean upper bound O(d/n).The construction takes a direct product of d independent portal components.
  • Budget dependence: With budget b, the lower bound becomes Ω(d log(2 + min{b,n}/d)/n), while the bounded regime falls back to the ordinary clean lower bound.The adversary scales the portal mass with s = min{b,n}.
  • Partial-binary portals: A cyclic ambiguity construction has partial VC dimension at most 18, while halfset flipping establishes the general lower-bound mechanism.The construction avoids the unbounded partial VC dimension of a literal binary analogue.
  • Partial-binary portals: The marker-flower analysis establishes unique ownership of correctable states and supports the common-transcript construction.The internal and external-profile sets of each cell are pairwise disjoint.
  • Partial-binary portals: Every occurrence in the constructed transcript is nonstar and correctly labeled by every target indexed by the relevant state.This shared labeling property is used to complete the adaptive lower bound.

C.4 Completing the Lower Bound

The completed partial-binary lower bound pads clean samples to a common transcript using correctly labeled nonstar insertions. Since every target then induces the same learner-output law, some fixed target has constant expected risk.

  • Risk lower bound: The double-sum argument forces an average error contribution of 1/4 across the hidden tags and target pairs.Each unordered pair of field elements appears with opposite required labels at the same instance.
  • Common transcript: The common transcript T(L, B) is shared by all targets in a B-line, so shuffled learner outputs have an identical distribution across those targets.The equality holds even after including the learner’s private randomness.
  • Risk lower bound: Averaging over random targets and clean samples fixes some target w⋆ with expected risk at least 1/4.The fixed target depends only on the learner and n.
  • Adaptive padding: The transcript contains nonstar examples correctly labeled by every target indexed by the state set, and the adversary uses exactly an insertions.The clean sample from the selected target is a submultiset of the padded transcript.
  • Risk lower bound: If p = Pr[Z > 1/8], then the expected-risk bound implies p ≥ 1/7.This converts the expectation lower bound into a constant-probability failure statement.

D.1 Arbitrarily Severe Proper-Learning Degradation

The construction preserves proper learnability under adaptive additions while making proper learning arbitrarily expensive under oblivious additions. By choosing block sizes to grow rapidly, the proper error rate can decay arbitrarily slowly along suitable sample-size scales.

  • Class structure: The class is countable and closed because each block supports finitely many hypotheses and hypotheses escaping across blocks converge pointwise to the all-$ hypothesis.At every coordinate, the hypothesis range is finite.
  • Clean and improper baselines: The block sizes do not affect clean proper or adaptive improper confidence complexity.The corresponding bounds retain the usual logarithmic dependence on confidence.
  • Adaptive proper learning: Proper learning remains possible under arbitrary adaptive additions, with finite sample complexity for every accuracy and confidence level.For K = ⌈C/(εδ)⌉, the bound depends on the block size L_K but remains finite.
  • Oblivious proper lower bound: Oblivious additions can make proper learning arbitrarily expensive when the learner uses at most c2L_k clean examples at block k.The lower bound holds for every randomized proper learner at confidence level δ = c1/k.
  • Separation: For L_k = 2^k, the construction yields an exponential separation between proper learning under oblivious additions and the adaptive improper bound.More generally, sufficiently rapid growth of L_k makes 1/κ(n) decay arbitrarily slowly, while R^prop_ad(n) = O(1/n) along the stated scales.

D.2 ERM Fragility and Sharpness

The section constructs a low-complexity class whose ERMs are robustly fragile: clean learning can coexist with failure after adversarial additions. It also identifies the sharp scope of this separation and gives a binary one-addition lower bound.

  • ERM sharpness: Linearly many oblivious additions can defeat every ERM even though a carefully designed clean ERM learns the class.The clean-side guarantee is the strongest possible ERM quantifier separation.
  • DS-one construction: A DS-one class admits a clean ERM that remains consistent by using identifying labels, fallback hypotheses, or a Cantor hypothesis.The nontrivial clean case is an all-⋆ sample contained in one active block.
  • DS-one construction: The constructed class has finite coordinatewise range and is closed, while its DS dimension is one.Private labels prevent pseudo-cubes of dimension at least two, and escaping block indices converge to h$.
  • ERM sharpness: The obstruction is properness rather than learnability: an improper learner achieves expected error at most 1/(n + 1) against arbitrarily many oblivious additions.The failure comes from requiring empirical-error minimization within the original class.
  • One adaptive addition: A binary class of VC dimension 2 lets one adaptive addition force every ERM to incur expected error Ω(log n/n) for infinitely many n.The addition leaves two endpoint hypotheses consistent, allowing the adversary to force the wrong one.
Loading 2608.20480v1…