# Fairness Reprogramming

Guanhua Zhang
UC Santa Barbara
<EMAIL_ADDRESS>
&Yihua Zhang11footnotemark: 1
Michigan State University
<EMAIL_ADDRESS>
&Yang Zhang
MIT-IBM Watson AI Lab
<EMAIL_ADDRESS>
&Wenqi Fan
The Hong Kong Polytechnic University
<EMAIL_ADDRESS>
&Qing Li
The Hong Kong Polytechnic University
<EMAIL_ADDRESS>
&Sijia Liu
Michigan State University & MIT-IBM Watson AI Lab
<EMAIL_ADDRESS>
&Shiyu Chang
UC Santa Barbara
<EMAIL_ADDRESS>
Equal contribution

###### Abstract

Despite a surge of recent advances in promoting machine Learning (ML)
fairness, the existing mainstream approaches mostly require retraining or
finetuning the entire weights of the neural network to meet the fairness
criteria. However, this is often infeasible in practice for those large-scale
trained models due to large computational and storage costs, low data
efficiency, and model privacy issues. In this paper, we propose a new generic
fairness learning paradigm, called FairReprogram, which incorporates the model
reprogramming technique. Specifically, FairReprogram considers the case where
models can not be changed and appends to the input a set of perturbations,
called the fairness trigger, which is tuned towards the fairness criteria
under a min-max formulation. We further introduce an information-theoretic
framework that explains why and under what conditions fairness goals can be
achieved using the fairness trigger. We show both theoretically and
empirically that the fairness trigger can effectively obscure demographic
biases in the output prediction of fixed ML models by providing false
demographic information that hinders the model from utilizing the correct
demographic information to make the prediction. Extensive experiments on both
NLP and CV datasets demonstrate that our method can achieve better fairness
improvements than retraining-based methods with far less data dependency under
two widely-used fairness criteria. Codes are available at
https://github.com/UCSB-NLP-Chang/Fairness-Reprogramming.git.

##  1 Introduction

Fairness in machine learning (ML) has become a critical concern. Due to the
biases in data collection, the output prediction is often spuriously
correlated with some demographic attributes, which are thus undesirably
incorporated into the decision-making process of machine learning models. For
example, it is found that some abusive language detection systems tend to
classify texts that contain mere mentioning of certain minority groups,
_e.g.,_ homosexual groups, as abusive content, even though the texts
themselves are not abusive at all [1, 2]. Despite the recent advances in
fairness promoting learning methods [3, 4, 5, 6, 7], the existing
mainstreaming approaches mostly require retraining or finetuning the entire
model parameters towards an extra fairness objective. However, this is often
infeasible in practice, particularly for those well-trained large-scale
models, due to the huge computation and storage costs. In addition, for
machine learning models that are deployed as a service, model retraining is
hindered by limited access to the model parameters.

Recently, model reprogramming has emerged as an alternative technique to model
finetuning. In particular, model reprogramming considers the pre-trained model
fixed, and instead modifies their input to re-purpose the model towards
different objectives. For example, it is shown that a well-crafted input
perturbation can re-program an ImageNet classifier to solve the task of
counting squares in an image [8, 9]. It is also shown that by learning task-
specific embedding prompts concatenated to the inputs, pre-trained language
models can achieve better performances than full-parameter tuning in natural
language understanding tasks [10, 11, 12] Compared with finetuning methods,
model reprogramming enjoys lower cost, better scalability, and requires less
access to the model parameters. Hence here come our research questions - _Can
model reprogramming techniques be applied to fairness objectives? If so, why
and how would it work?_

In this paper, we revisit the model reprogramming and propose a novel generic
fairness learning paradigm, called FairReprogram. In particular, FairReprogram
perturbs the input by appending to the input a global constant vector/feature,
called the _fairness trigger_ , which is optimized towards the fairness
objective under a min-max framework. FairReprogram is a generic framework that
works for various tasks and domains. We further introduce an information-
theoretic framework that explains why and under what conditions fairness goals
can be achieved using a constant fairness trigger. We show theoretically and
empirically that the fairness trigger can effectively obscure demographic
biases in the output prediction of fixed ML models by providing false
demographic information that hinders the model from utilizing the correct
demographic information to make predictions.

We perform extensive experiments across various NLP and CV datasets with in-
the-wild biases. The results show that FairReprogram can consistently achieve
better fairness improvement with the retraining-based methods under the two
widely-used fairness notions, but with far less trade-off in accuracy. For
example, with comparable accuracy, our method can outperform the retraining
based baseline with 10.5% and 36.5% lower bias scores over two fairness
criteria in the CelebA dataset with the hair color prediction task and gender
as demographic information. In addition, our method demonstrates great
transferability and interpretability. Our theoretical analysis and empirical
findings can provide useful insights toward more practical, scalable, and
flexible fairness learning paradigms.

##  2 Related Work

#### Fairness in ML

Fairness problems in ML models have received increasing attention from both
industry [13] and academia [14, 15, 16, 17]. There has been a myriad of
fairness definitions in the literature [18, 14, 19, 20]. Among them, group
fairness notions are one of the most popular [21, 22, 23], which require ML
models to perform similarly for different demographic groups. In this paper,
we mainly focus on the two most widely-used group fairness definitions,
demographic parity [21] and equalized odds [22], but it is worth mentioning
that our method is general for other fairness notions. Existing fairness
promoting methods can be broadly categorized into pre-processing, in-
processing, and post-processing methods [24]. Pre-processing methods calibrate
the training data to remove the spurious correlations and train fair model on
the modified data [25, 26, 27, 28, 2, 1, 29, 30]. In-processing methods work
on training ML with extra fairness-aware regularization [3, 4, 5, 6, 7, 31,
32]. For example, an adversarial framework is introduced to train model
parameters to meet fairness requirements [33]. In our method, we adopt a
similar adversarial loss but optimize the fairness triggers with a fixed
model. Despite the effectiveness, these methods usually consider training fair
models from scratch and do not directly apply to already-trained models. Post-
processing methods focus on calibrating trained ML models to be fair [24].
Many of them modify the model outputs to meet the fairness criteria [18, 22,
34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44]. For example, the model outputs
are directly modified to meet equalized odds by solving an optimization
problem [22]. Alternatively, a boosting-based method is introduced to
calibrate model outputs [40].

#### Model reprogramming

Model reprogramming [45, 9, 8, 46, 47, 48] aims to repurpose an already
trained neural network for different tasks. Different from the typical
transfer learning that requires modifying the structure and parameters of the
given pre-trained model, reprogramming technology instead designs a trainable
program appended to the input, while keeping the pre-trained model intact. The
model reprogramming technology can be designed in the form of an input-
agnostic perturbation [45, 8] or a trainable input transformation function
together with the label mapping from the source domain to the target domain
[9]. In particular, the feasibility of designing a universal input
perturbation to reprogram a well-trained ImageNet classifier to the CIFAR-10
dataset is demonstrated in the white-box setting [8]. As an exploration to
implement reprogramming in the discrete scenario, another work [46]
successfully reprograms the text classification neural network for alternate
classification tasks. This work also shows the possibility of developing
reprogramming in the black-box setting, where the reprogrammer may not have
the access to the parameters of the target model. Recent work [47] shows the
possibility of repurposing deep neural networks designed for image classifiers
for the natural language processing and other sequence classification tasks.
It is argued the success of the reprogramming lies in the size of the average
input gradient and the input dimension is crucial to the performance of the
reprogrammer [48]. It is also shown that generative models like FairGANs [49]
can be transfered to other tasks by reprogramming with variational auto-
encoders [50]. A highly related topic to model reprograming is prompt learning
in NLP [11]. It is shown that by designing designated text prompts appended to
inputs, pre-trained language models could be re-directed to perform well under
downstream tasks in a few-shot setting [51]. Prompt-based tuning methods have
become the mainstream and achieve better performance than fine-tuning in many
scenarios [52, 53, 54, 55]. Seminal works about prompt learning can be found
in [11, 12]. However, nearly all existing methods focus on using model
reprogramming to improve accuracy in domain-transfer tasks and to our best
knowledge, our work is the first to generalize model reprogramming to improve
fairness of a trained model.

##  3 Fairness Reprogramming

In this section, we will introduce the FairReprogram algorithms. As some
notations, upper-cased letters, $\bm{X}$ and $X$, denote random vectors and
random variables, respectively; lower-cased letters, $\bm{x}$ or $x$, denote
deterministic vectors and scalars respectively. $p_{\bm{X}}(\cdot)$ or
$p(\bm{X})$ denote the probability density function of the (discrete) random
variable $\bm{X}$.

###  3.1 Problem Formulation

Consider a classification task, where $\bm{X}$ represents the input feature,
and $Y$ represents the output label. In addition, there exists some sensitive
attributes or demographic group, $Z$, that may be spuriously correlated with
$Y$. There is a pre-trained classifier, $f^{*}(\cdot)$, that predicts $Y$ from
$\bm{X}$, _i.e._ $\hat{Y}=f^{*}(\bm{X})$. The weights of the classifier are
considered fixed (hence the superscript $*$). Unfortunately, due to the
spurious correlation between $Z$ and $Y$, the classifier may be biased against
certain demographics.

Our goal is to improve the fairness of the classifier by modifying the input
$\bm{X}$, rather than modifying the classifier’s fixed weights. In particular,
we aim to achieve either of the following fairness criteria.

$\mbox{{Equalized Odds:}}\quad\hat{Y}\perp
Z|Y,\quad\mbox{or}\quad\mbox{{Demographic Parity:}}\quad\hat{Y}\perp Z,$ (1)

where $\perp$ denotes independence. The following two subsection will explain
how to modify input and design the optimization objective respectively.

###  3.2 Modifying the Input Features

Input modification primarily involves appending a _fairness trigger_ to the
input. Formally, the input modification takes the following generic form:

$\tilde{\bm{X}}=m(\bm{X};\bm{\theta},\bm{\delta})=[\bm{\delta},g(\bm{X};\bm{\theta})],$
(2)

where $\tilde{\bm{X}}$ denotes the modified input; $[\cdot]$ denotes vector
concatenation. As can be observed, the input modification consists of two
steps. First, $\bm{X}$ is fed through a transformation function
$g(\cdot;\bm{\theta})$, where $\bm{\theta}$ represents the hyper-parameters of
the transformation function. The actual form of $g(\cdot;\bm{\theta})$ is
contingent upon different applications and modalities, but a general
requirement is that $g(\cdot;\bm{\theta})$ should largely retain the
information necessary for classification. The second step is to append a
fairness trigger, $\bm{\delta}$, to the input, which is a vector that can be
optimized over. It is important to note that $\bm{\delta}$ is a _constant_ –
different inputs get appended the same trigger. Although it does not seem
intuitive, we will soon show that a constant trigger is all you need to
achieve fair prediction on all different inputs.

Below are specific forms of transformations (Eq. (2)) we use.

Text Classification In text classification, $\bm{X}$ represents a sequence of
input token embeddings. To modify the input, we simply append a fixed number
of embeddings after the input text. In this case, $g(\cdot;\bm{\theta})$ is
the identity mapping, and $\bm{\delta}$ corresponds to the appended
embeddings.

(a) Border trigger (b) Patch trigger

Figure 1: Demonstration of the border and patch trigger applied on an image
from CelebA [56].

Image Classification In image classification, $\bm{X}$ represents the
(vectorized) input image. Unlike text classification, where the input can have
a variable length, the length of the input to the image classification network
is fixed. We thus apply the following two approaches to append the trigger, as
shown in Fig. 1. The first approach, called the _patch approach_ , removes a
patch from the original image, and appends a trigger the same size as the
patch to the patch location (as shown in Fig. 1(a)). In this case,
$g(\cdot;\bm{\theta})$ is a function that removes the patch dimension and
retain the rest, with $\bm{\theta}$ representing the patch location;
$\bm{\delta}$ represents the trigger feature that replaces the patch. The
second approach, called the _border approach_ , shrinks the image to a smaller
image, and then appends the trigger at the border (as shown in Fig. 1(b)). In
this case, $g(\cdot;\bm{\theta})$ is a function that shrinks the image, and
$\bm{\delta}$ represents the trigger feature at the border.

###  3.3 Optimization Objective

Our optimization objective is as follows

$\min_{\bm{\delta},\bm{\theta}}\,\,\,\mathcal{L}_{util}(\mathcal{D}_{tune},f^{*}\circ
m)+\lambda\mathcal{L}_{fair}(\mathcal{D}_{tune},f^{*}\circ m),$ (3)

