Pith. sign in

REVIEW 1 minor 27 references

Correlated noise added locally by users can match the estimation cost of central differential privacy up to arbitrarily small error.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-29 00:17 UTC pith:MEAOUAY7

load-bearing objection Correlated local noise closes the central-local DP utility gap for sum estimation up to o(1) error.

arxiv 2605.30476 v1 pith:MEAOUAY7 submitted 2026-05-28 cs.IT cs.CRcs.LGmath.IT

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

Madhura Pathegama , Srikanth Avasarala , Viveck R. Cadambe , Juba Ziani This is my paper
classification cs.IT cs.CRcs.LGmath.IT
keywords local differential privacycorrelated noisecentral differential privacysum estimationprivacy-utility tradeoffestimation cost
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the known utility gap between local and central differential privacy for estimating the sum of private values is not inevitable. By designing joint distributions over the noise each user adds, the authors ensure every individual release meets local ε-DP while the variance of the summed noises approaches the lower variance possible when noise is added only after aggregation. This construction works for any fixed ε and lets the total estimation error get arbitrarily close to the centralized optimum. A reader would care because it removes the need for a trusted server without paying the usual large accuracy penalty of independent local noise.

Core claim

The authors construct ε-DP mechanisms in which the noises added by the n users are jointly distributed so that each marginal satisfies local ε-DP yet the variance of their sum equals the minimal variance achievable under central ε-DP, up to an arbitrarily small additive term. The construction therefore achieves estimation cost for the sum that matches the central-DP optimum up to o(1) error.

What carries the argument

Joint distributions over local noise variables whose marginals obey local ε-DP while the variance of the sum matches the central-DP optimum.

Load-bearing premise

It is possible to choose a joint distribution over the noise terms such that each marginal satisfies local ε-DP while the variance of their sum is as small as the central-DP variance up to o(1).

What would settle it

A proof or numerical demonstration that the minimal achievable variance of the sum, subject only to each marginal obeying local ε-DP, must exceed the central-DP variance by more than an arbitrarily small amount would falsify the claim.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Sum estimation under local DP incurs no asymptotic utility loss relative to central DP.
  • The server can compute the sum after receiving the noisy values without ever seeing the raw data.
  • Privacy holds at each user's release and remains intact during server-side aggregation.
  • The result applies for any fixed privacy parameter ε and any number of users n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same correlation idea could be tested on estimating other linear statistics beyond the plain sum.
  • If users can coordinate on a shared randomness source before releasing, the construction becomes implementable without a central coordinator.
  • The approach suggests examining whether similar joint-noise designs close gaps for non-linear queries or for other local-DP tasks.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 1 minor

Summary. The paper studies private sum estimation of n user-held values under local pure ε-DP with an honest-but-curious server. It constructs correlated noise distributions such that each user's marginal mechanism satisfies local ε-DP while the variance of the aggregate noise matches the optimal central-DP variance up to an arbitrarily small additive error.

Significance. If the construction is correct, the result shows that the well-known utility gap between local and central DP for sum estimation is not fundamental and can be closed (up to o(1)) by joint noise design that preserves exact marginal privacy guarantees. This has implications for understanding the role of dependence in local privacy mechanisms and for practical distributed estimation protocols.

minor comments (1)
  1. The abstract would benefit from a one-sentence indication of the correlation construction technique (e.g., copula-based or Gaussian perturbation) to help readers assess the approach before the full text.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation to accept the manuscript. There are no major comments to address.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents a theoretical construction showing that correlated local noise can achieve central-DP optimal estimation cost up to arbitrarily small error. This is achieved by designing joint distributions over noise variables whose marginals satisfy the local ε-DP density-ratio bound while their sum variance matches the centralized optimum. No equations reduce to self-definition, no parameters are fitted then renamed as predictions, and no load-bearing steps rely on self-citations or imported uniqueness theorems. The argument is self-contained against standard DP definitions and variance identities that are independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities beyond the standard local-DP model and honest-but-curious server assumption stated in the text.

axioms (1)
  • domain assumption Honest-but-curious server model
    Explicitly stated in the abstract as motivation for requiring privacy throughout server-side computation.

