A Computational Separation Between Private Learning and Online Learning

Abstract

A recent line of work has shown a qualitative equivalence between differentially private PAC learning and online learning: A concept class is privately learnable if and only if it is online learnable with a finite mistake bound. However, both directions of this equivalence incur significant losses in both sample and computational efficiency. Studying a special case of this connection, Gonen, Hazan, and Moran (NeurIPS 2019) showed that uniform or highly sample-efficient pure-private learners can be time-efficiently compiled into online learners. We show that, assuming the existence of one-way functions, such an efficient conversion is impossible even for general pure-private learners with polynomial sample complexity. This resolves a question of Neel, Roth, and Wu (FOCS 2019).

PDF NeurIPS Semantic Scholar

Cite

Text

Bun. "A Computational Separation Between Private Learning and Online Learning." Neural Information Processing Systems, 2020.

Markdown

[Bun. "A Computational Separation Between Private Learning and Online Learning." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/bun2020neurips-computational/)

BibTeX

@inproceedings{bun2020neurips-computational,
  title     = {{A Computational Separation Between Private Learning and Online Learning}},
  author    = {Bun, Mark},
  booktitle = {Neural Information Processing Systems},
  year      = {2020},
  url       = {https://mlanthology.org/neurips/2020/bun2020neurips-computational/}
}