- Rating
- 2(+1)
- Confidence
- 3
- Informativeness
- 2(+1)
- Presentation
- 2
- Soundness
- 2(+1)
Read review
Paper summary
The paper studies nonasymptotic anytime-valid inference for quantiles under LDP, which is a problem at the intersection of sequential inference and privacy-preserving statistics. The authors use randomized response together with betting e-processes to construct a nonasymptotic, anytime-valid CS.
Critical strengths
S1. The paper provides several theoretical guarantees.
Beyond coverage, the authors also study the width of the proposed NonasympCS.
S2. The numerical study is extensive.
The experiments include experiment under different data distribution and other tuning-sensitivity experiments.
Critical weaknesses
W1. The methodological novelty appears limited relative to the literature of the proposed framework.
I think most individual ingredients, randomized response, betting/e-processes, and inversion of sequential tests, are well established. While technically nontrivial, I am not convinced that this constitutes a sufficiently substantial conceptual advance for ICLR.
At a high level, the method feels like it stitches together ideas from about three existing papers.
W2. The condition is too restrictive.
The local density is unknown, yet the user must choose . The required upper bound also depends on the privacy parameter through , and can become particularly restrictive for small privacy budgets, extreme quantiles, or low-density regions. The current sensitivity study over a narrow range of values under a standard Gaussian model does not resolve this issue.
W3. The empirical comparisons with the asymptotic baselines are not fully convincing.
Several of the most favorable comparisons for the proposed method use settings deliberately difficult for the asymptotic baselines. In fact, under more standard settings, the GM boundary proposed in Cai et. al. (2025) eventually produces narrower intervals.
W4. The proposed confidence sequences appear extremely conservative.
At a nominal 95% confidence level, the reported simultaneous coverage probabilities are almost near 100%. This suggests a potentially substantial efficiency loss.
W5. The scope of the sequential model is fairly narrow.
Despite the emphasis on online and streaming inference, the observations are assumed to be i.i.d. The method does not address dependence, nonstationarity, heterogeneous users, distribution shift, or adaptive data collection. If these issues are difficult for authors, I think they at least should discuss them carefully.
W6. The manuscript is poorly polished and, in many places, unnecessarily difficult to read.
Honestly, the paper often reads like a hastily assembled AI-assisted draft rather than a carefully polished conference submission: individual sentences may be grammatically acceptable, but the overall exposition frequently lacks natural flow, prioritization, and human-readable explanation.
Questions for authors
See weaknesses.
9 comments
Response to Reviewer QPgb (Part 2 of 3)
W3. The empirical comparisons with the asymptotic baselines are not fully convincing. Several of the most favorable comparisons for the proposed method use settings deliberately difficult for the asymptotic baselines. In fact, under more standard settings, the GM boundary proposed in Cai et. al. (2025) eventually produces narrower intervals.
The original manuscript reports that Cai GM, the Gaussian-mixture CS of Cai et al. (2025), gave narrower intervals than ours at large sample sizes (Appendix D.1, Figures D1-D3, and Section 6). In those normal, Cauchy, and lognormal experiments, all three methods had empirical simultaneous coverage above 95% with initial position 0 and . Cai GM relies on a large-sample Gaussian approximation. Our nonasymptotic CS guarantees simultaneous coverage from the first observation and also produced finite intervals earlier in these experiments. For the standard-normal median, the median time to the first finite interval across 1,000 replications was 237 users for our CS and 58,561 for Cai GM.
We used the increasing-chain method and burn-in of Cai et al. (2025). We chose GM as the main comparison because it often gave narrower intervals than their stitched CS (Section 5, lines 363-370). Figure 4 examines the density smoothness in their Assumptions A1-A2. Within the same distribution, Cai GM maintained coverage and eventually gave narrower intervals at and , where the density is smooth, and undercovered at the median, where the density jumps. In Figure 5, we varied only the initial position in the standard-normal median experiment. Cai GM's empirical simultaneous coverage stayed above 95% at starting values 0 and 4 and fell below 95% at more distant starts. Cai et al. (2025) also discuss this sensitivity to initialization in Section 6. Our coverage guarantee allows any starting value and does not require a continuous density.
W4. The proposed confidence sequences appear extremely conservative. At a nominal 95% confidence level, the reported simultaneous coverage probabilities are almost near 100%. This suggests a potentially substantial efficiency loss.
Please see our response to Reviewer Exwx (W2).
We agree that the empirical coverage is high in the standard-normal experiment. With and , the true median receives a betting factor of one whenever it lies in . On 414 of the 500 paths we replayed, its capital stayed at one through five million observations. On the other 86 paths the maximum was 15.37, below the exclusion threshold of 20. Thus all 500 paths covered the median throughout, even as the procedure ruled out candidates farther away.
The width comparison depends on how much precision we need. In the 1,000 replications in Figure D1, the median number of users needed to reach a full width of 0.10 was 91,780 for our method and 192,650.5 for Cai GM (Cai et al., 2025). At five million users, the mean full widths were 0.01404 and 0.00744, respectively. Section 6 identifies improving betting efficiency as a direction for future work.
References
- Cai, L., Hu, Q., Sun, J., and Wu, S. (2025). Time-uniform and asymptotic confidence sequence of quantile under local differential privacy. NeurIPS, 38, 114488-114520.
Response to Reviewer QPgb (Part 3 of 3)
W5. The scope of the sequential model is fairly narrow. Despite the emphasis on online and streaming inference, the observations are assumed to be i.i.d. The method does not address dependence, nonstationarity, heterogeneous users, distribution shift, or adaptive data collection. If these issues are difficult for authors, I think they at least should discuss them carefully.
We assume i.i.d. observations from one distribution with target quantile . The i.i.d. assumption is a standard starting point for online inference with streaming data. For example, Howard and Ramdas (2022) and Chen et al. (2023) use this assumption for non-private inference, and Liu et al. (2023) and Cai et al. (2025) use it under local differential privacy. Chen et al. (2020) use i.i.d. data for inference with stochastic gradient descent, and Zhu et al. (2023) use the same assumption for online covariance estimation. Luo and Song (2020) use it in streaming regression, as do Luo et al. (2023) and Han et al. (2026) in high dimensions.
The proof uses for a threshold chosen from past reports. Dependence or adaptive sampling can change this conditional probability. In future work, we would like to extend our coverage guarantee to dependent observations, adaptive sampling, and settings where the population distribution changes over time.
W6. The manuscript is poorly polished and, in many places, unnecessarily difficult to read. Honestly, the paper often reads like a hastily assembled AI-assisted draft rather than a carefully polished conference submission: individual sentences may be grammatically acceptable, but the overall exposition frequently lacks natural flow, prioritization, and human-readable explanation.
We organized the paper around how to construct a nonasymptotic quantile CS from one private report per user. The Introduction explains which part of this problem existing methods solve (Table 1), and Figure 1 shows how a single report updates the interval. After defining the privacy and coverage requirements in Section 2, we develop the method in the order the analyst uses it. Section 3 explains how to update the candidate tests, choose the next query, and store the surviving candidates. Section 4 then distinguishes what holds for every distribution (simultaneous coverage) from what requires additional assumptions (the rate at which the interval narrows). Section 5 examines both coverage and width in simulations and illustrates the procedure on wage data.
We wrote the manuscript ourselves and used AI tools to polish the language. Our AI Use Statement on page 11 describes how we used these tools, as required by the ICLR 2027 author policy. If you found a particular sentence unclear or a step in the argument difficult to follow, please point us to the passage. We would be glad to address each point in turn.
References
- Cai, L., Hu, Q., Sun, J., and Wu, S. (2025). Time-uniform and asymptotic confidence sequence of quantile under local differential privacy. NeurIPS, 38, 114488-114520.
- Chen, L., Keilbar, G., and Wu, W. B. (2023). Recursive quantile estimation: Non-asymptotic confidence bounds. Journal of Machine Learning Research, 24(91), 1-25.
- Chen, X., Lee, J. D., Tong, X. T., and Zhang, Y. (2020). Statistical inference for model parameters in stochastic gradient descent. The Annals of Statistics, 48(1), 251-273.
- Han, R., Luo, L., Luo, Y., Lin, Y., and Huang, J. (2026). Adaptive debiased lasso in high-dimensional generalized linear models with streaming data. Journal of the American Statistical Association.
- Howard, S. R., and Ramdas, A. (2022). Sequential estimation of quantiles with applications to A/B testing and best-arm identification. Bernoulli, 28(3), 1704-1728.
- Liu, Y., Hu, Q., Ding, L., and Kong, L. (2023). Online local differential private quantile inference via self-normalization. ICML, PMLR 202, 21698-21714.
- Luo, L., and Song, P. X.-K. (2020). Renewable estimation and incremental inference in generalized linear models with streaming data sets. J. R. Stat. Soc. Ser. B, 82(1), 69-97.
- Luo, L., Han, R., Lin, Y., and Huang, J. (2023). Online inference in high-dimensional generalized linear models with streaming data. Electronic Journal of Statistics, 17(2), 3443-3471.
- Zhu, W., Chen, X., and Wu, W. B. (2023). Online covariance matrix estimation in stochastic gradient descent. Journal of the American Statistical Association, 118(541), 393-404.
Response to Reviewer QPgb (Part 1 of 3)
Thank you for your comments. We address them one by one below.
Please see our response to Reviewer Exwx (W1).
Randomized response, betting e-processes, and test inversion are established tools. The challenge is to update every test from one private report. Table 1 compares three related methods.
We choose Lt<Ut from past reports and randomize the label of the region containing the observation. We use one ternary report Zt for both endpoint comparisons and all candidate tests. Under q=qτ, Pr(Zt=0∣Ft−1) has a fixed lower bound for q≤Lt, and Pr(Zt=2∣Ft−1) has a fixed upper bound for q>Ut as the thresholds move. We use the corresponding one-sided betting factor outside (Lt,Ut] and a factor of one inside. At qτ its conditional mean is at most one. This gives simultaneous coverage from t=1 under local differential privacy (LDP) for i.i.d. data from any distribution on R, with no search interval fixed in advance (Theorem 1).
The detailed comparison and derivation are in our response to Reviewer Exwx (W1).
We discuss bmin after Assumption 1 (lines 320-324).
If bmin>ρf(qτ), privacy and simultaneous coverage still hold (Theorem 1), but Theorem 2 no longer guarantees the stated width rate. For any positive floor, Theorems C1 and C2 still give a finite interval and bounded memory under their respective assumptions.
In Eq. (9), a small enough positive floor meets the condition if f(qτ)>0. The largest valid floor is unknown and may be smaller for extreme quantiles or small privacy budgets. Appendix E.3 shows that, when qτ survives, the slope estimate converges to ρf(qτ) if the sum of squared query radii diverges. If the sum is finite, the width is already o(t−1/2). The rate has no explicit bmin factor.
Appendix D.1 varies the scale, and Experiment A5 varies the floor (Appendix D.6). With bmin=0.01 and ε=1, varying the normal standard deviation over 0.1,1,5,10 changed the density at each quantile by a factor of 100. Across three quantiles, bmin/ρf(qτ) ranged from 0.007 to 0.79, so all met the condition. Coverage was 99.7%-100%. Larger scales delayed the first finite interval. Public rescaling shortened this delay (Figures D5-D6). We kept the same floor for normal data across ε∈0.5,1,2,3 and for Cauchy, lognormal, and Beta-mixture data at ε=1 (Table D1 and Figures D1-D4). In an unbounded exponential-tail mixture (ε=2, f(q0.5)=0.010), ρf(q0.5)≈0.0068<bmin=0.01. At 5M users, mean full width was 0.2848 and simultaneous coverage was 97.4% (487/500). Scale-invariant tuning remains open (Section 6).
References