arXiv preprint ·
New Lower Bounds for Private PAC Learning
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\mathcal{G}$ that can be packed independently into a class $\mathcal{H}$, and prove that every $(\varepsilon, δ)$-DP, $(α, β)$-PAC learner for $\mathcal{H}$, possibly improper, uses $Ω\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 $\mathcal{H}$ and cover its domain so that target labels can be used directly, ICP characterizes private PAC sample complexity up to logarithmic factors.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
MUON-RT Reusing the Teacher's Trajectory for Momentum-Free Muon for LLM Self-Distillation
Ensemble Classification and Cancer-Specific Gene Signatures from Quality-Aware Hybrid Gene Selection in TCGA RNA-Seq data
Differential rank preservation manifold learning
Where Causal Discovery Breaks on Real Data: Measuring the Assumptions One Property at a Time
TalentRL: Strategy-Guided Reinforcement Learning for Hierarchical Skill Routing
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.