# Multicalibrated Regression for Downstream Fairness

Ira Globus-Harris  University of Pennsylvania  Varun Gupta  University of
Pennsylvania  Christopher Jung  Stanford University  Michael Kearns
University of Pennsylvania  Jamie Morgenstern  University of Washington  Aaron
Roth  University of Pennsylvania

###### Abstract

We show how to take a regression function $\hat{f}$ that is appropriately
“multicalibrated” and efficiently post-process it into an approximately error
minimizing classifier satisfying a large variety of fairness constraints. The
post-processing requires no labeled data, and only a modest amount of
unlabeled data and computation. The computational and sample complexity
requirements of computing $\hat{f}$ are comparable to the requirements for
solving a single fair learning task optimally, but it can in fact be used to
solve many different downstream fairness-constrained learning problems
efficiently. Our post-processing method easily handles intersecting groups,
generalizing prior work on post-processing regression functions to satisfy
fairness constraints that only applied to disjoint groups. Our work extends
recent work showing that multicalibrated regression functions are
“omnipredictors” (i.e. can be post-processed to optimally solve unconstrained
ERM problems) to constrained optimization.

##  1 Introduction

The most common technical framing for fair machine learning is as constrained
optimization. The goal is to solve an empirical risk minimization problem over
some class of models $\mathcal{H}$, subject to _fairness constraints_. For
example, we might ask to find the best performing model $h\in\mathcal{H}$ that
equalizes false positive rates, false negative rates, raw error rates, or
positive classification rates across some collection of groups $\mathcal{G}$
(Hardt et al., 2016; Dwork et al., 2012)). For each of these notions of
fairness, there is a continuum of relaxations to consider: rather than asking
that (e.g.) false positive rates be exactly equalized across groups, we could
ask that they deviate by not more than 5%, or 10%, or 15%, etc. Because these
relaxations trade off with model accuracy (tracing out Pareto frontiers), it
is common to explore the entire range of tradeoffs for a particular family of
fairness constraints (see e.g. (Agarwal et al., 2018; Kearns et al., 2018)).

Each of these are distinct problems that seemingly require training fresh
models on the data. And each of these problems can be computationally
expensive to solve: for example, the “reductions” approach of Agarwal et al.
(2018) requires solving roughly $\log|\mathcal{G}|/\epsilon^{2}$ empirical
risk minimization problems over $\mathcal{H}$ to produce an
$\epsilon$-approximately optimal solution to any one of them, and the
computations cannot be reused. Our goal is to understand when we can pre-
compute a single regression model $\hat{f}$ which is sufficient to solve _all_
of the fair machine learning problems described above, each as only a
computationally easy _post-processing_ of $\hat{f}$, without sacrificing
accuracy.

###  1.1 Our Results in Context

The idea of _post-processing_ a trained model $\hat{f}$ in order to satisfy
fairness constraints is not new. For example, Hardt et al. (2016) propose a
simple post-processing of a regression function $\hat{f}$ to derive a
classifier subject to false positive or negative rate constraints. However,
the conditions under which such post-processing approaches work are not yet
well understood. In particular, two important questions about post-proceessing
remain: First, _how_ should one algorithmically post-process a regression
function $\hat{f}$ to obtain a good (and fair) downstream classifier, and
_what properties_ must $\hat{f}$ satisfy? Prior work (Hardt et al., 2016)
handles the case in which the groups $\mathcal{G}$ are disjoint, by finding a
different _thresholding_ of $\hat{f}$ for each group $g\in\mathcal{G}$. Is
there a simple, efficient post-processing that applies in the common case that
groups intersect — as is the case e.g. with groups defined by race and gender?
Second and similarly, Hardt et al. (2016) and Corbett-Davies et al. (2017)
show that this post-processing yields the Bayes Optimal fair classifier if
$\hat{f}$ is the true conditional label distribution. Are there weaker
conditions on $\hat{f}$ (that can be efficiently satisfied from only a
polynomial number of samples) that also lead to guarantees? We answer both of
these questions in the affirmative.

#### Post Processing for Intersecting Groups

Suppose we have $k=|\mathcal{G}|$ groups that are intersecting (e.g. divisions
of a population by race, gender, income, nationality, etc.) A naive reduction
to the post-processing approach of Hardt et al. (2016) would consider all
$2^{k}$ (now disjoint) intersections of groups, and find a separate
thresholding of $\hat{f}(x)$ for each one. We show that even when groups
intersect, for a variety of fairness constraints, the optimal post-processing
$\hat{h}$ remains a thresholding that depends on only $k$ parameters
$\lambda_{g}$, one for each group $g$. The value at which to threshold
$\hat{f}(x)$ now depends only on these $k$ parameters _and the subset of
groups that $x$ is contained in_. We give a simple, efficient algorithm to
compute these optimal post-processings. The algorithm is efficient in the
worst case — i.e. it does not have to call any heuristic “learning oracle” as
direct learning approaches do (Agarwal et al., 2018; Kearns et al., 2018), and
requires access only to a modest amount of _unlabeled_ data from the
underlying distribution.

#### Accuracy Guarantees from Multicalibration

As in Hardt et al. (2016) when $\hat{f}$ is the Bayes optimal regression
function, for a variety of fairness constraints, our post-processing $\hat{h}$
is the Bayes optimal fair classifier. But in general we cannot hope to learn
the Bayes optimal regression function $\hat{f}$ given only a polynomial amount
of data and computation. We show that substantially weaker conditions suffice:
If $\hat{f}$ is _multicalibrated_ with respect to a class of models
$\mathcal{H}$, a class of groups $\mathcal{G}$, and a simple class of
functions derived from $\mathcal{H}$ and $\mathcal{G}$, then the post-
processing $\hat{h}$ of $\hat{f}$ will be as accurate as the best fair model
in $\mathcal{H}$ while satisfying all of the fairness constraints defined over
$\mathcal{G}$. Learning a multicalibrated predictor with respect to these
classes can be done with polynomial sample complexity in an oracle-efficient
manner whenever $\mathcal{H}$ and $\mathcal{G}$ have polynomial VC dimension —
and so both the sample and computational complexity of computing $\hat{f}$ are
comparable to what would be required to directly solve a single instance of a
fairness constrained optimization problem over $\mathcal{H}$.

#### Experimental Evaluation

We provide preliminary experimental evaluation of our method on a dataset
derived from Pennsylvania Census data provided by the Folktables package (Ding
et al., 2021). The experimental results support the theoretical findings that
our method is able to quickly converge to a solution that approximately
satisfies the given target constraints.

####

Taken together, our results contribute to the following conclusion: even when
the notion of fairness that is eventually desired in downstream tasks is one
that approximately equalizes some notion of statistical error across groups,
this is _not_ necessarily what should be trained. Aiming instead for group-
wise fidelity in the form of _multicalibration_ provides the flexibility to
deploy an optimal downstream model subject to a variety of fairness
constraints without destroying information that would be needed to later relax
or tighten those constraints, to remove them or to add more, or to change
their type.

###  1.2 Additional Related Work

There are a number of other papers that study the problem of converting a
regression (or “score”) function into a classification rule in the context of
fair machine learning. For example, Woodworth et al. (2017) shows that post-
proceessing a learned binary classification model to satisfy fairness
constraints can be substantially suboptimal even when the hypothesis class
under consideration contains the Bayes optimal predictor, which motivates a
focus on post-processing regression functions instead. Yang et al. (2020)
study the structure of the Bayes optimal fair classifier for several notions
of fairness when groups are intersecting, under a continuity assumption on the
underlying distribution; they do not consider utility guarantees for post-
processing a regression function that does not completely represent the
underlying probability distribution. Wei et al. (2021) and Alabdulmohsin and
Lucic (2021) give post-processing algorithms that transforms a score function
into a regression function that optimizes different measures of accuracy
subject to a variety of fairness constraints using a similar primal/dual
perspective that we use in this paper. But these papers do not address the two
main questions we raise in our work: intersecting groups, and efficiently
learnable conditions on the score function that lead to utility guarantees
(they assume that in the limit the true conditional label distribution is
learnable and given as input to their algorithm)

In proving our accuracy bounds, we draw on a recent line of work on
_multicalibration_ (Hébert-Johnson et al., 2018; Kim et al., 2019; Jung et
al., 2021a; Dwork et al., 2021; Gupta et al., 2022). In particular, Gopalan et
al. (2022) showed that regression functions that are multicalibrated with
respect to a class of models $\mathcal{H}$ are _omni-predictors_ with respect
to $\mathcal{H}$, which means that they can be post-processed to perform as
well as the best model in $\mathcal{H}$ with respect to any convex loss
function satisfying mild technical conditions. The results in our paper can be
viewed as being a _constrained optimization_ parallel to Gopalan et al.
(2022), which studies _unconstrained_ optimization.

Several other papers also use multicalibration of intermediate statistical
products to argue for the utility of downstream models. Zhao et al. (2021)
consider the problem of calibrating a model to the utility function of a
downstream utility maximizing decision maker to preserve the usefulness of the
model for the decision-maker. Diana et al. (2021) show that a _proxy-model_
for a protected attribute can be useful in enforcing fairness constraints on a
downstream model when the real protected attribute is not available if the
proxy is appropriately multicalibrated. Burhanpurkar et al. (2021) propose
training a multicalibrated predictor on the level sets of a low dimensional
learned representation as a means of obtaining Bayes optimality. Kim et al.
(2022) show that a predictor that is multicalibrated with respect to a
function class can adapt to new domains with covariate shift as well as a
model trained using propensity-score reweighting via any propensity score
function in the class.

Hu et al. (2022) independently study a similar problem. Our two papers derive
a closely related but incomparable set of results. Hu et al. (2022) tackles a
more general problem, and studies a richer set of objective functions and
constraints (whereas we restrict attention to the classification error
objective and fairness motivated constraints). In contrast, in our paper, we
are able to take advantage of the additional structure of our problem to
derive improved bounds. In particular, we can handle intersecting groups (with
running time and sample complexity depending polynomially on the number of
groups), whereas Hu et al. (2022) requires taking all of the exponentially
many group intersections to recover disjoint groups—which leads to an
exponential (in the number of groups) loss in the running time and sample
complexity. Similarly, they require more precise multicalibration as more
groups are added, whereas we derive results from a multicalibrated predictor
with parameter that is independent of the number of groups.

###  1.3 Limitations

This work explores approaches to fairness that make a jump between complex and
ambiguous social ideas of fairness and mathematical guarantees such as
equality of false positive rates between groups of individuals. Our work can
be applied only when evaluating the membership of an individual to a group is
well-defined, and when consideration of group membership is legal111Note that
in some contexts such as consumer lending in the United States, direct
consideration of membership in protected groups such as race is illegal.
However, demographic information can be used when designing and auditing a
decision-making process, so long as those characteristics are not part of the
real-time lending decisions., and when the training data is representative of
the underlying population. There will be contexts in which these assumptions
are either false, overly simplistic, or bypass larger questions: e.g. an
application might be fair in its performance but still entirely unethical, or
groups may be systematically underrepresented in datasets. In the latter case,
the guarantees of our work cannot be interpreted as guarantees relative to the
optimal predictor for the true distribution over groups.

It is worth noting that while the assumption that we can define group
membership of individuals simplifies the complexities of personal identity,
this work does improve on the existing literature on post-processing
approaches to fairness in that it allows for non-disjoint, or intersectional,
group membership. In general, this work (and all work in algorithmic fairness)
should not be assumed to “solve" fairness. Instead it should be taken as a
tool in a larger system to evaluate and remediate issues of fairness and
ethics in machine learning.

##  2 Preliminaries

We study binary classification problems. Let $\mathcal{X}$ be an arbitrary
feature space and $\mathcal{Y}=\\{0,1\\}$ be a binary label space. A
classification problem is defined by an underlying data distribution
$\mathcal{D}\in\Delta(\mathcal{X}\times\mathcal{Y})$. In general we will not
have direct access to the data distribution, but rather only to samples drawn
i.i.d. from $\mathcal{D}$. We let $D$ denote a dataset of size $n$, drawn
i.i.d. from $\mathcal{D}$: $D\sim\mathcal{D}^{n}$.

We will study both regression functions $f:\mathcal{X}\rightarrow\mathbb{R}$
and classification functions (classifiers)
$h:\mathcal{X}\rightarrow\\{0,1\\}$. In general we will use $f$ and variants
($f^{*},\hat{f}$, etc.) when speaking of regression functions and $h$ and
variants $(h^{*},\hat{h}$, etc.) when speaking of classification functions.
Our interest will be in regression functions used to estimate conditoinal
label expectations in binary prediction problems, and so the natural range of
our regression functions will be (discrete subsets of) $[0,1]$.

######  Definition 1 (Bayes Optimal Regression Function).

We let $f^{*}$ denote the _Bayes Optimal Regression Function_
$f^{*}=\arg\min_{f}\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}(f(x)-y)^{2}$
which takes value:

$f^{*}(x)=\mathop{\mathbb{E}}_{(x^{\prime},y^{\prime})\sim\mathcal{D}}[y^{\prime}|x^{\prime}=x]$

######  Remark.

The property of $f^{*}$ that we are interested in is that it encodes the true
conditional label expectations. The fact that it minimizes squared error is
not important — $f^{*}$ would also minimize any other proper loss function.

Let $\mathcal{D}_{\mathcal{X}}$ denote the marginal distribution on features
induced by projecting $\mathcal{D}$ onto $\mathcal{X}$. Note that we can
equivalently sample a pair $(x,y)\sim\mathcal{D}$ by first sampling
$x\sim\mathcal{D}_{\mathcal{X}}$ and then sampling $y=1$ with probability
$f^{*}(x)$ and $y=0$ otherwise.

Given a classifier $h:\mathcal{X}\rightarrow\mathcal{Y}$, and a data
distribution $\mathcal{D}$, we can refer to various notions of error. We will
be interested in error rates not just overall, but on subsets of the data that
we call _groups_ (which we might think of as e.g. demographic groups when the
data represents people). We will represent groups by group indicator
functions:

######  Definition 2.

Let $\mathcal{G}$ denote a collection of _groups_ , each represented by a
group indicator function $g:\mathcal{X}\rightarrow\\{0,1\\}$. If $g(x)=1$ we
say that $x$ is a _member_ of group $g$. Let $I$ denote the group containing
all elements ($I(x)=1$ for all $x$). We will always assume that
$I\in\mathcal{G}$.

We allow $\mathcal{G}$ to contain arbitrarily intersecting groups. We can now
define error rates over these groups, and a notion of fairness.

######  Definition 3.

The error of a classifier $h:\mathcal{X}\rightarrow\mathcal{Y}$ on a group $g$
as measured over distribution $\mathcal{D}$ is:

$\text{err}(h,g,\mathcal{D})=\Pr_{(x,y)\sim\mathcal{D}}[h(x)\neq
y|g(x)=1]=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[\ell(h(x),y)|g(x)=1]$

The false positive rate of a classifier $h:\mathcal{X}\rightarrow\mathcal{Y}$
on a group $g$ is:

$\rho(h,g,\mathcal{D})=\Pr_{(x,y)\sim\mathcal{D}}[h(x)\neq y|y=0,g(x)=1]$

When $h$ is a randomized classifier, the probabilities are computed over the
randomness of $h$ as well. For convenience, we write
$\text{err}(h)=\text{err}(h,I,\mathcal{D}),\rho_{g}(h)\equiv\rho(h,g,\mathcal{D})$,
and $\rho(h)\equiv\rho(h,I,\mathcal{D})$.

######  Definition 4.

We say that classifier $h:\mathcal{X}\rightarrow\mathcal{Y}$ satisfies
$\gamma$-False Positive (FP) Fairness with respect to $\mathcal{D}$ and
$\mathcal{G}$ if for all $g\in\mathcal{G}$,

$w_{g}\left|\rho_{g}(h)-\rho(h)\right|\leq\gamma.$

where $w_{g}=\Pr_{(x,y)\sim\mathcal{D}}[g(x)=1,y=0]$.

######  Remark.

In the above definition, we include a multiplicative factor that provides
slack in the fairness guarantee for groups with small weight over the
distribution. This approximation parameter is necessary, as statistical
estimation over small groups is inherently more difficult. By including this
factor directly into our fairness constraint rather than incorporating it
indirectly into sample complexity guarantees, we are able to elide exposition
in our later proofs. An equivalent (up to reparameterization) alternative
would be to remove the $w_{g}$ term in our constraints, but to provide
guarantees only for groups for whom $w_{g}$ is sufficiently large.

For the sake of brevity and clarity, in the main body of this paper we prove
all results in the context of $\gamma$-False Positive Fairness. We discuss the
modifications necessary to extend the results to other fairness notions in
Appendix A.

