Show simple item record

dc.contributor.authorBun, Marken_US
dc.date.accessioned2021-10-28T17:16:53Z
dc.date.available2021-10-28T17:16:53Z
dc.date.issued2020-12-06
dc.identifier.citationM. Bun. 2020. "A computational separation between private learning and online learning." Neural Information Processing Systems (NeurIPS) https://arxiv.org/abs/2007.05665
dc.identifier.urihttps://hdl.handle.net/2144/43233
dc.description.abstractA 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).en_US
dc.description.urihttps://arxiv.org/abs/2007.05665
dc.language.isoen_US
dc.titleA computational separation between private learning and online learningen_US
dc.typeConference materialsen_US
pubs.elements-sourcemanual-entryen_US
pubs.organisational-groupBoston Universityen_US
pubs.organisational-groupBoston University, College of Arts & Sciencesen_US
pubs.organisational-groupBoston University, College of Arts & Sciences, Department of Computer Scienceen_US
pubs.publication-statusPublisheden_US
dc.identifier.mycv617012


This item appears in the following Collection(s)

Show simple item record