The Power of Factorization Mechanisms in Local and Central Differential Privacy
We give new characterizations of the sample complexity of answering linear queries (statistical queries) in the local and central models of differential privacy: *In the non-interactive local model, we give the first approximate characterization of the sample complexity. Informally our bounds are tight to within polylogarithmic factors in the number of queries and desired accuracy. Our characterization extends to agnostic learning in the local model. *In the central model, we give a characterization of the sample complexity in the high-accuracy regime that is analogous to that of Nikolov, Talwar, and Zhang (STOC 2013), but is both quantitatively tighter and has a dramatically simpler proof. Our lower bounds apply equally to the empirical and population estimation problems. In both cases, our characterizations show that a particular factorization mechanism is approximately optimal, and the optimal sample complexity is bounded from above and below by well studied factorization norms of a matrix associated with the queries.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Assessing differentially private deep learning with Membership Inference
Attacks that aim to identify the training data of public neural networks represent a severe threat to the privacy of individuals participating in the training data set. A possible protection is offered by anonymization o…
Deep LearningInference AttackMembership Inference AttackUniversal Exact Compression of Differentially Private Mechanisms
To reduce the communication cost of differential privacy mechanisms, we introduce a novel construction, called Poisson private representation (PPR), designed to compress and simulate any local randomizer while ensuring l…
(Amplified) Banded Matrix Factorization: A unified approach to private training
Matrix factorization (MF) mechanisms for differential privacy (DP) have substantially improved the state-of-the-art in privacy-utility-computation tradeoffs for ML applications in a variety of scenarios, but in both the …
Federated LearningDecentralized Matrix Factorization with Heterogeneous Differential Privacy
Conventional matrix factorization relies on centralized collection of users' data for recommendation, which might introduce an increased risk of privacy leakage especially when the recommender is untrusted. Existing diff…
Successive Point-of-Interest Recommendation with Local Differential Privacy
A point-of-interest (POI) recommendation system performs an important role in location-based services because it can help people to explore new locations and promote advertisers to launch advertisements at appropriate lo…
Privacy PreservingRecommendation Systems