Team-Optimal Distributed MMSE Estimation in General and Tree
Networks
Muhammed O. Sayina,∗, Suleyman S. Kozatb , Tamer Başara

arXiv:1610.00681v2 [] 8 Jan 2017

a The

Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Champaign, IL
61801 USA
b The Department of Electrical and Electronics Engineering, Bilkent University, Bilkent, Ankara 06800 Turkey

Abstract
We construct team-optimal estimation algorithms over distributed networks for state estimation
in the finite-horizon mean-square error (MSE) sense. Here, we have a distributed collection
of agents with processing and cooperation capabilities. These agents observe noisy samples
of a desired state through a linear model and seek to learn this state by interacting with each
other. Although this problem has attracted significant attention and been studied extensively in
fields including machine learning and signal processing, all the well-known strategies do not
achieve team-optimal learning performance in the finite-horizon MSE sense. To this end, we
formulate the finite-horizon distributed minimum MSE (MMSE) when there is no restriction
on the size of the disclosed information, i.e., oracle performance, over an arbitrary network
topology. Subsequently, we show that exchange of local estimates is sufficient to achieve the
oracle performance only over certain network topologies. By inspecting these network structures,
we propose recursive algorithms achieving the oracle performance through the disclosure of local
estimates. For practical implementations we also provide approaches to reduce the complexity
of the algorithms through the time-windowing of the observations. Finally, in the numerical
examples, we demonstrate the superior performance of the introduced algorithms in the finitehorizon MSE sense due to optimal estimation.
Keywords: Distributed networks, distributed Kalman filter, optimal information disclosure,
team problem, finite-horizon, MMSE estimation, tree networks, Gaussian processes.

1. Introduction
Over a distributed network of agents with measurement, processing and communication capabilities, we can have enhanced processing performance, e.g., fast response time, relative to the
centralized networks by distributing the processing power over the networks [1, 2, 3, 4]. Mainly,
distributed agents observe the true state of the system through noisy measurements from different viewpoints, process the observation data in order to estimate the state, and communicate with
each other to alleviate the estimation process in a fully distributed manner. Notably, the agents
∗ Corresponding

author
Email addresses: sayin2@illinois.edu (Muhammed O. Sayin), kozat@ee.bilkent.edu.tr (Suleyman S.
Kozat), basar1@illinois.edu (Tamer Başar)
Preprint submitted to Journal of LATEX Templates
January 10, 2017

can respond to streaming data in an online manner by disclosing information among each other
at certain instances. This framework is conveniently used to model highly complex structures
from defense applications to social and economical networks [5, 6, 7, 8]. As an example, say
that we have radar systems distributed over an area and seeking to locate hostile missiles, i.e., the
location of the missile is the underlying state of the system. In that respect, distributed processing
approach has vital importance in terms of detecting the missiles and reacting as fast as possible.
In particular, even if the viewpoints of a few radar systems are blocked due to environmental
obstacles, through the communication among the radar systems, each system should still be able
to locate the missiles. Additionally, since each radar system not only collects measurements but
also process them to locate the missiles, the overall system can respond to the missiles faster
than a centralized approach in which measurements of all the radar systems are collected at a
centralized unit and processed together.
Although there is an extensive literature on this topic, e.g., [2, 6, 7, 8, 9, 10, 11] and references
therein, we still have significant and yet unexplored problems for disclosure and utilization of
information among agents. Prior work has focused on the computationally simple algorithms
that aim to minimize certain cost functions through the exchange of local estimates, e.g., diffusion or consensus based estimation algorithms [2, 9, 3, 12, 13, 14], due to processing power
related practical concerns. However, there is a trade-off in terms of computational complexity
and estimation performance.
Formulating the optimal distributed estimation algorithms with respect to certain performance
criteria is a significant and unexplored challenge. To this end, we consider here the distributed
estimation problem as a team problem for distributed agents in which agents take actions, e.g.,
which information to disclose and how to construct the local estimate. This differs from the
existing approaches in which agents exchange their local estimates. Furthermore, we address the
optimality of exchanging local estimates with respect to the team problem over arbitrary network
structures.
We examine the optimal usage of the exchanged information based on its content rather than
a blind approach in which exchanged information is handled irrespective of the content as in the
diffusion or consensus based approaches. In such approaches, the agents utilize the exchanged
information generally through certain static combination rules, e.g., the uniform rule [15], the
Laplacian rule [16] or the Metropolis rule [17]. However, if the statistical profile of the measurement data varies over the network, i.e., each agent observes diverse signal-to-noise ratios, by
ignoring the variation in noise, these rules yield severe degradation in the estimation performance
[2]. In such cases the agents can perform better even without cooperation [2]. Therefore, the optimal usage of the exchanged information plays an essential role in performance improvement in
the team problem.
Consider distributed networks of agents that observe noisy samples of an underlying state
(possibly multi-dimensional) over a finite horizon. The agents can exchange information with
only certain other agents at each time instant. In particular, agents cooperate with each other
as a team according to a certain team cost depending on the agents’ actions. To this end, each
agent constructs a local estimate of the underlying state and constructs messages to disclose to
the neighboring agents at each time instant. We particularly consider a quadratic cost function
and that the underlying state and measurement noises are jointly Gaussian.
We note that restrictions on the sent messages, e.g., on the size of the disclosed information, has significant impact on the optimal team actions. We introduce the concept of the oracle
performance, in which there is no restriction on the disclosed information. In that case, a timestamped information disclosure can be team-optimal and we introduce the optimal distributed
2

online learning (ODOL) algorithm using the time-stamped information disclosure. Through a
counter example, we show that the oracle performance cannot be achieved through the exchange
of local estimates. Then, we analytically show that over certain networks, e.g., tree networks,
agents can achieve the oracle performance through the exchange of local estimates. We propose
the optimal and efficient distributed online learning (OEDOL) algorithm, which is practical for
real life applications and achieves the oracle performance over tree networks through the exchange of local estimates. Finally, we introduce the time windowing of the measurements in the
team cost and propose a recursive algorithm, sub-optimal distributed online learning (SDOL) algorithm, combining the received messages linearly through time-invariant combination weights.
We can list our main contributions as follows: 1) We introduce a team-problem to minimize
finite horizon mean square error cost function in a distributed manner. 2) We derive the ODOL
algorithm achieving the oracle performance over arbitrary networks through time-stamped information exchange. 3) We address whether agents can achieve the oracle performance through
the disclosure of local estimates. 4) We propose a recursive algorithm, the OEDOL algorithm,
achieving the oracle performance over certain network topologies with tremendously reduced
communication load. 5) We also formulate sub-optimal versions of the algorithms with reduced
complexity. 6) We provide numerical examples demonstrating the significant gains due to the
introduced algorithms.
The remainder of the paper is organized as follows. We introduce the team problem for
distributed-MMSE estimation in Section 2. We study the tree networks, exploit the network
topology to formulate the OEDOL algorithm that reduces the communication load and introduce
cell structures, which is relatively more connected than tree networks, in Section 3. We propose
the sub-optimal versions of the ODOL algorithm for practical implementations in Section 4. In
Section 5, we provide numerical examples demonstrating significant gains due to the introduced
algorithms. We conclude the paper in Section 6 with several remarks.
Notation: We work with real data for notational simplicity. N(0, .) denotes the multivariate
Gaussian distribution with zero mean and designated covariance. For a vector a (or matrix A), a0
(or A0 ) is its ordinary transpose. We denote the vector whose terms are all 1s (or all 0s) by 1 (and
0). We denote random variables by bold lower case letters, e.g., x . The operator col{·} produces
a column vector or a matrix in which the arguments of col{·} are stacked one under the other. For
a matrix A, diag{A} operator constructs a diagonal matrix with the diagonal entries of A. For a
given set N, diag{N} creates a diagonal matrix whose diagonal block entries are elements of the
set. The operator ⊗ denotes the Kronecker product.
2. Team Problem for Distributed-MMSE Estimation
Consider a distributed network of m agents with processing and communication capabilities.
In Fig. 1, we illustrate this network through an undirected graph, where the vertices and the edges
correspond to the agents and the communication links across the network, respectively. For each
agent i, we denote the set of agents whose information could be received at least after k hops, i.e.,
(k)
is the cardinality of Ni(k) (See Fig. 1b)1 . We assume
k-hop neighbors, by Ni(k) , and π(k)
i := Ni
(0)
(k)
that Ni = {i} and Ni = ∅ for k < 0. Note that the sequence of the sets {Ni(0) , Ni(1) , · · · } is a
non-decreasing sequence such that Ni(k) ⊆ Ni(l) if k < l.
1 For

notational simplicity, we define Ni := Ni(1) and πi := π(1)
i .

3

(2)
i

(3)
i

(1)
i
i

i

(a) First-order neighborhood

(b) All neighborhoods

Figure 1: The neighborhoods of ith agent over the distributed network.
Here, at certain time instants, the agents observe a noisy version of a time-invariant and unknown state vector x ∈ p which is a realization of a Gaussian random variable x with mean
x̄ and auto-covariance matrix Σ x . In particular, at time instant t, each agent i observes a noisy
version of the state as follows:

R

yi,t = Hi x + ni,t , t = 1, · · · , T,

R

R

where Hi ∈ q×p is a matrix commonly known by all agents, and ni,t ∈ q is a realization of
a zero-mean white Gaussian vector process {nni,t } with auto-covariance Σni . Correspondingly, the
observation yi,t ∈ q is a realization of the random process {yyi,t }, where y i,t = Hi x + n i,t almost
everywhere (a.e.). The noise n i,t is also independent of the state x and the other noise parameters
n j,τ , j , i and τ ≤ t. We assume that the statistical profiles of the noise processes are common
knowledge of the agents since they can readily be estimated from the data [18].
The agents have communication capabilities and at certain time instants, i.e., after each measurement, they can exchange information with the neighboring agents as seen in Fig. 1a. Let
zi, j,t ∈ Rr denote the information disclosed by i to j at time t, and r ≥ 0 is the size of the disclosed information. We assume that there exists a perfect channel between the agents such that
the disclosed information can be transmitted with infinite precision. Therefore, we denote the
information available to agent-i at time t by
n
o
δi,t = yi,t , yi,τ , z j,i,τ , for j ∈ Ni , τ = 1, · · · , t − 1

R

and let σi,t denote the sigma-algebra generated by the information set δi,t . Furthermore, we define
the set of all σi,t -measurable functions from Rqt × Rrπi (t−1) to Rr by Γi,t . Importantly, here, which
information to disclose is not determined a priori in the problem formulation. Let γi, j,t be the
decision strategy for zi, j,t , then agent-i chooses γi, j,t , j ∈ Ni , from the set Γi,t , i.e., γi, j,t ∈ Γi,t and
γi, j,t (δi,t ) = zi, j,t , based on his/her objective.
In addition to the disclosed information zi, j,t , j ∈ Ni , agent-i takes action ui,t ∈ Rq , where
the corresponding decision strategy ηi,t is chosen from the set Ωi,t , which is the set of all σi,t measurable functions from Rqt × Rrπi (t−1) to R p , i.e., ηi,t ∈ Ωi,t and ηi,t (δi,t ) = ui,t . Here, we
4

4 3 2 1 2 1

3 4 3 2 3 2

A

3 4 3 2 3 2

2 3 4 3 2 1

B

C

3 4 3 2 3 2

2 3 4 3 2 1

2 3 3 3 4 3

1 2 3 4 3 2

A B C D E F

t

4

F

E
1 2 1 2 3 4

D

2 3 3 3 4 3

2 3 3 3 4 3

1 2 3 4 3 2

y' , y' , y' , y' , y' , y'

4 3 2 1 2 1

A, 4

B ,3

C ,2

D ,1

E ,2

!

F ,1

Time stamp

Figure 2: Time stamped information disclosure over a network of 6 agents at time instant t = 4.
consider that the agents have a common cost function:
T X
m
X

kx − u j,t k2 ,

t=1 j=1

where all actions ui,t , i = 1, · · · , m and t = 1, · · · , T are costly, and agent-i should take actions
ui,t and zi, j,t , j = 1, · · · , πi and t = 1, · · · , T , accordingly. Therefore, this corresponds to a teamproblem, in which agent-i faces the following minimization problem:
min

T X
m
X

γi, j,t ∈Γi,t ,ηi,t ∈Ωi,t ,
j∈Ni ,t=1,··· ,T t=1 j=1

Ekxx − η j,t (δ j,t )k2 .

(1)

We point out that both Γi,t and Ωi,t are infinite dimensional, i.e., (1) is a functional optimization
problem and the optimal strategies can be a nonlinear function of the available information.
Furthermore, the agents should also construct the disclosed information accordingly since other
agents’ decisions u j,t directly depend on the disclosed information.
2.1. A Lower Bound
In order to compute the team optimal strategies, we first construct a lower bound on the performance of the agents by removing the limitation on the size of the disclosed information, i.e.,
r → ∞. In that case, the following proposition provides an optimal information disclosure strategy.
5

Proposition 2.1. When r → ∞, a time stamped information disclosure strategy, in which
agents transmit the most current version of the available information (e.g., see Fig. 2), can lead
to the team-optimal solution.
Proof. Through the time stamped information disclosure, each agent can obtain the measurements of the other agents separately in a connected network. However, the measurements of the
non-neighboring agents could only be received after certain hops due to the partially connected
structure, i.e., certain agents are not directly connected. As an example, the disclosed information of j ∈ Ni(2) reaches to i by passing through two communication links as seen in Fig. 1b. In
particular, this case assumes that each agent has access to full information from the other agents,
albeit with certain hops, and corresponds to the direct aggregation of all measurements across
the network at each agent.
Correspondingly, at time t, all the information aggregated at ith agent is given by
δoi,t :=


yi,τ

τ≤t

n oτ≤t−1
n oτ≤t−κi 
, y j,τ
,
·
·
·
,
y j,τ
(κi ) ,
(1)
j∈Ni

j∈Ni

(2)

where the information from the furthest agent is received at least after κi hops. Therefore, a
time-stamped information disclosure strategy can lead to the team-optimal solution.

Let σoi,t denote the sigma-algebra generated by the information set δoi,t and Ωoi,t be the set of all
κi

σoi,t -measurable functions from Rqt × Rqπi (t−1) × · · · × Rqπi |t−κi |+ (where |t − κi |+ = 0 if t − κi < 0)
to R p . Then, agent-i faces the following minimization problem:
T X
m
X

mino

ηi,t ∈Ωi,t ,
t=1 j=1
t=1,··· ,T

Ekxx − η j,t (δoj,t )k2 ,

(3)

which is equivalent to
T
X
t=1

min Ekxx − ηi,t (δoi,t )k2

(4)

ηi,t ∈Ωoi,t

since γi, j,t , j ∈ Ni , is set to the time-stamped strategy and ηi,t has impact only on the term
Ekxx − ηi,t (δoi,t )k2 . Let δ oi,t be defined by
δ oi,t :=


y i,τ

τ≤t

n oτ≤t−1
n oτ≤t−κi 
, y j,τ
,
·
·
·
,
y j,τ
(κi )
(1)
j∈Ni

j∈Ni

Then, team optimal strategy in the lower bound, i.e., oracle strategy, ηoi,t and the corresponding
action uoi,t are given by
ηoi,t (δoi,t ) = uoi,t = E[xx|δδoi,t = δoi,t ]

(5)

and we define u oi,t := E[xx|δδoi,t ].
2.2. ODOL Algorithm
Since the state and the observation noise are jointly Gaussian random parameters, we can
compute (5) through a Kalman-like recursion [19]. Therefore, we provide the following ODOL
6

o
 n
algorithm. We introduce a difference set ∆i,t := δoi,t \δoi,t−1 = yi,t , y j,t−1

j∈Ni(1)

n
o
, · · · , y j,t−κi

(κi )

j∈Ni

and a vector wi,t = col{∆i,t }. Then, for t ≥ 1 the iterations of the ODOL algorithm are given by


uoi,t = I − Ki,t H̄i uoi,t−1 + Ki,t wi,t ,

−1
Ki,t = Σ̂i,t−1 H̄iT H̄i Σ̂i,t−1 H̄iT + Σ̄ni ,


Σ̂i,t = I − Ki,t H̄i Σ̂i,t−1 ,


where2 uoi,0 = x̄, Σ̂i,0 = Σ x , H̄i := Pi ⊗ Iq H, H := col {H1 , · · · , Hm }, Σ̄ni :=

 
T

Pi ⊗ I p Σn Pi ⊗ I p , Σn := diag Σn1 , · · · , Σnm , and Pi is the corresponding permutation matrix.
We point out that this is a lower bound on the original cost function (1), i.e.,
T X
m
X

Ekxx − uoi,t k2 ≤

t=1 i=1

min

m
T X
X

γi, j,t ∈Γi,t ,ηi,t ∈Ωi,t ,
i=1,··· ,m; j∈Ni ;t=1,··· ,T t=1 j=1

Ekxx − η j,t (δ j,t )k2 ,

(6)

where we substitute team-optimal action (when r → ∞) uoi,t back into (4) and sum over t =
1, · · · , T and i = 1, · · · , m. However, the lower bound is not necessarily tight depending on r. By
Proposition 2.1, time-stamped information disclosure strategy, in which the size of the disclosed
information is q × m, yields the oracle solution. This implies that when r ≥ qm, the lower bound
is tight. Furthermore, team optimal solutions are linear in the available information and can
be constructed through the recursive algorithm ODOL. However, qm is linear in the number of
agents, m, and in large networks this can cause excessive communication load yet communication
load is crucial for the applicability of the distributed learning algorithms [14, 13]. Therefore, in
the following section, we provide a sufficient condition on the size of the disclosed information,
which depends on the network structure (rather than its size), in order to achieve the lower bound
(6).

