Improved Communication-Privacy Trade-offs in L2 Mean Estimation under Streaming Differential Privacy

We study L2 mean estimation under central differential privacy and communication constraints, and address two key challenges: firstly, existing mean estimation schemes that simultaneously handle both constraints are usually optimized for L∞ geometry and rely on random rotation or Kashin's representation to adapt to L2 geometry, resulting in suboptimal leading constants in mean square errors (MSEs); secondly, schemes achieving order-optimal communication-privacy trade-offs do not extend seamlessly to streaming differential privacy (DP) settings (e.g., tree aggregation or matrix factorization), rendering them incompatible with DP-FTRL type optimizers. In this work, we tackle these issues by introducing a novel privacy accounting method for the sparsified Gaussian mechanism that incorporates the randomness inherent in sparsification into the DP noise. Unlike previous approaches, our accounting algorithm directly operates in L2 geometry, yielding MSEs that fast converge to those of the uncompressed Gaussian mechanism. Additionally, we extend the sparsification scheme to the matrix factorization framework under streaming DP and provide a precise accountant tailored for DP-FTRL type optimizers. Empirically, our method demonstrates at least a 100x improvement of compression for DP-SGD across various FL tasks. * Part of the work was done during Wei-Ning's internship at Google. The paper has been accepted to ICML 2024. 1 Here, L 2 refers to the L 2 geometry of the local model updates, i.e., ∥g i ∥ 2 ≤ ∆ 2 for all client i. This condition is typically maintained through the L 2 clipping step of the differential privacy mechanism.