Breaking the Communication-Privacy-Accuracy Trilemma

Wei-Ning Chen, Peter Kairouz, Ayfer Özgür

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.

Introduction: The Distributed Estimation Trilemma

In distributed machine learning, such as Federated Learning on mobile devices, practitioners face a "trilemma" between three competing objectives: high accuracy, robust user privacy, and strict communication bandwidth. Traditionally, optimizing for one often necessitates a compromise in the others. For instance, privacy-preserving noise increases data entropy, making compression (communication efficiency) more difficult.

This work by Chen, Kairouz, and Özgür introduces novel encoding mechanisms—SQKR and RHR—that break this trilemma. They demonstrate that with "intelligent encoding," the fundamental trade-off is determined only by the most stringent constraint, effectively allowing the other constraint to be satisfied without additional accuracy loss.

Proposed Mechanisms

1. SQKR for Mean Estimation

The Subsampled and Quantized Kashin’s Response (SQKR) is designed for mean estimation of high-dimensional vectors. Unlike standard compression that concentrates information into a few coefficients, SQKR uses Kashin’s representation to spread information evenly across all dimensions. This makes the signal robust to both privacy-preserving noise and data loss from subsampling.

Comparison of SQKR with existing mean estimation methods under joint privacy and communication constraints.

The process involves transforming data into a tight frame, quantizing to 1-bit per dimension, and randomly sampling bits to send via a Randomized Response mechanism. As shown in the table above, SQKR achieves order-optimal $\ell_2$ error for any privacy level $\varepsilon$ and communication budget $b$.

2. RHR for Frequency Estimation

The Recursive Hadamard Response (RHR) addresses frequency estimation (counting item occurrences). It leverages the recursive structure of Walsh-Hadamard matrices, allowing estimation error to decay exponentially as the communication budget increases. It effectively "boosts" the sample size by a factor of $2^b$.

Comparison of RHR with other frequency and distribution estimation mechanisms.

RHR is computationally efficient, with a decoding complexity of $O(n + d \log d)$. It achieves the same accuracy as state-of-the-art Local Differential Privacy (LDP) methods while using significantly fewer bits—sometimes half the budget or less.

Key Insights and Results

The core finding is the existence of a "Free" Constraint: the error is dominated by whichever constraint (privacy or communication) is harsher. If privacy requirements are stricter than bandwidth limits, data can be compressed to that limit without further accuracy degradation.

Performance Highlights:

  • Order-Optimality: Both SQKR and RHR reach information-theoretic lower bounds. For mean estimation, SQKR's error scales linearly with dimension $d$, whereas naive "Separation" strategies scale quadratically ($d^2$).
  • Communication Efficiency: RHR often matches the accuracy of existing LDP methods using only a fraction of the communication budget.
  • Shared Randomness: The use of "public coins" (shared randomness between client and server) is a critical tool for reducing communication overhead, allowing the server to synchronize with client-side sampling decisions without extra signaling.

Conclusion and Future Directions

This research proves that joint optimization of privacy and communication is not only possible but necessary for high-dimensional distributed learning. Future work includes extending these distribution-free results to settings without shared randomness and integrating these subroutines into large-scale Distributed SGD training loops to evaluate real-world impact on model convergence.

Summary updated

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.
BibTeX
@inproceedings{chen2020breaking,
  author = {Wei-Ning Chen and Peter Kairouz and Ayfer Özgür},
  title = {{Breaking the Communication-Privacy-Accuracy Trilemma}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=cF3Q_i2M0Xb},
}
Figure