We will study how to derive classifiers with optimal error properties, subject
to fairness-motivated constraints on group-wise error rates from regression
functions satisfying _multicalibration_ constraints (Hébert-Johnson et al.,
2018). Informally, if $\hat{f}$ is multicalibrated with respect to a class of
functions $C$, then $\hat{f}(x)$ takes values equal to $f^{*}(x)$ in
expectation, even conditional on both the value of $\hat{f}(x)$ and on the
value of $c(x)$ for each $c\in C$. We use two variants. The first
(multicalibration in expectation) was defined and studied in (Gopalan et al.,
2022):

######  Definition 5 (Multicalibration in Expectation (Hébert-Johnson et al.,
2018; Gopalan et al., 2022)).

Fix a distribution $\mathcal{D}$ and let $C$ be a collection of functions
$c:\mathcal{X}\rightarrow\\{0,1\\}$. We say that a predictor
$\hat{f}:\mathcal{X}\rightarrow R$ where $R$ is some discrete domain
$R\subseteq[0,1]$ is $\alpha$-approximately multicalibrated with respect to
$C$ if for every $c\in C$:

$\displaystyle\sum_{v\in
R}\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[\hat{f}(x)=v]\cdot\left|\mathop{\mathbb{E}}_{(x,y)}\left[(\hat{f}(x)-f^{*}(x))\cdot
c(x)\middle|\hat{f}(x)=v\right]\right|$ $\displaystyle=\sum_{v\in
R}\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[\hat{f}(x)=v]\cdot\frac{\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[c(x)=1|\hat{f}(x)=v]}{\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[c(x)=1|\hat{f}(x)=v]}\cdot\left|\mathop{\mathbb{E}}_{(x,y)}\left[(\hat{f}(x)-f^{*}(x))\cdot
c(x)\middle|\hat{f}(x)=v\right]\right|$ $\displaystyle=\sum_{v\in
R}\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[c(x)=1,\hat{f}(x)=v]\cdot\left|\mathop{\mathbb{E}}_{(x,y)}\left[\hat{f}(x)-f^{*}(x)\middle|\hat{f}(x)=v,c(x)=1\right]\right|$
$\displaystyle=\sum_{v\in
R}\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[c(x)=1,\hat{f}(x)=v]\cdot\left|v-\mathop{\mathbb{E}}_{(x,y)}\left[f^{*}(x)\middle|\hat{f}(x)=v,c(x)=1\right]\right|$
$\displaystyle\leq\alpha$

We will require this notion of multicalibration with respect to the set of
groups $\mathcal{G}$ with which we define our fairness constraints, for the
classifiers $h\in\mathcal{H}$, and for the intersection of these classes
$\mathcal{G}\times\mathcal{H}=\\{g(x)\cdot
h(x)|g\in\mathcal{G},h\in\mathcal{H}\\}$. We will also need a variant of
multicalibration that is tailored to two-argument functions
$c:\mathcal{X}\times R\rightarrow\\{0,1\\}$ in order to argue about the
properties of thresholding functions, which take both a value
$x\in\mathcal{X}$ and a threshold in a discrete domain $R\subseteq[0,1]$, and
which threshold predictions to $\\{0,1\\}$.

In this definition, when we condition on $\hat{f}(x)=v$, we also condition on
the second argument of $c$ taking the same value $v$. We call this _joint_
-multicalibration. It is only a modest generalization of multicalibration: we
verify in Appendix C that existing algorithms for obtaining multicalibrated
predictors easily extend to our definition of joint multicalibration.

######  Definition 6 (Joint Multicalibration in Expectation).

We say that a predictor $\hat{f}:\mathcal{X}\rightarrow R$ where $R$ is some
discrete domain $R\subseteq[0,1]$ is $\alpha$-approximately jointly
multicalibrated with respect to a class of functions $c:\mathcal{X}\times
R\to\\{0,1\\}$ if for every $c\in C$:

$\sum_{v\in
R}\Pr[\hat{f}(x)=v,c(x,v)=1]\cdot\left|\mathop{\mathbb{E}}_{(x,y)}\left[(\hat{f}(x)-f^{*}(x))\middle|\hat{f}(x)=v,c(x,v)=1\right]\right|\leq\alpha,$

which is equivalent to

$\sum_{v\in
R}\Pr[\hat{f}(x)=v]\cdot\left|\mathop{\mathbb{E}}_{(x,y)}\left[c(x,v)\cdot(\hat{f}(x)-f^{*}(x))\middle|\hat{f}(x)=v\right]\right|\leq\alpha.$

##  3 The Structure of an Optimal Post-Processing

In this section, we consider a fairness-constrained optimization problem that
seeks to find the (distribution over) model(s) in $\mathcal{H}$ that minimize
error subject to a constraint on group-wise false positive rates:

$\displaystyle\min_{h\in\Delta\mathcal{H}}$ $\displaystyle\text{err}(h)$ (1)
$\displaystyle\textrm{s.t. for each }g\in\mathcal{G}:$ $\displaystyle
w_{g}|\rho_{g}(h)-\rho(h)|\leq\gamma,$

where $w_{g},\rho_{g}(h),$ and $\rho(h)$ are defined as in Definition 3.

It will be useful for us to re-write this optimization problem in terms of the
conditional label expectation $f^{*}(x)$. Since later in the paper we will
want to replace $f^{*}(x)$ with a different regression function $f$ that is
easier to learn, we define the linear program generically in terms of an
arbitrary regression function $f$:

######  Definition 7.

Let $f:\mathcal{X}\rightarrow R\subseteq[0,1]$ be some regression function and
let $\gamma\in\mathbb{R}_{+}$. Define $\psi(f,\gamma,\mathcal{H})$ to be the
following optimization problem:

$\displaystyle\min_{h\in\Delta\mathcal{H}}$
$\displaystyle\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[f(x)\ell(h(x),1)+(1-f(x))\ell(h(x),0)]$
$\displaystyle\textrm{s.t. for each }g\in\mathcal{G}:$
$\displaystyle\left|\mathbb{E}[\ell(h(x),0)g(x)(1-f(x))]-\beta_{g}\mathbb{E}\left[\ell(h(x),0)(1-f(x))\right]\right|\leq\gamma,$

where $\beta_{g}=\Pr[g(x)=1|y=0]$.

######  Lemma 1.

Let $f^{*}$ be the Bayes optimal regression function over $\mathcal{D}$. Then
optimization problem $\psi(f^{*},\gamma,\mathcal{H})$ is equivalent to the
fairness-constrained optimization problem (1).

The proof is in Appendix B.

We will be interested in the structure and properties of the optimal solution
to $\psi(f,\gamma,\mathcal{H})$, which will be elucidated via its Lagrangian.
Note that the optimization problem has $2|\mathcal{G}|$ linear inequality
constraints. Let $\lambda=\\{\lambda_{g}^{\pm}\\}_{g\in\mathcal{G}}$ denote
the vector of $2|\mathcal{G}|$ dual variables corresponding to those
constraints, and write $\lambda_{g}=\lambda_{g}^{+}-\lambda_{g}^{-}$.

######  Definition 8 (Lagrangian).

Given any regression function $f$, we define a Lagrangian of the optimization
problem $\psi(f,\gamma,\mathcal{H})$ as
$L_{f}:\mathcal{H}\times\mathbb{R}^{2|\mathcal{G}|}\rightarrow\mathbb{R}$:

$\displaystyle L_{f}(h,\lambda)$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\bigg{[}f(x)\ell(h(x),1)+(1-f(x))\ell(h(x),0)$
$\displaystyle\quad+\sum_{g\in\mathcal{G}}\lambda_{g}^{+}\big{(}\ell(h(x),0)g(x)(1-f(x))-\beta_{g}\ell(h(x),0)(1-f(x))-\gamma\big{)}$
$\displaystyle\quad+\sum_{g\in\mathcal{G}}\lambda_{g}^{-}\big{(}\beta_{g}\ell(h(x),0)(1-f(x))-\ell(h(x),0)g(x)(1-f(x))-\gamma\big{)}\bigg{]}$

For convenience, given a Bayes optimal regressor $f^{*}$, we write
$L^{*}=L_{f^{*}}$. Similarly, given some other regressor $\hat{f}$, we write
$\hat{L}=L_{\hat{f}}$.

Let $\mathcal{H}_{A}=2^{\mathcal{X}}$ be the set of all Boolean functions
$f:\mathcal{X}\rightarrow\\{0,1\\}$. We will consider solving our optimization
problem over this set of functions $\mathcal{H}_{A}$.

######  Definition 9 (Optimal post-processed classifier).

We say that a classifier $h_{f}$ is an optimal post-processing of $f$ if there
exists a vector $\lambda^{f}$ such that the following primal/dual optimality
conditions are simultaneously met:

$h_{f}(x)\in\arg\min_{h\in\mathcal{H}_{A}}L_{f}(h,\lambda^{f})\quad\lambda^{f}\in\arg\max_{\lambda\in\mathbb{R}^{2|\mathcal{G}|}}L_{f}(h_{f},\lambda).$

For convenience, we write

$\displaystyle h^{*}(x)=h_{f^{*}}(x)\quad$
$\displaystyle\text{and}\quad\lambda^{*}=\lambda^{f^{*}}$
$\displaystyle\hat{h}(x)=h_{\hat{f}}(x)\quad$
$\displaystyle\text{and}\quad\hat{\lambda}=\lambda^{\hat{f}}$

where $f^{*}$ is the Bayes optimal regressor and $\hat{f}$ is any other
regressor. We will write $\lambda_{g}^{*}$ and $\hat{\lambda}_{g}$ to refer to
the dual variable in $\lambda^{*}$ and $\hat{\lambda}$ for group $g$,
respectively. We observe that as the optimal solution to the Lagrangian
minimax optimization problem, $h^{*}(x)$ is the Bayes optimal classifier
subject to the fairness constraints in 1.

######  Lemma 2.

The optimal post-processed classifier $h$ of $\psi(f,\gamma,\mathcal{H}_{A}$)
for some regressor $f$ takes the following form:

$h(x)=\begin{cases}1,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})>0,\\\ 0,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})>0,\\\ 1,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})<0,\\\ 0,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})<0.\end{cases}$

In the edge case in which
$f(x)=\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}$,
$h(x)$ could take either value and might be randomized.

The proof is in Appendix B.

###  3.1 Computing the optimally post-processed classifier

To approximate $h$ given $f$, we need to compute an approximately optimal
solution to the linear program $\psi(f,\gamma,\mathcal{H}_{A})$. We can do
this by playing a no-regret algorithm over the dual variables $\lambda$ and
best response over the primal variables as defined in Definition 23. We can
approximate the losses to the no-regret algorithm from a finite sample of
unlabelled data of size scaling logarithmically in the number of constraints
and linearly in the number of rounds $T$ of the no regret dynamics, which
using standard techniques we can show yields an approximately optimal solution
to the original LP. The algorithm is described in Algorithm 1. We state its
approximate guarantees then spend the rest of this section formalizing the
structure necessary for the result.

######  Theorem 1.

Let $\mathrm{OPT}$ be the objective value of the optimal solution to
$\psi(f,\gamma,\mathcal{H}_{A})$. Then, for any $C\in\mathbb{R}$, after
$T=\frac{1}{4}\cdot C^{2}\cdot\left(C^{2}+4|\mathcal{G}|\right)^{2}$
iterations, Algorithm 1 outputs a randomized hypothesis $\bar{h}$ such that
$\text{err}(\bar{h})\leq\mathrm{OPT}+\frac{2}{C}$ and
$w_{g}|\rho_{g}(\bar{h})-\rho(\bar{h})|\leq\gamma+\frac{1}{C}+\frac{2}{C^{2}}$.

In order to prove Theorem 1 (which is proved fully in Appendix B),we first
must specify the game formulation of the problem and demonstrate that
constraining the dual player still allows for an adequate approximation to the
original problem.

#### Game formulation

We pose the optimization of our original linear program as a zero-sum game
between a primal (minimization) player who plays over the set of hypotheses
and a dual (maximization) player who plays over the set of dual variables. The
utility function of the game is the Lagrangian of our linear program as stated
in Definition 8. The value of this game is given by

$\displaystyle\min_{h\in\Delta\mathcal{H}}\max_{\lambda\in\mathbb{R}^{2|\mathcal{G}|}}L_{f}(h,\lambda).$

#### Constraining the linear program

In order to compute an approximate minimax solution to this game, we need to
constrain the strategy space of the dual player. That is, we need to bound the
dual space to a region
$\Lambda=\left\\{\lambda\in\mathbb{R}^{2\mathcal{G}}\big{|}\|\lambda\|_{1}\leq
C\right\\}$. We call this constrained version of the problem the
$\Lambda$-bounded Lagrangian problem, which has value

$\min_{h\in\Delta\mathcal{H}}\max_{\lambda:|\lambda|_{1}\leq
C}L_{f}(h,\lambda).$ (2)

We can apply the minimax theorem to this bounded game to see:

$\displaystyle\min_{h\in\Delta\mathcal{H}}\max_{\lambda:|\lambda|_{1}\leq
C}L_{f}(h,\lambda)\equiv\max_{\lambda:|\lambda|_{1}\leq
C}\min_{h\in\Delta\mathcal{H}}L_{f}(h,\lambda).$

We will only be able to achieve an approximate solution to the problem, which
we define as follows.

######  Definition 10.

We say that $(h,\lambda)$ is a $v$-approximate minimax solution to the
$\Lambda$-bounded Lagrangian problem $L_{f}$ if
$L_{f}(h,\lambda)\leq\min_{h^{\prime}\in\Delta\mathcal{H}}L_{f}(h^{\prime},\lambda)+v$
and
$L_{f}(h,\lambda)\geq\max_{\lambda^{\prime}\in\Lambda}L_{f}(h,\lambda^{\prime})-v.$

An approximate minimax solution to this bounded version of the problem is also
an approximate solution to the original problem we described in Equation 1:

######  Theorem 2.

[Kearns et al. (2018)] Let $(h,\lambda)$ be a $v$-approximate minimax solution
to the $\Lambda$-bounded Lagrangian problem $L_{f}$ and let $\mathrm{OPT}$ be
the objective value of the optimal solution to
$\psi(f,\gamma,\mathcal{H}_{A})$. Then, $err(h)\leq\text{OPT}+2v$, and
$\forall g\in\mathcal{G},w_{g}|\rho_{g}(h)-\rho(h)|\leq\gamma+(1+2v)/C.$

#### Approximate equilibrium of the constrained game

Now, we can proceed with no-regret play to find an approximate solution to the
game. The dual player will play projected gradient descent over their vector
$\lambda$ and the primal player will best respond, as described in Algorithm
1.

######  Theorem 3.

Algorithm 1 returns an $\epsilon-$approximate equilibrium solution to the
zero-sum game defined by Equation 2 after
$T=\frac{1}{4\epsilon^{2}}\left(\frac{1}{\epsilon^{2}}+4|\mathcal{G}|\right)^{2}$
rounds.

The proof of Theorem 3 is in Appendix B. Combining Theorem 2 and Theorem 3
gives us the proof of Theorem 1, which appears in Appendix B.

Input: (_$D$ : dataset, $f:\mathcal{X}\to[0,1]$: regression function,
$\mathcal{G}$: groups, $\gamma$: tolerance on fairness violation, $C$: bound
on dual $(\|\lambda\|_{1}\leq C)$, $\eta$: learning rate_)

Initialize dual vector $\lambda^{0}={\bf 0}$ and set $T=\frac{1}{4}\cdot
C^{2}\cdot(C^{2}+4|\mathcal{G}|)^{2}$.

for  _$t=1,\ldots,T$_ do

Primal player updates $h_{t}$ $h_{t}(x)=\begin{cases}1,&\text{if
}f(x)\geq\frac{1+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})>0,\\\
0,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})>0,\\\
1,&\text{if
}f(x)\leq\frac{1+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})<0,\\\
0,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})<0,\\\
1,&\text{if
}2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})=0\end{cases}$
Compute  $\displaystyle\hat{\rho}^{t}_{g}$
$\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim
D}[\ell(h_{t}(x),0)g(x)(1-f(x))]\text{ for all }g\in\mathcal{G},$
$\displaystyle\hat{\rho}^{t}$ $\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim
D}[\beta_{g}\ell(h_{t}(x),0)(1-f(x))],\text{ where }\beta_{g}=\Pr[g(x)=1|y=0]$
Dual player updates  $\displaystyle\lambda_{g}^{t,+}$
$\displaystyle=\max(0,\lambda_{g}^{t,+}+\eta\cdot(\hat{\rho}^{t}_{g}-\hat{\rho}^{t}-\gamma)),$
$\displaystyle\lambda_{g}^{t,-}$
$\displaystyle=\max(0,\lambda_{g}^{t,-}+\eta\cdot(\hat{\rho}^{t}-\hat{\rho}^{t}_{g}-\gamma)).$

