# Phase transitions for support recovery under local differential privacy

Cristina Butucea Financial support from the French National Research Agency
(ANR) under the grant Labex Ecodec (ANR-11-LABEX-0047) CREST, ENSAE, Institut
Polytechnique de Paris, 5 avenue Henry Le Chatelier, F-91120 Palaiseau.
<EMAIL_ADDRESS>Amandine Dubois Corresponding author. Financial
support from GENES and from the French ANR grant ANR-18-EURE-0004 CREST,
ENSAI, Campus de Ker-Lann - Rue Blaise Pascal - BP 37203 - 35172 BRUZ cedex.
<EMAIL_ADDRESS><EMAIL_ADDRESS>Adrien Saumard Financial
support from the French ANR grant ANR-18-EURE-0004 CREST, ENSAI, Campus de
Ker-Lann - Rue Blaise Pascal - BP 37203 - 35172 BRUZ cedex.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We address the problem of variable selection in a high-dimensional but sparse
mean model, under the additional constraint that only privatised data are
available for inference. The original data are vectors with independent
entries having a symmetric, strongly log-concave distribution on $\mathbb{R}$.
For this purpose, we adopt a recent generalisation of classical minimax theory
to the framework of local $\alpha-$differential privacy. We provide lower and
upper bounds on the rate of convergence for the expected Hamming loss over
classes of at most $s$-sparse vectors whose non-zero coordinates are separated
from $0$ by a constant $a>0$. As corollaries, we derive necessary and
sufficient conditions (up to log factors) for exact recovery and for almost
full recovery. When we restrict our attention to non-interactive mechanisms
that act independently on each coordinate our lower bound shows that, contrary
to the non-private setting, both exact and almost full recovery are impossible
whatever the value of $a$ in the high-dimensional regime such that
$n\alpha^{2}/d^{2}\lesssim 1$. However, in the regime
$n\alpha^{2}/d^{2}\gg\log(d)$ we can exhibit a critical value $a^{*}$ (up to a
logarithmic factor) such that exact and almost full recovery are possible for
all $a\gg a^{*}$ and impossible for $a\leq a^{*}$. We show that these results
can be improved when allowing for all non-interactive (that act globally on
all coordinates) locally $\alpha-$differentially private mechanisms in the
sense that phase transitions occur at lower levels.

Keywords : Hamming loss, Local differential privacy, Minimax rates, Phase
transition, Support recovery, Variable selection, Strong log-concavity

MSC2020 : 62G05, 62G20

##  1 Introduction

We consider the problem of distributed support recovery of the sparse mean of
$n$ independent, identically distributed (i.i.d.) random vectors. Precisely,
for $i=1,\ldots,n$, the $i$th data holder observes a random vector
$X^{i}=(X^{i}_{j})_{j=1,\ldots,d}\in\mathbb{R}^{d}$ issued from a rescaled and
shifted vector $\xi^{i}$: $X^{i}=\theta+\sigma\xi^{i}$. The noise is supposed
to have independent coordinates $\xi^{i}_{j},\,j=1,...,d$ identically
distributed with a symmetric and strongly log-concave distribution of variance
1 (see Section 1.3 below for definition and details). Note that the standard
Gaussian distribution belongs to our model, but the symmetric and strongly
log-concave probability density functions form a large non-parametric class of
functions.

The mean vector $\theta$ is assumed to be $(s,a)$-sparse in the sense that
$\theta$ belongs to one of the following sets:

$\Theta_{d}^{+}(s,a)=\\{\theta\in\mathbb{R}^{d}:\text{there exists a set
}S\subseteq\\{1,\ldots,d\\}\text{ with at most }s\text{ elements }\\\ \text{
such that }\theta_{j}\geq a\text{ for all }j\in S,\text{ and
}\theta_{j}=0\text{ for all }j\notin S\\},$

or

$\Theta_{d}(s,a)=\\{\theta\in\mathbb{R}^{d}:\text{there exists a set
}S\subseteq\\{1,\ldots,d\\}\text{ with at most }s\text{ elements }\\\ \text{
such that }|\theta_{j}|\geq a\text{ for all }j\in S,\text{ and
}\theta_{j}=0\text{ for all }j\notin S\\}.$

###  1.1 Differential Privacy

Nowadays, a large amount of data, such as internet browsing history, social
media activity, location information from smartphones, or medical records, are
collected and stored. On the one hand, the analysis of these data can benefit
to individuals, companies, or communities such as the scientific one. For
instance, companies can use data to improve their products and services, or
health data can be used for medical research. On the other hand, people are
more and more concerned with the protection of their privacy and may be
reluctant to share their sensitive data. In this context, it seems essential
to be able to understand the tradeoffs between the statistical utility of the
collected data and the privacy of individuals from whom these data are
obtained. This requires a formal definition of privacy and differential
privacy has been adopted by researchers in the computer science, machine
learning, and statistics communities as a natural one.

Two kinds of differential privacy are discussed in the literature: central
differential privacy which has been introduced by Dwork et al. in [22], and
local differential privacy. We will focus in this paper on the second setting
but we briefly discuss the difference between central and local privacy. In
both settings, $n$ individuals want their privacy to be preserved while their
data, which will be denoted $X_{1},\ldots,X_{n}$, are used for statistical
analyses. In the central setting, the $n$ data-holders share confidence in a
common curator who has access to the original data $X_{1},\ldots,X_{n}$ and
use them to generate a private release $Z$. In a nutshell, central
differential privacy ensures that the probability of observing an output does
not change much when a single data point of the original database is modified.
We refer to [38] for the formal definition of differential privacy in the
central setting. In the local setting, data is privatized before it is shared
with a data collector : for all $i\in\llbracket 1,n\rrbracket$, $X_{i}$ is
transformed into a private data $Z_{i}$ directly on the $i$th individual’s
machine and the data collector or the statistician only have access to the
private sample $Z_{1},\ldots,Z_{n}$. However, some interaction between the
different data-holders is allowed. Formally, the privatized data
$Z_{1},\ldots,Z_{n}$ are obtained by successively applying suitable Markov
kernels : given $X_{i}=x_{i}$ and $Z_{1}=z_{1},\ldots,Z_{i-1}=z_{i-1}$, the
$i$-th dataholder draws

$Z_{i}\sim Q_{i}(\cdot\mid X_{i}=x_{i},Z_{1}=z_{1},\ldots,Z_{i-1}=z_{i-1})$

for some Markov kernel
$Q_{i}:\mathscr{Z}\times\mathcal{X}\times\mathcal{Z}^{i-1}\to[0,1]$ where the
measure spaces of the non-private and private data are denoted with
$(\mathcal{X},\mathscr{X})$ and $(\mathcal{Z},\mathscr{Z})$, respectively.
Such randomizations are known as sequentially interactive. We say that the
sequence of Markov kernels $(Q_{i})_{i=1,\ldots,n}$ provides $\alpha$-local
differential privacy or that $Z_{1},\ldots,Z_{n}$ are $\alpha$-local
differentially private views of $X_{1},\ldots,X_{n}$ if

$\sup_{A\in\mathscr{Z}}\frac{Q_{i}(A\mid
X_{i}=x,Z_{1}=z_{1},\ldots,Z_{i-1}=z_{i-1})}{Q_{i}(A\mid
X_{i}=x^{\prime},Z_{1}=z_{1},\ldots,Z_{i-1}=z_{i-1})}\leq\exp(\alpha)\quad\forall
i\in\llbracket 1,n\rrbracket,\,\forall x,x^{\prime}\in\mathcal{X}.$ (1)

In this paper, we will focus on the special case of non-interactive local
differential privacy where $Z_{i}$ depends only on $X_{i}$ but not on $Z_{k}$
for $k<i$. In this scenario, we have

$Z_{i}\sim Q_{i}(\cdot\mid X_{i}=x_{i}),$

and condition (1) becomes

$\sup_{A\in\mathscr{Z}}\frac{Q_{i}(A\mid X_{i}=x)}{Q_{i}(A\mid
X_{i}=x^{\prime})}\leq\exp(\alpha)\quad\forall i\in\llbracket
1,n\rrbracket,\,\forall x,x^{\prime}\in\mathcal{X}.$

The aim is that every data holder releases a private view $Z^{i}$ of $X^{i}$
such that the notion of local differential privacy is satisfied and that the
support of $\theta$ can be estimated from the data $Z^{1},\ldots,Z^{n}$ in an
optimal way.

Notation. For two sequences $\\{a_{d}\\}_{d}$ and $\\{b_{d}\\}_{d}$ of non-
negative real numbers, we write $a_{d}\lesssim b_{d}$ if there exists some
constant $C>0$ such that $a_{d}\leq Cb_{d}$. If $b_{d}>0$ we write $a_{d}\sim
b_{d}$ if $a_{d}/b_{d}\rightarrow 1$ as $d\rightarrow\infty$ and we write
$a_{d}\gg b_{d}$ if $a_{d}/b_{d}\rightarrow\infty$ as $d\rightarrow\infty$. We
recall that a centred Laplace distribution with parameter $\lambda>0$ has the
probability density function defined by
$f_{\lambda}(x)=\frac{1}{2\lambda}\exp\left(-\frac{|x|}{\lambda}\right)$ on
$\mathbb{R}$.

###  1.2 Motivation

The problem of high-dimensional sparse vectors estimation has recently been
studied in the framework of local differential privacy in [19]. For the
$1$-sparse mean estimation problem, the authors considered the set of
distributions $P$ supported on $\mathbb{B}_{\infty}(r)$, i.e. the ball of
radius $r$ in $\mathbb{R}^{d}$ with respect to the sup norm
$\|\cdot\|_{\infty}$, and having $\|\mathbb{E}_{P}[X]\|_{0}\leq 1$. They
proved that the private minimax mean squared error for non-interactive
$\alpha$-locally differentially private mechanisms is bounded from below by

$\min\left\\{r^{2},\frac{r^{2}d\log(2d)}{n(e^{\alpha}-1)^{2}}\right\\},$

proving that high-dimensional $1$-sparse mean estimation is impossible in this
setting when both $r^{2}\gtrsim 1$ and $r^{2}d\log(2d)\gtrsim
n(e^{\alpha}-1)^{2}$. This result can be related to selecting the support of a
1-sparse mean vector of such a distribution $P$, under the same constraints.
We generalize these results to symmetric and strongly log-concave
distributions on the whole $\mathbb{R}^{d}$ and to arbitrary sparsity.

Obvious applications of variable selection are the estimation of the set that
supports the non-null coefficients in the mean vector, or the estimation of
its size. We propose to use our procedure to build a private mean estimator of
$s-$sparse vectors in two steps: use one part of the sample to recover the
support and the other part to estimate the mean values of the selected
variables, that is a vector of reduced size. Moreover these results are a
benchmark for working on more realistic models such as high-dimensional linear
regression and clustering of high-dimensional vectors, see [31] and [30].

###  1.3 Strongly log-concave distributions

Log-concave measures play a significant role in many areas of pure and applied
mathematics, such as convex geometry [23], functional inequalities [7],
optimal transport theory [13, 14], random matrix theory [1], Monte-Carlo
sampling [17, 20], Bayesian inference [32] or non-parametric estimation [16,
18, 24]. The log-concavity assumption arises also naturally in various
modelisation contexts, such as survival and reliability analysis [27] or
econometrics [4], since it possesses many interesting properties subject to
interpretation, such as monotone likelihood ratio or non-decreasing hazard
rate function for instance. For further applications and references, see [4,
34].

Let us now state the definitions related to log-concavity that will be in
force in this article. A probability distribution $P$ on $\mathbb{R}$ is log-
concave if it admits a density $p$ with respect to the Lebesgue measure, that
writes $p=\exp(-\phi)$, with $\phi$ a convex function on $\mathbb{R}$. The
function $\phi$ is called the potential of the density $p$ and of the
probability measure $P$.

Furthermore, a function $\phi:\mathbb{R}\to\mathbb{R}$ is $c-$strongly convex
for some constant $c>0$ if, for all $(x,y)\in\mathbb{R}^{2}$ and $t\in(0,1)$,

$\phi(tx+(1-t)y)-\left[t\phi(x)+(1-t)\phi(y)\right]\leq-\frac{c}{2}t(1-t)(x-y)^{2}.$
(2)

Note that the parameter $c$ in (2) gives a positive lower bound on the
curvature of the convex function $\phi$. In the case where the function $\phi$
is two times differentiable, condition (2) indeed corresponds to a lower bound
on the second derivative:
$\inf_{x\in\mathbb{R}}\left\\{\phi^{\prime\prime}(x)\right\\}\geq c>0$.

A probability measure $P$ is said to be $c-$strongly log-concave if it admits
a density function $p:\mathbb{R}\to(0,+\infty)$ which is $c-$strongly log-
concave with potential $\phi$, in the sense that $p=\exp(-\phi)$ and $\phi$ is
a $c-$strongly convex potential. This is equivalent to assuming that
$p(x)=\exp(-\phi_{0}(x))\exp(-cx^{2}/2)$, for all $x\in\mathbb{R}$, with
$\phi_{0}$ being a finite convex function.

We consider the problem of support recovery of the sparse mean $\theta$ of a
random vector $X=\theta+\sigma\xi$ of distribution $P_{\theta}$, where $\xi$
has i.i.d. coordinates $\xi_{j}$, $j=1,...,d$, distributed according to a
$c-$strongly log-concave distribution $P^{\xi_{1}}$ for some constant $c>0$,
with unit variance and that is symmetric around zero. As $\xi_{1}$ is assumed
to be symmetric, this amounts to require that the $c-$strongly convex
potential $\phi$ of $p$ is even, or again that
$p(x)=\exp(-\phi_{0}(x))\exp(-cx^{2}/2)$, for all $x\in\mathbb{R}$, where
$\phi_{0}$ is a finite even convex function.

When dealing with some minimax lower bounds in the sequel, we will need to
assume that the normalized noise distribution $p$ is not too peaked around its
mean, in the sense that its curvature is bounded from above. More precisely,
we will assume in this case that $p=\exp(-\phi)$, where $\phi$ is a finite
convex potential satisfying, for a constant $c_{+}>0$, for all
$(x,y)\in\mathbb{R}^{2}$ and $t\in(0,1)$,

$\phi(tx+(1-t)y)-\left[t\phi(x)+(1-t)\phi(y)\right]\geq-\frac{c_{+}}{2}t(1-t)(x-y)^{2}.$
(3)

When the potential $\phi$ is two times differentiable, condition (3) can be
equivalently formulated as an upper bound on the second derivative of $\phi$:
$\sup_{x\in\mathbb{R}}\left\\{\phi^{\prime\prime}\right\\}\leq c_{+}$.

Such framework provides a non-parametric generalization of the Gaussian
assumption, where $\phi_{0}$ would be assumed to be a constant function and
the unit variance of $\xi$ would correspond to the value $c=c_{+}=1$. Note
that when $\xi$ is only assumed to be centered and strongly log-concave, with
unit variance and scaling parameter $c$, we have in general $c\leq 1$ and the
equality case $c=1$ characterizes the normal distribution $\mathcal{N}(0,1)$,
see [25]. Finally, let us denote $\Phi$ the cumulative distribution function
of the normal distribution.

###  1.4 Minimax framework

Let $X^{i}$, $i=1,\ldots,n$ be i.i.d random vectors of $\mathbb{R}^{d}$ with
distribution $P_{\theta}$. We assume that the vectors
$X^{i}=(X^{i}_{j})_{j=1,\ldots,d}$ for $i=1,\ldots,n$ are observed by $n$
distinct data holders who refuse to share their respective observations. The
statistician does not have access to these data but only to $\alpha$-locally
differentially private views $Z^{1},\ldots Z^{n}$. We assume that $\theta$
belongs to one of the sets $\Theta_{d}^{+}(s,a)$ or $\Theta_{d}(s,a)$
introduced in Section 1.1 and we study the problem of selecting the relevant
components of $\theta$, that is, of estimating the vector

$\eta=\eta(P_{\theta})=\left(I(\theta_{j}\neq 0)\right)_{j=1,\ldots,d},$

where $I(\cdot)$ is the indicator function. Our goal is to estimate the vector
$\eta$ by a selector $\hat{\eta}$, that is a measurable function
$\hat{\eta}=\hat{\eta}(Z^{1},\ldots,Z^{n})$ taking values in $\\{0,1\\}^{d}$,
where $Z^{1},\ldots,Z^{n}$ are $\alpha$-locally differentially private views
of $X^{1},\ldots,X^{n}$. We judge the quality of a selector $\hat{\eta}$ as an
estimator of $\eta$ by the Hamming loss between $\hat{\eta}$ and $\eta$ which
counts the number of positions at which $\hat{\eta}$ and $\eta$ differ :

$|\hat{\eta}-\eta|:=\sum_{j=1}^{d}|\hat{\eta}_{j}-\eta_{j}|=\sum_{j=1}^{d}I(\hat{\eta}_{j}\neq\eta_{j}).$

For the support recovery problem, we consider only $\alpha$-locally
differentially private mechanisms which transform each
$X^{i}\in\mathbb{R}^{d}$ into a private release $Z^{i}$ taking also values in
$\mathbb{R}^{d}$, that are known as non-interactive privacy mechanisms.
However, we distinguish between privacy mechanisms that act on each coordinate
of $X^{i}$ either separately, locally or globally. More specifically, we will
consider the two following scenarios:

  * •

Coordinate Local (CL) Privacy Mechanisms : there is a sequence
$Q=(Q^{i})_{i=1,\ldots,n}$ of Markov kernels providing $\alpha$-local
differential privacy such that $Z^{i}\sim Q^{i}(\cdot\mid X^{i}=x^{i})$ for
all $i\in\llbracket 1,n\rrbracket$, and $Q^{i}$ is obtained as product of
coordinate-wise kernels as follows:

$\text{for all }i\in\llbracket 1,n\rrbracket\text{ and all }j\in\llbracket
1,d\rrbracket,Z^{i}_{j}\sim Q^{i}_{j}(\cdot\mid X^{i}_{j}=x)$

for some $(\alpha/d)$-differentially private mechanism $Q^{i}_{j}$. We denote
by ${\mathcal{Q}}^{CL}_{\alpha}$ the set of all privacy mechanisms
$Q=(Q^{1},\ldots,Q^{n})$ satisfying these assumptions.

  * •

Coordinate Global (CG) Privacy Mechanisms : there is a sequence
$Q=(Q^{i})_{i=1,\ldots,n}$ of Markov kernels providing $\alpha$-local
differential privacy such that $Z^{i}\sim Q^{i}(\cdot\mid X^{i}=x^{i})$ for
all $i\in\llbracket 1,n\rrbracket$. We denote by $\mathcal{Q}_{\alpha}$ the
set of all privacy mechanisms $Q=(Q^{1},\ldots,Q^{n})$ satisfying this
assumption.

In other words, in the Coordinate Local case, we consider only non-interactive
$\alpha$-locally differentially private mechanisms that act coordinates by
coordinates. This scenario is easier to study than the second one for which
any non-interactive $\alpha$-locally differentially private mechanism is
allowed to be used.

For both scenarios, if $P_{\theta}$ denotes the distribution of $X^{i}$ then
we denote by $Q^{i}P_{\theta}$ the distribution of $Z^{i}$. Since the
distribution of $(X^{1},\ldots,X^{n})$ is $P_{\theta}^{\otimes n}$, the
distribution of $(Z^{1},\ldots,Z^{n})$ will be denoted by
$Q(P_{\theta}^{\otimes n})$. In the Coordinate Local case, we denote by
$P_{\theta_{j}}$ the distribution of $X^{i}_{j}$ and by
$Q^{i}_{j}P_{\theta_{j}}$ the distribution of $Z^{i}_{j}$.

We say that a selector $\hat{\eta}=(\hat{\eta}_{1},\ldots,\hat{\eta}_{d})$ is
separable if for all $j=1,\ldots,d$ its $j$th component $\hat{\eta}_{j}$
depends only on $(Z^{i}_{j})_{i=1,\ldots,n}$ . We denote by $\mathcal{T}$ the
set of all separable selectors. We are interested in the study of the
following private minimax risks

