Metric Entropy Duality and the Sample Complexity of Outcome Indistinguishability

Traditionally, outcome indistinguishability and related notions such as multicalibration [Hébert-Johnson, Kim, Reingold, and Rothblum, 2018] have been viewed as providing stronger guarantees than $\ell_{1}$ error alone by allowing a predictor’s performance to be fine-tuned at the group level rather than just looking at the entire population. However, our obstruction-identification example from the previous section demonstrates how OI can also be viewed as a useful relaxation of the standard $\ell_{1}$ performance benchmark. By focusing on the important errors specified by the distinguisher class, outcome indistinguishability may allow us to achieve good performance with relatively small sample size. It is natural to ask: how much improvement in the sample size do we get from OI? This is the main focus of this paper—understanding the sample complexity of outcome indistinguishability.

It is one of the major objectives of learning theory to understand the sample complexity of various learning tasks and many influential characterizations of sample complexity have been discovered. The most notable example is the VC dimension for PAC learning [Vapnik and Chervonenkis, 1971, Blumer, Ehrenfeucht, Haussler, and Warmuth, 1989, Linial, Mansour, and Rivest, 1991]. In PAC learning [Valiant, 1984b, a], the learner receives examples $(x_{1},h^{*}(x_{1})),\ldots,(x_{n},h^{*}(x_{n}))$ where $x_{1},\ldots,x_{n}$ are drawn i.i.d. from a distribution $\mu$ over $X$, and aims to output a binary classifier (a.k.a. concept or hypothesis) $h:X\rightarrow\{0,1\}$ that is “close” to the target classifier $h^{*}:X\rightarrow\{0,1\}$. Here, the performance of $h$ is measured by the classification error $\Pr_{x\sim\mu}[h(x)\neq h^{*}(x)]$. In the realizable setting, the target classifier $h^{*}$ is assumed to be from a given class $\mathcal{H}$, whereas in the agnostic setting, there is no assumption on $h^{*}$ but the performance of $h$ is measured relative to the best classifier in the class $\mathcal{H}$. The main result of VC theory states that the sample complexity of PAC learning in both the realizable and the agnostic settings are characterized by the VC dimension [Vapnik and Chervonenkis, 1971] of the class $\mathcal{H}$, which has a simple combinatorial definition. The success of VC theory raises the possibility that the sample complexity of other learning tasks may also have natural characterizations. Below we discuss two such learning tasks that are most relevant to our work: predictor learning and distribution-specific learning.

The extension of PAC learning to predictor learning dates back to [Kearns and Schapire, 1994], in which predictors were termed probabilistic concepts. In predictor learning, binary classifiers are replaced by predictors whose predictions take values in $[0,1]$. Kearns and Schapire [1994] introduced the notion of fat-shattering dimension (see Section 2.4 for a precise definition) as a generalization of VC dimension to predictor classes and showed a lower bound on the sample complexity of learning a predictor class by its fat-shattering dimension. Alon, Ben-David, Cesa-Bianchi, and Haussler [1997] and Bartlett, Long, and Williamson [1996] complemented the result with corresponding upper bounds and concluded that a predictor class is learnable from finitely many examples if and only if it has finite fat-shattering dimension. Quantitatively, these papers showed that the sample complexity of learning a predictor in a class ${\mathcal{P}}$ within $\ell_{1}$ error $\varepsilon$ is characterized by

$$(1/\varepsilon)^{O(1)}\mathsf{fat}_{{\mathcal{P}}}\big{(}\varepsilon^{\Theta(1)}\big{)},$$

assuming we want the success probability to be at least a constant, say $9/10$. Moreover, Bartlett et al. [1996] extended the characterization to the agnostic setting, where the objective is the mean absolute error between the learned prediction and the actual outcome. Later, the sample complexity bounds and the related uniform convergence results from Alon et al. [1997] and Bartlett et al. [1996] were improved by Bartlett and Long [1995], Bartlett and Long [1998], and Li, Long, and Srinivasan [2001].

