# Optimal Federated Learning for Nonparametric Regression with Heterogeneous
Distributed Differential Privacy Constraints

T. Tony<EMAIL_ADDRESS>[ Abhinav
<EMAIL_ADDRESS>[ Lasse
<EMAIL_ADDRESS>[ Department of Statistics and Data
Science, University of Pennsylvaniapresep=, ]e1,e2,e3  T. Tony
<EMAIL_ADDRESS>[ Abhinav
<EMAIL_ADDRESS>[ Lasse
<EMAIL_ADDRESS>[ Department of Statistics and Data
Science, University of Pennsylvaniapresep=, ]e1,e2,e3

# Supplementary Material to “Optimal Federated Learning for Nonparametric
Regression with Heterogenous Distributed Differential Privacy Constraints”

T. Tony<EMAIL_ADDRESS>[ Abhinav
<EMAIL_ADDRESS>[ Lasse
<EMAIL_ADDRESS>[ Department of Statistics and Data
Science, University of Pennsylvaniapresep=, ]e1,e2,e3  T. Tony
<EMAIL_ADDRESS>[ Abhinav
<EMAIL_ADDRESS>[ Lasse
<EMAIL_ADDRESS>[ Department of Statistics and Data
Science, University of Pennsylvaniapresep=, ]e1,e2,e3

###### Abstract

This paper studies federated learning for nonparametric regression in the
context of distributed samples across different servers, each adhering to
distinct differential privacy constraints. The setting we consider is
heterogeneous, encompassing both varying sample sizes and differential privacy
constraints across servers. Within this framework, both global and pointwise
estimation are considered, and optimal rates of convergence over the Besov
spaces are established.

Distributed privacy-preserving estimators are proposed and their risk
properties are investigated. Matching minimax lower bounds, up to a
logarithmic factor, are established for both global and pointwise estimation.
Together, these findings shed light on the tradeoff between statistical
accuracy and privacy preservation. In particular, we characterize the
compromise not only in terms of the privacy budget but also concerning the
loss incurred by distributing data within the privacy framework as a whole.
This insight captures the folklore wisdom that it is easier to retain privacy
in larger samples, and explores the differences between pointwise and global
estimation under distributed privacy constraints.

###### Abstract

In this supplement, we present the detailed proofs for the main results in the
paper “Optimal Federated Learning for Nonparametric Regression with
Heterogenous Distributed Differential Privacy Constraints”.

62G08,

62C20,

68P27,

Besov Spaces,

Distributed Computation,

Differential Privacy,

Minimax Risk,

Nonparametric Regression,

Function Estimation,

62G08,

62C20,

68P27,

Distributed methods,

Nonparametric,

Minimax optimal,

###### keywords:

[class=MSC]

###### keywords:

###### keywords:

[class=MSC2020]

###### keywords:

, and

##  1 Introduction

In today’s data-driven world, the proliferation of personal data and
technological advancements has made the protection of privacy a matter of
paramount importance. Developing statistical methods with privacy guarantees
is becoming increasingly important. Differential privacy (DP), one of the most
widely adopted privacy frameworks, ensures that statistical analysis results
do not divulge any sensitive information about the input data. DP was
introduced in the seminal work by Dwork et al. [31]. Since its inception, DP
has garnered significant academic attention [6, 33, 34] and notable
applications within industry leaders, including Google [37], Microsoft [26],
and Apple [67]. It has also been embraced by governmental entities like the US
Census Bureau [1].

A common setting in many real-life applications is the distributed nature of
data collection and analysis. For example, medical data is spread across
various hospitals in healthcare, customer data is stored in different branches
or databases in financial institutions and various modern technologies rely on
federated learning from networks of users, see, for example, [55, 51, 43, 10,
59]. DP has found applications in many of these domains relating to, for
example, healthcare, finance, tech and social sciences, where preserving
individuals’ data privacy is of utmost concern. In such scenarios, it is vital
to develop efficient estimation techniques that respect privacy constraints
while harnessing the collective potential of distributed data.

Federated learning is a machine learning paradigm designed to address the
challenges of data governance and privacy. It enables organizations or groups,
whether from diverse geographic regions or within the same organization, to
collaboratively train and improve a shared global statistical model without
external sharing of raw data. The learning process occurs locally at each
participating entity, which we shall refer to as _servers_. The servers
exchange only characteristics of their data, such as parameter estimates or
gradients, in a way that preserves privacy of the individuals comprising their
data. Federated learning facilitates secure collaboration across industries
like retail, manufacturing, healthcare, and financial services, allowing them
to harness the power of data analysis while upholding data privacy and
security.

Rigorous study of theoretical performance in federated learning settings with
communication constraints has been conducted in, for example, bandwidth
constraint parametric problems [30, 11, 42, 8, 21, 3, 65] and bandwidth
constraint nonparametric estimation and testing [63, 73, 64, 20, 66]. Under DP
constraints, theoretical performance in federated learning settings have been
studied for various parametric estimation and testing problems [56, 4, 54,
58]. Federated learning settings where each server’s sample consists of one
individual observation (referred to as _local_ differential privacy settings)
have been studied in many-normal-means model, discrete distributions and
parametric models [28, 29, 7, 2, 71] and nonparametric density estimation [61,
52, 13].

This paper investigates the statistical optimality of federated learning under
DP constraints in the context of nonparametric regression. We consider a
setting where data is distributed among different entities, such as hospitals,
that are concerned about sharing their data with other entities due to privacy
concerns for their patients. Each entity communicates a transcript that
fulfills a distinct DP requirement, and we assume a setting with $m$ servers,
each with $n_{j}$ observations where $j=1,\dots,m$.

Our goals are two-fold: firstly, to establish optimal rates of convergence,
measured in terms of minimax risk, for estimating the nonparametric regression
function while adhering to DP constraints; secondly, to construct a rate-
optimal estimator under these DP constraints. We explore both global and
pointwise estimation, aiming to provide quantifiable measures of the trade-off
between accuracy and privacy preservation. These convergence rates offer
insights into the best achievable estimation performance in distributed
settings while ensuring privacy. Recognizing that global estimation exhibits
different characteristics compared to its pointwise counterpart in the
classical setting [16], we investigate how DP constraints impact global and
pointwise estimation risks differently.

###  1.1 Problem formulation

We will begin by formally introducing the general framework of distributed
estimation under privacy constraints. Consider a family of probability
measures $\\{P_{f}\\}_{f\in{\mathcal{F}}}$ on the measurable space
$(\mathcal{Z},\mathscr{Z})$, parameterized by $f\in{\mathcal{F}}$. We consider
a setting where $N=\sum_{j=1}^{m}n_{j}$ i.i.d. observations are drawn from a
distribution $P_{f}$ and distributed across $m$ servers. Each server
$j=1,\dots,m$ holds $n_{j}$ observations.

Figure 1: An illustration of the federated learning framework.

Let us denote by $Z^{(j)}=\\{Z^{(j)}_{i}\\}_{i=1}^{n_{j}}$ the $n_{j}$
realizations from $P_{f}$ on the $j$-th server. For each server, we output a
(randomized) transcript $T^{(j)}$ based on $Z^{(j)}$, where the law of the
transcript is given by a distribution conditional on $Z^{(j)}$,
${\mathbb{P}}(\cdot|Z^{(j)})$ on a measurable space
$({\mathcal{T}},\mathscr{T})$. The transcript $T^{(j)}$ has to satisfy a
$(\varepsilon_{j},\delta_{j})$-differential privacy constraint, which is
defined as follows.

######  Definition 1.1.

The transcript $T^{(j)}$ is $(\varepsilon_{j},\delta_{j})$-differentially
private if for all $A\in\mathscr{T}$ and $z,z^{\prime}\in\mathcal{Z}^{n_{j}}$
differing in one individual datum, it holds that

${\mathbb{P}}\left(T^{(j)}\in A|Z^{(j)}=z\right)\leq
e^{\varepsilon_{j}}{\mathbb{P}}\left(T^{(j)}\in
A|Z^{(j)}=z^{\prime}\right)+\delta_{j}.$

In the above definition, “differing in one datum” should be understood in
terms of being Hamming distance “neighbors.” To clarify, the local datasets
$Z^{(j)}$ and $\tilde{Z}^{(j)}$ are deemed _neighboring_ if their Hamming
distance is at most $1$. The Hamming distance is calculated over
$\mathcal{Z}^{n_{j}}\times\mathcal{Z}^{n_{j}}$. In other words,
$\tilde{Z}^{(j)}$ can be derived from $Z^{(j)}$ by modifying at most one of
the observations $Z^{(j)}_{1},\dots,Z^{(j)}_{n_{j}}$. The smaller the value of
$\epsilon_{j}$ and $\delta_{j}$, the more stringent the privacy constraint. We
shall consider $\varepsilon_{j}\leq C_{\varepsilon}$ for $j=1,\dots,m$ for a
fixed but arbitrarily constant $C_{\varepsilon}>0$, where the choice of the
constant does not affect the rates in the results derived.

We focus on distributed protocols that apply to situations in which sensitive
data is held by multiple parties, each generating an output while ensuring
differential privacy. Within such a distributed protocol, the transcripts from
each server only depend on its local data, and no information is exchanged
between the servers. This occurs, for example, when multiple trials concerning
the same population are conducted, but each location (e.g. hospital) does not
wish to pool their original data because of privacy concerns.

Each server transmits its transcript to the central server. The central
server, utilizing all transcripts $T:=(T^{(1)},\dots,T^{(m)})$, computes an
estimator $\hat{f}:{\mathcal{T}}^{m}\to{\mathcal{F}}$. We refer to the pair
$(\hat{f},\\{\left({\mathbb{P}}(\cdot|z)\right)_{z\in{\mathcal{Z}}}\\}_{j=1}^{m})$
as a _distributed estimation protocol_ , which we shall sometimes just denote
as $\hat{f}$. We denote the vector of the differing DP levels by
$(\boldsymbol{\varepsilon},\boldsymbol{\delta})=\\{(\varepsilon_{j},\delta_{j})\\}_{j=1}^{m}$
and denote the class of _distributed estimation protocols_ , i.e.
$\left(\hat{f},\\{\left({\mathbb{P}}(\cdot|z)\right)_{z\in{\mathcal{Z}}}\\}_{j=1}^{m}\right)$
satisfying Definition 1.1, with
${\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})$. We let
${\mathbb{P}}_{f}$ denote the joint law of transcripts and the
$N=\sum_{j=1}^{m}n_{j}$ i.i.d. observations generated from $P_{f}$. We let
${\mathbb{E}}_{f}$ denote the expectation corresponding to ${\mathbb{P}}_{f}$.

In the context of nonparametric regression, the distributed estimation problem
arises when data is distributed among multiple servers. Specifically, for each
server $j$, the data $Z^{(j)}=\\{(Y^{(j)}_{i},X^{(j)}_{i})\\}_{i=1}^{n_{j}}$
consists of $n_{j}$ pairs of observations $(Y^{(j)}_{i},X^{(j)}_{i})$. Here,
$X^{(j)}_{i}$ represents the input variable, and $Y^{(j)}_{i}$ represents the
corresponding response variable.

We assume that under $P_{f}$, $X^{(j)}_{i}$ and $Y^{(j)}_{i}$ are generated by
the relationship

$Y^{(j)}_{i}=f\left(X^{(j)}_{i}\right)+\xi^{(j)}_{i},\quad X^{(j)}_{i}\sim
U[0,1].$ (1)

Here, $f$ is an unknown function representing the underlying relationship
between the input and response variables. The term $\xi^{(j)}_{i}$ represents
random noise, assumed to be independent of $X^{(j)}_{i}$, and follows a
Gaussian distribution with mean $0$ and known variance $\sigma^{2}$. Without
loss of generality, we shall assume $\sigma=1$ throughout the paper.

The aim is to estimate the function $f$ based on the distributed data. The
difficulty of this estimation task arises from both the distributed nature of
the data and privacy constraints that limit the sharing of information between
servers. As in the conventional decision-theoretical framework, for global
estimation, the estimation accuracy of a distributed estimator
$\hat{f}\equiv\hat{f}(T)$ is measured by the integrated mean squared error
(IMSE), ${\mathbb{E}}_{f}\|\hat{f}-f\|_{2}^{2}$, where the expectation is
taken over the randomness in both the data (under $P_{f}$) and construction of
the transcripts. As in the conventional framework, a quantity of particular
interest in federated learning is the _global minimax risk_ for the
distributed private protocols over function class ${\mathcal{F}}$,

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in{\mathcal{F}}}{\mathbb{E}}_{f}\|\hat{f}-f\|_{2}^{2}.$
(2)

The global risk characterizes the difficulty of the distributed learning
problem over the function class ${\mathcal{F}}$ when trying to infer the
entire function underlying the data whilst adhering to the heterogeneous
privacy constraints.

Besides global estimation, it is also of interest to estimate $f$ at a fixed
point $x_{0}\in(0,1)$ under the mean squared error (MSE). The _pointwise
minimax risk_ in that case is given by

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in{\mathcal{F}}}{\mathbb{E}}_{f}(\hat{f}(x_{0})-f(x_{0}))^{2},\;\text{
for }x_{0}\in(0,1),$ (3)

where $\hat{f}(x_{0})$ denotes the estimated function value at
$x_{0}\in(0,1)$. The pointwise risk is particularly useful in understanding
the behavior of estimators at specific points within the domain, which can be
crucial in applications where certain regions are of particular interest or
have higher consequences associated with estimation errors. It is known that
in the classical setting, without privacy constraints, there are important
differences between the global risk and pointwise risk in terms of
performance. See, for example, [15].

We consider estimating $f$ over the Besov ball of radius $R>0$, denoted as
${\mathcal{B}}^{\alpha,R}_{p,q}[0,1]$ (defined in (11)), where $p\geq 2$,
$q\geq 1$ and ${\alpha}-1/p>1/2$. This Besov space offers a suitable framework
for analyzing functions with specific smoothness characteristics. Operating
within this space allows us to encompass diverse function classes,
accommodating varying levels of smoothness and complexity.

###  1.2 Main contribution

We quantify the cost of differential privacy for both the minimax global risk
given by (2) and the pointwise risk as in (3). To achieve this, we introduce
two differentially private estimators – one for global and one for pointwise
estimation. We obtain matching minimax lower bounds, up to logarithmic
factors, thereby establishing their optimality.

Our analysis reveals interesting phenomena, that go unobserved in settings
where servers are assumed to have homogeneous privacy budgets. Further
discussion on these broader findings is deferred to Section 2. The results for
the homogeneous case, where privacy budgets are equal among servers
($\varepsilon_{j}=\varepsilon$, $\delta_{j}=\delta$, and $n_{j}=n$ for
$j=1,\dots,m$), yield novel insights. In this case, our results yield the
following minimax rate for global estimation,

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in{\mathcal{B}}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}\|\hat{f}-f\|_{2}^{2}\asymp\min\left\\{M_{m,n}\cdot\left((mn^{2}\varepsilon^{2})^{-\frac{2\alpha}{2\alpha+2}}+(mn)^{-\frac{2\alpha}{2\alpha+1}}\right),1\right\\},$
(4)

where $M_{m,n}\geq 1$ is a sequence at most of the order
$\log(mn)\cdot\log(1/\delta)$. The rate
$\left(mn\right)^{-\frac{2\alpha}{2\alpha+1}}$ is the minimax rate for the
global risk in the unconstrained problem, and is attained whenever
$n\varepsilon^{2}\gtrsim\left(mn\right)^{\frac{1}{2\alpha+1}}$. The
unconstrained optimal rate is attainable (up to a possibly poly-logarithmic
factor) under DP constraints in the homogeneous setting as long as
$n\varepsilon^{2}\gtrsim\left(mn\right)^{\frac{1}{2\alpha+1}}$. Whenever
$n\varepsilon^{2}\ll\left(mn\right)^{\frac{1}{2\alpha+1}}$, the first term
dominates and the minimax rate becomes
$(mn^{2}\varepsilon^{2})^{-\frac{2\alpha}{2\alpha+2}}$. As expected in this
regime, a smaller $\varepsilon$, which indicates a stronger privacy guarantee,
results in an larger minimax estimation error. Whenever
$\varepsilon\ll(\sqrt{m}n)^{-1}$, consistent estimation ceases to be possible
altogether.

This result recover the known minimax rates under local DP constraints (i.e.
$n=1$) that were derived for the problem of nonparametric density estimation
for the $L_{2}$-risk in [13] and the squared Hellinger in [61], up to
logarithmic factor differences. When $n>1$, the different powers with which
$n$ and $m$ appear in the minimax rate reveal an important difference between
the general distributed setting and local DP; if one distributes $N=mn$
observations across $m$ machines, the task becomes more challenging as the $N$
observations are spread over a greater number of machines, rather than having
a large number of observations on a smaller number of machines. This
phenomenon has an intuitive explanation; it is easier to retain privacy in
larger samples, as each individual’s data will have only a small influence on
the aggregate statistics of interest.

For pointwise estimation, we establish the minimax rate in the homogeneous
setting;

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}|\hat{f}(x_{0})-f(x_{0})|^{2}\asymp\min\left\\{M_{m,n}\cdot\left(\left(mn^{2}\varepsilon^{2}\right)^{-\frac{2\nu}{2\nu+2}}+\left(mn\right)^{-\frac{2\nu}{2\nu+1}}\right),1\right\\},$
(5)

where $M_{m,n}\geq 1$ is a sequence at most of the order $\log(mn)$. The rate
reveals similar phenomena as the one for the global risk above, where for
$n=1$ we recover the known minimax rate for the problem of nonparametric
density estimation for the pointwise risk under local DP constraints as
studied in [52]. An important difference is the quantity $\nu=\alpha-1/p$
appearing in the exponent instead of $\alpha$. This implies that privacy
constraints impact pointwise estimation differently than global estimation,
with the Besov parameter $p$ influencing both the relative privacy cost and
the distribution of the $N=mn$ observations, as discussed further in Section
2.1.

Our findings have substantial implications for the development of federated
learning algorithms that balance distributed privacy with accuracy. A clear
understanding of the optimal convergence rate under distributed privacy
constraints allows the design of algorithms that strike the right balance
between accuracy and privacy trade-offs. This study contributes significantly
to the growing knowledge on distributed settings for privacy-preserving
machine learning, offering valuable insights for future research in this
domain.

###  1.3 Related Work

The nonparametric regression setting considered in this work bears
relationships with that of nonparametric density estimation as studied in the
privacy setting for global risk [29, 61, 13] and pointwise risk [52]. The
aforementioned papers consider the setting of local DP, in which the privacy
protection is applied at the level of individual data entries or observations.
This corresponds to the case wherein $n_{j}=1$ for $j=1,\dots,m$ in our
setting.

Distributed DP as considered in this paper, where DP applies at the level of
the local sample consisting of multiple observations, has been studied for the
homogeneous estimation setting for discrete distributions [56, 4] and
parametric mean estimation [54, 58]. In the paper [22], the authors consider
discrete distribution testing in a two server setting ($m=2$) with differing
DP constraints.

Settings in which the full data is assumed to be on a single server (i.e.
$m=1$), where a single privacy constraint applies to all the observations,
have also been studied for various parametric high-dimensional problems [62,
36, 9, 48, 49, 18, 57]. The problem of mean estimation with a single server
having heterogeneous privacy constraints for each individual observation have
been studied in [38, 23].

###  1.4 Organization of the paper

The rest of the paper is organized as follows. We conclude this section with
notation, definitions, and assumptions. Section 2 summarizes and discusses the
minimax optimal convergence rates for global and pointwise risks under privacy
constraints. In Section 3, we present distributed estimation procedures that
achieve optimal global and pointwise risk while adhering to distributed
privacy constraints, along with an upper bound on their statistical
performance. The matching minimax lower bounds for the global and pointwise
risks are derived in Section 4. The proofs of the main results are given in
the Supplementary Material [17].

###  1.5 Notation, definitions and assumptions

Throughout the article, we shall write $N:=\sum_{j=1}^{m}n_{j}$ and consider
asymptotics in $m$, the $n_{j}$’s and the privacy budget
$(\boldsymbol{\epsilon},\boldsymbol{\delta}):=\\{\varepsilon_{j},\delta_{j}\\}_{j=1}^{m}$,
where we assume that $N\to\infty$. For two positive sequences $a_{k}$, $b_{k}$
we write $a_{k}\lesssim b_{k}$ if the inequality $a_{k}\leq Cb_{k}$ holds for
some universal positive constant $C$. Similarly, we write $a_{k}\asymp b_{k}$
if $a_{k}\lesssim b_{k}$ and $b_{k}\lesssim a_{k}$ hold simultaneously and let
$a_{k}\ll b_{k}$ denote that $a_{k}/b_{k}=o(1)$.

We use the notations $a\vee b$ and $a\wedge b$ for the maximum and minimum,
respectively, between $a$ and $b$. For $k\in{\mathbb{N}}$, $[k]$ shall denote
the set $\\{1,\dots,k\\}$. Throughout the paper $c$ and $C$ denote universal
constants whose value can differ from line to line. The Euclidean norm of a
vector $v\in\mathbb{R}^{d}$ is denoted by $\|v\|_{2}$. For a matrix
$M\in{\mathbb{R}}^{d\times d}$, the norm $M\mapsto\|M\|$ is the spectral norm
and $\text{Tr}(M)$ is its trace. Furthermore, we let $I_{d}$ denote the
$d\times d$ identity matrix.

Throughout this paper, we shall let $\nu:=\alpha-1/p>1/2$, which is a required
assumption for estimation in Besov spaces (see e.g. [45]). We let
$\mathcal{B}^{\alpha,R}_{p,q}$ denote the closed Besov ball of radius $R$,
i.e.
$\\{f\in\mathcal{B}^{\alpha}_{p,q}[0,1]:\|f\|_{{\mathcal{B}}^{\alpha}_{p,q}}\leq
R\\}$, where $R>0$ is taken to be a constant.

For random variables $U$ and $V$ with probability measures $P$ and $Q$ defined
on the same measurable space, we let $D_{\mathrm{TV}}(U,V)$ denote the total
variation norm between $P$ and $Q$, i.e. $\|P-Q\|_{\mathrm{TV}}$. Whenever
$P\ll Q$, we write $D_{\mathrm{KL}}(U,V)$ for the Kullback-Leibler divergence
between $P$ and $Q$: $D_{\mathrm{KL}}(P;Q)=\int\log\frac{dP}{dQ}dP$. Our lower
bound results hold for transcripts taking values in standard Borel measure
spaces. Different measure spaces or larger sigma-algebras can be considered
(which only make the privacy constraint more stringent, see e.g. [70]) as long
as the quantities in the proofs are appropriately measurable.

##  2 Minimax optimal rates of convergence

In this section, we present our primary findings regarding the minimax rate of
convergence under DP constraints. Our results address both the global and
pointwise risks.

For the global risk, the minimax rates are encapsulated in the upper bound of
Theorem 3.2 and the lower bound of Theorem 4.1, derived in Sections 3.2 and
4.1. Similarly, for the pointwise risk, our findings are summarized in
Theorems 3.4 and 4.4, in the form of an upper bound and lower bound
respectively, in Sections 3.3 and 4.2. Together, these theorems are summarized
by the following result.

######  Theorem 2.1.

For $\gamma>0$, let $D>0$ be the number solving the equation

$D^{2\gamma+2}=\sum_{j=1}^{m}\left(n_{j}^{2}\varepsilon_{j}^{2}\right)\wedge\left(n_{j}D\right).$
(6)

Taking $\gamma=\alpha$, the minimax rate for the global risk is given by

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in{\mathcal{B}}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}\|\hat{f}-f\|_{2}^{2}\asymp\left(M_{N}D^{-2\alpha}\wedge
1\right),$

whenever for all $j=1,\dots,m$ we have
$\delta_{j}\lesssim(n_{j}^{1/2}\varepsilon_{j}^{2}(D\vee 1)^{-1})^{1+\kappa}$
for some $\kappa>0$ and where $M_{N}\geq 1$ is a sequence of the order at most
$\log(N)\log(1/\min_{j\in[m]}\delta_{j})$.

For $\gamma=\nu$, the minimax rate for the pointwise risk is given by

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}\left|\hat{f}(x_{0})-f(x_{0})\right|^{2}\asymp\left(M_{N}D^{-2\nu}\wedge
1\right),$

whenever $\sum_{j}n_{j}\delta_{j}\to 0$, for a sequence $M_{N}\geq 1$ of the
order at most $\log(N)$.

We briefly comment on the derived result. First, we note that a unique
positive solution to (14) always exists. To see this, note that the exponent
$2\gamma+2>2$ implies that the left-hand side is smaller than the right-hand
side for $D>0$ small enough, whilst the right-hand side grows linearly for
small enough $D>0$. Furthermore, the right-hand side increases sublinearly in
$D$, whilst the left-hand side increases superlinearly (strictly so).

When the privacy budget is large enough (e.g. $\varepsilon_{j}=\infty$ for
$j=1,\dots,m$), $D$ can be seen to correspond with the ‘effective resolution
level’ of the estimation problem. That is, $D$ would be proportional to the
number of wavelet coefficients needed to obtain a wavelet estimator that
attains the optimal estimation rate, see for example [27]. For $\alpha>0$
smooth functions in a Besov space, the optimal resolution level of a wavelet
estimator would correspond to $(1+2\alpha)^{-1}\lceil\log_{2}N\rceil$ for the
global risk. However, under privacy constraints, the effective resolution
level changes to $(2+2\alpha)^{-1}\lceil\log_{2}D\rceil$, which can be
substantially different from the case without privacy constraints. We present
several specific cases of Theorem 2.1 through corollaries that encapsulate its
various implications, as discussed in Sections 2.1 and 2.2.

The upper bounds for both types of risk (as given in Theorems 3.2 and 3.4) are
derived by constructing two estimators. One is proven optimal for global risk,
while the other is optimal for pointwise risk. The construction of these
estimators is detailed in Section 3. Notably, the optimal estimators for each
risk type take distinct forms and employ different privacy mechanisms.

Both of these lower bounds require a different technique. For the global risk,
the lower bounding technique is reminiscent of the score attack of [18, 19],
which is a generalization of the tracing adversary argument of [12, 35]. We
describe the technique in detail in Section 4.1. In case of the pointwise
risk, we employ a coupling argument akin to [5, 50] in conjunction with Le
Cam’s two point method (see e.g. [53, 72]). The technique for the pointwise
risk lower bound is described in Section 4.2. Whilst the techniques differ, a
similarity is that they both account for the differences in the required
levels of privacy between the servers, with the quantity $D>0$ in (14) being
the outcome of balancing a bias-variance trade-off, where the variance for
each of the servers is either dominated by the (local) noise in the data
itself or by the privacy requirement of the server.

###  2.1 The homogeneous setting

Let us start by studying the case where all machines have both an equal amount
of observations, as well as privacy budgets. The following result describes
the global risk behavior under DP constraints when the servers are homogeneous
in both the number of observations, as well as the privacy constraints they
adhere to.

######  Corollary 1.

Suppose that $n_{j}=n$, $\varepsilon_{j}=\varepsilon$, $\delta_{j}=\delta$ for
$j=1,\dots,m$ and assume that
$\delta\lesssim(\varepsilon^{2}/\sqrt{m})^{1+\kappa}$ for some $\kappa>0$.
Then, the global minimax risk over
${\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})$ satisfies (4).

