- 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 receives a stream of elements i.i.d. from a distribution with CDF . Each node also has a weighting factor and its own quantile level . The target is to find the element which satisfies , where is the weighted mixture distribution, and 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 as a parameter, where the objective function depends on the indicator of whether the received element is less than . 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 . 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 for all 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 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 's.
Meanwhile, if each node adopts a different , then 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 must be more carefully coped with.
W2.1. In Equation (1), the paper mentions that the unique solution to 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 .
- Missing derivation for this equivalence. For example, when considering empirical quantiles (i.e. when is discrete), there can be no solution to , 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 is compact, and all subsequent analyses are based on it. However, 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 , even if is initialized as an element from .
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 and .
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 '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 ? Any specific examples for ?
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
W4. The submitted full tables include , 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 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 and per node:
| Gain matched to | Coverage (Network/Liu) | MAE (Network/Liu) | Length (Network/Liu) |
|---|---|---|---|
| C1 | 0.942/0.944 | 0.002796/0.002795 | 0.017245/0.017255 |
| C5 | 0.926/0.926 | 0.002837/0.002841 | 0.016570/0.016558 |
| P15 | 0.922/0.924 | 0.003016/0.002881 | 0.017213/0.016284 |
C1/C5 closely track the Liu implementation in error and interval size. For P15, the network interval is about longer and MAE about higher, reflecting the different clock and averaging rule. In homogeneous upper-tail setting B under P15, both coverages are , while network/Liu MAE is and length ; these comparisons retain that configuration's statistical cost. The synchronized comparison in the heterogeneous case gives network/CENT coverage under C1 and under C5.
Communication benefits are coordinator removal and fewer gossip rounds with longer blocks: C5 and P15 use and fewer rounds than C1 at this budget. With one directed state message per neighbor per gossip round, peer transmissions are ; two gossip steps per block use . Under unicast query–response, the implemented CENT comparator uses threshold-query messages and responses, totaling . A hypothetical server gathering and broadcasting only at block endpoints would use messages; it performs a different recursion when . These counts distinguish interaction patterns; payloads and latency depend on implementation. Literal Liu processes 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 at . 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 , and all other conditional factors cancel. Postprocessing therefore gives the full message and interval transcript the guarantee for . Finite-cylinder bounds extend this result to the infinite transcript. Replacing or reusing multiple records composes their budgets; 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 describes a neighborhood in which the density assumptions hold. For the standard-normal or standard-Cauchy median, with a smaller fixed interior radius is valid. The revised stability proof uses positive local density, global CDF monotonicity, bounded private scores and 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.
Thank you for your time and valuable comments.
W1. The target is one common threshold for the mixture distribution, at level τ=∑kpkτ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=τ. 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) the median is 2/3, whereas the weighted average of the local medians is 3.
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 Θ separately. The objective is the anchored contrast
L(q)=∑kpkEρτk(Xk−q)−ρτk(Xk−qref),ρa(u)=ua−1(u<0).
The subtraction is inside the expectation, and the absolute contrast is bounded by ∣q−qref∣, making it finite for the Cauchy example as well. Its subgradient is ∂L(q)=[F(q−)−τ,F(q)−τ]. For a continuous CDF, the derivative is F(q)−τ; 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), allowing ties and nonuniqueness.
Algorithm 1 is defined on the real line and uses Θ 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 Kpk 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),
which equals ητ−F(q)=−ηL′(q) at consensus. The factor K cancels the 1/K in the arithmetic network mean, and double stochasticity preserves that mean during gossip. Removing pk generally changes the target; removing only K rescales the gain.
Complementing the threshold bit and using local gain ηKpk/rk 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=J; the graph need not exclude a clique.