Another natural extension of PAC learning is distribution-specific learning. In both PAC learning and predictor learning discussed above, performance of the learner is evaluated based on the worst-case distribution $\mu$. These settings are referred to as distribution-free due to their lack of dependence on a particular input distribution. Since the distribution is usually not the worst-case in practice, distribution-specific learning focuses on the performance of the learner on a given distribution $\mu$. In this setting, the sample complexity of learning a binary classifier in class $\mathcal{H}$ to achieve a classification error below $\varepsilon$ is characterized by

$$(1/\varepsilon)^{O(1)}\log N_{\mu}(\mathcal{H},\Theta(\varepsilon))$$

(1)

using the metric entropy, i.e., the logarithm of the covering number $N_{\mu}$ of $\mathcal{H}$ w.r.t. the classification error (as a metric), which indeed depends on the specific distribution $\mu$ [Benedek and Itai, 1991].

To compare OI with these previous clasification-error/$\ell_{1}$-error-based notions of learning in terms of sample complexity, we need a characterization of the sample complexity of OI using similar quantities such as the fat-shattering dimension or the metric entropy. While it is tempting to hope that we might directly apply such notions, OI introduces additional subtlety in that we must consider how the expressiveness of the predictor class ${\mathcal{P}}$ and the class of distinguishers ${\mathcal{D}}$ interact to fully understand the sample complexity requirements. This is in contrast to standard settings where characterizing the expressiveness of the concept class via VC dimension or related notions is sufficient.

We show a simple example where it is indeed important to consider the interplay between ${\mathcal{P}}$ and ${\mathcal{D}}$ rather than just considering their contributions independently: Partition the set of inputs $X$ into two equal-sized sets, $X_{1}$ and $X_{2}$. We consider a class of predictors that are maximally expressive on $X_{2}$ and constant on $X_{1}$: Let ${\mathcal{P}}=\{p:X\rightarrow[0,1]|p(x)=0,\forall x\in X_{1}\}$. Similarly, we can define a distinguisher class that are maximally inquisitive on one set and ignores the other set but depending on which set is ignored we will get dramatically different complexity: Define two potential distinguisher classes: ${\mathcal{D}}_{1}=\{d:X\times\{0,1\}\rightarrow\{\textnormal{ACCEPT},\textnormal{REJECT}\}|d(x,b)=\textnormal{REJECT},\forall x\in X_{1},b\in\{0,1\}\}$, ${\mathcal{D}}_{2}=\{d:X\times\{0,1\}\rightarrow\{\textnormal{ACCEPT},\textnormal{REJECT}\}|d(x,b)=\textnormal{REJECT},\forall x\in X_{2},b\in\{0,1\}\}$. ${\mathcal{D}}_{1}$ and ${\mathcal{D}}_{2}$ are symmetric and thus identical in any independent measure of complexity. Nevertheless, it is easy to see that while achieving $\varepsilon$-OI on ${\mathcal{P}}$ with respect to ${\mathcal{D}}_{1}$ is equivalent to learning a predictor from ${\mathcal{P}}$ with $\varepsilon$ $\ell_{1}$ error on the set $X_{2}$, learning an $\varepsilon$-OI predictor from ${\mathcal{P}}$ with respect to ${\mathcal{D}}_{2}$ is trivial as ${\mathcal{P}}$ is constant on all individuals that ${\mathcal{D}}_{2}$ can distinguish between, and therefore any $p\in{\mathcal{P}}$ will satisfy perfect OI with respect to ${\mathcal{D}}_{2}$. This example demonstrates the need for a more subtle variation of existing complexity notions in order to tightly characterize the sample complexity of OI.

Prior to our work, Dwork et al. [2021] showed that $O(\varepsilon^{-4}\log(|{\mathcal{D}}|/\varepsilon\delta))$ examples are sufficient for achieving an advantage below $\varepsilon$ over a distinguisher class ${\mathcal{D}}$ with probability at least $1-\delta$ in the distribution-free setting. In this work, we refine the $\log|{\mathcal{D}}|$ dependence on ${\mathcal{D}}$ to its fat-shattering dimension with a matching lower bound (Section 5). In addition, we characterize the sample complexity of OI in the distribution-specific setting with greater generality for every given predictor class ${\mathcal{P}}$, placing OI in the same setting as the classification-error/$\ell_{1}$-error-based notions of learning with improved sample complexity due to a well-tuned objective based on the distinguisher class ${\mathcal{D}}$. The interplay between the distinguisher class ${\mathcal{D}}$ and the predictor class ${\mathcal{P}}$ connects our sample complexity characterizations to the intriguing metric entropy duality conjecture in convex geometry, which we discuss more in Section 1.2 below.