Dual player sets
$\lambda^{t}=\sum_{g\in\mathcal{G}}\lambda_{g}^{t,+}-\lambda_{g}^{t,-}$.

If $\|\lambda^{t}\|_{1}>C$, set
$\lambda^{t}=\arg\min_{\\{\tilde{\lambda}\in\mathbb{R}^{2\mathcal{G}}|\|\tilde{\lambda}\|_{1}\leq
C\\}}\|\lambda_{t}-\tilde{\lambda}\|_{2}^{2}$.

end for

Output:  $\bar{h}:=\frac{1}{T}\sum_{t=1}^{T}\hat{h}_{t}$, a uniformly random
classifier over all rounds’ hypotheses.

Algorithm 1 Projected Gradient Descent Algorithm

###  3.2 Beginning with a Multicalibrated Regression Function $\hat{f}$

Thus far, we have considered the optimization problem
$\psi(f,\gamma,\mathcal{H}_{A})$ in the abstract, have characterized its
optimal solution $h$, and have given a simple algorithm to find $\bar{h}$, an
approximately optimal solution. When $f=f^{*}$, $h=h^{*}$ is the Bayes optimal
fair classifier, and $\bar{h}$ is approximately Bayes optimal. But in
practice, we will not have access to $f^{*}$, but will instead only have some
surrogate function, which we will call $\hat{f}(x)$. We will argue that if
$\hat{f}$ is appropriately multicalibrated, then it is good enough for our
purposes. We will compare the approximate solution $\bar{h}$ produced by
Algorithm 1 to the optimization problem $\psi(\hat{f},\gamma,\mathcal{H}_{A})$
which has corresponding Lagrangian $\hat{L}(\hat{h},\hat{\lambda})$, as
defined in Definition 8 to the optimal solution $(h^{*},\lambda^{*})$ to the
optimization problem $\psi(f^{*},\gamma,\mathcal{H})$ for some constrained
class $\mathcal{H}$, and show conditions under which they are close.

In order to proceed, we first need to determine what our surrogate function
ought to be multicalibrated with respect to. In addition to being
$\alpha$-approximately multicalibrated in expectation with respect to
$\mathcal{G}$ and $\mathcal{H}$, we will require that $\hat{f}$ be
$\alpha$-approximately multicalibrated with respect to
$\mathcal{G}\times\mathcal{H}=\\{g(x)\cdot
h(x)|g\in\mathcal{G},h\in\mathcal{H}\\}$. Furthermore, we will need to require
that $\hat{f}$ be $\alpha$-approximately jointly multicalibrated in
expectation with respect to a set of thresholding functions, defined below:

######  Definition 11 (Set of thresholding functions $\mathcal{B}(C)$).

Let $x_{\mathcal{G}}\in\\{0,1\\}^{|\mathcal{G}|}$ denote the group membership
indicator vector of some point $x$. Define the function

$d(v):=\frac{2v-1}{1-v}.$

Then, let for any $\lambda,x,\beta$

$s_{\lambda}(x,v):=\mathbbm{1}[\langle\lambda,x_{\mathcal{G}}-\beta\rangle\geq
d(v)].$

Define
$\mathcal{B}(C)=\\{s_{\lambda}|\lambda\in\Lambda(C),\beta=\beta_{g_{1}},\ldots,\beta_{g_{|\mathcal{G}|}}\\}$,
where
$\Lambda(C)=\left\\{\lambda\in\mathbb{R}^{2\mathcal{G}}\big{|}\|\lambda\|_{1}\leq
C\right\\}$, as defined in Equation 2 and
$\beta_{g}=\Pr_{(x,y)\sim\mathcal{D}}[g(x)=1|y=0]$, as defined in Definition
7.

######  Remark.

When the groups of interest are disjoint, joint multicalibraiton with respect
to this class $\mathcal{B}(C)$ is implied by multicalibration with respect to
$\mathcal{G}$. But when the groups can intersect, this is not an implication,
and asking for joint multicalibration with respect to $\mathcal{B}(C)$ adds
new constraints on $\hat{f}$.

Informally, these functions take an example, and map it to a vector of its
group membership, indicating whether a $\lambda$-weighting of the example’s
group membership is larger than some threshold $d(v)$. We will need joint
multicalibration with respect to such functions in order to relate the
estimated error of $\hat{h}$ to its true error. These thresholding functions
$\mathcal{B}(C)$ have a natural relationship to the deterministic thresholded
models $h_{t}$ that we compute at each round of Algorithm 1:

######  Lemma 3.

Let $h_{t}$ be the response to $\lambda^{t-1}$ described in Algorithm 1 at
some round $t\in[T]$. Then,

$h_{t}(x)=s_{\lambda^{t-1}}(x,f(x)).$

The proof is in Appendix B. We verify in Appendix C that a variant of the
multicalibration algorithms given in Hébert-Johnson et al. (2018); Gopalan et
al. (2022) can guarantee joint multicalibration with respect to
$\mathcal{B}(C)$ as well.

With these preliminaries behind us, we can now state our main theorem, which
shows that for any class of models $\mathcal{H}$ and class of groups
$\mathcal{G}$, given an appropriately multicalibrated $\hat{f}$ (with
multicalibration requirements depending on $\mathcal{H}$ and $\mathcal{G}$),
the model $\bar{h}$ output by Algorithm 1 achieves an error rate and fairness
guarantees comparable to the optimal solution to
$\psi(f^{*},\gamma,\mathcal{H})$:

######  Theorem 4.

Set $C=\sqrt{1/\alpha}$. Let $\hat{f}$ be $\alpha$-approximately
multicalibrated in expectation with respect to $\mathcal{G}$, $\mathcal{H}$,
and $\mathcal{G}\times\mathcal{H}$ and $\alpha$-approximately jointly
multicalibrated in expectation with respect to $\mathcal{B}(C)$. Let $\bar{h}$
be the result of running Algorithm 1 with input $\hat{f}$ and $C$. Then,
$\text{err}(\bar{h})\leq\text{err}(h^{*})+\alpha(5+2\sqrt{1/\alpha})+2\sqrt{\alpha},$
and for all
$g\in\mathcal{G},w_{g}\left|\rho_{g}(\bar{h})-\rho(\bar{h})\right|\leq
w_{g}\left|\rho_{g}(h^{*})-\rho(h^{*})\right|+w_{g}\alpha.$

Proof Sketch: Generalizing notation from the previous sections, let
$\text{err}(h)=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[f^{*}(x)\ell(h(x),1)+(1-f^{*}(x))\ell(h(x),0)]$
denote the true error of $h$ on the distribution (i.e. as measured according
to the true conditional label distribution $f^{*}$), and let
$\widehat{\text{err}}(h)=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[\hat{f}(x)\ell(h(x),1)+(1-\hat{f}(x))\ell(h(x),0)]$
denote the error of $h$ as estimated using the surrogate function $\hat{f}$.
At a high level, the proof of Theorem 4 will proceed as follows:

$\displaystyle\text{err}(h^{*})$ $\displaystyle=L^{*}(h^{*},\lambda^{*})$ (3)
$\displaystyle\geq L^{*}(h^{*},\hat{\lambda})$ (4)
$\displaystyle\approx\hat{L}(h^{*},\hat{\lambda})$ (5)
$\displaystyle\geq\hat{L}(\hat{h},\hat{\lambda})$ (6)
$\displaystyle=\widehat{\text{err}}(\hat{h})$ (7)
$\displaystyle\approx\widehat{\text{err}}(\bar{h})$ (8)
$\displaystyle\approx\text{err}(\bar{h}).$ (9)

Each of these steps takes a lemma (presented in full in the appendix) to
justify, but the logic is at a high level as follows: The equalities on lines
3 and 7 follow from complimentary slackness: at the optimal solution
$(h^{*},\lambda^{*})$ it must be that for each constraint $g$ either the
constraint is exactly tight so that its “violation" term in the Lagrangian
evaluates to 0, or its corresponding dual variable $\lambda_{g}^{\pm}=0$.
Thus, all terms in the Lagrangian other than the objective evaluate to 0. The
inequality in line 4 follows from the dual optimality condition that
$\lambda^{*}\in\arg\max_{\lambda}L^{*}(h^{*},\lambda)$ and similarly the
inequality in line 6 follows from the primal optimality condition that
$\hat{h}\in\arg\min_{h\in\mathcal{H}_{A}}\hat{L}(h,\hat{\lambda})$. Line 8
follows from the fact that $\bar{h}$ is an approximately optimal solution to
$\psi(\hat{f},\gamma,\mathcal{H}_{A})$. Steps 5 and 9 follow from our
multicalibration guarantees, the former from multicalibration with respect to
groups and our hypothesis class, and the latter from joint multicalibration
with respect to the set of thresholding functions from Definition 11. The
complete proof is found in Appendix B.

##  4 Experiments

In this section, we evaluate our post-processing algorithm on a dataset
derived from Pennsylvania Census data provided by the Folktables package (Ding
et al., 2021), which we use under its MIT license. The sensitive attributes we
use from the dataset are binarized gender and the re-coded detailed race code
(RAC1P) to create two classes of overlapping groups. We run our algorithm on
top of a regression function $\hat{f}$ trained using the sklearn gradient-
boosted decision trees package — notably it is _not_ guaranteed to be
multicalibrated in any of the ways our theorems require! Nevertheless our
experiments bear out that our post-processing method performs well even on top
of off-the-shelf regression methodologies. We expand on our experimental
investigation in Appendix E.

Figure 1: The plot on the left is a trajectory over 2000 iterations of
gradient descent of our method post-processing a base model of gradient-
boosted regression trees, for a single value of $\gamma=0.01$. The trajectory
starts at the top of the figure and moves downwards with time, and the blue
point represents the uniform distribution over the constituent models of the
2000 iterations. The blue point, whose error is 0.1987 and maximum violation
of group error - population error is 0.0098, shows our method limits the
maximum violation to $\gamma$. The plot on the right shows the pareto curve
for our method for constraint values ranging between $0.003\leq\gamma\leq
0.01$, showing that large reductions in false positive rate disparities cost
modestly in error.

The experimental findings we present support the theoretical analysis that the
algorithm quickly converges to classifier approximately satisfying our
fairness constraints.

We emphasize that our post-processing method is extremely lightweight. As a
primal/dual algorithm, it is very similar in structure to the “fair
reductions” method of (Agarwal et al., 2018). However where (Agarwal et al.,
2018) needs to solve an ERM problem at every iteration and then evaluate the
performance of the resulting trained model, we entirely skip the ERM step and
need only evaluate the performance of a thresholded classifier which we have
in closed form.

### Acknowledgements

This work was supported in part by NSF grants AF-1763307, CCF-2217062, and
FAI-2147212 and a grant from the Simons Foundation.

## References

  * Agarwal et al. [2018] Alekh Agarwal, Alina Beygelzimer, Miroslav Dudík, John Langford, and Hanna Wallach.  A reductions approach to fair classification.  In _International Conference on Machine Learning_ , pages 60–69. PMLR, 2018.
  * Alabdulmohsin and Lucic [2021] Ibrahim M Alabdulmohsin and Mario Lucic.  A near-optimal algorithm for debiasing trained machine learning models.  _Advances in Neural Information Processing Systems_ , 34:8072–8084, 2021.
  * Bassily et al. [2016] Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman.  Algorithmic stability for adaptive data analysis.  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , pages 1046–1059, 2016.
  * Burhanpurkar et al. [2021] Maya Burhanpurkar, Zhun Deng, Cynthia Dwork, and Linjun Zhang.  Scaffolding sets.  _arXiv preprint arXiv:2111.03135_ , 2021.
  * Corbett-Davies et al. [2017] Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq.  Algorithmic decision making and the cost of fairness.  In _Proceedings of the 23rd acm sigkdd international conference on knowledge discovery and data mining_ , pages 797–806, 2017.
  * Diana et al. [2021] Emily Diana, Wesley Gill, Michael Kearns, Krishnaram Kenthapadi, Aaron Roth, and Saeed Sharifi-Malvajerdi.  Multiaccurate proxies for downstream fairness.  _arXiv preprint arXiv:2107.04423_ , 2021.
  * Ding et al. [2021] Frances Ding, Moritz Hardt, John Miller, and Ludwig Schmidt.  Retiring adult: New datasets for fair machine learning.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Dua and Graff [2017] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.  URL http://archive.ics.uci.edu/ml.
  * Dwork et al. [2012] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel.  Fairness through awareness.  In _Proceedings of the 3rd innovations in theoretical computer science conference_ , pages 214–226, 2012.
  * Dwork et al. [2015] Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth.  Preserving statistical validity in adaptive data analysis.  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , pages 117–126, 2015.
  * Dwork et al. [2021] Cynthia Dwork, Michael P Kim, Omer Reingold, Guy N Rothblum, and Gal Yona.  Outcome indistinguishability.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 1095–1108, 2021.
  * Freund and Schapire [1996] Yoav Freund and Robert E. Schapire.  Game theory, on-line prediction and boosting.  In _Proceedings of the Ninth Annual Conference on Computational Learning Theory_ , COLT ’96, page 325–332, New York, NY, USA, 1996. Association for Computing Machinery.  ISBN 0897918118.  doi: 10.1145/238061.238163.  URL https://doi.org/10.1145/238061.238163.
  * Gopalan et al. [2022] Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder.  Omnipredictors.  In _13th Innovations in Theoretical Computer Science Conference (ITCS 2022)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * Gupta et al. [2022] Varun Gupta, Christopher Jung, Georgy Noarov, Mallesh M Pai, and Aaron Roth.  Online multivalid learning: Means, moments, and prediction intervals.  In _13th Innovations in Theoretical Computer Science Conference (ITCS 2022)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * Hardt et al. [2016] Moritz Hardt, Eric Price, and Nati Srebro.  Equality of opportunity in supervised learning.  _Advances in neural information processing systems_ , 29, 2016.
  * Hébert-Johnson et al. [2018] Ursula Hébert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum.  Multicalibration: Calibration for the (computationally-identifiable) masses.  In _International Conference on Machine Learning_ , pages 1939–1948. PMLR, 2018.
  * Hu et al. [2022] Lunjia Hu, Inbal Livni-Navon, Omer Reingold, and Chutong Yang.  Omnipredictors for constrained optimization.  In _Manuscript_ , 2022.
  * Jung et al. [2021a] Christopher Jung, Changhwa Lee, Mallesh Pai, Aaron Roth, and Rakesh Vohra.  Moment multicalibration for uncertainty estimation.  In _Conference on Learning Theory_ , pages 2634–2678. PMLR, 2021a.
  * Jung et al. [2021b] Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld.  A new analysis of differential privacy’s generalization guarantees.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 9–9, 2021b.
  * Kearns et al. [2018] Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu.  Preventing fairness gerrymandering: Auditing and learning for subgroup fairness.  In _International Conference on Machine Learning_ , pages 2564–2572. PMLR, 2018.
  * Kim et al. [2019] Michael P Kim, Amirata Ghorbani, and James Zou.  Multiaccuracy: Black-box post-processing for fairness in classification.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , pages 247–254, 2019.
  * Kim et al. [2022] Michael P Kim, Christoph Kern, Shafi Goldwasser, Frauke Kreuter, and Omer Reingold.  Universal adaptability: Target-independent inference that competes with propensity scoring.  _Proceedings of the National Academy of Sciences_ , 119(4), 2022.
  * Wei et al. [2021] Dennis Wei, Karthikeyan Natesan Ramamurthy, and Flavio P Calmon.  Optimized score transformation for consistent fair classification.  _J. Mach. Learn. Res._ , 22:258–1, 2021.
  * Woodworth et al. [2017] Blake Woodworth, Suriya Gunasekar, Mesrob I Ohannessian, and Nathan Srebro.  Learning non-discriminatory predictors.  In _Conference on Learning Theory_ , pages 1920–1953. PMLR, 2017\.
  * Yang et al. [2020] Forest Yang, Mouhamadou Cisse, and Sanmi Koyejo.  Fairness with overlapping groups; a probabilistic perspective.  _Advances in neural information processing systems_ , 33:4067–4078, 2020.
  * Zhao et al. [2021] Shengjia Zhao, Michael Kim, Roshni Sahoo, Tengyu Ma, and Stefano Ermon.  Calibrating predictions to decisions: A novel approach to multi-class calibration.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Zinkevich [2003] Martin Zinkevich.  Online convex programming and generalized infinitesimal gradient ascent.  In _Proceedings of the 20th international conference on machine learning (icml-03)_ , pages 928–936, 2003.

##  Appendix A Generalization to other fairness notions

###  A.1 False Negative (FN) Fairness

######  Definition 12.

The false negative rate of a classifier $h:\mathcal{X}\rightarrow\mathcal{Y}$
on a group $g$ is:

$\rho_{\text{FN}}(h,g,\mathcal{D})=\Pr_{(x,y)\sim\mathcal{D}}[h(x)\neq
y|y=1,g(x)=1]$

