To Pool or Not To Pool: Analyzing the Regularizing Effects of Group-Fair Training on Shared Models

Cyrus Cousins I. Elizabeth Kumar Suresh Venkatasubramanian

University of Massachusetts Amherst Brown University Brown University  ]

In fair machine learning, one source of

performance disparities between groups

is overfitting to groups with relatively few training samples.
We derive group-specific bounds on the generalization

welfare-centric fair machine learning

that benefit from
the larger sample size of the majority group. We do this by considering
group-specific Rademacher averages over a restricted hypothesis class,
which contains the family of models likely to perform well with respect to a

fair learning objective (e.g., a power-mean). Our simulations demonstrate
these bounds improve over a naïve method, as expected by theory, with particularly significant improvement for smaller group sizes.

§ INTRODUCTION

It is well-known that learned models can have performance or outcome disparities on underrepresented or disadvantaged groups in a distribution <cit.>.

Research suggests that these disparities are the result of a complex interaction between the training procedure, model class, and training data <cit.>.

Group-based welfare-centric machine learning attempts to mitigate disparities by
aggregations of per-group risk values, rather than average overall loss.
In other words, the task is to approximate $\argmin_{h \in \HC} \Malfare\bigl( \Risk(h, \ProbDist_1), \dots, \Risk(h, \ProbDist_{\NGroups}) \bigr)$ for some

malfare function $\Malfare(\cdot)$, where

$\Risk(h, \ProbDist_{i})$ is the risk (average loss) of

Such objectives
produce models that fairly compromise

among groups in various ways.

malfare function determines the fairness concept; for example, $\wv$-weighted risk minimization is equivalent to optimizing utilitarian malfare $\Malfare_{1}(\lv; \wv) = \lv \cdot \wv$, and

taking $\Malfare(\cdot)$ to be the maximum
produces the minimax-optimal $h^{*}$
a.k.a., the egalitarian or Rawlsian fair model.

training with empirical risk is susceptible to “overfitting to fairness,’’ wherein models

small or high-risk minority groups.

generalization error (
overfitting) of the overall objective decreases

with each group's sample size,

the current SOTA generalization
for group $i$

depend only on group $i$'s sample size.

We address this discrepancy;
in particular, we show that

in fair learning,
each group $i$

effectively learns
over a “restricted
of models that are reasonably likely
given the training data for

groups $j \neq i$, thus we bound their generalization error

via Rademacher averages of the restricted class, improving over existing bounds based on the original hypothesis class.

We begin by introducing notation and preliminary concepts (<ref>) and situating our approach with respect to existing literature (<ref>). We derive group-specific bounds on the generalization
of jointly trained models, which

benefit from the larger sample size of the majority group (<ref>).
techniques also translate to improved bounds on the generalization error of the malfare objective itself.

Additionally, we experimentally verify our methods
on synthetic linear and logistic regression tasks, finding
that our bounds better describe the overfitting behavior of fair-learning methods than
SOTA analysis (<ref>).
Our analysis allows us to resolve key real-world problems, such as when multiple groups benefit from pooling data to train a single (shared) model.
All proofs are relegated to <ref>.

§ BACKGROUND

We now introduce notation and preliminary concepts, followed by a brief review of related work.

§.§.§ More related work

Some useful intuition for this project is provided in <cit.> which explores the different potential causes of performance discrepancies in a model. They demonstrate that expected discrepancies of performance metrics across groups can be caused by “Differences in variance could be caused by differences in sample sizes $n_0, n_1$ or group-conditional feature variance, combined with a high capacity model. Targeted collection of training samples may help resolve this issue."

treat the issue of “when to split” (versus pool) training data from different groups in the setting where “infinite samples are available, or equivalently the distributions are known.” That is to say, they focus on the effects of the similarity of labeling functions $\Prob(Y|X,i)$ and the similarity of unlabeled distributions $\Prob(X|i)$,
and determine their effect on what they call the “benefit of splitting", i.e., the difference in loss between the best groupwise classifier and the best overall classifier.

\begin{align}
\underbrace{\inf_{h} \max_{g \in G} L_{g}(h)}_{\text{egalitarian $h$ loss}} - \underbrace{\max_{g \in G} \inf_{h} L_{g}(h)}_{\text{shared $h$ loss}}
\end{align}

In the above definition we noted from the original paper that both terms describe an egalitarian (or max-min) notion of loss which does not necessarily lend itself to a general case analysis of the “benefit of splitting” when other ways of comparing loss across groups.  Consider for example a “utilitarian” notation of loss which in the first term, adds up the loss across groups instead of taking their maximum.
Some important intuitive results they prove in this setting:

* If two groups share the same labeling function, ie $\Prob(Y|X,a) = \Prob(Y|X,b)$, there is no benefit to splitting.

* If two groups share the same unlabeled distributions $\Prob(X|a) = \Prob(X|b)$, but have different labeling functions $\Prob(Y|X,a) \neq \Prob(Y|X,b)$, the benefit of splitting is determined by the degree of disagreement.

* If two groups have disjoint support sets, that is, $\Prob(X|a)$ and $\Prob(X|b)$ are never nonzero at the same time for a certain $X$, there is no benefit to splitting (regardless of whether labeling functions are different), because you can basically define a piecewise joint function that matches each labeling in the appropriate part of the decision space. (NOTE: This is assuming model class has infinite capacity, NOT A REALISTIC ASSUMPTION. Also does not take overfitting into consideration.)

Rothblum et al. Cite propose a framework of multi-group agnostic PAC learnability. They define a notion of “multi-PAC compatibility” in which for every distribution, it is possible to learn a function that has generalization error “not much worse than” the best hypothesis for that group of a certain hypothesis class; they also provide a meta-algorithm to learn that model. This sounds similar to our framework of deriving groupies generalization bounds for (i.e.) an egalitarian malfare model which minimizes the maximum error on a group. However, their framework (and the related framework of Tosh and Hsu Cite) relies heavily on allowing the final hypothesis to not actually be a member of the original hypothesis class (a la boosting), instead relying on an additional subroutine which computes “individual” propensities (which I for one have a philosophical problem with). This nonetheless results in group-specific generalization bounds we should compare our results to.

Dwork et al. Cite propose exploring the biases in a jointly trained model by defining the cost-of-coupling as the difference between a jointly and separately trained model on a group, show that when this quantity is positive the learning algorithm “faces an inherent tradeoff in accuracy across groups,” and thus argue for “decoupled” classifiers that are trained using a “joint loss function” that penalizes differences in classification statistics between groups. They also suggest using transfer learning to exploit the similarity between groups to learn decoupled classifiers that generalize well. This results in another groupwise bound on generalization error that exploits group similarities.

§.§ Rademacher complexity

This should be cut/ moved to preliminaries

Rademacher complexity provides a nice way to parameterize a model class in terms of its generalization error. It is defined in terms of the notion of a set's representativeness, which quantifies the largest possible gap between the true error of a model and its empirical error.

Let $S$ be some training set drawn from distribution $\mathcal{D}$ where $|S| = n$, $\mathcal{H}$ a hypothesis class and $\ell$ a loss function. Let $S$ be some training set drawn from distribution $\mathcal{D}$ where $|S| = n$, $\mathcal{H}$ a hypothesis class and $\ell$ a loss function.
Let $L_{\mathcal{D}}(h) = \mathbb{E}_{z \sim \mathcal{D}} [\ell(h,z)]$ be the true expected error of $h$ on a distribution
and let $L_S(h) = \frac{1}{n} \sum_{i=1}^n \ell(h,z_i)$ be the empirical error.

The representativeness of $S$ is defined as
$$\text{Rep}_{\mathcal{D}}(\ell \circ \mathcal{H}, S) = \sup_{h \in \mathcal{H}} (L_{\mathcal{D}}(h) - L_S(h))$$

While we cannot calculate the representativeness of $S$ without access to $\mathcal{D}$, we can try to get at a similar notion by examining how well a subset of $S$ generalizes to its complement in $S$. (This is mirrors the practice of estimating a model's generalization error by training it on $S_1$ and evaluating with a validation set $S_2$.) That is to say, if $S = S_1 \cup S_2$, then we could estimate the representativeness of $S$ as
$\sup_{h \in \mathcal{H}} (L_{S_1}(h) - L_{S_2}(h))$.
If we call this the “empirical representativeness” of a subset of $S$, then the Rademacher complexity of $\mathcal{H}$ with respect to $S$ and $\ell$ is essentially the expected value of the empirical representativeness of $S$ over the possible partitions of $S$.

Let $\vsigma = (\vsigma_1, ..., \vsigma_n)$v or no? be a set of i.i.d. random variables distributed according to $\Prob(\vsigma_i = 1) = \Prob(\vsigma_i = -1) = \frac{1}{2}$. Then the Rademacher complexity is defined as

$$\ERade (\ell \circ \mathcal{H} \circ S ) = \frac{1}{n} \Exp_{\vsigma} \left[ \sup_{h \in \mathcal{H}} \sum_{i=1}^n \vsigma_i \ell(h, z_i) \right] $$

Notice that this is defined in terms of a fixed set $S$. To show this is a reasonable estimate of what we want, we have an important lemma:

The expected value of the representativeness of $S$ is bounded by twice the expected Rademacher complexity. That is,

$$\Exp_{S \sim \mathcal{D}^n} \left[ \sup_{h \in \mathcal{H}} (L_{\mathcal{D}}(h) - L_S(h)) \right] \leq 2 \Exp_{S \sim \mathcal{D}^n} \left[ \ERade(\ell \circ \mathcal{H} \circ S ) \right] $$

Key Intuition: This metric relates to how badly a hypothesis class might overfit to a sample. The $h$ that wins the supremum calculation does very well on one subset and very badly on another—or on a distribution more broadly—which is exactly what happens when you overfit to a dataset.

In fact, the Rademacher complexity allows us to express the notion that empirical risk minimization (i.e. using data to learn the model which minimizes the expectation of a loss function, rather than the loss function directly) yields a close-to-optimal result:

If $h_S$ is the result of $\text{ERM}_{\mathcal{H}}$ on $S$, then for all $h \in \mathcal{H}$,

$$ \Exp_{S \sim \mathcal{D}^m} [ L_{\mathcal{D}}(h_S) - L_{\mathcal{D}}(h)] \leq 2 \Exp_{S \sim \mathcal{D}^n} \left[ \ERade(\ell \circ \mathcal{H} \circ S ) \right]$$

Further, if $h*$ is the “true model” which minimizes $L_{\mathcal{D}}$, then for all $\delta \in (0,1)$, with probability of at least $1-\delta$ over the choice of $S$ we have

$$L_{\mathcal{D}}(h_S)  - L_{\mathcal{D}}(h*) \leq \frac{2 \Exp_{S' \sim \mathcal{D}^n}[\ERade(\ell \circ \mathcal{H} \circ S')]}{\delta}  $$

We get this because $h_S$ is the hypothesis that is expected to perform the best; in other words,
$\Exp_S [L_S(h_S)] \leq  L_{\mathcal{D}}(h*)$,
so the first part of the theorem follows directly from replacing the $L_S(h)$ term in the lemma. The second part is due to Markov's inequality.

Explain McDiarmid bound

§.§ Framework

For $p \in \R \cup \pm \infty$.
we define the weighted power-mean, given sentiment value vector $\lv \in \RNN^{\NGroups}$ and probability measure $\wv$, as

\begin{equation}
\label{eq:wpmean}
\Malfare_{p}(\lv; \wv) \doteq %\lim_{\varepsilon \to 0^{+}} \lim_{\rho \to p}
\vphantom{\sum}{\sqrt[p]{
\vphantom{\sum^{,}_{\cdot}}\smash{\sum_{i=1}^{\NGroups}}
\wv_{i} \lv_{i}^{p} }} \enspace,
\end{equation}

or limits thereof.
For disutility (loss or risk), $p \geq 1$ power-means promote fairness, and are always convex functions.

[TODO: Gini SWF]

Suppose weighted malfare function $\Malfare_{p}(\cdot; \wv)$, hypothesis class $\HC \subseteq \X \to \Y'$, loss function $\loss(\cdot, \cdot): \Y' \times \Y \to \RNN$, and data-distributions $\ProbDist_{1:\NGroups}$ over $\X \times \Y$ for groups $1, \dots, \NGroups$.

For shorthand that ignores the parameters $p$ and $w$ of malfare, we'll use the notation $\Malfare(\cdot)$, which in general is a function (i.e. sum, weighted sum, weighted power-mean) of the sentiments of each group usually the error or estimated error of a model on that group. Notice that with group-proportional weights and utilitarian malfare, $\Malfare$ is equivalent to the overall loss over the whole dataset or distribution.

§.§ Problem Statement

[todo: Explain risk, empirical risk notation.]

Suppose a hypothesis class $\HC$, per group distributions $\ProbDist_{1}$ through $\ProbDist_{\NGroups}$, and a malfare function $\Malfare$.
Our goal is to approximately learn the welfare optimal function

\[
h^{*} \doteq …
\]

As our empirical proxy, given $\bm{m}_{i}$ samples from each $\ProbDist_{i}$ , we take the empirical malfare minimizer

