# Truthful Generalized Linear Models

Yuan Qiu111The paper was done when Yuan Qiu was a research intern at King
Abdullah University of Science and Technology. College of Computing, Georgia
Institute of Technology  Jinyan Liu  School of Computer Science and
Technology, Beijing Institute of Technology  Di Wang  Division of CEMSE, King
Abdullah University of Science and Technology  SDAIA-KAUST Center of
Excellence in Data Science and Artificial Intelligence  Computational
Bioscience Research Center

###### Abstract

In this paper we study estimating Generalized Linear Models (GLMs) in the case
where the agents (individuals) are strategic or self-interested and they
concern about their privacy when reporting data. Compared with the classical
setting, here we aim to design mechanisms that can both incentivize most
agents to truthfully report their data and preserve the privacy of
individuals’ reports, while their outputs should also close to the underlying
parameter. In the first part of the paper, we consider the case where the
covariates are sub-Gaussian and the responses are heavy-tailed where they only
have the finite fourth moments. First, motivated by the stationary condition
of the maximizer of the likelihood function, we derive a novel private and
closed form estimator. Based on the estimator, we propose a mechanism which
has the following properties via some appropriate design of the computation
and payment scheme for several canonical models such as linear regression,
logistic regression and Poisson regression: (1) the mechanism is
$o(1)$-jointly differentially private (with probability at least $1-o(1)$);
(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, where $n$ is
the number of agents; (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)$. In the second part, we consider the
linear regression model under more general setting where both covariates and
responses are heavy-tailed and only have finite fourth moments. By using an
$\ell_{4}$-norm shrinkage operator, we propose a private estimator and payment
scheme which have similar properties as in the sub-Gaussian case.

##  1 Introduction

As one of the most fundamental models in statistics and machine learning,
Generalized Linear Models (GLMs) have been intensively studied and widely
applied to many areas such as medical trails [32], census surveys [30] and
crowdsourcing [2]. Among these studies, it is always assumed that the analysts
hold high-quality data, which is essential to the success of GLMs. However, in
many scenarios, such as medical trails and census surveys, data of interest
may contain sensitive information and thus they may be collected from
strategic and self-interested individuals who are concerned with their
privacy. In this case, data providers (agents)222In this paper, individuals,
data providers and participants are the same and all represent agents.  may be
unwilling to truthfully report their data, which will result in the failure of
estimating the underlying model. Thus, compared with the classical statistical
setting, it is necessary to model utility functions of individuals and to
design mechanisms that can output accurate estimators, preserve the privacy of
individuals reports, and provide proper incentives to encourage most
individuals to truthfully report their data to the analyst.

In general, the goal of solving the problem can be divided into two
interconnected components – data acquisition and privacy-preserving data
analysis. On one hand, an analyst will pay individuals (agents) in
compensation for possible privacy violation. He/She should pay each agent
strategically according to how well the reported data aligned with the
underlying statistical model and peers’ data, but meanwhile he/she needs to
minimize the total payment budget. On the other hand, the analyst needs to
perform privacy-preserving computation on the reported data to learn the
underlying model accurately. Thus, there is a tradeoff between the accuracy of
the estimator and the amount of payment budget required to compensate
participants. In this paper, we provide the first study on this tradeoff for
GLMs by proposing several Differentially Private (DP) mechanisms under
different settings. Specifically, our contribution can be summarized as
follows.

  * •

In the first part of the paper, we focus on GLMs where the distributions of
covariates are sub-Gaussian and the distributions of response are heavy-tailed
(only have finite fourth moments). First, based on stationary condition of the
maximizer of the likelihood function for GLMs, we derive a closed form
estimator and privatize the estimator to make it satisfies DP (with high
probability). Based on the DP estimator, we propose a general design of
computation and payment scheme. Specifically, for some canonical models such
as linear regression, logistic regression and Poisson regression, our
mechanism has the following properties (if we assume that the dimension of the
data is $O(1)$):

    1. 1.

The mechanism preserves privacy for individuals’ reported data, i.e., the
output of the mechanism is $o(1)$-Jointly Differentially Private (Definition
3) with probability $1-O(n^{-{\Omega(1)}})$, where $n$ is the number of
participants (agents).

    2. 2.

The private estimator of the mechanism is $o(1)$-accurate, i.e., when the
number of agents increases, our private estimator will be sufficiently close
to the underlying parameter.

    3. 3.

The mechanism is asymptotically truthful, i.e., it is an
$o(\frac{1}{n})$-approximate Bayes Nash equilibrium for a $(1-o(1))$-fraction
of agents to truthfully report their data.

    4. 4.

The mechanism is asymptotically individually rational, i.e., the utilities of
a $(1-o(1))$-fraction of agents are non-negative.

    5. 5.

The mechanism only requires $o(1)$ payment budget, i.e., when the number of
participants increases, the total payment tends to zero.

  * •

One disadvantage of the previous method is that the it relies on the
assumption that the distributions of covariates are sub-Gaussian, which may
not hold in some scenarios. To address this issue, in the second part we
consider a more general setting where the distributions of both covariates and
responses are heavy-tailed. Specifically, we focus on the linear regression
model and provide a private estimator by applying an $\ell_{4}$-norm shrinkage
operator to each covariate. Based on the private estimator and the idea of the
above method, we present a mechanism which has similar properties as in the
sub-Gaussian data case.

Due to space limit, all the proofs and technical lemmas are included in the
Appendix.

##  2 Related work

Start from [18], there is a long list of work studies data acquisition from
agents that have privacy concern from different perspectives [27, 16, 29, 17,
14]. However, most of them do not consider statistical estimation problems.
[11] is the work that is most closest to ours. It focuses on estimating the
linear regression model from self-interested agents that have privacy concern.
However, there are several critical differences compared with our work. First,
the method in [11] is based on the optimal solution of linear regression,
which has a closed form and thus cannot be extended to GLMs as the optimal
solution of GLMs does not have closed form in general. Secondly, [11] needs
strong assumptions on the data distribution to achieve the privacy guarantee,
i.e., it need to assume that the $\ell_{2}$-norm of the covariates and
responses are bounded, while in this paper we extend the setting to the heavy-
tailed case. Such extension is non-trivial as here we use the $\ell_{4}$-norm
shrinkage (see Section 4.3.1 for details) to preprocess the covariates.
Recently [26] also considers mean estimation and linear regression estimation
from agents with privacy concern. However, there is no DP guarantee for their
methods. Thus, it is incomparable with our work.

In the classical setting of estimating GLMs in the DP model, there are
numerous approaches, such as [3, 23, 34, 7, 5]. However, all of them are based
on adding noise to the output of some optimization methods, privatizing the
objective function or adding noise to gradients in optimization methods, which
cannot be adopted to our problem as data acquisition is just a single-round
interactive procedure between analyst and agents, while those above approaches
need multiple rounds of interactions. To address the issue, we propose a novel
and non-trivial private estimator for GLMs. Compared with the previous
approaches, our estimator has a closed-form expression and can be gotten via
single round of interaction. This is similar to the linear regression case and
we believe that it can also be used in other related problems.

Besides the privacy concern, statistical estimation from strategic agents also
has been studied in a variety of different contexts. For example, [9] studies
linear regression in the case where agents may intentionally introduce errors
to maximize their own benefits and presents several group strategyproof linear
regression mechanisms, which are later extended to classification problems
[8]. [20] proposes learning classifiers that are robust to agents
strategically misreporting their feature vectors to trick the algorithm into
misclassifying them. In [6], the authors study fitting linear regression model
in the case where agents can only manipulate their costs instead of their
data.

##  3 Preliminaries

Notations: Given a matrix $X\in\mathbb{R}^{n\times d}$, we denote its $i$-th
row by $\mathbf{x}_{i}^{T}$ and its $(i,j)$-th entry by $[X]_{ij}$. For a
vector $v$, denote $[v]_{j}$ or $v_{ij}$ as its $j$-th coordinate. For any
$p\in[1,\infty]$, let $\|X\|_{p}$ denote its $p$-norm, i.e.,
$\|X\|_{p}:=\sup_{y\neq 0}\frac{\|Xy\|_{p}}{\|y\|_{p}}$. For an event $A$, we
denote the indicator as $\mathbf{1}_{A}$ where $\mathbf{1}_{A}=1$ if $A$
occurs, otherwise $\mathbf{1}_{A}=0$. The sign function of a real number $x$
is a piecewise function which is defined as $\mathrm{sgn}(x)=-1$ if $x<0$;
$\mathrm{sgn}(x)=1$ of $x>0$; and $\mathrm{sgn}(x)=0$ if $x=0$.

###  3.1 Problem Setting

Suppose that there is a data universe
$\mathcal{D}=\mathcal{X}\times\mathcal{Y}\subseteq\mathbb{R}^{d}\times\mathbb{R}$
and $n$ agents in the population. The $i$-th agent has a feature vector
(covariate) $\mathbf{x}_{i}\in\mathcal{X}$, and a response variable
$y_{i}\in\mathcal{Y}$. We assume $\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{n}$ are
i.i.d. sampled from a Generalized Linear Model (GLM). That is,
$\mathbf{x}_{i}$ are i.i.d. random vectors drawn from some unknown
distribution $\mathcal{F}$ and there exists a $\theta^{*}\in\mathbb{R}^{d}$
such that the conditional probability function
$\mathcal{G}_{\mathbf{x}_{i}}=p(\cdot|\mathbf{x}_{i})$ of $y_{i}$ has the
following parameterized form:

$\displaystyle
p(y_{i}|\mathbf{x}_{i};\theta^{*})=\exp\left\\{\frac{y_{i}\langle\mathbf{x}_{i},\theta^{*}\rangle-A(\langle\mathbf{x}_{i},\theta^{*}\rangle)}{\phi}+c(y_{i},\phi)\right\\},$
(1)

where $\phi\in\mathbb{R}$ is a fixed and known scale parameter,
$c(\cdot,\cdot)$ is some known function and $A(\cdot)$ is the link function.
We assume that function $A$ is twice differentiable, and its derivative
function $A^{\prime}$ is monotonic increasing. It is well-known that
$\mathbb{E}[y|\mathbf{x}_{i},\theta^{*}]=A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)$
and
$\mathrm{var}[y|\mathbf{x}_{i},\theta^{*}]=A^{\prime\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)\phi$
(where $A^{\prime\prime}(\cdot)$ is the second derivative function of
$A(\cdot)$). Note that GLMs include several canonical models such as linear
regression, logistic regression and Poisson regression (see Section 4.3 for
details). In this paper, we focus on the low dimensional case which means
$n\gg d$ and we make the following assumptions on the parameter of interest.

######  Assumption 1.

Throughout the paper, we assume that the model parameter
$\theta^{*}\in\mathbb{R}^{d}$ is drawn from a prior distribution $p(\theta)$,
and $\|\theta^{*}\|_{2}\leq\tau_{\theta}$ with some (known) constant
$\tau_{\theta}>0$.

There is an analyst who aims to estimate the underlying parameter in (1) from
agents’ data. That is, she/he wants to estimate $\theta^{*}$ based on data
$D=\\{D_{i}=(\mathbf{x}_{i},y_{i})\\}_{i=1}^{n}$. As we mentioned previously,
here we consider the case that the agents are strategic or self-interested,
and they concern on the privacy when reporting their data. Specifically, we
assume that each agent is characterized by a privacy cost coefficient
$c_{i}\in\mathbb{R}_{+}$. Higher value of $c_{i}$ indicates that agent $i$
concerns more about the privacy violation due to truthfully reporting $y_{i}$
to the analyst. Thus, due to the privacy concern, each agent $i$ can
manipulate his/her response $y_{i}$. 333However, we assume that each agent $i$
cannot manipulate her/his feature vector $\mathbf{x}_{i}$, which has the same
setting as in [11]. If we denote $\hat{y}_{i}$ as the the reported response,
$\hat{D}_{i}=(\mathbf{x}_{i},\hat{y}_{i})$ as the reported data, and
$\sigma_{i}$ as the reporting strategy, i.e., $\hat{y}_{i}=\sigma_{i}(D_{i})$.
Then the main goal of the analyst is to estimate the parameter vector
$\theta^{*}\in\mathbb{R}^{d}$ based on the reported data
$\hat{D}=\\{\hat{D}_{i}\\}_{i=1}^{n}$. Moreover, as agents may lie about their
private responses $y_{i}$, the analyst need to construct a payment rule
$\pi:\mathcal{D}^{n}\to\Pi^{n}$ that encourages truthful reporting, i.e.,
misreporting the response $y_{i}$ will lead to lower received payment
$\pi_{i}$.

Overall, the analyst aims to a design a truthful mechanism $\mathcal{M}$ which
takes the reported data $\hat{D}$ as input, and outputs an estimator
$\bar{\theta}$ of $\theta^{*}$ and a set of non-negative payments
$\\{\pi_{i}\\}_{i=1}^{n}$ for each agent. To make the mechanism incentivize
truthful participation of most agents, there should be some privacy guarantees
for the reports provided by agents. Informally, we seek private mechanisms
that allow accurate estimation of $\theta^{*}$ and require only asymptotically
small payment budget. All the above build upon the agents’ rational behaviors
and the privacy model, which will be discussed in details in the following
sections.

###  3.2 Differential Privacy

In this section, we define the desired criteria of privacy protection. We
adopt some relaxations of the canonical notion of Differential Privacy (DP).

######  Definition 1 ($\varepsilon$-Differential Privacy [13]).

Given a data universe $\mathcal{D}$ and any positive integer $n$, we say that
two $n$-size datasets $D,D^{\prime}\subseteq\mathcal{D}^{n}$ are neighbors if
they differ by only one data sample, which is denoted as $D\sim D^{\prime}$. A
randomized algorithm $\mathcal{A}$ is $\epsilon$-differentially private (DP)
if for all neighboring datasets $D,D^{\prime}$ and for all events $S$ in the
output space of $\mathcal{A}$, we have 444All the methods and results in this
paper can be extended to $(\epsilon,\delta)$ version of DP by adding Gaussian
noise. For simplicity, we omit them here.

$\mathbb{P}(\mathcal{A}(D)\in S)\leq
e^{\epsilon}\mathbb{P}(\mathcal{A}(D^{\prime})\in S).$

The definition of DP guarantees that the distributions of $\mathcal{A}(D)$ and
$\mathcal{A}(D^{\prime})$ are almost indistinguishable. In other words, if a
mechanism is DP, one cannot tell whether any specific individual’s data is
included in the original dataset or not based on observing its output. For our
problem, at a high-level, the canonical notion of DP requires that all outputs
by the mechanism, including the payments it allocates to agents, are
insensitive to each agent’s input. However, this is quite stringent since the
payment to each agent is shared neither publicly nor with other agents. Thus,
instead of the original DP, we consider one of its relaxations namely joint
differential privacy [24].

######  Definition 2 ($\varepsilon$-Joint Differential Privacy [24]).

Consider a randomized mechanism
$\mathcal{M}:\mathcal{D}^{n}\to\Theta\times\Pi^{n}$ with arbitrary response
sets $\Theta,\Pi^{n}$. For each $i\in[n]$, let
$\mathcal{M}(\cdot)_{-i}=(\theta,\pi_{-i})\in\Theta\times\Pi^{n-1}$ denotes
the portion of the mechanism’s output that is observable to outside observers
and agents $j\neq i$. Then the mechanism $\mathcal{M}$ is $\epsilon$-jointly
differentially private (JDP) if for every agent $i$, every dataset
$D\in\mathcal{D}^{n}$ and every $D_{i}^{\prime},D_{i}\in\mathcal{D}$ we have

$\displaystyle\forall\mathcal{S}\subseteq\Theta\times\Pi^{n-1},\mathbb{P}\left(\mathcal{M}(D_{i},D_{-i})_{-i}\in\mathcal{S}|(D_{i},D_{-i})\right)\leq
e^{\varepsilon}\mathbb{P}\left(\mathcal{M}(D_{i}^{\prime},D_{-i})_{-i}\in\mathcal{S}|(D_{i}^{\prime},D_{-i})\right),$

where $D_{-i}\in\mathcal{D}^{n-1}$ is the dataset $D$ that excludes the $i$-th
sample in $D$ and $\pi_{-i}$ is the vector that comprises all payments
excluding the payment of agent $i$.

In Definition 2 we assume that the private estimator $\theta$ computed by the
mechanism $\mathcal{M}$ is a publicly observable output; in contrast, each
payment $\pi_{i}$ can only be observed by agent $i$. Thus, from the view of
each agent $i$, the mechanism output that is publicly released and that in
turn might violate his/her privacy is $(\theta,\pi_{-i})$.

In this paper, we further relax the definition of JDP by relaxing the
requirement that the ratio between two output distributions is upper bounded
for all pairs of datasets, to the requirement that the bounded ratio holds for
likely dataset pairs. Specifically, motivated by the definition of random DP
[19, 31], we consider random joint differential privacy:

######  Definition 3 ($(\varepsilon,\gamma)$-Random Joint Differential
Privacy).

Consider the same setting as in Definition 2, we call a mechanism
$\mathcal{M}$ preserves $(\varepsilon,\gamma)$-random joint differential
privacy (RJDP), at privacy level $\varepsilon>0$ and confidence level
$\gamma\in(0,1)$, if for every agent $i$, every dataset $D\in\mathcal{D}^{n}$
and every $D_{i},D_{i}^{\prime}\in\mathcal{D}$ we have

$\displaystyle\mathbb{P}[\forall\mathcal{S}\subseteq\Theta\times\Pi^{n-1},\mathbb{P}(\mathcal{M}(D_{i},D_{-i})_{-i}\in\mathcal{S}|(D_{i},D_{-i}))\leq
e^{\varepsilon}\mathbb{P}(\mathcal{M}(D_{i}^{\prime},D_{-i})_{-i}\in\mathcal{S}|(D_{i}^{\prime},D_{-i}))]\geq
1-\gamma.$

with the inner conditional probabilities take over the mechanism’s
randomization, and the outer probability takes over datasets
$(D_{i},D_{-i}),(D_{i}^{\prime},D_{-i})$.

Note that there exists another relaxation of $\epsilon$-JDP called approximate
JDP, or $(\epsilon,\delta)$-JDP, which is derived from $(\epsilon,\delta)$-DP.
An $(\varepsilon,\delta)$-JDP mechanism on any dataset (including likely ones)
may leak sensitive information on low probability responses, forgiven by the
additive $\delta$ relaxation, while $(\epsilon,\gamma)$-RJDP offers an
alternative relaxation, where on all but a small $\gamma$-proportion of
unlikely dataset pairs, pure $\epsilon$-JDP holds. Similar to the approximate
JDP, here we hope that $\gamma=o(\frac{1}{n})$.

###  3.3 Utilities of Agents

Based on the privacy definition, we now present the model on agents’ utility.
Here we adopt a similar assumption on the privacy cost as in the previous work
[11, 18]. Specifically, for each agent $i$, he/she has a privacy cost
parameter $c_{i}$ and a privacy cost function
$f_{i}(c_{i},\varepsilon,\gamma)$ which measures the cost he/she incurs when
his/her data is used in an $(\epsilon,\gamma)$-RJDP mechanism. Moreover, with
payment $\pi_{i}$, we define agent $i$’s utility from reporting his/her data
as $u_{i}=\pi_{i}-f_{i}(c_{i},\varepsilon,\gamma)$. In this paper, following
the previous work, we assume that all functions $f_{i}$ are bounded above by a
function of $\epsilon,\gamma$ and $c_{i}$.

######  Assumption 2.

The privacy cost function of each agent satisfies

$\displaystyle f_{i}(c_{i},\varepsilon,\gamma)\leq
c_{i}F(\varepsilon,\gamma).$

where $F(\varepsilon,\gamma)$ is an increasing function of both $\varepsilon$
and $\gamma$, and $F(\varepsilon,\gamma)\geq 0$ for all
$\varepsilon\in\mathbb{R}^{+}$.

Recall that $\varepsilon,\gamma$ are privacy parameters of the mechanism (see
Definition 3). As larger values of $\varepsilon$ and $\gamma$ imply weaker
privacy guarantee, which means the privacy cost of an agent becomes larger.
Thus, it is natural to let $F$ be a component-wise increasing function. Note
that in [11], the authors consider the case where $\gamma=0$ and
$F(\epsilon,\gamma)=\epsilon^{2}$. Thus, Assumption 2 can be considered as a
generalization of their assumption.

We also assume that each cost parameter $c_{i}$ is drawn independently from
some distribution $\mathcal{C}$. Here we allow $c_{i}$ to be correlated with
the data sample $D_{i}$. This is reasonable since for example, in a medical
survey setting, if agent $i$ has a private value $y_{i}=1$ which means she/he
is diagnosed as some disease, then she/he is probably more unwilling to
truthfully report the value, which implies $c_{i}$ is larger. However, we
assume that an agent’s cost coefficient $c_{i}$ does not provide any
information about other agents:

######  Assumption 3.

Given $D_{i},(D_{-i},c_{-i})$ is conditionally independent of $c_{i}$:

$\displaystyle
p(D_{-i},c_{-i}|D_{i},c_{i})=p(D_{-i},c_{-i}|D_{i},c_{i}^{\prime})\quad\text{for
all }D_{-i},c_{-i},D_{i},c_{i},c_{i}^{\prime}.$

where $c_{-i}$ is the collection of privacy costs excluding the privacy cost
of agent $i$.

In addition, we assume that the probability distribution of $c_{i}$ has
exponential decay. Actually we can relax the assumption to polynomial decay
and here the exponential decay assumption is only for simplicity.

######  Assumption 4.

There exists some constant $\lambda>0$ such that the conditional distribution
of privacy cost coefficient satisfies

$\displaystyle\inf_{D_{j}}\mathbb{P}_{c_{i}\sim
p(c_{i}|D_{j})}(c_{i}\leq\tau)\geq 1-e^{-\lambda\tau}.$

###  3.4 Truthful Mechanisms

In this paper, we aim to design mechanisms that have the following properties:
(1) truthful reporting is an equilibrium; (2) the private estimator of the
outputs should be close to $\theta^{*}$; (3) the utilities for almost all
agents are non-negative; (4) the payment budget required from the analyst to
run the mechanism is small. We will quantify these properties using the notion
of Bayesian game. A multiagent, one-shot, and simultaneous-move symmetric
Bayesian game can model the outcome of agents’ strategic reporting behavior.
Formally, there are $n$ agents involved in the game. They privately observe
their types
$(\mathbf{x}_{i},y_{i},c_{i})\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mathcal{F}\times\mathcal{G}_{\mathbf{x}_{i}}\times\mathcal{C}$.
Each agent $i$ plays action $(\mathbf{x}_{i},\hat{y}_{i})$ and receives a
real-valued payment $\pi_{i}$. And finally he/she receives utility
$u_{i}=\pi_{i}-f_{i}(c_{i},\varepsilon,\gamma)$. Let $\sigma_{i}$ denote agent
$i$’s reporting strategy (i.e., $\hat{y}_{i}=\sigma_{i}(y_{i})$),
$\sigma=(\sigma_{1},\cdots,\sigma_{n})$ denote the collection of all agents’
strategies, and
$\sigma_{-i}=(\sigma_{1},\cdots,\sigma_{i-1},\sigma_{i+1},\cdots,\sigma_{n})$
denote the collection of strategies except $\sigma_{i}$. 555Note that
throughout in the Bayesian game, the strategy spaces, the payoff functions,
possible types, and the prior probability distribution are assumed to be
common knowledge. Based on this, we first quantify the property (1) by
Bayesian Nash equilibrium.

######  Definition 4 ($\eta$-Bayesian Nash equilibrium).

A reporting strategy profile $\sigma=(\sigma_{1},\cdots,\sigma_{n})$ forms an
$\eta$-Bayesian Nash equilibrium if for every agent $i$, $D_{i}$ and $c_{i}$,
and for any other reporting strategy $\sigma^{\prime}_{i}\neq\sigma_{i}$,

$\displaystyle\quad\mathbb{E}_{D_{-i,c_{-i}}\sim
p(D_{-i},c_{-i}|D_{i},c_{i})}[u_{i}(\sigma_{i}(D_{i},c_{i}),\sigma_{-i}(D_{-i},c_{-i}))]$
$\displaystyle\geq\mathbb{E}_{D_{-i},c_{-i}\sim
p(D_{-i},c_{-i}|D_{i},c_{i})}[u_{i}(\sigma^{\prime}_{i}(D_{i},c_{i}),\sigma_{-i}(D_{-i},c_{-i}))]-\eta.$

The positive value $\eta$ quantifies at most how much additional expected
payment an agent can receive if she/he changes her/his reporting strategy. As
we want all agents to truthfully report their data, we require the payment
rule to keep $\eta$ as small as possible. In this paper we consider the
following threshold strategy. We will show that if all agents follow the
threshold strategy with some common positive value $\tau$, then such a
strategy profile achieves an $\eta$-Bayesian Nash equilibrium.

######  Definition 5 (Threshold strategy).

Define the threshold strategy $\sigma_{\tau}$ as follows:

$\displaystyle\hat{y}_{i}=\sigma_{\tau}(\mathbf{x}_{i},y_{i},c_{i})=\begin{cases}y_{i},\quad\text{if}\quad
c_{i}\leq\tau,\\\ \text{arbitrary value in $\mathcal{Y}$},\quad\text{if}\quad
c_{i}>\tau.\end{cases}$

To link truthful reporting strategy threshold $\tau$ and privacy cost
coefficients $c_{i}$, following [11], we use the following definition.

######  Definition 6.

Fix a probability density function $p(c)$ of privacy cost parameter, and let

$\displaystyle\tau^{1}_{\alpha,\beta}=\inf\\{\tau>0:\mathbb{P}_{(c_{1},\cdots,c_{n})\sim
p^{n}}(\\#\\{i:c_{i}\leq\tau\\}\geq(1-\alpha)n)\geq 1-\beta\\},$
$\displaystyle\tau_{\alpha}^{2}=\inf\\{\tau>0:\inf_{D_{i}}\mathbb{P}_{c_{j}\sim
p(c|D_{i})}(c_{j}\leq\tau)\geq 1-\alpha\\}.$

Define $\tau_{\alpha,\beta}$ as the larger of these two thresholds:
$\tau_{\alpha,\beta}=\max\\{\tau_{\alpha,\beta}^{1},\tau_{\alpha}^{2}\\}.$

Note that $\tau^{1}_{\alpha,\beta}$ is such a threshold that with probability
at least $1-\beta$, at least $1-\alpha$ fraction of agents have cost
coefficient $c_{i}\leq\tau_{\alpha,\beta}$. And $\tau_{\alpha}^{2}$ is such a
threshold that conditioned on his/her own dataset $D_{i}$, each agent $i$
believes that with probability $1-\alpha$ any other agent $j$ has cost
coefficient $c_{j}\leq\tau_{\alpha,\beta}$.

For property (2), we use the square of $\ell_{2}$-norm distance between the
private estimator $\bar{\theta}^{P}$ and the true parameter $\theta^{*}$.

######  Definition 7 ($\eta$-accurate).

We call the mechanism is $\eta$-accurate if its output $\bar{\theta}^{P}$
satisfies $\mathbb{E}[\|\bar{\theta}^{P}-\theta^{*}\|_{2}^{2}]\leq\eta$.

To satisfy property (3), we should make payments high enough to compensate
privacy cost.

######  Definition 8 (Individual rationality).

Let $u_{i}$ denote the utility agent $i$ receives. A mechanism is individually
rational if $\mathbb{E}[u_{i}]\geq 0$ for every agent $i$.

We also concern on the total amount of payment budget required by the analyst
to run the mechanism, and want it tend to be zero when the number of agents
increases.

######  Definition 9 (Asymptotically small budget).

An asymptotically small budget is such that
$\mathcal{B}=\sum_{i=1}^{n}\mathbb{E}[\pi_{i}]=o(1)$ for all realizable
$D=\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{n}$.

##  4 Sub-Gaussian Case for Generalized Linear Models

In this section we consider generalized linear models (1) with sub-Gaussian
covariates.

######  Definition 10 (Sub-Gaussian random variable).

A zero-mean random variable $X\in\mathbb{R}$ is said to be sub-Gaussian with
variance $\sigma^{2}$ ($X\sim\mathrm{subG}(\sigma^{2})$) if its moment
generating function satisfies
$\mathbb{E}[\exp(tX)]\leq\exp(\frac{\sigma^{2}t^{2}}{2})$ for all $t>0$.

######  Definition 11 (Sub-Gaussian random vector).

A zero mean random vector $X\in\mathbb{R}^{d}$ is said to be sub-Gaussian with
variance $\sigma^{2}$ ($X\sim\mathrm{subG}_{d}(\sigma^{2})$) if $\langle
X,u\rangle$ is sub-Gaussian with variance $\sigma^{2}$ for any unit vector
$u\in\mathbb{R}^{d}$.

The class of sub-Gaussian random variables is quite large. It includes bounded
random variables and Gaussian random variables, and it enjoys strong
concentration properties.

######  Lemma 1 ([36]).

If $X\sim\mathrm{subG}(\sigma^{2})$, then for any $t>0$, it holds that
$\mathbb{P}(|X|>t)\leq 2\exp(-\frac{t^{2}}{2\sigma^{2}})$.

######  Lemma 2 ([36]).

For a sub-Gaussian vector $X\sim\text{subG}_{d}(\sigma^{2})$, with probability
at least $1-\delta$ we have $\|X\|_{2}\leq
4\sigma\sqrt{d\log\frac{1}{\delta}}$.

We make the following assumptions used throughout this section.

######  Assumption 5.

The covariates
$\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{n}\in\mathbb{R}^{d}$ are
i.i.d. (zero-mean) sub-Gaussian random vectors with variance
$\frac{\sigma^{2}}{d}$ with $\sigma=O(1)$, Moreover, the covariance matrix
$\Sigma$ of $\mathbf{x}_{i}$ satisfies that
$\|\Sigma\|_{\infty}\geq\kappa_{\infty}$ and $\|\Sigma\|_{2}\geq\kappa_{2}$
for constants $\kappa_{\infty},\kappa_{2}=\Theta(1)$, i.e., $\forall
w\in\mathbb{R}^{d}$, $\|\Sigma w\|_{\infty}\geq\kappa_{\infty}\|w\|_{\infty}$
and $\|\Sigma w\|_{2}\geq\kappa_{2}\|w\|_{2}$. We also assume that $y_{i}$
have finite fourth moment $R:=\mathbb{E}[y_{i}^{4}]=O(1)$. 666For simplicity,
here we assume the variance proxy as $\frac{\sigma^{2}}{d}$ is to make
$\|x_{i}\|_{2}$ bounded by a constant so that we can compare with the previous
work on linear regression with bounded covariates. We can extend all of our
results to the general $\sigma^{2}$ case with additional factor of
$\text{Poly}(d)$ in the upper bounds of our results.  We focus on the low
dimension case where $n=\tilde{\Omega}(d)$, where $\tilde{\Omega}$ omits the
term of $\log n$. 777It is also notable that for all the constants, Big-$O$
and Big-$\Omega$ notations of in this paper we omit the terms of
$\sigma,R,\kappa_{2},\kappa_{\infty},\lambda_{\max}$ as we assume they are
constants, where $\lambda_{\max}$ is the largest eigenvalue of $\Sigma$. See
the proofs in Appendix for the full version of the results.

Note that by Lemma 2, with high probability each $\|\mathbf{x}_{i}\|_{2}$ is
upper bounded by a constant. This can be thought as a generalization of [11]
which assumes all $\|\mathbf{x}_{i}\|_{2}$ are bounded by a constant. However,
[11] also assumes that each $y_{i}$ is also bounded where here we assume that
it only has finite fourth moment.

###  4.1 Main Idea

Before showing our method, we first go back to estimating $\theta^{*}$ without
privacy constraint and manipulating the response. Given $n$ samples
$\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{n}$, the maximum likelihood estimator of
$\theta^{*}$ based on the probability distribution (1) is given by

$\displaystyle\tilde{\theta}\in\arg\max_{\theta}\prod_{i=1}^{n}p(y_{i}|\mathbf{x}_{i};\theta)=\arg\min_{\theta}-\frac{1}{n}\theta^{T}X^{T}y+\frac{1}{n}\textbf{1}^{T}A(X\theta),$
(2)

where
$X=(\mathbf{x}_{1}^{T},\cdots,\mathbf{x}_{n}^{T})^{T}\in\mathbb{R}^{n\times
d},y=(y_{1},\cdots,y_{n})^{T}\in\mathbb{R}^{n}$ and
$A(X\theta)\in\mathbb{R}^{n}$ with
$[A(X\theta)]_{j}=A(\mathbf{x}_{j}^{T}\theta)$. Since $\tilde{\theta}$ is the
maximizer of likelihood function (2), motivated by [38], it must satisfies the
stationary condition:

$\displaystyle X^{T}y=X^{T}\nabla A(X\tilde{\theta}),$

where $\nabla
A(\eta)\equiv(A^{\prime}(\eta_{1}),\cdots,A^{\prime}(\eta_{n}))^{T}\in\mathbb{R}^{n}$
for any $\eta\in\mathbb{R}^{n}$. Intuitively, it means that $\nabla
A(X\hat{\theta})\approx y$ which implies $X\tilde{\theta}\approx[\nabla
A]^{-1}(y)$, where $[\nabla
A]^{-1}(y)\equiv((A^{\prime})^{-1}(y_{1}),\cdots,(A^{\prime})^{-1}(y_{n}))$.
However, the challenge here is that the function $(A^{\prime})^{-1}(\cdot)$
may not be well defined on every point of $\mathcal{Y}$. In fact the function
$A^{\prime}(\cdot)$ is only onto the interior $\mathcal{M}^{o}$ of the
response moment polytope $\mathcal{M}$, which is defined as
$\mathcal{M}:=\\{\mu:\mu=\mathbb{E}_{p}[y],\text{for some distribution $p$
over $y\in\mathcal{Y}$}\\}$ [37]. Thus to make it well-defined we should
project each $y_{i}$ onto $\mathcal{M}^{o}$ first. However, as
$\mathcal{M}^{o}$ is an open set, the projection operator may not be well-
defined. Thus, we use a closed subset of $\mathcal{M}^{o}$ instead. In this
paper, for different GLM models, we construct a different closed subset
$\mathcal{\bar{M}}$ of the interior $\mathcal{M}^{o}$. The projection operator
$\Pi_{\mathcal{\bar{M}}}(\cdot)$ is defined as
$\Pi_{\mathcal{\bar{M}}}(y_{i})=\arg\min_{\mu\in\mathcal{\bar{M}}}|y_{i}-\mu|$
for any variable $y_{i}\in\mathcal{Y}$, and
$[\Pi_{\mathcal{\bar{M}}}(y)]_{i}=\Pi_{\mathcal{\bar{M}}}(y_{i})$ for any
vector $y\in\mathbb{R}^{n}$. After projecting each $y_{i}$, we can approximate
$\tilde{\theta}$ via the least square method on $(X,[\nabla
A]^{-1}(\Pi_{\bar{\mathcal{M}}}(y)))$. In total we have

$\displaystyle\tilde{\theta}\approx(\frac{X^{T}X}{n})^{-1}\frac{X^{T}[\nabla
A]^{-1}(\Pi_{\bar{\mathcal{M}}}(y))}{n}.$ (3)

From (3) we can see it is sufficient for the $i$-th agent to share
$x_{i},y_{i}$ and the analyst computes $\mathbf{x}_{i}^{T}\mathbf{x}_{i}$ and
$\mathbf{x}_{i}^{T}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(y_{i}))$. To
achieve RJDP, by the basic mechanism in DP one direct approach is to add noise
to the term $(\frac{X^{T}X}{n})^{-1}\frac{X^{T}[\nabla
A]^{-1}(\Pi_{\bar{\mathcal{M}}}(y)}{n}$, where the magnitude should be
proportional to the sensitivity of the term. However, the challenge here is
that the sensitivity of the RHS term in (3) maybe unbounded with constant
probability. To be more concrete, there are two terms
$(\frac{X^{T}X}{n})^{-1}$ and $\frac{X^{T}[\nabla
A]^{-1}(\Pi_{\bar{\mathcal{M}}}(y)}{n}$. The sensitivity of the term
$(\frac{X^{T}X}{n})^{-1}$ is bounded with high probability due to Lemma 2.
However, the main issue is, as we only assume $y_{i}$ has bounded fourth
moment, the term $[\nabla A]^{-1}(\Pi_{\bar{\mathcal{M}}}(y)$ could be
unbounded with high probability (such as Poisson regression). And this could
cause the sensitivity of the RHS term in (3) be unbounded. To overcome the
challenge, here we will further conduct a clipping step, that is, we shrink
each $y_{i}$ into an bounded interval $[-\tau_{2},\tau_{2}]$ for some finite
positive value $\tau_{2}$:

$\displaystyle\widetilde{y}_{i}:=\mathrm{sgn}(y_{i})\min\\{|y_{i}|,\tau_{2}\\}.$
(4)

In total, our non-private estimator will be

$\displaystyle\hat{\theta}(D)=(X^{T}X)^{-1}X^{T}(\nabla
A)^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y})).$ (5)

Later we will show that with high probability the $\ell_{2}$-norm sensitivity
of (5) is bounded. Thus, we can add noise to $\hat{\theta}(D)$ to make it
private: $\hat{\theta}^{P}(D)=\hat{\theta}(D)+\text{noise}$. Since we assume
$\|\theta^{*}\|_{2}\leq\tau_{\theta}$, we need to project
$\hat{\theta}^{P}(D)$ onto a $\ell_{2}$-norm ball:

$\displaystyle\bar{\theta}^{P}(D)=\Pi_{\tau_{\theta}}(\hat{\theta}^{P}(D)),$
(6)

where
$\Pi_{\tau_{\theta}}(v)=\arg\min_{v^{\prime}\in{\mathbb{B}(\tau_{\theta})}}\|v^{\prime}-v\|^{2}_{2}$
and ${\mathbb{B}(\tau_{\theta})}$ is the closed $\ell_{2}$-norm ball with
radius $\tau_{\theta}$ and centers at the origin.

Previously we focused on the privacy and accuracy. In the following we will
consider the payment rule. The analyst should pay each agent strategically. If
the analyst knows the ground-truth after collecting the reports, she/he can
pay each agent according to how well the reports are aligned with the ground-
truth, e.g., by using $\ell_{2}$ norm as the distance metric for relatedness.
However, in our setting, the data is unverifiable, which means we do not have
ground truth as reference. To deal with this problem, we adopt the peer
prediction method [28, 12, 33, 1, 10], which extracts information from peers’
reports used for reference. In other words, each agent will receive higher
payment if her/his report is more consistent with the statistical model
estimated by using other agents’ reports. Since we assume that all data are
generated by the same statistical model, the peer prediction method
intuitively encourages truthful reporting if most agents report their data
truthfully. There are many ways to quantify the relatedness between each
agent’s reports and her/his peers’ reports, e.g., point-wise mutual
information [25], delta matrices [1], the Brier scoring rule [17]. Here we
adopt the rescaled Brier score rule. Formally, the analyst uses payment rule

$\displaystyle B_{a_{1},a_{2}}(p,q)=a_{1}-a_{2}(p-2pq+q^{2}),$ (7)

where $a_{1},a_{2}>0$ are parameters to be determined, $q$ is the prediction
of agent $i$’s response given her/his reports, and $p$ is the prediction of
agent $i$’s response given her/his feature vector and her/his peers’ reports.
Note that $B_{a_{1},a_{2}}(p,q)$ is a strictly concave function of $q$ which
is maximized at $q=p$, which means the prediction of agent $i$’s response
given her/his information is aligned with the one given peers’ information. In
GLMs, for agent $i$, since
$\mathbb{E}[y_{i}|\mathbf{x}_{i},\theta^{*}]=A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)$,
it is natural to let
$p=A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle)$ and
$q=A^{\prime}(\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|\hat{D}_{i})}[\theta]\rangle)$, where $\bar{\theta}^{P}(\hat{D}^{b})$
is the private estimator on a dataset $\hat{D}^{b}$ that does not include
$\hat{D}_{i}$, and $p(\theta|\hat{D}_{i})$ is the posterior distribution of
$\theta$ after the analyst receives $\hat{D}_{i}$.

Based on the previous analysis, we formalize our Mechanism 1. Note that
instead of using agents’ original data, we use the reported data (which may
contain manipulated responses) to obtain the estimator. In order to eliminate
dependency, we need to partition the dataset into two subgroups $\hat{D}^{0}$
and $\hat{D}^{1}$. To calculate the payment for each agent $i$ in group
$b\in\\{0,1\\}$, we use $\hat{D}^{1-b}$ to estimate $\theta^{*}$, and then use
the estimator and her/his feature vector $\mathbf{x}_{i}$ to predict the
response.

###  4.2 Theoretical Analysis

Before showing our results, we first list some notations for later use. By
Assumption 5 and Lemma 2, with probability at least $1-n^{-\Omega(1)}$, it
holds that $\|\mathbf{x}_{i}\|_{2}\leq C\sigma\sqrt{\log n}$ for all $i\in[n]$
with sufficiently large $C>0$. Denote $\tau_{1}=C\sigma\sqrt{\log n}$, then
$|\langle\mathbf{x}_{i},\theta^{*}\rangle|\leq\tau_{1}\tau_{\theta}$ for all
$i\in[n]$. The following notations correspond to the upper bounds of some
functions on some closed sets.

