--- 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. ![Algorithm 1: Private and robust estimator for \(m_2\)](figures/alg2-robust_estimator_for_m2.png){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 .