* Zhu [2017] Xiaojin Zhu.  _Semi-supervised Learning_ , pages 1142–1147.  Springer US, 2017.
  * Joachims et al. [1999] Thorsten Joachims et al.  Transductive inference for text classification using support vector machines.  In _Proceedings of the 16th International Conference on Machine Learning (ICML)_ , volume 99, pages 200–209, 1999.
  * Blum and Mitchell [1998] Avrim Blum and Tom Mitchell.  Combining labeled and unlabeled data with co-training.  In _Proceedings of the eleventh annual conference on Computational learning theory_ , pages 92–100, 1998.
  * Dasgupta et al. [2002] Sanjoy Dasgupta, Michael Littman, and David McAllester.  PAC generalization bounds for co-training.  In T. Dietterich, S. Becker, and Z. Ghahramani, editors, _Advances in Neural Information Processing Systems_ , volume 14. MIT Press, 2002.  URL https://proceedings.neurips.cc/paper/2001/file/4c144c47ecba6f8318128703ca9e2601-Paper.pdf.
  * Littlestone and Warmuth [1994] Nick Littlestone and Manfred K Warmuth.  The weighted majority algorithm.  _Information and computation_ , 108(2):212–261, 1994.
  * Hanneke and Yang [2015] Steve Hanneke and Liu Yang.  Minimax analysis of active learning.  _J. Mach. Learn. Res._ , 16(12):3487–3602, 2015\.
  * Dasgupta [2005] Sanjoy Dasgupta.  Coarse sample complexity bounds for active learning.  _Advances in neural information processing systems_ , 18, 2005.
  * Beimel et al. [2013b] Amos Beimel, Kobbi Nissim, and Uri Stemmer.  Characterizing the sample complexity of private learners.  In _Proceedings of the 4th conference on Innovations in Theoretical Computer Science_ , pages 97–110, 2013b.
  * Kulkarni and Vidyasagar [1997] Sanjeev R Kulkarni and Mathukumalli Vidyasagar.  Learning decision rules for pattern classification under a family of probability measures.  _IEEE Transactions on Information Theory_ , 43(1):154–166, 1997.
  * Vidyasagar et al. [2001] M Vidyasagar, S Balaji, and Barbara Hammer.  Closure properties of uniform convergence of empirical means and PAC learnability under a family of probability measures.  _Systems & control letters_, 42(2):151–157, 2001.
  * Zhang et al. [2021] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning (still) requires rethinking generalization.  _Commun. ACM_ , 64(3):107–115, 2021.
  * Nagarajan and Kolter [2019] Vaishnavh Nagarajan and J. Zico Kolter.  Uniform convergence may be unable to explain generalization in deep learning.  In _Proceedings of the 33rd International Conference on Neural Information Processing Systems_ , 2019.
  * Alon et al. [2021b] Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev.  Adversarial laws of large numbers and optimal regret in online classification.  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , pages 447–455, 2021b.
  * Crammer et al. [2008] Koby Crammer, Michael Kearns, and Jennifer Wortman.  Learning from multiple sources.  _Journal of Machine Learning Research_ , 9(8), 2008.
  * Kasiviswanathan et al. [2011] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.  What can we learn privately?  _SIAM Journal on Computing_ , 40(3):793–826, 2011\.
  * Daniely and Shalev-Shwartz [2014] Amit Daniely and Shai Shalev-Shwartz.  Optimal learners for multiclass problems.  In _Conference on Learning Theory_ , pages 287–316. PMLR, 2014.
  * [49] S. Hanneke (https://cstheory.stackexchange.com/users/52878/s hanneke).  Proper PAC learning VC dimension bounds.  Theoretical Computer Science Stack Exchange.  URL https://cstheory.stackexchange.com/q/44252.  URL:https://cstheory.stackexchange.com/q/44252 (version: 2019-07-11).
  * Shimodaira [2000] Hidetoshi Shimodaira.  Improving predictive inference under covariate shift by weighting the log-likelihood function.  _Journal of statistical planning and inference_ , 90(2):227–244, 2000.
  * David et al. [2010] Shai Ben David, Tyler Lu, Teresa Luu, and Dávid Pál.  Impossibility theorems for domain adaptation.  In _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics_ , pages 129–136. JMLR Workshop and Conference Proceedings, 2010.
  * Bassily et al. [2020a] Raef Bassily, Shay Moran, and Anupama Nandi.  Learning from mixtures of private and public populations.  _arXiv preprint arXiv:2008.00331_ , 2020a.
  * Athalye et al. [2018] Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok.  Synthesizing robust adversarial examples.  In _International conference on machine learning_ , pages 284–293. PMLR, 2018.
  * Montasser et al. [2020] Omar Montasser, Steve Hanneke, and Nathan Srebro.  Reducing adversarially robust learning to non-robust PAC learning.  _arXiv preprint arXiv:2010.12039_ , 2020.
  * Ailon et al. [2018] Nir Ailon, Anup Bhattacharya, and Ragesh Jaiswal.  Approximate correlation clustering using same-cluster queries.  In _Latin American Symposium on Theoretical Informatics_ , pages 14–27. Springer, 2018.
  * Bousquet and Elisseeff [2002] Olivier Bousquet and André Elisseeff.  Stability and generalization.  _The Journal of Machine Learning Research_ , 2:499–526, 2002.
  * Dwork and Feldman [2018] Cynthia Dwork and Vitaly Feldman.  Privacy-preserving prediction.  In _Conference On Learning Theory_ , pages 1693–1702. PMLR, 2018\.
  * Shalev-Shwartz et al. [2010] Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan.  Learnability, stability and uniform convergence.  _The Journal of Machine Learning Research_ , 11:2635–2670, 2010.
  * Dagan and Feldman [2020] Yuval Dagan and Vitaly Feldman.  PAC learning with stable and private predictions.  In _Conference on Learning Theory_ , pages 1389–1410. PMLR, 2020\.
  * Kearns [1998] Michael Kearns.  Efficient noise-tolerant learning from statistical queries.  _Journal of the ACM (JACM)_ , 45(6):983–1006, 1998.
  * Rothblum and Yona [2018] Guy N Rothblum and Gal Yona.  Probably approximately metric-fair learning.  _arXiv preprint arXiv:1803.03242_ , 5(2), 2018.
  * Bassily et al. [2020b] Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Steven Wu.  Private query release assisted by public data.  In _International Conference on Machine Learning_ , pages 695–703. PMLR, 2020b.

##  Appendix A Doubly Bounded Loss

In this section we discuss a natural generalization of loss functions over
finite label classes we call doubly bounded loss: for all distinct
$y,y^{\prime}\in Y$, we require $\ell(y,y^{\prime})\in[a,b]$ for some $b\geq
a>0$. This is trivially satisfied by any loss function on a finite label class
that satisfies the identity of indiscernibles.

######  Definition A.1 (Doubly Bounded Loss).

We say $\ell:Y\to Y$ is $(a,b)$-bounded if there exist $b\geq a>0$ for any
distinct $y,y^{\prime}\in Y$:

$\ell(y,y^{\prime})\in[a,b].$

As discussed in Section 6.1, since we now allow $Y$ to be infinite, we need to
work with discrete learnability instead of realizable learnability. We can use
a slight modification to the discretization technique in Theorem 6.5 to prove
the equivalence of discrete and agnostic learnability for doubly-bounded loss
functions. Note that this is stronger than our guarantee for $c$-approximate
pseudometrics, which only gives $c$-agnostic learnability.

######  Theorem A.2.

Let $\ell:Y\times Y\to\mathbb{R}_{\geq 0}$ be an $(a,b)$-bounded loss
function. Then for any class $(\mathscr{D},X,H,\ell)$ the following are
equivalent:

  1. 1.

$(X,H,\mathscr{D},\ell)$ is (properly) discretely-learnable

  2. 2.

$(X,H,\mathscr{D},\ell)$ is (properly) agnostically learnable.

###### Proof.

The proof that agnostic learnability implies discrete learnability is the same
as in Theorem 6.5, so we focus only the forward direction. Assume
$(\mathscr{D},X,H,\ell)$ is discretely-learnable. Fix
$\varepsilon^{\prime}=\frac{a\varepsilon}{4b}$, and let
$H_{\varepsilon^{\prime}}$ be a learnable
$\varepsilon^{\prime}$-discretization of $H$. We argue that running
LearningToCover on $H_{\varepsilon^{\prime}}$ (using the promised discrete
learner) gives the desired agnostic learner. As before, it is sufficient to
prove that $C(S_{U})$ contains a hypothesis $h^{\prime}$ such that
$\text{err}_{D,\ell}(h^{\prime})\leq OPT+\varepsilon/2$. Since $\ell$ is upper
bounded, standard empirical risk minimization arguments then give the desired
result.

To see why $C(S_{U})$ has this property, recall from Lemma 5.2 that for any
$h\in H_{\varepsilon^{\prime}}$, with probability at least $1-\delta/2$ there
exists $h^{\prime}\in C(S_{U})$ that is $\varepsilon^{\prime}$-close to $h$ in
the following sense:

$\mathbb{E}_{x\sim
D_{X}}[\ell(h^{\prime}(x),h(x))]\leq\frac{a\varepsilon}{4b}.$

Because $\ell$ is $a$-lower bounded, this implies that $h^{\prime}$ must be
close to $h$ in classification error:

$\Pr_{x\sim D_{X}}[h(x)\neq h^{\prime}(x)]\leq\frac{\varepsilon}{4b},$

and since the loss is bounded by $b$, the risk of $h^{\prime}$ cannot be much
more than of $h$:

$\text{err}_{D,\ell}(h^{\prime})\leq\text{err}_{D,\ell}(h)+\varepsilon/4.$

Let $h_{OPT}\in H$ be an optimal hypothesis. Since $H_{\varepsilon^{\prime}}$
$\varepsilon^{\prime}$-covers $H$, there exists
$h^{\varepsilon^{\prime}}_{OPT}\in H_{\varepsilon^{\prime}}$ such that:

$\text{err}_{D,\ell}(h^{\varepsilon^{\prime}}_{OPT})-\text{err}_{D,\ell}(h_{OPT})\leq\varepsilon^{\prime}.$

Let $h^{\prime\varepsilon^{\prime}}_{OPT}\in H_{\varepsilon^{\prime}}$ denote
the output of the base learner $\mathcal{A}$ on the labeling given by
$h^{\varepsilon^{\prime}}_{OPT}$. Then by the above, we have that:

$\displaystyle\text{err}_{D,\ell}(h^{\prime\varepsilon^{\prime}}_{OPT})$
$\displaystyle=\underset{(x,y)\sim
D}{\mathbb{E}}[\ell(h^{\prime\varepsilon^{\prime}}_{OPT}(x),y)]$
$\displaystyle\leq\underset{(x,y)\sim
D}{\mathbb{E}}[\ell(h^{\varepsilon^{\prime}}_{OPT}(x),y)]+\varepsilon/4$
$\displaystyle\leq\underset{(x,y)\sim
D}{\mathbb{E}}[\ell(h^{\varepsilon^{\prime}}_{OPT}(x),y)-\ell(h_{OPT}(x),y)+\ell(h_{OPT}(x),y)]+\varepsilon/4$
$\displaystyle=\text{err}_{D,\ell}(h^{\varepsilon^{\prime}}_{OPT})-\text{err}_{D,\ell}(h_{OPT})+OPT+\varepsilon/4$
$\displaystyle\leq OPT+\varepsilon/2$

as desired. ∎

It is worth noting that the upper bound on the loss can be removed if the
adversary is restricted to choosing a marginal over $Y$ which is weakly
concentrated.

##  Appendix B Robust Learning

Robust learning is an extension to the PAC setting that models an adversary
with the power to perturb examples at test time. In practice, this corresponds
to the fact that we’d like our predictors to be stable to small amounts of
adversarial noise—this could range anywhere from a sticker on a stop-sign
tricking a self-driving car, to completely imperceptible perturbations that
totally fool standard classifiers. The latter was famously demonstrated by
Athalye, Engstrom, Ilyas, and Kwok [53], who showed how to generate such
perturbations and provided the classic example of tricking a standard ImageNet
classifier into thinking a turtle was a gun. Their seminal work caused an
explosion of both practical and theoretical research in the area.191919Their
work has over 900 citations despite being only four years old.

Formally, adversarial robustness is modeled simply by changing the error
function to be the maximum error over some pre-defined set of neighboring
perturbations.

######  Definition B.1 (Robust Loss).

Let $X$ be an instance space and $\mathcal{U}:X\to P(X)$ a “perturbation
function” mapping elements to a set of possible perturbations. Given a loss
function $\ell:Y\times Y\to\mathbb{R}_{\geq 0}$, the robust loss of a concept
$h:X\to Y$ with respect to a distribution $D$ over $X\times Y$ is:

$\text{R-err}_{\mathcal{U},D}(h)=\underset{(x,y)\sim
D}{\mathbb{E}}\left[\max_{x^{\prime}\in\mathcal{U}(x)}\ell(h(x^{\prime}),y)\right].$

In other words, a hypothesis with low robust loss performs well even against
an adversary who can perturb $x$ to any “nearby point” (i.e. any
$x^{\prime}\in\mathcal{U}(x)$). Standard realizable and agnostic Robust PAC-
learning are then simply defined by replacing the standard error function with
the robust error function. Robust learning in the distribution-family model
does require one extra twist: we need to make sure that each hypothesis in the
class actually has a corresponding distribution over which it is realizable.
To this end, we introduce a basic notion of closure for distribution families.

######  Definition B.2 (Robust Closure).

Let $\mathscr{D}$ be a set of distributions over an instance space $X$ and $H$
a concept class. Given any concept $h$, let $X_{h}$ denote the set of points
in $X$ on which $h$ has $0$ robust loss with respect to itself, that is:

$X_{h}\coloneqq\\{x\in\text{X}:\forall
x^{\prime}\in\mathcal{U}(x),\ell(h(x^{\prime}),h(x))=0\\}.$

For notational simplicity, let $D|_{h}$ denote the restriction $D|_{X_{h}}$.
The robust closure of $\mathscr{D}$ under $H$ is:

$\mathscr{D}_{H}\coloneqq\mathscr{D}\cup\bigcup_{D\in\mathscr{D},h\in
H}D|_{h}.$

In the robust distribution-family model, it only really makes sense to define
realizable learnability over the robust closure of $\mathscr{D}$, since
otherwise there may be hypotheses in the class that are not realizable with
respect to any distribution in $\mathscr{D}$ and cannot be chosen by the
adversary at all. With this in mind, let’s formalize this model.

######  Definition B.3 ((Realizable) Distribution-Family Robust PAC Learning).

A class $(\mathscr{D},X,H,\ell)$ is Robustly PAC-learnable in the realizable
setting with respect to perturbation function $\mathcal{U}$ if there exists an
algorithm $\mathcal{A}$ and function $n(\varepsilon,\delta)$ such that for all
$\varepsilon,\delta>0$ and distributions $D$ over $X\times Y$ satisfying:

  1. 1.

The marginal $D_{X}\in\mathscr{D}_{H}$,

  2. 2.

$\min_{h\in H}\text{R-err}_{\mathcal{U},D}(h)=0$,

then:

$\Pr_{S\sim
D^{n(\varepsilon,\delta)}}[\text{R-err}_{\mathcal{U},D}(\mathcal{A}(S))>\varepsilon]\leq\delta.$

Agnostic learnability is defined similarly, but since the adversary is
unrestricted, there is no longer any need to take the robust closure.

######  Definition B.4 ((Agnostic) Distribution-Family Robust PAC Learning).

A class $(\mathscr{D},X,H,\ell)$ is Robustly PAC-learnable in the agnostic
setting with respect to perturbation function $\mathcal{U}$ if there exists an
algorithm $\mathcal{A}$ and function $n(\varepsilon,\delta)$ such that for all
$\varepsilon,\delta>0$ and distributions $D$ over $X\times Y$ satisfying
$D_{X}\in\mathscr{D}$, then:

$\Pr_{S\sim
D^{n(\varepsilon,\delta)}}[\text{R-err}_{\mathcal{U},D}(\mathcal{A}(S))>OPT+\varepsilon]\leq\delta,$

where $OPT=\min_{h\in H}\\{\text{R-err}_{\mathcal{U},D}(h)\\}$.

We note that different works consider different models of access to the
perturbation set $\mathcal{U}$ as well (e.g. assuming $\mathcal{U}$ is known
to the learner [8], or has some type of oracle access [54, 24]). Our reduction
requires fairly weak access to $\mathcal{U}$—it is enough to be able to
estimate the empirical robust loss of a hypothesis $h$ over any finite sample
$S\subset X$. With this in mind, let’s now prove realizable and agnostic
robust learning are equivalent in the distribution-family model. We’ll focus
on the special case of (multi-class) classification, and start by re-stating
our modified algorithm for simplicity of presentation.

Input: Realizable Robust PAC-Learner $\mathcal{A}$

Algorithm:

  1. 1.

Draw an unlabeled sample $S_{U}$, and labeled sample $S_{L}$.

  2. 2.

Run $\mathcal{A}$ over all possible subsets and labelings of $S_{U}$ to get:

$C(S)\coloneqq\\{\mathcal{A}(S,h(S))\leavevmode\nobreak\ |\leavevmode\nobreak\
S\subseteq S_{U},h\in H|_{S}\\}.$

  3. 3.

Return the hypothesis in $C(S)$ with lowest empirical robust error over
$S_{L}$.

Algorithm 5 Agnostic to Realizable Reduction Robust Setting

######  Theorem B.5.

If $(\mathscr{D},X,H)$ is robustly PAC-learnable in the realizable setting
with sample complexity $n(\varepsilon,\delta)$, then Algorithm 5 robustly
learns $(\mathscr{D},X,H)$ in the agnostic setting in:

$m_{U}(\varepsilon,\delta)\leq
O\left(\max_{\mu\in[0,1-\varepsilon]}\left\\{\frac{n(\varepsilon/(2(1-\mu)),\delta/3)}{1-\mu}\right\\}\right)$

unlabeled samples, and

$m_{L}(\varepsilon,\delta)\leq
O\left(\frac{m_{U}(\varepsilon,\delta)+\log(1/\delta)}{\varepsilon^{2}}\right)$

labeled samples.

###### Proof.

The proof is similar to Theorem 5.3, but like malicious noise (Theorem 6.8),
requires the use of subsampling. The key issue is that for a distribution $D$
over $X\times Y$, the optimal hypothesis $h_{OPT}$ may not be realizable with
respect to $D_{X}$, that is we may have:

$\text{R-err}_{U,D_{X}\times h_{OPT}}(h_{OPT})>0.$

As a result, our realizable learner (and therefore LearningToCover) has no
guarantees over this distribution. On the other hand, our realizable learner
does have good guarantees over the _restricted marginal_ $D_{X}|_{h_{OPT}}$.
We can then fix the above issue by running LearningToCover of all subsets of
$S$ including its restriction to $X_{h_{OPT}}$. We will see that this
essentially simulates running the realizable learner on the realizable
restriction $D_{X}|_{h_{OPT}}$ and recovers the desired guarantees.

Let’s take a look at this more formally. As in our previous arguments it is
enough to prove that $C(S)$ contains a hypothesis $h^{\prime}$ with robust
error at most $OPT+\varepsilon/2$, since a standard Chernoff bound tells us
that $O(\log(|C(S)|/\delta)/\varepsilon^{2})$ labeled examples are enough to
estimate the robust loss of every hypothesis in $C(S)$ with high probability.
We note that this is the only step in our reduction which requires access to
the perturbation set $\mathcal{U}$.

It is left to show that $C(S)$ satisfies this property. Let $D|_{h_{OPT}}$
denote the restriction of $D$ to $X_{h_{OPT}}$, the points in $X$ on which
$h_{OPT}$ has $0$ robust loss with respect to itself. Let $\bar{D}|_{h_{OPT}}$
be the restriction to the complement, that is $X\setminus X_{h_{OPT}}$. The
idea is to decompose our analysis into two separate parts over $D|_{h_{OPT}}$
and $\bar{D}|_{h_{OPT}}$. With this in mind, let $\mu^{*}$ denote the mass of
$D_{X}$ on $X_{h_{OPT}}$, and let $OPT^{\prime}$ denote the robust error of
$h_{OPT}$ over $D|_{h_{OPT}}$. Since we are restricting our attention to
classification error, notice that we can decompose $OPT$ as:

$\displaystyle OPT$ $\displaystyle=\text{R-err}_{\mathcal{U},D}(h_{OPT})$
$\displaystyle=\underset{(x,y)\sim D}{\Pr}\left[\exists
x^{\prime}\in\mathcal{U}(x):h_{OPT}(x^{\prime})\neq y\right]$
$\displaystyle=\mu^{*}\underset{(x,y)\sim\bar{D}|_{h_{OPT}}}{\Pr}\left[\exists
x^{\prime}\in\mathcal{U}(x):h_{OPT}(x^{\prime})\neq
y\right]+(1-\mu^{*})\underset{(x,y)\sim D|_{h_{OPT}}}{\Pr}\left[\exists
x^{\prime}\in\mathcal{U}(x):h_{OPT}(x^{\prime})\neq y\right]$
$\displaystyle=\mu^{*}+(1-\mu^{*})OPT^{\prime},$

where the last step follows from noting that by definition for all $x$ in the
support of $\bar{D}|_{h_{OPT}}$, $h_{OPT}$ is not constant on
$\mathcal{U}(x)$. To get a function within $\varepsilon/2$ robust loss of
$OPT$, we claim it is sufficient to prove $C(S)$ contains some $h$ within
robust error $\varepsilon/(2(1-\mu^{*}))$ of $h_{OPT}$ over $D|_{h_{OPT}}$,
that is some $h$ satisfying:

$\Pr_{x\sim D_{X}|_{h_{OPT}}}[\exists
x^{\prime}\in\mathcal{U}(x):h(x^{\prime})\neq
h_{OPT}(x^{\prime})]\leq\varepsilon/(2(1-\mu^{*})).$ (3)

This follows from a similar analysis to the above. Namely, letting $R(h,x,y)$
denote the event

$R(h,x,y)\coloneqq\exists x^{\prime}\in\mathcal{U}(x):h(x^{\prime})\neq y$

for notational simplicity, we can break down $\text{R-err}_{\mathcal{U},D}(h)$
as:

$\displaystyle\text{R-err}_{\mathcal{U},D}(h)$
$\displaystyle=\mu^{*}\underset{(x,y)\sim\bar{D}|_{h_{OPT}}}{\Pr}\left[R(h,x,y)\right]+(1-\mu^{*})\underset{(x,y)\sim
D|_{h_{OPT}}}{\Pr}\left[R(h,x,y)\right]$
$\displaystyle\leq\mu^{*}+(1-\mu^{*})\underset{(x,y)\sim
D|_{h_{OPT}}}{\Pr}\left[R(h,x,y)\right]$
$\displaystyle\leq\mu^{*}+(1-\mu^{*})\left(\underset{(x,y)\sim
D|_{h_{OPT}}}{\Pr}\left[R(h_{OPT},x,y)\right]+\underset{(x,y)\sim
D|_{h_{OPT}}}{\Pr}\left[\exists x^{\prime}\in\mathcal{U}(x):h(x^{\prime})\neq
h_{OPT}(x^{\prime})\right]\right)$
$\displaystyle\leq\mu^{*}+(1-\mu^{*})\left(OPT^{\prime}+\frac{\varepsilon}{2(1-\mu^{*})}\right)$
$\displaystyle=OPT+\varepsilon/2.$

It remains to prove that $C(S)$ contains a hypothesis satisfying Equation 3
with high probability. To see this, note that by definition of realizable
robust learning, on a labeled sample $(S,h_{OPT}(S))\sim D|_{h_{OPT}}\times
h_{OPT}$ of size $n(\varepsilon/(2(1-\mu^{*})),\delta/3)$ our learner will
output $h$ satisfying:

$\Pr_{x\sim D_{X}|_{h_{OPT}}}[\exists
x^{\prime}\in\mathcal{U}(x):h(x^{\prime})\neq
h_{OPT}(x)]\leq\varepsilon/(2(1-\mu^{*}))$

with probability at least $1-\delta/3$. To get Equation 3, it is then enough
to note that $h_{OPT}$ is constant on $\mathcal{U}(x)$ for all $x$ in the
support of $D_{X}|_{h_{OPT}}$ by definition.

The idea is now to draw a large enough unlabeled sample such that with
probability at least $1-\delta/3$, the restriction to $X_{h_{OPT}}$ is at
least this size. By a Chernoff bound, it is enough to draw
$c_{1}\frac{n(\varepsilon/(1-\mu^{*}),\delta/3)}{1-\mu^{*}}$ points to achieve
this for some large enough constant $c_{1}>0$.202020We’ve assumed for
simplicity that $n(\varepsilon,\delta)\geq\Omega(\log(1/\delta))$. This
assumption can be removed by including an extra additive factor of
$\log(1/\delta)$. Since we do not know $\mu^{*}$, we’ll need to draw
$c_{1}\max_{\mu\in[0,1-\varepsilon]}\left\\{\frac{n(\varepsilon/(1-\mu),\delta/3)}{1-\mu}\right\\}$
points to ensure this property holds (if $\mu^{*}\geq 1-\varepsilon$, note
that any hypothesis gives a valid solution). By a union bound we have that
this overall process succeeds with probability at least $1-2\delta/3$, and
outputting the hypothesis in $C(S)$ with the lowest empirical robust risk then
succeeds with probability $1-\delta$ as desired. ∎

Theorem B.5 can be extended to many of the generic property generalization
results in the main body, including approximate pseudometric loss, malicious
noise, and semi-private learning, though the exact parameters may be somewhat
weaker (e.g. learning over non-binary loss may incur additional factors and
lead to $c$-agnostic rather than truly agnostic learning).

##  Appendix C Partial PAC-Learning

Partial PAC-learning is an extension of the standard PAC model to functions
that are only defined on a certain portion of the input. Originally introduced
by Long [12] and recently developed in greater depth by Alon, Hanneke,
Holzman, and Moran (AHHM) [13], this model allows for the theoretical
formalization of popular data-dependent assumptions such as _margin_ that have
no known analog in the PAC model. Combined with the distribution-family
framework, this captures a significant portion of learning assumptions studied
in both theory and practice (e.g. learning halfspaces with margin and
distributional tail bounds). Let’s formalize this model, starting with partial
functions.

######  Definition C.1 (Partial Function).

Let $X$ be an instance space and $Y$ a label space. A partial function is a
labeling $f:X\to Y\cup\\{*\\}$, where elements labeled “$*$” are thought as of
undefined. The support of $f$, denoted $\text{supp}(f)$, is the set of
elements $x\in X$ s.t. $f(x)\neq*$.

Standard Partial PAC-learning is defined much like the standard model with the
simple modification that “$*$” labels are always considered to be incorrect.
As a result, in the realizable case, when the adversary selects a particular
partial function $f$, their marginal distribution over the instance space $X$
must be restricted to lying on $\text{supp}(f)$. This makes formalizing data-
dependent assumptions easy. If one wanted to consider halfspaces with margin
$\gamma$ for instance, one simply labels every point within $\gamma$ of the
decision boundary as “$*$.” Interestingly, much like the distribution-family
setting, Partial-PAC learning falls outside both the uniform convergence and
the sample compression paradigm [55]. AHHM also show a dramatic failure of
empirical risk minimization: not only does naively applying an ERM to the
partial class fail, it will also fail on any total extension of the class.
Despite the lack of these standard tools, both Long and AHHM were able to show
that distribution-free classification of partial classes is still controlled
by VC dimension, and as a result that the equivalence of realizable and
agnostic learnability extends to this setting. In this section, we’ll discuss
how a variant of our reduction shows that this result extends to the
distribution-family model, extended loss function, and to properties beyond
agnostic learning.

In the distribution-family model, formalizing realizable learnability requires
some slight changes from the standard model, since we need to make sure our
hypotheses are actually realizable over some distribution in the family (this
is automatic in the distribution-free setting). To this end, we introduce a
basic notion of closure for distribution families.

######  Definition C.2 (Partial Closure).

Let $\mathscr{D}$ be a set of distributions over an instance space $X$ and $H$
a concept class. Given any concept $h$, and distribution $D$ over $X$, let
$D|_{h}$ denote the restriction $D|_{\text{supp}(f)}$. The partial closure of
$\mathscr{D}$ under $H$ is:

$\mathscr{D}_{H}\coloneqq\mathscr{D}\cup\bigcup_{D\in\mathscr{D},h\in
H}D|_{h}.$

In the realizable model it makes more sense to work with the closure of
$\mathscr{D}$ than $\mathscr{D}$ itself, since otherwise the class $H$ may
contain hypotheses that cannot be realized over any distribution, and
therefore cannot be accessed by the adversary at all. For simplicity, we’ll
also restrict our attention to (multi-class) classification where the label
space $Y=[m]$, and recall that the loss of any undefined point is always $1$.

######  Definition C.3 ((Realizable) Distribution-Family Partial PAC
Learning).

