New Lower Bounds for Private PAC Learning
Classes with identical VC and Littlestone dimensions can require different amounts of training data under approximate differential privacy.
Prathamesh Dharangutte and Amartya Sanyal show this gap persists even when learners can return hypotheses outside the class being learned. They introduce Independent Class Packing (ICP), a parameter that yields lower bounds on the number of examples required. The framework gives tight lower bounds for axis-aligned rectangles, unions of intervals and linear subspaces, and improves bounds for halfspaces and convex polygons. For product classes and certain other classes satisfying packing and coverage conditions, ICP determines private PAC sample complexity up to logarithmic factors.
ArXiv · AI/CL/LG's note
Prathamesh Dharangutte and Amartya Sanyal show this gap persists even when learners can return hypotheses outside the class being learned. They introduce Independent Class Packing (ICP), a parameter that yields lower bounds on the number of examples required. The framework gives tight lower bounds for axis-aligned rectangles, unions of intervals and linear subspaces, and improves bounds for halfspaces and convex polygons. For product classes and certain other classes satisfying packing and coverage conditions, ICP determines private PAC sample complexity up to logarithmic factors.
ArXiv · AI/CL/LG's note
score 4