# Investigating transformers in the
decomposition of polygonal shapes as point collections

Andrea Alfieri  Yancong Lin  Jan C. van Gemert

###### Abstract

Transformers can generate predictions in two approaches: 1. auto-regressively
by conditioning each sequence element on the previous ones, or 2. directly
produce an output sequences in parallel. While research has mostly explored
upon this difference on sequential tasks in NLP, we study the difference
between auto-regressive and parallel prediction on visual set prediction
tasks, and in particular on polygonal shapes in images because polygons are
representative of numerous types of objects, such as buildings or obstacles
for aerial vehicles. This is challenging for deep learning architectures as a
polygon can consist of a varying carnality of points. We provide evidence on
the importance of natural orders for Transformers, and show the benefit of
decomposing complex polygons into collections of points in an auto-regressive
manner.

Figure 1: Points
Figure 2: Lines

Figure 3: Gates
Figure 4: Polygons

(a) Synthetic gate dataset.

Figure 5: Examples of point collections used in our paper.

##  1 Introduction

Predicting polygonal shapes in images is a high-level task that is
representative of many vision problems. One example is to automatically
extract vectorized building outlines from high-resolutions satellite images
[11, 12, 16, 20]. Similarly, polygon detection can be beneficial for vision-
based flight control of unmanned aerial vehicles (UAVs), as demonstrated in
the Autonomous Drone Racing [17], where drones fly autonomously through a
sequence of polygon-shaped gates purely relying on vision signals. The
performance of polygon detection is critical for UAVs as it directly affects
the precision of navigation.

In this work, we treat polygonal shape prediction as a _collection prediction_
task such as sequences and sets . Many kinds of data can be naturally
represented using collection and many machine learning tasks can be viewed as
a collection prediction problem, such as predicting the collection of points
of a polygon [36], detecting objects in an image [4, 35], estimating the pose
of humans by detecting a set of key-points [3, 29], or predicting multiple
labels for the same sample [26]. The difficulty in such problems arises for
two main reasons: because the _cardinality_ (i.e. the number of elements) of
the collection is unknown and can vary among different samples, and because
collections when treated as a set are _permutation-invariant_. However,
canonical convolutional neural networks are not able to tackle these problems
by design [19].

Transformers [30] have achieved impressive results on numerous collection
prediction tasks [4, 19], thanks to the attention module [1], a solution
capable of aggregating information from the entire collection while also
satisfying permutation invariance.

The work in [30] first presents Transformers as an auto-regressive sequence-
to-sequence model that generates a collection of output tokens one by one.
Numerous following works [5, 10, 14] introduce new variants of Transformers to
reduce compute latency. However, the vast majority of auto-regressive
Transformers focuses on sequential tasks only, such as machine translation
[10, 14] or speech recognition [5]. Recently, parallel Transformers have
successfully been applied into computer vision, especially in object detection
[4, 37], where the model outputs a set of bounding boxes _in parallel_.
However, parallel Transformers rely on computationally intensive strategies,
such as oversampling and Hungarian matching [18].

The difference between auto-regressive and parallel Transformers is
fundamental. Let us consider an image containing a collection of three objects
(namely $A,B$ and $C$) which we are trying to detect. When asking a parallel
Transformer to learn this task, we are actually asking the model to learn the
joint probability of these three variables, conditioned on the model
parameters $\Theta$, namely:

$P(A,B,C\mid\Theta)$ (1)

In contrast, when the auto-regressive approach is presented with the same
task, what it needs to learn is the chain of conditional probability
distributions defined by:

$P(A\mid\Theta)\cdot P(B\mid A,\Theta)\cdot P(C\mid A,B,\Theta)$ (2)

In the second case, the Transformer is asked to produce one element of the
collection at a time, by exploiting information about the previous
predictions. This is similar to machine translation, in which the Transformer
outputs one word, conditioned on the previously generated output. Eq. (1) and
Eq. (2) are equal by definition of the general product rule of probability,
and Transformers are capable of modelling both. However, using Eq. (2) with
Transformers imposes an order even when there might not be a natural order
present.

In this work, we study the difference between auto-regressive and parallel
Transformers on polygonal shape prediction viewed as a collection of points,
including individual points, lines, gates and polygons, as shown in Fig. 5.
Our contributions are: $(1)$ We test auto-regressive and parallel models on
four collection prediction datasets and one sequential dataset to provide the
reader with a full picture of the advantages and disadvantages of both
approaches. $(2)$ We show that the conditional decomposition of the collection
can be beneficial for Transformers when there is an explicit order in the
elements of a set, such as predicting a collection of points on a line. $(3)$
we show empirically that the conditional decomposition benefits from a
particular order than others on a polygon dataset.

##  2 Related work

Polygonal shape detection: The work in [12] views satellite image mapping as a
polygon prediction task and makes use of a convolutional network to output the
polygon vertices directly. The work in [20] first detects bounding boxes of
buildings, and then uses recurrent networks to extract vectorized building
footprints. The work in [11] proposes to detect frame field for constructing
building topology via fully convolutional networks and is able to precisely
segment aerial images. Different from these works, we study the effect of
self-attentions or Transformers in polygonal shape prediction.

Object detection as set prediction. DETR [4] first presents object detection
as a set prediction task, and removes the need for non-maximal suppression on
a large amounts of _anchor boxes_. Similar to DETR, we also consider polygonal
shapes in an image as a set. Different from DETR which only output bounding
boxes, we produce vectorized polygons as a collection of vertices.

Transformers. Transformers were originally introduced by [30] as a novel auto-
regressive, sequence-to-sequence model, and gained popularity thanks to their
ability to dispense entirely with recurrence and support parallel processing
of sequences. Their stunning results on machine translation and other language
tasks [2, 7, 21, 24] have recently shed a light on employing Transformers for
computer vision tasks, such as image recognition [8], object detection [4],
segmentation [33], set prediction [19, 31] and other visual tasks [6, 13, 28,
32]. Inspired by these works, we study both auto-regressive and parallel
Transformers on polygonal shape prediction.

Transformers for set prediction. Deep Sets [34] has proven that transforming
all elements of an input set into some latent representations and then
combining them through a permutation invariant function is a universal
approximator of any set function. The work in [31] shows that the attention
layer of Transformers can also be viewed as a generalization of the sum
operation of Deep Sets and is therefore also a universal approximator of set
functions. Moreover, Lee _et al_. [19] proposes an attention-based
permutation-invariant framework which demonstrates superior results on set-
structured data. Inspired by these works, we also study Transformers for set
prediction task, but on a particular type of set data - polygonal shapes.

Figure 6: The auto-regressive model for predicting polygons. This model
exploits the _sentences of tokens_ idea [30] which generates tokens auto-
regressively. There are only four possible tokens in its vocabulary: _start_ ,
_point_ , _end-of-polygon_ and _end_. The feed-forward network (FFN) at the
end of the pipeline produces a class label and a pair of coordinates (x, y).
Figure 7: Token embeddings for predicting gates and polygons. The first $2n$
elements (in blue) of the vector represent the $(x,\,y)$ coordinates of the
$n$ vertices/points, normalized by the image width and height. The following
elements (in red) represent the class label in one-hot format. For gate
detection, we have three red blocks because we have two special tokens _start_
and _end_ , and an object token _gate_. For polygon detection we have 4 red
blocks because all possible tokens are _start_ , _end_ , _point_ and _end-of-
polygon_ , as explained in 4.2. The vector is padded with zeros to reach the
required dimensionality of 256.

##  3 Datasets

To illustrate our setting, we first show examples of our datasets in Fig. 5.
We use 4 toy datasets and 1 synthetic dataset. The toy images are manually
generated during training and if not specified otherwise, we generate 3
million images for training and 10,000 images for testing.

The point dataset contains images with $n$ white points randomly distributed
over the image space. Each point’s size is uniformly sampled from three
possible values. The task is to predict the $x,\,y$ coordinates of all points
in any order. This dataset is an instance of a pure set prediction problem,
with points representing the set elements.

The line dataset contains images picturing a single white line composed by 7
segments. A green point of fixed size is placed on top of each end of a
segment. The line is generated by first drawing a straight line going from the
bottom left corner of the image to the top right corner, and then randomly
shifting 8 equally distributed points perpendicularly to the line direction by
$r\in[-15\%,15\%]$ with respect to the image size. The task is to predict the
$x,\,y$ coordinates of the 8 points following the line order, starting from
the end on the bottom left of the image. The set elements are represented in
this case by the green points, and this dataset is an example of a set
prediction task where there exists an explicit order in which we need to
predict its elements.

The gate dataset contains images with $n$ convex polygons of 4 corners, called
_gates_. Each gate is generated by defining 4 equally spaced points on a
circumference of random radius $r\in[5\%,40\%]$ with respect to the image
size. Each point is then shifted randomly in the direction of the radius and
the four points are finally connected to define the gate. All four edges of
the gates are of the same thickness, uniformly sampled out of 3 possible
choices.

The synthetic gate dataset [9] contains realistic synthetic images generated
with a graphical engine, which simulate the flight of a drone in different
environments containing empty wireframe objects (EWFOs or _gates_). This
dataset is a simulation of the images that a UAV would face in the IROS 2018
Autonomous Drone Race [17]. The training set contains 26,000 images from two
different scenes, with light coming from outside and inside the rooms. The
test set contains 3,000 images from two additional scenes with light coming
only from artificial sources placed inside the rooms. For all scenes,
different walls and pavement textures are used, as well as different
artificial shapes and light intensities for internal lamps. All images contain
1 to 4 gates. For both synthetic and toy gate datasets, the task is to predict
the position of the four corners in the image for each gate. These two
datasets represent a set prediction scenario closer to real-life problems,
where the complexity of the single set element prediction (the gate) is
greater than a simple point prediction. The synthetic gates dataset increases
the complexity even further by picturing gates with different backgrounds and
different lighting situations.

Finally, the polygon dataset contains images with $n$ polygons of $m\in[3,7]$
corners, generated using the same technique as the gate dataset. As multiple
non-convex polygons can be represented by the same set of points, the task is
to predict the $m$ corners of a polygon in clockwise order. Any starting point
is accepted, and distinct polygons can be predicted in any order. This dataset
represents the hardest set prediction task in which we require our models to
predict a _set of ordered sets_.

For all datasets, $n$ is a parameter varied for different experimental
settings. All samples in the toy datasets are RGB images of size 256x256,
while images from the synthetic gate dataset are of size 400x400. The
coordinates of the labels are represented as the relative height/width to the
image size with values in $[0,1]$.

##  4 Models

All of the models that we implemented and tested are derived from DETR [4], an
end-to-end Transformer which achieves competitive results against Faster R-CNN
[25] on object detection. It takes advantage of a CNN backbone and parallel
encoding-decoding Transformers to solve object detection as a set prediction
task. In short, DETR is composed of four modules: a CNN backbone, a
Transformer Encoder, a Transformer Decoder, and a feed-forward network (FFN).
An example of our models is shown in Fig. 6. It pictures the auto-regressive
variant used for the polygon toy setting dataset.

