Scalable and Stable Surrogates for Flexible Classifiers with Fairness Constraints
Authors: Harry Bendekgey
Erik B. Sudderth
Venue: NeurIPS 2021 Poster (2021)
Keywords: Fairness
Classification
Constrained Optimization

Abstract: We investigate how fairness relaxations scale to flexible classifiers like deep neural networks for images and text. We analyze an easy-to-use and robust way of imposing fairness constraints when training, and through this framework prove that some prior fairness surrogates exhibit degeneracies for non-convex models.  We resolve these problems via three new surrogates: an adaptive data re-weighting, and two smooth upper-bounds that are provably more robust than some previous methods. Our surrogates perform comparably to the state-of-the-art on low-dimensional fairness benchmarks, while achieving superior accuracy and stability for more complex computer vision and natural language processing tasks. 



Scalable and Stable Surrogates for Flexible Classifiers with Fairness Constraints
Harry Bendekgey" hbendekg@uci.. edu
Erik B. Sudderth" sudderth@uci. edu
Abstract
We investigate how fairness relaxations scale to flexible classifiers like deep neural networks for images and text. We analyze an easy-to-use and robust way impos- ing faimess constraints when training, and through this framework prove that some prior fairness surrogates exhibit degeneracies for non-convex models. We resolve these problems via three surrogates: adaptive data re-weighting, and smooth upper-bounds that are provably more robust than some previous methods. Our surrogates perform comparably the state-of-the-art on low-dimensional fairness benchmarks, while achieving superior accuracy and stability for more complex computer vision and natural language processing tasks.
1 Introduction
growing body of research has explored the ethical and societal implications of increasingly automated decision-making. One critical concern is whether particular machine learning algorithms perform differently on average for members of marginalized groups In addition to being an ethical question, this is a legal one: Attributes such an employer whose decision- makiing process disproportionately hurts one group can be litigated for committing adverse disparate impact. One quantitative notion of fairness is called demographic parity, which states that a decision maker should accept (or classify as positive) a roughly equal proportion of each group [8]. An employer who hires many male applicants, but few female applicants, violates demographic parity by disproportionately allocating resources to one sensitive group.
and gender are prottl-p categories, and
Machine learning is also increasingly used by law enforcement, where ethical questions become civil rights questions. Facial recognition and risk assessment algorithms have been shown to have disparities in accuracy between black and white defendants [2, 7]. which may lead to the arrest of an innocent person [29]. The equalized odds [27] fairness criterion requires a decision maker to have the same false negative rates, well as the same false positive rates, for each sensitive group. Equality of opportunity requires only one of those two equalities to hold, whichever is considered more ethically important (e.g., in law enforcement, Other notions of fairness include predictive parity [16], which matches classifier precision across groups, the minimization of mutual information [34] between predictions and sensitive attributes. Except in degenerate cases, some pairs of criteria cannot be achieved simultaneously [3], meaning a domain expert must make moral decision about which fairness constraint they aim to satisfy.
may ensure that innocent individuals have similar treatment).
We formalize the problem of fair classification as learning the highest-accuracy model that satisfies a constraint on some fairness criterion (either demographic parity equality of opportunity). This constrained optimization problem is mathematically difficult to solve, which has lead to the creation of a variety of fair classification algorithms, many involving relaxations of constraints like those analyzed in this paper. Prior work has mostly limited experiments to small tabular data sets like COMPAS [2], obseuring the fact that many previous methods are either heuristic, or have guarantees that are limited to linear classifiers with convex losses.
Department of Computer Science, University of Californi Irvine School of Information and Computer Science, Irvine, CA, USA
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We compare fairness relaxations via an optimization framework that explores entire trajectories of fairnes- accuurccy trade-offs, illuminating advantages and weaknesses of each method. We are the first to show (theoretically and empirically) what conditions may lead relaxation methods to fail or converge to degenerate solutions. We further show that this problem grows worse for non-convex classifiers like deep neural networks. To address this weakness, we promote three new fairness surrogates with promising theoretical properties: the log-sigmoid difference, log-sigmoid sum, and sigmoid relaxations. These surrogates are more stable and efficient to optimize than prior work. The log-sigmoid sum and sigmoid bounds have provable fairness guarantees; the log-sigmoid difference has weaker guarantees, but excellent empirical performance.
We are the first to empirically compare relaxation methods on deep neural network models for large- scale image and text classification. To enable these experiments, we show how our faimess surrogates may be optimized via stochastic gradient descent, and applied data where the sensitive attribute not always observed. Our methods are comparable to the state-of-the-art small tabular datasets, and show clear improvements for deep learning of flexible (but fair) image and text classifiers.
2 Background: Fair Classification
Let D {(x, y)) be a set of N training examples with predictive features R2, target class E {0,1}, 1. and sensitive attribute E {a, b} encoding protected group membership. A parameterized classifier fx). like logistic regression or neural network, then predicts y = when fe(x) > 0.
In this work, we focus on the fairness metrics demographic parity (DP) and equality of opportunity (EO). We define the difference in demographic parity (DDP) equal
DDP( = ((f((X) > 0 S a) P(f > 0 S = =b.
If DDP(6) >> O, group receives an unfair share of positive outcomes; if DDP(O) < 0, group b is favored. We seek models where (0) s 0. The difference in equality of opportunity (DEO) is
DEO (X) > 0 a, Y 0)- (X) > 0
b, =))
(2)
where fair classifiers have DEO 0. If false negative rates are of more concern than false positives, (E) may be modified to condition on Y instead of Y = O. We seek the best classifier whose empirical fairness disparity A(f) has magnitude smaller than some tolerance c > O:
min
L(fo(x), v), such that |A)) <. (X.
Σ
Our experiments and theorems focus on the case where fo(x) = w (xx with (possibly learned)
data representation (x),, output layer weights w, and overall parameters 0 = w U Og. We let L()) be the negative log-likelihood (or cross-entropy) loss,
((fo y) -y y log(a (f(())) (1 y) fog(x()
with (2) = 1/(1 + e e=*). This model family includes logistic regression and many neural networks.
We set (0) DDP(O) for demographic parity, A0)) = DEO(() for equality of opportunity, where
DDP(O) No.
Σ (x.D #=u
1(6())20) - No. (x.
Σ
[(f(<))>0)
(4)
DEO(() NoO
Σ (XD
1[6(0)00)-
(5)
No0
(X.W))D s=b.y=
s=
There Noy data with sensitive group and predictive label y. No. data with group and any label, and N.,, data with label y and any group. For later use, we also define Pay = N P.. = No. and P.y * as the proportions of data with each group and label. To achieve equalized odds, we may enforce two constraints as in Eq. (5), one for false positives and one for false negatives.
In addition to selecting the fairness metric, user must specify an unfairness tolerance > 0. Although we might wish to bring unfairness to exactly zero, this may not be possible except in trivial cases [22, 49]. or might come at a huge accuracy cost [27] with no guarantee of generalized fairness on test data [32]. Moreover, positive tolerances often have legal justifications: adverse impact hiring laws dictate that the ratio of hiring rates for two sensitive groups should be at least 4/5 [21].

---

2.1 Surrogates for Tractable Optimization
The constrained optimization problem of Eq. (3) is typically intractable due to the discontinuous constraints (0), which make muddentt-based algorithms for constrained optimization inapplicable or ineffective. We overcome this intractability by replacing constraints with smooth surrogates.
Linear relaxations. The widely-used family of linear relaxations [52] seeks to improve demographic parity by replacing the intractable difference in acceptance rates with the covariance between the sensitive attribute and model output. Letting+ 2 = 1 if = a and & = 0 if s = b, we then have
Cov(z, fo(x)
Σ 2 () & ([fo(x) = (lfo = 0).
(6)
Because the sensitive attribute is binary, this covariance equals a difference in expectations. Bringing this first moment relaxation [49] zero is equivalent to forcing the output distributions for the two sensitive groups to have equal means. By modifying the expectations in Eq. (6) to also condition on
Y = 0, others have applied equivalent relaxations (up constants) equality of opportunity [4, 17]. However, matching the mean response across groups is insufficient to ensure fairesss: Classifiers often still differ in higher moments, causing disparities on how groups are treated [40].
Non-linear relaxations. Zafar et al. [53, 51] also propose relaxation for equality of opportunity, the covariance between the sensitive attribute and the model response for only misclassified pointss
Cov(2,9(Jo(x)) Y = 0) x [lo(S((x)) Z = 1, = 0] - (l)(Jo(x)) Z = = 0], (7)
where f(oo(x))=
0). This constraint is non-convex, but for classifiers like SVMs with convex loss functions, convex-concave programming [45] may be used to find a local optimum. However, the gap between the relaxation and the true target persists: even when this covariance equals O, we have no guarantees about the difference in false positive rates between the two groups
2.2 Other Related Work
Post-Processing of Unfair Classifiers. Post-processing methods learn a model via an unconstrained loss with regard to fairness, and then enforce fairness as a post- pros-processing step [27] by setting group-specific decision boundaries to equalize false positive rates (or acceptance rates). However, this requires the sensitive attribute at test time. Besides being impractical in some applications, such classifiers may make different decisions for individuals with identical features x. Such disparate treatment constitutes different form of unfaimess and can be illegal in some domains [19].
Wei et al. [48] avoid requiring sensitive attributes by training a separate classifier to estimate p(S) X). Morally, this is not much different than disparate treatment; instead of treating individuals differently based on their sensitive attributes, the model treats them differently based on its estimate of their sensitive attribute. The authors also acknowledge that while their method is effective at small reductions unfairness, it often fails to achieve large reductions. Without knowledge of true sensitive attributes, proseprocsssing algorithms may lack the maneuverability to dramatically reduce unfairness.
Fairness by Density Estimation. Celis et al. [9] optimize classifiers with a constraint on the true fairness discrepancy of the data-generating distribution. This requires an explicit density estimate for the training data, for which they use a Gaussian Naive Bayes model that would poorly capture high-dimensional images or text. Generative modeling of such data is challenging research problem.
Data Set Stability. Huang & Vishnoi [31] examine the stability of fair classifiers under data perturbations, and propose regularizer that can be added to other fairness algorithms, including ours. We instead analyze and improve fairness surrogates for complex, non-convex classifiers.
Fair Mixup. Instead of penalizing a surrogate to the fairness discrepancy, Chuang & Mroueh [11] penalize the gradient of (X) along interpolated paths between data with opposite attributes. This approach is less interpretable, and does not guarantee demographic parity nor equality of opportunity.
Fairness in Computer Vision. Large-scale image data sets are often unannotated and thus lack guarantees that they are balanced along sensitive attributes such as race or gender [10]. Dataset balance has become focus of conversation in fair computer vision [29], but it is insufficient to guarantee fairnsss [47]. Other work in fair computer vision has explored issues of bias amplification [28, 55), counterfactual fairness [14], and transfer learning [18, 35). Whereas relaxation methods explore fairness- accuracy trade-offs, many vision papers use fairesss as a vehicle to boost accuracy [44, 38,
3

---

46]. By improving classifier performance on under-represented sub cob--opulations, overall accuracy can be increased, but groups may still receive disparate impact from the model's decisions.
Fairness in Natural Language Processing. Much of the previous work on fair language models has focused on domain-specifer examples of bias, such as word embeddings [5, 57, 25, 6, 58] or coreference resolution [43, 56]. In contrast, model's word representation; we want to ensure that predictive models do not discriminate against authors based on their identity. It has been shown that gender expression writing [37], so models could discriminate against authors of one gender if fairness is not mandated.
are not concerned with latent bias in the language
be predicted from
3 A Lagrangian Framework for Relaxations
The absolute value in Eq. (3) induces two linear fairness constraints, a lower bound and an upper bound, at most one of which can be active. For the optimal unconstrained classifier parameters O" arg min N (xx (x), v). we assume (without loss of generality) that A(0") > c. A())) < -E, we swap the sensitive groups a, b to negate the discrepancy and obtain A > e. If [A())) S e, the unconstrained classifier already sufficiently fair and optimally solves Eq. (3).
3.1 Fair Classification via Smooth Penalties
Letting g(r) be continuous and monotonically non-decreasing surrogate for the indicator functions arising in exact faimess constraints, we define the following tractable optimization problem:
min
Σ
L(fo(x),u) s.t. (0) ST.
(8)
N
(x,SWN)
For demographic parity, we (0)
DDP, (0), where
DDP, = No.
1
Σ
g(fo(x))
1 No. (X. s=h
Σ 9(fo(x)).
(9)
(X.
8=0
For equality of opportunity, we similarly define DEO, (0) by replacing the indicators in Eq. (5) with surrogates g()). When g(r) for DDP we recover [53], and for DEO we recover [4, 17]. In this case, both gr) and g()) are linear and convex, so when the loss is also convex we have a convex optimization problem. When g(r)
for DEO we recover the relaxation in [51, 53]. For non-linear (r). Eq. (8) non-convex even for convex losses due to the -g(r) term in (0)
Unlike some prior work, we employ the KKT conditions [42] to optimize Eq. (8) via its Lagrangian:
1 N
min (0), where (0)
Σ
x)
(10)
(X,a))E
For every relaxed-fairnes tolerance r, there exists A 2 0 such that the constrained optimum of (8) is minimizer of (10). Furthermore, second-order sufficient conditions [42, Chap. 12.5] guarantee that every local minima ê of (10), with fairness discrepancy (0). is feasible local minima of the constrained objective (8) with 7 = (0)) For non-convex losses C, gradient descent may reach a fixed point with sub-optimal likelihood. But this is concern for any optimizer, and in experiments we find that deep neural networks are flexible enough to achieve effective fairness fairness-accurage accuracy tradcoffs.
fairness-penalized We can rewrite the fairness penalized objective of Eq. (10) as a sum over data examples:
(0) =
Σ
[((o(x)) v) + (x,(x,
(11)
N
(N.E.))D
For demographic parity and equality of opportunity, the faimess regularizers given by g(fe(x))
if = a, 0,
o(fo(x)) if a, (DP), (x,,)) o(h))))
Rg (x,
(at)) if b, y 0, (EO). otherwise.
if
Pho
0
Our framework differs from prior work that introduced these surrogates that we do not seek A, We know A, will decrease as we increase X, but it might be necessary to bring Ag < 0 to achieve S e for relaxations (like the linear) where Ag does not rigorously bound A. In practice, we need not monitor Ag: we can increase À and track changes in A until we find X* with A < if it exists.

