On the Limits of Sparse Linear Model with Shuffled Differential Privacy

Yan Zhang; Jiong Tuo; Meng Ding; Yuheng Ma; Di Wang

cs.LGOct 23, 2026

On the Limits of Sparse Linear Model with Shuffled Differential Privacy

Authors: Yan Zhang, Jiong Tuo, Meng Ding, Yuheng Ma, Di Wang

Organizations: Provable Responsible AI and Data Analytics Lab · Nankai University · King Abdullah University of Science and Technology (KAUST) · Xi’an Jiaotong University ·

Abstract

Sparse linear regression is a fundamental problem in high-dimensional statistics, and its private counterparts leave a large gap between the central and the local model of differential privacy. Shuffled differential privacy (SDP) sits between the two, offering accuracy closer to the central model without the trust requirement of a central curator. This paper studies sparse linear regression under both non-interactive and interactive SDP protocols. In the non-interactive setting, any non-interactive $(ε,δ)$ -SDP protocol is shown to incur an $\ell_2$ -norm estimation error of $Ω( \frac{\sqrt{dk}}{nε} )$ with dimension $d$ , sparsity $k$ , and $n$ users, revealing an inherent dimensionality barrier. In addition, a non-interactive algorithm is proposed that achieves an $\ell_2$ -norm upper bound of $\tilde{\mathcal{O}}( \sqrt{\frac{k}{n}} + \frac{d\sqrt{k}}{nε})$ . To overcome this barrier, we turn to the interactive user-level setting, where each user holds $m$ samples. A two-round interactive algorithm is developed that first recovers the support through a heavy hitter step and then estimates the parameter, achieving an error of $\tilde{\mathcal{O}}( \sqrt{\frac{k}{nm}} + \frac{k}{n\sqrt{m}ε} )$ with no polynomial dependence on $d$ . Furthermore, by extending the score attack framework to user-level data, a new lower bound $Ω( \sqrt{\frac{k\log(d/k)}{nm}} + \frac{k\log(d/k)}{n\sqrt{m}ε} )$ is established for any user-level $(ε,δ)$ -DP, showing that the proposed algorithm is near-optimal with only a gap of the factor $\log(d/k)$ .

Figures & tables

Model	Type	Unit	Setting	Upper Bound	Lower Bound	Source
Central	-	sample	general	$\tilde{\mathcal{O}}(\sqrt{\frac{d}{n}}+\frac{d}{n\epsilon})$	$\Omega(\sqrt{\frac{d}{n}}+\frac{d}{n\epsilon})$	Cai et al. (2021)
Central	-	sample	k-sparse	$\tilde{\mathcal{O}}(\sqrt{\frac{k}{n}}+\frac{k}{n\epsilon})$	$\Omega(\sqrt{\frac{k\log d}{n}}+\frac{k\log d}{n\epsilon})$	Cai et al. (2021)
Local	Non-interactive	sample	k-sparse	$\tilde{\mathcal{O}}(\frac{d\sqrt{k}}{\sqrt{n}\epsilon})$	$\Omega(\sqrt{\frac{dk\log d}{n\epsilon^{2}}})$	Zhu et al. (2024a)
	Interactive	sample	k-sparse	$\tilde{\mathcal{O}}(\frac{k\sqrt{d}}{\sqrt{n}\epsilon})$	$\Omega(\sqrt{\frac{dk}{n\epsilon^{2}}})$	Zhu et al. (2024a)
	Interactive	user-level	k-sparse	$\tilde{\mathcal{O}}(\sqrt{\frac{k}{nm}}+\frac{k}{\sqrt{nm}\epsilon})$	$\Omega(\frac{k}{\sqrt{nm}\epsilon})$	Ma et al. (2024)
Shuffle	Non-interactive	sample	k-sparse	$\tilde{\mathcal{O}}(\sqrt{\frac{k}{n}}+\frac{d\sqrt{k}}{n\epsilon})$	$\Omega(\frac{\sqrt{dk}}{n\epsilon})$	Our Work

Table 1: Comparison summary of our work with related studies on

(\epsilon,\delta)

-DP linear regression under sub-Gaussian data assumptions. Here

n

m

k

, and

d