Whenever $n\varepsilon^{2}\ll\left(mn\right)^{\frac{1}{2\alpha+1}}$, we have
that

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in{\mathcal{B}}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}\|\hat{f}-f\|_{2}^{2}\asymp
M_{m,n}\left(mn\right)^{-\frac{2\alpha}{2\alpha+1}}\left(m^{\frac{1}{2\alpha+1}}n^{-\frac{2\alpha}{2\alpha+1}}\varepsilon^{-2}\right)^{\frac{2\alpha}{2\alpha+2}},$

which indicates that the minimax estimation error becomes larger than the
unconstrained minimax rate ($(mn)^{-\frac{2\alpha}{2\alpha+1}}$) by a factor
of
$(m^{\frac{1}{(2\alpha+1)}}n^{-\frac{2\alpha}{2\alpha+1}}\varepsilon^{-2})^{\frac{2\alpha}{2\alpha+2}}$
(ignoring the logarithmic factor). This factor can be seen to capture the cost
of privacy in terms of the global risk. A smaller $\varepsilon$ results in an
increase in minimax estimation error, where larger smoothness exacerbates the
increase.

A second observation that can be made on the basis of the privacy cost factor,
is the cost of distributing observations in a privacy setting. That is to say,
if one distributes $N=mn$ observations across $m$ machines, the task becomes
more challenging as the $N$ observations are spread over a greater number of
machines, rather than having a large number of observations on a smaller
number of machines. The relative cost of distributing observations is also
revealed to be related to the smoothness, where a larger smoothness again
exacerbates the relative cost of distributing data. This observation confirms
a folklore understanding that it is easier to retain privacy within a larger
crowd. Distributing data across more machines means that each machine needs to
add additional noise, to compensate for an overall lack of observations. It
also affirms that local differentially private methods perform relatively
poorly in multiple observation settings and that applying a privacy constraint
at an observation level is comparatively costly.

Classically, the pointwise risk is known to be subject to different phenomena
than the global risk over the Besov spaces [16]. Writing $\nu=\alpha-1/p$ and
assuming $\alpha>1/p$, it is known that the unconstrained pointwise minimax
risk satisfies

$\inf_{\hat{f}}\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}|\hat{f}(x_{0})-f(x_{0})|^{2}\asymp\left(mn\right)^{-\frac{2\nu}{2\nu+1}}.$
(7)

Compared to the unconstrained global risk, this indicates that the estimation
error at a point is subject to a fundamentally slower convergence rate than
the global estimation minimax rate, where the $\ell_{p}$-norm used to measure
the smoothness of the Besov ellipsoid influences the minimax estimation
performance. Roughly speaking, the “pointwise” integrability of the
derivatives of the function underlying the data impacts the problem of
estimation at a point, whilst the global risk remains unaffected. This effect
disappears for Hölder alternatives, where $p=\infty$ and the minimax rate for
the global risk and the pointwise risk coincide.

The main theorem on the minimax risk for pointwise estimation leads to the
following result for the homogeneous setting.

######  Corollary 2.

Suppose that $n_{j}=n$, $\varepsilon_{j}=\varepsilon$, $\delta_{j}=\delta$ for
$j=1,\dots,m$ and $\delta\ll(mn)^{-1}$. Then, for $x_{0}\in[0,1]$, the
pointwise minimax risk at $x_{0}$ over the class
${\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})$ satisfies (5).

The minimax rate for the pointwise risk seemingly takes on a similar form as
that of the global risk and it coincides with the global risk whenever
$p=\infty$. However, for finite values of $p$, the cost of privacy can be seen
to differ. In particular, to attain the unconstrained optimal pointwise
minimax rate (7), it can be seen that a relatively larger $\varepsilon$ is
needed, where a smaller value of $p$ in fact exacerbates the demand. More
precisely, whenever $\left(mn\right)^{\frac{1}{2\alpha+1}}\lesssim
n\varepsilon^{2}\ll\left(mn\right)^{\frac{1}{2\nu+1}}$, the pointwise risk
suffers from the DP constraints, whereas the global risk performance is the
same as in the problem without the DP constraints.

Whenever $n\varepsilon^{2}\ll\left(mn\right)^{\frac{1}{2\nu+1}}$, comparing
(5) to (7) shows that the minimax rate of the classical (unconstrained)
pointwise risk increases by a factor of
$(m^{\frac{1}{2\nu+1}}n^{-\frac{2\nu}{2\nu+1}}\varepsilon^{-2})^{\frac{2\nu}{2\nu+2}}$
(ignoring the logarithmic factor). This shows that the pointwise risk is
subject to a similar cost-relationship as the global risk. What is similar is
that more stringent privacy demands in terms of a smaller $\varepsilon$
translate to an increased cost in terms of the pointwise risk. However, the
relative increase in privacy cost resulting from a decrease in $\varepsilon$
for the case of pointwise risk, is smaller than the relative increase in
privacy cost of the global risk, where this discrepancy is further exacarbated
for smaller values of $p$. This shows that stringent privacy demands are
comparatively less costly for the pointwise risk.

On the other hand, the cost of distributing observations (i.e. increasing $m$
when distributing $N=nm$ observations) is relatively larger for smaller values
of $p$. That is to say, differentially private estimation in pointwise risk
suffers less from stringent per machine privacy demands, while it suffers more
from the fact that data is distributed before privacy preservation is applied.
This surprising phenomenon shows that in a distributed setting with privacy
constraints, the distribution of the data across servers impacts the rate
differently depending on the inferential task at hand.

###  2.2 The heterogeneous setting

While the homogeneous setting described in the introduction serves to
illustrate fundamental phenomena, real-world scenarios often involve
heterogeneous data and privacy constraints across various data silos. In
applications, data may not be uniformly distributed among different sources.
For instance, consider cases where data is observed and processed locally, as
in the context of hospitals. The results presented here highlight the optimal
estimation under differential privacy in such a heterogeneous setting.

Theorems 4.1 and 3.2 describe the minimax rate for the global risk for the
full spectrum of possibilities in terms of heterogeneous constraints.
Similarly, Theorems 4.4 and 3.4 describe the minimax rate for the local risk
in the heterogeneous setting. Here, for the sake of clarity of interpretation,
we will focus on two different regimes of privacy budgets. For both regimes,
whenever $\min_{j}\varepsilon\gtrsim 1/(mn)$, we require that
$\min_{j}\delta_{j}\ll 1/(mn)^{2}$, which translates to $\delta$ having no
further impact on the minimax performance except for incurring a logarithmic
factor in case of the global risk. For the first regime, we shall consider
privacy budgets where the no single server has much more data than the other
servers, comparatively to the stringency in terms of the DP parameter
$\varepsilon$. This amounts to

$\left(\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\right)^{\frac{1}{2\gamma+2}}\geq\max_{j}\,n_{j}\varepsilon_{j}^{2},$
(8)

where $N=\sum^{m}_{j=1}n_{j}$ and $\gamma=\alpha$ or $\gamma=\nu$ for the
global and pointwise risk respectively. The following result describes the
minimax rate in this regime for the global and pointwise risks.

######  Corollary 3.

Suppose that $(\boldsymbol{\epsilon},\boldsymbol{\delta})$ is such that
$\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\to\infty$, for $j=1,\dots,m$ we
have $\delta_{j}\lesssim(\varepsilon_{j}^{2}/\sqrt{m})^{1+\kappa}$ for some
$\kappa>0$ and (8) holds with $\gamma=\alpha$. Then, it holds that

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in{\mathcal{B}}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}\left\|\hat{f}-f\right\|_{2}^{2}\asymp
M_{N}\left(\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\right)^{-\frac{2\alpha}{2\alpha+2}}.$

for some $M_{N}\geq 1$ of the order at most
$\log(N)\cdot\log(1/\min_{j}\delta_{j})$.

If (8) holds for $\gamma=\nu$ and $\sum_{j=1}^{m}n_{j}\delta_{j}\to 0$, it
holds that

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}\left|\hat{f}(x_{0})-f(x_{0})\right|^{2}\asymp
M_{N}\left(\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\right)^{-\frac{2\nu}{2\nu+2}}$

for some $M_{N}\geq 1$ of the order at most $\log(N)$.

In such a setting, the behaviour in terms of the privacy cost is similar to
that described by Corollaries 1 and 2. A first glance shows that in the
distributed privacy setup, the problem is much more difficult compared to the
problem without privacy constraints: the rate when no privacy constraints are
in place, which is $N^{-\frac{2\alpha}{2\alpha+1}}$. Furthermore, the minimax
rate shows that, when $N$ observations are divided over $m$ machines somewhat
equally, there is benefit in dividing over as few machines as possible and
there is an additional benefit to having machines with a relatively large
amount of data. The explanation for this is the same as described in the
homogeneous case: it is easier to retain privacy within large local samples.
When the samples are “spread thinly” across the servers, the cost of DP is
larger. Between the pointwise risk and the global risk, the phenomenon of
pointwise risk incurring relatively less cost when $\varepsilon_{j}$’s are
decreased compared to the global risk is also still observed when $p<\infty$,
whilst the cost of distributing is relatively higher.

In the regime of (8), even though the privacy budgets vary between the
servers, all the servers can be seen to provide a non-negligible contribution
to the central estimator. Another regime which we highlight, is the case where
some $j^{*}\in[m]$ the privacy budget satisfies

$\displaystyle\left(n_{j^{*}}^{2}\varepsilon_{j^{*}}^{2}\right)\wedge\left(n_{j^{*}}^{\frac{2\gamma+4}{2\gamma+2}}\varepsilon_{j^{*}}^{\frac{2}{2\gamma+2}}\right)\wedge
n_{j^{*}}^{\frac{2\gamma+2}{2\gamma+1}}\geq\underset{[m]\setminus\\{j^{*}\\}}{\overset{}{\sum}}n_{j}^{2}\varepsilon_{j}^{2},$
(9)

where we consider $\gamma=\alpha$ or $\gamma=\nu$ for the global and pointwise
risk respectively. This regime is in a sense the juxtaposition of (8). Where
in (8), no server has a substantially better privacy budget compared to its
number of observations, in the case of (9), there is (at least) one server
with a substantially larger sample and/or a relatively better privacy budget
than the other servers. The following result captures the minimax rate for the
global and pointwise risks in such a regime.

######  Corollary 4.