where $m=m(\cdot;\bm{\theta},\bm{\delta})$ represents the input modification
function as in Eq. (2); $\circ$ represents nested functions;
$\mathcal{D}_{tune}$ represents the dataset that are used to train the
fairness trigger. Note that this is different from the dataset where the
classifier, $f^{*}$, is pre-trained.

The first loss term, $\mathcal{L}_{util}$, is the utility loss function of the
task. For classification tasks, $\mathcal{L}_{util}$ is usually the cross-
entropy loss, _i.e._ ,

$\mathcal{L}_{util}(\mathcal{D}_{tune},f^{*}\circ
m)=\mathbb{E}_{\bm{X},Y\sim\mathcal{D}_{tune}}[\textrm{CE}(Y,f^{*}(m(\bm{X})))],$
(4)

where CE$(\cdot,\cdot)$ denotes the cross-entropy loss.

The second loss term, $\mathcal{L}_{fair}$, encourages the prediction to
follow the fairness criteria as in Eq. (1). According to Eq. (1),
$\mathcal{L}_{fair}$ should measure how much information about $Z$ is in
$\hat{Y}$. To measure this, we introduce another network, called the
discriminator, $d(\cdot;\bm{\phi})$, where $\bm{\phi}$ represents its
parameters. If the equalized odds criterion is applied, then
$d(\cdot;\bm{\phi})$ should predict $Z$ from $\hat{Y}$ and $Y$; if the
demographic parity criterion is applied, then the input to
$d(\cdot;\bm{\phi})$ would just be $\hat{Y}$. In the following, we will focus
on equalize odds criterion for conciseness. Then, the information of $Z$ can
be measured by maximizing the _negative_ cross-entropy loss for the prediction
of $Z$ over the discriminator parameters, _i.e._ ,

$\mathcal{L}_{fair}(\mathcal{D}_{tune},f^{*}\circ
m)=\max_{\bm{\phi}}\mathbb{E}_{\bm{X},Y,Z\sim\mathcal{D}_{tune}}[-\textrm{CE}(Z,d(f^{*}(m(\bm{X})),Y;\bm{\phi}))].$
(5)

By plugging Eqs. (4) and (5) into (3), we can see that the entire optimization
objective becomes a min-max framework, where the discriminator tries to
improve its prediction of $Z$ while the fairness trigger tries to make the
prediction worse. As shown in [33], when the discriminator cannot predict $Z$
better than chance, the aforementioned fairness criteria can be achieved.

###  3.4 Why Does It Work?

It is not immediately straightforward why a _global_ trigger can obscure the
demographic information for _any_ input. In this section, we will propose an
information-theoretic framework that illustrates one of the mechanisms through
which the trigger can remove the demographic information.

Figure 2: Illustration of why fairness trigger works. (a) The data generation
process. (b) The information flow from data to the classifier through the
sufficient statistics. (c) Fairness trigger strongly indicative of a
demographic group can confuse the classifier with a false demographic
posterior, and thus preventing the classifier from using the correct
demographic information.

Our theoretical framework builds upon the data generation process as shown in
Fig. 2(a). Specifically, we assume that $\bm{X}$ consists of a set of
features, _i.e._ $\bm{X}=[\bm{X}_{1},\cdots,\bm{X}_{T}]$, where $T$ is the
total number of features. In text classification, a feature can be a word or a
word piece; in image classification, a feature can be specific shapes, colors,
patterns, _etc_. Assume that these features can be divided into two groups.
The first group, denoted as $\bm{X}^{(y)}$, consists of features that are
directly governed by the output label $Y$; the second group, denoted as
$\bm{X}^{(z)}$, consists of featuers that are directly governed by the
demographic information $Z$. $Z$ and $Y$ can be spuriously correlated, _i.e._
there can be common confounders, $C$, between $Z$ and $Y$. As a result, both
$\bm{X}^{(y)}$ and $\bm{X}^{(z)}$ are indicative of $Y$.

To further simplify our theoretical analysis, we consider a bag-of-feature
scenario, where each feature in $\bm{X}^{(y)}$ is drawn from the vocabulary
set $\mathcal{X}^{(y)}$, and each feature in $\bm{X}^{(z)}$ is drawn from the
vocabulary set $\mathcal{X}^{(z)}$. There should not be any overlap between
the two vocabulary sets, _i.e._
$\mathcal{X}^{(y)}\cap\mathcal{X}^{(z)}=\varnothing$. Otherwise it violates
our assumption that demographic-related features are biased features.

It can be shown (in Appendix C) that the posterior distributions,
$p_{Y}(\cdot|\bm{X}^{(y)})$ and $p_{Z}(\cdot|\bm{X}^{(z)})$, are the
sufficient statistics of $\bm{X}^{(y)}$ and $\bm{X}^{(z)}$ respectively for
inferring $Y$. In other words, these two posterior distributions summarize all
the information about $\bm{X}^{(y)}$ and $\bm{X}^{(z)}$ that the classifier
needs to know to predict $Y$. Therefore, we assume that the classifier takes
the following generic form

$\hat{Y}=f^{*}(\bm{X})=h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)})).$
(6)

Note that we add a superscript, $tr$, to emphasize that the probability
distributions are over the data set where the classifier is trained, because
the classifier has never been trained on inputs modified with the fairness
trigger. Eq. (6) encompasses many common decision functions. For example, it
can be shown (in Appendix C) that the posterior distribution $p(Y|\bm{X})$,
which is the minimizer of the cross-entropy loss, is a special case of Eq.
(6).

As illustrated in Fig. 2(b), $p_{Y}(\cdot|\bm{X}^{(y)})$ and
$p_{Z}(\cdot|\bm{X}^{(z)})$ provide two sets of information from input
features. $p_{Y}(\cdot|\bm{X}^{(y)})$ provides the _unbiased_ information,
because a desirable fair classifier should rely only upon
$p_{Y}(\cdot|\bm{X}^{(y)})$ to make a decision. On the other hand,
$p_{Z}(\cdot|\bm{X}^{(z)})$ provides the _biased_ information, because it
conveys the demographic information. In other words, the fairness goals can be
achieved by cutting off the biased information path. Therefore, our research
question boils down to: is it possible to cut off the biased information path
with a global fairness trigger $\bm{\delta}$?

Without loss of generality, assume that $\bm{\delta}$ consists of only one
feature. Consider the case where $\bm{\delta}$ is a demographic feature,
_i.e._ $\bm{\delta}\in\mathcal{X}^{(z)}$. In this case, we assume the
transformed input as defined in Eq. (2) can also be divided into two groups:

$\tilde{\bm{X}}=[\tilde{\bm{X}}^{(y)},\tilde{\bm{X}}^{(z)}],\quad\mbox{where}\quad\tilde{\bm{X}}^{(y)}=g(\bm{X}^{(y)}),\quad\tilde{\bm{X}}^{(z)}=[\bm{\delta},g(\bm{X}^{(z)})].$
(7)

The following theorem states our main conclusion:

######  Theorem 1.

Under the assumptions in Eq. (6) and (7), and some additional regularity
conditions111Formal assumptions stated in the appendix., if the fairness
trigger $\bm{\delta}$ is indicative of a certain demographic group $z$, then

$\lim_{p^{tr}(Z=z|\bm{X}_{0}^{(z)}=\bm{\delta})\rightarrow
1}\textrm{MI}(\hat{\tilde{Y}},Z|Y)=0,$ (8)

where MI means mutual information; $\hat{\tilde{Y}}=f^{*}(\tilde{\bm{X}})$ is
the classifier’s prediction after input is modified.

$p^{tr}(Z=z|\bm{X}_{0}^{(z)}=\bm{\delta})\rightarrow 1$ means that the
fairness trigger is very strongly indicative of the demographic group $z$.
Therefore, Thm. 1 essentially states that if the prepended trigger feature is
very strongly indicative of a certain demographic group, then equalized odds
can be achieved. A formal proof is presented in Appendix C. Here we would like
to give an intuitive explanation. When
$p^{tr}(Z=z|\bm{X}_{0}^{(z)}=\bm{\delta})\rightarrow 1$, it will also happen
that $p^{tr}(Z=z|\bm{X}^{(z)}=\tilde{\bm{X}}^{(z)})\rightarrow 1$. In other
words, the fairness trigger $\bm{\delta}$ would overshadow the rest of the
demographic features and ‘trick’ the classifier into believing all the
different inputs belong to the same demographic group $z$. As a result, the
second argument in Eq (6) would reduce to a constant (1 for demographic group
$z$ and 0 elsewhere), effectively blocking the biased information path, as
shown in Fig. 2(c). Note that the premise for the fairness trigger to work is
that the classifier has never seen the modified input. Otherwise, the
classifier will be able to learn to ignore the constant trigger and still
elicit the true demographic information from input.

##  4 Experiments

In this section, we evaluate the effectiveness of FairReprogram on both NLP
and CV applications in terms of accuracy, fairness, performances under low-
data regime, transferability and interpretability.

###  4.1 Experiment Setup

#### Datasets

We consider the following two commonly used NLP and CV datasets:

  * •

Civil Comments [57, 58]: The dataset contains 448k texts with labels that
depict the toxicity of each input. The demographic information of each text is
provided.

  * •

CelebA [56]: The dataset contains over 200k human face images and each
contains 39 binary attribute annotations. We follow the conventional setting
[56] that adopts the hair color prediction task in our experiment and uses
gender annotation as the demographic information. [59, 60, 61]

For both datasets, we split the entire data into a training set, a tuning set,
a validation set, and a testing set. The training set is used for the base
model training, _i.e._ , to obtain a biased model for reprogramming. The
tunning set and validation set are used for trigger training and hyper-
parameter selection. We report our results on the testing set. It is worth
mentioning that there is no overlapping data between different sets and the
size of the tuning set is much smaller than the training one. Specifically, we
set the size ratio between the tunning set and the training as $1/5$ and
$1/100$ for Civil Comments and CelebA, respectively. The full statistics of
the datasets can be found in Appendix A.1.

#### Metrics

Besides the model accuracy, we introduce two empirical fairness metrics, one
under each of the two fairness criteria as in Eq. (1). For binary
classification, the metrics are calculated as:

$\mbox{{DP:}}\sum_{z\in\mathcal{Z}}|\text{p}(\hat{Y}=1)-\text{p}(\hat{Y}=1|Z=z)|,\quad\mbox{{EO:}}\sum_{z\in\mathcal{Z}}(|\text{FPR}-\text{FPR}_{z}|+|\text{FNR}-\text{FNR}_{z}|)/2,$

where DP and EO stand for demographic parity and equalized odds respectively.
FPR and FNR are the false positive/negative rate, and the subscript $z$
denotes the score is calculated within a specific demographic group $Z=z$. For
example, $\text{FPR}_{male}$ indicates the false positive rate calculated over
all examples with the “male” annotation. For a multi-class setting, the bias
scores are first calculated similarly using one-vs-all for each class and then
averaged across different classes. All reported results are the average of
three different random runs. It can be shown that these metrics are non-
negative, and will become zero when their corresponding fairness criteria are
achieved. For better elaboration, we report the negative bias scores in our
experiments, so the larger these negative scores are, the better the model
satisfies the corresponding fairness criteria.

#### Baselines and implementation details

We consider the following models for comparison:

$\bullet$ Base: the base model to be reprogrammed, trained with the cross-
entropy loss on the training set.

$\bullet$ AdvIn [33]: an in-processing adversarial training method that
optimizes both model accuracy and fairness using the training set.

$\bullet$ AdvPost: a post-processing variant of AdvIn, which fine-tunes the
Base model with the same fairness-aware adversarial objectives as AdvIn, but
using the (low-resource) tunning set only.

For NLP experiments, we use a pre-trained Bert [62] to obtain the Base and
AdvIn models. We use AdamW [63] as the optimizer, and set the learning rate to
$10^{-5}$ for all baselines and $0.1$ for FairReprogram. For CV experiments,
we consider a ResNet-18 [64] that pre-trained on ImageNet. The discriminator
used in AdvIn, AdvPost and FairReprogram is a three-layer MLP, and the
parameters are optimized using Adam with a learning rate of $0.01$. We pick
the best model based on the accuracy (for the Base) or the bias scores (for
all other debiasing methods) of the validation set. We refer to Appendix A.2
for more details and Appendix B for more baseline studies.

Next we introduce the implementation details of the triggers for different
variants of FairReprogram. For image classification task, we adopt the border
and patch trigger as shown in Fig. 1, termed FairReprogram (Border) and
FairReprogram (Patch) correspondingly. We define the trigger size as the width
of the trigger frame for border trigger and the width of the square patch for
patch trigger. Unless otherwise stated, the default trigger size for each
setting are $20$ and $80$.

