The Double-Edged Nature of the Rashomon Set for Trustworthy Machine Learning

AI summary

Overview

Research area: Trustworthy machine learning — specifically model multiplicity (the Rashomon effect), adversarial robustness, algorithmic stability, and information-theoretic privacy.

Technical level: Intermediate. The paper is written as a conceptual piece with accessible framing, but its claims are supported by formal theorems, proofs, and bounds, so comfort with basic probability, loss functions, and adversarial attacks helps.

Scope: The paper examines how the properties of robustness, stability, and privacy differ when analyzed at the level of a single near-optimal model versus the level of the entire Rashomon set of near-optimal models.

What This Paper Is About

Real machine learning pipelines almost never produce one single best model; hyperparameter sweeps, random seeds, fairness constraints, and model search all yield many models with nearly identical accuracy. The authors argue that this collection — the Rashomon set — should be treated as the natural unit of analysis in governance and auditing, rather than any one model. They then ask what a large, diverse Rashomon set does to trustworthiness, showing that the same diversity that enables robustness also causes information leakage.

Key Contributions

1. A duality framing of Rashomon sets. The paper argues that multiplicity is simultaneously a resource (a pool of alternate models for reactive robustness) and a risk (a richer surface for information leakage about the training data), formalized as a robustness–privacy trade-off governed by diversity.

2. Theoretical results for the single-model case. Theorem 4.1 shows that mutual information between a decision tree and its training data is bounded as I(f;S) = O(l_f log d) for trees with l_f leaves over {0,1}^d, so sparser trees are more private. Theorem 4.2 shows that a single rule list is inherently vulnerable: the adversarial error gap is at least (n_+ − n̄_+)/n, and when each rule uses a single literal (l = 1) this holds with perturbation budget η = 1.

3. Theoretical results for the Rashomon-set case. The authors prove that diversity enables reactive robustness (diversity bounds in Hamming distance for 0–1 loss and in the angle between weight vectors for linear models), that the set is stable under small distribution shifts and under small dataset modifications, and that ensembles drawn from the set approximate the underlying label distribution increasingly well as more models are released.

4. Empirical illustration and a released codebase. Experiments on the COMPAS recidivism dataset (Figure 1) plot collections of sparse decision trees of varying size and identity, showing adversarial accuracy rising with diversity while reconstruction error falls. Experiments with multi-layer perceptrons are reported to show the trends extend to more complex architectures, and code is released at https://github.com/EtHsu0/rashomon-duality.

Main Findings

• Sparse models are private and stable but fragile. Theorem 4.1 bounds mutual information by the number of leaves, so sparser trees leak less. The paper connects this to membership-inference advantage, which prior work bounds by the model's generalization gap, and notes that regularization simultaneously improves algorithmic stability. Despite this, Theorem 4.2 shows a single rule list remains vulnerable: the adversarial error gap is at least (n_+ − n̄_+)/n, meaning a low-error robust rule list requires substantial class imbalance, and balanced datasets are unlikely to admit robust single models.

• Diversity enables reactive robustness. For 0–1 loss, the bound |L_{S′}(f) − L_{S′}(f̂)| ≤ H_{S′}(f, f̂) shows a model can only beat the attacked model on the adversarial dataset if it disagrees with it sufficiently often; models that mimic f̂ fail the same way. Diversity is measured by Hamming distance of predictions for discrete hypothesis spaces (decision trees, rule lists, scoring systems) and by the angle between weight vectors for linear classifiers.

• Adversarial transfer depends on model geometry. Theorem 5.1 gives the loss of any linear model w on the adversarially perturbed dataset as (1/n) Σ φ(y_i wᵀx_i − η‖w‖₂ cos(w, ŵ_S)). Corollary 5.2 shows that under exponential loss, for unit weights with cos(w₁, ŵ_S) > cos(w₂, ŵ_S), the loss ratio L̂_{S′}(w₁)/L̂_S(w₁) exceeds that of w₂ when η > 0; Corollary 5.3 shows that for large enough η the higher-angle model eventually attains lower adversarial loss. The authors caution that diversity only through parallel shifts of the boundary likely will not produce a robust member.

