* [25] Evfimievski, A., Gehrke, J., & Srikant, R. (2003, June). Limiting privacy breaches in privacy preserving data mining. In Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (pp. 211-222).
  * [26] Forti, M. (2021). The deployment of artificial intelligence tools in the health sector: privacy concerns and regulatory answers within the GDPR. Eur. J. Legal Stud., 13, 29.
  * [27] Gray, R. M. (1990). Entropy and information. Entropy and information theory, 21-55.
  * [28] Györfi, L., & Kroll, M. (2022). On rate optimal private regression under local differential privacy. arXiv preprint arXiv:2206.00114. Chicago
  * [29] Joseph, M., Mao, J., Neel, S., & Roth, A. (2019, November). The role of interactivity in local differential privacy. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (pp. 94-105). IEEE.
  * [30] Kairouz, P., Oh, S., & Viswanath, P. (2014). Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27.
  * [31] Kroll, M. (2020). Adaptive spectral density estimation by model selection under local differential privacy. arXiv preprint arXiv:2010.04218.
  * [32] Lam-Weil, J., Laurent, B., & Loubes, J. M. (2022). Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint. Bernoulli, 28(1), 579-600.
  * [33] Li, M., Berrett, T., & Yu, Y. (2022a). Network change point localisation under local differential privacy. Advances in Neural Information Processing Systems, 35, 15013-15026.
  * [34] Li, M., Berrett, T. B., & Yu, Y. (2022b). On robustness and local differential privacy. arXiv preprint arXiv:2201.00751.
  * [35] Polyak, B. T., & Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, 30(4), 838-855.
  * [36] Rohde, A., & Steinberger, L. (2020). Geometrizing rates of convergence under local differential privacy constraints.
  * [37] Sart, M. (2021). Density estimation under local differential privacy and Hellinger loss.
  * [38] Tang, J., Korolova, A., Bai, X., Wang, X., & Wang, X. (2017). Privacy loss in apple’s implementation of differential privacy on macos 10.12. arXiv preprint arXiv:1709.02753.
  * [39] Tsybakov, A. B. (2004). Introduction to nonparametric estimation, 2009. URL https://doi. org/10.1007/b13794. Revised and extended from the, 9(10).
  * [40] Warner, S. L. (1965). Randomized response: A survey technique for eliminating evasive answer bias. Journal of the American Statistical Association, 60(309), 63-69.
  * [41] Wang, D. & Xu, J. On sparse linear regression in the local differential privacy model IEEE Transactions on Information Theory, 2021, 67, 1182-1200
  * [42] Wasserman, L., & Zhou, S. (2010). A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489), 375-389.

##  Appendix A Appendix

In this section we provide all the technical proofs. We will start by proving
Propositions 3.5 and 3.9. After that, we will give the proofs for the locally
private estimation of the joint moment and of the density, as presented in
Sections 4.2 and 4.3, respectively.

###  A.1 Proof of Proposition 3.5

###### Proof.

Proposition 3.5 is proven by recurrence. The proof is split in two steps.

Step 1
The aim of this step is to show that

$l[z^{1},\dots,z^{d}]\leq
l[\emptyset,z^{2},\dots,z^{d}]+l[dx^{1},z^{2},\dots,z^{d}].$

From the definition of $l$ it is

$l[z^{1},\dots,z^{d}]=|q(z^{1},\dots,z^{d})-\tilde{q}(z^{1},\dots,z^{d})|.$

As observed in (3.6), we have

$q(z^{1},\dots,z^{d})=\int_{\mathcal{X}^{1}}q^{1}(z^{1}|x^{1}){\color[rgb]{0,0,0}q(dx^{1},z^{2},\dots,z^{d})}$

and, in the same way,

$\tilde{q}(z^{1},\dots,z^{d})=\int_{\mathcal{X}^{1}}q^{1}(z^{1}|x^{1}){\color[rgb]{0,0,0}\tilde{q}(dx^{1},z^{2},\dots,z^{d})}.$

It follows that

$\displaystyle{}l[z^{1},\dots,z^{d}]=BBig\lvert\int_{\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1})[q(dx^{1},z^{2},\dots,z^{d})-\tilde{q}(dx^{1},z^{2},\dots,z^{d})]BBig\rvert.$
(A.1)

We split the signed measure
$q(dx^{1},z^{2},\dots,z^{d})-\tilde{q}(dx^{1},z^{2},\dots,z^{d})$ into its
positive and negative part:

$\displaystyle{\color[rgb]{0,0,0}l[z^{1},\dots,z^{d}]}$
$\displaystyle=\Big{|}{\color[rgb]{0,0,0}\int_{\mathcal{X}^{1}}q^{1}(z^{1}|x^{1})[q(dx^{1},z^{2},\dots,z^{d})-\tilde{q}(dx^{1},z^{2},\dots,z^{d})]_{+}}$
$\displaystyle+{\color[rgb]{0,0,0}\int_{\mathcal{X}^{1}}q^{1}(z^{1}|x^{1})[q(dx^{1},z^{2},\dots,z^{d})-\tilde{q}(dx^{1},z^{2},\dots,z^{d})]_{-}\Big{|}}$
$\displaystyle\leq\Big{|}\sup_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1}){\color[rgb]{0,0,0}\int_{\mathcal{X}^{1}}[q(dx^{1},z^{2},\dots,z^{d})-\tilde{q}(dx^{1},z^{2},\dots,z^{d})]_{+}}$
$\displaystyle+\inf_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1}){\color[rgb]{0,0,0}\int_{\mathcal{X}^{1}}[q(dx^{1},z^{2},\dots,z^{d})-\tilde{q}(dx^{1},z^{2},\dots,z^{d})]_{-}}\Big{|},$

using the notation $[A]_{+}$ and $[A]_{-}$ for the positive and negative part
of $A$, respectively. We now have

$\displaystyle[q({\color[rgb]{0,0,0}d}x^{1},z^{2},\dots,z^{d})-\tilde{q}({\color[rgb]{0,0,0}d}x^{1},z^{2},\dots,z^{d})]_{-}$
$\displaystyle=[q({\color[rgb]{0,0,0}d}x^{1},z^{2},\dots,z^{d})-\tilde{q}({\color[rgb]{0,0,0}d}x^{1},z^{2},\dots,z^{d})]-[q({\color[rgb]{0,0,0}d}x^{1},z^{2},\dots,z^{d})-\tilde{q}({\color[rgb]{0,0,0}d}x^{1},z^{2},\dots,z^{d})]_{+}.$

We remark that, if we integrate the last equation with respect to
$x^{1}\in\mathcal{X}^{1}$, the middle term gives a contribution when $d\geq
2$, since
$\int_{\mathcal{X}^{1}}q({\color[rgb]{0,0,0}d}x_{1},z_{2},\dots,z_{d})=q({\color[rgb]{0,0,0}\emptyset,}z_{2},\dots,z_{d})$
is not simply $1$ as in the mono-dimensional case. Hence, it provides

$\displaystyle{}{\color[rgb]{0,0,0}l[z^{1},\dots,z^{d}]}$
$\displaystyle\leq\Big{|}\big{(}\sup_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1})-\inf_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1})\big{)}{\color[rgb]{0,0,0}\int_{\mathcal{X}^{1}}[q(x^{1},z^{2},\dots,z^{d})-\tilde{q}(x^{1},z^{2},\dots,z^{d})]_{+}}|$
(A.2)
$\displaystyle+\inf_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}(z^{1}|x^{1})}|q({\color[rgb]{0,0,0}\emptyset,}z^{2},\dots,z^{d})-\tilde{q}({\color[rgb]{0,0,0}\emptyset,}z^{2},\dots,z^{d})\Big{|}.$

We now observe that

$\displaystyle\sup_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1})-\inf_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1})$
$\displaystyle=\inf_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1})\left(\frac{\sup_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1})}{\inf_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1})}-1\right)$
$\displaystyle\leq\inf_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1})(e^{\alpha_{1}}-1)=q^{1}(z^{1}|x^{1}_{*})(e^{\alpha_{1}}-1),$
(A.3)

where we used (2.4) and the definition
$q^{1}(z^{1}|x^{1}_{*})=\inf_{x^{1}\in\mathcal{X}^{1}}{\color[rgb]{0,0,0}q^{1}}(z^{1}|x^{1})$.
We replace it in (A.2), which entails

$\displaystyle l[z^{1},\dots,z^{d}]$ $\displaystyle\leq
q^{1}(z^{1}|x^{1}_{*})(e^{\alpha_{1}}-1)\int_{\mathcal{X}^{1}}|q(dx^{1},z^{2},\dots,z^{d})-\tilde{q}(dx^{1},z^{2},\dots,z^{d})|$
$\displaystyle+q^{1}(z^{1}|x^{1}_{*})|q(\emptyset,z^{2},\dots,z^{d})-\tilde{q}(\emptyset,z^{2},\dots,z^{d})|$
$\displaystyle={\color[rgb]{0,0,0}l[dx^{1},z^{2},\dots,z^{d}]}+{\color[rgb]{0,0,0}l[\emptyset,z^{2},\dots,z^{d}]},$

which concludes the proof of Step 1.

Step 2
Assume now that $\zeta^{i}\in\\{\emptyset,{\color[rgb]{0,0,0}d}x^{i}\\}$ for
any $i$ smaller than some $j$. Then, this step is devoted to the proof of

${\color[rgb]{0,0,0}l[\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d}]}\leq{\color[rgb]{0,0,0}l[\zeta^{1},\dots,\zeta^{j-1},\emptyset,z^{j+1},\dots,z^{d}]}+{\color[rgb]{0,0,0}l[\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d}]}.$

By definition it is indeed

$\displaystyle{}l[\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d}]$
$\displaystyle=\prod_{i=1}^{j-1}q^{i}(z^{i}|x^{i}_{*})\prod_{i<j:\zeta^{i}=dx^{i}}(e^{\alpha_{i}}-1)$
(A.4)
$\displaystyle\times\int_{\prod\limits_{i<j:\zeta^{i}=dx^{i}}\mathcal{X}^{i}}|q(\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d})|$

We observe that, similarly to (3.6), it is

$q(\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d})={\color[rgb]{0,0,0}\int_{x^{j}\in\mathcal{X}^{j}}q^{j}(z^{j}|x^{j})q(\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d})}$
(A.5)

and also,

$\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d})=\int_{x^{j}\in\mathcal{X}^{j}}q^{j}(z_{j}|x_{j})\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d}).$
(A.6)

Then,

$\displaystyle|q(\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d})|$
(A.7)
$\displaystyle=\Big{|}\int_{x^{j}\in\mathcal{X}^{j}}q^{j}(z^{j}|x^{j})[q(\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d})]\Big{|}.$

Acting as above (A.2), remarking also that

$\int_{{\color[rgb]{0,0,0}x^{j}\in\mathcal{X}^{j}}}q(\zeta^{1},\dots,\zeta^{j-1},{\color[rgb]{0,0,0}dx^{j}},z^{j+1},\dots,z^{d})=q(\zeta^{1},\dots,\zeta^{j-1},{\color[rgb]{0,0,0}\emptyset,}z^{j+1},\dots,z^{d}),$

it follows that the quantity (A.7) is upper bounded by

$\displaystyle\Big{|}(\sup_{x^{j}\in\mathcal{X}^{j}}{\color[rgb]{0,0,0}q^{j}}(z^{j}|x^{j})-\inf_{x^{j}\in\mathcal{X}^{j}}{\color[rgb]{0,0,0}q^{j}}(z^{j}|x^{j}))$
$\displaystyle\times{\color[rgb]{0,0,0}\int_{{\color[rgb]{0,0,0}q^{j}\in\mathcal{X}^{j}}}[q(\zeta^{1},\dots,\zeta^{j-1},{\color[rgb]{0,0,0}dx^{j}},z^{j+1},\dots,z^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},{\color[rgb]{0,0,0}dx^{j}},z^{j+1},\dots,z^{d})]_{+}}\Big{|}$
$\displaystyle+\inf_{x^{j}\in\mathcal{X}^{j}}{\color[rgb]{0,0,0}q^{j}}(z^{j}|x^{j})|q(\zeta^{1},\dots,\zeta^{j-1},{\color[rgb]{0,0,0}\emptyset,}z^{j+1},\dots,z^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},{\color[rgb]{0,0,0}\emptyset,}z^{j+1},\dots,z^{d})|.$

Thus, Equation (A.3) with $q^{j}$ in place of $q^{1}$, entails

$\displaystyle|q(\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d})|$
$\displaystyle\leq(e^{\alpha_{j}}-1){\color[rgb]{0,0,0}q^{j}}(z^{j}|x^{j}_{*}){\color[rgb]{0,0,0}\int_{x_{j}\in\mathcal{X}^{j}}|q(\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d})|}$
$\displaystyle+{\color[rgb]{0,0,0}q^{j}}(z^{j}|x^{j}_{*})|q(\zeta^{1},\dots,\zeta^{j-1},{\color[rgb]{0,0,0}\emptyset,}z^{j+1},\dots,z^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},{\color[rgb]{0,0,0}\emptyset,}z^{j+1},\dots,z^{d})|.$

We replace it in (A.4), obtaining

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

Thus, the proof of Step 2 is completed.

To conclude, we want to show that Steps 1 and 2 imply the stated result of the
proposition. From the two steps above we have, by recurrence,

$\displaystyle l[z^{1},\dots,z^{d}]$
$\displaystyle\leq{\color[rgb]{0,0,0}l[\emptyset,z^{2},\dots,z^{d}]}+{\color[rgb]{0,0,0}l[dx^{1},z^{2},\dots,z^{d}]}$
$\displaystyle\leq{\color[rgb]{0,0,0}l[\emptyset,\emptyset,z^{3},\dots,z^{d}]}+{\color[rgb]{0,0,0}l[\emptyset,dx^{2},z^{3},\dots,z^{d}]}+{\color[rgb]{0,0,0}l[dx^{1},\emptyset,z^{3},\dots,z^{d}]}+{\color[rgb]{0,0,0}l[dx^{1},dx^{2},z^{3},\dots,z^{d}]}$
$\displaystyle\leq\sum_{(\zeta^{1},\dots,\zeta^{d})\in\prod_{j=1}^{d}\\{\emptyset,{dx^{j}}\\}}{\color[rgb]{0,0,0}l[\zeta^{1},\dots,\zeta^{d}]},$

as we wanted. ∎

###  A.2 Proof of Proposition 3.9

