An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning
Authors: Cyrus Cousins
Venue: NeurIPS 2021 Poster (2021)
Keywords: PAC-Learning
Fair Learning
Welfare
Computational Learning Theory
Statistical Learning Theory

Abstract: We address an inherent difficulty in welfare-theoretic fair machine learning (ML), by proposing an equivalently-axiomatically justified alternative setting, and studying the resulting computational and statistical learning questions. Welfare metrics quantify overall wellbeing across a population of groups, and welfare-based objectives and constraints have recently been proposed to incentivize fair ML methods to satisfy their diverse needs. However, many ML problems are cast as loss minimization tasks, rather than utility maximization, and thus require nontrivial modeling to construct utility functions. We define a complementary metric, termed malfare, measuring overall societal harm, with axiomatic justification via the standard axioms of cardinal welfare, and cast fair ML as malfare minimization over the risk values (expected losses) of each group. Surprisingly, the axioms of cardinal welfare (malfare) dictate that this is not equivalent to simply defining utility as negative loss and maximizing welfare. Building upon these concepts, we define fair-PAC learning, where a fair-PAC learner is an algorithm that learns an ε-δ malfare-optimal model with bounded sample complexity, for any data distribution and (axiomatically justified) malfare concept. Finally, we show conditions under which many standard PAC-learners may be converted to fair-PAC learners, which places fair-PAC learning on firm theoretical ground, as it yields statistical — and in some cases computational — efficiency guarantees for many well-studied ML models. Fair-PAC learning is also practically relevant, as it democratizes fair ML by providing concrete training algorithms with rigorous generalization guarantees.

