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

• URL: http://arxiv.org/abs/2605.30476v1
• Date: Thu, 28 May 2026 18:47:37 GMT
• Title: Local Differential Privacy with Correlated Noise Achieves Central-DP Optimal Cost
• Abstract summary: We study privately estimating the sum of $n$ user-held values in the presence of an honest-but-curious server.<n>We adopt the local (pure) differential privacy model, in which each user transmits a noise-perturbed value.
• Score: 6.714751340563297
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• LoRA and Privacy: When Random Projections Help (and When They Don't) [55.65932772290123]
  We introduce the (Wishart) projection mechanism, a randomized map of the form $S mapsto M f(S)$ with $M sim W_d (1/r I_d, r)$ and study its differential privacy properties.<n>For vector-valued queries $f$, we prove non-asymptotic DP guarantees without any additive noise, showing that Wishart randomness alone can suffice.<n>For matrix-valued queries, however, we establish a sharp negative result: in the noise-free setting, the mechanism is not DP, and we demonstrate its vulnerability.
  arXiv  Detail & Related papers  (2026-01-29T13:43:37Z)
• $(ε, δ)$-Differentially Private Partial Least Squares Regression [1.8666451604540077]
  We propose an $(epsilon, delta)$-differentially private PLS (edPLS) algorithm to ensure the privacy of the data underlying the model.<n> Experimental results demonstrate that edPLS effectively renders privacy attacks, aimed at recovering unique sources of variability in the training data.
  arXiv  Detail & Related papers  (2024-12-12T10:49:55Z)
• Adaptive Differential Privacy in Federated Learning: A Priority-Based Approach [0.0]
  Federated learning (FL) develops global models without direct access to local datasets. DP offers a framework that gives a privacy guarantee by adding certain amounts of noise to parameters. We propose adaptive noise addition in FL which decides the value of injected noise based on features' relative importance.
  arXiv  Detail & Related papers  (2024-01-04T03:01:15Z)
• General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation [58.03500081540042]
  A classical approach to private mean estimation is to compute the true mean and add unbiased, but possibly correlated, Gaussian noise to it. We show that for every input dataset, an unbiased mean estimator satisfying concentrated differential privacy introduces approximately at least as much error.
  arXiv  Detail & Related papers  (2023-01-31T18:47:42Z)
• Optimizing the Noise in Self-Supervised Learning: from Importance Sampling to Noise-Contrastive Estimation [80.07065346699005]
  It is widely assumed that the optimal noise distribution should be made equal to the data distribution, as in Generative Adversarial Networks (GANs) We turn to Noise-Contrastive Estimation which grounds this self-supervised task as an estimation problem of an energy-based model of the data. We soberly conclude that the optimal noise may be hard to sample from, and the gain in efficiency can be modest compared to choosing the noise distribution equal to the data's.
  arXiv  Detail & Related papers  (2023-01-23T19:57:58Z)
• Tight Differential Privacy Guarantees for the Shuffle Model with $k$-Randomized Response [6.260747047974035]
  Most differentially private (DP) algorithms assume a third party inserts noise to queries made on datasets, or a local model where the users locally perturb their data. The recently proposed shuffle model is an intermediate framework between the central and the local paradigms. We perform experiments on both synthetic and real data to compare the privacy-utility trade-off of the shuffle model with that of the central one privatized.
  arXiv  Detail & Related papers  (2022-05-18T10:44:28Z)
• FedCorr: Multi-Stage Federated Learning for Label Noise Correction [80.9366438220228]
  Federated learning (FL) is a privacy-preserving distributed learning paradigm that enables clients to jointly train a global model. We propose $textttFedCorr$, a general multi-stage framework to tackle heterogeneous label noise in FL. Experiments conducted on CIFAR-10/100 with federated synthetic label noise, and on a real-world noisy dataset, Clothing1M, demonstrate that $textttFedCorr$ is robust to label noise.
  arXiv  Detail & Related papers  (2022-04-10T12:51:18Z)
• The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
  We show that deviating from this assumption can actually lead to better statistical estimators. In particular, the optimal noise distribution is different from the data's and even from a different family.
  arXiv  Detail & Related papers  (2022-03-02T13:59:20Z)
• Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms [9.599356978682108]
  We consider a platform's problem of collecting data from privacy sensitive users to estimate an underlying parameter of interest. We consider two popular differential privacy settings for providing privacy guarantees for the users: central and local. We pose the mechanism design problem as the optimal selection of an estimator and payments that will elicit truthful reporting of users' privacy sensitivities.
  arXiv  Detail & Related papers  (2022-01-10T00:27:43Z)
• Deconvoluting Kernel Density Estimation and Regression for Locally Differentially Private Data [14.095523601311374]
  Local differential privacy has become the gold-standard of privacy literature for gathering or releasing sensitive individual data points. However, locally differential data can twist the probability density of the data because of the additive noise used to ensure privacy. We develop density estimation methods using smoothing kernels to remove the effect of privacy-preserving noise.
  arXiv  Detail & Related papers  (2020-08-28T03:39:17Z)
• RDP-GAN: A R\'enyi-Differential Privacy based Generative Adversarial Network [75.81653258081435]
  Generative adversarial network (GAN) has attracted increasing attention recently owing to its impressive ability to generate realistic samples with high privacy protection. However, when GANs are applied on sensitive or private training examples, such as medical or financial records, it is still probable to divulge individuals' sensitive and private information. We propose a R'enyi-differentially private-GAN (RDP-GAN), which achieves differential privacy (DP) in a GAN by carefully adding random noises on the value of the loss function during training.
  arXiv  Detail & Related papers  (2020-07-04T09:51:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.