DETR takes as input an RGB image and extracts a high-level feature map of
shape $C\times H\times W$, where $C$ is the size of number of channels, and
$H$ and $W$ are the spatial dimensions. The feature map is supplemented with
fixed positional embeddings before the Transformer encoder. The Transformer
encoder is a stack of 6 self-attention mechanisms, each of which consists of a
standard self-attention layer followed by a feed forward network, a residual
connection and layer normalization [4]. All of the models we tested are
identical up to this stage of the architecture, but differ in the subsequent
modules.

###  4.1 Parallel models

The design of parallel models is identical to DETR [4]. The $N$ learned
_object queries_ are converted _in parallel_ into $N$ output embeddings of
size 256 by the Transformer decoder, which are subsequently fed into a simple
feed forward network (FFN) for classification and position regression.

Depending on the task, we modify the dimensionality of the FFN for position
regression accordingly. For example, on the point and the line datasets, the
output is a vector of size 2 representing the $(x,\,y)$ coordinates of a point
normalized by the image width and height, while the output on the gate dataset
is an 8-element vector indicating the four vertices of a gate in clock-wise
order. The class labels for all datasets are the same, namely the _object_
class and the _no-object_ class.

On the polygon dataset, the FFN is replaced by a simple multi-layer Elman RNN
[27], since the output dimension is also a variable. The RNN model takes as
input the embeddings from the _object_ class and generates a sequence of
points one by one. The RNN is possibly the minimal modification we could make
to the architecture to work with polygons and have the smallest impact on the
model’s properties and our experiments.

###  4.2 Auto-regressive models

The auto-regressive models diverge from the parallel ones on all set
prediction tasks, because they work with _sentences of tokens_ that are
generated one by one, by conditioning the next prediction on the previous
ones. In particular, each token is a vector of dimension 256 that represents
an element of the set, or acts as a special representation. Special tokens can
be:

  * •

_start_ or S: This token is at the beginning of all sentences and defines the
starts of the computation.

  * •

_end_ or E: This token is at the end of all sentences and terminates the
computation.

  * •

_end-of-polygon_ or EOP: This token separates polygons from polygons inside
the same image. It acts similarly to the _period_ token used in machine
translation to separate words belonging to different sentences.

Depending on the task, object tokens can be:

  * •

_point_ or P: On the point dataset and the line dataset, each point is a
2-element vector representing the position of the $(x,\,y)$ coordinate
normalized by the image width and height.

  * •

_gate_ or G: On both toy and synthetic gate datasets, a gate is represented as
a vector of size 8, which defines the normalized coordinates $(x,\,y)$ of all
4 vertices.

To batch sequences of different lengths together, we pad sentences with the
_end_ token up to the same length. For example, given a batched sequences
where the maximal length is 8, we pad the shorter sequence with 4 visible
points only with two extra E:

$\textbf{S},\;\textbf{P},\;\textbf{P},\;\textbf{P},\;\textbf{P},\;\textbf{E},\;\textbf{E},\;\textbf{E}$

We use the same Transformer decoder as the parallel models, but adopt the
_masking_ technique for parallel training, which prevents each token from
attending to subsequent positions [30]. The token embedding is a fixed length
vector of size 256 as shown in figure 7.

The auto-regressive approach predicts all polygons in a certain order. If not
specified otherwise, we always predict objects going from left to right in the
image, splitting ties with top-to-bottom order. We sort polygons and gates
accordingly by their centers, computed as the average of their vertices.
Particularly, for the polygon dataset, we also impose an order on points such
that the polygon is clock-wisely defined by the points, otherwise the same set
of the points may result in several polygons of different shapes.

Figure 8: Results on the line dataset. The task is to predict a series of
ordered points. The auto-regressive model produces approximately perfect
prediction, while the parallel model fails.

##  5 Experiments

First, we validate that the auto-regressive approach is preferable on the line
dataset where there is an explicit natural order in the predictions, and that
the parallel solution is better on the point dataset for pure set prediction
tasks without orders. We then compare the two strategies on more challenging
gate datasets where the element is no longer a single point and where data is
scarce. Finally, we explore deeper into the auto-regressive solution to study
upon the importance of the prediction order and the order of the conditional
variables.

On toy datasets, we train all models with 3,000,000 images. On the real gate
datasets with 26,000 images, we train all models for 300 epochs. We apply
multiple data augmentation techniques, including horizontal flip, vertical
flip, hue shift, Gaussian noising.

We train all models on a single NVIDIA GeForce RTX 2080 Ti GPU with AdamW
[22], and set the Transformer’s learning rate to $10^{-4}$, the backbone’s
learning rate to $10^{-5}$, and the weight decay to $10^{-4}$. The learning
rate is dropped by a factor of 10 after 200 epochs, or after 2,000,000 images
for the toy settings. Mask R-CNN [15] is also trained for 300 epochs with
learning rate $5\times 10^{-3}$, which is decreased by 10 after 200 epochs.

###  5.1 Evaluation

The evaluation metric on the gate and polygon datasets is mean Average
Precision [4], averaged over different IoU thresholds
($[0.50,0.55,\ldots,0.95]$). On the point and line datasets, we also evaluate
mean Average Precision, but averaged over different point-to-point $L_{1}$
distance thresholds ($[0.10,0.09,\ldots,0.01]$), computed directly on the
relative coordinates.

Figure 9: Results on the point dataset. The auto-regressive model shows
marginally better performance than the parallel one on collections of limited
cardinality, but its performance is lacking when the cardinality grows. The
legends with _$n$ points_ represent results on images with exactly $n$ points
while the others indicate that the number of points in an image varies from 1
to $n$.

###  5.2 Line and point detection

With this experiment we show that the conditional decomposition of collections
by auto-regressive Transformers is beneficial when the elements in a
collection adhere to a natural order. Results on the line dataset are shown in
figure Fig. 8. For this task, a line prediction is considered as a false
positive if the sum of all $L_{1}$ point distances is greater than the given
threshold. The experiment shows that in this setting the auto-regressive
solution is much more precise than the parallel counterpart as it is able to
achieve perfect mAP up to a threshold of 0.02.

On the other hand, the experiments on the point dataset study the behaviour of
parallel and auto-regressive models on a pure set prediction task. The models
are now expected to predict the $n$ points in any order. The parallel
Transformers is order-insensitive because of the Hungarian matching, but the
auto-regressive Transformers are trained by always feeding points in the left-
to-right order. Results on this dataset are shown in Fig. 9. In this
experiment, we train all models on images with 1 to $n$ points. We present
test results on images with 1 to $n$ points, as well as results on images with
exactly $n$ points. Results show that on collection prediction tasks, the
auto-regressive approach is effective when the cardinality is low, but quickly
deteriorates as the cardinality increases.

The two experiments on lines and points prove that the presence of a natural
order in the task is indeed an important discriminative factor towards the
performance of the parallel and auto-regressive models in collection
prediction. Moreover, we show the advantage of the auto-regressive approach in
low-cardinality prediction tasks. The parallel ones show significant advantage
in predicting high-cardinality collections but at the cost of using redundant
object queries (100 object queries in this experiment).

###  5.3 Gate detection

The following experiments verify whether the observations on the line and
point datasets generalize in complicated scenarios where the collection
element is a gate of four vertices. First, we evaluate the performances of
auto-regressive approach and its parallel counterpart on the toy gate dataset,
as shown in Fig. 10. There are two parallel models in comparison: one with
oversampling where we use 30 object queries which is several times more than
the total number of gates, and the other one without oversampling where we use
as many object queries as the maximal number of objects in the images. The
parallel model with oversampling outperforms the one without oversampling
substantially, validating the need for the parallel models to oversample the
cardinality. Moreover, we show once more the auto-regressive approach performs
comparably to the parallel one on low-cardinality collections, but suffers
from the growing cardinality.

Figure 10: Results on the gate dataset. Each point of the plot is an
experiment in which the model is trained and tested on images with 1 to $n$
gates. They show the necessity of oversampling for parallel Transformers. The
performance of auto-regressive models deteriorates when collection cardinality
increases.

In Fig. 11, we provide our findings on the generalization capabilities of
these models, where the number of gates in test images is up to twice more
than the number during training. The auto-regressive model struggles at
detecting more gates, while the parallel one only shows minor performance
decrease and achieves an mAP of 0.8 even on images with twice the amount of
gates. We believe this behavior is a result of the oversampling strategy: each
of the 30 object queries is assigned to at least one gate during training,
which implicitly tells the model that there could be more objects than the
ones it sees in each image.

Figure 11: Generalization capability of the different models. We test both
parallel and auto-regressive on images with twice as many gates as the
training images. The parallel model is able to detect many more gates than the
auto-regressive one. We believe oversampling attributes to better
generalization.

Finally, we numerically compare the general performances of all models on both
toy and synthetic gate datasets with images containing 1 to 6 gates. We choose
Mask R-CNN as the baseline. Tab. 1 shows parallel Transformer outperforms Mask
R-CNN by 5 $\%$ mAP on the toy dataset and by 4 $\%$ mAP on the synthetic gate
dataset. The auto-regressive approach is not able to achieve comparable
results as there is no natural order in this task. However, the auto-
regressive model is approximately two times faster than the parallel model as
it does not require Hungarian algorithm or oversampling.

Models | Toy gates | Training time [min/10k images] | Synthetic gates | Training time [min/10k images]
---|---|---|---|---
_Mask R-CNN_ | 90.67% | 23.6 | 61.30% | 13.85
Parallel | 95.45% | 2.2 | 65.00% | 3.85
Auto-regressive | 87.67% | 1.5 | 59.03% | 1.85
Table 1: Numerical results on gate datasets. We evaluate the overall
performance in mAP averaged over 10 IoU thresholds [0.50, 0.55, …, 0.95]. The
parallel model outperforms Mask R-CNN. The performance of auto-regressive
model is lacking due to the absence of natural order in this task.

###  5.4 Polygon detection

Results on the polygon toy setting dataset are shown in table Tab. 2. This
experiment explores an hybrid scenario in which the collection elements we are
trying to predict are also collections with an imposed order, because a
collection of points can represent multiple polygons if the order of its
points is not given. The auto-regressive approach is the special one described
at the end of section 4.2, which predicts a polygon as a sequence of points
followed by the _end-of-polygon_ token, and it outperforms the parallel model
substantially by over 20 $\%$ in terms of mAP. When using the auto-regressive
solution on polygons, we are predicting each polygon individually by
predicting its vertices and then an end-of-polygon token. This means that we
are splitting a problem of directly predicting all points of all polygons into
multiple sub-problems of predicting each polygon and then deciding when all
points have been predicted. We speculate that the advantage of the auto-
regressive model could be a direct consequence of the conditional
decomposition of the joint probability, as imposing the conditional order on
these models can serve as a strong inductive bias by reducing the search space
of the model. This behaviour might not show up on the previous experiments
because gates, points and lines are simple collection elements which do not
enlarge the search space enough. As polygon detection is representative of
many common computer vision tasks, we leave further exploration of this
approach as future work.

