We study closure properties for learnability of binary-labeled hypothesis classes in two related settings: online learning and differentially private PAC learning.

Closure Properties for Online Learning. Let H be a class of experts that can be online learned with vanishing regret. That is, there exists an algorithm A such that given any sequence of T prediction tasks, the number of false predictions made by A is larger by at most R(T) = o(T) than the number of false predictions made by the best expert in H.

Consider a scenario where the sequence of tasks is such that every single expert in H predicts poorly on it, however there is a small unknown set of experts that can predict well by collaborating. More formally, there is an aggregation rule such that the combined expert exhibits accurate predictions on a significant majority of the tasks. For example, a possible aggregation rule G could be the majority-vote of the k experts. Since we assume that the identities of the k experts are not known, it is natural to consider the class which consists of all possible G-aggregations of k experts from H. We study the following question:

Question 1.1. Can the optimal regret with respect to be bounded in terms of that of H?

The Littlestone dimension is a combinatorial parameter that determines online learnability [Littlestone, 1987, Ben-David et al., 2009]. In particular, H is online learnable if and only if it has a finite Littlestone dimension , and the best possible regret R(T) for online learning H satisfies

Furthermore, if it is known that if one of the experts never errs (a.k.a the realizable setting), then the optimal regret is exactly (The regret is called mistake-bound in this context.)

Thus, the above question boils down to asking whether the Littlestone dimension of is bounded by a function of the Littlestone dimension of H. One of the two main results in this work provides an affirmative answer to this question (Theorem 2.1).

We next discuss a variant of this question in the setting of Differentially Private (DP) learning. The two settings of online and DP-learning are intimately related (see, e.g., Bun et al. [2020], Abernethy et al. [2017], Joseph et al. [2019], Gonen et al. [2019]). In particular, both online learning and DP-learning are characterized by the finiteness of the Littlestone dimension [Littlestone, 1987, Ben-David et al., 2009, Bun et al., 2015, Alon et al., 2019, Bun et al., 2020].

Closure Properties for Differentially Private Learning. Imagine the following medical scenario: consider a family H of viruses for which there is an algorithm A that can learn to diagnose any specific virus given enough labeled medical data. Further assume that A has the desired property of being differentially private learning algorithm as defined by [Kasiviswanathan et al., 2011]; that is, it is a PAC learning algorithm in which the privacy of every patient whose data is used during training is guarded in the formal sense of differential privacy [Dwork et al., 2006b].

Assume that an outbreak of a deadly disease has occurred in several locations all over the world and that it is known that is caused by some relatively small, yet unknown group of viruses from H. That is, our prior information is that there are unknown viruses for a relatively small k such that for some rule G. For example, G could be the OR function in which case and only if the patient is infected with at least one of the viruses

It would be highly beneficial if one could use the algorithm A to diagnose in an automated fashion. Moreover, doing it in a private manner could encourage health institutions in the different locations to contribute their patients’ data. This inspires the following question:

Question 1.2. Can one use the algorithm A to privately learn to diagnose ? How does the sample complexity of this learning task scale as a function of G?

Differential Privacy, Online Learning, and the Littlestone Dimension. Question 1.2 and Question 1.1 are equivalent in the sense that both online learning and DP-learning are characterized by the finiteness of the Littlestone dimension [Littlestone, 1987, Ben-David et al., 2009, Bun et al., 2015, Alon et al., 2019, Bun et al., 2020].

Note however that unlike the bounds relating the Littlestone dimension to online learning, which are tight up to logarithmic factors (see (1)), the bounds relating the Littlestone dimension and DP-learning are very far from each other; specifically, if d denotes the Littlestone dimension of H then the lower bound on the sample complexity of privately learning H scales with [Bun et al., 2015, Alon et al., 2019], while the best known2 upper bound scales with exp(d) [Bun et al., 2020].

Thus, while our solution to Question 1.1 yields an affirmative answer to Question 1.2, the implied quantitative bounds are far from being realistically satisfying. Specifically, every finite H is learnable with privacy using O(log |H|) samples [Kasiviswanathan et al., 2011], and so if H is finite and not too large, the bounds implied by the Littlestone dimension are not meaningful. We therefore focus on deriving effective bounds for private learning, which is the content of Theorem 2.3 (see Theorem 7.1 for a precise statement).

Littlestone Classes. It is natural to ask which natural hypothesis classes have bounded Littlestone dimension. First, it holds that , so for finite classes the Littlestone dimension scales rather gracefully with their size.

There are also natural infinite Littlestone classes: for example, let the domain dimensional vector space over some field consist of all affine subspaces of V of dimension . It can be shown here that Ldim(H) = d. (For example, the class of all lines in Littlestone dimension 1.) A bit more generally, any class of hypotheses that can be described by polynomial equalities of a bounded degree has bounded Littlestone dimension. (Observe that if one replaces “equalities” with “inequalities” then the Littlestone dimension may become unbounded, however the VC dimension remains bounded (e.g. Halfspaces).) We note in passing that this can be further generalized to classes that are definable in stable theories, which is a deep and well-explored notion in model theory. We refer the reader to Chase and Freitag [2019], Section 5.1 for such examples.

Organization. Formal statement of our main results and description of our techniques appears in Section 2, specifically, a short overview of the proofs is given in Section 2.1. Definitions and background results are provided in Section 3. The complete proofs appear in the rest of the paper. Closure properties for Littlestone classes is proved in Section 4. The effective bounds for private learning are given in Section 5 and Sections 6 and 7. We note that each of these parts can be read independently of the other.

Let be a boolean function and let be hypothesis classes. Denote by the following class For example, if is the class of all pairwise intersections/conjunctions of a function from and a function from

Theorem 2.1 (A Closure Theorem for the Littlestone Dimension). Let be a boolean function, let be classes, and let

where conceals polynomial factors in log k and log d.

In particular, if . Consequently, if each of the ’s is online learnable then is online learnable. We comment that if the aggregating function G is simple then one can obtain better bounds. For example, if G is a majority-vote, a k-wise OR, or a k-wise AND function then a bound of holds. (See Section 4.2.2.)

Another combinatorial parameter which arises in the relationship between online and DP learning is the threshold dimension: a sequence threshold-shattered by H if there are such that if and only if threshold dimension, T(H) is the maximum size of a sequence that is threshold-shattered by H. The threshold dimension plays a key role in showing that DP learnable classes have a finite Littlestone dimension [Alon et al., 2019]. A classical theorem by Shelah [1978] in model theory shows that the Littlestone and the threshold dimensions are exponentially related.3 In particular if and only if . (See Theorem 3.2 in the preliminaries section.) We prove the following closure theorem in terms of the threshold dimension.