${\mathcal{R}}^{CL}_{n}(\alpha,\Theta)=\inf_{Q\in{\mathcal{Q}}^{CL}_{\alpha}}\inf_{\hat{\eta}=\hat{\eta}(Z^{1},\ldots,Z^{n})\in\mathcal{T}}\sup_{\theta\in\Theta}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}(Z^{1},\ldots,Z^{n})-\eta|,$ (4)

in the coordinate local case, and

$\mathcal{R}_{n}(\alpha,\Theta)=\inf_{Q\in\mathcal{Q}_{\alpha}}\inf_{\hat{\eta}=\hat{\eta}(Z^{1},\ldots,Z^{n})\in\mathcal{T}}\sup_{\theta\in\Theta}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}(Z^{1},\ldots,Z^{n})-\eta|,$ (5)

in the coordinate global case, for $\Theta=\Theta_{d}^{+}(s,a)$ and
$\Theta=\Theta_{d}(s,a)$.

We are interested in the study of two asymptotic properties : almost full
recovery and exact recovery, that we define here. Let
$(\Theta_{d}^{+}(s_{d},a_{d}))_{d\geq 1}$ be a sequence of classes of sparse
vectors. We will say that almost full recovery is possible for
$(\Theta_{d}^{+}(s_{d},a_{d}))_{d\geq 1}$ in the Coordinate Local case if
there exists $Q\in{\mathcal{Q}}^{CL}_{\alpha}$ and a selector $\hat{\eta}$
such that

$\lim_{d\rightarrow\infty}\sup_{\theta\in\Theta_{d}^{+}(s_{d},a_{d})}\frac{1}{s_{d}}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|=0.$

We will say that almost full recovery is impossible for
$(\Theta_{d}^{+}(s_{d},a_{d}))_{d\geq 1}$ in the Coordinate Local case if

$\liminf_{d\rightarrow+\infty}\inf_{Q\in{\mathcal{Q}}^{CL}_{\alpha}}\inf_{\hat{\eta}=\hat{\eta}(Z^{1},\ldots,Z^{n})\in\mathcal{T}}\sup_{\theta\in\Theta_{d}^{+}(s,a)}\frac{1}{s_{d}}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|>0.$

We will say that exact recovery is possible for
$(\Theta_{d}^{+}(s_{d},a_{d}))_{d\geq 1}$ in the Coordinate Local case if
there exists $Q\in{\mathcal{Q}}^{CL}_{\alpha}$ and a selector $\hat{\eta}$
such that

$\lim_{d\rightarrow\infty}\sup_{\theta\in\Theta_{d}^{+}(s_{d},a_{d})}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|=0.$

We will say that exact recovery is impossible for
$(\Theta_{d}^{+}(s_{d},a_{d}))_{d\geq 1}$ in the Coordinate Local case if

$\liminf_{d\rightarrow+\infty}\inf_{Q\in{\mathcal{Q}}^{CL}_{\alpha}}\inf_{\hat{\eta}=\hat{\eta}(Z^{1},\ldots,Z^{n})\in\mathcal{T}}\sup_{\theta\in\Theta_{d}^{+}(s,a)}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|>0.$

We use similar definitions in the Coordinate Global case with
${\mathcal{Q}}^{CL}_{\alpha}$ replaced by $\mathcal{Q}_{\alpha}$.

###  1.5 Related work

Variable selection with Hamming loss in the Gaussian mean model in
$\mathbb{R}^{d}$ has been studied in the non-private setting in [11]. The
authors provide non-asymptotic lower and upper bounds on the non-private
version of minimax risk (4). As corollaries, they derive necessary and
sufficient conditions for almost full recovery and exact recovery to be
possible. If $s,\,d\to\infty$ such that $s/d\to 0$, they highlight a critical
value $a^{*}=(\sigma/\sqrt{n})\sqrt{2\log(d/s-1)}(1+\delta)$ for a specific
sequence $\delta=\delta(d,s)\to 0$ such that almost full recovery is possible
for $a\geq a^{*}$ and impossible for $a<a^{*}$. Similar results have been
obtained for exact recovery with the greater critical value
$a^{*}=(\sigma/\sqrt{n})(\sqrt{2\log(d-s)}+\sqrt{2\log s})$. In the present
paper, we will see how these results are affected by the privacy constraints.

For estimating the $1-$sparse mean of high-dimensional vectors with
distribution supported on a compact support it is known that the rates are
deteriorates by a factor $d$ under local differential privacy, see [19]. Under
a relaxation of central differential privacy called
$(\alpha,\delta)-$approximate differential privacy - see for instance [21],
[2] and [6] have provided estimators of the mean and the covariance of high-
dimensional Gaussian vectors and theoretical guarantees that do not require
additional assumptions on the parameters. In some regimes the rates are not
deteriorated and it is therefore difficult to anticipate the role of privacy
on each particular problem.

A few papers tackle a slightly different selection problem under privacy
constraints mostly under central differential privacy constraints. They are
interested in the largest sum of $k$ coordinates of the common mean value
$\theta$ of a vector supported on $\\{0,1\\}^{d}$. We are mainly interested in
recovering the position of significant coordinates in the $s-$sparse mean
vector $\theta$.
In [35], the authors study top-$k$ selection under a relaxation of central
differential privacy called $({\alpha},\delta)$-approximate differential
privacy. However, they use a weighted Hamming loss as described below.
Precisely, if $X_{1},\ldots,X_{n}$ are drawn i.i.d. from some distribution $P$
on $\\{0,1\\}^{d}$, they want to find the $k$ greatest coordinates of the mean
vector $\theta=\mathbb{E}_{P}[X_{1}]$ while respecting
$({\alpha},\delta)$-differential privacy constraints. They prove the existence
of a $(1,1/(nd))$-differentially private mechanism that outputs
$Z\in\\{0,1\\}^{d}$ with $k$ non zero coordinates such that

$\mathbb{E}\left[\sum_{j=1}^{d}\theta_{j}{I}(Z_{j}=1)\right]\geq\max_{\eta\in\\{0,1\\}^{d}:\|\eta\|_{1}=k}\sum_{j=1}^{d}\theta_{j}{I}(\eta_{j}=1)-\beta$

requires $n\gtrsim\sqrt{k}\log d$ samples in the low accuracy regime where
$\beta=k/10$. Moreover, repeated use of the classical exponential mechanism
solves this problem with $n=O(\sqrt{k}\log d)$ samples. In [3], the authors
study an empirical version of the problem studied in [35]: they want to find
the top-k coordinates of the vector $q\in\mathbb{R}^{d}$ defined by
$q_{j}=(1/n)\sum_{i=1}^{n}X_{i,j}$, $j=1,\ldots,d$ while respecting
$({\alpha},\delta)$-differential privacy constraints. Let $\tau$ be the $k$-th
largest value among the coordinates $\\{q_{1},\ldots,q_{k}\\}$. They prove the
existence of a $({\alpha},\delta)$-differentially private mechanism that
outputs a set $S\subset\llbracket 1,d\rrbracket$ of $k$ elements such that
$q_{j}\geq\tau-\beta$ for all $j\in S$ requires $n\gtrsim k\log(d)$ samples in
the high-accuracy regime where $\beta\asymp\sqrt{\log d/n}$. In [37], the
author studies the same problem as [35] for $k=1$ under non-interactive
$\alpha$-local differential privacy constraints. If we consider the low-
accuracy regime considered by [35], this result shows that estimating the
largest coordinate of a 1-sparse mean $\theta$ under non-interactive
$\alpha$-local differential privacy requires $n\gtrsim d\log d/\alpha^{2}$
samples, which is by a factor $d$ larger than in the central model of
$({\alpha},\delta)$-approximate differential privacy.

###  1.6 Description of results

We address the problem of variable selection in a symmetric, strongly log-
concave model in $\mathbb{R}^{d}$ under local differential privacy
constraints. We provide lower and upper bounds on the rate of convergence for
the expected Hamming loss over classes of at most $s$-sparse vectors whose
non-zero coordinates are separated from $0$ by a constant $a>0$.

When we restrict our attention to non-interactive mechanisms that act
independently on each coordinate (coordinate local privacy mechanisms) we have
proved that, contrary to the non-private setting, almost full recovery and
exact recovery are impossible whatever the value of $a$ in the high-
dimensional regime when $n\alpha^{2}\lesssim d^{2}$. This is due to the fact
that the loss of information due to privacy may reduce the effective sample
size $N:=n\alpha^{2}/d^{2}$ under the value 1, and this does not allow support
recovery neither exact nor almost full. This result is significantly different
from the non-private case where [11] shows that variable selection is always
possible, even for $n=1$ observation for significant enough mean value $a$.
However, in the regime $n\alpha^{2}/d^{2}\gg\log(d)$ we exhibit a critical
value $a^{*}$ (up to a logarithmic factor) such that exact recovery is
possible for all $a\gg a^{*}$ and impossible for all $a\leq a^{*}$. We also
prove that these results can be improved when allowing for all non-interactive
locally differentially private mechanisms, that we also call coordinate
global. The effective sample size is $Nd$ in this case and it is larger than
$N$.
Let us note that the separable selectors that we propose are free of the
sparsity parameter $s$. They depend on $a$ and methods could be made adaptive
to $a$, but this is beyond the scope of this work.
For many estimation problems, allowing for sequentially interactive privacy
mechanisms, that randomize each vector $X_{i}$ by using also the publicly
available information $Z_{1},...,Z_{i-1}$, $i=2,...,n$, does not improve
substantially over non-interactive minimax rates. This includes for instance
density estimation [10], one-dimensional mean estimation [19], and estimation
of a linear functional of the true distribution [33]. However, for some
estimation problems (see for instance the estimation of the integrated square
of a density, [12]) and some testing problems (see [5] and [12]) allowing for
sequentially interaction between data-holders can substantially improve over
non-interactive minimax rates of estimation or non-interactive minimax rates
of testing. We consider here only non-interactive privacy mechanisms for each
vector $X_{i}$, but we conjecture that the exact and almost full recovery
would be improved for interactive privacy mechanisms. It is left for future
work to study whether that is indeed the case.

The paper is organised as follows. In Section 2, we study the minimax risk
(4). We first provide a lower bound which enables us to derive necessary
conditions for almost full recovery and exact recovery to be possible in the
case where only coordinate local privacy mechanisms are used. In particular,
we prove that almost full recovery is impossible in this case as soon as the
quantity $n\alpha^{2}/d^{2}$ is bounded from above. We then provide non-
asymptotic upper bounds on the minimax risks in propositions and state more
explicit asymptotic sufficient conditions for almost full recovery and exact
recovery to be possible in our corollaries. These conditions and associated
results are summarised in Table 1. In Section 3, we study the minimax risk (5)
and prove that the results of Section 2 can be improved when any non-
interactive (coordinate global) $\alpha$-locally differentially private
mechanism is allowed. See Table 2 for a summary of these results. Detailed
proofs can be found in the Appendix.

| $a\lesssim\frac{\sigma}{\sqrt{N}}$ |  $\frac{\sigma}{\sqrt{N}}\ll a\leq 2\sigma$ |  $a\geq 2\sigma$
---|---|---|---
$N:=\frac{n\alpha^{2}}{d^{2}}\lesssim 1$ | impossible |  impossible |  impossible
$N:=\frac{n\alpha^{2}}{d^{2}}\gg 1$ | impossible |  possible, as soon as $a\gg\frac{\sigma}{\sqrt{N}}\sqrt{\log(d)}$ if moreover $N\gg{\log\left(d\right)}$ |  possible, if $\frac{\log(d)}{N}\lesssim 1$
Table 1: Exact recovery of $\theta$ in either $\Theta^{+}_{d}(s,a)$ or $\Theta_{d}(s,a)$ in the Coordinate Local case. Similar results hold for almost full recovery with $\log(d)$ replaced by $\log(d/s)$.  | $a\lesssim\sigma\sqrt{\frac{\log d}{Nd}}$ |  $\sigma\sqrt{\frac{\log d}{Nd}}\ll a\leq 2\sigma$ |  $a\geq 2\sigma$
---|---|---|---
$\frac{Nd}{\log d}\lesssim 1$ | impossible |  impossible |  impossible if $a\leq\sigma\sqrt{\log\left(1+\frac{\log d}{16Nd}\right)}$
$\frac{Nd}{\log d}\gg 1$ | impossible |  possible, as soon as $a\gg\sigma\sqrt{\frac{\log d}{Nd}}$, if moreover $Nd\gg{\log(d)}$ |  possible
Table 2: Exact recovery of $\theta$ in either $\Theta^{+}_{d}(s,a)$ or
$\Theta_{d}(s,a)$ in the Coordinate Global case. We have set
$N=n\alpha^{2}/d^{2}$ for a better comparison with the Coordinate Local case.

##  2 Coordinate local non-interactive privacy mechanisms

In this section, we provide a lower bound on the private minimax risk (4).
This enables us to obtain necessary conditions for almost full recovery and
exact recovery to be possible in the Coordinate Local scenario. In particular,
we prove that almost full recovery is impossible in the private setting of the
Coordinate Local case if the quantity $N:=n\alpha^{2}/d^{2}$ is bounded from
above. We then provide upper bounds on the minimax risk that entail sufficient
conditions for almost full recovery and exact recovery to be possible.

###  2.1 Lower bound

We first state our lower bound.

######  Theorem 2.1.

Assume that the measure $P^{\xi_{1}}$ of the noise coordinates, is log-concave
with a density $p=\exp(-\phi)$, where the potential $\phi$ has a curvature
bounded from above by a constant $c_{+}>0$, that satisfies inequality (3).
Then for any $a>0$, $\alpha>0$, $1\leq s\leq d$, $n\geq 1$, we have

$\mathcal{R}^{CL}_{n}(\alpha,\Theta_{d}^{+}(s,a))\geq\left(1-\frac{s}{d}\right)\exp\left(-4n(e^{\alpha/d}-1)^{2}\min\left\\{\frac{c_{+}a^{2}}{4\sigma^{2}},1\right\\}\right).$
(6)

The proof of Theorem 2.1 can be found in Appendix A.2. Some auxiliary results
used for the proof of Theorem 2.1 can be found in Appendix A.1. Note that
since $\Theta_{d}^{+}(s,a)\subset\Theta_{d}(s,a)$ we have
$\mathcal{R}^{CL}_{n}(\alpha,\Theta_{d}^{+}(s,a))\leq\mathcal{R}^{CL}_{n}(\alpha,\Theta_{d}(s,a))$,
thus the right hand side of (6) is also a lower bound for
$\mathcal{R}^{CL}_{n}(\alpha,\Theta_{d}(s,a))$.

A careful look at the proof of Theorem 2.1 shows that log-concavity is in fact
not needed in the previous result, if we assume the existence of a positive
density, converging to zero at infinity, and with a two times continuously
differentiable potential achieving (3).

For better confidentiality in practice, the parameter $\alpha$ must not be too
large. In particular, we assume that $\alpha/d\rightarrow 0$ when
$d\rightarrow+\infty$. We thus have $n(e^{\alpha/d}-1)^{2}\sim
n\alpha^{2}/d^{2}$ and Theorem 2.1 immediately shows the following.

######  Corollary 2.2.

Grant assumptions of Theorem 2.4. Let $\alpha>0$, $1\leq s\leq d$, $n\geq 1$
be such that $s/d\leq C_{0}$ for some constant $C_{0}\in(0,1)$, and
$\alpha/d\rightarrow 0$ when $d\rightarrow\infty$. Then, if
$n\alpha^{2}/d^{2}\leq C_{1}$ for some constant $C_{1}>0$ or if
$n\alpha^{2}/d^{2}\rightarrow\infty$ as $d\rightarrow\infty$ and $a^{2}\leq
C_{2}\sigma^{2}d^{2}/n\alpha^{2}$ for some constant $C_{2}>0$ depending only
on $c_{+}$, it holds

$\mathcal{R}^{CL}_{n}(\alpha,\Theta)\geq C$

for some constant $C>0$, where $\Theta=\Theta_{d}^{+}(s,a)$ or
$\Theta=\Theta_{d}(s,a)$.

Corollary 2.2 shows that almost full recovery is impossible under local
differential privacy constraints if the quantity $n\alpha^{2}/d^{2}$ is
bounded from above. In particular, almost full recovery is impossible under
local differential privacy constraints in the high-dimensional setting, that
is when $n\leq d$, whatever the value of $a$. Corollary 2.2 also proves that
if $n\alpha^{2}/d^{2}\rightarrow+\infty$ then almost full recovery is
impossible if $a\lesssim\sigma d/\sqrt{n\alpha^{2}}$.

This underlines a strong difference between the private setting and the
classical setting, since [11] proved that in the non-private setting almost
full recovery is possible for values of $|a|$ large enough, even if $n=1$.
However, both almost full and exact recovery are impossible for any signal
value $a$ when the effective size $N=n\alpha^{2}/d^{2}\lesssim 1$ under
privacy constraints.

###  2.2 Privacy mechanism

In this section, we introduce a non-interactive privacy mechanism creating
private views $Z^{1},\ldots,Z^{n}$ of the original data $X^{1},\ldots,X^{n}$
that satisfy the local differential privacy constraint of level $\alpha$.
These privatized data will then be used to define a private selector whose
risk will be studied in Section 2.3.

To obtain the privatized data, we first censor the unbounded random variables
$X^{i}_{j}$, for $i=1,\ldots,n$, $j=1,\ldots,d$, and then make use of an
appropriately scaled version of the classical Laplace mechanism. For all
$i\in\llbracket 1,n\rrbracket$ and $j\in\llbracket 1,d\rrbracket$ define

$Z^{i}_{j}=\mathrm{sgn}[X^{i}_{j}]+\frac{2d}{\alpha}W^{i}_{j},$ (7)

where $\mathrm{sgn}[x]=1$, for $x\geq 0$, and 0, for $x<0$, the $W^{i}_{j}$’s
are i.i.d Laplace$(1)$ random variables, and $W^{i}_{j}$ is independent from
$X^{i}_{j}$.

Note that the privacy mechanism defining $(Z^{i})_{i=1,\ldots,n}$ is non-
interactive since $Z^{i}$ does only depend on $X^{i}$ and not on $Z^{k}$ for
$k\neq i$. This is also a coordinate local mechanism since $Z^{i}_{j}$ depends
on $X^{i}_{j}$ but not on the $X^{i}_{l}$ for $l\neq j$. The following
Proposition shows that it satisfies the condition of $\alpha$-local
differential privacy.

######  Proposition 2.3.

For all $i\in\llbracket 1,n\rrbracket$ and $j\in\llbracket 1,d\rrbracket$,
$Z^{i}_{j}$ is an $\alpha/d$-differentially private view of $X^{i}_{j}$.
Consequently, for all $i\in\llbracket 1,n\rrbracket$
$Z^{i}=(Z^{i}_{j})_{j=1,\ldots,d}$ is an $\alpha$-differentially private view
of $X^{i}$.

###### Proof.

Set $r=2d/\alpha$. By definition of the privacy mechanism (7), the conditional
density of $Z^{i}_{j}$ given $X^{i}_{j}=x$ can be written as

$q^{Z^{i}_{j}\mid
X^{i}_{j}=x}(z)=\frac{1}{2r}\exp\left(-\frac{|z-\mathrm{sgn}[x]|}{r}\right).$

Thus, by the reverse and the ordinary triangle inequality it holds for all
$i\in\llbracket 1,n\rrbracket$, $j\in\llbracket 1,d\rrbracket$ and all
$x,x^{\prime},z\in\mathbb{R}$,

$\displaystyle\frac{q^{Z^{i}_{j}\mid X^{i}_{j}=x}(z)}{q^{Z^{i}_{j}\mid
X^{i}_{j}=x^{\prime}}(z)}$
$\displaystyle=\exp\left(\frac{|z-\mathrm{sgn}[x^{\prime}]|}{r}-\frac{|z-\mathrm{sgn}[x]|}{r}\right)$
$\displaystyle\leq\exp\left(\frac{|\mathrm{sgn}[x^{\prime}]-\mathrm{sgn}[x]|}{r}\right)$
$\displaystyle\leq\exp\left(\frac{2}{r}\right)\leq\exp\left(\frac{\alpha}{d}\right).$

This proves that $Z^{i}_{j}$ is an $\alpha/d$-differentially private view of
$X^{i}_{j}$. Let us check that $Z^{i}$ is an $\alpha$-differentially private
view of $X^{i}$. Denote by $q^{Z^{i}\mid X^{i}=x}$ the conditional density of
$Z^{i}$ given $X^{i}=x$ and note that for all
$x,x^{\prime},z\in\mathbb{R}^{d}$ it holds