The proof follows computations in the proof of Proposition 8 in [20], together
with a representation similar to the result of Proposition 3.5. We start by
introducing notations useful for the proof, which are modifications of (3.7).
For $\bm{z}=(z^{1},\dots,z^{d})\in\bm{\mathcal{Z}}$,
$\bm{x}=(x^{1},\dots,x^{d})\in\bm{\mathcal{X}}$,
$\bm{x_{0}}=(x^{1}_{0},\dots,x^{d}_{0})\in\bm{\mathcal{X}}$:

$\displaystyle\delta^{j}(z^{j}\mid x^{j},x^{j}_{0})=$ $\displaystyle
q^{j}(z^{j}\mid x)-q^{j}(z^{j}\mid x_{0}^{j}),\text{ $j\in\\{1,\dots,d\\}$,}$
$\displaystyle k[\zeta^{1},\dots,\zeta^{d}]:=$ $\displaystyle
q(z^{1},\dots,z^{d})-\tilde{q}(z^{1},\dots,z^{d}),\leavevmode\nobreak\ \text{
for $\bm{\zeta}=\bm{z}$},$ $\displaystyle k[\zeta^{1},\dots,\zeta^{d}]:=$
$\displaystyle\prod_{j:\zeta^{j}=\emptyset}q^{j}(z^{j}|x^{j}_{0})\times$
$\displaystyle\int_{\prod\limits_{j:\zeta^{j}=dx^{j}}\mathcal{X}^{j}}\prod_{j:\zeta^{j}=dx^{j}}\delta^{j}(z^{j}\mid
x^{j},x^{j}_{0})[q(\zeta^{1},\dots,\zeta^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{d})],\leavevmode\nobreak\
\text{ for $\bm{\zeta}\neq\bm{z}$}.$ (A.8)

We recall that with slight abuse of notation, this defines
$k[\emptyset,\dots,\emptyset]=0$.

We first prove the following lemma.

######  Lemma A.1.

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

###### Proof.

The proof of this lemma is very similar to the proof of Proposition 3.5 and we
omit some details. By induction it is sufficient to prove that, for
$j\in\\{1,\dots,d-1\\}$, if $\zeta^{i}\in\\{\emptyset,dx^{i}\\}$ for $j<i$, we
have

$k[\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d}]=k[\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d}]+\\\
k[\zeta^{1},\dots,\zeta^{j-1},\emptyset,z^{j+1},\dots,z^{d}].$ (A.9)

To prove (A.9), using (A.5)–(A.6), we write
$q[\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d}]-\tilde{q}[\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d}]$
as

$\int_{x^{j}\in\mathcal{X}^{j}}q^{j}(z^{j}|x^{j})[q(\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d})].$

Then, we plug in the last expression the equality
$q^{j}(z^{j}|x^{j})=\delta^{j}(z^{j}\mid
x^{j},x_{0}^{j})+q^{j}(z^{j}|x^{j}_{0})$. It yields that
$q[\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d}]-\tilde{q}[\zeta^{1},\dots,\zeta^{j-1},z^{j},\dots,z^{d}]$
is equal to

$\int_{x^{j}\in\mathcal{X}^{j}}\delta^{j}(z^{j}|x^{j},x_{0}^{j})[q(\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{j-1},dx^{j},z^{j+1},\dots,z^{d})]+\\\
q^{j}(z^{j}|x^{j}_{0})q[\zeta^{1},\dots,\zeta^{j-1},\emptyset,z^{j+1},\dots,z^{d}]-\tilde{q}[\zeta^{1},\dots,\zeta^{j-1},\emptyset,z^{j+1},\dots,z^{d}].$

Now, (A.9) is a consequence of the last equality and definition (A.8). ∎

###### Proof of (3.17).

From the definition of the $f_{l}$-divergence, we have

$D_{f_{l}}(M\|\tilde{M})=\int_{\mathcal{Z}^{1}\times\dots\times\mathcal{Z}^{d}}\frac{\lvert
q(\bm{z})-\tilde{q}(\bm{z})\rvert^{l}}{\tilde{q}(\bm{z})^{l-1}}d\bm{\mu}(\bm{z}).$
(A.10)

Since $t\mapsto t^{1-l}$ is convex, we deduce from Jensen’s inequality that

$\tilde{q}(\bm{z})^{1-l}=\left(\int_{\bm{\mathcal{X}}}\prod_{j=1}^{d}q^{j}(z^{j}\mid
x_{0}^{j})\tilde{P}(d\bm{x_{0}})\right)^{1-l}\leq\int_{\bm{\mathcal{X}}}\prod_{j=1}^{d}q^{j}(z^{j}\mid
x_{0}^{j})^{1-l}\tilde{P}(d\bm{x_{0}}).$

Inserting this control in (A.10), and using Fubini-Tonelli theorem we deduce
that
$D_{f_{l}}(M\|\tilde{M})=\int_{\bm{\mathcal{X}}}W(\bm{x_{0}})^{l}\tilde{P}(d\bm{x_{0}})$
where

$W(\bm{x_{0}})=\Big{(}\int_{\mathcal{Z}^{1}\times\dots\times\mathcal{Z}^{d}}\frac{\lvert
q(\bm{z})-\tilde{q}(\bm{z})\rvert^{l}}{\prod_{j=1}^{d}q^{j}(z^{j}\mid
x_{0}^{j})^{l-1}}d\bm{\mu}(\bm{z})\Big{)}^{1/l}.$

Now, using that $\tilde{P}$ is a probability, the control (3.17) follows if we
can prove that $W(\bm{x_{0}})$ is upper bounded independently of $\bm{x_{0}}$
by the RHS of (3.17). From the definition of $k[\eta^{1},\dots,\eta^{d}]$ we
have $\lvert q(\bm{z})-\tilde{q}(\bm{z})\rvert=k[z^{1},\dots,z^{d}]$, and we
use Lemma A.1 to get,

$W(\bm{x_{0}})=\Big{(}\int_{\mathcal{Z}^{1}\times\dots\times\mathcal{Z}^{d}}\Big{\lvert}\sum_{(\zeta^{1},\dots,\zeta^{d})\in\prod_{j=1}^{d}\\{\emptyset,{dx^{j}}\\}}\frac{k[\zeta^{1},\dots,\zeta^{d}]}{\prod_{j=1}^{d}q^{j}(z^{j}\mid
x_{0}^{j})^{1-1/l}}\Big{\rvert}^{l}d\bm{\mu}(\bm{z})\Big{)}^{1/l}.$

It follows from the triangular inequality that

$W(\bm{x_{0}})\leq\sum_{(\zeta^{1},\dots,\zeta^{d})\in\prod_{j=1}^{d}\\{\emptyset,dx^{j}\\}}W_{\zeta^{1},\dots,\zeta^{d}}(\bm{x_{0}}),$
(A.11)

with

$W_{\zeta^{1},\dots\zeta^{d}}(\bm{x_{0}}):=\Big{(}\int_{\mathcal{Z}^{1}\times\dots\times\mathcal{Z}^{d}}\Big{\lvert}\frac{k[\zeta^{1},\dots,\zeta^{d}]}{\prod_{j=1}^{d}q^{j}(z^{j}\mid
x_{0}^{j})^{1-1/l}}\Big{\rvert}^{l}d\bm{\mu}(\bm{z})\Big{)}^{1/l}.$

We remind the definition (A.8) of $k[\zeta^{1},\dots,\zeta^{d}]$ and use
generalized Minkowski’s inequality to get

$W_{\zeta^{1},\dots\zeta^{d}}(\bm{x_{0}})\leq\int_{\prod\limits_{j:\zeta^{j}=dx^{j}}\mathcal{X}^{j}}\Big{(}\int_{\mathcal{Z}^{1}\times\dots\times\mathcal{Z}^{d}}\prod_{j:\zeta^{j}=dx^{j}}\big{\lvert}\frac{\delta(z^{j}\mid
x^{j},x_{0}^{j})}{q^{j}(z^{j}\mid x^{j}_{0})^{1-1/l}}\big{\rvert}^{l}\times\\\
\prod_{j:\zeta^{j}=\emptyset}q(z^{j}\mid
x^{j}_{0})d\bm{\mu}(\bm{z})\Big{)}^{1/l}\lvert
q(\zeta^{1},\dots,\zeta^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{d})\rvert.$

Recall that the reference measure is in a product form, i.e.
$\bm{\mu}(d\bm{z})=\prod_{j=1}^{d}\mu^{j}(dz^{j})$. Moreover, notice that
$\zeta^{j}$ can only be $\emptyset$ or $dx^{j}$ and that
$\int_{\mathcal{Z}^{j}}q(z^{j}\mid x^{j}_{0})\mu^{j}(dz^{j})=1$ and
$\int_{\mathcal{Z}^{j}}\big{\lvert}\frac{\delta(z^{j}\mid
x^{j},x_{0}^{j})}{q^{j}(z^{j}\mid
x^{j}_{0})^{1-1/l}}\big{\rvert}^{l}\mu^{j}(dz^{j})=D_{f_{l}}(Q^{j}(\cdot\mid
X^{j}=x^{j})\|Q^{j}(\cdot\mid X^{j}=x^{j}_{0}))$. From here we deduce

$\displaystyle W_{\zeta^{1},\dots\zeta^{d}}(\bm{x_{0}})$
$\displaystyle\begin{multlined}\leq\int_{\prod\limits_{j:\zeta^{j}=dx^{j}}\mathcal{X}^{j}}\Big{(}\prod_{j:\zeta^{j}=dx^{j}}D_{f_{l}}(Q^{j}(\cdot\mid
X^{j}=x^{j})\|Q^{j}(\cdot\mid X^{j}=x^{j}_{0}))\Big{)}^{1/l}\\\ \times\lvert
q(\zeta^{1},\dots,\zeta^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{d})\rvert\end{multlined}\leq\int_{\prod\limits_{j:\zeta^{j}=dx^{j}}\mathcal{X}^{j}}\Big{(}\prod_{j:\zeta^{j}=dx^{j}}D_{f_{l}}(Q^{j}(\cdot\mid
X^{j}=x^{j})\|Q^{j}(\cdot\mid X^{j}=x^{j}_{0}))\Big{)}^{1/l}\\\ \times\lvert
q(\zeta^{1},\dots,\zeta^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{d})\rvert$
$\displaystyle\leq\int_{\prod\limits_{j:\zeta^{j}=dx^{j}}\mathcal{X}^{j}}\Big{(}\prod_{j:\zeta^{j}=dx^{j}}\varepsilon_{j}\Big{)}\lvert
q(\zeta^{1},\dots,\zeta^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{d})\rvert,$

where we used (3.16). Since
$\int_{\prod\limits_{j:\zeta^{j}=dx^{j}}\mathcal{X}^{j}}\lvert
q(\zeta^{1},\dots,\zeta^{d})-\tilde{q}(\zeta^{1},\dots,\zeta^{d})\rvert$ is
the total variance distance between the laws of $(X^{j})_{j:\zeta^{j}=dx^{j}}$
under $P$ and $\tilde{P}$ we deduce

$W_{\zeta^{1},\dots\zeta^{d}}(\bm{x_{0}})\leq\big{(}\prod_{j:\zeta^{j}=dx^{j}}\varepsilon_{j}\big{)}\times
d_{TV}\big{(}L_{((X^{j})_{j:\zeta^{j}=dx^{j}})},L_{((\tilde{X}^{j})_{j:\zeta^{j}=dx^{j}})}\big{)}$
(A.12)

Collecting (A.11), (A.12), we deduce

$W(\bm{x_{0}})\leq\sum_{(\zeta^{1},\dots,\zeta^{d})\in\prod_{j=1}^{d}\\{\emptyset,dx^{j}\\}}\big{(}\prod_{j:\zeta^{j}=dx^{j}}\varepsilon_{j}\big{)}\times
d_{TV}\big{(}L_{((X^{j})_{j:\zeta^{j}=dx^{j}})},L_{((\tilde{X}^{j})_{j:\zeta^{j}=dx^{j}})}\big{)}.$

After reorganizing the sum in the equation above, we recognize the RHS of
(3.17), and the Proposition 3.9 is proved. ∎

###  A.3 Locally private joint moment estimation

In this section we prove all the technical results related to the estimation
of joint moment under local differential privacy constraints.

####  A.3.1 Proof of Theorem 4.5

###### Proof.

$\bullet$ We first prove the result for $\hat{\gamma}_{n}$ as stated in (4.9).
This is based on a bias-variance decomposition for the $L^{2}$ risk. Let us
denote the bias term by

${\color[rgb]{0,0,0}b_{T^{(1)},T^{(2)},\dots,T^{(d)}}:=\mathbb{E}[\prod_{j=1}^{d}Z^{j}_{i}]-\mathbb{E}[\prod_{j=1}^{d}X^{j}_{i}]=\mathbb{E}[\prod_{j=1}^{d}Z^{j}]-\mathbb{E}[\prod_{j=1}^{d}X^{j}].}$
(A.13)

We first state as lemma a control on the magnitude of this bias term, its
proof can be found at the end of this section.

######  Lemma A.2.

We have

$\left\lvert
b_{T^{(1)},T^{(2)},\dots,T^{(d)}}\right\rvert\leq\sum_{l=1}^{d}\Big{\\{}(T^{(l)})^{-k_{l}(1-\frac{d}{\overline{k}})}\Big{(}\prod_{\begin{subarray}{c}j=1\\\
j\neq l\end{subarray}}^{d}\lVert X^{j}\rVert_{k_{j}}\Big{)}\lVert
X^{l}\rVert_{k_{l}}^{1+k_{l}(1-\frac{d}{\overline{k}})}\Big{\\}}.$

To get (4.9), we write the bias variance decomposition,
$\mathbb{E}\left[(\hat{\gamma}_{n}-\gamma)^{2}\right]={\color[rgb]{0,0,0}(b_{T^{(1)},\dots,T^{(d)}})^{2}}+\text{var}(\hat{\gamma}_{n})$.
By independence and Hölder’s inequality,

$\displaystyle{\color[rgb]{0,0,0}\text{var}(\hat{\gamma}_{n})=n^{-2}\sum_{i=1}^{n}\text{var}(\prod_{j=1}^{d}Z^{j}_{i})\leq
n^{-1}\mathbb{E}(\lvert\prod_{j=1}^{d}Z^{j}\rvert^{2})\leq
n^{-1}\prod_{j=1}^{d}\mathbb{E}(\lvert Z^{1}\rvert^{2d})^{\frac{1}{d}}.}$
(A.14)

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