A partial class $(\mathscr{D},X,H)$ is PAC-learnable in the realizable setting
if there exists an algorithm $\mathcal{A}$ and function
$n(\varepsilon,\delta)$ such that for all $\varepsilon,\delta>0$ and
distributions $D$ over $X\times Y$ satisfying:

  1. 1.

The marginal $D_{X}\in\mathscr{D}_{H}$,

  2. 2.

$\min_{h\in H}\text{err}_{D}(h)=0$,

then:

$\Pr_{S\sim
D^{n(\varepsilon,\delta)}}[\text{err}_{D}(\mathcal{A}(S))>\varepsilon]\leq\delta,$

where the error $\text{err}_{D}(h)$ is standard classification error:

$\text{err}_{D}(h)=\Pr_{(x,y)\sim D}[h(x)\neq y].$

Agnostic learnability is defined analogously, but since the adversary is
unrestricted, there is no need to move to the closure of $\mathscr{D}$.

######  Definition C.4 ((Agnostic) Distribution-Family Partial PAC Learning).

A partial class $(\mathscr{D},X,H)$ is PAC-learnable in the agnostic setting
if there exists an algorithm $\mathcal{A}$ and function
$n(\varepsilon,\delta)$ such that for all $\varepsilon,\delta>0$ and
distributions $D$ over $X\times Y$ satisfying $D_{X}\in\mathscr{D}$, then:

