Is Interaction Necessary for Distributed Private Learning?

Adam Smith, Abhradeep Thakurta, Jalaj Upadhyay

Research output: Chapter in Book/Report/Conference proceedingConference contribution

119 Scopus citations

Abstract

Recent large-scale deployments of differentially private algorithms employ the local model for privacy (sometimes called PRAM or randomized response), where data are randomized on each individual's device before being sent to a server that computes approximate, aggregate statistics. The server need not be trusted for privacy, leaving data control in users' hands. For an important class of convex optimization problems (including logistic regression, support vector machines, and the Euclidean median), the best known locally differentially-private algorithms are highly interactive, requiring as many rounds of back and forth as there are users in the protocol. We ask: how much interaction is necessary to optimize convex functions in the local DP model? Existing lower bounds either do not apply to convex optimization, or say nothing about interaction. We provide new algorithms which are either noninteractive or use relatively few rounds of interaction. We also show lower bounds on the accuracy of an important class of noninteractive algorithms, suggesting a separation between what is possible with and without interaction.

Original languageEnglish (US)
Title of host publication2017 IEEE Symposium on Security and Privacy, SP 2017 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages58-77
Number of pages20
ISBN (Electronic)9781509055326
DOIs
StatePublished - Jun 23 2017
Event2017 IEEE Symposium on Security and Privacy, SP 2017 - San Jose, United States
Duration: May 22 2017May 24 2017

Publication series

NameProceedings - IEEE Symposium on Security and Privacy
ISSN (Print)1081-6011

Other

Other2017 IEEE Symposium on Security and Privacy, SP 2017
Country/TerritoryUnited States
CitySan Jose
Period5/22/175/24/17

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Software
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Is Interaction Necessary for Distributed Private Learning?'. Together they form a unique fingerprint.

Cite this