For text classification task, we introduce a probability vector $\bm{v}_{i}$
to control the selection of trigger word for each position $i$. Specifically,
we have the trigger $\bm{\delta}_{i}=\bm{E}\bm{v}_{i}$ where $\bm{E}$
represents the pretrained word embedding matrix of Bert. Then we simply
concatenate $\bm{\delta}$ after all input texts222The trigger is appended as a
suffix after all input tokens but before [SEP] for Bert. in the embeddings
space as the fairness trigger. We introduce two types of trigger. The first
type, called FairReprogram (Soft) , uses continuous $\bm{v}_{i}$’s, and each
$\bm{v}_{i}$ is projected onto the continuous probability simplex using the
bisection algorithm after each training step. The second type, called
FairReprogram (Hard), discretizes each $\bm{v}_{i}$ into a one-hot vector
$\hat{\bm{v}}_{i}$ via $\mathop{\arg\max}$ operation. We adopt the straight
through technique [65] to update $\bm{v}_{i}$ during training. The triggers
found by FairReprogram (Hard) enjoy better interpretability as they correspond
to a sequence of word tokens. Unless specified otherwise, we set the trigger
word number as five for our experiments.

###  4.2 Results

(a) Civil Comments (b) CelebA

Figure 3: Results on (a) Civil Comments and (b) CelebA. We report the negative
DP (left) and the negative EO (right) scores. For each method, we vary the
trade-off parameter $\lambda$ (as shown in (3)) to record the performance. The
closer a dot to the upper-right corner, the better the model is. We consider
five different $\lambda$s for each method. The solid curve is the fitted
polynomial with order 30.

(a) Civil Comments (b) CelebA

Figure 4:  Results on (a) Civil Comments and (b) CelebA with different tuning
data ratio. We report the negative DP (left) and negative EO (right) scores.
We consider a fixed Base model trained with training set, whose negative bias
scores are presented as a black dashed line. Then we train other methods with
different tuning data ratio to promote fairness of the Base model.

Fig. 3 shows the performance of the proposed FairReprogram with other
baselines on both NLP (subfigure (a)) and CV (subfigure (b)) datasets using DP
(left) and EO (right) metrics. In each subfigure, the data samples of the same
method (dots in the same color) are generated by explicit changing the
adversary weight $\lambda$ in (3), which controls the trade-off between
fairness and accuracy. We further fit the data with polynomial regression to
present the curves. Appendix A.2 shows the detailed $\lambda$ choices for
different methods. Here are our key observations. First, our method improves
the fairness of the Base model. In particular, our methods (both orange and
red curves) achieve higher negative DP and EO scores with a comparable
classification accuracy. Second, our method enjoys a better fairness-accuracy
trade-off compared with all other baselines. Specifically, the curves of our
method lie farther to the upper-right corner of the plots, which implies that
our method improves model fairness with fewer sacrifices on accuracy. It is
also worth noting that although AdvIn achieves good fairness scores, it uses
much more data for training.

#### Limited data setting

We further evaluate AdvPost and FairReprogram with decreasing the number of
data in the tuning set. Specifically, we fix a $\lambda$ for each method such
that all methods achieve comparable bias score with full tuning set. The
detailed $\lambda$ choices are provided in Appendix A.2. Then we apply these
methods to subsets of the tuning set with different proportions. The results
are shown in Fig. 4. There are two key observations. First, our method can
consistently improve fairness upon Base model even with 1% tuning data,
indicating a high data efficiency of FairReprogram. Second, FairReprogram
achieves better fairness than AdvPost does when tuning data number decreases.
For example, in Fig. 4 (a), the curve of our method is significantly above the
AdvPost as tuning data decreases. When the tuning set size is extremely small,
AdvPost significantly deteriorates and even underperforms the Base model.

#### Transferability

(a) Civil Comments (b) CelebA

Figure 5:  Results in the transfer setting. We report negative DP (left) and
negative EO (right) scores. The triggers are firstly trained in a Base model.
Then we evaluate the triggers based on another unseen Base model. We change
the parameter $\lambda$ to trade-off accuracy with fairness and draw the
curves in the same way with Fig. 3. The ★ point corresponds to the average of
all Base models with different random seeds.  Figure 6: Gradient-based
saliency map visualized with Grad Cam [66] of different methods. The
highlighted zones (marked in red) depicting regions exerting major influence
on the predicted labels (non-blond hair v.s. blond hair) in each row, which
also depict the attention of the model on the input image.

Next, we show the transferability of the fairness triggers found by
FairReprogram. We first tune the triggers with a Base source model and then
apply the trigger on a target model trained with a different random seed. The
results are shown in Fig. 5. As can be seen, FairReprogram achieves comparable
fairness-accuracy trigger on both the source model and the target model,
indicating our method has a good transferability. This intriguing property
brings two benefits of our method: ① if ML model parameters are infeasible
(_e.g._ when ML models are provided as services), the users could train a
surrogate model and tune the trigger based on it to promote fairness of the
original model; ② when ML model parameters are updated with new data (_e.g._
online learning), the user could still use the original trigger for fixing
fairness problems. We further elaborate the results of FairReprogram for
transferring to different tasks and model architectures in Appendix B.5.

#### Input saliency attribution.

Fig. 7 and 6 compare the saliency maps of some example inputs with and without
the fairness triggers. Specifically, For the NLP applications, we extract a
subset of Civil Comments with religion-related demographic annotations, and
apply IG [67] to localize word pieces that contribute most to the text
toxicity classification. For the CV application, we use GradCam [66] to
identify class-discriminative regions of CelebA’s test images. As shown in
Fig. 7, our fairness trigger consists of a lot of religion-related words
(e.g., diocesan, hebrew, parish). Meanwhile, the predicted toxicity score of
the benign text starting from ‘muslims’ significantly reduces. These
observations verify our theoretical hypothesis that the fairness trigger is
strongly indicative of a certain demographic group to prevent the classifier
from using the true demographic information. In addition, Fig. 6 presents the
input saliency maps on two input images with respect to their predicted
labels, non-blond hair and blond hair, respectively. As can be observed, when
there is no fairness trigger, the saliency region incorrectly concentrates on
the facial parts, indicating the classifier is likely to use biased
information, such as gender, for its decision. With the fairness trigger, the
saliency region moves to the hair parts, which matches the behavior of AdvIn.
These results confirm that our fairness trigger can drive models to make
fairer predictions.

Table 1: Predictions of the demographic classifier on a null input with
triggers generated by different $\lambda$. The demographic prediction for CV
triggers indicate the predicted score for _Male_ and _Female_ , and it is
_Christian_ , _Muslim_ and _Other religion_ for NLP.

Trigger | Demographic Prediction
---|---
| 0.85, 0.15
| 0.92, 0.08
| 0.80, 0.20
same diocesan bula rev proceedings | 0.96, 0.11, 0.02
soto cc rib hebrew armenian | 0.51, 0.08, 0.81
paul long course parish body | 0.98, 0.04, 0.03

_Text (Non-toxic)_ | _Predicted Toxicity_
---|---
muslims need to take a look in the mirror | 0.149
muslims need to take a look in the mirror same diocesan bula rev proceedings | 0.069
muslims need to take a look in the mirror soto cc rib hebrew armenian | 0.054
muslims need to take a look in the mirror paul long course parish body | 0.073

Figure 7:  A text example from Civil Comments with Integrated Gradient [67,
68] highlighting important words that influence ERM model predictions. The
text is concatenated with three triggers generated with different adversary
weight. Green highlights the words that lean to toxic predictions and Red
highlights non-toxic leaning words. The model prediction tends to be correct
after adding the triggers.

To further verify that the triggers encode demographic information, we trained
a demographic classifier to predict the demographics from the input (texts or
images) without triggers. The obtained demographic classifiers can accurately
identify the demographics contained in the inputs and achieve over 0.99 AUC
for identifying demographics in the validation datasets. Then, we use the
demographic classifier to predict the demographic information of a null
image/text333We use an empty string as the null text and an all-black image as
the null image. with the trigger. Specifically, we select three triggers
generated with different $\lambda$ values for both two datasets. The
results444One text could contain multiple religions so the probabilities do
not sum to one for NLP triggers. can be seen in Table 1. We see that the
demographic classifier gives confident outputs on the triggers. For example,
we see that the trigger _paul long course parish body_ is classified as
containing _christian_ with 0.98 confidence, indicating that the found
triggers are highly indicative of demographics. This is consistent with our
perspective in Section 3.4 that the fairness triggers are encoding fake
demographic information to obscure ML models from making biased predictions.

###  4.3 Multi-Class Classification

(a) 8-class negative DP (b) 8-class negative EO (c) 16-class negative DP (d)
16-class negative EO

Figure 8: Performance of multi-class classification. For (a) and (b), we use
the attributes Blond Hair, Smiling, Attractive for multi-class construction.
We add an addition attribute Wavy Hair for (c) and (d).

To extend our evaluation to a multi-class setting, we use the CelebA dataset
and select $n$ binary attributes that may be spuriously correlated with
_gender_ [59, 60, 61]. Then, following [69], we construct data groups by
enumerating all $2^{n}$ possible binary vectors, where each dimension
corresponds to a binary attribute. We index these vectors and treat them as
the class labels. Fig. 8 shows the accuracy-fairness trade-off curves similar
to Fig. 3. It can be observed that our method outperforms the other methods as
the red curves are closer to the top-right corner. Also, as the class label
number increases, the post-processing-based AdvPost falls behind its in-
processing counterpart AdvIn, indicating a larger class number may induce more
challenges to post-processing methods.

###  4.4 Ablation Studies

(a) Civil Comments (b) CelebA

Figure 9: Ablation study of the trigger size. We evaluate the bias scores with
different trigger word numbers (Civil Comments) and different trigger size
(CelebA) with fixed adversary weight $\lambda$.

We perform an ablation study to investigate the effects of the trigger size.
Specifically, we run experiments with different numbers of trigger words /
trigger patch sizes on the NLP / CV dataset. We set a $\lambda$ value for each
method such that all methods achieve comparable bias scores with the largest
trigger size. The detailed $\lambda$ choices can be seen in Appendix A.2. Then
we train the triggers with different sizes in the tuning set using the fixed
$\lambda$’s. For the text trigger as shown in Fig. 9(a), we see that the
negative bias score gets worse as the number of trigger words gets smaller.
However, our method can still improve fairness upon the Base model even with
only a one-word trigger. On the other hand, the results with five trigger
words and above are all comparable, indicating that five words is enough to
achieve the fairness goal. Similarly, for the image trigger as shown in Fig.
9(b), the results suggest a larger trigger would consistently improve
fairness. On the other hand, we show that larger trigger size could hurt
accuracy in Appendix B, which is similar to the effect of increasing
$\lambda$.

###  4.5 Summary of Additional Results

We compare our proposed FairReprogram with four additional baselines, and we
show the full results with variance in Tab. 3. We further compare our method
with MMD methods where $\mathcal{L}_{fair}$ in Eq. (3) is replaced with
Maximum Mean Discrepancy regularization [70] to partial out the instability of
adversarial training, and the results are shown in Fig. 10. We also implement
the fairness reprogramming in the black-box setting on CelebA dataset, where
the model parameters are not available for training the reprogram, and the
results are shown in Fig. 11. Besides, we show that FairReprogram could also
be used in tabular data, and the corresponding experiment results on the Adult
dataset are shown in Fig. 13.

##  5 Conclusion

In this paper, we introduce a novel model reprogramming based fairness
promoting method, termed FairReprogram. Specifically, FairReprogram considers
a fixed ML model and optimizes a set of vectors, named fairness trigger,
concatenated on inputs to boost model fairness. We introduce an information-
theoretic framework to explain the rationales of why FairReprogram can improve
model fairness. As implied by our theoretic framework as well as our empirical
findings, the fairness trigger can effectively mask out the true demographic
information with its strong, false demographic information. Extensive
experiments demonstrate that our method could achieve better fairness
improvements to retraining based methods with far-less training cost. We
further empirically show fairness triggers enjoys great transferability and
interpretability. We hope that FairReprogram can inspire new fairness learning
paradigms that are more feasible and flexible in practice.