$\frac{q^{Z^{i}\mid X^{i}=x}(z)}{q^{Z^{i}\mid
X^{i}=x^{\prime}}(z)}=\prod_{j=1}^{d}\frac{q^{Z^{i}_{j}\mid
X^{i}_{j}=x_{j}}(z_{j})}{q^{Z^{i}_{j}\mid
X^{i}_{j}=x_{j}^{\prime}}(z_{j})}\leq e^{\alpha},$

using the independence of the coordinates $X_{1}^{i},...,X_{d}^{i}$ and the
conditional independence of $Z_{1}^{i},...,Z_{d}^{i}$ given $X^{i}$. ∎

###  2.3 Upper bounds

Using these privatized data, we define two selectors that will provide upper
bounds on the minimax risk (4). For the class $\Theta_{d}^{+}(s,a)$, we will
use the selector $\hat{\eta}^{+}$ with the components

$\hat{\eta}^{+}_{j}=I\left(\frac{1}{n}\sum_{i=1}^{n}Z^{i}_{j}\geq\tau\right),\quad
j=1,\ldots,d,$ (8)

where the threshold $\tau$ has to be properly chosen, later on. For the class
$\Theta_{d}(s,a)$, we will use the selector $\hat{\eta}$ with the components

$\hat{\eta}_{j}=I\left(\left|\frac{1}{n}\sum_{i=1}^{n}Z^{i}_{j}\right|\geq\tau\right),\quad
j=1,\ldots,d,$ (9)

where $\tau$ to be defined later on. Note that $\hat{\eta}^{+}$ and
$\hat{\eta}$ are separable selectors since $\hat{\eta}^{+}_{j}$ and
$\hat{\eta}_{j}$ depend only on $(Z^{i}_{j})_{i=1,\ldots,n}$ and not on the
$Z^{i}_{k}$ for $k\neq j$. We now study the performances of these selectors.
Recall that $\Phi$ is c.d.f. of the normal distribution.

######  Proposition 2.4.

Assume that $a\geq 2\sigma$. Set $C_{1}:=2\Phi(2\sqrt{c})-1>0$. If $\tau$ is
chosen such that

$C_{1}-\tau>0,\,\tau\alpha/(8d)\leq 1\text{ and }\alpha(C_{1}-\tau)/(8d)\leq
1,$

then it holds for all $\theta\in\Theta_{d}^{+}(s,a)$,

$\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]\leq\frac{d-|S|}{s}\left[\exp\left(-\frac{n\tau^{2}}{2^{3}}\right)+\exp\left(-\frac{\tau^{2}n\alpha^{2}}{2^{7}d^{2}}\right)\right]\\\
+\frac{|S|}{s}\left[\exp\left(-\frac{n(C_{1}-\tau)^{2}}{2^{3}}\right)+\exp\left(-\frac{(C_{1}-\tau)^{2}n\alpha^{2}}{2^{7}d^{2}}\right)\right],$
(10)

and for all $\theta\in\Theta_{d}(s,a)$ it holds

$\mathbb{E}\left[\frac{1}{s}|\hat{\eta}-\eta|\right]\leq
2\frac{d-|S|}{s}\left[\exp\left(-\frac{n\tau^{2}}{2^{3}}\right)+\exp\left(-\frac{\tau^{2}n\alpha^{2}}{2^{7}d^{2}}\right)\right]\\\
+2\frac{|S|}{s}\left[\exp\left(-\frac{n(C_{1}-\tau)^{2}}{2^{3}}\right)+\exp\left(-\frac{(C_{1}-\tau)^{2}n\alpha^{2}}{2^{7}d^{2}}\right)\right],$
(11)

where $S$ denotes the support of $\theta$.

The proof of Proposition 2.4 is given in Section A.4 in the Appendix. Some
auxiliary results used in the proof of Proposition 2.4 can be found in
Appendix A.3. The following Corollary gives sufficient conditions so that
almost full recovery and exact recovery are possible under local differential
privacy in the Coordinate Local case when $a\geq 2\sigma$.

######  Corollary 2.5.

Set $C_{1}=2\Phi(2\sqrt{c})-1>0$. Assume that

$\alpha/d\rightarrow 0,n\alpha^{2}/d^{2}\rightarrow+\infty\text{ and
}\limsup\frac{\log(d/s)}{n\alpha^{2}/d^{2}}<\frac{C_{1}^{2}}{2^{9}}.$

Then the selector $\hat{\eta}^{+}$ defined by (8) with $\tau=C_{1}/2$
satisfies

$\sup_{\theta\in\Theta}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}^{+}(Z^{1},\ldots,Z^{d})-\eta|\rightarrow 0,$ (12)

for all $a\geq 2\sigma$, where $\Theta=\Theta_{d}^{+}(s,a)$ or
$\Theta=\Theta_{d}(s,a)$. If, in addition,
$\limsup\frac{\log(d)}{n\alpha^{2}/d^{2}}<\frac{C_{1}^{2}}{2^{9}}$, then

$\sup_{\theta\in\Theta}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}^{+}(Z^{1},\ldots,Z^{d})-\eta|\rightarrow 0,$ (13)

for all $a\geq 2\sigma$.

The proof of Corollary 2.5 is given in Section A.5 in the Appendix. Since we
have seen that almost full recovery is impossible when $n\alpha^{2}/d^{2}$ is
bounded from above or when $n\alpha^{2}/d^{2}\rightarrow+\infty$ and
$a\lesssim(\sigma d)/(\sqrt{n}\alpha)$, it remains to study the case where
$n\alpha^{2}/d^{2}\rightarrow+\infty$ and $\sigma d/(\sqrt{n}\alpha)\ll a\leq
2\sigma$. This is done below.

######  Proposition 2.6.

Let $a>0$. If $\tau$ is chosen such that $\tau<2a/\sigma p(2)$,
$\tau\alpha/(8d)<1$ and $\alpha(a/\sigma p(2)-\tau/2)/(4d)\leq 1$ then it
holds for all $\theta\in\Theta_{d}^{+}(s,a)$,

$\displaystyle\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]$
$\displaystyle\leq\frac{d-|S|}{s}\left[\exp\left(-\frac{n\tau^{2}}{2^{3}}\right)+\exp\left(-\frac{\tau^{2}n\alpha^{2}}{2^{7}d^{2}}\right)\right]$
$\displaystyle+\frac{|S|}{s}\left[\exp\left(-\frac{n(a/\sigma
p(2)-\tau/2)^{2}}{2^{3}}\right)+\exp\left(-\frac{(a/\sigma
p(2)-\tau/2)^{2}n\alpha^{2}}{2^{5}d^{2}}\right)\right],$

where $S$ denotes the support of $\theta$.

The proof of Proposition 2.6 can be found in Section A.6 in the Appendix. Note
that as for the case $a\geq 2\sigma$, if $\theta\in\Theta_{d}(s,a)$ we use
$\hat{\eta}$ instead of $\hat{\eta}^{+}$ and we can prove the same result with
an extra multiplicative factor 2. The next corollary gives new sufficient
conditions so that almost full recovery and exact recovery are possible.

######  Corollary 2.7.

Assume that $\alpha/d\rightarrow 0$, $n\alpha^{2}/d^{2}\rightarrow+\infty$ and
$\sigma d/(\sqrt{n}\alpha)\ll a\leq 2\sigma$. The selector $\hat{\eta}^{+}$
defined by (8) with $\tau=p(2)a/\sigma$ satisfies for $d$ large enough

$\sup_{\theta\in\Theta_{d}^{+}(s,a)}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}^{+}(Z^{1},\ldots,Z^{d})-\eta|\leq
2\exp\left(\log\left(\frac{d}{s}\right)-\frac{p^{2}(2)a^{2}n\alpha^{2}}{2^{9}\sigma^{2}d^{2}}\right).$

In particular, if $a\gg\frac{\sigma
d}{\alpha\sqrt{n}}\log^{1/2}\left(\frac{d}{s}\right)$ it holds

$\sup_{\theta\in\Theta_{d}^{+}(s,a)}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}^{+}(Z^{1},\ldots,Z^{d})-\eta|\rightarrow 0.$ (14)

Moreover, if $a\gg\frac{\sigma d}{\alpha\sqrt{n}}\log^{1/2}\left(d\right)$
then

$\sup_{\theta\in\Theta_{d}^{+}(s,a)}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}^{+}(Z^{1},\ldots,Z^{d}))-\eta|\rightarrow 0.$ (15)

If $n\alpha^{2}/d^{2}\rightarrow\infty$ with
$(n\alpha^{2}/d^{2})\gg\log(d/s)$, then Corollary 2.7 combined with Corollary
2.5 and with the lower bound (6) prove a phase transition result (up to $\log$
factors) at the value $a^{*}=a^{*}(n,\alpha,d,\sigma)=\sigma
d/(\alpha\sqrt{n})$. Indeed, we get that almost full recovery is impossible in
the Coordinate Local case for all $a\leq Ca^{*}$ and is possible for all $a\gg
a^{*}\log^{1/2}(d/s)$.

##  3 Coordinate global non-interactive privacy mechanisms

In this section, we study the minimax risk (5). We prove that in the
Coordinate Global case, almost full recovery and exact recovery are possible
under weaker assumptions than the one we obtained for the Coordinate Local
case.

###  3.1 Privacy mechanism

We describe in this section the privacy mechanism we use to obtain private
data that will be used to design a private selector and to obtain upper bounds
on the minimax risk (5) in the Coordinate Global case.

For all $i\in\llbracket 1,n\rrbracket$, the private view $Z^{i}$ of $X^{i}$ is
obtained using the following steps:

  * •

Compute $f(X^{i})=(\mathrm{sgn}[X^{i}_{j}])_{j=1,\ldots,d}$. For short, let us
denote $\tilde{X}^{i}=f(X^{i})$.

  * •

Sample $Y^{i}\sim\mathcal{B}(\pi_{\alpha})$ where
$\pi_{\alpha}=e^{\alpha}/(e^{\alpha}+1)$ and generate $\tilde{Z}^{i}$
uniformly distributed on the set

$\left\\{\tilde{z}\in\left\\{-B,B\right\\}^{d}\,\mid\,\langle\tilde{z},\tilde{X}^{i}\rangle>0\text{
or }(\langle\tilde{z},\tilde{X}^{i}\rangle=0\text{ and
}\tilde{z}_{1}=B\tilde{X}^{i}_{1})\right\\}$

if $Y^{i}=1$, respectively on the set

$\left\\{\tilde{z}\in\left\\{-B,B\right\\}^{d}\,\mid\,\langle\tilde{z},\tilde{X}^{i}\rangle<0\text{
or }(\langle\tilde{z},\tilde{X}^{i}\rangle=0\text{ and
}\tilde{z}_{1}=-B\tilde{X}^{i}_{1})\right\\}$

if $Y^{i}=0$, with

$B=\frac{e^{\alpha}+1}{e^{\alpha}-1}K_{d},\text{ where
}\frac{1}{K_{d}}=\begin{cases}\frac{1}{2^{d-1}}\binom{d-1}{\frac{d-1}{2}}&\text{
if $d$ is odd}\\\
\frac{(d-2)!(d-2)}{2^{d-1}(\frac{d}{2}-1)!\frac{d}{2}!}&\text{ if $d$ is
even}.\end{cases}$ (16)

  * •

Define the vector $Z^{i}$ by $Z^{i}=\tilde{Z}^{i}$ if $d$ is odd, and by its
components

$Z^{i}_{j}=\begin{cases}\frac{d-2}{2(d-1)}\tilde{Z}^{i}_{1}&\text{if }j=1\\\
\tilde{Z}^{i}_{j}&\forall j\in\llbracket 2,d\rrbracket,\end{cases}$

if $d$ is even.

This mechanism is strongly inspired by the one proposed by Duchi et al. [19]
for mean estimation on the set of distributions $P$ supported on
$\mathbb{B}_{\infty}(r)\subset\mathbb{R}^{d}$ with $\|\mathbb{E}[X]\|_{0}\leq
s$. In particular, if $d$ is odd, the event
$\\{\langle\tilde{z},\tilde{X}^{i}\rangle=0\\}$ has probability zero for all
$\tilde{z}\in\\{-B,B\\}^{d}$ and our mechanism coincides in this case with the
one proposed by Duchi et al. [19] applied to $\mathrm{sgn}(X^{i})$ instead of
$X^{i}$.

######  Proposition 3.1.

For all $i\in\llbracket 1,n\rrbracket$, $Z^{i}$ is an $\alpha$-differentially
private view of $X^{i}$.

The following proposition will be useful in the analysis of the selector
proposed in Section 3.2.

######  Proposition 3.2.

For all $i\in\llbracket 1,n\rrbracket$, it holds

$\mathbb{E}[Z^{i}\mid X^{i}]=f(X^{i}).$

The proofs of Proposition 3.1 and Proposition 3.2 can be found respectively in
Section B.1 and B.2 of the Appendix. Note that it also holds
$\mathbb{E}[Z^{i}\mid X^{i}]=f(X_{i})$ when $Z_{i}$ is produced via the
Laplace mechanism described in Subsection 2.2. However the variance
$\mathrm{Var}(Z^{i}_{j}\mid X^{i})$ is slower by a multiplicative factor $d$
when $Z^{i}$ is produced with the Laplace mechanism than when it is obtained
with the above coordinate global mechanism. Indeed, if $Z^{i}$ is produced
with the above mechanism, then we have $\mathrm{Var}(Z^{i}_{j}\mid X^{i})\leq
B^{2}$. Stirling’s approximation yields $K_{d}^{2}\lesssim d$ for $d$ large
enough, see Lemma B.1 in Appendix B.3 for details. Thus, if $\alpha$ is
bounded, we obtain $\mathrm{Var}(Z^{i}_{j}\mid X^{i})\leq d/\alpha^{2}$. Now,
if $Z^{i}$ is produced with the Laplace mechanism then it holds
$\mathrm{Var}(Z^{i}_{j}\mid X^{i})=8d^{2}/\alpha^{2}$. This faster variance
explains that we will obtain better results when allowing for coordinate
global mechanisms.

###  3.2 Upper bounds

Using the privatized data of the previous subsection, we define two selectors
that will enable us to obtain upper bounds on the minimax risk (5). As in the
Coordinate Local case, for the class $\Theta_{d}^{+}(s,a)$, we will use the
selector $\hat{\eta}^{+}$ with the components

$\hat{\eta}^{+}_{j}=I\left(\frac{1}{n}\sum_{i=1}^{n}Z^{i}_{j}\geq\tau\right),\quad
j=1,\ldots,d,$ (17)

where the threshold $\tau$ has to be chosen. For the class $\Theta_{d}(s,a)$,
we will use the selector $\hat{\eta}$ with the components

$\hat{\eta}_{j}=I\left(\left|\frac{1}{n}\sum_{i=1}^{n}Z^{i}_{j}\right|\geq\tau\right),\quad
j=1,\ldots,d.$ (18)

We now study the performances of these selectors.

The following result gives an upper bound on the risk of selector (17) when
$a\geq C\sigma$ and will enable us to obtain sufficient conditions so that
almost full recovery is possible when $a\geq 2\sigma$ in the Coordinate Global
case.

######  Proposition 3.3.

Assume that $a>2\sigma$ and set $C_{1}:=2\Phi(2\sqrt{c})-1>0$. If $\tau$ is
chosen such that $C_{1}-\tau>0,$ then it holds for all
$\theta\in\Theta_{d}^{+}(s,a)$,

$\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]\leq\frac{d-|S|}{s}\exp\left(-\frac{n\tau^{2}}{2B^{2}}\right)+\frac{|S|}{s}\exp\left(-\frac{n(C_{1}-\tau)^{2}}{2B^{2}}\right),$

where $S$ denotes the support of $\theta$. In particular, choosing
$\tau=C_{1}/2$ yields

$\sup_{\theta\in\Theta_{d}^{+}(s,a)}\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]\leq\frac{d}{s}\exp\left(-\frac{C_{1}^{2}n(e^{\alpha}-1)^{2}}{8(e^{\alpha}+1)^{2}K_{d}^{2}}\right)$

for all $a\geq 2\sigma$.

The proof of Proposition 3.3 can be found in section B.4 of the Appendix. Note
that we can provide similar results on the class $\Theta_{d}(s,a)$ considering
the selector $\hat{\eta}$. The upper bounds are the same as for the class
$\Theta_{d}^{+}(s,a)$ up to a multiplicative factor 2 that comes from the use
in the proof of the two-sided Hoeffding’s inequality instead of the one-sided
inequality. Since $K_{d}\leq C\sqrt{d}$ for $d$ large enough, we obtain that a
sufficient condition for almost full recovery to be possible when $a\geq
2\sigma$ is that
$\frac{n(e^{\alpha}-1)^{2}}{(e^{\alpha}+1)^{2}d}\gtrsim\log(d/s)$. Moreover,
using that $(e^{\alpha}-1)^{2}/(e^{\alpha}+1)^{2}\geq 0.2\alpha^{2}$ if
$\alpha\leq 1$, we obtain that a sufficient condition for almost full recovery
to be possible when $a\geq 2\sigma$ and $\alpha\leq 1$ is that
$n\alpha^{2}/d\gtrsim\log(d/s)$. This improves the result we obtained when we
considered only privacy mechanisms acting coordinates by coordinates for which
we needed $n\alpha^{2}/d^{2}\gtrsim\log(d/s)$. We now deal with the case
$a\ll\sigma$.

######  Proposition 3.4.

Let $a>0$ and $a\leq 2\sigma$. If $\tau$ is chosen such that
$\tau<2p(2)a/\sigma,$ then it holds for all $\theta\in\Theta_{d}^{+}(s,a)$,

$\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]\leq\frac{d-|S|}{s}\exp\left(-\frac{n\tau^{2}}{2B^{2}}\right)+\frac{|S|}{s}\exp\left(-\frac{n(2p(2)a/\sigma-\tau)^{2}}{2B^{2}}\right),$

where $S$ denotes the support of $\theta$.

The proof of Proposition 3.4 can be found in Appendix B.5.

######  Corollary 3.5.

Assume that $\alpha/d\rightarrow 0$, $n\alpha^{2}/d\rightarrow+\infty$ and
$\sigma\sqrt{d}/(\alpha\sqrt{n})\ll a\leq 2\sigma$. The selector
$\hat{\eta}^{+}$ defined by (17) with $\tau=p(2)a/\sigma$ satisfies for $n,d$
large enough

$\sup_{\theta\in\Theta_{d}^{+}(s,a)}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}^{+}(Z^{1},\ldots,Z^{d}))-\eta|\leq\frac{d}{s}\exp\left(-\frac{n(e^{\alpha}-1)^{2}p^{2}(2)a^{2}}{2\sigma^{2}(e^{\alpha}+1)^{2}K_{d}^{2}}\right).$

In particular, if $\alpha\in(0,1]$, if $n\alpha^{2}/d\rightarrow+\infty$ with
$n\alpha^{2}/d\gg\log(d)$ then it holds

$\sup_{\theta\in\Theta_{d}^{+}(s,a)}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}^{+}(Z^{1},\ldots,Z^{d}))-\eta|\rightarrow 0,$

for all $a$ satisfying $\sigma\sqrt{\frac{d}{n\alpha^{2}}}\sqrt{\log(d/s)}\ll
a\leq 2\sigma$; and also

$\sup_{\theta\in\Theta_{d}^{+}(s,a)}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}^{+}(Z^{1},\ldots,Z^{d}))-\eta|\rightarrow 0,$

for all $a$ satisfying $\sigma\sqrt{\frac{d}{n\alpha^{2}}}\sqrt{\log(d)}\ll
a\leq 2\sigma$.

The first statement in Corollary 3.5 is a direct consequence of Proposition
3.4. The second statement is a direct consequence of the first one where we
have used $(e^{\alpha}-1)^{2}/(e^{\alpha}+1)^{2}\geq 0.2\alpha^{2}$ for
$\alpha\in(0,1]$ and $K_{d}\leq C\sqrt{d}$ for $d$ large enough. In the next
subsection, we complement these results with a lower bound. This will enable
us to exhibit a value $a^{*}$ such that exact recovery is impossible for all
$a\leq a^{*}$ and possible for $a\gg a^{*}$ under the assumptions
$\alpha\in(0,1]$ and $n\alpha^{2}/d\rightarrow\infty$ with
$n\alpha^{2}/d\gg\log(d)$.