Suppose that $(\boldsymbol{\epsilon},\boldsymbol{\delta})$ satisfies
$\delta_{j}\lesssim(\sqrt{n_{j}}\varepsilon_{j}^{2}/(n_{j^{*}}^{2/3}\varepsilon_{j^{*}}^{2/3}))^{1+\kappa}$
for some $\kappa>0$ and all $j=1,\dots,m$, (9) holds for $\gamma=\alpha$ and
$\varepsilon_{j^{*}}>(n_{j^{*}})^{-1}$. Then, it holds that

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in{\mathcal{B}}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}\|\hat{f}-f\|_{2}^{2}\asymp
M_{m,n}\left(\left(n_{j^{*}}^{2}\varepsilon_{j^{*}}^{2}\right)^{-\frac{2\alpha}{2\alpha+2}}+\left(n_{j^{*}}\right)^{-\frac{2\alpha}{2\alpha+1}}\right)$

for some $M_{N}\geq 1$ of the order at most
$\log(N)\cdot\log(1/\min_{j}\delta_{j})$. If (9) holds for $\gamma=\nu$, it
holds that

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}|\hat{f}(x_{0})-f(x_{0})|^{2}\asymp
M_{m,n}\left(\left(n_{j^{*}}^{2}\varepsilon_{j^{*}}^{2}\right)^{-\frac{2\nu}{2\nu+2}}+\left(n_{j^{*}}\right)^{-\frac{2\nu}{2\nu+1}}\right)$

for some $M_{N}\geq 1$ of the order at most $\log(N)$.

In the regime described by the theorem, certain servers have a large sample
and relatively large privacy budget, compared to the “majority” of the other
servers in the sense of (9). The minimax rate derived describes that in such
settings these large sample/budget servers dictate the statistical accuracy of
estimation. This is true both for the global, as well as the pointwise risk.
In terms of optimal estimation procedures, the minimax rate can be achieved by
only using estimators based on the data of the server(s) with relatively large
samples and privacy budget, as the benefit of the servers with smaller samples
and privacy budgets have an asymptotically negligible benefit.

##  3 Optimal Distributed $(\boldsymbol{\varepsilon},\boldsymbol{\delta})$-DP
Estimators

In this section, we present two estimators that attain the optimal rates as
described by the theorems of the previous section. One estimator specifically
targets the global risk, the other is constructed specifically to perform well
in terms of the pointwise risk. Whilst it perhaps natural to estimate
$f(x_{0})$ using the global risk DP-estimator evaluated at $x_{0}$, the
specific pointwise estimator we propose combines DP-estimates of $f(x_{0})$
computed locally (i.e. estimators of $f(x_{0})$ computed at each of the
servers). This approach offers several benefits, such as an improved
performance regardless of the value of $\delta_{j}\geq 0$. Both estimators are
constructed using a wavelet basis.

Wavelets are known to have many favourable properties when using them for
function estimation in classical settings, see for example [27, 41, 14]. Under
DP constraints, wavelet constructions have other desirable properties: they
allow for exact control of the estimator’s _sensitivity_ to changes in the
data. Loosely speaking, this allows us to control the “influence” each
individual observation has on the outcome of the estimator, whilst retaining
the information the full sample has to a large extent.

###  3.1 Wavelets and Besov spaces

In the context of nonparametric regression, we aim to construct an optimal
estimator for an unknown function $f$ based on the distributed data. Here, we
assume that $f$ belongs to the Besov space ${\mathcal{B}}^{\alpha}_{p,q}$.
Roughly stated, the Besov space ${\mathcal{B}}^{\alpha}_{p,q}$ containts
functions having $\alpha$ bounded derivatives in $L_{p}$-space, with $q$
giving a finer control of the degree of smoothness. We refer the reader to
[69] for a detailed description.

Wavelet bases allow characterization of the Besov spaces, where $\alpha$, $p$
and $q$ are parameters that capture the decay rate of wavelet basis
coefficients. Before presenting the two optimal estimators for global and
pointwise risk in Sections 3.2 and 3.3 respectively, we first briefly
introduce wavelets and collect some properties used to define the Besov space.
For a more detailed and elaborate introduction of wavelets in the context of
Besov spaces, we refer to [44, 47].

In our work we consider the Cohen, Daubechies and Vial construction of
compactly supported, orthonormal, $A$-regular wavelet basis of $L_{2}[0,1]$,
see for instance [24]. First for any $A\in\mathbb{N}$ one can follow
Daubechies’ construction of the father $\phi(\cdot)$ and mother $\psi(\cdot)$
wavelets with $A$ vanishing moments and bounded support on $[0,2A-1]$ and
$[-A+1,A]$, respectively, for which we refer to [25]. The basis functions are
then obtained as

$\displaystyle\big{\\{}\phi_{l_{0}+1,m},\psi_{lk}:\,m\in\\{0,...,2^{l_{0}+1}-1\\},\quad
l\geq l_{0}+1,\quad k\in\\{0,...,2^{l}-1\\}\big{\\}},$

with $\psi_{lk}(x)=2^{l/2}\psi(2^{l}x-k)$, for $k\in[A-1,2^{l}-A]$, and
$\phi_{l_{0}+1,k}(x)=2^{l_{0}+1}\phi(2^{l_{0}+1}x-m)$, for
$m\in[0,2^{l_{0}+1}-2A]$, while for other values of $k$ and $m$, the functions
are specially constructed, to form a basis with the required smoothness
property. In a slight abuse of notation, we shall denote the father wavelet by
$\psi_{l_{0}k}=\phi_{l_{0}+1,k}$ and represent any function $f\in L_{2}[0,1]$
in the form

$\displaystyle f=\sum_{l=l_{0}}^{\infty}\sum_{k=0}^{2^{l}-1}f_{lk}\psi_{lk},$
(10)

where the $f_{lk}=\langle f,\psi_{lk}\rangle$ are called the _wavelet
coefficients_. Note that in view of the orthonormality of the wavelet basis
the $L_{2}$-norm of the function $f$ is equal to

$\displaystyle\|f\|_{2}^{2}=\sum_{l=l_{0}}^{\infty}\sum_{k=0}^{2^{l}-1}f_{lk}^{2}.$

Next we give definition of Besov spaces using wavelets. Let us define the
norms

$\|f\|_{{\mathcal{B}}^{\alpha}_{p,q}}:=\begin{cases}\left(\underset{l=l_{0}}{\overset{\infty}{\sum}}\left(2^{l(\alpha+1/2-1/p)}\left\|(f_{lk})_{k=0}^{2^{l}-1}\right\|_{p}\right)^{q}\right)^{1/q}&\text{
for }1\leq q<\infty,\\\ \;\underset{l\geq
l_{0}}{\sup}\;2^{l(\alpha+1/2-1/p)}\left\|(f_{lk})_{k=0}^{2^{l}-1}\right\|_{p}&\text{
for }q=\infty,\end{cases}$

for $\alpha\in(0,A)$, $1\leq q\leq\infty$, $2\leq p\leq\infty$. Then, the
Besov space $\mathcal{B}^{\alpha}_{p,q}[0,1]$ and Besov ball
$\mathcal{B}^{\alpha,R}_{p,q}[0,1]$ of radius $R>0$ can be defined as

$\mathcal{B}^{\alpha}_{p,q}[0,1]=\\{f\in
L_{2}[0,1]:\|f\|_{{\mathcal{B}}^{\alpha}_{p,q}}<\infty\\}\;\text{and}\;\mathcal{B}^{\alpha,R}_{p,q}[0,1]=\\{f\in
L_{2}[0,1]:\|f\|_{{\mathcal{B}}^{\alpha}_{p,q}}\leq R\\},$ (11)

respectively. The above definition of the Besov space and norm is equivalent
to the classical one based on the weak derivatives of the function (see e.g.
Chapter 4 in [40]).

For the construction of our estimators, we consider a $A$-smooth wavelet basis
($A>\alpha$) with a compactly supported mother wavelet $\psi$ such that
wavelets $\psi_{lk}(x)=2^{l/2}\psi(2^{l}x-k)$ for $l\geq l_{0}$ and
$k=0,\dots,2^{l}-1$ form an orthonormal basis for
${\mathcal{B}}^{\alpha}_{p,q}[0,1]$.

We will briefly describe in broad terms the idea behind using the wavelet
transform (10) to construct the global and pointwise optimal estimators. Both
estimators are based on wavelet approximations up until a limited resolution
level. Besides the excellent approximation properties of wavelets in Besov
spaces (see e.g. [40]), the first property ensures that a change in the data
in terms of $X_{i}^{(j)}$ has a limited change in terms of the “size” the
wavelet estimator. The second and third property yield a limited support that
shrinks at higher “resolution levels” of the wavelet functions, which controls
the number of wavelet coefficients affected by a change in $X_{i}^{(j)}$.
Making sure that changes in individual datums have a limited effect on the
shared transcript is crucial for assuring privacy. A further, more detailed
description of how these properties interlink is given in the Sections 3.2 and
3.3 below.

###  3.2 Constructing an optimal global estimator

We now proceed to construct the estimator, utilizing the wavelet transform of
(10), allowing the representation of a function $f$ in $L_{2}$ as a linear
combination of wavelet basis functions. We first introduce some notation. For
$\tau>0,x\in{\mathbb{R}}$, let $[x]_{\tau}$ denote $x$ clipped at the
threshold $\tau$:

$[x]_{\tau}:=\begin{cases}\tau\;\text{ if }x>\tau,\\\ x\;\text{ if }-\tau\leq
x\leq\tau\\\ -\tau\;\text{ otherwise.}\end{cases}$

Given $L\in{\mathbb{N}}$ and $\tau>0$, each machine $j=1,\dots,m$ computes the
real numbers

$\hat{f}^{(j)}_{lk;\tau}=\frac{1}{n_{j}}\sum_{i=1}^{n_{j}}\left[Y_{i}^{(j)}\right]_{\tau}\psi_{lk}\left(X_{i}^{(j)}\right),$
(12)

for $l,k\in{\mathbb{N}}$ such that $l_{0}\leq l\leq L$, $0\leq k\leq 2^{l}-1$.
We will specify the exact choice of $\tau$ and $L$ later. These numbers, which
we denote as the vector

$\boldsymbol{\hat{f}}^{(j)}_{L,\tau}:=\left\\{\hat{f}^{(j)}_{lk;\tau}:k=0,\ldots,2^{l}-1,l=l_{0},\ldots,L\right\\},$

will form the statistic underlying our transcript. To assure privacy, we aim
to communicate a noisy version of this vector. Adding additional noise leads
to an estimator that is necessarily worse, adding noise of a large enough
magnitude yields a final transcript satisfies the privacy guarantee of
Definition 1.1. To control the magnitude of the noise that needs to be added,
it is important to have a statistic that does not change too drastically when
the underlying data is changed in one data point. We formalize this in terms
of the _sensitivity_ of the statistic $\boldsymbol{\hat{f}}^{(j)}_{L,\tau}$.

The following lemma controls the _$L_{2}$ -sensitivity_ of the statistic
$\boldsymbol{\hat{f}}^{(j)}_{L,\tau}$, i.e. the difference in Euclidian
distance when applied to two neighboring data sets.

######  Lemma 3.1.

Let $Z^{(j)}$ and $\tilde{Z}^{(j)}$ any realizations of neighboring data sets.
It holds that

$\left\|\boldsymbol{\hat{f}}^{(j)}_{L,\tau}(Z^{(j)})-\boldsymbol{\hat{f}}^{(j)}_{L,\tau}(\tilde{Z}^{(j)})\right\|_{2}\leq
c_{\psi}\frac{\tau\sqrt{2^{L}}}{n_{j}}$

where $c_{\psi}$ is a constant depending only on the choice of wavelet basis.

We provide a proof for the lemma in Section B.1.1. The limited
$L_{2}$-sensitivity of the $\boldsymbol{\hat{f}}^{(j)}_{L,\tau}$ is a
consequence of merging two elements in its construction. First of, clipping
limits the change in (12) when $Y_{i}^{(j)}$ is exchanged for another data
point $\tilde{Y}_{i}^{(j)}$. In the vector as a whole, the coordinate wise
change is limited by the compact support of the wavelet basis. The essential
feature of the wavelet basis here is that, even though the basis elements
increase exponentially as the resolution levels $l$ increases, their support
shrinks proportionally, ensuring that each $X_{i}^{(j)}$ is in the support of
only finitely many wavelets at each resolution level. That is, there are at
most $c_{A}>0$ number of basis functions $\psi_{lk}$ with overlapping support
at each resolution level $l$, where $c_{A}>0$ depends on $A>\alpha$. This
means that changing one datum in $Z^{(j)}$, say $(Y_{i}^{(j)},X_{i}^{(j)})$ to
$(\tilde{Y}_{i}^{(j)},\tilde{X}_{i}^{(j)})$, has only a limited impact at the
level of the transcript $\boldsymbol{\hat{f}}^{(j)}_{L,\tau}(Z^{(j)})$.

The bounded $L_{2}$-sensitivity means that the statistic
$\boldsymbol{\hat{f}}^{(j)}_{L,\tau}(Z^{(j)})$, combined with additive,
appropriately scaled Gaussian noise satisfies
$(\varepsilon_{j},\delta_{j})$-differentially privacy. This result for
mappings with bounded $L_{2}$-sensitivity is well known and a proof can be
found in e.g. Appendix A of [32]. To be precise, the $j$-th server outputs
$\tilde{T}^{(j)}_{lk;\tau}=\hat{f}^{(j)}_{lk;\tau}+W^{(j)}_{lk}$ for
$\,k=0,\dots,2^{l}-1,\,l=l_{0},\dots,L$, where the coordinates of
$\boldsymbol{W}^{(j)}:=(W^{(j)}_{lk}:k=0,\ldots,2^{l}-1,l=l_{0},\ldots,L)$ are
i.i.d. mean zero gaussian with variance
$\frac{4\tau^{2}2^{L}c_{\psi}^{2}\log(2/\delta_{j})}{n_{j}^{2}\varepsilon_{j}^{2}}$.
The constant $c_{\psi}:=2\sqrt{2}\sqrt{c_{A}}\|\psi\|_{\infty}$ matches the
constant in Lemma 3.1. The addition of the gaussian noise ensures that the
transcript

${T}^{(j)}_{L,\tau}:=\left\\{T^{(j)}_{lk;\tau}\,:\,k=0,\dots,2^{l}-1,\,l=l_{0},\dots,L\right\\}=\boldsymbol{\hat{f}}^{(j)}_{L,\tau}(Z^{(j)})+\boldsymbol{W}^{(j)}$

is $(\varepsilon_{j},\delta_{j})$-differentially private.

The final estimator of $f$ is then obtained via a post-processing step in
which each of the transcripts is reweighted, taking the heterogeneity between
the servers into account. The choice of weight depends crucially on the local
number of observations $n_{j}$ and the local privacy constraint
$\varepsilon_{j}$. Given the transcripts
$T=({T}^{(1)}_{L,\tau},\dots,{T}^{(m)}_{L,\tau})$, the final estimator takes
the form of

$\hat{f}_{L,\tau}(x)=\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\left(\sum_{j=1}^{m}u_{j}T^{(j)}_{lk;\tau}\right)\psi_{k,l}(x),$

where the weights are given by

$u_{j}=\frac{v_{j}}{\sum_{j}v_{j}}\;\text{ with
}\;v_{j}=\left(n_{j}^{2}\varepsilon_{j}^{2}\right)\wedge\left(n_{j}2^{L}\right).$
(13)

The following theorem captures the global risk attained by the estimator
$\hat{f}_{L,\tau}$ resulting from the distributed
$(\boldsymbol{\epsilon},\boldsymbol{\delta})$-DP procedure outlined above,
with optimal selection of $L$ and a sufficiently large choice of $\tau$. For
the latter, a choice of $C_{\alpha,R}+\sqrt{(2\alpha+1)L}$ is adequate, where
$C_{\alpha,R}>0$ is a constant, as specified by Lemma B.6 or a larger
constant.

The variance of the Gaussian noise vectors $\boldsymbol{W}^{(j)}$, which yield
the privacy guarantee, increases with $L$. Consequently, the optimal choice of
$L$ is not just governed by the classical bias variance trade-off, but also by
the trade-off in the additional noise required to guarantee privacy.

The optimal choice of $L$ is taken as follows. Let $D>0$ be the number solving
the equation

$D^{2\alpha+2}=\sum_{j=1}^{m}\left(n_{j}^{2}\varepsilon_{j}^{2}\right)\wedge\left(n_{j}D\right).$
(14)

Setting $L=(l_{0}+1)\vee\lceil\log_{2}(D)\rceil$ yields the optimal
performance as described by the theorem below, in terms of a bias-variance-
sensitivity trade-off. Furthermore, this performance turns out to be the
theoretically best possible performance in a minimax sense, as established by
the lower bound of Theorem 4.1 in Section 4.

######  Theorem 3.2.

Set $\tau=C_{\alpha,R}+\sqrt{(2\alpha+1)L}$ and take
$L=(l_{0}+1)\vee\lceil\log_{2}(D)\rceil$, where $D>0$ is the solution to (14).

Then, the $L_{2}$-risk of the distributed
$(\boldsymbol{\varepsilon},\boldsymbol{\delta})$-DP protocol
$\hat{f}_{L,\tau}$ satisfies

$\sup_{f\in{\mathcal{B}}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}\left\|\hat{f}_{L,\tau}-f\right\|_{2}^{2}\leq
C_{\psi}\log(N)2^{-2L\alpha}\log(2/\delta^{\prime}),$

where $\delta^{\prime}=\min_{i\in[m]}\delta_{i}$ and $C_{\psi}$ denotes a
constant depending on $\psi$.

We briefly comment on the derived result. We first note that the choice of
wavelet basis (in particular the father wavelet $\psi$) influences the
constants in the theorem, but not the convergence rate. The rate attained by
the choice of $L$ as directed by (14) yields optimal rate as given in
Corollary 1 in case of homogeneous servers, the optimal rate of Corollary 3 in
case the privacy budgets satisfy (8) or the optimal rates of Corollary 4 in
case the budget satisfies (9).

###  3.3 Constructing an optimal estimator of $f$ at a point

We now turn to the task of estimating the unknown function
$f\in{\mathcal{B}}^{\alpha,R}_{p,q}$ at a given point $x_{0}\in(0,1)$. That is
to say, we will construct an estimator $\hat{f}$ such that
${\mathbb{E}}_{f}(\hat{f}(x_{0})-f(x_{0}))^{2}$ achieves the optimal rates as
predicated by Corollaries 2, 3 and 4.

A natural estimator of $f(x_{0})$ is to use the global plug-in estimator of
the previous section, $\hat{f}_{L,\tau}(x_{0})$, with $\hat{f}_{L,\tau}$ as
constructed in the previous section. However, for estimation at a point as
goal of inference, we instead opt for estimating $f(x_{0})$ locally. Similarly
to the pre-processing step in Section 3.2, the preliminary local estimator is
to be perturbed with noise to ensure it satisfies the DP constraint of
Definition 1.1. Adding Laplacian noise turns out to suffice to ensure
$(\varepsilon_{j},0)$-DP, which is a stronger guarantee than
$(\varepsilon_{j},\delta_{j})$-DP. Another advantage to this approach compared
to the plug-in estimator $\hat{f}_{L,\tau}(x_{0})$ is that the procedure
derived below has a $\log(N)$-factor improved rate compared to the plug-in
estimator.

