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

# When Does More Correct Data Hurt?Insertion-Stability and the Limits of Dimension-Based Theory
Source: [https://arxiv.org/html/2608.14020](https://arxiv.org/html/2608.14020)
August 14, 2026

###### 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 dimensiond≥2d\\geq 2no learner can guarantee expected error better thanΘ⁡\(\(d/n\)​log⁡\(e​n/d\)\)\\Theta\\big\(\(d/n\)\\log\(en/d\)\\big\), 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𝔼⁡\[Err\]≤\(21​d\+34\)/n\\mathbb\{E\}\[\\Err\]\\leq\(21d\+34\)/n\.

Immunity is not something the classical dimensions can predict\. Two classes can agree onVCdim=Ldim=2\\VC=\\Ldim=2and still split, one atΘ⁡\(1/n\)\\Theta\(1/n\)and the other atΘ⁡\(log⁡\(e​n\)/n\)\\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\.

## 1Introduction

Suppose you augment a training set: for every image you already hold, you add a rotated copy carrying the same label\. Or you notice a rare class is thin, so you duplicate its examples\. Nothing you added is wrong, and you chose what to add only after looking at what you had\. Practitioners perform such passes routinely and expect at worst no harm from them, since the standard generalization bounds require independence or exchangeability and augmentation appears to threaten neither the labels nor the sample’s coverage\. It does, however, destroy exactly that symmetry, and the guarantees rest on it\.

The model of Larsen, Pabbaraju, and Shetty\[[8](https://arxiv.org/html/2608.14020#bib.bib8)\]isolates this effect from every other way a dataset can go wrong\. Their adversary reads the clean sample, then appends whatever examples it pleases under a single restriction: each appended point must receive the label the target hypothesis gives it\. Nothing is mislabeled, so the added constraints are all valid, and an oracle identifying the original points would let the learner ignore the rest at no cost\. What the additions destroy is independence: they are chosen with knowledge of the clean draw, and the learner receives one shuffled pool in which the two groups are indistinguishable, so it can neither isolate the clean subsample nor treat what it holds as exchangeable\.

Mehrotra\[[9](https://arxiv.org/html/2608.14020#bib.bib9)\]determined the optimal rate in this model\. Over classes of VC dimensiond≥2d\\geq 2it isΘ⁡\(\(min⁡\{d,n\}/n\)​log⁡\(e​n/min⁡\{d,n\}\)\)\\Theta\\big\(\(\\min\\\{d,n\\\}/n\)\\log\(en/\\min\\\{d,n\\\}\)\\big\), exceeding the clean rateΘ⁡\(d/n\)\\Theta\(d/n\)by a logarithmic factor, against all randomized possibly improper learners; the same rates hold with Littlestone dimension in place ofdd, so finite mistake bounds do not help either\. Counterintuitively, correctly labeled insertions raise the statistical difficulty of the problem\.

#### This paper\.

Mehrotra’s bound is a supremum over classes, witnessed by a specific construction, and his first stated open problem asks:

> *“Which structural properties of a fixed binary class determine its rate under monotone insertions?”*

Our answer is two\-sided, and the two sides are what the worst\-case rate obscures\. What decides the outcome is neither the class’s size nor its classical dimensions, but the*geometry of the error region of the learner one runs on it*\. Where a learner exists whose error region can only shrink as correct examples arrive, the insertions cost nothing at all: not merely a survivable amount, but nothing, at any budget\. Where no such learner exists, the penalty is a property of the class, and Mehrotra’s lower bound says every learner pays it\. The phenomenon therefore attaches to the pairing of learner and class\.

#### Contributions\.

1. 1\.The insertion\-stability lemma\(Section[3](https://arxiv.org/html/2608.14020#S3)\)\. If a learner’s error region only shrinks under correctly labeled insertions, its adversarial risk is dominated*almost surely*by its clean risk\. Adaptivity, arbitrarily many insertions, repeated and out\-of\-support points, randomized adversaries, and high\-probability guarantees are all free consequences\. The proof is a reduction; the i\.i\.d\. assumption is quarantined inside a citation about the clean sample and never applied to the corrupted one\.
2. 2\.Closure is insertion\-stable\(Section[4](https://arxiv.org/html/2608.14020#S4)\), so every intersection\-closed class retains the clean rate under arbitrarily many adaptive monotone insertions, with explicit constants\(21​d\+34\)/n\(21d\+34\)/nin expectation\. We also observe that Mehrotra’s own bounded\-budget converse pads with*negative*repeated points, and is therefore not merely survivable but*invisible*to Closure\.
3. 3\.Dimension independence\(Section[5](https://arxiv.org/html/2608.14020#S5)\)\.ℋ≤2\\mathcal\{H\}\_\{\\leq 2\}andℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}have identical VC and Littlestone dimension and rates differing byΘ⁡\(log⁡n\)\\Theta\(\\log n\); intervals have unbounded Littlestone dimension and retain the clean rate\. No function ofVCdim\\VCandLdim\\Ldimdetermines the monotone\-insertion rate\.
4. 4\.The negative half, sharpened to a family of algorithms\(Section[5](https://arxiv.org/html/2608.14020#S5)\)\. Forℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}we show that*no*consistent monotone permutation\-invariant compression scheme, of any finite size, attains the clean rate\. This rules out a whole class of would\-be remedies rather than one algorithm, and is our main technical result\.

#### What we do not claim\.

We give a sufficient condition, not a characterization\. A converse, in which structure that is*not*insertion\-stable forces the logarithmic penalty, remains open, and Section[7](https://arxiv.org/html/2608.14020#S7)says precisely what is missing\. The candidate measure of Section[6](https://arxiv.org/html/2608.14020#S6)is a bookkeeping device, not a theory: it repackages the hypotheses of a known theorem, and we are explicit that it cannot currently be evaluated on a class without already knowing that class’s rate\. Our machinery is borrowed from Hanneke\[[7](https://arxiv.org/html/2608.14020#bib.bib7)\]; the contribution is the reduction that makes it apply here, plus the negative result above\. All combinatorial claims about specific classes were additionally verified by exhaustive computation\.

## 2Model and preliminaries

Notation and the model statement follow\[[9](https://arxiv.org/html/2608.14020#bib.bib9)\]\. For a distribution𝒟\\mathcal\{D\}on𝒳\\mathcal\{X\}andg,h:𝒳→\{0,1\}g,h:\\mathcal\{X\}\\to\\\{0,1\\\}writeErr𝒟\(g,h\)=ℙX∼𝒟\{g\(X\)≠h\(X\)\}\\Err\_\{\\mathcal\{D\}\}\(g,h\)=\\mathbb\{P\}\_\{X\\sim\\mathcal\{D\}\}\\\{g\(X\)\\neq h\(X\)\\\}\. Multiset union is written⊎\\uplus, and every duplicate of a point counts as its own occurrence throughout\. Logarithms are baseee\.

###### Problem 1\(Learning with a monotone adversary\[[8](https://arxiv.org/html/2608.14020#bib.bib8),[9](https://arxiv.org/html/2608.14020#bib.bib9)\]\)\.

Fix a nonempty classℋ⊆\{0,1\}𝒳\\mathcal\{H\}\\subseteq\\\{0,1\\\}^\{\\mathcal\{X\}\}, integersn≥1n\\geq 1,m≥0m\\geq 0, a targeth⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}, and a distribution𝒟\\mathcal\{D\}on𝒳\\mathcal\{X\}\. A deterministic monotone adversary with exact budgetmmis a mapA:𝒳n→𝒳mA:\\mathcal\{X\}^\{n\}\\to\\mathcal\{X\}^\{m\}\. A dataset is generated as follows\.

1. 1\.Nature draws an ordered clean sampleX=\(X1,…,Xn\)∼𝒟nX=\(X\_\{1\},\\dots,X\_\{n\}\)\\sim\\mathcal\{D\}^\{n\}\.
2. 2\.The adversary seesXXand returnsA⁡\(X\)=\(X~1,…,X~m\)A\(X\)=\(\\widetilde\{X\}\_\{1\},\\dots,\\widetilde\{X\}\_\{m\}\)\. It may repeat points and choose points outsidesupp⁡\(𝒟\)\\supp\(\\mathcal\{D\}\), but must label every appended point byh⋆h^\{\\star\}\.
3. 3\.Nature draws an independent uniform permutationΠ\\Piof then\+mn\+moccurrences and gives the learnerTh⋆,A​\(X,Π\)=Π⁡\(\(Xi,h⋆​\(Xi\)\)i=1n⊎\(X~j,h⋆​\(X~j\)\)j=1m\)T\_\{h^\{\\star\},A\}\(X,\\Pi\)=\\Pi\\big\(\(X\_\{i\},h^\{\\star\}\(X\_\{i\}\)\)\_\{i=1\}^\{n\}\\uplus\(\\widetilde\{X\}\_\{j\},h^\{\\star\}\(\\widetilde\{X\}\_\{j\}\)\)\_\{j=1\}^\{m\}\\big\)\.

The learner knowsℋ\\mathcal\{H\},nn, andmm, but not which examples came from𝒟\\mathcal\{D\}\. It is scored byErr𝒟⁡\(h^,h⋆\)\\Err\_\{\\mathcal\{D\}\}\(\\hat\{h\},h^\{\\star\}\)on a fresh independent point from𝒟\\mathcal\{D\}\.

Four features of the model are load\-bearing below, and all are explicit in\[[9](https://arxiv.org/html/2608.14020#bib.bib9)\]: every label is correct; the adversary may repeat points and use points outsidesupp⁡\(𝒟\)\\supp\(\\mathcal\{D\}\); the learner sees a uniform shuffle, so it is a function of the*multiset*rather than the sequence; and the adversary is*adaptive*, seeing all ofXXbefore choosing insertions\. The last is the entire source of difficulty; in the oblivious case the clean rateΘ⁡\(d/n\)\\Theta\(d/n\)is already attainable\[[8](https://arxiv.org/html/2608.14020#bib.bib8)\]\. Adversary randomization does not change the picture: as Mehrotra notes, upper bounds hold after conditioning on the adversary’s randomness\.

A*labeled multiset*is a finite multiset of pairs\(x,y\)∈𝒳×\{0,1\}\(x,y\)\\in\\mathcal\{X\}\\times\\\{0,1\\\}; it is*correctly labeled by*h⋆h^\{\\star\}ify=h⋆​\(x\)y=h^\{\\star\}\(x\)for every occurrence\. We writeS⊆TS\\subseteq Tfor multiset containment, soTTmay contain additional copies of points already inSS\. The*version space*ofℋ\\mathcal\{H\}on a labeled multisetLLisVℋ\(L\)=\{h∈ℋ:h\(x\)=yfor all\(x,y\)∈L\}V\_\{\\mathcal\{H\}\}\(L\)=\\\{h\\in\\mathcal\{H\}:h\(x\)=y\\text\{ for all \}\(x,y\)\\in L\\\}\.

Recall thatℋ\\mathcal\{H\}is*intersection\-closed*if\{\{x:h⁡\(x\)=1\}:h∈ℋ\}\\\{\\\{x:h\(x\)=1\\\}:h\\in\\mathcal\{H\}\\\}is closed under pairwise intersection of its members; conjunctions on\{0,1\}p\\\{0,1\\\}^\{p\}, axis\-aligned rectangles onℝp\\mathbb\{R\}^\{p\}, andℋ≤d=\{h:\|\{x:h⁡\(x\)=1\}\|≤d\}\\mathcal\{H\}\_\{\\leq d\}=\\\{h:\|\\\{x:h\(x\)=1\\\}\|\\leq d\\\}are all intersection\-closed\[[7](https://arxiv.org/html/2608.14020#bib.bib7)\]\. \(We use the standard convention of closure under pairwise intersection of members; some authors additionally require𝒳\\mathcal\{X\}itself to belong to the family, whichℋ≤d\\mathcal\{H\}\_\{\\leq d\}would fail for\|𝒳\|\>d\|\\mathcal\{X\}\|\>d\.\) For such a class, the*Closure*algorithm on a labeled multisetLLwithVℋ​\(L\)≠∅V\_\{\\mathcal\{H\}\}\(L\)\\neq\\emptysetreturns the classifierh^L\\hat\{h\}\_\{L\}with

\{x:h^L​\(x\)=1\}=⋂h∈Vℋ​\(L\)\{x:h⁡\(x\)=1\}\.\\\{x:\\hat\{h\}\_\{L\}\(x\)=1\\\}\\;=\\;\\textstyle\\bigcap\_\{h\\in V\_\{\\mathcal\{H\}\}\(L\)\}\\\{x:h\(x\)=1\\\}\.\(1\)

## 3Insertion\-stability

For a learnerAAand a labeled multisetTTcorrectly labeled byh⋆h^\{\\star\}, define the*error region*ErrRegh⋆⁡\(A⁡\(T\)\)=\{x∈𝒳:A⁡\(T\)​\(x\)≠h⋆​\(x\)\}\\ErrReg\_\{h^\{\\star\}\}\(A\(T\)\)=\\\{x\\in\\mathcal\{X\}:A\(T\)\(x\)\\neq h^\{\\star\}\(x\)\\\}\.

###### Definition 2\(Insertion\-stable\)\.

A learnerAAis*insertion\-stable*if it is

1. \(i\)*permutation\-invariant*:A⁡\(T\)A\(T\)depends only on the labeled multisetTT; and
2. \(ii\)*superset\-monotone*: for everyh⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}and all finite labeled multisetsS⊆TS\\subseteq Tboth correctly labeled byh⋆h^\{\\star\}, ErrRegh⋆⁡\(A⁡\(T\)\)⊆ErrRegh⋆⁡\(A⁡\(S\)\)\.\\ErrReg\_\{h^\{\\star\}\}\(A\(T\)\)\\;\\subseteq\\;\\ErrReg\_\{h^\{\\star\}\}\(A\(S\)\)\.

For randomizedAAwe require \(ii\) for each realization of coins drawn independently of the sample\.

Three details matter and are deliberately permitted\. Containment is*multiset*containment, soTTmay repeat points ofSS, which is necessary because Mehrotra’s constructions pad with many copies of a point\. No constraint tiesTT’s points tosupp⁡\(𝒟\)\\supp\(\\mathcal\{D\}\); indeed𝒟\\mathcal\{D\}does not appear in Definition[2](https://arxiv.org/html/2608.14020#Thmtheorem2)at all, which is what makes the reduction below work for all𝒟\\mathcal\{D\}at once\. And permutation\-invariance is folded into the definition rather than carried alongside, because the model’s shuffle supplies it\.

###### Theorem 3\(Insertion\-stability lemma\)\.

LetAAbe insertion\-stable\. Then for every𝒟\\mathcal\{D\}, everyh⋆∈ℋh^\{\\star\}\\in\\mathcal\{H\}, every finite budgetm∈ℕm\\in\\mathbb\{N\}, and every possibly randomized adaptive monotone adversary, on a single probability space carrying the clean draw, the adversary’s coins, the shuffle, and the learner’s coins,

Err𝒟⁡\(A⁡\(T\),h⋆\)≤Err𝒟⁡\(A⁡\(S\),h⋆\)almost surely,\\Err\_\{\\mathcal\{D\}\}\\big\(A\(T\),h^\{\\star\}\\big\)\\;\\leq\\;\\Err\_\{\\mathcal\{D\}\}\\big\(A\(S\),h^\{\\star\}\\big\)\\qquad\\text\{almost surely,\}whereSSis the clean sample labeled byh⋆h^\{\\star\}andTTis the learner’s input\.

###### Proof\.

Condition on a realization of the clean sampleXX, the adversary’s coins, the shuffleΠ\\Pi, and the learner’s coins\.

*Step 1:TTis a correctly labeled superset ofSS\.*By Problem[1](https://arxiv.org/html/2608.14020#Thmtheorem1),TTconsists of thennclean occurrences together with themminserted ones, permuted\. Every inserted occurrence is labeled byh⋆h^\{\\star\}, as is every clean occurrence, soTTis correctly labeled byh⋆h^\{\\star\}; discarding the inserted occurrences exhibitsS⊆TS\\subseteq Tas multisets\.

*Step 2: the error region shrinks\.*By \(i\),A⁡\(T\)A\(T\)does not depend onΠ\\Piand is a function of the labeled multiset alone\. Applying \(ii\) toS⊆TS\\subseteq TgivesErrRegh⋆⁡\(A⁡\(T\)\)⊆ErrRegh⋆⁡\(A⁡\(S\)\)\\ErrReg\_\{h^\{\\star\}\}\(A\(T\)\)\\subseteq\\ErrReg\_\{h^\{\\star\}\}\(A\(S\)\)\.

*Step 3: monotonicity of the measure\.*Since𝒟\\mathcal\{D\}is a measure, and sinceErr𝒟⁡\(A⁡\(L\),h⋆\)\\Err\_\{\\mathcal\{D\}\}\(A\(L\),h^\{\\star\}\)equals𝒟⁡\(ErrRegh⋆⁡\(A⁡\(L\)\)\)\\mathcal\{D\}\\big\(\\ErrReg\_\{h^\{\\star\}\}\(A\(L\)\)\\big\)for anyLL, Step 2 yields

Err𝒟⁡\(A⁡\(T\),h⋆\)≤Err𝒟⁡\(A⁡\(S\),h⋆\)\\Err\_\{\\mathcal\{D\}\}\(A\(T\),h^\{\\star\}\)\\;\\leq\\;\\Err\_\{\\mathcal\{D\}\}\(A\(S\),h^\{\\star\}\)for this realization\.

Since the realization was arbitrary, the inequality holds almost surely\. ∎

###### Corollary 5\(Transfer\)\.

LetAAbe insertion\-stable\. Because Theorem[3](https://arxiv.org/html/2608.14020#Thmtheorem3)is an almost\-sure domination under an explicit coupling, since the two learners are run on the*same*clean sample, every monotone functional of the risk transfers from the clean setting to the adversarial one\. In particular, for every finite budgetmmand every randomized adaptive monotone adversary, hence also forR𝒟∞R^\{\\infty\}\_\{\\mathcal\{D\}\}of Remark[4](https://arxiv.org/html/2608.14020#Thmtheorem4): if𝔼⁡\[Err𝒟⁡\(A⁡\(S\),h⋆\)\]≤B⁡\(n\)\\mathbb\{E\}\[\\Err\_\{\\mathcal\{D\}\}\(A\(S\),h^\{\\star\}\)\]\\leq B\(n\)then𝔼⁡\[Err𝒟⁡\(A⁡\(T\),h⋆\)\]≤B⁡\(n\)\\mathbb\{E\}\[\\Err\_\{\\mathcal\{D\}\}\(A\(T\),h^\{\\star\}\)\]\\leq B\(n\); and ifErr𝒟⁡\(A⁡\(S\),h⋆\)≤B⁡\(n,δ\)\\Err\_\{\\mathcal\{D\}\}\(A\(S\),h^\{\\star\}\)\\leq B\(n,\\delta\)with probability at least1−δ1\-\\delta, then the same bound holds with probability at least1−δ1\-\\deltaagainst the adversary\. All moments and tail probabilities transfer likewise\.

The distinction is worth emphasizing: domination*in expectation*alone would not give the high\-probability transfer\. It is the almost\-sure coupling that does\.

## 4Closure is insertion\-stable

###### Proposition 8\.

For*any*classℋ\\mathcal\{H\}, the Closure algorithm \([1](https://arxiv.org/html/2608.14020#S2.E1)\) is insertion\-stable\.

###### Proof\.

WriteP⁡\(L\)=⋂h∈Vℋ​\(L\)\{x:h⁡\(x\)=1\}P\(L\)=\\bigcap\_\{h\\in V\_\{\\mathcal\{H\}\}\(L\)\}\\\{x:h\(x\)=1\\\}\.

\(i\)Vℋ​\(L\)V\_\{\\mathcal\{H\}\}\(L\)depends onLLonly through its set of constraints, and is unaffected by their order or multiplicity, since a hypothesis consistent with one occurrence of\(x,y\)\(x,y\)is consistent with all\. Henceh^L\\hat\{h\}\_\{L\}is a function of the labeled multiset\.

\(ii\) LetS⊆TS\\subseteq Tbe correctly labeled byh⋆h^\{\\star\}\. Every constraint ofSSis one ofTT, soVℋ​\(T\)⊆Vℋ​\(S\)V\_\{\\mathcal\{H\}\}\(T\)\\subseteq V\_\{\\mathcal\{H\}\}\(S\); andh⋆h^\{\\star\}lies in both, so both are nonempty and Closure is defined on each\. Intersecting over a smaller family yields a larger set, so

P⁡\(S\)⊆P⁡\(T\)\.P\(S\)\\;\\subseteq\\;P\(T\)\.\(2\)Sinceh⋆∈Vℋ​\(L\)h^\{\\star\}\\in V\_\{\\mathcal\{H\}\}\(L\), the intersection definingP⁡\(L\)P\(L\)includes\{h⋆=1\}\\\{h^\{\\star\}=1\\\}, soP⁡\(L\)⊆\{x:h⋆​\(x\)=1\}P\(L\)\\subseteq\\\{x:h^\{\\star\}\(x\)=1\\\}: Closure never produces a false positive\. Its error region is therefore exactly the missed positives,ErrRegh⋆\(h^L\)=\{h⋆=1\}∖P\(L\)\\ErrReg\_\{h^\{\\star\}\}\(\\hat\{h\}\_\{L\}\)=\\\{h^\{\\star\}=1\\\}\\setminus P\(L\), and by \([2](https://arxiv.org/html/2608.14020#S4.E2)\),

ErrRegh⋆\(h^T\)=\{h⋆=1\}∖P\(T\)⊆\{h⋆=1\}∖P\(S\)=ErrRegh⋆\(h^S\)\.∎\\ErrReg\_\{h^\{\\star\}\}\(\\hat\{h\}\_\{T\}\)=\\\{h^\{\\star\}\{=\}1\\\}\\setminus P\(T\)\\;\\subseteq\\;\\\{h^\{\\star\}\{=\}1\\\}\\setminus P\(S\)=\\ErrReg\_\{h^\{\\star\}\}\(\\hat\{h\}\_\{S\}\)\.\\qed

The three edge cases the model permits are all harmless, and for instructive reasons\. Repeated points do not changeVℋ​\(L\)V\_\{\\mathcal\{H\}\}\(L\)at all\. An out\-of\-support insertion\(x,h⋆​\(x\)\)\(x,h^\{\\star\}\(x\)\)is still a*correct*constraint, so it plays the same role as any other; the argument never mentions𝒟\\mathcal\{D\}\. And a*negatively*labeled insertion can only shrinkVℋ​\(L\)V\_\{\\mathcal\{H\}\}\(L\), which by \([2](https://arxiv.org/html/2608.14020#S4.E2)\) can only enlargeP⁡\(L\)P\(L\): negatives are weakly helpful, never harmful\.

###### Corollary 10\.

Letℋ\\mathcal\{H\}be intersection\-closed withVCdim⁡\(ℋ\)=d\\VC\(\\mathcal\{H\}\)=dand letAAbe Closure\. Against every randomized adaptive monotone adversary, at every finite budgetmm\(hence forR𝒟∞R^\{\\infty\}\_\{\\mathcal\{D\}\}\), withnnclean examples,

𝔼⁡\[Err𝒟⁡\(h^,h⋆\)\]≤21​d\+34n,andErr𝒟⁡\(h^,h⋆\)≤1n​\(21​d\+16​ln⁡3δ\)\\mathbb\{E\}\\big\[\\Err\_\{\\mathcal\{D\}\}\(\\hat\{h\},h^\{\\star\}\)\\big\]\\;\\leq\\;\\frac\{21d\+34\}\{n\},\\qquad\\text\{and\}\\qquad\\Err\_\{\\mathcal\{D\}\}\(\\hat\{h\},h^\{\\star\}\)\\;\\leq\\;\\frac\{1\}\{n\}\\Big\(21d\+16\\ln\\tfrac\{3\}\{\\delta\}\\Big\)with probability at least1−δ1\-\\delta\.

###### Proof\.

Compose Proposition[8](https://arxiv.org/html/2608.14020#Thmtheorem8)with Theorem[3](https://arxiv.org/html/2608.14020#Thmtheorem3)and Corollary[5](https://arxiv.org/html/2608.14020#Thmtheorem5), then apply Hanneke’s bound for Closure on intersection\-closed classes\[[7](https://arxiv.org/html/2608.14020#bib.bib7), Theorem 5\]to the clean sampleSS, which consists ofnni\.i\.d\. examples labeled byh⋆h^\{\\star\}\. ∎

Note the constants are inherited rather than re\-derived, and that both bounds are free of logarithmic factors, a point that becomes essential in Theorem[18](https://arxiv.org/html/2608.14020#Thmtheorem18)\.

###### Corollary 11\(The bounded\-budget converse is invisible to Closure\)\.

Mehrotra’s converse\[[9](https://arxiv.org/html/2608.14020#bib.bib9), Remark 3\.2\]showing that errorO⁡\(min⁡\{1,d/n\}\)O\(\\min\\\{1,d/n\\\}\)remains achievable atm=O⁡\(1\)m=O\(1\)proceeds by augmenting a clean lower\-bound class with a common point labeled zero by every concept, and appendingmmcopies of that point\. Both features of the attack are inert against Closure on an intersection\-closed class: the inserted point is labeled*negatively*, and negatives never shrinkPP; and the insertions are*repeated copies*of one point, which do not changeVℋ​\(L\)V\_\{\\mathcal\{H\}\}\(L\)\. On intersection\-closed classes that padding attack is not merely survivable, it is invisible\.

Nothing above is special to Closure\. Any learner meeting the hypotheses of Hanneke’s compression bound and Definition[2](https://arxiv.org/html/2608.14020#Thmtheorem2)inherits the same conclusion, and we record that form because Section[5](https://arxiv.org/html/2608.14020#S5)needs it\.

###### Corollary 12\(Scheme\-level rate bound\)\.

LetAAbe consistent, permutation\-invariant, superset\-monotone, and expressible as a sample compression scheme of sizekkwith permutation\-invariant reconstruction\. Then against every randomized adaptive monotone adversary, at every finite budget \(hence forR𝒟∞R^\{\\infty\}\_\{\\mathcal\{D\}\}\),

𝔼⁡\[Err𝒟⁡\(h^,h⋆\)\]≤21​k\+34n,Err𝒟⁡\(h^,h⋆\)≤1n​\(21​k\+16​ln⁡3δ\)​w\.p\.≥1−δ\.\\mathbb\{E\}\\big\[\\Err\_\{\\mathcal\{D\}\}\(\\hat\{h\},h^\{\\star\}\)\\big\]\\leq\\frac\{21k\+34\}\{n\},\\qquad\\Err\_\{\\mathcal\{D\}\}\(\\hat\{h\},h^\{\\star\}\)\\leq\\frac\{1\}\{n\}\\Big\(21k\+16\\ln\\tfrac\{3\}\{\\delta\}\\Big\)\\ \\text\{ w\.p\. \}\\geq 1\-\\delta\.

###### Proof\.

Superset\-monotonicity and permutation\-invariance makeAAinsertion\-stable, so Theorem[3](https://arxiv.org/html/2608.14020#Thmtheorem3)and Corollary[5](https://arxiv.org/html/2608.14020#Thmtheorem5)reduce the adversarial risk toAA’s risk on the clean i\.i\.d\. sample\. There the four hypotheses are exactly those of\[[7](https://arxiv.org/html/2608.14020#bib.bib7), Theorem 3\], whose bounds are free of logarithmic factors\. ∎

## 5No dimension\-based theory can work

### 5\.1The survivor and the victim

Letℋ≤d=\{h:\|\{x:h⁡\(x\)=1\}\|≤d\}\\mathcal\{H\}\_\{\\leq d\}=\\\{h:\|\\\{x:h\(x\)=1\\\}\|\\leq d\\\}, the concepts labeling at mostddpoints positive a canonical intersection\-closed family\[[7](https://arxiv.org/html/2608.14020#bib.bib7)\]\. Letℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}be Mehrotra’s Littlestone\-two class: for each primeqqtake a disjoint copy of the projective plane of orderqq, retain only its*checker*coordinatescr​Mc\_\{rM\}indexed by incident point–line pairs, setup​\(cr​M\)=𝟏​\{p∈M,p≠r\}u\_\{p\}\(c\_\{rM\}\)=\\mathbf\{1\}\\\{p\\in M,\\,p\\neq r\\\}andvL\(cr​M\)=𝟏\{L=M\}v\_\{L\}\(c\_\{rM\}\)=\\mathbf\{1\}\\\{L=M\\\}, extend each concept by zero outside its component, add the global zero concept, and take the union over primes\.

###### Lemma 13\.

For any domain𝒳\\mathcal\{X\}with\|𝒳\|≥d\|\\mathcal\{X\}\|\\geq d, finite or infinite, we haveVCdim⁡\(ℋ≤d\)=Ldim⁡\(ℋ≤d\)=d\\VC\(\\mathcal\{H\}\_\{\\leq d\}\)=\\Ldim\(\\mathcal\{H\}\_\{\\leq d\}\)=d, andℋ≤d\\mathcal\{H\}\_\{\\leq d\}is intersection\-closed\.

###### Proof\.

VCdim≥d\\VC\\geq d: anyddpoints are shattered, since every subset of add\-set has size at mostdd\.VCdim≤d\\VC\\leq d: the all\-positive pattern ond\+1d\+1points would needd\+1d\+1positives\. ForLdim≤d\\Ldim\\leq d, recall thatLdim\\Ldim*is*the optimal mistake bound in the realizable online model, so exhibiting any one learner with mistake boundddsuffices\. Take the learner predicting11only at points already known positive\. Each mistake occurs whereh⋆h^\{\\star\}is positive and reveals a new element ofh⋆h^\{\\star\}’s positive set, which has at mostddelements, so it errs at mostddtimes\. WithVCdim≤Ldim\\VC\\leq\\Ldimthis givesLdim=VCdim=d\\Ldim=\\VC=d, independent of\|𝒳\|\|\\mathcal\{X\}\|\. Intersection\-closedness is immediate from\|A∩B\|≤\|A\|≤d\|A\\cap B\|\\leq\|A\|\\leq d\. ∎

The mechanism is the intuition for the whole paper:*every positive example spends one unit of a budget ofdd\.*A positive answer is irreversibly informative, so an adversary restricted to adding correctly labeled points cannot manufacture ambiguity\.

Forℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}, Mehrotra provesVCdim⁡\(ℋprime\)=Ldim⁡\(ℋprime\)=2\\VC\(\\mathcal\{H\}\_\{\\mathrm\{prime\}\}\)=\\Ldim\(\\mathcal\{H\}\_\{\\mathrm\{prime\}\}\)=2and the lower bound below\. We verified both computationally, constructingP​G​\(2,q\)PG\(2,q\)from normalized nonzero triples overG​F​\(q\)GF\(q\)forq∈\{2,3\}q\\in\\\{2,3\\\}\(and the two\-prime union\), withLdim\\Ldimcertified by depth\-bounded shattered\-tree search: depth22is achievable, depth33is not\.

### 5\.2The separation

###### Theorem 14\.

Against every randomized adaptive monotone adversary at every finite budgetmm\(hence forR𝒟∞R^\{\\infty\}\_\{\\mathcal\{D\}\}\), Closure onℋ≤2\\mathcal\{H\}\_\{\\leq 2\}satisfies𝔼⁡\[Err𝒟⁡\(h^,h⋆\)\]≤76/n\\mathbb\{E\}\[\\Err\_\{\\mathcal\{D\}\}\(\\hat\{h\},h^\{\\star\}\)\]\\leq 76/n\. The rate isΘ⁡\(1/n\)\\Theta\(1/n\)\.

###### Proof\.

ℋ≤2\\mathcal\{H\}\_\{\\leq 2\}is intersection\-closed withVCdim=2\\VC=2by Lemma[13](https://arxiv.org/html/2608.14020#Thmtheorem13), so Corollary[10](https://arxiv.org/html/2608.14020#Thmtheorem10)withd=2d=2gives\(21⋅2\+34\)/n=76/n\(21\\cdot 2\+34\)/n=76/n\. The adversary may choosem=0m=0, so the rate is at least the clean minimax rate, which isΩ⁡\(1/n\)\\Omega\(1/n\)for a class shattering a pair\[[4](https://arxiv.org/html/2608.14020#bib.bib4)\]\. ∎

Concretely, Closure onℋ≤2\\mathcal\{H\}\_\{\\leq 2\}labels11exactly the positive points it has seen\. Its error region is the set of not\-yet\-seen positives, of which there are at most two\. Every insertion either reveals a new positive, shrinking the error region, or is a negative or a repeat, changing nothing\. There is nothing the adversary can add that is both correctly labeled and unhelpful\.

###### Theorem 15\(\[[9](https://arxiv.org/html/2608.14020#bib.bib9), Theorem 3\.3, casedL=2d\_\{L\}=2; Lemma 3\.16\]\)\.

For everyn≥1n\\geq 1there is a finite budgetmnm\_\{n\}such that every randomized, possibly improper learner forℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}has some target, distribution, and deterministic adaptive monotone adversary with𝔼⁡\[Err𝒟⁡\(h^,h⋆\)\]≥log⁡\(e​n\)/\(30​n\)\\mathbb\{E\}\[\\Err\_\{\\mathcal\{D\}\}\(\\hat\{h\},h^\{\\star\}\)\]\\geq\\log\(en\)/\(30n\)\. With the matchingO⁡\(log⁡\(e​n\)/n\)O\(\\log\(en\)/n\)upper bound by ERM\[[8](https://arxiv.org/html/2608.14020#bib.bib8)\], the rate forℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}isΘ⁡\(log⁡\(e​n\)/n\)\\Theta\(\\log\(en\)/n\)\.

We invoke this rather than reproving it\. Its mechanism is that the adversary can pad two candidate targetsup,vLu\_\{p\},v\_\{L\}to the*identical*multiset, leaving the posterior balanced on a point of test mass1/\(q\+1\)1/\(q\+1\)withq\+1=Θ⁡\(n/log⁡\(e​n\)\)q\+1=\\Theta\(n/\\log\(en\)\)\.

Theorem[15](https://arxiv.org/html/2608.14020#Thmtheorem15)is consistent with Corollary[10](https://arxiv.org/html/2608.14020#Thmtheorem10)only becauseℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}is*not*intersection\-closed; had it been, Corollary[10](https://arxiv.org/html/2608.14020#Thmtheorem10)would have given itΘ⁡\(1/n\)\\Theta\(1/n\)and refuted the framework\. We verified the failure explicitly: for distinct pointsp≠p′p\\neq p^\{\\prime\}on the lineL=p​p′L=pp^\{\\prime\}, the intersectionup∩up′u\_\{p\}\\cap u\_\{p^\{\\prime\}\}has sizeq−1q\-1, and\|up∩vL\|=q\|u\_\{p\}\\cap v\_\{L\}\|=qfor a flagp∈Lp\\in L, while the nonempty positive\-set sizes realizable in the class are exactlyq\+1q\+1andq⁡\(q\+1\)q\(q\+1\)\. Since1≤q−1<q<q\+11\\leq q\-1<q<q\+1forq≥2q\\geq 2, neither intersection belongs to the class\.

###### Corollary 16\(Dimension independence\)\.

ℋ≤2\\mathcal\{H\}\_\{\\leq 2\}andℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}both haveVCdim=Ldim=2\\VC=\\Ldim=2, with monotone\-insertion ratesΘ⁡\(1/n\)\\Theta\(1/n\)andΘ⁡\(log⁡\(e​n\)/n\)\\Theta\(\\log\(en\)/n\)respectively\. Hence no function of VC and Littlestone dimension determines the monotone\-insertion rate\.

Two remarks\. First,d=2d=2is the right place for this: atd=1d=1the rate isΘ⁡\(1/n\)\\Theta\(1/n\)regardless\[[9](https://arxiv.org/html/2608.14020#bib.bib9), Theorem 3\.1\], so there is nothing to separate\. Second, the separation runs in*both*directions\. Intervals onℝ\\mathbb\{R\}are intersection\-closed withVCdim=2\\VC=2, so by Corollary[10](https://arxiv.org/html/2608.14020#Thmtheorem10)they retain the clean rate under arbitrarily many insertions, yet their Littlestone dimension is*unbounded*, growing asΘ⁡\(log⁡N\)\\Theta\(\\log N\)on an ordered domain ofNNpoints \(thresholds alone already give⌊log2⁡N⌋\\lfloor\\log\_\{2\}N\\rfloor\)\. So bounded Littlestone dimension is neither necessary nor sufficient for surviving monotone insertions\.

###### Corollary 17\(A barrier, not a non\-existence\)\.

Every insertion\-stable learner forℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}has*clean\-sample*rateΩ⁡\(log⁡\(e​n\)/n\)\\Omega\(\\log\(en\)/n\)\. Equivalently, onℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}no learner is both insertion\-stable and clean\-rate\-optimal\.

###### Proof\.

WritingCR⁡\(A,n\)\\mathrm\{CR\}\(A,n\)forAA’s clean\-sample rate, Corollary[5](https://arxiv.org/html/2608.14020#Thmtheorem5)givessupm𝔼⁡\[Err𝒟⁡\(A⁡\(T\)\)\]≤CR⁡\(A,n\)\\sup\_\{m\}\\mathbb\{E\}\[\\Err\_\{\\mathcal\{D\}\}\(A\(T\)\)\]\\leq\\mathrm\{CR\}\(A,n\), while Theorem[15](https://arxiv.org/html/2608.14020#Thmtheorem15)givessupm𝔼⁡\[Err𝒟⁡\(A⁡\(T\)\)\]≥log⁡\(e​n\)/\(30​n\)\\sup\_\{m\}\\mathbb\{E\}\[\\Err\_\{\\mathcal\{D\}\}\(A\(T\)\)\]\\geq\\log\(en\)/\(30n\)\. Chain the two\. ∎

The stronger\-sounding claim that*no*insertion\-stable learner exists forℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}would be false: the constant learnerA⁡\(L\)≡h0A\(L\)\\equiv h\_\{0\}is insertion\-stable on every class, its error region never changing\. Insertion\-stability constrains how the error region*moves*, never how*small*it is, so it never implies a good rate on its own; every rate statement here pairs it with a clean\-sample guarantee for a specific learner\.

### 5\.3The negative half, sharpened to a family of algorithms

Corollary[17](https://arxiv.org/html/2608.14020#Thmtheorem17)rules out one property of one learner at a time\. The following says more: forℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}, an entire natural family of algorithms fails, at every size\. This is the one result here whose proof we do not think an expert reconstructs on sight, and it is stated about*schemes*, so no dimension is needed to say it\.

###### Theorem 18\(No monotone compression scheme certifiesℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}\)\.

There is nok<∞k<\\inftyand no learner forℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}that is simultaneously consistent, permutation\-invariant, superset\-monotone, and expressible as a sample compression scheme of sizekkwith permutation\-invariant reconstruction\.

###### Proof\.

Suppose such a learner existed for some finitekk\. Corollary[12](https://arxiv.org/html/2608.14020#Thmtheorem12)would give it𝔼⁡\[Err𝒟\]≤\(21​k\+34\)/n\\mathbb\{E\}\[\\Err\_\{\\mathcal\{D\}\}\]\\leq\(21k\+34\)/nagainst every adaptive monotone adversary at every finite budget\. Butℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}is a*single fixed*class for which Theorem[15](https://arxiv.org/html/2608.14020#Thmtheorem15)supplies, at everynn, an adversary forcing𝔼⁡\[Err𝒟\]≥log⁡\(e​n\)/\(30​n\)\\mathbb\{E\}\[\\Err\_\{\\mathcal\{D\}\}\]\\geq\\log\(en\)/\(30n\)on every learner\. Choosingnnlarge enough thatlog⁡\(e​n\)/30\>21​k\+34\\log\(en\)/30\>21k\+34contradicts the first bound\. Askkwas arbitrary, no finitekkworks\. ∎

Three features of this argument are load\-bearing, and each fails if weakened\.

- •The compression bound must be free of logarithmic factors\.The contradiction pits a constant,21​k\+3421k\+34, against a growinglog⁡\(e​n\)/30\\log\(en\)/30\. The generic sample\-compression estimateO⁡\(k​log⁡\(n/k\)/n\)O\\big\(k\\log\(n/k\)/n\\big\)would instead*exceed*Theorem[15](https://arxiv.org/html/2608.14020#Thmtheorem15)for everyk≥1k\\geq 1at everynn, and the argument would collapse entirely\. Hanneke’s Theorem 3 is log\-free, which is precisely why the hypothesis list in Corollary[12](https://arxiv.org/html/2608.14020#Thmtheorem12)is the one it is\.
- •The bound must not depend on the budget\.Theorem[15](https://arxiv.org/html/2608.14020#Thmtheorem15)’s witnessing budget grows rapidly withnn, so a budget\-dependent guarantee such as Mehrotra’s ownO⁡\(d⁡\(m\+1\)/n\)O\(d\(m\{\+\}1\)/n\)is vacuous in the relevant regime\. Superset\-monotonicity is what removesmmfrom the bound \(Remark[4](https://arxiv.org/html/2608.14020#Thmtheorem4)\)\.
- •The class must be fixed, notnn\-dependent\.Theorem 3\.5 of\[[9](https://arxiv.org/html/2608.14020#bib.bib9)\]yields a different finite class for eachnn, from which no statement about a single class would follow\.ℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}’s union over primes is one class that is hard at everynn, which is what licenses “no finitekk”\.

Table 1:The rate landscape\. The first two rows are the payload: identical VC and Littlestone dimension, rates differing byΘ⁡\(log⁡n\)\\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 learnerA⁡\(L\)≡h0A\(L\)\\equiv h\_\{0\}is insertion\-stable on every class and useful on none\. Provenance of eachisdim\\isdimand last\-column entry:afrom a rate lower bound via the contrapositive of Corollary[12](https://arxiv.org/html/2608.14020#Thmtheorem12)\(in the last row, for the witness class attaining the supremum\);bfrom an explicit scheme, namely Closure \(Proposition[19](https://arxiv.org/html/2608.14020#Thmtheorem19)\);copen\. 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](https://arxiv.org/html/2608.14020#S7)\.![Refer to caption](https://arxiv.org/html/2608.14020v1/fig1_separation.png)Figure 1:Left:ℋ≤2\\mathcal\{H\}\_\{\\leq 2\}andℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}have identical VC and Littlestone dimension but different asymptotic shape, with constants normalized \(the true bounds are≤76\\leq 76, an upper bound, and≥log⁡\(e​n\)/30\\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](https://arxiv.org/html/2608.14020#Thmtheorem16), diverging asΘ⁡\(log⁡n\)\\Theta\(\\log n\)\.

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

One may package Corollary[12](https://arxiv.org/html/2608.14020#Thmtheorem12)’s hypotheses as a measure: letisdim⁡\(ℋ\)\\isdim\(\\mathcal\{H\}\)be the leastkkadmitting such a size\-kkscheme, and∞\\inftyif there is none\. Then Corollary[12](https://arxiv.org/html/2608.14020#Thmtheorem12)reads𝔼⁡\[Err\]≤\(21​isdim⁡\(ℋ\)\+34\)/n\\mathbb\{E\}\[\\Err\]\\leq\(21\\isdim\(\\mathcal\{H\}\)\+34\)/nat every finite budget, and Theorem[18](https://arxiv.org/html/2608.14020#Thmtheorem18)readsisdim⁡\(ℋprime\)=∞\\isdim\(\\mathcal\{H\}\_\{\\mathrm\{prime\}\}\)=\\infty\. On intersection\-closed classes it is pinned down to a constant:

###### Proposition 19\.

For intersection\-closedℋ\\mathcal\{H\}, writingv=VCdim⁡\(ℋ\)v=\\VC\(\\mathcal\{H\}\), asymptotically

c0​v≤isdim⁡\(ℋ\)≤v,c\_\{0\}\\,v\\;\\leq\\;\\isdim\(\\mathcal\{H\}\)\\;\\leq\\;v,soisdim⁡\(ℋ\)=Θ⁡\(v\)\\isdim\(\\mathcal\{H\}\)=\\Theta\(v\)\. HereH2H\_\{2\}denotes binary entropy andc0≈0\.2271c\_\{0\}\\approx 0\.2271solvesH2​\(c\)\+c=1H\_\{2\}\(c\)\+c=1\.

###### Proof\.

*Upper\.*Closure satisfies the first three conditions by Proposition[8](https://arxiv.org/html/2608.14020#Thmtheorem8), and for everyLLat mostVCdim⁡\(ℋ\)\\VC\(\\mathcal\{H\}\)of the observed*positive*points share its closure\[[1](https://arxiv.org/html/2608.14020#bib.bib1)\], so Closure on those points is a scheme of that size\.*Lower\.*LetCCbe shattered,\|C\|=v\|C\|=v\. The2v2^\{v\}samples listingCCunder each labeling must receive2v2^\{v\}distinct messages, since equal messages give equal classifiers and one classifier cannot agree with two labelings ofCC\. Counting labeled subsets of size≤k\\leq kgives2v≤∑j≤k\(vj\)​2j2^\{v\}\\leq\\sum\_\{j\\leq k\}\\binom\{v\}\{j\}2^\{j\}, whose dominant term atk=c​vk=cvis2v​\(H2​\(c\)\+c\)2^\{v\(H\_\{2\}\(c\)\+c\)\}, forcingH2​\(c\)\+c≥1H\_\{2\}\(c\)\+c\\geq 1\. ∎

The separations of Section[5](https://arxiv.org/html/2608.14020#S5)can be read off this quantity, but nothing is gained by doing so: they are Corollary[16](https://arxiv.org/html/2608.14020#Thmtheorem16)and Theorem[18](https://arxiv.org/html/2608.14020#Thmtheorem18), statements about rates and schemes that need no dimension\.

## 7Discussion and open problems

Our results are one\-directional:isdim⁡\(ℋ\)=k\\isdim\(\\mathcal\{H\}\)=kcertifies the rateO⁡\(k/n\)O\(k/n\), but we do not show that largeisdim\\isdim*forces*a large rate\. Theisdim=∞\\isdim=\\inftyentries in Table[1](https://arxiv.org/html/2608.14020#S5.T1)are derived*from*known rate lower bounds via Corollary[12](https://arxiv.org/html/2608.14020#Thmtheorem12)rather than computed intrinsically\.isdim\\isdimcurrently certifies good rates and merely records bad ones\.

###### Open Problem 21\.

Is there a combinatorial quantityq⁡\(ℋ\)q\(\\mathcal\{H\}\), computable fromℋ\\mathcal\{H\}without reference to any rate, such thatq⁡\(ℋ\)q\(\\mathcal\{H\}\)large implies every learner suffersω⁡\(1/n\)\\omega\(1/n\)under monotone insertions? Ideallyq=isdimq=\\isdim, giving a characterization\.

The obstacle is structural:isdim\\isdimis defined by an*existential over learners*, so provingisdim⁡\(ℋ\)=∞\\isdim\(\\mathcal\{H\}\)=\\inftydirectly means excluding every superset\-monotone compression scheme of every size\. Every dimension in this literature that supports a lower bound, whether VC, Littlestone, the extended threshold dimension of\[[3](https://arxiv.org/html/2608.14020#bib.bib3)\], or inference dimension, is instead defined by an explicit shattering or witness structure\. This suggests seeking a shattering\-style quantity first and relating it toisdim\\isdimafterwards\. Mehrotra’s construction indicates the shape: many pairs of concepts agreeing except at a point of non\-negligible mass, together with a correctly labeled completion consistent with both\. Any candidate must vanish on intersection\-closed classes, or it contradicts Corollary[10](https://arxiv.org/html/2608.14020#Thmtheorem10)\. This is a cheap and strong test\.

###### Open Problem 22\.

Which constants are optimal inisdim=Θ⁡\(VCdim\)\\isdim=\\Theta\(\\VC\)for intersection\-closed classes? Proposition[19](https://arxiv.org/html/2608.14020#Thmtheorem19)gives0\.2271​VCdim≤isdim≤VCdim0\.2271\\,\\VC\\leq\\isdim\\leq\\VC, but neither bound is known to be attained\. Closure realizes compression sizeVCdim\\VC, which certifiesisdim≤VCdim\\isdim\\leq\\VCand neverisdim=VCdim\\isdim=\\VC, sinceisdim\\isdimminimizes over all schemes; and Remark[20](https://arxiv.org/html/2608.14020#Thmtheorem20)exhibits an intersection\-closed class withisdim/VCdim=2/3\\isdim/\\VC=2/3\. Letc−c\_\{\-\}andc\+c\_\{\+\}be the least and the greatest value of the ratioisdim/VCdim\\isdim/\\VCacross such classes\. The witness then gives

0\.2271≤c−≤2/3≤c\+≤1,0\.2271\\;\\leq\\;c\_\{\-\}\\;\\leq\\;2/3\\;\\leq\\;c\_\{\+\}\\;\\leq\\;1,and all four inequalities may be strict\.

###### Open Problem 23\.

What isisdim\\isdimon classes that are neither intersection\-closed nor of theℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}type? Proposition[19](https://arxiv.org/html/2608.14020#Thmtheorem19)brackets it on intersection\-closed classes and Theorem[18](https://arxiv.org/html/2608.14020#Thmtheorem18)gives∞\\inftyforℋprime\\mathcal\{H\}\_\{\\mathrm\{prime\}\}, but the middle of the landscape is uncharted in both directions, and Remark[20](https://arxiv.org/html/2608.14020#Thmtheorem20)explains why we have no method that would settle a new case\.

Finally, Corollary[5](https://arxiv.org/html/2608.14020#Thmtheorem5)yields high\-probability guarantees for free wherever a clean high\-probability bound exists, which bears on Mehrotra’s last stated open problem, the optimal\(ε,δ\)\(\\varepsilon,\\delta\)sample complexity under monotone insertions; the matching lower bound is open\.

#### Related work\.

Beyond\[[8](https://arxiv.org/html/2608.14020#bib.bib8),[9](https://arxiv.org/html/2608.14020#bib.bib9)\], the closest methodological relative is\[[3](https://arxiv.org/html/2608.14020#bib.bib3)\], which studies online learning under a*replay*adversary, introduces the extended threshold dimension with matching bounds, uses a closure\-based learner, and characterizes proper learnability by being “\(almost\) intersection\-closed”; they also exhibit classes of constant Littlestone dimension with unbounded extended threshold dimension\. Their model is online with corrupted*feedback*that may be wrong, whereas ours is offline with corrupted*training data*that is always correct, and our risk is measured on the untouched clean distribution; and they obtain matching bounds where we have only an upper bound\. Their lower\-bound technique is the most promising source for the converse above\. Also close is\[[5](https://arxiv.org/html/2608.14020#bib.bib5)\], which studies clean\-label adversarial injections with abstention and introduces a certificate dimension via “robust witnesses”, compact labeled subsets certifying predictions while resisting contamination, structurally close to our compression schemes\. Notably their positive results*require*abstention, without which halfspaces are not learnable\[[2](https://arxiv.org/html/2608.14020#bib.bib2)\]; the monotone constraint lets Closure predict everywhere and still be immune\. The name “monotone adversary” comes from semirandom models in combinatorial optimization\[[6](https://arxiv.org/html/2608.14020#bib.bib6)\], where “helpful” modifications likewise raise recovery thresholds\.

## References

- \[1\]P\. Auer and R\. Ortner\. A new PAC bound for intersection\-closed concept classes\.*Machine Learning*, 66\(2–3\):151–163, 2007\.
- \[2\]A\. Blum, S\. Hanneke, J\. Qian, and H\. Shao\. Robust learning under clean\-label attack\. In*Proceedings of the 34th Conference on Learning Theory*, volume 134 of PMLR, pages 591–634, 2021\.
- \[3\]D\. Dmitriev, H\. E\. Franck, C\. Heinzler, and A\. Sanyal\. Learning in an echo chamber: Online learning with replay adversary\. In*Proceedings of the 2026 Annual ACM–SIAM Symposium on Discrete Algorithms*, pages 6674–6695\. SIAM, 2026\. arXiv:2509\.25135\.
- \[4\]A\. Ehrenfeucht, D\. Haussler, M\. Kearns, and L\. Valiant\. A general lower bound on the number of examples needed for learning\.*Information and Computation*, 82\(3\):247–261, 1989\.
- \[5\]E\. Edelman and S\. Goel\. Reliable abstention under adversarial injections: Tight lower bounds and new upper bounds\. arXiv:2602\.20111, 2026\.
- \[6\]U\. Feige\. Introduction to semirandom models\. In*Beyond the Worst\-Case Analysis of Algorithms*, pages 189–211\. Cambridge University Press, 2021\.
- \[7\]S\. Hanneke\. Refined error bounds for several learning algorithms\.*Journal of Machine Learning Research*, 17\(135\):1–55, 2016\. arXiv:1512\.07146\.
- \[8\]K\. G\. Larsen, C\. Pabbaraju, and A\. Shetty\. Learning with monotone adversarial corruptions\. In*Proceedings of the 37th International Conference on Algorithmic Learning Theory*, volume 313 of PMLR, pages 1–18, 2026\. arXiv:2601\.02193\.
- \[9\]A\. Mehrotra\. Optimal rates for learning with monotone adversaries\. arXiv:2608\.06337, 2026\.