REVIEW 4 major objections 7 minor 1 cited by
Differentially Private Empirical Cumulative Distribution Functions
T0 review · 4 major / 7 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read Publishing a complete ECDF is ε-differentially private, the paper proves, with error growing only as a cube of the logarithm of the number of curve points.
desk verdict A useful private-ECDF primitive with a real gap: Theorem 1 only holds for a fixed public grid, while the method builds the grid from private extrema, and the HL composition proof is shaky. 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 a dyadic hierarchy of Laplace noise indexed by $I[L]=\{(j,l)\mid l\in[0,L],\, j\in[\lceil 2^{L-l}\rceil]\}$, where each evaluation point $\tau_i$ receives the sum of noise terms whose dyadic intervals contain $i$. A single changed data point shifts the ECDF on a contiguous range of indices, and Lemma 1 shows that any such contiguous range can be represented as a weighted sum of at most $L+1$ indicator functions from the hierarchy with coefficients in $\{-1,0,1\}$. The privacy proof then bounds the log-likelihood ratio between adjacent datasets by $(L+1)\cdot\epsilon/(L+1)=\epsilon$. This hierarchy also drives the computational strategies: ECDF evaluation is cast as a U-statistic, inverse ECDF evaluation runs by binary search, and function secret sharing for comparison functions makes per-query server cost independent of the number of data owners after a one-time key distribution.
What would settle it
Take two adjacent datasets whose only difference is one extreme value. If the grid endpoints are chosen as the data minimum and maximum, the two runs use different grids, and an attacker who knows the grid can infer the extreme value directly. A concrete check is to simulate the mechanism with a data-dependent grid and compare output distributions on adjacent inputs: for small ε the likelihood-ratio bound will be violated because the support of the output shifts with the grid, whereas fixing an arbitrary public grid that contains both datasets' ranges restores the bound.
Extended reading notes
Core claim
The central claim is Theorem 1: for a fixed public evaluation grid $\tau_1<\cdots<\tau_N$, publishing all values $\hat F_\phi(X,\tau_i)$ defined by summing the dyadic Laplace noise terms is ε-differentially private, with expected squared error $2(L+1)^3/\epsilon^2$. The proof compares adjacent datasets differing in one instance and shows that the difference in the released vector is a sparse combination, with coefficients in $\{-1,0,1\}$, of the dyadic noise terms; because at most $L+1$ noise coefficients are changed and each is drawn from $\mathrm{Lap}((L+1)/\epsilon)$, the likelihood ratio stays within $e^\epsilon$. The same machinery gives a private inverse ECDF evaluated by binary search, a private ROC curve from two privatized ECDFs, a private Hosmer-Lemeshow statistic through private quantile boundaries and group counts, and an improved continual-observation guarantee for partial sums.
Load-bearing premise
The proof treats the evaluation grid $\tau$ as a fixed public constant chosen before seeing the data; if the grid's endpoints are set to the data's private minimum and maximum, the released curve can leak those extrema and the ε-DP argument no longer applies.
Editorial extensions
If this is right
- A full ECDF can be published under ε-differential privacy with error growing only logarithmically in the number of evaluation points, instead of linearly as with pointwise independent noise.
- ROC curves can be made differentially private by privatizing the two underlying ECDFs with $\epsilon/2$ each, and the smoothed curve remains usable even though the raw noisy curve is not monotone.
- A differentially private Hosmer-Lemeshow statistic follows from private inverse-ECDF quantile boundaries plus private group counts, with the privacy budget split as $(L+1)\epsilon' + 8\epsilon'$.
- The dyadic noise decomposition also improves the privacy guarantee for continual observation of stream sums, reducing the number of changed noise terms by about a factor of two compared with earlier work.
- Federated implementations can inherit the trust model of any secure aggregation protocol, and the function-secret-sharing variant makes the communication cost per query $O(m)$ for $m$ servers rather than $O(n)$ for $n$ data owners.
Reading between the lines
- The authors leave implicit that if the evaluation grid is chosen from the data's private minimum and maximum, as suggested in Section 3.1, the ε-DP guarantee of Theorem 1 does not follow because the grid itself becomes data-dependent; a public fixed grid or a two-stage release with privatized extrema would restore the formal guarantee.
- The same dyadic noise scheme should extend naturally to empirical quantile processes and to functionals such as the Kolmogorov–Smirnov statistic, since these are computed from the same privately released ECDF; the paper does not test these extensions.
- A direct experimental benchmark against bin-wise histograms is testable: for a fixed privacy budget, the complete-curve approach should have smaller error at high resolution, and this comparison can be run on real datasets with known sensitivity.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a method for releasing a complete empirical cumulative distribution function (ECDF) under ε-differential privacy. The main mechanism adds Laplace noise organized in a binary-tree structure, so that the noise level grows only logarithmically in the number N of evaluation points rather than linearly. The authors also present federated computation strategies based on secure aggregation and function secret sharing, a post-processing smoothing step to restore monotonicity, and applications to ROC curves and the Hosmer-Lemeshow statistic, with experiments on several datasets.
Significance. If the main theorem is correct, the paper provides a useful and nontrivial building block: publishing a full ECDF under ε-DP with noise O((log N)^{3/2}/ε) is substantially better than pointwise independent noise, and the claimed constant-factor improvement over prior continual-observation results is of independent interest. The federated algorithms and the identification of ROC curves and Hosmer-Lemeshow statistics as ECDF-based applications give the work practical scope. The paper is generally well written, and the experimental section is thoughtful, including an honest discussion of high variance in the Hosmer-Lemeshow experiments. However, the central privacy proof is incomplete as stated because the evaluation grid is data-dependent, and there are several additional inaccuracies in the theorem statements and proofs that need correction before the results can be relied upon.
major comments (4)
- [§3.1, Theorem 1, Appendix A.1] The privacy proof assumes a fixed, public evaluation grid, but the construction in §3.1 chooses τ_1 = φ_min and τ_N = φ_max, with τ = {t ∈ ψZ | φ_min ≤ t ≤ φ_max}. This makes the grid, and possibly N, a function of the private extrema. In the proof of Theorem 1, Eq. (7) and the coordinatewise comparison of the published vectors are only valid when both neighboring datasets are evaluated on the same τ. With a data-dependent τ, the two adjacent datasets have different grids, the published vectors are not comparable entry by entry, the interval [t_1+1, t_2] does not describe the actual change, and the Laplace ratio argument does not go through. Moreover, if the grid itself (or its endpoints) is part of the output, exact φ_min and φ_max are released without noise, which is not ε-DP for unbounded data domains. The theorem needs to be restated for a fixed public grid, or a separate privacy analysis must be provided for a data-dependent grid.
- [Theorem 1 statement and Eq. (2)] The stated expected squared error E[(F_φ(x)−F̂_φ(x))^2] = 2(L+1)^3/ε^2 is missing the normalization by n^2. Equation (2) defines F̂_φ as F_φ plus (1/|X|) times the sum of Laplace noises, so the variance of the added noise is 2(L+1)^3/(n^2 ε^2), not 2(L+1)^3/ε^2. The proof in Appendix A.1 computes the variance of the unnormalized sum of η's, which is n^2 times the quantity claimed in the theorem. This error propagates to the interpretation of the experimental results and to any application that uses the stated bound.
- [Appendix A.1, Eq. (7) and the following probability comparison] There are notation errors in the proof of Theorem 1 that need correction. Equation (7) writes nF_φ(X^{(s)}, τ) − (n−1)F_φ(X^{(s)}, τ) = 1_{[t_s+1,2^L]}, but since X^{(s)} = X′ ∪ {x_Δ^{(s)}}, the second term should be (n−1)F_φ(X′, τ) for the identity to represent the count difference. Similarly, in the probability comparison, the denominator of the ratio is written as P(n·F̂_φ(X^{(2)}, τ) = y) when it should be P(n·F̂_φ(X^{(1)}, τ) = y). These appear to be fixable typographical issues, but as written they obscure the proof and should be corrected.
- [Appendix A.2, Theorem 2] The proof of Theorem 2 asserts that when one instance changes, only 2 of the Q groups — and hence 8 statistics — are affected. This assumes the group thresholds t_q are fixed. In Algorithm 2, however, the thresholds are computed as t_q ← F̂_M^{-1}(q/Q), which depends on the private data through the private ECDF. For two adjacent datasets, the thresholds can differ, so the membership of every group can change, and the counts O_{s,i}, E_{s,i} in all Q groups may be affected. The privacy argument needs to account for the data-dependent thresholds, either by proving that the composition still holds with the inverse-ECDF mechanism, or by using public or pre-fixed bin boundaries. The sentence claiming that the 4Q statistics together are '8ε′-DP' also needs clarification: if only 8 are affected the composition is 8ε′, but if thresholds shift, the number of affected statistics is not obviously bounded by 8.
minor comments (7)
- [Abstract and §1] The abstract says revealing complete functions is 'more expensive from the point of view of privacy budget,' but the paper's main point is that the cost is only logarithmic in the number of evaluation points. Please rephrase to avoid the impression that the cost is necessarily high.
- [§3.1] The precision parameter ψ is used in the definition of the grid τ but is never formally defined in the main text. Please state explicitly what ψ is and how it relates to N and the domain.
- [§5.1] The sentence 'if we add sufficient noise to make both functions ε/2-differentially private, their combined disclosure is 2ε-differentially private' is confusing: basic composition gives ε = ε/2 + ε/2, not 2ε. If the intended meaning is different (e.g., using a different budget allocation), it should be stated clearly.
- [§6.6 and Figure 6] The discussion of the Hosmer-Lemeshow experiments is honest about the high variance and suggests a direct computation approach, but the comparison would be stronger if the alternative (compute the statistic securely, then add one noise) were implemented and reported rather than only discussed.
- [Appendix A.1, after Theorem 1] Theorem 3, which claims an improvement over the continual-observation result of [4], is stated and justified with a single sentence ('direct application of Lemma 1'). Given that the paper advertises this as a contribution, a full proof or a rigorous sketch should be provided.
- [Algorithm 1] The binary search over F̂_φ assumes the function is non-decreasing, but the paper acknowledges that F̂_φ may not be monotone. The algorithm description could state explicitly what happens when the noisy function is non-monotonic or specify that it is applied to the smoothed F́_φ.
- [References] Reference [13] is cited as a technical report; if a published version exists, it would be helpful to cite that. Also, the URL for the Heart disease dataset should have a stable access date or a DOI if available.
Circularity Check
No significant circularity is present: Theorem 1 is derived from the Laplace mechanism and a self-contained tree-decomposition lemma, and no fitted quantity is renamed as a prediction.
full rationale
The central privacy claim (Theorem 1) is proved in Appendix A.1 rather than assumed: the paper defines the noise variables explicitly, proves Lemma 1 (interval indicators are sparse sums of the Haar-like basis Z_{L,d}) by induction, and then shows that for adjacent datasets the output difference is a vector with at most L+1 nonzero Laplace-noise coefficients, giving the e^epsilon probability ratio. This is a standard Laplace-mechanism composition argument and does not fit any parameter to data or rename an empirical pattern as a derivation. The cited works [9,4] are background for the continual-observation idea; the present proof is reproduced in the appendix, so the citation is not load-bearing. The few self-references ([16,18,19]) concern applications and secure-aggregation building blocks, not the privacy proof. Two correctness concerns are present but are not circularity: Section 3.1 suggests choosing the grid tau from private extrema while the proof of Theorem 1 treats tau as a fixed public vector (Eq. (7) coordinates the two adjacent datasets on the same [N]), and the stated error bound omits the 1/|X|^2 normalization from Eq. (2). Neither makes the derivation equivalent to its inputs; they are gaps in the proof's hypotheses, not self-definition or fitted-input prediction.
Assumptions & free parameters
assumptions (3)
- domain assumption The evaluation grid τ is fixed and public, independent of the data.
- domain assumption A secure aggregation primitive U Stat exists and hides individual contributions under the chosen attack model.
- standard math Standard composition and post-processing of differential privacy.
Cite this review
Pith. "Pith review of Differentially Private Empirical Cumulative Distribution Functions." pith.science (2026). https://pith.science/paper/GGXTWSLI
@misc{pith2026250206651,
author = {Pith},
title = {Pith review of: Differentially Private Empirical Cumulative Distribution Functions},
year = {2026},
howpublished = {\url{https://pith.science/paper/GGXTWSLI}},
note = {Machine review of arXiv:2502.06651}
}
read the original abstract
In order to both learn and protect sensitive training data, there has been a growing interest in privacy preserving machine learning methods. Differential privacy has emerged as an important measure of privacy. We are interested in the federated setting where a group of parties each have one or more training instances and want to learn collaboratively without revealing their data. In this paper, we propose strategies to compute differentially private empirical distribution functions. While revealing complete functions is more expensive from the point of view of privacy budget, it may also provide richer and more valuable information to the learner. We prove privacy guarantees and discuss the computational cost, both for a generic strategy fitting any security model and a special-purpose strategy based on secret sharing. We survey a number of applications and present experiments.
Figures
Figures from the paper (7 more)
Forward citations
Cited by 1 Pith paper
-
Dropout-Robust Mechanisms for Differentially Private and Fully Decentralized Mean Estimation
IncA is a fully decentralized, differentially private mean-estimation protocol whose correlated noise cancels in the no-dropout case, achieving central-DP accuracy under a strong adversarial model.
Reference graph
Works this paper leans on
-
[1]
Private Summation in the Multi-Message Shuffle Model
Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. Private Summation in the Multi-Message Shuffle Model. InCCS, 2020
work page 2020
-
[2]
Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical Secure Aggregation for Privacy-Preserving Machine Learning. InCCS, 2017
work page 2017
-
[3]
Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing. In Elisabeth Oswald and Marc Fischlin, editors,Advances in Cryptology - EUROCRYPT 2015 , pages 337–367, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg
work page 2015
-
[4]
Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown
Adrian Rivera Cardoso and Ryan Rogers. Differentially private histograms under continualobservation:Streamingselectionintotheunknown. CoRR,abs/2103.16787, 2021
work page Pith review arXiv 2021
-
[5]
T. H. Chan, E. Shi, and D. Song. Private and continual release of statistics.ACM Transactions on Information and System Security , 14(3):26:1–26:24, 2011
work page 2011
-
[6]
Hubert Chan, Elaine Shi, and Dawn Song
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Privacy-preserving stream aggre- gation with fault tolerance. InFinancial Cryptography, 2012
work page 2012
-
[7]
Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev
Albert Cheu, Adam D. Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed Differential Privacy via Shuffling. InEUROCRYPT, 2019
work page 2019
-
[8]
Our Data, Ourselves: Privacy Via Distributed Noise Generation
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our Data, Ourselves: Privacy Via Distributed Noise Generation. In EUROCRYPT, 2006
work page 2006
Show all 20 references
-
[9]
Differential privacy under continual observation
Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing , pages 715–724, 2010
2010
-
[10]
The Algorithmic Foundations of Differential Privacy
Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science , 9(3–4):1–277, 2014
2014
-
[11]
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
Ulfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, and Kunal Talwar. Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. In SODA, 2019
2019
-
[12]
Private counting from anonymous messages: Near-optimal accuracy with vanishing communication overhead
Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Rasmus Pagh. Private counting from anonymous messages: Near-optimal accuracy with vanishing communication overhead. In ICML, 2020
2020
-
[13]
Privacy-Preserving Distributed Learning with Secret Gradient Descent
Valentin Hartmann and Robert West. Privacy-Preserving Distributed Learning with Secret Gradient Descent. Technical report, arXiv:1906.11993, 2019
1906 arXiv
-
[14]
Hosmer, Stanley Lemeshow, and Rodney X
David W. Hosmer, Stanley Lemeshow, and Rodney X. Sturdivant.Applied Logistic Regression. Wiley, New York, 2013
2013
-
[15]
Distributed learning without distress: Privacy-preserving empirical risk minimization
Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning without distress: Privacy-preserving empirical risk minimization. In NeurIPS, 2018
2018
-
[16]
Meyfroidt, F
G. Meyfroidt, F. Güiza, D. Cottem, W. De Becker, K. Van Loon, JM. Aerts, D. Berckmans, J. Ramon, M. Bruynooghe, and G. Van den Berghe. Computerized prediction of intensive care unit discharge after cardiac surgery: development and validation of a gaussian processes model.BMC M...
2011
-
[17]
Provost, T
F. Provost, T. Fawcett, and R. Kohavi. The case against accuracy estimation for comparing induction algorithms. InInternational Conference on Machine Learning , pages 445–453, 1998
1998
-
[18]
Zero knowledge arguments for verifiable sampling
Cesar Sabater and Jan Ramon. Zero knowledge arguments for verifiable sampling. In NeurIPS workshop on Privacy in Machine Learning , 2021
2021
-
[19]
An accurate, scalable and verifiable protocol for federated differentially private averaging, 2021
César Sabater, Aurélien Bellet, and Jan Ramon. An accurate, scalable and verifiable protocol for federated differentially private averaging, 2021
2021
-
[20]
Hubert Chan, Eleanor G
Elaine Shi, T.-H. Hubert Chan, Eleanor G. Rieffel, Richard Chow, and Dawn Song. Privacy-Preserving Aggregation of Time-Series Data. InNDSS, 2011. A Proofs A.1 Proof of Theorem 1 Before proving Theorem 1, we first introduce some additional definitions and lemmas. ForL ∈ N \ {0}...
2011
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.