As a first step in constructing the estimator of $f(x_{0})$, we consider for
$L\in{\mathbb{N}}$ and $\tau>0$ the first wavelet coefficients
$\boldsymbol{\hat{f}}^{(j)}_{L,\tau}$ as computed in (12). On the $j$-th
server, we construct the estimator corresponding to
$\boldsymbol{\hat{f}}^{(j)}_{L,\tau}$, which we then evaluate in the point
$x_{0}$,

$\hat{f}_{L,\tau}^{(j)}(x_{0})\equiv\hat{f}_{L,\tau}^{(j)}(x_{0}|Z^{(j)}):=\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\hat{f}^{(j)}_{lk;\tau}\psi_{lk}(x_{0}).$
(15)

In order to create a $(\varepsilon_{j},0)$-DP transcript, we add Laplacian
noise to $\hat{f}_{L,\tau}^{(j)}(x_{0})$ directly. Laplacian noise performs
well for statistics with small $L_{1}$-_sensitivity_ , i.e. the change in
$L_{1}$-norm when one datum is changed underlying the statistic. The
$L_{1}$-sensitivity scales poorly in the dimension of the statistic compared
to the $L_{2}$-sensitivity dictating the noise of the Gaussian mechanism of
Section 3.2. Essentially, the estimator proposed in (15) has large sensitivity
only for observations that are “close” to $x_{0}$. To see this, note that
$\psi_{lk}\lesssim 2^{l/2}$ and that the latter estimator can be written as

$\hat{f}_{L,\tau}^{(j)}(x_{0}|Z^{(j)})=\sum_{l=l_{0}}^{L}\sum_{k\in
K_{l}(x_{0})}\hat{f}^{(j)}_{lk;\tau}\psi_{lk}(x_{0}),$

where $K_{l}(x_{0}):=\\{k:\psi_{lk}(x_{0})\neq 0\\}$. Using this fact, the
lemma below gives an exact bound on the $L_{1}$-sensitivity of the functional
$\hat{f}_{L,\tau}^{(j)}(x_{0})$.

######  Lemma 3.3.

Let $Z^{(j)}$ and $\tilde{Z}^{(j)}$ any realizations of neighboring data sets.
It holds that

$\left\|\hat{f}_{L,\tau}^{(j)}(x_{0}|Z^{(j)})-\hat{f}_{L,\tau}^{(j)}(x_{0}|\tilde{Z}^{(j)})\right\|_{1}\leq
c^{\prime}_{\psi}\frac{\tau 2^{L}}{n_{j}},$ (16)

where $c^{\prime\prime}_{\psi}:=2c_{A}\|\psi\|_{\infty}^{2}$ is a constant
depending only on the choice of wavelet basis.

This bound on the $L_{1}$-sensitivity yields that as a privacy mechanism it
suffices to add Laplace noise with variance $\frac{c^{\prime}_{\psi}\tau
2^{L}}{n_{j}\varepsilon_{j}}$ to the functional
$\hat{f}_{L,\tau}^{(j)}(x_{0})$. That is, the transcript $T^{(j)}_{lk,\tau}$
for $j\in[m]$ given by

$T^{(j)}_{L,\tau}=\hat{f}_{L,\tau}^{(j)}(x_{0})+W^{(j)},\quad\mathrm{where}\quad
W^{(j)}\overset{i.i.d}{\sim}\mathrm{Lap}\left(0,\frac{c^{\prime}_{\psi}\tau
2^{L}}{n_{j}\varepsilon_{j}}\right)$

is $(\varepsilon_{j},0)$-DP (see e.g. [32]). With each $j$-th server
transmitting $T^{(j)}_{L,\tau}$, the estimator computed in the central server
is given by $\hat{f}(x_{0})=\sum_{j=1}^{m}u_{j}T^{(j)}_{L,\tau}$.

It remains to determine the optimal choice of $L$. Similarly as in in the case
of the estimator of global risk as presented in Section 3.2, there is a trade-
off between bias, variance and sensitivity, where the $L_{1}$-sensitivity can
be seen to have a dependence on $L$. The explanation for this, is that even
though the functional $\hat{f}_{L,\tau}^{(j)}(x_{0})$ is unidimensional, the
wavelet resolution level $L$ still determines how a change in an individual
datum can potentially change the value of a local estimator defined in (15).

Here, the choice of $L$ is governed by
$L=(l_{0}+1)\vee\lceil\log_{2}(D)\rceil$, where $D>0$ be the number solving
the equation

$D^{2\nu+2}=\sum_{j=1}^{m}\left(n_{j}^{2}\varepsilon_{j}^{2}\right)\wedge\left(n_{j}D\right).$
(17)

The following theorem describes the performance of the pointwise estimator on
the basis of the $(\boldsymbol{\varepsilon},\boldsymbol{\delta})$-DP
transcript $T=({T}^{(1)}_{L,\tau},\dots,{T}^{(m)}_{L,\tau})$ for a
sufficiently large choice of $\tau$, such as
$\tau=C_{\nu,R}+\sqrt{2(2\nu+1)L}$, with $C_{\nu,R}>0$ as given by Lemma B.6.

######  Theorem 3.4.

Set $\tau=C_{\nu,R}+\sqrt{2(2\nu+1)L}$ and take
$L=(l_{0}+1)\vee\lceil\log_{2}(D)\rceil$, where $D$ is governed by (17).

Then, the pointwise $\ell_{2}$-risk of the distributed
$(\boldsymbol{\varepsilon},\boldsymbol{\delta})$-DP protocol
$\hat{f}_{L,\tau}$ satisfies

$\sup_{f\in{\mathcal{B}}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}(\hat{f}(x_{0})-f(x_{0}))^{2}\leq
C_{\psi}\log(N)2^{-2L\nu}.$

for a constant $C_{\psi}>0$ depending only on the choice of wavelet basis.

The rate attained by the choice of $L$ as directed by (17) does not just yield
the best possible bias-variance-sensitivity trade-off for the estimator class
under consideration, but it turns out to be minimax optimal (up to a log
factor) as established in the lower bound of Theorem 4.4. It consequently
yields the optimal rate as given in Corollary 2 in case of homogeneous
servers, the optimal rate of Corollary 3 in case the privacy budgets satisfy
(8) or the optimal rates of Corollary 4 in case the budget satisfies (9). As
is the case with Theorem 3.2, the choice of wavelet basis influences the
constants in the theorem, but not the convergence rate.

##  4 Minimax Lower Bounds

Theorems 3.2 and 3.4 provide the rates of convergence for the proposed
estimators of $f$ and $f(x_{0})$, respectively. In this section we shall show
that these rates of convergence are indeed optimal among all estimators by
establishing two matching minimax lower bounds, up to logarithmic factors, for
global and pointwise estimation. These results affirm the optimality of the
estimators presented in Section 3.

The lower bounds are presented in Theorems 4.1 and 4.4 for the global and
pointwise risks, respectively. The derivation of each lower bound relies on
entirely distinct techniques, elaborated in Section 4.1 and Section 4.2.

###  4.1 Minimax lower bounds under heterogeneous distributed DP constraints

The following theorem states a lower bound on the minimax risk for global
estimation.

######  Theorem 4.1.

Let $D>0$ be the solution to (14) and assume that
$\delta_{j}<(n_{j}^{1/2}\varepsilon_{j}^{2}(D\vee 1)^{-1})$ for some
$\kappa>0$ and all $j\in[m]$. Then, we have the following lower bound on the
minimax risk:

$\inf_{\hat{f}\in{\mathcal{M}}(\boldsymbol{\varepsilon},\boldsymbol{\delta})}\,\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}\mathbb{E}_{f}\|\hat{f}-f\|_{2}^{2}\gtrsim
D^{-2\alpha}\wedge 1.$ (18)

Before outlining the proof, we briefly note that this lower bound matches that
of the upper bound of Theorem 3.2 (up to a log-factor), for the choice
$L=(l_{0}+1)\vee\lceil\log_{2}(D)\rceil$ in the estimator under consideration
in Section 3.2. The theorem affirms that, up to a log factor, the proposed
estimator attains the best rate among all privacy constrained estimators.

Next, we discuss the most important steps in the proof here, whilst leaving
the technical details to the appendix. To lower bound the global risk, we
first restrict to a finite-dimensional sub-model of the Besov space
$\mathcal{B}^{\alpha,R}_{p,q}$. To align notation with the previous section,
we shall use the wavelet basis from before to do so. Given $L\in{\mathbb{N}}$,
we consider the finite-dimensional subspace

$\mathcal{B}^{\alpha,R,L}_{p,q}:=\left\\{f\in\mathcal{B}^{\alpha,R}_{p,q}:f=\sum_{k=0}^{2^{L}-1}f_{Lk}\psi_{Lk},\;f_{Lk}\in[-2^{-L(\alpha+1/2)}R,2^{-L(\alpha+1/2)}R]\right\\}.$

Let $\boldsymbol{\psi}(X)$ denote the $2^{L}$ dimensional vector
$\\{\psi_{Lk}(X)\\}_{k=1}^{2^{L}}$ and define

$\boldsymbol{S}_{f}\left(Z_{i}^{(j)}\right):=\sigma^{-1}\left(Y^{(j)}_{i}-\sum_{k=0}^{2^{L}-1}f_{Lk}\psi_{Lk}\left(X^{(j)}_{i}\right)\right)\boldsymbol{\psi}\left(X^{(j)}_{i}\right).$
(19)

The random vector $\boldsymbol{S}_{f}(Z_{i}^{(j)})$ can be seen as an “score
function” of the $i$-th observation on the $j-$th server, within the finite
dimensional sub-model. Similarly, consider the “score function” for local data
$Z^{(j)}$ on the $j$th server;
$\boldsymbol{S}_{f}(Z^{(j)}):=\sum_{i=1}^{n_{j}}\boldsymbol{S}_{f}(Z_{i}^{(j)})$.
Furthermore, let $\boldsymbol{C}_{f}(T^{(j)})$ denote the $2^{L}$ dimensional
matrix

$\mathbb{E}\;\mathbb{E}\left[\boldsymbol{S}_{f}\left(Z^{(j)}\right)\mid
T^{(j)}\right]\mathbb{E}\left[\boldsymbol{S}_{f}\left(Z^{(j)}\right)\mid
T^{(j)}\right]^{T}.$ (20)

We shall write $\boldsymbol{C}_{f}(Z^{(j)})$ for the unconditional version
covariance matrix of $\boldsymbol{S}_{f}(Z^{(j)})$and let
$\boldsymbol{C}_{f,i}^{{(j)}}=\mathbb{E}\left[\boldsymbol{S}_{f}(Z_{i}^{(j)})\boldsymbol{S}_{f}(Z_{i}^{(j)})^{T}\right]$,
such that $\boldsymbol{C}_{f}=\sum_{i=1}^{n_{j}}\boldsymbol{C}_{f,i}^{{(j)}}$.

Using the Van-Trees inequality (with a prior as specified later on in the
section), we obtain an expression in terms of the sum-of-traces of the
matrices in display (20), i.e. the covariance of the score function
$\boldsymbol{S}_{f}(Z^{(j)})$, conditionally on the released transcripts.

As the conditional expectation contracts the $L_{2}$-norm, we have the “data
processing” bound
$\boldsymbol{C}_{f}(T^{(j)})\leq\boldsymbol{C}_{f}(Z^{(j)})$, which in turn
implies that

$\text{Tr}(\boldsymbol{C}_{f}(T^{(j)}))\leq\text{Tr}(\boldsymbol{C}_{f}(Z^{(j)})).$
(21)

The right-hand side can be bounded by $2^{L}n_{j}$ by direct calculation,
which we defer to Section B.2. These standard bounds do not take the privacy
constraints into account and would lead to the unconstrained minimax rate.

To capture the loss of information stemming from the DP constraint of
Definition 1.1, a more sophisticated data processing argument is required.
This bring us to one of the key technical innovations of the paper, which
comes in the form of a data-processing inequality (Lemma 4.2 below) for the
conditional covariance given a $(\varepsilon_{j},\delta_{j})$-differentially
private transcripts of linear functionals of the data such as the score
$\boldsymbol{S}_{f}(Z_{i}^{(j)})$. The lemma can be seen as a geometric
version of the “score attack” lower bound of [19]. Combining this data
processing step with the linearity of the trace accommodates for the
heterogeneity between the servers.

######  Lemma 4.2.

Let $\delta_{j}\log(1/\delta_{j})<n_{j}^{1/2}\varepsilon_{j}^{2}(D\vee
1)^{-1}$ for $j=1,\dots,m$. There exists a universal constant $C>0$ such that

$\displaystyle\mathbb{E}\left[\mathrm{Tr}(\boldsymbol{C}_{f}(T^{(j)}))\right]\leq
Cn_{j}\varepsilon_{j}\sqrt{\mathbb{E}\left[\mathrm{Tr}(\boldsymbol{C}_{f}(T^{(j)}))\right]}$
$\displaystyle\sqrt{\lambda_{\max}(\boldsymbol{C}_{f,i})}$
$\displaystyle+C\delta_{j}\left(2^{L}n_{j}^{1/2}\log(1/\delta_{j})+n_{j}\right).$

In Section B.2 of the appendix, we show that the largest eigenvalue of
$\boldsymbol{C}_{f,i}$; $\lambda_{\max}(\boldsymbol{C}_{f,i})$, is bounded,
from which it follows from the
$\mathbb{E}\left[\mathrm{Tr}(\boldsymbol{C}_{f}(T^{(j)}))\right]\lesssim
n_{j}^{2}\varepsilon_{j}^{2}$ uniformly for
$f\in\mathcal{B}^{\alpha,R,L}_{p,q}$ whenever $\delta_{j}$ is of smaller than
$n_{j}^{1/2}\varepsilon_{j}^{2}D^{-1}$.

With the two bounds on the trace of $\boldsymbol{C}_{f}(T^{(j)})$ in hand, we
now lower bound global estimation risk using the Van-Trees inequality. The
Van-Trees inequality provides an expression in terms of the trace of a certain
covariance matrix, which is the conditional covariance of a linear functional
of the data. Combined with the data processing inequalities, the linearity of
the trace accommodates for the heterogeneity between the servers.

In order to apply the Van-Trees inequality, we first define a prior such that
the worst-case global risk is lower bounded by the corresponding Bayes risk.
To that extent, we define a prior $\Pi$ that is supported on
$\mathcal{B}^{\alpha,R,L}_{p,q}$. Given the resolution level
$L\in{\mathbb{N}}$, we draw $f_{Lk}$ independently from the probability
distribution $\Pi_{Lk}$, defined through an appropriately rescaled version of
the density $t\mapsto\cos^{2}(\pi t/2)\mathbbm{1}_{|t|\leq 1)}$ such that has
its support equal to $[-2^{-L(\alpha+1/2)}R,2^{-L(\alpha+1/2)}R]$ for
$k=0\dots,2^{L}-1$ and set $f_{lk}=0$ otherwise. For this choice of prior, the
Van-Trees inequality of [39] yields the following lemma, for which we defer
the details of the proof to Section B.2 in the appendix.

######  Lemma 4.3.

It holds that
$\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}\mathbb{E}_{f}\|\hat{f}-f\|_{2}^{2}$
is lower bounded by the Bayes risk
$\int\mathbb{E}_{f}\|\hat{f}-f\|_{2}^{2}d\Pi(f)$, which is further lower
bounded as follows

$\int\mathbb{E}_{f}\|\hat{f}-f\|_{2}^{2}d\Pi(f)\geq\frac{2^{2L}}{\sup_{f\in\mathcal{B}^{\alpha,R,L}_{p,q}}\sum_{j=1}^{m}\mathrm{Tr}(\boldsymbol{C}_{f}(T^{(j)}))+\pi^{2}2^{L(2\alpha+2)}}.$

Combining the upper bound on the trace of $\boldsymbol{C}_{f}(T^{(j)})$ of
(21) and Lemma 4.2, we have, by Lemma 4.3, that

$\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}\mathbb{E}_{f}\|\hat{f}-f\|_{2}^{2}\gtrsim\frac{2^{2L}}{\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\wedge
n_{j}2^{L}+\pi^{2}2^{L(2\alpha+2)}}.$

We obtain the desired lower bound by choosing an $L$ that maximizes the lower
bound. Setting $L=(l_{0}+1)\vee\lceil\log_{2}(D)\rceil$ can be seen to do so
by the relationship (14), which proves Theorem 4.1.

###  4.2 Lower bound for the pointwise risk

In this section, we derive the minimax lower bound for the pointwise risk. We
first present the lower bound as the main result of the section in the form of
Theorem 4.4, after which we discuss its proof. The theorem tells us that the
pointwise risk estimator proposed in Section 3.3 performs optimally in terms
of achieving the minimax privacy constrained rate up to a logarithmic factor.

######  Theorem 4.4.

Let $D>0$ be the number solving the equation

$D^{2\nu+2}=\sum_{j=1}^{m}\left(n_{j}^{2}\varepsilon_{j}^{2}\right)\wedge\left(n_{j}D\right).$
(22)

Assume furthermore that $\sum_{j}n_{j}\delta_{j}\to 0$. Then, for any
$x_{0}\in(0,1)$, the minimax pointwise risk is lower bounded as follows:

$\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}\mathbb{E}_{f}\left(\hat{f}(x_{0})-f(x_{0})\right)^{2}\gtrsim
D^{-2\nu}\wedge 1.$

Whenever
$\left(\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\right)^{\frac{1}{2\nu+2}}\geq\max_{j}n_{j}\epsilon_{j}^{2}$,
the right hand side is further bounded from below by
$\left(\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\right)^{-\frac{2\nu}{2\nu+2}}\wedge
1$.

The proof of the theorem is based around the Le Cam two point method, which is
a common approach to lower bounding the pointwise risk, see for example [72].
However, to capture the effect of the transcripts satisfying the DP constraint
of Definition 1.1, we introduce a coupling argument in conjunction.

We briefly sketch the two point method and coupling argument here, leaving the
technical details to the appendix. Take any function
$f\in{\mathcal{B}}^{\alpha}_{p,q}$ such that
$\|f\|_{{\mathcal{B}}^{\alpha}_{p,q}}=R^{\prime}<R$ and a compactly supported
function $g\in{\mathcal{B}}^{\alpha}_{p,q}$ such that
$\|g\|_{{\mathcal{B}}^{\alpha}_{p,q}}\leq R-R^{\prime}$ and $g(0)>0$. Define a
third function

$\tilde{f}(t):=\gamma_{D}^{-1}g(\beta_{D}(t-x_{0}))+f(t),$