Before we describe our sample complexity characterizations for OI, we would like to discuss the ideas behind the metric-entropy-based sample complexity characterization (1) for distribution-specific learning by Benedek and Itai [1991]. Our characterizations for distribution-specific OI are based on similar ideas, but in a more subtle and arguably surprising way, making an intriguing connection to the metric entropy duality conjecture, a long-standing conjecture in convex geometry.

The idea behind the sample complexity upper bound in (1) is to reduce the size of the classifier class $\mathcal{H}$ by taking an $\varepsilon$-covering of it. Consider the space of all binary classifiers endowed with the “classification error metric” $\eta(h_{1},h_{2})=\Pr_{x\sim\mu}[h_{1}(x)\neq h_{2}(x)]$. If two classifiers $h_{1}$ and $h_{2}$ are close w.r.t. this metric, choosing $h_{1}$ and $h_{2}$ would result in roughly equal classification errors w.r.t. the target predictor. This gives a natural procedure for simplifying the classifier class and consequently controlling the sample complexity: we can replace $\mathcal{H}$ by an $\varepsilon$-covering $\mathcal{H}^{\prime}$ of it with only minor loss in its expressivity. Here, an $\varepsilon$-covering is a subset $\mathcal{H}^{\prime}\subseteq\mathcal{H}$ such that every $h\in\mathcal{H}$ can find a close companion $h^{\prime}\in\mathcal{H}^{\prime}$ such that $\eta(h,h^{\prime})\leq\varepsilon$. As the size of $\mathcal{H}^{\prime}$ can be bounded by the covering number $N_{\mu}(\mathcal{H},\varepsilon)$, we can use a relatively small amount of examples to accurately estimate the classification error of every classifier in $\mathcal{H}^{\prime}$. This naturally leads to the empirical risk minimization (ERM) algorithm used in [Benedek and Itai, 1991].

To extend the ERM algorithm to outcome indistinguishability, a natural idea is to define the metric $\eta(p_{1},p_{2})$ between two predictors $p_{1}$ and $p_{2}$ to be the maximum distinguishing advantage for $p_{1}$ and $p_{2}$ w.r.t. the distinguisher class ${\mathcal{D}}$, and compute an $\varepsilon$-covering ${\mathcal{P}}^{\prime}$ of the predictor class ${\mathcal{P}}$. However, this direct extension (Algorithm 1) of the ERM algorithm to OI does not give us the right sample complexity upper bound (we show this formally in Appendix A, especially in Lemma 33). This failure is partly because the acceptance probabilities of the distinguishers in ${\mathcal{D}}$ are not all preserved on a small sample. Indeed, learning a predictor $p$ with MDA below $\varepsilon$ w.r.t. to the target predictor $p^{*}$ necessarily requires estimating the acceptance probability of every distinguisher in ${\mathcal{D}}$ on $p^{*}$ within error $\varepsilon$ (the estimates are simply the acceptance probabilities on $p$).

To meet the need of estimating the acceptance probabilities of the distinguishers in ${\mathcal{D}}$, we use a new algorithm (Algorithm 2) where we compute a covering of ${\mathcal{D}}$ w.r.t. a metric defined by the predictor class ${\mathcal{P}}$, i.e., we flip the roles of ${\mathcal{P}}$ and ${\mathcal{D}}$ in the covering. Using this new algorithm, we get a sample complexity upper bound as a function of the metric entropy $\log N_{\mu,{\mathcal{P}}}({\mathcal{D}},\varepsilon)$ of ${\mathcal{D}}$ w.r.t. ${\mathcal{P}}$, but the sample complexity lower bound we get by extending the arguments from [Benedek and Itai, 1991] is still a function of the metric entropy $\log N_{\mu,{\mathcal{D}}}({\mathcal{P}},\varepsilon)$ of ${\mathcal{P}}$ w.r.t. ${\mathcal{D}}$. How do we make the upper and lower bounds match?

