Interaction is Necessary for Distributed Learning with Privacy or Communication Constraints
| Autor: | Vitaly Feldman, Yuval Dagan |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Statistics and Probability Computer Science - Machine Learning Technology Computer Science - Cryptography and Security Theoretical computer science Computer science Social Sciences Machine Learning (stat.ML) 0102 computer and information sciences 010501 environmental sciences 01 natural sciences Upper and lower bounds Machine Learning (cs.LG) Statistical Queries Statistics - Machine Learning Margin (machine learning) Computer Science - Data Structures and Algorithms Computer Science (miscellaneous) Differential privacy Data Structures and Algorithms (cs.DS) Interactive Protocol Distributed Learning 0105 earth and related environmental sciences Local Differential Privacy Communication-constrained Learning Linear model Lipschitz continuity Computer Science Applications Task (computing) Hyperplane 010201 computation theory & mathematics Convex optimization Cryptography and Security (cs.CR) |
| Zdroj: | The Journal of Privacy and Confidentiality, Vol 11, Iss 2 (2021) STOC |
| ISSN: | 2575-8527 |
| Popis: | Local differential privacy (LDP) is a model where users send privatized data to an untrusted central server whose goal it to solve some data analysis task. In the non-interactive version of this model the protocol consists of a single round in which a server sends requests to all users then receives their responses. This version is deployed in industry due to its practical advantages and has attracted significant research interest. Our main result is an exponential lower bound on the number of samples necessary to solve the standard task of learning a large-margin linear separator in the non-interactive LDP model. Via a standard reduction this lower bound implies an exponential lower bound for stochastic convex optimization and specifically, for learning linear models with a convex, Lipschitz and smooth loss. These results answer the questions posed by Smith, Thakurta, and Upadhyay (IEEE Symposium on Security and Privacy 2017) and Daniely and Feldman (NeurIPS 2019). Our lower bound relies on a new technique for constructing pairs of distributions with nearly matching moments but whose supports can be nearly separated by a large margin hyperplane. These lower bounds also hold in the model where communication from each user is limited and follow from a lower bound on learning using non-adaptive statistical queries. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|