# The Dataset Multiplicity Problem: How Unreliable Data Impacts Predictions

Anna P. Meyer  Aws Albarghouthi  Loris D’Antoni

###### Abstract

We introduce dataset multiplicity, a way to study how inaccuracies,
uncertainty, and social bias in training datasets impact test-time
predictions. The dataset multiplicity framework asks a counterfactual question
of what the set of resultant models (and associated test-time predictions)
would be if we could somehow access all hypothetical, unbiased versions of the
dataset. We discuss how to use this framework to encapsulate various sources
of uncertainty in datasets’ factualness, including systemic social bias, data
collection practices, and noisy labels or features. We show how to exactly
analyze the impacts of dataset multiplicity for a specific model architecture
and type of uncertainty: linear models with label errors. Our empirical
analysis shows that real-world datasets, under reasonable assumptions, contain
many test samples whose predictions are affected by dataset multiplicity.
Furthermore, the choice of domain-specific dataset multiplicity definition
determines what samples are affected, and whether different demographic groups
are disparately impacted. Finally, we discuss implications of dataset
multiplicity for machine learning practice and research, including
considerations for when model outcomes should not be trusted.

##  1 Introduction

Datasets that power machine learning algorithms are supposed to be accurate
and fully representative of the world, but in practice, this level of
precision and representativeness is impossible [27, 44]. Datasets display
inaccuracies — which we use as a catch-all term for both errors and
nonrepresentativeness — due to sampling bias [10], human errors in label or
feature transcription [39, 63], and sometimes deliberate poisoning attacks [3,
52]. Datasets can also reflect undesirable societal inequities. But more
broadly, datasets never reflect objective truths because the worldview of
their creators is imbued in the data collection and postprocessing [27, 42,
44]. Additionally, seemingly-trivial decisions in the data collection or
annotation process influence exactly what data is included, or not [42, 45].
In psychology, these minute decisions have been termed ‘researcher degrees of
freedom,’ i.e., choices that can inadvertently influence conclusions that one
ultimately draws from the data analysis [55]. In this paper, we study how
unreliable data of all kinds impacts the predictions of the models trained on
such data and frame this analysis as a ‘multiplicity problem.’

Multiplicity occurs when there are multiple explanations for the same
phenomenon. Many recent works in machine learning have studied predictive
multiplicity, which occurs when multiple models have equivalent accuracy, but
still give different predictions to individual samples [14, 33, 51]. A
consequence of predictive multiplicity is procedural unfairness concerns;
namely, defending the choice of model may be challenging when there are
alternatives that give more favorable predictions to some individuals [6]. But
model selection is just one source of multiplicity. In this paper, we argue
that it makes sense to consider training datasets through a multiplicity lens,
as well. To do so, we will consider a _set of datasets_. Intuitively, this set
captures all datasets that could have been collected if the world was slightly
different, i.e., if we could correct the unknown inaccuracies in the data. We
illustrate this idea through the following example.

#### Example dataset multiplicity use case

Suppose a company wants to deploy a machine learning model to decide what to
pay new employees. They have access to current employees’ backgrounds,
qualifications, and salaries. However, they are aware that in various
societies, including the United States, there is a gender wage gap, i.e.,
systematic disparities in the average pay between men and women [65].
Economists believe that while some of the gap is attributable to factors like
choice of job industry, overt discrimination also plays a role [7]. But even
though we know that discrimination exists, it is very difficult to adjudicate
whether specific compensation decisions are affected by discrimination.

The original dataset is shown, along with the best-fit model $f$, in Figure
1(a). Note that under $f$, the proposed salary for a new employee $\mathbf{x}$
is $$73,000$. But an alternate possibility of the ‘ground-truth,’ debiased
dataset is shown in Figure 1(b). In the world that produced this dataset,
perhaps there is no gender discrimination, so, ideally, we would learn from
this dataset and yield model $g$, which places $\mathbf{x}$’s salary at
$$78,000$.

Figure 1: Salary prediction: (a) Training dataset and resultant model $f$. The
prediction for the test sample $\mathbf{x}$ is $$73,000$. (b) Training dataset
with two label modifications (in red) along with the newly-learned model
($g$). The prediction for the test sample $\mathbf{x}$ is now about $$78,000$.
(c) $H$ contains the set of models $h$ that we could have obtained based on
various small modifications to the provided dataset. We see that
$\mathbf{x}$’s prediction can be anywhere between $$68,000$ and $$83,000$
(blue dotted line).

The modified dataset in Figure 1(b) is just one example of how different data
collection practices — in this case, collecting data from an alternate
universe where there is no gender-based discrimination in salaries — can lead
to various datasets that produce models that make conflicting predictions for
individual test samples.

But what if we could consider the entire range of candidate ‘ground-truth’
datasets? For example, all datasets where each woman’s salary may be increased
by up to $$10,000$ to account for the impacts of potential gender
discrimination. Figure 1(c) shows what we could hypothetically do if that set
of datasets were available — and we had unlimited computing power. Rather than
outputting a single model, we bound the range of models (the highlighted
region) obtainable from alternate-universe training datasets. We could then
use this set of models to obtain a confidence interval for $\mathbf{x}$’s
prediction - in this case, $$68,000$-$$83,000$. This range corresponds to the
_dataset multiplicity robustness_ of $\mathbf{x}$, that is, the sensitivity of
the model’s prediction on $\mathbf{x}$ given specific types of changes in the
training dataset.

Work in algorithmic stability, robust statistics, and distributional
robustness has attempted to quantify how varying the training data impacts
downstream predictions. However, as illustrated by the example, we aim to find
the _pointwise_ impact of uncertainty in training data rather than studying
robustness purely in aggregate, and we want our analysis to encompass the
_worst-case_ (i.e., adversarial) reasonable alternate models, unlike the
purely statistical approaches.

#### Our vision for dataset multiplicity in machine learning

The proposed solution in the above example suffers from a number of drawbacks.
First, is the solution solving the right problem? That is, is dataset
multiplicity a better choice for reasoning about unreliable data than existing
learning theory techniques? Second, how do we define what is a reasonable
alternate-universe dataset to include in the set of datasets? Third, even if
we had a set of datasets encompassing all alternate universes, how would we
compute the graph in Figure 1(c)? And finally, what are the implications for
fair and trustworthy machine learning? How can, and should, we incorporate
dataset multiplicity into machine learning research, development and
deployment?

We address all of these concerns in this paper through the following
contributions:

Conceptual Contribution 1

We formally define the dataset multiplicity problem and give several example
use cases to provide intuition of how to define the set of reasonable
alternate-universe datasets (Section 2)

Theoretical Contribution

We present a novel technique that, for linear models with label errors, can
exactly characterize the range of a test sample’s prediction. We also show how
to over-approximate the range of models (i.e., Figure 1(c)) (Section 3)

Experimental Contribution

We use our approaches to evaluate the effects of dataset multiplicity on real-
world datasets with a particular eye towards how demographic subgroups are
differently affected (Section 4)

Conceptual Contribution 2

We explore the implications of dataset multiplicity (Section 5)

##  2 The Dataset Multiplicity Problem

We formalize _dataset multiplicity_ as a technique that conceptualizes
uncertainty and societal bias in training datasets and discuss how to use
dataset multiplicity as a tool to critically assess machine learning models’
outputs.

We assume the following supervised machine learning setup: we start with a
fixed, deterministic learning algorithm $A$ and a training dataset
$D=(\mathbf{X},\mathbf{y})$ with features $\mathbf{X}\in\mathbb{R}^{n\times
d}$ and outputs $\mathbf{y}\in\mathbb{R}^{n}$.111 $A$ is inclusive of all
modeling steps including preprocessing the training data, selecting the model
hyperparameters through a holdout validation set (segmented off from $D$),
etc.  We run $A$ on $D$ to get a model $f$, that is, $f=A(D)$. Given a test
sample $\mathbf{x}$, we obtain an associated prediction
$\hat{y}=f(\mathbf{x})$.

###  2.1 Defining Dataset Multiplicity

We describe dataset multiplicity for a dataset $D$ with a _dataset
multiplicity model_ $\mathcal{M}(D)$. Intuitively, we want $\mathcal{M}(D)$ to
be the smallest set that contains all conceivable alternatives to $D$. We
present a few examples of $\mathcal{M}$:

####  $\mathcal{M}$ under societally-biased labels

We continue the example from the introduction. Suppose we believe that women
in a dataset are underpaid by up to $$10,000$ each. In this case, we define
$\mathcal{M}(D)$ as the set of all datasets $D^{\prime}$ with identical
features to $D$, such that all labels for men in $D^{\prime}$ are identical to
the labels in $D$ and all labels for women in $D^{\prime}$ are the same as in
$D$, or increased by up to $\$$10,000$$.

####  $\mathcal{M}$ under noisy measurement

Suppose a dataset contains a weight feature and where data was collected using
a tool whose measurements may be inaccurate by up to 5 grams. If weight is the
$k^{\textrm{th}}$ feature, then we can represent $\mathcal{M}(D)$ as the set
of all datasets $D^{\prime}$ that are identical to $D$ except that feature $k$
may differ by up to 5 grams.

####  $\mathcal{M}$ given unreliable feature data

People commonly misreport their height on dating profiles [61]: men add
0.5"($\pm 0.88$) to their height, on average, while women add 0.17"($\pm
0.98$). So, for a given man with reported height $h$ we can be 95% confident
that his height is in $[h-1.26,h+2.26]$ and for a women with height $h$,
$[h-1.79,h+2.13]$. If a dataset contains height (as self-reported via dating
apps) in position $i$, then $\mathcal{M}(D)$ will contain all datasets
$D^{\prime}$ that are equivalent to $D$, except that each sample’s
$i^{\textrm{th}}$ feature may be modified according to the gender-specific 95%
confidence intervals.

####  $\mathcal{M}$ with missing data

Getting a representative population sample can be a challenge for many data
collection tasks. Suppose we suspect that a dataset underrepresents a specific
minority population by up to $20$ samples. If the undersampled group has
feature $i=k$, then $\mathcal{M}(D)$ will be the set of datasets $D^{\prime}$
such that $D\subseteq D^{\prime}$, there are at most 20 additional samples in
$D^{\prime}$, and all new samples have feature $i=k$. (We additionally assume
that all new samples are in the proper feature space, i.e., that they are
valid data samples.)

###  2.2 Learning with Dataset Multiplicity

We define $A(\mathcal{M}(D))$ to be the set of all models obtainable by
training with some dataset in $\mathcal{M}(D)$, i.e.,
$A(\mathcal{M}(D))=\\{f\mid\exists D^{\prime}\in\mathcal{M}(D)\text{ s.t.
}A(D^{\prime})=f\\}$. Given this set of models, we can inquire about the range
of possible predictions for a test sample $\mathbf{x}$. In particular, we can
ask whether $\mathbf{x}$ is _robust_ to dataset multiplicity, that is, will it
receive a different prediction if we started with any other model in
$\mathcal{M}(D)$? Formally, we say that a deterministic algorithm $A$, a
dataset $D$, and a dataset multiplicity model $\mathcal{M}(D)$ are
$\epsilon$-robust to dataset multiplicity on a sample $\mathbf{x}$ if Equation
1 holds. (Equivalently, we will say that $\mathbf{x}$ is $\epsilon$-robust.)

$D^{\prime}\in\mathcal{M}(D)\implies
A(D^{\prime})(x)\in[A(D)(x)-\epsilon,A(D)(x)+\epsilon]$ (1)

######  Example 2.1.

Returning to the example from the introduction, the test sample $\mathbf{x}$
originally receives a prediction of $\$$78,000$$ (Figure 1a). Figure 1c shows
that $\mathbf{x}$ is _not_ $\epsilon$-robust for $\epsilon=\$$5,000$$, since
it can receive any prediction in $[$68,000$,\ $83,000$]$, and
$$78,000$-$68,000$>$5,000$$. However, $\mathbf{x}$ is $\epsilon$-robust for
$\epsilon=$10,000$$.

