Nearly Linear Private Learning of Littlestone Classes
Abstract
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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper proves a nearly linear upper bound of $O(d \log d)$ on the sample complexity of differentially private PAC learning for classes of Littlestone dimension $d$, resolving a central open problem in the field. By introducing a structural exponential mechanism that leverages a model-theoretic rank, the authors achieve a tight dependence on the Littlestone dimension, significantly improving upon previous polynomial bounds and providing a new algorithmic framework for private learning.
Methodology
The paper introduces a "structural exponential mechanism" that generalizes the classical exponential mechanism to handle data-dependent candidate sets. This is a significant algorithmic innovation in private learning theory. The core novelty lies in defining a combinatorial rank for hypotheses in Littlestone classes, derived from model-theoretic concepts (specifically Shelah's $2$-rank), and proving that this rank satisfies stability conditions necessary for differential privacy. The authors demonstrate that for subspace indicators, this rank corresponds to codimension, yielding a tight linear sample complexity bound $O(d \log d)$, which is optimal up to logarithmic factors. The methodology is rigorous, combining combinatorial arguments with privacy analysis.
Results & evaluation
This is a theoretical paper in learning theory and differential privacy. There are no empirical experiments, datasets, or benchmarks. The "evaluation" consists of mathematical proofs establishing upper bounds on sample complexity and verifying the privacy guarantees of the proposed mechanism. The contribution is entirely analytical.
Reproducibility
As a pure theory paper, reproducibility is defined by the correctness of the proofs. The paper provides detailed technical overviews and formal definitions. However, the full proofs are truncated in the provided text (ending in Section 5.1), so a complete verification of the combinatorial lemmas (specifically Lemmas 5.2-5.4 and the counting bounds in Section 5.3) is not possible from the snippet alone. Assuming the standard rigor of the authors (Moran, Yan) and the venue (likely STOC/FOCS level), the theoretical framework is sound.
Limitations
The primary limitation is that the result is a sample complexity bound, not a computational complexity bound. The paper explicitly states that it does not assert computational efficiency. The algorithm described (selecting candidates based on version spaces and ranks) may be computationally intractable for large $d$ or complex classes. Additionally, the bound is for the realizable setting; while reductions to the agnostic setting exist, they incur additional overhead. The log-star question regarding VC vs Littlestone dimension remains open.
Broader impact
This work resolves a major open problem in private learning theory by establishing a nearly linear dependence on Littlestone dimension. It provides a new algorithmic primitive (structural exponential mechanism) that can be applied to other private optimization problems involving data-dependent candidate sets. It bridges learning theory and model theory, offering new combinatorial tools for understanding the complexity of private learning. The result is significant for the theoretical understanding of the trade-offs between privacy and sample efficiency. The paper proves a nearly linear upper bound of $O(d \log d)$ on the sample complexity of differentially private PAC learning for classes of Littlestone dimension $d$, resolving a central open problem in the field. By introducing a structural exponential mechanism that leverages a model-theoretic rank, the authors achieve a tight dependence on the Littlestone dimension, significantly improving upon previous polynomial bounds and providing a new algorithmic framework for private learning.
Author of this paper? Send a correction.