Models | Polygons dataset | Training time [min/10k images]
---|---|---
Parallel | 53.55% | 5.1
Auto-regressive |  76.41% | 2.15
Table 2: Numerical results on the polygon dataset. Scores are represented as
mAP averaged over 10 IoU thresholds [0.50, 0.55, …, 0.95]. The auto-regressive
approach outperforms the parallel one by over 20% absolute mAP. We speculate
that this could be a direct consequence of conditional decomposition of the
collection.

###  5.5 Orders of conditional decomposition

| With positional encodings | W/o positional encodings
---|---|---
Order based on polygon positions | $-1.90\%\pm 1.07\%$ | –
Order based on the size of polygons | $-7.68\%\pm 4.53\%$ | $-2.95\%\pm 1.30\%$
Table 3: Ablation studies on position encodings and condition orders. This
tables shows results of adding positional encodings and imposing orders. The
top performing model is spatially ordered (left-to-right and top-to-bottom)
and has no positional encoding. Our observations are that: (1) changing the
imposed order on auto-regressive Transformers has a great impact on the
performance as shown in the first column; (2) adding position encodings
decreases the performance.

We conclude our experiments by providing insights on the importance of orders
imposed on conditional decomposition of a collection by the auto-regressive
Transformers. Moreover, we also study the influence of positional endcodings.
We run experiments on the toy gate dataset, synthetic gate and the polygon
datasets multiple times, by using two different object orderings and by adding
or removing the positional encodings of the attention layer. Without the
positional encodings, the Transformer decoder is unaware of the index of the
previous predictions in the sequence. When predicting a new point, it only
knows which points were predicted before, but not their orders. The two
orderings are the left-to-right, top-to-bottom order and the small-to-large
order in terms of the size of the objects. Experiment results are shown in
table Tab. 3. Using the left-to-right, top-to-bottom order and removing the
positional encodings lead to the best performance in all experiments. We show
the mean absolute difference of other models compared to best one. The result
shows that the artificial order _matters_ for auto-regressive models.
Moreover, we show that fixed positional encodings are not beneficial in this
setting, in contrast to the original Transformer architectures. This is
expected as different orders of the same words in NLP can have different
meaning, while this does not matter in our setting, as knowing the location of
a point can already prevent our model to predict the same point twice.

##  6 Conclusion

We studied two important variants of the Transformer architecture: the
parallel one and the auto-regressive one on the polygonal shape prediction
task cast as a collection prediction problem. We find that the ordering of
objects is a strong factor towards the performance of these models on point,
line, gate and polygon datasets. The auto-regressive model benefits
collections of small cardinality or on collection prediction problems that can
be easily split into multiple easier tasks.

One limitation of this research is that most experiments are conducted on toy
datasets only, and it is unclear whether the observations and conclusions on
toy datasets generalize on challenging real-world datasets. A task that would
be suitable to expand our research is polygonal building segmentation from
satellite images, as in [11, 23].

As future work, we find it important to further explore on the polygon
detection task as it is a fundamental problem that is representative in
computer vision. Testing the effect of fixed or learned token embeddings would
also be of interest.

## References

  * [1] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  arXiv preprint arXiv:1409.0473, 2014.
  * [2] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  arXiv preprint arXiv:2005.14165, 2020.
  * [3] Zhongzheng Cao, Rui Wang, Xiangyang Wang, Zhi Liu, and Xiaoqiang Zhu.  Improving human pose estimation with self-attention generative adversarial networks.  In 2019 IEEE International Conference on Multimedia & Expo Workshops (ICMEW), pages 567–572. IEEE, 2019.
  * [4] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko.  End-to-end object detection with transformers.  In European Conference on Computer Vision, pages 213–229. Springer, 2020.
  * [5] William Chan, Chitwan Saharia, Geoffrey Hinton, Mohammad Norouzi, and Navdeep Jaitly.  Imputer: Sequence modelling via imputation and dynamic programming.  In International Conference on Machine Learning, pages 1403–1413. PMLR, 2020.
  * [6] Hanting Chen, Yunhe Wang, Tianyu Guo, Chang Xu, Yiping Deng, Zhenhua Liu, Siwei Ma, Chunjing Xu, Chao Xu, and Wen Gao.  Pre-trained image processing transformer.  arXiv preprint arXiv:2012.00364, 2020.
  * [7] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [8] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [9] Philipp Dürnay.  Detecting empty wireframe objects on micro-air vehicles: Applied for gate detection in autonomous drone racing.  2018\.
  * [10] Marjan Ghazvininejad, Omer Levy, Yinhan Liu, and Luke Zettlemoyer.  Mask-predict: Parallel decoding of conditional masked language models.  arXiv preprint arXiv:1904.09324, 2019.
  * [11] Nicolas Girard, Dmitriy Smirnov, Justin Solomon, and Yuliya Tarabalka.  Polygonal building segmentation by frame field learning.  arXiv preprint arXiv:2004.14875, 2020.
  * [12] Nicolas Girard and Yuliya Tarabalka.  End-to-end learning of polygons for remote sensing image classification.  In IGARSS 2018-2018 IEEE International Geoscience and Remote Sensing Symposium, pages 2083–2086. IEEE, 2018.
  * [13] Rohit Girdhar, Joao Carreira, Carl Doersch, and Andrew Zisserman.  Video action transformer network.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 244–253, 2019.
  * [14] Jiatao Gu, James Bradbury, Caiming Xiong, Victor OK Li, and Richard Socher.  Non-autoregressive neural machine translation.  arXiv preprint arXiv:1711.02281, 2017.
  * [15] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask r-cnn.  In Proceedings of the IEEE international conference on computer vision, pages 2961–2969, 2017.
  * [16] Vladimir Iglovikov, Selim Seferbekov, Alexander Buslaev, and Alexey Shvets.  Ternausnetv2: Fully convolutional network for instance segmentation.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 233–237, 2018.
  * [17] Sunggoo Jung, Sungwook Cho, Dasol Lee, Hanseob Lee, and David Hyunchul Shim.  A direct visual servoing-based framework for the 2016 iros autonomous drone racing challenge.  Journal of Field Robotics, 35(1):146–166, 2018.
  * [18] Harold W Kuhn.  The hungarian method for the assignment problem.  Naval Research Logistics (NRL), 52(1):7–21, 2005.
  * [19] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh.  Set transformer: A framework for attention-based permutation-invariant neural networks.  In International Conference on Machine Learning, pages 3744–3753. PMLR, 2019.
  * [20] Zuoyue Li, Jan Dirk Wegner, and Aurélien Lucchi.  Topological map extraction from overhead images.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1715–1724, 2019.
  * [21] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.  Roberta: A robustly optimized bert pretraining approach.  arXiv preprint arXiv:1907.11692, 2019.
  * [22] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  arXiv preprint arXiv:1711.05101, 2017.
  * [23] Sharada Prasanna Mohanty, Jakub Czakon, Kamil A Kaczmarek, Andrzej Pyskir, Piotr Tarasiewicz, Saket Kunwar, Janick Rohrbach, Dave Luo, Manjunath Prasad, Sascha Fleer, et al.  Deep learning for understanding satellite imagery: An experimental survey.  Frontiers in Artificial Intelligence, 3, 2020.
  * [24] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever.  Improving language understanding by generative pre-training.  2018\.
  * [25] Shaoqing Ren, Kaiming He, Ross Girshick, and Jian Sun.  Faster r-cnn: Towards real-time object detection with region proposal networks.  arXiv preprint arXiv:1506.01497, 2015.
  * [26] S Hamid Rezatofighi, Vijay Kumar BG, Anton Milan, Ehsan Abbasnejad, Anthony Dick, and Ian Reid.  Deepsetnet: Predicting sets with deep neural networks.  In 2017 IEEE International Conference on Computer Vision (ICCV), pages 5257–5266. IEEE, 2017.
  * [27] Alex Sherstinsky.  Fundamentals of recurrent neural network (rnn) and long short-term memory (lstm) network.  Physica D: Nonlinear Phenomena, 404:132306, 2020.
  * [28] Chen Sun, Austin Myers, Carl Vondrick, Kevin Murphy, and Cordelia Schmid.  Videobert: A joint model for video and language representation learning.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 7464–7473, 2019.
  * [29] Wei Tang and Ying Wu.  Does learning specific features for related parts help human pose estimation?  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1107–1116, 2019.
  * [30] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  arXiv preprint arXiv:1706.03762, 2017.
  * [31] Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A Osborne.  On the limitations of representing functions on sets.  In International Conference on Machine Learning, pages 6487–6494. PMLR, 2019.
  * [32] Fuzhi Yang, Huan Yang, Jianlong Fu, Hongtao Lu, and Baining Guo.  Learning texture transformer network for image super-resolution.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5791–5800, 2020.
  * [33] Linwei Ye, Mrigank Rochan, Zhi Liu, and Yang Wang.  Cross-modal self-attention network for referring image segmentation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10502–10511, 2019.
  * [34] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola.  Deep sets.  arXiv preprint arXiv:1703.06114, 2017.
  * [35] Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett.  Deep set prediction networks.  arXiv preprint arXiv:1906.06565, 2019.
  * [36] Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett.  Fspool: Learning set representations with featurewise sort pooling.  arXiv preprint arXiv:1906.02795, 2019.
  * [37] Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai.  Deformable detr: Deformable transformers for end-to-end object detection.  arXiv preprint arXiv:2010.04159, 2020.


# Fairness via In-Processing in the Over-parameterized Regime:
A Cautionary Tale

Akshaj Kumar Veldanda  Ivan Brugere  Jiahao Chen  Sanghamitra Dutta  Alan
Mishler  Siddharth Garg

###### Abstract

11footnotetext: Electrical and Computer Engineering Department, New York
University, New York, USA 2JP Morgan Chase AI Research, New York, USA 3Parity,
New York, USA. Correspondence to: Akshaj Kumar Veldanda<EMAIL_ADDRESS>∗Equal Contribution.

The success of deep learning is driven by the counter-intuitive ability of
over-parameterized deep neural networks (DNNs) to generalize, even when they
have sufficiently many parameters to perfectly fit the training data. In
practice, test error often continues to decrease with increasing over-
parameterization, a phenomenon referred to as double descent. This allows deep
learning engineers to instantiate large models without having to worry about
over-fitting. Despite its benefits, however, prior work has shown that over-
parameterization can exacerbate bias against minority subgroups. Several
fairness-constrained DNN training methods have been proposed to address this
concern. Here, we critically examine MinDiff, a fairness-constrained training
procedure implemented within TensorFlow’s Responsible AI Toolkit, that aims to
achieve Equality of Opportunity. We show that although MinDiff improves
fairness for under-parameterized models, it is likely to be ineffective in the
over-parameterized regime. This is because an overfit model with zero training
loss is trivially group-wise fair on training data, creating an “illusion of
fairness,” thus turning off the MinDiff optimization (this will apply to any
disparity-based measures which care about errors or accuracy. It won’t apply
to demographic parity). We find that within specified fairness constraints,
under-parameterized MinDiff models can even have lower error compared to their
over-parameterized counterparts (despite baseline over-parameterized models
having lower error compared to their under-parameterized counterparts). We
further show that MinDiff optimization is very sensitive to choice of batch
size in the under-parameterized regime. Thus, fair model training using
MinDiff requires time-consuming hyper-parameter searches. Finally, we suggest
using previously proposed regularization techniques, viz. L2, early stopping
and flooding in conjunction with MinDiff to train fair over-parameterized
models. In our results, over-parameterized models trained using
MinDiff+regularization with standard batch sizes are fairer than their under-
parameterized counterparts, suggesting that at the very least, regularizers
should be integrated into fair deep learning flows.