$\Pr_{S\sim
D^{n(\varepsilon,\delta)}}[\text{err}_{D}(\mathcal{A}(S))>OPT+\varepsilon]\leq\delta.$

The issue with our standard reduction strategy for partial functions is that
in the agnostic model, the adversary’s marginal distribution over $X$ might
have support outside of $\text{supp}(h_{OPT})$, which causes LearningToCover
to lose its guarantee of outputting a non-uniform cover. This can be dealt
with by a variant of our subsampling technique. If we run LearningToCover over
all subsamples of the unlabeled sample $S_{U}$, one of these subsamples must
match the support of $h_{OPT}$. This is in fact the same strategy used for
adversarial robustness in Appendix B, but we will include the algorithm again
to make this section self-contained.

Input: Realizable Robust PAC-Learner $\mathcal{A}$

Algorithm:

  1. 1.

Draw an unlabeled sample $S_{U}$, and labeled sample $S_{L}$.

  2. 2.

Run $\mathcal{A}$ over all possible subsets and labelings of $S_{U}$ to get:

$C(S)\coloneqq\\{\mathcal{A}(S,h(S))\leavevmode\nobreak\ |\leavevmode\nobreak\
S\subseteq S_{U},h\in H|_{S}\\}.$

  3. 3.

Return the hypothesis in $C(S)$ with lowest empirical error over $S_{L}$.

