cs.LGOct 30, 2026

New Lower Bounds for Private PAC Learning

Authors: Prathamesh Dharangutte, Amartya Sanyal

Organizations: Department of Computer Science, University of Copenhagen

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.

Figures & tables

Explore similar work

Oct 16, 2026

Nearly Linear Private Learning of Littlestone Classes

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 dd, the first general upper bound was doubly exponential in dd (Bun, Livni, and Moran, FOCS 2020). Subsequent work improved this to O~(d6)\widetilde O(d^6) (Ghazi et al., STOC 2021) and then to O~(d5)\widetilde O(d^5) (Lyu, STOC 2026). We prove a nearly linear upper bound of O(dlog⁡d)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 dd over any field, with tight linear dependence on dd 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.
Oct 4, 2026

Private Component-by-Component Learning

We study differentially private learning problems in the realizable setting, where a hypothesis is specified by kk components. A direct iteration of private component learners is obstructed by a simple difficulty: an approximate choice of the next component may destroy exact realizability of the labeled sample, even when the next component is locally accurate. We restore realizability using the LabelBoost procedure of Beimel, Nissim, and Stemmer [SODA '15, Algorithmica '21] and recycle data through two alternating reservoirs. The resulting learner, for a target privacy ε\varepsilon, pays only O~(k/ε)\widetilde O(\sqrt{k}/\varepsilon) overhead relative to the active sample requirement of a single component learning step at target accuracy Θ(α/k)Θ(α/k). For learning dd-dimensional halfspaces over a finite coordinate grid of size LL, exact realizability makes the direct component-depth objective quasi-concave. Instantiating the framework with the IPConcave algorithm of Nissim, Tsfadia, and Yan [SODA '26] and with the quasi-concave optimizer of Cohen, Lyu, Nelson, Sarl'os, and Stemmer [STOC '23] yields a realizable sample complexity of O~(1εα⋅min⁡{d2.5log⁡∗L,  d2.5+d1.52log⁡∗L}),\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot \min\{d^{2.5} \log^*L, \:\: d^{2.5} + d^{1.5} 2^{\log^*L}\}\right), which improves on the previously known bound of O~(1εα⋅min⁡{1α⋅d5.5log⁡∗L,  d2.52log⁡∗L}).\widetilde{O}\left(\frac{1}{\varepsilon α}\cdot\min\{\frac{1}α\cdot d^{5.5}\log^*L,\:\: d^{2.5}2^{\log^*L}\}\right). We also apply the framework to Boolean compositions: given proper private learners for classes H1,…,HkH_1,\ldots,H_k, we obtain a proper private learner for G(H1,…,Hk)G(H_1,\ldots,H_k) for any fixed Boolean function G:{0,1}k→{0,1}G:\{0,1\}^k\to\{0,1\}. Compared with the closure theorem of Alon, Beimel, Moran, and Stemmer [COLT '20], this reduces the overhead on a common component sample bound from O~(k/ε)\widetilde O(k/\varepsilon) to O~(k/ε)\widetilde O(\sqrt{k}/\varepsilon).
Oct 5, 2026

Private online learning and prediction for Littlestone classes

We study mistake bounds for differentially private online learning and online prediction under oblivious realisable adversaries. Online learning requires the learner to release a hypothesis at each time step whereas in online prediction, the learner only needs to make predictions without releasing a hypothesis. Using a novel lower bound for private online learning and an upper bound for private prediction, we show that the sample complexity of these two problems are separated by a factor that grows with the time horizon for every class of finite Littlestone dimension dd. First, we prove that every (ε,δ)(ε,δ)-private online learner has a deterministic realisable stream of length TT on which the mistake bound is at least E[MT]=O(dεlog⁡2/3T)\mathbb E [M_T]= O\left(\frac dε\log^{2/3} T\right). In particular, this is the first non-trivial lower in the range 1/T<δ<1/log⁡T)1/T<δ<1/\log T) left open in earlier works[SR22,DSS24,LWY24]. Second, we prove that for every class of of Littlestone dimension dd, there exists an (ε,δ)(ε,δ)-jointly private predictor with at most 22cd2ε−2log⁡2(2/(εδ))2^{2^{cd^2}}ε^{-2}\log^2(2/(εδ)) expected mistakes, independently of TT, for some absolute constant c>0c>0. Thus, for every fixed class of finite Littlestone dimension when δ=Θ(1/log⁡T)δ=Θ(1/\log T), private learning requires O(log⁡2/3T)O\left(\log^{2/3} T\right) expected mistakes, whereas private prediction admits O(log⁡log⁡T2)O(\log\log T^2).