Theorem 2.2 (A Closure Theorem for the Threshold Dimension). Let be a boolean function, let be classes, and let

Moreover, an exponential dependence in t is necessary: for every there exists a class H such that

Note that the bounds in Theorem 2.1 and Theorem 2.2 escalate rapidly with k (the arity of G) and with t. It will be interesting to determine tight bounds.

By Alon et al. [2019], Bun et al. [2020], Theorem 2.1 also implies closure properties for DP-learnable classes. However, the quantitative bounds are even worse: not only do the bounds on the Littlestone dimension of escalate rapidly with d and k, also the quantitative relationship between the Littlestone dimension and DP-learning sample complexity is very loose, and the best bounds exhibit a tower-like gap between the upper and lower bounds. For example, if the class of functions H is finite and its Littlestone dimension is , then the bound of Theorem 2.1 is most likely to be much worse than the generic application of the exponential mechanism, whose sample complexity is the logarithm of the size of the class. We therefore explore the closure properties of differentially-private learning algorithms directly and derive the following bound.

Theorem 2.3 (A Closure Theorem for Private Learning (informal)). Let boolean function. Let be classes that are -differentially private and accurate learnable with sample complexity respectively. Then, -private and -accurate learnable with sample complexity

The exact quantitative satement of the results appears in Theorem 7.1. We remark that closure properties for pure differentially-private learning algorithms (i.e., when ) are implied by the characterization of [Beimel et al., 2019]. Similarly, closure properties for non-private PAC learning are implied by the characterization of their sample complexity in terms of the VC dimension and by the Sauer-Shelah-Perles Lemma [Sauer, 1972]. However, since there is no tight characterization of the sample complexity of approximate differentially-private learning algorithms (i.e., when ), we prove Theorem 2.3 algorithmically by constructing a (non-efficient) learning algorithm for from private learning algorithms for

Beimel et al. [2015] proved that any proper private learning algorithm in the realizable case4 can be transformed into an agnostic5 private learning algorithm, with only a mild increase in the sample complexity. We show that the same result holds even for improper private learning (i.e., when the private learning algorithm can return an arbitrary hypothesis).

Theorem 2.4 (Private Learning Implies Agnostic Private Learning). For every , and every concept class H, if there exists a -differentially private -accurate PAC learner for the hypothesis class H with sample complexity m, then there exists an -differentially private learner for H with sample complexity

Furthermore, if the original learner is proper, then the agnostic learner is proper.

We obtain this result by showing that a variant of the transformation of [Beimel et al., 2015] also works for the improper case; we do not know if the original transformation of [Beimel et al., 2015] also works for the improper case. Our analysis of the transformation for the improper case is more involved than the analysis for the proper case.

2.1 Technical Overview

2.1.1 Closure for Littlestone Dimension

Our proof of Theorem 2.1 exploits tools from online learning. It may be instructive to compare Theorem 2.1 with an analogous result for VC classes: a classical result by Dudley [1978] upper bounds the VC dimension of is the VC dimension of . The argument uses the Sauer-Shelah-Perles Lemma [Sauer, 1972] to bound the growth-rate (a.k.a. shatter function) of some : indeed, if we let then by the definition of the shatter function, , which implies that as stated. It is worth noting that a notion of growth-rate as well as a corresponding variant of the Sauer-Shelah-Perles Lemma also exist for Littlestone classes [Bhaskar, 2017, Chase and Freitag, 2018]. However we are not aware of a way of using it to prove Theorem 2.1.

We take a different approach. We first focus on the case where G is a majority-vote. That is, the class consists of all k-wise majority-votes of experts . We bound the Littlestone dimension of H by exhibiting an online learning algorithm A that learns H in the mistake-bound model with at most mistakes. The derivation of A exploits fundamental tools from online learning such as the Weighted Majority Algorithm by Littlestone and Warmuth [1989] and Online Boosting [Chen et al., 2012, Beygelzimer et al., 2015, Brukhim et al., 2020].

Then, the bound for a general is obtained by expressing G as a formula which only uses majority-votes and negations gates. The exponential dependence in k in the final bound is a consequence of the formula-size which can be exponential in k. We do not know whether this exponential dependence is necessary.

2.1.2 Closure for Threshold Dimension

Our proof of Theorem 2.2 is combinatorial. First, note that an inferior bound follows from Theorem 2.1, using the fact that the Littlestone and threshold dimensions are exponentially related (see Theorem 3.2). However this approach yields a super-exponential bound on

The bound in Theorem 2.2 follows by arguing contra-positively that if then is also “largish” for some . Specifically, if . This is shown using a Ramsey argument that asserts that any large enough sequence that is threshold-shattered by must contain a relatively large subsequence that is threshold-shattered by one of the ’s. Quantitatively, if then there must be a subsequence that is threshold-shattered by one of the

This upper bounds . It is worth noting that, in contrast with Theorem 2.1, an exponential dependence here is inevitable: we prove in Theorem 2.2 that for any t there exists a class This lower bound is achieved by a randomized construction.

2.1.3 Private learning Implies Agnostic Private Learning

We start by describing the transformation of [Beimel et al., 2015] from a proper private learning algorithm of a class H to an agnostic proper private learning algorithm for H. Assume that there is a private learning algorithm A for H with sample complexity m. The transformation takes a sample S of size O(m) and constructs all possible behaviors H of functions in H on the points of the sample (ignoring the labels). By the Sauer-Shelah-Perles Lemma, the number of such behaviors is at most. Then, it finds using the exponential mechanism a behavior that minimizes the empirical error on the sample. (The exponential mechanism is guaranteed to identify a behavior with small empirical error because the number of possible behaviors is relatively small.) Finally, the transformation relabeles the sample applies A on the relabeled sample. If A is a proper learning algorithm then, by standard VC arguments, the resulting algorithm is an agnostic algorithm for H. The privacy guarantees of the resulting algorithm are more delicate, and it is only O(1)-differentially private, even if -differentially private for a small (The difficulty in the privacy analysis is the set of behaviors H is data-dependent. Therefore, the privacy guarantees of the resulting algorithms are not directly implied by those of the exponential mechanism, which assume that the set of possible outcomes is fixed and data-independent.)

