An Axiomatic Theory of Provably-Fair Welfare-Centric Machine Learning
Year: 2022

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.

heading: 1 Introduction
text: 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–7], in medical settings [2, 17], and many others. This exacerbates existing inequality, as facial recognition in policing yields disproportionate false-arrest rates, and medical ML yields disproportionate health outcomes. Welfarecentric ML methods encode both accuracy and fairness in a welfare function defined on a set of groups, and optimize or constrain welfare to 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-upon welfare function. Unfortunately, welfare metrics require a notion of (positive) utility, and we argue that this is not natural to many ML tasks, wherein we instead minimize some negatively connoted loss value. We thus define a complementary measure to welfare, which we term malfare, measuring societal harm (rather than wellbeing). In 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 (NeurIPS 2021).
Perhaps surprisingly, minimizing a malfare function is not equivalent to maximizing some welfare function while taking utility to be 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 it 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 function defined on 1-0 gain.
Building upon these concepts, we develop a generic notion of fair ML, termed fair-PAC (FPAC) learning, where the goal is to learn models for which finite training samples may guarantee (additively) ε-optimal malfare, with probability at least 1− δ, for any (axiomatically justified) malfare concept. This definition extends Valiant’s [31] classic PAC-learning formalization, and we show that, with appropriate modifications, many (standard) PAC-learners 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 convex optimization under standard assumptions, then training ε-δ malfare-optimal models, like training risk-optimal models, requires polynomial time. We briefly summarize our contributions below.
1. We derive in section 2 the malfare concept, extending welfare to measure negatively-connoted attributes, and show that malfare-minimization naturally generalizes risk-minimization to produce fairness-sensitive ML 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 a 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.

heading: 1.1 Related Work
text: Constraint-based 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 fairness at odds, where additional tolerance parameters are required to strike a balance between the two. Furthermore, recent works [14, 15] 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 fairnessconcepts, wherein both accuracy and fairness are encoded in a welfare function defined on a group of subpopulations. Welfare is then directly optimized [14, 23, 28] or constrained [13, 29] to promote fair learning 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 is an effective strategy when an appropriate and natural measure of utility is available, but in ML 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 fairness issues with an axiomatically-justified 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” [3, 24], also considers per-group risk values, but there regret (maximum relative dissatisfaction), rather than malfare, is minimized.

heading: 2 Aggregating Sentiment within Populations
text: A generic aggregator function M(S;w) summarizes some sentiment vector S ∈ Rg0+, across a population of g groups, weighted by a probability vector w ∈ Rg+ s.t.‖w‖1 = 1. When S measures a desirable quantity, generally termed utility, the aggregator function is a measure of cardinal welfare [19], 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 justification 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 a population, given sentiment vector S and probability vector w. If S denotes a desirable quantity (e.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 W (S;w).
For now, think of the term aggregator function as signifying that an 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 Si). As we introduce axioms and show consequent properties, the appropriateness of the term shall become more apparent. We use the term sentiment to refer to S with neutral connotation, but when discussing welfare or malfare, we 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 on utility values and risk values are mathematically 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 W (S;w) is W (inverted W), to emphasize its inverted nature.

