acceptodds
Under review as a conference paper at ICLR 2027

Locally Differentially Private Online Quantile Inference with an Adaptive Mechanism

Abstract

A local privacy mechanism chosen for frequency estimation need not produce an efficient joint confidence set for quantiles. We select the reporting channel for ellipsoid volume or maximum simultaneous interval width, using one locally private categorical report per user. At the target quantiles, category probabilities are determined by the requested levels, making each candidate's reference score law public. Unknown quantile densities cancel from the volume comparison; an independent private probe supplies them for interval-width selection. Under local smoothness and bounded-library conditions, we establish exact library minimization for volume, a plug-in oracle inequality for width, and conditional asymptotic coverage after selection. A fixed-threshold correction separates localization error from the final score average. Independent strong-privacy experiments give selected joint coverage of – and 42%–43% smaller ellipsoid volumes than randomized response under the same correction, including the users reserved for localization. The comparison connects mechanism choice to confidence geometry and quantifies the precision cost of localization.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Local Differential privacy, Mechanism selection, Online inference, Quantile

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_VtQ5OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors of the paper study joint quantile estimation and confidence sets under sequential, local differential privacy (specifically, one-report-per-user local differential privacy). Comparisons with all current thresholds are encoded as one categorical variable and decoded through a private channel. At the true quantiles, category probabilities depend only on the requested quantile levels, making each candidate channel’s reference score distribution public. This enables selection by calibrated ellipsoid volume without knowing quantile densities; maximum-width selection additionally uses a private density probe. A disjoint pilot/probe/main split supports conditional asymptotic inference after selection. A fixed-threshold correction separates score noise from localization and density-estimation errors. Experimental validation includes simulated distributions, comparisons among five channels, calibration checks, and an illustration using public BMI records.

Critical strengths

(1) The inference-specific mechanism-selection formulation is useful: The public category distribution at the target quantiles allows computation of the score covariance despite the unknown population distribution. (A similar technique was used in [1]). Equations (8)–(9) identify why unknown density factors cancel when comparing ellipsoid volumes, while the maximum-width objective retains dependence on individual quantile densities. The common optimal decoder puts heterogeneous channels on the same CDF workload. This explains when the desired uncertainty summary should affect mechanism choice.

(2) The analysis addresses selection and the actual online recursion: Theorem 3.2 analyzes moving thresholds and does not seem to assume that online scores already follow the frozen truth distribution. Conditioning on the pilot and probe handles the selected channel, including selection near ties. Equation (19) and Proposition 3.3 provide a decomposition for fixed-threshold correction. The experiments differentiate channel improvements from localization costs and report independent calibration checks and coverage shortcomings. This makes the statistical contribution more convincing than a numerical comparison of channel covariances alone!

[1] https://arxiv.org/abs/2201.03380

Critical weaknesses

(1) I believe the authors do not sufficiently compare to related works in the literature on quantile Inference. Can the authors comment on how techniques from [1] apply to their results?

(2) Limits of reliable finite-sample coverage: Appendix B.3 reports coverage around 0.850–0.865 under a narrower density-probe bandwidth despite using >= 500,000 users! The improved fixed-threshold procedure uses 175,000 final inference reports out of 500,000 total users and increases confidence volumes by approximately 5.3–6.0 times relative to the recursive branch. This limits any claims about practical efficiency. The asymptotic results do not (yet) give an operationally and reliable way to choose the bandwidth and localization allocation for an unknown/unfamiliar distribution. Also, there are limits of the demonstrated incremental benefit of the selector: Section 4.2 explicitly states that the headline 42%–43% Wald-volume reductions are the gains of fixed OLH over fixed RR under the same protocol: both determinant-only and calibrated Wald selection choose OLH in those designs. The current evidence does not imply a meaningful practical gain of finite-score selection over a simpler determinant-based selector with Gaussian calibration. The confidence-geometry formulation is certainly useful! But I believe the headline improvements cannot be interpreted as demonstrating an additional benefit from adaptive selection.

[1] https://arxiv.org/abs/2201.03380