When A is improper, we cannot use VC arguments to argue that the resulting algorithm is an agnostic learner. We rather use the generalization properties of differential privacy (proved in [Dwork et al., 2015, Bassily et al., 2016, Rogers et al., 2016, Feldman and Steinke, 2017, Nissim and Stemmer, 2017, Jung et al., 2020]): if a differentially private algorithm has a small empirical error on a sample chosen i.i.d. from some distribution, then it also has a small generalization error on the underlying distribution (even if the labeling hypothesis is chosen after seeing the sample). There are technical issues in applying these results in our case that require some modifications in the transformation.

2.1.4 Closure for Differentially Private Learning

We prove Theorem 2.3 by constructing a private algorithm for the class private learning algorithms for the classes . Algorithm uses the relabeling procedure (the one that we use to transform a private PAC learner into a private agnostic learner) in a new setting.

The input to is a sample labeled by some function in . The algorithm finds hypotheses in steps, where in the i’th step, the algorithm finds a hypothesis have a completion to a hypothesis with small error (assuming that have a good completion).

Each step of is similar to the algorithm for agnostic learning described above. That is, in the first relabels the input sample S using some in a way that guarantees completion to a hypothesis with small empirical error. The relabeling h is chosen using the exponential mechanism with an appropriate score function. The relabeled sample is then fed to the private algorithm for the class to produce a hypothesis and then the algorithm proceeds to the next step i + 1. As in the algorithm for agnostic learning, the proof that the hypothesis returned by the algorithm is easier when the private algorithms for are proper and it is more involved if they are improper.

This section is organized as follows: Section 3.1 contains basic definitions and tools related to the Littlestone dimension and Section 3.2 contains basic definitions and tools related to private learning.

3.1 Preliminaries on the Littlestone Dimension

The Littlestone dimension is a combinatorial parameter that characterizes regret bounds in online learning [Littlestone, 1987, Ben-David et al., 2009]. The definition of this parameter uses the notion of mistake-trees: these are binary decision trees whose internal nodes are labeled by elements of X. Any root-to-leaf path in a mistake tree can be described as a sequence of examples is the label of the i’th internal node in the path, and ’th node in the path is the right child of the i’th node, and otherwise . We say that a tree T is shattered by H if for any root-to-leaf path . The Littlestone dimension of H, denoted by Ldim(H), is the depth of the largest complete tree that is shattered by H.

Definition 3.1 (Subtree). Let T be labeled binary tree. We will use the following notion of a subtree depth h of T by induction on h:

1. Any leaf of T is a subtree of height 0.

2. For a subtree of height h is obtained from an internal vertex of T together with a subtree of height of the tree rooted at its left child and a subtree of height of the tree rooted at its right child.

Note that if T is a labeled tree and it is shattered by the class H, then any subtree of it with the same labeling of its internal vertices is shattered by the class H.

Threshold Dimension. A classical theorem of Shelah in model-theory connects bounds on 2-rank (Littlestone dimension) to the concept of thresholds: let be a hypothesis class. We say that a sequence threshold-shattered by H if there are and only if . Define the threshold dimension, T(H), as the maximum size of a sequence that is threshold-shattered by H.

Theorem 3.2 (Littlestone Dimension versus Threshold Dimension [Shelah, 1978, Hodges, 1997]). Let H be a hypothesis class, then:

3.2 Preliminaries on Private Learning

Differential Privacy. Consider a database where each record contains information of an individual. An algorithm is said to preserve differential privacy if a change of a single record of the database (i.e., information of an individual) does not significantly change the output distribution of the algorithm. Intuitively, this means that the information inferred about an individual from the output of a differentially-private algorithm is similar to the information that would be inferred had the individual’s record been arbitrarily modified or removed. Formally:

Definition 3.3 (Differential privacy [Dwork et al., 2006b,a]). A randomized algorithm -differentially private if for all neighboring databases (i.e., databases differing in one entry), and for all sets F of outputs,

where the probability is taken over the random coins of we omit it and say that A preserves pure -differential privacy. When , we use the term approximate differential privacy , in which case is typically a negligible function of the database size m.

PAC Learning. We next define the probably approximately correct (PAC) model of Valiant [1984]. A hypothesis is a predicate that labels examples taken from the domain X by either 0 or 1. We sometime refer to a hypothesis as a concept. A hypothesis class H over X is a set of hypotheses (predicates) mapping X to {0, 1}. A learning algorithm is given examples sampled according to an unknown probability distribution P over X, and labeled according to an unknown target concept . The learning algorithm is successful when it outputs a hypothesis h that approximates the target concept over samples from P. More formally:

Definition 3.4. The generalization error of a hypothesis with respect to a concept c and a distribution P over X is defined as we say that h is

Definition 3.5 (PAC Learning [Valiant, 1984]). An algorithm -accurate PAC learner for a hypothesis class H over X if for all concepts , all distributions P on X, given an input of m samples is drawn i.i.d. from P, algorithm A outputs a hypothesis h satisfying

where the probability is taken over the random choice of the examples in S according to P and the random coins of the learner A. If the output hypothesis h always satisfies is called a proper PAC learner; otherwise, it is called an improper PAC learner.

Definition 3.6. For an unlabeled sample empirical error of two concepts

For a labeled sample empirical error of

The previous definition of PAC learning captures the realizable case, that is, the examples are drawn from some distribution and labeled according to some concept . We next define agnostic learning, i.e., where there is a distribution over labeled examples and the goal is to find a hypothesis whose error is close to the error of the best hypothesis in H with respect to the distribution. Formally, for a distribution on and a function

Definition 3.7 (Agnostic PAC Learning). Algorithm agnostic PAC learner for a hypothesis class H with sample complexity m if for all distributions , given an input of m labeled samples , where each labeled example is drawn i.i.d. from algorithm A outputs a hypothesis satisfying

where the probability is taken over the random choice of the examples in S according to and the random coins of the learner A. If the output hypothesis h always satisfies is called a proper agnostic PAC learner; otherwise, it is called an improper agnostic PAC learner.

The following bound is due to [Vapnik and Chervonenkis, 1971, Blumer et al., 1989].

Theorem 3.8 (VC-Dimension Generalization Bound). Let H and P be a concept class and a distribution over a domain

Suppose that we draw an unlabeled sample are drawn i.i.d. from P. Then,

