Private PAC learning implies finite Littlestone dimension

lib:dafa92434d8ab837 (v1.0.0)

Authors: Noga Alon,Roi Livni,Maryanthe Malliaris,Shay Moran
ArXiv: 1806.00949
Document:  PDF  DOI
Abstract URL: http://arxiv.org/abs/1806.00949v3

We show that every approximately differentially private learning algorithm (possibly improper) for a class \$H\$ with Littlestone dimension~\$d\$ requires \$\Omega\bigl(\log^*(d)\bigr)\$ examples. As a corollary it follows that the class of thresholds over \$\mathbb{N}\$ can not be learned in a private manner; this resolves open question due to [Bun et al., 2015, Feldman and Xiao, 2015]. We leave as an open question whether every class with a finite Littlestone dimension can be learned by an approximately differentially private algorithm.