When $h$ is a randomized classifier, the probabilities are computed over the
randomness of $h$ as well.
$\rho_{g}^{\text{FN}}(h)\equiv\rho_{\text{FN}}(h,g,\mathcal{D})$, and
$\rho_{\text{FN}}(h)\equiv\rho(h,I,\mathcal{D})$.

######  Definition 13.

We say that classifier $h:\mathcal{X}\rightarrow\mathcal{Y}$ satisfies
$\gamma$-False Negative (FN) Fairness with respect to $\mathcal{D}$ and
$\mathcal{G}$ if for all $g\in\mathcal{G}$,

$w_{g}^{\text{FN}}\left|\rho_{g}^{\text{FN}}(h)-\rho_{\text{FN}}(h)\right|\leq\gamma.$

where $w_{g}^{\text{FN}}=\Pr_{(x,y)\sim\mathcal{D}}[g(x)=1,y=1]$.

We consider the following fairness-constrained optimization problem:

$\displaystyle\min_{h\in\Delta\mathcal{H}}$ $\displaystyle\text{err}(h)$ (10)
$\displaystyle\textrm{s.t. for each }g\in\mathcal{G}:$ $\displaystyle
w_{g}^{\text{FN}}|\rho_{g}^{\text{FN}}(h)-\rho_{\text{FN}}(h)|\leq\gamma,$

######  Definition 14.

Let $f:\mathcal{X}\rightarrow R\subseteq[0,1]$ be some regression function and
let $\gamma\in\mathbb{R}_{+}$. Define $\psi_{\text{FN}}(f,\gamma,\mathcal{H})$
to be the following optimization problem:

$\displaystyle\min_{h\in\Delta\mathcal{H}}$
$\displaystyle\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[f(x)\ell(h(x),1)+(1-f(x))\ell(h(x),0)]$
$\displaystyle\textrm{s.t. for each }g\in\mathcal{G}:$
$\displaystyle\left|\mathbb{E}[\ell(h(x),1)g(x)f(x)]-\beta_{g}^{\text{FN}}\mathbb{E}\left[\ell(h(x),1)f(x)\right]\right|\leq\gamma,$

where $\beta_{g}^{\text{FN}}=\Pr[g(x)=1|y=1]$.

######  Lemma 4.

Let $f^{*}$ be the Bayes optimal regression function over $\mathcal{D}$. Then
optimization problem $\psi_{\text{FN}}(f^{*},\gamma,\mathcal{H})$ is
equivalent to the fairness-constrained optimization problem 10.

###### Proof.

Note that the objective function is equivalent to that of Equation 1, and
hence proof of the objectives being equivalent is identical to that of Lemma
1. For the constraints, note that

$\displaystyle w_{g}^{\text{FN}}|\rho_{g}^{\text{FN}}(h)-\rho_{\text{FN}}(h)|$
$\displaystyle=\Pr[g(x)=1,y=1]\left|\Pr[h(x)=0|g(x)=1,y=1]-\Pr[h(x)=0|y=1]\right|$
$\displaystyle=\Pr[g(x)=1,y=1]\bigg{|}\frac{\Pr[h(x)=0,g(x)=1,y=1]}{\Pr[g(x)=1,y=1]}-\frac{\Pr[h(x)=0,y=1]}{\Pr[Y=1]}\bigg{|}$
$\displaystyle=\left|\Pr[h(x)=0,g(x)=1,y=1]-\frac{\Pr[g(x)=1,y=1]\Pr[h(x)=0,y=1]}{\Pr[Y=1]}\right|$
$\displaystyle=\left|\mathbb{E}[\ell(h(x),1)g(x)f^{*}(x)]-\frac{\Pr[g(x)=1,y=1]}{\Pr[Y=1]}\mathbb{E}\left[\ell(h(x),1)f^{*}(x)\right]\right|$
$\displaystyle=\left|\mathbb{E}[\ell(h(x),1)g(x)f^{*}(x)]-\Pr[g(x)=1|Y=0]\mathbb{E}\left[\ell(h(x),1)f^{*}(x)\right]\right|$
$\displaystyle=\left|\mathbb{E}[\ell(h(x),1)g(x)f^{*}(x)]-\beta_{g}^{\text{FN}}\mathbb{E}\left[\ell(h(x),1)f^{*}(x)\right]\right|.$

The result follows. ∎

######  Definition 15 (Lagrangian).

Given any regression function $f$, we define a Lagrangian of the optimization
problem $\psi_{\text{FN}}(f,\gamma,\mathcal{H})$ as
$L_{f}^{\text{FN}}:\mathcal{H}\times\mathbb{R}^{2|\mathcal{G}|}\rightarrow\mathbb{R}$:

$\displaystyle L_{f}^{\text{FN}}(h,\lambda)$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\bigg{[}f(x)\ell(h(x),1)+(1-f(x))\ell(h(x),0)$
$\displaystyle\quad+\sum_{g\in\mathcal{G}}\lambda_{g}^{+}\big{(}\ell(h(x),1)g(x)f(x)-\beta_{g}\ell(h(x),1)f(x)-\gamma\big{)}$
$\displaystyle\quad+\sum_{g\in\mathcal{G}}\lambda_{g}^{-}\big{(}\beta_{g}\ell(h(x),1)f(x)-\ell(h(x),1)g(x)f(x)-\gamma\big{)}\bigg{]}$

######  Lemma 5.

$\displaystyle L_{f}^{\text{FN}}(h,\lambda)$
$\displaystyle=\mathbb{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}\ell(h(x),0)-\gamma\sum_{g\in\mathcal{G}}(\lambda_{g}^{+}+\lambda_{g}^{-})$
$\displaystyle\quad+f(x)\left(-\ell(h(x),0)+\ell(h(x),1)\left(1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g}^{\text{FN}})\right)\right)\Bigg{]}$

###### Proof.

Distributing out like terms in the expression for the Lagrangian in Definition
15 gives us

$\displaystyle L_{f}(h,\lambda)$
$\displaystyle=\mathbb{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}\ell(h(x),0)-\gamma\sum_{g\in\mathcal{G}}(\lambda_{g}^{+}+\lambda_{g}^{-})$
$\displaystyle\quad+f(x)\left(\ell(h(x),1)-\ell(h(x),0)+\ell(h(x),1)\sum_{g\in\mathcal{G}}(\lambda^{+}_{g}(g(x)-\beta_{g})+\lambda^{-}_{g}(\beta_{g}-g(x))\right)\Bigg{]}$
$\displaystyle=\mathbb{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}\ell(h(x),0)-\gamma\sum_{g\in\mathcal{G}}(\lambda_{g}^{+}+\lambda_{g}^{-})$
$\displaystyle\quad+f(x)\left(-\ell(h(x),0)+\ell(h(x),1)\left(1+\sum_{g\in\mathcal{G}}(\lambda_{g}^{+}-\lambda_{g}^{-})(g(x)-\beta_{g})\right)\right)\Bigg{]}.$

Recall that $\lambda_{g}=\lambda_{g}^{+}-\lambda_{g}^{-},$ so we are done. ∎

######  Lemma 6.

The optimal post-processed classifier $h$ of $\psi(f,\gamma,\mathcal{H}_{A}$)
for some regressor $f$ takes the following form:

$h(x)=\begin{cases}1,&\text{if
}f(x)>\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{ and
}2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})>0,\\\ 0,&\text{if
}f(x)<\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{ and
}2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})>0,\\\ 1,&\text{if
}f(x)<\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{ and
}2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})<0,\\\ 0,&\text{if
}f(x)>\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{ and
}2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})<0.\end{cases}$

In the edge case in which
$f(x)=\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}$, $h(x)$
could take either value and might be randomized.

###### Proof.

Note that since we are optimizing over the set of all binary classifiers, $h$
optimizes the Lagrangian objective pointwise for every $x$. In particular, we
have from Lemma 5 that:

$h(x)=\arg\min_{p}\left[\ell(p,0)+f(x)\left(-\ell(p,0)+\ell(p,1)\left(1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\right)\right)\right].$

In order to determine the threshold, we need to check when setting $p=1$ leads
to a value less than setting $p=0$. In other words, we need to solve for
$f(x)$ when

$\displaystyle 1-f(x)$
$\displaystyle<f(x)\left(1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\right)$
$\displaystyle\Rightarrow f(x)$
$\displaystyle>\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}.$

Thus,

$h(x)=\begin{cases}1,&\text{if
}f(x)>\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{ and
}2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})>0,\\\ 0,&\text{if
}f(x)<\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{ and
}2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})>0,\\\ 1,&\text{if
}f(x)<\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{ and
}2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})<0,\\\ 0,&\text{if
}f(x)>\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{ and
}2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})<0.\end{cases}$

∎

From Lemma 6, we can now define a best-response model and use Algorithm 2 to
generate an optimally post-processed model that preserves $\gamma-$False
Negative fairness. The algorithm’s error bounds may be derived using symmetric
arguments to sections 3.1 and 3.2, where $\hat{f}$ is required to be
$\alpha$-approximately jointly multicalibrated in expectation with respect to
$s_{\lambda}(x,v):=\mathbbm{1}[\langle\lambda,x_{\mathcal{G}}-\beta\rangle\geq(1-2v)/v]$
following the same arguments as used in Lemma 3.

Input: (_$D$ : dataset, $f:\mathcal{X}\to[0,1]$: regression function,
$\mathcal{G}$: groups, $\gamma$: tolerance on fairness violation, $C$: bound
on dual $(\|\lambda\|_{1}\leq C)$, $\eta$: learning rate_)

Initialize dual vector $\lambda^{0}={\bf 0}$ and set $T=\frac{1}{4}\cdot
C^{2}\cdot(C^{2}+4|\mathcal{G}|)^{2}$.

for  _$t=1,\ldots,T$_ do

Primal player updates $h_{t}$ $h_{t}(x)=\begin{cases}1,&\text{if
}f(x)\geq\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})>0,\\\
0,&\text{if
}f(x)<\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})>0,\\\
1,&\text{if
}f(x)<\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})<0,\\\
0,&\text{if
}f(x)\geq\frac{1}{2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})}\text{
and }2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})<0,\\\
0&\text{if
}2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})=0\end{cases}$
Compute  $\displaystyle\hat{\rho}^{t}_{g}$
$\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim
D}[\ell(h_{t}(x),1)g(x)f(x)]\text{ for all }g\in\mathcal{G},$
$\displaystyle\hat{\rho}^{t}$ $\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim
D}[\beta_{g}\ell(h_{t}(x),1)f(x)],\text{ where }\beta_{g}=\Pr[g(x)=1|y=0]$
Dual player updates  $\displaystyle\lambda_{g}^{t,+}$
$\displaystyle=\max(0,\lambda_{g}^{t,+}+\eta\cdot(\hat{\rho}^{t}_{g}-\hat{\rho}^{t}-\gamma)),$
$\displaystyle\lambda_{g}^{t,-}$
$\displaystyle=\max(0,\lambda_{g}^{t,-}+\eta\cdot(\hat{\rho}^{t}-\hat{\rho}^{t}_{g}-\gamma)).$

Dual player sets
$\lambda^{t}=\sum_{g\in\mathcal{G}}\lambda_{g}^{t,+}-\lambda_{g}^{t,-}$.

If $\|\lambda^{t}\|_{1}>C$, set
$\lambda^{t}=\arg\min_{\\{\tilde{\lambda}\in\mathbb{R}^{2\mathcal{G}}|\|\tilde{\lambda}\|_{1}\leq
C\\}}\|\lambda_{t}-\tilde{\lambda}\|_{2}^{2}$.

end for

Output:  $\bar{h}:=\frac{1}{T}\sum_{t=1}^{T}\hat{h}_{t}$, a uniformly random
classifier over all rounds’ hypotheses.

Algorithm 2 Projected Gradient Descent Algorithm for $\gamma$-False Negative
Fairness

###  A.2 Error Fairness

######  Definition 16.

We say that classifier $h:\mathcal{X}\rightarrow\mathcal{Y}$ satisfies
$\gamma$-Error (E) Fairness with respect to $\mathcal{D}$ and $\mathcal{G}$ if
for all $g\in\mathcal{G}$,

$w_{g}^{\text{E}}\left|\text{err}(h,g,\mathcal{D})-\text{err}(h,\mathcal{D})\right|\leq\gamma,$

where $w_{g}^{\text{E}}=\Pr_{(x,y)\sim\mathcal{D}}[g(x)=1]$.

We consider the following fairness-constrained optimization problem:

$\displaystyle\min_{h\in\Delta\mathcal{H}}$ $\displaystyle\text{err}(h)$ (11)
$\displaystyle\textrm{s.t. for each }g\in\mathcal{G}:$ $\displaystyle
w_{g}^{\text{E}}\left|\text{err}(h,g,\mathcal{D})-\text{err}(h,\mathcal{D})\right|\leq\gamma,$

######  Definition 17.

Let $f:\mathcal{X}\rightarrow R\subseteq[0,1]$ be some regression function and
let $\gamma\in\mathbb{R}_{+}$. Define $\psi_{\text{E}}(f,\gamma,\mathcal{H})$
to be the following optimization problem:

$\displaystyle\min_{h\in\Delta\mathcal{H}}\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[f(x)\ell(h(x),1)+(1-f(x))\ell(h(x),0)]$
$\displaystyle\textrm{s.t. for each }g\in\mathcal{G}:$
$\displaystyle|\mathbb{E}[\ell(h(x),1)g(x)f^{*}(x)+\ell(h(x),0)g(x)(1-f^{*}(x))$
$\displaystyle\quad-
w_{g}^{\text{E}}(\ell(h(x),1)f^{*}(x)-w_{g}^{\text{E}}\ell(h(x),0)(1-f^{*}(x)]|\leq\gamma,$

where $w_{g}^{\text{E}}=\Pr_{(x,y)\sim\mathcal{D}}[g(x)=1]$ as in the previous
definition.

######  Lemma 7.

Let $f^{*}$ be the Bayes optimal regression function over $\mathcal{D}$. Then
optimization problem $\psi_{\text{E}}(f^{*},\gamma,\mathcal{H})$ is equivalent
to the fairness-constrained optimization problem 11.

###### Proof.

Note that the objective function is equivalent to that of Equation 1, and
hence proof of the objectives being equivalent is identical to that of Lemma
1. For the constraints, note that

$\displaystyle
w_{g}^{\text{E}}|\text{err}(h,g,\mathcal{D})|-\text{err}(h,\mathcal{D})$
$\displaystyle=\Pr[g(x)=1]\bigg{|}\Pr[y=1|g(x)=1]\Pr[h(x)=0|g(x)=1,y=1]$
$\displaystyle\quad+\Pr[y=0|g(x)=1]\Pr[h(x)=1|g(x)=1,y=0]$
$\displaystyle\quad-(\Pr[y=1]\Pr[h(x)=0|y=1]+\Pr[y=0]\Pr[h(x)=1|y=0])\bigg{|}$
$\displaystyle=\Pr[g(x)=1]\bigg{|}\Pr[y=1|g(x)=1]\frac{\Pr[h(x)=0,g(x)=1,y=1]}{\Pr[g(x)=1,y=1]}$
$\displaystyle\quad+\Pr[y=1|g(x)=1]\frac{\Pr[h(x)=1,g(x)=1,y=0]}{\Pr[g(x)=1,y=0]}$
$\displaystyle\quad-\Pr[y=1]\frac{\Pr[h(x)=0,y=1]}{\Pr[y=1]}-\Pr[y=0]\frac{\Pr[h(x)=1,y=1]}{\Pr[y=0]}\bigg{|}$
$\displaystyle=|\mathbb{E}[\ell(h(x),1)g(x)f^{*}(x)+\ell(h(x),0)g(x)(1-f^{*}(x))$
$\displaystyle\quad-
w_{g}^{\text{E}}(\ell(h(x),1)f^{*}(x)-w_{g}^{\text{E}}\ell(h(x),0)(1-f^{*}(x)]|$

∎

######  Definition 18 (Lagrangian).

Given any regression function $f$, we define a Lagrangian of the optimization
problem $\psi_{\text{E}}(f,\gamma,\mathcal{H})$ as
$L_{f}^{\text{E}}:\mathcal{H}\times\mathbb{R}^{2|\mathcal{G}|}\rightarrow\mathbb{R}$:

$\displaystyle L_{f}^{\text{E}}(h,\lambda)$
$\displaystyle=\mathbb{E}_{x\sim\mathcal{D}_{\mathcal{X}}}\bigg{[}f(x)\ell(h(x),1)+(1-f(x))\ell(h(x),0)$
$\displaystyle\quad+\sum_{g\in\mathcal{G}}\lambda_{g}^{+}\big{(}\ell(h(x),1)g(x)f(x)+\ell(h(x),0)g(x)(1-f(x))$
$\displaystyle\quad\quad\quad\quad-
w_{g}^{\text{E}}\ell(h(x),1)f(x)-w_{g}^{\text{E}}\ell(h(x),0)(1-f(x))-\gamma\big{)}$
$\displaystyle\quad+\sum_{g\in\mathcal{G}}\lambda_{g}^{-}\big{(}w_{g}^{\text{E}}\ell(h(x),1)f(x)+w_{g}^{\text{E}}\ell(h(x),0)(1-f(x))$
$\displaystyle\quad\quad\quad\quad-\ell(h(x),1)g(x)f(x)-\ell(h(x),0)g(x)(1-f(x))-\gamma\big{)}\bigg{]}.$

######  Lemma 8.

$\displaystyle L^{\text{E}}_{f}(h,\lambda)$
$\displaystyle=\mathbb{E}_{x\sim\mathcal{D}_{x}}\Bigg{[}\ell(h(x),0)\bigg{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\bigg{)}-\gamma\sum_{g\in\mathcal{G}}(\lambda^{+}_{g}+\lambda^{-}_{g})$
$\displaystyle\quad+f(x)\Bigg{(}-\ell(h(x),0)\bigg{[}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\bigg{]}$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad+\ell(h(x),1)\bigg{[}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\bigg{]}\Bigg{)}\Bigg{]}$

###### Proof.

Distribute out like terms as shown previously. ∎

######  Lemma 9.

The optimal post-processed classifier $h$ of $\psi(f,\gamma,\mathcal{H}_{A}$)
for some regressor $f$ takes the following form:

$h(x)=\begin{cases}1,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}\text{
and }2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})>0,\\\
0,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}\text{
and }2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})>0,\\\
1,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}\text{
and }2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})<0,\\\
0,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}\text{
and
}2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})>0.\end{cases}$

