# Minimax rate for multivariate data under componentwise local differential
privacy constraints

Chiara Amorino Arnaud Gloter  Université du Luxembourg, L-4364 Esch-Sur-
Alzette, Luxembourg. The author gratefully acknowledges financial support of
ERC Consolidator Grant 815703 “STAMFORD: Statistical Methods for High
Dimensional Diffusions”.Laboratoire de Mathématiques et Modélisation d’Evry,
CNRS, Univ Evry, Université Paris-Saclay, 91037, Evry, France.

###### Abstract

Our research analyses the balance between maintaining privacy and preserving
statistical accuracy when dealing with multivariate data that is subject to
componentwise local differential privacy (CLDP). With CLDP, each component of
the private data is made public through a separate privacy channel. This
allows for varying levels of privacy protection for different components or
for the privatization of each component by different entities, each with their
own distinct privacy policies. It also covers the practical situations where
it is impossible to privatize jointly all the components of the raw data. We
develop general techniques for establishing minimax bounds that shed light on
the statistical cost of privacy in this context, as a function of the privacy
levels $\alpha_{1},\dots,\alpha_{d}$ of the $d$ components.
We demonstrate the versatility and efficiency of these techniques by
presenting various statistical applications. Specifically, we examine
nonparametric density and covariance estimation under CLDP, providing upper
and lower bounds that match up to constant factors, as well as an associated
data-driven adaptive procedure. Furthermore, we quantify the probability of
extracting sensitive information from one component by exploiting the fact
that, on another component which may be correlated with the first, a smaller
degree of privacy protection is guaranteed.

Keywords: local differential privacy, minimax optimality, rate of convergence,
non parametric estimation, density estimation

AMS 2010 subject classifications: Primary 62C20, secondary 62G07, 62H05

##  1 Introduction

In the current era of information technology, protecting data privacy has
become a significant challenge for statistical inference. With the widespread
collection and storage of massive amounts of data, including medical records,
social media activity and smartphone user behavior, individuals are
increasingly reluctant to share sensitive information with companies or state
officials. To address this issue, researchers in computer science and related
fields have produced a vast literature on constructing privacy-preserving data
release mechanisms. Real-world applications have also emerged, with companies
such as Apple [38], Google [24] and Microsoft [13] developing data analysis
methodologies that achieve strong statistical performance while maintaining
individuals’ privacy. This interest has been driven by regulatory pressure and
the need to comply with privacy laws (see for example [26, 2]).

A highly effective method of protecting data from privacy breaches consists in
differential privacy (see the landmarks [22, 23] as well as [21, 25]). It
involves the use of randomized data perturbation, where the original data is
replaced with a modified version that maintains the overall statistical
properties of the original data, but is different enough to prevent individual
data points from being identifiable. This approach offers a high degree of
plausible deniability to data providers, as they can argue that their true
answer was different from the one provided.

There are two main types of differential privacy: local privacy and central
privacy. Local privacy involves privatizing data before sharing it with a data
collector, while central privacy involves a centralized curator who maintains
the sample and guarantees that any information it releases is appropriately
private. While the local model provides stronger privacy protections, it also
involves some loss of statistical efficiency. Nevertheless, major technology
companies such as Apple and Google (see [3] and [1], respectively) have
adopted local differential privacy protections in their data collection and
machine learning tools to protect sensitive data. In this paper, the focus is
on the local version of differential privacy, which is formally defined in
Section 2.

Recently, there has been growing interest in studying differential privacy
from a statistical inference perspective. The seminal work by Warner [40]
introduced randomized responses, which have since become one of the primary
randomization techniques employed in differential privacy. However, modern
research has produced mechanisms for a wide range of statistical problems,
including mean and median estimation in [19], hypothesis testing (see for
example [30, 29, 4, 32]), robustness [34], change point analysis [6, 33] and
nonparametric estimation [12, 11, 31, 5], among others. In light of the
increasing significance of data protection, it is crucial to find a balance
between statistical utility and privacy: it is essential to ensure that data
remains protected from privacy breaches while also allowing for the extraction
of useful information and insights. Therefore, finding the optimal balance
between these two aspects has become increasingly important.

This paper examines $n$ independent and identically distributed multivariate
datasets with law $\bm{X}=(X^{1},\dots,X^{d})$, subject to what we call
componentwise local differential privacy constraints. Componentwise local
differential privacy (CLDP) is a term here introduced and refers to the method
of separately making each component public through different privacy channels.
This approach can be beneficial as different components may require varying
levels of privacy protection or can not be privatized jointly. We denote by
$\alpha_{j}$ the amount of privacy ensured to the component $X^{j}$.
Intuitively, $\alpha_{j}=0$ guarantees perfect privacy while as $\alpha_{j}$
increases towards infinity, the privacy constraints become less strict. The
reader can refer to Equation (2.2) for a precise definition. The study focuses
on exploring the trade-off between privacy protection and efficient
statistical inference and aims to determine the optimal mechanisms for
preserving privacy in this context.

Let us take the example where data is collected from $n$ individuals,
comprising $d$ different aspects of their life. For instance, one component
could represent data related to sport practice, which is widely available on
phone applications, while another component could concern medical expenses. It
is evident that disclosing information about the first component has a
different impact than disclosing the same about the second, given that
maintaining high confidentiality for medical bills is more important. Since
some of the components may be correlated, it is necessary to work within a
framework that takes this into account. One could wonder if it is possible to
extract sensitive information on one component by taking advantage of the fact
that on another component, possibly correlated to the first, a smaller amount
of privacy is guaranteed.
We give a first answer to this question in Proposition 4.1, where we quantify
the amount of private information $X^{1}$ carried by the privatized views of
the other components in term of the dependence of $(X^{2},\dots,X^{d})$ on
$X^{1}$ and of privacy levels $\alpha_{1}$, $\bar{\alpha}$, where
$\bar{\alpha}$ is an upper bound for the levels of privacy ensured on the
components $X^{2},\dots,X^{d}$.

Related to the issue of a varying level of privacy, the reference [41] studies
the problem of regression estimation when only the response variables are
considered as private. However, this situation is extreme as only one
component is sent through a channel and it does not compare to ours, where
privacy is kept for all the variables. Also, an emerging literature [7]
studies the situation where a subset of individuals in the sample allows to
access their raw data. In such scenario the privacy constraint is not constant
through the sample, but the situation is different with our case where the
privacy level is varying through the different variables. In [16], the authors
establish results in the case where the privacy parameter can have the same
size as the dimension $d$. Specifically, in Section 3, they investigate how
the estimation of $d$-dimensional quantities is affected by the presence or
absence of correlation among the coordinates.

Our research is also motivated by situations where different components can
not be privatized jointly. It may occur when practical aspects prevent the
joint components to be gathered by the same organism prior to the
privatisation mechanism. Consider the situation where two different entities
have collected data on different aspects of the life of $n$ individuals. These
two entities could be, for instance, a health insurance company and a tax
office having respectively collected health and income data on a population.
Let denote by $(X^{j}_{i})_{i=1,\dots,n}$ the data set belonging to the entity
$j$, with $j\in\\{1,2\\}$ and assume that none of the two entities is disposed
to publicly reveal their data. A statistician interested in inferring the
joint law of $\bm{X}=(X^{1},X^{2})$ would face a componentwise privatisation.
Indeed, each entity can still privatize its own data on the individual $i$,
independently of the knowledge of the data owned by the other entity. Such
mechanism yields to the privatization of the vector
$\bm{X}_{i}=(X^{1}_{i},X^{2}_{i})$ component by component.

These examples are encouraging us to explore the balance between statistical
utility and individual privacy (on a componentwise basis) for the people from
whom data is obtained. By using a framework that considers componentwise local
differential privacy constraints, we are able to identify optimal privacy
mechanisms for some statistical problems and characterize how the optimal rate
of estimation varies as a function of the privacy levels $\alpha_{j}$’s.

With a similar goal in mind but in the case where all the components of one
vector are made public through the same privacy channel, Duchi, Jordan and
Wainwright proposed the private version of the Le Cam, Fano and Assouad lemmas
(see [15, 17, 18, 19]). They provide minimax rates of convergence for specific
estimation problems under privacy constraints through a case-by-case study.
Rohde and Steinberger’s research [36], published in 2020, takes a different
approach by developing a general theory, similar to that of Donoho and Liu in
[14], to characterize the differentially private minimax rate of convergence
using the moduli of continuity.

It is worth highlighting that the minimax approach developed under local
differential privacy constraints in [19] enables the authors to examine the
private minimax rate of estimation for various classical problems, including
mean, median, and density estimation. These bounds have proven to be vital in
other research studies that analyze the impact of privacy constraints on the
convergence rate of various estimation problems, such as those discussed in
[31], [11], [37], or [28], to name a few. The broad range of applications and
their diversity demonstrate the significant impact of such research. However,
despite the existence of multivariate data, there is currently no work that
considers separate components made public with varying levels of privacy and
through independent channels. Our goal is to address this research gap.

The novel contribution of this article is to develop bounds to quantify the
contraction in Kullback-Liebler divergence that arises from passing
multivariate data through $d$ different private channels. These bounds enable
us to understand how the optimal convergence rate varies as a function of the
privacy levels $\alpha_{1}$, …, $\alpha_{d}$, which characterizes the
statistical price of privacy.
We present statistical applications of such bounds to demonstrate their
efficiency and versatility comprehensively. Specifically, we detail the
estimation of density and covariance under componentwise local differential
privacy constraints. Although our main results are proven under the general
framework of sequentially interactive privacy mechanism, we simplify the
notation by considering non-interactive algorithms for the two statistical
problems.

To elaborate, we have two sets of raw data samples
$\bm{X}=(X^{1},\dots,X^{d})$ and
$\bm{\tilde{X}}=(\tilde{X}^{1},\dots,\tilde{X}^{d})$, each drawn from a
probability distribution $P$ and $\tilde{P}$ respectively. We also have two
corresponding sets of privatized samples $\bm{Z}=(Z^{1},\dots,Z^{d})$ and
$\bm{\tilde{Z}}=(\tilde{Z}^{1},\dots,\tilde{Z}^{d})$, where $Z^{j}$ and
$\tilde{Z}^{j}$ are the $\alpha_{j}$-local differential privatized views of
$X^{j}$ and $\tilde{X}^{j}$, respectively. The following equation explains the
closeness of the laws of the privatized samples based on the proximity of the
original laws:

${}d_{KL}(L_{\bm{Z}},L_{\bm{\tilde{Z}}})\leq\Big{(}\sum_{k=1}^{d}\sum_{(j_{1},\dots,j_{k})}\prod_{i=1}^{k}(e^{\alpha_{j_{i}}}-1)d_{TV}(L_{(X^{j_{1}},\dots,X^{j_{k}})},L_{(\tilde{X}^{j_{1}},\dots,\tilde{X}^{j_{k}})})\Big{)}^{2},$
(1.1)

where we refer to (3.1) and (3.2) for a formal definition of the distances
introduced above. Here, $L_{(X^{j_{1}},\dots,X^{j_{k}})}$ represents the law
of the marginals $X^{j_{1}},\dots,X^{j_{k}}$ of $\bm{X}$, and the inner
summation is over $1\leq j_{1}<\dots<j_{k}\leq d$ where any $k$ distinct
indexes in ${1,\dots,d}$ are considered.
This bound is useful for proving lower bounds for statistical problems and so
it will be often used with two specific priors that are chosen by
statisticians. In this case, it is helpful to use priors that have equal $d-1$
marginals, which simplifies the bound above to the following expression

$d_{KL}(L_{\bm{Z}},L_{\bm{\tilde{Z}}})\leq\left(\prod_{j=1}^{d}(e^{\alpha_{j}}-1)d_{TV}(P,\tilde{P})\right)^{2}.$

We can compare our result with Theorem 1 of [19], which assumes that only one
privacy channel has been used (so $\alpha_{1}=\dots=\alpha_{d}=\alpha$). It
provides the result
$d_{KL}(L_{\bm{Z}},L_{\bm{\tilde{Z}}})\leq\min(4,e^{2\alpha})(e^{\alpha}-1)^{2}d_{TV}(P,\tilde{P})^{2}$.
In Section 2.1, we demonstrate that componentwise local differential privacy
with a privacy parameter $\bm{\alpha}=(\alpha,\dots,\alpha)$ can be viewed as
a special case of classical local differential privacy with a privacy
parameter $d\alpha$. Consequently, we can derive a crude bound on (1.1) that
yields the same result as in [19] (see Remark 3.3). However, our findings are
generally more precise, enabling us to recover a refined bound that accurately
assesses the contributions of the differences between each $k$-dimensional
marginal.

Using Equation (1.1), we can analyze the rate of convergence for nonparametric
density estimation of a vector $\bm{X}$ belonging to an Hölder class
$\mathcal{H}(\beta,\mathcal{L})$. We propose a kernel density estimator based
on the observation of privatized variables $Z_{i}^{j}$, where $i=1,\dots,n$
and $j=1,\dots,d$ (refer to (4.20) for details). By imposing the conditions
$\alpha_{j}\leq 1$ and $n\prod_{i=1}^{d}\alpha_{j}^{2}\rightarrow\infty$, we
demonstrate that the $L^{2}$ pointwise error of this estimator reaches the
convergence rate
$(\frac{1}{n\prod_{i=1}^{d}\alpha_{j}^{2}})^{\frac{\beta}{\beta+d}}$. This
rate is optimal in a minimax sense for small $\alpha$ (refer to Theorems 4.18,
4.21 below).
It is natural to compare the convergence rate of our kernel density estimator
with that of non-componentwise local privacy constraints. According to [11]
the latter achieves, for $\alpha<1$, a convergence rate of
$(n(e^{\alpha}-1)^{2})^{-\frac{2\beta}{2\beta+2}}\approx(n\alpha^{2})^{-\frac{\beta}{\beta+1}}$
for estimating the density of a vector $\bm{X}$ belonging to an Hölder class
$\mathcal{H}(\beta,\mathcal{L})$ (see Remark 4.23 below for more details).
Our results are consistent with those in [11] when $d=1$, and they provide
some extensions for $d>1$. In particular, when
$\alpha_{1}=\dots=\alpha_{d}=\alpha$, the role of $\alpha^{2}$ in [11] is
replaced by $\alpha^{2d}$ in our analysis.

Furthermore, we provide a detailed analysis of the estimation of the joint
moment of a $d$-dimensional vector $(X^{1},\dots,X^{d})$ under componentwise
privacy constraints, in addition to the density estimation discussed above.
Here, we again find that under componentwise privacy mechanism, the quality of
the estimation of the joint moment is degraded as $\alpha$ becomes small,
compared to a joint privacy mechanism (see Remark 4.6). We also draw
consequences of these results on the estimation of the covariance and
correlation between two variables under componentwise privacy in Section
4.2.2.

The paper is organized as follows. In Section 2, we provide an introduction to
differential privacy, we present our notation for componentwise local
differential privacy and compare it with the classical local differential
privacy. Our main results are presented in Section 3, where we derive bounds
on divergence between pairs in Section 3.1 and extend them to the case of
interactive privatization of independent sampling in Section 3.2. We
demonstrate the practical application of our results in statistical problems
in Section 4. Firstly, in Section 4.1, we use our techniques to investigate
the precision of revealing one marginal of $\bm{X}$ by observing $\bm{Z}$.
Next, in Section 4.2, we focus on the problem of estimating the joint moment
of a vector : we propose a private estimator and establish upper and lower
bounds for its $L^{2}$ risk in Sections 4.2.1 and 4.2.3, respectively. Section
4.2.2 deals with the application to the estimation of the covariance between
random variables. In Section 4.2.4, we suggest an adaptive procedure for the
estimation of the joint moment. Then, we examine the problem of nonparametric
density estimation in Section 4.3, using a private kernel density estimator.
The convergence rate of the estimator is studied in Section 4.3.1, while in
Section 4.3.2 we establish the minimax optimality of such rate. We conclude
the density estimation section by proposing a data-driven procedure for
bandwidth selection in Section 4.3.3. Finally, all proofs are collected in the
Appendix.

##  2 Problem formulation

We consider $\bm{X}_{1}$,…, $\bm{X}_{n}$ iid data whose law is
$\bm{X}=(X^{1},\dots,X^{d})\in\bm{\mathcal{X}}=\prod_{j=1}^{d}\mathcal{X}^{j}$.
It can represent the information coming from $n$ different individuals, about
$d$ different aspect of their life. For each individual the information is
privatized in a different way. Compared to the literature, where all the
components relative to the same person are made public through the same
channel, we now consider the case where each component is made public
separately, that is why we talk of ”componentwise local differential privacy”
(CLDP).
Let us formalize the framework discussed before. The act of privatizing the
raw samples $(\bm{X}_{i})_{i=1,\dots,n}$ and transforming them into the public
set of samples $(\bm{Z}_{i})_{i=1,\dots,n}$ is modeled by a conditional
distribution, called privacy mechanism or channel distribution. We assume that
each component of a disclosed observation, denoted by $Z_{i}^{j}$, is
privatized separately and belongs to some space $\mathcal{Z}^{j}$, which may
vary depending on the component $j$. This implies that the observation
$\bm{Z}_{i}$ is an element of the product space
$\bm{\mathcal{Z}}:=\prod_{j=1}^{d}\mathcal{Z}^{j}$.
We also assume that the spaces $\mathcal{X}^{j}$ and $\mathcal{Z}^{j}$ are
separable complete metric spaces, with their Borel sigma-fields defining
measurable spaces $(\mathcal{X}^{j},\Xi_{\mathcal{X}^{j}})$ and
$(\mathcal{Z}^{j},\Xi_{\mathcal{Z}^{j}})$, respectively, for all
$j\in\\{1,\dots,d\\}$.

The privacy mechanism is allowed to be sequentially interactive, meaning that
during the privatization of the $j$-th component of the $i$-th observation
$X_{i}^{j}$, all previously privatized values $(\bm{Z}_{m})_{m=1,\dots,i-1}$
are publicly available. This leads to the following conditional independence
structure, for any $j\in\\{1,\dots,d\\}$:

$\\{{X}_{i}^{j},\bm{Z}_{1},\dots,\bm{Z}_{i-1}\\}\rightarrow Z_{i}^{j},\qquad
Z_{i}^{j}\perp
X_{k}^{j}\mid\\{{X}_{i}^{j},\bm{Z}_{1},\dots,\bm{Z}_{i-1}\\}\,\text{ for
}k\neq i.$

More precisely, for $j=1,\dots,d$ and $i=1,\dots,n$, given
$X_{i}^{j}=x_{i}^{j}\in\mathcal{X}^{j}$ and
$\bm{Z}_{m}=\bm{z}_{m}\in\bm{\mathcal{Z}}$ for $m=1,\dots,i-1$; the i-th
privatized output $Z_{i}^{j}\in\mathcal{Z}^{j}$ is drawn as

${}Z_{i}^{j}\sim
Q_{i}^{j}(\cdot|X_{i}^{j}=x_{i}^{j},\bm{Z}_{1}=\bm{z}_{1},\dots,\bm{Z}_{i-1}=\bm{z}_{i-1})$
(2.1)

for Markov kernels
$Q_{i}^{j}:\Xi_{\mathcal{Z}^{j}}\times(\mathcal{X}^{j}\times(\bm{\mathcal{Z}})^{i-1})\rightarrow[0,1]$.
The notation
$(\bm{\mathcal{Z}},\Xi_{\bm{\mathcal{Z}}})=(\prod_{j=1}^{d}\mathcal{Z}^{j},\otimes_{j=1}^{d}\Xi_{\mathcal{Z}^{j}})$
refers to the measurable space of privatized data while
$(\bm{\mathcal{X}},\Xi_{\bm{\mathcal{X}}})=(\prod_{j=1}^{d}\mathcal{X}^{j},\otimes_{j=1}^{d}\Xi_{\mathcal{X}^{j}})$
is the space of sensitive or raw data.
All of the examples presented in Section 4 have raw data that take values in
$\bm{\mathcal{X}}=\mathbb{R}^{d}$. The space of privatized data, denoted by
$\bm{\mathcal{Z}}$, can be quite general, as it is selected by the
statistician based on a specific privatization mechanism. Nonetheless, in all
of the practical examples of privatization that are discussed in Section 4,
the privatized data will be valued in
$\bm{\mathcal{Z}}=\mathbb{R}^{d^{\prime}}$ with $d^{\prime}\geq 1$.

A specific example of the privacy mechanism described earlier is the non-
interactive algorithm, where the value of $Z_{i}^{j}$ is solely dependent on
$X_{i}^{j}$. Therefore, Equation (2.1) no longer contains any correlation with
the previously generated $\bm{Z}$ values. In this scenario, we eliminate any
dependence of the Markov kernels on the observation $i$. However, when
different components represent diverse encrypted information associated with
the same individual, there is no justification for the distinct components to
follow the same distribution. Therefore, it is necessary to consider that
different components may have different laws. In the non-interactive case for
any $j=1,\dots,d$ and for any $i=1,\dots,n$ the privatized output is given by

