FLEA: Provably Robust Fair Multisource Learning from Unreliable Training Data
Authors: Eugenia Iofinova
Nikola Konstantinov
Christoph H Lampert
Venue: Accepted by TMLR ()

Abstract: Fairness-aware learning aims at constructing classifiers that not only make accurate predictions, but also do not discriminate against specific groups. It is a fast-growing area of machine learning with far-reaching societal impact. However, existing fair learning methods are vulnerable to accidental or malicious artifacts in the training data, which can cause them to unknowingly produce unfair classifiers. In this work we address the problem of fair learning from unreliable training data in the robust multisource setting, where the available training data comes from multiple sources, a fraction of which might not be representative of the true data distribution. We introduce FLEA, a filtering-based algorithm that identifies and suppresses those data sources that would have a negative impact on fairness or accuracy if they were used for training. As such, FLEA is not a replacement of prior fairness-aware learning methods but rather an augmentation that makes any of them robust against unreliable training data. We show the effectiveness of our approach by a diverse range of experiments on multiple datasets. Additionally, we prove formally that –given enough data– FLEA protects the learner against corruptions as long as the fraction of affected data sources is less than half. Our source code and documentation are available at https://github.com/ISTAustria-CVML/FLEA.

Published in Transactions on Machine Learning Research (09/2022)
FLEA: Provably Robust Fair Multisource Learning from Unreliable Training Data
Eugenia Iofinova"
eugenia.iofinan iofinova @ist. ac.
Institute of Science and Technology Austria (ISTA)
Nikola Konstantinov
mukolahristov.konss/ee wwnstantinoow@nnn.coco ethz.cth
ETH Al Center and ETH Department of Computer Science
Christoph H. Lampert
chl@ist.ac..t
Instibute of Science and Technology Austria (ISTA)
Reviewed on OpenReview: https: oppenreveee, net/ forum? XsPopigZXV
Abstract
Fairness-aware learning aims constructing classifiers that not only make accurate pre- dictions, but also do not discriminate against specific groups. It is a fast-growing area of machine learning with far-reaching societal impact. However, existing fair learning methods are vulnerable to accidental or malicious artifacts in the training data, which can cause them to unknowingly produce unfair classifiers. In this work we address the problem of fair learning from unreliable training data in the robust multisource setting, where the available training data comes from multiple sources, fraction of which might not be rep- resentative of the true data. distribution. We introduce FLEA, flltering-base algorithm that identifies and suppresses those data sources that would have negative impact fairness accuracy if they were used for training. As such, FLEA is not a replacement of prior fairness-aware learning methods but rather an augmentation that makes any of them robust against unreliable training data. We show the effectiveness of our approach by a diverse range of experiments on multiple datasets. Additionally, we prove formally that given enough data- FLEA protects the learner against corruptions as long as the fraction of affected data sources is less than half. Our source code and documentation are available at http://gthhb...cm./SSSatstr...a.
1 Introduction
Machine learning systems have started to permeate many aspects of our everyday life, such as finance (e.g. credit scoring), employment (c.g. judging job applications) or even judiciary (e.g. recidivism prediction). the wake of this trend, other aspects besides prediction accuracy become important to consider. One crucial aspect is (group) fairness, which aims at preventing learned classifiers from acting in a discriminatory way. To achieve this goal, Cairness-aware learning methods adjust the classifier parameters in order to fulfill an appropriate measure of fairness. This strategy is highly successful, but only under idealized conditions of clean t..dl-sampled data. Unfortunately, fairness-aware learning methods are not robust against unintentional errors or intentional manipulations of the training data.
"These authors contributed equally.
This manuscript differs from the accepted camera-ready version: the definition of demographic parity violation has been changed allow for two-sided bounds in Theorem 1. The proof in Appendix F' has been adjusted accordingly.

---

Published in Transactions on Machine Learning Research (09/2022)
data sources
ordinary multi-source learning
FLEA
pooling
FILTERSOURCES
(Tairnss aware)
(fairness aware)
training
training
unfair classifier
fair classifier
Illustration of robust multisource learning with FLEA: (top) We are given multiple sources, some of which might contain noisy manipulated data. (left) Ordinary multisource learning pools the data from all sources, which can cause the resulting classifier to be inaccurate and/or unfair, even if fairness-aware training is employed. (right) FLEA filters the data before pooling, thereby suppressing likely corrupted sources. This allows fairness-aware training to succeed.
Figure 1:
In this work, we address this problem in a setting where the training data is not one monolithic block, but rather centralized collection of data obtained from multiple sources. This is, in fact, common scenario. For instance, organizations that specialize in large-scale data mining, such large hospital chains political analysis firms, may receive data that is collected separately from multiple physical locations or data vendors. In such cases, it may be that not all of these data sources are completely trustworthy, and so robust.ness concerns arise.
In order achieve robustness to unreliable data in such contexts, we propose new algorithm, FLEA (Fair LEarning against Adversaries). FLEA adds a filtering step top of any standard fairness-aware learning algorithm and effectively identifies and suppresses data sources that could have a negative impact the classifier fairness accuracy. Thereby, FLEA acts as procedure that guarantees robustness in the context. of fair learning.
To accomplish this, we introduce a new dissimilarity measure, disparity, that measures the maximum achievable difference in classifier fairness between two data sources. We use this measure as a filtering criterion, since it has the property of flagging changes in the data distribution that can be potentially harmful for the end-classifier fairness. We combine this with the existing discreponcy measure, which plays an analogous role for the classifier accuracy, and the disbalance, which measures changes to the group composition of the training data. We show both empirically and theoretically that combination of these three measures provides sufficient criterion for detecting harmful data, as long as the fraction of harmful sources is less than half
While previous method for robust. Tairness-aware learning were only able to protect against specific data issues, such random label flips, FLEA ensures that even a worst-case adversary unable negatively affect the training process: either the changes to the data are minor and will not hurt learning, or they large enough so that the affected data sources are identified and removed. Our theoretical analysis provides finile sample guarantees and certifies the ability of FLEA to learn classifiers with optimal fairness and accuracy in the infinite sample size limit. Our extensive experimental evaluation demonstrates FLEA's practical usefulness in suppressing the effect of corrupted data when learning fair models, even in cases where previous robust. methods fail.
2 Preliminaries and related work
2.1 Fair classification
Throughout this work, adopt standard classification setting in which the task is to predict binary label e (0,1) for any x E X. For fixed data distribution p(z, y) P(X x })) the classic goal of learning
The where half more sources are harmful impossible solve in general, see egg. Charikar al. 2017
2

---

Published in Transactions on Machine Learning Research (09/2022)
is to find prediction function f: X + 3 with high accuracy, i.c small risk, Ry(f) Ep(a,)) 1 f())), where [(P]= 1 if a predicate P is true and 1 [(P) = 0 otherwise.
With the recent trend to consider not only the accuracy but also the fairness of a classifier, a number of statistical measures have been proposed to formalize this notion. In this work, we focus on the most common and simplest one, demographic parily (DP) [Calders et al. 2009). It postulates that the probability of a positive classifier decision should be equal for all subgroups of the population. Formally, we assume that each example (x. y) also possesses protected attribute, subgroup of the population. For example, could indicate race, gender exposition, we treat the protected attribute as binary-valued, but extensions to multi-valued attributes are (traightforward by summing over all pairwise terms. Note that might be a component or a function of æ; in which case it is available at prediction time, or it might be contextual information, in which case it would only be available for the learning algorithm at training time, but not for the resulting classifier at prediction time. We cover both aspects by treating as an additional random variable, and write the underlying joint data distribution as p(r, y, a).
A, which indicates its membership in a specific disability. For simplicity of
For classifier f f: X + {0, 1}, the demographic parity violation, Lp, and the empirical counterpart, I's for dataset S C X x y x A are defined as (Calders et al. 2009; Dwork et al. 2012
Tf(()= = E o) - (x)),
1 Ts( na=0 xESamD
Es(s)
1 E)(r) nam1
(1)
xESa-1
Negative values of the demographic parity violation indicate unfairness against. group 0, while positive values indicate unfairness against group 1. Analogous quantities can be defined for related fairness measures, such as equality of opportunity equalized odds (Hardt et al.] 2016 Zafar et al. 2017a). A detailed description of these and many others choices can be found in Barocas et al. (019)).
Fairness-aware learning In the last years, a plethora of algorithms have been developed that are able to learn classifiers that are not only accurate but also fair, see, for example Mehrabi et al. (2021a) for an overview. They mostly rely on one or multiple of four core mechanisms. Preprocessing methods (Kamiran & Calders 2012 Calmon et al. 2017 Wang et al. 2019; Celis et al., 2020) change the training data to remove potential bias. This is often simple and effective, but comes with the danger of reduced accuracy, since the data distribution at training time will not reflect the distribution al prediction time anymore. Poslprocessing
methods (Hardt et al.) 2016 Woodworth et al. 2017 Chzhen et al. 2020) adjust the acceptance thresholds of a previously trained classifier for each protected group, so that the desired fairness criterion is met. This is a simple, reliable and often effective method, but it requires the protected attribute to be available at prediction
time. Penalty-baase based methods (Kamishima et al. 2012 Zemel et al. 2013 Zafar et al. 2017bb Donini et al. Mandal et al.) 2020 Chuang & Mroueh| 2021) add a regularizer or constraints to the learning objective
2018
that penalize prevent parameter choices that lead to unfair decisions. Adversarial methods (Beutel et al.
2017 Wadsworth et al.
2020 train an adversary in parallel to the classifier that tries to predict the protected attribute from the model outputs; if this cannot be done better
2018 Zhang et al.) 2018 Lahoti et al.
than chance level, fairness is achieved.
Many other methods have been proposed, e.g. based on distriiuutonaall robust optimization Rezaei et al. 2020 or tailored to specific family of classifiers or optimization procodures (Cho et al., 2020: Tan al., 2020 They all share, however, the property that accurate information about the data distribution and the protected attribute is needed at training time.
If the training data is not representative of the actual data distribution, e.g. it is noisy, biased, or has been manipulated, then -orreinn mechanisms fall short (Kallus et al. 2020 Mehrabi et al. 2021b). Partial solutions have been proposed, e.g., when only the protected attribute or only the label is noisy (Lany et al.) 2019: Wang et al.] 22020) Celis et al.) 22021b a Mchrotra Colis 2021 Roh et al.] 2021). However, as shown in Konstantinov & Lampert (2022). full protection against malicious manipulations of the training data is provably impossible when learning from single dataset.
3

---

