betaFeedback

WorksMathematics

Infinite Quantiles Inference under Local Differential Privacy

Abstract

We study simultaneous quantile inference under local differential privacy for a number of target probabilities that grows with the sample size. Each user participates once, so learning unknown quantile locations and calibrating their joint uncertainty must share the same private information. We fuse complementary cumulative distribution function (CDF) scores from a single tree report using their exact covariance; the variance at the correct anchor is no larger than that of either score, and anchor error incurs only quadratic excess variance. Three consecutive cohorts then localize the quantiles, estimate their densities, and supply fresh scores for a one-step correction and joint multiplier calibration. Under mild conditions, a uniform representation controls localization and density errors and yields asymptotically valid simultaneous coverage. A fixed-privacy regime permits every polynomially growing target grid. Simulations show consistent same-report precision gains, while comparisons with CDF-band inversion expose the sample cost of learning target locations. Census microdata illustrates how the resulting joint intervals support wage-percentile ratios.

Introduction

From 1987 to 2004, U.S. upper-half wage inequality rose while lower-half inequality contracted [4]. Quantile comparisons distinguish these distributional changes that a mean or an isolated percentile can miss. As a data stream grows, a finer percentile grid permits more detailed comparisons. Their uncertainty must be assessed jointly: a collection of pointwise intervals does not control the largest error over an expanding grid. We study this problem when each user privatizes a measurement before sending it to the server and participates only once.

Local differential privacy (LDP) makes this joint inference problem different from classical quantile inference. Sample-quantile representations and cumulative distribution function (CDF) bands connect nonprivate quantile error to a shared empirical process [5, 13, 23, 11]. Under LDP, the server receives randomized reports rather than observations [31, 15]. It must learn where the quantiles are while deciding which thresholds to query. Giving each percentile a separate user group loses information as the number of targets grows; using a shared report avoids this split but creates dependent errors at adaptively selected thresholds. Joint calibration must accommodate both that dependence and the error in the learned locations.

Recent work provides online inference for a prespecified scalar quantile. Liu et al. [21] use randomized binary inquiries and self-normalization to avoid nuisance-density estimation. Cai et al. [6] use dynamically growing parallel stochastic-approximation paths to obtain an asymptotic confidence sequence over time. Other developments address communication-efficient single-quantile estimation, federated scalar inference, and fixed-dimensional quantile-regression contrasts (Aamand et al., 2025; Cai et al., 2026a,b; Liu and Hu, 2026). Our target is joint inference at a terminal horizon fixed before data collection, with the number of probability targets increasing as that horizon grows. Extending scalar inference to this setting requires uniform control of localization and density errors at the scale of a maximum, rather than a separate scalar approximation at every target.

CDF estimation followed by inversion is an important alternative. Liu et al. [22] study private CDF estimation on public inspection grids. A simultaneous CDF band supports probability queries selected after release, whereas direct inference learns locations for prespecified probabilities.

For independent observations with CDF FF, our targets are

0<τ1,n<⋯<τkn,n<1,Qj,n=F−1(τj,n),0 < \tau_{1,n} < \cdots< \tau_{k_n,n} < 1,\qquad Q_{j,n} = F^{-1}(\tau_{j,n}),

where the deterministic number knk_n may diverge. “Infinite” refers to this increasing sequence of finite target grids. With one report per user at privacy budget εn>0\varepsilon_n > 0 and public queries allowed to depend on past reports, we seek intervals satisfying

P{Qj,n∈In,j for every j≤kn}→1−α,α∈(0,1).\mathbb{P}\left\{Q_{j,n} \in\mathcal{I}_{n,j}\ \text{for every }j \leq k_n\right\} \to1-\alpha,\qquad\alpha\in(0,1).

The probability targets are specified before collection; the method learns their spatial locations.

Our first step extracts more information from a shared range-tree report with optimized unary encoding (OUE) [30, 12]. Every threshold has two unbiased CDF scores: a prefix sum and the complement of a suffix sum. Their exact covariance determines a minimum-variance linear fusion at the correct CDF anchor. Fusion remains unbiased for any public anchor, and the variance penalty for an inaccurate anchor is quadratic. Thus the target probability itself supplies an increasingly accurate anchor as localization improves. This gain changes only decoding, with no additional report or privacy expenditure.

