,

# Certifying Data-Bias Robustness in Linear Regression

Anna P. Meyer, Aws Albarghouthi, and Loris D’Antoni
Department of Computer Sciences
University of Wisconsin–Madison
Madison, WI 53706
{annameyer, aws<EMAIL_ADDRESS>
Author’s name in native alphabet: ’aws albr.gU_ty

###### Abstract

Datasets typically contain inaccuracies due to human error and societal
biases, and these inaccuracies can affect the outcomes of models trained on
such datasets. We present a technique for certifying whether linear regression
models are _pointwise-robust_ to label bias in the training dataset, i.e.,
whether bounded perturbations to the labels of a training dataset result in
models that change the prediction of test points. We show how to solve this
problem exactly for individual test points, and provide an approximate but
more scalable method that does not require advance knowledge of the test
point. We extensively evaluate both techniques and find that linear models –
both regression- and classification-based – often display high levels of bias-
robustness. However, we also unearth gaps in bias-robustness, such as high
levels of non-robustness for certain bias assumptions on some datasets.
Overall, our approach can serve as a guide for when to trust, or question, a
model’s output.

##  1 Introduction

We see an inherent tension between the growing popularity of machine learning
models and the fact that the data that powers these models is not always
objective, accurate, or complete [27]. Labels of a dataset are particularly
vulnerable due to social biases in crowdworkers and other data-labellers, and
subjectivity in many labeling tasks [2, 15, 31, 36]. A key concern, and one we
show how to address, is _whether biases or inaccuracies in the data change
test-time predictions._ We posit that considering the impact that bias in
datasets has on the predictions’ _robustness_ is key. We illustrate this idea
with the following example. Both the example and our approach use linear
regression models.

######  Example 1.1.

Suppose a company $C$ trains a linear regression model to decide what to pay
their new hires based on data such as their education and work experience. $C$
wants to compensate its new employees fairly – in particular, it does not want
the salary offers to be tainted by bias in how its current employees (i.e.,
the training data) are compensated, whether due to the gender pay gap,
inconsistencies on how managers apply raises, or other factors.

Alice was just hired at C and the model predicts that her salary should be
$60000. Now, suppose that we could _unbias_ the training data, that is,
eradicate the gender pay gap, standardize compensation practices across
divisions, and remove any other irregularities. If we trained a new model on
this unbiased data, would Alice’s new salary prediction be the same as (i.e.,
within $\epsilon$ of) the old prediction? If so, then we would say that the
company’s model is _pointwise-bias-robust_ for Alice.

In this paper, we formally study how biases or inaccuracies in the labels of a
training dataset affect the test-time predictions of linear regression models.
A naïve approach is to enumerate all possible sets of labels, train a model
using each, and compare the results. We have two key insights that allow us to
solve the problem more efficiently: first, given a fixed test point
$\mathbf{x}$, we can take advantage of the linearity of the regression
algorithm to exactly compute the minimal label perturbations needed to change
the prediction of $\mathbf{x}$ by a given threshold. Second, in the absence of
a fixed test point, we can extend the same approach and use interval
arithmetic to compute an over-approximation of the feasible range of models,
allowing for fast (though over-approximate) robustness certification at test
time. We discuss how these innovations can help model designers evaluate
whether their models’ decisions can be trusted, i.e., whether their models are
ready to be deployed.

##### Contributions

Our main contributions are:(1) Defining the bias-robustness problem for
regression datasets with label bias (§ 3). (2) A technique to find the
smallest training-data label perturbation that changes the prediction of a
fixed test point, thereby certifying or disproving pointwise robustness (§ 4).
(3) A faster, over-approximate certification technique that can certify
pointwise bias robustness by bounding the range of linear models obtainable
with a fixed amount of label perturbation (§ 5). (4) Evaluating our results on
a variety of datasets and with a variety of forms of bias, and discuss what
dataset properties impact label-bias robustness (§ 6).

##  2 Related work

##### Uncertainty in machine learning

Uncertainty in machine learning has been studied in conjunction with fair and
trustworthy AI because in high-impact domains it is crucial to understand when
an algorithm might fail or have disparate impacts on different subgroups [1,
4, 35]. In this area, previous work has shown that many models can yield
comparable accuracy (but different predictions) on the same training set [8,
13, 20]. We conduct a similar analysis in a parallel direction by considering
the range of models that can be learned over similar datasets.

##### Poisoning attacks and defenses

Poisoning attacks, where an attacker can modify a small portion of the
training dataset, can be effective at reducing the accuracy of models at test-
time [5, 32, 38, 37]. Various defenses counteract these attacks [17, 26, 30,
34, 39], including ones that focus on attacking and defending linear
regression models [16, 22]. Some of these works have a broad definition of
bias that includes label perturbations, data deletion, and data poisoning. We
only consider label perturbations, making our threat model similar to a
handful of others [26, 30, 37]; however, we allow a more flexible threat model
by allowing the user to target the label poisoning to certain subgroups.

Our work differs from existing poisoning literature in two important ways:
first, we certify _pointwise_ robustness _deterministically_ : that is, we
prove, with 100% certainty, whether the prediction of a particular test point
is vulnerable to bias (i.e., poisoning) in the training data. Second, we do
not modify the training procedure, as in [17, 34, 30], nor do we make
assumptions that we have access to (parts of) the clean data [34, 39]. Meyer
et al. have a similar problem definition to ours: they certify robustness by
overapproximating the set of models that one can learn on variants of the
dataset, and although their approach applies to complex forms of bias, it is
limited to decision trees [21].

##### Robustness

Distributional robustness studies how to find models that perform well across
a family of distributions [3, 23, 33]. Our problem definition can be framed as
working over a family of distributions (where the distributions differ only in
the labels). Robust statistics shows how algorithms can be adapted to account
for outliers or other errors in the data [10, 11]. Our work does not require
that the data follows any particular distribution, and thus we can certify a
broader range of datasets. Others have shown that some algorithms are
inherently, or modifiable to be, robust to label noise [24, 25, 29]. However,
these works – along with the robust statistics and distributional robustness
literature – provide statistical global robustness guarantees, rather than the
provable exact robustness guarantees that we make. That is, they are
interested in finding one good classifier, rather than understanding the range
of classifiers that could be obtained even in extreme cases.

##### Algorithmic stability

Algorithmic stability measures how sensitive algorithms are to small
perturbations in the training data [7, 9]. Our work differs from this
literature in a couple ways: first, rather than the commonly used leave-one-
out perturbation model [6, 18], we allow for a fixed number of small label
perturbations; second, as discussed above, our focus is certifying point-wise
robustness rather than ensuring comparable overall behavior.

##  3 Label-Bias Robustness

First, we formally define label bias and what it means for a learning
algorithm to be bias-robust.

##### Label-bias function

We define a dataset as a matrix of features $\mathbf{X}\in\mathbb{R}^{n\times
m}$ and a corresponding vector of labels $\mathbf{y}\in\mathbb{R}^{n}$. The
_label-bias function_ , or bias function for short,
$\textsc{bias}:\mathbb{R}^{n}\rightarrow 2^{\mathbb{R}^{n}}$, is a function
that takes in a label vector $\mathbf{y}$ and returns set of label vectors
such that $\mathbf{y}\in\textsc{bias}(\mathbf{y})$. Intuitively,
$\textsc{bias}(\mathbf{y})$ returns a set of all labels vectors that are
similar to $\mathbf{y}$ (we will define what “similar” means in § 3.1). Thus,
if $\mathbf{y}$ is biased by a small amount, its “true,” unbiased counterpart
will be in $\textsc{bias}(\mathbf{y})$. We will refer to
$\textsc{bias}(\mathbf{y})$ as the label-bias set of $\mathbf{y}$, or bias set
for short.

##### Pointwise label-bias robustness

Assume we have a learning algorithm that, given a training dataset, returns a
model $h$ from some hypothesis class. Fix a dataset $(\mathbf{X},\mathbf{y})$
and bias function bias. Let $h$ be the model learned from
$(\mathbf{X},\mathbf{y})$. Given a test point $\mathbf{x}\in\mathbb{R}^{m}$
and a _robustness radius_ $\epsilon$, we say that our learning algorithm is
_$(\epsilon,\textsc{bias})$ -robust_ on $\mathbf{x}$ iff for all
$\tilde{\mathbf{y}}\in\textsc{bias}(\mathbf{y})$, if $\tilde{h}$ is the model
learned on $(\mathbf{X},\tilde{\mathbf{y}})$, then

$\tilde{h}(\mathbf{x})\in[h(\mathbf{x})-\epsilon,h(\mathbf{x})+\epsilon]$ (1)

In other words, even if there were label bias in the dataset, the prediction
on $\mathbf{x}$ would not deviate by more than $\epsilon$.

###  3.1 Models of Bias

We now demonstrate how we define the bias function bias to mimic real-world
scenarios.

##### Vectors of intervals

We will use interval arithmetic to define bias. The set of intervals is
defined as $\mathbb{\mathbb{IR}}=\\{[l,u]\mid l,u\in\mathbb{R},\ l\leqslant
u\\}$. Given an interval $V=[l,u]$, we define $V^{l}=l$ and $V^{u}=u$. If
$\Delta\in\mathbb{\mathbb{IR}}^{n}$ is a vector of intervals, we use
$\delta_{i}^{l}$ and $\delta_{i}^{u}$ to denote the lower and upper bounds of
the $i$th interval in $\Delta$.

##### Defining the bias set

We assume that up to $k$ of the labels in $\mathbf{y}$ are incorrect, that is,
perturbed within some range. We will use a vector of intervals $\Delta$ to
specify how much each label can be changed—we call this vector the
_perturbation vector_.

Given a dataset $(\mathbf{X},\mathbf{y})$, a maximum number $k$ of biased
labels, and a perturbation vector $\Delta$, the set
$\textsc{bias}_{k,\Delta}(\mathbf{y})$ is the set of all label vectors that we
can create by modifying up to $k$ labels in $\mathbf{y}$ according to
$\Delta$, i.e.,

$\textsc{bias}_{k,\Delta}(\mathbf{y})=\\{\tilde{\mathbf{y}}\mid\tilde{y}_{i}\in[y_{i}+\delta_{i}^{l},y_{i}+\delta_{i}^{u}]\textrm{
for all }i\textrm{ and }||\tilde{\mathbf{y}}-\mathbf{y}||_{0}\leqslant k\\}$

Since we require that $\mathbf{y}\in\textsc{bias}(\mathbf{y})$, it is
necessary that $0\in\Delta$.

######  Example 3.1.

Let $\Delta=([-1,1],[-1,1])^{\top}$. Given $\mathbf{y}=(3,4)^{\top}$ and a
maximum number of biased labels $k=1$, we have

$\textsc{bias}_{k,\Delta}(\mathbf{y})=\left\\{\mathbf{y}\right\\}\cup\left\\{\begin{pmatrix}a\\\
4\end{pmatrix}\mid a\in[2,4]\right\\}\cup\left\\{\begin{pmatrix}3\\\
b\end{pmatrix}\mid b\in[3,5]\right\\}.$

In other words, at most one label in $\mathbf{y}$ can be changed by at most 1.

######  Example 3.2.

We continue the premise from Example 1.1. If we know, or suspect, that C has a
gender wage gap (i.e., women are systematically paid less than men), we can
model $\Delta$ as follows: if the gender of data point $\mathbf{x}_{i}$ is
male, then $\delta_{i}=[0,0]$; if the gender of $\mathbf{x}_{i}$ is female,
then $\delta_{i}=[0,2000]$, under the assumption that each woman employee is
potentially underpaid by up to $2000.

##### Binary classification

In a classification setting with $\\{0,1\\}$ labels, the default value for
$\Delta$ is $\delta_{i}=[-1,0]$ when $y_{i}=1$, and $\delta_{i}=[0,1]$ when
$y_{i}=0$, modeling a label flip. If we wish to further limit the bias, these
intervals may be changed to $[0,0]$ for some indices. E.g., if we believe that
there was historical bias against women leading to incorrect negative labels,
then we can use $\delta_{i}=[0,1]$ for women with a negative label (i.e., when
$y_{i}=0$), and $\delta_{i}=[0,0]$ for the rest of the dataset.

##  4 Exact Bias-Robustness Certification for Linear Regression

In this section, we present a technique for proving bias robustness (Eq. 1)
for a given input. Our approach is an exact certification technique, that is,
it can prove or disprove $(\epsilon,\textsc{bias})$-robustness. In the latter
case, it will produce a perturbation
$\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})$ that changes the
prediction by more than $\epsilon$, as we illustrate in the following example.

