acceptodds
Under review as a conference paper at ICLR 2027

Nonasymptotic anytime-valid inference for quantiles under local differential privacy

Abstract

We propose a framework for sequential inference on population quantiles under local differential privacy (LDP). Specifically, we construct a nonasymptotic, anytime-valid confidence sequence by sequentially testing candidate quantiles with betting -processes and permanently eliminating those rejected at level . A ternary randomized response mechanism based on adaptively chosen query intervals provides the LDP guarantee. The proposed algorithm updates the confidence sequence in a single pass by taking the closed convex hull of the surviving candidates, while a nested-lattice implementation reduces memory requirements. We establish distribution-free, nonasymptotic coverage of at least uniformly over time, ensuring valid inference at data-dependent stopping times. Under suitable regularity conditions, the interval width contracts at the iterated-logarithm rate . Numerical experiments demonstrate the finite-sample validity and practical effectiveness of our algorithm.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
anytime-valid inference, confidence sequence, e-process, local differential privacy, quantile, sequential testing

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_QPgbOpenReview ↗
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 b{min⁡}≤ρf(qτ)b_\{\min\}\leq \rho f(q_\tau) is too restrictive.
The local density f(qτ)f(q_\tau) is unknown, yet the user must choose bmin⁡>0b_{\min}>0. The required upper bound also depends on the privacy parameter through ρ\rho, and can become particularly restrictive for small privacy budgets, extreme quantiles, or low-density regions. The current sensitivity study over a narrow range of bmin⁡b_{\min} 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
AuthorsOpenReview ↗

Response to Reviewer QPgb (Part 1 of 3)

Thank you for your comments. We address them one by one below.

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.

Please see our response to Reviewer Exwx (W1).

Randomized response, betting ee-processes, and test inversion are established tools. The challenge is to update every test from one private report. Table 1 compares three related methods.

  • Howard and Ramdas (2022) use sample order statistics as endpoints. Private region labels do not reveal those values.
  • Cai et al. (2025) use a strong Gaussian approximation with an asymptotic remainder. Section 6 identifies a nonasymptotic private confidence sequence (CS) for their iterates as an open question.
  • Waudby-Smith et al. (2023) construct a private CS for one fixed mean. Applied to 1Xt≤x\mathbf{1}\\{X_t\le x\\}, it targets F(x)F(x), which can change as xx moves to locate the quantile.

We choose Lt<UtL_t<U_t from past reports and randomize the label of the region containing the observation. We use one ternary report ZtZ_t for both endpoint comparisons and all candidate tests. Under q=qτq=q_\tau, Pr⁡(Zt=0∣Ft−1)\Pr(Z_t=0\mid\mathcal F_{t-1}) has a fixed lower bound for q≤Ltq\le L_t, and Pr⁡(Zt≠2∣Ft−1)\Pr(Z_t\ne2\mid\mathcal F_{t-1}) has a fixed upper bound for q>Utq>U_t as the thresholds move. We use the corresponding one-sided betting factor outside (Lt,Ut](L_t,U_t] and a factor of one inside. At qτq_\tau its conditional mean is at most one. This gives simultaneous coverage from t=1t=1 under local differential privacy (LDP) for i.i.d. data from any distribution on R\mathbb R, with no search interval fixed in advance (Theorem 1).

The detailed comparison and derivation are in our response to Reviewer Exwx (W1).

W2. The condition bmin⁡≤ρf(qτ)b_{\min}\le\rho f(q_\tau) is too restrictive. The local density f(qτ)f(q_\tau) is unknown, yet the user must choose bmin⁡>0b_{\min}>0. The required upper bound also depends on the privacy parameter through ρ\rho, and can become particularly restrictive for small privacy budgets, extreme quantiles, or low-density regions. The current sensitivity study over a narrow range of bmin⁡b_{\min} values under a standard Gaussian model does not resolve this issue.

We discuss bmin⁡b_{\min} after Assumption 1 (lines 320-324).

  1. If bmin⁡>ρf(qτ)b_{\min}>\rho f(q_\tau), 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.

  2. In Eq. (9), a small enough positive floor meets the condition if f(qτ)>0f(q_\tau)>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τq_\tau survives, the slope estimate converges to ρf(qτ)\rho f(q_\tau) if the sum of squared query radii diverges. If the sum is finite, the width is already o(t−1/2)o(t^{-1/2}). The rate has no explicit bmin⁡b_{\min} factor.

  3. Appendix D.1 varies the scale, and Experiment A5 varies the floor (Appendix D.6). With bmin⁡=0.01b_{\min}=0.01 and ε=1\varepsilon=1, varying the normal standard deviation over 0.1,1,5,10\\{0.1,1,5,10\\} changed the density at each quantile by a factor of 100. Across three quantiles, bmin⁡/ρf(qτ)b_{\min}/\\{\rho f(q_\tau)\\} 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\varepsilon\in\\{0.5,1,2,3\\} and for Cauchy, lognormal, and Beta-mixture data at ε=1\varepsilon=1 (Table D1 and Figures D1-D4). In an unbounded exponential-tail mixture (ε=2\varepsilon=2, f(q0.5)=0.010f(q_{0.5})=0.010), ρf(q0.5)≈0.0068<bmin⁡=0.01\rho f(q_{0.5})\approx0.0068<b_{\min}=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

