# Multi-group Agnostic PAC Learnability

Guy N. Rothblum
Weizmann Institute of Science
<EMAIL_ADDRESS>This project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No. 819702), from the Israel Science
Foundation (grant number 5219/17), from the U.S.-Israel Binational Science
Foundation (grant 2018102), and from the Simons Foundation Collaboration on
the Theory of Algorithmic Fairness. Part of this work was done while the
author was visiting Microsoft Research. Gal Yona
Weizmann Institute of Science
<EMAIL_ADDRESS>This project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and
innovation programme (grant agreement No. 819702), from the Israel Science
Foundation (grant number 5219/17) and from the Simons Foundation Collaboration
on the Theory of Algorithmic Fairness. This research was also partially
supported by the Israeli Council for Higher Education (CHE) via the Weizmann
Data Science Research Center and by a research grant from Madame Olga
Klein–Astrachan.

###### Abstract

An agnostic PAC learning algorithm finds a predictor that is competitive with
the best predictor in a benchmark hypothesis class, where competitiveness is
measured with respect to a given loss function. However, its predictions might
be quite sub-optimal for structured subgroups of individuals, such as
protected demographic groups. Motivated by such fairness concerns, we study
“multi-group agnostic PAC learnability”: fixing a measure of loss, a benchmark
class $\mathcal{H}$ and a (potentially) rich collection of subgroups
$\mathcal{G}$, the objective is to learn a single predictor such that the loss
experienced by every group $g\in\mathcal{G}$ is not much larger than the best
possible loss for this group within $\mathcal{H}$. Under natural conditions,
we provide a characterization of the loss functions for which such a predictor
is guaranteed to exist. For any such loss function we construct a learning
algorithm whose sample complexity is logarithmic in the size of the collection
$\mathcal{G}$. Our results unify and extend previous positive and negative
results from the multi-group fairness literature, which applied for specific
loss functions.

##  1 Introduction

Machine learning tools are used to make and inform increasingly consequential
decisions about individuals. Examples range from medical risk prediction to
hiring decisions and criminal justice. Automated classification and risk
prediction come with benefits, but they also raise substantial societal
concerns. One prominent concern is that these algorithms might discriminate
against protected and/or disadvantaged groups. In particular, a learned
predictor might perform differently on a protected subgroup compared to the
general population. The growing literature on algorithmic fairness has studied
different concerns. Many works aim to ensure parity or balance between
demographic groups, e.g. similar rates of positive predictions or similar
false positive or false negative rates [Hardt et al., 2016, Kleinberg et al.,
2016]. Other works consider accuracy guarantees, such as calibration [Dawid,
1982], for protected groups. Protections at the level of a single group might
be too weak [Dwork et al., 2012], and recent works have studied extending
these notions to the setting of multiple overlapping groups [Hébert-Johnson et
al., 2018, Kearns et al., 2018].

In this work, we focus on the setting of (supervised) agnostic learning
[Kearns et al., 1994]. Given an i.i.d. training set of labeled data, the goal
is to learn a predictor $h$ that performs well on the underlying distribution.
Performance is measured by a loss function, and with respect to a fixed class
$\mathcal{H}$: the loss incurred by the predictor $h$ should be competitive
with the best predictor in $\mathcal{H}$. To capture a wide variety of
settings, we aim to be quite general in our treatment of different loss
functions. With fairness in mind, the agnostic learning paradigm raises a
fundamental concern: since the predictor’s loss is measured over the entire
underlying distribution, it might not reflect the predictor’s performance on
sub-populations such as protected demographic groups. Indeed, it has been
demonstrated that standard machine learning tools, when applied to standard
data sets, produce predictors whose performance on protected demographic
groups is quite poor [Buolamwini and Gebru, 2018].

Motivated by these concerns, we study multi-group agnostic learning. For a
rich collection $\mathcal{G}$ of (potentially) overlapping groups, our goal is
to learn a single predictor $h$, such that the loss experienced by every group
$g\in\mathcal{G}$ (when classified by $h$) is not much larger than the loss of
the best predictor for that group in the class $\mathcal{H}$. We emphasize
that this should hold for all groups in $\mathcal{G}$ simultaneously.

To see how this objective is different from the usual agnostic PAC, consider
the simple example in which $\mathcal{H}$ is the class of hyperplanes and we
have two subgroups $S,T\subseteq\mathcal{X}$. Suppose that the data is
generated such that every group $g$ has a hyperplane $h_{g}$ that has very low
error on it (but that these are different, so e.g. $h_{T}$ has large loss on
$S$ and vice versa). This means that there is no classifier $h\in\mathcal{H}$
that perfectly labels the data. If $S$ is small compared to $T$, then the
agnostic learning objective could be satisfied by $h_{T}$, the optimal
classifier for $T$. For _multi-group_ agnostic PAC, the fact that there is
some other classifier in $\mathcal{H}$ that perfectly labels $S$ serves to
disqualify $h_{T}$ (more generally, it could be the case that no
$h\in\mathcal{H}$ will be multi-PAC). This also highlights that the multi-
group objective becomes challenging when the groups in question are
intersecting (if the groups are disjoint, we can combine the optimal
classifiers for each group [Dwork et al., 2017]).

A recent work by Blum and Lykouris [Blum and Lykouris, 2019] studied this
question in an online setting with sequential predictions. Our focus is on the
batch setting. They showed that (for every collection of groups and every
benchmark hypothesis class) it is possible to achieve competitive loss for all
groups, so long as the loss function is decomposable: the loss experienced by
each group is an average of losses experienced by its members (this result
also applies to the batch setting). On the other hand, they showed a loss
function (the average of false negative and false positive rates), for which
the objective is infeasible even in the batch setting. Since this loss is non-
decomposable (the false positive rate of a classifier depends on the negative
rate, which is a property of the entire distribution in question), one might
conjecture that the multi-group objective is only possible for decomposable
losses. However, this conjecture is false: For example, calibration [Dawid,
1982] is a non-decomposable loss that is compatible with the multi-group
objective. Indeed, [Hébert-Johnson et al., 2018] propose an algorithm that
guarantees predictions are calibrated across groups (in other words, the
calibration loss for each $g\in\mathcal{G}$ is close to zero). In particular,
the output of this algorithm would satisfy the multi-group agnostic PAC
requirement (with respect to the calibration loss, and for every hypothesis
class).

###  1.1 Our contributions

Motivated by these observations, in this work we formalize two main questions:

  1. 1.

We define a loss function as (multi-group) _compatible_ if it is “appropriate”
to use with our objective, in the sense that for every hypothesis class
$\mathcal{H}$ and collection of groups $\mathcal{G}$, there exists a
hypothesis $h$ that is competitive with $\mathcal{H}$ for every group in
$\mathcal{G}$. What makes a loss function compatible? Previous works provide
several positive and negative results, but there was no clear characterization
of compatibility.

  2. 2.

Is it always the case that for such “compatible” losses, a multi-group
predictor can also be found using a finite number of samples? In other words,
is there a separation between multi-group compatibility and multi-group
learnability?

Our main technical contributions answer both questions:

  1. 1.

We prove a partial information-theoretic characterization of the compatible
loss functions.

  2. 2.

For any such loss function that also satisfies a natural uniform convergence
property, we show an algorithm that, for any specified finite collection
$\mathcal{G}$ and finite hypothesis class $\mathcal{H}$, learns a multi-group
agnostic predictor from labeled data. The sample complexity is logarithmic in
the sizes of $\mathcal{G}$ and $\mathcal{H}$. Our algorithm is derived by a
reduction to outcome indistinguishability (OI), a learning objective recently
introduced by Dwork et al. [Dwork et al., 2020], drawing a new connection
between OI and agnostic learning. This shows that (under minimal assumptions
on the loss function), multi-group compatibility implies multi-group
learnability.

In slightly more detail, we characterize the compatible loss functions
assuming an additional unambiguity property (we refer to the characterization
as “partial” because of this assumption): we assume that once we fix a single
individual and specify the distribution of their label, there is a unique
prediction that minimizes the loss for that individual. We view this as a very
natural assumption on the loss function, see the discussion following
Definition 2.2. We show that if a loss function is compatible and unambiguous,
then for each individual, the optimal prediction can be obtained by a fixed
“local” function $f$, whose output only depends on the features and on the
marginal distribution of that individual’s label. The point is that the
function $f$ doesn’t depend on the global distribution, but the predictions
that it specifies still minimize the loss for that distribution. We call loss
functions that satisfy this property $f$-proper, and we show that (under the
unambiguity assumption) being $f$-proper is equivalent to multi-group agnostic
PAC compatibility.

We then construct a universal multi-group agnostic PAC learning algorithm for
any $f$-proper loss function that also satisfies a minimal uniform convergence
property (this is necessary for finite sample complexity). The learning
algorithm works for any specified finite hypothesis class $\mathcal{H}$ and
any finite collection of groups $\mathcal{G}$, and its sample complexity is
logarithmic in $|\mathcal{H}|$ and $|\mathcal{G}|$. The algorithm is obtained
via a reduction from multi-group agnostic PAC learning to the recently studied
task of outcome indistinguishable learning [Dwork et al., 2020]. Beyond
unifying previous work in _multi-group fairness_ , this result can be thought
of as a multi-group analogue for the known result that every PAC learnable
class is learnable via empirical risk minimization.

###  1.2 Related work

The literature on algorithmic fairness is broad and growing. Most pertinent to
our work is the literature on fairness notions that aim to stake a middle-
ground between the strong, individual-level semantics of _individual fairness_
notion [Dwork et al., 2012] and the weaker but useful _group fairness_ notions
[Hardt et al., 2016, Kleinberg et al., 2016]. We broadly refer to such notions
as _multi-group_ notions. Some of these works are geared towards guaranteeing
parity: equalizing some statistic across the (possibly exponentially-many)
subgroups in $\mathcal{G}$. For example, [Kearns et al., 2018] study multi-
group versions of both Equality of Opportunity and Demographic Parity notions
[Hardt et al., 2016]. We note however, that as the collection $\mathcal{G}$
becomes richer and richer, it might be the case multi-group parity can only be
obtained via trivial predictions or otherwise undesirable behaviour, such as
intentionally making worse predictions on some groups to achieve parity [Chen
et al., 2018]. A different line of works consider guarantees that are not
inherently in conflict with accuracy, e.g. because the Bayes optimal predictor
always satisfies multi-group fairness (regardless of $\mathcal{G}$). Notable
examples include multi-calibration [Hébert-Johnson et al., 2018] and multi-
accuracy [Kim et al., 2019], with subsequent works studying extensions in
ranking [Dwork et al., 2019], regression [Jung et al., 2020] and online
learning [Gupta et al., 2021]. As discussed above, Blum and Lykouris [Blum and
Lykouris, 2019] study multi-group agnostic PAC learning (which, depending on
the loss function, is often similarly aligned with accuracy) in the online
setting. In the batch setting, their approach for learning a multi-PAC
predictor is via the mixture of experts approach [Jacobs et al., 1991], where
the “experts” in question are a set of $\left|\mathcal{G}\right|$ predictors,
with each $h_{i}$ being the optimal predictor for group $g_{i}\in\mathcal{G}$
in the class $\mathcal{H}$. However, this approach fails to produce a multi-
PAC predictor when the loss is non-decomposable, such as calibration (this
happens even though, by [Hébert-Johnson et al., 2018], such multi-fair
predictors exist and can be found in sample complexity that scales with
$\log\left|\mathcal{G}\right|$).

#### Discussion.

The strength of the multi-group agnostic PAC guarantee depends on both the
choice of subgroups $\mathcal{G}$ and the choice of benchmark class
$\mathcal{H}$. As in the majority of the multi-group fairness literature
[Hébert-Johnson et al., 2018, Dwork et al., 2019, Kim et al., 2019], the
guarantee might be weak if the groups are not sufficiently descriptive (either
due to the features or the choice of the class $\mathcal{G}$ itself). In
Similarly, the benchmark class $\mathcal{H}$ could be insufficient (again, due
to the features or the choice of the functions in $\mathcal{H}$). Both of
these choices could be manipulated by a decision-maker with an intention to
discriminate against a certain subgroup, e.g. by deleting features that will
allow this group to be defined within $\mathcal{G}$ or by intentionally
choosing $\mathcal{H}$ to only contain bad classifiers for this group, if it
is in $\mathcal{G}$. In either case, this highlights that the multi-group
agnostic PAC guarantee should only be interpreted w.r.t the choice of
$\mathcal{G}$ and $\mathcal{H}$, and that these choices should be scrutinized
separately.

#### Organization.

The rest of this manuscript is organizes as follows. Section 2 covers the
background on our general formulation of loss functions, as well as the
learning paradigms (Agnostic PAC and Outcome Indistinguishability). In Section
3 we formalize the notions of compatibility and learnability in the multi-
group sense. Section 4 contains our main result, the equivalence between the
two notions. Full proofs are deferred to the appendices.