$\displaystyle\mathcal{M}^{\prime}:=\\{\mu:\mu=A^{\prime}(a),a\in[-\tau_{\theta}\tau_{1},\tau_{\theta}\tau_{1}]\\},$
$\displaystyle\kappa_{A,0}:=\max_{a\in\mathcal{M}^{\prime}\cup\bar{\mathcal{M}}}|[(A^{\prime})^{-1}]^{\prime}(a)|,\quad\kappa_{A,1}:=\max_{a\in\bar{\mathcal{M}}\cap[-\tau_{2},\tau_{2}]}|(A^{\prime})^{-1}(a)|,$
$\displaystyle\kappa_{A,2}:=\max_{a\in[-\tau_{\theta}\tau_{1},\tau_{\theta}\tau_{1}]}|A^{\prime\prime}(a)|,\quad
M_{A}:=\max_{a\in[-\tau_{\theta}\tau_{1},\tau_{\theta}\tau_{1}]}|A^{\prime}(a)|,$
$\displaystyle\varepsilon_{\bar{\mathcal{M}}}:=\max_{y_{i}\in\mathcal{Y}\cap[-\tau_{2},\tau_{2}]}|y_{i}-\Pi_{\bar{\mathcal{M}}}(y_{i})|,$

where $\tau_{2}$ is the threshold value in (4) and $\bar{\mathcal{M}}$ is the
closed set in (5). Note that all these parameters depend on the link function
$A$, which varies for different specific models. Thus, here we cannot assume
they are constants. In the following we will always assume Assumptions 1-5
hold.

1 Ask all agents to report their data $\hat{D}_{1},\cdots,\hat{D}_{n}$;

2 Randomly partition agents into two groups, with respective data pairs
$\hat{D}^{0},\hat{D}^{1}$;

3 Compute estimators
$\hat{\theta}(\hat{D}),\hat{\theta}(\hat{D}^{0}),\hat{\theta}(\hat{D}^{1})$
according to (5) on $\hat{D},\hat{D}^{0}$ and $\hat{D}^{1}$ respectively;

4 Compute estimator sensitivity $\Delta_{n},\Delta_{n/2}$, and set
differential privacy parameter $\varepsilon$;

5 Draw $v\in\mathbb{R}^{d}$ according to distribution
$p(v)\propto\exp(-\frac{\varepsilon}{\Delta_{n}}\|v\|_{2})$, and independently
draw $v_{0},v_{1}\in\mathbb{R}^{d}$ according to distribution
$p(v)\propto\exp(-\frac{\varepsilon}{\Delta_{n/2}}\|v\|_{2})$;

6 Add noise:
$\hat{\theta}^{P}(\hat{D})=\hat{\theta}(\hat{D})+v,\hat{\theta}^{P}(\hat{D}^{b})=\hat{\theta}({\hat{D}^{b}})+v_{b}$
for $b=0,1$;

7 Compute private estimators
$\bar{\theta}^{P}(\hat{D})=\Pi_{\tau_{\theta}}(\hat{\theta}^{P}(\hat{D}))$ and
$\bar{\theta}^{P}(\hat{D}^{b})=\Pi_{\tau_{\theta}}(\hat{\theta}^{P}(\hat{D}^{b}))$
for $b=0,1$;

Set parameters $a_{1},a_{2}$, and compute payments to each agent $i$: if agent
$i$’s is in group $1-b$, then he will receive payment
$\displaystyle\pi_{i}=B_{a_{1},a_{2}}\left(A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle),A^{\prime}(\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|\hat{D}_{i})}[\theta]\rangle)\right).$

Mechanism 1 Private Generalized Linear Models Mechanism

######  Lemma 3 (Sensitivity).

With probability at least $1-C_{1}n^{-\Omega(1)}$ the $\ell_{2}$-norm
sensitivity of $\hat{\theta}(D)$ computed by (5) satisfies

$\displaystyle\max_{D\sim
D^{\prime}}\|\hat{\theta}(D)-\hat{\theta}(D^{\prime})\|_{2}\leq\Delta_{n}=C_{0}\kappa_{A,1}\frac{\sqrt{d\log
n}}{\sqrt{n}},$

where $C_{0},C_{1}>0$ are constants. For later use, we denote
$\gamma_{n}=C_{1}n^{-\Omega(1)}$ as the failure probability.

######  Lemma 4 (Accuracy of the non-private estimator).

With probability at least $1-O(n^{-\Omega(1)})$ one has

$\displaystyle\|\hat{\theta}(D)-\theta^{*}\|_{2}\leq\lambda_{n}\sqrt{\frac{\log
n}{n}},$

where
$\lambda_{n}:=\tilde{O}({\kappa_{A,0}}(\sqrt{\kappa_{A,2}+\frac{1}{\tau_{2}^{2}}}+(M_{A}+\tau_{2})\sqrt[4]{\frac{1}{n}}+\varepsilon_{\bar{\mathcal{M}}})$
and the Big-$\tilde{O}$ notation omits the term of $\mathrm{Poly}(\log n)$.

The previous lemma indicates that the closed-form estimator (5) on the
original dataset is consistent. It is notable that its convergence rate may
not be as fast as $\tilde{O}(\sqrt{\frac{1}{n}})$ since $\lambda_{n}$ has
different growth rates in different specific models.

######  Theorem 1 (Privacy).

Mechanism 1 satisfies $(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$-random joint
differential privacy, where $\gamma_{n}=C_{1}n^{-\Omega(1)}$ is in Lemma 3.

######  Theorem 2 (Truthfulness).

Fix a privacy parameter $\varepsilon$, a participation goal $1-\alpha$ and a
desired confidence parameter $\beta$ in Definition 6. Then with probability at
least $1-\beta-O(n^{-\Omega(1)})$, the symmetric threshold strategy
$\sigma_{\tau_{\alpha,\beta}}$ is an $\eta$-Bayesian Nash equilibrium in
Mechanism 1 with

$\displaystyle\eta=\tilde{O}\left(a_{2}\kappa_{A,2}^{2}(\alpha^{2}\kappa^{2}_{A,1}{{{nd}}}+{\frac{\lambda^{2}_{n}}{n}}+\frac{\kappa^{2}_{A,1}d^{3}}{n\epsilon^{2}})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})\right),$

where $\gamma_{n}=C_{1}n^{-\Omega(1)}$ is in Lemma 3, $\lambda_{n}$ is in
Lemma 4, $a_{2}$ is in (7), $\tau_{\alpha,\beta}$ is in Definition 6 and
function $F$ is in Assumption 2.

######  Theorem 3 (Accuracy).

Fix a privacy parameter $\varepsilon$, a participation goal $1-\alpha$ and a
desired confidence parameter $\beta$ in Definition 6. Then under the symmetric
threshold strategy $\sigma_{\tau_{\alpha,\beta}}$, the output
$\bar{\theta}^{P}(\hat{D})$ of Mechanism 1 satisfies that with probability at
least $1-\beta-O(n^{-\Omega(1)})$,

$\displaystyle\mathbb{E}[\|\bar{\theta}^{P}(\hat{D})-\theta^{*}\|_{2}^{2}]\leq\tilde{O}\left(\alpha^{2}\kappa^{2}_{A,1}nd+\frac{\kappa^{2}_{A,1}{{d^{3}}}}{\varepsilon^{2}n}+{\frac{\lambda^{2}_{n}}{n}}\right),$

where $\lambda_{n}$ is in Lemma 4.

######  Theorem 4 (Individual rationality).

With probability at least $1-\beta-O(n^{-\Omega(1)})$, Mechanism 1 is
individually rational for all agents with cost coefficients
$c_{i}\leq\tau_{\alpha,\beta}$ as long as

