Private PAC learning implies finite Littlestone dimension

1 Introduction

• Private learning asks how to learn from samples containing sensitive data while protecting that data.Differential privacy [Dwork et al., 2006b,a] provides a standard mathematical formalism for studying algorithmic privacy in machine learning.Source: §1 · p. 1
• Thresholds matter as a basic learning problem and as the one-dimensional version of Euclidean half-spaces, which underlie kernel machines and neural networks [Shalev-Shwartz and Ben-David, 2014].Without privacy, thresholds can be PAC learned with a constant number of examples; the private case has been more challenging.Source: §1 · p. 2
• For finite domains of size n, pure-private threshold learning has matching O(log n) sample bounds, while approximate-private bounds include an Ω(log*(n)) lower bound for proper learners [Feldman and Xiao, 2015; Bun et al., 2015].Whether the dependence on n can be removed for improper learners remained open; this paper states that its main result answers that question.Source: §1 · p. 2
• An invariant characterizing private learnability is sought, but no such parameter is known for approximate differential privacy.The introduction contrasts this gap with characterizations for pure privacy, including one-way communication complexity [Feldman and Xiao, 2015] and representation dimension [Beimel et al., 2013].Source: §1 · p. 2

1.1 Littlestone dimension vs. approximate private learning

• A class has finite Littlestone dimension exactly when it does not embed thresholds as a subclass, and private learning requires Ω(log*(d)) examples for dimension d.Whether every finite-Littlestone-dimension class is privately learnable remains open.Source: §1.1 · p. 3

2 Main Results

• Thresholds over an infinite domain cannot be learned privately.The threshold theorem considers approximate-DP learners with ε=0.1 and δ=O(1/(m^2 log m)).Source: §2 · p. 3
• Any privately learnable class has finite Littlestone dimension, extending a result by Feldman and Xiao [2015].The paper derives this implication by combining Theorems 1 and 3.Source: §2 · p. 4
• The corollary considers accurate learners with ε=0.1 and δ=O(1/(m^2 log m)).The supplied theorem statement identifies these privacy conditions but does not include its concluding quantitative bound.Source: §2 · p. 4

3.1 PAC learning

• The PAC setup focuses on realizable distributions, defines sample and distribution loss, and calls a learner (α, β)-accurate when it meets the stated error and confidence criteria.The section also defines the Littlestone dimension as the depth of the largest complete mistake tree shattered by the class.Source: §3.1 · pp. 4–5
• Shelah’s result connects finite Littlestone dimension with the absence of arbitrarily large threshold patterns, and the section gives a combinatorial proof of that connection.The connection is also placed alongside the relation between NIP theories and VC dimension [Laskowski, 1992].Source: §3.1 · p. 5
• A class containing d thresholds has Littlestone dimension at least floor(log d), connecting threshold structure to this online-learning complexity measure.The section defines containing k thresholds by an ordered sequence of points and hypotheses; it also notes Littlestone dimension coincides with Shelah’s 2-rank [Chase and Freitag, 2018].Source: §3.1 · p. 5

3.2 Privacy

• Differential privacy requires output distributions on samples differing in one example to be (ε, δ)-indistinguishable; the section treats ε as small and δ as negligible.It states that δ = 0 is pure differential privacy and gives a composition bound of (kε, kδ) for k independent outputs.Source: §3.2 · pp. 5–6
• The authors use private empirical learning as a simpler substitute for PAC learning, citing a result that converts a private PAC learner of sample complexity m into one with complexity 9m.The empirical task minimizes loss on realizable samples.Source: §3.2 · p. 6

3.3 Additional notations

• For ordered domains, the section defines increasing samples and ord_S(x) as the number of sample points at most x; points with equal rank form an interval.It also defines balanced samples as having equal numbers of positive and negative labels, and associates an algorithm and sample with its average output function.Source: §3.3 · pp. 6–7
• The iterated logarithm applies logarithms recursively, while log* counts applications until the value is at most 1.The section also defines the tower function recursively.Source: §3.3 · p. 7

