Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model

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 ǫ non-interactive LDP model and provide a lower bound of Ω( 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 to preserve privacy when sharing aggregated data. Traditional data analysis techniques such as linear regression often face a number of challenges when dealing with sensitive data, especially in social research [38, 10, 9] . Differential privacy (DP) [22] has emerged as a widely recognized approach for privacy-preserving, which provides verifiable protection against identification and is resistant to arbitrary auxiliary information that attackers may have access to. Previous research on 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 Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model A PREPRINT data analysis. This paradigm is exemplified by Google's Chrome browser and Apple's iOS-10, which collect statistics from user devices [45, 24] . 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, resulting in many fundamental problems remaining unanswered. Linear regression, a 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 θ ∈ R d that minimizes the empirical risk L(θ, D) = 1 n n i=1 ( x i , θy i ) 2 or population risk L P (θ) = E (x,y)∼P [( x, θy) 2 ] of the given dataset D = (x i , y i ) n i=1 , where P is the underlying distribution of (x, y) with covariate x and response y. In the latter, it considers a linear model with covariate x and response y that satisfy y = x, θ * + ζ, where ζ is a zero-mean random noise, and θ * is an underlying parameter. The goal is to find a private estimator θ priv that approximates θ * as closely as possible, with the ℓ 2 -norm estimation error θ privθ * 2 being minimized. 2 To make our results comparable to the previous results and for simplicity, in this paper we assume κ∞ and κx all are constants. Note that previous studies on private regression also hide factors related to Σ in their main context(e.g. [56, 51, 11] hide the term of poly (1/λmin(Σ)).