######  Example 4.1.

We continue the premise from Example 1.1. Figure 1a shows salary data and the
resulting regression model (all features are projected onto the $x$-axis).
Figure 1b shows the same dataset, with one salary (in red) perturbed by
$+\$\num{10000}$. Note that the new model is slightly different from the
original. Figure 1c shows a data point, $\mathbf{x}$, that – given a
robustness radius of $1000 – is not robust since the original model predicts
$\mathbf{x}$’s salary as $85720 while the new one predicts $90956.

##### Linear regression

We use least-squares regression, i.e., we want to solve the optimization
problem

$\min_{\theta\in\mathbb{R}^{m}}(\mathbf{y}-\mathbf{X}\theta)$

Least-squares regression admits a closed-form solution,
$\theta=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}\mathbf{y}$, for
which we will prove bias-robustness. 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 certify bias robustness by
exploiting linearity (Rosenfeld et al. make an analogous observation [30], and
on medium-sized datasets and modern machines, computing the closed-form
solution is efficient).

Given an input $\mathbf{x}$, we predict its label $\hat{y}$ as
$\theta^{\top}\mathbf{x}$. We can expand and rearrange
$\theta^{\top}\mathbf{x}$ as follows:

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

We will use $\mathbf{z}$ to denote
$\mathbf{x}^{\top}(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}$.

##### Certifying robustness for regression tasks

Suppose we have a dataset $(\mathbf{X},\mathbf{y})$, a corresponding bias
model $\textsc{bias}_{k,\Delta}(\mathbf{y})$, and a test point $\mathbf{x}$.
We want to prove that the prediction on $\mathbf{x}$ is
$(\epsilon,\textsc{bias}_{k,\Delta})$-robust, as per Eq. 1. Informally, our
goal is to find how the prediction $\hat{y}=\theta^{\top}\mathbf{x}$ varies
when different $\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})$ are
used to find $\theta$. Specifically, we aim to find

$\max_{\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}|\mathbf{z}\tilde{\mathbf{y}}-\mathbf{z}\mathbf{y}|$
(2)

######  Lemma 1.

Given $\tilde{\mathbf{y}}$ as per Eq. 2, $\mathbf{x}$ is
$(\epsilon,\textsc{bias}_{k,\Delta})$-robust iff
$\mathbf{z}\tilde{\mathbf{y}}\in[\hat{y}-\epsilon,\hat{y}+\epsilon]$.

##### Algorithmic technique

The naïve approach to solve this maximization objective is to enumerate all
$\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})$, train a model on
each, and compare the resulting $\hat{y}$’s. Of course, this will not be
computationally feasible since the set $\textsc{bias}_{k,\Delta}(\mathbf{y})$
is infinite. Instead, we exploit the linearity of the inner product
$\mathbf{z}\mathbf{y}$ and iteratively find a label $y_{i}$ that when changed
will result in the largest perturbation to the prediction of $\mathbf{x}$.

We will discuss how to find the range of values $V$ that
$\mathbf{z}\tilde{\mathbf{y}}$ can take on, i.e.,