##  2 Preliminaries

Setup and notation. We consider binary classification problems, where
$\mathcal{X}\subseteq\mathbb{R}^{d}$ denotes a feature space and
$Y=\left\\{0,1\right\\}$ the target labels. As a general convention, we use
$\mathcal{D}$ to denote distributions over $\mathcal{X}\times Y$ and
$\mathcal{D}_{X}$ for the marginal distribution of $\mathcal{D}$ over
$\mathcal{X}$. The support of a distribution (w.r.t $\mathcal{X}$) is
$\text{supp}(\mathcal{D})=\text{supp}(\mathcal{D}_{X})$. We will sometimes be
interested in distributions over $\mathcal{X}\times Y$ for which
$\left|\text{supp}(\mathcal{D})\right|=1$, i.e. distributions that are
supported on a single element $x\in\mathcal{X}$. We refer to these as
“singleton distributions”. For a distribution $\mathcal{D}$ and an element
$x\in\mathcal{X}$, we use $\mathcal{D}_{x}$ to denote the singleton
distribution on $\mathcal{X}\times\mathcal{Y}$ obtained by restricting
$\mathcal{D}$ to $X=x$. A predictor is a mapping $h:\mathcal{X}\to[0,1]$,
where $h(x)$ is an estimate for the probability that the label of $x$ is 1. We
will sometimes consider the special case of classifiers (binary predictors),
whose range is $\left\\{0,1\right\\}$. A hypothesis class is a collection of
predictors, and is denoted by $\mathcal{H}$. A subgroup is some subset of
$\mathcal{X}$. A collection of subgroups is denoted by $\mathcal{G}$. For this
work we generally assume $\mathcal{H}$ and $\mathcal{G}$ are finite (but
possibly exponentially large in $d$). For a distribution $\mathcal{D}$ and a
group $g\subseteq\mathcal{X}$, we use $\mathcal{D}_{g}$ to denote the
distribution on $\mathcal{X}\times Y$ obtained by restricting $\mathcal{D}$ to
$x\in g$.

###  2.1 General loss functions

A loss function $L$ is some mapping from a distribution $\mathcal{D}$ and a
predictor $h$ (technically, its’ restriction to $\mathcal{D}$) to $[0,1]$. We
are typically interested in how $L$ changes as we keep the first argument (the
distribution) fixed, and only change the second argument (the predictor in
question). We thus typically use $L_{\mathcal{D}}(h)$ to denote the loss of
$h$ w.r.t. a distribution $\mathcal{D}$. For a sample
$S=\left\\{(x_{i},y_{i})\right\\}_{i=1}^{m}$ we use $L_{S}(h)$ to denote the
empirical loss, calculated as $L_{\hat{\mathcal{D}}}(h)$, where
$\hat{\mathcal{D}}$ is the empirical distribution defined by the sample $S$.
Note that this setup is extremely general, and assumes nothing about the loss
(except that it is bounded and can’t depend on what happens outside
$\mathcal{D}$). In machine learning it is common to consider more structured
losses, in which $L_{\mathcal{D}}(h)$ is the expected loss of $h$ on a random
example drawn according to $\mathcal{D}$. We refer to such structured losses
as _decomposable_ losses.

######  Definition 2.1 (Decomposable losses).

A loss function $L$ is _decomposable_ if there exists a function $\ell:X\times
Y\times[0,1]\to[0,1]$ such that for every distribution $\mathcal{D}$ and
classifier $h$, $L_{\mathcal{D}}(h)=\operatorname*{\textnormal{\bf
E}}_{(x,y)\sim\mathcal{D}}[\ell(x,y,h(x))]$.

For example, for binary classifiers a standard decomposable loss is the 0-1
loss, in which $\ell(x,y,h(x))=\textbf{1}[h(x)\neq y]$. For predictors, an
example of a standard decomposable loss is the squared loss, in which
$\ell(x,y,h(x))=(h(x)-y)^{2}$.

#### Beyond decomposable losses.

While decomposable losses are standard and common, there are many loss
functions of interest that don’t have this form – especially in the literature
on algorithmic fairness. For this reason, we focus on a general notion of loss
functions (which does not explicitly assume losses are decomposable) in our
exploration of multi-group agnostic PAC learning. Notable examples of such
losses, as used in the algorithmic fairness literature, include the following
notions:

  * •

Calibration [Hébert-Johnson et al., 2018, Kleinberg et al., 2016,
Chouldechova, 2017, Shabat et al., 2020]: A predictor is _calibrated_ if for
every value $v\in[0,1]$, conditioned on $p(x)=v$, the true expectation of the
label is close to $v$. Intuitively, this means that the outputs of the
predictor can reasonably be thought of as probabilities, and hence is a
fundamental requirement in the literature on forecasting [Dawid, 1982, Foster
and Vohra, 1998]. For example, in weather prediction, calibrated forecasts
ensure that, out of all the days on which the forecaster predicted say 0.8, it
really rained on 80% of them. Calibration loss measures the extent to which a
predictor is miscalibrated; e.g., the _expected calibration error_ [Kumar et
al., 2018] measures the deviation from calibration w.r.t a value $v$ drawn
from the distribution induced by the prediction in questions. This loss is not
decomposable because it is a global function of the predictions, not a
property of the prediction for a single $x\in\mathcal{X}$.

  * •

One-sided error rates [Hardt et al., 2016, Chouldechova, 2017, Blum and
Lykouris, 2019, Blum and Stangl, 2019, Kearns et al., 2018]: The _false
positive rate_ (similarly, false negative rate) measures the probability of a
random example being labeled as $h(x)=1$, conditioned on the true label being
$y=0$. This isn’t a decomposable loss because the exact contribution of a
single misclassification depends on the frequency of the negative labels,
which is a global property.

  * •

Individual fairness [Dwork et al., 2012, Rothblum and Yona, 2018]: Individual
fairness (IF) requires that individuals that are considered similar w.r.t the
task at hand are treated similarly by the classifier. Similarity is specified
by a metric $d:\mathcal{X}\times\mathcal{X}\to[0,1]$. If
$d(x,x^{\prime})\approx 0$ ($x,x^{\prime}$ are similar), then it should be the
case that $h(x)\approx h(x^{\prime})$. An IF loss may quantify the expected
violation of this requirement, e.g. over a draw of a pair $(x,x^{\prime})$
i.i.d from $\mathcal{D}$. This objective isn’t decomposable because the
requirement w.r.t a single $x\in\mathcal{X}$ depends on the extent to which
there are other similar $x^{\prime}$ in $\text{supp}(\mathcal{D})$.

We note that both the latter two losses (false positive rate and Individual
fairness) are typically not interesting on their own – e.g. because the
constant classifier $h\equiv 0$ minimizes them. Typically we are interested in
these losses as either an additional constraint on an existing objective, or
paired with an additional loss (e.g. IF + accuracy based loss, or false
positive rate + false negative rate).

In the rest of this section we continue to specify two minimal conditions for
the losses we consider. We will use the notation $\mathcal{L}$ for the class
of losses that satisfy both conditions. The first condition is _unambiguity_.
It guarantees that distributions over a single example $x$ have a unique loss
minimizer.

######  Definition 2.2 (Unambiguity).

A loss $L$ is unambiguous if for every singleton distribution
$\mathcal{D}_{x}$ over $\mathcal{X}\times Y$, there is a unique prediction
$h(x)$ that minimizes the loss. That is,
$\left|\arg\min_{h(x)\in[0,1]}L_{\mathcal{D}_{x}}(h)\right|=1$.

Standard decomposable losses satisfy this condition because the function
$\ell(h(x),y)$ typically has a unique minimum w.r.t its first argument. For
example when $\ell$ corresponds to the squared loss the optimal labeling is
$h(x)=\operatorname*{\textnormal{\bf E}}\left[y|x\right]$ and when $\ell$
corresponds to the expected 0-1 loss it is
$h(x)=1\left[\operatorname*{\textnormal{\bf E}}\left[y|x\right]\geq
0.5\right]$. With respect to the fairness-motivated losses mentioned above,
unambiguity fails w.r.t individual fairness and the one-sided error rates
(exactly because they can both be minimized by the constant all-zeroes
classifier, regardless of the true distribution). But as mentioned above,
these losses are rarely interesting on their own, and combined losses
(individual fairness with an unambiguous loss, or an average of false positive
rate and false negative rate) are unambiguous. In other words, all losses that
are of practical interest to us are unambiguous.

The second condition we will require is that the empirical risk $L_{S}(\cdot)$
can really be used to approximate the true risk $L_{\mathcal{D}}(\cdot)$, for
a sufficiently large sample $S$. To build up to this notion we first recall
the standard definition of uniform convergence for hypotheses classes.

######  Definition 2.3 (Uniform Convergence for hypotheses classes).

We say that a hypothesis class $\mathcal{H}$ has the uniform convergence
property (w.r.t. a domain $X\times Y$ and a loss function $L$) if there exists
a function $m^{UC}_{\mathcal{H}}:(0,1)^{2}\to\mathbb{N}$ such that for every
$\varepsilon,\delta\in(0,1)$ and for every probability distribution
$\mathcal{D}$ over $X\times Y$, if $S$ is a sample of $m\geq
m^{UC}_{\mathcal{H}}(\varepsilon,\delta)$ examples drawn i.i.d. according to
$\mathcal{D}$, then, with probability of at least $1-\delta$, $\forall
h\in\mathcal{H}:\quad\left|L_{S}(h)-L_{D}(h)\right|\leq\varepsilon$.

In our context, we will be interested in uniform convergence as a property of
the _loss function_. We will say that a loss $L$ has uniform convergence
(w.r.t finite classes) with sample complexity
$m^{UC}_{L}:(0,1)^{2}\times\mathbb{N}\to\mathbb{N}$ if every finite class
$\mathcal{H}$ has the uniform convergence property w.r.t $L$ with sample
complexity $m^{UC}_{\mathcal{H}}(\varepsilon,\delta)\leq
m^{UC}_{L}(\varepsilon,\delta,\left|\mathcal{H}\right|).$ Specifically, we
will be interested in losses that have the uniform convergence property with
sample complexity that depends polynomially on $1/\varepsilon,1/\delta$ and
$\log\left|\mathcal{H}\right|$. This gives rise to the following definition:

######  Definition 2.4 (Uniform convergence for loss functions).

A loss $L$ has the uniform convergence property (w.r.t finite classes) with
sample complexity $m^{UC}_{L}:(0,1)^{2}\times\mathbb{N}$ if there exists a
polynomial $f:\mathbb{R}^{3}\to\mathbb{N}$ such that for every
$\varepsilon,\delta\in(0,1)$ and $k\in\mathbb{N}$,

$m^{UC}_{L}(\varepsilon,\delta,k)\triangleq\max_{\mathcal{H}:\,\left|\mathcal{H}\right|=k}m^{UC}_{\mathcal{H}}(\varepsilon,\delta)\leq
f(1/\varepsilon,1/\delta,\log(k))$

The uniform convergence property is satisfied by any decomposable loss
function. This follows by a combination of Heoffding’s bound (for a single
$h$) and a union bound to get a simultaneous guarantee for every
$h\in\mathcal{H}$. Out of the fairness-motivated losses we discussed above,
only the loss
$L_{\mathcal{D}}(h)=a\cdot\mathtt{FPR}_{\mathcal{D}}(h)+b\cdot\mathtt{FNR}_{\mathcal{D}}(h)$
doesn’t have uniform convergence, as we prove in Appendix A. For calibration,
uniform convergence follows as a special case of the bounds in [Shabat et al.,
2020]; for individual fairness, the argument is similar to the standard
argument for decomposable losses, only this time the concentration argument is
w.r.t pairs of samples from $\mathcal{D}$ [Rothblum and Yona, 2018].

To summarize, we have defined a collection of “reasonable“ losses
$\mathcal{L}$ as all loss functions that are both unambiguous and have the
uniform convergence property. We have argued that of the loss functions we
discussed, this only rules out the one-sided error rate loss; see Figure 1 for
an overview.

loss | notation |  in $\mathcal{L}$?
---|---|---
decomposable | $L^{\mathtt{\ell}}_{\mathcal{D}}(h)$ | ✓
calibration | $L^{\mathtt{C}}_{\mathcal{D}}(h)$ | ✓
IF + decomposable | $a\cdot L^{\mathtt{IF}}_{\mathcal{D}}(h)+b\cdot L^{\mathtt{\ell}}_{\mathcal{D}}(h)$ | ✓
error rates | $a\cdot L^{\mathtt{FPR}}_{\mathcal{D}}(h)+b\cdot L^{\mathtt{FNR}}_{\mathcal{D}}(h)$ | ✗
Figure 1: Summary: loss functions and the set $\mathcal{L}$ (all losses that
are unambiguous and have the uniform convergence property.)

