PaperfootJoin free
arXiv

A proof cuts the data needed for private learning

A mathematical proof establishes a nearly linear upper bound on the training examples needed for private classification, improving on an earlier fifth-power bound.

Paper by Shay Moran, Chao Yan
A large blue structure sorts a few shapes into circles and squares along a clear black path, beside a smaller broken structure crowded with gray shapes.
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

In a preprint, the authors proved a nearly linear upper bound on the sample complexity of differentially private learning for binary classification classes of Littlestone dimension d. Sample complexity is the training data needed to learn, while private learning protects individual training examples. Earlier work showed that the required sample size scaled doubly exponentially with d, before subsequent research reduced it to a sixth power and then a fifth power.

The authors proved the bound by designing a structural exponential mechanism, an algorithm that evaluates candidate hypotheses with a stable ranking function. Using ideas from model theory, they constructed this rank for general Littlestone classes and proved the required counting bounds. For subspace indicators, the rank matches geometric codimension. This yielded a private learner for subspaces of dimension at most d over any field, with a tight linear dependence on d that improved on earlier quadratic bounds.

Why it matters

The mathematical proof shows that protecting individual privacy across these classification problems requires far less training data than earlier upper bounds suggested. For subspace indicators over any field, the result achieves a tight linear dependence on dimension with no dependence on the ambient dimension.

Caveats

The findings are theoretical proofs rather than empirical tests on real-world systems, and the abstract does not report computational running times. In addition, the paper is a preprint that has not yet undergone peer review.

In this paper

differentially private PAC learning of Littlestone classes

Methods
structural exponential mechanism (this paper)classical exponential mechanism (baseline)Standard Optimal Algorithm (SOA)

What it shows

For classes of finite Littlestone dimension d, there exists an (epsilon, delta)-differentially private (alpha, beta)-PAC learner with sample complexity O(d log d) for fixed learning and privacy parameters.

For fixed learning and privacy parameters, the bound is O(d\log d).

Theorem 1 (Private PAC learning of Littlestone classes).

The structural exponential mechanism operates on data-dependent candidate sets and satisfies (epsilon, delta)-differential privacy.

Then, Algorithm 1 is (\varepsilon,\delta) -differentially private and for every dataset S and 0<\beta<1, with probability at least 1-\beta its output satisfies

Theorem 2 (Structural exponential mechanism).

Quoted word for word from the full text on arXiv.

The paper

Nearly Linear Private Learning of Littlestone Classes

Shay Moran, Chao Yan

arXiv, Oct 16, 2026, Open access, CC0, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.23160

arXiv:2610.23160v1 in cs.LG

AbstractPDFHTML

Cite as BibTeX
@misc{moran2026nearly,
  title = {Nearly Linear Private Learning of Littlestone Classes},
  author = {Moran, Shay and Yan, Chao},
  year = {2026},
  eprint = {2610.23160},
  archivePrefix = {arXiv},
  primaryClass = {cs.LG},
  doi = {10.48550/arxiv.2610.23160},
  url = {https://arxiv.org/abs/2610.23160}
}

Related