Truthful High Dimensional Sparse Linear Regression

Authors: liyang  zhu
amina  manseur
meng  ding
jinyan  liu
jinhui  xu
di  wang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 18:53:07

Abstract: We study the problem of fitting the high dimensional sparse linear regression model, where the data are provided by strategic or self-interested agents (individuals) who prioritize their privacy of data disclosure. In contrast to the classical setting, our focus is on designing mechanisms that can effectively incentivize most agents to truthfully report their data while preserving the privacy of individual reports. Simultaneously, we seek an estimator which should be close to the underlying parameter. 
We attempt to solve the problem by deriving a novel private estimator that has a closed-form expression. 
Based on the estimator, we propose a mechanism which has the following properties via some appropriate design of the computation and payment scheme:  (1) the mechanism is $(o(1), O(n^{-\Omega({1})}))$-jointly differentially private, where $n$ is the number of agents; (2) it is an $o(\frac{1}{n})$-approximate Bayes Nash equilibrium for a $(1-o(1))$-fraction of agents to truthfully report their data; (3) the output could achieve an error of $o(1)$ to the underlying parameter; (4) it is individually rational for a $(1-o(1))$ fraction of agents in the mechanism; (5) the payment budget required from the analyst to run the mechanism is $o(1)$. To the best of our knowledge, this is the first study on designing truthful (and privacy-preserving) mechanisms for high dimensional sparse linear regression.

Main paper: 
 introduction: 
 One fundamental learning task is estimating the linear regression model, with a wide array of applications ranging from statistics to experimental sciences like medicine [7, 23] and sociology [36] . These studies typically assume that analysts have high-quality data, which is essential to the success of the model. However, real-world data, such as medical records and census surveys, often contain sensitive information sourced from strategic, privacy-concerned individuals. In this case, data providers (agents) 1 may be disinclined to reveal their data truthfully, potentially jeopardizing the accuracy of model estimation. Therefore, in contrast to conventional statistical settings, it becomes imperative to model the utility functions of individuals and engineer mechanisms that can concurrently yield precise estimators, safeguard the privacy of individual reports, and encourage the majority of individuals to candidly disclose their data to the analyst.The problem involves two intertwined components: data acquisition and privacy-preserving data analysis. The analyst must strategically compensate agents for potential privacy violations, considering the alignment of their reported data with both the statistical model and their peers' contributions, while minimizing the payment budget. Additionally, the analyst must perform privacy-preserving computations to accurately learn the underlying model. As agents cannot refine their reports after seeing their payment, the interaction is designed to be completed in one round, creating a trade-off between estimator accuracy and the total payment budget needed for participant cooperation.In recent years, there has been a line of work studying truthful and privacy-preserving linear models such as [2, 37, 14, 38] . However, due to the complex nature of the problem, all of them only consider the low dimension case, where the dimension of the feature vector (covariate) is much lower than the sample size, i.e., they need to assume the dimension is a constant. In practice, we always encounter the high dimensional sparse case where the dimension of the feature vector is far greater than the sample size but the underlying parameter has an additional sparse structure. While the (high dimensional sparse) linear model has been widely studied in statistics and privacy-preserving machine learning [39, 24, 3, 52, 61, 53, 49, 28] , to the best of our knowledge, there is no previous study on truthfully and privately estimating high dimensional sparse linear models due to some intrinsic challenges of the problem (see Section C in Appendix for details). Therefore, a natural question to ask is:Can we fit the high dimensional sparse linear regression and design mechanism which incentivizes most agents and truthfully report their data and preserves the privacy of the individuals?In this paper, we answer the question in the affirmative via providing the first study on the trade-off between privacy, the accuracy of the estimator, and the total payment budget for high dimensional sparse linear models where the dimension d can be far greater than the sample size n, while the sparsity k and log d are far less than n can be considered as constants. Specifically, for the privacypreserving data analysis part, we adopt the definition of Joint Differential Privacy (JDP) [31] to protect individuals' data and develop a novel closed-form and JDP estimator for sparse linear regression, which is significantly different from the low dimension case and can be applied to other problems. Moreover, we develop a general DP estimator for the ℓ p -sparse covariance matrix with p ∈ [0, 1] as a by-product, which extends the previous results on the ℓ 0 -sparse case. Based on our JDP estimator, via the peer prediction method, we then provide a payment mechanism that can incentivize almost all participants to truthfully report their data with a small amount of the total payment budget.In detail, our mechanism has the following properties. (1) The mechanism preserves privacy for individuals' reported data, i.e., the output of the mechanism is (o (1) , O(n -Ω(1) ))-JDP, where n is the number of agents. (2) The private estimator of the mechanism is o(1)-accurate, i.e., when the number of agents increases, our private estimator will be sufficiently close to the underlying parameter. (3) The mechanism is asymptotically truthful, i.e., it is an o( 1 n )-approximate Bayes Nash equilibrium for a (1 -o(1))-fraction of agents to truthfully report their data. (4) The mechanism is asymptotically individually rational, i.e., the utilities of a (1 -o(1))-fraction of agents are non-negative. (5) The mechanism only requires o(1) payment budget, i.e., when the number of participants increases, the total payment tends to zero. 
preliminaries: 
 Notations. Given a matrix X ∈ R n×d , let x T i be its i-th row and x ij (or [X] ij ) be its (i, j)-th entry (which is also the j-th element of the vector x i ). For any p ∈ [1, ∞], ∥X∥ p is the p-norm, i.e., ∥X∥ p := sup y̸ =0 ∥Xy∥p ∥y∥p , and ∥X∥ ∞,∞ = max i,j |x ij | is the max norm of matrix X. For an event A, we let I[A] denote the indicator, i.e., I[A] = 1 if A occurs, and I[A] = 0 otherwise. The sign function of a real number x is a piece-wise function which is defined as sgn(x) = -1 if x < 0; sgn(x) = 1 if x > 0; and sgn(x) = 0 if x = 0. We also use λ min (X) to denote the minimal eigenvalue of X. For a sub-Gaussian random variable X, its sub-Gaussian norm ∥X∥ ψ2 is defined as∥X∥ ψ2 = inf{c > 0 : E[exp( X 2 c2 )] ≤ 2} (see Appendix E for more preliminaries).We consider the problem of sparse linear regression in the high dimensional setting where d ≫ n.Suppose that we have a data universe D = X ×Y ⊆ R d ×R and n agents in the population, where each agent i has a feature vector x i ∈ X and a response variable y i ∈ Y (we denote D i = (x i , y i ) and D as the whole dataset). We assume that {(x i , y i )} n i=1 are i.i.d. sampled from a sparse linear regression model, i.e., each (x i , y i ) is a realization of the sparse linear regression model y = ⟨θ * , x⟩ + ζ, where the distribution of x has mean zero, ζ is some randomized noise that satisfies E[ζ|x] = 0, and θ * ∈ R d is the underlying model estimator with sparsity assumption ∥θ * ∥ 0 ≤ k. In the following, we provide some assumptions related to the model. See Section A in Appendix for a table of notations. Assumption 1. We assume ∥θ * ∥ 2 ≤ 1. Moreover, for the covariance matrix of x, Σ, there exist κ ∞ and κ x such that ∥Σw∥ ∞ ≥ κ ∞ ∥w∥ ∞ , ∀w ̸ = 0 and ∥Σ -12 x∥ ψ2 ≤ κ x . 2 These assumptions have been commonly adopted in some relevant studies such as [52, 14, 3] . Next, we present the assumptions made on the covariate vectors x i and response variable y i . Assumption 2. We assume that the covariates (feature vectors) x 1 , x 2 , • • • , x n ∈ R d are i.i.d. (zeromean) sub-Gaussian random vectors with variance σ 2 d with σ = O(1). 3 The responses y i are i.i.d. (zero-mean) sub-Gaussian random variables with variance σ 2 with σ = O(1).In our setting, the agents are self-interested or strategic. They concerned about their privacy and can misreport their responses {y i } n i=1 but not their features {x i } n i=1 . This means the features are directly observable but the response (e.g., during physical examination) is unverifiable. We denote D = { Di = (X i , ŷi )} n i=1 the reported dataset where ŷi = σ i (D i ) is the reporting strategy adopted by agent i. Specifically, each agent is characterized by a privacy cost coefficient c i ∈ R + . Higher c i indicates the agent i is concerned more about the privacy violation.Apart from the agents, there is an analyst who seeks an accurate estimator θ of θ * based on the reported data and needs to construct a payment rule π : D n → Π n that encourages the truthful participation, i.e., reveal their data truthfully to the agent. Misreporting the response y i will result in a decrease in the payment received π i . The analyst will thus design a mechanism M takes the reported dataset D = { Di = (X i , ŷi )} n i=1 as input and outputs an estimator θ of θ * and a set of non-negative payments {π i } n i=1 for each agent. This mechanism will in turn satisfy some privacy guarantee for the reports provided by agents. Moreover, the desired mechanism must constrain the payments to an asymptotically small budget. All of the above discussion depends upon the rationality of each agent.Due to space limit, we postpone all the relevant definitions of DP to the appendix, readers can refer to Section. A.1. In our case, DP requires that all outputs, including the payments allocated to agents, are insensitive to each agent's input. This requirement is quite strict, as the payment to each agent is not shared publicly or with other agents. Therefore, instead of using the original DP, we consider a relaxation known as joint differential privacy (JDP) [31] .Based on the definition of JDP, we introduce in this section our model of agent utilities. We assume that each agent i is characterized by her privacy cost parameter c i ∈ R + representing how she is concerned about the privacy violation in the case she truthfully reports y i to the analyst. We also introduce her privacy cost function f i (c i , ε, δ) which measures the cost she incurs when her response y i is used in an (ε, δ)-Joint Differential Private Mechanism. Considering the payment π i of agent i and her privacy cost function f i (c i , ε, δ), we denote by u i = π i -f i (c i , ε, δ), her utility function that represents the utility she gets when she reports her response y i truthfully to the analyst. Following the previous works, we assume that all functions f i are bounded by a function of c i and ε, increasing with ε. Assumption 3. The privacy cost function of each agent i satisfiesf i (c i , ε, δ) ≤ c i (1 + δ)ε 3Larger values of ε and δ imply weaker privacy guarantees, which means the privacy cost of an agent becomes larger. Thus, it is natural to let f i be bounded by a component-wise increasing function, which can be denoted by F (c i , ε, δ). Here F (c i , ε, δ) = c i (1 + δ)ε 3 . In [14] , the authors consider the case where the response is bounded and δ = 0, they assumef i (c i , ε, δ) ≤ c i ε 2 , i.e., F (c i , ε, δ) = c i ε 2 .However, since our Assumption 2 on the distribution of the response is more relaxed, we need stronger assumptions regarding the privacy cost function and the distribution of privacy cost coefficients.We assume that the privacy cost parameters are also random variables, sampled from a distribution C. It is intuitive to believe that the privacy cost c i for each individual does not reflect the privacy costs incurred by other individuals. Also, we allow c i to be correlated with its corresponding data sample D i . Therefore, we make the following assumption. Assumption 4.Given D i , (D -i , c -i ) is conditionally independent of c i , for each i ∈ [n] : p(D -i , c -i |D i , c i ) = p(D -i , c -i |D i , c ′ i )where c -i represents the set of privacy costs excluding the privacy cost of agent i.In addition, we make the same assumption on the tail of C as in [37] that the probability distribution of c i has exponential decay. This assumption is essential for providing a bound on the threshold value τ α,β of truthful reporting, which will be explained in the following section. Assumption 5. There exists some constant λ > 0 such that the conditional distribution of the privacy cost coefficient satisfiesinf Di P ci∼p(ci|Di) (c i ≤ τ ) ≥ 1 -e -λτ .Following the previous work, we propose to design mechanisms that satisfy the following properties :(1) truthful reporting is an equilibrium; (2) the private estimator output should be accurate; (3) the utilities of almost all agents are ensured to be non-negative; and (4) the total payment budget required from the analyst to run the mechanism is small. These concepts will be measured and evaluated using the framework of a multiagent, one-shot, simultaneous-move symmetric Bayesian game, where the behavior of the agents is modeled. Due to space limit, we provide rigorous definitions of the truthful mechanism properties to the Appendix. Readers can refer to Section A.2 for details.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: We do not solve the inherent one-round communication constraint as mentioned in Section 1 and Section D.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