Algorithm 6 Agnostic to Realizable Reduction Partial PAC Setting

######  Theorem C.5.

If $(\mathscr{D},X,H)$ is a realizably PAC-learnable partial class with sample
complexity $n(\varepsilon,\delta)$, then Algorithm 6 agnostically learns
$(\mathscr{D},X,H)$ in

$m_{U}(\varepsilon,\delta)\leq
O\left(\max_{\mu\in[0,1-\varepsilon]}\left\\{\frac{n(\varepsilon/(2(1-\mu)),\delta/3)}{1-\mu}\right\\}\right)$

unlabeled samples, and

$m_{L}(\varepsilon,\delta)\leq
O\left(\frac{m_{U}(\varepsilon,\delta)+\log(1/\delta)}{\varepsilon^{2}}\right)$

labeled samples.

###### Proof.

The proof is essentially the same as for Theorem B.5, but we repeat it here
for completeness. As always, it is enough to prove that $C(S)$ (from Algorithm
6) contains a hypothesis $h^{\prime}$ with error at most $OPT+\varepsilon/2$.
The key issue with our standard reduction is that the optimal hypothesis
$h_{OPT}$ may be undefined on certain examples in the unlabeled sample
$S_{U}$. By running over all subsamples of $S_{U}$, we in essence simulate
pulling samples only from the support of $h_{OPT}$, which is enough to get the
desired guarantee.

More formally, let $D|_{h_{OPT}}$ be the restriction of $D$ to
$\text{supp}(h_{OPT})$, and $\bar{D}|_{h_{OPT}}$ the restriction to its
complement $X\setminus\text{supp}(h_{OPT})$. The idea is to decompose our
analysis into two separate parts over $D|_{h_{OPT}}$ and $\bar{D}|_{h_{OPT}}$.
With this in mind, let $\mu^{*}$ denote the mass of $D_{X}$ on the undefined
portion of $h_{OPT}$, and let $OPT^{\prime}$ denote the error of $h_{OPT}$
over $D|_{h_{OPT}}$. Since we have restricted our attention to classification,
notice that we can decompose $OPT$ as:

