Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model
Authors: Liyang Zhu
Meng Ding
Vaneet Aggarwal
Jinhui Xu
Di Wang
Venue: ICLR 2024 poster (2024)
Keywords: local differential privacy; linear regression
Primary area: societal considerations including fairness, safety, privacy

Abstract: In this paper, we revisit 
the problem of sparse linear regression in the local differential privacy (LDP) model. Existing research in the non-interactive and sequentially local models has focused on obtaining the lower bounds for the case where the underlying parameter is $1$-sparse, and extending such bounds to the more general $k$-sparse case has proven to be challenging. Moreover, it is unclear whether efficient non-interactive LDP (NLDP) algorithms exist. To address these issues, 
we  first consider the problem in the $\epsilon$ non-interactive LDP model and provide a lower bound of $\Omega(\frac{\sqrt{dk\log d}}{\sqrt{n}\epsilon})$ on the $\ell_2$-norm estimation error for sub-Gaussian data, where $n$ is the sample size and $d$ is the dimension of the space. 
We propose an innovative NLDP algorithm, the very first of its kind for the problem. As a remarkable outcome, this algorithm also yields a novel and highly efficient estimator as a valuable by-product. Our algorithm achieves an upper bound of $\tilde{O}({\frac{d\sqrt{k}}{\sqrt{n}\epsilon}})$ for the estimation error when the data is sub-Gaussian, which can be further improved by a factor of  $O(\sqrt{d})$ if the server has additional public but unlabeled data. 
For the sequentially interactive LDP model, we show a similar lower bound of $\Omega({\frac{\sqrt{dk}}{\sqrt{n}\epsilon}})$. As for the upper bound, we rectify a previous method and show that it is possible to achieve a bound of $\tilde{O}(\frac{k\sqrt{d}}{\sqrt{n}\epsilon})$. Our findings reveal fundamental differences between the non-private case, central DP model, and local DP model in the sparse linear regression problem.

