Source-linked AI summary
Nearly Linear Private Learning of Littlestone Classes
Shay Moran, Chao Yan
TL;DR
For approximate private PAC learning, finite Littlestone dimension characterizes learnability, but how it controls sample complexity remains a central question. The paper develops a structural exponential mechanism for ranked, data-dependent candidates and constructs ranks for general Littlestone classes. It proves an O(d log d) general upper bound and a tight linear-in-d subspace bound independent of ambient dimension.
Problem
How Littlestone dimension controls private sample complexity remains open, despite prior general upper bounds improving to eO(d^5).
Source: §1 · p. 2Method
A structural exponential mechanism handles data-dependent candidate sets using a rank, and the paper constructs a suitable rank for general Littlestone classes.
Source: §3 · p. 5, §3.3 · p. 8Results
O(d log d) is the general upper bound, while subspace learning has tight linear dependence on d independent of field and ambient dimension.
Source: §1 · pp. 2–3, §3 · p. 5Takeaways & Limitations
For subspace indicators, codimension gives a natural rank and yields a tight sample-complexity bound that avoids dependence on ambient dimension.
Source: §1 · p. 3, §3 · p. 5The guarantees are stated in the realizable setting, and whether complexity can depend on VC dimension and log* d remains open.
Source: §2 · p. 3, §2.1 · p. 3
Abstract
from arXiv · showhide
Differentially private learning aims to learn from data while protecting individual training examples. For binary classification, finite Littlestone dimension characterizes approximate private PAC learnability (Alon et al., JACM 2022). Understanding how this dimension controls private sample complexity remains a central question. For classes of Littlestone dimension $d$, the first general upper bound was doubly exponential in $d$ (Bun, Livni, and Moran, FOCS 2020). Subsequent work improved this to $\widetilde O(d^6)$ (Ghazi et al., STOC 2021) and then to $\widetilde O(d^5)$ (Lyu, STOC 2026). We prove a nearly linear upper bound of $O(d\log d)$. Our main algorithmic contribution is a structural exponential mechanism for data-dependent candidate sets equipped with a rank satisfying suitable stability conditions. For natural Littlestone classes such as subspace indicators, this rank has a simple geometric interpretation: it is the codimension. This yields a private PAC learner for subspaces of dimension at most $d$ over any field, with tight linear dependence on $d$ and no dependence on the ambient dimension, improving the quadratic dependence of Kaplan et al. (STOC 2025). Our second contribution is combinatorial: drawing on model-theoretic ideas, we construct a suitable rank for general Littlestone classes and establish the counting bounds required by the mechanism.
1 Introduction
The introduction frames private learning’s open questions around sample complexity and the principles that attain it. It presents an O(d log d) upper bound for Littlestone classes, obtained with a structural exponential mechanism and a stable rank, with codimension yielding a dimension-independent subspace learner.
1 Introduction
- Approximate private PAC learnability is characterized by finite Littlestone dimension, but optimal sample complexity and the methods attaining it remain open.Earlier general upper bounds improved from doubly exponential in d to eO(d^6) and then eO(d^5); the general lower bound is Ω(v + log* d).Source: §1 · p. 2
- O(d log d) is a nearly linear general upper bound in Littlestone dimension, optimal up to a logarithmic factor when VC dimension equals d.Without privacy, learning requires Ω(v) examples, giving an Ω(d) lower bound for classes with v = d.Source: §1 · p. 2
- The structural exponential mechanism handles data-dependent candidate sets by equipping hypotheses with a rank satisfying stability conditions.The paper constructs such a rank for general Littlestone classes, drawing on model-theoretic connections to learning [20] [21].Source: §1 · p. 2
- For subspace indicators, codimension supplies the rank and yields a tight sample-complexity bound linear in the maximum subspace dimension and independent of ambient dimension.This provides the paper’s simpler application of the structural mechanism.Source: §1 · pp. 2–3
2 Main Results
The main results give a nearly optimal general sample-complexity bound and a structural exponential mechanism for data-dependent candidates. The mechanism’s score guarantee depends on candidate count and rank range, while its stability conditions support the applications to Littlestone classes.
2 Main Results
- The stated guarantees are for the realizable setting; known reductions extend them to the agnostic setting while preserving properness.The refined reduction incurs an additive sample overhead of eO(VCdim(H)/α^2), where α is excess error.Source: §2 · p. 3
2.1 Nearly Linear Dependence on Littlestone Dimension
- For fixed learning and privacy parameters, the general bound is O(d log d), compared with an Ω(d) lower bound when VC and Littlestone dimensions both equal d.The bound leaves open whether classes with VC dimension much smaller than Littlestone dimension admit substantially smaller sample complexity; the poly(v, log* d) question remains open.Source: §2.1 · p. 3
2.2 A Structural Exponential Mechanism
- The structural variant permits data-dependent candidate sets by controlling the probability of outputs that disappear between neighboring datasets.Approximate privacy allows that probability to be charged to δ; the mechanism adds a rank-based structural bonus to the empirical score.Source: The classical exponential mechanism · p. 4
The classical exponential mechanism
- The score guarantee combines the usual logarithmic candidate-count cost with a term linear in the rank range, which is at most d for the Littlestone-class application.For classification, the score counts correct examples and has sensitivity Δ = 1; the extra rank-range cost reflects local preimage growth.Source: The classical exponential mechanism · p. 5
3 Technical Overview
The technical overview develops a structural exponential mechanism for data-dependent candidate sets, using rank constructions from a rank-zero warm-up and subspace codimension to a combinatorial rank for general Littlestone classes. It also presents the local counting bound and applies the mechanism with classification accuracy, yielding the stated preimage-growth parameter and Theorem 1.
3.1 The Classical Exponential Mechanism
- Assigning every candidate rank zero recovers the classical exponential mechanism, with pure ε-privacy and the usual utility bound.The candidate universe is fixed, the rank bonus vanishes, and the identity maps satisfy the mechanism’s conditions with preimage bound B = 1.Source: §3 · p. 5, §3.1 · pp. 5–6
3.2 Subspaces: Codimension as Rank
- The bound is independent of the field and ambient dimension D; for fixed learning and privacy parameters, linear dependence on d is tight even without privacy, avoids an extra log d factor, and closes Kaplan et al. [14]’s quadratic dimensional gap in sample complexity.The full positive span is a candidate containing all positive examples; this does not establish that candidate subspaces generally are spanned by positive sample vectors. The result does not settle the computational-efficiency question also raised by Kaplan et al. [14].Source: §3.2 · pp. 6, 8
3.3 Littlestone Classes: Ranks and Local Counting
- For a class of Littlestone dimension d, the rank is defined by recursively requiring large Littlestone dimension in version spaces after prescribing labels on small sets.The rank applies to locally realizable predictors, is independent of the sample, and guides candidate construction using version spaces and their Standard Optimal Algorithm predictors.Source: §3.3 · pp. 8–9
Basic properties of the rank.
- The rank’s key properties are that higher-rank predictors have smaller Littlestone dimension, majorities of good families gain rank, and small witnesses distinguish predictors from others of equal or higher rank.The sample-dependent candidate set selects predictors across sample-induced version spaces, realizes every labeling induced by U, and neighboring-sample maps fix common candidates while increasing the rank of disappearing ones and preserving labels on the new sample.Source: Basic properties of the rank · pp. 9–10
- For n ≥ d, the candidate count has logarithm O(d log(en)), using good-family extraction, majority-based avoidance, and the Sauer–Shelah bound.A finite family of Littlestone dimension at most k with more than [2(d + 1)]^k members contains a good subfamily with at least two members; a good family’s majority raises rank.Source: Basic properties of the rank · p. 11
- [2(d + 1)]^(r − s) bounds selected rank-s predictors within a rank-r predictor’s witness version space and a fixed version space.Predictors of rank at least s in the witness version space have Littlestone dimension at most r − s (Lemma 7); the precise counting statements appear in Lemma 11.Source: Basic properties of the rank · p. 11
- 4(d + 1) bounds preimage growth when classification accuracy is the score, yielding Theorem 1 with rank range at most d.For rank gap t ≥ 1, preimages agree on common sample points and occupy at most two version spaces, so Lemma 11 gives 2[2(d + 1)]^t ≤ [4(d + 1)]^t; every realizable sample has a mistake-free candidate, and the utility bound plus VC generalization completes the result.Source: Basic properties of the rank · p. 11
4 Technical Preliminaries
The preliminaries define the learning and privacy settings, then introduce VC and Littlestone dimensions and the version spaces used in the paper. They also establish that subspace indicators of dimension at most d have both dimensions equal to d.
4.1 Learning and Privacy
- In realizable PAC learning, the learner must achieve population loss at most α with probability at least 1 − β; privacy is required independently of realizability.The section also defines addition/deletion neighboring samples and pure privacy as the case δ = 0.Source: §4.1 · p. 12
4.2 Dimensions, Version Spaces, and Generalization
- Littlestone dimension is the maximum depth of a mistake tree shattered by a class, modeling realizable online learning with adversarially chosen examples.The SOA predicts a label whose version space has maximum Littlestone dimension, and the opposite-label branch has smaller dimension.Source: §4.1 · p. 12, §4.2 · p. 13
- VC dimension bounds the number of nonempty version spaces induced by n points, while VC generalization transfers sufficiently low empirical loss to population loss.The section defines version spaces as predictors consistent with a labeled sequence and defines empirical loss by the number of mistakes.Source: §4.2 · pp. 12–13
- For every field F and 1 ≤ d ≤ D, the subspace class has VCdim(Hd,D) = LDim(Hd,D) = d.The proof shatters d linearly independent vectors and gives an online rule making at most d mistakes.Source: §4.2 · p. 13
5 Proof of the Structural Mechanism
The proof establishes privacy by controlling probability assigned to outputs that disappear between neighboring datasets. It establishes utility by comparing the mechanism’s sampled candidate with a highest-scoring candidate.
Privacy
- For each image and rank gap t, at most Bt disappearing outputs map to it, and each has weight at most wT(h)(δ/(8B))^t.Summing over preimages, rank gaps, and images bounds the total weight of disappearing outputs.Source: §5 · p. 14
- For common outputs, the rank is unchanged and low sensitivity bounds the weight ratio; the proof combines this comparison with a bound on disappearing-output probability to establish privacy.The proof applies the argument in both directions between neighboring datasets.Source: §5 · pp. 14–15
Utility
- With probability at least 1 − β, the sampled candidate’s score is bounded relative to the maximum score, with an additive term depending on log(N/β) and the rank range.The proof chooses a = (2/ε) log(N/β) and then converts the bound to the original score units.Source: §5 · p. 15
6 Application to Subspace PAC Learning
The subspace application uses codimension as a rank in a private span-selection procedure, then converts that procedure into a proper PAC learner. Its analysis bounds missed vectors and uses VC generalization to obtain population accuracy.
6.1 Private Span Selection
- SpanSelect samples candidate spans with score combining the number of input vectors contained in a span and its codimension.Its candidate set consists of spans generated by input vectors with dimension at most d.Source: §6.1 · p. 15
- SpanSelect is (ε, δ)-differentially private under addition/deletion on all finite vector sequences, and its output V is contained in span(P) with dimension at most d.If span(P) = {0}, there are no missed vectors.Source: §6.1 · p. 16
6.2 From Span Selection to a Proper PAC Learner
- The learner applies span selection to positive examples, returns a subspace indicator, and is proper and (ε, δ)-private.Privacy follows because one labeled example changes at most one positive vector, and the output is postprocessed to an indicator within the dimension cap.Source: §6.2 · pp. 16–17
- On realizable samples, the selected span lies inside the target subspace, so it incurs no false positives; the PAC proof uses VC generalization after bounding empirical error.The analysis notes that cancellation in log(en/d) avoids a d log d term in this sample bound.Source: §6.2 · p. 17
7 Application to Littlestone Classes
For general Littlestone classes, the paper constructs a rank and data-dependent candidate sets whose counts support the structural privacy mechanism. It then verifies the mechanism’s axioms and combines its utility guarantee with VC generalization for PAC learning.
7.1 Basic Properties of the Rank
- The output universe allows predictors whose labels on every set of at most d + 1 points are consistent with H; the rank tracks surviving Littlestone dimension under small label prescriptions.Predictors of rank at least s have Littlestone dimension at most d − s; overwhelming pointwise majorities increase rank, and each predictor has a small distinguishing witness.Source: §7 · p. 17, §7.1 · pp. 17–18
7.2 Candidate Construction and Counting
- The candidate construction processes version spaces by decreasing rank and excludes predictors covered by higher-rank candidates’ witness version spaces.The counting argument uses good-subfamily extraction, rank increase, avoidance, and coverage; the local count depends on the rank gap.Source: §7.2 · pp. 19, 21
- For n ≥ d, the candidate set satisfies |C(S)| ≤ 2[2(d + 1)]^d(en/d)^d.The bound combines a rank-based count within each version space with the Sauer–Shelah bound on the number of nonempty version spaces.Source: §7.2 · p. 21
7.3 Verifying the Structural Axioms
- Neighboring datasets admit maps that fix common candidates and send other candidates to higher-rank candidates, with at most [4(d + 1)]^t preimages at rank gap t.These maps verify all four structural axioms with Δ = 1 and B = 4(d + 1).Source: §7.3 · p. 22
7.4 Utility and PAC Learning
- The structural mechanism gives privacy on all samples, and its utility bound plus VC generalization yields the realizable PAC guarantee.The output’s VC dimension is at most d, and the proof completes the population-error bound by a union bound.Source: §7.4 · pp. 22–23
A A Private Solver for Linear Equalities
The section turns span selection into a private solver for linear systems: it selects a subspace of augmented equation rows, then uses that subspace to choose a solution with high probability satisfying most equations.
A A Private Solver for Linear Equalities
- With probability at least 1 −β, the algorithm returns a vector satisfying at least (1 −α)n equations of a consistent system.The algorithm is (ε, δ)-differentially private, including on inconsistent systems.Source: A A Private Solver for Linear Equalities · p. 25
- Applying SpanSelect to augmented rows yields W, from which a fixed rule chooses a solution when one exists and otherwise returns a fixed vector.The output choice depends only on W, so it preserves privacy by postprocessing.Source: A A Private Solver for Linear Equalities · p. 25
- When the system is consistent, its augmented rows span dimension at most d, and each row in W corresponds to an equation satisfied by the returned vector.The span-selection guarantee bounds the rows outside W, and the stated sample bound makes that number at most αn.Source: A A Private Solver for Linear Equalities · p. 25
B Extension to Agnostic Learning
The section applies a realizable-to-agnostic reduction and extends the resulting fixed-size learner to arbitrary input sizes. The extension preserves privacy at every size, while its accuracy guarantee requires at least n genuine examples.
B Extension to Agnostic Learning
- The realizable-to-agnostic reduction yields an (ε, δ0)-private learner under replacement with excess error O(α), failure probability O(β + nδ0), and preserved properness.It builds on the reduction of [17, Theorem 3.6].Source: B Extension to Agnostic Learning · pp. 25–26
- Choosing sufficiently small constant multiples of α and β and δ0 ≤ min{δ, cβ/n} gives (ε, δ)-privacy under replacement with the desired learning guarantee.The parameter choice controls the additional failure term O(nδ0).Source: B Extension to Agnostic Learning · p. 26
- For arbitrary input sizes, the extension pads inputs shorter than n, subsamples n examples from longer inputs, then randomly permutes before running the learner.The same fixed n is used on every input; permutation can be omitted for a permutation-invariant learner.Source: B Extension to Agnostic Learning · p. 26
- Coupling neighboring inputs makes the resulting fixed-size sequences differ in at most one coordinate, yielding (ε, δ0)-privacy at every input size.The learning guarantee holds with at least n genuine examples, but below n the extension asserts privacy only, not accuracy.Source: B Extension to Agnostic Learning · p. 26