$\displaystyle\text{err}_{D}(h_{OPT})$ $\displaystyle=\underset{(x,y)\sim
D}{\Pr}\left[h_{OPT}(x)\neq y\right]$
$\displaystyle=\mu^{*}\underset{(x,y)\sim\bar{D}|_{h_{OPT}}}{\Pr}\left[h_{OPT}(x)\neq
y\right]+(1-\mu^{*})\underset{(x,y)\sim D|_{h_{OPT}}}{\Pr}\left[h_{OPT}(x)\neq
y\right]$ $\displaystyle=\mu^{*}+(1-\mu^{*})OPT^{\prime}.$

We’d like to prove that $C(S)$ contains a hypothesis $h$ within
$\varepsilon/2$ error of optimal. We claim it is sufficient to show that
$C(S)$ contains a hypothesis within $\varepsilon/(2(1-\mu^{*}))$
classification distance of $h_{OPT}$, since:

$\displaystyle\text{err}_{D}(h)$
$\displaystyle=\mu^{*}\underset{(x,y)\sim\bar{D}|_{h_{OPT}}}{\mathbb{E}}\left[h(x)\neq
y\right]+(1-\mu^{*})\underset{(x,y)\sim
D|_{h_{OPT}}}{\mathbb{E}}\left[h(x)\neq y\right]$
$\displaystyle\leq\mu^{*}+(1-\mu^{*})\underset{(x,y)\sim
D|_{h_{OPT}}}{\mathbb{E}}\left[h(x)\neq y\right]$
$\displaystyle\leq\mu^{*}+(1-\mu^{*})\left(\underset{(x,y)\sim
D|_{h_{OPT}}}{\mathbb{E}}\left[h_{OPT}(x)\neq
y\right]+\frac{\varepsilon}{2(1-\mu^{*})}\right)$
$\displaystyle=\mu^{*}+(1-\mu^{*})OPT^{\prime}+\frac{\varepsilon}{2}$
$\displaystyle=OPT+\varepsilon/2,$

where the third line follows from the fact that $h^{\prime}$ and $h_{OPT}$
only differ on a $\frac{\varepsilon}{2(1-\mu^{*})}$ fraction of inputs over
$D|_{h_{OPT}}$.

It is left to argue that $C(S)$ contains such a hypothesis $h$. Recall that on
a labeled sample $(S,h(S))\sim D|_{h_{OPT}}\times h_{OPT}$ of size
$n(\varepsilon/(2(1-\mu^{*})),\delta/3)$, LearningToCover will contain $h$
that is $\varepsilon/(2(1-\mu^{*}))$-close to $h_{OPT}$ in classification
error over $D|_{h_{OPT}}$ with probability at least $1-\delta/3$. The idea is
then to draw a large enough unlabeled sample such that with probability at
least $1-\delta/3$, the restriction of the sample to $D|_{h_{OPT}}$ is at
least this size (since we run over every subsample, we will always hit this
restriction). By a Chernoff bound, it is enough to draw
$c_{1}\frac{n(\varepsilon/(2(1-\mu^{*})),\delta/3)}{1-\mu^{*}}$ points to
achieve this for some large enough constant $c_{1}>0$.212121As in Theorem B.5,
we’ve assumed for simplicity that
$n(\varepsilon,\delta)\geq\Omega(\log(1/\delta))$. This assumption can be
removed by including an extra additive factor of $\log(1/\delta)$. Since we do
not know $\mu^{*}$, we’ll need to draw
$c_{1}\max_{\mu\in[0,1-\varepsilon]}\left\\{\frac{n(\varepsilon/(1-\mu),\delta/3)}{1-\mu}\right\\}$
points to ensure this property holds (if $\mu^{*}\geq 1-\varepsilon$, note
that any hypothesis gives a valid solution). By a union bound we have that
this overall process succeeds with probability at least $1-2\delta/3$, and
outputting the hypothesis in $C(S)$ with the lowest empirical risk then
succeeds with probability $1-\delta$ as desired. ∎

Like Theorem B.5, Theorem C.5 can be extended to many of the generic property
generalization results in the main body, including approximate pseudometric
loss, malicious noise, and semi-private learning, though it may experience
some degradation of parameters (e.g. $c$-agnostic rather than truly agnostic
learning) depending on how the loss of “$*$” values are formalized in these
settings.

##  Appendix D Uniform Stability

Uniform stability, originally introduced by Bousquet and Elisseeff [56], is a
useful algorithmic property that is closely tied to both generalization and
privacy. Informally, an algorithm $\mathcal{A}$ is said to be uniformly stable
if for all elements $x\in X$, the probability that $\mathcal{A}$ changes its
output on $x$ over neighboring datasets is small.

######  Definition D.1 (Uniform Stability).

A learning algorithm is said to be $\alpha$-uniformly stable if for all
neighboring inputs $S,S^{\prime}$ which differ on a single example, all $x\in
X$, and all $y\in Y$:

$\Pr[\mathcal{A}(S)(x)=y]\leq\Pr[\mathcal{A}(S^{\prime})(x)=y]+\alpha.$

Uniform stability can also be thought of as a form of private prediction [57],
which protects against adversaries who have restricted access to a model only
through prediction responses on individual points (this is often the case in
practice since it is common to release APIs with query access rather than full
models). Like semi-privacy, this definition has the benefit of maintaining
practicality in a reasonable range of circumstances while weakening the
stringent requirements of standard private learning. Indeed, it is well known
that in the distribution-free classification setting, uniformly stable
learning and private prediction are both possible for any class with finite VC
dimension [58, 57, 59]. Unsurprisingly, these previous works (at least those
working in the agnostic model), rely on uniform convergence and uniform
covers. We’ll show these can be replaced with a variant of our standard
reduction. The argument is otherwise similar to the proof in [59].

######  Theorem D.2.

Let $(\mathscr{D},X,H)$ be a realizably learnable class with sample complexity
$n(\varepsilon,\delta)$. Then there exists an $\alpha$-uniformly stable,
$\alpha$-semi private algorithm that agnostically learns $(\mathscr{D},X,H)$
in only

$m_{U}(\varepsilon,\delta,\alpha)\leq
O\left(\frac{n(\varepsilon/2,\delta/2)}{\alpha}\right)$

unlabeled samples, and

$m_{L}(\varepsilon,\delta,\alpha)\leq
O\left(\frac{\log\left(\Pi_{H}(n(\varepsilon,\delta))\right)}{\min\\{\alpha\varepsilon,\varepsilon^{2}\\}}\right)$

labeled samples.

###### Proof.

The proof boils down to a standard subsampling trick first noted by [58].
Instead of drawing our standard unlabeled sample of size
$n(\varepsilon/2,\delta/2)$, we draw a sample of size
$\frac{n(\varepsilon/2,\delta/2)}{2\alpha}$ and run LearningToCover over a
random $\alpha/2$ fraction of the sample. This ensures that swapping out any
individual sample can only effect the result with probability $\alpha/2$.
Since this subsample is of size $n(\varepsilon/2,\delta/2)$, LearningToCover
keeps its standard guarantees and the output $C(S_{U})$ has a hypothesis
within $\varepsilon/2$ of optimal with probability $1-\delta/2$. We can now
apply the exponential mechanism with privacy parameter $\alpha/4$, which
ensures the algorithm is $\alpha/2$-uniformly stable with respect to the
labeled sample as well. The sample complexity bounds come from standard
analysis of the exponential mechanism and the size of $C(S_{U})$. Semi-privacy
comes for free due to our use of the exponential mechanism. ∎

As in previous sections, Theorem D.2 can be extended to any of the generic
property generalization results in the main body, including for instance
$c$-approximate pseudometric loss, malicious noise, and robustness to
covariate shift.

##  Appendix E Statistical Query Model

Kearns’ [60] statistical query model is a popular modification of PAC learning
where the sample oracle is replaced with the ability to ask noisy statistical
questions about the data.

######  Definition E.1 (Realizable SQ-learning).

Given a distribution $D$ over $X$ and $h\in H$, let $STAT(D,h)$ be an oracle
which upon input of a function $\psi:X\times Y\to[-1,1]$ and tolerance
$\tau\in\mathbb{R}_{\geq 0}$ may output any estimate of the expectation of
$\psi$ up to $\tau$ error, that is:

$STAT(D,h)(\psi,\tau)\in\mathbb{E}_{x\sim D}[\psi(x,h(x))]\pm\tau.$