If a sample $\mathbf{x}$ is $\epsilon$-robust, then we can be certain that its
prediction will not change by more than $\epsilon$ due to dataset
multiplicity. In practice, this may mean we can deploy the prediction with
greater confidence, or less oversight. Conversely, if $\mathbf{x}$ is not
$\epsilon$-robust, then this means there is some plausible alternate training
dataset that, when used to train a model, would result in a different
prediction for $\mathbf{x}$. In this case, the prediction on $\mathbf{x}$ may
be less trustworthy — we discuss options for dealing with non-robustness in
Section 5.

###  2.3 Choosing a Dataset Multiplicity Model

We have discussed how to formalize $\mathcal{M}(D)$ given various conceptions
of dataset inaccuracy; however, we have not discussed how to determine in what
ways a given dataset may be inaccurate. In practice, these judgments should be
made in collaboration with domain experts, both within the data science and
social science realms. Still, there is no one normative, ‘right’ answer of how
to define $\mathcal{M}$ for a given situation — any judgment will be
normative. Furthermore, there may be multiple ways to describe the same social
phenomenon, as illustrated by the following example:

######  Example 2.2.

The first example in Section 2.1 formalizes gender discrimination in salaries.
When index 0 is gender and value 1 is woman, we define $\mathcal{M}$ as
$\mathcal{M}(D)=\\{(\mathbf{X},\mathbf{y}^{\prime})\mid(\mathbf{X}_{i})_{0}=1\implies
y^{\prime}_{i}\in[y_{i},y_{i}+$10,000$]\textrm{ and }(\mathbf{X}_{i})_{0}\neq
1\implies y_{i}=y^{\prime}_{i}\\}$. However, what if we frame the problem as
men are overpaid, rather than women are underpaid? In that case, a more
appropriate formalization would be
$\mathcal{M}(D)=\\{(\mathbf{X},\mathbf{y}^{\prime})\mid(\mathbf{X}_{i})_{0}=0\implies
y^{\prime}_{i}\in[y_{i}-$10,000$,y_{i}]\textrm{ and }(\mathbf{X}_{i})_{0}\neq
0\implies y_{i}=y^{\prime}_{i}\\}$.

As we will see in Section 4.2, this variability in framing can affect the
conclusions we draw about dataset multiplicity’s impacts, highlighting the
need for thoughtful reflection and interdisciplinary collaboration when
choosing $\mathcal{M}$.

##  3 The Dataset Multiplicity Problem for Linear Models with Label Errors

We consider a special case of the dataset multiplicity problem introduced in
Section 2, namely, linear models given noise or errors in the training data’s
labels. (We use the term ‘label’ in the context of both linear regression and
classification.) We present this analysis to begin to characterize the impact
of dataset multiplicity on real-world datasets and models, and to provide an
example for how we envision the study of dataset multiplicity’s impacts to
continue in future work.

We focus on linear models with label errors for a few reasons. First, linear
models are well-studied and used in practice, especially with tabular data,
which is common in areas with societal implications. Furthermore, complicated
models like neural nets can often be conceived of as encoders followed by a
final linear layer, making our results more widely applicable. Second, label
errors and noise are common, well-documented realities in many applications
[39]. Finally, as we will see, the closed-form solution for linear regression
allows us to solve this problem exactly, a challenge that is currently
impractical even for other simple, widely-studied model families like decision
trees [35].

###  3.1 Formulating the Dataset Label Multiplicity Problem

We assume our dataset is of the form $D=(\mathbf{X},\mathbf{y})$ with feature
matrix $\mathbf{X}\in\mathbb{R}^{n\times d}$ and output vector
$\mathbf{y}\in\mathbb{R}^{n}$. (Even though $\mathbf{y}$ is continuous, we
borrow terminology from classification to also refer to $y_{i}$ as the _label_
for $\mathbf{X}_{i}$.) At times, we will reference the interval domain,
$\mathbb{\mathbb{IR}}$, that is, $\mathbb{\mathbb{IR}}=\\{[a,b]\mid
a,b\in\mathbb{R},a\leq b\\}$.

#### Parameterizing $\mathcal{M}$ given label perturbations

We parameterize $\mathcal{M}$ given label noise with three parameters, $k$,
$\Delta$, and $\phi$. First, $k\in\mathbb{N}$ is an upper bound on the number
of training samples that have an inaccurate label. Second,
$\Delta\in\mathbb{\mathbb{IR}}^{n}$ stores the amount that each label can
change. The $i^{\textrm{th}}$ element of $\Delta$ is
$[\delta_{i}^{l},\delta_{i}^{u}]$, signifying that the true value of $y_{i}$
falls in the interval $[y_{i}+\delta_{i}^{l},y_{i}+\delta_{i}^{u}]$. Finally,
$\phi$ is predicate over the feature space specifying whether we can modify a
given sample when, for example, label errors are limited to a population
subgroup. Given $k$, $\Delta$, and $\phi$ we define $\mathcal{M}$ as

$\mathcal{M}_{k,\Delta,\phi}((\mathbf{X},\mathbf{y}))=\\{(\mathbf{X},\mathbf{y}^{\prime})\mid\|\mathbb{1}[\mathbf{y}\neq\mathbf{y}^{\prime}]\|_{1}\leq
k\land\forall i.y_{i}\neq
y_{i}^{\prime}\implies\phi(\mathbf{x}_{i})\land\forall
i.y_{i}^{\prime}-y_{i}\in\delta_{i}\\}$

We describe $k$, $\Delta$, and $\phi$ for the following examples:

######  Example 3.1.

We assume that women in a salary dataset are underpaid by up to $\$$10,000$$
each. Since we place no limit on how many labels may be incorrect — beyond the
proportion of women in the dataset — we set $k=n$, the total number of
samples. Since labels may be underreported by up to $\$$10,000$$, we set
$\Delta=[0,$10,000$]^{n}$. And finally, since $\mathbf{x}_{0}=1$ means that
$\mathbf{x}$ is a woman, we define
$\phi(\mathbf{x})=\mathbb{1}[\mathbf{x}_{0}=1]$ since we assume that only
women’s salaries may change.

######  Example 3.2.

(Spam filter) Suppose a dataset $D=(\mathbf{X},\mathbf{y})$ contains emails
$\mathbf{X}$ that are labeled as not spam or spam (i.e.,
$\mathbf{y}\in\\{-1,1\\}^{n}$). From manual inspection of a small portion of
the dataset, we estimate that up to 2% of the emails are mislabeled. Since up
to $2\%$ of the labels may be incorrect, we set $k=0.02n$. As the labels are
binary, we can modify each label by $+/-2$, depending on its original
label.222The linearity of the algorithm ensures that all labels will remain
valid, i.e., either -1 or 1. Thus, $\Delta=[a,b]^{n}$ where $[a,b]_{i}=[0,2]$
when $y_{i}=-1$ and $[a,b]_{i}=[-2,0]$ when $y_{i}=1$. Finally,
$\phi(\mathbf{x})=1$ since there are no limitations on which samples have
inaccurate labels.

###  3.2 Linear Regression Overview

Our goal is to find the optimal linear regression parameter $\theta$, i.e.,

$\theta=\operatorname*{argmin}_{\theta\in\mathbb{R}^{d}}(\theta^{T}\mathbf{X}-\mathbf{y})^{2}$
(2)

Least-squares regression admits a closed-form solution333In practice, we
implement ridge regression, $\theta=(\mathbf{X}^{T}\mathbf{X}-\lambda
I)^{-1}\mathbf{X}^{T}\mathbf{y}$, for greater stability.

$\theta=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{y}$ (3)

for which we will analyze dataset label multiplicity. We work with the closed-
form solution, instead of a gradient-based one, as it is deterministic and
holistically considers the whole dataset, allowing us to exactly measure
dataset multiplicity by exploiting linearity (Rosenfeld et al. make an
analogous observation [47]). On medium-sized datasets and modern machines,
computing this closed-form solution is efficient.

Given a solution, $\theta$, to Equation 2, we output the prediction
$\hat{y}=\theta^{\top}\mathbf{x}$ for a test point $\mathbf{x}$.

#### Extension to binary classification

Given a binary output vector $\mathbf{y}\in\\{-1,1\\}^{n}$, we find $\theta$
in the same way, but when making test-time predictions, use 0 as a cutoff
between the two classes, i.e., given parameter vector $\theta$ and test sample
$\mathbf{x}$, we return $1$ if $\theta^{T}\mathbf{x}>0$ and $-1$ otherwise. To
evaluate robustness for binary classification, we care about whether the
predicted label can change when training with any dataset
$D^{\prime}\in\mathcal{M}(D)$. Thus, if $\theta^{T}\mathbf{x}\geq 0$, then
$\mathbf{x}$ is dataset multiplicity robust if there is no model
$\theta^{\prime}$ such that $(\theta^{\prime})^{T}\mathbf{x}<0$ (and vice-
versa when $\theta^{T}\mathbf{x}<0$).

###  3.3 Exact Pointwise Solution

Given a model $\theta$ and test sample $\mathbf{x}$ we can expand and
rearrange $\theta^{\top}\mathbf{x}$ as follows:

$\hat{y}=\theta^{\top}\mathbf{x}=((\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{y})^{\top}\mathbf{x}=\underbrace{(\mathbf{x}^{\top}(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top})}_{\mathbf{z}}\mathbf{y}$

This form is useful since it isolates $\mathbf{y}$, which under our dataset
multiplicity assumption contains all of the dataset’s uncertainty. We will use
$\mathbf{z}$ to denote
$\mathbf{x}^{\top}(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}$. Thus,
our goal is to find

$(\\_\ ,\mathbf{y}^{\prime})=\operatorname*{argmax}_{(\\_\
,\tilde{\mathbf{y}})\in\mathcal{M}_{k,\Delta,\phi}(D)}|\mathbf{z}\tilde{\mathbf{y}}-\mathbf{z}\mathbf{y}|$
(4)

and then to check whether
$\|\hat{y}-\mathbf{z}\mathbf{y}^{\prime}\|<\epsilon$. If so, then we will have
proved that the prediction for $\mathbf{x}$ is $\epsilon$-robust under
$\mathcal{M}_{k,\Delta,\phi}(D)$. (Conversely, if
$\|\hat{y}-\mathbf{z}\mathbf{y}^{\prime}\|\geq\epsilon$, then
$\mathbf{y}^{\prime}$ is a counterexample proving that $\mathbf{x}$ is not
$\epsilon$-robust under $\mathcal{M}_{k,\Delta,\phi}(D)$.)

#### Solving for Equation 4

One option is to formulate Equation 4 as a mixed-integer linear program.
However, due to the vast number of possible label perturbation combinations,
this approach is prohibitively slow (we provide a runtime comparison with our
approach in Appendix B). Instead, we use the algorithmic technique presented
in Algorithm 1. Intuitively, one iteration of the algorithm’s inner loop
identifies what output $y_{i}\in\mathbf{y}$ to modify so that we maximally
increase $\mathbf{z}\mathbf{y}$. After $k$ output modifications — or once all
outputs eligible for modification under $\phi$ have been modified — we check
whether the new prediction, $\hat{y}^{\prime}$, has
$\hat{y}^{\prime}>\theta^{T}\mathbf{x}+\epsilon$. If this is the case, we stop
because we have shown that $\mathbf{x}$ is not $\epsilon$-dataset multiplicity
robust. Otherwise, we repeat a variation of the algorithm (see the appendix)
to maximally decrease $\mathbf{z}\mathbf{y}$ and check whether we can achieve
$\hat{y}^{\prime}<\theta^{T}\mathbf{x}-\epsilon$.

Algorithm 1 Find the allowable perturbation that makes $\hat{y}$ as large as
possible, i.e.,
$\max_{(\mathbf{X},\tilde{\mathbf{y}})\in\mathcal{M}_{k,\Delta,\phi}((\mathbf{X},\mathbf{y}))}\mathbf{z}\tilde{\mathbf{y}}$

$\mathbf{z}\in\mathbb{R}^{n},(\mathbf{X},\mathbf{y})\in(\mathbb{R}^{n\times
d},\mathbb{R}^{n}),\Delta\in\mathbb{IR}^{n}$ with $0\in\Delta$, $k\geq 0$,
$\phi:\mathbb{R}^{d}\rightarrow\\{0,1\\}$

$\mathbf{y}^{u}\leftarrow\mathbf{y}$

if $z_{i}\geq 0$ then $\rho^{+}_{i}\leftarrow z_{i}\delta_{i}^{u}\ $ else
$\rho^{+}_{i}\leftarrow z_{i}\delta_{i}^{l}\ $

if not $\phi(\mathbf{x}_{i})$ then $\rho^{+}_{i}\leftarrow 0$

Let $\rho^{+}_{i_{1}},\ldots,\rho^{+}_{i_{l}}$ be the $l$ largest elements of
$\rho^{+}$ by absolute value

for each $\rho^{+}_{i_{j}}$ do

if $z_{i_{j}}\geq 0$ then
${y^{u}_{i_{j}}}\leftarrow{y^{u}_{i_{j}}}+\delta_{i_{j}}^{u}$ else
${y^{u}_{i_{j}}}\leftarrow{y^{u}_{i_{j}}}+\delta_{i_{j}}^{l}$

return $\mathbf{z}\mathbf{y}^{u}$

#### Extension to binary classification

The binary classification version of the algorithm works identically, except
we check whether $\hat{y}$ rounds to a different class than
$\theta^{T}\mathbf{x}$ to ascertain $\mathbf{x}$’s robustness.

###  3.4 Over-Approximate Global Solution

In Section 3.3, we described a procedure to find the exact dataset
multiplicity range for a test point $\mathbf{x}$. For every input $\mathbf{x}$
for which we want to know the dataset multiplicity, the procedure effectively
relearns the worst-case linear regression model for $\mathbf{x}$. In practice,
we may want to explore the dataset multiplicity of a large number of samples,
e.g., a whole test dataset, or we may need to perform online analysis.

We would like to understand the dataset multiplicity range for a large number
of test points without performing linear regression for every input. We
formalize capturing all linear regression models we may obtain as follows:

$\Theta=\\{\theta\mid\theta=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\tilde{\mathbf{y}}\textrm{
for some }(\mathbf{X},\tilde{\mathbf{y}})\in\mathcal{M}_{k,\Delta,\phi}(D)\\}$

To see whether $\mathbf{x}$ is $\epsilon$-robust, we check whether
$\tilde{\theta}^{\top}\mathbf{x}\in[\theta^{\top}\mathbf{x}-\epsilon,\theta^{\top}\mathbf{x}+\epsilon]$
for all $\tilde{\theta}\in\Theta$. For ease of notation, let
$\mathbf{C}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}$. Note that
$\mathbf{C}\in\mathbb{R}^{m\times n}$, while $\mathbf{z}\in\mathbb{R}^{1\times
n}$.

#### Challenges

The set of weights $\Theta$ is not enumerable and is non-convex (proof in
appendix A). Our goal is to represent $\Theta$ efficiently so that we can
simultaneously apply all weights $\theta\in\Theta$ to a point $\mathbf{x}$.
Our key observation is that we can easily compute a hyperrectangular over-
approximation of $\Theta$. In other words, we want to compute a set
$\Theta^{a}$ such that $\Theta\subseteq\Theta^{a}$. Note that the set
$\Theta^{a}$ is an interval vector in $\mathbb{\mathbb{IR}}^{n}$, since
interval vectors represent hyperrectangles in Euclidean space.

This approach results in an overapproximation of the true dataset multiplicity
range for a test sample $\mathbf{x}$ — that is, some values in the range may
not be attainable via any allowable training label modification.

#### Approximation approach

We will iteratively compute components of the vector $\Theta^{a}$ by finding
each coordinate $i$ as the following interval, where $\mathbf{c}_{i}$ are the
column vectors of $\mathbf{C}$:

$\Theta^{a}_{i}=\left[\min_{(\mathbf{X},\mathbf{y}^{\prime})\in\mathcal{M}_{k,\Delta,\phi}(D)}\mathbf{c}_{i}\mathbf{y}^{\prime},\max_{(\mathbf{X},\mathbf{y}^{\prime})\in\mathcal{M}_{k,\Delta,\phi}(D)}\mathbf{c}_{i}\mathbf{y}^{\prime}\right]$

To find
$\min_{\mathbf{y}^{\prime}\in\mathcal{M}_{k,\Delta}(\mathbf{y})}\mathbf{c}_{i}\mathbf{y}^{\prime}$,
we use the same process as in Section 3.3. Specifically, we use Algorithm 1 to
compute the lower and upper bounds of each $\Theta^{a}_{i}$. We show in the
appendix that the interval matrix $\Theta^{a}$ is the tightest possible
hyperrectangular overapproximation of the set $\theta$.

#### Evaluating the impact of dataset multiplicity on predictions

Given $\Theta^{a}$ as described above, the output for an input $\mathbf{x}$ is
provably robust to dataset multiplicity if

$\displaystyle(\Theta^{a})^{\top}\mathbf{x}\subseteq[\theta^{\top}\mathbf{x}-\epsilon,\theta^{\top}\mathbf{x}+\epsilon]$
(5)

Note that $(\Theta^{a})^{\top}\mathbf{x}$ is computed using standard interval
arithmetic, e.g., $[a,b]+[a^{\prime},b^{\prime}]=[a+a^{\prime},b+b^{\prime}]$.
Also note that the above is a one-sided check: we can only say that the
model’s output given $\mathbf{x}$ is robust to dataset multiplicity, but
because $\Theta^{a}$ is an overapproximation, if Equation 5 does not hold, we
cannot conclusively say that the model’s prediction on $\mathbf{x}$ is subject
to dataset multiplicity.

##  4 Empirical Evaluation

We use Python to implement the algorithms from Sections 3.3 and 3.4 for
measuring label-error multiplicity in linear models.444Our code is available
at https://github.com/annapmeyer/linear-bias-certification. To speed up the
evaluation, we use a high-throughput computing cluster. (We request 8GB memory
and 8GB disk, but all experiments are feasible to run on a standard laptop.)
This approach does not have a direct baseline with which to compare, as ours
is the first work to propose and analyze the dataset-multiplicity problem.

#### Datasets and tasks

We analyze our approach on three datasets: the Income prediction task from the
FolkTables project [20], the Loan Application Register (LAR) from the Home
Mortgage Disclosure Act publication materials [22], and MNIST 1/7 (i.e., the
MNIST dataset limited to 1’s and 7’s) [32]. We divide each dataset into train
(80%), test (10%), and validation (10%) datasets and repeat all experiments
across 10 folds, except when a standard train/test split is provided, as with
MNIST. We perform classification on the Income dataset (whether or not an
individual earned over $$50,000$), on LAR (whether or not a home mortgage loan
was approved), and on MNIST (binary classification limited to 1’s and 7’s).
Additionally, in the appendix we evaluate the regression version of Income by
predicting an individual’s exact income. For all of the Income experiments, we
limit the dataset to only include data from a single U.S. state to speed
computations. In Sections 4.1 and 4.3 we present results from a single state,
Wisconsin, while in Section 4.2 we compare results across five different US
states.

#### Accuracy-Robustness Tradeoff

There is a tradeoff between accuracy and robustness to dataset multiplicity
that is controlled by the regularization parameter $\lambda$ in the ridge
regression formula $\theta=(\mathbf{X}^{\top}\mathbf{X}-\lambda
I)^{-1}\mathbf{X}^{\top}\mathbf{y}$. Larger values of $\lambda$ improve
robustness at the expense of accuracy. Figure 2 illustrates this tradeoff. All
results below, unless otherwise stated, use a value of $\lambda$ that
maximizes accuracy.

Figure 2: Fraction of test samples whose predictions are robust to dataset
multiplicity for different accuracy/robustness trade-offs as controlled by the
ridge regression parameter $\lambda$. The different lines within each graph
plot robustness for different accuracy/robustness trade-offs. The line labeled
0.0 corresponds to the value of $\lambda$ that achieves maximal accuracy, the
line labeled 0.2 corresponds to the value of $\lambda$ that sacrifices a 0.2
percentage-point drop in accuracy for more robustness, etc. We include the
specific accuracy values in the appendix. The datasets for each graph are (a)
LAR, (b) Income, and (c) MNIST 1/7.

#### Experiment goals

Our core objective is to see how robust linear models are to dataset label
multiplicity. We measure this sensitivity with the _robustness rate_ , that
is, the fraction of test points that receive invariant predictions (within a
radius of $\epsilon$) given a certain level of label inaccuracies. The
robustness rate is a proxy for the stability of a modeling process under
dataset multiplicity, so knowing this rate — and comparing it across various
datasets, demographic groups, and algorithms — can help ML practitioners
analyze the trustworthiness of their models’ outputs. In Section 4.1, we
describe the overall robustness results for each dataset. Then, in Section
4.2, we perform a stratified analysis across demographic groups and show how
varying the dataset multiplicity model definition can significantly change
data’s vulnerability to dataset multiplicity. Finally, in Section 4.3, we
discuss results of the over-approximate approach and how it can be used to
evaluate dataset multiplicity robustness.

###  4.1 Robustness to Dataset Multiplicity

Key insights: When a small percentage (e.g., 1%) of labels are incorrect, a
significant minority of test samples are not robust to dataset multiplicity,
raising questions about the reliability of the models’ predictions.

Table 1 shows the fraction of test points that are dataset multiplicity robust
for classification datasets at various levels of label inaccuracies. For each
dataset, the robustness rates are relatively high ($>80\%$) when fewer than
0.25% of the labels can be modified, and stay above 50% for 1% label error.

Table 1: Robustness rates (percentage of test dataset whose predicted label cannot change under dataset label multiplicity) for classification datasets given different rates of inaccurate labels. Dataset | Inaccurate labels as a percentage of training dataset size
---|---
0.1% | 0.25% | 0.5% | 0.75% | 1.0% | 1.5% | 2.0% | 3.0% | 4.0% | 5.0% | 6.0%
LAR | 93.9 | 88.1 | 79.4 | 69.2 | 61.3 | 45.9 | 33.7 | 16.2 | 5.2 | 0.4 | 0.0
Income | 91.1 | 81.4 | 67.8 | 58.4 | 50.7 | 37.2 | 23.3 | 12.1 | 4.8 | 1.7 | 0.7
MNIST 1/7 | 98.3 | 96.3 | 93.1 | 88.3 | 84.4 | 73.1 | 60.8 | 38.8 | 23.3 | 13.1 | 7.0

Despite globally high robustness rates, we must also consider the non-robust
data points. In particular, we want to emphasize that for Income and LAR, each
non-robust point represents an individual whose classification hinges on the
labels of only a small number of training samples. That is, given the assumed
uncertainty about the labels’ accuracy, it is plausible that a ‘clean’ dataset
would output different test-time predictions for these samples. Some data
points will almost surely fall into this category — if not, that would mean
the model was independent from the training data, which is not our goal!
However, if a sample is not robust to a small number of label modifications,
perhaps the model should not be deployed on that sample. Instead, if the
domain is high-impact, the sample could be evaluated by a human or auxiliary
model (see Section 5 for more discussions on how to handle non-robust test
samples).