$\mathbb{E}(\lvert
Z^{j}\rvert^{\color[rgb]{0,0,0}2d})=\mathbb{E}(\lvert\left[X^{j}\right]_{T^{(j)}}+\mathcal{E}^{j}\rvert^{2d})\leq{\color[rgb]{0,0,0}2^{2d-1}}\mathbb{E}[\left[X^{j}\right]_{T^{(j)}}^{\color[rgb]{0,0,0}2d}]+{\color[rgb]{0,0,0}2^{2d-1}}\mathbb{E}[\lvert\mathcal{E}^{j}\rvert^{\color[rgb]{0,0,0}2d}]\\\
\leq{\color[rgb]{0,0,0}2^{2d-1}}|T^{(j)}|^{\color[rgb]{0,0,0}2d}\left(1+\left(\frac{2}{\alpha_{j}}\right)^{\color[rgb]{0,0,0}2d}\mathbb{E}\left[\lvert\mathcal{L}(1)\rvert^{\color[rgb]{0,0,0}2d}\right]\right),$

as $\mathcal{E}^{j}$ is equal in law to a
$\frac{2T^{(j)}}{\alpha_{j}}\times\mathcal{L}(1)$ variable. We deduce
$\mathbb{E}(\lvert Z^{j}\rvert^{2d})\leq 2^{2d-1}\lvert
T^{(j)}\rvert^{2d}(1+\frac{2^{2d}d!}{\alpha^{2d}_{j}})\leq C\lvert
T^{(j)}\rvert^{2d}/\alpha^{2d}_{j}$ for some constant $C$, using
$\alpha_{j}\leq 1$. From (A.14), it entails

$\text{var}(\hat{\gamma}_{n})\leq
Cn^{-1}{\color[rgb]{0,0,0}\frac{\prod_{j=1}^{d}\lvert
T^{(j)}\rvert^{2}}{\prod_{j=1}^{d}\alpha^{2}_{j}},}$ (A.15)

for some constant $C>0$. In turn, recalling Lemma A.2, we get

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

The calibration given in the statement of the theorem is for all
$j\in\\{1,\dots,d\\}$,
$(T^{(j)})^{k_{j}}=(n\prod_{j=1}^{d}\alpha_{j}^{2})^{1/2}$, which is such that
all the terms in the right hand side of (A.16) equilibrate and
$\mathbb{E}\left[(\hat{\gamma}_{n}-\gamma)^{2}\right]\leq
c{\color[rgb]{0,0,0}(n\prod_{j=1}^{d}\alpha^{2}_{j})^{-(1-\frac{d}{\overline{k}})}=c(n\prod_{j=1}^{d}\alpha^{2}_{j})^{-\frac{\overline{k}-d}{\overline{k}}}}$.
The proof of (4.9) is complete.  ∎

###### Proof of Lemma A.2.

From (4.6) and (A.13), we have

$\displaystyle b_{{\color[rgb]{0,0,0}T^{(1)},\dots,T^{(d)}}}$
$\displaystyle=\mathbb{E}\left[{\color[rgb]{0,0,0}\prod_{j=1}^{d}\left(\left[X^{j}\right]_{T^{(j)}}+\mathcal{E}^{j}\right)}\right]-\mathbb{E}\left[{\color[rgb]{0,0,0}\prod_{j=1}^{d}X^{j}}\right]$
$\displaystyle=\mathbb{E}\left[{\color[rgb]{0,0,0}\prod_{j=1}^{d}\left[X^{j}\right]_{T^{(j)}}}\right]-\mathbb{E}\left[{\color[rgb]{0,0,0}\prod_{j=1}^{d}X^{j}}\right],$
(A.17)

where we used that the variables $\mathcal{E}^{j}$, $j=1,\dots,d$ are centered
and independent of the variables $X^{j}$ $j=1,\dots,d$. We set
$\Delta^{(j)}=\left[X^{j}\right]_{T^{(j)}}-X^{j}$ for $j=1,\dots,d$ and get,

$b_{{\color[rgb]{0,0,0}T^{(1)},\dots,T^{(d)}}}=\sum_{l=1}^{d}\mathbb{E}\left[\big{(}\prod_{j=1}^{l-1}X^{j}\big{)}\Delta^{(l)}\big{(}\prod_{j=l+1}^{d}\left[X^{j}\right]_{T^{(j)}}\big{)}\right]$

We remark that $\Delta^{(l)}=\Delta^{(l)}\mathds{1}_{\\{\lvert X^{l}\rvert\geq
T^{(l)}\\}}$ and deduce

$\lvert
b_{{\color[rgb]{0,0,0}T^{(1)},\dots,T^{(d)}}}\rvert\leq\sum_{l=1}^{d}\mathbb{E}\left[\big{(}\prod_{j=1}^{l-1}\lvert
X^{j}\rvert\big{)}\lvert\Delta^{(l)}\rvert\mathds{1}_{\\{\lvert
X^{l}\rvert\geq
T^{(l)}\\}}\big{(}\prod_{j=l+1}^{d}|\left[X^{j}\right]_{T^{(j)}}|\big{)}\right]$

We assess the magnitude of each term in the sum above. Using that
$\sum_{j=1}^{d}\frac{1}{k_{j}}<1$, we define $r>1$ by the identity
${\color[rgb]{0,0,0}\sum_{j=1}^{d}}\frac{1}{k_{j}}+\frac{1}{r}=1$. We now
apply for the term corresponding to index $l$ in the sum above the Hölder
inequality to a product of $d+1$ quantities with coefficients
$\frac{1}{k_{1}}+\dots+\frac{1}{k_{l-1}}+\frac{1}{k_{l}}+\frac{1}{r}+\frac{1}{k_{l+1}}+\dots\frac{1}{k_{d}}=1$.
This yields,

$\lvert
b_{{\color[rgb]{0,0,0}T^{(1)},\dots,T^{(d)}}}\rvert\leq\sum_{l=1}^{d}\big{(}\prod_{j=1}^{l-1}\lVert
X^{j}\rVert_{k_{j}}\big{)}\lVert\Delta^{(l)}\rVert_{k_{l}}\lVert\mathds{1}_{\\{\lvert
X^{l}\rvert\geq
T^{(l)}\\}}\rVert_{r}\big{(}\prod_{j=l+1}^{d}\lVert\left[X^{j}\right]_{T^{(j)}}\rVert_{k_{j}}.\big{)}$

Using that $\lvert\Delta^{(l)}\rvert\leq\lvert X^{l}\rvert$ and
$\lvert\left[X^{j}\right]_{T^{(j)}}\rvert\leq\lvert X^{j}\rvert$, we deduce

$\lvert
b_{{\color[rgb]{0,0,0}T^{(1)},\dots,T^{(d)}}}\rvert\leq\sum_{l=1}^{d}\big{(}\prod_{j=1}^{d}\lVert
X^{j}\rVert_{k_{j}}\big{)}\lVert\mathds{1}_{\\{\lvert X^{l}\rvert\geq
T^{(l)}\\}}\rVert_{r}.$

By Markov inequality $\lVert\mathds{1}_{\\{\lvert X^{l}\rvert\geq
T^{(l)}\\}}\rVert_{r}=\mathbb{P}\left(\lvert X^{l}\rvert\geq
T^{(l)}\right)^{1/r}\leq\Big{(}\frac{\lVert
X^{l}\rVert_{k_{l}}^{k_{l}}}{|T^{(l)}|^{k_{l}}}\big{)}^{1/r}$ and we obtain

$\lvert
b_{{\color[rgb]{0,0,0}T^{(1)},\dots,T^{(d)}}}\rvert\leq\sum_{l=1}^{d}\big{(}\prod_{\begin{subarray}{c}j=1\\\
j\neq l\end{subarray}}^{d}\lVert X^{j}\rVert_{k_{j}}\big{)}\lVert
X^{l}\rVert^{1+\frac{k_{l}}{r}}_{k_{l}}|T^{(l)}|^{-k_{l}/r}.$

As $\frac{1}{r}=1-\sum_{j=1}^{d}\frac{1}{k_{j}}=1-\frac{d}{\overline{k}}$, we
deduce the lemma.  ∎

####  A.3.2 Proof of Corollary 4.8

###### Proof.

By direct application of Theorem 4.5, we have

$\mathbb{E}\left[\left\lvert\hat{\gamma}_{n}-\gamma\right\rvert^{2}\right]\leq
c(n\alpha^{2}_{1}\alpha^{2}_{2})^{-\frac{\overline{k}-2}{\overline{k}}}.$
(A.18)

We now deduce the result (4.10) on $\hat{\theta}_{n}$. An additional error
appears in the estimation of $\theta$ due to the inference of both means
$m_{1}$, $m_{2}$. We will see that these additional errors are at most of the
same magnitude as the estimation error of the cross term
$\gamma=E[X^{1}X^{2}]$. We need to recall the bias-variance decomposition
given in the proof of Corollary 1 in [19] :

$\mathbb{E}\left[(\hat{m}_{n}^{(j)}-m^{(j)})^{2}\right]\leq
c\left((T^{(j)})^{-(k_{j}-1)}+n^{-1}\frac{\lvert
T^{(j)}\rvert^{2}}{\alpha^{2}_{j}}\right),\quad\text{for $j\in\\{1,2\\}$},$
(A.19)

where the constant $c$ does not depend on $n\geq 1$, $\alpha_{j}\in(0,1]$. Let
us emphasize that the optimal trade-off in (A.19) is given by the choices of
$T^{(j)}$ appearing in the statement of Theorem 4.4. However, our choice
$T^{(j)}=(n\alpha_{1}^{2}\alpha_{2}^{2})^{\frac{1}{2k_{j}}}$ is tailored to
get the optimal trade-off while estimating $\gamma$ with
$\alpha_{1},\alpha_{2}<1$, and yields to a $\mathbf{L}^{2}$-risk for the
estimation of the means which is suboptimal in $\alpha_{j}$. Replacing in
(A.19), we get,

$\mathbb{E}\left[(\hat{m}_{n}^{(j)}-m^{(j)})^{2}\right]\leq
c\left((n\alpha_{1}^{2}\alpha_{2}^{2})^{-\frac{k_{j}-1}{k_{j}}}+n^{-1}\frac{(n\alpha_{1}^{2}\alpha_{2}^{2})^{2}}{\alpha_{j}^{2}}\right)\leq
c(n\alpha^{2}_{1}\alpha_{2}^{2})^{-\frac{k_{j}-1}{k_{j}}}\left(1+\alpha_{3-j}^{2}\right)\\\
\leq c(n\alpha^{2}_{1}\alpha_{2}^{2})^{-\frac{k_{j}-1}{k_{j}}}\quad\text{for
$j\in\\{1,2\\}$}.$ (A.20)

Now, we split

$\hat{\theta}_{n}-\theta=\hat{\gamma}_{n}-\gamma-\left[(\hat{m}^{(1)}_{n}-m^{(1)})m^{(2)}+\hat{m}^{(1)}_{n}(\hat{m}^{(2)}_{n}-m^{(2)})\right],$
(A.21)

and denote by $\sum_{l=1}^{2}e_{n}^{(l)}$ the two terms in the bracket of the
above equation. By (A.20), we have,

$\mathbb{E}\left[\lvert
e_{n}^{(1)}\rvert^{2}\right]=\mathbb{E}\left[(\hat{m}^{(1)}_{n}-m^{(1)})^{2}\right]\lvert
m^{(2)}\rvert^{2}\leq
c(n\alpha^{2}_{1}\alpha^{2}_{2})^{-\frac{k_{1}-1}{k_{1}}}\\\ \leq
c(n\alpha^{2}_{1}\alpha^{2}_{2})^{-[1-\frac{1}{k_{1}}-\frac{1}{k_{2}}]}=c(n\alpha^{2}_{1}\alpha^{2}_{2})^{-\frac{\overline{k}-2}{\overline{k}}}$
(A.22)

where we used $n\alpha^{2}_{1}\alpha^{2}_{2}\geq 1$ and
$X^{2}\in\mathbf{L}^{k_{2}}\subset\mathbf{L}^{1}$. The control of the second
term necessitates more care. Using (4.6), we have, recalling the definition
$\hat{m}^{(1)}_{n}=n^{-1}\sum_{i=1}^{n}Z^{1}_{i}$, as given in (4.7),

$\displaystyle\mathbb{E}\left[\lvert e_{n}^{(2)}\rvert^{2}\right]$
$\displaystyle=\mathbb{E}\left[\lvert\hat{m}^{(1)}_{n}\rvert^{2}(\hat{m}_{n}^{(2)}-m^{(2)})^{2}\right]$
$\displaystyle\leq
2\mathbb{E}\left[\left(\frac{1}{n}\sum_{i=1}^{n}\left[X_{i}^{1}\right]_{T^{(1)}}\right)^{2}(\hat{m}_{n}^{(2)}-m^{(2)})^{2}\right]+2\mathbb{E}\left[\left(\frac{1}{n}\sum_{i=1}^{n}\mathcal{E}^{1}_{i}\right)^{2}(\hat{m}_{n}^{(2)}-m^{(2)})^{2}\right]$
$\displaystyle\leq 2\lvert
T^{(1)}\rvert^{2}\mathbb{E}\left[(\hat{m}_{n}^{(2)}-m^{(2)})^{2}\right]+2\mathbb{E}\left[\left(\frac{1}{n}\sum_{i=1}^{n}\mathcal{E}^{1}_{i}\right)^{2}\right]\mathbb{E}\left[(\hat{m}_{n}^{(2)}-m^{(2)})^{2}\right],$

where we used $\left\lvert\left[X_{i}^{1}\right]_{T^{(1)}}\right\rvert\leq
T^{(1)}$ for the first expectation, and the independence of
$(\mathcal{E}^{1}_{i})_{i}$ and $\hat{m}_{n}^{(2)}$ for the second one.
Recalling $T^{(1)}=(n\alpha^{2}_{1}\alpha^{2}_{2})^{\frac{1}{2k_{1}}}$ and
that $\mathcal{E}_{i}^{1}$ are iid centered variable with variance
$\frac{8\lvert T^{(1)}\rvert^{2}}{\alpha^{2}_{1}}$, we get