pith-pipeline@v0.9.1-grok · 5667 in / 1099 out tokens · 26453 ms · 2026-06-29T00:17:13.572893+00:00 · methodology

0 comments
read the original 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.

Figures

Figures reproduced from arXiv: 2605.30476 by Juba Ziani, Madhura Pathegama, Srikanth Avasarala, Viveck R. Cadambe.

Figure 1
Figure 1. Figure 1: Quadratic loss vs ε for different DP schemes. We numerically evaluate the two-user case (n = 2) with sensitivity ∆ = 2 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: quadratic loss vs ε for different ε0 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: illustrates the density of Pe for n = 2 [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 1 canonical work pages

  1. [1]

    Deep learning with differential pri- vacy,

    M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential pri- vacy,” inProceedings of the 2016 ACM SIGSAC conference on computer and communications security, 2016, pp. 308–318

    2016

  2. [2]

    Communication-efficient learning of deep networks from decentralized data,

    B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” inArtificial intelligence and statistics. PMLR, 2017, pp. 1273–1282

    2017

  3. [3]

    Differentially private iterative synchronous consensus,

    Z. Huang, S. Mitra, and G. Dullerud, “Differentially private iterative synchronous consensus,” inProceedings of the 2012 ACM workshop on Privacy in the electronic society, 2012, pp. 81–90

    2012

  4. [4]

    Differentially pri- vate average consensus with optimal noise selection,

    E. Nozari, P. Tallapragada, and J. Cort ´es, “Differentially pri- vate average consensus with optimal noise selection,”IFAC- PapersOnLine, vol. 48, no. 22, pp. 203–208, 2015

    2015

  5. [5]

    Differentially private aggregation of distributed time-series with transformation and encryption,

    V . Rastogi and S. Nath, “Differentially private aggregation of distributed time-series with transformation and encryption,” in Proceedings of the 2010 ACM SIGMOD International Confer- ence on Management of data, 2010, pp. 735–746

    2010

  6. [6]

    Proactive fault- tolerant aggregation protocol for privacy-assured smart metering,

    J. Won, C. Y . Ma, D. K. Yau, and N. S. Rao, “Proactive fault- tolerant aggregation protocol for privacy-assured smart metering,” inIEEE INFOCOM 2014-IEEE Conference on Computer Com- munications. IEEE, 2014, pp. 2804–2812

    2014

  7. [7]

    Calibrating noise to sensitivity in private data analysis,

    C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” inTheory of cryp- tography conference. Springer, 2006, pp. 265–284

    2006

  8. [8]

    What can we learn privately?

    S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?”SIAM Journal on Computing, vol. 40, no. 3, pp. 793–826, 2011

    2011

  9. [9]

    Local privacy and statistical minimax rates,

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in2013 IEEE 54th annual sym- posium on foundations of computer science. IEEE, 2013, pp. 429–438

    2013

  10. [10]

    The optimal noise-adding mecha- nism in differential privacy,

    Q. Geng and P. Viswanath, “The optimal noise-adding mecha- nism in differential privacy,”IEEE Transactions on Information Theory, vol. 62, no. 2, pp. 925–951, 2015

    2015

  11. [11]

    The role of inter- activity in local differential privacy,

    M. Joseph, J. Mao, S. Neel, and A. Roth, “The role of inter- activity in local differential privacy,” in2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2019, pp. 94–105

    2019

  12. [12]

    New directions in cryptography,

    W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. 22, no. 6, 1976

    1976

  13. [13]

    Optimal algorithms for mean estimation under local differential privacy,

    H. Asi, V . Feldman, and K. Talwar, “Optimal algorithms for mean estimation under local differential privacy,” inInternational Conference on Machine Learning. PMLR, 2022, pp. 1046–1056

    2022

  14. [14]

    A differentially private stochastic gradient descent algorithm for multiparty classification,

    A. Rajkumar and S. Agarwal, “A differentially private stochastic gradient descent algorithm for multiparty classification,” inArti- ficial Intelligence and Statistics. PMLR, 2012, pp. 933–941

    2012

  15. [15]

    Stochastic gradient descent with differentially private updates

    S. Song, K. Chaudhuri, A. D. Sarwateet al., “Stochastic gradient descent with differentially private updates.” inGlobalSIP, 2013, pp. 245–248

    2013

  16. [16]

    Distributed differentially private algorithms for matrix and tensor factorization,

    H. Imtiaz and A. D. Sarwate, “Distributed differentially private algorithms for matrix and tensor factorization,”IEEE journal of selected topics in signal processing, vol. 12, no. 6, pp. 1449– 1464, 2018

    2018

  17. [17]

    A correlated noise-assisted decentralized differentially private estimation protocol, and its application to fMRI source separation,

    H. Imtiaz, J. Mohammadi, R. Silva, B. Baker, S. M. Plis, A. D. Sarwate, and V . D. Calhoun, “A correlated noise-assisted decentralized differentially private estimation protocol, and its application to fMRI source separation,”IEEE Transactions on Signal Processing, vol. 69, pp. 6355–6370, 2021

    2021

  18. [18]

    The privacy power of correlated noise in de- centralized learning,

    Y . Allouah, A. Koloskova, A. El Firdoussi, M. Jaggi, and R. Guerraoui, “The privacy power of correlated noise in de- centralized learning,” inProceedings of the 41st International Conference on Machine Learning, 2024, pp. 1115–1143

    2024

  19. [19]

    Cor- related privacy mechanisms for differentially private distributed mean estimation,

    S. Vithana, V . R. Cadambe, F. P. Calmon, and H. Jeong, “Cor- related privacy mechanisms for differentially private distributed mean estimation,” in2025 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML). IEEE, 2025, pp. 590– 614

    2025

  20. [20]

    Differentially private distributed mean estimation with constrained user correlations,

    ——, “Differentially private distributed mean estimation with constrained user correlations,” in2025 IEEE International Sym- posium on Information Theory (ISIT). IEEE, 2025, pp. 1–6

    2025

  21. [21]

    Practical secure aggregation for privacy-preserving machine learning,

    K. Bonawitz, V . Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth, “Practical secure aggregation for privacy-preserving machine learning,” in proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017, pp. 1175–1191

    2017

  22. [22]

    The fundamental price of secure aggregation in differentially private federated learning,

    W.-N. Chen, C. A. C. Choo, P. Kairouz, and A. T. Suresh, “The fundamental price of secure aggregation in differentially private federated learning,” inInternational Conference on Machine Learning. PMLR, 2022, pp. 3056–3089

    2022

  23. [23]

    Efficient differentially private secure aggregation for federated learning via hardness of learning with errors,

    T. Stevens, C. Skalka, C. Vincent, J. Ring, S. Clark, and J. Near, “Efficient differentially private secure aggregation for federated learning via hardness of learning with errors,” in31st USENIX security symposium (USENIX Security 22), 2022, pp. 1379–1395

    2022

  24. [24]

    Practical and private (deep) learning without sampling or shuffling,

    P. Kairouz, B. McMahan, S. Song, O. Thakkar, A. Thakurta, and Z. Xu, “Practical and private (deep) learning without sampling or shuffling,” inInternational Conference on Machine Learning. PMLR, 2021, pp. 5213–5225

    2021

  25. [25]

    A., Dvijotham, K., Ganesh, A., Henzinger, M., Katz, J., McKenna, R., McMahan, H

    K. Pillutla, J. Upadhyay, C. A. Choquette-Choo, K. Dvijotham, A. Ganesh, M. Henzinger, J. Katz, R. McKenna, H. B. McMahan, K. Rushet al., “Correlated noise mechanisms for differentially private learning,”arXiv preprint arXiv:2506.08201, 2025

    work page arXiv 2025

  26. [26]

    R ´enyi differential privacy,

    I. Mironov, “R ´enyi differential privacy,” in2017 IEEE 30th computer security foundations symposium (CSF). IEEE, 2017, pp. 263–275

    2017

  27. [27]

    General staircase mechanisms for optimal differential privacy,

    A. Kulesza, A. T. Suresh, and Y . Wang, “General staircase mechanisms for optimal differential privacy,” inProceedings of The 28th International Conference on Artificial Intelligence and Statistics, vol. 258, 2025, pp. 4564–4572. APPENDIXA PROOF OFLEMMA1 For convenience, we restate Lemma 1. Lemma(Scaling invariance of the optimal cost).Let ε,∆, α >0and le...

    2025