When Free Correct Labels Cost You a Logarithm: Optimal Rates Under Monotone Adversaries

Paper: 2608.06337 Authors: Anay Mehrotra Categories: stat.ML, cs.DS, cs.LG, math.ST

The Gap

Standard realizable PAC learning has a settled answer. For a class of VC dimension d and n i.i.d. labeled examples, the optimal expected error is Theta(d/n). ERM alone does not get you there: Auer and Ortner exhibited classes where empirical risk minimization genuinely pays Theta((d/n) log(n/d)). The log is removed by cleverer learners — the one-inclusion-graph predictor of Haussler, Littlestone and Warmuth (and its modern descendants), or online-to-batch conversion of a mistake-bounded online learner, which gives O(d_L/n) in terms of Littlestone dimension.

Larsen, Pabbaraju and Shetty asked what happens when the sample is polluted in the gentlest possible way. A monotone adversary looks at your clean i.i.d. sample, then appends a finite number of extra examples of its choosing, each one *correctly labeled by the same target hypothesis. You then see a uniform shuffle of the union, and you are still graded on the original distribution. Nothing is mislabeled. Nothing is deleted. You strictly received more true information.

Their findings were unsettling: ERM still achieves O((d/n) log(n/d)) in this model, but every previously known log-free optimal learner can be knocked off the Theta(d/n) rate by such insertions. So the field was left with an uncomfortable ambiguity: is the log an artifact of those particular clever algorithms failing in a new environment, or is the environment itself intrinsically log-hard? That is precisely the gap this paper closes.

[Problem] under monotone insertions, is O((d/n)log(n/d)) the truth,
          or just a failure of the known optimal learners?
              |
              v
[Assumption] insertions are correctly labeled; budget m is finite
             and even KNOWN to the learner; origin hidden by shuffle
              |
    +---------+--------------------------+
    |                                    |
    v                                    v
[Method: lower bound]              [Method: upper bound at d = 1]
one explicit class + one prior     simple IMPROPER learner;
two targets that induce the        leave-one-out argument behind
SAME observed sample law           one-inclusion graph, repaired
    |                                    |
    v                                    v
[Evidence] the two targets         [Evidence] O(1/n) attained,
disagree on a point of mass        no log, so d = 1 is genuinely
~ (d/n)log(n/d) ==> any            different from d >= 2
learner errs w.p. >= 1/2 there
    |                                    |
    +---------+--------------------------+
              |
              v
[Conclusion] minimax expected error = Theta(1/n) at d = 1,
             Theta((d/n) log(n/d)) for d >= 2.
             Same with Littlestone dimension d_L in place of d
             ==> the clean online-to-batch rate O(d_L/n) is
             also unattainable. ERM is minimax-optimal here.

The Increment

One sentence: Before, we knew that *known optimal learners break under monotone insertions; after, we know that no learner can survive them — the extra logarithm is a property of the model, not of the algorithms, for every d >= 2, and VC dimension one is the sole exception.

Core Mechanism

The lower bound is a single indistinguishability construction, and it is elementary. Fix an explicit hypothesis class and a prior over two target hypotheses h1 and h2 that disagree on one distinguished point x* whose probability mass is not negligible — it is on the order of (d/n) log(n/d), i.e. a log factor heavier than the d/n mass that a clean-PAC learner would have to concede. Now let the adversary be target-dependent: when the truth is h1 it inserts one packet of correctly-labeled points, when the truth is h2 it inserts a different packet. The insertions are chosen so that the distribution of the shuffled multiset the learner observes is identical in both worlds. Since the observation carries zero information about which world you are in, any learner — proper, improper, randomized — must be wrong about x* with probability at least 1/2 in one of the two worlds. Multiply by the mass of x* and you have the bound. No concentration inequalities, no packing arguments, no Fano.

Why can the adversary pull this off with only truthful additions? Because both classical routes to the log-free d/n rate are symmetry arguments, and symmetry is exactly what is destroyed. The one-inclusion-graph analysis says: put the n training points and the test point in one bag of n+1 points; by exchangeability, the test point is equally likely to be any of them; the predictor’s error is then at most (out-degree)/(n+1), and the out-degree is at most d. Online-to-batch is the same trick in different clothes — average over the positions of a random ordering. Under monotone insertions, the test point is exchangeable with the n clean points only, but the learner cannot tell clean points from inserted ones. The 1/(n+1) bookkeeping loses its justification, and the adversary’s whole job is to make the fake points look like exactly the clean points that would have arisen under the other target.

The complementary result is the d = 1 upper bound. VC-dimension-one classes are tree-like: their one-inclusion graphs admit orientations of out-degree one, and correctly-labeled extra points can only shrink the set of consistent hypotheses along that tree structure. The paper gives a simple improper learner (its prediction need not lie in the class) and adapts the leave-one-out argument to the non-exchangeable sample, recovering O(1/n). The properness is load-bearing, which is itself a hint: the model punishes learners whose output is forced into the class.

CLEAN PAC (exchangeable)
   bag = [ x1 x2 x3 ... xn | x_test ]      all n+1 slots symmetric
                   |
                   v
   one-inclusion / online-to-batch:  err <= d / (n+1)


MONOTONE ADVERSARY (not exchangeable)
   clean S ~ D^n            adversary T (depends on S and h*)
     [ x1 ... xn ]     +      [ t1 ... tm ]   all labels CORRECT
                   \             /
                    v           v
             shuffle( S + T )  -- origin of each point hidden
                   |
                   v
   test point is symmetric with S only, but S is unidentifiable
                   |
                   v
   the 1/(n+1) accounting has no ground to stand on


THE HARD INSTANCE
   world A: target h1 --> adversary inserts T_A --+
                                                  |--> SAME law of
   world B: target h2 --> adversary inserts T_B --+     observed sample
                   |
                   v
   h1(x*) != h2(x*)  with  D(x*) ~ (d/n) log(n/d)
                   |
                   v
   any learner: P[error on x*] >= 1/2 in one world
                   ==> expected error >= (1/2) * (d/n) log(n/d)

The structural metaphor: a lawyer packing the courtroom with truthful witnesses.

You are the juror. Normally you interview n people pulled at random off the street — that randomness is the entire basis of your statistical reasoning. Your best inference trick is this: “the next random person I meet is statistically just like one of the n I already interviewed, so if my rule would have gotten one of them wrong, I would have noticed.” That trick — the next stranger is interchangeable with the ones already in the room — is the one-inclusion graph, and it is what buys you the d/n rate.

Now a lawyer is allowed to add witnesses. Crucially, she cannot suborn perjury: every witness she adds tells the literal truth, consistent with the same underlying facts. But she chooses *which truthful people to bring, after seeing who you already interviewed, and they enter the room mixed in with your random sample so you cannot tell who walked in from the street and who arrived by subpoena. Now your trick collapses. The room is no longer a random draw from the population, and you have no way to peel the random draw back out.

The paper’s lower bound is the lawyer’s best play: she constructs two entire cases, h1 and h2, that differ on one materially important question x*, and packs the room so that the transcript reads identically under either case. Every word is true in both. You must guess x**, and you will be wrong half the time, and x* matters a log-factor more than it would have if nobody had “helped” you. The d = 1 result is the special case where the dispute has a single axis — a line — so that no matter who the lawyer brings, the truthful testimony still brackets the answer from both sides, and a juror willing to render a verdict outside the menu of offered cases (the improper learner) recovers the clean rate.

Key Concepts

• Exchangeability, and why learning rates secretly depend on it: A sample is exchangeable if shuffling it does not change its probability. An i.i.d. sample is. That sounds like bookkeeping, but it is the engine behind the optimal PAC learners: they never estimate anything, they just argue “the test point could have been any one of these n+1 points, so my error is at most 1 in n+1 times how badly I can be structurally confused”. Concretely: with d=1 thresholds on the line, look at your n points plus the unlabeled test point, and ask how many of the n+1 possible “which one is the test point” assignments your rule gets wrong — the answer is at most one, hence error <= 1/(n+1). Break the “equally likely” step and that entire argument is gone, even if every label is pristine. This paper is a demonstration that exchangeability, not label noise, is the fragile resource.