$\displaystyle a_{1}\geq
a_{2}(M_{A}+3M_{A}^{2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+\gamma_{n/2})$

regardless of the reports from agents with cost coefficients above
$\tau_{\alpha,\beta}$, where $\gamma_{n}=C_{1}n^{-\Omega(1)}$ is in Lemma 3,
$a_{1},a_{2}$ are in (7) and $\lambda_{n}$ is in Lemma 4.

######  Theorem 5 (Budget).

With probability at least $1-\beta-O(n^{-\Omega(1)})$, the total expected
budget $\mathcal{B}:=\mathbb{E}[\sum_{i=1}^{n}\pi_{i}]$ required by the
analyst to run Mechanism 1 under threshold equilibrium strategy
$\sigma_{\tau_{\alpha,\beta}}$ satisfies

$\mathcal{B}\leq n(a_{1}+a_{2}(M_{A}+M_{A}^{2})),$

where $a_{1},a_{2}$ are in (7).

###  4.3 Implementation for Some Specific Models

In this section we will apply our framework to three canonical models in GLM:
linear regression, logistic regression and Poisson regression. Based on our
previous results, to provide appropriate design of computation and payment
scheme it is sufficient to construct $\bar{\mathcal{M}}$, specify the growth
rates of $\\{\kappa_{A,i}\\}_{i=0}^{2},M_{A},\varepsilon_{\bar{\mathcal{M}}}$,
and set suitable parameters including
$\alpha,\beta,\varepsilon,a_{1},a_{2},\tau_{2}$. In this section, we suppose
that the privacy cost dominated function $F(\varepsilon,\gamma)$ in Assumption
2 satisfies $F(\varepsilon,\gamma)=(1+\gamma)\varepsilon^{4}$ for simplicity.
It is notable that functions of $F$ can also be other functions. Moreover, for
some specific models we may allow more relaxed assumptions on the dependency
of $\epsilon$ and $\gamma$ in $F(\epsilon,\gamma)$.

####  4.3.1 Linear Regression

######  Example 1.

Consider the (Gaussian) linear regression model
$y=\langle\theta^{*},\mathbf{x}\rangle+\zeta$, where random variables
$\mathbf{x}$ and $\zeta$ are independent, and
$\zeta\sim\mathcal{N}(0,\sigma^{2})$. Then conditioned on $\mathbf{x}$, the
response $y$ follows the distribution
$p(y|\mathbf{x};\theta^{*})=\frac{1}{\sqrt{2\pi}\sigma}\exp\\{-\frac{(y-\langle\mathbf{x},\theta^{*}\rangle)^{2}}{2\sigma^{2}}\\}=\exp\\{\frac{y\langle\mathbf{x},\theta^{*}\rangle-\frac{1}{2}\langle\mathbf{x},\theta^{*}\rangle^{2}}{\sigma^{2}}-\frac{1}{2}(\frac{y^{2}}{\sigma^{2}}+\log(2\pi\sigma^{2}))\\}$.
Thus, $A(a)=\frac{1}{2}a^{2}$, $\phi=\sigma^{2}$, and
$c(y,\phi)=-\frac{1}{2}(\frac{y^{2}}{\sigma^{2}}+\log(2\pi\sigma^{2}))$.

######  Corollary 1.

For any $\delta\in(\frac{1}{4},\frac{1}{3})$ and $c>0$, we set
$\bar{\mathcal{M}}=\mathbb{R}$ ( we have
$\Pi_{\mathcal{\bar{M}}}(\widetilde{y}_{i})=\widetilde{y}_{i}$),
$\varepsilon=n^{-\delta}$, $\tau_{2}=n^{\frac{1-3\delta}{2}}$
$\alpha=\Theta(n^{-3\delta})$, $\beta=\Theta(n^{-c})$,
$a_{2}=O(n^{-4\delta})$,
$a_{1}=a_{2}(M_{A}+3M_{A}^{2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$.
Then the output of Mechanism 1 satisfies
$(O(n^{-\delta}),O(n^{-\Omega(1)}))$-RJDP. Moreover, with probability at least
$1-O(n^{-\Omega(1)})$, it holds that: 888Note that for clearness and to be
consistent with the previous results [11] here we omit the term of
$\text{Poly}(d)$, the same for all the other corollaries in this paper.

  * •

the symmetric threshold strategy $\sigma_{\tau_{\alpha,\beta}}$ is a
$\widetilde{O}(n^{-4\delta})$-Bayesian Nash equilibrium for a
$1-O(n^{-3\delta})$ fraction of agents to truthfully report their data;

  * •

the private estimator $\bar{\theta}^{P}(\hat{D})$ is
$\widetilde{O}(n^{-\delta})$-accurate;

  * •

it is individually rational for a $1-O(n^{-3\delta})$ fraction of agents to
participate in the mechanism;

  * •

the total expected budget required by the analyst is
$\widetilde{O}(n^{-4\delta+1})$.

######  Remark.

In [11], the authors also study the problem of truthful linear regression.
Specifically, they show that under the assumption of
$F(\epsilon,\gamma)=\epsilon^{2}$ it is possible to design an
$o(\frac{1}{\sqrt{n}})$-JDP mechanism that is an $o(\frac{1}{n})$-approximate
Bayes Nash equilibrium, $o(1)$-accurate, individually rational for $(1-o(1))$
fraction of truthful agents and needs $o(1)$ budgets. In comparison, here we
need stronger dependency on $\epsilon$ in the function $F$ and our algorithm
can only guarantee $o(\frac{1}{\sqrt[4]{n}})$-RJDP. However, it is notable
that $o(\frac{1}{\sqrt[4]{n}})$-RJDP is still in the extremely high privacy
regime as in practice $\epsilon=0.1-0.5$ is enough to preserve privacy. For
the dependency of $\epsilon$ in $F$, it is notable that [11] need to assume
$y_{i}$ is bounded where here we relax it to the case where it only has finite
fourth moment. Thus, their results are incomparable with ours.

####  4.3.2 Logistic Regression

######  Example 2.

Here the response $y\in\mathcal{Y}\equiv\\{-1,1\\}$. Let
$p:=\mathbb{P}(y=1|\mathbf{x}_{i},\theta^{*})$, then the conditional
distribution of $y$ can be written as
$p^{\frac{y+1}{2}}(1-p)^{\frac{1-y}{2}}=\exp\\{\frac{y}{2}\log\frac{p}{1-p}+\frac{1}{2}\log
p(1-p)\\}$. If we set
$\langle\mathbf{x}_{i},\theta^{*}\rangle=\frac{1}{2}\log\frac{p}{1-p}$, then
$p=\frac{e^{\langle\mathbf{x}_{i},\theta^{*}\rangle}}{e^{\langle\mathbf{x}_{i},\theta^{*}\rangle}+e^{-\langle\mathbf{x}_{i},\theta^{*}\rangle}}$
and the above distribution is equal to
$\exp\\{y\langle\mathbf{x}_{i},\theta^{*}\rangle-\log(\exp(-\langle\mathbf{x}_{i},\theta^{*}\rangle)+\exp(\langle\mathbf{x}_{i},\theta^{*}\rangle))\\}$.
Hence, here $A(a)=\log(e^{-a}+e^{a})$, $\phi=1$, and $c(y,\phi)=0$.

######  Corollary 2.

For any $\delta\in(\frac{1}{4},\frac{1}{2})$ and $c>0$, we set
$\bar{\mathcal{M}}=[-1+\varepsilon^{\prime},1-\varepsilon^{\prime}]$ for
$\varepsilon^{\prime}=2n^{-\delta}$ (we have
$\Pi_{\mathcal{\bar{M}}}(\widetilde{y}_{i})=\widetilde{y}_{i}(1-2n^{-\delta})$),
$\varepsilon=n^{-\delta}$, $\tau_{2}=1$, $\alpha=\Theta(n^{-3\delta})$,
$\beta=\Theta(n^{-c})$, $a_{2}=O(n^{-4\delta})$,
$a_{1}=a_{2}(M_{A}+3M_{A}^{2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$.
Then the output of Mechanism 1 satisfies
$(O(n^{-\delta}),O(n^{-\Omega(1)}))$-RJDP. And with probability at least
$1-O(n^{-\Omega(1)})$, it holds that:

  * •

the symmetric threshold strategy $\sigma_{\tau_{\alpha,\beta}}$ is a
$\widetilde{O}(n^{-4\delta})$-Bayesian Nash equilibrium for a
$1-O(n^{-3\delta})$ fraction of agents to truthfully report their data;

  * •

the private estimator $\bar{\theta}^{P}(\hat{D})$ is
$\widetilde{O}(n^{-1+2\delta})$-accurate;

  * •

it is individually rational for a $1-O(n^{-3\delta})$ fraction of agents to
participate in the mechanism;

  * •

the total expected budget required by the analyst is
$\widetilde{O}(n^{-4\delta+1})$.

####  4.3.3 Poisson Regression

######  Example 3.

For a count-valued response $y\in\mathcal{Y}\equiv\\{0,1,2,\cdots\\}$, suppose
its distribution is given by $p(y)=\frac{\lambda^{y}}{y!}e^{-\lambda}$ with
parameter $\lambda>0$. If we set
$\langle\mathbf{x}_{i},\theta^{*}\rangle=\log\lambda$, then the distribution
is equal to
$\exp\\{y\langle\mathbf{x}_{i},\theta^{*}\rangle-\exp(\langle\mathbf{x}_{i},\theta^{*}\rangle)-\log(y!)\\}$.
Thus, $A(a)=e^{a}$, $\phi=1$, and $c(y,\phi)=0$.

######  Corollary 3.

For any $\delta\in(\frac{1}{4},\frac{1}{3})$ and $c>0$, we set
$\bar{\mathcal{M}}=[n^{-\delta},+\infty)$ (we have
$\Pi_{\mathcal{\bar{M}}}(\widetilde{y}_{i})=\mathbf{1}_{\\{\widetilde{y}_{i}=0\\}}n^{-\delta}+\mathbf{1}_{\\{\widetilde{y}_{i}\neq
0\\}}\widetilde{y}_{i}$), $\varepsilon=n^{-3\delta}$,
$\tau_{2}=\Theta(n^{\frac{1}{4}})$, $\alpha=\Theta(n^{-3\delta})$,
$\beta=\Theta(n^{-c})$, $a_{2}=O(n^{-6\delta})$,
$a_{1}=a_{2}(M_{A}+3M_{A}^{2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$.
Then the output of Mechanism 1 satisfies
$(O(n^{-3\delta}),O(n^{-\Omega(1)}))$-RJDP. And with probability at least
$1-O(n^{-\Omega(1)})$, it holds that

  * •

the symmetric threshold strategy $\sigma_{\tau_{\alpha,\beta}}$ is a
$\widetilde{O}(n^{-4\delta})$-Bayesian Nash equilibrium for a
$1-O(n^{-3\delta})$ fraction of agents to truthfully report their data;

  * •

the private estimator $\bar{\theta}^{P}(\hat{D})$ is
$\widetilde{O}(n^{-1+3\delta})$-accurate;

  * •

it is individually rational for a $1-O(n^{-3\delta})$ fraction of agents to
participate in the mechanism;

  * •

the total expected budget required by the analyst is
$\widetilde{O}(n^{-4\delta+1})$.

##  5 Heavy-tailed Case for Linear Regression

In the previous section, we studied GLMs with sub-Gaussian covariates.
However, the sub-Gaussian assumption is quite strong in practice. For example,
it has been widely known that large-scale imaging datasets in biological
studies and macroeconomic variables are corrupted by heavy-tailed noises due
to limited measurement precision [15, 4], which reveal that heavy-tailed
distribution is a stylized feature of high-dimensional data. Thus, one natural
question is whether we can extend the setting to the case where the data
distribution is heavy-tailed. In this section, we focus on the linear
regression and leave the generalized linear models as future work.
Specifically, we consider the case where both covariate vectors
$\mathbf{x}_{i}$ and responses $y_{i}$ only have bounded fourth moments. It is
notable that Assumption 6 is commonly used in the previous study in robust
statistics [15, 22].

######  Assumption 6.

We assume that $x_{1},x_{2},\cdots,x_{n}$ are i.i.d. and for each $x_{i}$
there exist constants $R_{1},R_{2}=O(1)$ such that
$\sup_{\nu\in\mathcal{S}^{d-1}}\mathbb{E}(\nu^{T}\mathbf{x}_{i})^{4}\leq
R_{1}$ for any unit vectors $\nu\in\mathbb{R}^{d}$ and
$\mathbb{E}[y_{i}^{4}]\leq R_{2}$. Moreover, the covariance matrix $\Sigma$ of
$\mathbf{x}_{i}$ satisfies that $\|\Sigma\|_{\infty}\geq\kappa_{\infty}$ and
$\|\Sigma\|_{2}\geq\kappa_{2}$ for some constants
$\kappa_{\infty},\kappa_{2}=\Theta(1)$, i.e., $\forall w\in\mathbb{R}^{d}$,
$\|\Sigma w\|_{\infty}\geq\kappa_{\infty}\|w\|_{\infty}$ and $\|\Sigma
w\|_{2}\geq\kappa_{2}\|w\|_{2}$. We also only focus on the low dimension case
where $n=\tilde{\Omega}(d)$.

Before showing our method, we first discuss why $\hat{\theta}(D)$ in (5) in
the non-private case does not work in this setting. Recall that in the case of
linear model, as shown in Section 4.3.1 we have
$\hat{\theta}(D)=(X^{T}X)^{-1}X^{T}\tilde{y}$ in (5). However, as now each
$\mathbf{x}_{i}$ is heavy-tailed, the previous Lemma 3 on the $\ell_{2}$-norm
sensitivity will not hold as the terms $X^{T}X$ and $X^{T}\tilde{y}$ will not
be concentrated with high probability. Inspired by [15], similar to
$\tilde{y}_{i}$, here we also need to preprocess each $x_{i}$. Specifically,
we apply a similar clipping operation as in the previous section to $y_{i}$
and an $l_{4}$-norm shrinkage operation to $\mathbf{x}_{i}$, i.e., let
$\widetilde{\mathbf{x}}_{i}$ satisfies
$\widetilde{\mathbf{x}}_{i}=\min\\{\|\mathbf{x}_{i}\|_{4},\tau_{1}\\}\mathbf{x}_{i}/\|\mathbf{x}_{i}\|_{4}$
and $\widetilde{y}_{i}=\mathrm{sgn}(y_{i})\min\\{|y_{i}|,\tau_{2}\\}$ for each
$i\in[n]$, where $\tau_{1},\tau_{2}>0$ are predetermined threshold values.
Since now each $\tilde{x}_{i}$ and $\tilde{y_{i}}$ are bounded, the terms of
$\tilde{X}^{T}\tilde{X}$ and $\tilde{X}^{T}\tilde{y}$ will be concentrated
with high probability by Hoeffding’s inequality. In total, now the non-private
estimator becomes to

$\displaystyle\hat{\theta}(D)=(\widetilde{X}^{T}\widetilde{X})^{-1}\widetilde{X}^{T}\widetilde{y}.$
(8)

Similar to the sub-Gaussian case we then project
$\hat{\theta}^{P}(D)=\hat{\theta}(D)+\text{noise}$ onto the $\ell_{2}$-norm
ball: $\bar{\theta}^{P}(D)=\Pi_{\tau_{\theta}}(\hat{\theta}^{P}(D)).$ In the
following we show the $\ell_{2}$-norm sensitivity and the accuracy of
$\hat{\theta}(D)$.

######  Lemma 5 (Sensitivity).

If we set $\tau_{1}=\Theta((n/\log n)^{1/4})$ and $\tau_{2}=\Theta((n/\log
n)^{1/8})$, then with probability at least $1-C_{1}n^{-\Omega(1)}$, the
$\ell_{2}$-norm sensitivity of $\hat{\theta}(D)$ computed from (8) satisfies

$\displaystyle\max_{D\sim
D^{\prime}}\|\hat{\theta}(D)-\hat{\theta}(D^{\prime})\|_{2}\leq\Delta_{n}=C_{0}d^{\frac{3}{4}}(\frac{\log
n}{n})^{\frac{1}{8}},$

where $C_{0},C_{1}>0$ are constants.

######  Lemma 6 (Accuracy of the non-private estimator).

By setting $\tau_{1},\tau_{2}$ as in Lemma 5, with probability at least
$1-O(n^{-\Omega(1)})$, one has with some constant $C>0$:

$\|\hat{\theta}(D)-\theta^{*}\|_{2}\leq Cd(\frac{\log n}{n})^{\frac{1}{4}}.$

######  Remark.

Compared with the previous linear regression in the sub-Gaussian case, we can
see due to the clipping parameters $\tau_{1}$ and $\tau_{2}$, both sensitivity
and accuracy become larger. Secondly, besides the $\ell_{4}$-norm shrinkage
operator in (8), another way is performing the element-wise shrinkage operator
to each $x_{i}$ [22], i.e., $\widetilde{\mathbf{x}}_{i}$ satisfies
$\widetilde{x}_{ij}=\mathrm{sgn}(x_{ij})\min\\{|x_{ij}|,\tau_{1}\\}$ for each
$i\in[n],j\in[d]$. However, by a similar proof as in Lemma 5 one can see the
$\ell_{2}$-norm sensitivity of $\hat{\theta}(D)$ based on this shrinkage
operation will be $\tilde{O}(d^{\frac{3}{2}}(\frac{1}{n})^{\frac{1}{8}})$,
which is larger than the bound in Lemma 5. Thirdly, while there are some work
also uses different shrinkage operators (such as $\ell_{2}$-norm shrinkage or
element-wise shrinkage) to variants statistical estimation problems [22, 15],
here we use the $\ell_{4}$-norm shrinkage and the thresholds
$\tau_{1},\tau_{2}$ are not equal, which are quite different with the previous
approaches.

Based on the previous two lemmas and the similar idea as in the sub-Gaussian
case, we propose Mechanism 2. Specifically, we have the following results
under Assumptions 1-4 and 6.

######  Theorem 6 (Privacy).

Mechanism 2 satisfies $(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$-random joint
differential privacy, where $\gamma_{n}=C_{1}n^{-\Omega(1)}$ is the failure
probability in Lemma 5.

######  Theorem 7 (Truthfulness).

Fix a privacy parameter $\varepsilon$, a participation goal $1-\alpha$ and a
desired confidence parameter $\beta$ in Definition 6. Then with probability at
least $1-\beta-O(n^{-\Omega(1)})$, the symmetric threshold strategy
$\sigma_{\tau_{\alpha,\beta}}$ is an $\eta$-approximate Bayesian Nash
equilibrium in Mechanism 2 with

$\displaystyle\eta=\widetilde{O}(a_{2}(\alpha^{2}d^{2}n^{\frac{9}{4}}+d^{4}n^{\frac{1}{4}}\varepsilon^{-2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})).$

######  Theorem 8 (Accuracy).

Fix a privacy parameter $\varepsilon$, a participation goal $1-\alpha$ and a
desired confidence parameter $\beta$ in Definition 6. Then under the symmetric
threshold strategy $\sigma_{\tau_{\alpha,\beta}}$, the output
$\bar{\theta}^{P}(\hat{D})$ of Mechanism 2 satisfies that with probability at
least $1-\beta-O(n^{-\Omega(1)})$,

$\displaystyle\mathbb{E}\|\bar{\theta}^{P}(\hat{D})-\theta^{*}\|_{2}^{2}=\widetilde{O}(\alpha^{2}d^{\frac{3}{2}}n^{\frac{7}{4}}+d^{\frac{7}{2}}n^{-\frac{1}{4}}\varepsilon^{-2}).$

1 Ask all agents to report their data $\hat{D}_{1},\cdots,\hat{D}_{n}$;

2 Randomly partition agents into two groups, with respective data pairs
$\hat{D}^{0},\hat{D}^{1}$;

3 Compute estimators
$\hat{\theta}(\hat{D}),\hat{\theta}(\hat{D}^{0}),\hat{\theta}(\hat{D}^{1})$
according to (8) with $\tau_{1}$ and $\tau_{2}$ in Lemma 5;

4 Compute the sensitivity upper bounds $\Delta_{n},\Delta_{n/2}$ in Lemma 5,
and set differential privacy parameter $\varepsilon$;

5 Draw $v\in\mathbb{R}^{d}$ according to distribution
$p(v)\propto\exp(-\frac{\varepsilon}{\Delta_{n}}\|v\|_{2})$, and independently
draw $v_{0},v_{1}\in\mathbb{R}^{d}$ according to distribution
$p(v)\propto\exp(-\frac{\varepsilon}{\Delta_{n/2}}\|v\|_{2})$;

6 Add noise:
$\hat{\theta}^{P}(\hat{D})=\hat{\theta}(\hat{D})+v,\hat{\theta}^{P}(\hat{D}^{b})=\hat{\theta}({\hat{D}^{b}})+v_{b}$
for $b=0,1$;

7 Compute private estimators
$\bar{\theta}^{P}(\hat{D})=\Pi_{\tau_{\theta}}(\hat{\theta}^{P}(\hat{D}))$ and
$\bar{\theta}^{P}(\hat{D}^{b})=\Pi_{\tau_{\theta}}(\hat{\theta}^{P}(\hat{D}^{b}))$
for $b=0,1$;

Set parameters $a_{1},a_{2}$, and compute payments to each agent $i$: if agent
$i$’s is in group $1-b$, then he will receive payment
$\displaystyle\pi_{i}=B_{a_{1},a_{2}}\left(\langle\mathbf{\widetilde{x}}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle,\langle\mathbf{\widetilde{x}}_{i},\mathbb{E}_{\theta\sim
p(\theta|\hat{D}_{i})}[\theta]\rangle\right).$

Mechanism 2 Private Heavy-tailed Linear Model Mechanism

######  Theorem 9 (Individual rationality).

With probability at least $1-\beta-O(n^{-\Omega(1)})$, Mechanism 2 is
individually rational for all agents with cost coefficients
$c_{i}\leq\tau_{\alpha,\beta}$ as long as

$\displaystyle a_{1}\geq
a_{2}(d^{\frac{1}{4}}\tau_{1}\tau_{\theta}+3d^{\frac{1}{2}}\tau_{1}^{2}\tau_{\theta}^{2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2}),$

regardless of the reports from agents with cost coefficients above
$\tau_{\alpha,\beta}$.

######  Theorem 10 (Budget).

The total expected budget $\mathcal{B}:=\mathbb{E}[\sum_{i=1}^{n}\pi_{i}]$
required by the analyst to run Mechanism 2 under threshold equilibrium
strategy $\sigma_{\tau_{\alpha,\beta}}$ satisfies

$\displaystyle\mathcal{B}=\widetilde{O}(n(a_{2}\sqrt{dn}+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2}))).$

######  Corollary 4.

Suppose that $F(\varepsilon,\gamma)=(1+\gamma)\varepsilon^{9}$. For any
$\delta\in(\frac{1}{9},\frac{1}{8})$ and $c>0$, we set
$\bar{\mathcal{M}}=\mathbb{R}$, $\tau_{1}=\Theta((n/\log n)^{1/4})$,
$\tau_{2}=\Theta((n/\log n)^{1/8})$, $\varepsilon=n^{-\delta}$,
$\alpha=\Theta(n^{-1+\delta})$, $\beta=\Theta(n^{-c})$,
$a_{2}=n^{-\frac{1}{2}-9\delta}$,
$a_{1}=a_{2}(d^{\frac{1}{4}}\tau_{1}\tau_{\theta}+3d^{\frac{1}{2}}\tau_{1}^{2}\tau_{\theta}^{2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$.
Then the output of Mechanism 2 satisfies
$(O(n^{-\delta}),O(n^{-\Omega(1)}))$-random joint differential privacy. And
with probability at least $1-O(n^{-\Omega(1)})$, it holds that

  * •

the symmetric threshold strategy $\sigma_{\tau_{\alpha,\beta}}$ is a
$\widetilde{O}(n^{-9\delta})$-Bayesian Nash equilibrium for a
$1-O(n^{-1+\delta})$ fraction of agents to truthfully report their data;

  * •

the private estimator $\bar{\theta}^{P}(\hat{D})$ is
$\widetilde{O}(n^{-\frac{1}{4}+2\delta})$-accurate;

  * •

it is individually rational for a $1-O(n^{-1+\delta})$ fraction of agents to
participate in the mechanism;

  * •

the total expected budget required by the analyst is
$\widetilde{O}(n^{-9\delta+1})$.

######  Remark.

It is worth mentioning that throughout the whole paper, the privacy cost
function $f_{i}(c_{i},\epsilon,\gamma)$ can change with respect to the
distortion in the report, i.e. $|y_{i}-\hat{y}_{i}|$. But we do not write
explicitly this relation, since it does not matter in reaching our results
above. What really matters is the assumption on upper bounding the privacy
cost function (see Assumption 2). And we only consider the case where an agent
can reduce his/her privacy cost at most by misreporting the data (see the last
paragraph in the proof of Theorem 2). However, the lack of a closer look at
the distribution of an agent’s utility under different reporting strategies
prevents us concluding that each agent will have the highest utility in
average if she truthfully reports the data (We only establish that the
symmetric threshold strategy is an $\eta$ Bayesian Nash equilibrium, which
means an agent may increase $\eta$ utility by misreporting the data). Thus, we
need to further study how the payment and privacy cost vary under different
reporting strategies to obtain a more satisfactory result.

## Acknowledgement

Di Wang is supported in part by the baseline funding BAS/1/1689-01-01, funding
from the CRG grand URF/1/4663-01-01, FCC/1/1976-49-01 from CBRC and funding
from the AI Initiative REI/1/4811-10-01 of King Abdullah University of Science
and Technology (KAUST). He is also supported by the funding of the SDAIA-KAUST
Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUST
AI). Jinyan Liu is partially supported by National Natural Science Foundation
of China (NSFC Grant No.62102026).

## References

  * [1] Arpit Agarwal, Debmalya Mandal, David C Parkes, and Nisarg Shah.  Peer prediction with heterogeneous users.  ACM Transactions on Economics and Computation (TEAC), 8(1):1–34, 2020.
  * [2] Nestor Alvaro, Mike Conway, Son Doan, Christoph Lofi, John Overington, and Nigel Collier.  Crowdsourcing twitter annotations to identify first-hand experiences of prescription drug use.  Journal of biomedical informatics, 58:280–287, 2015.
  * [3] Raef Bassily, Cristóbal Guzmán, and Michael Menart.  Differentially private stochastic optimization: New results in convex and non-convex settings.  Advances in Neural Information Processing Systems, 34, 2021.
  * [4] Atanu Biswas, Sujay Datta, Jason P Fine, and Mark R Segal.  Statistical advances in the biomedical science.  Wiley Online Library, 2007.
  * [5] T Tony Cai, Yichen Wang, and Linjun Zhang.  The cost of privacy in generalized linear models: Algorithms and minimax lower bounds.  arXiv preprint arXiv:2011.03900, 2020.
  * [6] Yang Cai, Constantinos Daskalakis, and Christos Papadimitriou.  Optimum statistical estimation with strategic data sources.  In Conference on Learning Theory, pages 280–296. PMLR, 2015.
  * [7] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate.  Differentially private empirical risk minimization.  Journal of Machine Learning Research, 12(3), 2011.
  * [8] Yiling Chen, Yang Liu, and Chara Podimata.  Learning strategy-aware linear classifiers.  Advances in Neural Information Processing Systems, 33:15265–15276, 2020.
  * [9] Yiling Chen, Chara Podimata, Ariel D Procaccia, and Nisarg Shah.  Strategyproof linear regression in high dimensions.  In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 9–26, 2018.
  * [10] Yiling Chen, Yiheng Shen, and Shuran Zheng.  Truthful data acquisition via peer prediction.  Advances in Neural Information Processing Systems, 33:18194–18204, 2020.
  * [11] Rachel Cummings, Stratis Ioannidis, and Katrina Ligett.  Truthful linear regression.  In Conference on Learning Theory, pages 448–483. PMLR, 2015.
  * [12] Anirban Dasgupta and Arpita Ghosh.  Crowdsourced judgement elicitation with endogenous proficiency.  In Proceedings of the 22nd international conference on World Wide Web, pages 319–330, 2013.
  * [13] 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\.
  * [14] Alireza Fallah, Ali Makhdoumi, Azarakhsh Malekian, and Asuman Ozdaglar.  Optimal and differentially private data acquisition: Central and local mechanisms.  arXiv preprint arXiv:2201.03968, 2022.
  * [15] Jianqing Fan, Weichen Wang, and Ziwei Zhu.  A shrinkage principle for heavy-tailed data: High-dimensional robust low-rank matrix recovery.  Annals of statistics, 49(3):1239, 2021.
  * [16] 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 on electronic commerce, pages 568–585, 2012.
  * [17] Arpita Ghosh, Katrina Ligett, Aaron Roth, and Grant Schoenebeck.  Buying private data without verification.  In Proceedings of the fifteenth ACM conference on Economics and computation, pages 931–948, 2014.
  * [18] Arpita Ghosh and Aaron Roth.  Selling privacy at auction.  In Proceedings of the 12th ACM conference on Electronic commerce, pages 199–208, 2011.
  * [19] Rob Hall, Alessandro Rinaldo, and Larry Wasserman.  Random differential privacy.  arXiv preprint arXiv:1112.2680, 2011.
  * [20] Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, and Mary Wootters.  Strategic classification.  In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pages 111–122, 2016.
  * [21] Justin Hsu, Zhiyi Huang, Aaron Roth, Tim Roughgarden, and Zhiwei Steven Wu.  Private matchings and allocations.  SIAM Journal on Computing, 45(6):1953–1984, 2016.
  * [22] Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang.  High dimensional differentially private stochastic optimization with heavy-tailed data.  In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 227–236, 2022.
  * [23] Prateek Jain and Abhradeep Guha Thakurta.  (near) dimension independent risk bounds for differentially private learning.  In International Conference on Machine Learning, pages 476–484. PMLR, 2014.
  * [24] 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.
  * [25] Yuqing Kong and Grant Schoenebeck.  Water from two rocks: Maximizing the mutual information.  In Proceedings of the 2018 ACM Conference on Economics and Computation, pages 177–194, 2018.
  * [26] Yuqing Kong, Grant Schoenebeck, Biaoshuai Tao, and Fang-Yi Yu.  Information elicitation mechanisms for statistical estimation.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 2095–2102, 2020.
  * [27] Katrina Ligett and Aaron Roth.  Take it or leave it: Running a survey when privacy comes at a cost.  In International workshop on internet and network economics, pages 378–391. Springer, 2012.
  * [28] Nolan Miller, Paul Resnick, and Richard Zeckhauser.  Eliciting informative feedback: The peer-prediction method.  Management Science, 51(9):1359–1373, 2005.
  * [29] 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.
  * [30] Lennart Nordberg.  Generalized linear modeling of sample survey data.  Journal of Official Statistics, 5(3):223–239, 1989.
  * [31] Benjamin IP Rubinstein and Francesco Aldà.  Pain-free random differential privacy with sensitivity sampling.  In International Conference on Machine Learning, pages 2950–2959. PMLR, 2017.
  * [32] Greg Schwemer.  General linear models for multicenter clinical trials.  Controlled clinical trials, 21(1):21–29, 2000.
  * [33] Victor Shnayder, Arpit Agarwal, Rafael Frongillo, and David C Parkes.  Informed truthfulness in multi-task peer prediction.  In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 179–196, 2016.
  * [34] 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 2638–2646. PMLR, 2021.
  * [35] Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices.  arXiv preprint arXiv:1011.3027, 2010.
  * [36] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.
  * [37] Martin J Wainwright, Michael I Jordan, et al.  Graphical models, exponential families, and variational inference.  Foundations and Trends® in Machine Learning, 1(1–2):1–305, 2008.
  * [38] 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.

##  Appendix A Supporting lemmas

######  Lemma 7.

For any $w,w^{\prime}\in\mathbb{R}^{d}$ and closed convex set
$\mathcal{C}\subseteq\mathbb{R}^{d}$ we have

$\|\Pi_{\mathcal{C}}(w)-\Pi_{\mathcal{C}}(w^{\prime})\|_{2}\leq\|w-w^{\prime}\|_{2},$

where $\Pi_{\mathcal{C}}$ is the projection operation onto the set
$\mathcal{C}$, i.e.,
$\Pi_{\mathcal{C}}(v)=\arg\min_{u\in\mathcal{C}}\|u-v\|_{2}$.

######  Lemma 8 ([36]).

Let $X_{1},\cdots,X_{n}$ be $n$ independent random variables such that
$X_{i}\sim\mathrm{subG}(\sigma^{2})$. Then for any $a\in\mathbb{R}^{n},t>0$,
we have

$\displaystyle\mathbb{P}(|\sum_{i=1}^{n}a_{i}X_{i}|>t)\leq
2\exp(-\frac{t^{2}}{2\sigma^{2}\|a\|_{2}^{2}}).$

######  Lemma 9 (Hoeffding’s inequality [36]).

Let $X_{1},\cdots,X_{n}$ be independent random variables bounded by the
interval $[a,b]$. Then, for any $t>0$,

$\displaystyle\mathbb{P}(|\frac{1}{n}\sum_{i=1}^{n}X_{i}-\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[X_{i}]|>t)\leq
2\exp(-\frac{2nt^{2}}{(b-a)^{2}}).$

######  Lemma 10 (Bernstein’s inequality [36]).

Let $X_{1},X_{2},\cdots,X_{n}$ be independent centered bounded random
variables, i.e. $|X_{i}|\leq M$ and $\mathbb{E}[X_{i}]=0$, with variance
$\mathbb{E}[X_{i}^{2}]=\sigma^{2}$. Then, for any $t>0$,

$\displaystyle\mathbb{P}(|\sum_{i=1}^{n}X_{i}|>\sqrt{2n\sigma^{2}t}+\frac{2Mt}{3})\leq
2e^{-t}.$

######  Lemma 11 (Billboard lemma [21]).

Let $\mathcal{M}:\mathcal{D}^{n}\to\mathcal{O}$ be an
$\varepsilon$-differential private mechanism. Consider a set of $n$ functions
$\pi_{i}:\mathcal{D}\times\mathcal{O}\to\mathcal{R}$, for $i\in[n]$. Then the
mechanism
$\mathcal{M}^{\prime}:\mathcal{D}^{n}\to\mathcal{O}\times\mathcal{R}^{n}$ that
computes $r=\mathcal{M}(D)$ and outputs
$\mathcal{M}^{\prime}(D)=(r,\pi_{1}(D_{1},r),\cdots,\pi_{n}(D_{n},r))$, where
$D_{i}$ is the agent $i$’s data, is $\varepsilon$-differential private.

######  Lemma 12.

If $v\in\mathbb{R}^{d}$ is drawn from the distribution with probability
density function $p(v)\propto\exp(-\frac{\varepsilon}{\Delta}\|v\|_{2})$, then
$\mathbb{E}[v]=0$,
$\mathbb{E}[\|v\|_{2}^{2}]=d(d+1)(\frac{\Delta}{\varepsilon})^{2}$,
$\mathbb{E}[\|v\|_{2}]=\frac{d\Delta}{\varepsilon}$.

######  Lemma 13.

Let $\hat{\theta}(D)$ and $\hat{\theta}(D^{\prime})$ be the estimators on two
fixed datasets $D,D^{\prime}$ that differ on at most $k$ entries. Suppose that
with probability at least $1-\gamma_{n}$, the sensitivity of $\hat{\theta}(D)$
is upper bounded by $\Delta_{n}$. Then we have with probability at least
$1-k\gamma_{n}$, it holds that

$\displaystyle\|\hat{\theta}(D)-\hat{\theta}(D^{\prime})\|_{2}\leq
k\Delta_{n}.$

######  Lemma 14 (Bound on threshold $\tau_{\alpha,\beta}$).

Under the Assumption 4,
$\tau_{\alpha,\beta}\leq\frac{1}{\lambda}\log\frac{1}{\alpha\beta}$.

######  Lemma 15 (Largest singular value of sub-Gaussian matrices [35]).

Let $A$ be an $n\times d$ matrix whose rows $A_{i}$ are independent sub-
Gaussian isotropic (i.e. $\mathbb{E}[A_{i}A_{i}^{T}]=I$) random vectors in
$\mathbb{R}^{d}$. Then for every $t\geq 0$, with probability at least
$1-2e^{-c_{0}t^{2}}$ one has

$\displaystyle\|A\|_{2}\leq\sqrt{n}+C_{0}\sqrt{d}+t.$

where $c_{0},C_{0}\geq 0$ are universal constants.

######  Lemma 16 (Covariance estimation for sub-Gaussian distribution [35]).

Assume that $X$ be an $n\times d$ matrix whose rows $\mathbf{x}_{i}^{T}$ are
independent sub-Gaussian random vectors in $\mathbb{R}^{n}$ with covariance
matrix $\Sigma$. Then for every $s\geq 0$, with probability at least
$1-2\exp(-c_{1}s^{2})$, one has

$\displaystyle\|\frac{X^{T}X}{n}-\Sigma\|_{2}\leq\max(\delta,\delta^{2})\quad\text{where}\quad\delta=C_{1}\sqrt{\frac{d}{n}}+\frac{s}{\sqrt{n}},$

where $c_{1},C_{1}>0$ are universal constants.

######  Lemma 17 (Covariance estimation for heavy-tailed distribution).

Assume that $X$ be an $n\times d$ matrix whose rows $\mathbf{x}_{i}^{T}$ are
independent random vectors in $\mathbb{R}^{d}$ with finite fourth moment,
i.e., $\sup_{\nu\in\mathcal{S}^{d-1}}\mathbb{E}(\nu^{T}\mathbf{x}_{i})^{4}\leq
R<\infty$, where $\mathcal{S}^{d-1}$ is a $d$ dimensional unit sphere. Denote
the covariance matrix as
$\Sigma:=\mathbb{E}[\mathbf{x}_{i}\mathbf{x}_{i}^{T}]$. For any $\delta>0$,
let $\tau_{1}=\Theta((nR/(\delta\log n))^{1/4})$ and
$\widetilde{\mathbf{x}}_{i}=\min\\{\|\mathbf{x}_{i}\|_{4},\tau_{1}\\}\mathbf{x}_{i}/\|\mathbf{x}_{i}\|_{4}$
for each $i\in[n]$. Then, with probability at least $1-dn^{-C\delta}$ it holds
that

$\displaystyle\|\frac{\widetilde{X}^{T}\widetilde{X}}{n}-\Sigma\|_{2}\leq
2\sqrt{\frac{\delta Rd\log n}{n}},$

where constant $C>0$ is a universal constant.

##  Appendix B Proofs of Supporting Lemmas

###### Proof of Lemma 7.

Denote $b=\Pi_{\mathcal{C}}(w)$ and
$b^{\prime}=\Pi_{\mathcal{C}}(w^{\prime})$. Since $b$ and $b^{\prime}$ are in
$\mathcal{C}$, so the segment $bb^{\prime}$ is contained in $\mathcal{C}$,
thus we have for all $t\in[0,1],\|(1-t)b+tb^{\prime}-w\|_{2}\geq\|b-w\|_{2}$.
Thus

$0\leq\frac{d}{dt}\|tb+(1-t)b^{\prime}-w\|_{2}^{2}|_{t=0}=2\langle
b^{\prime}-b,b-w\rangle$

Similarly, we have $\langle b-b^{\prime},b^{\prime}-w^{\prime}\rangle\geq 0$.
Now consider the function
$D(t)=\|(1-t)b+tw-(1-t)b^{\prime}-tw^{\prime}\|_{2}^{2}=\|b-b^{\prime}+t(w-w^{\prime}+b^{\prime}-b)\|_{2}^{2}$,
which is a quadratic function in $t$. And by the previous two inequalities we
have $D^{\prime}(0)=2\langle b-b^{\prime},w-w^{\prime}+b^{\prime}-b\rangle\geq
0$. Thus $D(\cdot)$ is a increasing function on $[0,\infty)$, thus $D(1)\geq
D(0)$ which means $\|w-w^{\prime}\|_{2}\geq\|b-b^{\prime}\|_{2}$. ∎

######  Proof of Lemma 12.

Write $p(v)=\frac{1}{Z}\exp(-\frac{\varepsilon}{\Delta}\|v\|_{2})$, in which
$Z$ is a constant such that $\int_{\mathbb{R}^{d}}p(v)\,\textrm{d}{v}=1$. Then

$\displaystyle
Z=\int_{\mathbb{R}^{d}}\exp(-\frac{\varepsilon}{\Delta}\|v\|_{2})\,\textrm{d}{v}=\int_{0}^{\infty}\exp(-\frac{\varepsilon}{\Delta}r)A_{d}r^{d-1}\,\textrm{d}{r}=A_{d}(d-1)!(\frac{\Delta}{\varepsilon})^{d},$

where $A_{d}$ is the ”area” of boundary of $d$-dimensional unit ball and the
last inequality follows from integration by parts for $d-1$ times. Similarly,

$\displaystyle\mathbb{E}[\|v\|_{2}^{2}]=\int_{\mathbb{R}^{d}}\frac{1}{Z}\exp(-\frac{\varepsilon}{\Delta}\|v\|_{2})\|v\|_{2}^{2}\,\textrm{d}{v}$
$\displaystyle=\int_{0}^{\infty}\frac{1}{Z}\exp(-\frac{\varepsilon}{\Delta}r)A_{d}r^{d+1}\,\textrm{d}{r}$
$\displaystyle=\frac{1}{Z}A_{d}(d+1)!(\frac{\Delta}{\varepsilon})^{d+2}=d(d+1)(\frac{\Delta}{\varepsilon})^{2},$

and $\mathbb{E}[\|v\|]=\frac{d\Delta}{\varepsilon}$. Since $p(v)$ is symmetric
to the origin, $\mathbb{E}[v]=0$. ∎

###### Proof of Lemma 13.

Define a sequence of datasets $D^{0},D^{1},\cdots,D^{k}$, such that $D^{0}=D$,
$D^{k}=D^{\prime}$, and for each $i\in[k]$, $D^{i},D^{i-1}$ differ on at most
one agent’s dataset. Then, by the triangular inequality, we obtain

$\displaystyle\|\hat{\theta}(D)-\hat{\theta}(D^{\prime})\|_{2}=\|\hat{\theta}(D^{0})-\hat{\theta}(D^{k})\|_{2}=\|\sum_{i=1}^{k}\hat{\theta}(D^{i-1})-\hat{\theta}(D^{i})\|_{2}\leq\sum_{i=1}^{k}\|\hat{\theta}(D^{i-1})-\hat{\theta}(D^{i})\|_{2}\leq
k\Delta_{n}.$

with probability at least $1-k\gamma_{n}$ by taking a union bound over $k$
failure probabilities $\gamma_{n}$. ∎

###### Proof of Lemma 14.

We first bound $\tau_{\alpha,\beta}^{1}$. Since
$n=\\#\\{i:c_{i}\leq\tau\\}+\\#\\{i:c_{i}>\tau\\}$, the event
$\\{\\#\\{i:c_{i}\leq\tau\\}\geq(1-\alpha)n\\}$ is equivalent to the event
$\\{\\#\\{i:c_{i}>\tau\\}\leq\alpha n\\}$. Thus, by the definition of
$\tau_{\alpha,\beta}^{1}$,

$\displaystyle\tau_{\alpha,\beta}^{1}$
$\displaystyle=\inf\\{\tau>0:\mathbb{P}_{(c_{1},\cdots,c_{n})\sim
p^{n}}(\\#\\{i:c_{i}>\tau\\}\leq\alpha n)\geq 1-\beta\\}$
$\displaystyle=\inf\\{\tau>0:\mathbb{P}_{(c_{1},\cdots,c_{n})\sim
p^{n}}(\\#\\{i:c_{i}>\tau\\}>\alpha n)\leq\beta\\},$

By Markov’s inequality, we have

$\displaystyle\mathbb{P}_{(c_{1},\cdots,c_{n})\sim
p^{n}}(\\#\\{i:c_{i}>\tau\\}>\alpha
n)\leq\frac{\mathbb{E}_{(c_{1},\cdots,c_{n})\sim
p^{n}}[\sum_{i=1}^{n}\mathbf{1}_{\\{c_{i}>\tau\\}}]}{\alpha n}$
$\displaystyle=\frac{\sum_{i=1}^{n}\mathbb{E}_{c_{i}\sim
p}[\mathbf{1}_{\\{c_{i}>\tau\\}}]}{\alpha
n}=\frac{n\mathbb{P}[c_{i}>\tau]}{\alpha
n}=\frac{\mathbb{P}[c_{i}>\tau]}{\alpha}.$

Thus,
$\\{\tau>0:\mathbb{P}(c_{i}>\tau)\leq\alpha\beta\\}\subseteq\\{\tau>0:\mathbb{P}_{(c_{1},\cdots,c_{n})\sim
p^{n}}(\\#\\{i:c_{i}>\tau\\}>\alpha n)\leq\beta\\}$, which implies
$\tau_{\alpha,\beta}^{1}\leq\inf\\{\tau>0:\mathbb{P}(c_{i}>\tau)\leq\alpha\beta\\}$.
The Assumption 4 implies that $\mathbb{P}(c_{i}>\tau)\leq e^{-\lambda\tau}$.
Hence,
$\tau_{\alpha,\beta}^{1}\leq\frac{1}{\lambda}\log\frac{1}{\alpha\beta}$. By
the definition of $\tau_{\alpha}^{2}$ and Assumption 4, we have
$\tau_{\alpha}^{2}\leq\frac{1}{\lambda}\ln\frac{1}{\alpha}$. Since
$\beta\in(0,1)$,
$\frac{1}{\lambda}\log\frac{1}{\alpha\beta}>\frac{1}{\lambda}\log\frac{1}{\alpha}$,
then
$\tau_{\alpha,\beta}=\max\\{\tau_{\alpha,\beta}^{1},\tau_{\alpha}^{2}\\}\leq\frac{1}{\lambda}\log\frac{1}{\alpha\beta}$.
∎

###### Proof of Lemma 17.

Note that

$\displaystyle\|\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}\|_{2}=\sup_{v\in\mathcal{S}^{n-1}}|\nu^{T}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}\nu|=\sup_{\nu\in\mathcal{S}^{d-1}}|\nu^{T}\widetilde{\mathbf{x}}_{i}|^{2}=\|\widetilde{\mathbf{x}}_{i}\|_{2}^{2}\leq\sqrt{d}\|\widetilde{\mathbf{x}}_{i}\|_{4}^{2}\leq\sqrt{d}\tau^{2},$

and

$\displaystyle\|\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}\|_{2}=\sup_{\nu\in\mathcal{S}^{d-1}}|\nu^{T}\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}\nu|=\sup_{\nu\in\mathcal{S}^{d-1}}\mathbb{E}|\nu^{T}\widetilde{\mathbf{x}}_{i}|^{2}\leq\sup_{\nu\in\mathcal{S}^{d-1}}\mathbb{E}|\nu^{T}\mathbf{x}_{i}|^{2}\leq\sup_{\nu\in\mathcal{S}^{d-1}}\sqrt{\mathbb{E}(\nu^{T}\mathbf{x}_{i})^{4}}=\sqrt{R}.$

Thus,

$\displaystyle\|\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}-\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}\|_{2}\leq\|\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}\|_{2}+\|\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}\|_{2}\leq\sqrt{d}\tau^{2}+\sqrt{R}.$

Also note that

$\displaystyle\|\mathbb{E}(\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T})^{2}\|_{2}$
$\displaystyle=\sup_{\nu\in\mathcal{S}^{d-1}}|\nu^{T}\mathbb{E}(\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T})^{2}\nu|=\sup_{\nu\in\mathcal{S}^{d-1}}\mathbb{E}(\nu^{T}\widetilde{\mathbf{x}}_{i})^{2}\|\widetilde{\mathbf{x}}_{i}\|_{2}^{2}\leq\sup_{\nu\in\mathcal{S}^{d-1}}\sum_{i=j}^{d}\mathbb{E}x_{ij}^{2}(\nu^{T}\mathbf{x}_{i})^{2}$
$\displaystyle\leq\sup_{\nu\in\mathcal{S}^{d-1}}\sum_{j=1}^{d}\sqrt{\mathbb{E}(x_{ij}^{4})\mathbb{E}(\nu^{T}\mathbf{x}_{i})^{4}}\leq
Rd.$

Thus,

$\displaystyle\|\mathbb{E}(\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}-\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T})^{2}\|_{2}=\|\mathbb{E}(\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T})^{2}-(\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T})^{2}\|_{2}\leq\|\mathbb{E}(\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T})^{2}\|_{2}+\|\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}\|_{2}^{2}\leq
R(d+1).$

