Search papers, labs, and topics across Lattice.
This paper introduces QuerySmasher, a novel divide-and-conquer approach for differentially private matrix mechanisms that decomposes complex queries into orthogonal sub-workloads. By independently and optimally answering these low-dimensional sub-problems with existing mechanisms and then stitching the solutions together, QuerySmasher achieves scalability and accuracy improvements. The authors theoretically prove and empirically demonstrate that QuerySmasher subsumes and dominates prior state-of-the-art methods like ResidualPlanner and Weighted Fourier Factorizations in terms of sum squared error.
QuerySmasher shatters the accuracy barrier for differentially private data release, outperforming existing methods by strategically decomposing complex queries into manageable, orthogonal sub-problems.
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.
