betaFeedback

WorksComputer Science

New Lower Bounds for Private PAC Learning

Abstract

We study realizable PAC learning under approximate differential privacy, and give a framework for proving lower bounds on its sample complexity. We construct classes with identical VC and Littlestone dimensions but different private sample complexities at common privacy and accuracy parameters, showing that these dimensions do not determine the sample complexity, even for improper learners. To address this we introduce the Independent Class Packing (ICP) parameter, the largest total sample complexity of classes in G\mathcal{G} that can be packed independently into a class H\mathcal{H}, and prove that every (ε,δ)(\varepsilon, δ)-DP, (α,β)(α, β)-PAC learner for H\mathcal{H}, possibly improper, uses Ω(ICP(H,G)/(αε))Ω\left(\mathrm{ICP}(\mathcal{H}, \mathcal{G})/(α\varepsilon)\right) examples. Using this framework we prove tight lower bounds for axis-aligned rectangles, union of intervals and linear subspaces and improved lower bounds for halfspaces and convex polygons. Finally we also show that for product classes, and more generally when the same classes pack into H\mathcal{H} and cover its domain so that target labels can be used directly, ICP characterizes private PAC sample complexity up to logarithmic factors.

Introduction

A learning algorithm trained using sensitive data should not reveal much about any individual example. Differential privacy (DP) [12, 13] makes this requirement precise; private PAC learning [20] asks how many examples a PAC learner needs when its output must also satisfy DP. Privacy can make learning substantially more expensive, and a central question is which properties of a hypothesis class determine this cost. Without privacy, the sample complexity of PAC learning is characterised by the VC dimension [5]. In their seminal result, Alon et al. [2] showed that under approximate differential privacy, a class is learnable if and only if its Littlestone dimension is finite. This settled the qualitative question of when a hypothesis class is privately learnable. However, the known upper and lower bounds on the private sample complexity in terms of the VC and Littlestone dimensions are far apart.

We study realizable PAC learning [32] and allow improper learners. Let H⊆{0,1}X\mathcal{H} \subseteq\{0,1\}^{\mathcal{X}}. An nn-sample learner receives nn i.i.d. examples {(xi,h⋆(xi))}i=1n\{(x_i,h^\star(x_i))\}_{i=1}^n, where h⋆∈Hh^\star\in\mathcal{H}, and outputs a Boolean function. It is an (α,β)(\alpha,\beta)-PAC learner if its population error is at most α\alpha with probability at least 1−β1-\beta uniformly over all h⋆h^\star and all distributions. It is (ε,δ)(\varepsilon,\delta)-DP if, for all samples S,S′S,S' of size nn that differ in one example, and every event EE,