By Theorem 5.29 in [35], for any $t>0$, it holds that

$\displaystyle\mathbb{P}(\|\frac{1}{n}\sum_{i=1}^{n}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}-\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}\|_{2}>t)\leq
2d\exp\big{[}-c\min\\{\frac{nt^{2}}{R(d+1)},\frac{nt}{\sqrt{d}\tau^{2}+\sqrt{R}}\\}\big{]}.$
(9)

where $c>0$ is a constant. In addition,

$\displaystyle\|\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}-\mathbb{E}\mathbf{x}_{i}\mathbf{x}_{i}^{T}\|_{2}$
$\displaystyle=\sup_{\nu\in\mathcal{S}^{d-1}}|\nu^{T}(\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}-\mathbb{E}\mathbf{x}_{i}\mathbf{x}_{i}^{T})\nu|$
$\displaystyle=\sup_{\nu\in\mathcal{S}^{d-1}}|\mathbb{E}(((\nu^{T}\widetilde{\mathbf{x}}_{i})^{2}-(\nu^{T}\mathbf{x}_{i})^{2})\mathbf{1}_{\\{\|\mathbf{x}_{i}\|_{4}>\tau\\}})|$
$\displaystyle\leq\sup_{\nu\in\mathcal{S}^{d-1}}|\mathbb{E}(\nu^{T}\mathbf{x}_{i})^{2}\mathbf{1}_{\\{\|\mathbf{x}_{i}\|_{4}>\tau\\}}|$
$\displaystyle\leq\sup_{\nu\in\mathcal{S}^{d-1}}\sqrt{\mathbb{E}(\nu^{T}\mathbf{x}_{i})^{4}\mathbb{P}(\|\mathbf{x}_{i}\|_{4}>\tau)}$
$\displaystyle\leq\sup_{\nu\in\mathcal{S}^{d-1}}\sqrt{\mathbb{E}(\nu^{T}\mathbf{x}_{i})^{4}\frac{\mathbb{E}\|\mathbf{x}_{i}\|_{4}^{4}}{\tau^{4}}}\leq\frac{R\sqrt{d}}{\tau^{2}}.$
(10)

Let $\tau=\Theta((nR/(\delta\log n))^{1/4})$ and $t=\sqrt{\delta Rd\log n/n}$.
Then, combining (9) and (10) delivers that with probability at least
$1-2dn^{-C\delta}$ one has

$\displaystyle\|\frac{\widetilde{X}^{T}\widetilde{X}}{n}-\Sigma\|_{2}\leq\|\frac{1}{n}\sum_{i=1}^{n}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}-\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}\|_{2}+\|\mathbb{E}\widetilde{\mathbf{x}}_{i}\widetilde{\mathbf{x}}_{i}^{T}-\mathbb{E}\mathbf{x}_{i}\mathbf{x}_{i}^{T}\|_{2}\leq
2\sqrt{\frac{\delta Rd\log n}{n}}.$

∎

##  Appendix C Omitted Proofs

###### Proof of Lemma 3.

Let $D$ and $D^{\prime}$ be two arbitrary neighboring datasets that differ
only on the last agent’s report $(\mathbf{x}_{n},\hat{y}_{n})$ in $D$ and
$(\mathbf{x}_{n}^{\prime},\hat{y}_{n}^{\prime})$ in $D^{\prime}$. Let
$\mathcal{E}:=\\{\max_{i\in[n]}\|\mathbf{x}_{i}\|_{2}\leq
4\sqrt{c}\sigma\sqrt{\log n}\\}$ for constant $c>1$. By Lemma 8, we have
$\mathbb{P}(\mathcal{E}^{c})\leq n^{-{c+1}}$. In the following, we will always
assume the event $\mathcal{E}$ holds.

Step 1: Upper bound
$\|\frac{X^{T}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(y))}{n}\|_{2}$. By
Lemma 15, and note that $\mathbf{x}_{i}^{T}\Sigma^{-\frac{1}{2}}$ is
isotropic, then with probability at least $1-2e^{-c_{0}n}$ we have
$\|X^{T}\|_{2}=\|X\|_{2}=\|X\Sigma^{-\frac{1}{2}}\Sigma^{\frac{1}{2}}\|_{2}\leq\|X\Sigma^{-\frac{1}{2}}\|_{2}\|\Sigma^{\frac{1}{2}}\|_{2}\leq(2\sqrt{n}+C_{0}\sqrt{d})\sqrt{\lambda_{\max}}$,
where $\lambda_{\max}$ is the largest eigenvalue of $\Sigma$. Thus,

$\displaystyle\|\frac{X^{T}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))}{n}\|_{2}$
$\displaystyle\leq\frac{1}{n}\|X^{T}\|_{2}\|(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))\|_{2}$
$\displaystyle\leq\frac{1}{n}(2\sqrt{n}+C_{0}\sqrt{d})\sqrt{\lambda_{\max}}\sqrt{n}\kappa_{A,1}=O(\sqrt{\lambda_{\max}}\kappa_{A,1}).$

Step 2: Upper bound the sensitivity of
$\|\frac{X^{T}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))}{n}\|_{2}$.

$\displaystyle\quad\|\frac{X^{T}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))}{n}-\frac{X^{\prime^{T}}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}^{\prime}))}{n}\|_{2}=\frac{1}{n}\|\mathbf{x}_{n}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{n})-\mathbf{x}_{n}^{\prime}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{n}^{\prime}))\|_{2}$
$\displaystyle\leq\frac{1}{n}\left(\|\mathbf{x}_{n}\|_{2}|(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{n}))|+\|\mathbf{x}_{n}^{\prime}\|_{2}|(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{n}^{\prime}))|\right)=O(\frac{1}{n}\sigma\sqrt{\log
n}\kappa_{A,1}).$

Step 3: Upper bound $\|(\frac{X^{T}X}{n})^{-1}\|_{2}$. For any nonzero vector
$w\in\mathbb{R}^{d}$, Note that