4.1 Proof overview

• For any algorithm, a Ramsey argument finds a large homogeneous subset, where output probabilities are controlled by a list indexed by sample order.The coloring rounds probabilities associated with balanced increasing samples; a homogeneous set makes the rounded lists agree.Source: §4.1 · pp. 7–8, §4.3 · p. 11

4.2 Proof of Theorem 1

• The proof converts the learner to an empirical learner with the same privacy and accuracy parameters and at most 9 times the sample size, then combines bounds on the homogeneous set.The two lemmas give a set of size at least log^(m)(n)/2^O(m log m) and an upper bound of 2^O(m² log²m), yielding the threshold sample-complexity lower bound.Source: §4.2 · p. 10, §4.4 · p. 11

4.3 Proof of Lemma 9

• Coloring each (m+1)-subset by rounded output probabilities and applying a quantitative Ramsey theorem yields a homogeneous subset of size at least log^(m)(n)/2^O(m log m).The common color ensures that the resulting subset is m-homogeneous with respect to the algorithm.Source: §4.3 · p. 11

4.4 Proof of Lemma 10

• On an m-homogeneous set, the constructed family of distributions has size at least proportional to the set size but is bounded by 2^O(m² log²m).The distributions’ coordinate probabilities lie on opposite sides of a common value r, with a gap of 1/(10m) according to the relative positions of their indices.Source: §4.4 · p. 11

4.4.1 Proof of Lemma 12

• A gap of at least 1/(4m) between consecutive probabilities identifies an example position whose neighboring samples generate the distribution family.Replacing that example with different points gives neighboring samples; privacy makes their output distributions indistinguishable, while the probability gap separates coordinates around r.Source: §4.4.1 · pp. 12–13

4.4.2 Proof of Lemma 13

• A binary-search map on repeated output vectors creates disjoint events, while privacy and concentration bounds preclude too many such events.Assuming the family is too large gives more disjoint events with substantial probability than the privacy-based bound permits.Source: §4.4.2 · p. 13

5 Privately learnable classes have finite Littlestone dimension

• Ω(log*(d)) examples are required to privately learn a class with Littlestone dimension d.The proof selects floor(log d) hypotheses that realize thresholds and applies the threshold lower bound to this subclass.Source: §5 · p. 14

• The paper’s main result is a lower bound on private-learning sample complexity expressed in terms of Littlestone dimension.Source: §6 · p. 14
• Whether every class with finite Littlestone dimension can be learned privately remains an open question.Source: §6 · p. 14
• The open question concerns a broad set of mathematically interesting classes with finite Littlestone dimension, including examples noted by Chase and Freitag [2018].Source: §6 · p. 14

• The theorem is proved by induction using a lemma that composes indistinguishable distribution pairs under products.Source: A Proof of Lemma 5 · p. 17
• If p1 and q1, and p2 and q2, are respectively (ϵ1, δ1)- and (ϵ2, δ2)-indistinguishable, their product distributions are (ϵ1 + ϵ2, δ1 + δ2)-indistinguishable.Source: A Proof of Lemma 5 · p. 17
• The proof extends ∆1 and ∆2 to measures on X and defines S_a as the section of S containing pairs whose first coordinate is a.Source: A Proof of Lemma 5 · pp. 17–18

• A tree of height t can be labeled so that 2^t thresholds yield root-to-leaf paths ending at their corresponding leaves.Source: B Proof of Theorem 3 · p. 18
• A subtree of a shattered labeled tree remains shattered when its internal-vertex labels are retained.Source: B Proof of Theorem 3 · p. 18
• A two-colored tree of height p + q − 1 contains either a red subtree of height p or a blue subtree of height q.Source: B Proof of Theorem 3 · pp. 18–19
• If the Littlestone dimension is at least 2^(t+1) − 1, the proof shows that H contains t + 2 thresholds.It colors tree vertices according to a fixed h, applies a red-or-blue subtree lemma, then recurses on a child subtree.Source: B Proof of Theorem 3 · p. 19