denote the number of users, samples per user, sparsity, and dimension. Note that we can regard

m=1

when the privacy unit is sample . All bounds are measured by the

\ell_{2}

-norm estimation error. The

\tilde{\mathcal{O}}

notation suppresses polylogarithmic factors. The full table can be seen in the Appendix A .

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Type	Unit	Setting	Upper Bound	Lower Bound	Source
Central DP
-	sample	general	$\tilde{\mathcal{O}}(\sqrt{\frac{d}{n}}+\frac{d}{n\epsilon})$	$\Omega(\sqrt{\frac{d}{n}}+\frac{d}{n\epsilon})$	Cai et al. (2021)
-	sample	k-sparse	$\tilde{\mathcal{O}}(\sqrt{\frac{k}{n}}+\frac{k}{n\epsilon})$	$\Omega(\sqrt{\frac{k\log d}{n}}+\frac{k\log d}{n\epsilon})$	Cai et al. (2021)
Local DP
Non-interactive	sample	1-sparse	-	$\Omega(\sqrt{\frac{d\log d}{n\epsilon^{2}}})$	Wang & Xu (2020)
Non-interactive	sample	k-sparse	$\tilde{\mathcal{O}}(\frac{d\sqrt{k}}{\sqrt{n}\epsilon})$	$\Omega(\sqrt{\frac{dk\log d}{n\epsilon^{2}}})$	Zhu et al. (2024a)

Appendix

Table 2: Detailed comparison of related studies on

(\epsilon,\delta)

-DP linear regression. Data assumptions and parameter definitions are identical to Table 1 .

Symbol	Setting	Role
$C_{F}$	$c_{0}\,d\log n$	$\ell_{2}$ clipping radius
$p$	$\Big\lceil\dfrac{\sqrt{n}\,\epsilon}{d\log n\sqrt{\log(4D/\delta)}}\Big\rceil$	rounding precision
$\Delta_{2}^{(p)}$	$2pC_{F}+\sqrt{D}$	$\ell_{2}$ sensitivity of the integer query
$M$	$\Big\lceil\dfrac{32(\Delta_{2}^{(p)})^{2}\log(4D/\delta)}{\epsilon^{2}}\Big\rceil$	total binomial parameter
$N_{0}$	$2\lceil M/(2n)\rceil$	binomial parameter per user and coordinate
$q$	$4n(pC_{F}+N_{0})$	modulus of the group $\mathbb{Z}_{q}$

Appendix

Table 3: Parameters of Algorithm 2 , used in Theorem 2 .

Symbol	Setting	Role
$\lambda_{\mathrm{loc}}$	$c_{\lambda}\,\sigma\sqrt{\dfrac{\log d}{m}}$ , with $\lambda_{\mathrm{loc}}\leq\dfrac{\kappa\rho}{16\sqrt{k}}$	regularization parameter of the local Lasso
$\rho/2$	—	threshold of the local selection step
$\gamma$	$\dfrac{C_{\gamma}\log(1/\delta)}{n_{1}\epsilon^{2}}$	flipping probability of the randomized response
$\tau_{HH}$	$\dfrac{n_{1}}{4k}$	threshold on the debiased counts

Appendix

Table 4: Parameters of Algorithm 3 , used in Proposition 1 .

Symbol	Setting	Role
$\tau_{\beta}$	$C_{\beta}\,\sigma\sqrt{\dfrac{s\log n}{m}}$	uniform bound on $\\|\tilde{\theta}_{i}-\theta^{*}_{\hat{S}}\\|_{2}$
$R_{0}$	$B_{\theta}+\tau_{\beta}$	clipping radius of Stage 2a
$\hat{A}$	$c_{A}\,\sigma\sqrt{\dfrac{s\log n}{n_{3}m}}+c_{A}^{\prime}\,\dfrac{R_{0}\sqrt{s\log n\log(4s/\delta)}}{n_{3}\epsilon}$	error bound of the coarse estimate $c$
$\tau$	$\tau_{\beta}+\hat{A}$	clipping radius of Stage 2b
$p_{g}$	$\max\Big\{\dfrac{c_{p}\sqrt{n_{g}\log n}\,\epsilon}{R_{g}\sqrt{\log(1/\delta)}},\;\dfrac{(\sqrt{s}+2)\max\{1,\epsilon\}}{R_{g}}\Big\}$	rounding precision
$\Delta_{g}$	$2p_{g}R_{g}+\max\{1,\epsilon\}\sqrt{s}+2$	$\ell_{2}$ sensitivity of the integer query; $\Delta_{g}\leq 3p_{g}R_{g}$