$V=\left[\min_{\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{z}\tilde{\mathbf{y}},\max_{\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{z}\tilde{\mathbf{y}}\right]$

To check robustness, we check whether
$V\subseteq[\mathbf{z}\mathbf{y}-\epsilon,\mathbf{z}\mathbf{y}+\epsilon]$.
Formally: Formally,

######  Lemma 2.

$V\subseteq[\mathbf{z}\mathbf{y}-\epsilon,\mathbf{z}\mathbf{y}+\epsilon]$ iff
$\mathbf{x}$ is $(\epsilon,\textsc{bias}_{k,\Delta})$-robust

We discuss how to find the upper bound of $V$ here—see Algorithm 1. Finding
the lower bound is analogous and is presented in the appendix.

Intuitively, the labels in $\mathbf{y}$ with the highest influence on the
prediction of $\mathbf{x}$ are those corresponding to elements of $\mathbf{z}$
with the largest magnitude. However, we must also take into account $\Delta$:
even if $z_{i}$ is very large, perturbing $y_{i}$ will only affect the outcome
if $\delta_{i}$ allows for a non-zero perturbation.

We define the _positive potential impact_ $\rho_{i}^{+}$ of $z_{i}$ as the
maximal positive change that perturbing $y_{i}$ can have on
$\mathbf{z}\mathbf{y}$. After computing $\rho^{+}$, we find the $k$ largest
elements of $\rho^{+}$ by absolute value. The indices of these entries
correspond to the indices of the labels of $\mathbf{y}$ we will change to
maximally increase $\mathbf{z}\mathbf{y}$, i.e., to find the upper bound of
$V$.

######  Example 4.2.

Let $\mathbf{y}=(3,4)^{\top}$ and $\mathbf{z}=(-1,2)$. Suppose
$\Delta=([-1,1],[-1,1])^{\top}$. Since $z_{1}<0$, we can increase
$\mathbf{z}\mathbf{y}$ by decreasing $y_{1}$, that is, by adding
$\delta_{1}^{l}=-1$ to it. Thus $\rho^{+}_{1}=z_{1}\delta_{1}^{l}=1$. Since
$z_{2}\geq 0$, we can increase $\mathbf{z}\mathbf{y}$ by increasing $y_{2}$.
Therefore, $\rho^{+}_{2}=z_{2}\delta_{2}^{l}=2$.

Figure 1: Motivation for our approach. (a) shows an example dataset and model.
(b) shows the same dataset (and resulting model) with one label perturbed. (c)
shows that the new data point $\mathbf{x}$ is not robust to the label
perturbation from (b). (d) shows the overlay of all models that could be
constructed by changing any one label in the dataset by up to $10000.
Algorithm 1 Find the upper bound of
$V=[\min_{\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{z}\tilde{\mathbf{y}},\max_{\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{z}\tilde{\mathbf{y}}]$

$\mathbf{z}\in\mathbb{R}^{n},\mathbf{y}\in\mathbb{R}^{n},\Delta\in\mathbb{IR}^{n}$
with $0\in\Delta$, $k\geq 0$

$\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}\ $

Let $\rho^{+}_{i_{1}},\ldots,\rho^{+}_{i_{k}}$ be the $k$ 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}$

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

######  Example 4.3.

We continue Example 4.2. Suppose $k=1$. We initially set
$\mathbf{y}^{u}=\mathbf{y}$. Since $\rho^{+}=(1,2)$, we initially perturb
$y^{u}_{2}$. Since ${z}_{2}\geq 0$, we add $\delta_{2}^{u}$ to $y^{u}_{2}$,
that is, we set ${y^{u}_{2}}=4+1=5$. Thus, with $\mathbf{y}^{u}=(3,5)$, we
calculate $V^{u}=\mathbf{z}\mathbf{y}^{u}=7$. Similar logic will find
$V^{l}=3$.

Suppose $\epsilon=3$. We need to check whether
$V\subseteq[\mathbf{z}\mathbf{y}-\epsilon,\mathbf{z}\mathbf{y}+\epsilon]=[2,8]$.
Since $V=[3,7]$, this condition is satisfied and the input is
$\textsc{bias}_{k,\Delta}$-robust.

######  Theorem 1.

Algorithm 1 computes the upper bound of $V$.

######  Example 4.4.

Figure 1c happens to perturb the data point that causes the maximal positive
prediction for $\mathbf{x}$, i.e., $V^{u}=\$\num{90956}$.

##### Alternate goal: finding the minimum $k$

We may be interested in finding the smallest $k$ such that $\mathbf{x}$ is not
robust to $k$ label perturbations, i.e., the threshold at which $\mathbf{x}$
stops being robust. To find this threshold, we iteratively call Algorithm 1
with $k=1$, while keeping track of $\mathbf{y}^{u}$ and $\rho$ to ensure that
we do not perturb the same label multiple times. We check robustness after
each iteration – as soon as the robustness check fails, we end our search. If
we get to a point where we have perturbed all indices of $\mathbf{y}$, we stop
and conclude that no number of label perturbations will cause non-robustness
for $\mathbf{x}$.

The next theorem discusses the relationship between $\Delta$ and $\epsilon$.
Specifically, we find that the ratio between $\epsilon$ and $\Delta$ uniquely
determines robustness. We make use of this fact in § 6.

######  Theorem 2.

$\mathbf{x}$ is $(\epsilon,\textsc{bias}_{k,\Delta})-$robust iff $\mathbf{x}$
is $(c\epsilon,\textsc{bias}_{k,c\Delta})$-robust for all $c>0$.

##### Classification

Our method is also exact in the binary classification setting (details in
appendix).

##  5 An Approximate Certification Method

In § 4, we described a decision procedure for certifying bias-robustness. For
every input $\mathbf{x}$ for which we want to certify robustness, the
procedure effectively relearns the worst-case linear regression model for
$\mathbf{x}$. In practice, we may want to certify robustness of a large number
of samples, e.g., a whole test dataset, or we may need to perform online
certification. We would like to perform this certification without having to
solve linear regression for every input. The following example provides
intuition for our approach.

######  Example 5.1.

We continue the scenario from Example 4.1. Figure 1d shows the entire range of
linear models obtainable by changing any one data point by $\pm$$10000. Given
a test point $\mathbf{x}$, the range of predictions is the range of the shaded
region at $\mathbf{x}$.

We formalize capturing all 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 }\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})\\}$

To certify robustness of $\mathbf{x}$, we then simply check that every
$\tilde{\theta}\in\Theta$ satisfies
$\tilde{\theta}^{\top}\mathbf{x}\in[\theta^{\top}\mathbf{x}-\epsilon,\theta^{\top}\mathbf{x}+\epsilon]$.

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 an infinite, non-convex set (see Example A.1).
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 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 approximation approach results in an _incomplete_ procedure that abstains
when it cannot prove robustness of an input.

##### Approximation approach

We will iteratively compute component 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{y}^{\prime}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{c}_{i}\mathbf{y}^{\prime},\max_{\mathbf{y}^{\prime}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{c}_{i}\mathbf{y}^{\prime}\right]$

To find
$\min_{\mathbf{y}^{\prime}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{c}_{i}\mathbf{y}^{\prime}$,
we use the same process as in § 4. Specifically, we use Algorithm 1 to compute
the lower and upper bounds of each $\Theta^{a}_{i}$. Returning to Example 5.1,
the dotted red lines in Fig. 1d show $\Theta^{a}$. Notice that this region
overapproximates the exact set of obtainable models, which is shown in solid
green.

The following theorem states that the interval matrix $\Theta^{a}_{i}$ is a
tight overapproximation of the set $\Theta$.

######  Theorem 3.

(i) $\Theta\subseteq\Theta^{a}$. (ii) There does not exist a hyperrectangle
${{\Theta}^{a}}^{\prime}\supseteq\Theta$ where
${{\Theta}^{a}}^{\prime}\subset{\Theta}^{a}$.

##### Evaluating robustness

Given $\Theta^{a}$, as described above, an input $\mathbf{x}$ is
$(\epsilon,\textsc{bias}_{k,\Delta})$-robust if

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

Note that $(\Theta^{a})^{\top}\mathbf{x}$ is computed using standard interval
arithmetic, e.g., $[l,u]+[l^{\prime},u^{\prime}]=[l+l^{\prime},u+u^{\prime}]$.
Also note that the above is a one-sided check: we can only say that
$\mathbf{x}$ is robust, but because $\Theta^{a}$ is an overapproximation, if
Eq. 3 does not hold, we cannot conclusively say that $\mathbf{x}$ is not
robust.

##  6 Experimental Evaluation

We implement both the exact and approximate pointwise certification procedures
in Python. 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.) We find that both techniques are valuable, as
the approximate version – though it loses precision – is much faster when
certifying a large number of data points. Neither approach has a baseline with
which to compare, as ours is the first work to address the bias-robustness
problem in linear regression using exact certification.

##### Description of datasets