Questions for authors

(1) I believe the authors do not sufficiently compare to related works in the literature on quantile Inference. Can the authors comment on how techniques from [1] apply to their results?

(2) Contribution-isolating evaluation: Across the existing configurations, how much improvement in coverage and confidence-set size comes from finite-score mechanism selection relative to determinant-only Wald selection with Gaussian calibration and to the best fixed channel? Please compare these using the same user, privacy, and declared communication budgets. This would clarify the added value of the proposed selection/calibration layer.

(3) Tuning robustness: What rule should a practitioner use to choose the density bandwidth and localization allocation before seeing the evaluation distribution? Please quantify coverage, volume/width, and RMSE sensitivity around the reported bandwidth factors and the b=Nb=N allocation. The narrow-bandwidth coverage shortfall and the cost of fixed-threshold correction make this central to practical usefulness.

[1] https://arxiv.org/abs/2201.03380

3 comments
AuthorsOpenReview ↗

Response to Reviewer VtQ5 (1/3)

Thank you for your time and valuable comments.

W1 / Q1. Alabi, Ben-Eliezer and Chaturvedi (2022) include Gaussian population-quantile accuracy as well as central-DP sketches and continual release. Their server accesses raw stream items; ours receives one locally private report per user and targets joint confidence coverage after channel selection. A valid simultaneous CDF band yields joint quantile intervals by generalized inversion: on its coverage event, F‾←(τj)≤F←(τj)≤F‾←(τj)for every j.\overline F^{\leftarrow}(\tau_j)\le F^{\leftarrow}(\tau_j)\le\underline F^{\leftarrow}(\tau_j)\quad\text{for every }j. Simultaneous band coverage, nondecreasing bands and conservative endpoint conventions yield this statement, and an inverse-modulus condition, such as a positive local density lower bound, controls interval width. In the one-report LDP setting, this route requires a reporting design for a simultaneous CDF band that accounts for sampling, privacy and approximation errors.

W2 / Q2. In the submitted strong-privacy comparison, both determinant-only and calibrated Wald selection choose OLH; the 42–43% volume gain is therefore a fixed-OLH versus fixed-RR gain. In a separate near-tie design at ϵ=1\epsilon=1, the determinant-only OLH/RR factor is 0.955, whereas the estimated calibrated factor is 1.011 and selects RR. In the central-five privacy sweep, with matched user counts, privacy budgets, splits and an eight-bit Stage-3 ceiling, selected-method finite/Gaussian coverage differences are at most 0.004 and mean paired size ratios are 0.986–1.006. A separate rerun of the broader configurations retains the recursive estimator, multiplier 0.70 and 10%/20%/70% split, but uses 500 fresh online repetitions, 20000 calibration draws plus 20000 independent holdout draws, and common Stage-3 ceilings of 7, 8 and 10 bits for 3, 5 and 9 quantiles. The submission used separate repetitions, 500 calibration draws and its stated communication accounting. In this rerun, finite-score and determinant-only/Gaussian Wald selection choose the same channel in both libraries. Their coverage differences are between -0.002 and 0.002; their mean paired volume ratios are 0.9503–1.0329. These differences change calibration, not the selected channel. Across both geometries in this rerun, finite/Gaussian coverage differences range from -0.008 to 0.014, the largest from width-selector switching, and mean paired size ratios from 0.9503 to 1.0329.

Comparing the five-channel and expanded libraries within this same rerun gives:

SettingFive-channel rerun coverage/RMSEExpanded rerun coverage/RMSEVolume/RR, five-channel/expanded
Normal, 9 quantiles, n=500000n=500000, ϵ=1\epsilon=10.920/0.01390.944/0.01370.232/0.221
Mixture, 5 quantiles, n=400000n=400000, ϵ=1\epsilon=10.942/0.01600.906/0.0159—

