Learning multiple accurate models from one dataset reduces shared errors

Monoculture Robust Learning

Machine Learning

Summary

When many computer programs learn from the same data, they tend to make mistakes on the same tricky examples, which is a problem called algorithmic monoculture. The authors introduce a way to measure if one dataset can produce multiple good models that don’t all fail on the same examples. They connect this idea to a concept called replicability, showing that running a reliable learner several times can create diverse models whose errors don’t overlap much. They also explain that to reduce these shared errors significantly, you might need much more data.

What this means in practice

  • For machine learning engineers: Design systems that generate multiple diverse models from a single dataset to reduce simultaneous failures on the same inputs
  • For data infrastructure teams: Plan data collection strategies by understanding the trade-off between dataset size and reducing shared errors across multiple models

A theory result. No direct application yet.

Authors

Lee Cohen, Jon Kleinberg, Omer Reingold

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 $k$ individually accurate hypotheses whose joint failure probability is comparable to training on $k$ independent datasets. We say that such a learning procedure achieves monoculture robustness, and we quantify this by bounding the conjunctive error that all $k$ 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 $k$ times on the same sample yields individual monoculture error that shrinks exponentially with $k$, 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/γ))$.