acceptodds
Under review as a conference paper at ICLR 2027

Near-Optimal Estimation and Inference for Distribution Functions under Local Differential Privacy

Abstract

We estimate population cumulative distribution functions under local differential privacy using independent cycles of dyadic optimized unary encoding reports. An exact grid-approximation modulus yields continuous uniform risk of order under public Hölder regularity. An interactive lower bound establishes optimality up to logarithmic factors on a bounded-density class for . Total-mass-constrained least-squares reconstruction with a symmetric monotone envelope retains this rate. We further establish conditions for studentized pointwise Gaussian limits and construct ordered simultaneous bands with finite-sample or asymptotic coverage guarantees. Ordering band endpoints preserves coverage, whereas recentering pointwise intervals at a monotone estimate can fail. Across four simulated distributions at and , the least-squares estimator reduces mean uniform error by 47–50% relative to one-bit current-status estimation based on Liu, Hu, and Kong (2024). Fixed-grid inference experiments show a 40–43% reduction in mean band width on identical reports.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Distribution, Local differential privacy, Statistical inference, Tree-based mechanism

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_RFisOpenReview ↗
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
AuthorsOpenReview ↗

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<ϵ≤10<\epsilon\le1. 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→∞r_n=\rho_{\epsilon_n}\sqrt n/\lbrace\log(en)\rbrace^{3/2}\to\infty. For fixed true Hölder parameters 0<s∗≤10<s_*\le1, 1≤L∗<∞1\le L_*<\infty and fixed public working values 0<s0≤10<s_0\le1, L0>0L_0>0, the smallest dyadic grid above max⁡{2,(L0rn)1/s0}\max\lbrace 2,(L_0r_n)^{1/s_0}\rbrace has expected loss at most C/rn+L∗L0−s∗/s0rn−s∗/s0.C/r_n+L_*L_0^{-s_*/s_0}r_n^{-s_*/s_0}. The proof controls dyadic rounding and legal user allocation. A fixed error in LL 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=65536n=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\epsilon=1:

ParticipantsDDOUE–LSHR–LSLHK24
1024160.20320.21170.2093
16384640.07990.08630.0949
655361280.04850.05150.0638