Fairness & Diversity, Trustworthy Machine Learning

##  1 Introduction

Over the past few years, machine learning (ML) solutions have found wide
applicability in wide range of domains. However, recent work has shown that ML
methods can exhibit unintended biases towards specific population groups, for
instance in applications like hiring (Schumann et al., 2020), credit
verification (Khandani et al., 2010), facial recognition (Buolamwini & Gebru,
2018; Grother et al., 2010; Ngan & Grother, 2015), recidivism prediction
(Chouldechova, 2017) and recommendation systems (Biega et al., 2018; Singh &
Joachims, 2018), resulting in negative societal consequences. To address this
concern, there is an growing and influential body of work on mitigating
algorithmic unfairness of ML models. These solutions are being integrated
within widely used ML frameworks and are beginning to find practical
deployment (AI, ; Akihiko Fukuchi, 2020). As ML fairness methods make the
transition from theory to practice, their ability to achieve stated goals in
real-world deployments merits closer examination.

Methods to train fair models can be broadly categorized based on the stage at
which they are deployed: pre-training, in-training, or post-training. Of
these, only in-training methods substantively modify the model training
process. This paper examines the performance of MinDiff (Prost et al., 2019),
the principal in-training method integrated within TensorFlow’s Responsible AI
Framework (AI, ). We are particularly interested in MinDiff for training fair
deep learning models because, given TensorFlow’s widespread adoption, there is
good reason to believe that it will be picked as the default choice by
practitioners working within this framework.

We evaluate MinDiff on two datasets, Waterbirds and CelebA that are commonly
used in fairness literature, and observe several notes of caution. Because the
success of deep learning can be attributed at least in part to the surprising
ability of over-parameterized deep networks (networks with sufficiently many
parameters to _memorize_ the training dataset) to generalize (Nakkiran et al.,
2020), we begin by evaluating the relationship between model capacity and
fairness with MinDiff. We observe that MinDiff does increase fairness for
small, under-parameterized models, but is almost entirely ineffective on
larger over-parameterized networks. Thus, in some cases, under-parameterized
MinDiff models can have lower fairness-constrained error compared to their
over-parameterized counterparts even though over-parameterized models are
always better on baseline error (i.e., error on models trained without MinDiff
optimization). We caution that when using MinDiff for fairness, ML
practitioners must carefully choose model capacity, something which is
generally unnecessary when fairness is not a concern and the goal is simply to
minimize error.

We find the reason MinDiff is ineffective in the over-parameterized regime is
because an overfit model with zero training loss means any disparity-based
unfairness necessarily goes to zero on the training dataset, creating an
“illusion of fairness” during training, thus turning off the MinDiff
optimization (this will apply to any disparity-based measures which care about
errors or accuracy. It won’t apply to demographic parity). Thus, we explore
whether strong regularization used along with MinDiff can alleviate its
ineffectiveness. Specifically, we consider two classes of regularization
techniques: implicit (batch sizing (Smith et al., 2021; Barrett & Dherin,
2021) and early stopping (Morgan & Bourlard, 1990)) and explicit (weight decay
(Krogh & Hertz, 1992) and a recently proposed “loss flooding” method (Ishida
et al., 2020)) regularizers. We find that: (1) batch sizing only helps for
medium sized models around the interpolation threshold; (2) the remaining
three methods all improve fairness in the over-parameterized regime; (3)
early-stopping and flooding result in the fairest models for the Waterbirds
and CelebA datasets, respectively; and (4) with effective regularization,
over-parameterized models are fairer than their under-parameterized
counterparts.

##  2 Related Work

There are several techniques in literature to mitigate algorithmic bias. These
techniques can be broadly categorized as: pre-processing, in-processing and
post-processing. Pre-processing techniques aim to de-identify sensitive
information and create more balanced training datasets (Quadrianto et al.,
2019; Ryu et al., 2018; Feldman et al., 2015; Wang & Deng, 2019; Karkkainen &
Joo, 2021; Dixon et al., 2018). In-processing (Prost et al., 2019; Cherepanova
et al., 2021; Sagawa et al., 2020a, b; Padala & Gujar, 2021; Agarwal et al.,
2018; Zafar et al., 2019; Donini et al., 2018; Lahoti et al., 2020; Beutel et
al., 2019; Martinez et al., 2020; Wadsworth et al., 2018; Goel et al., 2018;
Wang & Deng, 2019; Hashimoto et al., 2018) techniques alter the training
mechanism by imposing fairness constraints to the training objective, or
utilize adversarial training (Beutel et al., 2017; Zhang et al., 2018; Madras
et al., 2018) to make predictions independent of sensitive attributes. Post-
processing techniques (Hardt et al., 2016b; Wang et al., 2020; Savani et al.,
2020; Chzhen et al., 2019; Jiang et al., 2020; Wei et al., 2020) alter the
outputs of an existing model, for instance, using threshold correction (Zhou &
Liu, 2006; Collell et al., 2016; Menon et al., 2021a) that applies different
classification thresholds to each sensitive group (Hardt et al., 2016b). In
this paper, we focus on MinDiff (Prost et al., 2019), the primary in-
processing procedure implemented within TensorFlow’s Responsible AI toolkit.
While our quantitative conclusions might differ, we believe that similar
qualitative conclusions will hold for other in-processing methods because
overfit models are trivially fair.

With the growing adoption of large over-parameterized deep networks, recent
efforts have sought to investigate their fairness properties (Menon et al.,
2021b; Sagawa et al., 2020a; Cherepanova et al., 2021; Sagawa et al., 2020b).
Sagawa et al. (2020b) proposed a pre-processing technique by investigating the
role of training data characteristics (such as ratio of majority to minority
groups and relative informativeness of spurious versus core features) on
fairness and observed that sub-sampling improves fairness in the over-
parameterized regime. Menon et al. (2021b) found that post-processing
techniques including retraining with sub-sampled majority groups and threshold
correction also enhance fairness in over-parameterized models. Cherepanova et
al. (2021) report that in-processing convex surrogates of fairness constraints
like equal loss, equalized odds penalty, disparate impact penalty, etc.,
(Padala & Gujar, 2021) are ineffective on over-parameterized models, but do
not propose any techniques to increase the effectiveness of in-processing
methods. Our work is the first to systematically compare under- vs. over-
parameterized deep models trained using in-processing fairness methods using
MinDiff as a representative method.

Regularization techniques (Morgan & Bourlard, 1990; Srivastava et al., 2014;
Krogh & Hertz, 1992; Ishida et al., 2020) are popularly used in deep learning
frameworks to avoid over-fitting. Lately, researchers have also exploited the
benefits of regularizers to train fair models. For example, Sagawa et al.
(2020a) proposed distributionally robust optimization (DRO) to improve worst-
group generalization, but they observed that their approach fails if training
loss converges to zero. Hence, they use L2 weight regularization and early
stopping to improve fairness in the over-parameterized regime. Our paper
systematically evaluates different regularizers, including batch sizing, early
stopping, weight decay and the recently proposed flooding loss (Ishida et al.,
2020) for MinDiff training across different model sizes, and makes several new
observations about the role of regularization in enhancing fairness.

##  3 Methodology

We now describe our evaluation methodology.

###  3.1 Setup

In this paper, we consider binary classification problem on a training dataset
$\mathcal{D}=\\{x_{i},a_{i},y_{i}\\}_{i=1}^{N}$, where $x_{i}$ is an input (an
image for instance) $a_{i}\in\\{0,1\\}$ is a sensitive attribute of the input,
and $y_{i}\in\\{0,1\\}$ is the corresponding ground-truth label. The training
data is sampled from a joint distribution $P_{X,A,Y}$, over random variables
$X$, $A$, and $Y$. Deep neural network (DNN) classifiers are represented as a
parameterized function $f_{\theta}:\mathcal{X}\rightarrow[0,1]$, where
$\theta$ are trainable parameters, obtained in practice by minimizing the
binary cross-entropy loss function $\mathcal{L}_{P}$:

$\mathcal{L}_{P}=-\frac{1}{N}\sum_{i=1}^{N}[y_{i}\cdot
log(f_{\theta}(x_{i}))+(1-y_{i})\cdot log(1-f_{\theta}(x_{i}))]$ (1)

via stochastic gradient descent.

We denote the classification threshold as $\tau$ which can be used to make
predictions $\hat{f}_{\theta}(x;\tau)$ as shown below

$\hat{f}_{\theta}(x;\tau)=\begin{cases}1,\hskip
10.00002ptf_{\theta}(x)\geq\tau\\\ 0,\hskip
10.00002pt\textrm{otherwise}.\end{cases}$ (2)

Standard DNN training methods seek to achieve low test error
$\mathbb{P}[\hat{f}_{\theta}(X;\tau)\neq Y]$ (typically, $\tau=0.5$) but
performance conditioned on sensitive attributes can vary, leading to outcomes
that are biased in favor of or against specific sub-groups. Several fairness
metrics have been defined in prior work to account for this bias; in this
paper, we will use the widely adopted equality of opportunity metric (Hardt et
al., 2016a).

##### Equality of Opportunity

(Hardt et al., 2016a) is a widely adopted fairness notion that seeks to
equalize false negative rates (FNR) across sensitive groups. For binary
sensitive attributes the $\operatorname{FNR_{gap}}$ is defined as:

$\begin{multlined}\operatorname{FNR_{gap}}=\big{|}\mathbb{P}[\hat{f}_{\theta}(X;\tau)=0|Y=1,A=0]-\\\
\mathbb{P}[\hat{f}_{\theta}(X;\tau)=0|Y=1,A=1]\big{|}.\end{multlined}\operatorname{FNR_{gap}}=\big{|}\mathbb{P}[\hat{f}_{\theta}(X;\tau)=0|Y=1,A=0]-\\\
\mathbb{P}[\hat{f}_{\theta}(X;\tau)=0|Y=1,A=1]\big{|}.$ (3)

As we describe next, MinDiff (and several other methods) seek to minimize the
$\operatorname{FNR_{gap}}$ during training.

###  3.2 MinDiff Training

MinDiff (Prost et al., 2019) is an in-processing optimization framework that
seeks to achieve a balance between two objectives: low test error and low
$\operatorname{FNR_{gap}}$. For this, MinDiff proposes a modified loss
function $\mathcal{L}_{T}=\mathcal{L}_{P}+\lambda\mathcal{L}_{M}$, where
$\mathcal{L}_{T}$ is the total loss, that is a weighted sum of the cross-
entropy loss, defined in Equation 1, and $\mathcal{L}_{M}$, a differentiable
proxy for the $\operatorname{FNR_{gap}}$. In the modified loss function,
$\lambda\in\mathbb{R}_{+}$ is a user-defined parameter that controls the
relative importance of the fairness versus test error. The fairness term in
the modified loss function, $\mathcal{L}_{M}$, uses the maximum mean
discrepancy ($\operatorname{MMD}$) distance between the neural network’s
outputs for the two sensitive groups when $Y=1$, i.e.,