The next theorem, due to [Vapnik and Chervonenkis, 1971, Anthony and Bartlett, 2009, Anthony and Shawe-Taylor, 1993], handles (in particular) the agnostic case.

Theorem 3.9 (VC-Dimension Agnostic Generalization Bound). There exists a constant such that for every domain X, every concept class H over the domain X, and every distribution over the domain For a sample

and are drawn i.i.d. from , it holds that

Notice that in Theorem 3.9 the sample complexity is proportional to , as opposed to in Theorem 3.8.

Private Learning. Consider an algorithm A in the probably approximately correct (PAC) model of Valiant [1984]. We say that A is a private learner if it also satisfies differential privacy w.r.t. its training data.

Definition 3.10 (Private PAC Learning [Kasiviswanathan et al., 2011]). Let A be an algorithm that gets an input , where each is a labeled example. Algorithm -differentially private -accurate PAC learner with sample complexity m for a class H over X if

Note that the utility requirement in the above definition is an average-case requirement, as the learner is only required to do well on typical samples. In contrast, the privacy requirement is a worst-case requirement that must hold for every pair of neighboring databases (no matter how they were generated).

The following definition and lemma are taken from Bun et al. [2015].

Definition 3.11 (Empirical Learner). Algorithm -accurate empirical learner for a class H over X with sample complexity m if for every and for every sample S of size m that is labeled by c, the algorithm A outputs a hypothesis satisfying

Lemma 3.12 (Bun et al. [2015]). Suppose -differentially private -accurate PAC learner for a concept class H with sample complexity be an algorithm, whose input sample S contains 9m randomly labeled examples. Further assume that samples with repetitions m labeled examples from S and returns the output of A on these examples. Then, -differentially private empirical learner for H with sample complexity 9m. Clearly, if A is proper, then so is

The Exponential Mechanism. We next describe the exponential mechanism of McSherry and Talwar [2007]. Let X be a domain and H a set of solutions. Given a score function a database , the goal is to chooses a solution approximately minimizing q(S, h). The mechanism chooses a solution probabilistically, where the probability mass that is assigned to each solution h decreases exponentially with its score q(S, h):

Kasiviswanathan et al. [2011] showed that the exponential mechanism can be used as a generic private learner – when used with the score function , the probability that the exponential mechanism outputs a hypothesis at most . This results in a generic private proper-learner for every finite concept class H, with sample complexity

Generalization Properties of Differentially Private Algorithms. In this paper we use the fact that differential privacy implies generalization [Dwork et al., 2015, Bassily et al., 2016, Rogers et al., 2016, Feldman and Steinke, 2017, Nissim and Stemmer, 2017, Jung et al., 2020]: differentially private learning algorithms satisfy that their empirical loss is typically close to their population loss. We use the following variant of this result, which is a multiplicative version that applies also to the case that (as needed in this paper).

Theorem 3.14 (DP Generalization – Multiplicative version [Dwork et al., 2015, Bassily et al., 2016, Feld- man and Steinke, 2017, Nissim and Stemmer, 2017]). Let -differentially private algorithm that operates on a database of and outputs a predicate be a distribution over X and S be a database containing n i.i.d. elements from P. Then,

In this section we study closure properties for Littlestone classes. We begin in Section 4.1 with a rather simple (and tight) analysis of the behavior of the Littlestone and Threshold dimension under unions. Then, in Section 4.2 we prove our main results in this part (Theorems 2.1 and 2.2) which bound the variability of the Littlestone and Thresholds dimension under arbitrary compositions.

4.1 Closure Under Unions

We begin with two basic bounds on the variability of the Littlestone/Threshold dimension under union. Note that here denotes the usual union: . These bounds are useful as they allows us to reduce a bound on the dimension of for arbitrary to the case where

Observation 4.1. [Threshold Dimension Under Union] Let be hypothesis classes with

Moreover, this bound is tight: for every , there are classes with Threshold dimension respectively such that

Proof. For the upper bound, observe that if threshold-shatters the sequence then threshold-shatters . For the lower bound, set if and only if

Proposition 4.2 (Littlestone Dimension Under Union). Let be hypothesis classes with

Moreover, this bound is tight: for every , there are classes with Littlestone dimension respectively such that

Proof of Proposition 4.2. There are several ways to prove this statement. One possibility is to use the realizable online mistake-bound setting [Littlestone, 1987] and argue that can be learned with at most mistakes in this setting. We present here an alternative inductive argument, which may be of independent interest. Towards this end, it is convenient to define the depth of the empty tree as that of a tree consisting of one vertex (leaf) as 0.

Consider a shattered tree with leaves labelled in the obvious way. Recall the notion of a subtree in Definition 3.1, and let be the maximum depth of a complete binary subtree all whose leaves are leaves, and the maximum depth of a subtree all whose leaves are -leaves. Similarly, let denote the maximum depth of a and a -subtree in the tree rooted at the left child of the root of be the same for the tree rooted at the right child.

It suffices to show that . Similarly