$\displaystyle\|\frac{X^{T}X}{n}w\|_{2}$
$\displaystyle=\|\frac{X^{T}X}{n}w-\Sigma w+\Sigma w\|_{2}$
$\displaystyle\geq\|\Sigma
w\|_{2}-\|(\frac{X^{T}X}{n}-\Sigma)w\|_{2}\geq(\kappa_{2}-\|\frac{X^{T}X}{n}-\Sigma\|_{2}\|w\|_{2}).$
(11)

By Lemma 16, let $s=C_{1}t\sqrt{d}$ for any $t\geq 1$, then when $n\geq
4C_{1}^{2}t^{2}d=\Omega(t^{2}d)$, with probability at least $1-2e^{-t^{2}d}$,
we have $\|\frac{X^{T}X}{n}-\Sigma\|_{2}\leq 2C_{1}t\sqrt{\frac{d}{n}}$. Thus,
when $n\geq\frac{16C_{1}^{2}t^{2}d}{\kappa_{2}^{2}}$, we have
$\|\frac{X^{T}X}{n}-\Sigma\|_{2}\leq\frac{\kappa_{2}}{2}$. Combining this
inequality and (11) yields that
$\|\frac{X^{T}X}{n}w\|_{2}\geq\frac{\kappa_{2}}{2}\|w\|_{2}$, which implies
$\|(\frac{X^{T}X}{n})^{-1}\|_{2}\leq\frac{2}{\kappa_{2}}$.

Step 4:  Next we bound the sensitivity of $\|(\frac{X^{T}X}{n})^{-1}\|_{2}$.
Note that for any two nonsingular square matrices $A,B$ with the same size, it
holds that $A^{-1}-B^{-1}=-B^{-1}(A-B)A^{-1}$. Thus,

$\displaystyle\|(\frac{X^{T}X}{n})^{-1}-(\frac{X^{\prime^{T}}X^{\prime}}{n})^{-1}\|_{2}$
$\displaystyle\leq\|(\frac{X^{T}X}{n})^{-1}\|_{2}\|(\frac{X^{\prime^{T}}X^{\prime}}{n})\|_{2}\|\frac{X^{T}X}{n}-\frac{X^{T}X}{n}\|_{2}$
$\displaystyle\leq\frac{4}{\kappa_{2}^{2}}(\|\frac{X^{T}X}{n}-\Sigma\|_{2}+\|\Sigma-\frac{X^{\prime^{T}}X^{\prime}}{n}\|_{2})\leq\frac{16C_{1}t}{\kappa_{2}^{2}}\sqrt{\frac{d}{n}}.$

Take $t=\sqrt{\log n}$ we have
$\|(\frac{X^{T}X}{n})^{-1}-(\frac{X^{\prime^{T}}X^{\prime}}{n})^{-1}\|_{2}=O(\frac{1}{\kappa_{2}^{2}}\sqrt{\frac{d\log
n}{n}})$.

Step 5:  Applying the inequality $\|AB-A^{\prime}B^{\prime}\|_{2}=\|AB-
AB^{\prime}+AB^{\prime}-A^{\prime}B^{\prime}\|_{2}\leq\|A\|_{2}\|B-B^{\prime}\|_{2}+\|A-A^{\prime}\|_{2}\|B^{\prime}\|_{2}$,
we have with probability at least $1-n^{-c+1}-4n^{-d}$,

$\displaystyle\|\hat{\theta}(D)-\hat{\theta}(D^{\prime})\|_{2}$
$\displaystyle=\|(\frac{X^{T}X}{n})^{-1}\frac{X^{T}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))}{n}-(\frac{X^{\prime^{T}}X^{\prime}}{n})^{-1}\frac{X^{\prime^{T}}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}^{\prime}))}{n}\|_{2}$
$\displaystyle=O(\kappa_{A,1}(\frac{2\sigma}{\kappa_{2}}\frac{\sqrt{\log
n}}{n}+\frac{\sqrt{\lambda_{\max}}}{\kappa_{2}^{2}}\sqrt{\frac{d\log n}{n}}),$
(12)

where the first inequality is due to Lemma 7. ∎

###### Proof of Lemma 4.

Note that by the proof of Lemma 3 we can see that when
$n\geq\frac{16C_{1}^{2}t^{2}d}{\kappa_{2}^{2}}$, with probability at least
$1-2e^{-t^{2}d}$ we have
$\|(\frac{X^{T}X}{n})^{-1}\|_{2}\leq\frac{2}{\kappa_{2}}$. Thus,

$\displaystyle\|\theta^{*}-\hat{\theta}(D)\|_{2}$
$\displaystyle=\|\theta^{*}-\big{(}\frac{X^{T}X}{n}\big{)}^{-1}\frac{X^{T}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))}{n}\|_{2}$
$\displaystyle\leq\|\big{(}\frac{X^{T}X}{n}\big{)}^{-1}\|_{2}\|\big{(}\frac{X^{T}X}{n}\big{)}\theta^{*}-\frac{X^{T}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))}{n}\|_{2}$
$\displaystyle\leq\frac{2}{\kappa_{2}}\|\frac{X^{T}}{n}\\{X\theta^{*}-(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))\\}\|_{2}$
$\displaystyle\leq\frac{2\sqrt{d}}{\kappa_{2}}\|\frac{X^{T}}{n}\\{X\theta^{*}-(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))\\}\|_{\infty}.$
(13)

To complete the proof, we upper bound the term
$\|\frac{X^{T}}{n}\\{X\theta^{*}-(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))\\}\|_{\infty}$.

$\displaystyle\quad\|\frac{X^{T}}{n}\\{X\theta^{*}-(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))\\}\|_{\infty}$
$\displaystyle=\max_{j\in[d]}|[\frac{X^{T}}{n}\left\\{X\theta^{*}-(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))\right\\}]_{j}|$
$\displaystyle=\max_{j\in[d]}|\frac{1}{n}\sum_{i=1}^{n}x_{ij}(\sum_{k=1}^{d}x_{ik}\theta^{*}_{k}-(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{i})))|$
$\displaystyle=\max_{j\in[d]}|\frac{1}{n}\sum_{i=1}^{n}x_{ij}((A^{\prime})^{-1}\circ
A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{i})))|$
$\displaystyle=\max_{j\in[d]}|\frac{1}{n}\sum_{i=1}^{n}x_{ij}[(A^{\prime})^{-1}]^{\prime}(\xi_{i})(A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{i}))|\quad\text{(by
mean value theorem)}$
$\displaystyle\leq\max_{j\in[d]}|\frac{1}{n}\sum_{i=1}^{n}x_{ij}[(A^{\prime})^{-1}]^{\prime}(\xi_{i})(A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-\widetilde{y}_{i})|+\max_{j\in[d]}|\frac{1}{n}\sum_{i=1}^{n}x_{ij}[(A^{\prime})^{-1}]^{\prime}(\xi_{i})(\widetilde{y}_{i}-\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{i}))|$
$\displaystyle\equiv\max_{j\in[d]}\text{I}_{j}+\max_{j\in[d]}\text{II}_{j},$
(14)

where $\xi_{i}$ is some value between
$A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)$ and
$\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{i})$. Let
$\mathcal{E}:=\\{\max_{i\in[n]}\|\mathbf{x}_{i}\|_{2}\leq
4\sqrt{c}\sigma\sqrt{\log n}\\}$ for constant $c>1$. By Lemma 8, we have
$\mathbb{P}(\mathcal{E}^{c})\leq n^{-{c+1}}$. In the following, we will omit
the conditioning on the event $\mathcal{E}$.

Since
$x_{ij}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mathrm{subG}(\sigma^{2}/d),\forall
i\in[n]$, by Lemma 8, for any $t>0$, $\mathbb{P}(\text{I}_{j}>t)\leq
2\exp(-\frac{t^{2}}{2\sigma^{2}\|a\|_{2}^{2}/d})$, where
$a=[\frac{1}{n}[(A^{\prime})^{-1}]^{\prime}(\xi_{i})(A(\langle\mathbf{x}_{i},\theta^{*}\rangle)-\widetilde{y}_{i})]_{i=1}^{n}$.
Let $t=c_{1}^{\prime}\sigma\|a\|_{2}\sqrt{\log n}/\sqrt{d}$. then

$\displaystyle\mathbb{P}\left(\text{I}_{j}>c_{1}^{\prime}\frac{\sigma}{\sqrt{d}}\sqrt{\frac{1}{n}\sum_{i=1}^{n}([(A^{\prime})^{-1}]^{\prime}(\xi_{i})(A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-\widetilde{y}_{i}))^{2}}\sqrt{\frac{\log
n}{n}}\right)\leq 2n^{-\frac{c_{1}^{\prime^{2}}}{2}}.$

Since $|[(A^{\prime})^{-1}](\xi_{i})|\leq\kappa_{A,0}$, with probability at
least $1-2n^{-\frac{c_{1}^{\prime^{2}}}{2}}$ we have

$\displaystyle\text{I}_{j}\leq
c_{1}^{\prime}\frac{\sigma}{\sqrt{d}}\kappa_{A,0}\sqrt{\frac{1}{n}\sum_{i=1}^{n}(A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-\widetilde{y}_{i})^{2}}\sqrt{\frac{\log
n}{n}}.$

Since
$(A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-\widetilde{y}_{i})^{2}\leq(M_{A}+\tau_{2})^{2}$,
by Hoeffding’s inequality (Lemma 9), with probability at least
$1-2n^{-\frac{c_{1}^{\prime^{2}}}{2}}-2n^{-\zeta}$

$\text{I}_{j}\leq
c_{1}^{\prime}\frac{\sigma}{\sqrt{d}}\kappa_{A,0}\sqrt{\mathbb{E}[(A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-\widetilde{y}_{i})^{2}]+(M_{A}+\tau_{2})^{2}\sqrt{\frac{\zeta\log
n}{n}}}\sqrt{\frac{\log n}{n}}.$

Note that

$\displaystyle\mathbb{E}[(A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-\widetilde{y}_{i})^{2}]=\mathbb{E}[(A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-y_{i}+y_{i}-\widetilde{y}_{i})^{2}]\leq
2(\mathbb{E}[(A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-y_{i})^{2}]+\mathbb{E}[(y_{i}-\widetilde{y}_{i})^{2}]).$
(15)

Since
$\mathbb{E}[y_{i}|\mathbf{x}_{i},\theta^{*}]=A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)$
and
$\mathrm{var}[y_{i}|\mathbf{x}_{i},\theta^{*}]=A^{\prime\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)\phi\leq\kappa_{A,2}\phi$,
we have

$\displaystyle\mathbb{E}[(A^{\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)-y_{i})^{2}]=\mathbb{E}_{\mathbf{x}_{i}}[(\mathbb{E}_{y_{i}}[y_{i}|\mathbf{x}_{i},\theta^{*}]-y_{i})^{2}]=\mathbb{E}_{\mathbf{x}_{i}}[A^{\prime\prime}(\langle\mathbf{x}_{i},\theta^{*}\rangle)\phi]\leq\kappa_{A,2}\phi.$
(16)

For the second term of (15), we have

$\displaystyle\mathbb{E}[(y_{i}-\widetilde{y}_{i})^{2}]=\mathbb{E}[(y_{i}-\widetilde{y}_{i})^{2}\mathbf{1}(|y_{i}|>\tau_{2})]$
$\displaystyle\leq\mathbb{E}[y_{i}^{2}\mathbf{1}_{\\{|y_{i}|>\tau_{2}\\}}]$
$\displaystyle\leq\sqrt{\mathbb{E}[y_{i}^{4}]\mathbb{P}(|y_{i}|>\tau_{2})}\leq\sqrt{\mathbb{E}[y_{i}^{4}]}\sqrt{\frac{\mathbb{E}[y_{i}^{4}]}{\tau_{2}^{4}}}\leq\frac{R}{\tau_{2}^{2}}.$
(17)

Combining (15), (16) and (17) delivers that

$\displaystyle\text{I}_{j}\leq
c_{1}^{\prime}\frac{\sigma}{\sqrt{d}}\kappa_{A,0}\sqrt{(\kappa_{A,2}\phi+\frac{R}{\tau_{2}^{2}})+(M_{A}+\tau_{2})^{2}\sqrt{\frac{\zeta\log
n}{n}}}\sqrt{\frac{\log n}{n}}.$ (18)

Similarly, since
$x_{ij}\stackrel{{\scriptstyle\mathrm{iid}}}{{\sim}}\mathrm{subG}(\sigma^{2}/d)$,
by Lemma 8, with probability at least $1-2n^{-\frac{c_{2}^{\prime^{2}}}{2}}$
it holds that

$\displaystyle\text{II}_{j}\leq
c_{2}^{\prime}\frac{\sigma}{\sqrt{d}}\kappa_{A,0}\varepsilon_{\bar{M}}\sqrt{\frac{\log
n}{n}}.$ (19)

Combining (18) and (19), by the union bound for all $j\in[d]$, yields that
with probability at least
$1-2dn^{-\frac{c_{1}^{\prime^{2}}}{2}}-2dn^{-\zeta}-2dn^{-\frac{c_{2}^{\prime^{2}}}{2}}$,

$\displaystyle\max_{j\in[d]}\text{I}_{j}+\max_{j\in[d]}\text{II}_{j}\leq
O((\sqrt{(\kappa_{A,2}\phi+\frac{R}{\tau_{2}^{2}})+(M_{A}+\tau_{2})^{2}\sqrt{\frac{\zeta\log
n}{n}}}+\varepsilon_{\bar{M}})\frac{\sigma}{\sqrt{d}}\kappa_{A,0}\sqrt{\frac{\log
n}{n}}).$ (20)

Considering the failure of the event $\mathcal{E}$ and combining (13), (14),
and (20) delivers that for any $\delta>0$, with probability at least
$1-n^{-c+1}-2dn^{-\frac{c_{1}^{\prime^{2}}}{2}}-2dn^{-\zeta}-2dn^{-\frac{c_{2}^{\prime^{2}}}{2}}=1-O(n^{-\Omega(1)})$,

$\displaystyle\|\theta^{*}-(\frac{X^{T}X}{n})^{-1}\frac{X^{T}(A^{\prime})^{-1}(\Pi_{\bar{\mathcal{M}}}(\widetilde{y}))}{n}\|_{2}\leq\lambda_{n}\sqrt{\frac{\log
n}{n}}$

where
$\lambda_{n}:=\tilde{O}({\kappa_{A,0}}(\sqrt{\kappa_{A,2}+\frac{1}{\tau_{2}^{2}}}+(M_{A}+\tau_{2})\sqrt[4]{\frac{1}{n}}+\varepsilon_{\bar{\mathcal{M}}})$.
∎

###### Proof of Theorem 1.

We first show that $\hat{\theta}^{P}(\hat{D})$ is
$(\varepsilon,\gamma_{n})$-random joint differential privacy (RJDP). Let
$\hat{D}$ and $\hat{D}^{\prime}$ be any two datasets that differ only on one
agent’s dataset. For any fixed $\theta\in\Theta\subseteq\mathbb{R}^{d}$, by
Lemma 2, with probability at least $1-\gamma_{n}$ we have
$\|\hat{\theta}(\hat{D})-\hat{\theta}(\hat{D}^{\prime})\|_{2}\leq\Delta_{n}$.
Thus

$\displaystyle\quad\frac{p(\hat{\theta}^{P}(\hat{D})=\theta|\hat{D})}{p(\hat{\theta}^{P}(\hat{D}^{\prime})=\theta|\hat{D}^{\prime})}=\frac{p(\hat{\theta}(\hat{D})+v=\theta|\hat{D})}{p(\hat{\theta}(\hat{D}^{\prime})+v^{\prime}=\theta|\hat{D}^{\prime})}=\frac{p(v=\theta-\hat{\theta}(\hat{D})|\hat{D})}{p(v^{\prime}=\theta-\hat{\theta}(\hat{D}^{\prime})|\hat{D}^{\prime})}$
$\displaystyle=\exp\\{\frac{\varepsilon}{\Delta_{n}}(\|\hat{\theta}(\hat{D})\|_{2}-\|\hat{\theta}(\hat{D}^{\prime})\|_{2})\\}\leq\exp\\{\frac{\varepsilon}{\Delta_{n}}\|\hat{\theta}(\hat{D})-\hat{\theta}(\hat{D}^{\prime})\|_{2}\\}\leq\exp(\varepsilon),$

which means $\hat{\theta}^{P}(\hat{D})$ is $(\varepsilon,\gamma_{n})$-RJDP.
The estimators $\hat{\theta}^{P}(\hat{D}^{0})$ and
$\hat{\theta}^{P}(\hat{D}^{1})$ are computed in the same way as
$\hat{\theta}^{P}(\hat{D})$, so $\hat{\theta}^{P}(\hat{D}^{0})$ and
$\hat{\theta}^{P}(\hat{D}^{1})$ each satisfy
$(\varepsilon,\gamma_{n/2})$-RJDP. Since $\hat{\theta}^{P}(\hat{D}^{0})$ and
$\hat{\theta}^{P}(\hat{D}^{1})$ are computed on disjoint subsets of the data,
then by the Parallel Composition Theorem, together they satisfy
$(\varepsilon,2\gamma_{n/2})$-RJDP. By the Sequential Composition Theorem, the
estimators
($\hat{\theta}^{P}(\hat{D})$,$\hat{\theta}^{P}(\hat{D}^{0})$,$\hat{\theta}^{P}(\hat{D}^{1})$)
together satisfy $(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$-RJDP. Finally,
using the post-processing property and Billboard Lemma 11, the output
$(\bar{\theta}^{P}(\hat{D})$,$\bar{\theta}^{P}(\hat{D}^{0})$,
$\bar{\theta}^{P}(\hat{D}^{1})$,
$\\{\pi_{i}(D_{i},\bar{\theta}^{P}(\hat{D}^{b}))\\}_{i=1}^{n})$ of Mechanism 1
satisfies $(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$-RJDP. ∎

###### Proof of Theorem 2.

Suppose all agents other than $i$ are following strategy
$\sigma_{\tau_{\alpha,\beta}}$. Let agent $i$ be in group $1-b,b\in\\{0,1\\}$.
We will show that $\sigma_{\tau_{\alpha,\beta}}$ achieves $\eta$-Bayesian Nash
equilibrium by bounding agent $i$’s incentive to deviate. Assume that
$c_{i}\leq\tau_{\alpha,\beta}$, otherwise there is nothing to show because
agent $i$ would be allowed to submit an arbitrary report under
$\sigma_{\tau_{\alpha,\beta}}$. For ease of notation, we write $\sigma$ for
$\sigma_{\tau_{\alpha,\beta}}$ for the remainder of the proof. We first
compute the maximum expected mount (based on his belief) that agent $i$ can
increase his payment by misreporting to the analyst, i.e.

$\displaystyle\quad\mathbb{E}[\pi_{i}(\hat{D}_{i},\sigma(D^{b},c^{b}))|D_{i},c_{i}]-\mathbb{E}[\pi_{i}(D_{i},\sigma(D^{b},c^{b}))|D_{i},c_{i}]$
$\displaystyle=\mathbb{E}\left[B_{a_{1},a_{2}}\left(A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle),A^{\prime}(\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|\hat{D}_{i})}[\theta]\rangle)\right)\big{|}D_{i},c_{i}\right]$
$\displaystyle\quad-\mathbb{E}\left[B_{a_{1},a_{2}}\left(A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle),A^{\prime}(\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]\rangle)\right)\big{|}D_{i},c_{i}\right].$ (21)

Note that $B_{a_{1},a_{2}}(p,q)=a_{1}-a_{2}(p-2pq+q^{2})$ is linear with
respect to $p$, and is a strictly concave function of $q$ maximized at $q=p$.
Thus, (21) is upper bounded by the following with probability
$1-C_{1}n^{-\Omega(1)}$

$\displaystyle\quad
B_{a_{1},a_{2}}(\mathbb{E}[A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle)|D_{i},c_{i}],\mathbb{E}[A^{\prime}(\langle\mathbf{x}_{i},\hat{\theta}^{P}(\hat{D}^{b})\rangle)|D_{i},c_{i}])$
$\displaystyle\quad-
B_{a_{1},a_{2}}(\mathbb{E}[A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle)|D_{i},c_{i}],A^{\prime}(\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]\rangle))$
$\displaystyle=a_{2}\left(\mathbb{E}[A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle)|D_{i},c_{i}]-A^{\prime}(\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]\rangle)\right)^{2}$
$\displaystyle=a_{2}\left(\mathbb{E}[A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle)-A^{\prime}(\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]\rangle)|D_{i},c_{i}]\right)^{2}$ $\displaystyle\leq
a_{2}\left(\mathbb{E}[\kappa_{A,2}\mathbf{x}_{i}^{T}(\bar{\theta}^{P}(\hat{D}^{b})-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta])|D_{i},c_{i}]\right)^{2}$ $\displaystyle\leq
a_{2}\kappa_{A,2}^{2}\|\mathbf{x}_{i}\|_{2}^{2}\|\mathbb{E}[\bar{\theta}^{P}(\hat{D}^{b})-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]|D_{i},c_{i}]\|_{2}^{2}$ $\displaystyle\leq
Ca_{2}\kappa_{A,2}^{2}\sigma^{2}\log
n\|\mathbb{E}[\bar{\theta}^{P}(\hat{D}^{b})-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]|D_{i},c_{i}]\|_{2}^{2}.$

