PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Joseph Sankoorikal Johny

arXiv:2608.14020v1cs.LGstat.ML

TL;DR

Correctly labeled data can worsen learning because adaptive insertions destroy the symmetry underlying standard guarantees. The paper analyzes insertion-stable learners and shows that immunity depends on the learner–class pairing, not classical dimensions alone.

  • Problem

    Existing guarantees do not identify when correct insertions are harmless or costly across different learner–class pairings.

  • Method

    The paper defines insertion stability and proves that learners whose error regions shrink under correct insertions retain their clean-sample risk.

  • Results

    VC and Littlestone dimensions do not determine monotone-insertion rates, and no finite monotone permutation-invariant compression scheme attains the clean rate on Hprime.

  • Takeaways & Limitations

    Correct additions are free for insertion-stable learners with clean guarantees, while otherwise the penalty belongs to the class–learner pairing.

  • Takeaways & Limitations

    The proposed isdim measure certifies good rates but does not show that large values force large rates.

Abstract

from arXiv · show

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.

1 Introduction

Correctly labeled additions can worsen learning by destroying independence, but the penalty depends on the pairing of class and learner rather than on classical dimensions alone. Insertion-stable learners eliminate this cost, while Mehrotra’s hard class defeats broad families of compression schemes.

  • Worst-case penalty: Mehrotra’s optimum rate is Θ((min{d, n}/n) log(en/ min{d, n})) for VC dimension d ≥2, a logarithmic factor above Θ(d/n).The same rates hold with Littlestone dimension replacing d, against all randomized possibly improper learners.
  • Insertion stability: An insertion-stable learner’s error region only shrinks under correctly labeled insertions, so adversarial risk is almost surely bounded by clean risk.This remains true with adaptive, randomized, repeated, out-of-support, and arbitrarily many insertions, including high-probability guarantees.
  • Positive result: Closure is insertion-stable, giving every intersection-closed class expected error at most (21d + 34)/n under arbitrarily many adaptive monotone insertions.Mehrotra’s bounded-budget converse is invisible to Closure because it pads with repeated negative points.
  • Dimension independence: Classical dimensions do not determine insertion-robust rates: H≤2 and Hprime share VC and Littlestone dimensions yet differ by Θ(log n), while intervals remain clean-rate learnable.Thus the geometry of the learner’s error region, not class size or VCdim and Ldim alone, determines the outcome.
  • Negative result: No consistent monotone permutation-invariant compression scheme of any finite size attains the clean rate for Hprime.The result rules out a family of potential remedies rather than only one algorithm.

2 Model and preliminaries

The model studies learning from a clean sample augmented by adaptive, correctly labeled insertions that may be repeated, out of distribution support, and uniformly shuffled before reaching the learner. Its difficulty comes from the adversary seeing the entire clean sample before choosing the insertions.

  • Monotone-adversary model: The learner receives n clean examples plus m adversarial insertions, all labeled by the target h⋆, and is evaluated on fresh data from D.The adversary maps the clean sample X ∈ X^n to an insertion sequence in X^m, while the learner is scored by Err_D(ĥ, h⋆).
  • Adversarial insertions: The adversary may repeat points or choose points outside supp(D), provided every appended point receives its correct target label.Duplicates count as separate occurrences in the multiset representation.
  • Observed data: A uniformly random permutation hides which examples are clean, so the learner operates on the resulting labeled multiset rather than the original sequence.The shuffle acts on the n + m occurrences, including duplicate occurrences.
  • Source of difficulty: Adaptivity is the model’s central source of difficulty because the adversary observes the entire clean sample before selecting its insertions.In contrast, the stated oblivious case already attains the clean rate Θ(d/n).
  • Preliminaries: For a labeled multiset L, the version space contains hypotheses in H consistent with every labeled occurrence; intersection-closed classes include conjunctions, axis-aligned rectangles, and H≤d.The Closure algorithm is defined for such classes when the version space is nonempty.