main results: 
 In this section, we will design truthful and private mechanisms for our problem. Generally speaking, our method consists of two components: a closed-form JDP estimator for high dimensional sparse linear regression and a payment mechanism. In the following, we first introduce our private estimator for the original dataset D.As mentioned in Section 1, the one-round communication constraint necessitates a closed-form estimator. For this reason, in the low dimension setting, previous methods did not favour LASSO as there is no closed-form solution and thus also cannot be used. [14, 37] are motivated by the closed-form solution of the ordinary least square (OLS) or ridge regression (See Section C for detailed discussion). However, it is well-known that for high dimensional sparse setting these two estimators come with less favorable guarantees when compared to the LASSO. When employed as a regularization term, the ℓ 2 -norm does not encourage sparsity to the same extent as the ℓ 1 -norm. Thus, all previous methods for truthful linear regression cannot be applied to our problem.In the following, we derive a new estimator based on a variant of the classical OLS estimator, tailored for the high dimensional sparse setting. Our aim is twofold: first, to achieve convergence rates similar to the LASSO, and second, to exploit the inherent sparsity of the model.We initiate our analysis with an initial, albeit unrealistic "scaffolding" assumption that the inverse of the empirical covariance matrix ( ΣXX ) -1 exists with ΣXX = 1 n n i=1 x i x T i , which will be removed in the course of our analysis. Intuitively, our goal is to find a sparse estimator that is close to OLS, i.e., arg min θ ∥θ -Σ-1EQUATIONwith some λ n > 0.Although (1) is very similar to LASSO, fortunately, the above minimizer is just the proximal operator on OLS: Prox λn∥•∥1 ( Σ-1 XX ΣXY ), which has a closed form expression. Since the proximal operator is separable with respect to both vectors, θ and Σ-1XX ΣXY , we have(Prox λn∥•∥1 ( Σ-1 XX ΣXY )) i = sgn(( Σ-1 XX ΣXY )) i ) max{|( Σ-1 XX ΣXY )) i | -λ n , 0}.And the optimal solution θ satisfies:EQUATIONwhere for a given thresholding parameter λ, the element-wise soft-thresholding operator S λ : R d → R d for any u ∈ R d is defined as the following: the i-th element of S λ (u) is defined as[S λ (u)] i = sgn(u i ) max(|u i | -λ, 0).A key insight is that this operation is equivalent to embedding the classical OLS estimator within the sparsity constraint. This secures ℓ 2 -norm consistency which does not hold for neither the ridge regression nor the original OLS estimator. The ℓ 1 regularization serves to minimize the structural complexity of the parameter under constraints. Importantly, the estimator above is available in closed-form.Our next focus centers on the privatization scheme. Prior work on truthful linear regression [14, 37] employed the output perturbation method, which adds some noise to the closed-form estimator. The noise should be calibrated by the ℓ 2 -sensitivities of their non-private estimators to ensure DP, which depend on Poly( d/n). This is unacceptable when d ≫ n. Should we adopt the same strategy to analyze the sensitivity of S λn ( Σ-1 XX ΣXY ), we inevitably encounter the estimation error of Σ-1 XX . This error will cause the noise to have an unavoidable dependency on Poly( d/n) [46] . Given the previous discussion, we propose to inject Gaussian noise separately to ΣXX and ΣXY . It is notable that while similar methods have been used in DP statistical estimation [40, 48] , it has not been used in truthful linear regression. This is due to that in our problem, the data is misreported, which makes the utility analysis more difficult. We will discuss it in Section 4.1.For the term ΣXX , we apply ℓ 2 -norm clipping so that the sensitivity of clipped version Σ X X is irrelevant to d. For the term ΣXY , since the covariate and the response y i are sub-Gaussian. Therefore, clipping operation becomes necessary. We shrink each coordinate of x i via parameters τ x , i.e., for j ∈ [d] and xi = sgn (x i ) min {|x i | , τ x }. We also perform the element-wise clipping on the response y i by τ y . Then the server aggregates these terms xi xT i and xi ỹi and separately add Gaussian noises to Σ X X and Σ X Y . The noisy version is denoted by Σ X X and Σ X Y . We now give a second thought to the estimation of the covariance matrix. As mentioned earlier, we used the scaffolding assumption on the invertibility of ΣXX matrix, which does not hold as the matrix is rank-deficient if d ≫ n. To mitigate this issue, we need to impose additional assumptions and here switch to the sparsity assumption introduced below on the structure of the covariance matrix, which has been widely studied previously such as [4, 5] . Assumption 6. We assume that Σ ∈ G q (s) for some 0 ≤ q < 1, whereG q (s) = {Σ = (σ xx T ,ij ) 1≤i,j≤d : max i d j=1 |σ xx T ,ij | q ≤ s, ∀j ∈ [d]}is the parameter space of s-approximately sparse covariance matrices.It is notable that the sparse covariance assumption is commonly adopted in the previous work on high dimensional estimation [60, 9] . To the best of our knowledge, the only work that considers the private sparse covariance matrix estimation is [51] . Unfortunately, [51] only considers the case where q = 0, which is a special case of Assumption 6 and we cannot trivially apply their method to our setting. Also, as we will discuss in Remark 3, even if the assumption does not hold, all of our theoretical results still hold if the sample size is large enough. Directly using the perturbed covariance matrix will be insufficient to exploit the sparsity structure. In fact, it can be readily seen that ∥ Σ X X -Σ∥ 2 ≤ O(√ d nϵ ), which is quite large under the high dimensional setting. To see why Σ X X will introduce a large error under Assumption 6, we observe that some of its entries are quite large which makes | σxx T ,ij -σ xx T ,ij | large for some i, j. Thus, we need to develop a new private estimator for (approximately) sparse covariance matrices as a valuable by-product. By Lemma 24 and 11 in the Appendix, we can get the following, with high probability, for all1 ≤ i, j ≤ d, σxx T ,ij -σ xx T ,ij ≤ Õ( √ ln 1 δ nε). However, under the sparsity assumption, there will be two cases: (1) If σ xx T ,ij is small enough, then maybe the zero entry could have a smaller error than σxx T ,ij since the noise is quite large. (2) If σ xx T ,ij is large, then the original σxx T ,ij could be better. Motivated by the above observation, we perform a hard-thresholding operation on each σxx T ,ij . This method takes advantage of this sparsity assumption by first estimating the sample covariance matrix, and then setting all entries with absolute values below a certain threshold Thres to 0. To be more specific, it filters out σxx T ,ij smaller than Thres and sets them to 0 while keeping those larger than Thres unchanged. This effectively shrinks the magnitude of the perturbed covariance matrix and thus lowering the error since some small σ xx T ,ij correspond to large σxx T ,ij . After the hard-thresholding operation, we denote the resulting matrix by Σ X X and it is invertible with high probability as shown below.Algorithm 1 (ε, δ)-DP Algorithm for Sparse Linear Regression X Y = 1 n n i=1 xi ỹi . 7: Add noise Σ X X = Σ X X + N 1 ,where N 1 ∈ R d×d is a symmetric matrix and each entry of the upper triangular matrix is sampled from N (0,32r 4 log 2.5 δ n 2 ε 2 ). Add noise Σ X Y = Σ X Y + N 2 , where the vector N 2 ∈ R d is sampled from N (0, 32τ 2 x τ 2 y log 2.5 δ n 2 ε 2 I d ). 8:Apply hard-thresholding to Σ X X and obtain Σ X X where each entry is defined asσxx T ,ij = σxx T ,ij • I[| σxx T ,ij | > Thres], where Thres = γ log d n + 4r 2 √ 2 ln 1.25/δ √ log d nεand γ is some constant. 9: The server outputs θP(D) = S λn ([ Σ X X ] -1 Σ X Y ).Lemma 1. The estimation error of private estimator Σ X X satisfies with probability 1 -d -Ω(1) that E∥ Σ X X -Σ∥ 2 ∞ ≤ O s 2 log d log 1 δ r 4 nε 2 1-q + log d log 1 δ r 4 nε 2where the expectation takes over the randomness of the data records and the algorithm. Remark 1. When q = 0 and r = O(1), Lemma 1 could achieve an error bound of O( s 2 log d nϵ 2 ), which matches the optimal rate of locally differentially private sparse covariance matrix estimation [51, 50] .Our private estimator is of the form θP (D) = S λn ( Σ-1 X X Σ X Y ). With some r, τ x , and τ y , θP (D), upper bound of Õ( √ k √ nε ) is achievable. See Algorithm 1 for details. Notably, step 8 is the hard thresholding step for the private covariance matrix estimator. Importantly, the threshold only depends on n, log d, and the privacy parameters and is independent on the two sparsities s and k of our problem. Moreover, since we assume ∥θ * ∥ 2 ≤ τ θ , we can also project θP (D) in Algorithm 1 onto a ℓ 2 -norm ball: θP (D) = Π τ θ ( θP (D)), where Π τ θ (v) = arg min v ′ ∈B(τ θ ) ∥v ′ -v∥ 2 2 and B(τ θ ) is the closed ℓ 2 -norm ball with radius τ θ .To sum up, high dimensionality gives rise to several consequences: (1) the regularization techniques used by [37, 14] are not applicable, (2) the invertibility of covariance matrix estimate is not guaranteed, (3) it also precludes the output perturbation method. Our proposed estimator properly overcomes the above challenges. To tackle (1) we embed the OLS estimator within the ℓ 1 constraint to exploit the sparsity, along with a novel estimator of the covariance matrix to mitigate (2), and privatize it by sufficient perturbation to solve (3) , which in turn makes our truthful analysis part much more complicated.We now turn our attention to the payment rule. The analyst wants to pay agents according to the veracity of the data they have provided and needs a reference against which to compare each data item. As mentioned before, the response is unverifiable, hence we lack a ground truth reference to validate the accuracy of the reported values. To circumvent the problem, we adopt the peer prediction method to determine a player's payment. In principle, the higher payment means higher consistency between the agent's reported value ŷi and the predicted value of y i estimated using the collective input from their peers D-i .To quantitatively measure the similarity between each agent's report and their peer's reports, we will use the rescaled Brier score rule [21] . Let a 1 and a 2 be positive parameters to be specified. Consider that q represents the prediction of agent i's response based on her own reports, and p represents the prediction of agent i's response based on her feature vector and her peers' reports. The analyst uses Algorithm 2 General Framework for Truthful and Private High Dimensional Linear Regression 1: Ask all agents to report their data D1 , • • • , Dn ; 2: Randomly partition agents into two groups, with respective data pairs D0 , D1 3: For each dataset D, D0 and D1 , compute private estimators θP ( D), θP ( Db ) for b = 0, 1 according to Algorithm 1 4: Compute estimators θP ( D) = Π τ θ ( θP ( D)) and θP ( Db ) = Π τ θ ( θP ( Db )) for b = 0, 1 5: Set parameters a 1 , a 2 , and compute payments to each agent i: if agent i's is in group 1 -b, then he will receive paymentπ i = B a1,a2 ⟨x i , θP ( Db )⟩, ⟨x i , E θ∼p(θ| Di) [θ]⟩) .the following payment rule:EQUATIONObserving that B a1,a2 (p, q) is a function that exhibits strict concavity with respect to q, we point out that its maximum is attained when q equals p. This implies a congruence between the prediction of agent i's response based on her own information and that derived from her peers' information. For agent i, givenE[y i |x i , θ * ] = ⟨x i , θ * ⟩, it is logical to set p = ⟨x i , θP ( Db )⟩ and q = ⟨x i , E θ∼p(θ| Di) [θ]⟩.Here, θP ( Db ) denotes the private estimator for a dataset Db excluding Di , and p(θ| Di ) represents the posterior distribution of θ post the analyst's receipt of Di .Building upon this analysis, we structure our Algorithm 2. This algorithm utilizes reported data, which may contain manipulated responses, to generate estimators. To maintain data independence, we divide the dataset into two subsets, D0 and D1 . For the purpose of calculating the payment for each agent i in group b ∈ {0, 1}, the estimator θ * is derived using D1-b . Finally, the algorithm applies θP ( D) in combination with the specific agent's feature vector x i to forecast their response.4 Theoretical Results and ImplementationQuestion: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructo faithfully reproduce the main experimental as described in supplemental material? Answer: [NA] Justification: Our paper does not include experiments. Guidelines:• The answer NA means that paper does not include experiments requiring code. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes] Justification: This paper presents work whose goal is to advance the field of machine learning theory. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to applications, let alone deployments. However, if is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