Appendix

Table 5: Parameters of Algorithm 4 , used in Theorem 3 . The index

g\in\{a,b\}

refers to Stage 2a and Stage 2b, with

(n_{a},R_{a})=(n_{3},R_{0})

and

(n_{b},R_{b})=(n_{4},\tau)

Figure 1: Relative coefficient error versus

\epsilon

in the left, and

n

in the right, with default

n=15000

m=50

d=256

k=8

and

\epsilon=4

. Lines show means over 30 repetitions; shaded bands span the empirical 95% coverage of 2.5th–97.5th percentiles.

$d$	U2R	2-SLR	LDP-IHT	Sample-SDP	Lasso
64	$0.00643$	$0.49079$	$0.13262$	$0.01849$	$0.00450$
128	$0.00659$	$0.61461$	$0.12595$	$0.03571$	$0.00453$
256	$0.00553$	$0.64914$	$0.13354$	$0.07027$	$0.00520$
512	$0.00598$	$0.77533$	$0.18692$	$0.14111$	$0.00522$

Appendix

Table 6: Exp3: relative coefficient error versus dimension at

n=15000

m=50

, and

\epsilon=4

. Entries are means over ten repetitions.

Budget	$m$	U2R	2-SLR	LDP-IHT	Sample-SDP
	$10$	$1.48261$ $\pm 0.04759$	$11.21592$ $\pm 10.06853$	$3.15212$ $\pm 0.72151$	$3.14939$ $\pm 0.36992$
$\epsilon=1$	$50$	$1.17245$ $\pm 0.02983$	$3.08118$ $\pm 1.14883$	$2.36752$ $\pm 0.39188$	$1.91000$ $\pm 0.31047$
	$100$	$1.12978$ $\pm 0.02725$	$3.23649$ $\pm 1.62979$	$2.25214$ $\pm 0.45721$	$1.50741$ $\pm 0.12895$
	$10$	$1.43505$ $\pm 0.01006$	$3.07791$ $\pm 1.29223$	$2.44676$ $\pm 0.59026$	$2.05930$ $\pm 0.36280$
$\epsilon=4$	$50$	$1.15861$ $\pm 0.02794$	$2.08907$ $\pm 0.16864$	$2.36333$ $\pm 0.41893$	$1.48151$ $\pm 0.27440$
	$100$	$1.13213$ $\pm 0.00306$	$2.19689$ $\pm 0.26004$	$2.32449$ $\pm 0.33028$	$1.37230$ $\pm 0.12374$

Appendix

Table 7: Exp5: Kelmarsh test MSE divided by the paired non-private Lasso MSE at

n=10000

and

d=90

. U2R and Sample-SDP use

\delta=10^{-5}

. Entries are mean

\pm

sample standard deviation over ten repetitions.

Exp4a: vary $m$ ; $n=15000$ , $d=256$ , $\epsilon=4$
Value	U2R recall in %	2-SLR recall in %	U2R exact	2-SLR exact
25	$3.75\pm 8.44$	$26.25\pm 13.76$	0/10	0/10
50	$100.00\pm 0.00$	$63.75\pm 12.43$	10/10	0/10
75	$100.00\pm 0.00$	$72.50\pm 16.46$	10/10	1/10
100	$100.00\pm 0.00$	$76.25\pm 12.43$	10/10	0/10
Exp4b: vary $n$ ; $m=50$ , $d=256$ , $\epsilon=4$

Appendix

Table 8: Exp4: Stage 1 support recall and exact recovery. Recall entries are mean

\pm

sample standard deviation in percentage points; exact recovery is the number of repetitions with

\hat{S}=S^{*}

out of ten.