\[
\]

This work asks the question, “What is the generalization error of the objective value?’’ and moreover, “How much does each group overfit, i.e., what is $...$ for each group $i$?’’

In particular, can we show that training a fair objective considering multiple groups provably reduces overfitting to each group, and moreover can we show sharper generalization bounds then if we were to bound the supremum deviation within each group individually, and combine these individual bounds into a single bound on the generalization error of the objective?

§.§ Preliminaries

We assume a standard supervised learning setting.
Given domain label space $\Y$, domain $\X$, and codomain $\Y'$, we assume a hypothesis class $\HC \subseteq \X \to \Y'$ and loss function $\loss: \Y' \times \Y \to \R$.
Now, suppose a sample $(\bm{x}, \bm{y}) = \bm{z} \in (\X \times \Y)^{m}$ or instance distribution $\ProbDist$ over $\X \times \Y$.

define the empirical risk of
hypothesis $h$ as

\[
\ERisk(h, \bm{z}) \doteq \frac{1}{m} \sum_{i=1}^{m} \loss(h(\bm{x}_{i}), \bm{y}_{i})
\enspace,
\]

and the true risk over the distribution $\ProbDist$ as

\[
\Risk(h, \ProbDist) \doteq \Expect_{(x,y) \distributed \ProbDist} [ \loss(h(x), y) ]
\enspace.
\]

A standard supervised learning task then
identifies the empirical risk minimizer

\[
\hat{h} \doteq \argmin_{h \in \HC} \ERisk(h, \bm{z})
\]

as a proxy for the true risk minimizer

\[
h^{*} \doteq \argmin_{h \in \HC} \Risk(h, \ProbDist)
\enspace.
\]

This framework encapsulates simple supervised settings where $\Y = \Y'$, such as
least-squares regression or hard binary classification, but it also

more sophisticated supervised learning settings, like probabilistic classification or conditional density estimation.
Is the rest of this para  necessary?Not necessary, but helpful I think. but I inevitably get questions of the form “can I do X in this framework?” or worse yet, criticisms that the framework is not sufficiently general to handle X, during the review process. If we really need the space, we can comment all or part of this out, and ideally put it back into an extended version.
I'm not sold on why this needs to be here. But to C's point, we might consider moving this to the discussion at the end on “what else can we do with this” if space permits.

We also model more exotic settings, such as

conditional density estimation, where the prediction space $\Y’$
distributions over $\Y$.

Furthermore, taking $\Y = \X$
easily encodes unsupervised objectives, such as
(relatives of)
$k$-means clustering, where $h(\vec{x})$ produces the nearest cluster center, and $\loss(h(x), x) = \norm{h(x) - x}_{p}^{q}$ for some $p,q \in \R$.
Finally, observe that by concatenating group identity $i$ onto $\X$, we can also allow for group-specific loss functions and even prediction functions, i.e., for $x = (x', i)$, we can take $h(x) = (h_{i}(x'), i)$ and $\loss(h(x', i), y) = \loss_{i}( h_{i}(x'), y )$ for group-specific $h_{1:\NGroups}(\cdot)$ and $\loss_{1:\NGroups}(\cdot, \cdot)$.

Group-Fair Learning

This work considers group-fair learning, in which we assume not one instance distribution $\ProbDist$, but rather $\NGroups$ per-group instance distributions $\ProbDist_{1:\NGroups}$, and per-group samples $\bm{z}_{i} \distributed \ProbDist_{i}^{\smash{\bm{m}_{i}}}$ where $\bm{m}_{i}$ is the sample size for group $i$.
The distribution $\ProbDist_{i}$ encapsulates the situations encountered by members of each group $i$, which may vary in
$\X$ (situations encountered by each group), as well as their conditional labels $\Y | \X$ (responses or labels to a given situation).

To treat groups fairly, we consider objectives that consider the risk of all groups.

In particular, we assume a cardinal malfare function $\Malfare(\cdot): \R^{\NGroups} \to \R$, and
we then seek the empirical malfare minimizer

\begin{align*}
\hat{h} &\doteq \argmin_{h \in \HC} \Malfare \bigl(i \mapsto \ERisk(h, %\bm{z}_{i,1:\bm{m}_{i}}
\bm{z}_{i}
\bigr) \\
&= \argmin_{h \in \HC} \Malfare \bigl( \ERisk(h, \bm{z}_{1}), \ERisk(h, \bm{z}_{2}), \dots, \ERisk(h, \bm{z}_{\NGroups}) \bigr)
\end{align*}

as a proxy for the true malfare minimizer

\[
h^{*} \doteq \argmin_{h \in \HC} \Malfare \bigl(i \mapsto \Risk(h, \ProbDist_{i}) \bigr)
\enspace.
\]

On Malfare Functions

The choice of malfare function $\Malfare(\cdot)$ directly encodes how one wishes to make tradeoffs between various groups at various levels of risk.
The malfare function is thus a fundamental
hyperparameter that must be selected to achieve a modeler’s desired fairness properties, i.e., choosing a malfare function is equivalent to choosing a fairness concept.

Two popular choices are the utilitarian malfare (weighted average), which generally weights the risk of each group proportional to their size, and the egalitarian malfare, which seeks to lift up the most disadvantaged groups by minimizing the maximum risk.
These are in some sense two extremes of a spectrum: utilitarian malfare

only weights
groups, and does not distinguish between high-risk and low-risk groups (no equitable redistribution), whereas egalitarian malfare considers only the risk of each group, offering preferential treatment to those most in need (no consideration of non-minimal groups).

It is known that both of the above malfare functions belong to a general class of such functions.

Suppose some
$p \geq 1$, positive probability measure $\wv \in \triangle_{\NGroups}$, and nonnegative

risk vector $\lv \in \RNN^{\NGroups}$.
We define the weighted power-mean as

\begin{equation}
\label{eq:wpmean}
\!\!\!
\Malfare_{p}(\lv; \wv) \doteq %\lim_{\varepsilon \to 0^{+}} \lim_{\rho \to p}
\vphantom{\sum}
\vphantom{\sum^{,}_{\cdot}}\smash{\sum_{i=1}^{\NGroups}}
\wv_{i} \lv_{i}^{p} }}
\enspace, \;\,
\Malfare_{\infty}(\lv; \wv) \doteq
%\lim_{p \to \infty} \Malfare_{p}(\lv; \wv) =
\, \smash{\max_{\mathclap{i \in 1, \dots, \NGroups}}} \, \lv_{i}
\enspace. \!
\end{equation}

More generally, we define two popular classes of malfare function.

Suppose a descending sequence of Gini weights $\wv^{\downarrow} \in \triangle_{\NGroups}$,
risk vector $\lv \in \R^{\NGroups}$, and let $\lv^{\downarrow}$ denote $\lv$ in descending
The Gini malfare
is then

\begin{equation}
\label{eq:gini}
\Malfare_{\wv^{\downarrow}}(\lv) \doteq \vphantom{\sum}\smash{\sum_{i=1}^{\NGroups}} \wv^{\downarrow}_{i} \lv^{\downarrow}_{i} = \wv^{\downarrow} \cdot \lv^{\downarrow}
\enspace.
\end{equation}

utilitarian and egalitarian malfare arise as

power-mean special-cases

$p=1$ and
$p=\infty$, respectively.

They also arise in the Gini family, for 0.9[0.95]$\wv^{\uparrow} \! = \! \langle \mathsmaller{\frac{1}{\NGroups}}, \dots, \mathsmaller{\frac{1}{\NGroups}} \rangle$ and 0.9[0.95]$\wv^{\uparrow} \! = \! \langle 1, 0, \dots, 0 \rangle$, respectively.

The power-mean class is axiomatically justified <cit.>, which motivates its use in a variety of learning and allocation settings <cit.>.
Similarly, a slightly different set of axioms
yields the Gini class <cit.>.

Fairness and robustness are closely linked, and <cit.> also motivates power-means, as well as Gini malfare, and other malfare classes, from the perspective of robustness.
This work is neutral to the choice of malfare function;
we only seek to show that our methods may be applied to any malfare concept that meets certain broad criteria.

We generally assume
that $\Malfare(\cdot)$ is monotonic, i.e., that increasing any group's risk

never decreases
convex malfare functions are convenient for optimization, and in <ref> we utilize this property to efficiently bound Rademacher averages.
Finally, several of our bounds

algebraically convenient corollaries if we assume
Lipschitz continuity, i.e., small changes to risk

small changes to malfare.

The power-mean malfare family, as well as other
malfare classes, such as

the Gini class
<cit.> or

the utilitarian-maximin

each arise uniquely from

their own
sets of

Each assume
some type of monotonicity,

transfer principles, such as the Pigou-Dalton <cit.>, which incentivize equitable redistribution of harm
and give rise to convexity, as well as
some concept of
continuity, which coupled with functional analysis of the resultant class, give rise to Lipschitz continuity.
Our criteria for malfare functions are thus quite reasonable.
which each enjoy
their own
axiomatizations, all satisfy monotonicity, convexity, and Lipshitz continuity <cit.>.
In particular, each assume variations of the monotonicity axiom,
and transfer principles, such as the Pigou-Dalton <cit.> incentivize equitable redistribution of harm, are closely related to convexity.

Problem Statement
I don't know what the purpose of this paragraph is, and suggest it be removed. Especially since this section is or should be about BACKGROUND material.

In this work, we are concerned with both the generalization error of the chosen objective value as well as the impact of generalization errors $\Risk(\hat{h}, \ProbDist_{i}) - \ERisk(\hat{h}, \bm{z}_{i})$ for each group $i$.

In particular, can we show that training a fair objective considering multiple groups provably reduces overfitting to each group, and moreover can we show sharper generalization bounds than if we were to bound the supremum deviation within each group individually, and combine these individual bounds into a single bound on the generalization error of the objective?

Statistical Background

The Rademacher average is a key statistical tool used to bound the supremum deviation of empirical means from their expectations <cit.>.
Denote the loss class $\loss \circ \HC \doteq \left\{ (x, y) \mapsto \loss(h(x), y) \, \middle| \, h \in \HC \right\}$, and define Rademacher averages as follows.

$\vsigma_{1:m}$ be a

of $m$
$\mathrm{Unif}(\pm 1)$ random variables.
The empirical Rademacher average is then

\[
\ERade_{m} (\ell \circ \mathcal{H}, \bm{z} ) \doteq \Expect_{\vsigma} \left[ \sup_{h \in \HC} \frac{1}{m} \sum_{i=1}^m \vsigma_i \ell(h(\bm{x}_{i}), \bm{y}_{i}) \right]
\enspace,
\]

i.e., the maximum correlation of any $h \in \HC$ with noise on a sample $\bm{z} \in (\X \times \Y)^{m}$,
and the Rademacher average is

its expectation over

from $\ProbDist$, i.e.,

\[
\Rade_{m} (\ell \circ \mathcal{H}, \ProbDist ) \doteq \Expect_{\bm{z} \distributed \ProbDist^{m}} \bigl[ \, \ERade_{m}(\loss \circ \HC, \bm{z}) \, \bigr]
\enspace.
\]

Suppose loss class $\loss \circ \HC \subseteq (\X \times \Y) \to [0, \frange]$ where $\frange$ is the range of loss values,
per-group distributions $\ProbDist_{1:\NGroups}$ over ($\X \times \Y)$, and per-group samples $\bm{z}_{1:\NGroups} \in (\X \times \Y)^{\bm{m}_{1}} \times \dots \times (\X \times \Y)^{\bm{m}_{\NGroups}}$ where $\bm{z}_{i} \distributed \ProbDist_{i}^{\smash{\bm{m}_{i}}}$ and $\bm{m}_{i}$ is the sample size for group $i$.

Assuming bounded loss range $\frange$,

$\epsv_{i} \doteq \frange\sqrt{\frac{\ln \frac{1}{\delta}}{2\bm{m}_{i}}}$ and

$\hat{\etav}_{i} \doteq 2\ERade_{\bm{m}_{i}}(\loss \circ \HC, \bm{z}_{i}) + 2\epsv_{i}$.
For any failure probability $\delta$

$h \in \HC$, and group $i$,
sampling error is bounded as