and this gives by induction on d (starting with as required. To see that this bound is tight, pick

One can verify that , as required (in fact, even the VC dimension of

Proposition 4.2 implies that provided that this inequality can be tight when k = 2. The following proposition shows that for a larger k this bound can be significantly improved:

Proposition 4.3 (Littlestone Dimension Under Multiple Unions). Let hypothesis classes with . Then, for every

Moreover, this bound is tight up to a constant factor: for every k, there are classes

Proposition 4.3 demonstrates a difference with the threshold dimension. Indeed, while the bound above scales logarithmically with k, in the case of the threshold dimension a linear dependence in k is necessary: indeed, set if and only if

Figure 1: An illustration of the tree shattered by in the construction in Proposition 4.3. In this illustration equals 3.

Proof of Proposition 4.3. We begin with the lower bound: pick any class with Littlestone dimension d, and let T be a tree of depth d which is shattered by new points X, and extend the domain by extending each ’s in each of the possible ways. (So, each for each possible pattern on the is a union of , one copy for each boolean pattern on the ’s. In particular, is the union of classes with Littlestone dimension d. Also note that , as witnessed by the tree which is illustrated in Figure 1.

The upper bound is based on a multiplicative-weights argument. Recall that the Littlestone dimension equals the optimal number of mistakes performed by a deterministic online learner in the mistake-bound model (i.e. online learning when the sequence of input examples is labelled by some ). Thus, it suffices to demonstrate an online learner for which makes at most 3d + 3 log k mistakes. Pick for every an online learner which makes at most d mistakes on input sequences consistent with set the online learning algorithm The Weighted Majority Algorithm by Littlestone and Warmuth [1989] with the k experts being the algorithms . Now, consider an input sequence consistent with H. Thus, S is consistent with and therefore makes at most d mistakes on it. Thus, by the multiplicative weights analysis (see e.g. Corollary 2.1 in Littlestone and Warmuth [1989]), the number of mistakes A makes on S is at most

where is multiplicative factor which discounts the weights of wrong experts. The upper bound follows by setting

4.2 Closure Under Composition

4.2.1 Threshold Dimension

Proof of Theorem 2.1. We begin with the upper bound. Let . It suffices to show that if then there is . By assumption, there are

functions

Construct a coloring of the edges of the complete graph on colors as follows: for each , the color of the edge {p, q} is given by the following ordered sequence of 2k bits:

By Ramsey Theorem [Ramsey, 1930], if then there is a monochromatic set of size Denote the elements of A by

and let such that the color of every pair in A is

Thus, for every pair

We claim that is threshold-shattered by the functions

Thus,

Therefore, and in particular . Pick an index . Therefore, for every

This shows that either is threshold shattered by is thresholds shattered by ); in either way, the threshold dimension of is at least t. This completes the proof of the upper bound.

Lower Bound. We next prove the lower bound. Let , and construct randomly as follows: H consists of 2m random functions

where for each , pick uniformly at random one of it to be 1 in position j and set the other to be 0 in position j. All of the aboverandom choices are done independently. By construction, threshold-shatters the sequence 1, 2 . . . , m with probability 1 and hence has threshold dimension at least m. It suffices to show that with a positive probability it holds that

We set out to prove (3). Consider the following event:

Note that E implies that and therefore it suffices to show that Pr[E] > 0. Towards this end we use a union bound: we define a family of “bad” events whose total sum of probabilities is less than one with the property that if none of the bad events occurs then E occurs. The bad events are defined as follows: for any pair of subsets denote the event

Note that indeed and thus it suffices to show that with a positive probability none of the occurs. We claim that

Indeed, for a fixed , the probability that one of is at most independence, the probability that the latter simultaneously holds for every is at most the probability that occurs for at least one pair A, B is at most

where the last inequality holds because

4.2.2 Littlestone Dimension

Proof of Theorem 2.1. We will first show that for an odd k, the majority-vote

(Recall that .) Then, we use this to argue that for any G,

We start with proving (4). Let , it suffices to show that . We use online boosting towards this end.

Online boosting (in the realizable setting) is an algorithmic framework which allows to transform a weak online learner for H with a non-trivial mistake-bound of sublinear regret function, to a strong online learner with a vanishing mistake-bound of boosting has been studied by several works (e.g. Chen et al. [2012], Beygelzimer et al. [2015], Brukhim et al. [2020]). We use here the variant given by Brukhim et al. [2020] (see Theorem 2 there)7.

Which weak learner to use? Recall that by Ben-David et al. [2009] (see Equation (1)) there exists an agnostic online learning algorithm W for H whose (expected) regret bound is

We claim that W is a weak learner for with mistake-bound

To prove this, it suffices to show that for every sequence of examples which is consistent with there exists which makes at most mistakes on it. Indeed, let that . Thus, on every example of the ’s make a mistake on it. By averaging, this implies that one of the makes at most mistakes in total, and (6) follows.

Now, by applying online boosting with W as a weak learner, we obtain an algorithm with a mistake-bound of at most

Thus, since the Littlestone dimension characterizes the optimal mistake-bound, letting get that

and in particular , which implies that

and finishes the proof of (4).

We next set out to prove (5). The idea is to represent an arbitrary G using a formula which only uses majority-votes and negations. Let be an arbitrary boolean function. It is a basic fact that G can be represented by a Disjunctive Normal Form (DNF) as follows:

where each . Now, note that

Thus, can be written as , where for class which contains the all-zero function

such that each class or its negation is the class contains the all-one function. We now apply (4) to conclude that that

as required.

In this section we describe our private learning algorithm. We start by discussing a relabeling procedure (discussed in 2), explaining the difficulties in designing the procedure and how we overcome them. We then provide a formal description of the relabeling procedure in and prove that it can be used to construct a private algorithm that produces hypothesis that has good generalization properties; this is done by presenting an algorithm

Let H be a hypothesis class, and suppose that we have a differentially private learning algorithm A for H for the realizable setting. That is, A is guaranteed to succeed in its learning task whenever it is given a labeled database that is consistent with some hypothesis in H. Now suppose that we are given a database S sampled from some distribution P on X and labeled by some concept (not necessarily in H). So, S might not be consistent with any hypothesis in H, and we cannot directly apply A on S. Heuristically, one might first relabel the database S using some function from H, and then apply A on the relabeled database. Can we argue that such a paradigm would satisfy differential privacy, or is it the case that the relabeling process “vaporises” the privacy guarantees of algorithm A?

Building on a result of Beimel et al. [2015], we show that it is possible to relabel the database before applying algorithm A while maintaining differential privacy. As we mentioned in the introduction, the relabeling procedure of Beimel et al. [2015] instantiates the exponential mechanism in order to choose a hypothesis h that is (almost) as close as possible to the original labels in S, uses this hypothesis to relabel the database, and applies the given differentially private algorithm A on the relabeled database to obtain an outcome f.

Now we want to argue that f has low generalization error. We known (by the guarantees of the exponential mechanism) that the hypothesis h with which we relabeled S has a relatively small empirical error on S (close to the lowest possible error). Via standard VC arguments, we also know that h has a relatively small generalization error. Therefore, in order to show that the returned hypothesis f has low generalization

error, it suffices to show that is small. This might seem trivial at first sight: Since as A is a PAC learner, and since it is applied on a database S labeled by the hypothesis , it must (w.h.p.) return a hypothesis f with small error w.r.t. h. Is that really the case? The difficulty with formalizing this argument is that A is only guaranteed to succeed in identifying a good hypothesis when it is applied on an i.i.d. sample from some underlying distribution. This is not true in our case. Specifically, we first sampled the database S from the underlying distribution, then based on S, we identified the hypothesis h and relabeled S using h. For all we know, A might completely fail when executed on such a database (not sampled in an i.i.d. manner).8 Therefore, before applying A on the relabeled database, we subsample i.i.d. elements from it, and apply A on this newly sampled database. Now we know that A is applied on an i.i.d. sampled database, and so, by the utility guarantees of A, the hypotheses f and h are close w.r.t. the underlying distribution. However, this subsampling step changes the distribution from which the inputs of A are coming from. This distribution is no longer P (the original distribution from which S was sampled), rather it is the uniform distribution on the empirical sample S. This means that what we get from the utility guarantees of is small. We need to show that If A is a proper learner, then f is itself in H, and hence, using standard VC arguments, the fact that is small implies that is small. However, if A is an improper learner, then this argument breaks because f might come from a different hypothesis class with a much larger VC dimension. To overcome this difficulty, we will instead relate using the generalization properties of differential privacy. These generalization properties state that if a predicate t was identified using a differentially private algorithm, then (w.h.p.) the empirical average of this predicate and its expectation over the underlying distribution are close. More formally, we would like to consider the predicate , which would complete our mission because the empirical average of that predicate on , and its expectation over . However, while f is indeed the outcome of a differentially private computation, h is not, and we cannot directly apply the generalization properties of differential privacy to this predicate. Specifically, our relabeling procedure does not reveal the chosen hypothesis h. We overcome this issue by introducing the following conceptual modification to the relabeling procedure. Let us think about the input database . In the relabeling procedure we still relabel all of S using h. We show that (a small variant of) this relabeling procedure still satisfies differential privacy w.r.t. D even if the algorithm publicly releases the relabeled database T. This works in our favour because given the relabeled database T we can identify a hypothesis that agrees with it, and by standard VC arguments we know that is small (since both addition, is computed by post-processing the relabeled database T which we can view as the result of a private computation w.r.t. D. Therefore, we can now use the generalization properties of differential privacy to argue that , which would allow us to complete the proof. We remark that the conceptual modification of treating S as two databases is crucial for our analysis. We do not know if the original relabeling procedure of Beimel et al. [2015] can be applied when A is an improper learner. In Algorithm 2 we formally describe . We next provide an informal description of the algorithm.

Let H be a hypothesis class, and let q be a score function. Algorithm takes two input databases , where the labels in D and T are arbitrary. The algorithm relabels D and T using a hypothesis with near optimal score q(D, h). The output of this algorithm is the two relabeled databases . Observe that algorithm is clearly not differentially private, since it outputs its input database (with different labels). Before formally presenting algorithm , we introduce the following definition.

Definition 5.1. Let X be a domain and let H be a class of functions over X. A function matched-sensitivity k if for every every that agree on every element of S we have that

In words, a score function q has low matched-sensitivity if given “similar” databases it assigns “similar” scores to “similar” solutions. Note that if a function q has matched-sensitivity 1, then in particular, it has (standard) sensitivity (at most) 1.

Example 5.2. Let H be a concept class over X. Then, the score function q(S, h) that takes a labeled database and a concept and returns the number of errors h makes on S has matched-sensitivity at most 1.

We next present an algorithm and analyze its properties. This algorithm is an abstraction of parts of and is used for unifying the proofs of privacy and correctness of these algorithms. We start with an informal description of algorithm algorithm first applies the relabeling algorithm and then applies a private algorithm to the relabeled database. For the analysis of our algorithms in the sequence, also publishes part of the relabeled database. We prove that guarantees differential privacy w.r.t. to the part of the database that it did not publish.

In Lemma 5.3, we analyze the privacy properties of algorithm

Lemma 5.3. Let -differentially private algorithm and q be a score function with matched-sensitivity 1. Then, for every V , algorithm

Thus, and similarly

More specifically, for every and every pattern there are either one or two (but not more) patterns in that agree with h on K. We denote these one or two patterns by may be identical if only one unique pattern exists. By the fact that q has matched-sensitivity at most 1, for every we have that

where the last inequality is because agree on every point in D and because q has matched-sensitivity at most 1.

For every be the probability that the exponential mechanism chooses either in Step (3) of the execution of . We get that for every

We are now ready to conclude the proof. For every be the event that the exponential mechanism chooses in Step (3) of the execution on be the random variable denoting the pattern that the exponential mechanism chooses in Step (3) of the execution on conditioned on the event . Observe that are distributions on neighboring databases; thus, applying the differentially private A on them satisfies differential privacy, i.e., for every possible sets of outputs F of A:

Recall that algorithm outcomes: the relabeled database , hypothesis h that is consistent with , and the output of algorithm A. As h is computed from , we can consider it as post-processing and ignore it, and assume for the the privacy analysis that two outputs: and the output of algorithm A. Also recall that the database V is fixed, and observe that once the hypothesis h is fixed (in Step (3) of algorithm ), the relabeled database is also fixed. Furthermore, for every we have that agree on all of V .

Let be a set of possible outcomes for algorithm the range of algorithm A. For every h we denote

Observe that for every we have that

because agree on all points in V . We calculate,

The next claim proves that returns a hypothesis whose score is close to the hypothesis with smallest score in the class H.

Claim 5.4. Fix be a labeled database such that

Consider the execution of denote the hypothesis chosen on Step (3). With probability at least we have that . In particular, assuming that it suffices that

Proof. Note that by Sauer-Shelah-Perles lemma,

As H contains all patterns of H restricted to S, the set H contains a pattern . Hence, Proposition 3.13 (properties of the exponential mechanism) ensures that the probability of the exponential mechanism choosing an is at most

which is at most

Let f denote the hypothesis returned by A and let h be a hypothesis consistent with the pattern chosen on Step (3) of . The next lemma relates the generalization error to the empirical error

Lemma 5.5. Fix be a distribution on be the marginal distribution on unlabeled examples from X. Furthermore, let be database sampled i.i.d. from

and

Consider the execution of be a hypothesis consistent with the pattern chosen on Step (3) of and assume that A outputs some hypothesis f. With probability at least we have that

Proof. Let h be the third output of , i.e., a hypothesis from H that is consistent with Since h and h agree on V and |V | is big enough, by Theorem 3.8, with probability at least sampling V ),

Since |D| is big enough, by Theorem 3.9 (applied to and the distribution that samples x according to P and labels it with 0), with probability at least

We will now use the generalization properties of differential privacy to argue that By Lemma 5.3, algorithm -differentially private w.r.t. the database D. In addition, by post-processing the outcomes of (the hypotheses f and h) we can define the following predicate otherwise. Now observe that

Similarly,

Recall that test is the result of a private computation on the database D (obtained as a post-processing of the outcomes of ). Also observe that since -differentially private, it is in particular,-differentially private for every choice of assuming , Theorem 3.14 (the generalization properties of differential privacy) states that with probability at least

So, by (9), (10), and (11), with probability at least

Thus, the next inequality, which concludes the proof, holds with probability

In this section we show that private learning implies private agnostic learning (with essentially the same sample complexity) even for improper learning algorithms. Algorithm , the agnostic algorithm for a class H, first applies algorithm on the data and relabels the sample using a hypothesis in H that has close to minimal empirical error, and then uses the private learning algorithm (after sub-sampling) to learn the relabeled database.

Theorem 6.1 (Theorem 2.4 Restated). Let -differentially private -accurate PAC learner for H with sample complexity differentially private learner for H with sample complexity

Proof. The privacy properties of the algorithm are straightforward. Specifically, by Lemma 3.12, Step (3) the algorithm (applying A on a subsample from -differential privacy. Algorithm is, therefore, -differentially private by Lemma 5.3. In particular, if A is (1, 0)-differentially private then -differentially private.

As for the utility analysis, fix a target distribution , and denote

Also let P denote the marginal distribution on unlabeled examples from X. Let S be a sample containing n i.i.d. samples from , and denote . By Theorem 3.9 (the agnostic VC generalization bound), assuming that , with probability at least sampling S), the following event occur.

We continue with the analysis assuming that this event occurs, and show that (w.h.p.) the hypothesis f returned by the algorithm has low generalization error. Consider the execution of Step (2) we apply algorithm to obtain the relabeled databases be a hypothesis extending the pattern used by algorithm to relabel these databases. By Claim 5.4, assuming that |D| is big enough, with probability at least it holds that

In this case, by Event we have that

Recall that A is executed on the database Q containing i.i.d. samples from . By Lemma 3.12, with probability at least , the hypothesis f chosen in Step (3) satisfies

By Lemma 5.5 and (15) with probability at least

In this section we prove Theorem 7.1 – if are privately learnable, then vately learnable.

Theorem 7.1 (Closure Theorem for Private Learning). Let be a boolean function and be classes that are -differentially private and -accurate learnable by a possibly improper learning algorithms with sample complexity respectively. Then, -private and -accurate learnable with sample complexity

To prove Theorem 7.1, we present – a generic transformation of private learning algorithms for the classes respectively to a private learner for transformation could be applied to proper as well as improper learners, and to a learners that preserves pure or approximate privacy. Given a labeled sample S of size N, algorithm finds hypotheses in steps, where in the i’th step, the algorithm finds a hypothesis have a completion to a hypothesis with small error (assuming that have a good completion). In the relabels the input sample S so that the relabeled sample is realizable by . The relabeling h is chosen using in a way that guarantees completion to a hypothesis with small empirical error. That is, using an appropriate score-function in (i.e., in the exponential mechanism), it is guaranteed that for the hypotheses computed in the previous steps there are some such that the function has a small loss with respect to the original sample S. The relabeled sample is fed (after subsampling) to the private algorithm to produce a hypothesis and then the algorithm proceeds to the next step i + 1.

In Lemma 7.2, we analyze the privacy guarantees of

Lemma 7.2. Let and assume the algorithms -private. Then, -differentially private.

Proof. Fix and consider the i’th step of the algorithm. By Lemma 3.12, Step (2c) of algorithm (i.e., sub-sampling with replacement and executing a -private algorithm) is differentially private. Thus, by Lemma 5.3, Steps (2b)–(2c) of algorithm differentially private. Since each step is executed on a disjoint set of examples, differentially private.

In the next lemma we prove that is an accurate learner for the class

Lemma 7.3. Assume that -differentially private -accurate (possibly improper) learning algorithms for with sample complexity . If at each iteration

then with probability at least we have that is the hypothesis returned by

Proof. Let be the hypotheses that computes in Step (2c). We prove by induction that for every with probability at least there exist such that

The induction basis for i = 0 is implied by the fact that the examples are labeled by some from . For the induction step, assume that there are

We need to prove that with probability at least such that

Recall that each example in S, and hence in , is chosen i.i.d. from the distribution in P. Since

by Theorem 3.9 applied to , with probability at least sampling of ) the following event occurs:

We continue proving the induction step assuming that occurs. The proof of the induction step is as follows: Since

By the definition of that agrees with , and therefore

By Claim 5.4, if

We assume that the above event occurs, thus, the latter implies that there are

Since occurs, by (22),

Since

Lemma 3.12 implies that Step (2c) of empirical learner and, therefore, with probability at least

Again, we assume in the rest of the proof that the above event occurs. By Lemma 5.5, since

with probability at least

Thus, by (25), with probability at least

The latter, combined with (23), implies the induction step: with probability at least

By (19), (21), (24), and (26), the sample complexity ’th step is

To conclude, by a union bound, returns, with probability at least a hypothesis with error less than with respect to the distribution P.

Proof of Theorem 7.1.

Proof. Theorem 7.1 follows from Lemmas 7.2 and 7.3. Specifically, by Lemma 7.3, to prove that is -accurate it suffices that

By Lemma 7.2, -differentially private.

Remark 7.4. Since each -accurate learning algorithm for the class

Furthermore, by the Sauer-Shelah-Perles Lemma, sample complexity of

For constant this is nearly tight. By using sub-sampling (see e.g., Kasiviswanathan et al. [2011], Beimel et al. [2014]), we can achieve -differential privacy by increasing the sample complexity by a factor of . Furthermore, by using private boosting Dwork et al. [2010], one can start with a private algorithm that is, for example, accurate and get a private algorithm that is by increasing the sample complexity by a factor of , and by simple technique, one can boost by increasing the sample complexity by a factor of . Thus, we get an -differentially private accurate learner for whose sample complexity is

We thank Adam Klivans and Roi Livni for insightful discussions.

Jacob D. Abernethy, Chansoo Lee, Audra McMillan, and Ambuj Tewari. Online learning via differential privacy. CoRR, abs/1711.10019, 2017. URL http://arxiv.org/abs/1711.10019.

Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private PAC learning implies finite Littlestone dimension. In Proceedings of the 51st Annual ACM Symposium on the Theory of Computing, STOC ’19, New York, NY, USA, 2019. ACM.

Martin Anthony and John Shawe-Taylor. A result of Vapnik with applications. Discrete Applied Mathematics, 47(3):207–217, 1993.

Matin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, 2009. ISBN 9780521118620. URL http://books.google.co.il/books?id= UH6XRoEQ4h8C.

Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algo- rithmic stability for adaptive data analysis. In Proceedings of the 48th Annual ACM Symposium on the Theory of Computing, STOC ’16, pages 1046–1059, New York, NY, USA, 2016. ACM.

Amos Beimel, Hai Brenner, Shiva Prasad Kasiviswanathan, and Kobbi Nissim. Bounds on the sample complexity for private learning and private data release. Machine Learning, 94(3):401–437, 2014.

Amos Beimel, Kobbi Nissim, and Uri Stemmer. Learning privately with labeled and unlabeled examples. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’15, pages 461–477, Philadelphia, PA, USA, 2015. SIAM.

Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of pure private learn- ers. Journal of Machine Learning Research, 20(146):1–33, 2019. URL http://jmlr.org/papers/ v20/18-269.html.

Shai Ben-David, D´avid P´al, and Shai Shalev-Shwartz. Agnostic online learning. In COLT 2009 – The 22nd Conference on Learning Theory, 2009. URL http://www.cs.mcgill.ca/%7Ecolt2009/papers/ 032.pdf#page=1.

Alina Beygelzimer, Satyen Kale, and Haipeng Luo. Optimal and adaptive algorithms for online boosting. In International Conference on Machine Learning, pages 2323–2331, 2015.

Siddharth Bhaskar. Thicket density. Technical Report arXiv:1702.03956, ArXiV, 2017.

Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4):929–965, 1989.

Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran. Online agnostic boosting via regret minimiza- tion. CoRR, abs/2003.01150, 2020.

Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’15, pages 634–649, Washington, DC, USA, 2015. IEEE Computer Society.

Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. CoRR, abs/2003.00563, 2020. URL https://arxiv.org/abs/2003.00563.

