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

CardsList
  1. Adversarially Robust PAC Learning with Optimal VC Rates

    Sep 21, 2026Steve Hanneke, Amirreza ShaeiriSample ComplexityAdversarial Robustness

  2. Near-Optimal List Replicability from Littlestone Dimension

    Oct 23, 2026Ari Blondal, Pooya Hatami, Chavdar Lalov +1PAC Learning