ADAPTIVE DISTRIBUTED METHODS UNDER
COMMUNICATION CONSTRAINTS
By Botond Szabó∗,† , and Harry van Zanten∗
Leiden University and University of Amsterdam

arXiv:1804.00864v1 [math.ST] 3 Apr 2018

We study distributed estimation methods under communication
constraints in a distributed version of the nonparametric signal-inwhite-noise model. We derive minimax lower bounds and exhibit
methods that attain those bounds. Moreover, we show that adaptive estimation is possible in this setting.

1. Introduction. In this paper we take up the study of the fundamental possibilities and limitations of distributed methods for high-dimensional, or nonparametric problems. The design and study of such methods has attracted substantial
attention recently. This is for a large part motivated by the ever increasing size of
datasets, leading to the necessity to analyze data while distributed over multiple
machines and/or cores. Other reasons to consider distributed methods include privacy considerations or the simple fact that in some situations data are physically
collected at multiple locations.
By now a variety of methods are available for estimating nonparametric or highdimensional models to data in a distributed manner. A (certainly incomplete) list
of recent references includes the papers [12, 18, 11, 4, 13, 14, 8]. The number of
more theoretical papers on the fundamental performance of such methods is still
rather limited however. In the paper [15] we recently introduced a distributed version of the canonical signal-in-white-noise model to serve as a benchmark model to
study aspects like convergences rates and optimal tuning of distributed methods.
We used it to compare the performance of a number of distributed nonparametric
methods recently introduced in the literature. The study illustrated the perhaps
intuitively obvious fact that in order to achieve an optimal bias-variance trade-off,
or, equivalently, to find the correct balance between over- and under-fitting, distributed methods need to be tuned differently than methods that handle all data
at once. Moreover, our comparison showed that some of the proposed methods are
more successful at this than others.
A major challenge and fundamental question for nonparametric distributed methods is whether or not it is possible to achieve a form of adaptive inference. In other
words, whether we can design methods that do automatic, data-driven tuning in order to achieve the optimal bias-variance trade-off. We illustrated by example in [15]
that naively using methods that are known to achieve optimal adaptation in nondistributed settings, can easily lead to sub-optimal performance in the distributed
case. In the recent paper [19], which considers the same distributed signal-in-whitenoise model and was written independently and at the same time as the present
paper, it is in fact conjectured that adaptation in this model is not possible.
In order to study convergence rates and adaptation for distributed methods in a
meaningful way the class of methods should be restricted somehow. Indeed, if there is
∗

Research supported by the Netherlands Organization of Scientific Research NWO.
The research leading to these results has received funding from the European Research Council
under ERC Grant Agreement 320637.
†

1

2

SZABÓ AND VAN ZANTEN

no limitation on communication or computation, then we could simply communicate
all data from the various local machines to a central machine, aggregate it, and
use some existing adaptive, rate-optimal procedure. In this paper we consider a
setting in which the communication between the local and the global machines is
restricted, much in the same way as the communication restrictions imposed in [18]
in a parametric framework and recently in the simultaneously written paper [19] in
the context of the distributed signal-in-white-noise model we introduced in [15].
In this distributed model with communication constraints we can derive minimax
lower bounds for the best possible rate that any distributed procedure can achieve
under smoothness conditions on the true signal. Technically this essentially relies on
an extension of the information theoretic approach of [18] to the infinite-dimensional
setting (this is different from the approach taken in [19], which relies on results from
[17]). It turns out there are different regimes, depending on how much communication
is allowed. On the one extreme end, and in accordance with intuition perhaps, if there
is enough communication allowed, it is possible to achieve the same convergence rates
in the distributed setting as in the non-distributed case. The other extreme case is
that there is so little communication allowed that combining different machines does
not help. Then the optimal rate under the communication restriction can already
be obtained by just using a single local machine and discarding the others. The
interesting case is the intermediate regime. For that case we show there exists an
optimal strategy that involves grouping the machines in a certain way and letting
them work on different parts of the signal.
These first results on rate-optimal distributed estimators are not adaptive, in the
sense that the optimal procedures depend on the regularity of the unknown signal.
The same holds true for the procedure obtained in parallel in [19]. In this paper
we go a step further and show that contrary perhaps to intuition, and contrary
to the conjecture in [19], adaptation is in fact possible. Indeed, we exhibit in this
paper an adaptive distributed method which involves a very specific grouping of the
local machines, in combination with a Lepski-type method that is carried out in the
central machine. We prove that the resulting distributed estimator adapts to a range
of smoothness levels of the unknown signal and that, up to logarithmic factors, it
attains the minimax lower bound.
Although our analysis is theoretical, we believe it contains interesting messages
that are ultimately very relevant for the development of applied distributed methods
in high-dimensional settings. First of all, we show that depending on the communication budget, it might be advantageous to group local machines and let different
groups work on different aspects of the high-dimensional object of interest. Secondly, we show that it is possible to have adaptation in communication restricted
distributed settings, i.e. to have data-driven tuning that automatically achieves the
correct bias-variance trade-off. We note however that although our proof of this fact
is constructive, the method we exhibit appears to be still rather unpractical. We view
our adaptation result primarily as a first proof of concept, that hopefully invites the
development of more practical adaptation techniques for distributed settings.
1.1. Notations. For two positive sequences an , bn we use the notation an . bn if
there exists an universal positive constant C such that an ≤ Cbn . Along the lines
an  bn denotes that an . bn and bn . an hold simultaneously. Furthermore we
write an  bn if an /bn = o(1). In the proofs we use the notation C and c for universal
constants which value can differ from line to line. Let us denote by dae andP
bac the
upper and lower integer value of the real number a, respectively. The sum bi=a xj

ADAPTIVE DISTRIBUTED ESTIMATION

3

P
for a, b positive real number denotes the sum i∈N:a≤i≤b xj . For a set A let #(A) or
|A| denote
R 1 the size of the set. For f ∈ L2 [0, 1] we denote the standard L2 -norm as
kf k22 = 0 f (x)2 dx, while for bounded functions kf k∞ denotes the L∞ -norm.
The function sign : R 7→ {0, 1} evaluates to 1 on (−∞, 0) and 0 on [0, ∞).
Furthermore, we use the notation mean{a1 , . . . , an } = (a1 + . . . + an )/n.
2. Main results. As in [15] we work with the distributed version of the signalin-white-noise model which, we regard as the natural ‘benchmark model’ in this case,
playing the same role as the usual signal-in-white-noise model in the non-distributed
case (e.g. [16, 7, 10]). We assume that we have m ‘local’ machines and in the ith
(i)
machine we observe the random function (Xt : t ∈ [0, 1]) satisfying the stochastic
differential equation
r
m
(i)
(i)
dXt = f0 (t) +
(2.1)
dWt , t ∈ [0, 1],
n
where W (1) , . . . , W (m) are independent Wiener processes and f0 ∈ L2 [0, 1] (which
is the same for all machines) is the unknown functional parameter of interest. For
our theoretical results we will assume that the unknown true function f0 belongs
to some regularity class. We work in our analysis with Besov smoothness classes,
more specifically we assume that for some degree of smoothness s > 0 we have f0 ∈
s (L) or f ∈ B s
B2,∞
0
∞,∞ (L). The first class is of Sobolev type, while the second one is
of Hölder type. For precise definitions, see Appendix B. Each local machine carries
out (parallel to the others) a local statistical procedure and transmits the results
to a central machine, which produces an estimator for the signal f0 by somehow
aggregating the messages received from the local machines.
We study these distributed procedures under communication constraints between
the local machines and the central machine. We allow each local machine to send
at most B (i) bits on average to the central machine. More formally, a distributed
estimator fˆ is a measurable function of m binary strings, or messages, passed down
from the local machines to the central machine. We denote by Y (i) the finite binary
string transmitted from machine i to the central machine, which is a measurable
function of the local data X (i) . For a class of potential signals F ⊂ L2 [0, 1], we
restrict the communication between the machines by assuming that for numbers
B (1) , . . . , B (m) , it holds that Ef0 [l(Y (i) )] ≤ B (i) for every f0 ∈ F and i = 1, . . . , m,
where l(Y ) denotes the length of the string Y . We denote the resulting class of
communication restricted distributed estimators fˆ by Fdist (B (1) , . . . , B (m) ; F). The
number of machines m and the communication constraints B (i) are allowed to depend
on the overall signal-to-noise ratio n, in fact that is the interesting situation. To
alleviate the notational burden somewhat we do not make this explicit in the notation
however.
2.1. Distributed minimax lower bounds for the L2 -risk. The first theorem we
present gives a minimax lower bound for distributed procedures for the L2 -risk,
uniformly over Sobolev-type Besov balls, see Appendix B for rigorous definitions.
Theorem 2.1. Consider s, L > 0 and communication constraints B (1) , . . . , B (m) >
0. Let the sequence δn = o(1) be defined as the solution to the equation
n m
o
m
δn = min
(2.2)
,
.
1
n log2 n Pm
n i=1 [log2 (n)δn1+2s B (i) ∧ 1]

4

SZABÓ AND VAN ZANTEN

Then in distributed signal-in-white-noise model (2.1) we have that
2s

inf

sup

s
s
fˆ∈Fdist (B (1) ,...,B (m) ;B2,∞
(L)) f0 ∈B2,∞
(L)

Ef0 kfˆ − f0 k22 & δn1+2s .

Proof. See Section 3.1
We briefly comment on the derived result. First of all note that the quantity δn
in (2.2) is well defined, since the left-hand side of the equation is increasing, while
the right-hand side is decreasing in δn . The proof of the theorem is based on an
application of a version of Fano’s inequality, frequently used to derive minimax lower
bounds. More specifically, as a first step we find as usual a large enough finite subset
s (L) over which the minimax rate is the same as over the
of the functional space B2,∞
whole space. This is done by finding the ‘effective resolution level’ jn in the wavelet
representation of the function of interest and perturbing the corresponding wavelet
coefficients, while setting the rest of the coefficients to zero. This effective resolution
level for s-smooth functions is usually (1 + 2s)−1 log2 n in case of the L2 -norm for
non-distributed models (e.g. [7]). However, in our distributed setting the effective
resolution level changes to (1 + 2s)−1 log δn−1 , which can be substantially different
from the non-distributed case, as it strongly depends on the number of transmitted
bits. The dependence on the expected number of transmitted bits enters the formula
by using a variation of Shannon’s source coding theorem. Many of the information
theoretic manipulations in the proof are an extended and adapted version of the
approach introduced in [18] in context of distributed methods with communication
constraints over parametric models.
To understand the result it is illustrative to consider the special case that the
communication constraints are the same for all machines, i.e. B (1) = · · · = B (m) =
B for some B > 0. We can then distinguish three regimes: (i) the case B ≥
n1/(1+2s) / log2 n; (ii) the case (n log2 (n)/m2+2s )1/(1+2s) ≤ B < n1/(1+2s) / log2 n;
and (iii) the case B < (n log2 (n)/m2+2s )1/(1+2s) .
In regime (i) we have a large communication budget and by elementary computations we get that the minimum in (2.2) is taken in the second fraction and hence that
δn = 1/n. This means that in this case the derived lower bound corresponds to the
usual non-distributed minimax rate n−2s/(1+2s) . In the other extreme case, regime
(iii), the minimum is taken at the first term in (2.2) and δn = m/(n log2 n), so the
lower bound is of the order (n log2 (n)/m)−2s/(1+2s) . This rate is, up to the log2 n factor, equal to the minimax rate corresponding to the noise level n/m. Consequently, in
this case it does not make sense to consider distributed methods, since by just using a
single machine the best rate can already obtained (up to a logarithmic factor). In the
intermediate case (ii) it is straightforward to see that δn = (nB log2 n)(1+2s)/(2+2s) .
It follows that if B = o(n1/(1+2s) / log2 n), i.e. if we are only allowed to communicate ‘strictly’ less than in case (i), then the lower bound is strictly worse than the
minimax rate corresponding to the non-distributed setting.
The findings above are summarized in the following corollary.
Corollary 2.2.

Consider s, L > 0 and a communication constraint B > 0.

(i) If B ≥ n1/(1+2s) / log2 n, then
inf

sup

s
s
fˆ∈Fdist (B,...,B;B2,∞
(L)) f0 ∈B2,∞
(L)

2s

Ef0 kfˆ − f0 k22 & n− 1+2s .

5

ADAPTIVE DISTRIBUTED ESTIMATION

(ii) If (n log2 (n)/m2+2s )1/(1+2s) ≤ B < n1/(1+2s) / log2 n, then
sup

inf

s
s
(L)) f0 ∈B2,∞
fˆ∈Fdist (B,...,B;B2,∞
(L)

Ef0 kfˆ − f0 k22 &

 n1/(1+2s) 
B log2 n

2s
2+2s

2s

n− 1+2s .

(iii) If (n log2 (n)/m2+2s )1/(1+2s) > B
inf

s
fˆ∈Fdist (B,...,B;B2,∞
(L))

 n log n − 2s
1+2s
2
Ef0 kfˆ − f0 k22 &
.
s
m
f0 ∈B2,∞ (L)
sup

2.2. Non-adaptive rate-optimal distributed procedures for L2 -risk. Next we show
that the derived lower bounds are sharp by exhibiting distributed procedures that
attain the bounds (up to logarithmic factors). We note that it is sufficient to consider
only the case B ≥ (n log2 (n)/m2+2s )1/(1+2s) , since otherwise distributed techniques
do not perform better than standard techniques carried out on one of the local
servers.
The estimators we provide start by a standard expansion of the observed sample
paths on every machine in an appropriate wavelet basis (cf. e.g. [7]). In L2 [0, 1] we
consider Daubechies wavelets ϕj,k , j ∈ N, k ∈ Kj , of regularity smax > s. Here Kj is
the set of wavelet basis function at resolution level j and note that |Kj | = 2j . (For
details, see Appendix B.) Then, slightly abusing notation, for every machine i we
define the observed noisy wavelet coefficients by
Z 1
(i)
(i)
ϕjk (t)dXt .
Xjk =
0

Note that it follows from (2.1) that for all j ∈ N and k ∈ Kj we have
r
m (i)
(i)
Xjk = f0,jk +
(2.3)
Z ,
n jk
R1
where f0,jk = 0 f0 (t)ϕjk (t)dt are the wavelet coefficients of the true signal f0 and
(i)

the Zjk are independent standard normal variables.
Next, we repeatedly use a particular method to transmit a finite-bit approximation
of a real number from a local machine to the central machine. To explain how it
works, take an arbitrary number x ∈ R not equal to zero and consider its binary
scientific representation
x = (−1)sign(x) ∗ 0.1 . . . ∗ 21+blog2 |x|c .
Note that the sign of x can be encoded by one bit, the sign of the exponent again
by one bit and the absolute value of the exponent by 1 + blog2 (1 ∨ |1 + blog2 |x|c|)c
bits, since it is a nonnegative integer. Then we construct our approximation y of x
by taking the first d0.5 log2 ne bits after the dot in the scientific representation of x
and multiplying it by (−1)sign(x) ∗ 21+blog2 |x|c . Note that x = 0 can be transmitted
by a single bit. Abusing our notation slightly, we use the notation y both for the real
number approximating x and for the binary string encoding it. The length of the
string is denoted by l(y). We summarize the approximation scheme in Algorithm 1
(with D = 1/2).
Observe that the length of the constructed approximation y of the number x
(viewed as a binary string) is bounded from above by 3 + log2 (1 ∨ |1 + blog2 |x|c|) +

6

SZABÓ AND VAN ZANTEN

Algorithm 1 Transmitting a finite-bit approximation of a number
1: procedure TransApprox(x)
2:
For x = 0 transmit 0.
3:
Else write x = (−1)sign(x) ∗ 0.1... ∗ 21+blog2 |x|c .
4:
Transmit: sign(x), sign(1 + blog2 |x|c), |1 + blog2 |x|c|.
5:
Transmit: ỹ= first dD log2 ne digits of x.
sign(1+blog2 |x|c)
∗(1+blog2 |x|c)
6:
Construct: y = (−1)sign(x) ∗ 0.ỹ ∗ 2(−1)
.

0.5 log2 n bits. The following lemma asserts that if X is a normally distributed
random variable with bounded mean and variance m/n, then the expected length
E[l(Y )] of the constructed binary string approximating X is less than log2 n (for
sufficiently large n) and the approximation is sufficiently close to X.
Lemma 2.3. Assume that X ∼ N (µ, m/n), with |µ| ≤ L. Then the approximation Y of X given in Algorithm 1 satisfies that
0 ≤ (X − Y )/X ≤ n−D

and

E[l(Y )] ≤ (D + o(1)) log2 (n).

Furthermore we also have that

P l(Y ) ≤ D log2 n + 3 + log2 log2 n ≥ 1 − cn−3/2 ,
for some large enough constant c > 0.
Proof. See Section 3.4.
After these preparations we can exhibit procedures attaining (nearly) the theoretical limits obtained in Corollary 2.2.
We first consider the case (i) that B ≥ n1/(1+2s) / log2 n. In this case each local
(i)
machine i = 1, . . . , m transmits the approximations Yjk (given in Algorithm 1) of
(i)

the first n1/(1+2s) ∧ (B/ log2 n) observed coefficients Xjk , i.e. for all indices j ∈ N
and k ∈ Kj such that 2j + k ≤ n1/(1+2s) ∧ (B/ log2 n). Then in the central machine
we simply average the transmitted approximations to obtain the estimated wavelet
coefficients
( P
(i)
m
1
Y , if 2j + k ≤ n1/(1+2s) ∧ (B/ log2 n),
fˆjk = m i=1 jk
0,
else.
The finalPestimator fˆ for f0 is the function in L2 [0, 1] with these wavelet coefficients,
i.e. fˆ =
fˆjk ϕjk . The method is summarized as Algorithm 2 below.
Algorithm 2 Nonadaptive L2 -method, case (i)
1: In the local machines:
2: for i = 1 to m do:
3:
for 2j + k = 1 to n1/(1+2s) ∧ (B/ log2 n) do
(i)
(i)
4:
Yjk :=TransApprox(Xjk )
5: In the central machine:
6: for 2j + k = 1 to n1/(1+2s) ∧ (B/ log2 n) do
(i)
7:
fˆjk := mean{Yjk : 1 ≤ i ≤ m}.
P
8: Construct: fˆ =
fˆjk ϕjk .

The following theorem asserts that the constructed estimator indeed attains the
lower bound in case (i) (up to a logarithmic factor).

7

ADAPTIVE DISTRIBUTED ESTIMATION

Theorem 2.4. Let s, L > 0 and suppose that B ≥ n1/(1+2s) / log2 n. Then the
s (L))
distributed estimator fˆ described in Algorithm 2 belongs to Fdist (B, . . . , B; B2,∞
and satisfies
sup
s
f0 ∈B2,∞
(L)

2s

Ef0 kfˆ − f0 k22 . n− 1+2s ∨ (B/ log2 n)−2s .

Proof. See Section 3.2
Next we consider the case (ii) of Corollary 2.2, i.e. the case that the communication restriction satisfies (n log2 (n)/m2+2s )1/(1+2s) ≤ B < n1/(1+2s) / log2 n. Using
Algorithm 2 in this case would result in a highly sub-optimal procedure, as we prove
at the end of Section 3.3. It turns out that under this more severe communication
restriction we can do much better if we form different groups of machines that work
on different parts of the signal.
1
We introduce the notation η = b(n 1+2s log2 n/B)(1+2s)/(2+2s) c and note that in
this case 1  η  m. Then we group the local machines into η groups and let the
different groups work on different parts of the signal as follows: the machines with
(i)
numbers 1 ≤ i ≤ m/η each transmit the approximations Yjk of the observations
(i)

Xjk for 1 ≤ 2j + k ≤ B/ log2 n; the next machines, with numbers m/η < i ≤ 2m/η,
(i)

each transmit the approximations Yjk for B/ log2 n < 2j + k ≤ 2B/ log2 n, and so
(i)

on. The last machines with numbers (η − 1)m/η < i ≤ m transmit the Yjk for
(η − 1)B/ log2 n < 2j + k ≤ ηB/ log2 n. Then in the central machine we average the
corresponding transmitted
noisy coefficients
in the obvious way. Formally, using the


notation µjk = (2j + k) log2 n/B − 1, the aggregated estimator fˆ is the function
with wavelet coefficients given by
(
µ m
(µ +1)m
(i)
ηB
mean{Yjk : jkη < i ≤ jk η
}, if 2j + k ≤ log
,
2n
fˆjk =
0,
else.
The procedure is summarized as Algorithm 3.
Algorithm 3 Nonadaptive L2 -method, case (ii)
1: In the local machines:
2: for ` = 1 to η do
3:
for i = b(` − 1)m/ηc + 1 to b`m/ηc do
4:
for 2j + k = b(` − 1)B/ log2 nc + 1 to b`B/ log2 nc do
(i)
(i)
5:
Yjk :=TransApprox(Xjk )
6: In the central machine:
7: for 2j + k = 1 to bηB/ log2 nc do
(i)
8:
fˆjk := mean{Yjk : µjk m/η < i ≤ (µjk + 1)m/η}
P
9: Construct: fˆ =
fˆjk ϕjk .

The following theorem asserts that this estimator attains the lower bound in case
(ii) (up to a logarithmic factor).
Theorem 2.5. Let s, L > 0 and suppose that (n log2 (n)/m2+2s )1/(1+2s) ≤ B <
ˆ
2 n. Then the distributed estimator f described in Algorithm 3 belongs

n1/(1+2s) / log

8

SZABÓ AND VAN ZANTEN

s (L)) and satisfies
to Fdist (B, . . . , B; B2,∞

sup
s
f0 ∈B2,∞
(L)

Ef0 kfˆn − f0 k22 . Mn

1
 n 1+2s
 2s
2+2s − 2s
n 1+2s ,
B log2 n

4s

with Mn = (log2 n) 2+2s .
Proof. See Section 3.3
2.3. Distributed minimax results for L∞ -risk. When we replace the L2 -norm by
the L∞ -norm and correspondingly change the type of Besov balls we consider, we
can derive a lower bound similar to Theorem 2.1 (see Appendix B for the rigorous
definition of Besov balls).
Theorem 2.6. Consider s, L > 0 and communication constraints B (1) , . . . , B (m) >
0. Let the sequence δn = o(1) be defined as the solution to the equation (2.2). Then
in distributed signal-in-white-noise model (2.1) we have that
inf

sup

s
s
fˆ∈Fdist (B (1) ,...,B (m) ;B∞,∞
(L)) f0 ∈B∞,∞
(L)

Ef0 kfˆ − f0 k∞ &

 n − s
s
1+2s
∨ δn1+2s ,
log n

Proof. See Section 3.5
The proof of the theorem is very similarly to the proof of Theorem 2.6. The first
term on the right hand side follows from the usual non-distributed minimax lower
bound. For the second term we use the standard version of Fano’s inequality. We
s
again consider a large enough finite subset of B∞,∞
(L). The effective resolution
−1
level in the non-distributed case is (1 + 2s) log2 (n/ log2 n) in case of the L∞ -norm.
Similar to the L2 case the effective resolution level changes to (1 + 2s)−1 log δn−1 ,
which can be again substantially different from the non-distributed case. The rest
of the proof follows the lines of that of Theorem 2.6.
We can draw similar conclusions for the L∞ -norm as for the L2 -norm. If we do not
transmit a sufficient amount of bits (at least n1/(1+2s) up to a log n factor) from the
local machines to the central one then the lower bound from the theorem exceeds the
minimax risk corresponding the non-distributed case. Furthermore by transmitting
s
the sufficient amount of bits Cn1/(1+2s) log n corresponding to the class B∞,∞
(L),
the lower bound will coincide with the non-distributed minimax estimation rate.
One can also show that slightly modified versions of the algorithms given in the
L2 -case can reach the lower bound (up to a logarithmic factor) in the L∞ -case as
well, hence the derived results are (nearly) sharp.
2.4. Adaptive distributed estimation. The (almost) rate-optimal procedures considered so far have in common that they are non-adaptive, in the sense that they
all use the knowledge of the regularity level s of the unknown functional parameter
of interest. In this section we exhibit a distributed algorithm attaining the lower
bounds (up to a logarithmic factor) across a whole range of regularities s simultaneously. In the non-distributed setting it is well known that this is possible, and many
adaptation methods exist, including for instance the block Stein method, Lepski’s
method and Bayesian adaptation methods (e.g. [16, 7]). In the distributed case the
matter is more complicated. Using the usual adaptive tuning methods in the local

ADAPTIVE DISTRIBUTED ESTIMATION

9

machines will typically not work (see [15]) and in fact it was recently conjectured
that adaptation, if at all possible, would require more communication than is allowed
in our model (see [19]).
We will show however that in our setting, if all machines have the same communication restriction given by B > 0, it is possible to adapt to regularities s ranging
in the interval [smin , smax ), where
n
o
1
smin = arg inf (n log2 (n)/m2+2s ) 1+2s ≤ B
s>0

and smax is the regularity of the considered Daubechies’ wavelet and can be chosen
arbitrarily large. Note that smin is well defined. If s ∈ [smin , smax ), then we are in one
of the non-trivial cases (i) or (ii) of Corollary 2.2. We will construct a distributed
method which, up to logarithmic factors, attains the corresponding lower bounds,
without using knowledge about the regularity level s.
In the non-adaptive case we saw that different strategies were required to attain
the optimal rate, case (ii) requiring a particular grouping of the local machines. The
cut-off between cases (i) and (ii) depends however on the value of s, so in the present
adaptive setting we do not know beforehand in which of the two cases we are. In
order to tackle this problem we introduce a somewhat more involved grouping of
the machines, which basically gives us the possibility to carry out both strategies
simultaneously. This is combined with a modified version of Lepski’s method, carried out in the central machine, ultimately leading to (nearly) optimal distributed
concentration rates for every regularity class s ∈ [smin , smax ), simultaneously.
As a first step in our adaptive procedure we divide the machines into groups. Let
us first take the first bm/2c machines and denote the set of their index numbers by I.
Then the remaining dm/2e machines are split into η̃ = d(1 + 2smin )−1 log2 ne equally
sized groups (for simplicity each group has bdm/2e/η̃c machines and the leftovers are
discarded). The corresponding sets of indices are denoted by I0 , I1 , . . . , Iη̃−1 . Note
that |It |  m/ log n, for t ∈ {0, ..., η̃ − 1}. Then the machines in the group I transmit
(i)
the approximations Yjk (with D = 5/2 in Algorithm 1) of the observed coefficients
(i)

Xjk , for 1 ≤ j ≤ jB,n − 1, k ∈ Kj , with
jB,n := blog2 (B/(3 log2 n))c,
to the central machine. The machines in group It , t ∈ {0, ..., η̃−1}, will be responsible
for transmitting the coefficients at resolution level j = jB,n + t. First for every t ∈
{0, . . . , η̃ − 1}, the machines in group It are split again into 2t equal size groups (for
simplicity each group has b2−t bdm/2e/η̃cc machines and the leftovers are discarded
again), denoted by It,1 , It,2 , . . . , It,2t . A machine i in one of the groups It,` for ` ∈
(i)

{1, ..., 2t } transmits the approximations Yjk (again with D = 5/2 in Algorithm 1)
(i)

of the noisy coefficients Xjk , for j = jB,n + t and (` − 1)2jB,n ≤ k < `2jB,n to the
central machine.
In the central machine we first average the transmitted approximations of the
corresponding coefficients. We define
(
P
(i)
|I|−1 i∈I Yjk
if j < jB,n , k ∈ Kj ,
(2.4)
Yjk =
P
(i)
−1
|It,` |
if jB,n ≤ j < jB,n + η̃, k ∈ Kj .
i∈It,` Yjk
Using these coefficients we can construct for every j the preliminary estimator
X X
f˜(j) =
Yjk ϕjk .
l≤j−1 k∈Kl

10

SZABÓ AND VAN ZANTEN

This gives us a sequence of estimators from which we select the appropriate one
log2 n
using a modified version of Lepski’s method. We consider J = {1, ..., 1+2s
} and
min
define ĵ as

(2.5)
ĵ = min j ∈ J : kf˜(j) − f˜(l)k2 ≤ τ 2l /nl , ∀l > j, l ∈ J ,
for some sufficiently large parameter τ > 1 (τ = 29 smax is sufficiently large, but
nB
smaller choices are possible) and nj = |Ij−jB,n ,1 |n/m  2j (log
2 , for j ≥ jB,n and
2 n)
nj = |I|n/m  n for j < jB,n . Then we construct our final estimator fˆ simply by
taking fˆ = f˜(ĵ).
We summarize the above procedure (without discarding servers for achieveing
exacty equal size subgroups) in Algorithm 4, below.

Algorithm 4 Adaptive L2 -method
1: In the local machines:
2: for i = 1 to bm/2c do
3:
for j = 1 to jB,n − 1 do
4:
for k = 0 to 2j − 1 do
(i)
(i)
5:
Yjk :=TransApprox(Xjk )
6: for t = 0 to η̃ − 1 do
7:
for ` = 1 to 2t do j
j
j
k
j
kk
j
k j
kk
8:
for i = bm/2c+t dm/2e
+(`−1) 2−t dm/2e
+1 to bm/2c+t dm/2e
+` 2−t dm/2e
η̃
η̃
η̃
η̃
do
9:
for j = jB,n to jB,n + η̃ − 1 do
10:
for k = 0 to 2j − 1 do
(i)
(i)
11:
Yjk :=TransApprox(Xjk )
12: In the central machine:
13: (1) Averaging the local observations:
14: for j = 1 to jB,n − 1 do
15:
for k = 0 to 2j − 1 do
(i)
16:
yjk := mean{Yjk : i ≤ m/2}
17: for t = 0 to η̃ − 1 do
18:
j := jB,n + t
19:
for ` = 1 to 2t do
jB,n
20:
for k = (` − 1)2n
to `2jB,n −j1 do k
j
j
kk
(i)
dm/2e
−t dm/2e
21:
yjk := mean Yjk : b m
+
(`
−
1)
2
<i≤
c
+
t
2
η̃
j η̃ kko
j
k
j
dm/2e
−t dm/2e
m
22:
≤b2c+t
+` 2
η̃
η̃
23: (2) Lepski’s method :
24: for j = 1 toPblog2 n/(1
P + 2smin )c do
25:
f˜(j) := l≤j−1 k∈Kj yjk ϕjk
26: Let ĵ := blog2 n/(1 + 2smin )c, stop := F ALSE
27: while stop == F ALSE and ĵ ≥ 1 do
28:
Let l = ĵ + 1
29:
while stop == F ALSE and l ≤ blog2 n/(1 + 2smin )c do
30:
if kf˜(j) − f˜(l)k22 ≤ τ 2l /nl then
31:
l := l + 1
32:
else stop := T RU E
33:
if stop == F ALSE then
34:
ĵ := ĵ − 1
35: Construct: fˆ = f˜(ĵ).

11

ADAPTIVE DISTRIBUTED ESTIMATION

Theorem 2.7. For every L, s > 0 the distributed method fˆ described above
s (L)). Furthermore for all L > 0 there exists a positive
belongs to Fdist (B, . . . , B; B2,∞
constant C > 0 such that for all s ∈ [smin , smax )
 −2s/(1+2s)
n
,



sup
Ef0 kfˆ−f0 k22 ≤ C B/n,

 2s

s
f0 ∈B2,∞ (L)

 nB − 2+2s ,
log22 n

if B ≥ CL n1/(1+2s) log2 n,
1

2s

1

if n 1+2s (log2 n) 1+2s ≤ B < CL n 1+2s log2 n,
2s

if B < n1/(1+2s) (log2 n) 1+2s ,

with CL = 12L2/(1+2s) .
Proof. See Section 3.6.
3. Proofs.
3.1. Proof of Theorem 2.1. Note that without loss of generality we can multiply
δn with an arbitrary constant. In the proof we define δn as the solution to
o
n m
m
(3.1)
.
δn = 2−15 L−2 min
, P
1
n log2 n
1+2s
(i) ∧ 1]
[δ
n m
(n)B
log
n
2
i=1
We prove the desired lower bound for the minimax risk using a modified version
of Fano’s inequality, given in Theorem A.6. As a first step we construct a finite
s (L). We use the wavelet notation outlined in Appendix B. Define
subset F0 ⊂ B2,∞
jn = b(log2 δn−1 )/(1 + 2s)c. For β ∈ {−1, 1}|Kjn | , let fβ ∈ L2 [0, 1] be the function
with wavelet coefficients
(
1/2
Lβk δn , if j = jn , k ∈ Kjn ,
fβ,jk =
(3.2)
0,
else.
s (L), since
Now define F0 = {fβ : β ∈ {−1, 1}|Kjn | }. Note that F0 ⊂ B2,∞
s
kfβ k2B2,∞
= sup 22sj

j

X

2
fβ,jk
= L2 2(2s+1)jn δn ≤ L2 .

k∈Kj

For this set of functions F0 , the maximum and minimum number of elements in
balls of radius t > 0, given by
n
o
Ntmax = max #{fβ 0 ∈ F0 : kfβ − fβ 0 k2 ≤ t} ,
fβ ∈F0
n

Ntmin = min #{fβ 0 ∈ F0 : kfβ − fβ 0 k2 ≤ t} ,
fβ ∈F0


P
2
satisfy Ntmax = Ntmin and Ntmax = t̃i=o |Kijn | < |F0 |/2 for t̃ = 4δtn L2 < |Kjn |/2
(and therefore Ntmax < |F0 | − Ntmin ).
Now recall that X = (X (1) , . . . , X (m) ) is the data available at the local machines
and Y = (Y (1) , . . . , Y m) ) are the binary messages transmitted to the central machine.
We can consider the Markov chain F → X → Y , where F is a uniform random

12

SZABÓ AND VAN ZANTEN

element in F0 . It then follows from Theorem A.6 (with t2 = 2L2 δn |Kjn |/3 and
d(f, g) = kf − gk2 ) that
(3.3)

I(F ; Y ) + log 2 
,
Ef0 kfˆ − f0 k22 & L2 δn |Kjn | 1 −
s
s
log(|F0 |/Ntmax )
(L)) f0 ∈B2,∞
fˆ∈Fdist (B (1) ,...,B (m) ;B2,∞
(L)
sup

inf

where I(F ; Y ) is the mutual information between the random variables F and Y .
Pt̃
|Kjn |
To lower bound the right-hand side, first note that Ntmax =
<
i=1
i
|Kjn |
2
2
t̃
2 t̃
≤ 2(e|Kjn |/t̃) and therefore, for t̃ = |Kjn |/6 (i.e. t = 2L δn |Kjn |/3),
log(|F0 |/Ntmax ) ≥ |Kjn | log(2(6e)−1/6 2−1/|Kjn | ) ≥ |Kjn |/6.
1

−

Hence, using |Kjn | = δn 1+2s we see that to derive the statement of the theorem from
(3.3) it is sufficient to show that
I(F ; Y ) ≤ δn−1/(1+2s) /8 + O(1).

(3.4)

To do so, first note that for δn ≤ m/(211 L2 n log2 n) the conditions of Lemma A.13
−

1

are satisfied hence by applying the lemma (with δ 2 = L2 δn and d = δn 1+2s ) we get
2

−1

I(F ; Y ) ≤ 2L nδn m

m
X

o
n
− 1
− 1
min 210 log(mδn 1+2s )H(Y (i) ), δn 1+2s + 4 log 2

i=1
−

1

≤ 2L2 nδn m−1 δn 1+2s

(3.5)

m 
X


1
211 log(n)δn1+2s B (i) ∧ 1 + O(1),

i=1

where the last inequality follows from Lemma A.15. Since from the definition of δn
it follows that
2−4 L−2 mn−1
δn ≤ P 
1
,
m
1+2s
(i)
11
B ∧1
i=1 2 log(n)δn
−

1

the right-hand side of (3.5) is further bounded by 2−3 δn 1+2s + O(1), finishing the
proof of assertion (3.4) and concluding the proof of the theorem.
3.2. Proof of Theorem 2.4. In the procedure as a first step we take the first
(i)
∧ (B/ log2 n) noisy coefficients, i.e. Xjk , 2j + k ≤ n1/(1+2s) ∧ (B/ log2 n),

n1/(1+2s)

(i)

and transmit their approximation Yjk , cf. Algorithm 1 with D = 1/2. Note that for
P 2
s (L) we have that f 2 ≤ sup 2js
2
any f ∈ B2,∞
j
k fjk ≤ L , hence in view of Lemma
jk
2.3 (with |µ| = |f0,jk | ≤ L) the approximation satisfies
√
(i)
(i)
(i)
0 ≤ (Xjk − Yjk )/Xjk ≤ 1/ n

(i)

and Ef [l(Yjk )] ≤ (1/2 + o(1)) log2 n.
(i)

Therefore we need at most (1/2 + o(1))B bits in expected value to transmit {Yjk :
2j + k ≤ n1/(1+2s) ∧ (B/ log n)}, hence fˆn ∈ Fdist (B, ..., B; B s (L)).
2

2,∞

Next for convenience we introduce the notation
(i)

(i)

(i)

(1 − εjk )Xjk , which satisfies εjk

(i)
εjk

(i)

for the error term Yjk =
−1/2
∈ [0, n
]. The estimator fˆ is given by its wavelet

13

ADAPTIVE DISTRIBUTED ESTIMATION

coefficients fˆjk , j ∈ N, k ∈ Kj . For 2j + k > n1/(1+2s) ∧ (B/ log2 n) we have fˆjk = 0,
while for 2j + k ≤ n1/(1+2s) ∧ (B/ log2 n),
m

m

i=1

i=1

1 X (i)
1 X (i)
1
(i)
fˆjk =
Yjk =
Xjk (1 − εjk ) = f0,jk (1 − εjk ) + √ Zjk − Wjk ,
m
m
n
where εjk = m−1
satisfying

(i)
i=1 εjk

Pm

iid

∈ [0, n−1/2 ], Zjk ∼ N (0, 1) and Wjk = (nm)−1/2
(i)

Ef0 |Wjk | ≤ n−1/2 E|Zjk | =

p
2/πn−1/2 ,

(i)

2
Ef0 Wjk
≤ n−1 E(Zjk )2 = n−1 .

For convenience we also introduce the notation jn =
Then the risk is bounded from above by
Ef0 kfˆ − f0 k22 ≤

X X

2
f0,jk

+

jn X 
X
j=1 k∈Kj

j≥jn k∈Kj

(i) (i)
i=1 Zjk εjk ,

Pm




1
log2 (n 1+2s ∧ (B/ log2 n)) .

1
Ef0 ( √ Zjk − Wjk )2
n


2
Ef0 ε2jk + Ef0 |f0,jk εjk |(|Wjk | + n−1/2 |Zjk |)
+ f0,jk
.

X

j≥jn

j≥jn
−2jn s

(3.6)

X

2−2js sup 22js

.2

jn

2
f0,jk
+

n−1

j=1 k∈Kj

k∈Kj

+ 2 /n . n

jn X
X

−2s/(1+2s)

∨ (B/ log2 n)−2s ,

s (L) we have |f
where we have used that for f0 ∈ B2,∞
0,jk | ≤ L for any j ≥ 1, k ∈ Kj .
s (L) we have
3.3. Proof of Theorem 2.5. First recall that for every f0 ∈ B2,∞
2
≤ L , j ≥ 1, k ∈ Kj . Therefore, in view of Lemma 2.3 (with D = 1/2) we have

2
f0,jk

(i)

Ef0 [l(Yjk )] ≤ (1/2+o(1)) log2 n. Since each machine transmits at most bB/ log2 nc+
1 coefficients we get that the total amount of transmitted bits per machine is bounded
s (L)).
from above by B (for large enough n), hence fˆ ∈ Fdist (B, . . . , B; B2,∞
Let Ajk = {bµjk m/ηc + 1, ..., b(µjk + 1)m/ηc} be the collection of machines transmitting the (j, k)th coefficient and note that #(Ajk )  m/η. Then our aggregated
estimator fˆ satisfies for 2j + k ≤ ηB/ log2 n (i.e. the total number of different coefficients transmitted) that
r
X (i)
1
m
ˆ
fjk =
Yjk = f0,jk (1 − ε̃jk ) +
Zjk − W̃jk ,
#(Ajk )
n#(Ajk )
i∈Ajk

where ε̃jk =
ing

1
#(Ajk )

(i)

−1/2 ], W̃
jk =
i∈Ajk εjk ∈ [0, n

P

(i)

Ef0 |W̃jk | ≤ n−1/2 E|Zjk | =
iid

p
2/πn−1/2 ,

√

√

m
n#(Ajk )

P

(i) (i)

i∈Ajk

Zjk εjk satisfy-

(i)

2
Ef0 W̃jk
≤ n−1 E(Zjk )2 = n−1 ,

and Zjk ∼ N (0, 1).
Let jn = blog2 (ηB/ log2 n)c. Then similarly to (3.6) the risk of the aggregated

14

SZABÓ AND VAN ZANTEN

estimator is bounded as
Ef0 kfˆ − f0 k22 ≤

.

∞ X
X

jn X
X

m
Zjk − W̃jk )2
n#(Ajk )
j=jn k∈Kj
j=1 k∈Kj
r

o2
m
2
+ f0,jk
Ef0 ε̃2jk + Ef0 |f0,jk ε̃jk | |W̃jk | +
|Zjk |
n#(Ajk )
∞
X

2
f0,jk
+

sup 22js

j=jn j≥jn

X

2
f0,jk
+

k∈Kj

r
n
Ef0 Ef0 (

jn X
X

η/n

j=1 k∈Kj

Bη 2

2s
Bη −2s
+
 (nB/ log2 n)− 2+2s
log2 n
n log2 n

 2s
1/(1+2s)
4s
n
2+2s − 2s
2+2s
= (log2 n)
n 1+2s ,
B log2 n

.
(3.7)

concluding the proof of the theorem.
Finally we show that Algorithm 1 is in general suboptimal in this case. Consider
s (1) with wavelet coefficients f
−j(s+1/2) , j ∈ N, k ∈ K ,
the function f0 ∈ B2,∞
j
0,jk = 2
and take jn = dlog2 (B/ log2 n)e, then
X
X X
2
2−jn (2s+1)
≥
Ef0 kfˆ − f0 k22 ≥
f0,jk
j≥jn k∈Kj

k∈Kjn

 B −2s
 n1/(1+2s)  2s
2+2s − 2s
&
n 1+2s
= M̃n
log2 n
B log2 n
 2s

3+2s
2+2s
2 n)
term tends to infinity and
where the multiplication factor M̃n = n(log
B 1+2s
can be of polynomial order, yielding a highly sub-optimal rate.
3.4. Proof of Lemma 2.3. One can easily see by construction that
0 ≤ (X − Y )/X ≤ n−D .

(3.8)

Next note that the expected number of transmitted bits is bounded from above by
E(3 + log2 (1 ∨ |1 + log2 |X||) + D log2 n) = 3 + D log2 (n) + E log2 |1 + log2 |X||.
The expected value Elog2 (1 ∨ |1 + log2 |X||) is further bounded from above by
2

n−1

Z ∞
2
 log (1 + log (1/x)) (x−µ)2
log2 (1 + log2 (x)) − (x−µ)
−
2
2
p
p
e 2m/n dx + 2
e 2m/n dx
2πm/n
2πm/n
n−1
0
1
Z
Z
−1
2
n
1
p
(x−µ)
1
−
p
. n/m
log(1/x)dx + log(log n)
e 2m/n dx
2πm/n
0
n−1
Z ∞
2
(x−µ)
x
−
p
+
e 2m/n dx
2πm/n
1
r

µ2
2m − 2m/n
−µ 
−1/2
. (log n)(nm)
+ log log n +
e
+ µ 1 − 2Φ
nπ
m/n
. log log n.

Z

Z

1

+

We can conclude that El(Y ) ≤ (D + o(1)) log n.

15

ADAPTIVE DISTRIBUTED ESTIMATION

Finally, note that by similar computation

P log2 (1 ∨ |1 + log2 |X||) > log2 (1 + log2 n2 ) ≤ P(|X| < n−2 ) + P(|X| > n2 )
 Z n−2 Z ∞ r n
(x−µ)2
−
+
≤2
e 2m/n dx
2πm
0
n2
√ −n3 /(4m)
−1/2 −3/2
.m
n
+ ne
= o(n−3/2 ),
finishing the proof of the lemma.
3.5. Proof of Theorem 2.6. First of all we note that in the non-distributed case
where all the information
is available in the global machine the minimax L∞ -risk
s
− 1+2s
is (n/ log n)
. Since the class of distributed estimators is clearly a subset of the
class of all estimators this will be also a lower bound for the distributed case. The
rest of the proof goes similarly to the proof of Theorem 3.1.
s
First we construct a finite subset F0 ⊂ B∞,∞
(L) and then give a lower bound for
the minimax risk over it. Let us denote by K̃j the largest set of Daubechies wavelets
with disjoint supports. Note that |K̃j | ≥ c0 2j (for large enough j and sufficiently
small c0 > 0). Let us again multiply δn with a sufficiently small constant and work
with this δn in the rest of the proof
n m
o
m
δn := c0 2−13 L−2 min
(3.9)
.
, P
1
n log2 n
1+2s
(i) ∧ 1]
[δ
(n)B
n m
log
n
2
i=1
Let jn = b(log2 δn−1 )/(1 + 2s)c and for β ∈ {−1, 1}|K̃jn | let fβ ∈ L2 [0, 1] be the
function with wavelet coefficients
(
1/2
Lδn βk , if j = jn , k ∈ K̃jn ,
fβ,jk =
0,
else,
Now let F0 = {fβ : βk ∈ {−1, 1}, k ∈ K̃jn }.
s
Note that each function fβ ∈ F0 belongs to the set B∞,∞
(L), since
2
s
kfβ kB∞,∞
= sup 2(s+1/2)j sup fβ,jk
= 2(s+1/2)jn sup Lδn1/2 = L2(s+1/2)jn δn1/2 ≤ L.
j

k∈K̃j

k∈K̃jn

Furthermore, if fβ 6= fβ 0 , then there exists a k ∈ K̃jn such that βk 6= βk0 . Then due
to the disjoint support of the corresponding Daubechies’ wavelets ϕjn ,k , k ∈ K̃jn the
L∞ -distance between the two functions is bounded from below by
s

kfβ − fβ 0 k∞ ≥ |fjn k0 − fj0n k0 | · kϕjn ,k0 k∞ &2jn /2+1 δn1/2 ≥ δn1+2s .
Now let F be a uniform random variable on the set F0 . Then in view of Fano’s
s/(1+2s)
inequality (see Theorem A.5 with δ = δn
and p = 1) we get that


s 
I(F ; Y ) + log 2 
Ef0 kfˆ − f0 k∞ & δn1+2s 1 −
.
s
log2 |F0 |
s
fˆ∈Fdist (B (1) ,...,B (m) ;B∞,∞
(L)) f0 ∈B∞,∞
(L)
inf

sup

−1/(1+2s)

Hence, since log2 |F0 | ≥ |K̃jn | ≥ c0 2jn = c0 δn
−1/(1+2s)
I(F ; Y ) ≤ (c0 /2)δn
.

, it remains to show that

16

SZABÓ AND VAN ZANTEN
−

1/2

1

In view of Lemma A.13 (applied with δ = δn , d = |K̃jn | = c0 δn 1+2s , X = X (i) ,
Y = Y (i) , i = 1, ..., m, and noting that δn ≤ m/(211 L2 n log2 n) hence the conditions
are fulfilled)
−

1

I(F ; Y ) ≤ 2L2 nδn m−1 δn 1+2s
≤

m 
X


1
210 log(n)δn1+2s H(Y (i) ) ∧ c0 + 4 log 2,

i=1
m 
X

− 1
212 L2 nδn m−1 δn 1+2s


1
log(n)δn1+2s B (i) ∧ 1 + O(1),

i=1

where the last line follows from Theorem A.15. We conclude the proof by using the
definition of δn , see (3.9).
s (L)
3.6. Proof of Theorem 2.7. First recall that for every s, L > 0 and f0 ∈ B2,∞
2
we have f0,jk
≤ L2 , j ≥ 1, k ∈ Kj . Therefore, in view of Lemma 2.3 (with D = 5/2)
(i)

we have Ef0 [l(Yjk )] ≤ (5/2 + o(1)) log2 n. Since the machines in group I and the
machines in It,` , t ∈ {0, ..., η̃ − 1}, ` ∈ {1, ..., 2t } transmit at most 2blog2 (B/(3 log2 n))c
coefficients we have that in expected value at most

2blog2 (B/(3 log2 n))c 5/2 + o(1) log2 n ≤ B
bits are transmitted per machine (for n large enough). Therefore the estimator indeed
s (L)).
belongs to Fdist (B, . . . , B; B2,∞
Next we show that the estimator fˆ achieves the minimax rate. First let us in(i)
(i)
(i)
(i)
troduce the notation jmax = b(log2 n)/(1 + 2smin )c and εjk = (Xjk − Yjk )/Xjk ∈
[0, n−5/2 ]. Then note that for j ≤ jmax and k ∈ Kj the aggregated quantities Yjk
defined in (2.4) are equal to
(3.10)

Yjk =

1 X (i)
(i)
−1/2
Xjk (1 − εjk ) = f0,jk + nj Zjk − Wjk − εjk f0,jk ,
|Jjk |
i∈Jjk

where

where εjk

(
I,
if j < jB,n , k ∈ Kj ,
Jjk =
Ij−jB,n ,` , if j ≥ jB,n , (` − 1)2jB,n ≤ k < `2jB,n ,
P
P
(i)
(i) (i)
−5/2 ], W
1/2 n−1
= n−1
jk = (m/n)
i∈Jjk εjk ∈ [0, n
i∈Jjk Zjk εjk , satisj
j
iid

2 = O(n−5 ), Z
fying Ef0 |Wjk | = O(n−5/2 ) and Ef0 Wjk
jk ∼ N (0, 1), and recall that
nj = n|Jjk |/m for every j ≤ jmax , k ∈ Kj . Recall also that nj  nB/(2j (log2 n)2 )
for j ≥ jB,n and nj  n for j < jB,n .
Note that the squared bias satisfies

kEf0 f˜(j) − f0 k22 . kK(f0 , j) − f0 k22 + n−5 (kf0 k22 + 1)
s
. 2−2js kf0 k2B2,∞
+ n−5 ,

Pj−1 P
where K(f0 , j) = l=1
k∈Kl f0,lk ϕlk . Let us introduce the notation B(j, f0 ) =
−2js
2
2
kf0 kB s and define the optimal choice of the parameter j (the optimal reso2,∞
lution level) as

j ∗ = min j ∈ J : B(j, f0 ) ≤ 2j /nj .

17

ADAPTIVE DISTRIBUTED ESTIMATION

Note that since the right hand side is monotone increasing and the left hand side is
monotone decreasing in j, we have that
B(j, f0 ) ≤ 2j /nj , for j ≥ j ∗

and B(j, f0 ) > 2j /nj , for j < j ∗ .

Therefore
2j

∗ −1

∗

/nj ∗ −1 < B(j ∗ − 1, f0 ) = 22s B(j ∗ , f0 ) ≤ 22s 2j /nj ∗ .

Let us distinguish three cases according to the value of j ∗ . If j ∗ < jB,n then
∗
nj ∗ −1 = nj ∗  n and therefore 2j  n1/(1+2s) (using the definition B(j ∗ , f0 ) =
∗
2−2j s kf0 k2B s ). Note that the inequality j ∗ < jB,n is implied by B(jB − 1, f0 ) ≤
2,∞

2jB −1 /njB −1 , which in turns holds if 2jB −1 ≥ (nkf0 k2B s )1/(1+2s) . Therefore we can
2,∞

conclude that B ≥ 12L2/(1+2s) n1/(1+2s) log2 n implies the inequality j ∗ < jB,n . If
∗
j ∗ = jB,n , then nj ∗  n/ log2 n, nj ∗ −1  n and therefore (n/ log2 n)1/(1+2s) . 2j 
∗
B/ log2 n . n1/(1+2s) . Finally, if j ∗ > jB,n , then nj ∗ −1  nj ∗  nB/(2j log22 n) and
∗
therefore 2j  (nB/ log22 n)1/(2+2s) . We summarize these findings in the following
display

(3.11)

j∗

2

 1/(1+2s)
,

n
 B/ log2 n,


(nB/ log22 n)1/(2+2s)

if B ≥ CL n1/(1+2s) log2 n,
1

2s

1

if n 1+2s (log2 n) 1+2s ≤ B < CL n 1+2s log2 n,
2s

if B < n1/(1+2s) (log2 n) 1+2s ,

and

(3.12)

nj ∗



n,
& n/ log2 n,

1+2s

(nB/ log22 n) 2+2s

if B ≥ CL n1/(1+2s) log2 n,
1

2s

1

if n 1+2s (log2 n) 1+2s ≤ B < CL n 1+2s log2 n,
2s

if B < n1/(1+2s) (log2 n) 1+2s ,

where CL = 12L2/(1+2s) .
Finally, we also note that for ` ≤ j we have n` ≥ nj and hence
X X 2
2
Ef Z 2 + 2Ef0 W`k
n` 0 `k

Ef0 kf˜(j) − Ef0 f˜(j)k22 ≤

`≤j−1 k∈Kj

−1/2

2
+ f0,`k
Ef0 ε2`k + 2|f0,`k |E(n`
X X
j
.
n−1
` ≤ 2 /nj .


|Z`k | + |W`k |)|ε`k |

`≤j−1 k∈Kj

Let us split the risk into two parts
(3.13)

Ef0 kf0 − fˆk22 = Ef0 kf0 − f˜(ĵ)k22 1ĵ>j ∗ + Ef0 kf0 − f˜(ĵ)k22 1ĵ≤j ∗

and deal with each term on the right-hand side seperately. First note that
Ef0 kf0 − f˜(ĵ)k22 1ĵ≤j ∗ ≤ 2Ef0 kf˜(j ∗ ) − f˜(ĵ)k22 1ĵ≤j ∗ + 2Ef0 kf˜(j ∗ ) − f0 k22
∗
. τ 2j /nj ∗ + kEf0 f˜(j ∗ ) − f0 k22 + Ef0 kf˜(j ∗ ) − Ef0 f˜(j ∗ )k22
∗

∗

. 2j /nj ∗ + 2−2j s ,

18

SZABÓ AND VAN ZANTEN

which implies together with (3.11) and (3.12) that
(3.14)
 −2s/(1+2s)
n
,
if B ≥ CL n1/(1+2s) log2 n,



1
2s
1
if n 1+2s (log2 n) 1+2s ≤ B < CL n 1+2s log2 n,
Ef0 kf0 −fˆk22 1ĵ≤j ∗ . B/n,

 2s

2s

 nB/ log2 n − 2+2s , if B < n1/(1+2s) (log n) 1+2s
.
2

2

Next we deal with the first term on the right hand side of (3.13). By CauchySchwarz inequality and Lemma 3.1 we get that
jX
max

Ef0 kf0 − fˆk2 1ĵ>j ∗ ≤

1/2
1/2
Ef0 kf0 − f˜(j)k22 Pf0 (ĵ = j)

j=j ∗ +1
jX
max

.

1/2

Pf0 (ĵ = j) .

j=j ∗ +1

≤e

∞
X

j∗ i

e−(c/2)τ 2

+ 2jmax n−2

i=1

−(c/2)τ 2j

∗

−(c/2)τ 2j

/(1 − e

∗

∗

) + o(n−1 ) = o(2−2sj ) + o(n−1 ),

for sufficiently large choice of the parameter τ (i.e. τ ≥ 2smax /c is sufficiently large),
resulting in the required upper bound in view of (3.14), concluding the proof of our
statement.
Lemma 3.1.
j > j ∗ we have

s (L), for some s, L > 0. Then for every
Assume that f0 ∈ B2,∞
j

Pf0 (ĵ = j) . e−cτ 2 + n−4 ,
for some universal sufficiently small constant c > 0 (c = 2−8 is small enough).
Proof. The proof of the lemma is a slight adaptation of Lemma 8.2.1 of [7].
Let us introduce the notation j − = j − 1 and note that for every j > j ∗ we have
−
j ≥ j ∗ . Then by the definition of ĵ
Pf0 (ĵ = j) ≤

jX
max

Pf0 (kf˜(j − ) − f˜(l)k22 > τ 2l /nl ).

l=j

Note that the left hand side term in the probability in view of Parseval’s inequality
can be given in the form
kf˜(j − ) − f˜(l)k22 =

l−1 X 
X

−1/2

f0,`k (1 − ε`k ) + n`

Z`k − W`k

2

`=j − k∈K`

≤

l−1 X 
X
`=j −

−1/2

2
2
2f0,lk
+ 2n−1
` Z`k + 2n`

Z`k f0,`k

k∈K`

+

2
3W`k

+



−1/2
2n` |Z`k ε`k |

.

We deal with the five terms on the right hand side separately. Note that the functions
j 7→ B(j, f0 ) and j 7→ nj are monotone decreasing, hence by the definition of j ∗ we
get for l ≥ j − ≥ j ∗
l−1 X
X
`=j − k∈K`

∗

2
f0,`k
≤ B(j − , f0 ) ≤ B(j ∗ , f0 ) ≤ 2j /nj ∗ ≤ 2l /nl .

ADAPTIVE DISTRIBUTED ESTIMATION

19

2 = O(n−5 ) and then by applying Markov’s and Chebyshev’s
Next recall that Ef0 W`k
inequalities we get that
Pl−1 P
l−1 X
−5 −1
2
X
2
2l  4 `=j − k∈K` n nl Ef0 Z`k
= O(n−4 ),
P f0
|Z
ε
|
>
≤
√
`k `k
2l /n2
n
2n
2
`
l
l
`=j − k∈K`
P
P
l−1
l−1 X
2
X
2l  6 `=j − k∈K` Ef0 W`k
2
3W`k >
P f0
≤
= O(n−4 ).
l /n
2n
2
−
k∈K`

`=j

Furthermore, note that
P f0

l−1
l−1
X
 X
X
2 X 2
τ − 3 2l 
τ − 5 l
2
Z`k >
≤
(Z`k
− 1) >
2
Pf0
n`
2 nl
4
−
−
k∈K`

`=j

P f0

l−1
 X
`=j −

`=j

k∈K`

l−1

X
2 X
τ − 3 2l 
τ − 3 2l 
Z`k f0,`k >
≤
Pf0 |Z(j − )| >
,
√
√
n`
2 nl
2
nl
−
k∈K`

`=j

where Z(j − ) is a centered Gaussian random variable with variance
l−1
X
nl X 2
f0,`k ≤ B(j ∗ , f0 ).
n
`
−

`=j

k∈K`

Then by Theorem 3.1.9 of [7] the first probability in the preceding display is bounded
from above by a multiple of
l−1
X

exp{−D

`=j −

(τ − 5)2 22l
} ≤ exp{−c̃τ 2l },
(τ − 4)2l

for some universal, small enough constants c̃, D > 0 (the constants D = 2−6 and
c̃ = 2−8 are sufficiently small if τ ≥ 10) and the second probability by
l−1
X

exp{−D0

`=j −

(τ − 3)2 22l
} ≤ exp{−c0 τ 2l },
nl B(j ∗ , f0 )

again for some universal, small enough constants c0 , D0 > 0 (the constants D0 = 2−4
and c0 = 2−2 are sufficiently small if τ ≥ 9). Those we obtain that
Pf0 (ĵ = j) .

jX
l
max X

l

e−cτ 2 + O(n−4 ),

for all j > j ∗ ,

l=j `=j

for some universal constant c > 0 (c = 2−8 is sufficiently small), finishing the proof
of the statement.
APPENDIX A: INFORMATION THEORETIC RESULTS
A.1. Basic definitions and results. A classical reference for basic concepts
and results from information theory is the second chapter of [2]. Statements are only
proved for discrete variables in Chapter 2 of [2], but several are valid more generally
and are used more generally in this paper. All logarithms are base e here.

20

SZABÓ AND VAN ZANTEN

In this section, where we recall notations and basic results, (X, Y, Z) is a random
triplet in a space X × Y × Z that is nice enough, so that regular versions of all
conditional distributions exist (for instance a Polish space). We denote the joint
distribution by P(X,Y,Z) , the (regular version of the) conditional distribution of X
given Y = y by PX | Y =y , etcetera. If X and Y are discrete we denote by p(X,Y )
the joint probability mass function (pmf) of (X, Y ), by pX and pY the marginal
pmf of X and Y , and by pX | Y =y (x) = p(X,Y ) (x, y)/pY (y) the conditional pmf of X
given Y = y. For probability measures P and Q on
R the same space we define the
Kullback-Leibler divergence as usual as K(P, Q) = (log dP /dQ) dP if P  Q, and
as +∞ if not.
The mutual information between X and Y and the conditional mutual information
between X and Y , given Z, are defined as
I(X; Y ) = K(P(X,Y ) , PX × PY ),
I(X; Y | Z = z) = K(P(X,Y ) | Z=z , PX | Z=z × PY
Z
I(X; Y | Z) = I(X; Y | Z = z) dPZ (z).

| Z=z ),

The (conditional) mutual information is nonnegative and symmetric in X and Y .
If X and Y are discrete we define the entropy of X and the conditional entropy
of X given Y by
X
H(X) = −
pX (x) log pX (x)
x

H(X | Y ) = −

X

p(X,Y ) (x, y) log pX | Y =y (x).

x,y

Entropy and conditional entropy are nonnegative. For discrete X and Y , it holds
that I(X; Y ) = H(X) − H(X | Y ). Hence, since mutual information is nonnegative,
H(X | Y ) ≤ H(X) (conditioning reduces entropy). If X is a discrete variable on a
finite set X then H(X) ≤ log |X |, with equality if X is uniformly distributed on
X . We denote by H(p) = −p log p − (1 − p) log(1 − p) the entropy of a Bernoulli
variable with parameter p ∈ (0, 1). The function p 7→ H(p) is a concave function
that is symmetric around p = 1/2. Its maximum value, attained at p = 1/2, equals
log 2.
We now recall a number of basic identities for mutual information. First of all,
we have the following rule for a general, not necessarily discrete random triplet.
Proposition A.1 (Chain rule for mutual information).

We have

I(X; (Y, Z)) = I(X; Y | Z) + I(X; Z).
We call the triplet (X, Y, Z) a Markov chain, and write X → Y → Z, if the joint
distribution disintegrates as
dP(X,Y,Z) (x, y, z) = dPX (x)dPY

| X=x (y)dPZ | Y =y (z).

In this situation we have the following result, which relates the information in the
different links of the chain. Again, discreteness of the variables is not necessary for
this result.

ADAPTIVE DISTRIBUTED ESTIMATION

21

Proposition A.2 (Data-processing inequality). If X → Y → Z is a Markov
chain, then
I(X; Y ) = I(X; Y | Z) + I(X; Z).
In particular
I(X; Z) ≤ I(X; Y ).
In case of independence, mutual information is sub-additive in the following sense.
Proposition A.3 (Role of independence).
pendent given X, then

If Y and Z are conditionally inde-

I(X; (Y, Z)) = I(X; Y ) + I(X; Z) − I(Y ; Z) ≤ I(X; Y ) + I(X; Z).
Finally we recall Fano’s inequality [6] which we use in the following form in this
paper.
Proposition A.4 (Fano’s lemma). Let X → Y → X̂ be a Markov chain, where
X and X̂ are random elements in a finite set X and X has a uniform distribution
on X . Then
log 2 + I(X; Y )
P(X 6= X̂) ≥ 1 −
.
log |X |
A.2. Lower bounds for estimators using processed data. In this section
we consider a situation in which we have a random element X in X with a distribution Pf depending on a parameter f in a semimetric space (F, d). Moreover, we
assume that we have a Markov chain X → Y defined through a Markov transition
kernel Q(dy | x) from X to some space Y. Note that this includes the case that Y is
simply a measurable function Y = ψ(X) of the full data X. We view Y as a transformed, or processed version of the full data X. We are interested in lower bounds
for estimators fˆ for f that are only based on the processes data. The collection of
all such estimators, i.e. measurable functions of Y , is denoted by E(Y ).
The usual approach of relating lower bounds for estimation to lower bounds for
testing multiple hypotheses, in combination with Fano’s lemma, gives the following
useful result in our setting.
Theorem A.5. If F contains a finite set F0 of functions that are 2δ-separated
for the semimetric d, then

log 2 + I(F ; Y ) 
inf sup Ef dp (fˆ, f ) ≥ δ p 1 −
log |F0 |
fˆ∈E(Y ) f ∈F
for all p > 0. Here I(F ; Y ) is the mutual information between F and Y in the Markov
chain F → X → Y , where F has a uniform distribution on F0 and X | f ∼ Pf .
We also use a slight modification of this basic result, where the condition that
the functions in F0 are separated is replaced by a condition on the minimum and
maximum number of elements in F0 that are contained in small balls. Given a finite
set F0 , we use the notations
n
o
Ntmax = max #{f˜ ∈ F0 : d(f, f˜) ≤ t} ,
f ∈F0
n
o
Ntmin = min #{f˜ ∈ F0 : d(f, f˜) ≤ t} .
f ∈F0

22

SZABÓ AND VAN ZANTEN

The following theorem is a slight extension of Corollary 1 of [5]. In the latter corollary
it is implicitly assumed that Y is a discrete random variable (the conditional entropy
H(F | Y ) is considered), while we can allow continuous random variables as well. For
self-containedness we provide the proof below.
If F contains a finite set F0 and |F0 | − Ntmin > Ntmax , then

Theorem A.6.


I(F ; Y ) + log 2 
sup Ef dp (fˆ, f ) ≥ tp 1 −
log(|F0 |/Ntmax )
fˆ∈E(Y ) f ∈F
inf

for all p, t > 0. Here I(F ; Y ) is the mutual information between F and Y in the
Markov chain F → X → Y , where F has a uniform distribution on F0 and X | f ∼
Pf .
Proof. We have
inf

sup Ef dp (fˆ, f ) ≥ tp inf

sup Pf (d(fˆ, f ) ≥ t)

fˆ∈E(Y ) f ∈F0

fˆ∈E(Y ) f ∈F

≥ tp inf P(Y,F ) (d(fˆ, F ) > t),
fˆ∈E(Y )

therefore it is sufficient to show that
I(F ; Y ) + log 2
inf P(Y,F ) (d(fˆ, F ) > t) ≥ 1 −
.
log(|F0 |/Ntmax )
fˆ∈E(Y )
By definition,
Z
I(F ; Y ) =

log

dP(F,Y )
dP
.
d(PF × PY ) (F,Y )

By disintegration, dP(F,Y ) (f, y) = dPY (y)dPF | Y =y (f ), so that by Fubini,
(A.1)

I(F ; Y ) =

Z Z

log


dPF | Y =y
dPF | Y =y dPY (dy).
dPF

Now PF is the uniform distribution on F0 . Hence, it has density p(f ) = 1/|F0 | w.r.t.
the counting measure df on F0 . Define p(f | y) = PF | Y =y ({f }), so that PF | Y =y has
density p(f | y) w.r.t. df . The KL-divergence K(PF | Y =y , PF ) in the inner integral
can then be written as
Z
p(f | y)
p(f | y) log
df.
p(f )
Similarly fˆ has some density p̂(fˆ) w.r.t. the counting measure dfˆ on F0 and we
define p̂(fˆ|y) = PF̂ |Y =y ({fˆ}).
Next note that by the data-processing inequality, see Proposition A.2, we have
I(F ; Y ) − I(F ; fˆ) ≥ 0. Then
Z Z
Z
0 ≤ I(F ; Y ) − I(F ; fˆ) =
p(f |y) log p(f |y)df dPY (dy) − p(f ) log p(f )df
Z
Z Z

−
p(f, fˆ) log p(f |fˆ)df dfˆ − p(f ) log p(f )df
Z Z
=
p(f |y) log p(f |y)df dPY (dy)+H(F |fˆ).

ADAPTIVE DISTRIBUTED ESTIMATION

23

Next note that since F is uniform on F0 (see Section A.1),
Z Z
p(f, y) log p(f |y)df dy = I(F ; Y )−H(F )=I(F ; Y ) − log(|F0 |).
We can summarize the above results as
H(F |fˆ)≥ log(|F0 |) − I(F ; Y ).

(A.2)

Since by assumption the conditions of Proposition 1 of [5] hold, we have
min

|F0 | − Nt
H(F |fˆ) ≤ H(pt ) + pt log
Ntmax

+ log Ntmax ,

where pt = P(F,Y ) (d(fˆ, F ) > t). Then noting that log pt ≤ log 2 and by combining
the preceding display with (A.2) we get that
log(|F0 |) − I(F ; Y ) ≤ log 2 + pt log

|F0 | − Ntmin
+ log Ntmax .
Ntmax

Reformulation of the inequality yields
log(|F0 |/Ntmax )
I(F ; Y ) + log 2
−

min
max
log (|F0 | − Nt )/Nt
log (|F0 | − Ntmin )/Ntmax
I(F ; Y ) + log 2
,
≥1−
log(|F0 |/Ntmax )

P(Y,F ) (d(fˆ, F ) > t) ≥

which completes the proof.
In the next subsections we give bounds for the mutual information under various
assumptions on the random variables X and f .
A.3. Bounding I(F ; Y ): bounded likelihood ratios. We consider again a
Markov chain F → X → Y . We assume that F has a uniform distribution on a
finite set F0 and that X | (F = f ) ∼ Pf .
In this section we assume that there exists a constant C ≥ 1 and a set X 0 that
has full mass under Pf for every f ∈ F0 , such that
(A.3)

sup

max

x∈X 0 f1 ,f2 ∈F0

dPf1
(x) ≤ C.
dPf2

This condition bounds the information in the first link F → X of the chain. As
a result, it becomes possible to derive an upper bound on I(F ; Y ) in terms of the
constant C and the information I(X; Y ) in the other link of the chain.
The following theorem is a slight extension of Lemma 3 of [18] (without the
independence assumption, see later) where we allow the random variables X and Y
to be continuous as well, unlike in Lemma 3 of [18], where it was implicitly assumed
that they are discrete (by using the entropy H(X) and H(X|Y ) in the proof).
However, in our manuscript X is continuous and therefore the above mentioned
lemma does not apply directly.
Theorem A.7.

Assume that (A.3) holds for C ≥ 1. Then
I(F ; Y ) ≤ 2C 2 (C − 1)2 I(X; Y ).

24

SZABÓ AND VAN ZANTEN

Proof. In view of (A.1)
Z Z
(A.4)

p(f | y) log

I(F ; Y ) =

p(f | y)
df dPY (dy).
p(f )

Since KL-divergence is nonnegative, we have
Z
p(f | y)
− p(f ) log
df ≥ 0.
p(f )
It follows that the inner integral in (A.4) is bounded by
Z
p(f | y)
df.
(p(f | y) − p(f )) log
p(f )
Since | log(a/b)| ≤ |a − b|/(a ∧ b), we have the further bound
Z
|(p(f | y) − p(f )|2
df.
K(PF | Y =y , PF ) ≤
p(f | y) ∧ p(f )
We will see ahead that the denominator in the integrand is always strictly positive.
We also define p(f | x) = PF | X=x ({f }). Then by conditioning on X we see that
Z
Z
p(f | y) = p(f | x) dPX | Y =y (x),
p(f ) = p(f | x) dPX (x).
By subtracting these relations and using also that
Z

0 = p(f ) dPX | Y =y (x) − dPX (x) ,
we obtain
Z
|p(f | y) − p(f )| =
(A.5)


(p(f | x) − p(f )) dPX | Y =y (x) − dPX (x)

≤ 2 sup |p(f | x) − p(f )| kPX | Y =y − PX kTV .
x∈X 0

Now by Bayes’ formula and the assumption (A.3) on the likelihood,
(A.6)

1
p(f | x)
=R
∈ [1/C, C]
p(f )
dPf 0 /dPf (x)p(f 0 ) df 0

for all x ∈ X 0 . But then also
(1 − C)p(f ) ≤ (1/C − 1)p(f ) ≤ p(f | x) − p(f ) ≤ (C − 1)p(f ),
that is, |p(f | x) − p(f )| ≤ (C − 1)p(f ). Also note that since
Z
p(f | y) = p(f | x) dPX | Y =y (dx),
(A.6) implies that p(f | y)/p(f ) ∈ [1/C, C] as well. In particular, p(f ) ≤ Cp(f | y).
Together, we get
|p(f | x) − p(f )| ≤ C(C − 1)(p(f ) ∧ p(f | y))

ADAPTIVE DISTRIBUTED ESTIMATION

25

for all x ∈ X 0 . Combining with what we had above, we get
|p(f | y) − p(f )| ≤ 2C(C − 1)(p(f ) ∧ p(f | y))kPX | Y =y − PX kTV ,
and hence
|(p(f | y) − p(f )|2
≤ 4C 2 (C − 1)2 p(f )kPX | Y =y − PX k2TV .
p(f | y) ∧ p(f )
Integrating w.r.t. f this gives the bound
K(PF , PF | Y =y ) ≤ 4C 2 (C − 1)2 kPX | Y =y − PX k2TV .
Use Pinsker’s inequality (e.g. [16], p. 88) and integrate w.r.t PY to arrive at the
statement of the theorem.
A.4. Bounding I(F ; Y ): general case. We consider the same setting as in
the preceding section, that is, we have Markov chain F → X → Y and we assume
that F has a uniform distribution on a finite set F0 and that X | f ∼ Pf . In this
section we drop the condition that we have a uniform bound on the the likelihood
ratio. The bound for the mutual information I(F ; Y ) then takes the following form.
The following theorem is a slight extension of Lemma 4 of [18] (without the
independence assumption, see later) where we allow again that the random variables
X and Y are continuous as well, unlike in Lemma 4 of [18], where it was implicitly
assumed that they are discrete.
For all C ≥ 1 we have


dPf1
log |F0 | X
I(F ; Y ) ≤ log 2 +
max
(X) > C + 2C 2 (C − 1)2 I(X; Y ).
Pf
f1 ,f2 ∈F0 dPf2
|F0 |
Theorem A.8.

f ∈F0

Proof. Define the set
n
o
dPf1
B = x :∈ X : max
(x) ≤ C
f1 ,f2 ∈F0 dPf2
and the indicator variable E = 1X∈B . With this notation the statement of the
theorem reads
I(F ; Y ) ≤ log 2 + P(X,F ) (E = 0) log |F0 | + 2C 2 (C − 1)2 I(X; Y ),
where P(X,F ) is the probability measure defined by the Markov chain, i.e. the measure
under which F is uniform and X | (F = f ) ∼ Pf .
By the chain rule and the fact that the mutual information is nonnegative,
I(F ; (Y, E)) = I(F ; Y ) + I(F ; E | Y ) ≥ I(F, Y ). On the other hand, applying the
chain rule with Y and E reversed shows that I(F ; (Y, E)) = I(F ; Y | E) + I(F ; E).
Hence, we have the inequality
I(F ; Y ) ≤ I(F ; Y | E) + I(F ; E).
The second term on the right involves only discrete variables and can be bounded
by H(E). This is the entropy of a Bernoulli variable, which is bounded by log 2. The
first term equals
pI(F ; Y | E = 1) + (1 − p)I(F ; Y | E = 0),

26

SZABÓ AND VAN ZANTEN

where p = PX (E = 1). Below we prove that
(A.7)

I(F ; Y | E = 1) ≤ 2C 2 (C − 1)2 I(X, Y | E = 1).

By the chain rule, I(X; Y | E) = I(Y ; (X, E)) − I(Y ; E) ≤ I(Y ; (X, E)). Since E
is a function of X, the last quantity equals I(Y ; X). Next, observe that it follows
from the definitions that
Z Z
1
I(F ; Y | E = 0) = H(F | E = 0)−
p(f |y) log
df dPY | E=0 (y) ≤ H(F | E = 0).
p(f |y)
Since F | E = 0 lives in the finite set F0 , this is further bounded by log |F0 |.
It remains to establish (A.7). This essentially follows from conditioning on E = 1
everywhere in the proof of Theorem A.7. Indeed, conditioning in the first part of the
proof shows that
Z Z
|(p(f | y, E = 1) − p(f | E = 1)|2 
I(F ; Y | E = 1) ≤
df dPY | E=1 (dy)
p(f | y, E = 1) ∧ p(f | E = 1)
and
|p(f | y, E = 1) − p(f | E = 1)| ≤ 2 sup p(f | x, E = 1) − p(f | E = 1)
x∈B

× kPX | Y =y,E=1 − PX | E=1 kTV .
Now observe that since the likelihood ratio is uniformly bounded by C for x ∈ B,
Bayes formula implies that
p(f | x, E = 1)
∈ [1/C, C]
p(f | E = 1)
for all x ∈ B. We can then follow the rest of the proof of Theorem A.7 and arrive
at (A.7).
A.5. Bounding I(F ; Y ): extra independence assumption. Next we consider one additional assumption on the structure of the problem. We assume that
the data X is a d-dimensional vector of the form X = (X1 , . . . , Xd ), and that F is
a d-dimensional vector as well such that for all coordinates j ∈ {1, . . . , d}, it holds
that Fj and Xj |(Fj = fj ) are independent of F−j . More precisely, we assume that
for the marginal conditional density of Xj it holds that
p(xj |f ) = p(xj | fj )
for every j. Note that this is an assumption on the statistical model for the data X
and is not related to the distribution of F .
The following theorem is an extended version of Lemma 3 of [18] (now also with
the independence assumption) as it holds also for continuous random variables X
and Y , unlike the result derived in [18] .
Theorem A.9. Suppose that F and X are d-dimensional and that Xj | F only
depends on Fj (i.e. p(xj |f ) = p(xj |fj )). Moreover, suppose that for the marginal
densities p(xj | fj ) it holds that
sup max0
xj f 6=f

p(xj | fj )
≤C
p(xj | fj0 )

ADAPTIVE DISTRIBUTED ESTIMATION

27

for a constant C ≥ 1. Then
I(F ; Y ) ≤ 2C 2 (C − 1)2

d
X

I(Xj ; Y | F1:j−1 ).

i=1

Proof. By the chain rule,
I(F ; Y ) =

d
X

I(Fj ; Y | F1:j−1 ).

j=1

So consider term i in the sum.
By definition of conditional mutual information and Fubini’s theorem,
I(Fj ; Y | F1:j−1 ) =
Z
 
Z
Z
p(fj | y, f1:j−1 )
dfj dy df1:j−1 .
p(f1:j−1 )
p(y | f1:j−1 )
p(fj | y, f1:j−1 ) log
p(fj | f1:j−1 )
We are first going to analyze the inner integral. So fix f1:j−1 for now. To simplify
the notation somewhat we are going to write densities that are conditional on f1:j−1
by p̃ instead of p. So then the inner integral becomes
Z
p̃(fj | y)
dfj .
p̃(fj | y) log
p̃(fj )
Since KL-divergence is nonnegative, it follows that the inner integral is bounded by
Z
p̃(fj | y)
dfj .
(p̃(fj | y) − p̃(fj )) log
p̃(fj )
In view of the inequality | log(a/b)| ≤ |a − b|/(a ∧ b) we obtain the further bound
Z

|(p̃(fj | y) − p̃(fj )|2
dfj .
p̃(fj | y) ∧ p̃(fj )

(we will see ahead that the denominator in the integrand is always strictly positive).
By conditioning on xj (and still on f1:j−1 ) we see that
Z
Z
(A.8)
p̃(fj | y) = p̃(fj | xj )p̃(xj | y) dxj ,
p̃(fj ) = p̃(fj | xj )p̃(xj ) dxj .
R
By subtracting these relations and using also that 0 = p̃(fj )(p̃(xj | y) − p̃(xj )) dxj ,
we obtain
Z
(p̃(fj | xj ) − p̃(fj ))(p̃(xj | y) − p̃(xj )) dxj
|(p̃(fj | y) − p̃(fj )| =
(A.9)

≤ 2 sup |p̃(fj | xj ) − p̃(fj )| kP̃Xj | Y =y − P̃Xj kTV .
xj ∈X 0

Now by Bayes’ formula,
p̃(fj | xj )
p̃(xj | fj )
=R
.
p̃(fj )
p̃(xj | fj0 ) dfj0

28

SZABÓ AND VAN ZANTEN

But by the conditional independence assumption, p̃(xj | fj ) = p(xj | f1:j ) = p(xj | fj ).
Hence, by the assumed bound on the marginal likelihood-ratio, p̃(fj | xj )/p̃(fj ) ∈
[1/C, C] for all xj ∈ X 0 . But then also
(1 − C)p̃(fj ) ≤ (1/C − 1)p̃(fj ) ≤ p̃(fj | xj ) − p̃(fj ) ≤ (C − 1)p̃(fj ),
that is, |p̃(fj | xj ) − p̃(fj )| ≤ (C − 1)p̃(fj ). Also note that the first identity in (A.8)
implies that p̃(fj | y)/p̃(fj ) ∈ [1/C, C] as well. In particular, p̃(fj ) ≤ C p̃(fj | y).
Together, we get
|p̃(fj | xj ) − p̃(fj )| ≤ C(C − 1)(p̃(fj ) ∧ p̃(fj | y))
for all xj ∈ X 0 . Combining with what we had above, we get
|p̃(fj | y) − p̃(fj )| ≤ 2C(C − 1)(p̃(fj ) ∧ p̃(fj | y))kP̃Xj | Y =y − P̃Xj kTV ,
and hence
|(p̃(fj | y) − p̃(fj )|2
≤ 4C 2 (C − 1)2 p̃(fj )kP̃Xj | Y =y − P̃Xj k2TV .
p̃(fj | y) ∧ p̃(fj )
Integrating w.r.t. fj this gives the bound
Z
p̃(fj | y)
dfj ≤ 4C 2 (C − 1)2 kP̃Xj | Y =y − P̃Xj k2TV .
p̃(fj | y) log
p̃(fj )
By Pinsker’s inequality,
1
kP̃Xj | Y =y − P̃Xj k2TV ≤ K(P̃Xj | Y =y , P̃Xj ).
2
Hence, by multiplying by p̃(y) and integrating we find that
Z
Z

p̃(fj | y)
p̃(y)
dfj dy ≤ 2C 2 (C − 1)2 I(Xj ; Y | F1:j−1 = f1:j−1 ).
p̃(fj | y) log
p̃(fj )
Multiplying by p(f1:j−1 ) and integrating gives
I(Fj ; Y | F1:j−1 ) ≤ 2C 2 (C − 1)2 I(Xj ; Y | F1:j−1 ).

We also have the version of the preceding result for the case that we do not have
the likelihood ratio bound everywhere. This result is an extended version of Lemma
4 of [18].
Theorem A.10. Suppose that F and X are d-dimensional and that Fj and Xj |Fj
are independent of F−j . For C ≥ 1, define
n
o
p(xj | fj )
Bj = xj : max0
≤
C
f 6=f p(xj | fj0 )
for a constant C ≥ 1. Then
I(F ; Y ) ≤

d 
X
j=1

q

(log 2) PXj (Xj 6∈ Bj ) + log |F0 |PXj (Xj 6∈ Bj ) + 2C 2 (C − 1)2 I(X; Y )

ADAPTIVE DISTRIBUTED ESTIMATION

29

Proof. Again we start with
I(F ; Y ) =

d
X

I(Fj ; Y | F1:j−1 ).

j=1

Now for fixed j we argue as in Theorem A.8, but conditional on F1:j−1 , to get
I(Fj ; Y | F1:j−1 ) ≤ H(1Xj ∈Bj | F1:j−1 ) + log |F0 |PXj (Xj 6∈ Bj )
+ 2C 2 (C − 1)2 I(Xj , Y | F1:j−1 ).
Since conditioning decreases entropy,
q
H(1Xj ∈Bj | F1:j−1 ) ≤ H(1Xj ∈Bj ) ≤ (log 2) PXj (Xj 6∈ Bj ).
Combining the preceding computations we get that
I(F, Y ) ≤

d 
X

q
(log 2) PXj (Xj 6∈ Bj ) + log |F0 |PXj (Xj 6∈ Bj )

j=1


+ 2C 2 (C − 1)2 I(Xj , Y | F1:j−1 ) .
Then the statement of the theorem follows from Lemma A.11 (below) and by applying the chain rule of information, i.e.
d
X

I(Xj ; Y |F1:j−1 ) ≤

j=1

Lemma A.11.
we have that

d
X

I(Xj ; Y |X1:j−1 ) = I(X; Y ).

j=1

Under the assumption that Xj |Fj and Fj are independent of F−j
I(Xj ; Y |F1:j−1 ) ≤ I(Xj ; Y |X1:j−1 ).

Proof.
Z Z Z
I(Xj ; Y |F1:j−1 ) =

p(xj , y|f1:j−1 ) log

p(xj , y|f1:j−1 )
dxj dy p(f1:j−1 )df1:j−1
p(xj |f1:j−1 )p(y|f1:j−1 )

Z Z Z
=
(A.10)

p(xj , y, f1:j−1 ) log p(xj |y, f1:j−1 )dxj dydf1:j−1
Z Z
−
p(xj , f1:j−1 ) log p(xj |f1:j−1 )dxj df1:j−1 .

Next we note that since Xj is independent of F1:j−1 we have p(xj ) = p(xj |f1:j−1 ),
furthermore since Xj and X1:j−1 are independent we get p(xj ) = p(xj |x1:j−1 ). Besides, we show below that
Z Z Z
p(xj , y, f1:j−1 ) log p(xj |y, f1:j−1 )dxj dydf1:j−1
(A.11) Z Z Z Z
≤
p(xj , y, f1:j−1 , x1:j−1 ) log p(xj |y, f1:j−1 , x1:j−1 )dxj dydf1:j−1 dx1:j−1

30

SZABÓ AND VAN ZANTEN

Combining the preceding assertions we get that the right hand side of (A.10) is
further bounded from above by
Z Z Z Z
p(xj , y, f1:j−1 , x1:j−1 ) log p(xj |y, f1:j−1 , x1:j−1 )dxj dydf1:j−1 dx1:j−1
Z Z
−
p(xj , x1:j−1 ) log p(xj |x1:j−1 )dxj dx1:j−1
Z Z Z
=
p(xj , y, x1:j−1 ) log p(xj |y, x1:j−1 )dxj dydx1:j−1
Z Z Z
−
p(xj , y, x1:j−1 ) log p(xj |x1:j−1 )dxj dydx1:j−1
=

I(Xj ; Y |X1:j−1 ),

where in the first equation we used the Markov property of the chain F 7→ X 7→ Y
combined with the independence of Xj:d and F1:j−1 , i.e.
p(xj |y, f1:j−1 , x1:j−1 ) =

p(xj , y|f1:j−1 , x1:j−1 )
p(xj , y|x1:j−1 )
=
= p(xj |y, x1:j−1 ).
p(y|f1:j−1 , x1:j−1 )
p(y|x1:j−1 )

It remained to verify the inequality (A.11).
Z Z Z Z
p(xj , y, f1:j−1 , x1:j−1 ) log p(xj |y, f1:j−1 , x1:j−1 )dxj dydf1:j−1 dx1:j−1
Z Z Z
−
p(xj , y, f1:j−1 ) log p(xj |y, f1:j−1 )dxj dydf1:j−1
Z Z Z Z
p(xj |y, f1:j−1 , x1:j−1 )
dxj dydf1:j−1 dx1:j−1
=
p(xj , y, f1:j−1 , x1:j−1 ) log
p(xj |y, f1:j−1 )
Z Z Z Z
p(xj , x1:j−1 |y, f1:j−1 )
=
p(xj , y, f1:j−1 , x1:j−1 ) log
dxj dydf1:j−1 dx1:j−1
p(xj |y, f1:j−1 )p(x1:j−1 |y, f1:j−1 )
= I(Xj ; X1:j−1 |Y, F1:j−1 ) ≥ 0.

A.6. Bounding I(F ; Y ): decomposable Markov chain. Suppose now in
addition that the data can be decomposed as X = (X (1) , . . . X (m) ) and that under
(i)
Pf , the X (i) are independent and X (i) ∼ Pf . This is intended to describe a setting
in which the data is distributed over m different local machines. The machines have
(i)
independent data and each machine has its local model (Pf : f ∈ F). Next we
have for every i a Markov chain X (i) → Y (i) defined by some Markov transition
kernel Q(i) . In other words, every machine processes or transforms its local data in
some way. Next the processed data is aggregated into a vector Y = (Y (1) , . . . , Y (m) ).
As before we consider the collection E(Y ) of all estimators that are measurable
functions of this aggregated, processed data Y . In this distributed setting we have
by Proposition A.3 that
X
(A.12)
I(F ; Y ) ≤
I(F ; Y (i) ).
i

Then the statement of Theorem A.12 can be reformulated as

31

ADAPTIVE DISTRIBUTED ESTIMATION

Theorem A.12. Let us assume that the data X is decomposable as above and
suppose that F and X are d-dimensional and that Xj | Fj and Fj are independent of
F−j . For C ≥ 1, define
n
o
p(xj | fj )
Bj = xj : max0
≤
C
f 6=f p(xj | fj0 )
for a constant C ≥ 1. Then
I(F ; Y ) ≤

m X
d 
X

r

(i)
(i)
(log 2) PX (i) (Xj 6∈ Bj ) + log |F0 |PX (i) (Xj 6∈ Bj )
j

i=1 j=1

+ 2C 2 (C − 1)2

j

m
X

I(X (i) ; Y (i) ).

i=1

I(X (i) ; Y (i) )

Here
is the mutual information between X (i) and Y (i) in the Markov
chain F → X (i) → Y (i) , where F has a uniform distribution on F0 and X (i) | (F =
(i)
f ) ∼ Pf = PX (i) |F =f .
Proof. The statement of the theorem follows by combining assertion (A.12) with
Theorem A.12.
A.7. Bounding I(F ; Y ): Gaussian example. In this example we further
(i)
(i)
assume that the random variables Xj are conditionally Gaussian, i.e. Xj |(Fj =
fj ) ∼ N (fj , m/n), for fj = δβj with βj ∈ {−1, 1} and that the observation X
satisfies the independence and decomposable assumptions introduced in Sections
A.5 and A.6, respectively. Then we can give a more concrete upper bound for the
mutual information I(F ; Y ).
Lemma A.13. Let F = δβ, with δ 2 ≤ 2−10 m/(n log(md)) and β a uniformly distributed random variable over {−1, 1}d . Furthermore, suppose that X = (X (1) , ..., X (m) ),
(i)
the X (i) ’s are independent, d-dimensional random variables and that Xj | (F =
(i)

f ) ∼ Pfj = N (fj , m/n). Then
I(F ; Y ) ≤

m
n
o
X
2δ 2
min 210 log(md)H(Y (i) ), d + 4 log 2,
m/n
i=1

where I(F ; Y ) is the mutual information between F and Y in the Markov chain
F →X →Y.
Proof. Let us introduce the notation a2 = 24 log(md)m/n and note that
n|(x−δ)2 −(x+δ)2 |
2n|δx|
2an|δ|
ϕδ,m/n (x)
2m
≤ sup e
≤ sup e m ≤ e m ,
|x|≤a ϕ−δ,m/n (x)
|x|≤a
|x|≤a

sup

where ϕµ,σ2 denotes the density function of a normal distribution with mean µ and
variance σ 2 . Furthermore, let us introduce
the notation Bj = {|xj | ≤ a}, j = 1, ..., d.

Then by Theorem A.12 (with F0 = f = δβ : β ∈ {−1, 1}d ) we have that
r
(i)
(i)
/ Bj ) + d2 mPX (i) (Xj ∈
/ Bj )
I(F ; Y ) ≤ dm(log 2) PX (i) (Xj ∈
j

(A.13)

+ 2C 2 (C − 1)2

j

m
X
i=1

I(X (i) ; Y (i) ),

32

SZABÓ AND VAN ZANTEN
3 |δ|

with C = e2

√

log(md)n/m

. Next note that for Z ∼ N (0, 1)

(i)

PX (i) (Xj ∈
/ Bj ) ≤ P (|Z| ≥ a − δ) ≤ 2e−

(a−δ)2 n
2m

a2 n

≤ 2e− 4m ≤ 2(md)−4 ,

j

and the inequality I(X (i) ; Y (i) ) ≤ H(Y (i) ) holds. Then by plugging in the above
inequalities into (A.13) and using the inequalities ex ≤ 1 + 2x for x ≤ 0.4 and
C 2 ≤ 2 we get that
I(F ; Y ) ≤

√

m

2(log 2)(md)−1 + 2(log 2)m−3 d−2 + 211 δ 2

log(md)n X
H(Y (i) ).
m
i=1

Furthermore, from the data-processing inequality and the convexity of the KL
divergence
I(F ; Y ) ≤

m
X

I(F ; Y (i) ) ≤

i=1

≤

=

m
X
i=1
m
X
i=1

m
X

I(F ; X (i) )

i=1

1
|F0 |2

(i)

X

(i)

K(Pf kPf )

f,f 0 ∈F0

X
1
δ2
kβ − β 0 k22
2m/n |F0 |2 0
f,f ∈F0

2

≤ 2ndδ .

Remark A.14. We note that the Gaussianity of the problem was only applied
in Lemma A.13, above. The rest of the information theoretic computations are distribution free and apply for a wider range of models. This leaves room for possible
extensions of the minimax lower bounds for other problems as well.
A.8. Entropy of a finite binary string. In the proof of Theorem 2.1 we need
to bound the entropy of transmitted finite binary string Y (i) . Since we do not want to
restrict ourself only to prefix codes, we can not use a standard version of Shannon’s
source coding theorem for this purpose. Instead we use the following result.
Lemma A.15.
the inequality

Let Y be a random finite binary string. Its expected length satisfies
H(Y ) ≤ 2El(Y ) + 1.

Proof. Let N = l(Y ) and consider a random binary string U with distribution
U N = n ∼ U nif ({0, 1}n ). Then for S the collection of finite binary strings,
K(Y, U ) =

X

=

X

=

X

P(Y = s) log

P(Y = s)
P(U = s)

P(Y = s) log

1
− H(Y )
P(U = s)

s∈S

s∈S

X

n s∈{0,1}n

P(Y = s) log

1
− H(Y ).
P(U = s)

ADAPTIVE DISTRIBUTED ESTIMATION

33

Now for every n and s ∈ {0, 1}n , we have P(U = s) = P(U = s | N = n)P(N = n) =
2−n P(N = n). It follows that
X

P(Y = s) log

s∈{0,1}n

1
2n
=P(N = n) log
.
P(U = s)
P(N = n)

Hence,
K(Y, U ) ≤ (log 2)EN + H(N ) − H(Y )
The non-negativity of the KL-divergence thus implies that H(Y ) ≤ EN + H(N ).
To complete the proof we show that H(N ) ≤ EN + 1. To do so consider the index
set I = {i : P (N = i) ≥ e−i } and note that the function x 7→ x log(1/x) is monotone
increasing for x ≤ e−1 . Then
X
1
1
+
P (N = i) log
P (N = i)
P (N = i)
i∈I
i∈I c
X
X
≤
P (N = i)i +
e−i i ≤ EN + 1.

H(N ) =

X

P (N = i) log

i∈I

i∈I c

This completes the proof.
APPENDIX B: DEFINITIONS AND NOTATIONS FOR WAVELETS
In this section we give a brief introduction to wavelets. A more detailed and
elaborate description of wavelets can be found for instance in [9, 7].
In our work we consider the Cohen, Daubechies and Vial construction of compactly supported, orthonormal, N -regular wavelet basis of L2 [0, 1], see for instance
[1]. First for any N ∈ N one can follow Daubechies’ construction of the father
ϕ(.) and mother ψ(.) wavelets with N vanishing moments and bounded support on
[0, 2N − 1] and [−N + 1, N ], respectively, see for instance [3]. Then we obtain the
basis functions

ϕj0 m , ψjk : m ∈ {0, ..., 2j0 −1 }, j > j0 , k ∈ {0, ..., 2j−1 } ,
for some sufficiently large resolution level j0 > 0. We also denote by Kj = {0, 1, ..., 2j − 1}
the collection indices at resolution level j > 0. Note that |Kj | = 2j . The basis functions (on x ∈ [0, 1]) are given as ψjk (x) = 2j/2 ψ(2j x − k), for k ∈ [N − 1, 2j − N ],
and ϕj0 k (x) = 2j0 ϕ(2j0 x − m), for m ∈ [0, 2j0 − 2N ], while for other values of k and
m, the basis functions are specially constructed, to form a basis with the required
smoothness property. For convenience we introduce the notation ψj0 k := ϕj0 k for
k = 0, ..., 2j0 −1 . This does not mean, however, that ϕj0 k (x) = 2−1 ψj0 +1,k (2−1 x).
Then the function f ∈ L2 [0, 1] can be represented in the form
∞ X
X

f=

fjk ψjk .

j=j0 k∈Kj

Note that in view of the orthonormality of the wavelet basis the L2 -norm of the
function f is equal to
kf k22

=

∞ X
X
j=j0 k∈Kj

2
fjk
.

34

SZABÓ AND VAN ZANTEN

For notational convenience we will take j0 to be 1 in our paper, this can be done
without loss of generality.
Next we introduce the Besov spaces we are considering in our analysis. Let us
define the Besov (Sobolev-type) norm for s ∈ (0, N ) as
kf ks,2 = max{2j0 s khf, ϕj0 ik2 , sup 2js khf, ψj ik2 },
j>j0

where hf, gi is the standard L2 -inner product of the functions f, g ∈ L2 [0, 1]. Then
s
s (L) of radius L > 0 are defined as
the Besov space B2,∞
and Besov ball B2,∞
s
B2,∞
= {f ∈ L2 [0, 1] : kf ks,2 < ∞},

s
and B2,∞
(L) = {f ∈ L2 [0, 1] : kf ks,2 < L},

respectively. We note that the present Besov space is larger than the standard
Sobolev space where instead of the supremum one would take the sum over the
resolution levels j. Then we introduce the Besov (Hölder-type) norm for s ∈ (0, N )
as
kf ks,∞ = sup {2j(s+1/2) |fjk |}.
j≥j0 ,k
s
s
Then similarly to before we define the Besov space B∞,∞
and Besov ball B∞,∞
(L)
of radius L > 0 as
s
B∞,∞
= {f ∈ L2 [0, 1] : kf ks,∞ < ∞},

s
and B∞,∞
(L) = {f ∈ L2 [0, 1] : kf ks,∞ < L},

respectively. For s 6= N these spaces are equivalent to the classical Hölder spaces,
while for integer s they are equivalent to the so called Zygmond spaces, see [1].
REFERENCES
[1] Cohen, A., Daubechies, I., and Vial, P. Wavelets on the interval and fast wavelet transforms. Applied and Computational Harmonic Analysis 1, 1 (1993), 54 – 81.
[2] Cover, T. M., and Thomas, J. A. Elements of information theory. John Wiley & Sons,
2012.
[3] Daubechies, I. Ten Lectures on Wavelets. Society for Industrial and Applied Mathematics,
1992.
[4] Deisenroth, M. P., and Ng, J. W. Distributed Gaussian Processes. ArXiv e-prints (Feb.
2015).
[5] Duchi, J. C., and Wainwright, M. J. Distance-based and continuum Fano inequalities with
applications to statistical estimation. ArXiv e-prints (Nov. 2013).
[6] Fano, R. M., and Hawkins, D. Transmission of information: A statistical theory of communications. American Journal of Physics 29, 11 (1961), 793–794.
[7] Giné, E., and Nickl, R. Mathematical foundations of infinite-dimensional statistical models.
Cambridge series in statistical and probabilistic mathematics. 2016.
[8] Guhaniyogi, R., Li, C., Savitsky, T. D., and Srivastava, S. A Divide-and-Conquer
Bayesian Approach to Large-Scale Kriging. ArXiv e-prints (Dec. 2017).
[9] Härdle, W., Kerkyacharian, G., Picard, D., and Tsybakov, A. Wavelets, Approximation, and Statistical Applications. Lecture Notes in Statistics. Springer New York, 2012.
[10] Johnstone, I. Gaussian estimation: Sequence and wavelet models. 2018+.
[11] Kleiner, A., Talwalkar, A., Sarkar, P., and Jordan, M. I. A scalable bootstrap for
massive data. Journal of the Royal Statistical Society: Series B (Statistical Methodology) 76,
4 (2014), 795–816.
[12] Scott, S. L., Blocker, A. W., Bonassi, F. V., Chipman, H., George, E., and McCulloch, R. Bayes and big data: The consensus monte carlo algorithm. In EFaBBayes 250
conference (2013), vol. 16.

ADAPTIVE DISTRIBUTED ESTIMATION

35

[13] Shang, Z., and Cheng, G. A Bayesian Splitotic Theory For Nonparametric Models. ArXiv
e-prints (Aug. 2015).
[14] Srivastava, S., Cevher, V., Tran-Dinh, Q., and Dunson, D. B. Wasp: Scalable bayes
via barycenters of subset posteriors. In AISTATS (2015).
[15] Szabo, B., and van Zanten, H. An asymptotic analysis of distributed nonparametric methods. ArXiv e-prints (Nov. 2017).
[16] Tsybakov, A. B. Introduction to nonparametric estimation. Springer, New York, 2009.
[17] Wang, J., Chen, J., and Wu, X. On the sum rate of gaussian multiterminal source coding:
New proofs and results. IEEE Transactions on Information Theory 56, 8 (Aug 2010), 3946–
3960.
[18] Zhang, Y., Duchi, J., Jordan, M. I., and Wainwright, M. J. Information-theoretic lower
bounds for distributed statistical estimation with communication constraints. In Advances in
Neural Information Processing Systems (2013), pp. 2328–2336.
[19] Zhu, Y., and Lafferty, J. Distributed Nonparametric Regression under Communication
Constraints. ArXiv e-prints (Mar. 2018).
Mathematical Institute
Leiden University
Niels Bohrweg 1
2333 CA Leiden
The Netherlands
E-mail: b.t.szabo@math.leidenuniv.nl

Korteweg-de Vries Institute for Mathematics
University of Amsterdam
Science Park 107
1098 XG Amsterdam
The Netherlands
E-mail: hvzanten@uva.nl