accuracy and privacy analysis: 
 Theorem 2 (Privacy). The output of Algorithm 2 satisfies (2ε, 3δ)-JDP.Remark 2. By the selection of ε and δ, our mechanism could achieve an (o(1 √ n ), O(n -Ω(1)))-JDP, which provides asymptotically the same good privacy guarantee as in [14] for the low dimension setting with bounded covariates and responses. Specifically, [14] shows that it is possible to design an o( 1 √ n )-JDP mechanism, while here we consider the approximate JDP due to the Gaussian noise we add. [37] considers truthful (low dimensional) linear regression with sub-Gaussian/heavy-tailed covariates and responses, our Theorem 2 is better than theirs. In detail, [37] can only guarantee Random Joint Differential Privacy (RJDP) where on all but a small proportion of unlikely dataset pairs, pure ε-JDP holds, while in this paper we can guarantee approximate JDP, which is more widely used in the DP literature. The main reason is that [37] used the output perturbation-based method to ensure DP. However, as the data distribution is sub-Gaussian rather than bounded as in [14] , the sensitivity of the closed-form linear regression estimator could be extremely large (with some probability). Thus, the output perturbation-based method can fail with a small probability and can only ensure RJDP. Instead, in our method, we use sufficient statistics perturbation, due to our clipping operator, the sensitivities of Σ X X and Σ X Y are always bounded. One consequence of adopting our sufficient statistics perturbation method is that the utility analysis is harder than that of the output perturbation-based method, as we will discuss in the following. Theorem 3 (Accuracy). Fix a privacy parameter ε, a participation goal 1 -α and a desired confidence parameter β in Definition 6. Then under the symmetric threshold strategy σ τ α,β , when n is sufficient large such that n ≥ Ω(s 2 r 4 log d log 1 δ ε 2 κ∞), the output θP ( D) of Algorithm 2 satisfies that with probability at least1 -β -O(n -Ω(1) ), E[∥ θP ( D) -θ * ∥ 2 2 ] ≤ O α 2 n + 1 n kr 4 log d log 1 δ ε 2 .Remark 3. The above bound is independent on Poly(d). This outcome is primarily due to the use of sufficient statistics perturbation method, which effectively reduces the size of noise. It is notable that Assumption 6 only ensures that when n ≥ Ω( s 2 r 4 ε 2 κ∞ ) our private covariance estimator is invertible. Thus, even if the assumption does not hold, we can still get the same upper bound as in Theorem 3 as long as n ≥ Ω(d).Our framework for analyzing the accuracy differs dramatically from that of the prior ones since our privatization mechanism incurs finer and more delicate analysis on some specific error terms. The work of [37] and [14] both used the output perturbation method, as it provides an explicit characterization of the noise. Specifically, their estimator can be represented as θP ( D) = Π τ θ ( θP ( D)), where θP ( D) = θ( D) + v with θ( D) as a (non-private) closed-form estimator and v is the added Gamma noise of scale O( d/n) to the non-private estimator. It can be shown that:EQUATION)where D is original data and D is the reported data. Note that the second and the third terms in ( 4) are easy to upper bound. For the first term, since we know the number of manipulated data in D is bounded by αn with high probability, indicating there are at most αn different samples between D and D. Thus, it can be bounded by directly re-using the sensitivity analysis of θ(D) as a part of the privacy data analysis. However, as we mentioned previously, the sensitivity of ( 2) is of scale O( d/n), indicating the previous method cannot be applied in our setting. Hence our tactic is to privatize the terms Σ X X and Σ X Y separately. We shall take another route to estimate the error of the private estimator θP ( D):E[∥ θP ( D) -θ * ∥ 2 2 ] ≤ E∥ θP ( D) -θ * ∥ 2 2 ≤ 2E∥ θP ( D) -θP (D)∥ 2 2 + 2E∥ θP (D) -θ * ∥ 2 2 .The above framework is now estimating the difference in the private θP (instead of the non-private θ). However, this nuance inevitably leads to more complex analysis, i.e. the term E∥ θP ( D) -θP (D)∥ 2 2 is much more complicated to deal with than the first term in (4) . The bound on E∥ θP ( D) -θP (D)∥ 2 2 cannot be obtained by simply applying existing results on the covariance matrix estimation as in [37] or the assumption of strong convexity of the loss function as in [14] . Specifically, we tackle this issue by combining the analysis for s-approximately sparse covariance matrices and some technical tools such as the decomposability of the ℓ 1 norm term in (1) to give a non-trivial bound. The relevant lemma is given below and as mentioned this bound comprises a key component for the proof of Theorem 3. Lemma 4. Let θP ( D) and θP (D) be the private estimators on the original dataset D and the reported dataset D that at most one agent misreports. We set the constraint boundλ n = O r 2 √ log d log 1 δ √ nε ,when n is sufficient large such that n ≥ Ω(s 2 r 4 log d log 1 δ ε 2 κ∞), with probability at least 1 -O(d -Ω(1) ) we have the following error bounds:∥ θP ( D) -θP (D)∥ ∞ ≤ 4λ n , θP ( D) -θP (D) 2 ≤ 16 √ kλ n .Theorem 5 (Truthfulness). Fix a privacy parameter ε, a participation goal 1 -α and a desired confidence parameter β in Definition 6. Then with probability at least1 -β -O(n -Ω(1) ) -nd -9 2 , the symmetric threshold strategy σ τ α,β is an η-approximate Bayesian Nash equilibrium in Algorithm 2 with η = O a 2 r 4 log d log 1 δ nα 2 k ε 2 + 1 nε 2 + τ α,β δε 3 .We can see with some specified parameters, the above bound could be sufficiently small. For example, when we setα = O( 1 n ) we have η → 0 as n → ∞ since δ = o( 1 n ). Theorem 6 (Individual rationality). With probability at least 1 -β -O(n -Ω(1) ) -nd -92 , Algorithm 2 is individually rational for all agents with cost coefficients c i ≤ τ α,β as long asEQUATION(1 + 3δ)ε 3 regardless of the reports from agents with cost coefficients above τ α,β , where a 1 , a 2 are in (6) .Remark 4. Our mechanism may not be individually rational for all agents, since the privacy cost coefficients follow an unbounded distribution with exponential decay. This assumption is made reasonable because for a relatively small subset of agents the privacy costs could be exceptionally high, indicating certain individuals may persistently refrain from reporting truthfully, regardless of the compensation offered to them. The same situation happens in other truthful mechanisms as well.Theorem 7 (Budget). With probability at least 1 -β -O(n -Ω(1) ) -nd -9 2 , the total expected budget B = n i=1 E (π i ) required by the analyst to run Mechanism 1 under threshold equilibrium strategy σ τ α,β satisfies B ≤ n(a 1 + a 2 (rτ θ + r 2 τ 2 θ )). Remark 5. With some appropriate setting of α, it is reasonable to expect the overall expected budget to diminish toward zero as the sample size increases. This is because if the sample size is infinite, the ground-truth parameters can always recovered by our estimator, which allows the analyst to pay nothing to incentivize the agents.Result Corollary 8. For any ξ ∈ ( 1 3 , 1 2 ) and c > 0, we set ε = n -ξ , δ = Θ(n -Ω(1) ), α = Θ(n -3ξ ), β = Θ(n -c ), a 2 = O(n -3ξ ), a 1 = a 2 (rτ θ + 3r 2 τ 2 θ ) + τ α,β 8(1 + 3δ)ε 3 . Then the output of Algorithm 2 satisfies (O(n -ξ ), O(n -Ω(1)))-JDP. Moreover, with probability at least 1 -O(n -Ω(1) ), it holds that:1. The symmetric threshold strategy σ τ α,β is a O(n -ξ-1 )-Bayesian Nash equilibrium for a 1 -O(n -3ξ ) fraction of agents to truthfully report their data;2. The private estimator θP ( D) is O(n 2ξ-1 )-accurate;3. It is individually rational for a 1 -O(n -3ξ) fraction of agents to take part in the mechanism;4. The total expected budget required by the analyst is O(n 1-3ξ ). Remark 6. It is important to highlight the subtle balance between the precision of the estimator and the other attributes of the mechanism. Compromising on accuracy often results in several consequences: (1) a reduction in the total compensation paid to the agents, (2) an increase in the proportion of rational agents, and (3) a closer approximation to the Bayesian Nash Equilibrium. However, we do not observe such a trade-off in [37] 's implementation for linear regression cases. Besides, our results slightly differ from that of [14] in the sense that they do not have a trade-off between rationality and accuracy. Such discrepancies may be caused by varying willingness to supply higher compensation to the agents, resulting in different settings of parameters. 