Returning to Table 1, many data points are not robust at low label error
rates, e.g., when 1% of labels may be wrong, 49.3% of Income test samples are
not robust. Likewise, $38.7\%$ of LAR test samples can receive the opposite
classification if the correct subset of 1% of labels change. These low
robustness rates call into question the advisability of using linear
classifiers on these datasets unless one is confident that label accuracy is
very high.

###  4.2 Disparate Impacts of Dataset Multiplicity

In Section 4.1, we showed dataset multiplicity robustness results given the
assumption that all labels in the training dataset were potentially
inaccurate. However, in practice, label errors may be systemic. In particular,
two of the datasets we analyzed in Section 4.1 contain data that may display
racial or gender bias. We hypothesize that the Income dataset likely reflects
trends where women and people of color are underpaid relative to white men in
the United States, and that the LAR dataset may similarly reflect racial and
gender biases on the part of mortgage lending decision makers. To leverage
this refined understanding of potential inaccuracies in the labels, in this
section we evaluate test data robustness under the following two _targeted_
dataset multiplicity paradigms:

  * •

_‘Promoting’ the disadvantaged group_ : We restrict label modification to
members of the disadvantaged group (i.e., Black people or women); furthermore,
we only change labels from the negative class to the positive class.

  * •

_‘Demoting’ the advantaged group_ : We restrict label modification to the
advantaged group (i.e., White people or men); furthermore, we only allow
change labels from the positive class to the negative class. This setup is
compatible with the worldview (for example) that men are overpaid.

Before delving into the results, we want to acknowledge that this analysis has
a few shortcomings. First, for simplicity we use binary gender (male/female)
and racial (White/Black) breakdowns. Clearly, this dichotomy fails to capture
complexities in both gender and racial identification and perceptions. Second,
the targeted dataset multiplicity models that we use also over-simplify both
how discrimination manifests and how it can interact with other identities not
captured by the data. Finally, we are not social scientists or domain experts
and it is possible that the folk wisdom we rely on to propose data biases does
not fully capture the patterns in the world. Rather, readers should treat this
section as an analysis of ‘toy phenomena’ meant to illustrate how our
technique can be used for real-world tasks.

#### Basic results

First, we present the overall dataset multiplicity robustness rates for the
various multiplicity definitions.

Key insights: Limiting label errors to a subset of the training dataset (i.e.,
refining $\mathcal{M}$) yields higher dataset multiplicity robustness rates.
However, the exact choice of $\mathcal{M}$ is significant.

Figure 3 shows that in all cases the targeted multiplicity definition yields
significantly higher overall robustness rates than a broad multiplicity
definition does. Notably, limiting all label perturbations to one racial group
for Income greatly affects robustness: using the original multiplicity
definition (no targeting), no test samples are robust when 12% of labels can
be modified. However, when limiting label errors to Black people with the
negative label, the robustness rate remains over 95% — it turns out this is
not surprising, since fewer than 2% of the data points have race=Black.
However, more than 80% of samples have race=White, and limiting label changes
to White people with the positive label still yields over 60% robustness when
12% of labels can be changed. Similarly, using targeted dataset multiplicity
definitions for LAR can increase overall robustness by up to 30 percentage
points.

Figure 3: Dataset multiplicity robustness rates for (a) Income stratified by
race, (b) Income stratified by gender, (c) LAR stratified by race, (d) LAR
stratified by gender. “No targeting” means that we place no restrictions on
which labels can be modified. “Target on group 1” indicates that we can modify
labels for group 1 (the minority/disadvantaged group) from the negative to
positive class, while “target on group 2” indicates that we can modify labels
for group 2 (the majority/advantaged group) from the positive to the negative
class. For the race plots, Group 1 is Black people and Group 2 is White
people. For the gender plots, Group 1 is women and Group 2 is men.

#### Demographic group robustness rates

We also investigate the robustness rates for different demographic groups,
both under the original, untargeted multiplicity assumptions and under the
targeted versions.

Key insights: Different demographic groups do not exhibit the same dataset
multiplicity robustness rates and targeting $\mathcal{M}$ to reflect real-
world uncertainty can exacerbate discrepancies.

Each row of Figure 4 compares baseline (untargeted) robustness rates,
stratified by demographic groups, with targeted versions of $\mathcal{M}$ for
five US states. We observe two trends: first, there are commonly racial and
gender discrepancies (see the pairs of dotted lines). E.g., for all states
except Wisconsin, men consistently have higher baseline robustness rates than
women (sometimes by a margin of over 20%). Second, using various targeted
versions of $\mathcal{M}$ has unequal impacts across demographic groups. The
top row of Figure 4 shows that targeting on race=Black (i.e., allowable label
perturbations can change Black people’s labels from $-1$ to $1$) modestly
improves dataset multiplicity robustness rates for Black people, but massively
improves them for White people. We see similar trends, namely, that the non-
targeted group sees higher robustness rate gains than the targeted group,
across the other versions of $\mathcal{M}$, as well.

Figure 4: Dataset multiplicity robustness rates given targeted label errors
across several states’ Income datasets. Row 1: target on race=Black, flipping
labels to -1 to 1. Row 2: target on race=White, flipping labels from 1 to -1.
Row 3: target on gender=female, flipping labels from -1 to 1. Row 4: target on
gender=male, flipping labels from 1 to -1. For the graphs targeting on race,
Group 1 is Black people and group 2 is White people. For the graphs targeting
on gender, Group 1 is women and Group 2 is men. "Orig" refers to the baseline,
untargeted models.

On LAR, similar results hold. (Graphs and discussion are in the appendix.)

###  4.3 Approximate Approach

Key insights: Using the approximate approach greatly reduces precision in
proving dataset-multiplicity robustness, but still shows promise for
understanding dataset multiplicity’s impact given low levels of label errors.

As expected, the approximate approach from Section 3.4 is less precise than
the exact one. The loss in precision depends highly on the dataset and the
level of label uncertainty, as shown in Figure 5. For Income and MNIST, there
are very large gaps: for example, given 2% label error, 80% of test samples
are robust to dataset multiplicity, but the approximate version cannot prove
robustness for any samples. However, there are some bright points: at 1% label
error, we can still prove robustness for 90% of MNIST-1/7 samples, and over
60% of Income samples. In situations where label error is expected to be
relatively small, the approximate approach can still be useful for gauging the
relative dataset multiplicity robustness of a dataset.

Figure 5: Left to right: Robustness rates (fraction of the test set) for the
exact and approximate techniques on (a) LAR, (b) Income, and (c) MNIST 1/7.
For all examples, $\lambda$ was chosen to obtain results within 2% of the
optimal accuracy. Error bars (for Income and LAR) are the median 50% for
10-fold cross validation.

We also measured the time complexity of each approach. To check the robustness
of $1,000$ Income samples, it takes 37.2 seconds for the exact approach and
6.8 seconds for the approximate approach. For $10,000$ samples, it takes 383.5
seconds and 30.7 seconds, respectively. I.e., the exact approach scales
linearly with the number of samples, but the approximate approach stays within
a single order of magnitude. See appendix for more details and discussion.

##  5 Implications and Ethical Challenges of Dataset Multiplicity

For the conclusions we draw from machine learning to be robust and
generalizable, we need to _understand_ dataset multiplicity, _reduce_ its
impacts on predictions, and _adapt_ machine learning practices to consider
dataset multiplicity.

#### Understanding dataset multiplicity

Adopting standardized data documentation practices will likely aid in
identifying potential inaccuracies or biases in datasets [23, 43]. Further
work surrounding _how_ and _why_ datasets are created with particular
worldviews (e.g., [26, 50]) will assist in identifying blind spots in existing
datasets and help further the push for more robust dataset curation and
documentation. But even if specific shortcomings in data collection are
addressed through better curation and documentation practices, unavoidable
variations in data collection will still contribute to dataset multiplicity
[45], making modeling and model deployment interventions important, too.

#### Reducing the impacts of dataset multiplicity

An advantage of predictive multiplicity (i.e., multiplicity in the model
selection process given a fixed training dataset) is that the wide range of
equally-accurate models allows model developers to choose a model based on
criteria like fairness or robustness without sacrificing predictive accuracy
[6, 67]. Likewise, we know that there exist datasets — typically de-biased or
more representative than a naïvely-collected baseline dataset — that yield
models that are both fair and accurate [11, 21, 64]. If there exists a dataset
in the dataset multiplicity set that yields a fairer (or more robust, more
interpretable, etc.) model, then we should consider whether it is more
appropriate to use that dataset to train the deployed model. (This may or may
not be appropriate, depending on the domain, and is a decision that should be
considered in conjunction with stakeholders.) Another option is to find
learning algorithms or model classes that are inherently more robust to
dataset multiplicity. In the context of ridge regression, we found that using
a larger regularization parameter (see Figure 2) increases dataset-
multiplicity robustness. Ensemble learning is another promising direction, as
it has been shown to decrease predictive multiplicity [5].

#### Adapting ML to handle non-robustness to dataset multiplicity

If a model has low dataset multiplicity robustness in aggregate across a test
dataset, then confidence may be too low to deploy the model because of
procedural fairness concerns [6]. It is also important to consider how
robustness to dataset multiplicity varies across different population
subgroups. As we saw in Section 4.2, different multiplicity definitions can
yield disparate multiplicity-robustness rates across populations. The
approximate approach from Section 3.4 is well-suited to these aggregate
analyses. If we find that dataset multiplicity rates are low (either overall
or for some demographic groups), it may be more appropriate to train with a
different algorithm, refine the training dataset so that multiplicity is
lessened, or avoid machine learning for the task at hand.

Dataset multiplicity robustness should also be considered on an individual
level, as in the exact approach from Section 3.3. If a given dataset and
algorithm are not dataset multiplicity-robust on a test sample $\mathbf{x}$,
options include abstaining on $\mathbf{x}$ or using the most favorable outcome
in its dataset multiplicity range. But in many cases, an algorithm is deployed
to allocate a finite resource — thus, returning the best-case label for all
samples is likely infeasible. Instead, the chosen model is a function of the
arbitrary nature of the provided dataset. Creel and Hellman explain that
arbitrary models are not necessarily cause for concern, however, algorithmic
monoculture becomes a concern when the same arbitrary outcomes are used
widely, thereby broadly excluding otherwise-qualified people from
opportunities [15, 31]. Given machine learning’s reliance on benchmark
datasets, it seems plausible that there is algorithmic monoculture stemming
from the choice of arbitrary training dataset. To avoid algorithmic
monoculture effects in the modeling process, scholars have proposed
randomizing over model selection or outcomes [24, 31] — we suspect that a
similar approach would make sense in the context of dataset multiplicity.

##  6 Related Work

Dataset multiplicity robustness can be used either to _certify_ (i.e., prove)
that individual predictions are stable given uncertainty in the training data,
or to characterize the overall stability of a model. Other approaches in the
realms of adversarial ML, uncertainty quantification, and learning theory aim
to answer similar questions.

#### Comparison with other sources of multiplicity

Predictive multiplicity and underspecification show that there are often many
models that fit a given dataset equally well [9, 16, 33, 60]. Because of this
multiplicity, models can often be selected to simultaneously achieve accuracy
and also fairness, robustness, or other desirable model-level properties [6,
14, 51, 60, 67]. The extent of predictive multiplicity can be lessened by
constructing more sophisticated models (e.g., [48]), however, this type of
intervention only reduces algorithmic multiplicity and, furthermore, does not
address the underlying procedural fairness concern that individuals can
justifiably receive different decisions. Multiplicity also arises when
modifying training parameters like random seed, data ordering, and
hyperparameters [8, 13, 34, 54, 56], but most of the works on this topic focus
on either attack vulnerability or the reproducibility and generalizability of
the training process. In a notable exception, Bell et al. explore the
‘multiverse’ of models by characterizing what hyperparameter values correspond
with what conclusions [1], but their analysis does not account for uncertainty
in the training dataset, nor does the predictive multiplicity literature.
There is, however, a line of work that aims to increase the fairness of a
model by debiasing or augmenting a dataset [11, 21, 64]. Our dataset
multiplicity framework is more broad than those approaches since we aim to
understand the entire range of feasible datasets and models, rather than
identify a single fair alternative.

#### Other approaches to bounding uncertainty

Approaches from causal inference, uncertainty quantification, and learning
theory aim to measure and reduce uncertainty in machine learning. One major
concern in this realm is the role that researcher decisions can play in
reproducibility [12, 55]. Coker et al. propose ‘hacking intervals’ to capture
the range of outcomes that any realistic researcher could obtain through
different analysis choices or datasets [12]. Our dataset multiplicity
framework can be viewed as extending their prescriptively constrained hacking-
interval concept to allow for arbitrarily-defined changes to the training
dataset. However, their results employ causality to make a stronger case for
defining reasonable dataset modifications. Likewise, partial identification in
economics uses domain knowledge and statistical tools to bound the range of
possible outcomes in a data analysis [59].

The methods described above — ‘hacking intervals’ and partial identification —
are special formulations of uncertainty quantification (UQ), which aims to
understand the range of predictions that a model may output. UQ can occur
either through Bayesian methods that treat model weights as random variables,
or through ensembling or bootstrapping [58]. While UQ shares a common goal
with dataset multiplicity — i.e., understanding the range of outcomes — the
assumptions about where the multiplicity arises are different. UQ typically
assumes that uncertainty stems from either insufficient data or noisy data,
and does not account for the systemic errors that dataset multiplicity can
encompass. Work on selection bias aims to learn in the presence of missing
data, feature, or labels. For example, multiple imputation fills the missing
data in multiple ways and aggregates the results [49, 62], similar to how
dataset multiplicity considers all alternative models. The main difference
between multiple imputation as a selection bias intervention and dataset
multiplicity is that given selection bias, it is easy to identify where the
inaccuracies are, and multiple imputation only considers a small number of
dataset options, rather than all options as dataset multiplicity aims to do.

Within learning theory, distributional robustness studies how to find models
that perform well across a family of distributions [2, 37, 53], robust
statistics shows how algorithms can be adapted to account for outliers or
other errors in the data [19, 18], and various works focus on robustifying
training algorithms to label noise [38, 40, 46]. However, these works all (a)
provide statistical global robustness guarantees, rather than the provable
exact robustness guarantees that we make, (b) try to find a single good
classifier, rather than understand the range of possible outcomes, and (c)
typically require strong assumptions about the data distribution and the types
of noise or errors. Algorithmic stability [9, 17] and sensitivity analysis
[25] aim to quantify how sensitive algorithms are to small perturbations in
the training data. However, they both typically make strict assumptions about
the perturbation’s form, either as a leave-one-out perturbation model in
algorithmic stability [4, 30], or as random noise in sensitivity analysis.

#### Robustness in adversarial ML

Checking robustness to dataset multiplicity has parallels to adversarial
machine learning, especially data poisoning, where an attacker modifies a
small portion of the training dataset to reduce test-time accuracy [3, 52, 68,
66]. Various defenses counteract these attacks [29, 41, 47, 57, 69], including
ones that focus on attacking and defending linear regression models [28, 36].
Some of these works (e.g., [47] for label-flipping) additionally try to
_certify_ robustness. Our exact solution to dataset multiplicity in linear
models with label errors functions as a certificate, since we prove robustness
to all allowable label perturbations, including adversarial ones. Three major
differences from Rosenfeld et al. [47] are that we do not modify the
underlying algorithm to achieve a certificate, the certification process is
deterministic, not probabilistic, and we allow the label perturbations to be
targeted towards a particular subgroup. Meyer et al. use a similar targeted
view on data modifications, but their approach is strictly overapproximate and
is limited to decision trees [35]. Furthermore, our definition of dataset
multiplicity is distinct from the _defense_ papers in that we aim to study
dataset multiplicity robustness of existing algorithms; however, an
interesting direction for future work would be to improve dataset multiplicity
robustness via algorithmic modifications.

##  7 Conclusions

We defined the dataset multiplicity problem, showed how to evaluate the
impacts of dataset multiplicity on linear models in the presence of label
noise, and presented thoughts for how dataset multiplicity should be
considered as part of the machine learning pipeline. Notably, we find that we
can certify robustness to dataset multiplicity for some test samples,
indicating that we can deploy these predictions with confidence. By contrast,
we show that other test samples are not robust to low levels of dataset
multiplicity, meaning that unless labels are very accurate, these test samples
may receive predictions that are artifacts of the random nature of data
collection, rather than real-world patterns.

Future work in the area of dataset multiplicity abounds, and many connections
with other areas are mentioned throughout Sections 5 and 6. The most important
technical direction for future exploration, in our opinion, is extending the
dataset multiplicity framework to probabilistic settings, e.g., by asking what
proportion of reasonable datasets yield a different prediction for a given
test sample. This inquiry is likely to be more fruitful than finding exact
solutions for more complicated model classes, and it may open opportunities to
leverage techniques from areas like distributional robustness or uncertainty
quantification. Making direct connections with areas like causal inference and
partial identification in economics should also be a priority for future work,
as these topics have similar goals and have been studied more broadly. In a
social-science realm, dataset multiplicity could benefit from more work on
what features and labels in a dataset are most likely to be inaccurate or
affected by social biases, since this will allow us to bound dataset
multiplicity more precisely. Similarly, it is difficult to separate out
instances of direct bias (e.g., salary disparities due to gender
discrimination) and indirect bias (e.g., salary disparities due to women
feeling unwelcome in STEM careers), and more research is needed into how that
distinction should affect dataset multiplicity definitions.