\begin{equation}
\label{eq:hoeff-bound}
\Prob_{\!\bm{z}_{i} \distributed \ProbDist_{i}^{\smash{\bm{m}_{i}}}\!} \left( \, \abs{ %\EExpect_{\bm{z}_{i}}[\loss \circ h] - \Expect_{\ProbDist_{i}}[\loss \circ h]
\ERisk(h, \bm{z}_{i}) - \Risk(h, \ProbDist_{i})
> \epsv_{i} \right) < 2\delta %\leq 1 - 2\delta
\enspace.
\end{equation}

Moreover, considering all $h \in \HC$ simultaneously,
we have for each group $i$ that

\begin{equation}
\label{eq:rade-textbook}
%\Expect\left[ \sup_{h \in \HC} \abs{ \EExpect_{\bm{z}_{i}}[h] - \Expect_{\ProbDist_{i}}[h] } \right] \leq ...
\Prob_{\!\!\bm{z}_{i} \distributed \ProbDist_{i}^{\smash{\bm{m}_{i}}}\!} \! \left( \! \begin{matrix} 2\Rade_{m}(\loss \! \circ \! \HC, \ProbDist_{i}) > 2\ERade_{m}(\loss \! \circ \! \HC,\bm{z}_{i}) \! + \! \epsv_{i}  \\ \bigvee \sup\limits_{h \in \HC} \abs{
%\EExpect_{\bm{z}_{i}}[\loss \circ h] - \Expect_{\ProbDist_{i}}[\loss \circ h]
\ERisk(h, \bm{z}_{i}) - \Risk(h, \ProbDist_{i})
> \hat{\etav}_{i}
\end{matrix} \! \right) < 3\delta %\! \leq \! 1 - 3\delta
\!\enspace.
\end{equation}

Equations (<ref>) and (<ref>) are used throughout for various

hypotheses and hypothesis classes,
both in the above forms, and as 1-tailed variants.
These “textbook results” are now standard in learning theory[Constants vary between sources, depending on
definitions and derivations.
Our probabilistic statements
use 2-tailed Hoeffding
and 3 applications of McDiarmid's  inequality,

bounded differences, for
Rademacher averages with no absolute value

inside the supremum.
] <cit.>.

The quantity $\abs{\smash{\ERisk(h, \bm{z}_{i})} - \Risk(h, \ProbDist_{i})}$ of (<ref>) is the absolute deviation between the empirical risk
and the expected risk for

each individual
$h \in \HC$,

it bounds

the estimation error (i.e., error due to sampling) of any such function.

The quantity $\sup_{h \in \HC} \abs{
%\EExpect_{\bm{z}_{i}}[\loss \circ h] - \Expect_{\ProbDist_{i}}[\loss \circ h]
\smash{\ERisk(h, \bm{z}_{i})} - \Risk(h, \ProbDist_{i}) }$ of (<ref>) is known as the supremum deviation over
the loss class $\loss \circ \HC$, and

it bounds
the generalization error, both due to sampling error
and due to

selection bias

(training), of the learned $\hat{h}$.

Redundant with footnote.
The selection bias due to optimizing a learning objective

generally results in empirical-expected risk deviation
somewhere between that of a single $h$ and all of $\HC$.tease localization

NB that

$1$-tailed versions of (<ref>) and (<ref>) exist, and also that constants vary in the literature, due to analysis artifacts.

Note also that some presentations of Rademacher averages employ an absolute value inside the supremum, which is equivalent to

$\ERade_{\bm{m}_{i}}(\loss \circ \HC \cup - \loss \circ \HC, \bm{z_{i}})$, and in doing so

a single tail of the supremum deviation bound (<ref>) suffices.

We present results in terms of the non-absolute formulation, but the absolute formulation may be used to reduce the number of tails in union bounds, at the cost of larger Rademacher averages. Similarly, if independence between groups is assumed, union bounds over groups can be improved to Šidák bounds, and when variances are known to be small, variance-sensitive tail bounds, such as the Bennett and Bousquet inequalitiescite, can yield asymptotically sharper deviation bounds.

(<ref>) and a union-bound over groups, following <cit.>,

we probabilistically bound each group's generalization error (training-true

risk gap) as

\begin{equation}
\label{eq:group-gen}
%\Expect\left[ \sup_{h \in \HC} \abs{ \EExpect_{\bm{z}_{i}}[h] - \Expect_{\ProbDist_{i}}[h] } \right] \leq ...
\Prob_{\bm{z}_{1:\NGroups}} \! \left( \forall i\!:\, % \in 1,\dots,\NGroups: \
\abs{
%\EExpect_{\bm{z}_{i}}[\loss \circ h] - \Expect_{\ProbDist_{i}}[\loss \circ h]
\ERisk(\hat{h}, \bm{z}_{i}) - \Risk(\hat{h}, \ProbDist_{i})
\leq \hat{\etav}_{i} \right) \geq 1 - 3\NGroups\delta
\enspace.
\end{equation}

Moreover, if $\Malfare(\lv)$ is monotonically increasing in $\lv$,
then the malfare generalization

error obeys

\begin{equation}
\label{eq:m-gen}
%\Prob_{\bm{z}_{1:\NGroups}} \Bigl( \underbrace{\Malfare\bigl( i \mapsto \ERisk(\hat{h}, \bm{z}_{i}) - \hat{\etav}_{i} \bigr)}_{\textsc{Empirical LB}} \leq \underbrace{\Malfare\bigl( i \mapsto \Risk(\hat{h}, \ProbDist_{i}) \bigr)}_{\mathclap{\textsc{True Malfare of Learned $\hat{h}$}}} \leq \underbrace{\Malfare\bigl( i \mapsto \ERisk(\hat{h}, \bm{z}_{i}) + \hat{\etav}_{i} \bigr)}_{\textsc{Empirical UB}} \Bigr) \leq 1 - 3\NGroups\delta
\!\!\Prob_{\mathclap{\bm{z}_{1:\NGroups}}} \left( \begin{matrix}{\Malfare\bigl( i \mapsto \ERisk(\hat{h}, \bm{z}_{i}) \! - \! \hat{\etav}_{i} \bigr)} & \!\! {\text{(Empcl.\ LB)}} \\ \leq  {\Malfare\bigl( i \mapsto \Risk(\hat{h}, \ProbDist_{i}) \bigr)} & \!\! {\mathclap{\text{(True Malfare)}}} \ \  \\ \leq \! {\Malfare\bigl( i \mapsto \ERisk(\hat{h}, \bm{z}_{i}) \! + \! \hat{\etav}_{i} \bigr)} \!\!\!\!\! & \!\! {\text{(Empcl.\ UB)}} \end{matrix} \, \right) \! \geq \! 1 - 3\NGroups\delta
\enspace,
\end{equation}

i.e., the true malfare of

$\hat{h}$ is sandwiched by upper and lower bounds in terms of empirical malfare.

Finally, using also a union bound over (<ref>),

between the true risk of the empirical malfare minimizer $\hat{h}$ and the true malfare minimizer $h^{*}$

\begin{equation}
\label{eq:m-subopt}
\hspace{-0.4cm}\Prob_{\bm{z}_{1:\NGroups}} \! \left( \begin{matrix} \Malfare\bigl( i \mapsto \Risk(\hat{h}, \ProbDist_{i}) - \hat{\etav}_{i} \bigr) \\ \leq \Malfare\bigl( i \mapsto \Risk(h^{*}\!, \ProbDist_{i}) + \epsv_{i} \bigr) \end{matrix} \right) \geq 1 - 5\NGroups\delta
\enspace.
\hspace{-0.25cm}
\end{equation}

Could be $1 - 3\NGroups\delta$; only need 1 tail of each bound type. Tails.
Note that $\epsv$ and $\hat{\etav}$ are inside of the malfare operator $\Malfare(\cdot)$ in (<ref>) and (<ref>), but they can often be extracted via Lipschitz continuity; in particular for $p \geq 1$ power-means, $\Malfare_{p}(\lv + \lv'; \wv) \leq \Malfare_{p}(\lv; \wv) + \Malfare_{p}(\lv'; \wv)$, which provides loose but convenient bounds. What does 'extract' mean here?

§.§ Related work

This work

follows others in group-based welfare-centric fair machine learning.

We consider welfare-centric group-based fairness settings, where the goal is to optimize a cardinal malfare function of the form

\[
\hat{h} \doteq \argmin_{h' \in \HC} \Malfare\!\left( j \mapsto \ERisk(h', \bm{z}_{j}) %; \wv
\right) \enspace,
\]

where $\ERisk(h', \bm{z}_{j})$ denotes the empirical risk of model $h'$ on group $j$, and $\Malfare: \R^{\NGroups} \to \R$ is some malfare function.
often takes the form of Rawlsian or egalitarian learning, also known as minimax fair learning, wherein $\Malfare(\cdot)$ is the maximum function, and the goal is to minimize the maximum (over groups) average loss <cit.>

, which is
a form of distributionally robust optimization <cit.>

. Most such works only consider performance over the training set, but the Seldonian learner framework <cit.> explicitly
requires trained models be probably approximately optimal  some constrained nonlinear objective.

Similarly, the fair-PAC learning framework <cit.>

malfare minimization with power-mean objectives.
Some works consider not just the amount of overfitting to a fair objective, but also decompose the cause of this overfitting by group, and how to optimally sample to the better optimize an objective, finding that optimal sample sizes are not necessarily proportional to population sizes, and often smaller groups need to be overrepresented in order to avoid overfitting to them.
In particular, <cit.> proposes to not just optimize

\[
\hat{h} \doteq \argmin_{h' \in \HC} \Malfare\!\left( j \mapsto \ERisk(h', \bm{z}_{j}); \wv \right) \enspace,
\]

but rather to optimize

\[
\hat{h} \doteq \argmin_{h' \in \HC} \Malfare\!\left( j \mapsto \ERisk(h', \bm{z}_{j}) + \etav_{i}; \wv \right) \enspace,
\]

for $\etav_{i}$ an upper-bound on generalization error,
in order to avoid the subtle bias of overfitting to minority groups: the appearance of fairness on the training set, when in actuality due to overfitting the model still ends up favoring majority groups.

Due to the nonlinearity of $\Malfare(\cdot)$, existing work bounds generalization errror separately for each group $j$, and applies assumed Lipschitz or Hölder continuity properties of $\Malfare(\cdot)$ to bound the overall objective <cit.>.
In this work, we show sharper bounds on the generalization error of

but we also seek
to bound

each group's

generalization error.
This fine-grained information allows us to better assess the fairness of models and distinguish between cases where the cardinal objective is approximately known, but overfitting error comes from a model behaving discriminatory to some small minority groups, versus cases where the model is fairer, as overfitting error is more evenly distributed.

Multitask learning
There is

overlap between group fair learning (GFL) and multitask learning (MTL).

This work

that GFL

reduces generalization error for all groups (particularly smaller groups), which is essentially the motivation for MTL.
In both cases, we have

$\NGroups$ distributions
(per-group in GFL, per-task in MTL) and some objective that considers each distribution through $\Risk(h, \ProbDist_{i})$.

To our knowledge, there is no published work in multitask learning

on objectives that treat tasks nonlinearly, i.e., the objective is always <cit.>

\[
\hat{h} \doteq \argmin_{h \in \HC} \sum_{i=1}^{\NGroups} \frac{1}{\bm{m}_i} \sum_{j=1}^{\bm{m}_i} \loss_{i}(h(\bm{x}_{i,j}), \bm{y}_{i,j}) \enspace.
\]

Because of this formulation,
theoretical analysis for
generally reduces to applying standard statistical learning theory techniques for bounding deviations of functions from their means (e.g., VC dimension, [localized] Rademacher averages).
We are aware of no work which provides “fine grained bounds” for each subtask, rather than merely for the overall task.

This work differs from
in that we consider nonlinear objectives, and we wish to show that not only does task performance improve in aggregate (as measured through better generalization bounds on the objective), but also that the “individual tasks” (groups) are less susceptible to overfitting than with models trained per-group.

MTL analysis bounds
generalization error
by considering all data at once <cit.>;
assuming $m$ samples each for $\NGroups$ groups,
VC dimension, Rademacher averages,

bound total estimation error as

$O  \sqrt{{\ln \mathsmaller{\frac{1}{\delta}}}/{m\NGroups}}$.
Such methods do not apply in our setting, as we seek per-group generalization bounds and treat nonlinear objectives, thus ultimately we do not expect bounds of this order.

In contrast, with $\lambda$-Lipschitz non-linear fairness objectives,
existing methods bound

generalization error
each group individually, and then combine these bounds into a single generalization bound of $O(\lambda\sqrt{\frac{\ln \frac{\NGroups}{\delta}}{m}})$.

This is sufficient

nonlinear objectives, but it also has the side-benefit of providing per-group error bounds “for free.”
Existing work treats the analysis of each group in isolation, but this work explicitly considers the data for all groups $j \neq i$ in establishing bounds for each group $i$, essentially by considering only subsets of the hypothesis class likely to optimize the overall objective, which yields bounds that reflect the substantially reduced overfitting we see in group-fair training.

To pool or not to pool
Some work directly addresses the tradeoff between training pooled versus separate models for groups.
<cit.> define the cost-of-coupling as