We call a class $(\mathscr{D},X,H,\ell)$ SQ-learnable if for all
$\varepsilon>0$, there exists some tolerance $\tau=\tau(\varepsilon)$, query
complexity $n(\varepsilon,\tau)$, and an algorithm $\mathcal{A}$ such that for
all $D\in\mathscr{D}$ and $h\in H$, $\mathcal{A}$ achieves $\varepsilon$ error
in at most $n(\varepsilon,\tau)$ oracle calls to $STAT(D,h)$ with tolerance at
worst $\tau$.222222While we generally think of $\tau$ as being at worst
polynomial in $\varepsilon$, this is not strictly necessary for the model.

Agnostic learning is then defined analogously where $D,h$ is replaced with a
generic distribution over $X\times Y$ whose marginal lies in $\mathscr{D}$. We
can use a basic form of discretization to prove property generalization in the
SQ model.

######  Theorem E.2.

Let $\ell$ be a $c$-approximate pseudometric and $(\mathscr{D},X,H,\ell)$ a
realizably SQ-learnable class with query complexity $n(\varepsilon,\tau)$.
Then $(\mathscr{D},X,H,\ell)$ is $c$-agnostically SQ-learnable up to
$\varepsilon+\tau$ error in $(1/\tau)^{n(\varepsilon,\tau)}$ statistical
queries of tolerance at worst $\tau$.

###### Proof.

The idea is similar to our discretization in Theorem 6.5. The realizable SQ-
learner $\mathcal{A}$ makes some finite $n(\varepsilon,\tau)$ queries. Let
$C_{\mathcal{A}}$ denote the set of outputs of $\mathcal{A}$ when fed every
possible combination of responses from the discretized set
$\\{-1,-1+2\tau,\ldots,1-2\tau,1\\}$. For every $D\in\mathscr{D}$ and $h\in
H$, one of these combinations must be a valid query response in the realizable
model, so $C_{\mathcal{A}}$ covers $(\mathscr{D},X,H,\ell)$. By the same
arguments of Theorem 6.5, $C_{\mathcal{A}}$ must contains a hypothesis with
error at most $c\cdot OPT+\varepsilon$. Since we can directly compute the loss
of every element in $C_{\mathcal{A}}$ up to $\tau$ error in the SQ model
simply by querying the loss function, this gives the desired result in
$|C_{\mathcal{A}}|=(1/\tau)^{n(\varepsilon,\tau)}$ queries. ∎

We note that while our reduction in this model experiences exponential blowup
in the number of queries, this should really be thought of as corresponding to
a blow up in run-time instead of “sample complexity” in the standard sense
(which corresponds more closely to $\tau$).

##  Appendix F Fairness

Recent years have seen rising interest in an algorithmic property called
fairness. Informally, fairness tries to tackle the issue that “well-
performing” classifiers in the standard sense may actually be discriminatory
against certain individuals or subgroups. We will consider a form of fair
leaning introduced by Rothblum and Yona [61] called Probably Approximately
Correct and Fair (PACF) learning. Their definition is based off of a notion of
fairness that ensures that similar individuals are treated similarly with
respect to a fixed metric.

######  Definition F.1 (Metric Fairness).

Let $d:X\times X\to\mathbb{R}_{\geq 0}$ be a similarity measure on $X$ and $D$
a distribution over $X$. A classifier $h:X\to Y_{\text{out}}$ is called
$(\alpha,\gamma)$-fair with respect to $d$ and $D$ if h acts similarly on most
similar individuals:

$\Pr_{x,x^{\prime}\sim
D}[|h(x)-h(x^{\prime})|>d(x,x^{\prime})+\gamma]\leq\alpha.$

We note that the output space $Y_{\text{out}}$ may differ from the label space
$Y$ in general learning problems.

In fact, this definition only really makes sense when the output classifier
$h$ is allowed to be real-valued (as this allows for some flexibility in the
$|h(x)-h(x^{\prime})|$ term). As such, when considering settings such as
binary classification where $Y=\\{0,1\\}$ is discrete, Rothblum and Yona’s
[61] initial formalization considers returning probabilistic classifiers with
$Y_{\text{out}}=[0,1]$. Here $h(x)=y\in[0,1]$ is taken to be the probability
of the label being $1$. The error of a probabilistic classifier $h$ with
respect to any distribution $D$ over $X\times\\{0,1\\}$ is then given by its
expected $\ell_{1}$ distance:

$err_{D}(h)=\underset{(x,y)\sim D}{\mathbb{E}}[|h(x)-y|].$

For simplicity we’ll focus in this section on this same regime extended to the
distribution-family model.

In broad strokes, the goal of Fair PAC learning is to output a fair classifier
satisfying standard PAC guarantees. Practically this requires a few
modifications. First, since there may be no fair classifier satisfying these
guarantees, we will only require our output to be as good as the best fair
classifier. Second, we will actually allow some slack in the fairness
parameters, which Rothblum and Yona [61] show is a practical way to ensure
that fair learnability remains possible across a broad range of classes.

######  Definition F.2 (PACF-learning232323We note that our presentation of
this definition differs slightly from [61]. Their $(\alpha,\gamma)$-PACF-
learnability formally corresponds to
$(\alpha-\varepsilon_{\alpha},\gamma-\varepsilon_{\gamma})$-PACF-learnability
in our version. [61]).

We say $(\mathscr{D},X,H)$ is (agnostically) $(\alpha,\gamma)$-PACF-learnable
with respect to a similarity metric $d:X\times X\to Y$ if there exists an
algorithm $\mathcal{A}$ and function
$n=n(\varepsilon,\varepsilon_{\alpha},\varepsilon_{\gamma},\delta)$ such that
for all $\varepsilon,\varepsilon_{\alpha},\varepsilon_{\gamma},\delta>0,$ and
distributions $D$ over $X\times Y$ such that $D_{X}\in\mathscr{D}$,
$\mathcal{A}(S)$ satisfies the following guarantees with probability
$1-\delta$ over samples $S$ of size $n$:

  1. 1.

$\mathcal{A}(S)$ is accurate:

$\text{err}_{D,\ell}(\mathcal{A}(S))\leq OPT_{\alpha,\gamma}+\varepsilon$

  2. 2.

$\mathcal{A}(S)$ is
$(\alpha+\varepsilon_{\alpha},\gamma+\varepsilon_{\gamma})$-fair.

Here $OPT_{\alpha,\gamma}$ is the optimal error of any $(\alpha,\gamma)$-fair
classifier, that is:

$OPT_{a,b}\coloneqq\min_{h\in H^{d}_{D_{X},a,b}}\\{err_{D,\ell}(h)\\},$

and

$H^{d}_{D_{X},a,b}=\\{h\in H:h\text{ is $(a,b)$-fair with respect to $d$ and
$D_{X}$}\\}$

Realizable learnability is defined similarly, where the adversary is
constrained to picking distributions which have $0$ error with respect to some
$(\alpha,\gamma)$-fair classifier in $H$. We show that property generalization
holds for the PACF model.

######  Theorem F.3 (Agnostic $\to$ Realizable (PACF Setting)).

Let $(\mathscr{D},X,H)$ be any class that is realizably $(\alpha,\gamma)$-PACF
learnable with sample complexity
$n(\varepsilon,\varepsilon_{\alpha},\varepsilon_{\gamma},\delta)$. Then
$(\mathscr{D},X,H)$ is agnostically $(\alpha,\gamma)$-fair-PAC learnable in
only

$m_{U}(\varepsilon,\varepsilon_{\alpha},\varepsilon_{\gamma},\delta)\leq
n(\varepsilon/2,\varepsilon_{\alpha},\varepsilon_{\gamma},\delta/2)$

unlabeled samples, and

$m_{L}(\varepsilon,\varepsilon_{\alpha},\varepsilon_{\gamma},\delta)\leq
O\left(\frac{\log(\Pi_{H}(n(\varepsilon/2,\varepsilon_{\alpha},\varepsilon_{\gamma},\delta/2)))+\log(1/\delta)}{\varepsilon^{2}}\right)$

labeled samples.

###### Proof.

The key observation is that the definition of fairness depends only on the
classifier $h$ and the marginal distribution $D_{X}$. Let $h_{OPT}$ be the
hypothesis achieving the minimum error over $H_{D_{X},\alpha,\gamma}$. By the
above observation, with probability $1-\delta$ the hypothesis set $C(S_{U})$
returned by LearningToCover contains an
$(\alpha+\varepsilon_{\alpha},\gamma+\varepsilon_{\gamma})$-fair $h$
satisfying:

$\mathbb{E}_{x\sim D_{X}}[|h(x)-h_{OPT}(x)|]\leq\varepsilon/2.$

