Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy
This work addresses communication-privacy trade-offs for federated learning and streaming differential privacy, offering incremental improvements over existing methods.
The paper tackles the problem of L2 mean estimation under streaming differential privacy and communication constraints by introducing a novel privacy accounting method for the sparsified Gaussian mechanism, resulting in mean square errors that converge to those of the uncompressed Gaussian mechanism and demonstrating at least a 100x improvement in compression for DP-SGD across federated learning tasks.
We study $L_2$ 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_\infty$ geometry and rely on random rotation or Kashin's representation to adapt to $L_2$ 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 $L_2$ 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.