We continue by bounding the term
$\|\mathbb{E}[\bar{\theta}^{P}(\hat{D}^{b})-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]|D_{i},c_{i}]\|_{2}$. By Lemma 7

$\displaystyle\|\mathbb{E}[\bar{\theta}^{P}(\hat{D}^{b})-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]|D_{i},c_{i}]\|_{2}$
$\displaystyle\leq\|\mathbb{E}[\bar{\theta}^{P}(\hat{D}^{b})-\bar{\theta}^{P}(D^{b})|D_{i},c_{i}]\|_{2}+\|\mathbb{E}[\bar{\theta}^{P}(D^{b})|D_{i},c_{i}]-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]|D_{i},c_{i}]\|_{2}$
$\displaystyle\leq\|\mathbb{E}[\hat{\theta}^{P}(\hat{D}^{b})-\hat{\theta}^{P}(D^{b})|D_{i},c_{i}]\|_{2}+\|\mathbb{E}[\bar{\theta}^{P}(D^{b})|D_{i},c_{i}]-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]|D_{i},c_{i}]\|_{2}$
$\displaystyle\leq\mathbb{E}\|\hat{\theta}(\hat{D}^{b})-\hat{\theta}(D^{b})\|_{2}+\|\mathbb{E}[\bar{\theta}^{P}(D^{b})|D_{i}]-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]\|_{2},$ (22)

Since agent $i$ believes that with at least probability $1-\beta$, at most
$\alpha n$ agents will misreport their datasets under threshold strategy
$\sigma_{\tau_{\alpha,\beta}}$, datasets $D^{b}$ and $\hat{D}^{b}$ differ only
on at most $\alpha n$ agents’ datasets. By Lemma 13, with probability at least
$1-\alpha n\gamma_{n/2}$ we have
$\mathbb{E}\|\hat{\theta}(\hat{D}^{b})-\hat{\theta}(D^{b})\|_{2}\leq\alpha
n\Delta_{n/2}$. For the third term of (22),

$\displaystyle\quad\mathbb{E}[\bar{\theta}^{P}(D^{b})|D_{i}]-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]$ $\displaystyle=\mathbb{E}_{D^{b}\sim
p(D^{b}|D_{i})}[\bar{\theta}^{P}(D^{b})]-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]$ $\displaystyle=\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\mathbb{E}_{D^{b}\sim
p(D^{b}|\theta)}[\bar{\theta}^{P}(D^{b})]|\theta]-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]$ $\displaystyle=\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\mathbb{E}_{D^{b}\sim
p(D^{b}|\theta)}[\bar{\theta}^{P}(D^{b})-\theta]|\theta].$

Since

$\displaystyle
p(D^{b}|\theta)=p(X^{b},y^{b}|\theta)=p(y^{b}|X^{b},\theta)p(X^{b}|\theta)=p(y^{b}|X^{b},\theta)p(X^{b}),$

we have

$\displaystyle\mathbb{E}_{D^{b}\sim
p(D^{b}|\theta)}[\hat{\theta}(D^{b})-\theta]=\mathbb{E}_{X^{b}}[\mathbb{E}_{y^{b}}[\bar{\theta}^{P}(X^{b},y^{b})-\theta]|X^{b},\theta].$

Since we have the prior knowledge that $\|\theta^{*}\|_{2}\leq\tau_{\theta}$.
Thus, the for posterior distribution $\theta\sim p(\theta|\hat{D}_{i})$ it
will also have $\|\theta\|_{2}\leq\tau_{\theta}$. By Jensen’s inequality,
Lemma 7 and Lemma 4, with probability at least $1-O(n^{-\Omega(1)})$ we have

$\displaystyle\|\mathbb{E}[\bar{\theta}^{P}(D^{b})|D_{i}]-\mathbb{E}_{\theta\sim
p(\theta|D_{i})}[\theta]\|_{2}\leq\mathbb{E}_{\theta\sim
p(\theta|D_{i}),X^{b}}[\mathbb{E}_{y^{b}}[\|\bar{\theta}^{P}(X^{b},y^{b})-\theta\|_{2}|X^{b},\theta]]$
$\displaystyle\leq\mathbb{E}_{\theta\sim
p(\theta|D_{i}),X^{b}}[\mathbb{E}_{y^{b}}[\|\hat{\theta}^{P}(X^{b},y^{b})-\theta\|_{2}|X^{b},\theta]]\leq\lambda_{n}\sqrt{\frac{\log
n}{n}}+\mathbb{E}\|v_{b}\|_{2},$

where
$\lambda_{n}:=\tilde{O}({\sigma\kappa_{A,0}}(\sqrt{\kappa_{A,2}+\frac{1}{\tau_{2}^{2}}}+(M_{A}+\tau_{2})\sqrt[4]{\frac{1}{n}}+\varepsilon_{\bar{\mathcal{M}}}).$
In addition to an increased payment, agent $i$ may also experience decreased
privacy costs from misreporting. By Assumption 2, this decrease in privacy
costs is bounded above by $c_{i}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$.
Since we have assumed $c_{i}\leq\tau_{\alpha,\beta}$, the decrease in privacy
costs for agent $i$ is bounded above by
$\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$. Hence, agent
$i$’s total incentive to deviate is bounded above by

$\displaystyle\eta=O(a_{2}\kappa_{A,2}^{2}\sigma^{2}\log n(\alpha
n\Delta_{n/2}+\lambda_{n}\sqrt{\frac{\log
n}{n}}+\frac{d\Delta_{n/2}}{\epsilon})^{2}+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})).$

∎

###### Proof of Theorem 3.

For any realization $D$ held by agents, let
$\hat{D}=\sigma_{\tau_{\alpha,\beta}}(D)$. Then by Lemma 7 we have

$\displaystyle\mathbb{E}[\|\bar{\theta}^{P}(\hat{D})-\theta^{*}\|_{2}^{2}]\leq\mathbb{E}\|\hat{\theta}^{P}(\hat{D})-\theta^{*}\|_{2}^{2}$
$\displaystyle=\mathbb{E}\|\hat{\theta}^{P}(\hat{D})-\hat{\theta}(D)+\hat{\theta}(D)-\theta^{*}\|_{2}^{2}$
$\displaystyle=\mathbb{E}\|\hat{\theta}^{P}(\hat{D})-\hat{\theta}(D)\|_{2}^{2}+2\langle\hat{\theta}^{P}(\hat{D})-\hat{\theta}(D),\hat{\theta}(D)-\theta^{*}\rangle++\|\hat{\theta}(D)-\theta^{*}\|_{2}^{2}$
$\displaystyle\leq
2\mathbb{E}\|\hat{\theta}^{P}(\hat{D})-\hat{\theta}(D)\|_{2}^{2}+2\mathbb{E}\|\hat{\theta}(D)-\theta^{*}\|_{2}^{2}.$
(23)

For the first term of (23), by Lemma 13 and Lemma 12, with probability at
least $1-\beta-\alpha n\gamma_{n}$, we have

$\displaystyle\mathbb{E}\|\hat{\theta}^{P}(\hat{D})-\hat{\theta}(D)\|_{2}^{2}$
$\displaystyle=\mathbb{E}\|\hat{\theta}(\hat{D})+v-\hat{\theta}(D)\|_{2}^{2}$
$\displaystyle=\mathbb{E}\|\hat{\theta}(\hat{D})-\hat{\theta}(D)\|_{2}^{2}+\mathbb{E}\|v\|_{2}^{2}+2\mathbb{E}\langle\hat{\theta}(\hat{D})-\hat{\theta}(D),v\rangle$
$\displaystyle=\mathbb{E}\|\hat{\theta}(\hat{D})-\hat{\theta}(D)\|_{2}^{2}+\mathbb{E}\|v\|_{2}^{2}+2\langle\mathbb{E}\hat{\theta}(\hat{D})-\hat{\theta}(D),\mathbb{E}[v]\rangle$
$\displaystyle\leq(\alpha
n\Delta_{n})^{2}+d(d+1)(\frac{\Delta_{n}}{\varepsilon})^{2}.$ (24)

For the last term of (23), by Lemma 4,

$\displaystyle\|\hat{\theta}(D)-\theta^{*}\|^{2}_{2}\leq\lambda^{2}_{n}{\frac{\log
n}{n}}.$ (25)

Combining (24) and (25) yields that with probability at least $1-\beta-
Cdn^{-\Omega(1)}$,

$\displaystyle\mathbb{E}[\|\hat{\theta}^{P}(\hat{D})-\theta^{*}\|_{2}^{2}]\leq
O((\alpha
n\Delta_{n})^{2}+d^{2}(\frac{\Delta_{n}}{\varepsilon})^{2}+\lambda^{2}_{n}{\frac{\log
n}{n}}).$

∎

###### Proof of Theorem 4.

Let agent $i$ have privacy cost $c_{i}\leq\tau_{\alpha,\beta}$ and consider
agent $i$’s utility from participating in the mechanism. Suppose agent $i$ is
in group $1-b$, then his expected utility is

$\displaystyle\mathbb{E}[u_{i}]$
$\displaystyle=\mathbb{E}\left[B_{a_{1},a_{2}}\left(A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle),A^{\prime}(\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|\hat{D}_{i})}[\theta]\rangle)\right)|D_{i},c_{i}\right]-f_{i}(c_{i},\varepsilon)$
$\displaystyle\geq
B_{a_{1},a_{2}}\left(\mathbb{E}[A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle)|D_{i},c_{i}],A^{\prime}(\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|\hat{D}_{i})}[\theta]\rangle)\right)-\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2}).$
(26)

Since both $|\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle|$ and
$|\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|\hat{D}_{i})}[\theta]\rangle|$ are bounded by $\tau_{1}\tau_{\theta}$
with probability at least $1-\beta-O(n^{-\Omega(1)})$, both two inputs of
$B_{a_{1},a_{2}}(\cdot,\cdot)$ are bounded above by $M_{A}$. Note that

$\displaystyle B_{a_{1},a_{2}}(p,q)=a_{1}-a_{2}(p-2pq+q^{2})\geq
a_{1}-a_{2}(|p|+2|p||q|+|q|^{2}),$ (27)

thus by (26) and (27) agent $i$’s expected utility is non-negative as long as

$\displaystyle a_{1}\geq
a_{2}(M_{A}+3M_{A}^{2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+\gamma_{n/2}).$

∎

###### Proof of Theorem 5.

Note that

$\displaystyle B_{a_{1},a_{2}}(p,q)\leq
B_{a_{1},a_{2}}(p,p)=a_{1}-a_{2}(p-p^{2})\leq a_{1}+a_{2}(|p|+|p|^{2}),$

thus

$\displaystyle\mathcal{B}=\sum_{i=1}^{n}\mathbb{E}[\pi_{i}]$
$\displaystyle=\sum_{i=1}^{n}\mathbb{E}[B_{a_{1},a_{2}}\left(A^{\prime}(\langle\mathbf{x}_{i},\bar{\theta}^{P}(\hat{D}^{b})\rangle),A^{\prime}(\langle\mathbf{x}_{i},\mathbb{E}_{\theta\sim
p(\theta|\hat{D}_{i})}[\theta]\rangle)\right)|D_{i},c_{i}]$ $\displaystyle\leq
n(a_{1}+a_{2}(M_{A}+M_{A}^{2})).$

∎

###### Proof of Corollary 1.

The response moment polytope for the real-valued response variable is
$\mathcal{M}=\mathbb{R}$. Thus its interior is
$\mathcal{M}^{\circ}=\mathbb{R}$. We set $\bar{\mathcal{M}}=\mathbb{R}$, so
that
$\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{i})=\widetilde{y}_{i},\varepsilon_{\bar{\mathcal{M}}}=0$.
To bound $\kappa_{A,0},\kappa_{A,1},\kappa_{A,2},M_{A}$, we first compute that
$A^{\prime}(a)=a$, $(A^{\prime})^{-1}(a)=a$,
$[(A^{\prime})^{-1}]^{\prime}(a)=1$, $A^{\prime\prime}(a)=1$. Note that
$\mathcal{M}^{\prime}=[-\tau_{\theta}\tau_{1},\tau_{\theta}\tau_{1}]=[-C\sigma\tau_{\theta}\sqrt{\log
n},C\sigma\tau_{\theta}\sqrt{\log n}]$, thus we have

$\kappa_{A,0}=1,\kappa_{A,1}=\tau_{2},\kappa_{A,2}=1,M_{A}=C\sigma\tau_{\theta}\sqrt{\log
n}.$

For any $\delta\in(\frac{1}{4},\frac{1}{3})$ and $c>0$, we set
$\varepsilon=n^{-\delta}$, $\tau_{2}=n^{\frac{1-3\delta}{2}}$,
$\alpha=\Theta(n^{-3\delta})$, $\beta=\Theta(n^{-c})$ ,
$a_{2}=O(n^{-4\delta})$, and
$a_{1}=a_{2}(M_{A}+3M_{A}^{2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$.
Then, by Lemma 3, the sensitivity of the private estimator is
$\Delta_{n}=\widetilde{O}(\tau_{2}n^{-\frac{1}{2}})=\widetilde{O}(n^{-\frac{3\delta}{2}})$.
Since for any $\delta\in(\frac{1}{4},\frac{1}{3})$ we always have
$\frac{1-3\delta}{2}<\frac{1}{4}$, which means $\tau_{2}=O(n^{\frac{1}{4}})$,
by Lemma 4 we obtain $\lambda_{n}=O(1)$,
$\|\bar{\theta}(D)-\theta^{*}\|_{2}=\widetilde{O}(n^{-\frac{1}{2}})$.

Recall that by Theorem 3, the private estimator is
$\widetilde{O}(\alpha^{2}\kappa_{A,1}^{2}nd+\frac{\kappa_{A,1}^{2}d^{3}}{\varepsilon^{2}n}+\frac{\lambda_{n}^{2}}{n})$-accurate.
Note that
$\widetilde{O}(\alpha^{2}\kappa_{A,1}^{2}nd)=\widetilde{O}(n^{-9\delta+2})$,
$\widetilde{O}(\frac{\kappa_{A,1}^{2}d^{3}}{\varepsilon^{2}n})=\widetilde{O}(n^{-\delta})$,
$\widetilde{O}(\frac{\lambda_{n}^{2}}{n})=\widetilde{O}(n^{-1})$. Since for
any $\delta\in(\frac{1}{4},\frac{1}{3})$ it holds that
$-1<-9\delta+2<-\delta$, we obtain
$\mathbb{E}\|\bar{\theta}^{P}(\hat{D})-\theta^{*}\|_{2}^{2}=\widetilde{O}(n^{-\delta})$.
To bound the expected budget, we first bound the threshold value
$\tau_{\alpha,\beta}$ and the term
$\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$. By Lemma 14,
$\tau_{\alpha,\beta}\leq\frac{1}{\lambda}\log\frac{1}{\alpha\beta}=\Theta(\frac{3\delta+c}{\lambda}\log
n)=\widetilde{\Theta}(1)$. If
$F(\varepsilon,\gamma)=(1+\gamma)\varepsilon^{4}$, then
$\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})=\widetilde{O}(n^{-4\delta})$.
Recall that by Theorem 2, the first term of truthfulness bound is
$a_{2}\kappa_{2}^{2}(\alpha^{2}\kappa_{A,1}^{2}nd+\frac{\lambda_{n}^{2}}{n}+\frac{\kappa_{A,1}^{2}d^{3}}{n\varepsilon^{2}})=\widetilde{O}(n^{-5\delta})$,
thus
$\eta=\widetilde{O}(n^{-5\delta}+n^{-4\delta})=\widetilde{O}(n^{-4\delta})$.
By the choice of $a_{1}$ and Theorem 4, the mechanism is individual rational
for at least $1-O(n^{-3\delta})$ fraction of agents. By Theorem 5, the total
expected budget is
$\mathcal{B}=\widetilde{O}(na_{2}(2M_{A}+4M_{A}^{2})+n\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2}))=\widetilde{O}(n^{-4\delta+1})$.
∎

###### Proof of Corollary 2.

The response moment polytope for the binary response variable $y\in\\{-1,1\\}$
is $\mathcal{M}=[-1,1]$. Thus, its interior is given by
$\mathcal{M}^{\circ}=(-1,1)$. For the closed subset of $\mathcal{M}^{\circ}$,
we define it as
$\bar{\mathcal{M}}=[-1+\varepsilon^{\prime},1-\varepsilon^{\prime}]$ for some
$\varepsilon^{\prime}\in(0,1)$. Then, we can easily compute that
$\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{i})=\widetilde{y}_{i}(1-\varepsilon^{\prime})$,
$\varepsilon_{\bar{\mathcal{M}}}=\varepsilon^{\prime}$. Since $|y|\leq 1$,
here we can just set $\tau_{2}=1$. To bound
$\kappa_{A,0},\kappa_{A,1},\kappa_{A,2},M_{A}$, we first compute that
$A^{\prime}(a)=\frac{e^{2a}-1}{e^{2a}+1}$,
$(A^{\prime})^{-1}(a)=\frac{1}{2}\log\frac{1+a}{1-a}$.
$[(A^{\prime})^{-1}]^{\prime}(a)=\frac{1}{1-a^{2}}$,
$A^{\prime\prime}(a)=\frac{4}{(e^{a}+e^{-a})^{2}}$. Note that
$\mathcal{M}^{\prime}=[-\frac{e^{2C\sigma\tau_{\theta}\sqrt{\log
n}}-1}{e^{2C\sigma\tau_{\theta}\sqrt{\log
n}}+1},\frac{e^{2C\sigma\tau_{\theta}\sqrt{\log
n}}-1}{e^{2C\sigma\tau_{\theta}\sqrt{\log n}}+1}]$, then we have

$\displaystyle\kappa_{A,0}=\max_{a\in\mathcal{M}^{\prime}\cup\bar{\mathcal{M}}}|[(A^{\prime})^{-1}]^{\prime}(a)|=\max_{a\in\mathcal{M}^{\prime}\cup\bar{\mathcal{M}}}\frac{1}{2}(\frac{1}{1-a}+\frac{1}{1+a})$
$\displaystyle<\max\\{\frac{1}{2}+\frac{1}{2}e^{2C\sigma\tau_{\theta}\sqrt{\log
n}},\frac{1}{\varepsilon^{\prime}}\\}=\max\\{\frac{1}{2}+\frac{1}{2}n^{\frac{2C\sigma\tau_{\theta}}{\sqrt{\log
n}}},\frac{1}{\varepsilon^{\prime}}\\},$
$\displaystyle\kappa_{A,1}=\frac{1}{2}\log\frac{2-\varepsilon^{\prime}}{\varepsilon^{\prime}},\kappa_{A,2}\leq
1,M_{A}\leq 1.$

For any $\delta\in(\frac{1}{4},\frac{1}{2})$, we choose
$\varepsilon^{\prime}=2n^{-\delta}$ and let $n\geq
e^{(\frac{2C\sigma\tau_{\theta}}{\delta})^{2}}$ then
$\kappa_{A,0}=O(n^{\delta})$, $\kappa_{A,1}=\widetilde{O}(1)$. We set
$\varepsilon=n^{-\delta}$, $\alpha=\Theta(n^{-3\delta})$,
$\beta=\Theta(n^{-c})$ for any $c>0$, $a_{2}=n^{-4\delta}$,
$a_{1}=a_{2}(M_{A}+3M_{A}^{2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$.
Then, by Lemma 3, the sensitivity of the private estimator is
$\Delta_{n}=\widetilde{O}(n^{-\frac{1}{2}})$. Then, by Lemma 4, we have
$\lambda_{n}=\widetilde{O}(\kappa_{A,0})=\widetilde{O}(n^{\delta})$ and
$\|\bar{\theta}(D)-\theta^{*}\|_{2}=\widetilde{O}(n^{-\frac{1-2\delta}{2}})$.
Note that $\alpha^{2}\kappa_{A,1}^{2}nd=\widetilde{O}(n^{-6\delta+1})$,
$\frac{\kappa_{A,1}^{2}d^{3}}{\varepsilon^{2}n}=n^{-1+2\delta}$,
$\frac{\lambda_{n}^{2}}{n}=\widetilde{O}(n^{-1+2\delta})$. Since for any
$\delta\in(\frac{1}{4},\frac{1}{2})$ it holds that $-6\delta+1<-1+2\delta$, by
Theorem 3, we obtain
$\mathbb{E}[\|\bar{\theta}^{P}(\hat{D})-\theta^{*}\|_{2}^{2}]=\widetilde{O}(n^{-1+2\delta})$.
By Lemma 14 and the assumption that
$F(\varepsilon,\gamma)=(1+\gamma)\varepsilon^{4}$,
$\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})=\widetilde{O}(n^{-4\delta})$.
Note that
$a_{2}\kappa_{A,2}^{2}(\alpha^{2}\kappa_{A,1}^{2}nd+\frac{\lambda_{n}^{2}}{n}+\frac{\kappa_{A,1}^{2}d^{3}}{n\varepsilon^{2}})=\widetilde{O}(n^{-1-2\delta})=\widetilde{O}(n^{-4\delta})$,
thus by Theorem 2, $\eta=\widetilde{O}(n^{-4\delta})$. By the choice of
$a_{1}$ and Theorem 4, the mechanism is individual rational for at least
$1-O(n^{-3\delta})$ fraction of agents. By Theorem 5, the total expected
budget is
$\mathcal{B}=\widetilde{O}(na_{2}(2M_{A}+4M_{A}^{2})+n\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2}))=\widetilde{O}(n^{-4\delta+1})$.
∎

