- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper proposes a noninteractive LDP method for estimating an entire population CDF. It aims to support arbitrary threshold queries chosen after data collection while also enabling statistical inference. The proposed approach combines a dyadic hierarchy, optimized unary encoding, and independent cycles to reuse private reports across thresholds and estimate their joint covariance structure. The theoretical results include a continuous uniform error rate and a minimax lower bound, establishing near-optimality up to logarithmic factors. LS reconstruction and monotonicity enforcement are also considered to obtain a valid CDF without sacrificing the uniform rate. The paper further addresses pointwise and simultaneous inference separately from shape-constrained point estimation.
Critical strengths
- Proposes a method for releasing an entire population CDF under LDP while supporting thresholds chosen after data collection, rather than answering only a prespecified finite collection of queries.
- Address both estimation and inference. The independent-cycle construction provides repeated estimates of the entire curve and an estimable covariance structure.
- Provides near-optimal theoretical results, with a lower bound that allows arbitrary message and sequentially interactive LDP protocols.
Critical weaknesses
- The paper is difficult to follow, especially the introduction, unless readers are already very familiar with the area. It becomes technical too quickly without clearly defining key terms, providing a big picture view, or sufficiently motivating the problem. In addition, the positioning of the proposed method within the existing literature and its main contributions are not clearly presented. It is difficult to determine which components are new and in what sense they are novel. The related work discussion does not sufficiently clarify these issues. Thus, readers have to do much work to understand the paper, and the presentation is not sufficiently self-contained.
- The meaning and practical relevance of the assumptions are not sufficiently discussed. The theoretical results are substantial, but their statistical meaning and relationships to one another are not fully explained.
- The method requires public regularity information to select the resolution needed to attain the claimed uniform rate. The practical consequences of misspecifying the public Hölder condition are not explored.
- The simulation study does not sufficiently examine robustness. For example, it does not consider various types of distributions or density bounds larger than assumed. In addition, the empirical comparison with Liu et al. does not equalize communication costs.
- A real data analysis, which would help demonstrate the practical usefulness of the proposed method, is missing. The paper mentions taxi pickup times as a motivating example in the introduction, but does not provide a corresponding real data application.
Questions for authors
- How should the comparison with Liu et al. be interpreted, given the substantially different communication requirements? Could the authors provide an error vs. communication comparison, or compare the methods under a common communication budget?
- What are the practical consequences of misspecifying the public Hölder condition? How sensitive is the proposed method to the choice of the regularity parameters?
- The sample sizes used in the simulations are quite large, and the improvement over the current status method becomes more apparent as the sample size increases. At what sample size and communication cost does the proposed method become practically worhwhile?
4 comments
Response to Reviewer RFis (2/2)
Q2. At and , the original finite-sample rule selects the grids below, where minimizes the public bound over the declared dyadic candidate set. OUE–LS mean continuous sup errors are:
| Law | , | , | , | , |
|---|---|---|---|---|
| Uniform | 0.0483 | 0.0453 | 0.0451 | 0.0486 |
| Spike | 0.1178 | 0.0911 | 0.0580 | 0.0495 |
| Grid atoms | 0.0267 | 0.0323 | 0.0377 | 0.0499 |
This table uses 256 replications per condition from the resolution-study batch, independent of the robustness batch in W4. A finer grid improves approximation where it matters, at a cost in noise and communication. The numerical rule differs from the illustrative dyadic rule in W3; for and fixed positive envelope values, the finite-sample minimization rule also retains the stated asymptotic rate.
Q3. The submitted experiment shows a useful finite-sample regime: at and , OUE–LS lowers mean continuous error by – across the four original laws, with about 21 bits per user against one for LHK24. The reductions grow to – at and – at . At , , identical-report LS inference reduces mean band width by – with simultaneous coverage –. In the additional uniform-law experiment at and tree resolution , OUE–LS, HR–LS and LHK24 errors are 0.1918, 0.1985 and 0.1874: there is no small-sample tree advantage in that setting. The observed gains from concern the four original laws at fixed participants and about 21 OUE bits per user. When total bits instead limit recruitment, LHK24 is preferable for both continuous laws in Q1. These results identify tested operating regimes, not a universal sample-size crossover.
Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.
I appreciate the authors' detailed responses and additional analyses. They have addressed some of my concerns. However, my primary concern was the presentation of the paper (W1 and W2), which may require substantial revision and at least another round of review to assess properly. In addition, the novelty of the proposed method compared to existing work still needs to be clarified. The new results also show that LHK24 outperforms the proposed method on some of the distributions considered under a fixed total communication budget, which may require further investigation. Therefore, I have decided to maintain my original score.
We appreciate your further assessment and the attention you have given to both the paper and the additional analyses. We respect your judgment. The discussion has helped us clarify the contribution and improve how the comparisons are presented. Thank you for your time and valuable feedback.
Response to Reviewer RFis (1/2)
Thank you for your time and valuable comments.
W1. The task is to release one private curve that answers thresholds chosen after collection and quantifies their joint uncertainty. A hierarchy reuses noisy reports across prefixes, LS reconciles redundant node estimates, and repeated cycle scores make their covariance estimable. Inference then differs from point estimation: monotone correction can improve a curve's uniform error while moving an individual prefix by more than its standard error; ordering band endpoints preserves simultaneous coverage. Hierarchical reporting and LS come from prior work. The finite-grid whole-CDF logarithmic order is established in Aamand et al.'s (2025) Appendix D.
W2. The public interval specifies the reporting domain, and independent observations with a common law make the cycle scores i.i.d. The finite-sample bound applies to arbitrary CDFs through stochastic error plus the actual approximation modulus. Public Hölder regularity controls that modulus and selects a rate-attaining resolution; the same uniform rate transfers to affine LS through its coefficient bound. The lower bound uses a narrower bounded-density class and allows sequential interaction for 0<ϵ≤1. Pointwise Gaussian inference additionally requires sufficient Bernoulli information and off-grid bias negligible relative to the standard error, or a valid explicit bias bound. Ordering band endpoints transfers simultaneous grid coverage to the continuum using CDF monotonicity. Growing-grid Gaussian calibration is proved for canonical scores; LS Gaussian coverage remains fixed-grid. We will add this explanation of the task and of the role of each assumption to Section 2 of the final version.
W3. Public misspecification has the following consequence for both canonical and affine-LS reconstruction. Write rn=ρϵnn/{log(en)}3/2→∞. For fixed true Hölder parameters 0<s∗≤1, 1≤L∗<∞ and fixed public working values 0<s0≤1, L0>0, the smallest dyadic grid above max{2,(L0rn)1/s0} has expected loss at most C/rn+L∗L0−s∗/s0rn−s∗/s0. The proof controls dyadic rounding and legal user allocation. A fixed error in L at the correct exponent preserves the rate; a conservative exponent shrinks the approximation term at a communication cost; an overly large exponent gives the slower displayed upper bound, not a matching lower bound. The ordered Hoeffding band covers for any legal grid fixed before collection, since it uses CDF order rather than a bias estimate.
W4. We evaluated additional laws beyond the working density envelope 1.5: the bimodal, spike and Beta$(8,1)$ densities reach 4.5, 10.8 and 8, and Beta$(0.35,1)$ is unbounded. At n=65536, OUE–LS improves on continuous-threshold LHK24 for the bimodal and Beta$(8,1)$ laws (0.0646 vs 0.0860; 0.0733 vs 0.0905), while the narrow spike and first-cell singularity expose approximation bias: the corresponding OUE–LS/LHK24 errors are 0.0899/0.0844 and 0.1830/0.1000.
W5. We ran a benchmark on the January 2024 NYC yellow-taxi pickup-time distribution (2964606 pickups), resampling independently from this fixed empirical CDF before privatization; one resampled pickup is the privacy unit. Mean continuous sup errors at ϵ=1:
At n=65536 OUE–LS has about 24% lower error than LHK24, with average reports of 36.29, 5 and 1 bits.
Q1. Fixing total uplink bits at B=524288 (D=128, ϵ=1) lets each method use as many one-report participants as the budget permits: 14448 for OUE, 104853 for HR and 524288 for LHK24. Uniform-law errors are 0.0796, 0.0417 and 0.0314; bimodal 0.0988, 0.0615 and 0.0464; grid atoms 0.0700, 0.0273 and 0.3682. HR substantially improves the tree's efficiency under this constraint, and LHK24 is more accurate for both continuous laws shown here in this budget-limited regime. The submitted fixed-n gains answer a different resource question: more informative reports improve precision when the participant pool is fixed.