$\displaystyle\mathbb{E}\left[\lvert e_{n}^{(2)}\rvert^{2}\right]$
$\displaystyle\leq c\left(\lvert T^{(1)}\rvert^{2}+\frac{{\lvert
T^{(1)}\rvert^{2}}}{n\alpha^{2}_{1}}\right)\mathbb{E}\left[(\hat{m}_{n}^{(2)}-m^{(2)})^{2}\right]$
$\displaystyle\leq
c\left((n\alpha^{2}_{1}\alpha^{2}_{2})^{\frac{1}{k_{1}}}+\alpha^{2}_{1}(n\alpha^{2}_{1}\alpha_{2}^{2})^{\frac{1}{k_{1}}-1}\right)\mathbb{E}\left[(\hat{m}_{n}^{(2)}-m^{(2)})^{2}\right]$
$\displaystyle\leq
c\left((n\alpha^{2}_{1}\alpha_{2}^{2})^{\frac{1}{k_{1}}}+\alpha^{2}_{1}(\alpha^{2}_{1}\alpha_{2}^{2})^{\frac{1}{k_{1}}-1}\right)(n\alpha^{2}_{1}\alpha_{2}^{2})^{-\frac{k_{2}-1}{k_{2}}}$
$\displaystyle\leq
c(n\alpha^{2}_{1}\alpha_{2}^{2})^{\frac{1}{k_{1}}}(n\alpha^{2}_{1}\alpha_{2}^{2})^{-\frac{k_{2}-1}{k_{2}}}=c(n\alpha^{2}_{1}\alpha_{2}^{2})^{-\frac{\overline{k}-2}{\overline{k}}},$
(A.23)

where we used $\alpha_{1}^{2}\leq 1$, $n\alpha^{2}_{1}\alpha_{2}^{2}\geq 1$.

Collecting (A.18) with (A.21)– (A.23), we deduce (4.10). ∎

####  A.3.3 Proof adaptive procedure

Before proving Theorem 4.15, we introduce several notations and state some
auxiliary lemmas. We set for ${\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T}$,

$\displaystyle\mathbb{D}_{\color[rgb]{0,0,0}\bm{T}}=\left(\sup_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left\lvert\mathbb{E}\left[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}\right]\right\rvert\right)\vee\left\lvert\mathbb{E}\left[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}_{n}\right]-\gamma\right\rvert,$
(A.24)
$\displaystyle\overline{\bm{b}}_{{\color[rgb]{0,0,0}\bm{T}}}=\overline{\bm{b}}_{{\color[rgb]{0,0,0}(T^{(1)},\dots,T^{(d)})}}={\color[rgb]{0,0,0}\sum_{l=1}^{d}\Big{\\{}|T^{(l)}|^{-k_{l}(1-\frac{d}{\overline{k}})}\big{(}\prod_{\begin{subarray}{c}j=1\\\
j\neq l\end{subarray}}^{d}\lVert X^{j}\rVert_{k_{j}}\big{)}\lVert
X^{l}\rVert^{1+k_{l}(1-\frac{d}{\overline{k}})}_{k_{l}}\Big{\\}}}.$ (A.25)

The quantity $\overline{\bm{b}}_{\color[rgb]{0,0,0}\bm{T}}$ is some upper
bound for the bias term according to Lemma A.2. We show in the next lemma that
it also controls $\mathbb{D}_{\color[rgb]{0,0,0}{\bm{T}}}$.

######  Lemma A.3.

We have $\mathbb{D}_{\color[rgb]{0,0,0}\bm{T}}\leq
2\overline{\bm{b}}_{\color[rgb]{0,0,0}\bm{T}}$.

###### Proof.

By Lemma A.2 we have
$\left\lvert\mathbb{E}\left[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}_{n}\right]-\gamma\right\rvert{\color[rgb]{0,0,0}{}=\lvert
b_{T^{(1)},\dots,T^{(d)}}\rvert}\leq\overline{\bm{b}}_{\color[rgb]{0,0,0}\bm{T}}$
for ${\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T}$. For
$({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})\in\mathcal{T}^{2}$,
recalling (4.13)–(4.14), we have

$\displaystyle\mathbb{E}\left[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}\right]$
$\displaystyle=\mathbb{E}\left[{\color[rgb]{0,0,0}\prod_{j=1}^{d}Z^{j,T^{(j)}\wedge
T^{\prime(j)}}_{1}}\right]-\mathbb{E}\left[{\color[rgb]{0,0,0}\prod_{j=1}^{d}Z^{j,T^{\prime(j)}}_{1}}\right]$
$\displaystyle=\mathbb{E}\left[{\color[rgb]{0,0,0}\prod_{j=1}^{d}\left[X^{j}_{1}\right]_{T^{(j)}\wedge
T^{\prime(j)}}}\right]-\mathbb{E}\left[{\color[rgb]{0,0,0}\prod_{j=1}^{d}\left[X^{j}_{1}\right]_{T^{\prime(j)}}}\right]$
$\displaystyle=:{\color[rgb]{0,0,0}\bm{b}_{\bm{T},\bm{T}^{\prime}}},$

where we used definitions (4.12) and the centering of the Laplace variables in
the second line. Now we show
$\left\lvert\bm{b}_{\bm{T},\bm{T}^{\prime}}\right\rvert\leq
2\overline{\bm{b}}_{\bm{T}}$. We write
$\bm{b}_{\bm{T},\bm{T}^{\prime}}=\sum_{l=1}^{d}\bm{b}^{(l)}_{\bm{T},\bm{T}^{\prime}}$
where

$\bm{b}^{(l)}_{\bm{T},\bm{T}^{\prime}}=\mathbb{E}\left[\Big{(}\prod_{j=1}^{l-1}\left[X^{j}_{1}\right]_{T^{\prime(j)}}\Big{)}\Big{(}\left[X^{l}_{1}\right]_{T^{(l)}\wedge
T^{\prime(l)}}-\left[X^{l}_{1}\right]_{T^{\prime(l)}}\Big{)}\Big{(}\prod_{j=l+1}^{d}\left[X^{j}_{1}\right]_{T^{(j)}\wedge
T^{\prime(j)}}\Big{)}\right].$

Let us study $\bm{b}^{(l)}_{\bm{T}\wedge\bm{T}^{\prime}}$ :

  * •

Case 1 : $T^{(l)}\geq T^{\prime(l)}$. Then,
$\left[X^{l}_{1}\right]_{T^{(l)}\wedge
T^{\prime(l)}}=\left[X^{l}_{1}\right]_{T^{\prime(l)}}$ and
$\bm{b}^{(l)}_{\bm{T}\wedge\bm{T}^{\prime}}=0$.

  * •

Case 2 : $T^{(l)}\leq T^{\prime(l)}$. Then,
$\left[X^{l}_{1}\right]_{T^{(l)}\wedge
T^{\prime(l)}}=\left[X^{l}_{1}\right]_{T^{(l)}}$ and we write

$\bm{b}^{(l)}_{\bm{T},\bm{T}^{\prime}}=\mathbb{E}\left[\Big{(}\prod_{j=1}^{l-1}\left[X^{j}_{1}\right]_{T^{\prime(j)}}\Big{)}\Big{(}\left[X^{l}_{1}\right]_{T^{(l)}}-X^{l}_{1}\Big{)}\Big{(}\prod_{j=l+1}^{d}\left[X^{j}_{1}\right]_{T^{(j)}\wedge
T^{\prime(j)}}\Big{)}\right]+\\\
\mathbb{E}\left[\Big{(}\prod_{j=1}^{l-1}\left[X^{j}_{1}\right]_{T^{\prime(j)}}\Big{)}\Big{(}X^{l}_{1}-\left[X^{l}_{1}\right]_{T^{\prime(l)}}\Big{)}\Big{(}\prod_{j=l+1}^{d}\left[X^{j}_{1}\right]_{T^{(j)}\wedge
T^{\prime(j)}}\Big{)}\right].$

Now, we use
$\lvert\left[X^{l}_{1}\right]_{T^{(l)}}-X^{l}_{1}\rvert=\lvert\left[X^{l}_{1}\right]_{T^{(l)}}-X^{l}_{1}\rvert\mathds{1}_{\\{\lvert
X^{l}\rvert\geq T^{(l)}\\}}\leq\lvert X^{l}_{1}\rvert\mathds{1}_{\\{\lvert
X^{l}\rvert\geq T^{(l)}\\}}$. Similarly, $\lvert
X^{l}_{1}-\left[X^{l}_{1}\right]_{T^{\prime(l)}}\rvert\leq\lvert
X^{l}_{1}\rvert\mathds{1}_{\\{\lvert X^{l}\rvert\geq T^{\prime(l)}\\}}$ and
$\lvert\left[X^{j}_{1}\right]_{T^{(j)}\wedge
T^{\prime(j)}}\rvert\leq\lvert\left[X^{j}_{1}\right]_{T^{\prime(j)}}\rvert\leq\lvert
X^{j}_{1}\rvert$. We deduce

$\lvert\bm{b}^{(l)}_{\bm{T},\bm{T}^{\prime}}\rvert\leq\mathbb{E}\left[\Big{(}\prod_{j=1}^{l}\lvert
X^{j}_{1}\rvert\Big{)}\Big{(}\lvert X^{l}_{1}\rvert\mathds{1}_{\\{\lvert
X^{l}\rvert\geq T^{(l)}\\}}\Big{)}\Big{(}\prod_{j=l+1}^{d}\lvert
X^{j}_{1}\rvert\Big{)}\right]+\\\ \mathbb{E}\left[\Big{(}\prod_{j=1}^{l}\lvert
X^{j}_{1}\rvert\Big{)}\Big{(}\lvert X^{l}_{1}\rvert\mathds{1}_{\\{\lvert
X^{l}\rvert\geq T^{\prime(l)}\\}}\Big{)}\Big{(}\prod_{j=l+1}^{d}\lvert
X^{j}_{1}\rvert\Big{)}\right].$

Now, following the proof of Lemma A.2, we can show

$\displaystyle\lvert\bm{b}^{(l)}_{\bm{T},\bm{T}^{\prime}}\rvert$
$\displaystyle\leq\left[(T^{(l)})^{-k_{l}(1-\frac{d}{\overline{k}})}+(T^{\prime(l)})^{-k_{l}(1-\frac{d}{\overline{k}})}\right]\Big{(}\prod_{\begin{subarray}{c}j=1\\\
j\neq l\end{subarray}}^{d}\lVert X^{j}\rVert_{k_{j}}\Big{)}\lVert
X^{l}\rVert_{k_{l}}^{1+k_{l}(1-\frac{d}{\overline{k}})},$ $\displaystyle\leq
2(T^{(l)})^{-k_{l}(1-\frac{d}{\overline{k}})}\Big{(}\prod_{\begin{subarray}{c}j=1\\\
j\neq l\end{subarray}}^{d}\lVert X^{j}\rVert_{k_{j}}\Big{)}\lVert
X^{l}\rVert_{k_{l}}^{1+k_{l}(1-\frac{d}{\overline{k}})},$

where in the second line we used $T^{\prime(l)}\geq T^{(l)}$.

Summing in $l$ the controls we have just obtained for
$\lvert\bm{b}^{(l)}_{\bm{T},\bm{T}^{\prime}}\rvert$, we deduce
$\left\lvert\bm{b}_{\bm{T},\bm{T}^{\prime}}\right\rvert\leq
2\overline{\bm{b}}_{\bm{T}}$, from the definition (A.25). This proves the
lemma.  ∎

The following proposition shows that $\mathbb{B}_{T}$, defined in (4.16), can
be compared to the bias and heuristically justifies the choice (4.17).

######  Proposition A.4.

Assume that $\sum_{j=1}^{d}\frac{1}{k_{j}}<1$,
$\beta_{n}^{j}=\frac{\alpha_{j}}{\lfloor\log_{2}(n)\rfloor}$, for
$j=1,\dots,d$ and $\kappa_{n}=c_{0}\log_{2}(n)$ for some $c_{0}>0$. Then, if
$c_{0}$ is large enough, there exists $c>0$, $\overline{c}>0$, such that for
all ${\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T}$, $\forall n\geq 1$,
$(n\prod_{j=1}^{d}\alpha^{2}_{j})/\log(n)^{2d+1}\geq 1$,

$\mathbb{E}\left[\mathbb{B}_{\color[rgb]{0,0,0}\bm{T}}\right]\leq
c\overline{\bm{b}}^{2}_{\color[rgb]{0,0,0}\bm{T}}+\frac{c}{n^{\overline{c}}{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha^{2}_{j}}}.$

The constant $\overline{c}$ can be arbitrarily large if $c_{0}$ is chosen
large enough.

###### Proof.

For
$({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})\in\mathcal{T}^{2}$,
we write,

$\displaystyle\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}\rvert^{2}\leq
8\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}\left[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}\right]\right\rvert^{2}+8\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}\left[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}\right]\right\rvert^{2}+8\left\lvert\mathbb{E}\left[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}\right]-\mathbb{E}\left[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}\right]\right\rvert^{2},$

and deduce from (4.16) and (A.24) that

$\displaystyle\mathbb{B}_{T}$ $\displaystyle\leq
8\sum_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left\\{\left(\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\right)_{+}\right\\}$
$\displaystyle\qquad\qquad\qquad+8\sum_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left\\{\left(\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\right)_{+}\right\\}+8\mathbb{D}_{\color[rgb]{0,0,0}\bm{T}}^{2}$
$\displaystyle=:8\left[\mathbb{B}_{{\color[rgb]{0,0,0}\bm{T}}}^{(1)}+\mathbb{B}_{{\color[rgb]{0,0,0}\bm{T}}}^{(2)}+\mathbb{D}_{\color[rgb]{0,0,0}\bm{T}}^{2}\right].$
(A.26)

Using Lemma A.3, we see that the proposition will be proved as soon as we
show,

$\mathbb{E}\left[\mathbb{B}^{(l)}_{\color[rgb]{0,0,0}\bm{T}}\right]\leq\frac{c}{n^{\overline{c}}{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha_{j}^{2}}},\text{
for }{\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T},\text{ and }l=1,2.$ (A.27)

First, we focus on
$\mathbb{E}\left[\mathbb{B}^{(2)}_{\color[rgb]{0,0,0}\bm{T}}\right]$. For
${\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}$, we denote by
$g_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}:\mathbb{R}^{\color[rgb]{0,0,0}d}\times\mathbb{R}^{\color[rgb]{0,0,0}d}$
the function defined as
$g_{{\bm{T}}^{\prime}}(\bm{x},\bm{e})=g_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}(\bm{x},e_{1},\dots,e_{d})=\prod_{j=1}^{d}(\left[x_{j}\right]_{T^{\prime{(j)}}}+e_{j})$,
which is such that

${\color[rgb]{0,0,0}g_{{\bm{T}}^{\prime}}(\bm{X}_{i},{\color[rgb]{0,0,0}\mathcal{E}^{{(1)},T^{\prime{(1)}}}_{i},\dots,\mathcal{E}^{{(d)},T^{\prime{(d)}}}_{i}})=\prod_{j=1}^{d}\big{(}\left[X_{i}^{1}\right]_{T^{\prime{(j)}}}+\mathcal{E}^{(j),T^{\prime{(j)}}}_{i}\big{)}=\prod_{j=1}^{d}Z^{j,T^{\prime{(j)}}}_{i},}$

