Event URL: https://openreview.net/forum?id=NqikEZ6ABea »
Optimizing the \puc tradeoff is a key challenge for federated learning. Under distributed differential privacy (DP) via secure aggregation (SecAgg), we prove that the worst-case communication cost per client must be at least $\Omega\left( d \log \left( \frac{n^2\varepsilon^2}{d} \right) \right)$ to achieve $O\left( \frac{d}{n^2\varepsilon^2} \right)$ centralized error, which matches the error under central DP. Despite this bound, we leverage the near-sparse structure of model updates, evidenced through recent empirical studies, to obtain improved tradeoffs for distributed \DP. In particular, we leverage linear compression methods, namely sketching, to attain compression rates of up to $50\times$ with no significant decrease in model test accuracy achieving a noise multiplier $0.5$. Our work demonstrates that fundamental tradeoffs in differentially private federated learning can be drastically improved in practice.