Breaking the Communication-Privacy-Accuracy Trilemma

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

In modern distributed systems, such as federated learning, data is spread across millions of user devices. To learn from this data effectively, central servers face three competing pressures:

  1. Communication: Bandwidth is limited, requiring clients to send as few bits as possible.
  2. Privacy: Users demand Local Differential Privacy (LDP), meaning the data sent to the server shouldn't reveal too much about any individual.
  3. Accuracy: The system still needs high-quality global estimates (e.g., the average gradient for a model update).

Previously, researchers addressed these challenges separately. However, "naive" combinations—like privatizing data first and then compressing it—often lead to disastrous results. For example, in mean estimation, a naive approach causes the error to grow quadratically with the data's dimension ($d^2$), whereas the theoretical lower bound suggests it should only grow linearly ($d$).

This paper introduces novel encoding and decoding mechanisms that "break" this perceived trilemma. By leveraging Kashin’s representation and the recursive structure of Hadamard matrices, the authors demonstrate that we can achieve the same optimal accuracy under joint privacy and communication constraints as we would under either constraint alone—essentially getting one constraint "for free."

Proposed Mechanisms

The authors propose two primary mechanisms tailored for different statistical tasks:

SQKR for Mean Estimation

Standard compression often "concentrates" information into a few coefficients. While efficient for communication, this makes the signal extremely fragile to the noise required for privacy. To solve this, the authors introduce SQKR (Subsampled and Quantized Kashin’s Response).

SQKR uses Kashin’s representation, a technique from functional analysis that spreads information evenly across all dimensions. This "spread" makes the signal robust. The data is then quantized to 1-bit per dimension, subsampled to meet the bit budget, and privatized using Randomized Response.

SQKR vs. Separation

RHR for Frequency and Distribution Estimation

For categorical data, the authors leverage the Walsh-Hadamard Transform to create RHR (Recursive Hadamard Response). Unlike previous Hadamard-based methods, RHR exploits the recursive structure of these matrices. This allows the mechanism to boost the effective sample size exponentially as the communication budget increases, rather than just linearly. It is also computationally efficient, boasting a decoding complexity of $O(n + d \log d)$.

Key Insights and Results

  • The "For Free" Principle: The most striking insight of the paper is that the fundamental trade-off is determined only by the more stringent of the two constraints (privacy or communication). With clever encoding, the less stringent constraint doesn't add any additional asymptotic error.
  • Spreading vs. Concentrating: In the privacy-communication regime, "spreading" information (via Kashin) is superior to "concentrating" it. If you concentrate information, a small amount of privacy noise can destroy the most important bits. If you spread it, the noise is averaged out across many components.
  • Closing the Gap: For mean estimation, SQKR achieves an $\ell_2$ error of $O(d/n)$, matching the optimal rate under privacy alone. This is a significant improvement over the $O(d^2/n)$ error seen in prior joint-constraint work.
  • Communication Efficiency: For frequency estimation, RHR achieves optimal accuracy with only $\min(\lceil\epsilon\rceil, \log d)$ bits. This is a massive reduction compared to the $d$ bits required by previous state-of-the-art methods like Asymmetric RAPPOR to achieve the same accuracy.
RHR Communication Efficiency

Limitations and Future Work

While the theoretical results are strong, the authors note a few limitations:

  • Shared Randomness: The current mechanisms rely on "public coins" (shared randomness between the client and server). While this can be reduced or eliminated in some statistical settings, it remains a requirement for achieving the absolute best communication efficiency in others.
  • Task Scope: The paper focuses on "canonical" tasks: mean, frequency, and distribution estimation. While these are the building blocks of many algorithms (like SGD), extending these specific encoding tricks to more complex, non-linear distributed learning tasks remains an open challenge.
  • Computational Overhead: While RHR is highly efficient, the pre-processing for SQKR (finding Kashin's representation) can be computationally intensive for very high-dimensional data on low-power edge devices.

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 epsilon-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 epsilon = 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},
}

Loading related content...

Figure