where $\gamma_{D}:=c_{0}^{-1}D^{\nu}$ and $\beta_{D}=\gamma_{D}^{1/\nu}$,
where we recall that $\nu=\alpha-\frac{1}{p}$. By e.g. Lemma 1 from [16],
$\|f\|_{{\mathcal{B}}^{\alpha}_{p,q}}\leq R$.

Let $(Y_{i}^{(j)},X_{i}^{(j)})\sim P_{f}$ and
$(\tilde{Y}_{i}^{(j)},\tilde{X}_{i}^{(j)})\sim P_{\tilde{f}}$ for individual
observations generated according to (1) with either $f$ or $\tilde{f}$ the
true underlying regression function respectively. We construct a coupling
between $P_{f}$ and $P_{\tilde{f}}$ such that $(Y_{i}^{(j)},X_{i}^{(j)})$ and
$(\tilde{Y}_{i}^{(j)},\tilde{X}_{i}^{(j)})$ are equal with probability
proportional to $\sigma^{-1}\|\tilde{f}-f\|_{1}$, which forms the content of
the following lemma.

######  Lemma 4.5.

There exists a joint distribution $P_{f,\tilde{f}}$ of
$\left((Y_{i}^{(j)},X_{i}^{(j)}),(\tilde{Y}_{i}^{(j)},\tilde{X}_{i}^{(j)})\right)$
such that

$\rho:=P_{f,\tilde{f}}\left(\left(Y_{i}^{(j)},X_{i}^{(j)}\right)\neq\left(\tilde{Y}_{i}^{(j)},\tilde{X}_{i}^{(j)}\right)\right)\leq\frac{c}{\sigma}\|\tilde{f}-f\|_{1},$
(23)

for a universal constant $c>0$.

We prove the above lemma in Section C.3. Loosely speaking, the quantity $\rho$
captures the difficulty of distinguishing individual observations from $P_{f}$
of those generated from $P_{\tilde{f}}$.

Consider now transcripts $T=(T^{(1)},\dots,T^{(m)})$ each satisfying the DP
constraint of Definition 1.1 with a privacy budget
$(\boldsymbol{\varepsilon},\boldsymbol{\delta})$, and let ${\mathbb{P}}_{f}$
denote the joint law of transcripts and the $N=\sum_{j=1}^{m}n_{j}$
observations generated from $P_{f}$. Let ${\mathbb{P}}_{f}^{T}$ denote the
push-forward measure of the transcript, i.e. its marginal distribution given
that the data is generated by $P_{f}$. Similarly, let
${\mathbb{P}}_{\tilde{f}}$ denote the joint law of $T$ with the data generated
from $P_{\tilde{f}}$ and let ${\mathbb{P}}_{\tilde{f}}^{T}$ denote the
corresponding marginal distribution of $T$. With the coupling of Lemma 4.5 in
hand, we derive the following lemma.

######  Lemma 4.6.

For any subset $S\subseteq[m]$,

$\left\|{\mathbb{P}}_{f}^{T}-{\mathbb{P}}_{\tilde{f}}^{T}\right\|_{\mathrm{TV}}\leq\sqrt{2}\sqrt{\sum_{j\in
S}\bar{\varepsilon}_{j}\left(e^{\bar{\varepsilon}_{j}}-1\right)+\sum_{j\in
S^{c}}n_{j}D_{\mathrm{KL}}(P_{f};P_{\tilde{f}})}+4\underset{j\in
S}{\overset{}{\sum}}e^{\bar{\varepsilon}_{j}}n_{j}\delta_{j}\rho,$ (24)

where $\bar{\varepsilon}_{j}=6n_{j}\varepsilon_{j}\rho$, $\rho$ as defined in
(23).

We defer a proof of the lemma to Section C.3 of the appendix. The lemma allows
analysis of the contributions of the separate the servers, accounting for the
heterogeneity in the privacy budgets $(\epsilon_{j},\delta_{j})$ and the
differing number of observations. Roughly speaking, for servers with
relatively large privacy budgets, their contribution to the estimator is to be
captured by $n_{j}D_{\mathrm{KL}}(P_{f};P_{\tilde{f}}^{T})$, which does not
involve the privacy budget all together. Servers for which the privacy budget
is more stringent, contribute with the (potentially) smaller quantity
$\bar{\varepsilon}_{j}$, where $\rho$ corresponds to the probability in (23),
established in the coupling relationship of Lemma 4.5.

The optimal division into these stringent and non-stringent privacy budgets is
made by taking

$S=\left\\{j\in[m]:\varepsilon_{j}\leq\sqrt{{D}/{n_{j}}}\right\\},$

in the sense that this choice of $S$ minimizes the right-hand side of (24).
With this choice of $S$, the bound on $\rho$ established in Lemma 4.5 and the
fact that by the construction of $\tilde{f}$ we have
$\|\tilde{f}-f\|_{1}=\gamma_{D}^{-1}\beta_{D}^{-1}\|g\|_{1}$ with
$\gamma_{D}:=c_{0}^{-1}D^{\nu}$ and $\beta_{D}=\gamma_{D}^{1/\nu}$, we obtain
that

$\displaystyle\sum_{j\in
S}\bar{\varepsilon}_{j}\left(e^{\bar{\varepsilon}_{j}}-1\right)\lesssim\sum_{j\in
S}n_{j}^{2}\varepsilon_{j}^{2}\rho^{2}\leq\gamma_{D}^{-2}\beta_{D}^{-2}\|g\|_{1}^{2}\sum_{j\in
S}n_{j}^{2}\varepsilon_{j}^{2}=c_{0}^{2+2/\nu}D^{-2-2\nu}\|g\|_{1}^{2}\sum_{j\in
S}n^{2}_{j}\varepsilon_{j}^{2}.$

The bound
$D_{\mathrm{KL}}(P_{\tilde{f}};P_{f})\lesssim\sigma^{-2}\|\tilde{f}-f\|_{2}^{2}$,
which is obtained through standard calculations, combined with the fact that
$\|\tilde{f}-f\|_{2}^{2}\lesssim\gamma_{D}^{-2}\beta_{D}^{-1}\|g\|_{2}^{2}$ by
construction,

$\sum_{j\in S^{c}}n_{j}D_{\mathrm{KL}}(P_{f};P_{\tilde{f}})\lesssim
c_{0}^{1+2/\nu}D^{-2-2\nu}\|g\|_{2}^{2}\sum_{j\in S^{c}}n_{j}D.$

In Section C.3 of the appendix, it is shown that if $\sum_{j\in
S}n_{j}\delta_{j}=o(1)$ as is assumed in the theorem, it holds that
$\underset{j\in
S}{\overset{}{\sum}}e^{\bar{\varepsilon}_{j}}n_{j}\delta_{j}\rho=o(1)$ for the
particular choice of $S$ as well. Per the choice of the set $S$ and $D$
satisfying (17), we obtain that for $c_{0}<1$,

$\left\|{\mathbb{P}}_{f}^{T}-{\mathbb{P}}_{\tilde{f}}^{T}\right\|_{\mathrm{TV}}\leq
Cc_{0}^{1+2/\nu}+o(1).$

By taking the constant $c_{0}$ sufficiently small, the conclusion of Theorem
4.4 follows by Le Cam’s two point method (see e.g. Lemma 1 in [72]), which
then yields that

$\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}\mathbb{E}_{f}\left(\hat{f}(x_{0})-f(x_{0})\right)^{2}\gtrsim\left(\tilde{f}(x_{0})-f_{0}(x_{0})\right)^{2}\gtrsim\gamma_{n}^{-2}g^{2}(0)\gtrsim
D^{-2\nu},$

proving the theorem.

##  5 Discussion

The findings in the present paper highlight the trade-off between statistical
accuracy and privacy preservation within the context of federated
nonparametric regression. The results under the heterogeneous setting quantify
the degree to which the individual DP constraints, as well as the degree to
which observations are distributed among the different servers, impact the
statistical performance as measured by the minimax risk. Furthermore, we find
that the influence of the privacy constraints on the optimal performance
depends on the inferential task at hand, with global estimation of an unknown
function being subject to a different performance impact than estimation of a
function at a point. For each of these inferential tasks, we provide an
estimation procedure that attains the optimal statistical performance up to a
logarithmic factor.

One promising direction for future research is the exploration of adaptive
estimation in the federated learning framework. While our paper characterizes
the statistical performance for nonparametric regression in a heterogeneous
setting, the estimation procedures in this paper assume knowledge about the
regularity of the underlying function. However, in many real-world
applications, the regularity is unknown and estimators that can adapt to the
true underlying regularity are required to attain the best possible
performance. while such adaptive techniques exist for problems without privacy
constraints (see e.g. [27, 16]), the theoretical (im)possibilities of
adaptation under privacy constraints are relatively understudied. Such
adaptive techniques might serve dual purposes: they could potentially refine
the statistical accuracy while also optimizing the DP constraints for
individual servers, especially when the constraints are dynamic or based on
real-time needs. We leave this for future work.

Another promising avenue for future research is nonparametric hypothesis
testing. It is well known that testing in nonparametric settings is subject to
different phenomena than estimation, see for example [46]. However, under
privacy constraints, the theoretical best possible performance in
nonparametric hypothesis testing is not well understood. Addressing this
question complements our understanding of the estimation problem.

The research of Tony Cai was supported in part by NIH grants R01-GM123056 and
R01-GM129781.

Supplement to “Optimal Federated Learning for Nonparametric Regression with
Heterogenous Distributed Differential Privacy Constraints” In the supplement
to this paper, we present the detailed proofs for the main theorems in the
paper “Optimal Federated Learning for Nonparametric Regression with
Heterogenous Distributed Differential Privacy Constraints”.

## References

  * [1] [author] Abowd, John MJ. M., Rodriguez, Ian MI. M., Sexton, William NW. N., Singer, Phyllis EP. E. and Vilhuber, LarsL. (2020). The modernization of statistical disclosure limitation at the US Census Bureau. US Census Bureau.
  * [2] [author] Acharya, JayadevJ., Bonawitz, KallistaK., Kairouz, PeterP., Ramage, DanielD. and Sun, ZitengZ. (2020). Context Aware Local Differential Privacy. In Proceedings of the 37th International Conference on Machine Learning (Hal DauméH. D. III and AartiA. Singh, eds.). Proceedings of Machine Learning Research 119 52–62. PMLR.
  * [3] [author] Acharya, JayadevJ., Canonne, Clément LC. L. and Tyagi, HimanshuH. (2020). Distributed Signal Detection under Communication Constraints. In Proceedings of Thirty Third Conference on Learning Theory (JacobJ. Abernethy and ShivaniS. Agarwal, eds.). Proceedings of Machine Learning Research 125 41–63. PMLR.
  * [4] [author] Acharya, JayadevJ., Liu, YuhanY. and Sun, ZitengZ. (2023). Discrete Distribution Estimation under User-level Local Differential Privacy. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (FranciscoF. Ruiz, JenniferJ. Dy and Jan-WillemJ.-W. van de Meent, eds.). Proceedings of Machine Learning Research 206 8561–8585. PMLR.
  * [5] [author] Acharya, JayadevJ., Sun, ZitengZ. and Zhang, HuanyuH. (2018). Differentially Private Testing of Identity and Closeness of Discrete Distributions. In Advances in Neural Information Processing Systems (S.S. Bengio, H.H. Wallach, H.H. Larochelle, K.K. Grauman, N.N. Cesa-Bianchi and R.R. Garnett, eds.) 31\. Curran Associates, Inc.
  * [6] [author] Arachchige, Pathum Chamikara MahawagaP. C. M., Bertok, PeterP., Khalil, IbrahimI., Liu, DongxiD., Camtepe, SeyitS. and Atiquzzaman, MohammedM. (2019). Local differential privacy for deep learning. IEEE Internet of Things Journal 7 5827–5842.
  * [7] [author] Barnes, Leighton PateL. P., Chen, Wei-NingW.-N. and Özgür, AyferA. (2020). Fisher information under local differential privacy. IEEE Journal on Selected Areas in Information Theory 1 645–659.
  * [8] [author] Barnes, Leighton PateL. P., Han, YanjunY. and Ozgur, AyferA. (2020). Lower bounds for learning distributions under communication constraints via Fisher information. Journal of Machine Learning Research 21 1–30.
  * [9] [author] Bassily, RaefR., Smith, AdamA. and Thakurta, AbhradeepA. (2014). Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science 464–473. IEEE.
  * [10] [author] Beaufays, FrancoiseF., Rao, KanishkaK., Mathews, RajivR. and Ramaswamy, SwaroopS. (2019). Federated learning for emoji prediction in a mobile keyboard.
  * [11] [author] Braverman, MarkM., Garg, AnkitA., Ma, TengyuT., Nguyen, Huy LH. L. and Woodruff, David PD. P. (2016). Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing 1011–1020.
  * [12] [author] Bun, MarkM., Ullman, JonathanJ. and Vadhan, SalilS. (2014). Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing 1–10.
  * [13] [author] Butucea, CristinaC., Dubois, AmandineA., Kroll, MartinM. and Saumard, AdrienA. (2020). Local differential privacy: Elbow effect in optimal density estimation and adaptation over Besov ellipsoids. Bernoulli 26 1727 – 1764. 10.3150/19-BEJ1165
  * [14] [author] Cai, T TonyT. T. (1999). Adaptive wavelet estimation: A block thresholding and oracle inequality approach. The Annals of Statistics 27 898–924.
  * [15] [author] Cai, T. TonyT. T. (2002). On block thresholding in wavelet regression: Adaptivity, block size, and threshold level. Statistica Sinica 12 1241-1274.
  * [16] [author] Cai, T TonyT. T. (2003). Rates of convergence and adaptation over Besov spaces under pointwise risk. Statistica Sinica 881–902.
  * [17] [author] Cai, T TonyT. T., Chakraborty, AbhinavA. and Vuursteen, LasseL. (2023). Supplement to “Optimal Federated Learning for Nonparametric Regression with Heterogenous Distributed Differential Privacy Constraints”.
  * [18] [author] Cai, T TonyT. T., Wang, YichenY. and Zhang, LinjunL. (2021). The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics 49 2825–2850.
  * [19] [author] Cai, T TonyT. T., Wang, YichenY. and Zhang, LinjunL. (2023). Score attack: A lower bound technique for optimal differentially private learning. arXiv preprint arXiv:2303.07152.
  * [20] [author] Cai, T. TonyT. T. and Wei, HongjiH. (2022). Distributed nonparametric regression: Optimal rate of convergence and cost of adaptation. The Annals of Statistics 50 698-725.
  * [21] [author] Cai, T. TonyT. T. and Wei, HongjiH. (2023). Distributed Gaussian mean estimation under communication constraints: Optimal rates and communication-efficient algorithms. Journal of Machine Learning Research to appear.
  * [22] [author] Canonne, Clément LC. L. and Sun, YuchengY. (2023). Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine. arXiv preprint arXiv:2309.06068.
  * [23] [author] Chaudhuri, SyomantakS. and Courtade, Thomas AT. A. (2023). Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Free. arXiv preprint arXiv:2305.09668.
  * [24] [author] Cohen, AlbertA., Daubechies, IngridI. and Vial, PierreP. (1993). Wavelets on the interval and fast wavelet transforms. Applied and computational harmonic analysis.
  * [25] [author] Daubechies, IngridI. (1992). Ten lectures on wavelets. SIAM.
  * [26] [author] Ding, BolinB., Kulkarni, JanardhanJ. and Yekhanin, SergeyS. (2017). Collecting telemetry data privately. Advances in Neural Information Processing Systems 30\.
  * [27] [author] Donoho, David LD. L. and Johnstone, Iain MI. M. (1998). Minimax estimation via wavelet shrinkage. The annals of Statistics 26 879–921.
  * [28] [author] Duchi, John CJ. C., Jordan, Michael IM. I. and Wainwright, Martin JM. J. (2013). Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science 429–438. IEEE.
  * [29] [author] Duchi, John CJ. C., Jordan, Michael IM. I. and Wainwright, Martin JM. J. (2018). Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association 113 182–201.
  * [30] [author] Duchi, John C.J. C., Jordan, Michael I.M. I., Wainwright, Martin J.M. J. and Zhang, YuchenY. (2014). Optimality guarantees for distributed statistical estimation. arXiv:1405.0782 [cs, math, stat]. arXiv: 1405.0782.
  * [31] [author] Dwork, CynthiaC. (2006). Differential privacy. In International colloquium on automata, languages, and programming 1–12. Springer.
  * [32] [author] Dwork, CynthiaC., Roth, AaronA. et al. (2014). The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science 9 211–407.
  * [33] [author] Dwork, CynthiaC. and Smith, AdamA. (2010). Differential privacy for statistics: What we know and what we want to learn. Journal of Privacy and Confidentiality 1\.
  * [34] [author] Dwork, CynthiaC., Smith, AdamA., Steinke, ThomasT. and Ullman, JonathanJ. (2017). Exposed! a survey of attacks on private data. Annual Review of Statistics and Its Application 4 61–84.
  * [35] [author] Dwork, CynthiaC., Smith, AdamA., Steinke, ThomasT., Ullman, JonathanJ. and Vadhan, SalilS. (2015). Robust traceability from trace amounts. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science 650–669. IEEE.
  * [36] [author] Dwork, CynthiaC., Talwar, KunalK., Thakurta, AbhradeepA. and Zhang, LiL. (2014). Analyze gauss: optimal bounds for privacy-preserving principal component analysis. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing 11–20.
  * [37] [author] Erlingsson, ÚlfarU., Pihur, VasylV. and Korolova, AleksandraA. (2014). RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. CCS ’14 1054–1067. Association for Computing Machinery, New York, NY, USA. 10.1145/2660267.2660348
  * [38] [author] Fallah, AlirezaA., Makhdoumi, AliA., Malekian, AzarakhshA. and Ozdaglar, AsumanA. (2023). Optimal and differentially private data acquisition: Central and local mechanisms. Operations Research.
  * [39] [author] Gill, Richard DR. D. and Levit, Boris YB. Y. (1995). Applications of the van Trees inequality: a Bayesian Cramér-Rao bound. Bernoulli 59–79.
  * [40] [author] Gine, EvaristE. and Nickl, RichardR. (2016). Mathematical Foundations of Infinite-Dimensional Statistical Models. Cambridge University Press, Cambridge. 10.1017/CBO9781107337862
  * [41] [author] Hall, PeterP., Kerkyacharian, GérardG. and Picard, DominiqueD. (1999). On the minimax optimality of block thresholded wavelet estimators. Statistica Sinica 33–49.
  * [42] [author] Han, YanjunY., Özgür, AyferA. and Weissman, TsachyT. (2018). Geometric lower bounds for distributed parameter estimation under communication constraints. In Conference On Learning Theory 3163–3188. PMLR.
  * [43] [author] Hard, AndrewA., Rao, KanishkaK., Mathews, RajivR., Ramaswamy, SwaroopS., Beaufays, FrançoiseF., Augenstein, SeanS., Eichner, HubertH., Kiddon, ChloéC. and Ramage, DanielD. (2018). Federated learning for mobile keyboard prediction. arXiv preprint arXiv:1811.03604.
  * [44] [author] Härdle, WolfgangW., Kerkyacharian, GerardG., Picard, DominiqueD. and Tsybakov, AlexanderA. (2012). Wavelets, approximation, and statistical applications 129\. Springer Science & Business Media.
  * [45] [author] Ibragimov, I.I. and Khasminskii, R.R. (1997). Some Estimation Problems in Infinite Dimensional Gaussian White Noise In Festschrift for Lucien Le Cam: Research Papers in Probability and Statistics 259–274. Springer New York, New York, NY. 10.1007/978-1-4612-1880-7_16
  * [46] [author] Ingster, Yu. I.Y. I. and Suslina, Irina A.I. A. (2003). Nonparametric Goodness-of-Fit Testing Under Gaussian Models. Lecture Notes in Statistics 169\. Springer New York, New York, NY. 10.1007/978-0-387-21580-8
  * [47] [author] Johnstone, Iain MI. M. (2019). Function Estimation and Gaussian Sequence Models. Unpublished manuscript.
  * [48] [author] Kamath, GautamG., Li, JerryJ., Singhal, VikrantV. and Ullman, JonathanJ. (2019). Privately learning high-dimensional distributions. In Conference on Learning Theory 1853–1902. PMLR.
  * [49] [author] Kamath, GautamG., Singhal, VikrantV. and Ullman, JonathanJ. (2020). Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory 2204–2235. PMLR.
  * [50] [author] Karwa, VisheshV. and Vadhan, SalilS. (2017). Finite sample differentially private confidence intervals. arXiv preprint arXiv:1711.03908.
  * [51] [author] Konečnỳ, JakubJ., McMahan, H BrendanH. B., Ramage, DanielD. and Richtárik, PeterP. (2016). Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv:1610.02527.
  * [52] [author] Kroll, MartinM. (2021). On density estimation at a fixed point under local differential privacy. Electronic Journal of Statistics 15 1783 – 1813. 10.1214/21-EJS1830
  * [53] [author] LeCam, LucienL. (1973). Convergence of estimates under dimensionality restrictions. The Annals of Statistics 38–53.
  * [54] [author] Levy, DanielD., Sun, ZitengZ., Amin, KareemK., Kale, SatyenS., Kulesza, AlexA., Mohri, MehryarM. and Suresh, Ananda TheerthaA. T. (2021). Learning with user-level privacy. Advances in Neural Information Processing Systems 34 12466–12479.
  * [55] [author] Li, TianT., Sahu, Anit KumarA. K., Talwalkar, AmeetA. and Smith, VirginiaV. (2020). Federated learning: Challenges, methods, and future directions. IEEE signal processing magazine 37 50–60.
  * [56] [author] Liu, YuhanY., Suresh, Ananda TheerthaA. T., Yu, Felix Xinnan XF. X. X., Kumar, SanjivS. and Riley, MichaelM. (2020). Learning discrete distributions: user vs item-level privacy. Advances in Neural Information Processing Systems 33 20965–20976.
  * [57] [author] Narayanan, ShyamS. (2022). Private high-dimensional hypothesis testing. In Conference on Learning Theory 3979–4027. PMLR.
  * [58] [author] Narayanan, ShyamS., Mirrokni, VahabV. and Esfandiari, HosseinH. (2022). Tight and robust private mean estimation with few users. In International Conference on Machine Learning 16383–16412. PMLR.
  * [59] [author] Nguyen, AnhA., Do, TuongT., Tran, MinhM., Nguyen, Binh XB. X., Duong, ChienC., Phan, TuT., Tjiputra, ErmanE. and Tran, Quang DQ. D. (2022). Deep federated learning for autonomous driving. In 2022 IEEE Intelligent Vehicles Symposium (IV) 1824–1830. IEEE.
  * [60] [author] Raginsky, MaximM. (2016). Strong data processing inequalities and $\backslash$Phi-Sobolev inequalities for discrete channels. IEEE Transactions on Information Theory 62 3355–3389.
  * [61] [author] Sart, MathieuM. (2023). Density estimation under local differential privacy and Hellinger loss. Bernoulli 29 2318 – 2341. 10.3150/22-BEJ1543
  * [62] [author] Smith, AdamA. (2011). Privacy-preserving statistical estimation with optimal convergence rates. In Proceedings of the forty-third annual ACM symposium on Theory of computing 813–822.
  * [63] [author] Szabo, BotondB. and van Zanten, HarryH. (2020). Adaptive distributed methods under communication constraints. The Annals of Statistics 48 2347–2380.
  * [64] [author] Szabó, BotondB. and van Zanten, HarryH. (2022). Distributed function estimation: Adaptation using minimal communication. Mathematical Statistics and Learning 5 159–199.
  * [65] [author] Szabó, BotondB., Vuursteen, LasseL. and Van Zanten, HarryH. (2022). Optimal distributed composite testing in high-dimensional Gaussian models with 1-bit communication. IEEE Transactions on Information Theory 68 4070–4084.
  * [66] [author] Szabó, BotondB., Vuursteen, LasseL. and Van Zanten, HarryH. (2023). Optimal high-dimensional and nonparametric distributed testing under communication constraints. The Annals of Statistics 51 909–934.
  * [67] [author] Team, ADPA. et al. (2017). Learning with privacy at scale. Apple Mach. Learn. J 1 1–25.
  * [68] [author] Thorisson, H.H. (2000). Coupling, Stationarity, and Regeneration. Probability and Its Applications. Springer New York.
  * [69] [author] Triebel, H.H. (1992). Theory of Function Spaces II. Monographs in mathematics. Springer.
  * [70] [author] Wasserman, LarryL. and Zhou, ShuhengS. (2010). A statistical framework for differential privacy. Journal of the American Statistical Association 105 375–389.
  * [71] [author] Ye, MinM. and Barg, AlexanderA. (2018). Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy. IEEE Transactions on Information Theory 64 5662-5676. 10.1109/TIT.2018.2809790
  * [72] [author] Yu, BinB. (1997). Assouad, Fano, and Le Cam In Festschrift for Lucien Le Cam: Research Papers in Probability and Statistics 423–435. Springer New York, New York, NY. 10.1007/978-1-4612-1880-7_29
  * [73] [author] Zhu, YuanchengY. and Lafferty, JohnJ. (2018). Distributed Nonparametric Regression under Communication Constraints. In Proceedings of the 35th International Conference on Machine Learning (JenniferJ. Dy and AndreasA. Krause, eds.). Proceedings of Machine Learning Research 80 6009–6017. PMLR.

