Differentially Private Range Queries with Correlated Input Perturbation
Abstract
This work proposes a class of differentially private mechanisms for linear queries, in particular range queries, that leverages correlated input perturbation to simultaneously achieve unbiasedness, consistency, statistical transparency, and control over utility requirements in terms of accuracy targets expressed either in certain query margins or as implied by the hierarchical database structure. The proposed Cascade Sampling algorithm instantiates the mechanism exactly and efficiently. Our theoretical and empirical analysis demonstrates that we achieve near-optimal utility, effectively compete with other methods, and retain all the favorable statistical properties discussed earlier.
Cite
Text
Dharangutte et al. "Differentially Private Range Queries with Correlated Input Perturbation." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.Markdown
[Dharangutte et al. "Differentially Private Range Queries with Correlated Input Perturbation." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.](https://mlanthology.org/aistats/2025/dharangutte2025aistats-differentially/)BibTeX
@inproceedings{dharangutte2025aistats-differentially,
title = {{Differentially Private Range Queries with Correlated Input Perturbation}},
author = {Dharangutte, Prathamesh and Gao, Jie and Gong, Ruobin and Wang, Guanyang},
booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics},
year = {2025},
pages = {1504-1512},
volume = {258},
url = {https://mlanthology.org/aistats/2025/dharangutte2025aistats-differentially/}
}