For these two settings, the submission's separate five-channel results were 0.940/0.0135 and 0.924/0.0165, respectively; they are not the rerun values in the table. In that mixture, holding the Subset2 estimates fixed and replacing only the final Wald density standardization by true densities raises coverage from 0.906 to 0.930, with whitened covariance trace 5.01 against reference 5. For width selection, the ratio of mean selected width to the smallest mean fixed width is 0.9621–1.0000 (five-channel library) and 0.9692–1.0000 (expanded); at n=100000n=100000 in the mixture, the expanded ratio 0.9692 comes with selected/fixed coverage 0.924/0.938.

AuthorsOpenReview ↗

Response to Reviewer VtQ5 (2/3)

We ran a comparison across contrasting density profiles using the same feasible width selector. The populations are N(0,1)N(0,1) and the equal mixture of N(−1.25,0.652)N(-1.25,0.65^2) and N(1.25,0.652)N(1.25,0.65^2). Both use the central five probabilities (0.10,0.25,0.50,0.75,0.90)(0.10,0.25,0.50,0.75,0.90), public bounds [−4,4][-4,4], ϵ=0.5\epsilon=0.5, and the same ten-channel library with an eight-bit report allowance. Every method receives n=2000000n=2000000 users, split 10%/20%/70%; localization uses 3/43/4 of the last stage, leaving N=350000N=350000 final reports. The bandwidth multiplier 1.05 and localization fraction 3/43/4 were chosen after separate model-specific development runs and frozen before 500 fresh confirmation repetitions per population; the confirmation uses a disjoint seed family. The larger localization fraction supplies a longer anchor recursion, while the smaller multiplier reduces smoothing across the mixture valley. This is a development-selected configuration, not a data-driven tuning rule for an unknown distribution. The other recursion settings are unchanged. Channel choice uses only the independent private density probe and public score-law cutoffs. The nominal simultaneous coverage is 0.95:

PopulationMethodJoint coverageMean maximum widthRMSE
NormalFixed Subset20.9480.17050.0255
NormalFixed PairStair0.9480.18830.0265
NormalFeasible selector0.9480.17050.0255
Bimodal mixtureFixed Subset20.9420.35950.0415
Bimodal mixtureFixed PairStair0.9460.30170.0349
Bimodal mixtureFeasible selector0.9460.30170.0349

The private selector chooses Subset2 (100.0%) for normal data and PairStair (100.0%) for the bimodal mixture. Its mean maximum width is 9.5% smaller than fixed PairStair in the normal population and 16.1% smaller than fixed Subset2 in the mixture. Within each population, the selector exactly matches the better of these two fixed channels in width, coverage and RMSE; the percentage gains compare it with the other fixed channel. Neither Subset2 nor PairStair is the better choice in both populations, and the same private selection rule follows this change. The table gives coverage and RMSE alongside width; this larger-budget comparison is separate from the original 500000-user results.

The dominant Wald-volume gains in these studies come from the reporting channel (OLH or Subset2). Selection adds no gain over the fixed Wald winner here; the incremental practical benefit of finite-score calibration is small, and a width reduction accompanied by lower coverage is not an equal-coverage advantage.

AuthorsOpenReview ↗

Response to Reviewer VtQ5 (3/3)

Q3. The reference implementation fixes public bounds and levels before evaluation, a 10%/20%/70% pilot/probe/main split, step exponent 2/32/3, bandwidth 1.40(U−L)n2−1/41.40(U-L)n_2^{-1/4} and b=⌊n3/2⌋b=\lfloor n_3/2\rfloor, with pilot/main step constants 0.50/0.30, a bandwidth cap at half the smaller pilot boundary margin and densities truncated to [0.25/n2,max⁡{2,log⁡n2}][0.25/\sqrt{n_2},\max\lbrace 2,\log n_2\rbrace]. For locally Lipschitz densities, h≍n2−1/4h\asymp n_2^{-1/4} balances the stated density-error bound, and a=2/3a=2/3 requires β>1/2\beta > 1/2.