###### Proof of Corollary 3.

In this case, the response moment polytope for the count-valued
$y\in\\{0,1,2,\cdots\\}$ is $\mathcal{M}=[0,+\infty)$. Thus, its interior is
given by $\mathcal{M}^{\circ}=(0,+\infty)$. For the closed subset of the
interior, we define $\bar{\mathcal{M}}=[\varepsilon^{\prime},+\infty)$, for
some $\varepsilon^{\prime}\in(0,1)$, and thus
$\Pi_{\bar{\mathcal{M}}}(\widetilde{y}_{i})=\mathbf{1}_{\\{\widetilde{y}_{i}=0\\}}\varepsilon^{\prime}+\mathbf{1}_{\\{\widetilde{y}_{i}\neq
0\\}}\widetilde{y}_{i}$,
$\varepsilon_{\bar{\mathcal{M}}}=\varepsilon^{\prime}$. To bound
$\kappa_{A,0},\kappa_{A,1},\kappa_{A,2},M_{A}$, we compute that
$A^{\prime}(a)=e^{a}$, $(A^{\prime})^{-1}(a)=\log a$,
$[(A^{\prime})^{-1}]^{\prime}(a)=\frac{1}{a}$, $A^{\prime\prime}(a)=e^{a}$.
Note that $\mathcal{M}^{\prime}=[e^{-C\sigma\tau_{\theta}\sqrt{\log
n}},e^{C\sigma\tau_{\theta}\sqrt{\log n}}]$, then we have

$\displaystyle\kappa_{A,0}=\max_{a\in\mathcal{M}^{\prime}\cup\bar{\mathcal{M}}}|[(A^{\prime})^{-1}]^{\prime}(a)|=\max_{a\in\mathcal{M}^{\prime}\cup\bar{\mathcal{M}}}|\frac{1}{a}|=\max\\{e^{C\sigma\tau_{\theta}\sqrt{\log
n}},\frac{1}{\varepsilon^{\prime}}\\}=\max\\{n^{\frac{C\sigma\tau_{\theta}}{\sqrt{\log
n}}},\frac{1}{\varepsilon^{\prime}}\\}$
$\displaystyle\kappa_{A,1}=\max\\{|\log\varepsilon^{\prime}|,|\log\tau_{2}|\\},\quad\kappa_{A,2}=M_{A}=n^{\frac{C\sigma\tau_{\theta}}{\sqrt{\log
n}}}.$

For any $\delta\in(\frac{1}{4},\frac{1}{3})$, set
$\varepsilon^{\prime}=n^{-\delta}$, then when $n\geq
e^{(\frac{C\sigma\tau_{\theta}}{\delta})^{2}}$, we have
$\kappa_{A,0}=O(n^{\delta})$. Also $\kappa_{A,2}=M_{A}=O(n^{\delta})$. We
choose $\varepsilon=n^{-3\delta}$, $\tau_{2}=\Theta(n^{\frac{1}{4}})$,
$\alpha=\Theta(n^{-3\delta})$, , $\beta=\Theta(n^{-c})$ for any $c>0$,
$a_{2}=n^{-6\delta}$, and
$a_{1}=a_{2}(M_{A}+3M_{A}^{2})+\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})$.
By Lemma 3, the sensitivity of the private estimator is
$\Delta_{n}=\widetilde{O}(n^{-\frac{1}{2}})$. Then, recall that by Lemma 4,
$\lambda_{n}=\widetilde{O}(\kappa_{A,0}(\sqrt{\kappa_{A,2}+\frac{1}{\tau_{2}^{2}}}+(M_{A}+\tau_{2})\sqrt[4]{\frac{1}{n}}+\varepsilon_{\bar{\mathcal{M}}}))$.
We have $\sqrt{\kappa_{2}+\frac{1}{\tau_{2}^{2}}}=O(n^{\frac{\delta}{2}})$,
$(M_{A}+\tau_{2})\sqrt[4]{\frac{1}{n}}=O(n^{-\frac{1}{4}+\delta})=O(n^{\frac{\delta}{2}})$,
$\varepsilon_{\bar{\mathcal{M}}}=O(1)$. Thus,
$\lambda_{n}=\widetilde{O}(n^{\frac{3\delta}{2}})$ and
$\|\bar{\theta}(D)-\theta^{*}\|_{2}=\widetilde{O}(n^{-\frac{1-3\delta}{2}})$.
Nota that $\alpha^{2}\kappa_{A,1}^{2}nd=\widetilde{O}(n^{-6\delta+1})$,
$\frac{\kappa_{A,1}^{2}d^{3}}{\varepsilon^{2}n}=\widetilde{O}(n^{-1+2\delta})$,
$\frac{\lambda_{n}^{2}}{n}=\widetilde{O}(n^{-1+3\delta})$. For any
$\delta\in(\frac{1}{4},\frac{1}{3})$, it holds that
$-6\delta+1<-1+2\delta<-1+3\delta$, thus by Theorem 3, we obtain
$\mathbb{E}\|\hat{\theta}^{P}(\hat{D})-\theta^{*}\|_{2}^{2}=\widetilde{O}(n^{-1+3\delta})$.
By Lemma 14 and the assumption that
$F(\varepsilon,\gamma)=(1+\gamma)\varepsilon^{4}$,
$\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2})=\widetilde{O}(n^{-4\delta})$.
Note that
$a_{2}\kappa_{A,2}^{2}(\alpha^{2}\kappa_{A,1}^{2}nd+\frac{\lambda_{n}^{2}}{n}+\frac{\kappa_{A,1}^{2}d^{3}}{n\varepsilon^{2}})=\widetilde{O}(n^{-1-\delta})=\widetilde{O}(n^{-4\delta})$,
thus by Theorem 2, $\eta=\widetilde{O}(n^{-4\delta})$. By the choice of
$a_{1}$ and Theorem 4, the mechanism is individual rational for at least
$1-O(n^{-3\delta})$ fraction of agents. By Theorem 5, the total expected
budget is
$\mathcal{B}=\widetilde{O}(na_{2}(2M_{A}+4M_{A}^{2})+n\tau_{\alpha,\beta}F(2\varepsilon,\gamma_{n}+2\gamma_{n/2}))=\widetilde{O}(n^{-4\delta+1})$.
∎

###### Proof of Lemma 5.

We apply the same techniques as in the proof of Lemma 3. Let $D$ and
$D^{\prime}$ be two arbitrary neighboring datasets that differ only on the
last agent’s dataset. First,

$\displaystyle\|\frac{\widetilde{X}^{T}\widetilde{y}}{n}\|_{2}$
$\displaystyle\leq\frac{1}{n}\|\widetilde{X}^{T}\|_{2}\|\widetilde{y}\|_{2}=\frac{1}{n}\sup_{v\in\mathcal{S}^{n-1}}\|\widetilde{X}^{T}v\|_{2}\|\widetilde{y}\|_{2}$
$\displaystyle=\frac{1}{n}\sup_{v\in\mathcal{S}^{n-1}}\|\sum_{i\in[n]}\mathbf{\widetilde{x}}_{i}v_{i}\|_{2}\|\widetilde{y}\|_{2}\leq\frac{1}{n}\sup_{v\in\mathcal{S}^{n-1}}\sum_{i\in[n]}\|\mathbf{\widetilde{x}}_{i}\|_{2}|v_{i}|\|\widetilde{y}\|_{2}$
$\displaystyle\leq\frac{1}{n}\sup_{v\in\mathcal{S}^{n-1}}\sum_{i\in[n]}d^{\frac{1}{4}}\|\widetilde{\mathbf{x}}_{i}\|_{4}|v_{i}|\|\widetilde{y}\|_{2}\leq\frac{d^{\frac{1}{4}}\tau_{1}\tau_{2}}{\sqrt{n}}\sup_{v\in\mathcal{S}^{n-1}}\sum_{i\in[n]}|v_{i}|\leq
d^{\frac{1}{4}}\tau_{1}\tau_{2}.$

Then we bound the sensitivity of
$\|\frac{\widetilde{X}^{T}\widetilde{y}}{n}\|_{2}$,

$\displaystyle\|\frac{\widetilde{X}^{T}\widetilde{y}}{n}-\frac{\widetilde{X}^{\prime^{T}}\widetilde{y}^{\prime}}{n}\|_{2}=\frac{1}{n}\|\mathbf{\widetilde{x}}_{n}\widetilde{y}_{n}-\mathbf{\widetilde{x}}_{n}^{\prime}\widetilde{y}_{n}^{\prime}\|_{2}\leq\frac{1}{n}(\|\mathbf{\widetilde{x}}_{n}\|_{2}|\widetilde{y}_{n}|+\|\mathbf{\widetilde{x}}_{n}^{\prime}\|_{2}|\widetilde{y}_{n}^{\prime}|)\leq\frac{2d^{\frac{1}{4}}\tau_{1}\tau_{2}}{n}.$

For any nonzero vector $w\in\mathbb{R}^{d}$,

$\displaystyle\quad\|\frac{\widetilde{X}^{T}\widetilde{X}}{n}w\|_{2}=\|\frac{\widetilde{X}^{T}\widetilde{X}}{n}w-\Sigma
w+\Sigma w\|_{2}$ $\displaystyle\geq\|\Sigma
w\|_{2}-\|(\frac{\widetilde{X}^{T}\widetilde{X}}{n}-\Sigma)w\|_{2}\geq(\kappa_{2}-\|\frac{\widetilde{X}^{T}\widetilde{X}}{n}-\Sigma\|_{2})\|w\|_{2}.$
(28)

By Lemma 17, when $\tau_{1}=\Theta((n/\log n)^{1/4})$, with probability at
least $1-dn^{-C_{0}}$ we have
$\|\frac{\widetilde{X}^{T}\widetilde{X}}{n}-\Sigma\|_{2}\leq
2\sqrt{\frac{Rd\log n}{n}}$. Thus when $n$ is sufficiently large such that
$2\sqrt{\frac{Rd\log n}{n}}\leq\frac{\kappa_{2}}{2}$, we have
$\|\frac{\widetilde{X}^{T}\widetilde{X}}{n}-\Sigma\|_{2}\leq\frac{\kappa_{2}}{2}$.
Combining this inequality and (28) delivers that
$\|\frac{\widetilde{X}^{T}\widetilde{X}}{n}w\|_{2}\geq\frac{\kappa_{2}}{2}\|w\|_{2}$,
which implies
$\|(\frac{\widetilde{X}^{T}\widetilde{X}}{n})^{-1}\|_{2}\leq\frac{2}{\kappa_{2}}$.
Thus,

$\displaystyle\|(\frac{\widetilde{X}^{T}\widetilde{X}}{n})^{-1}-(\frac{\widetilde{X}^{\prime^{T}}\widetilde{X}^{\prime}}{n})^{-1}\|_{2}$
$\displaystyle\leq\|(\frac{\widetilde{X}^{T}\widetilde{X}}{n})^{-1}\|_{2}\|(\frac{\widetilde{X}^{\prime^{T}}\widetilde{X}^{\prime}}{n})^{-1}\|_{2}\|\frac{\widetilde{X}^{T}\widetilde{X}}{n}-\frac{\widetilde{X}^{\prime^{T}}\widetilde{X}^{\prime}}{n}\|_{2}$
$\displaystyle\leq\frac{4}{\kappa_{2}^{2}}(\|\frac{\widetilde{X}^{T}\widetilde{X}}{n}-\Sigma\|_{2}+\|\Sigma-\frac{\widetilde{X}^{\prime^{T}}\widetilde{X}^{\prime}}{n}\|_{2})\leq\frac{8}{\kappa_{2}^{2}}\sqrt{\frac{Rd\log
n}{n}}.$

By applying the inequality $\|AB-A^{\prime}B^{\prime}\|_{2}=\|AB-
AB^{\prime}+AB^{\prime}-A^{\prime}B^{\prime}\|_{2}\leq\|A\|_{2}\|B-B^{\prime}\|_{2}+\|A-A^{\prime}\|_{2}\|B^{\prime}\|_{2}$
and setting $\tau_{2}=\Theta((n/\log n)^{1/8})$ we have

$\displaystyle\|\hat{\theta}(D)-\hat{\theta}(D^{\prime})\|_{2}$
$\displaystyle=\|(\frac{\widetilde{X}^{T}\widetilde{X}}{n})^{-1}\frac{\widetilde{X}^{T}\widetilde{y}}{n}-(\frac{\widetilde{X}^{\prime^{T}}\widetilde{X}^{\prime}}{n})^{-1}\frac{\widetilde{X}^{\prime^{T}}\widetilde{y}^{\prime}}{n}\|_{2}$
$\displaystyle\leq\frac{8d^{\frac{1}{4}}\tau_{1}\tau_{2}}{\kappa_{2}^{2}}\sqrt{\frac{Rd\log
n}{n}}+\frac{4d^{\frac{1}{4}}\tau_{1}\tau_{2}}{\kappa_{2}n}=O(d^{\frac{3}{4}}(\frac{\log
n}{n})^{\frac{1}{8}}).$ (29)

∎

###### Proof of Lemma 6.

Note that by the proof of Lemma 5, when $n$ is sufficiently large such that
$2\sqrt{\frac{Rd\log n}{n}}\leq\frac{\kappa_{2}}{2}$, with probability at
least $1-dn^{-C_{0}}$, we have
$\|(\frac{\widetilde{X}^{T}\widetilde{X}}{n})^{-1}\|_{2}\leq\frac{2}{\kappa_{2}}$.
Thus,

$\displaystyle\|\hat{\theta}(D)-\theta^{*}\|_{2}$
$\displaystyle=\|\theta^{*}-\big{(}\frac{\widetilde{X}^{T}\widetilde{X}}{n}\big{)}^{-1}\frac{\widetilde{X}^{T}\widetilde{y}}{n}\|_{2}$
$\displaystyle\leq\|\big{(}\frac{\widetilde{X}^{T}\widetilde{X}}{n}\big{)}^{-1}\|_{2}\|\big{(}\frac{\widetilde{X}^{T}\widetilde{X}}{n}\big{)}\theta^{*}-\frac{\widetilde{X}^{T}\widetilde{y}}{n}\|_{2}$
$\displaystyle\leq\frac{2}{\kappa_{2}}\|\frac{\widetilde{X}^{T}}{n}\\{\widetilde{X}\theta^{*}-\widetilde{y}\\}\|_{2}$
$\displaystyle\leq\frac{2\sqrt{d}}{\kappa_{2}}\max_{j\in[d]}|\frac{1}{n}\sum_{i=1}^{n}\widetilde{x}_{ij}(\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle-\widetilde{y}_{i})|.$
(30)

Next we bound
$|\frac{1}{n}\sum_{i=1}^{n}\widetilde{x}_{ij}(\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle-\widetilde{y}_{i})|$.

$\displaystyle\quad|\frac{1}{n}\sum_{i=1}^{n}\widetilde{x}_{ij}(\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle-\widetilde{y}_{i})|$
$\displaystyle\leq|\frac{1}{n}\sum_{i=1}^{n}\widetilde{x}_{ij}\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle-\mathbb{E}[\widetilde{x}_{ij}\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle]|+|\mathbb{E}[\widetilde{x}_{ij}\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle]-\mathbb{E}[\widetilde{x}_{ij}\widetilde{y}_{i}]|+|\frac{1}{n}\sum_{i=1}^{n}\widetilde{x}_{ij}\widetilde{y}_{i}-\mathbb{E}[\widetilde{x}_{ij}\widetilde{y}_{i}]|$
$\displaystyle\equiv\text{I}+\text{II}+\text{III}.$

Under the assumption that $\mathbb{E}(\nu^{T}\mathbf{x}_{i})^{4}\leq R_{1}$
for any $\nu\in\mathcal{S}^{d-1}$, if
$\nu=\frac{\mathbf{x}_{i}}{\|\mathbf{x}_{i}\|_{2}}$, then
$\mathbb{E}\|\mathbf{x}_{i}\|_{2}^{4}\leq R_{1}$; if $\nu=e_{j}$ for any
$j\in[d]$ ($e_{j}$ is the unit vector whose $j$-th element is $1$), then
$\mathbb{E}|x_{ij}|^{4}\leq R_{1}$ and thus
$\mathbb{E}\|\mathbf{x}_{i}\|_{4}^{4}=\sum_{j=1}^{d}\mathbb{E}|x_{ij}|^{4}\leq
dR_{1}$. Since

$\displaystyle|\frac{1}{n}(\widetilde{x}_{ij}\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle-\mathbb{E}[\widetilde{x}_{ij}\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle])|\leq\frac{2}{n}|\widetilde{x}_{ij}|\|\widetilde{\mathbf{x}}_{i}\|_{2}\|\theta^{*}\|_{2}\leq\frac{2d^{\frac{1}{4}}\tau_{1}^{2}\tau_{\theta}}{n},$

and

$\displaystyle\mathrm{var}(\frac{1}{n}(\widetilde{x}_{ij}\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle-\mathbb{E}[\widetilde{x}_{ij}\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle]))\leq\frac{1}{n^{2}}\mathbb{E}|\widetilde{x}_{ij}|^{2}\|\mathbf{\widetilde{x}}_{i}\|_{2}^{2}\|\theta^{*}\|_{2}^{2}\leq\frac{\tau_{\theta}^{2}}{n^{2}}\mathbb{E}\|\mathbf{x}_{i}\|_{2}^{4}\leq\frac{\tau_{\theta}^{2}R_{1}}{n^{2}},$

by Bernstein’s inequality (Lemma 10), we obtain for any $t>0$,

$\displaystyle\mathbb{P}\left(\text{I}>\frac{4d^{\frac{1}{4}}\tau_{\theta}\tau_{1}^{2}t}{3n}+\sqrt{\frac{2R_{1}\tau_{\theta}^{2}t}{n}}\right)\leq
2\exp(-t).$ (31)

Next we bound II.

II
$\displaystyle=|\mathbb{E}\widetilde{x}_{ij}(\langle\widetilde{\mathbf{x}}_{i},\theta^{*}\rangle-\widetilde{y}_{i})|$
$\displaystyle\leq|\mathbb{E}\widetilde{x}_{ij}\langle\widetilde{\mathbf{x}}_{i}-\mathbf{x}_{i},\theta^{*}\rangle|+|\mathbb{E}\widetilde{x}_{ij}(\langle\mathbf{x}_{i},\theta^{*}\rangle-
y_{i})|+|\mathbb{E}\widetilde{x}_{ij}(y_{i}-\widetilde{y}_{i})|$
$\displaystyle\leq\mathbb{E}|\widetilde{x}_{ij}|\|\mathbf{\widetilde{x}}_{i}-\mathbf{x}_{i}\|_{2}\|\theta^{*}\|_{2}+|\mathbb{E}_{\mathbf{x}_{i}}[\widetilde{x}_{ij}\mathbb{E}_{y_{i}}[\langle\mathbf{x}_{i},\theta^{*}\rangle-
y_{i}]]|+\mathbb{E}|\widetilde{x}_{ij}(y_{i}-\widetilde{y}_{i})|$
$\displaystyle\leq\tau_{\theta}\mathbb{E}|\widetilde{x}_{ij}|\|\mathbf{\widetilde{x}}_{i}-\mathbf{x}_{i}\|_{2}\mathbf{1}_{\\{\|\mathbf{x}_{i}\|_{4}>\tau_{1}\\}}+\mathbb{E}|\widetilde{x}_{ij}(y_{i}-\widetilde{y}_{i})\mathbf{1}_{\\{|y_{i}|>\tau_{2}\\}}|$