$Z_{i}^{j}\sim Q^{j}(\cdot|X_{i}^{j}=x_{i}^{j}).$

Although it is usually easier to consider non interactive algorithms, as they
lead to iid privatized sample, in some situations it is useful for the
channel’s output to rely on previous computations. Stochastic approximation
schemes, for instance, necessitate this kind of dependency (see [35]).

It is possible to quantify the privacy through the notion of local
differential privacy. For a given parameter
$\bm{\alpha}=(\alpha_{1},\dots,\alpha_{d}),\,\alpha_{j}\geq 0$, for any
$j\in\\{1,\dots,d\\}$, the random variable $Z_{i}^{j}$ is an
$\alpha_{j}$-differentially locally privatized view of $X_{i}^{j}$ if for all
$\bm{z}_{1},\dots,\bm{z}_{i-1}\in{\color[rgb]{0,0,0}\bm{\mathcal{Z}}}$ and
$x,x^{\prime}\in{\color[rgb]{0,0,0}\mathcal{X}^{j}}$ we have

${}{\sup_{A\in\Xi_{\mathcal{Z}^{j}}}\frac{Q_{i}^{j}(A|X_{i}^{j}=x,\bm{Z_{1}}=\bm{z_{1}},\dots,\bm{Z}_{i-1}=\bm{z_{i-1}})}{Q_{i}^{j}(A|X_{i}^{j}=x^{\prime},\bm{Z}_{1}=\bm{z}_{1},\dots,\bm{Z}_{i-1}=\bm{z}_{i-1})}\leq\exp(\alpha_{j}).}$
(2.2)

We say that the privacy mechanism $\bm{Q}_{i}=(Q^{1}_{i},\dots,Q^{d}_{i})$ for
$i=1,\dots,n$ is $\bm{\alpha}$-differentially locally private if each variable
$Z_{i}^{j}$ is an $\alpha_{j}$\- differentially locally private view of
$X^{j}_{i}$. We denote by $\mathcal{Q}_{\bm{\alpha}}^{(n)}$ the set of all
local $\bm{\alpha}$-differential private Markov kernels
$(Q^{j}_{i})_{\begin{subarray}{c}1\leq i\leq n\\\ 1\leq j\leq d\\\
\end{subarray}}$.
The parameter $\alpha_{j}$ quantifies the amount of privacy that is guaranteed
to the variable $X_{i}^{j}$: setting $\alpha_{j}=0$ ensures perfect privacy
for recovering $X^{j}_{i}$ from the view of
$Z^{j}_{i},\bm{Z}_{1},\dots,\bm{Z}_{i-1}$, whereas letting $\alpha_{j}$ tend
to infinity softens the privacy restriction.
In the non-interactive case, $\bm{Q}_{i}=\bm{Q}=(Q^{1},\dots,Q^{d})$ does not
depend on $i$ and the bound (2.2) becomes

${}\sup_{A\in{\Xi_{\mathcal{Z}^{j}}}}\frac{Q^{j}(A|X_{i}^{j}=x)}{Q^{j}(A|X_{i}^{j}=x^{\prime})}\leq\exp(\alpha_{j}).$
(2.3)

Under componentwise local differential privacy the kernels
$Q^{j}(\cdot|X^{j}_{i}=x)$ are mutually absolutely continuous for different
$x$. Hence, we can suppose that there exists a dominating measure $\mu^{j}$ on
$(\mathcal{Z}^{j},\Xi_{\mathcal{Z}^{j}})$ such that the kernel $Q^{j}$ admits
a density with respect to $\mu^{j}$. We denote by $q^{j}$ this density. Then,
the property of $\bm{\alpha}$-CLDP defined in (2.3) is equivalent to the
following. For all $x,x^{\prime}\in{\color[rgb]{0,0,0}\mathcal{X}^{j}}$

${}\sup_{z\in{\color[rgb]{0,0,0}\mathcal{Z}^{j}}}\frac{q^{j}(z|X^{j}=x)}{q^{j}(z|X^{j}=x^{\prime})}\leq\exp(\alpha_{j}).$
(2.4)

In this framework, we want to characterize the tradeoff between local
differential privacy and statistical utility. In particular, we want to
characterize how, for several canonical estimation problems, the optimal rate
of convergence changes as a function of the privacy. For this reason, we
develop some bounds on pairwise divergences which lead us to the derivation of
minimax bounds under CLDP constraints.

###  2.1 Comparison with LDP

To better understand the difference between CLDP and LDP, let us focus on the
situation of one sample
$\bm{X}=(X^{1},\dots,X^{d})\in\bm{\mathcal{X}}=\prod_{j=1}^{d}\mathcal{X}^{j}$
which is publicly displayed through a CLDP mechanism based on $d$ independent
channels $\bm{Q}=(Q^{1},\dots,Q^{d})$ with privacy parameter
$\bm{\alpha}=(\alpha_{1},\dots,\alpha_{d})$. Each kernel $Q^{j}$ is a
randomization taking values in some space $\mathcal{Z}^{j}$. This CLDP
mechanism also induces a LDP mechanism on the whole vector
$\bm{X}\in\bm{\mathcal{X}}$ with Markov kernel $\overline{\bm{Q}}$ taking
values in $\bm{\mathcal{Z}}=\prod_{j=1}^{d}\mathcal{Z}^{j}$, defined by
$\overline{\bm{Q}}(A^{1}\times\dots\times
A^{d}\mid\bm{X}=(x^{1},\dots,x^{d}))=\prod_{j=1}^{d}Q^{j}(A^{j}\mid
X^{j}=x^{j})$. Then, the following lemma shows that $\overline{\bm{Q}}$
satisfies the classical LDP constraint.

######  Lemma 2.1.

If $\bm{Q}$ satisfies the $\bm{\alpha}$-CLDP constraint with
$\bm{\alpha}=(\alpha_{1},\dots,\alpha_{d})$, then $\overline{\bm{Q}}$
satisfies $\overline{\bm{\alpha}}$-LDP constraint with
$\overline{\bm{\alpha}}=\sum_{j=1}^{d}\alpha_{j}$.

###### Proof.

Using the definition of $\overline{\bm{Q}}$ we write,

$\sup_{(A^{1},\dots,A^{d})\in\prod_{j=1}^{d}\Xi_{\mathcal{Z}^{j}}}\frac{\overline{\bm{Q}}(A^{1}\times\dots\times
A^{d}\mid\bm{X}=(x^{1},\dots,x^{d}))}{\overline{\bm{Q}}(A^{1}\times\dots\times
A^{d}\mid\bm{X}=(x^{\prime 1},\dots,x^{\prime d}))}\\\
\leq\prod_{j=1}^{d}\sup_{A^{j}\Xi_{\mathcal{Z}^{j}}}\frac{Q^{j}(A^{j}\mid
X^{j}=x^{j})}{Q^{j}(A^{j}\mid X^{j}=x^{\prime
j})}\leq\exp\left(\sum_{j=1}^{d}\alpha^{j}\right)$

where we used (2.3). This implies that the channel $\overline{\bm{Q}}$
satisfies the classical LDP constraint with level
$\overline{\bm{\alpha}}=\sum_{j=1}^{d}\alpha^{j}$. ∎

This lemma allows us to see the CLDP kernels as a subset of the LDP kernels
with privacy parameter $\overline{\bm{\alpha}}$. The main specificity of CLDP
type kernels is that they must satisfy the additional constraint to act
independently on the different components of the raw data $\bm{X}$. This
additional constraint reduces the set of possible kernels and makes the
inference on the law of the vector $\bm{X}$ harder than without the
componentwise constraint. For instance if
$\alpha_{1}=\dots=\alpha_{d}=\alpha$, we show in Sections 4.3 that the rate of
estimation for the joint law of $\bm{X}$ is determined by the growth to
infinity of the quantity $n\alpha^{2d}$ when the vector $\bm{X}$ is privatized
in a componentwise way, whereas this rate is determined by
$n\overline{\bm{\alpha}}^{2}=nd^{2}\alpha^{2}$ when the vector $\bm{X}$ is
privatized with a classical LDP channel with privacy parameter
$\bm{\overline{\alpha}}=d\alpha$. It shows that the impact of the
componentwise constraint is large when the privacy parameters are small and
$n\alpha^{2d}<<nd^{2}\alpha^{2}$. However, we stress that the CLDP constraint
may be unavoidable in practice if it is impossible to collect all the
components of the sensitive vector $\bm{X}$ prior emitting the public views.

We now give examples of privacy channels satisfying the CLDP constraint and
for which the inclusion described in Lemma 2.1 is sharp.

Assume that $\mathcal{X}^{j}=\mathbb{R}$. Let $T^{(j)}>0$ and $\alpha_{j}>0$.
We recall the definition of the Laplace mechanism channel $Q^{j}$. This
channel is valued in $\mathcal{Z}^{j}=\mathbb{R}$. It is defined by
$Q^{j}(A\mid X^{j}=x^{j})=\mathbb{P}(Z^{j}\in A)$ where
$Z^{j}=\left[x\right]_{T^{(j)}}+\frac{2T^{(j)}}{\alpha_{j}}\mathcal{E}^{j}$
with $\left[x\right]_{T^{(j)}}=\max(\min(x,T^{(j)}),-T^{(j)})$ and
$\mathcal{E}^{j}$ is a Laplace random variable. This channel admits a density
with respect to the Lebesgue measure $\mu^{j}$, given by $q^{j}(z^{j}\mid
X^{j}=x^{j})=\frac{\alpha_{j}}{4T^{(j)}}\exp\left(\frac{\alpha_{j}}{2T^{(j)}}\lvert
z^{j}-\left[x^{j}\right]_{T^{(j)}}\rvert\right)$. Then, we have the following
result.

######  Lemma 2.2.

1) We have for all $j\in\\{1,\dots,d\\}$,

$\sup_{(x,x^{\prime},z)\in\mathbb{R}^{3}}\frac{q^{j}(z\mid
X^{j}=x)}{q^{j}(z\mid X^{j}=x^{\prime})}=e^{\alpha_{j}}.$

In particular $\bm{Q}=(Q^{1},\dots,Q^{d})$ satisfies the $\bm{\alpha}$-CLDP
constraint with $\bm{\alpha}=(\alpha_{1},\dots,\alpha_{d})$.

2) The kernel $\overline{\bm{Q}}$ satisfies the $\overline{\bm{\alpha}}$-LDP
constraint with $\overline{\bm{\alpha}}=\sum_{j=1}^{d}\alpha_{j}$ but is not
$\beta$-LDP for $\beta<\sum_{j=1}^{d}\alpha_{j}$.

###### Proof.

1) From the expression of the density of the Markov kernel $Q^{j}$, we have
for $(x,x^{\prime},z^{\prime})\in\mathbb{R}^{3}$,

$\displaystyle\frac{q^{j}(z|X^{j}=x)}{q^{j}(z|X^{j}=x^{\prime})}$
$\displaystyle=\exp\Big{(}-\frac{\alpha_{j}}{2T^{(j)}}\lvert
z-\left[x\right]_{T^{(j)}}\rvert+\frac{\alpha_{j}}{2T^{(j)}}\lvert
z-\left[x^{\prime}\right]_{T^{(j)}}\rvert\Big{)}$
$\displaystyle\leq\exp\Big{(}\frac{1}{2T^{(j)}}\alpha_{j}\lvert\left[x\right]_{T^{(j)}}-\left[x^{\prime}\right]_{T^{(j)}}\rvert\Big{)}$
$\displaystyle\leq\exp(\alpha_{j}),$

where in the second line we used the reverse triangle inequality, and in the
third line that
$\lvert\left[x\right]_{T^{(j)}}-\left[x^{\prime}\right]_{T^{(j)}}\rvert\leq
2T^{(j)}$. This proves that we have
$\sup_{(x,x^{\prime},z)\in\mathbb{R}^{3}}\frac{q^{j}(z\mid
X^{j}=x)}{q^{j}(z\mid X^{j}=x^{\prime})}\leq e^{\alpha_{j}}$ and in turn the
kernel $\bm{Q}=(Q^{1},\dots,Q^{d})$ is $\bm{\alpha}$-CLDP by the definition
(2.4).

Moreover, if one takes $x=T^{(j)}$, $x^{\prime}=-T^{(j)}$ and $z=T^{(j)}$ we
see that the above supremum is exactly $e^{\alpha_{j}}$.

2) Using the product structure of the kernel $\overline{\bm{Q}}$, it is
defined from $\bm{\mathcal{X}}=\mathbb{R}^{d}$ and takes values in the public
space $\bm{\mathcal{Z}}=\mathbb{R}^{d}$ with the associated density

$\overline{\bm{q}}(\bm{z}\mid\bm{X}=\bm{x})=\prod_{j=1}^{d}q^{j}(z^{j}|X^{j}=x^{j}),$

for all $\bm{x}=(x^{1},\dots,x^{d})\in\bm{\mathcal{X}}$ and
$\bm{z}=(z^{1},\dots,z^{d})\in\bm{\mathcal{Z}}$. Then, by computations
analogous to the first point of the lemma we get
$\sup_{\bm{x},\bm{x}^{\prime},\bm{z}}\frac{\overline{\bm{q}}(\bm{z}\mid\bm{X}=\bm{x})}{\overline{\bm{q}}(\bm{z}\mid\bm{X}=\bm{x}^{\prime})}=e^{\overline{\bm{\alpha}}}$.
This shows the second point of the lemma. ∎

By the first point of the above lemma, we see that the product of Laplace
kernels is $\bm{\alpha}$-CLDP with
$\bm{\alpha}=(\alpha_{1},\dots,\alpha_{d})$, and that the values of the
privacy parameter can not be reduced. The purpose of Point 2) is to show that
it is impossible, in general, to reduce the value of $\overline{\bm{\alpha}}$
in Lemma 2.1.

###  2.2 Minimax framework

Before we keep proceeding, we introduce the minimax risk in the classical
framework. It will be useful to present the notion of multivariate
$\bm{\alpha}$-private minimax rate, which is defined starting from the
observation of the privatized outputs $Z_{i}^{j}$, for $i\in\\{1,\dots,n\\}$
and $j\in\\{1,\dots,d\\}$.

Suppose we have a set of probability distributions $\mathcal{P}$ defined on a
sample space $\mathcal{X}$, and let $\theta(P)$ be a function that maps each
distribution in $\mathcal{P}$ to a value in a set of parameters $\Theta$. The
specific set $\Theta$ depends on the statistical model being used. For
instance, if we are estimating the mean of a single variable, $\Theta$ will be
a subset of the real numbers. On the other hand, if we are estimating a
probability density function, $\Theta$ can be a subset of the space of all
possible density functions over $\mathcal{X}$. Suppose moreover we have a
function $\rho$ that measures the distance between two points in the set of
parameters $\Theta$ and which is a semi-metric (i.e. it does not necessarily
satisfy the triangle inequality). We use this function to evaluate the
performance of an estimator for the parameter $\theta$. Additionally, we
consider a non-decreasing function
$\Phi:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ such that $\Phi(0)=0$. The
classical example consists in taking $\rho(x,y)=|x-y|$ and $\Phi(t)=t^{2}$.

In a scenario without privacy, a statistician has access to iid observations
$\bm{X}_{1},…,\bm{X}_{n}$ that are drawn from a probability distribution
$P\in\mathcal{P}$. The goal is to estimate an unknown parameter $\theta(P)$
that belongs to a set of parameters $\Theta$. To achieve this goal, the
statistician uses a measurable function
$\hat{\theta}:\mathcal{X}^{n}\rightarrow\Theta$. The quality of the estimator
$\hat{\theta}(\bm{X}_{1},\dots,\bm{X}_{n})$ is evaluated in terms of its
minimax risk, defined as

${}\inf_{\hat{\theta}}\sup_{P\in\mathcal{P}}\mathbb{E}_{P}[\Phi(\rho(\hat{\theta}(\bm{X}_{1},\dots,\bm{X}_{n}),\theta(P)))],$
(2.5)

where the inf is taken over all the possible estimators $\hat{\theta}$.
A vast body of statistical literature is dedicated to the development of
methods for determining upper and lower bounds on the minimax risk for
different types of estimation problems.
In this paper we want to consider the private analogous of the minimax risk
described above, which takes into account the privacy constraints in the
multivariate context, where the components are made public separately. Its
definition is a straightforward consequence of the $\bm{\alpha}$-CLDP
mechanism as in (2.2). Indeed, for any given privacy level $\alpha_{j}>0$ we
have $\mathcal{Q}_{\bm{\alpha}}$ denoting the set of all the privacy
mechanisms having the $\bm{\alpha}$-CLDP property. Then, for any sample
$\bm{X}_{1},\dots,\bm{X}_{n}$, any distribution
$\bm{Q}^{n}:=(\bm{Q}_{1},\dots,\bm{Q}_{n})\in{\color[rgb]{0,0,0}\mathcal{Q}^{(n)}_{\bm{\alpha}}}$
produces a set of privatized observations which have been made public
separately, i.e. $Z_{1}^{1},\dots,Z_{1}^{d},\dots,Z_{n}^{1},\dots,Z_{n}^{d}$.
We can focus on estimators $\hat{\theta}$ which depend exclusively on the
privatized sample and we can therefore write
$\hat{\theta}=\hat{\theta}(Z_{1}^{1},\dots,Z_{1}^{d},\dots,Z_{n}^{1},\dots,Z_{n}^{d})$.
Then, it seems natural to look for the privacy mechanism
$\bm{Q}^{n}\in{\color[rgb]{0,0,0}\mathcal{Q}^{(n)}_{\bm{\alpha}}}$ for which
the estimator
$\hat{\theta}(Z_{1}^{1},\dots,Z_{1}^{d},\dots,Z_{n}^{1},\dots,Z_{n}^{d})$
performs as good as possible. The performance of the estimator is even in this
case judged in term of the minimax risk, which leads us to the following
definition.

######  Definition 1.

Given a privacy parameter
$\bm{\alpha}=(\alpha_{1},\dots,\alpha_{d}),\,\alpha_{j}>0$ and a family of
distributions $\theta(P)$, the componentwise $\bm{\alpha}$ private minimax
risk in the metric $\rho$ is

$\inf_{\bm{Q}^{n}\in\mathcal{Q}^{(n)}_{\bm{\alpha}}}\inf_{\hat{\theta}}\sup_{P\in\mathcal{P}}\mathbb{E}_{P,\bm{Q}}[\Phi(\rho(\hat{\theta}(Z_{1}^{1},\dots,Z_{n}^{d}),\theta(P)))],$

where the inf is taken over all the estimators $\hat{\theta}$ and all the
choices
$(\bm{Q}_{1},\dots,\bm{Q}_{n})\in{\color[rgb]{0,0,0}\mathcal{Q}^{(n)}_{\bm{\alpha}}}$
such that the data $Z_{1}^{1},\dots,Z_{n}^{d}$ are $\bm{\alpha}$-CLDP views of
$X_{1}^{1},\dots,X_{n}^{d}$ in the sense of (2.2).

Our main goal consists in proving some sharp bounds on pairwise divergences,
as in Section 3.1. From there, it will be possible to derive sharp lower
bounds on the $\bm{\alpha}$ private minimax risk for the statistical
estimation of manifolds canonical problems, see Section 4 for some examples of
applications.

##  3 Main results

In this section, we establish a connection between the proximity of two laws
for the private individual variable $\bm{X}$ and the proximity of their
corresponding public views under the $\bm{\alpha}$-CLDP property. Then, we
explore the usefulness of this result for the privatization of independent
samplings.

###  3.1 Bounds on pairwise divergences

We assume that we are given a pair of distributions $P$ and $\tilde{P}$
defined on a common space
${\bm{\mathcal{X}}}=(\mathcal{X}^{1},\dots,\mathcal{X}^{d})$, and a
privatization kernel $\bm{Q}=(Q^{1},\dots,Q^{d})$ where $Q^{j}$ is the
privatization channel from $\mathcal{X}^{j}$ to $\mathcal{Z}^{j}$. We denote
by $M$ and $\tilde{M}$ the law of the images of $P$ and $\tilde{P}$ through
the operation of privatization. It means that we consider a couple of raw
samples $\bm{X}$, $\bm{\tilde{X}}$ with distribution $P$, $\tilde{P}$, and
that the associated privatized samples $\bm{Z}$, $\bm{\tilde{Z}}$ have
distribution denoted by $M$ and $\tilde{M}$. Consistently with the description
in Section 2, each channel $Q^{j}$ acts on its associated component $X^{j}$
independently of the other channels. More formally, we can write the
correspondence between $P$ and $M$ as

$M\left(\prod_{j=1}^{d}A_{j}\right)=\int_{\bm{\mathcal{X}}}\prod_{j=1}^{d}Q^{j}(A_{j}\mid
X^{j}=x^{j})P(dx^{1},\dots,dx^{d}),$