Hunter Chase and James Freitag. Model theory and combinatorics of banned sequences, 2018.

Hunter Chase and James Freitag. Model theory and machine learning. The Bulletin of Symbolic Logic, 25 (03):319332, Feb 2019. ISSN 1943-5894. doi: 10.1017/bsl.2018.71. URL http://dx.doi.org/10. 1017/bsl.2018.71.

Shang-Tse Chen, Hsuan-Tien Lin, and Chi-Jen Lu. An online boosting algorithm with theoretical justi- fications. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML12, page 18731880, Madison, WI, USA, 2012. Omnipress. ISBN 9781450312851.

R. M. Dudley. Central limit theorems for empirical measures. Ann. Probab., 6(6):899–929, 12 1978. doi: 10.1214/aop/1176995384. URL https://doi.org/10.1214/aop/1176995384.

Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, our- selves: Privacy via distributed noise generation. In Proceedings of the 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT ’06, pages 486–503, Berlin, Heidelberg, 2006a. Springer.

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the 3rd Conference on Theory of Cryptography, TCC ’06, pages 265–284, Berlin, Heidelberg, 2006b. Springer.

Cynthia Dwork, Guy N. Rothblum, and Salil Vadhan. Boosting and differential privacy. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS ’10, pages 51–60, Washington, DC, USA, 2010. IEEE Computer Society.

Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. The reusable holdout: Preserving validity in adaptive data analysis. Science, 349(6248):636–638, 2015.