\[
\max_{\ProbDist} \left( \min_{h \in \HC}\sum_{i=1}^{\NGroups}\Risk(h, \ProbDist_{i}) -
%\min_{h \in \HC'} \sum_{i=1}^{\NGroups}\Risk(h, \ProbDist_{i})
\sum_{i=1}^{\NGroups} \min_{h \in \HC} \Risk(h, \ProbDist_{i})
\right) \enspace,
\]

i.e., worst-case difference between the sum risk of the optimal shared model $\hat{h}$, vs. sum risk of optimal per-group models $\hat{h}_{1:\NGroups}$.

When this quantity is positive,
training with pooled data may require tradeoffs in accuracy across groups.
They then introduce transfer learning methods to train per-group classifiers $\hat{h}_{1:\NGroups}$ while leveraging available data where appropriate.

Similarly to our work, this results in improved VC-theoretic groupwise bounds on generalization error than fully separated training.
However, the goal of our learning framework is still to learn a joint model, avoiding thorny questions of disparate treatment.
<cit.> also examine the tradeoff, where the metric of interest or benefit of splitting is based on an egalitarian notion of fairness.

largely focus on
the infinite-samples or known-distributions settings;
they provide VC-theoretic generalization bounds on the benefit of splitting.
These are necessarily worst-case (over possible distributions), and specific to binary classification, whereas we provide data-dependent Rademacher average bounds applicable to a broad range of supervised and unsupervised settings.

§ BOUNDING GENERALIZATION ERROR
IN FAIR TRAINING

The above are used by <cit.>, and mirror standard techniques for the analysis of risk objectives.
It is possible to improve $\hat{\etav}$ if one centralizes the function family <cit.>, and $\epsv$ can be improved to depend primarily on the variance, rather than the range, of the hypothesis class <cit.>.
Beyond this, no more than constant factor improvement to the supremum error is possible, however using localization methods <cit.>, improved bounds can be shown for specific near-optimal or low-variance members of the hypothesis class (though not for the entire class).
Such methods of localization are not directly applicable to this work, as we have no guarantee that the welfare optimal $h^{*} = \argmin_{h \in \HC} \Malfare(i \mapsto \Risk(h, \ProbDist_{i}) )$ is at all similar to the per-group optimal $h^{*}_{i} \doteq \argmin_{h \in \HC} \Risk(h, \ProbDist_{i})$.

The generalization error analysis of <ref> does not take into account the fact
that learning is not equally likely to produce any $h \in \HC$. In this section, we present a sharper analysis that reflects this, both in per-group generalization error bounds, and in the overall generalization error of a malfare objective.

Our approach is to take the core idea of localization <cit.> — restricting the function class of interest to a subset that with high probability contains the function that will be learned — and generalize it to apply in multi-group fair learning settings.

In <Ref> we argue that, for each group $i$, with high probability, the learned function $\hat{h}$ belongs to some $\HC_{i}^{*} \subseteq \HC$.
bound generalization error over $\HC_{i}^{*}$,

with $\ERade_{\bm{m}_{i}}(\HC_{i}^{*}, \bm{z}_{i})$,
where often $\ERade_{\bm{m}_{i}}(\HC_{i}^{*}, \bm{z}_{i}) \ll \ERade_{\bm{m}_{i}}(\HC, \bm{z}_{i})$. The analysis depends on the group index $i$, since while analyzing group $i$, we can treat the training samples $\bm{z}_{j}$ as constant for each $j \neq i$, but the class $\HC_{i}^{*}$ must not depend on $\bm{z}_{i}$ for vital technical reasons (see proof of <ref>;
we require $\HC_{i}^{*}$ to be established independently from $\bm{z}_{i}$ in $\ERade_{\bm{m}_{i}}(\HC_{i}^{*}, \bm{z}_{i})$). We thus establish a theoretical hypothesis class that directly depends on the training sample for each $j \neq i$, but depends on the distribution for group $i$ instead of its training sample.

Unfortunately, $\HC_{i}^{*}$ is a theoretical object (not actually known, as it depends on $\ProbDist_{i}$). Thus, we have little recourse but to relax to dependence on purely empirical quantities. We thus establish in <Ref> an empirical class $\hat{\HC}_{i}$, which depends on $\bm{z}_{i}$ instead of $\ProbDist_{i}$. At first glance this seems to violate core statistical precepts, but through careful construction, we show that $\hat{\HC}_{i}$ acts merely as a probabilistic proxy for $\HC_{i}^{*}$.

Finally, we must actually estimate the relevant Rademacher bounds. In <Ref> we illustrate how this can be done for linear hypothesis classes using Monte-Carlo Rademacher averaging.

§.§ Theoretical Restricted

the generalization error of group $i$, we want to construct a restricted hypothesis class leveraging information given by the remaining group samples, in particular their empirical risks.

we can't directly use the group $i$ sample $\bm{z}_{i}$, so instead we bound empirical risk $\ERisk(h, \bm{z}_{i})$
in terms of $\Risk(h, \ProbDist_{i})$.
Intuitively, we want this restricted class to be the set of all $h \in \HC$ that could reasonably be the function
we learn from all data (the empirical malfare minimizer $\hat{h}$), where the restricted class is constructed after observing only the data $\bm{z}_{j}$ for all groups $j \neq i$.

Similar techniques are common in learning theory and the study of localization, where a theoretical class
is constructed based on the (unknown) distribution(s), and subsequently an empirical class that is with high probability a superset which can be built from the data.
Our approach, however, is unique in that it is in some sense half-empirical, as the theoretical class depends on the distribution $\ProbDist_{i}$ of one group, and the samples $\bm{z}_{j}$ from all groups $j \neq i$.
We do this instead of
constructing a “fully theoretical” class using only the distributions $\ProbDist_{1:\NGroups}$, as well as an empirical variant based on all training samples $\bm{z}_{1:\NGroups}$, which would be substantially larger.
However, a necessary consequence of our strategy is that we must assume samples are independent between groups, whereas the looser strategy would not require this assumption. i'm not sure what is meant / implicated by this assumption?We need to assume that, say, $\bm{z}_{1,1}$ and $\bm{z}_{2,1}$ are independent.
This is in addition to the standard assumption that $\bm{z}_{1,1}$, $\bm{z}_{1,2}$, …are independent. Sorry if this is a dumb question, but does this imply that if the group distributions are related in some way the assumptions are violated? If not, we should add a comment that this assumption is reasonable in our setting.They can be arbitrarily similar, as long as samples aren't correlated.

First, let $\epsv_{i} \doteq \frange\sqrt{\frac{\ln \frac{1}{\delta}}{2\bm{m}_{i}}}$

$\etav_{i} \doteq 2\Rade_{\bm{m}_{i}}(\loss \circ \HC, \ProbDist_{i} ) + \epsv_{i}$,
where $\bm{m}_{i}$ is the sample size for group $i$ and $\frange$ is the range of loss values in $\loss \circ \HC$.

Recall that the empirical malfare minimization task
is to select

\[
\hat{h} \doteq \argmin_{h' \in \HC} \Malfare\!\left( j \mapsto \smash{\ERisk}(h', \bm{z}_{j}) %; \wv
\right) \enspace,
\]

but since we can't observe sample $i$ yet, we (pessimistically) upper-bound the objective value (w.h.p.) as

\begin{align*}
\inf_{{h' \in \HC}} \Malfare\!\left( j \mapsto \smash{\ERisk}(h', \bm{z}_{j}) ; \wv \right) \leq \\
\inf_{{h' \in \HC}} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \smash{\ERisk}(h                       ', \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h', \ProbDist_{i}) + \epsv_{i} \end{cases} %; \wv \!
\right) \enspace,
\end{align*}

and (optimistically) lower-bound the empirical malfare of all $h \in \HC$, w.h.p. simultaneously, as

\begin{align*}
&\Malfare\!\left( j \mapsto \smash{\ERisk}(h, \bm{z}_{j}) ; \wv \right) \geq \\
&\Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \smash{\ERisk}(h, \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h, \ProbDist_{i}) - \etav_{i} \end{cases} %; \wv \!
\right) \enspace.
\end{align*}

Via this analysis, we then construct our theoretical class, which with high probability shall contain the empirical malfare minimizer $\hat{h}$,

the subset $\HC_{i}^{*} \subseteq \HC$ constrained to $h$ such that

\begin{align}
&\Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h, \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h, \ProbDist_{i}) - \etav_{i}^{} \end{cases} %; \wv \!
\right) \leq \notag \\ &\inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h', \ProbDist_{i}) + \epsv_{i} \end{cases} \label{eq:theoretical-restricted-class}%; \wv \!
\right)
\enspace.
\end{align}

This construction is valid (formalized in <ref>), as we took any $h$ that optimistically could outperform a pessimistic estimate of the empirical objective.

LHS is a “best case” estimate of the empirical malfare of a candidate hypothesis, whereas the

is a “worst case” estimate of the minimal empirical malfare, because we want our restricted hypothesis class to be large enough to

any $h \in \HC$ that might be the empirical malfare minimizer.
In particular, the LHS uses a Rademacher average bound

as the

bound must apply to all $h \in \HC$, but a simple tail-bound term

suffices on the RHS, as we are comparing to a bound involving some specific $h'$ (not dependent on the data $\bm{z}_{i}$).

for utilitarian malfare,

$\hat{\HC}_{i}$ describes models that definitely perform well for

groups $j \neq i$,
and will probably perform well for group $i$.
Some malfare functions, such as power-means, are undefined for negative risk values, and the LHS

risk lower bounds $\Risk(h, \ProbDist_{i}) - \etav_{i}^{}$
may be negative.
However, if we assume risk (or loss) is nonnegative,
we may use the risk lower bound $\max(0, \Risk(h, \ProbDist_{i}) - \etav_{i}^{})$,
which preserves convexity, continuity, and even differentiability if $p < \infty$
except around the point $\bm{0}$.

Observe now that, conditioning on $\bm{z}_{j}$ for each $j \neq i$, with high probability over choice of $\bm{z}_{i}$, empirical malfare minimization yields some $\hat{h} \in \HC_{i}^{*}$.
Therefore, for all intents and purposes, learning occurs over $\HC_{i}^{*}$, and we may thus use Rademacher averages over this restricted class to bound generalization error for group $i$.

This argument can actually be chained: we now define $\HC_{i}^{2*}$ using $\HC_{i}^{*}$, and in general $\HC_{i}^{k*}$ in terms of $\HC_{i}^{(k-1)*}$ for any $k > 0$, i.e.,

we take

\begin{equation}
\label{eq:theoretical-restricted-class-gen}
\HC_{i}^{k*} \doteq \left\{ h \in \HC_{i}^{(k-1)*} \middle| \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h, \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h, \ProbDist_{i}) - \etav_{i}^{k-1} \end{cases} %; \wv \!
\right) \leq \inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h', \ProbDist_{i}) + \epsv_{i} \end{cases} %; \wv \!
\right) \! \right\} \enspace.
\end{equation}

Similarly, we take
$\HC_{i}^{\infty*} \doteq \lim_{k \to \infty} \HC_{i}^{k*}$.
We can then use any $\HC_{i}^{k*}$ or $\HC_{i}^{\infty*}$ as a replacement for $\HC_{i}^{*}$, via similar arguments to the above.
Furthermore, as they obey containment, i.e.,

\[
\HC \supseteq \HC_{i}^{*} \supseteq \HC_{i}^{2*} \supseteq \HC_{i}^{3*} \supseteq \dots \supseteq \HC_{i}^{\infty*} \enspace,
\]

this approach yields smaller Rademacher averages (the sequence $\etav_{i}^{k}$ decreases in $k$), and thus sharper bounds.
Doing so does not require a union bound over $k$,
although proof is much subtler than
with $\HC_{i}^{*}$, and greater computational effort must be invested in computing (approximating) the limit of this sequence of Rademacher averages.
Note that it clearly does not converge to $0$, as $\varepsilon$$\epsv$? terms ensure that
does not converge to a single point.

I can say more about these sequences, not sure if this is the place though.

Formally put, we have the following result.

[Theoretical Group-Regularized Malfare Bounds]theoremthmboundstheoretical

Suppose a monotonic
malfare function [3]$\Malfare(\cdot): \R^{\NGroups} \to \R$, hypothesis class $\HC \subseteq \X \to \Y'$, loss function $\loss: \Y' \times \Y \to \R$, per-group distributions $\ProbDist_{1:\NGroups}$ over $\X \times \Y$, and per-group samples $\bm{z}_{1:\NGroups}$, with $\bm{z}_{j} \distributed \ProbDist_{j}^{\bm{m}_{j}}$ for each group $j$.

Fix any group index $i$, and take $\HC_{i}^{*}$ defined as in (<ref>).

The following then hold.

* With probability at least $1 - 2\delta$ over choice of $\bm{z}_{i}$, it holds that
$\hat{h} \in \HC_{i}^{*}$.

* With probability at least $1 - 4\delta$ over choice of $\bm{z}_{i}$,

\[
\abs{ \Risk(\hat{h}, \ProbDist_{i}) - \ERisk(\hat{h}, \bm{z}_{i}) } \leq 2\Rade_{\bm{m}_{i}}(\loss \circ \HC_{i}^{*}, \ProbDist_{i} ) + \epsv_{i} \enspace.
\]

Empirical Restricted

$\HC_{i}^{*}$ is an object only of theoretical interest (it is not actually known, since it depends on $\ProbDist_{i}$).
Consequently, without more information, $\Rade_{\bm{m}_{i}}(\loss \circ \HC_{i}^{*}, \ProbDist_{i})$, and thus the bounds of <ref>, can not be computed.

hclass/.style=draw=black,very thick,
ehclass/.style=hclass,dashed,fill=red,draw opacity=0.6,fill opacity=0.2,decorate,decoration=random steps,segment length=6pt,amplitude=1pt,

[hclass,fill=yellow,fill opacity=0.3] (0, -0.25) circle (3.35);
(hs0) at (0, 2.65)   $\HC$

