(based on the exponential mechanism) on a fresh set of examples to identify such an accurate hypothesis from the short list.

Preliminaries {#sec:preliminaries}
=============

PAC Learning
------------

We use standard notation from statistical learning; see, e.g., [@Shalev14book]. Let $X$ be any “domain” set and consider the “label” set $Y=\{\pm 1\}$. A [*hypothesis*]{} is a function $h : X\to Y$, which we alternatively write as an element of $Y^X$. An [*example*]{} is a pair $(x, y) \in X\times Y$. A [*sample*]{} $S$ is a finite sequence of examples.

Let ${\mathcal{D}}$ be a distribution over $X \times \{\pm 1\}$. The population loss of a hypothesis $h : X \to \{\pm 1\}$ is defined by $${\operatorname{loss}}_{{\mathcal{D}}}(h) = \Pr_{(x, y) \sim {\mathcal{D}}}[h(x) \ne y].$$ Let $S=\bigl((x_i,y_i)\bigr)_{i=1}^n$ be a sample. The empirical loss of $h$ with respect to $S$ is defined by $${\operatorname{loss}}_{S}(h) = \frac{1}{n}\sum_{i=1}^n1[h(x_i)\neq y_i].$$

Let ${\mathcal{H}}\subseteq Y^X$ be a [*hypothesis class*]{}. A sample $S$ is said to be [*realizable by ${\mathcal{H}}$*]{} if there is $h\in H$ such that ${\operatorname{loss}}_S(h)=0$. A distribution ${\mathcal{D}}$ is said to be [*realizable by ${\mathcal{H}}$*]{} if there is $h\in H$ such that ${\operatorname{loss}}_{\mathcal{D}}(h)=0$. A [*learning algorithm*]{} $A$ is a (possibly randomized) mapping taking input samples to output hypotheses. We 