Vitaly Feldman and Thomas Steinke. Generalization for adaptively-chosen estimators via stable median. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, volume 65 of Proceedings of Machine Learning Research, pages 728–757. PMLR, 2017. URL http://proceedings.mlr.press/v65/feldman17a. html.

Alon Gonen, Elad Hazan, and Shay Moran. Private learning implies online learning: An efficient reduction. NeurIPS, 2019.

R. E. Greenwood and A. M. Gleason. Combinatorial relations and chromatic graphs. Canadian Journal of Mathematics, 7:1–7, 1955. doi: 10.4153/CJM-1955-001-4.

Wilfrid Hodges. A Shorter Model Theory. Cambridge University Press, New York, NY, USA, 1997. ISBN 0-521-58713-1.

Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. The role of interactivity in local differential privacy. In FOCS, 2019.

Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Moshe Shenfeld. A new analysis of differential privacy’s generalization guarantees. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 31:1–31:17. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik, 2020. doi: 10.4230/LIPIcs.ITCS.2020.31. URL https://doi.org/10.4230/LIPIcs.ITCS.2020.31.

Haim Kaplan, Katrina Ligett, Yishay Mansour, Moni Naor, and Uri Stemmer. Privately learning thresholds: Closing the exponential gap, 2019.

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.

N. Littlestone and M. K. Warmuth. The weighted majority algorithm. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, SFCS 89, page 256261, USA, 1989. IEEE Computer Society. ISBN 0818619821. doi: 10.1109/SFCS.1989.63487. URL https://doi.org/10.1109/ SFCS.1989.63487.

Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2(4):285–318, 1987.

Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’07, pages 94–103, Washington, DC, USA, 2007. IEEE Computer Society.

Kobbi Nissim and Uri Stemmer. Personal communication, 2017.

F. P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, s2-30 (1):264–286, 1930. doi: 10.1112/plms/s2-30.1.264. URL https://londmathsoc.onlinelibrary. wiley.com/doi/abs/10.1112/plms/s2-30.1.264.

Ryan Rogers, Aaron Roth, Adam Smith, and Om Thakkar. Max-information, differential privacy, and post- selection hypothesis testing. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’16, pages 487–494, Washington, DC, USA, 2016. IEEE Computer Society.

F. Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386–408, 1958. ISSN 0033-295X. doi: 10.1037/h0042519. URL http: //dx.doi.org/10.1037/h0042519.

N. Sauer. On the density of families of sets. J. Comb. Theory, Ser. A, 13:145–147, 1972. ISSN 0097-3165. doi: 10.1016/0097-3165(72)90019-2.

Saharon. Shelah. Classification theory and the number of non-isomorphic models. North-Holland Pub. Co. ; sole distributors for the U.S.A. and Canada, Elsevier/North-Holland Amsterdam ; New York : New York, 1978. ISBN 0720407575.

Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984.

V.N. Vapnik and A.Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16:264–280, 1971. ISSN 0040-585X; 1095-7219/e. doi: 10.1137/1116025.