---
title: "Algorithms"
output: rmarkdown::html_vignette
vignette: >
%\VignetteIndexEntry{Algorithms}
%\VignetteEngine{knitr::rmarkdown}
%\VignetteEncoding{UTF-8}
---
```{r, include = FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
comment = "#>"
)
```
This page collects the algorithms used in the `dppca` package.
## Algorithm 1: Private and robust estimator for \(m_2\) {#alg-m2}
This algorithm constructs a private scale proxy $\widetilde m_{2,\ell}$ for selecting the Huber robustification parameter $\tau_\ell$. Given the paired squared differences $\{w_{r\ell}\}_{r=1}^{m}$, it forms additional pairwise half squared differences and computes block medians to obtain a robust measure of variability. A private histogram over dyadic scales is then used to select the final scale proxy.
{width=95%}
## Algorithm 2: Unbounded DP upper-quantile estimator {#alg-unbounded-quantile}
This one-sided algorithm is the building block for the score-frame and PMWM
quantile estimates. Following [Durfee (2023)](#ref-Durfee2023), it searches a
geometric grid using noisy comparisons against the empirical CDF. The fully
unbounded mechanism invokes the one-sided search in both the positive and
sign-flipped directions.
For a one-sided quantile release with total budget $\varepsilon_Q$, the implementation uses $\varepsilon_1=\varepsilon_2=\varepsilon_Q/2$ for the noisy target and query counts. It accepts $0
Durfee, D. (2023). Unbounded differentially private quantile and maximum
estimation. In *Advances in Neural Information Processing Systems*, 36,
77691--77712.
Vishesh Karwa and Salil Vadhan. (2018). "Finite sample differentially private confidence intervals". In Proceedings of ITCS 2018, LIPIcs, 94, 44:1--44:9. https://doi.org/10.4230/LIPIcs.ITCS.2018.44
Wasserman, L. and Zhou, S. (2010). A statistical framework for differential
privacy. *Journal of the American Statistical Association*, 105(489), 375--389.
https://doi.org/10.1198/jasa.2009.tm08651
Yu, M., Ren, Z., and Zhou, W.-X. (2024). Gaussian differentially private robust
mean estimation and inference. *Bernoulli*, 30(4), 3059--3088.
https://doi.org/10.3150/23-BEJ1706
.