AuthorsOpenReview ↗

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 ε=1\varepsilon=1. 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 τ=0.3\tau=0.3 and 0.70.7, 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 τ=0.5\tau=0.5 and ε=1\varepsilon=1, the true median receives a betting factor of one whenever it lies in (Lt,Ut](L_t,U_t]. 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

AuthorsOpenReview ↗

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 FF with target quantile qτq_\tau. 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 Pr⁡(Xt≤Lt∣Ft−1)=F(Lt)\Pr(X_t\le L_t\mid\mathcal F_{t-1})=F(L_t) 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

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

The paper studies nonasymptotic inference for population quantiles under local differential privacy. In addition to differential privacy, it focuses on confidence sequences (CSs). A confidence sequence consists of confidence intervals that jointly satisfy the required confidence level over time. The authors connect this construction with e-processes, using a sequential evidence process to construct the confidence sequence. The paper explains the construction in detail and provides helpful figures to illustrate it. It also establishes guarantees for privacy protection and the resulting inference.

Critical strengths
  • The paper is clearly written and well organized. The introduction explains the relevant concepts effectively, and the figures help readers understand the proposed construction.
  • The connection between e-processes and confidence sequences is presented coherently. The paper provides both privacy guarantees and nonasymptotic coverage guarantees, which I consider valuable aspects of the work.
Critical weaknesses
  • The contribution relative to closely related work needs clearer positioning. The research objective and problem setting are closely aligned with existing work on anytime-valid quantile inference under local differential privacy. I recognize the distinction between asymptotic and nonasymptotic guarantees, but I would appreciate a more explicit discussion of the methodological advances underlying this distinction.
  • The application motivation could be more concrete. Although the statistical construction is clearly explained, I would like a clearer account of the intended practical setting and the benefits of the proposed guarantees compared with existing approaches.
Questions for authors
  1. The submission discusses Cai et al. (2026), but its relationship to the extended preprint, “Asymptotic Anytime-Valid Quantile Inference under Local Differential Privacy,” deserves further clarification. Could the authors explain the specific methodological and theoretical advances relative to this work, while distinguishing the shared research objective from the new contributions?
  2. Which technical obstacles in obtaining the nonasymptotic guarantee require new ideas beyond the existing e-process and confidence-sequence framework? Clarifying these points would help me assess the significance of the contribution.
  3. Could the authors explain more concretely how the proposed confidence sequence would be used in the intended application, and why its guarantees are consequential for that application?
5 comments
AuthorsOpenReview ↗

Response to Reviewer NQ9o (Part 1 of 3)

Thank you very much for your thoughtful comments and suggestions. We address them one by one below.

W1: The contribution relative to closely related work needs clearer positioning. The research objective and problem setting are closely aligned with existing work on anytime-valid quantile inference under local differential privacy. I recognize the distinction between asymptotic and nonasymptotic guarantees, but I would appreciate a more explicit discussion of the methodological advances underlying this distinction.

Please see our response to Reviewer Exwx (W1).

Cai et al. (2025) are the closest comparison because they also construct a quantile confidence sequence (CS) under local differential privacy (LDP). They update their quantile estimator using a randomized binary comparison at one threshold per user. They use a strong Gaussian approximation for the estimation error and apply a time-uniform bound to the Gaussian term. Their bound on the remaining error is asymptotic.

The two nonasymptotic approaches in Table 1 use different information. Howard and Ramdas (2022) use sample order statistics, which our private reports do not reveal. Waudby-Smith et al. (2023) construct a private CS for the mean of bounded observations. Applied to 1Xt≤x\mathbf{1}\\{X_t\le x\\}, their CS targets F(x)F(x) at one threshold. As xx moves to locate the quantile, successive reports can have different means.

To obtain a nonasymptotic quantile CS under LDP, we use ee-processes to test H0(q):qτ=qH_0(q):q_\tau=q for each q∈Rq\in\mathbb R. The analyst cannot observe 1Xt≤q\mathbf{1}\\{X_t\le q\\} for each candidate. We use one private report about two thresholds to update the tests for all candidates. We choose Lt<UtL_t<U_t from past reports, label the three regions they define 0,1,20,1,2 from left to right, and randomize the label of the region containing XtX_t. Under H0(q)H_0(q), the resulting report ZtZ_t satisfies