Since $\ell_{1}$ error is a metric (and therefore satisfies the triangle
inequality), we can use our argument for $c$-pseudometric loss functions from
Theorem 6.5 to argue that choosing the lowest empirical risk
$(\alpha+\varepsilon_{\alpha},\gamma+\varepsilon_{\gamma})$-fair classifier in
$C(S_{U})$ with respect to a sufficiently large labeled sample $S_{L}$ gives
the desired learner. ∎

With care, this result can be extended to a broader range of loss functions as
well as to other finitely-satisfiable properties covered in this work.

##  Appendix G Notions of Coverability

In this section we discuss the connection between non-uniform covers and
several previous notions of coverability used in various learning
applications. For simplicity, we’ll restrict our attention to covering with
respect to standard classification distance, that is given a distribution $D$
and hypotheses $h$ and $h^{\prime}$ over some instance space $X$:

$d_{D}(h,h^{\prime})=\Pr_{x\sim D}[h(x)\neq h^{\prime}(x)].$

To start, let’s recall the basic notion of an $\varepsilon$-cover specified to
this measure for simplicity.

######  Definition G.1 ($\varepsilon$-cover).

Let $X$ be an instance space, $Y$ a label space, and let $L_{X,Y}$ denote the
set of all labelings $c:X\to Y$. A set $C\subset L_{X,Y}$ is said to form an
$\varepsilon$-cover for $(D,X,H)$ if for every hypothesis $h\in H$, there
exists $c\in C$ such that

$d_{D}(c,h)\leq\varepsilon\,.$

$C$ is called proper if $C\subset H$.

Finite $\varepsilon$-covers are exceedingly useful in learning theory. As
discussed in Section 3, a common strategy in the literature is to use
unlabeled samples to construct an $\varepsilon$-cover with high probability
[19, 38, 18, 62]. This results in a distribution over potential covers we call
a uniform $(\varepsilon,\delta)$-cover.

######  Definition G.2 (Uniform $(\varepsilon,\delta)$-cover).

Let $X$ be an instance space, $Y$ a label space, and let $L_{X,Y}$ denote the
set of all labelings $c:X\to Y$. A distribution $D_{C}$ over the power set
$P(L_{X,Y})$ is said to form a uniform $(\varepsilon,\delta)$-cover for
$(D,X,H)$ if:

$\Pr_{C\sim D_{C}}[C\leavevmode\nobreak\ \text{is an $\varepsilon$-cover
for}\leavevmode\nobreak\ (D,X,H)]\geq 1-\delta.$

$D_{C}$ is called proper if its support lies entirely in $H$.

In this work, we introduce a weaker non-uniform variant of this notion where
each $h$ has an individual guarantee of being covered by the distribution, but
it is not necessarily the case that a sample will cover all $h\in H$
simultaneously.

######  Definition G.3 (Non-Uniform $(\varepsilon,\delta)$-cover).

Let $X$ be an instance space, $Y$ a label space, and let $L_{X,Y}$ denote the
set of all labelings $c:X\to Y$. A distribution $D_{C}$ over the power set
$P(L_{X,Y})$ is said to form a non-uniform $(\varepsilon,\delta)$-cover for
$(D,X,H)$ if for every fixed hypothesis $h\in H$,

$\Pr_{C\sim D_{C}}[C\leavevmode\nobreak\ \text{is an $\varepsilon$-cover
for}\leavevmode\nobreak\ (D,X,\\{h\\})]\geq 1-\delta.$

$D_{C}$ is called proper if its support lies entirely in $H$.

In the context of learning, we are usually interested not just in the
existence of these covers, but in the more challenging problem of constructing
them from a small number of unlabeled samples. In other words, given a class
$(\mathscr{D},X,H)$, we’d like to know how many unlabeled samples from an
adversarially chosen distribution $D\in\mathscr{D}$ are necessary to build a
uniform (or non-uniform) $(\varepsilon,\delta)$-cover for $(D,X,H)$. In
Section 6.3, we saw that the ability to construct a non-uniform
$(\varepsilon,\delta)$-cover from
$O\left(\frac{\log(1/\delta)}{\varepsilon}\right)$ samples was crucial to give
a semi-private learner with optimal public sample complexity. This improved
over recent work of Alon, Bassily, and Moran (ABM) [18], who showed that it is
possible to build a uniform $(\varepsilon,\delta)$-cover in
$O\left(\frac{\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}\right)$
samples.

It is interesting to ask whether non-uniformity is really necessary here, or
whether ABM’s analysis is simply sub-optimal. We’ll show that the former is
true, at least in the proper distribution-family setting: the
$\log(1/\varepsilon)$ gap between these models is necessary and uniform covers
cannot be used to build optimal semi-private learners.

######  Theorem G.4 (Separation of Uniform and Non-Uniform Covers).

There exists an instance space $X$, hypothesis class $H$, and family of
distributions $\mathscr{D}$ such that for any sufficiently small
$\varepsilon>0$, the following statements holds:

  1. 1.

Any algorithm which returns a finite proper uniform $(\varepsilon,1/3)$-cover
for $(\mathscr{D},X,H)$ requires at least
$\Omega(1/\varepsilon\cdot\log(1/\varepsilon))$ samples.

  2. 2.

There exists an algorithm which returns a finite proper non-uniform
$(\varepsilon,\delta)$-cover for $(\mathscr{D},X,H)$ in
$O(\log(1/\delta)/\varepsilon)$ samples.

###### Proof.

Let the instance space $X=\mathbb{N}$ and $H$ be the class of indicators along
with the all $0$’s function, that is
$H=\\{h_{i}:i\in\mathbb{N}\\}\cup\\{h_{0}\\}$ where
$h_{i}(x)=\mathbbm{1}\\{x=i\\}$ and $h_{0}$ is $0$ everywhere. We consider the
family of distribution $\mathscr{D}=\\{\mathscr{D}_{n,k}\\}_{n,k>0}$ given by
$k$-sets of $[n]$ where

$\mathscr{D}_{n,k}=\\{\mathrm{unif}(T):T\subset[n]\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ |T|=k\\},$

where $\mathrm{unif}(T)$ is a uniform distribution over $T$.

We start with the first claim, that building a bounded uniform
$(\varepsilon,1/2)$-cover needs at least
$\Omega(1/\varepsilon\log(1/\varepsilon))$ samples. More formally, for any
error parameter $\varepsilon>0$ and size bound
$m=m(\varepsilon)\in\mathbb{N}$, let $k=\lfloor 1/(2\epsilon)\rfloor$. We will
show that for any algorithm $\mathcal{A}$ on $k\log(k)$ samples that outputs
at most $m$ hypotheses, $\mathcal{A}$ must fail to output an
$\varepsilon$-cover with probability at least $1/2$.

Let $n\gg m,k$ be some natural number to be fixed later and consider the
family of distributions $\mathscr{D}_{n,k}$. By Yao’s minimax principle, it is
sufficient to show that there exists a distribution over the elements in
$\mathscr{D}_{n,k}$ such that any deterministic algorithm over $k\log(k)$
samples outputting a set of (at most) $m$ hypotheses fails to give a proper
$\varepsilon$-cover with probability $1/2$. We claim that taking the uniform
distribution over $\mathscr{D}_{n,k}$ suffices. To formalize this, it is
useful to observe the following claim.

######  Claim G.5.

Any subset of hypotheses $C\subset H$ of size $m$ can be a proper
$\varepsilon$-cover for $H$ under at most ${m\choose k}$ distributions in
$\mathscr{D}_{n,k}$.

Let’s prove the result under this assumption. The key observation is that by
standard lower bounds on the coupon collector problem, a sample $S$ of
$k\log(k)$ points from any $\mathrm{unif}(T)\in\mathscr{D}_{n,k}$ will not
include $\mathrm{unif}(T)$’s entire support with probability at least $1/2$.
With this in mind, assume that the input sample $S$ contains only
$\text{supp}(S)=j<k=\text{supp}(\mathrm{unif}(T))$ elements. As a result,
there are ${n-j\choose k-j}$ consistent distributions with $S$, and by G.5,
$\mathcal{A}(S)$ is a proper $\varepsilon$-cover for at most ${m\choose k}$ of
them. Since $S$ is equally likely to have been sampled from any of these
distributions, the probability that $\mathcal{A}(S)$ is a proper
$\varepsilon$-cover is at most:

$\Pr[\mathcal{A}\text{ fails given }\text{supp}(S)=j<k]\geq\frac{{n-j\choose
k-j}-{m\choose k}}{{n-j\choose k-j}}.$

Taking $n$ sufficiently larger than $m$ and $k$, we can make this probability
as close to $1$ as desired for any $0<j<k$. Finally, since samples of this
form occur with probability at least $1/2$, the algorithm fails with
probability at least $1/3$ as desired. It is left to prove G.5.