by (4.12). Thus,

$\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}\left[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}\right]=\frac{1}{n}\sum_{i=1}^{n}\left\\{g_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}(\bm{X}_{i},{\color[rgb]{0,0,0}\mathcal{E}^{{(1)},T^{\prime{(1)}}}_{i},\dots,\mathcal{E}^{{(d)},T^{\prime{(d)}}}_{i}})-\mathbb{E}\left[g_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}(\bm{X}_{i},{\color[rgb]{0,0,0}\mathcal{E}^{{(1)},T^{\prime{(1)}}}_{i},\dots,\mathcal{E}^{{(d)},T^{\prime{(d)}}}_{i}})\right]\right\\},$

recalling (4.13). We intend to apply Bernstein’s inequality and introduce a
set on which the random variables we consider are bounded. Let

$\Omega_{n}=\left\\{\omega\in\Omega\mid\forall
j\in{\color[rgb]{0,0,0}\\{1,\dots,d\\},}\leavevmode\nobreak\ \forall
T\in\mathcal{T}^{(j)},\leavevmode\nobreak\ \forall
i\in\\{1,\dots,n\\},\text{we have }\lvert\mathcal{E}_{i}^{{(j)},T}\rvert\leq
T\tilde{\kappa}_{n}^{(j)}\right\\}$

where
$\tilde{\kappa}_{n}^{(j)}=\frac{(2c_{0}+{\color[rgb]{0,0,0}8d})\log(n)}{\beta_{n}^{j}}$
for $j=1,\dots,d$, and $c_{0}$ is the constant given in the statement of the
proposition. We introduce the following lemma, its proof is postponed until
after the current proposition.

######  Lemma A.5.

We have $\mathbb{P}(\Omega_{n}^{c})\leq 2\frac{\lfloor
log_{2}(n)\rfloor}{n^{{\color[rgb]{0,0,0}4d}+c_{0}}}$.

We introduce a bounded modification of $g_{T^{\prime}}$ defined as

${\color[rgb]{0,0,0}\tilde{g}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}(\bm{X}_{i},\mathcal{E}^{1,T^{\prime{(1)}}}_{i},\dots,\mathcal{E}^{d,T^{\prime{(d)}}}_{i})=\prod_{j=1}^{d}\left(\left[X_{i}^{j}\right]_{T^{\prime{(j)}}}+\left[\mathcal{E}^{(j),T^{\prime{(j)}}}_{i}\right]_{T^{\prime{(j)}}\tilde{\kappa}_{n}^{(j)}}\right).}$

We have
$\lVert\tilde{g}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\rVert_{\infty}\leq{\color[rgb]{0,0,0}\prod_{j=1}^{d}\big{(}T^{\prime(j)}(1+\tilde{\kappa}_{n}^{(j)})\big{)}}=:M_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}$,
and with computations analogous to the ones giving (A.15), we can prove

${\color[rgb]{0,0,0}\mathop{var}\left(\tilde{g}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}(\bm{X}_{i},\mathcal{E}^{1,T^{\prime{(1)}}}_{i},\dots,\mathcal{E}^{j,T^{\prime{(j)}}}_{i})\right)\leq
C\frac{\prod_{j=1}^{d}\lvert
T^{\prime(j)}\rvert^{2}}{\prod_{j=1}^{d}\lvert\beta_{n}^{j}\rvert^{2}}}=:v_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}},$

for some universal constant $C$. We recall the Bernstein’s inequality (see
e.g. [9]) : for $({G}_{i})_{i=1,\dots,n}$ a iid sequence with $\lVert
G_{i}\rVert_{\infty} \leq M$ and $\mathop{var}({G}_{i})\leq v$,

$\displaystyle\mathbb{P}\left(\lvert\frac{1}{n}\sum_{i=1}^{n}{G}_{i}-\mathbb{E}[{G}_{i}]\rvert\geq
t\right)\leq 2\exp\left(-\frac{nt^{2}}{2(v+Mt)}\right)\leq
2\exp\left(-\frac{nt^{2}}{4v}\right)+2\exp\left(-\frac{nt}{4M}\right).$

As on $\Omega_{n}$, the random variables
${g}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}(\bm{X}_{i},\mathcal{E}^{1,T^{\prime{(1)}}}_{i},{\color[rgb]{0,0,0}\dots,\mathcal{E}^{d,T^{\prime{(d)}}}_{i}})$
and
$\tilde{g}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}(\bm{X}_{i},\mathcal{E}^{1,T^{\prime{(1)}}}_{i},{\color[rgb]{0,0,0}\dots,\mathcal{E}^{d,T^{\prime{(d)}}}_{i}})$
are almost surely equal, we deduce for $t\geq 0$,

$\mathbb{P}\left(\left\\{\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\geq
t;\leavevmode\nobreak\ \Omega_{n}\right\\}\right)\\\
=\mathbb{P}\left(\left\\{\lvert
n^{-1}\sum_{i=1}^{n}\tilde{g}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}(\bm{X}_{i},\mathcal{E}^{1,T^{\prime{(1)}}}_{i},{\color[rgb]{0,0,0}\dots,\mathcal{E}^{d,T^{\prime{(d)}}}_{i}})-\mathbb{E}[\tilde{g}_{T^{\prime}}(\bm{X}_{i},\mathcal{E}^{1,T^{\prime{(1)}}}_{i},{\color[rgb]{0,0,0}\dots,\mathcal{E}^{d,T^{\prime{(d)}}}_{i}})]\rvert\geq\sqrt{\frac{1}{16}\mathbb{V}_{T^{\prime}}+t};\leavevmode\nobreak\
\Omega_{n}\right\\}\right)\\\ \leq
2\exp\left(-\frac{n\left(\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}+t\right)}{4v_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right)+2\exp\left(-\frac{n\sqrt{\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}+t}}{4M_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right)\\\
\leq
2\exp\left(-\frac{n\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}{64v_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right)\exp\left(-\frac{nt}{4v_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right)+2\exp\left(\frac{-n\sqrt{\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}}{32M_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right)\exp\left(\frac{-n\sqrt{t}}{8M_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right).$
(A.28)

By (4.15), we have
$\frac{n\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}{v_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}=\frac{\kappa_{n}}{C}=\frac{c_{0}\ln(n)}{C}$
for some universal constant $C$, and
$\frac{n\sqrt{\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}}{M_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}=\frac{\sqrt{n}\sqrt{\kappa_{n}}}{\prod_{j=1}^{d}\beta_{n}^{j}\prod_{j=1}^{d}(1+\tilde{k}_{n}^{(j)})}$
is equal to
$\frac{\sqrt{n}\sqrt{c_{0}\log(n)}\lfloor\log_{2}(n)\rfloor^{\color[rgb]{0,0,0}2d}}{{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha_{j}}{\color[rgb]{0,0,0}\prod_{j=1}^{d}(1+(2c_{0}+8d)\frac{\log(n)\lfloor\log_{2}(n)\rfloor}{\alpha_{j}})}}\geq\frac{C^{\prime}{\color[rgb]{0,0,0}{\sqrt{n}}}}{(c_{0}+{\color[rgb]{0,0,0}4d})^{\color[rgb]{0,0,0}2d-1/2}\log(n)^{\color[rgb]{0,0,0}2d-1/2}}$
for some constant $C^{\prime}$. Hence,

$\mathbb{P}\left(\left\\{\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\geq
t;\leavevmode\nobreak\ \Omega_{n}\right\\}\right)\\\ \leq
2\exp\left(-\frac{c_{0}\ln(n)}{C64}\right)\exp\left(-\frac{nt}{4v_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right)+2\exp\left(-\frac{C^{\prime}{\color[rgb]{0,0,0}{\sqrt{n}}}}{{\color[rgb]{0,0,0}(c_{0}+2d)^{2d-1/2}\log(n)^{2d-1/2}}}\right)\exp\left(\frac{-n\sqrt{t}}{8M_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right).$

By choosing $c_{0}$ large enough, we have

$\mathbb{P}\left(\left\\{\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\geq
t;\leavevmode\nobreak\ \Omega_{n}\right\\}\right)\\\ \leq
Cn^{-\overline{c}}\left(\exp\left(-\frac{nt}{4v_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right)+\exp\left(\frac{-n\sqrt{t}}{8M_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right)\right),$

where $\overline{c}>0$ is any arbitrary constant. Since the previous control
is valid for any ${\color[rgb]{0,0,0}\bm{T}}^{\prime} \in\mathcal{T}$, we
deduce that,

$\mathbb{P}\left(\left\\{\sup_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left(\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\right)_{+}\geq
t;\leavevmode\nobreak\ \Omega_{n}\right\\}\right)\\\ \leq
Cn^{-\overline{c}}\sum_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left(\exp\left(-\frac{nt}{4v_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right)+\exp\left(\frac{-n\sqrt{t}}{8M_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}\right)\right).$

Integrating with respect to $t$ on $[0,\infty)$, we get

$\mathbb{E}\left[\sup_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left(\left\lvert\hat{\gamma}^{(T^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\right)_{+}\mathds{1}_{\Omega_{n}}\right]\\\
\leq
Cn^{-\overline{c}}\sum_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left(\frac{v_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}}{n}+\frac{M_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}^{2}}{n^{2}}\right).$

Using (4.11),
$v_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}=C{\color[rgb]{0,0,0}\frac{\prod_{j=1}^{d}T^{\prime(j)}}{\prod_{j=1}^{d}\lvert\beta_{n}^{j}\rvert^{2}}}\leq
C\frac{n^{{\color[rgb]{0,0,0}2d}}{\color[rgb]{0,0,0}{\log_{2}(n)}^{{\color[rgb]{0,0,0}2d}}}}{{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha_{j}^{2}}}$
and
$M_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}={\color[rgb]{0,0,0}\prod_{j=1}^{d}\big{(}T^{\prime(j)}(1+\tilde{\kappa}_{n}^{(j)})\big{)}}$
is upper bounded by $n^{d}\prod_{j=1}^{d}(1+\frac{C\log(n)^{2}}{\alpha_{j}})$,
we deduce

$\mathbb{E}\left[\sup_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left(\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\right)_{+}\mathds{1}_{\Omega_{n}}\right]\leq
Cn^{-\overline{c}}{\color[rgb]{0,0,0}\frac{n^{2d-1}\log(n)^{2d+1}}{\prod_{j=1}^{d}\alpha^{2}_{j}}}.$
(A.29)

We now study the contribution coming from the event $\Omega_{n}^{c}$. We have,
using the simple inequality $(a-b)_{+}\leq(a)_{+}$ and Jensen’s inequality

$\mathbb{E}\left[\sup_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left(\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\right)_{+}\mathds{1}_{\Omega_{n}^{c}}\right]\leq
2\sum_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\mathbb{E}\left[\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}\right\rvert^{2}\mathds{1}_{\Omega_{n}^{c}}\right].$

By using Cauchy–Schwarz’s inequality, it comes

$\displaystyle\mathbb{E}\left[\sup_{T^{\prime}\in\mathcal{T}}\left(\left\lvert\hat{\gamma}^{(T^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{(T^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{T^{\prime}}\right)_{+}\mathds{1}_{\Omega_{n}^{c}}\right]$
$\displaystyle\leq
2\sum_{T^{\prime}\in\mathcal{T}}\mathbb{E}\left[\left\lvert\hat{\gamma}^{(T^{\prime})}_{n}\right\rvert^{4}\right]^{1/2}\mathbb{P}(\Omega_{n}^{c})^{1/2}$
$\displaystyle\leq
2\sum_{T^{\prime}\in\mathcal{T}}\left[n^{-1}\sum_{i=1}^{n}\mathbb{E}({\color[rgb]{0,0,0}\lvert\prod_{j=1}^{d}Z^{j,T^{\prime(j)}}\rvert^{4}})\right]^{1/2}\mathbb{P}(\Omega_{n}^{c})^{1/2},$

where we used again Jensen’s inequality. Since $\mathbb{E}(\lvert
Z^{l,T^{\prime(l)}}\rvert)^{q}\leq C_{q}\frac{\lvert
T^{\prime(l)}\rvert^{q}}{\beta_{n}^{q}}$ for all $q\geq 1$ and
$l\in\\{1,\dots,d\\}$, we deduce,

$\displaystyle\mathbb{E}\left[\sup_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left(\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\right)_{+}\mathds{1}_{\Omega_{n}^{c}}\right]$
$\displaystyle\leq
C{\color[rgb]{0,0,0}\Big{(}\sum_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\frac{\prod_{j=1}^{d}\lvert
T^{\prime(j)}\rvert^{2}}{\prod_{j=1}^{d}\beta_{n}^{j}}\Big{)}}\mathbb{P}(\Omega_{n}^{c})^{1/2}$
$\displaystyle\leq
C\mathop{card}(\mathcal{T})\times\frac{n^{\color[rgb]{0,0,0}2d}}{{\color[rgb]{0,0,0}\prod_{j=1}^{d}\beta_{n}^{j}}}\times\frac{\sqrt{\log(n)}}{n^{{\color[rgb]{0,0,0}2d}+c_{0}/2}}$
$\displaystyle\leq
C\frac{\log(n)^{{\color[rgb]{0,0,0}3d+1/2}}}{{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha^{2}_{j}}\leavevmode\nobreak\
n^{c_{0}/2}}$ (A.30)

by Lemma A.5. Collecting (A.29) and (A.30), with the fact that $c_{0}$ can be
chosen arbitrarily large, and $\alpha\leq 1$, we have

$\mathbb{E}\left[\sup_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}\in\mathcal{T}}\left(\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{T^{\prime}}\right)_{+}\right]\leq\frac{C}{{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha^{2}_{j}}\leavevmode\nobreak\
n^{\overline{c}}}.$

This is exactly (A.27) with $l=2$. The proof of $\eqref{eq: control Bl preuve
control D}$ with $l=1$ is obtained similarly, remarking that the application
of the Bernstein’s inequality, with the same constants $M_{T^{\prime}}$,
$v_{T^{\prime}}$ still yields to the upper bound (A.28) for
$\mathbb{P}\left(\left\\{\left\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},{\color[rgb]{0,0,0}\bm{T}}^{\prime})}_{n}]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{{\color[rgb]{0,0,0}\bm{T}}^{\prime}}\geq
t;\leavevmode\nobreak\ \Omega_{n}\right\\}\right)$. ∎

###### Proof of Lemma A.5.

The set $\Omega_{n}^{c}$ is included in

$\bigcup_{j=1}^{\color[rgb]{0,0,0}d}\bigcup_{T^{(j)}\in\mathcal{T}^{(j)}}\\{\lvert\mathcal{E}^{(j),T^{(j)}}\rvert\geq
T^{(j)}\tilde{\kappa}_{n}^{(j)}\\}.$

But $\mathcal{E}^{(j),T^{(j)}}/T^{(j)}$ is distributed as a Laplace
$\frac{2}{\beta_{n}^{j}}\times\mathcal{L}(1)$ variable, and we deduce

$\mathbb{P}\left(\Omega_{n}^{c}\right)\leq{\color[rgb]{0,0,0}\sum_{j=1}^{d}\mathop{card}\left(\mathcal{T}^{(j)}\right)\mathbb{P}\left(\frac{2}{\beta_{n}^{j}}\left\lvert\mathcal{L}(1)\right\rvert\geq\tilde{\kappa}_{n}^{(j)}\right)}\leq
2\lfloor\log_{2}(n)\rfloor
e^{-\tilde{\kappa}_{n}\beta_{n}^{{\color[rgb]{0,0,0}(j)}}/2}\\\
=2\lfloor\log_{2}(n)\rfloor
e^{-\ln(n)(2c_{0}+{\color[rgb]{0,0,0}8d})/2}=2\lfloor\log_{2}(n)\rfloor
n^{-{\color[rgb]{0,0,0}4d}-c_{0}},$

as we wanted. ∎

######  Proposition A.6.

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

$\mathbb{E}\left[(\hat{\gamma}^{\widehat{T}}_{n}-\gamma)^{2}\right]\leq
c\inf_{{\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T}}[\overline{\bm{b}}_{\color[rgb]{0,0,0}\bm{T}}^{2}+\mathbb{V}_{\color[rgb]{0,0,0}\bm{T}}]+\frac{c}{{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha^{2}_{j}\leavevmode\nobreak\
n^{\overline{c}_{0}}}},$

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

###### Proof.

Let ${\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T}$, we have

$\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}})}-\gamma\rvert\leq\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}})}-\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}},{\color[rgb]{0,0,0}\bm{T}})}\rvert+\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}},{\color[rgb]{0,0,0}\bm{T}})}-\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}\rvert+\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}-\gamma\rvert.$