[hclass,draw,use Hobby shortcut,closed=true, fill=red,fill opacity=0.3] (2, 0) .. (0, -2.2) .. (-1.6, -2) .. (-1.8, 0) .. (0, 1.1);

(ehs1) at (-0.5, -1.5)   $\hat{\HC}_{i}$
$\bm{z}_{1,2,\dots,\NGroups}, +2\etav_{i}$

[ehclass,draw,use Hobby shortcut,closed=true, fill=red,fill opacity=0.3,xscale=1.2] (2, 0) .. (0, -2.2) .. (-1.6, -2) .. (-1.8, 0) .. (0, 1.1);

[ehclass,draw,use Hobby shortcut,closed=true, fill=red,fill opacity=0.3] (2, 0) .. (0, -2.2) .. (-1.6, -2) .. (-2, 0) .. (0, 2);

[ehclass,draw,use Hobby shortcut,closed=true,xscale=1.3,yscale=1.2] (1.2, 0) .. (0, -1.5) .. (-0.8, -1) .. (-1.1, 0) .. (0, 1.6) .. (0.2, 1.7);

(ehs1) at (0, -3)    Samples of $\hat{\HC}_{i}$

(ehs1) – (0.5, -2.1);
(ehs1) – (-0.5, -2.3);
(ehs1) – (0, -1.8);

[hclass,fill=blue!30!white] (0, 0) circle (1);
(hs1) at (0, 0.18)   $\HC_{i}^{*}$

(hh) at (0.36, -0.58) 0.2ex$\bm{\cdot}$  $\hat{h}$;

(hs) at
(0.8, 1.4) ${h}^{*}$  -0.2ex$\bm{\cdot}$;

Visualization of unrestricted class $\HC$,
theoretical restricted class $\HC_{i}^{*} $,
and samples of empirical restricted class $\hat{\HC}_{i}$ (varying $\bm{z}_{i}$).
One possible empirical malfare minimizer $\hat{h}$ (contained by $\hat{\HC}_{i}$ and $\HC_{i}^{*}$ with high probability), as well as the true malfare minimzer $h^{*}$ (which may fall outside of $\HC_{i}^{*}$ or $\hat{\HC}_{i}$ due to overfitting to groups other than $i$) are also shown.

We remedy this issue here, relaxing dependence on the distribution $\ProbDist_{i}$ by replacing it with dependence on the training sample $\bm{z}_{i}$ and thus establishing a new empirically restricted hypothesis class.

Note that we can't simply substitute $\ERisk(h, \bm{z}_{i})$ for $\Risk(h, \ProbDist_{i})$, as <ref>
clearly requires the restricted hypothesis class $\HC_{i}^{*}$ to be fixed before observing the training data $\bm{z}_{i}$.
We account for this by indirectly using $\ERisk(h, \bm{z}_{i})$ to bound $\Risk(h, \ProbDist_{i})$.
[Updated result]:
In particular,
take $\tilde{\etav}_{i} \doteq 4\ERade_{\bm{m}_{i}}(\loss \circ \HC, \bm{z}_{i} ) + 3\epsv_{i}$ (this seemingly-eldritch construct

$\sup_{h \in \HC}
%\abs{ \Risk(h, \ProbDist_{i}) - \smash{\ERisk}(h, \bm{z}_{i}) }
\bigl(\ERisk(h, \bm{z}_{i}) - \Risk(h, \ProbDist_{i})\bigr) + \etav_{i}$ , see (<ref>), which is needed to
relate the LHS of the empirical constraint (<ref>) to the theoretical constraint (<ref>))
and take $\epsv_{i} \doteq \frange\sqrt{\frac{\ln \frac{1}{\delta}}{2\bm{m}_{i}}}$.

Now, set $\hat{\HC}_{i} \doteq \left\{ h \in \HC \right\}$, where

\begin{align}
\label{eq:empirical-restricted-class}
&\Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h, \bm{z}_{j}) \\ j \! = \! i \!\! & \ERisk(h, \bm{z}_{i}) - \tilde{\etav}_{i} \end{cases} %\! ; \wv
\right) \leq \notag \\ &\inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \ERisk(h', \bm{z}_{i}) + 2\epsv_{i} \end{cases} %\! ; \wv
\right) \enspace.
\end{align}

Note that (<ref>) matches (<ref>), except risks and Rademacher averages are upper and lower bounded in terms of their empirical counterparts.

In particular,
take $\hat{\etav}_{i} \doteq 2\ERade_{\bm{m}_{i}}(\loss \circ \HC, \bm{z}_{i} ) + 2\epsv_{i}$,
and take $\epsv_{i} \doteq \frange\sqrt{\frac{\ln \frac{1}{\delta}}{2\bm{m}_{i}}}$, as in (<ref>).

Now, we construct our empirical class $\hat{\HC}_{i}$, which with high probability shall contain the theoretical class $\HC_{i}^{*}$,

the subset $\hat{\HC}_{i} \subseteq \HC$ constrained to $h$ such that

\begin{align}
\label{eq:empirical-restricted-class}
\Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h, \bm{z}_{j}) \\ j \! = \! i \!\! & \ERisk(h, \bm{z}_{i}) - 2\hat{\etav}_{i} \end{cases} %\! ; \wv
\right) \leq \notag \\ &%\hspace{1.1cm}
\inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \ERisk(h', \bm{z}_{i}) + 2\epsv_{i} \end{cases} %\! ; \wv
\right) \enspace.
\end{align}

Note that (<ref>) matches (<ref>), except risks and Rademacher averages are
bounded in terms of their empirical counterparts.
In particular, on the LHS, , for all $h \in \HC$ it holds
$\ERisk(h, \bm{z}_{i}) - 2\hat{\etav_{i}} \leq \Risk(h, \ProbDist_{i}) - \etav_{i}$,

and on the RHS, ,
$\ERisk(h', \bm{z}_{i}) + 2\epsv_{i} \geq \Risk(h', \ProbDist_{i}) + \epsv_{i}$.

<Ref> visualizes the difference between $\hat{\HC}_{i}$ and ${\HC}_{i}^{*}$, as well as other key players.

Observe now that, with high probability, $\HC_{i}^{*} \subseteq \hat{\HC}_{i}$, therefore we can employ the theoretical properties of $\HC_{i}^{*}$ while being able to compute everything from a sample using $\hat{\HC}_{i}$.
The following theorem makes precise this statement, and should be viewed as an empirical counterpart to <ref>.

[Empirical Group-Regularized Malfare Bounds]theoremthmboundsempirical

Suppose as in <ref>.
The following then hold for $\hat{\HC}_{i}$ defined as in (<ref>).

* With probability at least $1 - 4\delta$ over choice of $\bm{z}_{i}$, it holds that $\hat{h} \in \HC_{i}^{*} \subseteq \hat{\HC}_{i}$.

* With probability at least $1 - 6\delta$, it holds that

\[
\abs{ \Risk(\hat{h}, \ProbDist_{i}) - \ERisk(\hat{h}, \bm{z}_{i}) } \leq 2\ERade_{\bm{m}_{i}}(\loss \circ \hat{\HC}_{i}, \bm{z}_{i} ) + 2\epsv_{i} \enspace.
\]

<Ref> satisfies our primary goal of showing per-group generalization bounds for fair learning that leverage information from other groups.
In particular,

when $\hat{\HC}_{i} \subset \HC$,
we obtain sharper generalization bounds, which
quantifies the intuition that
training a shared model is less susceptible to overfitting than training
per-group models.
<Ref> part 2 should be contrasted with (<ref>), which gives a similar guarantee
using Rademacher averages of the unrestricted class $\HC$.

<Ref> now applies these bounds to improve the state-of-the-art generalization guarantees for (nonlinear) malfare objectives,

which would otherwise depend on Rademacher averages of $\hat{\HC}_{i}$ rather than $\HC$,

[Empirical Malfare Generalization Bounds]corollarycoroempmalfarebounds

Suppose as in <ref>.

Suppose also that there exists some $\lambda > 0$ and norm $\norm{\cdot}_{\Malfare}$ such that $\Malfare(\cdot)$ is $\lambda$-$\norm{\cdot}_{\Malfare}$ Lipschitz continuous,

i.e., $\forall \lv,\lv'$:

\Malfare(\lv + \lv') \leq \Malfare(\lv) + \lambda \norm{\lv'}_{\Malfare}

We then have:

With probability at least $1 - 5\NGroups\delta$, the true malfare of $\hat{h}$ is bounded by

\begin{align*}
\Malfare\!\left(j \mapsto \Risk(\smash{\hat{h}}, \ProbDist_{j}) %; \wv
\right)
\hspace{-2.08cm} & \\
&\leq \Malfare\!\left(j \mapsto \ERisk(\smash{\hat{h}}, \bm{z}_{j}) + 2\ERade_{\bm{m}_{j}}(\hat{\HC}_{j}, \bm{z}_{j}) + 2\epsv_{j} %; \wv
\right) \\
&\leq \Malfare\!\left(j \mapsto \ERisk(\smash{\hat{h}}, \bm{z}_{j}) \! \right) + \lambda\norm{j \mapsto 2\ERade_{\bm{m}_{j\!}}(\hat{\HC}_{j}, \bm{z}_{j}) + 2\epsv_{j}}_{\Malfare\!}
\enspace.
\end{align*}

With probability at least $1 - 6\NGroups\delta$, we bound the suboptimality of $\smash{\hat{h}}$ as

\begin{align*}
% \Malfare\left(j \mapsto \Risk(h^{*}, \ProbDist_{j}) %; \wv
%     \right)
% & \leq
\Malfare\left(j \mapsto \Risk(\smash{\hat{h}}, \ProbDist_{j}) %; \wv
\right) \hspace{-0.85cm} & \\
&\leq \Malfare\left(j \mapsto \Risk(h^{*}\!, \ProbDist_{j}) + 2\ERade_{\bm{m}_{j}}(\hat{\HC}_{j}, \bm{z}_{j}) + 3\epsv_{j} %; \wv
\right) \\
\ \implies \ \; \abs{ \vphantom{\ERisk} \Malfare\left(j \mapsto \Risk(h^{*}\!, \ProbDist_{j}) %; \wv
\right) - \Malfare\left(j \mapsto \Risk(\smash{\hat{h}}, \ProbDist_{j}) %; \wv
\right) } \hspace{-5.25cm} & \\
&\leq \lambda\norm{j \mapsto 2\ERade_{\bm{m}_{j}}(\hat{\HC}_{j}, \bm{z}_{j}) + 3\epsv_{j}}_{\Malfare}
\enspace.
\end{align*}

The first inequality of parts 1 & 2 of <ref> is
sharper, but the second is generally more analytically convenient.
In particular, any power-mean or Gini malfare function $\Malfare(\cdot)$ is Lipschitz-continuous, and moreover subadditive, obeying