## References

  * [1] Lucas Dixon, John Li, Jeffrey Scott Sorensen, Nithum Thain, and Lucy Vasserman,  “Measuring and mitigating unintended bias in text classification,”  Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, 2018.
  * [2] J. Park, Jamin Shin, and Pascale Fung,  “Reducing gender bias in abusive language detection,”  in EMNLP, 2018.
  * [3] Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez-Rodriguez, and Krishna P. Gummadi,  “Fairness constraints: Mechanisms for fair classification,”  in AISTATS, 2017.
  * [4] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna M. Wallach,  “A reductions approach to fair classification,”  ArXiv, vol. abs/1803.02453, 2018.
  * [5] Toshihiro Kamishima, Shotaro Akaho, Hideki Asoh, and Jun Sakuma,  “Fairness-aware classifier with prejudice remover regularizer,”  in ECML/PKDD, 2012.
  * [6] Sina Baharlouei, Maher Nouiehed, and Meisam Razaviyayn,  “Rényi fair inference,”  arXiv: Learning, 2019.
  * [7] Adrián Pérez-Suay, Valero Laparra, Gonzalo Mateo-García, Jordi Muñoz-Marí, Luis Gómez-Chova, and Gustau Camps-Valls,  “Fair kernel learning,”  in ECML/PKDD, 2017.
  * [8] Gamaleldin F Elsayed, Ian Goodfellow, and Jascha Sohl-Dickstein,  “Adversarial reprogramming of neural networks,”  arXiv preprint arXiv:1806.11146, 2018.
  * [9] Yun-Yun Tsai, Pin-Yu Chen, and Tsung-Yi Ho,  “Transfer learning without knowing: Reprogramming black-box machine learning models with scarce data and limited resources,”  in International Conference on Machine Learning. PMLR, 2020, pp. 9614–9624.
  * [10] Karen Hambardzumyan, Hrant Khachatrian, and Jonathan May,  “Warp: Word-level adversarial reprogramming,”  arXiv preprint arXiv:2101.00121, 2021.
  * [11] Ning Ding, Shengding Hu, Weilin Zhao, Yulin Chen, Zhiyuan Liu, Haitao Zheng, and Maosong Sun,  “Openprompt: An open-source framework for prompt-learning,”  ArXiv, vol. abs/2111.01998, 2022.
  * [12] Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig,  “Pre-train, prompt, and predict: A systematic survey of prompting methods in natural language processing,”  ArXiv, vol. abs/2107.13586, 2021.
  * [13] Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daumé, Miroslav Dudík, and H. Wallach,  “Improving fairness in machine learning systems: What do industry practitioners need?,”  Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems, 2019.
  * [14] A. Chouldechova and Aaron Roth,  “The frontiers of fairness in machine learning,”  ArXiv, vol. abs/1810.08810, 2018.
  * [15] Tony Sun, Andrew Gaut, Shirlyn Tang, Yuxin Huang, Mai ElSherief, Jieyu Zhao, Diba Mirza, Elizabeth M. Belding-Royer, Kai-Wei Chang, and William Yang Wang,  “Mitigating gender bias in natural language processing: Literature review,”  in ACL, 2019.
  * [16] Ninareh Mehrabi, Fred Morstatter, Nripsuta Ani Saxena, Kristina Lerman, and A. G. Galstyan,  “A survey on bias and fairness in machine learning,”  ACM Computing Surveys (CSUR), vol. 54, pp. 1 – 35, 2021.
  * [17] Anjalie Field, Su Lin Blodgett, Zeerak Waseem, and Yulia Tsvetkov,  “A survey of race, racism, and anti-racism in nlp,”  ArXiv, vol. abs/2106.11410, 2021.
  * [18] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel,  “Fairness through awareness,”  ArXiv, vol. abs/1104.3913, 2012.
  * [19] Karima Makhlouf, Sami Zhioua, and Catuscia Palamidessi,  “Survey on causal-based machine learning fairness notions,”  ArXiv, vol. abs/2010.09553, 2020.
  * [20] T. Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang,  “Fairness without demographics in repeated loss minimization,”  in ICML, 2018.
  * [21] Toon Calders and Sicco Verwer,  “Three naive bayes approaches for discrimination-free classification,”  Data Mining and Knowledge Discovery, vol. 21, pp. 277–292, 2010\.
  * [22] Moritz Hardt, Eric Price, and Nathan Srebro,  “Equality of opportunity in supervised learning,”  in NIPS, 2016.
  * [23] Tim Räz,  “Group fairness: Independence revisited,”  Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, 2021.
  * [24] Simon Caton and Christian Haas,  “Fairness in machine learning: A survey,”  ArXiv, vol. abs/2010.04053, 2020.
  * [25] Faisal Kamiran and Toon Calders,  “Data preprocessing techniques for classification without discrimination,”  Knowledge and Information Systems, vol. 33, pp. 1–33, 2011.
  * [26] Richard S. Zemel, Ledell Yu Wu, Kevin Swersky, Toniann Pitassi, and Cynthia Dwork,  “Learning fair representations,”  in ICML, 2013.
  * [27] Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Eduardo Scheidegger, and Suresh Venkatasubramanian,  “Certifying and removing disparate impact,”  Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015.
  * [28] Flávio du Pin Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R. Varshney,  “Optimized pre-processing for discrimination prevention,”  in NIPS, 2017.
  * [29] Aditya Grover, Kristy Choi, Rui Shu, and Stefano Ermon,  “Fair generative modeling via weak supervision,”  in ICML, 2020.
  * [30] Guanhua Zhang, Bing Bai, Junqi Zhang, Kun Bai, Conghui Zhu, and T. Zhao,  “Demographics should not be the reason of toxicity: Mitigating discrimination in text classifications with instance weighting,”  in ACL, 2020.
  * [31] Yuji Roh, Kangwook Lee, Steven Euijong Whang, and Changho Suh,  “Fr-train: A mutual information-based approach to fair and robust training,”  in ICML, 2020.
  * [32] Wenbin Zhang and Eirini Ntoutsi,  “Faht: An adaptive fairness-aware decision tree classifier,”  in IJCAI, 2019.
  * [33] B. Zhang, Blake Lemoine, and Margaret Mitchell,  “Mitigating unwanted biases with adversarial learning,”  Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society, 2018.
  * [34] Felix Petersen, Debarghya Mukherjee, Yuekai Sun, and Mikhail Yurochkin,  “Post-processing for individual fairness,”  in NeurIPS, 2021.
  * [35] Dennis Wei, Karthikeyan Natesan Ramamurthy, and Flávio du Pin Calmon,  “Optimized score transformation for fair classification,”  in AISTATS, 2020.
  * [36] Pranjal Awasthi, Matthäus Kleindessner, and Jamie H. Morgenstern,  “Equalized odds postprocessing under imperfect group information,”  in AISTATS, 2020.
  * [37] Blake E. Woodworth, Suriya Gunasekar, Mesrob I. Ohannessian, and Nathan Srebro,  “Learning non-discriminatory predictors,”  ArXiv, vol. abs/1702.06081, 2017.
  * [38] Alan Mishler and Edward H. Kennedy,  “Fairness in risk assessment instruments: Post-processing to achieve counterfactual equalized odds,”  Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, 2021.
  * [39] Jieyu Zhao, Tianlu Wang, Mark Yatskar, Vicente Ordonez, and Kai-Wei Chang,  “Men also like shopping: Reducing gender bias amplification using corpus-level constraints,”  in EMNLP, 2017.
  * [40] Michael P. Kim, Amirata Ghorbani, and James Y. Zou,  “Multiaccuracy: Black-box post-processing for fairness in classification,”  Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, 2019.
  * [41] Pranay Kr. Lohia, Karthikeyan Natesan Ramamurthy, Manish Bhide, Diptikalyan Saha, Kush R. Varshney, and Ruchir Puri,  “Bias mitigation post-processing for individual and group fairness,”  ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2847–2851, 2019.
  * [42] Pranay Kr. Lohia,  “Priority-based post-processing bias mitigation for individual and group fairness,”  ArXiv, vol. abs/2102.00417, 2021.
  * [43] Cynthia Dwork, Nicole Immorlica, Adam Tauman Kalai, and Mark D. M. Leiserson,  “Decoupled classifiers for group-fair and efficient machine learning,”  in FAT, 2018.
  * [44] Evgenii Chzhen, Christophe Denis, Mohamed Hebiri, L. Oneto, and Massimiliano Pontil,  “Leveraging labeled and unlabeled data for consistent fair binary classification,”  in NeurIPS, 2019.
  * [45] Hyojin Bahng, Ali Jahanian, Swami Sankaranarayanan, and Phillip Isola,  “Visual prompting: Modifying pixel space to adapt pre-trained models,”  arXiv preprint arXiv:2203.17274, 2022.
  * [46] Paarth Neekhara, Shehzeen Hussain, Shlomo Dubnov, and Farinaz Koushanfar,  “Adversarial reprogramming of text classification neural networks,”  arXiv preprint arXiv:1809.01829, 2018.
  * [47] Paarth Neekhara, Shehzeen Hussain, Jinglong Du, Shlomo Dubnov, Farinaz Koushanfar, and Julian McAuley,  “Cross-modal adversarial reprogramming,”  in Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, 2022, pp. 2427–2435.
  * [48] Yang Zheng, Xiaoyi Feng, Zhaoqiang Xia, Xiaoyue Jiang, Ambra Demontis, Maura Pintor, Battista Biggio, and Fabio Roli,  “Why adversarial reprogramming works, when it fails, and how to tell the difference,”  arXiv preprint arXiv:2108.11673, 2021.
  * [49] Depeng Xu, Shuhan Yuan, Lu Zhang, and Xintao Wu,  “Fairgan: Fairness-aware generative adversarial networks,”  2018 IEEE International Conference on Big Data (Big Data), pp. 570–575, 2018.
  * [50] Beatrice Nobile, Gabriele Santin, Bruno Lepri, and Pierpaolo Brutti,  “Reprogramming fairgans with variational auto-encoders: A new transfer learning model,”  ArXiv, vol. abs/2203.05811, 2022.
  * [51] Tianyu Gao, Adam Fisch, and Danqi Chen,  “Making pre-trained language models better few-shot learners,”  ArXiv, vol. abs/2012.15723, 2021.
  * [52] Xiang Lisa Li and Percy Liang,  “Prefix-tuning: Optimizing continuous prompts for generation,”  Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), vol. abs/2101.00190, 2021\.
  * [53] Timo Schick and Hinrich Schütze,  “It’s not just size that matters: Small language models are also few-shot learners,”  ArXiv, vol. abs/2009.07118, 2021.
  * [54] Taylor Shin, Yasaman Razeghi, Robert L Logan IV, Eric Wallace, and Sameer Singh,  “Eliciting knowledge from language models using automatically generated prompts,”  ArXiv, vol. abs/2010.15980, 2020.
  * [55] Shizhe Diao, Xuechun Li, Yong Lin, Zhichao Huang, and Tong Zhang,  “Black-box prompt learning for pre-trained language models,”  ArXiv, vol. abs/2201.08531, 2022.
  * [56] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang,  “Deep learning face attributes in the wild,”  in Proceedings of International Conference on Computer Vision (ICCV), December 2015.
  * [57] Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Wei hua Hu, Michihiro Yasunaga, Richard L. Phillips, Sara Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang,  “Wilds: A benchmark of in-the-wild distribution shifts,”  in ICML, 2021.
  * [58] Jigsaw/Conversation AI,  “Jigsaw unintended bias in toxicity classification,” 2019.
  * [59] Tian Xu, Jennifer White, Sinan Kalkan, and Hatice Gunes,  “Investigating bias and fairness in facial expression recognition,”  in European Conference on Computer Vision. Springer, 2020, pp. 506–523.
  * [60] Saloni Dash and Amit Sharma,  “Counterfactual generation and fairness evaluation using adversarially learned inference,”  ArXiv, 2020.
  * [61] Sunhee Hwang, Sungho Park, Dohyung Kim, Mirae Do, and Hyeran Byun,  “Fairfacegan: Fairness-aware facial image-to-image translation,”  arXiv preprint arXiv:2012.00282, 2020.
  * [62] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova,  “Bert: Pre-training of deep bidirectional transformers for language understanding,”  ArXiv, vol. abs/1810.04805, 2019.
  * [63] Ilya Loshchilov and Frank Hutter,  “Decoupled weight decay regularization,”  arXiv preprint arXiv:1711.05101, 2017.
  * [64] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * [65] Yoshua Bengio, Nicholas Léonard, and Aaron C. Courville,  “Estimating or propagating gradients through stochastic neurons for conditional computation,”  ArXiv, vol. abs/1308.3432, 2013.
  * [66] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra,  “Grad-cam: Visual explanations from deep networks via gradient-based localization,”  in Proceedings of the IEEE international conference on computer vision, 2017, pp. 618–626.
  * [67] Mukund Sundararajan, Ankur Taly, and Qiqi Yan,  “Axiomatic attribution for deep networks,”  ArXiv, vol. abs/1703.01365, 2017.
  * [68] Narine Kokhlikyan, Vivek Miglani, Miguel Martin, Edward Wang, Bilal Alsallakh, Jonathan Reynolds, Alexander Melnikov, Natalia Kliushkina, Carlos Araya, Siqi Yan, and Orion Reblitz-Richardson,  “Captum: A unified and generic model interpretability library for pytorch,” 2020.
  * [69] Ni Zhuang, Yan Yan, Si Chen, Hanzi Wang, and Chunhua Shen,  “Multi-label learning based deep transfer neural network for facial attribute classification,”  Pattern Recognition, vol. 80, pp. 225–240, 2018.
  * [70] Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel,  “The variational fair autoencoder,”  arXiv preprint arXiv:1511.00830, 2015.
  * [71] Geoff Pleiss, M. Raghavan, Felix Wu, J. Kleinberg, and Kilian Q. Weinberger,  “On fairness and calibration,”  in NIPS, 2017.
  * [72] Faisal Kamiran, Asim Karim, and Xiangliang Zhang,  “Decision theory for discrimination-aware classification,”  2012 IEEE 12th International Conference on Data Mining, pp. 924–929, 2012.
  * [73] Rachel K. E. Bellamy, Kuntal Dey, Michael Hind, Samuel C. Hoffman, Stephanie Houde, Kalapriya Kannan, Pranay Lohia, Jacquelyn Martino, Sameep Mehta, Aleksandra Mojsilovic, Seema Nagar, Karthikeyan Natesan Ramamurthy, John Richards, Diptikalyan Saha, Prasanna Sattigeri, Moninder Singh, Kush R. Varshney, and Yunfeng Zhang,  “AI Fairness 360: An extensible toolkit for detecting, understanding, and mitigating unwanted algorithmic bias,” Oct. 2018.
  * [74] Yimeng Zhang, Yuguang Yao, Jinghan Jia, Jinfeng Yi, Mingyi Hong, Shiyu Chang, and Sijia Liu,  “How to robustify black-box ml models? a zeroth-order optimization perspective,”  arXiv preprint arXiv:2203.14195, 2022.
  * [75] Arthur Asuncion and David Newman,  “Uci machine learning repository,” 2007.

##  Appendix A Experiment Setup

###  A.1 Dataset Details

Table 2: Statistics of the datasets. “Pos. (%)” column indicates the ratio of
positive labels (_i.e._ “blond hair” for CelebA, “toxic” for Civil Comments).
We use “Tr.”, “Tun.”, “Val.” and “test.” columns to indicate the size of
training set, tuning set, validation set and testing set. “Demographics”
column indicates the considered demographics in each dataset.

Dataset | Task | Pos. (%) | Tr. | Tun. | Val. | Test. | Demographics
---|---|---|---|---|---|---|---
CelebA | Hair color recognition | 17.4 | 161143 | 1627 | 19867 | 19962 | Gender
Civil Comments | Toxicity classification | 11.3 | 223858 | 45180 | 45180 | 133782 | Gender, Sex orientation, Race, Religion

The dataset splitting setting and demographic information of the datasets are
shown in Tab. 2.

###  A.2 Training Details

We specify the different $\lambda$ values used to generate the curves in Figs.
3 and Figs. 5 in Tab. 3.

For Civil Comments in Figs 4 and 9, we set $\lambda=0.5$ for AdvPost,
$\lambda=50.0$ for FairReprogram (Soft) and $\lambda=1000.0$ for FairReprogram
(Hard) with the DP measure; we set $\lambda=1.0$ for AdvPost and
$\lambda=50.0$ for both of our methods with the EO measure.

For CelebA in Fig. 4 and Fig. 9, we set $\lambda=1.0$ for FairReprogram
(Border) and FairReprogram (Patch) with DP and we set $\lambda=10.0$ for both
with EO. By default, the trigger size of FairReprogram (Border) is set to 20,
which corresponds to the width of the trigger frame. The trigger size of
FairReprogram (Patch) is fixed to 80, namely the width of the trigger block
attached to the original input image. For AdvIn and AdvPost, the $\lambda$ is
set to 0.1 in the setting with DP and $\lambda$ is fixed to 0.5 for training
with EO. The value of $\lambda$ is selected so that different methods achieve
comparable bias scores.

##  Appendix B Additional Experiment Results

###  B.1 Experiments with Additional Post-processing Baselines

Table 3: Numerical results with standard derivation on Civil Comments and
CelebA shown in Fig. 3. All reported results are the average of three
different random runs. We report the negative DP and the negative EO scores
correspondingly for the “Fairness” column. Note that the best models are also
selected based on corresponding fairness measures.

Method | Civil Comments | CelebA
---|---|---
Demographic parity | Equalized odds | Demographic parity | Equalized odds
$\lambda$ | Accuracy | Fairness | $\lambda$ | Accuracy | Fairness | $\lambda$ | Accuracy | Fairness | $\lambda$ | Accuracy | Fairness
ERM | - | $0.922_{\pm 0.004}$ | $-0.036_{\pm 0.005}$ | - | $0.923_{\pm 0.004}$ | $-0.054_{\pm 0.025}$ | - | $0.961_{\pm 0.004}$ | $-0.094_{\pm 0.002}$ | - | $0.961_{\pm 0.004}$ | $-0.231_{\pm 0.008}$
AdvIn | 0.0 | $0.926_{\pm 0.004}$ | $-0.036_{\pm 0.025}$ | 0.0 | $0.919_{\pm 0.004}$ | $-0.033_{\pm 0.005}$ | 0.01 | $0.944_{\pm 0.007}$ | $-0.084_{\pm 0.004}$ | 0.1 | $0.952_{\pm 0.005}$ | $-0.181_{\pm 0.009}$
0.1 | $0.899_{\pm 0.014}$ | $-0.016_{\pm 0.004}$ | 0.1 | $0.899_{\pm 0.006}$ | $-0.016_{\pm 0.009}$ | 0.05 | $0.938_{\pm 0.005}$ | $-0.085_{\pm 0.007}$ | 0.3 | $0.941_{\pm 0.002}$ | $-0.177_{\pm 0.014}$
0.5 | $0.905_{\pm 0.003}$ | $-0.018_{\pm 0.035}$ | 1.0 | $0.919_{\pm 0.006}$ | $-0.023_{\pm 0.002}$ | 0.1 | $0.932_{\pm 0.006}$ | $-0.072_{\pm 0.005}$ | 0.5 | $0.936_{\pm 0.005}$ | $-0.175_{\pm 0.012}$
5.0 | $0.889_{\pm 0.007}$ | $-0.001_{\pm 0.039}$ | 5.0 | $0.889_{\pm 0.005}$ | $-0.001_{\pm 0.007}$ | 0.2 | $0.911_{\pm 0.003}$ | $-0.071_{\pm 0.009}$ | 1.0 | $0.913_{\pm 0.007}$ | $-0.168_{\pm 0.009}$
20.0 | $0.888_{\pm 0.023}$ | $-0.000_{\pm 0.039}$ | 20.0 | $0.888_{\pm 0.009}$ | $-0.000_{\pm 0.006}$ | 0.3 | $0.897_{\pm 0.002}$ | $-0.064_{\pm 0.002}$ | 2.0 | $0.901_{\pm 0.004}$ | $-0.153_{\pm 0.007}$
AdvPost | 0.0 | $0.923_{\pm 0.003}$ | $-0.035_{\pm 0.019}$ | 0.0 | $0.921_{\pm 0.005}$ | $-0.055_{\pm 0.004}$ | 0.01 | $0.959_{\pm 0.004}$ | $-0.097_{\pm 0.004}$ | 0.1 | $0.947_{\pm 0.003}$ | $-0209._{\pm 0.007}$
0.1 | $0.925_{\pm 0.002}$ | $-0.043_{\pm 0.011}$ | 0.2 | $0.925_{\pm 0.002}$ | $-0.045_{\pm 0.002}$ | 0.05 | $0.947_{\pm 0.009}$ | $-0.083_{\pm 0.005}$ | 0.3 | $0.931_{\pm 0.005}$ | $-0.201_{\pm 0.011}$
0.5 | $0.909_{\pm 0.011}$ | $-0.007_{\pm 0.032}$ | 0.4 | $0.925_{\pm 0.002}$ | $-0.041_{\pm 0.004}$ | 0.1 | $0.931_{\pm 0.009}$ | $-0.074_{\pm 0.007}$ | 0.5 | $0.918_{\pm 0.004}$ | $-0.168_{\pm 0.015}$
1.0 | $0.888_{\pm 0.022}$ | $-0.000_{\pm 0.033}$ | 0.7 | $0.924_{\pm 0.002}$ | $-0.042_{\pm 0.005}$ | 0.2 | $0.917_{\pm 0.003}$ | $-0.069_{\pm 0.005}$ | 1.0 | $0.911_{\pm 0.008}$ | $-0.165_{\pm 0.011}$
5.0 | $0.888_{\pm 0.022}$ | $-0.000_{\pm 0.033}$ | 1.0 | $0.888_{\pm 0.022}$ | $-0.000_{\pm 0.028}$ | 0.3 | $0.873_{\pm 0.002}$ | $-0.058_{\pm 0.002}$ | 2.0 | $0.899_{\pm 0.002}$ | $-0.141_{\pm 0.013}$
EqOdds | - | $0.913_{\pm 0.005}$ | $-0.032_{\pm 0.020}$ | - | $0.915_{\pm 0.003}$ | $-0.031_{\pm 0.005}$ | - | $0.919_{\pm 0.009}$ | $-0.047_{\pm 0.005}$ | - | $0.919_{\pm 0.009}$ | $-0.172_{\pm 0.009}$
CaliEqOdds | - | $0.922_{\pm 0.003}$ | $-0.044_{\pm 0.023}$ | - | $0.922_{\pm 0.004}$ | $-0.057_{\pm 0.011}$ | - | $0.927_{\pm 0.007}$ | $-0.053_{\pm 0.005}$ | - | $0.927_{\pm 0.007}$ | $-0.169_{\pm 0.018}$
RejectOption | - | $0.886_{\pm 0.028}$ | $-0.152_{\pm 0.052}$ | - | $0.874_{\pm 0.017}$ | $-0.101_{\pm 0.002}$ | - | $0.934_{\pm 0.003}$ | $-0.089_{\pm 0.004}$ | - | $0.934_{\pm 0.003}$ | $-0.189_{\pm 0.015}$
DIRemover | - | $0.917_{\pm 0.008}$ | $-0.017_{\pm 0.017}$ | - | $0.922_{\pm 0.003}$ | $-0.034_{\pm 0.003}$ | - | $0.959_{\pm 0.004}$ | $-0.086_{\pm 0.003}$ | - | $0.959_{\pm 0.004}$ | $-0.183_{\pm 0.014}$
FairReprogram (Soft / Border) | 0.0 | $0.919_{\pm 0.005}$ | $-0.018_{\pm 0.021}$ | 0.0 | $0.920_{\pm 0.004}$ | $-0.040_{\pm 0.002}$ | 0.1 | $0.961_{\pm 0.002}$ | $-0.093_{\pm 0.005}$ | 2.0 | $0.961_{\pm 0.005}$ | $-0.171_{\pm 0.005}$
0.5 | $0.911_{\pm 0.007}$ | $-0.012_{\pm 0.018}$ | 0.1 | $0.916_{\pm 0.007}$ | $-0.026_{\pm 0.007}$ | 0.5 | $0.959_{\pm 0.005}$ | $-0.087_{\pm 0.006}$ | 5.0 | $0.951_{\pm 0.007}$ | $-0.167_{\pm 0.004}$
5.0 | $0.913_{\pm 0.008}$ | $-0.009_{\pm 0.011}$ | 10.0 | $0.918_{\pm 0.005}$ | $-0.042_{\pm 0.006}$ | 1.0 | $0.952_{\pm 0.007}$ | $-0.078_{\pm 0.005}$ | 10.0 | $0.933_{\pm 0.003}$ | $-0.163_{\pm 0.003}$
20.0 | $0.901_{\pm 0.014}$ | $-0.005_{\pm 0.023}$ | 20.0 | $0.917_{\pm 0.006}$ | $-0.025_{\pm 0.012}$ | 2.0 | $0.929_{\pm 0.003}$ | $-0.075_{\pm 0.004}$ | 20.0 | $0.926_{\pm 0.004}$ | $-0.162_{\pm 0.005}$
100.0 | $0.907_{\pm 0.011}$ | $-0.001_{\pm 0.003}$ | 50.0 | $0.917_{\pm 0.004}$ | $-0.011_{\pm 0.010}$ | 5.0 | $0.911_{\pm 0.002}$ | $-0.072_{\pm 0.002}$ | 30.0 | $0.918_{\pm 0.002}$ | $-0.161_{\pm 0.003}$
FairReprogram (Hard / Patch) | 0.0 | $0.908_{\pm 0.008}$ | $-0.010_{\pm 0.016}$ | 0.0 | $0.920_{\pm 0.007}$ | $-0.039_{\pm 0.001}$ | 0.1 | $0.955_{\pm 0.004}$ | $-0.088_{\pm 0.004}$ | 2.0 | $0.955_{\pm 0.004}$ | $-0.178_{\pm 0.011}$
0.1 | $0.908_{\pm 0.011}$ | $-0.008_{\pm 0.022}$ | 20.0 | $0.918_{\pm 0.005}$ | $-0.034_{\pm 0.002}$ | 0.5 | $0.950_{\pm 0.005}$ | $-0.078_{\pm 0.007}$ | 5.0 | $0.946_{\pm 0.008}$ | $-0.161_{\pm 0.009}$
10.0 | $0.906_{\pm 0.012}$ | $-0.007_{\pm 0.019}$ | 200.0 | $0.907_{\pm 0.015}$ | $-0.023_{\pm 0.017}$ | 1.0 | $0.934_{\pm 0.005}$ | $-0.060_{\pm 0.003}$ | 10.0 | $0.934_{\pm 0.004}$ | $-0.152_{\pm 0.007}$
30.0 | $0.894_{\pm 0.017}$ | $-0.003_{\pm 0.021}$ | 600.0 | $0.902_{\pm 0.013}$ | $-0.016_{\pm 0.014}$ | 2.0 | $0.917_{\pm 0.003}$ | $-0.040_{\pm 0.008}$ | 20.0 | $0.917_{\pm 0.002}$ | $-0.139_{\pm 0.012}$
100.0 | $0.893_{\pm 0.015}$ | $-0.002_{\pm 0.017}$ | 1200.0 | $0.901_{\pm 0.017}$ | $-0.014_{\pm 0.011}$ | 5.0 | $0.890_{\pm 0.001}$ | $-0.019_{\pm 0.002}$ | 30.0 | $0.890_{\pm 0.001}$ | $-0.121_{\pm 0.005}$