###### Proof of G.5.

Notice that for any distribution $\mathrm{unif}(T)\in\mathscr{D}_{n,k}$, any
$i\in T$ and any $j\neq i$, $d_{\mathrm{unif}(T)}(h_{i},h_{j})>2\varepsilon$.
Let $C$ be any proper $\varepsilon$-cover of $H$ under distribution
$\mathrm{unif}(T)$. Then, by the above argument, it must contain
$\\{h_{i}:i\in T\\}$. Since $|T|=k$, $C$ can be a proper $\varepsilon$-cover
of $H$ under at most $|C|\choose k$ distributions in $\mathscr{D}_{n,k}$. ∎

We now move to proving that a proper _non-uniform_
$(\varepsilon,\delta)$-cover can be built in only
$O(\log(1/\delta)/\varepsilon)$ samples. This follows from the fact that for
any $n\geq k$ and distribution $\mathrm{unif}(T)\in\mathscr{D}_{n,k}$, each
$i\in T$ is in the random sample $S$ with probability $1-\delta$. Since each
$h_{j}$ for $j\notin T$ is covered by $h_{0}$, outputting $\\{h_{i}:i\in
S\\}\cup\\{h_{0}\\}$ generates a proper non-uniform
$(\varepsilon,\delta)$-cover. ∎

The construction in Theorem G.4 can easily be modified to give a class with
the same gap which is not privately learnable (say by embedding a single copy
of a threshold over $[0,1]$). Since any such class requires at least
$\Omega(\frac{1}{\varepsilon})$ public samples to semi-privately learn by
Theorem 6.17,242424While Alon, Bassily, and Moran only state this result for
the distribution-free setting, it holds in the distribution-family model as
well. Theorem G.4 then provides a separation between using uniform and non-
uniform covers in semi-private learning: the former provably requires an extra
log factor, while the latter matches the lower bound exactly. Unfortunately,
our proof of this result only holds in the proper setting, as G.5 fails when
improper hypotheses are allowed. We conjecture that this is not an inherent
barrier: the separation should continue to hold in the improper case, albeit
with some different analysis.

We have now seen a weak separation between uniform and non-uniform covers, but
one might reasonably wonder whether a much stronger separation is possible. In
particular, all previous constructions of uniform covers use uniform
convergence, but there exist simple examples of learnable classes in the
distribution-family model that fail this property: do such classes provide an
example of objects which are non-uniformly coverable but not uniformly
coverable? Surprisingly, the answer is no! It turns out that an algorithm for
non-uniform covering can always be used to construct a uniform covering
without too much overhead. Moreover, we’ll see that the $\log(1/\varepsilon)$
gap is tight when $(X,H)$ has finite VC dimension.

To prove this, it will actually be useful to make a brief aside and introduce
another closely related notion of covering called fractional covers. These
objects are essentially a form of non-uniform covering which output a single
hypothesis instead of a set of them.

######  Definition G.6 (Fractional cover).

Let $X$ be an instance space, $Y$ a label space, and let $L_{X,Y}$ denote the
set of all labelings $c:X\to Y$. A distribution $D_{C}$ over $L_{X,Y}$ is said
to form a fractional $(\varepsilon,p)$-cover for a hypothesis class $H$ for
$(D,X,H)$ if for any fixed $h\in H$, a sample from $D_{C}$ covers $h$ with
probability $p$:

$\Pr_{c\sim D_{C}}[d(c,h)\leq\varepsilon]\geq p.$

Fractional covers are closely connected to non-uniform covers. In fact, one
can easily move between the two by sampling or subsampling.

######  Proposition G.7 (Non-uniform cover $\iff$ Fractional cover).

Let $(D,X,H)$ be any class, $C_{\text{frac}}$ a fractional
$(\varepsilon,p)$-cover, and $C_{\text{n-u}}$ a non-uniform
$(\varepsilon,1/2)$-cover. Then the following hold:

  1. 1.

Drawing $\log_{1/(1-p)}(1/\delta)$ samples from $C_{\text{frac}}$ gives a non-
uniform $(\varepsilon,\delta)$-cover.

  2. 2.

Choosing a random hypothesis from $C_{\text{n-u}}$ gives a fractional
$(\varepsilon,1/2|C|)$-cover.

###### Proof.

Both statements are essentially immediate from definition. For any fixed $h\in
H$, if we draw $M$ samples from $C_{\text{frac}}$, the probability we fail to
cover $h$ is $(1-p)^{M}$, so setting $M=\log_{1/(1-p)}(1/\delta)$ gives the
desired non-uniform cover. On the other hand, for any fixed $h\in H$, a sample
from $C\sim C_{\text{n-u}}$ contains $c$ $\varepsilon$-close to $h$ with
probability $1/2$. Outputting a uniformly random element of $C$ then gives an
element within $\varepsilon$ of $h$ with probability $1/2|C|$ as desired. ∎

It will also be useful to note a classical relation between covers and
fractional covers.

######  Lemma G.8.

If there exists a fractional $(\varepsilon,p)$-cover for $(D,X,H)$, then there
exists a $2\varepsilon$-cover of size $1/p$.

###### Proof.

This follows from classical packing-covering duality. The existence of a
fractional $(\varepsilon,p)$-cover implies there cannot exist a
$2\varepsilon$-packing of size greater than $1/p$ (that is, a set of more than
$1/p$ hypotheses in $H$ that are pairwise $2\varepsilon$-separated with
respect to $D$). By packing-covering duality, this implies the existence of a
$2\varepsilon$-cover of size $\lceil 1/p\rceil+1$. ∎

With this in hand, let’s show that uniform covers can be constructed for any
realizably learnable class, regardless of whether we have uniform convergence.

######  Theorem G.9 (Realizable learning $\to$ Uniform cover).

Let $(\mathscr{D},X,H)$ be realizably PAC-learnable with sample complexity
$n(\varepsilon,\delta)$. Then it is possible to construct a uniform
$(\varepsilon,\delta)$-cover for $(\mathscr{D},X,H)$ in
$n(\varepsilon/2,\delta^{\prime})$ samples where
$\delta^{\prime}=O\left(\frac{\delta}{\Pi_{H}(n(\varepsilon/2,1/2))}\right)$.

###### Proof.

We’ll start by proving a slightly more general fact. If for every
$D\in\mathscr{D}$, $(D,X,H)$ has a proper $(\varepsilon/2)$-cover $C_{D}$ of
size at most $C=C(\varepsilon/2)$, then it is possible to construct a uniform
$(\varepsilon,\delta)$-cover in $n(\varepsilon/2,\delta/C)$ samples. This is
essentially immediate from Lemma 5.2, which states that running
LearningToCover over a sample of size $n(\varepsilon/2,\delta/C)$ gives a non-
uniform $(\varepsilon/2,\delta/C)$-cover. Union bounding over $C_{D}$ then
gives that a sample from the non-uniform cover $(\varepsilon/2)$-covers
$C_{D}$ with probability at least $1-\delta$. Since $C_{D}$ is itself an
$(\varepsilon/2)$-cover, this implies that the entire class $H$
$\varepsilon$-covered by the sample with probability at least $1-\delta$ as
desired.

It remains to show that for every $D\in\mathscr{D}$, $(D,X,H)$ has a proper
$(\varepsilon/2)$-cover of size $O(\Pi_{H}(n(\varepsilon/2,1/2)))$. This
follows from combining Proposition G.7 and Lemma G.8. In particular, Lemma 5.2
implies that running LearningToCover over a sample of size
$n(\varepsilon/2,1/2)$ produces a non-uniform $(\varepsilon/2,1/2)$-cover of
size at most $\Pi_{H}(n(\varepsilon/2,1/2))$. Proposition G.7 states that
subsampling from this cover gives a fractional
$(\varepsilon/2,1/(2\Pi_{H}(n(\varepsilon/2,1/2))))$-cover, which in turn
implies the existence of a $(\varepsilon/2)$-cover of size
$O(\Pi_{H}(n(\varepsilon/2,1/2)))$ as desired. We note that this last argument
is similar to an observation made in Benedek and Itai’s [6] seminal work on
the distribution-dependent model. ∎

When $(X,H)$ has finite VC-dimension $d$, note that Theorem G.9 exactly
matches the lower bound exhibited in Theorem G.4 as the required number of
samples for a uniform $(\varepsilon,\delta)$-cover becomes:

$n(\varepsilon/2,\delta^{\prime})\leq
O\left(\frac{d\log(1/\varepsilon)+\log(1/\delta)}{\varepsilon}\right).$

This also matches the bound given by ABM [18] using uniform convergence.