When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory

Joseph Sankoorikal Johny

cs.LGAug 14, 2026

When Does More Correct Data Hurt? Insertion-Stability and the Limits of Dimension-Based Theory

Authors: Joseph Sankoorikal Johny

Organizations: Independent Researcher, Seattle, USA

Abstract

Adding data known to be correct ought to be safe. Not always. Larsen, Pabbaraju and Shetty model the failure with a monotone adversary, which reads an i.i.d. training sample and may append as many further examples as it likes, provided the target hypothesis labels them all. Mehrotra has since settled the cost, showing that for classes of VC dimension d >= 2 no learner can guarantee expected error better than Theta((d/n)log(en/d)), a logarithmic factor above the clean PAC rate. Because that rate is a worst case over all classes, it says nothing about which classes actually suffer the penalty, and the answer turns on the learner. We call a learner insertion-stable if feeding it more correctly labeled examples can only shrink the region where it errs. Such learners are immune to the adversary, since on any given sample the risk after insertions never exceeds the risk on the clean part alone, however much is added and however cleverly it is chosen. High- probability guarantees carry over unchanged, and because Closure is insertion-stable every intersection-closed class keeps its clean rate of E[Err] <= (21d+34)/n. Immunity is not something the classical dimensions can predict. Two classes can agree on VCdim = Ldim = 2 and still split, one at Theta(1/n) and the other at Theta(log(en)/n), while intervals have unbounded Littlestone dimension and are immune anyway. On Mehrotra's hard class we prove more than the failure of a single algorithm, showing that no monotone permutation-invariant compression scheme of any finite size attains the clean rate. The question is therefore not whether a class is hard, nor whether a learner is good, but whether the two suit each other. Given an insertion-stable learner that is optimal on clean data, correct additions are free, and without one the cost belongs to the class, so changing the learner will not avoid it.

Figures & tables

Class	$\VC$	$\Ldim$	$\isdim$	rate vs. adversary	stable optimal?
$\mathcal{H}_{\leq 2}$	$2$	$2$	$\leq 2$	$\Theta(1/n)$ , $\leq 76/n$	yes b
$\mathcal{H}_{\mathrm{prime}}$ [ 9 ]	$2$	$2$	$\infty^{a}$	$\Theta(\log(en)/n)$	no a
$\mathcal{H}_{\leq d}$	$d$	$d$	$\leq d$	$\Theta(d/n)$	yes b
axis-aligned rectangles, $\mathbb{R}^{p}$	$2p$	$\infty$	$\leq 2p$	$\Theta(p/n)$	yes b
monotone conjunctions, $\{0,1\}^{p}$	$p$	$p$	$\leq p$	$\Theta(p/n)$	yes b
linear subspaces, $\dim k$	$k$	$k$	$\leq k$	$\Theta(k/n)$	yes b

Table 1: The rate landscape. The first two rows are the payload: identical VC and Littlestone dimension, rates differing by

\Theta(\log n)

. Rows four and seven run the separation the other way: unbounded Littlestone dimension, clean rate retained. The last column asks whether the class admits an insertion-stable learner attaining its clean rate , not merely an insertion-stable learner, since the constant learner

A(L)\equiv h_{0}

is insertion-stable on every class and useful on none. Provenance of each

\isdim

and last-column entry: a from a rate lower bound via the contrapositive of Corollary 12 (in the last row, for the witness class attaining the supremum); b from an explicit scheme, namely Closure (Proposition 19 ); c open . Failing to be intersection-closed defeats Closure here, but does not preclude some other superset-monotone permutation-invariant scheme, and we prove no rate lower bound for halfspaces. That entry illustrates the limitation noted in Section 7 .

Figure 1: Left: $\mathcal{H}_{\leq 2}$ and $\mathcal{H}_{\mathrm{prime}}$ have identical VC and Littlestone dimension but different asymptotic shape, with constants normalized (the true bounds are $\leq 76$ , an upper bound, and $\geq\log(en)/30$ , a lower bound; these are not pointwise comparable and their literal crossover lies beyond any plottable range). Right: the ratio of rates, which is the content of Corollary 16 , diverging as $\Theta(\log n)$ .

Statistical Learning Theory

Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.

See all 579 papers

Aug 6, 2026

Optimal Rates for Learning with Monotone Adversaries

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

Θ(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

Θ(1/n)

d=1

and

Θ((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.

Anay Mehrotra

Stanford University

Minimax Estimation Statistical Learning Theory

Ask PDF

Aug 20, 2026

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

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

Julian Asilis, Shaddin Dughmi, Chirag Pabbaraju

USC · Stanford University

Statistical Learning Theory Multiclass Classification

Ask PDF

Feb 23, 2026

Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds

We study online learning in the adversarial injection model introduced by [Goel et al. 2017], where a stream of labeled examples is predominantly drawn i.i.d.\ from an unknown distribution

\mathcal{D}

, but may be interspersed with adversarially chosen instances without the learner knowing which rounds are adversarial. Crucially, labels are always consistent with a fixed target concept (the clean-label setting). The learner is additionally allowed to abstain from predicting, and the total error counts the mistakes whenever the learner decides to predict and incorrect abstentions when it abstains on i.i.d.\ rounds. Perhaps surprisingly, prior work shows that oracle access to the underlying distribution yields

O(d^2 \log T)

combined error for VC dimension

d

, while distribution-agnostic algorithms achieve only

\tilde{O}(\sqrt{T})

for restricted classes, leaving open whether this gap is fundamental. We resolve this question by proving a matching

Ω(\sqrt{T})

lower bound for VC dimension

1

, establishing a sharp separation between the two information regimes. On the algorithmic side, we introduce a potential-based framework driven by robust witnesses, small subsets of labeled examples that certify predictions while remaining resilient to adversarial contamination. We instantiate this framework using two combinatorial dimensions: (1) inference dimension, yielding combined error

\tilde{O}(T^{1-1/k})

for classes of inference dimension

k

, and (2) certificate dimension, a new relaxation we introduce. As an application, we show that halfspaces in

\mathbb{R}^2

have certificate dimension

3

, obtaining the first distribution-agnostic bound of

\tilde{O}(T^{2/3})

for this class. This is notable since [Blum et al. 2021] showed halfspaces are not robustly learnable under clean-label attacks without abstention.

Ezra Edelman, Surbhi Goel

University of Pennsylvania

Statistical Learning Theory Adversarial Robustness

Ask PDF

Abstract

Statistical Learning Theory

Explore similar work

Optimal Rates for Learning with Monotone Adversaries

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

Reliable Abstention under Adversarial Injections: Tight Lower Bounds and New Upper Bounds