heading: 2.1 Axioms of Cardinal Welfare and Malfare
text: Definition 2.2 (Axioms of Cardinal Welfare and Malfare). We define the aggregator-function axioms for aggregator function M(S;w) below. For each item, assume (if necessary) that the axiom applies ∀S,S ′ ∈ Rg0+, scalars α, β ∈ R0+, and probability vector w ∈ R g +. 1. Strict Monotonicity: S ′ 6= 0 =⇒ M(S;w) < M(S + S ′;w). 2. Weighted Symmetry:1 Suppose S ′ ∈ Rg ′
0+ and probability vector w ′ ∈ Rg
′
0+, such that for all u ∈ R0+ it holds ∑ i:Si=uwi = ∑ i:Si=uw ′ i. Then M(S;w) = M(S ′;w′). 3. Continuity: M(S;w) is a continuous function in both S and w. 4. Independence of Unconcerned Agents:
M(〈S1:g−1, α〉;w) ≤ M(〈S ′1:g−1, α〉;w) =⇒ M(〈S1:g−1, β〉;w) ≤ M(〈S ′1:g−1, β〉;w) .
5. Independence of Common Scale: M(S;w) ≤ M(S ′;w) =⇒ M(αS;w) ≤ M(αS ′;w). 6. Multiplicative Linearity: M(αS;w) = αM(S;w). 7. Unit Scale: M(1;w) = M(〈1, . . . , 1〉;w) = 1. 8. Pigou-Dalton Transfer Principle: Suppose µ = w · S = w · S ′, and for all i ∈ {1, . . . , g}:∣∣µ− S ′i∣∣ ≤|µ− Si|. Then W(S ′;w) ≥W(S;w). 9. Negated Pigou-Dalton Transfer Principle: Suppose as in 8, but conclude W (S ′;w) ≤ W (S;w).
We take a moment to comment on each axiom, to preview their purpose and assure the reader of their necessity. Axioms 1-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 a simple strengthening of a traditional cardinal welfare axiom. We will also see that it is essential to show convenient statistical and learnability properties. Axiom 7
1In the unweighted case, it is standard to define symmetry as simply M(S) = M ( π(S) ) for all permutations
π over {1, . . . , g}, but with weightings, the simple extension M(S;w) = M ( π(S);π(w) ) is not quite sufficient. In particular, in this weaker form, nowhere is additive decomposability, wherein a group may be decomposed into multiple groups of the same sentiment value and total weight without impacting the aggregate, codified.
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 “Si is above the population’s welfare” meaningful), and also enabling comparison across populations (i.e., comparing averages rather than sums).
Finally, axiom 8, the Pigou-Dalton transfer principle [9, 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 8-9 specifically for welfare or malfare, respectively, whereas axioms 1-7 apply equally well to both welfare and malfare.
Axioms 1-5, are modified from their standard presentation to include the weighting w, wherein continuity (3) must also hold over w, and weighted symmetry (2) specifies additionally that weight may be transferred between groups with equal sentiment value. Axioms 6-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 9 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 to 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 Mp(·; ·), for any p ∈ R∪±∞, 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 ∈ R∪±∞, sentiment vector S ∈ Rg0+ and probability vector w ∈ Rg+. We then define the p-weighted-power-mean as
Mp(S;w) . = p √√√√ g∑ i=1 wiSpi , M0(S;w) . = exp  g∑ i=1 wi lnSi  , M±∞(S;w) .= ± max i∈1,...,g ±Si ,
where p ∈ {−∞, 0,∞} attain their limits, the minimum, geometric mean, and maximum, respectively.
Theorem 2.4 (Properties of the Power-Mean). Suppose sentiment vectors S,S ′ ∈ Rg0+ and probability vector w ∈ Rg+. The following then hold.
1. Monotonicity: Mp(S;w) is weakly-monotonically-increasing in p. 2. Subadditivity: ∀p ≥ 1 : Mp(S + S ′;w) ≤ Mp(S;w) + Mp(S ′;w). 3. Contraction: ∀p ≥ 1 : ∣∣Mp(S;w)−Mp(S ′;w)∣∣ ≤ Mp(∣∣S − S ′∣∣ ;w) ≤∥∥S − S ′∥∥∞. 4. Curvature: Mp(S;w) is concave in S for p ≤ 1 and convex in S for p ≥ 1.

heading: 2.2 Properties of Welfare and Malfare Functions
text: 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 ∈ Rg0+ and probability vector w ∈ R g +. If M(·; ·) satisfies (subsets of) the aggregator-function axioms (see definition 2.2), then M(·; ·) exhibits the following properties. 1. Identity: Axioms 6-7 imply that ∀α ∈ R0+: M(α1;w) = α. 2. Debreu-Gorman Factorization: Axioms 1-5 imply ∃p ∈ R, strictly-monotonically-increasing continuous F : R→ R0+ s.t.
M(S;w) = F  g∑ i=1 wifp(Si)  , with { p = 0 f0(x) .= ln(x) p 6= 0 fp(x) . = sgn(p)xp .
3. Power-Mean Factorization: Axioms 1-7 imply F (x) = f−1p (x), thus M(S;w) = Mp(S;w). 4. Fair Welfare: Axioms 1-5 and 8 imply p ∈ (−∞, 1]. 5. Fair Malfare: Axioms 1-5 and 9 imply p ∈ [1,∞).
Theorem 2.5 tells us that the mild conditions of axioms 1-5 (generally assumed for welfare), along with 6 (multiplicative linearity), 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-mean is effectively the only reasonable family of welfare or malfare function; even without axiom 6, axioms 1-5 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 i is above (or below) the population’s malfare” meaningful. Finally, we have that Wp(·;w) promotes equitable redistribution of utility for p ≤ 1, and W p(·;w) promotes equitable redistribution of loss for p ≥ 1.

heading: 3 Statistical and Computational Learning-Efficiency Guarantees
text: In this section, we define a formal notion of fair-learnability, termed FPAC-learning, where a loss function and hypothesis class are FPAC-learnable 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 of research on PAC-learning algorithms to be applied to FPAC learning. In particular, 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 Y , and a hypothesis class sequence H = H1,H2, . . . is a nested sequence of hypothesis classes, each mapping X → Y . In other words,H1 ⊆ H2 ⊆ · · · .
For example, linear classifiers naturally form a sequence of families using their dimension as Hd . = { ~x 7→ sgn ( ~x · 〈~w1:d,~0〉 ) ∣∣ ~w ∈ Rd}. The hypothesis class sequence concept allows us to distinguish statistically-easy problems, like learning hyperplanes in finite-dimensional Rd, from statistically-challenging problems, like learning hyperplanes in R∞. It is also used to analyze the computational complexity of learners as d increases.

heading: 3.1 Empirical Malfare Minimization and the Rademacher Average
text: We define the risk of hypothesis h : X → Y w.r.t. loss ` : Y × Y → R+ on distribution D over (X × Y), and the empirical risk on sample z ∈ (X × Y)m, as
R(h; `,D) .= E (x,y)∼D
[ `(y, h(x)) ] & R̂(h; `, z) . = Ê
(x,y)∈z
[ `(y, h(x)) ] ,
respectively. The goal in ML is generally to recover the h∗ that minimizes (true) risk, and empirical risk minimization (ERM) computes ĥ .= argminh∈HR̂(h; `, z) as a proxy for h
∗ .= argminh∈HR(h; `,D). Analogously, for fair ML, we define empirical malfare minimization (EMM), given W (·;w), D1:g , and z1:g , with empirical and true optimal models
ĥ . = argmin
h∈H
W( i 7→ R̂(h; `, zi);w ) & h∗ . = argmin
h∈H
W( i 7→ R(h; `,Di);w ) .
Although empirical risk is an unbiased estimate of risk, with
W
p(·;w) for p > 1, empirical malfare is a biased estimator of malfare. Fortunately, empirical malfare is a consistent estimator of malfare, and we show that standard tools for bounding the error of ERM can be applied to EMM. Here it is necessary to consider not the loss function or hypothesis class in isolation, but their composition ∀h ∈ H : (` ◦ h)(x, y) .= `(y, h(x)) & ` ◦ H .= {` ◦ h |h ∈ H} . The empirical Rademacher average is a well-studied [8, 18, 26] data-dependent measurement of the capacity to overfit of a model classH w.r.t. loss function `, defined as
R̂m(` ◦ H, z) . = E σ [ sup h∈H ∣∣∣∣ 1m m∑ i=1 σi` ( yi, h(xi) )∣∣∣∣ ] ,
where σ1: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 classH ⊆ X → Y , bounded loss function ` : (Y × Y)→ [0, r], and per-group samples zi ∼ Dmi . Then, with probability at least 1−δ over choice of z, it holds simultaneously for all fair malfare functions W
(·; ·) (i.e., W
p(·; ·) for p ≥ 1) and probability vectors w ∈ Rg+, that
sup h∈H
∣∣∣ W(i 7→R(h; `,Di);w)− W(i 7→ R̂(h; `, zi);w)∣∣∣≤ W(i 7→2R̂m(` ◦ H, zi) + 3r√ ln gδ2m ;w) .
Figure 1: We minimize malfare of a weighted
hinge-loss SVM, with g = 5 ethnoracial protected groups, listed in the legend with group weight wi (population frequency) and class bias bi (proportion with income ≥ $50k/yr.). Due to existing societal inequity, class imbalance varies widely by group, so we weight risk by 1bi . We report per-group training (dotted) and test (dashed) hinge risks, along with the malfare objective (green) of the EMM solution ĥ . =argmin
h∈H
W p ( i 7→ 1bi R̂(h; `hinge, zi);w ) ,
as functions of p ∈ [1, 32]. The experimental setup is detailed in appendix A.1.
Per-Group (Race) Weighted Hinge Risk and Malfare Versus p
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 Wp(S;w) for p ∈ [0, 1) are Lipschitzdiscontinuous; e.g., the Nash social welfare (geometric welfare) W0(S; 1g ) = g √∏g i=1Si is unstable to perturbations of each Si around 0, which causes great difficulty in sampling-based welfare estimation. For example, if utility samples are BERNOULLI(q)-distributed for S1, the sample complexity of ε-δ estimating W0(S;w) grows unboundedly as w1 → 0, q → 0 (jointly).
Experimental Validation Figure 1 presents a brief experiment on the lauded adult dataset, where the task is to predict whether income is above or below $50k/yr. We train W
p(·;w)-minimizing 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 = 1 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 monotonically2), 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 is 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 tradeoffs in our supplementary experiments (appendix A.2), on weighted and unweighted SVM and logistic regressors with race and sex groups.

heading: 3.2 Fair Probably Approximately Correct Learning
text: For context, we first present a generalized notion of 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-Learnability). Suppose hypothesis class sequence H1 ⊆ H2 ⊆ . . . , all over X → Y , and loss function ` : Y × Y → R0+. We say H is PAC-learnable w.r.t. ` if there exists a (randomized) algorithm A, such that for all
1. sequence indices d; 2. instance distribution D over X × Y;
3. additive approximation error ε > 0; and 4. failure probability δ ∈ (0, 1);
2Note that for continuous loss functions and g = 2 groups, group training risks are monotonic in p, as seen in the supplementary sex-based experiments (see appendix A.2 ).
A can identify a hypothesis ĥ ∈ H, i.e., ĥ← A(D, ε, δ, d), such that 1. there exists some sample complexity function m(ε, δ, d) : ( R+×(0, 1)×N ) → N s.t.A(D, ε, δ, d) consumes no more than m(ε, δ, d) samples from D (i.e., finite sample complexity); and 2. with probability at least 1− δ (over randomness of A), ĥ obeys
R(ĥ; `,D) ≤ inf h∗∈H
R(h∗; `,D) + ε .
The class of such learning problems is denoted PAC, with membership denoted (H, `) ∈ PAC. Furthermore, if for all d, the space of D is restricted such that inf
h∈Hd R(h; `,D) = 0, then (H, `) is
realizable-PAC-learnable, written (H, `) ∈ PAC0.
We now generalize this concept to fair-PAC learnability. In particular, we replace the univariate riskminimization task with a multivariate malfare-minimization task. Following the theory of section 2.2, we do not commit to any particular objective, but instead require that a 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 H1 ⊆ H2 ⊆ · · · ⊆ X → Y , and loss function ` : Y × Y → R0+. We sayH is fair-PAC-learnable w.r.t. ` if there exists a (randomized) algorithm A, such that for all 1. sequence indices d; 2. g instance distributions D1:g over (X × Y)g; 3. probability vectors w ∈ Rg+; 4. malfare concepts W satisfying axioms 1-7+9; 5. additive approximation errors ε > 0; and 6. failure probabilities δ ∈ (0, 1);
A can identify a hypothesis ĥ ∈ H, i.e., ĥ← A(D1:g,w,
W
, ε, δ, d), such that 1. there exists some sample complexity function m(ε, δ, d, g) : ( R+ × (0, 1) × N × N ) → N s.t. A(D1:g,w, W
, ε, δ, d) consumes no more than m(ε, δ, d, g) samples (finite sample complexity); and 2. with probability at least 1− δ (over randomness of A), ĥ obeys
W( i 7→ R(ĥ; `,Di);w ) ≤ inf h∗∈H W( i 7→ R(h∗; `,Di);w ) + ε .
The class of such fair-learning problems is FPAC, with membership denoted (H, `) ∈ FPAC.
Finally, if for all d, the space of D is restricted such that inf h∈Hd max i∈1,...,g R(h; `,Di) = 0, then (H, `) is realizable-FPAC-learnable, written (H, `) ∈ FPAC0. Observation 3.5 (Malfare Functions and Special Cases). By assumption, W (·; ·) must be W
p(·; ·) for some p ∈ [1,∞). Taking g = 1 implies w = 〈1〉, and W
p(S;w) = 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 =∞ yields a minimax optimization problem, where the max is over groups, as commonly encountered in adversarial and robust learning settings.
On Computational Efficiency Some authors consider not just the statistical but also the computational performance of learning, generally requiring that A have polynomial time complexity (and thus implicitly sample complexity). In other words, they require that A(D, ε, δ, d) terminates in m(ε, δ, d) ∈ Poly( 1ε , 1 δ , d) steps. A similar concept of polynomial-time FPAC-learnability is equally interesting, where here we assume A(D1:g,w, W
, ε, δ, d) may be computed by a Turing machine (with access to sampling and entropy oracles) in m(ε, δ, d, g) ∈ Poly( 1ε , 1 δ , d, g) steps. We denote these concepts PACPoly, PAC 0 Poly, FPACPoly, and FPAC 0 Poly. 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 or undesirable outcome can impact different groups in different ways.3 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 is 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 FPAC-learnability requires uniform learnability over all distributions, this also includes distributions where per-group weightings are constant.
3The experiments of section 3.1 represent a special case of this, wherein incorrect classifications disproportionately impact marginalized groups, who already have disproportionately many low-income members.
We also observe (immediately from definitions 3.3 and 3.4) that PAC-learning is a special case of FPAC-learning; in particular, taking g = 1 implies Mp(S) = M1(S) = S1, thus malfareminimization 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-learnability via a constructive polynomial-time 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 efficiency-preserving), this gives us generic algorithms for (efficient) realizable FPAC-learning in terms of algorithms for realizable PAC-learning. Theorem 3.7 (Realizable Reductions). Suppose loss function ` and hypothesis classH. Then 1. (H, `)∈PAC0 =⇒ (H, `)∈FPAC0; and 2. (H, `)∈PAC0Poly =⇒ (H, `)∈FPAC 0 Poly.
We construct a(n) (efficient) FPAC-learner for (H, `) by noting that there exists some A′ with sample-complexity mA′(ε, δ, d) and time complexity tA′(ε, δ, d) to PAC-learn (H, `), and taking A(D1:g,w, W , ε, δ, d) . = A′(mix(D1:g), εg , δ, d), where mix(D1:g) denotes the uniformly-weighted mixture of distributions D1:g . Then A FPAC-learns (H, `), with sample-complexity mA(ε, δ, d, g) = mA′( ε g , δ, d), and time-complexity tA(ε, δ, d, g) = tA′( ε g , δ, d).
Unfortunately, the argument here strongly depends on 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 a world where all parties may be satisfied completely, the obvious solution is to do so. Thus nontrivial unfairness and bias issues logically only arise in a world of conflict, e.g., in zero-sum or resource-constrained settings, which foster competition between groups. We henceforth focus our efforts on the more interesting agnostic-learning setting.

heading: 3.3 Characterizing Fair Statistical Learnability with FPAC-Learners
text: 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 a generalized notion of uniform convergence. In particular, our 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 classH ⊆ X → Y . We say (H, `) ∈ UC if
lim m→∞ sup D over X×Y E z∼Dm [ sup h∈H ∣∣∣R̂(h; `, z)− R(h; `,D)∣∣∣] = 0 . We stress that this definition is both uniform over ` 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. It is also helpful to consider the sample complexity of ε-δ uniform-convergence, where we take
mUC(` ◦ H, ε, δ) . = argmin { m ∣∣∣ sup D over X×Y P ( sup h∈H ∣∣∣E D [` ◦ h]− Ê z∼Dm [` ◦ h] ∣∣∣ > ε) ≤ δ} ,
i.e., the minimum sufficient sample size to ensure ε-δ uniform-convergence over the loss family ` ◦ H. For classification, uniform convergence bijectively implies PAC-learnability as 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. ∀d ∈ N: Hd has finite Vapnik-Chervonenkis (VC) dimension [33, 34].
2. ∀d ∈ N: (`,Hd) has the uniform convergence property. 3. Any ERM rule is a successful agnostic-PAC learner forH, thusH is agnostic-PAC learnable. 4. Any ERM rule is a successful realizable-PAC learner forH, thusH is realizable-PAC learnable.
It is rather subtle to generalize this result beyond classification, as there are PAC-learnable problems for which uniform convergence does not hold. However, [1] show similar results for various regression problems, and we now generalize to FPAC learning (summarized in figure 2). Theorem 3.10 (Fundamental Theorem of Fair Statistical Learning). Suppose ` such that ∀H : (H, `) ∈ PAC0 =⇒ (H, `) ∈ UC. Then ∀H, the following are equivalent: 1. ∀d ∈ N: (`,Hd) has the generalized uniform convergence property. 2. Any EMM rule is an agnostic-FPAC learner for (`,H), thus (`,H) is agnostic-FPAC learnable. 3. Any EMM rule is a realizable-FPAC learner for (`,H), thus (`,H) is realizable-FPAC learnable.

