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

Apr 11, 2026

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

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.

Sasmita Harini S, Anshoo Tandon

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

Differential Privacy Linear Regression

Ask PDF

Oct 8, 2026

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

We study online sparse linear regression (OSLR) where any algorithm is restricted to accessing only

b

out of

d

attributes per instance for prediction and

b_0\geq 0

additional attributes after prediction, which was proved to be NP-hard. Previous work focused on designing computationally efficient algorithms under regularity assumptions, but did not characterize its information theoretic complexity. In this work, we give the first lower bound on the minimax regret of OSLR and design algorithms with better upper bounds without regularity assumptions. We characterize how minimax regret scales with problem-dependent parameters, capturing the information theoretic complexity of OSLR.

Xiaofeng Cao, Junfan Li, Langzhang Liang +2

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

Linear Regression Minimax Regret Information-Theoretic Lower Bounds

Ask PDF

Mar 27, 2026

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

We study privacy-preserving sparse linear regression in the high-dimensional regime, focusing on the LASSO estimator. We analyze two widely used mechanisms for differential privacy: output perturbation, which injects noise into the estimator, and objective perturbation, which adds a random linear term to the loss function. Using approximate message passing (AMP), we characterize the typical behavior of these estimators under random design and privacy noise. To quantify privacy, we adopt typical-case measures, including the on-average KL divergence, which admits a hypothesis-testing interpretation in terms of distinguishability between neighboring datasets. Our analysis reveals that sparsity plays a central role in shaping the privacy-accuracy trade-off: stronger regularization can improve privacy by stabilizing the estimator against single-point data changes. We further show that the two mechanisms exhibit qualitatively different behaviors. In particular, for objective perturbation, increasing the noise level can have non-monotonic effects, and excessive noise may destabilize the estimator, leading to increased sensitivity to data perturbations. Our results demonstrate that AMP provides a powerful framework for analyzing privacy-accuracy trade-offs in high-dimensional sparse models.

Ayaka Sakata, Haruka Tanzawa

Department of Information Science, Ochanomizu University · RIKEN center for AIP

Approximate Message Passing Privacy-Preserving ML Differential Privacy

Ask PDF

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