conclusions: 
 In this paper, we fit the high dimensional sparse linear regression privately and we propose a truthful mechanism to incentivize the strategic users. On the one hand, the mechanism is (o(1), O(n -Ω(1) ))jointly differentially private. This is achieved by using the sufficient statistics perturbation method which adds much less noise than the output perturbation method employed by prior work. Leveraging the idea of soft-thresholding, we propose a private estimator of θ * to exploit the sparsity of the model and it achieves an error of o(1). On the other hand, via some computation on the consistency between the agent's reported value and the predicted value using peers' reports, we design an appropriate payment scheme for each agent using rescaled Brier score rule. This method ensures that our mechanism reaches an o( 1 n )-approximate Bayes Nash equilibrium for a (1 -o(1))-fraction of agents to truthfully report their data while a (1 -o(1)) fraction of agents receive non-negative utilities, thus establishing their individual rationality. Moreover, the total payment budget required from the analyst to run the mechanism is o(1). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: Our paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: The number of agents dThe dimensionalityx i ∈ X ⊆ R dThe feature vector of agent i yi ∈ Y ⊆ R The response variable of agent i Σ XX or Σ The covariance matrix of x i ∥X∥ p p-norm of matrix X I[A]Indicator of event A sgn(x)Sign function of a real number x [S λ (u)] iElement-wise soft-thresholding operatorN 1 ∈ R d×d Gaussian noise added to Σ X X N 2 ∈ R d Gaussian noise added to Σ X Y γ Some constant associated with the variance of N 2 ỹi shrunken version of y i via parameter τ y Σ X X ( Σ X Y )The sample covariance between X and X (The sample covariance between the clipped X and the clippedY ) Σ X X ( Σ X Y ) a noisy and (clipped) version of Σ X X ( Σ X Y ) c i ∈ C ⊆ R + The privacy cost coefficient of agent i D = X × YThe feature-response data universeD i = (x i , y i )The feature-response data pair of agent iσ i (•, •) : D × C → Y The reporting strategy of agent i ŷi = σ i (D i , c i )The reported response of agent i Di = (x i , ŷi )The reported feature-response data pair of agent iD = {D i } n i=1All feature-response data pairsD = Di n i=1All reported feature-response data pairsσ = {σ i } n i=1The collection of all agents' reporting strategiesD -i = D\D iThe collection of data pairs exceptD i D-i = D\ DiThe collection of reported data pairs except Diσ -i = σ\σ iThe collection of strategies exceptσ i c -i = {c j } n j=1 \c iThe collection of privacy cost coefficients except c i π iThe payment to agent i u iThe utility of agent i ε, δ ∈ R +The privacy parameters of the mechanismθ * ∈ R dThe model parameter needs to estimate σ τThe threshold strategy with privacy cost threshold τ ∈ R + τ α,βThe privacy cost threshold characterized by α, β ∈ (0, 1) BThe expected total budget θ(D)The non-private estimator on data D θP ( D)The private estimator on the reported data D θP ( D)The private estimator on the reported data D after projection κ 2 , κ ∞The lower bounds for the operator norm and infinity norm of matrix Σ respectively ηThe level of truthfulness ξ ∈ ( 1 3 , 12 )The parameter to control the trade-off between accuracy and truthfulness, payment amount and individual rationality.Definition 1 (Differential Privacy [17] ). Given a data universe X , we say that two datasets D, D ′ ⊆ X are neighbors if they differ by only one entry, which is denoted as D ∼ D ′ . A randomized algorithm A is (ε, δ)-differentially private (DP) if for all neighboring datasets D, D ′ and for all events S in the output space of A, we have P(A(D) ∈ S) ≤ e ε P(A(D ′ ) ∈ S) + δ.Definition 2. (Gaussian Mechanism). Given any function q : X n → R p , the Gaussian Mechanism is defined as: M G (D, q, ε) = q(D) + Y, where Y is drawn from Gaussian Distribution N 0, σ 2 I p with σ ≥ 2 ln(1.25/δ)∆ 2 (q)/ε. Here ∆ 2 (q) is the ℓ 2 -sensitivity of the function q, i.e. ∆ 2 (q) = sup D∼D ′ ∥q(D) -q (D ′ ) ∥ 2 . Gaussian Mechanism preserves (ε, δ)-differential privacy. Definition 3 (Joint Differential Privacy [31] ). Consider a randomized mechanism M : D n → Θ×Π n with arbitrary response sets Θ, Π n . For each i ∈ [n], we denote byM(•) -i = (θ, π -i ) ∈ Θ × Π n-1the portion of the mechanism's output that is observable by external observers and agents j ̸ = i. a mechanism M preserves (ε, δ)joint differential privacy (JDP), at privacy level ε > 0 and confidence level δ ∈ (0, 1), if for every agent i, every dataset D ∈ D n and everyD i , D ′ i ∈ D we have ∀S ⊆ Θ × Π n-1 , P (M(D i , D -i ) -i ∈ S|(D i , D -i )) ≤ e ε P (M(D ′ i , D -i ) -i ∈ S|(D ′ i , D -i )) + δ, where D -i ∈ D n-1is the dataset D that excludes the i-th sample in D and π -i is the vector that contains all payments except the payment of agent i.An (ε, δ)-JDP mechanism on any dataset (including likely ones) may leak sensitive information on low probability responses, forgiven by the additive δ relaxation, which we hope to have a magnitude of o( 1n ). Definition 3 assumes that the private estimator θ produced by the mechanism M is publicly observable, and that the payments π i can only be seen by agent i. Thus, from the perspective of each agent i, the released public output (θ, π -i ) may compromise their privacy.Consider M the regression mechanism that takes as input the reported data D = { Di = (X i , ŷi )} n i=1 from n agents, with ŷi = σ i (D i ) the reporting strategy adopted by agent i. We denote the set of all agents' strategies by the strategy profile σ = (σ 1 , ..., σ n ) and σ -i = (σ 1 , ..., σ i-1 , σ i+1 , ..., σ n ) denotes the set of strategies excluding the reporting strategy of agent i. Let f i (c i , ε, δ) be the privacy cost function of agent i with c i her cost parameter. Each agent i receives a real-valued payment π i and finally receives utility u i = π i -f i (c i , ε, δ). Based on these settings, we quantify property (1) by introducing Bayesian Nash equilibrium. Definition 4 (η-Bayesian Nash Equilibrium). A strategy profile σ = (σ 1 , ..., σ n ) forms an η-Bayesian Nash Equilibrium if for every agent i, D i and c i , and for every reporting strategy σ ′ i ̸ = σ i , one have :E D-i,c -i ∼p(D-i,c-i|Di,ci) [u i (σ i (D i , c i ), σ -i (D -i , c -i ))] ≥ E D-i,c-i∼p(D-i,c-i|Di,ci) [u i (σ ′ i (D i , c i ), σ -i (D -i , c -i ))] -η.The positive value η represents the maximum of additional expected payment an agent might receive by altering their reporting strategy. To encourage agents to report their data truthfully, the payment rule should aim to keep η as minimal as possible. This paper investigates a specific threshold strategy. We will establish that if all agents consistently employ the threshold strategy with a common positive value τ , this unified strategy profile will effectively realize an η-Bayesian Nash equilibrium. Definition 5 (Threshold Strategy). The threshold strategy σ τ is defined as follows:ŷi = σ τ (x i , y i , c i ) = y i , if c i ≤ τ, arbitrary value in Y, if c i > τ.Definition 6 (Threshold τ α,β ). Fix a probability density function p(c) of privacy cost parameter, and letτ 1 α,β = inf{τ > 0 : P (c1,••• ,cn)∼p n (#{i : c i ≤ τ } ≥ (1 -α)n) ≥ 1 -β}, τ 2 α = inf{τ > 0 : inf Di P cj ∼p(c|Di) (c j ≤ τ ) ≥ 1 -α}.Define τ α,β as the larger of these two thresholds:τ α,β = max{τ 1 α,β , τ 2 α }.τ 1 α,β is a threshold that with probability at least 1 -β, at least 1 -α fraction of agents have cost coefficient c i ≤ τ α,β . τ 2 α is a threshold that conditioned on their own dataset D i , each agent i believes that with probability 1 -α any other agent j has cost coefficient c j ≤ τ α,β .We introduce the definition of η-accuracy and we use the l 2 -norm distance between the private estimator and the true parameter.A mechanism is η-accurate if its output θP satisfies E ∥ θP -θ * ∥ 2 2 ≤ η. Definition 8 (Individual Rationality). A mechanism is individually rational if the utility received by each agent i has a non-negative expectation: ∀i ∈[n], E[u i ] ≥ 0To satisfy individual rationality, the mechanism should output payments high enough to compensate for privacy costs. Meanwhile, we also expect a total payment budget B = n i=1 E[π i ] = o(1) that tends to zero as the number of agents n increases.Definition 9 (Asymptotically Small Budget). An asymptotically small budget is such thatB = n i=1 E[π i ] = o(1) for all realizable dataset D = {(x i , y i )} n i=1 .To sum up, we have n agents reporting potentially manipulated data, denoted as D = (x i , y i ), to an analyst. Subsequently, the analyst computes an estimator for the model parameters using the reported data. To preserve DP, the analyst meticulously introduces controlled noise into the estimator. Furthermore, the analyst strategically compensates the agents for their privacy costs based on their reports, with the goal of incentivizing truthful reporting. This incentivization is implemented under the assumption that the agents will adhere to a threshold strategy.Following the pioneering work of [22] , a substantial body of research has explored data acquisition problems involving agents with privacy concerns [20, 32, 57, 15, 21, 18, 19, 13] . The majority of this work operates in a model where agents cannot fabricate their private information; their only recourse is either to withhold it or, at most, misrepresent their costs related to privacy. A related thread [22, 34, 10] explores cost models based on the notion of differential privacy [17] . However, most of the aforementioned work only considers the mean estimation problem and does not consider advanced statistical models [18, 19, 13] . Thus, these methods cannot be applied to linear models. [14] and [37] represent the closest work to ours, as they investigate the challenge of estimating (generalized) linear models from self-interested agents that have privacy concerns. However, as we mentioned above, they only consider the low dimensional case and their methods cannot be applied to the high dimensional sparse setting, see Section C for details.Classical approaches including the work by [55, 27, 43, 44, 45, 58, 1, 30, 41, 8, 3, 52, 54] for estimating linear regression models with differential privacy (DP) guarantee utilize central and local models. These approaches typically involve adding noise to the output of optimization methods, privatizing the objective function, or injecting noise into the gradients during optimization. However, the truthful data acquisition process follows a single-round interactive procedure between the analyst and the agents, in contrast to the multi-round interactions typically encountered in these approaches, indicating these methods cannot be applied to our problem. The closed-form expression of our estimator ensures that this requirement is satisfied. We believe that our method is non-trivial and it has the potential to extend to other related scenarios. Recently, [61] proposed a closed-form private estimator for sparse linear regression. However, as we discussed in Section 3.1, their estimator cannot be directly applied to our problem due to inherent limitations, such as challenges associated with the invertibility of the covariance matrix.Recently, there has been also some worth-noting literature on estimating linear regression from strategic agents (without privacy consideration). [25] and [6] have investigated regressing a linear model using data from strategic agents who can manipulate their associated costs but not the data. [29] explored a setting without direct payments, in which agents receive a utility that serves as a measure of estimation accuracy. [11] studied the case where agents may intentionally introduce errors to maximize their own benefits and proposed several group-strategyproof linear regression mechanisms.Additionally, [16] and [35] considered an analyst who aims to derive a "consensus" model from data provided by multiple strategic agents. In this setting, agents seek a consensus value that minimizes their individual data loss, and the authors demonstrated that empirical risk minimization is groupstrategyproof. However, all of these methods only consider the low dimensional setting and cannot be applied to the high dimensional sparse linear regression.In this section, we provide a retrospect of previous methods and then outline the explain why existing methods are not suitable for directly applying to our settings. The challenges associated with the problem make it fundamentally difficult to design a desirable mechanism.Under truthful setting, [14] proposed to use the general Ridge regression estimator, i.e., solving the regularized convex program: arg min θ1 2n ∥Y -Xθ∥ 2 2 + γ∥θ∥ 2 2where γ is some parameter andX = (x T 1 , • • • , x T n ) T ∈ R n×d , and Y = (y 1 , • • • , y n ) T ∈ R n .The unique closed-form solution can be written as θR (D) = (γI + X T X) -1 X T Y . [37] considered the classical ordinary least square (OLS) estimator θOLS = ( ΣXX ) -1 ΣXY where ΣXX = 1 n n i=1 x i x T i and ΣXY = 1 n n i=1 x i y i . Both of the private estimators are based on the closed-form solution θL (D) of the ridge regression. However, there are four problems with the above methods, θR and θOLS .The ℓ 2 -norm accuracy errors of θR and θOLS are both bounded by O( d/n). This rate is not convergent in the data-poor scenario, indicating that both of these two estimators are not suitable in our setting. Since ℓ 2 -regularization used in θR is not a sparsity-encouraging technique, we shall seek some alternative regularization. A qualified estimator that satisfies our need must (1) exploit the sparsity assumption and ( 2) have a closed-form solution.Apart from the choice of (non-private) estimator, we also need to give some thoughts on the privacy mechanism. Previous work [14] and [37] both adopt the output perturbation method to ensure ε-JDP, i.e., adding some Gamma noise to θR or θOLS . According to the DP theory, the scale of the noise should be proportional to the ℓ 2 -norm sensitivity, which can be readily bounded by d/n through clipping operation or if the data are assumed to be bounded. In the high dimensional setting, output perturbation could fail catastrophically as d ≫ n. The magnitude of noise needs to grow polynomially with d/n, causing the estimation error much larger. This means we must find a privatization mechanism that gives a better accuracy guarantee.The invertibility of the covariance matrix is also an issue in high dimensional space. The classical OLS estimator θOLS used in [37] is no longer well-defined as Σ X X is not full-rank. In the case of θR = (ϱI + X T X) -1 X T Y , although (ϱI + X T X) -1 always exists for some ϱ > 0, the caveat with such method is however its concentration only holds when n = Ω(d) [46] .To solve the invertibility issue posed by high dimensionality, we need to consider properly imposing some reasonable assumption on the structure of covariance matrix Σ, which will be formally introduced and serve to yield an efficient estimator for the covariance matrix with such assumption.Due to the additional regularization parameter ϱ, θL is a biased estimator of θ * , which complicates the truthfulness analysis. This complexity arises because the OLS linear regression estimator θOLS = X T X -1 X T y maximizes the scoring rule when players truthfully report their responses. However, for θL (D), the bias caused by ϱ causes the optimal report of each player to deviate from truthful reporting by a quantity proportional to the bias. To address the above issue, [14] shows that as long as ϱ grows more slowly than n, the bias term of θL converges to zero with high probability. More specifically, it is shown that the estimation error can be decomposed into the summation of a bias and a vari-ance term: E[ θ(D) -θ * 2 2 ] = trace(Cov( θ(D))) + ∥ bias( θ(D))∥ 2 2 , where trace(Cov( θ(D))) = σ 2 ϱI + X T X -1 X T X ϱI + X T X -1 , bias( θ(D)) = -ϱ ϱI + X T X -1 θ * , σ 2 is the vari-ance of the noise variables ζ i . However, it remains uncertain whether there is a closed-form biasvariance decomposition available for our estimator proposed in Section 3.1.Although some truthful mechanism studies [12] provided payment schemes for multiple-round data acquisition, existing truthful linear regression research poses constraint to the mechanism where data are only collected once. In this paper we mainly follow the analysis framework of [14] to guarantee truthful mechanism properties, therefore our work is still hampered by the one-round communication constraint. It remains uncertain whether this constraint could be removed in the future.Definition 10 (Sub-Gaussian random variable). A zero-mean random variable X ∈ R is said to be sub-Gaussian with variance σ 2 X ∼ subG σ 2 if its moment generating function satisfiesE[exp(tX)] ≤ exp σ 2 t 2 2for all t > 0. For a sub-Gaussian random variable X, its sub-Gaussian norm ∥X∥ ψ2 is defined as∥X∥ ψ2 = inf{c > 0 : E[exp( X 2 c 2 )] ≤ 2}. Specifically, if X ∼ subG(σ 2 ) we have ∥X∥ ψ2 ≤ O(σ).Definition 11 (Sub-Gaussian random vector). A zero mean random vector X ∈ R d is said to be sub-Gaussian with variance σ 2 (for simplicity, we call it σ 2 -sub-Gaussian), which is denoted as X ∼ subG d σ 2 , if ⟨X, u⟩ is sub-Gaussian with variance σ 2 for any unit vector u ∈ R d . Lemma 9. For a sub-Gaussian vector X ∼ sub G d σ 2 , with probability at least 1 -δ ′ we have∥X∥ 2 ≤ 4σ d log 1 δ ′ . Lemma 10 ([47]). Let X 1 , X 2 , • • • , X n ben (zero mean) random variables such that each X i is sub-Gaussian with σ 2 . Then the following holdsP max i∈n X i ≥ t ≤ ne -t 2 2σ 2 , P max i∈n |X i | ≥ t ≤ 2ne -t 2 2σ 2 .Below is a lemma related to the Gaussian random variable. We will employ it to bound the noise added by the Gaussian mechanism. Lemma 11. Let {x 1 , • • • , x n } be n random variables sampled from Gaussian distribution N 0, σ 2 . ThenE max 1≤i≤n |x i | ≤ σ 2 log 2n, P max 1≤i≤n |x i | ≥ t ≤ 2ne -t 2 2σ 2 .Particularly, if n = 1, we haveP ({|x i | ≥ t}) ≤ 2e -t 2 2σ 2 . Lemma 12 (Hoeffding's inequality). Let X 1 , • • • , X n be independent random variables bounded by the interval [a, b]. Then, for any t > 0, P 1 n n i=1 X i - 1 n n i=1 E [X i ] > t ≤ 2 exp - 2nt 2 (b -a) 2 .Lemma 13 (Bernstein's inequality for bounded random variables). Let X 1 , X 2 , • • • , X n be independent centered bounded random variables, i.e. |X i | ≤ M and E [X i ] = 0, with variance E X 2 i = σ 2 . Then, for any t > 0,P n i=1 X i > √ 2nσ 2 t + 2M t 3 ≤ 2e -t .Lemma 14 (Bound on threshold τ α,β ). Under the Assumption 5, τ α,β ≤ 1 λ log 1 αβ . Lemma 15. For any w, w ′ ∈ R d and closed convex set C ⊆ R d we have∥Π C (w) -Π C (w ′ )∥ 2 ≤ ∥w -w ′ ∥ 2 ,where Π C is the projection operation onto the set C, i.e., Π C (v) = arg min u∈C ∥u -v∥ 2 .Lemma 16 (Post-processing). Let M : X n → Y be an ε-differential private mechanism. Consider F : Y → Z as an arbitrary randomized mapping. Then the mechanism F • M is ε-differential private. Lemma 17 (Billboard lemma [26] ). Let M : D n → O be an (ε, δ)-differential private mechanism. Consider a set of n functions π i :D ×O → R, for i ∈ [n]. Then the mechanism M ′ : D n → O ×R n that computes r = M(D) and outputs M ′ (D) = (r, π 1 (D 1 , r), • • • , π n (D n , r)), where D i is the agent i's data, is (ε, δ)-joint differential private. Theorem 18 (Parallel Composition Theorem). Let O 1 , O 2 , ..., O k be n independent operations that satisfy (ε i , δ-DP for each i ∈ [k], then the parallel composition of these operations guarantee (ε 1 + ε 2 + ... + ε k , δ)-DP. Theorem 19 (Sequential Composition Theorem(Theorem 4 in [33] )). If O 1 , O 2 , ..., O k are sequential operations that satisfy ε-individual differential privacy with a failure probability of δ, then the sequential composition of these operations guarantees (ε 1 + ε 2 + ... + ε k , k • δ)-individual differential privacy, where ε i represents the ε of operation O i , and k is the total number of operations performed.Lemma 20. Let θ(D) and θ(D ′ ) be the estimators on two fixed datasets D, D ′ that differ on at most k entries and let D denote the fixed dataset that differs from D on at most one entries. Suppose that with probability at least 1 -γ n , if ∥ θ(D) -θ( D)∥ 2 ≤ λ n then we have with probability at least 1 -gγ n , it holds that∥ θ(D) -θ(D ′ )∥ 2 ≤ gλ n .Lemma 21 (Theorem 2 in [59] ). Suppose we solve the problem of the form min θ ∥θ -θ∥ 2 2 + λ n ∥θ∥ 1 , such that constraint term λ n is set as λ n ≥ θ * -θ(D) ∞ . Then, the optimal solution θ = S λn ( θ) satisfies:θ(D) -θ * ∞ ≤ 2λ n , θ(D) -θ * 2 ≤ 4 √ kλ n , θ(D) -θ * 1 ≤ 8kλ n .Lemma 22. Under Assumption 1 and 6, we setτ x = Θ( σ √ log n √ d ), τ y = Θ(σ √ log n), r = Θ(σ √ log n), λ n = O r 2 √ log d log 1 δ √ nε, when n is sufficient large such that n ≥ Ω(s 2 r 4 log d log 1 δ ε 2 κ∞),with probability at least 1 -O(d -Ω(1) ), one hasθP (D) -θ * 2 ≤ √ kλ nLemma 23. (Weyl's Inequality [42] ) Let X, Y ∈ R d×d be two symmetric matrices, andE = X -Y . Then, for all i = 1, • • • , d, we have |λ i (X) -λ i (Y )| ≤ ∥E∥ 2 ,where we take some liberties with the notation and use λ i (M ) to denote the i-th eigenvalue of the matrix M .Lemma 24EQUATIONΣ X X = σxx T ,ij 1≤i,j≤d = 1 n n i=1 xi xT iis the empirical covariance matrix, then there exist constants C 1 and γ > 0 such that for any i, j ∈ [d], we have:P Σ X X -Σ XX ∞,∞ > t ≤ C 1 e -nt 2 8 γ 2 ,for all |t| ≤ ϕ with some ϕ, where C 1 and γ are constants and depend only on σ 2 . Specifically,P Σ X X -Σ XX ∞,∞ ≥ γ log d n ≤ C 1 d -8 .Lemma 25. For every fixed 1 ≤ i, j ≤ d, there exists a constant C 1 > 0 such that with probability at least 1 -C 1 d -9 2 , the following holds: EQUATIONt ∈ [0, 1], ∥(1 -t)b + tb ′ -w∥ 2 ≥ ∥b -w∥ 2 . Thus 0 ≤ d dt ∥tb + (1 -t)b ′ -w∥ 2 2 | t=0 = 2⟨b ′ -b, b -w⟩ Similarly, we have ⟨b -b ′ , b ′ -w ′ ⟩ ≥ 0. Now consider the function D(t) = ∥(1 -t)b + tw -(1 - t)b ′ -tw ′ ∥ 2 2 = ∥b -b ′ + t(w -w ′ + b ′ -b)∥ 2 2, which is a quadratic function in t. And by the previous two inequalities we haveD ′ (0) = 2⟨b -b ′ , w -w ′ + b ′ -b⟩ ≥ 0. Thus D(•) is a increasing function on [0, 2), thus D(1) ≥ D(0) which means ∥w -w ′ ∥ 2 ≥ ∥b -b ′ ∥ 2 .Proof of Lemma 14. We first bound τ 1 α,β . Since n = #{i :c i ≤ τ } + #{i : c i > τ }, the event {#{i : c i ≤ τ } ≥ (1 -α)n} is equivalent to the event {#{i : c i > τ } ≤ αn}. Thus, by the definition of τ 1 α,β , τ 1 α,β = inf{τ > 0 : P (c1,••• ,cn)∼p n (#{i : c i > τ } ≤ αn) ≥ 1 -β} = inf{τ > 0 : P (c1,••• ,cn)∼p n (#{i : c i > τ } > αn) ≤ β},By Markov's inequality, we haveP (c1,••• ,cn)∼p n (#{i : c i > τ } > αn) ≤ E (c1,••• ,cn)∼p n [ n i=1 I {ci>τ } ] αn = n i=1 E ci∼p [1 {ci>τ } ] αn = nP[c i > τ ] αn = P[c i > τ ] α .Thus, {τ > 0 :P(c i > τ ) ≤ αβ} ⊆ {τ > 0 : P (c1,••• ,cn)∼p n (#{i : c i > τ } > αn) ≤ β}, which implies τ 1 α,β ≤ inf{τ > 0 : P(c i > τ ) ≤ αβ}. The Assumption 5 implies that P(c i > τ ) ≤ e -λτ . Hence, τ 1 α,β ≤ 1 λ log 1 αβ .By the definition of τ 2 α and Assumption 5, we haveτ 2 α ≤ 1 λ ln 1 α . Since β ∈ (0, 1), 1 λ log 1 αβ > 1 λ log 1 α , then τ α,β = max{τ 1 α,β , τ 2 α } ≤ 1 λ log 1 αβ .Proof of Lemma 4. For the ease of presentation, we denote the initial parameter ( Σ-1 X X ) Σ X Y on which the soft-thresholding S λn is performed by θ. Let ∆ be the error vector ∆ = θP (D) -θP ( D).EQUATION)where we utilize the fact that θP ( D) is feasible.Using the property of generalized thresholding operator, we can bound the first term of equation 6 as ∥ θP ( D) -θ( D)∥ ∞ ≤ λ n . For the third term of equation 6, from Lemma 22, we know that∥ θ(D) -θP (D)∥ ∞ ≤ λ n .Our next task it to show λ n is indeed greater than the second term of equation 6 ∥ θ( D) -θ(D)∥ ∞ . It can be expressed as∥ θ( D) -θ(D)∥ ∞ = ∥ Σ X X ( D) -1 Σ X Y ( D) -Σ X X (D) -1 Σ X Y (D)∥ ∞ .Applying the inequality ∥AB -A ′ B ′ ∥ ∞ = ∥AB -AB ′ + AB ′ -A ′ B ′ ∥ ∞ ≤ ∥A∥ ∞ ∥B -B ′ ∥ ∞ + ∥A -A ′ ∥ ∞ ∥B ′ ∥ ∞ , we have, ∥ Σ X X ( D) -1 Σ X Y ( D) -Σ X X (D) -1 Σ X Y (D)∥ ∞ ≤∥ Σ X X ( D) -1 ∥ ∞ ∥ Σ X Y ( D) -Σ X Y (D)∥ ∞ +∥ Σ X X ( D) -1 -Σ X X (D) -1 ∥ ∞ ∥ Σ X Y (D)∥ ∞ (7)For the first term of equation 7, we see from Lemma 1 that when n ≥ Ωs 2 r 4 log d log 1 δ ε 2 κ∞ , Σ X X -1 ∞ ≤ 2 κ∞ .And by equation 15, we have with probability1 -2d -8 that ∥ Σ X Y ( D) -Σ X Y (D)∥ ∞ =∥ Σ X Y ( D) -N 2 ( D) + N 2 (D) -Σ X Y (D)∥ ∞ ≤∥ Σ X Y ( D) -Σ X Y (D)∥ ∞ + ∥N 2 ( D)∥ ∞ + ∥N 2 (D)∥ ∞ ≤ 1 n max i (∥x i ∥ 2 (|ỹ i |) + ∥x i ∥ 2 (|ỹ i |)) + 8rτ y 2 log 1 δ log d εn ≤ 2rτ y n + 8rτ y 2 log 1 δ log d εn ≤O   rτ y log 1 δ log d εn   ≤ λ nFor the second term of equation 7, note that for any two nonsingular square matrices A, B with the same size, it holds that A -1 -B -1 = -B -1 (A -B)A -1 . Thus, by Lemma 1, we have∥ Σ X X ( D) -1 -Σ X X (D) -1 ∥ ∞ ≤∥ Σ X X ( D) -1 ∥ ∞ ∥ -Σ X X (D) -1 ∥ ∞ ∥ Σ X X ( D) -Σ X X (D) ∥ ∞ ≤ 4 κ 2 ∞ ∥ Σ X X ( D) -Σ∥ ∞ + ∥ Σ X X (D) -Σ∥ ∞ ≤c 2   sr 2 log d log( 1 δ ) κ 2 ∞ ε √ n   ≤ λ nCombining above, we haveEQUATIONTo further our analysis, we introduce the notion of decomposibility of norm and subspace compatibility constant. We call M, M ⊥ a subspace pairs where M is the model subspace in which the estimated model parameter θ * and similarly structured parameters lie, and which is typically low-dimensional, while M ⊥ is the perturbation subspace of parameters that represents perturbations away from the model subspace.Definition 12. A regularization function R is said to be decomposable with respect to a subspace pairM, M ⊥ , if R(u + v) = R(u) + R(v), for all u ∈ M, v ∈ M ⊥ .Note that when R(•) is a norm, by the triangle inequality, the LHS is always less than or equal to the RHS, so that the equality indicates the largest possible value for the LHS. For notational simplicity, we use (S, S c ) instead of an arbitrary subspace pair M, M ⊥ .Definition 13. The subspace compatibility constant is defined asM : Ψ(M, ∥ • ∥) := sup u∈M\{0} R(u) ∥u∥ .It is noted that subspace compatibility constant that captures the relationship between the regularization function R(•) and the error norm ∥ • ∥, over vectors in subspace. In our proof, it is clear that the regularization is the ℓ 1 -norm, which is decomposable with respect to the subspace pair. We also denote the subspace of vectors in R d by S. Since we assume k is the sparsity level of θ * , the cardinality of the support set of the model space where the true parameter θ * lies. It can be seen that any parameter θ ∈ S would be at-most k-sparse. Therefore, we have thatΨ (S, ∥ • ∥ 2 ) ≤ √ k.Additionally, we use the notion Π S (∆) to represent the ℓ 2 projection onto the model space S. Then, by the assumption of the statement that θ * S c = 0, and the decomposability of ∥ • ∥ 1 with respect to (S, S c ),EQUATION)where the equality (i) holds by the triangle inequality, which is the basic property of norms. Since we are minimizing the objective function ∥ θP (D)∥ 1 , we obtain the inequality of ∥ θP ( D)+ ∆∥ 1 = ∥ θP (D)∥ 1 ≤ ∥ θP ( D)∥ 1 .Combining this inequality with equation 9, we haveEQUATION)Armed with inequalities equation 8 and equation 10, we utilize the Hölder's inequality and the decomposability of our regularizer ∥ • ∥ 1 in order to derive the error bounds in terms of ℓ 2 norm:∥∆∥ 2 2 = ⟨∆, ∆⟩ ≤ ∥∆∥ ∞ ∥∆∥ 1 ≤ ∥∆∥ ∞ (∥Π S (∆)∥ 1 + ∥Π S c (∆)) ∥ 1 .Since the error vector ∆ satisfies the inequality equation 10,EQUATIONCombining all the pieces together yields∥∆∥ 2 2 ≤ 4Ψ(S)λ n ∥Π S (∆)∥ 2 where Ψ(M) is the abbreviation for Ψ (S, ∥ • ∥ 2 ).Notice that the projection operator is non-expansive, ∥Π S (∆)∥ 2 2 ≤ ∥∆∥ 2 2 . Hence, we obtain ∥Π S (∆)∥ 2 ≤ 4Ψ(S)λ n , and plugging it back into equation 11 yields the ℓ 2 error bounds.Proof of Lemma 20. Define a sequence of datasets D 0 , D 1 , • • • , D k , such that D 0 = D, D k = D ′ , and for each i ∈ [k], D i , D i-1 differ on at most one agent's dataset. Then, by the triangular inequality, we obtain∥ θ(D) -θ(D ′ )∥ 2 = ∥ θ(D 0 ) -θ(D k )∥ 2 = ∥ k i=1 θ(D i-1 ) -θ(D i )∥ 2 ≤ k i=1 ∥ θ(D i-1 ) -θ(D i )∥ 2 ≤ g∆ n .with probability at least 1 -kγ n by taking a union bound over g failure probabilities γ n .Proof of Lemma 22. Before giving theoretical analysis, we first prove that Σ X X is invertible with high probability. With the help of Weyl's Inequality (Lemma 23), we can see that to showΣ X X is invertible it is sufficient to show that ∥ Σ X X -Σ∥ 2 ≤ λmin(Σ). This is due to that by Lemma 23, we haveλ min (Σ) -∥ Σ X X -Σ∥ 2 ≤ λ min ( Σ X X ). Thus, if ∥ Σ X X -Σ∥ 2 ≤ λmin(Σ) 2 , we have λ min ( Σ X X ) ≥ λmin(Σ) 2 > 0. Thus, by Lemma 1, it is sufficient to show that λ min (Σ) ≥ O sr 2 √ log d log 1 δ ε √ n, which is true under the assumption of n ≥ Ωs 2 r 4 log d log 1 δ ε 2 λmin(Σ) 2. Thus, with probability at least 1 -exp(-Ω(d)) -ξ, it is invertible. In the following we will always assume that this event holds.To prove the theorem, we first introduce the following lemma on the estimation error of θ in equation 2.Note that this is a non-probabilistic result, and it holds deterministically for any selection of λ n or any distributional setting of the covariates x i . Our goal is to show thatλ n ≥ θ * -Σ X X -1 Σ X Y ∞under the assumptions specified in Lemma 21.EQUATION)where the vector N 2 ∈ R d is sampled from N (0,32τ 2 x τ 2 y log 1.25 δ n 2 ε 2 I d ).We first develop upper bound of Σ X X . For any nonzero vector w ∈ R d , Note thatΣ X X w ∞ = Σ X X w -Σw + Σw ∞ ≥ ∥Σw∥ ∞ -Σ X X -Σ w ∞ ≥ κ ∞ -Σ X X -Σ ∞ ∥w∥ ∞ .Our objective is to find a sufficiently large n such that Σ X X -Σ ∞ is less than κ∞ 2 .By Lemma 1 we can see the following:∥ Σ X X -Σ∥ 2 ∞ = ∥ Σ X X -Σ∥ 2 1 ≤ O s 2 log d log 1 δ r 4 nε 2 1-q + log d log 1 δ r 4 nε 2 (13) Thus, when n ≥ Ω s 2 r 4 log d log 1 δ ε 2 κ∞ , we have Σ X X w ∞ ≥ κ∞ 2 ∥w∥ ∞ , which implies Σ X X -1 ∞ ≤ 2 κ∞ .Given sufficiently large n, from equation 12, we have:EQUATIONWe will bound the above four terms one by one.For1 ≤ j ≤ d, we have Var (ỹ i x ij ) ≤ E (ỹ i x ij ) 2 ≤ E (y i x ij ) 2 ≤ Ey 4 i Ex 4 ij =: v 1 < ∞. In addition, E |ỹ i x ij | p ≤ (τ x τ y ) p-2 v 1 holds.Therefore, according to Lemma 13, we have:P σ Y xj -σ Y xj ≥ 2v 1 t n + cτ x τ y t n ≤ exp(-t),whereσ Y xj = 1 n n i=1 ỹi x ij , σ Y xj = Eỹ i x ij and c is a certain constant.Then by the union bound, the following can be derived:P |T 1 | > 2v 1 t n + cτ x τ y t n ≤ d exp(-t).Next, we give an estimation of T 2 . Note that for 1 ≤ j ≤ d, by lemma 9 we have:Eỹ i x ij -Ey i x ij = Eỹ i x ij -Eỹ i x ij + Eỹ i x ij -Ey i x ij = Eỹ i ( x ij -x ij ) + E (ỹ i -y i ) x ij ≤ E y 2 i ( x ij -x ij ) 2 P (|x ij | ≥ τ x ) + E (ỹ i -y i ) 2 x 2 ij P (|y i | ≥ τ y ) ≤ √ v 1 2e -τ 2 x 2σ 2 + 2e - τ 2 y 2σ 2 , which shows that T 2 ≤ √ v 1 2e -τ 2 x 2σ 2 + 2e - τ 2 y 2σ 2 .To upper bound term T 3 , we need to evaluate ∥ Σ X X -Σ∥ ∞ and we can reuse obtained results from Lemma 1.We can see that T 3 is bounded by O(√ log d log 1 δ √ nε). Here we used the fact that Σ X X -Σ is a symmetric matrix.∥( Σ X X -Σ)θ * ∥ ∞ ≤ ∥ Σ X X -Σ∥ 2 ∥θ * ∥ 2 ≤ ∥ Σ X X -Σ∥ 1 ∥θ * ∥ 2 ≤ O(r 2 ( log d log 1 δ nε 2 )) ∥θ * ∥ 2 ,given the selection of r.The last term of equation 14 can be bounded by Gaussian tail bound by lemma 11. With probability 1 -O(d -8 ), we have:EQUATIONFinally combining all pieces, we can find that T 3 is the dominating term. Sinceλ n ≥ θ * -Σ X X -1 Σ X Y ∞, Lemma 21 implies that with probability at least1 -O(d -8 ) -e -Ω(d) , θ * -Σ X X -1 Σ X Y + N 2 2 ≤ O   k log d log 1 δ √ nε   ,which completes our proof of Theorem.Proof of Lemma 1. Our goal is to proveE∥ Σ X X -Σ∥ 2 ≤ C   s 2 log d n + 4r 2 2 ln 1.25/δ √ log d εγn 2-2q + log d n + 4r 2 2 ln 1.25/δ √ log d εγn 2   (16) for some constant C. Since Σ X X -Σ is symmetric, we know that ∥ Σ X X -Σ∥ 1 = ∥ Σ X X -Σ∥ ∞ .Thus, it suffices to prove that the bound in equation 16 holds for ∥ Σ X X -Σ∥ 1 .Define the event A ij byEQUATIONThen by lemma 25, we haveEQUATION)Note the first term in equation 18 is bounded by Cs2 log d n + 4r 2 √ 2 ln 1.25/δ √ log d εγn 2-2q, and the first term is dominating, while the second term E∥D∥ 2 1 is comparably negligible. By settingk * = s log d n + 4r 2 √ 2 ln 1.25/δ √ log d εγn -q, we have:i̸ =j min σ xx T ,ij , γ log d n + 4r 2 2 ln 1.25/δ √ log d εn ≤ γ   i≤k * + i>k *   min σ [i]j , log d n + 4r 2 2 ln 1.25/δ √ log d εγn ≤ C 5 k * log d n + 4r 2 2 ln 1.25/δ √ log d εγn + C 5 i>k * s i 1/q ≤ C 6 k * log d n + 4r 2 2 ln 1.25/δ √ log d εγn + s 1/q • (k * ) 1-1/q ≤ C 7 s log d n + 4r 2 2 ln 1.25/δ √ log d εγn 1-q which implies equation 16 if E∥D∥ 2 1 = O 1 n . We shall now show that E∥D∥ 2 1 = O 1 n . Note that: E∥D∥ 2 1 ≤ d ij Ed 2 ij = d ij E d 2 ij I A c ij ∩ σxx T ,ij = σxx T ,ij + d 2 ij I A c ij ∩ σxx T ,ij = 0 = d ij E σxx T ,ij -σ xx T ,ij 2 I A c ij + d ij Eσ 2 xx T ,ij I A c ij ∩ σxx T ,ij = 0 ≡ R 1 + R 2Lemma 25 yields that P A c ij ≤ 2C 1 d -9/2 , and the Whittle inequality (Theorem 2 in [56] ) implies σxx T ,ij -σ xx T ,ij has all finite moments under the sub-Gaussianity condition. Hence, we have:EQUATIONP 2/3 A c ij ≤ C 8 d • d 2 • 1 n • d -3 = C 8 /nOn the other hand,R 2 = d ij Eσ 2 xx T ,ij I A c ij ∩ σxx T ,ij = 0 = d ij Eσ 2 xx T ,ij I σ xx T ,ij ≥ 4 γ log d n + 4r 2 2 ln 1.25/δ √ log d ε I σxx T ,ij ≤ γ log d n + 4r 2 2 ln 1.25/δ √ log d ε ≤ d ij σ 2 xx T ,ij EI σ xx T ,ij 4γ log d n + 16r 2 2 ln 1.25/δ √ log d ε I σ xx T ,ij -σxx T ,ij -σ xx T ,ij ≤ γ log d n + 16r 2 2 ln 1.25/δ √ log d ε ≤ d ij σ 2 xx T ,ij EI σxx T ,ij -σ xx T ,ij > 3 4 σ xx T ,ij I σ xx T ,ij ≥ 4 γ log d n + 16r 2 2 ln 1.25/δ √ log d ε ≤ d ij σ 2 xx T ,ij EI σ xx T ,ij > 4γ log p n + 16r 2 2 ln 1.25/δ √ log p nε I σxx T ,ij -σ xx T ,ij + |n 1,ij | ≥ 3 4 σ xx T ,ij ≤ d ij σ 2 xx T ,ij P σxx T ,ij -σ xx T ,ij ≥ 3 4 σ xx T ,ij -|n 1,ij | σ xx T ,ij > 4γ log d n + 16r 2 2 ln 1.25/δ √ log d nε = d ij σ 2 xx T ,ij P σxx T ,ij -σ xx T ,ij ≥ 3 4 σ xx T ,ij -|n 1,ij | |n 1,ij | ≤ 1 4 σ xx T ,ij σ xx T ,ij > 4γ log d n + 16r 2 2 ln 1.25/δ √ log d nε + d ij σ 2 xx T ,ij P σxx T ,ij -σ xx T ,ij ≥ 3 4 σ xx T ,ij -|n 1,ij | |n 1,ij | ≥ 1 4 σ xx T ,ij σ xx T ,ij > 4γ log d n + 16r 2 2 ln 1.25/δ √ log d nεThis gives us:EQUATIONFor the first term of equation 19, by Lemma 24 we have:d ij σ 2 xx T ,ij P σxx T ,ij -σ xx T ,ij ≥ 1 2 σ xx T ,ij σ xx T ,ij ≥ 4γ log d n ≤ d n ij nσ 2 xx T ,ij exp -n 2σ 2 xx T ,ij γ 2 I σ xx T ,ij ≥ 4γ log d n ≤ d n ij nσ 2 xx T ,ij exp -n σ 2 xx T ,ij γ 2 exp -n σ 2 xx T ,ij γ 2 I σ xx T ,ij ≥ 4γ log d n ≤ C d 3 n d -16 = O 1 nFor the second term of equation 19, by Lemmas 11 and 24 we haved ij σ 2 xx T ,ij P |n 1,ij | ≥ 1 4 σ xx T ,ij σ xx T ,ij > 4γ log d n + 16r 2 2 ln 1.25/δ √ log d nε ≤ d ij σ 2 xx T ,ij P |n 1,ij | ≥ γ log d n + 4 2 ln 1.25/δ log d nε   P |n 1,ij | > 1 4 σ xx T ,ij ≤ Cd ij σ 2 xx T ,ij • exp      - γ log d n + 4σ 1 √ log d 2 2σ 2 1      exp - σ 2 xx T ,ij 32σ 2 1 ≤ Cσ 2 1 d • d 2 exp - γ 2 log d 2nσ 2 1 d -8 ≤ Cσ 2 1 d -5 2nσ 2 1 γ 2 log d = O log 1/δ nε 2 .Putting R 1 and R 2 together yields that for some constant C > 0,E∥D∥ 2 1 ≤ C n .Proof of Lemma. 25. Firstly, let us note that ΣX X = Σ X X + N 1 = n i xi xT i + N 1 .Therefore by Lemma 24 and Lemma 11 with probability at least 1 -Cd -8 , for all 1 ≤ i, j ≤ d, and for some constants γ and C that depends on σ N1 ,EQUATION)Define the eventA ij = σxx T ,ij > γ log d n + 4r 2 √ 2 ln 1.25/δ √ log d εn .Let Σ X X = σxx T ,ij 1≤i,j≤d and N 1 = (n 1,ij ) 1≤i,j≤d .We have:EQUATIONBy the triangle inequality, it is easy to see thatEQUATIONA c ij = σxx T ,ij -σ xx T ,ij + σ xx T ,ij ≤ γ log d n + 4r 2 2 ln 1.25/δ √ log d εn ⊂ σxx T ,ij -σ xx T ,ij > σ xx T ,ij -γ log d n + 4r 2 2 ln 1.25/δ √ log d εn .Depending on the value of σ xx T ,ij , we need to consider the following three cases. For this case, we have:P (A ij ) ≤ P σxx T ,ij -σ xx T ,ij > 3γ 4 log d n + 3 2 ln 1.25/δ √ log d nε ≤ C 1 d -9 2 + 2d -9 2 .This is due to the fact:P σxx T ,ij -σ xx T ,ij > 3γ 4 log d n + 3 2 ln 1.25/δ √ log d nε ≤ P σxx T ,ij -σ xx T ,ij > 3γ 4 log d n + 3 2 ln 1.25/δ √ log d nε -|n 1,ij | = P B ij 3 2 ln 1.25/δ √ log d nε -|n 1,ij | > 0 +P B ij 3 2 ln 1.25/δ √ log d nε -|n 1,ij | ≤ 0 ≤ P σxx T ,ij -σ xx T ,ij > 3γ 4 log d n + P 2 3 ln 1.25/δ log d nε ≤ |n 1,ij | ≤ C 1 d -9 2 + 2d -9 2 ,where event For this case, we haveB ij denotes B ij = σxx T ,ij -σ xx T ,ij > 3γP A c ij ≤ P σxx T ,ij -σ xx T ,ij ≥ γ log d n + r 2 2 ln 1.25/δ √ log d εn ≤ C 1 d -8 + 2d -8 ,where the proof is identical to the proof for case 1. Thus, with probability at least 1 -C 1 d -9 2 -2d -8 , we have:σxx T ,ij -σ xx T ,ij = σxx T ,ij -σ xx T ,ij .Also, by equation 20, equation 5 also holds.Case 3. Otherwise,γ 4 log d n + r 2 2 log 1.25/δ √ log d nε ≤ σ xx T ,ij ≤ 2γ log d n + 8r 2 2 ln 1.25/δ √ log d nε .For this case, we have or not, which completes the proof of Lemma 25.σxx T ,ij -σ xx T ,ij = σ xx T ,ij or σxx T ,ij -σ xx T ,ij . When σ xx T ,ij ≤ γ log d n + 4r 2 √Note that B a1,a2 (p, q) = a 1 -a 2 (p -2pq + q 2 ) is linear with respect to p, and is a strictly concave function of q maximized at q = p. Thus, equation 25 is upper bounded by the following with probability 1 -C 1 n -Ω(1)B a1,a2 E ⟨x i , θP ( Db )⟩|D i , c i , E ⟨x i , θP ( Db )⟩|D i , c i -B a1,a2 E[⟨x i , θP ( Db )⟩|D i , c i ], ⟨x i , E θ∼p(θ|Di) [θ]⟩ = a 2 E[⟨x i , θP ( Db )⟩|D i , c i ] -⟨x i , E θ∼p(θ|Di) [θ]⟩ 2 = a 2 E[⟨x i , θP ( Db )⟩ -⟨x i , E θ∼p(θ|Di) [θ]⟩|D i , c i ] 2 ≤ a 2 E[x T i ( θP ( Db ) -E θ∼p(θ|Di) [θ])|D i , c i ] 2 ≤ a 2 ∥x i ∥ 2 2 ∥E[ θP ( Db ) -E θ∼p(θ|Di) [θ]|D i , c i ]∥ 2 2 ≤ r 2 a 2 ∥E[ θP ( Db ) -E θ∼p(θ|Di) [θ]|D i , c i ]∥ 2 2 .We continue by bounding the termEQUATIONFor the first term of equation 26, since agent i believes that with at least probability 1 -β, at most αn agents will misreport their datasets under threshold strategy σ τ α,β , datasets D b and Db differ only on at most αn agents' datasets. By Lemma 20 and Lemma 4, we set the constraint boundλ n = O r 2 √ log d log 1 δ √ nε, when n is sufficient large such that n ≥ Ω(s 2 r 4 log d log 1 δ ε 2 κ∞), with probability at least 1 -β -O(αnd -Ω(1) ) we have thatEQUATIONFor the second term of equation 26 :E[ θP (D b )|D i ] -E θ∼p(θ|Di) [θ] = E D b ∼p(D b |Di) [ θP (D b )] -E θ∼p(θ|Di) [θ] = E θ∼p(θ|Di) [E D b ∼p(D b |θ) [ θP (D b )]|θ] -E θ∼p(θ|Di) [θ] = E θ∼p(θ|Di) [E D b ∼p(D b |θ) [ θP (D b ) -θ]|θ]. Since p(D b |θ) = p(X b , y b |θ) = p(y b |X b , θ)p(X b |θ) = p(y b |X b , θ)p(X b ),we haveE D b ∼p(D b |θ) [ θ(D b ) -θ] = E X b [E y b [ θP (X b , y b ) -θ]|X b , θ].Since we have the prior knowledge that ∥θ * ∥ 2 ≤ τ θ . Thus, for the posterior distribution θ ∼ p(θ| Di ) it will also have ∥θ∥ 2 ≤ τ θ . By Jensen's inequality, Theorem 3 and Lemma 15, we have∥E[ θP (D b )|D i ] -E θ∼p(θ|Di) [θ]∥ 2 ≤ E θ∼p(θ|Di),X b [E y b [∥ θP (X b , y b ) -θ∥ 2 |X b , θ]] ≤ E θ∼p(θ|Di),X b [E y b [∥ θP (X b , y b ) -θ∥ 2 |X b , θ]] ≤ O   r 2 k log d log 1 δ nε  In addition to an increased payment, agent i may also experience decreased privacy costs from misreporting. By Assumption 3, this decrease in privacy costs is bounded above by c i 8(1 + 3δ)ε 3 . Since we have assumed c i ≤ τ α,β , the decrease in privacy costs for agent i is bounded above by τ α,β 8(1 + 3δ)ε 3 . Hence, agent i's total incentive to deviate is bounded above byη = O a 2 α 2 r 6 k log d log 1 δ ε 2 + r 4 log d log 1 δ n 2 ε 2 + τ α,β δε 2 .Proof of Theorem 6. Let agent i have privacy cost c i ≤ τ α,β and consider agent i's utility from participating in the mechanism. Suppose agent i is in group 1 -b, then their expected utility isEQUATIONNote that EQUATIONa 1 ≥ a 2 (rτ θ + 3r 2 τ 2 θ ) + τ α,β 8(1 + 3δ)ε 3 .Proof of Theorem 7. Note thatB a1,a2 (p, q) ≤ B a1,a2 (p, p) = a 1 -a 2 (p -p 2 ) ≤ a 1 + a 2 (|p| + |p| 2 ), thus B = n i=1 E[π i ] = n i=1 E[B a1,a2 ⟨x i , θP ( Db )⟩, ⟨x i , E θ∼p(θ| Di) [θ]⟩ |D i , c i ] ≤ n(a 1 + a 2 (rτ θ + r 2 τ 2 θ )).Proof of Corollary 8. For any ξ ∈ ( 1 3 , 1 2 ) and c > 0, we set ε= n -ξ , δ = n -Ω(1) , α = Θ(n -3ξ ), β = Θ(n -c ), a 1 = a 2 (rτ θ + 3r 2 τ 2 θ ) + τ α,β 8(1 + 3δ)ε 3 , a 2 = O(n -3ξ ).Note that by choosing ξ ∈ ( 1 3 , 1 2 ), we ensure that αn = o(1).Recall that by Theorem 3, the private estimator is O knα2 r 4 log d log 1 ξ ε 2 + r 4 log d log 1 δ nε 2 -accurate. Note that O( nα 2 ε 2 ) = O(n 1-4ξ ), O( 1 nε 2 ) = O(n 2ξ-1 ). Since for any ξ ∈ ( 1 3 , 1 2 ), we always have 1 -4ξ < 2ξ -1, we obtain E∥ θP ( D) -θ * ∥ 2 2 = O(n 2ξ-1). To bound the expected budget and truthfulness, we first consider bounding the threshold value τ α,β and the term 8(1 + 3δ)ε 3 . By Lemma 14, τ α,β ≤ 1 λ log 1 αβ = Θ( 3ξ+c λ log n) = Θ(1). Combining these, we get τ α,β 8(1 + 3δ)ε 3 = O(n -3ξ ). Now we bound the term η for the truthfulness. Recall that by Theorem 5, the first term of the truthfulness bound is a 2nα 2 r 6 k log d log 1 δ ε 2 + r 4 log d log 1 δ nε 2 = O(n -1-ξ ) , and the second term of the bound is τ α,β 8(1 + 3δ)ε 3 = O(n -3ξ ), thus η = O(n -1-ξ + n -3ξ ) = O(n -1-ξ ).Then we consider individual rationality. By the choice of and Theorem 6, the mechanism is individual rational for at least 1 -O(n -3ξ ) fraction of agents.Lastly, we consider total payment made to the agents. By Theorem 7, the total expected budget isB = O n(a 1 + a 2 (rτ θ + r 2 τ 2 θ )) = O(n(a 2 + ε 3 + a 2 )) = O(n 1-3ξ ).This paper presents work whose goal is to advance the field of machine learning theory. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.NeurIPS Paper Checklist Justification: We have provided a detailed description of the claims in Section 1 which summarizes the major contributions.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.In this paper, individuals, data providers, and participants are the same and all represent agents. 38th Conference on Neural Information Processing Systems (NeurIPS2024).To make our results comparable to the previous results, we assume κ∞ and κx are constants for simplicity.In order to make our result comparable to previous work on linear regression with bounded covariates, we assume the variance proxy is σ 2 /d so that with high probability ∥xi∥2 is bounded by some constant.log 1.25/δ √ log d nε . 


Decision: Two paper reviews are positive, and one negative at a reject. 

However, as an expert in both differential privacy and mechanism design, and after taking a look at the paper myself, I should note that I strongly disagree with the negative assessment of Reviewer BxFH. Reviewer BxFH's review seems to conflate and confuse several differential privacy and mechanism design and complain about lack of novelty in comparison to work that is only related at a superficial level, in that it includes the keywords "differential privacy", "regression", and "mechanism design". Reviewer BxFH also largely ignored author responses, as well as my own comment, and never replied to the last comment trying to clarify the issues with the paper. I think Review BxFH provides largely insufficient evidence to reject this paper. 

I recommend to accept the paper as a poster.

Reviews: review: paper_summary: paper_summary: This paper focuses on mechanism design that incentivizes truthful data reporting while preserving privacy in the context of high dimensional sparse linear regression. The proposed mechanism is $(o(1),O(n^{-Omega(1)}))$-jointly differentially private, provides an estimator that is $o(1)$ accurate, is an approximate Bayes NE where most of the agents report truthfully, asymptotically individually rational, and requires a small payment budget.
strength_weakness: strength_weakness: Currently, each agent only collects one data point. Is it possible to study the free-riding issue as well under the current framework?
questions: questions: See above
limitations: limitations: See above
paper_summary: paper_summary: The paper solves the problem of high dimensional sparse regression with subgaussian covariates. Along with doing that they also ensure differential privacy of the data providers. Finally, they also provide a payment scheme that is individually rational and which incentivizes truthfulness.
strength_weakness: strength_weakness: 1) The paper seems to be a slight extension of differentially private logistic regression while also incorporating payments into it which does not seem like a major extension given the earlier works of Fallah et al. or Anjarlekar et al. have incorporated incentive-compatible payment mechanisms in traditional DP settings with Fallah et al. solving the problem for mean estimation while Anjarlekar et al. extending that work for the case of logistic regression.
2) The assumptions made in the paper do not seem practical (for example assumptions 3 and 4)
questions: questions: 1) It is unclear to me why the authors have used Joint Differential Privacy instead of the original DP definition. Can the authors provide more justification for this?
2) Assumption 3 seems a bit vague. Can the authors clarify the specific structure of the upper bound used in the assumption? It seems more clear to have f(.) which is a monotonically increasing convex function of $\epsilon$.
3) Can the authors clarify more about the practical validity of Assumption 4?
4) A literature survey related to incorporating payments in differentially private models seems incomplete. Some relevant works are as follows
[a] Justin Kang, Ramtin Pedarsani, & Kannan Ramchandran. (2024). The Fair Value of Data Under Heterogeneous Privacy Constraints in Federated Learning.
[b] Ameya Anjarlekar, Rasoul Etesami, & R. Srikant. (2023). Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regression.
5) Can be approach be extended to scenarios incorporating heterogeneous differential privacy? Similarly can the proposed approach work for larger models such as deep neural networks?
6) It would have been better to add some experimental results to highlight how the payments and model error varies with a change in the differential privacy guarantees and other parameters.
limitations: limitations: NA
paper_summary: paper_summary: The authors present an $\varepsilon$-Bayesian incentive compatible and individually rational $k$-sparse linear regression algorithm with side payments for (almost all) privacy-oriented data providing agents. Remarkably, in the limit $d >> n >> \log d$, the accuracy and the needed budget both vanish.
strength_weakness: strength_weakness: The paper already has a lot of different notations, which are easily confusing for the reader. It is thus very important to significantly improve the writing, which is too often extremely hard on the reader:
- Isn't the $\Pi_{\tau_\theta}$ the same operator as clipping (lines 2 and 3 of Algorithm 1)? It would make it much easier to read if all identical operators were written in the same way.
- The partition $\hat D^0 \cup \hat D^1$ should be presented before its use in line 273.
- Assumption 5 has a typo (I guess). It should be $D-i$ rather than $D_j$. There should also be a quantification over $i$ (unless each (c_i, D_i) is iid?).
- The "symmetric threshold strategy" is used in the main text without definition (and without even a reference to the appendix!).