###  3.3 Lower bound

Recall that $P_{0}$ denotes the distribution of $\sigma\xi_{1}$ and $P_{a}$
that of $a+\sigma\xi_{1}$ and denote by $\chi^{2}(P_{0},P_{a})$ the chi-square
discrepancy between the two distributions.

######  Proposition 3.6.

For any $a>0$ such that $\chi^{2}(P_{0},P_{a})<\infty$, $\alpha>0$, $d\geq 4$,
$1\leq s\leq d$, $n\geq 1$, we have

$\inf_{Q\in\mathcal{Q}_{\alpha}}\inf_{\hat{\eta}\in\mathcal{T}}\sup_{\theta\in\Theta_{d}^{+}(s,a)}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|\geq\frac{1}{4}\left(1-\frac{2n(e^{\alpha}-1)^{2}}{d\log(d)}\chi^{2}(P_{0},P_{a})\right).$

Assume now that the measure $P^{\xi_{1}}$ of the noise coordinates is strongly
log-concave, with density $p=\exp(-\phi)$, with a potential $\phi$ that has a
curvature bounded from above by a constant $c_{+}$ as in (3). Then

$\chi^{2}\left(P_{0},P_{a}\right)\leq\exp\left(c_{+}\left(\frac{a}{\sigma}\right)^{2}\right)-1.$
(19)

Note that Inequality (19) is sharp in the sense that in the Gaussian case,
$c_{+}=1$ holds and Inequality (31) turns out to be an equality. Note also
that log-concavity is actually not needed in Proposition 3.6, since we only
require an upper bound on the curvature of the potential $\phi$.

The proof of Proposition 3.6 is based on a private version of Fano’s method,
see Proposition 2 in [19]. It can be found in Section B.6 of the Appendix.
Using that $(e^{\alpha}-1)^{2}\leq 4\alpha^{2}$ for $\alpha\in(0,1)$ and
$\exp(c_{+}x^{2})-1\leq Lx^{2}$ for $0\leq x\leq 2$ and some constant $L$ only
depending on $c_{+}$ (e.g. $L=(\exp(2c_{+})-1)/2$), Proposition 3.6
immediately shows the following.

######  Corollary 3.7.

Let $\alpha\in(0,1)$. If $n\alpha^{2}/(d\log d)\leq C/(32L)$ for some constant
$C\in(0,1)$ then it holds

$\inf_{Q\in\mathcal{Q}_{\alpha}}\inf_{\hat{\eta}\in\mathcal{T}}\sup_{\theta\in\Theta_{d}^{+}(s,a)}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|\geq\frac{1}{4}\left(1-C\right)>0,$

for all $a\leq 2\sigma$.

This shows that exact recovery is impossible for all $a\leq 2\sigma$ if
$n\alpha^{2}/(d\log d)\leq C/(32L)$ for some constant $C\in(0,1)$. Proposition
3.6 also implies that exact recovery is impossible if
$a\leq\sigma\sqrt{\log(1+Cd\log d/(8n\alpha^{2}))/c_{+}}$ for some constant
$C\in(0,1)$. However, unlike the coordinate local case, the lower bound
provided by Proposition 3.6 does not allow us to say that exact recovery is
also impossible for $a\geq\max\\{2\sigma,\sigma\sqrt{\log(1+Cd\log
d/(8n\alpha^{2}))/c_{+}}\\}$ when $n\alpha^{2}/(d\log d)$ is bounded from
above. The following corollary is also a direct consequence of Proposition
3.6. It shows that when $n\alpha^{2}/(d\log d)\rightarrow\infty$, exact
recovery is still impossible if $a$ is too small.

######  Corollary 3.8.

If $\alpha\in(0,1)$, $n\alpha^{2}/d\rightarrow+\infty$ with
$n\alpha^{2}/d\gg\log d$ and $a\leq(\sigma/(16L))\sqrt{d\log d/(n\alpha^{2})}$
it holds

$\liminf_{d\rightarrow+\infty}\inf_{Q\in\mathcal{Q}_{\alpha}}\inf_{\hat{\eta}\in\mathcal{T}}\sup_{\theta\in\Theta_{d}^{+}(s,a)}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|\geq\frac{1}{8}.$

The lower bound of Proposition 3.6 combined with the upper bounds of
Subsection 3.2 exhibit a phase transition at the value $a^{*}$ (up to a
logarithmic factor) such that exact recovery is impossible for all $a\leq
a^{*}$ and possible for $a\gg a^{*}$ under the assumptions $\alpha\in(0,1]$
and $n\alpha^{2}/d\rightarrow\infty$ with $n\alpha^{2}/d\gg\log(d)$.
Precisely, set

$a^{*}=a^{*}(n,\alpha,d,\sigma)=\frac{\sigma}{16L}\sqrt{\frac{d\log
d}{n\alpha^{2}}},$

where we recall that $L=(\exp(2c_{+})-1)/2$. Proposition 3.6 combined with
Corollary 3.5 and Proposition 3.3 give the following result.

######  Corollary 3.9.

Assume that $\alpha\in(0,1]$ and $n\alpha^{2}/d\rightarrow+\infty$ with
$n\alpha^{2}/d\gg\log(d)$. Then, exact recovery is impossible for all $a\leq
a^{*}$ and is possible for all $a\gg a^{*}.$

Note that Proposition 3.6 does not allow us to obtain impossibility results
for almost full recovery in the regime $n\alpha^{2}/(d\log d)\gg 1$. Its proof
relies on a private Fano’s method (Proposition 2 in [19]) applied with the
family of distributions
$\left\\{\mathcal{N}(a\omega_{i},\sigma^{2}I_{d}),i=1,\ldots,d\right\\}$ where
$\omega_{i}\in\\{0,1\\}^{d}$ is defined by $\omega_{ij}=\delta_{ij}$ and
$\delta$ is the Kronecker delta. The same proof with $\omega_{i}$ defined by
$\omega_{ij}=1$ if $j\in\llbracket(i-1)s+1,is\rrbracket$ and $\omega_{ij}=0$
otherwise for $i=1,\ldots\lfloor d/s\rfloor$, provides the following lower
bound.

######  Proposition 3.10.

For any $a>0$ such that $\chi^{2}(P_{0},P_{a})<\infty$, $\alpha>0$, $n\geq 1$.
If $d/s\leq 4$ then we have

$\inf_{Q\in\mathcal{Q}_{\alpha}}\inf_{\hat{\eta}\in\mathcal{T}}\sup_{\theta\in\Theta_{d}^{+}(s,a)}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|\geq\frac{1}{4}\left(1-\frac{2n(e^{\alpha}-1)^{2}}{\lfloor
d/s\rfloor\log(\lfloor d/s\rfloor)}\chi^{2}(P_{0}^{\otimes s},P_{a}^{\otimes
s})\right).$

If the noise has a potential $\phi$ that is two times continuously
differentiable, with curvature bounded from above by a constant $c_{+}$ as in
(3), then it holds $\chi^{2}(P_{0}^{\otimes s},P_{a}^{\otimes s})=\exp(s\cdot
c_{+}a^{2}/\sigma^{2})-1$.

Note that $\chi^{2}(P_{0}^{\otimes s},P_{a}^{\otimes
s})=(\chi^{2}(P_{0},P_{a})+1)^{s}-1$.

However, this bound turns out to be suboptimal in the sense that when it holds
$n\alpha^{2}/d\gg\log(d/s)$ the combination of this bound with upper bounds in
Proposition 3.3 and Corollary 3.5 allows us to exhibit the critical value
$a^{*}$ for almost full recovery only up to a logarithmic factor times the
sparsity $s$. Indeed, on the one hand Proposition 3.3 and Corollary 3.5 prove
that almost full recovery is possible for all
$a\gg\sigma\sqrt{d/(n\alpha^{2})}\sqrt{\log(d/s)}$ in the regime
$n\alpha^{2}/d\gg\log(d/s)$. On the other hand Proposition 3.10 proves that,
in the same regime, almost full recovery is impossible for
$a\lesssim(\sigma/s)\sqrt{d/(n\alpha^{2})}\sqrt{\log(d/s)}$ but does not allow
us to say what happens for
$(\sigma/s)\sqrt{d/(n\alpha^{2})}\sqrt{\log(d/s)}\ll
a\lesssim\sigma\sqrt{d/(n\alpha^{2})}\sqrt{\log(d/s)}$.

| $a\lesssim\frac{\sigma}{s}\sqrt{\frac{\log(d/s)}{Nd}}$ |  $\frac{\sigma}{s}\sqrt{\frac{\log(d/s)}{Nd}}\ll a\lesssim\frac{\sigma}{\sqrt{s}}$ | $a\gg\frac{\sigma}{\sqrt{s}}$
---|---|---|---
$s\frac{Nd}{\log(d/s)}\lesssim 1$ | impossible |  impossible | ?
$s\frac{Nd}{\log(d/s)}\gg 1$ | impossible |  possible, as soon as $a\gg\sigma\sqrt{\frac{\log(d/s)}{Nd}}$ if moreover $Nd\gg\log(d/s)$ | possible
Table 3: Almost full recovery of $\theta$ in either $\Theta^{+}_{d}(s,a)$ or
$\Theta_{d}(s,a)$ in the Coordinate Global case. We have set
$N=n\alpha^{2}/d^{2}$.

##  Appendix A Proofs of Section 2

###  A.1 Some auxiliary results for the proof of the lower bound

The proof of Theorem 2.1 strongly relies on the following result known as the
Bayesian version of the Neyman-Pearson lemma.

######  Theorem A.1 ([29], Problem 3.10).

Let $P_{0}$ and $P_{1}$ be probability distributions possessing densities
$p_{0}$ and $p_{1}$ with respect to a measure $\mu$. Consider the problem of
testing $H_{0}:P=P_{0}$ against $H_{1}:P=P_{1}$, and suppose that known
probabilities $\pi$ and $1-\pi$ can be assigned to $H_{0}$ and $H_{1}$ prior
to the experiment. Then the test $T^{*}$ given by

$T^{*}(X)=I((1-\pi)p_{1}(X)>\pi p_{0}(X))$

is a minimizer of the overall probability of error resulting from the use of a
test $T$,

$\pi\mathbb{E}_{0}[T(X)]+(1-\pi)\mathbb{E}_{1}[1-T(X)].$

The following lemmas are also useful to prove the lower bound.

######  Lemma A.2.

Let $b,c>0$. Let $P$ and $Q$ be two probability measures having densities $p$
and $q$ with respect to some measure $\mu$. It holds

$\int\min\\{bp(x),cq(x)\\}\mathrm{d}\mu(x)\geq\frac{bc}{b+c}\left(\int\sqrt{p(x)q(x)}\mathrm{d}\mu(x)\right)^{2}.$

The case $b=c=1$ can be found in [36] (lemma 2.3). We generalize the proof for
any $b,c>0$.

###### Proof.

The Cauchy-Schwarz inequality yields

$\displaystyle bc\left(\int\sqrt{p(x)q(x)}\mathrm{d}\mu(x)\right)^{2}$
$\displaystyle=\left(\int\sqrt{bp(x)\cdot cq(x)}\mathrm{d}\mu(x)\right)^{2}$
$\displaystyle=\left(\int\sqrt{\min\\{bp(x),cq(x)\\}}\sqrt{\max\\{bp(x),cq(x)\\}}\mathrm{d}\mu(x)\right)^{2}$
$\displaystyle\leq\int\min\\{bp(x),cq(x)\\}\mathrm{d}\mu(x)\int\max\\{bp(x),cq(x)\\}\mathrm{d}\mu(x).$

In order to finish, we use that $\max\\{u,\,v\\}\leq u+v$ and get
$\int\max\\{bp(x),cq(x)\\}\mathrm{d}\mu(x)\leq b\int
p(x)\mathrm{d}\mu(x)+c\int q(x)\mathrm{d}\mu(x)=b+c$. ∎

In the proof of the lower bound, Lemma A.2 will be combined with the following
result whose proof can be found in [36].

######  Lemma A.3.

Let $P$ and $Q$ be two probability measures having densities $p$ and $q$ with
respect to some measure $\mu$. It holds

$\left(\int\sqrt{p(x)q(x)}\mathrm{d}\mu(x)\right)^{2}\geq\exp(-\mathrm{KL}(P,Q)).$

###  A.2 Proof of Theorem 2.1

Let $Q\in\mathcal{Q}_{\alpha}^{CL}$ and let $\hat{\eta}$ be a separable
selector. Since $\hat{\eta}_{j}$ depends only on $(Z^{i}_{j})_{i=1,\ldots,n}$,
it holds

$\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}(Z)-\eta|=\sum_{j=1}^{d}\mathbb{E}_{\otimes_{i=1}^{n}Q^{i}_{j}P_{\theta_{j}}}|\hat{\eta}_{j}(Z^{1}_{j},\ldots,Z^{n}_{j})-\eta_{j}|.$

Following the proof of Theorem 2.2 in [11], we denote by $\Theta^{\prime}$ the
set of all $\theta$ in $\Theta_{d}^{+}(s,a)$ such that exactly $s$ components
of $\theta$ are equal to $a$ and the remaining $d-s$ components are equal to
$0$. Since $\Theta^{\prime}$ is a subset of $\Theta_{d}^{+}(s,a)$, it holds

$\displaystyle\sup_{\theta\in\Theta_{d}^{+}(s,a)}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}(Z)-\eta|$
$\displaystyle\geq\frac{1}{s|\Theta^{\prime}|}\sum_{\theta\in\Theta^{\prime}}\sum_{j=1}^{d}\mathbb{E}_{\otimes_{i=1}^{n}Q^{i}_{j}P_{\theta_{j}}}|\hat{\eta}_{j}(Z^{1}_{j},\ldots,Z^{n}_{j})-\eta_{j}|$
$\displaystyle=\frac{1}{s|\Theta^{\prime}|}\sum_{j=1}^{d}\left(\sum_{\theta\in\Theta^{\prime}:\theta_{j}=0}\mathbb{E}_{\otimes_{i=1}^{n}Q^{i}_{j}P_{0}}(\hat{\eta}_{j})+\sum_{\theta\in\Theta^{\prime}:\theta_{j}=a}\mathbb{E}_{\otimes_{i=1}^{n}Q^{i}_{j}P_{a}}(1-\hat{\eta}_{j})\right)$
$\displaystyle=\frac{1}{s}\sum_{j=1}^{d}\left(\left(1-\frac{s}{d}\right)\mathbb{E}_{\otimes_{i=1}^{n}Q^{i}_{j}P_{0}}(\hat{\eta}_{j})+\frac{s}{d}\mathbb{E}_{\otimes_{i=1}^{n}Q^{i}_{j}P_{a}}(1-\hat{\eta}_{j})\right)$
$\displaystyle\geq\frac{1}{s}\sum_{j=1}^{d}\inf_{T\in[0,1]}\left(\left(1-\frac{s}{d}\right)\mathbb{E}_{\otimes_{i=1}^{n}Q^{i}_{j}P_{0}}(T)+\frac{s}{d}\mathbb{E}_{\otimes_{i=1}^{n}Q^{i}_{j}P_{a}}(1-T)\right).$

Set

$L^{*}_{j}=\inf_{T\in[0,1]}\left(\left(1-\frac{s}{d}\right)\mathbb{E}_{\otimes_{i=1}^{n}Q^{i}_{j}P_{0}}(T)+\frac{s}{d}\mathbb{E}_{\otimes_{i=1}^{n}Q^{i}_{j}P_{a}}(1-T)\right).$

Since $Q^{i}_{j}$ provides $\alpha_{j}$-differential privacy, the channel
probabilities $Q^{i}_{j}(\cdot\mid x)$ have densities $z\mapsto
q^{i}_{j}(z\mid x)$ with respect to some measure $\mu^{i}_{j}$. Therefore,
$dQ^{i}_{j}P_{0}(z)=m^{i}_{j,0}(z)\mathrm{d}\mu^{i}_{j}(z)$, and
$dQ^{i}_{j}P_{a}(z)=m^{i}_{j,a}(z)\mathrm{d}\mu^{i}_{j}(z)$, where
$m^{i}_{j,b}(z)=\int_{\mathbb{R}}q^{i}_{j}(z\mid x)dP_{b}(x)$,
$b\in\\{0,a\\}$. Thus, for $b\in\\{0,a\\}$, it holds

$d(\otimes_{i=1}^{n}Q^{i}_{j}P_{b})(y_{1},\ldots,y_{n})=[\prod_{i=1}^{n}m^{i}_{j,b}(y_{i})]\mathrm{d}\mu_{j}(y_{1},\ldots,y_{n}),$

where $\mu_{j}=\mu^{1}_{j}\otimes\cdots\otimes\mu^{n}_{j}$. According to
Theorem A.1, the infimum $L^{*}_{j}$ is thus attained for $T=T^{*}_{j}$ given
by

$T^{*}_{j}(Y_{1},\ldots,Y_{n})=I\left(\frac{s}{d}\prod_{i=1}^{n}m^{i}_{j,a}(Y_{i})>\left(1-\frac{s}{d}\right)\prod_{i=1}^{n}m^{i}_{j,0}(Y_{i})\right).$

Set
$A_{j}=\\{(y_{1},\ldots,y_{n})\in\mathbb{R}^{n}:\frac{s}{d}\prod_{i=1}^{n}m^{i}_{j,a}(y_{i})>\left(1-\frac{s}{d}\right)\prod_{i=1}^{n}m^{i}_{j,0}(y_{i})\\}$.

$\displaystyle\sup_{\theta\in\Theta_{d}^{+}(s,a)}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}(Z)-\eta|$
$\displaystyle\geq\frac{1}{s}\sum_{j=1}^{d}\left[\left(1-\frac{s}{d}\right)\int_{A_{j}}[\prod_{i=1}^{n}m^{i}_{j,0}(y_{i})]\mathrm{d}\mu_{j}(y_{1},\ldots,y_{n})\right.$
$\displaystyle\hskip
28.45274pt\left.+\frac{s}{d}\int_{A_{j}^{C}}[\prod_{i=1}^{n}m^{i}_{j,a}(y_{i})]\mathrm{d}\mu_{j}(y_{1},\ldots,y_{n})\right]$
$\displaystyle=\frac{1}{s}\sum_{j=1}^{d}\int_{\mathbb{R}^{n}}\min\left\\{\left(1-\frac{s}{d}\right)\prod_{i=1}^{n}m^{i}_{j,0}(y_{i}),\frac{s}{d}\prod_{i=1}^{n}m^{i}_{j,a}(y_{i})\right\\}\mathrm{d}\mu_{j}(y_{1},\ldots,y_{n})$
$\displaystyle\geq\left(1-\frac{s}{d}\right)\cdot\frac{1}{d}\sum_{j=1}^{d}\left(\int_{\mathbb{R}^{n}}\sqrt{\left(\prod_{i=1}^{n}m^{i}_{j,0}(y_{i})\right)\left(\prod_{i=1}^{n}m^{i}_{j,a}(y_{i})\right)}\mathrm{d}\mu_{j}(y_{1},\ldots,y_{n})\right)^{2}$
$\displaystyle\geq\left(1-\frac{s}{d}\right)\cdot\frac{1}{d}\sum_{j=1}^{d}\exp\left(-\mathrm{KL}\left(\otimes_{i=1}^{n}Q^{i}_{j}P_{0},\otimes_{i=1}^{n}Q^{i}_{j}P_{a}\right)\right),$

where the two last inequalities follow from lemma A.2 and lemma A.3. Using the
tensorization property of the Kullback-Leibler divergence we obtain

$\displaystyle\sup_{\theta\in\Theta_{d}^{+}(s,a)}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}(Z)-\eta|$
$\displaystyle\geq\left(1-\frac{s}{d}\right)\cdot\frac{1}{d}\sum_{j=1}^{d}\exp\left(-\sum_{i=1}^{n}\mathrm{KL}\left(Q^{i}_{j}P_{0},Q^{i}_{j}P_{a}\right)\right)$
$\displaystyle\geq\left(1-\frac{s}{d}\right)\cdot\frac{1}{d}\sum_{j=1}^{d}\exp\left(-4n(e^{\alpha/d}-1)^{2}\mathrm{TV}(P_{0},P_{a})^{2}\right)$
$\displaystyle=\left(1-\frac{s}{d}\right)\exp\left(-4n(e^{\alpha/d}-1)^{2}\mathrm{TV}(P_{0},P_{a})^{2}\right),$

where the second inequality is a direct consequence of the strong data
processing inequality in Theorem 1 of [19] showing the contraction property of
privacy:

$\mathrm{KL}(QP_{0},QP_{a})+\mathrm{KL}(QP_{a},QP_{0})\leq(4\wedge
e^{2\alpha/d})(e^{\alpha/d}-1)^{2}TV(P_{0},P_{a})^{2}$

if $Q$ is $\alpha/d-$DP. Since this result holds for all
$Q\in\mathcal{Q}_{\alpha}^{CL}$ and all separable selector $\hat{\eta}$, we
obtain

$\inf_{Q\in\mathcal{Q}_{\alpha}^{CL}}\inf_{\hat{\eta}\in\mathcal{T}}\sup_{\theta\in\Theta_{d}^{+}(s,a)}\frac{1}{s}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|\geq\left(1-\frac{s}{d}\right)\exp\left(-4n(e^{\alpha/d}-1)^{2}\mathrm{TV}(P_{0},P_{a})^{2}\right).$

Note that the $TV$ distance is invariant to a scale parameter, thus
$TV(P_{0},P_{a})$ can be calculated as the $TV$ distance between the
distribution of $\xi_{1}$ and the same one shifted by $a/\sigma$. The
inequality $TV(P_{0},P_{a})\leq 1$, Pinsker’s inequality and Inequality (21)
of Lemma A.4 below, give

$TV(P_{0},P_{a})\leq\sqrt{\frac{\mathrm{KL}(P_{0},P_{a})}{2}}\leq\frac{a\sqrt{c_{+}}}{2\sigma},$

which implies the statement of Theorem 2.1.

######  Lemma A.4.

Consider that the measure $P^{\xi_{1}}$ of the noise coordinates is
$c-$strongly log-concave on $\mathbb{R}$, with density $p=\exp(-\phi)$, the
convex function $\phi$ thus being $c-$strongly convex for some constant $c>0$.
Recall that the measure $P_{0}$ is the distribution of the scaled noise
coordinate $\sigma\xi_{1}$ and that $P_{a}$ is the image of $P_{0}$ by the
translation of $a$. It holds

${\rm KL}(P_{0},P_{a})\geq\frac{ca^{2}}{2\sigma^{2}}.$ (20)

If, on the other hand, we assume that the measure $P^{\xi_{1}}$ has a density
$p=\exp(-\phi)$ converging to zero at infinity, with $\phi$ being two times
continuously differentiable and satisfying Inequality (3) for a constant
$c_{+}>0$, that gives a uniform upper bound of the curvature of $\phi$ by the
constant $c_{+}$, then it holds

${\rm KL}(P_{0},P_{a})\leq\frac{c_{+}a^{2}}{2\sigma^{2}}.$ (21)

If $P^{\xi_{1}}$ is $c-$strongly log-concave and its potential achieves (3)
for a positive constant $c_{+}$, then Inequality (21) holds true.

Note that Lemma A.4 is tight in the sense that if $P_{0}$ is Gaussian with
variance $\sigma^{2}$, then ${\rm KL}(P_{0},P_{a})=a^{2}/(2\sigma^{2})$ and we
have equality in both bounds (20) and (21), with $c=c_{+}=1$.

###### Proof.

Consider first the case of a $c-$strongly log-concave density $p$.By standard
approximation arguments (see for instance [34, Proposition 5.5]), we can
assume without loss of generality that the potential $\phi$ is two times
continuously differentiable. Consequently, $c-$strong convexity of $\phi$ is
equivalent to $\phi^{\prime\prime}(x)\geq c$ for all $x\in\mathbb{R}$. Using
Taylor expansion, this gives that for any $x\in\mathbb{R}$,

$\phi(x-a)\geq\phi(x)-a\phi^{\prime}(x)+c\frac{a^{2}}{2}.$

This gives,

$\displaystyle{\rm KL}(P_{0},P_{a})$
$\displaystyle=\frac{1}{\sigma^{2}}\int_{\mathbb{R}}[\phi(x-a)-\phi(x)]\exp(-\phi(x))dx$
$\displaystyle\geq-\frac{a}{\sigma^{2}}\int_{\mathbb{R}}\phi^{\prime}(x)\exp(-\phi(x))dx+c_{-}\frac{a^{2}}{2\sigma^{2}}\int_{\mathbb{R}}\exp(-\phi(x))dx$
$\displaystyle=c_{-}\frac{a^{2}}{2\sigma^{2}}.$

Hence, (20) is proved. In order to prove (21), just remark that the regularity
of $\phi$ and the upper bound on its curvature yield
$\sup_{x\in\mathbb{R}}\phi^{\prime\prime}(x)\leq c_{+}$. Hence, by Taylor
expansion again,

$\phi(x-a)\leq\phi(x)-a\phi^{\prime}(x)+c_{+}\frac{a^{2}}{2}.$

Analogous computations now give ${\rm KL}(P_{0},P_{a})\leq
c_{+}a^{2}/(2\sigma^{2})$, which is (21).

Finally, if $p$ is strongly log-concave, then it tends to zero at infinity. By
convolution by Gaussians, we can also assume without loss of generality that
$\phi$ is two times continuously differentiable ([34, Proposition 5.5]).
Hence, if in addition $p$ satisfies (3), then it achieves the conditions that
lead to (21). This concludes the proof of Lemma A.4. ∎

###  A.3 Some auxiliary results for the upper bounds

First recall that since the vector $\xi=(\xi_{1},...,\xi_{d})$ is $c$-strongly
log-concave - as it has independent $c$-strongly log-concave coordinates -,
then it achieves the following sub-Gaussian concentration inequality for
Lipschitz functions (see Proposition 2.18 in [28]): for any $L$-Lipschitz
function $F:\mathbb{R}^{d}\rightarrow\mathbb{R}$, and any $r\geq 0$,

$\mathbb{P}(F(\xi)-\mathbb{E}[F(\xi)]\geq r)\leq\exp(-cr^{2}/(2L^{2})).$ (22)

Furthermore, the celebrated Cafarelli’s contraction theorem [14] state that
the Brenier transport map pushing forward a Gaussian distribtion to a strongly
log-concave measure with the same Gaussian factor is a contraction. As a
result, one can derive the following Mill’s type bound for the deviations the
coordinate $\xi_{1}$ ([15], Proposition 2): for any $r>0$,

$\mathbb{P}(|\xi_{1}|\geq r)\leq
2(1-\Phi(\sqrt{c}r))\leq\sqrt{\frac{2}{\pi}}\frac{\exp(-cr^{2}/2)}{\sqrt{c}r},$
(23)

where $\Phi$ is the standard Gaussian cumulative distribution function.
Another useful fact is that, as $\xi_{1}$ is log-concave, it is unimodal (see
[34]) and as $\xi_{1}$ is also symmetric, the maximum of its density
$p(x)=\exp(-\phi_{0}(x))\exp(-cx^{2}/2)$ is attained at its median $0$. Note
that as $\phi_{0}$ is convex and symmetric, the maximum of the function
$\exp(-\phi_{0}(x))$ is also attained at $0$. In addition, by a result of
Bobkov and Ledoux [8] (see also [34] Proposition 5.2), as $0$ is the median of
$\xi_{1}$, it holds $p(0)=\exp(-\phi_{0}(0))\leq
1/(\sqrt{2}\sigma_{\xi_{1}})\leq 1/\sqrt{2}$. Putting things together we
obtain that for any $x\in\mathbb{R}$,

$p(x)\leq\frac{1}{\sqrt{2}}\exp(-cx^{2}/2).$ (24)

######  Lemma A.5.

For all $a\geq 0$ and all $\tau>0$, by Hoeffding inequality we have

$\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[a+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{i}_{j}]\right]\right)\geq\tau\right)\leq\exp(-n\frac{\tau^{2}}{2}).$

We now recall Bernstein’s inequality (cf. [9] Corollary 2.11).

######  Theorem A.6.

Let $Y_{1},\ldots,Y_{n}$ be independent real valued random variables. Assume
that there exist some positive numbers $v$ and $u$ such that

$\sum_{i=1}^{n}\mathbb{E}[Y_{i}^{2}]\leqslant v,$ (25)

and for all integers $m\geqslant 3$

$\sum_{i=1}^{n}\mathbb{E}[|Y_{i}|^{m}]\leqslant\frac{m!}{2}vu^{m-2}.$ (26)

Let $S=\sum_{i=1}^{n}(Y_{i}-\mathbb{E}[Y_{i}])$, then for every positive $t$

$\mathbb{P}\left(S\geqslant
t\right)\leqslant\exp\left(-\frac{t^{2}}{2(v+ut)}\right).$ (27)

Note that if $v\leq ut$ then (27) yields $\mathbb{P}(S\geq
t)\leq\exp(-t/(4u))$. If $ut\leq v$ then (27) yields $\mathbb{P}(S\geq
t)\leq\exp(-t^{2}/4v)$.

We will apply this to get concentration bounds for the average of i.i.d.
Laplace distributed random variables that check the assumptions of the
Theorem.

###  A.4 Proof of Proposition 2.4

It holds

$\displaystyle|\hat{\eta}^{+}-\eta|$
$\displaystyle=\sum_{j:\eta_{j}=0}\hat{\eta}^{+}_{j}+\sum_{j:\eta_{j}=1}(1-\hat{\eta}^{+}_{j})$
$\displaystyle=\sum_{j:\eta_{j}=0}I\left(\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\sigma\xi^{i}_{j}]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}\geq\tau\right)$
$\displaystyle\hskip
42.67912pt+\sum_{j:\eta_{j}=1}I\left(\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}<\tau\right).$

Thus,

$\displaystyle\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]$
$\displaystyle=\frac{1}{s}\sum_{j:\eta_{j}=0}\underbrace{\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\sigma\xi^{i}_{j}]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}\geq\tau\right)}_{=T_{1,j}}$
$\displaystyle\hskip
42.67912pt+\frac{1}{s}\sum_{j:\eta_{j}=1}\underbrace{\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}<\tau\right)}_{=T_{2,j}}.$

We first study $T_{1,j}$. It holds

$T_{1,j}\leq\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\sigma\xi^{i}_{j}]\geq\frac{\tau}{2}\right)+\mathbb{P}\left(\sum_{i=1}^{n}W^{i}_{j}\geq\frac{\tau
n\alpha}{4d}\right).$

Note that $\mathbb{E}\left[\mathrm{sgn}[\sigma\xi_{j}^{i}]\right]=0$ by
symmetry of $\xi_{j}^{i}$. Using Lemma A.5 to bound from above the first term
and Bernstein’s inequality (27) with $v=2n$ and $u=1$ to bound from above the
second term, we obtain if $\tau\alpha/(8d)<1$

$T_{1,j}\leq\exp\left(-\frac{n\tau^{2}}{2^{3}}\right)+\exp\left(-\frac{\tau^{2}n\alpha^{2}}{2^{7}d^{2}}\right).$

Since $x\mapsto\mathrm{sgn}[x]$ is a non-decreasing function and since
$\theta_{j}\geq a$ for all $j$ such that $\eta_{j}=1$, it holds

$\displaystyle T_{2,j}$
$\displaystyle\leq\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[a+\sigma\xi^{i}_{j}]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}<\tau\right)$
$\displaystyle=\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[a+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{i}_{j}]\right]\right)+\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{1}_{j}]\right]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}<\tau\right)$
$\displaystyle=\mathbb{P}\left(-\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[a+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{i}_{j}]\right]\right)-\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}>\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{1}_{j}]\right]-\tau\right).$

As $\xi_{1}$ is symmetric and absolutely continuous, we have

$\displaystyle\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi_{1}]\right]$
$\displaystyle=\mathbb{P}\left(\xi_{1}\geq-\frac{a}{\sigma}\right)-\mathbb{P}\left(\xi_{1}<-\frac{a}{\sigma}\right)$
$\displaystyle=1-2\mathbb{P}\left(\xi_{1}>\frac{a}{\sigma}\right).$

Using (23) we further get

$\displaystyle\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi_{1}]\right]$
$\displaystyle\geq 2\Phi\left(\sqrt{c}\frac{a}{\sigma}\right)-1\geq
2\Phi(2\sqrt{c})-1=:C_{1},$

for $a/\sigma\geq 2$, with $\Phi$ the c.d.f. of the standard Gaussian
distribution.

Thus, if $a\geq 2\sigma$, it holds

$\displaystyle T_{2,j}$
$\displaystyle\leq\mathbb{P}\left(-\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[a+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{i}_{j}]\right]\right)-\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}>C_{1}-\tau\right)$
$\displaystyle\leq\mathbb{P}\left(-\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[a+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{i}_{j}]\right]\right)>\frac{C_{1}-\tau}{2}\right)$
$\displaystyle\hskip
142.26378pt+\mathbb{P}\left(\sum_{i=1}^{n}\left(-W^{i}_{j}\right)>\frac{n\alpha(C_{1}-\tau)}{4d}\right).$

We can now bound from above the first term using lemma A.5 and the second term
using Bernstein’s inequality. This gives, if $C_{1}\geq\tau$ and
$\alpha(C_{1}-\tau)/(8d)\leq 1$

$T_{2,j}\leq\exp\left(-\frac{n(C_{1}-\tau)^{2}}{2^{3}}\right)+\exp\left(-\frac{(C_{1}-\tau)^{2}n\alpha^{2}}{2^{7}d^{2}}\right).$

This ends the proof of (10). We now prove (11). If $\theta\in\Theta_{d}(s,a)$,
we use the estimator $\hat{\eta}$ instead of $\hat{\eta}^{+}$ and it holds

$\displaystyle\mathbb{E}\left[\frac{1}{s}|\hat{\eta}-\eta|\right]$
$\displaystyle=\frac{1}{s}\sum_{j:\eta_{j}=0}\underbrace{\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\sigma\xi^{i}_{j}]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}\right|\geq\tau\right)}_{=\tilde{T}_{1,j}}$
$\displaystyle\hskip
42.67912pt+\frac{1}{s}\sum_{j:\eta_{j}=1}\underbrace{\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}\right|<\tau\right)}_{=\tilde{T}_{2,j}}.$

We first study $\tilde{T}_{1,j}$. It holds

$\displaystyle\tilde{T}_{1,j}$
$\displaystyle\leq\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\sigma\xi^{i}_{j}]\right|+\frac{2d}{n\alpha}\left|\sum_{i=1}^{n}W^{i}_{j}\right|\geq\tau\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\sigma\xi^{i}_{j}]\right|\geq\frac{\tau}{2}\right)+\mathbb{P}\left(\left|\sum_{i=1}^{n}W^{i}_{j}\right|\geq\frac{\tau
n\alpha}{4d}\right)$ $\displaystyle\leq
2\left[\exp\left(-\frac{n\tau^{2}}{2^{3}}\right)+\exp\left(-\frac{\tau^{2}n\alpha^{2}}{2^{7}d^{2}}\right)\right],$

if $\tau\alpha/(8d)<1$, where we have used the two-sided versions of the
concentration inequalities we used to prove (10). We now study
$\tilde{T}_{2,j}$. For all $j$ such that $\eta_{j}=1$, it holds

$\displaystyle\tilde{T}_{2,j}$
$\displaystyle=\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]\right]\right)+\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{1}_{j}]\right]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}\right|<\tau\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{1}_{j}]\right]\right|-\left|\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]\right]\right)+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}\right|<\tau\right)$
$\displaystyle=\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]\right]\right)+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}\right|>\left|\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{1}_{j}]\right]\right|-\tau\right)$

Now, observe that

$\left|\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{1}_{j}]\right]\right|\geq\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{1}_{j}]\right]\geq\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{1}_{j}]\right],$

if $\theta_{j}\geq a$ since $x\mapsto\mathrm{sgn}[x]$ is non-decreasing, and
if $\theta_{j}\leq-a$ we have

$\displaystyle\left|\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{1}_{j}]\right]\right|\geq-\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{1}_{j}]\right]\geq-\mathbb{E}\left[\mathrm{sgn}[-a+\sigma\xi^{1}_{j}]\right]$
$\displaystyle=-\mathbb{E}\left[\mathrm{sgn}[-a-\sigma\xi^{1}_{j}]\right]=\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{1}_{j}]\right],$

where we have used that $x\mapsto\mathrm{sgn}[x]$ is a non-decreasing and odd
function and that $-\xi^{1}_{j}$ and $\xi^{1}_{j}$ have the same distribution.
Moreover, we have seen in the proof of (10) that it holds

$\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi]\right]\geq
2\Phi\left(2\sqrt{c}\right)-1=:C_{1},$

where $\Phi$ denotes the cumulative distribution function of the Gaussian
distribution. Thus, if $a\geq 2\sigma$, it holds
$\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{1}_{j}]\right]\geq C_{1}$ for all
$j$ such that $\eta_{j}=1$, and

$\displaystyle\tilde{T}_{2,j}$
$\displaystyle\leq\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]\right]\right)+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}\right|>C_{1}-\tau\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]\right]\right)\right|+\left|\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}\right|>C_{1}-\tau\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]\right]\right)\right|>\frac{C_{1}-\tau}{2}\right)$
$\displaystyle\hskip
142.26378pt+\mathbb{P}\left(\left|\sum_{i=1}^{n}W^{i}_{j}\right|>\frac{n\alpha(C_{1}-\tau)}{4d}\right).$

Using the two-sided version of the concentration inequalities that we used to
bound $T_{2,j}$ in the proof of (10), we obtain if $C_{1}>\tau$ and
$\alpha(C_{1}-\tau)/(8d)\leq 1$

$\tilde{T}_{2,j}\leq
2\left[\exp\left(-\frac{n(C_{1}-\tau)^{2}}{2^{3}}\right)+\exp\left(-\frac{(C_{1}-\tau)^{2}n\alpha^{2}}{2^{7}d^{2}}\right)\right].$

This ends the proof of (11).

###  A.5 Proof of Corollary 2.5

Let us prove (12). Note that if the assumptions of Corollary 2.5 are
satisfied, and if $\tau=C_{1}/2$ then the assumptions of Proposition 2.4 are
also satisfied and for all $a\geq 2\sigma$ we have

$\displaystyle\sup_{\theta\in\Theta}\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]$
$\displaystyle\leq
2\cdot\frac{d}{s}\left[\exp\left(-\frac{C_{1}^{2}n}{2^{5}}\right)+\exp\left(-\frac{C_{1}^{2}n\alpha^{2}}{2^{9}d^{2}}\right)\right]$
$\displaystyle=2\left\\{\exp\left(\log\left(\frac{d}{s}\right)-\frac{C_{1}^{2}n}{2^{5}}\right)+\exp\left(\log\left(\frac{d}{s}\right)-\frac{C_{1}^{2}n\alpha^{2}}{2^{9}d^{2}}\right)\right\\}$
$\displaystyle=2\exp\left(-\frac{n\alpha^{2}}{d^{2}}\left[\frac{C_{1}^{2}d^{2}}{2^{5}\alpha^{2}}-\frac{\log(d/s)}{n\alpha^{2}/d^{2}}\right]\right)$
$\displaystyle+2\exp\left(-\frac{n\alpha^{2}}{d^{2}}\left[\frac{C_{1}^{2}}{2^{9}}-\frac{\log(d/s)}{n\alpha^{2}/d^{2}}\right]\right).$

The two terms appearing in the last inequality both tend to $0$ as
$d\rightarrow+\infty$ under the assumptions of Corollary 2.5, which gives
(12). The proof of (13) is similar.

###  A.6 Proof of Proposition 2.6

The beginning of the proof is similar to the proof of Proposition 2.4. It
holds

$\displaystyle\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]$
$\displaystyle=\frac{1}{s}\sum_{j:\eta_{j}=0}\underbrace{\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\sigma\xi^{i}_{j}]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}\geq\tau\right)}_{=T_{1,j}}$
$\displaystyle\hskip
42.67912pt+\frac{1}{s}\sum_{j:\eta_{j}=1}\underbrace{\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\mathrm{sgn}[\theta_{j}+\sigma\xi^{i}_{j}]+\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}<\tau\right)}_{=T_{2,j}},$