\begin{equation}
\label{eq:lip-subadd}
\hspace{-0.1cm} \Malfare(\lv \! + \! \lv') \! - \! \Malfare(\lv) \leq \Malfare(\lv') \leq \norm{\lv'}_{\infty} \enspace,
\end{equation}

and moreover, $p=1$ power-mean malfare and Gini malfare functions with weights $\wv$ obey

\begin{equation}
\label{eq:lip-l1}
\hspace{-0.1cm} \Malfare(\lv \! + \! \lv') \! - \! \Malfare(\lv) \leq \max_{\mathclap{i \in 1, \dots, \NGroups}} \wv_{i} \norm{\lv'}_{1} \enspace.
\end{equation}

Equation (<ref>) thus bounds malfare generalization error in terms of combinations or worst-case of per-group errors, and (<ref>) bounds in terms of sum error, which can be significantly sharper when weights are near-uniform.
In particular, any power-mean malfare function
$\Malfare_{p}(\cdot; \wv)$

\begin{equation}
\label{eq:lip-subadd}
\renewcommand{\!}{\hspace{-0.025em}}
\hspace{-0.2cm}
\Malfare_{p}(\lv \! + \! \lv'\!; \wv) \! - \! \Malfare_{p}(\lv; \wv) \leq \Malfare_{p}(\lv'\!; \wv) \leq \norm{\lv'}_{\infty} \!\!\!\hspace{-0.25em} \enspace, \!\!\!
\end{equation}

thus we bound malfare generalization error in terms of

the generalization error of each group.

Naturally, one may ask how sharp this localization strategy is.
We now show
an example where <ref> improves slow $\LandauO(\frac{1}{\sqrt{m}})$ convergence rates to fast $\LandauO(\frac{1}{m})$ convergence rates.

Consider unit-range 0-dimensional linear regression,
mean estimation under square loss $\loss$, with $\NGroups = 1$.

Thus we have

\[
\loss \circ \HC_{r} = \left\{ \loss( h_{c}(x), y) = (c - y)^{2} \, \middle| \, c \in [-r, r] \right\}
\]

with $r = 1$.
Take constant probability distribution $\ProbDist = 0$, thus $\bm{y} = \bm{0}$.

From random walk theory, we have

\begin{align*}
\ERade_{m}(\loss \circ \HC_{r}, \bm{y}) &=
\Expect_{\vsigma} \left[ \sup_{c \in [-r, r]} \frac{1}{m}\sum_{i=1}^{m} \vsigma_{i} (\bm{y}_{i} - c)^{2} \right] \\
&= \Expect_{\vsigma} \left[ \sup_{c \in [-r, r]} \frac{1}{m}\sum_{i=1}^{m} \vsigma_{i} c^{2}  \right] \\
&= \frac{r^{2}}{2} {\Expect_{\vsigma} \left[ \, \abs{ \frac{1}{m}\sum_{i=1}^{m}  \vsigma_{i} } \right]} %\\
\approx r^{2} %\mathsmaller
{\sqrt{\frac{1}{2\pi m}}}
\enspace.
\end{align*}

construct $\hat{\HC}$, observe that we have $\ERisk(c, \bm{y}) = c^{2}$, thus via (<ref>) we restrict s.t. $c^{2} \leq 4\ERade_{m}(\loss \circ \HC_{r}, \bm{y}) + 6\varepsilon \approx \sqrt{\frac{8}{\pi m}} + 6\sqrt{\frac{\ln \frac{1}{\delta}}{ 2m }} \implies %\abs{c} \lesssim \implies
%r \approx \sqrt[4]{\frac{8}{\pi m}}$.
\abs{c} \leq r \in \LandauTheta \sqrt[4]{\frac{1}{m}}$.

We thus have

$\ERade_{m}(\loss \circ \hat{\HC}, \bm{y}) \approx \sqrt{\frac{1}{2\pi m}} \cdot \left(\vphantom{\frac{1}{2}}\smash{\sqrt[4]{\frac{8}{\pi m}}}\right)^2 = \frac{4}{\pi} \cdot \frac{1}{m}$

\[
\ERade_{m}(\loss \circ \hat{\HC}, \bm{y}) \approx \frange^{2} \mathsmaller{\sqrt{\frac{1}{2\pi m}}} \in \LandauTheta\left( \mathsmaller{\frac{1}{m}} \right)
\enspace,
\]

which asymptotically improves
$\ERade_{m}(\loss \circ {\HC}, \bm{y}) \approx \sqrt{\frac{1}{2\pi m}}$.
We conjecture that
similar holds for realizable linear regression, and

label noise of variance $v$ instead yields a mixed learning rate of $\LandauTheta\left( \frac{1}{m} + \sqrt{\frac{v}{m}} \right)$.
Not quite: Hoeffding tail bound terms get in the way.

§.§ Monte-Carlo Rademacher Averages of Linear Hypothesis Classes

We now present a method to estimate Rademacher averages for linear hypothesis classes using Monte-Carlo sampling. We start by noting that, in general if $\ell(\hat{y}, y) = f(g(\hat{y}, y))$ and $f$ is $\lambda$-Lipschitz-continuous, then we have, for any $\bm{z} \in (\X \times \Y)^{m}$, that

\begin{equation}
\label{eq:contraction}
\ERade_{m}(\ell \circ \HC, \bm{z} ) \leq \lambda \ERade_{m}(g \circ \HC, \bm{z} )
\enspace.
\end{equation}

For this reason, we formulate the Rademacher averages of both linear least-squares regression and logistic regression as follows. Take  $\HC = \left\{ h_{\bm{\beta}}(\bm{x}) \doteq \bm{\beta} \cdot \bm{x} \, \middle| \, \bm{\beta} \in \bm{B} \right\}$ and loss function $\ell(\hat{y}, y) = f(g(\hat{y}, y))$, where for least-squares regression, $g(\hat{y},y) = \hat{y} - {y}$ and $f(u) = u^2$. This is $\lambda$-Lipschitz continuous, assuming bounded $\bm{B}$, $\mathcal{X}$, and $\mathcal{Y}$, with $\lambda = 2 \sup_{\bm{B}, \mathcal{Y}, \mathcal{X}} |\bm{x} \cdot \bm{\beta} - y|$.[In practice, we compute the Lipschitz constant over $\HC$, rather than over $\hat{\HC}_i \subseteq \HC$, which would require computing the diameter of $\hat{\HC}_i$ or bounding the range of $g \circ \hat{\HC}_{i}$.

For logistic regression, in which $\mathcal{Y} = \pm 1$, we have $g(\hat{y},y) = \hat{y} \cdot y$ and $f(u) = \ln(1 + \exp(u) )$, which is

Standard methods for bounding Rademacher averages of linear regression classes start by bounding the Rademacher average of $\HC$ itself <cit.>. However, this method is loose <cit.>, and seems especially so for irregular weight spaces (i.e., those not defined by simple $p$-norms), which known analytic methods can not handle.

Instead, we directly estimate the Rademacher average of the function family $g \circ \HC$ directly using Monte-Carlo estimation. That is to say, given sampled Rademacher random variables $\vsigma \in (\pm 1)^{n \times m}$ and data sample $\bm{z} \in (\X \times \Y)^{m}$, we compute

\begin{equation}
\label{eq:lin-mcera}
% &\ERade{}^n_{m}(g \circ \HC, \bm{z}; \vsigma) \doteq \\
% &\frac{1}{n} \sum_{k=1}^n  \sup_{\bm{\beta} \in W} \left[ \frac{1}{m} \sum_{j=1}^{m} \vsigma_{k,j} g( \bm{x}_{j} \cdot \bm{\beta}, \bm{y}_j ) \right] \enspace.
\!\!\ERade{}^n_{m}(g \circ \HC,  \bm{z}; \vsigma) \! \doteq \! \frac{1}{n} \smash{ \sum_{k=1}^n  \sup_{\bm{\beta} \in W} \frac{1}{m} \! \sum_{j=1}^{m} } \vsigma_{k,j} g( \bm{x}_{j} \cdot \bm{\beta}, \bm{y}_j ) \enspace.
\end{equation}

This fully data-dependent method gracefully tolerates arbitrary data distributions and

parameter spaces, and is loose only in a small amount of Monte-Carlo error and the contraction inequality <cit.>.
In practice, we use $\lambda \ERade{}^n_{\bm{m}_i}(g \circ \HC,  \bm{z}_i; \vsigma)$ as a plug-in estimate of $\lambda \ERade{}_{\bm{m}_i}(g \circ \HC,  \bm{z}_i)$, which then bounds $\ERade_{\bm{m}_{i}}(\ell \circ \HC, \bm{z}_{i} )$ via (<ref>).
We similarly estimate and bound Rademacher averages over our restricted hypothesis classes
as $\lambda \ERade{}^n_{\bm{m}_i}(g \circ \hat{\HC}_i,  \bm{z}_i; \vsigma)$.

[Convex Optimization for Monte-Carlo Rademacher Averages]lemmalemmacvx

Suppose the parameter space $\bm{B}$ of $\HC$ is a convex set, loss $\loss(h_{\bm{\beta}}(\bm{x}), y)$ is convex in $\bm{\beta} \in \bm{B}$ for all $\bm{x} \in \X$, $y \in \Y$, and malfare $\Malfare(\cdot): \R^{\NGroups} \to \R$ is quasiconvex and
monotonically increasing in each argument.
Then the parameter spaces of $\hat{\HC}_{i}$ and $\HC^{*}_{i}$ are
convex sets.

Moreover, if $g \circ \HC$ is an affine function family, then $\ERade{}^n_{m}(g \circ \hat{\HC}_{i}, \bm{z}_{i}; \vsigma)$
reduces to maximizing a linear function over a convex set.

Similarly, if we strengthen the quasiconvexity assumption on $\Malfare(\cdot)$ to convexity, then

EMM reduces to minimizing a convex objective over the convex set $\bm{B}$.

Visualizing $\hat{\HC}_i$ in least-squares regression

Rademacher average samples in the parameter space of $\hat{\HC}_i$ for each group $i \in \{1, 2, 3\}$.

Would it be a good idea to restrict the plot to [-1, 1], or at least a smaller region, in each dimensions, since that's where the action is and we have an l1 constraint anyway?.
I kinda like seeing the circles, but fair point

Is it possible to visualize this for egalitarian welfare? Even if it's just visualizing one group, I think that would be nice. It might also be nice to show $\hat{\HC}_{i}$ for two different sample sizes?
I tried it. the contours are not as easy to derive, and the points do not make a convincing shape, it just looks like a blob. I wanted this example to reinforce the reader's intuition
I'm personally pretty happy with how this figure looks at the moment? Do we need to discuss further?

Sample sizes $\bm{m}_{1:3}$, parameter vectors $\bm{\beta}_{1:3}$, and Monte-Carlo empirical Rademacher averages (MCERA) for both $\HC$ and $\smash{\hat{\HC}_{1:3}}$.

Group     $\bm{m}_{i}$     True $\bm{\beta}$     2c MCERA

ID               $\HC$       $\hat{\HC}_{i}$

1     6500     (0.3,0.3)     0.047     0.046

2     3000     (-0.1,0.1)     0.075     0.046

3     500     (0.3,0)     0.183     0.135

For least-squares regression, under utilitarian malfare, the restricted hypothesis constraint of $\hat{\HC}_{i}$ is an ellipsoid (under egalitarian welfare, it is an intersection of ellipsoids). We visualize a simple example in <ref>, with parameters and results described in <ref>.

Math in 1 col submission

$\bm{B} \doteq \left\{ \bm{\beta} \in \R^{2} \, \middle| \, \norm{\bm{\beta}}_{1} \leq 1 \right\}$
to be the unit $\ell_{1}$ ball, we
sample $(\bm{x}, y)$ as [3]$\bm{x} \sim \mathrm{Unif}([-1,1]^2)$, [3]$y = \bm{x} \cdot \bm{\beta}_i + \mathrm{Unif}([-1,1])$,
where each group has slightly different data generating parameters $\bm{\beta}_i$.

In <ref>, taking $\delta=0.1$, we plot the $n=100$ values of $\bm{\beta}$ which

realize each

of (<ref>) for some Rademacher sample $\vsigma_{k}$.
These points necessarily lie on either (the corner of) the $\ell_1$ constraint boundary of $\bm{B}$ or the restricted hypothesis constraint boundary of $\hat{\HC}_i$, illustrated by the concentric

which represent constant upper-bounds of weighted utilitarian malfare over the whole dataset and are centered around $\hat{h}$.

Note that for the smallest group, 3, the fact that $\hat{h}$ must perform well on the other two groups under weighted utilitarian malfare shrinks $\hat{\HC}_3$ significantly. However, the generalization bound over the largest group, 1, is not significantly improved when taken over $\hat{\HC}_1$.
Punchline: for small sample sizes $\hat{\HC}_{i} = \HC^{*}_{i} = \HC$ (w.h.p.), after some point, $\HC^{*}_{i} \subset \HC$, and $\hat{\HC}_{i}$ follows.
Moreover, if $h^{*}$ is not on the boundary of $W$, and the class is uniformly convergent, for a sufficiently large sample size, the $W$ constraint does not matter.

future idea: Fix data for one or two groups, and see dynamics of sample size

§ EXPERIMENTS

We illustrate the utility of our results with some experiments. Our approach is to construct an example dataset where we can demonstrate a clear benefit (to minority groups) to pooled training, and then show how our refined generalization bounds are in fact sharper than standard Rademacher bounds.
We do this by assuming that the individual distributions of the groups are similar enough that, for underrepresented minority groups, pooled training reduces generalization error.

Our experiments are based on a binary logistic regression task with $3$ groups.
Suppose the unit $\ell_{\infty}$ ball domain, i.e., $\X = [-1, 1]^{15}$, binary label space
$\Y = \pm 1$, and parameter space

[3]$\bm{B} \doteq \left\{\bm{\beta} \in \mathbb{R}^{15} \, \middle| \,  \norm{ \bm{\beta} }_1 \leq 15 \right\}$.
For each group $i$, we generate samples $(\bm{x}, y)$ with $\bm{x} \sim \mathrm{Unif}(\mathcal{X})$,  [3]$\Prob(y = 1) = \text{logistic}(\bm{x} \cdot \bm{\beta}_i + \xi)$, with noise [2]$\xi \sim \mathcal{N}(0,0.1)$, for [2]$\text{logistic}(u) = \frac{1}{1 + \exp(-u)}$.

We assume groupwise data generating parameters and a constant proportional composition of the full training sample as in <ref>. Notably, the data generating model for groups 1 and 3 are very similar, but there is always much more data available for group 1.

Data generating parameters for logistic regression experiments.

Data proportion     True parameters

Group 1     75%                $\beta_i = 0.3$

Group 2     20%                $\beta_i = 0.1$

Group 3     5%                 $\beta_i = 0.2$

Made it longer. Shorter version also in figures folder (with the appendix "_shorter") if it comes to that

Average test risk of pooled and separately trained models on three groups
(see <ref>).

Generalization error bounds derived from original hypothesis class $\HC$ and restricted hypothesis classes $\hat{\HC}_i$, compared with
shared model $\hat{h}$

train-test gap
over 7 independent runs, with quartiles and
median trend lines.

In <ref>, we plot the

average test risk  of each group $i$ over 7 independent runs for
malfare-minimizing models $\hat{h}$

or for risk-minimizing models $\hat{h}_{i}$
as a function of total training sample size, where
test risk is computed from a held-out test set
with 20,000 samples for each group.
We observe that pooled models almost always have lower per-group test risks than the separately-trained models
on the minority groups (2 and 3),
which we attribute to

the regularizing effect of pooled training overcoming the small discrepancies between the data generating parameters of each group (see <ref>).

While the above describes small-sample behavior, for

sufficient sample sizes,
per-group models

dominate shared models, and we do observe this for group 3 with the maximum sample size of $32768 \cdot 0.05 \approx 1638$.

We then compute the bounds derived from Monte-Carlo Rademacher averages (with $\delta=0.1$) over samples $\bm{z}_i$ over both $\HC$ and $\hat{\HC}_i$ for each $i$ (<ref>).
Since the bounds derived from Rademacher averages over $\HC$ essentially function as bounds on the generalization error of the separately trained models, the fact that the bound over $\hat{\HC}_i$ is tighter correctly suggests that pooled training is better for the minority groups in this scenario, especially when using egalitarian training.

In the utilitarian case, we see that initially $\hat{\HC}_i$ bounds match $\HC$ bounds, but for sufficiently large sample sizes, they diverge.
In the egalitarian case, $\hat{\HC}_i$ bounds are always better than $\HC$ bounds, and they appear to decay at an asymptotically greater rate (slope on the log-log plot), reaching an order of magnitude improvement in the case of the largest group (group 1).
This suggests that our bounds characterize generalization error substantially more sharply than the naïve method.

TODO: bounds diverge, order of magnitude, why egal is better?

It is known that the generalization error usually behaves as

\[
\LandauOmega\!\left(\!\sqrt{\frac{v}{m}}\right)
\leq \Expect_{%\hat{h},
\bm{z}_{1:\NGroups}}\left[ \abs{\Risk(\hat{h}, \ProbDist_{i}) - \ERisk(\hat{h}, \bm{z}_{i})} \right]
\leq \LandauO\!\left(\!\sqrt{\frac{C}{m}}\right) \enspace,
\]

where $v > 0$ is the maximum loss variance over any risk-optimal $h^{*}$, and $C < \infty$ is a constant that depends on $\HC$ and $\ProbDist$.
In particular, letting $V$ denote the maximum loss variance over all of $\HC$, $C \leq \lim_{m \to \infty} V + \bigl(\sqrt{m}\Rade_{m}(\loss \circ \HC, \ProbDist) \bigr)^{2}$, and obeys $C \in \LandauO ( V \cdot \ln^{2} \abs{\HC} )$ or $C \in \LandauO ( V \cdot \VC^{2}(\HC) )$, i.e., the log-cardinality $\ln \abs{\HC}$ or VC dimension $\VC(\HC)$ (or similar quantities) measure the capacity of $\HC$ to overfit.
Citations for fast learning rate theory

For sufficiently small sample sizes, we expect the restriction of our theory is vacuous, i.e., $\hat{\HC}_{i} = \HC$, and thus we see the slow learning rate
of $\frac{1}{\sqrt{m}}$ initially.
As the sample size $\bm{m}_{i}$ grows and constraints become non-vacuous, the simultaneous contraction of the hypothesis space $\hat{\HC}_{i}$ and growth of $\bm{m}_{i}$ can lead to a temporary fast convergence rate of $\approx \frac{1}{m}$, though the above theory indicates that, so long as $v > 0$, this fast learning rate does not hold asymptotically; eventually the learning rate settles back to $\frac{1}{\sqrt{m}}$, albeit with error bounds a constant factor $\LandauTheta( \sqrt{\frac{v}{C}} )$ better than the naïve method.

This hypothesis is borne out in <ref>: under utilitarian welfare, bounds using $\hat{\HC}_{i}$ initially match those using $\HC$, until reaching roughly $\bm{m}_{1} = 1024$, $\bm{m}_{2} = 512$, and $\bm{m}_{3} = 256$ samples, after which the $\hat{\HC}_{i}$ bounds diverge from those using $\HC$.
Moreover, our log-log plot reveals a slope of roughly $-\frac{1}{2}$, i.e., a $\frac{1}{\sqrt{m}}$ power-law rate, for both the initial portion of $\hat{\HC}_{i}$ bounds and $\HC$ bounds in their entirety.
This feels like tea leaf reading to me
In the egalitarian constraint experiments, we actually see that even at only $64$ samples, $\hat{\HC}_{i} \subset \HC$, and our bounds already

more rapidly than the $\HC$ bounds.

§ CONCLUSION

We show that fair learning, like multitask learning, has a regularizing effect,

reducing overfitting to each group as compared to per-group models trained solely on
their data.
Concretely, we show that, from the perspective of each group,
fair-learning (empirical malfare minimization) effectively occurs over some
restricted hypothesis class, and we the bound generalization error of each group's risk in terms of their Rademacher averages over these restricted classes.
technique yields refined generalization bounds, not just for the overall learning, task, but also for the risk of each individual group.

Such bounds are of particular importance in

learning settings where

minority groups often suffer poor model performance <cit.>, such as medical ML <cit.> and facial recognition <cit.>.

in critical systems, having provable guarantees on the generalization error of each task, rather than just the overall generalization error,

can greatly improve reliability and user trust.
This is also valuable in multi-task learning settings, where task fairness and task-specific bounds are of interest, e.g., in
distributionally-robust LLMs <cit.>.

While the contributions of this paper are theoretical,

our setting is practically motivated.
Understanding the generalization error of each group allows modelers to make better-informed decisions,
particularly regarding

minority groups.

Generalization bounds for a
group-specific model $\hat{h}_{i}$ and a shared model $\hat{h}$ can be used to bound risk for

group $i$,

which can be used for
model selection (i.e., group $i$ can select between $\hat{h}$ and $\hat{h}_{i}$ with confidence).

It is known that, given infinite data, individual models are always preferable, and the degree of suboptimality of a shared model can be bounded using transfer learning techniques; however, for data-hungry models, in particular with sparse data for minority groups, a better understanding of the interplay between generalization error and the negative impacts of majority group data on minority group performance are vital.

We also envision more sophisticated applications of our

For example,

if some smaller groups are more similar to minority group $i$ than a majority group,
a shared model $\hat{h}$ optimizing,
say, utilitarian malfare,

may perform poorly
for group $i$,

but perhaps a
better-performing $\hat{h}'$

would arise from

more egalitarian malfare function (i.e., higher $p$ power-mean), or one that emphasizes similar groups (through the weights vector $\wv$).

Group-fair learning methods can be combined with other aspects of model selection,
such as

feature and hyperparameter selection, where the bias-variance tradeoff plays a significant role.

Our bounds indicate that we can provably learn a more complex shared model without overfitting, and our analysis enables rigorous model selection guarantees

, both for individual group risks and for malfare objectives.

We are hopeful that future work explores these model-search questions and other applications of our methods.

Technically speaking, our methods … this is different from refined methods of localization, and not the process is only iterated once, i.e., we do not search for a fixed point, peel classes, or rescale hypotheses based on variances <cit.>.
This results in substantially simpler analysis, and yet retains the possibility of fast or mixed learning rates if .
In particular, and standard localization, there is a simple relationship between the risk of a hypothesis and it's variance, and this is used to show that learning effectively occurs over a set of low risk hypothesis. However, with non-linear objectives, there is no such simple relationship, so any more faithful application of the localization principle would require substantially more complexity.
We are hopeful that future work will resolve the technical challenges that arise when working with variances of restricted classes. We are also interested to see whether sharper analysis or more sophisticated localization techniques can be used to further improve our results.

§.§ Acknowledgments

This research was made possible in part by the generous support of the Ford Foundation and the MacArthur Foundation.
Cyrus Cousins also wishes to acknowledge

the Center for Data Science at the University of Massachusetts Amherst, where part of this work was

postdoctoral fellowship.
We would also like to thank Kweku Kwegyir-Aggrey for his insights and feedback on early versions of this work.

§ CHECKLIST

* For all models and algorithms presented, check if you include:

* A clear description of the mathematical setting, assumptions, algorithm, and/or model. [Yes]

* An analysis of the properties and complexity (time, space, sample size) of any algorithm. [Not Applicable]

* (Optional) Anonymized source code, with specification of all dependencies, including external libraries. [Yes]

* For any theoretical claim, check if you include:

* Statements of the full set of assumptions of all theoretical results. [Yes]

* Complete proofs of all theoretical results. [Yes]

* Clear explanations of any assumptions. [Yes]

* For all figures and tables that present empirical results, check if you include:

* The code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL). [Yes]

* All the training details (e.g., data splits, hyperparameters, how they were chosen). [Yes]

* A clear definition of the specific measure or statistics and error bars (e.g., with respect to the random seed after running experiments multiple times). [Not Applicable]

* A description of the computing infrastructure used. (e.g., type of GPUs, internal cluster, or cloud provider). [Yes]

* If you are using existing assets (e.g., code, data, models) or curating/releasing new assets, check if you include:

* Citations of the creator If your work uses existing assets. [Not Applicable]

* The license information of the assets, if applicable. [Not Applicable]

* New assets either in the supplemental material or as a URL, if applicable. [Not Applicable]

* Information about consent from data providers/curators. [Not Applicable]

* Discussion of sensible content if applicable, e.g., personally identifiable information or offensive content. [Not Applicable]

* If you used crowdsourcing or conducted research with human subjects, check if you include:

* The full text of instructions given to participants and screenshots. [Not Applicable]

* Descriptions of potential participant risks, with links to Institutional Review Board (IRB) approvals if applicable. [Not Applicable]

* The estimated hourly wage paid to participants and the total amount spent on participant compensation. [Not Applicable]

New file for appendices?

§ PROOFS

We now show <ref>.

We begin by proving part 1 and then we prove part 2 as a consequence.

We now show part 1.

Recall that $\etav_{i} \doteq 2\Rade_{\bm{m}_{i}}(\loss \circ \HC, \ProbDist_{i} ) + \epsv_{i}$. With probability at least $1 - 2\delta$, for all $h \in \HC$, it holds that

\[
\abs{ \Risk(h, \ProbDist_{i}) - \ERisk(h, \bm{z}_{i}) } \leq \etav_{i} \enspace.
\]

This is a textbook application of McDiarmid's bounded difference inequality, using twice the Rademacher average to bound the expected supremum deviation, i.e., the upper and lower tails of (<ref>).

We could use this directly to show a weaker version of the result, however to show the stated form, we need only one tail of the above, which is used to bound generalization error of the (unknown) $\hat{h}$, and also one tail of the simple Hoeffding’s inequality tail bound (<ref>).

Now, suppose some arbitrary but fixed $h'$ that realizes the infimum of (<ref>), i.e.,

\[
h' \in \argmin_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h', \ProbDist_{i}) + \epsv_{i} \end{cases} \right)
\]