q\le L_t &\implies \Pr(Z_t=0\mid\mathcal F_{t-1}) =a+\rho F(L_t)\ge a+\rho\tau,\\\\ q>U_t &\implies \Pr(Z_t\ne2\mid\mathcal F_{t-1}) =2a+\rho F(U_t)<2a+\rho\tau, \end{aligned}$$ where $a=1/(e^\varepsilon+2)$ and $\rho=(e^\varepsilon-1)/(e^\varepsilon+2)$. **The two bounds stay fixed as the thresholds move**. We use the corresponding one-sided betting factor outside $(L_t,U_t]$ and a factor of one inside. At the true quantile, the factor has conditional mean at most one in every round. Its $e$-process therefore reaches $1/\alpha$ with probability at most $\alpha$. This gives simultaneous coverage from $t=1$ for i.i.d. observations from any distribution on $\mathbb R$, without having to specify an interval containing $q_\tau$ in advance (Theorem 1). **References** - Cai, L., Hu, Q., Sun, J., and Wu, S. (2025). [Time-uniform and asymptotic confidence sequence of quantile under local differential privacy](https://openreview.net/pdf?id=Mt2UnV8jmB). *NeurIPS*, 38, 114488-114520. - Howard, S. R., and Ramdas, A. (2022). [Sequential estimation of quantiles with applications to A/B testing and best-arm identification](https://doi.org/10.3150/21-BEJ1388). *Bernoulli*, 28(3), 1704-1728. - Waudby-Smith, I., Wu, S., and Ramdas, A. (2023). [Nonparametric extensions of randomized response for private confidence sets](https://proceedings.mlr.press/v202/waudby-smith23a.html). *ICML*, PMLR 202, 36748-36789.
AuthorsOpenReview ↗

Response to Reviewer NQ9o (Part 2 of 3)

W2: The application motivation could be more concrete. Although the statistical construction is clearly explained, I would like a clearer account of the intended practical setting and the benefits of the proposed guarantees compared with existing approaches.

Q3: Could the authors explain more concretely how the proposed confidence sequence would be used in the intended application, and why its guarantees are consequential for that application?

Consider an agency estimating the median annual wage of California adults with positive wage income in a given year. It samples respondents independently and interviews them one at a time. Pay is sensitive (Cullen and Perez-Truglia, 2023), and the agency would like to stop interviewing once its estimate is precise enough. We illustrate this setting in Section 5 using 179,799 previously collected records in random order from the 2018 American Community Survey (U.S. Census Bureau, 2018). The wage distribution is right-skewed, with a median of USD 40,524 and a mean of USD 61,469.

  • The agency chooses a 95% confidence sequence (CS) for the median, a privacy budget ε=1\varepsilon=1 per respondent, a target full width of USD 5,000, and a maximum of NN interviews. The CS starts from C0=RC_0=\mathbb R on the log-wage scale. Under the acquisition condition, it becomes bounded and nonempty in finite time with probability at least 95% (Theorem C1).
  • Respondent tt compares Xt=log⁡(waget/50,000)X_t=\log(\mathrm{wage}_t/50{,}000) with two thresholds chosen from past reports. They randomize the label of the region containing XtX_t and send only that randomized label. For any two wages, the probability ratio for the same report is at most eεe^\varepsilon. This gives local differential privacy for each respondent (Theorem 1) using randomized response (Warner, 1965). The non-private CS of Howard and Ramdas (2022) requires the raw observations to compute the endpoint order statistics.
  • For each candidate median outside the two thresholds, the agency uses the corresponding one-sided betting factor. Inside the query interval the factor is one. The agency excludes a candidate once its capital reaches 1/α=201/\alpha=20 and takes the smallest closed interval containing the survivors. The coverage guarantee allows ties in wages. On the nested grid, candidates with identical betting histories share one capital value, keeping memory bounded (Theorem C2). There were 15 surviving cells at the end of the ACS run.
  • If Ct=[At,Bt]C_t=[A_t,B_t] on the log scale, the agency reports the dollar interval Dt=[50,000eAt,50,000eBt]D_t=[50{,}000e^{A_t},50{,}000e^{B_t}]. Let WtW_t be its full width and mm the population median wage in dollars. Theorem 1 gives
\Pr_F(m\in D_T)\ge0.95.$$ The agency can check the width after every interview and **still have at least 95% coverage when it stops**. Liu et al. (2023) give fixed-time inference, and the time-uniform guarantee of Cai et al. (2025) is asymptotic. In the ACS run (Figure 6), our interval first became finite after 348 reports. The Gaussian-mixture CS of Cai et al. (2025) first became finite after its burn-in of 2,125 reports. The first recorded checkpoint meeting the USD 5,000 target was 49,000 reports for our method, with interval [USD 38,336, USD 42,601], and 24,000 reports for their method. The final widths were USD 2,142 and USD 1,918, respectively. Thus our interval became informative earlier in this run, while their interval reached the target precision earlier. **References** - Cai, L., Hu, Q., Sun, J., and Wu, S. (2025). [Time-uniform and asymptotic confidence sequence of quantile under local differential privacy](https://openreview.net/pdf?id=Mt2UnV8jmB). *NeurIPS*, 38, 114488-114520. - Cullen, Z., and Perez-Truglia, R. (2023). [The salary taboo privacy norms and the diffusion of information](https://doi.org/10.1016/j.jpubeco.2023.104890). *Journal of Public Economics*, 222, 104890. - Howard, S. R., and Ramdas, A. (2022). [Sequential estimation of quantiles with applications to A/B testing and best-arm identification](https://doi.org/10.3150/21-BEJ1388). *Bernoulli*, 28(3), 1704-1728. - Liu, Y., Hu, Q., Ding, L., and Kong, L. (2023). [Online local differential private quantile inference via self-normalization](https://proceedings.mlr.press/v202/liu23q.html). *ICML*, PMLR 202, 21698-21714. - U.S. Census Bureau (2018). [2018 American Community Survey 1-year Public Use Microdata Sample, California person file](https://www.census.gov/programs-surveys/acs/microdata/access.2018.html). - Warner, S. L. (1965). [Randomized response: A survey technique for eliminating evasive answer bias](https://doi.org/10.1080/01621459.1965.10480775). *Journal of the American Statistical Association*, 60(309), 63-69.
AuthorsOpenReview ↗

Response to Reviewer NQ9o (Part 3 of 3)

Q1: The submission discusses Cai et al. (2026), but its relationship to the extended preprint, “Asymptotic Anytime-Valid Quantile Inference under Local Differential Privacy,” deserves further clarification. Could the authors explain the specific methodological and theoretical advances relative to this work, while distinguishing the shared research objective from the new contributions?

Thank you for pointing us to the extended preprint. The preprint by Cai et al. (2026a) extends the quantile confidence sequence (CS) of Cai et al. (2025), which we compare with in Table 1. They estimate the limiting variance from variation across the private stochastic gradient chains and prove how fast the new estimator converges. Corollary 8 uses a Gaussian-mixture boundary calibrated to the monitoring start mm. Under their density and chain-growth assumptions, simultaneous coverage over all t≥mt\ge m converges to 1−α1-\alpha as m→∞m\to\infty. They also apply their CS to quantile best-arm identification and sequential A/B testing. Cai et al. (2026b), cited in our Introduction, is their separate paper on federated quantile inference.

We share the goal of monitoring a population quantile using one locally private report per user. Cai et al. (2026a) use a binary comparison at one threshold to update a quantile estimator and a strong Gaussian approximation to construct their CS. We use a ternary report about two thresholds chosen from past reports to test each candidate qq directly. Under q=qτq=q_\tau, a candidate q≤Ltq\le L_t implies F(Lt)≥τF(L_t)\ge\tau, and a candidate q>Utq>U_t implies F(Ut)<τF(U_t)<\tau. The same report gives the corresponding one-sided betting factor outside (Lt,Ut](L_t,U_t], with a factor of one inside. Inverting these tests gives simultaneous coverage from the first observation,

Pr⁡F!(qτ∈Ct for all t≥1)≥1−α,\Pr_F\\!\left(q_\tau\in C_t\text{ for all }t\ge1\right)\ge1-\alpha,

for i.i.d. observations from every distribution FF on R\mathbb R, including discrete distributions (Theorem 1).

Q2: Which technical obstacles in obtaining the nonasymptotic guarantee require new ideas beyond the existing e-process and confidence-sequence framework? Clarifying these points would help me assess the significance of the contribution.

The challenge is to use one private report to build a valid betting factor for each candidate qq as the query thresholds Lt<UtL_t<U_t move. The analyst cannot observe 1Xt≤q\mathbf{1}\\{X_t\le q\\} for each candidate qq, and successive reports generally concern different CDF values.

For example, under q=qτ≤Ltq=q_\tau\le L_t, the conditional probability p=Pr⁡(Zt=0∣Ft−1)p=\Pr(Z_t=0\mid\mathcal F_{t-1}) is at least c=a+ρτc=a+\rho\tau, where a=1/(eε+2)a=1/(e^\varepsilon+2) and ρ=(eε−1)/(eε+2)\rho=(e^\varepsilon-1)/(e^\varepsilon+2). For any forecast 0<v<c0<v<c chosen from past reports, the left betting factor satisfies

=1+\frac{(p-c)(v-c)}{c(1-c)}\le1.$$ For $q>U_t$, the right comparison $\mathbf{1}\\{Z_t\ne2\\}$ has conditional mean below $2a+\rho\tau$ under the null, and we choose the forecast above this bound. Inside $(L_t,U_t]$ the factor is one. **Each candidate's position determines the bet before the report arrives**. Even if the tracker is far from $q_\tau$, the factor at the true quantile has conditional mean at most one, and the probability of ever excluding it is at most $\alpha$ (Theorem 1). A second challenge is finding a finite interval starting from $C_0=\mathbb R$. Early queries far from the quantile can use up the capital needed to rule out the tails. We **set aside part of the initial capital and release it gradually**, so we can keep betting even after early losses. Under the acquisition condition, the CS then becomes bounded and nonempty in finite time with probability at least $1-\alpha$ (Theorem C1). **References** - Cai, L., Hu, Q., Sun, J., and Wu, S. (2025). [Time-uniform and asymptotic confidence sequence of quantile under local differential privacy](https://openreview.net/pdf?id=Mt2UnV8jmB). *NeurIPS*, 38, 114488-114520. - Cai, L., Hu, Q., and Wu, S. (2026a). [Asymptotic anytime-valid quantile inference under local differential privacy](https://arxiv.org/abs/2609.21338). arXiv:2609.21338. - Cai, L., Hu, Q., and Wu, S. (2026b). [Federated learning of quantile inference under local differential privacy](https://proceedings.iclr.cc/paper_files/paper/2026/hash/8fad1ce6d16f654936b98662fce84c5d-Abstract-Conference.html). *ICLR*.
Reviewer_ExwxOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper develops a method for constructing nonasymptotic confidence sequences for population quantiles from sequentially collected data under LDP. Unlike existing methods that rely on asymptotic approximation, the proposed approach provides distribution-free coverage guarantees that remain valid over time. The method uses adaptive interval queries and a tenary randomized response mechanism to protect individual observations, together with e-processes to test and eliminate candidate quantiles. An online tracking procedure adjusts the query intervals, while a prepaid capital reserve helps the method recover from unfavorable initial queries. The authors also develop a nested-lattice algorithm that processes each observation only once and uses a limited amount of memory. They show that the method provides nonasymptotic simultaneous coverage guarantees and produces confidence intervals that become narrower at the same rate as their non-private counterparts.

Critical strengths
  • Develops confidence sequences for population quantiles under LDP, which provides distribution-free coverage guarantees that remain valid throughout the data collection process. It allows continuous monitoring and remains valid even when the stopping time depends on the observed data.
  • Does not require a prespecified bounded interval containing the target quantile, and its coverage guarantees apply to discrete and discontinuous distributions.
  • Provides theoretical guarantees for privacy and coverage. It shows that bounded confidence intervals can be obtained in finite time and establishes a convergence rate matching that of non-private quantile confidence sequences.
  • The nested-lattice algorithm processes observations in a single pass with bounded memory usage.
Critical weaknesses
  • The paper combines several existing techniques, which makes it difficult to assess its methodological novelty. The authors could better explain which aspects of the proposed framework are technically new and why existing approaches cannot be directly extended to achieve the same theoretical guarantees.
  • The empirical coverage is often close to 100%, well above the nominal 95% (e.g., Table D1), which suggests that the proposed method may be too conservative.
  • The convergence rate depends on the privacy budget, but the paper does not discuss whether this dependence is optimal.
  • The numerical comparisons focus mainly on Cai et al. Comparisons with a broader range of methods would help demonstrate the practical advantages of the proposed approach.
  • Although the paper establishes bounded memory usage theoretically, it does not report computational costs or compare its computational efficiency with competing methods.
Questions for authors
  • It would be helpful to include additional quantiles and a non-private benchmark in the real data analysis. The authors could also better explain how the simulation settings reflect the real data application, particularly in terms of sample size, distributional characteristics, and data transformation.
  • Please see the weaknesses for the remaining questions.
7 comments
AuthorsOpenReview ↗

Response to Reviewer Exwx (Part 1 of 3)

Thank you very much for your thoughtful comments and suggestions. We address them one by one below.

W1: The paper combines several existing techniques, which makes it difficult to assess its methodological novelty. The authors could better explain which aspects of the proposed framework are technically new and why existing approaches cannot be directly extended to achieve the same theoretical guarantees.

Three closely related approaches each address part of our goal of constructing a nonasymptotic quantile confidence sequence (CS) under local differential privacy (LDP).

  • Howard and Ramdas (2022) choose two ranks that bracket the population quantile qτq_\tau uniformly over time. The finite endpoints are sample order statistics satisfying

    Pr⁡!(X(kt−):t≤qτ≤X(kt+):t for all t≥1)≥1−α.\Pr\\!\left(X_{(k_t^-):t}\le q_\tau\le X_{(k_t^+):t}\text{ for all }t\ge1\right)\ge1-\alpha.

    There are two common ways to protect privacy in this setting. One is to add noise to the interval endpoints, but the analyst must first compute the two order statistics from the raw data. The other is for each user to privatize their observation before sharing it. Under our ternary randomized response mechanism, each user reports only a randomized region label. Because values in the same region have the same report distribution, the analyst cannot recover the original sample order statistics.

  • Following Waudby-Smith et al. (2024), Cai et al. (2025) use a strong Gaussian approximation to construct an asymptotic quantile CS under LDP. Their private quantile estimator satisfies

    q^t−qτ=1t∑i=1tGi+rt,Gi∼i.i.d.N(0,σ2).\widehat q_t-q_\tau=\frac{1}{t}\sum_{i=1}^{t}G_i+r_t,\quad G_i\stackrel{\mathrm{i.i.d.}}{\sim}N(0,\sigma^2).

    They bound the Gaussian term uniformly over time. Control of rtr_t is asymptotic, so their argument does not guarantee simultaneous coverage from the first observation. Cai et al. (2025, Section 6) identify a fully nonasymptotic CS for private stochastic gradient descent (SGD) iterates as a challenging extension of existing SGD error bounds.

  • Waudby-Smith et al. (2023) construct a nonasymptotic LDP CS for the mean of observations in [0,1][0,1]. Each private report has conditional mean determined by the same unknown mean μ\mu,

    E[Zt∣Ft−1]=rtμ+1−rt2,\mathbb E[Z_t\mid\mathcal F_{t-1}]=r_t\mu+\frac{1-r_t}{2},

    where rtr_t is known. If each user privatizes Yt=1Xt≤xY_t=\mathbf{1}\\{X_t\le x\\} at a fixed threshold xx, their CS covers μ=E[Yt]=Pr⁡(Xt≤x)=F(x)\mu=\mathbb E[Y_t]=\Pr(X_t\le x)=F(x). To locate qτ=inf⁡x∈R:F(x)≥τq_\tau=\inf\\{x\in\mathbb R:F(x)\ge\tau\\}, we need to vary xx. Even for bounded data, the reports then concern different CDF values and cannot be pooled under the fixed-mean guarantee. We also allow unbounded support with no known finite interval containing qτq_\tau.

We take a different approach and recast CS construction as sequential testing. We use ee-processes to test H0(q):qτ=qH_0(q):q_\tau=q for each q∈Rq\in\mathbb R. The analyst cannot observe 1Xt≤q\mathbf{1}\\{X_t\le q\\} at every candidate qq. Our key step is to use one private report about two moving endpoints to update all the candidate tests.

To update both sides, we choose Lt<UtL_t<U_t from past reports, label the three regions Xt≤LtX_t\le L_t, Lt<Xt≤UtL_t<X_t\le U_t, and Xt>UtX_t>U_t as 0,1,20,1,2, and randomize the label to obtain one private report ZtZ_t. Under H0(q)H_0(q),

q\le L_t&\implies\Pr(Z_t=0\mid\mathcal F_{t-1})=a+\rho F(L_t)\ge a+\rho\tau,\\\\ q>U_t&\implies\Pr(Z_t\ne 2\mid\mathcal F_{t-1})=2a+\rho F(U_t)<2a+\rho\tau, \end{aligned}$$ where $a=1/(e^\varepsilon+2)$ and $\rho=(e^\varepsilon-1)/(e^\varepsilon+2)$. The bounds stay fixed as the endpoints move. We use the corresponding one-sided factor outside $(L_t,U_t]$ and a factor of one inside. At the true quantile its conditional mean is at most one in every round, so the probability of ever excluding $q_\tau$ is at most $\alpha$ (Theorem 1). This gives the CS on the full real line without a prespecified search interval (Introduction, page 2, lines 70-79). **References** - Cai, L., Hu, Q., Sun, J., and Wu, S. (2025). [Time-uniform and asymptotic confidence sequence of quantile under local differential privacy](https://openreview.net/pdf?id=Mt2UnV8jmB). *NeurIPS*, 38, 114488-114520. - Howard, S. R., and Ramdas, A. (2022). [Sequential estimation of quantiles with applications to A/B testing and best-arm identification](https://doi.org/10.3150/21-BEJ1388). *Bernoulli*, 28(3), 1704-1728. - Waudby-Smith, I., Wu, S., and Ramdas, A. (2023). [Nonparametric extensions of randomized response for private confidence sets](https://proceedings.mlr.press/v202/waudby-smith23a.html). *ICML*, PMLR 202, 36748-36789. - Waudby-Smith, I., Arbour, D., Sinha, R., Kennedy, E. H., and Ramdas, A. (2024). [Time-uniform central limit theory and asymptotic confidence sequences](https://doi.org/10.1214/24-AOS2408). *The Annals of Statistics*, 52(6), 2613-2640.
AuthorsOpenReview ↗

Response to Reviewer Exwx (Part 2 of 3)

W2: The empirical coverage is often close to 100%, well above the nominal 95% (e.g., Table D1), which suggests that the proposed method may be too conservative.

We agree that the empirical coverage is often close to 100%. However, Theorem 1 guarantees at least 95% simultaneous coverage for our nonasymptotic CS under i.i.d. sampling from any distribution. The high coverage rates observed in Table D1 are consistent with this guarantee.

To understand why coverage was so close to 100% in this experiment, we examined the betting process at the true median.

  • At each step, the private report provides evidence about two query endpoints, LtL_t and UtU_t. When a candidate qq lies in (Lt,Ut](L_t,U_t], its betting factor is et(q)=1e_t(q)=1. When the true median lies in this interval, the procedure can therefore accumulate evidence against candidates outside it while leaving the capital at the median unchanged.
  • We replayed 500 paths from the standard-normal setting with τ=0.5\tau = 0.5 and ε=1\varepsilon=1. On 414 of the 500 paths, the capital at the true median stayed at 1 for all five million steps. The largest value across the remaining 86 paths was 15.37, below the rejection threshold of 1/α=201/\alpha=20. Thus the interval could narrow by excluding candidates on either side while retaining the true median on all 500 paths.

We found that empirical simultaneous coverage can be closer to 95% in other settings. With ε=2\varepsilon=2 and initial position 0, our median CS covered the true median throughout five million observations on 482 of 500 paths (96.4%) for a bounded uniform mixture and 487 of 500 paths (97.4%) for an unbounded exponential-tail mixture.

Other methods for quantile CSs also showed high empirical coverage. In our simulations, the quantile CS of Howard and Ramdas (2022) had 99.8%-100% simultaneous coverage. Figure 3 of Cai et al. (2025) shows that their stitched CS had less than 1% cumulative miscoverage after burn-in for the standard-normal median under LDP.

W3: The convergence rate depends on the privacy budget, but the paper does not discuss whether this dependence is optimal.

Theorem 2 gives the contraction rate for a fixed privacy budget ε\varepsilon. For fixed τ∈(0,1)\tau\in(0,1) and under the assumptions of Theorem 2, we have

\sqrt{\frac{\log\log t}{t}}, \qquad \rho(\varepsilon)=\frac{e^\varepsilon-1}{e^\varepsilon+2}.$$ For each fixed privacy budget, the rate in $t$ is $\sqrt{\log\log t/t}$. As noted in Remark 2, this matches the rate of the non-private quantile CS of Howard and Ramdas (2022) and the stitched asymptotic LDP quantile CS of Cai et al. (2025). Cai et al. (2025, Theorems 1 and 3) fix the randomized response parameter when studying how their asymptotic CS contracts with sample size. Their results leave the optimal dependence on $\varepsilon$ open. We also study contraction at a fixed privacy budget, with a nonasymptotic simultaneous coverage guarantee. The explicit factor $1/\rho(\varepsilon)$ is asymptotic to $3/\varepsilon$ as $\varepsilon\to0$, but Appendix E.3 does not quantify the remaining dependence through $C_\varepsilon$. **Whether the full width has the best possible dependence on $\varepsilon$ remains open**. Figures D10-D11 in Appendix D.5 illustrate the scaling for standard normal and standard Cauchy data at $\tau\in\\{0.3,0.5,0.7\\}$ and $\varepsilon\in\\{0.5,1,2,3,\infty\\}$, with 1,000 replications per setting. At $T=5\times10^6$, the normalized mean full width $\rho(\varepsilon)f(q_\tau)\\,\mathrm{AW}(T)\sqrt{T/\log\log T}$ ranged from approximately 2.6 to 2.9 across all 30 settings, so the normalized widths were similar across budgets at that sample size. **References** - Cai, L., Hu, Q., Sun, J., and Wu, S. (2025). [Time-uniform and asymptotic confidence sequence of quantile under local differential privacy](https://openreview.net/pdf?id=Mt2UnV8jmB). *NeurIPS*, 38, 114488-114520. - Howard, S. R., and Ramdas, A. (2022). [Sequential estimation of quantiles with applications to A/B testing and best-arm identification](https://doi.org/10.3150/21-BEJ1388). *Bernoulli*, 28(3), 1704-1728.
AuthorsOpenReview ↗

Response to Reviewer Exwx (Part 3 of 3)

W4: The numerical comparisons focus mainly on Cai et al. Comparisons with a broader range of methods would help demonstrate the practical advantages of the proposed approach.

Cai et al. (2025) and Howard and Ramdas (2022) are our most direct benchmarks. Both construct CSs for population quantiles. Figures 4-5 and Appendix D.1 compare our method with the private CSs of Cai et al. (2025). Figure 3 (page 8) compares our method with the non-private Howard-Ramdas CS.

Under the conditions of Theorem 2, our width and the Howard-Ramdas width contract at the same rate in tt, O(log⁡log⁡t/t)O(\sqrt{\log\log t/t}) (Remark 2, page 7). For the standard-normal median after five million observations, the mean full widths were 0.00511 for Howard-Ramdas and 0.00526 for our method without privacy. At ε=3\varepsilon=3, our mean width increased to 0.00605, illustrating the cost of local privacy in this setting.

Liu et al. (2023) construct an asymptotic quantile confidence interval under LDP at a fixed sample size. We compare quantile CSs because our target is simultaneous coverage over time.

W5: Although the paper establishes bounded memory usage theoretically, it does not report computational costs or compare its computational efficiency with competing methods.

We compared our method with both CSs of Cai et al. (2025) and the CS of Howard and Ramdas (2022). Each C++ implementation used the same first ten standard-normal streams from Experiment 1, updating a median CS one observation at a time on one AMD Ryzen Threadripper PRO 3995WX core. The table reports median runtime and peak memory for the stored state across the ten streams. Both Cai CSs cached step sizes. At 5M users, uncached Cai GM used 1.94 KiB and took 0.745 s.

MethodPrivacy budgetTime at 1M usersTime at 5M usersPeak memory at 1MPeak memory at 5M
Proposedε=1\varepsilon=10.132 s0.648 s6.10 KiB6.10 KiB
Cai et al. (2025), Gaussian mixture (GM)ε=1\varepsilon=10.124 s0.662 s1.50 MiB1.50 MiB
Cai et al. (2025), stitchedε=1\varepsilon=10.125 s0.664 s1.50 MiB1.50 MiB
ProposedNon-private0.121 s0.627 s2.91 KiB2.91 KiB
Howard and Ramdas (2022), exact order statisticsNon-private0.684 s5.674 s53.41 MiB267.03 MiB

At ε=1\varepsilon=1, all three implementations processed five million users in about 0.65 seconds. Without privacy, our method stored only the surviving cells and used 2.91 KiB at both sample sizes, consistent with Theorem C2. The exact Howard-Ramdas implementation stored one entry per observation, and its peak memory increased from 53.41 MiB to 267.03 MiB.

Q1: It would be helpful to include additional quantiles and a non-private benchmark in the real data analysis. The authors could also better explain how the simulation settings reflect the real data application, particularly in terms of sample size, distributional characteristics, and data transformation.

Thank you for this valuable suggestion. Figure 6 (page 9) now includes our non-private CS and the non-private CS of Howard and Ramdas (2022). On the same wage records, our median interval first became finite after 99 users without privacy and 348 users at privacy budget 1. The final widths were USD 1,001 and USD 2,142, respectively. The 30th and 70th percentiles showed the same pattern as the median. Specifically, our private interval became finite earlier than the Gaussian-mixture CS of Cai et al. (2025), which was narrower at the end. Without privacy, the upper and lower bounds of our CS were close to those of Howard and Ramdas (2022).

The 2018 American Community Survey wage sample (U.S. Census Bureau, 2018) contains 179,799 records, close to the 180,000-user checkpoint in our simulations. The lognormal setting reflects the right skew of wages in dollars. In the wage sample, the mean was USD 61,469 and the median was USD 40,523.88. We use Xt=log⁡(waget/50,000)X_t=\log(\mathrm{wage}_t/50{,}000) in the application. This preserves wage ranks and makes the simulation starting value of zero correspond to an annual wage of USD 50,000. We transform the interval endpoints back to 2018 dollars for reporting. Changes in the revised manuscript are highlighted in blue.

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.
  • 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.
  • U.S. Census Bureau (2018). 2018 American Community Survey 1-year Public Use Microdata Sample, California person file.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary for AC and Reviewers

Dear AC and Reviewers,

Thank you for your careful reviews and constructive feedback. We highlight three points from our responses.

  • Methodological contribution. Existing methods rely on raw observations, large-sample approximations, or a fixed mean. In our responses, we explain why these methods do not directly yield a nonasymptotic confidence sequence for a population quantile under local differential privacy. Our key idea is to turn interval construction into a sequential testing problem. We choose two thresholds from past reports and use one ternary private report per user to update the tests for all candidate quantiles. Inverting these tests gives simultaneous coverage from the first observation without requiring known bounds on the quantile. (Exwx W1, NQ9o Q2, QPgb W1)

  • Coverage and interval width. At the nominal 95% level, empirical simultaneous coverage was 96.4% and 97.4% in two additional mixture settings. For the standard-normal median, the median time to the first finite interval was 237 users for our method and 58,561 for Cai GM. Cai GM gave narrower intervals at large sample sizes. (Exwx W2, QPgb W3-W4)

  • Practical comparisons. We added the non-private benchmark of Howard and Ramdas (2022) to the wage analysis in Figure 6 and reported runtime and memory use for all three approaches in our response. (Exwx W5 and Q1)

We would like to summarize the main advantages of our method.

  • We establish nonasymptotic simultaneous coverage for a population quantile under local differential privacy. Under some conditions, our confidence sequence has the same width contraction rate as the non-private CS of Howard and Ramdas (2022).

  • Our simulations show the advantage of our method when inference is needed at small sample sizes. Our coverage guarantee holds from the first observation, and our intervals became finite earlier than the asymptotic CS of Cai et al. (2025). Without privacy, our CS produced intervals similar in width to those of Howard and Ramdas (2022) at a much lower computational cost.

Best regards,

The authors

References

AuthorsOpenReview ↗

Follow-up Summary for AC

Dear Area Chair,

We are grateful to Reviewers NQ9o and QPgb for reconsidering our paper and raising their scores. In the follow-up discussion, we clarified how our method differs from that of Cai et al. (2025) in response to Reviewer QPgb's concern about novelty.

Following the asymptotic confidence sequence (CS) framework of Waudby-Smith et al. (2024) and the parallel stochastic gradient descent approach of Zhu et al. (2024), Cai et al. (2025) established a strong Gaussian approximation for their private quantile estimator and obtained asymptotic time-uniform coverage. Our quantile CS under local differential privacy (LDP) guarantees simultaneous coverage from the first private report, even when the data determine when to stop. To obtain this guarantee, we invert sequential tests of candidate quantiles, an approach that differs fundamentally from the Gaussian approximation used by Cai et al. (2025).

  • Our online tracker uses past reports to choose two thresholds so that a single private ternary report can update the tests for all candidate quantiles.
  • Our nested-lattice algorithm groups candidates with identical betting histories, allowing us to perform these updates exactly in one pass with bounded working memory.

An interesting advantage of our method is robustness to initialization. In Figure 5, starting far from the true quantile had little effect on our empirical coverage but substantially reduced that of the Gaussian-mixture CS of Cai et al. (2025). Our coverage guarantee also requires weaker distributional assumptions. In the middle column of Figure 4, our CS maintained high empirical coverage even though the density jumps at the median, violating the continuity assumption of Cai et al. (2025).

In response to Reviewer Exwx, we also derived a matching lower bound for the privacy dependence in Theorem 2. We considered a family of distributions with the same positive density near their target quantiles. In the worst case over this family, the 1/ε1/\varepsilon dependence of the long-run width coefficient is optimal up to constant factors under strong privacy among sequentially interactive LDP procedures with the same guarantees.

Thank you for considering these points in your assessment.

Best regards,

The authors

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.
  • Waudby-Smith, I., Arbour, D., Sinha, R., Kennedy, E. H., and Ramdas, A. (2024). Time-uniform central limit theory and asymptotic confidence sequences. The Annals of Statistics, 52(6), 2613-2640.
  • Zhu, W., Lou, Z., Wei, Z., and Wu, W. B. (2024). High confidence level inference is almost free using parallel stochastic optimization. arXiv:2401.09346.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.