###  2.2 Learning paradigms

In this work we draw a connection between an extension of the classic notion
of agnostic PAC learnability in the presence of multiple groups and the
recently introduced complexity-theoretic inspired framework of Outcome
Indistinguishability [Dwork et al., 2020], which builds on previous work in
algorithmic fairness [Hébert-Johnson et al., 2018]. In this section we review
both of these learning paradigms, starting with agnostic PAC learnability. For
consistency, we give the definition w.r.t finite classes.

######  Definition 2.5 (Agnostic-PAC learnability).

A hypothesis class $\mathcal{H}$ is agnostic PAC learnable with respect to a
set $X\times Y$ and a loss function $L$ if there exist a function
$m_{\mathcal{H}}:(0,1)^{2}\to\mathbb{N}$ and a learning algorithm with the
following property: For every $\varepsilon,\delta\in(0,1)$ and for every
distribution $\mathcal{D}$ over $\mathcal{X}\times Y$, when running the
learning algorithm on $m\geq m_{\mathcal{H}}(\varepsilon,\delta)$ i.i.d.
examples generated by $\mathcal{D}$, the algorithm returns $h$ such that, with
probability of at least $1-\delta$ (over the choice of the $m$ training
examples),

$L_{\mathcal{D}}(h)\leq L_{\mathcal{D}}(\mathcal{H})+\varepsilon$ (1)

Additionally, the sample complexity $m_{\mathcal{H}}$ should be polynomial in
$1/\varepsilon,1/\delta$ and in $\log(\left|\mathcal{H}\right|)$.

#### Outcome indistinguishability.

A predictor $\tilde{p}:\mathcal{X}\to[0,1]$ can be viewed as providing a
generative model for outcomes, where for $x\in\mathcal{X}$ a binary outcome is
sampled as $y\sim\text{Ber}(\tilde{p}(x))$. Given a distribution $\mathcal{D}$
and a predictor $\tilde{p}$, we define the “modeled distribution”
$\tilde{\mathcal{D}}=\mathcal{D}(\tilde{p})$ as the distribution over
$\mathcal{X}\times Y$ obtained by first drawing $x$ according to the marginal
distribution of $\mathcal{D}$ on $\mathcal{X}$ and then labeling it as
$y\sim\text{Ber}(\tilde{p}(x))$. The framework of Outcome Indistinguishability
(OI) aims to guarantee that outcomes produced by $\tilde{p}$ are
indistinguishable from the true outcomes under $\mathcal{D}$. This guarantee
is formulated with respect to a fixed class $\mathcal{A}$ of distinguishers,
and the requirement is that every distinguisher $A\in\mathcal{A}$ behaves
similarly on samples from the real distribution $\mathcal{D}$ and on samples
from the “modeled distribution” $\tilde{\mathcal{D}}$.

As discussed and studied in [Dwork et al., 2020], there are several different
ways to instantiate this framework based on the power of the distinguishers.
In particular, two axes of variation are (i) the input to the distinguisher
(single sample vs multi-sample) and (ii) the access level it receives to the
predictor $\tilde{p}$ in question. In this work, we focus on multi-sample
Sample-Access OI distinguishers, where the inputs to each distinguisher
$A\in\mathcal{A}^{k}$ are $k-$tuples of the form
$\left\\{(x_{i},y_{i},\tilde{p}_{i})\right\\}_{i=1}^{k}$, where for every
$i\in[k]$, $(x_{i},y_{i})$ is sampled from either $\mathcal{D}$ or
$\tilde{\mathcal{D}}$:

######  Definition 2.6 (Outcome Indistinguishability [Dwork et al., 2020]).

Fix a distribution $\mathcal{D}$, a collection of distinguishers
$\mathcal{A}^{k}$ and $\tau>0$. A predictor $\tilde{p}:\mathcal{X}\to[0,1]$
satisfies $(\mathcal{A}^{k},\tau)$-OI if for every $A\in\mathcal{A}^{k}$,

