On Mehrotra's hard class the authors 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.
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.
This model shows that adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning.
Worst-case multiclass bounds do not become smaller when the best classifier is already nearly correct: what is missing is an optimistic rate, a guarantee whose fluctuation scales with the oracle risk itself. For a class of Natarajan dimension $d_N$ and Daniely-Shalev-Shwartz dimension $d_{DS}$, the optimal excess risk is known at the two endpoints ($d_{DS}/n$ realizable, $\sqrt{d_N/n}+d_{DS}/n$ agnostic [HMZ24, CEH+26, Pab26]) and open in between. We close the gap: at every fixed oracle risk $L^\star$, the optimal excess risk is $\widetilde{\Theta}(\sqrt{L^\star d_N/n}+d_{DS}/n)$, uniformly in the alphabet size, attained by a learner that knows neither $L^\star$ nor the confidence level. The upper bound composes the cover-menu-compression architecture of [CEH+26], at the realizable rate of [Pab26], with a new comparator-facing relative compression theorem: a size-$k$ compression rule that empirically dominates a comparator $h$ has population risk at most $L(h)+O(\sqrt{L(h)\Gamma}+\Gamma)$ with $\Gamma=(k\log n+\log(1/\delta))/n$, without stability; this transfers the comparison principle of the sharp binary theory [MQZ26] while discarding its Boolean-cube geometry, which does not lift to multiclass labels. The lower bound forces both terms using one class and one distribution at every fixed $L^\star$, by a pair-Assouad scheme calibrated to $L^\star$ and a fiber argument on the pseudo-cubes underlying the Natarajan-versus-DS separation of [BCD+22]. Both theorems extend to list learning: against the best $r$-tuple of hypotheses, the same architecture and the same two engines yield an optimistic rate and a lower bound of the same shape, forcing the fluctuation term that [Pab26] expected to be necessary against list comparators, and removing the factor $r$ from the known realizable list lower bound.
Xiaoyu Li, Andi Han, Jiaojiao Jiang et al.· 1 citation
A stable compression score can still select the worse model. In our dense study, a split-half reliable path-quadratic score predicted a 16.1\% gain, while the selected endpoints were 6.0--7.7% worse than two controls. We ask what a compression statistic can justify when deployment cares about the worst supplied group. We treat each statistic as an information interface. Its observation leaves a fiber of compatible endpoint-risk tables, and only orders fixed across that fiber are identified. Cone and fiber identities quantify the remaining uncertainty, while matched observations reverse endpoint order for pooled moments, group-local moments, and reference-path curvature. Sequential composition adds one state variable: the slack from each group risk to the current maximum. This vector determines every unrestricted one-step response, and a margin condition keeps the active group fixed along paths with bounded relative drift. The experiments follow the same ladder. Across three dense LLMs, an early-preserving allocation reduces worst-group perplexity inflation by 12.6--20.9%; target-matched complete-menu selection improves over its references by 2.7--8.0%. Across all 16 routed layers of OLMoE, pooled endpoint refresh lowers held-out worst-group teacher KL by 15.8% over the best static score. A compute-matched hard-max trajectory ends 32.7% worse than pooled, and neither adaptive trajectory improves excess NLL. Local evidence can narrow a menu. Complete endpoints rank that menu, while multistep claims also require control of the evolving active face and future candidates.
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 $\Omega (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, S. Dughmi, Chirag Pabbaraju· 0 citations
It is shown that the classical Bayesian bootstrap closes this gap in U-calibration, which asks one online probability fore-caster to have low regret for every bounded proper loss, including losses unknown when the forecasts are made.
Best-of-$N$ reranking draws independent candidates from a reference policy and selects the response maximal under a fixed, sample-independent strict total order on outcomes. The selected law may differ substantially from the reference in Kullback–Leibler divergence. Prior work introduced a bounded statistic depending only on the accepted response's reference mass and conjectured that its expectation upper-bounds this divergence. This letter proves the conjecture for every finite ordered distribution. The proof applies to the full positive cumulative-distribution-function power family, not only integer sample counts. It combines a strictly monotone binary gauge, a top-atom chain-rule recursion, and induction, and yields an exact nonnegative slack decomposition and a quantitative tightness bound. A beta-quantile representation identifies the universal divergence cap. We also treat reference-preserving reward ties, provide deterministic high-precision illustrations, derive clipped fixed-sample confidence bounds, and specify stable evaluation and exact probability-logging requirements.
Yutong Zhang, Yaoran Yang· IEEE Signal Processing Lette...· 0 citations