The submitted narrow-bandwidth recursive comparison has RR/OLH coverage 0.865/0.850 at ϵ=0.5\epsilon=0.5 and n=500000n=500000. Replacing only its final density standardization by true densities raises both to 0.908. The fixed-threshold expanded-library results below use a different estimator and independent repetitions. The broader rerun retains multiplier 0.70 to reproduce the recursive design; the profile comparison uses separately developed, frozen tuning as stated above. We currently have no data-driven bandwidth/localization rule with a finite-sample coverage guarantee for an unknown distribution.

The prespecified sensitivity multipliers are 0.70, 1.05, 1.40, 1.75, 2.10. Small bandwidth amplifies private probe noise: two density-floor events account for about 86.1% of Subset2 squared error in the normal 0.70 cell. For untruncated standardized t3t_3 with bounds [−6,6][-6,6], the reference multiplier 1.40 itself gives h=0.9447h=0.9447: the population symmetric difference quotient is 0.42325 against f(0)=0.63662f(0)=0.63662, and Wald/Max coverage is 0.880/0.928 with no density-floor activation. Thus the reference rule also has a material coverage shortfall in this design.

Fixed-threshold inference uses N=n3−bN=n_3-b reports; halving NN increases leading width by 2\sqrt2, and the correction has the exact decomposition

=N^{-1/2}\sum_{s=b+1}^{n_3}V_s +\sqrt N(\widehat D-D)e+\sqrt N r(e).$$ Here $e=\overline{\boldsymbol q}_b-\boldsymbol Q$, $D=\operatorname{diag}\\{f(Q_j)\\}$, $h(q)=\boldsymbol\tau-F(q)$ componentwise, $r(e)=h(\boldsymbol Q+e)+De$, and $V_s=\boldsymbol\tau-a_{\widehat r,Y_s}-h(\overline{\boldsymbol q}_b)$. Conditional on the localization reports, $V_s$ is centered. The remaining terms are the density-estimation/localization product and the local curvature remainder. The submitted inference result assumes $b,N\to\infty$ with $N/b$ bounded. Under its local smoothness and uniform-library conditions, $e=O_P(b^{-1/2})$ and consistent density estimation make both remainders vanish. A sublinear localization allocation would require additional uniform rate arguments. At $n=500000$, $\epsilon=0.5$, five quantiles and the expanded library (volume and width entries are ratios of medians, relative to the same law's multiplier-1.40, $b/n_3=0.5$ cell): | Law | Multiplier | $b/n_3$ | Coverage W/Max | RMSE W | Median volume/width ratio | |---|---:|---:|---:|---:|---:| | Normal | 1.40 | 0.500 | 0.932/0.942 | 0.0396 | 1.000/1.000 | | Normal | 0.70 | 0.500 | 0.912/0.938 | 0.1590 | 1.035/1.092 | | Normal | 1.40 | 0.250 | 0.918/0.916 | 0.0339 | 0.357/0.799 | | Normal | 1.40 | 0.750 | 0.960/0.954 | 0.0560 | 6.101/1.423 | | Normal | 1.40 | Recursive | 0.928/0.940 | 0.0266 | 0.172/0.700 | | Mixture | 1.40 | Recursive | 0.922/0.928 | 0.0292 | 0.180/0.698 | At $b/n_3=1/2$, the complete bandwidth comparison is: | Law | Multiplier | Coverage W/Max | RMSE W | Median volume/width ratio | |---|---:|---:|---:|---:| | Normal | 0.70 | 0.912/0.938 | 0.1590 | 1.035/1.092 | | Normal | 1.05 | 0.952/0.942 | 0.0605 | 1.015/1.061 | | Normal | 1.40 | 0.932/0.942 | 0.0396 | 1.000/1.000 | | Normal | 1.75 | 0.946/0.944 | 0.0387 | 0.998/0.986 | | Normal | 2.10 | 0.924/0.930 | 0.0396 | 1.006/0.948 | | Mixture | 0.70 | 0.918/0.950 | 0.0722 | 0.941/1.078 | | Mixture | 1.05 | 0.922/0.940 | 0.0450 | 0.932/1.025 | | Mixture | 1.40 | 0.930/0.930 | 0.0442 | 1.000/1.000 | | Mixture | 1.75 | 0.942/0.940 | 0.0440 | 1.124/0.994 | | Mixture | 2.10 | 0.944/0.948 | 0.0434 | 1.126/0.980 | Each setting has 500 independent repetitions; the mixture is $0.5N(-1,0.75^2)+0.5N(1,0.75^2)$ with the quantile bounds given above. Revised Tables 10 and 11 give every predefined setting, including density-floor events. Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.
Reviewer_ntVhOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the problem of generating joint confidence sets for multiple quantiles under local differential privacy (LDP) guarantees. It focuses on choosing an LDP mechanism from a predefined set to minimize either the volume of confidence ellipsoids or the maximum width of simultaneous confidence intervals. The authors propose an adaptive framework for selecting LDP mechanisms to improve joint quantile inference. They establish theoretical guarantees for mechanism selection and confidence-set coverage. Numerical experiments show that the selected mechanisms yield smaller confidence sets than randomized response while achieving coverage close to the nominal level.

Critical strengths

Unlike conventional approaches that focus on estimation accuracy, the paper considers the geometry of confidence sets when selecting LDP mechanisms. Specifically, it considers two criteria: 1) minimizing the volume of confidence ellipsoids and 2) minimizing the maximum width of simultaneous confidence intervals. This provides an interesting perspective on improving statistical inference under privacy constraints.