## References

  * [1] S. Bell, O. Kampman, J. Dodge, and N. D. Lawrence.  Modeling the Machine Learning Multiverse.  In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [2] A. Ben-Tal, D. den Hertog, A. De Waegenaere, B. Melenberg, and G. Rennen.  Robust Solutions of Optimization Problems Affected by Uncertain Probabilities.  Management Science, 59(2):341–357, 2013.
  * [3] B. Biggio, B. Nelson, and P. Laskov.  Poisoning Attacks against Support Vector Machines.  In Proceedings of the 29th International Conference on Machine Learning, ICML’12, page 1467–1474. Omnipress, 2012.
  * [4] E. Black and M. Fredrikson.  Leave-One-out Unfairness.  In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’21, page 285–295. Association for Computing Machinery, 2021.
  * [5] E. Black, K. Leino, and M. Fredrikson.  Selective Ensembles for Consistent Predictions.  In International Conference on Learning Representations, 2022.
  * [6] E. Black, M. Raghavan, and S. Barocas.  Model Multiplicity: Opportunities, Concerns, and Solutions.  In 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’22, page 850–863, New York, NY, USA, 2022. Association for Computing Machinery.
  * [7] F. D. Blau and L. M. Kahn.  The Gender Wage Gap: Extent, Trends, and Explanations.  Journal of Economic Literature, 55(3):789–865, September 2017.
  * [8] X. Bouthillier, P. Delaunay, M. Bronzi, A. Trofimov, B. Nichyporuk, J. Szeto, N. Mohammadi Sepahvand, E. Raff, K. Madan, V. Voleti, S. Ebrahimi Kahou, V. Michalski, T. Arbel, C. Pal, G. Varoquaux, and P. Vincent.  Accounting for Variance in Machine Learning Benchmarks.  In A. Smola, A. Dimakis, and I. Stoica, editors, Proceedings of Machine Learning and Systems, volume 3, pages 747–769, 2021.
  * [9] L. Breiman.  Heuristics of Instability and Stabilization in Model Selection.  The Annals of Statistics, 24(6):2350 – 2383, 1996.
  * [10] J. Buolamwini and T. Gebru.  Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification.  In S. A. Friedler and C. Wilson, editors, Proceedings of the 1st Conference on Fairness, Accountability and Transparency, volume 81 of Proceedings of Machine Learning Research, pages 77–91. PMLR, 23–24 Feb 2018\.
  * [11] I. Y. Chen, F. D. Johansson, and D. Sontag.  Why is My Classifier Discriminatory?  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 3543–3554, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * [12] B. Coker, C. Rudin, and G. King.  A Theory of Statistical Inference for Ensuring the Robustness of Scientific Results.  Management Science, 67(10):6174–6197, 2021.
  * [13] A. F. Cooper, Y. Lu, J. Forde, and C. M. De Sa.  Hyperparameter Optimization Is Deceiving Us, and How to Stop It.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 3081–3095. Curran Associates, Inc., 2021.
  * [14] A. Coston, A. Rambachan, and A. Chouldechova.  Characterizing Fairness Over the Set of Good Models Under Selective Labels.  In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2144–2155. PMLR, 18–24 Jul 2021.
  * [15] K. Creel and D. Hellman.  The Algorithmic Leviathan: Arbitrariness, Fairness, and Opportunity in Algorithmic Decision-Making Systems.  Canadian Journal of Philosophy, 52(1):26–43, 2022.
  * [16] A. D’Amour, K. Heller, D. Moldovan, B. Adlam, B. Alipanahi, A. Beutel, C. Chen, J. Deaton, J. Eisenstein, M. D. Hoffman, F. Hormozdiari, N. Houlsby, S. Hou, G. Jerfel, A. Karthikesalingam, M. Lucic, Y. Ma, C. McLean, D. Mincu, A. Mitani, A. Montanari, Z. Nado, V. Natarajan, C. Nielson, T. F. Osborne, R. Raman, K. Ramasamy, R. Sayres, J. Schrouff, M. Seneviratne, S. Sequeira, H. Suresh, V. Veitch, M. Vladymyrov, X. Wang, K. Webster, S. Yadlowsky, T. Yun, X. Zhai, and D. Sculley.  Underspecification Presents Challenges for Credibility in Modern Machine Learning, 2020.
  * [17] L. Devroye and T. Wagner.  Distribution-Free Performance Bounds for Potential Function Rules.  IEEE Transactions on Information Theory, 25(5):601–604, 1979.
  * [18] I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart.  Robustness Meets Algorithms.  Commun. ACM, 64(5):107–115, 2021.
  * [19] I. Diakonikolas and D. M. Kane.  Recent Advances in Algorithmic High-Dimensional Robust Statistics, 2019.
  * [20] F. Ding, M. Hardt, J. Miller, and L. Schmidt.  Retiring Adult: New Datasets for Fair Machine Learning.  arXiv preprint arXiv:2108.04884, 2021.
  * [21] S. Dutta, D. Wei, H. Yueksel, P.-Y. Chen, S. Liu, and K. R. Varshney.  Is There a Trade-off between Fairness and Accuracy? A Perspective Using Mismatched Hypothesis Testing.  In Proceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020.
  * [22] Federal Financial Institutions Examination Council.  One Year National Loan-Level Dataset, 2019.  Accessed 5 Jan. 2023.
  * [23] T. Gebru, J. Morgenstern, B. Vecchione, J. W. Vaughan, H. Wallach, H. D. III, and K. Crawford.  Datasheets for Datasets.  Commun. ACM, 64(12):86–92, nov 2021.
  * [24] N. Grgić-Hlača, M. B. Zafar, K. P. Gummadi, and A. Weller.  On Fairness, Diversity and Randomness in Algorithmic Decision Making, 2017.
  * [25] A. S. Hadi and S. Chatterjee.  Sensitivity Analysis in Linear Regression.  John Wiley & Sons, 2009.
  * [26] B. Hutchinson, A. Smart, A. Hanna, E. Denton, C. Greer, O. Kjartansson, P. Barnes, and M. Mitchell.  Towards Accountability for Machine Learning Datasets: Practices from Software Engineering and Infrastructure.  In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’21, page 560–575, New York, NY, USA, 2021. Association for Computing Machinery.
  * [27] A. Z. Jacobs and H. Wallach.  Measurement and Fairness.  In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’21, page 375–385, New York, NY, USA, 2021. Association for Computing Machinery.
  * [28] M. Jagielski, A. Oprea, B. Biggio, C. Liu, C. Nita-Rotaru, and B. Li.  Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning.  In 2018 IEEE Symposium on Security and Privacy (SP), pages 19–35, 2018.
  * [29] J. Jia, X. Cao, and N. Z. Gong.  Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks.  Proceedings of the AAAI Conference on Artificial Intelligence, 35(9):7961–7969, May 2021.
  * [30] M. Kearns and D. Ron.  Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation.  Neural Computation, 11(6):1427–1453, 1999.
  * [31] J. Kleinberg and M. Raghavan.  Algorithmic Monoculture and Social Welfare.  Proceedings of the National Academy of Sciences, 118(22):e2018340118, 2021.
  * [32] Y. LeCun, C. Cortes, and C. J. C. Burges.  The MNIST Database of Handwritten Digits, [n.d.].
  * [33] C. Marx, F. Calmon, and B. Ustun.  Predictive Multiplicity in Classification.  In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 6765–6774. PMLR, 7 2020.
  * [34] J. Mehrer, C. J. Spoerer, N. Kriegeskorte, and T. C. Kietzmann.  Individual Differences among Deep Neural Network Models.  Nature Communications, 11, 2020.
  * [35] A. P. Meyer, A. Albarghouthi, and L. D' Antoni.  Certifying Robustness to Programmable Data Bias in Decision Trees.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 26276–26288. Curran Associates, Inc., 2021.
  * [36] N. Müller, D. Kowatsch, and K. Böttinger.  Data Poisoning Attacks on Regression Learning and Corresponding Defenses.  In 2020 IEEE 25th Pacific Rim International Symposium on Dependable Computing (PRDC), pages 80–89, 2020.
  * [37] H. Namkoong and J. C. Duchi.  Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
  * [38] N. Natarajan, I. S. Dhillon, P. K. Ravikumar, and A. Tewari.  Learning with Noisy Labels.  In C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
  * [39] C. G. Northcutt, A. Athalye, and J. Mueller.  Pervasive Label Errors in Test Sets Destabilize Machine Learning Benchmarks.  In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), 2021.
  * [40] G. Patrini, A. Rozza, A. K. Menon, R. Nock, and L. Qu.  Making Deep Neural Networks Robust to label Noise: A Loss Correction Approach.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2233–2241, 2017.
  * [41] A. Paudice, L. Muñoz-González, and E. C. Lupu.  Label Sanitization Against Label Flipping Poisoning Attacks.  In C. Alzate, A. Monreale, H. Assem, A. Bifet, T. S. Buda, B. Caglayan, B. Drury, E. García-Martín, R. Gavaldà, I. Koprinska, S. Kramer, N. Lavesson, M. Madden, I. Molloy, M.-I. Nicolae, and M. Sinn, editors, ECML PKDD 2018 Workshops, pages 5–15, Cham, 2019\. Springer International Publishing.
  * [42] A. Paullada, I. D. Raji, E. M. Bender, E. Denton, and A. Hanna.  Data and its (Dis)contents: A Survey of Dataset Development and Use in Machine Learning Research.  Patterns, 2, 11 2021.
  * [43] M. Pushkarna, A. Zaldivar, and O. Kjartansson.  Data Cards: Purposeful and Transparent Dataset Documentation for Responsible AI.  In 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’22, page 1776–1826, New York, NY, USA, 2022. Association for Computing Machinery.
  * [44] I. D. Raji, E. Denton, E. M. Bender, A. Hanna, and A. Paullada.  AI and the Everything in the Whole Wide World Benchmark.  In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
  * [45] B. Recht, R. Roelofs, L. Schmidt, and V. Shankar.  Do ImageNet Classifiers Generalize to ImageNet?  In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5389–5400. PMLR, 09–15 Jun 2019\.
  * [46] D. Rolnick, A. Veit, S. J. Belongie, and N. Shavit.  Deep Learning is Robust to Massive Label Noise.  CoRR, abs/1705.10694, 2017.
  * [47] E. Rosenfeld, E. Winston, P. Ravikumar, and Z. Kolter.  Certified Robustness to Label-Flipping Attacks via Randomized Smoothing.  In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8230–8241. PMLR, 7 2020.
  * [48] A. Roth, A. Tolbert, and S. Weinstein.  Reconciling Individual Probability Forecasts.  arXiv preprint arXiv:2209.01687, 2022.
  * [49] D. B. Rubin.  Multiple Imputation for Nonresponse in Surveys.  John Wiley & Sons, New York, 1987.
  * [50] M. K. Scheuerman, A. Hanna, and E. Denton.  Do Datasets Have Politics? Disciplinary Values in Computer Vision Dataset Development.  Proc. ACM Hum.-Comput. Interact., 5, oct 2021.
  * [51] L. Semenova, C. Rudin, and R. Parr.  On the Existence of Simpler Machine Learning Models.  In 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’22, page 1827–1858, New York, NY, USA, 2022. Association for Computing Machinery.
  * [52] A. Shafahi, W. R. Huang, M. Najibi, O. Suciu, C. Studer, T. Dumitras, and T. Goldstein.  Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks.  In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS’18, page 6106–6116. Curran Associates Inc., 2018.
  * [53] S. Shafieezadeh-Abadeh, P. M. Esfahani, and D. Kuhn.  Distributionally Robust Logistic Regression.  In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1, NIPS’15, page 1576–1584. MIT Press, 2015.
  * [54] I. Shumailov, Z. Shumaylov, D. Kazhdan, Y. Zhao, N. Papernot, M. A. Erdogdu, and R. J. Anderson.  Manipulating SGD with Data Ordering Attacks.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 18021–18032. Curran Associates, Inc., 2021.
  * [55] J. P. Simmons, L. D. Nelson, and U. Simonsohn.  False-Positive Psychology: Undisclosed Flexibility in Data Collection and Analysis Allows Presenting Anything as Significant.  Psychological Science, 22(11):1359–1366, 2011.  PMID: 22006061.
  * [56] J. Snoek, H. Larochelle, and R. P. Adams.  Practical Bayesian Optimization of Machine Learning Algorithms.  Advances in Neural Information Processing Systems, 25, 2012.
  * [57] J. Steinhardt, P. W. Koh, and P. Liang.  Certified Defenses for Data Poisoning Attacks.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 3520–3532. Curran Associates Inc., 2017.
  * [58] T. J. Sullivan.  Introduction to Uncertainty Quantification, volume 63.  Springer, 2015.
  * [59] E. Tamer.  Partial Identification in Econometrics.  Annu. Rev. Econ., 2(1):167–195, 2010.
  * [60] D. Teney, M. Peyrard, and E. Abbasnejad.  Predicting Is Not Understanding: Recognizing and Addressing Underspecification in Machine Learning.  In S. Avidan, G. Brostow, M. Cissé, G. M. Farinella, and T. Hassner, editors, Computer Vision – ECCV 2022, pages 458–476, Cham, 2022. Springer Nature Switzerland.
  * [61] C. Toma, J. Hancock, and N. Ellison.  Separating Fact From Fiction: An Examination of Deceptive Self-Presentation in Online Dating Profiles.  Personality & Social Psychology Bulletin, 34:1023–36, 09 2008\.
  * [62] S. Van Buuren.  Flexible Imputation of Missing Data.  CRC press, 2018.
  * [63] V. Vasudevan, B. Caine, R. Gontijo-Lopes, S. Fridovich-Keil, and R. Roelofs.  When Does Dough Become a Bagel? Analyzing the Remaining Mistakes on ImageNet, 2022.
  * [64] M. Wick, S. Panda, and J.-B. Tristan.  Unlocking Fairness: a Trade-off Revisited.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [65] M. Wisniewski.  In Puerto Rico, No Gap in Median Earnings between Men and Women.  Technical report, United States Census Bureau, 3 2021.
  * [66] H. Xiao, H. Xiao, and C. Eckert.  Adversarial Label Flips Attack on Support Vector Machines.  In Proceedings of the 20th European Conference on Artificial Intelligence, ECAI’12, page 870–875. IOS Press, 2012.
  * [67] R. Xin, C. Zhong, Z. Chen, T. Takagi, M. Seltzer, and C. Rudin.  Exploring the Whole Rashomon Set of Sparse Decision Trees.  In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
  * [68] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding Deep Learning (Still) Requires Rethinking Generalization.  Commun. ACM, 64(3):107–115, Feb. 2021.
  * [69] X. Zhang, X. Zhu, and S. Wright.  Training Set Debugging Using Trusted Items.  Proceedings of the AAAI Conference on Artificial Intelligence, 32(1), Apr. 2018.

##  Appendix A Additional Details From Section 3

#### A note on the relationship between $\epsilon$ and $\Delta$

Given a fixed $\epsilon$, if $\delta_{i}$ is the same for all $i$, the ratio
between $\delta$ and $\epsilon$ uniquely determines robustness to dataset
multiplicity (we make use of this fact for computing Table 2).

###  A.1 Details about Algorithm 1

Algorithm 2 is the complete algorithm for the approach described in Section
3.3. Note that this algorithm supersedes Algorithm 1.

We define the _positive potential impact_ $\rho^{+}_{i}$ as the maximal
positive change that perturbing $\tilde{\mathbf{y}}_{i}$ can have on
$\mathbf{z}\mathbf{y}$, likewise, $\rho^{-}_{i}$ is the _negative potential
impact_ , that is, the maximal negative change that perturbing
$\tilde{\mathbf{y}}_{i}$ can have on $\mathbf{z}\mathbf{y}$.

Algorithm 2 finds the minimal label perturbation necessary to change the label
of test point $\mathbf{x}$, a fact we formalize in the following theorem:

######  Theorem A.1.

Suppose we have a deterministic learning algorithm $A$, a training dataset
$D=(\mathbf{X},\mathbf{y})$ where up to $k$ labels $y_{i}$ corresponding to
data points $\mathbf{X}_{i}$ that satisfy $\phi(\mathbf{X}_{i})$ are
inaccurate by $+/-\Delta$. Let $\mathcal{M}(D)$ be the set of all datasets
that can be constructed by modifying $D$ according to $k$, $\phi$, and
$\Delta$. Let $F=A(\mathcal{M}(D))$ be the set of models $f$ obtainable by
training using $A$ on any dataset $D^{\prime}\in\mathcal{M}(D)$. Given a test
point $\mathbf{x}$, (i) Algorithm 2 outputs an interval containing all values
$f(\mathbf{x})$ for all $f\in F$ (i.e., the algorithm is sound) and (ii) there
is some $f_{1},f_{2}\in F$ such that $f_{1}(\mathbf{x})$ is equal to the upper
bound of the output and $f_{2}(\mathbf{x})$ is equal to the lower bound of the
output (i.e., the algorithm is tight).

###### Proof.

We will prove (i) that the upper bound Theorem A.1’s output is an upper bound
on the value of $f(\mathbf{x})$ for any $f\in F=A(\mathcal{M}(D))$ and (ii)
that this upper bound is achieved by some $f_{1}\in F$. The proofs for the
lower bounds are analogous.

(i) Let $u$ be the upper bound of Theorem A.1’s output. We want to show that
$f(\mathbf{x})\leq u$ for all $f\in F=A(\mathcal{M}(D))$, where

$\mathcal{M}(D=(\mathbf{X},\mathbf{y}))=\\{(\mathbf{X},\mathbf{y}^{\prime})\mid\|\mathbf{y}^{\prime}-\mathbf{y}\|_{1}\leq
k\land\mathbf{y}_{i}\neq\mathbf{y}^{\prime}_{i}\implies\phi(\mathbf{X}_{i})\land\|\mathbf{y}_{i}-\mathbf{y}^{\prime}_{i}\|\leq\Delta\\}$

.

Suppose, towards contraction, that there is some $f^{\prime}\in
A(\mathcal{M}(D))$ such that $f^{\prime}(\mathbf{x})=u^{\prime}>u$. Then,
there is some set of labels $y_{i_{1}},y_{i_{2}},\ldots,y_{i_{k}}$ that can be
modified to create a $\mathbf{y}^{\prime}$ such that
$(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}\mathbf{y}^{\prime}\mathbf{x}=u^{\prime}$.
Recall that $z=\mathbf{x}(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}$. So,
either (a), we modify the same set of labels, but modify at least one in a
different magnitude or direction, or (b), there must be some ${i_{j}}$ that we
modify $y_{i_{j}}$ to find $u^{\prime}$, but the algorithm does not identify
this index in line 8 of the algorithm.

First, suppose (a) occurred. WLOG, suppose the if case on line 2 is satisfied,
i.e., $z_{i_{j}}\geq 0$. Then we hypothetically modified $y_{i_{j}}$ by
$a\neq\delta^{u}_{i_{j}}$ in place of line 11. We know $a<\delta^{u}_{i_{j}}$
since $\delta$ is an upper bound on how much we can change each label. We have
$\delta^{u}_{i_{j}}\geq 0$ and $z_{i_{j}}\geq 0$, so their product is also
greater than 0, so $az_{i_{j}}<\delta^{u}_{i_{j}}z_{i_{j}}$. So, the final
product $\mathbf{z}\mathbf{y}^{\prime}$ cannot be larger than had we followed
the algorithm.

Now, suppose (b) occurred. Suppose $y_{i_{j}}$ is modified to yield
$u^{\prime}$, but is not modified in the algorithm. Then, there must be some
$y_{i^{\prime}}$ such that (assume WLOG that $\mathbf{z}_{i^{\prime}}\geq 0$
and $\mathbf{z}_{i_{j}}\geq 0$)
$\mathbf{z}_{i^{\prime}}\delta^{u}_{i^{\prime}}\geq\mathbf{z}_{i_{j}}\delta^{u}_{i_{j}}$.
If equality holds, we will have $u=u^{\prime}$. So, assume
$\mathbf{z}_{i^{\prime}}\delta^{u}_{i^{\prime}}>\mathbf{z}_{i_{j}}\delta^{u}_{i_{j}}$.
But then, modifying $\mathbf{y}_{i^{\prime}}$ by $\delta^{u}_{i^{\prime}}$
will result in a greater increase to $mathbf{z}\mathbf{y}$ than increasing
$\mathbf{y}_{i_{j}}$ by $\delta^{u}_{i_{j}}$ will. So, changing $y_{i_{j}}$
cannot result in an output $u^{\prime}>u$.

(ii) We need to construct the function $f\in F=A(\mathcal{M}(D))$ such that
$f(\mathbf{x})=u$, where $u$ is the upper bound of Theorem A.1’s output. Let
$y_{i_{1}},y_{i_{2}},\ldots,y_{i_{k}}$ be the labels modified by lines 15-19
of the algorithm to yield some $\mathbf{y}^{\prime}$. Then, let
$f(x)=(\mathbf{X}^{T}\mathbf{X})^{-1}\mathbf{X}^{T}\mathbf{y}^{\prime}$. ∎

###  A.2 Details on the Approximate Approach

We will next present an example to show that $\Theta$ can be non-convex.

######  Example A.1.

Suppose $\mathbf{y}=(1,-1,2)$, $\Delta=[-1,1]^{3}$, and $k=2$. Given
$\mathbf{C}=\begin{pmatrix}1&2&1\\\ -1&0&2\\\ 2&1&0\end{pmatrix}$, we have

$\Theta=\mathbf{C}\mathbf{y}\cup\left\\{\mathbf{C}\begin{pmatrix}a\\\ b\\\
2\end{pmatrix}\right\\}\cup\left\\{\mathbf{C}\begin{pmatrix}a\\\ -1\\\
c\end{pmatrix}\right\\}\cup\left\\{\mathbf{C}\begin{pmatrix}1\\\ b\\\
c\end{pmatrix}\right\\}$

for $a\in[0,2]$, $b\in[-2,0]$, and $c\in[1,3]$.

Note that $(3,6,3)^{\top}\in\Theta$ and $(4,5,2)^{\top}\in\Theta$, but their
midpoint $(3.5,5.5,3.5)^{\top}\notin\Theta$, thus, $\Theta$ is non-convex.

We present the complete algorithm for procedure described in Section 3.4
Algorithm 3. Next, we will show that this algorithm outputs the tightest
hyperrectangular (i.e., box) enclosure of $\mathcal{M}$.

######  Theorem A.2.

Algorithm 3 computes the tightest hyperrectangular enclosure of $\mathcal{M}$.

###### Proof.

First, we will show that Algorithm 3 computes an enclosure of $\mathcal{M}$,
and next we will show that this output is the tightest hyperrectangular
enclosure of $\mathcal{M}$.

By construction of the algorithm, we see that the output will be an enclosure
of $\mathcal{M}$. The algorithm constructs the maximal way to
increase/decrease each coordinate.

Now, suppose there is another hyperrectangle ${{\Theta}^{a}}^{\prime}$ that
with $\mathcal{M}(D)\subseteq{{\Theta}^{a}}^{\prime}$ and
${{\Theta}^{a}}^{\prime}_{i}\subset{\Theta}^{a}_{i}$. WLOG, assume that the
upper bound of ${\Theta^{a}}^{\prime}_{i}$ is strictly less than the upper
bound of ${\Theta}^{a}_{i}$. But
${\Theta}^{a}_{i}=\max_{(\mathbf{X},\mathbf{y}^{\prime})\in\mathcal{M}(D)}(\mathbf{z}_{i}\mathbf{y}^{\prime})$,
which means that
$\mathbf{y}^{*}=\max_{(\mathbf{X},\mathbf{y}^{\prime})\in\mathcal{M}(D)}\mathbf{C}\mathbf{y}^{\prime}$
has $\mathbf{C}_{i}\mathbf{y}^{*}$ greater than the upper bound of
${\Theta^{a}}^{\prime}_{i}$, and thus ${\Theta^{a}}^{\prime}$ is not a sound
enclosure of $\Theta$. ∎

Algorithm 2 Solve for
$V=[\min_{(\mathbf{X},\tilde{\mathbf{y}})\in\mathcal{M}_{k,\Delta,\phi}((\mathbf{X},\mathbf{y}))}\mathbf{z}\tilde{\mathbf{y}},\max_{(\mathbf{X},\tilde{\mathbf{y}})\in\mathcal{M}_{k,\Delta,\phi}((\mathbf{X},\mathbf{y}))}\mathbf{z}\tilde{\mathbf{y}}]$
by finding perturbations of $\mathbf{y}$ that maximally decrease/increase
$\mathbf{z}\mathbf{y}$.

1:$\mathbf{z}\in\mathbb{R}^{n},(\mathbf{X},\mathbf{y})\in(\mathbb{R}^{n\times
d},\mathbb{R}^{n}),\Delta\in\mathbb{IR}^{n}$ with $0\in\Delta$, $k\geq 0$,
$\phi:\mathbb{R}^{d}\rightarrow\\{0,1\\}$

2:$\mathbf{y}^{l}\leftarrow\mathbf{y}$ and
$\mathbf{y}^{u}\leftarrow\mathbf{y}$

3:if $z_{i}\geq 0$ then

4: $\rho^{+}_{i}\leftarrow\mathbf{z}_{i}\delta_{i}^{u}\ $, $\ \
\rho^{-}_{i}\leftarrow\mathbf{z}_{i}\delta_{i}^{l}$

5:else

6: $\rho^{+}_{i}\leftarrow\mathbf{z}_{i}\delta_{i}^{l}\ $, $\ \
\rho^{-}_{i}\leftarrow\mathbf{z}_{i}\delta_{i}^{l}$

7:if not $\phi(\mathbf{x}_{i})$ then

8: $\rho^{+}_{i}\leftarrow 0$, $\ \ \rho^{-}_{i}\leftarrow 0$

9:Let $\rho^{+}_{i_{1}},\ldots,\rho^{+}_{i_{l}}$ be the $k$ largest elements
of $\rho^{+}$ by absolute value

10:for each $\rho^{+}_{i_{j}}$ do

11: if $z_{i_{j}}\geq 0$ then

12: $(y^{u})_{i_{j}}\leftarrow(y^{u})_{i_{j}}+\delta_{i_{j}}^{u}$

13: else

14: $(y^{u})_{i_{j}}\leftarrow(y^{u})_{i_{j}}+\delta_{i_{j}}^{l}$

15:Let $\rho^{-}_{i_{1}},\ldots,\rho^{-}_{i_{l}}$ be the $k$ largest elements
of $\rho^{-}$ by absolute value

16:for each $\rho^{-}_{i_{j}}$ do

17: if $z_{i_{j}}\geq 0$ then

18: $(y^{l})_{i_{j}}\leftarrow(y^{l})_{i_{j}}+\delta_{i_{j}}^{l}$

19: else

20: $(y^{l})_{i_{j}}\leftarrow(y^{l})_{i_{j}}+\delta_{i_{j}}^{u}$

21:$V=[\mathbf{z}\mathbf{y}^{l},\mathbf{z}\mathbf{y}^{u}]$

Algorithm 3 Computing $\Theta^{a}$

1:$\mathbf{C}\in\mathbb{R}^{d\times
n},(\mathbf{X},\mathbf{y})\in(\mathbb{R}^{n\times
d},\mathbb{R}^{n}),\Delta\in\mathbb{IR}^{n}$ with $0\in\Delta$, $k\geq 0$,
$\phi:\mathbb{R}^{d}\rightarrow\\{0,1\\}$

2:$\mathbf{y}^{l}\leftarrow\mathbf{y}$ and
$\mathbf{y}^{u}\leftarrow\mathbf{y}$

3:$\ \Theta^{a}\leftarrow[0,0]^{d}$

4:for $i$ in range $d$ do:

5: $\mathbf{y}^{l}\leftarrow\mathbf{y}$, $\ \
\mathbf{y}^{u}\leftarrow\mathbf{y}$

6: if $c_{ij}<0$ then

7: $\rho^{+}_{j}\leftarrow\mathbf{C}_{ij}\delta_{j}^{l}\ $, $\ \
\rho^{-}_{j}\leftarrow\mathbf{C}_{ij}\delta_{j}^{u}$

8: else

9: $\rho^{+}_{j}\leftarrow\mathbf{C}_{ij}\delta_{j}^{u}\ $, $\ \
\rho^{-}_{j}\leftarrow\mathbf{C}_{ij}\delta_{j}^{l}$

10: if not $\phi(\mathbf{x}_{i})$ then

11: $\rho^{+}_{j}\leftarrow 0$, $\ \ \rho^{-}_{j}\leftarrow 0$

12: Let $\rho^{+}_{k_{1}},\ldots,\rho^{+}_{k_{l}}$ be the $k$ largest elements
of $\rho^{+}$ by absolute value.

13: for each $\rho^{+}_{k_{j}}$ do

14: if $c_{i{k_{j}}}\geq 0$ then

15: $(y^{u})_{k_{j}}\leftarrow(y^{u})_{k_{j}}+\delta_{k_{j}}^{u}$

16: else

17: $(y^{u})_{k_{j}}\leftarrow(y^{u})_{k_{j}}+\delta_{k_{j}}^{l}$