Our second step separates adaptive learning from joint calibration. The first cohort averages one projected stochastic-approximation path for each target. The second estimates densities near the learned locations. The third supplies fresh user-level score vectors. A one-step correction cancels first-order localization error, leaving a product of localization and density errors and a local nonlinear remainder. Conditional on the first two cohorts, the fresh vectors are independent and identically distributed; shared Gaussian multipliers retain their cross-quantile dependence. We bound the remainder uniformly and connect it to high-dimensional Gaussian approximation [24, 9, 10]. At fixed privacy, a sufficient regime permits every polynomial growth rate of knk_n, with only logarithmic grid-size factors in the width bound.

We compare a same-channel fixed-grid inversion procedure with the complete three-cohort method, including the users spent on learning. Fusion reduces error by 21–23% relative to balanced decoding in the matched three-stage experiments. CDF inversion gives smaller errors and narrower, more conservative intervals on the tested public spatial grids. These comparisons distinguish the benefit of extracting complementary information from a report from the cost of learning where to query it.

The paper is organized as follows. Section 2 develops the procedure and its implementation. Section 3 states the assumptions and theoretical guarantees, and Section 4 compares fixed-chain calibration. Sections 5 and 6 present the complete numerical experiments and wage-percentile application. Section 7 concludes. Proofs and their auxiliary lemmas are collected in the appendices.

Shared private scores and quantile inference

Algorithm 1 gives the complete procedure, from public inputs to simultaneous intervals. We first construct the shared private report and then describe the three cohorts and default tuning; Section 2.4 gives the streaming updates.

We suppress the subscript nn on τj,n\tau_{j,n} and Qj,nQ_{j,n} when the sample size is clear. The generalized inverse is

F−1(u)=inf⁡{x∈R:F(x)≥u}.F^{-1}(u)=\inf\{x\in\mathbb{R}:F(x)\ge u\}.

The public projection bracket [L,U][L, U] contains all target quantiles in its interior, while the raw observations may be unbounded. Public scientific range information or an independently privatized range-estimation cohort can supply this bracket. The Stage-1 projection frequency and the distance of final iterates from its endpoints summarize its adequacy. At time ii, a public query qiq_i may be a measurable function of the previous reports Z1,…,Zi−1Z_1, \ldots, Z_{i-1}. A local randomizer Mi\mathcal{M}_i is εn\varepsilon_n-LDP conditional on the public history if, for every pair x,x′x, x', every history, and every measurable report set AA,