$\left|\operatorname*{\textnormal{\bf
Pr}}_{\\{(x_{i},y_{i})\\}_{i=1}^{k}\sim\mathcal{D}^{k}}[A(\\{(x_{i},y_{i},\tilde{p}(x_{i})\\}_{i=1}^{k})=1]-\operatorname*{\textnormal{\bf
Pr}}_{\\{(x_{i},y_{i})\\}_{i=1}^{k}\sim\tilde{\mathcal{D}}^{k}}[A(\\{(x_{i},y_{i},\tilde{p}(x_{i})\\}_{i=1}^{k})=1]\right|\leq\tau$

Much like the definition of (regular) PAC learning, we say that an algorithm
_learns_ multi-sample OI if upon receiving sufficiently many i.i.d samples
from the distribution, it is guaranteed to return a predictor that is
“probably approximately” OI.

######  Definition 2.7 (OI learnability).

A family of $k$-sample distinguishers $\mathcal{A}^{k}$ is multi-sample OI
learnable with respect to $\mathcal{X}\times Y$ if there exists a function
$m_{\mathcal{A}}:(0,1)^{2}\to\mathbb{N}$ and a learning algorithm with the
following property: For every $\tau,\eta\in(0,1)$ and for every distribution
$\mathcal{D}$, when running the learning algorithm on $m\geq
m_{\mathcal{A}}(\tau,\eta)$ i.i.d example generated by $\mathcal{D}$, the
algorithm returns $h$ such that with probability at least $1-\eta$ (over the
choice of the $m$ training examples), $h$ satisfies
$(\tau,\mathcal{A}^{k})$-OI.

Additionally, the sample complexity $m_{\mathcal{A}}$ should be polynomial in
$1/\tau,1/\eta$ and in $\log(\mathcal{A}^{k})$.

Dwork _et al._ [Dwork et al., 2020] showed that every $k-$sample distinguisher
class $\mathcal{A}^{k}$ is OI-learnable. In our analysis we use the following
theorem, which bounds the sample complexity of this algorithm and follows from
[Dwork et al., 2020].

######  Theorem 2.8 (from [Dwork et al., 2020]).

Fix $\mathcal{A}^{k}$. There exists an algorithm
$\mathtt{OI}_{\mathcal{A}^{k}}$ that satisfies the requirement of Definition
(2.7), and whose sample complexity is
$O\left(\frac{k\cdot\left(\log|A^{k}|/\eta\right)}{\tau^{4}}\right)$.

##  3 Agnostic PAC with multiple groups

The objective of agnostic PAC learning is to output a predictor $h$ that
satisfies $L_{\mathcal{D}}(h)\lesssim L_{\mathcal{D}}(\mathcal{H})$ (Equation
1). Putting aside questions of computational complexity and sample complexity,
this objective is itself always feasible. In other words, regardless of the
loss in question, it can always be obtained using a learner who has full
knowledge of the distribution $\mathcal{D}$ and is not constrained in runtime.
From an information-theoretic perspective, this makes the interesting question
the question of what can be done with finite samples from $\mathcal{D}$ –
hence the focus on agnostic PAC _learnability_.

A multi-group extension of agnostic PAC asks for a predictor that satisfies
the above, but simultaneously for every group $g$ in a collection
$\mathcal{G}$: $L_{\mathcal{D}_{g}}(h)\lesssim
L_{\mathcal{D}_{g}}(\mathcal{H})$, where $\mathcal{D}_{g}$ denotes the
restriction of $\mathcal{D}$ to samples from $g$.

When $\mathcal{G}$ consists of intersecting groups, however, it is not
immediately clear that this objective is always feasible: it might not be
satisfied by _any_ predictor $h:\mathcal{X}\to[0,1]$. For a simple (but
contrived) example, let $h^{0},h^{1}$ denote the all-zeroes and all-ones
predictors, and consider a loss $L$ that specifies that
$L_{\mathcal{D}_{S}}(h^{0})=0$ and $L_{\mathcal{D}_{T}}(h^{1})=0$ (and for any
other classifier $h$, the loss of every distribution is always 1). Then the
multi-group objective w.r.t $\mathcal{G}=\left\\{S,T\right\\}$ requires that
we label the intersection $S\cap T$ as both 1 and 0, which is impossible. The
following lemma proves that this can be the case even for seemingly natural
losses, that are in the class $\mathcal{L}$ defined in Section 2.1.

######  Proposition 3.1.

There exists $L\in\mathcal{L}$ for which some problem instances (corresponding
to a distribution $\mathcal{D}$, class $\mathcal{H}$, subgroups $\mathcal{G}$
and $\varepsilon>0$) don’t admit a multi-group agnostic PAC solution. In other
words, there is no classifier $h$ for which $L_{\mathcal{D}_{g}}(h)\lesssim
L_{\mathcal{D}_{g}}(\mathcal{H})$ for every group $g\in\mathcal{G}$.

The loss in question is a weighted combination of an individual fairness loss
with an accuracy loss. We construct two intersecting groups $S$ and $T$ and a
similarity metric $d$ that specifies $d(x,x^{\prime})=0$ if and only if $x\in
S-T$ and $x^{\prime}\in S\cap T$. However, the true labels of these
individuals are different: for $x\in S-T$ the label is $y=0$ but for $x\in
S\cap T$ the label is $y=1$. This creates a situation in which group $T$ is
optimizing strictly for accuracy (and so it wants the intersection to be
labeled as $\hat{y}=1$) whereas for the group $S$ the dominating term is IF
(and so it wants everyone, and in particular the intersection, to be labeled
as $\hat{y}=0$). Thus, any classifier that is simultaneously multi-PAC w.r.t
both $T$ and $S$ must label the intersection as both $0$ and $1$, which is
impossible. See Appendix B for the full proof.

We note that [Blum and Lykouris, 2019] already demonstrated that this
impossibility occurs in the batch setting. This motivated them to focus on the
0-1 loss. However, their counter example is for the error-rate type loss we
discussed earlier, which is a fixed combination of the false positive rate and
false negative rate of a classifier. As noted in Section 2.1, this loss
doesn’t have the uniform convergence property and is therefore not in
$\mathcal{L}$. Proposition 3.1 clarifies that uniform convergence is not the
issue, and there are natural (and otherwise reasonable) losses that are not
“appropriate” to use with the multi-group objective (in the sense that even an
approximate solution is not guaranteed to exist).

In light of this discussion, we proceed to explicitly separate the question of
_feasibility_ (whether it’s always the case that some multi-group solution is
guaranteed to exist) from _learnability_ (whether we can find it with a
“reasonable” number of samples). Formally, we define two notions –
compatibility and learnability – that formalize these concepts. Importantly,
both are properties of the loss function in question, taking a universal
quantifier over the class $\mathcal{H}$ and the groups $\mathcal{G}$ (and the
other aspects of the problem instance).

######  Definition 3.2 (Multi-PAC compatibility).

We say that a loss $L$ is _multi-PAC compatible_ if for every distribution
$\mathcal{D}$, class $\mathcal{H}$, subgroups $\mathcal{G}$ and
$\varepsilon>0$, there exists $h:\mathcal{X}\to[0,1]$ such that for every
group $g\in\mathcal{G}$, $L_{\mathcal{D}_{g}}(h)\leq
L_{\mathcal{D}_{g}}(\mathcal{H})+\varepsilon$.

Multi-PAC learnability strengthens the above requirement by asking that such a
solution can also be found by a learning algorithm whose sample complexity is
constrained to depend inverse-polynomially on the parameters in question and
logarithmically on the sizes of $\mathcal{H}$ and $\mathcal{G}$.

######  Definition 3.3 (Multi-PAC learnability).

We say that a loss $L$ is _multi-PAC learnable_ with sample complexity
$m^{gPAC}_{L}:(0,1)^{3}\times\mathbb{N}^{2}\to\mathbb{N}$ if there exists a
learning algorithm with the following property: For every
$\varepsilon,\delta,\gamma\in(0,1)$, for every finite hypothesis class
$\mathcal{H}$, for every finite collection of subgroups $G\subseteq
2^{\mathcal{X}}$ and for every distribution $\mathcal{D}$ over
$\mathcal{X}\times Y$, when running the learning algorithm on $m\geq
m^{gPAC}_{L}(\varepsilon,\delta,\gamma,\left|\mathcal{H}\right|,\left|\mathcal{G}\right|)$
i.i.d. examples generated by $\mathcal{D}$, the algorithm returns $h$ such
that, with probability at least $1-\delta$ (over the choice of the $m$
training examples and the coins of the learning algorithm)
$g\in\mathcal{G}_{\gamma}$, $L_{\mathcal{D}_{g}}(h)\leq
L_{\mathcal{D}_{g}}(\mathcal{H})+\varepsilon$, where
$\mathcal{G}_{\gamma}\subseteq\mathcal{G}$ is the subset of groups whose mass
under $\mathcal{D}$ is at least $\gamma$:
$\mathcal{G}_{\gamma}=\left\\{g\in\mathcal{G}:\operatorname*{\textnormal{\bf
Pr}}_{\mathcal{D}}[x\in g]\geq\gamma\right\\}$.

Additionally, the sample complexity $m^{gPAC}_{L}$ should be polynomial in
$1/\varepsilon,1/\delta,1/\gamma$ and
$\log(\left|\mathcal{H}\right|),\log(\left|\mathcal{G}\right|)$.

##  4 Compatibility $\iff$ Learnability via OI

In this section we prove our main result: that for loss functions in
$\mathcal{L}$, multi-PAC compatibility implies also multi-PAC learnability.

######  Theorem 4.1.

If a loss $L\in\mathcal{L}$ is multi-group compatible (Definition 3.2), then
it is also multi-group learnable (Definition 3.3).

Towards proving Theorem 4.1, we introduce an additional property of loss
functions, which we define below.

######  Definition 4.2 ($f$-proper).

For a function $f:\mathcal{X}\times[0,1]\to[0,1]$, we say that a loss $L$ is
_$f$ -proper_ if for every distribution $\mathcal{D}$ on $\mathcal{X}\times
Y$, the classifier $h_{\mathcal{D}}$ given by
$h_{\mathcal{D}}(x)=f(x,\operatorname*{\textnormal{\bf
E}}_{\mathcal{D}}[y|x])$ minimizes the loss w.r.t $\mathcal{D}$:
$h_{\mathcal{D}}\in\arg\min_{h}L_{\mathcal{D}}(h)$.

Recall that proper losses (or proper scoring functions) are losses that are
minimized by the conditional expectation predictor
$x\mapsto\operatorname*{\textnormal{\bf E}}_{\mathcal{D}}[y|x]$ [Buja et al.,
2005]. Definition 4.2 is a weaker requirement that says that for every
distribution a minimizer can be obtained as some _local_ transformation of
this predictor (i.e. that does not depend on the rest of the distribution).

Recalling that we defined $\mathcal{L}$ as precisely all loss functions that
satisfy both uniform convergence and unambiguity, we see that Theorem 4.1
follows as a direct corollary of the following two lemmas.

######  Lemma 4.3.

If $L$ is unambiguous (Definition 2.2) and multi-group compatible (Definition
3.2), then $L$ is $f$-proper (Definition 4.2).

######  Lemma 4.4.

If $L$ is $f$-proper (Definition 4.2) and has the uniform convergence property
(Definition 2.4), then $L$ is multi-group learnable (Definition 3.3).

We note that the other direction of Lemma 4.3 is also true (if a loss is
$f$-proper, it is also multi-group compatible): this follows immediately,
since labeling everyone in $\text{supp}(\mathcal{D})$ according to $f$ is
optimal – and in particular satisfies the multi-group requirement for every
$\mathcal{H}$. This means that the notion of $f-$proper provides a partial
characterization of compatibility (up to unambiguity).

The full proofs of Lemmas 4.3 and 4.4 can be found in Appendices C and D,
respectively. In the rest of this section we give an overview of both proofs.

###  4.1 Overview of Lemma 4.3

Let $L\in\mathcal{L}$ be a loss function that is multi-group compatible and
unambiguous (we do not use the uniform convergence property here). We show
that $L$ is also $f$-proper, where the function $f$ maps a singleton
distribution (specified by an input $x$ and the conditional probability that
the label is 1) to whatever prediction minimizes the loss on that
distribution. In more detail: for an input $x\in\mathcal{X}$ and a value
$z\in[0,1]$, let $\mathcal{D}_{x,z}$ be the singleton distribution over
$\\{x\\}\times\\{0,1\\}$, where the label is drawn by the Bernoulli
distribution $\text{Ber}(z)$. Let $h_{x,z}$ be the predictor that minimizes
the loss on this distribution, i.e.
$h_{x,z}=\arg\min_{h}L_{\mathcal{D}_{x,z}}(h)$, and recall that by
unambiguity, the prediction that minimizes the loss is unique, and so the
value $h_{x,z}(x)$ is well defined. We take $f(x,z)=h_{x,z}(x)$.

It remains to prove that $L$ is an $f$-proper loss function. Suppose for
contradiction that it is not: i.e., there exists a distribution $\mathcal{D}$
for which $h_{\mathcal{D}}(x)=f(x,\operatorname*{\textnormal{\bf
E}}_{\mathcal{D}}[y|x])$ does not minimize the loss, i.e. there exists some
predictor $h^{\prime}$ s.t.
$L_{\mathcal{D}}(h^{\prime})<L_{\mathcal{D}}(h_{\mathcal{D}})$. We show this
contradicts the multi-group compatibility of $L$. To see this, define a
collection of sets that includes all the singletons in the support of
$\mathcal{D}$, as well as the global set comprised of the entire support of
$\mathcal{D}$. By unambiguity, the singletons all “want” to be labeled by
$h_{D}$. On the other hand, the global set wants to be labeled by
$h^{\prime}$. Whatever predictor we pick, the loss on either the global set or
of one of the singletons will not be optimal. Thus, for the above collection
of groups $\mathcal{G}$ (comprised of all singletons plus the global set), and
for the hypothesis class $\mathcal{H}$ that includes $h_{\mathcal{D}}$ and
$h^{\prime}$, it is impossible to obtain predictions that are competitive with
$\mathcal{H}$ for all groups in $\mathcal{G}$ simultaneously.

Algorithm 1
$\mathtt{MultiGroup_{L,f}}(\epsilon,\delta,\gamma,\mathcal{H},\mathcal{G})$

1: Parameters: loss function $L$, function $f:\mathcal{X}\times[0,1]\to[0,1]$

2: Input: accuracy parameter $\epsilon\in(0,1)$, failure probability
$\delta\in(0,1)$, minimal subgroups size parameter $\gamma\in(0,1)$,
hypothesis class $\mathcal{H}$, collection of subgroups $\mathcal{G}$.

3: Output: A classifier $h$ satisfying the $(\varepsilon,\delta)$-multi-group
guarantee w.r.t $\mathcal{H}$ and $\mathcal{G}$

4: Set $\varepsilon^{\prime}=\alpha=\varepsilon/4$ and
$\delta^{\prime}=\eta=\tau=\delta/4$.

5: Set
$k_{\mathcal{G}}=m^{UC}_{L}\left(\varepsilon^{\prime},\delta^{\prime},\left|\mathcal{H}\right|+1\right)$.

6: Set $k=10\cdot\frac{1}{\gamma}\cdot\log\frac{1}{\delta^{\prime}}\cdot
k_{\mathcal{G}}$.

7: Let
$\mathcal{A}=\left\\{A^{L,f,k}_{g,h,\alpha}\,\,|\,\,g\in\mathcal{G},h\in\mathcal{H}\right\\}$
be a collection of distinguishers, as defined in Algorithm 4.

8: Invoke OI as a sub-routine to learn
$\tilde{p}\leftarrow\mathtt{OI}(\tau,\eta,\mathcal{A})$.

9: return $f(\tilde{p})$

Algorithm 2 $A^{L,f,k}_{g,h,\alpha}$ (multi-sample Sample-Access OI
distinguisher)

1: Parameters: number of samples $k\in\mathbb{N}$, group
$g\subseteq\mathcal{X}$, classifier $h:\mathcal{X}\to[0,1]$, loss function
$L$, function $f:\mathcal{X}\times[0,1]\to[0,1]$

2: Input: $\left\\{(x_{i},y_{i},p_{i})\right\\}_{i=1}^{k}$, where
$x_{i}\in\mathcal{X}$, $y_{i}\in\left\\{0,1\right\\}$ and $p_{i}\in[0,1]$

3: Output: A binary output denoting Accept/Reject

4: $I_{g}=\left\\{i:x_{i}\in g\right\\}$

5: $S_{g}=\left\\{(x_{i},y_{i})\right\\}_{i\in I_{g}}$

6: Define a predictor $f_{g}$ as
$f_{g}(x)=\begin{cases}f(x_{i},p_{i})&\exists i\in[k]\,\,\text{such
that}\,\,x=x_{i}\\\ 0&\text{otherwise}\end{cases}$ (2)

7: if $L_{S_{g}}(f_{g})<L_{S_{g}}(h)+2\alpha$ then

8: return 1

9: end if

10: return 0

###  4.2 Overview of Lemma 4.4

Given a loss function $L$ that is $f$-proper and has the uniform convergence
property, we want to construct a multi-group agnostic PAC learning algorithm
that works for any (finite) hypothesis class $\mathcal{H}$ and (finite)
collection of groups $\mathcal{G}$. The algorithm will work by a reduction to
the task of OI learning (see above): namely, we construct a collection
$\mathcal{A}$ of distinguishers, and show that any predictor $\tilde{p}$ that
is OI w.r.t this collection can be used to derive a multi-group agnostic
predictor $h$. In particular, we show that if $\tilde{p}$ is OI (w.r.t
$\mathcal{A}$), then $\tilde{h}(x)=f(x,\tilde{p}(x))$ is a multi-group
agnostic predictor (recall that $f$ is the local transformation for the
$f$-proper loss function $L$). The collection of distinguishers depends on the
loss function $L$, on the hypothesis class $\mathcal{H}$ and on the collection
of groups $\mathcal{G}$. This reduction, together with the OI learning
algorithm of Theorem 2.8 (from [Dwork et al., 2020]), gives a “universal”
multi-group agnostic learning algorithm for any $f$-proper loss function. The
algorithm is described in Figure 3.

It remains to construct the family of distinguishers $\mathcal{A}$, and to
prove the reduction. Towards this, fix a group $g\in\mathcal{G}$ and fix a
hypothesis $h\in\mathcal{H}$. We want to guarantee that the loss of the
hypothesis $\tilde{h}(x)=f(x,\tilde{p}(x))$ is competitive with the loss of
$h$, where both losses are measured on the distribution $\mathcal{D}_{g}$ over
members of the group $g$. We begin by observing that this is true when the
labels are drawn by $\tilde{p}(x)$ (as in the distribution
$\tilde{\mathcal{D}}$). We will use OI (with an appropriately constructed
distinguisher) to ensure that it is also true for the “real” distribution
$\mathcal{D}_{g}$.

In more detail, since $L$ is an $f$-proper loss function, we have:
$L_{\tilde{\mathcal{D}}_{g}}(\tilde{h})\leq L_{\tilde{\mathcal{D}}_{g}}(h)$,
because in $\tilde{\mathcal{D}}$ the labels are indeed generated by
$\tilde{p}$, i.e. $\tilde{p}(x)=E_{\tilde{\mathcal{D}}}[y|x]$. By uniform
convergence, this will remain true even if we consider the empirical loss over
a (sufficiently large) i.i.d. sample from $\tilde{\mathcal{D}}_{g}$. With this
in mind, we define a distinguisher $A^{k}_{g,h,\alpha}$, which takes as input
$k$ samples $\\{(x_{i},y_{i},p_{i})\\}$ and checks whether, for the samples
where $x_{i}\in g$, it is true that the loss obtained by predicting
$f(x_{i},p_{i})$ for each $x_{i}$ is competitive with the loss obtained by $h$
on those samples (up to an additive factor of $\alpha$). By the above
discussion, when the labels $y_{i}$ values are drawn by
$\text{Ber}(\tilde{p}(x_{i}))$, and assuming that there are sufficiently many
samples in $g$ to guarantee uniform convergence for the loss $L$, the
distinguisher will accept with high probability. See Figure 4 for a full
description of the distinguisher.

Now, if $\tilde{p}$ is OI w.r.t. a class that includes the distinguisher
$A^{k}_{g,h,\alpha}$, then the distinguisher should accept with similar
probabilities when the labeled examples are drawn by $\tilde{\mathcal{D}}$ or
by $\mathcal{D}$ (where in both cases $p_{i}=\tilde{p}(x_{i})$). I.e.,
$A^{k}_{g,h,\alpha}$ should also accept w.h.p. when the labeled examples are
drawn by $\mathcal{D}$. This can only happen if the predictor $\tilde{h}$ is
competitive with the hypothesis $h$ w.r.t. the distribution $\mathcal{D}_{g}$,
which is exactly the guarantee we wanted from $\tilde{h}$!

The class $\mathcal{A}$ of distinguishers includes such a distinguisher for
each $g\in\mathcal{G}$ and $h\in\mathcal{H}$, and thus if $\tilde{p}$ is OI
w.r.t. $\mathcal{A}$, we conclude that the loss of $\tilde{h}$ is competitive
with every $h\in\mathcal{H}$ for every group in $\mathcal{G}$ simultaneously.
Note that the distinguishers in $\mathcal{A}$ use multiple samples, and the
number of samples must be sufficiently large so that (for any sufficiently-
large group $g$) w.h.p. enough of them fall in $g$ to guarantee uniform
convergence.

The sample complexity of the learning algorithm is governed by the sample
complexity of OI learning, which is logarithmic in the number of
distinguishers. Since the class $\mathcal{A}$ includes
$|\mathcal{G}|\cdot|\mathcal{H}|$ distinguishers, the resulting learning
algorithm has sample complexity that is logarithmic in $|\mathcal{G}|$ and in
$|\mathcal{H}|$. We note that we need $\mathcal{G}$ and $\mathcal{H}$ to be
finite because the known OI learning algorithm works for finite collections of
distinguishers.

#### Acknowledgements.

We thank Cynthia Dwork, Michael P. Kim and Omer Reingold for fruitful
discussions throughout this work.

## References

  * [Blum and Lykouris, 2019] Blum, A. and Lykouris, T. (2019).  Advancing subgroup fairness via sleeping experts.  arXiv preprint arXiv:1909.08375.
  * [Blum and Stangl, 2019] Blum, A. and Stangl, K. (2019).  Recovering from biased data: Can fairness constraints improve accuracy?  arXiv preprint arXiv:1912.01094.
  * [Buja et al., 2005] Buja, A., Stuetzle, W., and Shen, Y. (2005).  Loss functions for binary class probability estimation and classification: Structure and applications.  Working draft, November, 3.
  * [Buolamwini and Gebru, 2018] Buolamwini, J. and Gebru, T. (2018).  Gender shades: Intersectional accuracy disparities in commercial gender classification.  In Friedler, S. A. and Wilson, C., editors, Conference on Fairness, Accountability and Transparency, FAT 2018, 23-24 February 2018, New York, NY, USA, volume 81 of Proceedings of Machine Learning Research, pages 77–91. PMLR.
  * [Chen et al., 2018] Chen, I., Johansson, F. D., and Sontag, D. (2018).  Why is my classifier discriminatory?  In Advances in Neural Information Processing Systems, pages 3539–3550.
  * [Chouldechova, 2017] Chouldechova, A. (2017).  Fair prediction with disparate impact: A study of bias in recidivism prediction instruments.  Big data, 5(2):153–163.
  * [Dawid, 1982] Dawid, A. P. (1982).  The well-calibrated bayesian.  Journal of the American Statistical Association, 77(379):605–610.
  * [Dwork et al., 2012] Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. (2012).  Fairness through awareness.  In Proceedings of the 3rd innovations in theoretical computer science conference, pages 214–226.
  * [Dwork et al., 2017] Dwork, C., Immorlica, N., Kalai, A. T., and Leiserson, M. (2017).  Decoupled classifiers for fair and efficient machine learning.  arXiv preprint arXiv:1707.06613.
  * [Dwork et al., 2019] Dwork, C., Kim, M. P., Reingold, O., Rothblum, G. N., and Yona, G. (2019).  Learning from outcomes: Evidence-based rankings.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 106–125. IEEE.
  * [Dwork et al., 2020] Dwork, C., Kim, M. P., Reingold, O., Rothblum, G. N., and Yona, G. (2020).  Outcome indistinguishability.  arXiv preprint arXiv:2011.13426.
  * [Foster and Vohra, 1998] Foster, D. P. and Vohra, R. V. (1998).  Asymptotic calibration.  Biometrika, 85(2):379–390.
  * [Gupta et al., 2021] Gupta, V., Jung, C., Noarov, G., Pai, M. M., and Roth, A. (2021).  Online multivalid learning: Means, moments, and prediction intervals.  arXiv preprint arXiv:2101.01739.
  * [Hardt et al., 2016] Hardt, M., Price, E., and Srebro, N. (2016).  Equality of opportunity in supervised learning.  In Advances in neural information processing systems, pages 3315–3323.
  * [Hébert-Johnson et al., 2018] Hébert-Johnson, Ú., Kim, M. P., Reingold, O., and Rothblum, G. (2018).  Multicalibration: Calibration for the (computationally-identifiable) masses.  In International Conference on Machine Learning, pages 1939–1948.
  * [Jacobs et al., 1991] Jacobs, R. A., Jordan, M. I., Nowlan, S. J., and Hinton, G. E. (1991).  Adaptive mixtures of local experts.  Neural computation, 3(1):79–87.
  * [Jung et al., 2020] Jung, C., Lee, C., Pai, M. M., Roth, A., and Vohra, R. (2020).  Moment multicalibration for uncertainty estimation.  arXiv preprint arXiv:2008.08037.
  * [Kearns et al., 2018] Kearns, M., Neel, S., Roth, A., and Wu, Z. S. (2018).  Preventing fairness gerrymandering: Auditing and learning for subgroup fairness.  In International Conference on Machine Learning, pages 2564–2572.
  * [Kearns et al., 1994] Kearns, M. J., Schapire, R. E., and Sellie, L. M. (1994).  Toward efficient agnostic learning.  Machine Learning, 17(2-3):115–141.
  * [Kim et al., 2019] Kim, M. P., Ghorbani, A., and Zou, J. (2019).  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.
  * [Kleinberg et al., 2016] Kleinberg, J., Mullainathan, S., and Raghavan, M. (2016).  Inherent trade-offs in the fair determination of risk scores.  arXiv preprint arXiv:1609.05807.
  * [Kumar et al., 2018] Kumar, A., Sarawagi, S., and Jain, U. (2018).  Trainable calibration measures for neural networks from kernel mean embeddings.  In International Conference on Machine Learning, pages 2805–2814. PMLR.
  * [Rothblum and Yona, 2018] Rothblum, G. and Yona, G. (2018).  Probably approximately metric-fair learning.  In International Conference on Machine Learning, pages 5680–5688. PMLR.
  * [Shabat et al., 2020] Shabat, E., Cohen, L., and Mansour, Y. (2020).  Sample complexity of uniform convergence for multicalibration.  arXiv preprint arXiv:2005.01757.

##  Appendix A $L_{\mathcal{D}}(h)=\mathtt{FPR}_{\mathcal{D}}(h)$ doesn’t have
the uniform convergence property

Recall that the false positive rate of a binary classifier can be written as

$\mathtt{FPR}_{\mathcal{D}}(h)\equiv\operatorname*{\textnormal{\bf
Pr}}\left[h(x)=1|y=0\right]$

For intuition, the fact that we condition on the event $y=0$ means that for
distributions in which the probability of this event is small, a good estimate
of the true loss will require more samples. Intuitively, this contradicts the
uniform convergence requirement that there is a single number of samples that
“works” for every distribution $\mathcal{D}$.

###### Proof.

Suppose $\mathcal{X}$ is finite and $\left|\mathcal{X}\right|=n$. Fix some
element $x^{\prime}\in\mathcal{X}$, and consider the distribution
$\mathcal{D}$ on $\mathcal{X}\times Y$ obtained by taking a uniform
distribution over $\mathcal{X}$ and labeling elements via the deterministic
labeling function

$y(x)=\begin{cases}0&x\neq x^{\prime}\\\ 1&x=x^{\prime}\end{cases}$

Consider the classifier $h$ that labels everyone as 1: $h(x)\equiv 1$. Then,
$\mathtt{FPR}_{\mathcal{D}}(h)=1$ (since there is a single negative example,
which is incorrectly labeled as a positive). On the other hand, the empirical
estimate w.r.t any sample $S\subseteq\mathcal{X}-\left\\{x^{\prime}\right\\}$
is zero, so for such a sample, the difference between $L_{S}(h)$ and
$L_{D}(h)$ is at a maximal value of 1. Recall that uniform convergence
requires us to estimate this difference to arbitrary precision with high
probability; therefore, the “bad event” in which $x\notin S$ must happen with
probability at most $\delta$. Equivalently,

$\left(\frac{n-1}{n}\right)^{m}\leq\delta$

This require taking $m$ large enough to guarantee that
$m\geq\log\frac{1}{\delta}\cdot\frac{1}{\log\frac{n}{n-1}}$. However, there is
no function $f:(0,1)\to\mathbb{N}$ that guarantees that $m\geq f(\delta)$
satisfies this condition _for every $n$_, because as $n$ approaches infinity,
$\log\frac{n}{n-1}\to 0$, so the expression is unbounded.

∎

##  Appendix B Exist $L\in\mathcal{L}$ that are not multi-group compatible

###### Proof.

For the counter-example we focus on binary classification and individual
(metric) fairness w.r.t a binary metric (i.e., that specifies for every two
individuals, whether they are identical or completely different). Fixing a
metric $d:\mathcal{X}\times\mathcal{X}\to\left\\{0,1\right\\}$, the loss
function $L$ is a combination of accuracy and individual (metric) fairness:

$\displaystyle L_{\mathcal{D}}(h)$ $\displaystyle=a\cdot
L^{IF}_{\mathcal{D}}(h)+b\cdot L^{0-1}_{\mathcal{D}}(h)$ $\displaystyle\equiv
a\cdot\operatorname*{\textnormal{\bf
Pr}}_{x,x^{\prime}\sim\mathcal{D}_{X}}\left[h(x)\neq h(x^{\prime})\land
d(x,x^{\prime})=0\right]+b\cdot\operatorname*{\textnormal{\bf
Pr}}_{x,y\sim\mathcal{D}}\left[h(x)\neq y\right]$

Let us now construct the problem instance in question. Let the domain
$\mathcal{X}$ be $\mathcal{X}=\left\\{x_{S},x_{T},x_{ST}\right\\}$, with
$\mathcal{D}_{X}$ denoting the marginal distribution on $\mathcal{X}$ in which
$x_{S}$ has probability 0.8, and $x_{T},x_{ST}$ each have probability of 0.1.
A distribution $\mathcal{D}$ is obtained as the product of $\mathcal{D}_{X}$
and $\mathcal{D}_{Y|X=x}$, where the latter assigns deterministic labels:
$y(x_{S})=0$ and $y(x_{ST})=y(x_{T})=1$. The class $\mathcal{H}$ consists of
the constant classifiers, $h^{0}$ and $h^{1}$, and the collection of groups is
$\mathcal{G}=\left\\{S,T\right\\}$ where $S=\left\\{x_{S},x_{ST}\right\\}$ and
$T=\left\\{x_{T},x_{ST}\right\\}$. Finally, the metric specifies that $x_{S}$
and $x_{ST}$ are identical, and the rest are different:

$d(x_{S},x_{ST})=0,\quad,d(x_{T},x_{ST})=1,\quad d(x_{S},x_{T})=1$

We argue that there is no classifier satisfying the multi-PAC requirement
w.r.t $\mathcal{H}$ and $\mathcal{G}$. To see this, we first note that

$L_{\mathcal{D}_{S}}(\mathcal{H})=b/9,\,\,L_{\mathcal{D}_{T}}(\mathcal{H})=0$

This is because the optimal classifier for $T$ is $h^{1}$, which is perfect
for both the accuracy and IF losses; whereas for $S$, the best classifier is
$h^{0}$, which is perfect in terms of IF and has a 0-1 loss of $1/9$.

Assume for contradiction that for every $\varepsilon>0$, there is a classifier
that satisfies the multi-PAC requirement. From the perspective of $T$, the
next-best classifier has a loss of $1/2$. So, for multi-PAC with
$\varepsilon<1/2$, it must be the case that $h(x_{ST})=1$. On the other hand,
from the perspective of $S$, when $a\gg b$ the next-best classifier has loss
$8b/9$. So, for multi-PAC with $\varepsilon<7b/9$, it must be the case that
$h(x_{ST})=0$. This means that for this problem instance and for
$\varepsilon<\min\left\\{7b/9,1/2\right\\}$, there is no classifier satisfying
the $\varepsilon$-multi-PAC requirement.

∎

##  Appendix C Proof of Lemma 4.3 (compatibility $\to$ $f$-proper)

Let $L$ be any unambiguous and compatible loss. First, we note that by
unambiguity, for any singleton distribution $\mathcal{D}$, the loss minimizer
is unique. We can therefore denote it by $h^{\star}_{\mathcal{D}}$.

Next, we make an observation that we will use in the proof: that for any
distribution $\mathcal{D}$, the classifier $h:\mathcal{X}\to[0,1]$ defined by

$h(x)=\begin{cases}h^{\star}_{\mathcal{D}_{x}}(x),&x\in\text{supp}(\mathcal{D})\\\
0,&\text{otherwise}\end{cases}$

minimizes the loss $L_{\mathcal{D}}(\cdot)$. That is, we are forming a new
classifier $h$ by predicting on an input $x\in\text{supp}(\mathcal{D})$ using
the prediction of the classifier that minimizes the loss on the distribution
$\mathcal{D}$ restricted to $x$. The claim is that this classifier is
competitive with the best possible loss on the original distribution
$\mathcal{D}$.

We claim that the observation follows as a corollary from the compatibility
assumption. Note that this is trivially the case for any singleton
distribution $\mathcal{D}$ (by unambiguity), so assume for contradiction that
there is a non-singleton distribution $\mathcal{D}$ for which the observation
does not hold. We define a multi-PAC problem instance as follows. For
$x\in\mathcal{X}$, let $g_{x}=\left\\{x\right\\}$ denote the singleton group
that consists only of $x$. Define
$\mathcal{G}_{singletons}=\left\\{g_{x}:\,\,x\in\text{supp}(\mathcal{D})\right\\}$
and
$\mathcal{H}_{singletons}=\left\\{h^{\star}_{\mathcal{D}_{x}}:\,\,x\in\text{supp}(\mathcal{D})\right\\}$.
Additionally, let $h^{\star}$ denote some classifier in
$\arg\min_{h}L_{\mathcal{D}}(h)$. Finally,

$\displaystyle\mathcal{G}$
$\displaystyle=\mathcal{G}_{singletons}\cup\left\\{\text{supp}(\mathcal{D})\right\\}$
$\displaystyle\mathcal{H}$
$\displaystyle=\mathcal{H}_{singletons}\cup\left\\{h^{\star}\right\\}$

Note that by definition, for every group $g$ in $\mathcal{G}$,
$L_{\mathcal{D}_{g}}(\mathcal{H})=0$ (because we specifically included an
optimal classifier for every group in $\mathcal{H}$). Multi-PAC for the
singleton groups $\mathcal{G}_{singeltons}$ with an arbitrarily small
precision $\varepsilon$ therefore requires that we predict
$h^{\star}_{\mathcal{D}_{x}}(x)$ for $x\in\text{supp}(\mathcal{D})$. But by
the assumption, the resulting classifier is not optimal for the group
$\left\\{\text{supp}(\mathcal{D})\right\\}$, in violation to multi-PAC w.r.t
that group. This completes the proof of the observation.

We can now use the observation to directly prove niceness. We will do this by
constructing a specific function $f$ and showing that the classifier defined
by $h_{\mathcal{D}}(x)=f(x,\operatorname*{\textnormal{\bf
E}}_{\mathcal{D}}[y|x])$ always minimizes the loss $L_{\mathcal{D}}$. Consider

$f(x,v)=h^{\star}_{\mathcal{D}_{x,v}}(x)$

where $\mathcal{D}_{x,v}$ is the singleton distribution supported on $x$ that
predicts a label of 1 w.p $v$, and $h^{\star}_{\mathcal{D}_{x,v}}$ is the loss
minimizer for this distribution (which, by unambiguity, is indeed unique).

We need to prove that $f$ satisfies the requirement in the definition of
$f-$proper. Fix some distribution $\mathcal{D}$; we need to prove that

$h_{\mathcal{D}}\in\arg\min_{h}L_{\mathcal{D}}(h)$

where $h_{\mathcal{D}}(x)=f(x,\operatorname*{\textnormal{\bf
E}}_{\mathcal{D}}[y|x])$.

By the observation, the classifier that predicts for
$x\in\text{supp}(\mathcal{D})$ using the optimal classifier for
$\mathcal{D}_{x}$ is itself optimal for $\mathcal{D}$. But by construction,
$\mathcal{D}_{x}\equiv\mathcal{D}_{x,\operatorname*{\textnormal{\bf
E}}_{\mathcal{D}}[y|x]}$, so we get:

$h^{\star}_{\mathcal{D}_{x}}(x)=h^{\star}_{\mathcal{D}_{x,\operatorname*{\textnormal{\bf
E}}_{\mathcal{D}}[y|x]}}=f(x,\operatorname*{\textnormal{\bf
E}}_{\mathcal{D}}[y|x])=h_{\mathcal{D}}(x)$

In other words, the classifier that predicts for
$x\in\text{supp}(\mathcal{D})$ using the optimal classifier for
$\mathcal{D}_{x}$ is precisely $h_{\mathcal{D}}$. The observation therefore
proves $h_{\mathcal{D}}\in\arg\min_{h}L_{\mathcal{D}}(h)$, as required.

##  Appendix D Proof of Lemma 4.4 ($f$-proper $\to$ learnability)

To prove the lemma, we construct a learning algorithm,
$\mathtt{MultiGroup_{L}}$, and prove that when $L$ is compatible and has the
uniform convergence property, the output of this algorithm satisfies the
requirements in the definition of multi-group learnability.

The definition of $\mathtt{MultiGroup_{L}}$ is given in Algorithm 3. At a
high-level, $\mathtt{MultiGroup_{L}}$ accepts a class $\mathcal{H}$,
collection of subgroups $\mathcal{G}$ and parameters
$\varepsilon,\delta,\gamma$, and returns a classifier by invoking a learning
algorithm for OI w.r.t an appropriate distinguisher class $\mathcal{A}$. The
definition of each distinguisher $A\in\mathcal{A}$ is given separately – see
Algorithm 4.

Algorithm 3
$\mathtt{MultiGroup_{L,f}}(\epsilon,\delta,\gamma,\mathcal{H},\mathcal{G})$

1: Parameters: loss function $L$, function $f:\mathcal{X}\times[0,1]\to[0,1]$

2: Input: accuracy parameter $\epsilon\in(0,1)$, failure probability
$\delta\in(0,1)$, minimal subgroups size parameter $\gamma\in(0,1)$,
hypothesis class $\mathcal{H}$, collection of subgroups $\mathcal{G}$.

3: Output: A classifier $h$ satisfying the $(\varepsilon,\delta)$-multi-group
guarantee w.r.t $\mathcal{H}$ and $\mathcal{G}$

4: Set $\varepsilon^{\prime}=\alpha=\varepsilon/4$ and
$\delta^{\prime}=\eta=\tau=\delta/4$.

5: Set
$k_{\mathcal{G}}=m^{UC}_{L}\left(\varepsilon^{\prime},\delta^{\prime},\left|\mathcal{H}\right|+1\right)$.

6: Set $k=10\cdot\frac{1}{\gamma}\cdot\log\frac{1}{\delta^{\prime}}\cdot
k_{\mathcal{G}}$.

7: Let
$\mathcal{A}=\left\\{A^{L,f,k}_{g,h,\alpha}\,\,|\,\,g\in\mathcal{G},h\in\mathcal{H}\right\\}$
be a collection of distinguishers, as defined in Algorithm 4.

8: Invoke OI as a sub-routine to learn
$\tilde{p}\leftarrow\mathtt{OI}(\tau,\eta,\mathcal{A})$.

9: return $f(\tilde{p})$

Algorithm 4 $A^{L,f,k}_{g,h,\alpha}$ (multi-sample Sample-Access OI
distinguisher)

1: Parameters: number of samples $k\in\mathbb{N}$, group
$g\subseteq\mathcal{X}$, classifier $h:\mathcal{X}\to[0,1]$, loss function
$L$, function $f:\mathcal{X}\times[0,1]\to[0,1]$

2: Input: $\left\\{(x_{i},y_{i},p_{i})\right\\}_{i=1}^{k}$, where
$x_{i}\in\mathcal{X}$, $y_{i}\in\left\\{0,1\right\\}$ and $p_{i}\in[0,1]$

3: Output: A binary output denoting Accept/Reject

4: $I_{g}=\left\\{i:x_{i}\in g\right\\}$

5: $S_{g}=\left\\{(x_{i},y_{i})\right\\}_{i\in I_{g}}$

6: Define a predictor $f_{g}$ as
$f_{g}(x)=\begin{cases}f(x_{i},p_{i})&\exists i\in[k]\,\,\text{such
that}\,\,x=x_{i}\\\ 0&\text{otherwise}\end{cases}$ (3)

7: if $L_{S_{g}}(f_{g})<L_{S_{g}}(h)+2\alpha$ then

8: return 1

9: end if

10: return 0

We begin by proving that if $L$ is $f$-proper, then
$h\leftarrow\mathtt{MultiGroup_{L,f}}(\varepsilon,\delta,\mathcal{H},\mathcal{G})$
satisfies the $(\varepsilon,\delta)$-multi-group requirement w.r.t
$\mathcal{H}$ and $\mathcal{G}$.

######  Lemma D.1.

Suppose $L$ is $f$-proper. Fix a distribution $\mathcal{D}$ over
$\mathcal{X}\times Y$, a finite class $\mathcal{H}$, a finite collection of
subgroups $\mathcal{G}$ and parameters $\delta,\varepsilon,\gamma\in(0,1)$.
Then, w.p at least $1-\delta$, the predictor
$h\leftarrow\mathtt{MultiGroup_{L,f}}(\epsilon,\delta,\gamma,\mathcal{H},\mathcal{G})$
satisfies

$\forall g\in\mathcal{G}_{\gamma}:\quad L_{\mathcal{D}_{g}}(h)\leq
L_{\mathcal{D}_{g}}(\mathcal{H})+\varepsilon$

###### Proof.

We begin by lower-bounding the acceptance probability of each distinguisher
$A\in\mathcal{A}$ when it receives samples from the modeled distribution
$\tilde{\mathcal{D}}$. Recall that this is the distribution in which outcomes
$y_{i}$ are sampled according to $\text{Ber}(\tilde{p}(x_{i}))$, where
$\tilde{p}$ is the predictor returned by OI.

######  Claim D.2.

The probability that each $A\triangleq A_{g,h}\in\mathcal{A}$ accepts when
given samples from the modeled distribution $\tilde{\mathcal{D}}$ is at least
$1-2\delta^{\prime}$:

$\operatorname*{\textnormal{\bf
Pr}}_{\\{(x_{i},y_{i})\\}_{i=1}^{k}\sim\tilde{D}^{k}}[A(\\{(x_{i},y_{i},\tilde{p}(x_{i})\\}_{i=1}^{k})=1]\geq
1-2\delta^{\prime}$

To see why this is true, we first note that by construction, the predictor
$f(\tilde{p})$ (where $f(\tilde{p})(x)=f(x,\tilde{p}(x))$) coincides with the
predictor $h_{\tilde{\mathcal{D}}}$ from the definition of $f-$proper. Thus,
invoking the assumption that $L$ is $f$-proper for the distribution
$\mathcal{D}_{g}$ guarantees that

$L_{\tilde{\mathcal{D}}_{g}}f(\tilde{p})\leq L_{\tilde{\mathcal{D}}_{g}}(h)$
(4)

To relate this fact to the acceptance criteria of $A$, which is in terms of a
sample $S_{g}$ from $\tilde{\mathcal{D}}_{g}$, we need to use the uniform
convergence property of $L$. Recall that the distinguisher operates on
$k=10\cdot\frac{1}{\gamma}\cdot\log\frac{1}{\delta^{\prime}}\cdot
k_{\mathcal{G}}$ samples from $\tilde{\mathcal{D}}$; this was chosen precisely
to guarantee that w.p at least $1-\delta^{\prime}$, we have at least
$k_{\mathcal{G}}$ samples from $\tilde{\mathcal{D}}_{g}$ for every group $g$
whose mass is at least $\gamma$. Since
$k_{\mathcal{G}}=m^{UC}_{L}\left(\varepsilon^{\prime},\delta^{\prime},\left|\mathcal{H}\right|+1\right)$,
we have a uniform convergence guarantee for the class that includes
$\mathcal{H}$ and $\tilde{p}$. That is, we know that w.p at least
$1-\delta^{\prime}$

$\displaystyle\left|L_{S_{g}}(h)-L_{\tilde{\mathcal{D}}_{g}}(h)\right|\leq\varepsilon^{\prime},\qquad\left|L_{S_{g}}(f(\tilde{p}))-L_{\tilde{\mathcal{D}}_{g}}(f(\tilde{p}))\right|\leq\varepsilon^{\prime}$
(5)

Combining Equations (4) and (5), we have that with probability at least
$1-2\delta^{\prime}$ (obtained by union bounding with respect to the two
$\delta^{\prime}$ failure probabilities we used above),

$L_{S_{g}}(f(\tilde{p}))\leq L_{S_{g}}(h)+2\epsilon^{\prime}$

Finally, we note that w.r.t $S_{g}$, the predictor $f_{g}$ defined in Equation
(3) of Algorithm 4 is the same as $f(\tilde{p})$ – so the above is precisely
the acceptance criterion for $A$ in this case. We thus conclude that the
acceptance probability of $A$ when it receives samples from the modeled
distribution is at least $1-2\delta^{\prime}$, which concludes the proof of
the claim.

Next, we argue that a direct corollary is a related lower bound on the
acceptance probability of $A$ when it receives samples from the true
distribution $\mathcal{D}$.

######  Claim D.3.

The probability that each $A\triangleq A_{g,h}\in\mathcal{A}$ accepts when
given samples from the true distribution $\mathcal{D}$ is at least
$1-(2\delta^{\prime}+\tau+\eta)$:

$\operatorname*{\textnormal{\bf
Pr}}_{\\{(x_{i},y_{i})\\}_{i=1}^{k}\sim\mathcal{D}^{k}}[A(\\{(x_{i},y_{i},\tilde{p}(x_{i})\\}_{i=1}^{k})=1]\geq
1-(2\delta^{\prime}+\tau+\eta)$

The claim follows as a direct corollary from the previous claim. By
definition, since $\mathtt{OI}$ is a learning algorithm for OI predictors,
$\tilde{p}$ is $(\tau,\mathcal{A})$-OI w.p at least $1-\eta$. Recall that if
$\tilde{p}$ is $(\tau,\mathcal{A})$-OI, then we are guaranteed that the
probabilities of each $A\in\mathcal{A}$ accepting on samples from
$\tilde{\mathcal{D}}$ and $A$ accepting on samples from $\mathcal{D}$ differ
by at most $\tau$:

$\left|\operatorname*{\textnormal{\bf
Pr}}_{\\{(x_{i},y_{i})\\}_{i=1}^{k}\sim\mathcal{D}^{k}}[A(\\{(x_{i},y_{i},\tilde{p}(x_{i})\\}_{i=1}^{k})=1]-\operatorname*{\textnormal{\bf
Pr}}_{\\{(x_{i},y_{i})\\}_{i=1}^{k}\sim\tilde{\mathcal{D}}^{k}}[A(\\{(x_{i},y_{i},\tilde{p}(x_{i})\\}_{i=1}^{k})=1]\right|\leq\tau$
(6)

in other words, w.p at least $1-\eta$ we are guaranteed that
$\operatorname*{\textnormal{\bf
Pr}}_{\\{(x_{i},y_{i})\\}_{i=1}^{k}\sim\mathcal{D}^{k}}[A(\\{(x_{i},y_{i},\tilde{p}(x_{i})\\}_{i=1}^{k})=1]\geq
102\delta^{\prime}-\tau$. This implies that a lower bound on the acceptance
probability in this case is exactly $1-(2\delta^{\prime}+\tau+\eta)$,
completing the proof of the claim.

Next, we recall that by the definition of the acceptance condition for $A$,
the condition in Equation (6) is the same as saying that w.p at least
$1-(2\delta^{\prime}+\tau+\eta)$ over the choice of
$S_{g}\sim\mathcal{D}_{g}$,

$L_{S_{g}}(f(\tilde{p}))\leq L_{S_{g}}(h)+2\varepsilon^{\prime}$

Again using the uniform convergence guarantee from Equation (5), this implies

$L_{\mathcal{D}_{g}}(f(\tilde{p}))\leq
L_{\mathcal{D}_{g}}(h)+4\varepsilon^{\prime}$

Plugging in $\varepsilon^{\prime}=\varepsilon/4$ and
$\delta^{\prime}=\tau=\eta=\delta/4$, we conclude that w.p at least
$1-\delta$,

$L_{\mathcal{D}_{g}}(f(\tilde{p}))\leq L_{\mathcal{D}_{g}}(h)+\varepsilon$

which is the required. This completes the proof of Lemma D.1. ∎

To prove multi-group learnability, it remains to bound the sample complexity
of Algorithm 3, which we do in the following claim.

######  Claim D.4.

The sample complexity of Algorithm 3 is

$m^{gPAC}_{L}(\varepsilon,\delta,\gamma,\mathcal{H},\mathcal{G})=O\left(\frac{m_{\mathcal{H}}(\varepsilon,\delta)\cdot\log\left(\frac{\left|\mathcal{H}\right|\cdot\left|\mathcal{G}\right|}{\varepsilon}\right)}{\delta^{4}\cdot\gamma}\right)$

###### Proof.

By the definition of Algorithm 3, the number of samples required is the number
of samples required to obtain OI w.r.t $(\tau,\eta,\mathcal{A})$, where
$\mathcal{A}$ is a collection of
$\left|\mathcal{H}\right|\cdot\left|\mathcal{G}\right|$ $k-$sample OI
distinguishers. By Theorem 2.8, this requires an order of
$O(\frac{k\cdot\log(\left|A\right|/\eta)}{\tau^{4}})$ samples. Ignoring
constant factors and plugging in the settings of $k,\eta$ and $\tau$ used in
Algorithm 3,

$\displaystyle\eta$ $\displaystyle=O(\delta)$ $\displaystyle\tau$
$\displaystyle=O(\varepsilon)$ $\displaystyle k$
$\displaystyle=O\left(\frac{1}{\gamma}\cdot\log\frac{1}{\delta}\cdot
m^{UC}_{L}(\varepsilon,\delta,\left|\mathcal{H}\right|)\right)=O\left(\frac{1}{\gamma}\cdot\log\frac{1}{\delta}\cdot
m_{\mathcal{H}}(\varepsilon,\delta\right)$

we obtain the stated bound. ∎

Note that when $L$ has the uniform convergence property, this entire
expression is indeed polynomial in $1/\varepsilon,1/\delta,1/\gamma$ and
$\log(\left|\mathcal{H}\right|),\log(\left|\mathcal{G}\right|)$, as required.
Together with the previous lemma, this concludes the proof of Lemma 4.4.


\frac{1}{2}-\frac{\gamma}4 & \frac{1}{2}-\frac{\gamma}4 & \frac{\gamma}2
\end{bmatrix}
\end{equation*}

with \(\gamma = 2 - \sqrt{2}\). We define for \(\xi \in \mathbb{R}\) the quantities

\begin{align}
A(\xi) &= A\left(I - \xi A\right)^{-1} \qquad b^{T}(\xi) = b^{T}\left(I - \xi A\right)^{-1} \nonumber \\
e(\xi) &= \left(I - \xi A\right)^{-1}e \qquad\hspace{0.27cm} \varphi(\xi) = 1 + \xi b^{T}\left(I - \xi A\right)^{-1}e
\end{align}

where \(I\) is the \(3\times 3\) identity matrix and \(e\) is a vector whose all components are equal to \(1\). Therefore, for the specific scheme, we obtain

\begin{equation*}
A(\xi) = \begin{bmatrix}
0 & 0 & 0 \\
\gamma & 0 & 0 \\
1 + \alpha\left(\gamma\xi - 1\right) & \alpha & 0
\end{bmatrix}
\end{equation*}

\begin{equation*}
b^T(\xi) = \begin{bmatrix}
\frac{1}{4}\left[2+\gamma\left(-1 + \xi\left(4-\gamma+2\alpha\left(\gamma\xi - 1\right)\right)\right)\right] & \\
\frac{1}{4}\left[2+\gamma\left(2\alpha\xi - 1\right)\right] & \\
\frac{\gamma}2
\end{bmatrix}
\end{equation*}

\begin{equation*}
e(\xi) = \begin{bmatrix}
1 & \\
1 + \gamma\xi & \\
1 + \xi + \alpha\gamma\xi^2
\end{bmatrix}
\end{equation*}

\begin{equation*}
\varphi(\xi) = 1 + \xi + \frac{\xi^2}{2} + \left(3 - 2\sqrt{2}\right)\alpha\xi^3.
\end{equation*}

A method with tableaux \(\left(A,b^{T}\right)\) is absolutely monotone at \(\xi \in \mathbb{R}\) if \(A(\xi) \ge 0\), \(b^{T}(\xi) \ge 0\), \(e(\xi) \ge 0\) and \(\varphi(\xi)\ge 0\) elementwise; moreover the radius of absolute monotonicity is defined for all \(\xi\) in \(-r \le \xi \le 0\) as

\[R(a,b) = \sup\left[r|r\ge 0, A(\xi) \ge 0,b^{T}(\xi) \ge 0,e(\xi) \ge 0, \varphi(\xi)\ge 0\right].\]

Figure <ref> shows the behaviour of the radius of absolute monotonicity as \(\alpha\) varies, along with the behaviour of the stability region along the imaginary axis. As already mentioned before, \(\alpha = \frac{7 - 2\gamma }{6}\) was chosen originally to maximize the stability region, but in this case \(R = \frac{2\sqrt{2} - 3}{2 + \sqrt{2}} \approx 0.05\), so that the region of absolute monotonicity is quite small. It can be shown that the region of absolute stability is given by

$$ S=\left\{z \in \mathbb{C} : \left|1 + z + \alpha\gamma z^2\right| < 1 \right\}. $$

The alternative value \(\alpha = 0.5\) maximizes the region of absolute monotonicity without compromising too much the stability. The impact of this alternative choice on numerical results is discussed in Section <ref>.

Analysis of the explicit part of IMEX scheme: a) Radius of absolute monotonicity as function of \(\alpha\), b) Size of stability region along the imaginary axis as \(\alpha\) varies.

§ EIGENVALUES OF 1D EULER EQUATIONS

In this Appendix we compute the eigenvalues for the Euler equations in non-dimensional form for a general equation of state. For the sake of simplicity, we focus on 1D case and so the equations can be written as follows

\begin{eqnarray}
\frac{\partial \rho}{\partial t}
+\frac{\partial}{\partial x}\left(\rho u\right)&=& 0   \nonumber \\
\frac{\partial \rho u}{\partial t}
+\frac{\partial}{\partial x}\left(\rho u^2\right)
+ \frac{1}{M^2}\frac{\partial p}{\partial x} &=& 0 \\
\frac{\partial \rho E}{\partial t}
+\frac{\partial}{\partial x}\left[\left(\rho E + p\right)u \right] &=& 0. \nonumber
\end{eqnarray}

This is equivalent to

\begin{eqnarray}
\frac{\partial \rho}{\partial t} + u\frac{\partial \rho}{\partial x} + \rho \frac{\partial u}{\partial x} &&= 0 \nonumber \\
\frac{\partial \rho}{\partial t}u + \frac{\partial u}{\partial t}\rho
+ u^2\frac{\partial \rho}{\partial x} + 2\rho u\frac{\partial u}{\partial x}
+ \frac{1}{M^2}\frac{\partial p}{\partial x} &&= 0 \\
\frac{\partial \rho}{\partial t}E + \frac{\partial E}{\partial t}\rho
+ \left(\rho E + p\right)\frac{\partial u}{\partial x} + u\left(\frac{\partial \rho}{\partial x}E + \frac{\partial E}{\partial x}\rho + \frac{\partial p}{\partial x}\right) &&= 0. \nonumber
\end{eqnarray}

Thanks to the continuity equation and to the relation \(E = e + \frac{1}{2}M^2u^2\), we obtain

\begin{eqnarray}
\frac{\partial \rho}{\partial t} + u\frac{\partial \rho}{\partial x} + \rho \frac{\partial u}{\partial x} &=& 0 \nonumber \\
\frac{\partial u}{\partial t} + u\frac{\partial u}{\partial x}
+ \frac{1}{\rho M^2}\frac{\partial p}{\partial x} &=& 0 \\
\frac{\partial e}{\partial t} + \frac{p}{\rho}\frac{\partial u}{\partial x} + u\frac{\partial e}{\partial x} &=& 0. \nonumber
\end{eqnarray}

In general \(e = e(p, \rho)\), so that

\begin{equation}
\frac{\partial e}{\partial \square} = \frac{\partial e}{\partial \rho}\frac{\partial \rho}{\partial \square} + \frac{\partial e}{\partial p}\frac{\partial p}{\partial \square},
\end{equation}

and, hence, the system reduces to

\begin{eqnarray}
\frac{\partial \rho}{\partial t} + u\frac{\partial \rho}{\partial x} + \rho \frac{\partial u}{\partial x} &=& 0 \nonumber \\
\frac{\partial u}{\partial t} + u\frac{\partial u}{\partial x}
+ \frac{1}{\rho M^2}\frac{\partial p}{\partial x} &=& 0 \\
\frac{\partial p}{\partial t} + \frac{\left(\frac{p}{\rho} - \rho\frac{\partial e}{\partial \rho}\right)}{\frac{\partial e}{\partial p}}\frac{\partial u}{\partial x} + u \frac{\partial p}{\partial x} &=& 0, \nonumber
\end{eqnarray}

which can be thought in the following vector form as:

\begin{equation}
\frac{\partial\mathbf{Q}}{\partial t} + \mathbf{A}\frac{\partial\mathbf{Q}}{\partial x} = \mathbf{0}
\end{equation}

\begin{equation}
\mathbf{Q} = \begin{bmatrix}
\rho \\
u \\
\end{bmatrix}
\end{equation}

\begin{equation}\label{eq:matrix_Euler}
\mathbf{A} = \begin{bmatrix}
u & \rho & 0 \\
0 & u & \frac{1}{\rho M^2} \\
0 & \frac{\left(\frac{p}{\rho} - \rho\frac{\partial e}{\partial \rho}\right)}{\frac{\partial e}{\partial p}} & u
\end{bmatrix}.
\end{equation}

The eigenvalues of (<ref>) are \(u - \frac{1}{M}\frac{1}{\rho}\sqrt{\frac{p - \frac{\partial e}{\partial \rho}\rho^2}{\frac{\partial e}{\partial p}}}\), \(u\) and \(u + \frac{1}{M}\frac{1}{\rho}\sqrt{\frac{p - \frac{\partial e}{\partial \rho}\rho^2}{\frac{\partial e}{\partial p}}}\). The first law of thermodynamics, already recalled in Section <ref>, provides us the following relation

\begin{equation}
Tds = de - \frac{p}{\rho^2}d\rho = \left(\frac{\partial e}{\partial \rho} - \frac{p}{\rho^2}\right)d\rho + \frac{\partial e}{\partial p}dp,
\end{equation}

or, equivalently,

\begin{equation}
dp = \frac{\frac{p}{\rho^2} - \frac{\partial e}{\partial \rho}}{\frac{\partial e}{\partial p}}d\rho + \frac{T}{\frac{\partial e}{\partial p}}ds.
\end{equation}

Hence, following [53], we have

\begin{equation}
c^2 = \frac{\partial p}{\partial \rho}\bigg\rvert_{s} = \frac{\frac{p}{\rho^2} - \frac{\partial e}{\partial \rho}}{\frac{\partial e}{\partial p}}
\end{equation}

and, therefore, the eigenvalues of (<ref>) are

$$ u + \frac{c}{M} \ \ \ u \ \ \ u + \frac{c}{M}$$

also for a generic equation of state, and not only in the case of an ideal gas, as already discussed in [38]. This justifies the definition (<ref>) also in case of non-ideal gases.

[1]
D.N. Arnold.
An interior penalty finite element method with discontinuous
SIAMNUM, 19:742–760, 1982.

[2]
W. Bangerth, R. Hartmann, and G. Kanschat.
deal II: a general-purpose object-oriented finite element library.
ACM Transactions on Mathematical Software (TOMS), 33:24–51,

[3]
R.E. Bank, W.M. Coughran, W. Fichtner, E.H. Grosse, Rose D.J., and R.K. Smith.
Transient Simulation of Silicon Devices and Circuits.
IEEE Transactions on Electron Devices., 32:1992–2007,

[4]
F. Bassi, L. Botti, A. Colombo, A. Ghidoni, and F. Massa.
Linearly implicit Rosenbrock-type Runge–Kutta schemes applied
to the Discontinuous Galerkin solution of compressible and incompressible
unsteady flows.
Computers & Fluids, 118, 2015.

[5]
F. Bassi, A. Crivellini, D.A. Di Pietro, and S. Rebay.
An implicit high-order discontinuous Galerkin method for steady and
unsteady incompressible flows.
Computers & Fluids, 36:1529–1546, 2007.

[6]
L. Bonaventura.
A semi-implicit, semi-Lagrangian scheme using the height coordinate
for a nonhydrostatic and fully elastic model of atmospheric flows.
Journal of Computational Physics, 158:186–213, 2000.

[7]
L. Bonaventura and A. Della Rocca.
Unconditionally strong stability preserving extensions of the
TR-BDF2 method.
Journal of Scientific Computing, 70:859–895, 2017.

[8]
L. Bonaventura, R. Redler, and R. Budich.
Earth System Modelling 2: Algorithms, Code Infrastructure and
Springer Verlag, New York, 2012.

[9]
S. Boscarino, J. Qiu, G. Russo, and T: Xiong.
High Order Semi-implicit WENO Schemes for All-Mach
Full Euler System of Gas Dynamics.
SIAM Journal on Scientific Computing, 44(2):B368–B394, 2022.

[10]
W. Boscheri and L. Pareschi.
High order pressure-based semi-implicit IMEX schemes for the 3D
Navier-Stokes equations at all Mach numbers.
Journal of Computational Physics, 434:110206, 2021.

[11]
S. Busto, M. Tavelli, W. Boscheri, and M. Dumbser.
Efficient high order accurate staggered semi-implicit discontinuous
Galerkin methods for natural convection problems.
Computers & Fluids, 198:104399, 2020.

[12]
V. Casulli and D. Greenspan.
Pressure method for the numerical solution of transient, compressible
fluid flows.
International Journal for Numerical Methods in Fluids,
4:1001–1012, 1984.

[13]
M.J.P. Cullen.
A test of a semi-implicit integration technique for a fully
compressible non-hydrostatic model.
Quarterly Journal of the Royal Meteorological Society,
116:1253–1258, 1990.

[14]
M. Dumbser and V. Casulli.
A conservative, weakly nonlinear semi-implicit finite volume scheme
for the compressible navier- stokes equations with general equation of state.
Applied Mathematics and Computation, 272:479–497, 2016.

[15]
M. Dumbser, O. Zanotti, R. Loubère, and S. Diot.
A posteriori subcell limiting of the discontinuous Galerkin finite
element method for hyperbolic conservation laws.
Journal of Computational Physics, 278:47–75, 2014.

[16]
N. Fehn, M. Kronbichler, C. Lehrenfeld, G. Lube, and P. Schroeder.
High-order DG solvers for under-resolved turbulent incompressible
flows: A comparison of $l^2$ and $h(div)$ methods.
International Journal of Numerical Methods in Fluids,
91:533–556, 2019.

[17]
M. Fernandez.
Propellant tank pressurization modeling for a hybrid rocket.
Master's thesis, Rochester Institute of Technology, 2009.

[18]
L. Ferracina and M.N. Spijker.
Stepsize restrictions for the Total-Variation-Diminishing
property in general Runge-Kutta methods.
SIAM Journal of Numerical Analysis, 42(3):1073–1093, 2004.

[19]
M. Gandolfi.
Baer-Nunziato type models for the simulation of hybrid rockets
self-pressurizing tanks.
Master's thesis, Politecnico di Milano, 2019.

[20]
U. Ghia, K.N. Ghia, and C.T. Shin.
High-Re solutions for incompressible flow using the
Navier-Stokes equations and a multigrid method.
Journal of Computational Physics, 48(3):387–411, 1982.

[21]
F.X. Giraldo.
Semi-implicit time-integrators for a scalable spectral element
atmospheric model.
Quarterly Journal of the Royal Meteorological Society,
131:2431–2454, 2005.

[22]
F.X. Giraldo.
An Introduction to Element-Based Galerkin Methods on
Tensor-Product Bases.
Springer Nature, 2020.

[23]
F.X. Giraldo, J.F. Kelly, and E.M. Constantinescu.
Implicit-explicit formulations of a three-dimensional nonhydrostatic
unified model of the atmosphere (NUMA).
SIAM Journal of Scientific Computing, 35:1162–1194, 2013.

[24]
F.X. Giraldo, M. Restelli, and M. Läuter.
Semi-implicit formulations of the Navier–Stokes equations:
Application to nonhydrostatic atmospheric modeling.
SIAM Journal on Scientific Computing, 32:3394–3425, 2010.

[25]
S. Gottlieb and C.W. Shu.
Total variation diminishing Runge-Kutta schemes.
Mathematics of Computation, 67(221):73–85, 1998.

[26]
S. Gottlieb, C.W. Shu, and E. Tadmor.
Strong stability-preserving high-order time discretization methods.
SIAM Review, 43(1):89–112, 2001.

[27]
I. Higueras.
On strong stability preserving time discretization methods.
Journal of Scientific Computing, 21:193–223, 2004.

[28]
M.E. Hosea and L.F: Shampine.
Analysis and implementation of TR-BDF2.
Applied Numerical Mathematics, 20:21–37, 1996.

[29]
B. Janssen and G. Kanschat.
Adaptive multilevel methods with local smoothing for $H^1$- and
$H^{curl}$-conforming high order finite element methods.
SIAM Journal on Scientific Computing, 33(4):2095–2114, 2011.

[30]
G.E. Karniadakis and S. Sherwin.
Spectral $hp-$Element Methods for Computational Fluid
Oxford University Press, 2005.

[31]
C.A. Kennedy and M.H. Carpenter.
Additive Runge-Kutta schemes for convection-diffusion-reaction
Applied Numerical Mathematics, 44:139–181, 2003.

[32]
J.F.B.M. Kraaijevanger.
Contractivity of Runge-Kutta methods.
BIT, 31:482–528, 1991.

[33]
C. Kühnlein, W. Deconinck, R. Klein, S. Malardel, Z.P. Piotrowski, P.K.
Smolarkiewicz, J. Szmelter, and N.P. Wedi.
FVM 1.0: A nonhydrostatic finite-volume dynamical core formulation
for IFS.
Geoscientific Model Development, 12:651–676, 2019.

[34]
O. Le Métayer and R. Saurel.
The Noble-Abel Stiffened-Gas equation of state.
Physics of Fluids, 28:046102, 04 2016.

[35]
E.W. Lemmon and R. Span.
Short fundamental equations of state for 20 industrial fluids.
Journal of Chemical & Engineering Data, 51:785–850, 2006.

[36]
R.J. LeVeque.
Finite volume methods for hyperbolic problems.
Cambridge University Press, 2002.

[37]
S.G. Lias, J. Bartmess, J.F. Liebman, J. Holmes, R.D. Levin, and G. Mallard.
NIST chemistry webbook standard reference database number 69.
National Institute of Standards Technology, 01 2010.

[38]
C.D. Munz, S. Roller, R. Klein, and K.J. Geratz.
The extension of incompressible flow solvers to the weakly
compressible regime.
Computers and Fluids, 32:173–196, 2003.

[39]
P. Nederstigt.
Real gas thermodynamics: and the isentropic behavior of substances.
Master's thesis, Delft University of Technology, 2017.

[40]
G. Orlando.
A filtering monotonization approach for dg discretizations of
hyperbolic problems.
Technical Report 2204.08693, arXiv, 2022.

[41]
G. Orlando, A. Della Rocca, P.F. Barbante, L. Bonaventura, and N. Parolini.
An efficient and accurate implicit DG solver for the incompressible
Navier‐Stokes equations.
to appear in International Journal for Numerical Methods in
Fluids, 2022.

[42]
L. Pareschi and G. Russo.
Implicit–explicit Runge–Kutta schemes and applications to
hyperbolic systems with relaxation.
Journal of Scientific computing, 25:129–155, 2005.

[43]
M. Restelli.
Semi-Lagrangian and Semi-Implicit Discontinuous Galerkin Methods
for Atmospheric Modeling Applications.
PhD thesis, Politecnico di Milano, 2007.

[44]
M. Restelli and F.X. Giraldo.
A conservative Discontinuous Galerkin semi-implicit formulation
for the Navier-Stokes equations in nonhydrostatic mesoscale modeling.
SIAM Journal of Scientific Computing, 31:2231–2257, 2009.

[45]
A. Robert.
A semi-Lagrangian and semi-implicit numerical integration scheme
for the primitive meteorological equations.
Journal of the Meteorological Society of Japan, 60:319–325,

[46]
P.K. Smolarkiewicz, C. Kühnlein, and N.P. Wedi.
Semi-implicit integrations of perturbation equations for all-scale
atmospheric dynamics.
Journal of Computational Physics, 376:145–159, 2019.

[47]
G.A. Sod.
A survey of several finite difference methods for systems of
nonlinear hyperbolic conservation laws.
Journal of Computational Physics, 27(1):1–31, 1978.

[48]
R. Span.
Multiparameter Equations of State.
Springer, 2000.

[49]
J. Steppeler, R. Hess, G. Doms, U. Schättler, and L. Bonaventura.
Review of numerical methods for nonhydrostatic weather prediction
Meteorology and Atmospheric Physics, 82:287–301, 2003.

[50]
G. Strang.
On the construction and comparison of difference schemes.
SIAM Journal on Numerical Analysis, 5:506–517, 1968.

[51]
M. Tavelli and M. Dumbser.
A pressure-based semi-implicit space–time discontinuous Galerkin
method on staggered unstructured meshes for the solution of the compressible
Navier–Stokes equations at all Mach numbers.
Journal of Computational Physics, 341:341–376, 2017.

[52]
G. Tumolo and L. Bonaventura.
A semi-implicit, semi-Lagrangian discontinuous Galerkin framework
for adaptive numerical weather prediction.
Quarterly Journal of the Royal Meteorological Society,
141:2582–2601, 2015.

[53]
J. Vidal.
Thermodynamics: Applications to chemical engineering and
petroleum industry.
Editions Technip, 2001.

[54]
J. Zeifang, J. Schütz, K. Kaiser, A. Beck,
M. Lukáčová-Medvid'ová, and S. Noelle.
A Novel Full-Euler Low Mach Number IMEX Splitting.
Communications in Computational Physics, 27(1):292–320, 2019.