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 276 papers

May 28, 2026

The Fast Mixing Mechanism for Differential Privacy

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.

Omri Lev, Moshe Shenfeld, Vishwak Srinivasan +2

Massachusetts Institute of Technology · The Hebrew University of Jerusalem

Randomized Sketching Differential Privacy

Ask PDF

Apr 30, 2026

Shuffling-Aware Optimization for Private Vector Mean Estimation

We study

d

-dimensional unbiased mean estimation in the single-message shuffle model, where each user sends a single privatized message and the analyzer only observes the shuffled multiset of reports. While minimax-optimal mechanisms are well understood in the local differential privacy setting, the corresponding notion of optimality after shuffling has remained largely unexplored. To address this gap, we introduce the recently proposed shuffle index and use it to formulate the post-shuffling mechanism design problem as an explicit optimization problem. We then establish a minimax lower bound on the achievable mean squared error in terms of the shuffle index, which implies that mechanisms that are optimal under LDP can become suboptimal once shuffling is applied. Finally, we construct an asymptotically minimax optimal mechanism in the high privacy regime, which as a consequence achieves a privacy-utility trade-off nearly identical to that of the central Gaussian mechanism.

Shun Takagi, Seng Pei Liew

LY Corporation, Tokyo, Japan

Differential Privacy Privacy-Utility Tradeoff

Ask PDF

May 27, 2026

Mind the Gap: Mixtures of Gaussians in Approximate Differential Privacy

We design a class of additive noise mechanisms that satisfy

(\varepsilon, δ)

-differential privacy (DP) for scalar, real-valued query functions with known sensitivities, with a particular focus on moderate and low-privacy regimes. These mechanisms, which we call mixture mechanisms, are constructed by mixing multiple Gaussian distributions that share the same variance but differ in their means and mixture weights. The resulting distributions can be interpreted as convex combinations of a zero-mean Gaussian (as used in the analytic Gaussian mechanism) and additional Gaussians whose means depend on the sensitivity of the query function. We derive tight conditions on the variances required for

(\varepsilon, δ)

-DP and provide efficient algorithms to compute them. Compared to the analytic Gaussian mechanism, our mechanisms yield substantially lower expected noise amplitudes (

l_1

-loss) and variances (

l_2

-loss for zero-mean distributions). In the low-privacy regime that motivates our design, our mechanisms approach optimality, mitigating nearly all of the optimality gap of the analytic Gaussian mechanism.

Huikang Liu, Aras Selvi, Wolfram Wiesemann

1Shanghai Jiao Tong University · 2UCL School of Management · 3Imperial Business School

Differential Privacy

Ask PDF

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