The authors study the sample complexity of approximately differentially private PAC learning.
Nearly linear sample complexity suffices for private learning of Littlestone classes
Moran and Yan improve the approximate private PAC learning sample bound from O~(d^5) to O(d log d), with a tight linear bound for subspace indicators.
Big Tech
Shay Moran · Chao Yan
Technion - Israel Institute of Technology · Google Research
Research Digest··3 min read
Shay Moran and Chao Yan prove that any binary concept class with Littlestone dimension d can be learned under approximate differential privacy using O(d log d) examples, nearly matching the lower bound of Omega(d) when VC dimension is maximal.
§