and we have

$T_{1,j}\leq\exp\left(-\frac{n\tau^{2}}{2^{3}}\right)+\exp\left(-\frac{\tau^{2}n\alpha^{2}}{2^{7}d^{2}}\right)$

if $\tau\alpha/(8d)<1$, and

$T_{2,j}\leq\mathbb{P}\left(-\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[a+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{i}_{j}]\right]\right)-\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}>\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{1}_{j}]\right]-\tau\right).$

Now, we bound from below $\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi]\right]$ in
a different way than in the proof of Proposition 2.4 by the tighter bound:

$\displaystyle\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi_{1}]\right]$
$\displaystyle=2\mathbb{P}(0<\xi_{1}\leq\frac{a}{\sigma})\geq
2\frac{a}{\sigma}p(\frac{a}{\sigma})\geq 2\frac{a}{\sigma}p(2),$

for $a/\sigma<2$, as the pdf $p$ of $\xi_{1}$ is $c-$strongly log-concave and
symmetric and thus uni-modal at 0 and decreasing on $(0,\infty)$.

Thus,

$\displaystyle T_{2,j}$
$\displaystyle\leq\mathbb{P}\left(-\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[a+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{i}_{j}]\right]\right)-\frac{2d}{n\alpha}\sum_{i=1}^{n}W^{i}_{j}>2\frac{a}{\sigma}p(2)-\tau\right)$
$\displaystyle\leq\mathbb{P}\left(-\frac{1}{n}\sum_{i=1}^{n}\left(\mathrm{sgn}[a+\sigma\xi^{i}_{j}]-\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{i}_{j}]\right]\right)>\frac{a}{\sigma}p(2)-\frac{\tau}{2}\right)$
$\displaystyle\hskip
142.26378pt+\mathbb{P}\left(\sum_{i=1}^{n}\left(-W^{i}_{j}\right)>\frac{n\alpha(a/\sigma
p(2)-\tau/2)}{2d}\right).$

We can now bound from above the first term using lemma A.5 and the second term
using Bernstein’s inequality. This gives, if $\tau<2a/\sigma p(2)$ and
$\alpha(a/\sigma p(2)-\tau/2)/(4d)\leq 1$

$T_{2,j}\leq\exp\left(-\frac{n(a/\sigma
p(2)-\tau/2)^{2}}{2^{3}}\right)+\exp\left(-\frac{(a/\sigma
p(2)-\tau/2)^{2}n\alpha^{2}}{2^{5}d^{2}}\right).$

###  A.7 Proof of Corollary 2.7

Let prove (14). The chosen value of $\tau=a/\sigma\cdot p(2)$ satisfies the
assumptions of Proposition 2.6 for $d$ large enough and yield

$\displaystyle\sup_{\theta\in\Theta_{d}^{+}(s,a)}\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]$
$\displaystyle\leq\frac{d}{s}\left[\exp\left(-\frac{na^{2}}{2^{3}\sigma^{2}}p^{2}(2)\right)+\exp\left(-\frac{n\alpha^{2}a^{2}}{2^{7}\sigma^{2}d^{2}}p^{2}(2)\right)\right]$
$\displaystyle=\exp\left(\log\left(\frac{d}{s}\right)-\frac{na^{2}}{2^{3}\sigma^{2}}p^{2}(2)\right)+\exp\left(\log\left(\frac{d}{s}\right)-\frac{n\alpha^{2}a^{2}}{2^{7}\sigma^{2}d^{2}}p^{2}(2)\right)$
$\displaystyle\leq
2\exp\left(\log\left(\frac{d}{s}\right)-\frac{n\alpha^{2}a^{2}}{2^{7}\sigma^{2}d^{2}}\right).$

Conclude using that $a\gg\sigma d/\sqrt{n\alpha^{2}}\sqrt{\log(d/s)}$. The
proof of (15) is similar.

##  Appendix B Proofs of Section 3

###  B.1 Proof of Proposition 3.1

Note that it is sufficient to prove that $\tilde{Z}^{i}$ is an $\alpha$-LDP
view of $X^{i}$. Indeed, if $\tilde{Z}^{i}$ is an $\alpha$-LDP view of $X^{i}$
then it holds for all $z\in\mathcal{Z}$ and $x,x^{\prime}\in\mathbb{R}^{d}$
(we omit the superscript $i$)

$\displaystyle\frac{\mathbb{P}\left(Z=z\mid
X=x\right)}{\mathbb{P}\left(Z=z\mid X=x^{\prime}\right)}$
$\displaystyle=\frac{\sum_{\tilde{z}\in\\{-B,B\\}^{d}}\mathbb{P}\left(Z=z\mid\tilde{Z}=\tilde{z},X=x\right)\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x\right)}{\sum_{\tilde{z}\in\\{-B,B\\}^{d}}\mathbb{P}\left(Z=z\mid\tilde{Z}=\tilde{z},X=x^{\prime}\right)\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x^{\prime}\right)}$
$\displaystyle=\frac{\sum_{\tilde{z}\in\\{-B,B\\}^{d}}\mathbb{P}\left(Z=z\mid\tilde{Z}=\tilde{z}\right)\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x\right)}{\sum_{\tilde{z}\in\\{-B,B\\}^{d}}\mathbb{P}\left(Z=z\mid\tilde{Z}=\tilde{z}\right)\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x^{\prime}\right)}$ $\displaystyle\leq e^{\alpha},$

where we have used that $Z$ is independent from $X$ conditionally to
$\tilde{Z}$ and the fact that $\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x\right)\leq e^{\alpha}\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x^{\prime}\right)$ for all $\tilde{z}\in\\{-B,B\\}^{d}$ if $\tilde{Z}$ is an
$\alpha$-LDP view of $X$. So, let’s prove that $\tilde{Z}^{i}$ is an
$\alpha$-LDP view of $X^{i}$. In what follows, we omit once again the
superscript $i$. We have to prove that for all $\tilde{z}\in\\{-B,B\\}^{d}$
and all $x,x^{\prime}\in\mathbb{R}^{d}$ it holds

$\frac{\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x\right)}{\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid X=x^{\prime}\right)}\leq
e^{\alpha}.$

Let $\tilde{z}\in\\{-B,B\\}^{d}$ and $x\in\mathbb{R}^{d}$. It holds

$\displaystyle\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid X=x\right)$
$\displaystyle=\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x,\tilde{X}=\tilde{x}\right)\cdot\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)$
$\displaystyle=\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid\tilde{X}=\tilde{x}\right)\cdot\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right),$

and since $Y$ and $\tilde{X}$ are independent we have

$\displaystyle\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid\tilde{X}=\tilde{x}\right)$
$\displaystyle=\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid\tilde{X}=\tilde{x},Y=1\right)\cdot\mathbb{P}\left(Y=1\right)$
$\displaystyle\hskip
28.45274pt+\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid\tilde{X}=\tilde{x},Y=0\right)\cdot\mathbb{P}\left(Y=0\right)$
$\displaystyle=\pi_{\alpha}\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid\tilde{X}=\tilde{x},Y=1\right)+(1-\pi_{\alpha})\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid\tilde{X}=\tilde{x},Y=0\right).$

Moreover, since for $\tilde{x}\in\\{-1,1\\}^{d}$

$\mathrm{Card}\left(\left\\{\tilde{z}\in\left\\{-B,B\right\\}^{d}\,\mid\,\langle\tilde{z},\tilde{x}\rangle>0\text{
or }(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=B\tilde{x}_{1})\right\\}\right)\\\
=\mathrm{Card}\left(\left\\{\tilde{z}\in\left\\{-B,B\right\\}^{d}\,\mid\,\langle\tilde{z},\tilde{x}\rangle<0\text{
or }(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=-B\tilde{x}_{1})\right\\}\right)=2^{d-1},$

it holds

$\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid\tilde{X}=\tilde{x},Y=1\right)=\left\\{\begin{array}[]{ll}0&\text{
if }\langle\tilde{z},\tilde{x}\rangle<0\text{ or
}\left(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=-B\tilde{x}_{1}\right)\\\ \frac{1}{2^{d-1}}&\text{ if
}\langle\tilde{z},\tilde{x}\rangle>0\text{ or
}\left(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=B\tilde{x}_{1}\right),\end{array}\right.$

and

$\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid\tilde{X}=\tilde{x},Y=0\right)=\left\\{\begin{array}[]{ll}\frac{1}{2^{d-1}}&\text{
if }\langle\tilde{z},\tilde{x}\rangle<0\text{ or
}\left(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=-B\tilde{x}_{1}\right)\\\ 0&\text{ if
}\langle\tilde{z},\tilde{x}\rangle>0\text{ or
}\left(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=B\tilde{x}_{1}\right).\end{array}\right.$

We thus have

$\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid\tilde{X}=\tilde{x}\right)=\left\\{\begin{array}[]{ll}\frac{1-\pi_{\alpha}}{2^{d-1}}&\text{
if }\langle\tilde{z},\tilde{x}\rangle<0\text{ or
}\left(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=-B\tilde{x}_{1}\right)\\\ \frac{\pi_{\alpha}}{2^{d-1}}&\text{
if }\langle\tilde{z},\tilde{x}\rangle>0\text{ or
}\left(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=B\tilde{x}_{1}\right),\end{array}\right.$

and, if we set

$A_{\tilde{z}}=\left\\{\tilde{x}\in\\{-1,1\\}^{d}:\langle\tilde{z},\tilde{x}\rangle>0\text{
or }\left(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=B\tilde{x}_{1}\right)\right\\}$

and

$C_{\tilde{z}}=\left\\{\tilde{x}\in\\{-1,1\\}^{d}:\langle\tilde{z},\tilde{x}\rangle<0\text{
or }\left(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=-B\tilde{x}_{1}\right)\right\\},$

we obtain

$\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x\right)=\frac{\pi_{\alpha}}{2^{d-1}}\sum_{\tilde{x}\in
A_{\tilde{z}}}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)+\frac{1-\pi_{\alpha}}{2^{d-1}}\sum_{\tilde{x}\in
C_{\tilde{z}}}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid X=x\right).$

Consequently, it holds for all $\tilde{z}\in\\{-B,B\\}^{d}$ and all
$x\in\mathbb{R}^{d}$,

$\frac{\min\\{\pi_{\alpha},1-\pi_{\alpha}\\}}{2^{d-1}}\leq\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x\right)\leq\frac{\max\\{\pi_{\alpha},1-\pi_{\alpha}\\}}{2^{d-1}},$

where we have used that $A_{\tilde{z}}\sqcup C_{\tilde{z}}=\\{-1,1\\}^{d}$ and
$\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)=1$. We finally obtain for all $\tilde{z}\in\\{-B,B\\}^{d}$ and all
$x,x^{\prime}\in\mathbb{R}^{d}$,

$\frac{\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x\right)}{\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid
X=x^{\prime}\right)}\leq\frac{\max\\{\pi_{\alpha},1-\pi_{\alpha}\\}}{\min\\{\pi_{\alpha},1-\pi_{\alpha}\\}}=\frac{\pi_{\alpha}}{1-\pi_{\alpha}}=e^{\alpha}.$

###  B.2 Proof of Proposition 3.2

Let $x\in\mathbb{R}^{d}$. We first compute $\mathbb{E}\left[\tilde{Z}\mid
X=x\right]$. It holds

$\displaystyle\mathbb{E}\left[\tilde{Z}\mid X=x\right]$
$\displaystyle=\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)\cdot\mathbb{E}\left[\tilde{Z}\mid X=x,\tilde{X}=\tilde{x}\right]$
$\displaystyle=\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)\cdot\mathbb{E}\left[\tilde{Z}\mid\tilde{X}=\tilde{x}\right],$

and since $Y$ and $\tilde{X}$ are independent we have

$\displaystyle\mathbb{E}\left[\tilde{Z}\mid\tilde{X}=\tilde{x}\right]$
$\displaystyle=\mathbb{P}\left(Y=1\right)\cdot\mathbb{E}\left[\tilde{Z}\mid\tilde{X}=\tilde{x},Y=1\right]+\mathbb{P}\left(Y=0\right)\cdot\mathbb{E}\left[\tilde{Z}\mid\tilde{X}=\tilde{x},Y=0\right]$
$\displaystyle=\pi_{\alpha}\mathbb{E}\left[\tilde{Z}\mid\tilde{X}=\tilde{x},Y=1\right]+(1-\pi_{\alpha})\mathbb{E}\left[\tilde{Z}=z\mid\tilde{X}=\tilde{x},Y=0\right].$

Define

$\displaystyle
A_{\tilde{x}}:=\left\\{\tilde{z}\in\left\\{-B,B\right\\}^{d}\,\mid\,\langle\tilde{z},\tilde{x}\rangle>0\text{
or }\left(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=B\tilde{x}_{1}\right)\right\\},$ $\displaystyle
C_{\tilde{x}}:=\left\\{\tilde{z}\in\left\\{-B,B\right\\}^{d}\,\mid\,\langle\tilde{z},\tilde{x}\rangle<0\text{
or }\left(\langle\tilde{z},\tilde{x}\rangle=0\text{ and
}\tilde{z}_{1}=-B\tilde{x}_{1}\right)\right\\}.$

Conditionnally on $\left\\{\tilde{X}=\tilde{x},Y=1\right\\}$, it holds
$Z\sim\mathcal{U}\left(A_{\tilde{x}}\right)$. Thus,

$\displaystyle\mathbb{E}\left[\tilde{Z}\mid\tilde{X}=\tilde{x},Y=1\right]=\sum_{\tilde{z}\in
A_{\tilde{x}}}\mathbb{P}\left(\tilde{Z}=\tilde{z}\mid\tilde{X}=\tilde{x},Y=1\right)\tilde{z}=\frac{1}{\mathrm{Card}(A_{\tilde{x}})}\sum_{\tilde{z}\in
A_{\tilde{x}}}\tilde{z}.$

Similarly,

$\displaystyle\mathbb{E}\left[\tilde{Z}\mid\tilde{X}=\tilde{x},Y=0\right]$
$\displaystyle=\frac{1}{\mathrm{Card}(C_{\tilde{x}})}\sum_{\tilde{z}\in
C_{\tilde{x}}}\tilde{z}=\frac{1}{\mathrm{Card}(C_{\tilde{x}})}\sum_{\tilde{z}\in
A_{\tilde{x}}}(-\tilde{z})$
$\displaystyle=-\mathbb{E}\left[\tilde{Z}\mid\tilde{X}=\tilde{x},Y=1\right],$

where we have used
$\mathrm{Card}(C_{\tilde{x}})=\mathrm{Card}(A_{\tilde{x}})$. We thus obtain

$\mathbb{E}\left[\tilde{Z}\mid\tilde{X}=\tilde{x}\right]=\frac{2\pi_{\alpha}-1}{\mathrm{Card}(A_{\tilde{x}})}\sum_{\tilde{z}\in
A_{\tilde{x}}}\tilde{z},$

and, using that $\mathrm{Card}(A_{\tilde{x}})=2^{d-1}$ for all
$\tilde{x}\in\\{-1,1\\}^{d}$ we obtain

$\mathbb{E}\left[\tilde{Z}\mid
X=x\right]=\frac{2\pi_{\alpha}-1}{2^{d-1}}\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\left[\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)\cdot\sum_{\tilde{z}\in A_{\tilde{x}}}\tilde{z}\right].$

We now compute $\sum_{\tilde{z}\in A_{\tilde{x}}}\tilde{z}$ for all
$\tilde{x}\in\\{-1,1\\}^{d}$. Note that for $\tilde{z}\in\\{-B,B\\}^{d}$ and
$\tilde{x}\in\\{-1,1\\}^{d}$, $\langle\tilde{z},\tilde{x}\rangle$ is a sum of
$d$ terms, each equal to $-B$ or $B$. If $a$ denotes the number of elements of
this sum equal to $B$ and $b$ denotes the number of elements of this sum equal
to $-B$, then it holds $a+b=d$ and $\langle\tilde{z},\tilde{x}\rangle=aB-
bB=B(d-2b)$. Thus we can only have $\langle\tilde{z},\tilde{x}\rangle=kB$,
with $k\in\llbracket-d,d\rrbracket$ and $|k|$ has the same parity as $d$. We
thus have

$\sum_{\tilde{z}\in
A_{\tilde{x}}}\tilde{z}=\sum_{p=0}^{(d-1)/2}\sum_{\\{\tilde{z}\in\\{-B,B\\}^{d}:\langle\tilde{z},\tilde{x}\rangle=(2p+1)B\\}}z,$
(28)

if $d$ is odd, and

$\sum_{\tilde{z}\in
A_{\tilde{x}}}\tilde{z}=\sum_{p=1}^{d/2}\displaystyle\sum_{\begin{subarray}{c}\tilde{z}\in\\{-B,B\\}^{d}:\\\
\langle\tilde{z},\tilde{x}\rangle=2p\cdot
B\end{subarray}}\tilde{z}+\sum_{\begin{subarray}{c}\tilde{z}\in\\{-B,B\\}^{d}:\\\
\langle\tilde{z},\tilde{x}\rangle=0\\\
\tilde{z}_{1}=B\tilde{x}_{1}\end{subarray}}\tilde{z},$ (29)

if $d$ is even. Now, observe that for all $\tilde{x}\in\\{-1,1\\}^{d}$, for
all $j\in\llbracket 1,d\rrbracket$ and for all $k\in\\{0,\ldots,d\\}$ with the
same parity as $d$, it holds

$\sum_{\begin{subarray}{c}\tilde{z}\in\\{-B,B\\}^{d}:\\\
\langle\tilde{z},\tilde{x}\rangle=kB\end{subarray}}\tilde{z}_{j}=B\left[\binom{d-1}{\frac{d+k}{2}-1}-\binom{d-1}{\frac{d+k}{2}}\right]\tilde{x}_{j}.$
(30)

Indeed, for all $\tilde{z}\in\\{-B,B\\}^{d}$, for all
$\tilde{x}\in\\{-1,1\\}^{d}$, and for all $k\in\\{0,\ldots,d\\}$ with the same
parity as $d$, it holds

$\langle\tilde{z},\tilde{x}\rangle=k\cdot
B\iff\left\\{\begin{array}[]{ll}\tilde{z}_{j}=B\tilde{x}_{j}&\text{ for
$\frac{d+k}{2}$ elements }j\in\llbracket 1,d\rrbracket\\\
\tilde{z}_{j}=-B\tilde{x}_{j}&\text{ for $\frac{d-k}{2}$ elements
}j\in\llbracket 1,d\rrbracket.\end{array}\right.$

Setting
$D_{k,\tilde{x}}=\\{\tilde{z}\in\\{-B,B\\}^{d}:\langle\tilde{z},\tilde{x}\rangle=k\cdot
B\\}$, it thus holds

$\displaystyle\sum_{\tilde{z}\in D_{k,\tilde{x}}}\tilde{z}_{j}$
$\displaystyle=\sum_{\tilde{z}\in
D_{k,\tilde{x}}}B\tilde{x}_{j}\mathds{1}\left(\tilde{z}_{j}=B\tilde{x}_{j}\right)-\sum_{z\in
D_{k,\tilde{x}}}B\tilde{x}_{j}\mathds{1}\left(\tilde{z}_{j}=-B\tilde{x}_{j}\right)$
$\displaystyle=B\left[\mathrm{Card}\left(\tilde{z}\in
D_{k,\tilde{x}}:\tilde{z}_{j}=B\tilde{x}_{j}\right)-\mathrm{Card}\left(\tilde{z}\in
D_{k,\tilde{x}}:\tilde{z}_{j}=-B\tilde{x}_{j}\right)\right]\tilde{x}_{j}$
$\displaystyle=B\left[\binom{d-1}{\frac{d+k}{2}-1}-\binom{d-1}{\frac{d+k}{2}}\right]\tilde{x}_{j}.$

We now end the proof of Proposition 3.2 when $d$ is odd. Combining (30) with
(28), we obtain for $d$ odd

$\sum_{z\in A_{\tilde{x}}}\tilde{z}=B\binom{d-1}{\frac{d-1}{2}}\tilde{x},$

and the choice of $B$ yields

$\displaystyle\mathbb{E}\left[\tilde{Z}\mid X=x\right]$
$\displaystyle=\frac{2\pi_{\alpha}-1}{2^{d-1}}B\binom{d-1}{\frac{d-1}{2}}\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)\cdot\tilde{x}$ $\displaystyle=\mathbb{E}\left[\tilde{X}\mid
X=x\right]$