3 Insertion-stability

Insertion-stability makes correctly labeled additions harmless by requiring permutation invariance and error-region shrinkage under correctly labeled multiset supersets. This yields pointwise transfer of clean expected, high-probability, moment, and tail guarantees to adaptive monotone adversaries, uniformly over finite and unbounded budgets.

  • Definition: An insertion-stable learner is permutation-invariant and superset-monotone on correctly labeled finite multisets.For randomized learners, superset-monotonicity must hold for every realization of independently drawn learner coins.
  • Insertion-stability lemma: Theorem 3 shows that a monotone adversary’s correctly labeled output cannot enlarge the learner’s error region relative to the clean sample.The adversarial input is a correctly labeled multiset superset of the clean sample, so superset-monotonicity gives pointwise error-region inclusion and risk domination.
  • Unbounded budgets: The risk bound is uniform in the insertion budget, including the supremum over finite budgets defining unbounded-budget risk.The bound is independent of m, so it survives arbitrarily many finite insertions without assuming a literal infinite sample.
  • Transfer: Clean expected and high-probability guarantees transfer unchanged against every finite-budget or unbounded adaptive randomized monotone adversary.The almost-sure coupling also transfers all moments and tail probabilities, not merely expectation bounds.
  • Reduction: The reduction needs neither exchangeability nor independence of adversarial examples: it applies clean-sample guarantees to the i.i.d. subset S.Its novelty is recognizing the adversary’s output as a correctly labeled superset; equivalence with prefix monotonicity requires permutation invariance.

4 Closure is insertion-stable

Closure is insertion-stable: correctly labeled additions cannot increase its error, regardless of repetition, support, or adversarial adaptivity. On intersection-closed classes, this preserves the clean, logarithm-free rate, and the same reduction extends to suitable compression schemes.

  • 4 Closure is insertion-stable: Closure is insertion-stable for every hypothesis class, so correctly labeled insertions cannot worsen its error region.The proof does not require intersection-closedness.
  • 4 Closure is insertion-stable: Constraint order and multiplicity do not matter: Closure depends on the labeled multiset, while added correct constraints can only reduce the version space.For S ⊆ T correctly labeled by h⋆, VH(T) ⊆ VH(S), causing the intersection P(T) to contain P(S).
  • 4 Closure is insertion-stable: Repeated points, out-of-support examples, and negative insertions are harmless; negatives are weakly helpful because they can only enlarge Closure’s positive region.The argument is distribution-independent and treats repetition as unchanged constraints.
  • 4 Closure is insertion-stable: On intersection-closed classes, Closure transfers its clean guarantee against every randomized adaptive monotone adversary and every finite insertion budget, including unlimited budget.The resulting bounds are free of logarithmic factors.
  • 4 Closure is insertion-stable: The same conclusion applies to consistent, permutation-invariant, superset-monotone compression schemes with permutation-invariant reconstruction.Superset-monotonicity and permutation-invariance provide insertion stability, reducing adversarial risk to clean-sample risk.

5 No dimension-based theory can work