From the definition (A.24), we have
$\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}-\gamma\rvert\leq\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}]\rvert+\lvert\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}-\gamma]\rvert\leq\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}]\rvert+\mathbb{D}_{\color[rgb]{0,0,0}\bm{T}}$,
and it follows

$\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}})}-\gamma\rvert\leq\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}})}-\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}},{\color[rgb]{0,0,0}\bm{T}})}\rvert+\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}},{\color[rgb]{0,0,0}\bm{T}})}-\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}\rvert+\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}]\rvert+\mathbb{D}_{\color[rgb]{0,0,0}\bm{T}}.$

By (4.16), we have
$\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}},{\color[rgb]{0,0,0}\bm{T}})}-\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}\rvert^{2}\leq\mathbb{B}_{\widehat{{\color[rgb]{0,0,0}\bm{T}}}}+\mathbb{V}_{\widehat{{\color[rgb]{0,0,0}\bm{T}}}}$,
and recalling
$\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}},{\color[rgb]{0,0,0}\bm{T}})}=\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}},\widehat{{\color[rgb]{0,0,0}\bm{T}}})}$,
we also get
$\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}})}-\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}},{\color[rgb]{0,0,0}\bm{T}})}\rvert^{2}\leq\mathbb{B}_{{{\color[rgb]{0,0,0}\bm{T}}}}+\mathbb{V}_{{{\color[rgb]{0,0,0}\bm{T}}}}$.
Thus,

$\lvert\hat{\gamma}^{(\widehat{\color[rgb]{0,0,0}\bm{T}})}-\gamma\rvert^{2}\leq
16\left[\mathbb{B}_{\widehat{{\color[rgb]{0,0,0}\bm{T}}}}+\mathbb{V}_{\widehat{{\color[rgb]{0,0,0}\bm{T}}}}+\mathbb{B}_{{{\color[rgb]{0,0,0}\bm{T}}}}+\mathbb{V}_{{{\color[rgb]{0,0,0}\bm{T}}}}+\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}]\rvert^{2}+\mathbb{D}_{{\color[rgb]{0,0,0}\bm{T}}}^{{\color[rgb]{0,0,0}2}}\right].$

Using (4.17), we deduce

$\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}})}-\gamma\rvert^{2}\leq
16\left[2\mathbb{B}_{{{\color[rgb]{0,0,0}\bm{T}}}}+2\mathbb{V}_{{{\color[rgb]{0,0,0}\bm{T}}}}+\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}]\rvert^{2}+\mathbb{D}_{{\color[rgb]{0,0,0}\bm{T}}}^{{\color[rgb]{0,0,0}2}}\right].$

From the study of the variance of
$\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}$ as in (A.15), we have
$\mathbb{E}[\lvert\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}-\mathbb{E}[\hat{\gamma}^{({\color[rgb]{0,0,0}\bm{T}})}]\rvert^{2}]\leq
Cn^{-1}{\color[rgb]{0,0,0}\frac{\prod_{j=1}^{d}\lvert
T^{(j)}\rvert^{2}}{\prod_{j=1}^{d}\lvert\beta_{n}^{j}\rvert^{2}}}$, which is
smaller than $\mathbb{V}_{T}$, if $c_{0}$ in (4.15) is large enough. Thus, we
deduce

$\mathbb{E}\left[\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}})}-\gamma\rvert^{2}\right]\leq
16\left[2\mathbb{E}[\mathbb{B}_{{{\color[rgb]{0,0,0}\bm{T}}}}]+3\mathbb{V}_{{{\color[rgb]{0,0,0}\bm{T}}}}+\mathbb{D}_{{\color[rgb]{0,0,0}\bm{T}}}^{{\color[rgb]{0,0,0}2}}\right].$

Now, Lemma A.3 and Proposition A.4 yield to

$\mathbb{E}\left[\lvert\hat{\gamma}^{(\widehat{{\color[rgb]{0,0,0}\bm{T}}})}-\gamma\rvert^{2}\right]\leq
c\left[\overline{\bm{b}}_{\color[rgb]{0,0,0}\bm{T}}^{2}+\mathbb{V}_{\color[rgb]{0,0,0}\bm{T}}\right]+\frac{c}{{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha^{2}_{j}}\leavevmode\nobreak\
n^{\overline{c}_{0}}},$

for any ${\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T}$. This proves the
proposition. ∎

We end this section by providing the proof of Theorem 4.15

###### Proof of Theorem 4.15.

By Proposition A.6, it is sufficient to evaluate
$\inf_{{\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T}}\left[\overline{\bm{b}}_{\color[rgb]{0,0,0}\bm{T}}^{2}+\mathbb{V}_{\color[rgb]{0,0,0}\bm{T}}\right]$
which is, up to a constant, the infimum over
${\color[rgb]{0,0,0}\bm{T}}\in\mathcal{T}$ of

$\displaystyle{\color[rgb]{0,0,0}\sum_{j=1}^{d}(T^{(j)})^{-2k_{j}(1-\frac{d}{\overline{k}})}+n^{-1}\kappa_{n}\frac{\prod_{j=1}^{d}\lvert
T^{(j)}\rvert^{2}}{\prod_{j=1}^{d}\lvert\beta_{n}^{j}\rvert^{2}}}$
$\displaystyle\leq{\color[rgb]{0,0,0}\sum_{j=1}^{d}(T^{(j)})^{-2k_{j}(1-\frac{d}{\overline{k}})}+Cn^{-1}\log(n)^{2d+1}\frac{\prod_{j=1}^{d}\lvert
T^{(j)}\rvert^{2}}{\prod_{j=1}^{d}\alpha^{2}_{j}}},$ (A.31)

for some $C>0$. If we set
$T^{*(j)}=\left(\frac{n{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha_{j}^{2}}}{\log(n)^{\color[rgb]{0,0,0}2d+1}}\right)^{1/(2k_{\color[rgb]{0,0,0}j})}$
for $j\in\\{1,\dots,d\\}$, the above quantity is smaller than some constant
time

$\left(\frac{\log(n)^{\color[rgb]{0,0,0}2d+1}}{n{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha_{j}^{2}}}\right)^{\frac{\overline{k}-{\color[rgb]{0,0,0}d}}{\overline{k}}},$

which is the expected rate. It remains to check that the same rate can be
obtained by restricting $T$ in $\mathcal{T}$. As
$(n{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha_{j}^{2}})/(\log(n))^{\color[rgb]{0,0,0}2d+1}\geq
1$, and $\alpha_{j}\leq 1$, we see that for $n\geq 3$, $T^{*(j)}\in[1,n]$ for
$j\in\\{1,\dots,d\\}$. By the definition (4.11) of $\mathcal{T}^{(j)}$, we see
that $\mathcal{T}^{(j)}$ is a grid of $[1,n]$ such that for any
$t^{*}\in[1,n]$, there exists $t^{(j)}\in\mathcal{T}^{(j)}$ with
$\frac{1}{2}t^{*}\leq t^{(j)}\leq 2t^{*}$. Hence, by replacing the $T^{*(j)}$
by their closest values in $\mathcal{T}^{j}$ we only increase the value of
(A.31) by a multiplicative constant. We deduce

$\inf_{T\in\mathcal{{\color[rgb]{0,0,0}\bm{T}}}}\left[\overline{\bm{b}}_{\color[rgb]{0,0,0}\bm{T}}^{2}+\mathbb{V}_{\color[rgb]{0,0,0}\bm{T}}\right]\leq
c\left(\frac{\log(n)^{\color[rgb]{0,0,0}2d+1}}{n{\color[rgb]{0,0,0}\prod_{j=1}^{d}\alpha_{j}^{2}}}\right)^{\frac{\overline{k}-{\color[rgb]{0,0,0}d}}{\overline{k}}},$

and Theorem 4.15 follows from Proposition A.6. ∎

###  A.4 Proof locally private density estimation

This section is devoted to the proof of the results stated in Section 4.3,
about the density estimation under $\alpha$-CLDP constraints.

We start by proving that $Z_{i}^{j}$ defined according to (4.19) are
$\alpha_{j}$ local differential private view of the observation $X_{i}^{j}$,
as stated in Lemma 4.17.

###### Proof of Lemma 4.17.

The density of $\mathcal{E}_{i}^{j}$ at the point $x\in\mathbb{R}$ is given by
the value
$\frac{1}{2\kappa}\alpha_{j}h\exp(-\frac{1}{2\kappa}\alpha_{j}h|x|)$. Then,
the reverse triangle inequality and the fact the infinity norm of $K$ is
bounded by $\kappa$ provide

$\displaystyle\sup_{z\in\mathcal{Z}}\frac{q^{j}(z|X_{i}^{j}=x)}{q^{j}(z|X_{i}^{j}=x^{\prime})}$
$\displaystyle\leq\sup_{z\in\mathcal{Z}}\exp\Big{(}-\frac{1}{2\kappa}\alpha_{j}h\lvert
z-\frac{1}{h}K(\frac{x-x_{0}^{j}}{h})\rvert+\frac{1}{2\kappa}\alpha_{j}h\lvert
z-\frac{1}{h}K(\frac{x^{\prime}-x_{0}^{j}}{h})\rvert\Big{)}$
$\displaystyle\leq\exp\Big{(}\frac{1}{2\kappa}\alpha_{j}h\frac{1}{h}\lvert
K(\frac{x-x_{0}^{j}}{h})-K(\frac{x^{\prime}-x_{0}^{j}}{h})\rvert\Big{)}$
$\displaystyle\leq\exp(\alpha_{j}).$

∎

###### Proof of Theorem 4.18..

The proof is based on the usual bias-variance decomposition. We have indeed
$\mathbb{E}[|\hat{\pi}^{Z}_{h}(\bm{x_{0}})-\pi(\bm{x_{0}})|^{2}]=|\mathbb{E}[\hat{\pi}^{Z}_{h}(\bm{x_{0}})]-\pi(\bm{x_{0}})|^{2}+var(\hat{\pi}^{Z}_{h}(\bm{x_{0}})).$
One can easily bound the bias part (see for example Proposition 1.2 in [39]),
obtaining for any $\bm{x_{0}}\in\mathbb{R}^{d}$ and any $h>0$

${}|\mathbb{E}[\hat{\pi}^{Z}_{h}(\bm{x_{0}})]-\pi(\bm{x_{0}})|^{2}\leq
ch^{2\beta},$ (A.32)

for some $c>0$. Regarding the variance of $\hat{\pi}^{Z}_{h}(\bm{x_{0}})$, we
use its explicit form and the fact that the vectors
$\bm{X}_{1},\dots,\bm{X}_{n}$ and the Laplace random variables are independent
to get

$\displaystyle var(\hat{\pi}^{Z}_{h}(\bm{x_{0}}))$
$\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{n}var\Big{(}\prod_{j=1}^{d}(\frac{1}{h}K(\frac{X_{i}^{j}-x_{0}^{j}}{h})+\mathcal{E}_{i}^{j})\Big{)}$
$\displaystyle=\frac{1}{n^{2}}\sum_{i=1}^{n}var\Big{(}\sum_{I_{k}}\prod_{j\in
I_{k}}\frac{1}{h}K(\frac{X_{i}^{j}-x_{0}^{j}}{h})\prod_{j\in(I_{k})^{c}}\mathcal{E}_{i}^{j}\Big{)}$

where $I_{k}$ is a set of index such that $|I_{k}|=k$, for
$k\in\\{1,\dots,d\\}$. Then, it is well known that
$var(\frac{1}{h^{d}}\prod_{j=1}^{d}K(\frac{X_{i}^{j}-x_{0}^{j}}{h}))\leq\frac{c}{h^{d}}$
for some positive $c$ (one can easily see that by adapting Proposition 1.1 in
[39] to the multidimensional context). Moreover, by construction,
$\mathcal{E}_{i}^{j}$ are iid $\sim\mathcal{L}(\frac{2\kappa}{\alpha_{j}h})$,
which guarantees that
$var(\prod_{j=1}^{d}\mathcal{E}_{i}^{j})\leq\frac{c}{\prod_{j=1}^{d}(\alpha_{j}h)^{2}}.$
One can then readily check that, for any set of index $I_{k}$ such that
$|I_{k}|=k$, it is

$var(\prod_{j\in
I_{k}}\frac{1}{h}K(\frac{X_{i}^{j}-x_{0}^{j}}{h})\prod_{j\in(I_{k})^{c}}\mathcal{E}_{i}^{j})\leq\frac{c}{h^{k}}\frac{1}{h^{2(d-k)}}\prod_{j\in(I_{k})^{c}}\frac{1}{\alpha_{j}^{2}}.$