At n=65536n=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=524288B=524288 (D=128D=128, ϵ=1\epsilon=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-nn gains answer a different resource question: more informative reports improve precision when the participant pool is fixed.

AuthorsOpenReview ↗

Response to Reviewer RFis (2/2)

Q2. At n=65536n=65536 and ϵ=1\epsilon=1, the original finite-sample rule D=4D0D=4D_0 selects the grids below, where D0D_0 minimizes the public bound over the declared dyadic candidate set. OUE–LS mean continuous sup errors are:

Law(1,0.5)(1,0.5), D=64D=64(1,1.5)(1,1.5), D=128D=128(1,4.5)(1,4.5), D=256D=256(1,10.8)(1,10.8), D=1024D=1024
Uniform0.04830.04530.04510.0486
Spike0.11780.09110.05800.0495
Grid atoms0.02670.03230.03770.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 4D04D_0 differs from the illustrative dyadic rule in W3; for s=1s=1 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 n=8192n=8192 and ϵ=1\epsilon=1, OUE–LS lowers mean continuous error by 10.610.6–12.412.4\\% across the four original laws, with about 21 bits per user against one for LHK24. The reductions grow to 22.722.7–26.626.6\\% at n=131072n=131072 and 46.946.9–50.350.3\\% at n=8388608n=8388608. At n=8192n=8192, D=128D=128, identical-report LS inference reduces mean band width by 4040–4343\\% with simultaneous coverage 94.294.2–96.896.8\\%. In the additional uniform-law experiment at n=1024n=1024 and tree resolution D=16D=16, 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 n=8192n=8192 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.

Reviewer_LEtYOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The authors study the problem of cumulative distribution function estimation under local, pure differential privacy. Establishing Kolmogorov loss bounds in high probability and in expectation, as well as bounds after "studentization". The numerical results compare with a work of Liu et al. [1], showing improved errors.

[1] Liu et al. "Tuning-free estimation and inference of cumulative distribution function under local differential privacy" ICML 2024

Critical strengths

I cannot identify any particular strength of the work, as the method and the main bounds appear to lack novelty, or have unjustified novelty.

Critical weaknesses

The paper is written in an obscure way, preventing a reader to clearly see the contribution and its relation to prior works. In particular, the authors extensively introduce new notation, making it hard to follow the argument or even understand the main theorem. Here are a few examples of obsucure or unnecesery writing.

  1. In Theorem 3.1, it is unclear what is aϵa_{\epsilon}. In the line after the theorem, in the O()O() bound, it is substituted with ρϵ\rho_{\epsilon}, which is technically correct because three pages before aϵa_{\epsilon} was defined as ρϵ/2\rho_{\epsilon} / 2, where ρϵ:=pϵ−qϵ\rho_{\epsilon} := p_{\epsilon} -q_{\epsilon}, where pϵ:=eϵ1−eϵp_{\epsilon} := \frac{e^{\epsilon}}{1 - e^{\epsilon}} and qϵ:=11−eϵq_{\epsilon} := \frac{1}{1 - e^{\epsilon}}. Notation pϵp_{\epsilon} is not used afterwards, qϵq_{\epsilon} is only used a few times, and ρϵ\rho_{\epsilon} is used interchangeably with aϵa_{\epsilon}. All of it could be avoided by just writing the corresponding expressions of ϵ\epsilon.

  2. In equation (4) the notation Yi,jY_{i,j} is not defined.

  3. In equation (7) the notation p^b,j\hat{p}_{b,j} is not defined.

  4. It is unclear what does the Definition 2.1 define.

  5. Line 96 "Our protocol is noninteractive; allowing interaction in the lower bound makes the comparison stronger.", which lower bound? why does it make the comparison stronger? Why don't you compare with the interactive mechanism of Aamand et al. [3]?

  6. As an example of unnecessary writing, those are two line from the end of the introduction "The rest of the paper is organized as follows. Sections 2–4 present the method, theory and experiments; Section 5 concludes. The appendices collect implementation details, further results and proofs". The same text could apply to 90% of all ICLR papers, there is nothing specific about the work mentioned there.

My general impression is that the paper is build upon the work of Cormode et al. [1], reusing their notation and constructions. It is unclear whether any of the bounds in the paper are novel, or cannot be trivially obtained by the Cormode et al. [1] or Edmonds et al. [2] or Liu et al. [4].

Importantly, the authors claim novelty, or at least reusing the name TreeOUE for their method, which was already introduced in Cormode et al.. Please clarify the novelty of your method and avoid reusing the same names.

[1] Cormode et al. "Answering Range Queries Under Local Differential Privacy" VLDB 2019

[2] Edmonds et al. "The power of factorization mechanisms in local and central differential privacy" STOC 2020

[3] Aamand et al. "Lightweight Protocols for Distributed Private Quantile Estimation" ICLM 2025

[4] Liu et al. "Tuning-free estimation and inference of cumulative distribution function under local differential privacy" ICML 2024

Questions for authors

I do not have any particular questions, please comment on the weaknesses that I have mentioned.

3 comments
AuthorsOpenReview ↗

Response to Reviewer LEtY

Thank you for your time and valuable comments.

W1. Here qϵ=(1+eϵ)−1q_\epsilon=(1+e^\epsilon)^{-1} is the false-bit probability, aϵ=1/2−qϵ=tanh⁡(ϵ/2)/2a_\epsilon=1/2-q_\epsilon=\tanh(\epsilon/2)/2 is the OUE contrast used in decoding, and ρϵ=2aϵ=tanh⁡(ϵ/2)\rho_\epsilon=2a_\epsilon=\tanh(\epsilon/2) is the randomized-response contrast used for comparison with LHK24. The OUE true-category bit has success probability 1/21/2; the denominators are 1+eϵ1+e^\epsilon. pϵp_\epsilon is defined locally where binary randomized response is used. Retaining aϵa_\epsilon and ρϵ\rho_\epsilon distinguishes these two channel contrasts without repeatedly expanding the exponential expression; the explicit formula for aϵa_\epsilon is also recalled at Theorem 3.1.

W2. We define Yi,j∈{0,1}Y_{i,j}\in\lbrace 0,1\rbrace as coordinate jj of user ii's released level-rr OUE vector Yi=(Yi,1,…,Yi,2r)\boldsymbol Y_i=(Y_{i,1},\ldots,Y_{i,2^r}). Conditional on the user's true level-rr category cc, the released bits are independent, with Pr⁡(Yi,j=1∣c)=1/2\Pr(Y_{i,j}=1\mid c)=1/2 for j=cj=c and Pr⁡(Yi,j=1∣c)=qϵ=(1+eϵ)−1\Pr(Y_{i,j}=1\mid c)=q_\epsilon=(1+e^\epsilon)^{-1} otherwise.

W3. Here p^b,j\widehat p_{b,j} is coordinate jj of the fitted leaf-mass vector p^b\widehat{\boldsymbol p}_b in (7). The fitted masses satisfy the total-mass constraint and can be signed.

W4. Definition 2.1 specifies the conditional privacy inequality for each report given the preceding transcript; noninteraction is the special case without dependence on previous private reports. It is titled “Sequential local differential privacy.”

W5. Theorem 3.4 is the lower bound for continuous uniform loss over bounded-density CDFs. Its infimum includes sequentially interactive protocols, a larger class containing all noninteractive protocols. Its impossibility conclusion therefore applies even when interaction is available; the noninteractive upper bound matches it up to logarithmic factors on the stated class for 0<ϵ≤10<\epsilon\le1.

Aamand et al. (2025) provide two relevant results. Their Appendix D analyzes a nonadaptive hierarchical whole-CDF estimator, with sample complexity O((log⁡B)3/(ϵ2α2))O((\log B)^3/(\epsilon^2\alpha^2)) for simultaneous error α\alpha on [B][B] in the small-privacy regime. This establishes the matching finite-grid logarithmic order. Their Theorem 1.1 instead estimates one empirical quantile using fresh sequentially queried users, each sending one bit. An error benchmark for a reusable one-round population-CDF release with simultaneous uncertainty would not be a like-for-like evaluation of that single-quantile protocol. Their Appendix F.2 reduction uses success amplification with composed privacy, and their Appendix H treats continuous inputs with known cutpoints controlling empirical CDF increments. The distinct targets do not imply that their single-quantile result is contradicted by our CDF lower bound.

W6. We removed the generic paragraph listing the subsequent section numbers.

W7. Hierarchical reporting and LS consistency are established by Cormode et al.; Edmonds et al.'s factorization and Aamand et al.'s Appendix D give the finite-grid logarithmic-order upper rate. These results supply the reporting and finite-grid rate ingredients. Corollary 3.3 requires an additional reconstruction-specific step: minimizing a nodewise LS residual does not itself bound every prefix's linear coefficients or its sup-norm error uniformly in the grid size. The proof controls those coefficients and their weighted OUE moment-generating function for the total-mass-constrained affine map, then adds the exact continuous approximation modulus.

The inference analysis concerns raw pointwise studentization, growing-grid canonical calibration, fixed-grid LS calibration, and coverage-preserving ordering of band endpoints. The recentering counterexample distinguishes a shape-valid point estimate from a valid pointwise interval center. LHK24's continuous-threshold estimator and designated-point Gaussian limits concern different reconstructed statistics; they do not supply the covariance calibration for these cycle scores or justify recentering them after shape correction. Fixed-grid Gaussian calibration here still uses standard affine unbiasedness, positive variances and a fixed-dimensional limit. The bounded-density lower bound combines the stated CDF construction with established sequential-privacy contraction tools.

W8. TreeOUE is Cormode et al.'s (2019) name; we keep it to signal that the hierarchical OUE reporting mechanism is theirs. We arrange its reports into independent cycles for inference. TreeOUE–LS denotes the total-mass-constrained least-squares reconstruction and symmetric-envelope estimator, not a new privatization mechanism.

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

Thank you for your time and thoughtful reply!

I made another quick pass on the updated manuscript, I appreciate that you have fixed a few issues that I have mentioned, but the problem with the quality of the writing is more systematic. For instance, in the current version, the very first sentence of the abstract goes:

"We estimate population cumulative distribution functions under local differential privacy using independent cycles of dyadic optimized unary encoding reports."

For a reader familiar with statistics and local differential privacy it would still be unclear what is "independent cycles of dyadic optimized unary encoding reports". One could, of course, learn it by reading the whole paper, but it is not a high quality exposition. Thus, I remain my opinion that the manuscript writing is below the expected quality for publication.

Regarding the novelty, I understood that there are technical differences to the previous works, there are improvements on certain metrics. However, I cannot judge the significance of the novelty, as I do not find the writing clear enough. Thus, I remain my score.

Thank you for rereading the manuscript and illustrating your concerns with a concrete example. We value your perspective on how to introduce the work more clearly to readers. Your comments give us useful guidance for improving the exposition, and we appreciate the care you have taken in the review.

Reviewer_UvmrOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

To address the estimation problem of the overall cumulative distribution function under local differential privacy, this paper proposes a total mass-constrained least squares reconstruction scheme based on precise mesh approximate modulus and band-symmetric monotonic envelope, and constructs an ordered synchronous band with coverage guarantees. This scheme achieves the optimal order of continuous uniform risk under common Hölder regularity, theoretically demonstrating that sorted band endpoints can effectively maintain coverage. Experiments show that under large-scale data (n≈8.4×106,ϵ=1n \approx 8.4 \times 10^6, \epsilon=1), this method reduces the average uniform error by 47–50% and the average bandwidth width by 40–43%.

Critical strengths
  1. The Independent Cycles structure proposed by the author is a very good design. By grouping users and assigning them to different levels of a binary tree, it allows reports from the same user to be safely reused across multiple prefix queries, while keeping different cycles completely independent.
  2. The paper clearly points out and empirically validates that using a symmetric monotone envelope for point estimation is safe, but "recentering" confidence intervals can severely harm coverage (dropping from 96.2% to 63.8% in experiments). The author proposes an alternative of ordering the confidence band endpoints, which maintains monotonicity while ensuring correct statistical coverage.
Critical weaknesses
  • The core contribution of this paper is unclear. The locally private hierarchical queries and least squares consistency reconstruction used in this paper have already been discussed by Cormode et al. (2019). Although this paper provides covariance estimation, error control after LS reconstruction, and inference under shape constraints, it does not sufficiently clarify which of these results require new techniques and which are direct consequences of combining existing mechanisms with standard concentration inequalities or fixed-dimension central limit theorems.
  • The main method of the paper, TreeOUE, uses OUE by default, which has a reported length of 2r2^r bits. When the hierarchy level r is large (for example, r=20 corresponding to a million-level grid), the communication cost per user becomes unacceptable. Although the paper mentions Hadamard Response (HR) as a low-communication alternative, it does not provide a systematic analysis of the communication-accuracy trade-off between OUE and HR at different hierarchy levels. Furthermore, LS reconstruction significantly reduces error and bandwidth, but the experiments do not fully report communication and computation costs, nor performance in both simple and complex scenarios such as sparse distributions or small samples.
  • The paper theoretically discusses finite-sample error decomposition for arbitrary distributions and proves corresponding convergence rates for distribution classes satisfying Hölder regularity. However, the main continuous-domain estimation experiments use four bounded and relatively regular simulated distributions, which do not sufficiently cover continuous-domain estimation performance under discrete, multi-peak, spiky, or heavily skewed distributions.
  • The main continuous uniform error experiments focus on comparing LHK24's continuous threshold and preselected grid versions, as well as internal variants of the proposed method. Meanwhile, the related work section lists various hierarchical, wavelet, and adaptive distribution reconstruction methods. The paper does not experimentally distinguish whether the performance improvements come from hierarchical reporting, LS reconstruction, grid selection, or a combination of these factors.
  • There are some minor writing issues. For example, in Appendix A.1, the 'for each x' has no specific ending (Line 609). 'Representing a continuous CDF' can be easily misunderstood as requiring the CDF to be continuous, but immediately afterward, Theorem 3.1 explicitly applies to arbitrary distributions, including atomic distributions. Here, 'continuous domain' and 'continuous function' should be clearly distinguished (Lines 244–245).
Questions for authors

Refer Critical Weaknesses

2 comments
AuthorsOpenReview ↗

Response to Reviewer Uvmr (1/2)

Thank you for your time and valuable comments.

W1. The statistical contribution is a reusable population-CDF release with reconstruction and joint uncertainty guarantees. Hierarchical range reporting, the TreeOUE name and least-squares consistency come from Cormode et al. (2019); we arrange their reports into independent cycles. Hoeffding grid bounds and fixed-grid affine-LS Gaussian calibration use standard concentration and fixed-dimensional central limit arguments. The reconstruction-specific step is to control all LS prefix coefficient norms uniformly as resolution grows: a smaller least-squares residual alone does not control continuous sup loss. The analysis also retains the exact grid-approximation modulus, calibrates growing-grid canonical scores under its stated conditions, and gives a recentering counterexample. Shaping an estimate can invalidate pointwise recentering even when it contracts uniform error, whereas ordering band endpoints preserves simultaneous coverage. The lower bound combines localized CDF deviations with established sequential-privacy contraction and Fano tools. LS Gaussian coverage remains a fixed-grid result.

W2. We ran additional comparisons for three practical questions: precision with a fixed participant pool, precision with fixed total uplink bits, and decoding cost. At n=65536n=65536 and ϵ=1\epsilon=1, with LS and the symmetric envelope for both channels, mean continuous sup errors and average report lengths are:

LawDDOUE–LSHR–LSOUE bitsHR bits
Uniform1280.04530.048736.295
Uniform5120.04630.0509113.566
Spike1280.09110.090736.295
Spike5120.05100.0535113.566

This resolution study uses 256 replications with random streams independent of the reconstruction/robustness study in W3–W4. Both studies use the same frozen estimator and tuning rules. A balanced tree uses J⌊n/J⌋J\lfloor n/J\rfloor participants from the available pool, whereas LHK24 uses all nn.

HR thus cuts communication sharply at similar accuracy. At D=220D=2^{20}, OUE averages (2D−2)/20=104857.5(2D-2)/20=104857.5 bits per participating user and has a maximum of 1048576 bits; HR averages (20+3)/2=11.5(20+3)/2=11.5 bits and has a maximum of 21 bits. Under a fixed total budget of 524288 uplink bits at D=128D=128, uniform-law errors are 0.0796 for OUE–LS, 0.0417 for HR–LS and 0.0314 for continuous-threshold LHK24, since shorter messages admit more participants. The aggregate LS decoder takes O(D)O(D) time, with median single-thread decode times 0.053, 0.078, 0.116 and 0.360 ms at D=32,128,512,2048D=32,128,512,2048; full prefix-covariance storage takes O(D2)O(D^2) memory. For the uniform law at n=1024n=1024, ϵ=1\epsilon=1 and tree resolution D=16D=16, OUE–LS, HR–LS and continuous-threshold LHK24 have errors 0.1918, 0.1985 and 0.1874 in the robustness batch, respectively, and the submitted experiment shows gains from n=8192n=8192, with same-report band-width reductions of 4040–4343\\%.

W3. Additional runs at n=65536n=65536 and ϵ=1\epsilon=1 use the original public rule (s,L)=(1,1.5)(s,L)=(1,1.5), frozen comparator tuning and a common available participant pool:

LawOUE–LSHR–LSLHK24
Bimodal0.06460.06880.0860
Spike0.08990.09180.0844
Beta(0.35,1)0.18300.18300.1000
Grid atoms0.03160.03410.3774
Off-grid atoms0.48150.48020.3773
Beta(8,1)0.07330.07500.0905

The bimodal law is 0.45,Unif(0.15,0.25)+0.55,Unif(0.65,0.80),0.45\\,\mathrm{Unif}(0.15,0.25)+0.55\\,\mathrm{Unif}(0.65,0.80), and the spike is 0.8,Unif(0,1)+0.2,Unif(0.49,0.51).0.8\\,\mathrm{Unif}(0,1)+0.2\\,\mathrm{Unif}(0.49,0.51). The atomic laws put masses (0.25,0.5,0.25)(0.25,0.5,0.25) at (0.25,0.5,0.75)(0.25,0.5,0.75) or (0.17,0.52,0.91)(0.17,0.52,0.91). Resolution effects follow the exact approximation modulus: the fixed working grid gives error 0.1830 for Beta$(0.35,1)$, exactly its first-cell mass, and large error for off-grid atoms.

AuthorsOpenReview ↗

Response to Reviewer Uvmr (2/2)

W4. A same-report, same-grid ablation at n=65536n=65536, D=128D=128, ϵ=1\epsilon=1 isolates reconstruction and shape correction ("C" canonical decoding, "max" cumulative maximum, "sym" symmetric envelope):

LawC + maxC + symLS + maxLS + sym
Uniform0.09080.08010.04820.0458
Bimodal0.10520.10140.06520.0646
Off-grid atoms0.42670.46310.46380.4815

Under uniformity the envelope alone reduces error by 11.8% and LS alone by 46.9%; with the symmetric envelope fixed, LS reduces it by 42.9%. These percentages use the unrounded replication means. For off-grid atoms, approximation bias reverses the ranking. The submitted n=8192n=8192, D=128D=128 experiment isolates reconstruction on identical reports: mean band widths decrease by 4040–4343\\% with simultaneous coverage 94.294.2–96.896.8\\%. At the same participant budget, flat OUE gives uniform-law error 0.0746 against 0.0458 for hierarchical OUE–LS. W2 varies DD from 128 to 512 at fixed nn and decoder/envelope, separating resolution from reconstruction: the spike improves substantially while uniform-law error changes little. Flat OUE is a same-grid control, not a reproduction of adaptive-tree or wavelet estimators; these experiments do not rank all such methods.

W5. The loop terminator is displayed as end for. We replace “representing a continuous CDF” by “approximating a CDF across the full interval” and use “For any right-continuous CDF FF” before (29). The reporting domain is continuous, but the population CDF may have jumps. The finite-sample bounds retain the exact approximation modulus for arbitrary distributions; the rate corollaries additionally use Hölder regularity.

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.