The experimental results show substantial reductions in confidence ellipsoid volume (42%–43%) compared to randomized response under strong privacy constraints (ϵ=0.5\epsilon = 0.5), demonstrating the effectiveness of the proposed approach. This highlights the importance of choosing LDP mechanisms based on the desired inference objective, which is one of the main motivations of the paper.

Critical weaknesses

The main limitation of the paper is that the mechanism-selection guarantees are restricted to a finite set of predefined LDP mechanisms, rather than all possible LDP mechanisms. Although some well-known LDP mechanisms have been studied, it is unclear how close the selected mechanism is to the globally optimal one. For instance, the framework and therefore the experimental evaluation do not consider some existing LDP mechanisms, such as subset selection [1,2] and thresholding with histogram encoding [3].

Moreover, It is not clear how much benefit the adaptive mechanism-selection framework provides over using a fixed LDP mechanism. More specifically, in the main experiments, the Wald-volume selector consistently chooses OLH. This can be interpreted as the improvements over randomized response mainly come from using OLH rather than from adaptive selection itself.


References:

[1] Wang S, Huang L, Wang P, Nie Y, Xu H, Yang W, Li XY, Qiao C. Mutual information optimally local private discrete distribution estimation. arXiv preprint arXiv:1607.08025. 2016 Jul 27.

[2] Ye M, Barg A. Optimal schemes for discrete distribution estimation under locally differential privacy. IEEE Transactions on Information Theory. 2018 Feb 26;64(8):5662-76.

[3] Wang T, Blocki J, Li N, Jha S. Locally differentially private protocols for frequency estimation. In26th USENIX security symposium (USENIX Security 17) 2017 (pp. 729-745).

Questions for authors

Is there a way to extend the proposed framework to consider a more general class of LDP mechanisms? Are there any specific properties of the mechanisms considered in the paper that prevent such a generalization?

Could the authors provide additional experiments demonstrating scenarios where adaptive mechanism selection offers a clear advantage over using a fixed mechanism?

4 comments
AuthorsOpenReview ↗

Response to Reviewer ntVh (1/2)

Thank you for your time and valuable comments.

