# Local Differential Privacy with Correlated Noise Achieves Central-DP Optimal Cost

arXiv: https://arxiv.org/abs/2605.30476 · HTML: https://mlsanity.com/paper/2605.30476/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 25 references that are in the map.
- First posted on arXiv 28 May 2026.

## Builds on (most cited first, 10 of 10)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Efficient Differentially Private Secure Aggregation for Federated Learning via Hardness of Learning with Errors](https://mlsanity.com/paper/2112.06872/) (2021)
- [The Privacy Power of Correlated Noise in Decentralized Learning](https://mlsanity.com/paper/2405.01031/) (2024)
- [Correlated Noise Mechanisms for Differentially Private Learning](https://mlsanity.com/paper/2506.08201/) (2025)
- [Distributed Differentially-Private Algorithms for Matrix and Tensor Factorization](https://mlsanity.com/paper/1804.10299/) (2018)
- [Correlated Privacy Mechanisms for Differentially Private Distributed Mean Estimation](https://mlsanity.com/paper/2407.03289/) (2024)

## Abstract (arXiv)

We study privately estimating the sum of n user-held values in the presence of an honest-but-curious server. This motivates requiring privacy not only at data release but also throughout server-side computation. We therefore adopt the local (pure) differential privacy model, in which each user transmits a noise-perturbed value. It is well known that independent local noise typically incurs a substantial utility loss compared to the centralized model, where noise is added only after aggregation. We show that this gap is not fundamental. By carefully designing correlations among the locally added noise variables, we construct varepsilon-DP mechanisms whose estimation cost matches the optimal cost achievable in the centralized setting, up to an arbitrarily small error.