• The Rashomon set is stable under small distribution shift. Theorem 5.4 states that for a bounded loss φ ∈ [0,1] and covariate shift with KL(D‖D′) ≤ ε²/8, a function in the true Rashomon set of D at tolerance ε/2 is also in the true Rashomon set of D′ at tolerance ε. Absolute accuracy is not guaranteed, since a shift can increase task difficulty for all models.

• Empirical Rashomon sets are stable to small dataset edits. Theorem 5.5 shows that for 0–1 loss, if two datasets of size n differ in at most K samples, each empirical Rashomon set at tolerance ε is contained in the other at tolerance ε + 2K/n. Empirically, across four datasets with pre-computed Rashomon sets, raising tolerance from ε to ε + 2K/n kept the recomputed sets highly overlapping: under a 6% dataset modification more than 80% of models remained, and for smaller perturbations such as 2% the sets were nearly identical (Figure 11).

• Larger Rashomon sets leak more. Theorem 5.6 bounds the expected total variation distance between the true conditional label probability p(x) and an ensemble average q_Π(x) of m models sampled without replacement from a set of N models: E_Π[TV(p(x)‖q_Π(x))] ≤ sqrt((p(x) − μ(x))² + (N − m)σ²(x)/((N − 1)m)), where μ and σ² are the mean and variance of predictions in the set at input x. When each f_k(x) ∈ [δ, 1 − δ], the analogous KL bound divides the same expression by δ(1 − δ). Leakage therefore decreases as m grows — larger sets offer more "views" of the data.

• Diversity is necessary for leakage to grow. Theorem C.5 is cited as showing that model diversity is required for ensembles to leak more about the underlying distribution as models are added.

• The trade-off is measured on a real dataset. Figure 1 uses COMPAS recidivism data, where each point is a collection of sparse decision trees selected from the Rashomon set, varying how many and which trees are included. Increasing diversity raises adversarial accuracy while lowering reconstruction error, and the paper reports similar behavior across multiple datasets in Section 6. The Rashomon tolerance ε is described as typically corresponding to a slight accuracy drop, on the order of 1–3%.

• Single-model and set-level criteria diverge. Table 1 summarizes the contrast: a single sparse model is vulnerable to attack but private and algorithmically stable; the Rashomon set offers reactive robustness and stability under shift but is leakier.

Methodology in Plain English

The authors take a conceptual approach backed by theory and experiments rather than proposing a new learning algorithm. They set up standard notation: n i.i.d. samples, a hypothesis space F of interpretable models (linear models and decision trees, though some results apply more generally), and a regularized objective combining empirical risk with a penalty Ω(f). The Rashomon set is defined as all models whose objective is within a tolerance ε of the empirical risk minimizer's objective, following Semenova et al. (2022); a true-distribution version is defined analogously.

From there, they analyze trustworthiness criteria at two levels. For a single model, they derive bounds on how much mutual information a tree leaks and how much a rule list's error can be increased by flipping features, working through the structure of if-then-else rule lists and 0–1 and margin-based losses. For the set, they prove a triangle-inequality bound linking robustness on an adversarially perturbed dataset to prediction disagreement with the attacked model, then extend this to linear classifiers where the geometry of weight vectors replaces Hamming distance. They prove stability results for distribution shift (using KL divergence between the covariate distributions) and for neighboring datasets, and an ensemble bound relating sample size m to how closely the ensemble matches the true label distribution.

Empirically, they illustrate the trade-off with sparse decision trees on COMPAS, vary the number and identity of released trees, and track adversarial accuracy against reconstruction error. They also test dataset-level stability by modifying K samples in four datasets with pre-computed Rashomon sets and recomputing. Multi-layer perceptron experiments are reported to check whether the trends carry beyond interpretable model classes. The exact numerical values of adversarial accuracy, reconstruction error, and the names of the four datasets used for the stability experiment are not reported in the available content, and Section 6, where the cross-dataset results appear, is truncated.