In the edge case in which
$f(x)=\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})},h(x)$
could take either value and might be randomized.

###### Proof.

Note that since we are optimizing over the set of all binary classifiers, $h$
optimizes the Lagrangian objective pointwise for every $x$. In particular, we
have from Lemma 8 that:

$\displaystyle h(x)$
$\displaystyle=\arg\min_{p}\Bigg{[}\ell(p,0)\bigg{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\bigg{)}$
$\displaystyle\quad+f(x)\Bigg{(}-\ell(p,0)\bigg{[}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\bigg{]}+\ell(p,1)\bigg{[}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\bigg{]}\Bigg{)}\Bigg{]}$

Setting $p=0$ makes the inner portion of the expression evaluate to

$f(x)\Bigg{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\Bigg{)},$

and setting $p=1$ makes the inner portion of the expression evaluate to

$\bigg{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\bigg{)}-f(x)\Bigg{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\Bigg{)}$

In order to find the optimal $h$, we want to find the threshold at which
setting $p=1$ minimizes the expression, and hence:

$\displaystyle\bigg{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\bigg{)}-f(x)\Bigg{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\Bigg{)}$
$\displaystyle<f(x)\Bigg{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\Bigg{)}$
$\displaystyle\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{\Bigg{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\Bigg{)}+\Bigg{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})\Bigg{)}}$
$\displaystyle<f(x)$
$\displaystyle\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}$
$\displaystyle<f(x)$

Thus,

$h(x)=\begin{cases}1,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}\text{
and }2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})>0,\\\
0,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}\text{
and }2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})>0,\\\
1,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}\text{
and }2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})<0,\\\
0,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})}\text{
and
}2+2\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})>0.\end{cases}$

∎

From Lemma 9, we can now define a best-response model and use Algorithm 3 to
generate an optimally post-processed model that preserves $\gamma-$Error
fairness. The algorithm’s error bounds may be derived using symmetric
arguments to sections 3.1 and 3.2, where $\hat{f}$ is $\alpha$-multicalibrated
in expectation with respect to $\mathcal{G},\mathcal{H},$ and
$\mathcal{G}\times\mathcal{H}$ and is jointly multicalibrated with respect to
functions of the form:

$\mathbbm{1}\left[\langle\lambda^{t-1},x_{\mathcal{G}}-w^{\text{E}}\rangle\geq\frac{2v-1}{1-2v}\right]$

the proofs from section 3.2 may be modified to get its desired error bounds.

Input: (_$D$ : dataset, $f:\mathcal{X}\to[0,1]$: regression function,
$\mathcal{G}$: groups, $\gamma$: tolerance on fairness violation, $C$: bound
on dual $(\|\lambda\|_{1}\leq C)$, $\eta$: learning rate_)

Initialize dual vector $\lambda^{0}={\bf 0}$ and set $T=\frac{1}{4}\cdot
C^{2}\cdot(C^{2}+4|\mathcal{G}|)^{2}$.

for  _$t=1,\ldots,T$_ do

Primal player updates $h_{t}$

$h_{t}(x)=\begin{cases}1,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})}\text{
and }2+2\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})>0,\\\
0,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})}\text{
and }2+2\sum_{g^{t-1}\in\mathcal{G}}\lambda_{g}(g(x)-w_{g}^{\text{E}})>0,\\\
1,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})}\text{
and }2+2\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})<0,\\\
0,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})}{2+2\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})}\text{
and }2+2\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})>0,\\\
1,&\text{if
}2+2\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-w_{g}^{\text{E}})=0.\end{cases}$
Compute  $\displaystyle\hat{\rho}^{t}_{g}$
$\displaystyle=\mathbb{E}_{(x,y)\sim
D}[\ell(h_{t}(x),1)g(x)f(x)+\ell(h_{t}(x),0)g(x)(1-f(x))$ $\displaystyle\quad-
w_{g}^{\text{E}}(\ell(h_{t}(x),1)f(x)-w_{g}^{\text{E}}\ell(h_{t}(x),0)(1-f(x)]\text{
for all }g\in\mathcal{G},$ $\displaystyle\hat{\rho}^{t}$
$\displaystyle=\mathbb{E}_{(x,y)\sim
D}[f(x)\ell(h_{t}(x),1)+(1-f(x))\ell(h_{t}(x),0)],$

where $w_{g}^{\text{E}}=\Pr_{(x,y)\sim\mathcal{D}}[g(x)=1]$.

Dual player updates  $\displaystyle\lambda_{g}^{t,+}$
$\displaystyle=\max(0,\lambda_{g}^{t,+}+\eta\cdot(\hat{\rho}^{t}_{g}-\hat{\rho}^{t}-\gamma)),$
$\displaystyle\lambda_{g}^{t,-}$
$\displaystyle=\max(0,\lambda_{g}^{t,-}+\eta\cdot(\hat{\rho}^{t}-\hat{\rho}^{t}_{g}-\gamma)).$

Dual player sets
$\lambda^{t}=\sum_{g\in\mathcal{G}}\lambda_{g}^{t,+}-\lambda_{g}^{t,-}$.

If $\|\lambda^{t}\|_{1}>C$, set
$\lambda^{t}=\arg\min_{\\{\tilde{\lambda}\in\mathbb{R}^{2\mathcal{G}}|\|\tilde{\lambda}\|_{1}\leq
C\\}}\|\lambda_{t}-\tilde{\lambda}\|_{2}^{2}$.

end for

Output:  $\bar{h}:=\frac{1}{T}\sum_{t=1}^{T}\hat{h}_{t}$, a uniformly random
classifier over all rounds’ hypotheses.

Algorithm 3 Projected Gradient Descent Algorithm for $\gamma$-Error Fairness

###  A.3 Statistical Parity Fairness

######  Definition 19.

We say that classifier $h:\mathcal{X}\rightarrow\mathcal{Y}$ satisfies
$\gamma$-Statistical Parity (SP) Fairness with respect to $\mathcal{D}$ and
$\mathcal{G}$ if for all $g\in\mathcal{G}$,

$\Pr_{(x,y)\sim\mathcal{D}}[g(x)=1]\left|\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[h(x)|g(x)=1]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[h(x)]\right|\in\gamma.$

We consider the following fairness-constrained optimization problem:

$\displaystyle\min_{h\in\Delta\mathcal{H}}$ $\displaystyle\text{err}(h)$ (12)
$\displaystyle\textrm{s.t. for each }g\in\mathcal{G}:$
$\displaystyle\Pr[g(x)=1]\left|\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[h(x)|g(x)=1]-\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[h(x)]\right|\leq\gamma,$

######  Definition 20.

Let $f:\mathcal{X}\rightarrow R\subseteq[0,1]$ be some regression function and
let $\gamma\in\mathbb{R}_{+}$. Define $\phi_{\text{SP}}(f,\gamma,\mathcal{H})$
to be the following optimization problem:

$\displaystyle\min_{h\in\Delta\mathcal{H}}$
$\displaystyle\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[f(x)\ell(h(x),1)+(1-f(x))\ell(h(x),0)]$
$\displaystyle\textrm{s.t. for each }g\in\mathcal{G}:$
$\displaystyle\left|\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[h(x)g(x)]-w_{g}^{\text{SP}}\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[h(x)]\right|\leq\gamma$

where $w_{g}^{\text{SP}}=\Pr[g(x)=1]$.

######  Lemma 10.

Let $f^{*}$ be the Bayes optimal regression function over $\mathcal{D}$. Then
optimization problem $\psi_{\text{SP}}(f^{*},\gamma,\mathcal{H})$ is
equivalent to the fairness-constrained optimization problem 12.

######  Definition 21 (Lagrangian).

Given any regression function $f$, we define a Lagrangian of the optimization
problem $\psi_{\text{SP}}(f,\gamma,\mathcal{H})$ as
$L_{f}^{\text{SP}}:\mathcal{H}\times\mathbb{R}^{2|\mathcal{G}|}\rightarrow\mathbb{R}$:

$\displaystyle L_{f}^{\text{SP}}(h,\lambda)$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\bigg{[}f(x)\ell(h(x),1)+(1-f(x))(\ell(h(x),0)$
$\displaystyle\quad\quad+\sum_{g\in\mathcal{G}}\lambda^{+}_{g}\big{(}h(x)(g(x)-1)-\gamma\big{)}+\sum_{g\in\mathcal{G}}\lambda^{-}_{g}\big{(}h(x)(1-g(x)\big{)}-\gamma)\bigg{]}.$

######  Lemma 11.

The optimal post-processed classifier $h$ of
$\psi_{\text{SP}}(f,\gamma,\mathcal{H}_{A}$) for some regressor $f$ takes the
following form:

$h(x)=\begin{cases}1,&\text{if
}f(x)>1/2+(1/2)\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-1),\\\ 0,&\text{if
}f(x)<1/2+(1/2)\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-1).\end{cases}$

In the edge case in which
$f(x)=1/2+(1/2)\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-1)$, $h(x)$ could take
either value and might be randomized.

###### Proof.

Note that we can rewrite our Lagrangian from Definition 21 as

$L_{f}^{\text{SP}}(h,\lambda)=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[f(x)(\ell(h(x),1)-\ell(h(x),0))+\ell(h(x),0)+h(x)\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-1)+\gamma\sum_{g\in\mathcal{G}}(\lambda^{+}+\lambda^{-})\right],$

and hence our optimal $h$ will be optimal pointwise, i.e.

$h(x)\arg\min_{p}\left[f(x)(\ell(p,1)+\ell(p,0))-\ell(p,0)+p\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-1)\right]$

We can then find our threshold by comparing this expression when $p=0$ and
$p=1$, i.e.

$\displaystyle-f(x)+1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-1)$
$\displaystyle<f(x)$
$\displaystyle\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-1)}{2}$
$\displaystyle<f(x).$

Hence,

$h(x)=\begin{cases}1,&\text{if
}f(x)>1/2+(1/2)\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-1),\\\ 0,&\text{if
}f(x)<1/2+(1/2)\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-1).\end{cases}$

∎

We can now define a best-response model and use Algorithm 4 to generate an
optimally post-processed model that preserves $\gamma$-Statistical Parity
fairness. Assuming that $\hat{f}$ is $\alpha$-multicalibrated in expectation
with respect to $\mathcal{G},\mathcal{H},$ and $\mathcal{G}\times\mathcal{H}$
and is jointly multicalibrated with respect to functions of the form
$\mathbbm{1}[\langle\lambda,x_{\mathcal{G}}-\beta\rangle\geq 2v-1]$, the
proofs from section 3.2 may be modified to get its desired error bounds.

Input: (_$D$ : dataset, $f:\mathcal{X}\to[0,1]$: regression function,
$\mathcal{G}$: groups, $\gamma$: tolerance on fairness violation, $C$: bound
on dual $(\|\lambda\|_{1}\leq C)$, $\eta$: learning rate_)

Initialize dual vector $\lambda^{0}={\bf 0}$ and set $T=\frac{1}{4}\cdot
C^{2}\cdot(C^{2}+4|\mathcal{G}|)^{2}$.

for  _$t=1,\ldots,T$_ do

Primal player updates $h_{t}$

$h_{t}(x)=\begin{cases}1,&\text{if }f(x)\geq
1/2+(1/2)\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-1),\\\ 0,&\text{if
}f(x)<1/2+(1/2)\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-1).\end{cases}$

Compute

$\displaystyle\hat{\rho}^{t}_{g}$
$\displaystyle=\left|\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[h_{t}(x)g(x)]-w_{g}^{\text{SP}}\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[h_{t}(x)]\right|\text{
for all }g\in\mathcal{G},$ $\displaystyle\hat{\rho}^{t}$
$\displaystyle=\mathbb{E}_{(x,y)\sim
D}[f(x)\ell(h_{t}(x),1)+(1-f(x))\ell(h_{t}(x),0)],$

where $w_{g}^{\text{SP}}=\Pr[g(x)=1]$.

Dual player updates  $\displaystyle\lambda_{g}^{t,+}$
$\displaystyle=\max(0,\lambda_{g}^{t,+}+\eta\cdot(\hat{\rho}^{t}_{g}-\hat{\rho}^{t}-\gamma)),$
$\displaystyle\lambda_{g}^{t,-}$
$\displaystyle=\max(0,\lambda_{g}^{t,-}+\eta\cdot(\hat{\rho}^{t}-\hat{\rho}^{t}_{g}-\gamma)).$

Dual player sets
$\lambda^{t}=\sum_{g\in\mathcal{G}}\lambda_{g}^{t,+}-\lambda_{g}^{t,-}$.

If $\|\lambda^{t}\|_{1}>C$, set
$\lambda^{t}=\arg\min_{\\{\tilde{\lambda}\in\mathbb{R}^{2\mathcal{G}}|\|\tilde{\lambda}\|_{1}\leq
C\\}}\|\lambda_{t}-\tilde{\lambda}\|_{2}^{2}$.

end for

Output:  $\bar{h}:=\frac{1}{T}\sum_{t=1}^{T}\hat{h}_{t}$, a uniformly random
classifier over all rounds’ hypotheses.

Algorithm 4 Projected Gradient Descent Algorithm for $\gamma$-Statistical
Parity Fairness

###  A.4 Achieving All Fairness Notions

Ideally, we would like our function to be multicalibrated so that we can
achieve any fairness notion downstream. Putting everything together from the
previous sections, we can do so.

######  Definition 22 (Set of thresholding functions $\mathcal{B}(C)$).

Let $x_{\mathcal{G}}\in\\{0,1\\}^{|\mathcal{G}|}$ denote the group membership
indicator vector of some point $x$, and define the following functions:

$\displaystyle d^{\text{FP}}(v)$ $\displaystyle:=\frac{2v-1}{1-v},$
$\displaystyle d^{\text{FN}}(v)$ $\displaystyle:=\frac{1-2v}{v},$
$\displaystyle d^{\text{E}}(v)$ $\displaystyle:=\frac{2v-1}{1-2v},$
$\displaystyle d^{\text{SP}}(v)$ $\displaystyle:=2v-1.$

Then, for any $\lambda,x,\beta$, let

$\displaystyle s^{\text{FP}}_{\lambda}(x,v)$
$\displaystyle:=\mathbbm{1}[\langle\lambda,x_{\mathcal{G}}-\beta^{\text{FP}}\rangle\geq
d^{\text{FP},\text{E}}(v)],$ $\displaystyle s^{\text{FN}}_{\lambda}(x,v)$
$\displaystyle:=\mathbbm{1}[\langle\lambda,x_{\mathcal{G}}-\beta^{\text{FN}}\rangle\geq
d^{\text{FN}}(v)],$ $\displaystyle s^{\text{E}}_{\lambda}(x,v)$
$\displaystyle:=\mathbbm{1}[\langle\lambda,\alpha
x_{\mathcal{G}}-w^{\text{E}}\rangle\geq d^{\text{E}}(v)],$ $\displaystyle
s^{\text{SP}}_{\lambda}(x,v)$
$\displaystyle:=\mathbbm{1}[\langle\lambda,x_{\mathcal{G}}-1\rangle\geq
d^{\text{SP}}(v)],$

where