W1 / Q1. For a fixed channel, the decoder is Loewner optimal. Over the realized finite library, Wald selection exactly minimizes calibrated pre-intersection volume, and the feasible maximum-width selector satisfies a plug-in oracle inequality. A separate staircase reduction gives a global weighted-trace optimum among finite-output LDP channels admitting an unbiased CDF decoder. This is a different objective from volume or maximum width; their gap to the optimum over all LDP channels is not bounded by our results. PairStair searches a complementary-pair subclass, not the complete staircase program. A new finite channel enters after its privacy, normalization, unbiased decoding, bounded scores and covariance nondegeneracy are verified. For a pilot-generated library, the number of candidates is bounded by a fixed Rmax⁡R_{\max}, the baseline remains available, and every retained unbiased ϵ\epsilon-LDP decoder satisfies deterministic uniform bounds σ‾2I⪯Σr⪯σ‾2I\underline\sigma^2 I\preceq\Sigma_r\preceq\overline\sigma^2 I and max⁡y∣τ−ar,y∣2≤Gmax⁡\max_y\\|\boldsymbol\tau-a_{r,y}\\|_2\le G_{\max}. Fresh final-stage users are independent of the information used to construct and select the library. Conditional on the realized library and common report count, Wald ranking exactly minimizes pre-intersection volume. Pilot information can affect library construction even though density factors cancel from this ranking. Growing or infinite libraries require approximation and calibration uniformly beyond fixed Rmax⁡R_{\max}; continuous-output channels require corresponding decoding and public-calibration constructions. Failure of uniform score bounds or covariance nondegeneracy also prevents applying the present theorem.

The expanded central-five library includes subset selection (Wang et al., 2016; Ye and Barg, 2018) and threshold histogram encoding (Wang et al., 2017). It has ten channels: the original five, subset sizes two through five, and THE. Size one is RR and is not counted twice. For subset outputs of size ss, probabilities are proportional to eϵe^{\epsilon} if the output contains the input and to one otherwise; comparing subsets that exchange one category proves full column rank. For THE, the output-bit expectation matrix is (p−q)I+q11⊤(p-q)I+q\mathbf 1\mathbf 1^{\top} with p>q>0p > q > 0, proving full column rank. The optimal CDF decoder applies, and total covariance bounds its score covariance below by the positive-definite CDF-indicator covariance. THE uses independent Laplace noise of scale 2/ϵ2/\epsilon and the threshold minimizing Wang et al. (2017)'s rare-frequency variance proxy qθ(1−qθ)/(pθ−qθ)2q_\theta(1-q_\theta)/(p_\theta-q_\theta)^2. The thresholds used are 0.561629,0.618553,0.7096140.561629,0.618553,0.709614 for ϵ=0.5,1,2\epsilon=0.5,1,2; this public frequency proxy is distinct from quantile confidence geometry.

At n=500000n=500000, ϵ=0.5\epsilon=0.5, bandwidth multiplier 1.401.40 and localization fraction 1/21/2, we ran 500 new repetitions per law, independently of the submission's 800-normal/400-mixture evaluation. The populations are N(0,1)N(0,1) and 0.5N(−1,0.752)+0.5N(1,0.752)0.5N(-1,0.75^2)+0.5N(1,0.75^2); bounds are their respective 0.0025 and 0.9975 quantiles, approximately [−2.8070,2.8070][-2.8070,2.8070] and [−2.9319,2.9319][-2.9319,2.9319]. Each channel has 20000 public calibration draws and 20000 independent reference holdout draws. The matched fixed-threshold comparison is:

ChannelNormal coverageNormal RMSENormal volume/RRMixture coverageMixture RMSEMixture volume/RR
RR0.9340.04561.0000.9480.05061.000
OLH0.9440.04040.5640.9380.04480.564
Subset20.9320.03960.4880.9300.04420.488

The comparisons match user/privacy budgets and use a common eight-bit Stage-3 ceiling. Adding Subset2 reduces Wald volume by 13.4% relative to OLH (13.4206% from unrounded values); the expanded-library Wald selector equals fixed Subset2 in every repetition, so it gives no additional gain over this fixed winner. The full-column-rank and covariance arguments above verify the added subset channels' admissibility.

AuthorsOpenReview ↗

Response to Reviewer ntVh (2/2)

W2 / Q2. The 42–43% Wald-volume reduction compares OLH with RR under the same estimation protocol. The additional mixture experiment examines data-dependent width selection: the private probe leads to Subset2 and PairStair choices with frequencies 69.4% and 30.6%. Coverage and width are:

MethodJoint coverageMean paired maximum width/RR
Feasible width selector0.9300.847
Fixed Subset20.9320.872
Fixed PairStair0.9420.898

The selector minimizes the reported plug-in width. We also evaluate how closely the feasible choice matches the true-density width criterion:

SettingMax coverageMean true-density criterion regretTrue-density oracle chosen
Normal, quantile bounds0.9420%100%
Mixture, quantile bounds0.9303.62%30.6%
Standardized t3t_3, [−6,6][-6,6]0.9280%100%
Mixture, [−6,6][-6,6]0.9545.09%2.4%

These comparisons use the same n,ϵn,\epsilon, multiplier and localization fraction above. The diagnostic evaluates the feasible choice using true densities after selection, holding the realized library and public cutoffs fixed. The common-bound designs use [−6,6][-6,6] and standard-normal quantile initialization; the t3t_3 observations are divided by 3\sqrt3 and are not truncated. In the quantile-bound mixture, selection reduces true-density criterion regret from fixed Subset2’s 5.22% to 3.62%; the tables show the corresponding coverage and width.

We ran a comparison across contrasting density profiles using the same feasible width selector. The populations are N(0,1)N(0,1) and the equal mixture of N(−1.25,0.652)N(-1.25,0.65^2) and N(1.25,0.652)N(1.25,0.65^2). Both use the central five probabilities (0.10,0.25,0.50,0.75,0.90)(0.10,0.25,0.50,0.75,0.90), public bounds [−4,4][-4,4], ϵ=0.5\epsilon=0.5, and the same ten-channel library with an eight-bit report allowance. Every method receives n=2000000n=2000000 users, split 10%/20%/70%; localization uses 3/43/4 of the last stage, leaving N=350000N=350000 final reports. The bandwidth multiplier 1.05 and localization fraction 3/43/4 were chosen after separate model-specific development runs and frozen before 500 fresh confirmation repetitions per population; the confirmation uses a disjoint seed family. The larger localization fraction supplies a longer anchor recursion, while the smaller multiplier reduces smoothing across the mixture valley. This is a development-selected configuration, not a data-driven tuning rule for an unknown distribution. The other recursion settings are unchanged. Channel choice uses only the independent private density probe and public score-law cutoffs. The nominal simultaneous coverage is 0.95:

PopulationMethodJoint coverageMean maximum widthRMSE
NormalFixed Subset20.9480.17050.0255
NormalFixed PairStair0.9480.18830.0265
NormalFeasible selector0.9480.17050.0255
Bimodal mixtureFixed Subset20.9420.35950.0415
Bimodal mixtureFixed PairStair0.9460.30170.0349
Bimodal mixtureFeasible selector0.9460.30170.0349

The private selector chooses Subset2 (100.0%) for normal data and PairStair (100.0%) for the bimodal mixture. Its mean maximum width is 9.5% smaller than fixed PairStair in the normal population and 16.1% smaller than fixed Subset2 in the mixture. Within each population, the selector exactly matches the better of these two fixed channels in width, coverage and RMSE; the percentage gains compare it with the other fixed channel. Neither Subset2 nor PairStair is the better choice in both populations, and the same private selection rule follows this change. The table gives coverage and RMSE alongside width; this larger-budget comparison is separate from the original 500000-user results.

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

Thank you for the detailed responses and the clarification regarding the scope of the optimality guarantees and the expanded mechanism library. The new experiments help demonstrate the benefit of adaptive mechanism selection across different distributions. I encourage the authors to incorporate these results and clarifications into the final version. The most important part I would recommend is: the distinction between improvements over a fixed mechanism and the best fixed mechanism for a given distribution.

Thank you for the follow-up and for the clear recommendation. We will incorporate the new experiments and clarifications into the final version.

Reviewer_xoJuOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper considers local differential privacy for quantile estimation. Each user holds some private data and applies an ϵ\epsilon-LDP protocol to the the data where different users need not have the same privacy parameter ϵ\epsilon. Upon receiving these noisy, reports, the goal of the central server is to recover accurate quantiles. I did not understand much else of the paper.

