[2305.08175] ResidualPlanner+: a scalable matrix mechanism for marginals and beyond

Computer Science > Databases arXiv:2305.08175 (cs) [Submitted on 14 May 2023 (v1), last revised 3 Apr 2026 (this version, v4)] Title:ResidualPlanner+: a scalable matrix mechanism for marginals and beyond Authors:Yingtai Xiao, Guanlin He, Levent Toksoz, Zeyu Ding, Danfeng Zhang, Daniel Kifer View a PDF of the paper titled ResidualPlanner+: a scalable matrix mechanism for marginals and beyond, by Yingtai Xiao and 5 other authors View PDF HTML (experimental) Abstract:Noisy marginals are a common form of confidentiality protecting data release and are useful for many downstream tasks such as contingency table analysis, construction of Bayesian networks, and even synthetic data generation. Privacy mechanisms that provide unbiased noisy answers to linear queries (such as marginals) are known as matrix mechanisms. We propose ResidualPlanner and ResidualPlanner+, two highly scalable matrix mechanisms. ResidualPlanner is both optimal and scalable for answering marginal queries with Gaussian noise, while ResidualPlanner+ provides support for more general workloads, such as combinations of marginals and range queries or prefix-sum queries. ResidualPlanner can optimize for many loss functions that can be written as a convex function of marginal variances (prior work was restricted to just one predefined objective function). ResidualPlanner can optimize the accuracy of marginals in large scale settings in seconds, even when the previous state of the art (HDMM) runs out of memory. It ev...