We evaluate our approaches for both classification and regression tasks. We
divide each dataset into train (80%), test (10%), and validation (10%) sets,
except when a standard train/test split is provided (i.e., for MNIST 1/7). The
classification datasets are the Income task from the FolkTables project
(training $n=\num{26153}$ – we limited the results to one state to have a
manageable dataset size) [12, 14], the COMPAS dataset ($n=\num{4936}$) [28],
and MNIST 1/7 ($n=\num{13007}$) [19]. We also use the Income dataset for
regression (“Income-Reg") by predicting the exact salary.

We also generate a variety of synthetic datasets to explore what datasets
properties impact bias-robustness. Details about the synthetic data
experiments are available in the appendix.

##### Accuracy-robustness tradeoff

There is a trade-off between accuracy and robustness that is controlled by the
regularization parameter $\lambda$ in the least-squares 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 trade-off.
All results below, unless otherwise stated, use a value of $\lambda$ that
maximizes accuracy.

Figure 2: Fraction of test samples that are certifiably robust for different
values of $\lambda$. The values of $\lambda$ yield accuracies within certain
percentage-point values of the optimal, as described in the legend. The
datasets for each graph are (a) MNIST 1/7, (b) Income, and (c) COMPAS.

##### Experiment goals

Our core objective is to see how robust linear classifiers are to bias in the
training data. We measure this aspect with the _certifiable robustness rate_ ,
that is, the fraction of test points in a dataset that our algorithm can
certify as robust. In § 6.1, we evaluate the exact technique from § 4, and
then in § 6.2, we compare with the approximate approach from § 5. Finally, in
§ 6.3, we show how different dataset and bias function properties impact
overall bias-robustness.

###  6.1 Exact data-bias robustness

Table 1 shows the fraction of test points that are bias-robust for
classification datasets at various levels of label bias. For each dataset, the
robustness rates are relatively high ($>80\%$) when fewer than 0.2% of the
labels are perturbed, and stay above 50% for 1% label bias on COMPAS and MNIST
1/7.

Table 1: Robustness rates (% certifiably robust) for different numbers of label-flips for various classification datasets given different label perturbation amounts. Dataset |  Bias level $k$ 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
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
Income | 91.1 | 81.4 | 67.8 | 58.4 | 50.7 | 37.2 | 23.3 | 12.1 | 4.8 | 1.7 | 0.7
COMPAS | 96.2 | 91.8 | 85.2 | 78.6 | 72.8 | 57.0 | 46.6 | 31.9 | 17.9 | 6.7 | 3.5

Despite globally high robustness rates, we must also consider the non-robust
data points. In particular, we want to emphasize that for Income and COMPAS,
each non-robust point represents an individual whose decision under the model
is vulnerable to attack by changing a small number of labels. Some data points
will 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 data
point is not robust to a small number of label flips, perhaps the model should
not be deployed on that point: instead, the example could be evaluated by a
human or auxiliary model. For some datasets, a nontrivial minority of data
points are not robust at low bias levels, e.g., at just 0.25% label bias,
around 18.6% of Income test points are not robust. This low robustness rate
calls into question the advisability of using a linear classifier on Income
unless one is very confident that label bias is low.

##### Regression dataset results

Table 2 presents results on Income-Reg for the fixed robustness radius
$\epsilon=\$\num{2000}$, 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 bias function (Theorem 2). Notably, for small $\Delta$ to $\epsilon$
ratios, we can certify many test points as robust, even when the number of
perturbed training points is relatively large (up to $10\%$).

Table 2: Certifiable robustness rates for Income-Reg given various $\Delta$ and $k$ values. $\epsilon=\num{2000}$ in all experiments. Note that when $\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. $\Delta$ | Ratio $\frac{\Delta}{\epsilon}$ |  Bias level $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
1000 | 0.5 | 100.0 | 100.0 | 100.0 | 100.0 | 99.8 | 99.4 | 99.1 | 98.6 | 98.0 | 97.1
2000 | 1 | 100.0 | 96.6 | 91.1 | 85.4 | 84.1 | 76.4 | 73.3 | 64.0 | 49.9 | 35.2
4000 | 2 | 91.2 | 84.2 | 69.2 | 35.7 | 14.2 | 2.0 | 0 | 0 | 0 | 0
6000 | 3 | 85.9 | 61.1 | 15.4 | 0 | 0 | 0 | 0 | 0 | 0 | 0
8000 | 4 | 80.1 | 20.0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
10000 | 5 | 69.6 | 3.6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0

###  6.2 Approximate data-bias robustness

As expected, the approximate approach is less precise than the exact one. The
loss in precision depends highly on the dataset and the amount of label bias.
Fig. 3 shows that the precision gap is large for MNIST 1/7, relatively small
for COMPAS and medium for Income. Unlike in the previous section, we use an
accuracy/robustness tradeoff that sacrifices 2% accuracy to gain robustness.

Figure 3: Left to right: Certifiable robustness rates (fraction of the test
set) for the exact and approximate techniques on (a) MNIST 1/7, (b) Income,
and (c) COMPAS. For all examples, $\lambda$ was chosen to obtain results
within 2% of the optimal accuracy.

We also measured the time complexity of the exact and approximate approaches.
To certify 1000 test points of Income, it takes 44.9 seconds for the exact
approach and 6.3 seconds for the approximate approach. For 10000 test points,
it takes 442.5 seconds and 22.0 seconds, respectively. I.e., the exact
approach scales linearly with the number of test points, but the approximate
approach stays within a single order of magnitude. See appendix for more
details and discussion.

###  6.3 Varying dataset properties

We conduct experiments to probe how the size of the demographic subgroup
impacts bias robustness.

##### Balancing demographic groups

We discuss trends in robustness of different racial groups (limited to White
and Black since these are the largest racial groups in the datasets). We
discuss the results from Income below and the results from COMPAS in the
appendix.

The original Income dataset we used only includes the U.S. state of Wisconsin,
which has a majority-White population. Thus, 92.7% of the dataset entries have
race=White, and just 2.6% race=Black. We downloaded other states’ data,
summarized in the appendix. None of these states have racially-balanced data,
however, three of them (Georgia, Louisiana, and Maryland) have more balanced
data, and another (Oregon) is similar to Wisconsin, but with a lower share of
White people.

Figure 4 shows that more race-balanced states have minimal racial robustness
gaps. However, the states where Black people were severely underrepresented in
the data have a large bias-robustness gap between racial groups. We
hypothesize that better demographic representation yields higher robustness,
but future work to establish this connection formally is needed.

Figure 4: Certifiable robustness rate for White people (gray lines) and Black
people (black lines) across 5 different states. GA, LA, and MD have relatively
even demographic distributions; OR and WI have very few Black people. Error
bars show averages across 10 folds.

##### Altering $\Delta$ for unequal demographic groups

In the United States, structural inequity leads to higher salaries for White
people. Our concept of bias functions lets us model this in $\Delta$. We
define _targeting_ on $\phi$ as limiting label perturbations to samples
$\mathbf{x}$ that satisfy $\phi(\mathbf{x})$. Figure 5 shows that for
Wisconsin, targeting on race=Black (i.e., $\delta_{i}=0$ when race is not
Black) greatly increases certifiable-robustness rates for White people, but
barely changes them for Black people. However, in Georgia, targeting on
race=Black significantly increases robustness rates for both groups. For both
states, targeting on race=White is less impactful.

Figure 5: Certifiable robustness rates for White people, Black people, White
people given $\Delta$ targeting (indicated as White(*)), and Black people
given $\Delta$ targeting (Black(*)), for the following states and targeting
scenarios: (a) Georgia, targeted race = Black, (b) Georgia, targeted race =
White, (c) Wisconsin, targeted race = Black, (d) Wisconsin, targeted race =
White.

There are two takeaways: first, as is common sense, if a demographic group is
smaller, there is more uncertainty surrounding that group. E.g., targeting on
race=Black for Wisconsin barely changes the robustness rates for Black people,
but makes the robustness rates for White people very high. Second, when there
is enough data, targeting $\Delta$ based on domain knowledge is promising for
being able to certify a larger fraction of the data, as we see with Georgia.

##  7 Conclusions and broader impacts

We defined the label-bias robustness problem and showed how to certify
pointwise bias-robustness for linear models both exactly and approximately. We
evaluated our approaches on three commonly-used benchmark datasets, showing
that (i) our approaches can certify bias robustness and (ii) there are
commonly gaps in bias-robustness, particularly for smaller demographic groups.
These results merit further study of bias-robustness, and suggest that our
technique may be valuable for ML practitioners wishing to explore limitations
of their models.

##### Limitations

A major limitation of our work is that we use the closed-form least-squares
formula, and not a commonly used surrogate like gradient descent.
Additionally, if any fairness interventions (e.g., weighting the dataset or
forcing behavior such as equal odds) are applied, then our algorithm is not
directly applicable, and the trends we observed may not hold. Future work is
needed for bias-robustness certification for more complex algorithms. The
restriction of data bias to labels is another limitation, since data may be
biased or inaccurate for other reasons - e.g., under-representation of some
groups or poorly transcribed features. We used Income and COMPAS as real-world
examples where bias may have impacted labeling; however, future work should
include domain experts’ input and focus on certifying robustness to a wider
range of bias types.

##### Broader impacts

We hope that bias-robustness certification can help ML practitioners assess
whether the outputs of their models are reliable. Specifically, failure to
achieve certification is a sign that the prediction may have been tainted by
biased data and should not be taken at face value. Given infrequent non-
robustness it may be appropriate to deploy a model and then abstain or defer
to a secondary decision-making process upon encountering a non-robust test
point; widespread non-robustness may necessitate a different modeling
technique, different training data, or both. Clearly, more work is needed to
make this vision a reality, both on the technical side (adapting our approach
for commonly used implementations) and on a sociotechnical scale (deciding how
to proceed when decisions are not robust). Additionally, more work is needed
to understand what realistic bias models look like in different domains, which
is a question that must be addressed by careful thought and reflection of data
collectors and domain experts.

The certification technique that we propose could be leveraged adversarially
to construct minimal label-flipping data poisoning attacks, a possibility we
explore in the appendix. However, we feel that these attacks would not be
high-impact compared with other techniques, since they require full dataset
access and – in their most effective form – target a specific test point.
Another risk of our technique is fairwashing. That is, a bias-robustness
certification may be taken as evidence that a machine learning prediction is
reliable and trustworthy, when in reality, the results are invalid (either due
to a poorly specified bias model, or to extraneous factors like a poorly-
defined machine learning task). It is important that anyone who uses our
certification approach continues to think critically about other potential
failure points.

## References

  * [1] Junaid Ali, Preethi Lahoti and Krishna P. Gummadi  “Accounting for Model Uncertainty in Algorithmic Discrimination”  In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ New York, NY, USA: Association for Computing Machinery, 2021, pp. 336–345  URL: https://doi.org/10.1145/3461702.3462630
  * [2] Lora Aroyo and Chris Welty  “Truth Is a Lie: Crowd Truth and the Seven Myths of Human Annotation”  In _AI Magazine_ 36.1, 2015, pp. 15–24  DOI: 10.1609/aimag.v36i1.2564
  * [3] Aharon Ben-Tal et al.  “Robust Solutions of Optimization Problems Affected by Uncertain Probabilities”  In _Management Science_ 59.2, 2013, pp. 341–357  DOI: 10.1287/mnsc.1120.1641
  * [4] Umang Bhatt et al.  “Uncertainty as a Form of Transparency: Measuring, Communicating, and Using Uncertainty”  In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ New York, NY, USA: Association for Computing Machinery, 2021, pp. 401–413  URL: https://doi.org/10.1145/3461702.3462571
  * [5] Battista Biggio, Blaine Nelson and Pavel Laskov  “Poisoning Attacks against Support Vector Machines”  In _Proceedings of the 29th International Coference on International Conference on Machine Learning_ , ICML’12  Edinburgh, Scotland: Omnipress, 2012, pp. 1467–1474
  * [6] Emily Black and Matt Fredrikson  “Leave-One-out Unfairness”  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , FAccT ’21  Virtual Event, Canada: Association for Computing Machinery, 2021, pp. 285–295  DOI: 10.1145/3442188.3445894
  * [7] Leo Breiman  “Heuristics of instability and stabilization in model selection”  In _The Annals of Statistics_ 24.6 Institute of Mathematical Statistics, 1996, pp. 2350 –2383  DOI: 10.1214/aos/1032181158
  * [8] Alexander D’Amour et al.  “Underspecification Presents Challenges for Credibility in Modern Machine Learning”  arXiv, 2020  DOI: 10.48550/ARXIV.2011.03395
  * [9] L. Devroye and T. Wagner  “Distribution-free performance bounds for potential function rules”  In _IEEE Transactions on Information Theory_ 25.5, 1979, pp. 601–604  DOI: 10.1109/TIT.1979.1056087
  * [10] Ilias Diakonikolas and Daniel M. Kane  “Recent Advances in Algorithmic High-Dimensional Robust Statistics”, 2019  arXiv:1911.05911 [cs.DS]
  * [11] Ilias Diakonikolas et al.  “Robustness meets algorithms”  In _Commun. ACM_ 64.5, 2021, pp. 107–115  DOI: 10.1145/3453935
  * [12] Frances Ding, Moritz Hardt, John Miller and Ludwig Schmidt  “Retiring Adult: New Datasets For Fair Machine Learning”  In _arXiv preprint arXiv:2108.04884_ , 2021
  * [13] Aaron Fisher, Cynthia Rudin and Francesca Dominici  “All Models are Wrong, but Many are Useful: Learning a Variable’s Importance by Studying an Entire Class of Prediction Models Simultaneously”  In _Journal of Machine Learning Research_ 20.177, 2019, pp. 1–81  URL: http://jmlr.org/papers/v20/18-760.html
  * [14] Sarah Flood et al.  “Integrated Public Use Microdata Series, Current Population Survey: Version 8.0 [dataset]”, 2020  DOI: https://doi.org/10.18128/D030.V8.0
  * [15] Christoph Hube, Besnik Fetahu and Ujwal Gadiraju  “Understanding and Mitigating Worker Biases in the Crowdsourced Collection of Subjective Judgments”  In _Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems_ , CHI ’19  Glasgow, Scotland Uk: Association for Computing Machinery, 2019, pp. 1–12  DOI: 10.1145/3290605.3300637
  * [16] Matthew Jagielski et al.  “Manipulating Machine Learning: Poisoning Attacks and Countermeasures for Regression Learning”  In _2018 IEEE Symposium on Security and Privacy (SP)_ , 2018, pp. 19–35  DOI: 10.1109/SP.2018.00057
  * [17] Jinyuan Jia, Xiaoyu Cao and Neil Zhenqiang Gong  “Intrinsic Certified Robustness of Bagging against Data Poisoning Attacks”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 35.9, 2021, pp. 7961–7969  URL: https://ojs.aaai.org/index.php/AAAI/article/view/16971
  * [18] Michael Kearns and Dana Ron  “Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation”  In _Neural Computation_ 11.6, 1999, pp. 1427–1453  DOI: 10.1162/089976699300016304
  * [19] Yann LeCun, Corinna Cortes and Christopher J. C. Burges  “The MNIST Database of handwritten digits”, [n.d.]  URL: http://yann.lecun.com/exdb/mnist/
  * [20] Charles Marx, Flavio Calmon and Berk Ustun  “Predictive Multiplicity in Classification”  In _Proceedings of the 37th International Conference on Machine Learning_ 119, Proceedings of Machine Learning Research  PMLR, 2020, pp. 6765–6774  URL: https://proceedings.mlr.press/v119/marx20a.html
  * [21] Anna P. Meyer, Aws Albarghouthi and Loris D’ Antoni  “Certifying Robustness to Programmable Data Bias in Decision Trees”  In _Advances in Neural Information Processing Systems_ 34 Curran Associates, Inc., 2021, pp. 26276–26288  URL: https://proceedings.neurips.cc/paper/2021/file/dcf531edc9b229acfe0f4b87e1e278dd-Paper.pdf
  * [22] Nicolas Müller, Daniel Kowatsch and Konstantin Böttinger  “Data Poisoning Attacks on Regression Learning and Corresponding Defenses”  In _2020 IEEE 25th Pacific Rim International Symposium on Dependable Computing (PRDC)_ , 2020, pp. 80–89  DOI: 10.1109/PRDC50213.2020.00019
  * [23] Hongseok Namkoong and John C Duchi  “Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences”  In _Advances in Neural Information Processing Systems_ 29 Curran Associates, Inc., 2016  URL: https://proceedings.neurips.cc/paper/2016/file/4588e674d3f0faf985047d4c3f13ed0d-Paper.pdf
  * [24] Nagarajan Natarajan, Inderjit S Dhillon, Pradeep K Ravikumar and Ambuj Tewari  “Learning with Noisy Labels”  In _Advances in Neural Information Processing Systems_ 26 Curran Associates, Inc., 2013  URL: https://proceedings.neurips.cc/paper/2013/file/3871bd64012152bfb53fdf04b401193f-Paper.pdf
  * [25] Giorgio Patrini et al.  “Making Deep Neural Networks Robust to Label Noise: A Loss Correction Approach”  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017, pp. 2233–2241  DOI: 10.1109/CVPR.2017.240
  * [26] Andrea Paudice, Luis Muñoz-González and Emil C. Lupu  “Label Sanitization Against Label Flipping Poisoning Attacks”  In _ECML PKDD 2018 Workshops_ Cham: Springer International Publishing, 2019, pp. 5–15
  * [27] Amandalynne Paullada et al.  “Data and its (dis)contents: A survey of dataset development and use in machine learning research”  In _Patterns_ 2 Cell Press, 2021  DOI: 10.1016/j.patter.2021.100336
  * [28] Propublica  “Propublica Compas Analysis”  URL: https://github.com/propublica/compas-analysis
  * [29] David Rolnick, Andreas Veit, Serge J. Belongie and Nir Shavit  “Deep Learning is Robust to Massive Label Noise”  In _CoRR_ abs/1705.10694, 2017  arXiv: http://arxiv.org/abs/1705.10694
  * [30] Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar and Zico Kolter  “Certified Robustness to Label-Flipping Attacks via Randomized Smoothing”  In _Proceedings of the 37th International Conference on Machine Learning_ 119, Proceedings of Machine Learning Research  PMLR, 2020, pp. 8230–8241  URL: http://proceedings.mlr.press/v119/rosenfeld20b.html
  * [31] Shilad Sen et al.  “Turkers, Scholars, "Arafat" and "Peace": Cultural Communities and Algorithmic Gold Standards”  In _Proceedings of the 18th ACM Conference on Computer Supported Cooperative Work & Social Computing_, CSCW ’15  Vancouver, BC, Canada: Association for Computing Machinery, 2015, pp. 826–838  DOI: 10.1145/2675133.2675285
  * [32] Ali Shafahi et al.  “Poison Frogs! Targeted Clean-Label Poisoning Attacks on Neural Networks”  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18  Montréal, Canada: Curran Associates Inc., 2018, pp. 6106–6116
  * [33] Soroosh Shafieezadeh-Abadeh, Peyman Mohajerin Esfahani and Daniel Kuhn  “Distributionally Robust Logistic Regression”  In _Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1_ , NIPS’15  Montreal, Canada: MIT Press, 2015, pp. 1576–1584
  * [34] Jacob Steinhardt, Pang Wei Koh and Percy Liang  “Certified Defenses for Data Poisoning Attacks”  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17  Long Beach, California, USA: Curran Associates Inc., 2017, pp. 3520–3532
  * [35] Richard Tomsett et al.  “Rapid Trust Calibration through Interpretable and Uncertainty-Aware AI”  In _Patterns_ 1.4 Elsevier, 2020  DOI: 10.1016/j.patter.2020.100049
  * [36] Dimitris Tsipras et al.  “From ImageNet to Image Classification: Contextualizing Progress on Benchmarks”  In _Proceedings of the 37th International Conference on Machine Learning_ 119, Proceedings of Machine Learning Research  PMLR, 2020, pp. 9625–9635  URL: https://proceedings.mlr.press/v119/tsipras20a.html
  * [37] Han Xiao, Huang Xiao and Claudia Eckert  “Adversarial Label Flips Attack on Support Vector Machines”  In _Proceedings of the 20th European Conference on Artificial Intelligence_ , ECAI’12  Montpellier, France: IOS Press, 2012, pp. 870–875
  * [38] Chiyuan Zhang et al.  “Understanding Deep Learning (Still) Requires Rethinking Generalization”  In _Commun. ACM_ 64.3 New York, NY, USA: Association for Computing Machinery, 2021, pp. 107–115  DOI: 10.1145/3446776
  * [39] Xuezhou Zhang, Xiaojin Zhu and Stephen Wright  “Training Set Debugging Using Trusted Items”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 32.1, 2018  URL: https://ojs.aaai.org/index.php/AAAI/article/view/11610

##  Appendix A Additional details from sections 3-5

##### Exact approach in the binary case

As discussed in § 4, the exact approach is sound and precise in the binary 0/1
case. Even though we technically allow perturbed labels to take on any real
value in [0,1], in practice, all labels will remain either 0 or 1 due to the
linearity of maximal perturbations.

##### Computing $\Theta$

We walk through an example of computing $\Theta$ directly. Recall that
$\mathbf{C}=(\mathbf{X}^{\top}\mathbf{X})^{-1}\mathbf{X}^{\top}$.

######  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.

##  Appendix B Complete algorithms

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

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

Algorithm 2 Solve Eq. 2 by finding a perturbation of $\mathbf{y}$ that
maximally increases $\mathbf{z}\mathbf{y}$ and then a perturbation of
$\mathbf{y}$ that maximally decreases $\mathbf{z}\mathbf{y}$

$\mathbf{z}\in\mathbb{R}^{n},\mathbf{y}\in\mathbb{R}^{n},\Delta\in\mathbb{IR}^{n}$
with $0\in\Delta$, $k\geq 0$

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

if $z_{i}\geq 0$ then

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

else

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

Let $\rho^{+}_{i_{1}},\ldots,\rho^{+}_{i_{l}}$ be the $k$ 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}$

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

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

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

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

else

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

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

We also present the complete algorithm for the approximate approach in
Algorithm 3.

Algorithm 3 Computing $\Theta^{a}$

$\mathbf{C}\in\mathbb{R}^{m\times
n},\mathbf{y}\in\mathbb{R}^{n},\Delta\in\mathbb{IR}^{n}$ with $0\in\Delta$,
$k\geq 0$

$\ \Theta^{a}\leftarrow[0,0]^{m}$

for $i$ in range $m$ do:

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

if $c_{ij}<0$ then

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

else

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

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

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

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

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

else

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

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

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

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

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

else

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

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

##  Appendix C Omitted proofs

Proof of Lemma 1

###### Proof.

(Contradiction) Suppose
$\mathbf{z}\tilde{\mathbf{y}}\notin[\hat{y}-\epsilon,\hat{y}+\epsilon]$. Then,
without loss of generality, there is some
$\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}$ such that
$\mathbf{z}\tilde{\mathbf{y}}>\hat{y}+\epsilon$. Thus, we can modify the
prediction of $\mathbf{x}$ by more than $\epsilon$ given $\Delta$-allowable
label perturbations, so $\mathbf{x}$ is not
$(\epsilon,\textsc{bias}_{k,\Delta})$-robust. ∎

Proof of Lemma 2

###### Proof.

Let
$V=[\min_{\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{z}\tilde{\mathbf{y}},\max_{\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{z}\tilde{\mathbf{y}}]$.
Then if $V^{u}>\mathbf{z}\mathbf{y}+\epsilon$, by Lemma 1, $\mathbf{x}$ is not
$(\epsilon,\textsc{bias}_{k,\Delta}$-robust. A similar argument holds for
$V^{l}$.

Suppose $\mathbf{x}$ is $(\epsilon,\textsc{bias}_{k,\Delta}$-robust. Then
there is no $\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})$ with
$\mathbf{z}\tilde{\mathbf{y}}>\mathbf{z}\mathbf{y}+\epsilon$. Thus
$\max_{\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{z}\tilde{\mathbf{y}}=V^{u}\leqslant\mathbf{z}\mathbf{y}+\epsilon$.
A similar argument holds for $\mathbf{z}\mathbf{y}-\epsilon$ and $V^{l}$. ∎

Proof of Theorem 1

###### Proof.

Our goal is to show that $V^{u}$, the output of Algorithm 1, satisfies
$V^{u}=\max_{\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{z}\tilde{\mathbf{y}}$.

Suppose that there is a label perturbation that we did not make that would
have perturbed $\mathbf{z}\mathbf{y}^{u}$ more. That is, for some label
perturbation $y_{i_{j}}^{u}=y_{i_{j}}^{u}+\delta_{i_{j}}^{u}$, there was a
different label $y_{m}$, with $m\notin\\{i_{1},\cdots,i_{k}\\}$ with
$\mathbf{z}_{m}\delta_{m}^{u}>\mathbf{z}_{i_{j}}\delta_{i_{j}}^{u}$. But then
$m$ would have been in $\\{i_{1},\cdots,i_{k}\\}$. So this is not possible,
thus, $\mathbf{y}^{u}$ satisfies
$\operatorname*{argmax}_{\tilde{\mathbf{y}}\in\textsc{bias}_{k,\Delta}(\mathbf{y})}\mathbf{z}\tilde{\mathbf{y}}$,
and $V^{u}=\mathbf{z}\mathbf{y}^{u}$. ∎

Proof of Theorem 2

###### Proof.

Suppose $\mathbf{x}$ is $(\epsilon,\textsc{bias}_{k,\Delta})-$robust. Consider
$\mathbf{y}^{\prime}\in\textsc{bias}_{k,\Delta}(\mathbf{y})$, supposing that
labels $y^{\prime}_{i_{1}},\ldots,y^{\prime}_{i_{l}}$ were perturbed by
$d_{i_{1}},\ldots,d_{i_{l}}$ from $\mathbf{y}$. Note that
$d_{i_{j}}\in\delta_{i_{j}}$, and that
$\mathbf{z}\mathbf{y}\in[\mathbf{z}\mathbf{y}-\epsilon,\mathbf{z}\mathbf{y}+\epsilon]$.
But we can write
$\mathbf{z}\mathbf{y}^{\prime}=\mathbf{z}\mathbf{y}+z_{i_{1}}y^{\prime}_{i_{1}}+\cdots+z_{i_{l}}y^{\prime}_{i_{l}}$.
Thus,
$z_{i_{1}}y^{\prime}_{i_{1}}+\cdots+z_{i_{l}}y^{\prime}_{i_{l}}\in[-\epsilon,\epsilon]$.
If we instead create $\mathbf{y}^{\prime\prime}$ by perturbing the labels
$i_{1},\ldots,i_{l}$ of $\mathbf{y}$ by $cd_{i_{1}},\ldots,cd_{i_{l}}$ to
satisfy $\mathbf{y}^{\prime\prime}\in\textsc{bias}_{k,c\Delta}(\mathbf{y})$,
we will have
$\mathbf{z}\mathbf{y}^{\prime\prime}\in[\mathbf{z}\mathbf{y}-c\epsilon,\mathbf{z}\mathbf{y}+c\epsilon]$.
∎

Proof of Theorem 3

###### Proof.

(i) Consider $\theta^{*}\in\Theta$. Then,
$\theta^{*}=\mathbf{C}\mathbf{y}^{*}$ for some
$\mathbf{y}^{*}\in\textsc{bias}(\mathbf{y})$. Consider coordinate $i$ of
$\theta^{*}$. We have $\theta^{*}_{i}\in\Theta^{a}$ because the lower bound of
$\theta^{a}$ was chosen to be
$\min_{\mathbf{y}^{\prime}\in\textsc{bias}(\mathbf{y})}\mathbf{C}_{i}\mathbf{y}^{\prime}$.
Similarly, the upper bound of $\theta^{*}$ was chosen to be
$\max_{\mathbf{y}^{\prime}\in\textsc{bias}\mathbf{y}}(\mathbf{C}_{i}\mathbf{y}^{\prime})$.
Therefore, $\theta^{*}_{i}=\mathbf{C}_{i}\mathbf{y}^{*}\in\Theta^{a}_{i}$.

(ii) Suppose there is another box ${{\Theta}^{a}}^{\prime}$ with
${{\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{y}^{\prime}\in\textsc{bias}(\mathbf{y})}(\mathbf{z}_{i}\mathbf{y}^{\prime})$,
which means that
$\mathbf{y}^{*}=\max_{\mathbf{y}^{\prime}\in\textsc{bias}(\mathbf{y})}\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$. ∎

##  Appendix D Additional experimental results

###  D.1 More details on the robustness-accuracy tradeoff

Fig. 6 shows the robustness for MNIST 1/7, Income, and COMPAS at four
different accuracy levels. For the most-accurate version (column 1), we see
that the over-approximate certifiable robustness rates are very low,
especially for MNIST 1/7, where we cannot certify anything. As the accuracy
level drops, the amount we can certify grows for both the exact and
approximate approaches, but this trend is more pronounced for the approximate
certification. Table 3 shows the same information numerically.

Figure 6: Each graph shows the certifiable robustness rates for the exact (black lines) and approximate (gray lines) approachces for various amount of label-bias (x-axis). Each row corresponds to a different dataset (1: MNIST 1/7, 2: Income, 3: COMPAS) and each column corresponds to a different accuracy degradation measure, e.g., column 1 corresponds to the maximally-accurate model, column 2 to a model within 0.5% accuracy of the optimal model, and so on. The error bars show the range across 10 folds, apart from MNIST, where we used the standard provided train/test split. Table 3: Robustness rates for different numbers of label-flips for various classification datasets. Each entry is the percentage of test-set elements that are certifiably robust against any training-data set perturbation involving up to a the specified percentage of labels. Dataset | Accuracy | Bias level as a percentage of training dataset size
---|---|---
loss | 0.25 | 0.5 | 1.0 | 2.0 | 3.0 | 4.0 | 5.0 | 6.0 | 7.0 | 8.0
MNIST 1/7 | 0 | 96.3 | 93.1 | 84.4 | 60.8 | 38.8 | 23.3 | 13.1 | 7.0 | 2.4 | 0.4
0.2 | 96.7 | 93.6 | 85.8 | 63.2 | 42.5 | 27.0 | 16.1 | 9.7 | 4.6 | 1.1
0.5 | 97.7 | 95.3 | 90.8 | 79.1 | 64.1 | 49.1 | 37.2 | 27.1 | 21.0 | 15.5
1.0 | 98.5 | 97.3 | 94.6 | 89.8 | 84.8 | 78.0 | 69.5 | 60.8 | 51.7 | 44.9
1.5 | 99.2 | 98.1 | 96.2 | 93.6 | 90.7 | 88.2 | 84.7 | 80.2 | 76.1 | 71.1
2.0 | 99.2 | 98.6 | 96.9 | 94.1 | 92.0 | 89.4 | 87.0 | 83.1 | 79.6 | 76.2
Income | 0 | 81.4 | 67.8 | 50.7 | 23.3 | 12.1 | 4.8 | 1.7 | 0.7 | 0 | 0
0.2 | 83.5 | 71.4 | 54.7 | 27.6 | 12.9 | 6.2 | 2.0 | 1.3 | 0 | 0
0.5 | 87.6 | 75.6 | 59.3 | 36.0 | 17.5 | 9.2 | 3.6 | 1.6 | 1.1 | 0
1.0 | 94.1 | 86.7 | 70.6 | 51.4 | 35.9 | 24.0 | 16.9 | 9.5 | 6.0 | 2.9
1.5 | 94.1 | 89.3 | 78.4 | 57.6 | 43.2 | 32.5 | 24.0 | 16.4 | 10.9 | 7.3
2.0 | 94.2 | 89.6 | 81.0 | 58.9 | 45.7 | 34.4 | 25.7 | 18.5 | 11.7 | 9.0
COMPAS | 0 | 91.8 | 85.2 | 72.8 | 46.6 | 31.9 | 17.9 | 6.7 | 0.4 | 0 | 0
0.2 | 92.1 | 85.4 | 73.6 | 46.9 | 32.5 | 18.5 | 7.3 | 0.3 | 0 | 0
0.5 | 93.7 | 86.2 | 74.3 | 51.7 | 37.8 | 26.0 | 14.4 | 4.2 | 0 | 0
1.0 | 94.7 | 88.5 | 74.3 | 56.7 | 42.5 | 27.1 | 19.1 | 10.8 | 0.8 | 0
1.5 | 95.7 | 89.8 | 73.1 | 58.1 | 43.9 | 30.5 | 20.7 | 13.4 | 3.4 | . 0
2.0 | 94.5 | 89.4 | 76.4 | 61.1 | 48.3 | 37.0 | 30.3 | 19.5 | 13.5 | 3.7

###  D.2 Description of synthetic data

We created datasets of size 200, 500, or 1000, with 3, 4 or 5 normally
distributed features. Feature 1 was $\mathcal{N}(0.5,1)$ for class 1 and
$\mathcal{N}(-0.5,1)$ for class 2. Feature 2 was $\mathcal{N}(1,1)$ for both
classes. Feature 3 was $\mathcal{N}(-0.5,1)$ and $\mathcal{N}(0.5,1)$ for
classes 0 and 1, respectively, feature 4 was $\mathcal{N}(1,1)$ and
$\mathcal{N}(-1,1)$ for the two classes, and feature 5 was $\mathcal{N}(0,1)$
for both classes.

##### Demographics data

We used 4 different distributions to generate data in $\mathbb{R}^{2}$ for the
majority group with label 1, on the minority group with label 1, in the
majority group with label 0, and the minority group with label 0. Details of
distribution means and covariances are available in our code repository.

###  D.3 Synthetic dataset results

Compared with the real-world datasets, the synthetic datasets could withstand
much higher rates of label-flipping bias while maintaining robustness. We
hypothesize that this is because the synthetic datasets are much ‘easier’ in
general, as they lack real-world noise and obey a linearly-separable data
distribution, which is not always true of real-world data.

We performed two types of experiments with synthetic data. The first probes
how the number of features and dataset size impact robustness, while the
second investigates how robust different simulated demographic groups are
relative to subgroup representation. These results validate our experimental
approach because the results are very intuitive. Namely, there was higher
robustness when the datasets were larger and when there were fewer features,
as is true in ML more broadly.

We first discuss the impact of general data properties, and then turn our
attention to the demographics-based experiments.

####  D.3.1 Dataset properties

We found that the dataset size and the number of features both impact label-
bias robustness.

##### Dataset size

When there are just three features, the dataset size does not significantly
impact robustness. However, the addition of a fourth, and especially a fifth,
feature leads to a positive correlation between the size of the dataset and
label-bias robustness, as summarized in Table 4. We hypothesize that the size
of the dataset matters less given fewer features because it takes less data to
be confident in the predictor and to attain a certain level of stability with
fewer features, that is, fewer potential confounders.

##### Number of features

Adding additional features reduces robustness, as shown in Table 4.

Table 4: Robustness rates for synthetic datasets of different sizes and number of features. Dataset size | Number of features | Bias level as a % of training dataset size
---|---|---
4 | 8 | 12 | 16 | 20
200 | 3 | 83.8 | 75.5 | 69.8 | 66.8 | 65.0
500 | 3 | 83.7 | 75.2 | 70.3 | 68.0 | 67.0
1000 | 3 | 84.0 | 75.5 | 69.6 | 68.1 | 67.0
200 | 4 | 81.5 | 71.3 | 64.0 | 61.3 | 61.0
500 | 4 | 81.7 | 70.5 | 65.3 | 63.3 | 61.6
1000 | 4 | 82.9 | 71.9 | 66.1 | 63.3 | 62.6
200 | 5 | 78.0 | 66.5 | 59.8 | 56.8 | 56.0
500 | 5 | 79.5 | 69.1 | 60.6 | 57.2 | 56.8
1000 | 5 | 79.9 | 67.6 | 62.2 | 59.5 | 58.5

##### Results for approximate robustness

Approximate robustness behaves similarly upon perturbing the dataset size and
is very sensitive to the number of features. We can certify higher label-bias
robustness when there are fewer features, and this trend holds not only in
absolute terms but also relative to exact certification. For example, given
10% label bias, when there are three features, we can certify 79.1% of the
samples as robust using the exact procedure and 60.2% as robust using the
approximate version – an 18.9% gap. For four and five features, we can certify
76.4% and 74.7%, respectively, of samples exactly, and 45.5% and 31.7% using
the approximate technique, leading to certification gaps of 30.9% for four
features and 43% for five features.

This trend can also be directly inferred from the algorithm: because we bound
each coordinate of $\Theta$ (i.e., the coefficient for each coordinate)
individually, a larger number of features will inherently lead to less robust
bounds.

####  D.3.2 Demographic experiments

We found that subgroup representation (i.e., the size of the demographic
minority) was very influential for label-bias robustness.

##### Subgroup representation

As shown in Fig. 7, when the minority demographic group forms a smaller
percent of the total population, that demographic group is less robust. By
contrast, the majority group sees only slightly higher robustness rates when
its majority is larger.

Figure 7: Robustness for minority group (left) and majority group (right) for
different data distributions.  Figure 8: Robustness with error bars for the
majority group and minority group for 10% minority group representation
(left), 25% (middle), and 50% (right). Error bars are over 4 folds.

Additionally, as shown in Fig. 8, we found that robustness rates for the
minority group are much more variable across folds when the minority group is
smaller. We hypothesize that this trend is related to the size of the dataset;
that is, when the minority group is very small, we suspect that there is just
not enough data to make generalizable conclusions.

###  D.4 Dataset variation experiments

##### Altering the dataset size

We repeated the Income and COMPAS experiments on random subsets of 20-80% of
the original data. For Income, the robustness rates are indistinguishable
across all dataset sizes. However, for COMPAS, larger dataset sizes yield
higher robustness, e.g., given 0.5% label bias, we can certify 81.5% of test
points as robust on the full dataset but only 49.8% on the 20%-size dataset.
We suspect that Income is similarly robust at different sizes because it is
much larger: even the smallest subset, containing 20% of the full dataset, is
larger than all of COMPAS.

##### COMPAS demographics

The version of the COMPAS dataset that we use has the racial breakdown of
34.2% White, 51.4% Black, 8.2% Hispanic, and 6.2% other. Analysis of our
results from § 6.1 show that the robustness rates between White and Black
defendants diverge significantly for moderate (>1.5%) label-bias, as shown in
Table 5.

Table 5: Robustness rates by race, COMPAS. | Bias level 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
Black | 96.9 | 92.7 | 86.5 | 81.2 | 71.9 | 49.5 | 40.3 | 28.9 | 11.8 | 1.3 | 0.7
White | 93.7 | 88.9 | 83.1 | 74.8 | 73.0 | 66.9 | 56.6 | 37.0 | 30.4 | 17.7 | 0.0

We tried balancing the dataset demographically by selecting a subset of the
data that was 50% White people and 50% Black people. This re-balancing
increases the robustness of the previously less-represented group (i.e., White
people) while having no impact on the average robustness for Black people.
Clearly, demographic representation is not sufficient for equal robustness
rates. We leave a further exploration of what properties of population
subgroups impact robustness for future work, and note that domain knowledge is
likely to be important in making these discoveries.

##### Income demographics

Table 6 shows the demographic make-up of various states’ data from the Income
dataset.

Table 6: 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

###  D.5 Running time

Table 7 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.

Table 7: Running time 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 200 labels (which is enough to bring the robustness to 0%). Dataset |  100 samples |  1000 samples |  10000 samples
---|---|---|---
Exact | Approx. | Exact | Approx. | Exact | Approx.
Income | 5.25 | 4.79 | 44.90 | 6.33 | 442.47 | 22.02
Compas | 1.07 | 2.32 | 6.49 | 2.44 | 51.04 | 10.90
MNIST 1/7 | 4.05 | 3.83 | 24.78 | 5.99 | 448.50 | 24.33

###  D.6 Connection to attacks

As linear regression is often not used in practice for classification
datasets, we were interested in seeing whether our approach could identify
effective label-bias attacks that generalize to other machine learning
algorithms, e.g., logistic regression.

We targeted 100 samples in each Income and MNIST 1/7. We performed six
different attacks: one was the minimal attack needed to change the sample’s
binary prediction, and the others flipped a fixed percentage (1%, 2%, 3%, 4%
or 5%) of the test samples.

The results are summarized in Table 8. Notably, if we target MNIST 1/7 test
samples and are allowed to flip at least 4% of the labels, the attack will
carry over to logistic regression over 90% of the time. The attacks were not
as effective on Income.

Table 8: Each entry shows the percentage of test samples for which the attack generated by our method, flipping the specified amount of training labels, changed the classification. For example, the minimal perturbation needed to change a sample’s classification under our approach resulted in a classification change for out-of-the-box logistic regression 4% of the time.  | minimal | 1% | 2% | 3% | 4% | 5%
---|---|---|---|---|---|---
Income | 4 | 3 | 5 | 5 | 5 | 5
MNIST 1/7 | 18 | 36 | 71 | 84 | 94 | 98