Published in Transactions on Machine Learning Research (09/2022)
2.2 Robust multisource learning
Learning from multiple sources The multisource learning setting formalizes the increasingly frequent situation in which the training data is not collected as a single batch, but from multiple data sources (Ting
& Loo 1997; Russakovsky et al.) 2015). For bairness-aware learning, this means we are given N datasets, S1...., Sy C x y A. Fach S. [(of" 3i a
Yi. an.)) }} contains i.i.d. samples from a data distribution pa y. a). Given these datascts, the learning algorithm has the goal of selecting a prediction function f from a hypothesis class H that has as-small-as- possible risk (expected prediction error) and unfairness (e.g. demographic parity violation) with respect to the unknown distribution at prediction time, p(z, y: a), (also called target distribution). The classical setting of p1 P2 = = PN = P, we call homogeneous mullisource learning. Otherwise, we call the setting heterogeneous.
In clean data scenario, when all data distribution are the same or very similar to each other, then there is no drawback to simply merging all sources and training on the resulting large datasct. However, merging all data is not the best strategy when some of the data sources are unrepresentative, i... their data distribution differs lot from the target one. Such data can occur accidentally, for instance due to biases in the data collection or annotation process. In some cases, such issues can be overcome by domain adaptation techniques (Ben-David 2010 Crammer et al. 2008 Natarajan et al.] 2013). Unreprcsentative sources can also be the result of intentions ional manipulations, which are typically harder to detect and compensate for (Feng et al., 2019 Fowl In fact, the datascts might not be samples from any probability distribution in that case, but adversarially constructed.
ct al.
ct al. 2021
Robust multisource learning In this work aim to cover wide range of possible problems with some of the data sources as possible. Therefore, we study the multisource lcarning problem in the presence 2 In this setting, the adversary observes an original collection of N dalasets, Si,..., SN, where each S, contains i..d. samples from a data distribution (1 y, a). Next, the adversary manipulates the data in an arbitrary (deterministic or randomized) way with the only restriction that for a fixed subset of indices, G C fI......?? NY. the data source remains unaffected. That is, S, S. for all E G, and S; is arbitrary for E G. The subset G is unknown to the learning algorithm, of course. The adversary model places no restrictions on the corruptions, and thus subsumes many scenarios that have to otherwise be studied in isolation. In particular, both data-quality issues, such as sampling bias, data entry errors or label noise, as well as malicious manipulations, such as class erasure or data poisoning, are covered as special cases.
of an adversary
Multisource learning with protection against potential manipulations is known as robust multisource learn- ing (Erfani el al., 2017). In order to detect harmful sources, a natural approach is to compare all pairs of datasets with an appropriate distance measure and then use the pairwise distances to filter out sources that are far from the others. Key to the success of such approach is using the right definition of distance. On the one hand one must be able to estimate the measure from finite sample sets in statistically efficient cnoematiin-theorete measures, such as Kullback-Leibh divergence (Kullback & Leibler, 1951I, total variation (Tsybakov 2009) or Wasserstein distance (Villani 2009), do not fulfill this criterion. On the other hand, the measure must be sensitive enough such that if two sources appear similar then training on either of them must yield similar classifiers. Classical two-sample tests, such as Student's 's (-test. (Student, 1908) or MMD (Gretton al.
way. Many common
2012), fail to guarantee this.
In the context of multisource learning mcasure that combines both useful properties is the (empirical) discrepancy dislance. (Kiler el al. 2004 Mohri & Medinal 2012). For two datasets, SI, S2, and hypothesis set H. C {h: X + y}, it measures the maximal amount by which their estimates of the classification accuracy can differ:
(1) = sup Rs. (4) - (1)
NEW
where Rh) = 1st Eiswes 1V # h(z)} is the empérical risk of h on S. In Konstantinov et al. (2020) the discrepancy used as a distance measure to identify and suppress data sources that might harm the classifier's accuracy. However, the associated algorithm is mostly of theoretical interest: it only suppresses
2 Adversary the common computer scieuce term for a process whose aim is to prevent system from operating as intended. Our adversaries manipulate the training data and should not he confused with adversaries in adversarial machine learning, such as adversarial eaamples (Goodfellow al. 20155), or generative adversarial networks (Goodfellow et 2014).
4

---

Published in Transactions on Machine Learning Research (09/2022)
those sources of which it is certain that they have been manipulated using thresholds that are derived from its generalization bound. As consequence, it requires training sets that are too large to be practical. Similarly, Jain & Orlitsky (2020b) provide an analysis of the carning-thhoretic limitations of robust multisource learning. Konstantinov & Lampert (2019) also use the discrepancy measure for detecting harmful data sources, but the proposed algorithm requires access to a reference set that guaranteed be free of data manipulations. In Qiao & Valiant (2018); Chen et al. (2019); Jain Orlitsky (2020a) robust multisource learning addressod using tools from robust statistics, but only in the context of discrete density estimation. The problem of achieving robustness to noisy data annotators is also related (Awasthi et al. (2017); Khetan et al. (2018)), but more restricted, as in our context we allow for arbitrary changes of the inputs and protected attributes, in addition to the labels.
All of the above works are tailored to the task of ensuring high accuracy the learned classifiers or estimators, but they are not sensitive issues of fairness. To our awareness, the only prior work that considers achieving fairness in multisource learning sctting and in the presence of data corruption the one of Li al.) (2021b). However, that paper focuses on personalized fedevaled learning and fairness objective tailored to federated learning, which postulates that models' performances should be relatively similar across edge devices. In contrast, we study a centralized sctup, where privacy and communication issues are not present and where single global model is trained. In addition, we aim to ensure that this model does not act discriminatory against members of protected subgroups, aligned with the classic notions of group fairness in supervised learning.
3
Fair multisource learning
The goal of this work is to develop method that allows fairness-aware learning, even if some of the available data sources are unrepresentative of the true training distribution. For this, we introduce FLFA, a filtering- based algorithm that identifies and suppresses those data sources that would negatively impact the fairness of the trained classifier. Its main innovation is the dispority measure for comparing datasets in terms of their fairness estimates.
Definition (Fmpirical Disparity). For two datasets S1 c XXX y' A, their empirical dispority with respect hypothesis class H is
disp(S,, sup I's (h) I's (h) beR
where rs : H - IR is an empirical faimneis measure, such as the demographic parity violation
The disparity measures the maximal amount by which the estimated fairness of a classifier in H. can differ between using S1 or S2 as the basis of the estimate. A small disparity value implics that if we construct a classifier that is fair with respect to Si, then it will also be fair with respect S2.
Definition D is inspired by the empirical discrepancy (2) Just as low discrepancy implies that a classifier learned
dataset will have comparable accuracy one learned on the other, low disparity implics that the two classifiers will have comparable fairness. FLEA makes use of the discrepancy well the disparity, because ensuring fairness alone does not suffice (e.g. constant classifier is perfectly fair). As third relevant quantity we introduce the (empirical) disbalance.
|
|Sg [S
disb(S,,
(4)
The disbalance compares the relative sizes of the protected groups of two datascts. Its inclusion is a technical requirement to be able to also formally prove that demographic parity fairness remains unaffected by corruptions.
In combination, disparity, discrepancy, and disbalance form an effective criterion for detecting datasct. manipulations. This is most apparent in the homogencous setting: two datasets of sufficient size are sampled i.i.d. from distributions close to the target one, then by the law of large numbers we can expect all
5

---

Published in Transactions on Machine Learning Research (09/2022)
three measures to be small. If one of the datasets is sampled like this (called clean from now on) but the other is manipulated, then there are two possibilities. It is still possible that all three values are small. In this case, equations (2) 4 ensure that neither accuracy nor fairness would be negatively affected, and we call such manipulations benign. at least one of the values is large, training on such a manipulated datasource could have undesirable consequences. Such manipulations we will call malignant. Finally, when comparing two manipulated datasets, discrepancy, disparity, and disbalance can each have arbitrary values.
In the heterogeneous setting, path of similar reasoning applies, though the measures for clean sources will not approach exactly zero due to the difference in their data distributions.
3.1 FLEA: Fair learning against adversaries
We now introduce the FLEA algorithm, which is able to learn fair classifiers even if up to half of the datasets are noisy, biased or have been manipulated. Similar to classic outlier rejection techniques (Barnett & Lewis 1984) and statistical two-sample tests (Corder & Foreman 2014), the main algorithm (Algorithm) ! takes a filtering approach. Given the available data sources and additional parameters, it calls a subroutine that identifics a subset of clean or benign sources, merges the training data from these, and trains a (prosumably lwirness-aware) learning algorithu on the resulting dataset.
FLEA's crucial component is the filtering subrou- tine. This estimates the pairwise disparity, dis- crepancy and disbalance between all pairs of data sources and combines them, by summing 3 into a matrix of dissimilarity scores (short: D-scores). As discussed above, large values indicate that at least one of the two compared sources must. be malignant. It is not a priori clear, though, how to use this information. On the one hand, we do not know which of the two datasets is malignant or if both arc.
Algorithm FLEA
Input: datascts S1,..., Sy
Input: quantile parameter 3
Input: (fairness-aware) learning algorithm C
1: I + F B)
2: S - S: S:
3: (
Output: trained model f: + y
Subroutine FILTERSOURCES
Input: S1, ....... Sx; 3 1: for i = I,... N do
On the other hand, malignant sources can also occur in pairs with small D-score, when both datascts were manipulated in similar ways. Fi- nally, even the D-scores between two clean or benign sources will have non-zero values, which depend number of factors, in particular the data distributions and the hypothesis class.
2:
for j = 1,..., N do
3:
Daj + disc (isc,S,, S5) + disp(S,, S,) + disb(S,,
4: end for
5:
qi 4 B-quantile( IDi,,...., Da,N)
end for
I (t:q: q: S B-quantilo((i,.... .... 9N)]
FLEA overcomes this problem by using tools from robust statistics. For any dataset S,, it computes
Output: index set I
value d (called g-value) as the 8-quantile of the D-scores all other datasets, where B is hyperparameter we discuss below. It then computes the 8-quantile of all such values and selects those datasets with q-values up to this threshold.
To see that this procedure has the desired effect of filtering out malignant datasets, we first look at the case K in which the sources are homogeneous and B = N where K = |G|
N is the number of clean data sources.
> 2
For any clean dataset S., by assumption there are at least K 1 other clean sources with which it is compared. We can expect the D-scores of these pairs are small, and, of course, that Dü = O. Because 3 N, the 3- quantile, qi, is simply the Kth-smallest of St's D-scores. Consequently, qi will be at least as small as the result of comparing two clean sources. For benign sources, the same reasoning applics, since their D-scores are indistinguishabl the ones where S; is compared to clean source. Hence, there can be at most N - K small D-scores for S..
from clean ones. For malignant S,, at least K of the D-scores will be large, namely
OOther aggregation methods would be possible, as long as they ensure preserve large values, such as the maximum. This would yield similar theoretical guarantees, but we did not find it to perform better in practice.
6

---

Published in Transactions on Machine Learning Research (09/2022)
Because BN = K and K > N - K, the 8-quantile 9s will be at least as large comparing clean dataset to malignant one.
Choosing those sources that fall into the 8-quantile of the qi values means selecting the K sources of smallest qi value. By the above argument, these will either be not manipulated at all, or only in a way that does not have a negative effect on either the fairness or the accuracy of the training process. In practice, the regimes of large and small D-scores can overlap due to noise in the sampling process, and the perfect filtering property will only hold approximately. We later discuss generalization bound that makes this reasoning rigorous.
N so in partieular for B 2 3. To obtain the guaranlee on the selected sources, B NV suffices. Therefore, even if the exact value of K is unknown in practice, setting 3 always be working choices. These are also the values we use in our experiments.
Revisiting the above arguments one sees that the guarantees on the qi follow also for any B> N-K K
N for even N and 3 =
+ 2N for odd N will
In the heterogeneous situation, the D-scores between clean sources might not lend to zero for large n anymore. However, they will approach the true discrepancy, disparity and disbalance values between the sources' distributions. From this, one can obtain a guarantce that the selected sources are not more dissimilar from each other than the clean sources are, which the best one can hope for in the heterogeneous setting.
3.2 Implementation
FLEA is straightforward to implement, with only the discrepancy and disparity estimates in the FILTER- SOURCES routine requiring some consideration. Naively, these would require optimizing combinatorial functions (the differences of fraction of errors positive decisions) over all functions in the hypothesis class. This task is at least as hard as the problem of scparating two point sets by hyperplane, which is known to be NP-hard (Marcolle& & Savard 1992) and even difficult to approximate under any real-world conditions. Instead, we exploit the structure of the optimization problems to derive tractable approximations.
We describe the procedure here and provide pscudocode in Appendix B For the discrepancy (2) such a method was originally proposed in the domain adaptation literature (Ben-David al.] 2010): finding the hypothesis with maximal accuracy difference between two datasets is equivalent to training binary classifier their union with the labels of one of the datasets flipped.
For the disparity 3 we propose an analogous route. Intuitively, the optimization step requires finding a hypothesis that is as unfair as possible on S1 (i.e. maximizes Ts,) while being as unfair as possible in the opposite direction on S2 (i.e. minimizes [s,), ) or vice versa. From Equation (1) one sees that a hypothesis f is maximally positively unfair if it outputs f(z) 1 on Sq=1 and f(x) = 0 on S S and maximally negatively unfair if it has the opposite outputs. Consequently,
estimate the disparity, we can use a classifier trained
on S2. To give both protected groups equal importance, as the definition requires, we use per-sample weights that are inversely proportional to the group sizes.
to predict fx) = S1 and fx=
3.3 Theoretical analysis
The informal justification of FLEA can be made precise in the form of generalization bound. In this section we present our theoretical guarantees for FLEA We begin by stating formally the assumptions we make on the data generating process, both for the heterogeneous and the homogeneous cases discussed above. We then state our main theoretical result, which certifies the performance of FLEA in the both the homogeneous and the more general heterogeneous case. Finally, we briefly outline the main proof steps. The full proofs can be found in Appendix F
3.3.1 Assumptions and formal adversarial model
First we present our formal set of assumptions, directly in the general sctting of heterogeneous data sources. A crucial parameter here setup n,, which denotes the amount of variability between the clean sources' distributions. The case of n) = 0 recovers the homogeneous setup.
7

---

Published in Transactions on Machine Learning Research (09/2022)
We assume the following data generation model, similar to the of Qiao & Valiant (018)) By p(æ, y, a) we denote the target distribution. It is unknown to the learning algorithm, though potentially known to the adversary. Initially, there are N datasets $1,..., SN, with the i-th set of samples being drawn i..d. from a distribution pz( y, a). These distributions might differ from the target distribution p by at most in terms of total variation both with respect to the overall distributions as well as the conditional distributions with respect a. Formally, we assume the following conditions for i = I....,N:
(pi y, a). p(a, y, 0)) S m. and max zEA
(TV(p 2), p(z, yla ==))] S n
(5)
where TV is the total voriation distance between probability distributions Halmos 2011
Once the clean datasets ,5. are sampled, an adversary operates on them. This results in new datasets, -1,..., Sv, which the learning algorithm receives as input. The adversary is arbitrary (deterministic randomized) function F: FIII:=1 (X x y x A) + II (X' y x A)" with the only restriction that for a fixed subset of indices, G. (L. (L...,, ,N, the data remains unchanged. That is, S, S, for all i E G, and S; is arbitrary for i G. For simplicity, refer to dataset S; or source [N] clean if E G.
3.3.2 Theoretical guarantees FLEA
We are now ready to state our theoretical guarantee on FLEA. For simplicity of notation, we present the case where all sources have the same number of samples. Results for general sample sizes can be obtaín in an analogous way. We first state the guarantees for the homogeneous situations, which we obtain in fact as a corollary for = 0 of the general theorem later in this section.
Theorem 1 (Homogencous setting). Assume that H has finite VC-dimension d 2 1. Let be an arbitrary target data distribution and without loss of generality let datasets, each consisting of n somples, out of which K > N
p(a 0) (0,0.5). Let SN be N 2 are sampled i.i.d. from the distribution p. For 1 < $ K and I = FILTERSOURCES( .N (3 set S u S,. Let 8 > 0. Then there erists constant C - C(,, N,n), such that for any 2 C, the following inequalities hold with probobility at least 1 - uniformly over all f E H and against any adversary:
N
( Ō (V
RR(f) - R,(0) (V
where Ô indicates Landau's 's O notation for function growth up to logarithmic factors CCormen et al. 2009).
Discussion To analyze the statement, we obsorve that Equation G ensures that for large enough training sets the filtered training data S becomes an arbitrarily good representative of the true underlying data distribution with respect to the classification accuracy as well as the fairness. Moreover, the approximation holds uniformly across all hypotheses in the class. We note that similar generalization bound for accuracy in the homogeneous setting is given in Konstantinov et al. (002
This uniform convergence property is similar to the classic concentration results from learning theory for learning with clean data (Shalev-Shwartz & Den-David 2014 Woodworth et al. 2017) and essentially ensures that using the data S is safe for the purposes of fairnes--wwan aware learning. Indeed, since the empirical risk and fairness deviation on the filtered data S are good estimates of the true population measures, any algorithm that uses the data S to learn hypothesis with good empirical fairness and accuracy will also perform well at prediction time.
Note that despite the intuitive conclusion, the result from Theorem | is highly non-trivial, due to the presence of data corruption. For example, in the case of learning from a single datasource in which a constant fraction of the data can be manipulated, an analogous theorem is provably impossible (Kearns & Li 1993 Konstantinov & Lampert 2022). This observation also implies that no learning algorithm can guarantee accurate and fair learning if it given access to the training data only after all sources have been merged.
For the general situation (1) 2 0), obtain the following guarantees:

---

Published in Transactions on Machine Learning Research (09/2022)
Theorem 1 (Heterogeneous setting). Assume that H. has a finite VC-dimension 2 1. Let p be arbitrary target data distribution and without loss of generality let T = =p(a- = 0) E (0, 0.5). Let , SN be N dalasets, each consisting of n samples, out of which K > N. are sampled i.i.d from data distributions pi that are y-close to the distribution p in the sense of Section 3.3.1 Assume that 181 <. For 1 < S N and I = FuTTERSOURCSS(S......
2
set S = =UE S, Let ö > U. Then there exists a constant C C(ô, T, N,N, such that for any n 2 C, the following inequalities hold with probability at least 1 - ô uniformly over all f E H. and against any adversary:
+ $ 0 (V
Rs(f) - RR) + o( (V
S ((n)
(7)
Discussion In contrast to the homogeneous situation, an additional factor linear in enters the right hand side of the bound. As discussed in Section 3.1 we believe that such a factor will be unavoidable in the heterogeneous case: 1j is a measure of the dissimilarity between the clean sources and the target distribution. Therefore, even without data corruptions, the accuracy of a learned classifier for the unknown target distribution p will be limited by how close that is to the training distributions (Bartlett) 1992 Hanneke & Kpotufe 2020). That the increase in risk is of order n can be seen from simple binary classification example: let p(a,, v) = 1 (a 2 0.5} and (1 v) = {zr 2 0.5 + 7), such that TV(p, P1) = 1). Then, the optimal classifier learned with respect to has expected error with respect to p.
In cases when 17 is small, the stated result still certifies that the empirical risk and fairness deviation on the data S are good estimates of the underlying population values. Therefore, the discussion from the homogeneous case applies here as well, meaning that the data S is "safe" to train on for the purposes of lairness-aware learning.
Proof sketch The proof consists of three steps. First, we characterize a set of values into which the empirical risks and empirical deviation measures of the clean data sources fall with probability at least 1 - 8. Then we show that because the clean datasets cluster in such a way, any individual dataset that is accepted by the FILTERSOURCES algorithm provides good empirical estimates of the true risk and the true unfairness mcasure. Finally, we show that the same holds for the union of these sets, S, which implics the incqualities in the theorem. For the risk, the last step is straightforward consequence of the second. For the fairness, which is not simply expectation average over per-sample contributions, more careful derivation is needed that crucially uses the disbalance measure well. For details of the steps, please see Appendix F
3.4 Computational complexity of FLEA
In order to apply FLEA, we must train two classifiers (one to estimate disc and one estimate disp) for every pair of sources in the dataset. Assuming that the maximum number of points in every data source (after adversarial perturbation) is n, the complexity of training all of these classifiers is therefore bounded above by F2n)), where N is the number of data sources, and F(t) is the computational complexity of running the chosen method of learning a classifier on a data set of size t. Then, all but K sources are filtered out and the data in the rest is combined, resulting in a total computational complexity of O(22 F(2n) + F(Kn)). Since N K < N, which term dominates depends on the complexity of the learning algorithm. In the case that F is subquadratic, the total complexity is dominated by the first term; if F is quadratic, by neither term, and if F is of higher complexity then the combined training dominates. Please see Appendix sections A.2
2
and A.4 for specific details and running time of our experimental sctup.
4 Experiments
FLEA's claim is that it allows learning classifiers that are fair even in the presence of perturbations in the training data. Due to its filtering approach it can be used in combination with any existing learning method. For our experiments, we run it in combination with four fairness-aware learning methods as well as one fairness-unaware one against a variety of adversarics on five established fair classification datasets. We benchmark our method against the corresponding base learning algorithms without preffitering, as well against four robust learning baselines.
9

---

Published in Transactions on Machine Learning Research (09/2022)
4.1 Experimental setup
We report experiments in two setups: for homogeneous and heterogeneous data sources.
Datasets For the homogeneous setup we use four standard benchmark datasets from the fair classification literature: COMPAS (Aingwin et al. 2016) (6171 examples), adult (48841), germancredi((100) and drugs (1885) (Dua & Graif 2017). To obtain multiple identically distributed sources, we randomly split each training set into N E {3,5, 7, 9, 11] equal-sized parts, out of which the adversary can manipulate N-1 For the heterogeneous case we use the 2018 US census data of the folktables dataset (Ding al.) 2021]. We
form 51 similarly but not identically distributed data sources by using up to 10000 examples from each of the US-states. Out of these 5, 10, 15, 20 25 can be manipulated. Details about the data preprocessing and feature extraction steps can be found in the supplemental material.
In all cases, we use gender as the exemplary protected attribute, because it is present in all feature sets. We train linear classifiers by logistic regression without regularization, using 80% of the data for training and the remaining 20% for evaluation. All experiments are repeated ten times with different train-test splits and random seeds. We measure the mean and standard deviation of the accuracy and the fairness of the learned classifiers, where compute fairness as 1 - Tss, where I's is the demographic parity violation the test set.
Pairness-Aware Learners We use FLEA in combination with four fairnoss-aware learning methods that have found wide adoption in research and practice. In all cases, we use logistic regression as the underlying classification model.
Faórness regularization (Kamishima et al., 2012) learns fair classifier by minimizing a linear combination of the classification loss and the empirical unfairness measure I's, where for numeric stability, in the latter the binary-valued classifier decisions f(z) are replaced by the real-valued confidences p(f(x) = 1/z).
Data preprocessing (Kamiran & Calders 2012) modifies the training data to remove potential biases. Specifically, it creates a new dataset by uniform resampling (with repetition) from the original dataset, such that the the fractions of positive and negative labels are the same for each protected group. On the resulting unbiased dataset trains an ordinary fairness- unaware classifier.
Score postprocessing (Hardt et al. 2016) first learns an ordinary (fairness- (airness-unaware) classifier on the available data. Afterwards, it determines which decision thresholds for each protected groups achieve (approximate) demographic parity on the training set, finally picking the fair thresholds with highest training accuracy.
Adversarial fairness (Wadsworth et al. 2018) learns by minimizing weighted difference between two terms. One is the loss of the actual classifier; the other is the loss of a classificr that trics to predict the protected attribute from the real-valued outputs of the main classifier.
For completeness, we also include plain logistic regression as a sdirness-unawar learner. The supplemental material details the learners' implementations and paramcters.
Adversaries In real-world setting, one does not know what kind of data quality issues will occur. Therefore, we test the baselines and FLEA for a range of adversaries that reflect potentially unintentional errors as well as intentional manipulations.
flip protected (PP), flip label (FL., flip both (FB): the adversary flips the value of protected attribute, of the label, or both, in all sources it can manipulate.
shuffle protected (SP): the adversary shuffies the protected attribute entry in each effected batch. overurite protected (OP), overurite label (OL): the adversary overwrites the protected attribute of each sample in the affected batch by its label, or vice versa.
resample protected (RP): the adversary samples new batches of data in the following ways: all original samples of protected group a = 0 with labels y = are replaced by data samples from other sources which also have a = but y == 0. Analogously, all samples of group with labels y = 0 are replaced by data samples from other sources with and y =1
10

---

Published in Transactions on Machine Learning Research (09/2022)
Table I: Result of FLEA and baselines for robust fairness-aware multisource learning with homogeneous and heterogencons data sources. Reported accuracy and fairness values are the minimal (worst-case) ones across all tested data manipulations in the respective settings. See main text for an explanation of the methods and details of the experimental sctup.
(a) homogeneous: adult, COMPAS, drugs and germancredit datasets with 5 sources of which 2 are unreliable.
adult
COMPAS
druge
germancredit
method
accuracy
fairness
accuracy
fairness
accuracy
fairness
accuracy
fairness
naive
66.2
77.611.2
13.1-18
78.942.3
60.042.5
72.313.1
58.014.0
78.7
robust ensemble
69.9
90.941.6
64.9-1.1
87.1
61.042.1
66,844.6
61.942.9
62.3
DRO (Wang et al., 2020)
62.840.3
15.441.3
53.7=1.4
57.1
55.2
48.5+27.0
34446.0
81.1
hTERM (Li et al., 2021a)
66.8
50.7+1.8
52.9-2.5
29.3:12.9
54.643.0
40.749.11
41.2 41.2444.0
25.2+9.4
(Konstantinuv et al., 2020)
69.34
77.6+1.2
63.1-1.8
78,942.3
60.042.5
72.34-a.1
58.04-4.0
78.7+6.3
FLEA (proposed)
70.2+0.4
97.9+1.1
65.9=1.0
94.543.0
64.341.4
92.62442
65.9433.0
93.443.9
oracle
70.3
98.2+1.0
66.2-1.1
96.211.3
64.4
93.613.3
67.313.0
94.4
(b) heterogeneous: folktables dataset with N = 51 sources of which N - K E (5, 10, 10, 25) are unreliable.
N K =
N K 10
N K 15
N K 20
N K 25
method
accuracy fairness
accuracy fairness
accuracy fairness
accuracy fairness
accuracy fairness
naive
74.4+0.2 93.440.8
73.7+0.2 87.0+a.8
72.9+0.5 80.1+0.9
71.2+0.8 73.4+0.6
58.2+6.2
73.9+1.
robust ensemble
74.910.2 90.3
74.310.2
93.8
73.5.0.3
89.1
71.910.3
81.710.7
65.811.1
60.412.2
DRO (Wang et al., 2020)
65.210.8
96.010.7
68.1
95.2.0.7
66.2.0.9
85.8=2.
66.1
77.4
58.145.6
6.748.5
ATERM (Li et al., 2021a)
76.3
73.9
74.320.6
63.421.3
71.0go.7
52.221.8
65.3g1.1
45.921.1
64.740.4
39.621.4
(Konstantinov et al., 2020)
74.3
93.440.8
73.740.2
87.0=0.8
72.9.0.5
80.1
71.2g0.8
73.4
58.246.2
73.9
FLEA (proposed)
75.440.2
99.440.2
75.440.2
99.5+0.2
75.440.2
99.5...2
75.3+0.2
99.440.2
74.041.4
94.241.
oracle
75.240.2
99.5
75.240.2
99.6
75.3
99.7
75.3
99.7
75.140.3
99.640.4
random anchor (RA0/RA1): these adversarics follow the protocol introduced in Mchrabi et al. (2021b)
A fter picking anchor points from each protected group they create poisoned datasets consisting of examples that lie close to the anchors but have opposite label to them. The difference wetn RAO and RA1 lies which combinations of label and protected attribute are encouraged or discouraged.
random (RND): the adversary randomly picks one of the strategics above for each source.
dentity (ID): the adversary makes no changes to the data.
We include ID to certify that FLEA does not unnecessarily damage the learning process in the case when the training data is actually clean. The other adversarics either weaken the correlations between the protected attribule and the larget data, thereby masking a potential existing bias in the data, or they strengthen the correlation between the protected attribute and the target label, thereby increasing the chance that the learned classifier will use the protected attribute as basis for its decisions. In both cases, the dataset statistics at training time will differ from the situation at test time, and the efficacy of potential mechanisms to ensure fairness at training time can be expected to suffer. For more detailed discussion of the ad adversaries' effects, please see the supplemental material.
Baselines To the best of our knowledge, FLEA is the only existing method to tackle fair learning under arbitrary data manipulations. To nevertheless put our results into context, we compare it to four baselines: 1) robust ensemble (similar to /mith & Martinez 2018)), which learns separate classifiers on each datasource and then combines their decisions by majority vote. 2) A distributionally robust optimization (DRO) approach proposed in Wang et al. (2020) to address noisy protected attributes. 3) Hierarchical tilted empirical risk minimization (hTERM) Li ct al. (2021a), which aims at enforcing robustness by a softmin across per-sources losses, which themselves express a form of fairness by a softmar-loss across protected groups. 4) The filtering approach of Konstantinov et al. (0200) which uses discrepancy to identify manipulated sources but does not specifically aim to preserve fairness. More details on these can be found in the supplemental Konstantinov & Lampert (2019). but these are not applicable in our setting, they require access to guaranteed clean validation data.
material. Further candidates could be Roh et al. (2020): ;
11

---

Published in Transactions on Machine Learning Research (09/2022)
4.2 Results
The results of our experiments show a very consistent picture across different datascts, base learners and adversaries. For the sake of conciseness, for FLEA we only present the results using a regularizal regularization-basee fairness-aware learner in the main manuscript. Results for other learners are qualitatively the same and can be found, together with more detailed results and ablation studics, in the supplemental material.
In Table 1 we report results for six learning methods: an ordinary learner that is fairness-aware but not protected against data manipulations (naive), the proposed FLEA,, and the four baseline methods: the robust ensemble, DRO (adapted from Waag et al. (2020]), hTERM (following Li et al. (2021a)), and discrepancy- based filtering Konstantinov et al. (2020). In addition, we report the value of a hypothetical oracle- based learner that knows which of the sources are actually clean and learns only on their data.
Each entry in the table is the minimum accuracy and fairness in the respective setting across all eleven tested adversaries. We choose this worst-case measure because it allows compact representation and reflects the fact that real-world system should be robust against all possible data errors or manipulation simultancously. Results broken down by individual adversaries are provided in the supplemental material.
Examining the results, a comparison of the naive results with the oracle confirms that the need for robust learning method real: naive fairness-aware learning not sufficient to ensure fair (or accurate) classifiers in the presence of unreliable data.
An ideal robust method should achieve results approximately as good as the oracle result, as this would indicate that the adversary was indeed not able to negatively affect the learning process beyond the unavidablee loss of some training data. The results show that FLEA comes close to this behavior, but none of the other methods does. In the homogeneous setting (Table Ta for the largest dataset, adult, FLEA reliably suppresses the effects of all tested adversaries. It learns classifiers with accuracy and fairness almost exactly those of a fair classifier trained only on the clean data sources. For the other datasets, COMPAS, drugs and germancredit FLEA increases the accuracy and fairness to levels only slightly below the oracle. In all cases, FLEA's 'ss results are as good as or better than the basclines; the robust ensemble is also able to improve fairness to some extent, but it does not reach the oracle results.
The DRO-based and hTERM approaches show highly volatile behavior. For some adversaries they improve fairness or accuracy, but for some adversarics they fail severely. Consequently, their min-aggregated values in the table are often even lower than for the naive method. Note that these results should be seen in context though: Wang et al. (2020) is designed for different and less challenging data manipulation model. Li et al. (2021a)'s 's notion of robustness and fairness differ from the ones we employ in this work.
The approach from Konstantinov et al. (2020) has almost no effect. Only for the largest dataset, adult, it yields a slight accuracy improvement. This can be explained by the fact that the method only removes sources that it can confidently identify as manipulated. The theory-derived thresholds for this are quite strict, so the method is ineffective unless a lot of data is available. The observed characteristics of the different methods hold also for the other base learners, see the supplemental material.
In the heterogeneous setting (Table lb the results show similar trends: manages reliably to filter out the malignant sources, such that the accuracy and fairness of the learned classifiers matches the one of the oracle method almost perfectly. The robust ensemble has positive effect, but less so than FLEA. For this data, DRO somewhat improves fairness, but this comes at loss of accuracy. The method from Konstantinov el al. (2020) has no noticeable effect. For N - K = 25, FLEA still performs best, although a bit worse than the hypothetical best oracle. Presumably, this is because the combined effect of distribution differences between the sources and the uncertainty due to finite sampling when estimating disc, disp and disb are too large to perfectly allow a decision which 26 sources to keep and which 25 exclude.
for N (5, 10, 15, 20), FLEA
12

---

Published in Transactions on Machine Learning Research (09/2022)
5 Conclusion
We studied the task of fairnoss-aware classification in the sctting when data from multiple sources is available, but some of them might by noisy, contain unintentional errors, even have been maliciously manipulated. Ordinary fairness-awee aware learming methods are not robust against such problems and often fail to produce fair classifiers. We proposed a filtering-bssed algorithm, FLEA, that able to identify and suppress those data sources that would negatively affect the training process, thereby restoring the property that fairness-aware learning methods actually produce fair classifiers. We showed the effectiveness of FLFA experimentally, and we also presented a theorem that provides formal guarantees of FLEA's efficacy.
Despite promising results, consider FLEA just first step on the path toward making fairness-aware learning more robust. One potential future step is to include other notions of fairness besides demographic parity. So far, FLEA can already be used as it is with classifiers that enforce other fairness criteria. However, our theoretical guarantees do not holds for these, as the disparily measure that enters our filtering slep is not tailored to them. We do not see fundamental problems in deriving filtering steps for other fairness notions that are also defined in terms of propertics of the joint distribution inputs, outputs, and protectod attribules, such as equality of opportunity or equalized odds. However, the theoretical analysis and the practical implementation could get more involved.
On the algorithmic side, FLEA as we formulated it, requires computing all pairwisc similarities between the sources. This could render it inefficient when the number of sources is very large (e.g. thousands). We expect that it will be possible to overcome this, for example by randomization of the sources, but we leave this step to future work.
6 Acknowledgements
The authors would like to thank Bernd Prach, Elias Frantar, Alexandra Peste, Mahdi Nikdan, and Peter Súkeník for their helpful feedback. This research was supported by the Scientific Service Units (SSU) of IST Austria through resources provided by Scientific Computing (SciComp). This publication was made possible by an ETH AI Center postdoctoral fellowship granted to Nikola Konstantinov. Eugenia Iofinova was supported in part by the FWF DK VGSCO, grant agreement number W1260-N35.
References
Agarwal, A., Beygelzimer, A., Dudik, M., Langford, J., and Wallach, H. A reductions approach to fair classification. In International Conference on Machine Learing (ICML), 2018.
Aingwin, J., Larson, J., Mattu, S., and Kirchner, L. Machine bias: There's 's sofe used across the country to predict future criminals and its biased against blacks., 2016. URL https: com/ com/propublica/ compas analysis
Awasthi, P., Blun, A., Haghtalab, N., and Mansour, Y. Efficient PAC learning from the crowd. In Workshop on Computational Learning Theory (COLT), 2017.
Barnett, V. and Lewis, T. Outliers in statistical data. Wiley, 1984.
Barocas, S., Hardt, M., and Narayanan, A. Fairness and Machine Learning. fairmlbook.org, 2019.
Bartlett, P. L. Learning with a slowly changing distribution. In Workshop on Computational Learning Theory (COLT), 1992.
Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Vaughan, W. A theory of learning from different domains. Machine Learning (ML), 2010.
Beutel, A., Chen, J., Zhao, Z., and Chi, E. H. Data decisions and theoretical implications when adversarially learning fair representations. In Conference on Fairness, Accounlability and Transparency (PAceT), 2017.
13

---

Published in Transactions on Machine Learning Research (09/2022)
Calders, T., Kamiran, F., and Pechenizkiy, M. Building classifiers with independency constraints. In International Conference on Dala Mining Workshops (IDCMW), 2009.
Calmon, F., Wei, D., Vinzamuri, B., Natesan Ramamurthy, K., and Varshney, K. R. Optimized pre- pre-processing for discrimination prevention. In Conference Neural Information Processing Systems (NeurIPS), 2017.
Celis, L. E.,, Keswani, V., and Vishnoi, N. Data preprocessing to mitigate bias: A maximum entropy based approach. In International Conference on Machine Learing (ICML), 2020.
Celis, L. E.,, Huang, L., Keswani, V., and Vishnoi, N. K. Fair classification with noisy protected attributes: A framework with provable guarantees. In International Conference on Machine Learing (ICML), 2021a.
Celis, L. E., Mehrotra, A., and Vishnoi, N. K. Fair classification with adversarial perturbations. In Conference Neural Information Processing Systems (NeurIPS), 2021b. 2021b.
Charikar, M., Stcinhardt, J., and Valiant, G. Learning from untrusted data. In Symposium on Theory of Compuling (STOC), 2017.
Chen, S., Li, J., and Moitra, A. Efficiently learning structured distributions from untrusted batches. In Symposium on Theory of Compuling (STOC), 2019.
Cho, J., Hwang, G., and Suh, C. A fair classifier using kernel density estimation. In Conference on Neural Information Processing Systems (NewrIPS), 2020.
Chuang, C.-Y. and Mroueh, Y. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations (ICLR), 2021.
Chzhen, E., Denis, C., Hebiri, M., Oneto, L., and Pontil, M. Fair regression with Wasserstein barycenters. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Corder, G. W. and Foreman, D. I. Nonparametric statistics: A step-by-step approach. John Wiley & Sons, 2014.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to algorithms. The MIT Press, 2009.
Crammer, K., Kearns, M., and Wortman, J. Learning from multiple sources. Journal of Machine Learning Research (JMLR), 2008.
Ding, F., Hardt, M., Miller, J., and Schmidt, L. Retiring adult: New datasets for fair machine learning. In Conference on Neural Information Processing Systems (NeurIPS), 2021.
Donini, M., Oneto, L., BeviDavid, S., Shawe-Taylor, J. S., and Pontil, M. Empirical risk minimization under fairness constraints. In Conference on Newral Information Processing Systems (NewrIPS), 2018.
Dua, D. and Graff, C. UCT machine learning repository, 2017. URL http:://archiee..tee ics uci edw.mmdummm ml
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Innovations in Theoretical Computer Science Conference (ITCS), 2012.
Erfani, S., Baktashmotlagh, M., Moshtaghi, M., Nguyen, V., Lockie, C., Bailey, J., and Ramamohanarao, K. From shared subspaces shared landmarks: A robust multi-source classification approach. In Conference Artificial Intelligence (AAAI), 2017.
Feng, J., Cai, Q-Zz,, and Zhou, Z.-H. Learning to confuse: Generating training time adversarial data with auto-encoder. In Conference on Newral Information Processing Systems (NewrIPS), 2019.
Fowl, L., Goldblum, M., Chiang, P-y.,, Geiping, J., Czaja, W., and Goldstein, T. Adversarial examples make strong poisons. In Conference on Neural Information Processing Systems (NewrIPS), 2021.
Friedman, J. H. Greedy function approximation: gradient boosting machine. Annols of Statistics, 2001.
14

---

Published in Transactions on Machine Learning Research (09/2022)
Goodfellow, I. J., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., and Bengio, Y. Generative adversarial networks. In Conference on Newral Information Processing Systems (NeurIPS), 2014.
Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. In International Conference on Learning Representations (ICLR), 2015.
Gretton, A., Borgwardt, K. M., Rasch, M. J., Schölkopf, B., and Smola, A. kernel two-sample test. Journal of Machine Learning Research (JMLR), 2012.
Halmos, P. R. Measure Theory. Springer, 2013.
Hanneke, S. and Kpotufe, S. A no-free-lunch theorem for multitask learning. arXiv preprint arXiv:2006.1578. 2020.
Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. In Conference on Neural Information Processing Systems (NewrIPS), 2016.
Jain, A. and Orlitsky, A. Optimal robust learning of discrete distributions from batches. In International Conference on Machine Learing (ICML), 2020a.
Jain; A. and Orlitsky, A. A general method for robust learning from batches. In Conference on Neural Information Processing Systems (NewrIPS), 2020b.
Kallus, N., Mao, X., and Zhou, A. Assessing algorithmic fairness with unobserved protected class using data combination. In Conference on Fairness, Accountability and Transparency (FAccT), 2020.
Kamiran, F. and Calders, T. Data preprocessing techniques for classification without discrimination. Knowledge and Information Systems (KAIS), 2012.
Kamishima, T., Akaho, S., Asoh, H., and Sakuma, J. Fairness-aware classifier with prejudice remover regularizer. In European Conference on Machine Learning and Dala Mining (ECML PKDD), 2012.
Kearns, M. and Li, M. Learning in the presence of malicions errors. SIAM Journal on Computing, 1993.
Khetan, A., Lipton, Z. C., and Anandkumar, A. Learning from noisy singly-labeled data. In International Conference on Learning Representations (ICLR), 2018.
Kifer, D., Ben-David, S., and Gchrke, J. Detecting change in data streams. In International Conference Very Large Data Bases (VLDB), 2004.
Konstantinov, N. and Lampert, C. H. Robust learning from untrusted sources. International Conference on Machine Learing (ICML), 2019.
Konstantinov, N. and Lampert, C. H. Fairness-awde aware learning from corrupted data. Journal of Machine Learning Research (JMLR), 2022.
Konstantinov, N., Frantar, E., Alistarh, D., and Lampert, C. On the sample complexity of adversarial multi-source PAC learning. In International Conference on Machine Learing (ICML., 2020.
Kullback, and Leibler, R. A. On information and sufficiency. The Annals of Mathematical Statistics, 1951.
Lahoti, P., Beutel, A., Chen, J., Lee, K., Prost, F., Thain, N., Wang, X., and Chi, E. Fairness without demographics through adversarially reweighted learning. In Conference on Neural Information Processing Systems (NewrIPS), 2020.
Lamy, A., Zhong, Z., Menon, A. K., and Verma, N. Noise-tolerant fair classification. In Conference on Newral Information Processing Systems (NeurIPS), 2019.
Li, T., Beirami, A., Sanjabi, M., and Smith, V. Tilted empirical risk minimization. In International Conference Learning Representations (ICL.), 2021a.
15

---

Published in Transactions on Machine Learning Research (09/2022)
Li, T., Hu, S., Beirami, A., and Smith, V. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learing (TCML), 2021b.
Mandal, D., Deng, S., Jana, S., Wing, J., and Hsu, D. Ensuring faimesss beyond the training data. Conference on Neural Information Processing Systems (NeurIPS), 2020.
Marcotte, P. and Savard, G. Novel approaches to the discrimination problem. Zeitschrift für Operations Research, 1992.
Mehrabi, N., Morstatter, F., Saxena, N., Lerman, K., and Galstyan, A. A survey on bias and fairness in machine learning. ACM Compuling Surveys (CSUR), 2021a.
Mehrabi, N., Naveed, M., Morstatter, F., and Galstyan, A. Exacerbating algorithmic bias through fairness attacks. In Conference on Artificial Intelligence (AAAT), 2021b.
Mehrotra, A. and Celis, L. Mitigating bias in set selection with noisy protected attributes. In Conference on Fairness, Accountability and Transparency (FAceT), 2021.
Mohri, M. and Medina, A. M. New analysis and algorithm for learning with drifting distributions. In Algorithmic Learning Theory (ALT), 2012.
Natarajan, N., Dhillon, I. S., Ravikumar, P., and Tewari, A. Learning with noisy labels. In Conference on Neural Information Processing Systems (NeurIPS), 2013.
Qiao, M. and Valiant, G. Learning discrete distributions from untrusted batches. In Innovations in Theoretical Computer Science Conference (ITCS), 2018.
Rezaei, A., Fathony, R., Memarrast, O., and Ziebart, B. Fairness for robust log loss classification. Conference on Artificial Intelligence (AAAI), 2020.
Roh, Y., Lee, K., Whang, S., and Suh, C. FR-train: A mutual information-based approach to fair and robust training, In International Conference Muchine Learing (ICML), 2020.
Roh, Y., Lee, K., Whang, S., and Suh, C. Sample selection for fair and robust training. In Conference on Neural Information Processing Systems (NeurIPS), 2021.
Russakovsky, O., Deng, J., Su, H., Krause, J., Satheesh, S., Ma, S., Huang, Z., Karpathy, A., Khosla, A., Bernstein, M., Berg, A. C., and Fei-Fei, L. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 2015.
Shalev-Shwarz, S. and Ben-David, S. Understanding machine learnóng: from theory algorithms. Cambridge University Press, 2014.
Smith, M. R. and Martinez, T. R. The robustness of majority voting compared to filtering misclassified instances in supervised classification tasks. Artificial Intelligence Review, 2018.
Student. The probable error of mean. Biometrika, 1908.
Tan, Z., Yeom, S., Fredrikson, M., and Talwalkar, A. Learning fair representations for kernel models. In Conference on Uncertainty in Artificial Intelligence (AISTATS), 2020.
Ting, K. M. and Low, B. T. Model combination in the multiple-data-bateee scenario. In European Conference on Marchine Learning (ECML), 1997.
Tsybakov, A. B. Introduction to Nonporametric Estimation. Springer series in statistics. Springer, 2009.
Vapnik, V. The nature of slatistical learning theory. Statistics for Engineering and Information Science. Springer, 2013.
Villani, C. Optimal tronsport: old and new. Springer, 2009.
16

---

Published in Transactions on Machine Learning Research (09/2022)
Wadsworth, C., Vera, F., and Piech, C. Achieving fairness through adversarial learning: application to recidivism prediction. In Conference Fairness, Accounlability and Transporency (FAceT), 2018.
Wang, H., Ustun, B., and Calmon, F. Repairing without retraining: Avoiding disparate impact with counterfactual distributions. In International Conference Machine Learing (TCMT.) 2019.
Wang, S., Guo, W., Narasimhan, H., Cotter, A., Gupta, M., and Jordan, M. Robust optimization for fairness with noisy protected groups. In Conference on Neural Information Processing Systems (NewrIPS), 2020.
Woodworth, B., Gunasekar, S., Ohannessian, M. I., and Srebro, N. Learning non-diseriminatory predictors. In Workshop on Computational Learning Theory (COLT), 2017.
Zafar, M. B., Valera, 1., Gomez Rodriguez, M., and Gummadi, K. P. Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In International World Wide Web Conference ( (WWW), 2017a.
Zalar, M. B., Valera, I., Rogriguez, M. G., and Gummadi, K. Fairness constraints: Mechanisms for fair classification. In Conference on Uncertainty in Artificial Intelligence (AISTATS), 2017b.
Zemel, R., Wu, Y., Swersky, K., Pitassi, T., and Dwork, C. Learning fair representations. In International Conference on Machine Learing (ICML), 2013.
Zhang, B. H., Lemoine, B., and Mitchell, M. Mitigating unwanted biases with adversarial learning. In Conference on AI, Ethics, and Society (AIES), 2018.
17

---

Published in Transactions on Machine Learning Research (09/2022)
Appendix
Table of Contents
A: Experimental Setup
B: Detailed Algorithm for Estimating disc and disp
C: Detailed Experimental Results
D: Discussion of the Role of disb, disc and disp and Ablation Study
E: Complete Formulation and Proof of Theorem 1
A Experimental setup
A.1 Dataset preparation
The datasets we use are publicly available and frequently used to evaluate fair classification methods.
The COMPAS dataset was introduced by ProPublica. It contains data from the US criminal justice system and was obtained by a public records request. The dataset contains personal information. To mitigate negative side effects, we delete the name, first, last and dob (date birth) entries from the dataset before processing it further. We then exclude entrics that do not fit the problem setting of predicting two year recidivism, following the steps of the original analysis [ Specifically, this means keeping only cases from Broward county, Florida, for which data has been entered within 30 days of the arrest. Traffic offenses and cases with insufficient information are also excluded. This steps leave 6171 examples out of the original 7214 cases. The categorical features and numerical features that we extract from the data are provided in Table 3a
adult, germancredit, and drugs are available the UCI data repository as well as multiple other online sources We use them unmodified form, except for binning some of the feature values; see Tables 2 and
Table 2: Dataset information
(a) adult
dataset 48842
categorical features
workclass
federal-gov, local-gov, never- worked, private, self-emp-ine, self-emp- not-ine, state-gov, without-pay, unknown
education
1st-4th, 5th-6th, 7th-Sth, 9th, 10th, 11th, 12th, Assoc-acdm, Assoc-
voc, Bachelors, Doctorate, HS-grad, Masters, Preschool, Prof-school,
Some-college
hours-per-week
< 19, 20-29 29, 30 39, 2 40 < 24, 25-34 34, 35 44, 45-54, 55 64, 2 65
age native-country
United States, other Amer-Indian-Fskinog Asian-Pac-Islander, Black, White, other
race
numerical features
protected attribute larget variable
gender
values: female (33.2%), male (66.8%)
income
I 50K (76.1%), 50A (33.9%)
hattps://githee http:hhwwww...poooaaaa/////aaaaa
Padult: https://archive.icm http:///hhh..........i.a/a/////r
gernancredit httpe//rdddtttttee//gtttt...... httpa//w.w...aa.......o..aaaaaaa oet.eeaeeeccceaeee.e.oooeaoaaaee
data.cav
drugs: httpa://ran htg.a//aaaaooo.aoo.aaaaaaaaaaaaa http://///atatteeeeeoooooooonoo. cot.:upoocooauuiioo.....
18

---

Published in Transactions on Machine Learning Research (09/2022)
Table 3: Dataset information (contimued)
(a) CDMPAS
dalaset size
6171 (7214 before fillering)
categorical features
c-charge-degrec
values: (felouy), M (misconduct)
age-cat
values: <25, 25-45, >45
nace
values:
African-Amerien Caucasian, Hispanic, Other
numerical features
priors-count
protected attribute
Female (19.0%), Male (81.0%)
largel variable
two-gear-recid
0 (54.9%). (45.1%)
(b) drugs
dataset size categorical features
1885
numerical features
Age, Gender, Education, Coundry, Ethnicity, Nscore, Escore, Oscore, Ascore, Cscore, Impulsive, SS Gender Coke
(precomputed numeric values dataset)
protected attribute target variable
female (31.0)), male (69.0%) never used (55.1%), used (44.9%)
(c) germancredit
dataset
1000
categorical features
Age
values: 24, 25 34, 35 44, 45 54, 55 64, 65
Saving accounts
little, moderate, quite rich, rich little, moderate, rich
Checking account
numerical features
Duration, Oredit amount
protected attribute
Sex
female (31.0%), male (69.0%)
target variable
Risk
bad (30%), good (70%)
(d) folktables
dataset size categorical features
255078
AGE (age; binned)
values: 14, 15-24, 25-34, 35 44, 54,54, 55 64, > 65
COW (class of worker)
values: 1,...,9
SCHL (education)
values: 1....,24
MAR (marital status)
values: married, widowed, divorced, separated, never married
OCCP (occupation code)
values: 0, ....,
POBP (place of birth)
values: USA, other
RELP (relationship in household)
values: 0, 1,...,17
WKHP (weekly working hours;
values: S 19, 20-29, 30-39, 2 40
binned)
RACIP (race code)
values: 1,....9
numerical features
protected attribute
SEX
female (52.1%). male (47.9%) 50K (61.8%), 50K (35.2%)
target variable
income
For details of the numeric codes, see asAps//tee www/peogaeeeoooooooooooo www.eeowwwwerr//sooooo/.o
Dastinmasy
19

---

Published in Transactions on Machine Learning Research (09/2022)
A.2 Training objectives
All training objectives are derived from logistic regression classifiers. For data S = ((11,)) vi)....... (nn) c
Rd x {+1} we learn prediction function g(z) w x + by solving
min (s(w, b) + A /wol2 BEER
(8)
with
[s(w,b) =
Σ (x.y)es
y log((1 + )000))) + (1 (1-3) (1-y) log(1 + ea(a))
(9)
[S|
We use the LogisticRegression routine the sklearn package for this, which runs a LBFGS optimizer for up to 500 iterations. By default, we do not use regularizer, i.c. 0. From g(x) we obtain classification decisions as f(x) sign g(x) and probability estimates as ow; w. b) p(y 1/x) Ite-way where we clip the output of to the interval [-20, 20] to avoid numeric issues.
To train with fairness regularization, we solve the optimization problem
min Ls(w, b) s b) wER" BER
(10)
with
(s(w,b)=
Σ zEgamD
Σ Sami
ox; wr
(11)
[5a=0
Sa==
where for reasons of numeric stability, we use |t|. V P+e with 10-8 To do so, we use the Siiipy.mnimizo routine with bfgs optimizer for up to 500 iterations. The necessary gradients are computed automatically using jax{ To initialize b), we use the result of training a (fairness-unwwarg logistic regression with À = 1, where the regularization is meant to ensure that the parameters do not take too extreme values. When estimating the disparity, we use the same objective, but with different datasets, S,, S2 for the two terms in (10), with the protected attributes target labels for S₁, and the inverse of the protected attributes as target labels for S2.
To train with adversarial regularization, parameterize an adversary g' :RR R- IR as g'(x') w''' + b and solve the optimization problem
max Ls(w, b) nnC nIC's sw'' WER ER
min
(12)
with
b' =
Σ (E.O)ES
alog(1 e I'(o(a)) + (1- - a) log(1 + t g'(o(o)))
(13)
To do so, we use the optax package with gradient updates by the Adam rule for up to 1000 steps. The learning rates for classifier and adversary are 0.001. The gradients are again computed using faz. We initialize (w, b) the same way as for 110.. (w',8') we simply initialize with zeros.
To perform score prspprocss,,ng, we evaluate the linear prediction function on the training set and determine the thresholds that result in fraction of r {0, 0.01,...... ... 0.99, 1} positive decision soparately for cach protected group. For each r we then compute the overall accuracy of the classifier that results from using these group-specific thresholds and select the value for that leads to the highest accuracy. We then modify the classifier to use the corresponding thresholds for each group by adjusting the classifier weights of the protected attributes.
http:/thhwwb.ccoooggg//////////a (version 0.3.14)
20

---

Published in Transactions on Machine Learning Research (09/2022)
A.3 Baselines
In this section, we provide more details about the baselines.
Robust ensemble For this baseline, we train N classifiers, one per data source, using the respective base learner. For prediction, we compute the median value the predicted probabilities and threshold it at 0.5 to obtain a binary label. Since our experiments the number of sources always odd, this is also equivalent. to classifying using the majority vote rule.
Filtering method from Konstantinov et al. (2020) The method proposed in Konstantinov et al 2020 uses a filtering step to suppress unreliable sources, like we do, but that differs from FLEA's in two main aspects: it uses only the discrepancy score for its decisions, and its decision criterion is threshold-based, not quantile-based.
For its implementation, one first computes the pairwise discrepancy scores, disc(S,, Sy), between all sources.
Then, one determines a threshold, t class (for us: the dimensionality of the feature vectors plus 1). 5 is a freely choosable confidence parameter. In the limited data regime of our experiments, its value has little influence on the threshold, so we leave it at default of 8 = 0.1. Finally, for each source, S₁, check for how many other sources, Sy, their pairwise discrepancy to S; is less than (i.c. Ejæ; [ddisc(S;, Sy) < t)). If the number of such sources is at least K - 1, the source S; is made part of the overall training set, otherwise is it discarded.
where d is the VC dimension of the hypothesis
One can check that in the setting of our experiments, only for the adult dataset one obtains values for substantially below 1. Therefore, only for this dataset, the filtering step can have a non-trivial effect.
DRO method from Wang et al. (2020) The DRO method was proposed originally for the equal opportunity equalized odds fairness measures. We adapt it to demographie parity by imposing constraints on the fraction of positive decisions instead of the true and false positive rates.
Our implementation follows the publicly available github repository which implements an approximate version of the method described in the publication. The main step is learning a classifier with fairness constraints. This is implemented by deriving a Lagrangian objective and performing simultaneous gradient descent on the classifier parameters and gradient ascent on the Lagrange multipliers. This construction has one hyperparameter, &, the permitted slack up to which the constraints have to be fulfilled. We set this adaptively, starting with small value ş = 0.01, but then doubling & until the optimization results in a non-degenerate solution (i.e. not constant classifier).
Additionally, the constraint torm of the objective is optimized in a distributionally robust (DRO) way. For this, sample weights are introduced, and the Lagrangian term is maximized also with respect to these weights, subject to 7.*bball constraints around uniform weights, and T.--simplex constraints to ensure that the weights encode a discrete probability distribution. Following the original code, we use projected gradient algorithm for the ball constraint, while the simplex constraint is approximated by implicit renormalization. The DRO also has one hyperparameter, 8, the radius of the T.*-bal. Following the derivation in the original work, we set this to twice the maximal total variation distance between the data distribution of the protected attribute in the original data and in the manipulated data, which in our case is s = 2(1 - a).
Additional hyperparameters are the learning rates for the classifier itself, for the Lagrangian multipliers, and for the sample weights. After some initial sanity checks we keep these at the values that worked best in the original publication, which 0.01 in all three cases.
hTERM method from Li et al. (2021a) TERM (tilted empirical risk méndmization) learns classifier by minimizing an exponentially weighted loss, loog (1') E( (=)())(=))) instead of the standard uniform average of losses over all samples. For negative values of t, this expression acts a softmin, thereby encouraging robustness in the sense that hard-to-classify outliers will be ignored. For positive values of t, the effect is of a softmaz, which encourages fairness in the sense that all loss values should be comparably large.
21

---

Published in Transactions on Machine Learning Research (09/2022)
For our experiments, use TERM's hicrarchical group- based extension (hTERM); outer softmin-loss encourages robustness across sources, while an inner per-source sofbmar-loss enforces fairness across protected groups,
N ni with R₂( = log 2 Σ - ()))
((1) = log
(14)
N
2E(0,1}
where
(f) = S
Σ (2.
fly
(15)
Following the original manuscript, we use = 2 and r = 2. To numerically solve the resulting optimization problem, we use the binary cross-enlropy as the loss function, l, and we call sklearn's minimize routine with LGFBS optimization.
A.4 Computing resources
All experiments were run on CPU-only compute servers. For each train/test split: of each dataset and each adversary, one experimental run across all basclinc lcarning methods takes between minutes and 3 hours on two CPU cores, depending on the number of sources, the size of the data sets, and the CPU architecture. The time needed for each in the ablation study is similar, except for the folktables data, which each took 4-6 hours. The combined time for all reported experiments with linear classifiers (5 datasets, 12 adversarics, 10 train-test splits, 5 base learners) is approximately 1800 core hours. The experiments with nonlinear classifiers required approximately 500 times longer per setting, most of which is spent on cross-validation of the hyperparameters.
For the baselines we are able to reuse many already computed parts. If implemented individually, we'd estimate that the robust ensemble would be the fastest to train, but is slower than the other methods at prediction time. hTERM would also be efficient to train, it only requires learning one classifier the combined training data. The training time for Konstantinov et al. (020 and the DRO method would be comparable to FLEA's.
A.5 Hyperparameters
We avoid hyperparameter tuning as far as possible. We do not use Ir-reeularizzation (hyperparameter X) except to create initializers, where we found the value used to hardly matter. For the fsirness-regularizer and fairness-adversary we use fixed values of 1 = }. We found these to result in generally fair classifiers for unperturbed data without causing classifiers degenerate (i.e. become constant). Hence we, did not tune these values on a caso-by-case basis. When estimating the disparity, we use n = 1 be consistent with the theory.
As learning rate for the adversarial fairness training, Itadv 0.001 was found by trial and error to ensure convergence at reasonable speed. Once we identified reliably working sctting, we did not try to tune it further.
A.6 Adversaries
In this section, we describe the adversaries and their motivation in more detail.
flip protected (FP): the adversary flips the value of protected attribute.
This is a straightforward attack on fairness. FP inverts the correlation between the protected attribute and the rest of the data After the sources have been combined, the correlation therefore weakened, which makes the training data look "less unfair'. On the one hand, this can cause fairness-enforcing mechanisms as used, e.g., in postprocessing fairness, to erroneously believe that.
22

---

Published in Transactions on Machine Learning Research (09/2022)
little compensation for dataset unfairness is required. Consequently, the resulting classifier is actually unfair when applied to future unmanipulated data. On the other hand, it is possible that the training process actually learns to ignore the protected attribute during training, because it is uncorrelated with the target labels. This could make the classifier more fair, c.g. when used with lairness-unaware training.
Our detailed experimental results (Fig. 2 10 show that both of these effect do, in fact, occur. FP typically increases unfairness when regularization-basse or postprocessing based base learners are used, but has the opposite effect for the Bainesssumawan base learner.
slip label (FL): the adversary llips the value of the label.
This is a straightforward attack on accuracy. Following an analog reasoning as above, FL reduces the correlation between the target label and all other data, which makes it harder for the learner to identify a strong classifier.
Indeed, the experiments shows that the FL adversary often succeeds in reducing the accuracy, while the fairness is relatively unaffected. The adverse effect is small for the large datasets (adult, COMPAS) and larger for the small ones (drugs, germancredit), presumably because having more data increases the robustness of the learners against mislabeled data.
flip both (FB): the adversary flips the value of the protected attribute and the label.
This attack influences fairness and accuracy at the same time. It preserves the correlation between the protected attribute and the labels, but reduces the correlation between these two and all the other features. Consequently, the learned classifier might rely heavily on the protected altribute to predict the label, which would make maximally unfair, but potentially also less accurate.
Our experiments show that this is, indeed, often the observed effect, though the exact amount. depends strongly on the dataset and the base learner.
shuffll protected (SP): the adversary shuffles the protected attribute entries of each batch it modifies, ie. each example gets assigned the protected attribute of another example that has been chosen at. random (without replacement).
This adversary is similar to FP in that is reduces the overall correlation between the protected attribute and the other data. Its effect is weaker, since it does not explicitly introduce anti-correlation in the manipulated sources. However, its manipulations or manual inspection, since it does not change the marginal statistics of the data, i.e. even after the manipulation, the statistical distribution of each feature dimension, including the protected attribute, is the same as for clean sources.
less likely to be detected by automatic
In experimental results, SP indeed performs similarly to FP for the fairness-aware base learners, and its effect are somewhat weaker for the fairness-unaware base learner.
overurite protected (OP): the adversary overwrites the protected attribute of each sample in the affected batch by its label.
This manipulation creates a strong artificial correlation between the protected attribute and the target label. In fact, the maximally unfair classifier that predicts the label directly from the protected attribute will have perfect accuracy on the manipulated data, and still much higher accuracy than what would be correct on the overall training data. Consequently, the learned classifier might make strong use of the protected attribute, which leads to unfair and potentially incorrect decisions on clean data.
Our experiments show that OP indeed often leads to large increases in unfairness. However, there are also cases where the unfairness is actually reduced, but then typically this is accompanied by loss of accuracy.
overurite label (OL): the adversary overwrites the label of each sample in the affected batch by its protected attribute.
23

---

Published in Transactions on Machine Learning Research (09/2022)
Like the OP adversary, this manipulation leads to perfect correlation between the target labels and the protected attributes. However, it achieves this without changing the marginal distribution of the protected attribute, instead influencing the statistics of the labels. Depending on the specific situation, it might be casier or harder to detect from automatic or manual inspection. OL is also more likely to negatively affect the accuracy, since the classifier will try to predict incorrect labels.
The experiments show that OL indeed almost always reduces the accuracy, while at the same time often inercasing unfairness.
resample protected (RP): the adversary samples new batches data in the following ways: all original samples of protected group a = 0 with labels y == 1 are replaced by data samples from other sources with labels y are
which also have a 0, but y O. Analogously, all samples of group replaced by data samples from other sources with 1 and y 1.
Like OL and OP, RP results in a perfect correlation between protected attributes and labels, thereby facilitating unfairness and reducing accuracy. It does in more subtle and harder-to-detect way, however, as it achieves the effect using original data samples.
Indood, in our experimental results RP influences fairness and accuracy in similar ways as the other two methods.
random anchor (RA0/RAI)) these adversaries follow the protocol introduced in Mehrabi et al 2002Tb). RAO first picks a random anchor example Ttarget of group target source. It then creates group, G+, of poisoned data by constructed new examples within a feasible set that also have a = 1 and are close to Ttarget> but that have label = 1. The number of samples in 9+ matches the mumber of samples in the target source with a = 1. Subsequently, the adversary repeats the above procodure for group a = 0, but with the opposite label values, resulting in a second group of poisoned samples G_. Both poisoned sets are then merged to yield manipulated source that is meant to influence the decision boundary near the anchor points in a maximally unfair way. The adversary RA1 performs the same construction as RA0, but with the roles of 0 and 1 exchanged.
with label y = 0 from the
Given that our data sources mostly have categorical features, it is not possible to create realistie- looking new samples simply by small random perturbations. Instead, we define as feasible set the set of all samples that occur in any of the original training sources. As newly 'constructed" samples we then take those examples with smallest Euclidean distance to the anchors.
random (RND): the adversary randomly picks one of the strategies above (except ID) for each source.
This adversary reflects the observation that different sources might be manipulated in different ways. One reason for this could be that in a real-world system, multiple adversaries exists who manipulate individual data sources without coordinating their actions. Alternatively, there might be just one adversary who manipulates all sources, but chooses to manipulate them different ways, e.g. to avoid easy detection.
The experimental results show that this stratogy docs, indeed, work to some extent, with RND often having an effect where some the other methods do not, but the effect is weaker.
identity (ID): the adversary makes no changes to the data.
The ID adversary serves as a useful check that FLEA does not damage the learning process in the case that all data is actually clean. It also reflects the fact that even though the adversary has the power to manipulate the data docs not have to. Idcally, the learning method will notice this and achieve even better results in presence of the ID adversary than for the oracle.
In the experimental results, this is effect is only rarely visible for any method, though.
Note that even though we introducod the adversarics above as intentional manipulations, many of them could also oceur accidentally when data from different sources collected, e.g. as problems during data entering or numeric encoding.
24

---

Published in Transactions on Machine Learning Research (09/2022)
B Detailed algorithm for estimating disc and disp
In this section we provide pscudocode for estimating the pairwise discrepancy and disparity between two data sources. In both cases we approximate a classifier f that maximizes continuous relaxation of the relevant metric, and then estimate the actual quantity of interest from it. The disc maximizing classifier is trained by flipping the labels of one of the two sources, combining the sources into a single datasct, and then training a classifier to predict the (new) label. The maximizng classifier is trained as a classifier that comes as close as possible predicting the protected attribute on one data source, and a the other, while balancing the loss from each subgroup.
EMPIRICAL DISCREPANCY ESTIMATION
Input: datasets S2
1: f t miny (
Σ ChOSSENTROPY(fEE).0) +
1
Σ
CROSENTROP(((()))
[551
18al
(x.y)E82
2: disc + [S FESi
Σ ((((()) 0.5) # [5o1 Σ 1(((() 2 0.5) = y}
Output: Empiriaal discrepancy estimate disc E R+
EMPIRICAL DISPARITY ESTIMATION (Demographic Parity)
Input: datasets S1, S2
1: f f miny
Σ
CROSSENTROPY(((3s.00) + B
Σ CROSENNTROPY(()))..
xESu
ZEST-1
Σ CROSSENTROPY(((E)..)
Σ
CROSENNROPP(((33..O)
SaET
#ESA
rESS
2: disp
H(((2) 2 2.5) + イッ}
Σ [1((2) 2 (15))1)
xEST
xEST
Σ {1)(2) 2 0.5) + v) +
Σ 1(((x) 0.5) + ッ
S
#E
SES
Output:
Empirical discrepancy estimate disp R+
C Detailed experimental results
In addition to the experiments with ingularization-basee base learner that were reported in the main manuscript, we also run experiments with postprocossing-basee fairness, preprocessing-basee fairness, ad- versarial fairness, and fairness-unaware learning. The results are depicted Fig. 2 for the homogeneous setting and Fig. 0 10 for the heterogeneous setting. Also included are results for two of the baselines, robust ensemble and Konstantinov et al. (2020). The DRO (Wang al. 2020 and hTERM (Li al. 2021a require specific learning procedures and therefore cannot be combined with arbitrary base learners. We report them together with results for the regulariiaation-baseel base learners.
The format of the figures is as follows: for each datasets and method, we report the accuracy and fairness results for different adversarics. Each panel contains 12 bars. The left-most one in each diagram shows the result of the hypothetical oracle setting, where the learning algorithm trains only on the clean data sources, i.e. the ones which the adversary cannot modify. The remaining bars correspond to the outcome when different. adversaries have perturbed the data. An ideal robust method should achieve results approximately as good the oracle result, this would indicate that the adversary was indeed not able to negatively affect the learning process.
From the results, one can see that FLEA works almost perfectly in the homogeneous setting with a lot of data (adult) and still quite well when the amount data is limited (COMPAS, drugs and germancreditdata) In the latter cascs, for some adversarics FLEA does not always exactly match the oracle results, but still performs better than the basclines. In the heterogencous case, FLEA works reliably in all settings, except for the fairness measure when N K 25, as had already discussed in the main manuscript. The results also
25

---

Published in Transactions on Machine Learning Research (09/2022)
show that different base learners achieve different reeuracy/fairees trade-offs, but FLEA is effective with each of them. In a few cases, FLFA'ss 's results appear to even improve over the ones of the oracle. However, we do not believe this to be a systematic effect, but rather a case in which the adversarial perturbation were largely benign, and FLEA chooses a subset of sources that by random chance yields a better classifier than when using exactly the clean sources.
26

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 2: adult dataset, N 5, K
(a)
regulariization-baee fairness
ordinary fair training
ensemble
DRD (Wing al, 2020)
2021] [Konstantion al, 2020]
(proposed)
U.6
0.6
0.6
2.6
0.6
1.0
0.5
0.5
0.5
0.5
0.0
0.0
126
RAM
RHD
(b) preprocessing basedd fairness
ondinary traiiig
(proposed)
0.6
0.6
0.6
1.0
3.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0706
19
F1
5P
ANO
RA0
RAX
RF
RND
OP
80
RAO
RA0
RA1
(c) postprocessing based fairness
(notntiin ICML
FLEA
9.6
1.0
3.0
1.0
1.0
farress
0.5
F7
11
00
80
RND
RA1
11
RP
IND
100
FL
FB
OF
RP
AND
RAO
NA11
OF
01
AP
RAD
RA1
(d) adversarial fairness
ordinary fair trairing
robust ensemble
nKttntiin al, ICML 2020]
FLEA (praposed)
0.8
0.8
0.8
1.9
faimess
1
RID
RA3
181
100
RAO
00dc
RP
RND
8&0
8A1
(e)
fairness-unas unaware
falmes-unaware training
robust ensemble
[Konstantioo al, ICML 2020]
FLEA (proposed)
0.5
0.8
0.8
0.5
faimers
0
RVD
AN0
A41
2
M1
OF
RP
RND
960
RA1
27

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 3: COMPAS dataset, N N K 2
(a) regularizationn-aseee fairness
ordinary fair training
ensemble
DRD [Wiing al, 2020)
2021]
[Konstantino al, 2020]
(proposed)
9.8
U.S
0.6
0.6
0.6
1.0
0.5
0.5
0.5
0.5
0.5
0.0
0.0
10
125
RND
(b) preprocessing based fairness
ondinary trairing
(proposed)
0.6
0.6
0.6
0.6
1.
3.0
3.0
1.0
0.5
0.5
0.5
0.5
0706
50
RNO
RA0
RAX
RND
R2
RA0
(c) postprocessing based fairness
ICML
FLEA
9.6
1.0
3.0
3.0
1.0
farres
0.5
F7
70
RND
RA1
IND
100
RP
IND
RAO
NA11
30db
NP
RAD
RA1
(d) adversarial fairness
ordinary fair trairing
robust ensemble
nstantiioo al, ICML 2020]
FLEA (praposed)
0.8
0.8
0.8
1.9
RID
RA3
100
RAO
00dc
RND
860
8A1
(c)
fairness unaware
faimes-unaware training
robust ensemblee
[oonstatiiov al, ICML 2020]
FLEA (proposed)
0.6
0.8
0.8
0.5
faimets
0
RND
ANO
A41
87
960
M1
RP
RID
960
RA1
28

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 4: drugs dataset, N 5, K
(a) regularization--aaee fairness
ordinany fair training
ensemble
DRD [Wiing al, 2020)
2021]
[Konstantinn al, 2020)
(proposed)
9.8
U.S
0.6
0.6
2.6
1.0
0.5
0.5
0.5
0.5
0.0
0.0
10
121
RND
(b) preprocessing based fairness
ondinary training
(proposed)
0.6
0.6
0.6
0.6
1.0
3.0
3.0
1.0
0.5
0.5
0.5
0.5
0.0
0706
5
ANO
RA0
RAX
RND
80
RA0
(c) postprocessing based fairness
ICML
FLEA
0.6
1.0
3.0
3.0
1.0
farves
0.5
F7
12
RND
RA1
IND
100
RP
IND
RAO
NA11
30db
RAD
RA1
(d) adversarial fairness
ordinary fair trairing
robust ensemble
nstantiino al, ICML 2020]
FLEA (praposed)
0.8
0.8
0.8
1.9
RID
RA3
100
00dc
RND
860
8A1
(c)
fairness unaware
faimes-unaware training
robust ensemblee
[oonttntino al, ICML 2020]
FLEA (proposed)
0.6
0.8
0.8
0.5
faimess
A00
A41
2
87
R60
M1
F
RP
RID
960
AA1
29

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 5: germancredit dataset, N 5, K
(a) regularization--asee fairness
ordinany fair training
ensemble
DRD [Wing al, 2020)
2021]
[Konstantinn al, 2020)
(proposed)
U.S
0.6
0.6
2.6
0.6
1.0
0.5
0.5
0.5
0.5
0.0
10
125
RND
NAL
(b) preprocessing based fairness
ondinary traiiing
(proposed)
0.6
0.6
0.6
3.0
3.0
1.0
0.5
0.5
0.5
0.5
0006
19
50
RNO
RA0
RAX
RND
80
MA1
RA0
RA1
(c) postprocessing based fairness
nntantiiio ICML
FLEA
90
1.0
3.0
3.0
0.5
F7
11
00
RND
RA1
IND
100
FB
0F
IND
RA0
1A11
NP
RAD
RA1
(d) adversarial fairness
ordinary fair trairing
robust ensemble
nnttntitn al, ICML 2020]
FLEA (praposed)
0.8
0.8
1.9
faimess
1
RID
RA3
100
RAO
00dc
RND
860
8A1
(e)
fairness unaware
faimes-unaware training
robust ensemble
[Konstantioo al, ICML 2020]
FLEA (proposed)
0.5
0.8
0.8
0.5
faimers
RND
M1
M1
RP
RND
960
RA1
30

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 6: folktables dataset, regularization-basse fairness
(a) N 51, N
ordinary fair training
DRD [Wiing al, 2020)
2021]
[Konstantioo al, 2020]
FLEA (proposed)
0.6
0.6
0.6
2.6
0.6
1.9
1.0
1.0
0.5
0.5
0.5
0.5
0.5
0.0
0.0
126
RN
N N
K
10
ordinary training
[Wang
[Konstantinov
(proposed)
0.6
0.6
0.6
0.6
0.6
1.0
1.0
1.0
1.0
1.0
1.0
0.5
0.5
0.5
0.5
0.5
850
(c) N N - K = 15
ensemble
DRD
HITERM 2021)
[Konstantinov
FLEA (proposed)
RCCURSSO
0.6
1.0
1.0
1.0
1.0
1.0
firmess
100
1N0
(d) = 51, K
20
ordinary fair training
robust ensemble
DRO [Wang al. NeurtPS 2020) IITERM at al, 2021]
[Konstantinae et al, ICNL 2020]
FLEA (proposed)
0.8
0.8
1.0
Wiimess
22223
omie
51,
ordinary fair training
robust ensemble
DRD [Wang et al, NourtPS 2000) INTERM [Li at al, ICLA 2021]
[Konsiantinov et al, ICML 20201
FLEA (proposed)
0.5
0.6
0.8
fnimess
5.5
0.0
omcce
31

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 7: folktables dataset, preprocessing based fairness
(a) N 5 N K
ondinary traringg
[Konstantinov ICML 2020]
FL FA (proposed)
0.8
0.5
0.6
0.6
0..5
0.5
0.5
0.5
0.5
0.6
96
00
RND
RA1
OF
106
FL
80
RA0
RA0
RA1
(b) N 51,
K 10
ondinary trairing
(proposed)
0.6
0.6
0.6
0.6
1.0
3.0
1.0
1.0
0.5
0.5
0.5
0.5
0706
19
F1
5P
AND
RA0
RAX
IND
0rode
OF
80
RAO
0r0de
RAO
(c) N = 51,
K
15
nnttntiin ICML
FLEA
0.6
1.0
3.0
1.0
1.0
farres
0.5
F7
11
OF
00
80
RND
RA1
11
CF
RP
IND
100
SDds
OF
RP
AND
RA0
NA11
30ds
OF
01
NP
RAD
RA1
(d)
51,
K
20
ordinary fair traiiing
robust ensemble
nnttntiin al, ICML 2020]
FLEA (praposed)
0.8
0.8
0.8
1.9
Wiimess
1
O0
RID
RA3
WAD
100
RA0
00dc
RP
RND
8&0
8A1
51,
ordinary fair training
robust ensemble
[Konstantinov al, ICML 2020]
FLEA (proposed)
faimets Koun
0.5
0.8
0.8
0.5
RVD
8P
M1
F
RP
RND
960
RA1
32

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 8: folktables dataset, postprocessing based fairness
(a) N N N
ondinary traringg
[Konstantinov ICML 2020]
FA (proposed)
0.8
0.5
0.6
0.6
01.5
Samen
0.5
0.5
0.5
0.5
0.6
96
00
RND
RA1
OF
106
7L
80
RA0
RA0
RA1
(b) N 51,
K 10
ondinary trairing
(proposed)
0.6
0.6
0.6
1.0
3.0
1.0
1.0
0.5
0.5
0.5
0.5
19
5P
AND
RA0
RAX
RND
0rode
OF
80
RAO
0r0de
RAO
RA1
(c) N = 51,
K
15
nnttntiin ICML
FLEA
9.6
1.0
3.0
1.0
1.0
firres
0.5
F7
11
OF
RND
RA1
11
CF
RP
IND
100
0F
RP
AND
RAO
NA11
50ds
01
NP
RAD
RA1
(d)
51,
K
20
ordinary fair traiiing
robust ensemble
(notntinn al, ICML 2020]
FLEA (praposed)
0.8
0.8
0.8
1.9
Wimess
RID
RA3
0
WAD
181
1M0
00dc
RP
RND
8&0
8A1
51,
ordinary fair training
robust ensemble
[Konstantinov al, ICML 2020]
FLEA (proposed)
0.5
0.8
0.8
0.5
faimets
RVD
ANC
2
M1
M1
RP
RND
960
9A1
33

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 9: folktables dataset, adversarial fairness
(a) N 51, N K
ondinary traring
robust
[Konstantinov ICML, 2020]
FL FA (proposed)
0.8
0.5
0.6
0.6
0..5
fames
0.5
0.5
0.5
0.5
0.6
96
00
RND
RA1
OF
106
FL
80
RA0
RA0
RA1
(b) N 51,
K 10
ondinary trairing
(proposed)
0.6
0.6
0.6
0.6
1.0
3.0
1.0
1.0
0.5
0.5
0.5
0.5
0.0
0706
F1
5P
AND
RA0
RAX
IND
0rode
OF
80
RAO
RAO
(c) N = 51,
K
15
nsttntinn ICML
FLEA
0.6
1.0
3.0
1.0
1.0
farres
0.6
F7
11
OF
00
80
RND
RA1
11
OF
RP
IND
100
SDds
OF
RP
AND
RA0
1A11
50ds
OF
01
NP
RAD
RA1
(d)
51,
K
20
ordinary fair trairing
robust ensemble
nnttntiin al, ICML 2020]
FLEA (praposed)
0.8
0.8
0.8
1.9
Wnimess
1
RID
RA3
WAD
181
100
RAO
00dc
RP
RND
8&0
8A1
51,
ordinary fair training
robust ensemble
[Konstantinov al, ICML 2020]
FLEA (proposed)
0.5
0.8
0.8
0.5
faimess
RN
ANC
M1
5
RP
RND
960
RA1
34

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 10: folktables dataset, fairness-tnaware unaware
(a) N 51, N K
Faress-unaaaee training
[Konstantinov ICML 2020]
(proposed)
0.5
0.6
0.6
0..5
0.5
0.5
0.5
0.5
0.0
00
RND
RA1
OF
FL
80
RA0
F1
RA0
RA1
(b) N 51,
K 10
training
(proposed)
0.6
0.6
0.6
1.0
3.0
1.0
1.0
0.5
0.5
0.5
0.5
0706
5P
AND
RAO
RAX
RF
IND
0rode
OF
80
RAO
or0de
RP
RAO
(c) N = 51,
K
15
nnttntiin ICML
FLEA
0.6
1.0
3.0
1.0
1.0
0.6
OF
RND
RA1
OF
RP
IND
100
RP
AND
RAO
NA11
50ds
OF
01
NP
RAD
RA1
(d)
51,
K
20
faless-unawree training
robust ensemble
nKtantiinn al, ICML 2020]
FLEA (praposed)
0.8
0.8
1.9
faimess
RID
DA0
RA3
1M0
RAO
00ds
RP
RND
8&0
8A1
51,
faimes-unaware training
robust ensemble
[Konstantinov al, ICML 2020]
FLEA (proposed)
0.5
0.8
0.8
0.5
faimess
AN0
8
M1
P
RP
RID
960
RA1
35

---

Published in Transactions on Machine Learning Research (09/2022)
Table 4: Results FLEA and baselines for robust fairness- aware multisource learning using preprocessing fairness and a non-linear (gradient boosted decision trees) classifer. See Table for an explanation of setting and entries.
(a) adult, COMPAS, drugs and germancredit datasets with 5 sources of which are unreliahle.
adult
COMPAS
druga
germancredit
method
accuracy
fairness
accuracy
fairness
accuracy
fairness
accuracy
fairness
naive
66.2
86.9
5..6
83.3
60.0
77.8
5..9
76.243.8
robust ensemble
74.4
71.8+2.3
56.342.5
41.245.7
54.9
36.5=5.2
58.8
48.044..1
(Konstantinov et al., 2020)
77.5+u.4
90.9+1.7
56.2+3.
81 34.3
52.7+1.6
79.4+2.2
53.34a.0
79.0+4.1
FLEA (proposed)
4
12.1
62.340.9
87.845.4
62.8+1.6
80.623.3
64.526.6
84.443.7
oracle
78.520.4
98.3
64.8
93.045.9
64.1
88. 88.124.6
69.043.8
92.824.7
D Additional Results
While our experimental evaluation in this work focussed on the setting of linear classification, FLEA also applicable in combination with nonlinear classifiers. However, this leads to increased computational cost, and also the size of the training sources would have to be larger to effectively estimate the disc and disp measures. A compromise is to perform FLEA's filtering step with respect to linear classifiers but afterwards train a non-linear classifier on the resulting combined training set. We observed this setup to work well in practice, even though the theoretical guarantees do not hold.
As exemplary setting, we perform experiments in a subset of the situations using gradient boosted decision trees Friedinan (2001) from the xgboost package [ as nonlinear classifiers. We use 5-fold crossvalidation to select hyperparameters n_ eestmaators E {100, 200, 300, 400, 500} and hax_depth {3, 5, 7,9}. To encourage fairness of the resulting classifiers we use the preprocessing approach, as that requires no changes to the actual classifier training routines. As baselines, we compare to the robust ensemble and the filtering
approach of (Konstantino et al.] (2020). The other baselines of Section 4.2 are not applicable, as they require modifications of the training process itself.
Table reports the results in tabular form. Figures and Figure 12 visualize the results for each adversary.
Overall, one can the same trend as in the linear setting: naively merging the data sources leads to strong decreases in accuracy and fairness. The different robust methods overcome this to varying degrees, with FLEA always achieving the best results, i.e. closest to the hypothetical oracle.
A comparison of Table to Table shows that the use of a nonlinear instead of linear classifier generally does not lead to more accurate nor more fair classifiers in the tested setting. Presumably, this because in the chosen categorical representation, the bottleneck for prediction quality is not a lack of expressibility of the hypothesis class, but rather the datasets' intrinsic noise. This view is supported by the fact that accuracy and fairness are not much increased even for the oracle approach, which is not affected by the data manipulations.
E Discussion of the role of disb, disc and disp and ablation study
FLEA relies on the combination of three dissimilarity measures: disc, disp and disb. In these section we discuss the importance of each of them and report on an ablation study to verify their practical significance.
Of the three measures, disc is indispensable to ensure classifier accuracy, as it is the only mcasure that depends on the label values. At the same time, disc is blind to changes in the protected attributes whenever those are not part of the feature set.
Even in the case when the protected attribute is among the features, the disc measure may not detect changes in the data that may harm fairness. For example, if one of the protected groups is much more rare than the other, changing even small number of data points (e.g. the points from that group) can cause large change in the conditional distributions of the data given the value of the protected attribute. At the same time, the diserepancy will remain largely unaffected, since only a few points have been changed in total.
36

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 11: Nonlinear (gradient- boosted decision trees) classifier, preprocessing- based fairness
(a) adult (N 5,
ondinary fair traeing
robust ensemble
[Korstantine et al, ICML 2020]
FLBFA (praposed)
0.5
0.8
0.8
0.5
0.5
famess
0.0
0.0
0.0
0.0
RXD
RA1
RA0
RND
RA0
COMPAS (N
N
K
ordinary fair trwring
robust ensemble
[Konstantinov ICML 2020]
FLEX (proposed)
0.8
0.6
0.6
0.6
0.6
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
R10
RA1
MAL
RMO
RA0
RAL
(c) drugs (N
5.
K
ordinary training
(prapesed)
0.8
0.6
0.6
0.6
0.6
1.0
3.0
1.0
1.0
0.5
0.5
0.5
0.5
10
RN0
000
RA3
IND
orade
R6O
100
grdde
(d) germancredit(N
5, N
K
[Konstantinov ICML
FLEA
0.6
1.0
3.0
3.0
1.0
0.5
2005
70
RND
860
R63
2ods
12
FL
80
INN
R60
NA1
50ds
01
RP
R60
R61
Therefore, filtering only based on disc insufficient sources with a different conditional distribution may get in through the filtering step, potentially causing unfair classifiers (on clean data) to appear fair the (corrupted) dataset.
FLEA avoids such issues by additionally adopting the disp measure, which can reliably detect changes in the conditional distributions of the data given the value of the protected attribute, thereby ensuring reliable fairness estimates based on the sources that are returned by the filtering procedure. However, disb is not sensitive to manipulations in the size the protected attributes, for example, an adversary who seloctively drops examples of one protected group. However, the disb measure would detect such manipulation. Thereby, ensures that the disparity of the union of multiple sources is close to their average individual
37

---

Published in Transactions on Machine Learning Research (09/2022)
Figure 12: Nonlinear (gradient- boosted decision trees) classifier, fairness- unaware learning
(a) adult (N 5, K
Faimes-unamare training
robust ensemble
[Korstantinev et al, ICML 2020]
FLEAA (praposed)
0.5
0.8
0.8
0.5
0.5
famess
0.0
0.0
0.0
0.0
R7D
RND
R24
RAL
COMPAS (N
N
K
farmes-unaware training
robust ensemble
[Konstantinov ICML 2020]
FLEX (proposed)
0.8
0.6
0.6
0.6
0.6
1.0
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
RAL
RAO
PAL
(c) drugs (N
5.
K
training
(propesed)
0.8
accore
0.6
0.6
0.6
0.6
1.0
3.0
3.0
1.0
0.5
0.5
0.5
0.5
000
RA3
IND
orade
100
ardde
RA0
(d) germancredit(N 5, N
K
[Konstantinov ICML
FLEA
0.6
1.0
3.0
3.0
1.0
0.5
50ds
70
RND
860
R03
cods
12
FL
80
IND
860
NA1
50dc
01
RP
R60
RA1
disparity. This is important because fairness-aware learner works on top of FILTEROURRCES by merging the data from the sources returned by the filtering algorithm. This aspect becomes apparent only in the proof of Theorem 1 see Section
E.1 Ablation study
To understand the respective contributions of disb, disc, and disp on real-world data, we performed an ablation study that runs variants of FLFAA in which any subsets of the three measures used to compute
38

---

Published in Transactions on Machine Learning Research (09/2022)
Table 5: Performance of FLEA with different combination of disb, disc, and disp activated or deactived (crossed-out). Reported results are in the same format Table 1 minimal accuracy (A) and fairness (F) against any of the tested adversaries
regularization-hasee fairness
disb
disb
disb
Aist
disb
Tist
Wist
Tist
disc
disc
disc
disc
disp
disp
disp
diss
disp
adult 70.3
70.3
63.7
70.3
53.3
70.3
64.3
57 57.4516.55
N = 5, N - K = 2 F: 28.
98. 98.2+1.1
91.2g18.4
18.2
64.0
89. 89.225.6
91.8+18.6
68. 68.84
compas
A: 66.2
66.1
61.948.9
16.2+1.1
43.8
66.0g1.1
61.7
56.0+13.0
N = 5, N K = 2
F: 95.442.6
93.1
94.3+2.6
95.3+2.6
86.247.5
90.2g1.9
94.34.24
68.7+26.2
drugs
A: 64.4
64.3
52.1+11.
64.3+1.4
55.4+9.2
64.3
58, 18.14
52.9+11.1
N 5, N K 2
93.0+4.5
88.9
72.6424.7
92.5+4.9
69.6+12.3
86.446.2
82.9+18.1
70.5
germancredit
A: 66.542.
66.0+2.7
60.2
66.842.8
59.7.
66.222.5
55.949.8
56.6+11.5
N 5, N = 2
93.8
92.643.8
86.2+13.1
93.943.9
87.1
92.5.44.1
81.0
75.4
folktables
A: 2..
75.510.2
74.6
75.410.2
74.4
75.4
74.6
74.210.5
== 51, N K = 5
F: 99.5
99.010.5
99.3
99.510.2
93.0+2.6
99.1
99.410.2
92.7144.0
folktables
75. 20.2
75.4
73.9
75.420.2
73.7
75.322.2
73.9
73.010.99
N = 51, N K = 10
F: 99.5.0.3
98.1
99.1
99.540.3
88.343.0
98. 98.220.5
99. 09.1
86.713.7
folktables A: 75.4
75.440.3
72.7
75.420.2
72.3
75.320.3
72.720.8
68.8
N = 51, N- K 15
F: 99.720.2
97.0+0.6
98.9
99.620.3
82.4+2.4
97.1
98.940.5
78.945.4
folktables
A: 75.3
75.3+0.2
69.9
75.3
70.5
75.3
68.4
64.8+10.0
51, N 20
99.5
95.641.1
98 98.440.6
99.5+0.2
79.1
93.941.5
98.320.7
74.943.3
folktables
A: 74.0+1.4
75.0+0.3
53.9
74.1+1.3
41.6414.1
59.3411.6 15.1
56.5413.3
N = 51, N = 25
F: 94.2+1.6
89.941.6
95.2+4.7
94.541.8
79.446.7
89.3+1.7
96.9+1.7
72.6+2.7
the D-scores. The variant with all measures active is identical to FLEA. The variant with all measures inactive randomly chooses subsets to train on.
The results are presented in Table 5a One can see that for all datasets, not using disc (column 3) for the filtering step has the most noticeable effect. This makes sense, because several of the adversaries make large changes to the labels and features, and disc is well suited to idcntify these.
Not using disp (column 2) has usually less of an effect, but in some situations it does lead to a noticeable drop in fairness, see e.g. COMPAS, and drugs, as well as folktables with N - K E {5, 10, 15, 20). This is also consistent with our expectations, as the measure is specifically able to detect even subtle manipulation that would negatively affect fairness. However, for folktables with N K = 25, where the amount of manipulated data is very close half, not using disp would actually be beneficial for the system. We attribute this to the fact that as a difference of ratios, disp is harder to estimate from small sample sets than the other two measures. A noisy estimate, however, can lead to clean sources to be suppressed, and manipulated ones to be selected. This explanation is also supported by the fact that for small datasets the variability of results is bigger when disp is included than when it is not.
The effect of not using disb (column 4) is small on real data. It never exceeds the standard deviation of the estimates. This, again, expected, as the other two measures are typically able to ensure accuracy and fairness, whereas the role of disb is mainly to handle corner cases that are unlikely to occur in real data.
Dropping two measures from the filtering step only makes sense, if the remaining measure is disc (column 6). Even then, a decrcase in accuracy and/or fairness is quite common, or at least an increase in variability.
Another interesting ablation study would be to determine the success rale of the FLEA's filtering step, i.e. how what fraction of the malignant sources it successfully suppresses. This, however, we cannot estimate, because we lack ground truth information which sources are malignant and which are not. From the experimental setup, only the information is available which sources have been manipulated and in what way. However, whether manipulation is benign malignant depends not only on the ad adversary's strategy, but also on
39

---

Published in Transactions on Machine Learning Research (09/2022)
the actual data and the later learning strategy. The proxy measure of determining what fraction of all manipulated sources were detected would not be very meaningful, as adversaries can easily create manipulated data sources that are indistinguishable from clean ones, e.g. just shufiling the data point or not making any changes at all, as realized in our experiments by the ID adversary.
F Complete formulation and proof of Theorem
In this section we present the full proof of Theorem We begin by reminding the reader our notation and formal assumption from in [..]] Next in Section F 2 we state a few standard concentration results that are used in our main proof. In Section F.3 we define the population counterparts of the empirical discrepancy, disparity and disbalance measures, as understanding how well these mcasures are estimated from finite data is crucial for the proof of our results.
Finally, we present the full proof of Theorem in Section from Section F.2 in Section F.5
F.4 and the proof of the concentration lemmas
F.1 Assumptions and formal adversary model
For convenience of the reader, we repeal the formal notation and assumptions stated in 3.3.1 Initially, there are datasets Si..... Ss,, with the i-th set of samples being drawn i.id. from a distribution pı(x, y, a). We assume that all these distributions are clean, in the sense that they are close to the true target distribution p. Formally, we assume that each of the following conditions hold:
TV v, v,,)), P(F, S n, and max ( (TV(p:(z, -lt.://la==x,..,/.)>> yla = =z))} S
(16)
=EA
where TV g) = SuDDEB(XXUXA) (p(B) aB)) with B(X) denoting the Borel o-algebra on a topological space X.
Once the clean datasets $,,..., Sy sampled, an adversary operates them. This results in new datasets, S1,..., Sv, which the learning algorithm receives input. The adversary is arbitrary (deterministic randomized) function F = (X' y x A)" - I (X' x y x A)", with the only restriction that for a fixed subset of indices, G C (1, (I....,,N)) N}, the data remains unchanged. That is, S, S, for all i G, and S; is arbitrary for i & G.
Note that the learner only observes the datasets S; and outputs a hypothesis based on them. Therefore, in the proof we will only work with the datasets S, and not with St, using that S, = 3; whenever i E G, so that S; is f..dd. from pt. For simplicity, we refer to a dataset S; or a source E [N] as clean if G.
We assume without loss of generality that T PP (A 0) E (0, 2 For technical reasons, we also assume that 187 r === -(X((...))=p(A
F.2 Concentration tools and notation
We first present the two lemmas which demonstrate uniform convergence of the empirical risk and the empirical fairness deviation measure respectively, for any hypothesis set. H with finite VC dimeusion. The first. is just the classic VC generalization bound, given in Chapter 28.1 of "SShlle-Shwartee & Bavid 2014 1 The proof of the second lemma closcly follows the proofs of similar results from Woodworth et al. (2017) Agarwal et al. (2018); Konstantinov & Lampert (2022) and is presented in Section F.5 for completeness.
Lemma 1 (Uniform Convergence for Binary Loss). Let d be the VC-dimension of H. Then for any dataset S of size n sampled i.i.d. from a distribution p. for all E (0,1),
8d (:T) + 2 log (1)
P sup (h) Rp(h)) > 21 hEH
5
Lemma (Uniform Convergence for demographie parity). Let p be distribution on X x A Let d = VC(H) 2 and let min (( a) for some constant E (0,0.).. Then for any
40

---

Published in Transactions on Machine Learning Research (09/2022)
8log( +)
dataset of size n 2 max
sampled i.i.d. from p, for all E (0,1/2):
[ls(h) [p(h|] 2 161 dlog 2en + log
(4
Iss
sup hEH
8
5ó d
(17)
For the dataset Si, denote by
a= E
Lia 03 = 15-
(18)
(BMMajES,
Denote 7; P(x, (A 0). Then for clean data source have that c; Bin(n, m.). Therefore, by the Hooffding bound, for any 5 > 0:
2 2(v log (3)
2
log (3)
P c. nTi 2 m
exp
6.
(19)
2n
Because, by assumption, r P(X.Y.A)ppi (A= 0) mm.nae P(X.Y.A)=p(A=a)) and TV 17 for any clean dataset S, it holds that
-) 2
In addition,
1 1 = 1- P. (1)
= n
Recall also that r - T- 187 0 by assumption. Denote by:
8d + log (3)
16 dlog log (
log (2)
(6) = max
21
(20)
n(T 11)
2n
dlogg (2en) + log (2)
=16//
(21)
n - 11)
The lemmas above, as well as the observation that min(r,, 1 - -r 2 imply that:
for any clean source i, readily
sup Rs. (h) - Ry, (h)l 2 A()) 26
(22)
NCH
Ps sup
I's (h) Ip. (h)l 2 A
2
(23)
hEW
and
Ps (ecll-non 106g-nii 2 ni( < 8,
(24)
for any clean i.
F.3 Discrepancy, disparity and disbalance between distributions
In our proof we will consider the population counterparts of the betweon-dataset distances that we defined in the main body of the text. In particular, the discrepancy distance between two distributions p and g is
disc(p. g) sup (h) (h)
(25)
hCH
41

---

Published in Transactions on Machine Learning Research (09/2022)
Similarly, the disparity is
disp(p, q) sup [p)h) (h)h)
(26)
NEH
where as an unfairness measure p we will use:
(h)) = P(X,Y.aa> (l(X) = 1/A 0) -p (k(X) = 1/A = 1).
Finally, the disbalance is simply
disb(p. () = (A P 0)-
(27)
Next we study these distances, between a distribution p: of a clean source and the true target distribution p. Recall our assumptions about the bounded TV distances from Section F.1 disb(pi, p) S TV(p,, p) 77. Note also that:
Clearly, we have that
disc(pr. p) sup Rp, (h) Rp(()] sup (xx Y) (b(x) + Y) S n kEH
MEH
because any (measurable) classifier h X + y can be associated with a (Borel) set S₁ = {(x, a) E (X' x y x A) h(x) + y). Finally, we bound the disparity in terms of 17. Note that:
disp(p:.P) = sup P (X)Y.,A)m (X(X) = 1/4 0) - P(X (h(X) = 1|A NEW
-P -x, (h(X) = 1|4 0) + PX (h(X) = 1/A 1)
( (((Y,,)))> (h(X) 1/A 0) P(X (h(X) 1/A 0)
sup kEH
(X,Y,A)~>p (h(X) 1|A 1) P(X (h(X) 1|A 1)
sup kcH
P(X.Y.A)<p (4(X) 1|A 0) P(X.AA (h(X) 1 = 0)
+ sup |Pxx,.XA)>>p (N(X) 1/A = 1) P.X.Y.AMp (M(X) 1/A = 1)
kEH
< 2m..
F.4 Proof
Theorem 1. Assume that H has finite VC-dimension d > 1. Let be arbitrary target data distribution and without loss of generalily T =(a 0) E (0, 0.5). Let SN be N dalasels, each consisting of n. samples, out of which K. > 2 are sampled i.i.d. from a data distribution that is n-close the distribution in the sense of Section F.1 Assume that 187 < T. For 1/2 < 3 NN and I FILTERSOURCES(SI..
SN: set S =iez S.. Tet 8 >> O. Then there crists constont C = C(8, d. N, 1), such that for any 2 C, the following inequalities hold with probability at least 1 uniformly over all f E H. and against any adversary:
K
(5(0))1(()1 00) (VA)
1
(Rs(F) - -R, (r) +Ō (V
(28)
Proof. First, characterize set of values into which the empirical risks and empirical deviation measures of the clean data sources falls with probability at least 1 1-8. Then we show that because the clean datascts cluster in such a way, any individual dataset that is accepted by the FILTERSOURCES algorithm provides good empirical estimates of the true risk and the unfairness measure. Finally, we show that the same holds for the union of these sets, S, which implics the incqualitics (28). For the risk, the last stop is a straightforward consequence of the second. For the fairness, however, careful derivation needed that crucially uses the disbalance measure well.
42

---

Published in Transactions on Machine Learning Research (09/2022)
Step 1 Let G G [N] be the set of indexes i, such that S, was not modified by the adversary. By definition, G K. Now consider the following events that, we will show, describe the likely values of the studied quantities on the clean datasets.
In particular, for all E G, let E, be the event that:
8
sup (Rs - Ry, (h) $
(29)
6N
NEW
let E. be the event that
5
sup IT' (h) Tp. (h)] A NEW
(30)
6N
let Ehin be the event that
lG nTi S nA
(31)
6.V
and finally, let ggount be the event. that
< G < n.
(32)
Denote by (E, ye (EF)) and (Ehi)), (Ecount) the respective complements of these events. Then, by equations
22 and 23 (24) we have:
P((E))S 8
5 P((E))) P((E)())) S 6N
5 VIEG.
6N'
6N¹
To bound the probability of the complement of Erownt, note that for any EEG P(,YY.)) (A= < (A=x))=(4=1)+======
and that 1 - + 17 because of the assumption that 1) < Similarly,
T. P(X.Y.A)sp.AA (A= 0) P(X.Y.A))pl (A -
=
Now, for any E G, whenever n 2 Ci(5, T,(0,, = log( 4N) log(T=tr))
log AN
log 4 we have that
2 max
log I
log
IP ((goount) 9 = (1 - TT) + T.
)) cxp
1 In
I exp
- log
1 1-
Ts
T.
8
8
8
4N
4N
2N
Therefore, setting E = (NeG R A (NeG
eT (Niece
chin A Mieneyountt then by the union bound the 6.
probability of ((8) < K uN + K ON
+ K &
+ K
< 3
EN
NN
Hence the probability of the event & that all of
30
and
32 hold is at least 6.
Step Now we show that under the event E, the inequalities in 28 are fulfilled. Indeed, assume that E holds. Fix any adversary A and any h H.
For any pair of clean sources i,j [N] the triangle law and the derivations in Section F.3 give:
disc (isc(S,, S,, sup Rss (h) (0s,(h)
< sup RRs, (h) Ry, (h) + sup RRp (h) (h)l + sup (R, - R2 (h)(h)) + sup Rp, (h) Rs, (h) Kcy
NEW
McH
43

---

Published in Transactions on Machine Learning Research (09/2022)
8 6N
S 2n + 2A
Similarly,
disp(S;, = sup hCH
I'', (h) - I's (h)) & 4n + 24
6.N
and
disb(S;,
C;
9 S 2m 24
n
n
6N
Therefore, for any pair of clean sources i,j E [N]:
disc(S;; S;) + disp(S; Sj) + disb(S;; Sy) 8n + 64
(33)
6N
It follows that, under E, we have that qi S 8n + 6Λ 6N for any clean [AV]. Since the fraction of clean sources is K N 2 3, follows that also S 8n + 6 (xx). where q is the 8-th quantile the g.ss.
Denote by I FLLTERSOURCE(SS ...... Sw: 3) the result of the filtering algorithm. Now for any I, have that qi S q S 8n 6A ). In addition, by the definition of qi, disc(S,, Sj) I disc(S,, Sq) + dSsp(S;; S,) + (S, S,) S qi for at least ||| = 3N > 2 values of j E [N]. Since K N 2: this means that
disc [S;, Sj) S q: S 8n + 6Λ
6N for at least 1 value j E G. Therefore, we have:
sup [Rs; (h) (h)l < sup NEH
RRs (h) Rs, (h) + sup hEH
Rs, (h) - Rys (h) + sup Rp,(h) (p)b
(34)
NCH
hcH
8
s 8n 6A
+ A
17
(35)
6NV
6.V
8
9n 7A
(36)
6N
because & holds. Similarly,
8
sup Iss (h) - r2(h)] & 10n + 74 NEH
(37)
6.N
and
5
1c: - nT| S 9pm - 7nd
(38)
6N
Step 3 Finally, we study the risk and disparity measures based all filtered data S UierSt.
Denote by Rs(h) the empirical risk across the entire trusted dataset 1:
Rs(h): [
Σ Rs. (s.
(39)
ie!
Then the triangle law gives:
(Rs(h) Rp)
1
Σ
Rs. (h) R2(h))
<
1
Σ ie!
Rs. (h) Rp(h)) = 9n 7A
8
6N
ie!
Since
3A
8
= 112
2
d dlo (2an) + log
(14N (T n)n
((/ -0((r-)) 7)m
Ö
(40)
6N
the bound the risk follows.
44

---

Published in Transactions on Machine Learning Research (09/2022)
Denote by (h) the empirical estimate of demographic parity across the entire trusted dataset I:
[h(h) Ejer E.= 1( (10 = 11 (1,00==)) =0} EJEr Ei= 1(h(x, = (1) =13
(41)
EJEr Ei=1 1( =0}
EjE 11a, =
For convenience, denote v; (h)) = Σ { 1,a 0} and wj wy(h) = 11h(z! 1, L,a, }}. so that:
Ts(h) = Ej Uj Ejer Cj En
Eyer
Our goal to bound the difference
[ss M Eier Ts, and the difference
[1] Eier Ts. Tp. and use these
two bounds to bound [[s rpl-- The sccond bound follows directly from
37
r
1
Σ
Ts.
< 10m + 7A
ô
(42)
6N
SEI
To compute the first bound, we first build on (38 to note
C
nTT
9ryn + 7nA
6
GN
91 + 7A
6N
4
11T
11T
nT
T (91) + 7A
(6N
1T cal
9mm + 7n
(
6
6N
9n + 7A
6N
5
G
C2
Ci
T (91) + 74
6N
and therefore,
9n + 7A
(
6N
C
<
9n + 7A ( 6
(43)
7 (91 + 7A
6N
11T
T
(97) + 7A
6N
5
9m + 7A (6N)
9n + 7A
6
1
GNV
(44)
(9n) + 7A
-- (9t) + 7A
5
6N
6N
Applying the same logic to n G::
9n + 7A ( à
6N
C
9n + 7A
6N
4
(45)
1 (917 - 7A
ONN
n1 17
1 1-7- (9n + 7A (x)))
9n 7A ( (
9n + 7A ( 6
nT
<
(46)
1
(9n + 7A 6NN)
n 4
1 1 5
(9n + 7A (6N)
Now consider,
Wj
Ts
Cj
[n C5)
JES
JEI
jEI
9n + 7A
1
9n + 7A (
<
1+
66N
(6N)
7
5 (9n) 7A
(x)
7
nn c)
T (97 7A
JEI
JEI
6.N
ΣjEr" Uj
9m + 7A ( (6x))
Σ ΣjEr Wjj
9n 77 ( (6)
1
Ejere
(91 + 7A (+f
Ejer (n - c)
1- (91) + 7A
8
6.
EjEr" Vs
On + 7A 6
(6N)
99+7A 6T
(9n + 7A (oN)
Ejere Cj
7
45

---

Published in Transactions on Machine Learning Research (09/2022)
EjE1 Wj
9n + 7A
6N
91+7A( BV
T (91)
7A
Cne)(n-c))
1
G.V
(91)7 c.x))
1+ 99+74(
90+7 A
E EjEr") V
(9 65
ΣjEr wj
1 197
Σ EjEr Cj)
99+7A( 4
Σ EjEr(n - cq)
90+74 EX
1
(91+7
(91++7 (
91y 91 BV
7 8V
Ejer") 1/j ΣjEreh Cj
Ejeryy Wy Ejer(n -cg)
+ Ejer'h V/3 EjEr C3
(9n+7A DT
+ EjEr Wy
(9t+7A 03
99+7A( +
EjEr(n (n-c)) cy)
9 n.3
1
1 1-r (9n+7A 05
79. (.
where we have used that 1+t 1 + simplifying the fractions further, obtain
2
and
1-t 148
21
Now, using Vi S Cj and wy S n - Cg and
I-t
I-t
142
Ejer 1/
Ejerus
2 29 + 7A (ex)
2 (97 + 7A 6,
Ejere Gj Ejer(n (n- cgg)
2 + 7A 6NN)
2 (917 + 7A 5
2 (9 + 7
Is + T 2 (91 + 7A 6N
6N
1-T T
Using analogue steps, we can show that
2 (99 + 74 ())
2 (9n + 7 (ev)
Σ ss. -Ts+
1 1 2 (9n + 7A
5
6.
Combining these two bounds:
1
2 (9n + 7 (( 2 (91) + 7A
2 (91) + 7A ( 6N
rs l's
(47)
T
6N
5
T 2 (9m + 7A
6N
Now, combining 47 with
42
and using the triangle incquality before,
5
2 (9n + 7
6N
2 (91 + 7A (6.
1r I'l < 10n + 7A
(48)
6N
T (97
1 1 7 2 (9n + 7A
ON
6N
dlog 2gn +log 11
Recalling from 20 that A = 161
we obtain that
[r, - Ts + δ
1
(49)
vn
F.5 Proof of Lemma 2
Let S {0, Vs. -- For E {0, 1}. denote:
33)) Σí 1(h(1:) = 1, o}
(50)
Σ 1(a =
and
(/()) TP(1(X 1|4
(51)
46

---

Published in Transactions on Machine Learning Research (09/2022)
that (h) (h) (h) and r2(h) (0)))~7)0 (/)))
First we use technique of Woodworth et al. (2017 ; Agarwal et al. 2018 for proving concentration results
about conditional probability estimates to bound the probability of a large deviation of l's(h) from (h),, for a fixed hypothesis h E H. Our result is similar to the one in Woodworth et al. (2017), but for demographic parity, instead of equal odds.
Lemma 3. Let h E H be a fixed hypothesis and E P(X' x A x y) be a fixed distribution. Let T min (0.1) ((x,Y,A))p(A = a) E (0,0.). Then for any dataset S, drawn i..dd from p, of size n and for any 10,1) and any L 0:
PTT (-88) 8
((][s(h)- [2(h]] > 21) S 6exp
(52)
Proof. Denote by S. = {i E [n] : a, = a} the set indexes of the points in S for which the protected group is a. Let Ca == |Sal and Pa -(xx,r.))=p(A = a), so that T min, Pa- For both {0, 1}, we have:
(1 - T > t)
Σ
P (h3 - Val >
S.
1
P
Ca <
Pan +
Σ
P(h %al t|S.) P(S.)
2
Saita >o Pan
Pan
S cxp
Σ
2 exp (-2f P(Sa)
8
Sacea > Pan
Pan
exp
+ -2exp (-PPan)
8
< 3exp
8
The triangle law gives:
1( - (1 } 1/1
78
70
0
+
1/g -0 + +/1 3/1-
Combining the previous two results:
P((( - -78) - (7p - - > 2t)
< (113
3/ + 13 - 2t)
P ((/1g
70 > 1) v (1 1/ > t))
$ (113
7/
> t) P (175 7 >t)
< 6exp
8
Finally, we prove Lemma 2 by extending the previous result to hold uniformly over the whole hypothosis space, for any hypothesis space H with a finite VC-dimension d == VC(H). The extension is essentially identical to Konstantinoy & Lampert (002) and is included here for completeness.
Lemma (Uniform convergence for demographic parity). Let = VC(H) 2 1 and let T = minae P(x,.,A))<pA = a) for some consland т (0,0.5). Then for any dataset S of size n 2
Blog(:) {) 2
max
sampled ii.dd from p. for all E (0, 1/2):
Ps sup [s(h) -Tp()) 2 16 2 log
2en
+ log 24
5
(53)
hEW
47

---

Published in Transactions on Machine Learning Research (09/2022)
Proof. To extend Lemma 3 to hold uniformly over H. first prove version of the classic symmetrization lemma (Vapnik) 2013) for I and then proceed via standard growth function argument.
1) Consider a ghost sample S" = {(/,, a, Di) also sampled i..d. from p. For any E H, let (s) be the empirical estimate of (h) based on S¹.
We show the following symmetrization inequality for the measure:
Ps
21)))2 sup [Tshh) - [b) 21) s s,s WeH
sup [T's - I's(h)) 2 1/2)
(54)
hcH
for any constant 2 8v
log((12
Indeed, let h* be the hypothesis achieving the supremum on the left-hand side 9 Then:
(IT) (b0)) 2 (2222))10 (IT(((sss)))))))))))))))) (h') (2())) 1/2)) 1(Tss (h²) [s(h')] 2 1/2).
Taking expectation with respect to S":
- - t)
- s
t/2) s
- -11 21/1)//// t/2).
Now using Lemma
t'
1
Psr (ITs (1) 1/2) 2 - 6 exp
2 1
128
2
2
where the second inequality follows from the condition
8
2 (12)
Therefore,
((TTs(h)) - r2(h)) t) s Ps (ITs [s(h') 1/2).
Taking expectation with respect
Ps((L's(h)) 12(h t) s s.s (L''s(h'' I's (h")) 2 f/2)
2TP s.s (sup ITs (h) Ts (h) > 1/2).
heW
2) Next use the symmetrization inequality
54 to bound the large deviation of [h)h) uniformly over H.
Specifically, given points 2i...., E X, denote
Ha, ....... on
h E H}.
Then define the growth function of H as:
GH(n)= = sup |
(55)
21 Rn
We will use that well-known Sauer's lemma (Vapnik 2013). which states that whenever n 2 d, Gx - (
Notice that given the two datasots S,S', the values of Ts and Tsr depend only on the values of on S and S' respectively. Therefore, for any 2 8// 2l0((12)
na
sup sss (Ts)) t
P3 sup ITs ke7
[2(h) 21) S 2Ps
(56)
hel
9If the supremum attained, the argument can be repeated for each element of sequence classifiers approaching the supremum
48

---

Published in Transactions on Machine Learning Research (09/2022)
(Is:(h)-Tss(h)) [s(()) 2 ;
s 22Gx(2n)Pss.'
(57)
(II3(()) - [2(h) -12h))))-((0))) =
(Bp(0)))(000)2 2))
s 2GH((2))Psss''
(58)
(2ph)- 4)
< 42
(59)
t
244HH(22) exp
(60)
516
2en
Tm
s 24
exp
(61)
516
Here the second-to-last inequality is due to the same bound on the difference between Ns and Tp that was used in the previous lemmaa, and the last one follows from Sauer's s lemma. Now if we use the threshold
t = 161 log ( 2eNN +log (24)
(12g(12)
8V
we get:
dloo
2en log <6.
Ps
sup (h) - r2(h)] 2 161 NCH
d
(62)
49


Reviews:
[{"review_id": "og1YkBhsxy", "reviewer": "Reviewer_68xw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nStrengths:\n* The paper is generally well-written, and related work is discussed in a decent manner.\n\n* The authors derive theoretical guarantees for robust federated learning in heterogenous settings. \n\nWeaknesses:\n* As authors have correctly mentioned, learning from multiple unreliable sources has been studied in the literature before. Here I point out to key recent baselines that are missing from the mix, where they study the same problem in the context of noisy annotators. Without comparisons with these works, it is not easy to compare the empirical performance of the proposed FilterSource method with those existing in the literature.\n\nKhetan, A., Lipton, Z.C. and Anandkumar, A., 2018. Learning from noisy singly-labeled data. ICLR.\n\nLi, T., Beirami, A., Sanjabi, M. and Smith, V., 2021. Tilted empirical risk minimization. ICLR.\n\n* The efficacy of the proposed filtering approach in a federated setting is unclear. While this is implicit, given lack of details on the algorithm, my understanding is that the authors are assuming **full device participation** at each round which is unrealistic for real-world federated setups. \n\n* It is unclear where and how the computations required for FilterSource are performed. In particular, these computations scale quadratically with the number of devices, something that is prohibitive when we have millions of devices. Without the details (which are mostly missing), I am not able to assess the applicability of the proposed algorithm in real world settings.\n\n* The experimental setup mostly encompasses linear models. It is not clear whether the proposed idea extends beyond that.\n\n* A strong baseline for the proposed algorithm would be hierarchical TERM (Li et al 2021), where negative tilting is done at device level and positive tilting at sensitive attribute level. This baseline is missing.\n\n* A discussion around key baselines on fair federated learning is missing:\n\nMohri, M., Sivek, G. and Suresh, A.T., 2019, May. Agnostic federated learning. In International Conference on Machine Learning (pp. 4615-4625). ICML.\n\nLi, T., Sanjabi, M., Beirami, A. and Smith, V., 2020. Fair resource allocation in federated learning. ICLR.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors propose FLEA, a filtering approach for fair federated learning in presence of unreliable training data from malicious devices. The authors do a decent job putting their work in context, provide an algorithm, provide theoretical guarantees followed by experiments. From a conceptual point of view, the **federated learning from multiple malicious sources problem** and **fair federated learning problem** are treated in a disjoint manner in this paper and the contribution mostly lies on the former front. As detailed in the summary of strengths and weaknesses, unfortunately the treatment of the paper in its current form is lacking in several major ways, which requires a major revision.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "* Is there a converse bound for Thm 1 that can establish the linear dependence on $\\eta$ is optimal? Can you please elaborate?\n\n* At the end of Section 3, you want to connect with personalized FL literature as they overcome the dependence on $\\eta$ via personalization.\n\n* In practice, one would imagine that the filtering and federated model learning need to be performed jointly. Can the authors comment on that?\n\n* Please compare with robust aggregation methods such as multi krum.\n\n* Please compare FilterSource with (Khetan et al 2018) and (Li et al 2021) as they also perform filtering of unreliable sources.\n\n* Please chime in on partial device participation and how the filtering can be done in a federated manner itself.\n\n* Please include the implementation details of the filtering algorithm, especially as it intersects with federated learning. Currently, it is not clear what each device needs to do at each round.\n\n* Please empirically report settings where number of devices scale, and showcase the scaling behavior of the proposed algorithm with number of devices.\n\n* Please compare your end-to-end algorithm with hierarchical TERM (Li et al 2021), where negative tilting is done at device level and positive tilting at sensitive attribute level.", "broader_impact_concerns": "Broader impact is sufficiently addressed.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "KdtqyeI9v7", "reviewer": "Reviewer_77G8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nOverall, it is a solid paper with theoretical analyses and promising empirical performance. The strengths and weakness are listed as follows:\n\nStrengths:\n\n1. The paper proposes a sound solution to improve fair multisource learning from unreliable training data, which is an important application scenario. The idea of the proposed filtering algorithm is well motivated.\n\n2. The related works are well summarized and the contributions are clearly demonstrated.\n\n3. Theoretical analyses on the accuracy and fairness achieved by the proposed algorithm are well established by the generalization bounds under both homogeneous and heterogeneous data distribution settings.\n\n4. Comprehensive experimental results are presented to demonstrate the effectiveness of FLEA compared with multiple baseline methods on multiple datasets. The empirical performance is promising.\n\nWeakness:\n\n1. The implementation details of the proposed filtering algorithm are not clear. For instance, in section 3.2, the computation of disc and disp measures is not demonstrated sufficiently. \n\n2. The generalization bounds imply that the generalization errors of accuracy and fairness vanish with the rate $1/\\sqrt{n}$. However, there is a lack of discussion on how the filtering algorithm improves these generalization bounds compared with other algorithms. For instance, is it possible that an algorithm without filtering can also achieve vanishing generalization error with infinite samples? \nMoreover, the theorems do not quantify how well the filtering algorithm identifies the unreliable data sources.\n\n3. Although the paper presents a significant amount of experimental results, all of them are based on simple linear models. It is unclear whether the observations and conclusions can generalize to more complicated models.\n\n5. There is no discussion on computation complexities and the running time of the filtering process. \n\n6. The paper claims to defend against adversarial attacks, but all the data attacks are very simple random attacks that are not really adversarial. It is unclear how the proposed filtering method performs under stronger adversarial attacks. \n\n7. In the experiments in the appendix, the proposed FLEA sometimes even outperforms the oracle performance where unreliable data sources are excluded beforehand. Clarifications of this will be helpful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a filtering-based algorithm to identify the unreliable data sources that have a negative impact on fairness or accuracy in a multisource learning setting. The major contribution is to establish that as long as the unreliable data sources constitute less than half of all sources, it is still able to identify and suppress their negative impact by utilizing three dissimilarity measures between the data sources (disparity, discrepancy, and disbalance). ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. The paper should make the implementation of discrepancy and disparity estimates detailed and clear.\n\n2. The paper should discuss how well the filtering algorithm identifies unreliable data sources (theoretically and empirically) and how it improves the generalization bounds.\n\n2. The paper should discuss the computation complexities and the running time of the filtering process. \n\n4. The paper should include some experiments on more complex models. \n\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "R5glLrwB9i", "reviewer": "Reviewer_RTB6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the paper lies in the detailed decomposition of the D-score -- discrepancy, disparity, and disbalance -- for the purpose of enforcing robust fair learning, and also the exposition of the approach and experimental results. Here, \"fair\" is in the sense of demographic parity. In terms of technical details, I think the presentation is overall clear and I don't see obvious technical invalidity.\n\nThe weakness of the paper comes from a worry about the usage of disbalance in the D-score. If I understand it correctly, in the literature, disbalance (or representation imbalance) is often referred to as a direct measure of (potential) violation of demographic parity in terms of the disparity in base rates across groups (not sources). Here, disbalance seems to mean the source-level base rates difference. I am not sure how the disparity measurement across sources can help mitigate demographic parity, which is on group level (each data source contains multiple groups). If we only consider fairness violation on prediction, then disp() term serves the purpose. But if we were to consider fairness violation on data itself, I am not sure how disb() term can help.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers a filter-based approach towards robust learning with multiple data sources. The setup is motivated by the situations where i.i.d. assumption is not satisfied across data sources. The paper propose to consider dissimilarity (D-score) which consist of three parts, namely, disparity, discrepancy, and disbalance, to capture the existence of \"unclean\" data sources. An intuitive procedure (Algorithm 1), as well as large sample performance guarantees, is also provided.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "For the usage of disbalance, i.e., disb() term, it would be very helpful if authors can provide some clarifications to avoid misunderstandings. For theoretical analysis (Section 3.3), I think readers can benefit more from the implication of the provided theorem(s) after presenting the technical results for homogeneous and heterogeneous settings.", "broader_impact_concerns": "I do not see any concern in terms of ethical implications of the paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "pGwJZJOGnX", "reviewer": "Reviewer_mx1h", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**::\nThe proposed approach is generic enough to cover a wide range of multisource learning scenarios (from both data-quality and adversarial perspectives). In particular, it considers the problem of multisource learning in the presence of an adversary that can arbitrarily manipulate a fixed subset of the sources, which is unknown to the learning algorithm. The authors elaborate on how existing SOTA fairness-aware and multisource learning approaches only partially address the problem. The proposed solution achieves better performance compared to existing approaches. The experiments are quite exhaustive, covering a wide range of scenarios, and demonstrating the generic nature of the solution. \n\n**Weakness**::\nThe paper did not discuss what \"enough data\" means in high data corruption settings. Also, some design choices are not well substantiated. For example, why D-Scores are computed as a sum. What about using the minimum of the three metrics? Finally, the performance of the filtering especially false-negative rates could also give more credit to the proposed solution ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work considers the problem of fair learning in a context where the training data is composed of multiple sources, some of which are not representative of the true data distribution. A filtering approach (FLEA) is proposed to remove data instances that could negatively affect fairness and accuracy. \n\nOverall, the proposed approach relies on three metrics (discrepancy, disparity, and disbalance) to ensure that the learned classifier is respectively accurate, fair, and remains fair in presence of data corruptions. More precisely, the pairwise disparity, discrepancy and disbalance between all pairs of data sources are computed and aggregated into a score used to filter out undesirable sources. Moreover, the authors show that FLEA can guarantee the learning of a fair classifier under a 50% data corruption rate. Several experiments are performed and the results show that the proposed approach can significantly improve the performance of fairness-aware learning approaches in the presence of unreliable data. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Elaborate more on the requirements for dataset size in high corruption setting\n- Explain more why the three metrics are aggregated. Why not other alternatives like using the minimum of the three metrics or solving the underlying multiobjective optimization problem?\n-  Report false negative rates of the filtering approach", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies an important problem where one tries to learn a fair classifier with multiple training datasets, some of which are adversarially corrupted. The theoretical contribution is solid though the novelty might be limited. (It's a relatively straightforward extension of robust multi-source learning.). Empirical evaluation is quite extensive and shows fairly promising results.  

The reviewers unanimously agreed to accept this paper as it is.  One of the reviewers gave a harsh review, but it was based on their own misunderstanding that the paper was considering federated learning scenarios.  The authors clarified this point during the discussion phase, and the reviewer appropriately updated their review.  There were some constructive (and critical) comments that the reviewers suggested, and the authors successfully addressed them, e.g., they clarified how the newly proposed metrics are estimated by adding pseudocodes in the appendix, and they added a clear discussion on computational complexity.  The revision reads much better.

No certification applicable.

In sum, I recommend to accept the paper as it is.  Let me know if you have any questions. 
Decision: Accept (poster)