3. Distributed-MMSE Estimation with Disclosure of Local Estimate
In the conventional distributed estimation algorithms, e.g., consensus and diffusion approaches, agents disclose their local estimates, which have size p (note that this does not depend
on the network size). The following example addresses whether the disclosure of local estimates
can achieve the lower bound (6) or not.
3.1. A Counter Example
Consider a cycle network of 4 agents as seen in Fig. 3, where p = q = 1, Hi = 1, Σni = σ2n , for
i = 1, · · · , 4, and Σ x = σ2x . We aim to show that agent-1’s oracle action at time t = 3, i.e., uo1,3 ,
cannot be constructed through the exchange of local estimates.

2 If

the inverse fails to exist, a pseudo inverse can replace the inverse [19].

7

1

2

3

4

Figure 3: A cycle network of 4 agents.
At time t = 2, agent-2 and agent-3 have the following oracle actions:
uo2,2 = E[xx|yy2,2 = y2,2 , y 2,1 = y2,1 , y 1,1 = y1,1 , y 4,1 = y4,1 ],
σ2x
(y2,2 + y2,1 + y1,1 + y4,1 ),
4(σ2x + σ2n )
= E[xx|yy3,2 = y3,2 , y 3,1 = y3,1 , y 1,1 = y1,1 , y 4,1 = y4,1 ].
=

uo3,2

=

σ2x
(y3,2 + y3,1 + y1,1 + y4,1 ).
4(σ2x + σ2n )

(7)

(8)

Note that since there are two hops between agents 2 and 3, at t = 2, agents do not have access to
each other’s any measurement yet. At time t = 3, agent-1’s oracle action is given by
uo1,3 = E[xx|yy1,3 = y1,3 , y 1,2 = y1,2 , y 1,1 = y1,1 ,
y 2,2 = y2,2 , y 2,1 = y2,1 ,
y 3,2 = y3,2 , y 3,1 = y3,1 ,
y 4,1 = y4,1 ],
=

σ2x
(y1,3 + y1,2 + y1,1 + y2,2 + y2,1 + y3,2 + y3,1 + y4,1 ).
+ σ2n )

