Accurate and Scalable Matrix Mechanisms via Divide and Conquer
Guanlin He, Yingtai Xiao, Jiamu Bai, Xin Gu, Zeyu Ding, Wenpeng Yin, Daniel Kifer · 2026
Read Accurate and Scalable Matrix Mechanisms via Divide and Conquer by Guanlin He, Yingtai Xiao, Jiamu Bai, Xin Gu, Zeyu Ding, Wenpeng Yin, Daniel Kifer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-00868.txt.
Introduction
He and colleagues present QuerySmasher, a scalable matrix method for unbiased private query answers based on divide and conquer. It splits each query into sub-queries and reassembles the pieces into non-overlapping sub-jobs. These are small, low-dimensional jobs solved on their own in the best way, then stitched back together. QuerySmasher covers ResidualPlanner, ResidualPlanner+, and Weighted Fourier Factorizations, and provably beats them under sum squared error for all workloads.
Catalog record
| CREATOR | Guanlin He, Yingtai Xiao, Jiamu Bai, Xin Gu, Zeyu Ding, Wenpeng Yin, Daniel Kifer |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 122593 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.00868
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Accurate and Scalable Matrix Mechanisms via Divide and Conquer Guanlin He, Yingtai Xiao, Jiamu Bai, Xin Gu, Zeyu Ding, Wenpeng Yin, Daniel Kifer Abstract . 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 subqueries and re-assembles the pieces into mutually orthogonal subworkloads. These subworkloads 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 . 1. Introduction Confidential datasets about individuals and businesses provide a wealth of information that is useful for scientific, economic, and policy purposes. Clearly, they cannot be released without modification and so a variety of perturbed summary statistics are released instead. The fundamental theorem of database reconstruction ( 5 ) demonstrates limits on how many approximate query answers can be released before privacy breaks down under any reasonable notion, and differential privacy ( 8 ; 4 ; 23 ; 6 ) has become a de facto standard for navigating the privacy/utility tradeoff. Although the datasets can be high-dimensional, the queries of interest ( 28 ; 29 ; 27 ) often involve a small set of variables at a time. Hence, the queries of interest can be answered from a collection of data marginals. For example, age range queries for each race can be answered by a 2-way marginal on age and race, 2-d range queries on age and income for each gender can be answered by a 3-way marginal on age, gender, and income, etc. These are examples of linear queries , and they can be answered using a class of differentially private mechanisms known as matrix mechanisms ( 17 ; 36 ; 35 ; 9 ; 19 ; 33 ; 32 ; 15 ) . Given a workload of linear queries, these methods create a set of strategy queries that can be answered with low noise. The original workload queries can then be answered by linear postprocessing of the strategy query answers. This is a powerful framework that has been used in the 2020 Census disclosure avoidance system ( 1 ) and is also a key element of more complex algorithms ( 38 ; 21 ; 39 ; 10 ; 24 ; 22 ) . One of the key challenges of the matrix mechanism line of work is scalability to high-dimensional datasets. If a dataset has attributes {{\color[rgb]{0,0,0}A}}_{1},,\dots,{{\color[rgb]{0,0,0}A}}_{{\color[rgb]{0,0,0}k}} with domains sizes {{\color[rgb]{0,0,0}d}}_{1},\dots,{{\color[rgb]{0,0,0}d}}_{{\color[rgb]{0,0,0}k}} , then optimizing a matrix mechanism to minimize the sum squared error of an arbitrary query workload can be formulated as a semi-definite programming problem with O\left(\left(\prod_{i=1}^{{\color[rgb]{0,0,0}k}}d_{i}\right)^{2}\right) variables ( 35 ) . Solving such an optimization problem is only feasible for low-dimensional datasets that have a small number of attributes. However, most applications require answers to structured query workloads rather than arbitrary workloads. Specifically, each linear query accesses a small number of attributes (different queries can access different attributes) and so the entire workload can be computed using a collection of lower dimensional marginals ( 28 ; 29 ; 27 ) . McKenna et al. ( 19 ) first showed how to scale matrix mechanism construction by exploiting such structure. However, their algorithm still required O\left(\prod_{i=1}^{{\color[rgb]{0,0,0}k}}d_{i}\right) space, which becomes a bottleneck for scalability. A recent line of work called ResidualPlanner (RP) ( 33 ) , ResidualPlanner+ (RP+) ( 32 ) , and Weighted Fourier Factorizations (WFF) ( 15 ) overcame this bottleneck by proposing matrix mechanisms whose time and space complexity scales with the output size (i.e., size of the marginals needed to answer the workload queries) rather than the exponentially sized data domain. This is enabled by special types of linearly independent queries, such as the residual basis ( 33 ) or multidimensional Fourier basis ( 15 ) , that can compactly represent any collection of marginals and therefore they can compactly represent any linear workload that is computable from collections of marginals (such as range queries, prefix-sum queries, etc.). Surprisingly, a proper choice of basis also guarantees optimality (among matrix mechanisms) for expressive classes of queries like marginals ( 33 ) or, more generally, circular product queries ( 15 ) . In this paper, we present QuerySmasher , a novel approach to matrix mechanism scalability that is provably more accurate than this prior work ( 33 ; 32 ; 15 ) under the weighted sum squared error metric. It breaks apart each query into subqueries and groups those pieces into subworkloads. These subworkloads are mutually orthogonal, so that matrix mechanisms for each subworkload can be constructed independently. The subworkloads are also low dimensional, so that optimal low-dimensional techniques ( 35 ) can be used to generate the matrix mechanisms for each subworkload. Afterwards, these matrix mechanisms are combined together to create a mechanism for the original workload. This divide-and-conquer approach ensures scalability. QuerySmasher can also be viewed from an alternate lens of automatically searching for a good workload-dependent compact linear basis that can represent marginals, instead of always using the residual basis ( 33 ) or Fourier basis ( 15 ) . This ensures high accuracy. To summarize, our contributions are the following: • We propose a new matrix mechanism, called QuerySmasher , for computing privacy-preserving answers to any workload of linear queries that are computable from sets of marginals. QuerySmasher uses a novel query decomposition approach to achieve both scalability and high accuracy. • We mathematically prove that QuerySmasher can dominate the scalable compact-linear-basis approaches RP ( 33 ) , RP+ ( 32 ) , and WFF ( 15 ) , in terms of weighted sum squared error, for every workload. Specifically, if the optimal low-dimensional matrix mechanism construction ( 37 ) for each subworkload is replaced by approximate methods, the result becomes mathematically equivalent to RP, RP+, and WFF. • We empirically evaluate QuerySmasher against competing scalable matrix mechanisms ( 33 ; 32 ; 15 ; 19 ) to show that its theoretical accuracy and scalability advantages translate into practice. This paper is organized as follows. In Section 2 , we introduce our notation. In Section 3 we explain background on differential privacy and matrix mechanisms. In Section 4 , we discuss related work. We present an intuitive overview of QuerySmasher in Section 5 and the technical details in Section 6 . In Section 7 , we prove that QuerySmasher dominates RP ( 33 ) , RP+ ( 32 ) , and WFF ( 15 ) , in terms of sum squared error, for