On the Inevitability of the Rashomon Effect

The Rashomon effect in machine learning (ML) occurs when multiple distinct models achieve similar average loss on a given learning task. The set of all models with expected loss smaller than ϵ is called the Rashomon set. The characterization of this set for a given learning task allows searching for models that satisfy additional constraints (e. g. , interpretability, fairness) without compromising accuracy. Though folklore treats the Rashomon set as the collection of all indistinguishable "good" models, there are no established theoretical guarantees that models in this set are statistically indistinguishable. We fill this gap by proposing a hypothesis test framework to choose the best-performing model between two elements in the Rashomon set and derive lower and upper bounds for its probability of error. Specifically, we prove that for any ϵ > 0 if the data set has less than O ({{ {log (/ ({1 -) }) }^ - 1}}) instances, models in the Rashomon set are statistically indistinguishable and the Rashomon effect is inevitable. Additionally, our bounds can guide data scientists to choose an ϵ that generates a Rashomon set so that any two models in it are indistinguishable.