Since for all $j\in\llbracket 1,d\rrbracket$ it holds

$\mathbb{E}\left[\tilde{X}_{j}\mid X=x\right]=\mathrm{sgn}[x_{j}],$

we obtain for $d$ odd

$\mathbb{E}\left[Z\mid X=x\right]=\mathbb{E}\left[\tilde{Z}\mid
X=x\right]=\mathbb{E}\left[\tilde{X}\mid X=x\right]=f(x),$

which proves Proposition 3.2 when $d$ is odd. From now on, we assume that $d$
is even. Combining (30) with (29), we obtain

$\sum_{\tilde{z}\in
A_{\tilde{x}}}\tilde{z}=B\binom{d-1}{\frac{d}{2}}\tilde{x}+\sum_{\begin{subarray}{c}\tilde{z}\in\\{-B,B\\}^{d}:\\\
\langle\tilde{z},\tilde{x}\rangle=0\\\
\tilde{z}_{1}=B\tilde{x}_{1}\end{subarray}}\tilde{z}.$

Now, observe that for $\tilde{z}\in\\{-B,B\\}^{d}$ and
$\tilde{x}\in\\{-1,1\\}^{d}$ it holds $\langle\tilde{z},\tilde{x}\rangle=0$ if
and only if $\tilde{z}_{j}=B\tilde{x}_{j}$ for exactly $d/2$ subscripts
$j\in\llbracket 1,d\rrbracket$ and $\tilde{z}_{j}=-B\tilde{x}_{j}$ for exactly
$d/2$ subscripts $j\in\llbracket 1,d\rrbracket$. We thus have

$\displaystyle\sum_{\begin{subarray}{c}\tilde{z}\in\\{-B,B\\}^{d}:\\\
\langle\tilde{z},\tilde{x}\rangle=0\\\
\tilde{z}_{1}=B\tilde{x}_{1}\end{subarray}}\tilde{z}_{1}$
$\displaystyle=B\tilde{x}_{1}\cdot\mathrm{Card}\left(\left\\{\tilde{z}\in\\{-B,B\\}^{d}:\langle\tilde{z},\tilde{x}\rangle=0\text{
and }\tilde{z}_{1}=B\tilde{x}_{1}\right\\}\right)$
$\displaystyle=B\binom{d-1}{\frac{d}{2}-1}\tilde{x}_{1},$

and for $j\geq 2$ it holds

$\displaystyle\sum_{\begin{subarray}{c}\tilde{z}\in\\{-B,B\\}^{d}:\\\
\langle\tilde{z},\tilde{x}\rangle=0\\\
\tilde{z}_{1}=B\tilde{x}_{1}\end{subarray}}\tilde{z}_{j}$
$\displaystyle=B\tilde{x}_{j}\left[\mathrm{Card}\left(\left\\{\tilde{z}\in\\{-B,B\\}^{d}:\langle\tilde{z},\tilde{x}\rangle=0,\tilde{z}_{1}=B\tilde{x}_{1},\tilde{z}_{j}=B\tilde{x}_{j}\right\\}\right)\right.$
$\displaystyle\hskip
56.9055pt\left.-\mathrm{Card}\left(\left\\{\tilde{z}\in\\{-B,B\\}^{d}:\langle\tilde{z},\tilde{x}\rangle=0,\tilde{z}_{1}=B\tilde{x}_{1},\tilde{z}_{j}=-B\tilde{x}_{j}\right\\}\right)\right]$
$\displaystyle=B\left[\binom{d-2}{\frac{d}{2}-2}-\binom{d-2}{\frac{d}{2}-1}\right]\tilde{x}_{j}.$

We thus obtain

$\sum_{\tilde{z}\in
A_{\tilde{x}}}\tilde{z}_{j}=\begin{cases}B\binom{d}{\frac{d}{2}}\tilde{x}_{1}&\text{
if }j=1\\\
B\left[\binom{d-1}{\frac{d}{2}}+\binom{d-2}{\frac{d}{2}-2}-\binom{d-2}{\frac{d}{2}-1}\right]\tilde{x}_{j}&\text{
if }j\in\llbracket 2,d\rrbracket\end{cases}.$

The choice

$B=\frac{2^{d-1}}{2\pi_{\alpha}-1}\cdot\frac{(\frac{d}{2}-1)!\frac{d}{2}!}{(d-2)!(d-2)}$

then yields

$\displaystyle\mathbb{E}\left[\tilde{Z}_{j}\mid X=x\right]$
$\displaystyle=\begin{cases}\frac{(2\pi_{\alpha}-1)B}{2^{d-1}}\binom{d}{\frac{d}{2}}\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\tilde{x}_{1}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)&\text{ if }j=1\\\
\frac{(2\pi_{\alpha}-1)B}{2^{d-1}}\cdot\frac{(d-2)!(d-2)}{(\frac{d}{2}-1)!\frac{d}{2}!}\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\tilde{x}_{j}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)&\text{ if }j\in\llbracket 2,d\rrbracket\end{cases}$
$\displaystyle=\begin{cases}\frac{2(d-1)}{d-2}\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\tilde{x}_{1}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)&\text{ if }j=1\\\
\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\tilde{x}_{j}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)&\text{ if }j\in\llbracket 2,d\rrbracket\end{cases}.$

Thus, it holds $\mathbb{E}\left[Z_{j}\mid
X=x\right]=\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)\tilde{x}_{j}$ for all $j\in\llbracket 1,d\rrbracket$, and

$\mathbb{E}[Z\mid
X=x]=\sum_{\tilde{x}\in\\{-1,1\\}^{d}}\mathbb{P}\left(\tilde{X}=\tilde{x}\mid
X=x\right)\tilde{x}=\mathbb{E}\left[\tilde{X}\mid X=x\right]=f(x).$

###  B.3 Asymptotic analysis of the value $K_{d}$ defined in (16)

######  Lemma B.1.

The value $K_{d}$ defined in (16) behaves asymptotically in $d$ as

$K_{d}\underset{d\rightarrow\infty}{\sim}\sqrt{\frac{\pi}{2}}\sqrt{d}.$

In particular, it holds $K_{d}\lesssim\sqrt{d}$ for $d$ large enough.

The proof relies on Stirling’s approximation. We first deal with the case
where $d$ is odd. In this case, Stirling’s approximation yields

$K_{d}=2^{d-1}\frac{\left[\left(\frac{d-1}{2}\right)!\right]^{2}}{(d-1)!}\underset{d\rightarrow\infty}{\sim}2^{d-1}\cdot\pi(d-1)\left(\frac{d-1}{2e}\right)^{d-1}\cdot\left[\sqrt{2\pi(d-1)}\left(\frac{d-1}{e}\right)^{d-1}\right]^{-1}.$

The right-hand side of this asymptotic equivalence is equal to
$\sqrt{\pi/2}\sqrt{d-1}$. We thus obtain
$K_{d}\underset{d\rightarrow\infty}{\sim}\sqrt{\pi/2}\sqrt{d}$.

We now assume that $d$ is even. in this case, Stirling’s approximation yields

$K_{d}=\frac{2^{d-1}(\frac{d}{2}-1)!\frac{d}{2}!}{(d-2)!(d-2)}\underset{d\rightarrow\infty}{\sim}\frac{2^{d-1}}{d-2}\cdot\pi\sqrt{(d-2)d}\left(\frac{d-2}{2e}\right)^{\frac{d}{2}-1}\left(\frac{d}{2e}\right)^{\frac{d}{2}}\cdot\left[\sqrt{2\pi(d-2)}\left(\frac{d-2}{e}\right)^{d-2}\right]^{-1}$

The right-hand side of this asymptotic equivalence is equal to

$\frac{\sqrt{\pi}}{e\sqrt{2}}\sqrt{d}(d-2)^{-\frac{d}{2}}d^{\frac{d}{2}}=\frac{\sqrt{\pi}}{e\sqrt{2}}\sqrt{d}\exp\left(-\frac{d}{2}\log\left(1-\frac{2}{d}\right)\right)\underset{d\rightarrow\infty}{\sim}\sqrt{\frac{\pi}{2}}\sqrt{d},$

which ends the proof.

###  B.4 Proof of Proposition 3.3

The proof is similar to the one we made in the Coordinate Local case
(Proposition 2.4). However, in the Coordinate Global case, for all
$j\in\llbracket 1,d\rrbracket$ the $(Z^{i}_{j})_{i}$ are bounded random
variables, which will enable us to use Hoeffding’s inequality instead of Lemma
A.5 and Bernstein’s inequality.

Writting

$|\hat{\eta}^{+}-\eta|=\sum_{j:\eta_{j}=0}\hat{\eta}^{+}_{j}+\sum_{j:\eta_{j}=1}(1-\hat{\eta}^{+}_{j}),$

we have

$\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]=\frac{1}{s}\sum_{j:\eta_{j}=0}\underbrace{\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}Z^{i}_{j}\geq\tau\right)}_{=T_{1,j}}+\frac{1}{s}\sum_{j:\eta_{j}=1}\underbrace{\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}Z^{i}_{j}<\tau\right)}_{=T_{2,j}}.$

We first study $T_{1,j}$. For $j$ satisfying $\eta_{j}=0$, it holds

$\mathbb{E}\left[Z^{i}_{j}\right]=\mathbb{E}\left[\mathbb{E}\left[Z^{i}_{j}\mid
X^{i}\right]\right]=\mathbb{E}\left[\mathrm{sgn}[X^{i}_{j}]\right]=\mathbb{E}\left[\mathrm{sgn}[\sigma\xi^{i}_{j}]\right]=0,$

where we have used Proposition 3.2 and the fact that the distribution of the
random variable $\xi_{j}^{i}$ is symmetric. Thus, Hoeffding’s inequality
yields

$T_{1,j}=\mathbb{P}\left(\sum_{i=1}^{n}(Z^{i}_{j}-\mathbb{E}[Z^{i}_{j}])\geq
n\tau\right)\leq\exp\left(-\frac{n\tau^{2}}{2B^{2}}\right).$

We now study $T_{2,j}$. Let $j\in\llbracket 1,d\rrbracket$ such that
$\eta_{j}=1$. It holds

$\displaystyle T_{2,j}$
$\displaystyle=\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\left(Z^{i}_{j}-\mathbb{E}\left[Z^{i}_{j}\right]\right)+\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\left[Z^{i}_{j}\right]<\tau\right)$
$\displaystyle=\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\left(-Z^{i}_{j}-\mathbb{E}\left[-Z^{i}_{j}\right]\right)>\mathbb{E}\left[Z^{1}_{j}\right]-\tau\right).$

Proposition 3.2 gives

$\mathbb{E}\left[Z^{1}_{j}\right]=\mathbb{E}\left[\mathrm{sgn}[X^{1}_{j}]\right]=\mathbb{E}\left[\mathrm{sgn}[\theta_{j}+\sigma\xi_{j}^{1}]\right]\geq\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi_{j}^{1}]\right],$

and we have proved in Appendix A.4 that it holds

$\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi_{1}]\right]\geq
2\Phi\left(\sqrt{c}\frac{a}{\sigma}\right)-1,$

where $\Phi$ denotes the standard Gaussian cumulative distribution function.
Thus, if $a\geq 2\sigma$, it holds
$\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi^{1}_{j}]\right]\geq C_{1}$ with
$C_{1}=2\Phi(2\sqrt{c})-1$, and

$\displaystyle T_{2,j}$
$\displaystyle\leq\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\left(-Z^{i}_{j}-\mathbb{E}\left[-Z^{i}_{j}\right]\right)>C_{1}-\tau\right)$
$\displaystyle\leq\exp\left(-\frac{n(C_{1}-\tau)^{2}}{2B^{2}}\right)$

according to Hoeffding’s inequality if $C_{1}-\tau>0$. This yields

$\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]\leq\frac{d-|S|}{s}\exp\left(-\frac{n\tau^{2}}{2B^{2}}\right)+\frac{|S|}{s}\exp\left(-\frac{n(C_{1}-\tau)^{2}}{2B^{2}}\right).$

The proof of the second statement of Proposition 3.3 is straightforward.

###  B.5 Proof of Proposition 3.4

The beginning of the proof is similar to the proof of Proposition 3.3. It
holds

$\mathbb{E}\left[\frac{1}{s}|\hat{\eta}^{+}-\eta|\right]=\frac{1}{s}\sum_{j:\eta_{j}=0}\underbrace{\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}Z^{i}_{j}\geq\tau\right)}_{=T_{1,j}}+\frac{1}{s}\sum_{j:\eta_{j}=1}\underbrace{\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}Z^{i}_{j}<\tau\right)}_{=T_{2,j}},$

with

$T_{1,j}\leq\exp\left(-\frac{n\tau^{2}}{2B^{2}}\right),$

and

$T_{2,j}\leq\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\left(-Z^{i}_{j}-\mathbb{E}\left[-Z^{i}_{j}\right]\right)>\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi_{j}^{i}]\right]-\tau\right).$

Moreover, we have proved in Appendix A.6 that
$\mathbb{E}\left[\mathrm{sgn}[a+\sigma\xi_{1}]\right]\geq 2p(2)a/\sigma$ for
$a/\sigma<2$. Thus, if $\tau<2p(2)a/\sigma$, Hoeffding’s inequality yields

$T_{2,j}\leq\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\left(-Z^{i}_{j}-\mathbb{E}\left[-Z^{i}_{j}\right]\right)>\frac{2p(2)a}{\sigma}-\tau\right)\leq\exp\left(-\frac{n(2p(2)a/\sigma-\tau)^{2}}{2B^{2}}\right).$

###  B.6 Proof of Proposition 3.6

For $i=1,\ldots,d$, define the vector $\omega_{i}\in\\{0,1\\}^{d}$ by
$\omega_{i,j}=1$ if $j=i$, $\omega_{i,j}=0$ if $j\neq i$ and define
$P_{\omega_{i}}$ as the multivariate distribution of the random vector
$X=a\omega_{i}+\sigma\xi$. For $i\neq j$ it holds

$|\eta(P_{\omega_{i}})-\eta(P_{\omega_{j}})|=|\omega_{i}-\omega_{j}|=2.$

The private Fano method (Proposition 2 in [19]) thus yields

$\inf_{Q\in\mathcal{Q}_{\alpha}}\inf_{\hat{\eta}\in\mathcal{T}}\sup_{\theta\in\Theta_{d}^{+}(s,a)}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|\geq\frac{1}{2}\left\\{1-\frac{n(e^{\alpha}-1)^{2}}{d\log(d)}\left[\sup_{\gamma\in\mathbb{B}_{\infty}(\mathbb{R}^{d})}\sum_{i=1}^{d}(\varphi_{\omega_{i}}(\gamma))^{2}\right]-\frac{\log(2)}{\log(d)}\right\\},$

with

$\mathbb{B}_{\infty}(\mathbb{R}^{d})=\left\\{\gamma\in
L_{\infty}(\mathbb{R}^{d})\mid\|\gamma\|_{\infty}\leq 1\right\\},$
$\varphi_{\omega_{i}}(\gamma)=\int_{\mathcal{X}}\gamma(x)(dP_{\omega_{i}}(x)-d\bar{P}(x))=\int_{\mathbb{R}^{d}}\gamma(x)(f_{\omega_{i}}(x)-\bar{f}(x))dx,$

where $f_{\omega_{i}}$ is the density of $P_{\omega_{i}}$ and
$\bar{f}=(1/d)\sum_{i=1}^{d}f_{\omega_{i}}$. We have

$\displaystyle\sum_{i=1}^{d}\left(\varphi_{\omega_{i}}(\gamma)\right)^{2}$
$\displaystyle=\sum_{i=1}^{d}\left(\int_{\mathbb{R}^{d}}\gamma(x)(f_{\omega_{i}}(x)-\bar{f}(x))dx\right)\left(\int_{\mathbb{R}^{d}}\gamma(y)(f_{\omega_{i}}(y)-\bar{f}(y))dy\right)$
$\displaystyle=\int_{\mathbb{R}^{d}}\gamma(x)\left[\int_{\mathbb{R}^{d}}\left(\sum_{i=1}^{d}(f_{\omega_{i}}(x)-\bar{f}(x))(f_{\omega_{i}}(y)-\bar{f}(y))\right)\gamma(y)dy\right]dx.$

Let $\bar{p}$ denote the density of the random vector $\sigma\xi$. If $\gamma$
belongs to $\mathbb{B}_{\infty}(\mathbb{R}^{d})$ then it also belongs to
$L_{2}(\mathbb{R}^{d},dq)$ and, moreover,
$\|\gamma\|_{L_{2}(\mathbb{R}^{d},d\bar{p})}\leq 1$. We can write

$\displaystyle\sum_{i=1}^{d}\left(\varphi_{\omega_{i}}(\gamma)\right)^{2}$
$\displaystyle=\int_{\mathbb{R}^{d}}\gamma(x)\left[\int_{\mathbb{R}^{d}}\left(\sum_{i=1}^{d}\frac{f_{\omega_{i}}(x)-\bar{f}(x)}{\bar{p}(x)}\cdot\frac{f_{\omega_{i}}(y)-\bar{f}(y)}{\bar{p}(y)}\right)\gamma(y)\bar{p}(y)dy\right]\bar{p}(x)dx$
$\displaystyle=\langle\gamma,K\gamma\rangle_{L_{2}(\mathbb{R}^{d},d\bar{p})},$

where

$\begin{array}[]{ccccc}K&:&L_{2}(\mathbb{R}^{d},d\bar{p})&\to&L_{2}(\mathbb{R}^{d},d\bar{p})\\\
&&\gamma&\mapsto&\int_{\mathbb{R}^{d}}\left(\sum_{i=1}^{d}\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}}(\cdot)\cdot\frac{f_{\omega_{i}}(y)-\bar{f}(y)}{\bar{p}(y)}\right)\gamma(y)\bar{p}(y)dy\\\
\end{array}$

For any $\omega\in\\{0,1\\}^{d}$, $f_{\omega}\in
L_{2}(\mathbb{R}^{d},d\bar{p})$. Note that we can rewrite

$K\gamma=\sum_{i=1}^{d}\left[\left\langle\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}},\gamma\right\rangle_{L_{2}(\mathbb{R}^{d},d\bar{p})}\cdot\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}}\right].$

This expression implies that $K$ is an operator of finite rank (it is thus a
compact operator), $K$ is self-adjoint, and $\langle K\gamma,\gamma\rangle\geq
0$ for all $\gamma\in L_{2}(\mathbb{R}^{d},d\bar{p})$. In particular, the last
point implies that the eigenvalues of $K$ are non-negative. We have

$\displaystyle\sup_{\gamma\in\mathbb{B}_{\infty}(\mathbb{R}^{d})}\sum_{i=1}^{d}\left(\varphi_{\omega_{i}}(\gamma)\right)^{2}$
$\displaystyle\leq\sup_{\\{\gamma\in
L_{2}(\mathbb{R}^{d},d\bar{p}):\|\gamma\|_{L_{2}(\mathbb{R}^{d},d\bar{p})}^{2}\leq
1\\}}\langle\gamma,K\gamma\rangle_{L_{2}(\mathbb{R}^{d},d\bar{p})}$
$\displaystyle=\sup_{\\{\gamma\in
L_{2}(\mathbb{R}^{d},d\bar{p}):\|\gamma\|_{L_{2}(\mathbb{R}^{d},d\bar{p})}^{2}=1\\}}\langle\gamma,K\gamma\rangle_{L_{2}(\mathbb{R}^{d},d\bar{p})}$
$\displaystyle=\sup_{\\{\gamma\in
L_{2}(\mathbb{R}^{d},d\bar{p}):\|\gamma\|_{L_{2}(\mathbb{R}^{d},d\bar{p})}^{2}=1\\}}\left|\langle\gamma,K\gamma\rangle_{L_{2}(\mathbb{R}^{d},d\bar{p})}\right|$
$\displaystyle=\|K\|,$

where the last equality follows from the fact that
$\left(L_{2}(\mathbb{R}^{d},d\bar{p}),\langle\cdot,\cdot\rangle_{L_{2}(\mathbb{R}^{d},d\bar{p})}\right)$
is an Hilbert space and $K$ is self-adjoint. Since $K$ is also compact and
since the eigenvalues of $K$ are non-negative it follows

