Fast Private Adaptive Query Answering for Large Data Domains

Miguel Fuentes, Brett Mullins, Yingtai Xiao, Daniel Kifer, Cameron N Musco, Daniel Sheldon
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:3790-3798, 2026.

Abstract

Privately releasing marginals of a tabular dataset is a foundational problem in differential privacy. However, state-of-the-art mechanisms suffer from a computational bottleneck when marginal estimates are reconstructed from noisy measurements. Recently, residual queries were introduced and shown to lead to highly efficient reconstruction in the batch query answering setting. We introduce new techniques to integrate residual queries into state-of-the-art adaptive mechanisms such as AIM. Our contributions include a novel conceptual framework for residual queries using multi-dimensional arrays, lazy updating strategies, and adaptive optimization of the per-round privacy budget allocation. Together these contributions reduce error, improve speed, and simplify residual query operations. We integrate these innovations into a new mechanism (AIM+GReM), which improves AIM by using fast residual-based reconstruction instead of a graphical model approach. Our mechanism is orders of magnitude faster than the original framework and demonstrates competitive error and greatly improved scalability.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-fuentes26a, title = { Fast Private Adaptive Query Answering for Large Data Domains }, author = {Fuentes, Miguel and Mullins, Brett and Xiao, Yingtai and Kifer, Daniel and Musco, Cameron N and Sheldon, Daniel}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {3790--3798}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/fuentes26a/fuentes26a.pdf}, url = {https://proceedings.mlr.press/v300/fuentes26a.html}, abstract = { Privately releasing marginals of a tabular dataset is a foundational problem in differential privacy. However, state-of-the-art mechanisms suffer from a computational bottleneck when marginal estimates are reconstructed from noisy measurements. Recently, residual queries were introduced and shown to lead to highly efficient reconstruction in the batch query answering setting. We introduce new techniques to integrate residual queries into state-of-the-art adaptive mechanisms such as AIM. Our contributions include a novel conceptual framework for residual queries using multi-dimensional arrays, lazy updating strategies, and adaptive optimization of the per-round privacy budget allocation. Together these contributions reduce error, improve speed, and simplify residual query operations. We integrate these innovations into a new mechanism (AIM+GReM), which improves AIM by using fast residual-based reconstruction instead of a graphical model approach. Our mechanism is orders of magnitude faster than the original framework and demonstrates competitive error and greatly improved scalability. } }
Endnote
%0 Conference Paper %T Fast Private Adaptive Query Answering for Large Data Domains %A Miguel Fuentes %A Brett Mullins %A Yingtai Xiao %A Daniel Kifer %A Cameron N Musco %A Daniel Sheldon %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-fuentes26a %I PMLR %P 3790--3798 %U https://proceedings.mlr.press/v300/fuentes26a.html %V 300 %X Privately releasing marginals of a tabular dataset is a foundational problem in differential privacy. However, state-of-the-art mechanisms suffer from a computational bottleneck when marginal estimates are reconstructed from noisy measurements. Recently, residual queries were introduced and shown to lead to highly efficient reconstruction in the batch query answering setting. We introduce new techniques to integrate residual queries into state-of-the-art adaptive mechanisms such as AIM. Our contributions include a novel conceptual framework for residual queries using multi-dimensional arrays, lazy updating strategies, and adaptive optimization of the per-round privacy budget allocation. Together these contributions reduce error, improve speed, and simplify residual query operations. We integrate these innovations into a new mechanism (AIM+GReM), which improves AIM by using fast residual-based reconstruction instead of a graphical model approach. Our mechanism is orders of magnitude faster than the original framework and demonstrates competitive error and greatly improved scalability.
APA
Fuentes, M., Mullins, B., Xiao, Y., Kifer, D., Musco, C.N. & Sheldon, D.. (2026). Fast Private Adaptive Query Answering for Large Data Domains . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:3790-3798 Available from https://proceedings.mlr.press/v300/fuentes26a.html.

Related Material