18: Let $\rho^{-}_{k_{1}},\ldots,\rho^{-}_{k_{l}}$ be the $k$ largest elements
of $\rho^{-}$ by absolute value.

19: for each $\rho^{-}_{k_{j}}$ do

20: if $c_{i{k_{j}}}\geq 0$ then

21: $(y^{l})_{k_{j}}\leftarrow(y^{l})_{k_{j}}+\delta_{k_{j}}^{l}$

22: else

23: $(y^{l})_{k_{j}}\leftarrow(y^{l})_{k_{j}}+\delta_{k_{j}}^{u}$

24:
$\Theta^{a}_{i}\leftarrow[\mathbf{c}_{i}\mathbf{y}^{l},\mathbf{c}_{i}\mathbf{y}^{u}]$

##  Appendix B Additional Experiments

We present additional tables, graphs, and discussion about the experimental
results.

#### Accuracy

The maximal accuracy for each dataset (i.e., in Figure 2, the accuracy for the
0.0 line) is 76.5% for Income, 61.9% for LAR, and 98.9% for MNIST. The exact
values we used for $\lambda$ (as well as the procedure to obtain $\lambda$)
are in the code.

#### Additional LAR data

Figure 6 shows demographic-stratified dataset-multiplicity robustness rates
for LAR under different ways of defining targeted dataset multiplicity. To
varying extents, the majority/advantaged group sees higher robustness rates as
compared with the disadvantaged group across all versions of $\mathcal{M}$.

Figure 6:  Targeted label multiplicity for LAR. (a) only allows errors in
labels for Black people (flip labels from -1 to 1), (b) only allows errors in
labels for White people (flip labels from 1 to -1), (c) only allows errors in
labels for women (flip labels from -1 to 1), and (d) only allows errors in
labels for men (flip labels from 1 to -1). In graphs (a) and (b), group 1 is
Black people while group 2 is White people. In graphs (c) and (d), group 1 is
women and group 2 is men. In all graphs, the error bars represent the middle
50% of values across 10-fold cross validation.

#### Regression dataset results

Table 2 presents results on Income-Reg for the fixed robustness radius
$\epsilon=\$$2,000$$, which we chose as a challenging, but reasonable,
definition for two incomes being close. We also empirically validated that the
ratio between $\Delta$ and $\epsilon$ uniquely determines robustness for a
fixed multiplicity definition. Notably, for small $\Delta$ to $\epsilon$
ratios (i.e., when we can modify labels by small amounts, but predictions can
be far apart and still considered robust), many test points are dataset-
multiplicity robust, even when the number of untrustworthy training labels is
relatively large (up to $10\%$). However, when this ratio is large, e.g., when
$\Delta=5\epsilon$, we are still able certify a majority of test points as
robust up to 1% bias. For example, if we can modify 1% of labels by up to
$$10,000$, then 69.6% of test samples’ predictions cannot be modified by more
than $$2,000$. By contrast, only allowing 1% of labels to be modified by up to
$$4,000$ yields a dataset-multiplicity robustness rate of 91.2% (again, within
a radius of $$2,000$).

Table 2: Robustness rates (percentage of test dataset whose prediction cannot change by more than $\epsilon$) for Income-Reg given various $\Delta$ and $k$ values. $\epsilon=$2,000$$ in all experiments. Note that the shorthand $\Delta=a$ means $\Delta=[-a,a]^{n}$. Column 2 gives the ratio between the maximum label perturbation ($\Delta$) and the robustness radius ($\epsilon$), which uniquely determines robustness for a given $k$.  $\Delta$ | Ratio $\frac{\Delta}{\epsilon}$ |  Maximum label error $k$ as a percentage of training dataset size
---|---|---
1.0% | 2.0% | 3.0% | 4.0% | 5.0% | 6.0% | 7.0% | 8.0% | 9.0% | 10.0%
$1,000$ | 0.5 | 100.0 | 100.0 | 100.0 | 100.0 | 99.8 | 99.4 | 99.1 | 98.6 | 98.0 | 97.1
$2,000$ | 1 | 100.0 | 96.6 | 91.1 | 85.4 | 84.1 | 76.4 | 73.3 | 64.0 | 49.9 | 35.2
$4,000$ | 2 | 91.2 | 84.2 | 69.2 | 35.7 | 14.2 | 2.0 | 0 | 0 | 0 | 0
$6,000$ | 3 | 85.9 | 61.1 | 15.4 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$8,000$ | 4 | 80.1 | 20.0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$10,000$ | 5 | 69.6 | 3.6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0

#### Income demographics

Table 3 shows the demographic make-up of various states’ data from the Income
dataset. Notice that Oregon has the lowest percentage of Black people in the
dataset - we suspect that this is why the robustness rates between White and
Black people is so large.

Table 3: Summary of data download by state from the Folktables Income task. State |  training $n$ | % White | % Black
---|---|---|---
Georgia | 40731 | 67.6 | 23.9
Louisiana | 16533 | 70.9 | 23.5
Maryland | 26433 | 63.6 | 23.5
Oregon | 17537 | 86.4 | 1.4
Wisconsin | 26153 | 92.7 | 2.6

Figure 7 shows robustness rates, stratified by race or gender, for five U.S.
states on the Income dataset. We see that for most states, there is a
significant gap in robustness rates across with race and gender. In
particular, Georgia and Louisiana have higher robustness rates for Black
people, and Oregon has _drastically_ higher robustness rates for White people.
All states, except Wisconsin, have higher robustness rates for men than women.

Figure 7: Row 1: Robustness rate for White people (gray lines) and Black
people (black lines) across 5 different states of the Income dataset. Row 2:
Robustness rates for men (gray lines) and women (black lines) across 5
different states of the Income dataset. Error bars show averages across 10
folds.

Figure 8 shows the demographic group-level robustness rates under the over-
approximate technique.

Figure 8: Row 1: Robustness rate under the over-approximate approach for White
people (gray lines) and Black people (black lines) across 5 different states
of the Income dataset. Row 2:  Robustness rates for men (gray lines) and women
(black lines) across 5 different states of the Income dataset. Error bars show
averages across 10 folds.

###  B.1 Running time

Table 4 shows the running time of our techniques, as evaluated on a 2020
MacBook Pro with 16GB memory and 8 cores. These times should be interpreted as
upper bounds; in practice, both approaches are amenable to parallelization,
which would yield faster performance. We notice that both the exact approach
scales linearly with the number of samples, while the approximate approach
stays within a single order of magnitude as the number of samples
grows.Clearly, the approximate approach is more scalable for checking the
robustness of large numbers of data points.

Table 4: Running time, in seconds, for exact and approximate experiments. The exact experiments flip labels for each data point until the sample is no longer robust. The approximate experiments flip 10% of the labels (which is enough to bring the robustness to 0%). Dataset |  $100$ samples |  $1,000$ samples |  $10,000$ samples
---|---|---|---
Exact | Approx. | Exact | Approx. | Exact | Approx.
Income | 2.5 | 4.4 | 37.2 | 6.8 | 383.5 | 30.7
LAR | 7.5 | 1.8 | 73.5 | 2.6 | 730.2 | 10.6
MNIST 1/7 | 4.1 | 3.8 | 24.8 | 6.0 | 448.5 | 24.3

Table 5 shows the running time of the MILP solver for Income and LAR. We see
that the times scale linearly (as with our exact approach), but are much
worse. To check robustness for 100 samples, it is over 80% slower to use MILP.

Table 5: Running time, in seconds, for the MILP solver. We modify 10% of the labels.  Dataset | 10 samples | 100 samples
---|---|---
Income | 49.1 | 498.8
LAR | 58.1 | 616.6


* Di Vita  _et al._ [2014] S. Di Vita, P. Mastrolia, U. Schubert, and V. Yundin, Three-loop master integrals for ladder-box diagrams with one massive leg, JHEP 09, 148, arXiv:1408.3107 [hep-ph] .
  * Henn [2013] J. M. Henn, Multiloop integrals in dimensional regularization made simple, Phys. Rev. Lett. 110, 251601 (2013), arXiv:1304.1806 [hep-th] .
  * Carter and Heinrich [2011] J. Carter and G. Heinrich, SecDec: A general program for sector decomposition, Comput. Phys. Commun. 182, 1566 (2011), arXiv:1011.5493 [hep-ph] .
  * Borowka  _et al._ [2013] S. Borowka, J. Carter, and G. Heinrich, Numerical evaluation of multi-loop integrals for arbitrary kinematics with SecDec 2.0, Comput. Phys. Commun. 184, 396 (2013), arXiv:1204.4152 [hep-ph] .
  * Borowka  _et al._ [2015] S. Borowka, G. Heinrich, S. P. Jones, M. Kerner, J. Schlenk, and T. Zirke, SecDec-3.0: numerical evaluation of multi-scale integrals beyond one loop, Comput. Phys. Commun. 196, 470 (2015), arXiv:1502.06595 [hep-ph] .
  * Borowka  _et al._ [2018] S. Borowka, G. Heinrich, S. Jahn, S. Jones, M. Kerner, J. Schlenk, and T. Zirke, pySecDec: a toolbox for the numerical evaluation of multi-scale integrals, Comput. Phys. Commun. 222, 313 (2018), arXiv:1703.09692 [hep-ph] .
  * Cirigliano  _et al._ [2012] V. Cirigliano, M. L. Graesser, and G. Ovanesyan, WIMP-nucleus scattering in chiral effective theory, JHEP 10, 025, arXiv:1205.2695 [hep-ph] .
  * Patel [2015] H. H. Patel, Package-X: A Mathematica package for the analytic calculation of one-loop integrals, Comput. Phys. Commun. 197, 276 (2015), arXiv:1503.01469 [hep-ph] .
  * Denner and Dittmaier [2003] A. Denner and S. Dittmaier, Reduction of one loop tensor five point integrals, Nucl. Phys. B658, 175 (2003), arXiv:hep-ph/0212259 .
  * Denner and Dittmaier [2006] A. Denner and S. Dittmaier, Reduction schemes for one-loop tensor integrals, Nucl. Phys. B734, 62 (2006), arXiv:hep-ph/0509141 .
  * Denner and Dittmaier [2011] A. Denner and S. Dittmaier, Scalar one-loop 4-point integrals, Nucl. Phys. B844, 199 (2011), arXiv:1005.2076 [hep-ph] .
  * Denner  _et al._ [2017] A. Denner, S. Dittmaier, and L. Hofer, Collier: a fortran-based Complex One-Loop LIbrary in Extended Regularizations, Comput. Phys. Commun. 212, 220 (2017), arXiv:1604.06792 [hep-ph] .
  * Zyla  _et al._ [2020] P. Zyla _et al._ (Particle Data Group), Review of Particle Physics, PTEP 2020, 083C01 (2020).
  * Hoferichter and Stoffer [2020] M. Hoferichter and P. Stoffer, Asymptotic behavior of meson transition form factors, JHEP 05, 159, arXiv:2004.06127 [hep-ph] .
  * Anastasiou  _et al._ [2007] C. Anastasiou, S. Beerli, S. Bucherer, A. Daleo, and Z. Kunszt, Two-loop amplitudes and master integrals for the production of a Higgs boson via a massive quark and a scalar-quark loop, JHEP 01, 082, arXiv:hep-ph/0611236 .
  * Ferguson and Bailey [1992] H. R. P. Ferguson and D. H. Bailey, A Polynomial Time, Numerically Stable Integer Relation Algorithm, RNRTechnical Report RNR-91-032 (1992).
  * Argeri  _et al._ [2002] M. Argeri, P. Mastrolia, and E. Remiddi, The analytic value of the sunrise selfmass with two equal masses and the external invariant equal to the third squared mass, Nucl. Phys. B631, 388 (2002), arXiv:hep-ph/0202123 [hep-ph] .