We further compare our method with four extra post-processing fairness-
promoting baselines.

$\bullet$ EqOdds [22]: Method that alters model predictions to meet equalized
odds by solving a linear program.

$\bullet$ CaliEqOdds [71]: Method that optimizes the model outputs to achieve
a relaxed equalized odds objective together with calibration with information
withholding.

$\bullet$ RejectOption [27]: Method that tunes model outputs with more
favorable labels to minority groups (vice versa) in the low confidence region
of classifiers to achieve better demographic parity.

$\bullet$ DIRemover [72]: Disparate impact remover is proposed as a pre-
processing fairness promoting method, which modifies input features with rank-
ordering preserving operations. We simply apply the method to modify model
predictions as a post-processing method to promote demographic parity.

EqOdds, CaliEqOdds and RejectOption are trained on the tuning set and then
applied on testing set while DIRemover directly tune the model predictions on
the testing set. We use the implementation [73] for all four baselines.

The results can be seen in Table 3. We see that our method consistently
outperforms these baselines with improved fairness-accuracy trade-off. For
example, we see that FairReprogram (Border) can achieve -0.167 negative EO and
0.951 accuracy in CelebA with $\lambda=5.0$. By contrast, the best-performing
post-processing baseline achieves much worse accuracy (0.927). Similar
comparisons can also be seen in Civil Comments, where the best post-processing
baseline can achieve -0.031 negative EO score and 0.915 accuracy, while our
method FairReprogram (Soft) can achieve -0.011 negative EO with 0.917 accuracy
with $\lambda=50.0$.

###  B.2 Experiments with Additional MMD Baselines

To partial out the instability of the adversarial training, we further compare
our method with MMD method, where the adversarial loss $\mathcal{L}_{fair}$ in
Eq. (3) is replaced with the Maximum Mean Discrepancy regularization [70].
Specifically, we consider MmdIn and MmdPost, where model parameters are
trained from scratch in an in-processing manner and fine-tuned in a post-
processing manner, respectively, following the settings for adversarial
training in Section 4.1. The experiment results on the Civil Comments dataset
are presented in Fig. 10. As we can see, our proposed method FairReprogram
outperforms the MMD baselines, which can alleviate the concern that fairness
reprogramming has a better performance simply because of the instability of
adversarial training of the baselines.

(a) (b)

Figure 10:  Results on Civil Comments with the new MMD baseline. We report the
negative DP (left) and the negative EO (right) scores. For each method, we
vary the trade-off parameter $\lambda$ (as shown in (3)) to record the
performance. The closer a dot to the upper-right corner, the better the model
is. We consider four different $\lambda$s for each method. The solid curve is
the fitted polynomial with order 30.

###  B.3 Black-box FairReprogram Generation

Previous experiments are all based on the white-box setting, which assumes
access to the complete model information, such as model architectures and
parameters. This precludes the use case of reprogramming a well-trained but
access-limited model, _e.g._ , a commercial APIs or other query-based software
[9]. Thus, we further explore the feasibility of our method in the black-box
setup [9, 74], where the gradients of the pre-trained model are estimated
using only function queries. We follow the general black-box setting in [9]
and adopt a query number of 30. The results are summarized in Fig. 11. As we
can see, out algorithm can still improve the fairness without the knowledge of
the model information. However, in such a case, the gain in fairness would
sacrifice the accuracy largely when compared to our baselines. While in the
future work, we will try to mitigate such degradation using more query
numbers[9] and coordinate gradient estimation (CGE) [74] to achieve more
accurate gradient estimation.

Figure 11: Performance of FairReprogram in the black-box setting. The left
Performance of the triggers trained in the black-box setting. Both the
reprogrammer and the adversary are trained with query-based estimated
gradients. Different data samples represent different

###  B.4 Results with Standard Derivation

The numerical results in Figs. 3, 4 and 9 with standard derivation are
correspondingly presented in Tabs 3, 4 and 5.

Table 4:  Numerical results with standard derivation on Civil Comments and
CelebA with different tuning data ratio, corresponding to Fig. 4. All reported
results are the average of three different random runs. We report the negative
DP and the negative EO scores correspondingly for the “Fairness” column. We
consider a fixed Base model trained with the training set, whose negative bias
scores are presented as a black dashed line. Then we train other methods with
different tuning data ratios to promote fairness of the Base model.

Method | Tuning Data Ratio | Civil Comments | CelebA
---|---|---|---
Demographic parity | Equalized odds | Demographic parity | Equalized odds
Accuracy | Fairness | Accuracy | Fairness | Accuracy | Fairness | Accuracy | Fairness
ERM | - | $0.922_{\pm 0.004}$ | $-0.036_{\pm 0.025}$ | $0.923_{\pm 0.004}$ | $-0.054_{\pm 0.005}$ | $0.961_{\pm 0.004}$ | $-0.094_{\pm 0.002}$ | $0.961_{\pm 0.004}$ | $-0.231_{\pm 0.008}$
AdvPost | 1.0 | $0.909_{\pm 0.011}$ | $-0.007_{\pm 0.032}$ | $0.888_{\pm 0.022}$ | $-0.000_{\pm 0.028}$ | $0.908_{\pm 0.005}$ | $-0.067_{\pm 0.005}$ | $0.905_{\pm 0.004}$ | $-0.150_{\pm 0.007}$
0.5 | $0.923_{\pm 0.005}$ | $-0.044_{\pm 0.009}$ | $0.919_{\pm 0.005}$ | $-0.053_{\pm 0.008}$ | $0.915_{\pm 0.007}$ | $-0.069_{\pm 0.007}$ | $0.911_{\pm 0.006}$ | $-0.162_{\pm 0.013}$
0.2 | $0.923_{\pm 0.004}$ | $-0.038_{\pm 0.017}$ | $0.919_{\pm 0.006}$ | $-0.061_{\pm 0.004}$ | $0.939_{\pm 0.002}$ | $-0.075_{\pm 0.006}$ | $0.929_{\pm 0.005}$ | $-0.171_{\pm 0.010}$
0.1 | $0.917_{\pm 0.007}$ | $-0.038_{\pm 0.015}$ | $0.918_{\pm 0.011}$ | $-0.056_{\pm 0.013}$ | $0.943_{\pm 0.003}$ | $-0.083_{\pm 0.004}$ | $0.933_{\pm 0.007}$ | $-0.178_{\pm 0.008}$
0.01 | $0.922_{\pm 0.002}$ | $-0.041_{\pm 0.014}$ | $0.920_{\pm 0.010}$ | $-0.060_{\pm 0.014}$ | $0.948_{\pm 0.005}$ | $-0.089_{\pm 0.005}$ | $0.948_{\pm 0.003}$ | $-0.202_{\pm 0.012}$
0.001 | $0.917_{\pm 0.005}$ | $-0.083_{\pm 0.018}$ | $0.921_{\pm 0.006}$ | $-0.060_{\pm 0.009}$ | $0.951_{\pm 0.007}$ | $-0.091_{\pm 0.005}$ | $0.955_{\pm 0.002}$ | $-0.229_{\pm 0.005}$
FairReprogram (Soft/Border) | 1.0 | $0.917_{\pm 0.003}$ | $-0.002_{\pm 0.001}$ | $0.917_{\pm 0.004}$ | $-0.011_{\pm 0.010}$ | $0.935_{\pm 0.003}$ | $-0.066_{\pm 0.003}$ | $0.907_{\pm 0.004}$ | $-0.153_{\pm 0.009}$
0.5 | $0.905_{\pm 0.009}$ | $-0.002_{\pm 0.004}$ | $0.922_{\pm 0.005}$ | $-0.018_{\pm 0.013}$ | $0.941_{\pm 0.003}$ | $-0.070_{\pm 0.003}$ | $0.937_{\pm 0.003}$ | $-0.162_{\pm 0.008}$
0.2 | $0.911_{\pm 0.013}$ | $-0.002_{\pm 0.006}$ | $0.917_{\pm 0.008}$ | $-0.017_{\pm 0.011}$ | $0.947_{\pm 0.003}$ | $-0.074_{\pm 0.005}$ | $0.935_{\pm 0.005}$ | $-0.162_{\pm 0.011}$
0.1 | $0.905_{\pm 0.010}$ | $-0.001_{\pm 0.005}$ | $0.917_{\pm 0.000}$ | $-0.025_{\pm 0.007}$ | $0.951_{\pm 0.005}$ | $-0.079_{\pm 0.004}$ | $0.951_{\pm 0.006}$ | $-0.177_{\pm 0.009}$
0.01 | $0.911_{\pm 0.007}$ | $-0.003_{\pm 0.004}$ | $0.918_{\pm 0.005}$ | $-0.033_{\pm 0.017}$ | $0.958_{\pm 0.003}$ | $-0.087_{\pm 0.002}$ | $0.959_{\pm 0.003}$ | $-0.197_{\pm 0.003}$
0.001 | $0.908_{\pm 0.176}$ | $-0.009_{\pm 0.042}$ | $0.921_{\pm 0.181}$ | $-0.044_{\pm 0.013}$ | $0.957_{\pm 0.008}$ | $-0.091_{\pm 0.003}$ | $0.959_{\pm 0.002}$ | $-0.221_{\pm 0.008}$
FairReprogram (Hard/Patch) | 1.0 | $0.897_{\pm 0.012}$ | $-0.005_{\pm 0.004}$ | $0.905_{\pm 0.006}$ | $-0.009_{\pm 0.007}$ | $0.938_{\pm 0.005}$ | $-0.065_{\pm 0.014}$ | $0.931_{\pm 0.002}$ | $-0.154_{\pm 0.004}$
0.5 | $0.905_{\pm 0.014}$ | $-0.006_{\pm 0.026}$ | $0.917_{\pm 0.006}$ | $-0.028_{\pm 0.007}$ | $0.932_{\pm 0.002}$ | $-0.062_{\pm 0.002}$ | $0.937_{\pm 0.004}$ | $-0.164_{\pm 0.006}$
0.2 | $0.902_{\pm 0.013}$ | $-0.006_{\pm 0.017}$ | $0.909_{\pm 0.020}$ | $-0.025_{\pm 0.020}$ | $0.941_{\pm 0.003}$ | $-0.073_{\pm 0.005}$ | $0.945_{\pm 0.005}$ | $-0.166_{\pm 0.013}$
0.1 | $0.900_{\pm 0.014}$ | $-0.005_{\pm 0.016}$ | $0.909_{\pm 0.008}$ | $-0.024_{\pm 0.011}$ | $0.948_{\pm 0.006}$ | $-0.079_{\pm 0.003}$ | $0.951_{\pm 0.002}$ | $-0.183_{\pm 0.008}$
0.01 | $0.896_{\pm 0.013}$ | $-0.004_{\pm 0.010}$ | $0.918_{\pm 0.003}$ | $-0.035_{\pm 0.005}$ | $0.967_{\pm 0.007}$ | $-0.087_{\pm 0.004}$ | $0.955_{\pm 0.004}$ | $-0.192_{\pm 0.010}$
0.001 | $0.907_{\pm 0.007}$ | $-0.008_{\pm 0.012}$ | $0.921_{\pm 0.000}$ | $-0.042_{\pm 0.001}$ | $0.955_{\pm 0.004}$ | $-0.089_{\pm 0.005}$ | $0.958_{\pm 0.005}$ | $-0.228_{\pm 0.013}$