heading: 3.4 Characterizing Computational Learnability with Efficient FPAC Learners
text: 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-efficiency guarantees, i.e., PACPoly = FPACPoly. Theorem 3.7 has already characterized the computational complexity of realizable FPAC-learning, so we now focus on the agnostic case. Here we show neither a generic reduction, nor a non-constructive proof that PACPoly = FPACPoly, nor do we show a counterexample, but rather we show that under standard convexity conditions often leveraged as sufficient for efficient PAC-learning, so 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 generalized linear models [20] and many kernel methods. Theorem 3.11 (Efficient FPAC Learning via Convex Optimization). Suppose each hypothesis space Hd ∈ H is indexed by Θd ⊆ RPoly(d), i.e., Hd = {h(·; θ) | θ ∈ Θd}, s.t. (Euclidean) Diam(Θd) ∈ Poly(d), and ∀x ∈ X , θ ∈ Θd, h(x; θ) can be evaluated in Poly(d) time, and θ̃ ∈ RPoly(d) can be Euclidean-projected onto Θd in Poly(d) time. Suppose also ` such that ∀x ∈ X , y ∈ Y : θ 7→ `(y, h(x; θ)) is a convex function, and suppose Lipschitz constants λ`, λH ∈ Poly(d) and some norm‖·‖Y over Y s.t. ` is λ`-‖·‖Y -|·|-Lipschitz in ŷ, i.e.,
∀y, ŷ, ŷ′ ∈ Y : ∣∣`(y, ŷ)− `(y, ŷ′)∣∣ ≤ λ`∥∥ŷ − ŷ′∥∥Y ,
Algorithm 1 Approximate Empirical Malfare Minimization via the Projected Subgradient Method 1: procedure APSG(`,H, θ0,mUC(·, ·),D1:g,w, W
(·; ·), ε, δ) 2: input: λ`-Lipschitz loss function `, λH-Lipschitz hypothesis class H with parameter space
Θ s.t. ` ◦ H is convex, initial guess θ0 ∈ Θ, uniform-convergence sample-complexity bound mUC(·, ·), group distributions D1:g, group weights w ∈ Rg+, malfare function W
(·; ·), and additive error guarantee ε-δ
3: output: ε-δ-
W
(·; ·)-optimal ĥ ∈ H 4: mA ← mUC( ε3 , δ g ); z1:g,1:mA ∼ D mA 1 × · · · × DmAg . Draw sufficient sample for each group
5: n← 1 + ( 3 Diam(Θ)λ`λH
ε
)2 ; α← Diam(Θ)
λ`λH √ n
. Set iteration count n and learning rate α
6: f(θ) : Θ 7→ R0+ . = W( i 7→ R̂(h(·; θ); `, zi);w ) . Define empirical malfare objective
7: θ̂ ← PROJECTEDSUBGRADIENT(f,Θ, θ0, n, α) . Run PSG algorithm on empirical malfare 8: return h(·; θ̂) . Return ε-δ optimal model 9: end procedure
and also that eachHd is λH-‖·‖2-‖·‖Y -Lipschitz in θ, i.e.,
∀x ∈ X , θ, θ′ ∈ Θd : ∥∥h(x; θ)− h(x; θ′)∥∥Y ≤ λH∥∥θ − θ′∥∥2 .
Finally, assume ` ◦ Hd exhibits ε-δ uniform convergence with sample complexity mUC(ε, δ, d) ∈ Poly( 1ε , 1 δ , d). It then holds that, for arbitrary initial guess θ0 ∈ Θd, for any group distributions D1:g , group weights w, and fair malfare function W (·; ·), the algorithm (see algorithm 1)
A(D1:g,w,
W (·; ·), ε, δ, d) .= APSG ( `,Hd, θ0,mUC(·, ·, d),D1:g,w, W (·; ·), ε, δ )
FPAC-learns (H, `) with sample complexity m(ε, δ, d, g) = g ·mUC( ε3 , δ g , d), and (training) timecomplexity ∈ Poly( 1ε , 1 δ , d, g), thus (H, `) ∈ FPACPoly.

heading: 4 Conclusion
text: 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 is a better or more useful concept than welfare; rather only that it is significantly different, enjoys equivalent axiomatic footing, and it stands to reason that the right tool (malfare) should be 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 as minimizing nonnegative loss functions.
We are highly interested in exploring a parallel theory of fair welfare maximization, however some key malfare properties do not hold for welfare. In particular, non-Lipschitz welfare functions, i.e., Wp(·; ·) 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 item 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 (e.g., artificially limit the permitted range of p), or otherwise provide weaker (non-uniform) learning guarantees.
As FPAC learning generalizes PAC learning, known hardness reductions and lower-bounds apply, thus the interesting computation-theoretic question is whether malfare minimization is harder than 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-learnability are also sufficient for efficient FPAC-learnability. We hope that deeper inquiry into these questions will lead to both a better understanding of what is and is not FPAC-learnable, as well as more practical and efficient reductions and FPAC-learners.

heading: Acknowledgments
text: 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 of a generalized PAC-learnability concept.

Review summaries:
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.

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. 

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.