The same VC and Littlestone dimensions can support different monotone-insertion rates: H≤2 is immune at Θ(1/n), while Hprime incurs Θ(log(en)/n). Thus no dimension-only theory predicts immunity, and Hprime admits neither clean-rate-optimal insertion-stable learners nor finite monotone compression schemes of the stated kind.

  • Dimension comparison: VCdim(H≤d) = Ldim(H≤d) = d, and H≤d is intersection-closed.The class consists of concepts labeling at most d points positively.
  • H≤2 versus Hprime: 76/n is Closure’s expected-error bound on H≤2 against every randomized adaptive monotone adversary at every finite budget, yielding Θ(1/n).Each insertion either reveals a new positive and shrinks the error region or changes nothing.
  • H≤2 versus Hprime: log(en)/(30n) is a lower bound for every randomized learner on Hprime, while ERM gives O(log(en)/n), so its rate is Θ(log(en)/n).The adversary can pad two candidate targets to an identical multiset, preserving uncertainty on a test point.
  • Dimension independence: H≤2 and Hprime both have VCdim = Ldim = 2, yet their rates are Θ(1/n) and Θ(log(en)/n), so no function of those dimensions determines the rate.Intervals provide the reverse separation: they are immune despite having unbounded Littlestone dimension.
  • Learner-class barrier: Every insertion-stable learner for Hprime has clean-sample rate Ω(log(en)/n), so no learner is simultaneously insertion-stable and clean-rate-optimal there.Insertion-stability alone does not imply accuracy: the constant learner is insertion-stable because its error region never changes.
  • Compression-scheme barrier: No finite-size learner for Hprime is simultaneously consistent, permutation-invariant, superset-monotone, and a permutation-invariant-reconstruction sample compression scheme.The contradiction compares the log-free bound (21k + 34)/n with the lower bound log(en)/(30n) on one fixed class at every n.

6 A candidate dimension, and why it is hard to compute

The paper introduces isdim, a compression-based candidate dimension that yields clean-rate bounds, and shows it is Θ(VCdim) on intersection-closed classes. However, isdim is difficult to evaluate intrinsically: finite values require explicit constructions, infinite values require prior lower bounds, and some classes remain unclassified.

  • Definition and rate: isdim(H) is the least finite compression-scheme size satisfying the stated conditions, with isdim(H)=∞ when no such scheme exists.At finite budget, it gives E[Err] ≤ (21 isdim(H) + 34)/n.
  • Intersection-closed classes: For intersection-closed classes, isdim(H)=Θ(v), where v=VCdim(H).The lower bound counts distinct messages on all labelings of a shattered v-point set; the upper bound uses Closure retaining at most v positive points.
  • Why computation is hard: The upper bound is largely definitional: its hypotheses reproduce the cited compression theorem rather than providing an intrinsic method for discovering the dimension.Thus, “isdim(H)=k implies rate O(k/n)” restates that theorem.
  • Why computation is hard: Finite isdim values currently come from exhibiting Closure, while infinite values come from pre-existing rate lower bounds; classes such as halfspaces therefore remain unclassified.The paper marks such cases with “?”.
  • A strict separation: For all 2^3 functions on a three-point domain, isdim=2<3=VCdim, showing the lower constant in the intersection-closed bound cannot be raised to 1.The size-2 rule is verified to satisfy consistency, permutation invariance, superset monotonicity, and compression conditions.

7 Discussion and open problems

The section identifies limits of isdim as a one-directional certificate and lays out open problems on intrinsic lower-bound characterizations, constants, unexplored classes, and sample complexity. It also situates the results relative to replay-adversary work with a different online corruption model.

  • Limits of isdim: isdim(H) = k certifies O(k/n), but large isdim is not shown to force a large rate; infinite entries derive from known lower bounds.Thus, isdim currently certifies good rates and merely records bad ones.
  • Intrinsic lower-bound characterizations: Open Problem 21 asks whether a rate-independent q(H) can make large q(H) imply every learner suffers ω(1/n) under monotone insertions.The ideal choice is q = isdim, yielding a characterization.
  • Intrinsic lower-bound characterizations: A shattering-style quantity may be needed because directly proving isdim(H) = ∞ requires excluding every superset-monotone compression scheme of every size.Existing lower-bound dimensions instead use explicit shattering or witness structures.
  • Open problems: For intersection-closed classes, Proposition 19 gives 0.2271 VCdim ≤isdim ≤VCdim, while the optimal constants and attainment of either bound remain unknown.Remark 20 gives an example with isdim / VCdim = 2/3.
  • Related work: Related work studies online learning under a replay adversary with potentially wrong corrupted feedback, whereas this paper studies an offline model.That work introduces the extended threshold dimension with matching bounds and uses a closure-based learner.
Loading 2608.14020v1…