Published as a conference paper at ICLR 2024
IMPROVED ANALYSIS OF SPARSE LINEAR REGRESSION IN LOCAL DIFFERENTIAL PRIVACY MODEL
Liyang Zhu - Meng Ding2 Vaneet Aggarwal Jinhui Xu² Di Wang'
PRADD Lab, King Abdullah University of Science and Technology
State University of New York at Buffalo Purdue University
(liyang zhu, di.wang @kaust. edu. sa
(mengding, jinhu @buffaao... edu
@aneet@purruueedd
ABSTRACT
In this paper, we revisit the problem of sparse linear regression in the local differen- tial privacy (LDP) model. Existing research the non-interactive and sequentially local models has focused on obtaining the lower bounds for the case where the underlying parameter 1-sparse, and extending such bounds to the more gen- eral k-sparse case has proven be challenging. Moreover, it is unclear whether efficient non-interee non-interactive LDP (NLDP) algorithms exist. To address these issues, we first consider the problem in the -on-interecttve LDP model and provide a on the f2-norm estimation error for sub-Gaussian data, where n. is the sample size and d is the dimension of the space. We propose an innovative NLDP algorithm, the very first of its kind for the problem. As a remark- able outcome, this algorithm also yields novel and highly efficient estimator as a ddy/ y'me for the
lower bound of 22( yak log
//r
valuable by-product. Our algorithm achieves an upper bound Ö estimation error when the data is sub-Gaussian, which can be further improved by a factor of ((vd)) if the server has additional public but unlabeled data. For the sequentially interactive LDP model, show similar lower bound of 22( Vak As for the upper bound, we rectify a previous method and show that possible achieve a bound of Ó kvd /ne! Our findings reveal fundamental differences between the non-prie non-private case, central DP model, and local DP model in the sparse linear regression problem.
Vile
INTRODUCTION
Protecting data privacy is a major concern in many modern information or database systems. Such systems often contain personal and sensitive information, making it essential preserve privacy when sharing aggregated data. Traditional data analysis techniques such as linear regression often face number of challenges when dealing with sensitive data, especially in social research (Serlin & Marascuilo, 1988 Büžková 2013) Bühlmann & de Geer 2011)). Differential privacy (DP) (Dwork itt al. (206bb has emerged as widely recognized approach for crivacy-preserving which provides verifiable protection against identification and is resistant to arbitrary auxiliary information that attackers may have access to.
Previous research DP has given rise to two primary user models: the central model and the local model. The central model uses a trusted central entity to handle the data, including collecting data, determining which differentially private data analysis to perform, and distributing the results. The central model is commonly used for processing census data. Different from the central model, the local model empowers individuals to control their own data, using differentially private procedures to reveal it to a server. The server then "merges" the private data of each individual into a resultant data analysis. This paradigm exemplified by Google's Chrome browser and Apple's iOS-10, which collect statistics from user devices (Tag et al. 2017 Erlingsson et al. 2014
The local model. despite its widespread application in industry, has received less attention than the central model. This is because there are inherent constraints to what can be done in the local model,
"qqual contributions. Part of the work was done when Meng Ding was research intern at KAUST.

---

Published as a conference paper at ICLR 2024
resulting in many fundamental problems remaining unanswered. Linear regression, fundamental model in both machine learning and statistics, has been extensively studied in recent years in the DP community in two different settings: the (stochastic) optimization and the (statistical) estimation settings. In the former, the aim is to find a private estimator 0 E IR that minimizes the empirical risk L(0, D) Σ ((x2,, 00) yi)2 or population risk (0) = B(x.))>p(((
y) of the 9.) where P is the underlying distribution of (æ; y) with covariate and response y. In the latter, it considers a linear model with covariate x and response y that satisfy y = (ar, 0*) + <. where
given dataset D
zero-mean random noise, and 0" is an underlying parameter. The goal is to find a private estimator (prir that approximates 0" as closely as possible, with the 22-norm estimation error ||@priv - 112 being minimized.
DP linear regression has been extensively studied in the central model, including both the optimization and estimation settings (see the Related Work section A for further details). Recently, researchers have also investigated the problem in the high-dimensions space where the dimensionality is much larger than the sample size. For instance, Talwar al. (2015) focused on the private LASSO problem in the optimization setting, where the underlying constraint set is an E f1-norm ball. In the estimation setting, which involves sparse linear regression where 0* is k-sparse vector with k < d, Cai et al. (2021) Kifer et al. (2012a) considered sub-Gaussian covariates, and this was later expanded by Hu ct al. (202) to include heavy-tailed covariates.
Despite the growing interest in DP linear regression, there is still lack of understanding of the local model compared to the central one. While there have been numerous studies on the optimization setting in the fow-dimensional case (Duchi et al. 2018), less attention has been paid to the statistical estimation setting in the high- -igh-dimensional space. Although Wang & Xu (2021) provided the first study on sparse linear regression in the LDP model, the problem is still far from well-understood in comparison to the non-private and central DP cases. By and large, there are three main challenges that need to be addressed. Firstly, for lower bounds, Wang & Xu (22T) only considered the 1-sparse case and their proof cannot be extended to the general k-sparse case. Thus, there is still no lower bound for the k-sparse case. Secondly, in the non-interactive setting, is unclear whether there exists any efficient algorithm due to the non- non-interactivity constraint and the sparsity nature of the problem. Even for the 1-sparse case, WWang& & Xu (202T) showed only a lower bound. Finally, for the upper bound in the sequentially interactive setting, while Wang & Xu (2021) provided an algorithm, it heavily relies on the assumption that the covariate follows the uniform distribution of [-1, +134, and there are some technical flaws in their analysis (see Section 4.2 for details).
In this paper, we address the three challenges of sparse linear regression in the LDP model that were left by previous research. Specifically, we provide new hard instances of lower bounds, novel self- interested NLDP algorithms, and new proof techniques for lower and upper bounds. Our contributions are three-fold. See Table T in Appendix for comparisons with previous work.
1. In the first part of this paper. we focus on the non-interactive setting. For the k-sparse case, we show that even with 1-sub- u-sub-Gaussian covariates and responses, the output of any e-NLDP algorithm must have estimation error of at least 2i dimension of the space. This lower bound is significantly different from the optimal rates achieved by non-private and central DP algorithms. Moreover, previous results only consider the case where k = and is technically difficult to extend to the general spsare case. Prior to our work, there were no comparable lower bounds. We give non-trivial proofs for lower bounds by constructing hard instances that might be instructive for other related problems.
ne" dk logdd where is the sample size and d is the
2. Then, we consider upper bounding the estimation error for our problem. Due the constraints in the model, there is no previous study. We develop a novel and closed-form estimator for sparse linear regression and propose the first (e, 8) NDDD algorithm. We also give a non-trivial upper bound of
Ō dv/log i when the covariates and responses are sub-Gaussian and n is large enough. Moreover, Vnee
we show that if the server has enough public but unlabeled data, an error bound of Ö( dk log can be achieved. Fianlly, we relax the assumption to the case where the responses only have bounded 2p-moment with some p > 1.
ne
3. In the second part of the paper, we investigate the problem in the sequentially interactive model.
), which is similar to the First, for sub-Gaussian data we establish a lower bound of Ω xe
dk
2

---

Published as a conference paper at ICLR 2024
non-interactive case, but requires different hard instance construction and proof technique. The investigation on upper bound in the interactive setting is still quite deficient. We thus rectify and generalize the private iterative hard thresholding algorithm in Wang & Xu (222)) for sub- Gaussian covariates and responses and demonstrate that the algorithm can only achieve an upper bound of Ö(kva) kvd) rather than Ō vak in Wang & Xu 2021). Vnc
To adhere to space limitations, certain additional sections, including the related work section, along with all omitted proofs, have been included in the Appendix.
PRELIMINARIES
This section introduces the problem setting, local differential privacy, and some notations used throughout this paper. Additional preliminaries can be found in Section D of the Appendix.
Notations. Given matrix X Raxd let x!f be its i-th row and Fij (or {X];)) be its (i,
entry (which is also the j-th element of the vector x;)). For any E oo), || is the p-norm,
[|yylee and || bo,00 maxi, Jragl is the max norm of matrix X. For an event A, we let [[]] denote the indicator, i.e.. /[A] = 1 if A occurs, and [[A] = otherwise. The sign function of real number x is piece- function which is defined sgn(x) -1 if x < 0g x)) = 1 if x > 0: and sgn(r) = 0 if = O. We also use Amin (X) to denote the minimal eigenvalue of X. For sub-Suusee Gaussian random variable X, its uub-Gaussian norm || || is defined as ||l = inffc > 0 : Ejexp(( X² - 2}.
i.., || p supy#0 Tell,
2.1 PROBLEM SETTING
Throughout the paper, we consider the classical setting of sparse linear regression. Suppose that we have a data universe D X' x y S Rd R and users in the population, where each user has feature vector 2; X' and response variable yi E V. We assume that ((I;, y)) are i.i.d. sampled from a sparse linear regression model, i.e., each (2t,, Vi) a realization of the sparse linear regression model y (0" .x) + S. where the distribution of has mean zero, S is some randomized noise that satisfies B[{[z] = O, and 6 E Rd the underlying sparse estimator with ||0* llo S k. In the following, we provide some assumptions related to the model.
Assumption 1. We assume that ||0* 11 S 1. Moreover, for the covariance matrix of x, E, there exist Koo and Ki such that ||Eue]|> 2 Keo /oo/|///ooo Vw + 0 and ||- kxrll/22 S Kg.
Remark 1. Due to the hardness of the problem in the NLDP model, rather than making bounded f2-norm assumption, we consider a stronger one where | S 1, which has been previously studied in the literature such as Chen et al. (2023 (022a); Fan al. (2021). It is notable that all the lower bounds established in our paper remain valid even in the weaker case [|0*]|2 < 1, without any modifications the proofs. Moreover, our upper bound in the interactive setting will still not be changed under the & assumption. However, our upper bound for the NLDP model relies on such an assumption. The only result that relies on the l assumption is our upper bound in the NLDP model.
Our focus in this paper is on estimating 6* in the local differential privacy (LDP) model. We aim to design a locally differentially private algorithm that produces output @erie that is as close as possible to the true 8*, with the goal of minimizing the & f--morm error ||@prio 1 We provide definitions related to LDP in Appendix B with more detailed information available in reference Duchi et al. (2014a 2018).
3
IMPROVED ANALYSIS FOR NON-INTERACTIVE SETTING
3.1 LOWER BOUND FOR GENERAL k-SPARSE CASE
In this section, we analyze the lower bound for the estimation error of non-interactive local differential privacy (NLDP) algorithms. According to Bun al. 2011)). transformed into an e-NLDP protocol without affecting its utility. Therefore. we will focus solely on e-NLDP. To establish the lower bound, consider a class of distributions for (x, y). where follows the uniform distribution over (-1,+1)d, and ( is a bounded randomized noise. We denote
(c, ()-LDP protocol can be
'To make our results comparable the previous results and for simplicity, in this paper we assume Koo and Kg all are constants. Note that previous studies on private regression also hide factors related to Σ, in their main context(c.g, Wang (2018); Wang et al. (2022): ; Cai et al. (202)) hide the term of poly (1/ //miin (X:).
"The lower bound results also hold for (c, NLDD protocol.
3

---

Published as a conference paper at ICLR 2024
Pk.d,c
Pk,d,c==Pa.. 30 Rd s.t. ||0|| 1, 1101lo I k, Uniform(+1, -1"" =00,x) + +; where [ satisfies E((] = 0 and K<| S C).
Based on the notation introduced above, it is evident that for any given data D { : vA) }3== pds where Po.5 E Pk.d.C. each || vd. Consequently, if we use the Gaussian mechanism on each to ensure (c. (o)-noo-interactte LDP, the scale of the noise should be O(2). This scaling implies that the Gaussian noise would introduce an error Poly(d). In the following, we will generalize the above observation and show for all NLDP algorithms, such polynomial dependency on is unavoidable.
Theorem 1. Given 0 <Es) 1 and an enror - consider the distribution class Pk.d,2. if Vk for any Pa.c E PR.d.2 given D = {(11,81)... (In, Bn)} i..d sampled from Pa.c there is an non-interactive LDP algorithm A whose output satisfies E A.D= [I[A(D) - 0112] < 5. Then, we
dk logl 12 -²
must have n 2 52(
Remark 2. It is noteworthy that the class of distributions PK.d.c reduces to the set of distribu- tions studied in Wang & Xu (2021 2019) when k = 1. The above theorem asserts that for 1, there exists instance Pe.c E P.,d,2 such that
any c-NLDP algorithm A with
In contrast to the optimal rate of O(V llo o for the f--morm estimation error in the non non-private case (Raskutti et al. 2011). and the nearly optimal rate
E AA [|)((D) 0|12] 2 SVV
dk dklog ne*
of O(max loog f. log.d we }) in the central 6)-P) model (Cai al. 2021) 1. for NLDP model
}), respectively. These results indi- cate that sparse linear models in the non-interactive LDP setting are ill-suited for high-dimensional scenarios where < d.
observe an additional factor of O yd) and O(max( sdd c
vnd v/l log
Theorem recovers the lower bound of 2 dllogd in Wang & Xu (2019 2021 when = 1.
nr? [ is more general than previous work. Notably, our proof of the lower bound differs significantly from that in Wang & Xu (2019) 202T) where the private Fano's Lemma in [Duchi et al. (2018) was mainly employed. The aim was to construct an r-separated family of distributions {Po for some set V such that the term C (Po is minimized, where
Thus, Theorem
1
C (Polvev
sup E(or(t))
= [V]
TE WEV
Here, each linear functional o, B.x + R is defined by (7) J (x) dP(x)) with B. =7 X + R| < 1} as the set of uniformly bounded functions, and P(xr) = M E.ED (x( is the average distribution. Wang Xu 2019 2021 considered the case where is the set of all basis vectors, which is 1-sparse. They showed that for some r-separated family of distributions, C (Pv( (Pu)vev= I - However, their approach is challenging to extend to the k-sparse case as |V| O(d"), and it is difficult to bound the summation term. To overcome this difficulty, adopt a private version of the Assouad's 's lemma in /Acharya et al. (2022). In details, we first construct random vector Z 0-1,0,+11 with | / k with high probability. For each realization of Z, 2, we have an associated 0g which is also k-sparse. Suppose Ú is the message obtained via the non-interactive LDP algorithm A on D ~ p We consider the mutual information between Z and
D, i.c., 1(Z ^ D). On the one hand, we demonstrate that any sufficiently accurate (private) estimation protocol must provide sufficient information about each Z, from the messages D. which reflected by the lower bound on mutual information [ A D) 2 ( log $) On the other hand, we show that if the output of algorithm A achieves estimation error of the mutual information scales as the privacy budget c, which is reflected by the upper bound on mutual information I I A DD S 200ee" "
3.2 EFFICIENT NON-INTERACCIVV LDP ALGORITHMS
This suggests that high- dimensional sparse linear regression, where n & d, becomes effortless the NLDP model. However,
In the preceding section, we established a lower bound of Ω( loloo d ni?
4

---

Published as a conference paper at ICLR 2024
this raises two questions. First, in the low dimensional case where > d, is the lower bound tight? Second, are there efficient algorithms for this problem? In this section, we focus on the upper bound. Before that, we introduce assumption about the distribution of (a. y) to elucidate our approach.
Assumption 2. There exists constant = 0(1) such that the covariates (feature vectors) 21,-2, In E Ed are i.i.d. (zero-mean) sub- sub-Gaussian random vectors with variance o², and the responses y1, y2. :..... In are i.i.d. (zero-mean) nub-Gaussian random variables with variance o².
Before presenting our method, we will outline the challenges associated with the problem at hand and explain why existing (non-private) methods are not suitable for our purposes. In the private and classical setting, where the fn-norm of each (I., 1i) is bounded by some constant, the most direct approach is to perturb the sufficient statistics locally (Smith et al. 2017 Wang et al. 2021), i... Σxx= = - "; and Σ - Tith. by adding Gaussian matrix and Gaussian vector each 2.n and Tiys, respectively. However, in our sparse setting, such a private estimator will provide a sub-optimal bound as it does not exploit the sparsity assumption of the model. In the non private and high dimensional sparse setting, to achieve the optimal estimation error, one approach is based on the LASSO (Raskutti et al. 2011). i..., to minimize 2n || - x013 + 1011
with some An where X = (xf .... ".", E RRad and Y (yi.... Un )². The second type of approach is based on the Dantzig estimator (Candes & Tao 2007), i.e. solving the linear program: An with some An. However, these two approaches difficult to privatize. However, the significant amount of noise needed for privatization is problematic, it destroys the assumptions of the theoretical results for LASSO and the Dantzig estimator. We that existing estimators for sparse linear regression all rely on solving an optimization problem, which is difficult to privatize. Nonetheless, in the classical setting, the private estimator can be obtained by adding noise to the sufficient statistics without solving an optimization problem. Therefore, a closed-form estimator will serve our purpose and it can be used to design an efficient private estimator for the sparse linear model. This approach will minimize the amount of noise added to the model.
ming [|0]] s.t. 1 ||XT (XA Y)
Before showing our private estimator, we first consider the non-private case. As we focus on the low dimension case, the empirical covariance matrix Xxx always exists. Thus, there no sparse assumption, the optimal estimator will be the ordinary least square (OLS) estimator $-1 XxxExx ExY given the dataset. However, now 0" is k-sparse, the OLS estimation will have a large estimation error since it is not sparse. Intuitively, our goal is to find a sparse estimator that is close to OLS, iee, arg ming |@0 Σxx Ex exyl 12. s.t. [101 I k, whose & convex relaxation of the lo constraint is equivalent to arg ming 10- xx 1 + >m.11011 with some An > O. Fortunately, the above minimizer is just the proximal operator on OLS: ProxA, (xxxExx) Since the proximal operator is separable with respect to both vectors, l and xx Exx,
(Proxx,, I1 (xxx = arg min (0, (xxx )x) + Am10.l
=gnn xx εxx)), max ( & Exy)),l Am. Om,
where the second equality is due the first-order optimality condition. Thus, the previous & regularized optimization problem has a closed-form optimal solution, which denoted as A:
i = Sx, (xxx Exy),
(2)
where for given thresholding parameter X, the element-wise soft-thresoolding operator Sx Rd + Rdd for any u E Idd is defined as the following: the i-th element of Sx(w) is defined as [Sx(u)]= = sgn(u,) max [u:] -)
Motivated by 2 and the preceding discussion, a direct approach to designing a private estimator is perturbing the terms of Σxx and Σxy in (2). However, the unbounded &g-sensitivity of both terms under Assumption 2 Suggesss that we must preprocess the data before applying the Gaussian mechanism. Since each z; is sub- Gau-Gaussiin,, we can readily ensure that ||x:||2 I (ololl n) for all i E [n] with high probability. Thus, we typically preprocess the data by fg-norm clipping, i.e., T;; = min [1[=:ll,,,") r | where r = 0(avd n) (Hu et al. 2022 Wang et al. 2022). However, if we preprocess each 2; and y; in 2 using this strategy, it becomes difficult to bound the term ||0 0111,., which is crucial for utility analysis.
5

---

Published as a conference paper at ICLR 2024
To address the challenge, propose new approach. For the term of Σxx, the ordinary f--norm clipping to each I; and get E, and then add Gaussian matrix to C, For the term Exy, we shrink each coordinate of x4 and each y; via parameters and respectively, i.e., Tij = sgn (2xg) min [1 ri} for j E [d] and üJ = sgn (yi) min flyal .2)). Then we add Gaussian noise to Z.y.. Finally, the server aggregates these noisy terms and gets noisy and clipped (shrunken) version of Σxx (Exy), i.e., xxx and Exy. Finally, we get (priv (D) Sx, (S xxxx" xxx) See Algorithm for details. In the following we show with some T, and T2, the previous (prie(D) could achieve an upper bound of Ō dvk
Vne
Theorem 2. For any 0 < e, < 1, Algorithm 1 satisfies (e, non-interactive LDP.
Theorem 3. Under Assumptions! 7 and
we set T1 т2 Olooolllonn.... = Oio /dgo
and An = O dl //oo in Algorithm
1
When n is sufficiently large such that n 2
Vne
(maxx moo 22 (2)
}), with probability at least 1 1- 0(d-9) - -((d) for some constant
one has
dllog ny l log dl log &
(ario (D) 8t 50
Vne
where Si ignores the logarithmic terms.
Remark 3. Compared with Smith et al. (2017). we improve by factor of O is worth noting that in the absence the soft-thresholding operator, the upper bound can be
yd
in our Theorem
Vk
shown to be Ō Vine which is consistent with previous work on linear regression (Wang et al. 2022
Smith et al. 2017 Hence, we can observe that the soft-threshodding operator plays critical role in our private estimator. The upper bound in equation 3 has an additional factor of Ö(Vd) compared to the lower bound in Theorem[] This is due to the fact that each entry of the Gaussian matrix we
added to each Ā. is Ō()), which indicates that |Σxx - Σ Lo, S Ō Viee). This Ö(vd) scaling
seems necessary in the NLDP model because each ||0; I D(Vdlog n) with high probability, and thus, we must add noise of scale Ō(#) to release the covariance matrix privately. Based on this, we conjecture that the lower bound in Theorem [ not tight, and the upper bound is nearly optimal. We leave it as an open problem. Additionally, equation 3 holdd only when is sufficiently large such that n 2 fmmmx Fx
}) to ensure that the noisy empirical covariance matrix is invertible and
(({xx)~11
Roc
Improved rate with public unlabeled data. As discussed in Remark 3 the main reason for the gap of ((Vd) between the lower and upper bounds is due to |Exx* - Σ 00,00 I Ō
Vnc However,
when compared to the non-private case where the error is ||Exx= - Eloo,,0 S < we can see
Vn
that the eитor due to the Gaussian matrix dominates. Since estimating the covariance matrix does not require the responses, we can use public but unlabeled data to achieve an improved estimation rate. It is worth noting that NLDP with public unlabeled data has been widely studied in recent years (Wang et al. 2022 Su et al., 2023 Daniely & Feldman 2019). Here we assume that the
server has access to m unlabeled data points Dawb = {xr ) j=n+1
n+m
C X where each æ; is sampled 2 Based on the above observations,
from the same Bub-Gaussian distribution as x; in Assumption
rather than using private data, we can utilize these public data points to estimate the underlying covariance matrix. Subsequently, we propose our private estimator gunl (D) = x 1 where Puub 1 a-mm -xx in Algorithm 3 The following result shows that we can improve the estimation error by factor of ((vd) compared with that in Theorem
D=n+11 2TZT is the empirical covariance matrix of {2;; { The details are provided
'Here we use O(d"s) ") as the failure probability is for simplicity, we can get a similar result for any failure probability 8' > O. The same for other results in the following parts.
'It should be noted that Smith et al. (011)) assumes ||и||| < 1, but we can get bound of Ō Vpe
when we
extend to |mılla la2 z vd via the same proof in Smith
2017

---

Published as a conference paper at ICLR 2024
Algorithm 1 Non-interactive LDP algorithm for Sparse Linear Regression
1: Input: Private data (i)) (IR x IR)" Predefined parameters 71 72, An.
2: for Each user i E [n] do
3: Clip ã, = 2, min |
Add noise T = =,07 + n1,6 where n1,1 E Raxd is sym-
metric matrix and each entry of the upper triangular matrix is sampled from from M(, 32r" log 3
6²
Release न. to the server.
4: for j E [d] do
5: Coordinately shrink Zi = sgn (riy) min { m1)
6: end for
7: Clip ü : sgn (W:) min flyil, 72). Add noise Z.0., ū,g; + n2,5, where the vector n2, RR
is sampled from A(, 32dr log 2. Ia). Release R.D; the server.
8:
end for
9: The server aggregates Σxx D 35 and Exy E
10: The server outputs garia (D) = Sxm, (p 1xxx)=1Exx)
Theorem 4. Under Assumptions lic and unlabeled dataset Doub (zjfz=nt1 E n described above. When is sufficiently large
andd 2 we suppose the server also has access to the additional pub-
that { d² d| }), set
72 0 /lg and An. 0 log n. log d'log à ) in
Fix A (2)
cvmm
Algorithm with probability at least Old -S(id) for some constant then one has
log n dl log d log
( - -0 0o
evR
where Qt ignores the logarithmic terms.
In addition to improving the estimation error by factor of O O(vd), our proposed estimator guml (D)
requires a smaller number of public unlabeled data points compared to the requirements Theorem
We only need m 2 (max ( d? =|
Reo X (E) }), instead of 2 {(mmx{ Prx 2n (x))
dt ||
(my)) in Theorem
This is because we do not need to estimate the covariance matrix privately.
Estimation error for haave- responses. In the preceding parts, focus has been the sub-Gaussian case, where both x and are aub-Gaussian, meaning that the random noise Ç is sub- Gaussian well. However, this assumption may be too stringent in real-world scenarios, where heavy-tailed noise is more commonly encountered. Our method is highly adaptable and can handle such heavy-tailed cases with ease. Here we consider the heavy-tailed case where the responses have only bounded 2p-moment with some 1. This assumption has been widely studied in both the
differential privacy and robust statistics communities (Hu et 2022 Kamath al. 2020 Sun et 2020 Chen et al. 2022b).
Assumption 3. There exist constants and M such that the covariates (feature vectors) Vi I2.
E Id are i.i.d. (zero-mean) sub- Gaussian random vectors with variance o² and
l....... n, [| < M < 0o for some (known) p
Theorem 5. Under Assumptions and
we set
TI =
n)
log
Olo/dlogn). and An Ol n log ( 24
lox net
11 in Algorithu 1 then as long as n >
28
"ل ②(max{ FR (X)
}) for some constant > O, one has
- 5 (dlogny/ k
log d ne²
log
(4)
z
where Ó ignores the logarithmic terms.
The limit of the bound in equation 4 as - oc the same as in equation 3 However, due to the htavy-tailed nature of the response variable y, our estimator requires more aggressive shrinking than
7

---

Published as a conference paper at ICLR 2024
in the sub- Gaussian case. Hence, unlike the sub- Gabssin case, we have T1 # 72. is worth noting that our current approach relaxes the assumption on the distribution of only. We anticipate that our general framework can also handle scenarios where the distributions of both and y are heavy-tailed, which we plan to explore in future work.
IMPROVED ANALYSIS FOR INTERACTIVE LDP
In the previous section, we studied both the lower bound and upper bound of sparse linear regression in the non-interactive model and showed that even for (LL)-sub-Gaussial data, it is impossible to avoid the polynomial dependency on the dimension d in the estimation error. However, since non-interactive protocols have more constraints compared to interactive ones, a natural question arises as to whether we can obtain better lower and upper bounds in the interactive model. To simplify the analysis, we mainly focus on sequentially interactive LDP protocols in this section, and note that all results can be extended to the fully interactive LDP model (Acharya et al. 2022).
4.1 LOWER BOUND FOR GENERAL S-SPARSE CASE
We begin by considering the lower bound, similar to the previous section. When k: 1. Wang & Xu (2021 provides a nearly optimal lower bound of Q dd for the estimation error. Thus, we are more interested in whether we can obtain an improved rate for general k. Unfortunately, we will show that, for the same distribution class Pk.d,2 as in Section 3.1 the term of O(Vk) in the non-interactive case cannot be improved even if we allow interactions.
Theorem 6. Given 0 < S 1 and an error v S 1v2k' consider the distribution class Pk,d,2 {(z1.y1) ... (In, 3n)3 i.i.d. sampled from Pe.c, there is an e-sequentially interactive LDP algorithm A whose output satisfies E A.D- [IIAA(D) - 0112| - v.
if for any Po.s- E Pk.d,.. given
Then, we have >> Q2
dk
Remark 4. The above theorem states that for the class Pk,d,2 and any e-LDP algorithm A with
0 6 S 1, there exists an instance Po.ç Pk.,, such that E P [IIA(D) 012] 2 22(
dk
ne?
Although the difference is only O(ylog d) compared to the lower bound in the non-interactive model, the proof and the hard instance construction are entirely different. Moreover, the lower bound proof of Theorem 6 is also distinct from that of the l case in Wang & Xu (2021). Briefly speaking, Wang & Xu (2021) mainly uses an LDP version of the Le Cam method, where it needs to upper bound the term C (P. eeyy (which is similar to the non-interactive LDP case). In contrast, use
private Assouad's lemma in Acharya et al. (2020).
4.2 LDP ITERATIVE HARD THRESHOLLIIN REVISITED
Regarding the upper bound, Wang & Xu 2021 considers the case where the covariates {x; ) 1
satisfy Assumption] 1 with ~ Uniform +1, and |s| < C for some constant C. Wang & Xu
(2021) aims to solve the following optimization problem in the LDP model, where k' a parameter that will be specified later.
min L( D) = 2n Σ (z,,0) - y))², s.t. |101]2 S 1, 1,110 I S..
(5)
The authors proposed a method called LDP Iterative Hard Thresholding, and claimed it achieves
an upper bound of Ö(
dk for the general k-sparse case, nearly optimal based on Theorem 6 ne"
However, this rate is mistaken. The sensitivity analysis of the per-sample gradient is incorrect under the assumption of ||0*|| 2|2 < 1, and such analysis leads to the incorrect utility bound. Specifically, in the proof of Theorem in Wang & Xu (021)), ;, it needs upper-bound the each term (I,, 0,-1), i). where ||0,-1l2 212 < and ||0z-1loo X O(K). They claims that this term is upper bounded by 1, but in fact it is upper bounded by O(Vk). Seeing the flaw of its own, we also highlight the technical constraint. Their sensitivity and utility analysis heavily relies on the uniform distribution assumption of æ and the assumption that the random noise is bounded, which is challenging to extend to general distributions (such as those in Assumption 2). In this section, we aim to rectify the previous analysis and show an upper bound of Ö(kvā) for the LDP Iterative Hard Thresholding method. Moreover, generalize to the distributions satisfying Assumption
8

---

Published as a conference paper at ICLR 2024
For data distributions satistying Assumption to ensure bounded sensitivity of the per-sample gradient of L(0; D.. || ((0,z,) - y1) 2|2 for i E [n], we adopt a similar strategy as Section That is, each user i conducts the same shrinkage operation: Eij sgn (zty) min {|raa] Ta for
3.2
J E
[d] and o = sgn (y:) min [ In this case, we can see the i-th sample gradient satisfies (10, - - TTs) l2 S (dn(VVk' (VKT) + +72) if |00| S and |10|u - k'.
|o
To privately solve the optimization problem equation 5] apply combination of private randomizer Duchi et al. 2014 (see equation 6 in Appendix ( and the iterative hard thresholding gradient descent method develop an e-LDP algorithm. In total, our approach begins by assigning each user to one of the groups {St with the value of T to be specified later. During the t-th iteration, users with (z, y) in group S. randomize their current gradients T" ((z, f--1) y) using equation 6 Once the server receives the gradient data from each user, it executes gradient descent step followed by truncation step 8 Trunc (ft, k)), which retains the largest k' entries of 9, (in terms of magnitude) and sets the remaining entries to zero. Finally, our algorithm projects 8, onto the unit & norm ball 13, to get 0,. See Algorithm for details.
Algorithm 2 LDP Iterative Hard Thresholding
1: Input: Private data {( 3:) E (IR' x R)". Iteration number T,, privacy parameter step size 7). truncation parameters т, Tı, T2, threshold k'. Initial parameter 0g =00 0.
2: For the i-th user with
[m]. truncate his/her data follows: shrink x; to o. with T.j sgn (ztz) min { [ ri for j E [d]. and D; := sgn (vx) min {1ya], r2). Partition the users into
T groups. For t= 1, ... T, define the index set S. = {(1 - 1) | + 1,... , ] = T.
then S. = = T.
+ ,....,
3: for = 2,, .T do
4: The server sends 0,-1 to all the users in S.. Each user i E St perturbs his/her own gradient: let v X² ((0-1,,ā))
9i compute z = R. (V.), where R. is the randomizer defined (arl(Vi' W + T2) and send back to the server.
in equation 6 with r = vdn
5: The server computes V [& Eies, 2; and performs the gradient descent update 0 =
O2 v/V1-1
6:
8 = Trunc kk)
7: 6,- = argaeB, 100 0/112-
8: end for
9: Output: 0T
Theorem 7. For any O, Algorithm D ii sequentially interactive LDP.. Moreover, under Assump- tions] [ and [ and if the distribution of x is isotropic, i.e., == la- By taking T = O(log n). the output Or of the algorithm satisfies k' 8k, 7 O(1), TI T2 O(avooog
||0r 11 S Ō kydd with probability at least 1 - O(d some constant c 0.
In comparison to the upper bound presented in Theorem 3 for the non-interactive case, our algorithm exhibits noteworthy improvement by a factor of approximately Ó Ó(vd/Vk), This improvement stems from our approach, which eliminates the need for private estimation of the covariance matrix, thus achieving enhancement of approximately Ö(Vd). However, it is worth noting that the sensitivity of the per-user gradient in our algorithm, denoted Ö(V differs from the sensitivity Consequently, we introduce an additional factor of approximately Ö(Vk). Importantly, when compared to Wang & Xu (2021). our Theorem 7 primary contribution is extending the {-1, +1}" uniform distribution assumption of covariates Wang & (1)-suubbb
of Ö(Vd) associated with ž. in Algorithm |
Xu (2021) to general (1))-sub-Gausse sub-Gaaausin assumption on covariates and heavy-tailed assumption on responses, rather than improving the upper bound. In fact, our upper bound aligns with the correct
bound in Wang & Xu (221))
We can see that Theorem 7 only holds for the case where the distribution of is isotropic. Actually, we can relax this assumption, and we can show the bound Ō val also holds for general
Remark 5.
/
sub-Ga Gaussian distributions. Due to the space limit, please refer to Section in the Appendix, where have slightly modified Algorithm 2

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
Di Wang and Liyang Zhu are supported in part by the baseline funding BAS/1/1689-01-01, funding from the CRG grand URF/1/4663-01-01, FCC/1/1976-49-01 from CBRC, and funding from the AI Initiative REI/I/481 1-10-01 of King Abdullah University of Science and Technology (KAUST). They are also supported by the funding of the MAAIS-KUSST Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUS) when this study was performed. The research of Meng Ding and Jinhui Xu was supported in part by NSF through grant CCF-2200173 and by KAUST through grant CRG10-4663.22
AI). Vaneet Aggarwal was visiting professor in KAUST
10

---

Published as a conference paper at ICLR 2024
REFERENCES
Jayadev Acharya, Clément I. Canonne, Ziteng Sun, and Himanshu Tyagi. Unified lower bounds for interactive tigh-dimensional estimation under information constraints. arXiv preprint 2xXi::2010006662, 2020.
Jayadev Acharya, Clément L Canonne, Himanshu Tyagi, and Ziteng Sun. The role of interactivity in structured estimation. In Conference Learning Theory, pp. 1328-1355. PMLR, 2022.
Daniel Alabi, Audra McMillan, Jayshree Sarathy, Adam Smith, and Salil Vadhan. Differentially private simple linear regression. Proceedings on Privacy Enhancing Technologies, 2:184-204, 2022.
Hilal Asi, Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: Optimal rates 11 geometry. In International Conference on Machine Learning, pp. 393-403. PMLR, 2021a.
Hilal Asi, Daniel Lévy, and John C Duchi. Adapting to function difficulty and growth conditions in private optimization. Advances in Neural Information Processing Systems, 14:19069-19081, 2021b.
Andrés F. Barrientos, Jerome Reiter, Ashwin Machanavajhhala and Yan Chen. Differentially private significance tests for regression coefficients, June 2018. URL
abs abs/1 09561 1tdiv:1705.0900 [stat].
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances in neural information processing systems, 32, 2019.
Mark Bun, Jelani Nelson, and Uri Stemmer. Heavy hitters and the structure of local privacy. ACM Transactions Algorithms (TALG), 15(4):1-40, 2019.
Peter Bühlmann and Sara van de Geer. Statistics for Highh-Dimessioee Data. Springer Series in Statistics Ser. Springer Science & Business Media, June 2011.
Petra Búžková. Linear Regression in Genetic Association Studies. PLOS ONE, 8()):56977,, February 2013. ISSN 1932-6203. doi: 10. h URL http:t/::// /ttp::://.//rraa.......... org/pl oecoossoneaaa aattooeeerttti rt c www.eleeeee w1t.:ceeee111111310111 111.://=1111111/ooooooooo pone. 0056976 Library of Science.
Publisher: Public
T. Tony Cai and Harrison Zhou. Optimal rates of convergence for sparse covariance matrix estimation. The Annals of Statistics, 40(5), October 2012. ISSN 0090-5364. doi: 10. 12-A0S998. URL
3030 arXiv: 3002.3030 [math, stat].
T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):2825-22 22225-28500 October 2021. ISSN 0090-5364, 2168-896899998 8966. Mathematical Statistics.
doi: 10.1214/21-A022053 Publisher: Institute of
Emmanuel Candes and Terence Tao. The dantzig selector: Statistical estimation when p is much larger than 2007.
Junren Chen, Michael K Ng, and Wang. Quantizing heavy-tailed data statistical estimation:(near) minimax rates, covariate quantization, and uniform recovery. arXiv preprint arXiv:2212. 14562, 2022a.
Junren Chen, Cheng-Lone Wang. Michael K. Ng, and Di Wang. High Dimensional Statistical Estimation under Uniformly Dithered One-bit Quantization, August 2022b. URL http:// arxiv www.or/gbbs.... /2002.22222222222 13157 arXiv:2202.1315: [cs, eess, stat].
Junren Chen, Cheng-Long Wang, Michael K Ng, and Di Wang. High dimensional statistical estimation under uniformly dithered one-bit quantization. IEEE Transactions Information Theory, 2023.

---

Published as a conference paper at ICLR 2024
Yan Chen, Ashwin Machanavajjhala, Jerome P. Reiter, and Andres F. Barrientos. Differentially Private Regression Diagnostics. 2016 IEEE 16th International Conference on Data Mining
(ICDM), pp. 81-90, Barcelona, Spain, December 2016. IEEE. ISBN 978-1-5090-5473-2 doi: 10. (1991ICDM.2016.000 URL htt.httpp//eeeeeee
leee /et.eee..r/bbbccmmeetee///188111
Amit Daniely and Vitaly Feldman. Locally private learning without interaction requires separation. Advances in neural information processing systems, 32, 2019.
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Local Privacy, Data Processing Inequalities, and Statistical Minimax Rates, August 201 4a. httpt//:://aaxiivoo abs/
1302. 3203
arXiv: 1XX2::300..303 302.3203 [cs, math, stat].
John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. Privacy Aware Learning, Journal of the
ACM, 61 61(6); December 20 ISSN 0004-5411, 1557-735X. doi: 10.1145/2666468, URL
https: /1 acm.
wwt. wtq//oi////ooooooooooooo 10. 1141/116664444
John Duchi, Michael Jordan, and Martin Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521)::82-22) 201, 2018.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284, Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In Shai Halevi and Tal Rabin (eds.). Theory of Cryptography, Lecture Notes in Computer Science, pp. 265-284, Berlin, Heidelberg, 2006b. Springer. ISBN 978-3-440-3273--5. doi: 10.7/0 1681878_14
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy- preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pp. 1054-1067, 2014.
Jianqing Fan, Weichen Wang, and Ziwei Zhu. A shrinkage principle for heavy-tailed data: High- dimensional robust low-rank matrix recovery. Annals of statistics, 49(3):1239 2021.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 439-449, 2020.
Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 41st ACM SIGMOD-SIGACTTSSIAA Symposium on Principles of Database Systems, pp. 227-236, 2022.
Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high-dimensional m-estimation. Advances in neural information processing systems, 27, 2014.
Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory, pp. 2204-2233 PMLR, 2020.
Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In International Conference on Machine Learning, pp. 10633-10660. PMLR, 2022.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference Learning Theory, pp. 2. Workshop and Conference Proceedings. 2012a.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private Convex Empirical Risk Minimization and siggh-iimensional Regression. In Proceedings of the 25th Annual Conference on Learning Theory, pp. 25.1-25.444. 20. JMLR Workshop and Conference Proceedings, June 2012b. URL https: //proceedinge igg. ml r. prwss v//3//23/////k ferfeerr1.. html
ISSN: 1938-7228.
Xiyang Liu, Prateek Jain, Weihao Kong, Sewoong Oh, and Arun Sai Suggala. Near optimal private and robust linear regression. arXiv preprint arXiv:2301.33273 2023.
12

---

Published as a conference paper at ICLR 2024
Andrew Lowy and Meisam Razaviyayn. Private stochastic optimization with large worst-case lipschitz parameter: Optimal rates for (non-smooth) convex losses and extension to non-convex losses. In International Conference on Algorithmic Learning Theory, pp. 986-1054. PMLR, 2023.
Yuan Qiu, Jinyan Liu, and Di Wang. Truthful Generalized Linear Models, September 2022. URL http://arxiss org/ abs 2209. 0 07815 arXiv:2209.07815 [es].
Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Minimax rates of estimation for high-dimensional linear regression over by-ball.. IEEE transactions on information theory, (7(10):677669999 2011.
Jayshree Sarathy and Salil Vadhan. Analyzing the differentially private theil-sen estimator for simple linear regression. arXiv preprint arXiv:2207. 132899 2022.
Ronald C. Serlin and Leonard A. Marascuilo. Statistical Methods for the Social and Behavioral Sciences. Psychology Ser. WH Freeman/Times Books/Henry Holt & Co, January 1988.
Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is Interaction Necessary for Distributed Private Learning? In 2017 IEEE Symposium on Security and Privacy (SP), pp. 58-77, San Jose, CA, USA, May 2017. IEEE. ISBN 978-1-5090-5533-33 doi: 10.1109/SP.017.35. URL
ieareeiieeee ieee. wtgg//bcumentt/9555777
Gilbert W Stewart and Ji-guang Sun. Matrix perturbation theory. Academic press, 1990.
Jinyan Su, Lijie Hu, and Di Wang. Faster rates of private stochastic convex optimization. In
International Conference Algorithmic Learning Theory, pp. 995-19022 PMLR, 2022.
Jinyan Su, Jinhui Xu, and Di Wang. On pac learning halfspaces in non-interactive local privacy model with public unlabeled data. In Asian Conference on Machine Learnnng pp. 927-941. PMLR, 2023.
Qiang Sun, Wen-Xin Zhou, and Jianqing Fan. Adaptive huber regression. Journal of the American Statistical Association, 1 115(529):254 265. 2020.
Kunal Talwar, Abhradeep Guha Thakurta, and Li Zhang. Nearly Optimal Private LASSO. In Advances Neural Information Processing Systems, volume 28. Cur- ran Associates, Inc., 2015. URL
http://aapprra.ip...ccppaaaaapae cccppaperr/01//haah Awstrlltbbbttttttta.aaaaactc
Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12, September 2017. URL
02755 arXiv:1709.02753 [es].
Terence Tao. Topics in random matrix theory, volume 132. American Mathematical Soc., 2012.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends@ in Machine Learning, 8(1-2): 2015.
Prateek Varshney, Abhradeep Thakurta, and Prateek Jain. (nearly) optimal private linear regression via adaptive clipping. arXiv preprint arXiv:2207.04686, 2022.
Roman Vershynin. Introduction to the non asymptossymttttii analysis of random matrices, November 2011. 3027, 1xXiv:0011.302 [cs, math].
URL
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Di Wang and Jinhui Xu. On sparse linear regression the local differential privacy model. In International Conference Machine Learning, pp. 6628-6637, PMLR, 2019.
Di Wang and Jinhui Xu. On Sparse Linear Regression in the Local Differential Privacy Model. IEEE Transactions Information Theory, 57(2):1182 1200, February 2021. ISSN 0018-9448, 1557-9654. doi: 10. 109/TTT.2002.33444406 document/ 992ttt/9799997
URL https: httt:::/ieeexlore..eeeee org/
13

---

Published as a conference paper at ICLR 2024
Di Wang. Hanshen Xiao, Srinivas Devadas, and Jinhui Xu. On differentially private stochastic convex optimization with heavy-tailed data. In International Conference on Machine Learning, pp- 10081-10091. PMLR, 2020.
Di Wang. Huangyu Zhang, Marco Gaboardi, and Jinhui Xu. Estimating smooth glm in non-interactive local differential privacy model with public unlabeled data. In Algorithmic Learning Theory, pp.
1207-1213. PMLR, 2021.
Di Wang, Lijie Hu, Huanyu Zhang, and Marco Gaboardi. Estimating Smooth GLM in Non-interactive Local Differential Privacy Model with Public Unlabeled Data, August 2022. URL http://
arxiv. oeciv.org//bb.. (erg/abs/1911 00482) 1EXiv:190..0000 [es, stat].
Yu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction estimation in unbounded domain, July 2018. URL
wtt.:orrgaabs/........ 02596
arXiv:1803.025% [cs, stat].
Eunho Yang, Aurelie Lozano, and Pradeep Ravikumar. Elementary estimators for high-dimensional linear regression. In International Conference on Machine Learning, pp. 388-396. PMLR, 2014.
Kai Zheng, Wenlong Mou, and Liwei Wang. Collect at once, use effectively: Making non-interactive locally private learning possible. In International Conference Machine Learning, pp. 4130 4130-4139.
PMLR, 2017.
14

---

Published as a conference paper at ICLR 2024
Model
Method
Setting
Upper Bound
Lower Brund
Data Assimphion
Cai et al.
2021
general
ne
sub Gaussian
Central
Kiler el al
2012b
sparse
o Var
sub Gauxsian
Cai ot al.
2021
sparse
Ory /
+ n1
)
sub-Gaussian
Hu et al.
2022
sparse
O
heavy-tail
Wang Xu
2021
1-spunse
dloyd b
sub Gaussian
Non-inleractive Local
Our Work
k-sparse
sub-Caussian
Our Work
spapss
sub- Gaussian with public data
Our Work
k-spanse
vac
heavy-tailed response
(eet)
Smith et al.
2017
general
yms
Suh-Gaussian distribution
Interactive Local
Wang & Xu
2021
1-sparse
sub-Gaussian
Wang & Xu
2021
k-spanse
val O
Uniform distribution
Our Work
k-sparse
Vyne
0ly
we
d
sub-Gaussian
Table I: Comparison of our work with related studies on (e, (sparse) linear regression in the statistical estimation setting. Here, n represents the sample size, h denotes the sparsity, and d refers to the dimension. The asterisk (*) indicates that the proof of the upper bound in Wang & Xu (2021) contains technical flaws and is deemed incorrect. In our comparison, the term "sub-Gaussian" signifies that both the covariates and responses follow -(u-suubaaa distributions. On the other hand, "heavy-tail" indicates that both the covariates and responses have bounded fourth moments. Additionally, "heavy-tailed response" implies that the responses possess a 2p-moment, where p 1. "Sub-Gaussia with public data" characterizes the scenario where the data is uub-Gaussian, and the server possesses additional public but unlabeled data. Lastly, "uniform distribution" " describes the situation where the covariates are drawn from {+1,- -1] and the responses are bounded by ((1).
A RELATED WORK
There is a significant body of research on the differentially private (sparse) linear regression problem, which has been examined from multiple perspectives, such as Alabi al. (2022) : Chen al. (2016); Barrientos et al. (0118); Qiu et al. (2022). In this study, we mainly focus on the works that are highly relevant to our research problem. Thus, we compare the research on sparse linear regression in the
central model with that on linear regression in the local model. For a detailed comparison between these two directions of research, please refer to Table
Linear regression in the central DP model. Most studies on the optimization setting consider more general problems, such as Stochastic Convex Optimization (SCO) and Empirical Risk Minimization (ERM) (Wang] 2018). In recent years, DP-SCO and DP-ERM have been extensively studied (Bassily
et al. However, it is worth noting that in order to apply these results to linear regression,
2019 Feldman et al.] 2020 Asi et al. 2021b Su et al. 2022 Sarathy & Vadhan 2022).
need to assume
that both the covariates and responses are bounded, and the constraint set of 0 is also bounded to
ensure that the gradient of the loss is bounded. Some works, such Waag al. (2020); Kamath let al.] 2022): Lowy & Razaviyayn] (2023), have relaxed these assumptions to allow for sub-Gaussian or even heavy-tailed distributions. In the statistical estimation setting, Cai et al. (202I) provides a
nearly optimal rate of Ö(1) 0( + dv/og(1/6)) for the (c, 8DP model with ne
data. Later, Varshney et al. (2022) improves upon this rate by considering the variance of the random noise o². Additionally, Liu et al. 2023) extends this work to the case where some response variables are adversarially corrupted.
Sparse linear regression in the central DP model. In the optimization setting, the LASSO problem with an l -orm ball constraint set is studied in Talwar et al. (2015). The authors demonstrate that this
setting leads to an excess empirical risk of O log d ), which is further extended to the population [n/]
risk in Asi al. (2021a). On the other hand, Kifer al. (2012b) provides the first study for the
estimation setting and develops an efficient algorithm that achieves an upper bound of O k3/2 Vne!
Recently, Cai et al. (2021) has shown a nearly optimal rate of Õ(V
k blog
+ A klogd ) for (c, DDP in
15

---

Published as a conference paper at ICLR 2024
the case of (1)) D(u)-subaa Gaussian data. Additionally, Hu et al. (2022) has established upper bound of Ó k log d) for the scenario where the covariate and response have only bounded fourth-order /ne moments.
Linear regression in the local DP model. Regarding the non-interactive case, Smith et al. (0017) has demonstrated that if both covariates and responses are bounded by some constant, the private at
optimal rate for the excess empirical risk is O(y ne indicating a bound of only O
under
<V"
the ((1)-sub-Guussian assumption. On the other hand, in the (sequentially) interactive setting, the majority of research considers the DP-SCO DP-ERM protocols (Duchi et al. 2014b 2018).
Sparse linear regression in local DP model. Compared to the three aforementioned settings, there has been relatively less research conducted on sparse linear regression in LDP. For the optimization perspective, Zheng et al. (2017) has shown that when the covariate and response are bounded by some constant, it is possible to achieve an error of ((( ne= )+) if the constraint set is an & -nnormm ball. However, their method cannot be extended to the statistical setting since we always assume that the covariates are (())-uub-Gausianl which indicates that their 22-norm is bounded by O Regarding the estimation setting, as discussed in the introduction section, Wang & Xu (202T) provides the first study. Notably, the upper bound proof in Wang & Xu Xu) (2021) has flaw, and the correct upper vāk
bound is O
EV
B LOCAL DIFFERENTIAL PRIVACY
Definition (Differential Privacy (Dwork et al. 2006a)). Given data universe X, we say that two datasets D, D' C are neighbors if they differ by only one entry, which is denoted as ~ D'. randomized algorithm A is (e, differrrentill private (DP) if for all neighboring datasets D, D' and for all events S in the output space of A, we have (A(D) E 8) < E 5)+ +
Since we will consider the sequentially interactive and con-interactive local models in this pa- per, we follow the definitions in Duchi et al. (0018). We assume that { [ are the private observations transformed from { {X through some privacy mechanisms. We say that the mech- anism is sequentially interactive when it has the following conditional independence structure: + Zi, 24 Xj {X,, 21. 21.... 2 for all j * and [n]. where 1 means independent relation. The full conditional distribution can be specified in terms of condi- tionals (Z X, = F4, Z 21:1). The full privacy mechanism can specified by a collection Q = (Q.) When Z, only depends on X;, the mechanism is called non-interactive and in this case we have simpler form for the conditional distributions (Z: X; = 4.). We now define local differential privacy by restricting the conditional distribution Q,
{X,, -..... , 1
Definition 2 (Local Differential Privacy (Duchi et al. 2018)). For given privacy parameters 0 < é, < 1, the random variable Ze is an (e, sequentially locally differentially private view of X if Zi-1 and xr, x' E X we have the following for all events S.
for all 21, 22,
Q (7, E X, x,, 7 = (Q
71.-1 21:2-1) +
The random variable Z; is an (c,5) non-interactively locally differentially private (NLDP) view of x;= Q = (Q:)= is (c, sequentially (non-interactively) locally differentially private (LDP) if each
X, if Q, (Z, E S) X,= xx=x,)= S Q, (Z, E S | =x() x²)++ 8. We say that the privacy mechanism
2, is a sequentially (non-interactively) locally differentially private view. If = O, then we call the
mechanism sequentially inon-interactively) LDP.
In this paper, we mainly use the Gaussian mechanism Dwork et al. 2006b to guarantee (c. 6)-LDP.
Definition 3. (Gaussian Mechanism). Given any function q: X - RR, the Gaussian Mechanism is defined as: Mo(D, ()) = q(D) + Y, where Y is drawn from Gaussian Distribution. N (0. with o 2 2 (1l supp-p' [D) q (D') ||2- Gaussian Mechanism preserves (c,8) -)diffferential privacy.
Here A2(g) is the le-sensitivity of the function q, i.e. A2(g) =
16

---

Published as a conference paper at ICLR 2024
C PRIVATE RANDOMIZER IN SECTION 4.2
Private randomizer. On input æ E I2, where ||l|| S r, the randomizer (2)x) does the following.
first sets ā | where b {-1,+1} a Bernoulli random variable Ber 33 sample Ber (e//et + 1) and outputs ((rvP)R (3)), where
||=ll 2r
We then
(.))..
Uni E Sp
(u, σ)
= =
R (x) Uni u S (u, T
(6)
ifs
The following lemma, which is given by Smith et 2017)) coordinate of the randomizer is
: Wang Xu (0021 shows that each
R2 and is unbiased.
Lemma 8. Given any vector I R& with | S r, each coordinate of the randomizer (T(x) defined above is a sub-Gaussian random vector with variance o² = O(²) and [[)] = x.
Moreover (.)-) is e-DP.
D SUPPORTING LEMMAS
First, we introduce the definitions and lemmas related to sub-Gaussian random variables. The class of sub-Gaussian random variables quite large. It includes bounded random variables and Gaussian random variables, and it enjoys strong concentration properties. We refer the readers to Vershynin (2011) for more details.
Definition 4 (Sub-Gaussian random variable). A zero-mean random variable X E R is said to be Sab-Gaussian with variance o² (X subG (d²)) if its moment generating function satisfies E[exp(tXX) S exp =²e2) for all > 0. For a sub- -ab--aassinn random variable X, its sub-Gaussian norm || 1, defined as || inf(c > E Eeexp( x2 dt ) s 2). Specifically, X subG(o?)
we have || I ((r).
Definition 5 (Sub-exponential random variable). A random variable X with mean [[ Ç-sub- exponential for all [1] s t we have E[jex(!((X - [[(]) S exp( 2222 For sub-exponential ran- dom variable X. its sub-exponential norm || v is defined as || inf 0: Elexp( [x 2}.
Definition 6 "Sub-Gaussian random vector). A zero mean random vector X E Rd is said to be Sabb-aassian with variance o² (for simplicity, we call it P--sub-Gaussian which is denoted as (X ~ subGa (o")). if (X, u) is sub-Gaussien with variance 0² for any unit vector E Rd.
Lemma 9. If X is sub-Gaud Gabbsanssinn or sub-exponential, then we have ||X -[[X]]l> S 2| or
|| B[X]]| S ||
Lemma 10. For two sub- Gab-saasiinn random variables X1 and X2. X1 X2 is sub-exponential random variable with
[X X2lly, I [ : ||x2 11 }).
Lemma 11. X X ~ subG (o²), then for any t >> 0, it holds that P[[X] t) exp (app------ (-2oz)
Lemma 12. For sub- Gaussian vector X ~ sub Ga (a²), with probability at least 1 - 8' we have
||x||a S 4o 4o dlog 3.
Lemma 13. (Cai & Zhou 2012 If {21, 22..,,.....300 ,2n are realizations the (zero mean)
(--sub-Gassiann random vector X with covariance matrix Σxx E[XX"), and Exx (Ózx² 55) isissa= = 1,2 Ei z.de is the empirical covariance matrix, then there exist constants C and 7 > O such that for any i.j E [d], we have:
(||xxx- -X
-xx Ia 1)) S Sie
-nt
00,00
for all |4| S ④ with some Ss where C₁ and y are constants and depend only on o². Specifically,
log dl 271
P
Exx 15xx-Exx|1
< 8
100.00
17

---

Published as a conference paper at ICLR 2024
Lemma 14. Let X1, Xn be independent (zero mean) random variables such that X; subG (o²). Then for any a E R"; O, we have:
a
Σ
a >
2 exp
20
| |a
Let X2....... ,n be n (zero mean) random variables such that each X; is Sab-Gaussian with 0². Then the following holds
Lemma 15. \Vershynin 2011
max X; sEm
20
2
max iEn
X
2
2ne
20
Below is lemma related to the Gaussian random variable. We will employ it bound the noise added by the Gaussian mechanism.
Lemma 16. Let (x be n random variables sampled from Gaussian distribution (0, o²). Then
E
max ISisn
I a / 22V2looge log 2n,
|as| 2 t 1))
12
P
max
2nc 20
Isisn
Particularly, if==1, 1, we have (f]z;] 2 t}) $ 2c ===-
Lemma 17 (Hoeffding's inequality). Let X1, Xn be independent random variables bounded by the interval [a, b). Then, for any 0,
(- (-(6-) (b-a))
2nt2
IP
X
Σ E [X,]]
>
s 2 exp
Lemma 18 (Bernstein's inequality for bounded random variables). Let X1, X2, Xnn be indepen-
dent centered bounded random variables, i.e. |X,] S M and [X,] = 0. with variance [X?] = 0². Then, for any i O,
2Mr V2n02t+ +
IP
X; Σ i=1
< 2
3
Lemma (Bernstein's 's inequality for sub-exponential random variables). æı, " be i.i.d. realizations of (-subexponential random variable X with zero mean. Then,
P(
Σ
x
2 t) < 2exp(=exmmm
|0 }).
n1/x=13
Lemma 20. communiamnee Matrix Bernstein inequality (Vershynin 2017 Consider finite
sequence X; of independent centered symmetric random d x matrices. Assume we have for some
numbers K and that
||x.ll2 K.
Σ
E
X
0²
2
Then, for every t 2 0 we have
IP S
8/22
<
epexp
02 Kt/3
Lemma 21. (Jain et al. 2014) For any 0 E R* and integer < k, if 0, Trunc (0, s) then for k-s any 0* E R* with |10" S 8, we have 100, 0|1 < k- 0* - 01l
Lemma 22. Let IC be convex body in R2, and RP, Then for every E K., we have
[px(()) u/12 < ||D u112
where Pk is the operator of projection onto K.
18

---

Published as a conference paper at ICLR 2024
E OMITTED PROOFS
E. OMITTED PROOFS IN 3.1
Proof of Theorem We consider the hard distribution class Pk,d,2, where for each instance Po.c Pk.d,2 its random noise Ç satisfies E[c] = 0,1<l S 2, and ||@]] 1 S and ||0llo I k hold. We denote y = Vi and define a vector 0₂ where 0,,1 = -22 for é E [d]. { H= are realizations of the random
variable E {+1,0, 0.,4,, where each coordinate Z; is independent to others and has the following distribution:
k PIZ
k -1 11= 4d'
k
IP [2 +1]
P PZZ 0} 2d
4d'
We first show that 0- satisfies the conditions that |10|| and |00|o S k. The resulting 0₂ has an expected (k//2)-sparsit) and E [2,] 0. x² EE [ k/2d for all i E [d]. By utilizing Chernoff bound, we can conclude that 0₂ is k-sparse with probability at least 1 - -//4d if l 2 4log d. This will be enough for our purposes and allows us to consider the random prior of hard instances above instead of enforcing k-sparsity with probability one (see the followings for details). When 0₂ is k-sparse we can also see ||0211 S vku < 1 as we assume S v/
Next, we construct the random noise Ss for each fz. We first pick 2 randomly from {-1, 0, +134 as above. For each we let:
5 -- -1 (x,, 02)
- (x, 0z)
w.p.
1 1
fx. 2
w.p. (a.0.) 2
Note that since (z, (2,0,)) S VI.
The above distribution is well-defined and |cs| < 2, E[s|=] = 0 (thus E(s] = 0). Thus we can see our for (0z, C2), with probability at least 1 3d we have Po..c. E PR.d,2. Morevoer, we can see that density function for (2r, v) is Po..c((r,, y)) I+v(2.0.) for (x; y)
-1)11-1)0+1, Then, for the i-th user who has the data sample (I; Vi) from the distribution Pa.ç with mean vector 0z, he/she sends his/her through private algorithm A getting a message S.-
24+1
Next, will introduce the Lemma 23 to show that supposing the accuracy of the algorithm is then it will provide sufficient mutual information I (Z, A S"), where S" is the tuple of messages received from the private algorithm A. The idea of the proof follows Acharya al. (2022).
Lemma 23. Given 0 < c <<<., 1, if algorithm A is an c-NLDP algorithm such that, for any n-size dataset D = {(x, }:) consisting of i.i.d. samples from Poz.2z with the random variable Z has the above probabilities, and its output grriv satisfies E[]]@rrii 8 12] g. then we have Ed 1
= 16k $). Therefore, A = 22k log +) holds.
Proof of Lemma
23 Consider the estimator 0 - (S*). we define another estimator 2 for Z by
choosing
2 = argmin ||0_ 0112.
=1
Specifically,
10g
02l12
< 2 Oz with probability 1. and
E |102 0z112] E [
k + 0z112 [102]1
max 1 12.112 < 4
12
k
D2
d
31²
4d
64
4d
k
8
In light of the fact that Ø is good estimator with regards to the & loss and has a deviation of no more than v/4, provided that Oz is k-sparse, and considering the bound on the probability that Z is not k-sparse, as well as the fact that the maximum difference between any two mean vectors 0z, 0z.
derived from our construction is v/ / Vk, it follows that |02 - 0z o Σi= L 2. As result, it implies:
d +
3k
Σ
P(Z
2 $
8
1=1
19

---

Published as a conference paper at ICLR 2024
Also, consider the Markov chain:
24 -0 +Z,
We could derive:
T(Z A 2,) - Σ (Z (Z))
Next we will bound Σ T(Z4 A 7.). By Fano's inequality, we have for all i:
k 2d
1(2 A 2,) = (Z,) H 2 2,
h(PlZ, * 2,))
where h(x) log x (1 x) log(1 z) is the binary entropy. Thus, could complete the proof by the subsequent inequalities, where the penultimate inequality arises from the concavity and monotonicity of h.
d
T(Z A 2,) 2 d
h
h(P + 2:))
2d
d
h
2 d
h
h
P|Z + 2:1
2d
d
1=1
3k
3
h log ek
d
h
h
2d
8d
100
d
where the last one established by noting that inf
h(x/2) h(32/8) 2 =lg((e/2)
> 0.03.
In the following, will present Lemma 24
connect the relationship between Z and data size.
Lemma 24. Given 0 < < 1, under the above setting, for any c-NLDP algorithm A, we have A = m=222)
Proof of Lemma 24 Since ",,"., ",," are mutually independent conditionally on Z, this implies that
I(ASS") & Σ (Z
Thus, it sufficient to bound each term [ ^ 5.) = 0 222 d
Let fix any S t S n, denote
be any uniformly distribution over {-1,+11 +1] For the LDP algorithm for the t-th user, A, {-1, +1] + +-1,+1j let A,= be the distribution on A = +1,++1 induced by the input V (st, ye) drawn from Paz.cz:
Af2
E Vn-Pa
[Ac(a V)], a A.
We also denote A as the distribution on A = (-1, +1]d+1 where any uniformly distribution over {+1, -11d+1,
E A u--uniform 11 [A,(a w)]. A.
Hence the mutual information for each user could be formulated as:
I S.) Ez KL (4. (4,7)1177)
Ez Xx (A 114
To simplify the notions and make the proof clear, we omit the subscript for W,. 2,, and y here. By the definition of Chi-square divergence and suppose V (x, v), V (a',n/) generated i.i.d from
20

---

Published as a conference paper at ICLR 2024
the distribution u, then:
Ev A(a V) (P2(V) -V=())
Bz xx2 [4f-11A4)
= Ez
Σ
Ev A(a V)u(V)
LOEA
Eu [A(a V) (y(2, 0z))1²
Σ Ez
Eug [A(a V)
aed
Ev, A(a V)A (a V1) 1 (222z(((")))
Bz
Eu A(aa V)l
acA
where the x' denotes the i-th coordinate of We first focus on the last two terms of the molecule. Since Ez[2,] = 0 and Ez [2,] all i E [d]. we could derive that:
k 2d
o² for
{ Σ 22 (a')) (C))))(()t)))
) of
Ez
i=1
Now we combine the above results, the following will hold:
Ev.v'nu A(aa | A)A V`) (Ei= o2g
Ez
x² A AP 11211144)
Eu[A(a) V)]
aEA
En [A(a V)rt)²
022²
En [A (a V)]
aEd
E ( V) + [Aly= V)xt) 2
2 2
Empy=1 1 A(a V) 1Eug--11(( V)
aEd i=1
E B AA(a V)
E 11A=- V)xt13
S 2022²
E A A(a V)
E Buiy=-1A(a V)
aEA i=1
Euly=IA(aa V) |]
|Buuy=-A[A(a V)a'|l
= 20022 aEA
Σ
Emlp= A(a A(a
V)
Enjy=-1A(a V)
We introduce the Lemma to bound the above equation:
Lemma 25. (Acharya et al. 2022 Let Φi : Rdd R. for i S 1, be a family of functions. If the functions satisfy. for all i,J.
E mmifform { +1, 11-11444 172+1
then, for any c-LDP algorithm and = (x, y), we have
Σ Ey (X)A((a vy]² s Vary [A(a|A(a) V)]
Evau AA(a V)x²?
k
Vary [A(a V)]
5
2d
Ev [A(a V)]
2d
Ev [((a V)]
aEA
aEA
$ k
(e-- 11)- By v)}² EvlA(a V)
2
2d
aEA
v²
(e - 1
2d
21

---

Published as a conference paper at ICLR 2024
Hence, we could derive the conclusion of Lemma 24
a
nu262
I AZASS & Σ
(Z,A <
By combining the above lemmas, could have the final results:
d
nu²e2
k llog(
k
d
which implies:
dk logs [c)
3 52
12
E.2
OMITTED PROOFS IN SECTION 3.2
Proof of Theorem For each user i, it is easily to see that releasing J. satisfies (g -DP, releasing Z.lh: satisfies ( )DD. Thus, the algorithm is (e,O)-LDP Moreover, we case see it is
non-interactive.
Proof of Theorem 3 Before giving theoretical analysis, first prove that Σxx is invertible with high probability.
be represented as Σxx Exx Ni = E "हي N1, where Ni a symmetric Gaussian matrix with each entry sampled from N (0, oN, and N, = to start our analysis.
By Algorithm 1 we can see that the noisy sample covariance matrix aggregated by the
log
ne? We present the following lemma
Lemma 26. (Weyl's Inequality & Sun 1990 Let X, E gdxd be two symmetric matrices,
and E X Y. Then, for all 1,... .d, have
- - x S |El|2
where we take some liberties with the notation and use (MM to denote the i-th eigenvalue of the matrix M.
To show E Exx is invertible it is sufficient to show that || 1 - E112 S
This is due to that
2
by Lemma 26 we have
Amin (2) 1|xxx - 2212
Amin (2xx). Aminn (X) 0.
Thus, if 1xx 2112
Amiia (2C) we have Amin (xxxx)
In the following, we split the term |E E112-
1Ê E112 < ||N + +1E Exxl12 + Ell2
where we denote Σxx E प.o. and Exx- E[
Lemma 27 (Corollary 2.3.6 in Tao 22012). Let M Red be a symmetric matrix whose entries maj
are independent for j > i, have mean zero, and are uniformly bounded in magnitude by 1. Then, there exists absolute constants C2 ci 0 such that with probability least exp (-C2cid), the following inequality holds |||]]2 S Cvd.
By Lemma 27 we can see that with probability 1 1- ex))(-)((d))
/2 dl $
2-
| 50
Viee
22

---

Published as a conference paper at ICLR 2024
Lemma 28. nf 2 (d with probability at least
-
V Vallzile log log
|xX8 Σxx/1 :0
Proof. Note that || - Exx11 S | ||2 + |xxxl2 S 2r², And for any unit vector E I
we have the following if denote X Fy
X Xv) =
||: (v (U' E.) - (
Thus we have | X
S ( Since ||(())*((X|] v |B(X) S 2², we have
(r Thus, by the Non-communicative Bernstein incquality (Lemma 20 we have for some constant 0:
[[X EX|T E[X - EX S
P -| Exx
|| > >1) s exp (-omin
n2l2 nl
))
p2
Thus we have with probability least 1 and the definition of we have,
(
Vdlizila log n log
Exx 1xxx-xxx 00
vn
|
We also that |Exx E112 0
This is due
12
|Σxx 2112 - E [( (a,aī" - mxx 1nstb2r]l..
For any unit vector Iº we have
v² E [و x,a5)) || v v= E [B(((()))) (oF 1|x2
|2
< E (u"a;)) [1/ber]] s [o |||xa|le 2 21
where the last inequality is due to the assumption on sub-Gaussian where P([zs) 2 r) S 2 expp(
= nz
3
20
Thus, it is sufficient show that Amin (E) |x.1B/> (1703:² ddl o log
which true under the
Vnc
assumption of Ω ||ll log o log x Thus, with probability at least - exp(-S((d) - g.
22x2 (E)
is invertible. In the following will always assume that this event holds.
To prove the theorem, we first introduce the following lemma on the estimation error of θ in equation
Lemma 29 (Theorem 2 in Yang et (0014)). Suppose we solve the problem of the form ming ||0
0 0|3 + >mn Am/1001/2 such that constraint term Xn is set An 2 0 θ
Then, the optimal solution
θ = Sx, (0)
satisfies:
0 0-
80
0 0"
< LVk2n
0
0-
< 8k2
23

---

Published as a conference paper at ICLR 2024
Note that this is non-probabilistic result, and it holds deterministically for any selection of An or any distributional setting of the covariates zy. Our goal is to show that An 2
0- (xxx)
{xxx) under the assumptions specified in Lemma 29
100
Óerie (D)
0- - (Ixx) (Exx)
10
(8)
(>iex) -1
(Exxx) 0r (2 + Na)
where the vector N2 E Fd sampled from No0, 32dr r2 log 123
La). We first develop upper bound
Vne*
of Egx. . For any nonzero vector 12d, Note that
$ Exxu
Exxw - Ew + Ene
=
[Ew| x - -1(28xx -2)
Nox |>ix - 211,o)
110 oo0.
Our objective is to find sufficiently large such that |5xx Σ
is less than Keg.
From above we see that, we have ||N1l2 < O(VdON)) 0( -0= indicates the following holds:
/d.'Vdlos" by Lemma 27 which Vnee
|ス - - S 11xx - Ell2 + 1|Nil12
72 Vdlog dlog 1.25
Vnea2
where the second inequality comes from Tropp et al. 2015).
The following inequality always hold
| E11o I
vdllis El12
O(" dr /log dlog 1:25
5))
Thus, when 2 Ω
d log dl log 1
Vnc²
2
we have 1xxxu
Rix 1olloc. which implies
($xx)
2 Aoo
Given sufficiently large
from Eq.equation we have:
0 jerio (orte(D) 20
2
[2xx)) 0- - ((xx + N2) No)
<
Kio
(9)
Exy
Σr
+
(
{xxx
Σ
0r
+
N21
Rio
N₂
T3
We will bound the above four terms one by one.
We first consider term Ti. Since and y are both O(1)-sub Gaussian, D(1assub-Ga
denote their th norm by Rx and Ky, respectively. For < j I d, we have Var(D,ā.y) $ E((g,T,y) s (( 2 <
(EE[)))) (B([a,))) (B[ly] J) = [EE لو
A 2 (2= vn co. We have
U1 = O(). Therefore, according to Lemma 18 we have:
2
CT172t
P
T8z, - -8
>
< exp((-(),
24

---

Published as a conference paper at ICLR 2024
where Vzz Ei= Dy Ya, the following can be derived:
Bly and c is a certain constant. Then by the union bound,
2016
CTiT2!
Th
S dexp(-t)..
n
n
Next, we give an estimation
T2. Note that for j.j S d. by lemma 12 we have:
E 1y
E [yy [g
[y E [yaay]]
= E Us (Tay may)] E 1(0s vi mayl
-
v (Tiy =
P P( 2 m1) V V (ūr y1) xt
P ((yvl 2 T2)
=
+2 20
3 voi
2e
20
2e
1 2e 20
which shows that T3 S v0
+ 2e
To upper bound term Ts. we need to evaluate |スxx El..0.00. It can be seen that Σxx = Σxx= N1 = Σx -; + N1. Therefore by Lemma 13 and Lemma 16 with probability least 1 Cd- for all j, < d, and for some constants and C' 'hat depends N,
log
128r 2 2og
12 logd a
log d nie
OEFT, TxOT vsl S v
S 0
yr²
(10)
Vne
We can see that T3 is bounded by Ogdlog ny
log d
)).
Here we used the fact that ||(Exx
ne²
|| 1ス E oc |0"l 1 S 0(2
log d ||0" ||
given the selection of r, where the
last inequality is from Eq 10
The last term of Eq.equation can be bounded by Gaussian tail bound by lemma I6 With probability 1 O(d 5), have:
N2 so TiTyy
d log 1/ log d c/n
(11)
Finally combining all pieces, we can find that T3 is the dominating term. Since An 2
($xx)
($xx) Lemma 29 implies that with probability least Odd -
dlog n / k log d z
|0- - [xx] 1' (Exx + No) 0o
Vne
which completes our proof of Theorem.
Proof of Theorem We basically follow the same ideas in the proof of Theorem 3
First using similar argument, we can show that (xxx) ) exists with high probability.
The following lemma is the concentration result on sub-Gaussian matrix.
2018) Let x be a random vector in Idd that is sub- Gaussian with covariance matrix Σ. and Σ t empirical covariance matrix Exx = En N.co satisfies
Lemma 30. (Theorem 4.7.1 in Vershynin
S Ki. Then, with probability at least 1 - exp(-d), the
Va
d Exx 2/1 C V
||ا|
25

---

Published as a conference paper at ICLR 2024
Algorithm 3 Non-interactive LDP algorithm for Sparse Linear Regression with public but unlabeled
data
1: Input: Private data {(1a Ui)) (IR. x R)". Predefined parameters T2, An-
2: for Each user i E [x] do
3: for j [d] do
4: Coordinately shrink Ti = sgn (rıy) min {|r5), T1
5: end for
6: Clip ū sgn (vi) min (lual, 72). Add noise 7:0: F.D; + 02,1, where the vector n2, IRd
is sampled from (0, 2dr log 1.2 Ia). Release T.U; to the server. 6a
7:
end for
8: The server aggregates Egy # Ei T.y. and compute S 1 Ditn Z5z using
dataset
9:
The server outputs Oerio (D) Sx,, (SS -1 -1 xxxx).
By Lemma 26
and and Lemma 30 with probability at least exp(-I2(d)),
Amin
Xxx
2
Amin
Mig
|
m ).
Kr || La Aniia (2)
We know that under the assumption of m 2 Ω
it is sufficient to show that Amin (E) 2
O Elllaaavd
Vm Thus, with probability at least exp( -s(d)), it is invertible. In the following
will always assume that this event holds.
With the benefit of Lemma 29 we need to show that A, 2 110 (Sxx)) -1 12 x )lx
We know from the proof of Theorem 4 in Cai & Zhou 2012) that |ix.
-
Elooc
Tdg
Therefore when n 2 22( _2d"' logd) we have |Xxx w//xx 2
|| which implies
2
youb XX
1 2. Given this sufficiently large n, from Eq.equation
8
we have that
0r (orte 00
Spuu XX
-1 [ ($xx) 0r -(xx + +NNall
-
2
|1 (S 0" 8-- -5ixx + +N2)
(12)
K00
<
2
Exp - Σxr
+ Exx
Σyx 1la
(
Suub xx
E
0
+
N2
Kio
N2
Ti
is easy to see that only T3 term is different from Equation 9 By Lemmal 16 we can get the following, with probability at least O(d-8), 8), for all < i,j d, for some constant
puu ax" ig
log d n
O uxx is
71
By similar argument in the proof of Theorem given the selection r.
3 we have that T3 is bounded by O(
logd )) |000| I|
Therefore taking π O(ovlogn)) 72 = we can see that the dominating terms are T2 and N₂ thus the result follows.
O (a >, O
dld n log
Vne
26

---

Published as a conference paper at ICLR 2024
Proof of Theorem 5 We follow basically the same techniques in the proof of Theorem With
the benefit of Lemma 29 we need to show that An 2 0r
(5xx)
[ x From the proof
y log dlog + we have ||
of Theorem
when 2 Ω
A
| which implies
$ {xx
Given this sufficiently large n, from Eq.equation the following can be
Keo
obtained:
0r jorio (D)
{xx))
($xxx) 0r (5xx + No) lac
2
||
{ [xxx) 0r - -5xxx + >Na)11a
(13)
Ki
2
|5pp ExF
+ 1
Ex
($xx-1)) 12 0- + V2l
Kio0
T1
T2
T'
Since the new assumption made on ys, T3 is not affected by this difference. Therefore, we only need to examine 7i and T2.
Using similar arguments, we can see that Ti is bounded by 0 ( and N₂ is still bouneded by O
m
miray /dlog//ooooooooooool do with high probability.
c/B
We bound the terms E
[ ky
E
by
max [ E
E
E
(E [maa]] 1-
< <2Mbnsp/ 1) <
which is constant that we denote by v. Note that for 1 S j d, by lemma 12 and Markov's inequality, the following holds:
E T.p E [yg
=B E [.
E [ī 1ys E [yerag)
Elūe (Vig 2.i )1 + TE [ūt Di) masl
S
?? (Tey )2a))]
P (1xayl 2 TI)
(ū: v1)²² 2
(lysl 2 T2)
E
SVD
2e
20
2p 2
7
v M
<VU
2e
20
+2 2
which shows that Tg < V
2e
+
2/M M *p
n # completes the proof. Taking 72 (log
E.3 OMITTED PROOFS IN SECTION 4.1
Before presenting the full proof of Theorem 6, we first introduce several necessary definitions and assumptions.
27

---

Published as a conference paper at ICLR 2024
Definition 7. For distributions P1, P2 over sample space X, denote their Dallback-Leibler divergence (in nats) by KL P2), and their Hellinger distance by
2
dP dd
dP2 dd
dh (P) = \ 2
dA
Definition 8. Let Z = (Zi...., Za) be a random variable over 2 = (-1,+1) such that P PIZ; =1
T for all E (d] and the Zi are all independent; we denote this distribution by Rad(r) sd For E Z, we denote z E Z as the vector obtained by flipping the sign of the i-th coordinate of
Assumption (Densities Exist). For every E Z and E [d] it holds that P.e. Pa (we refer to Po. simply as P2), and there exist measurable functions 02, Rd - IR such that
dP. dP
11+ 2z.i
Assumption 5 (Orthogonality). There exists some a² such that, for all z E and distinct i [d], Pp,, [dh,; ΦzJl = 0 and Ep. 12,1 a
Assumption (Additive loss). For every 2, E +11,
[diam (z, 2¹)
1/2
bg (0,, 4v
Td
where dHam (=,d)===ie 12 # 2/} denotes the Hamming distance, where = k//2d, lo and denotes sparsity and error rale respectively.
Proof of Theorem 6 Similar to the con-interactive setting, we consider the hard distribution class Pk,d22, where for each instance Po.ç E Pk.d,2, its random noise Ç satisfies Biç x] 0, K<l S 2, and
|10|] S 1 and ||0||o S hold. By setting 7 = dv and defining 0z,5 = 2
+1 for E [d]. {
vk
realizations of the random variable Z E { 1, +1]d, where each coordinate Z, independent to others and has the following distribution:
P (4 11 k/2d,
P PiZ: - = kk/2d
We will first show that 0₂ satisfies the conditions that ||0|] and |l@l|o S le and 02 k-sparse with probability of 1 where k/2d by the following fact.
Fact 1. Acharya et al. 2020 For Z Rad(r) and rd 2 4log then we have IP 21 2rd) 2
1 - r/4, where 7 = E (d) 1).
When 0₂ is k-sparse, we can also see |0_|1 S 4v 2kv S 1 as we assume S
4v2K
Next, we construct the following generative process, we first pick z randomly from (-1, above. For each Z we let:
{
1- (z, w.p. 1+ (a.0.) 2
5. -- 1 -1 02) w.p.
(x.
2
Note that since (r, 0-)1 < Vk.y= 4v2v- < 1. The above distribution is well-defined and
Iszl < 2. We can see that density function for (2. is P. Poz.s. (x, 1+g(2,0.) for
2
(x, v) E (-1,
In the subsequent, we will confirm that P. under the above constructions could satisfy the Assump- tions
dP
+ y (x, 0gar)
(I, 0gei 0z)
dP. 1 y (r, 02)
1 (2, (x,0z)
0 - 02 = 0.... 7( (-x+1)
7 (2, +1
0.. = (0, ..,00.0...... 72c, -..
2
2
28

---

Published as a conference paper at ICLR 2024
Thus, could simplify the previous formulations as:
dP
y7242
=1 1 y 0z)
dP.
Let az2á I+ Since 02) & &Vll| & 1/2, we have dzs hand side denoted as a.
1v2v 2v
where the right
Now there exists measurable function 0z,4 - y with E [d2, dzal = 0 if i + j and
[yn] = = 1 i j. indicating that assumptions 4nd hold.
Lemma 31 (AAcharya et al. 2020)), For a e-sequentially interactive LDP algorithm A and any family of distributions {P=s Po ((x, y}}} satisfying Assumptions 4 and let Z be random variable on Z {-1, +1] with distribution Rad(T)@4, Let S be the tuple of messages from the algorithm A when the input Vi = (21,81)...... Vn = (In, yn) is iidd with common distribution Po Po. then we have:
d Σ 1=1
drv (Ptt, (2.) ) 2
S naa (ce-1)) 1)211)2 Aee)
(14)
d
where PS = E PS. Z; +1 :=:====: := PSS 12 11 In Eq.equation 14 the left-
hand side is defined as the average discrepancy, which represents the average amount of information that the transcript conveys about each coordinate of Z.
With the assumptions holding and introducing the Lemma31 have the following conclusions for our LDP algorithm and constructed distribution:
(2 D drv (PST )) I ?_aa?? where
2v2u Next, we will verify the remaining assumptions that should be satisfied for the lower vi
bound of ( (1 drv (PfT.PS7] Since
- 02 = 32v d
1 1(7 # 2,) = 4v (ditm(z.s)
1/2
thus the assumption holds for any 2, z +-1 with T = k/2d.
Lemma 32 (Accharya et al. 2020)). Assume that Po..s. (Ir,)) satisfy Assumption 6 and k/2d E [0, 1/2]. 2]. Let Z be random variable on Z = +11" with distribution (ad(T) if algorithm A an e- sequentially interactive LDP algorithm such that, for any n-size dataset (:) consisting of i..dd samples from Poz. with the probability Pz [Po..s. E Pk.d22) 2
1 1/7/4, and its oulput (priv satisfies [[[]iprii 00 S v, then the tuple of messages S from the algorithm A satisfies
d
(pS- pSn) +1+
drv
2
With the fact of 02 is k-sparse w.p. - 7/4 and assumption Gosionn/hhooaa (holding it is easy to obtain that lemma applicable for our sequentially interactive LDP algorithm.
32
Combining the above results, we have:
1 < drv (pS" .p5.)
7
dk
which implies n 2 ( de
29

---

Published as a conference paper at ICLR 2024
E.4
OMITTED PROOFS IN SECTION 4
Proof of Theorem 7
We first show the guarantee of e-LDP. First, we will show that | (((;;, 0t 0)- - B0ll2 & vdn (VhT + T2), this is due to that
| ((21,001) - 71)l2
< | lla ( 0-1) - -il)
| lla (IVA 1abb:100--111 - Tel) S VVTi(VIT + T2);
where the last inequality is due to that 0 is k' ssparse,, 110--112 I 1 and each || T1. Based on this and Lemma 8 dataset, we can see sequentially interactive.
easily Algorithm 2 is e-LDP. Due to the partition of the
Next, consider the utiliiy. Without loss of generality, assumee each [St] = 3/. From the randomizer RT (-) and Lemma 8 we can see that V. - m Eies, o.. ((Tr,0--1) - T1)) + dr. where
each coordinate of de is sub-Gaussian vector with variance = O (dTP(K((tT)))
Let S = supp (0*) denote the support of 0", and = |S Similarly, we define S = supp (0:). and jrl1 =
US. Thus, we have | < 2k' + k. Let 0 denote as the following:
0 = 0 1/ 1-1,1
where U means keeping 2 for E Fi-1 and converting all other terms 0. By the definition of Jt-1, we have 0f 'Trune (0._..h²)
For each iteration we also denote L (0(-1) m Eies, 3; ((2,,81-1) (.). 7 (0t-1) = 1/2 Eies. F; (1rg, 0z-1) v:). and (Lp(00-1)== = E(x((x, p - -)]
Denote by A, the difference of 0, 8" We have the following:
000 - 0- 00112 | v/ll12 || v Ve 1|2
D
7 LL (0, 1))--1))--1111 V ViFe-1
We first bound the term B. Specifically, we have
| - V (V = - 10-11
|| 1 (01-1)
s M|-i (| I (0c-1)
V Vh- (0 + -10xelloo)
B1
Br
For term B2, by Lemma 15 we have with probability least 1 - 8'
(TiVdk + TIT2 Vd) / log
B2 5
(15)
Vmc
For B1, we have
B
< sup
LLp + sup
Lp
| 11
[0
B
B1.
Next we bound the term B1.1, we have
sup (Q)=1(0)) - (LP(O))l S sup |I|
1
Σ
Fxx
0
+ sup
Σ
a
Ejryllls
[|0 51
51
m
||0|| 51
m
1=1
30

---

Published as a conference paper at ICLR 2024
1
E
00
F.y E[ryy] 1oxc.
172
m
We consider the first term
|1 Li=1
Eiax' E[rx"Illoo.o I1lbo,,0 for simplicity for each j, E [d]
denote ōzk = ( Ei= " j = 1
Di= FigTi,k Ozk (B(2*"))s = [B(z and ask
(Elax²")) 1)sk= = E We have
1ōyk - Jyhel & 1k - ومووة + 1zsk - ozkl--
We know that ا S oी and Vār( & Var(z)22)) & B(2,01) S O(o4). By Bernstein's inequality we have
P(max Jā,k 8z S CV 3.k
+
2 d² exp(-1t
(16)
m
m
Moreover, we have
josz Jjkl = -iil - x* )
2 m))
- 23 -z
2 T))
< (īx In 2P( ([a 2,)x) m)
s 00 )
where the last inequality is due to the assumption on sub- Gau-Gaa where P(|xy] 2 71) s 2 2exp(- + 202 O (āx =x))² < 4E(z)ax))² I O(o*) and E((i, 2z) 5
4B (2(2)xxx)) S ((a)). In total have with probability least 1 - 8
0² log n log Vm
2. - -B(re"
[] S 0
We can use the same technique term
1 Σm= 3.04 E byy loo for simplicity for each j e [d]
m
denote d5 = >x U. ōj E gū, and 0, = Elyx, J. We have
|Ø, o,ن < |6g o, + |,, ozl- Since الاسا| S T1 and we have the following by the Holder's inequality
Var(ū,ū) = Var(I,y) s E[ < (EIr") < 0(04)
Thus, by Bernstein's 's inequality we have for all j E [d]
P(Gē, - o, s sly cov/=t got
n2t
+
1) 2 1 dexp(-t).
m
m
Moreover
|8, o, S - 21
ml + E| 1) 2 r2)
< V B((i(T, - 22)))(((3112))) ( T2)
x 00 + 1
we can easily see that with probability at most - 8',
02 log n log +
m Σ a. E(zylllo =0(00
(17)
/ m
Thus with probability at least 8'
B1,1 < 0 o² log n log #
(18)
mm
31

---

Published as a conference paper at ICLR 2024
Next, consider B,,2, similar to B1,1 have
sup |
[VL;-1
(L - -
E xaae - B|rx" bo, +
1
Σ rit
B|ryll
For term we have
|| Σi=1 1qa0
E [rrra""""llooo oo by Lemma 13 we have with probability at least (cd
n m a5z; E|rx" I| S s0(
log d m
For term || | Ex= Fiye E[ryl] boo consider each coordinate, 1 that 2y is o -ussuGGaa and y o'-sub-Gaussian, thus, by Lemma exponential with |ااااع $ O()²). Thus, by Bernstein's 's inequality, have with probability at least 1 - C²
Ei=
Ti E[zyy]. Noted
m
10 we have zyy is sub-
m
0² 22 log 1/8
Figl E[z,a|l S 0
m
Vm
Thus, with probability at least
- 5¹
Vlog d/8 /m
Tili E[ry]lxx S s0(0
t=1
Thus, with probability at least Odd-)) we have
B1 S 0 Vlog d Vm
and
Vlog d Vm
B1 S 0
Thus, we have
(T VdW dl + 12T22
log 8'
B OSO
22K +
(19)
Vine
In the following, consider term A. Noted that we have y/ (r,, 0-) C. thus, have
A 1/ 1 1113 S | 71 m
(o (m,((1;,00-) (11000001-00) 001) xgGi)) 11l2
1 (1,((a,, 0")]]/-~1112 + |
< |
Σ 2:ooloo
We first consider the term m Em &.lol Specifically, we consider each coordinate j E [d]
J Em Cel. Since E[G:] = and is independent on æ we have E[Gar,] = O. Moreover, we have
|| < [2,, 1 + llullo, s O(a) 0(1)
Thus, ||co|le, O((2) by Lemma 10 By Bernstein's inequality have
G 0 11yllo
log 1/8
(20)
Vm
Thus, with probability Odd-o) we have
llogd Vm
Σ
S.Cillos I 0
m
T=1
32

---

Published as a conference paper at ICLR 2024
Finally, we consider the term
||Ar-1 ml
Σi= (12( 01-1 0-)) 12:
|| 77| m
1
Σ
m
(1r 001 1|12 = |1[(11 1 1 ) 11l2.
where D 1 Eies, ب. Bddd Since Supp (D' A1-1) F-1 (by assumption),
have A
- - 1 A |1 nD 1, .) || 12lz- Next we will bound the term
|| (T-nD DD-nDDe-I,FFE 1l2. where is the | -iimensinl identity matrix.
Before giving analysis, we show that each of the partitioned dataset safisfies the Restriced Isometry Property (RIP) defined as follows.
Definition 9. We say that a data matrix X E Rgnx satisfies the Restricted Isometry Property (RIP) with parameter 2k' + ki if for any I2 with ||ollo 2k' + k, there exists a constant which satisfies (1 - A)||u|? S t. |
2 S (1 + 1)
The following lemma states that with high probability, where is some constant each Xs, on our algorithm satisfies Definition and thus we can make use of this property to bound the term
D D1-1----
Lemma 33. (Theorem 10.5.11 in Vershynin (2018). Consider an n x d matrix A whose rows (A₂) are independent, isotropic, and sub- gaussian random vectors, and let K max; | Assume that
N CK* s log(ed/s).
Then, with probability at least 1 - exp (-en/ K*), the random matrix A satisfies RIP with parame- ters s and A 0.1.
Thus, since {a;} are isotropic and || I O we have with probability at least 2T exp (-cm/o"), {Xs, all satisfy RIP when m 2 OoO((2 + k)). By the RIP property and [ < 2k' k, we obtain the following using Lemma 33 for any [iime--dimnnnoonal vector
v
0.91 < x" D'' 1. S 1.1///112.
(1-
112 < max (1 -7 17- 0.9, 1.1 - 1}. This means that we can take 7)
Thus,
O(1) such that
(1I- 1,51 1) 111p=
2 -
-
In total we have with probability least 1 Old-9)
(Ti dk rrravdd log 8
| 00112-
10-4--011, s 2
112 11 V2k +k
(21)
/e
Our next task is to bound
110, - 0-112 by
0 2-
- -0-
by Lemma 21
Thus, we have
2
00 8/_ 1/2 E -
|
0 0 gr
2
<
0 -- 3
2x
2
Taking 1/' = 8k, we get
00g 0 0-
112
3
00_ 0-
4
and
( (T/V
dk + m T2 va) /y /11 d
110% - 80112 < 7 2/10- 0 - 0-
<
+0
Vk
4
me
33

---

Published as a conference paper at ICLR 2024
Finally, need to show that |اهlع| ||0 1111 - 110 - 11. which is due to the Lemma 22 Putting all together, we have the following with probability at least 1 O(d"),
(VR
log ny T log
1اله| - | +
Vnee
Thus, with probability at least O(Td=) we have
( 1100 +0
(bloog ny / Td log d
A 12 <
Vnc
Take T = (log nt). We have the result.
F UPPER BOUND OF LDP-IHT FOR GENERAL SUB-GAUSSIAN DISTRIBUTIONS
Algorithm 4 LDP Iterative Hard Thresholding
1: Input: Private data {( 81) (IR" x R)". Iteration number T', privacy parameter step size 7) truncation parameters т, Ti, T2, threshold k' Initial parameter 0g = 0.
2: For the i-th user with
[n). truncate his/her data follows: shrink x; to ã; with T.j agn (z4)) min {Raygl ri for j E [d]. and Dü :- sgu (wx) min {luel, r2). Partition the users into
T groups. For t= 1 .... T, define the index set S. = ((1 - 1) [ + +1... [ if T,
then S, S,
Ut
+ 1....
3: for = 1, ... T do
4: The server sends 0,-1 to all the users in S., Each user i E St perturbs his/her own gradient:
let v o.= ((0-1,,.) Rx) ((
71). compute 2; = R5 (V,), where R. is the randomizer defined in equation 6 with r = =vdr, (2v + T2) and send back to the server.
5: The server computes V.-1 = [ Eies, 2 and performs the gradient descent update 0 =
8 no V-1-
6:
8 = Trunc k.).
7: A. ar argaeB: |00 0'112--
8: end for
9: Output: 0T
Theorem 7 establishes the upper bound specifically for isotropic sub-Gaussin distributions. However, we can also demonstrate that the aforementioned upper bound also holds for general sub-Gaussian distributions, albeit with different parameters. Notably, for general Lub-Gaussian distributions, we need to slightly modify the LDP-IHT algorithm (Algorithm{). Specifically, rather than projecting onto the unit normr ball, here we need to project onto the centered f2-norm ball with radius (actually, we can project onto any centered ball with radius larger than 1). See Algorithm 4 for details. Such a modification is necessary for our proof, as we can show that with high probability, |0%|12 <. for all E [T', which implies there is projection with high probability. Since use a different radius, the fz-norm sensitivity of V, also has been changed to ensure c-LDP. In the following, present the theoretical result assuming that the initial parameter 6g is sufficently close to .
Theorem 34. For any > O, Algorithm f is e-LDP. Moreover, under Assumptions 7 anndd 2 if the initial parameter 0g satisfies |10g 11 S 1 and is sufficiently large such that n. 2 9 kdd
setting 170 35.
2. k' 72 2 k. with probability at least 1 8' we have u
dik log² n log %
||0r 1- s O
Vne
where 7 Amax (E(xx"]),
Amiin (E(xx big OO and big-Ω notations omit the terms of a,
and μ..
34

---

Published as a conference paper at ICLR 2024
Proof of Theorem 34 The proof of privacy is almost the same the proof of Theorem 7 The only difference is that here we have V S vdtı (2Vk'T + r2). In the following, we will show the utility. We first recall two definitions and one lemma.
Definition 10. A function f is L-Lipschitz w.r. the norm II- if all w, w/ W, [f((w)) - f(w')l L| w'll
Definition 11. A fanction I is o-smooth on W for all w. w W. f(d') (w) + (VI(w): w w) +
2
Lemma 35 (Lemma in Jain et al.
(2114) For any index set I, any E R| let ū Trunc(u, k).
Then for any V* R11 such that
[ llo
S k- we have
I k 1100 - -012.
|| w11= <
(22)
1 k.
For simplicity we denote L( = [[((,, 03 -} L = 1 - (((,00-1) 0,_1) 8). L(c-1 = VL(0,-1) = Elz(( (x, 02-1) - y) 5t-1 supp(0, (0-p( St supp(0;). S = supp(0") and l
S' "US-UU* We see that | < K, |St < k' and [T"| 2 + K. We let 7
Amax B|x [], F Amin (B[rx"" "J) and 170 = - for some 1). We can easily see that L(-) is p-strongly convex and y-smooth.
Then from the smooth property we have
I(O)) I(Ox-1)
S (8, 81-1, (L-11 + 1100 01-112
2
-0%,, 01-1,1,, VL-1111) + 2 2110%. -
11²
S 2 $100.11 - 01-1,11 + " VL 1,1²
IVI,, + (1 (0 - 02-1, Vla-1) (23)
27
First, let focus on the third term of 23 By Lemma and the definition, know that 02 can be written as 8g 0r,s: + Øi, where 0. (6.-1 no VL.1))s and de a sub-Gaussian vector with
variance 0 dr (K'7 me²
Thus,
00 0,-1, VL (0r.st 11 VL-1188
+ (o, VL - (9,-1,5t-115 VL 1,5
(24)
For the first term in 24 we have
(0r.s O2 1,94, TT 1.9+) (-700 VI,-1,,, VI+-1,s::)= = (VI4-11,8 Vin-1ss))
! V 112
!!
(VL VL.-1,8 V..-1.s))
7.
S --11VVL-1155
17
V
112
! | V4
2%
27
11 1
11
V
(25)
24
27
Take (25 into
24
we have for >0
(0, - 16--0-1, VL-1) --
"
|
17
VL - VLL-1.S
2
27
(26)
+o st 112 +
| 1 (0-115t-115 V (1))1,
401
For the last term of (26) we have
-01-1,5:-11555 V (1-118
35

---

Published as a conference paper at ICLR 2024
7.
(100--1.t-1118--
"
VI.
-1 -
27
7
110,
101-1,95 1,81-1188
" "L
111011 24
111-1155-1.511
211
S
11 (1 +
122
+ -1-
2m
- -14-1197851
27
C)
VI 12
(27)
27
where the last inequality comes from
111122 ! V
10ss 188
118t L 118 01,,5-119111
< 110--18--115
( - -- + 2r s
17 < 110-1.891 (VL [V + s 17 L., + t
2 V4.-1.94 1||2 ! VL. F4.-1,5488 s =112.
where the second inequality is due to the fact that st = 1st111s5"1 the definitions of hard thresholding, 6% (0:-1 7(L + oi))s, St and 5t-1; the first equality is due to Supp(0,-1) 5t Thus we have
1,5- 1,5t-1-11
7
VL. - 1, 4
21)
7
1 1
2n
<
27
We can easily see that
7
V
112
11
V -
|
L
27
27
27
11
11
V V4--188
27
27
"
V 11/2
=
27
In total
- -0,-0--1, VL--1)
< 27
112 +
121 +
1 ?
112
7 1 1
VL--1.5
4c1 2y01
2
2n
+ &ill 112
11 (28)
Take (88
into 23
we have
L(O) L(0.-1)
? S
1106
11-1,11
1 V L, 1,1
1
V L, 1,7
+ (1-
06-1, VL--1)
2
27
$ 7 110 01-1,1'
7
112
n
(1 (1-1)m
2
7
27
27
+(1 - m)(
1
+
71
|||
V
V
112 (1 - 11) ?
V 7I=-1,8:122
Aci
27c1
2
27 (1 + LL1,1VL11,
V44-1,84,8111
7
< 2
3110, 0,-1,14 + 7
!
VL,-1,11
1²
|
2
36

---

Published as a conference paper at ICLR 2024
V V (1-1)y
1,
Ust
27
2
+ +(1- n)(
1
?
V
12 + (1 - 11) 7
+ s
dc1
2
24
20 (1 1
+ 7
V44-1,544
01,54,,5-1115
7 2106,,1 81-1,1'
7 -
1/2 112
1 VV (15-1,(8-UUS)))
VV US.)
2
7
27
27
(1 (1-1)1 V VLL-1,55(18-SS 1|2 + (1 r)){
- +
1
| L 12
27
Aci
27c1
+ (1 n))( "1 V
- Vh.-1s 12 + talborss 112 +
27
+ a))
VL4 1- Vh--1,44 1 - -rs 112))
27
Ng
(29)
where the last inequality is due to S* (5* y US Next we will analyze the term
3110% 1,- + ž/ V L, 1 3/m VVL-L/((8-
(9)
Let R be subset of Ss such that R definition of hard thresholding, we can easily see
Us* (S* By the
" -)) 110-1,R - 7) ( + 2) (0,1
7
(30)
11 (6 + +0) n
Thus have
2 || V L1 (S-UU--
11 1,-
VT, 1. 1222
71 2(VLL-I. Vh- de,1el2
?
(31)
VLL - (4.-1,1((0 11, ( (12-))12))
Then we have for any 02 0
2 1100,,- 01-1,1'
2
77
VL
172
| V 1. -SS-) 1
27
<
I 310 -1-111--
1
13
7 2
(b
c)2 +0²
2n (b + c)a)
2
7
2
22
7
7 $108,1I 01-1,11 +
17
V 1,
112
7
1
)a²
+
(202
1 1²
(b + c)²
2
7
2
2
2 ア
2100 ,,RR - 01-1.1 + v
L
+
00-1,8
2
202
7
+ (4c2 - Th
(1 1r
+ V
- - - -.1' US{-
(32)
< 2116%,1,. - -1-1,118 + V 1. + I ||0,11,
! (VL + 2
2
+
|V - (İL-11R + 21 +
(33)
22
N5
37

---

Published as a conference paper at ICLR 2024
-00 - 01-1. - + "V L 1.. +N2,
N2,
(34)
where 32) is due to that 01-1.R O, thus |10/_1. (0.-1,8 V
1|0-1,
VVL-1.R 1.8- l2. In the following, we will consider the first term in (34).
In Lemma 35 take 01-1.14n (VLL-1,, + 11-1, ū= Truncuu,k) 01-1,1900
1= R.
0nn - 0-, we have
! (/
PAR k/ [ k
10 02-1 7
Then we have
1
116 110 - -1-1,11 + LL 1,70112 (cs 1) 72
(1
VL. -L, -
C3
7
72
110.1'A -0-1118R - 14-11111
[ -K 110- - + " L4-1,11
| -k k
I'AR| R k'
(1+ - )110 -0-1, + V + (1 o3) - -L-------LL------------- - 01-1.
1 R - k
C3
Since 17 S 2k' and k² h we have
1 | S
k'th
2k'
S
k+b
2k'
Thus
110 0 + 7
2k
C3 c1+1 10 - -0--11
V L, LI-II
7
+ k' C3 -
2k
2
+ +(1+ c3)
+
03
1)
ALLLTN -
k k
Take c3 5 K' = === O(k), we have
100 - 01-1148 +
V VV.-1// -
3 2k:
1 -
- " VL VILIIA
2 ks + ks
y
+ +0 7/2
VL 1
-
(35)
Take 35
into
34 we have
3 1100 01-1,16
7
17 "V..11,11
V V (
7
27
< 37 k 1 - -0-1.. + "
+ +
(36)
2 ke k
Take (36) into 29 we have
(()) L(0--1)
7
110%
-0,-1,1-
+ 7 7 LL-1I.111
172
V
Us-))
772
2
7
2
2-
(1 7)m
Us+ U 112 112 +
7){
1
+
77
)||
V
+
27
4e1
27c1
<
37 k
|10
1,
" -V ,,
1/²
|
VL,
(S
2 kv' + k
?
27
(1 7)
11 + (1 7){
+
V
L, 1 11 1 1 +NN + 7N3..
27
4cr
2
(37)
38

---

Published as a conference paper at ICLR 2024
Note that when 7 2 2/2 there exists sufficiently large e1 is such that 1.
+
n 2y0
S
y. we have
4c1
(1 n)(( 4ei +
"
V 1.5t
711 - 11
V
1,5
2701
47
1
(1 (1-
47
47
Thus
I(#)) L(f(-1)
37 k
110-
01-1,1R +
! V 1.L--ll
"1²
V 1, USS-
k +
?
27
(1 -1)mm
7/m
(1
1 11
/ 11 + No + N22 + NN3
27
4e
37 k
" ?
|10
1
8
|
2 k' + k
47
(1
7/m
>> + No + N3 +
47
It is notable that by strong convexity
3y
k
10"
11-11
"
7 7
L
k
3y k
1100 -02-1,1* + L
2 k + k
37
112
2n (0) -0,-1,1. V (((-111)
(110- - 00-1/99122 +
V
2 W + k
722
7
37
1/2
21 (0* - -0,-1, VL+-1))
(110- 0 00-1111,11
+
V 1
+ 7
2 W/ + k
72
3k ? 110 00-1112+ +
V V 112 + rl((0)) L(0,-1)) - 7/1 110 02-2 112)
< 3. + k 2
27
2
Take 17 2. K 72 so that
3k K+E
<
2 nue g. we have
L(6)) L(0--1)
k + (m((T(0)) - T((0-1))+
3k
7-1
7- 7/44 110 - -0--112++ +
1
V V4
2
27
|L 11s-)112- (1
1)11
VL4-1,5440 Us! 12 + No No + 7
4y
47
2k
1
(L(0") - L(0--1))
+ 487
110
0,-1
+
W. + T
367
1
|L1-1,181-1
VL
V -
11 + No. + No. +
9-
18y
2k
3
22 110 θ,ー 12 + No. + No + +
k+k' k' (L(0") - L(0c-1))
(1|
1, Us- 1
367
(38)
2k
P -(000) + No6 + N₂ + 7N3
(39)
k
24-
Where
388 is due to the following lemma:
Lemma 36. [Lmma 6 in Jain et al. (014
2
010 - - 2 11 (L(()_1) - L((*)).
V LL (L
(40)
4
2
39

---

Published as a conference paper at ICLR 2024
Thus
p (L((,-1) -(0))) + No + N2 +
L( - L(07)
(1 =
7
Next, will bound the term Ng + N2 + y.33. For Ni we have
N2 (1 (1-n)()) 7 1.. VL:-1,s=113
+ ea 11,5 11 + 211 (1 + 4)) V -11-118- - -
=0 VL-Il 1k)1)1)11e).
By equation 18 know that with probability least 1 - 8'
| V4l-l 3 0 0² log n log
(41)
vm
Moreover, by Lemma 15 we have with probability at least 1 -
(FRVaN + +TTaaVlll log $ @0el 50
(42)
mTEE
Thus, with probability at least - 8' we have
N2 0 a d log d/8 8' log" n
mc²
Similarly, we have
Adk!
log d/ log" n, me²
N2. No O
Thus we have with probability at least 1 8
11 (L((-1)) L(0")) + o 00 d' log d/0' log² d/o'log² n 72
L(O)) L(0*) S1
(43)
me²
In the following we will assume the above event holds. We note that by our model for any 0 7110 0- > ((0) L(O") 2 1|10 11.
In the following will show that 8, = 6% for all t. We will use induction, assume 0; =6 holds for all i E [t 1], we will show that it will also true for L. Use (43) for i E [I [J we have
5 5 (1000-))
+ 00 Adk log d/ log² n
ml10 0-1 < L(O)) -(O") (1
727 72-
me²
Adk! 1 log d/6 log n
5 11 (T.(0)) I(0))) 00
(1
72 7
mc²
5 - - 110 1- 0
2 o dk
log d log"
< 71
727
/
me²
When 100 11 < 14 and n is large enough such that
do
n 2 Đ2
112
2
Then |10/122 S |10*1|2 + / + < 2. Thus = G.. So we have with probability least 8'
- " (L(0n)- L(O))) O dkk 2T log 8
dI log²
ul10% - -0'1 < 1(00)) L( s
ne2
Thus, take T = Ō lo and A' = =(())²k) we have the result.
40


Reviews:
[{"review_id": "VCB68tqTzO", "reviewer": "Reviewer_qQ5H", "summary": "This paper studies sparse linear regression under local differential privacy. Firstly, it establishes a lower bound under a non-interactive LDP protocol for sub-gaussian data. Secondly, it proposes the first upper bound that has a $\\sqrt{d}$ gap compared to the aforementioned lower bound. It also demonstrates that this gap can be closed if public unlabeled data is available. Lastly, in the case of sequentially interactive protocol, this paper presents a lower bound and corrects the results of the iterative hard thresholding algorithm from prior work.", "questions": "1. Is the l2 norm the right metric for linear regression? For example, Cai at el (2021) consider $\\|\\theta^{priv}-\\theta^*\\|_\\Sigma$, which corresponds to minimal emprical risk. Do the results also hold under this normalized metric?\n2. Is k used in Algorithm 1?\n3. Regarding Remark 3, is it necessary to release the covariance matrix privately in LDP model? Can you privatize the two terms in OLS solution together?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is thorough and clearly written. \n2. The problem is well-defined and important.", "weaknesses": "The upperbound and lowerbound do not match. It is unclear which bound is tight. Also $n$ has to be greater than $O(d^4)$ to achieve a rate of $O(d)$ in Theorem 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "O16uFRHQN5", "reviewer": "Reviewer_UbUb", "summary": "This paper studies the problem of sparse linear regression under the local differential privacy setting. The authors provide new lower bound results for this problem with a $k$-sparse underlying model parameter. In addition, the authors develop efficient upper bound algorithms for the same problem.", "questions": "Here are some additional questions I have for the current paper:\n1. For the Remark 2, why the authors claim that the sparse linear models in the non-interactive LDP setting are ill-suited? It seems to me that the dimension dependence in Theorem 1 comes from the norm of the data, what will the result look like if you assume the data vector to be $\\ell_2$ norm bounded? In addition, the results in Raskutti et al. 2011 and Cai et al. 2021 seem to assume the data vector to be $\\ell_2$ norm bounded.\n2. For Theorem 3, why do you assume Assumptions 1 and 2 holds simultaneously? In Assumption 1, you assume $x$ with covariance $\\Sigma$, and the transformed data to be Sub Gaussian. In Assumption 2, you further assume $x_i$ has variance $\\sigma^2$. In addition, what is the assumption on $\\zeta$?\n3. If the lower bound has nothing to do with $\\ell_1$ norm bound, you should give the results in terms of the $\\ell_2$ norm bound. \n4. Whether the upper bound results can be extended to the $\\ell_2$ norm bound case?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The strengths of the current paper are summarized as follow:\n1. The authors provide new lower bound results for sparse linear regression under local differential private model.\n2. The authors develop new efficient algorithm for solving the same problem.", "weaknesses": "The weaknesses of the current paper:\n1. It is unclear the dimension dependence in the lower bound is due to the hardness of the LDP setting or the norm of the data.\n2. It is unclear why the authors need the $\\ell_1$ norm bound in their results.\n3. It is unclear why Assumptions 1 and 2 are both required in the upper bound results.\n4. Why it is reasonable to consider the sparse model in the classical setting?\n5. The sample complexity requirement seems to be very bad in terms of $d$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eYQQuAJgIe", "reviewer": "Reviewer_ZWvr", "summary": "The paper studies sparse linear regression in the different local differential privacy models (LDP). \n\nFor non-interactive LDP they propose an algorithm with estimation error $\\tilde{O}(\\frac{d\\sqrt{k}}{\\epsilon\\sqrt{n}})$, and show a lower bound $\\Omega(\\frac{\\sqrt{dk\\log d}}{\\epsilon \\sqrt{n}})$ (for sub-Gaussian covariates). In addition, they show that it is possible to improve the upper bound by a factor $\\sqrt{d}$ given public unlabeled covariates.\n\nFor interactive LDP they propose an algorithm with estimation error $\\tilde{O}(\\frac{k\\sqrt{d}}{\\epsilon\\sqrt{n}})$, and show a lower bound $\\Omega(\\frac{{\\sqrt{dk}}}{\\epsilon \\sqrt{n}})$ (for sub-Gaussian covariates)", "questions": "Your proof of Theorem 7 looks very similar to the proof of Theorem 9 from [1] (and you mention that). Could you please explain what are important differences, assuming linear regression settings? (I didn't check the details, so maybe I missed something). From the first glance it looks like the proof from [1] works not only for the uniform distribution, but also for 1-sub-Guaussian distributions (modulo their wrong bound in the very beginning), and if it is the case, it should also work for you settings, or did I miss anything important?\n\nAnd one minor thing: I suggest to move Table 1 to the introduction.\n\n[1] Di Wang and Jinhui Xu. On Sparse Linear Regression in the Local Differential Privacy Model.\nIEEE Transactions on Information Theory 2021", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "There are a few new non-trivial results that improve over the state of the art. The paper is well-written, I really enjoyed reading it. The contribution and comparison with prior works is clear. The idea behind Algorithm 1 is very nice and seems to be new (though I'm not an expert in the field, so I'm not 100% sure).\n\nIn addition, they found and fixed a bug in one of the results of prior work [1] on the iterative LDP settings that implied an incorrect upper bound. I briefly checked it, and indeed Hoelder's inequality in the proof of Theorem 9 is used incorrectly there, so it is good that this mistake was found and fixed.", "weaknesses": "I didn't find major weaknesses. However there is one thing (which I formulate in the Questions below) that is confusing to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)