Accurate and Scalable Matrix Mechanisms via Divide and Conquer

Guanlin He; Yingtai Xiao; Jiamu Bai; Xin Gu; Zeyu Ding; Wenpeng Yin; Daniel Kifer

cs.DBApr 1, 2026

Accurate and Scalable Matrix Mechanisms via Divide and Conquer

Authors: Guanlin He, Yingtai Xiao, Jiamu Bai, Xin Gu, Zeyu Ding, Wenpeng Yin, Daniel Kifer

Organizations: Penn State University · TikTok · Binghamton University

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 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.

Figures & tables

${{\color[rgb]{0,0,0}\mathcal{D}}}$ :	Dataset of records $\{{{\color[rgb]{0,0,0}r}}_{1},\dots,{{\color[rgb]{0,0,0}r}}_{{{\color[rgb]{0,0,0}n}}}\}$ .
${{\color[rgb]{0,0,0}n}}$ :	number of records in ${{\color[rgb]{0,0,0}\mathcal{D}}}$
${{\color[rgb]{0,0,0}k}}$ :	The number of attributes in the data schema.
${{\color[rgb]{0,0,0}A}}_{i}$ :	Attribute $i$ of the data schema.
${{\color[rgb]{0,0,0}a}}^{(i)}_{j}$ :	the $j^{\text{th}}$ domain element of attribute ${{\color[rgb]{0,0,0}A}}_{i}$ .
${{\color[rgb]{0,0,0}d}}_{i}$ :	Size of domain of Attribute ${{\color[rgb]{0,0,0}A}}_{i}$ .
${{\color[rgb]{0,0,0}\mathbf{T}}}$ :	Tensor view of the data.

Table 1. Table of Notation

