cs.LGNov 18, 2026

Monoculture Robust Learning

Authors: Lee Cohen, Jon Kleinberg, Omer Reingold

Organizations: Stanford University · Cornell University

Abstract

We introduce a notion of monoculture robustness in Probably Approximately Correct (PAC) learning, as a way to mitigate the problem of algorithmic monoculture (Kleinberg and Raghavan, 2021): the tendency of models sharing the same components (e.g., training data) to fail on the same inputs. Specifically, we ask whether a learner with access to a single dataset can output kk individually accurate hypotheses whose joint failure probability is comparable to training on kk independent datasets. We say that such a learning procedure achieves monoculture robustness, and we quantify this by bounding the conjunctive error that all kk hypotheses misclassify points in an individual sense. We design methods for achieving this type of guarantee by drawing a surprising connection between replicability (Impagliazzo et al., 2022) and monoculture robustness. Specifically, we show that if the base learner is ρρ-replicable, then running it independently kk times on the same sample yields individual monoculture error that shrinks exponentially with kk, controlled by the single-run error of the base learner at the point and ρρ. We complement these positive results with a lower bound: for individual monoculture robustness, we prove a worst-case lower bound showing that, for learners, driving the individual conjunctive error down to γγ can require a sample-size multiplier of t=Ω(log⁡(1/γ))t = Ω(\log(1/γ)).

Figures & tables

Explore similar work

Sep 21, 2026

Adversarially Robust PAC Learning with Optimal VC Rates

We study the problem of adversarially robust PAC learning. In this framework, the learner observes independent samples from an unknown distribution over X×{0,1}\mathcal{X} \times \{0,1\}, as in classical PAC learning. However, given a perturbation map U:X→2X\mathcal{U} : \mathcal{X} \to 2^{\mathcal{X}} known to the learner, the goal is to output, with high probability, a predictor that correctly classifies every perturbation z∈U(x)z \in \mathcal{U}(x) of most future examples (x,y)(x,y) drawn from the same underlying distribution. We determine the optimal U\mathcal{U}-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class H\mathcal{H} of VC⁡\operatorname{VC} dimension dd, we prove upper bounds of O(d/ε+log⁡(1/δ)/ε)\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big) in the realizable setting and O(d/ε2+log⁡(1/δ)/ε2)\mathcal{O} \big( d/ε^2 + \log(1/δ)/ε^2 \big) in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs no additional distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call binomial-bagging. We believe that binomial-bagging and its analysis may be of independent interest.
Oct 23, 2026

Near-Optimal List Replicability from Littlestone Dimension

We study the list replicability number in the realizable PAC learning framework and prove that every concept class HH over a countable domain with Littlestone dimension dd and dual VC dimension v∗v^* satisfies LR(H)≤2O(dmin⁡{log⁡d,v∗}).\mathrm{LR}(H)\leq 2^{O(d\min\{\log d,v^*\})}. This matches the worst-case lower bound of 2Ω(d)2^{Ω(d)} up to a logarithmic factor in the exponent and exponentially improves the previous best upper bound LR(H)≤22O(d)\mathrm{LR}(H)\le 2^{2^{O(d)}} of Bun, Livni, and Moran [FOCS 2020]. Unlike earlier bounds of 2Oε(d2)2^{O_ε(d^2)} for fixed accuracy ε>0ε>0 implied by the work of Ghazi, Golowich, Kumar, and Manurangsi [STOC 2021] and Lyu [STOC 2026], our bound is independent of εε. The 2O(dlog⁡d)2^{O(d\log d)} bound follows from a new inductive framework for bounding list replicability that builds on the recent notion of irreducibility from differentially private learning. The 2O(dv∗)2^{O(dv^*)} bound follows from a simple globally stable learner that takes the majority vote of multiple empirical risk minimizers, with stability established using tools from stable regularity.
Oct 18, 2026

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension d≥1d\ge1, the required number of independent examples is Θ ⁣(dρ2α2+log⁡(1/β)α2)Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right), uniformly over independent accuracy, failure, and disagreement parameters α,β,ρ∈(0,1/10)α,β,ρ\in(0,1/10). The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the confidence cost additive. Together with matching lower bounds, this removes the remaining logarithmic overhead and parameter restrictions in the general countable-domain sample-complexity problem. This extended version also retains the earlier explicit constructions and their proofs, including proper learning for VC-one classes, the full finite-atom class, a faster realizable bound, and counterexamples that separate restrictions of particular algorithms from restrictions of the learning problem.