Table 5:  Numerical results with standard derivation on Civil Comments and
CelebA with different trigger size, corresponding to Fig. 9. We evaluate the
bias scores with different trigger word numbers (Civil Comments) and different
trigger size (CelebA) with fixed adversary weight $\lambda$. All reported
results are the average of three random runs. We report the negative DP and
the negative EO scores correspondingly for the “Fairness” column.

Method | Trigger Size | Civil Comments | Trigger Size | CelebA
---|---|---|---|---
Demographic parity | Equalized odds | Demographic parity | Equalized odds
Accuracy | Fairness | Accuracy | Fairness | Accuracy | Fairness | Accuracy | Fairness
ERM | - | $0.922_{\pm 0.004}$ | $-0.036_{\pm 0.025}$ | $0.923_{\pm 0.004}$ | $-0.054_{\pm 0.005}$ | - | $0.961_{\pm 0.004}$ | $-0.094_{\pm 0.002}$ | $0.961_{\pm 0.004}$ | $-0.231_{\pm 0.008}$
FairReprogram (Soft/Border) | 20 | $0.890_{\pm 0.011}$ | $-0.001_{\pm 0.000}$ | $0.910_{\pm 0.005}$ | $-0.004_{\pm 0.001}$ | 30 | $0.914_{\pm 0.002}$ | $-0.054_{\pm 0.008}$ | $0.903_{\pm 0.005}$ | $-0.155_{\pm 0.005}$
10 | $0.906_{\pm 0.004}$ | $-0.002_{\pm 0.001}$ | $0.906_{\pm 0.004}$ | $-0.009_{\pm 0.010}$ | 25 | $0.933_{\pm 0.003}$ | $-0.061_{\pm 0.006}$ | $0.917_{\pm 0.003}$ | $-0.162_{\pm 0.009}$
5 | $0.917_{\pm 0.003}$ | $-0.002_{\pm 0.001}$ | $0.917_{\pm 0.004}$ | $-0.011_{\pm 0.010}$ | 20 | $0.939_{\pm 0.006}$ | $-0.070_{\pm 0.009}$ | $0.923_{\pm 0.007}$ | $-0.170_{\pm 0.008}$
2 | $0.912_{\pm 0.002}$ | $-0.007_{\pm 0.001}$ | $0.921_{\pm 0.002}$ | $-0.038_{\pm 0.009}$ | 15 | $0.943_{\pm 0.004}$ | $-0.074_{\pm 0.06}$ | $0.951_{\pm 0.004}$ | $-0.189_{\pm 0.011}$
1 | $0.917_{\pm 0.001}$ | $-0.011_{\pm 0.000}$ | $0.920_{\pm 0.000}$ | $-0.051_{\pm 0.002}$ | 10 | $0.951_{\pm 0.004}$ | $-0.081_{\pm 0.008}$ | $0.958_{\pm 0.008}$ | $-0.222_{\pm 0.012}$
FairReprogram (Hard/Patch) | 20 | $0.890_{\pm 0.002}$ | $-0.001_{\pm 0.001}$ | $0.892_{\pm 0.001}$ | $-0.005_{\pm 0.005}$ | 70 | $0.912_{\pm 0.005}$ | $-0.048_{\pm 0.005}$ | $0.932_{\pm 0.003}$ | $-0.151_{\pm 0.006}$
10 | $0.891_{\pm 0.009}$ | $-0.001_{\pm 0.003}$ | $0.901_{\pm 0.002}$ | $-0.016_{\pm 0.005}$ | 60 | $0.937_{\pm 0.008}$ | $-0.056_{\pm 0.004}$ | $0.947_{\pm 0.004}$ | $-0.160_{\pm 0.011}$
5 | $0.897_{\pm 0.012}$ | $-0.005_{\pm 0.004}$ | $0.905_{\pm 0.006}$ | $-0.009_{\pm 0.007}$ | 50 | $0.935_{\pm 0.002}$ | $-0.061_{\pm 0.008}$ | $0.954_{\pm 0.004}$ | $-0.172_{\pm 0.012}$
2 | $0.905_{\pm 0.007}$ | $-0.006_{\pm 0.005}$ | $0.911_{\pm 0.002}$ | $-0.030_{\pm 0.007}$ | 40 | $0.944_{\pm 0.006}$ | $-0.074_{\pm 0.010}$ | $0.959_{\pm 0.008}$ | $-0.191_{\pm 0.009}$
1 | $0.913_{\pm 0.002}$ | $-0.012_{\pm 0.001}$ | $0.921_{\pm 0.003}$ | $-0.051_{\pm 0.001}$ | 30 | $0.958_{\pm 0.004}$ | $-0.091_{\pm 0.007}$ | $0.958_{\pm 0.002}$ | $-0.204_{\pm 0.013}$

###  B.5 Transfer experiments with different tasks and model architectures

We further test the transferability of reprogramming to different tasks and
model architectures as shown in Fig. 12. Specifically, for transfer setting,
the reprogram is optimized on the (ResNet-18, CelebA) with the task of
predicting the hair color, and evaluated on (ResNet-20, CelebA) with the task
of predicting smiling. For both tasks, the attribute gender is chosen as the
demographic information throughout the experiments. We can see that the
trigger still has good transferability with different model architectures.
Meanwhile, we find that the triggers are able to boost the fairness of the
model in the task-transfer setting, but the accuracy is traded off more than
the original setting.

(a) (b)

Figure 12: Results of the transferability experiment on CelebA dataset with
different tasks and model architectures. In each figure, we compare the
reprogramming in the transferred setting (curves denoted with ‘transfer’) with
the reprogram directly trained on the target task. For transfer setting, the
reprogram is optimized on the (ResNet-18, CelebA) with the task of predicting
the hair color, and evaluated on (ResNet-20, CelebA) with the task of
predicting smiling. For both tasks, the attribute gender is chosen as the
demographic information throughout the experiments.

###  B.6 Experiments on Reprogramming Tabular Data

We show that FairReprogram could also be applied to tabular data. For
reprogramming, there are many ways to design triggers according to different
tasks and requirements. Unlike NLP, where we append the trigger to the input
or embeddings, the model for tabular data is sensitive to the input size. As
the tabular data have a fixed input size, we can directly apply the additive
trigger to the input data to keep the input dimension unchanged (i.e., adding
a perturbation on the original input), just as we adopted in image domains in
Fig. 1.b. To verify our argument, we conducted additional experiments on the
UCI Adult dataset [75] with a two-layer MLP model, and the results are shown
in Fig. 13. Our method achieves comparable debiasing performance with the
post-processing adversarial training method without modifying any model
parameters. The results suggest that our method could effectively improve
model fairness for tabular data.

(a) (b)

Figure 13:  Results on Adult. We report the negative DP (left) and the
negative EO (right) scores. For each method, we vary the trade-off parameter
$\lambda$ (as shown in (3)) to record the performance. The closer a dot to the
upper-right corner, the better the model is. We consider six different
$\lambda$s for each method. The solid curve is the fitted polynomial with
order 30.

##  Appendix C Theoretical Proofs

In this section, we will provide formal proofs to the claims and theorem in
the main paper.

###  C.1 Sufficient Statistics

We will show that $p_{Y}(\cdot|\bm{X}^{(y)})$ and $p_{Z}(\cdot|\bm{X}^{(z)})$
are the sufficient statistics of $\bm{X}^{(y)}$ and $\bm{X}^{(z)}$
respectively for inferring $Y$. Formally, what we need to show is

$\small p(Y|\bm{X}^{(y)})=p(Y|p_{Y}(\cdot|\bm{X}^{(y)}))$ (9)

and

$\small p(Y|\bm{X}^{(z)})=p(Y|p_{Z}(\cdot|\bm{X}^{(z)}))$ (10)

Eq. (9) is an identity. To show Eq. (10):

$\displaystyle p(Y|\bm{X}^{(z)})$ $\displaystyle=\mathbb{E}_{Z\sim
p_{Z}(\cdot|\bm{X}^{(z)})}[p(Y|Z,\bm{X}^{(z)})]$
$\displaystyle=\mathbb{E}_{Z\sim
p_{Z}(\cdot|\bm{X}^{(z)})}[p(Y|Z,p_{Z}(\cdot|\bm{X}^{(z)}))]$
$\displaystyle=\mathbb{E}_{Z\sim
p_{Z}(\cdot|p_{Z}(\cdot|\bm{X}^{(z)}))}[p(Y|Z,p_{Z}(\cdot|\bm{X}^{(z)}))]$
$\displaystyle=p(Y|p_{Z}(\cdot|\bm{X}^{(z)})).$

The second equality is because $Y$ and $\bm{X}^{(z)}$ are independent
conditional on $Z$, so replacing $\bm{X}^{(z)}$ with any functions of
$\bm{X}^{(z)}$ would not change the conditional probability. The third
equality is implied from the identity
$p(Z|\bm{X}^{(z)})=p(Z|p_{Z}(\cdot|\bm{X}^{(z)}))$.

Using the sufficient statistics, it is very easy to show that $p(Y|\bm{X})$ is
a special case of Eq. (6):

$p(Y|\bm{X})=p(Y|\bm{X}^{(y)},\bm{X}^{(z)})=p(Y|p_{Y}(\cdot|\bm{X}^{(y)}),p_{Z}(\cdot|\bm{X}^{(z)})).$

###  C.2 Proof to Thm. 1

We first provide the regularity conditions as stated in Thm. 1.

  1. 1.

Conditional Independence. The features in $\bm{X}^{(y)}$ and $\bm{X}^{(z)}$
are independent and identically distributed conditional on $Y$ and $Z$
respectively.

$\small p^{tr}(\bm{X}^{(y)}|Y)=\prod_{t}p^{tr}(\bm{X}^{(y)}_{t}|Y),\quad
p^{tr}(\bm{X}^{(z)}|Z)=\prod_{t}p^{tr}(\bm{X}^{(z)}_{t}|Z).$ (11)

  2. 2.

_Infrequent Strong Demographic Features._ The probability of occurrence of
features that are very strongly indicative against a certain demographic group
is low. Formally $\forall z$, $\forall\varepsilon>0$, $\exists\sigma>0$, such
that define

$\small\mathcal{S}(\sigma)=\\{\bm{x}^{(z)}\in\mathcal{X}^{(z)}:p(Z=z|\bm{X}^{(z)}=\bm{x}^{(z)})\leq\sigma\\},$
(12)

we have

$\small p(\bm{X}^{(z)}\in\mathcal{S}(\sigma))\leq\varepsilon.$ (13)

  3. 3.

_Continuous Classifier._ $h(\cdot,\cdot)$ is continuous with respect to both
arguments.

With these assumptions, we will state the following lemma.

######  Lemma 1.1.

Consider the case where $Z$ takes on $K$ different values, _i.e._ , there are
$K$ demographic groups. Then

$\small\lim_{p^{tr}(Z=z|\bm{X}_{0}^{(z)}=\bm{\delta})\rightarrow
1}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=\tilde{\bm{X}}^{(z)})),Y)=H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y),$
(14)

where $c$ is a K-dimensional one-hot vector with the $z$-th dimension equal to
1 and 0 elsewhere.

###### Proof.

According to Assumption 13 (Eq. (13)),

$\forall\varepsilon>0,\quad\exists 0<\sigma<1,\quad
p(\bm{X}^{(z)}\in\mathcal{S}(\sigma))\leq\frac{\varepsilon}{4H(Z)},$ (15)

where $\mathcal{S}(\sigma)$ is defined in Eq. (12). On the other hand,
consider the following composite function

$\small
H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])),Y).$
(16)

Note that this is _different_ from
$H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=\tilde{\bm{X}}^{(z)})),Y)$,
which is essentially the expectation of Eq. (16) over different values of
$\bm{x}^{(z)}$.

