REVIEW 4 major objections 5 minor 34 references
Distributed, communication-efficient, and differentially private estimation of KL divergence
T0 review · 4 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The paper claims that KL divergence from a public reference to private federated data can be estimated privately and with bounded communication through Monte Carlo probes, with unbiasedness in two trust models.
desk verdict A sensible architecture for private federated KL divergence, but the unbiasedness and DP proofs have a load-bearing gap: client subsampling makes the estimator biased and the sensitivity of the released estimator is never established. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the per-sample estimator $K(r)=\lambda(r-1)-\log r$, where $r(X)=P(X)/\Pi(X)$ and $X$ is drawn from the public reference $\Pi$. Because $D_{\mathrm{KL}}(\Pi\parallel P)$ is a Bregman divergence, $K$ measures the vertical gap between $\log r$ and its tangent, and Fact 4.2 states $\mathbb{E}[K]=D_{\mathrm{KL}}(\Pi\parallel P)$. The algorithm averages $T$ such terms over sampled clients, aggregates frequencies with secure aggregation, and adds Gaussian noise scaled by the sensitivity bound $\Delta(\eta|_{P^{>1}})<0.7$; an information-theoretic inequality bounds the variance-optimal $\lambda_0$, and Theorem 4.4 bounds the final variance.
What would settle it
Run Algorithm 1 on a fixed finite domain with $n$ clients, each holding one item, sampling $|C_t|<n$ clients uniformly per round, and using a known full-support $\Pi$; compute the empirical mean of the estimator for $T=10^5$ rounds and compare it with the exact $D_{\mathrm{KL}}(\Pi\parallel P)$. If the gap does not shrink toward zero as $T$ grows, the unbiasedness guarantee does not hold under client subsampling.
Extended reading notes
Core claim
On the paper's own terms, the discovery is that KL divergence is estimable in the federated setting by drawing $T$ symbols from the public distribution $\Pi$ and averaging the Bregman tangent expression $\lambda(r-1)-\log r$ with $r(x)=P(x)/\Pi(x)$. Facts 4.1 and 4.2 show the expectation of this expression is $D_{\mathrm{KL}}(\Pi\parallel P)$, giving unbiased estimates in the Trusted and TAgg models; adding Gaussian noise calibrated to the sensitivity of the KL query (bounded by $0.7$ on distributions whose symbols each occur at least twice, Theorem 4.9) yields $(\varepsilon,\delta)$-DP. The fully distributed variant adds client-side noise and a clipping floor $\tau$, preserving DP but explicitly giving up unbiasedness.
Load-bearing premise
The unbiasedness proofs assume that the aggregated frequency $P(x_t)$ equals the exact global probability $P(x_t)$ when the expectation identity is applied; if only a random subset of clients participates, the expected log ratio is not the log of the global ratio, so the promised zero bias can fail.
Editorial extensions
If this is right
- A server can detect distribution drift against a public reference without collecting raw client data, since the communication cost is $T$ probes and per-probe secure-aggregated counts.
- Under the Trusted and TAgg models, the estimator is unbiased with variance bounded by Theorem 4.4, so accuracy improves by increasing $T$ or choosing $\lambda$ near the recommended range.
- The TAgg and Dist versions provide formal $(\varepsilon,\delta)$-DP guarantees, with Dist preferred empirically when privacy is strict and TAgg preferred as $\varepsilon$ grows.
- Because the sensitivity bound for the KL query is a constant below $0.7$, the Gaussian noise added for privacy does not scale with the size of the domain.
- Experiments on the handwritten-digit benchmark indicate that sampling roughly 10% of clients per round and setting $\lambda\approx 0.1$ gives a good privacy-accuracy trade-off.
Reading between the lines
- The same Bregman-tangent estimator could be adapted to other divergences expressible as expectations under the reference distribution, so the algorithmic template may transfer beyond KL divergence.
- A natural next step would be to derive privacy-amplification bounds from the random client subsampling itself; if such bounds hold, the required added noise could shrink as the sampling rate decreases.
- The sensitivity analysis suggests the privacy guarantee is independent of domain size when all symbols appear frequently; testing on sparse high-dimensional domains would reveal how the $\tau$ clipping in the Dist model interacts with that bound.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper introduces PRIEST-KLD, a family of algorithms for estimating the KL divergence DKL(Π∥P) between a public reference distribution Π and a private federated distribution P under three trust models: Trusted, TAgg, and Dist. The server samples T points from Π; in each round a randomly sampled subset of clients reports the frequency of the sampled symbol, a secure aggregation yields P(xt), and the estimator averages λ(P(xt)/Π(xt)−1)−log(P(xt)/Π(xt)) over the T rounds. The paper claims unbiasedness under the Trusted and TAgg models, bounded variance, and (ε,δ)-DP via Gaussian noise calibrated to the sensitivity of the true KL divergence, and it presents FEMNIST experiments concluding that the private estimators achieve accuracy comparable to a non-private baseline.
Significance. If the theorems were correct, PRIEST-KLD would be a useful primitive for federated analytics: communication cost bounded by T queries, a natural Monte Carlo/Bregman estimator, and formal DP guarantees under several trust assumptions. The problem is well motivated, and the paper is transparent about the Dist model lacking unbiasedness. However, the central formal claims are not established: the unbiasedness proof conflates the randomly sampled aggregate with the global distribution, and the DP proof calibrates noise to the sensitivity of the true KL query rather than to the sensitivity of the released estimator. The experimental section also selects λ in-sample on the same data used to report accuracy. These issues are load-bearing, so the significance of the paper as it stands is limited.
major comments (4)
- [Section 4.2.1, Theorem 4.3 (and Theorem 4.7)] The proof applies Fact 4.2 to r(xt)=P(xt)/Π(xt), treating P(xt) from Algorithm 1 line 7 as the fixed global distribution P. In fact P(xt) is the SecAgg average over the randomly sampled client subset Ct, so r is random even conditional on xt. Unbiasedness would require E_{X∼Π,Ct}[λ(P_C(X)/Π(X)−1)−log(P_C(X)/Π(X))] = DKL(Π∥P), but Jensen's inequality gives E_C[−log(P_C/Π)] ≥ −log(E_C[P_C]/Π), with equality only if P_C is constant. A minimal example with X={0,1}, Π=(1/2,1/2), two clients with local distributions (0.9,0.1) and (0.1,0.9), and |Ct|=1 yields an estimator expectation of about 0.511 while DKL(Π∥P)=0. Thus Theorems 4.3 and 4.7 do not establish unbiasedness, and Theorem 4.4's variance bound inherits the same incorrect premise.
- [Section 4.2.2, Theorem 4.6 and Section 4.2.3, Theorem 4.9] The DP proof sets f(P)=DKL(Π∥P) and adds Gaussian noise with variance proportional to Δ(f), the sensitivity of the exact KL query. But the released object is D̂, the noisy average of λ(r−1)−log r over T sampled symbols and sampled clients; D̂ is not f(P), and its sensitivity is not bounded by Δ(f). Theorem 4.10 bounds a per-sample expression by (α̂+1)|λ1−λ2| + λ2/(N m) + log 2, which is not a sensitivity bound for the final averaged estimator and still depends on λ0,P. Moreover, Theorem 4.9's bound Δ(η|P>1)<0.7 is restricted to histograms in which every symbol occurs at least twice (P>1), a condition not enforced by Algorithms 1–3 and unrealistic for the 65,536-symbol FEMNIST domain. Therefore the (ε,δ)-DP guarantee in Theorem 4.6 is not established.
- [Section 4.3, Theorem 4.11] The DP proof for the Dist model asserts that one change to the input changes P(xt) by at most 1/N, but this is not justified under client-level adjacency: changing one client's data changes its local frequency by 1/|D_c|, so the aggregated average can change by 1/(|Ct||D_c|), which is not necessarily bounded by 1/N. The proof also does not account for the T queries or the effect of the max{·,τ} truncation on sensitivity. Consequently the Dist model's (ε,δ)-DP claim is not established.
- [Section 5.1 and Section 5.2] The empirical claim that the private estimators achieve accuracy comparable to a non-private baseline is weakened by in-sample selection: in Section 5.1, λ is chosen by minimizing MSE on the same FEMNIST distribution pairs, and the MSE values reported in Section 5.2 are computed on those same pairs. There is no held-out split, cross-validation, or error bars, and the baseline estimator is not fully specified. The experimental conclusion is therefore descriptive of the fitted setting rather than a predictive comparison.
minor comments (5)
- [Section 4.2.2, Algorithm 2] The notation for the noise η′ is confusing: line 10 and line 11 both add η′, and the proof later refers to 2η′/T, so the reader cannot tell whether the noise is added once or twice and what its variance is.
- [Section 4.2.2, Theorem 4.7 proof] The proof says 'By similar arguments to the proof of Theorem 4.6,' but Theorem 4.6 is the DP claim; the unbiasedness argument should refer to Theorem 4.3 or to Facts 4.1 and 4.2.
- [Section 4.2.1, Corollary 4.5] Corollary 4.5 minimizes the upper bound from Theorem 4.4, not the actual variance; the text should say 'the variance upper bound is minimized at' rather than describing the result as the optimal λ0.
- [Section 5.1] The narrative about choosing λ is inconsistent: Section 5.1.1 recommends λ=0.1, Section 5.1.2 later selects λ=0.05 for all models, and the relationship between these recommendations is not reconciled.
- [Section 5, experimental setup] The reference distribution Π for the FEMNIST experiments is not fully specified: it is unclear whether Π is the empirical distribution of a fixed writer/digit store or some other distribution, and how the 65,536-dimensional probabilities are formed from the reported 1,400-image samples.
Circularity Check
Empirical accuracy claim is partially circular: lambda is tuned to minimize MSE on the same FEMNIST evaluation data before the same MSE is reported as achieved accuracy; the theoretical KL identities are not circular but have separate correctness gaps.
-
fitted input called prediction
[Section 5.2 opening, with tuning procedure in Section 5.1 and abstract conclusion]
"For both low and high KL divergence, the best λ ∈ [0, 2] is chosen in order to reduce the MSE according to the values seen in the previous section."
The parameter λ is selected by minimizing the very MSE metric, on the same FEMNIST digit-pair data and the same ε/|Ct| settings, that Section 5.2 then reports as the achieved accuracy of PRIEST-KLD. The abstract's claim that 'our private estimators achieve accuracy comparable to a baseline algorithm' is therefore an in-sample optimum of the tuning objective rather than an independent prediction: the reported MSE is, by construction, at or near the minimum of the curve used to pick λ. The 'best λ' values (0.05, 0.1, 0.25, etc.) are fitted to the evaluation data, so the empirical validation cannot serve as an independent confirmation of the accuracy claim.
full rationale
The theoretical derivation chain is not circular. Facts 4.1 and 4.2 are genuine identities, and Theorems 4.3, 4.4, 4.7, and 4.8 do not reduce to fitted parameters or to self-citations. There is no load-bearing self-citation: the authors' own prior work is cited only for background and for vector-valued shuffle-DP, not to justify the KL estimator. The empirical section is the one place where a fitted quantity is renamed as a demonstrated result: λ is chosen by minimizing MSE on the same FEMNIST data used to report accuracy, making the 'comparable to baseline' conclusion partially circular. Separately, the unbiasedness proof has a non-circular correctness gap: Algorithm 1 line 7's SecAgg over the sampled subset Ct is a random aggregate P_C, not the global P used in Fact 4.2, so E[log(P_C/Π)] ≠ log(P/Π); and Theorem 4.6's DP proof applies the sensitivity of the true KL query to the released estimator without establishing that the estimator has that sensitivity. These are mathematical gaps rather than circular reductions, so they do not raise the circularity score above 4.
Assumptions & free parameters
free parameters (2)
- λ =
various values in [0,2], e.g., 0.1, 0.05, 0.25 depending on model and privacy level
- τ =
not specified
assumptions (4)
- standard math Gaussian mechanism (Corollary 3.1)
- domain assumption Fact 4.1 requires P's support to be contained in Π's support
- domain assumption P>1 restriction for sensitivity bound
- domain assumption Honest and independent clients
Cite this review
Pith. "Pith review of Distributed, communication-efficient, and differentially private estimation of KL divergence." pith.science (2026). https://pith.science/paper/V7IQ5JRG
@misc{pith2026241116478,
author = {Pith},
title = {Pith review of: Distributed, communication-efficient, and differentially private estimation of KL divergence},
year = {2026},
howpublished = {\url{https://pith.science/paper/V7IQ5JRG}},
note = {Machine review of arXiv:2411.16478}
}
read the original abstract
A key task in managing distributed, sensitive data is to measure the extent to which a distribution changes. Understanding this drift can effectively support a variety of federated learning and analytics tasks. However, in many practical settings sharing such information can be undesirable (e.g., for privacy concerns) or infeasible (e.g., for high communication costs). In this work, we describe novel algorithmic approaches for estimating the KL divergence of data across federated models of computation, under differential privacy. We analyze their theoretical properties and present an empirical study of their performance. We explore parameter settings that optimize the accuracy of the algorithm catering to each of the settings; these provide sub-variations that are applicable to real-world tasks, addressing different context- and application-specific trust level requirements. Our experimental results confirm that our private estimators achieve accuracy comparable to a baseline algorithm without differential privacy guarantees.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
J. F. McCarthy, K. A. Marx, P. E. Hoffman, A. G. Gee, P. O’Neil, M. L. Ujwal, and J. Hotchkiss. Applications of machine learning and high- dimensional visualization in cancer detection, diagnosis, and management. In Annals of the New York Academy of Sciences , 1020(1):239-262. Wiley Online Library, 2004
work page 2004
-
[2]
M. M. Najafabadi, F. Villanustre, T. M. Khoshgoftaar, N. Seliya, R. Wald, and E. Muharemagic. Deep learning applications and challenges in big data analytics. In Journal of Big Data , 2:1-21. Springer, 2015
work page 2015
-
[3]
A. Bharadwaj and G. Cormode. An introduction to federated computation. In Proceedings of the 2022 International Conference on Management of Data, pages 2448-2451. ACM, 2022. 25
work page 2022
-
[4]
P. Kairouz, H. B. McMahan, B. Avent, A. Ballet, M. Bennis, A. N. Bhagoji, K. A. Bonawitz, Z. Charles, G. Cormode, R. Cummings, R. G. L. D’Oliveira, H. Eichner, S. El Rouayheb, D. Evans, J. Gardner, Z. Garrett, A. Gasc´ on, B. Ghazi, P. B. Gibbons, M. Gruteser, Z, Harchaoui, C. He, L. He. Z. Hou, B. Hutchinson, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Kho...
work page 2021
-
[5]
M. Abadi, A. Chu, I. J. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016 , pages 308-318. ACM, 2016
work page 2016
-
[6]
K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, 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 Con- ference on Computer and Communications Security , pages 1175-1191, 2017
work page 2017
-
[7]
S. Kullback and R. A. Leibler. On information and sufficiency. In The Annals of Mathematical Statistics , 22(1):79-86. Institute of Mathematical Statistics, 1951
work page 1951
-
[8]
C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science , 9(3-4):211-407, 2014
work page 2014
Show all 34 references
-
[9]
McMahan, E
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication-efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics , pages 1273-1282. PMLR, 2017
2017
-
[10]
S. Guha, P. Indyk, and A. McGregor. Sketching information divergences. In 20th Annual Conference on Learning Theory , pages 424-438. Springer, 2007
2007
-
[11]
Blocki, A
J. Blocki, A. Blum, A. Datta, and O. Sheffet. The Johnson-Lindenstrauss Transform itself preserves differential privacy. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 410-419. IEEE Com- puter Society, 2012
2012
-
[12]
Kenthapadi, A
K. Kenthapadi, A. Korolova, I. Mironov, and N. Mishra. Privacy via the Johnson-Lindenstrauss Transform. In Journal of Privacy and Confidentiality, 5(1):39-71, 2013
2013
-
[13]
C. Hou, H. Zhan, A. Shrivastava, S. Wang, A. Livshits, G. Fanti, and D. Lazar. Privately customizing prefinetuning to better match user data in federated learning. arXiv preprint arXiv:2302.09042 , 2023. 26
2023 arXiv
-
[14]
Nielsen, K
F. Nielsen, K. Sun, and S. Marchand-Maillet. On H¨ older projective diver- gences. In Entropy, 19(3):122. MDPI, 2017
2017
-
[15]
Andoni, K
A. Andoni, K. Do Ba, P. Indyk, and D. Woodruff. Efficient sketches for earth-mover distance, with applications. In 2009 50th Annual IEEE Sym- posium on Foundations of Computer Science , pages 324-330. IEEE, 2009
2009
-
[16]
Heikkil¨ a, J
M. Heikkil¨ a, J. J¨ alk¨ o, O. Dikmen, and A. Honkela. Differentially private Markov chain Monte Carlo. In Advances in Neural Information Processing Systems, 32:1-11, 2019
2019
-
[17]
J. R. Hershey and P. A. Olsen. Approximating the Kullback Leibler diver- gence between Gaussian mixture models. In 2007 IEEE International Con- ference on Acoustics, Speech and Signal Processing-ICASSP’07 , 4:IV-317. IEEE, 2007
2007
-
[18]
Heikkil¨ a, E
M. Heikkil¨ a, E. Lagerspetz, S. Kaski, K. Shimizu, S. Tarkoma, and A. Honkela. Differentially private Bayesian learning on distributed data. In Ad- vances in Neural Information Processing Systems , 30:1-10, 2017
2017
-
[19]
Corrigan-Gibbs and D
H. Corrigan-Gibbs and D. Boneh. Prio: Private, robust, and scalable com- putation of aggregate statistics. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17) , pages 259-282. USENIX, 2017
2017
-
[20]
Addanki, K
S. Addanki, K. Garbe, E. Jaffe, R. Ostrovsky, and A. Polychroniadou. Prio+: Privacy preserving aggregate statistics via boolean shares. In In- ternational Conference on Security and Cryptography for Networks , pages 516-539. Springer, 2022
2022
-
[21]
Keeler, C
D. Keeler, C. Komlo, E. Lepert, S. Veitch, and X. He. DPrio: Efficient differential privacy with high utility for Prio. In Proceedings on Privacy En- hancing Technologies, 2023(3):375-390, 2023
2023
-
[22]
J. Kim, G. Park, M. Kim, and S. Park. Cluster-based secure aggregation for federated learning. In Electronics, 12(4):870. MDPI, 2023
2023
-
[23]
A. Shamir. How to share a secret. In Communications of the ACM , 22(11):612-613. ACM, 1979
1979
-
[24]
A. Shapiro. Monte Carlo sampling methods. In Handbooks in Operations Research and Management Science , 10:353-425. Elsevier, 2003
2003
-
[25]
S. Amari. α-Divergence Is Unique, Belonging to Both f -Divergence and Bregman Divergence Classes. In IEEE Transactions on Information Theory , 55(11):4925-4931. IEEE, 2009
2009
-
[26]
S. S. Dragomir and V. Gluˇ sˇ cevi´ c. Some inequalities for the Kullback-Leibler and χ2-distances in information theory and applications. InRGMIA Research Report Collection, 3(2):199-210. School of Communications and Informatics, Faculty of Engineering and Science, 2000. 27
-
[27]
Caldas, S
S. Caldas, S. M. K. Duddu, P. Wu, T. Li, J. Koneˇ cn` y, H. B. McMahan, V. Smith, and A. Talwalkar. LEAF: A benchmark for federated settings. arXiv preprint arXiv:1812.01097, 2018
2018 arXiv
-
[28]
B. Ding, J. Kulkarni, and S. Yekhanin. Collecting telemetry data privately. In Advances in Neural Information Processing Systems , pages 3571-3580, 2017
2017
-
[29]
Scott, G
M. Scott, G. Cormode, and C. Maple. Aggregation and transformation of vector-valued messages in the shuffle model of differential privacy. In IEEE Transactions on Information Forensics and Security, 17:612-627. IEEE, 2022
2022
-
[30]
Xiao and L
Y. Xiao and L. Xiong. Protecting locations with differential privacy under temporal correlations. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security , pages 1298-1309. ACM, 2015
2015
-
[31]
Jorgensen, T
Z. Jorgensen, T. Yu, and G. Cormode. Conservative or liberal? Personalized differential privacy. In 2015 IEEE 31st International Conference on Data Engineering, pages 1023-1034. IEEE, 2015
2015
-
[32]
Bonawitz, F
K. Bonawitz, F. Salehi, J. Jakub Koneˇ cn` y, B. McMahan, and M. Gruteser. Federated learning with autotuned communication-efficient secure aggrega- tion. In 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pages 1222-1226. IEEE, 2019
2019
-
[33]
Kairouz, K
P. Kairouz, K. Bonawitz, and D. Ramage. Discrete distribution estimation under local privacy. International Conference on Machine Learning, 48:2436-
-
[34]
Kairouz, Z
P. Kairouz, Z. Liu, and T. Steinke. The distributed discrete gaussian mech- anism for federated learning with secure aggregation. In International Con- ference on Machine Learning , pages 5201-5212. PMLR, 2021. 28
2021
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.