Differentially Private Range Queries with Correlated Input Perturbation

Prathamesh Dharangutte, Jie Gao, Ruobin Gong, Guanyang Wang
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:1504-1512, 2025.

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 this Paper

BibTeX
@InProceedings{pmlr-v258-dharangutte25a, 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}, pages = {1504--1512}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/dharangutte25a/dharangutte25a.pdf}, url = {https://proceedings.mlr.press/v258/dharangutte25a.html}, 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.} }
Endnote
%0 Conference Paper %T Differentially Private Range Queries with Correlated Input Perturbation %A Prathamesh Dharangutte %A Jie Gao %A Ruobin Gong %A Guanyang Wang %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-dharangutte25a %I PMLR %P 1504--1512 %U https://proceedings.mlr.press/v258/dharangutte25a.html %V 258 %X 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.
APA
Dharangutte, P., Gao, J., Gong, R. & Wang, G.. (2025). Differentially Private Range Queries with Correlated Input Perturbation. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:1504-1512 Available from https://proceedings.mlr.press/v258/dharangutte25a.html.

Related Material