(technically, $h'$ may be in $\HC$ or a limit of a sequence of functions in $\HC$
Recalling $\epsv_{i} \doteq \frange\sqrt{\frac{\ln \frac{1}{\delta}}{2\bm{m}_{i}}}$, we obtain by Hoeffding's inequality that,
with probability at least $1-2\delta$, it holds

\[
\abs{ \Risk(h', \ProbDist_{i}) - \ERisk(h', \bm{z}_{i}) } \leq \epsv_{i} \enspace.
\]

Therefore, when these bounds hold, we have

\begin{align*}
\hspace{-1.5cm}
\Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk( \hat{h}, \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(\hat{h}, \ProbDist_{i}) \! - \! \etav_{i} \end{cases} %\! ; \wv
\right)
\hspace{-4cm}
\leq \Malfare\!\left( j \mapsto \ERisk( \hat{h}, \bm{z}_{j}) %; \wv
\right) & \begin{tabular}{r} W.h.p.: $\Risk(\hat{h}, \ProbDist_{i}) - \etav_{i} \leq \ERisk(\hat{h}, \bm{z}_{i})$ \\ Monotonicity of $\Malfare(\cdot)$ \end{tabular} \\
&=  \inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \ERisk(h', \bm{z}_{j}) %; \wv
\right) & \begin{tabular}{r} By Definition \end{tabular} \\
&\leq \inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h', \ProbDist_{i}) \! + \! \epsv_{i} \end{cases} %\! ; \wv
\right) \!\enspace. & \hspace{-0.5cm} \begin{tabular}{r} W.h.p.: $\ERisk(h', \bm{z}_{i}) \leq \Risk(h', \ProbDist_{i}) + \epsv_{i}$ \\ Monotonicity of $\Malfare(\cdot)$ \end{tabular}
\end{align*}

We may thus conclude with probability at least $1 - 4\delta$ that $\hat{h} \in \HC_{i}^{*}$ (by definition).
However, observe that both the McDiarmid (Rademacher) and Hoeffding bounds required only one tail each, and thus a more careful analysis yields the guarantee with probability at least $1 - 2\delta$.

We now show part 2.
By part 1, we have that $\hat{h} \in \HC_{i}^{*}$ with probability at least $1 - 2\delta$.
Then we apply the standard 2-tailed Rademacher bound with McDiarmid's inequality over the restricted class $\HC_{i}^{*}$, i.e., we have

