Time-uniform and Asymptotic Confidence Sequence of Quantile under Local Differential Privacy
Authors: Leheng Cai
Qirui Hu
Juntao Sun
Shuyuan Wu
Venue: NeurIPS 2025 poster ()
Keywords: Confidence sequence
local differential privacy
quantile
stochastic gradient decent
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: In this paper, we develop a novel algorithm for constructing time‑uniform, asymptotic confidence sequences for quantiles under local differential privacy.

Abstract: In this paper, we develop a novel algorithm for constructing time-uniform, asymptotic confidence sequences for quantiles under local differential privacy (LDP). The procedure combines dynamically chained parallel stochastic gradient descent (P-SGD) with a randomized response mechanism, thereby guaranteeing privacy protection while simultaneously estimating the target quantile and its variance. A strong Gaussian approximation for the proposed estimator yields asymptotically anytime-valid confidence sequences whose widths obey the law of the iterated logarithm (LIL). Moreover, the method is fully online, offering high computational efficiency and requiring only $\mathcal{O}(\kappa)$ memory, where $\kappa$ denotes the number of chains and is much smaller than the sample size. Rigorous mathematical proofs and extensive numerical experiments demonstrate the theoretical soundness and practical effectiveness of the algorithm.

Time-uniform and Asymptotic Confidence Sequence of Quantile under Local Differential Privacy
Leheng Cailt, Qirui Hu Juntao Sun Shuyuan Wu
1 Department of Statistics and Data Science
Tsinghua University, Beijing, China
School of Statistics and Data Science
Shanghai University of Finance and Economics, Shanghai, China
Institute of Big Data Research, Shanghai University of Finance and Economics, Shanghai, China
cailh22@mails. tww.ghussinguuuu..mm edu. Setirui@@aail...ai edu. cn sunjuntaol @stu. sufe. edu wushuyuantmail.cm sufe. edu cn
Abstract
In this paper, we develop novel algorithm for constructing time-uniform, asymp- totic confidence sequences for quantiles under local differential privacy (LDP). The procedure combines dynamically chained parallel stochastic gradient descent (P-SGD) with a randomized response mechanism, thereby guaranteeing privacy protection while simultaneously estimating the target quantile and its variance. A strong Gaussian approximation for the proposed estimator yields asymptotically anytime-valid confidence sequences whose widths obey the law of the iterated logarithm (LIL). Moreover, the method fully online, offering high computational efficiency and requiring only ((k) memory, where & denotes the number of chains and much smaller than the sample size. Rigorous mathematical proofs and ex- tensive numerical experiments demonstrate the theoretical soundness and practical effectiveness of the algorithm.
Introduction
Mobile sensor traces (uccelerometer, gyroscope, wireless- charger emissions) can be reverse- engineered to reveal routes, speech, and browsing habits (30 57 3 37). This shows privacy risks arise whenever fine-grained data are aggregated and mined; Differential Privacy (DP) mitigates this by adding calibrated noise so any individual's 's presence has negligible effect (22]. But DP assumes trusted central curator, model broken by the Netflix deanonymization and the March 2023 ChatGPT exposure [41 34 Local Differential Privacy (LDP) removes that single point of failure by randomizing data on-device and is already used in Google's 's RAPPOR, Apple's ' iOS telemetry, and Microsoft's
's Windows diagnostics. [20 24 As data ecosystems grow, LDP shifts analytics toward provable, user-centric privacy.
Quantile estimation and inference play critical role in a variety of scientific and practical fields. In finance, quantiles such as value-at-risk and expected shortfall help manage portfolio risks under regulatory requirements and market volatility [10, 4]. Accurate estimation of extreme quantiles is especially important for capturing heavy-tailed financial risks [51]. In healthcare, quantile methods identify clinically significant thresholds, such as safe medication doses and treatment effectiveness
"Corresponding Author
The authors are listed in alphabetical order with equal contribution
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

551, and guide resource allocation in treatment prioritization [56]. Reliability engineering also frequently employs quantile estimation to establish conservative safety standards for machinery in harsh operating conditions [8 29] In addition, policy evaluation also benefits from quantile approaches to capture intervention effects across diverse population groups, highlighting impacts that mean-based analyses may miss [ 33 [5]. Unlike traditional methods focused on averages, quantile-based methods are robust when dealing with skewed or heavy-tailed real-world data, thus providing deeper insight into complex data distributions [9]. More discussion can be found in [31.
substantial body of literature addresses quantile estimation under either CDP or LDP. Early contributions in the CDP setting include [23 33). More recent work, such as 48 proposes a rate-oltimal sample-quantile estimator that avoids histogram evaluation, and [26] extends this line of research to the simultaneous estimation of multiple quantiles. Quantile estimation under CDP remains an active topic, with applications ranging from hounded-suppone data [2] to large-scale query systems [.. In online scenarios such as continual observation [21], algorithms can compress recompute the added noise at each time step to improve efficiency 50 Both cases require access to raw data and apply the privacy mechanism iteratively. In the LDP setting, the curator never observes raw data but only privacy-protectee challenging to design algorithms that achieve accurate quantile estimation while supporting rigorous statistical inference; for example, [38] proposed an SGD-based estimator, [39 studied inference for simultaneous quantiles, [7] investigated federated quantile inference. and considered hierarchical mechanisms and noisy binary search.
reports supplied by users. This constraint makes it considerably more
Inference on quantiles under an LDP constraint is challenging because it requires estimating the asymptotic variance (or other normalizing constants) of the LDP quantile estimator. Classical central limit theorem results show that the efficiency of a quantile estimator hinges on the density value at the true quantile. For SGD-based methods, however, this density is difficult to recover using only the iterates or perturbed gradients. Moreover, estimating the Hessian matrix is non-trivial, owing to the non-smoothness of the quantile loss, even if one is willing to spend additional privacy budget. Pointwise confidence intervals can be built via seff-normalization or random-scaling techniques, but asymptotic sequential inference requires an almost surely consistent variance estimator; see (52). Recently, [58] developed a righ-confidence inference framework using P-SGD with identical initial values across chains, thus obtaining an i.i.d. sequence. In their theoretical results, the number of chains is fixed and cannot ensure the consistency of the variance estimator. Inspired by this smart approach, we consider a dynamically chained P-SGD whose number of chains grows with the sample size ensure variance consistency.
We highlight our contributions as follows:
(i) We develop a novel algorithm based on the dynamically chained P-SGD for constructing time- uniform, asymptotic confidence sequences for quantiles under LDP. The procedure operates fully online, offering high computational efficiency while requiring only (x) memory, where is the number of chains and diverges to infinity at a rate much slower than T. e.g., at the order of log T.
(ii) We derive an almost surely Gaussian approximation for the Jolyak-Ruppert-yyy quantile obtained by P-SGD. This result is non-trivial even in the non-private setting due to the non-smoothness of the loss function and its gradient. Notably, our strong Gaussian approximation is more general than those in [54] and (58), both of which address SGD with smooth loss functions. While the latter only establishes an L2 approximation for SGD within a fixed chain, which is not applicable to sequential inference. Our approximation rate is Oo.e. ((T/ log log T) -1/2). faster than the LII. rate, yielding asymptotically anytime-valid confidence sequences for quantiles.
estimator of
(iii) We propose an almost surely consistent estimator of the quantile variance that relies only on the iterates of P-SGD and incurs no additional privacy cost. Unlike [58), which uses fixed number of chains, we allow the number of chains to grow with the sample size T to ensure the consistency of variance estimation. As by-prouuct, the true density at the target quantile can also be consistently estimated under LDP. To the best of our knowledge, this is the first result on sequential inference for quantiles within the LDP framework.
The remainder of this paper is organized follows. We first review the key concepts of DP and LDP. Next, we introduce our methodology, detailing the proposed algorithms together with the theoretical guarantees. Finally, we present experimental results that demonstrate the effectiveness of the approach. All theoretical proofs and additional simulation results are established in Appendix.
2

---

2 Methodologies
First, we introduce the mathematical definition of LDP and the asymptotic confidence sequence. Then, we will introduce the problem setting and algorithm details.
Definition (Differential Privacy, see (22)) A randomized algorithm A, taking a dataset consist- ing of individuals as is input, is (c,8) ( -ifffereenial private if. for any pair of datasets S and S' that differ in the record of single individual and any event E, satisfies the condition below:
PP(((S) E] S e'P(A(S) E +
When 6 = 0, A is called c-differentially private (c-DP).
Definition 2 (Local Differential Privacy,see (32
An (c, -randomiee R X Y is (c, 6)-
differentially private function taking a single data point as input.
CDP regulates the distribution of released data rather than the curator's credibility. A trusted curator can centrally add noise, keeping algorithm design simple and accuracy loss modest g
LDP takes stricter view by removing any trust assumption. The curator merely coordinates users, each holding a private value X, In each round it selects a user and specifies a randomized mechanism Rg Users verify that the stated (e. 8) guarantee suits the study, apply R2 to their data, and return the perturbed result. Interaction may fully adaptive, sequential, or non-interacttve; we adopt the tightest, -da-addptive model, fixing all user-randomizer pairs before data collection (Definitions 2.3 and 2.6 in (12). Unlike CDP, where the curator adds noise, under LDP the curator must draw inference solely from rsnd-randd data.
From an inference perspective, the gap between central-DP (CDP) estimator and its non-private analogue is typically (n) Consequently, after vn scaling, both estimators share the same asymptotic distribution, and one can estimate the associated variance from the (slightly perturbed) data by spending a modest additional privacy budget. By contrast, for locally private procedures, the error of an LDP estimator is usually On 1122), which alters the limiting distribution and inflates the asymptotic variance. Moreover, in most practical settings, the variance cannot be consistently recovered from locally privatized data that were collected solely for point estimation.
Definition 3 (Asymptotic confidence sequences, see (52) Let T be a totally ordered infinite set (denoting time) that has minimum value to T. We say that the intervals (0, Lt, Or + Ut) centered at the estimators (0t)eeT with non-zero bounds L,, U, O, Vi E form a (1 a)- asymptotic confidence sequence (AsympCS) for sequence of real parameters (0:) if there exists a (typically unknown) non-asymptotic (1 a)--s (0. - LT, 0.,0.+ DEET for (0t)LET -, i.e. satisfying
P 00 T, 0, + +U:)) 31 a, and Le, Ue become arbitrurily precise almost-sure approximations to Lū and Uj
L as and U, /U, 03
Compared with classical asymptotic confidence intervals, AsympCS offer several advantages and have therefore attracted considerable research attention; see, for example, 44) 28 27). AsympCS quantifies uncertainty uniformly over all sample sizes, rather than at a single, pre-specified size. To guarantee valid coverage across this entire time horizon, the requisite consistency must hold almost surely, rather than merely in probability, as emphasized by [52].
We formulate the problem follows. Let { be independent observations drawn sequentially from a distribution F. Our goal is to construct an AsympCS for the -uuantile of F, denoted by x", ie. F(x*) T, under a LDP framework.
To privatize [ we adopt the interactive, permutation- binary-respone mechanism of which is optimal in certain regimes. Let W; and V2 be i.i.d. Bernoulli variables, mutually independent and also independent of & with
P(W, 1)
IPWW, 0) = 1 r-,,
P(V/ 1) PPVV, 0) 1/2.
3

---

For any ( - (5, W,WW,, V and scalar I, define
C(x,()= = + 2rt
((<=))-(-W)(--)) 1-++ 2rt
= S
1 > x: ] +(1-
2
2
Given sequence (2ra )f= this yields the privatized sequence (G( (t) which be viewed as a permuted stochastic gradient. The parameter r is the truthful-response rate, and 38 shows that the mechanism e-LDP with e log(1 + r) log(1 (o(1-r). r)..
Using the privatized gradients, we run the SGD iteration
r+++ xt - ?pt G(
0=.....,
Although this approach yields a consistent LDP estimator of the target quantile, estimating its asymptotic variance from {G( (t)), alone is difficult. To address this, we employ parallel SGD (P-SGD): the data are split into disjoint chains, all initialized identically,
1k,t+1 The Thr G( (4,211),
== o...... Th 1, k= -
(1)
When each chain has the same length, the trajectories {I asymptotic variance to be estimated by the sample variance across chains. Ensuring consistency, however, requires - oc. Repartitioning the data would disrupt the SGD structure and consume additional privacy budget, so we adopt dynamically chained P-SGD in which grows with T.
Th ) are i.i.d. across k, allowing the
To accommodate a vare-ngrying number of chains, we let K h(T), where h 24 + 2+ is an increasing. sescewise-constan function. Set Ko == h(1). For each & E N define my := (T) denotes cardinality. We require
h(T) = Ko + kH/, where
mo 2 Ko
and
mk
Σ m,
E E
Ko
This condition ensures that no new chain will be added before the new chain is aligned in length with the previous ones. For example, h(T) |clog, T] + Kg with a a//e max + 2, Ko} satisfies these conditions. Algorithm provides the index of the chain to which each sample from 1 T is assigned. Figure provides a visual illustration.
When the 7' sample arrives, let T3 denote the number of observations held by the k-th chain. Our online quantile estimator is
T The
Tx
TT
(2)
ie., weighted average of the chain-wise means. The asymptotic variance 0² of the approximating Gaussian variables Z, 's in Theorem is estimated by the weighted sample variance
T
1/2 T
I1.1
(3)
T
T
1=l
Because both the quantile estimator (2) and the corresponding variance estimator S are computed directly from the P-SGD iterates they each satisfy e-LDP with log(1 + log(1 r).
Theoretical results
To investigate the asymptotic properties, some mild assumptions are introduced.
(A1) The density f(-) is continuous and f(x") > 0.
(A2) For some constant Cp > 0, (5'()) is uniformly bounded by Cy:.
(A3) For some constant a E (1/2, 1), the step size n7 x t
(A4) As T +
and < 11((/

---

Algorithm Data allocation for parallel runs
Input T' and function h(.).
2: Initialize array nums of length Ku h(0) with all zeros
3: Initialize array result of length T with all zeros
4: for = 1-110 to T do
5: if' hi(i) > h(i
then
Append the end of nums
6: end if
7: <- index of the first minimum in nums;
result(d k;
nums [k] <- nums (M) +
8:
end for
9:
Output result
T+2
T+l T+i
MTT + 1 M(T)
New Observations Arrival
40
1
1
2
K
K+1
Initial
Update Criterion
Update Criterion with New Chain
without New Chain
K
K T
T74
Figure 1: Overview of the Algorithm
(1) The left panel illustrates the initial state with T (2) When new observations arrive, the algorithm determines chain. If not, new observations are sequentially added to existing chains, right panel,
observations partitioned into K chains.
whether to introduce as shown in the middle panel. (3) If required, a new chain created, as illustrated which continues receiving observations until it matches the length of existing chains. The update criterion ensures no additional chain is required before alignment.
Assumptions (A1) and (A2) are regular conditions for the distribution function. Assumption (A3) is standard in the literature; see [54]. Assumption (A4) restricts the rate at which the number of chains diverges with the sample size. The divergence rate can be arbitrarily slow, which offers great flexibility in practical implementation.
Theorem Under Assumptions (AI)-A44), for the quantile estimator 2 there exist i...d normal
E.'s Z with mean zero and variance o² 2²(27 1)2) (2(x") (x*)), such that
2 = Oo.s. (V10g 110gg log
1 T
TT
T
Theorem [ establishes a strong Gaussian approximation for 2T- - x", providing an almost surely result rather than in probability. Interestingly, for each fixed although Ft,4 dependent across t, the deviation of the final weighted sum estimator Ty from the true value x can be approximated by the average of T i.i.d. Gaussian random variables. Besides, the rate is significantly faster than the law of iterated logarithm bound, which crucial for constructing asymptotic confidence sequences. Notably, (58) derived Gaussian approximation result for single chain, but their approximation error is measured in terms mean squared error rather than an almost surely bound, which is not applicable to sequential inference. On the other hand, although (54) provides almost surely Gaussian approximation, both [54] and (58 consider smooth loss and assume average Lipschitzness of the gradient, which does not hold for the quantile loss. In fact, the gradient of quantile loss only
enjoys average 1/2-Hölder smoothness, since [E(1 < œ) 1(g S 2) 1/2 S | 2/2/2 for any random variable with uniformly bounded density functions, which poses challenges for theoretically analyzing the approximation error.
5

---

The next theorem shows the almost surely consistency of o7.
Theorem 2 Under Assumptions (A1)-(A4), for the variance estimator T 00.
- (2T 1) f2²")
oa.s. (1).
A byproduct of Theorem is that it enables the estimation of the density at the true quantile xt under the framework of differential privacy, i.e., v(1 - (2T 1)2
(4r
Let lut - TT., HrT + TTmm be any confidence sequence started from time m 2 for the unknown mean of a Gaussian distribution with unit variance.
Theorem Under Assumptions (A1)-A4), there exists some nonasymptotic (1 ---oofddeeence - sequence (2r- BE-OTTT m. By B TT. i.e., P (VT m, x² [oT OTT.m T7 ). 1-a,
such that /0/11/m//rr11
= Oa.s. (1) as T
With the help of the strong consistency established in Theorem 2 Theorem 3 provides a general framework for constructing AsympCSs for quantiles under the LDP setting, requiring only confi- dence sequence for Gaussian random variables with unit variance. Existing confidence sequences for Gaussian variables in the literature include different types of boundaries, for example, the stitched
boundary developed by
28 with a concentration rate of O (Vlog T/T)
log log( (2T) m, e}) + 0.72 log 10.4/a)
Tm 1.7v
(4)
T
Robbins' mixture boundary
44
and
45
which achieves concentration rate of O ((ylog Vlog'o T/T)::
{g
(a))² log (m/
TT.m
where g(a) 2(1 +(a) + ab(a))
(5)
T
Here, (-)) and (--) are the CDF and PDF of a standard Gaussian random variable, respectively. For m = 1. the Gaussian mixture bound can be generalized to the following, see [52].
p + +1) T2p²
V TPp² +1
TT,1
log
Vp pp>0 0.
(6)
a
By tuning the hyperparameter in (6). one can minimize the width of the confidence interval at specific time point given significance level
We note that the Robbins' boundary is not inferior due to its slower asymptotic convergence rate, On the contrary, it is often preferable in practice because it tends to be tighter in early stages with finite samples, as also discussed in [52]
There may be some confusion regarding the burn-in strategy used in SGD-based methods versus the construction of AsympCSs starting from index m. The burn-in strategy discards a predetermined number of initial iterates to mitigate the effect of unstable early updates on the final averaged estimator, thereby reducing the effective sample size. contrast, the coverage probability calculation starting from m retains all iterates from 1 to and uses them to construct the AsympCSs based on equations (5). If burn-in of b iterations applied and coverage probabilities are reported starting from index then the AsympCSs should begin at iteration + + 1.
Combined with estimators 2), (3) and Theorems 3 .e summarize the construction of the LDP (1 - a) -SyympCS in Algorithm 2 It is worth noting that the entire procedure can be computed sequentially, storing only the most recent updates from each chain, thereby requiring approximately (kx) memory, where < T. As straightforward derivation, following Theorems and the LDP point-wise confidence interval of quantile is concluded as follows.
Corollary Under Assumptions (AI)-(A4), the asymptotically correct (1 a) posnt-wise confidence interval of quantile x² is [ØT 0T21-a/2/VT कo + @rm1-/2/ i.e.
xx E ß5r 021-a/2/ VT,5r 021-0/2/ / 2 a, as T - 0o, where 21-a/2 is the (1 a/2) //quniiaeeeeee of standard normal random variables.

---

0.89
0.32
0.51
5.82
0.80
1x10"
2x100
3x 4x 5xx10
3.80
1x:00 2x-
3x110 4x100 5x" 3.00
1x 2x 5x10 4x10 5x10
Figure 2: Plots of trajectories when confidential data come from standard normal distribution N(,, 1) for pointwise confidence interval from Corollary (in red with upward-pointing triangles), pointwise confidence interval from
[8] (in purple with asterisks), proposed AsympCS based (4) (in blue
with circles) and 6 (in green with squares) with = 0.8, r 1, 0.9, 0.75 (left, middle and right
panel).
It is well known that the tail of a self-normalized distribution is typically heavier than that of the normal distribution, noted in [77. As a result, the pointwise confidence interval constructed based on Corollary | is more efficient than those proposed in [38]. We further provide a visualization comparing our constructed AsympCSs, the pointwise confidence intervals, and the intervals from [38] in Figures and A.7 One can observe that although the asymptotic widths of both pointwise confidence intervals are similar, our proposed intervals tend to slightly narrower. Additionally, AsympCS constructed using equation (6) is numerically tighter than the one based on equation (4)
although the latter enjoys faster asymptotic convergence rate.
Algorithm Algorithm to construct LDP AsympCS quantile
1: Input data: {&:] truthful response rate [0, 1J. significance level a, initial sample size m
for sequential inference, initial number of chains learning rate {n >T= initial index = 0
and initial values across all chains T To-
2: For t = I...
3:
Computed the current update chain 4 result[t] from Algorithm Set = nhe = 0, In.,n = 0.
4:
If >
5: EndIf
6:
Require perturbed gradient G( St)-
7:
Update in 1,- chain: Zl,mm, +1 2l,,, T/m,, GlIlamy St),
8:
31, = (n4, 34, + I4, -i,,,,,, +1 /mi,, + 1), nt, nt, +1,
Update of quantile estimator and corresponding variance estimator: 9:
N n1 t
Tkk Ik:
1/2
n
Ik
n2
27
t
End For
11: Output the (1 -ASymmpCC computed by or
[
Tem,, T4 + @emmm for f. = m,
T, where 7t. can be
Experiments
4.1 General setting
In this section, we evaluate the finite-sample performance of the proposed method. The confi-
dential data are generated from two distributions: standard Normal A/ 1) and standard Cauchy C(O. 1). Target quantiles are set to 0.8, 0.5, 0.3. The truthful response rates are chosen as privacy budgets e = log(1 + r) - log(1 r) of too, 2.94, 1.95, 1.10, 0.51, respectively. The algorithm uses random initialization with standard
r = 1, 0.9, 0.75, 0.5, 0.25, corresponding
7

---

Normal (0,, 1) of all chains and step sizes set to Th,t 1/t" with a = 0.6 for all chains as well, satisfying Assumption (A3). Following [35]. we incorporate a burn-in strategy into the algorithm to reduce the impact of initial parameter bias and enhance the stability of statistical inference, with the number of burn-in samples being about (0.25/r2)% of the total sample size. Each experiment replicated 2000 times using 110 Intel Xeon R Platinum 8352V CPU @ 2.10GHz CPUs with 360G B memory and 1200GB storage.
4.2 Results
Our first analysis focuses on the unineun convergence performance. We consider the number of chains as a function of time via h(t) = [8 (T])]] for t < T/5, and h(t) [8 1og (t) for / 2 7/5, where 7 = 5. 5,000,000 denotes the total sample size. Time-uniform 95% AsympCSs constructed using the stitched boundary in 4 and the Gaussian mixture boundary in (6) with 0.001. We report the time-uniform type error rates and the average lengths of the resulting CSs. As benchmark, we include the order-statistics-basse non-private method proposed in [27].
Results for the standard normal distribution based on equations and (6) are presented Figures
and 4 while additional results for the standard Cauchy distribution are provided in Appendix A
These numerical results are consistent with Theorem [ Figure 3 shows that all methods maintain the nominal type error rate (5%) across various values of the parameters r and 7 for both AsymCSs based on (4) and ( Figure indicates that the average length of the constructed AsympCSs decreases the privacy budget increases. Moreover, From Figure Rl one observes that the AsymCSs based on (4) will be more conservative than (6) in most stages under finite sample sizes, which is also reflected Figure [
Therefore, the AsymCSs based on (6) enjoys the better finite sample performance in our setting, even its theoretically asymptotic rate O / Vlo T/T), which is slower than O (Vloo log T/T).
Notably, when r = 1, the non-DP AsympCSs based on P-SGD are tighter than the nonasymptotic CSs from 277 while still maintaining valid type error control. These findings suggest that our proposed confidence sequences can provide improved efficiency for quantile inference, even in the absence of privacy constraints. similar phenomenon observed under the Cauchy distribution setting, as illustrated in Figures A.3 and A.4
Next, investigate finite-sample variance estimation क.. To illustrate consistency with respect to T. we set = 20, 40, 80, 100. Relative absolute errors (RAEs), defined as | - a² 1/02, are summarized via boxplots in Figures [A.5] [A.5]and A.6 in Appendix The results demonstrate that RAEs consistently decrease as T increases, aligning with Theorem Furthermore, for a fixed T', smaller values of yield lower RAES.
Finally, to further strengthen our simulation study, we conducted additional experiments, including: (1) sensitivity analysis of tuning parameters, (2) finite-sample performance under mixture of Beta distributions, and (3) a comparison between our proposed method and (38) under specific settings. Across these settings, the results consistently demonstrate the robustness and effectiveness of our approach; see details in Appendix A
Real data application
In this section, we empirically evaluate the effectiveness of our proposed method on the following two representative real datasets widely used in privacy research:
Law school dataset [53] This dataset consists of 20,649 examples aiming to predict students' undergraduate GPA based on their personal information and academic abilities. Given that GPA reflects individual educational outcomes and is protected under strict data-use agreements [53] we treat it as sensitive educational information requiring privacy protection.
Government salary dataset [2 This dataset originates from the 2018 American Community Survey conducted by the U.S. Census Bureau. It includes over 200,000 observations, with annual salary (USD) as the response variable. Annual salary represents typical personal financial information 26 therefore, treat it as sensitive data warranting privacy protection.
To facilitate analysis, we applied a logarithmic transformation for two datasets and then back- transformed the confidence sequence bounds after prediction. We apply proposed method:
8

---

0.8
T=5.5
0=3.3
Iime-nifrrn
003
0.3
10
30.
1'.00
24.00
3
3
1:300
2
10
4 30
r=0.25
T-0.5
p=0.9
baseline
significance level
0.8
0.5
0.3
043
003
0.3
10
20
3x
42.10
10.
10.30 2x
3xx 4
5xx 20
1:30 2x
4 307
1=0.25
1=0.5
significance
Figure 3: Time-uniform type error for AsypmCS constructed by (4 (on top panel) and 6 (on
bottom panel) and non-DP non asymptotic CS in (27], when confidential data come from standard Normal (0, 1) with r = 0.25, 0.5, 0.75, 0.9, and T = 0.3, 0.5, 0.8.
Confience sequence lengts
0.8
0125-
3.003
3.000
r=0.25
7-0.5
baseline
Confeience sequence length
0325
3.00
0=0.5
baseline
Figure 4: Average length for AsypmCS constructed by (4) (on top panel) and (6) (on bottom panel) and non-DP non asymptotic CS in 277, when confidential data come from standard Normal A(00 1) with 0.25, 0.5, 0.75,,7..0 0.9, and 0.3, 0.5, 0.8.
AsympCS based on equation and equation (6) to conduct privacy-preserving inference on the median (r = 0.5), targeting GPA in the first dataset and annual salary in the second. Specifically, construct time-uniform CS for the respective quantiles under truthful response rates 0.75 and 0.9, and set the hyperparameter in equation (6) to p 0.01, while keeping all other tuning parameters consistent with those used in Section The upper and lower bounds of the confidence sequences are presented in Figure 5 From the results in Figure we observe that the CSs produced by our two methods under different response rates r covering similar central values. addition, in both datasets, the length of the constructed CS decreases as increases. As grows, the sequence based on 4 becomes more conservative than that based on (6). These observations align with our simulation findings and further demonstrate the methods' adaptability.

---

3.5
3.4
3.3
10
20
10
20
T (x10F))
T (x103)
T ((x103)
54000
50000
48000
46000
44000
50
100
150
200
50
100
150
200
50
100
150
200
(xx102)
Txx10²)
(xx1DF)
Figure 5: Confidence sequence boundaries for GPA in the Law dataset (on top panel) and annual salary in the government salary dataset (on bottom panel). The pointwise confidence interval from Corollary | (red), and the proposed AsympCS based equation (4 (blue) and equation (6) (green), with target quantile = 0.5 and truthful response rates 0.9, 0.8, and 0.75 (left, middle, and right panels, respectively).
6 Concluding remark
this paper, we introduce an online, mmemmmrrrry algorithm that provides time-uniform, asymptotic confidence sequences for quantiles under LDP. We establish an almost-sure Gaussian approximation for the Polyak- Ruppert quantile estimator obtained via parallel SGD, which is non-trivial even in the non-DP case at rate (TT log log T) ( thereby sharpening the L2 and smooth-loss based results of (58] and [54]. In addition, we devise an almost-surely consistent estimator of the quantile variance (and density) using only the SGD iterates, thus providing the first sequential
quantile-inference inference procedure in the LDP setting.
Nonetheless, our methodology has tuning parameters, such as the learning rate and the initial values, whose optimal calibration can be delicate. Second, the rate of variance consistency hinges on the number of parallel chains, K. and the dynamically sicreasing-chann scheme requires relatively sharp assumptions on the relationship between and T' fixed-k variant could leverage t-distribution with (N 1) degrees of freedom to form confidence sequences, but deriving mmntotittooiic t- t-based bounds is far from straightforward Finally, although -on-asymptotic error bounds for SGD estimators have been extensively studied (e.g..19), extending these results to obtain fully non non-asympootic confidence sequences for SGD iterates under LDP remains an attractive yet challenging avenue for future research.
limitations. First, the SGD-based procedure depends
7
Acknowledgments
The authors sincerely thank the anonymous reviewers, AC, and PCs for their valuable suggestions that have greatly improved the quality of our work. This work was supported by the Shanghai Engineering Research Center of Finance Intelligence (Grant No, 19DZ2256600,,, Leheng Cai would thank to the funding supported by China Association for Science and Technology and National Natural Science Foundation of China (No. 12171269). Shuyuan Wu's research is partially supported by National Natural Science Foundation of China (No. 12401392) and China Postdoctoral Science Foundation (No. 2024M751929, No. 0024T1705400
10

---

References
Anders Aamand, Fabrizio Boninsegna, Abigail Gentle, Jacob Imola, and Rasmus Pagh. Lightweight protocols for distributed private quantile estimation. arXiv preprint arXiv:2502. 02990. 2025.
[2] Daniel Alabi, Omri Ben-Ellizer, and Anamay Chaturvedi. Bounded space differentially private quantiles. arXiv preprint (:XXi:2201103330 2022.
[3] S Abhishek Anand, Chen Wang, Jian Liu, Nitesh Saxena, and Yingying Chen. Spearphone: A speech privacy exploit via seglerommter-senseee reverberations from smartphone loudspeakers. arXiv preprint arXiv: / 1977,0597, 2019.
[4] Luca Barbaglia, Sergio Consoli, and Sebastiano Manzan. Forecasting with economic news. Journal of Business & Economic Statistics, 41(3):708 779, 2023.
[5] Omri Ben-Eliezer, Mikulincer. and Ilias Zadik. Archimedes meets privacy; On privately estimating quantiles in high dimensions under minimal assumptions. arXiv preprint arXiv:2208. 07443, 2022.
[6] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, (0(2)223-3111 2018.
[7] Leheng Cai, Qirui Hu, and Shuyuan Wu. Federated learning of quantile inference under local differential privacy. arXiv preprint arXiv 2509. 2025.
[8] T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825 2850, 2021.
[9] Likai Chen, Georg Keilbar, and Wei Biao Wu. Recursive quantile estimation: Non-asymptotic confidence bounds. Journal of Machine Learning Research, 24(91): 2023.
[10] Song Xi Chen, Nonparametric estimation of expected shortfall. Journal of financial econometrics, 601):87-177, 2008.
[11] Victor Chernozhukoy and Iván Fernández- Val. Inference for extremal conditional quantile models, with an application to market and birthweight risks. The Review of Economic Studies, 78(2):559-589, 2011.
[12] Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. Distributed differential privacy via shuffling. In Advances Crypology-ERROCRYPY 2019; 38th Annual International Con- ference on Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part 1 38, pages 375-403. Springer, 2019.
[13] Jeremy Cohen, Simran Kaur, Yuanzhi Li, Zico Kolter, and Ameet Talwalkar, Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representutions. 2021.
[14] Miklos Csörgo and Pál Révész. Strong approximations in probability and statistics. Academic press, 1981.
[15] David Deuber. Jinzhou Li. Sebastian Engelke, and Marloes H Maathuis. Estimation and inference of extremal quantile treatment effects for heavy-tailed distributions. Journal of the American Statistical Association, 119(547):226-22216 2024.
[16] Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step-sizes. 2016.
[17] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. Advances in Neural Information Processing Systems, 30, 2017.
[18] Dana Draghicoseu, Serge Guillas, and Wei Biao Wu. Quantile curve estimation and visualization for nonstationary time series. Journal of Computational and Graphical Statistics, 18(1):1-20 2009.
[19] John Duchi, Elad Hazan, Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
[20] John C Duchi, Michael Jordan, and Martin Wainwright. Local privacy and statistical minimax rates. In
2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 029-438. IEEE, 2013,
[21] Cynthia Dwork. Differential privacy in new settings. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 774. SIAM, 2010.

---

[22] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry. Ilya Mironov, and Moni Naor. Our data. ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486-503. Springer, 2006.
[23] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. Proceedings of the forty-first annual ACM symposium on Theory of compuring, pages 371-380, 2009.
[24] Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067, 2014.
[25] Sébastien Gadat and Fabien Panloup. Optimal non-asymptotic analysis of the ruppert- polyak averaging stochastic algorithm. Stochastic Processes and their Applications, 156:312-344 2023.
[26] Jennifer Gillenwater. Matthew Joseph, and Alex Kulesza. Differentially private quantiles. In Marina Meila and Tong Zhang. editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 3713-3722. PMLR, 18-24 Jul 2021.
[27] Steven R Howard and Aaditya Ramdas. Sequential estimation of quantiles with applications to a/b testing and best-arm identification. Bermoulli, 1843)117 2022.
[28] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasject Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2): (2)):0555 1050- 2021.
[29] Jiaqiao Hu, Yijie Peng, Gongbo Zhang, and Qi Zhang. A stochastic approximation method for simulation- based quantile optimization. INFORMS Journal on Computing, 34(6) -9009, 2022.
[30] Jingyu Hua, Zhenyu Shen, and Sheng Zhong. We can track you you take the metro: Tracking metro riders using accelerometers on smartphones. IEEE Transactions on Information Forensics and Security, 12(2):286-29) 2016.
[31] Qi Huang, Hanze Zhang, Jiaqing Chen, and MJJBB He. Quantile regression models and their applications: A review. Journal of Biometrics & Biostatistics, 8(3):166, 2017.
[32] Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. The role of interactivity in local differential privacy. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 94 14-105, 2019.
[33] Nathan Kallus, Xiaojie Mao, and Masatoshi Uchara. Localized debiased machine learning: Efficient inference on quantile treatment effects and beyond. Journal of Machine Learning Research, 15(16):1-59 2024.
[34] In Lee. An analysis of data breaches in the healthcare industry: diversity, trends, and risk profiling. Information Security Journal: A Glohal Perspective, 3163)3346-358, 2022.
[35] Sokbae Lee, Yuan Liao, Myung Hwan Sen, and Youngki Shin. Fast and robust online inference with stochas- tic gradient descent via random scaling. Proceedings of the AAAI Conference on Artificial Intelligence, (((7):331-7388) June 2022.
[36] Jing Lei. Differentially private m m-estimators. Advances in Neural Information Processing Systems, 24, 2011.
[37] Jianwei Liu, Xiang Zou. Leqi Zhao, Yusheng Tao. Sideng Hu, Jinsong Han, and Kui Ren. Privacy leakage in wireless charging. IEEE Transactions on Dependable and Secure Computing, 2022.
[38] Yi Liu, Qirui Hu, Lei Ding, and Linglong Kong. Online local differential private quantile inference via self-normalization. In International Conference on Machine Learning, pages 21698-21714, PMLR, 2023.
[39] Yi Liu, Qirui Hu, and Linglong Kong. Tuning-free estimation and inference of cumulative distribution function under local differential privacy. In Proceedings of the 41 International Conference on Machine Learning, pages 31147-31164, 2024.
[40] Tudor Manole and Aaditya Ramdas. Martingale methods for sequential estimation of convex functionals and divergences. IEEE Transactions on Information Theory, (9(7)4441-4655 2023.
[41] Arvind Narayanan and Vitaly Shmatikov. How to break anonymity of the Netflix prize dataset. arXiv preprint cs/0610105, 2006.
12

---

[42] Drago Plečko, Nicolas Bennetl, and Nicolai Meinshausen. fairadapt: Causal reasoning for fair data preprocessing, Journal Statistical Software, 110:1-35, 2024.
[43] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal control and optimization, 30(4):838 855888888858,,88 1992.
[44] Herbert Robbins, Statistical methods related to the law of the iterated logarithm. The Annals of Mathemati- cal Statistics, 41(5):1377-1409, 1970.
[45] Herbert Robbins and David Siegmund. Boundary crossing prohabilities for the wiener process and sample sums. The Annals Mathematical Statistics, pages 1410-1429, 1970.
[46] Robert J Serfling. Approximation theorems of mathematical statistics. John Wiley & Sons, 2009.
[47] Xiaofeng Shao. Self-noraalization for time series: review of recent developments. Journal of the American Statistical Association, 1105112)1797-1817 2015.
[48] Adam Smith. Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the forty-third annual ACM symposium Theory of computing, pages 813-822, 2011.
[49] llya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference machine learning, pages 1139 1147, pmir, 2013.
[50] Jay Tenenbaum, Haim Kaplan, Yishay Mansour, and Uri Stemmer. Concurrent shuffic differential privacy under continual observation. In International Conference on Machine Learning, pages 33961-33982. PMLR, 2023.
[51] Huixia Judy Wang, Deyuan Li, and Xuming He. Estimation of high conditional quamtiles for heavy-tailed distributions. Journal of the American Statistical Association, 107(500):1455) 1453-1464, 2012.
[52] lan Soudby--mmihh David Arbour, Ritwik Sinha, Edward H Kennedy, and Aaditya Ramdas. Time-uniform central limit theory and asymptotic confidence sequences. The Annals of Statisticx, 52(6):611322400, 2024.
[53] Linda Wightman. Isac national longitudinal bar passage study. Isac research report series. 1998.
[54] Chuhan Xie, Kaicheng Jin, Jiadong Liang, and Zhihua Zhang. Asymptotic time-uniform inference for parameters averaged stochastic approximation. arXiv preprint arXiv:2410. 1500. 2024.
[55] Dandan Xu, Michael Daniels, and Almut G Winterstein. bayesian nonparametric approach causal inference on quantiles. Biometrics, 74(3):986 996, 2018
[56] Steve Yadlowsky, Scott Fleming, Nigam Shah, Emma Brunskill, and Stefan Wager. Evaluating treatment prioritization rules via reightei average treatment effects. Journal of the American Statistical Association, 120(549):38551, 2025.
[57] Li Zhang, Parth H Pathak, Muchen Wu, Yixin Zhao, and Prasant Mohapatra. Accelword: Energy efficient hotword detection through accelerometer. In Proceedings the 13th Annual International Conference on Mobile Systems, Applications, and Services, pages 301-315, 2015.
[58] Wanrong Zhu, Zhipeng Lou, Ziyang Wei, and Wei Biao Wu. High confidence level inference is almost free using parallel stochastic optimization. arXiv preprint arXiv:2401.0934. 2024.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have accurately summarized the paper's contributions and scope in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed the limitations in Conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
14

---

Justification:
We have provided detailed theoretical assumptions and corresponding com- ments in Section and complete proofs in the Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We have described the experimental setting in Section 4 in detail.
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
15

---

Answer: [Yes]
We have uploaded the code that reproduces the experimental results in the paper.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm ec/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips. //nips.cc/ppl wwwppbblccgguiicuceccccccooooopp wttpggudddee/eeebeiiinnneeee htt.SSbbbiiiiooooiiiii.oooi for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have established these details in Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
This information has been defined correctly in Section 4.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
16

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have reported the computer resources in Section 4,
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics httppp////.errre....o/////////aa
Answer: [Yes]
Justification:
We have checked that our paper satisfies the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss our contributions and potential future directions in the last section. No apparent negative societal impacts are foreseen.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper doesn't 't involve this.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: No existing assets used.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification:
We only use the LLM for writing and editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neur/i: http://///////oofeeeeee///////// for what should or should not be described.
20

---

A Additional simulation results
A.1 Other results in Section
In this section, we provide additional figures not shown in the main text (see Figures A. Notably, the left panel of Figure A.I] the time-uniform type error slightly exceeds the nominal level of 0.05 (approximately 0.08), with most errors occurring during the start of the algorithm. This primarily occurs because the initial values (A(0, 1)) are relatively far from the true values, resulting in poor estimation at the initial moments. Additionally, although (4) is generally more conservative than (6) during the early stage, calculations indicate that the boundary given by 4 narrower at the very beginning of the algorithm, causing slightly poorer coverage during these initial moments. Increasing the burn-in period could further reduce this error rate.
0.5
0
Time- unlo-umiomm type-1 error
r=0.25
rm0.5
0m0.75
r=0.9
significance level (or 0.05)
Figure A.I: Time-uniform type I error for AsypmCS constructed by and non-DP non asymptotic CS in (27]. when confidential data come from standard Cauchy C(O, 1) with r = 0.25, 0.5, 0.75, 1 and 0.3, 0.5, 0.8.
0.8
0.5
0.3
Time-unfom type-1 error
0.03
0.69
0.1
0=0.25
F-0.5
050.
r=0.9
r-1
significance level (a 0.05)
Figure A.2: Time-uniform type I error for AsypmCS constructed by (6) and non-DP asymptotic CS in 27). when confidential data come from standard Cauchy C(O, with r 0.25, 0.5, 0.75, 0.9, and 0.3, 0.5, 0.8.
Contidence sequence length
T 0.6
T= 0.5
T= 0.3
0.26
0.20
0.15
0.05
3.00
0.255
0=0.5
050.
r=0.9
baseline
Figure A.3: Average length for AsypmCS constructed by 4 and non-DP non asymptotic CS in 27 when confidential data come from standard Cauchy C(O, with r = 0.25, 0.5, 0.75, 0.9, 1 and 0.3, 0.8.
Next, we evaluate the finite-sample performance under a mixture of Beta distributions and make some discussions about our Assumptions. To be specific, for our Assumption (A1), according to
21

---

Confidence sequence lengen
T- 0.8
0.5
T-0.3
0.2
9.20
9:35
0.00
2x
1x300
rw0.25
baseline
Figure A.4: Average length for AsypmCS constructed by 6 and non-DP non asymptotic CS in 27 when confidential data come from standard Cauchy C(O, with = 0.25, 0.5, 0.75, 0.9, 1 and 0.3, 0.5, 0.8.
0.8
80%
60%
20%
T=5
100%
60%
RAE
40%
0%
T=0.3
100%
80%
60%
20%
0%
20
100
values
0.0.5
05
r=0.75
r.0.9
Figure A.S: Relative error of the variance estimator when confidential data come from standard 0.3, 0.5, 0.8.
Normal (o0, 1) with 0.25, 0.5, 0.75, 0.9, and
Corollary 2.3.3.A
[4] the asymptotic normality of the sample quantile relies on the assumption that the distribution function F--) is differentiable at the true quantile value x²,, with strictly positive derivative. While it's not strictly necessary that density function f(-) equals the derivative of the distribution function, f(.) = F-)., this relationship holds if the density f(-) is continuous at x², in which case F' F'(x*) f(x") > In addition, Assumption (A2) is technical requirement crucial for controlling a negligible term in the Gaussian approximation, where second-order Taylor expansion applied (refer equation 7.). This a mild assumption that holds for many common distributions, including heavy-tailed ones. For example, the derivative of the density function for a standard Cauchy random variable is:
2r
f(x)= =-
dæ f(x))= dr +(]+2²)) T(1 + 22)2
This derivative is both continuous and bounded, thereby satisfying Assumption (A2).
While Assumptions (A1) and (A2) hold for wide range of distributions, our theoretical results require the underlying density to have continuous and bounded derivatives. This condition is not met by all irregular "spiky" distributions. To investigate method's practical performance under
22

---

T 0.8
100%
60%
40%
0%
T=
80%
RAE
40%
20%
T
100%
60%
40%
0%
20
100
values
0022
F0.5
00.75
-09
Figure A.6: Relative error of the variance estimator when confidential data come from standard
Cauchy C(O, 1) with r 0.25, 0.5, 0.75, 0.9, and 0.3, 0.5,
145
1.43
141
142
141
139
1.39
1.39
137
1.37
1.7
135
1.33
1.3
1x100
1xi
5x10
2x Sw10 5x10
Figure A.7: Plots of trajectories when confidential data from standard Cauchy distribution C(O, 1), for pointwise confidence interval from Corollary
| (in red with upward-pointing triangles), pointwise confidence interval from (38 (in purple with asterisks), proposed AsympCS based (4) (in blue with circles) and (6) (in green with squares) with 7 0.8, r 1, 0.9, 0.75 (left, middle and right panel).
these challenging conditions, conducted further experiments. To be specific, test method using a mixture of Beta distributions with the following density:
f(x) 1010) + 8100, (2) + (100.10 /3.
where (2))(2) the density of Beta distribution with parameters a and 3.. This specific mixture creates sharp spike at 0.5, resulting in a large derivative of the density at that point, which slightly violates Assumption (A2). Despite this, our numerical simulations under r 0.75 and 0.5 confirm that our method remains valid. The results shown in Figure A.8
23

---

across various settings of and т, indicating higher = 0.5
0.06
0.05
Time- -nino-uiform type-1 error
0.04
0.03
0.02
0.01
0.00
106
2 10
10
10c
5 10"
method=ub
method=gm
significance level (a 0.05)
Time-uniform type error for AsypmCS constructed by by (4 and (6. when confidential Figure A.8:
data come from a mixture of Beta distributions with r = 0.5 and r 0.75.
A.2 Comparison between the proposed method and (38
We conduct additional experiments compare proposed quantile estimation and confidence interval in Corollary with (38). Recall that (38) adopts a pointwise estimation approach and employs self-normalization for inference. Specifically,
considered the same simulation setting in Section 4, with total sample size T = 5, 000, 000, quantile level r = 0.3, 0.5, 0.8, the truthful response rates 0.25, 0.5, 0.75, 0.9, and distribution type to normal. The results are in figure A.9] While both methods achieve empirical coverage rates close to the nominal confidence level, the average length of our confidence interval is more efficiency of our approach.
For point estimation accuracy of quantiles, we use the same simulation settings as in the confidence- interval study and evaluate performance by the mean squared error (MSE) of the estimated quantiles. The detailed comparison results are provided in fig A.10 We find that when is close to 0.5, our method achieves comparable MSE to that in (38]. However, as 7 deviates from 0.5, the MSE of our method becomes slightly worse. This can be attributed to the dynamically chained parallel procedure used procedure employed our quantile inference.
24

---

T 0.8
0.5
0.3
Average length
0.05
0.04
0.03
0.00
0.06
Average length
0.05
0.02
0.01
0.00
1x
10
2
10
10
4 10t X 10"
1 10
10 3x 10
x 10
10
1 10 x
x 10 10 5x10
Figure A.9: Average length onstructed by the proposed method in Corollary (on top panel) and 38 (on bottom panel), when confidential data come from standard Normal N N 1) with T 0.3, 0.5, 0.8 and 0.25, 0.5, 0.75, 0.9,
0.8
= 0.5
0.3
0.00025
0.00020
MSE
0.00010
0.00005
0.00000
10"
x0
0.00025
0.00020
0.00015
0.00005
0.00000
2x
10 x 10
10"5 10
1 10 10 4 10
1x 20 10 10 10'5
Figure A.10: MSE constructed by the proposed method in Corollary (on top panel) and 38 (on bottom panel), when confidential data come from standard Normal (00 1) with - = 0.3. 0.5, 0.8 and 0.25, 0.5, 0.75, 0.9,
25

---

A.3 The selection and sensitivity analysis of tuning parameters
The proposed method requires the selection of several tuning parameters. This subsection conducts comprehensive sensitivity analyses to show that the results are robust to variations in these choices.
Note that tuning parameters fall into three categories. The first includes SGD-based parameters (e.g., the learning rate-related parameter a). Selecting the learning rate is indeed a well-known challenge in practice: SGD can be sensitive this choice, especially in high-dimensional sparse settings and rare-frequent or heavy-tailed regimes; see [6 [3] 19 Nevertheless, under appropriate conditions, for example, when the objective convex and smooth, when the initialization is sufficiently close to the true parameter, Polyak-Ruppert averaged SGD enjoys provable convergence 16 As later reported in our sensitivity studies, our results are robust to reasonable variations in this hyperparameter. The second category includes tuning parameters related to time-unifrm inference, such as the AsympCS starting index m and the hyperparameter p in the Gaussian mixture bound (equation ( The third category consists of tuning parameters specific to our proposed method, such as the number of chains htt). We find that the results are not sensitive to these parameters; thus, recommendations from the time-uniform inference literature [54] and the default setting provided in our paper (e.g., h(t) log (t) can serve as practical choices.
with tolerable sensitivity to the learning 4 49
We next conduct comprehensive sensitivity analyses for the aforementioned tuning parameters (i.e., a, and (.)... Specifically, we consider one of the simulation settings from Section 4, with total sample size of T 5,000,000, 1, 000 repetitions, truthful response rate r 0.75, quantile level time-uniform = 0.5, and normally distributed data. We evaluate the time- uniform type error for AsympCS
the following Figures A.1I to A.14 The proposed methods maintain the nominal type eтrоr rate (5%) for nearly all hyperparameter choices, demonstrating insensitivity these tuning parameters.
across range of hyperparameter choices. The results are summarized
0.06
0.05
Time-un un--uunlfmm
0.02
v.5auue-0.55 30valuc-0.6 v.value-0.7
a_vvluee0.65 0.65
significance level 0.05)
Figure A.11: Time-uniform type I error for AsypmCS constructed by (4) (on left panel) and (6) (on right panel), when confidential data come from standard Normal (0, with a = 0.55, 0.6, 0.65, 0.7.
26

---

T= 0.5
lime-unifomn type-1 error
0.03
0.02
0.1
0.00
1x
2x
3x
4x
5x
1x
2x
3x
4x 10"
5x
h(t) = Glog1o (t)
h(t) = Blog1o (f)
h(t) = 10logio (8)
h(t) = (1)
h(c) 9log1a (t)
significance level (a 0.05)
Time-uniform type I error for AsypmCS constructed by (4) (on left panel) and (6) (on right panel), when confidential data come from standard Normal (0, with h(t) foogo (t), (t), log10 (t), 9 log 10 10 (t).
Figure A.12:
T= 0.5
Time-uniform type-1 error
0.04
0.03
0.02
0.01
0.00
10
10
10
m=1
m= 1=100000
significance level (a 0.05)
m=10000
5=500000
Figure A.13: Time-uniform type I error for AsypmCS constructed by 4 when confidential data
come from standard Normal N 1) with 10000, 100000, 500000.
27

---

0.5
0.06
0.35
Time-unifort type-1 error
0.34
0.33
1 10"
x 10
3 10
x 10
x 10
000.50
p=0.002
significance level 0.05)
000001
0=0.005
Figure A.14:
Time-uniform type I error for AsypmCS constructed by 66. when confidential data
come from standard Normal (o, 1) with 0.0005, 0.001, 0.002, 0.005.
28

---

B Proofs
This section includes detailed proofs of the theoretical results in the main article. Elementary calculation shows that
g(x) = RG () = r (F(x) F(t"))
which will be frequently used in our proofs.
Proofs of Theorem
1 Define the weight wk = TT One rewrites
6 Tk
K
Ts 1
Th
DRJ
[Rk x²)
wk Tk. h=1
T
Tk
k=1j=1
k=1
j=1
There are two possible cases for the value of Ty: either Ta E (T/R -1,T/m N 1) for all 1 < k <
(case 1), or Ti = T2 = Tno 2 Tro+1 =...= Tx-1 2 Tx and [Tno Txo+1l I 1, Th x T/KK
for any 1 < k S 1 (case 2). Define
Sktt g( - G(F,,e-1;CA Exst = g00x))>>>>>>>)))))>>>)) - G(x", C..)).
Elementary calculation shows that
B(E (F.,-1) = 1 (FFF(1)()))
2r 1 r 2 (FF,(1))-1)) 2
2
2
1 - (222((3),011) - 1)²
4
1 (² - 1)²
4
where the convergence in probability holds by the consistency of the quantile estimation and the continuous mapping theorem. Denote "kkt = FK - x², H = rf(x") B, = 1 - -,,H, A² =
Exn
IIi B.) m for any j S L. We decompose that
Ta
Tp Th.j
Tk = T /=1
(Fkj x²)= =
Tk
j=1
Th-1
T
1 - BOTK.O +
T
Tx-1ppp
1 TkJ
Th-1 - 11 ENJ+1
Tx
Tx
TB 1=
)
1=0
1 Tx-1
1 Tx Tx-1
Σ
H-! (EKJ+1 - Enj+1) +
Σ
H -
Ek,++
Tk
Tk ==0
=: Tx,1 + Tx.2 + Th.3 + TTAA + Tk.51
which
Kk.j H( x²) - gg(kk))
For 1x.1: : According to Lemma C.4 of [4]. one has |Ab-1| < Co uniformly for all 2 1. Further observe that 7k.0 20 x for all S S K. thus one obtains
Σ
wk T Tx.1 = 0 (KTT!).
For Te.2: Theorem 5 of 25 shows that
max E [ak,
x²12 S m/-
ISkSN
29

---

Since | 2 [k,t x=12 by Assumption (A2), we show that
E walr 1 1- log (1)
k=1 wxB E
Th.t 1= 11-a llg It (1)
max SAS E Iri.t x=1
11-a log ((())
1 flog (t(t) oc.
Hence, with probability one,
20
Σ ki wa|rk,rl o0.
log (t)
According to the uniform boundedness of 1A for case 1, one shows that
K
Tx
Wk WKTRR Tk.2
Wk Tk
lnkil
j=ū
[T/K+1J-1 Σ
[T/K + 1]
Wi
|rajl
[T/K [T/x+11
f=0
Oa.. ((K/TT) ( log (og)+((T))
For case 2, one shows that
T4
Wk Tx
Wk Ts
1=0
Tk-
T
1
Inaal
Wk
Inkul
+
Inxel
Tk
T
k=1
1=0
k=
f=0
j=0
Oa.s. ((x/T)² log + (T))
For Tk.3t For any fixed p 0 (large enough), note that maxigAg BlEk,j 22 = 1 is bounded.
Following the arguments in [54 one has 173. O (1==+a/2) Then, using the Lemma A in Chapter 9.2.6 of (66 and the independence over k; one has that
= (o (1(K/((/
wk
Tx.3
Am
2p
which implies that
-1t//2/1///// log log ((T))
Wh T2.3 = =Oas.
For Te.4: Observe that Ek.j - ERj- = g(( G( + G(x*, Ck.s), and
[(ENJ - =k,,) < (xx(#x)-11) + E (G( (G(zz,--1 G(x", ((.5))
$ Blak.j-1 112 + E .R.j x"1
Ba x (E x²] 1/2 z 11:-
1/2
where the last inequality holds by Theorem 5 of (25] and the constant does not depend on k.
30

---

We rewrite
tr 1
Th.4
H (St, En,e)
T lT
k=1
t= k=1
where tr maxisA<k Tk x T/k and K₁ = life : T& 2 tl| S K. Notice that
Var
H (Ex, Ek,e) S Var - Ex,e) S km) 1/2
Hence,
0C
Σ H (Ex.1 Ek,1)
00
Var
log (t) 0o,
x2/22//2--//4 log 1/2t
which implies that (by Kronecker's lemma),
w/ Tr.4 = Oo.s.
(TTx/ a/4 /l///loo////// 1/2+e (ogg1/+((TT)) (T)
For Tk,s: Elementary calculation shows that
EE 1 - p2r 112 S.
4
Applying Theorem 2.6.7 of [1 with ((x) 2D
and In 8,, there exist i..d. standard normal
Za and some a, > 0 (depending on the distribution H -- such that
k T
H H
T
Σ
2. > To) s Ca 2p711208.
SH
A=1
Thus.
P
Tx
H Ekg
1
Zi
> 1490
ST
VH-ISH-1
T
k=
1=1
For > 2, one selects Sa E 1/2), the Borel-Cantelli lemma leads to
T
wk T
Σ Z, = O... (1-1+)))).
T i=1
where Zi's are i.i.d. normal rv''s with mean zero and covariance SHH! Therefore, obtain that
1
T
(V
log log T
(
x²)
Zg
= Oa.s.
T Am
T
T
im
which completes the proof.
Proofs of Theorem 2 Recall that the weight W/ = -'k/T. We rewrite
2
Wk
Tkk
x²)
Wk
x²)
VTR
kk
y=1
Recall the definitions of Tk.j. 5
For Tx, : According to Lemma C.4 of [54], one has | S Co uniformly for all 2 1. Further observe that 7 = 2ig - for S K, thus one obtains ||Tx,1l22 O (T where the
constant does not depend on k.
31

---

For Tk.2: Consider that
7 -1
T
7
A
[k.
x Tk
[k.s
~ Tk
[k - x²12.
Tk
j=0
1=0
Then,
Tx-1
T
A7
Tk.
- Tk
|| [kkj - x" 2²112
j=0
3=0
Applying Theorem of [25]. have
max E
x²1² 2 nz.
Since f7 =j with a > 1/2, it follows that TT = o (T
For TR.3: As shown in the proof of Theorem | one has || = O (Tr (To - -0 -OTT
since a < 1.
For TR.4: Observe that Σ/= H (Eky - Eks)) is a martingale for each &s (independent over 1 -
S k), Burkholder's inequality entails that
1/2
Th H 1 (EN.) - =ke))
Th -1
H
(ENr - -EmJ)1
1=1
1/2
Tk
Σ
1/2
S $TZ 1/1//1221/22
1/j
/=l
Hence, for any 1 k S n,
=0 =O(Tz112-00)
TTT. = Tk
H (ERU - EkJ)
1
For Tk.s: Applying Theorem 2.6.7 of 14 with H(x) 222 and H, un there exist i.i.d. standard normal Zu.j' 's and some age C (depending on the distribution of Ekg)) such that
H Ek.j
Th
P
Σ
ZRj
vTT
< Ckap 2p -20T1 22071-2290
H
SH-1
Thus,
1 Th
H - و
Ts
P
ZR.s
S v -o-p-aa- 2030 > vI 1+80
Tk
H-HH
Tk
j=1
j=1
Since EXP = 10 pup-1p((Xi
v) vidu, we also have
1 Tv
Tk.5
Z
00
-0
Tk
j=1
According to the above results, we show that
1 Th
T
1
(I 1/3
(IX.. x²)
Z
=
Tk
1
j=1
32

---

which implies
T
Σ
x²)
Zon
+o(1) < 00,
j=1
2
j=1
E
Zk.j + o(1) o1))
VTK
The SLLN (independent but not identically distributed) further yields that
Ts (kkj - x²) 9.6.,
k=
sufficed to show
2
Th
1- r²(2T 1)? 4r2 ()²
Σ
Wk
Ik.j - x²)
EZ
T
km
jml
For case 1, Ti
T2
TRo
Tko
Tx + 1. The SLLN (i.i..)) implies that
6g Σ
1
[Th.
x²)
0.3.
Th
Σ
T3 (2 11
1)²
TTk
T
T
4r
(x=")
k=1
k=1
k=1
2
Th [RR
T T
T3 (2 1)? T f2(")(x²)
Wk
V
x²)
E
kgj
Σ
Am
j=1
k=
k=
+1
The result is obtained by adding the above two expressions. For case 2, the SLLN (i..d.) entails that
Tp (aku
Wk
x²))
Wk
R.Z
k:
k=1
2
R
Tk [bb. - x²)
Tx T
Wk
EZE
a... O,
VTI
j=1
As o()). it completes the proof of the consistency of 0?.
Proofs of Theorem 3 According to the law of iterated logarithm, the rate of the bound of any confidence sequence for the unknown mean of Gaussian random variables with unit variance is at least TT log T. On the one hand, Theorem shows that Conditions G-1 and G-3 in [52] are satisfied. On the other hand, Theorem 2 ensures Condition G-4 in [2] Hence, we apply Theorem 2.4 [52 to complete the proof.
33


Reviews:
[{"review_id": "gAakhk3Beu", "reviewer": "Reviewer_By34", "summary": "The paper studies the construction of asymptotic confidence sequence for the quantile of a distribution on the line under local differential privacy; where an $\\epsilon,\\delta$-differential privacy constraint applies to each individual datum in the sequence of observations. \n\nThe method is based on parallel private SGD, where the privacy mechanism is essentially randomized response and where the estimation of the quantile and its variance is done using the SGD iterates, where the parallel chains need to be constructed in a clever way\". The authors provide both theoretical guarantees for their method as well as simulations.", "questions": "* What if the user is interested in more than just one quantile, but say more general tail risk? Can the method be adapted to these types of questions?\n* What can be said about the method in terms of the efficiency theory (Steinberger 2024 - Efficiency in local differential privacy)?", "limitations": "The main limitation I see are the hyperparameters of the method and setting these under differential privacy constraints in practice.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n* I found the paper to be well organized and easy to read.\n* The theoretical contributions are interesting independently of the motivation and are formulated as such.\n* The method is well well explained - both in terms of its how and why.\n* The writing is clear and the authors are forward in terms of what the do and don't assume.\n\nWeakness:\n* The method seems to rely on tuning parameters which are difficult to set in practice. Furthermore, it is unclear to me whether these tuning parameters can be set in a way that does not lead to \"privacy leakage\" due to having to run the method for different hyperparameter values. \n\nA minor comment: sometimes there is some unnecessary notation overflow: On page 3, $U$ is used twice for completely different purposes. Similarly, the choice of the $\\delta_{T,i}$-notation is somewhat unfortunate given the differential privacy definition.", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the time and effort you've invested in reviewing our paper. Your feedback is invaluable to us, and we have addressed each of your concerns below. Should you have any further questions, please do not hesitate to ask.\n\n\n**For weakness:**  \n\nOur tuning parameters fall into three categories. \n\nThe first includes SGD-based parameters (e.g., the learning rate-related parameter $a$). Selecting the learning rate is indeed a well-known challenge in practice: SGD can be sensitive to this choice, especially in high-dimensional sparse settings and in rare–frequent or heavy-tailed regimes; see [1,2,3].\nWe will reiterate this limitation in the revised manuscript and plan to investigate additional techniques for reducing our method's sensitivity to SGD-based parameters in future work. Nevertheless, under appropriate conditions, for example, when the objective is convex and smooth, or when the initialization is sufficiently close to the true parameter, Polyak–Ruppert averaged SGD enjoys provable convergence with tolerable sensitivity to the learning rate [4,5,6]. As later reported in our sensitivity studies, our results are robust to reasonable variations in this hyperparameter.\n\nThe second category includes tuning parameters related to time-uniform inference, such as the AsympCS starting index $m$ and the hyperparameter $\\rho$ in the Gaussian mixture bound (equation (6)). \n\nThe third category consists of tuning parameters specific to our proposed method, such as the number of chains $h(t)$. We find that the results are not sensitive to these parameters; thus, recommendations from the time-uniform inference literature [7]  and the default setting provided in our paper (e.g., $h(t) = \\lfloor 8 \\log_{10}(t) \\rfloor$) can serve as practical choices. \n\nTherefore,  we use a single, fixed set of tuning parameters in all our experiments, thereby avoiding scenarios in which multiple hyperparameter evaluations might inadvertently compromise privacy.\n\nFurthermore, according to your valuable comment, we have now conducted comprehensive sensitivity analyses for the aforementioned tuning parameters (i.e., $a$, $m$, $\\rho$, and $h(t)$). Specifically, we consider one of the simulation settings from Section 4, with a total sample size of $T = 5{,}000{,}000$, $1000$ repetitions, truthful response rate $r = 0.75$, quantile level $\\tau = 0.5$, and normally distributed data. We evaluate the time-uniform type I error for AsympCS across a range of hyperparameter choices. The results are summarized in the following Tables. We are pleased to report that, the proposed methods maintain the nominal type I error rate (5\\%) for nearly all hyperparameter choices, demonstrating its insensitivity to these tuning parameters.\n\n**Sensitivity analysis for $a$**: (t $\\times 10^4$)\n| $a$ | method | t = 5 | t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|-----------|---------------|---------------|---------------|---------------|---------------|\n| 0.55 | UB | 0.003 | 0.005 | 0.005 | 0.005 | 0.005 | 0.005 |\n| 0.6 | UB | 0.002 | 0.003 | 0.003 | 0.003 | 0.003 | 0.004 |\n| 0.65 | UB | 0.002 | 0.003 | 0.004 | 0.004 | 0.004 | 0.004 |\n| 0.7 | UB | 0.002 | 0.002 | 0.002 | 0.002 | 0.002 | 0.002 |\n| 0.55 | GM | 0 | 0.002 | 0.005 | 0.01 | 0.012 | 0.014 |\n| 0.6 | GM | 0 | 0.001 | 0.002 | 0.004 | 0.009 | 0.012 |\n| 0.65 | GM | 0 | 0.002 | 0.007 | 0.01 | 0.012 | 0.014 |\n| 0.7 | GM | 0 | 0.001 | 0.002 | 0.003 | 0.007 | 0.009 |\n\n\n**Sensitivity analysis for $h(t)$** (t $\\times 10^4$)\n| $h(t)$ | method | t = 5 | t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|-----------|---------------|---------------|---------------|---------------|---------------|\n| $6\\log_{10}(t/5)$ | UB | 0.01| 0.016 | 0.017 | 0.018 | 0.019 | 0.02 |\n| $7\\log_{10}(t/5)$ | UB | 0.006 | 0.008 | 0.01 | 0.011 | 0.011 | 0.011 |\n| $8\\log_{10}(t/5)$ | UB | 0.002 | 0.003 | 0.003 | 0.003 | 0.003 | 0.004 |\n| $9\\log_{10}(t/5)$ | UB | 0.003 | 0.003 | 0.003 | 0.003 | 0.003 | 0.003 |\n| $10\\log_{10}(t/5)$ | UB | 0 | 0 | 0 | 0 | 0 | 0 |\n| $6\\log_{10}(t/5)$ | GM | 0 | 0.006 | 0.025 | 0.043 | 0.054 | 0.065 |\n| $7\\log_{10}(t/5)$ | GM | 0 | 0.001 | 0.012 | 0.021 | 0.027 | 0.031 |\n| $8\\log_{10}(t/5)$ | GM | 0 | 0.001 | 0.002 | 0.004 | 0.009 | 0.012 |\n| $9\\log_{10}(t/5)$ | GM | 0 | 0.001 | 0.004 | 0.006 | 0.007 | 0.01 |\n| $10\\log_{10}(t/5)$ | GM | 0 | 0 | 0.001 | 0.002 | 0.004 | 0.004 |\n\n\n**Sensitivity analysis for $m$** (t $\\times 10^4$)\n| $m$ | method |t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|---------------|---------------|---------------|---------------|---------------|\n| 1 | UB | 0.003 | 0.003 | 0.003 | 0.003 | 0.0035 |\n| 10000 | UB | 0.0065 | 0.007 | 0.0075 | 0.0075 | 0.008 |\n| 100000 | UB | 0.0065 | 0.008 | 0.008 | 0.008 | 0.0085 |\n| 500000 | UB | 0.0025 | 0.004 | 0.005 | 0.005 | 0.005 |\n\n\n\n**Sensitivity analysis for $\\rho$** (t $\\times 10^4$)\n| $\\rho$ | method | t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|---------------|---------------|---------------|---------------|---------------|\n| 0.0005 | GM | 0 | 0 | 0 | 0 | 0.0005 | 0.0005 |\n| 0.001 | GM | 0.002 | 0.003 | 0.003 | 0.003 | 0.003 | 0.0035 |\n| 0.002 | GM | 0 | 0.0085 | 0.015 | 0.0185 | 0.0225 | 0.024 |\n| 0.005 | GM | 0 | 0.022 | 0.026 | 0.0275 | 0.029 | 0.029 |\n\n\n\n**For minor comment:**\n\nTo avoid a conflict with the symbol $U$ used in the upper bound in the confidence sequence, we have changed the notation for the random variable perturbing the gradient from $ U $ to $ W$ . Similarly, to prevent confusion with the symbol $\\delta $ commonly used in the definition of differential privacy, we have replaced the radius of the confidence sequence with  $\\gamma $.\n\n\n\n**For questions:**\n\n\nQ1: If we understand your question correctly, when estimating more than one quantile, such as multiple quantile values, a naive approach would be to divide the privacy budget and query the data multiple times. However, this method is inefficient and suffers from the quantile crossing issue. In the non-DP setting, there have been recent developments to address the crossing problem (see [8]). However, smoothing the gradient in these methods breaks the binary structure, potentially increasing the variance of the added noise under differential privacy.\n\nMore generally, if the goal is to estimate functionals such as the distribution function (CDF) $P(X < t)$, the tail probability $P(X > t)$, or the conditional value at risk (CVaR) $\\mathbb{E}(X \\mathbf{1}(X > Q_{1-\\alpha}) \\mid X)$, then SGD-based approaches may not be applicable. For non-DP sequential inference of the CDF, see [9], and for local differential privacy (LDP) estimation of the CDF, see [10]. Sequential inference under LDP for these related functionals would require entirely different derivations, which we believe is an interesting but challenging direction.\n\n\nQ2: Since our main focus is sequential inference for quantiles, we only establish that the order of the proposed confidence sequence is optimal in the sense that it matches the law of the iterated logarithm (LIL) rate. However, we do not discuss the optimality of the average length of the sequence. The paper [11] you referred to investigates optimality for mean estimation and related problems under local differential privacy (LDP), as does the subsequent work [12].\n\nRegarding quantile estimation, SGD-based methods combined with binary permutation are shown to be optimal in some sense, as discussed in Section 3.5 of [13]. However, from an inference perspective, particularly in the sequential setting—obtaining an optimal confidence sequence remains challenging, even in the non-DP case.\n\n\n\n**Reference**\n\n\n[1] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for\nlarge-scale machine learning. SIAM review, 60(2):223–311, 2018.\n\n[2] Jeremy Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar.\nGradient descent on neural networks typically occurs at the edge of stability. In\nInternational Conference on Learning Representations, 2021.\n\n[3] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods\nfor online learning and stochastic optimization. Journal of machine learning\nresearch, 12(7), 2011.\n\n[4] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation\nby averaging. SIAM journal on control and optimization, 30(4):838–855, 1992.\n\n[5]  Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the\nimportance of initialization and momentum in deep learning. In International\nconference on machine learning, pages 1139–1147. pmlr, 2013.\n\n\n[6] Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation\nwith large step-sizes. 2016.\n\n[7] Chuhan Xie, Kaicheng Jin, Jiadong Liang, and Zhihua Zhang. Asymptotic time-uniform inference for parameters in averaged stochastic approximation. arXiv\npreprint arXiv:2410.15057, 2024.\n\n[8] Chen, L., Keilbar, G., \\& Wu, W. B. (2025). Smoothed SGD for quantiles: Bahadur representation and Gaussian approximation. arXiv preprint arXiv:2505.13299.\n \n[9]  Steven R Howard and Aaditya Ramdas. (2022) Sequential estimation of quantiles with\napplications to a/b testing and best-arm identification. Bernoulli, 28(3):1704–\n1728. \n\n[10] Liu, Y., Hu, Q., \\& Kong, L. (2024). Tuning-free estimation and inference of cumulative distribution function under local differential privacy.\n\n \n[11] Steinberger, L. (2024). Efficiency in local differential privacy. The Annals of Statistics, 52(5), 2139-2166.\n\n\n[12] Nikita, K., \\& Steinberger, L. (2025, April). Efficient Estimation of a Gaussian Mean with Local Differential Privacy. In International Conference on Artificial Intelligence and Statistics (pp. 118-126). PMLR.\n\n\n[13] Liu, Y., Hu, Q., Ding, L., \\& Kong, L. (2023, July). Online local differential private quantile inference via self-normalization. In International Conference on Machine Learning (pp. 21698-21714). PMLR."}, {"review_id": "UFsTi1uVo7", "reviewer": "Reviewer_wd2F", "summary": "The paper presents an online algorithm for computing time-uniform, asymptotic confidence sequences for quantiles under LDP.  Specifically, the proposed solution combines dynamically chained parallel SGD (P-SGD) with a randomized response (RR) mechanism to simultaneously estimate the target quantile and its variance. A Gaussian approximation leads to asymptotically anytime-valid confidence sequences whose widths obey the law of the iterated logarithm (LIL), with optimal convergence rates. The method is also computationally efficient, requiring only O(κ) memory for κ chains.", "questions": "Q1: The paper claims to provide the \"first result on sequential inference for quantiles within the LDP framework\". However, prior work like Liu et al. (2023) also presents an online LDP quantile inference method. Could you clarify the distinction? \n\nQ2: Could you provide practical guidance on selecting h(t)?\n\nQ3: The experimental results show that your P-SGD-based method, in the non-private setting (r=1), produces tighter confidence sequences than the state-of-the-art non-asymptotic method from Howard and Ramdas (2022). Could you explain the reason?\n\nQ4: In theorem 2, it seems that big-O_a,s.(1) should be small-o?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\nS1. The paper introduces a novel approach that enables the consistent estimation of the estimator's variance without incurring any additional privacy cost.\n\nS2. The paper provides a strong, almost sure Gaussian approximation for the quantile estimator. \n\nS3. This work presents the first method for constructing time-uniform, asymptotic confidence sequences for quantiles with LDP.\n\nWeaknesses:\n\nW1. All experiments are conducted on synthetic data (mostly Normal and Cauchy). There is no demonstration on real-world datasets or application scenarios.\n\nW2: The algorithm's performance relies on several key hyperparameters, most notably the function h(t) that determines the number of parallel chains. The specific choice used in the experiments (e.g., h(t)=⌊8log₁₀(t)⌋) is presented without justification or a sensitivity analysis showing how performance changes with different functions.\n\nW3: The paper makes some empirical claims based on weak evidence. For instance, the claim that its pointwise confidence interval is \"more efficient\" than a competing method is supported only by visual inspection of a single plot (Figure 2), which is anecdotal.\n\nW4. The confidence sequences are only asymptotically valid. There are no finite-sample coverage guarantees, which limits their practical reliability in early rounds.\n\nW5. The theoretical results require a continuous and bounded derivative of the underlying density near the quantile. This excludes irregular or heavy-tailed distributions, despite claims of robustness.", "was_revised": true, "final_justification": "In the rebuttal, the authors added real-world experiments (addressing W1). They also provided quantitative evidence for their efficiency claims (W3), as well as theoretical justification for their asymptotic approach (W4/Q3). The new experiment shows robustness to assumption violations (W5).\n\nThese changes have improved the quality and impact of the paper. The work now appears significantly more solid, well-evaluated, and technically sound than it did in the initial submission.\n\nThe remaining issues are the weak response regarding the hyperparameter h(t) (W2/Q2) and the unaddressed technical error in Theorem 2 (Q4).", "rebuttal": "We sincerely appreciate the time and effort you've invested in reviewing our paper. Your feedback is invaluable to us, and we have addressed each of your concerns below. Should you have any further questions, please do not hesitate to ask.\n\n\n**For weakness:**  \n\nW1: We have now incorporated two representative real datasets widely used in privacy research:\n\nLaw school dataset [1]. This dataset consists of 20,649 examples aiming to predict students' undergraduate GPA based on their personal information and academic abilities. Given that GPA reflects individual educational outcomes and is protected under strict data-use agreements [1], we treat it as sensitive educational information requiring privacy protection.\n\nGovernment salary dataset [2]. This dataset originates from the 2018 American Community Survey conducted by the U.S. Census Bureau. It includes over 200,000 observations, with annual salary (USD) as the response variable. Annual salary represents typical personal financial information [3]; therefore, we treat it as sensitive data warranting privacy protection.\n\nTo facilitate analysis, we applied a logarithmic transformation for two datasets and then back-transformed the confidence sequence bounds after prediction. We apply our proposed method: AsympCS based on equation (4) (UB) and equation (6) (GM)—to conduct privacy-preserving inference on the median ($\\tau = 0.5$), targeting GPA in the first dataset and annual salary in the second. Specifically, we construct AsmpCS for the respective quantiles under truthful response rates $r = 0.75$ and $0.9$, and set the hyperparameter $\\rho =0.01$ in equation (6) while keeping all other tuning parameters consistent with those used in Section 4. The upper and lower bounds of the confidence sequences are presented in Table 1. Due to space limitations, we present only the government salary dataset results; the GPA results of law school dataset are qualitatively similar.\n\n**Table 1.** AsmpCS for the government salary dataset.\n| Method | t=2000 | t=10000 | t=20000 | t=50000 | t=200000 |\n| :-: |-|-|-|-|-|\n ||||**r = 0.75**||| \n| GM-L | 37898 | 44404 | 45774 | 47381  | 48326 |\n| GM-U | 49301 | 49097 | 48732 | 48850  | 48982 |\n| UB-L | 39522 | 44067 | 45348 | 47096  | 48197 |\n| UB-U | 47286 | 49472 | 49189 | 49145  | 49113 |\n |||| **r = 0.9** |||  \n| GM-L | 41707 | 45584 | 46375 |47728|48429|\n| GM-U | 50777 | 48980 | 48751 |48727|48954|\n| UB-L | 43036 | 45336 | 46030 |47533|48325|\n| UB-U | 49215 | 49247 | 49115 |48927|49059|\n\nFrom the results in Table 1, we observe that the CSs produced by our two methods (UB and GM) under different response rates $r$ covering similar central values. In addition, in both datasets, the length of the constructed CS decreases as $r$ increases. As $t$ grows, the sequence based on UB becomes more conservative than that based on GM. These observations align with our simulation findings and further demonstrate the methods' adaptability.\n\nW2:  According to your valuable comment, we have conducted comprehensive sensitivity analyses for several key hyperparameters. Due to the space limits, please see the rebuttal for reviewer By34.\n\nW3: We conduct additional experiments to compare our proposed confidence interval in Corollary 1 with the SN-based method in [9]. While both methods achieve empirical coverage rates close to the nominal confidence level, the average length of our confidence interval is more narrow across various settings of $r$ and $\\tau$, indicating higher efficiency of our approach. Due to the space limits, we only present the following table.\n\n**Table 2.** $T = 1 \\times 10^6$.\n| method | $\\tau$ | $r = 1$   | $r = 0.9$  | $r = 0.75$ | $r = 0.5$  | $r = 0.25$ | \n|-|-|-|-|-|-|-|\n|| | |  length | ($\\times 10^{-3}$) | | |\n| SN-based| 0.8|7.22|8.33|10.8| 16.9| 35.7|\n|| 0.5| 6.41| 7.03 | 8.47| 12.6| 26.2|\n|| 0.3| 6.73 | 7.52| 9.20| 14.2| 29.3|\n|Ours| 0.8| 5.61| 6.59 | 8.48 | 13.8| 30.3|\n|| 0.5| 4.89 | 5.48| 6.61|10.0| 21.3|\n|| 0.3| 5.17| 5.86| 7.26| 11.3| 24.4|\n\nW4: In the concluding remarks of the original paper, we stated that “Finally, although non-asymptotic error bounds for SGD estimators have been extensively studied (e.g., [4]), extending these results to obtain fully non-asymptotic confidence sequences for SGD iterates under LDP remains an attractive yet challenging avenue for future research.”\n    \nWe elaborate on this point to clarify our results. Under local differential privacy, we estimate quantiles and conduct sequential inference using permutation-based SGD iterates, which are temporally dependent rather than i.i.d. Existing non-asymptotic sequential inference methods (e.g., [5]) assume i.i.d. data, and extending them to dependent settings remains challenging.\n\nAlthough our AsmpCSs are theoretically asymptotic, extensive experiments show they control type I error well, even in early rounds.\n\nConsider a special case when $r=1$, corresponding to the non-DP setting.  Our proposed method produces tighter confidence sequences than [6]. We elaborate on this comparison below for greater clarity.  Theoretically,  according to [5], the stitching function $\\mathcal S_\\alpha$ for the sub-gamma process with scale parameter $c$ is defined by, \n\n$\\mathcal S_{\\alpha}(v):=\\sqrt{k_1^2v\\ell(v)+k_2^2c^2\\ell^2(v)}+k_2c\\ell(v).$\n\nThe non-asymptotic confidence sequence (CS) developed in [6] is based on the observation that a sub-Bernoulli process with range parameters $(g,h) = (p, 1-p)$ or $(g,h) = (1-p, p)$ is also sub-gamma with scale $c = (1-2p)/3$ or $c = (2p-1)/3$, respectively, as detailed in the proof of Theorem 1 therein.  In contrast, our asymptotic CS is based on a sub-Gaussian process, which corresponds to the special case where $c=0$,    which yields a sharper bound for $\\mathcal{S}_\\alpha(v)$. Consequently, the resulting confidence sequences are tighter than [6], and they  also align with the form of the law of the iterated logarithm, as discussed in [5].\n\nEmpirically, our CSs are tighter and better calibrated (type I error near $\\alpha$), while the non-asymptotic CS in [5] is often overly conservative. Similar empirical advantages of asymptotic CSs are also noted in [7].\n\nW5: Assumption (A1) ensures asymptotic normality of the sample quantile under the non-DP setting, as shown in Corollary 2.3.3.A of [8]. It requires that the distribution function $F(\\cdot)$ is differentiable at the true quantile $x^\\ast$, with a strictly positive derivative, in the non-DP framework. If $f(\\cdot)$ is a density of $F(\\cdot)$, it is not necessary that $f(\\cdot)=F'(\\cdot)$. However, if $f(\\cdot)$ is continuous at $x^\\ast$, then $F'(x^\\ast)=f(x^\\ast)>0$. \n\nAssumption (A2) is technical but important for controlling a negligible term in the Gaussian approximation, where a second-order Taylor expansion is used (see line 731). It is mild and holds for many distributions, including heavy-tailed ones like the Cauchy.\n\nFor irregular distributions, we consider the density \n\n$f(x)= (\\beta_{10,100}(x) + \\beta_{100,100}(x) + \\beta_{100,10}(x))/ 3,$\n\nwhere $\\beta_{\\alpha,\\beta}(x)$ denotes the density of a Beta distribution with parameters $\\alpha$ and $\\beta$. This mixture has a   spike at $\\tau = 0.5$, implying a large derivative of the density at that point. We perform additional numerical simulations and show the result under $r=0.75$ and $\\tau=0.5$ in Table 3, confirming that our method remains valid.\n\n**Table 3.** $t \\times 10^4$\n|method|t= 5|t= 100|t= 200|t= 300|t= 400|t = 500|\n|-|-|-|-|-|-|-|\n|UB|0.002|0.004|0.007|0.024|0.028| 0.029|\n|GM|0|0|0.002|0.031|0.036|0.046|\n\n**For questions:**  \n\nQ1: We study asymptotic confidence sequences for quantiles under the LDP framework, while [9] developed pointwise confidence intervals. Confidence sequences provide valid intervals over time for ongoing monitoring, unlike confidence intervals which apply to fixed sample sizes. We estimate the variance via permutation-based SGD without extra privacy cost, whereas [9] uses a self-normalized method that avoids variance estimation but yields wider intervals.\n\nQ2: According to the sensitivity analysis for the choice of $h(\\cdot)$ we conduct, \nthe default setting provided in our original paper (e.g., $h(t) = \\lfloor 8 \\log_{10}(t) \\rfloor$) can serve as a practical choice.\n\nQ3: Please see W4.\n\nQ4: Thank you for your careful reading. We would like to clarify that in Theorem 2, we indeed use $o_{a.s.}(1)$, not  $O_{a.s.}(1)$, as correctly stated in the manuscript. Kindly see page 6 for reference.\n\n**Reference**\n[1] Linda F Wightman. Lsac national longitudinal bar passage study. lsac research report series. 1998.\n\n[2] Drago Ple\\v{c}ko, Nicolas Bennett, and Nicolai Meinshausen. fairadapt: Causal reasoning for fair data preprocessing. Journal of Statistical Software, 110:1–35, 2024.\n\n[3] Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza. Differentially private quantiles. In International Conference on Machine Learning, pages 3713–3722. PMLR, 2021.\n\n[4] Likai Chen, Georg Keilbar, and Wei Biao Wu. Recursive quantile estimation: Non-asymptotic confidence bounds. Journal of Machine Learning Research, 24(91):1–25, 2023.\n\n[5] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055–1080, 2021.\n\n[6] Steven R Howard and Aaditya Ramdas. Sequential estimation of quantiles with applications to a/b testing and best-arm identification. Bernoulli, 28(3):1704– 1728, 2022.\n\n[7] Ian Waudby-Smith, David Arbour, Ritwik Sinha, Edward H Kennedy, and Aaditya Ramdas. Time-uniform central limit theory and asymptotic confidence sequences. The Annals of Statistics, 52(6):2613–2640, 2024.\n\n[8] Robert J Serfling. Approximation theorems of mathematical statistics. JohnWiley \\& Sons, 2009.\n\n[9]  Yi Liu, Qirui Hu, Lei Ding, and Linglong Kong. Online local differential private quantile inference via self-normalization. In International Conference on Machine Learning, pages 21698–21714. PMLR, 2023."}, {"review_id": "JbyfhIO9gK", "reviewer": "Reviewer_Nwru", "summary": "This work studies quantile estimation (and its variance) in the online setting under local differential privacy. The main techniques used in the paper is a parallel stochastic gradient descent (P-SGD) which partitions the data and uses multiple parallel SGD optimizations to estimate the quantile. One of the main contributions of the work is increasing the number of partitions as the number of samples increases dynamically. The algorithm is also able to measure the variance of the estimator using the sample variance from the multiple chains. To achieve privacy, the algorithm applies randomized response on the binary quantity of whether the current estimate of the quantile is smaller or larger than the data point. This signal is used to estimate the true quantile using SGD. \n\nThe paper analyzes this algorithm theoretically to show that this allows them to derive an almost surely Gaussian approximation for the Polyak-Ruppert-type estimator of a quantile obtained by P-SGD and an almost surely consistent estimator of the quantile variance that relies only on the iterates of P-SGD.\n\nFinally, the work also simulates some finite sample performance of the method using a Gaussian and Cauchy distributions which shows that they are able to achieve narrower intervals compared to previous works.", "questions": "Can the authors expand on how sensitive finite sample performance is on the choice of hyperparameters?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Paper is easy to read and follow. \n- The algorithm is simple, easy to implement, is fully online and requires low memory overhead.\n- Work provides strong theoretical and simulation results. \n\nWeaknesses:\n- The algorithm might require tuning many hyperparameters", "was_revised": true, "final_justification": "Based on the other reviews and rebuttals, I will choose to keep my initial rating.", "rebuttal": "We sincerely appreciate the time and effort you've invested in reviewing our paper. Your feedback is invaluable to us, and we have addressed each of your concerns below. Should you have any further questions, please do not hesitate to ask.\n\n\n**For weakness:**  \n\nW1: Our tuning parameters fall into three categories. The first includes SGD-based parameters (e.g., the learning rate–related parameter $a$). Selecting the learning rate is indeed a well-known challenge in practice: SGD can be sensitive to this choice, especially in high-dimensional sparse settings and in rare–frequent or heavy-tailed regimes; see [1,2,3].\n\n\nWe will reiterate this limitation in the revised manuscript and plan to investigate additional techniques for reducing our method's sensitivity to SGD-based parameters in future work. Nevertheless, under appropriate conditions, for example, when the objective is convex and smooth, or when the initialization is sufficiently close to the true parameter, Polyak–Ruppert averaged SGD enjoys provable convergence with tolerable sensitivity to the learning rate [4,5,6]. As later reported in our sensitivity studies, our results are robust to reasonable variations in this hyperparameter.\n\nThe second category includes tuning parameters related to time-uniform inference, such as the AsympCS starting index $m$ and the hyperparameter $\\rho$ in the Gaussian mixture bound (equation (6)). The third category consists of tuning parameters specific to our proposed method, such as the number of chains $h(t)$. We find that the results are not sensitive to these parameters; thus, recommendations from the time-uniform inference literature [7]  and the default setting provided in our paper (e.g., $h(t) = \\lfloor 8 \\log_{10}(t) \\rfloor$) can serve as practical choices. \n\nFurthermore, according to your valuable comment, we have now conducted comprehensive sensitivity analyses for the aforementioned tuning parameters (i.e., $a$, $m$, $\\rho$, and $h(t)$). Specifically, we consider one of the simulation settings from Section 4, with a total sample size of $T = 5{,}000{,}000$, $1,000$ repetitions, truthful response rate $r = 0.75$, quantile level $\\tau = 0.5$, and normally distributed data. We evaluate the time-uniform type I error for AsympCS across a range of hyperparameter choices. The results are summarized in the following Tables. We are pleased to report that, the proposed methods maintain the nominal type I error rate (5\\%) for nearly all hyperparameter choices, demonstrating its insensitivity to these tuning parameters.\n\n**Sensitivity analysis for $a$**: (t $\\times 10^4$)\n| $a$ | method | t = 5 | t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|-----------|---------------|---------------|---------------|---------------|---------------|\n| 0.55 | UB | 0.003 | 0.005 | 0.005 | 0.005 | 0.005 | 0.005 |\n| 0.6 | UB | 0.002 | 0.003 | 0.003 | 0.003 | 0.003 | 0.004 |\n| 0.65 | UB | 0.002 | 0.003 | 0.004 | 0.004 | 0.004 | 0.004 |\n| 0.7 | UB | 0.002 | 0.002 | 0.002 | 0.002 | 0.002 | 0.002 |\n| 0.55 | GM | 0 | 0.002 | 0.005 | 0.01 | 0.012 | 0.014 |\n| 0.6 | GM | 0 | 0.001 | 0.002 | 0.004 | 0.009 | 0.012 |\n| 0.65 | GM | 0 | 0.002 | 0.007 | 0.01 | 0.012 | 0.014 |\n| 0.7 | GM | 0 | 0.001 | 0.002 | 0.003 | 0.007 | 0.009 |\n\n\n**Sensitivity analysis for $h(t)$** (t $\\times 10^4$)\n| $h(t)$ | method | t = 5 | t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|-----------|---------------|---------------|---------------|---------------|---------------|\n| $6\\log_{10}(t/5)$ | UB | 0.01| 0.016 | 0.017 | 0.018 | 0.019 | 0.02 |\n| $7\\log_{10}(t/5)$ | UB | 0.006 | 0.008 | 0.01 | 0.011 | 0.011 | 0.011 |\n| $8\\log_{10}(t/5)$ | UB | 0.002 | 0.003 | 0.003 | 0.003 | 0.003 | 0.004 |\n| $9\\log_{10}(t/5)$ | UB | 0.003 | 0.003 | 0.003 | 0.003 | 0.003 | 0.003 |\n| $10\\log_{10}(t/5)$ | UB | 0 | 0 | 0 | 0 | 0 | 0 |\n| $6\\log_{10}(t/5)$ | GM | 0 | 0.006 | 0.025 | 0.043 | 0.054 | 0.065 |\n| $7\\log_{10}(t/5)$ | GM | 0 | 0.001 | 0.012 | 0.021 | 0.027 | 0.031 |\n| $8\\log_{10}(t/5)$ | GM | 0 | 0.001 | 0.002 | 0.004 | 0.009 | 0.012 |\n| $9\\log_{10}(t/5)$ | GM | 0 | 0.001 | 0.004 | 0.006 | 0.007 | 0.01 |\n| $10\\log_{10}(t/5)$ | GM | 0 | 0 | 0.001 | 0.002 | 0.004 | 0.004 |\n\n\n**Sensitivity analysis for $m$** (t $\\times 10^4$)\n| $m$ | method |t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|---------------|---------------|---------------|---------------|---------------|\n| 1 | UB | 0.003 | 0.003 | 0.003 | 0.003 | 0.0035 |\n| 10000 | UB | 0.0065 | 0.007 | 0.0075 | 0.0075 | 0.008 |\n| 100000 | UB | 0.0065 | 0.008 | 0.008 | 0.008 | 0.0085 |\n| 500000 | UB | 0.0025 | 0.004 | 0.005 | 0.005 | 0.005 |\n\n\n**Sensitivity analysis for $\\rho$** (t $\\times 10^4$)\n| $\\rho$ | method | t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|---------------|---------------|---------------|---------------|---------------|\n| 0.0005 | GM | 0 | 0 | 0 | 0 | 0.0005 | 0.0005 |\n| 0.001 | GM | 0.002 | 0.003 | 0.003 | 0.003 | 0.003 | 0.0035 |\n| 0.002 | GM | 0 | 0.0085 | 0.015 | 0.0185 | 0.0225 | 0.024 |\n| 0.005 | GM | 0 | 0.022 | 0.026 | 0.0275 | 0.029 | 0.029 |\n\n\n\n**Reference**\n\n[1] Linda F Wightman. Lsac national longitudinal bar passage study. lsac research report series. 1998.\n\n[2] Drago Ple\\v{c}ko, Nicolas Bennett, and Nicolai Meinshausen. fairadapt: Causal reasoning for fair data preprocessing. Journal of Statistical Software, 110:1–35, 2024.\n\n[3] Jennifer Gillenwater, Matthew Joseph, and Alex Kulesza. Differentially privatequantiles. In International Conference on Machine Learning, pages 3713–3722. PMLR, 2021.\n\n[4] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838–855, 1992.\n\n[5]  Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pages 1139–1147. pmlr, 2013.\n\n\n[6] Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step-sizes. 2016.\n\n[7] Chuhan Xie, Kaicheng Jin, Jiadong Liang, and Zhihua Zhang. Asymptotic time-uniform inference for parameters in averaged stochastic approximation. arXiv preprint arXiv:2410.15057, 2024."}, {"review_id": "El2hBCKu41", "reviewer": "Reviewer_2z3U", "summary": "Accurately estimating the quantiles under LDP is challenging because it needs asymptotic variance estimates of the estimator. For online quantile inference (LDP reports arriving in sequence), [46] proposed a parallel SGD based framework with high confidence variance estimation. However, their variance estimator does not obey consistency due to fixed length of the chains.\nThis work extends the idea of using P-SGD, and proposes a new low resource online method for estimating confidence sequences for quantiles, and an almost surely consistent estimator  of the quantile variance (derived from P-SGD iterates) under LDP.\nThey also show that Gaussian approximation for the proposed estimator provides asymptotically anytime-valid confidence sequences with lengths  following the LIL.", "questions": "1)\tThe setting does not seem to assume any bound on the input? Please clarify.\n2)\tPlease explain the equation on line 128 (at least in the Appendix). It’s not immediate how G(x, \\Xi) can be viewed as a permuted stochastic gradient.   \n3)\tPlease discuss the continual observations model (or the differences from it) in the literature review, placing your solution in perspective. Some generic background on DP and LDP can be reduced in Section 1.\n4)\tMarkers and legends in Figures are barely visible. Please increase the sizes.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1)\tOnline quantile and its consistent variance estimation with asymptotic confidence sequences under LDP seems unsolved. \n2)\tThe method seems easy to implement and practical. \n\nWeakness: \n1)\tSGD based methods can be sensitive to the choice of hyperparameters and require tuning.\n\n2)\tThe continual observation model under DP (https://dl.acm.org/doi/10.1145/1806689.1806787) is well-established in the central setting. Authors do not discuss this model in the literature review.  There are some works (e.g. https://openreview.net/attachment?id=pWeQdceMHL&name=pdf) also in the LDP setting, possibly not on the same problem though.", "was_revised": true, "final_justification": "Authors have promised to add missing descriptions, and added new experiments in the rebuttal.", "rebuttal": "We sincerely appreciate the time and effort you've invested in reviewing our paper. Your feedback is invaluable to us, and we have addressed each of your concerns below. Should you have any further questions, please do not hesitate to ask.\n\n\n**For weakness:**  \n\nW1: We totally agree with you that SGD-based methods can be sensitive to the choice of hyperparameters and\nrequire tuning, especially in high-dimensional sparse settings and in rare–frequent or heavy-tailed regimes; see [1,2,3].\n\nWe will reiterate this limitation in the revised manuscript and plan to investigate additional techniques for reducing our method's sensitivity to SGD-based parameters in future work. Nevertheless, under appropriate conditions, for example, when the objective is convex and smooth, or when the initialization is sufficiently close to the true parameter, Polyak–Ruppert averaged SGD enjoys provable convergence with tolerable sensitivity to the learning rate [4,5,6]. \n\n\nFurthermore, according to your valuable comment, we have now conducted comprehensive sensitivity analyses. Specifically, we varied the learning rate hyperparameter $a$. We consider one of the simulation settings from Section 4, with a total sample size of $T = 5{,}000{,}000$, $1,000$ repetitions, truthful response rate $r = 0.75$, quantile level $\\tau = 0.5$, and normally distributed data. We evaluate the time-uniform type I error for AsympCS across a range of hyperparameter choices. The results are summarized in the following Tables. We are pleased to report that, the proposed methods maintain the nominal type I error rate (5\\%) for all hyperparameter choices, demonstrating its insensitivity to these tuning parameters.\n\n**Sensitivity analysis for $a$**: (t $\\times 10^4$)\n| $a$ | method | t = 5 | t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|-----------|---------------|---------------|---------------|---------------|---------------|\n| 0.55 | UB | 0.003 | 0.005 | 0.005 | 0.005 | 0.005 | 0.005 |\n| 0.6 | UB | 0.002 | 0.003 | 0.003 | 0.003 | 0.003 | 0.004 |\n| 0.65 | UB | 0.002 | 0.003 | 0.004 | 0.004 | 0.004 | 0.004 |\n| 0.7 | UB | 0.002 | 0.002 | 0.002 | 0.002 | 0.002 | 0.002 |\n| 0.55 | GM | 0 | 0.002 | 0.005 | 0.01 | 0.012 | 0.014 |\n| 0.6 | GM | 0 | 0.001 | 0.002 | 0.004 | 0.009 | 0.012 |\n| 0.65 | GM | 0 | 0.002 | 0.007 | 0.01 | 0.012 | 0.014 |\n| 0.7 | GM | 0 | 0.001 | 0.002 | 0.003 | 0.007 | 0.009 |\n\n\n**Sensitivity analysis for $h(t)$** (t $\\times 10^4$)\n| $h(t)$ | method | t = 5 | t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|-----------|---------------|---------------|---------------|---------------|---------------|\n| $6\\log_{10}(t/5)$ | UB | 0.01| 0.016 | 0.017 | 0.018 | 0.019 | 0.02 |\n| $7\\log_{10}(t/5)$ | UB | 0.006 | 0.008 | 0.01 | 0.011 | 0.011 | 0.011 |\n| $8\\log_{10}(t/5)$ | UB | 0.002 | 0.003 | 0.003 | 0.003 | 0.003 | 0.004 |\n| $9\\log_{10}(t/5)$ | UB | 0.003 | 0.003 | 0.003 | 0.003 | 0.003 | 0.003 |\n| $10\\log_{10}(t/5)$ | UB | 0 | 0 | 0 | 0 | 0 | 0 |\n| $6\\log_{10}(t/5)$ | GM | 0 | 0.006 | 0.025 | 0.043 | 0.054 | 0.065 |\n| $7\\log_{10}(t/5)$ | GM | 0 | 0.001 | 0.012 | 0.021 | 0.027 | 0.031 |\n| $8\\log_{10}(t/5)$ | GM | 0 | 0.001 | 0.002 | 0.004 | 0.009 | 0.012 |\n| $9\\log_{10}(t/5)$ | GM | 0 | 0.001 | 0.004 | 0.006 | 0.007 | 0.01 |\n| $10\\log_{10}(t/5)$ | GM | 0 | 0 | 0.001 | 0.002 | 0.004 | 0.004 |\n\n\n**Sensitivity analysis for $m$** (t $\\times 10^4$)\n| $m$ | method |t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|---------------|---------------|---------------|---------------|---------------|\n| 1 | UB | 0.003 | 0.003 | 0.003 | 0.003 | 0.0035 |\n| 10000 | UB | 0.0065 | 0.007 | 0.0075 | 0.0075 | 0.008 |\n| 100000 | UB | 0.0065 | 0.008 | 0.008 | 0.008 | 0.0085 |\n| 500000 | UB | 0.0025 | 0.004 | 0.005 | 0.005 | 0.005 |\n\n\n**Sensitivity analysis for $\\rho$** (t $\\times 10^4$)\n| $\\rho$ | method |t = 100 | t = 200 | t = 300 | t = 400 | t = 500 |\n|---|---------------|---------------|---------------|---------------|---------------|---------------|\n| 0.0005 | GM | 0 | 0 | 0 | 0 | 0.0005 | 0.0005 |\n| 0.001 | GM | 0.002 | 0.003 | 0.003 | 0.003 | 0.003 | 0.0035 |\n| 0.002 | GM | 0 | 0.0085 | 0.015 | 0.0185 | 0.0225 | 0.024 |\n| 0.005 | GM | 0 | 0.022 | 0.026 | 0.0275 | 0.029 | 0.029 |\n\n\nW2:  Thank you for bringing the interesting work [7] to our attention. Our setting, which combines sequential inference with online algorithms, is designed for scenarios involving continual observation. Specifically, we consider user-level privacy protection under LDP, where the true data cannot be accessed directly. In contrast, under continual observation or in the simpler central DP setting, one may have access to the raw data and apply privacy mechanisms in subsequent steps.\n\nIn such cases, quantile inference, or even point estimation, is nontrivial; see recent developments in [8] and [9]. To achieve differential privacy under continual observation, one may compress or recompute the induced noise at each step to improve efficiency, as discussed in [10]. We will incorporate a more detailed literature review on continual observation in the revised version.\n\n \n\n\n**For questions**\n\nQ1:  Indeed, our algorithm does not require the input random variables to be bounded. \nThis contrasts with classical linear statistics, such as those in [11], which require a boundedness assumption. In our approach, the quantile is estimated via SGD, leveraging the fact that the gradient is an indicator function that always outputs binary values, which allows us to avoid imposing boundedness assumptions under LDP. \n\nThis is supported both theoretically and empirically. Theoretically, the proposed asymptotic confidence sequence is   justified by the Gaussian approximation established in Theorem 1, which, similar to the Gaussian approximation used in [12], does not rely on any boundedness condition. Empirically, both the Gaussian and Cauchy distributions used in our simulations are unbounded random variables, and our method performs well even under the heavy-tailed Cauchy distribution.\n\nQ2: We apologize for any confusion. The permuted input gradient is modified using the algorithm proposed in [14]. Regarding the required data, the true data is observed with probability $r$, and a Bernoulli(0.5) sample is used with probability $1 - r$. As a result, the quantile being estimated from the permuted data corresponds to $r\\tau/2 + (1 - r)/2$, as stated in the equation on line 128. We will include a more detailed explanation of the LDP mechanism in the Appendix in the revised version.\n\nQ3: We will reduce the general background on DP and LDP in Section 1 and include a more detailed literature review on continual observation in the revised version.\n\nQ4: We have carefully revised all figures by enlarging the markers, and font sizes of the legends, so that the visual presentation is now clearer and easier to read.\n\n\n**Reference**\n\n\n[1] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223–311, 2018.\n\n[2] Jeremy Cohen, Simran Kaur, Yuanzhi Li, J Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. In International Conference on Learning Representations, 2021.\n\n[3] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.\n\n[4] Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4):838–855, 1992.\n\n[5]  Ilya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pages 1139–1147. pmlr, 2013.\n\n\n[6] Aymeric Dieuleveut and Francis Bach. Nonparametric stochastic approximation with large step-sizes. 2016.\n\n[7] Dwork, C., Naor, M., Pitassi, T., \\& Rothblum, G. N. (2010, June). Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing (pp. 715-724).\n\n[8] Gillenwater, J., Joseph, M., & Kulesza, A. (2021, July). Differentially private quantiles. In International Conference on Machine Learning (pp. 3713-3722). PMLR.\n\n[9] Lalanne, C., Garivier, A., & Gribonval, R. (2023, July). Private statistical estimation of many quantiles. In International Conference on Machine Learning (pp. 18399-18418). PMLR.\n\n[10] Tenenbaum, J., Kaplan, H., Mansour, Y., & Stemmer, U. (2023, July). Concurrent shuffle differential privacy under continual observation. In International Conference on Machine Learning (pp. 33961-33982). PMLR.\n\n[11]  Ian Waudby-Smith, Steven Wu, and Aaditya Ramdas. Nonparametric extensions of randomized response for private confidence sets. In International Conference on Machine Learning, pages 36748–36789. PMLR, 2023.\n\n\n[12] Chuhan Xie, Kaicheng Jin, Jiadong Liang, and Zhihua Zhang. Asymptotic time-\nuniform inference for parameters in averaged stochastic approximation. arXiv\npreprint arXiv:2410.15057, 2024.\n\n[13] Liu, Y., Hu, Q., Ding, L., \\& Kong, L. (2023, July). Online local differential private quantile inference via self-normalization. In International Conference on Machine Learning (pp. 21698-21714). PMLR."}, {"review_id": "JRvu0bibrB", "reviewer": "Reviewer_PTJr", "summary": "The paper is the first to extend the asymptotic confidence sequences of the quantile estimation framework introduced by Waudby-Smith et al. [41] to differential privacy.  It uses a parallel SGD method that was recently applied to high-confidence interval problems by Wanrong Zhu et al. [46]. Differential privacy is ensured through a randomized response mechanism used with gradient-like updates proposed by Liu et al. [32].", "questions": "1) The paper states that the proposed approximation rate is faster than that given by the Law of the Iterated Logarithm (LIL). However, isn't the LIL rate of order $ O\\left(\\frac{1}{\\sqrt{t \\log \\log t}}\\right)$, which appears faster than the rate you claim? \n\n2) Would high-confidence intervals alone suffice for private quantile estimation with confidence intervals? What advantages does the asymptotic sequence framework offer in practice?\n\n3) If the goal was only quantile estimation without confidence intervals, how would your procedure compare to that of Liu et al. [32]?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "This paper is the first to bring the time uniform quantile estimation with confidence intervals problem into differential privacy. In doing so, it generalizes previous non-private works. I find the paper to be interesting, and the technical contributions are solid and non-trivial.\n\nHowever, I am not fully convinced that the asymptotic sequence framework is the most appropriate choice for practical applications. Would high-confidence intervals alone be sufficient?\n\nAdditionally, the paper would benefit from further polishing:\n\nPresentation : The fonts in all of the plots are too small and difficult to read.\n\n\nThere are issues with spacing and punctuation in citations, such as: “Privacy , see [16]”, “Privacy,see [26]”, “(e.g., 7)”", "was_revised": true, "final_justification": "This paper is the first to bring the time uniform quantile estimation with confidence intervals problem into differential privacy. In doing so, it generalizes previous non-private works. I find the paper to be interesting, and the technical contributions are solid and non-trivial.\n\nIn the rebuttal, the authors provided additional justification for the practicality of the asymptotic sequence framework. While I find their arguments reasonable, they are not fully convincing; therefore, I maintain my borderline accept score.\n\nMy concerns regarding the paper’s presentation are promised to be resolved.", "rebuttal": "We sincerely appreciate the time and effort you've invested in reviewing our paper. Your feedback is invaluable to us, and we have addressed each of your concerns below. Should you have any further questions, please do not hesitate to ask.\n\n\n**For weakness:**  \nW1: \nIn practice, it has become standard for organizations with an online presence to conduct large-scale A/B testing [1,2] to improve product performance and user experience. These experiments are inherently sequential, with users arriving over time and results observed quickly. \nUnlike clinical trials or industrial quality control, where formal planning is the norm, online experiments are often run with little predefined stopping rules and rely on dynamic decision-making. In such settings, confidence sequences offer a principled alternative, providing valid inference at arbitrary stopping times without sacrificing statistical rigor.  \n\nWhile classical confidence intervals are indeed sufficient in fixed-sample settings, the asymptotic confidence sequence framework is particularly well-suited for modern practical applications that involve continuous monitoring and sequential decision-making. Otherwise, using confidence intervals may lead to severely uncontrolled type-I error, as evidenced in [3,4]. Thus, our use of the asymptotic CS framework is highly  practically motivated. \n\nWhen the number of chains $K$ is fixed, $\\widehat{\\sigma}_T^2 $ is no longer a consistent estimator of $\\sigma^2$. According to  the proof of Theorem 1, we can derive that the statistic $\\sqrt{T}\\widehat\\sigma_T^{-1}\\widehat x_T$ asymptotically follows a $t$-distribution with $K-1$ degrees of freedom, which entails that an  asymptotic confidence interval for the quantile at time $T$ takes the form:\n\n$ [\\widehat x_T - \\widehat\\sigma_T t_{K-1,1-\\alpha/2} / \\sqrt{T},   $ $\\widehat x_T + \\widehat\\sigma_T t_{K-1,1-\\alpha/2} / \\sqrt{T}]$\n\n\n\nsimilar to the  high-confidence interval proposed in [5]. This indeed improves the accuracy of the confidence interval, as it  holds for any fixed number of chains $K$. However, constructing confidence sequences based on the \n$t$-distribution is highly challenging, as existing results in the literature predominantly focus on sub-Gaussian or sub-Gamma random variables; see [6].\n\n\nW2: \"Additionally, the paper would benefit from further polishing.\"\n\nWe have carefully revised the manuscript to improve the clarity, organization, and overall presentation.\n\nW3: \"Presentation : The fonts in all of the plots are too small and difficult to read.\"\n\nWe have carefully revised all plots by increasing the font sizes to ensure that the figures are clearer and more readable.\n\nW4: \"here are issues with spacing and punctuation in citations, such as: “Privacy , see [16]”, “Privacy,see [26]”, “(e.g., 7)\"\n\nWe have corrected these citation issues and carefully reviewed the entire manuscript to ensure that all spacing and punctuation in citations are now properly formatted.\n\n**For questions**\n\n\nQ1: For a sequence of i.i.d. random variables $\\{X_i\\}$ with mean $0$ and variance $\\sigma^2$, let $S_n = \\sum_{i=1}^n X_i$. The Law of the Iterated Logarithm (LIL) states:\n\n$$\\limsup_{n \\to \\infty} \\frac{S_n}{\\sqrt{2n \\log \\log n}} = \\sigma \\quad \\text{almost surely}.$$\n\n\nThus, for sample mean $S_n/n$, the LIL rate is of order $O_{a.s.}\\left(\\sqrt{ \\log \\log n/n}\\right)$. Note that the strong approximation rate established in Theorem 1 is of order \n$o_{a.s.}\\left(\\sqrt{ \\log \\log n/n}\\right)$, which is strictly faster than the rate given by the law of the iterated logarithm. \n\n\nQ2: Kindly refer to weakness 1. \n\nQ3: we conducted additional experiments to directly compare our method with that of [7], focusing solely on point estimation accuracy for quantiles. Specifically, we considered the same simulation setting as in Section 4, with total sample size $T = 5,000,000$, quantile level $\\tau = 0.3,0.5,0.8$, the truthful response rates $r=0.25,0.5,0.75,0.9,1$ and distribution type set to normal. The evaluation metric is the mean squared error (MSE) of the estimated quantiles.  The detailed comparison results are provided in Tables 1-5. We find that when $\\tau$ is close to $0.5$, our method achieves comparable MSE to that in [7]. However, as $\\tau$ deviates from $0.5$, the MSE of our method becomes slightly worse. This can be attributed to the  dynamically chained parallel procedure used procedure employed in our quantile inference.\n\n**Table 1.** MSE ($\\times 10^{-7}$) for $T = 5 \\times 10^6$.\n\n| method | $\\tau$ | $r = 1$   | $r = 0.9$  | $r = 0.75$ | $r = 0.5$  | $r = 0.25$ | \n|--------|--------|-----------|------------|------------|------------|------------|\n|        |        |           |   MSE      | ($\\times 10^{-7}$) |   |   |\n| sn     | 0.8    | 4.49      | 5.71       | 9.53       | 22.7       | 105        |\n|        | 0.5    | 3.22      | 3.80       | 5.57       | 12.6       | 53.6       |\n|        | 0.3    | 3.75      | 4.63       | 6.99       | 16.2       | 70.6       |\n| Our   | 0.8    | 5.47      | 7.48       | 12.2       | 31.8       | 154        |\n|        | 0.5    | 3.20      | 4.04       | 5.71       | 13.1       | 52.5       |\n|        | 0.3    | 4.11      | 4.94       | 7.43       | 18.3       | 82.3       |\n\n\n**Table 2.** MSE ($\\times 10^{-7}$) for $T = 4 \\times 10^6$.\n\n| method | $\\tau$ | $r = 1$   | $r = 0.9$  | $r = 0.75$ | $r = 0.5$  | $r = 0.25$ | \n|--------|--------|-----------|------------|------------|------------|------------|\n|        |        |           |   MSE      | ($\\times 10^{-7}$) |   |   |\n| SN-based     | 0.8    | 5.61      | 7.25       | 11.4       | 29.2       | 128        |\n|        | 0.5    | 4.13      | 4.84       | 6.78       | 16.0       | 61.1       |\n|        | 0.3    | 4.52      | 5.49       | 8.53       | 21.1       | 80.7       |\n| Our   | 0.8    | 6.68      | 9.23       | 15.4       | 39.7       | 193        |\n|        | 0.5    | 3.98      | 5.21       | 7.02       | 16.5       | 67.7       |\n|        | 0.3    | 4.98      | 6.23       | 9.30       | 23.4       | 104        |\n\n**Table 3.** MSE ($\\times 10^{-7}$) for $T = 3 \\times 10^6$.\n| method | $\\tau$ | $r = 1$   | $r = 0.9$  | $r = 0.75$ | $r = 0.5$  | $r = 0.25$ | \n|--------|--------|-----------|------------|------------|------------|------------|\n|        |        |           |   MSE      | ($\\times 10^{-7}$) |   |   |\n| SN-based     | 0.8    | 7.26      | 9.61       | 15.3       | 40.0       | 176        |\n|        | 0.5    | 5.66      | 6.74       | 9.04       | 21.9       | 83.9       |\n|        | 0.3    | 6.19      | 7.46       | 11.3       | 29.6       | 110        |\n| Our   | 0.8    | 8.84      | 12.5       | 20.2       | 53.5       | 255        |\n|        | 0.5    | 5.25      | 6.67       | 9.43       | 22.0       | 94.5       |\n|        | 0.3    | 6.66      | 8.32       | 12.8       | 30.6       | 138        |\n\n**Table 4.** MSE ($\\times 10^{-7}$) for $T = 2 \\times 10^6$.\n\n| method | $\\tau$ | $r = 1$   | $r = 0.9$  | $r = 0.75$ | $r = 0.5$  | $r = 0.25$ | \n|--------|--------|-----------|------------|------------|------------|------------|\n|        |        |           |   MSE      | ($\\times 10^{-7}$) |   |   |\n| SN-based     | 0.8    | 10.5      | 13.9       | 21.8       | 60.6       | 256        |\n|        | 0.5    | 8.25      | 10.2       | 13.0       | 32.5       | 126        |\n|        | 0.3    | 9.58      | 12.1       | 16.7       | 43.5       | 166        |\n| Our   | 0.8    | 13.0      | 19.2       | 30.0       | 82.8       | 394        |\n|        | 0.5    | 7.64      | 10.0       | 14.1       | 32.3       | 144        |\n|        | 0.3    | 10.2      | 12.8       | 19.4       | 47.4       | 207        |\n\n**Table 5.** MSE ($\\times 10^{-7}$) for $T = 1 \\times 10^6$.\n\n| method | $\\tau$ | $r = 1$   | $r = 0.9$  | $r = 0.75$ | $r = 0.5$  | $r = 0.25$ | \n|--------|--------|-----------|------------|------------|------------|------------|\n|        |        |           |   MSE      | ($\\times 10^{-7}$) |   |   |\n| SN-based     | 0.8    | 20.6      | 27.6       | 44.9       | 124        | 498        |\n|        | 0.5    | 16.1      | 19.9       | 26.4       | 64.5       | 245        |\n|        | 0.3    | 17.6      | 23.2       | 31.7       | 84.3       | 314        |\n| Our   | 0.8    | 26.6      | 38.9       | 62.3       | 174        | 823        |\n|        | 0.5    | 16.1      | 21.3       | 28.5       | 68.0       | 306        |\n|        | 0.3    | 20.7      | 25.9       | 38.6       | 96.3       | 440        |\n\n\n**Reference**\n\n[1]  Nicholas Larsen, Jonathan Stallrich, Srijan Sengupta, Alex Deng, Ron Kohavi, and Nathaniel T Stevens. Statistical challenges in online controlled experiments: A review of a/b testing methodology. The American Statistician, 78(2):135–149, 2024.\n\n[2] Dan Siroker and Pete Koomen. A/B testing: The most powerful way to turn clicks into customers. John Wiley \\& Sons, 2015.\n\n[3] Peter Armitage, CK McPherson, and BC Rowe. Repeated significance tests on accumulating data. Journal of the Royal Statistical Society: Series A (General), 132(2):235–244, 1969.\n\n[4]  Ron Berman, Leonid Pekelis, Aisling Scott, and Christophe Van den Bulte. Phacking and false discovery in A/B testing, volume 10. SSRN, 2018.\n\n[5] Wanrong Zhu, Zhipeng Lou, Ziyang Wei, and Wei Biao Wu. High confidence level inference is almost free using parallel stochastic optimization. arXiv preprint arXiv:2401.09346, 2024.\n\n\n[6] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon. Time-uniform, nonparametric, nonasymptotic confidence sequences. The Annals of Statistics, 49(2):1055–1080, 2021.\n\n[7] Liu, Y., Hu, Q., Ding, L., \\& Kong, L. (2023, July). Online local differential private quantile inference via self-normalization. In International Conference on Machine Learning (pp. 21698-21714). PMLR."}]

Author rebuttal:

Meta-review: ## Metareview

This paper studies the question of private quantile inference for sequence of elements. Here we are given datapoints drawn from some underlying distribution, one at a time, and we would like to produce asymptotic confidence sequence (AsymCS) such that the true quantile lies in the sequence *simultaneously for all time step* with a certain probability. We would like to protect the datapoint via local differential privacy (LDP), meaning that each datapoint is privatized immediately without using central curator.

The main result of this work is an LDP algorithm which produces AsymCS such that the width of the confidence intervals is smaller than Law of Iterated Logarithm (LIL). This is obtained using a parallel SGD (P-SGD) approach where we construct multiple chains of (roughly) equal size, and each datapoint is allocated to a chain as they arrive. The actual SGD in each chain is done via a similar approach to [Liu et al., ICML 2023] who considers the pointwise version of the problem and uses binary randomized response to privatize each datapoint. Finally, the estimator is the weighted average of the chain-wise means.

## Strengths

- The setting of private AsymCS is natural in many modern scenarios e.g. in A/B testing. This paper provides a rigorous result that can be applied in such settings.

- This is the first work to use P-SGD in the context of private (asymptotic) confidence sequence. This is innovative and should be applicable to future work.

- The algorithm is simple, efficient (both from time and memory perspectives) and, thus, should be practical.

## Weaknesses

- Although this is the first work that considers computation of asymptotic confidence *sequence* with LDP, the *pointwise* setting has been considered before [Liu et al., ICML 2023] (who also used SGD-based algorithm with binary randomized response). However, getting anytime-valid guarantees for sequence like in this paper still requires significant amount of technical work.

- There are multiple hyperparameters that can be tuned and might affect the performance. This is addressed in the authors' response as they show sensitivity analysis that their AsymCS remains effective for a vast region of hyperparameters. 

## Recommendation

Given that this is the first work to tackle private confidence sequences for quantiles and that it obtains very interesting rigorous results, we support acceptance.
Decision: Accept (poster)