Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation
<|reference_start|>Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation: Differentially private distributed mean estimation (DP-DME) is a fundamental building block in privacy-preserving federated learning, where a central server estimates the mean of $d$-dimensional vectors held by $n$ users while ensuring $(\epsilon,\delta)$-DP. Local differential privacy (LDP) and distributed DP with secure aggregation (SecAgg) are the most common notions of DP used in DP-DME settings with an untrusted server. LDP provides strong resilience to dropouts, colluding users, and malicious server attacks, but suffers from poor utility. In contrast, SecAgg-based DP-DME achieves an $O(n)$ utility gain over LDP in DME, but requires increased communication and computation overheads and complex multi-round protocols to handle dropouts and malicious attacks. In this work, we propose CorDP-DME, a novel DP-DME mechanism that spans the gap between DME with LDP and distributed DP, offering a favorable balance between utility and resilience to dropout and collusion. CorDP-DME is based on correlated Gaussian noise, ensuring DP without the perfect conditional privacy guarantees of SecAgg-based approaches. We provide an information-theoretic analysis of CorDP-DME, and derive theoretical guarantees for utility under any given privacy parameters and dropout/colluding user thresholds. Our results demonstrate that (anti) correlated Gaussian DP mechanisms can significantly improve utility in mean estimation tasks compared to LDP -- even in adversarial settings -- while maintaining better resilience to dropouts and attacks compared to distributed DP.<|reference_end|>
@article{vithana2024correlated,
    title={Correlated Privacy Mechanisms for Differentially Private Distributed
  Mean Estimation},
    author={Sajani Vithana, Viveck R. Cadambe, Flavio P. Calmon, Haewon Jeong},
    journal={arXiv preprint arXiv:2407.03289},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.03289},
    primaryClass={cs.IT cs.CR cs.LG math.IT}
}