---

3.2 Degeneracy of Fairness Relaxations
When we choose an unbounded surrogate, we may observe pathological behavior where Ag becomes negative and large enough in mag- nitude for the optimizer to ignore predictive loss. For example in Fig. 1, the linear relax- ation performs reasonably well on initial synthetic dataset. We then add an outlier with (x1,222) 222) (103, 102) and y = 1. The uncon- strained model sees no change, because the new point is already classified correctly. If the outlier has 8 = 6, then the relaxed difference becomes much more negative. This outlier causes the classifier to degenerate for even small X values, focusing on improving the fairness objective at great detriment to the predictive objective.
15
10
X1
Lnglig Sun Accuracy S
lone Ascuricyi..4
Unear Acco sacii
Accu Aecu
Figure 1: Synthetic dataset with large latent fairness discrepancy. Circles have true label y = 1 and crosses have true lahel tribute, with green indicating group b. For both linear and log-sigmoid sum (see See. 4.2) fairness relaxations, we trained a logistic regression model, searching across values to find one for which DDP - 0.03. Adding a single outlier at (10", 110)) with y L, b does not change the unconstrained or log-sigmoid deci- sion boundaries, but linear deteriorates dramatically.
O. Color encodes sensitive at-
The optimization framework of Sec. 3.1 may fail in two ways: the surrogate problem (8) could be infeasible if the model is not expressive enough, or a poor choice of surrogate g(r) may cause there to be value of r for which the solution to (8) solves the true objective (3). We now pro- vide theoretical conditions under which fairness surrogates fail to achieve fairness. Detailed proofs are in the supplement.
a grid
We minimize the Lagrangian L..A of Eq. (11) with predictors (xx) and fairess surrogate g(r) that is continuous and monotonically increasing, where limits 5z = -limy- g' (r) and 6 - (r) exist. Let Pijy be the mean of ((x),. the j*h entry of (xx), for the Nay data points with sensitive group 8 and label y. Also let jtjs. be the mean of & (xx,; ;) for data with group s and any label, and Fyy be the mean of ((x), for data with label and any group.
Theorem (Degeneracy for DP). Consider a feature j such that Φ(x); 2 for all x E DD.
(1) 5 + 0 and Pjaa > Pyb., then for X > X3- 8y (150. "Ps.."
ByaPa
lim ( = -00
30
(2) 18 + and Ujaa < Pyb., then for X > N3- 57 (1....-p3a.
lim (0) = -0.
+00+
Theorem 2 (Degeneracy for EO). Consider a feature j. such that (xx; 2 0 for all x E D.
(1) 1 * 0 and Pjaan > P330, then for X >> Xj 8. (My30 (asjaonnje uooo
lim 2 = -00
(2) 8 + and Pja0 < Pj50, then for X X3
Miopo
lim ( = -O0
wy-++00
For constraint multipliers > Nj. the Lagrangian is unbounded below and can be reduced arbitrarily by changing single parameter w,. Each attribute satisfying (I) or (2) induces a critical X/. so the entire model has a critical value X = min, Aj. where we take X; = do for an attribute j not satisfying either criterion. Because the predictive loss is bounded below. divergence must be caused by Ag approaching - cc. Note this divergence is not a failure of the KKT conditions: for every finite T, the corresponding constraint multiplier À is bounded in 0 < X < X Further note that if db (x) is fixed and g(r) is linear, L,,x is convex and has no stationary points for all À > X"
While we may solve the surrogate problem (11) for any finite via some X A X", for general gr)) there is no guarantee we satisfy our true fairness constraints (3). This is illustrated in Fig. 2, which highlights gaps between the surrogate and true rate differences. Degeneracy occurs for the linear relaxation g(r) = r. where 67 = oj = 1, DDP on the Adult data set. For the ReLU relaxation of DEO, which takes g(r) = max(0, r) so that 67 = 0 but o = 1, degeneracy also occurs on the COMPAS data set; this is possible because - -g(r) and Ag are unbounded below. Although our theorem provides sufficient but not necessary condition for degeneracy, in Fig. 2 it accurately predicts the value of x for which degeneracy occurs, suggesting the bound may sometimes be tight.
Even in less extreme cases like Fig. 1 where we recover a solution to the true target, if we need to set 7 & and thus X R X*, the surrogate's magnitude may cause the learned model to mostly ignore predictive loss. While Lg regularization will prevent wy from fully diverging, it may still
5

---

Ugdg 8am
Adult
COMPAS
Figure 2: Relationship between surrogate threshold 7 and multiplier (first & third plots) or non-relaxed unfairness (second & fourth plots). When T is large, the constraint is inactive. Highlighted points show models with critical À = X derived from Theorem (left, for DDP) or Theorem 2 (right, for DEO). Our log log-sigmoid sum surrogate provably never degenerates (see Sec. 4.2). We avoid numerical instabilities via very weak Ig-regularization of weights w, with coefficient 2-20 so that models with > have bounded loss.
grow large enough in magnitude to substantially hurt performance. For example, when constrain- ing DDP on the Adult dataset, the feature occupation_ wwrtooorrootteeeeeeeeeeeeeeeeeee
induces A 0.066. Regularizing above that threshold results in huge losses to mean bog-likelihood as w diverges (see Fig. 3). This degeneracy is not clearly visible from accuracy plots because only 4% of the data has SerettioooPPottttie---eeeeee
Degeneracy becomes more prevalent for deep neural networks, which can learn one feature & (x);; such that X is minimized and very negative training loss is achievable, while doing little to improve the true fairness. The assumption that (x), 2 0 is satisfied by many common attributes including discrete indicators and ReLU non-linearities in neural networks. As we prove in the supplement, notationally complicated generalizations of Theorems 1-2 exist that characterize arbitrary (xx).
3.3 Related Work: SearchFair
The SearchFair algorithm [40] also reduced relaxations A, < 0 to enforce fairness. Letting (()) be the model parameters induced by constraint multiplier X, they prove that when the fairness-penalle penalized loss is convex, DDP(@(A)) for the (unknown) true data distribution is continuous with respect to A. If there exist A and A such that (DP(@(A )) < O, (DP(O(A*)) > 0, there exists a root x < < < X with DDP(((X9)) O. SearchFair then uses binary search approximate Xo
limiting assumption of SearchFair is that A and X exist for any fairness surrogate. One of our key contributions is to demonstrate theoretically (via Theorems 1-2) and empirically (via Figs. 2-3) that this not true: binary search cannot be used to find the root of a function with no root. Note that Lohaus et al. [40] explicitly consider both relaxations whose degeneracies are demonstrated in Fig. 2.
Continuity of (DP() required guarantee the existence of the X sought by SearchFair, is not guaranteed for non con-convex losses like (deep) neural networks. We do not use SearchFair's 's binary search for this reason, and because (as motivated in Sec. we instead seek (DDP(#) I e for
Logistic Fairness Relaxations
We promote surrogates based on the log-sigmoie g(r) = - log o(-r) and sigmoid g(r) (r)).
4.1 Log-Sigmoid Differences for Improved Fairness
(org(-)) has the same form as the likeeiiooood:: (x)) L(fo (x)) 0). When using that loss function and the DEO criterion, the two terms in Eq. (11) combine nicely, and the relaxed objective can be interpreted as simple reweighting of points: positive examples have weight 1, negative examples of group have weight Pao" and negative examples of group b have weight Peo Thus for logistic regression with < Pbo, the Lagrangian formulation in Eq. (10) is convex and bounded even though the corresponding constraints in Eq. (8) are non-convex. This analysis aligns with our earlier theorems:
Difference in Equality of Opportunity. The log-sigmoid surrogate g(r)
Theorem 3. For any surrogate g(r) of EO such that 57 O, any feature D(x), satisfying the Pso 65
conditions of Thm. 2 has a bounded degeneracy threshold X3
The reweighting interpretation shows that the log niggiioood surrogate, which has 8, 0, 0,8 = cannot degenerate for À < Pbu- Our theorem recovers that result, and extends it to other surrogates with the same asymptotic behavior (such as a ReLU function). Note that for À >> X², degeneracy as in Fig. 2 is possible as we observe for the ReLU surrogate, but this is not observed for log-sigmoid in any of our experiments. Surrogates with 6 * observe no such lower bound, and can degenerate for any À >>> O. Because neural network can learn representation to minimize X" and thus diverge

---

the objective, Theorem 3's guarantee that any learned representation (xx) exhibits a threshold above P60 powerful. A generalization of Thm. 3, that allows arbitrary ((x), is proven the supplement.
Difference in Demographic Parity. To retain this intuitive reweighting property for DP, we need to keep (r) in the same form the loss, which depends the true label y- Thus, we must use different surrogate for each target label. Suppose we use the surrogate g(r)
log (-r) for data with y = 0, and gr) = log (r) for data with y 1. Because the surrogates are of the same form as the predictive loss, we recover an unconstrained classification problem where negative examples of group a have weight 1 + 2_ negative examples of group have weight 1- }_ positive examples of Ps.
group have weight 1 Pu. and positive examples of group b have weight 1+ Ph, a single surrogate and does not apply here, but an expanded theorem is included in the supplement. We note that degeneracy is not possible for À < min(Pb. Pa. because the reweighting intepretation gives us all non-negative weights, and therefore a convex and bounded loss.
>. Thm. assumes
Related Work: Data Re-weighting. Re- Re-weighting of data points is classic way to correct deficien- cies of generative models [30, 26]. For fair classification, Kamiran & Calders [33] pre-process data to encourage demographic parity by assigning weight w(s, y) = z(s)p(g) to points from group with label y. Probabilities are estimated from the training data that y and are independent under the weighted empirical distribution. However, this lack of dependence does not guarantee demographic parity; relative to these weights, classifiers may either under- or over-balance sensitive groups.
p(*Ag)
Our lig-si difference relaxation instead implies that some amount of weight increase for the low-accuracy group, and weight decrease for the high-accuracy group, leads to approximate fairness. The search for X must be integrated with training; it cannot be determined from raw data statistics.
Related Work: Reductions Approach. Agarwal al. [1] use the 0-1 loss for both the predietive loss and the constraint. These losses linearly combine via the KKT conditions. inducing a classification problem with reweighted data. They then relax the combined loss via either hinge logistic log-likelihood surrogate. Their Fair Reductions approach is thus closely related to our log-sigmoid difference surrogate, but the two methods not exactly equivalent: their fairness criteria are defined via distinct constraints, and for constraint multipliers that induce negative weights for some training examples, they instead swap the example's label y and assign positive weights.
4.2 Log-Sigmoid Sums with Fairness Guarantees
The primary weakness of Eq. (8) is that we lack meaningful guarantees about the relationship between A, and A. When the fairness criterion is DP, we can address this problem by rewriting the unfairness
DDP(
Σ
210())200
(12)
Na.
No.
(X.S.))ED s=u
(N,S,y)ED s=b
Replacing indicators with convex upper bounds g(r), the corresponding Lagrangian becomes:
min 1
Σ [(fo(x),V) such that
Σ
g(f((x))
g(- (()fox)) ST+1. (13)
N
No.
No.
(K,A,))ED
(x.
(x.,,))ED s=b
We need g(r) 2 ((r>0) for all E R. as satisfied by the hinge function g(r) = max(0, 1 + r) and the scaled log-sigmoid g() = -c log (-r), c 1/ log(2). Because the constraint in Eq. (13) is a rigorous upper bound on (D), if we set 7 S we are guaranteed that DDP(0) < a, S < S e. This bound prevents the pathological behavior we demonstrated for other relaxations, where A, can be brought arbitrarily negative without sufficiently reducing DDP, An identical derivation can be applied to the EO criterion, resulting surrogate involving only the points with y = =0.
In practice, the Lagrangian lets us skip the need to select 7 entirely. For expressive models where (13) is feasible, there exists some surrogate threshold т, and therefore X, which reduces fairness discrepancy below e. A practitioner must simply search to find a value satisfying their tolerance e.
We can rewrite Eq. (13) as in Eq. (11), but with new fairness regularizer Rt:
(x)) Pa
if a, (DP), RS (x, =
Pop o P60
g(fo(x))
if 8 0, y = 0,
Rt (x, 8)
((-fx(x)
if s = b, = 0, (EO). otherwise.
g( (a)
if b.
Ps.
7

---

Peaor OF
Raseliro O Toows ghinng
SEP
Mean Liaihood
2801
100
Maan hood
Rabirtton
R
Acouraoy
Vear Log Lialhood
Abco 1ayy
Noan Log Likelhoodd
Adult
COMPAS
Figure 3: Fair logistic regression results on the Adult and COMPAS data sets. Each relaxation is run over a dense grid of À values until A0) < 0 is achieved on training data (or for demographic parity on Adult, until degeneracy occurs in Fig. 2). Dashed lines show results training data, solid lines on test data. For the reweighting baseline [33], the diamond shows training results and the circle test results.
Lagrangian Dual Ascent. The Lagrangian dual [1, 41] provides an iterative approach to choosing Lagrange multipliers for multiple constraints. A grid search over values is usually sufficient for single constraint [1]. but scales exponentially with the number of constraints. Some prior work has focused on efficiently setting À [1. 12, 40, 41]. but all of these methods require the use of surrogate function, and none of them discuss the desiderata for that choice. Thus, view our work as orthogonal to theirs; surrogates informed by our theory may be integrated with a more complex dual ascent method when multiple fairness constraints are enforced.
Related Work:
Related Work: Lower-Upper Bounds. Wu et al. [50] used a similar transform to replace the difference in rates with sum. They then add second constraint to Eq. (13), using a concave surrogate h(r) < [(r>0) to lower bound (O), giving us (D N - -o (0) S 7 for some lower-bound constraint threshold y. Their experiments take g(r) = max(r + 1, and h(r) -( this optimization problem is solved, we know the resulting model has -y S DDP < т. However, choosing 7 and is difficult: hinge functions are loose bounds on the 0-1 loss, so typically
-7 < -DP < т. Lohaus et al. [40] argue that for SVMs and meaningful values of 7. the constraints induce disjoint sets and no solution exists. Compared to this method, we identify the active fairness constraint and only require one upper bound. We also avoid the need to explicitly specify a threshold 5 (let alone 7) by directly varying the constraint multiplier X. This simplification critical in enabling tractable application more complex classifiers like deep neural networks.
4.3 Sigmoid Sums for Tight Bounds
We examine third and final relaxation, the non-convex sigmoid function g(r) = ar)) Because -o(r) = (-r)- 1, the difference and sum constructions lead to the same constraint. When viewed as difference, we see 6y 6 O, preventing degeneracy. When viewed as sum, we see it as scaled upper bound the indicator function, (r) 2 [(r>0)- Thus like log-sigmoid sum, there provably exists some 7 such that the solution to the surrogate achieves the true target fairness.
While sigmoids are widely used to relax indicator functions, there seems to be little work using them as surrogates for DDP or DEO. Kamishima al. [34] use sigmoids to parameterize a different. mutual information fairness criterion. The cost of this approach is that g(r) and R2 (x. y, 8) R2 (x, y, 8) are non-convex, producing local minima even for convex predictive losses. For deep neural networks, the vanishing gradients of the sigmoid function may lead to greater optimization difficulties.
Experiments and Data Sets
We compare relaxations by training cermess--regulaiigg logistic regression on tabular data, and fairness-regularizedd deep neural networks on image and text data. To ensure equal treatment, for all models the sensitive attribute is not used as a predictive attribute. Methods for hyperparameter selection, data pre-processing, and optimization are detailed in the supplement.
Relavations. We examine the linear relaxation g(r) r [52, 4, 17]: the non-linear ReI.U Diff' relaxation of [53, 51] with g(r) max(0, r); our log-sigmoid difference (LogSig Diff) formulation
8

---

with g(r) logoolorrrr o (-r) for DEO and g 1 =0) = logoologo--))
log (r) for DDP;
our log-sigmoid sum Sig Sum) upper bound g(r) logo (-r) with regularizer Rgg and our sigmoid upper bound g(r) = (r). ). As a final baseline, we test the reweighting technique of Kamiran & Calders [33] as outlined in Sec. 4.1.
5.1 Fair Logistic Regression for Tabular Data
For fairness-regularrized logistic regression we optimize Eq. (11) with negative log-likelihood loss function, linear model class (x) = 0 x, and an added L2 regularizer.
Adult. The Adult data set [36] one of the most popular in the fair classification literature [L. 4, 12, 17, 23, 24, 40, 50, 53]. The goal of the prediction task is to predict whether an individual is carning more or less than $50,000 per year. We use sex as a sensitive attribute with values male and female.
COMPAS. The COMPAS data set was compiled by Angwin et al. [2] to investigate racial bias in recidivism prediction. The goal of the classification task is to predict whether the defendant will commit another crime recidivate within two years. We use only the subset of the data with sensitive attribute Caucasian or African-American
5.2 Fair Deep Learning with Image and Text Data
To our knowledge, are the first to compare the performance of general purposs fairness relaxations on deep neural networks for text and image classification. For the computer vision tasks, we randomly-initee -enitmll-inntiaaizeed wide residual network architecture (WRN-50-2), which in 2016 broke established records on many visual recognition benchmarks including CIFAR- 100 [54]. For the text classification task, we use Google's transformer-based BERT, state-of-the-art language model [15].
CelebA. The CelebFaces Attributes data set [39] contains images of celebrities' faces with 40 annotated binary attributes. As in other work, we use smiling as the target attribute and sex as the sensitive attribute. We discard the remaining binary attributes and use the image data for prediction.
Faces of the World. The Faces of the World (FOTW) data set [20] comes from the 2016 Looking at People CVPR Challenge. We use smiling the target attribute and gender the sensitive attribute. To demonstrate the performance cost Lohaus et al. [40]'s convexity requirement, we also compare faimess-regularizze deep neural network to their kernel-based approach.
Yelp Text Data. We use a subset of the Yelp review data set [13], which includes the text of reviews along with metadata including the reviewer's first name and the review's star rating. We perform the sentiment analysis task of predicting if reviewer gives 2 4 or < 4 stars from the text of the review. We use gender the sensitive attribute, which is inferred from reviewers' first names.
Sensitive Attribute Unknown. The Yelp and FOTW data sets include examples for which the sensitive attribute is unknown or cannot be inferred. These data therefore do not contribute towards the fairness constraint, but do affect the predictive loss and improve classifier accuracy.
Minibatch loss. Because we have written the objective of Eq. (11) as a sum over data points, we can create an unbiased estimate of it from mini-batches D(1) ...,, D(T), where (*) = {(x, s, y) M has M points drawn randomly from the full data set. By estimating via batch the point- wise in Eq. (11), we are not evaluating the batch's 's surrogate discrepancy Ag. Instead, by using the Noy and Psy statistics for the entire data set (not just the batch), we evaluate the batch's contribution to the full data unfairness Ag- This is possible because demographic parity and equality opportunity decompose as sums over data examples. This scalable stochastic approximation cannot be performed for other fairness criteria like predictive parity [16] or mutual information [34].
5.3 Analysis of Results
Linear Degeneracy, On CelebA, the linear relaxation degenerates almost immediately, achieving mean log-likelihoods 1000 times worse than competitors. This is predicted by our claim that neural networks may design (xx to induce degeneracy as in Theorems 1-2. Degeneracy is less severe for FOTW and Yelp, which are initialized from pre-trained models. We conjecture that pre-training safeguards against the model learning to optimize fairness without regard for prediction.
Smoothness Matters. The log-sigmoid difference and ReLU difference surrogates have the same asymptotic limits, and therefore the same potential for degeneracy with large constraint multipliers. However, we only observe degeneracy for the ReI.U difference formulation. Due to a mismatch between the smooth predictive loss and the ReLU surrogate, the Lagrangian may be non-convex

---

Deadii Rowwighting
Rexcstion Peer
rol lina Kerral
Asourny
User Lialheed
Vetn Loadhhood
CelebA (DP)
Faces of the World
1.50
1200
Sam
Acouncy
Unar Logi Setlhood
Acaipiy
Wenn Lodthood
CelebA (EO)
Yelp
Figure 4: reiuuies-regulariiee deep neural network results on computer vision and natural language processing data sets. Each simulation uses different random seeds for drawing minibatches, revealing instability in some relaxations. All results are shown on test data. The kemel-based model optimizes convex loss function, using the SearchFair method of binary search to find model with A0)) = 0 on training data.
for any À O. In the supplement, additional experiments show that optimization convergence for non-smooth surrogates is about 10 times slower than for smooth log-sigmoids.
The Cost of Guarantees. The log-sigmoid sum formulation is guaranteed to not degenerate, but this comes at the cost of poorer likelihood. We conjecture that this is due to the surrogate punishing high-confidence model outputs. The sigmoid formulation has the same fairness guarantees, but has slightly worse accuracy for large-scale data; we conjecture this is due to additional local optima.
The Lagrangian View. The re-weighting baseline often only reduces the fairness discrepancy marginally: data set balance is insufficient to ensure fairness. This baseline can be thought of as way to set before learning based on data statistics. Its poor fairness gains argue in favor of tuning multipliers via iterative training, despite the computational demands of training several models.
The Cost of Convexity. The binary search method of SearchFair [40] is only guaranteed to find a root when the loss function is convex. In the case of image data, forcing linear model by using kernel method comes at a large accuracy cost. Though SearchFair finds a point with (0)) = 0 on the training split, due to sampling noise this does not guarantee perfect fairness on test data.
Limitations. Our strongest theoretical guarantees are about global minima, which non-convex optimization may fail to find. Training may converge to a model with arbitrarily worse likelihood than the true minimizer of Eq. (8). However, this is problem for all deep learning methods. Because our surrogates induce losses which have been widely studied deep learning, we conjecture that the same architectures that enable standard deep learning will be effective for our fair extensions.
We also acknowledge that faimeess constraints are universal solution problems of bias in artificial intelligence. Some tasks might be inherently unethical to automate, or the very existence of the task itself might be unethical and reinforce existing power structures. Demonstrating equitable group-level performance does not solve these problems, and might obfuscate deeper problems.
Discussion
We analyze three new faimess surrogates: the log- log-sigmoid difference, log-sigmoie sum, and sigmoid relaxations. They are easier to optimize than non-smooth alternatives in the literature, and provably more stable (especially for non-convex classifiers) than linear or ReL.U relaxations. Experiments demonstrate the tightness of our theoretical results, advancing understanding of trade-offs between fairness surrogates. Results on complex vision and NLP tasks confirm our approach is robust, scalable, and easily integrated with sfate-of-the-an deep neural networks.
Acknowledgements
This research supported part by the HPI Research Center in Machine Learning and Data Science at UC Irvine, well as the UC Irvine Initiative in AI, Law, and Society.
10

---

References
[I] Agarwal, A., Beygelzimer. A., Dudik, M., Langford, J., and Wallach, H. A reductions approach to fair classification. In International Conference on Machine Learning, pp. 60-69. PMIR, 2018.
[2] Angwin, J., Larson, J., Mattu, S., and Kirchner, L. Machine bias. propublica, may 23, 2016, 2016.
[3] Barocas, S., Hardt, M., and Narayanan, A. Fairness and Machine Learning. fairmlbook.org. 2019. http: /twp://wwwww////////////// www.:ffarmmooooooooo org.
[4] Bechavod, Y. and Ligett, K. Penalizing unfaireess in binary classification. arXiv preprint arXiv:1707.00044, 2017.
[5] Bolukhasi, T., Chang, K.-W., Zou, Y., Saligrama, V., and Kalai, A. T. Man is to computer programmer as woman is to homemaker? debiasing word embeddings. In Advances in neural information processing systems, pp. 4349-4357, 2016.
[6] Brunet, M.-E., Alkalay-Houlihan, C.,, Anderson, A., and Zemel, R. Understanding the origins of bias in word embeddings. In International Conference on Machine Learning, pp. 803-811.
PMLR, 2019.
[7] Buolamwini, J. and Gebru, T. Gender shades: Intersectional accuracy disparities in commercial gender classification. In Conference on fairness, accountability and transparency, pp. 77-91. PMLR, 2018.
[8] Calders, T. and Verwer, S. Three naive bayes approaches for discrimination-free classification. Data Mining and Knowledge Discovery, 21(2):277-292, 2010.
[9] Celis, L. E.,, Huang, L., Keswani, V., and Vishnoi, N. K. Classification with fairness constraints: A meta-algorithm with provable guarantees. In Proceedings of the conference on fairness, accountabilityy and Iransparency, pp. 319-328, 2019.
[10] Choi, K., Grover, A., Singh, T., Shu, R., and Ermon, S. Fair generative modeling via weak supervision, International Conference on Machine Learning, pp. 1887-1898. PMLR, 2020.
[11] Chuang, C.-Y. and Mrouch, Y. Fair mixup: Fairness via interpolation. International Conference Learning Representations, 2021. URL https:// http:/ewwwwwweee/rfrrrre. id=DN15s5BXeBn.
[12] Cotter, A., Jiang, H., and Sridharan, K. Two-player games for efficient non-convex constrained optimization. In Algorithmic Learning Theory, pp. 300-332. PMLR, 2019.
[13] Dataset, Y., 2014. URL https: http///www.elp..ccm/maaaaaaaeeea
[14] Denton, E., Hutchinson, B., Mitchell, M., and Gebru, T. Detecting bias with generative counterfactual face attribute augmentation. In CVPR 2019 Workshop on Fairness Accountability Transparency and Ethics in Computer Vision, 2019.
[15] Devlin, J., Chang, M., Lee, K., and Toutanova, K. BERT: pre-training of deep bidirectional transformers for language understanding. In Burstein, J., Doran, C., and Solorio, T. (eds.), Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, NAACL-HI.T 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume I (Long and Short Papers), pp. 4171-4186. Association for Computational Linguistics, 2019, doi: 10. 10.11863/v1/119-1 1423. URL https:: //doi. org/10. 11853/v1/n19-1223
[16] Dieterich, W., Mendoza, C., and Brennan, T. Compas risk scales: Demonstrating accuracy equity and predictive parity. Northpoint Inc, 7(7.4):1, 1,.4)),.201... 2016.
[17] Donini, M., Oneto, I., Ben-David, S., Taylo, J. S., and Pontil, M. Empirical risk minimization under fairness constraints. In Advances Neural Information Processing Systems, pp. 2791-2801, 2018.
11

---

[18] Dwork, C., Immorlica, N., Kalai. A. T., and Leiserson, M. Decoupled classifiers for group-fai -air and efficient machine learning. In Conference on Fairness, Accountability and Transparency, pp. 119-133, 2018.
[19] EEOC, T. Uniform guidelines on employee selection procedures, 1979.
[20] Escalera, S., Baró, X., Escalante, H. J., and Guyon, I. Chalearn looking at people: A review of events and resources. In 2017 International Joint Conference on Neural Networks (IJCNN) pp- 1604-1601. IEEE, 2017.
[21] Feldman, M.. Friedler, S. A., Moeller, J., Scheidegger, C.,, and Venkatasubramanian, S. Certify- ing and removing disparate impact. proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. pp. 259-268, 2015.
[22] Friedler, S. A., Scheidegger, C., and Venkatasuubammaninn, S. On the (im) possibility of faimess. arXiv preprint arXiv: 160900723, 2016.
[23] Friedler, A., Scheidegger, C., Venkatasubramanian, S., Choudhary, S., Hamilton, P., and Roth, D. A comparative study of faimess--nhancing interventions in machine learning. In Proceedings of the Conference on Fairness, Accountabilityy and Transparency, pp. 329-338, 2019.
[24] Goh, G., Cotter, A., Gupta, M., and Friedlander, M. P. Satisfying real-world goals with dataset constraints. Advances in Neural Information Processing Systems, pp. 2415-2423, 2016.
[25] Gonen, H. and Goldherg, Y. Lipstick on pig: Debiasing methods cover up systematic gender biases in word embeddings but do not remove them. In Proceedings of NAACI-HLTT, pp. 609-614, 2019.
[26] Grover, A., Song, J., Kapoor, A., Tran, K., Agarwal, A., Horvitz, E. J., and Ermon, Bias conrection of learned generative models using likelihood-free importance weighting. In Advances Neural Information Processing Systems, pp. 1108--1070, 2019.
[27] Hardt, M., Price, E., Srebro, N., et al. Equality of opportunity supervised learning. In Advances in neural information processing systems, pp. 3315-3323, 2016.
(28) Hendricks, L. A., Bums, K., Saenko, K., Darrell, T., and Rohrbach, A. Women also snowboard: Overcoming bias captioning models. In European Conference on Computer Vision, pp. 793-811. Springer, 2018.
[29] Hill, K. Wrongfully accused by algorithm. The New York Times, June, 24, 2020.
[30] Horvitz, D. G. and Thompson, D. J. A generalization of sampling without replacement from finite universe. Journal of the American statistical Association, 47(260))6636855, 1952.
[31] Huang, and Vishnoi, N. Stable and fair classification. In International Conference on Machine Learning, pp. 2879-28900 PMLR, 2019.
[32] Ji, D., Smyth, P., and Steyvers, M. Can i trust my fairness metric? assessing faimesss with unlaheled data and bayesian inference. In Advances Neural Information Processing Systems, volume 33, pp. 16000-8611- Curran Associates, Inc., 2020.
[33] Kamiran, F. and Calders, T. Data preprocessing techniques for classification without discrimi- nation. Knowledge and Information Systems, 33(1):1-33, 2012.
[34] Kamishima, T., Akaho, S., Asoh, H., and Sakuma, Pairness-awan classifier with prejudice remover regularizer. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 35-50. Springer, 2012.
[35] Kim, B., Kim, H., Kim, K., Kim, S., and Kim, Learning not to learn: Training deep neural networks with biased data. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 9012-9020, 2019.
[36] Kohavi, R. Scaling up the accuracy of naive-bayes classifiers: decision-tree hybrid. Kdd, volume 96, pp. 202-207, 1996.
12

---

[37] Koppel, M., Argamon, S., and Shimoni, A. R. Automatically categorizing written texts by author gender. Literary and linguistic computing, 17(4):401-412, 2002.
[38] Li, Y. and Vasconcelos, N. Repair: Removing representation bias by dataset resampling. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp- 9572-9581, 2019.
[39] Liu, Z., Luo, P., Wang, and Tang, X. Deep learning face attributes in the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015.
[40] Lohaus, M., Perrot, M., and von Luxburg, U. Too relaxed to be fair. International Conference on Machine Learning. 2020.
[41] Lokhande, V. S., Akash, A. K., Ravi, S. N., and Singh, V. Fairalm: Augmented lagrangian method for training fair models with little regret. In European Conference Computer Vision, pp. 365-381. Springer, 2020.
[42] Nocedal, and Wright, S. Numerical optimization. Springer Science & Business Media, 2006.
[43] Rudinger, R., Naradowsky, J., Leonard, B., and Van Durme, B. Gender bias in coreference resolution. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pp. 8-14, 2018.
[44] Ryu, H. J., Mitchell, M., and Adam, H. Improving smiling detection with race and gender diversity. arXiv preprint arXiv:1712.00193 1(2):7, 2017.
[45] Shen, X., Diamond, S., Gu, Y., and Boyd, S. Disciplined convex-concave programming. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp- 1009-1014. IEEE, 2016.
[46] Wang, M., Deng, W., Hu, J., Tao, X., and Huang, Y. Racial faces in the wild: Reducing racial bias by information maximization adaptation network. In Proceedings of the IEEE International Conference Computer Vision, pp. 692-702, 2019.
[47] Wang, T., Zhao, J., Yatskar, M., Chang, K.-W., and Ordonez, Balanced datasets are not enough: Estimating and mitigating gender bias in deep image representations. In Proceedings of the IEEE International Conference on Computer Vision, pp. 5310-5319, 2019.
[48] Wei, D., Ramamurthy, K. N., and Calmon, F. Optimized score transformation for fair classi- fication. In International Conference on Artificial Intelligence and Statistics, pp. 1673-1683. PMLR, 2020.
[49] Woodworth, B., Gunasekar, S., Ohannessian, M. I., and Srebro, N. Learning non-discrminatory predictors. In Conference on Learning Theory, pp. 1920 1920-1953. PMLR, 2017.
[50] Wu, Y., Zhang, L., and Wu, X. On convexity and bounds of fairness-aware classification. In The World Wide Web Conference, pp. 3356-3362, 2019.
[51] Zafar, M. B., Valera, I., Gomez Rodriguez, M., and Gummadi, K. P. Fairness beyond disparate treatment & disparate impact: Learning classification without disparate mistreatment. In Proceedings of the 26th international conference on world wide web. pp. 1171-1180, 2017.
[52] Zafar, M. B.. Valera, I., Rogriguez, M. G., and Gummadi, K. P. Fairness constraints: Mech- anisms for fair classification. In Artificial Intelligence and Staristics, pp. 962-970. PMLR, 2017.
[53] Zafar, M. B., Valera, I., Gomez-Rodriguee M., and Gummadi. K. P. Fairness constraints: A flexible approach for fair classification. Journal of Machine Learning Research, 20(75):1-42, 2019. URL http: / jmlr. orgoooagaaa. httpps/ppps//// stteerss/////// 18220/11110 26222..11222222 html.
[54] Zagoruyko, and Komodakis, N. Wide residual networks. In British Machine Vision Confer- ence 2016. British Machine Vision Association, 2016.
13

---

[55] Zhao, J., Wang, T., Yatskar, M., Ordonez, V., and Chang, K.-W. Men also like shopping: Reducing gender bias amplification using corpus- level constraints. In Proceedings of the 2017 Conference Empirical Methods in Natural Language Processing, 2017.
[56] Zhao, J., Wang. T., Yatskar, M., Ordonez, V., and Chang, K.-W Gender bias in coreference resolution: Evaluation and debiasing methods. Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, volume 2, 2018.
[57] Zhao, J., Zhou, Y., Li, Z., Wang, W., and Chang, K.-W. Learning gender-neutral word embeddings. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing, pp. 4847-4853, 2018.
[58] Zhao, J., Wang, T., Yatskar, M., Cotterell, R., Ordonez, V., and Chang, K.-W. Gender bias in contextualized word embeddings. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Pupers), pp. 629-634, 2019.
14


Reviews:
[{"review_id": "vaGX6JjrmY", "reviewer": "Reviewer_4qDK", "summary": "The authors study fairness relaxations, especially in deep learning settings. They propose several conditions under which prior fairness surrogates may degenerate. Three new surrogates are proposed further to avoid degeneracy and the performance and stability of the new surrogates are proved by real-world experiments.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "Generally, the authors propose several interesting fairness relaxations and prove the effectiveness both theoretically and empirically. However, more analysis on the theories is needed and the experiment results should be further explained. Meanwhile, the writing of the paper should be improved.\n\n**Pros**\n\n1. Theory part: Theorem 1 and 2 are insightful results and they show that under some conditions, ill-defined fairness relaxations will degenerate. Meanwhile, it is interesting to develop the logistic sum from the logistic difference.\n2. Experiment part: Different kinds of datasets are included (both tabular and deep tasks). In addition, several meaningful conjectures are proposed, which may shed light on the optimization of fairness in deep models.\n\n**Cons**\n\n1. Theory part: Theorem 1 and 2 propose the critical points. However, it will be more useful if the authors could discuss the tightness of the critical point. In other words, when will the critical points be small enough so that the relaxations would totally fail and when will the critical points be large? \n2. Experiment part: An important baseline [1] is missing for the DP setting. In addition, improvements over ReLU Difference for the EO setting are not significant.\n3. Writing part: The writing should be improved. Some notations are used without explanation (such as $\\gamma$ at Line 283) and some notations are introduced in different parts of the paper so that it is difficult to look up (such as $p_{s0}$ and $\\mu_{jsy}$). I think it would be better if the authors could provide a paragraph to introduce all the notations solely. In addition, explanations of the experiments on tabular datasets are missing. This may be caused by the space limit but some texts could be moved to the appendix (such as Line 317 to 338).\n4. Some small typos:\n   - Line 249: \"A generalization Theorem 3\" --> \"A generalization of Theorem 3\"\n   - Line 342: \"to induce cause degeneracy as in Theorems 1-2\" --> \"to cause\" or \"to induce\"\n   - Figure 4 subcaption: \"CelebA (EOO)\" --> \"CelebA (EO)\"\n\n**References**\n\n[1] Zafar, Muhammad Bilal, et al. \"Fairness constraints: Mechanisms for fair classification.\" Artificial Intelligence and Statistics. PMLR, 2017.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As shown in the main review part, theory, experiment, and writing could be improved.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "t1JVJHupz-", "reviewer": "Reviewer_T3F6", "summary": "The paper discusses several relaxations for the hard-indicator based fairness measures and compares their fairness-accuracy tradeoffs. \n\nDetailed discussion on the necessary conditions for the failure case of certain relaxations (like linear or hinge) is provided. When the said conditions are satisfied, it is shown that the method converges to degenerate solutions where improving the fairness measure results in very high loss values of the prediction function. \n\nThree surrogates are proposed, namely, the logistic sum, the logistic difference, and the sigmoid relaxation. They are shown to be more stable than the linear and hinge relaxations especially in non-convex models. \n\nExperimental results are provided on tabular, vision and NLP datasets.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "## Strengths\n\nThe paper identifies that degenerate solutions are not caused not by the failure of KKT conditions but instead because of the conditions discovered in the paper (one of the important ones being the asymptotic behaviour). As demonstrated in the paper, despite \\lambda being bounded, the Lagrangian could turn out to be unbounded. \n\nThe logistic sum relaxation offers a means to search for only one parameter ($\\lambda$)  instead of two ($\\lambda$ and $\\tau$). Here, $\\lambda$ is the constraint multiplier and $\\tau$ appears in DDP $\\le \\tau$. Varying only the value of $\\lambda$ for a feasible solution of the objective function ensures that the tolerance is brought under $\\epsilon$. \n\nIt is a strength that the claims of the paper on the degeneracy of current fairness relaxations is supported both by empirical and theoretical evidence (Theorem 1, 2). The experiments support the applicability of the proposed relaxation even in the regime of non-convex models such as deep networks. \n\nSection 5 offers some valuable insights into the behavior of the relaxations, such as -- despite the similar asymptotic behavior of ReLU and the proposed logistic difference, degeneracy is observed only with ReLU indicating the importance of adopting smooth relaxations. \n\n\n## Weaknesses \n\nDegeneracy is primarily caused by the fairness measure $\\Delta_g$ approaching $-\\infty$. This happens when the parameters of the model $w$ diverge. This is as per Theorem 1 and 2. A simpler alternative to prevent degeneracy would be to incorporate weight clipping / gradient clipping approaches. It is unclear how such regularization techniques compare against the use of the proposed relaxations. \n\nThe assumption for degeneracy $\\delta_g \\ne 0$ is weak as only a handful of relaxations, such as max(x, 0) or a linear function, qualify for this criterion. The use of softmax and gaussian functions, with $\\delta_g = 0$, as a relaxation has been very common in the literature. Eg., eq (2) in  [1] or [2]. Very few methods in the existing literature have adopted max(x, 0) or linear relaxation, thereby reducing the relevance of the paper within the community. \n\nTo prepare the claims on degeneracy of fairness relaxations, the authors use the inequality constraint $\\Delta_g \\le \\epsilon$ rather than $\\Delta_g = 0$ adopted by several prior works (section 3.1 of the paper). It is unclear what motivates this modeling choice. Observe that adopting $\\Delta_g = 0$ has an immediate benefit -- it would prevent the failure case where $\\Delta_g$ is significantly negative yet the DDP measure is not satisfied.  \n\nThe paper misses out on discussing generalization ability of the proposed relaxation techniques. It is well studied [3] that a differentiable surrogate to the indicator function leads to over-constrained objective, causing poor generalization performance. It is unclear if any of the proposed relaxations suffer from such an over-constraining phenomena. It is further unclear how the gap between the training and test accuracies differs across different relaxations. \n\n\n[1] http://proceedings.mlr.press/v28/zemel13.pdf\n\n[2] https://arxiv.org/pdf/1412.5244.pdf\n\n[3] https://www.fatml.org/media/documents/training_fairness_constrained_classifiers_to_generalize.pdf\n\n\n\n## Comments / Questions\n\nCan the highly unstable training, seen on CelebA and FOTW datasets due to the use of linear relaxation, be reduced by lowering the learning rate of the model?\n\nline 43 in the paper argues that the proposed surrogates are robust to outliers. However, there is no experimental or theoretical evidence provided for this in the paper. Please elaborate or edit the line accordingly. \n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Authors have discussed the limitations of their work. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8-10"}, "extra_text": {}}, {"review_id": "F3yxF4LmuBp", "reviewer": "Reviewer_okm9", "summary": "A popular approach in fair machine learning in-processing methods is to replace the original fairness constraints, which are non-convex and non-differentiable, with surrogates that are easier to handle. This paper studies several of these relaxations. On the one hand, it shows some of their limits by proving sufficient conditions under which existing surrogates may lead to optimization problems where the Lagrangian has no stationary points. On the other hand, it proposes three relaxations that are less prone to this undesirable behavior.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "Pros:\n - The paper is relatively easy to follow\n - Studying the limits of surrogates in fair machine learning is an important problem\n - The paper comes with both theoretical and empirical results\n\nCons:\n - Some comparison to existing work is missing\n - It remains unclear how fair models can be efficiently found using the proposed relaxations\n - The theoretical results are limited to very specific problems\n\nDetailed comments:\n1. Surrogate constraints are an appealing way to enforce fairness in machine learning as they are relatively easy to implement and the resulting constrained optimization problems may be solved efficiently. Unfortunately, these surrogates are often not guaranteed to lead to fair solutions. This paper proposes to study a particular case of failure where the lagrangian of the problem may become arbitrarily small, potentially leading to very sub-optimal solutions. Thus, proposing relaxations that can avoid this pitfall is important.\n\n2. A comparison with the work of Cotter et al., Two-player games for efficient non-convex constrained optimization (2019) is missing. It studies the more general problem of non-convex constrained optimization and proposes an approach based on surrogates in a lagrangian formulation that is very reminiscing of the problem considered here. This approach should, at the very least, be considered as a baseline in the experiments \n\n3. While it is interesting to exhibit sufficient conditions under which surrogates may lead to degeneracies (Theorem 1 and 2), it remains unclear whether the relaxations will behave well when the conditions are not met. Furthermore, the result seems to be limited to linear models (since the representation is fixed) with a particular family of loss functions. This greatly reduces the interest of the results.\n\n4. Three different surrogates are proposed with the common idea that the indicator function should be relaxed. While the relaxations themselves are not new, for example it has long been known that the sigmoid may be used to approximate the indicator function, the paper gives interesting insights on their particular interest for fairness and gives interesting connections to the existing literature.\n\n5. From the paper, it seems that a critical point to achieve fairness using the proposed relaxations is to correctly choose the Lagrangians parameters \\lambda. Unfortunately, the paper does not provide any algorithm to find the optimal parameters in an efficient way (a grid-search is used in the experiments). This might not be trivial in practice and thus slightly reduces the overall interest of the paper. \n\nSummary of the review:\n\nOn the one hand, this paper studies the important problem of surrogates in fair machine learning showing the limits of existing formulations and proposing alternative relaxations. On the other hand, the applicability of the theoretical results remains quite limited. Furthermore, a comparison with the work of Cotter et al., that seems quite close in spirit, is missing. Overall, I think that this paper presents valuable ideas but is slightly below the acceptance threshold.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations and potential negative societal impact of this work were correctly addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "98e4QzGueeR", "reviewer": "Reviewer_C1h7", "summary": "The authors study several surrogates for fairness constraints. They show that simple surrogates such as linear can lead to degeneracy. They show that when the derivative of the surrogate does not go to zero as the prediction goes to infinite, we should deal with degeneracy. They show that such degeneracy is not only theoretical and happens on real-world datasets as well for linear surrogates. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "", "main_review": "The authors study several surrogates for fairness constraints. They show that simple surrogates such as linear can lead to degeneracy. They show that when the derivative of the surrogate does not go to zero as the prediction goes to infinite, we should deal with degeneracy. They show that such degeneracy is not only theoretical and happens on real-world datasets as well for linear surrogates. \n\nThe writing can be improved, I had a hard time understanding some parts of the paper! Especially some parts of the paper were really dense and it was hard to understand the main point. \n\nPeople usually use the loss function as the surrogate for f especially when working with DNN. So, the proposed surrogates (sigmoid and log sigmoid) are not very novel. However, the thorough analysis of them and showing that they will not lead to degeneracy was interesting!\n\nMinimizing the worst-case group loss (either grouping data points with label and sensitive attribute to achieve EOO or only sensitive attribute to achieve DP) is also a very common technique for fairness application (e..g, group-DRO). (note that we can always randomize the performance of the better group if equality is really the goal!). Do they also have the mentioned degeneracy problems?\nI didn’t exactly follow why Agrawal et al. method may fail, I think a better description there would help. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies the effect of different fairness relaxations in the training of "fair" classifiers. The reviewers point out some limitations of the work, but think that the paper has ideas that could be interesting to the NeurIPS community, and therefore recommend acceptance. The authors are strongly encouraged to incorporate the feedback provide, and in particular, work on improving the writing as suggested by the reviewers.

**Additional comments from AC:**

To Reviewer okm9's comment on comparison to Cotter et al., my understanding of their work is that they propose a Lagrangian-based solver, in which the classifier is optimized using surrogate relaxations, whereas the Lagrange multipliers or costs $\lambda$ are updated using the *unrelaxed fairness constraint*. I think this is reminiscent of how you perform grid search, although when there are multiple constraints (e.g. over large number of protected groups), a simple grid search may not be feasible, and methods such as theirs may be needed. I think it's important to at least have a discussion on this in the paper, and to be explicit about the difficulty of applying grid search with non-binary attributes.

To Reviewer C1h7's question on why the method of Agarwal et al. may *fail* with non-negative costs, I don't think the authors provided a response. I can see why the surrogate relaxations would become non-convex with negative costs, but given that training of deep networks would anyway result in a non-convex problem, would the surrogate being non-convex be all that problematic? As the reviewer suggested, I think it's important to elaborate on why their method may *fail* (which I think is a strong claim).

Finally, a couple of minor comments on the writing from a quick glance:
- In the abstract, you mention that "We propose an easy-to-use and robust way of imposing fairness constraints when training": are you referring to Lagrangian formulation, which I think has already been well-studied in the literature and not necessarily a contribution of this paper, or specifically to the use of grid-search to tune $\lambda$, which unfortunately is not scalable to multiple constraints / protected groups. It might be good to be a bit more specific about what the paper claims to be its proposal.
- In the intro, you mention that "We also provide some of the first empirical results on fair relaxations for large-scale image and
text classification." Is this statement entirely accurate? I do remember CelebA being used commonly in prior fairness papers, e.g. https://arxiv.org/pdf/2004.01355.pdf.

I trust that the authors will put in the time and effort to make a thorough pass over the paper to polish up the writing, and to ensure that the statements made are all precise and accurate.

Decision: Accept (Poster)