Pr⁡[M(S)∈E]≤eεPr⁡[M(S′)∈E]+δ.\Pr[\mathcal{M}(S)\in E]\leq e^\varepsilon\Pr[\mathcal{M}(S')\in E]+\delta.

We write mpriv(H;ε,δ,α,β)m_{\mathrm{priv}}(\mathcal{H};\varepsilon,\delta,\alpha,\beta) for the smallest sample size a learner satisfying both conditions needs. Let v=VC⁡(H)v=\operatorname{VC}(\mathcal{H}) and D=LDim⁡(H)D=\operatorname{LDim}(\mathcal{H}), and let log⁡∗x\log^* x be the iterated logarithm i.e., the number of base-two logarithms needed to bring xx below two. For constant privacy and utility parameters, the best known general lower bound is Ω(v+log⁡∗D)\Omega(v+\log^* D) [2, 5]. A recent work by Moran and Yan [27] gives the best known general upper bound, O(Dlog⁡D)O(D\log D). Finding a combinatorial characterization that closes this gap is a central open problem, recently restated by Nissim et al. [28].

Lower bounds for private learning are typically proved in one of two ways. The first finds a simple problem hidden inside the larger class such that we know a lower bound on the sample complexity of the simple problem, and argues that every learner for the larger class must require it. For example, Alon et al. [2] use a threshold class. By a quantitative form of Shelah’s theorem, every class of Littlestone dimension DD contains a threshold class of length about log⁡D\log D, and privately learning thresholds on NN points requires Ω(log⁡∗N)\Omega(\log^* N) examples, which gives their bound Ω(log⁡∗D)\Omega(\log^* D). The second measures how many hypotheses are needed to represent the class to realise a packing style bound. Beimel et al. [4] introduced probabilistic representations and the associated probabilistic representation dimension PRDim. Roughly this measures how compactly a class can be represented by random sets of hypotheses and they showed that every purely private learner needs Ω(PRDim⁡(H)/(αε))\Omega(\operatorname{PRDim}(\mathcal{H})/(\alpha\varepsilon)) examples. Feldman and Xiao [14] related PRDim to randomized one-way communication complexity. They showed that PRDim is at least of the order of the Littlestone dimension but can be much larger, e.g. the class of lines over Zp2\mathbb{Z}_p^2 has Littlestone dimension 2 and representation dimension Θ(log⁡p)\Theta(\log p). They also gave an approximate-private learner for this class whose sample complexity, for fixed privacy and utility parameters, does not depend on pp. Thus, approximate privacy can be much cheaper than pure privacy. Nevertheless, PRDim still gives a lower bound under approximate privacy but only up to log⁡(1/δ)\log(1/\delta): the journal version of Beimel et al. [4] gives Ω(min⁡{PRDim⁡(H),log⁡(ε/δ)}/(αε))\Omega(\min\{\operatorname{PRDim}(\mathcal{H}),\log(\varepsilon/\delta)\}/(\alpha\varepsilon)). At constant accuracy, Ghazi et al. [16] prove a bound of the same form in the more general setting of user-level privacy. Additionally, the non-private VC lower bound also applies to private learners. Combined with the threshold lower bound, it gives the general lower bound Ω(v+log⁡∗D)\Omega(v+\log^* D).

Many natural classes contain several hard learning problems on disjoint parts of their domain. These problems are independent when every combination of their target concepts can be realized by a single hypothesis of the larger class. The bounds above need not capture their combined private learning cost. This is the main observation our lower bound leverages. We express this bound through the Independent Class Packing parameter ICP(H,G)(\mathcal{H},\mathcal{G}). For a collection G\mathcal{G} of classes, ICP(H,G)(\mathcal{H},\mathcal{G}) is the largest sum of the sample complexities, at constant accuracy, of classes from G\mathcal{G} that can be packed independently in H\mathcal{H}. Our proof reduces the private learning of H\mathcal{H} to learning the packed classes and establishes an additive lower bound on the required sample size. The hard problems used in earlier lower bounds provide the packed classes. Packing thresholds of length LL adds the cost Ω(log⁡∗L)\Omega(\log^* L) for each packed threshold class, and for small δ\delta, packing classes with a large representation dimension adds the bound of Beimel et al. [4] across these classes.

For the parameters that characterize other learning models, additivity over independent parts is often direct. For independently packed classes G1,…,Gk\mathcal{G}_1,\ldots,\mathcal{G}_k in H\mathcal{H}, the VC dimension satisfies VC⁡(H)≥∑iVC⁡(Gi)\operatorname{VC}(\mathcal{H}) \ge\sum_i \operatorname{VC}(\mathcal{G}_i), so the corresponding non-private lower bounds add. Similarly, LDim⁡(H)≥∑iLDim⁡(Gi)\operatorname{LDim}(\mathcal{H}) \ge\sum_i \operatorname{LDim}(\mathcal{G}_i), giving additive lower bounds for online learning. For private learning, however, the known Littlestone-based lower bound depends on log⁡∗LDim⁡(H)\log^*\operatorname{LDim}(\mathcal{H}). Assume LDim⁡(Gi)=D\operatorname{LDim}(\mathcal{G}_i)=D for all ii. Using only this inequality in the known private lower bound gives Ω(log⁡∗(kD))\Omega(\log^*(kD)), rather than the sum Ω(klog⁡∗D)\Omega(k\log^*D). Our framework establishes an additive lower bound directly in terms of the packed classes’ private learning costs.

Our contributions.

We first show that the VC and Littlestone dimensions do not determine the private sample complexity of a class as two classes with the same VC and Littlestone dimensions can have different private sample complexities. The underlying reason is that the cost of private learning adds up over independent hard problems inside a class in a way that existing bounds do not capture. The ICP parameter captures this. It gives a lower bound for every class, and this lower bound is tight up to logarithmic factors for several natural classes. All our lower bounds hold for improper learners.

A separation at equal VC and LDim. For every 1≤v≤D1\leq v\leq D, we construct classes Pv,D\mathcal{P}_{v,D} and Uv,D\mathcal{U}_{v,D}, both with dimensions (v,D)(v,D), such that for the same privacy and utility parameters

mpriv(Pv,D)=Θ~(vlog⁡∗(max⁡{2,D/v})),m_{\mathrm{priv}}(\mathcal{P}_{v,D})=\widetilde{\Theta}\left(v\log^{*}(\max\{2,D/v\})\right),
mpriv(Uv,D)=Θ~(v+log⁡∗D).m_{\mathrm{priv}}(\mathcal{U}_{v,D})=\widetilde{\Theta}\left(v+\log^{*}D\right).

Here Θ~\widetilde{\Theta} hides factors polylogarithmic in the rates (see Theorem 3 for full details). Taking v=log⁡∗Dv=\log^{*}D, the sample complexities differ by Ω~(log⁡∗D)\widetilde{\Omega}(\log^{*}D), so no function of (v,D)(v,D) can determine the private sample complexity up to polylogarithmic factors. However, this does not rule out an upper bound poly⁡(v,log⁡∗D)\operatorname{poly}(v,\log^{*}D) that holds for every class.

A stronger lower bound. We propose the Independent Class Packing (ICP) parameter in Definition 2. Our main result, Theorem 1, shows that all (ε,δ)(\varepsilon,\delta)-DP, (α,β)(\alpha,\beta)-PAC learner of H\mathcal{H} requires

n=Ω(ICP⁡0.1,δ/ε(H,G)εα)n=\Omega\left(\frac{\operatorname{ICP}_{0.1,\delta/\varepsilon}(\mathcal{H},\mathcal{G})}{\varepsilon\alpha}\right)

samples.

If H∈G\mathcal{H}\in\mathcal{G}, the one-component packing of H\mathcal{H} into itself only compares its sample complexity at different privacy and accuracy parameters. The interesting regime is when G\mathcal{G} is restricted to simple classes with known sample complexity, such as thresholds, so that packing several of them into H\mathcal{H} gives explicit lower bounds that add over the packed classes. The strength of these bounds therefore depends on what is known about the sample complexity of the packed classes, and any improved lower bound for a simple class immediately gives improved lower bounds for every class into which several copies of it can be packed.

This lower bound matches the upper bounds for Pv,D\mathcal{P}_{v,D} and Uv,D\mathcal{U}_{v,D}, up to logarithmic factors, via packing thresholds. For Pv,D\mathcal{P}_{v,D}, the packing contains all threshold components, so their sample complexities add in ICP. For Uv,D\mathcal{U}_{v,D}, the Boolean and the threshold components cannot be packed independently together. The separate VC and threshold lower bound already give v+log⁡∗Dv + \log^* D which matches the upper bound § 3. More generally, let G≤1\mathcal{G}_{\leq1} be the collection of all VC =1= 1 classes (for example thresholds). Then we have that for every class H\mathcal{H} with VC dimension vv and Littlestone dimension DD,

Ω(v+log⁡∗D)≲ICP⁡0.1,δ/ε(H,G≤1)≲O~(vlog⁡∗(D/v)).(1)\Omega(v+\log^*D)\lesssim\operatorname{ICP}_{0.1,\delta/\varepsilon}(\mathcal{H},\mathcal{G}_{\leq1})\lesssim\widetilde{O}\left(v\log^*(D/v)\right). \tag*{(1)}

Applications to natural classes. The packing idea applies well beyond Pv,D\mathcal{P}_{v,D} and Uv,D\mathcal{U}_{v,D}. A simple packing also gives multiplicative lower bounds for (i) axis-aligned boxes, (ii) affine halfspaces on finite grids, (iii) unions of intervals, and (iv) convex polygons in the plane. For boxes on [N]d[N]^d we obtain Ω(dlog⁡∗N)\Omega(d\log^*N), and for unions of kk intervals on [N][N] we obtain Ω(klog⁡∗(N/k))\Omega(k\log^*(N/k)). These improve the earlier bounds Ω(d+log⁡∗N)\Omega(d+\log^*N) and Ω(k+log⁡∗N)\Omega(k+\log^*N), respectively. They match the known upper bound for boxes and our upper bound for unions of intervals, up to logarithmic factors. Resolving the gap for halfspaces and polygons remains open.

For small δ\delta, we also add the representation-dimension lower bound of Beimel et al. [4], Ghazi et al. [16] across packed classes. At fixed ε,α,β\varepsilon,\alpha,\beta, this bound contributes at most O(log⁡(1/δ))O(\log(1/\delta)) when applied to the whole class, whereas each packed class can contribute this amount. Packing lines into linear subspaces and paths into unions of tree paths gives Ω(dlog⁡(1/δ))\Omega(d\log(1/\delta)), improving the Ω(d)\Omega(d) bounds from VC. The subspace bound is tight. For unions of paths, it is tight when log⁡(1/δ)=Θ(k)\log(1/\delta)=\Theta(k). In this regime, packing paths gives Ω(dk)\Omega(dk), whereas every threshold packing yields a lower bound of at most O(dlog⁡(k+1))O(d\log(k+1)) through ICP (Lemma 14). Thus the improvement over threshold packings grows without bound with kk. Table 1 summarizes the bounds for these six classes.

References

  1. [1]Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. Closure properties for private classification and online prediction. In Proceedings of the 33rd Conference on Learning Theory, 2020.arxiv.org/abs/2003.04509
  2. [2]Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran. Private and online learnability are equivalent. Journal of the ACM, 2022.DOI
  3. [3]Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. In Advances in Neural Information Processing Systems, 2018.arxiv.org/abs/1807.01647
  4. [4]Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of pure private learners. Journal of Machine Learning Research, 2019.
  5. [5]Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Learnability and the Vapnik–Chervonenkis dimension. Journal of the ACM, 1989.DOI
  6. [6]Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan. Differentially private release and learning of threshold functions. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, 2015.arxiv.org/abs/1504.07553
  7. [7]Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultaneous private learning of multiple concepts. In Proceedings of the 7th Innovations in Theoretical Computer Science Conference, 2016.
  8. [8]Mark Bun, Roi Livni, and Shay Moran. An equivalence between private classification and online prediction. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science, 2020.arxiv.org/abs/2003.00563
  9. [9]Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Optimal differentially private learning of thresholds and quasi-concave optimization. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023.arxiv.org/abs/2211.06387
  10. [10]Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Lower bounds for differential privacy under continual observation and online threshold queries. In Proceedings of the 37th Conference on Learning Theory, 2024.arxiv.org/abs/2403.00028
  11. [11]Daniil Dmitriev, Kristóf Szabó, and Amartya Sanyal. On the growth of mistakes in differentially private online learning: A lower bound perspective. In Proceedings of the 37th Conference on Learning Theory, 2024.arxiv.org/abs/2402.16778
  12. [12]Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology—EUROCRYPT 2006, 2006.
  13. [13]Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, 2006.
  14. [14]Vitaly Feldman and David Xiao. Sample complexity bounds on differentially private learning via communication complexity. In Proceedings of the 27th Conference on Learning Theory, 2014.arxiv.org/abs/1402.6278
  15. [15]Badih Ghazi, Noah Golowich, Ravi Kumar, and Pasin Manurangsi. Sample-efficient proper PAC learning with approximate differential privacy. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021.arxiv.org/abs/2012.03893
  16. [16]Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. User-level differentially private learning via correlated sampling. In Advances in Neural Information Processing Systems, 2021.
  17. [17]Noah Golowich and Roi Livni. Littlestone classes are privately online learnable. In Advances in Neural Information Processing Systems, 2021.arxiv.org/abs/2106.13513
  18. [18]Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Differentially private learning of geometric concepts. SIAM Journal on Computing, 2022.arxiv.org/abs/1902.05017
  19. [19]Dvir Karni and Eliad Tsfadia. Private component-by-component learning. arXiv preprint, 2026.arxiv.org/abs/2610.05102
  20. [20]Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 2011.
  21. [21]Bo Li, Wei Wang, and Peng Ye. The limits of differential privacy in online learning. In Advances in Neural Information Processing Systems, 2024.arxiv.org/abs/2411.05483
  22. [22]Bo Li, Wei Wang, and Peng Ye. Private online learning against an adaptive adversary: Realizable and agnostic settings. In Advances in Neural Information Processing Systems, 2025.
  23. [23]Yi Li, Philip M. Long, and Aravind Srinivasan. The one-inclusion graph algorithm is near-optimal for the prediction model of learning. IEEE Trans. Inf. Theory, 2001.DOI
  24. [24]Xin Lyu. Private learning of Littlestone classes, revisited. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026.
  25. [25]Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007.
  26. [26]Hugh L. Montgomery and Robert C. Vaughan. Hilbert’s inequality. Journal of the London Mathematical Society, 1974.DOI
  27. [27]Shay Moran and Chao Yan. Nearly linear private learning of Littlestone classes. arXiv preprint, 2026.arxiv.org/abs/2610.23160
  28. [28]Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia. Invited open problem: Does differential privacy make PAC learning much harder? In Proceedings of the 39th Conference on Learning Theory, 2026.
  29. [29]Menachem Sadigurschi and Uri Stemmer. On the sample complexity of privately learning axis-aligned rectangles. In Advances in Neural Information Processing Systems, 2021.arxiv.org/abs/2107.11526
  30. [30]Amartya Sanyal. Private online learning and prediction for Littlestone classes. arXiv preprint, 2026.arxiv.org/abs/2610.06822
  31. [31]Satchit Sivakumar, Mark Bun, and Marco Gaboardi. Multiclass versus binary differentially private PAC learning. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, 2021.
  32. [32]Leslie G. Valiant. A theory of the learnable. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 1984.
  33. [33]Chao Yan. An Õptimal differentially private PAC learner for concept classes with VC dimension 1. arXiv preprint, 2025.arxiv.org/abs/2505.06581

Paper details

vlnc:W_8n2udubv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus 5.5 (bare), GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents