acceptodds
Under review as a conference paper at ICLR 2027

Decentralized Locally Private Inference for Quantiles

Abstract

We study quantile inference under local differential privacy for heterogeneous data streams distributed over a peer-to-peer network without a trusted central server. The proposed procedure targets a weighted mixture quantile using one-bit randomized-response scores and blockwise gossip, with each observation processed once and communication restricted to neighboring nodes. The main challenge is that incomplete synchronization creates persistent network disagreement that interacts with discontinuous quantile scores. We derive graph-dependent error bounds and establish asymptotic normality and a functional central limit theorem for the spatial–temporal average under suitable mixing and growth conditions. These results yield self-normalized confidence intervals without estimating the mixture density or the privacy-inflated score variance. Under stronger balance conditions, node-wise temporal averages inherit the same first-order limits, enabling inference from a single node's trajectory without additional network-wide aggregation. Numerical experiments and a real-data application examine the effects of privacy, communication frequency, and network connectivity on estimation and inference.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Chung-type law, Decentralized learning, Differential privacy, Quantile, Self-normalized inference

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_GtrMOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the problem of quantile estimation under LDP. The problem assumes there are K nodes, where each node kk receives a stream of elements i.i.d. from a distribution PkP_k with CDF FkF_k. Each node also has a weighting factor pkp_k and its own quantile level τk\tau_k. The target is to find the element Q∗Q* which satisfies F(Q∗)=τF(Q*)=\tau, where F(q)=∑kpkFk(q)F(q)=\sum_{k} p_kF_k(q) is the weighted mixture distribution, and τ=∑kpkτk\tau=\sum_{k}p_k\tau_k is the global quantile level. The solution borrows idea from Liu et al. (2023): the quantile inference problem is converted to an optimization problem with quantile value qq as a parameter, where the objective function depends on the indicator of whether the received element is less than qq. The indicator is released using randomized response, and debiased for SGD updates. The difference is that this paper considers a decentralized setting, so that aggregations are also performed locally through a P2P network.

Overall, I find the problem important and the paper provides detailed theoretical analysis under reasonable assumptions. However, I have concerns on the practical meaning of its problem formulation, consistency between the algorithm and the theoretical result, comparison to existing result, and the limited scale of its experimental evaluation. Therefore, I am leaning towards weak rejection.

Critical strengths

S1. The problem studied is fundamental. The algorithm design is clean and easy to implement.

S2. The paper provides detailed theoretical analysis while listing all its assumptions, which justifies its technical contribution.

Critical weaknesses

W1. The problem definition assumes that each node has its own quantile level τk\tau_k. It is unclear what the practical meaning is for this setting. As mentioned in the first paragraph, median (50%) and tail (e.g. 99%) quantiles typically adopt a common threshold across all nodes. There should be more explanation on the practical meaning of considering a separate threshold for each node, and the meaning of the final threshold as their weighted sum.

It is true that setting τk=τ\tau_k=\tau for all kk reduces the algorithm to the common-quantile setting, but then the separation from Liu et al. (2023) seems minor. The prior work also assumes a common τ\tau and works under LDP, and many algorithmic components of this paper are from the prior work. The paper should clearly compare against it and emphasize any differences under the setting of homogeneous τk\tau_k's.

Meanwhile, if each node adopts a different τk\tau_k, then τk\tau_k itself may cause a privacy leakage. In particular, this paper does not contain any definition for neighbors in DP, nor privacy proofs. While its privacy perturbation technique follows Liu et al. (2023), the privacy claim is incomplete without a formal definition. For example, do neighboring instances differ by a timestamp or the entire stream? This cannot be inferred from Definition 2.

W2. The parameter domain Θ\Theta must be more carefully coped with.

W2.1. In Equation (1), the paper mentions that the unique solution to F(Q∗)=τF(Q*)=\tau is equivalent to the minimizer of the objective function, but there are missing assumptions and discussions here:

  • Are there assumptions for the solution to exist and being unique?
  • The equivalence only holds if Q∗∈ΘQ*\in \Theta.
  • Missing derivation for this equivalence. For example, when considering empirical quantiles (i.e. when FkF_k is discrete), there can be no solution to F(Q∗)=τF(Q*)=\tau, and the solution may not be unique even if it exists; but there can be a minimizer for Equation (1).

W2.2. Assumption 1 assumes that the interval Θ\Theta is compact, and all subsequent analyses are based on it. However, Θ\Theta is not an input parameter to Algorithm 1, therefore it is unclear whether the analyses in Section 3 works for Algorithm 1. It is also unclear whether the updating step in Line 5 of Algorithm 1 preserves the membership of qk,t∈Θq_{k,t}\in \Theta, even if q0q_0 is initialized as an element from Θ\Theta.

W3. In line 181, there is no derivation for the complicated update rule for q_{k,t}. It is unclear why the update involves the number of sites KK and pkp_k.

W3.1. The authors should also compare with the update rule in Liu et al. (2023) to identify which parts are contributions from this paper.

W3.2. The communication graph G and W should be better explained. In particular, they should be part of the problem formulation instead of the algorithm description. I assume that the difference from Liu et al. (2023) is that G is not a clique, but since both algorithms are LDP, any computation on g_{k,t}(q) is post-processing, which can be done using any graph aggregation algorithm without requiring a centralized aggregator. It is unclear to me whether the aggregation in the prior work cannot be performed, or whether there are particular improvements from this new updating function.

W4. Experiments only considered K=7 or 10 nodes, whose scale is relatively small. The paper should also compare with Liu et al. (2023), to demonstrate the overhead (if any) in considering the decentralized setting compared to a centralized setting.

Questions for authors

For W1, what is the practical meaning of considering heterogeneous τk\tau_k's and their weighted average?

What is the definition for neighboring instances in this paper?

For W2, how does Algorithm 1 ensure it only considers parameter q∈Θq \in \Theta? Any specific examples for Θ\Theta?

For W3, can the algorithm in Liu et al. (2023) be combined with a graph aggregation to work in the proposed decentralized case, or are there fundamental separations?

6 comments

Thank you for your time and valuable comments.

W1. The target is one common threshold for the mixture distribution, at level τ=∑kpkτk\tau=\sum_kp_k\tau_k. Public heterogeneous levels can encode different asymmetric costs for that common decision, while a common median or tail level is obtained by setting every τk=τ\tau_k=\tau. Their effect on the target is entirely through this weighted level. The threshold is a mixture quantile: for .75,U(0,1)+.25,U(10,11).75\\,U(0,1)+.25\\,U(10,11) the median is 2/32/3, whereas the weighted average of the local medians is 33.

The same finite-gossip disagreement and node-transfer problem remains when all levels coincide. We credit Liu et al. (ICML 2023) for the private scalar recursion and Cai et al. (ICLR 2026) for the accumulator updates and empirical decentralized extension; our theoretical results characterize inference under incomplete synchronization. The levels, node membership, weights and communication schedule are public. The added transcript guarantee protects replacement of one record at a fixed node and time; private levels or an entire user's multi-record stream would require the corresponding additional privacy protection.

W2. We have specified the target and the role of Θ\Theta separately. The objective is the anchored contrast

L(q)=∑kpkEρτk(Xk−q)−ρτk(Xk−qref),ρa(u)=ua−1(u<0).L(q)=\sum_kp_k\mathbb E\\{\rho_{\tau_k}(X_k-q)-\rho_{\tau_k}(X_k-q_{\rm ref})\\},\qquad \rho_a(u)=u\\{a-\mathbf1(u < 0)\\}.

The subtraction is inside the expectation, and the absolute contrast is bounded by ∣q−qref∣|q-q_{\rm ref}|, making it finite for the Cauchy example as well. Its subgradient is ∂L(q)=[F(q−)−τ,F(q)−τ]\partial L(q)=[F(q-)-\tau,F(q)-\tau]. For a continuous CDF, the derivative is F(q)−τF(q)-\tau; endpoint bracketing and positive mixture density give a unique interior root. We now state the uniform interior margin explicitly. For a discrete distribution, minimizers satisfy F(q−)≤τ≤F(q)F(q-)\le\tau\le F(q), allowing ties and nonuniqueness.

Algorithm 1 is defined on the real line and uses Θ\Theta as a regularity neighborhood. The revised cosh-Lyapunov proof controls excursions of the unprojected recursion, establishes the quantitative MSE, and supplies the uniform Abel bound needed by the FCLT. It uses the explicit root, initialization, independence and step-variation assumptions. Thus the analysis follows the displayed algorithm, with no projection step added.

W3. The factors KpkKp_k calibrate the local updates to the intended weighted mixture. Conditional on the past, the mean of the local-update changes is

η∑kpkτk−Fk(qk),\eta\sum_kp_k\\{\tau_k-F_k(q_k)\\},

which equals ητ−F(q)=−ηL′(q)\eta\\{\tau-F(q)\\}=-\eta L'(q) at consensus. The factor KK cancels the 1/K1/K in the arithmetic network mean, and double stochasticity preserves that mean during gossip. Removing pkp_k generally changes the target; removing only KK rescales the gain.

Complementing the threshold bit and using local gain ηKpk/rk\eta Kp_k/r_k recovers the scalar construction from Liu et al. (2023). We now introduce the graph and compatible mixing matrix with the problem formulation, and credit the inherited private update. Previously privatized scores can be aggregated over a graph through postprocessing. Our analysis addresses the remaining statistical error when only finite gossip is performed and local thresholds differ. Complete synchronization is included through W=JW=J; the graph need not exclude a clique.

W4. The submitted full tables include K=30K=30, K=50K=50 and sparse-network comparisons. We directly implemented Liu et al. (2023), Algorithm 2, for the homogeneous pooled iid stream, using its per-record averaging and ordinary-clock normalizer. Its deterministic gain matches the aggregate update scale of each decentralized schedule. CENT evaluates the KK fresh-record scores at a common query, updates it after each observation batch, and averages temporally at decentralized block endpoints.

For the standard-normal median with K=10,r=.25K=10,r=.25 and N=200,000N=200{,}000 per node:

Gain matched toCoverage (Network/Liu)MAE (Network/Liu)Length (Network/Liu)
C10.942/0.9440.002796/0.0027950.017245/0.017255
C50.926/0.9260.002837/0.0028410.016570/0.016558
P150.922/0.9240.003016/0.0028810.017213/0.016284

C1/C5 closely track the Liu implementation in error and interval size. For P15, the network interval is about 5.75.7\\% longer and MAE about 4.74.7\\% higher, reflecting the different clock and averaging rule. In homogeneous upper-tail setting B under P15, both coverages are 1.0001.000, while network/Liu MAE is .0054/.0026.0054/.0026 and length .0423/.0201.0423/.0201; these comparisons retain that configuration's statistical cost. The synchronized comparison in the heterogeneous K=50K=50 case gives network/CENT coverage .902/.904.902/.904 under C1 and .880/.874.880/.874 under C5.

Communication benefits are coordinator removal and fewer gossip rounds with longer blocks: C5 and P15 use 8080\\% and 85.785.7\\% fewer rounds than C1 at this budget. With one directed state message per neighbor per gossip round, peer transmissions are 2∣E∣T=KdT2|\mathcal E|T=KdT; two gossip steps per block use 2KdT2KdT. Under unicast query–response, the implemented CENT comparator uses KNKN threshold-query messages and KNKN responses, totaling 2KN2KN. A hypothetical server gathering and broadcasting only at block endpoints would use 2KT2KT messages; it performs a different recursion when Em>1E_m > 1. These counts distinguish interaction patterns; payloads and latency depend on implementation. Literal Liu processes KNKN sequential records with per-record averaging.

Q1. Heterogeneous public levels describe different asymmetric costs attached to a shared threshold. The target remains the quantile of F=∑kpkFkF=\sum_kp_kF_k at τ=∑kpkτk\tau=\sum_kp_k\tau_k. For a common median or tail probability, identical levels are the natural default. We clarify this interpretation and distinguish it from the weighted average of local quantiles. The theory's finite-gossip and node-inference contributions also apply to common levels.

Q2. Adjacent complete data arrays differ in one record's value at a fixed node and time. Node membership, weights, levels, privacy parameters, graph, schedule and initialization are public and fixed. This is replacement-event privacy.

Given any fixed transcript history, both arrays yield the same adaptive query. The changed record's channel likelihood ratio is at most (1+rk)/(1−rk)(1+r_k)/(1-r_k), and all other conditional factors cancel. Postprocessing therefore gives the full message and interval transcript the guarantee εk=log⁡(1+rk)/(1−rk)\varepsilon_k=\log\\{(1+r_k)/(1-r_k)\\} for rk<1r_k < 1. Finite-cylinder bounds extend this result to the infinite transcript. Replacing or reusing multiple records composes their budgets; rk=1r_k=1 has an unbounded privacy parameter. The revision states this adjacency and transcript proof explicitly; raw-private-data tuning requires its own privacy protection.

Q3. Algorithm 1 accepts every real threshold, while Θ\Theta describes a neighborhood in which the density assumptions hold. For the standard-normal or standard-Cauchy median, [−1,1][-1,1] with a smaller fixed interior radius is valid. The revised stability proof uses positive local density, global CDF monotonicity, bounded private scores and V(x)=cosh⁡(x)−1V(x)=\cosh(x)-1 to control excursions and the MSE of the unprojected recursion. The ensuing score-remainder and uniform Abel estimates establish inference under the explicit uniform root, initialization, independence and step-variation assumptions.

Q4. Yes. Graph aggregation of Liu et al.'s privatized scores is valid postprocessing. Complementing its threshold bit and scaling its gain gives the local scalar update used here. With finite gossip, nodes query at different thresholds, so their discontinuous scores add a disagreement error. We quantify that error, derive the network-mean inferential limit, and specify the stronger condition for transfer to a single node trajectory. The revision credits Liu et al.'s scalar construction and Cai et al.'s empirical decentralized extension, locating our contribution in these graph-dependent statistical guarantees. W4's coverage, interval-size and communication comparisons show the finite-sample tradeoff.

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

Thank you for the feedback, but my concerns have not been fully addressed.

W1/Q1. Any concrete example here? The concern was not on how the weighted quantile should be calculated, but rather on whether there is any pratical meaning of computing the weighted average of local thresholds.

W2/Q3: Would you respond to W2.1 and 2.2 in separate? Also, response to Q3 only gave a specific example, but a general solution is expected here. Otherwise this is a major change to the algorithm.

W4/Q4. Novelty is still limited compared to Liu et al. in my opinion.

Reviewer_bPJiOpenReview ↗
Rating
2(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies quantile inference under local differential privacy in a decentralized network. The method combines one-bit private scores with communication between neighboring nodes. The authors analyze three averaging estimators with corresponding asymptotic results and construct confidence intervals. Numerical experiments and real data application show the effectiveness of the proposed method.

Critical strengths
  1. The authors provide theoretical analysis of the estimators from the decentralized one-bit LDP quantile recursion. This includes asymptotic normality for QTstQ_T^{st} (Cor. 1 and Thm. 2), Qk,TtimeQ_{k,T}^{time} (Thm. 3), and QtspaceQ_t^{space} (Thm. 4). These results provide statistical guarantees for the estimators.

  2. The algorithm (Alg. 1) is easy to interpret, and suitable for streaming data. Its structure is clear, and the paper explains the errors arising from different parts.

  3. The experiments cover several factors related to the assumptions and applications of the method, which can help explain the impact of privacy, heterogeneity, and network connectivity on the estimation and inference.

Critical weaknesses

I have concerns about the novelty of the proposed method. Specifically, the one-bit LDP score is related to the online LDP quantile inference algorithm in [1], which is also used and analyzed in [2]. Also, [2] already proposes a decentralized extension in Appendix C.4. The online self-normalization updates in Alg. 2 also appear to be the same as those in [2, Alg. 2], after accounting for notation and scaling. The authors should explain more clearly what is new beyond this existing decentralized extension and inference procedure.

For the numerical experiments, the authors do not report standard deviations across repeated runs for the reported measures, such as coverage, MAE, and CI length. In Table 1, some value is evaluated only by MAE, without coverage or interval length. Reporting these measures is important for checking whether the numerical results agree with the asymptotic guarantees.


[1]. Liu et al., "Online local differential private quantile inference via self normalization", ICML, 2023

[2]. Cai et al., "Federated learning of quantile inference under local differential privacy", ICLR, 2026

Questions for authors
  1. In line 148, what does the horizon TT refer to? Also, in line 172, what does the infimum over TT mean in the definition rmin⁡:=inf⁡Tmin⁡k≤Krk>0r_{\min} := \inf_T \min_{k \le K} r_k > 0?

  2. In line 192, should Sk,tS_{k,t} be written as Sk,t(qk,t−1)S_{k,t}(q_{k,t-1}), since it takes qk,t−1q_{k,t-1} as input?

  3. Compared with existing LDP quantile inference, such as [2], what do the authors consider the most important new insight of this paper? Does it mainly concern new technical challenges, new statistical results, or the ability to operate in a different network setting?

  4. With the amount of data and privacy budgets fixed, how should the communication interval be chosen in practice? Are there simple and reliable recommendations?

4 comments

Thank you for your time and valuable comments.

W1. We have clarified the inherited components and the specific theoretical contribution. The one-bit randomized-response score and scalar recursion build on Liu et al. (ICML 2023), Algorithms 1–2. The online self-normalization accumulators are those of Cai et al. (ICLR 2026), Algorithm 2, whose Appendix C.4 also presents an empirical decentralized extension.

Our contribution is the analysis of persistent finite-gossip disagreement interacting with discontinuous quantile scores, and the conditions under which network-mean and individual-node trajectories support inference. The graph-dependent disagreement bounds feed into the decentralized-score remainder, linear expansion and FCLT; a separate process-transfer condition yields node-wise inference. The revised presentation centers these statistical and technical results, including their graph and growth requirements, and explicitly credits the existing recursion and accumulator construction.

W2. We now supply the across-repetition SDs for the supplementary comparison. At N=200,000N=200{,}000 per node, A is the homogeneous normal median (K=10,r=.25K=10,r=.25), while D is the heterogeneous-location normal median (K=50,r=.9K=50,r=.9). Each entry below is the network-mean result; parentheses report the SD of the corresponding coverage indicator, absolute error or interval length.

Setting / ruleCoverage (SD)MAE (SD)Mean length (SD)
A / C10.942 (0.234)0.002796 (0.002138)0.017245 (0.007732)
A / C50.926 (0.262)0.002837 (0.002152)0.016570 (0.007753)
A / P150.922 (0.268)0.003016 (0.002292)0.017213 (0.008185)
D / C50.880 (0.325)0.000412 (0.000308)0.002171 (0.001011)

Node-average quantities are first averaged within each repetition, so their spread reflects independent data-stream repetitions rather than treating dependent nodes as independent observations. The historical submission's SDs cannot be recovered from these new streams.

The MAE-only entries concern different inferential objects. The terminal spatial estimator has a CLT with an unknown mixture-density and score-variance scale, whereas Algorithm 2 normalizes a temporal-average trajectory. The original growing-block example also lies outside the inference growth condition, and HIST has no specified feasible interval construction. Their MAE entries therefore remain estimation comparisons; feasible temporal-average intervals are reported with both coverage and length.

Q1. TT counts communication blocks, while tT=∑m≤TEmt_T=\sum_{m\le T}E_m is the number of fresh records processed at each node. The formulation allows a sequence of problems with deterministic KT,pk,T,rk,TK_T,p_{k,T},r_{k,T} indexed by this horizon. Thus rmin⁡:=inf⁡Tmin⁡k≤KTrk,T>0r_{\min}:=\inf_T\min_{k\le K_T}r_{k,T} > 0 imposes a uniform positive lower bound across that sequence. We have made the communication clock, record clock and horizon-indexed quantities explicit.

Q2. We have written Sk,t:=Sk,t(qk,t−1)S_{k,t}:=S_{k,t}(q_{k,t-1}) at its use in the recursion. This distinguishes the random score function from its evaluation at the current local threshold and makes the iterate dependence explicit.

Q3. The central insight is that finite gossip introduces a persistent discrepancy between local thresholds, and a discontinuous quantile score responds to that discrepancy through threshold-crossing events. Controlling this error jointly with the privacy-inflated stochastic noise yields the network-mean linear expansion and FCLT. Under the stated stronger balance condition, the full trajectory at an individual node inherits the first-order inferential limit.

This gives a statistical characterization of when neighbor-only operation supports inference using existing private iterates. CENT updates its common query after every batch of KK records and averages at the same block endpoints as the decentralized method. For example, at N=200,000N=200{,}000 per node in the normal-median comparison, network/CENT coverage is .942/.944.942/.944 under C1 and .926/.926.926/.926 under C5, with respective mean lengths .017245/.017262.017245/.017262 and .016570/.016559.016570/.016559. C5 uses 8080\\% fewer gossip blocks. In the heterogeneous K=50K=50 setting, node-average coverage can be appreciably lower than network coverage; the separate node-transfer conditions are therefore relevant to both the theory and the numerical interpretation.

Q4. At a fixed per-node record budget N=tTN=t_T, the leading variance is proportional to νT/N\nu_T/N, where νT=NHT/T2\nu_T=NH_T/T^2 and HT=∑m=1TEm−1H_T=\sum_{m=1}^T E_m^{-1}. For a constant block length EE with N=ETN=ET, νT=1\nu_T=1. Thus the leading variance alone does not distinguish between constant intervals. Practical choices also depend on finite-sample disagreement and communication costs.

We recommend starting with a short fixed interval, such as C1, when node-wise inference is the goal or network mixing is slow. A moderate interval, such as C5, is an option when communication is costly and inference focuses on the network mean. In our simulations, C5 uses 8080\\% fewer gossip rounds than C1 at the same record budget. Coverage varies across settings, and these comparisons use schedule-specific step sizes.

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

Thanks for clarifying the relationship to prior work and providing additional numerical results. I have updated my score accordingly. I appreciate the theoretical analysis of node-wise inference, but I still think the novelty of the proposed method is limited.

Thank you for updating your assessment. We appreciate your recognition of the theoretical analysis of node-wise inference and the additional numerical evidence.

Our main contribution is to establish when quantile inference remains valid with private one-bit messages and incomplete synchronization. The analysis connects network disagreement and discontinuous scores to the conditions for valid network-average and individual-node inference. The numerical comparisons illustrate the associated tradeoffs between communication, coverage, and interval length.

Thank you again for your time and valuable feedback. We welcome any further questions or discussion.

Reviewer_x8ZMOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies locally differentially private quantile inference over heterogeneous data streams without a trusted central server. The proposed method combines one-bit randomized response with blockwise gossip to estimate a weighted mixture quantile. The authors establish a CLT, a functional CLT, and self-normalized confidence intervals for the spatial–temporal average. Under stronger network and node-growth conditions, individual node-wise temporal averages inherit the same first-order limits. Simulations and a salary-data application examine privacy, communication frequency, and network connectivity.

Critical strengths

1、The paper jointly considers heterogeneous data, local privacy, and neighbor-only communication. Compared with server-coordinated LDP quantile methods, this setting is relevant when no trusted aggregator is available. 2、The analysis explicitly addresses the interaction between network disagreement and discontinuous quantile scores, rather than directly applying smooth-optimization results. Transferring the network-average inferential limit to individual node trajectories is particularly useful. 3、The self-normalized intervals avoid estimating the mixture density and privacy-inflated score variance. They are computed from existing privatized iterates without requiring additional privacy budget. 4、The appendix includes sparse networks, baseline comparisons under common record budgets, directed and asynchronous communication, edge dropout, and distribution shifts. These experiments help characterize the method’s practical scope.

Critical weaknesses
  1. Some nominal 95% intervals achieve coverage around 0.89–0.92, while others approach 1.00, despite long simulation horizons. Thus, the self-normalized intervals can exhibit undercoverage or excessive conservatism. The claim of near-nominal coverage should be qualified.
  2. Allowing growing communication intervals is a theoretical contribution, but the main coverage experiments use fixed intervals C1 and C5. The growing-block experiment P(1/5) uses a step size outside Assumption 4 and therefore reports estimation errors only. Inference under a theoretically admissible growing-block schedule remains insufficiently validated.
  3. The theory assumes i.i.d. streams with regular densities, whereas the salary experiment uses sampling without replacement from a fixed finite population, potentially with substantial salary ties. It also uses substantially different step-size constants across privacy levels. These differences complicate both theoretical interpretation and the separation of privacy effects from tuning effects.
Questions for authors
  1. How does Algorithm 1 ensure that all iterates remain in Θ? Is a projection step, a global drift condition, or a separate stability proof required?
  2. Could you state the main bounds with explicit dependence on 1−ρ, and specify conditions for valid node-wise inference when the spectral gap shrinks with network size?
  3. Could you evaluate growing communication intervals satisfying β<2α−1, reporting both coverage and interval length? In the existing undercoverage settings, is the main cause initialization, step-size choice, or asymptotic approximation?
  4. How do salary discreteness and sampling without replacement affect interval validity? How were the step-size constants a=12 a=72 selected, and was the population truth or empirical coverage used for tuning?
3 comments

Thank you for your time and valuable comments.

W1. The revised empirical discussion distinguishes network-mean inference from inference at an individual node, reporting coverage together with interval length and estimation error. At the same record budget, the network mean closely tracks synchronized CENT, while coverage depends on the distribution, block schedule and finite trajectory. CENT evaluates each batch of KK fresh-record scores at a common query, updates that query after every batch, and averages at the same block endpoints as the decentralized method. For N=200,000N=200{,}000 records per node, the following representative results include interval length alongside coverage. A is the standard-normal median with K=10,r=.25K=10,r=.25; B is the standard-normal .8.8 quantile with K=10,r=.9K=10,r=.9; D is the heterogeneous-location normal median with K=50,r=.9K=50,r=.9.

SettingRuleNetwork coverageCENT coverageNetwork MAENetwork lengthCENT length
AC10.9420.9440.0027960.0172450.017262
AC50.9260.9260.0028370.0165700.016559
BC10.9640.9640.0011290.0079920.007991
BC51.0001.0000.0038960.0299970.029991
DC10.9020.9040.0004090.0022710.002274
DC50.8800.8740.0004120.0021710.002177

The close network/CENT agreement demonstrates that finite gossip can preserve network-mean performance in these examples. The B/C5 intervals are conservative and substantially wider than B/C1, whereas D remains under-covered. In D/C5, node-average coverage is .82296.82296, compared with network coverage .880.880. The revised interpretation therefore gives the observed coverage and interval size separately for the network mean and nodes.

W2. We added growing-block inference with α=.7\alpha=.7 and β=.2\beta=.2, which satisfies β<2α−1\beta < 2\alpha-1. The gain is 1.08(m+199)−.71.08(m+199)^{-.7}, initialization is zero, and P1/5P_{1/5} uses Em=⌈(m+1)1/5⌉E_m=\lceil(m+1)^{1/5}\rceil, truncating the last block to the specified record budget. Calibration uses the reciprocal-block clock. The experimental appendix now justifies shortening the final block while keeping its effective gain: the scaled temporal-average perturbation and the change in normalized reciprocal-block weights vanish, preserving the averaged inference limits. The submitted α=.55,β=.2\alpha=.55,\beta=.2 configuration remains an estimation-only example.

At N=200,000N=200{,}000 per node, the growing-block results are:

SettingRuleNetwork coverageCENT coverageNetwork MAENetwork lengthCENT length
AP150.9220.9240.0030160.0172130.017211
BP151.0001.0000.0054210.0422650.042252
CP150.9260.9260.0030230.0173080.017286
DP150.8880.8900.0004290.0022420.002249

Here C is a .3/.3/.4.3/.3/.4 mixture of normal, uniform and Cauchy nodes, with K=10,τ=.5,r=.25K=10,\tau=.5,r=.25. The network mean remains close to CENT, including in the difficult D setting. P15 uses approximately 28,60028{,}600 gossip blocks, compared with 200,000200{,}000 for C1, reducing the number of gossip blocks by 85.785.7\\%. The table also makes the remaining undercoverage and conservative B intervals explicit.

W3. The salary application involves ties and sampling without replacement, which differ from the i.i.d. continuous-density setting of our asymptotic analysis. It provides an empirical assessment of the implemented procedure on real data. Related evaluations of private confidence intervals also use quantities computed from a full real dataset as reference values; see Drechsler et al. (2022) for Census-income medians and Wang, Cheng and Awan (2025) for quantile regression on Census data. In our experiment, coverage denotes inclusion of the fixed-population 80th percentile over 500 repeated samples. We will clarify the empirical role of this application and the step-size settings used in the comparison.

Q1. Algorithm 1 operates on the real line without projection; Θ\Theta supplies local regularity around the target. We have replaced the confinement-dependent proof with a global stability argument for this displayed recursion, with an explicit uniform interior root, bounded public initial error, fresh independent observations and coins, and uniform step-size envelopes, including ∣γm−1−γm−1−1∣≤C(m+1)α−1|\gamma_m^{-1}-\gamma_{m-1}^{-1}|\le C(m+1)^{\alpha-1}.

The proof first controls network disagreement using bounded private scores. For the network-mean error xx, it then uses V(x)=cosh⁡(x)−1V(x)=\cosh(x)-1: positive mixture density supplies inward drift near the root, while CDF monotonicity and the disagreement bound supply inward drift outside that neighborhood. At the observation level,

EV(x+)∣H≤(1−cη)V(x)+Cηγ2+Cκ2η2.\mathbb E\\{V(x^+)\mid\mathcal H\\}\le(1-c\eta)V(x)+C\eta\gamma^2+C\kappa^2\eta^2.

Iteration through a block and the resulting scalar recursion give an exponentially decaying initialization term plus Cκ2γm−1/Em+γm−12C\\{\kappa^2\gamma_{m-1}/E_m+\gamma_{m-1}^2\\}. Since V(x)≥x2/2V(x)\ge x^2/2, this establishes the MSE before that MSE is used to control the score remainder, including its excursion contribution C(γm−1+em−12)C(\gamma_{m-1}+e_{m-1}^2).

The revised uniform Abel argument bounds its boundary by OpΔT+T(α−1)/2log⁡(eT)O_p\\{\Delta_T+T^{(\alpha-1)/2}\sqrt{\log(eT)}\\}, with ΔT=nTT−1∑m≤Tγm−1\Delta_T=\sqrt{\mathfrak n_T}T^{-1}\sum_{m\le T}\gamma_{m-1}. Conditional exponential bounds control the frozen-score convolution, and inverse-step variation controls the Abel variation term. The target-replacement argument retains its quantitative bound OpT(β−1)/2log⁡(eT)+κ1/2T−(α+β)/4+T−α/2O_p\\{T^{(\beta-1)/2}\sqrt{\log(eT)}+\kappa^{1/2}T^{-(\alpha+\beta)/4}+T^{-\alpha/2}\\} and its absorption into the final remainder. These steps establish the endpoint control used by the FCLT for the unprojected algorithm.

Q2. We have made the graph dependence explicit through

AK,ρ=∑ℓ≥1min⁡2,Kρℓ≤2+log⁡K+11−ρ.A_{K,\rho}=\sum_{\ell\ge1}\min\\{2,\sqrt K\rho^\ell\\}\le2+\frac{\log K+1}{1-\rho}.

For common initialization, the appendix gives

Dtm≤C∑j≤mγj−1ρm−j+1,max⁡k∣qk,tm−qˉtm∣≤C∑j≤mγj−1min⁡2,Kρm−j+1.D_{t_m}\le C\sum_{j\le m}\gamma_{j-1}\rho^{m-j+1},\qquad \max_k|q_{k,t_m}-\bar q_{t_m}|\le C\sum_{j\le m}\gamma_{j-1}\min\\{2,\sqrt K\rho^{m-j+1}\\}.

These convolution bounds retain the influence of early inputs. Conditional on a valid network-mean FCLT, the sufficient node-transfer condition is AK,ρK,T(1+β)/2−α→0A_{K,\rho}\sqrt K\\,T^{(1+\beta)/2-\alpha}\to0. The complete inference theorems use a uniformly positive spectral gap, ρ≤ρˉ<1\rho\le\bar\rho < 1; applying the conditional transfer statement to a shrinking-gap sequence additionally requires network-mean stability and FCLT control along that sequence. This distinction specifies exactly which part of the graph-dependent argument extends directly.

Q3. The admissible growing-block experiment in W2 supplies coverage and length with α=.7,β=.2\alpha=.7,\beta=.2. We also examined the difficult K=50K=50 heterogeneous-location median under its original C5 gain schedule, keeping observations and privacy uniforms paired across changes in initialization, gain and gossip. At N=106N=10^6, the baseline network/CENT coverages are .942/.940.942/.940, whereas node-average coverage is .85212.85212.

VariantNode-average coverageNode MAENode mean length
Original gain and gossip.85212.000465.001776
Half gain.85784.000271.001252
Double gain.91716.000902.003072
Double gossip.88372.000245.001225
Initialization −1-11.00000.000630.004656
Initialization +1+11.00000.000639.004739

Additional gossip reduces local error and narrows the intervals, while its coverage remains below nominal. Increasing gain improves coverage at a cost in MAE and length; shifted initializations instead produce conservative, wider intervals. A fixed 1010\\% burn-in yields node coverages .78044.78044 for the baseline and .60928.60928 for double gain. The evidence identifies sensitivity to early trajectories, gain and local disagreement. These diagnostics use the original C5 schedule; the growing-block experiment uses its separately stated admissible schedule. The revised discussion presents these mechanisms together with their error and interval-size tradeoffs.

Q4. The reported salary results use step-size constants a=12a=12 at r=.6r=.6 and a=72a=72 at r=.9r=.9, with each constant held fixed across the 500 repetitions. These results evaluate two specified combinations of privacy level and step size. We will make this interpretation explicit in the discussion and present estimation error, interval length and empirical inclusion frequency together for each configuration.

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 careful review and valuable comments. We hope our theoretical clarifications and additional numerical results help address your concerns.

Our analysis establishes conditions for valid quantile inference with private one-bit messages and incomplete synchronization, distinguishing network-average from individual-node inference. The additional experiments examine growing communication intervals and clarify the finite-sample tradeoffs between communication, coverage, and interval length.

Thank you again for your time and consideration.

Comments on the paper

1 comment
Area_Chair_6AQeOpenReview ↗

Please read authors' answers

Dear reviewers,

As we are approaching the deadline of the discussion phase, please read the authors’ responses and share your thoughts in the discussion as soon as possible. Your reviews raised several substantial concerns, so it would be very helpful to know whether the rebuttal changes your assessment, or whether your main concerns still stand. A short message is enough if your evaluation is unchanged. If your view has changed, please update your review and scores.

Your timely input will help us reach a well-informed decision. Thank you for your time and effort!

Best regards, Area Chair

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.