• Monotone adversary: A corruption model where the adversary may only make things *look more helpful. The term comes from semi-random graph problems — e.g. planted clique or stochastic block models where an adversary adds edges inside the planted community and removes edges across it, monotonically “strengthening” the signal. The classic lesson there is that such moves nevertheless destroy spectral algorithms, because those algorithms rely on the shape of the randomness rather than on the signal itself. Here the analogue is exact: adding correctly-labeled examples is monotone in information content, yet it kills algorithms that rely on the shape (the symmetry) of the sampling process. Note how strong the negative result is: the adversary’s budget is finite and known to the learner, so this is not a “the adversary drowns you in data” effect.

• Why ERM eats a log and why that suddenly becomes optimal: ERM only promises “I am consistent with the data”. On some classes, being merely consistent leaves you fooled on a region of mass (d/n) log(n/d) — the log is a coupon-collector-flavored penalty for the region your sample happens to under-cover. The log-free learners are cleverer: they use the geometry of the class plus the exchangeability trick to pick *among consistent hypotheses wisely. This paper’s punchline is a levelling-down: strip exchangeability and the cleverness has nothing to bite on, so everybody falls back to ERM’s rate — and ERM, which never depended on exchangeability in the first place, turns out to be minimax-optimal in the model. The Littlestone version says the same for the online route: finite mistake bound no longer buys you O(d_L/n), because online-to-batch conversion is also an averaging-over-orderings argument.

Framework Shift

Before (mainstream view):              After (this paper):

  corruption is about LABELS             corruption is about the
       |                                 SAMPLING SYMMETRY
       v                                      |
  wrong labels  ==> hard                      v
  right labels  ==> harmless              exchangeability is the
       |                                  resource being spent
       v                                      |
  "more true data cannot hurt"                v
       |                                  right labels + wrong
       v                                  provenance ==> hard
  the log in ERM's rate is an           |
  ALGORITHM defect; fix it with            v
  one-inclusion graph or                 the log is a MODEL fact
  online-to-batch                        for all d >= 2;
       |                                 ERM becomes optimal;
       v                                 d = 1 is the lone island,
  Theta(d/n) is the frontier             reached by an IMPROPER rule
                                              |
                                              v
                                         Theta(1/n) at d=1,
                                         Theta((d/n)log(n/d)) at d>=2
                                         (also with d_L)

One sentence: from “which algorithm is optimal against this corruption?” to “which structural property of the sample was the optimality resting on?” — the core shift is recognizing that the Theta(d/n) frontier was a symmetry result, not a statistics result, and symmetry can be destroyed with nothing but the truth.

Expert Assessment

A caveat up front: I am working from the abstract and the surrounding literature, not from a line-by-line read of the proofs. Everything below is calibrated accordingly — in particular I cannot vouch for the constants or for the exact form of the hard class.

Problem choice: A real gap, and a well-posed one. The prior paper explicitly asked the question, so this is not a manufactured target. The bigger reason to care is diagnostic rather than practical: the field has accumulated a lot of machinery whose optimality quietly depends on exchangeability (one-inclusion graphs, sample compression bounds, online-to-batch, conformal prediction, most transductive arguments). This paper is a clean stress test of how much of that survives a very mild perturbation, and the answer — almost none of the log-removing part — is worth knowing. It is not a paper that will change what anyone deploys. It sits in the “tighten and delimit the theory” lane, which is where I would expect it: a follow-up that finishes a question rather than opens a field.

