Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy
<|reference_start|>Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy: 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.<|reference_end|>
@article{chen2024improved,
    title={Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under
  Streaming Differential Privacy},
    author={Wei-Ning Chen, Berivan Isik, Peter Kairouz, Albert No, Sewoong Oh,
  Zheng Xu},
    journal={arXiv preprint arXiv:2405.02341},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.02341},
    primaryClass={cs.CR cs.LG}
}