${{\color[rgb]{0,0,0}\mathbf{q}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{\}}:$	. 1/2
${{\color[rgb]{0,0,0}\vec{{{\color[rgb]{0,0,0}\mathbf{q}}}}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{\}}$ :	. 1/2
${{\color[rgb]{0,0,0}\mathbf{q}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{{{\color[rgb]{0,0,0}A}}_{1}\}}:$	. yes 1/6 no -1/6
${{\color[rgb]{0,0,0}\vec{{{\color[rgb]{0,0,0}\mathbf{q}}}}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{{{\color[rgb]{0,0,0}A}}_{1}\}}$ :	. $[1/6,~-1/6]$
${{\color[rgb]{0,0,0}\mathbf{q}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{{{\color[rgb]{0,0,0}A}}_{2}\}}:$	. a b c -1/2 0 1/2
${{\color[rgb]{0,0,0}\vec{{{\color[rgb]{0,0,0}\mathbf{q}}}}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{{{\color[rgb]{0,0,0}A}}_{2}\}}$ :	. $[-1/2,~0,~1/2]$
${{\color[rgb]{0,0,0}\mathbf{q}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{{{\color[rgb]{0,0,0}A}}_{1},{{\color[rgb]{0,0,0}A}}_{2}\}}:$	. a b c yes $-1/6$ $1/3$ $-1/6$ no $1/6$ $-1/3$ $1/6$

Figure 2. The decomposition of

{{\color[rgb]{0,0,0}\mathbf{q}}}

from Figure 1 into the subqueries

{{\color[rgb]{0,0,0}\mathbf{q}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{\}},{{\color[rgb]{0,0,0}\mathbf{q}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{{{\color[rgb]{0,0,0}A}}_{1}\}},{{\color[rgb]{0,0,0}\mathbf{q}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{{{\color[rgb]{0,0,0}A}}_{2}\}},

and

{{\color[rgb]{0,0,0}\mathbf{q}}}_{{{\color[rgb]{0,0,0}\Rightarrow}}\{{{\color[rgb]{0,0,0}A}}_{1},{{\color[rgb]{0,0,0}A}}_{2}\}}

Dataset	Workload	#Queries	RP+	HDMM	WFF	QS
Adult	1-way	588	5.11	5.648	5.804	5.047
	2-way	148,137	17.63	21.111	22.493	17.632
	3-way	20,894,536	47.19	60.025	66.934	47.055
	$\leq$ 3-way	21,043,261	48.90	61.613	66.794	47.853
CPS	1-way	163	3.18	3.347	3.589	3.135
	2-way	7,000	6.36	6.625	7.841	6.194

Table 2. RMSE for hybrid marginal/prefix workloads at privacy cost 1.

Dataset	Workload	#Queries	RP+	HDMM	WFF	QS
CPS	affine	805	10.012	NI	7.147	5.935
	abs_diff	731	10.476	NI	7.387	5.900
Adult	affine	99,830	19.395	NI	21.559	16.435
	abs_diff	99,200	19.441	NI	21.587	16.254
Loans	affine	66,318	18.082	NI	18.671	14.305
	abs_diff	65,682	18.148	NI	18.714	14.330

Table 3. RMSE for 2-way Affine and abs-diff workloads. QuerySmasher improves RMSE by

15-21\%

$n$	Workload	#Queries	RP+	HDMM	WFF	QS
10	marginal	78,400	23.48	23.48 ∗	23.48	23.48
	prefix	78,400	36.23	52.35 ∗	39.70	33.70
	range	2,361,700	48.95	68.98 ∗	41.36	41.08
	circular	7,804,000	NI	NI	39.77	39.77
	affine	15,220	62.48	NI	45.23	28.25
	abs	8,200	85.99	NI	64.11	35.85

Table 4. RMSE of 1-way + 2-way workloads at privacy cost

=1

, for different query types, on a synthetic dataset with

40

attributes (

d=40

) as

n

(domain size of an attribute) varies. NI indicates that competing methods do not have an implementation for the query type. For HDMM, we added a * to indicate that it can estimate its RMSE but will run out of memory when providing workload query answers.

$n$	$d$	RP+	HDMM	WFF	QS
10	10	22.49	NI	25.37	20.41
	20	57.17	NI	65.13	51.63
	30	99.66	NI	113.98	93.50
	40	148.46	NI	170.18	138.38
	50	202.72	NI	232.72	187.24
20	10	36.82	NI	47.04	34.60

Table 5. RMSE on mixed-query workloads of 1-way range queries, 2-way affine queries, 3-way prefix queries at privacy cost 1 as

d

(number of dataset attributes) and

n

(domain size of each attribute) vary.

$n$	$d$	#Views	Decomp	Solve	Assem	Total	Mem
			QuerySmasher Phase Time
10	10	55	${<}$ 0.1s	2.8s	${<}$ 0.1s	2.8s	${<}$ 1 GB
	20	210	${<}$ 0.1s	4.4s	${<}$ 0.1s	4.4s	${<}$ 1 GB
	30	465	${<}$ 0.1s	2.6s	${<}$ 0.1s	2.6s	${<}$ 1 GB
	40	820	0.1s	7.1s	${<}$ 0.1s	7.2s	${<}$ 1 GB
	50	1275	0.2s	9.5s	0.1s	9.7s	${<}$ 1 GB

Table 6. Timing experiments on 1-way + 2-way prefix queries as

d

(number of attributes in the dataset) and

n

(domain size of each attribute) vary. #Views refers to the number of data views that would be needed to answer the queries even in the non-private setting.

			QuerySmasher Phase Time
$n$	$d$	#Views	Decomp	Solve	Assem	Total	Mem
10	10	175	${<}$ 0.1s	4.5s	${<}$ 0.1s	4.6s	0.7 GB
	20	1350	0.5s	28.1s	0.8s	29.4s	1.0 GB
	30	4525	1.2s	25.6s	2.6s	29.4s	2.1 GB
	40	10700	2.7s	43.9s	4.7s	51.3s	4.2 GB
	50	20875	5.5s	88.7s	10.0s	104.2s	7.7 GB

Table 7. Timing experiments on mixed workloads containing all 1-way range queries, all 2-way affine queries, and all 3-way prefix sum queries, as

d

(number of attributes in the dataset) and

n

(domain size of each attribute) vary. #Views refers to the number of data views that would be needed to answer the queries even in the non-private setting.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

$n$	Workload	#Queries	WFF	QS
10	marginal	78,400	39.22	39.22
	prefix	78,400	66.58	56.59
	range	2,361,700	69.25	68.82
	circular	7,804,000	66.70	66.70
	affine	15,220	75.74	47.33
	abs	8,200	107.17	51.94

Appendix

Table 8. WRMSE at privacy cost 1 of weighted 1-way and 2-way marginal workload as

d

(dataset dimensions) and

n

(domain size of each attribute) vary. on

[n]^{40}

, varying domain size

n

. The RP+ and HDMM implementations do not support these queries.

Differential Privacy

Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.

See all 278 papers

The Fast Mixing Mechanism for Differential Privacy
May 28, 2026Omri Lev, Moshe Shenfeld, Vishwak Srinivasan +2Randomized Sketching Differential Privacy
Massachusetts Institute of Technology · The Hebrew University of Jerusalem
Shuffling-Aware Optimization for Private Vector Mean Estimation
Apr 30, 2026Shun Takagi, Seng Pei LiewDifferential Privacy Privacy-Utility Tradeoff
LY Corporation, Tokyo, Japan
Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy
May 27, 2026Huikang Liu, Aras Selvi, Wolfram WiesemannDifferential Privacy
1Shanghai Jiao Tong University · 2UCL School of Management · 3Imperial Business School

May 28, 2026J/K move · Enter open · S save

The Fast Mixing Mechanism for Differential Privacy

Omri Lev, Moshe Shenfeld, Vishwak Srinivasan, Katrina Ligett+1

Massachusetts Institute of Technology · The Hebrew University of Jerusalem

Randomized Sketching Differential Privacy

Open paper AskPDF arXiv

Randomized sketching is a central tool for compressing large-scale optimization problems while preserving accuracy. In particular, sketches that are based on structured matrices, such as the Hadamard matrix, can be applied efficiently and often yield solutions that approximate those of the original problem at much lower computational cost. In differential privacy (DP), Gaussian sketching has been used to solve DP linear regression, beginning with \citet{sheffet2017differentially, sheffet2019old} and later refined by \citet{lev2025gaussianmix, lev2026near}. However, although these methods achieve strong utility guarantees, they usually do not improve runtime over classical DP approaches. In this work, we introduce a new DP sketching mechanism based on fast transforms, which, in certain cases, matches the runtime of classical fast sketching methods. We prove state-of-the-art privacy guarantees for this mechanism and show that, in favorable regimes, they match those of the Gaussian sketch up to a constant factor. As an application, we combine this mechanism with recent sketch-based methods for DP linear regression to obtain a new algorithm with strong utility and improved runtime. We establish privacy and accuracy guarantees for this algorithm, yielding, to the best of our knowledge, the first fast method for DP ordinary least squares.

Abstract

Differential Privacy

Explore similar work

The Fast Mixing Mechanism for Differential Privacy

Shuffling-Aware Optimization for Private Vector Mean Estimation

Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy