Breaking the Communication-Privacy-Accuracy Trilemma
- URL: http://arxiv.org/abs/2007.11707v3
- Date: Tue, 20 Apr 2021 19:13:09 GMT
- Title: Breaking the Communication-Privacy-Accuracy Trilemma
- Authors: Wei-Ning Chen, Peter Kairouz, Ayfer \"Ozg\"ur
- Abstract summary: Two major challenges in distributed learning are preserving the privacy of local samples and communicating them efficiently to a central server.
We develop novel encoding and decoding mechanisms that simultaneously achieve optimal privacy and communication efficiency.
- Score: 19.399122892615573
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Two major challenges in distributed learning and estimation are 1) preserving
the privacy of the local samples; and 2) communicating them efficiently to a
central server, while achieving high accuracy for the end-to-end task. While
there has been significant interest in addressing each of these challenges
separately in the recent literature, treatments that simultaneously address
both challenges are still largely missing. In this paper, we develop novel
encoding and decoding mechanisms that simultaneously achieve optimal privacy
and communication efficiency in various canonical settings.
In particular, we consider the problems of mean estimation and frequency
estimation under $\varepsilon$-local differential privacy and $b$-bit
communication constraints. For mean estimation, we propose a scheme based on
Kashin's representation and random sampling, with order-optimal estimation
error under both constraints. For frequency estimation, we present a mechanism
that leverages the recursive structure of Walsh-Hadamard matrices and achieves
order-optimal estimation error for all privacy levels and communication
budgets. As a by-product, we also construct a distribution estimation mechanism
that is rate-optimal for all privacy regimes and communication constraints,
extending recent work that is limited to $b=1$ and $\varepsilon=O(1)$. Our
results demonstrate that intelligent encoding under joint privacy and
communication constraints can yield a performance that matches the optimal
accuracy achievable under either constraint alone.
Related papers
- Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures [5.513958040574729]
We develop a robust decentralized saddle-point algorithm against random link failures with heterogeneous probabilities.
We extend our algorithm and analysis to the two-point bandit feedback scenario.
arXiv Detail & Related papers (2024-01-04T00:57:33Z) - Optimal Private Discrete Distribution Estimation with One-bit Communication [63.413106413939836]
We consider a private discrete distribution estimation problem with one-bit communication constraint.
We characterize the first-orders of the worst-case trade-off under the one-bit communication constraint.
These results demonstrate the optimal dependence of the privacy-utility trade-off under the one-bit communication constraint.
arXiv Detail & Related papers (2023-10-17T05:21:19Z) - Differential Privacy via Distributionally Robust Optimization [8.409434654561789]
We develop a class of mechanisms that enjoy non-asymptotic and unconditional optimality guarantees.
Our upper (primal) bounds correspond to implementable perturbations whose suboptimality can be bounded by our lower (dual) bounds.
Our numerical experiments demonstrate that our perturbations can outperform the previously best results from the literature on artificial as well as standard benchmark problems.
arXiv Detail & Related papers (2023-04-25T09:31:47Z) - Breaking the Communication-Privacy-Accuracy Tradeoff with
$f$-Differential Privacy [51.11280118806893]
We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability.
We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP)
More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
arXiv Detail & Related papers (2023-02-19T16:58:53Z) - Decentralized Nonconvex Optimization with Guaranteed Privacy and
Accuracy [34.24521534464185]
Privacy protection and nonity are two challenging problems in decentralized optimization learning sensitive data.
We propose an algorithm that allows both privacy protection and avoidance.
The algorithm is efficient in both communication and computation.
arXiv Detail & Related papers (2022-12-14T22:36:13Z) - Quantization for decentralized learning under subspace constraints [61.59416703323886]
We consider decentralized optimization problems where agents have individual cost functions to minimize subject to subspace constraints.
We propose and study an adaptive decentralized strategy where the agents employ differential randomized quantizers to compress their estimates.
The analysis shows that, under some general conditions on the quantization noise, the strategy is stable both in terms of mean-square error and average bit rate.
arXiv Detail & Related papers (2022-09-16T09:38:38Z) - On Differential Privacy for Federated Learning in Wireless Systems with
Multiple Base Stations [90.53293906751747]
We consider a federated learning model in a wireless system with multiple base stations and inter-cell interference.
We show the convergence behavior of the learning process by deriving an upper bound on its optimality gap.
Our proposed scheduler improves the average accuracy of the predictions compared with a random scheduler.
arXiv Detail & Related papers (2022-08-25T03:37:11Z) - Robust and Differentially Private Mean Estimation [40.323756738056616]
Differential privacy has emerged as a standard requirement in a variety of applications ranging from the U.S. Census to data collected in commercial devices.
An increasing number of such databases consist of data from multiple sources, not all of which can be trusted.
This leaves existing private analyses vulnerable to attacks by an adversary who injects corrupted data.
arXiv Detail & Related papers (2021-02-18T05:02:49Z) - Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
Local exchange of estimates allows inference of data based on private data.
perturbations chosen independently at every agent, resulting in a significant performance loss.
We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
arXiv Detail & Related papers (2020-10-23T10:35:35Z) - Differential Privacy of Hierarchical Census Data: An Optimization
Approach [53.29035917495491]
Census Bureaus are interested in releasing aggregate socio-economic data about a large population without revealing sensitive information about any individual.
Recent events have identified some of the privacy challenges faced by these organizations.
This paper presents a novel differential-privacy mechanism for releasing hierarchical counts of individuals.
arXiv Detail & Related papers (2020-06-28T18:19:55Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.