Time-uniform and Asymptotic Confidence Sequence of Quantile under Local Differential Privacy

Leheng Cai (Department of Statistics and Data Science) · Qirui Hu (Shanghai University of Finance and Economics) · Juntao Sun (Shanghai University of Finance and Economics) · Shuyuan Wu (Shanghai University of Finance and Economics)

anytime-validcomputational efficiencyconfidence sequencesgaussian approximationlaw of the iterated logarithmlocal differential privacy memory complexity numerical experiments online learning privacy protectionquantilesrandomized responsestochastic gradient descenttheoretical soundness

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.