P{Mi(x;qi)∈A∣Z1:i−1}≤eεnP{Mi(x′;qi)∈A∣Z1:i−1}.\mathbb{P}\{\mathcal{M}_i(x;q_i) \in A \mid Z_{1:i-1}\} \le e^{\varepsilon_n}\mathbb{P}\{\mathcal{M}_i(x';q_i) \in A \mid Z_{1:i-1}\}.

The complete procedure is user-level εn\varepsilon_n-LDP for every deterministic horizon. Conditional on the past transcript, OUE has this privacy bound and the sampled tree level is independent of the user’s value. History-dependent queries and server-side computations preserve the bound; each person belongs to only one cohort. Section B gives the likelihood-ratio argument for the full sequential transcript.

Complementary scores from one report

For privacy budget ε=εn\varepsilon= \varepsilon_n, fix dd ordered public thresholds

x(1)≤⋯≤x(d).x_{(1)} \le\cdots\le x_{(d)}.

Stable tags distinguish ties. These thresholds induce d+1d+1 interval categories

C0=(−∞,x(1)],Cs=(x(s),x(s+1)] (1≤s<d),Cd=(x(d),∞).C_0 = (-\infty, x_{(1)}], \quad C_s = (x_{(s)}, x_{(s+1)}] \ (1 \le s < d), \quad C_d = (x_{(d)}, \infty).

Let Hd=⌈log⁡2(d+1)⌉H_d = \lceil\log_2(d+1) \rceil and pad the d+1d+1 real leaves by zero-probability leaves to obtain a complete binary tree with 2Hd2^{H_d} leaves. Levels are numbered 1,…,Hd1, \ldots, H_d, with the root excluded. A user with value XX determines the leaf C(X)C(X), draws a level L⋆L^\star uniformly from {1,…,Hd}\{1, \ldots, H_d\}, and finds the unique node on the path to C(X)C(X) at that level [12]. The node is represented by a unary vector. With pε=1/2p_\varepsilon= 1/2, qε=1/(eε+1)q_\varepsilon= 1/(e^\varepsilon+ 1), OUE [30] independently releases every bit as one with probability pεp_\varepsilon when its input bit is one and with probability qεq_\varepsilon when its input bit is zero. The report consists of the sampled level and the privatized unary vector.

For a node vv at level ℓ(v)\ell(v), let ZvZ_v be its released bit, or zero on an unsampled level, and define

ψv(Z)=Hd1{L⋆=ℓ(v)}Zv−qεpε−qε\psi_v(Z) = H_d \mathbf{1}\{L^\star= \ell(v)\}\frac{Z_v - q_\varepsilon}{p_\varepsilon- q_\varepsilon}

The privacy-noise constant and a deterministic score envelope are

νε=4eε(eε−1)2,Bd,ε=1+2Hdeεeε−1.(1)\nu_{\varepsilon} = \frac{4e^{\varepsilon}}{(e^{\varepsilon}-1)^2}, \qquad\mathcal{B}_{d,\varepsilon} = 1 + \frac{2H_d e^{\varepsilon}}{e^{\varepsilon}-1}. \tag*{(1)}

For threshold rank r∈{1,…,d}r \in\{1,\ldots,d\}, let Dr−\mathcal{D}^{-}_{r} be the canonical disjoint-node decomposition of the first rr leaves and let Dr+\mathcal{D}^{+}_{r} be the decomposition of the complementary leaves. Each decomposition consists of the maximal tree nodes whose leaves lie entirely in the required set. Write wr−=∣Dr−∣w^{-}_{r} = |\mathcal{D}^{-}_{r}| and wr+=∣Dr+∣w^{+}_{r} = |\mathcal{D}^{+}_{r}|; both are between one and HdH_d, and each decomposition contains at most one node at any level. Define

Ar=∑v∈Dr−ψv,Br=1−∑v∈Dr+ψv.A_r = \sum_{v\in\mathcal{D}^{-}_{r}} \psi_v, \qquad B_r = 1-\sum_{v\in\mathcal{D}^{+}_{r}} \psi_v.

Both estimate F(x(r))F(x_{(r)}). We choose the fusion weight by evaluating the variances and covariance of ArA_r and BrB_r at a public reference value u∈(0,1)u \in(0,1) for F(x(r))F(x_{(r)}). For this anchor, set

ar−(u)=Hdwr−νε+(2Hd−1)u,a^{-}_{r}(u) = H_d w^{-}_{r}\nu_{\varepsilon} + (2H_d-1)u,
ar+(u)=Hdwr+νε+(2Hd−1)(1−u),a^{+}_{r}(u) = H_d w^{+}_{r}\nu_{\varepsilon} + (2H_d-1)(1-u),
λr∘(u)=ar+(u)ar−(u)+ar+(u),\lambda^{\circ}_{r}(u) = \frac{a^{+}_{r}(u)}{a^{-}_{r}(u)+a^{+}_{r}(u)},

and form the fused score

Gr(u)=λr∘(u)Ar+{1−λr∘(u)}Br.(2)G_r(u) = \lambda^{\circ}_{r}(u)A_r + \{1-\lambda^{\circ}_{r}(u)\}B_r. \tag*{(2)}

References

  1. [2]Acharya, J., Sun, Z., and Zhang, H. (2019). Hadamard response: Estimating distributions privately, efficiently, and with little communication. Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, PMLR 89, 1120–1129.arxiv.org/abs/1802.04705
  2. [3]Anderson, T. W. (2003). An Introduction to Multivariate Statistical Analysis, 3rd ed. Wiley, Hoboken, NJ.
  3. [4]Autor, D. H., Katz, L. F., and Kearney, M. S. (2006). The polarization of the U.S. labor market. American Economic Review 96, 189–194.
  4. [5]Bahadur, R. R. (1966). A note on quantiles in large samples. Annals of Mathematical Statistics 37, 577–580.DOI
  5. [6]Cai, L., Hu, Q., Sun, J., and Wu, S. (2025). Time-uniform and asymptotic confidence sequence of quantile under local differential privacy. Advances in Neural Information Processing Systems 38, 114488–114520.DOI
  6. [9]Chernozhukov, V., Chetverikov, D., and Kato, K. (2013a). Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors. Annals of Statistics 41, 2786–2819.
  7. [10]Chernozhukov, V., Chetverikov, D., and Kato, K. (2017). Central limit theorems and bootstrap in high dimensions. Annals of Probability 45, 2309–2352.
  8. [11]Chernozhukov, V., Fernández-Val, I., and Melly, B. (2013b). Inference on counterfactual distributions. Econometrica 81, 2205–2268.
  9. [12]Cormode, G., Kulkarni, T., and Srivastava, D. (2019). Answering range queries under local differential privacy. Proceedings of the VLDB Endowment 12, 1126–1138.arxiv.org/abs/1812.10942
  10. [13]Csörgő, M. (1983). Quantile Processes with Statistical Applications. CBMS-NSF Regional Conference Series in Applied Mathematics 42, SIAM, Philadelphia.
  11. [14]Dette, H. and Graw, C. (2024). Uncertainty quantification by block bootstrap for differentially private stochastic gradient descent. arXiv:2405.12553.arxiv.org/abs/2405.12553
  12. [15]Duchi, J. C., Jordan, M. I., and Wainwright, M. J. (2018). Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association 113, 182–201.arxiv.org/abs/1604.02390
  13. [16]Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics 6, 65–70.DOI
  14. [17]Kairouz, P., Oh, S., and Viswanath, P. (2014). Extremal mechanisms for local differential privacy. Advances in Neural Information Processing Systems 27.arxiv.org/abs/1407.1338
  15. [18]Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., and Smith, A. (2011). What can we learn privately? SIAM Journal on Computing 40, 793–826.
  16. [19]Kushner, H. J. and Yin, G. G. (2003). Stochastic Approximation and Recursive Algorithms and Applications, 2nd ed. Springer, New York.
  17. [21]Liu, Y., Hu, Q., Ding, L., and Kong, L. (2023). Online local differential private quantile inference via self-normalization. Proceedings of the 40th International Conference on Machine Learning, PMLR 202, 21698–21714.arxiv.org/abs/2306.10260
  18. [22]Liu, Y., Hu, Q., and Kong, L. (2024). Tuning-free estimation and inference of cumulative distribution function under local differential privacy. Proceedings of the 41st International Conference on Machine Learning, PMLR 235, 31147–31164.
  19. [23]Massart, P. (1990). The tight constant in the Dvoretzky–Kiefer–Wolfowitz inequality. Annals of Probability 18, 1269–1283.DOI
  20. [24]Polyak, B. T. and Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization 30, 838–855.DOI
  21. [25]Robbins, H. and Monro, S. (1951). A stochastic approximation method. Annals of Mathematical Statistics 22, 400–407.
  22. [26]Ruppert, D. (1988). Efficient estimators from a slowly convergent Robbins–Monro process. Technical Report 781, School of Operations Research and Industrial Engineering, Cornell University.
  23. [28]U.S. Census Bureau (2025). 2024 ACS 1-Year PUMS User Guide and Overview. U.S. Department of Commerce, Washington, DC. Available at https://www2.census.gov/programs-surveys/acs/tech_docs/pums/2024ACS_PUMS_User_Guide.pdf.
  24. [29]van der Vaart, A. W. (1998). Asymptotic Statistics. Cambridge University Press, Cambridge.
  25. [30]Wang, T., Blocki, J., Li, N., and Jha, S. (2017). Locally differentially private protocols for frequency estimation. 26th USENIX Security Symposium, 729–745.
  26. [31]Warner, S. L. (1965). Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association 60, 63–69.pubmed.ncbi.nlm.nih.gov/12261830
  27. [32]Xie, J., Shi, E., Jiang, B., Kong, L., and He, X. (2025). Online differentially private inference in stochastic gradient descent. arXiv:2505.08227.arxiv.org/abs/2505.08227
  28. [33]Zhu, W., Lou, Z., Wei, Z., and Wu, W. B. (2026). High confidence level inference is almost free using parallel stochastic optimization. arXiv:2401.09346, version 2.arxiv.org/abs/2401.09346

Paper details

vlnc:W_7v97m52b
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents