Pith. sign in

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 →

arxiv 2502.06651 v1 pith:GGXTWSLI submitted 2025-02-10 cs.CR

classification cs.CR
keywords differentialprivacyempiricalcumulativedistributionfunctionfederatedlearningdyadicnoisetreecontinualobservationROCcurveHosmer-Lemeshowstatisticsecretsharing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks whether a full empirical cumulative distribution function can be released while guaranteeing ε-differential privacy, rather than only a single aggregated statistic such as a mean or an area under a curve. It answers yes: by adding Laplace noise organized in a dyadic hierarchy over the evaluation points, the entire curve can be published with privacy budget ε and expected squared error $2(L+1)^3/\epsilon^2$, where $L=\lceil\log_2 N\rceil$ for $N$ curve points. Because each ECDF evaluation is written as a U-statistic, the construction composes with any secure aggregation protocol, and a function-secret-sharing variant lowers communication cost. A post-processing smoothing step restores monotonicity without spending extra privacy budget and often reduces the noise-induced error. If the proof holds, practitioners can choose between a cheap private histogram and a richer, still-private full distribution, with applications to ROC curves and the Hosmer-Lemeshow calibration statistic.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 7 minor

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)
  1. [§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.
  2. [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.
  3. [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.
  4. [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)
  1. [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.
  2. [§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.
  3. [§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.
  4. [§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.
  5. [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.
  6. [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́_φ.
  7. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 3 assumptions · 0 invented entities

The central derivation rests on the Laplace mechanism, standard DP composition and post-processing, and the tree decomposition lemma proven in the paper. The main unstated premise is that the evaluation grid is fixed and public, which the text does not maintain when it ties the grid to φ_min and φ_max. No free parameters are fitted to data, and no new entities are postulated.

assumptions (3)
  • domain assumption The evaluation grid τ is fixed and public, independent of the data.
    Section 3.1's example defines τ from φ_min and φ_max, making it data-dependent, but the proof of Theorem 1 in Appendix A.1 treats τ as a constant vector. The DP claim requires the fixed-grid reading.
  • domain assumption A secure aggregation primitive U Stat exists and hides individual contributions under the chosen attack model.
    Section 4.1 inherits privacy and security from U Stat; the federated algorithms are modular on this building block.
  • standard math Standard composition and post-processing of differential privacy.
    Used for the smoothing step in Section 3.2 and for composing the ECDF and U-statistic budgets in Theorem 2.

how reviews work

0 comments
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 reproduced from arXiv: 2502.06651 by the authors.

Figure 1
Figure 1. ROC curve for logistic regression on the Heart disease dataset, and ϵ-DP curves with ϵ = 0.5. still quite commonly used. It is often used as calibration test for logistic regression, but may also be applied to other machine learning models [16]. While applying a non-decreasing function to the output of a classifier will not change its ROC curve, it will impact its callibration. For models outputting a probability th… view at source ↗
Figure 2
Figure 2. Effect of smoothing on DP error - fixed λ = 3 [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Effect of smoothing on DP error - fixed ϵ = 1 6.4 Evaluating an ECDF or its inverse Starting from the XP ois(λ) dataset, [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Inverse ECDF the unsmoothed differentially private ROC curves cross themselves, it is hard to compare their area with the area of the true ROC curve. 6.6 Hosmer-Lemeshow As for ROC curves, to understand calibration one can both look at the complete picture of the predi…
Figure 5
Figure 5. Figure 5: ROC curve estimation error multi-party computation is available for other operations than U-statistics, a direct approach may be preferable where one first computes securely the correct statistic and then adds noise at the end proportional to the sensitivity of (only) …
Figure 6
Figure 6. Figure 6: Hosmer-Lemeshow statistic relative MSE for a logistic regression model on the Bank dataset compute such private ECDFs. We elaborated in more depth two applications of ECDFs: ROC curves and the Hosmer-Lemeshow statistic. Our experimental results suggest the approach can…
Figure 7
Figure 7. Figure 7: Runtime of solving Eq 3 References 1. Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. Private Summation in the Multi-Message Shuffle Model. In CCS, 2020. 2. Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Dani…
Figure 8
Figure 8. Figure 8: ROC curve for logistic regression on the Bank dataset, and ϵ-DP curves with ϵ = 0.2 [PITH_FULL_IMAGE:figures/full_fig_p023_8.png]
Figure 9
Figure 9. Figure 9: ROC curve for logistic regression on the Diabetic dataset, and ϵ-DP curves with ϵ = 0.05 [PITH_FULL_IMAGE:figures/full_fig_p024_9.png]
Figure 10
Figure 10. Figure 10: Hosmer-Lemeshow statistic MSE for a logistic regression model on the Diabetes dataset [PITH_FULL_IMAGE:figures/full_fig_p024_10.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Dropout-Robust Mechanisms for Differentially Private and Fully Decentralized Mean Estimation

    cs.CR 2025-06 conditional novelty 7.0 of 10

    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

20 extracted references · 20 canonical work pages · cited by 1 Pith paper

  1. [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

  2. [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

  3. [3]

    Function secret sharing

    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

  4. [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

  5. [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

  6. [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

  7. [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

  8. [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

Show all 20 references
  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [14]

    Hosmer, Stanley Lemeshow, and Rodney X

    David W. Hosmer, Stanley Lemeshow, and Rodney X. Sturdivant.Applied Logistic Regression. Wiley, New York, 2013

  7. [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

  8. [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...

  9. [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

  10. [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

  11. [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

  12. [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}...

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.