Why This Matters

Research impact. The paper shifts attention from asking whether an individual model is robust or private to asking what the collection of near-optimal models does. It connects model multiplicity to adversarial transfer and to information leakage in a single framework, and it offers stability results suggesting a Rashomon set computed once can remain valid under small distribution shifts without recomputation — a claim with consequences for how robustness audits and privacy analyses are scoped.

Real-world applications:

• Lending and criminal justice. These high-stakes domains already generate many near-optimal models through hyperparameter sweeps and fairness constraints; the paper's framing suggests regulators and auditors should treat the whole candidate pool as the object of scrutiny, as illustrated on COMPAS recidivism data.
• Healthcare. Where institutions must document and compare models, the stability results imply that a documented set of near-optimal models need not be fully rebuilt after small data updates.
• Regulatory reporting and transparency disclosure. Releasing several interpretable models to satisfy transparency requirements may each look safe individually while collectively leaking more about the training data than intended.
• Deployed systems under attack. Organizations that detect an attack can rotate to a differently behaving near-optimal model instead of retraining from scratch, provided the set contains disagreement aligned with the attack geometry.

Industry relevance. The paper's central practical claim is computational: reactive robustness via model switching is cheaper than periodic retraining, and the pool of alternates usually already exists in the pipeline. This makes the robustness–privacy trade-off a governance and disclosure question, not just an algorithmic one.

Future Directions

• Choosing and validating diversity metrics. The authors explicitly state they do not claim any single diversity metric guarantees robustness against all adaptive attacks, leaving open how to select a metric that aligns with realistic attack geometry — they note that diversity through parallel boundary shifts likely does not suffice.

• Extending beyond the analyzed model classes. Results are developed mainly for decision trees, rule lists, and linear models, with multi-layer perceptron experiments reported as a check; whether the set-level bounds carry to other hypothesis classes is not established in the available content.

• Turning the trade-off into policy. If the Rashomon set is the natural policy object, what disclosure rules follow from the leakage bound in Theorem 5.6 — how many near-optimal models can be released, and with what diversity, before aggregate leakage becomes unacceptable?

• Connecting set-level leakage to formal privacy notions. The paper frames leakage information-theoretically and relates it to membership inference and differential privacy in prior work, but the available content does not establish a set-level differential privacy guarantee, leaving that link as an open question.

Target Audience

This paper suits machine learning researchers working on model multiplicity, interpretability, adversarial robustness, and privacy; practitioners responsible for model selection, auditing, and disclosure in regulated or high-stakes settings; and policy-minded readers interested in how the "many good models" phenomenon should be governed. Readers without a theoretical background can follow the conceptual argument and the COMPAS illustration, while the theorem statements and bounds will be most useful to those already familiar with Rashomon set literature.

Authors’ abstract

Real-world machine learning (ML) pipelines rarely produce a single model; instead, they produce a Rashomon set of many near-optimal ones. We show that this multiplicity reshapes key aspects of trustworthiness. At the individual-model level, sparse interpretable models tend to preserve privacy but are fragile to adversarial attacks. In contrast, the diversity within a large Rashomon set enables reactive robustness: even when an attack compromises one model, a practitioner can switch to a different near-optimal model that remains accurate, without retraining. However, the same diversity increases information leakage, as disclosing more near-optimal models provides an attacker with progressively richer views of the training data. This produces a robustness-privacy trade-off governed by diversity, which we analyze theoretically and empirically. Beyond this trade-off, Rashomon sets are stable under small distribution shifts, so a set computed once remains valid under such shifts without re-computation. Our results highlight the dual role of Rashomon sets as both a resource and a risk for trustworthy ML.