$\displaystyle\beta^{\text{FP}}$
$\displaystyle=\\{\Pr_{(x,y)\sim\mathcal{D}}\left[g(x)=1|y=0\right]\\}_{g\in\mathcal{G}},$
$\displaystyle\beta^{\text{FN}}$
$\displaystyle=\\{\Pr_{(x,y)\sim\mathcal{D}}\left[g(x)=1|y=1\right]\\}_{g\in\mathcal{G}},$
$\displaystyle w^{\text{E}}$
$\displaystyle=\\{\Pr_{(x,y)\sim\mathcal{D}}[g(x)=1]\\}_{g\in\mathcal{G}}.$

Define
$\mathcal{B}(C)=\\{s^{\text{FP}}_{\lambda}|\lambda\in\Lambda(C)\\}\cup\\{s^{\text{FN}}_{\lambda}|\lambda\in\Lambda(C)\\}\cup\\{s^{\text{E}}_{\lambda}|\lambda\in\Lambda(C)\\}\cup\\{s^{\text{SP}}_{\lambda}|\lambda\in\Lambda(C)\\}$,
where
$\Lambda(C)=\left\\{\lambda\in\mathbb{R}^{2\mathcal{G}}\big{|}\|\lambda\|_{1}\leq
C\right\\}$, as defined in Equation 2.

Then, if $f$ is multicalibrated with respect to $\mathcal{B}(C)$, any of the
projected gradient descent algorithms covered above (Algorithms 1 through 3)
may be run to achieve the desired fairness notion.

##  Appendix B Expanded Proofs and Section 3 Discussion

See 1

###### Proof.

We confirm that the objective and constraints are both equivalent. First the
objective:

$\displaystyle err(h)$
$\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\ell(h(x),y)\right]$
$\displaystyle=\sum_{(x,y)\in\mathcal{X}\times\mathcal{Y}}\Pr\left(X=x,Y=y\right)\ell(h(x),y)$
$\displaystyle=\sum_{x\in\mathcal{X}}\Pr\left(X=x,Y=0\right)\ell(h(x),0)+\Pr\left(X=x,Y=1\right)\ell(h(x),1)$
$\displaystyle=\mathop{\mathbb{E}}_{x\in\mathcal{X}}[(1-f^{*}(x))\ell(h(x),0)+f^{*}(x)\ell(h(x),1)]$

For the constraints, note that

$\displaystyle w_{g}|\rho_{g}(h)-\rho(h)|$
$\displaystyle=\Pr[g(x)=1,y=0]\left|\Pr[h(x)=1|g(x)=1,y=0]-\Pr[h(x)=1|y=0]\right|$
$\displaystyle=\Pr[g(x)=1,y=0]\bigg{|}\frac{\Pr[h(x)=1,g(x)=1,y=0]}{\Pr[g(x)=1,y=0]}-\frac{\Pr[h(x)=1,y=0]}{\Pr[Y=0]}\bigg{|}$
$\displaystyle=\left|\Pr[h(x)=1,g(x)=1,y=0]-\frac{\Pr[g(x)=1,y=0]\Pr[h(x)=1,y=0]}{\Pr[Y=0]}\right|$
$\displaystyle=\left|\mathbb{E}[\ell(h(x),0)g(x)(1-f^{*}(x))]-\frac{\Pr[g(x)=1,y=0]}{\Pr[Y=0]}\mathbb{E}\left[\ell(h(x),0)(1-f^{*}(x))\right]\right|$
$\displaystyle=\left|\mathbb{E}[\ell(h(x),0)g(x)(1-f^{*}(x))]-\Pr[g(x)=1|Y=0]\mathbb{E}\left[\ell(h(x),0)(1-f^{*}(x))\right]\right|$
$\displaystyle=\left|\mathbb{E}[\ell(h(x),0)g(x)(1-f^{*}(x))]-\beta_{g}\mathbb{E}\left[\ell(h(x),0)(1-f^{*}(x))\right]\right|.$

The result follows. ∎

######  Lemma 12.

$\displaystyle L_{f}(h,\lambda)$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}\ell(h(x),0)\Big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\Big{)}-\gamma\sum_{g\in\mathcal{G}}(\lambda_{g}^{+}+\lambda_{g}^{-})$
$\displaystyle\quad-f(x)\Big{(}-\ell(h(x),1)+\ell(h(x),0)\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}\Big{)}\Bigg{]}.$

###### Proof.

Distributing out like terms in the expression for the Lagrangian in Definition
8 gives us

$\displaystyle L_{f}(h,\lambda)$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}f(x)\ell(h(x),1)+(1-f(x))\ell(h(x),0)$
$\displaystyle\quad+\sum_{g\in\mathcal{G}}\lambda_{g}^{+}\big{(}\ell(h(x),0)g(x)(1-f(x))-\beta_{g}\ell(h(x),0)(1-f(x))-\gamma\big{)}$
$\displaystyle\quad+\lambda_{g}^{-}\big{(}\beta_{g}\ell(h(x),0)(1-f(x))-\ell(h(x),0)g(x)(1-f(x))-\gamma\big{)}\Bigg{]}$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}\ell(h(x),0)\Big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}^{+}(g(x)-\beta_{g})+\lambda_{g}^{-}(\beta_{g}-g(x))\Big{)}-\gamma\sum_{g\in\mathcal{G}}(\lambda_{g}^{+}+\lambda_{g}^{-})$
$\displaystyle\quad-f(x)\Big{(}-\ell(h(x),1)+\ell(h(x),0)\big{(}1+\sum_{g\in\mathcal{G}}\lambda^{+}_{g}(g(x)-\beta_{g})+\sum_{g\in\mathcal{G}}\lambda^{-}_{g}(\beta_{g}-g(x))\big{)}\Big{)}\Bigg{]}$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}\ell(h(x),0)\Big{(}1+\sum_{g\in\mathcal{G}}(\lambda^{+}_{g}-\lambda^{-}_{g})(g(x)-\beta_{g})\Big{)}-\gamma\sum_{g\in\mathcal{G}}(\lambda_{g}^{+}+\lambda_{g}^{-})$
$\displaystyle\quad-f(x)\Big{(}-\ell(h(x),1)+\ell(h(x),0)\big{(}1+\sum_{g\in\mathcal{G}}(\lambda^{+}_{g}-\lambda^{-}_{g})(g(x)-\beta_{g})\big{)}\Big{)}\Bigg{]}.$

Recall that $\lambda_{g}=\lambda_{g}^{+}-\lambda_{g}^{-},$ so we are done. ∎

See 2

###### Proof.

Note that since we are optimizing over the set of all binary classifiers, $h$
optimizes the Lagrangian objective pointwise for every $x$. In particular, we
have from Lemma 12 that:

$h(x)=\arg\min_{p}\Bigg{[}\ell(p,0)\Big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\Big{)}-f(x)\Big{(}-\ell(p,1)+\ell(p,0)\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}\Big{)}\Bigg{]}.$

Determining the optimal threshold is equivalent to determining when the above
expression with $\ell(p,0)=1$ and $\ell(p,1)=0$ is less than $f(x)$, i.e.

$\displaystyle
1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})-f(x)\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}$
$\displaystyle<f(x)$ $\displaystyle
1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})$
$\displaystyle<f(x)\left(1+\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}\right).$

Thus,

$h(x)=\begin{cases}1,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g}))>0,\\\ 0,&\text{if
}f(x)<\frac{1,+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g}))>0\\\ 1,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g}))<0,\\\ 0,&\text{if
}f(x)>\frac{1,+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g}))<0\end{cases}$

∎

In Lemma 2, we can only describe the optimal post-processed classifier for
cases where either $f(x)$ is less than or greater than the threshold
$\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}$,
$h(x)$. In practice, our algorithm will need to update $h$ at round $t$
according to the current dual variables $\lambda$ in a way that is well-
defined for all values of $f(x)$. Hence, we define our best response as
follows, where ties between $f(x)$ and the threshold are broken by rounding to
1.

######  Definition 23 (Best Response Model).

Given regressor $f$ and dual variables $\lambda$, let the best response $h$ be
defined as

$h(x)=\begin{cases}1,&\text{if
}f(x)\geq\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g}))>0,\\\ 0,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g}))>0,\\\ 1,&\text{if
}f(x)\leq\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g}))<0,\\\ 0,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g}))<0.\end{cases}$

######  Lemma 13.

For any regression model $f$ and dual variables $\lambda$, The classifier $h$
defined in Definition 23 is a “best response” in the sense that:

$h\in\arg\min_{h\in\mathcal{H}_{A}}L_{f}(h,\lambda).$

###  B.1 Proofs from Section 3.1

See 1 See 3

To prove this, we will use the following result from Freund and Shapire.

######  Theorem 5 (Freund and Schapire [1996]).

(Approximately solving a game). If
$\lambda_{1},\ldots,\lambda_{T}\in\Delta_{\lambda}$ is the sequence of
distributions over $\lambda$ played by the dual player and
$h_{1},\ldots,h_{T}\in\mathcal{H}$ is the sequence of best-response hypotheses
played by the primal player satisfying regret guarantees

$\displaystyle\frac{1}{T}\max_{\lambda\in\Lambda}\sum_{t=1}^{T}U(h_{t},\lambda)$
$\displaystyle-\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\lambda\sim\lambda_{t}}[U(h_{t},\lambda)]\leq\Delta_{1}$
and
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\lambda\sim\lambda_{t}}[U(h_{t},\lambda)]$
$\displaystyle-\frac{1}{T}\min_{h\in\mathcal{H}}\sum_{t=1}^{T}\mathop{\mathbb{E}}_{\lambda\sim\lambda_{t}}[U(h,\lambda)]\leq\Delta_{2}$

then the time-average of the two players’ empirical distributions is a
$(\Delta_{1}+\Delta_{2})-$approximate equilibrium.

###### Proof of Theorem 3.

We follow the regret analysis of Zinkevich [2003]. To instantiate their
result, we need a bound on the norm of the gradients of the loss function and
on the diameter of the feasible set $F$. First, we see that at each step the
gradient of the loss seen by gradient descent is bounded:

$\displaystyle\|\nabla\ell\|^{2}=\sum_{g\in\mathcal{G}}w_{g}\left(\rho_{g}-\rho-\gamma\right)^{2}+w_{g}\left(-\rho_{g}+\rho-\gamma\right)^{2}\leq
2|\mathcal{G}|.$

Second, we see that if we consider the feasible set such that
$\|\lambda\|\leq\frac{1}{\epsilon}$, then $\|F\|^{2}=\frac{1}{\epsilon^{2}}$.
Thus we have that the regret of the dual player is bounded:

$\displaystyle\mathcal{R}(T)$
$\displaystyle\leq\frac{\|F\|^{2}\sqrt{T}}{2}+(\sqrt{T}-\frac{1}{2})\|\nabla\ell\|^{2}$
$\displaystyle\frac{\mathcal{R}(T)}{T}$
$\displaystyle\leq\frac{1}{T}\left(\frac{\frac{1}{\epsilon^{2}}\sqrt{T}}{2}+(\sqrt{T}-\frac{1}{2})2|\mathcal{G}|\right)\leq\frac{\frac{1}{\epsilon^{2}}+4|\mathcal{G}|}{2\sqrt{T}}.$

After
$T=\frac{1}{4\epsilon^{2}}\left(\frac{1}{\epsilon^{2}}+4|\mathcal{G}|\right)^{2}$
rounds, by Freund and Schapire [1996] the average over empirical distributions
of play of the dual and primal players, $\bar{\lambda}$ and $\bar{h}$,
respectively, form an $\epsilon-$approximate equilibrium solution to the zero-
sum game defined by 2. ∎

###### Proof of Theorem 1.

Applying Theorems 2 and 3, we have that after $T$ rounds
$(\bar{h},\bar{\lambda})$ is an $\epsilon$-approximate equilibrium to the
zero-sum game of 2 and equivalently a minimax solution to the
$\Lambda$-bounded Lagrangian. Taking $\epsilon=1/C,$ the solution
$(\bar{h},\bar{\lambda})$ is a $\frac{1+2\epsilon}{1/\epsilon}=1/C+2/C^{2}$
approximate solution to the original linear program 1. ∎

###  B.2 Proofs from Section 3.2

See 3

###### Proof.

Recall from Lemma 13 and Algorithm 1 that the best response to $\lambda$ that
the primal player can make is to compute $h$ based on the thresholding of the
expression

$\tau=\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})}.$

Setting this threshold to be greater than or equal to some value $v$, note the
following is implied:

$\displaystyle\frac{1+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})}$
$\displaystyle\geq v,$
$\displaystyle\Rightarrow\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})-v\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})$
$\displaystyle\geq 2v-1,$
$\displaystyle\Rightarrow(1-v)(\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})$
$\displaystyle\geq 2v-1,$
$\displaystyle\Rightarrow\langle\lambda^{t-1},x_{\mathcal{G}}-\beta\rangle=\sum_{g\in\mathcal{G}}\lambda_{g}^{t-1}(g(x)-\beta_{g})$
$\displaystyle\geq\frac{2v-1}{1-v}.$

Thus, taking the indicator of

$\mathbbm{1}[\langle\lambda^{t-1},x_{\mathcal{G}}-\beta\rangle\geq d(v)]$

is equivalent to determining if the threshold $\tau$ is greater than or equal
to some $v$, and hence by the definition of $s_{\lambda^{t-1}}(x,v)$ in
Definition 11 and of the best response $h$ in Definition 23, if $v$ is set to
$f(x)$ it follows that

$h(x)=s_{\lambda^{t-1}}(x,f(x)).$

∎

See 4

In order to prove this, we will proceed through the specifics of each line of
the proof sketch in the section 3.2 through Lemmas 14 through 20.

######  Lemma 14 (Equality in Equation 3).

$err(h^{*})=L^{*}(h^{*},\lambda^{*})$

###### Proof.

Consider the optimal solution $(h^{*},\lambda^{*})$ to
$\psi(f^{*},\gamma,\mathcal{H})$, and recall that
$\text{err}(h)=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[f^{*}(x)\ell(h(x),1)+(1-f^{*}(x))\ell(h(x),0)]$.
Since the solution is optimal, it follows from complementary slackness, for
each group $g$ one of the following must hold: Either the constraint is
exactly tight and so its “violation” term in the Lagrangian evaluates to 0, or
its corresponding dual variables $\lambda^{\pm}_{g}=0$. Thus,
$L_{f}^{*}(h^{*},\lambda^{*})$ simplifies to

$\displaystyle L_{f}^{*}(h^{*},\lambda^{*})$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\bigg{[}f(x)\ell(h(x),1)+(1-f(x))\ell(h(x),0)$
$\displaystyle\quad+0\cdot\sum_{g\in\mathcal{G}}\lambda_{g}^{+}\big{(}\ell(h(x),0)g(x)(1-f(x))-\beta_{g}\ell(h(x),0)(1-f(x))-\gamma\big{)}$
$\displaystyle\quad+0\cdot\sum_{g\in\mathcal{G}}\lambda_{g}^{-}\big{(}\beta_{g}\ell(h(x),0)(1-f(x))-\ell(h(x),0)g(x)(1-f(x))-\gamma\big{)}\bigg{]}$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\bigg{[}f(x)\ell(h(x),1)+(1-f(x))\ell(h(x),0)\bigg{]}$
$\displaystyle=\text{err}(h^{*})$

∎

######  Lemma 15 (Bounding Equation 3 by Equation 4).

$L^{*}(h^{*},\lambda^{*})\geq L^{*}(h^{*},\hat{\lambda}).$

###### Proof.

This follows from the dual optimality condition that
$\lambda^{*}\in\arg\max_{\lambda}L^{*}(h^{*},\lambda)$. ∎

######  Lemma 16 (Bounding Equation 4 by Equation 5).

Fix any $\lambda$. If $\hat{f}$ is $\alpha$-multicalibrated with respect to
$\mathcal{G},\mathcal{H},$ and $\mathcal{G}\times\mathcal{H}=\\{g(x)\cdot
h(x)|g\in\mathcal{G},h\in\mathcal{H}\\}$, then then we have

$\left|\hat{L}(h^{*},\lambda)-L^{*}(h^{*},\lambda)\right|\leq\alpha(3+2\|\lambda\|_{1}).$

###### Proof.

Observe that we can write:

$\hat{L}(h,\lambda)=L_{1}(h,\lambda)-\gamma\sum_{g\in\mathcal{G}}(\lambda_{g}^{+}+\lambda_{g}^{-})-\hat{L}_{2}(h,\lambda),$

where

$\displaystyle L_{1}(h,\lambda)$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}\ell(h(x),0)\Big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\Big{)}\Bigg{]},$
$\displaystyle\hat{L}_{2}(h,\lambda)$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}\hat{f}(x)\Big{(}-\ell(h(x),1)+\ell(h(x),0)\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}\Big{)}\Bigg{]}.$