$\sup_{\gamma\in\mathbb{B}_{\infty}(\mathbb{R}^{d})}\sum_{i=1}^{d}\left(\varphi_{\omega_{i}}(\gamma)\right)^{2}\leq\|K\|=\max\\{|\lambda|:\lambda\in
VP(T)\\}=\max\\{\lambda:\lambda\in VP(T)\\},$

where $VP(T)$ is the set of all the eigenvalues of $K$. It remains to compute
this maximum. By definition, $\lambda$ is an eigenvalue of $K$ if $\lambda
I-K$ is not injective. For $\lambda\neq 0$, the Fredholm alternative for
compact self-adjoint operators (see for instance [26]) implies that $\lambda
I-K$ is not injective if and only if $\lambda I-K$ is not surjective. Thus,
the non-zero eigenvalues of $K$ are the values of $\lambda\in\mathbb{R}^{*}$
such that the operator $\lambda I-K$ is not surjective. For
$\lambda\in\mathbb{R}$, let $A_{\lambda}$ be the matrix with coefficients

$(A_{\lambda})_{ij}=\left\langle\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}},\frac{f_{\omega_{j}}-\bar{f}}{\bar{p}}\right\rangle_{L_{2}(\mathbb{R}^{d},d\bar{p})}-\lambda\delta_{ij},\quad
i,j\in\llbracket 1,d\rrbracket,$

where $\delta$ is the Kronecker delta. The following result proves that if
$\lambda$ is a non-zero eigenvalue of $K$ then it holds
$\mathrm{Det}(A_{\lambda})=0$.

######  Lemma B.2.

Let $\lambda\in\mathbb{R}$, $\lambda\neq 0$. If $\mathrm{Det}(A_{\lambda})\neq
0$ then $\lambda I-K$ is surjective.

###### Proof.

To lighten the notation, set
$\langle\cdot,\cdot\rangle_{2,\bar{p}}=\langle\cdot,\cdot\rangle_{L_{2}(\mathbb{R}^{d},d\bar{p})}$.
Let $\lambda\in\mathbb{R}$, $\lambda\neq 0$ and assume that
$\mathrm{Det}(A_{\lambda})\neq 0$. We prove that for all $g\in
L_{2}(\mathbb{R}^{d},d\bar{p})$ there exists $\gamma\in
L_{2}(\mathbb{R}^{d},d\bar{p})$ such that $g=(\lambda I-K)\gamma$. Consider
$g\in L_{2}(\mathbb{R}^{d},d\bar{p})$. Since $\mathrm{Det}(A_{\lambda})\neq
0$, the matrix $A_{\lambda}$ is invertible and for all $v\in\mathbb{R}^{d}$
there exists $\xi\in\mathbb{R}^{d}$ such that $v=A_{\lambda}\xi$. In
particular, for

$v=\left(\left\langle\frac{f_{\omega_{1}}-\bar{f}}{\bar{p}},g\right\rangle_{2,\bar{p}},\ldots,\left\langle\frac{f_{\omega_{d}}-\bar{f}}{\bar{p}},g\right\rangle_{2,\bar{p}}\right)^{T},$

there exists $\xi\in\mathbb{R}^{d}$ such that $v=A_{\lambda}\xi$, that is

$\left\langle\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}},g\right\rangle_{2,\bar{p}}=(A_{\lambda}\xi)_{i}=\sum_{j=1}^{d}\left\langle\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}},\frac{f_{\omega_{j}}-\bar{f}}{\bar{p}}\right\rangle_{2,\bar{p}}\xi_{j}-\lambda\xi_{i}$

for all $i\in\llbracket 1,d\rrbracket$. Define

$\gamma=\frac{1}{\lambda}g-\frac{1}{\lambda}\sum_{j=1}^{d}\xi_{j}\frac{f_{\omega_{j}}-\bar{f}}{\bar{p}}.$

We have

$\displaystyle(\lambda I-K)\gamma$ $\displaystyle=\lambda\gamma-K\gamma$
$\displaystyle=g-\sum_{i=1}^{d}\xi_{i}\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}}-\sum_{i=1}^{d}\left[\left\langle\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}},\gamma\right\rangle_{L_{2}(\mathbb{R}^{d},d\bar{p})}\cdot\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}}\right]$
$\displaystyle=g-\sum_{i=1}^{d}\underbrace{\left[\xi_{i}+\frac{1}{\lambda}\left\langle\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}},g\right\rangle_{2,\bar{p}}-\frac{1}{\lambda}\sum_{j=1}^{d}\xi_{j}\left\langle\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}},\frac{f_{\omega_{j}}-\bar{f}}{\bar{p}}\right\rangle_{2,\bar{p}}\right]}_{=0}\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}}$
$\displaystyle=g,$

which concludes the proof of the Lemma. ∎

We now find the values of $\lambda$ for which we have
$\mathrm{Det}(A_{\lambda})=0$. To do so, we first make explicit the
coefficients of $A_{\lambda}$. It holds

$\displaystyle\left\langle\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}},\frac{f_{\omega_{j}}-\bar{f}}{\bar{p}}\right\rangle_{2,\bar{p}}$
$\displaystyle=\left\langle\frac{f_{\omega_{i}}}{\bar{p}},\frac{f_{\omega_{j}}}{\bar{p}}\right\rangle_{2,\bar{p}}-\left\langle\frac{f_{\omega_{i}}}{\bar{p}},\frac{\bar{f}}{\bar{p}}\right\rangle_{2,\bar{p}}-\left\langle\frac{\bar{f}}{\bar{p}},\frac{f_{\omega_{j}}}{\bar{p}}\right\rangle_{2,\bar{p}}+\left\langle\frac{\bar{f}}{\bar{p}},\frac{\bar{f}}{\bar{p}}\right\rangle_{2,\bar{p}}$
$\displaystyle=\left\langle\frac{f_{\omega_{i}}}{\bar{p}},\frac{f_{\omega_{j}}}{\bar{p}}\right\rangle_{2,\bar{p}}-\frac{1}{d}\sum_{k=1}^{d}\left\langle\frac{f_{\omega_{i}}}{\bar{p}},\frac{f_{\omega_{k}}}{\bar{p}}\right\rangle_{2,\bar{p}}-\frac{1}{d}\sum_{k=1}^{d}\left\langle\frac{f_{\omega_{k}}}{\bar{p}},\frac{f_{\omega_{j}}}{\bar{p}}\right\rangle_{2,\bar{p}}$
$\displaystyle\hskip
71.13188pt+\frac{1}{d^{2}}\sum_{k=1}^{d}\sum_{l=1}^{d}\left\langle\frac{f_{\omega_{k}}}{\bar{p}},\frac{f_{\omega_{l}}}{\bar{p}}\right\rangle_{2,\bar{p}}.$

Furthermore, due to the independence of the coordinates of the vector $\xi$,
the scalar products
$\left\langle\frac{f_{\omega_{k}}}{\bar{p}},\frac{f_{\omega_{l}}}{\bar{p}}\right\rangle_{2,\bar{p}}$
can only take two values. More precisely, recall that $P_{0}$ denotes the
distribution of the random variable $\sigma\xi_{1}$ and $P_{a}$ the
distribution of the random variable $a+\sigma\xi_{1}$, we get

$\displaystyle\left\langle\frac{f_{\omega_{i}}}{\bar{p}},\frac{f_{\omega_{j}}}{\bar{p}}\right\rangle_{2,\bar{p}}$
$\displaystyle=\begin{cases}1+\chi^{2}(P_{0},P_{a})&\text{if }j=i\\\
1&\text{if }j\neq i.\end{cases}$

We thus obtain

$\left\langle\frac{f_{\omega_{i}}-\bar{f}}{\bar{p}},\frac{f_{\omega_{j}}-\bar{f}}{\bar{p}}\right\rangle_{2,\bar{p}}=\begin{cases}\left(1-\frac{1}{d}\right)\chi^{2}(P_{0},P_{a})&\text{if
}j=i\\\ -\frac{1}{d}\chi^{2}(P_{0},P_{a})&\text{if }j\neq i.\end{cases}$

Write

$C_{1}=\left(1-\frac{1}{d}\right)\chi^{2}(P_{0},P_{a}),$

and

$C_{2}=-\frac{1}{d}\chi^{2}(P_{0},P_{a}).$

The matrix $A_{\lambda}$ has its diagonal elements equal to $C_{1}-\lambda$
and the other coefficients equal to $C_{2}$. Operations on the rows and
columns of $A_{\lambda}$ yield

$\displaystyle\mathrm{Det}(A_{\lambda})$
$\displaystyle=\left(C_{1}+(d-1)C_{2}-\lambda\right)\left(C_{1}-C_{2}-\lambda\right)^{d-1}$
$\displaystyle=-\lambda\left(\chi^{2}(P_{0},P_{a})-\lambda\right)^{d-1}$

Thus, the operator $K$ has only one non-zero eigenvalue and it is equal to
$\chi^{2}(P_{0},P_{a})$. We finally obtain

$\displaystyle\inf_{Q\in\mathcal{Q}_{\alpha}}\inf_{\hat{\eta}\in\mathcal{T}}\sup_{\theta\in\Theta_{d}^{+}(s,a)}\mathbb{E}_{Q(P_{\theta}^{\otimes
n})}|\hat{\eta}-\eta|$
$\displaystyle\geq\frac{1}{2}\left(1-\frac{n(e^{\alpha}-1)^{2}}{d\log(d)}\chi^{2}(P_{0},P_{a})-\frac{\log(2)}{\log(d)}\right)$
$\displaystyle\geq\frac{1}{4}\left(1-\frac{2n(e^{\alpha}-1)^{2}}{d\log(d)}\chi^{2}(P_{0},P_{a})\right),$

if $d\geq 4$. To conclude with the proof of Proposition 3.6, just use Lemma
B.3 below.

######  Lemma B.3.

Consider that the measure $P^{\xi_{1}}$ of the noise coordinates has a density
$p=\exp(-\phi)$, where the potential $\phi$ is two times continuously
differentiable and has a curvature that is bounded from above by a constant
$c_{+}$ as in (3). Then it holds

$\chi^{2}\left(P_{0},P_{a}\right)\leq\exp\left(c_{+}\left(\frac{a}{\sigma}\right)^{2}\right)-1.$
(31)

If the density $p$ is log-concave, with a potential with curvature bounded
above by $c_{+}$ as in (3), then Inequality (31) holds without assuming the
differentiability of $\phi$.

Note that Lemma B.3 is sharp in the sense that in the Gaussian case, $c_{+}=1$
holds and Inequality (31) turns out to be an equality. Note also that log-
concavity is actually not needed in Lemma B.3, since we only require an upper
bound on the curvature of the potential $\phi$.

###### Proof.

Denote $\bar{a}=a/\sigma$. It suffices to show the following inequality,

$\int_{\mathbb{R}}\frac{p^{2}(x-\bar{a})}{p(x)}dx\leq\exp\left(c_{+}\bar{a}^{2}\right),$
(32)

where we recall that $p$ is the density of $\xi_{1}$. It holds

$\displaystyle\int_{\mathbb{R}}\frac{p^{2}(x-\bar{a})}{p(x)}dx$
$\displaystyle=\int_{\mathbb{R}}\exp\left(\phi(x)-2\phi(x-\bar{a})\right)dx.$

As $\phi$ is two times continuously differentiable, we have by Taylor
expansion, for all $x\in\mathbb{R}$,

$\phi(x)-\phi(x-\bar{a})\leq\bar{a}\phi^{\prime}(x-\bar{a})+c_{+}\frac{\bar{a}^{2}}{2}$

and

$\phi(x-2\bar{a})-\phi(x-\bar{a})\leq-\bar{a}\phi^{\prime}(x-\bar{a})+c_{+}\frac{\bar{a}^{2}}{2}.$

By adding the two previous inequalities, we get

$\phi(x)-2\phi(x-\bar{a})\leq-\phi(x-2\bar{a})+c_{+}\bar{a}^{2}.$

This gives

$\displaystyle\int_{\mathbb{R}}\frac{p^{2}(x-\bar{a})}{p(x)}dx$
$\displaystyle=\int_{\mathbb{R}}\exp\left(\phi(x)-2\phi(x-\bar{a})\right)dx$
$\displaystyle\leq\exp\left(c_{+}\bar{a}^{2}\right)\int_{\mathbb{R}}\left(\exp\left(-\phi(x-2\bar{a})\right)\right)dx$
$\displaystyle=\exp\left(c_{+}\bar{a}^{2}\right).$

We proved (32). In the case where $p$ is log-concave, it can be suitably
approximated by infinitely differentiable densities, via the use of
convultions with Gaussian random variables, which completes the proof of Lemma
B.3. ∎

## References

  * [1] R. Adamczak, A.. Litvak, A. Pajor and N. Tomczak-Jaegermann  “Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles”  In _J. Amer. Math. Soc._ 23.2, 2010, pp. 535–561  DOI: 10.1090/S0894-0347-09-00650-X
  * [2] Ishaq Aden-Ali, Hassan Ashtiani and Gautam Kamath  “On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians”  In _arxiv:2010.09929_ , 2020
  * [3] Mitali Bafna and Jonathan Ullman  “The Price of Selection in Differential Privacy”  In _Conference on Learning Theory (COLT)_ , 2017
  * [4] M. Bagnoli and T. Bergstrom  “Log-concave probability and its applications”  In _Econom. Theory_ 26.2, 2005, pp. 445–469
  * [5] Thomas B Berrett and Cristina Butucea  “Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms”  In _Neurips 33_ , 2020
  * [6] Sourav Biswas, Yihe Dong, Gautam Kamath and Jonathan Ullmann  “CoinPress: Practical Private Mean and Covariance Estimation”  In _arxiv:2006.06618_ , 2020
  * [7] S.. Bobkov and M. Ledoux  “From Brunn-Minkowski to Brascamp-Lieb and to logarithmic Sobolev inequalities”  In _Geom. Funct. Anal._ 10.5, 2000, pp. 1028–1052
  * [8] S. Bobkov and M. Ledoux  “One-dimensional empirical measures, order statistics, and Kantorovich transport distances”  In _Mem. Amer. Math. Soc._ 261.1259, 2019, pp. v+126
  * [9] Stéphane Boucheron, Gábor Lugosi and Pascal Massart  “Concentration inequalities: A nonasymptotic theory of independence”  Oxford university press, 2013
  * [10] Cristina Butucea, Amandine Dubois, Martin Kroll and Adrien Saumard  “Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids”  In _Bernoulli_ 26.3 Bernoulli Society for Mathematical StatisticsProbability, 2020, pp. 1727–1764
  * [11] Cristina Butucea, Mohamed Ndaoud, Natalia A Stepanova and Alexandre B Tsybakov  “Variable selection with Hamming loss”  In _The Annals of Statistics_ 46.5 Institute of Mathematical Statistics, 2018, pp. 1837–1875
  * [12] Cristina Butucea, Angelika Rohde and Lukas Steinberger  “Interactive versus non-interactive locally, differentially private estimation: Two elbows for the quadratic functional”  In _arXiv preprint arXiv:2003.04773_ , 2020
  * [13] L.. Caffarelli  “The regularity of mappings with a convex potential”  In _J. Amer. Math. Soc._ 5.1, 1992, pp. 99–104
  * [14] L.. Caffarelli  “Monotonicity properties of optimal transportation and the FKG and related inequalities”  In _Comm. Math. Phys._ 214.3, 2000, pp. 547–563
  * [15] D. Cordero-Erausquin  “Some applications of mass transport to Gaussian-type inequalities”  In _Arch. Ration. Mech. Anal._ 161.3, 2002, pp. 257–269
  * [16] Madeleine Cule and Richard Samworth  “Theoretical properties of the log-concave maximum likelihood estimator of a multidimensional density”  In _Electron. J. Stat._ 4, 2010, pp. 254–270  DOI: 10.1214/09-EJS505
  * [17] Arnak S. Dalalyan  “Theoretical guarantees for approximate sampling from smooth and log-concave densities”  In _J. R. Stat. Soc. Ser. B. Stat. Methodol._ 79.3, 2017, pp. 651–676  DOI: 10.1111/rssb.12183
  * [18] C.. Doss and J.. Wellner  “Global rates of convergence of the MLEs of log-concave and $s$-concave densities”  In _Ann. Statist._ 44.3, 2016, pp. 954–981  DOI: 10.1214/15-AOS1394
  * [19] John C Duchi, Michael I Jordan and Martin J Wainwright  “Minimax optimal procedures for locally private estimation”  In _Journal of the American Statistical Association_ 113.521 Taylor & Francis, 2018, pp. 182–201
  * [20] A. Durmus and É. Moulines  “Nonasymptotic convergence analysis for the unadjusted Langevin algorithm”  In _Ann. Appl. Probab._ 27.3, 2017, pp. 1551–1587  DOI: 10.1214/16-AAP1238
  * [21] Cynthia Dwork et al.  “Our data, ourselves: Privacy via distributed noise generation”  In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_ , 2006, pp. 486–503  Springer
  * [22] Cynthia Dwork, Frank McSherry, Kobbi Nissim and Adam Smith  “Calibrating noise to sensitivity in private data analysis”  In _Theory of cryptography conference_ , 2006, pp. 265–284  Springer
  * [23] O. Guédon  “Concentration phenomena in high dimensional geometry”  In _Proceedings of the Journées MAS 2012_ , 2012
  * [24] Q. Han  “Set structured global empirical risk minimizers are rate optimal in general dimensions”  In _Ann. Statist._ 49.5, 2021, pp. 2642–2671  DOI: 10.1214/21-aos2049
  * [25] Erwan Hillion, Oliver Johnson and Adrien Saumard  “An extremal property of the normal distribution, with a discrete analog”  In _Statist. Probab. Lett._ 145, 2019, pp. 181–186  DOI: 10.1016/j.spl.2018.08.018
  * [26] Francis Hirsch and Gilles Lacombe  “Elements of functional analysis”  Springer-Verlag New York Inc., 1999
  * [27] M.. Jones and A. Noufaily  “Log-location-scale-log-concave distributions for survival and reliability analysis”  In _Electron. J. Stat._ 9.2, 2015, pp. 2732–2750  DOI: 10.1214/15-EJS1089
  * [28] M. Ledoux  “The concentration of measure phenomenon” 89, Mathematical Surveys and Monographs  Providence, RI: American Mathematical Society, 2001, pp. x+181
  * [29] Erich L Lehmann and Joseph P Romano  “Testing statistical hypotheses”  Springer Science & Business Media, 2006
  * [30] Mohamed Ndaoud  “Sharp optimal recovery in the two component gaussian mixture model”  In _arXiv preprint arXiv:1812.08078_ , 2018
  * [31] Mohamed Ndaoud and Alexandre B Tsybakov  “Optimal variable selection and adaptive noisy compressed sensing”  In _IEEE Transactions on Information Theory_ 66.4 IEEE, 2020, pp. 2517–2532
  * [32] L. Paninski  “Log-concavity results on Gaussian process methods for supervised and unsupervised learning”  In _Advances in Neural Information Processing Systems_ , 2004, pp. 1025–1032
  * [33] Angelika Rohde and Lukas Steinberger  “Geometrizing rates of convergence under local differential privacy constraints”  In _Annals of Statistics_ 48.5 Institute of Mathematical Statistics, 2020, pp. 2646–2670
  * [34] A. Saumard and J.. Wellner  “Log-concavity and strong log-concavity: A review”  In _Statist. Surv._ 8, 2014, pp. 45–114
  * [35] Thomas Steinke and Jonathan Ullman  “Tight lower bounds for differentially private selection”  In _58th Annual IEEE Symposium on Foundations of Computer Science (FOCS)_ , 2017
  * [36] Alexandre B Tsybakov  “Introduction to nonparametric estimation”  Springer Science & Business Media, 2008
  * [37] Jonathan Ullman  “Tight lower bounds for locally differentially private selection”  In _arXiv preprint arXiv:1802.02638_ , 2018
  * [38] Larry Wasserman and Shuheng Zhou  “A statistical framework for differential privacy”  In _Journal of the American Statistical Association_ 105.489 Taylor & Francis, 2010, pp. 375–389