Since the conditional entropy is continuous and bounded, and $h(\cdot,\cdot)$
is continuous over both of its arguments with finite support, Eq. (16) is
_uniformly_ continuous with respect to $p^{tr}_{Z}(\cdot|\bm{X}^{(z)}))$.
Therefore, given the aforementioned $\varepsilon$,

$\displaystyle\exists 0<\eta<1,\quad\forall\bm{\delta},\bm{x}^{(z)}\mbox{ s.t.
}\|p_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])-c\|_{1}\leq\eta$ (17)
$\displaystyle\Rightarrow\Big{|}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])),Y)-H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)\Big{|}\leq\frac{\varepsilon}{2}.$

Now, divide the support of $\bm{X}^{(z)}$ into two disjoint sets. For
notational conciseness, define

$\small r(\bm{x}^{(z)})=\max_{z^{\prime}\neq
z}\frac{p^{tr}(Z=z^{\prime})p^{tr}(\bm{X}^{(z)}=\bm{x}^{(z)}|Z=z^{\prime})}{p^{tr}(Z=z)p^{tr}(\bm{X}^{(z)}=\bm{x}^{(z)}|Z=z)}.$
(18)

Then the two sets, denoted as $\mathcal{A}$ and $\mathcal{B}$ respectively,
are divided according to whether $r(\bm{x}^{(z)})$ exceeds a threshold, _i.e._

$\small\mathcal{A}=\\{\bm{x}^{(z)}\in\mathcal{X}^{(z)}:r(\bm{x}^{(z)})\leq\sigma^{-1}-1\\},\quad\mathcal{B}=\\{\bm{x}^{(z)}\in\mathcal{X}^{(z)}:r(\bm{x}^{(z)})>\sigma^{-1}-1\\}.$
(19)

$\forall\bm{x}^{(z)}\in\mathcal{A}$, define

$\small\zeta=1-\left[\frac{(1-\eta/2)^{-1}-1}{(K-1)(\sigma^{-1}-1)G}+1\right]^{-1},\quad\mbox{where
}G=\max_{z^{\prime}\neq z}\frac{p(Z=z)}{p(Z=z^{\prime})}.$ (20)

Then we will show that

$\small\forall\bm{x}^{(z)}\in\mathcal{A},\forall\bm{\delta}\mbox{ s.t.
}p^{tr}(Z=z|\bm{X}_{0}^{(z)}=\bm{\delta})\geq
1-\zeta\quad\Rightarrow\quad\|p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])-c\|_{1}\leq\eta,$
(21)

and hence Eq. (17) holds. This is because, according to the Bayesian rule,

$\small
p^{tr}(Z=z|\bm{X}_{0}^{(z)}=\bm{\delta})=\frac{p^{tr}(Z=z)p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z)}{\sum_{z^{\prime}\neq
z}p^{tr}(Z=z^{\prime})p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z^{\prime})}.$
(22)

Therefore

$\displaystyle p^{tr}(Z=z|\bm{X}_{0}^{(z)}=\bm{\delta})\geq 1-\zeta$
$\displaystyle\Rightarrow\quad 1+\sum_{z^{\prime}\neq
z}\frac{p^{tr}(Z=z^{\prime})p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z^{\prime})}{p^{tr}(Z=z)p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z)}\leq(1-\zeta)^{-1}$
(23)
$\displaystyle\Rightarrow\quad\frac{p^{tr}(Z=z^{\prime})p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z^{\prime})}{p^{tr}(Z=z)p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z)}\leq(1-\zeta)^{-1}-1,\forall
z^{\prime}\neq z$
$\displaystyle\Rightarrow\quad\frac{p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z^{\prime})}{p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z)}\leq
G[(1-\zeta)^{-1}-1],\forall z^{\prime}\neq z.$

As a result,

$\displaystyle p^{tr}(Z=z|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])^{-1}$
$\displaystyle=1+\sum_{z^{\prime}\neq
z}\frac{p^{tr}(Z=z^{\prime})p^{tr}(\bm{X}^{(z)}=\bm{x}^{(z)}|Z=z^{\prime})p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z^{\prime})}{p^{tr}(Z=z)p^{tr}(\bm{X}^{(z)}=\bm{x}^{(z)}|Z=z)p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z)}$
(24) $\displaystyle\leq 1+r(\bm{x}^{z})\sum_{z^{\prime}\neq
z}\frac{p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z^{\prime})}{p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z)}$
$\displaystyle\leq 1+(\sigma^{-1}-1)\sum_{z^{\prime}\neq
z}\frac{p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z^{\prime})}{p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z)}$
$\displaystyle\leq 1+(\sigma^{-1}-1)(K-1)G[(1-\zeta)^{-1}-1]=(1-\eta/2)^{-1},$

where the first line is implied from the Bayesian rule and assumption 11
(similar to Eq. (22)); the second line is implied from the definition of
$r(\bm{x}^{z})$ as in Eq. (18); the third line is due to the definition of set
$\mathcal{A}$ as in Eq. (19) (note that the scope of Eq. (21) is confined to
$\forall\bm{x}^{(z)}\in\mathcal{A}$); the last line is implied from Eq. (23)
and the definition of $\zeta$ as in Eq. (20).

It then follows that

$\displaystyle\|p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])-c\|_{1}$
$\displaystyle=1-p^{tr}(Z=z|\bm{X}^{(z)})+\sum_{z^{\prime}\neq^{\prime}}p^{tr}(Z=z^{\prime}|\bm{X}^{(z)})$
(25) $\displaystyle=2(1-p^{tr}(Z=z|\bm{X}^{(z)}))$ $\displaystyle\leq\eta,$

where the first line is implied from the definition of the one-hot vector $c$
as well as the fact that the probability mass function is alwasy between 0 and
1; the second line is given by the fact that any probability mass functions
sum to 1; and the last line is given by Eq. (24). This concludes the proof to
Eq. (21).

Next, notice that

$\displaystyle
H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=\tilde{\bm{X}}^{(z)})),Y)$
(26) $\displaystyle=$
$\displaystyle\sum_{\bm{x}^{(z)}\in\mathcal{X}^{(z)}}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])),Y)p(\bm{X}^{(z)}=\bm{x}^{(z)})$
$\displaystyle=$
$\displaystyle\sum_{\bm{x}^{(z)}\in\mathcal{A}}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])),Y)p(\bm{X}^{(z)}=\bm{x}^{(z)})$
$\displaystyle+\sum_{\bm{x}^{(z)}\in\mathcal{B}}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])),Y)p(\bm{X}^{(z)}=\bm{x}^{(z)}).$

Thus

$\displaystyle\Big{|}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}-\tilde{\bm{X}}^{(z)})),Y)-H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)\Big{|}$
(27) $\displaystyle=$
$\displaystyle\sum_{\bm{x}^{(z)}\in\mathcal{A}}\Big{|}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])),Y)-H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)\Big{|}p(\bm{X}^{(z)}=\bm{x}^{(z)})$
$\displaystyle+$
$\displaystyle\sum_{\bm{x}^{(z)}\in\mathcal{B}}\Big{|}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])),Y)-H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)\Big{|}p(\bm{X}^{(z)}=\bm{x}^{(z)})$

In the following, we will bound the two terms respectively. For the first term
in Eq. (27), Eq. (21) applies because $\bm{x}^{(z)}\in\mathcal{A}$. Therefore,
according to Eq. (21) and (17), when
$p^{tr}(Z=z|\bm{X}_{0}^{(z)}=\bm{\delta})\geq 1-\zeta$, we have

$\displaystyle\sum_{\bm{x}^{(z)}\in\mathcal{A}}\Big{|}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])),Y)-H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)\Big{|}p(\bm{X}^{(z)}=\bm{x}^{(z)})$
(28) $\displaystyle\leq$
$\displaystyle\sum_{\bm{x}^{(z)}\in\mathcal{A}}\frac{\varepsilon}{2}p(\bm{X}^{(z)}=\bm{x}^{(z)})\leq\frac{\varepsilon}{2}.$

For the second term, notice that when $\bm{x}^{(z)}\in\mathcal{B}$,
$r(\bm{x}^{(z)})>\sigma^{-1}-1$ (according to Eq. (19)). So it follows that

$\displaystyle p(Z=z|\bm{X}^{(z)}=\bm{x}^{(z)})^{(-1)}$
$\displaystyle=1+\sum_{z^{\prime}\neq
z}\frac{p^{tr}(Z=z^{\prime})p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z^{\prime})}{p^{tr}(Z=z)p^{tr}(\bm{X}_{0}^{(z)}=\bm{\delta}|Z=z)}$
(29) $\displaystyle\geq 1+r(\bm{x}^{(z)})\geq\sigma^{-1}$

According to (15), this implies

$\small p(\bm{X}^{(z)}\in\mathcal{B})\leq
p(\bm{X}^{(z)}\in\mathcal{S}(\sigma))\leq\frac{\varepsilon}{4H(Z)},$ (30)

and further

$\displaystyle\sum_{\bm{x}^{(z)}\in\mathcal{B}}\Big{|}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])),Y)-H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)\Big{|}p(\bm{X}^{(z)}=\bm{x}^{(z)})$
(31) $\displaystyle\leq$
$\displaystyle\Big{[}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=[\bm{\delta},\bm{x}^{(z)}])),Y)+H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)\Big{]}p(\bm{X}^{(z)}=\bm{x}^{(z)})$
$\displaystyle\leq$ $\displaystyle
2H(Z)p(\bm{X}^{(z)}=\bm{x}^{(z)})\leq\frac{\varepsilon}{2}.$

Plugging Eqs. (28) and (31) into Eq. (27), we can finally establish that
$\forall\varepsilon>0$, $\exists\zeta>0$ (one possible $\zeta$ as defined in
Eq. (20)), when $p^{tr}(Z=z|\bm{X}_{0}^{(z)}=\bm{\delta})\geq 1-\zeta$, we
have

$\small\Big{|}H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}-\tilde{\bm{X}}^{(z)})),Y)-H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)\Big{|}\leq\varepsilon.$
(32)

Hence this concludes the proof to Lemma 1.1. ∎

With Lemma 1.1, we are ready to prove Thm 1.

###### Proof.

Note that

$\displaystyle H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)\geq
H(Z|p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),Y)=H(Z|Y).$ (33)

The inequality sign is given by the data processing inequality; the equality
is given by the fact that $Z$ and $\bm{X}^{(y)}$ are independent conditional
on $Y$. On the other hand,

$\small H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)\leq H(Z|Y).$ (34)

Combining Eqs. (33) and (34), we have

$\small H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)=H(Z|Y).$ (35)

According to Lemma 1.1, when
$p^{tr}(Z=z|\bm{X}_{0}^{(z)}=\bm{\delta})\rightarrow 1$,

$\displaystyle
H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),p^{tr}_{Z}(\cdot|\bm{X}^{(z)}=\tilde{\bm{X}}^{(z)})),Y)$
$\displaystyle\rightarrow H(Z|h(p^{tr}_{Y}(\cdot|\bm{X}^{(y)}),c),Y)=H(Z|Y).$
(36)

∎

###  C.3 Discussion on Feature Disentanglement Assumption

In Section 3.4, we made a simplifying assumption that all features could be
divided into two disentangled groups, _i.e._ ,
$\bm{X}=[\bm{X}^{y},\bm{X}^{z}]$, which are governed by the output label $Y$
and demographic information $Z$, respectively. The corresponding data
generation process could be seen in Figure 2. On the other hand, however, if
features are entangled in practice, we show that FairReprogram can still
provide false demographic information to overshadow the true demographics in
Table 1.

##  Appendix D Broader Impact

Although there has been a proliferation of works in promoting ML fairness,
most methods require training or finetuning the existing models to meet
certain fairness notions. However, this could bring large computational and
storage costs, low data efficiency, and model privacy issues with those large-
scaled trained models.

Inspired by recent advances in model reprogramming techniques, we propose a
new generic post-processing fairness learning framework. Specifically, we
consider a fixed ML model and optimize a fairness trigger that is appended to
the inputs with a min-max formulation. The proposed method enjoys a better
fairness-accuracy trade-off compared with vast fairness promoting baselines
with far less training costs.

Despite the effectiveness of our method, we note that our method still has
some limitations. As a future research remark, our method still requires
demographic annotations to remove biases, which could be hard to acquire in
practice. It remains an open problem to develop a fairness-promoting technique
without the use of demographics annotations.

We do not observe any potential negative societal impacts of our method.
Instead, we believe that the outcome of our work could help enhance fairness
of AI systems in a computationally-efficient and constraint-least manner. It
can also provide broad positive impacts on diverse areas where AI techniques
are applied.