It implies

$\displaystyle{}var(\hat{\pi}^{Z}_{h}(\bm{x_{0}}))\leq\frac{1}{n}\sum_{k=0}^{d}\frac{c}{h^{k}}\frac{1}{h^{2(d-k)}}\sum_{I_{k}}\prod_{j\in(I_{k})^{c}}\frac{1}{\alpha_{j}^{2}}=\frac{c}{nh^{2d}\prod_{j=1}^{d}\alpha_{j}^{2}}\sum_{k=0}^{d}\sum_{I_{k}}\prod_{j\in
I_{k}}(h\alpha_{j}^{2}).$ (A.33)

We now recall that $h$ is a bandwidth we have assumed being smaller than $1$.
We have also required $\alpha_{j}\leq 1$ for any $j\in\\{1,\dots,d\\}$, which
yields $h\alpha_{j}^{2}<1$ for any $j\in\\{1,\dots,d\\}$. Then, the largest
term in the sum above is the one for which $k=0$, which means that
$I_{k}=\emptyset$. We derive

${}var(\hat{\pi}^{Z}_{h}(\bm{x_{0}}))\leq\frac{c}{nh^{2d}\prod_{j=1}^{d}\alpha_{j}^{2}}.$
(A.34)

We then look for the choice of $h$ that realizes the trade-off between the
bound on the variance here above and the bound on the bias term gathered in
(A.32). This is achieved by the rate optimal bandwidth
$h^{*}:=(\frac{1}{n\,\prod_{j=1}^{d}\alpha_{j}^{2}})^{\frac{1}{2(\beta+d)}}.$
We remark that, as by hypothesis it is
$n\prod_{j=1}^{d}\alpha_{j}^{2}\rightarrow\infty$ for $n\rightarrow\infty$, it
clearly follows $h^{*}=h^{*}_{n}\rightarrow 0$ for $n\rightarrow\infty$.
Replacing it in (A.32) and (A.34) we obtain
$\mathbb{E}[|\hat{\pi}^{Z}_{h}(\bm{x_{0}})-\pi(\bm{x_{0}})|^{2}]\leq
c\Big{(}\frac{1}{n\,\prod_{j=1}^{d}\alpha_{j}^{2}}\Big{)}^{\frac{\beta}{\beta+d}},$
which concludes the proof. ∎

###### Proof of Theorem 4.19.

We observe that, for $\alpha_{1}=\dots=\alpha_{d}=\alpha$, (A.33) translates
to
$var(\hat{\pi}^{Z}_{h}(\bm{x_{0}}))\leq\frac{c}{n(h\alpha)^{2d}}\sum_{k=0}^{d}(h\alpha^{2})^{k}$.
Then, we consider two different cases.

$\bullet$ If $\alpha\geq n^{\frac{1}{2(2\beta+d)}}$, we choose the optimal
bandwidth as in the privacy free-context
$h^{*}:=(\frac{1}{n})^{\frac{1}{2\beta+d}}.$ We observe we have in this case
$h\alpha^{2}\geq n^{-\frac{1}{2\beta+d}+\frac{1}{2\beta+d}}=1.$ Hence, in
(A.33), the worst term is the one for which $k=d$. It implies the variance of
$\hat{\pi}^{Z}_{h}(\bm{x_{0}})$ is bounded by

$\displaystyle\frac{c}{n(h\alpha)^{2d}}(h\alpha^{2})^{d}=\frac{c}{nh^{d}}=c(\frac{1}{n})^{\frac{2\beta}{2\beta+d}}.$

We observe that the bandwidth $h^{*}$ is the one that achieves the balance in
the decomposition bias-variance, as it is also
$(h^{*})^{2\beta}=(\frac{1}{n})^{\frac{2\beta}{2\beta+d}}$. The proof in the
first case is then concluded.

$\bullet$ Consider now what happens for $\alpha<n^{\frac{1}{2(2\beta+d)}}$. In
this case, we will see that the optimal choice in terms of convergence rate
will consist in taking
$h^{*}:=(\frac{1}{n\,\alpha^{2d}})^{\frac{1}{2(\beta+d)}}.$ Remark that we
have assumed $n\alpha^{2d}\rightarrow\infty$ for $n\rightarrow\infty$ so that
$h^{*}\rightarrow 0$, for $n$ going to $\infty$. We observe in this context it
is

$\displaystyle
h^{*}\alpha^{2}=(\frac{1}{n\,\alpha^{2d}})^{\frac{1}{2(\beta+d)}}\alpha^{2}=(\frac{1}{n})^{\frac{1}{2(\beta+d)}}\alpha^{\frac{2\beta+d}{\beta+d}}\leq(\frac{1}{n})^{\frac{1}{2(\beta+d)}}n^{\frac{1}{2(\beta+d)}}=1.$

Thus, the largest term in the sum in (A.33) is for $k=0$, which implies

$\displaystyle
var(\hat{\pi}^{Z}_{h}(\bm{x_{0}}))\leq\frac{c}{n(h\alpha)^{2d}}=\frac{c}{n\alpha^{2d}}(n\alpha^{2d})^{\frac{d}{\beta+d}}=c(\frac{1}{n\alpha^{2d}})^{\frac{\beta}{\beta+d}}.$

The bandwidth $h^{*}$ realizes the balance between the variance and the bias,
as $(h^{*})^{2\beta}=(\frac{1}{n\alpha^{2d}})^{\frac{\beta}{\beta+d}}$. The
proof is then complete.

∎

####  A.4.1 Proof adaptive procedure

We start by proving that $Z_{i}^{j}$ defined according to (4.12) are
$\alpha_{j}$ local differential private view of the observation $X_{i}^{j}$,
as stated in Lemma 4.24.

###### Proof of Lemma 4.24.

From the definition of Laplace, using the independence of the variables
$(Z_{i}^{j,h})_{h\in H_{n}}$ and denoting as $q^{j}((z^{j,h})_{h\in
H_{n}}|X_{i}^{j}=x)$ the density of the law of $Z_{i}^{j,h}$ conditional to
$X_{i}^{j}=x\in\mathbb{R}$ we obtain

$\displaystyle\frac{q^{j}((z^{j,h})_{h\in
H_{n}}|X_{i}^{j}=x)}{q^{j}((z^{j,h})_{h\in H_{n}}|X_{i}^{j}=x^{\prime})}$
$\displaystyle=\frac{\prod_{h\in
H_{n}}\exp(|z^{j,h}-\frac{1}{h}K(\frac{x-x_{0}^{j}}{h})|\frac{\beta_{n}^{j}\,h}{2\kappa})}{\prod_{h\in
H_{n}}\exp(|z^{j,h}-\frac{1}{h}K(\frac{x^{\prime}-x_{0}^{j}}{h})|\frac{\beta_{n}^{j}\,h}{2\kappa})}$
$\displaystyle\leq\prod_{h\in
H_{n}}\exp(|K(\frac{x-x_{0}^{j}}{h})-K(\frac{x^{\prime}-x_{0}^{j}}{h})|\frac{\beta_{n}^{j}}{2\kappa})$
$\displaystyle\leq\prod_{h\in H_{n}}\exp(\beta_{n}^{j})$
$\displaystyle=\exp(Card(H_{n})\beta_{n}^{j})\leq\exp(\alpha_{j}),$

being the last a consequence of how we have chosen $\beta_{n}^{j}$. ∎

Before proving the main theorem, let us introduce the notation
$\pi_{h}^{z}(\bm{x_{0}})$ for $\mathbb{E}[\hat{\pi}_{h}^{z}(\bm{x_{0}})]$ and

$\displaystyle{}\mathbb{D}_{h}$ $\displaystyle:=\Big{(}\sup_{\eta\in
H_{n}}|\mathbb{E}[\hat{\pi}_{\eta\land
h}^{z}(\bm{x_{0}})-\hat{\pi}_{h}^{z}(\bm{x_{0}})]|\Big{)}\lor|\mathbb{E}[\hat{\pi}_{h}^{z}(\bm{x_{0}})]-\pi(\bm{x_{0}})|$
(A.35)
$\displaystyle=\Big{(}\sup_{\eta<h}|\mathbb{E}[\hat{\pi}_{\eta}^{z}(\bm{x_{0}})-\hat{\pi}_{h}^{z}(\bm{x_{0}})]|\Big{)}\lor|\mathbb{E}[\hat{\pi}_{h}^{z}(\bm{x_{0}})]-\pi(\bm{x_{0}})|.$

As for (A.32), with classical computations as in Proposition 1.2 of [39] it
readily follows, for some $c>0$,

${}\mathbb{D}_{h}\leq ch^{\beta}.$ (A.36)

The proof of Theorem 4.25 heavily relies on the following proposition.

######  Proposition A.7.

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

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

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

###### Proof of Proposition A.7.

Let $h\in H_{n}$. It is

$|\hat{\pi}_{\hat{h}}^{z}(\bm{x_{0}})-\pi(\bm{x_{0}})|\leq|\hat{\pi}_{\hat{h}}^{z}(\bm{x_{0}})-\hat{\pi}_{\hat{h},h}^{z}(\bm{x_{0}})|+|\hat{\pi}_{\hat{h},h}^{z}(\bm{x_{0}})-\hat{\pi}_{h}^{z}(\bm{x_{0}})|+|\hat{\pi}_{h}^{z}(\bm{x_{0}})-\pi(\bm{x_{0}})|.$

Following the same computations as in the proof of Proposition A.6 it is then
easy to check that

$\mathbb{E}[|\hat{\pi}_{\hat{h}}^{z}(\bm{x_{0}})-\pi(\bm{x_{0}})|^{2}]\leq
c\Big{(}\mathbb{E}[\mathbb{B}_{h}]+\mathbb{V}_{h}+\mathbb{D}_{h}^{2}\Big{)}.$

Next, we study in detail $\mathbb{E}[\mathbb{B}_{h}]$. Splitting
$\mathbb{B}_{h}$ in a way analogous to (A.4.1) in Proposition A.4 we have

$\displaystyle\mathbb{B}_{h}$ $\displaystyle\leq 8\sum_{\eta\in
H_{n}}\left\\{\left(\left\lvert\hat{\pi}^{z}_{h,\eta}(\bm{x_{0}})-\mathbb{E}[\hat{\pi}^{z}_{h,\eta}(\bm{x_{0}})]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{\eta}\right)_{+}\right\\}$
$\displaystyle\qquad\qquad\qquad+8\sum_{\eta\in
H_{n}}\left\\{\left(\left\lvert\hat{\pi}^{z}_{\eta}(\bm{x_{0}})-\mathbb{E}[\hat{\pi}^{z}_{\eta}(\bm{x_{0}})]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{\eta}\right)_{+}\right\\}+8\mathbb{D}_{h}^{2}$
$\displaystyle=:8\left[\mathbb{B}_{h}^{(1)}+\mathbb{B}_{h}^{(2)}+\mathbb{D}_{h}^{2}\right].$

Hence, Proposition A.7 will be proven once we show that

${}\mathbb{E}[\mathbb{B}_{h}^{(l)}]\leq\frac{c}{n^{\bar{c}}}\frac{1}{\prod_{j=1}^{d}\alpha_{j}^{2}}$
(A.37)

for $h\in H_{n}$ and $l=1,2$. We start by considering
$\mathbb{E}[\mathbb{B}_{h}^{(2)}]$. Similarly as in Proposition A.7, we
introduce for any $\eta\in H_{n}$ the function
$g:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R},$ defined as

$g_{\eta}(x^{1},\dots,x^{d},e^{1},\dots,e^{d})=(\frac{1}{\eta}K(\frac{x^{1}-x_{0}^{1}}{\eta})+e^{1})\times\dots\times(\frac{1}{\eta}K(\frac{x^{d}-x_{0}^{d}}{\eta})+e^{d}).$

It is such that

$\displaystyle
g_{\eta}({X_{i}}^{1},\dots,X_{i}^{d},\mathcal{E}_{i}^{1,\eta},\dots,\mathcal{E}_{i}^{d,\eta})$
$\displaystyle=(\frac{1}{\eta}K(\frac{{X_{i}}^{1}-x_{0}^{1}}{\eta})+\mathcal{E}_{i}^{1,\eta})\times\dots\times(\frac{1}{\eta}K(\frac{X_{i}^{d}-x_{0}^{d}}{\eta})+\mathcal{E}_{i}^{d,\eta})$
$\displaystyle=Z_{i}^{1,\eta}\times\dots\times Z_{i}^{d,\eta}.$

Hence, we can write

$\hat{\pi}^{z}_{\eta}(\bm{x_{0}})-\mathbb{E}[\hat{\pi}^{z}_{\eta}(\bm{x_{0}})]=\frac{1}{n}\sum_{i=1}^{n}\left\\{g_{\eta}(\bm{X}_{i},\bm{\mathcal{E}}_{i}^{\eta})-\mathbb{E}[g_{\eta}(\bm{X}_{i},\bm{\mathcal{E}}_{i}^{\eta})]\right\\}.$

As in the proof of Proposition A.4 we want to apply Bernstein’s inequality,
for which we need the variables to be bounded. For this reason we introduce

$\tilde{\Omega}_{n}=\left\\{\omega\in\Omega\mid\forall
j\in\\{1,\dots,d\\}\leavevmode\nobreak\ \forall
l\in\\{1,2\\},\leavevmode\nobreak\ \forall h\in H_{n},\leavevmode\nobreak\
\forall i\in\\{1,\dots,n\\},\text{we have
}\lvert\mathcal{E}_{i}^{j,h}\rvert\leq\frac{\tilde{a}_{n}^{j}}{h}\right\\},$

where $\tilde{a}_{n}^{j}:=\frac{\log n}{\beta_{n}^{j}}2\kappa(c_{0}+4d)$,
$\kappa$ is as in (4.18) and $c_{0}$ is the constant given in the statement.
Then, we can modify $g_{\eta}$. We set

$\displaystyle\tilde{g_{\eta}}({X_{i}}^{1},\dots,X_{i}^{d},\mathcal{E}_{i}^{1,\eta},\dots,\mathcal{E}_{i}^{d,\eta}):=(\frac{1}{\eta}K(\frac{{X_{i}}^{1}-x_{0}^{1}}{\eta})+[\mathcal{E}_{i}^{1,\eta}]_{\frac{\tilde{a}_{n}^{1}}{\eta}})\times\dots\times(\frac{1}{\eta}K(\frac{X_{i}^{d}-x_{0}^{d}}{\eta})+[\mathcal{E}_{i}^{d,\eta}]_{\frac{\tilde{a}_{n}^{d}}{\eta}}),$