for any $A_{j}\in\Xi_{\mathcal{Z}^{j}}$.
Before we keep proceeding, let us introduce some notation. We denote as
$d_{TV}(P_{1},P_{2})$ the total variation distance between the two measures
$P_{1}$ and $P_{2}$:

${}d_{TV}(P_{1},P_{2})=\int\lvert
dP_{1}-dP_{2}\rvert=\int\lvert\frac{dP_{1}}{dP_{1}+dP_{2}}(x)-\frac{dP_{2}}{dP_{1}+dP_{2}}(x)\rvert(P_{1}+P_{2})(dx).$
(3.1)

Moreover, we denote as $d_{KL}(P_{1},P_{2})$ the Kullback divergence between
the two measures $P_{1}$ and $P_{2}$,

${}d_{KL}(P_{1},P_{2})=\int\log\big{(}\frac{dP_{2}}{dP_{1}}\big{)}dP_{2}$
(3.2)

for $P_{2}$ absolutely continuous to $P_{1}$.
Finally, we denote as $L_{(X^{j_{1}},\dots,X^{j_{k}})}$ the law of the
marginals $X^{j_{1}},\dots,X^{j_{k}}$ of $\bm{X}$, where $k$ and the indexes
$j_{1}$, …, $j_{k}$ belong to $\\{1,\dots,d\\}$. According to this notation it
is clearly $L_{(X^{1},\dots,X^{d})}=P$ and
$L_{(\tilde{X}^{1},\dots,\tilde{X}^{d})}=\tilde{P}$.

Our main result gives an intuition on how close the two output distributions
shall be, depending on how close the laws of the anonymised data were. Its
proof can be found at the end of this section.

######  Theorem 3.1.

Let $\alpha_{j}\geq 0$ and assume that $\bm{Q}=(Q^{1},\dots,Q^{d})$ guarantees
the $\bm{\alpha}$-CLDP constraint as defined by the condition (2.3). Then,

$d_{KL}(M,\tilde{M})\leq\Big{(}\sum_{k=1}^{d}\sum_{(j_{1},\dots,j_{k})}\prod_{i=1}^{k}(e^{\alpha_{j_{i}}}-1)d_{TV}(L_{(X^{j_{1}},\dots,X^{j_{k}})},L_{(\tilde{X}^{j_{1}},\dots,\tilde{X}^{j_{k}})})\Big{)}^{2},$

where the inner summation is on $1\leq j_{1}<j_{2}<\dots<j_{k}\leq d$ any $k$
distinct ordered indexes in $\\{1,\dots,d\\}$.

In the case where $\alpha_{1}=\dots=\alpha_{d}=:\alpha$, it reduces to

$d_{KL}(M,\tilde{M})\leq\Big{(}\sum_{k=1}^{d}(e^{\alpha}-1)^{k}\sum_{(j_{1},\dots,j_{k})}d_{TV}(L_{(X^{j_{1}},\dots,X^{j_{k}})},L_{(\tilde{X}^{j_{1}},\dots,\tilde{X}^{j_{k}})})\Big{)}^{2}.$
(3.3)

######  Remark 3.2.

To better understand the formula in the statement of the theorem the reader
may observe that, for $d=2$, the left hand side of our main bound is

$\Big{[}(e^{\alpha_{1}}-1)d_{TV}(L_{X^{1}},L_{\tilde{X}^{1}})+(e^{\alpha_{2}}-1)d_{TV}(L_{X^{2}},L_{\tilde{X}^{2}})+(e^{\alpha_{1}}-1)(e^{\alpha_{2}}-1)d_{TV}(L_{(X^{1},X^{2})},L_{(\tilde{X}^{1},\tilde{X}^{2})})\Big{]}^{2}.$

For $d=3$ it is instead

$\displaystyle\Big{[}\sum_{i=1}^{3}(e^{\alpha_{i}}-1)d_{TV}(L_{X^{i}},L_{\tilde{X}^{i}})$
$\displaystyle+\sum_{1\leq i<j\leq
3}(e^{\alpha_{i}}-1)(e^{\alpha_{j}}-1)d_{TV}(L_{(X^{i},X^{j})},L_{(\tilde{X}^{i},\tilde{X}^{j})})$
$\displaystyle+(e^{\alpha_{1}}-1)(e^{\alpha_{2}}-1)(e^{\alpha_{3}}-1)d_{TV}(L_{(X^{1},X^{2},X^{3})},L_{(\tilde{X}^{1},\tilde{X}^{2},\tilde{X}^{3})})\Big{]}^{2}.$

######  Remark 3.3.

In the mono-dimensional case, where $\bm{\mathcal{X}}=\mathcal{X}^{1}$ and
$\bm{\alpha}=\alpha_{1}$, we recover a bound similar to the one in Theorem 1
of [19], which is

$d_{KL}(M,\tilde{M})\leq\min(4,e^{2\alpha})(e^{\alpha}-1)^{2}d_{TV}(P,\tilde{P})^{2}.$
(3.4)

In the multidimensional setting with $\alpha_{1}=\dots=\alpha_{d}=\alpha$, if
we use in (3.3) the crude bound

$d_{TV}(L_{(X^{j_{1}},\dots,X^{j_{k}})},L_{(\tilde{X}^{j_{1}},\dots,\tilde{X}^{j_{k}})})\leq
d_{TV}(P,\tilde{P}),$

we obtain

${}d_{KL}(M,\tilde{M})\leq\left(\sum_{k=1}^{d}(e^{\alpha}-1)^{k}\binom{n}{k}d_{TV}(P,\tilde{P})\right)^{2}=(e^{\alpha
d}-1)^{2}d_{TV}(P,\tilde{P})^{2},$ (3.5)

where we have used Newton’s binomial formula. It is important to note that
when $d>1$, the inequality stated in Theorem 1 of [19] (referred to as (3.4))
is still valid. Recalling the discussion in Section 2.1, the CLDP channel with
privacy parameter $\bm{\alpha}=(\alpha,\dots,\alpha)$ is a special case of LDP
channel with privacy parameter $d\times\alpha$. Hence, the results given by
the bounds (3.4) and (3.5) are the same, up to a constant. However, our result
is generally more precise. Indeed, our analysis takes into account the fact
that the individual components of the vector have been made public
independently, which allows to recover the more precise upper bound (3.3),
where the contribution of the differences between each $k$-dimensional
marginals is assessed.

A main purpose of controls like (3.3)–(3.5) is to theoretically assess the
minimum loss of information about the raw law when the data are transmitted
through the channel. Our bound (3.3) reveals that, in the case of a CLDP
channel, when $\alpha$ gets small the information about the joint law is lost
faster than the information about the marginal laws.

As we will see in next section, the bound on pairwise divergences gathered in
Theorem 3.3 is particularly helpful when one wants to show lower bound on the
minimax risk, in order to illustrate the optimality of a proposed estimator,
in a minimax sense.
In this case one can propose two priors whose marginal laws are all the same
but for the last term, where the whole vector is considered. Then, our main
result reduces to the bound below.

######  Corollary 3.4.

Let us consider a couple of raw samples $\bm{X}$, $\bm{\tilde{X}}$ with
distributions $P$, $\tilde{P}$ and the associated couple of privatized samples
$\bm{Z}$, $\bm{\tilde{Z}}$ with distributions $M$, $\tilde{M}$. Assume
moreover that, for any $k\in\\{1,\dots,d-1\\}$, $1\leq j_{1}<\dots<j_{k}\leq
d$, it is
$L_{(X^{j_{1}},\dots,X^{j_{k}})}=L_{(\tilde{X}^{j_{1}},\dots,\tilde{X}^{j_{k}})}$.
Then,

$d_{KL}(M,\tilde{M})\leq\Big{(}\prod_{i=1}^{d}
(e^{\alpha_{i}}-1)^{2}\Big{)}d_{TV}(P,\tilde{P})^{2}.$

As we will see in next section, the bound stated in the corollary is extremely
useful to assess minimax risks under the $\alpha$-CLDP property. Indeed, under
the assumption of the corollary, the reduction of the distance between the
private laws and the public laws is maximal when the $\alpha$’s are small.
This is a worst case scenario when a statistician wants to determine from the
public view which of the two private laws, $P$ or $\tilde{P}$, is the true
one. Hence, this result is crucial in the proof of lower bounds related to
estimation problems.

The rest of this section is devoted to the proof of Theorem 3.3.

###### Proof of Theorem 3.3.

To prove our main theorem we introduce some notation. We first recall that
$q^{j}(z^{j}\mid x^{j})$ is the density of the the law of $Z^{j}$ conditional
to $X^{j}=x^{j}$ with respect to a dominating measure $\mu^{j}(dz^{j})$. We
denote by $q(z^{1},\dots,z^{d})$ the density of the law of
$(Z^{1},\dots,Z^{d})$, which exists with respect to the reference measure
$\bm{\mu}(d\bm{z}):=\mu^{1}(dz^{1})\times\dots\times\mu^{d}(dz^{d})$. In a
more general way, we examine a collection of $d$ symbols
$\zeta^{1},\dots,\zeta^{d}$, which can take one of three possible values:
$\zeta^{j}=dx^{j}$, $\zeta^{j}=z^{j}$, or $\zeta^{j}=\emptyset$. We define a
vector $\bm{W}$ such that the $j$-th component of $\bm{W}$, denoted $W^{j}$,
takes the value of $X^{j}$ if $\zeta^{j}=dx^{j}$, takes the value of $Z^{j}$
if $\zeta^{j}=z^{j}$, and is removed entirely if $\zeta^{j}=\emptyset$. We
denote as $q(\zeta^{1},\dots,\zeta^{d})$ the Markovian kernel such that

$q(\zeta^{1},\dots,\zeta^{d})\times\prod_{j:\zeta^{j}=z^{j}}\mu^{j}(dz^{j})$

is the law of $\bm{W}$. For example,

$q(dx^{1},\dots,dx^{i},\emptyset,\dots,\emptyset,z^{i+j+1},\dots,z^{d})\mu^{i+j+1}(dz^{i+j+1})\times\dots\times\mu^{d}(dz^{d})$

is the law of $(X^{1},\dots,X^{i},Z^{i+j+1},\dots,Z^{d})$ and we thus have

$\mathbb{E}\left[f(X^{1},\dots,X^{i},Z^{i+j+1},\dots,Z^{d})\right]=\int_{\mathcal{X}^{1}\times\dots\times\mathcal{X}^{i}\times\mathcal{Z}^{i+j+1}\times\dots\times\mathcal{Z}^{d}}f(x^{1},\dots,x^{i},z^{i+j+1},\dots,z^{d})\\\
q(dx^{1},\dots,dx^{i},\emptyset,\dots,\emptyset,z^{i+j+1},\dots,z^{d})\mu^{i+j+1}(dz^{i+j+1})\times\dots\times\mu^{d}(dz^{d}),$

for any positive measurable function $f$. Such Markovian kernels
$q(\zeta^{1},\dots,\zeta^{d})$ exist for all choices of symbols $\zeta^{j}$.
Indeed, it is possible to disintegrate the law of
$(W^{j})_{j:\zeta_{j}\neq\emptyset}$ with respect to the law of
$(W^{j})_{j:\zeta^{j}=z^{j}}$ and use that the law of
$(W^{j})_{j:\zeta^{j}=z^{j}}$ admits a density with respect to
$\prod_{j:\zeta^{j}=z^{j}}\mu^{j}(dz^{j})$. With a slight abuse of notation we
consider $q(\emptyset,\dots,\emptyset)=1$. It is consistent with the fact
that, when removing one marginal $W^{j}=X^{j}$ (or $W^{j}=Z^{j}$) from a
random vector, the corresponding probability measure is integrated with
respect to the variable $x_{j}$ (or $z_{j}$). Hence, when removing ultimately
all the variables the probability integrates to $1$, yielding to the notation
$q(\emptyset,\dots,\emptyset)=1$. Let us stress that these notations are
cumbersome as we are dealing with general variables $\bm{X}$ and $\bm{Z}$. For
instance, in the simple case where
$\bm{\mathcal{X}}=\bm{\mathcal{Z}}=\mathbb{R}^{d}$, $\bm{X}$ with density on
$\mathbb{R}^{d}$, and privacy channels having densities $q^{j}(z^{j}\mid
x^{j})$ with respect to the Lebesgue measure, we would have simply defined
$q(\zeta^{1},\dots,\zeta^{d})$ as the density of the variables
$(W^{j})_{j:\zeta^{j}\neq\emptyset}$.

We introduce analogously $\tilde{q}(\zeta_{1},\dots,\zeta_{d})$, which
corresponds to the law of $\bm{\tilde{X}}$ and $\bm{\tilde{Z}}$ in the same
way as above.

Then, using these notations and the fact that the law of $Z^{1}$ conditional
to $(X^{1},Z^{2},\dots,Z^{d})$ is given, from the definition of the privacy
mechanism, by $Q^{1}(dz^{1}\mid X^{1}=x^{1})=q^{1}(z^{1}\mid
x^{1})\mu^{1}(dz^{1})$, it is

$q(z^{1},\dots,z^{d})=\int_{\mathcal{X}^{1}}q^{1}(z^{1}|x^{1})q(dx^{1},z^{2},\dots,z^{d}).$
(3.6)

Finally, we introduce the function
$l[\zeta^{1},\dots,\zeta^{d}]:\mathcal{Z}^{1}\times\dots\times\mathcal{Z}^{d}\to\mathbb{R}_{+}$
as below:

$\displaystyle l[\zeta^{1},\dots,\zeta^{d}]:=$
$\displaystyle|q(z^{1},\dots,z^{d})-\tilde{q}(z^{1},\dots,z^{d})|,\leavevmode\nobreak\
\text{ for $\bm{\zeta}=\bm{z}$},$ (3.7) $\displaystyle
l[\zeta^{1},\dots,\zeta^{d}]:=$ $\displaystyle\prod_{j:\zeta^{j}\neq
z^{j}}q^{j}(z^{j}|x^{j}_{*})\prod_{j:\zeta^{j}=dx^{j}}|e^{\alpha_{j}}-1|\times$
$\displaystyle\qquad\qquad\qquad\qquad\int_{\prod\limits_{j:\zeta^{j}=dx^{j}}\mathcal{X}^{j}}|q(\zeta^{1},\dots,\zeta^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{d})|,\leavevmode\nobreak\
\text{ for $\bm{\zeta}\neq\bm{z}$},$ (3.8)

where $q^{j}(z^{j}|x^{j}_{*}):=\inf_{x^{j}}q^{j}(z^{j}|x^{j})$ and
$\bm{\zeta}=(\zeta^{1},\dots,\zeta^{d})$. To clarify the notation, let us
stress that the integration variables in (3.8) are the $\zeta^{j}$ such that
$\zeta^{j}=dx^{j}$. Moreover, $l[\zeta^{1},\dots,\zeta^{d}]$ is a function of
$(z^{1},\dots,z^{d})$ whatever is the choice $(\zeta^{1},\dots,\zeta^{d})$.
Indeed, the variable $z^{j}$ appears either in the product
$\prod_{j:\zeta^{j}\neq z^{j}}q^{j}(z^{j}|x^{j}_{*})$ when $j$ is such that
$\zeta^{j}\neq z^{j}$, or in the integral when $\zeta^{j}=z^{j}$. To give an
example, the quantity
$l[dx^{1},\dots,dx^{i},\emptyset,\dots,\emptyset,z^{i+j+1},\dots,z^{d}]$ is
equal to

$\prod_{l=1}^{i+j}q^{l}(z^{l}|x^{l}_{*})\prod_{l=1}^{i}|e^{\alpha_{l}}-1|\times\\\
\int_{\prod\limits_{l=1}^{i}\mathcal{X}^{l}}|q(dx^{1},\dots,dx^{i},\emptyset,\dots,\emptyset,z^{i+j+1},\dots,z^{d})-\tilde{q}(dx^{1},\dots,dx^{i},\emptyset,\dots,\emptyset,z^{i+j+1},\dots,z^{d})|,$

which is clearly a function of $(z^{1},\dots,z^{d})$. In the scenario where
$\bm{\zeta}=\bm{z}$, the equation (3.8) aligns with (3.7), except that the
integration variables disappear. Then, in the right-hand side of (3.8) the
integral no longer appears. We also specify that
$l[\emptyset,\dots,\emptyset]=0$, which results from the fact that, abusing
the notations, we have
$q(\emptyset,\dots,\emptyset)=\tilde{q}(\emptyset,\dots,\emptyset)=1$.

Our main result heavily relies on the following proposition. Its proof, based
on a recurrence argument, can be found in the Appendix.

######  Proposition 3.5.

Let the function $l[\zeta^{1},\dots,\zeta^{d}]$ be defined according to (3.7)
and (3.8). Then, under the hypothesis of Theorem 3.3, the following inequality
holds true.

$\displaystyle{}l[z^{1},\dots,z^{d}]\leq\sum_{(\zeta^{1},\dots,\zeta^{d})\in\prod_{j=1}^{d}\\{\emptyset,{dx^{j}}\\}}l[\zeta^{1},\dots,\zeta^{d}].$
(3.9)

Recalling (3.7), we remark that the left hand side of (3.9) assesses the
difference between the densities of $\bm{Z}$ and $\bm{\tilde{Z}}$, while the
right hand side only relies on the laws of $\bm{X}$, $\bm{\tilde{X}}$ as the
symbol $\zeta^{j}=z^{j}$ disappears in the sum.
From Proposition 3.5 we have

$\displaystyle{}|q(\bm{z})-\tilde{q}(\bm{z})|$
$\displaystyle=l[z^{1},\dots,z^{d}]\leq\sum_{\bm{\zeta}:\zeta^{j}\in\\{\emptyset,dx^{j}\\}}l(\bm{\zeta})$
(3.10)
$\displaystyle=\sum_{\bm{\zeta}:\zeta^{j}\in\\{\emptyset,{\color[rgb]{0,0,0}dx^{j}}\\}}\prod_{j=1}^{d}{\color[rgb]{0,0,0}q^{j}}(z^{j}|x^{j}_{*})\prod_{j:\zeta^{j}=dx^{j}}(e^{\alpha_{j}}-1){\color[rgb]{0,0,0}\int_{\prod\limits_{j:\zeta^{j}=dx^{j}}\mathcal{X}^{j}}|q(\bm{\zeta})-\tilde{q}(\bm{\zeta})|}.$
(3.11)

By the definition of total variation distance, the quantity above can be seen
as

$\displaystyle\prod_{j=1}^{d}{\color[rgb]{0,0,0}q^{j}}(z^{j}|x^{j}_{*})\sum_{\bm{\zeta}:\zeta^{j}\in\\{\emptyset,x^{j}\\}}\leavevmode\nobreak\
\Bigg{\\{}\big{(}\prod_{j:\zeta^{j}=dx^{j}}(e^{\alpha_{j}}-1)\big{)}{\color[rgb]{0,0,0}d_{TV}(L_{(X^{j})_{j:\zeta^{j}=dx^{j}}},L_{(\tilde{X}^{j})_{j:\zeta^{j}=dx^{j}}})}\Bigg{\\}}$
$\displaystyle=\prod_{j=1}^{d}{\color[rgb]{0,0,0}q^{j}}(z^{j}|x^{j}_{*})\sum_{k=1}^{d}{\color[rgb]{0,0,0}\sum_{\begin{subarray}{c}j_{1}<\dots<j_{k}\\\
\text{ $k$ different indexes}\\\ \text{ in $\\{1,\dots,d\\}$
}\end{subarray}}}\Bigg{\\{}\big{(}\prod_{i=1}^{k}(e^{\alpha_{j_{i}}}-1)\big{)}\leavevmode\nobreak\
d_{TV}(L_{(X^{j_{1}},\dots,X^{j_{k}})},L_{(\tilde{X}^{{j_{1}}},\dots,\tilde{X}^{{j_{k}}})})\Bigg{\\}}.$
(3.12)

To conclude the proof we observe it is

$\displaystyle d_{KL}(M,\tilde{M})$
$\displaystyle=\int_{{\color[rgb]{0,0,0}\mathcal{Z}^{1}\times\dots\times\mathcal{Z}^{d}}}q(\bm{z})\log(\frac{q(\bm{z})}{\tilde{q}(\bm{z})}){\color[rgb]{0,0,0}d\bm{\mu}(\bm{z})}+\int_{{\color[rgb]{0,0,0}\mathcal{Z}^{1}\times\dots\times\mathcal{Z}^{d}}}\tilde{q}(\bm{z})\log(\frac{\tilde{q}(\bm{z})}{q(\bm{z})}){\color[rgb]{0,0,0}d\bm{\mu}(\bm{z})}$
$\displaystyle{}=\int_{{\color[rgb]{0,0,0}\mathcal{Z}^{1}\times\dots\times\mathcal{Z}^{d}}}(q(\bm{z})-\tilde{q}(\bm{z}))\log(\frac{q(\bm{z})}{\tilde{q}(\bm{z})}){\color[rgb]{0,0,0}d\bm{\mu}(\bm{z})}.$
(3.13)

Then, Lemma 4 in [19] entails
$|\log\frac{q(\bm{z})}{\tilde{q}(\bm{z})}|\leq\frac{|q(\bm{z})-\tilde{q}(\bm{z})|}{\min(q(\bm{z}),\tilde{q}(\bm{z}))}$.
In order to study the denominator, we write

$\displaystyle q(\bm{z})$
$\displaystyle={\color[rgb]{0,0,0}\int_{{\color[rgb]{0,0,0}x^{1}\in\mathcal{X}^{1}}}q^{1}(z^{1}|x^{1})q(dx^{1},z^{2},\dots,z^{d})}\geq{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1}_{*})q({\color[rgb]{0,0,0}\emptyset,}z^{2},\dots,z^{d}).$

We iterate the arguing above, to recover

$\displaystyle q(\bm{z})$
$\displaystyle\geq\prod_{j=1}^{d-1}{\color[rgb]{0,0,0}q^{j}}(z^{j}|x^{j}_{*}){\color[rgb]{0,0,0}\int_{{\color[rgb]{0,0,0}x^{d}\in\mathcal{X}^{d}}}{\color[rgb]{0,0,0}q^{d}}(z^{d}|x^{d})q(\emptyset,\dots,\emptyset,dx^{d})}\geq\prod_{j=1}^{d}{\color[rgb]{0,0,0}q^{j}(z^{j}|x^{j}_{*}),}$

where we used
$\int_{x^{d}\in\mathcal{X}^{d}}q(\emptyset,\dots,\emptyset,dx^{d})=1$. An
analogous lower bound holds true for $\tilde{q}(\bm{z})$. Thus, using also the
bound in (3.10)–(3.12), we obtain

${}\lvert\log(\frac{q(\bm{z})}{\tilde{q}(\bm{z})})\rvert\leq\frac{\lvert
q(\bm{z})-\tilde{q}(\bm{z})\rvert}{\min(q(\bm{z}),\tilde{q}(\bm{z}))}\\\
\leq\sum_{k=1}^{d}\sum_{(j_{1},\dots,j_{k})}\big{(}\prod_{i=1}^{k}(e^{\alpha_{j_{i}}}-1)\Big{)}d_{TV}(L_{(X^{j_{1}},...,X^{j_{k}})},L_{(\tilde{X}^{j_{1}},\dots,\tilde{X}^{j_{k}})}).$
(3.14)

We replace it in (3.13) which, together with (3.10)–(3.12), implies

$d_{KL}(M,\tilde{M})\leq\Big{(}\sum_{k=1}^{d}\sum_{(j_{1},\dots,j_{k})}\prod_{i=1}^{k}(e^{\alpha_{j_{i}}}-1)d_{TV}(L_{(X^{j_{1}},\dots,X^{j_{k}})},L_{(\tilde{X}^{j_{1}},\dots,\tilde{X}^{j_{k}})})\Big{)}^{2}\\\
\times\int_{\mathcal{Z}^{1}\times\dots\times\mathcal{Z}^{d}}\prod_{j=1}^{d}q^{j}(z^{j}|x^{j}_{*})d\bm{\mu}(\bm{z}).$

The proof of Theorem 3.3 is then complete, as the last integral can not be
larger than one. ∎

######  Remark 3.6.

Let us stress that our proof also provides a control on the difference between
the densities of $\bm{Z}$ and $\bm{\tilde{Z}}$ given by (3.14).

###  3.2 Application to privatization of independent sampling

This section applies the previously proven results to a scenario where the
original samples $\bm{X}_{1},\dots,\bm{X}_{n}$ composed by independent vectors
distributed according to $\bm{X}$, are transformed into privatized samples
$\bm{Z}_{1},\dots,\bm{Z}_{n}$. The notation used in this section is consistent
with that used in Section 2 and will be used throughout the rest of the paper.
Specifically, $X_{i}^{j}$ refers to the $j$-th component of the $i$-th
individual $\bm{X}_{i}$.

Assume we sample a random vector $(\bm{X}_{1},\dots,\bm{X}_{n})$ with product
measure of the form
$P^{n}(d\bm{x_{1}},\dots,d\bm{x_{n}}):=\prod_{i=1}^{n}P_{i}(d\bm{x_{i}})$. We
draw then an $\bm{\alpha}$ componentwise local differential private view of
the sample $(\bm{X}_{1},\dots,\bm{X}_{n})$ through the privacy mechanism
$\bm{Q}^{n}=(\bm{Q}_{1},\dots,\bm{Q}_{n})$, where
$\bm{Q}_{i}=(Q_{i}^{1},\dots,Q_{i}^{d})$. The privatized samples
$(\bm{Z}_{1},\dots,\bm{Z}_{n})$ is distributed according to some measure
$M^{n}$. As we consider also the case where the algorithm is interactive, in
general the measure $M^{n}$ is not in a product form (with respect to $i$).
However, the proposition on tensorization inequality that follows will yield a
result similar to that provided by independence. It will prove especially
useful for applications.

######  Proposition 3.7.

Let $\alpha_{j}\geq 0$ and assume that $\bm{Q}^{n}$ guarantees the
$\bm{\alpha}$\- CLDP constraint as defined by the condition (2.2). Then, for
any paired sequences of independent vectors $(\bm{X}_{1},\dots,\bm{X}_{n})$
and $(\bm{\tilde{X}}_{1},\dots,\bm{\tilde{X}}_{n})$ of distributions
$P^{n}=\prod_{i=1}^{n}P_{i}$ and $\tilde{P}^{n}=\prod_{i=1}^{n}\tilde{P}_{i}$
respectively, we have

$d_{KL}(M^{n},\tilde{M}^{n})\leq\sum_{h=1}^{n}\Big{(}\sum_{k=1}^{d}\sum_{(j_{1},\dots,j_{k})}\prod_{i=1}^{k}(e^{\alpha_{j_{i}}}-1)d_{TV}(L_{(X_{h}^{j_{1}},\dots,X_{h}^{j_{k}})},L_{(\tilde{X}_{h}^{j_{1}},\dots,\tilde{X}_{h}^{j_{k}})})\Big{)}^{2},$
(3.15)

where the inner summation is on $j_{1}<\dots<j_{k}$ any $k$ distinct indexes
in $\\{1,\dots,d\\}$.

Assume now that the samples $(\bm{X}_{1},\dots,\bm{X}_{n})$ and
$(\bm{\tilde{X}}_{1},\dots,\bm{\tilde{X}}_{n})$, in addition to being
independent, are identically distributed and thus with laws $P^{n}=P^{\otimes
n}$ and $\tilde{P}^{n}=\tilde{P}^{\otimes n}$. Moreover, we suppose that all
the marginal laws of $\bm{X_{i}}$ and $\bm{\tilde{X}_{i}}$ are equals. Then,
in analogy to Corollary 3.4, the proposition above leads to the following
corollary.

######  Corollary 3.8.

Let $\alpha_{j}\geq 0$ and assume that $\bm{Q}^{n}$ guarantees the
$\bm{\alpha}$\- CLDP constraint as defined by the condition (2.2). Then, for
any paired sequences of iid vectors $(\bm{X}_{1},\dots,\bm{X}_{n})$ and
$(\bm{\tilde{X}}_{1},\dots,\bm{\tilde{X}}_{n})$ of distributions
${P}^{n}={P}^{\otimes n}$ and $\tilde{P}^{n}=\tilde{P}^{\otimes n}$ which are
such that for any $k\in\\{1,\dots,d-1\\}$
$L_{(X^{j_{1}},\dots,X^{j_{k}})}=L_{(\tilde{X}^{j_{1}},\dots,\tilde{X}^{j_{k}})}$,
we have

$\displaystyle d_{KL}(M^{n},\tilde{M}^{n})$ $\displaystyle\leq
n\Big{(}\prod_{j=1}^{d}(e^{\alpha_{j}}-1)\Big{)}^{2}d^{2}_{TV}(L_{(X^{1},\dots,X^{d})},L_{(\tilde{X}^{1},\dots,\tilde{X}^{d})})$
$\displaystyle=n\Big{(}\prod_{j=1}^{d}(e^{\alpha_{j}}-1)\Big{)}^{2}{\color[rgb]{0,0,0}d^{2}_{TV}(P,\tilde{P}).}$

The proof of Proposition 3.7 follows next, while Corollary 3.8 is a direct
consequence of the aforementioned proposition, remarking that in the two inner
sums of (3.15) the only non-zero term is for $k=d$,
$(j_{1},\dots,j_{k})=(1,\dots,d)$.

###### Proof of Proposition 3.7.

We can introduce the marginal distribution of $\bm{Z}_{h}$ conditioned on
$\bm{Z}_{1}=\bm{z}_{1}$, …, $\bm{Z}_{h-1}=\bm{z}_{h-1}$. We denote it as

$M_{h}(\cdot|\bm{Z}_{1}=\bm{z}_{1},\dots,\bm{Z}_{h-1}=\bm{z}_{h-1})=:M_{h}(\cdot|\bm{z}_{1:h-1}).$

Observe that for any $A_{j}\in\Xi_{\mathcal{Z}^{j}}$ and $x\in\mathbb{R}$,
$\bm{z}_{1},\dots,\bm{z}_{h-1}\in\mathbb{R}^{d}$ it is

$\displaystyle M_{h}(\prod_{j=1}^{d}A_{j}|\bm{z}_{1:h-1})$
$\displaystyle=\int_{\bm{\mathcal{X}}}\prod_{j=1}^{d}Q_{h}^{j}(A_{j}|X_{h}^{j}=x,\bm{Z}_{1}=\bm{z}_{1},...,\bm{Z}_{h-1}=\bm{z}_{h-1})P_{h}(dx^{1},\dots,dx^{d})$
$\displaystyle=:\int_{\bm{\mathcal{X}}}\prod_{j=1}^{d}Q_{h}^{j}(A_{j}|X_{h}^{j},\bm{Z}_{1:h-1})P_{h}(dx^{1},\dots,dx^{d}).$

Moreover, we introduce the notation $d_{KL}(M_{h},\tilde{M}_{h})$ for the
integrated Kullback divergence of the conditional distributions on the
$\bm{Z}_{h}$, which is

$\int_{\bm{\mathcal{Z}}^{h-1}}d_{KL}\Big{(}M_{h}(\cdot|\bm{z}_{1:h-1}),\tilde{M}_{h}(\cdot|\bm{z}_{1:h-1})\Big{)}dM^{h-1}(\bm{z}_{1},\dots,\bm{z}_{h-1}).$

Then, the chain rule for Kullback-Lieber divergences as gathered in Chapter
5.3 of [27] provides

$d_{KL}(M^{n},\tilde{M}^{n})=\sum_{h=1}^{n}d_{KL}(M_{h},\tilde{M}_{h}).$

By the definition of $\bm{\alpha}$-CLDP for sequentially interactive privacy
mechanism provided in (2.2), the distribution
$Q_{h}^{j}(A_{j}|X_{h}^{j},\bm{Z}_{1:h-1})$ is $\alpha_{j}$-differentially
private for $X_{h}^{j}$. We can therefore apply Theorem 3.3 on
$d_{KL}\Big{(}M_{h}(\cdot|\bm{z}_{1:h-1}),\tilde{M}_{h}(\cdot|\bm{z}_{1:h-1})\Big{)}$
which entails, together with the chain rule above,

$\displaystyle d_{KL}(M^{n},\tilde{M}^{n})$
$\displaystyle=\sum_{h=1}^{n}\int_{\bm{\mathcal{Z}}^{h-1}}d_{KL}\Big{(}M_{h}(\cdot|\bm{z}_{1:h-1}),\tilde{M}_{h}(\cdot|\bm{z}_{1:h-1})\Big{)}dM^{h-1}(\bm{z}_{1},\dots,\bm{z}_{h-1})$
$\displaystyle=\sum_{h=1}^{n}\int_{\bm{\mathcal{Z}}^{h-1}}\Big{(}\sum_{k=1}^{d}\sum_{(j_{1},\dots,j_{k})}\prod_{i=1}^{k}(e^{\alpha_{j_{i}}}-1)$
$\displaystyle\times
d_{TV}(L_{(X_{h}^{j_{1}},\dots,X_{h}^{j_{k}}|\bm{z}_{1:h-1})},L_{(\tilde{X}_{h}^{j_{1}},\dots,\tilde{X}_{h}^{j_{k}}|\bm{z}_{1:h-1})})\Big{)}^{2}dM^{h-1}(\bm{z}_{1},\dots,\bm{z}_{h-1}),$

where we have denoted as
$L_{(X_{h}^{j_{1}},\dots,X_{h}^{j_{k}}|\bm{z}_{1:h-1})}$ the conditional
distribution of $X_{h}^{j_{1}},\dots,X_{h}^{j_{k}}$ given the first $h-1$
values $\bm{Z}_{1},\dots,\bm{Z}_{h-1}$. Clearly in an analogous way
$L_{(\tilde{X}_{h}^{j_{1}},\dots,\tilde{X}_{h}^{j_{k}}|\bm{z}_{1:h-1})}$ is
the conditional distribution of
$\tilde{X}_{h}^{j_{1}},\dots,\tilde{X}_{h}^{j_{k}}$ given the first $h-1$
values $\bm{Z}_{1},\dots,\bm{Z}_{h-1}$. However, by construction, the random
variables $\bm{X}_{h}$ are conditionally independent, which implies that
$L_{(X_{h}^{j_{1}},\dots,X_{h}^{j_{k}}|\bm{z}_{1:h-1})}=L_{(X_{h}^{j_{1}},\dots,X_{h}^{j_{k}})}$
and
$L_{(\tilde{X}_{h}^{j_{1}},\dots,\tilde{X}_{h}^{j_{k}}|\bm{z}_{1:h-1})}=L_{(\tilde{X}_{h}^{j_{1}},\dots,\tilde{X}_{h}^{j_{k}})}$.
It yields

$\displaystyle d_{KL}(M^{n},\tilde{M}^{n})$
$\displaystyle\leq\sum_{h=1}^{n}\Big{(}\sum_{k=1}^{d}\sum_{(j_{1},\dots,j_{k})}\prod_{i=1}^{k}(e^{\alpha_{j_{i}}}-1)d_{TV}(L_{(X_{h}^{j_{1}},\dots,X_{h}^{j_{k}})},L_{(\tilde{X}_{h}^{j_{1}},\dots,\tilde{X}_{h}^{j_{k}})})\Big{)}^{2}$
$\displaystyle\times\int_{\bm{\mathcal{Z}}^{h-1}}dM^{h-1}(\bm{z}_{1},\dots,\bm{z}_{h-1}).$

The proof is then concluded once we remark that the integral in
$dM^{h-1}(\bm{z}_{1},\dots,\bm{z}_{h-1})$ is equal to $1$. ∎

###  3.3 Contraction on $f$-divergence

In this section we present a result similar to (3.3), but where we control a
family of $f$-divergences different from the Kullback Lieber distance. For
$f:\mathbb{R}_{+}\to\mathbb{R}\cup\\{\infty\\}$ with $f(1)=0$ we define the
$f$ divergence between two distributions as $D_{f}(P\|Q)=\int
f\left(\frac{dP}{dQ}\right)dQ$. In the sequel, we focus on $f$-divergences
with $f(t)=f_{l}(t)=\lvert t-1\rvert^{l}$ for $l>1$.

We are in the same context and use the same notations as in Section 3.1.
Recall that $\bm{Q}=(Q^{1},\dots,Q^{d})$ is a family of $d$ kernels, where
$Q^{j}$ is a randomization from some space $\mathcal{X}^{j}$ to
$\mathcal{Z}^{j}$. In this section we assume that for all $j$ there exists a
reference measure $\mu^{j}$ on $\mathcal{Z}^{j}$ such that
$\frac{dQ^{j}(z^{j}\mid X_{j}=x)}{d\mu^{j}(z^{j})}$ is given as a positive
density $q(z^{j}\mid X^{j}=x)$. Moreover, we do not assume that the
$\bm{\alpha}$-CLDP (2.3) constraint is valid. Instead, we assume that for some
$l>1$,

$\forall
j\in\\{1,\dots,d\\},\sup_{x,x^{\prime}\in\mathcal{X}^{j}}D_{f_{l}}(Q^{j}(\cdot\mid
X^{j}=x^{\prime})\|Q^{j}(\cdot\mid X^{j}=x))\leq(\varepsilon_{j})^{l},$ (3.16)

with some positive constants $\varepsilon_{1},\dots,\varepsilon_{d}$.

The following proposition is an extension of Proposition 8 in [20]. Its proof
is given in the Appendix.

######  Proposition 3.9.

Assume $l>1$. We have

$D_{f_{l}}(M\|\tilde{M})^{1/l}\leq\sum_{k=1}^{d}\leavevmode\nobreak\
\sum_{1\leq j_{1}<\dots<j_{k}\leq
d}\big{(}\prod_{i=1}^{k}\varepsilon_{j_{i}}\big{)}d_{TV}(L_{(X^{j_{1}},\dots,X^{j_{k}})},L_{(\tilde{X}^{j_{1}},\dots,\tilde{X}^{j_{k}})}).$
(3.17)

##  4 Applications to statistical inference

In this upcoming section, one objective is to demonstrate the usefulness of
the bounds on divergences between distributions that have been accumulated in
Section 3. We will show versatile applications of these bounds in different
statistical problems. First, we study how information about a private
characteristic of an individual can be revealed by the public views of other
characteristics of the same individual. For this problem, the results obtained
in Section 3 are insightful tools that lead us to introduce the quantity (4.2)
as the main parameter for measuring information leakage. In the following, we
will also provide details on the estimation of covariance and density in a
locally private and multivariate context. For these statistical problems, we
construct explicit estimators, and the results of Section 3 can be used to
derive the rate optimality of these estimators. Finally, we propose adaptive
versions of our estimators.

###  4.1 Effective privacy level

When the data $X^{1},\dots,X^{d}$ are disclosed by independent channels and
with different privacy levels $\alpha_{1},\dots,\alpha_{d}$, a natural
question is how precisely the value of one marginal, say $X^{1}$, could be
revealed by the observations of $Z^{1},\dots,Z^{d}$, which are publicly
available. This question leads to relate the values
$\alpha_{1},\dots,\alpha_{d}$ with the effective level of protection for the
raw data $X^{1}$.

The case where some variable ${X}^{1}\in\mathcal{X}^{1}$ is privatized using a
Markov kernel into the public data ${Z^{1}}\in\mathcal{Z}^{1}$ is the
situation studied in [42] and [19]. It is known from [19] that if the privacy
channel is $\alpha$-LDP, then for all $x^{1},x^{1\prime}\in{\mathcal{X}^{1}}$
and $\psi:{\mathcal{Z}^{1}}\to\\{x^{1},x^{1\prime}\\}$ we have

$\frac{1}{2}\mathbb{P}\left(\psi(Z^{1})\neq x^{1}\mid
X=x^{1}\right)+\frac{1}{2}\mathbb{P}\left(\psi(Z^{1})\neq x^{1\prime}\mid
X=x^{1\prime}\right)\geq\frac{1}{1+e^{\alpha}},$ (4.1)

This means that even if someone accesses two values $x^{1}$ and $x^{1\prime}$
from the raw data set, it will be impossible for them to determine with a high
level of certainty which of the values corresponds to a specific observation,
denoted as $Z^{1}$. Any attempt to make a decision in this regard would result
in an error, albeit with minimal probability.

If a vector $\bm{X}$ is privatized with independent channel for each
components ant the components of $\bm{X}$ are independent, then the result of
[19] applies componentwise. Indeed, the observations of $Z^{2},\dots,Z^{d}$
carry no information about the value of $X^{1}$ and thus recovering
information on $X^{1}$ from $\bm{Z}$ or from $Z^{1}$ is equivalent and a
result like (4.1) applies with $\alpha=\alpha_{1}$.

The situation is more intricate if the components of $\bm{X}$ are dependent,
as the observation of $Z^{2},\dots,Z^{d}$ brings informations on $X^{1}$. In
the extreme situation where all the components of $\bm{X}$ are almost surely
equal $X^{1}=\dots=X^{d}$, it is clear that the observation of
$\bm{Z}=(Z^{1},\dots,Z^{d})$ is a repetition of $d$ independent views of the
same raw data $X^{1}$ with different privacy level. Thus, this mechanism is
equivalent to the privatization of the single variable
$X^{1}\in\mathcal{X}^{1}$ through a channel taking the value
$\bm{Z}=(Z^{1},\dots,Z^{d})\in\bm{\mathcal{Z}}$. By independence of the
$Z^{j}$’s conditional to $X^{1}$ and (2.3), we can check that this mechanism
is a non componentwise $\alpha$-LDP view of $X^{1}$ with
$\alpha=\sum_{j=1}^{d}\alpha_{j}$. In turn, the lower bound (4.1) for deciding
the value of $X^{1}$ from the observation of $\bm{Z}$ holds true with
$\alpha=\sum_{j=1}^{d}\alpha_{j}\geq\alpha_{1}$. This evaluates how the
privacy of $X^{1}$ is deteriorated by observation of the side-channels
$Z^{2},\dots,Z^{d}$ in the worst case scenario $X^{1}=X^{2}=\dots=X^{d}$.

In intermediate situation, we need to introduce some quantity which assesses
the independence of $(X^{2},\dots,X^{d})$ on $X^{1}$. Let us denote by
$q(dx^{2},\dots,dx^{d}\mid X^{1}=x^{1})$ the conditional distribution of
$X^{2},\dots,X^{d}$ conditional to $X^{1}=x^{1}$. We let

$\Delta_{\text{ind}}:=\sup_{x^{1},x^{1\prime}\in\mathcal{X}^{1}}d_{TV}\left(q(dx^{2},\dots,dx^{d}\mid
X^{1}=x^{1}),q(dx^{2},\dots,dx^{d}\mid X^{1}=x^{1\prime})\right),$ (4.2)

which quantifies how close $(X^{2},\dots,X^{d})$ are from being independent
from $X^{1}$. We have indeed $\Delta_{\text{ind}}\in[0,2]$ and
$\Delta_{\text{ind}}=0$ when $X^{1}$ is independent from
$(X^{2},\dots,X^{d})$. We let $m(z_{1},\dots,z_{d}\mid X^{1}=x^{1})$ the
density with respect to $\bm{\mu}$ of the law of $(Z^{1},\dots,Z^{d})$
conditional to $X^{1}=x^{1}$. We have, using the notation of Section 3

$m(z^{1},\dots,z^{d}\mid
X^{1}=x^{1})=\int_{\prod\limits_{j=2}^{d}\mathcal{X}^{j}}\prod_{j=1}^{d}q^{j}(z^{j}\mid
x^{j})q(dx^{2},\dots,dx^{d}\mid X^{1}=x^{1}).$ (4.3)

To elaborate, the function $\bm{z}\mapsto m(\bm{z}\mid X^{1}=x^{1})$ is the
density of the channel which gives $\bm{Z}$ as a public view of the marginal
$X^{1}$, gathering the information directly revealed by the channel $q^{1}$
and indirectly by the channels $q^{j}$, $j\geq 2$. The following proposition
gives an upper bound for the privacy level of this channel. It is essentially
a consequence of Theorem 3.3.

######  Proposition 4.1.

Let $\alpha_{j}\geq 0$, and assume that $\bm{Q}=(Q^{1},\dots,Q^{d})$
guarantees the $\bm{\alpha}$-CLDP constraint as defined by the condition
(2.3). Assume that there exists $\alpha_{\text{max}}$ such that
$\alpha_{j}\leq\alpha_{\text{max}}$ for $j\in\\{2,\dots,d\\}$. Then, we have

$\sup_{x^{1},x^{1\prime}\in\mathcal{X}^{1}}\leavevmode\nobreak\
\frac{m(z^{1},\dots,z^{d}\mid X^{1}=x^{1})}{m(z^{1},\dots,z^{d}\mid
X^{1}=x^{1\prime})}\leq\exp\left(\alpha_{1}+\alpha_{\text{max}}\times(d-1)\Delta_{\text{ind}}\right).$
(4.4)

######  Remark 4.2.

If $x^{1},x^{1\prime}\in\mathcal{X}^{1}$ and
$\psi:\bm{\mathcal{Z}}\to\\{x^{1},x^{1\prime}\\}$ is any measurable map, then
the average probability of mispredicting $X^{1}$ from $\bm{Z}$,
$\frac{1}{2}\mathbb{P}\left(\psi(\bm{Z})\neq x^{1}\mid
X^{1}=x^{1}\right)+\frac{1}{2}\mathbb{P}\left(\psi(\bm{Z})\neq x^{1\prime}\mid
X^{1}=x^{1\prime}\right)$ is lower bounded by the same quantity as in Equation
(4.1) where $\alpha$ is replaced by
$\alpha_{1}+\alpha_{\text{max}}\times(d-1)\Delta_{\text{ind}}$.

###### Proof of Proposition 4.1.

We will apply the results of Section 3 with two well chosen probabilities
$\widetilde{P}$, $\widetilde{P}^{\prime}$ on
$\widetilde{\bm{\mathcal{X}}}=\prod_{j=2}^{d}\mathcal{X}^{j}$. We fix
$x^{1},x^{1\prime}\in\mathcal{X}^{1}$ and let $P$ be the measure on
$\widetilde{\bm{\mathcal{X}}}$ given by

$\widetilde{P}(dx^{2},\dots,dx^{d})=q(dx^{2},\dots,dx^{d}\mid X^{1}=x^{1}).$

We define $\widetilde{P}^{\prime}$ analogously with $x^{1\prime}$ in place of
$x^{1}$. We denote by $\widetilde{M}$ the measure on
$\widetilde{\bm{\mathcal{Z}}}=\prod_{j=2}^{d}\mathcal{Z}^{j}$ of the
privatized view of $P$ through the kernel $\widetilde{Q}=(Q^{2},\dots,Q^{d})$.
In an analogous way, $\widetilde{M}^{\prime}$ is the law of a privatized
version of $\widetilde{P}^{\prime}$. Let us denote by
$\widetilde{m}(z^{2},\dots,z^{d})$ and
$\widetilde{m}^{\prime}(z^{2},\dots,z^{d})$ the densities of $\widetilde{M}$
and $\widetilde{M}^{\prime}$. As emphasized in Remark 3.6, the equation (3.14)
provides a control on the difference between $\widetilde{m}$ and
$\widetilde{m}^{\prime}$, which yields to

$\frac{\lvert\widetilde{m}(z^{2},\dots,z^{d})-\widetilde{m}^{\prime}(z^{2},\dots,z^{d})\rvert}{\widetilde{m}^{\prime}(z^{2},\dots,z^{d})}\leq\sum_{k=1}^{d-1}\sum_{i_{1},\dots,i_{k}}\prod_{u=1}^{k}(e^{\alpha_{i_{u}}}-1)d_{TV}\left(\tilde{P}_{\mid(X^{i_{1}},\dots,X^{i_{k}})},\tilde{P}^{\prime}_{\mid(X^{i_{1}},\dots,X^{i_{k}})}\right)$

where the inner sum is on $2\leq i_{1}<\dots<i_{k}\leq d$ and
$\tilde{P}_{\mid(X^{i_{1}},\dots,X^{i_{k}})}$ is the restriction of the
measure $\tilde{P}$ on $\prod_{u=1}^{k}\mathcal{X}^{i_{u}}$. We use the bound
$d_{TV}\left(\tilde{P}_{\mid(X^{i_{1}},\dots,X^{i_{k}})},\tilde{P}^{\prime}_{\mid(X^{i_{1}},\dots,X^{i_{k}})}\right)\leq
d_{TV}\left(\tilde{P},\tilde{P}^{\prime}\right)$ to deduce,

$\displaystyle\frac{\lvert\widetilde{m}(z^{2},\dots,z^{d})-\widetilde{m}^{\prime}(z^{2},\dots,z^{d})\rvert}{\widetilde{m}^{\prime}(z^{2},\dots,z^{d})}$
$\displaystyle\leq\sum_{k=1}^{d-1}\sum_{i_{1},\dots,i_{k}}\prod_{u=1}^{k}(e^{\alpha_{i_{u}}}-1)d_{TV}\left(\tilde{P},\tilde{P}^{\prime}\right)$
$\displaystyle\leq\sum_{k=1}^{d-1}\binom{p-1}{k}(e^{\alpha_{\text{max}}}-1)^{k}d_{TV}\left(\tilde{P},\tilde{P}^{\prime}\right),\text{
using $\alpha_{j}\leq\alpha_{\text{max}}$ for $j\geq 2$,}$
$\displaystyle\leq\left[e^{\alpha_{\text{max}}\times(p-1)}-1\right]d_{TV}\left(\tilde{P},\tilde{P}^{\prime}\right),\text{
from the binomial formula.}$

The definitions of $\widetilde{P}$ and $\widetilde{P}^{\prime}$ as conditional
distributions imply that
$d_{TV}\left(\tilde{P},\tilde{P}^{\prime}\right)\leq\Delta_{\text{ind}}$, and
thus we deduce

$\frac{\widetilde{m}(z^{2},\dots,z^{d})}{\widetilde{m}^{\prime}(z^{2},\dots,z^{d})}\leq
1+\left[e^{\alpha_{\text{max}}\times(p-1)}-1\right]\Delta_{\text{ind}}.$

Using the simple inequality $1+(e^{\alpha}-1)q\leq e^{\alpha q}$ for
$\alpha,q\geq 0$, we get

$\frac{\widetilde{m}(z^{2},\dots,z^{d})}{\widetilde{m}^{\prime}(z^{2},\dots,z^{d})}\leq
e^{\alpha_{\text{max}}\times(p-1)\Delta_{\text{ind}}}.$ (4.5)

Recalling that $\widetilde{m}(z^{2},\dots,z^{d})$ is the density of the
privatized view of $\tilde{P}$ through $\widetilde{Q}=(Q^{2},\dots,Q^{d})$, we
have

$\widetilde{m}(z^{2},\dots,z^{d})=\int_{\prod\limits_{j=2}^{d}\mathcal{X}^{j}}\prod_{j=2}^{d}q^{j}(z^{j}\mid
x^{j})q(dx^{2},\dots,dx^{d}\mid X^{1}=x^{1}),$

and thus by comparison with (4.3)

$m(z^{1},\dots,z^{d}\mid X^{1}=x^{1})=q^{1}(z^{1}\mid
x^{1})\widetilde{m}(z_{2},\dots,z_{d}).$

An analogous relation holds true for $m^{\prime}$ and in turn,

$\frac{m(z^{1},\dots,z^{d}\mid X^{1}=x^{1})}{m(z^{1},\dots,z^{d}\mid
X^{1}=x^{1\prime})}=\frac{q(z^{1}\mid x^{1})}{q(z^{1}\mid
x^{1\prime})}\frac{\widetilde{m}(z^{2},\dots,z^{d})}{\widetilde{m}^{\prime}(z^{2},\dots,z^{d})}.$

Now, the proposition is a consequence of (2.4) and (4.5). ∎

###  4.2 Locally private joint moment estimation

In this section we assume that $\bm{X}=(X^{1},\dots,X^{d})$ is a d-dimensional
vector, for which we want to estimate the moment
$\gamma=\mathbb{E}\left[\prod_{j=1}^{d}X^{j}\right]$ under local differential
privacy constraints. Again, the components are made public separately. A
particular application of our results for the case $d=2$ will give the
estimation of the covariance and correlation discussed in Section 4.2.2.

####  4.2.1 Local differential private estimator

We assume that $\bm{X}_{1},\dots,\bm{X}_{n}$ are $n$ iid copies of
$\bm{X}=(X^{1},\dots,X^{d})$. As in this paper we stick to the framework of
local differential privacy, we want to introduce an anonymization procedure to
transform the $X_{i}^{j}$ to some

$Z_{i}^{j}\sim q_{j}(dz|X_{i}^{j})=q_{j}(z|X_{i}^{j})dz$

which satisfies the condition of local differential privacy, as in (2.4). In
particular, the privacy mechanism we consider in this example is non-
interactive.
It is well-known that adding centered Laplace distributed noise on bounded
random variables provides $\alpha$ differential privacy (cfr [19], [31],
[36]). This motivates our choice for the anonymization procedure, which
consists in constructing the public version of the $\bm{X}_{i}$ by using a
Laplace mechanism with an independent channel for each component. Let us
denote $\mathcal{E}^{i}_{j}$ for
$(i,j)\in\\{1,\dots,n\\}{\color[rgb]{0,0,0}\times\\{1,\dots,d\\}}$ a family of
independent random variables, such that $(\mathcal{E}^{i}_{j})_{i}$ are iid
sequences with law $\mathcal{L}(\frac{2T^{(j)}}{\alpha_{j}})$ for
$j=1,\dots,d$. The truncation $T^{(j)}>0$ will be specified later. We assume
that the variables $\mathcal{E}^{j}_{i}$ are independent from the data
$\bm{X}_{1},\dots,\bm{X}_{n}$ and we set

$Z^{j}_{i}=\left[X^{j}_{i}\right]_{T^{(j)}}+\mathcal{E}^{j}_{i},\quad\forall(i,j)\in\\{1,\dots,n\\}{\color[rgb]{0,0,0}\times\\{1,\dots,d\\},}$
(4.6)

where $\left[x\right]_{T}=\max(\min(x,T),-T)$.

Denoting by $z\mapsto q^{j}(z\mid X^{j}_{i}=x)$ the density of the privatized
data $Z^{j}_{i}$ conditional to $X^{j}_{i}=x$ for $j\in\\{1,\dots,d\\}$, it is
a direct application of Lemma 2.2 to check that the local differential privacy
control (2.4) holds true, as stated in the following lemma.

######  Lemma 4.3.

For any $i\in\\{1,\dots,n\\}$ and $j\in\\{1,\dots,d\\}$, the random variables
$Z^{j}_{i}=\left[X^{j}_{i}\right]_{T^{(j)}}+\mathcal{E}^{j}_{i}$, with
$\mathcal{E}_{i}^{j}$ iid $\sim\mathcal{L}(\frac{2T^{(j)}}{\alpha_{j}})$, are
$\alpha_{j}$ differential private views of the original $X_{i}^{j}$.

###### Proof.

As $\mathcal{E}_{i}^{j}$ is distributed as a centered Laplace random variable
with scale parameter $\frac{2T^{(j)}}{\alpha_{j}}$, its density at the point
$x\in\mathbb{R}$ is given by
$\frac{1}{2T^{(j)}}\alpha_{j}\exp(-\frac{1}{2T^{(j)}}\alpha_{j}|x|)$. Then,
the reverse triangle inequality and the fact that
$\left[X^{j}_{i}\right]_{T^{(j)}}$ is bounded by $T^{(j)}$ provide

$\displaystyle\sup_{z\in\mathcal{Z}}\frac{q^{j}(z|X_{i}^{j}=x)}{q^{j}(z|X_{i}^{j}=x^{\prime})}$
$\displaystyle\leq\sup_{z\in\mathcal{Z}}\exp\Big{(}-\frac{1}{2T^{(j)}}\alpha_{j}(z-\left[x\right]_{T^{(j)}})+\frac{1}{2T^{(j)}}\alpha_{j}(z-\left[x^{\prime}\right]_{T^{(j)}})\Big{)}$
$\displaystyle\leq\exp\Big{(}\frac{1}{2T^{(j)}}\alpha_{j}(\left[x\right]_{T^{(j)}}-\left[x^{\prime}\right]_{T^{(j)}})\Big{)}$
$\displaystyle\leq\exp(\alpha_{j}),$

as we wanted. ∎

Assume that, for $j\in\\{1,\dots,d\\}$ we have $X^{j}\in\mathbf{L}^{k_{j}}$
for $k_{j}>1$, with the condition $\sum_{j=1}^{d}\frac{1}{k_{j}}<1$. By
Hölder’s inequality, it ensures that $\mathbb{E}[|X^{1}\times\dots\times
X^{d}|]<\infty$. The goal is to estimate
$\gamma:=\mathbb{E}[X^{1}\times\dots\times X^{d}]$.

The estimation of the expectation of the marginals
$m^{(j)}:=\mathbb{E}[X^{j}]$ is discussed in [19], from which we recall the
result. We will state later the result on the estimation of the cross term
$\gamma=\mathbb{E}[X^{1}\times\dots\times X^{d}]$.

Let

$\displaystyle\hat{m}^{(j)}_{n}:=\frac{1}{n}\sum_{i=1}^{n}Z_{i}^{j},\text{for
$j\in\\{1,\dots,d\\}$},$ (4.7)
$\displaystyle\hat{\gamma}_{n}:=\frac{1}{n}\sum_{i=1}^{n}\prod_{j=1}^{d}Z_{i}^{j}.$
(4.8)

######  Theorem 4.4 (Corollary 1 in [19]).

Let $0<\alpha_{j}\leq 1$. Assume $k_{j}>1$ and set
$\widetilde{T}^{(j)}=(n\alpha^{2}_{j})^{1/(2k_{j})}$ for
$j\in{\color[rgb]{0,0,0}\\{1,\dots,d\\}}$. Then, there exists $c>0$ such that
for all $n\geq 1$, $j\in{\color[rgb]{0,0,0}\\{1,\dots,d\\}}$,

$\mathbb{E}\left[\left\lvert{\color[rgb]{0,0,0}\hat{m}^{(j)}_{n}}-m^{(j)}\right\rvert^{2}\right]\leq
c(n\alpha^{2}_{j})^{-\frac{k_{j}-1}{k_{j}}}.$

In Corollary 1 in [19], the privacy level $\alpha$ is the same for all
components. However, the result is useful also in our context, as we plan to
apply Corollary 1 in [19] with $d=1$ separately to each components of
$\bm{X}$. By [19], the choice of truncation
$\widetilde{T}^{(j)}=(n\alpha^{2}_{j})^{1/(2k_{j})}$ is optimal when
estimating $m^{(j)}$. The result for the estimation of the joint moment is the
following.

######  Theorem 4.5.

Let $\alpha_{j}\leq 1$. Assume $1/k_{1}+\dots+1/k_{d}<1$ and set
$T^{(j)}=(n\prod_{l=1}^{d}\alpha^{2}_{l})^{1/(2k_{j})}$ for
$j\in{\color[rgb]{0,0,0}\\{1,\dots,d\\}}$. Then, there exists $c>0$, such that
for all $n\geq 1$,

$\mathbb{E}\left[\left\lvert\hat{\gamma}_{n}-\gamma\right\rvert^{2}\right]\leq
c(n\prod_{j=1}^{d}\alpha^{2}_{j})^{-\frac{\overline{k}-{\color[rgb]{0,0,0}d}}{\overline{k}}},\\\
$ (4.9)

where
$\overline{k}=d\left(\frac{1}{k_{1}}+\dots+\frac{1}{k_{d}}\right)^{-1}>d$ is
the harmonic mean of $k_{1},\dots k_{d}$. The constant $c$ does not depend on
$\alpha_{j}$, $n$, as soon as
$n\alpha^{2}_{1}\times\dots\times\alpha_{d}^{2}\geq 1$.

The proof of this theorem is in the Appendix. It relies on a bias-variance
trade-off, and the choice for $T^{(j)}$, given in the statement, is in this
regard optimal.

######  Remark 4.6.

The upper bound provided by Theorem 4.5 can be compared with the case where
the private data $\bm{X}_{i}=(X_{i}^{1},\dots,X_{i}^{d})$ is disclosed using a
single channel that accesses all components of $\bm{X}_{i}$ and satisfying LDP
constraint with parameter $\overline{\bm{\alpha}}$ . In this scenario, we can
apply the results of Section 3.2.1 in [19] to estimate the mean of the iid one
dimensional private data $(\Gamma_{i})_{i=1,\dots,n}$, where
$\Gamma_{i}=\prod_{j=1}^{d}X^{j}_{i}$, using a locally differentially
privatized version of $\Gamma_{i}$. By applying Hölder’s inequality, we can
see that $\Gamma_{1}\in\mathbf{L}^{\overline{k}/{\color[rgb]{0,0,0}d}}$, and
hence by Corollary 1 in [19], there exists an estimator $\tilde{\gamma}_{n}$
such that

$\mathbb{E}\left[(\tilde{\gamma}_{n}-\gamma)^{2}\right]\leq
c(n{\color[rgb]{0,0,0}\overline{\bm{\alpha}}}^{2})^{-\frac{\overline{k}/{\color[rgb]{0,0,0}d}-1}{\overline{k}/{\color[rgb]{0,0,0}d}}}=c(n{\color[rgb]{0,0,0}\overline{\bm{\alpha}}}^{2})^{-\frac{\overline{k}-{\color[rgb]{0,0,0}d}}{\overline{k}}},$

where $\overline{\bm{\alpha}}$ is the LDP level when disclosing the
$\bm{X}_{i}$’s.
We can conclude that the rate exponent for estimating $\gamma$ is unchanged
when the data are disclosed using independent channels for each component,
compared to a situation where both components can be accessed before publicly
releasing the data. However, the effective number of data is reduced from
$n\overline{\bm{\alpha}}^{2}$ to $n\prod_{j=1}^{d}\alpha_{j}^{2}$. If we
consider the special case where $\alpha_{1}=\dots=\alpha_{d}=\alpha$ we know
that, by Lemma 2.1, the CLDP kernel is a special case of LDP kernel with
$\overline{\bm{\alpha}}=d\alpha$. Thus, it is evident that the loss is
significant for small values of $\alpha$, as $n\alpha^{2d}<nd^{2}\alpha^{2}$.
On the other hand, the loss can be moderate if the $\alpha_{j}$ are close to
$1$. We will see in Section 4.2.3 that this loss is unavoidable.

######  Remark 4.7.

The construction of the estimator $\hat{\gamma}_{n}$ necessitates to choose
the truncation levels $T^{(j)}$’s. The optimal choice is given in the
statement of Theorem 4.5 and relies on the number of finite moments $k_{j}$’s
of each components of the vector $\bm{X}$. In practice, these constants
$k_{j}$’s are unknown and the choice of the optimal $T^{(j)}$’s seems
unfeasible. We will present in Section 4.2.4 an adaptive version of the
estimator $\hat{\gamma}_{n}$ where the choice of the truncation levels is
data-driven, while preserving the rate of convergence of the estimator, up to
a log-term loss.

####  4.2.2 Application to the covariance estimation

We now focus on the estimation of the covariance between two random variables
when the associated data are privatized in the componentwise way. For
simplicity, we assume that we are dealing with a $2$-dimensional vector
$\bm{X}=(X^{1},X^{2})$ with $k_{1}^{-1}+k_{2}^{-1}<1$. It ensures that
$\mathbb{E}[|X^{1}X^{2}|]<\infty$, by Hölder’s inequality. The goal is to
estimate
$\theta:=\text{cov}(X^{1},X^{2})=\mathbb{E}[X^{1}X^{2}]-\mathbb{E}[X^{1}]\mathbb{E}[X^{2}]$.
We assume that $n$ private data $(\bm{X}_{i})_{i=1,\dots,n}$ are iid and that
the statistician can observe public views obtained through a CLDP mechanism
with parameter $\bm{\alpha}=(\alpha_{1},\alpha_{2})$. We apply the results of
Section 4.2.1. Consistently with the notations of this section, we have
$\hat{\gamma}_{n}=\frac{1}{n}\sum_{i=1}^{n}Z^{1}_{i}Z^{2}_{i}$, and define
$\hat{\theta}_{n}:=\hat{\gamma}_{n}-\hat{m}^{(1)}_{n}\hat{m}^{(2)}_{n}$.

The result for the estimation of the covariance is the following. Its proof is
given in the Appendix.

######  Corollary 4.8.

Let $\alpha_{j}\leq 1$. Assume $1/k_{1}+1/k_{2}<1$ and set
$T^{(j)}=(n\alpha^{2}_{1}\alpha^{2}_{2})^{1/(2k_{j})}$ for $j\in\\{1,2\\}$.
Then, there exists $c>0$, such that for all $n\geq 1$,

$\mathbb{E}\left[\left\lvert\hat{\theta}_{n}-\theta\right\rvert^{2}\right]\leq
c(n\alpha^{2}_{1}\alpha^{2}_{2})^{-\frac{\overline{k}-2}{\overline{k}}},$
(4.10)

where $\overline{k}=2\left(\frac{1}{k_{1}}+\frac{1}{k_{2}}\right)^{-1}>2$ is
the harmonic mean of $k_{1}$, $k_{2}$. The constant $c$ does not depend on
$\alpha_{1}$, $\alpha_{2}$ $n$, as soon as $n\alpha^{2}_{1}\alpha_{2}^{2}\geq
1$.

######  Remark 4.9.

By definitions (4.6)–(4.8), when estimating $\theta=\gamma-m^{(1)}m^{(2)}$, we
use the same truncation levels $T^{(j)}$ for the estimation of $\gamma$,
$m^{(1)}$ and $m^{(2)}$. It would be possible to use the optimal levels
$\widetilde{T}^{(j)}=(n\alpha^{2}_{j})^{1/(2k_{j})}$ for the estimation of
$m^{(1)}$, $m^{(2)}$ and the optimal levels
$T^{(j)}=(n\alpha^{2}_{1}\alpha^{2}_{2})^{1/(2k_{j})}$ for the estimation of
$\gamma$. However, this approach would necessitate publicly disclosing two
values for each private data point: one corresponding to the truncation level
$\widetilde{T}^{(j)}$ and one with level ${T}^{(j)}$. As a result, the overall
privacy of the procedure would be reduced. In Section 4.2.4, we will explore
another scenario where we must disclose multiple public values for each
private data point.

######  Remark 4.10.

Assuming that $k_{1}>2$ and $k_{2}>2$, it is also possible to estimate the
correlation between the two variables $X^{1}$ and $X^{2}$. From the definition
$\mathop{cor}(X^{1},X^{2})=\mathop{cov}(X^{1},X^{2})/\sqrt{\mathop{var}(X^{1})\mathop{var}(X^{2})}$
and since the covariance is estimated according to Corollary 4.8, it remains
to estimate the variance of $X^{1}$ and $X^{2}$ and deduce an estimate of the
correlation as a ratio. Since the estimation of the variance of each variable
reduces to the estimation on the marginal laws, we can use the result in [19],
recalled by Theorem 4.4. As $|X^{1}|^{2}\in\mathbf{L}^{k_{1}/2}$, we can
derive that the rate of estimation of $\mathbb{E}[|X^{1}|^{2}]$ is
$(n\alpha_{1}^{2})^{\frac{k_{1}/2-1}{2k_{1}/2}}=(n\alpha_{1}^{2})^{1/2-1/k_{1}}$.
We can deduce that it is possible to estimate $\mathop{var}(X^{1})$ with some
estimator converging with rate $(n\alpha_{1}^{2})^{1/2-1/k_{1}}$, and
analogously $\mathop{var}(X^{2})$ is estimated with rate
$(n\alpha_{2}^{2})^{1/2-1/k_{2}}$. On the other hand, from Corollary 4.8 the
covariance is estimated at rate
$(n\alpha_{1}^{2}\alpha_{2}^{2})^{\frac{1}{2}-\frac{1}{2k_{1}}-\frac{1}{2k_{2}}}$.
If $k_{1}=k_{2}=k$, and using that $\alpha_{j}\leq 1$, we see that the slower
rate is given by the estimation of the covariance. Consequently, the
correlation coefficient can be estimated with an estimator having at least a
rate given by
$(n\alpha_{1}^{2}\alpha_{2}^{2})^{\frac{1}{2}-\frac{1}{{\color[rgb]{0,0,0}\overline{k}}}}$.
If $k_{1}\neq k_{2}$, the rate of this estimation procedure is at most the
worst of the three rates, which is now dependent on the relative positions of
$\alpha_{1}$ and $\alpha_{2}$.

####  4.2.3 Lower bound for the joint moment estimation

For $k_{1}>1,\dots,k_{d}>1$ with $1/k_{1}+\dots+1/k_{d}<1$, we introduce the
notation

$\mathcal{P}_{k_{1},\dots,k_{d}}=\left\\{P,\quad\text{probability on
$\mathbb{R}^{d}$ such that }\mathbb{E}_{P}[|X^{j}|^{k_{j}}]\leq 1,\text{ for
$j\in\\{1,\dots,d\\}$ }\right\\},$

where $\bm{X}=(X^{1},\dots,X^{d})$ is the canonical random variable on
$\mathbb{R}^{d}$. For $P\in\mathcal{P}_{k_{1},\dots,k_{d}}$, we set

$\gamma(P)=\mathbb{E}_{P}\left[{\color[rgb]{0,0,0}\prod_{j=1}^{d}X^{j}}\right].$

We denote by $\mathcal{Q}_{\bm{\alpha}}$ the set of privacy mechanisms, where
for simplicity we restrict ourself to non interactive kernels. Thus,
$\bm{Q}=(Q^{1},\dots,Q^{d})\in\mathcal{Q}_{\bm{\alpha}}$ is such that $Q^{j}$
is a Markov kernel from $\mathcal{X}^{j}=\mathbb{R}$ to some measurable space
$(\mathcal{Z}^{j},\Xi_{\mathcal{Z}^{j}})$, and the condition (2.3) is
satisfied for $j=1,\dots,d$.

The private data are given by the iid sequence $(\bm{X}_{i})_{i=1,\dots,n}$.
We assume that the public data $(\bm{Z}_{i})_{i=1,\dots,n}$ are given by the
non interactive mechanism where the variable $Z_{i}^{j}$ is drawn according to
the law $Q^{j}(dz\mid X_{i}^{j})$.

We introduce the minimax risk

$\mathcal{M}_{n}(\gamma(\mathcal{P}_{{\color[rgb]{0,0,0}k_{1},\dots,k_{d}}}),\bm{\alpha})=\inf_{\bm{Q}\in\mathcal{Q}_{\bm{\alpha}}}\inf_{\hat{\gamma}_{n}}\sup_{{P\in\mathcal{P}_{{\color[rgb]{0,0,0}k_{1},\dots,k_{d}}}}}\mathbb{E}_{P}\left[\left(\hat{\gamma}_{n}-\gamma(P)\right)^{2}\right],$

where $\hat{\gamma}_{n}$ is any
$\hat{\gamma}_{n}((Z_{i}^{j})_{\begin{subarray}{c}1\leq i\leq n\\\ 1\leq
j\leq{\color[rgb]{0,0,0}d}\end{subarray}})$ measurable function from
$\big{(}\prod_{j=1}^{d}\mathcal{Z}^{j}\big{)}^{n}$. taking values in
$\mathbb{R}$, with finite second moment.

######  Theorem 4.11.

There exists some constant $c$ such that,

$\mathcal{M}_{n}(\gamma(\mathcal{P}_{{\color[rgb]{0,0,0}k_{1},\dots,k_{d}}}),\bm{\alpha})\geq{\color[rgb]{0,0,0}c(n\prod_{j=1}^{d}\lvert
e^{\alpha_{j}}-1\rvert^{2})^{-\frac{\overline{k}-d}{\overline{k}}}}$

for all $n\geq 1$, $n\prod_{j=1}^{d}\lvert e^{\alpha_{j}}-1\rvert^{2}\geq 1$.

######  Remark 4.12.

Comparing with Theorem 4.5, we see that when $\alpha_{j}\leq 1$ the rate
$(n\prod_{j=1}^{d}\alpha_{j}^{2})^{\frac{\overline{k}-{\color[rgb]{0,0,0}d}}{\overline{k}}}$
achieved by the estimator of Section 4.2.1. can not be improved.

###### Proof.

To get a lower bound for
$\mathcal{M}_{n}(\gamma(\mathcal{P}_{k_{1},\dots,k_{d}}),\bm{\alpha})$ we want
to apply the two hypothesis method (see for example Section 2.3 in [39]). We
need to construct $P$ and $P^{*}$ such that

  1. 1.

$P$, $P^{*}$ are elements of $\mathcal{P}_{k_{1},\dots,k_{d}}$,

  2. 2.

$\exists c>0$ with $\lvert\gamma(P)-\gamma(P^{*})\rvert\geq
c(n{\color[rgb]{0,0,0}\prod_{j=1}^{d}\lvert
e^{\alpha_{j}}-1\rvert^{2}})^{-\frac{\overline{k}-{\color[rgb]{0,0,0}d}}{2\overline{k}}}$,

  3. 3.

$\exists\epsilon_{0}>0$ such that
$d_{KL}\Big{(}Law((\bm{Z}_{i})_{i=1,\dots,n}),Law((\bm{Z}^{*}_{i})_{i=1,\dots,n})\Big{)}<\epsilon_{0}<2$,

where
$\bm{Z}_{i}={\color[rgb]{0,0,0}(Z_{i}^{1},\dots,{\color[rgb]{0,0,0}Z_{i}^{d}})}$
for $i=1,\dots,n$ are the public views of
$\bm{X}_{i}={\color[rgb]{0,0,0}(X_{i}^{1},\dots,X_{i}^{d})}$, $i=1,\dots,n$ a
iid sequence of random variables with law $P$, and
$\bm{Z}_{i}^{*}={\color[rgb]{0,0,0}(Z_{i}^{1},\dots,Z_{i}^{d})}$ are the
public views of
$\bm{X}^{*}_{i}={\color[rgb]{0,0,0}(X_{i}^{*,1},\dots,X_{i}^{*,d})}$,
$i=1,\dots,n$ a iid sequence of random variables with law $P^{*}$.

Let $0<\delta<1$ be a parameter whose value will be calibrated later. We
denote by $P$ the probability on $\mathbb{R}^{2}$ which makes
$\bm{X}={\color[rgb]{0,0,0}(X^{1},\dots,X^{d})}$ a discrete random variable
taking values in $\prod_{j=1}^{d}\\{-\delta^{1/k_{j}},0,-\delta^{1/k_{j}}\\}$
with the joint distribution given by

$P(X^{1}=a_{1}\delta^{-1/k_{1}},\dots,X^{d}=a_{d}\delta^{-1/k_{1}})=:p_{a_{1},\dots,a_{d}}$

for all $(a_{1},\dots,a_{d})\in\\{-1,0,1\\}^{d}$ and

$p_{a_{1},\dots,a_{d}}=\begin{cases}1-\delta&\text{if
$a_{1}=\dots=a_{d}=0$,}\\\ \delta(\frac{1}{2})^{d}&\text{if $a_{j}\neq
0,\forall j$,}\\\ 0&\text{if $\exists j_{1},j_{2}$ with $a_{j_{1}}=0$,
$a_{j_{2}}\neq 0$.}\end{cases}$

It means that, under $P$, we flip a coin to decide if all the $X^{j}$ are zero
with probability $1-\delta$, and otherwise the $X^{j}$ are taking the extremal
values $\pm\delta^{-1/k_{j}}$ independently and with equal probability. We can
check that
$P(X^{j}=\delta^{-1/k_{j}})=P(X^{j}=-\delta^{-1/k_{j}})=\frac{\delta}{2}$ and
$P(X^{j}=0)=1-\delta$. Thus $\mathbb{E}[|X^{j}|^{k_{j}}]=1$ for all
$j\in\\{1,\dots,d\\}$ implying that $P\in\mathcal{P}_{k_{1},\dots,k_{d}}$.
Moreover,

$\displaystyle\gamma(P)$
$\displaystyle=\mathbb{E}_{P}\left[X^{1}\times\dots\times
X^{d}\right]=(1-\delta)\times 0+\delta\sum_{(a_{1},\dots,a_{d})\in
\\{-1,1\\}^{d}}\left(\frac{1}{2}\right)^{d}\prod_{j=1}^{d}(a_{j}\delta^{k_{j}})$
$\displaystyle=\delta^{1-\sum_{j=1}^{d}\frac{1}{k_{j}}}\left(\frac{1}{2}\right)^{d}\sum_{l=0}^{d}\binom{d}{l}(-1)^{l}=\delta^{1-\sum_{j=1}^{d}\frac{1}{k_{j}}}\left(\frac{1}{2}\right)^{d}(1-1)^{d}=0,$

where in the second line $l$ is the cardinal of the $a_{j}$’s equal to $-1$.

We now define $P^{*}$. To this end, we set for $(a_{1},\dots,a_{d})\in
\\{-1,0,1\\}^{d}$:

$h_{a_{1},\dots,a_{d}}:=\frac{\delta}{2}\frac{1}{2^{d}}\prod_{j=1}^{d}a_{j},\quad
p^{*}_{a_{1},\dots,a_{d}}=p_{a_{1},\dots,a_{d}}+h_{a_{1},\dots,a_{d}}.$

Remark that these coefficients $p^{*}$ are those of a probability and it
allows us to define $P^{*}$ by
$P^{*}(X^{1}=a_{1}\delta^{-1/k_{1}},\dots,X^{d}=a_{d}\delta^{-1/k_{1}})=p^{*}_{a_{1},\dots,a_{d}}$.
Also, we have for all $j\in\\{1,\dots,d\\}$,
$(a_{1},\dots,a_{j-1},a_{j+1},\dots,a_{d})\in\\{-1,0,1\\}^{d-1}$ that,
$\displaystyle\sum_{b\in\\{-1,0,1\\}}h(a_{1},\dots,a_{j-1},b,a_{j+1},\dots,a_{d})=0$.
This implies that

$\sum_{b\in\\{-1,0,1\\}}p(a_{1},\dots,a_{j-1},b,a_{j+1},\dots,a_{d})=\sum_{b\in\\{-1,0,1\\}}p^{*}(a_{1},\dots,a_{j-1},b,a_{j+1},\dots,a_{d}),$

and in turn the law of $(X^{1},\dots,X^{j-1},X^{j+1},\dots,X^{d})$ is the same
under $P$ and $P^{*}$. This property is crucial to allow the application of
Corollaries 3.4 or 3.8. It also yields that for any $l\in\\{1,\dots,d\\}$, we
have $\mathbb{E}_{P^{*}}[|X^{l}|^{k_{l}}]=\mathbb{E}_{P}[|X^{l}|^{k_{l}}]=1$
and thus, $P^{*}\in\mathcal{P}_{k_{1},\dots,k_{d}}$. Moreover,

$\displaystyle\gamma(P^{*})$
$\displaystyle=\mathbb{E}_{P^{*}}\left[X^{1}\times\dots\times
X^{d}\right]=\mathbb{E}_{P}\left[X^{1}\times\dots\times
X^{d}\right]+\frac{\delta}{2}\sum_{(a_{1},\dots,a_{d})\in
\\{-1,1\\}^{d}}\left(\frac{1}{2}\right)^{d}\prod_{j=1}^{d}\prod_{j=1}^{d}(a_{j}\delta^{k_{j}})$
$\displaystyle=0+\frac{1}{2}\delta^{1-\sum_{j=1}^{d}\frac{1}{k_{j}}}\left(\frac{1}{2}\right)^{d}\sum_{(a_{1},\dots,a_{d})\in
\\{-1,1\\}^{d}}(\prod_{j=1}^{d}a_{j})^{2}$
$\displaystyle=\frac{1}{2}\delta^{1-\sum_{j=1}^{d}\frac{1}{k_{j}}}\left(\frac{1}{2}\right)^{d}\sum_{(a_{1},\dots,a_{d})\in
\\{-1,1\\}^{d}}1=\frac{1}{2}\delta^{1-\sum_{j=1}^{d}\frac{1}{k_{j}}}.$

As a result, we have
$\lvert\gamma(P)-\gamma(P^{*})\rvert=\frac{1}{2}\delta^{1-\sum_{j=1}^{d}\frac{1}{k_{j}}}$.

We apply Corollary 3.8 to the sequences of raw samples
$(\bm{X}_{i})_{i=1,\dots,n}$, $(\bm{X}_{i}^{*})_{i=1,\dots,n}$ whose
distributions are $P^{\otimes n}$ and $(P^{*})^{\otimes n}$. Indeed, this is
permitted as the $(d-1)-$dimensional marginal laws of the $d-$dimensional
vectors $\bm{X}_{i}$ and $\bm{X}_{i}^{*}$ coincide. We deduce

$d_{KL}\Big{(}Law((\bm{Z}_{i})_{i=1,\dots,n}),Law((\bm{Z}^{*}_{i})_{i=1,\dots,n})\Big{)}\leq
n\times{\color[rgb]{0,0,0}\prod_{j=1}^{d}|e^{\alpha_{j}}-1|^{2}\times
d_{TV}(P,P^{*})^{2}}$

Furthermore,

$\displaystyle d_{TV}(P,P^{*})$
$\displaystyle=\sum_{(a_{1},\dots,a_{d})\in\\{-1,0,1\\}^{d}}|p_{a_{1},\dots,a_{d}}-p^{*}_{a_{1},\dots,a_{d}}|=\sum_{(a_{1},\dots,a_{d})\in\\{-1,0,1\\}^{d}}|h(a_{1},\dots,a_{d})|$
$\displaystyle\leq\sum_{(a_{1},\dots,a_{d})\in\\{-1,0,1\\}^{d}}\frac{\delta}{2}\frac{1}{2^{d}}\lvert\prod_{j=1}^{d}a_{j}\rvert\leq\frac{\delta}{2}\frac{1}{2^{d}}\sum_{(a_{1},\dots,a_{d})\in\\{-1,1\\}^{d}}1\leq\frac{\delta}{2},$

and so we get

$d_{KL}\Big{(}Law((\bm{Z}_{i})_{i=1,\dots,n}),Law((\bm{Z}^{*}_{i})_{i=1,\dots,n})\Big{)}\leq
n{\color[rgb]{0,0,0}\times\prod_{j=1}^{d}|e^{\alpha_{j}}-1|^{2}\times\frac{\delta^{2}}{4}.}$

We now set
$\delta=\left(2\prod_{j=1}^{d}|e^{\alpha_{j}}-1|^{2}n\right)^{-1/2}$ which is
strictly smaller than $1$ by the assumption
$n\prod_{j=1}^{d}|e^{\alpha_{j}}-1|^{2}\geq 1$.  Then, we get,
$d_{KL}\Big{(}Law((\bm{Z}_{i})_{i=1,\dots,n}),Law((\bm{Z}^{*}_{i})_{i=1,\dots,n})\Big{)}{\color[rgb]{0,0,0}\leq
1/8<2}$. Moreover,

$\lvert\gamma(P)-\gamma(P^{*})\rvert=\frac{1}{2}\delta^{1-\sum_{j=1}^{d}\frac{1}{k_{j}}}=\frac{1}{2}\delta^{1-d/\overline{k}}=\frac{1}{2^{3/2}}\Big{(}n\prod_{j=1}^{d}\lvert
e^{\alpha_{j}}-1\rvert^{2}\Big{)}^{-(\frac{1}{2}-\frac{d}{2\overline{k}})}\\\
=\frac{1}{2^{3/2}}\Big{(}n\prod_{j=1}^{d}\lvert
e^{\alpha_{j}}-1\rvert^{2}\Big{)}^{-\frac{\overline{k}-d}{2\overline{k}}}.$

We have obtained the Points 1–3 stated at the beginning of the proof and the
lower bound on
$\mathcal{M}_{n}(\gamma(\mathcal{P}_{k_{1},\dots,k_{d}}),\bm{\alpha})$
follows. ∎

######  Remark 4.13.

For simplicity, we restrict the discussion on non-interactive mechanisms.
However, the Corollary 3.8 is true for interactive and non-interactive
mechanism. Thus, the lower bound holds true for interactive mechanism as well.
As the statistical procedure described in 4.2.1 is non-interactive, it means
that in the statistical problem of moment estimation, non-interactive
mechanism are rate efficient. However, optimality of non interactive
mechanisms is problem specific as shown in [4].

####  4.2.4 Adpative estimation of the joint moment

As discussed in Section 4.2.1, the privacy procedure proposed in this study
requires selecting the optimal truncation levels $T^{(j)}$’s, which depend on
the number of finite moments $k_{j}$’s for the variables. However, in
practice, it is unrealistic to assume that the number of finite moments is
known in all situations. To address this issue, we propose an adaptive method
to estimate the covariance that does not necessitate prior knowledge of the
$k_{j}$’s and conforms to the privacy constraint.

The main idea is to send a collection of public data with different truncation
levels via the privatization channel, and then let the statistician decide on
the optimal truncation level using a penalization method.

We introduce the following set of truncations :

$\displaystyle\mathcal{T}:={\color[rgb]{0,0,0}\prod_{j=1}^{d}\mathcal{T}^{(j)}},\text{where
for {\color[rgb]{0,0,0}$j\in\\{1,\dots,d\\}$}}$
$\displaystyle\mathcal{T}^{(j)}:=\left\\{T^{(j)}\in(0,\infty)\mid
T^{(j)}=\frac{n}{2^{r}},\quad\text{ for some
$r\in\\{1,\dots,\lfloor\log_{2}(n)\rfloor\\}$}\right\\}.$ (4.11)

Let $\beta_{n}^{j}>0$, for $j=1,\dots,d$ be $d$ parameters that we will
specify later. For all $i\in\\{1,\dots,n\\}$ we are given
$\sum_{j=1}^{d}\mathop{card}(\mathcal{T}^{(j)})=d\lfloor\log_{2}(n)\rfloor$
independent variables, $\mathcal{E}^{j,T^{(j)}}_{i}$ where $T^{(j)}$ ranges in
$\mathcal{T}^{(j)}$ and $j$ in $\\{1,\dots,d\\}$. We assume that each of the
variables $\mathcal{E}^{j,T^{(j)}}_{i}$ follows a Laplace distribution with
parameter $2\frac{T^{(j)}}{\beta_{n}^{j}}$, where
$T^{(j)}\in\mathcal{T}^{(j)}$ and $j$ takes values in $\\{1,\dots,d\\}$. We
further assume that these variables are independent for different values of
$i$ ranging from 1 to $n$.

We define the privatized data
$\bm{Z}_{i}=(Z_{i}^{1},\dots,Z_{i}^{d})\in\mathbb{R}^{\mathcal{T}^{(1)}}\times\dots\times\mathbb{R}^{\mathcal{T}^{(d)}}$,
$i\in\\{1,\dots,n\\}$, by

$\displaystyle Z^{1}_{i}$
$\displaystyle=(Z^{1,T}_{i})_{T\in\mathcal{T}^{(1)}},$ $\displaystyle
Z^{1,T}_{i}$
$\displaystyle=\left[X_{i}^{1}\right]_{T}+\mathcal{E}^{(1),T}_{i},$
$\displaystyle\quad\text{for $T\in\mathcal{T}^{(1)}$, $i\in\\{1,\dots,n\\}$},$
(4.12) $\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \vdots$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \textasciiacute\vdots$
$\displaystyle\quad\quad\vdots$ $\displaystyle Z^{d}_{i}$
$\displaystyle=(Z^{d,T}_{i})_{T\in\mathcal{T}^{(d)}},$ $\displaystyle
Z^{d,T}_{i}$
$\displaystyle=\left[X_{i}^{d}\right]_{T}+\mathcal{E}^{(d),T}_{i},$
$\displaystyle\quad\text{for $T\in\mathcal{T}^{(d)}$, $i\in\\{1,\dots,n\\}$}.$

Let us stress that on contrary to the privacy channel defined by (4.6), where
each data $X_{i}^{j}$ is publicly released using a one dimensional noisy view,
here each data $X_{i}^{j}$ is disclosed through a repetition of
$\mathop{card}(\mathcal{T}^{j})$ noisy views, where
$\mathop{card}(\mathcal{T}^{j})$ will grow to infinity. This tends to reduce
the privacy of the channel as all these public views contain information on
the same private value. To guarantee that this procedure is compatible with
the $\bm{\alpha}$-CLDP constraint, we need that the noise injected in the
channel growths with the dimension of the public view.

######  Lemma 4.14.

Assume that
$\beta_{n}^{j}=\frac{{\color[rgb]{0,0,0}\alpha_{j}}}{\mathop{card}(\mathcal{T}^{(j)})}=\frac{\alpha_{j}}{\lfloor\log_{2}(n)\rfloor}$.
Then, the privacy procedure satisfies the ${\bm{\alpha}}$-CLDP constraint as
in (2.4).

###### Proof.

For $j\in\\{1,\dots,d\\}$, let us denote by
$q^{j}((z^{j,T})_{T\in\mathcal{T}^{(j)}}\mid X^{j}=x)$ the density of the law
of $Z^{j}_{i}=(Z^{j,T}_{i})_{T\in\mathcal{T}^{(j)}}$ conditional to
$X^{j}_{i}=x\in\mathbb{R}$. Then, using the independence property of the
variables $(Z^{j,T}_{i})_{T\in\mathcal{T}^{(j)}}$, we have

$\displaystyle\frac{q^{j}((z^{j,T})_{T\in\mathcal{T}^{(j)}}\mid
X^{j}_{i}=x)}{q^{j}((z^{j,T})_{T\in\mathcal{T}^{(j)}}\mid
X^{j}_{i}=x^{\prime})}$
$\displaystyle=\frac{\prod_{T\in\mathcal{T}^{(j)}}\exp\left(\lvert
z^{j,T}-\left[x\right]_{T}\rvert\frac{\beta_{n}^{j}}{2T}\right)}{\prod_{T\in\mathcal{T}^{(j)}}\exp\left(\lvert
z^{j,T}-\left[x^{\prime}\right]_{T}\rvert\frac{\beta_{n}^{j}}{2T}\right)}$
$\displaystyle=\prod_{T\in\mathcal{T}^{(j)}}\exp\left(\frac{\beta_{n}^{j}}{2T}\left\\{\lvert
z^{j,T}-\left[x\right]_{T}\rvert-\lvert
z^{j,T}-\left[x^{\prime}\right]_{T}\rvert\right\\}\right)$
$\displaystyle\leq\prod_{T\in\mathcal{T}^{(j)}}\exp\left(\frac{\beta_{n}^{j}}{2T}\left\lvert\left[x\right]_{T}-\left[x^{\prime}\right]_{T}\right\rvert\right)$

where we used the inverse triangular inequality in the last line. As
$\left\lvert\left[x\right]_{T}-\left[x^{\prime}\right]_{T}\right\rvert\leq 2T$
we deduce,

$\frac{q^{j}((z^{j,T})_{T\in\mathcal{T}^{(j)}}\mid
X^{j}_{i}=x)}{q^{j}((z^{j,T})_{T\in\mathcal{T}^{(j)}}\mid
X^{j}_{i}=x^{\prime})}\leq\prod_{T\in\mathcal{T}^{(j)}}\exp\left(\beta_{n}^{j}\right)=\exp(\mathop{card}(\mathcal{T}^{(j)})\beta_{n}^{j})\leq\exp(\alpha_{j}),$

by the choice of $\beta_{n}^{j}$. ∎

We construct our adaptive estimator, following Goldenshluger-Lepski method.
For $\bm{T}=(T^{(1)},\dots,T^{(d)})\in\mathcal{T}$, we set

${\color[rgb]{0,0,0}\hat{\gamma}^{(\bm{T})}_{n}=\frac{1}{n}\sum_{i=1}^{n}\prod_{j=1}^{d}Z^{j,T^{(j)}}_{i},}$
(4.13)

and for ${\color[rgb]{0,0,0}\bm{T}=(T^{(1)},\dots,T^{(d)})}\in\mathcal{T}$,
${\color[rgb]{0,0,0}\bm{T}^{\prime}=(T^{\prime(1)},\dots,T^{\prime(d)})\in\mathcal{T}}$

$\hat{\gamma}^{(\bm{T},\bm{T}^{\prime})}_{n}=\frac{1}{n}\sum_{i=1}^{n}\prod_{j=1}^{d}Z^{j,T^{(j)}\wedge
T^{\prime(j)}}_{i}.$ (4.14)

Let us remark that the following commutativity relation hold true:
$\hat{\gamma}^{(\bm{T},\bm{T}^{\prime})}_{n}=\hat{\gamma}^{(\bm{T}^{\prime},\bm{T})}_{n}$.
Based on the upper bound (A.15) given in the Appendix for the variance of the
estimator, we introduce the penalization term for $\bm{T}\in\mathcal{T}$,

$\mathbb{V}_{\bm{T}}=\mathbb{V}_{(T^{(1)},\dots,T^{(d)})}=\kappa_{n}\frac{\prod_{j=1}^{d}\lvert
T^{(j)}\rvert^{2}}{n\prod_{j=1}^{d}\lvert\beta_{n}^{j}\rvert^{2}}$ (4.15)

for $\kappa_{n}\geq 1$ some sequence tending slowly to $\infty$, which will be
specified in Theorem 4.15.

For ${\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T}$, we define

$\mathbb{B}_{{\color[rgb]{0,0,0}\bm{T}}}=\sup_{{\color[rgb]{0,0,0}\bm{T}^{\prime}}\in\mathcal{T}}\left\\{\left(\left\lvert\hat{\gamma}^{{\color[rgb]{0,0,0}(\bm{T},\bm{T}^{\prime})}}_{n}-\hat{\gamma}^{{\color[rgb]{0,0,0}(\bm{T}^{\prime})}}_{n}\right\rvert^{2}-\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}^{\prime}}}\right)_{+}\right\\},$
(4.16)

and set

$\widehat{{\color[rgb]{0,0,0}\bm{T}}}=\underset{{\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T}}{\operatorname{arg}\\!\operatorname{min}}\;\left\\{\mathbb{B}_{\color[rgb]{0,0,0}\bm{T}}+\mathbb{V}_{\color[rgb]{0,0,0}\bm{T}}\right\\}.$
(4.17)

Our adaptive estimator is
$\hat{\gamma}_{n}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}})}$.

######  Theorem 4.15.

Assume that $k_{1}^{-1}+\dots+k_{d}^{-1}<1$,
$\beta_{n}^{j}=\frac{\alpha_{j}}{\lfloor\log_{2}(n)\rfloor}$, for
$j=1,\dots,d$ and $\kappa_{n}=c_{0}\log(n)$ for some $c_{0}>0$. If $c_{0}$ is
large enough, there exist $c>0$, $\overline{c}_{0}>0$, such that

$\mathbb{E}\left[(\hat{\gamma}^{\widehat{T}}_{n}-\gamma)^{2}\right]\leq
c\left(\frac{n{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha_{j}^{2}}}{(\log(n))^{{\color[rgb]{0,0,0}2d+1}}}\right)^{-\frac{\overline{k}-{\color[rgb]{0,0,0}d}}{\overline{k}}}+\frac{c}{{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha_{j}^{2}}n^{\overline{c}_{0}}},$

for all $n\geq 1$, $\alpha_{j}\leq 1$,
$(n\prod_{j=1}^{d}\alpha^{2}_{j})/(\log(n))^{2d+1}\geq 1$. Moreover, the
constant $\overline{c}_{0}$ can be chosen arbitrarily large by choosing
$c_{0}$ large enough.

######  Remark 4.16.

Comparing with Theorem 4.5, we observe that the rate of the adaptive version
of the estimator worsens by a factor of $\log(n)^{2d+1}$. The loss of a
$\log(n)$ factor is a well-known characteristic of adaptive methods and is
sometimes unavoidable, as mentioned in [10]. The additional loss of a
$\log(n)^{{\color[rgb]{0,0,0}2d}}$ term arises from the disclosure of
$\mathop{card}{\mathcal{T}^{(j)}}\asymp\log_{2}(n)$ observations for each raw
data, which increases the variance of the privatization mechanism while
maintaining a constant level of privacy, as demonstrated in Lemma 4.14. This
is one reason why, in defining the sets $\mathcal{T}^{(j)}$, we have attempted
to minimize their cardinality.

The proof of the adaptive procedure gathered in Theorem 4.15 can be found in
the Appendix.

###  4.3 Locally private multivariate density estimation

In this section we consider the non-parametric estimation of the density of
the vector $\bm{X}=(X^{1},\dots,X^{d})$, under $\alpha$-CLDP. We will see
that, similarly to the case where the components become public jointly, this
implies a deterioration on the convergence rate depending on $\bm{\alpha}$
(see for example Section 5.2.2 of [19]).
Consider $\bm{X}_{1},\dots,\bm{X}_{n}$, $n$ iid copies of $\bm{X}$. We will
assume that the density $\pi$ of $\bm{X}$ belongs to an Hölder class
$\mathcal{H}(\beta,\mathcal{L})$ (see for example Definition 1.2 in [39]). We
aim at estimating such density under componentwise local differential privacy.
We recall we reduce to consider the non-interactive privacy mechanism for the
statistical applications, in order to lighten the notation.

####  4.3.1 Local differential private estimator

In absence of privacy constraints, a well-studied estimator for density
estimation consists in the kernel density estimator (see for example Section
1.2 of [39] and Part III of [8]). It achieves the convergence rate
$n^{-\frac{2\beta}{2\beta+d}}$, which has been shown to be optimal in a
minimax sense (see Theorem 1.1 in [39] for the monodimensional case).
We therefore introduce some kernel function
$K:\mathbb{R}\rightarrow\mathbb{R}$ satisfying, for all
$l\in\left\\{1,\dots,\beta\right\\}$,

${}\int_{\mathbb{R}}K(x)dx=1,\quad\left\|K\right\|_{\infty}<\kappa,\quad\mbox{supp}(K)\subset[-1,1],\quad\int_{\mathbb{R}}K(x)x^{l}dx=0.$
(4.18)

Then, as for the estimation of the covariance, we add centered Laplace
distributed noise on bounded random variables to obtain $\alpha$-CLDP.

######  Lemma 4.17.

For any $i\in\\{1,\dots,n\\}$, $j\in\\{1,\dots,d\\}$ and any
$\bm{x_{0}}\in\mathbb{R}^{d}$, the random variables

${}Z_{i}^{j}:=\frac{1}{h}K(\frac{X_{i}^{j}-x_{0}^{j}}{h})+\mathcal{E}_{i}^{j},$
(4.19)

with $\mathcal{E}_{i}^{j}$ iid $\sim\mathcal{L}(\frac{2\kappa}{\alpha_{j}h})$,
are $\alpha_{j}$-differentially private views of the original $X_{i}^{j}$.

The index $h$ introduced in (4.19) is small. In particular, we assume $h<1$.
The proof of Lemma 4.17 consists in checking property (2.4), similarly as in
Lemma 4.3. The proof of the lemma is rather close to the proof of Lemma 2.2
and the detailed proof is left to the Appendix. We introduce the kernel
density estimator $\hat{\pi}^{Z}_{h}$ based on the discrete observations
$Z_{i}^{j}$, for $i\in\\{1,\dots,n\\}$ and $j\in\\{1,\dots,d\\}$. We define,
for any $\bm{x_{0}}\in\mathbb{R}^{d}$,

${}\hat{\pi}^{Z}_{h}(\bm{x_{0}}):=\frac{1}{n}\sum_{i=1}^{n}\prod_{j=1}^{d}Z_{i}^{j}=\frac{1}{n}\sum_{i=1}^{n}\prod_{j=1}^{d}\Big{(}\frac{1}{h}K(\frac{X_{i}^{j}-x_{0}^{j}}{h})+\mathcal{E}_{i}^{j}\Big{)}.$
(4.20)

We now prove an upper bound the $L^{2}$ pointwise risk, showing that
$\hat{\pi}^{Z}_{h}$ achieves the convergence rate
$(\frac{1}{n\prod_{j=1}^{d}\alpha_{j}^{2}})^{\frac{\beta}{\beta+d}}$.

######  Theorem 4.18.

Assume $\bm{X}_{1},\dots,\bm{X}_{n}$ are iid copies of an $\mathbb{R}^{d}$
vector $\bm{X}$ whose density $\pi$ belongs to the Hölder class
$\mathcal{H}(\beta,\mathcal{L})$ and $\bm{x_{0}}\in\mathbb{R}^{d}$. Let
$0<\alpha_{j}\leq 1$ for any $j\in\\{1,\dots,d\\}$.  If
$n\prod_{j=1}^{d}\alpha_{j}^{2}\rightarrow\infty$, then there exist $c>0$ and
$n_{0}>0$ such that for any $n\geq n_{0}$,

$\mathbb{E}[|\hat{\pi}^{Z}_{h}(\bm{x_{0}})-\pi(\bm{x_{0}})|^{2}]\leq
c(\frac{1}{n\prod_{j=1}^{d}\alpha_{j}^{2}})^{\frac{\beta}{\beta+d}}.$

This shows that the effects of local differential privacy constraints are
severe for non-parametric density estimation, as they lead to a different
convergence rate.

In the case where $\alpha_{1}=\dots=\alpha_{d}$ it is possible to obtain the
following result, which provides the threshold which dictates the behaviour of
the estimator with respect to the privacy mechanism. Indeed, for $\alpha\geq
n^{\frac{1}{2(2\beta+d)}}$, we recover the same convergence rate as in absence
of privacy.

######  Theorem 4.19.

Assume $\bm{X}_{1},\dots,\bm{X}_{n}$ are iid copies of an $\mathbb{R}^{d}$
vector $\bm{X}$ whose density $\pi$ belongs to the Hölder class
$\mathcal{H}(\beta,\mathcal{L})$, and $\bm{x_{0}}\in\mathbb{R}^{d}$. Then, the
following inequalities hold true

  1. 1.

If $\alpha\geq n^{\frac{1}{2(2\beta+d)}}$, then there exist $c>0$ and
$n_{0}>0$ such that, for any $n\geq n_{0}$,

$\mathbb{E}[|\hat{\pi}^{Z}_{h}(\bm{x_{0}})-\pi(\bm{x_{0}})|^{2}]\leq
c(\frac{1}{n})^{\frac{2\beta}{2\beta+d}}.$

  2. 2.

If otherwise $\alpha<n^{\frac{1}{2(2\beta+d)}}$ and
$n\alpha^{2d}\rightarrow\infty$, then there exist $c>0$ and $n_{0}>0$ such
that, for any $n\geq n_{0}$,

$\mathbb{E}[|\hat{\pi}^{Z}_{h}(\bm{x_{0}})-\pi(\bm{x_{0}})|^{2}]\leq
c(\frac{1}{n\alpha^{2d}})^{\frac{\beta}{\beta+d}}.$

The proof of these two results can be found in Section A.4 of the Appendix.

######  Remark 4.20.

The above result indicates that a threshold for the behavior of a system with
and without privacy is determined by $n^{\frac{1}{2(2\beta+d)}}$. If $\alpha$
is greater than this value, it means that the level of privacy provided is not
significant enough to degrade the convergence rate of our estimator compared
to the case without privacy. However, if $\alpha$ is smaller than
$n^{\frac{1}{2(2\beta+d)}}$, then the level of privacy provided is sufficient
to reduce the statistical utility, leading to a deterioration of the
convergence rate as a function of $\alpha$. It is essential to note that it is
impossible to achieve perfect privacy even in this context ($\alpha=0$). The
condition that $n\alpha^{2d}\rightarrow\infty$ must indeed be satisfied, which
is the price to pay for allowing statistical inference.

####  4.3.2 Lower bound for density estimation

We can now derive minimax lower bound, based on the key result gathered in
Theorem 3.3 and its consequences.

######  Theorem 4.21.

Let $\alpha_{j}\in(0,\infty)$ for $j\in\\{1,\dots,d\\}$ and let
$\beta,\mathcal{L}>0$. Then, there exists a constant $c>0$ such that

$\inf_{\bm{Q}\in\mathcal{Q}_{\bm{\alpha}}}\inf_{\tilde{\pi}}\sup_{\pi\in\mathcal{H}(\beta,\mathcal{L})}\mathbb{E}[|\tilde{\pi}(\bm{x_{0}})-\pi(\bm{x_{0}})|^{2}]\geq
c\Big{(}n\,\prod_{j=1}^{d}(e^{\alpha_{j}}-1)^{2}\Big{)}^{-\frac{\beta}{\beta+d}},$

for all $n\geq 1$, $n\prod_{j=1}^{d}|e^{\alpha_{j}}-1|\rightarrow\infty$. The
infimum is taken over all the estimators $\tilde{\pi}$ based on the privatized
vectors $\bm{Z}_{1},\dots,\bm{Z}_{n}$ and all the non-interactive Markov
kernels in $\mathcal{Q}_{\bm{\alpha}}$ guaranteeing ${\bm{\alpha}}$-CLDP.

######  Remark 4.22.

When the privacy parameters $\alpha_{j}$ are small, it is clear that the upper
and lower bounds in Theorems 4.18 and 4.21 match each other. This suggests
that the proposed privacy mechanism is optimal (in the minimax sense) as long
as a reasonable amount of privacy is ensured for all the components (i.e.,
$\alpha_{j}<1$ for any $j\in\\{1,\dots,d\\}$).

######  Remark 4.23.

One can compare the deterioration of the convergence rate gathered in our
Theorem 4.21 (and the corresponding upper bound in Theorem 4.19) with the
results in [11], which focuses on estimating the density under privacy
constraints using $n$ independent and identically distributed random variables
$X_{1},\dots,X_{n}$. Their analysis on Besov spaces $\mathcal{B}_{pq}^{s}$
under mean integrated $L^{r}$-risk revealed an elbow effect that led to the
optimal (in the minimax sense) convergence rate of
$(n(e^{\alpha}-1)^{2})^{-\frac{rs}{2s+2}}$ whenever $p>\frac{r}{s+1}$ (see
Equation (1.2) in [11]). Using our notation, this rate corresponds to
$(n(e^{\alpha}-1)^{2})^{-\frac{2\beta}{2\beta+2}}=(n(e^{\alpha}-1)^{2})^{-\frac{\beta}{\beta+1}}$
and the condition on $p$ reduces to $2>\frac{2}{\beta+1}$, which is always
true. Therefore, it is evident that our results match those of [11] when
considering $d=1$, but they are in general different as in the case where
$\alpha_{1}=\dots=\alpha_{d}=\alpha$ the size $(e^{\alpha}-1)^{2}$ in [11] is
now replaced by $(e^{\alpha}-1)^{2d}$.

###### Proof of Theorem 4.21.

We can assume without loss of generality that $\bm{x_{0}}=\bm{0}$, the general
case can be deduced by translation.
The proof of the lower bound relies on the two hypothesis method, as in
Section 2.3 of [39]. It consists in proposing $\pi$ and $\pi^{*}$, densities
of $\bm{X}$ and $\bm{X}^{*}$ and with privatized views $\bm{Z}$ and
$\bm{Z}^{*}$, such that the following three conditions hold true:

  1. 1.

$\pi$ and $\pi^{*}$ belong to $\mathcal{H}(\beta,\mathcal{L})$,

  2. 2.

$|\pi(\bm{0})-\pi^{*}(\bm{0})|\geq\frac{1}{M_{n}}$,

  3. 3.

$\exists c>0$ such that
$d_{KL}\Big{(}Law((\bm{Z}_{i})_{i=1,\dots,n}),Law((\bm{Z}^{*}_{i})_{i=1,\dots,n})\Big{)}<\epsilon_{0}<2$,

where $\frac{1}{M_{n}}$ is a calibration parameter which will be chosen later,
in order to obtain the wanted convergence rate. If the constraints above are
satisfied, then in the same way as in the proof of Theorem 4.11 it follows
there exists $c>0$ such that

${}\inf_{Q\in\mathcal{Q}_{\bm{\alpha}}}\inf_{\tilde{\pi}}\sup_{\pi\in\mathcal{H}(\beta,\mathcal{L})}\mathbb{E}[|\tilde{\pi}(\bm{0})-\pi(\bm{0})|^{2}]\geq
c(\frac{1}{M_{n}})^{2}.$ (4.21)

Let us define, for any $\bm{x}\in\mathbb{R}^{d}$,
$\pi(\bm{x}):=c_{\pi}e^{-\eta|x|^{2}}.$ The constant $\eta$ can be chosen as
small as we want, while $c_{\pi}$ is a normalization constant added in order
to get $\int_{\mathbb{R}^{d}}\pi(\bm{x})d\bm{x}=1$. Regarding $\pi^{*}$, we
give it as $\pi$ to which we add a bump. Let
$\tilde{\psi}:\mathbb{R}\rightarrow\mathbb{R}$ be a $C^{\infty}$ function with
support on $[-1,1]$ and such that $\tilde{\psi}(0)=1$,
$\int_{-1}^{1}\tilde{\psi}(z)dz=0.$ Then, we set
$\pi^{*}(\bm{x}):=\pi(\bm{x})+\frac{1}{M_{n}}\prod_{l=1}^{d}\tilde{\psi}(\frac{x^{l}}{h_{n}})=:\pi(\bm{x})+\frac{1}{M_{n}}\psi_{h_{n}}(\bm{x}).$
As $\frac{1}{M_{n}}$, $h_{n}$ will be calibrated later. The two calibration
constants satisfy $M_{n}\rightarrow\infty$ for $n\rightarrow\infty$ and
$h_{n}\rightarrow 0$ for $n\rightarrow\infty$.

It is easy to check Condition 1 holds true. Indeed, we can choose $\eta$ small
enough to obtain $\pi\in\mathcal{H}(\beta,\mathcal{L})$ and a similar
reasoning ensures also that $\pi^{*}\in\mathcal{H}(\beta,\mathcal{L})$.
However, $\left\|\psi_{h_{n}}^{(k)}\right\|_{\infty}\leq\frac{c}{h_{n}^{k}}$
and so in the k-derivative of $\pi^{*}$ an extra $\frac{1}{M_{n}h_{n}^{k}}$
appears. It implies we have to ask the existence of some constant $c>0$ such
that $\frac{1}{M_{n}h_{n}^{k}}<c$ for any
$k\in\\{0,\dots,\lfloor\beta\rfloor\\}$, in order to obtain
$\pi^{*}\in\mathcal{H}(\beta,\mathcal{L})$. Thus, for some $c>0$ it naturally
arises the condition $\frac{1}{M_{n}h_{n}^{\beta}}<c.$
Concerning Condition 2, by construction and from the properties of the
function $\tilde{\psi}$ it is

$|\pi(\bm{0})-\pi^{*}(\bm{0})|=|\frac{1}{M_{n}}\psi_{h_{n}}(\bm{0})|=\frac{1}{M_{n}}\prod_{l=1}^{d}|\tilde{\psi}(0)|=\frac{1}{M_{n}}.$

We are left to prove Condition 3. We observe that, for any
$k\in\\{1,\dots,d-1\\}$, it is
$Law(X^{i_{1}},\dots,X^{i_{k}})=Law(X^{*,i_{1}},\dots,X^{*,i_{k}})$. Indeed,
the law of $(X^{*,i_{1}},\dots,X^{*,i_{k}})$ is given by

$\displaystyle\int_{\mathbb{R}^{d-k}}\Big{(}\pi(x^{1},\dots,x^{d})+\frac{1}{M_{n}}\psi_{h_{n}}(x^{1},\dots,x^{d})\Big{)}\prod_{j:\,j\notin\\{i_{1},\dots,i_{k}\\}}dx^{j}$
$\displaystyle=\int_{\mathbb{R}^{d-k}}\pi(x^{1},\dots,x^{d})\prod_{j:\,j\notin\\{i_{1},\dots,i_{k}\\}}dx^{j}+\frac{1}{M_{n}}\int_{\mathbb{R}^{d-k}}\prod_{l=1}^{d}\tilde{\psi}(\frac{x^{l}}{h_{n}})\prod_{j:\,j\notin\\{i_{1},\dots,i_{k}\\}}dx^{j}$
$\displaystyle=\int_{\mathbb{R}^{d-k}}\pi(x^{1},\dots,x^{d})\prod_{j:\,j\notin\\{i_{1},\dots,i_{k}\\}}dx^{j}=Law(X^{i_{1}},\dots,X^{i_{k}}),$

where we have used that the integrals of $\tilde{\psi}$ are $0$ by
construction.
Thus, we can use Corollary 3.8. It yields

${}d_{KL}\Big{(}Law((\bm{Z}_{i})_{i=1,\dots,n}),Law((\bm{Z}^{*}_{i})_{i=1,\dots,n})\Big{)}\leq{\color[rgb]{0,0,0}n\times}\prod_{j=1}^{d}|e^{\alpha_{j}}-1|^{2}\Big{(}d_{TV}(Law(\bm{X}),Law(\bm{X}^{*}))\Big{)}^{2}.$
(4.22)

To conclude, we observe it is

$\displaystyle{}\Big{(}d_{TV}(Law(\bm{X}),Law(\bm{X}^{*}))\Big{)}^{2}$
$\displaystyle\leq\Big{(}\int_{\mathbb{R}^{d}}\frac{1}{M_{n}}\psi_{h_{n}}(x^{1},\dots,x^{d})dx^{1},\dots,dx^{d}\Big{)}^{2}\leq
c\frac{h_{n}^{2d}}{M_{n}^{2}}.$ (4.23)

From (4.22) and (4.23) we get there exists some constant $c_{k}>0$ such that

$d_{KL}\Big{(}Law((\bm{Z}_{i})_{i=1,\dots,n}),Law((\bm{Z}^{*}_{i})_{i=1,\dots,n})\Big{)}\leq
c_{k}n\prod_{j=1}^{d}|e^{\alpha_{j}}-1|^{2}\frac{h_{n}^{2d}}{M_{n}^{2}}.$

Hence, Condition 3 holds true up to say that
$c_{k}n\prod_{j=1}^{d}|e^{\alpha_{j}}-1|^{2}\frac{h_{n}^{2d}}{M_{n}^{2}}$ is
bounded by some $\epsilon_{0}<2$.
The constraint given by Condition 1 leads us to the choice
$h_{n}=(\frac{1}{M_{n}})^{\frac{1}{\beta}}$, which entails
$c_{k}n\prod_{j=1}^{d}|e^{\alpha_{j}}-1|^{2}\Big{(}\frac{1}{M_{n}}\Big{)}^{\frac{2d}{\beta}+2}<\epsilon_{0}$.
It holds true if and only if
$\Big{(}\frac{1}{M_{n}}\Big{)}^{\frac{2d+2\beta}{\beta}}<\frac{\epsilon_{0}}{c_{k}n\prod_{j=1}^{d}|e^{\alpha_{j}}-1|^{2}}.$
We therefore choose
$\frac{1}{M_{n}}=\Big{(}\frac{\epsilon_{0}}{c_{k}n\prod_{j=1}^{d}|e^{\alpha_{j}}-1|^{2}}\Big{)}^{\frac{\beta}{2(d+\beta)}}.$
Equation (4.21) concludes then the proof.

∎

####  4.3.3 Adaptive density estimation

As seen in previous subsection, the proposed procedure leads us to the choice
of a bandwidth which depends on the regularity $\beta$, that is in general
unknown. This motivates a data-driven procedure for the choice of $h$.
We introduce the set of candidate bandwidths

${}H_{n}:=\left\\{h\in(0,1]:\,\mbox{ such that
}\frac{1}{h}=\frac{n}{2^{r}}\mbox{ for some
}r\in\\{1,\dots,\lfloor\log_{2}(n)\rfloor\\}\right\\}.$ (4.24)

In a similar way as in Section 4.2.4 we introduce, for $j\in\\{1,\dots,d\\}$,
some parameters $\beta_{n}^{j}>0$ that will be better specified later. For any
$i\in\\{1,\dots,n\\}$ and $j\in\\{1,\dots,d\\}$ the independent variables
$\mathcal{E}_{i}^{j,h}$ are distributed as Laplace random variables with law
$\mathcal{L}(\frac{2\kappa}{h\beta_{n}^{j}})$ for all $h\in H_{n}$, where
$\kappa$ is defined in (4.18). We therefore define the privatized data
$\bm{Z}_{i}=(Z_{i}^{1},\dots,Z_{i}^{d})\in\mathbb{R}^{H_{n}}\times\dots\times\mathbb{R}^{H_{n}}$
by $Z_{i}^{j}=(Z_{i}^{j,h})_{h\in H_{n}}$;

${}Z_{i}^{j,h}:=\frac{1}{h}K(\frac{X_{i}^{j}-x_{0}^{j}}{h})+\mathcal{E}_{i}^{j,h}$
(4.25)

for $h\in H_{n}$, $i\in\\{1,\dots,n\\}$ and $j\in\\{1,\dots,d\\}$. The set of
potential estimators is defined accordingly:

$\mathcal{F}(H_{n}):=\left\\{\hat{\pi}^{z}_{h}(\bm{x_{0}})=\frac{1}{n}\sum_{i=1}^{n}\prod_{j=1}^{d}Z_{i}^{j,h}\quad
h\in H_{n}\right\\}.$

By following closely the proof of Lemma 4.17 it is easy to check the following
lemma, whose proof is in the Appendix.

######  Lemma 4.24.

Assume that $\beta_{n}^{j}=\frac{\alpha_{j}}{\lfloor\log_{2}n\rfloor}$ for any
$j\in\\{1,\dots,d\\}$. Then, the privatized variables described in (4.25) are
$\bm{\alpha}$-local differential private views of the original $X_{i}^{j}$.

As our adaptive procedure is based on Goldenshluger-Lepski method, we want to
introduce an auxiliary estimator. For any $h,\eta\in H_{n}$ we set

$\hat{\pi}_{h,\eta}^{z}(\bm{x_{0}}):=\hat{\pi}^{z}_{h\land\eta}(\bm{x_{0}})=\frac{1}{n}\sum_{i=1}^{n}\prod_{j=1}^{d}\frac{1}{h\land\eta}K(\frac{X_{i}^{j}-x_{0}^{j}}{h\land\eta})+\mathcal{E}_{i}^{j,h\land\eta}.$

Clearly it is
$\hat{\pi}_{h,\eta}^{z}(\bm{x_{0}})=\hat{\pi}_{\eta,h}^{z}(\bm{x_{0}})$. In
the proof of Theorem 4.18 given in the Appendix, we obtain the bound (A.34)
for the variance of the kernel estimator. This yield us to introduce the
penalization term
$\mathbb{V}_{h}:=a_{n}\frac{1}{nh^{2d}}\frac{1}{\prod_{j=1}^{d}(\beta_{n}^{j})^{2}},$
for $a_{n}\geq 1$ some sequence tending slowly to $\infty$, which will be
specified in Theorem 4.25 below. We also define, for any $h\in H_{n}$,
$\mathbb{B}_{h}:=\sup_{\eta\in
H_{n}}\left\\{(|\hat{\pi}_{h,\eta}^{z}(\bm{x_{0}})-\hat{\pi}_{\eta}^{z}(\bm{x_{0}})|^{2}-\mathbb{V}_{\eta})_{+}\right\\}.$
Heuristically, $\mathbb{V}_{h}$ plays the role of the variance while
$\mathbb{B}_{h}$ plays the role of the bias; the chosen bandwidth for the
adaptive procedure is the one that minimizes their sum, i.e.
$\hat{h}:=argmin_{h\in H_{n}}\\{\mathbb{B}_{h}+\mathbb{V}_{h}\\}.$ The
associated adaptive estimator is $\hat{\pi}_{\hat{h}}^{z}(\bm{x_{0}})$, for
which the following theorem holds true.

######  Theorem 4.25.

Assume that $\pi\in\mathcal{H}(\beta,\mathcal{L})$ for some $\beta$ and
$\mathcal{L}\geq 1$. Moreover,
$\beta_{n}^{j}=\frac{\alpha_{j}}{\lfloor\log_{2}n\rfloor}$ for any
$j\in\\{1,\dots,d\\}$ and $a_{n}={c_{0}}\log n$ for some ${c_{0}}>0$. If
$c_{0}$ is large enough, there exist $c>0$ and $\bar{c}>0$ such that

$\mathbb{E}[(\hat{\pi}_{\hat{h}}^{z}(\bm{x_{0}})-\pi(\bm{x_{0}}))^{2}]\leq
c(\frac{\log
n^{1+2d}}{n\prod_{j=1}^{d}\alpha_{j}^{2}})^{\frac{\beta}{\beta+d}}+\frac{c}{n^{\bar{c}}\prod_{j=1}^{d}\alpha_{j}^{2}}$

for all $n\geq 1$, $\alpha_{j}\leq 1$ and
$\frac{n\prod_{j=1}^{d}\alpha_{j}^{2}}{\log n^{1+2d}}\geq 1$. Moreover, the
constant $\bar{c}$ can be chosen arbitrarily large, taking the constant
$c_{0}$ large enough.

######  Remark 4.26.

Just as in the case of estimating the covariance, the adaptive version of the
density estimation algorithm has a slower convergence rate than the one
presented in Theorem 4.18, by a logarithmic factor.

The proof of the data-driven selection of the bandwidth as proposed in Theorem
4.25 can be found in the Appendix.

## References

  * [1] Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., & Zhang, L. (2016, October). Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security (pp. 308-318).
  * [2] Acharya, J., Sun, Z., & Zhang, H. (2021, July). Robust testing and estimation under manipulation attacks. In International Conference on Machine Learning (pp. 43-53). PMLR.
  * [3] Apple Differential Privacy Team. Learning with privacy at scale, 2017. Available at https: //machinelearning.apple.com/2017/12/06/learning-with-privacy-at-scale.html.
  * [4] Berrett, T., & Butucea, C. (2020). Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms. Advances in Neural Information Processing Systems, 33, 3164-3173.
  * [5] Berrett, T. B., Györfi, L., & Walk, H. (2021). Strongly universally consistent nonparametric regression and classification with privatized data.
  * [6] Berrett, T., & Yu, Y. (2021). Locally private online change point detection. Advances in Neural Information Processing Systems, 34, 3425-3437.
  * [7] Bie, A., Kamath, G., & Singhal, V. (2022). Private Estimation with Public Data. Advances in Neural Information Processing Systems, 35, 18653–18666,
  * [8] Bosq, D., & Blanke, D. (2008). Inference and prediction in large dimensions. John Wiley & Sons.
  * [9] Boucheron, S., Lugosi, G., & Massart, P. (2013). Concentration inequalities: A nonasymptotic theory of independence. Oxford university press.
  * [10] Brown, L. D., & Low, M. G. (1996). A constrained risk inequality with applications to nonparametric functional estimation. The annals of Statistics, 24(6), 2524-2535.
  * [11] Butucea, C., Dubois, A., Kroll, M., & Saumard, A. (2020). Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids.
  * [12] Butucea, C., Rohde, A., & Steinberger, L. (2020). Interactive versus non-interactive locally differentially private estimation: Two elbows for the quadratic functional. arXiv preprint arXiv:2003.04773.
  * [13] Ding, B., Kulkarni, J., & Yekhanin, S. (2017). Collecting telemetry data privately. Advances in Neural Information Processing Systems, 30.
  * [14] Donoho, D. L., & Liu, R. C. (1991). Geometrizing rates of convergence, II. The Annals of Statistics, 633-667.
  * [15] Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013, October). Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (pp. 429-438). IEEE.
  * [16] Duchi, J., & Rogers, R. (2019, June). Lower bounds for locally private estimation via communication complexity. In Conference on Learning Theory (pp. 1161-1191). PMLR.
  * [17] Duchi, J., Wainwright, M. J., & Jordan, M. I. (2013). Local privacy and minimax bounds: Sharp rates for probability estimation. Advances in Neural Information Processing Systems, 26.
  * [18] Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013). Local privacy, data processing inequalities, and statistical minimax rates. arXiv preprint arXiv:1302.3203.
  * [19] Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2018). Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521), 182-201.
  * [20] Duchi, John. C., Ruan, F., (2024) The right complexity measure in locally private estimation: It is not the Fisher information 52 The Annals of Statistics, 52(1), 1-51, https://doi.org/10.1214/22-AOS2227
  * [21] Dwork, C., & Nissim, K. (2004). Privacy-preserving datamining on vertically partitioned databases. In Advances in Cryptology–CRYPTO 2004: 24th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 2004. Proceedings 24 (pp. 528-544). Springer Berlin Heidelberg.
  * [22] Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006). Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3 (pp. 265-284). Springer Berlin Heidelberg.
  * [23] Dwork, C. (2008). Differential privacy: A survey of results. In Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Xi’an, China, April 25-29, 2008. Proceedings 5 (pp. 1-19). Springer Berlin Heidelberg.
  * [24] Erlingsson, U., Pihur, V., & Korolova, A. (2014, November). Rappor: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security (pp. 1054-1067).