Similarly, we can write:

$L^{*}(h,\lambda)=L_{1}(h,\lambda)-\gamma\sum_{g\in\mathcal{G}}(\lambda_{g}^{+}+\lambda_{g}^{-})-L_{2}^{*}(h,\lambda),$

where

$L_{2}^{*}(h,\lambda)=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}f^{*}(x)\Big{(}-\ell(h(x),1)+\ell(h(x),0)\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}\Big{)}\Bigg{]}.$

Observe that the $L_{1}$ term does not depend on $\hat{f}$ or $f^{*}$ and so
is common between $\hat{L}$ and $L^{*}$. We can bound $\hat{L}_{2}$ as
follows:

$\displaystyle\hat{L}_{2}(h^{*},\lambda)$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}\hat{f}(x)\Big{(}-\ell(h^{*}(x),1)+\ell(h^{*}(x),0)\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}\Big{)}\Bigg{]}$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\Bigg{[}\hat{f}(x)\Big{(}-(1-h^{*}(x))+h^{*}(x)\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}\Big{)}\Bigg{]}$
$\displaystyle=\sum_{v\in
R}\quad\Pr[\hat{f}(x)=v]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}\Bigg{[}\hat{f}(x)\Big{(}-(1-h^{*}(x))+h^{*}(x)\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}\Big{)}\Bigg{|}\hat{f}(x)=v\Bigg{]}$
$\displaystyle\leq\sum_{v\in
R}\quad\Pr[\hat{f}(x)=v]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}\Bigg{[}f^{*}(x)\Big{(}-(1-h^{*}(x))+h^{*}(x)\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}\Big{)}\Bigg{|}\hat{f}(x)=v\Bigg{]}$
$\displaystyle\quad+\alpha\left(3+\sum_{g\in\mathcal{G}}\lambda_{g}(1+\beta_{g})\right)$
$\displaystyle\leq
L_{2}^{*}(h^{*},\lambda)+\alpha\left(3+2\|\lambda\|_{1}\right),$

where the first inequality follows from the fact that $h^{*}\in\mathcal{H}$
and $\hat{f}$ is multicalibrated with respect to $\mathcal{G},\mathcal{H},$
and $\mathcal{G}\times\mathcal{H}$, which we verify below:

$\displaystyle\sum_{v\in R}$
$\displaystyle\quad\Pr[\hat{f}(x)=v]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}\Bigg{[}\bigg{(}f^{*}(x)-\hat{f}(x)\bigg{)}\cdot\Big{(}-(1-h^{*}(x))+h^{*}(x)\big{(}1+\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\big{)}\Big{)}\Bigg{|}\hat{f}(x)=v\Bigg{]}$
$\displaystyle=\sum_{v\in
R}\Pr[\hat{f}(x)=v]\Bigg{[}\bigg{(}f^{*}(x)-\hat{f}(x)\bigg{)}\cdot\Big{(}-1+2h^{*}(x)+h^{*}(x)\sum_{g\in\mathcal{G}}\lambda_{g}(g(x)-\beta_{g})\Big{)}\Bigg{|}\hat{f}(x)=v\Bigg{]}$
$\displaystyle=-\sum_{v\in
R}\Pr[\hat{f}(x)=v]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}\Big{[}\hat{f}^{*}(x)-\hat{f}(x)\big{|}\hat{f}(x)=v\Big{]}$
$\displaystyle\quad+2\sum_{v\in
R}\Pr[\hat{f}(x)=v]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}\Big{[}(f^{*}(x)-\hat{f}(x))h^{*}(x)\big{|}\hat{f}(x)=v\Big{]}$
$\displaystyle\quad+\sum_{v\in
R}\Pr[\hat{f}(x)=v]\sum_{g\in\mathcal{G}}\lambda_{g}\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}\Big{[}(f^{*}(x)-\hat{f}(x))h^{*}(x)g(x)\big{|}\hat{f}(x)=v\Big{]}$
$\displaystyle\quad-\sum_{v\in
R}\Pr[\hat{f}(x)=v]\sum_{g\in\mathcal{G}}\lambda_{g}\beta_{g}\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}\Big{[}(f^{*}(x)-\hat{f}(x))h^{*}(x)\big{|}\hat{f}(x)=v\Big{]}$
$\displaystyle\leq
3\alpha+\sum_{g\in\mathcal{G}}\lambda_{g}(1+\beta_{g})\alpha$
$\displaystyle\leq
3\alpha+\alpha\sum_{g\in\mathcal{G}}\lambda_{g}(1+\max_{g^{\prime}\in\mathcal{G}}\beta_{g^{\prime}})$
$\displaystyle\leq 3\alpha+\alpha\sum_{g\in\mathcal{G}}\lambda_{g}(1+1)$
$\displaystyle\leq 3\alpha+2\|\lambda\|_{1}\alpha$

Similarly, we can show that
$L^{*}(h^{*},\lambda)-\hat{L}(h^{*},\lambda)\leq\alpha\left(3+2\|\lambda\|_{1}\right)$.
Putting everything together, we get that:

$\left|\hat{L}(h^{*},\lambda)-L^{*}(h^{*},\lambda)\right|\leq\alpha(3+2\|\lambda\|_{1}).$

This concludes the proof. ∎

######  Lemma 17 (Bounding Equation 5 by Equation 6).

$\hat{L}(h^{*},\hat{\lambda})\geq\hat{L}(\hat{h},\hat{\lambda})$

###### Proof.

This follows from the primal optimality condition that
$\hat{h}\in\arg\min_{h\in\mathcal{H}_{A}}\hat{L}(h,\hat{\lambda})$ and that
$\mathcal{H}\subseteq\mathcal{H}_{A}$. ∎

######  Lemma 18 (Equality of Equation 6 and Equation 7).

$\hat{L}(\hat{h},\hat{\lambda})=\widehat{\text{err}}(\hat{h})$

###### Proof.

This follows the same complimentary slackness argument as the proof of Lemma
14. ∎

######  Lemma 19 (Bound of Equation 7 by Equation 8).

Consider $\bar{h}$ output by algorithm 1 after $T=\frac{1}{4}\cdot
C^{2}\cdot\left(C^{2}+4|\mathcal{G}|\right)^{2}$ rounds. Then,

$\widehat{\text{err}}(\hat{h})+2/C\geq\widehat{\text{err}}(\bar{h})$

###### Proof.

This follows directly from Theorem 1. ∎

######  Lemma 20 (Bound of Equation 8 by Equation 9).

Let $\hat{f}$ be $\alpha$-approximately jointly multicalibrated with respect
to $\mathcal{B}(C)$. Then,

$\left|\widehat{\text{err}}(\bar{h})-\text{err}(\bar{h})\right|\leq 2\alpha.$

###### Proof.

Since $\bar{h}$ is a randomized model that mixes uniformly over model
$\hat{h}_{t}$ for $t\in[T]$, it suffices to show that for every $t\in[T]$,

$\displaystyle\left|\widehat{\text{err}}(\hat{h}_{t})-\text{err}(\hat{h}_{t})\right|\leq
2\alpha.$

We can compute:

$\displaystyle\widehat{\text{err}}(\hat{h}_{t})$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}\left[\hat{f}(x)\ell(\hat{h}_{t},1)+(1-\hat{f}(x))\ell(\hat{h}_{t}(x),0)\right],$
$\displaystyle=\sum_{v\in
R}\Pr[\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=0]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[\hat{f}(x)\ell(\hat{h}_{t}(x),1)+(1-\hat{f}(x))\ell(\hat{h}_{t}(x),0)|\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=0],$
$\displaystyle+\sum_{v\in
R}\Pr[\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[\hat{f}(x)\ell(\hat{h}_{t}(x),1)+(1-\hat{f}(x))\ell(\hat{h}_{t}(x),0)|\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1].$

By Lemma 3, $\hat{h}_{t}(x)=s_{\lambda^{t-1}}(x,\hat{f}(x))$, and so in
particular conditioning on $\hat{f}(x)=v$ and $s_{\lambda^{t-1}}(x,v)$ fixes
the value of $\hat{h}_{t}(x)$. So, we can rewrite the above as

$\displaystyle\widehat{\text{err}}(\hat{h}_{t})$ $\displaystyle=\sum_{v\in
R}\Pr[\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=0]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[\hat{f}(x)|\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=0]$
$\displaystyle+\sum_{v\in
R}\Pr[\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[1-\hat{f}(x)|\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1]$
$\displaystyle\leq\sum_{v\in
R}\Pr[\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=0]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[f^{*}(x)|\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=0]+\alpha$
$\displaystyle+\sum_{v\in
R}\Pr[\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{\mathcal{X}}}[1-f^{*}(x)|\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1]+\alpha$
$\displaystyle=\mathop{\mathbb{E}}_{x\sim
D_{\mathcal{X}}}[f^{*}(x)\ell(\hat{h}_{t}(x),1)+(1-f^{*}(x))\ell(\hat{h}_{t}(x),0)]+2\alpha$
$\displaystyle=\text{err}(\hat{h}_{t})+2\alpha,$

where the inequality comes from our $\alpha$-approximate joint
multicalibration guarantee. The same argument yields the opposite direction,
so we are done. ∎

We now have the tools to prove our main theorem.

###### Proof of Theorem 4.

Applying lemmas 14 through 20 gives us

$\displaystyle\text{err}(h^{*})$ $\displaystyle=$ $\displaystyle
L^{*}(h^{*},\lambda^{*})\quad(\text{Lemma \ref{lem:eqfirst}})$ (13)
$\displaystyle\geq$ $\displaystyle L^{*}(h^{*},\hat{\lambda})\quad(\text{Lemma
\ref{lem:eqsecond}})$ (14) $\displaystyle\geq$
$\displaystyle\hat{L}(h^{*},\hat{\lambda})-\alpha(3+2\|\lambda\|_{1})\quad(\text{Lemma
\ref{lem:Lagr-closeness}})$ (15) $\displaystyle\geq$
$\displaystyle\hat{L}(\hat{h},\hat{\lambda})-\alpha(3+2\|\lambda\|_{1})\quad(\text{Lemma
\ref{lem:lhats}}),$ (16)

and

$\displaystyle\hat{L}(\hat{h},\hat{\lambda})$ $\displaystyle=$
$\displaystyle\widehat{\text{err}}(\hat{h})\quad(\text{Lemma
\ref{lem:LhattoErr}})$ (17) $\displaystyle\geq$
$\displaystyle\widehat{\text{err}}(\bar{h})-2/C\quad(\text{Lemma
\ref{lem:barh}})$ (18) $\displaystyle\geq$
$\displaystyle\text{err}(\bar{h})-2/C-2\alpha\quad(\text{Lemma \ref{lem:error-
closeness}}).$ (19)

Putting this all together gives us

$\displaystyle\text{err}(h^{*})$
$\displaystyle\geq\text{err}(\bar{h})-\alpha(3+2\|\lambda\|_{1})-2/C-2\alpha$
$\displaystyle=\text{err}(\bar{h})-\alpha(5+2\|\lambda\|_{1})-2/C$
$\displaystyle\geq\text{err}(\bar{h})-\alpha(5+2C)-2/C$

We want to set $C$ to minimize this discrepancy. Noting that the derivative of
$\alpha(5+2C)+2/C$ with respect to $C$ is $2\alpha-2/C^{2}$, we get a
minimization at $C=\sqrt{1/\alpha}$.

Setting $C$ as such gives the desired bound:

$\displaystyle\text{err}(h^{*})$
$\displaystyle\geq\text{err}(\bar{h})-\alpha(5+2\sqrt{1/\alpha})-2\sqrt{\alpha}.$

Following a similar analysis as Lemma 20, we can bound the fairness
constraints on $\bar{h}$ by bounding them for the model $\hat{h}_{t}$ found at
every round $t\in[T]$ of algorithm 1.

$\displaystyle\hat{\rho}_{g}$
$\displaystyle(\hat{h}_{t})-\hat{\rho}(\hat{h}_{t})=\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}[(1-\hat{f}(x))\ell(\hat{h}_{t}(x),0)g(x)]-\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}[(1-\hat{f}(x))\ell(\hat{h}_{t}(x),0)]$
$\displaystyle=\sum_{v\in
R}\Pr[\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=0]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}[(1-\hat{f}(x))\ell(\hat{h}_{t}(x),0)\cdot(g(x)-1)|\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=0]$
$\displaystyle\quad+\Pr[\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}[(1-\hat{f}(x))\ell(\hat{h}_{t}(x),0)\cdot(g(x)-1)|\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1]$
$\displaystyle=\sum_{v\in
R}\Pr[\hat{f}(x)=v,s_{\lambda^{t-1},\geq}(x,v)=1]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}[(1-\hat{f}(x))\ell(\hat{h}_{t}(x),0)\cdot(g(x)-1)|\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1]$
$\displaystyle\leq\sum_{v\in
R}\Pr[\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1]\mathop{\mathbb{E}}_{x\sim\mathcal{D}_{x}}[(1-f^{*}(x))\ell(\hat{h}_{t}(x),0)\cdot(g(x)-1)|\hat{f}(x)=v,s_{\lambda^{t-1}}(x,v)=1]+\alpha$
$\displaystyle=\mathop{\mathbb{E}}_{x\in\mathcal{D}_{x}}[(1-f^{*}(x))\ell(h_{t}(x),0)\cdot(g(x)-1)]+\alpha$
$\displaystyle=\rho_{g}(h_{t})-\rho(h_{t})+\alpha.$

Here, the inequality comes from our multicalibration guarantees. We can repeat
the same argument in the opposite direction, and get that

$w_{g}\left|\rho_{g}(h^{*})-\rho(h^{*})\right|\geq
w_{g}\left|\rho_{g}(\bar{h})-\rho(\bar{h})\right|-w_{g}\alpha.$

∎

##  Appendix C Achieving Joint Multicalibration

In this section we give an algorithm that can take as input any model
$f:\mathcal{X}\to[0,1]$ and transform it into a new model
$\hat{f}:\mathcal{X}\to R$ such that $\hat{f}$ achieves multicalibration in
expectation with respect to a class of functions
$\mathcal{C}_{1}\subset\\{0,1\\}^{\mathcal{X}}$ and simultaneously, joint
multicalibration in expectation with respect to a class of functions
$\mathcal{C}_{2}\subset\\{0,1\\}^{\mathcal{X}\times R}$ where
$R=\\{0,\frac{1}{m},\frac{2}{m},\dots,1\\}$ for some $m>0$. Our algorithm can
be viewed as a variant of the original multicalibration algorithm of Hébert-
Johnson et al. [2018] (our variant achieves the stronger guarantee of
calibration in expectation, first defined in Gopalan et al. [2022]), or a
simplification of the split-and-marge algorithm of Gopalan et al. [2022],
which replaces the “merge” operation with simple per-update rounding.

First we observe that without loss of generality, we can focus on achieving
joint multicalibration for a single class of functions. To see this, note that
given $\mathcal{C}_{1}\subset\\{0,1\\}^{\mathcal{X}}$, we can transform it
into an identical class of two argument functions that simply ignore their
second argument:

$\mathcal{C}^{\prime}_{2}=\\{\text{$c$ where $c(x,v)=c_{1}(x)$ for every
$c_{1}\in\mathcal{C}_{1}$}\\}.$

Note that if $\hat{f}$ is $\alpha$-approximately joint-multicalibrated with
respect to $\mathcal{C}^{\prime}_{2}$, then it is $\alpha$-approximately
multicalibrated with respect to $\mathcal{C}_{1}$ and vice versa. In other
words, in order to be simultaniously multicalibrated with respect to
$\mathcal{C}_{1}$ _and_ joint-multicalibrated with respect to
$\mathcal{C}_{2}$, it is sufficient (actually equivalent) to be joint-
multicalibrated with respect to $\mathcal{C}_{2}\cup\mathcal{C}^{\prime}_{2}$.
Therefore, we focus on enforcing joint-multicalibration with respect to
arbitrary $\mathcal{C}\subset\\{0,1\\}^{\mathcal{X}\times[0,1]}$.

Before we describe the algorithm, we define the round operation. Write
$[\frac{1}{m}]=\\{0,\frac{1}{m},\frac{2}{m},\dots,1\\}$ for any $m>0$. We let
$f^{\prime}=Round(f,m)$ to denote the function that simply rounds the output
of $f$ to the nearest grid point of $[1/m]$. Similarly, we write
$Round(v,m)=\arg\min_{v^{\prime}\in[1/m]}|v^{\prime}-v|$ to denote the grid
point of $[\frac{1}{m}]$ closest to $v$.

Input: (_$\alpha,f,\mathcal{C}$_)

$m=\frac{1}{\alpha}$

$f_{0}=Round(f,m)$

$t=0$

