← All AI/ML open problems

Statistical learning theory · AI safety & alignment · Privacy & encrypted learning / Open question

The Price of Privacy

Privacy is known to cost samples. The unresolved issue is how large that cost can become compared with the intrinsic statistical difficulty of learning.

OpenEditorially scopedSpecified modelCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

Can approximate differential privacy make finite-class PAC learning dramatically harder? Find a sequence of finite concept classes CκC_\kappa with ∣Cκ∣→∞|C_\kappa|\to\infty and log⁡∣Cκ∣\log|C_\kappa| superpolynomial in VC(Cκ)\mathrm{VC}(C_\kappa), for which every approximate-private PAC learner needs Ω(log⁡∣Cκ∣)\Omega(\log|C_\kappa|) samples, or rule out such a separation. This is the concrete second question of Nissim, Stemmer and Tsfadia at COLT 2026.

Assumptions and scope

  • Use realizable distribution-independent PAC learning at fixed nontrivial accuracy and confidence; specify whether hypotheses may be improper, and do not obtain an unrestricted lower bound by restricting to proper learners.
  • Use approximate (epsilon, delta)-DP with constant epsilon and a declared delta schedule much smaller than inverse sample size. Pure DP is a different, partly characterized problem.
  • Separate information-theoretic sample complexity from computational efficiency; state all hidden dependence on privacy and learning parameters.

What would settle it?

A finite-class family with the proposed sample separation, a universal upper bound excluding it, or a substantially sharper characterization in terms of VC and Littlestone dimensions with the weaker scope stated.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

Private learnability is characterized by finite Littlestone dimension; some privacy overhead and special-class bounds are known. The COLT paper's fifth-power Littlestone upper bound is superseded by Moran and Yan's October 2026 claimed O(d log d) bound. That improvement does not itself settle the proposed log-cardinality versus VC separation. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Nissim, Stemmer and Tsfadia — Does Differential Privacy Make PAC Learning Much Harder? ↗problem statement · source checked 2026-11-19

    PDF Section 2, Questions 1–2 checked: approximate DP, fixed learning/privacy constants with delta much smaller than inverse dataset size; asks finite class families with log-cardinality superpolynomial in VC dimension but private sample complexity Omega(log-cardinality). Known privacy overhead and pure-DP characterizations are not open.

  2. Bun, Livni and Moran — An Equivalence Between Private Classification and Online Prediction ↗partial theory · source checked 2026-11-19

    Metadata and the COLT 2026 account checked: finite Littlestone dimension characterizes approximate-private PAC learnability, but does not by itself give tight quantitative sample complexity.

  3. Moran and Yan — Nearly Linear Private Learning of Littlestone Classes ↗partial theory · source checked 2026-11-19

    Primary abstract checked: October 2026 preprint claims O(d log d) dependence on Littlestone dimension d, improving the earlier fifth-power bound. Learning/privacy-parameter dependence and the proof were not independently audited.