The paper makes a common ground-truth assumption (same $\theta^*$). In practice, this may be unrealistic.
questions: questions: I don't see Assumption 3 as a generalization of Cummings et al. Given that $\delta \leq 1$, the assumption is essentially equivalent to (at least implied by) $f_i \leq 2c_i \varepsilon^3$, which is more demanding than $f_i \leq c_i \varepsilon^2$. It should be rather presented as a relaxation. Do the authors agree?

I don't understand the claim (line 162) that "the one-round communication necessitates a closed-form estimator". Wouldn't any algorithm work? If so, I suggest that the authors merely present their new estimator as a proposal for covariance estimation, with a high-probability inversion guarantee (and even point to Theorem 3 as the end goal).

I fail to understand how $\theta^*$ can be recovered without assumptions on the thresholds $r$, $\tau_x$, $\tau_y$ and $\lambda_n$. It seems that this should not be possible for arbitrary values of these parameters. Can the authors clarify this?

Right now, though I think I mostly understand the algorithm, and its implications in terms of privacy, strategyproofness and individual rationality, its accuracy is a mystery to me, which prevents me from providing a larger score. I would be greatly thankful to the authors if they could help me gain insights into this aspect of their result.
limitations: limitations: The authors should better stress that
(i) Agents' "rationality" is merely on privacy leakage (they are indifferent to the trained model's behavior).
(ii) Agents are assumed to have the same labeling function (parameter $\theta^*$).
(iii) (Individually rational) agents whose data is too different are more likely removed from the system.