$\mathcal{L}_{M}=\operatorname{MMD}(f_{\theta}(X)|A=0,Y=1,f_{\theta}(X)|A=1,Y=1).$
(4)

We refer the reader to the original MinDiff paper for a formal definition of
the $\operatorname{MMD}$ distance (Prost et al., 2019).

###  3.3 Post-hoc Threshold Correction

Due to fairness requirements of the application, ML practitioners might seek
to train models with an $\operatorname{FNR_{gap}}$ lower than a specified
threshold $\operatorname{\Delta_{FNR}}$. However, MinDiff does not explicitly
constrain the $\operatorname{FNR_{gap}}$; this can be addressed using an
additional post-processing threshold correction step, as proposed by (Hardt et
al., 2016b). The idea is to use different classification thresholds for each
sub-group, $\tau_{A=0}$ and $\tau_{A=1}$, that are selected such that the
$\operatorname{FNR_{gap}}$ constraint is met _and_ test error is minimized.:

$\begin{multlined}\big{|}\mathbb{P}[\hat{f}_{\theta}(X;\tau_{A=0})=0|Y=1,A=0]-\\\
\mathbb{P}[\hat{f}_{\theta}(X;\tau_{A=1})=0|Y=1,A=1]\big{|}\leq\operatorname{\Delta_{FNR}},\end{multlined}\big{|}\mathbb{P}[\hat{f}_{\theta}(X;\tau_{A=0})=0|Y=1,A=0]-\\\
\mathbb{P}[\hat{f}_{\theta}(X;\tau_{A=1})=0|Y=1,A=1]\big{|}\leq\operatorname{\Delta_{FNR}},$
(5)

The two thresholds can be picked using grid search on a validation dataset; we
refer to the resulting test error as the fairness-constrained test error.
Pareto front of fairness-constrained test error and
$\operatorname{\Delta_{FNR}}$ is used to compare different model sizes and
fairness methods. In particular, a model or method is fairer if it has lower
fairness-constrained test error compared to the alternative for a fixed
$\operatorname{\Delta_{FNR}}$.

###  3.4 Regularization Techniques

We evaluate four regularization techniques to improve performance of MinDiff
on over-parameterized networks.

##### Reduced Batch Sizes:

Due to the stochastic nature of SGD, smaller batch sizes can act as implicit
regularizers during training (Smith et al., 2021; Barrett & Dherin, 2021).
This is because smaller batch sizes provide a noisy estimate of the total loss
$\mathcal{L}_{T}$.

##### Weight Decay:

Weight decay (Krogh & Hertz, 1992) explicitly penalizes the parameters
$\theta$ of the DNN from growing too large. Weight decay adds a penalty,
usually the L2 norm of the weights, to the loss function.

##### Early Stopping:

Early stopping (Morgan & Bourlard, 1990) terminates DNN training earlier than
the point at which training loss converges to a local minima, and has been
shown to be particularly effective for over-parameterized deep networks (Li et
al., 2019). A common implementation of early stopping is to terminate training
once the validation loss has increased for a certain number of gradient steps
or epochs (Morgan & Bourlard, 1990). For models trained with MinDiff, we
explore two versions of early stopping in which we use either the primary
loss, $\mathcal{L}_{P}$, or total loss, $\mathcal{L}_{T}$, as a stopping
criterion.

##### Flooding Regularizer:

Finally, motivated by our goal to prevent the primary training loss from going
to zero (which then turns off MinDiff as well), we apply the flooding
regularizer (Ishida et al., 2020) that encodes this goal _explicitly_.
Flooding operates by performing gradient descent only if $\mathcal{L}_{P}>b$,
where $b$ is the flood level. Otherwise, if $\mathcal{L}_{P}\leq b$, then
gradient ascent takes place as shown in Equation 6. This phenomenon ensures
that $\mathcal{L}_{P}$ floats around the flood level $b$ and never approaches
zero. We implement flooding by replacing the primary loss term in
$\mathcal{L}_{T}$ with a new loss term:

$\mathcal{L}^{\prime}_{P}=\big{|}\mathcal{L}_{P}-b\big{|}+b,$ (6)

which, in turn, enables continued minimization of the MinDiff loss term,
$\mathcal{L}_{M}$, over the training process.

(a) Waterbirds

(b) CelebA

Figure 1: We show the model-wise double descent behaviour on baseline models
trained using (a) Waterbirds and (b) CelebA datasets respectively.
Interpolation threshold (shown in green dotted line) is the point where the
model is large enough to fit the training data. The region beyond the
interpolation threshold is called the over-parameterized regime.

Figure 2: We show the (a) average test error, and (b)
$\operatorname{FNR_{gap}}$ versus model width for MinDiff optimization with
$\lambda=\\{0.0,0.5,1.0,1.5\\}$’s on Waterbirds dataset. MinDiff optimization
has negligible to no impact on fairness in the over-parameterized models.
However, for under-parameterized models, we find that increasing $\lambda$
substantially reduces the $\operatorname{FNR_{gap}}$.

##  4 Experimental Setup

We perform our experiments on the Waterbirds (Sagawa et al., 2020a) and CelebA
(Liu et al., 2015) datasets which have previously been used in fairness
evaluations of deep learning models. Here, we describe network architectures,
training and evaluations for the two datasets.

###  4.1 Waterbirds Dataset

Waterbirds is synthetically created dataset (Sagawa et al., 2020a) which
contains water- and land-bird images overlaid on water and land backgrounds. A
majority of waterbirds (landbirds) appear in water (land) backgrounds, but in
a minority of cases waterbirds (landbirds) also appear on land (water)
backgrounds. As in past work, we use the background as the sensitive feature.
Further, we use waterbirds as the positive class and landbirds as the negative
class. The dataset is split into training, validation and test sets with 4795,
1199 and 5794 images in each dataset respectively.

We follow the training methodology described in (Sagawa et al., 2020b) to
train a deep network for this dataset. First, a fixed pre-trained ResNet-18
model is used to extract a $d$-dimensional feature vector $\mu$. This feature
vector is then converted into an $m$-dimensional feature
$\mu^{\prime}=ReLU(U\mu)$, where $U\in\mathbb{R}^{m\times d}$ is a random
matrix with Gaussian entries. A logistic regression classifier is trained on
$\mu^{\prime}$. Model width is controlled by varying $m$, the dimensionality
of $\mu^{\prime}$, from $10$ to $10,000$.

Figure 3: We show the progress of primary loss and $\operatorname{FNR_{gap}}$,
evaluated on training dataset, versus SGD steps during MinDiff optimization
($\lambda=1.5$) for under-parameterized and over-parameterized models on
CelebA dataset. We find that over-parameterized models over-fits to the
training data and achieve zero $\operatorname{FNR_{gap}}$, thus turning off
MinDiff optimization. Whereas, $\operatorname{FNR_{gap}}$ is positive in the
under-parameterized models, allowing for MinDiff optimization to be effective.

(a) Under-parameterized (b) Over-parameterized

###  4.2 CelebA Dataset

The CelebA dataset consists of 202,599 celebrity face images annotated with 40
binary attributes including gender, hair colour, hair style, eyeglasses, etc.
In our experiments, we set the target label $\mathcal{Y}$ to be hair color,
which is either blond ($Y=1$) or non-blond ($Y=0$), and the sensitive
attribute to be gender. Blond individuals constitute only $15\%$ of this
dataset, and only $6\%$ of blond individuals are men. Consequently baseline
models make disproportionately large errors on blond men versus blond women.
The objective of MinDiff training is to minimize the
$\operatorname{FNR_{gap}}$ between blond men and blond women 111Note that the
MinDiff paper uses False Positive Rate, but this is totally arbitrary here
since the class labels are arbitrary.. The dataset is split into training,
validation and test sets with 162770, 19867 and 19962 images, respectively.

We used the ResNet-preact-18 model for this dataset, and vary model capacity
by uniformly scaling the number of channels in all layers.

###  4.3 Hyper-parameters and Training Details

##### Waterbirds

We train for a total of $30,000$ gradient steps using the Adam optimizer. For
our baseline experiments, we set batch size to $128$ and use a learning rate
schedule with initial learning rate $=0.01$ and decay factor of 10 for every
$10,000$ gradient steps. We ran every experiment 10 times with random
initializations and report the average of all the runs. We trained and
evaluated all the models using the Waterbirds dataset on an Intel Xeon
Platinum 8268 CPU (24 cores, 2.9 GHz).

##### CelebA

We train for a total of $48,000$ gradient steps using the Adam optimizer. We
set the baseline batch size to $128$ and adopt a learning rate scheduler with
initial learning rate of $0.0001$ and decay factor of 10 for every $16,000$
gradient steps. In our experiments, we varied the number of channels in the
first ResNet-preact-18 block from $1$ to $64$ (the number of channels is then
scaled up by two in each block). We trained all the models using the CelebA
dataset on NVIDIA 4 x V100 (32 GB) GPU cards.

For both datasets, we performed MinDiff training with values of
$\lambda=\\{0.0,0.5,1.0,1.5\\}$, where recall that $\lambda$ controls the
importance of the fairness objective. $\lambda=0.0$ corresponds to training
with the primary loss only, and we refer to the resulting model as the
baseline model. To study the effect of batch sizing, we trained additional
models with batch sizes $\\{8,32\\}$. We explored with three different weight
decay strengths $=\\{0.001,0.1,10.0\\}$ and two different flood levels,
$b\in\\{0.05,0.1\\}$. We report the average $\pm$ $95\%$ confidence interval
in all figures and tables.

##  5 Experimental Results

###  5.1 Identifying the Interpolation Threshold

To distinguish between under- and over-parameterized models, we begin by
identifying the interpolation threshold; the point where the model is
sufficiently large to interpolate the training data (achieve zero error).
Figure 1(a) and Figure 1(b) show the training and test error curves for
baseline training versus model width for the Waterbirds and CelebA datasets,
respectively, showing interpolation thresholds at model widths of 400 for
Waterbirds and 11 for CelebA. On both the datasets, we also observe the double
descent phenomenon (Nakkiran et al., 2020), where the test error _decreases_
with increasing model capacity beyond the interpolation threshold. That is,
for the original model (training without MinDiff), the largest models provide
high accuracy.

(a) Waterbirds

(b) CelebA

Figure 4: We plot the fairness constrained test error with a
$\operatorname{\Delta_{FNR}}\leq 10\%$ constraint on the MinDiff trained
models with $\lambda=\\{0.0,0.5,1.0,1.5\\}$ on (a) Waterbirds and (b) CelebA
datasets respectively. On both these datasets, we find that MinDiff is only
effective for under-parameterized models.