Critical strengths

None

Critical weaknesses

The paper seems to be almost completely AI generated. E.g., only a few paragraphs into the intro, without further ado it starts: Two obstacles prevent a direct substitution of an existing mechanism selector. First, quantile uncertainty transforms the score covariance by unknown density values. Ellipsoid volume aggregates directions through a determinant, whereas maximum interval width depends on individual scales and correlations. A good frequency-estimation channel need not optimize either objective. Second, a private quantile recursion queries thresholds learned from earlier reports. Its score law changes along the trajectory. Calibrating the noise at the true quantiles does not by itself establish coverage for the moving-threshold estimator.

Similarly, the theoretical results section starts The results take kk and ϵ\epsilon as fixed. Assume FF is continuous and strictly increasing on [L,U][L,U], the quantiles are separated and interior, and ff is positive and locally β\beta-H"older at them for 0<β≤10 < \beta \le 1. The three stream sizes diverge, the library has uniformly bounded cardinality and scores, and its covariance eigenvalues stay bounded away from zero and infinity. Pilot and main steps are proportional to (t+s0)−a(t+s_0)^{-a} with max⁡{1/2,1/(1+β)}<a<1\max\{1/2,1/(1+\beta)\} < a < 1; density bandwidths satisfy hn→0h_n \to 0 and n2hn2→∞n_2h_n^2 \to \infty. These conditions, including bandwidth clipping, are stated precisely in assumptions C.2 to C.4.

My human brain find this stuff quite non-sensical.

The paper has not technical overview

Questions for authors

No questions.

3 comments
AuthorsOpenReview ↗

Response to Reviewer xoJu

Thank you for your time and valuable comments.

W1. We estimate a vector of population quantiles and a confidence set covering the whole vector. All users have the same public privacy budget. Each user sends one privatized categorical report indicating which interval between the current thresholds contains an observation; the server decodes it into CDF scores and updates all quantiles. For lower and upper quartiles, the target category probabilities are (1/4,1/2,1/4)(1/4,1/2,1/4) for every continuous population. Thus the truth-score law for a specified channel is public. Density factors cancel from ellipsoid-volume ranking, while maximum-width ranking uses an independent private density probe. A pilot first localizes the two quartiles; disjoint probe users estimate their two densities. The server ranks the candidate channels using the public score law and, for maximum width, these density estimates. Fresh users then supply the selected-channel estimates. The conditional online limit connects the moving-threshold estimator to the public reference experiment.

Positive target densities control the conversion from CDF error to quantile error. Local smoothness controls linearization, separated interior quantiles allow projection to become inactive, and uniform library bounds permit approximation for whichever channel is selected. Decreasing steps average score noise; bandwidth conditions balance shrinking probe bias and private estimation noise. Concretely, the targets are separated from each other and from the public boundaries, f(Qj)>0f(Q_j) > 0, and ∣f(x)−f(Qj)∣≤Lj∣x−Qj∣β|f(x)-f(Q_j)|\le L_j|x-Q_j|^\beta locally. The disjoint stage sizes diverge; the final users are independent of the pilot and probes. Density bandwidths satisfy hn→0h_n\to0, n2hn2→∞n_2h_n^2\to\infty and ℓn=o(hn)\ell_n=o(h_n), with truncation limits tending to zero and infinity. Step exponents satisfy max⁡1/2,1/(1+β)<a<1\max\\{1/2,1/(1+\beta)\\} < a < 1, and step constants and offsets are uniformly bounded and fixed before each stage begins.

The submission includes an AI-use statement covering wording and readability, literature-search assistance, code drafting and debugging, and checks of the authors' proof arguments. The authors reviewed and verified AI-assisted material before incorporating it and retain full responsibility for the methodology, proofs, implementation, analysis and conclusions.

Thank you again for your valuable feedback. We hope our responses address your concerns and welcome any further questions or discussion.

I stand by my initial evaluation of the paper

Thank you for taking another look at our response and letting us know your assessment. We appreciate your participation in the discussion and the suggestions you have offered to help improve the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.