Budget	$m$	U2R	2-SLR	LDP-IHT	Sample-SDP	Lasso
	$10$	$3.55270$ $\pm 0.11390$	$26.89088$ $\pm 24.15804$	$7.55337$ $\pm 1.72935$	$7.54559$ $\pm 0.87616$	$2.39625$ $\pm 0.00376$
$\epsilon=1$	$50$	$2.80885$ $\pm 0.07139$	$7.38104$ $\pm 2.75047$	$5.67181$ $\pm 0.93834$	$4.57575$ $\pm 0.74360$	$2.39572$ $\pm 0.00123$
	$100$	$2.70655$ $\pm 0.06479$	$7.75405$ $\pm 3.90559$	$5.39543$ $\pm 1.09591$	$3.61122$ $\pm 0.30899$	$2.39565$ $\pm 0.00063$
	$10$	$3.43873$ $\pm 0.02432$	$7.37791$ $\pm 3.10457$	$5.86216$ $\pm 1.40887$	$4.93425$ $\pm 0.86685$	$2.39625$ $\pm 0.00376$
$\epsilon=4$	$50$	$2.77572$ $\pm 0.06713$	$5.00484$ $\pm 0.40439$	$5.66193$ $\pm 1.00425$	$3.54916$ $\pm 0.65645$	$2.39572$ $\pm 0.00123$
	$100$	$2.71218$ $\pm 0.00678$	$5.26299$ $\pm 0.62298$	$5.56877$ $\pm 0.79226$	$3.28753$ $\pm 0.29627$	$2.39565$ $\pm 0.00063$

Appendix

Table 9: Exp5: Kelmarsh test MSE in squared degrees Celsius. U2R and Sample-SDP use

\delta=10^{-5}

. Entries are mean

\pm

sample standard deviation over ten repetitions; Lasso is reused across budgets.

High-Dimensional Linear Regression

See all 19 papers

Refined Differentially Private Linear Regression via Extension of a Free Lunch Result
Apr 11, 2026Sasmita Harini S, Anshoo TandonDifferential Privacy Linear Regression
Indian Institute of Science, Bangalore, India · CDPG, Indian Institute of Science, Bangalore, India
New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression
Oct 8, 2026Xiaofeng Cao, Junfan Li, Langzhang Liang +2Linear Regression Minimax Regret
School of Computer Science and Technology, Tongji University, Shanghai, China · School of Computing and Artificial Intelligence, Shanghai University of Finance and Economics, Shanghai, China · AI3 Institute, Fudan University and Shanghai Innovation Institute +2
Privacy-Accuracy Trade-offs in High-Dimensional LASSO under Perturbation Mechanisms
Mar 27, 2026Ayaka Sakata, Haruka TanzawaApproximate Message Passing Privacy-Preserving ML
Department of Information Science, Ochanomizu University · RIKEN center for AIP

Apr 11, 2026J/K move · Enter open · S save

Refined Differentially Private Linear Regression via Extension of a Free Lunch Result

Sasmita Harini S, Anshoo Tandon

Indian Institute of Science, Bangalore, India · CDPG, Indian Institute of Science, Bangalore, India

Differential Privacy Linear Regression

Open paper AskPDF arXiv

As data-privacy regulations tighten and statistical models are increasingly deployed on sensitive human-sourced data, privacy-preserving linear regression has become a critical necessity. For the add-remove DP model, Kulesza et al. (2024) and Fitzsimons et al. (2024) have independently shown that the size of the dataset -- an important statistic for linear regression -- can be privately estimated for "free", via a simplex transformation of bounded variables and private sum queries on the transformed variables. In this work, we extend this free lunch result via carefully crafted multidimensional simplex transformations to variables and functions that are bounded in the interval [0,1]. We show that these transformations can be applied to refine the estimates of sufficient statistics needed for private simple linear regression based on ordinary least squares. We provide both analytical and numerical results to demonstrate the superiority of our approach. Our proposed transformations have general applicability and can be readily adapted for differentially private polynomial regression.

Abstract

High-Dimensional Linear Regression

Explore similar work

Refined Differentially Private Linear Regression via Extension of a Free Lunch Result

New Lower Bound and Upper Bounds on the Regret for Online Sparse Linear Regression

Privacy-Accuracy Trade-offs in High-Dimensional LASSO under Perturbation Mechanisms