### Abstract

We show that every approximately differentially private learning algorithm (possibly improper) for a class H with Littlestone dimension d requires Ωlog^{∗}(d) examples. As a corollary it follows that the class of thresholds over N can not be learned in a private manner; this resolves open questions due to [Bun et al. 2015] and [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.

Original language | English (US) |
---|---|

Title of host publication | STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Moses Charikar, Edith Cohen |

Publisher | Association for Computing Machinery |

Pages | 852-860 |

Number of pages | 9 |

ISBN (Electronic) | 9781450367059 |

DOIs | |

State | Published - Jun 23 2019 |

Event | 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States Duration: Jun 23 2019 → Jun 26 2019 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 |
---|---|

Country | United States |

City | Phoenix |

Period | 6/23/19 → 6/26/19 |

### All Science Journal Classification (ASJC) codes

- Software

### Keywords

- Differential Privacy
- Littlestone dimension
- PAC learning

## Fingerprint Dive into the research topics of 'Private PAC learning implies finite littlestone dimension'. Together they form a unique fingerprint.

## Cite this

Alon, N., Livni, R., Malliaris, M., & Moran, S. (2019). Private PAC learning implies finite littlestone dimension. In M. Charikar, & E. Cohen (Eds.),

*STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing*(pp. 852-860). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3313276.3316312