, and

##  A Proof of the main results in Section 2

###  A.1 Proof of Theorem 2.1

###### Proof.

The statement of the theorem follows from Theorems 3.2 and 4.1 for the global
risk and Theorems 3.4 and 4.4 for the pointwise risk. Depending on which
problem we consider, the global or the pointwise estimation problem, the
minimax rate upto logarithmic factors of the order at most $\log^{2}(N)$ and
$\log(N)$ respectively, is given by $2^{-2L\gamma}$ where $\gamma=\alpha$ for
the former problem and $\gamma=\nu$ for the latter, where $L$ is given by
$(l_{0}+1)\vee\lceil\log_{2}(D)\rceil$. Furthermore, each of the minimax risks
is trivially bounded over the class ${\mathcal{B}}^{\alpha,R}_{p,q}$ since
$f\in{\mathcal{B}}^{\alpha,R}_{p,q}$ are bounded by a uniform constant (see
Lemma B.6) and the estimator $\hat{f}\equiv 0$ does not require any
information to be shared, so it is trivially
$(\boldsymbol{\epsilon},\boldsymbol{\delta})$-DP. ∎

###  A.2 Proof of Corollaries 1 and 2

###### Proof.

For these choices of $\varepsilon_{j}$ and $n_{j}$, $D$ is defined by

$D^{2\gamma+2}=m((n^{2}\varepsilon^{2})\wedge(nD)).$

The solution to this equation is
$D=(mn)^{\frac{1}{2\gamma+1}}\wedge(mn^{2}\varepsilon^{2})^{\frac{1}{2\gamma+2}}$.
In the regime where $\varepsilon>(\sqrt{m}n)^{-1}$, we have that $D>1$ and
consequently $2^{L}\asymp D$ for $L=(l_{0}+1)\vee\lceil\log_{2}D\rceil$. The
minimax rate
$(mn)^{-\frac{2\gamma}{2\gamma+1}}\wedge(mn^{2}\varepsilon^{2})^{-\frac{2\gamma}{2\gamma+2}}$
consequently follows from Theorems 3.2 and 4.1. Whenever
$\varepsilon\leq(\sqrt{m}n)^{-1}$, we find that $D\leq 1$, which consequently
yields $L=1$.

∎

###  A.3 Proof of Corollary 3

###### Proof.

Let $L$ be given by $(l_{0}+1)\vee\lceil\log_{2}(D)\rceil$, where $D$ is given
by

$D^{2\gamma+2}=\left(\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\right)\wedge\left(n_{j}D\right).$

Depending on which problem we consider, the global or the pointwise estimation
problem, Theorem 2.1 implies that the minimax rate follow upto logarithmic
factors is given by $D^{-2L\gamma}\wedge 1$ where $\gamma=\alpha$ for the
former problem and $\gamma=\nu$ for the latter. Using (8) the equation in the
display above reduces to
$D^{2\gamma+2}=\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}$. To see that
observe that if we set $D$ such that
$D^{2\gamma+2}=\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}$ then we have by
using (8) that $n_{j}^{2}\varepsilon_{j}^{2}\wedge
n_{j}D=n_{j}^{2}\varepsilon_{j}^{2}$ for $j=1,\ldots,m$, and hence the above
display simplifies.

If $\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\to\infty$ we have that
$D\to\infty$, in which case we obtain the rate
$\left(\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\right)^{-\frac{2\gamma}{2\gamma+2}}$,
upto logarithmic factors. Whenever
$\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\lesssim 1$, we have $D\lesssim 1$
which in turn implies that the risks are bounded away from zero by a constant.
∎

###  A.4 Proof of Corollary 4

###### Proof.

As in Corollary 3 we tackle both the global and pointwise problem together.
Let us denote by
$D^{*}=\left(n^{2}_{j^{*}}\varepsilon_{j^{*}}^{2}\right)^{\frac{1}{2\gamma+2}}\wedge
n_{j^{*}}^{\frac{1}{2\gamma+1}}$, condition (9) implies that

$\displaystyle\left(n_{j^{*}}^{2}\varepsilon_{j^{*}}^{2}\right)\wedge\left(n_{j^{*}}\left(\left(n^{2}_{j^{*}}\varepsilon_{j^{*}}^{2}\right)^{\frac{1}{2\gamma+2}}\wedge
n_{j^{*}}^{\frac{1}{2\gamma+1}}\right)\right)\geq\underset{[m]\setminus\\{j^{*}\\}}{\overset{}{\sum}}n_{j}^{2}\varepsilon_{j}^{2},$

$n^{2}_{j^{*}}\varepsilon_{j^{*}}^{2}\wedge
n_{j^{*}}D^{*}\geq\sum_{j\in[m]\setminus\\{j^{*}\\}}n_{j}^{2}\varepsilon_{j}^{2}$.
We show below that under the previously mentioned condition,

$D^{2\gamma+2}=\sum_{j=1}^{m}\left(n_{j}^{2}\varepsilon_{j}^{2}\right)\wedge\left(n_{j}D\right)\quad\implies\quad
D^{*}\leq D\leq cD^{*}$

for some fixed constant $c>1$.

Using the fact that $D$ solves the equation above, we have that
$D^{2\gamma+2}\geq n_{j^{*}}^{2}\varepsilon_{j^{*}}^{2}\wedge n_{j^{*}}D$, as
all the summands are positive. Hence, $D\geq D^{*}$. For obtaining an upper
bound we proceed as follows:

$\displaystyle D^{2\gamma+2}$ $\displaystyle\leq
n_{j^{*}}^{2}\varepsilon_{j^{*}}^{2}\wedge
n_{j^{*}}D+\sum_{j\in[m]\setminus\\{j^{*}\\}}n_{j}^{2}\varepsilon_{j}^{2}$
$\displaystyle\leq n_{j^{*}}^{2}\varepsilon_{j^{*}}^{2}\wedge
n_{j^{*}}D+n_{j^{*}}^{2}\varepsilon_{j^{*}}^{2}\wedge
n_{j^{*}}D^{*}\quad(\text{by}~{}\eqref{eq:dominant_budget})$
$\displaystyle\leq 2n_{j^{*}}^{2}\varepsilon_{j^{*}}^{2}\wedge
n_{j^{*}}D\quad(\text{by }D^{*}\leq D)$

The last line can be shown to imply $D\leq
c\left(n^{2}_{j^{*}}\varepsilon_{j^{*}}^{2}\right)^{\frac{1}{2\gamma+2}}\wedge
n_{j^{*}}^{\frac{1}{2\gamma+1}}=cD^{*}$, for some $c>1$. Hence we can conclude
that $D\asymp D^{*}$, which gives us the proposed rate $(D^{*})^{-2\nu}$. ∎

##  B Proofs of the global risk estimation results

We would divide the proofs of the global estimation problem into two sections.
Section B.1 presents the proof the lemmas and theorem pertaining to the
proving the minimax upper bounds, whereas Section B.2 states the proofs of the
results pertaining to the lower bound.

###  B.1 Upper Bound Proofs

####  B.1.1 Proof of Lemma 3.1

###### Proof.

Consider two neighboring data sets $Z^{(j)}$ and $\tilde{Z}^{(j)}$, meaning
that at most for one $i\in[n]$ it holds that

$Z^{(j)}_{i}=(Y_{i}^{(j)},X_{i}^{(j)})\neq(\tilde{Y}_{i}^{(j)},\tilde{X}_{i}^{(j)})=\tilde{Z}^{(j)}_{i}.$

Let $\hat{f}^{(j)}_{lk;\tau}$ be as in (12) and consider

$\tilde{f}^{(j)}_{lk;\tau}:=\frac{1}{n_{j}}\sum_{i=1}^{n_{j}}\left[\tilde{Y}_{i}^{(j)}\right]_{\tau}\psi_{lk}\left(\tilde{X}_{i}^{(j)}\right).$

By Plancharel’s theorem, the $L_{2}$-sensitivity of the statistic
$\boldsymbol{\hat{f}}^{(j)}_{L,\tau}$ is given by

$\displaystyle\left\|\boldsymbol{\hat{f}}^{(j)}_{L,\tau}(Z^{(j)})-\boldsymbol{\hat{f}}^{(j)}_{L,\tau}((\tilde{Z}^{(j)}))\right\|^{2}_{2}$
$\displaystyle=\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}(\hat{f}_{lk;\tau}^{(j)}-\tilde{f}_{lk;\tau}^{(j)})^{2}$
$\displaystyle=\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\left(\frac{1}{n_{j}}[Y_{i}^{(j)}]_{\tau}\psi_{lk}(X_{i}^{(j)})-\frac{1}{n_{j}}[\tilde{Y}_{i}^{(j)}]_{\tau}\psi_{lk}(\tilde{X}_{i}^{(j)})\right)^{2}.$

Using the bound $\|\psi_{lk}\|_{\infty}=2^{l/2}\|\psi\|_{\infty}$ for all
$k=0,\dots,2^{l}-1$, we have that

$\displaystyle\frac{1}{n_{j}}[Y_{i}^{(j)}]_{\tau}\psi_{lk}(X_{i}^{(j)})-\frac{1}{n_{j}}[\tilde{Y}_{i}^{(j)}]_{\tau}\psi_{lk}(\tilde{X}_{i}^{(j)})\leq\frac{\tau}{n_{j}}\|\psi\|_{\infty}2^{l/2+1}.$

Since the wavelet $\psi$ is compactly supported, there is a constant number of
basis functions $\psi_{lk}$ with overlapping support at each resolution level
$l$ (the constant depends on the support size of the chosen wavelet $\psi$).
Consequently, the latter can be further bounded

$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\left(\frac{\tau}{n_{j}}\|\psi\|_{\infty}2^{l/2+1}\right)^{2}\mathbbm{1}\left\\{\\{X_{i}^{(j)},\tilde{X}_{i}^{(j)}\\}\cap\mathrm{supp}(\psi_{lk})\neq\emptyset\right\\}$
$\displaystyle\leq\left(\frac{\tau}{n_{j}}\|\psi\|_{\infty}\right)^{2}c_{A}2^{L+3}.$

Representing the constants that depend on $\psi$ as a single constant, we have
shown that for some $c_{\psi}>0$ it holds that

$\left\|\boldsymbol{\hat{f}}^{(j)}_{L,\tau}(Z^{(j)})-\boldsymbol{\hat{f}}^{(j)}_{L,\tau}(\tilde{Z}^{(j)})\right\|_{2}\leq
c_{\psi}\frac{\tau\sqrt{2^{L}}}{n_{j}}.$

∎

####  B.1.2 Proof of Theorem 3.2

###### Proof.

Let us denote the vector
$\boldsymbol{f}_{L}:=\\{f_{lk}:\,k=1\dots,2^{l},\,l=1,\dots,L\\}$. We
decompose the expected $L_{2}$-error
${\mathbb{E}}_{f}\|\hat{f}_{L,\tau}-f\|_{2}^{2}$ as follows

$\displaystyle{\mathbb{E}}_{f}\left\|\hat{f}_{L,\tau}-f\right\|_{2}^{2}$
$\displaystyle={\mathbb{E}}_{f}\left\|\sum_{j=1}^{m}u_{j}\boldsymbol{T}^{(j)}_{L,\tau}-\boldsymbol{f}_{L}\right\|_{2}^{2}+\sum_{l>L}\sum_{k=0}^{2^{l}-1}f_{lk}^{2}$
$\displaystyle\leq
2{\mathbb{E}}\left\|\sum_{j=1}^{m}u_{j}\boldsymbol{\hat{f}}^{(j)}_{L,\tau}-\boldsymbol{f}_{L}\right\|_{2}^{2}+2{\mathbb{E}}\left\|\sum_{j=1}^{m}u_{j}\boldsymbol{W}^{(j)}\right\|_{2}^{2}+\sum_{l>L}\sum_{k=0}^{2^{l}-1}f_{lk}^{2}.$
(S.1)

The equality follows from the orthonormality of the basis functions, the
inequality from the triangle inequality in conjunction with the parabolic
inequality $2ab\leq a^{2}+b^{2}$. Lemma B.5 in Section B.1.3 yields the
following bound on the third term;

$\sum_{l>L}\sum_{k=0}^{2^{l}-1}f_{lk}^{2}\leq c_{\alpha}2^{-2L\alpha}R^{2},$
(S.2)

for a universal constant $c_{\alpha}>0$ depending only on $\alpha$. Next we
bound the error term due to the noise added for privacy purposes as follows,