(a) Waterbirds

(b) CelebA

Figure 5: We plot the fairness constrained test error with a
$\operatorname{\Delta_{FNR}}\leq 10\%$ constraint on the MinDiff trained model
with $\lambda=1.5$ on (a) Waterbirds and (b) CelebA datasets respectively. We
find that smaller batch sizes are only effective around the interpolation
threshold.

###  5.2 MinDiff Evaluation

We now re-train our models with MinDiff optimization with
$\lambda=\\{0.0,0.5,1.0,1.5\\}$. Figure 2 shows the test error and
$\operatorname{FNR_{gap}}$ versus model width for the Waterbirds dataset. In
the under-parameterized regime, we observe that, increasing the MinDiff
weights significantly reduces the $\operatorname{FNR_{gap}}$ with only a small
drop in test accuracy. However, in the over-parameterized regime, we find that
MinDiff training has no impact on either test error or the
$\operatorname{FNR_{gap}}$.

Table 1 shows the test error and $\operatorname{FNR_{gap}}$ for selected
under- and over-parameterized models on the CelebA dataset trained with
MinDiff. Our conclusions are qualitatively the same as for Waterbirds. We find
that, MinDiff training significantly reduces the $\operatorname{FNR_{gap}}$
compared to the baseline model in the under-parameterized regime, for example,
from a $48\%$ FNR gap without MinDiff to a $37\%$ FNR gap with $\lambda=1.5$
for a model width of 5. On the other hand, MinDiff training compared with the
baseline model has a negligible effect on both test error and
$\operatorname{FNR_{gap}}$ in the over-parameterized regime, sometimes even
resulting in a (small) increase in both.

Table 1: We pick three under-parameterized and four over-parameterized model
widths and report the average test error and $\operatorname{FNR_{gap}}$ for
baseline training and several values of $\lambda$ on CelebA dataset. We find
that, in the under-parameterized models, the drop in
$\operatorname{FNR_{gap}}$ for MinDiff training vs baseline training is more
compared to that in the over-parameterized models. We report each data point
by averaging over 10 runs.

Width | $\lambda=0$ | $\lambda=0.5$ | $\lambda=1.0$ | $\lambda=1.5$
---|---|---|---|---
| Error | FNR Gap | Error | FNR Gap | Error | FNR Gap | Error | FNR Gap
5 (Under-) | $4.74\pm 0.07$ | $48.77\pm 1.44$ | $5.55\pm 0.39$ | $39.85\pm 3.82$ | $5.46\pm 0.36$ | $40.45\pm 5.58$ | $5.47\pm 0.34$ | $37.06\pm 5.88$
7 (Under-) | $5.07\pm 0.07$ | $47.35\pm 1.53$ | $5.76\pm 0.5$ | $40.27\pm 2.45$ | $5.64\pm 0.52$ | $42.7\pm 3.12$ | $5.48\pm 0.4$ | $43.05\pm 4.2$
9 (Under-) | $5.31\pm 0.07$ | $44.78\pm 1.72$ | $5.72\pm 0.4$ | $42.37\pm 1.75$ | $5.77\pm 0.53$ | $40.91\pm 3.28$ | $5.52\pm 0.42$ | $42.43\pm 3.74$
13 (Over-) | $5.52\pm 0.07$ | $42.79\pm 2.03$ | $5.57\pm 0.1$ | $42.16\pm 2.33$ | $5.66\pm 0.17$ | $42.53\pm 0.98$ | $5.67\pm 0.32$ | $43.07\pm 2.12$
19 (Over-) | $5.36\pm 0.09$ | $43.98\pm 1.81$ | $5.33\pm 0.05$ | $42.52\pm 1.25$ | $5.42\pm 0.07$ | $42.63\pm 1.01$ | $5.45\pm 0.11$ | $41.34\pm 1.41$
55 (Over-) | $4.98\pm 0.07$ | $44.14\pm 1.55$ | $5.05\pm 0.07$ | $42.46\pm 1.28$ | $5.24\pm 0.06$ | $42.65\pm 1.85$ | $5.47\pm 0.15$ | $41.93\pm 1.88$
64 (Over-) | $4.99\pm 0.06$ | $42.54\pm 2.01$ | $5.11\pm 0.06$ | $43.12\pm 2.04$ | $5.28\pm 0.12$ | $41.8\pm 2.32$ | $5.40\pm 0.15$ | $41.56\pm 2.7$

Table 2: We tabulate the fairness constrained test error (with a
$\operatorname{\Delta_{FNR}}\leq 10\%$ constraint) of early stopped MinDiff
models (trained with $\lambda=\\{0.5,1.0,1.5\\}$) for different widths. We
compare two methods for early stopping (es) based on the stopping criterion:
primary validation loss (es($\mathcal{L}_{P}$)) and total validation loss
(es($\mathcal{L}_{T}$)). We find that, for CelebA dataset, MinDiff $+$
es($\mathcal{L}_{P}$) is better than MinDiff $+$ es($\mathcal{L}_{T}$).

| $\lambda=0.5$ | $\lambda=1.0$ | $\lambda=1.5$
---|---|---|---
|  Width = $5$ |  Width = $19$ |  Width = $64$ |  Width = $5$ |  Width = $19$ |  Width = $64$ |  Width = $5$ |  Width = $19$ |  Width = $64$
No es | $6.36\pm 0.51$ | $6.54\pm 0.12$ | $5.88\pm 0.13$ | $6.25\pm 0.43$ | $6.43\pm 0.12$ | $6.06\pm 0.06$ | $6.36\pm 0.35$ | $6.54\pm 0.18$ | $6.07\pm 0.2$
es($\mathcal{L}_{P}$) | $6.17\pm 0.34$ | $5.91\pm 0.26$ | $5.45\pm 0.22$ | $6.32\pm 0.28$ | $5.82\pm 0.32$ | $4.79\pm 0.17$ | $6.37\pm 0.25$ | $5.63\pm 0.3$ | $4.70\pm 0.07$
es($\mathcal{L}_{T}$) | $7.76\pm 0.56$ | $6.47\pm 0.31$ | $5.76\pm 0.61$ | $7.79\pm 0.47$ | $7.18\pm 0.58$ | $6.05\pm 0.53$ | $8.65\pm 0.65$ | $7.38\pm 0.77$ | $6.80\pm 0.64$

We observe that MinDiff performs poorly for over-parameterized models: Figure
3 shows how the primary loss and $\operatorname{FNR_{gap}}$’s change during
SGD steps for under-parameterized and over-parameterized models on the CelebA
dataset. We note that at the beginning of training, the
$\operatorname{FNR_{gap}}$ is small because randomly initialized models make
random predictions. These random predictions are fair w.r.t the error rates
but not necessarily fair according to other criteria like Demographic Parity.
As training progresses, the over-parameterized model eventually over-fits the
training data at around 20,000 steps, achieving zero primary loss. This model
also appears to be trivially fair from the standpoint of the training
data—observe that at the same point, the $\operatorname{FNR_{gap}}$ also goes
to zero, and no further optimization takes place. On the other hand, the
$\operatorname{FNR_{gap}}$ during training remains positive for the under-
parameterized model.

Figure 4 plots the fairness constrained test error with a
$\operatorname{\Delta_{FNR}}\leq 10\%$ constraint using post-training
threshold correction on the MinDiff trained models. We can again observe that
MinDiff is only effective for under-parameterized models. For CelebA, the
lowest fairness constrained test error is actually achieved by an under-
parameterized model. In other words, _achieving fairness via MinDiff
optimization requires careful selection of model width, including exploring
the under-parameterized regime_.

Table 3: We tabulate the fairness constrained test error (with a
$\operatorname{\Delta_{FNR}}\leq 10\%$ constraint) for different
regularization schemes used in conjunction with MinDiff optimization
($\lambda=1.5$) on CelebA dataset. The performance of best regularizer is
highlighted in bold for each model width. Notation: wd is weight decay,
es($\mathcal{L}_{P}$) is early stopping w.r.t primary loss and fl is flooding

Method | Width = 5 | Width = 19 | Width = 64
---|---|---|---
| Under- | Over- | Over-
$\lambda=0$ | $5.92\pm 0.19$ | $6.51\pm 0.11$ | $5.76\pm 0.1$
$\lambda=1.5$ | $6.36\pm 0.35$ | $6.54\pm 0.18$ | $6.07\pm 0.2$
$\lambda=1.5$ \+ wd = 0.001 | $\mathbf{5.82\pm 0.2}$ | $6.53\pm 0.16$ | $5.08\pm 0.15$
$\lambda=1.5$ \+ wd = 0.1 | $6.15\pm 0.15$ | $5.82\pm 0.16$ | $6.57\pm 0.1$
$\lambda=1.5$ \+ es($\mathcal{L}_{P})$ | $6.37\pm 0.25$ | $5.63\pm 0.3$ | $4.70\pm 0.07$
$\lambda=1.5$ \+ fl = 0.05 | $6.28\pm 0.25$ | $6.30\pm 0.23$ | $5.49\pm 0.17$
$\lambda=1.5$ \+ fl = 0.1 | $6.30\pm 0.3$ | $\mathbf{5.25\pm 0.25}$ | $\mathbf{4.67\pm 0.12}$

###  5.3 Impact of Regularization in Over-parameterized Regime

We now examine if additional regularization can help improve the fairness of
MinDiff-regularized models in the over-parameterized regime. Unless otherwise
stated, in all subsequent evaluations we perform post-training threshold
correction with a $\operatorname{\Delta_{FNR}}\leq 10\%$ constraint and
compare fairness constrained test error.

##### Batch sizing only helps around the interpolation threshold.

Small batch sizes cause primary training loss curves to converge more slowly,
potentially providing more opportunity for MinDiff optimizations. In Figure
5(a) and Figure 5(b), we plot fairness constrained test error curves versus
model widths for different batch sizes on the Waterbirds and CelebA datasets,
respectively. We find that smaller batch sizes improve fairness constrained
test error only around the interpolation threshold for both the datasets, but
do not noticeably benefit smaller and larger models. On further examination,
we note the benefits around the interpolation threshold are because smaller
batch sizes induce stronger regularization effects and push the interpolation
threshold to the right (see Appendix Figure 9). As a result, MinDiff is
effective on a slightly increased range of model widths. However, other than
this behaviour, we see no other benefits of using batch sizing as a
regularizer and do not explore it further.

##### Early stopping criterion.

We evaluate two methods for early stopping. The first uses the primary
validation loss (MinDiff+es($\mathcal{L}_{P}$)) as a stopping criterion, while
the second uses total validation loss for stopping
(MinDiff+es($\mathcal{L}_{T}$)). Figure 6 plots fairness constrained test
error versus model width for these two schemes and different values of
$\lambda$ on Waterbirds, and Table 2 shows the same data for CelebA. We find
that both schemes improve fairness for over-parameterized models, but have
limited impact in the under-parameterized regime. For Waterbirds, the
differences between the two are small, although using primary validation loss
as the stopping criterion (MinDiff+es($\mathcal{L}_{P}$)) is marginally better
than using total validation loss (MinDiff+es($\mathcal{L}_{T}$)). However, for
CelebA, we find that primary loss stopping criterion
(MinDiff+es($\mathcal{L}_{P}$)) is substantially better than total loss
stopping criterion (MinDiff+es($\mathcal{L}_{T}$)), especially for large
models. Thus, we use the former for the remainder of our experiments.