Method maturity: Clever, not brute. The signature of a good lower bound is that it is short, and “one explicit class, one prior, two targets that induce the same sample” is about as short as it gets. Two-point indistinguishability with a 1/2 error probability is the oldest trick in the book, and getting the disagreement point to carry (d/n) log(n/d) mass while preserving exact indistinguishability is where the actual work must be hiding. The fact that the same construction yields the Littlestone statement suggests it is genuinely structural rather than a one-off gadget. The d=1 upper bound is the more delicate half — reusing the leave-one-out argument on non-exchangeable data is a real repair, and the improperness is a legitimate technical concession, not sloppiness. If I had one methodological worry it is the usual one for tight minimax results: worst-case-over-classes results can be driven by a pathological class and tell you nothing about the classes you care about. The paper (as advertised) does not give a class-dependent characterization, so the honest reading is “there exists a d-dimensional class that is log-hard”, not “your class is log-hard”.

Experimental integrity: There are no experiments, and there should not be — this is a minimax characterization. The right substitute for scrutiny here is: do the upper and lower bounds actually meet in the same model, with the same quantifiers? The claims as stated look properly aligned (the O((d/n)log(n/d)) upper bound comes from ERM in the prior work; the new bound is Omega of the same). Two quantifier details I would verify carefully in the paper: that the lower bound really holds when the insertion budget m is known to the learner and finite (this is claimed, and it is what makes the result strong rather than cheap), and that the learner is allowed to be randomized and improper in the lower bound (otherwise the d=1 improper upper bound and the d>=2 lower bound would be measuring different things). No red flags visible from the abstract, but those are the load-bearing joints.

Writing quality: The abstract does the right things — states the model precisely, credits the prior work, separates the d=1 and d>=2 regimes, and advertises that the proofs are elementary rather than hiding behind machinery. The line I would push back on is “somewhat counterintuitively”: once you say the word *exchangeability, the result stops being counterintuitive and starts being obvious in hindsight, which is a compliment. The section that would most elevate the paper is a plain-English anatomy of why the two worlds are indistinguishable — a worked d=2 instance with concrete numbers, showing the adversary’s packet in both worlds side by side. A reader who can hold that one picture in their head owns the whole paper. Second on my list: an explicit discussion of properness at d=1, since the improper learner raises the immediate question of whether proper learners pay the log even at d=1, which would be a nice separation in its own right.

Verdict: weak accept — a tight, elegant, elementary resolution of an explicitly posed open question, with the d=1 island as a genuine bonus; the ceiling is limited by the narrowness of the model and the absence of any class-dependent story about *when the log actually bites.

Takeaways

• Audit your analyses for hidden exchangeability, not just for hidden i.i.d.-ness. If a bound’s proof anywhere contains “by symmetry, the test point is as likely to be any of these”, that bound is fragile in ways label-noise robustness will not protect. This applies well beyond PAC theory: conformal prediction, leave-one-out and cross-validation guarantees, permutation tests, and online-to-batch conversions all rest on the same step. Any pipeline that appends curated-but-correct data (hard-negative mining, active-learning pools, synthetic examples verified by a checker, human-added “obviously true” cases, dataset patches from bug reports) is a monotone adversary in the wild, and it invalidates exactly this step.

• “All labels are correct” is a much weaker safety guarantee than it feels like. The transferable framing is: corruption models should be indexed by *what they do to provenance, not only by what they do to values. A dataset where every row is true but the rows were selected conditional on your original sample is not a dataset you can reason about with i.i.d. tools, and the loss here is a full log factor even with a known, finite insertion budget.

• When symmetry is unavailable, prefer the algorithm that never used it. ERM’s rate is worse in clean PAC precisely because it makes no structural assumptions — and that is exactly why it is the one left standing here. A useful heuristic for practice: under provenance uncertainty, the “dumber”, consistency-only method may be the robust choice, and the sophisticated method’s advantage may be entirely an artifact of a symmetry you no longer have.

• Improperness as a robustness lever. The one positive result in the paper needs a learner that is allowed to output something outside the hypothesis class. That is a cheap, concrete move to try whenever you are fighting a distribution-shift-flavored obstruction: relax the output space (mixtures, abstention, randomized predictions) before you relax the problem.

• The lower-bound recipe itself is stealable. If you want to show a data-collection protocol is intrinsically lossy, do not try to defeat all algorithms. Build two ground truths that disagree on something expensive, then show the protocol emits the same observation distribution under both. Two points and a 1/2 beats a concentration argument almost every time.