An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning
Cyrus Cousins
Department of Computer Science
Brown University
Abstract
We address an inherent difficulty in welfare-theorete fair machine learning (ML), by proposing an equivalently aaliimmllliaiiiiiicllllll justified alternative setting, and study- ing the resulting computational and statistical learning questions. Welfare metrics quantify overall wellbeing across population of groups, and welfare-based objec- tives and constraints have recently been proposed to incentivize fair MI. methods to satisfy their diverse needs. However, many ML problems are cast as loss minimiza- tion tasks, rather than utility maximization, and thus require nontrivial modeling to construct utility finctiins. We define complementary metric, termed malfare, measuring overall societal harm, with axiomatic justification via the standard axioms of cardinal welfare, and cast fair ML malfare minimization over the risk values (expected losses) each group. Surprisingly. the axioms of cardinal welfare (malfare) dictate that this is not equivalent to simply defining utility negative loss and maximizing welfare. Building upon these concepts, we define fair-PAC learning, where fair-PAC. learner is algorithm that learns an e-ō malfare-optimal model with bounded sample complexity, for any data distribution and (axiomatically justified) malfare concept. Finally, we show conditions under which many standard PAC-learners may be converted to fair-PAC learners, which places fair-PAC learning on firm theoretical ground, it yields statistical and in some cases computational - efficiency guarantees for many well-studied ML models. Fair-PAC learning also practically relevant, as it democratizes fair ML by providing concrete training algorithms with rigorous generalization guarantees.
Introduction
It is now well-understood that contemporary ML systems exhibit differential accuracy across gender, race, and other protected groups. for tasks like facial recognition [5 in medical settings [7]. and many others. This exacerbates existing inequality, as facial recognition in policing yields disproportionate false-arrest rates, and medical MI. yields disproportionate health outcomes. Welfare- centric MI methods encode both accuracy and fairness in welfare function defined on set of groups, and optimize or constrain welfare learn fairly. This addresses differential accuracy and bias issues across groups by ensuring that (1) each group is seen and considered during training, and (2) an outcome is incentivized that is desirable overall, ideally according to some mutually-agreed-upp welfare function. Unfortunately, welfare metrics require notion of (positive) utility, and argue that this is not natural to many ML tasks, wherein we instead minimize some negatively connoted loss value. We thus define complementary measure welfare, which we term malfare, measuring societal harm (rather than wellbeing). particular, malfare arises naturally when one applies the standard axioms of cardinal welfare to loss values rather than utility values. We then cast fair ML as a direct malfare minimization problem, and study its computational and statistical aspects.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Perhaps surprisingly, minimizing a malfare function is not equivalent to maximizing some welfare function while taking utility to negative loss, except in the egalitarian and utilitarian edge cases. This is because nearly every function satisfying the standard axioms of cardinal welfare requires nonnegative inputs, and is in general impossible to contort a loss function into a utility function while satisfying this requirement. For example, while minimizing the 0-1 loss, which simply counts the number of mistakes a classifier makes, is isomorphic to maximizing the 1-0 gain, which counts number of correct classifications, minimizing some malfare function defined on 0-1 loss over groups is not in general equivalent to maximizing any welfare cififarefunooe function defined on 1-0 gain.
Building upon these concepts, we develop generic notion of fair ML, termed fair-PAC (FPAC) learning. where the goal learn models for which finite training samples may guarantee (additively) e-optimal malfare, with probability at least 1 - 6, for any (axiomatically justified) malfare concept. This definition extends Valiant's 's [31 classic PAC-learning formalization, and we show that, with appropriate modifications, many (standard) PAC-learers may be converted to FPAC learners. In particular, we show via a constructive polynomial reduction that realizable FPAC-learning reduces to realizable PAC-learning. Furthermore, we show, non-constructively that for learning problems where PAC-learnability implies uniform convergence, it is equivalent to FPAC-learnability. We also show that when training is possible via conver optimization under standard assumptions, then training E-ō malfare-optimal models, like training risk-optimal models, requires polynomial time. We briefly summarize contributions below.
1. We derive in section the malfare concept, extending welfare to measure negatively-connote attributes, and show that malfare-miinimzzttion naturally generalizes risk-minnmizatiinn to produce fairness-sensifive MI. objectives that consider multiple protected groups
2. Section 3 extends PAC-learning to FPAC-learning. where we consider minimization of malfare rather than risk (expected loss) objectives. Both PAC and FPAC learning are parameterized by learning task (model space and loss function), and we explore the resulting learnability hierarchy. 3. We show that for many loss functions, PAC and FPAC learning are statistically equivalent, and convexity conditions for computationally efficient PAC-learning are also sufficient for FPAC-learning.
1.1 Related Work
Constraint-basee notions of algorithmic fairness have risen to prominence in fair ML, with the potential to ensure fairness (i.e., via parity constraints between the various groups, such as equalized odds, demographic parity, equality of opportunity, equality of outcome, etc.), thus correcting for some forms of data or algorithmic bias. While noble in intent and intuitive by design, fairness via such statistical constraints has several prominent flaws: most notably, several popular parity constraints are mutually unsatisfiable [16), and their constraint- based formulation inherently puts accuracy and fuirness at odds, where additional tolerance parameters are required to strike a balance between the two. Furthermore, recent works [14 [1] have shown that welfare and even disadvantaged group utility can be harmed by such fairness constraints, calling into question whether these constraints actually benefit those that they purport to aid.
Perhaps in response to these issues, some recent work has trended toward welfare- based fairness- concepts, wherein both accuracy and fairness are encoded in a welfare function defined on a group of
subpopulations. Welfare then directly optimized 14 23 28 or constrained [3] 29 to promote fair learming across all groups. Perhaps the most similar to our work is a method of [14], wherein they directly maximize empirical welfare over linear classifiers; however, as with other previous works, an appropriate utility function must be selected, which we avoid by instead using malfare. We argue that empirical welfare maximization an effective strategy when an appropriate and natural measure of utility is available, but in MI. contexts, there is no "correct" or clearly neutral way to generically convert loss to utility. We avoid this issue by working directly with malfare and loss.
Our most poignant contrast to existing theoretical work is the Seldonian learner [30) framework, which essentially extends PAC-learning to learning problems with both constraints and arbitrary nonlinear objectives. We argue that this generality is harmful to the utility of the concept as a mathematical or practical object, as nearly any ML problem can be posed as a constrained nonlinear optimization task. The utility in FPAC learning is that it is sophisticated enough to handle faimess issues with an woaomattiall--jutifiiii objective, but remains simple enough to study as a mathematical object, leading to informative reductions between various PAC and FPAC learnable classes. A similar framework, termed "multi-group agnostic PAC learning" [K 24 also considers per-group risk values, but there regret (maximum relative dissatisfaction), rather than malfare, is minimized.

---

2 Aggregating Sentiment within Populations
generic aggregator function M(S; w) summarizes some sentiment vector 8 F across population of g groups, weighted by probability vector w E IR4 s.t. [|wl|| 1. When S measures a desirable quantity, generally termed utility, the aggregator function is a measure of cardinal welfare [99] and thus quantifies overall wellbeing. We also consider the inverse-notion, that of overall illbeing, termed malfare, in terms of an undesirable S, generally loss or risk, which naturally extends the welfare concept. We show an equivalent axiomatic justificattin for malfare, and argue that its use is more natural in many situations, particularly when considering or optimizing loss functions.
Definition 2.1 (Aggregator Functions: Welfare and Malfare). An aggregator function M(S; w) measures the overall sentiment of population, given sentiment vector S and probability vector If denotes& a desirable quantity (c.g., utility), we call M(S; w) a welfare function, written W(S; w), and inversely, if it is undesirable (e.g., disutility, loss, or risk), we call M(S; w) a malfare function, written (S:
For now, think of the term aggregator function as signifying that entire population, with diverse and subjective desiderata, is considered and summarized into an aggregate value M(S; w), rather than a single group's perspective (i.e., some S,). As we introduce axioms and show consequent properties, the appropriateness of the term shall become more apparent. We use the term sentimens to refer to S with neutral connotation, but when discussing welfare or malfare, often refer to S as utility or risk, respectively, as in these cases, S describes a well-understood preëxisting concept. We shall see that often aggregator functions interchangeable, however, in order to promote fairness, the desirable axioms of malfare and welfare functions differ slightly. The notation reflects the distinction; M(S; w) is M for mean, whereas W(S:w) is W for welfare, and (SS; w) is M (inverted W), to emphasize its inverted nature.
utility values and risk values are mathematically
2.1 Axioms of Cardinal Welfare and Malfare
Definition 2.2 (Axioms of Cardinal Welfare and Malfare). We define the aggregatoo-function axioms for aggregator function M(S; w) below. For each item, assume (if necessary) that the axiom applies VS,S S' E Ri scalars a, 3 E Ro+. and probability vector w R
1. Strict Monotonicity; S * 0
M(S; un) < M(S + ww:
Weighted Symmetry Suppose S' E Bgg and probability vector w' E Rg' such that for all " E Ro+ holds S w; = Ens,, w/ Then M(S; = M(S")w"')
Contimuity: M(S; w) is a continuous function both S and w.
4. Independence of Unconcerned Agents:
M((Sig-1. w) S M((5' w) = (() S M((5
5. Independence of Common Scale: M(S; w) < M(S:; w)) = M(aS; M(aS';uu).
6. Multiplicatiiv Linearity: M(oS;; w) oM(S:w)
Unit Scale: M(1; w) M((I.... w); 1.
8. Pigou-Dalton Transfer Principle: Suppose = w S=w w S', and for all i E (l....,g]
1 - 5 S|m - Stl. Then W(S';w) w) 2 W(S;w).
9. Negated Catou- Transfer Principle: Suppose as in 8 but conclude MSS; ww) I (MSS:)) w).
We take a moment to comment on each axiom, to preview their purpose and assure the reader of their necessity. Axioms] 5 are essentially the standard axioms of cardinal welfarism [22] 25). Together, they imply (via the Debreu-Gorman theorem [10] 12)) that any aggregator function can be decomposed as a monotonic function of a sum (over groups) of logarithm or power functions.
Axiom 6 is a natural and useful property, and one which enables dimensional analysis on mean functions; in particular, the units of aggregator function match those of sentiment values. Note that axiom
6 implies axiom 5 and is thus simple strengthening of a traditional cardinal welfare axiom. We will also see that it is essential to show convenient statistical and learnability properties. Axiom
In unweighted case, it standard define symmetry as simply M(S) = M(T(S)) for all permutations n over fl...., g). but with weightings, the simple extension M(S; w) = ((())); x (w)) is not quite sufficient. In particular, in this weaker form, nowhere is additive decomposability, wherein group may be decomposed into multiple groups of the same sentiment value and total weight without impacting the aggregate, codified.
3

---

furthers this theme, as it ensures that not only do units of means match those of S, but scale does as well (making comparisons like "S; above the population's 's welfare" meaningful), and also enabling comparison across populations (i.e., comparing averages rather than sums).
Finally, axiom g the Pigou-Dalton transfer principle 21 is also standard in cardinal welfare theory, as it ensures fairness in the sense that welfare is higher when utility values are more uniform (i.e., incentivizing equitable redistribution of "wealth" in welfare). Its antithesis, axiom 9 encourages the opposite; in the context of welfare, this perversely incentivizes inequality, but for malfare, which we generally wish to minimize, the opposite occurs, thus this axiom characterizes fairness in the context of malfare. We thus state axioms 9 specifiical for welfare or malfare, respectively, whereas axioms apply equally well both welfare and malfare.
Axioms 15 are modified from their standard presentation to include the weighting w, wherein continuity must also hold over w, and weighted symmetry (2) specifies additionally that weight may be transferred between groups with equal sentiment value. Axioms 66 7 are novel to this work, and are key in strengthening the Debreu-Gorman theorem to ensure that all welfare and malfare functions are power-means in the sequel. Axiom is also novel, as it is necessary to flip the inequality of axiom 8 when the sense of the aggregator function is inverted from welfare malfare; in particular, the semantic meaning shifts from requiring that "redistribution of utility is desirable" to "redistribution of disutility is not undesirable."
The Power-Mean We now define the p-power-mean M2(5)). for any P E RU+, which we shall use to quantify both malfare and welfare. Power-means arise when analyzing aggregator functions obeying the various axioms of definition 2.2 and are thus particularly important to this work.
Definition 2.3 (Power-Mean Welfare and Malfare). Suppose p E RU+oo, sentiment vector S E R//+ and probability vector w RQ.. We then define the p-weighted poret-ooooeeeeeee mean as
9
M)(S;w)= = S Mo(S; w) = exp Σ w. In
Ms; w) = + max SS;
iel....
where E { {-00, 0, ) attain their limits, the minimum, geometric mean, and maximum, respectively.
Theorem 2.4 (Properties of the Power-Mean). Suppose sentiment vectors S, E &R. and probabil- ity vector w E R.. The following then hold.
1. Monotonicity: (S; w) is weakly-monntoricall---rreeeeeeee
in p.
Subadditivity: Vp 2 1 Mp(S + S'; w) S M, w) + M, w).
Contraction: Vp 2 1: MM w) MS'; w) S M,(S S :w) < S S'
4. Curvature: (S w) concave in S for p S and convex in S for porp211 1.
2.2 Properties of Welfare and Malfare Functions
We now derive properties of welfare and malfare from the axioms of definition 2.2
Theorem 2.5 (Aggregator Function Properties). Suppose aggregator function M(S; w)) and assume arbitrary sentiment vector S E Rg and probability vector w E RR_. If M(:-)) satisfies (subsets of) the snggregattor-unctionn axioms (see definition 2.2). then M(::-) exhibits the following properties.
1. Identity: Axioms 7 imply that Vo E Tk M(a1; w) a..
2. Rebreu-Gorman Factorization: Axioms imply Ep E R. striellymomnoooiccallyyonreessss continuous F TR. Ro_
M(S; F
Σ w. ((S.)
with {
p = 0 fo(x) In(x)) p + 0
fp(r) = ())
3. Power-Mean Factorization: Axioms
imply F(x) = f (z), thus M(S: w) = (p
4. Fair Welfare: Axioms 5 and imply E (-o0, 1].
5. Fair Malfare: Axioms and imply p oo).
Theorem 2.5 tells us that the mild conditions of axioms 5 (generally assumed for welfare), along
with 6 (multplicatiive lincarity), imply that welfare and utility, or malfare and loss, are measured in

---

the same units (e.g., nats of cross-entropy loss, or dollars of income utility), and the power- effectively the only reasonable family of welfare or malfare function; even without axiom 6 axioms 15 imply aggregator function functions are still monotonic transformations of power-means. Furthermore, the entirely milquetoast unit scale axiom (7) implies that sentiment values and aggregator functions have the same scale, making comparisons like "the risk of group is above (or below) the
power-mean
population's malfare" meaningful. Finally, we have that (- w) promotes equitable redistribution of utility for I 1, and (p w) promotes equitable redistribution of loss for p Z 1.
3 Statistical and Computational Learning-Efficiene Guarantees
In this section, define formal notion fair-learnability, termed FPAC-learning, where a loss function and hypothesis class are FPAC-learnbble essentially if any distribution can be learned to approximate malfare-optimality from a finite sample (w.h.p.). We then construct various FPAC learners, and relate the concept to standard PAC learning [31], with the understanding that this allows the vast breadth research on PAC-learning algorithms to be applied to FPAC learning. In partieular, we show a hierarchy of fair-learnability via generic statistical and computational reductions.
Definition 3.1 (Hypothesis Classes and Class Sequences). A hypothesis class is a family of functions mapping domain X' to codomain V, and hypothesis class sequence H. H1, H2,... is nested sequence hypothesis classes, each mapping X + V. In other words, Hi C H2 C.
For example, linear classifiers naturally form a sequence of families using their dimension as Ha = {ā + sgn(ī (WT..d 0)) v ]. The hypothesis class sequence concept allows us to distinguish statistically-easy problems, like learning hyperplanes in finite-dimensional Rd,, from problems, like learning hyperplanes in R It is also used to analyze the computational complexity of learners as increases.
3.1 Empirical Malfare Minimization and the Rademacher Average
We define the risk of hypothesis h X + y w.r.t loss e: Y x y + R+ on distribution 'D over (X x V), and the empirical risk on sample E (X x 3)m as R(h;
E (a.y)~
h(x)] & R(h; l,); = E [((v,hxx)]]
(a,9)E=
respectively. The goal in ML is generally to recover the ht that minimizes (true) risk, and empirical risk minimization (ERM) computes h = argmin f, as a proxy for h" = argmingeu D). Analogously, for fair ML, define empirical malfare minimization (EMM), given M.-;w)) Ding and #1:g. with empirical and true optimal models
h = argmin NEW
(i i R(h; 2i): & h" = argminAM R(h; E, E();;,D)); ΔER
Although empirical risk is an unbiased estimate of risk, with Mpp(; for p > 1, empirical malfare is a biased estimator of malfare. Fortunately, empirical malfare is consistent estimator of malfare, and we show that standard tools for bounding the error of ERM can be applied to EMM. Here is necessary to consider not the loss function or hypothesis class in isolation, but their composition
Vh E H (f h)(z, v) = ((y.(xx) & l o H = {e h h E H)
The empirical Rademacher average is well-studied & 18 26 data dependen measurement of the capucity to overfit of a model class w.r.t. loss function defined as
m o, 0 M(:))
Rmm (1 H. 2)
sup hew
m
where d1:m are drawn i.i.d. Rademacher (i.e., uniform on +1), which essentially measures the ability of the hypothesis class to spuriously correlate loss values with noise.
Theorem 3.2 (Generalization Guarantees for Malfare Estimation). Suppose hypothesis class H. C X' > ), bounded loss function É: ()) x )) + r). and per-group samples z; D.m Then, with probability at least over choice of z, holds simultaneously for all fair malfare functions M(::-)
(i.e., (+)))) for 2 1) and probability vectors w R2. that
sup M(1+ R(h; D.); w) -M MM R(; 2:); w) S SM 100(1-200 21 (eo H,,HH, 21) + 3r
lu 2m
RU
keW
5

---

Figure 1: We minimize malfare of a weighted hinge-loss SVM, with g 5 ethnoracial pro- tected groups, listed in the legend with group weight un (population frequency) and class bias b; (proportion with income 2 $50k/yr.). Due to existing societal inequity, class imbal- ance varies widely by group, so we weight risk by +. We report per-group training (dotted)
Per-Group (Race) Weighted Hinge Risk and Malfare Versus y
9.64%
White 85.43% 25, 4%%
Asan-Paa-ls 3.13% 26.9%
Am-ind-Esk 0.96% 11.7%
Other 0.84% 12.3%
Weighted U
and test (dashed) hinge risks, along with the malfare objective (green) of the EMM solution
argmin (i+ b, NEH as functions p E [1,32]. The experimental
RR;;;; Ehinge: 2:); w)
2
B 910
20
30
setup is detailed in uppendix A.1
Molfare Power
The contraction property (theorem 2.4 item 3 of malfare is key to this result, and this property
does not hold for welfare. Strikingly, fair welfare functions (S w) for [0. 1) are Lipschitz- discontinuous; e.g., the Nash social welfare (geometric welfare) (o !) = VII is unstable to perturbations of each S; around 0, which causes great difficulty in sampling- baanndd---eddd- welfare estima- tion. For example, if utility samples are BERNOULLI(g) diittrrbitd for S1, the sample complexity of E-ō estimating Wo w) grows unboundedly w + 0, q + (jointly).
Experimental Validation Figure presents a brief experiment on the lauded adult t dataset, where the task is to predict whether income is above or below $50k/yr. We train Mp(: w)) miinimizing SVM, and find significant risk-variation between groups; generally low risk for the white and Asian groups, and high risk for the native American and other groups. The p = model is a standard weighted SVM. with poor performance for small and traditionally marginalized groups, as expected in an 85.43% majority-white population. As p increases (towards egalitarianism), we observe interesting fairness tradeoffs; training malfare increases monotonically, and in general (but not monotonically:: white and Asian training risks increase, as the remaining risks decrease. At first, most improvement is in the relatively-large (9.64%), high-risk Black group. but for larger p, the much smaller (0.96%) but higher-risk, native American group sharply improves.
Both training and test performance generally improve for high-risk groups, but significant overfitting occurs in small groups and malfare. This unsurprising, since although SVM generalization error is well-understood [see [26] chapter 26], bounds are generally vacuous for tiny subpopulations of 400 individuals. In general, overfitting increases with p. due to the higher relative-importance of small but high-risk groups on h. This experiment validates EMM as a fair-learning technique, with the capacity to specify tradeoffs between majority and marginalized groups, while demonstrating overfitting to fairness, which we formally treat in the sequel. We observe similar fairness tradcoffs in our supplementary experiments (appendix A.2). on weighted and unweighted SVM and logistic regressors with race and sex groups
3.2 Fair Probably Approximately Correct Learning
For context, we first present generalized notion PAC-learnability, which we then generalize to FPAC-learnability. Standard presentations consider only classification under 0-1 loss, but we follow the generalized learning setting of [32), which treats generic learning problems.
Definition 3.3 (PAC-Learaablltty). Suppose hypothesis class sequence Hi S H2 C..., all over X' + V, and loss function é y x y + Ro+. We say H. is PAC-learnable w.r.t. E if there exists a (randomized) algorithm A, such that for all
1. sequence indices d;
3. additive approximation error é > 0; and
2. instance distribution D over X x );;
4. failure probability 8 E 1);
Note that for continuous loss functions and = 2 groups, group training risks are monotonic in as seen in the supplementary sex- sex-based experiments (see appendix A.2

---

A can identify hypothesis h E H, i.e., h < A(D,e, d), such that
1. there exists some sample complexity function m(=, 6, d) (R+ x 1)x + s.t. E consumes no more than m(e, 6, d) samples from 2 (i.e., finite sample complexity); and
2. with probability at least 1 - - (over randomness of A), h obeys
R(h; E, D)
inf : D) + E*
The class of such learning problems is denoted PAC, with membership denoted (H E) E PAC. Furthermore, if for all d. the space of D is restricted such that inf R(h; E, D) = 0, then (H, E) is PealizablePAAC-leanndi written (H, E) E PAC
heH.
We now generalize this concept to fair- learnability. In particular, we replace the univariate risk- minimization task with a multivariate malfare-minimizatio task. Following the theory of section we do not commit to any particular objective, but instead require that FPAC-learner is able to minimize any fair malfare function satisfying the standard axioms. Furthermore, here problem instances grow not just in problem complexity d, but also in the number of groups g.
Definition 3.4 (Fair-PAC (FPAC) Learnability). Suppose hypothesis class sequence H4 S H2 S
C + y, and loss function : y xX 3 - Ro+. We say is fair- Sair-PA--learaale w.r.t E there exists (randomized) algorithm A, such that for all
1. sequence indices d:
4. malfare concepts M satisfying axioms 77-9
y instance distributions Di.g over (X y):;
5. additive approximation errors & 0; and
3. probability vectors w E R
6. failure probabilities & E (0, 1);
A can identify hypothesis h H.e. h A(Di.g. w, M, 6, d), such that
1. there exists some sample complexity function m(c, 5, d. (I&+ (0, 1) N x N) - N s.t.
A(D 1:g> w, M, E, 8, d) consumes no more than m(e, 8, d, g) samples (finite sample complexity); and with probability at least 8 (over randomness of A). h obeys
M (i + R(h; e, D.); w) & inf M (i H &, +
M*EH
The class of such fair-learning problems is FPAC, with membership denoted (H, E) E FPAC.
Finally, if for all d, the space of D is restricted such that inf max R(h; e, D,) = 0, then (H, is realizable-FPAC FPAC-learablle, written (H. E) E FPACO. hEHaiEl.....
Observation 3.5 (Malfare Functions and Special Cases). By assumption, M(::)) must be (:-):) for some p E [1, 30). Taking g = implies w = (1), and M,(Sww) S1, thus reducing the problem to standard PAC-learning. Similarly, taking p 1 converts the problem to weighted loss minimization (weights determined by w), and p = oo yields minimax optimization problem, where the max over groups, commonly encountered in adversarial and robust learning settings.
On Computational Efficiency Some authors consider not just the statistical but also the com- putational performance of learning, generally requiring that A have polynomial time complexity (and thus implicitly sample complexity). In other words, they require that A(D, e, 6, d) terminates in m(e, 5, d) E Poly L 3. d) steps. A similar concept of polynomial-time FPAC-learnability is equally interesting, where here we assume A(D1gg w, M,&, E, 6, d) may be computed by a Turing machine (with access to sampling and entropy oracles) in m[s, 6, d. these concepts PACrayy PAC FPACraly- and FPAC Poly"
Poly 3. d. steps. We denote
Observation 3.6 (FPAC-Learnability and Weighted Loss Functions). Per-group weighted-loss functions are a well-studied object in the fairness literature, representing the idea that different types of incorrect undesirable outcome can impact different groups in different ways It is not immediately obvious that the FPAC framework covers this case, however observe that it is compatible with weighted loss functions, where the weighting associated with each individual sample, as this is just a particular choice of loss function. This is actually a much more general case, but since UPAC-learnaillity requires uniform learnability over all distributions, this also includes distributions where per-group weightings are constant.
'The experiments of section 3.1 represent special case of this, wherein incorrect classifications dispropor- tionately impact marginalized groups, who already have disproportionately many low-income members.
7

---

We also observe (immediately from definitions 3.3 and 3.4 that PAC-Iearning is a special case of FPAC-learnin; particular, taking 9 implies Mr(() Mi(S) Si, thus malfare- minimization coincides with risk minimization. The more interesting question, which we seek to answer in the remainder of this document, is when and whether the converse holds. Furthermore, when possible, we would like to show practical constructive reductions.
We now show that in the realizable case, PAC-learnability implies FPAC-learnabilityy via construc- tive polynomial-timg reduction. Our reduction simply takes a sufficiently number of samples from the uniform mixture distribution over all g groups, and PAC-learns on this distribution. As the reduction is constructive (and preeeccyrr.s..,ng) this gives us generic algorithms for (efficient) realizable FPAC-leaming in terms of algorithms for realizable PAC-learning.
Theorem 3.7 (Realizable Reductions). Suppose loss function l and hypothesis class H. Then 1. (H, PHAC EH, FPAC"; and
2. (H, E E
(),
We construct a(n) (efficient) FPAC-learner for (H, E) by noting that there exists some A' with sample-complextty (E, 5, d) and time complexity (E, to PAC-learn (H, E). and taking A(D w, M, E. 6, d) ('mmix(D (rixx(D1:)))) 1:0)). g. 8, d), where (i:g)) denotes the uniformly-weighter igg Then A FPAC-learns (H. f), with sample-complexit ma(s, 6, d. g)
mixture of distributions Di.g
m g. 5, d), and time-complexity ta 5, d. g) ( 6, d.
Unfortunately, the argument here strongly depends the properties of realizability, and does not extend to the agnostic case. Furthermore, we note that, philosophically speaking, realizable FPAC learning is rather uninteresting, essentially because in world where all parties may be satisfied completely, the obvious solution to do so. Thus nontrivial unfairness and bias issues logically only arise in a world of conflict, e.g., in zero-sum or eesource-constrainng settings, which foster competition between groups. We henceforth focus our efforts on the more interesting agnostic-learning setting.
3.3 Characterizing Fair Statistical Learnability with FPAC-Learners
We first consider only questions of statistical learning, i.e., we ignore computation and show that there exist FPAC-learning algorithms. In particular, we show a generalization of the fundamental theorem of statistical learning to fair learning problems. The aforementioned result relates uniform convergence and PAC-learnability and is generally stated for binary classification only. We define a natural generalization of uniform convergence to arbitrary learning problems within our framework, and then show conditions under which a generalized fundamental theorem of (fair) statistical learning holds. In particular, we show that, neglecting computational concerns, PAC-learnability and FPAC learnability are equivalent for learning problems with a particular no-free-lunch guarantee.
We first define generalized notion of uniform convergence. In particular, definition applies to any bounded loss function, thus greatly generalizes the standard notion for binary classification.
Definition 3.8 (Uniform Convergence). Suppose é y y - [0, r] and hypothesis class H. X +
y. We say (H, () E iC
R(,; RR(;; e, D) =0 bEA
E 170 aver X'x Zm
lim
sup
sup
We stress that this definition is both uniform over l composed with the hypothesis class H and uniform over all possible distributions D. Standard uniform convergence definitions consider only the convergence of empirical frequencies of events to their true frequencies, whereas we generalize to consider uniform convergence of the empirical means of functions to their expected values. also helpful to consider the sample complexity of E-Ō uniform-convergent converggece,, where we take
muc(t o H, e, 8) = argmin
sup
P sup MEH
El a h] - É [e z~D
>
2 s0)
D over Xxx
ie., the minimum sufficient sample size to ensure E-ō uniform- converrnccn over the loss family o H. For classification, uniform convergence bijectively implies PAC-learnability follows.
Theorem 3.9 (Fundamental Theorem of Statistical Learning 26 theorem 6.2]). Suppose is the 0-1
loss. Then the following are equivalent:
1. Vd e N: Hy has finite Vapnik- Chenii-Chervonenkis (VC) dimension B3

---

Uniform Convergence
is 0-1 Loss
TC(2)
::SS00Sc2R VC(H) < x0
PAC(E) ERM
FPAC(() EMM
Assumption
Agnostic Learning
PAC(E)
FPAC(E)
(E ERM
(E) EMM
Realizable Learning
PAC
(E)
PAC Learning
FPAC Learning
Figure 2: Implications between membership in PAC and FPAC classes. For arbitrary fixed f. denotes implication of membership of some H (i.e., containment); see theorems 3.7 and 3.10 and = = holds conditionally on f. Note that when the assumption on (see theorem 3.10 holds, the hierarchy collapses, and general, under realizability, some classes are known to coincide.
2. Ad E N: (e, Ha) has the uniform convergence property.
3. Any ERM rule successful agnostic-PAC learner for H. thus H. is agnostic-PAC learnable. Any ERM rule a successful realizable- PPC learner for H. thus H. is realizable-PACC learnable.
It is rather subtle to generalize this result beyond classification, as there PAC-learnable problems for which uniform convergence does not hold. However, 1 show similar results for various regression problems, and we now generalize FPAC learning (summarized in figure 2
Theorem 3.10 (Fundamental Theorem of Fair Statistical Learning). Suppose l such that 4H (H, E) E PAC = (H, () E UC. Then AH. the following are equivalent:
1. Ad E N: (e, Ha) has the generalized uniform convergence property.
Any EMM rule is an agnostic-FPP FPAC learner for (f. H). thus (e, H.) is agnostic-FPAC learnable.
3. Any EMM rule is realizable-FPAC learner for (E, H), thus (e, H) is realizable-FPACC learnable.
3.4 Characterizing Computational Learnability with Efficient FPAC Learners
In this section, we consider the more granular question of whether FPAC learning is computationally harder than PAC learning. In other words, where previously we showed conditions under which PAC FPAC, here we focus on the subset of models with polynomial time training-efficiene guarantees, i.e., PACpoly FPACPaly- Theorem 3.7 has already characterized the computational complexity of realizable FPAC-learingg so we now focus on the agnostic case. Here we show neither generic reduction, nor non-constructive proof that PACpoly FPACpoly. nor do show counterexample, but rather we show that under standard convexity conditions often leveraged as sufficient for efficient PAC-learning, too is efficient FPAC-learning possible.
Here we show concretely and constructively the existence of FPAC-learners under standard convex optimization assumptions via the projected subgradient method [27]. This result is immediately practical, and can be applied verbatim to problems like generulized linear models (20) and many kernel methods.
Theorem 3.11 (Efficient FPAC Learning via Convex Optimization). Suppose each hypothesis space H. E H. is indexed by O₂ C Poly(d), ie.. Ha (h(::0) | E @a). s.t. (Euclidean) (Oa) Poly(d), and Va E X E Oa, h(z; 0) can be evaluated in Poly(d) time, and Ō E Polly(d) can be Euclidean-projected onto Oa in Poly(d) time. Suppose also & such that VX E X.y E E >> l(y, hu, 0)) a corvex function, and suppose Lipschitz constants de, AN (oly(d) and some norm Ilyly over y s.t. lis - Lipsshhitz in 9. ie.,
Yy, V. y [(y. ú) ely, 5') de beli &'lly

---

Algorithm Approximate Empirical Malfare Minimization via the Projected Subgradient Method
1: procedure (f H. Oo, muc(:;), ") Di:g, w. M(;-),e,
2: input: Xy-Liischitz loss function f. >x-LLipschitz hypothesis class H with parameter space θ s.t. & o H is convex, initial guess Oo E O, uniform-convergence sample-complexity bound muc(;, -) group distributions Di:g. group weights w E 1R.. malfare function M(;:)), and additive enrrr guarantee 5-8
3: output: (-----(--)--piii >optimal h E H
4: ma mcc(3 3. )); 1:m D .... A Draw sufficient sample for each group
5: n 1+ (DDiam())Aerr :a0 ved
Diam(
Di Set iteration count n and learning rate a > Define empirical malfare objective Run PSG algorithm empirical malfare Return s-ô optimal model
6: f(0) : + Ro+ Mii + R(h(-;0); (;
7: 0 < PROJECTEDSUUBRRADDENNT f, O 60.
8: return h(:0)
9: end procedure
and also that each Ha is -ly-llllllly--iischht in 0, i.e.,
Yx E X. 0. o' E O2: |l,(2; 0) h(x; S dze 10|10- -0')
Finally, assume 8o Ha exhibits E-Ō uniform convergence with sample complexity muc(s, 6, d) e ( 1. d). It then holds that, for arbitrary initial guess Og E Oa. for any group distributions Di:g- group weights and fair malfare function M(;)), the algorithm (see algorithm
A(Digg M(x)))) E, = Apso (e, Ha. Go muc(-;;d)) Disg. w, M(:-),,,
FPAC-leams (H, E) with sample complexity m(e, 5, d,g) 9 muc(s ( 8 d), and (training) time- 1 complexity E Poly( go 8: d, g). thus (H, E FPACpoly
4
Conclusion
This paper introduces malfare minimization as a fair learning task, which we argue is better aligned to address ML tasks cast as loss minimization than is welfare. We then show statistical and computational relationships between malfare and risk minimization. We do not claim that malfare a better or more useful concept than welfare; rather only that it is significantly different, enjoys equivalent axiomatic footing, and stands to reason that the right tool (malfare) should used for the task (fair risk minimization).. We acknowledge that some learning tasks, e.g., bandit problems and reinforcement learning tasks, are more naturally phrased as maximizing utility or (discounted) reward, however, most supervised learning problems are naturally cast minimizing nonnegative loss functions.
We are highly interested in exploring a parallel theory fair welfare maxinization, however some key malfare properties do not hold for welfare. In particular, non-Lipschitz welfare functions, i.e., W Wx(+)) for p [0, 1), create great statistical and computational challenges in learning. For this reason, straightforward translation of our FPAC framework into a welfare setting is rather vacuous. In contrast, the contraction property (theorem 2.4 itfmmtmm] 3 of malfare leads to uniform sample complexity bounds, which are crucial to FPAC-learning. It thus seems that similar bounds for welfare would need either to either impose additional assumptions to avoid non- Lipschitz behavior (c.g.. artificially limit the permitted range of p), otherwise provide weaker (non-unifoni learning guarantees.
As FPAC learning generalizes PAC learning, known hardness reductions and lower-bounds apply, thus the interesting risk minimization. Theorem 3.7 answers this question in the negative under realizability. as does theorem 3.10 for sample complexity in the general (agnostic) case, under appropriate conditions on the loss function. The remaining cases are left open, though section 3..4 shows that convexity conditions sufficient for efficient PAC-learnabilityy are also sufficient for efficient FPAC-learnability.. We hope that deeper inquiry into these questions will lead both a better understanding of what and is not FPAC-Icarnabe as well as more practical and efficient reductions and FPAC-Icareed
question is whether malfare minimization is harder than
10

---

Acknowledgments
The author graciously acknowledges NSF grant RI-1813444 and DARPA/AFRL grant FA8750 for funding this work in part. The author also wishes to thank Cristina Menghini for her assistance with the experimental code, and Eli Upfal for insightful discussion regarding the intricacies generalized PAC-learnability concept.
References
[1] Noga Alon, Shai Ben- Ben-David, Nicolo Cesa- Dasa-Bianchi, and David Haussler, Scale-sensitive di- mensions, uniform convergence, and learnability. Journal of the ACM (JACM), 44(4):615-631, 1997.
[2] Ahmed Ashraf, Shehroz Khan, Nikhil Bhagwat, Mallar Chakravarty, and Babak Taati. Learning to unlearn: Building immunity to dataset bias in medical imaging studies. arXiv preprint wiXiv:1812.01766 2018.
[3] Avrim Blum and Thodoris Lykouris. Advancing subgroup faimesss via sleeping experts. In Innovations in Theoretical Computer Science Conference (ITCS), volume 11, 2020.
[4] Peter S Bullen. Handbook of means and their inequalities, volume 560. Springer Science & Business Media, 2013.
[5] Joy Buolamwini and Timnit Gebru. Gender shades: commercial gender classification. In Conference on fairness, accountability and transparency. pages 77-91. PMLR, 2018.
Intersectional accuracy disparities in
[6] Jacqueline G Cavazos, P Jonathon Phillips, Carlos D Castillo, and Alice J O'Toole. Accuracy comparison across face recognition algorithms: Where are we on measuring race bias? IFFE Transactions on Biometrics, Behavior, and Identity Science, 2020.
[7] Cynthia M Cook, John J Howard, Yevgeniy B Sirotin, Jerry L Tipton, and Arun R Vemury. Demographic effects facial recognition and their dependence on image acquisition: An evaluation of eleven commercial systems. IEEE Transactions Biometrics, Behavior and Identity Science, 1(1):32-41, 2019.
[8] Cyrus Cousins and Matteo Riondato. Sharp uniform convergence bounds through empirical centralization. Advances in Neural Information Processing Systems, 33, 2020.
[9] Hugh Dalton. The measurement of the inequality of incomes. The Economic Journal, 30(1 19): 348-361, 1920.
[10] Gerard Debreu. Topological methods in cardinal utility theory. 1959.
[11] Dheeru Dua and Casey Graff. UCI machine learning repository, 2021. URL http::////arciv
ics. uci, edu/ml
[12] William M Gorman. The structure of utility functions. The Review of Economic Studies, 35(4): 367-390, 1968.
[13] Hoda Heidari, Claudio Ferrari, Krishna Gummadi, and Andreas Krause. Fairness behind veil of ignorance: welfare analysis for automated decision making. In Advances in Neural Information Processing Systems, pages 1265-1276, 2018.
[14] Lily Hu and Yiling Chen. Fair classification and social welfare. In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, pages 535-545, 2020.
[15] Maximilian Kasy and Rediet Abebe, Fairness, equality, and power in algorithmic decision- making. In Proceedings of the 2021 ACM Conference Fairness, Accountability, and Trans- parency, pages 576-586, 2021.
[16] Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In 8th Innovations Theoretical Computer Science Conference (ITCS 2017), volume 67, page 43. Schloß Lngstuhl-LeibnizzZentiee für Informatik, 2017.
[17] Brian Mac Namee, Padraig Cunningham, Stephen Byrne, and Owen Corrigan. The problem of bias training data in regression problems in medical decision support. Artificial intelligence in medicine, 24(1):51-70, 2002.

---

[18] Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and proba-
bilistic techniques algorithms and data analysis. Cambridge university press, second edition. 2017.
[19] Hervé Moulin. Fair division and collective welfare. MIT Press, 2004.
[20] John Ashworth Nelder and Robert WM Wedderbumn. Generalized linear models. Journal of the
Royal Statistical Society: Series A (General), 135(3):370-384 1972.
[21] Arthur Cecil Pigou. Wealth and welfare. Macmillan and Company, limited, 1912.
[22] Kevin WS Roberts. Interpersonal comparability and social choice theory. The Review of Economic Studies, pages 421-439, 1980.
[23] Esther Rolf, Max Simchowitz, Sarah Dean, Lydia T Liu, Daniel Björkegren, Moritz Hardt, and Joshua Blumenstock. Balancing competing objectives with noisy data: Score-based classifiers for welfare-awart machine learning. In Proceedings of the 37th International Conference Machine Learning. JCML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 8158-8888 -168..68... PMLR, 2020.
[24] Guy N Rothblum and Gal Yona. Multi-group agnostic PAC learnability. In Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9107-9115. PMLR, 2021.
[25] Amartya Sen. On weights and measures: Informational constraints in social welfare analysis.
Econometrica: Journal of the Econometric Society, pages 1539-1572, 1977.
[26] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014.
[27] Naum Zuselevich Shor. Minimization methods for non-differentiable functions, volume 3.
Springer Science Business Media, 2012.
[28] Umer Siddique. Paul Weng, and Matthieu Zimmer. Learning fair policies in multi-objective (deep) reinforcement learning with average and discounted rewards. In International Conference on Machine Learning, pages 8905-8915. PMLR, 2020.
[29] Till Speicher, Hoda Heidari, Nina Grgié- Krishna P Gummadi, Adish Singla, Adrian Weller, and Muhammad Bital Zafar. A unified approach to quantifying algorithmic unfairness: Measuring individual & group unfairness via inequality indices. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2239-2248, 2018.
[30] Philip S Thomas, Bruno Castro da Silva, Andrew G Barto, Stephen Giguere, Yuriy Brun, and Emma Brunskill. Preventing undesirable behavior of intelligent machines. Science, 366(6468): 999-1004, 2019.
[31] Leslie G Valiant. A theory of the learnable. Communications of the ACM, 27411)1134--114 1984.
[32] Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 2013.
[33] Vladimir Vapnik and Aleksei Chervonenkis. The uniform convergence of frequencies of the appearance of events their probabilities. In Doklady Akademii Nauk, volume 181, pages 781-783. Russian Academy of Sciences, 1968.
[34] Vladimir Vapnik and Aleksei Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264-28) 1971.
12


Reviews:
[{"review_id": "yinhutfk-WM", "reviewer": "Reviewer_VZaR", "summary": "The authors consider malfaire metrics,\nmeasuring overall societal harm, with axiomatic justification via\nstandard axioms of welfare, and cast fair ML as malfare minimization\nover the risk values (expected losses) of each group. this is not \nequivalent to simply defining utility as negative loss and maximizing welfare.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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 paper tells us that malfare metrics have different properties to welfare \nmetrics and there may be applications where minimizing malfare is possible \nbut maximising welfare is not. I am not sure whether this is common \nor whether it just occurs for pathological situations. Nevertheless, \nit does seem important to know this. It would be useful (if possible) to give a \nbrief mathematical explanation for the difference between welfare and malfare.\nIs the only important difference possible Lipschitz-discontinuity or are there\nothers?\n\nResults concerning PAC learning are generalised to the case of \nF(for fair)PAC learning (which takes into account malfare).\nThis is clearly solid work backed up by proofs in the supplementary material.\n\nI just have one serious niggling doubt: axiom 6 is presented without any \nobvious justification. All other axioms have appropriate citations showing that \nthey are standard (or at least have been previously proposed). \nAxiom 6 is essential to show that the malfare function must be a power means function. \n(One could also probably find applications where some of the other axioms \nmaybe do not apply, but they do seem to be less contentious\nthan axiom 6). Axiom 6 is a strengthening of a traditional cardinal welfare axiom,\nbut is this strengthening really justified?\n\nFigure 1: Is there a simple summary of what this figure is telling us? \nI think that results improve (in terms of fairness) as p increases, but the \nimportant question is why? Is there a one-line explanation for this?\n\nline 320: This is a \"generalisation\" in the sense that the definition is slacker, \nwhich is not necessarily a good thing: the mean may converge when the frequency does not.\nIs this a possibly important difference or not? In Theorem 3.9 you mean generalised UC\nnot UC, so don't put parentheses around \"generalised\".\n\nMinor points:\n- In certain figs (in the supplementary material), eg race-01, \nthe y-axis has 1 several times which is clearly a typo.\n- line 105: write pre-existing instead of preëxisting\n- line 163: multiplicative linearity is axiom 6 in your list, not 5.\n- line 164: typo?: \"nats or of cross-entropy loss\"\n- line 167: \"milquetoast\" seems to be an inappropriate adjective. Perhaps 'weak' would be better.\n- Figure 1 (legend): what happens if b_i is close to 0?\n- Def. 3.3 use words instead of \\forall, \\exists\n- line 279: acronym Agn not defined.\n- line 291: careful with line numbers in middle of lines\n- Def. 3.7 perhaps give a reference for Uniform Convergence.\n- Fig. 2: what do dashed implications mean?", "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": "5"}, "extra_text": {}}, {"review_id": "c38FV2rG4Ky", "reviewer": "Reviewer_vUPX", "summary": "This paper investigates an important challenge in welfare-centric fair ML, that is, how to connect the standard loss minimization view of ML with the utility maximization view of welfare-based fairness. The authors define malfare to measure societal harm: malfare is a complementary metric of welfare, and it is justified with axioms of cardinal welfare (and extensions to malfare). Utilizing the malfare metric, the authors cast fair ML that seeks equitable risk distribution to groups as malfare minimization over the expected losses of all groups. They further build up on the malfare minimization framework to extend PAC learning to fair-PAC (FPAC) learning, which is proposed as a formal notion of fair learnability. Their analysis of FPAC learning shows that standard PAC-learners may be converted to FPAC-learners under some conditions, and these connections further yield theoretical results on the statistical and computational learnability with FPAC learners.", "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": "This paper studies a new problem in fair machine learning. The adopted methodology is a novel combination of the cardinal welfare theory from economics, welfare-centric methods in fair ML and the well-established PAC learning theory. In my opinion, the results are significant as they fill important theoretical gaps in fair ML. The paper focuses on welfare-centric fair ML, which is a relatively new thread of fair ML that uses a social welfare function to represent fairness. Compared to the dominant parity based fairness notions used in ML, the welfare-centric view could provide a broader perspective on fairness driven by the well-beings of stakeholders and represent a wide range of principled fairness concepts. In existing literature, these potential advantages tend to be undermined by the lack of theoretical justification from the learning aspect, that is, there are no general learning performance guarantees on welfare-centric fair ML. This paper contributes FPAC learning as one possible framework to offer solid theoretical justifications, thus, in my opinion, greatly expands the potentials of welfare-metric fair ML.\n\nThe paper is well organized and clearly written. The authors provide sufficient introduction of the background and motivations of their task by citing related works. They also gave clear explanations of what distinguish the work from previous research. The presented technical results are solid, and the proofs and derivations are correct as far as I could verify. \n\nI find the paper well written for the most part, and I only have a few minor questions and suggestions.\n1. From my understanding, the power mean formulation puts welfare and malfare on a spectrum from equality to inequality controlled by the power $p$. Do the authors think it is reasonable to interpret malfare as inequality measure? If so, I think it might be interesting to compare the FPAC framework or Empirical malfare minimization (EMM) with the results in [24]. On a related note, a potential reference to include is ‘An Axiomatic Theory of Fairness in Network Resource Allocation’ by Lan et al.: this paper adopts a similar axiomatic view on fairness and derive a mean-type format for fairness measures; if I recall correctly, the axioms they consider coincide with Axiom 1-5 used in the submission.\n2. In the appendix of [11], the authors discussed a mapping between loss minimization to social welfare maximization. Although their welfare function definition is different from the one used in the submission, I think it is worth mentioning this result in the ‘Related work’.\n3. The authors highlighted that EMM is more fitting in ML contexts since there often is no clearly neutral way to define utility based on loss. While I agree with this statement, I think in many cases the decision makers designing the learning task would have the expertise or authority to know what utility functions to consider. Certainly the utility definitions could be context dependent, but one may argue that it is desirably so to capture context-specific welfare considerations. Can the authors include brief examples of when utility definitions would be hard to define? \n4. Can the authors provide some intuition on which of the welfare/malfare axioms and welfare/malfare function properties appear to be indispensable for developing the theoretically sound FPAC learning framework? Along similar line, how hard will it be to extend the analysis to other welfare measures?\n\nMinor comments:\n1. Figure 1: the test hinge risk is shown as higher than the training hinge risk reversed pattern for the ‘Black’ group, while the other groups all have the reverse pattern. Is this figure correct?\n2. Theorem 2.5 Condition 2: is the summation term $\\sum_{i=1}^g f_p(\\mathcal{S}_i)$ missing the weight vector?\n3. Appendix proof of Theorem 2.4: line 558 and 559, convexity and concavity appear to be mixed up. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors acknowledged the limitations of their work in several aspects, such as the condition needed to prove Theorem 3.9, the difficulty in extending the analysis to fair welfare maximization. I think the limitations are adequately discussed, and as these limitations are non-trivial to address, it is reasonable to leave as future work as indicated by the authors. \n\nAs the paper studies fair ML, it naturally seeks to address potential negative societal impacts of ML. One aspect that may be useful to discuss is the welfare implication of EMM in practice. The authors state that EMM should be used when there is no explicit way to convert loss to utility, nevertheless, one may still wonder how the learner trained with EMM performs with respect to different utility definitions. For instance, if the predictions about whether income is above or below $50k per year are used to guide certain decisions, equitable risk distribution in the predictor does not necessarily guarantee desirable utility distribution in these decisions. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Pui34HrDrX", "reviewer": "Reviewer_aRtP", "summary": "The paper follows the axioms of cardinal welfare, in conjunction with an introduced notion of malfare which quantifies the amount of societal harm rather than welfare which quantifies overall benefit. This allows the authors to cast fair machine learning problems as risk minimization problems, where they aim to minimize the malfare function. The function, which follows the set of axioms, is a power mean function, defined over the set of groups of interest, weighing the loss on each, to output a combined, single, value. Casting the function as malfare allows them in turn to use a specific characteristic of the proposed formulation – contraction – which is crucial in establishing their generalization result, through bounding the values of the base loss function, and the use of Rademacher complexity. Finally, they show that for their notion of fair learning through the malfare function, in the agnostic case and under standard convex optimization assumptions, it is possible to efficiently learn through the subgradient method. The authors also perform an experimental evaluation of their suggested approach on the adult dataset.", "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": "I think that the paper does a nice job of formalizing and reasoning for the fairness objective they advocate for, and further – by showing that their formulation allows for generalization through the contraction property, which I thought was a nice observation. In terms of practicality, I think the proposed approach makes a good contribution for cases where we believe fairness should be measured in terms of accuracy in the different groups. In such cases, the algorithm they propose should be considered as one alternative in the fairness toolkit. In terms of overall novelty, my assessment is that the paper makes a moderate contribution. I think that the main theoretical contribution is through the observation that certain loss aggregation functions may allow for generalization using the contraction attribute, which leads to uniform sample complexity bounds. \n\nA main weakness that I see in the approach is that it weighs loss, in its general form, over the different groups. We have already seen that in many of the settings where fairness is a concern, false positives and false negatives can have entirely different effects on the individual (beneficial or detrimental), thus bundling them together and minimizing the overall loss may possibly result in an accumulation of mistakes of different types on different groups, which by itself may be problematic.\n\nThe presentation of the paper can be slightly improved, especially section 2, where the flow I thought was a bit confusing.\nThe submission appears to be technically sound, although I have only glanced at proofs in the appendix. The paper cites most of the relevant prior work, but could add a short discussion regarding existing group-based fairness techniques. \n\nQuestions to authors:\n1. Can the suggested approach be extended to also take into account the types of losses (false positives, false negatives)? How would your approach handle cases where the two types of losses have very different implications?\n2. Assuming access to an oracle for standard 0-1 ERM in the agnostic case, would it be possible to harness this “building block” to optimize for your proposed malfare objective?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe that the authors have addressed the limitations of their work properly. I would appreciate further discussion regarding their suggested objective of fairness and in which cases the authors think it should be used.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "7F5_tGzSKlc", "reviewer": "Reviewer_Wv61", "summary": "The paper is concerned with welfare-theoretic fair machine learning. Instead of enforcing statistical parity as a constraint, the paper instead casts fair learning as malfare minimization. Based on the axioms of cardinal welfarism, axioms for malfare are defined. Theoretical guarantees based on learning theory are established for malfare minimization. ", "questions": "", "limitations": "", "rating": 7, "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": "-I think the paper addresses an important topic and the way it casts fair machine learning is interesting and important. \n\n-I did not find the paper easy to read and it felt that too many results were packed in a limited number of pages. \n\n-It seems more natural to show that the axioms imply Th 2.5 then introduce definition 2.3 for the power mean. \n\n-Line 129: doesn't axiom 6 imply 5. \n\n-Axiom 4 (Def 2.2): the symbols should have some explanation. \n\n-Def 2.3: I think there is a typo for M_{\\infty} , it should be S_i not S_g also brackets for the set. \n\n-The paper mentions that we cannot simply define utility as negative loss, but I did not find a strong argument in the paper against that. Why can't a naive transformation that shifts the utility to positive values work? \n\n-The  sentiment vector at the end takes only a fixed form which is the risk for each population. I assume that it not  possible to use learning theory guarantees without the sentiment taking on this form. But isn't there now a loss of generality to the formulation, couldn't different groups have different ways for evaluating sentiment just the way two individuals assign a different utility to the same item? \n\n-I think the representation would improve if at least in the main body, the brief (informal) statements of theorem are given instead. \n\n-I think the simplex notation is usually used for probability vectors, so w \\in \\Delta^{g-1}\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the impacts were adequately discussed. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers’ overall assessment of the paper was that (a) it proposes an interesting, relatively well-justified formulation of fairness through the concept of malware minimization. (2) The ensuing learnability analysis is non-trivial and the proposed algorithms can be practically informative.  Reviewers made several suggestions to the authors to improve the flow and exposition (in particular, it is important that the authors expand their discussion of the proposed axioms, in particular, axiom 6, in the main body of the paper). Assuming that the authors will reflect those changes in their next revision of the paper, I recommend acceptance.
Decision: Accept (Poster)