Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation
This work addresses bottlenecks in federated learning and analytics by providing optimal algorithms for privacy-accuracy-communication trade-offs, which is incremental but practically relevant.
The paper tackles the problem of optimizing privacy, accuracy, and communication trade-offs in distributed mean and frequency estimation for federated learning and analytics, showing that compression can reduce client communication bits to Θ(n min(ε, ε²)) for mean estimation and Θ(log(n min(ε, ε²))) for frequency estimation, achieving significant savings when n min(ε, ε²) = o(d).
Privacy and communication constraints are two major bottlenecks in federated learning (FL) and analytics (FA). We study the optimal accuracy of mean and frequency estimation (canonical models for FL and FA respectively) under joint communication and $(\varepsilon, δ)$-differential privacy (DP) constraints. We show that in order to achieve the optimal error under $(\varepsilon, δ)$-DP, it is sufficient for each client to send $Θ\left( n \min\left(\varepsilon, \varepsilon^2\right)\right)$ bits for FL and $Θ\left(\log\left( n\min\left(\varepsilon, \varepsilon^2\right) \right)\right)$ bits for FA to the server, where $n$ is the number of participating clients. Without compression, each client needs $O(d)$ bits and $\log d$ bits for the mean and frequency estimation problems respectively (where $d$ corresponds to the number of trainable parameters in FL or the domain size in FA), which means that we can get significant savings in the regime $ n \min\left(\varepsilon, \varepsilon^2\right) = o(d)$, which is often the relevant regime in practice. Our algorithms leverage compression for privacy amplification: when each client communicates only partial information about its sample, we show that privacy can be amplified by randomly selecting the part contributed by each client.