Truthful High Dimensional Sparse Linear Regression
Authors: Liyang Zhu
Amina Manseur
Meng Ding
Jinyan Liu
Jinhui Xu
Di Wang
Venue: NeurIPS 2024 poster (2024)
Keywords: truthful mechanism
Bayesian game
linear regression
differential privacy
Primary area: privacy
TL;DR: We design a truthful (and privacy-preserving) mechanism for high dimensional sparse linear regression.

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.

Truthful High Dimensional Sparse Linear Regression
Liyang Zhu', Amina Amina Manseur' Meng Ding", Jinyan Liu Jinhui Xu² Di Wang'
'PRADA Lab, King Abdullah University of Science and Technology
State University of New York at Buffalo 'Bejjing Institute of Technology
{liyang-o . zhu, amina.manseul di. di.wang) wang) www.as.eeu.uu.s.......... sa {mengding, jinhu)@buffalo. edu jyliubbit.edus .du..n. cn
Abstract
We study the problem of fitting the high dimensional sparse linear regression model with sub-Gaussian covariates and responses, 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 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 novel private estimator that has closed-form expression. Based on the estimator, propose mechanism which has the following properties via some appropriate design of the computation and payment scheme: (I) the mechanism is (o(1), (n (R())) (R))))))oin j-joonntly differentially private, where n is the number of agents; (2) it is of ()) approximate Bayes Nash equilibrium for a (1 o(1) -fracciio of agents to truthfully report their data; (3) the output could achieve an error o(1) to the underlying parameter; (4) it is individually rational for a (1 o(1) fraction agents in the mechanism; (5) the payment budget required from the analyst
run the mechanism is o( (1). To the best of our knowledge, this is the first study on designing truthful (and privacy-press privacy-preserving) mechanisms for high dimensional sparse linear regression.
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 soureed from strategic, privacy- concereed individuals. In this case, data providers (agents [ may be disinclined 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 preserving data anal- ysis. 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- privacy-preserving preserving computations to accurately learn the underlying model. As agents cannot refine their reports after seeing their payment, the interaction is designed be completed in one round, creating trade-off between estimator accuracy and the total payment budget needed for participant cooperation.
In this paper, individuals, data providers, and participants the same and all represent agents.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In recent years, there has been a line of work studying truthful and such as 37 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 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 rrivacy-preserving machine learning 33
linear models
[2 53 49 28). to the best of our knowledge, there no previous study on truthfully and privately estimating high dimensional sparse linear models due to some intrinsic challenges of the problem (see Section Cin Appendix for details). Therefore, a natural question to ask is:
3
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 & and log d are far less than n can be considered as constants. Specifically, for the privacy- preserving data analysis part, we adopt the definition of Joint Differential Privacy (JDP) [3] 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 sp-spase covariance matrix with p [0. 1] as a by-product, which extends the previous results on the sp-sasse case. Based on our JDP estimator, via the peer prediction method, we then provide 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 ((n-(()))) J-DDP where is the number of agents. (2) The private estimator of the mechanism is o(1) (1)-acccuaate, i.e., when the number of agents increases, our private estimator will be sufficiently close the underlying parameter. (3) The mechanism is asymptotically truthful, i.e., it is an of -appproximme Bayes Nash equilibrium for (1 -frac-ftatio of agents truthfully report their data. (4) The mechanism is asymptotically individually rational, i.e., the utilities of (1 - -fr))-fraction of agents are non-negative. (5) The mechanism only requires (1) payment budget, i.e., when the number of participants increases, the total payment tends to zero
2 Preliminaries
Notations. Given a matrix X E Raxd, let xa be its i-th row and Tzz (or [X]s)) be its (1, entry (which is also the j-th element of the vector 2;)) For any p co], | is the p-norm,
[[Yyll> and || = max,, [mny is the max norm of matrix X. For an event A, we let [[A] denote the indicator, i.c.. /[4] 1 if A occurs, and [[A] 0 otherwise. The sign function of a real number x is a piece- wise function which is defined as sgn(z) = - O; sgn(x)
ie., || == supyyo ||>l
1 if x > O; and sgn(x) 0 if 0. We also use Amin (X) to denote the minimal eigenvalue of X. For a mab-Gaussian random variable X, its sub-Gaussiaa norm |X| is defined as
|| = inf > 0: Blexp(( x²) < 2) (see Appendix E for more preliminaries).
2.1 Problem Setting
We consider the problem of sparse linear regression in the high dimensional setting where d >> Suppose that we have a data universe D = X X'x ) C Rd x R and n agents in the population, where each agent i has a feature vector x; E X and response variable i E ) (we denote D; = (xt, y:) and D as the whole dataset). We assume that {<x,, };)} are i.i.d. sampled from a sparse linear regression model, i.e., each (Ii, 3;) realization of the sparse linear regression model y (0* xx) + Ç, where the distribution of x has mean zero, ( is some randomized noise that satisfies E(g|=] 0, and 8" E Rd is the underlying model estimator with sparsity assumption ||0* S 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 |10" 2|2 S 1. Moreover, for the covariance matrix x, E, there exist Rox. and K2 such that |Ew|l> xo 2 Koo ||w]| II oc, Vu # 0 and ||Σ #xlle> < Kig-
To make our results comparable to the previous results, assume Koo and Kx constants for simplicity.

---

These assumptions have been commonly adopted in some relevant studies such as [52] we present the assumptions made on the covariate vectors I; and response variable yi- Assumption 2. We assume that the covariates (feature vectors) 21, 22, In E ER' are i...d. (zero-
14 3
Next,
mean) uab-Gaussian random vectors with variance o with O(1). The responses yi are ii.d. (zero-mean) sub-Gaussian random variables with variance a² with (1).
In our setting. the agents are self-interested or strategic. They concerned about their privacy and can misreport their responses {ur 1= but not their features {2x This means the features are directly observable but the response (e.g., during physical examination) unverifiable. We denote D= {D: = (X,, 1/) 1= the reported dataset where S = (D,) is the reporting strategy adopted by agent i. Specifically, each agent is characterized by privacy cost coefficient c₁ E R.. Higher ca indicates the agent is concerned more about the privacy violation.
Apart from the agents, there is an analyst who seeks an accurate estimator 0 of 0" based on the reported data and needs to construct a payment rule и D + I that encourages the truthful participation, i.e., reveal their data truthfully to the agent. Misreporting the response y; will result in decrease in the payment received R;. The analyst will thus design a mechanism M takes the reported dataset ò = {D, = (X,, (0)= as imput and outputs an estimator @ of l and a set of non-negative payments { In 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.
2.2 Differential Privacy
Due to space limit, we postpone all the relevant definitions of DP the appendix, readers can refer to Section. [A.]] In our case, DP requires that all outputs, including the payments allocated to agents, are insensitive to each agent's s input. This requirement quite strict, as the payment to each agent not shared publicly with other agents. Therefore, instead of using the original DP, we consider relaxation known as joint differential privacy (JDP) (1
2.3 Utility of Agents
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 e; E RR+ 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 fs(c,, E, 5) which measures the cost she incurs when her response y: is used in an (e, oJoinnt Differential Private Mechanism. Considering the payment n; of agent and her privacy cost function fi(c,, 8), we denote by u4 क; fe(c,, E, 8). her utility function that represents the utility she gets when she reports her response y; truthfully to the analyst. Following the previous works, we assume that all functions f; are bounded by function of c; and s, increasing with c.
Assumption 3. The privacy cost function of each agent i satisfies fi(c,, e, 8) S ((( + 8)e3
Larger values of and 8 imply weaker privacy guarantees, which means the privacy cost of an agent becomes larger. Thus, it is natural to let Sa be bounded by a component-wist increasing function, which can be denoted by F(c;, e, Here F(c;, 5) (1(1 + d5ee. In [4), the authors consider the case where the response is bounded and 5 = 0, they assume f( 8) < c,e2, i.c., F(c,, e, 6) c However, since our Assumption 2 on the distribution of the response 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; for each individual does not reflect the privacy costs incurred by other individuals. Also, we allow 6 to be correlated with its corresponding data sample D, Therefore, we make the following assumption.
Assumption 4. Given D;, (D_i, c_i) is conditionally independent of for each i E [m]
pDD_,,c- = p(DDss.-.lDp
'In order to make our result comparable to previous work on linear regression with bounded covariates, we assume the variance proxy is d² /d so that with high probability ||æi||a is bounded by some constant.
3

---

where C-; 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 ci has exponential decay. This assumption is essential for providing bound on the threshold value Ta, of truthful reporting, which will be explained in the following section.
Assumption 5. There exists some constant cost coefficient satisfies inf Fop-p(e))).) (c: S r) 2 1 1- -e- Ar
such that the conditional distribution of the privacy
2.4 Truthful Mechanism Properties
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 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 multiagent, one-shot, simultaneous- 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.
symmetric Bayesian game, where the
3 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-fome 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.
3.1 Novel Efficient Private Estimator
As mentioned in Section D the one-round communication constraint necessitates 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 f2-norm does not encourage sparsity to the same extent the f--oomm Thus, all previous methods for truthful linear regression cannot be applied to our problem.
In the following, we derive a new estimator based on 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 (Exx)~1 exists with Exx = Ei= æ.C.. which will be removed in the course of our analysis. Intuitively, our goal is to find sparse estimator that is close to OL.S, s.t. |10||o < k. whose E convex relaxation of the lo constraint is
i.e. arg mine |00
arg min |10 E Exx 112 + 11111
with some An > O.
Although ① is very similar to LASSO, fortunately, the above minimizer is just the proximal operator on OLS: Proxx, (xxx Σxy), which has closed form expression. Since the proximal operator is separable with respect to both vectors, 0 and E εxv, we have (Prox I-Ila (Σx εxy)); =
sgn(( (xxxxxxxxxxxx (xxxxxxx)) max ( (((xxxxxx)))) (xv)) >n, 0}. And the optimal solution 0 satisfies:
θ = Sx, (xxxxxxXx
(2)
where for given thresholding parameter X, the element- soft-thresholding operator Sx : Rd +
Rd for any u E IR is defined as the following: the i-th element of (u) is defined as [Sx(u)]; =
sgn(u)) max [u:] Ax 0).
key insight is that this operation is equivalent to embedding the classical OLS estimator within the sparsity constraint. This secures morm consistency which does not hold for neither the ridge

---

regression nor the original OLS estimator. The ε 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 truthful linear regression 14 employed the output perturbation method, which adds some noise to the closed-form estimator. The noise should be calibrated by the fz-sensitivities of their non-private estimators to ensure DP, which depend on Volyvdd/n) This is unacceptable when d > n. Should we adopt the same strategy to analyze the sensitivity of Sx., xxx'x Exy), we inevitably encounter the estimation error of Σy1 This error will cause the noise to have an unavoidable dependency on Poly( V /d/n) [46. Given the previous discussion, we propose to inject Gaussian noise separately to Σxx and Exy. It notable that while similar methods have been used in DP statistical estimation [40] 48 it has not been used in truthful linear regression. This due to that in our problem, the data is misreported, which makes the utility analysis more difficult. We will discuss it in Section [.1
For the term Σxx, we apply f2-norm clipping so that the sensitivity of clipped version Exx is irrelevant to d. For the term Σxy, since the covariate and the response y/ are sub-Gaussian. Therefore, clipping operation becomes necessary. We shrink each coordinate of z; via parameters Tæx i.c., for j E [d] and ē, = sgn (I;) min {| JzJ. We also perform the element-wise clipping on the response Vi by Ty. Then the server aggregates these terms ,ęग! and R. and separately add Gaussian noises to Exx and Exy- The noisy version is denoted by Σxx and Exy-
We now give 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 [.
Assumption 6. We assume that Σ Gg(s) for some 0 S q 9 1, where Gg(s) {E (aaat sy) max; l0 , S s, Vj E [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 [6) To the best of our knowledge, the only work that considers the private sparse covariance matrix estimation is [5T. Unfortunately, [5T] only considers the case where q = 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 || - E) < O me ( which is quite large under the high dimensional setting. To see why Σxx will introduce large error under Assumption 6 we observe that some of its entries are quite large which makes | ig TzaT ,eنl large for some j, Thus, we need to develop a new private estimator for (approximately) sparse covariance matrices valuable by-product. By Lemma 24 and [1
in the Appendix, we can get the following, with high probability,
for all < i, S d, RRgT ,jj T ssl < Ō /lu ). However, under the sparsity assumption, there ne
will be two cases: (1) If G2rT, iij is small enough, then maybe the zero entry could have a smaller error than ōæzT iú since the noise is quite large. (2) If anxT .ú is large, then the original oz jús could be better. Motivated by the above observation, we perform a threhhodrrs operation on each Pa. 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 O. To be more specific, it filters out 0ggT .j 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 azz",ij correspond to large âzs" .3-- After the hard threshhreshoddig operation, we denote the resulting matrix by Σxx and it is invertible with high probability shown below.
5

---

Algorithm (e, 0)-DP Algorithm for Sparse Linear Regression
1: Input: Private data {(1,, 31)
(RR" x R)". Predefined parameters Tax Ty. An-
2: for each user i E [n] do
3: Clip i. 2; min (1, [| i.e. (r,)) Release उęØo to the server.
4: Clip ž = sgn (x.) min (10 Ta) and 0s = sgn (V: min (lusl,Ty): Release R.Ú; to the
server.
5: end for
6: The server aggregates Σxx = -E=EEtt and Egy - -
7: Add noise Exx = Σxx + Ni, where N1 E gdxd is a symmetric matrix and each entry of
the upper triangular matrix is sampled from (0, 32r 3 Add noise Exv = E Exy + N2,
where the vector N2 E R is sampled from (00, 32 n²2²
2 La).
8:
Apply hard-thresholding to E&x and obtain E&x where each entry defined as 0ss"
"i T[6 22" .5y > Thres], where Thres = ~V logd 1r2 2 25266////oog and is some constant.
ne
9: The server outputs (D(D) = SA^ ([xx11 -Exx).
Lemma 1.
The estimation error of private estimator
D satisfies with probability 1 d-1(1) that (
E113 -113 -0 (
log d 8
log dl log 3
E F1EXX
+
ng²
ng²
where the expectation takes over the randomness of the data records and the algorithm.
Remark 1.
When q 0 and O(1), Lemma could achieve error bound of O log d which matches the optimal rate of locally differentially private sparse covariance matrix estimation
50
Our private estimator is of the form (D) Sx,, x With some r, Tux and Ty. (D)).
upper bound of Ó Vt is achievable. See Algorithm I for details. Notably, step 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 and i of our problem. Moreover, since we assume ||0*]|2 S Ta. we can also project 0P (D) in Algorithm 1 onto f--norm ball: 8 (D) II, (@P(D)) where II (v) arg min, !/ - u112 and (( is the closed norm ball with radius Tg-
Vie
To sum up. high dimensionality gives rise to several consequences: (I) the regularization techniques used by 37 14] are not applicable, (2) the invertibility covariance matrix estimate is not guaranteed, (3) it also precludes the output perturbation method. Our proposed estimator properly overeomes the above challenges. To tackle (1) we embed the OLS estimator within the l constraint to exploit the sparsity, along with novel estimator of the covariance matrix mitigate (2), and privatize by sufficient perturbation to solve (3), which in turn makes our truthful analysis part much more complicated.
3.2 Payment Rule
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 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 player's 's payment. In principle, the higher payment means higher consistency between the agent's 's reported value ğ and the predicted value of y, estimated using the collective input from their peers D_,.
To quantitatively measure the similarity between each agent's report and their peer's reports, we will use the rescaled Brier score r1l Let and 02 be positive parameters to be specified. Consider that g represents the prediction 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 Di....,
2: Randomly partition agents into two groups, with respective data pairs D _id
3: For each dataset D, Do and DJ, compute private estimators 6" (D), (D() for = 0, according to Algorithm
4: Compute estimators 0º (D) 11 (D)) and 0 @D()) = 1L, (0 (D')) for b = 0,
5: Set parameters a1 022 and compute payments to each agent agent i's is in group 6, then
he will receive payment म. B Bay,a2 (5 0 (f))), (T,, R Bo-r(11,))
the following payment rule:
a (p.9) = a2(p 2pq + d²),
(3)
Observing that BB, az (p. q) is function that exhibits strict concavity with respect q, we point out that its maximum is attained when q equals p. This implies a congruence between the pre- diction of agent i's response based on her own information and that derived from her peers' in- formation. For agent i, given E(y, æ4, 0*] = (xt 8*), it is logical to p (z,, PP (D")) and q= = (2,, Ep-pt((b)) (0]). Here, 0" (D') denotes the private estimator for dataset D excluding D., and D.) represents the posterior distribution of 0 post the analyst's receipt of D.
Building upon this analysis, we structure our Algorithm 2 This algorithm utilizes reported data, which may contain manipulated responses, generate estimators. To maintain data independence, divide the dataset into two subsets, D and D', For the purpose of calculating the payment for each agent in group b (0, 1), the estimator #* is derived using D1-b, Finally, the algorithm applies 0º (D) in combination with the specific agent's feature vector x, to forecast their response.
4 Theoretical Results and Implementation 4.1 Accuracy and Privacy Analysis
Theorem (Privacy). The output of Algorithm satisfies (2e,30) 3JD
Remark By the selection of and 8, our mechanism could achieve an (o( 1 O(n I-DD
which provides asymptotically the same good privacy guarantee as in [1] for the low dimension setting with bounded covariates and responses. Specifically, [14] shows that it is possible to design an o( V JJPD 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 Sauusian/heavy-tailee ttilldd covariates and responses, our Theorem 2 is better than theirs. In detail, (37] can only guarantee Random Joint Differential Privacy (RJDP) where all but a small proportion of unlikely dataset pairs, pure 6-JDP holds, while 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 [I4), 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 method, we sufficient statistics perturbation, due to our clipping operator, the sensitivities of Σxx x and E Ex 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-hasel method, as we will discuss in the following.
Theorem 3 (Accuracy). Fix a privacy parameter e, a participation goal - a and a desired confidence parameter 3 in Definition 6 Then under the symmetrie threshold strategy O...s, when
n is sufficient large such that n 2 Q
log d dogg ), the output 0º (D) of Algorithm satisfies that
with probability at least 1 3 O(n 2()).
E110O( 0- <0((2n
kr log dl log
e2
Remark 3. The above bound is independent on (oly(d). This outcome primarily due to the use of sufficient statistics perturbation method, which effectively reduces the size of noise. It is notable that
7

---

Assumption 6 only ensures that when 2 $2 Thus, even if the assumption does not hold, we can still get the same upper bound as in Theorem 3 as long as 2 (d)).
our private covariance estimator is invertible.
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 [4] both used the output perturbation method, as it provides an explicit characteri- zation of the noise. Specifically, their estimator can be represented as 0 (D) = -I (0" (D)), where (D( = 0(D)+ + with (DD) as (non- private) closed- form estimator and v is the added Gamma noise of scale Olv O(vd/n) to the non-private estimator. It can be shown that:
B1100 ( - 0 ([2) S ElJōO (δ) - 0- 2 2 (D) - 0(D) 2BI - 0 11 - - + B|lo1 + BJJĀ(D) - 1
where is original data and Á 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 on with high probability, indicating there are at most an different samples between D and D. Thus, it can be bounded by directly re-using the sensitivity analysis of O(D) the privacy data analysis. However, as we mentioned previously, the sensitivity of (2) is of scale D(/d/n), indicating the previous method cannot be applied our setting. Hence our tactic is to privatize the terms Σx and Exy separately. We shall take another route to estimate the error of the private estimator 0² (D)::
part of
E[I(P(() 0" 1B: < E (D) - 0r
- O - 22 - 1-
The above framework is now estimating the difference in the private 8" (instead of the non-private 0).
However, this nuance inevitably leads to more complex analysis, i.e. the term E EI ()) (*)
is much more complicated to deal with than the first term in (4). The bound on ())P(()) 0 (D)
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 é norm term in ① give 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 (D) and 0" (D) be the private estimators on the original dataset D and the reported
dataset î) that at most one agent misreports. We set the constraint bound >n th=0 ( (12 Tog dl log
=O
//e
when n is sufficient large such that n 2 12( 2²p** log d log it ), with probability at least 1 - Old Odd-a(1)
we have the following error bounds:
|10º (D) - (D))lo 42m: - 516VkA,.
4.2 Analysis for the Properties of Truthful Mechanism
Theorem 5 (Truthfulness). Fix a privacy parameter E, a participation goal and a desired Then with probability at least - B ((n)())) nd 4, the symmetric threshold strategy Tr.,y an n-approximate Bayesian Nash equilibrium in Algorithm with
confidence parameter 3 in Definition 6
1 = - (or""oog
1 g
1(1
nnakk c
1
log d log
+
+
ng?
We can see with some specified parameters, the above bound could be sufficiently small. For example, when we set a = x we have 17 > as n + so since = o( (
Theorem 6 (Individual rationality). With probability at least 1 - 3 - On ((-))))))) nd 2, Algorithm
2 is individually rational for all agents with cost coefficients G; S Ta.3 as long as
01 2 az(rTo + (2) + 80, 1 +
3
regardless of the reports from agents with cost coefficients above Ta where a1, ag are in 6
8

---

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 well.
Theorem 7 (Budget). With probability least 1 1- 3 - ((-))))) -nd 2 the total expected budger B = Σx=1 B (T;)) required by the analyst to run Mechanism under threshold equilibrium strategy Ta satisfies
B H n(a1 + 02(rTo + r)))))
Remark 5. With some appropriate setting of a, 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 the ground-truth parameters can always recovered by our estimator, which allows the analyst to pay nothing incentivize the agents.
infinite,
4.3 Formal Statement of Main Result
Corollary 8. For any { E (3: 2) and e > 0, we set = n 8 O(n-u1)), a = O(n-3a = =a2(rT + 3g) + Ta, + 35)=3. Then the output of Algorithm 2 satissies (O(n-5) 50,00 ( Moreover, with probubility at least 1 - holds that:
3 = (nn a2 = O(n
1. The symmetric threshold strategy Tro.s is (on----)--aaysiiii Nash equilibrium for O(n-35 fraction of agents truthfully report their data;
2. The private estimator 8 is Õ(n (naastnt-))accaaaaa -accurate;
3. It is individually rational for O( fraction of agents to take part in the mechanism;
4. The total expected budget required by the analyst is O(n2-3E).
Remark 6. It is important to highlight the subtle balance between the precision of the estimator and the other attributes of the mechanism. Compromising accuracy often results in several consequences: (I) 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, do not observe such a trade-off in (37 's implementation for linear regression cases. Besides, our results slightly differ from that of [4] 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 the agents, resulting in different settings of parameters.
Conclusions
In this paper, we fit the high dimensional sparse linear regression privately and we propose truthful mechanism to incentivize the strategic users. On the one hand, the mechanism is (o(1), On (n--((()))))))))) -Q)))- 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-thresholdig, we propose private estimator l to exploit the sparsity of the model and it achieves an error of o(1). On the other hand, via some computation the agent's '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 mechanism reaches an o( (a)aaprroximmte Bayes Nash equilibrium for a (1 o(1)) 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)
the consistency between
of agents
to truthfully report their data while (1 o(1)) fraction of

---

Acknowledgments
Di Wang and Liyang Zhu were supported in part by the funding BAS/1/1689-01-00 URF/1/4663- 01-01, REI/1/5232-01-01, REI/1/5332001-011 and URF/1/5508-01-01 from KAUST, and funding from KAUST Center of Excellence for Generative AI, under award number 5940. Jinyan Liu is supported by the National Natural Science Foundation of China (NSFC Grant No. 62102026).
References
[1] Raef Bassily, Cristóbal Guzmán, and Michael Menart. Differentially private stochastic opti- mization: New results in convex and non-convex settings. Advances Neural Information Processing Systems, 34:9317-9322 2021.
[2] Raffael Bild, Klaus Kuhn, and Fabian Prasser. Safepub: A truthful data anonymization algorithm with strong privacy guarantees. Proc. Priv. Enhancing Technol., 2018()):67-87, 2018.
[3] T. Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49(5):285-22850, October 2021. Publisher: Institute of Mathematical Statistics.
[4] T. Tony Cai and Harrison H. Zhou. Optimal rates of convergence for sparse covariance matrix estimation. The Annals of Statistics, 40(5), October 2012.
[math, stat].
[5] Tony Cai and Weidong Liu. Adaptive thresholding for sparse covariance matrix estimation. Journal of the American Statistical Association, 106(494);672-684, 2011.
[6] Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou. Optimum statistical estimation with strategic data sources. Conference on Learning Theory, pages 280-296. PMLR, 2015.
[7] Robert J Casson and Lachlan DM Farmer. Understanding and checking the assumptions of linear regression: primer for medical researchers. Clinical & experimental ophthalmology. 42(6))590-596 2014.
[8] Kamalika Chaudhuri. Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
[9] Junren Chen, Cheng-Long Wang, Michael K Ng, and Di Wang. High dimensional statistical estimation under uniformly dithered one-bit quantization. IEEE Transactions on Information Theory, 2023.
[10] Yiling Chen, Stephen Chong, Ian A Kash, Tal Moran, and Salil Vadhan. Truthful mechanisms for agents that value privacy. ACM Transactions on Economics and Computation (TEAC), 4(3):1-30, 2016.
[11] Yiling Chen, Chara Podimata, Ariel D Procaccia, and Nisarg Shah. Strategyproof lincar regression in high dimensions. In Proceedings of the 2018 ACM Conference Economics and Computation, pages 9-26, 2018.
[12) Yiling Chen, Yiheng Shen, and Shuran Zheng. Truthful data acquisition via peer prediction. Advances Neural Information Processing Systems, 13:18194-18204 2020.
[13] Rachel Cummings, Hadi Elzayn, Emmanouil Pountourakis, Vasilis Gkatzelis, and Juba Ziani. Optimal data acquisition with privacy-aware agents. In 2023 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML), pages 210-224. IEEE, 2023.
[14] Rachel Cummings, Stratis Ioannidis, and Katrina Ligett. Truthful linear regression. In Confer- ence on Learning Theory, pages 483. PMLR, 2015.
[15] Rachel Cummings, Katrina Ligett, Aaron Roth, Zhiwei Steven Wu, and Juba Ziani. Accuracy for sale: Aggregating data with variance constraint. In Proceedings of the 2015 conference on innovations in theoretical computer science, pages 317-324, 2015.
10

---

[16] Ofer Dekel, Felix Fischer, and Ariel D Procaccia. Incentive compatible regression learning. Journal of Computer and System Sciences, 76(8):759-777, 2010.
[17] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[18] Alireza Fallah, Ali Makhdoumi, Azarakbsh Malekian, and Asuman Ozdaglar. Optimal and differentially private data acquisition: Central and local mechanisms. arXiv preprint arXiv:2201.00 003668, 2022.
[19] Alireza Fallah, Ali Makhdoumi, Asuman Ozdaglar, et al. Bridging central and local differential privacy in data acquisition mechanisms. Advances in Neural Information Processing Systems, 35:21628-2166 21639, 2022.
[20] Lisa K. Fleischer and Yu-Han Lyu. Approximately optimal auctions for selling privacy when costs are correlated with data. In Proceedings of the 13th ACM conference electronic commerce, pages 568-585, 2012.
[21] Arpita Ghosh, Katrina Ligett, Aaron Roth, and Grant Schoenebeck. Buying private data without verification. Proceedings of the fifteenth ACM conference on Economics and computation, pages 931-948, 2014.
[22] Arpita Ghosh and Aaron Roth. Selling privacy at auction. In Proceedings of the 12th ACM conference Electronic commerce, pages 199-208. 2011.
[23] Katherine Godfrey. Simple linear regression in medical research. New England Journal of Medicine, 313(26):1629-1636 1985.
[24] Trevor Hastie, Robert Tibshirani, and Martin Wainwright. Statistical learning with sparsity: the lasso and generalizations. CRC press, 2015.
[25] Thibaut Horel, Stratis loannidis, and S Muthukrishnan. Budget feasible mechanisms for experimental design. In Latin American Symposium Theoretical Informatics, pages 719-730. Springer, 2014.
[26] Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu. Private matchings and allocations. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 21-30, 2014.
[27] Lijie Hu, Ivan Habernal, Lei Shen, and Di Wang. Differentially private natural language models: Recent advances and future directions. In Findings of the Association for Computational Linguistics: EACL 2024, pages 478-499, 499, 2024.
[28] Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data. In Proceedings of the 41 ACM SIGMOD. SIGACT-SIGAI Symposium on Principles of Database Systems, pages 227-236. 2022.
[29] Stratis Ioannidis and Patrick Loiseau. Linear regression as cooperateee game. In Web and Internet Economics: 9th International Conference, WINE 2013. Cambridge, MA, USA, December 11-14, 2013, Proceedings 9, pages 277-290. Springer, 2013.
[30] Prateek Jain, Ambuj Tewari, and Purushottam Kar. On iterative hard thresholding methods for high-dimensional m-estimation. Advances in neural information processing systems, 27, 2014.
[31] Michael Kearns, Mallesh Pai, Aaron Roth, and Jonathan Ullman. Mechanism design in large games: Incentives and privacy. In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 403-410, 2014.
[32] Katrina Ligett and Aaron Roth. Take it or leave it: Running a survey when privacy comes at cost. In International workshop on internet and network economics, pages 378-391. Springer, 2012.
11

---

[33] Frank D McSherry. Privacy integrated queries: an extensible platform for privacy preseevvig data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Manage- ment of data, pages 19-30, 2009.
[34] Kobbi Nissim, Claudio Orlandi, and Rann Smorodinsky. Privacy-aware mechanism design. In Proceedings of the 13th ACM conference on electronic commerce, pages 774-789, 2012.
[35] Javier Perote Peña and Juan Perote Peña. Strategy-proof estimators for simple regression. Documento de trabajo, page 14, 2003.
[36] Dudley L Poston. Dudley L Poston Jr, Eugenia Conde, and Layton M Field. Applied Regression Models in the Social Sciences. Cambridge University Press, 2023.
[37] Yuan Qiu, Jinyan Liu, and Di Wang. Truthful Generalized Linear Models, September 2022. arXiv:2209.07815 [cs].
[38] Yuan Qiu, Jinyan Liu, and Di Wang. Truthful and privacy-presenvee generalized linear models. Information and Computation, 301:105225, 2024.
[39] Garvesh Raskutti, Martin J Wainwright, and Bin Yu. Minimax rates of estimation for high-dimensional linear regression over f,-balls. IEEE transactions information theory, 57(10):6976-6994 2011.
[40] Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is Interaction Necessary for Distributed Private Learning? In 2017 IEEE Symposium on Security and Privacy (SP). pages 58-77, San Jose, CA, USA, May 2017. IEEE.
[41] Shuang Song, Thomas Steinke, Om Thakkar, and Abhradeep Thakurta. Evading the curse of dimensionality in unconstrained private glms. In International Conference on Artificial Intelligence and Statistics, pages (636-2646. PMLR, 2021.
[42] Gilbert W Stewart and Ji-guang Sun. Matrix perturbation theory. Academic press, 1990.
[43] Jinyan Su, Lijie Hu, and Di Wang. Faster rates of differentially private stochastic convex optimization. Journal of Machine Learning Research, 25(1 15(114):144) 2024.
[44] Jinyan Su, Changhong Zhao, and Di Wang. Differentially private stochastic convex optimization in (uclldeull space revisited. In Uncertainty in Artificial Intelligence, pages 2026-2035 PMLR, 2023.
[45] Youming Tao, Yulian Wu, Xiuzhen Cheng, and Di Wang 0015. Private stochastic convex optimization and sparse learning with heavy-tailed data revisited. In ICCAI, pages 3947-3953, 2022.
[46] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv: 1011.300 2010.
[47] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, November 2011. arXiv:1011.300 [cs, math].
[48] Di Wang, Lijie Hu, Huanyu Zhang, Marco Gaboardi, and Jinhui Xu. Generalized linear models in non-interactive local differential privacy with public data. Journal of Machine Learning Research, (4(132):1-57, 2023.
[49] Di Wang and Jinhui Xu. On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning. pages
PMLR, 2019.
[50] Di Wang and Jinhui Xu. Tight lower bound of sparse covariance matrix estimation in the local differential privacy model. Theoretical computer science, 815:47-59, 2020.
[51] Di Wang and Jinhui Xu. Differentially private high dimensional sparse covariance matrix estimation. Theoretical Computer Science, 865:1 19-1 2021.
[52] Di Wang and Jinhui Xu. On Sparse Linear Regression in the Local Differential Privacy Model. IEEE Transactions on Information Theory, 1822)))1112220000 February 2021.
12

---

[53] Di Wang and Jinhui Xu. Differentially private 1o-mor linear regression with heavy-tailed data. In 2022 IEEE International Symposium on Information Theory (ISIT), pages 1856-1861. IEEE,
2022.
[54] Di Wang and Jinhui Xu. Gradient complexity and non-stationary views of differentially private empirical risk minimization. Theoretical Computer Science, 982:114233 2024.
[55] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017.
[56] Peter Whittle. Bounds for the moments of linear and quadratic forms in independent variables. Theory of Probability & Its Applications, 5(3):322-305, 1960.
[57] David Xiao. Is privacy compatible with truthfulness? In Proceedings of the 4th conference on Innovations Theoretical Computer Science, pages 67-86, 2013.
[58] Hanshen Xiao, Zihang Xiang, Di Wang, and Srinivas Devadas. A theory to instruct differentially- private learning via clipping bias reduction. In 2023 IEEE Symposium on Security and Privacy (SP), pages 2170-2189. IEEE, 2023.
[59] Eunho Yang, Aurelie Lozano, and Pradeep Ravikumar. Elementary estimators for high- dimensional linear regression. In International Conference on Machine Learning, pages 388-396. PMLR, 2014.
[60] Eunho Yang, Aurélie C Lozano, and Pradeep K Ravikumar. Closed-form estimators for high- dimensional generalized linear models. Advances in Neural Information Processing Systems, 28, 2015.
[61] Liyang Zhu, Meng Ding, Vaneet Aggarwal, Jinhui Xu, and Di Wang. Improved analysis of sparse linear regression in local differential privacy model. arXiv preprint arXiv:3310007367, 2023.
13

---

A
Notations and Omitted Relevant Definitions
Notation
Description
π2
The number of agents
d
The dimensionality
3j E X C R
The feature vector of agent i
y/ E y C R
The response variable of agent i
Σxx or Σ
The covariance matrix of T;
XX] p
p-norm of matrix X
1 [AA]
Indicator of event A
sgn (I)
Sign function of a real number æ
[Sx(u),
Element- wiiee soft-thresholding operator
N1 E Rddd
Gaussian noise added to Σxx
N₂ E R
Gaussian noise added to Exy
7
Some constant associated with the variance of N₂
Vi
shrunken version of y: via parameter Ty
Exx(Exx)
The sample covariance between X and X (The sample covariance be- tween the clipped X and the clipped Y)
Σxx (Exp))
noisy and (clipped) version of Σ xxx ( (xy)) The privacy cost coefficient of agent i
GEC C R+
D=Xx] X
The feature-response data universe
D. (1)
The feature-response data pair of agent i
0,(.s.): : D x C
C++ y
The reporting strategy of agent
Vi = 0, (1)
The reported response of agent
D. = (Zi, Ui)
The reported feature-response data pair of agent
D == Dijk
All feature-response data pairs
D Di
All reported feature-response data pairs
a = 07 )
The collection of all agents' reporting strategies
D_ D,D;
The collection of data pairs except D)
D_ DVD;
The collection of reported data pairs except D;
0-1 0.0.
The collection of strategies except Ø;
c_1 = (=) 14
The collection of privacy cost coefficients except
T
The payment to agent
44
The utility of agent
e, d E IR+
The privacy parameters of the mechanism
0' Rd
The model parameter needs to estimate
0,
The threshold strategy with privacy cost threshold 7 E R,
To.8
The privacy cost threshold characterized by a, B E (0, 1)
B
The expected total budget
((D)
The non-private estimator on data D
j (P(D)
The private estimator on the reported data 1)
(D)
The private estimator on the reported data D after projection
N2, Roo
The lower bounds for the operator norm and infinity norm of matrix Σ respectively
1)
The level of truthfulness
E 2
The parameter to control the trade-off between accuracy and truthfulness, payment amount and individual rationality.
A.1 Definitions of Differential Privacy
Definition (Differential Privacy [77). Given a data universe X, we say that two datasets D D' S X are neighbors if they differ by only one entry, which is denoted as D ~ D'. A randomized algorithm A is (e, diiffeerrntti private (DP) if for all neighboring datasets D, D' and for all events S in the output space of A. we have ((A()) E S) < e ((AA')) E 5.
14

---

Definition 2. (Gaussian Mechanism). Given any function q: x - R", the Gaussian Mechanism is
defined as: MM(D, q. = q(D) + +Y where is frow Gaussian Distribution N (0.
with a 2 /
Here D2(g) is the e of the function q, i.e. A2 =
supp-n [lg q (D') ll2. Gaussian Mechanism preserves (E. -diffferent privacy.
Definition 3 (Joint Differential Privacy (1). Consider randomized mechanism M D 1x11
with arbitrary response sets 6, I1"." For each E [nl, we denote by M - (0, E θ x 11n-1 the portion of the mechunism's oulput that is observable by external observers and agents + i. a mechanism M preserves (e. 8)- joint differential privacy (JDP), at privacy level ε > and
confidence level ó E (0, (0,1), 1), for every agent every dataset D E DD and every D,, D2 E D
have VS _ 9 x II
P F(M(D,, E SI(D,,,-i)) e (MM,,, D-i)-s SI(D,, D-.)) +
where D_s E DDn-1 the dataset D that excludes the i-th sample in D and n-द is the vector that contains all payments except the payment of agent i.
An (c, -JDI 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 magnitude of o( Definition assumes that the private estimator produced by the mechanism M is publicly observable, and that the payments can only be seen by agent Thus, from the perspective of each agent i, the released public output (0, T-)) may compromise their privacy.
A.2 Truthful mechanism properties
Consider M the regression mechanism that takes input the reported data D {D: ()))
from n agents, with ÿ (D))) the reporting strategy adopted by agent i. We denote the set of all agents' strategies by the strategy profile denotes the set of strategies excluding the reporting strategy of agent i. Let fi(c,, E, 8) be the privacy cost function of agent with e; her cost parameter. Each agent i receives real-valued payment T,; and finally receives utility = मH - e,(c,,,,)) Based on these settings, we quantify property (I) by introducing Bayesian Nash equilibrium.
(0.,.., nn) and a-t (01,..., 11 0+1,....
Definition& 4 (ny-Baysiaan Nash Equilibrium). A strategy profile (01, on) forms an 11- Bayyssian Nash Equilibrium if for every agent i, D, and eú and for every reporting strategy of # a one have
lu, (D) ob (u
77.
The positive value 1 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 17 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 r, this unified strategy profile will effectively realize an 17- Bayesian Nash equilibrium. Definition 5 (Threshold Strategy). The threshold strategy is defined as follows:
h - ( cs) = yk. if C3 S T, arbitrary value in V, if TT.
Definition (Threshold Ta. Fix a probability density function p(c) of privacy cost parameter, and let
0. inf(r r > 0: Pla
(aa...)pp -ap (# () a)n) 2 1-B3),
-- = =inf(r > : inf P
PepppteiD. <) 2 11 a-)
D.
Define Ta.3 the larger of these two thresholds: Ta. max a. =2)
The is threshold that with probability at least B, least 1 - fraction of agents have cost coefficient e S To.8. 72 a threshold that conditioned on their own dataset D,, each agent i believes that with probability - any other agent j has cost coefficient ej S Ta
15

---

We introduce the definition of nyaccuracy and we use the 2n-norm distance between the private estimator and the true parameter.
Definition 7 (17-accurccy). A mechanism is ry-accurate if its output OP satisfies E. [1]0P 0 S
Definition (Individual Rationality). A mechanism is individually rational if the utility received by
each agent i has non-negative expectation: Vi E [n]. Elu.] 2 0
To satisfy individual rationality, the mechanism should output payments high enough compensate
for privacy costs. Meanwhile, we also expect a total payment budget B = = TE [ = o(1) 1) that
tends to zero as the number of agents n increases.
Definition 9 (Asymptotically Small Budget). An asymptotically small budget is such that B Σ [[ - o for all realizable dataset D {1 W:)3
To sum up, we have n agents reporting potentially manipulated data, denoted as δ (zi, yc), 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 implemented under the assumption that the agents will adhere to threshold strategy.
B Related Work
Following the pioneering work of (22), substantial body of research has explored data acquisition
problems involving agents with privacy concerns [20, 32, [ [5] 21 18 [3]. 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 (2 34 10 explores cost models based the notion of differential privacy [7]. However, most of the aforementioned work only considers the mean estimation problem and does not consider Thus, these methods cannot be applied to linear models. [4] 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.
advanced statistical models [88 19 13
Classical approaches including the work by 155 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 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 has the potential to extend to other related scenarios. Recently, [61] proposed closed-form private estimator for sparse linear regression. However, as we discussed in Section 3.T] their estimator cannot be directly applied to our problem due to inherent limitations, such as challenges associated with the invertibility of the covariance matrix.
27 43
45
54 for
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 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 measure of estimation accuracy. [1]] studied the case where agents may intentionally introduce errors to maximize their own benefits and proposed several group-strategypen
linear regression mechanisms. Additionally, [16] and [35] considered an analyst who aims to derive "consensus" model from data provided by multiple strategic agents. this setting, agents seek a consensus value that minimizes their individual data loss, and the authors demonstrated that empirical risk minimization is group- strategyproof. However, all of these methods only consider the low dimensional setting and cannot be applied to the high dimensional sparse linear regression.
16

---

C Challenges in Designing Truthful and Privacy-preserving Sparse Linear Regression
In this section, we provide retrospect of previous methods and then outline the explain why existing methods are 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 the general Ridge regression estimator, i.e., solving the regularized convex program: arg ming 2n. |
x + + where y is some parameter and X = x= ,T,h² E R and Y = (11,,.. ... )T=T= E R". The unique closed-fon solution can be written as (D(D) (<l + x""X
371 considered the classical ordinary least square (OLS) estimator gOLS (Exx)- Exx where Σxx= A/4 Em= zạ and Σxy = Σ 24y/:- Both of the private estimators are based on the closed-form solution (D) of the ridge regression. However, there are four problems with the above methods, @ and ØOLS.
C.1 Sparsity-encouraging and Private Regressor
The -nrm accuracy emrors of @th and goLs are both bounded by O(vd/n). This rate is not convergent in the data-poor scenario, indicating that both of these two estimators are not suitable technique, we shall
our setting. Since l fg-reullarization used in 0 is not seek some alternative regularization. A qualified estimator that satisfies our need must (1) exploit the sparsity assumption and (2) have a closed- formmm--ommmmoo solution.
Apart from the choice of (non-po (oon-privtte) estimator, we also need to give some thoughts on the privacy mechanism. Previous work [14 and (37] both adopt the output perturbation method ensure e-JDP, i.e., adding some Gamma noise to 0ft or (OLS. According to the DP theory, the scale of the noise should be proportional to the fo-n sensitivity, which can be readily bounded by vd/n through clipping operation 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, n,, causing the estimation error much larger. This means we must find a privatization mechanism that gives better accuracy guarantee.
C.2 The Invertibility of Covariance Matrix
The invertibility of the covariance matrix is also an issue in high dimensional space. The classical OLS estimator jOLS used 377 is no longer well-defined as Exx is not full-rank. In case of @R. = (oT + +xXx) xxx)-1x7X xTy, although (el + xTX always exists for some > 0, the caveat with such method is however its concentration only holds when 2(d)) [46).
To solve the invertibility issue posed by high dimensionality, we need to consider properly impos- ing 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.
C.3 Truthfulness Analysis Framework
Due to the additional regularization parameter o. H is biased estimator of 6*, which complicates the truthfulness analysis. This complexity arises because the OLS linear regression estimator g = (xTx)-²xx -T y maximizes the scoring rule when players truthfully report their responses. However, for (D( the bias caused by @ causes the optimal report of each player to deviate from truthful reporting by quantity proportional to the bias. To address the above issue, [14] shows that as long as grows slowly than n, the bias term of ê'. converges zero with high probability. More specif- ically, it is shown that the estimation error can be decomposed into the summation of bias and a vari-
ance term: 1i| E(](0(D) -
0z 0=132- trace (ov (θO(()))) + bias (oa) I2, where trace(Cov(0())))
a² (wl (x x (el + x)) bias(ō(D)) = - + XT x)) 0*, o² is the vari- ance of the noise variables Ç. However, remains uncertain whether there a closed-form bias- variance decomposition available for our estimator proposed in Section 3.]
17

---

D Limitation
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 [[4] 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.
Although truthful mechanism studies 12
E
Supporting lemmas
Definition 10 (Sub-Gaussian random variable). A zero-mean random variable X E R. is said to be sub-Gaussian with variance o² (X subG (o²)) its moment generating function satisfies Elexp(tX)] S exp o2te) for all > For nau-Gaussian random variable X, its sub-Gaussian
norm || is defined as || inf > 0: R[exp( x+ s 2}. Specifically, if X ~ subG(oo) we have [| S (a)).
Definition 11 -Sub-Gaussian random vector). zero mean random vector R is said to be sub-Gaussica with variance σ² (for simplicity, we call it P-suu-Gaussian which is denoted as (X subGa (a²)). (X,u) u) sub-Gaussian with variance o² for any unit vector Rdd.
Lemma 9. For a sub-Gaussian vector X sub Ga (o²), with probability at least 8' we have
|| S 40 dllog 7.
Lemma 10 (147)) Let X2,...... Xy, be n (zero mean) random variables such that each X; is
sub- Gaussian with o². Then the following holds
P max X; 2 < ne 202
12 20 X 2 t
IP
max
< 2ne
Below is lemma related to the Gaussian random variable. We will employ it to bound the noise added by the Gaussian mechanism.
Lemma 11. Let (I n random variables sampled from Gaussian distribution N (0, o²). Then
E
max ISi5n
S Lov22 log 2n,
|1a| |n/12 +))
P
max
2nc 20
Isisnn
12
Particularly, in = 1, we have IP (f]2;|
+)) < 2e
207
Lemma 12 (Hoeffding's inequality). Let X1, ... Xn, be independent random variables bounded by the interval [a, b). Then, for any 0.
IP Σ
Σ
>1) ) 2exp (- (b-a)²
2nt?
(b - a)2
Lemma 13 (Bernstein's 's inequality for bounded random variables). Let X1, X2,... Xn be indepen- dent centered bounded random variables, i.e. [Xal < M and IE [X,] = 0, with variance E [x?] = =². Then, for any t 0,
IP Σ
X;
22 +
2M
< 2c
3
Lemma 14 (Bound on threshold Ta,g). Under the Assumption
Ta.9 S $ log 1
aB.
Lemma 15. For any w, w' dgd and closed convex set Rd we have [[TT(())) Ie( )| w|l w'll2, where Il is the projection operation onto the set C, i.e., Ilc(v) arg minnec ||u v112.
18

---

E.1
Lemmas for privacy guarantee
Lemma 16 Pros--prceessigg, Let M X" y an E-differential private mechanism. Consider : y + Z as arbitrary randomized mapping. Then the mechanism F M is E-differential private.
Lemma 17 (Billboard lemma (26)). Let M: D - O be an (c, 8)-differential private mechanism. Consider a set of f functions n. D + for i E [n]. Then the mechanism M' D + R that computes agent i's data, is (e, 6)-join differential private.
M(D) and oulputs M'(D) = (T, m rDi, Tn Tn (Dn;r)). where D; is the
Theorem 18 (Parallel Composition Theorem). Let 01, Oz.... O2 be n. independent operations that satisfy (E,, 6-DP for each E [k)] then the parallel composition of these operations guarantee (E1 + E2 + Ek. -D.
Theorem 19 (Sequential Composition Theorem( Theorem in (33 1f O2..... O₁ are sequential operations that satisfy e-individual differential privacy with failure probability of 8. then the sequential composition of these operations guarantees (ε) + +..++..e Ek, k- k- D--idiiiduall differential privacy, where & represents the of operation O, and is the total number of operations performed.
E.2 Technical lemmas for upper bounding the accuracy
Let DDD) and O(D") be the estimators two fixed datasets D, D' that differ most k entries and let D denote the fixed dataset that differs from D at most one entries. Suppose that with probability least 1 - Yia - if (IŌ(D) O(D)ll2 An then we have with probability at least
Lemma 20.
1 - giv. it holds that
(Ø( (D) - O(D')ll S gdn.
Lemma 21 (Theorem 2 in (59). Suppose solve the problem of the form mine 110 1100013 011 +mA1110111
such that constraint term An is set as An 2 -10 0(D) Then, the optimal solution Ô Sx., (0) satisfies:
((D) 0r)
$ 2dns
((D) 8r)
I <4VkAn
(OCD) 0"
S Sk.nn
Lemma 22. Under Assumption and we set
O Bayllogn 3,
n),r =
@(ovloogn) n), An - 1² Vlo d log Vne
when n is sufficient large such that 2 22 22 log dlog
cxM
with probability at least 1 O(d one has
(QP(D) - -0-1, S VRA
Lemma 23. (Weyl's Inequality (42) Let X,Y E Rdxd be two symmetric matrices, and E X Y. Then, for all = 1,-.- ,d, we have
(A(() Xx( < [E]|,
where we take some liberties with the notation and use XMM) to denote the i-th eigenvalue of the matrix M.
E.3 Technical lemmas for covariance matrix estimation
Lemma 24 (4), If (2, ,En, are n realizations of a (zero mean) o2-sub-Gaussie Gaussian random
vector X with covariance matrix Exx = E(XXT), and E. = (δzær (asr),))) ISijsa 1 Σ न.क. the empirical covariance matrix, then there exist constants C1 and 7 such that for any i, E [d], we have:
(|SS88 - Exx
00,00 >t) s Cie -nt
19

---

for all [8] S o with some o, where C₁ and y are constants and depend only on o². Specifically,
1|$88 Exx
log C2d
V n
00,00
Lemma 25. For every fixed S i,j d. there exists constant C₁ 0 such that with probability at
least 1 - Cid 2, the following holds:
Ö - -ianT.il
S 4min |o ssl . log d
4r 4/ 2n 2525/ /log
(5)
F Proofs of Supporting Lemmas
Proof of Lemmall 15
Denote b = [T(ww) and D = [Tc Since and D' are in C, so the segment
bV is contained C, thus we have for all E [0. 1]. |(1 t)b + th w|l2 2 ||b w//2.. Thus
d [1b
0
(1 1)b' - w - 2( b. w)
dt
Similarly. we have (b - 8 V w') 1 0. Now consider the function D(t) [1(1 - t)b + tw (1
-) 123 |6 // t(w w/ +B' b) which is a quadratic function in f. And by the previous
two inequalities we have (0) = (b D1, w/ + b) 2 0. Thus (--) is increasing function on [0, 2), thus (11) 2 ((0) which means || - w 2|2 2 11112-
Proof of Lemma 14 We first bound -2.g. -2, Since = # q S S + #li : > J). the event
{ G I } 2 (1 a)n} is equivalent to the event { (i c > 7 S am). Thus, by the
definition of a.,
a. inf > 0: (e
#(i: 7) < om) 2 1 3} #li: T} > am) S 3)
= inf > 0: IP te sa
By Markov's inequality, we have
E Merrrr.cc.lpp
Pl .or....ppppp (# (i: G > r] > an) S
an
Σ E Bawn! [G)7]
nP(cc > 7|
P Ple: >T]
Thus, {T > 0: P(c, > T) S a8) C (T 0: IP (e).... en yop" (# (i: > r} > am) S B}, which implies T2. < in > 0: P(c > 7) S a.3). The Assumption
5 implies that P(c: 7) < -Ar,
Hence, Ta,g S x
1 log as By the definition of +? and Assumption we have 7. < In a' Since
B E (0, 1), log aB X log 1 then Ta.8 max max (T -2) < X log a3
Proof of Lemma 4 For the ease of presentation, we denote the initial parameter x ) which the soft soft-thresholding Sx, is performed by 0. Let A be the error vector @P)(D) 0P (D). It follows that
zy on
1000-000000----00000000000000000 - - (D || - + O(D))> +|(()))=+++(()))) 0" (x)
(6)
where we utilize the fact that 0 (D) is feasible.
Using the property of generalized thresholding operator, we can bound the first term of equation 6
as 0 (D) - -(())l>> - An. For the third term of equation 6 from Lemma 22 we know that ( @ (D) An-
20

---

Our next task it to show X is indeed greater than the second term of equation 6 [1@(D) - llc) can be expressed as
[] l = =1xxxx(()) Exx - (Exx(D)) " Exx(D)]ls
Applying the inequality | ||AB AB' + AB' A' S || B'll ||A A (l)) we have,
|| { Exp(D) - - (Exx(D) {x)(
ا|| (5xx(D) 1001/200 - -xxx (D)ll
+|| (Exx(D)) - " -(Exx(D)) -1 a (xx
(7)
7 we see from Lemma 1 that when n 2 2
(fr
log dl log c
For the first term of equation
($xx)
And by equation 15 we have with probability 1 2d that
1 (D) - (D)(1)
=10x0 (D) - N2(D) + N2(D) - 5xx
+ 11N2( + ID2
-
1 mmax(1==;122(111) + ( +
8 2 log log d
en
8rTy / 2 log 1/ log d
2rTy +
En
rTy log 1 log d
00
S An
en
7 note that for any two nonsingular square matrices A, B with the same size, it holds that A B-1 -B B--(A--- (A-B)A- Thus, by Lemma |
For the second term of equation
we have
(Exx(D)) -1 - -(xx(D)) 1bx0
<|| (D) -1 ||ol| - ($xx (D)) looll (Exx(D)) - (Exx(D)) 1oo
(1ixx()) 21/00 + ||ixxx (D) - )11x))
< 22
s72 vi2vloo log d (
Se2
< Am
x26 e/n
Combining above, we have
110 (D) -0 (D) 10
rTvy log & log d
sT2
log d log(t))
<2h +0
0
en
<4hm
(8)
21

---

To further our analysis, we introduce the notion of decomposibility of norm and subspace compatibility constant. We call [M,MM subspace pairs where M the model subspace which the estimated model parameter 0* 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. regularization function R. is said be decomposable with respect to a subspace pair (M, ) (fR(u+ = R(u) + R(v), for all u E M.
Note that when R(.) is norm, by the triangle inequality, the LHS is always less than equal the RHS, so that the equality indicates the largest possible value for the LHS. For notational simplicity, we use (S, 5T) instead of an arbitrary subspace pair (M,M*)
Definition 13. The subspace compatibility constant is defined as M : (MM II) =
R(u)
SUP Tall
is noted that subspace compatibility constant that captures the relationship between the regular- ization function RR() and the error norm || |l, over vectors in subspace. In our proof, it is clear that the regularization the fornrm, which is decomposable with respect to the subspace pair. We also denote the subspace of vectors in I by S. Since we assume k is the sparsity level of 0", the cardinality of the support set of the model space where the true parameter 0/ lies. It can be seen that any parameter E S would be at-most k-sparse. Therefore, we have that V (S, (12) S Vk.
Additionally, use the notion 11s(A) ) to represent the &2 projection onto the model space S. Then, by the assumption the statement that 0g. 0, and the decomposability of || with respect to (S,S")
|1s (1) [[ss(())l (b)o1 (
(D) + (1s- |||s- (Λ)l
(1)
- [DP((D)+ +Is (A) 1I || (|)s(
|[I (A)]l
10) + All + ||>((a)l: || - || (A)ll
(9)
where the equality (i) holds by the triangle inequality, which the basic property of norms. Since
we are minimizing the objective function (D)()) we obtain the inequality of ( + All1
( < [D))( Combining this inequality with equation we have
0 S (A))
- ||Is (A))l1
(10)
Armed with inequalities equation decomposability of our regularizer T lI in order to derive the error bounds in terms of lg norm:
g and equation 10 we utilize the Hölder's inequality and the
A = (A,A) < |||||
| dc (|[ls(())]l
[Is ll.
Since the error vector A satisfies the inequality equation 10
| < ||
(11)
Combining all the pieces together yields
| < (S)A,), [Is(A)]l
where (MM is the abbreviation for V (8. -12).
22

---

Notice that the projection operator is non-expansive, [1]]ا I (S)),, and plugging back into equation 11 yields the &g error bounds.
|||{(A] I
| Hence, we obtain
Proof of Lemma 20 Define a sequence datasets D ...... Dd such that D = D. D* D', and for each i [k], Di, D differ on most one agent's dataset. Then, by the triangular inequality, we obtain
.....
k Σ -
[IĀ(D) - ((2') = - ((D)))12 -
S
s gA..
with probability at least kn by taking union bound over failure probabilities Y
Proof of Lemma 22
Before giving theoretical analysis, we first prove that Σxx is invertible with
high probability. With the help of Weyl's Inequality (Lemma 23 we can see that to show &g is
invertible it is sufficient to show that |xxx Σ112 1 have
Amin (2) This is due to that by Lemma 23 we
2
Amia [Σ) 1ス - E112 S Amin (ixx).
Thus, if |[ - ΣlI2 < Amin (2)
we have Amin (xxx) 2
Amin (I)
> O.
2
Thus, by Lemma it is sufficient to show that Amin (2:) 2 sx²
Vlog dog evn
which is true under
the assumption of n 2 Ω " dlogoggloggg [ug Thus, with probability at least - exp(-S((d)) it is Am (2)
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
Note that this a non-probabilistic result, and it holds deterministically for any selection of An any distributional setting of the covariates Iy. Our goal is to show that X, Z
r- (Exx)
[ (5xp)
under the assumptions specified in Lemma 21
1 -(ixx) ( (5x+) >
r QP (P(())
(12)
($xx)
-1 -
($$ex) 0" 00-(5xx Noa) 10)
32r2r3 log 1.28 2²ga
where the vector N₂ Rd is sampled from N(0,, Σxx. For any nonzero vector w E Idd Note that
Ia). We first develop upper bound of
Exxw
Exxw - Ew Ew 100
|wwl 0000000000000 - -1(88 - - w 80
Koo - 1iixx - 21(c] |
Our objective is to find sufficiently large such that [Exx Σ
is less than "ig.
By Lemma I we can see the following:
|x= - E/3 = 11xxx- =IE
(lag ng?
log d log 1rrt 1-4
(log
dog {rrl ng²
(13)
0
+
23

---

2r log dog we have [xxx]]
Thus, when
Q
2
Reo
|ooloo which implies
EtRos
2
(Exx)
Given sufficiently large n, from equation 12. have:
8+
( (D) 8
2
|| ($xx)
0r - -5xxx Nb)
(14)
2
1xp Exy
+ E - Exxll
[$xx - - 0-
+ +ll
Kio
N₂
Ti
T3
We will bound the above four terms one by one.
For J E d, we have Var (5) s E ( s (yyay)) & Eat = vs < cc. In
addition, E 1y (T=Tt))=2 v1 holds. Therefore, according to Lemma 13 have:
201t
cT&Tyt
P
S exp(-t))
where Tyn, - Ua Vaz the following can be derived:
Ey and is a certain constant. Then by the union bound,
2012 + Ty
7
< dexp(-t).
n
Next, we give an estimation
Tz. Note that for S.j S d. by lemma we have:
FijgTiy Eyyri
Fij,J Fij: + Fijunis Fyyar
Eji (Tij - mii) + (Ji- - y:) siij
S F 5t (Tiy xm5)²) P Plaral 2 Tx) E (ūr 3i)² x25)) P Pllvsl 2 Ty)
s vi
2e 20 2 20
which shows that T2 - /oi
2c
20
+ 2e
To upper bound term T3, we need to evaluate Lemma[]
1i Elloc and we can reuse obtained results from
We can see that T3 is bounded by O y log d log matrix.
Here we used the fact that Σxx is symmetric
Vne
11 - E) S 11EEx
E1|2|10 112 S 1|Exx E111|101112
log logdlog 100'12 noa
s 50
given the selection r.
The last term of equation 14 can be bounded by Gaussian tail bound by lemma
II
With probability
1 O(d- 5), have;
rTy log 1/2 logd
| 50
(15)
En
24

---

Finally combining all pieces, we can find that T3 is the dominating term. Since An 2
(Exx)
(1xx) Lemma 21 implies that with probability at least 1 8) - -2(d)
[Vllog
8- [ 0o
VTL
which completes our proof of Theorem.
Proof of Lemma
Our goal is to prove
E XX
E11
log
4r
2 1.25/6
105///log log d 87m
2-29
+(Voos
logd
4r2 /22 1.25/6 22555/log) Mog d
C 3²
87m
(16)
for some constant C. Since Σxx symmetric. know that [Šxx= E111 11 Thus, it suffices to prove that the bound in equation 16 holds for ||0xx El| Define the event Aij by
E11oo
Ag = ( TzrT < 4 min {1o sol Thres}
(17)
Then by lemma 25 we have P P(Aij) 21 2C 9/2,
Let D (dey) (dr)) with dij = (8zz7.8 - ozz .g) I (AG)). then the following holds.
B
211 < 2E
sup
T OzxT,i) 1 (Ais)
+ +2E|DDi
log d
4 22222 8
+
71
Eyn
$ 32
sup
min
1oze Sta..ssl:71
log
4r 4/2//111 2m 1.25/5 /v
Mog d
DI?
log (Vooyd
4r /
2 1.25/0
C
n
87n
(18)
1r2 /21n 2//g
2q
and the first term is dominating, while the second term EI D| is comparably negligible. By setting
Note the first term in equation 18 is bounded by Css
e7n
25

---

k-
log
4r2 12 1..21112.0 1.25/6 /lgg 67y
we have:
log d +
4r² /2 In 1.25/66/ logd
Σ
min
Taw ssl, , TV
en
171
Σ
min |otaol .
log d
41 v 2 In 1.25/ log d
+
n
Eyn
isk
13
log d
47 / 2 In 1.25/0vlogg
1/4
< Oskh"
+
C6 Σ
n
8ym
1>k
logd
4T² / 21 In 1.25/ /v ologd
S Ci
k*
+
81/0 (k=))2-1/9
8yH
1-9
log d
4r 2 1.25/6 2 llgd
S C7s
Eyn
which implies equation
if if E|I = 0 (+). We shall now show that D|] = Note that:
E D S d
Ede
Dg E {dly (Ag n (özZT = ŌzsT,1) 253) }) + di (A9 n (0 = =}]]}
1/
d Σ E { (ÖEET TunT (AE)) d
Eo nnt 5y (A n (özer = 0})
1/
ij
R R2
Lemma 25 yields that P (A,,) 2/ and the Whittle incquality (Thcorem 2 in (56) implies
0g 2.2
o 2x aj has all finite moments under the Gausssiaiintt condition. Hence, we have:
R1
(Ōaz", is - Oxx" ,1)²
"x)",1)) 2²11) (Ai))
(ORET.i -ZzT .s) 0 1/3
S Σ
p2/3 (A9))
15
< Cod d2 dd = =Os/n
On the other hand,
Rs
>
Eo² T is (AC, n (ōzsT,y -])
11
log d
4r 22 1.25/8 Vlog
=d =d>
Eo² Eo I |oauT.es 2 // n
17
logd 4r /
In 5
Tog
|022Ti0s S SM
E
Σ 22 u Bg
| sol 4ny
logd
16r / /21n 1.25/6 /
n
log d
16,2 / 22 In 1.25 1.25/8/loog logd
S S
n
26

---

sd
Σ
o
FxT uy
3 (1S85T Oz27.15
4
logd + 16r² / In 1 /.25/6
/ivv//loo llg d
0207
2 4
V
| > 4nV logp 16,² /2 2 1.25/ó 1.s/vvlogg Vlogy
Σ
pnn .s
El
ne
Txst lnie 3
oiut NyP (fl0ne7.s - -xxz"is (f10m57.s00000""
|massol
2
1
logd + 16r² / In 1.25/6 logd
TxST,s5 > 4rV
Σ
o0 NarT .s ({ | Tux
2 4
0 xxxT 25ع - |m ( @ocer.sl
mmsssl 1
17
logd
16r2 /2 16r2/21
1.25/6 / Vlgd
UNXT viyl > 4nV
ne
( (lozErio OZST,o5
3 Onx" ssl
d Σ
02 oxxt,1sh ,s
mm,ss
n(mass |msss 2 2210ss |oserrss M
log d > 44/
16r2 1oPV222n In 1.25/8/log ))
ne
This gives us:
OzsT .s 2 1
R2 S d Σ
logd d
16r2 22 1.25/ 2 8 Mogd
> 47
+
n
ne
(19)
Σ
0
|nnisl 2
ij
nf
log d
16 / 2 1. 1.25/ 8y Mog
(ore isl
>
47p
ne
For the first term of equation 19 by Lemma 24
we have:
((10E
I wol In{
log
d
axx .s
2 47
2
20 T
log d
na xx .ij exp
-1
ij
I
( uss
2 2
71
72
n
2
ij
22 72
Z. is
1 (1o000 no1 =47
log d
n1 uzz" F' .3j
exp
exp
8
1
< C
m
27

---

For the second term of equation 19 by Lemmas I1 and 24 we have
(fIrus))
2 0 0 In Dxxt vsl > 47V
log d +
16r 1 2 In 1.25/ ó Alog
Σ
ax! upP
ne
4 2 1. 1.255/8log log d /)
d
Σ
o ,trpP
(mussll m
log d
P
(miisll
81
2
TV
d
+ 40 10.1 Volloogd
o² ma T
$ Cd
SCd)
2x Kjj
exp
207
exp
32
(- 12
I Cold. d exp
d-8
2no
< Coodd 2no
log 1/0
7/2 72gg dl
ne2
Putting R₁ and R2 together yields that for some constant C >
C BIDD <
Proof of Lemma. 25.
Firstly, let us note that Σxx = Σxx + + Σ; " + Nj. Therefore by
Lemma 24 and Lemma 11 with probability at least Cd Cd for all I i, S d, and for some constants 7 and C that depends ON
log
128
2 log log
log d
O TnaT,is S 7/
So yr
(20)
n
ne
Vnee
Define the event Aij {(OREETAs) VV logd 4r 221n 1/22m1..2/// 1.25//
Let Exx
en (ÓRET uiigisa and N1 (n1,5))sissa We have:
@esT,K ky Oz .sl |a .ol (At,) + 1222 azxm -I
(21)
By the triangle inequality, is easy to see that
log
4r /2 In 1.25/6 log
Asj
MaaT,s Onn ig OnaFiah ssl > 7
n
En
logd d
4r 1.25/ /lg
GREF - Jnst > 27
n
En
and
logd
2r 21 1.25/8 /og
A JORTT - TnaT + TnaT S sn
log
2 2 1 255 6 log d
C
TEET,S -aaT (o
7V
+
en
Depending on the value of ana? ugn need consider the following three cases.
Case 1. Inat so1 S 4.4
logd
log 1 25/5/
28

---

For this case, we have:
37 4
log d
3 3 2 In 1.25/8 /555vv log
P ((A)) S | 0 axx
nol
- C1d 2d
This is due to the fact:
log d
3 3 In 1.25/0 0 /log
P | O2x
V
n
ne
3y
log d
3 2 In 1.25/6 2 log d
S
P
J02zT is - axx .s
|mm
n
ne
2 In 1.25/6 2/55/v1la V d
|m1,6s| > 0
P
Bij
nE
3 2 In 1.25/6 / logd
+PP
Big
00 |m1,el
ne
SP
| .j -Oxz"
3y
log d
P
1/333 3 In 1.25/ō
2
log d
|m.ss]
n
ne
< Cjd + 2d 2d 3,
where event B denotes B₁ |
logd
21n 1.25/8 295/1og log / ms
2xx 2 .d
and the last inequality comes from lemma 11 and 24
Thus by equation 21 with probability at least Zxx,, .i] which satisfies equation
1 Cid 2d- 2, we have: ÖzsT,5 ,6 xxx.. .i
Case 2. JRaT ssl 2 27V log + 81 22 1.25/6/logd
ne
For this case, we have
(bear - Oea asl
log d
72 222211 1.25/5 /lg I Cid + 2d
P (4 S
2 2
EN
where the proof is identical to the proof for case 1. Thus, with probability at least 1 Cid - have:
UEsT .ú Jx.F
@ azaF .sl
Also, by equation 20 equation also holds.
Case 3. Otherwise,
7
log d n
x2 2 log 1.25/6 10 dsl S usl=ss2s
log 8r 22 1.25/ 5 s2r
n +
nE For this case, we have
4
ne
TRnT s/l
TRuT syl or @ 1z.
logd 4r 22m. 1.25/6v/oog we can derive from equation 20 that with proba-
When I ssl 7/- bility at least 2d
n
on
Cid
logd 4r2
2 In 1.25/5 /llg 4
| aza ssl S S m
logd 2r /2 1. 25/6 or not, which completes
Thus, equation holds whether (oxs" .33 the proof of Lemma 25
2 7V
29

---

G
Omitted Proofs
Proof of Theorem 2 By Gaussian mechanism and the post-processing processing property, is easily that releasing E Ex satisfies (5 JDD, releasing E x satisfies (5 2 -DP. Thus, the output of Algorithm is (s, D)-..
Next, show that the output of the mechanism satisfies joint differential privacy using Billboard Lemma (Lemma 17 The estimators ('(D)) and 0" (i²) are computed in the same way as 0 (D). so 0F (P))) and 0 (²t))) each satisfy (e, JJDPP Since (P and 0 (δ²) are computed on disjoint
subsets of the data, then by the Parallel Composition Theorem, together they satisfy (c, 26D-JDP. By
the Sequential Composition Theorem (Lemma 19). the estimators (6 (D),6P (D)))) ( [D )) together
satisfy (2e, JJDP Finally, using the post-processing property and Billboard Lemma 17 the output
(0" (D),"" (D"), 80 (D"),, ( 80 (D*) }==)) of Algorithm 2 satisfies (2e, JJP.
Proof of Theorem For any realization D held by agents, let δ = T (D). Then by Lemma 15 have
E || (D) 1
< (D) 1
-E1I0P (Ō) - (D) 00'12 2(0
(Đ) - 00 (D)) 0-) 110 (D) 00 _2 (か) (D) 2E| ( (D) - 1-.
=RII@P (D) (F))) -
(22)
(1"Vlog =0==vinr dlogg Vnz
For the first term of equation 22 if we set the constraint bound An =0
we know
3²r logdlog with Eo
from Lemma 4 and Lemma
20 that when is sufficient large such that -2(
probability at least 1 - 3 Old a(1) we have
B100 (D) 8t (D)ll2 S 16v an
(23)
For the last term of equation 22 by Lemma 22 when n is sufficient large such that 2
2 2 log dlogg 1
with probability at least - O(d-R(1)
B((((D) - 0" S Vkdn.
(24)
Combining equation 23 and equation 24 yields that with probability at least 1 - 1-3-000 (3d-(d-)())
E(I 0- [E[ 1'1331 S 50( ka rlog "oogdoog' r Mog dl dlog
n2
Proof of Theorem 5 Suppose all agents other than are following strategy Tr..s. Let agent in group 1- b. E {0. 1). We will show that JT.., achieves 17- B-yyessann Nash equilibrium by bounding agent i's incentive to deviate. Assume that S Ta,s, otherwise there is nothing to show because agent would be allowed to submit an arbitrary report under o...g- For ease of notation, we write o for or... for the remainder of the proof. We first compute the maximum expected amount (based on their belief) that agent can increase their payment by misreporting to the analyst, i.c.
())) ne (D., (D))
(D, D..))
Banaz (1: 8 (D())) (T,, E 12 (01) D..
Boy.as
(D'))) (Z,, Ea Dr.c]
(25)
30

---

Note that Ba, ag (p.g) = a2(p 11lp-2pm 2pq + q²) is linear with respect to and is strictly concave function of 9 maximized at q p. Thus, equation 25 is upper bounded by the following with probability Cin R(1)
Bay
E
(Ti, 0" (F"( Di I (3x, 0" (0)()"(()))))
Bai.22
Bliai 0² ((((i)) Di. (D')) ci), (Ti, IE 101)
[T 0" (7(("))) P4, [3] - (5 (er
02
EK,,, 08 (D))) (ãi, 1, 2
02
EEET (0" (D*) (D. (0)]
02
$ 02 1 12 E (DD) - ~
ail1
r ||0 (D)) D 10]1D;,
We continue by bounding the term
-0 =0,)0 c:]l2. By Lemma 15
1B10"(1") Ep,
< |||00 (D*) 0" Dr.
|| "D"0 E D. 1.) cill2
-1B (D1"))_,ll ||E (D*) c.] Ea D, allla $ (D') -000))00'(0000
0" (D*))l2 |EE
|EE())(D))))) (D) - 1o
(26)
For the first term of equation 26 since agent believes that with at least probability 1 1 3, at most an agents will misreport their datasets under threshold strategy T datasets D and D differ only on at most an agents' datasets. By Lemma 20 and Lemma we the constraint
bound A. 2² l'Vllo d
when is sufficient large such that 2 52( * logdlog" 2 ) with 22
Vne
probability least 1 B O(and R(1) we have that
El 0 (D) 8p (D)ll2 S 16VRA,
(27)
For the second term of equation 26
E (DD))
E( [1)00 En D.) 10 (D")] Em-n(o|D,)
= Eenple D.) ED 0) 10" (D'))]] Ee e 1
Ee D.) EDD 17 @P(D') 0100)-
Since
p(D'10) v00) 0))(x'))) xx)x)x
we have
E E 1o
(0000))000)))))) (0(D") - - -Exx [R 10"h (x /²²) - 11
Since we have the prior knowledge that ||0"|l2 S Tg. Thus, for the posterior distribution ~ D.) it will also have ||0112 I re. By Jensen's inequality, Theorem 3 and Lemma 15 we have
( D.J Be>p(olD.) [.]112 S Ea-p(") D.), [ 11]0" (x x²) 01|2|X* 0]
< Ea-p x EL [1|@p(Xx 3² 01 0]
2
A log
0
ne
31

---

In addition to an increased payment, agent may also experience decreased privacy costs from misreporting, By Assumption B] this decrease in privacy costs is bounded above by c;8 + 38)=". Since we have assumed q S Ta,9, the decrease in privacy costs for agent is bounded above by To, + 30)=". Hence, agent i's total incentive to deviate is bounded above by
a r log d d'log
r*log d d'log 8 + Ta,
17 0 a2
2
n²c²
Proof of Theorem 6 Let agent have privacy cost O I Ta.3 and consider agent i's utility from participating in the mechanism. Suppose agent i is in group 1 b. then their expected utility is
E [u. = E Bar.s (Z,, (E,,0((D")) (T E a p b.) (0)) Di ci] - f((c),))
2 Bas Bai .a (B((Z,, 0" (D*))((()))) Co. (Te. E p (.) [0]) Ta, + 35)e
(28)
Note that
Bay (p,4) = 01 a2(p 2pg + x²) 2 0i a2( 2|pl1 + lg|
(29)
Since both
[T, 0 (D))) and ( Egmp(o) b.) 1,) are bounded by |2 ())) I rTo. thus
by equation 28 and equation 29 agent i's expected utility is non-negative as long as
a1 2 a2 + 3r) + T0, 35)e=.
Proof of Theorem 7 Note that
Bay (p. 9) S Ba Ba aa -2z(p - p²) s a az(1pl + lol²),
thus
B = Σ E(TT] Σ E B[Bar, (Z,, (Z,, (o. Di.
1=1
2=1
< n(a + ar + +()))
Proof of Corollary
g For any & E (3) 1) and > O, we set
n - ==n n ((])
a O(n 35 >,, = (n
a a2(rTo + +r + To Ta. 36)e" 02 = OOn
Note that by choosing { E (3: 1), we ensure that on on= o(1)
Recall that by Theorem 3 the private estimator is kna?
*log *log 22
>og d dooog n=2
accurate.
0(n25-1). Since for any (1) 1). we always have 1 4 < 25 1, we obtain 10 (D) 0- = (1)
Note that O ( O(n 2-n5-45) 0 (()))
To bound the expected budget and truthfulness, we first consider bounding the threshold value Ta
and the term 8(1 + 3. By Lemma 14 Ta,8 I 1 log dB + 383t log n) @(1). Combining these, we get 8 + e3 On 35).
Now we bound the term r7 for the truthfulness. Recall that by Theorem 5 the first term of the truthfulness bound is na² k dogg + r'log dlog O(n -1-E)_) and the second term of the 101--1-
ne?
bound is 8a. = O(n -3E), thus 17 O(n -1 -35 O(n (1-)-.
32

---

Then we consider individual rationality, By the choice of a1 and Theorem 6 the mechanism is individual rational for least 1 On 36) fraction of agents.
Lastly, we consider total payment made to the agents. By Theorem the total expected budget is B 0 (n(a1 a2(r7o r))))) ((n(22 + 8 + a2)) O(
H Impact Statement
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.
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have provided a detailed description of the claims in Section 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 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 long is clear that these goals are not attained by the paper.
2. Limitations
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 I and Section D
Guidelines:
The answer NA means that the paper has 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 (c.g.. independence assumptions, noiseless settings, model cell-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 few datasets or with 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, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails 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 faimesss.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
34

---

Answer: [Yes]
Justification: We have introduced all the assumptions in the main paper and we have also included the complete proofs of the theorems in the Apppendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
35

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
Our paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "tipps.c/ppulli//uuui httpe//gguu.eeeoeoouuubmmbibbi ceoommsssion ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
36

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp:///haarrpp..ccooopa//////t
Answer: [Yes]
Justification: Our paper conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal 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.
37

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, papprssii thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
38

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "qcix22OgOz", "reviewer": "Reviewer_YR32", "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.", "questions": "See above", "limitations": "See above", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper has a very clean presentation despite the complicated problem setting and technical components.\n2. The theoretical guarantees are comprehensive, including estimation error, privacy guarantee, truthfulness, individual rationality, and budget.\n3. The private estimator is quite interesting.", "weaknesses": "Currently, each agent only collects one data point. Is it possible to study the free-riding issue as well under the current framework?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for posing an interesting question. In our setting, we need to assume each user can only manipulate the response. Thus, it is unclear at this point whether our payment scheme can tackle the free-rider issue. We will leave it as a future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uupF4L1A82", "reviewer": "Reviewer_BxFH", "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.", "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?\n2) 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$.\n3) Can the authors clarify more about the practical validity of Assumption 4?\n4) A literature survey related to incorporating payments in differentially private models seems incomplete. Some relevant works are as follows\n[a] Justin Kang, Ramtin Pedarsani, & Kannan Ramchandran. (2024). The Fair Value of Data Under Heterogeneous Privacy Constraints in Federated Learning.\n[b] Ameya Anjarlekar, Rasoul Etesami, & R. Srikant. (2023). Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regression.\n5) 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?\n6) 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": "NA", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper provides an algorithm to solve the problem of high dimensional sparse regression with subgaussian covariates. They also make sure that the algorithm also ensures differential privacy of the data providers. Finally, they also provide a payment scheme that is individually rational and which incentivizes truthfulness.", "weaknesses": "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.\n2) The assumptions made in the paper do not seem practical (for example assumptions 3 and 4)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**W1: 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.**\n\n***We respectfully disagree with the reviewer regarding the contribution of our work compared to the work of Fallah et al. [1] or Anjarlekar et al [2]. Importantly, this paper is not a slight extension of DP logistic regression, and it is totally different from the work you mentioned.***\n\n* ***Our proposed DP algorithm is not adapted from DP logistic regression or mean estimation literature [1,2].*** The work of Anjarlekar et al. [2] is based on the previous literature on objective perturbation, which is an iterative algorithm. And the work of Fallah et al. [1] is based on adding Laplacian to a weighted mean. Compared to them, we developed a new closed-form estimator for sparse linear regression. \n\n* ***The methods you mentioned cannot solve our problem.*** Specifically, it is unknown where the objective perturbation method is suitable for high-dimension sparse linear regression, even if we only consider DP, as the utility will always depend on the dimensionality. the work of Fallah et al. [1] is based on adding Laplacian to a weighted mean, which obviously cannot solve our problem. \n\n* We provided theoretical results on individual rationality, Bayesian Nash equilibrium, and the payment budget, which have not been given by previous work Anjarlekar et al. [2]. \n\n* While there has been work on incorporating IC payment scheme into DP setting, we want to highlight that ***our paper are the first work to study in the high dimensional setting.*** High dimensionality gives rise to several consequences: (1) the regularization techniques used by prior work are not applicable, (2) a (novel) covariance matrix estimator is needed to guarantee the invertibility, (3) this assumption precludes the use of the output perturbation mechanism adopted in the previous work and therefore we seek to privatize by sufficient perturbation scheme, which in turn greatly makes our truthful analysis part more complicated. We strongly recommend the reviewer to go through Section.C in the Appendix for a comprehensive understanding and accurate evaluation of our work.\n\n[1] Fallah, Alireza, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar. \"Optimal and differentially private data acquisition: Central and local mechanisms.\" Operations Research 72, no. 3 (2024): 1105-1123.\n\n[2] Anjarlekar, Ameya, Rasoul Etesami, and R. Srikant. \"Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regression.\" arXiv preprint arXiv:2309.10340 (2023).\n\n>**W2: The assumptions made in the paper do not seem practical (for example assumptions 3 and 4)**\n\nWe made five assumptions throughout the paper. \n- Assumption 1 is the boundedness of the underlying parameter $\\theta^*$ and the covariance matrix.  As we mentioned in the paper, such assumptions have also been used in existing literature. \n- Assumption 2 is sub-Gaussianity on the covariate vector and response. Note that such an assumption is natural in the literation of statistical estimation and is weaker than the boundness assumption in [1, 2].  \n- Assumption 3 is a stronger version of [1]. We mimic their assumption on upper bounding the privacy cost function but instead of quadratic bound, we use cubic bound. This is a bit stronger since our assumption on the distribution of response is more relaxed than prior work and we consider the high dimensional sparse setting. Note that the quadratic bound assumption for $(\\epsilon,\\delta)$-DP is reasonable, as mentioned in Appendix D of [1]. ***We would like to point out that the upper bound on the privacy cost function is necessary for truthfulness analysis and it is also reasonable to assume that strategic users have bounded privacy cost functions.*** We will leave the problem of how to relax the assumption in future work. \n- Assumption 4 is the conditional independence of privacy cost coefficient $c_i$ of a user $i$ and the data of the other user's data $D_{-i}$ and cost coefficient $c_{-i}$ given a user's data $D_i$. ***This is a practical assumption since in our setting users are also concerned that their payment might be inferred from the privacy cost coefficient.*** This also means $c_i$ does not reveal any additional information about the costs or data of any other users.\n- Assumption 5 is the exponential tail decay of $c_i$ which we adopt from [1, 2].\n\nWe believe that each of these assumptions is necessary to carry out the analysis and also reasonable in practice. Please see below for more explanation about Assumption 3 and 4.\n\n[1] Cummings, Rachel, Stratis Ioannidis, and Katrina Ligett. \"Truthful linear regression.\" Conference on Learning Theory. PMLR, 2015.\n\n[2] Qiu, Yuan, Jinyan Liu, and Di Wang. \"Truthful Generalized Linear Models.\" arXiv preprint arXiv:2209.07815 (2022).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "POZuSrkoou", "reviewer": "Reviewer_81kj", "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.", "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?\n\nI 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).\n\nI 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?\n\nRight 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": "The authors should better stress that\n(i) Agents' \"rationality\" is merely on privacy leakage (they are indifferent to the trained model's behavior).\n(ii) Agents are assumed to have the same labeling function (parameter $\\theta^*$).\n(iii) (Individually rational) agents whose data is too different are more likely removed from the system.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 4, "strengths": "The paper tackles an interesting problem, at the heart of data collection for machine learning applications.\n\nThe algorithms and the proof techniques are important advancements in the understanding of privacy-preserving machine learning with financial compensations to strategic data providers.", "weaknesses": "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:\n- 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.\n- The partition $\\hat D^0 \\cup \\hat D^1$ should be presented before its use in line 273.\n- 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?).\n- The \"symmetric threshold strategy\" is used in the main text without definition (and without even a reference to the appendix!).\n\nThe paper makes a common ground-truth assumption (same $\\theta^*$). In practice, this may be unrealistic.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**W1: 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.**\n\nWe wish to thank the reviewer for pointing out this. We will add $\\Pi_r$ to Line 2 of Algorithm 1  and unify the rest of the notations.\n\n>**W2: The partition $\\hat{D}^{0} \\cap \\hat{D}^1$ should be presented before its use in line 273.**\n\n Yes, we will notate it before its use in the finalized version.\n\n>**W3: Assumption 5 has a typo (I guess). It should be $D_{-i}$ rather than $D_{j}$.  There should also be a quantification over $i$\n (unless each $(c_i, D_i)$ is iid?).**\n\nYes, there is a typo: $D_j$ should be $D_i$. i.e., the conditional marginal distribution of $c_i$.  We are indeed taking the infimum over every data $D_i$. This is not supposed to exclude user $i$. And yes, from Assumption 2 we have that $D_i$ is i.i.d and $c_i$ is also i.i.d because otherwise, the user will be able to gauge other user's payment.\n\n>**W4: The \"symmetric threshold strategy\" is used in the main text without definition (and without even a reference to the appendix!).**\n\nDue to the space limit, we postpone it to  Definition 4 (threshold strategy) of Section.A.1 in the Appendix. In game theory, a symmetric threshold strategy might involve players adopting the same threshold for their strategies. We will change the \"threshold strategy\" to the \"symmetric threshold strategy\" and move it to the main paper if space allows.\n\n>**W5: The paper makes a common ground-truth assumption (same \n). In practice, this may be unrealistic.**\n\nWe admit that a common underlying parameter $\\theta^*$ may not be the case in reality. However, in the statistical estimation literature, this is quite normal as we always assume the data are i.i.d. sampled from the same distribution or model. Moreover, current research on truthful and private mechanism design [1, 2] and private statistical estimation [3-5] always need such an i.i.d. assumption. Thus, such an assumption is reasonable. \n\n[1] Cummings, Rachel, Stratis Ioannidis, and Katrina Ligett. \"Truthful linear regression.\" Conference on Learning Theory. PMLR, 2015.\n\n[2] Qiu, Yuan, Jinyan Liu, and Di Wang. \"Truthful Generalized Linear Models.\" arXiv preprint arXiv:2209.07815 (2022).\n\n[3] Varshney, Prateek, Abhradeep Thakurta, and Prateek Jain. \"(Nearly) Optimal Private Linear Regression via Adaptive Clipping.\" arXiv preprint arXiv:2207.04686 (2022).\n\n[4] Cai, T. Tony, Yichen Wang, and Linjun Zhang. \"The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy.\" The Annals of Statistics 49.5 (2021): 2825-2850.\n\n[5] Bassily, Raef, et al. \"Private stochastic convex optimization with optimal rates.\" Advances in neural information processing systems 32 (2019).\n\n>**Q1:  I don't see Assumption 3 as a generalization of Cummings et al. Given that $\\delta < 1$\n, the assumption is essentially equivalent to (at least implied by) $f_i < 2c_i \\epsilon^3$\n, which is more demanding than $f_i < c_i \\epsilon^2$\n. It should be rather presented as a relaxation. Do the authors agree?**\n\nThe authors agree with the reviewer's opinion in this regard. Currently, Assumption 3 is indeed not a generalization of the assumption used in the work of Cummings et al. We will delete the generalization part in our paper.\n\n>**Q2: 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).**\n\nHere, one-round communication is the protocol that all agents send to the server once and simultaneously. Thus, there are no further interactions, which means not all algorithms work. For example, the based method is not one-round, and it does not work. As there is just one round, the server intuitively needs to aggregate this feedback and get an estimator, which has a closed form. \n\nIn the final version, if additional pages are allowed, we will move the results of the high-probability inversion guarantee to the main context. \n\n>**Q3: 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?**\n\nYes, indeed these parameters cannot be arbitrary and their values need to be carefully decided. Due to the space limit, we introduce how to tune these parameters in Lemma 22 in the Appendix. In the revised version, we will also state these conditions in our Theorem 3 and Corollary 8 in the main paper for ease of understanding.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**Response to Reviewer BFxH's question 6 about adding experiment**

>**Q6: 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.**

We wish to underscore that the essence of our contribution is theoretical. We would also like to bring the reviewer's attention to the broader field of truthful mechanism design where the majority does not have experiments. Some preliminary experiment results are provided now and more results will come out in our finalized version.

This figure plots the results of our mechanism. It is clear from the figure that when the sample size increases, the error goes down for every value of $\epsilon$. Different privacy budget values $\epsilon$ do make a great difference in error under a small data size regime. When the data size becomes larger, all errors quickly reduce to a very low level. This matches our estimation error $\tilde{O}(\frac{\sqrt{k}}{\sqrt{n}\epsilon})$.

Meta-review: 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.
Decision: Accept (poster)