\[
\Prob_{\bm{z}_{i} \distributed \ProbDist_{i}^{\bm{m}_{i}}} \left( \sup_{h \in \HC_{i}^{*}}
\abs{ \Risk(h, \ProbDist_{i}) - \ERisk(h, \bm{z}_{i}) } \leq \etav_{i} \right) \leq 1 - 2\delta
\enspace.
\]

The union bound then yields the desideratum.

We now show <ref>.

We begin by proving part 1, and we then show part 2 as a consequence.

We now show part 1.
First, we apply part 1 of <ref> (2 tails).
We will then
argue that

\[
\Prob_{\bm{z}_{i} \distributed \ProbDist_{i}^{\bm{m}_{i}}}
\left( \HC_{i}^{*} \subseteq \hat{\HC}_{i} \right) \geq 1 - 2\delta
\enspace,
\]

which holds for similar reasons (a 1-tail Rademacher bound for $\HC$, and a 1-tail Hoeffding bound for $\hat{h}$, both the opposite tails bounded in  part 1 of <ref>).

The result then follows via union bound.

In particular,
recall (<ref>)

\begin{equation*}
\HC_{i}^{*} \doteq \left\{ h \in \HC \,\middle|\, \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h, \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h, \ProbDist_{i}) - \etav_{i}^{} \end{cases} %; \wv \!
\right) \leq \inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h', \ProbDist_{i}) + \epsv_{i} \end{cases} %; \wv \!
\right) \! \right\} \enspace,
\end{equation*}

and also (<ref>)

\begin{equation*}
\hat{\HC}_{i} \doteq \left\{ h \in \hat{\HC} \,\middle|\, \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h, \bm{z}_{j}) \\ j \! = \! i \!\! & \ERisk(h, \bm{z}_{i}) - 2\hat{\etav}_{i} \end{cases} %\! ; \wv
\right) \leq \inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \ERisk(h', \bm{z}_{i}) + 2\epsv_{i} \end{cases} %\! ; \wv
\right) \! \right\}
\enspace.
\end{equation*}

Now, observe that by McDiarmid's inequality, by essentially the same argument as in (<ref>), it holds that

\[
\! \Prob_{\bm{z}_{i} \hspace{-0.1em} \distributed \hspace{-0.1em} \ProbDist_{i}^{ \hspace{-0.1em} \bm{m}_{i\!}}
} \!\! \left(
\sup_{\mathclap{h \in \HC}} \ERisk(h, \bm{z}_{i}) \! - \! \Risk(h, \ProbDist_{i})
+ \etav_{i} %2\Rade_{\bm{m}_{i}}(\loss \circ \HC, \ProbDist_{i}) + \epsv_{i}
> 2\hat{\etav}_{i}
\!\hspace{-0.1em}
\right)
= \!\!\!\!\! \Prob_{\bm{z}_{i} \hspace{-0.1em} \distributed \hspace{-0.1em} \ProbDist_{i}^{ \hspace{-0.1em} \bm{m}_{i\!}}
}\!\! \left(
\sup_{\mathclap{h \in \HC}} \ERisk(h, \bm{z}_{i}) \! - \! \Risk(h, \ProbDist_{i})
+ 2\Rade_{\bm{m}_{i}\!}(\loss \circ \HC, \ProbDist_{i}) %+ \epsv_{i}
4\ERade_{\bm{m}_{i}\!}(\loss \circ \HC, \bm{z}_{i}) \! + \! 3\epsv_{i}
\!\hspace{-0.1em}
\right)
< \delta
\hspace{-0.1em}\enspace.
\]

We thus have that,
with probability at least $1 - \delta$,

for all $h \in \HC_{i}^{*}$,

\[
\Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h, \bm{z}_{j}) \\ j \! = \! i \!\! & \ERisk(h, \bm{z}_{i}) - 2\hat{\etav}_{i} \end{cases} %\! ; \wv
\right) \leq \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h, \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h, \ProbDist_{i}) - \etav_{i} \end{cases} %\! ; \wv
\right) \enspace,
\]

and similarly,

with probability at least $1 - \delta$
by the Hoeffding bound (<ref>) on $h'$,

we have

\[
\inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h', \ProbDist_{i}) + \epsv_{i} \end{cases} %\! ; \wv
\right)
\leq
\inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \ERisk(h', \bm{z}_{i}) + 2\epsv_{i} \end{cases} %\! ; \wv
\right) \enspace,
\]

where both steps apply monotonicity of $\Malfare(\cdot)$.

From this, we may conclude that, with probability at least $1 - 2\delta$, for each $h \in \HC$, if  the constraint in (<ref>) is satisfied, then the constraint (<ref>) is satisfied, thus ${\HC}_{i}^{*} \subseteq \hat{\HC}_{i}$.
The union bound over all tail bounds above then yields part 1.

We now show part 2.
This result essentially follows the structure of part 2 of <ref>.
However, we now start with part 1 above, which allows us to conclude that $\hat{h} \in \hat{\HC}_{i}$ with probability at least $1 - 4\delta$, and then apply the standard empirical Rademacher bounds, i.e., 2 tails of (<ref>) (we require only the upper and lower bounds to the supremum deviation, not the bound on the Rademacher average itself), to $ \hat{\HC}_{i}$ (rather than to $ {\HC}_{i}^{*}$).

Taking the union bound over all events then yields the desideratum.

We now show <ref>.

For both

results, we apply part 2 of <ref> to each group $i$, which by union bound gives a result with probability at least $1 - 6\NGroups\delta$.
However, careful accounting reveals that we only require one tail of the final Rademacher bound of <ref> part 2, i.e., we require $\Risk(\hat{h}, \ProbDist_{j}) \leq \ERisk(\hat{h}, \bm{z}_{j}) + 2\ERade_{\bm{m}_{j}}(\hat{\HC}_{j}, \bm{z}_{j}) + 2\epsv_{j}$, but not $\ERisk(\hat{h}, \bm{z}_{j}) \leq \Risk(\hat{h}, \ProbDist_{j}) + 2\ERade_{\bm{m}_{j}}(\hat{\HC}_{j}, \bm{z}_{j}) + 2\epsv_{j}$, thus
we begin with tail bounds that hold with probability at least $1 - 5\NGroups\delta$.

We now show part 1.
Subject to all tail bounds holding, we have
for all $j \in 1,\dots,\NGroups$ that $\Risk(\hat{h}, \ProbDist_{j}) \leq \ERisk(\hat{h}, \bm{z}_{j}) + 2\ERade_{\bm{m}_{j}}(\hat{\HC}_{j}, \bm{z}_{j}) + 2\epsv_{j}$, thus by monotonicity of $\Malfare(\cdot)$, we have

\[
%\Risk(\hat{h}, \ProbDist_{j}) \leq \ERisk(\hat{h}, \bm{z}_{j}) + 2\ERade_{\bm{m}_{j}}(\hat{\HC}_{j}, \bm{z}_{j}) + 2\epsv_{j}
\Malfare\left(j \mapsto \Risk(\hat{h}, \ProbDist_{j}) %; \wv
\right)
\leq \Malfare\left(j \mapsto \ERisk(\hat{h}, \bm{z}_{j}) + 2\ERade_{\bm{m}_{j}}(\hat{\HC}_{j}, \bm{z}_{j}) + 2\epsv_{j} %; \wv
\right)
\enspace.
\]

Applying the Lipschitz property then yields the final portion of part 1.

We now show part 2.
First, observe that
\Malfare\left(j \mapsto \Risk(h^{*}, \ProbDist_{j}) %; \wv
\right)
\leq \Malfare\left(j \mapsto \Risk(\hat{h}, \ProbDist_{j}) %; \wv
\right)
by definition.
For the remaining inequality, we introduce one new tail bound for each group $j$, in particular, a 1-tail Hoeffding bound of

\[
\Prob_{\bm{z}_{j} \distributed \ProbDist_{j}^{\bm{m}_{j}}}\left(\Risk(h^{*}, \ProbDist_{j}) \leq \ERisk(h^{*}, \bm{z}_{j}) + \epsv_{j} \right) \geq 1 - \delta
\enspace.
\]

This seems familiar, but it is not quite the same as the 2-tail Hoeffding bound on each $\Risk(h', \ProbDist_{j})$ used by

<ref>, thus this tail bound must be counted separately.
Now, we substitute into the result of part 1, again applying monotonicity, to get

\[
%\Risk(h^{*}, \ProbDist_{j}) \leq \ERisk(h^{*}, \bm{z}_{j}) + \epsv_{j}
\Malfare\left(j \mapsto \Risk(\hat{h}, \ProbDist_{j}) %; \wv
\right)
\leq \Malfare\left(j \mapsto \Risk(h^{*}, \ProbDist_{j}) + 2\ERade_{\bm{m}_{j}}(\hat{\HC}_{j}, \bm{z}_{j}) + 3\epsv_{j} %; \wv
\right)
\enspace.
\]

Applying the Lipschitz property then yields the final portion of part 2.

By union bound, we may conclude the result with probability at least $1 - 6\NGroups\delta$.

We now show <ref>.

We first show that the restricted parameter spaces of ${\HC}^{*}_{i}$ and $\hat{\HC}_{i}$ are convex sets.

The crux of
this result

is to show
that $\Malfare\bigl(j \mapsto f_{j}(\bm{\beta})\bigr)$ is quasiconvex, where $f_{j}(x)$ represents $\ERisk(h_{\bm{\beta}}, \bm{z}_{j}) - \bm{c}_{j}$ or $\Risk(h_{\bm{\beta}}, \ProbDist_{j}) - \bm{c}_{j}$ for some constant $\bm{c} \in \R^{\NGroups}$.
This indeed holds, so long as $f_{j}(\bm{\beta})$ is quasiconvex.
First note that convexity of
loss immediately implies convexity of (empirical) risk.
Now, by standard compositional rules, since we assume $\Malfare(\cdot)$ to be quasiconvex and monotonic, we conclude that $\Malfare(j \mapsto f_{j}(\bm{\beta}))$ is quasiconvex in $\bm{\beta} \in \bm{B}$.

Now, converting $\HC$ to $\bm{B}$, observe that the parameter spaces associated with both $\HC_{i}^{*}$ in (<ref>)

\begin{equation*}
%\HC_{i}^{*} \doteq
\left\{
%h \in \HC
\bm{\beta} \in \bm{B}
\,\middle|\, \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h_{\bm{\beta}}, \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h_{\bm{\beta}}, \ProbDist_{i}) - \etav_{i}^{} \end{cases} %; \wv \!
\right) \leq \inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \Risk(h', \ProbDist_{i}) + \epsv_{i} \end{cases} %; \wv \!
\right) \! \right\}
\enspace,
\end{equation*}

and also $\hat{\HC}_{i}$ in (<ref>)

\begin{equation*}
%\hat{\HC}_{i} \doteq
\left\{
%h \in \hat{\HC}
\bm{\beta} \in \bm{B}
\,\middle|\, \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h_{\bm{\beta}}, \bm{z}_{j}) \\ j \! = \! i \!\! & \ERisk(h_{\bm{\beta}}, \bm{z}_{i}) - 2\hat{\etav}_{i} \end{cases} %\! ; \wv
\right) \leq \inf_{\!h' \in \HC\!} \Malfare\!\left( j \mapsto \begin{cases} j \! \neq \! i \!\! & \ERisk(h', \bm{z}_{j}) \\ j \! = \! i \!\! & \ERisk(h', \bm{z}_{i}) + 2\epsv_{i} \end{cases} %\! ; \wv
\right) \! \right\}
\enspace,
\end{equation*}

are subsets of the convex set $\bm{B}$.
In particular, the RHS of the condition is constant in $\bm{\beta}$, and as above, the LHS is quasiconvex in $\bm{\beta}$, thus both restricted parameter spaces are convex sets.

note that
once we determine the parameter space to be convex, Monte-Carlo Rademacher averages can be efficiently computed via standard convex optimization techniques, e.g., first-order methods to maximize a linear objective on a convex set.
Key to this observation is that we assumed $g \circ \HC$ to be an affine function family, thus even after multiplying terms by $\pm 1$ in the Monte-Carlo Rademacher average (<ref>), the objective of the supremum remains convex.

Finally, observe that if $\Malfare(\cdot)$ is convex and monotonically increasing, then the EMM objective is also convex. This follows from standard compositional rules, see discussion following <cit.> equation (3.15).  EMM then reduces to minimizing a convex function on a convex set.

§ IMPLEMENTATION DETAILS

All code used to generate the results in this paper are available upon request.

The computation of
each supremum in (<ref>), i.e., $\ERade{}^n_{m}(g \circ \HC, \bm{z}_{i}; \vsigma)$
and $\ERade{}^n_{m}(g \circ \hat{\HC}_{i}, \bm{z}_{i}; \vsigma)$

optimize linear functions of $\beta$.
However, since the restricted hypothesis constraints are convex functions (see <ref>) over the
parameter space, we need to use solvers that can handle
nonlinear convex constraints.
For this reason, we use either the ECOS <cit.> or SCS <cit.> algorithms available in CVXPY <cit.>. These algorithms are also able to compute the upper bound of the restricted hypothesis class constraint itself, which minimizes an objective  which is
dependent on the loss $\ell$.