Our idea is to first transform distinguishers into the same inner product space as the predictors, and then interpret ${\mathcal{D}}$ and ${\mathcal{P}}$ as two abstract vector sets ${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{2}$ in the same inner product space that can exchange roles freely. Specifically, combining our upper and lower bounds, we know that the lower bound based on $\log N_{\mu,{\mathcal{D}}}({\mathcal{P}},\varepsilon)$ never exceeds the upper bound based on $\log N_{\mu,{\mathcal{P}}}({\mathcal{D}},\varepsilon)$. If we set ${\mathcal{F}}_{1}={\mathcal{P}}$ and ${\mathcal{F}}_{2}={\mathcal{D}}$, a more precise version of what we get is

$$\log N_{\mu,{\mathcal{F}}_{2}}({\mathcal{F}}_{1},\varepsilon)\leq O\Big{(}\varepsilon^{-2}\Big{(}1+\log N_{\mu,{\mathcal{F}}_{2}}({\mathcal{F}}_{1},\Omega(\varepsilon))\Big{)}\Big{)}.$$

(2)

If ${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{2}$ are two arbitrary abstract sets of vectors, we can inversely set ${\mathcal{F}}_{1}={\mathcal{D}}$ and ${\mathcal{F}}_{2}={\mathcal{P}}$ in the inequality above and get

$$\log N_{\mu,{\mathcal{P}}}({\mathcal{D}},\varepsilon)\leq O\Big{(}\varepsilon^{-2}\Big{(}1+\log N_{\mu,{\mathcal{D}}}({\mathcal{P}},\Omega(\varepsilon))\Big{)}\Big{)}.$$

This inequality is exactly what we need to flip back the roles of ${\mathcal{P}}$ and ${\mathcal{D}}$ and make our upper bound match our lower bound.

The key inequality (2) that helps match our upper and lower bounds comes from combining the bounds themselves. Moreover, this inequality makes an intriguing connection to the long-standing metric entropy duality conjecture in convex geometry, which conjectures that (2) holds without the $\varepsilon^{-2}$ factor, but with the additional assumption that ${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{2}$ are convex and symmetric around the origin. Without this additional assumption, we show that the quadratic dependence on $1/\varepsilon$ in (2) is nearly tight (Lemma 14).

The metric entropy duality conjecture (formally stated in Conjecture 12) was first proposed by Pietsch [1972]. While the conjecture remains open, many weaker versions of it have been proved [e.g. Bourgain, Pajor, Szarek, and Tomczak-Jaegermann, 1989]. Most notably, the conjecture was proved by Artstein, Milman, and Szarek [2004b] in the special case where one of the two convex sets is an ellipsoid. This result was further strengthened by Artstein, Milman, Szarek, and Tomczak-Jaegermann [2004a]. Milman [2007] proved a weaker form of the conjecture with the constant factors replaced by dimension dependent quantities.

Outcome indistinguishability was originally proposed as a strong fairness and accuracy criterion, potentially requiring large sample sizes to achieve. In this work, we view OI differently as a meaningful notion when we have insufficient data for $\ell_{1}$-error-based learning. For this reason, we focus on no-access OI, the simplest form of OI introduced by Dwork et al. [2021]. For no-access OI, we show that (randomized) distinguishers can be converted to vectors in the same inner product space as the predictors (Section 2.1.2), connecting the MDA objective to the multiaccuracy objective used by Kim et al. [2019]. This allows us to understand predictor classes ${\mathcal{P}}$ and distinguisher classes ${\mathcal{D}}$ using geometric notions such as the dual Minkowski norms $\|\cdot\|_{\mu,{\mathcal{P}}},\|\cdot\|_{\mu,{\mathcal{D}}}$ and the covering numbers $N_{\mu,{\mathcal{P}}}(\cdot,\cdot),N_{\mu,{\mathcal{D}}}(\cdot,\cdot)$ defined by these norms (see Section 2.2).

In the distribution-specific setting, we consider realizable OI where the target predictor lies in an arbitrary given predictor class ${\mathcal{P}}$. Setting the failure probability bound $\delta$ in Theorem 13 to be a constant, say $1/10$, for every predictor class ${\mathcal{P}}$, every distinguisher class ${\mathcal{D}}$, every data distribution $\mu$ and every MDA bound $\varepsilon$, we characterize the sample complexity of distribution-specific realizable OI both as

$$(1/\varepsilon)^{O(1)}\log N_{\mu,{\mathcal{D}}}({\mathcal{P}},\Theta(\varepsilon))$$

(3)

and as

$$(1/\varepsilon)^{O(1)}\log N_{\mu,{\mathcal{P}}}({\mathcal{D}},\Theta(\varepsilon)).$$

(4)

Our sample complexity characterizations (3) and (4) highlight an intriguing connection between learning theory and the metric entropy duality conjecture (Conjecture 12) first proposed by Pietsch [1972], which conjectures that

$$\log N_{\mu,{\mathcal{F}}_{1}}({\mathcal{F}}_{2},\varepsilon)\leq O(\log N_{\mu,{\mathcal{F}}_{2}}({\mathcal{F}}_{1},\Omega(\varepsilon)))$$

whenever two function classes ${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{2}$ are convex and symmetric around the origin. Our sample complexity characterizations imply a variant version of metric entropy duality (Theorem 11) where ${\mathcal{F}}_{1}$ and ${\mathcal{F}}_{2}$ are not required to be convex and symmetric, which we show is nearly tight (Lemma 14).

In the distribution-free setting, we focus on the case where ${\mathcal{P}}$ contains all possible predictors, which is the setting considered by Dwork et al. [2021]. Setting $\delta=1/10$ in Theorem 15, we show that the sample complexity of distribution-free OI in this setting is characterized by

$$(1/\varepsilon)^{O(1)}\mathsf{fat}_{{\mathcal{D}}}(\Theta(\varepsilon)).$$

This characterization extends to multicalibration with some modifications (see Remark 21 and Remark 24). Our result refines the $\log|{\mathcal{D}}|$ in the sample complexity upper bounds by Dwork et al. [2021] (for OI) and by Hébert-Johnson et al. [2018] (for multicalibration) to the fat-shattering dimension of ${\mathcal{D}}$ with a matching lower bound.

In addition, we show that the sample complexity of OI in the agnostic setting behaves very differently from the realizable setting. This is in contrast to many common learning settings where the sample complexities of realizable and agnostic learning usually behave similarly (a recent independent work by Hopkins et al. [2021] gives a unified explanation for this phenomenon). In both the distribution-free and the distribution-specific settings, we show that the sample complexity of agnostic OI can increase when we remove some distinguishers from ${\mathcal{D}}$, and it can become arbitrarily large even when the realizable sample complexity is bounded by a constant (Section 6.2). This also suggests that OI can have larger sample complexity compared to $\ell_{1}$-error based learning in the agnostic setting. This is because in the agnostic setting, the performance of the learned predictor is measured relative to the best predictor in the class ${\mathcal{P}}$, which can have a much better performance when measured using the selected objective of OI than using the $\ell_{1}$ error. On the other hand, when the target predictor $p^{*}$ belongs to the symmetric convex hull of the predictor class ${\mathcal{P}}$, we show that the sample complexity in the distribution-specific agnostic setting has the same characterizations as in the realizable setting (Lemma 25).

The notion of outcome indistinguishability originated from the growing research of algorithmic fairness. Specifically, outcome indistinguishability can be treated as a generalization of multiaccuracy and multicalibration introduced by Hébert-Johnson, Kim, Reingold, and Rothblum [2018] and Kim, Ghorbani, and Zou [2019], in which the goal is to ensure that the learned predictor is accurate in expectation or calibrated conditioned on every subpopulation in a subpopulation class $\mathcal{C}$. Roughly speaking, the subpopulation class $\mathcal{C}$ in multiaccuracy and multicalibration plays a similar role as the distinguisher class ${\mathcal{D}}$ in outcome indistinguishability, and this connection has been discussed more extensively in [Dwork et al., 2021, Section 4]. Beyond fairness, multicalibration and OI also provide strong accuracy guarantees [see e.g. Rothblum and Yona, 2021, Blum and Lykouris, 2020, Zhao, Kim, Sahoo, Ma, and Ermon, 2021, Gopalan, Kalai, Reingold, Sharan, and Wieder, 2022, Kim, Kern, Goldwasser, Kreuter, and Reingold, 2022, Burhanpurkar, Deng, Dwork, and Zhang, 2021]. For a general predictor class ${\mathcal{P}}$ and a subpopulation class $\mathcal{C}$, Shabat, Cohen, and Mansour [2020] showed sample complexity upper bounds of uniform convergence for multicalibration based on the maximum of suitable complexity measures of $\mathcal{C}$ and ${\mathcal{P}}$. They complemented this result with a lower bound which does not grow with $\mathcal{C}$ and ${\mathcal{P}}$. In comparison, we focus on the weaker no-access OI setting where the sample complexity can be much smaller, and we provide matching upper and lower bounds in terms of the dependence on ${\mathcal{D}}$ and ${\mathcal{P}}$.

The remainder of this paper is structured as follows. In Section 2, we formally define OI and related notions. We give lower and upper bounds for the sample complexity of distribution-specific realizable OI in Section 3, and turn these bounds into a characterization in Section 4 via metric entropy duality. We characterize the sample complexity of distribution-free OI in Section 5. Finally, in Section 6 we show a strong separation between the sample complexities of realizable and agnostic OI in both the distribution-free and distribution-specific settings.

Outcome indistinguishability is a theoretical framework introduced by Dwork et al. [2021] that aims to guarantee that the outcomes produced by some learned predictor $p:X\rightarrow[0,1]$ are indistinguishable to a predetermined class of distinguishers ${\mathcal{D}}$ from outcomes sampled from the true probabilities for each individual defined by $p^{*}:X\rightarrow[0,1]$.

The distinguishing task in outcome indistinguishability consists of drawing an individual $x\in X$ according to some population distribution $\mu\in\Delta_{X}$ and then presenting the distinguisher with an outcome/individual pair $(x,o)$ where $o$ is either sampled according to the true predictor $p^{*}$ from the Bernoulli distribution $\mathrm{Ber}(p^{*}(x))$, or sampled according to the learned predictor $p$ from $\mathrm{Ber}(p(x))$. Taking a pair $(x,o)\in X\times\{0,1\}$, a distinguisher $d$ outputs $d(x,o)=\textnormal{ACCEPT}$ or $d(x,o)=\textnormal{REJECT}$. We allow distinguishers to be randomized.

Given a predictor $p$ and a distribution $\mu$ over $X$, we define $\mu_{p}$ to be the distribution of pairs $(x,o)\in X\times\{0,1\}$ drawn using the process described above such that $x\sim\mu$ and $o\sim\mathrm{Ber}(p(x))$. With this notation in hand, we can now provide a formal definition of outcome indistinguishability:

We refer to the left-hand-side of (5) as the distinguishing advantage (or simply advantage) of the distinguisher $d$, denoted $\mathrm{adv}_{\mu,d}(p,p^{*})$. Given a class ${\mathcal{D}}$ of distinguishers, we use $\mathrm{adv}_{\mu,{\mathcal{D}}}(p,p^{*})$ to denote the supremum $\sup_{d\in{\mathcal{D}}}\mathrm{adv}_{\mu,d}(p,p^{*})$. According to Definition 1, a learned predictor $p$ satisfies $({\mathcal{D}},\varepsilon)$-OI if and only if $\mathrm{adv}_{\mu,{\mathcal{D}}}(p,p^{*})\leq\varepsilon$.

There are many different extensions of OI to settings in which the power of distinguishers is extended to allow access to additional information about the learned predictor $p$ or access to more than one individual/outcome pair. We will be focusing on this most basic case in which the distinguisher only has access to a single pair $(x,o)$ and has no additional access to the learned predictor $p$ (hence the name No-Access OI).

The set $\mathbb{R}^{X}$ of all real-valued functions on $X$ is naturally a linear space: for all $f_{1},f_{2}\in\mathbb{R}^{X}$, we define $f_{1}+f_{2}=g\in\mathbb{R}^{X}$ where $g(x)=f_{1}(x)+f_{2}(x)$ for all $x\in X$, and for $f\in\mathbb{R}^{X}$ and $r\in\mathbb{R}$, we define $rf=h\in\mathbb{R}^{X}$ where $h(x)=rf(x)$ for all $x\in X$.

For any function class ${\mathcal{F}}\subseteq\mathbb{R}^{X}$ and a real number $r$, we use $r{\mathcal{F}}$ to denote $\{rf:f\in{\mathcal{F}}\}$ and use $-{\mathcal{F}}$ to denote $(-1){\mathcal{F}}$. For any two function classes ${\mathcal{F}}_{1},{\mathcal{F}}_{2}\subseteq\mathbb{R}^{X}$, we define

	$\displaystyle{\mathcal{F}}_{1}+{\mathcal{F}}_{2}$	$\displaystyle=\{f_{1}+f_{2}:f_{1}\in{\mathcal{F}}_{1},f_{2}\in{\mathcal{F}}_{2}\},\textnormal{and}$
	$\displaystyle{\mathcal{F}}_{1}-{\mathcal{F}}_{2}$	$\displaystyle=\{f_{1}-f_{2}:f_{1}\in{\mathcal{F}}_{1},f_{2}\in{\mathcal{F}}_{2}\}.$

For any non-empty function class ${\mathcal{F}}\subseteq\mathbb{R}^{X}$, we say a function $f\in\mathbb{R}^{X}$ is in the convex hull of ${\mathcal{F}}$ if there exist $n\in\mathbb{Z}_{>0}$, $f_{1},\ldots,f_{n}\in{\mathcal{F}}$ and $r_{1},\ldots,r_{n}\in\mathbb{R}_{\geq 0}$ such that $r_{1}+\cdots+r_{n}=1$ and $f=r_{1}f_{1}+\cdots+r_{n}f_{n}$. We use $\bar{}{\mathcal{F}}$ to denote the symmetric convex hull of ${\mathcal{F}}$ consisting of all functions in the convex hull of ${\mathcal{F}}\cup(-{\mathcal{F}})$. When ${\mathcal{F}}$ is empty, we define $\bar{}{\mathcal{F}}$ to be the class consisting of only the all zeros function.

We say a function $f\in\mathbb{R}^{X}$ is bounded if there exists $M>0$ such that $|f(x)|\leq M$ for all $x\in X$. We say a function class ${\mathcal{F}}\subseteq\mathbb{R}^{X}$ is bounded if there exists $M>0$ such that $|f(x)|\leq M$ for all $f\in{\mathcal{F}}$ and $x\in X$.

For two bounded functions $f_{1},f_{2}\in\mathbb{R}^{X}$, we define their inner product w.r.t. distribution $\mu$ as

$$\langle f_{1},f_{2}\rangle_{\mu}=\operatorname{\mathbb{E}}_{x\sim\mu}[f_{1}(x)f_{2}(x)].$$

Although we call the above quantity an inner product for simplicity, it may not be positive definite ($\langle f,f\rangle_{\mu}=0$ need not imply $f(x)=0$ for all $x\in X$). For a non-empty bounded function class ${\mathcal{F}}_{1}\subseteq\mathbb{R}^{X}$ and a bounded function $f\in\mathbb{R}^{X}$, we define the dual Minkowski norm of $f$ w.r.t. ${\mathcal{F}}_{1}$ to be

$$\|f\|_{\mu,{\mathcal{F}}_{1}}=\sup_{f_{1}\in{\mathcal{F}}_{1}}|\langle f,f_{1}\rangle_{\mu}|.$$

If ${\mathcal{F}}_{1}$ is empty, we define $\|f\|_{\mu,{\mathcal{F}}_{1}}=0$. The norm $\|\cdot\|_{\mu,{\mathcal{F}}_{1}}$ is technically only a semi-norm as it may not be positive definite, but whenever it is positive definite, it is the dual norm of the Minkowski norm induced by (the closure of) $\bar{}{\mathcal{F}}_{1}$ for finite $X$ [see e.g. Nikolov et al., 2013, Section 2.1].

For a non-empty bounded function class ${\mathcal{F}}_{2}\subseteq\mathbb{R}^{X}$ and $\varepsilon\geq 0$, we say a subset ${\mathcal{F}}_{2}^{\prime}\subseteq{\mathcal{F}}_{2}$ is an $\varepsilon$-covering of ${\mathcal{F}}_{2}$ w.r.t. the norm $\|\cdot\|_{\mu,{\mathcal{F}}_{1}}$ if for every $f_{2}\in{\mathcal{F}}_{2}$, there exists $f_{2}^{\prime}\in{\mathcal{F}}_{2}^{\prime}$ such that $\|f_{2}-f_{2}^{\prime}\|_{\mu,{\mathcal{F}}_{1}}\leq\varepsilon$. We define the covering number $N_{\mu,{\mathcal{F}}_{1}}({\mathcal{F}}_{2},\varepsilon)$ of ${\mathcal{F}}_{2}$ w.r.t. the norm $\|\cdot\|_{\mu,{\mathcal{F}}_{1}}$ to be the minimum size of such an $\varepsilon$-covering of ${\mathcal{F}}_{2}^{\prime}$. We refer to the logarithm of the covering number, $\log N_{\mu,{\mathcal{F}}_{1}}({\mathcal{F}}_{2},\varepsilon)$, as the metric entropy.

The following basic facts about the covering number are very useful:

The inner products and norms provide convenient ways for describing distinguishing advantages. Given a distinguisher $d\in[-1,1]^{X}$ and two predictors $p_{1},p_{2}\in[0,1]^{X}$, Lemma 5 tells us that

	$\displaystyle\mathrm{adv}_{\mu,d}(p_{1},p_{2})=|\langle d,p_{1}-p_{2}\rangle_{\mu}|,\quad\textnormal{and thus}$
	$\displaystyle\mathrm{adv}_{\mu,{\mathcal{D}}}(p_{1},p_{2})=\|p_{1}-p_{2}\|_{\mu,{\mathcal{D}}}\quad\textnormal{for all distinguisher classes}\ {\mathcal{D}}\subseteq[-1,1]^{X}.$

Using these representations for advantages, we can prove the following lemma relating advantages to the $\ell_{1}$ error:

Given a function class ${\mathcal{F}}\subseteq\mathbb{R}^{X}$ and $\gamma\geq 0$, we say $x_{1},\ldots,x_{n}\in X$ are $\gamma$-fat shattered by ${\mathcal{F}}$ w.r.t. $r_{1},\ldots,r_{n}\in\mathbb{R}$ if for every $(b_{1},\ldots,b_{n})\in\{-1,1\}^{n}$, there exists $f\in{\mathcal{F}}$ such that

$$b_{i}(f(x_{i})-r_{i})\geq\gamma\quad\textnormal{for all}\ i\in\{1,\ldots,n\}.$$

We sometimes omit the mention of $r_{1},\ldots,r_{n}$ and say $x_{1},\ldots,x_{n}$ is $\gamma$-fat shattered by ${\mathcal{F}}$ if such $r_{1},\ldots,r_{n}$ exist. The $\gamma$-fat-shattering dimension of ${\mathcal{F}}$ introduced first by Kearns and Schapire [1994] is defined to be

$$\mathsf{fat}_{\mathcal{F}}(\gamma)=\sup\{n\in\mathbb{Z}_{\geq 0}:\textnormal{there exist $x_{1},\ldots,x_{n}\in X$ that are $\gamma$-fat shattered by ${\mathcal{F}}$}\}.$$