Accurate and Scalable Matrix Mechanisms via Divide and Conquer
This work addresses the challenge of scalable and accurate privacy-preserving data analysis for statisticians and data scientists, representing an incremental improvement over existing matrix mechanisms.
The paper tackles the problem of providing unbiased differentially private query answers for high-dimensional datasets by introducing QuerySmasher, a scalable divide-and-conquer approach that splits queries into orthogonal sub-workloads for independent optimization, and it demonstrates dominance over prior methods like ResidualPlanner and Weighted Fourier Factorizations under sum squared error.
Matrix mechanisms are often used to provide unbiased differentially private query answers when publishing statistics or creating synthetic data. Recent work has developed matrix mechanisms, such as ResidualPlanner and Weighted Fourier Factorizations, that scale to high dimensional datasets while providing optimality guarantees for workloads such as marginals and circular product queries. They operate by adding noise to a linearly independent set of queries that can compactly represent the desired workloads. In this paper, we present QuerySmasher, an alternative scalable approach based on a divide-and-conquer strategy. Given a workload that can be answered from various data marginals, QuerySmasher splits each query into sub-queries and re-assembles the pieces into mutually orthogonal sub-workloads. These sub-workloads represent small, low-dimensional problems that can be independently and optimally answered by existing low-dimensional matrix mechanisms. QuerySmasher then stitches these solutions together to answer queries in the original workload. We show that QuerySmasher subsumes prior work, like ResidualPlanner (RP), ResidualPlanner+ (RP+), and Weighted Fourier Factorizations (WFF). We prove that it can dominate those approaches, under sum squared error, for all workloads. We also experimentally demonstrate the scalability and accuracy of QuerySmasher.