8(σ2x

Assume that uo1,3 can be obtained through the exchange of local estimates:
û1,3 := E[xx|yy1,3 = y1,3 , y 1,2 = y1,2 , y 1,1 = y1,1 ,
u o2,2 = uo2,2 , u o2,1 = uo2,1 ,
u o3,2 = uo3,2 , u o3,1 = uo3,1 ].

(9)

Since all parameters are jointly Gaussian, the local estimates are also jointly Gaussian, û1,3 , is
linear in uo2,2 and uo3,2 . Furthermore, the measurements y2,2 , y3,2 , and y4,1 are only included in uo2,2
and uo3,2 . Therefore, we obtain
û1,3 = · · · + αuo2,2 + βuo3,2
= ··· + α

σ2x
σ2x
(y
+
y
+
·
·
·
)
+
β
(y3,2 + y4,1 + · · · ),
2,2
4,1
4(σ2x + σ2n )
4(σ2x + σ2n )

where · · · refers to the other terms. However, the equality of û1,3 and uo1,3 implies α = β = 1/2 due
to the combination weights of y2,2 and y3,2 , respectively, and α + β = 1/2 due to the combination
8

weight of y4,1 , which leads to a contradiction. Hence, which information to disclose over arbitrary
networks for team-optimal solutions should be considered elaborately. In the following, we
analytically show that lower bound could be achieved through the disclosure of local estimates
over “tree networks”.
3.2. Tree Networks
A network has a “tree structure” if its corresponding graph is a tree, i.e., connected and undirected without any cycles [20]. As an example, the conventional star or line networks have tree
structures. We remark that for an arbitrary network topology we can also construct the spanning
tree of the network and eliminate the cycles. In the literature, there exists numerous distributed
algorithms for minimum spanning tree construction [21, 22, 23, 24, 25].
Importantly, the following theorem shows that over tree networks we can achieve the performance of the oracle algorithm through the disclosure of the local estimates only.
Theorem 3.1: Consider the team-problem over a tree network, in which r = p. Then, exchange of local estimates can lead to the team-optimal solution, i.e., agents can achieve the
oracle performance.
Proof: Initially, agent-i has access to yi,1 only and the oracle action is uoi,1 = E[xx|yyi,1 = yi,1 ]. At
time t = 2, the oracle action is given by
 
n
o 
uoi,2 = E x | y i,τ = yi,τ τ=1,2 , y j,1 = y j,1
,
(10)
j∈Ni

which can be written as
 
uoi,2 = E x | y i,τ = yi,τ
 
= E x | y i,τ = yi,τ

n
o 
x
y
,
E[x
|y
=
y
]
,
j,1
j,1
τ=1,2
j∈Ni

n
o
o
o
.
τ=1,2 , u j,1 = u j,1
j∈Ni

(11)

This implies that for t = 1 and t = 2, the oracle performance can be achieved through the
disclosure of local estimate. Therefore, we can consider the oracle action (10) even though
agents disclose their local estimate instead of time-stamped information disclosure.
As seen in Fig. 4, over a tree network, for k ∈ {1, · · · , κi } we have
[

Ni(k) =
Ni(k) ∩ N (k−1)
.
(12)
j
j∈Ni

Note that the sets in (12) are disjoint as
 (k)
  (k)

Ni ∩ N (k−1)
∩ Ni ∩ N (k−1)
=∅
j1
j2

(13)

for all j1 , j2 ∈ Ni and j1 , j2 . Notably, over a tree network, by (13), we can partition the
collection set of the measurements received after at least k-hops as follows
(n o
n o
y j,τ
y j,τ
(k) =
(k)
(k−1) ,
j∈Ni ∩N j

j∈Ni

n o
· · · , y j,τ

1

)
j∈Ni(k) ∩N (k−1)
jπ
i

9

.

(14)

i1
(2)
i

i1

i5
i3 ,

i4 ,

i2

i

i2
i5

i4

i3

Figure 4: An example tree network. Notice the eliminated links from Fig. 1 to avoid multi path
information diffusion.
In the time-stamped information disclosure, at time t = 3, agent-i has access to δoi,3 , defined in
(2). We denote the set of new measurements received by i over j at time t = 2 by
=y j,2

∆oj,i,2

}|
{ 
nz

:= yk,2 k∈N (1) ∩N (0) , yk,1
i

j

k∈Ni(2) ∩N (1)
j

o
,

which can also be written as
=δo

∆oj,i,2

j,1
n z}|{
= δoj,2 \ y j,1 ,

o
yi,1
,
|{z}

(15)

=∆oi, j,1 =δoi,1

where we exclude the information sent by i to j at time t = 1, i.e., yi,1 . Then, we can write the
accessed information as the union of new measurement yi,3 , new measurements received over the
neighboring agents and the accessed information at time t = 2 as follows:
n
o
δoi,3 = yi,3 , ∆oj1 ,i,2 , · · · , ∆ojπ ,i,2 , δoi,2 .
(16)
i

Note that the sets on the right hand side of (16) are disjoint due to tree structure. Furthermore, by
(15) and (16), the sigma-algebra generated by δoi,3 is equivalent to the sigma-algebra generated
n
o
by the set {yi,τ }τ≤3 , {δoj,τ }τ≤2
. Since uoj,t = E[xx|δδoj,t = δoj,t ], we obtain
j∈Ni
 
uoi,3 = E x | y i,τ = yi,τ

τ≤3

n
oτ≤2 
, u oj,τ = uoj,τ
.
j∈Ni

(17)

By (15), we have
n
o
∆oj,i,t = δoj,t \ δoj,t−1 ∪ ∆oi, j,t−1 ,

(18)

which implies that for t ≥ 2, ∆oj,i,t is constructible from δoi,τ and δoj,τ for τ ≤ t. Hence, by induction,
we conclude that the lower bound can be achieved through the exchange of local estimates. 
10

Remark 3.1: When the expectation of the state is conditioned on infinite number of observations over even a constructed spanning tree, only a finite number of the observations is missing
compared to the case over a fully connected network. Hence, even if we construct the spanning
tree of that network, we would still achieve the lower bound over a fully connected (or centralized) network asymptotically. As an illustrative example, in Fig. 10, we observe that the MMSE
performance over the fully connected, star and line networks are asymptotically the same. Similarly, in [26, 27, 28], the authors show that the performance of the diffusion based algorithms
could approach the performance of a fully connected network under certain regularity conditions.
In the sequel, we propose the OEDOL algorithm that achieves the lower bound over tree
networks iteratively.
3.3. OEDOL Algorithm
By Theorem 3.1, over a tree network, oracle action can be constructed by
 
n
oτ≤t−1 
uoi,t = E x | y i,τ = yi,τ τ≤t , u oj,τ = uoj,τ
j∈Ni

(19)

through the disclosure of oracle actions, i.e., local estimates. We remark that uoi,t is linear in
the previous actions uoi,τ , τ ≤ t − 1. In order to extract new information, i.e., innovation part,
we need to eliminate the previously received information at each instant on the neighboring
agents. This brings in additional computational complexity. On the contrary, agents can just
send the new information compared to the previously sent information, e.g., si,t . Note that here
agents disclose the same information to the neighboring agents. Since we are conditioning on the
linear combinations of the conditioned variables without effecting their spanned space, i.e., si,t is
computable from uoi,τ for τ ≤ t and vice versa, agents can still achieve the oracle performance by
reduced computational load, yet.
At time t, agent-i receives local measurement yi,t and sent information from the neighboring
agents, ri,t := col{s j1 ,t−1 , · · · , s jπi ,t−1 }. We aim to determine the content of the received information ri,t to extract the innovation within them and utilize this innovation in the update of the oracle
action.
Initially, at time t = 1, agent-i has only access to the local measurement yi,1 . Then, the oracle
action is given by
uoi,1 = (I − Σ x Hi0 (Hi Σ x Hi0 + Σni )−1 Hi ) x̄ + Σ x Hi0 (Hi Σ x Hi0 + Σni )−1 yi,1 .
Let uoi,0 = x̄ and Σ̂i,0 = Σ x , and set Bi,1 = Σ̂i,0 Hi0 (Hi Σ̂i,0 Hi0 + Σni )−1 and Ai,1 = I − Bi,1 Hi . Then, we
obtain
uoi,1 = Ai,1 uoi,0 + Bi,1 yi,1 ,
Σ̂i,1 = Ai,1 Σ̂i,0 .
Next, instead of sending uoi,1 , agent-i sends to the neighboring agents, j ∈ Ni ,
si,1 = uoi,1 − Ai,1 uoi,0
= Bi,1 yi,1 .
11

Correspondingly, at time t = 2, agent-i receives yi,2 and ri,2 . Let r i,2 be the corresponding random
vector. Then, conditioning the state and the received information on the previously available
information y i,1 = yi,1 , we have
 o  

0
Σ̂i,1 Hi0
Σ̂i,1 H̄i,1
 x 
 ui,1   Σ̂i,1

y i,2 y
 Hi uoi,1  ,  Hi Σ̂i,1 Hi Σ̂i,1 Hi0 +Σni Hi Σ̂i,1 H̄i,10  ,
=
y
∼
N
i,1
i,1
r i,2
0
0
H̄ uo
H̄i,1 Σ̂i,1

i,1 i,1

n

where H̄i,1 := col B j1 ,1 H j1 , · · · , B jπi ,1 H jπi


col B j1 ,1 Σn j1 B0j1 ,1 , · · · , B jπi ,1 Σn jπi B0jπ ,1 .

o

H̄i,1 Σ̂i,1 Hi

and Ḡi,1

=

H̄i,1 Σ̂i,1 H̄i,1 +Ḡi,1

diag{Gi,1 }, where Gi,1

:=

i

Let H̃i,1 := col{Hi , H̄i,1 } and G̃i,1 := diag{Σni , Ḡi,1 } and set
h
i

−1
0
0
Bi,2 Ci,2 = Σ̂i,1 H̃i,1
H̃i,1 Σ̂i,1 H̃i,1
+ G̃i,1 ,

(20)

Ai,2 = I − Bi,2 Hi − Ci,2 H̄i,1 .
Then, we obtain
uoi,2 = Ai,2 uoi,1 + Bi,2 yi,2 + Ci,2 ri,2 ,

(21)

Σ̂i,2 = Ai,2 Σ̂i,1
and agent-i sends
si,2 = uoi,2 − Ai,2 uoi,1
X
( j)
= Bi,2 yi,2 +
Ci,2
B j,1 y j,1 ,
| {z }
j∈N
=s j,1

i

( j)
where Ci,2
denotes the corresponding jth block of Ci,2 . Therefore, at time t = 3, agent-i receives
from j ∈ Ni :
X
(i)
s j,2 = B j,2 y j,2 +
(C (k)
(22)
j,2 B j,1 y j,1 ) + C j,2 Bi,1 yi,1 .
k∈N j \i

Since the last term on the right hand side of (22) is known by i, we have
=H̄i,2

E[rr i,2 |δδoi,2

z
 B +P }| C (k) B {
 j1 ,2 k∈N j1 \i j1 ,2 k,2 

 o
o
..
 ui,2 + Di,2 si,1 ,
= δi,2 ] = 
.


P
B
+
C (k) B
jπi ,2

k∈N jπ \i
i

(23)

jπi ,2 k,2

(i)
where Di,2 := col{C (i)
j1 ,2 , · · · , C jπ ,2 }, and
i

Gi,2




= 


B j1 ,2 Σn j B0j
1

1 ,2

B jπi ,2 Σn jπ B0jπ
i

i

P
+ k∈N j

P
,2 + k∈N j

1

(k)
(k) 0
0
\i C j ,2 Bk,1 Σnk Bk,1 (C j ,2 )
1
1

πi

..
.

(k)
(k)
0
\i C jπ ,2 Bk,1 Σnk Bk,1 (C jπ ,2 )
i






0 

i

By (21), (23), and (24), the next oracle action uoi,3 is given by
uoi,3 = Ai,3 uoi,2 + Bi,3 yi,3 + Ci,3 (ri,3 − Di,2 si,1 ).
12

(24)

Subsequently, agent-i sends si,3 = uoi,3 − Ai,3 uoi,2 and the received information from j ∈ Ni yields


X
X


(k) 
(l)

s j,3 =B j,3 y j,3 +
C j,3  Bk,2 yk,2 +
Ck,2 Bl,1 yl,1 
l∈Nk \ j

k∈N j



X
X


(l)
(k) 

Ck,2 Bl,1 yl,1 
=B j,3 y j,3 +
C j,3  Bk,2 yk,2 +
l∈Nk \ j

k∈N j \i

+ C (i)
j,3



( j)
si,2 − Ci,2
s j,1



.

Then, H̄i,3 is given by
H̄i,3



= 

B j1 ,3 H j1 +C j1 ,3 H̄ j1 ,2

 
 
 − 
 

..
.

B jπi ,3 H jπi +C jπi ,3 H̄ jπi ,2

(i)
C (i)
j ,3 H̄ j ,2
1

..
.

1

(i)
C (i)
jπi ,3 H̄ jπi ,2




 .


(25)

Correspondingly, we have
Gi,3

 B Σ B0 +C Ḡ C 0
 j1 ,3 n j1 j1 ,3 j1 ,3 j1 ,2 j1 ,3

..
= 
.
 B Σ B0 +C
Ḡ
C0
jπi ,3 n jπ
i

jπi ,3

jπi ,3

jπi ,2

jπi ,3

 
 
 
 − 
 

(i)
(i) 0
C (i)
j ,3 G j ,2 (C j ,3 )
1

1

..
.

1




 .

0

(26)

(i)
(i)
C (i)
jπi ,3 G jπi ,2 (C jπi ,3 )

Therefore, the oracle action can be written as
uoi,4 = Ai,4 uoi,3 + Bi,4 yi,4 + Ci,4 (ri,4 − Di,3 si,2 + T i,3 ri,2 ),
where Ai,4 , Bi,4 , Ci,4 , Di,3 are defined accordingly and
 (i) ( j1 )
 C j1 ,3 Ci,2

..
T i,3 := 
.





 .

( jπ ) 

i
C (i)
jπ ,3 C i,2
i

Following identical steps, for t ≥ 1, the OEDOL algorithm is given by
uoi,t = Ai,t uoi,t−1 + Bi,t yi,t + Ci,t wi,t ,

(27)

Σ̂i,t = Ai,t Σ̂i,t−1 ,

(28)

where wi,t is the innovation term extracted from the received information, which evolves according to
wi,t = ri,t − Di,t−1 si,t−2 + T i,t−1 wi,t−2 .
(29)
The weighting matrices Ai,t , Bi,t , Ci,t , Di,t , and T i,t are defined by
h
i
T
Bi,t Ci,t = Σ̂i,t−1 H̃i,t−1
×

−1
T
H̃i,t−1 Σ̂i,t−1 H̃i,t−1
+ G̃i,t−1 ,
Ai,t = I − Bi,t Hi − Ci,t H̄i,t−1 ,
n
o
(i)
Di,t = col C (i)
,
·
·
·
,
C
jπi ,t
j1 ,t
 (i) ( j1 )

0 
 C j1 ,t Ci,t−1 ···

 .
..
 .
..
T i,t =  ..
.

.

(
j
)
πi 
0
··· C (i)
jπi ,t C i,t−1
13

(30)
(31)
(32)
(33)

where H̃i,t = col{Hi , H̄i,t }, G̃i,t = diag{Σni , Ḡi,t } and Ḡi,t = diag{Gi,t }. By (25) and (26), the
intermediate parameters H̄i,t and Gi,t evolve according to


H̄i,t = 

B j1 ,t H j1 +C j1 ,t H̄ j1 ,t−1

..
.

B jπi ,t H jπi +C jπi ,t H̄ jπi ,t−1

 
 
 − 
 

(i)
C (i)
j ,t H̄ j ,t−1
1

(i)
C (i)
jπi ,t H̄ jπi ,t−1

 B Σ BT +C Ḡ C T
 j1 ,t n j1 j1 ,t j1 ,t j1 ,t−1 j1 ,t

..
Gi,t = 
 B Σ BT +C. Ḡ
CT
jπi ,t n jπ
i

jπi ,t

jπi ,t

jπi ,t−1

..
.

1

jπi ,t

 
 
 
 − 
 




 ,


(34)


T
(i)
(i)
C (i)
j ,t G j ,t−1 C j ,t
1

1

(i)
C (i)
jπ ,t G jπ
i

i

..
.

1


(i)
,t−1 C jπ

i ,t






T 


(35)

and we initialize the parameters as H̄ j,τ = 0 and G j,τ = 0 for τ < 1.Then, agent-i sends
si,t = uoi,t − Ai,t uoi,t−1 .
The detailed description of the algorithm is provided in Table 1.
3.4. Computational Complexity
In (27), the combination matrices Ai,t , Bi,t , Ci,t , Di,t−1 , and T i,t−1 are independent of the
streaming data although they are time-varying. Hence they can be computed before-hand. In
that case, the computational complexity of the iterations for each agent is dominated by the
term Ci,t wi,t . Therefore, the average computational complexity is on the order of p2 π2 , where
P
2 2
2
π2 := 1/m m
i=1 πi , i.e., O(p π ). Otherwise, the computational complexity of the algorithm is
mainly dominated by the matrix inversion in (30), note that Ḡi,t ∈ R pπi ×pπi , unless the network
is sparsely connected, i.e., πi  m for i = 1, · · · , m. Therefore, over a non-sparse network, the
average complexity is on the order of mp3 π3 (π3 is defined accordingly) since each
agent
 i com
putes B j,t and C j,t for j = 1 · · · , m. In particular, the complexity is given by O mp3 π3 , while it


is O (qm)3 for the ODOL algorithm. Note that over tree networks, we have m − 1 edges and
correspondingly average neighborhood size is small. Hence, disclosure of local estimates over
tree networks also reduces the computational complexity compared to the time-stamped disclosure strategy in general (in addition to the substantial reduction in communication). In Table 2,
we tabulate the computational complexities of the introduced algorithms.
We point out that diffusion or consensus based algorithms have relatively low complexity, i.e.,
on the order of p2 in the least-mean-square based algorithms and on the order of p3 in quasiNewton based algorithms, since exchanged information is handled irrespective of the content.
Such algorithms also present appealing performance for certain applications in addition to the
low computational complexity. However, they do not achieve the oracle performance.
In the following, we analyze whether the agents can still achieve the oracle performance
through the exchange of local estimates over the networks not in tree structure.
3.5. Tree Networks Involving Cell Structures
While constructing the spanning tree, we cancel certain communication links in order to avoid
multi-path information propagation. However, we also observe that in a fully connected network
agents can achieve the oracle performance through the disclosure of local observations. In particular, since all of the agents are connected, each agent can receive the observations across the
14

Table 1: The description of the OEDOL algorithm.
Algorithm: The OEDOL Algorithm
Initialization:
For i = 1 to m do
uoi,0 = x̄, Σ̂i,0 = Σ x ,
H̄i,τ = 0, Gi,τ = 0, and wi,τ = 0 for τ < 1
End for
Iterations:
Do for t ≥ 1
For i = 1 to m do
Construction of Weights:
For j = 1 to m do
Calculate H̄ j,t and G j,t by (34) and (35).
Determine combination matrices via (30), (31), (32), and (33).
End for
Construct ri,t through received s j,t−1 for j ∈ Ni
Extraction of Innovation:
wi,t = ri,t − Di,t−1 si,t−2 + T i,t−1 wi,t−2
Update:
uoi,t = Ai,t uoi,t−1 + Bi,t yi,t + Ci,t wi,t
Σ̂i,t = Ai,t Σ̂i,t−1
Disclose si,t = uoi,t − Ai,t uoi,t−1 to the neighbors.
End for
Table 2: A comparison of the computational complexities of the proposed algorithms.

Algorithm
ODOL algorithm
OEDOL algorithm

Without weights


O (qm)3


O mp3 π3

Pre-computed weights


O (qm)2


O p2 π2

network directly. Correspondingly, in a fully connected network, we can achieve identical performance with the ODOL algorithm only through the disclosure of the local estimates as stated
in the following corollary formally.
Corollary 3.1: Consider the team-problem over a fully connected network, in which r = p.
Then, exchange of local estimates can lead to the team-optimal solution, i.e., agents can achieve
the oracle performance.
15

Proof: Over a fully connected network, κi = 1 and the oracle action is given by
#
uoi,t = E[xx|{yyi,τ = yi,τ }τ≤t , {yy j,τ = y j,τ }τ≤t−1
j∈Ni

(36)

and we can also obtain (36) by (11) since we have
∆oj,i,t = δoj,t \ {δoi,t \ {yi,t }},
which implies that ∆oj,i,t is constructible from δoi,τ and δoj,τ for τ ≤ t. The proof is concluded. 
We point out that the team-optimal strategies can fail if a link or node failure occurs. However,
once a link failure is detected, team-optimal strategies can be recomputed by eliminating the
failed link in the new network configuration. Hence, through such strategies, we can increase the
robustness of the team against link and node failures.
We define a “cell structure” as a sub-network in which all agents are connected to each other.
Intuitively, considering a cell structure as a “single” agent, the cell (i.e., all the agents in the cell)
can be involved in the tree such that the agents can still achieve the oracle performance through
the disclosure of local estimates (although there may be loops in the cell). We list the features of
the cell structures, e.g., seen in Fig. 5, as follows:
• Agents out of a cell can connect to at most one of the agents within that cell.
• A cell structure consists of at least 2 agents.
• An agent can belong to more than one cell.
• Two different agents cannot belong to more than one cell at the same time.
• All of the agents belong to at least a cell in a connected network.
• Each agent has also the knowledge of the cells of the other agents.
• Each agent labels its cells from its own and its first order neighbor’s point of view. As an
example, for agent-i, Ci,i1 denotes the cell involving both i and i1 . Note that if the same cell
also includes i2 , Ci,i1 = Ci,i2 .
The following theorem shows that agents can achieve the oracle performance over tree networks involving cell structures through the disclosure of the local estimates.
Theorem 3.2: Consider the team problem over tree networks involving cell structures. Then,
exchange of local estimates can lead to the team-optimal solution, i.e., agents can achieve the
oracle performance.
Proof: Initially, we have ∆oj,i,1 = δ j,1 = {y j,1 } and the oracle action is also given by (11)
over this network topology. Note that the information received by j at t = 2 is given by δoj,2 =
=∆ok, j,0
)
(
o
n z}|{
o
, δ j,1 , which yields
y j,2 , yk,1
k∈N j

∆oj,i,2







[




o
o
= δ j,2 \ 
δ j,1 ∪
yk,1 
,






k∈Ci, j






[


 o
o 
= δoj,2 \ 
δ
∪
∆

j,1
k,
j,1






k∈Ci, j
16

Ci,i
Ci,i
Ci,i

1

i2

i1

i3

i

i4

i5

2

3

Ci,i

i6

4

Ci,i5 ,Ci,i6
Figure 5: An example tree network involving cell structures.
and ∆oj, j,t = ∅ by definition. Due to the cell structure, we have
[
[
∆ok, j,1 = ∆oi, j,1 ∪
∆ok,i,1 ,
k∈Ci, j \ j

k∈C j,i

=

δoi,1

∪

[

δok,1 .

k∈Ci, j \ j

Correspondingly, for t > 0 we have
∆oj,i,t

=

δoj,t







[


 o

o
o
\
δ
∪
∆
∪
∆

j,t−1
i,
j,t−1
k,i,t−1






k∈Ci, j \ j

(37)

and ∆oj,i,t is constructible by the sets δoi,τ and δoj,τ for j ∈ Ni and τ ≤ t. Note that over tree networks,
Ci, j \ j = ∅ for i = 1, · · · , m, j ∈ Ni , and (37) leads to (18). Hence, for t > 0 we obtain (19) and
the proof is concluded.

Note that the network can have loops within the cell structures and agents can still achieve the
oracle performance through the diffusion of the local estimates. This increases the robustness of
the team strategies against the link failures. In the sequel, we provide the sub-optimal extensions
of the algorithms for practical applications.
4. Sub-optimal Approaches
Minimization of the cost function (4) optimally requires relatively excessive computations.
We aim to mitigate the problem sub-optimally yet in a computationally efficient approach while
achieving comparable performance with the optimal case. As an example, we can approximate
the cost measure (4) through T o ≥ max{κi }i=1,··· ,m size time-windowing as follows
T
X
t=1

s
min Ekxx − ηi,t (δi,t
)k2 ,

s
ηi,t ∈Ωi,t

17

(38)

Current Time-Window

t

t!

To

t

i

1

t

time

N i( 0)
N i(1)

s

ui,t

N i( 2)
!
N i(

!

!

!
ri,t

i)

Currently received data

u

s
i ,t 1

mt-To

mt-

e
ui,t1

i

(Extracted information)

Figure 6: Information aggregation illustration. Small squares represent the information across
the agents in the corresponding neighborhood and time.
where agent-i has the information set

n ot−To <τ≤t−1
n ot−To <τ≤t−κi 
s
δi,t
:= yi,τ t−To <τ≤t , y j,τ
,
·
·
·
,
y j,τ
,
(κi )
(1)
j∈Ni

(39)

j∈Ni

s
s
if t ≥ T o and other cases are defined accordingly, σi,t
is the sigma-algebra generated by δi,t
, and
κi

s
-measurable functions from Rqκ × Rqπi (κ−1) × · · · × Rqπi
Ωoi,t denotes the set of all σi,t
Then, team-optimal action is given by

(κ−κi )

to R p .

s
s
s
ui,t
= E[xx|δδi,t
= δi,t
],
s
where δ i,t
is the set of corresponding random parameters.
In Fig. 6, we illustrate the time-windowing approach for time stamped information disclosure.
We define a memory element mt denoting the expectation of the state conditioned on all measurement at time t, i.e., mt := E[xx|{yyi,t = yi,t }m
i=1 ]. We consider that x̄ = 0. Then, we can write
mt = Myt , where M := Σ x H 0 (HΣ x H 0 + Σn )−1 and yt := col{y1,t , · · · , ym,t }.
s
Let uei,t−1 represent the extracted information from the estimate ui,t−1
via the memory element
mt−To , i.e.,
#
"
t−T o +1<τ≤t−κi −1
t−T o +1<τ≤t−1
e
, · · · , {yy j,τ = y j,τ } (κi )
ui,t−1 := E x {yyi,τ = yi,τ }
j∈Ni

if t ≥ T o and other cases are defined accordingly. Then, we can write uei,t−1 = Ni yei,t−1 , where
−1

and yei,t−1 is the vector collecting the measurements within that
Ni = Σ x Ĥi0 Ĥi Σ x Ĥi0 + Σ̂ni
window (See Fig. 6). Additionally, we define
o
n
Ĥi := col Hi , Hi , Hi(1) , Hi , Hi(1) , Hi(2) , · · · , Hi , Hi(1) , · · · , Hi(κi )
18

n o
and Hi(k) := col H j

j∈Ni(k)

. Correspondingly, we have

n
o
(1) (2)
(1)
(κi )
Σ̂ni := diag Σni , Σni , Σ(1)
ni , Σni , Σni , Σn,i , · · · , Σni , Σni , · · · , Σni
n o
and Σ(k)
ni := diag Σn j

j∈Ni(k)

. Therefore, for t ≥ T o , we have
s
= E[xx|uuei,t−1 = uei,t−1 , m t−To = mt−To ].
ui,t−1

mt−To = mt−To ] = mt−To and Σ̂ := E[(xx − mt−To )(xx − mt−To )0 ] = Σ x H 0 (HΣH 0 +
Note that E[xx|m
−1
Σn ) HΣ = (I − MH)Σ. Then, the distribution of x and u ei,t−1 conditioned on m t−To = mt−To is
given by
h


h x i
mt−To i
Σ̂
Σ̂Ĥi0 Ni0
mt−To = mt−To ∼ N Ni Ĥi mt−T
,
uei,t−1 |m
N Ĥ Σ̂ N Ĥ Σ̂Ĥ 0 N 0 +N Σ̂ N 0
o
i

i

i

i

i

i

i ni

i

and we obtain
s
ui,t−1
= mt−To + Σ̂Ĥi0 Ni0 (Ni Ĥi Σ̂Ĥi0 Ni0 + Ni Σ̂ni Ni0 )−1 (uei,t−1 − Ni Hi mt−To )

= Ki mt−To + Li uei,t−1 ,

(40)

where
Li := Σ̂Ĥi0 Ni0 (Ni Ĥi Σ̂Ĥi0 Ni0 + Ni Σ̂ni Ni0 )−1 ,
Ki := I − Li Ni Ĥi .
s
s
s
Next, we aim to compute ui,t
through ui,t−1
and δi,t
= {yei,t−1 , yi,t , ri,t }, where ri,t is a vector
consisting of currently received measurements as seen in Fig. 6. Let H̄i := col{Hi , Hi(1) , · · · , Hi(κi ) }
(κi )
x − uei,t−1 )(xx − uei,t−1 )0 ] = Σ x Ĥi0 (Ĥi Σ x Ĥi0 + Σ̂n )−1 Ĥi Σ x =
and Σ̄i := col{Σni , Σ(1)
ni , · · · , Σni }. Since E[(x
(I − Ni Ĥi )Σ x , we have
h y i

s
ui,t
= uei,t−1 + Σ x,i H̄i0 (H̄i Σ x,i H̄i0 + Σ̄ni )−1 ri,ti,t − H̄i uei,t−1 ,
s
where Σ x,i := (I − Ni H̄i )Σ x . By (40), uei,t−1 = Li−1 (ui,t−1
− Ki mt−To ), and we define the combination
matrices
h
i

−1
Bi Ci = Σ x,i H̄iT H̄i Σ x,i H̄iT + Σ̄ni ,
(41)
 h
i 
Ai := I − Bi Ci H̄i Li−1 ,
(42)

Di := Ai Ki M.

(43)

Therefore, for t ≥ T o , the sub-optimal distributed online learning (SDOL) algorithm is given by
s
s
ui,t
= Ai ui,t−1
+ Bi yi,t + Ci ri,t − Di yt−To .

(44)

In the following we provide several remarks about the practical implementation of the SDOL
algorithm.
Remark 4.1:
19

• We point out that in the update (44) the matrices Ai , Bi , Ci , and Di are independent from
the data and they are time invariant for t ≥ T o . Hence, they can be pre-computed and
installed onto the agents. Then, the SDOL algorithm basically takes the linear average of
the previous estimate, the current measurement and received data, and measurements at
time t − T o .
• Different from the conventional approaches, the SDOL algorithm requires to memorize previous observations. Note that if q < p/m, storing measurements individually rather than a
linear combination, i.e., mt , might be more efficient in terms of memory usage.
• The computational complexity of the SDOL algorithm is O(p2 +2pmq) (or say O(p2 ) for q 
p/m) due to matrix-vector multiplications in (44), and the algorithm requires disclosure of
a data vector with (m − 1) × q dimensions.
• Finally, even though agent-i uses update (44) for t < T o assuming that3 y j,τ = 0 for j =
1, · · · , m and τ < 1, we have

−1
s 0
s
E[(x − ui,τ
) (x − ui,τ
)] = Σ x,i − Σ x,i H̄iT H̄i Σ x,i H̄iT + Σ̄ni H̄i Σ x,i
= Ai Li Σ x,i

(45)

for τ ≥ T o since at each iteration, agent-i excludes the impact of yt−To on
This sharp
change results in as a breaking point on the learning curve as seen in Fig. 15.
s
ui,t
.

In Table 3, we tabulate a detailed description of the SDOL algorithm. Note that SDOL algorithm is based on the aggregation of information. Correspondingly, we can apply the timewindowing approach to the disclosure of local estimates and formulate a sub-optimal efficient
distributed online learning algorithm (SEDOL) over tree networks.
In the sequel, we also provide illustrative simulations showing the enhanced tracking performance due to the proposed algorithm over several distributed network scenarios.
5. Illustrative Examples
In this section, we examine the performance of team optimal actions under different scenarios
through numerical examples. To this end, we consider three main network structures, namely
fully connected, star, and line networks with m = 20 agents, and a randomly generated network
seen in Fig. 7. In a fully connected network, each agent has a connection with each other and
any new measurement can be collected at each other after just one hop. This is the best possible
connection such that the corresponding achievable team cost is the smallest. In a star network,
there exists a pseudo-centralized agent, e.g., agent-1 in Fig. 7b, and all the other agents are
connected to that agent. Therefore, the furthest distance between any two agents is 2, e.g., there
exist 2-hops between agent-2 and agent-3 (agent-2 to agent-1 then agent-1 to agent-3) in Fig. 7b.
We have generated the network in Fig. 7c randomly such that number of neighbors of agent-i, πi ,
is chosen uniformly between 2 to 10. Therefore, the generated network can have loops, i.e., may
not be a tree. Furthermore, in a line network, the connections between the agents form a line as
seen in Fig. 7d. Contrary to the fully connected network, a line network has the least possible
connection such that any two agents are connected via a certain number of hops. Note that there
exist m − 1 = 19 hops between agent-1 and agent-2 in Fig. 7d.
3 The

action is no more team-optimal because of the assumption.

20

Table 3: The description of the SDOL-T o algorithm.
Algorithm: The SDOL-T o algorithm
Initialization:
s
= 0 for all i
ui,0

yi,τ = 0 for τ < 1 and all i
Calculate combination matrices via (41), (42) and (43).
Update:
Do for t ≥ 1
For i = 1 to m do
Construct ri,t through received s j,t−1 for j ∈ Ni .
Store ri,t and yi,t in the memory accordingly.
s
s
ui,t
= Ai ui,t−1
+ Bi yi,t + Ci ri,t − Di yt−To .

Erase yt−To from the memory.
Diffuse si,t to the neighboring agents.
End for
We analyze the performance of a team of agents over those network structures. We set p = 10,
q = 1, x̄ = 0, Σ x = I, and the standard deviation of the zero-mean measurement noise is
chosen randomly from a folded normal distribution as seen in Fig. 8. Furthermore, we choose
Hi randomly from normal distribution, N(0, I). In order to observe the change of oracle cost
(r → ∞) for different time horizons, we introduce
J(T ) =

min

T X
m
X

ηi,t ∈Ωi,t ,
i=1,··· ,m,t=1,··· ,T t=1 i=1

Ekxx − ηi,t (δoi,t )k2 ,

(46)

which is a function of the length of time horizon, T . We re-emphasize that in (46), each action
at t = 1, · · · , T has a cumulative impact on the cost. Let ηoi,t , for i = 1, · · · , m and t = 1, · · · , T ,
be the oracle strategies for J(T ). Then, we introduce a terminal cost function defined by
P(T ) =

m
X

Ekxx − ηoi,T (δoi,T )k2 ,

(47)

i=1

which is the impact of final action on J(T ).
In Fig. 9, we compare J(T ), for T = 1, · · · , 20, over the fully connected, star, arbitrary, and
line networks in Fig. 7 by ensemble averaging empirical cost of the ODOL algorithm over 100
independent trials. Note that if the associated network is a tree network, e.g., the star network
is a tree, the same cost could be attained through the OEDOL algorithm as shown analytically
in Section 3. We point out that Fig. 9 is not a time evolution of a learning algorithm. In particular, for each time horizon T , we compare the corresponding oracle cost over certain networks.
As pointed out before, because of the most possible connection between the agents, the fully
connected network results in the least oracle cost for each time horizon T while the line network possesses the largest cost. Additionally, because of the cumulation of the impact of the
21

7

6

5

8

7
4

9

3

10

11

12

20

11

1

12

19

16

3

2

20

13

18
15

19
14

17

7

6

7
4

9

10

11

12

20

19

16

17

(c) Arbitrary network

5
4
3

10

1

15

6

9

2

18

17

8
3

13

16

(b) Star network

5

14

18
15

(a) Fully connected network

8

4

10

1

14

5

9

2

13

6

8

2

11

1

12

20

13

19
14

18
15

16

17

(d) Line network

Figure 7: Different network configurations.

actions at each time, for larger time horizon the corresponding oracle cost is also larger, i.e.,
J(T ) is a non-decreasing function of T (indeed increasing function since measurement noise is a
white process). The arbitrary network is relatively more connected. In particular, in the arbitrary
network, neighborhood size of agents is chosen uniformly between 2 and 10 while in the star
network, neighborhood size of agents except agent-1 is 2. We observe that oracle cost over the
arbitrary network is smaller than the oracle cost over the star network. For T = 1, all network
configurations lead to the same oracle cost since agents can exchange information beginning at
time t = 2. Furthermore, in Fig. 9, for time horizon T = 2, the oracle cost in the star network
is larger than the cost in the line network. This is because even though in the star network any
two agents are connected through at most 2 hops, over a horizon T = 2, the information can
only propagate over 1 hop and in the line network all the agents except agents 1 and 2 have 2
neighbors each. For horizon T > 2, the information can now propagate over more than 1 hop
and correspondingly, the cost in the star network is less than the cost in the line network.
In addition to the comparison of oracle cost, J(T ), for different time horizons over certain
networks, in Fig. 10, we compare the terminal cost, P(T ), in order to observe the cumulative
22

Statistical profile across the network
Standard deviation, σn

i

3.5
3

2.5
2
1.5
1
0.5
0

2

4

6

8

10
12
Agent Index, i

14

16

18

20

Figure 8: Standard deviation of measurement noise across the network.

Team cost for different time horizons T=1,...,20
900
800

Full
Star
Arbitrary
Line

700

Team Cost, J(T)

600
500
400
300
200
100
0

0

5

10
Horizon, T

15

20

Figure 9: Comparison of oracle cost for different time horizons over certain networks.

impact of the actions in the beginning stages of the horizon, e.g., t  T . We again ensemble
averaged empirical cost of the ODOL algorithm over 100 independent trials. Even though a
line and a fully connected network are two extreme connections for a network, in Fig. 10, the
terminal costs, P(T ), are asymptotically, as T → ∞, the same. We recall that this is pointed out
in Remark 3.1 and attributed to the negligible difference between the available information at
each agent over fully connected and line networks as the information sets grow. We also point
out that in the zoomed-out plot, for T = 2, the terminal cost in the star network is larger than the
terminal cost in the line network while the terminal cost in star network becomes substantially
smaller for larger T as explained above for Fig. 9.
23

Terminal cost for different time horizons T=1,...,200
25
Full
Star
Arbitrary
Line

20
Terminal Cost in dB, 10log(P(T))

Star Network
15

Fully
connected
Network

10

Line Network
5
0
Arbitrary Network
−5
−10
−15

0

50

100
Horizon, T

150

200

Figure 10: Comparison of terminal cost for different time horizons over certain networks.

Importantly, in Figs. 9 and 10, the oracle and terminal costs lead to counter-intuitive results
as time horizon grows. In particular, while the oracle costs over different networks are separated
as time horizon grows, the terminal costs converge to each other. The cumulation of the costs
of each action plays a significant role in these distinct results. By yielding relatively large cost,
the actions in the early stages have crucial impact on the team cost. Therefore, the sequential
algorithms aiming to learn the underlying state in time through a trial and error based approach
lead to larger team cost over horizon since trials at early stages lead to significantly large costs.
In the following, we analyze such circumstances.
We consider a randomly generated network in Fig. 11a, constructed as the network in Fig.
7c. This network is not a tree and has loops. We construct a spanning tree of this network,
see Fig. 11b, based on the paths from the agent having the largest neighborhood size, i.e., i =
arg max j π j , and then eliminating the multi-paths [21]. The statistical profile of the measurement
noise is plotted in Fig. 12. Here, we consider the diffusion recursive least squares (D-RLS)
algorithm [29] with Laplacian combination rule [30] for the incremental update and relativevariance combination rule for the spatial update. In D-RLS, agents use a recursive least squares
(RLS) update locally, diffuse local estimate to the neighbors at each time instant, and combine
received estimates and the local one linearly through certain combination weights, e.g., agent-i
has the weight λi, j for the information received from the neighbor- j:

σ−2

nj


 P
if j ∈ Ni ∪ {i}
−2
λi, j = 
k∈Ni ∪{i} σnk


 0
otherwise.
24

(48)

6

7

5

7

8

4

9

3

10

11

12

3

2

11

20

1

12

20

19

13

18
15

19
14

17

16

4

10

1

14

5

9

2

13

6

8

18
15

(a) Arbitrary network

16

17

(b) Corresponding spanning tree

Figure 11: An arbitrary network and a corresponding spanning tree.
Statistical profile across the network
Standard deviation, σn

i

2
1.5
1
0.5
0

2

4

6

8

10
12
Agent Index, i

14

16

18

20

Figure 12: Standard deviation of measurement noise across the network in Fig. 11.

In Fig. 13, we compare the ensemble average of the empirical-cost (over 100 independent trials) of the ODOL and D-RLS algorithms over Fig. 11a and the OEDOL algorithm over Fig. 11b
for different time horizon. Note that in the OEDOL algorithm, agents exchange local estimates
while in the ODOL algorithm, agents exchange information through time-stamped approach.
The OEDOL algorithm can achieve the oracle performance over a tree network. Therefore,
we construct a spanning tree of the arbitrarily generated network and the OEDOL algorithm
achieves the oracle performance of the spanning tree. Since we eliminate certain links while
constructing the spanning tree, the oracle performance, i.e., team-cost, is worse than the oracle
performance over the original network. However, even though the OEDOL algorithm operates
over the spanning tree, the algorithm has performed better than the D-RLS algorithm operating
over the original network. Additionally, in Fig. 14, we compare the terminal cost of the algorithms for larger time horizon, e.g., T = 1, · · · , 4000. We observe that even though the OEDOL
algorithm operates over the spanning tree, the terminal costs of the ODOL and OEDOL algorithms are close to each other for large time horizon, e.g., T > 40. We also note that as T → ∞,
the terminal cost decreases since noise processes are white.
Finally, in Fig. 15 we examine the impact of the time-windowing depth, e.g., T o = 50, 100,
on the terminal cost for different time horizon over an arbitrarily generated network of 20 agents
25

Team cost for different time horizons T=1,...,20
1000
D−RLS
OEDOL
ODOL

900
800

Team Cost, J(T)

700
600
500
400
300
200
100
0

0

5

10
Horizon, T

15

20

Figure 13: Comparison of team cost of the algorithms for different time horizon.
seen on the upper-right of Fig. 15. We note out that for T < T o , the terminal cost of the SDOL
algorithms differs from the terminal cost of the ODOL algorithm, i.e., the oracle performance
since in the SDOL algorithms, agents uses the update (44) for t < T o assuming that all measurements y j,τ = 0 for j = 1, · · · , m and τ < 1. As also pointed out in Remark 4.1, by excluding the
impact of these measurements on the future actions through sliding time-window, the terminal
cost of the SDOL-T o algorithm eventually reaches the terminal cost of the ODOL algorithm at
T = T o and for larger time window, this performance is maintained. Furthermore, depending on
the time window depth T o , the agents can achieve smaller terminal cost.
6. Conclusion
Distributed algorithms have attracted significant attention due to their wide spread applicability to highly complex structures from biological systems to social and economical networks.
However, there are still challenges for disclosure and utilization of information among agents.
We have considered this problem as a team problem, in which each agent takes actions, e.g.,
which information to disclose and how to construct the local estimate. We introduced the ODOL
algorithm achieving the oracle cost for Gaussian state and noise statistics through a time-stamped
approach. Importantly, we have shown that the exchange of the local estimates is sufficient to
achieve the oracle cost only over certain network topologies, e.g., over the introduced tree networks involving cell structures. Furthermore, we have introduced the OEDOL algorithm, which
achieves the oracle cost through the exchange of local estimates over tree networks. Finally,
26

Terminal cost for different time horizons T=1,...,4000
25
25
20
Terminal Cost in dB, 10log(P(T))

D−RLS
15
OEDOL

10

ODOL

5
−5
0

0

40

−5

D−RLS

−10
−15
OEDOL
−20
−25

ODOL
0

500

1000

1500

2000
2500
Horizon, T

3000

3500

4000

Figure 14: Comparison of terminal cost of the algorithms for different time horizon.
we have introduced a time-windowing approach for practical applications due to reduced complexity. The sub-optimal approaches possess recursive updates with time-invariant combination
weights that should be calculated only once.
Some future directions of research on this topic include team problems for distributed MMSE
estimation of a dynamic state and formulation of optimal information exchange in team decision
problems for linear continuous-time systems [31].
7. Acknowledgments
This work is supported in part by TUBITAK Contract No 115E917, in part by the U.S. Office
of Naval Research (ONR) MURI grant N00014-16-1-2710, and in part by NSF under grant CCF
11-11342.
References
References
[1] M. K. Banavar, J. J. Zhang, B. Chakraborty, H. Kwon, Y. Li, H. Jiang, A. Spanias, C. Tepedelenlioglu,
C. Chakrabarti, A. P.-Suppappola, An overview of recent advances on distributed and agile sensing algorithms
and implementation, Digital Signal Processing 39 (2015) 1–14.
[2] A. H. Sayed, S.-Y. Tu, J. Chen, X. Zhao, Z. J. Towfic, Diffusion strategies for adaptation and learning over networks:
An examination of distributed strategies and network behavior, IEEE Signal Processing Magazine 30 (3) (2013)
155–171.

27

Terminal cost for diffe0rent time horizons T=1,...,4000

Average Terminal Cost in dB, 10 log(P(T)/m)

10

7

6

5

8

0

4

9

3

10

2

11

D−RLS

−10

1

12

20

13

SDOL−50

19
14

18
15

16

17

−20

SDOL−100

−30

ODOL

−40

−50

0

500

1000

1500

2000
2500
Horizon, T

3000

3500

4000

Figure 15: Comparison of terminal cost of the SDOL-50 and SDOL-100 algorithms.

[3] S. Kar, J. M. F. Moura, Consensus+innovations distributed inference over networks: Cooperation and sensing in
networked systems, IEEE Signal Processing Magazine 30 (3) (2013) 99–109.
[4] J. Fernandez-Bes, L. A. Azpicueta-Ruiz, J. Arenas-Garcia, M. T. M. Silva, Distributed estimation in diffusion
networks using affine least-squares combiners, Digital Signal Processing 36 (2015) 1–14.
[5] V. Krishnamurthy, Decentralized activation in sensor networks-global games and adaptive filtering games, Digital
Signal Processing 21 (5) (2011) 638–647.
[6] A. Jadbabaie, P. Molavi, A. Sandroni, A. Tahbaz-Salehi, Non-Bayesian social learning, Games and Economic
Behavior 76 (1) (2012) 210–225.
[7] D. Acemoglu, A. Ozdaglar, Dynamic games and applications, Opinion dynamics and learning in social networks
1 (1) (2011) 3–49.
[8] M. Jackson, Social and Economic Networks, Princeton University Press, Princeton, N.J., 2008.
[9] C. G. Lopes, A. H. Sayed, Diffusion least-mean squares over adaptive networks: Formulation and performance
analysis, IEEE Transactions on Signal Processing 56 (7) (2008) 3122–3136.
[10] F. S. Cattivelli, A. H. Sayed, Diffusion strategies for distributed Kalman filtering and smoothing, IEEE Transactions
on Automatic Control 55 (9) (2010) 2069–2084.
[11] S. Shahrampour, A. Rakhlin, A. Jadbabaie, Online learning of dynamic parameters in social networks, in: Neural
Information Processing Systems, 2013, pp. 2013–2021.
[12] G. Mateos, I. D. Schizas, G. B. Giannakis, Distributed recursive least-squares for consensus-based in-network
adaptive estimation, IEEE Transactions on Signal Processing 57 (11) (2009) 4583–4588.
[13] M. O. Sayin, S. S. Kozat, Single bit and reduced dimension diffusion strategies over distributed networks, IEEE
Signal Processing Letters 20 (10) (2013) 976–979.
[14] M. O. Sayin, S. S. Kozat, Compressive diffusion strategies over distributed networks for reduced communication
load, IEEE Transactions on Signal Processing 62 (20) (2014) 5308–5323.
[15] V. D. Blondel, J. M. Hendrickx, A. Olshevsky, J. N. Tsitsiklis, Convergence in multiagent coordination, consensus,
and flocking, in: Proceedings of 44th IEEE Conference on Decision and Control (CDC-ECC), 2005, pp. 2996–
3000.
[16] D. S. Scherber, H. C. Papadopoulos, Locally constructed algorithms for distributed computations in ad-hoc net-

28

works, in: Proceedings of Information Processing Sensor Networks (IPSN), 2004, pp. 11–19.
[17] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller, Equation of state calculations by fast
computing machines, The Journal of Chemical Physics 21 (6) (1953) 1087–1092.
[18] A. H. Sayed, Fundamentals of Adaptive Filtering, Wiley, New York, 2003.
[19] B. D. O. Anderson, J. B. Moore, Optimal Filtering, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1979.
[20] S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, AddisonWesley, Reading, MA, 1990.
[21] B. Y. Wu, K.-M. Chao, Spanning Trees and Optimization Problems (Discrete Mathematics and Its Applications),
CRC Press, New York, 2004.
[22] R. G. Gallager, P. A. Humblet, P. M. Spira, A distributed algorithm for minimum-weight spanning trees, ACM
Transactions on Programming Languages and Systems 5 (1) (1983) 66–71.
[23] D. Peleg, Distributed Computing: A Locality-Sensitive Approach, SIAM, Philadelphia, PA, 2000.
[24] M. Elkin, Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning
tree problem, in: Proceedings of 36th ACM Symposium on Theory of Computing (STOC), 2004, pp. 331–340.
[25] M. Khan, G. Pandurangan, V. S. A. Kumar, Distributed algorithms for constructing approximate minimum spanning
trees in wireless sensor networks, IEEE Transactions on Parallel and Distributed Systems 20 (1) (2009) 124–139.
[26] J. Chen, A. H. Sayed, Optimal combination rules for adaptation and learning over networks, in: Proceedings of
50th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2012, pp. 1535–1542.
[27] J. Chen, A. H. Sayed, On the learning behavior of adaptive networks - Part II: transient analysis, IEEE Transactions
on Information Theory 61 (6).
[28] J. Chen, A. H. Sayed, On the learning behavior of adaptive networks - Part II: performance analysis, IEEE Transactions on Information Theory 61 (6).
[29] F. S. Cattivelli, C. G. Lopes, A. H. Sayed, Diffusion recursive least-squares for distributed estimation over adaptive
networks, IEEE Transactions on Signal Processing 56 (5) (2008) 1865–1877.
[30] R. Olfati-Saber, R. M. Murray, Consensus problems in networks of agents with switching topology and time-delays,
IEEE Transactions on Automatic Control 49 (9) (2004) 1520–1533.
[31] A. Bagchi, T. Başar, Team decision theory for linear continuous-time systems, IEEE Transactions on Automatic
Control AC-25 (6) (1980) 1154–1161.

29