while  _there exists a $c\in\mathcal{C}$ such that: _ $\sum_{v\in
R}\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[f_{t}(x)=v,c(x,v)=1]\left(v-\Pr_{(x,y)\sim\mathcal{D}}[y|f_{t}(x)=v,c(x,v)=1]\right)^{2}\geq\alpha$
__ do

Let  $\displaystyle(v_{t},c_{t})$ $\displaystyle=\arg\max_{v\in
R,c\in\mathcal{C}}\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[f_{t}(x)=v,c(x,v)=1]\cdot\left(v-\Pr_{(x,y)\sim\mathcal{D}}[y|f_{t}(x)=v,c(x,v)=1]\right)^{2}$
$\displaystyle S_{t}$
$\displaystyle=\\{x\in\mathcal{X}:f_{t}(x)=v,c_{t}(x,v_{t})=1\\}$
$\displaystyle\tilde{v}_{t}$
$\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[y|x\in S_{t}]$
$\displaystyle v^{\prime}_{t}$ $\displaystyle=Round(\tilde{v}_{t},m)$ Let
$f_{t+1}(x)=\begin{cases}v^{\prime}_{t}\quad\text{if $x\in S_{t}$}\\\
f_{t}(x)\quad\text{otherwise}.\end{cases}$

$t=t+1$

end while

Algorithm 5 Multicalibration algorithm

######  Theorem 6.

The output of Algorithm 5 $f_{T}:\mathcal{X}\to\\{0,\alpha,2\alpha,\dots,1\\}$
is $\sqrt{\alpha}$-approximately jointly multicalibrated with respect to
$\mathcal{C}$ where $T\leq\frac{4}{\alpha^{2}}$.

###### Proof.

By definition, the output of the algorithm $f_{T}$ is such that

$\sum_{v\in
R}\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[f_{t}(x)=v,c(x,v)=1]\left(v-\Pr_{(x,y)\sim\mathcal{D}}[y|f_{t}(x)=v,c(x,v)=1]\right)^{2}<\alpha$

for every $c\in\mathcal{C}$, meaning it is satisfies $\sqrt{\alpha}$-joint
calibration:

$\displaystyle\sum_{v\in
R}\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[f_{t}(x)=v,c(x,v)=1]\left|v-\Pr_{(x,y)\sim\mathcal{D}}[y|f_{t}(x)=v,c(x,v)=1]\right|$
$\displaystyle\leq\sqrt{\sum_{v\in
R}\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[f_{t}(x)=v,c(x,v)=1]\left(v-\Pr_{(x,y)\sim\mathcal{D}}[y|f_{t}(x)=v,c(x,v)=1]\right)^{2}}$
$\displaystyle<\sqrt{\alpha}.$

So it suffices to show that the algorithm halts in less than
$T\leq\frac{4}{\alpha^{2}}$ rounds. Define

$B(f)=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[(y-f(x))^{2}].$

We use $B$ as a potential function and show that we decrease it in each round
in the following lemma.

######  Lemma 21.

For every $t<T$, $B(f_{t+1})-B(f_{t})\leq-\frac{\alpha^{2}}{4}$

###### Proof.

Define $\tilde{f}_{t}$ such that

$\tilde{f}_{t}(x)=\begin{cases}\tilde{v}_{t}\quad&\text{if $x\in B_{t}$}\\\
f_{t}(x)\quad&\text{otherwise}.\end{cases}$ $\displaystyle
B(f_{t+1})-B(f_{t})=\underbrace{\left(B(f_{t+1})-B(\tilde{f}_{t})\right)}_{(*)}+\underbrace{\left(B(\tilde{f}_{t})-B(f_{t})\right)}_{(**)}$

#### Bounding (*):

$\displaystyle B(f_{t+1})-B(\tilde{f}_{t})$
$\displaystyle=\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[x\in
S_{t}]\cdot\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[(y-f_{t+1}(x))^{2}-(y-\tilde{f}_{t}(x))^{2}|x\in
S_{t}]$ $\displaystyle=\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[x\in
S_{t}]\cdot\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[((y-\tilde{f}_{t}(x))+(\tilde{v}_{t}-v^{\prime}_{t}))^{2}-(y-\tilde{f}_{t}(x))^{2}|x\in
S_{t}]$ $\displaystyle=\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[x\in
S_{t}]\cdot\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[2(y-\tilde{v}_{t})(\tilde{v}_{t}-v^{\prime}_{t})+(\tilde{v}_{t}-v^{\prime}_{t})^{2}|x\in
S_{t}]$ $\displaystyle\leq\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[x\in
S_{t}]\cdot\frac{1}{4m^{2}}$

where the last inequality follows from the fact that
$\tilde{v}_{t}=\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[y|x\in S_{t}]$ and
$|\tilde{v}_{t}-v^{\prime}_{t}|\leq\frac{1}{2m}$.

#### Bounding (**):

Because in round $t$,

$\sum_{v\in
R}\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[f_{t}(x)=v,c(x,v)=1]\left(v-\Pr_{(x,y)\sim\mathcal{D}}[y|f_{t}(x)=v,c(x,v)=1]\right)^{2}\geq\alpha,$

we must have

$\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[x\in
S_{t}]\left(v_{t}-\tilde{v}_{t}\right)^{2}=\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[x\in
S_{t}]\left(v_{t}-\Pr_{(x,y)\sim\mathcal{D}}[y|x\in
S_{t}]\right)^{2}\geq\frac{\alpha}{m+1}.$

Now,we show that

$\displaystyle B(\tilde{f}_{t})-B(f_{t+1})$
$\displaystyle=\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[x\in
S_{t}]\cdot\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[(y-\tilde{f}_{t}(x))^{2}-(y-f_{t}(x))^{2}|x\in
S_{t}]$ $\displaystyle=\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[x\in
S_{t}]\cdot\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[(y-\tilde{f}_{t}(x))^{2}-((y-\tilde{f}_{t}(x))+(\tilde{v}_{t}-v_{t}))^{2}|x\in
S_{t}]$ $\displaystyle=\Pr_{x\sim\mathcal{D}_{\mathcal{X}}}[x\in
S_{t}]\cdot\mathop{\mathbb{E}}_{(x,y)\sim\mathcal{D}}[-2(y-\tilde{v}_{t})(\tilde{v}_{t}-v_{t})-(\tilde{v}_{t}-v_{t}))^{2}|x\in
S_{t}]$ $\displaystyle\leq\frac{-\alpha}{m+1}$

where the last inequality follows from the fact that
$\mathop{\mathbb{E}}_{(x,y)}[y|x\in S_{t}]=\tilde{v}_{t}$.

Combining them together, we get

$\displaystyle B(f_{t+1})-B(f_{t})$
$\displaystyle\leq\frac{1}{4m^{2}}-\frac{\alpha}{m+1}$
$\displaystyle=\frac{\alpha^{2}}{4}-\frac{\alpha^{2}}{\alpha+1}$
$\displaystyle\geq\frac{\alpha^{2}}{4}-\frac{\alpha^{2}}{2}$
$\displaystyle=-\frac{\alpha^{2}}{4}.$

∎

Iterating Lemma 21 over $T$ rounds, we have

$B(f_{T})\leq B(f_{0})-T\frac{\alpha^{2}}{4}.$

Also, because $B(f)\in[0,1]$ for any $f$, it must be that
$T\leq\frac{4}{\alpha^{2}}$. ∎

##  Appendix D Out of Sample Guarantees

In the body of the paper, we assumed that we had direct access to
distributional quantities — in particular, we needed to evaluate expectations
over the feature distribution. In this section, we show that it is possible to
estimate these quantities from modest amounts of unlabeled data sampled from
the underlying distribution, and that the guarantees of our algorithm carry
over to the underlying distribution. In particular, our algorithm results in a
solution to the linear program that approximately satisfies its constraints on
the underlying distribution, and achieves objective value that is
approximately optimal within its comparison class. The strategy we take is to
analyze a slightly modified algorithm (Algorithm 6), which at every stage,
uses a fresh sample of data to evaluate the necessary expectations
empirically. In particular, it uses a _new_ sample at every iteration, and so
has sample complexity that scales linearly with the number of iterations.
Using techniques from adaptive data analysis Dwork et al. [2015], Bassily et
al. [2016], Jung et al. [2021b] similar to how they are used by Hébert-Johnson
et al. [2018] to prove sample complexity bounds, we could reduce our linear
dependence on $T$ in our sample complexity bound by a quadratic factor by
reusing data across rounds, but we settle for the conceptually simpler bound
here.

######  Theorem 7.

Fix any distribution $\mathcal{D}$, hypothesis class $\mathcal{H}$, class of
group indicators $\mathcal{G}$, dual bound $C$, and $\epsilon,\delta>0$. After
$T$ rounds, with probability $1-\delta$, Algorithm 6 outputs a randomized
hypothesis $\bar{h}$ such that
$err(\bar{h})\leq\text{OPT}+\frac{2}{C}+8\epsilon$ and
$\omega_{g}|\rho_{g}(\bar{h})-\rho(\bar{h})|\leq\gamma+\frac{1}{C}+\frac{2}{C^{2}}+\frac{8\epsilon}{C}$,
where OPT is the objective value of the optimal solution of
$\psi(f,\gamma,\mathcal{H}_{A})$. It makes use of
$m=O\left(T\frac{\log(\frac{2T|G|}{\delta})}{2\epsilon^{2}}\right)$ samples of
unlabeled data drawn i.i.d. from $\mathcal{D}_{\mathcal{X}}$. Here $T$ is as
specified in the algorithm: $T=\frac{1}{4}\cdot
C^{2}\cdot(C^{2}+4|\mathcal{G}|)^{2}$.

######  Lemma 22.

Fix any distribution $\mathcal{D}$, hypothesis class $\mathcal{H}$, and class
of group indicators $\mathcal{G}$. In a single round $t$ of Algorithm 6 with
$S_{t}\sim\mathcal{D}^{m}$ for
$m=O(\frac{\log(\frac{2|G|}{\delta})}{2\epsilon^{2}})$, Algorithm 6 returns a
hypothesis $h_{t}$ that with probability $1-\delta$ satisfies for all $g\in
G$:

$\displaystyle|err(h_{t},g,\mathcal{D})-err(h_{t},g,S_{t})|$
$\displaystyle\leq\epsilon$
$\displaystyle|\rho(h_{t},g,\mathcal{D})-\rho(h_{t},g,S_{t})|$
$\displaystyle\leq\epsilon.$

Input: (_$\mathcal{D}$ : data distribution, $f:\mathcal{X}\to[0,1]$:
regression function, $\mathcal{G}$: groups, $\gamma$: tolerance on fairness
violation, $C$: bound on dual $(\|\lambda\|_{1}\leq C)$, $\eta$: learning
rate, m = $\frac{\log(\frac{2|G|}{\delta})}{2\epsilon^{2}}$: batch size of
fresh data for each round of gradient descent, $\epsilon$: per round
estimation error, $\delta$: failure probability_)

Initialize dual vector $\lambda^{0}={\bf 0}$ and set $T=\frac{1}{4}\cdot
C^{2}\cdot(C^{2}+4|\mathcal{G}|)^{2}$.

for  _$t=1,\ldots,T$_ do

Primal player updates $h_{t}$ $h_{t}(x)=\begin{cases}1,&\text{if
}f(x)\geq\frac{1+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g}))>0,\\\
0,&\text{if
}f(x)<\frac{1+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g}))>0,\\\
1,&\text{if
}f(x)\leq\frac{1+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}\text{
and }(2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g}))<0,\\\
0,&\text{if
}f(x)>\frac{1+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}{2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g})}\text{
and
}(2+\sum_{g\in\mathcal{G}}\lambda^{t-1}_{g}(g(x)-\beta_{g}))<0.\end{cases}$
Sample $S_{t}$ i.i.d. from $\mathcal{D}^{m}$ Compute
$\displaystyle\hat{\rho}^{t}_{g}$
$\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim
S_{t}}[\ell(h_{t}(x),0)g(x)(1-f(x))]\text{ for all }g\in\mathcal{G},$
$\displaystyle\hat{\rho}^{t}$ $\displaystyle=\mathop{\mathbb{E}}_{(x,y)\sim
S_{t}}[\beta_{g}\ell(h_{t}(x),0)(1-f(x))],\text{ where
}\beta_{g}=\Pr[g(x)=1|y=0]$ Dual player updates
$\displaystyle\lambda_{g}^{t,+}$
$\displaystyle=\max(0,\lambda_{g}^{t,+}+\eta\cdot(\hat{\rho}^{t}_{g}-\hat{\rho}^{t}-\gamma)),$
$\displaystyle\lambda_{g}^{t,-}$
$\displaystyle=\max(0,\lambda_{g}^{t,-}+\eta\cdot(\hat{\rho}^{t}-\hat{\rho}^{t}_{g}-\gamma)).$

Dual player sets
$\lambda^{t}=\sum_{g\in\mathcal{G}}\lambda_{g}^{t,+}-\lambda_{g}^{t,-}$.

If $\|\lambda^{t}\|_{1}>C$, set
$\lambda^{t}=C\cdot\frac{\lambda^{t}}{\|\lambda^{t}\|_{1}}$.

end for

Output:  $\bar{h}:=\frac{1}{T}\sum_{t=1}^{T}\hat{h}_{t}$, a uniformly random
classifier over all rounds’ hypotheses.

Algorithm 6 Projected Gradient Descent Algorithm

######  Theorem 8 (Chernoff-Hoeffding Bound).

Let $X_{1},X_{2},\ldots,X_{m}$ be i.i.d. random variables with $a\leq
X_{i}\leq b$ and $\mathbb{E}[X_{i}]=\mu$ for all $i$. Then, for any
$\alpha>0,$

$\displaystyle\Pr\left(\left|\frac{\sum_{i}X_{i}}{m}-\mu\right|>\alpha\right)\leq
2\exp\left(\frac{-2\alpha^{2}m}{(b-a)^{2}}\right).$

###### Proof of Lemma 22.

This claim follows by applying a Chernoff-Hoeffding bound with
$m\geq\frac{\ln(\frac{2|G|}{\delta})}{2\epsilon^{2}}$ ∎

###### Proof Sketch of Theorem 7.

Taking $m>\frac{\log(\frac{2T|G|}{\delta})}{2\epsilon^{2}}$, we have that in a
single round $t$ of our algorithm we are able to estimate the true
distributional classification and fairness constraint errors up to an additive
error of $\epsilon$ with probability $1-\delta/T$ — and hence with probability
$1-\delta$, we estimate these quantities up to additive error $\epsilon$
uniformly over all $T$ rounds. We can then make one small modification to the
analysis of Algorithm 1. First observe that since the primal player’s best
response does not depend on any estimation of a distributional quantity based
on the sample $S_{t}$, their regret is still zero, as it is in the analysis of
Algorithm 1. The dual player, on the other hand, is given loss vectors that
deviate from the versions that would have been computed on the underlying
distribution by at most $2\epsilon$ in $\ell_{\infty}$ norm, and hence
experience additional regret (to the true distributional quantities) larger
than in the analysis of Algorithm 1 by up to an additional additive
$4\epsilon$. Consequently, the equilibrium solution $(\bar{h},\bar{\lambda})$
from Algorithm 6 is an $4\epsilon+1/C$ approximate equilibrium to the zero-sum
game of 2 which then, applying Theorem 2, yields a $\frac{2}{C}+8\epsilon$
approximate solution to the objective of the original linear program. ∎

##  Appendix E Expanded Experimental Discussion

Figure 2: The plot on the left is a trajectory over 2000 iterations of
gradient descent of our method post-processing a base logistic regression
model, for a single value of $\gamma=0.003$. The trajectory starts at the top
of the figure and moves downwards with time, and the purple point represents
the uniform distribution over the constituent models of the 2000 iterations.
The plot on the right shows the Pareto curve for our method (blue) and for the
fair reductions [Agarwal et al., 2018] for constraint values ranging between
$0.0025\leq\gamma\leq 0.00355$.

We provide additional experimental evaluation on the UCI Adult dataset [Dua
and Graff, 2017]. The sensitive attributes we use are binary gender and race,
categorized as White, Black, Asian and Pacific Islander, American Indian or
Eskimo, and Other. Note that race and gender are intersecting attributes. In
these experiments our algorithm is post-processing a standard sklearn logistic
regression model, notably, as in our previous results, not guaranteed to be
multicalibrated in the ways our theory requires. We also provide a comparison
to the popular in-processing “fair reductions” method [Agarwal et al., 2018].
We note that our algorithm performs competitively, even Pareto-dominating
certain points on the reductions Pareto frontier. However, the reductions
method is also able generate points corresponding to constraint violations
that our method is not able to access — this does not violate our theoretical
findings, since we are not starting with a multicalibrated regression
function. Our method requires solving a single logistic regression problem
over the dataset (to compute the regression model $\hat{f}$ that we post-
process), whereas the method of Agarwal et al. [2018] requires solving a
regression problem at every iteration.