${\mathbb{E}}_{f}\left\|\sum_{j=1}^{m}u_{j}\boldsymbol{W}^{(j)}\right\|_{2}^{2}\leq\frac{4c_{\psi}^{2}\tau^{2}2^{2L}\log(2/\delta^{\prime})}{\sum_{j}n^{2}_{j}\varepsilon^{2}_{j}\wedge
n_{j}2^{L}},$ (S.3)

which we prove in Lemma B.1 below.

Next, we consider the first term in (S.1), which by orthogonality of the
wavelet basis can be written as

$\displaystyle{\mathbb{E}}_{f}\left\|\sum_{j=1}^{m}u_{j}\boldsymbol{\hat{f}}^{(j)}_{L,\tau}-\boldsymbol{f}_{L}\right\|_{2}^{2}$
$\displaystyle={\mathbb{E}}\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\left(\sum_{j=1}^{m}u_{j}\hat{f}_{lk}^{(j)}-f_{lk}\right)^{2}$
$\displaystyle=\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left(\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}\left[Y^{(j)}_{i}\right]_{\tau}\psi_{lk}(X^{(j)}_{i})-f_{lk}\right)^{2}.$

We have that

$\left[Y^{(j)}_{i}\right]_{\tau}=\left[f(X^{(j)}_{i})+\xi_{i}^{(j)}\right]_{\tau}=\left[\xi_{i}^{(j)}\right]^{\tau-f(X^{(j)}_{i})}_{-\tau-f(X^{(j)}_{i})}+f(X^{(j)}_{i}).$

Writing
$\eta^{(j)}_{i}:=\left[\xi_{i}^{(j)}\right]^{\tau-f(X^{(j)}_{i})}_{-\tau-f(X^{(j)}_{i})}$,
we obtain

$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left(\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}\left[Y^{(j)}_{i}\right]_{\tau}\psi_{lk}(X^{(j)}_{i})-f_{lk}\right)^{2}$
$\displaystyle=$
$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left(\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}f(X_{i}^{(j)})\psi_{lk}(X^{(j)}_{i})+\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})-f_{lk}\right)^{2}$
$\displaystyle\leq$ $\displaystyle
2\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left(\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}f(X_{i}^{(j)})\psi_{lk}(X^{(j)}_{i})-f_{lk}\right)^{2}+$
$\displaystyle
2\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left(\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})\right)^{2}.$
(S.4)

We show in Lemma B.2 below that

$\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left(\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}f(X_{i}^{(j)})\psi_{lk}(X^{(j)}_{i})-f_{lk}\right)^{2}\leq
C_{R,\alpha}^{2}c_{3}2^{L}\sum_{j=1}^{m}\frac{u_{j}^{2}}{n_{j}}.$ (S.5)

The second term in (S.4) can be decomposed as follows

$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}$
$\displaystyle{\mathbb{E}}_{f}\left(\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})\right)^{2}=\overbrace{\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left[\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\frac{u^{2}_{j}}{n^{2}_{j}}\left(\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})\right)^{2}\right]}^{①}$
$\displaystyle+\underbrace{\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left[\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\sum_{(i^{\prime},j^{\prime})\neq(i,j)}\frac{u_{j}}{n_{j}}\frac{u_{j^{\prime}}}{n_{j^{\prime}}}\left(\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})\eta_{i^{\prime}}^{(j^{\prime})}\psi_{lk}(X^{(j^{\prime})}_{i^{\prime}})\right)\right]}_{②}.$

We show in Lemma B.3 and Lemma B.4 (Section B.1.3) respectively that

$①\leq c_{4}2^{L}\sum_{j=1}^{m}\frac{u_{j}^{2}}{n_{j}},$ (S.6)

and

$②\leq c_{5}R^{2}2^{-2\alpha L}$ (S.7)

for constants $c_{4},c_{5}>0$. Combining (S.5), (S.6) and (S.7) we have for
some constant $c_{6}>0$

${\mathbb{E}}\left\|\sum_{j=1}^{m}u_{j}\boldsymbol{\hat{f}}^{(j)}_{L,\tau}-\boldsymbol{f}_{L}\right\|_{2}^{2}\leq
c_{6}\left(2^{L}\sum_{j=1}^{m}\frac{u_{j}^{2}}{n_{j}}+2^{-2\alpha L}\right).$
(S.8)

Observe that the choice $u_{j}=\frac{v_{j}}{\sum_{j}v_{j}}$ with
$v_{j}=n_{j}^{2}\varepsilon_{j}^{2}\wedge n_{j}2^{L}$ and the above gives

$\sum_{j=1}^{m}\frac{u_{j}^{2}}{n_{j}}\leq\frac{1}{\sum_{j}n^{2}_{j}\varepsilon^{2}_{j}\wedge
n_{j}2^{L}}\sum_{j=1}^{m}u_{j}(n^{2}_{j}\varepsilon^{2}_{j}\wedge
n_{j}2^{L})\frac{1}{n_{j}}\leq\frac{2^{L}}{\sum_{j}n^{2}_{j}\varepsilon^{2}_{j}\wedge
n_{j}2^{L}}\lesssim 2^{(-2\alpha-1)L}.$

Next we combine (S.2), (S.3) and (S.8) with the above to obtain that

${\mathbb{E}}\left\|\hat{f}_{L,\tau}-f\right\|_{2}^{2}\leq
c_{\psi}^{\prime}\tau^{2}\log(2/\delta^{\prime})2^{-2L\alpha},$

for a constant $c_{\psi}^{\prime}>0$. The choice
$L=(l_{0}+1)\vee\lceil\log_{2}(D)\rceil$ where $D>0$ is the solution to (14)
gives

$2^{L(2\alpha+2)}\asymp\sum_{j=1}^{m}n_{j}^{2}\varepsilon_{j}^{2}\wedge
n_{j}2^{L}\leq N2^{L},$

which implies $L=O(\log N)$ and hence $\tau^{2}=O(\log N)$. ∎

####  B.1.3 Auxilliary Lemmas B.1, B.2, B.3, B.4, B.5 and B.6

######  Lemma B.1.

We have that

${\mathbb{E}}\left\|\sum_{j=1}^{m}u_{j}\boldsymbol{W}^{(j)}\right\|_{2}^{2}\leq\frac{2c_{\psi}^{2}\tau^{2}2^{2L}\log(2/\delta^{\prime})}{\sum_{j}n^{2}_{j}\varepsilon^{2}_{j}\wedge
n_{j}2^{L}},$

where $\boldsymbol{W}^{(j)}\sim
N\left(0,\frac{4\tau^{2}2^{L}c_{\psi}\log(2/\delta_{j})}{n_{j}^{2}\varepsilon_{j}^{2}}I_{2^{L}}\right)$,

$u_{j}=\frac{v_{j}}{\sum_{j}v_{j}}\;\text{ with
}\;v_{j}=n_{j}^{2}\varepsilon_{j}^{2}\wedge n_{j}2^{L}$

and $c^{\prime}_{\psi}>0$ a constant depending on the choice of wavelet basis,
$R$ and $\alpha>1/p$.

###### Proof.

Using the independence of the noise generating mechanisms across the servers
we have

$\displaystyle{\mathbb{E}}\left[\left\|\sum_{j=1}^{m}u_{j}W^{(j)}\right\|^{2}\right]$
$\displaystyle=\sum_{i=1}^{m}u^{2}_{j}{\mathbb{E}}\left[\left\|W^{(j)}\right\|_{2}^{2}\right]$
$\displaystyle=\sum_{j=1}^{m}u_{j}^{2}\frac{(c_{\psi})^{2}\tau^{2}\log(2/\delta_{j})}{n_{j}^{2}\varepsilon_{j}^{2}}2^{2L+2}.$

Using the fact that $v_{j}\leq n_{j}^{2}\varepsilon_{j}^{2}$ and
$\sum_{j}u_{j}=1$, the latter is bounded by from above by

$\displaystyle\frac{4c_{\psi}}{\sum_{j}n^{2}_{j}\varepsilon^{2}_{j}\wedge
n_{j}2^{L}}\sum_{j=1}^{m}u_{j}v_{j}\frac{\tau^{2}2^{2L}\log(2/\delta^{\prime})}{n_{j}^{2}\varepsilon_{j}^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{4c_{\psi}}{\sum_{j}n^{2}_{j}\varepsilon^{2}_{j}\wedge
n_{j}2^{L}}\sum_{j=1}^{m}u_{j}\tau^{2}2^{2L}\log(2/\delta^{\prime})$
$\displaystyle\leq$
$\displaystyle\frac{4c_{\psi}\tau^{2}2^{2L}\log(2/\delta^{\prime})}{\sum_{j}n^{2}_{j}\varepsilon^{2}_{j}\wedge
n_{j}2^{L}}.$

∎

######  Lemma B.2.

It holds that

$\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left(\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}f(X_{i}^{(j)})\psi_{lk}(X^{(j)}_{i})-f_{lk}\right)^{2}\leq
C_{R,\alpha}^{2}c_{3}2^{L}\sum_{j=1}^{m}\frac{u_{j}^{2}}{n_{j}},$

where $f_{lk}=\langle f,\psi_{lk}\rangle$ are the wavelet basis coefficents of
the function $f\in B^{\alpha}_{p,q}(R)$ and $u_{j}$ is as defined in (13).

###### Proof.

Using the independence of samples on a given server and using that
${\mathbb{E}}f(V)\psi_{lk}(V)=f_{lk}$ for $V\sim U[0,1]$, we have

$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left(\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}f(X_{i}^{(j)})\psi_{lk}(X^{(j)}_{i})-f_{lk}\right)^{2}$
$\displaystyle=$
$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\frac{u^{2}_{j}}{n^{2}_{j}}\mathrm{Var}\left(f(X_{i}^{(j)})\psi_{lk}(X^{(j)}_{i})\right)$
$\displaystyle\leq$
$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\frac{u^{2}_{j}}{n^{2}_{j}}{\mathbb{E}}_{f}\left(f(X_{i}^{(j)})\psi_{lk}(X^{(j)}_{i})\right)^{2}.$

By Lemma B.6, $\|f\|_{\infty}\leq C_{R,\alpha}$ for a universal constant
$C_{R,\alpha}>0$ depending on $R>0$ and $s>1/p$ only. Hence, each term in the
display above satisfies

$\displaystyle{\mathbb{E}}_{f}\left(f(X_{i}^{(j)})\psi_{lk}(X^{(j)}_{i})\right)^{2}\leq
C_{R,\alpha}^{2}{\mathbb{E}}_{f}\left(\psi_{lk}(X^{(j)}_{i})^{2}\right)=C_{R,\alpha}^{2}.$

We obtain that

$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}_{f}\left(\sum_{j=1}^{m}\frac{u_{j}}{n_{j}}\sum_{i=1}^{n_{j}}f(X_{i}^{(j)})\psi_{lk}(X^{(j)}_{i})-f_{lk}\right)^{2}$
$\displaystyle\leq\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\frac{u^{2}_{j}}{n^{2}_{j}}C_{R,\alpha}^{2}$
$\displaystyle\leq
2^{L+1}C_{R,\alpha}^{2}\sum_{j=1}^{m}\frac{u_{j}^{2}}{n_{j}}.$

∎

######  Lemma B.3.

It holds that

$\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}\left[\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\frac{u^{2}_{j}}{n^{2}_{j}}\left(\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})\right)^{2}\right]\leq
c_{4}2^{L}\sum_{j=1}^{m}\frac{u_{j}^{2}}{n_{j}},$

where
$\eta^{(j)}_{i}:=\left[\xi_{i}^{(j)}\right]^{\tau-f(X^{(j)}_{i})}_{-\tau-f(X^{(j)}_{i})}$
with $\tau=C_{\alpha,R}+\sqrt{(2\alpha+1)L}$ and $u_{j}$ is as defined in
(13).

###### Proof.

We first observe that since $\tau>C_{\alpha,R}>\|f\|_{\infty}$, Lemma B.7
yields that

$\displaystyle{\mathbb{E}}\left[(\eta_{i}^{(j)})^{2}\mid X^{(j)}_{i}\right]$
$\displaystyle={\mathbb{E}}\left[\left(\left[\xi_{i}^{(j)}\right]^{\tau-f(X^{(j)}_{i})}_{-\tau-f(X^{(j)}_{i})}\right)^{2}\mid
X^{(j)}_{i}\right]$
$\displaystyle\leq{\mathbb{E}}\left[(\xi_{i}^{(j)})^{2}\mid
X^{(j)}_{i}\right]=\sigma^{2},$

which in turn implies that

$\displaystyle{\mathbb{E}}\left[(\eta_{i}^{(j)})^{2}\psi^{2}_{lk}(X^{(j)}_{i})\right]$
$\displaystyle={\mathbb{E}}\left[\psi^{2}_{lk}(X^{(j)}_{i}){\mathbb{E}}\left[(\eta_{i}^{(j)})^{2}\mid
X_{i}^{(j)}\right]\right]$
$\displaystyle\leq\sigma^{2}{\mathbb{E}}\psi^{2}_{lk}(X^{(j)}_{i})=\sigma^{2}.$

Hence,

$\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}\left[\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\frac{u^{2}_{j}}{n^{2}_{j}}\left(\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})\right)^{2}\right]\leq\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\frac{u^{2}_{j}}{n^{2}_{j}}\sigma^{2}\leq
2^{L+1}\sum_{j=1}^{m}\frac{u_{j}^{2}}{n_{j}}.$

∎

######  Lemma B.4.

It holds that

$\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}\left[\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\sum_{(i^{\prime},j^{\prime})\neq(i,j)}\frac{u_{j}}{n_{j}}\frac{u_{j^{\prime}}}{n_{j^{\prime}}}\left(\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})\eta_{i^{\prime}}^{(j^{\prime})}\psi_{lk}(X^{(j^{\prime})}_{i^{\prime}})\right)\right]\leq
2R^{2}2^{-2\alpha L},$

where
$\eta^{(j)}_{i}:=\left[\xi_{i}^{(j)}\right]^{\tau-f(X^{(j)}_{i})}_{-\tau-f(X^{(j)}_{i})}$
with $\tau=C_{\alpha,R}+\sqrt{(2\alpha+1)L}$ and $u_{j}$ is as defined in
(13).

###### Proof.

Let $Z\sim N(0,1)$. Then, for $a>0$ and $\tau>a$,

$\displaystyle 0<{\mathbb{E}}\left[Z\right]^{\tau+a}_{-\tau+a}$
$\displaystyle\leq{\mathbb{E}}\left[Z\right]^{\tau-a}_{-\tau+a}+(2a){\mathbb{P}}(\tau-a\leq
Z\leq\tau+a)$ $\displaystyle\leq 4ae^{-\frac{1}{2}(\tau-a)^{2}}.$

Similarly, for $a<0$ and $\tau>a$ we obtain that
$0>{\mathbb{E}}\left[Z\right]^{\tau+a}_{-\tau+a}\geq
4ae^{-\frac{1}{2}(\tau+a)^{2}}$. Combining these two cases together we have
for $a\in{\mathbb{R}}$ and $\tau$ large that

$\left|{\mathbb{E}}\left[Z\right]^{\tau+a}_{-\tau+a}\right|\leq
4|a|e^{-\frac{1}{2}(\tau-|a|)^{2}}.$ (S.9)

Using the tower property consequently obtain

$\displaystyle\left|{\mathbb{E}}\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})\eta_{i^{\prime}}^{(j^{\prime})}\psi_{lk}(X^{(j^{\prime})}_{i^{\prime}})\right|$
$\displaystyle=\left|{\mathbb{E}}\left[\psi_{lk}(X^{(j)}_{i})\psi_{lk}(X^{(j^{\prime})}_{i^{\prime}}){\mathbb{E}}\left[\eta_{i}^{(j)}\eta_{i^{\prime}}^{(j^{\prime})}\mid
X^{(j)}_{i},X^{(j^{\prime})}_{i^{\prime}}\right]\right]\right|$
$\displaystyle\leq{\mathbb{E}}\left[\left|\psi_{lk}(X^{(j)}_{i})\psi_{lk}(X^{(j^{\prime})}_{i^{\prime}})\right|\left|{\mathbb{E}}\left[\eta_{i}^{(j)}\eta_{i^{\prime}}^{(j^{\prime})}\mid
X^{(j)}_{i},X^{(j^{\prime})}_{i^{\prime}}\right]\right|\right].$

Next we focus on the conditional expectation and bound it using (S.9) as
follows (observe that $(i,j)\neq(i^{\prime},j^{\prime})$)

$\displaystyle\left|{\mathbb{E}}\left[\eta_{i}^{(j)}\eta_{i^{\prime}}^{(j^{\prime})}\mid
X^{(j)}_{i},X^{(j^{\prime})}_{i^{\prime}}\right]\right|$
$\displaystyle\leq\left|{\mathbb{E}}\left[\eta_{i}^{(j)}\mid
X^{(j)}_{i}\right]\right|^{2}$
$\displaystyle\leq\left|{\mathbb{E}}\left[\left[\xi_{i}^{(j)}\right]^{\tau-f(X^{(j)}_{i})}_{-\tau-f(X^{(j)}_{i})}\mid
X^{(j)}_{i}\right]\right|^{2}$ $\displaystyle\leq
16|f(X^{(j)}_{i})|^{2}e^{-(\tau-|f(X^{(j)}_{i})|)^{2}}\leq 16R^{2}e^{-(\tau-
C_{\alpha,R})^{2}}.$

This implies that

$\displaystyle\left|{\mathbb{E}}\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})\eta_{i^{\prime}}^{(j^{\prime})}\psi_{lk}(X^{(j^{\prime})}_{i^{\prime}})\right|$
$\displaystyle\leq\left({\mathbb{E}}|\psi_{lk}(X^{(j)}_{i})|\right)^{2}16R^{2}e^{-(\tau-
C_{\alpha,R})^{2}}$ $\displaystyle\leq 16R^{2}e^{-(\tau-C_{\alpha,R})^{2}}.$

Plugging this inequality in (S.7) and using the prescribed choice of
$\tau=C_{\alpha,R}+\sqrt{(2\alpha+1)L}$ yields

$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}{\mathbb{E}}\left[\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\sum_{(i^{\prime},j^{\prime})\neq(i,j)}\frac{u_{j}}{n_{j}}\frac{u_{j^{\prime}}}{n_{j^{\prime}}}\left(\eta_{i}^{(j)}\psi_{lk}(X^{(j)}_{i})\eta_{i^{\prime}}^{(j^{\prime})}\psi_{lk}(X^{(j^{\prime})}_{i^{\prime}})\right)\right]$
$\displaystyle\leq$
$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\sum_{(i^{\prime},j^{\prime})\neq(i,j)}\frac{u_{j}}{n_{j}}\frac{u_{j^{\prime}}}{n_{j^{\prime}}}16R^{2}e^{-(\tau-
C_{\alpha,R})^{2}}$ $\displaystyle\leq$
$\displaystyle\sum_{l=l_{0}}^{L}\sum_{k=0}^{2^{l}-1}\left(\sum_{j=1}^{m}\sum_{i=1}^{n_{j}}\frac{u_{j}}{n_{j}}\right)^{2}16R^{2}e^{-(\tau-
C_{\alpha,R})^{2}}$ $\displaystyle\leq$ $\displaystyle
2R^{2}2^{L}2^{(-2\alpha-1)L}.$