Comments: title: (Cont'd) Response to Reviewer BxFH' s questions
(Continued) Re: Q4
comment: Dear Reviewer BxFH,

Please see above our detailed response to your question regarding our assumption 3. We believe that we have used a very general and practical bounding function. If you think our response clarifies your concerns, we kindly ask you to consider raising the score. 

Best Regards,
Authors
**Our upper bounding function has to include $c_i, \epsilon$ and $\delta$, where $c_i$ is the privacy cost coefficient.**  

| **Paper** | **Upper Bounding Function**          | **Data Assumption** | **Privacy Guarantee**         |
|-----------|--------------------------------------|---------------------|-------------------------------|
| Ours      | $c_i(1+\delta) \epsilon^3 $      | Sub-Gaussian        | $(\epsilon, \delta)$-JDP    |
| [1]       |$  c_i(1+\gamma) \epsilon^4    $    | Sub-Gaussian        | $(\epsilon, \gamma)$-RJDP   |
| [1]       |$ c_i(1+\gamma) \epsilon^9   $     | Heavy-tailed        | $(\epsilon, \gamma)$-RJDP   |
| [2]       | $ c_i \epsilon^2     $             | Bounded       |$ \epsilon$-JDP            |

It is clear that due to different data settings, our assumption is weaker than that of [1] but is stronger than the assumption in [2] which was first introduced by [3] and later adopted by [4]. 

To see why the upper bounding function in [2] is quadratic in $\epsilon$, we additionally define $g_i$ as the privacy cost for reporting $(x_i
, y_i)$ to the mechanism $M$ when all other agents report $(X_{-i}, y_{−i})$ and the output is $\hat{\theta}$. 

In [3], the authors assume that

$g_i\left(M, \hat{\theta},\left(x_i, y_i\right),\left(X_{-i}, y_{-i}\right)\right) \leq c_i \ln \left(\max_{y_i^{\prime}, y_i^{\prime \prime}} \frac{\operatorname{Pr}\left[M\left(X, y_i^{\prime}, y_{-i}\right)=\hat{\theta}\right]}{\operatorname{Pr}\left[M\left(X, y_i^{\prime \prime}, y_{-i}\right)=\hat{\theta}\right]}\right)$.

This assumption is natural because if $g_i$ is small if the agent $i$'s report exerts little influence on $\hat{\theta}$ and therefore should be upper bounded by a function that depends on the effect that the agent $i$’s report has on the mechanism’s output.

And by Composition Lemma (Lemma 3.2 in [3]), 

$\mathbb{E}\left[g_i\left(M, M(X, y),\left(x_i, y_i\right),\left(X_{-i}, y_{-i}\right)\right)\right]-\mathbb{E}\left[g_i\left(M, M\left(X, y_i^{\prime}, y_{-i}\right),\left(x_i, y_i\right),\left(X_{-i}, y_{-i}\right)\right)\right] \leq 2 c_i \epsilon\left(e^\epsilon-1\right) \leq 4 c_i \epsilon^2$

Therefore by setting the privacy cost function $f_i = \frac{1}{4} \mathbb{E}\left[g_i\left(M, M(X, y),\left(x_i, y_i\right),\left(X_{-i}, y_{-i}\right)\right)\right]$, it can be interpreted as the agent $i$’s expected cost for participating in the mechanism up to a scaling constant.

Given that our assumption regarding $f_i$ stems from natural ground and has been used widely in similar settings, we argue that it is a reasonable assumption.

[1] Qiu, Yuan, Jinyan Liu, and Di Wang. "Truthful Generalized Linear Models." arXiv preprint arXiv:2209.07815 (2022). 


[2]  Cummings, Rachel, Stratis Ioannidis, and Katrina Ligett. "Truthful linear regression." Conference on Learning Theory. PMLR, 2015.

[3] Chen, Yiling, et al. "Truthful mechanisms for agents that value privacy." ACM Transactions on Economics and Computation (TEAC) 4.3 (2016): 1-30.

[4] Ghosh, Arpita, et al. "Buying private data without verification." Proceedings of the fifteenth ACM conference on Economics and computation. 2014.
I am still not convinced about the choice of the bounding function. Do the results still hold if we consider a general monotonic bounding function?
Thank you for your reply. I have no more questions.
We thank the reviewer for their time and for mentioning the related work which we have not included. We will add these to our paper. If our response has addressed your concerns and positively influenced your view of our paper, we kindly ask you to consider revising the score.
We appreciate the reviewer's recognition and feedback. For the camera-ready version, we will incorporate the requested clarifications and definitions on the additional page to ensure completeness. We will also correct any typos and unify the notation to enhance readability. If our response has addressed your concerns and positively influenced your view of our paper, we kindly ask you to consider revising the score.
I thank the authors for their response, which clarified several points. Overall, I believe that the paper would greatly gain from improved writing, which is why I stick with my rating. But I fully recognize the value of their contribution.
>**Q1: It is unclear to me why the authors have used Joint Differential Privacy instead of the original DP definition. Can the authors provide more justification for this?**

Full differential privacy requires that all outputs by the mechanism, including the payment it allocates to a user, are insensitive to every user’s input. In our strategic user setting,  the payment to every user is supposed to be kept secret. Therefore, it is more natural to assume that the payment $\pi_i$ to each user is only observable by the user $i$ while the estimate $\hat{\theta}$ is publicly observable. This consideration exactly falls into the motivation of Joint Differential Privacy.

>**Q2: Assumption 3 seems a bit vague. Can the authors clarify the specific structure of the upper bound used in the assumption? It seems more clear to have $f(.)$ which is a monotonically increasing convex function of $\epsilon$.**

The monotonicity in $\epsilon$ is intuitive: smaller values imply stronger privacy properties. Specifically, $\epsilon = 0 $ indicates the
output is independent of user $i$’s data. Moreover, we use cubic term in $\epsilon$ to provide stronger constraints. **However, it should be noted that the bounding function $F = c_i (\delta+ 1) \epsilon^3$ is not associated with convexity. In our proof, we also did not use the convexity property.**

>**Q3: Can the authors clarify more about the practical validity of Assumption 4?**

In Assumption 4, we introduce the privacy cost coefficient $c_i$ as a random variable, sampled from some distribution. As mentioned earlier, the payment $\pi_i$ to each user is supposed to be private and the amount of payment is strongly linked to the privacy cost $c_i$. Therefore, it is very natural to assume that $c_i$ depends on each user's own data $D_i = (x_i,y_i)$ and conditioned on $D_i$, $c_i$ does not reveal any additional information on any other user's cost coefficient or data. Otherwise, a strategic user can use his privacy cost coefficient to infer other users' payments.


>**Q4: A literature survey related to incorporating payments in differentially private models seems incomplete. Some relevant works are as follows [a] Justin Kang, Ramtin Pedarsani,  Kannan Ramchandran. (2024). The Fair Value of Data Under Heterogeneous Privacy Constraints in Federated Learning. [b] Ameya Anjarlekar, Rasoul Etesami,  R. Srikant. (2023). Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regression.**

We thank the reviewer for providing the relevant literature to us. We will add them to the related work section.

>**Q5: Can be approach be extended to scenarios incorporating heterogeneous differential privacy? Similarly can the proposed approach work for larger models such as deep neural networks?**

Sadly, our current framework is not suitable for extending to other scenarios like heterogeneous differential privacy. This is because our privacy guarantee relies on the Billboard Lemma to broadcast the original DP to JDP, and it is unknown whether there is a 
heterogeneous version of Billboard Lemma.

Meanwhile, designing high-dimensional truthful mechanisms with privacy constraints is an 
intrinsically hard problem. Our mechanism cannot be directly applied to larger models such as DNNs like many other truthful mechanisms. Given this, we believe that our work has been a leap and paved the way for future research.

**Please see the above for response to question 6**
>**Q4: Right now, though I think I mostly understand the algorithm, and its implications in terms of privacy, strategyproofness and individual rationality, its accuracy is a mystery to me, which prevents me from providing a larger score. I would be greatly thankful to the authors if they could help me gain insights into this aspect of their results.**

We thank the reviewer for appreciating our contributions. We present the accuracy result in Theorem 3. In the upper bound of Thm.3 there are two terms. The first one is $\tilde{O}(\frac{\alpha^2  n k}{\epsilon^2})$ (we assume the radius $r$ as a constant), where $\alpha$ is defined in Definition 6 is $1-\alpha$. Note that if all agents' cost is less than the threshold, then this term becomes zero. Moreover, as $1-\alpha$ means our participation goal, by choosing the parameter $\alpha$ sufficiently small (as suggested in Corollary 8), it will be dominated by the second term. 

The second term is $\tilde{O}(\frac{k}{n\epsilon^2})$, which is the cost due to privacy and statistical error. It is notable that even in the standard (non-private) high dimensional sparse linear model, the optimal estimation error is $\tilde{O}(\frac{k}{n})$, which only depends on $\log d$ and the sparsity. As we consider the high dimensional case where $n\ll d$, this bound will be $o(1)$. Thus, our second term is also very small and comparable to the non-private case.