where we have used the same notation as in Section 4.2.1 to denote the
truncation of the Laplace random variables.
Following the proof of Lemma A.5 it is easy to check that

${}\mathbb{P}(\tilde{\Omega}_{n}^{c})\leq
d\frac{\lfloor\log_{2}n\rfloor}{n^{4d+c_{0}}}.$ (A.38)

Indeed, $\tilde{\Omega}_{n}^{c}$ is included in $\cup_{j=1}^{d}\cup_{h\in
H_{n}}\\{|\mathcal{E}_{i}^{j,h}|\geq\frac{\tilde{a}_{n}^{j}}{h}\\}$, with
$h\mathcal{E}_{i}^{j,h}$ distributed as
$\frac{2\kappa}{\beta_{n}^{j}}\mathcal{L}(1)$. Hence,

$\displaystyle\mathbb{P}(\tilde{\Omega}_{n}^{c})$ $\displaystyle\leq
Card(H_{n})\sum_{j=1}^{d}\mathbb{P}(\frac{2\kappa}{\beta_{n}^{j}}|\mathcal{L}(1)|\geq\tilde{a}_{n}^{j})\leq\lfloor\log_{2}n\rfloor\sum_{j=1}^{d}e^{-\frac{\tilde{a}^{j}_{n}\beta_{n}^{j}}{2\kappa}}\leq
d\lfloor\log_{2}n\rfloor n^{-4d-c_{0}},$

as we have chosen $\tilde{a}^{j}_{n}:=\frac{\log
n}{\beta_{n}^{j}}2\kappa(c_{0}+4d)$.
We observe that

${}\left\|\tilde{g}_{\eta}\right\|_{\infty}\leq\frac{1}{\eta^{d}}(\kappa+\tilde{a}_{n}^{1})\times...\times(\kappa+\tilde{a}_{n}^{d})=:M_{\eta}.$
(A.39)

Acting as in the proof of Theorem 4.18 (see in particular (A.33)) it is
moreover easy to see that

$\displaystyle{}var(\tilde{g_{\eta}}({X_{i}}^{1},...,X_{i}^{d},\mathcal{E}_{i}^{1,\eta},...,\mathcal{E}_{i}^{d,\eta}))$
$\displaystyle\leq\frac{c}{\eta^{2d}}\frac{1}{\prod_{j=1}^{d}(\beta_{n}^{j})^{2}}\sum_{k=0}^{d}\prod_{j=1}^{k}\eta(\beta_{n}^{j})^{2}\leq\frac{c}{\eta^{2d}}\frac{1}{\prod_{j=1}^{d}(\beta_{n}^{j})^{2}}=:v_{\eta},$
(A.40)

where we have used that $\eta(\beta_{n}^{j})^{2}\leq 1$. We then apply
Bernstein inequality (similarly to the proof of Proposition A.4) to the random
variables $\tilde{g_{\eta}}$, on $\tilde{\Omega}_{n}$. It follows, as in
(A.28),

$\mathbb{P}\left(\left\\{\left\lvert\hat{\pi}^{z}_{\eta}(\bm{x_{0}})-\mathbb{E}[\hat{\pi}^{z}_{\eta}(\bm{x_{0}})]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{\eta}\geq
t;\leavevmode\nobreak\ \tilde{\Omega}_{n}\right\\}\right)\\\
=\mathbb{P}\left(\left\\{\lvert
n^{-1}\sum_{i=1}^{n}\tilde{g}_{\eta}(\bm{X}_{i},\bm{\mathcal{E}}^{\eta}_{i})-\mathbb{E}[\tilde{g}_{\eta}(\bm{X}_{i},\bm{\mathcal{E}}^{\eta}_{i})]\rvert\geq\sqrt{\frac{1}{16}\mathbb{V}_{\eta}+t};\leavevmode\nobreak\
\tilde{\Omega}_{n}\right\\}\right)\\\ \leq
2\exp\left(-\frac{n\mathbb{V}_{\eta}}{64v_{\eta}}\right)\exp\left(-\frac{nt}{4v_{\eta}}\right)+2\exp\left(\frac{-n\sqrt{\mathbb{V}_{\eta}}}{32M_{\eta}}\right)\exp\left(\frac{-n\sqrt{t}}{8M_{\eta}}\right).$

We now have
$n\frac{\mathbb{V}_{\eta}}{v_{\eta}}=\frac{a_{n}}{c}=\frac{c_{0}\log n}{c}$
for some universal constant $c$. Moreover,

$\displaystyle\frac{n\sqrt{\mathbb{V}_{\eta}}}{M_{\eta}}$
$\displaystyle=n\sqrt{a_{n}\frac{1}{n\eta^{2d}}\frac{1}{\prod_{j=1}^{d}(\beta_{n}^{j})^{2}}}\eta^{d}\frac{1}{
\prod_{j=1}^{d}(\kappa+\tilde{a}_{n}^{j})}$
$\displaystyle=\sqrt{n}\sqrt{c_{0}\log
n}\frac{1}{\prod_{j=1}^{d}(\kappa+\frac{\log
n}{\beta_{n}^{j}}2\kappa(c_{0}+4d))}\frac{1}{\prod_{j=1}^{d}(\beta_{n}^{j})^{2}}$
$\displaystyle=\sqrt{n}\sqrt{c_{0}\log
n}\frac{1}{\prod_{j=1}^{d}(\kappa+\frac{\log
n\,\lfloor\log_{2}n\rfloor}{\alpha_{j}}2\kappa(c_{0}+4d))}\frac{(\lfloor\log_{2}n\rfloor)^{2d}}{\prod_{j=1}^{d}\alpha_{j}^{2}}$
$\displaystyle\geq c^{\prime}\sqrt{n}(\log n)^{\frac{1}{2}}$

for some constant $c^{\prime}$. Then, we can follow the arguing in Proposition
A.4 and, integrating with respect to $t$ on $[0,\infty)$, we obtain

${}\mathbb{E}\left[\sup_{\eta\in
H_{n}}\left(\left\lvert\hat{\pi}^{z}_{\eta}(\bm{x_{0}})-\mathbb{E}[\hat{\pi}^{z}_{\eta}(\bm{x_{0}})]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{\eta}\right)_{+}1_{\tilde{\Omega}_{n}}\right]\leq
cn^{-\bar{c}}\sum_{\eta\in
H_{n}}(\frac{v_{\eta}}{n}+\frac{M_{\eta}^{2}}{n^{2}}).$ (A.41)

From (A.39) and (A.40) and the definition (4.24) it follows

$M_{\eta}\leq\frac{1}{\eta^{d}}\prod_{j=1}^{d}(\kappa+\frac{\log
n}{\beta_{n}^{j}}2\kappa(c_{0}+4d))\leq cn^{d}\prod_{j=1}^{d}(1+\frac{\log
n}{\alpha_{j}}\lfloor\log_{2}n\rfloor),$
$v_{\eta}\leq\frac{c}{\eta^{2d}}\frac{1}{\prod_{j=1}^{d}(\beta_{n}^{j})^{2}}\leq
n^{2d}(\log_{2}n)^{2d}\frac{1}{\prod_{j=1}^{d}\alpha_{j}^{2}}.$

Replacing it in (A.41) we obtain

$\displaystyle\mathbb{E}\left[\sup_{\eta\in
H_{n}}\left(\left\lvert\hat{\pi}^{z}_{\eta}(\bm{x_{0}})-\mathbb{E}[\hat{\pi}^{z}_{\eta}(\bm{x_{0}})]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{\eta}\right)_{+}1_{\tilde{\Omega}_{n}}\right]$
(A.42) $\displaystyle\leq
cn^{-\bar{c}}\left(n^{2d-1}(\log_{2}n)^{2d+1}\frac{1}{\prod_{j=1}^{d}\alpha_{j}^{2}}+n^{2d-2}\prod_{j=1}^{d}(1+\frac{\log
n}{\alpha_{j}}\lfloor\log_{2}n\rfloor)^{2}\lfloor\log_{2}n\rfloor\right).$

We then deal with the contribution on $\tilde{\Omega}_{n}^{c}$ which, together
with (A.38), provides

$\mathbb{E}\left[\sup_{\eta\in
H_{n}}\left(\left\lvert\hat{\pi}^{z}_{\eta}(\bm{x_{0}})-\mathbb{E}[\hat{\pi}^{z}_{\eta}(\bm{x_{0}})]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{\eta}\right)_{+}1_{\tilde{\Omega}_{n}^{c}}\right]\leq
2\sum_{\eta\in
H_{n}}\mathbb{E}[|\hat{\pi}^{z}_{\eta}(\bm{x_{0}})|^{4}]^{\frac{1}{2}}\mathbb{P}(\tilde{\Omega}_{n}^{c})^{\frac{1}{2}}.$

We observe that, because of Jensen inequality, it is

$\mathbb{E}[|\hat{\pi}^{z}_{\eta}(\bm{x_{0}})|^{4}]\leq\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[|Z_{i}^{1,\eta}\times\dots\times
Z_{i}^{d,\eta}|^{4}].$

Moreover, for all $q\geq 1$,

$\displaystyle\mathbb{E}[|Z_{i}^{j,\eta}|^{q}]$
$\displaystyle=\mathbb{E}[|\frac{1}{\eta}K(\frac{X_{i}^{j}-x_{0}^{j}}{\eta})+\mathcal{E}_{i}^{j,\eta}|^{q}]\leq\frac{c}{\eta^{q}}+(\frac{2\kappa}{\eta\beta_{n}^{j}})^{q}\mathbb{E}[|\mathcal{L}(1)|^{q}]\leq(\frac{c}{\eta\beta_{n}^{j}})^{q}.$

It yields

$\displaystyle{}\mathbb{E}\left[\sup_{\eta\in
H_{n}}\left(\left\lvert\hat{\pi}^{z}_{\eta}(\bm{x_{0}})-\mathbb{E}[\hat{\pi}^{z}_{\eta}(\bm{x_{0}})]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{\eta}\right)_{+}1_{\tilde{\Omega}_{n}^{c}}\right]$
$\displaystyle\leq c\sum_{\eta\in
H_{n}}\frac{1}{(\eta\beta_{n}^{1})^{2}}\times\dots\times\frac{1}{(\eta\beta_{n}^{d})^{2}}(d\lfloor\log_{2}n\rfloor
n^{-4d-c_{0}})^{\frac{1}{2}}$ $\displaystyle\leq
c\,\mathop{card}(H_{n})\frac{n^{2d}}{\prod_{j=1}^{d}(\beta_{n}^{j})^{2}}\frac{\sqrt{\log
n}}{n^{2d+\frac{c_{0}}{2}}}$ (A.43) $\displaystyle\leq c\frac{(\log
n)^{2d+\frac{3}{2}}}{n^{\frac{c_{0}}{2}}\prod_{j=1}^{d}\alpha_{j}^{2}}.$

From (A.42) and (A.4.1), recalling that $c_{0}$ can be chosen arbitrarily
large and that $\alpha_{j}\leq 1$ for any $j\in\\{1,\dots,d\\}$ we obtain, for
some $\bar{c}>0$,

$\mathbb{E}\left[\sup_{\eta\in
H_{n}}\left(\left\lvert\hat{\pi}^{z}_{\eta}(\bm{x_{0}})-\mathbb{E}[\hat{\pi}^{z}_{\eta}(\bm{x_{0}})]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{\eta}\right)_{+}\right]\leq
c\frac{1}{n^{\bar{c}}\,\prod_{j=1}^{d}\alpha_{j}^{2}}.$

We have therefore proven (A.37) for $l=2$. For $l=1$ the proof of the bound in
(A.37) is obtained in the same way, applying Bernstein inequality with the
same constants $M_{\eta}$ and $v_{\eta}$ on

$\mathbb{P}\left(\left\\{\left\lvert\hat{\pi}^{z}_{\eta,h}(\bm{x_{0}})-\mathbb{E}[\hat{\pi}^{z}_{\eta,h}(\bm{x_{0}})]\right\rvert^{2}-\frac{1}{16}\mathbb{V}_{\eta}\geq
t;\leavevmode\nobreak\ \tilde{\Omega}_{n}\right\\}\right).$

The proof is therefore concluded. ∎

###### Proof of Theorem 4.25.

. From Proposition A.7 above one can remark it is enough to evaluate
$\inf_{h\in H_{n}}(\mathbb{D}_{h}^{2}+\mathbb{V}_{h})$. Equation (A.36)
entails we want to evaluate, up to a constant, the infimum over $h\in H_{n}$
of

${}h^{2\beta}+a_{n}\frac{1}{nh^{2d}\prod_{j=1}^{d}(\beta_{n}^{j})^{2}}\leq
h^{2\beta}+\frac{c\log n}{nh^{2d}}\frac{(\log
n)^{2d}}{\prod_{j=1}^{d}\alpha_{j}^{2}}.$ (A.44)

If we choose

${}h^{*}(n):=\left(\frac{(\log
n)^{2d+1}}{n\prod_{j=1}^{d}\alpha_{j}^{2}}\right)^{\frac{1}{2(\beta+d)}},$
(A.45)

then we obtain the quantity $\left(\frac{(\log
n)^{2d+1}}{n\prod_{j=1}^{d}\alpha_{j}^{2}}\right)^{\frac{2\beta}{2(\beta+d)}}$,
which is the wanted rate. To conclude the proof we have to check that
$h^{*}(n)$ as in (A.45) belongs to $H_{n}$. It is true as $H_{n}$ has been
constructed in analogy to $\mathcal{T}$, with $\frac{1}{h}$ playing the same
role as $T^{(l)}$, for $l=1,2$. Indeed, following the same argumentation as in
the proof of Theorem 4.15, as $\frac{n\prod_{j=1}^{d}\alpha_{j}^{2}}{(\log
n)^{2d+1}}\geq 1$ and $\alpha_{j}\leq 1$, it is $\frac{1}{h^{*}(n)}\in[1,n]$.
Then, by replacing $\frac{1}{h^{*}(n)}$ by its closest value in $H_{n}$ we
only modify its value in (A.44) by a constant, which provides

$\inf_{h\in H_{n}}(\mathbb{D}_{h}^{2}+\mathbb{V}_{h})\leq c\left(\frac{(\log
n)^{2d+1}}{n\prod_{j=1}^{d}\alpha_{j}^{2}}\right)^{\frac{2\beta}{2(\beta+d)}}.$

It concludes the proof of Theorem 4.25.

∎