∎

The following two lemmas are standard results, see e.g. Chapter 9 in [47].

######  Lemma B.5.

Let $f_{lk}$ are the wavelet coefficents of the function $f\in
B^{\alpha}_{p,q}(R)$. For any $1\leq q\leq\infty$, $2\leq p\leq\infty$, $L>0$,
we have

$\sum_{l>L}\sum_{k=0}^{2^{l}-1}f_{lk}^{2}\leq c_{\alpha}2^{-2L\alpha}R^{2},$

where $c_{\alpha}>0$ is a universal constant depending only on $\alpha$.

######  Lemma B.6.

There exists a constant $C_{\alpha,R}>0$ such that $\|f\|_{\infty}\leq
C_{\alpha,R}$ for all $f\in B^{\alpha}_{p,q}(R)$ with $\alpha-1/2-1/p>0$,
$1\leq q\leq\infty$ and $2\leq p\leq\infty$.

The last lemma of the section is a standard result too, which states that
clipping a random variable reduces its variance.

######  Lemma B.7.

For any $\tau>0$ and random variable $V$,

$\text{Var}\left(\left[V\right]_{\tau}\right)\leq\text{Var}\left(V\right).$

###### Proof.

Let $\mu={\mathbb{E}}V$. Since the expectation of a random variable is the
constant minimizing the $L_{2}$-distance to that random variable,

$\text{Var}\left(\left[V\right]_{\tau}\right)\leq{\mathbb{E}}\left(\left[V\right]_{\tau}-\mu\right)^{2}.$

The latter expectation can be written as

$\displaystyle{\mathbb{E}}\mathbbm{1}_{V\in[-\tau,\tau]}\left(V-\mu\right)^{2}+{\mathbb{E}}\mathbbm{1}_{V>\tau}\left(\tau-\mu\right)^{2}+{\mathbb{E}}\mathbbm{1}_{V<-\tau}\left(-\tau-\mu\right)^{2}.$

Assuming $\mu\geq 0$, $V<-\tau$ implies that $|-\tau-\mu|\leq|-V-\mu|$. Since
$\mu\leq\tau$, $V>\tau$ implies that $|\tau-\mu|\leq|V-\mu|$. Consequently,
the above display is bounded from above by

$\displaystyle{\mathbb{E}}\mathbbm{1}_{V\in[-\tau,\tau]}\left(V-\mu\right)^{2}+{\mathbb{E}}\mathbbm{1}_{V>\tau}\left(V-\mu\right)^{2}+{\mathbb{E}}\mathbbm{1}_{V<-\tau}\left(-V-\mu\right)^{2}={\mathbb{E}}\left(V-\mu\right)^{2}.$

The case where $\mu<0$ follows by the same reasoning. ∎

###  B.2 Lower Bound Proofs

####  B.2.1 Proof of Lemma 4.3

###### Proof.

Note that
${\mathbb{E}}_{f}\|\hat{f}-f\|_{2}^{2}\geq{\mathbb{E}}\left(\sum_{k=0}^{2^{L}-1}(\hat{f}_{Lk}-f_{Lk})^{2}\right)$.
Denote $f_{L}$ by the vector $\\{f_{Lk}:k=0,\dots,2^{L}-1\\}.$ For getting a
lower bound on the minimax risk we will use a multivariate version of the Van-
Trees inequality due to [39] (Theorem 1), which bounds the average $\ell^{2}$
risk by

$\int_{f_{L}}{\mathbb{E}}\left(\sum_{k=0}^{2^{L}-1}(\hat{f}_{Lk}-f_{Lk})^{2}\right)\lambda(f_{L})df_{L}\geq\frac{(2^{L})^{2}}{\int\mathrm{Tr}(I_{T^{(1)},\ldots,T^{(m)}}(f_{L}))\pi(f_{L})df_{L}+J(\pi)},$

where $I_{T^{(1)},\ldots,T^{(m)}}(f_{L})$ is the Fisher information
asscociated with $\boldsymbol{T}=\left(T^{(1)},\ldots,T^{(m)}\right)$ and
$\pi(f_{L})=\prod_{k=0}^{2^{L}-1}\pi_{k}(f_{Lk})$ is a prior for the parameter
$f_{L}$ and $J(\pi)$ is the Fisher information associated with the prior
$\pi$:

$J(\pi)=\sum_{k=0}^{2^{L}-1}\int\frac{\pi^{\prime}_{k}(f_{Lk})^{2}}{\pi_{k}(f_{Lk})}df_{Lk}.$

By taking as prior $\pi_{k}$ a rescaled version of the density
$t\mapsto\cos^{2}(\pi t/2)\mathbbm{1}\\{|t|\leq 1\\}$ such that it is
supported on $[-2^{-L(\alpha+1/2)}R,2^{-L(\alpha+1/2)}R]$, we obtain that
prior is supported on ${\mathcal{B}}^{\alpha,R}_{p,q}$. By a straightforward
calculation for the Fisher information associated with the prior, we have that
the minimax risk is lower bounded by

$\sup_{f\in{\mathcal{B}}^{\alpha,R}_{p,q}}{\mathbb{E}}_{f}\|\hat{f}-f\|_{2}^{2}\geq\frac{(2^{L})^{2}}{\sup_{f_{L}}\mathrm{Tr}(I_{T^{(1)},\ldots,T^{(m)}}(f_{L}))+\frac{2^{L}\pi^{2}}{(2^{-L(\alpha+1/2)}R)^{2}}}.$

Next using the fact that $T^{(1)},\dots,T^{(m)}$ are independent trancripts we
have that
$I_{T^{(1)},\ldots,T^{(m)}}(f_{L})=\sum_{j=1}^{m}I_{T^{(j)}}(f_{L})$. It is a
straighforward calculation to show that
$I_{T^{(j)}}(f_{L})={\mathbb{E}}[\boldsymbol{C}_{f}(T^{(j)})]$ which proves
the lemma. ∎

####  B.2.2 Proof of Lemma 4.2

###### Proof.

For random variables $V,W$, it holds that

${\mathbb{E}}W{\mathbb{E}}[W|V]={\mathbb{E}}{\mathbb{E}}[W|V]{\mathbb{E}}[W|V],$

since $W-{\mathbb{E}}[W|V]$ is orthogonal to ${\mathbb{E}}[W|V]$. Using this
fact and linearity of the inner product and conditional expectation,

${\mathbb{E}}\left[\text{Tr}(C_{f}(T^{(j)}))\right]={\mathbb{E}}\|{\mathbb{E}}[S_{f}(Z^{(j)})\mid
T^{(j)}]\|_{2}^{2}=\underset{i=1}{\overset{n_{j}}{\sum}}{\mathbb{E}}G^{(j)}_{i}.$
(S.10)

Define also

$\breve{G}^{(j)}_{i}=\langle{\mathbb{E}}[S_{f}(Z^{(j)})|T^{(j)}],S_{f}(\breve{Z}^{(j)}_{i})\rangle,$

where $\breve{Z}_{i}^{(j)}$ is and independent copy of ${Z}_{i}^{(j)}$ and
note that ${\mathbb{E}}\breve{G}^{(j)}_{i}=0$. Write $(G_{i}^{(j)})^{+}:=0\vee
G^{(j)}_{i}$ and $(G_{i}^{(j)})^{-}=-0\wedge G^{(j)}_{i}$. We have that
${\mathbb{E}}(G^{(j)}_{i})^{+}$ equals

$\displaystyle\int_{0}^{\infty}{\mathbb{P}}\left((G_{i}^{(j)})^{+}\geq
t\right)dt=\int_{0}^{M}{\mathbb{P}}\left((G_{i}^{(j)})^{+}\geq
t\right)+\int_{M}^{\infty}{\mathbb{P}}\left((G_{i}^{(j)})^{+}\geq t\right)$
$\displaystyle\leq$ $\displaystyle
e^{\epsilon}\int_{0}^{M}{\mathbb{P}}\left((\breve{G}_{i}^{(j)})^{+}\geq
t\right)dt+M\delta+\int_{M}^{\infty}{\mathbb{P}}\left((G_{i}^{(j)})^{+}\geq
t\right)$ $\displaystyle\leq$
$\displaystyle\int_{0}^{\infty}{\mathbb{P}}\left((\breve{G}_{i}^{(j)})^{+}\geq
t\right)dt+C^{\prime}\epsilon\int_{0}^{\infty}{\mathbb{P}}\left((\breve{G}_{i}^{(j)})^{+}\geq
t\right)dt+M\delta+\int_{M}^{\infty}{\mathbb{P}}\left((G_{i}^{(j)})^{+}\geq
t\right),$

where in the last inequality the constant $C^{\prime}$ depends only on
$C_{\varepsilon}$. In the same way, we obtain that
${\mathbb{E}}(G_{i}^{(j)})^{-}$ is lower bounded by

$\displaystyle
e^{-\epsilon}\int_{0}^{M}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{-}\geq
t\right)dt-M\delta+\int_{M}^{\infty}{\mathbb{P}}\left((G_{i}^{(j)})^{-}\geq
t\right)$ $\displaystyle\geq$
$\displaystyle\int_{0}^{M}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{-}\geq
t\right)dt-C^{\prime}\epsilon\int_{0}^{\infty}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{-}\geq
t\right)dt-M\delta+\int_{M}^{\infty}{\mathbb{P}}\left((G_{i}^{(j)})^{-}\geq
t\right)dt$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{-}\geq
t\right)dt-C^{\prime}\epsilon\int_{0}^{\infty}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{-}\geq
t\right)dt-M\delta-\int_{M}^{\infty}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{-}\geq
t\right)dt.$

Putting these together with $G_{i}=(G_{i}^{(j)})^{+}-(G_{i}^{(j)})^{-}$, we
get

$\displaystyle{\mathbb{E}}G^{(j)}_{i}$
$\displaystyle\leq\int_{0}^{\infty}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{+}\geq
t\right)dt+\int_{0}^{\infty}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{-}\geq
t\right)dt+2C^{\prime}\epsilon\int_{0}^{\infty}{\mathbb{P}}\left(|\breve{G}^{(j)}_{i}|\geq
t\right)dt$
$\displaystyle+2M\delta+\int_{M}^{\infty}{\mathbb{P}}\left((G_{i}^{(j)})^{+}\geq
t\right)dt-\int_{M}^{\infty}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{-}\geq
t\right)dt$
$\displaystyle={\mathbb{E}}\breve{G}^{(j)}_{i}+2C^{\prime}\varepsilon_{j}{\mathbb{E}}|\breve{G}^{(j)}_{i}|+2M\delta_{j}+\int_{M}^{\infty}{\mathbb{P}}\left((G^{(j)}_{i})^{+}\geq
t\right)dt+\int_{M}^{\infty}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{-}\geq
t\right)dt.$

The first term in the last display equals zero. For the second term, observe
that

$\displaystyle{\mathbb{E}}|\breve{G}^{(j)}_{i}|$
$\displaystyle\leq\sqrt{{\mathbb{E}}\left[{\mathbb{E}}\langle{\mathbb{E}}(S_{f}(Z^{(j)}_{i})|T^{(j)}),S_{f}(\breve{Z}^{(j)}_{i})\rangle^{2}\right]}$
$\displaystyle\leq\sqrt{{\mathbb{E}}\left[{\mathbb{E}}(S_{f}(Z^{(j)}_{i})|T^{(j)})^{T}\mathrm{Var}(S_{f}(\breve{Z}^{(j)}_{i})){\mathbb{E}}(S_{f}(Z^{(j)}_{i})|T^{(j)})\right]}$
$\displaystyle\leq\sqrt{{\mathbb{E}}\|{\mathbb{E}}(S_{f}(Z^{(j)}_{i})|T^{(j)})\|_{2}^{2}}\sqrt{\lambda_{\max}(\boldsymbol{C}_{f})}$
$\displaystyle\leq\sqrt{{\mathbb{E}}\mathrm{Tr}(\boldsymbol{C}_{f}(T^{(j)}))}\sqrt{\lambda_{\max}(\boldsymbol{C}_{f})}.$

A concentration argument bounding the tails of $(G^{(j)}_{i})^{+}$ and
$\breve{G}^{(j)}_{i}$, i.e. Lemma B.9 with
$M=(2^{L}\sqrt{n_{j}})\log(1/\delta_{j})$, in combination with the identity
(S.10), yields the desired result. ∎

####  B.2.3 Proof of Theorem 4.1

###### Proof.

The crux of the lower bound argument involves showing that

$\mathbb{E}\left[\mathrm{Tr}(\boldsymbol{C}_{f}(T^{(j)}))\right]\lesssim
n_{j}^{2}\varepsilon_{j}^{2},$ (S.11)

which we prove in Lemma B.8 in Section B.2.4.

It is easy to observe that $\boldsymbol{C}^{(j)}_{f,i}=I_{2^{L}}$, i.e. a
$2^{L}\times 2^{L}$ identity matrix. Using the properties of the conditional
expectations we have that for random vector $U$ and $V$

$\mathrm{Cov}\left[{\mathbb{E}}(U|V)\right]\preceq\mathrm{Cov}(U)$

where $\preceq$ denotes the positive definite inequality. This implies that
${\mathbb{E}}\boldsymbol{C}_{f}(T^{(j)})\preceq\boldsymbol{C}^{(j)}_{f}$ using
the fact that ${\mathbb{E}}\boldsymbol{S}_{f}(Z^{(j)})=0$. Hence we have that
$\mathrm{Tr}\left[\mathbb{E}(\boldsymbol{C}_{f}(T^{(j)}))\right]\leq\mathrm{Tr}(\boldsymbol{C}^{(j)}_{f})=n_{j}2^{L}$.

Combining these two upper bounds on the expected trace of
$\boldsymbol{C}_{f}(T^{(j)})$, we have, by Lemma 4.3, that

$\sup_{f\in\mathcal{B}^{\alpha,R}_{p,q}}\mathbb{E}_{f}\|\hat{f}-f\|_{2}^{2}\gtrsim\frac{2^{2L}}{\sum_{j=1}^{m}n_{j}^{2}\varepsilon^{2}\wedge
n_{j}2^{L}+\pi^{2}2^{L(2\alpha+2)}}$

Now employing our choice of $L$ we have the desired minimax lower bound. ∎

####  B.2.4 Lemmas B.8 and B.9

######  Lemma B.8.

Let
$\boldsymbol{C}_{f}(T^{(j)})=\mathbb{E}\left[\boldsymbol{S}_{f}(Z^{(j)})\mid
T^{(j)}\right]\mathbb{E}\left[\boldsymbol{S}_{f}(Z^{(j)})\mid
T^{(j)}\right]^{T}$ and $\boldsymbol{S}_{f}(Z^{(j)})$ is defined as in (19).
Assuming $\delta_{j}$ is such that $\delta_{j}\log(1/\delta_{j})\lesssim
n_{j}^{1/2}\varepsilon_{j}^{2}2^{-L}$, it holds that

$\mathbb{E}\left[\mathrm{Tr}(\boldsymbol{C}_{f}(T^{(j)}))\right]\lesssim
n_{j}^{2}\varepsilon_{j}^{2}.$

###### Proof.

We wish to employ Lemma 4.2 for the proof. Using Lemma B.9, we have that

$\displaystyle\underset{i=1}{\overset{n}{\sum}}{\mathbb{E}}G^{(j)}_{i}$
$\displaystyle\lesssim
2n_{j}\varepsilon_{j}\sqrt{\text{Tr}({\mathbb{E}}(\boldsymbol{C}_{f}(T^{(j)})))}+\delta_{j}(2^{L}n_{j}^{1/2})\log(1/\delta_{j})+n_{j}\delta_{j}.$

If $\sqrt{\text{Tr}({\mathbb{E}}(\boldsymbol{C}_{f}(T^{(j)})))}\leq
n_{j}\varepsilon_{j}$, then (S.11) holds (there is nothing to prove). So
assume instead that
$\sqrt{\text{Tr}({\mathbb{E}}(\boldsymbol{C}_{f}(T^{(j)})))}\geq
n_{j}\varepsilon_{j}$. Combining the above display with (S.10), we get

$\displaystyle\sqrt{\text{Tr}({\mathbb{E}}(\boldsymbol{C}_{f}(T^{(j)})))}$
$\displaystyle\lesssim{2n_{j}\varepsilon_{j}}+\delta_{j}\frac{2^{L}n_{j}^{1/2}}{n_{j}\varepsilon_{j}}\log(1/\delta_{j})+\frac{1}{\varepsilon_{j}}\delta_{j}.$

The assumption of small enough $\delta_{j}$
($\delta_{j}\log(1/\delta_{j})\lesssim n_{j}^{1/2}\varepsilon_{j}^{2}2^{-L}$)
implies that the last two terms are $o(n_{j}\varepsilon_{j})$ which yields the
result. ∎

######  Lemma B.9.

For $M\asymp(2^{L}\sqrt{n_{j}})\log(1/\delta_{j})$ we have that

$2M\delta_{j}+\int_{M}^{\infty}{\mathbb{P}}\left((G^{(j)}_{i})^{+}\geq
t\right)dt+\int_{M}^{\infty}{\mathbb{P}}\left((\breve{G}^{(j)}_{i})^{-}\geq
t\right)dt\lesssim\delta_{j}2^{L}\sqrt{n_{j}}\log(1/\delta_{j})+\delta_{j}.$

where $(G^{(j)}_{i})^{+}$ and $(\breve{G}^{(j)}_{i})^{-}$ is as defined in the
proof of Lemma 4.2 proved in Section B.2.2.

###### Proof.

We first analyze the term concerning
$G^{(j)}_{i}=\langle\mathbb{E}[\boldsymbol{S}_{f}(Z^{(j)})|T^{(j)}],\boldsymbol{S}_{f}(Z_{i}^{(j)})\rangle$.
Using Jensen’s and law of total probability we have that for $i=1,\dots,n$,

$\displaystyle{\mathbb{E}}e^{t|G^{(j)}_{i}|}$
$\displaystyle={\mathbb{E}}e^{t|\langle\mathbb{E}[\boldsymbol{S}_{f}(Z^{(j)})|T^{(j)}],\boldsymbol{S}_{f}(Z_{i}^{(j)})\rangle|}$
$\displaystyle=\int\int
e^{t|\langle\mathbb{E}[\boldsymbol{S}_{f}(Z^{(j)})|T^{(j)}=u],\boldsymbol{S}_{f}(Z_{i}^{(j)})\rangle|}dP^{T^{(j)}|Z_{i}^{(j)}=z}(u)dP^{Z^{(j)}_{i}}(z)$