##### Comparing regularization methods on Waterbirds.

In Figure 7, we plot the fairness constrained test error versus model width
for different regularization schemes including early stopping ($\lambda+$es),
weight decay with two different values ($\lambda+$wd=0.001, $\lambda+$wd=0.1)
and flooding ($\lambda+$fl) on Waterbirds. We find that the early stopping and
weight decay regularizes substantially improve fairness for models just below
the interpolation threshold and all over-parameterized models. In contrast,
flooding shows only small improvements in fairness. For $\lambda=0.5$, we find
that early stopping is the best across the board. For $\lambda=1.5$, either
early stopping and weight decay are the best depending on model width,
although the differences are small.

(a) $\lambda=0.5$

(b) $\lambda=1.0$

(c) $\lambda=1.5$

Figure 6: We plot the fairness constrained test error (with a
$\operatorname{\Delta_{FNR}}\leq 10\%$ constraint) of early stopped MinDiff
models (trained with $\lambda=\\{0.5,1.0,1.5\\}$) for several model widths. We
compare two methods for early stopping (es) based on the stopping criterion:
primary validation loss (es($\mathcal{L}_{P}$)) and total validation loss
(es($\mathcal{L}_{T}$)). We find that, for Waterbirds dataset, using either
stopping criterion will significantly improve fairness constrained error,
especially in the over-parameterized regime.

(a) $\lambda=0.5$

(b) $\lambda=1.5$

Figure 7: We plot fairness constrained test error (with a
$\operatorname{\Delta_{FNR}}\leq 10\%$ constraint) versus model widths for
different regularization schemes used in conjunction with MinDiff optimization
on Waterbirds dataset. We find that early stopping and weight decay are
preferred choice of regularizers for Waterbirds dataset. Notation: wd is
weight decay, es($\mathcal{L}_{P}$) is early stopping w.r.t primary loss and
fl is flooding.

##### Comparing regularization methods on CelebA.

Table 3 compares different regularization schemes on the CelebA dataset for
three model widths and for $\lambda=0.5$, $\lambda=1.0$ and $\lambda=1.5$,
respectively. For the smallest model, we find that weight decay schemes result
in the lowest fairness constrained error, while for the large over-
parameterized model, flooding works best. Comparing across model widths, we
find that for each $\lambda$ value, the largest model with flooding provides
the overall lowest fairness constrained test error. Recalling that flooding
was ineffective on Waterbirds, we conclude that no one regularizer works best
across datasets and model widths, but additional regularization in general can
restore the benefits of over-parameterization with fairness constraints.

##  6 Conclusion

In this paper, we have critically examined the performance MinDiff, an in-
training fairness regularization technique implemented within TensorFlow’s
Responsible AI toolkit, with respect to DNN model complexity, with a
particular eye towards over-parameterized models. On two datasets commonly
used in fairness evaluations, we find that although MinDiff improves the
fairness of under-parameterized models relative to baseline, it is ineffective
in improving fairness for over-parameterized models. As a result, we find that
for one of our two datasets, under-parameterized MinDiff models have lower
fairness constrained test error than their over-parameterized counterparts,
suggesting that time-consuming searches for best model size might be necessary
when MinDiff is used with the goal of training a fair model.

To address these concerns, we explore traditional batch sizing, weight decay
and early stopping regularizers to improve MinDiff training, in addition to
flooding, a recently proposed method that is evaluated for the first time in
the context of fair training. We find that batch sizing is ineffective in
improving fairness except for model widths near the interpolation threshold.
The other regularizers do improve fairness for over-parameterized models, but
the best regularizer depends on the dataset and model size. In particular,
flooding results in the fairest models on the CelebA dataset, suggesting its
utility in the fairness toolkit. Finally, we show that with appropriate choice
of regularizer, over-parameterized models regain their benefits over under-
parameterized counterparts even from a fairness lens.

## Availability

Code with README.txt file is available at:
https://anonymous.4open.science/r/fairml-EBEE/

