New Lower Bounds for Private PAC Learning
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 that can be packed independently into a class , and prove that every -DP, -PAC learner for , possibly improper, uses 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 and cover its domain so that target labels can be used directly, ICP characterizes private PAC sample complexity up to logarithmic factors.
Figures & tables
| Class | Previous lower bound | Our lower bound | Upper bound |
|---|---|---|---|
| Axis-aligned boxes | [ Alon et al., 2022 , Blumer et al., 1989 ] | Theorem 5 | [ Cohen et al., 2023 , Sadigurschi and Stemmer, 2021 ] |
| Unions of intervals | [ Alon et al., 2022 , Blumer et al., 1989 ] | Theorem 5 | Theorem 11 |
| Affine halfspaces | [ Alon et al., 2022 , Blumer et al., 1989 ] | Theorem 5 | [ Karni and Tsfadia, 2026 ] |
| Convex -gons | [ Alon et al., 2022 , Blumer et al., 1989 ] | Theorem 5 | [ Kaplan et al., 2022 ] |
| Linear subspaces | [ Blumer et al., 1989 ] | Theorem 7 | [ Moran and Yan, 2026 ] |
| Unions of tree paths | [ Blumer et al., 1989 ] | Theorem 8 |
PAC Learning
Probably approximately correct (PAC) learning studies when finite samples can yield predictors that generalize with bounded error and confidence.
See all 51 papers