## References

  * Agarwal et al. (2018) Agarwal, A., Beygelzimer, A., Dudík, M., Langford, J., and Wallach, H.  A reductions approach to fair classification, 2018.
  * (2) AI, T. R.  Responsible ai toolkit: Tensorflow.  URL https://www.tensorflow.org/responsible_ai.
  * Akihiko Fukuchi (2020) Akihiko Fukuchi, Yoko Yabe, M. S.  Fairtorch.  https://github.com/wbawakate/fairtorch, 2020.
  * Barrett & Dherin (2021) Barrett, D. and Dherin, B.  Implicit gradient regularization.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=3q5IqUrkcF.
  * Beutel et al. (2017) Beutel, A., Chen, J., Zhao, Z., and Chi, E. H.  Data decisions and theoretical implications when adversarially learning fair representations, 2017.
  * Beutel et al. (2019) Beutel, A., Chen, J., Doshi, T., Qian, H., Woodruff, A., Luu, C., Kreitmann, P., Bischof, J., and Chi, E. H.  Putting fairness principles into practice: Challenges, metrics, and improvements.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , AIES ’19, pp. 453–459, New York, NY, USA, 2019. Association for Computing Machinery.  ISBN 9781450363242.  doi: 10.1145/3306618.3314234.  URL https://doi.org/10.1145/3306618.3314234.
  * Biega et al. (2018) Biega, A. J., Gummadi, K. P., and Weikum, G.  Equity of attention: Amortizing individual fairness in rankings.  _The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval_, 2018.
  * Buolamwini & Gebru (2018) Buolamwini, J. and Gebru, T.  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In Friedler, S. A. and Wilson, C. (eds.), _Proceedings of the 1st Conference on Fairness, Accountability and Transparency_ , volume 81 of _Proceedings of Machine Learning Research_ , pp. 77–91. PMLR, 23–24 Feb 2018.  URL https://proceedings.mlr.press/v81/buolamwini18a.html.
  * Cherepanova et al. (2021) Cherepanova, V., Nanda, V., Goldblum, M., Dickerson, J. P., and Goldstein, T.  Technical challenges for training fair neural networks, 2021.
  * Chouldechova (2017) Chouldechova, A.  Fair prediction with disparate impact: A study of bias in recidivism prediction instruments.  _Big Data_ , 5(2):153–163, 2017.  doi: 10.1089/big.2016.0047.  URL https://doi.org/10.1089/big.2016.0047.  PMID: 28632438.
  * Chzhen et al. (2019) Chzhen, E., Denis, C., Hebiri, M., Oneto, L., and Pontil, M.  _Leveraging Labeled and Unlabeled Data for Consistent Fair Binary Classification_.  Curran Associates Inc., Red Hook, NY, USA, 2019.
  * Collell et al. (2016) Collell, G., Prelec, D., and Patil, K. R.  Reviving threshold-moving: a simple plug-in bagging ensemble for binary and multiclass imbalanced data.  _ArXiv_ , abs/1606.08698, 2016.
  * Dixon et al. (2018) Dixon, L., Li, J., Sorensen, J., Thain, N., and Vasserman, L.  Measuring and mitigating unintended bias in text classification.  In _Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society_ , AIES ’18, pp. 67–73, New York, NY, USA, 2018. Association for Computing Machinery.  ISBN 9781450360128.  doi: 10.1145/3278721.3278729.  URL https://doi.org/10.1145/3278721.3278729.
  * Donini et al. (2018) Donini, M., Oneto, L., Ben-David, S., Shawe-Taylor, J., and Pontil, M.  Empirical risk minimization under fairness constraints.  In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_ , NIPS’18, pp. 2796–2806, Red Hook, NY, USA, 2018. Curran Associates Inc.
  * Feldman et al. (2015) Feldman, M., Friedler, S. A., Moeller, J., Scheidegger, C., and Venkatasubramanian, S.  Certifying and removing disparate impact.  In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , KDD ’15, pp. 259–268, New York, NY, USA, 2015. Association for Computing Machinery.  ISBN 9781450336642.  doi: 10.1145/2783258.2783311.  URL https://doi.org/10.1145/2783258.2783311.
  * Goel et al. (2018) Goel, N., Yaghini, M., and Faltings, B.  Non-discriminatory machine learning through convex fairness criteria.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 32(1), Apr. 2018.  URL https://ojs.aaai.org/index.php/AAAI/article/view/11662.
  * Grother et al. (2010) Grother, P., Quinn, G., and Phillips, P.  Report on the evaluation of 2d still-image face recognition algorithms, 2010-06-17 2010.
  * Hardt et al. (2016a) Hardt, M., Price, E., Price, E., and Srebro, N.  Equality of opportunity in supervised learning.  In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 29. Curran Associates, Inc., 2016a.  URL https://proceedings.neurips.cc/paper/2016/file/9d2682367c3935defcb1f9e247a97c0d-Paper.pdf.
  * Hardt et al. (2016b) Hardt, M., Price, E., Price, E., and Srebro, N.  Equality of opportunity in supervised learning.  In Lee, D., Sugiyama, M., Luxburg, U., Guyon, I., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 29. Curran Associates, Inc., 2016b.  URL https://proceedings.neurips.cc/paper/2016/file/9d2682367c3935defcb1f9e247a97c0d-Paper.pdf.
  * Hashimoto et al. (2018) Hashimoto, T. B., Srivastava, M., Namkoong, H., and Liang, P.  Fairness without demographics in repeated loss minimization.  In _ICML_ , 2018.
  * Ishida et al. (2020) Ishida, T., Yamane, I., Sakai, T., Niu, G., and Sugiyama, M.  Do we need zero training loss after achieving zero training error?  In III, H. D. and Singh, A. (eds.), _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pp. 4604–4614. PMLR, 13–18 Jul 2020.  URL https://proceedings.mlr.press/v119/ishida20a.html.
  * Jiang et al. (2020) Jiang, R., Pacchiano, A., Stepleton, T., Jiang, H., and Chiappa, S.  Wasserstein fair classification.  In Adams, R. P. and Gogate, V. (eds.), _Proceedings of The 35th Uncertainty in Artificial Intelligence Conference_ , volume 115 of _Proceedings of Machine Learning Research_ , pp. 862–872. PMLR, 22–25 Jul 2020.  URL https://proceedings.mlr.press/v115/jiang20a.html.
  * Karkkainen & Joo (2021) Karkkainen, K. and Joo, J.  Fairface: Face attribute dataset for balanced race, gender, and age for bias measurement and mitigation.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pp. 1548–1558, 2021.
  * Khandani et al. (2010) Khandani, A. E., Kim, A. J., and Lo, A. W.  Consumer credit-risk models via machine-learning algorithms.  _Journal of Banking & Finance_, 34(11):2767–2787, 2010.  ISSN 0378-4266.  doi: https://doi.org/10.1016/j.jbankfin.2010.06.001.  URL https://www.sciencedirect.com/science/article/pii/S0378426610002372.
  * Krogh & Hertz (1992) Krogh, A. and Hertz, J.  A simple weight decay can improve generalization.  In Moody, J., Hanson, S., and Lippmann, R. P. (eds.), _Advances in Neural Information Processing Systems_ , volume 4. Morgan-Kaufmann, 1992.  URL https://proceedings.neurips.cc/paper/1991/file/8eefcfdf5990e441f0fb6f3fad709e21-Paper.pdf.
  * Lahoti et al. (2020) Lahoti, P., Beutel, A., Chen, J., Lee, K., Prost, F., Thain, N., Wang, X., and Chi, E. H.  Fairness without demographics through adversarially reweighted learning, 2020.
  * Li et al. (2019) Li, M., Soltanolkotabi, M., and Oymak, S.  Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks, 2019.
  * Liu et al. (2015) Liu, Z., Luo, P., Wang, X., and Tang, X.  Deep learning face attributes in the wild.  In _Proceedings of International Conference on Computer Vision (ICCV)_ , December 2015.
  * Madras et al. (2018) Madras, D., Creager, E., Pitassi, T., and Zemel, R.  Learning adversarially fair and transferable representations, 2018.
  * Martinez et al. (2020) Martinez, N., Bertran, M., and Sapiro, G.  Minimax pareto fairness: A multi objective perspective, 2020.
  * Menon et al. (2021a) Menon, A. K., Jayasumana, S., Rawat, A. S., Jain, H., Veit, A., and Kumar, S.  Long-tail learning via logit adjustment.  In _International Conference on Learning Representations_ , 2021a.  URL https://openreview.net/forum?id=37nvvqkCo5.
  * Menon et al. (2021b) Menon, A. K., Rawat, A. S., and Kumar, S.  Overparameterisation and worst-case generalisation: friend or foe?  In _International Conference on Learning Representations_ , 2021b.  URL https://openreview.net/forum?id=jphnJNOwe36.
  * Morgan & Bourlard (1990) Morgan, N. and Bourlard, H.  _Generalization and Parameter Estimation in Feedforward Nets: Some Experiments_ , pp. 630–637.  Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1990.  ISBN 1558601007.
  * Nakkiran et al. (2020) Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B., and Sutskever, I.  Deep double descent: Where bigger models and more data hurt.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=B1g5sA4twr.
  * Ngan & Grother (2015) Ngan, M. and Grother, P.  Face recognition vendor test (frvt) - performance of automated gender classification algorithms, 2015-04-20 2015.
  * Padala & Gujar (2021) Padala, M. and Gujar, S.  Fnnc: Achieving fairness through neural networks.  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence_ , IJCAI’20, 2021.  ISBN 9780999241165.
  * Prost et al. (2019) Prost, F., Qian, H., Chen, Q., Chi, E. H., Chen, J., and Beutel, A.  Toward a better trade-off between performance and fairness with kernel-based distribution matching, 2019.
  * Quadrianto et al. (2019) Quadrianto, N., Sharmanska, V., and Thomas, O.  Discovering fair representations in the data domain.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.
  * Ryu et al. (2018) Ryu, H. J., Adam, H., and Mitchell, M.  Inclusivefacenet: Improving face attribute detection with race and gender diversity, 2018.
  * Sagawa et al. (2020a) Sagawa, S., Koh, P. W., Hashimoto, T. B., and Liang, P.  Distributionally robust neural networks.  In _International Conference on Learning Representations_ , 2020a.  URL https://openreview.net/forum?id=ryxGuJrFvS.
  * Sagawa et al. (2020b) Sagawa, S., Raghunathan, A., Koh, P. W., and Liang, P.  An investigation of why overparameterization exacerbates spurious correlations.  In _ICML_ , pp. 8346–8356, 2020b.  URL http://proceedings.mlr.press/v119/sagawa20a.html.
  * Savani et al. (2020) Savani, Y., White, C., and Govindarajulu, N. S.  Intra-processing methods for debiasing neural networks, 2020.
  * Schumann et al. (2020) Schumann, C., Foster, J. S., Mattei, N., and Dickerson, J. P.  We need fairness and explainability in algorithmic hiring.  In _Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems_ , AAMAS ’20, pp. 1716–1720, Richland, SC, 2020. International Foundation for Autonomous Agents and Multiagent Systems.  ISBN 9781450375184.
  * Singh & Joachims (2018) Singh, A. and Joachims, T.  Fairness of exposure in rankings.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery &; Data Mining_, KDD ’18, pp. 2219–2228, New York, NY, USA, 2018. Association for Computing Machinery.  ISBN 9781450355520.  doi: 10.1145/3219819.3220088.  URL https://doi.org/10.1145/3219819.3220088.
  * Smith et al. (2021) Smith, S. L., Dherin, B., Barrett, D., and De, S.  On the origin of implicit regularization in stochastic gradient descent.  In _International Conference on Learning Representations_ , 2021.  URL https://openreview.net/forum?id=rq_Qr0c1Hyo.
  * Srivastava et al. (2014) Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I., and Salakhutdinov, R.  Dropout: A simple way to prevent neural networks from overfitting.  _Journal of Machine Learning Research_ , 15(56):1929–1958, 2014.  URL http://jmlr.org/papers/v15/srivastava14a.html.
  * Wadsworth et al. (2018) Wadsworth, C., Vera, F., and Piech, C.  Achieving fairness through adversarial learning: an application to recidivism prediction, 2018.
  * Wang & Deng (2019) Wang, M. and Deng, W.  Mitigate bias in face recognition using skewness-aware reinforcement learning, 2019.
  * Wang et al. (2020) Wang, Z., Qinami, K., Karakozis, I. C., Genova, K., Nair, P., Hata, K., and Russakovsky, O.  Towards fairness in visual recognition: Effective strategies for bias mitigation, 2020.
  * Wei et al. (2020) Wei, D., Ramamurthy, K. N., and Calmon, F.  Optimized score transformation for fair classification.  In Chiappa, S. and Calandra, R. (eds.), _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pp. 1673–1683. PMLR, 26–28 Aug 2020.  URL https://proceedings.mlr.press/v108/wei20a.html.
  * Zafar et al. (2019) Zafar, M. B., Valera, I., Gomez-Rodriguez, M., and Gummadi, K. P.  Fairness constraints: A flexible approach for fair classification.  _Journal of Machine Learning Research_ , 20(75):1–42, 2019.  URL http://jmlr.org/papers/v20/18-262.html.
  * Zhang et al. (2018) Zhang, B. H., Lemoine, B., and Mitchell, M.  Mitigating unwanted biases with adversarial learning, 2018.
  * Zhou & Liu (2006) Zhou, Z.-H. and Liu, X.-Y.  Training cost-sensitive neural networks with methods addressing the class imbalance problem.  _IEEE Transactions on Knowledge and Data Engineering_ , 18(1):63–77, 2006.  doi: 10.1109/TKDE.2006.17.

##  Appendix A Impact of Regularization in Over-parameterized Regime

###  A.1 Batch Size

####  A.1.1 Waterbirds

(a) MinDiff ($\lambda=0.5$) (b) MinDiff ($\lambda=1.0$) (c) MinDiff
($\lambda=1.5$)

Figure 8: Batch size - THR with fairness constraint $<$ 10%

(a) MinDiff ($\lambda=0.5$) (b) MinDiff ($\lambda=1.0$) (c) MinDiff
($\lambda=1.5$)

Figure 9: Training loss vs model widths for different batch sizes

###  A.2 All Other Regularizers

####  A.2.1 Waterbirds

(a) MinDiff ($\lambda=0.5$) (b) MinDiff ($\lambda=1.0$) (c) MinDiff
($\lambda=1.5$)

Figure 10: Regularization - THR with fairness constraint $<$ 10%

####  A.2.2 CelebA

Table 4: We tabulate the fairness constrained test error (with a
$\Delta_{FNR}\leq 10\%$ constraint) for different regularization schemes used
in conjunction with MinDiff optimization ($\lambda=0.5$) on CelebA dataset.
The performance of best regularizer is highlighted in bold for each model
width. Notation: wd is weight decay, es($\mathcal{L}_{P}$) is early stopping
w.r.t primary loss and fl is flooding

Method | Width = 5 | Width = 19 | Width = 64
---|---|---|---
| Under- | Over- | Over-
$\lambda=0$ | $5.92\pm 0.27$ | $6.51\pm 0.16$ | $5.76\pm 0.14$
$\lambda=0.5$ | $6.36\pm 0.72$ | $6.54\pm 0.17$ | $5.88\pm 0.19$
$\lambda=0.5$ \+ wd = 0.001 | $5.89\pm 0.32$ | $6.94\pm 0.18$ | $6.25\pm 0.48$
$\lambda=0.5$ \+ wd = 0.1 | $\mathbf{5.66\pm 0.18}$ | $\mathbf{5.27\pm 0.16}$ | $6.40\pm 0.18$
$\lambda=0.5$ \+ es($\mathcal{L}_{P}$) | $6.17\pm 0.48$ | $5.91\pm 0.37$ | $5.45\pm 0.32$
$\lambda=0.5$ \+ fl = 0.05 | $6.45\pm 0.69$ | $6.53\pm 0.21$ | $6.16\pm 0.09$
$\lambda=0.5$\+ fl = 0.1 | $6.34\pm 0.63$ | $5.75\pm 0.35$ | $\mathbf{4.80\pm 0.28}$

Table 5: We tabulate the fairness constrained test error (with a
$\Delta_{FNR}\leq 10\%$ constraint) for different regularization schemes used
in conjunction with MinDiff optimization ($\lambda=1.0$) on CelebA dataset.
The performance of best regularizer is highlighted in bold for each model
width. Notation: wd is weight decay, es($\mathcal{L}_{P}$) is early stopping
w.r.t primary loss and fl is flooding

Method | Width = 5 | Width = 19 | Width = 64
---|---|---|---
| Under- | Over- | Over-
$\lambda=0$ | $5.92\pm 0.27$ | $6.51\pm 0.16$ | $5.76\pm 0.14$
$\lambda=1.0$ | $6.25\pm 0.61$ | $6.43\pm 0.17$ | $6.06\pm 0.09$
$\lambda=1.0$ \+ wd = 0.001 | $5.94\pm 0.39$ | $6.75\pm 0.35$ | $5.90\pm 0.24$
$\lambda=1.0$ \+ wd = 0.1 | $\mathbf{5.80\pm 0.17}$ | $5.55\pm 0.19$ | $6.42\pm 0.12$
$\lambda=1.0$ \+ es($\mathcal{L}_{P}$) | $6.32\pm 0.40$ | $5.82\pm 0.46$ | $4.79\pm 0.24$
$\lambda=1.0$ \+ fl = 0.05 | $6.30\pm 0.68$ | $6.43\pm 0.17$ | $5.87\pm 0.11$
$\lambda=1.0$ \+ fl = 0.1 | $6.33\pm 0.52$ | $\mathbf{5.4\pm 0.35}$ | $\mathbf{4.77\pm 0.13}$