Decentralized RLS with Data-Adaptive Censoring for Regressions over Large-Scale Networks

I Introduction

In our big data era, various networks generate massive amounts of streaming data. Examples include wireless sensor networks, where a large number of inexpensive sensors cooperate to monitor, e.g. the environment , or data centers, where a group of servers collaboratively handles dynamic user requests . Since a single node has limited computational resources, decentralized information processing is preferable as the network size scales up . In this paper, we focus on a decentralized linear regression setup, and develop computation- and communication-efficient decentralized recursive least-squares (D-RLS) algorithms.

The main tool we adopt to reduce computation and communication costs is data-adaptive censoring, which leverages the redundancy present especially in big data. Upon receiving an observation, nodes determine whether it is informative or not. Less informative observations are discarded, while messages among neighboring nodes are exchanged only when necessary. We propose three censoring-based (C)D-RLS algorithms that can achieve estimation accuracy comparable to D-RLS without censoring, while significantly reducing the computation and communication overhead.

The merits of RLS algorithms in solving centralized linear regression problems are well recognized . When streaming observations that depend linearly on a set of unknown parameters become available, RLS yields the least-squares parameter estimates online. RLS reduces the computational burden of finding a batch estimate per iteration, and can even allow for tracking time-varying parameters. The computational cost can be further reduced by data-adaptive censoring , where less informative data are discarded. On the other hand, decentralized versions of RLS without censoring have been advocated to solve linear regression tasks over networks . In D-RLS, a node updates its estimate that is common to the entire network by fusing its local observations with the local estimates of its neighbors. As time evolves, all local estimates consent on the centralized RLS solution. This paper builds on both and by developing censoring-based decentralized RLS algorithms, thus catering to efficient online linear regression over large-scale networks.

Different from our in-network setting where operation is fully decentralized and nodes are only able to communicate with their neighbors, most of the existing distributed censoring algorithms apply to star topology networks that rely on a fusion center . Their basic idea is that each node transmits data to the fusion center for further processing only when its local likelihood ratio exceeds a threshold ; see also where communication constraints are also taken into account. Information fusion over fading channels is considered in . Practical issues such as joint dependence of sensor decision rules, randomization of decision strategies as well as partially known distributions are reported in , while also explores quantization jointly with censoring.

Other than the star topology studied in the aforementioned works, investigates censoring for a tree structure. If a node’s local likelihood ratio exceeds a threshold, its local data is sent to its parent node for fusion. A fully decentralized setting is considered in , where each node determines whether to transmit its local estimate to its neighbors by comparing the local estimate with the weighted average of its neighbors. Nevertheless, aims at mitigating only the communication cost, while the present work also considers reduction of the computational cost across the network. Furthermore, the censoring-based decentralized linear regression algorithm in deals with optimal full-complexity estimation when observations are partially known or corrupted. This is different from our context, where censoring is deliberately introduced to reduce computational and communication costs for decentralized linear regression.

I-B Our contributions and organization

The present paper introduces three data-adaptive online censoring strategies for decentralized linear regression. The resultant CD-RLS algorithms incur low computational and communication costs, and are thus attractive for large-scale network applications requiring decentralized solvers of linear regressions. Unlike most related works that specifically target wireless sensor networks (WSNs), the proposed algorithms may be used in a broader context of decentralized linear regression using multiple computing platforms. Of particular interest are cases where a regression dataset is not available at a single machine, but it is distributed over a network of computing agents that are interested in accurately estimating the regression coefficients in an efficient manner.

In Section II, we formulate the decentralized online linear regression problem (Section II-A), and recast the D-RLS in into a new form (Section II-B) that prompts the development of three censoring strategies (Section II-C). Section III develops the first censoring strategy (Section III-A), analyzes all three censoring strategies (Section III-B), and discusses how to set the censoring thresholds (Section III-C). Numerical experiments in Section IV demonstrate the effectiveness of the novel CD-RLS algorithms.

II Context and Algorithms

This section outlines the online linear regression setup over networks, and takes a fresh look at the D-RLS algorithm. Three strategies are then developed using data-adaptive censoring to reduce the computational and communication costs of D-RLS.

Our goal is to devise efficient decentralized online algorithms to solve the following exponentially-weighted least-squares (EWLS) problem

where $\hat{{\mathbf{s}}}_{ewls}(t)$ is the EWLS estimate at slot $t$, and $\lambda\in(0,1]$ is a forgetting factor that de-emphasizes the importance of past measurements, and thus enables tracking of a non-stationary process. When $\lambda=1$, (1) boils down to a standard decentralized online least-squares estimate.

II-B D-RLS revisited

The D-RLS algorithm of solves (1) as follows. Per time slot $t$, node $j$ receives $x_{j}(t)$ and $\mathbf{h}_{j}^{T}(t)$ and uses them to update the per-node inverse $p\times p$ covariance matrix as

along with the per-node $p\times 1$ cross-covariance vector as

Using $\mathbf{\Phi}_{j}^{-1}(t)$ and $\bm{\psi}_{j}(t)$, node $j$ then updates its local parameter estimate using

where ${\mathbf{v}}_{j}^{j^{\prime}}(t-1)$ denotes the Lagrange multiplier of node $j$ corresponding to its neighbor $j^{\prime}$ at slot $t-1$, that captures the accumulated differences of neighboring estimates, recursively obtained as ($\rho>0$ is a step-size)

Next, we develop an equivalent novel form of D-RLS recursions (2)–(5) that is convenient for our incorporation of data-adaptive censoring. Detailed derivation of the equivalence can be found in Appendix A. The inverse covariance matrix is updated as in (2). However, the update of ${\mathbf{s}}_{j}(t)$ in (4) is replaced by

where $\bm{\delta}_{j}(t)$ stands for a Lagrange multiplier conveying network-wide information that is updated as

Observe that $\bm{\delta}_{j}(t)$ stores the weighted sum of differences between the local estimate of node $j$, and all estimates of its neighbors. Interestingly, if the network is disconnected and the nodes are isolated, then $\bm{\delta}_{j}(t)=\mathbf{0}$ so long as $\bm{\delta}_{j}(0)=\mathbf{0}$, and the update of ${\mathbf{s}}_{j}(t)$ in (6) basically boils down to the centralized RLS one . That is, the current estimate is modified from its previous value using the prediction error $x_{j}(t)-\mathbf{h}_{j}^{T}(t){\mathbf{s}}_{j}(t-1)$, which is known as the incoming data innovation. If on the other hand the network is connected, nodes can leverage estimates of their neighbors (captured by $\bm{\delta}_{j}(t)$), which provide new information from the network other than its own observations $\{x_{j}(t)\}$. The term $\rho\mathbf{\Phi}_{j}^{-1}(t)\bm{\delta}_{j}(t-1)$ can be viewed as a Laplacian smoothing regularizer, which encourages all nodes of the graph to reach consensus on their estimates.

Remark 1. In D-RLS, (2) incurs computational complexity $O(p^{2})$, since calculating the products $\mathbf{\Phi}_{j}^{-1}(t-1)\mathbf{h}_{j}(t)$ and $\mathbf{\Phi}_{j}^{-1}(t-1)\bm{\psi}_{j}(t)$ requires $O(p^{2})$ multiplications. Similarly, (6) incurs computational complexity $O(p^{2})$, that is dominated by the matrix-vector multiplications $\mathbf{\Phi}_{j}^{-1}(t)\mathbf{h}_{j}(t)$ and $\mathbf{\Phi}_{j}^{-1}(t)\bm{\delta}_{j}(t-1)$. The cost of carrying out (7) is relatively minor. Regarding communication cost per slot $t$, node $j$ needs to transmit its local estimate ${\mathbf{s}}_{j}(t)$ to its neighbors and receive estimates ${\mathbf{s}}_{j^{\prime}}(t)$ from all neighbors $j^{\prime}\in\mathcal{N}_{j}$. The computational burden of D-RLS recursions (2)–(5) is comparable to that of (2), (6) and (7), with the cost of (4) being the same as what (6) requires. Meanwhile, the original form requires neighboring nodes $j$ and $j^{\prime}$ to exchange ${\mathbf{v}}_{j}(t)$ and ${\mathbf{v}}_{j^{\prime}}(t)$ in addition to ${\mathbf{s}}_{j}(t)$ and ${\mathbf{s}}_{j^{\prime}}(t)$, which doubles the communication cost relative to (6) and (7).

II-C Censoring-based D-RLS strategies

The D-RLS algorithm has well documented merits for decentralized online linear regression . However, its computational and communication costs per iteration are fixed, regardless of whether observations and/or the estimates from neighboring nodes are informative or not. This fact motivates our idea of permeating benefits of data-adaptive censoring to decentralized RLS, through three novel censoring-based (C)D-RLS strategies. They are different from the RLS algorithms in , where the focus is on centralized online linear regression.

Our first censoring strategy (CD-RLS-1) can be intuitively motivated as follows. If a given datum $(x_{j}(t),\mathbf{h}_{j}(t))$ is not informative enough, we do not have to use it since its contribution to the local estimate of node $j$, as well as to those of all network nodes, is limited. With $\{\tau\sigma_{j}(t)\}$ specifying proper thresholds to be discussed later, this intuition can be realized using a censoring indicator variable

If the absolute value of the innovation is less than $\tau\sigma_{j}(t)$, then $(x_{j}(t),\mathbf{h}_{j}(t))$ is censored; otherwise $(x_{j}(t),\mathbf{h}_{j}(t))$ is used. Section III-C will provide rules for selecting the threshold $\tau$ along with the local noise variance $\sigma_{j}^{2}(t)$, whose computations are lightweight. If data censoring is in effect, we simply throw away the current datum by letting $\mathbf{h}_{j}(t)=\mathbf{0}$ in (2), to obtain

Likewise, letting $x_{j}(t)=0$ and $\mathbf{h}_{j}(t)=\mathbf{0}$ in (6), yields

CD-RLS-1 is summarized in Algorithm 1. If censoring is in effect, computation cost per node and per slot is a fraction $2/7$ of the D-RLS in (4) and (7) without censoring. To recognize why, observe that the scalar-matrix multiplication $\lambda^{-1}\mathbf{\Phi}_{j}^{-1}(t-1)$ in (9) is not necessary as the update of $\mathbf{\Phi}_{j}^{-1}(t)$ can be merged to wherever it is needed, e.g., in (10) and the next slot. In addition, carrying out the $O(p^{2})$ multiplications to obtain $\mathbf{\Phi}_{j}^{-1}(t)\mathbf{h}_{j}(t)$ is no longer necessary, while the $O(p^{2})$ multiplications required to obtain $\mathbf{\Phi}_{j}^{-1}(t)\bm{\delta}_{j}(t-1)$ remain the same.

The first censoring strategy still requires nodes to communicate with neighbors per time slot; hence, the communication cost remains the same. Reducing this communication cost, motivates our second censoring strategy (CD-RLS-2), where each node does not perform extra computations relative to CD-RLS-1, but only receives neighboring estimates if its current datum is censored. The intuition behind this strategy is that if a datum is censored, then very likely the current local estimate is sufficiently accurate, and the node does not need to account for estimates from its neighbors. Estimates from neighbors, are only stored for future usage. Likewise, neighbors in $\mathcal{N}_{j}$ do not need node $j$’s current estimate either, because they have already received a very similar estimate. CD-RLS-2 is summarized in Algorithm 2.

The third censoring strategy (CD-RLS-3) given by Algorithm 3 is more aggressive than the second one. If a node has its datum censored at a certain slot, then it neither transmits to nor receives from its neighbors, and in that sense it remains “isolated” from the rest of the network in this slot. Apparently, we should not allow any node to be forever isolated. To this end, we can force each node to receive the local estimate from any of its neighbors at least once every $d_{\max}$ slots, which upper bounds the delay of information exchange to $d_{\max}$. Interestingly, the ensuing section will prove convergence of all three strategies to the optimal argument in the mean-square deviation sense under mild conditions.

III Development and performance analysis

This section starts with a criterion-based development of CD-RLS-1. Convergence analysis of all three censoring strategies will follow, before developing practical means of setting the censoring threshold $\tau\sigma_{j}(t)$.

Consider the following truncated quadratic cost that is similar to the one used in the censoring-based but centralized RLS

which is convex, but non-differentiable on $\{{\mathbf{s}}:|x_{j}(t)-\mathbf{h}_{j}^{T}(t){\mathbf{s}}|=\tau\sigma_{j}(t)\}$. Using (11) to replace the quadratic loss $[x_{j}(\tau)-\mathbf{h}_{j}^{T}(\tau){\mathbf{s}}]^{2}$ in (1), our CD-RLS-1 criterion is

Next, we employ alternating minimization and the stochastic Newton iteration to derive our first censoring-based solver of (13). To this end, consider the Lagrangian of (13) that is given by

To minimize (13) per slot $t>0$, we rely on alternating minimization in an online manner, which entails an iterative procedure consisting of three steps.

Observe that [S2] is a linearly constrained quadratic program, for which if ${\mathbf{v}}_{j}^{j^{\prime}}(t-1)+{\mathbf{u}}_{j}^{j^{\prime}}(t-1)=\mathbf{0}$, we always have

Therefore, the initial values of ${\mathbf{v}}_{j}^{j^{\prime}}$ and ${\mathbf{u}}_{j}^{j^{\prime}}$ in [S3] are selected to satisfy ${\mathbf{v}}_{j}^{j^{\prime}}(0)+{\mathbf{u}}_{j}^{j^{\prime}}(0)=\mathbf{0}$ (the simplest choice is ${\mathbf{v}}_{j}^{j^{\prime}}(0)={\mathbf{u}}_{j}^{j^{\prime}}(0)=\mathbf{0}$). It then holds for $t\geq 0$ that

Using the latter to eliminate ${\mathbf{u}}_{j}^{j^{\prime}}$ in [S3], we obtain

Moving on to [S1], observe that it can be split into $J$ per-node subproblems

Before solving (11) with the stochastic Newton iteration , eliminate ${\mathbf{v}}_{j}^{j^{\prime}}$ using (17) to obtain

which after manipulating the double sum yields

If the update in (7) is initialized with $\bm{\delta}_{j}(0)=\mathbf{0}$, summing up both sides from $\xi=1$ to $\xi=r-1$, we find after telescopic cancellation

Thus, optimization of ${\mathbf{s}}_{j}(t)$ reduces to

where the instantaneous cost per slot $t$ is

The stochastic gradient of the latter is given by

In the stochastic Newton method, the Hessian matrix is given by

where the second equality comes from (11) and (8). A reasonable approximation of the expectation is provided by sample averaging. However, presence of $\lambda\neq 1$ affects attenuation of regressors, which leads to

Applying the matrix inversion lemma, we obtain

and after adopting a diminishing step size $1/t$, the stochastic Newton update becomes

For rational convenience, let $\mathbf{\Phi}_{j}^{-1}(t):=\mathbf{M}_{j}^{-1}(t)/t$, and rewrite (21) as (cf. (2))

Substituting $\nabla g_{j,t}({\mathbf{s}}_{j}(t-1))$ and $\mathbf{\Phi}_{j}^{-1}(t)$ into the stochastic Netwon iteration yields (cf. (6))

which completes the development of CD-RLS-1.

III-B Convergence analysis

Here we establish convergence of all three novel strategies for $\lambda=1$. With $\lambda<1$, the EWLS estimator can even adapt to time-varying parameter vectors, but analyzing its tracking performance goes beyond the scope of this paper. For the time-invariant case ($\lambda=1$), we will rely on the following assumption.

(as1) Observations obey the linear model $x_{j}(t)=\mathbf{h}_{j}(t){\mathbf{s}}_{0}+\epsilon_{j}(t)$, where $\epsilon_{j}(t)\sim\mathcal{N}(0,\sigma_{j}^{2})$ is correlated across $j$ and $t$. Rows $\mathbf{h}_{j}^{T}(t)$ are uniformly bounded and independent of $\epsilon_{j}(t)$. Covariance matrices $\mathbf{R}_{h_{j}}:=E[\mathbf{h}_{j}(t)\mathbf{h}_{j}^{T}(t)]\succ\mathbf{0}_{p\times p}$ are time-invariant and positive definite. Process $\{c_{j}(t)\mathbf{h}_{j}(t)\mathbf{h}_{j}^{T}(t)\}$ is mean ergodic, while $\{\epsilon_{j}(t)\}$ and $\{c_{j}(t)\}$ are uncorrelated. Eigenvalues of $\mathbf{\Phi}_{j}(t)/t$, which approximate the true positive definite Hessian matrices $E[c_{j}(t)\mathbf{h}_{j}(t)\mathbf{h}_{j}^{T}(t)]$, are bounded below by a positive constant when $t$ is large enough.

We will assess convergence of our iterative algorithms using the squared mean-root deviation (SMRD) metric, defined as

Under (as1), convergence of CD-RLS-1 and CD-RLS-2 is asserted as follows; see Appendix B for the proof.

For CD-RLS-1 and CD-RLS-2 Algorithms 1 and 2, set $\sigma_{j}(t)=\sigma_{j}$ and $\mathbf{\Phi}^{-1}_{j}(0)=\gamma\mathbf{I}_{p}$ per node $j$. Let $\mu:=\min\{\lambda_{\min}(\mathbf{R}_{h_{j}}),j\in\mathcal{V}\}$, and suppose $0<\rho<1/(\gamma\lambda_{\max}(\mathbf{L}))$ for CD-RLS-1 and correspondingly $0<\rho<\rho_{0}$ for CD-RLS-2, while $\mathbf{L}$ is the network Laplacian and the constant $\rho_{0}$ depends on $\lambda_{\max}(\mathbf{L}),\gamma,\tau,\mu$, and the upper bound of $\mathbf{h}_{j}(t)$. Under (as1), there exists $t_{0}>0$ for which it holds for $t>t_{0}$ that

The proof for CD-RLS-3 is more challenging. Because a node does not receive any information from its neighbors when censoring is in effect, it has to rely on outdated neighboring estimates when the incoming datum is not censored. This delay in percolating information may cause computational instability. For this reason, we will impose an additional constraint to guarantee that all local estimates do not grow unbounded. In practice, this can be realized by truncating local estimates when they exceed a certain threshold.

(as2) Local estimates $\{{\mathbf{s}}_{j}(t)\}_{j=1}^{J}$ are uniformly bounded $\forall t\geq 0$.

Convergence of CD-RLS-3 is then asserted as follows. Similar to CD-RLS-1 and CD-RLS-2, the SMRD of CD-RLS-3 converges to zero with rate $O(\ln(t)/t)$, as stated in the following theorem.

For CD-RLS-3 given by Algorithms 3, set $\sigma_{j}(t)=\sigma_{j}$ and $\mathbf{\Phi}^{-1}_{j}(-1)=\gamma\mathbf{I}_{p}$ per node $j$. Under (as1) and (as2) with $0<\rho<\rho_{0}$ as in Theorem 1, there exists $t_{0}>0$ for which it holds $\forall t>t_{0}$, that

where $a$ and $b$ are positive constants that depend on the upper bounds of $\mathbf{h}_{j}(t)$ and ${\mathbf{s}}_{j}(t)$, parameters $\rho$ and $\tau$, the covariance $\mathbf{R}_{h_{j}}(t)$, the Laplacian matrix $\mathbf{L}$, and $t_{0}$.

Although the bounds asserted by Theorems 1 and 2 could be loose, they demonstrate that $\lim\sup_{t\rightarrow\infty}\text{SMRD}(t)=0$, which establishes that the decentralized estimates converge to the ground truth asymptotically.

III-C Threshold setting and variance estimation

The threshold $\tau$ influences considerably the performance of all CD-RLS algorithms. Its value trades off estimation accuracy for computation and communication overhead. We provide a simple criterion for setting $\tau$ using the average censoring ratio $\pi^{*}$, which is defined as the number of censored data over the total number of data . The goal is to choose $\tau$ so that the actual censoring ratio approaches $\pi^{*}$ as $t$ goes to infinity – since we are dealing with streaming big data, such an asymptotic property is certainly relevant. When $t$ is large enough, ${\mathbf{s}}$ is very close to ${\mathbf{s}}_{0}$; thus, the innovation $x_{j}(t)-\mathbf{h}_{j}^{T}(t){\mathbf{s}}_{j}(t-1)\approx x_{j}(t)-\mathbf{h}_{j}^{T}(t){\mathbf{s}}_{0}=\epsilon_{j}(t)\sim\mathcal{N}(0,\sigma_{j}^{2})$. As a consequence, $\Pr(c_{j}(t)=0)=\Pr(|x_{j}(t)-\mathbf{h}_{j}^{T}(t){\mathbf{s}}_{j}(t-1)|\leq\tau\sigma_{j})\approx\Pr(|\epsilon_{j}(t)|\leq\tau\sigma_{j})=\Pr(|\epsilon_{j}(t)/\sigma_{j}|\leq\tau)=1-2Q(\tau)$, where the last equality holds because $\epsilon_{j}(t)/\sigma_{j}\sim\mathcal{N}(0,1)$. Therefore, $\pi^{*}=\lim_{t\rightarrow\infty}\frac{1}{t}\sum_{\tau=0}^{t}E[c_{j}(\tau)]\approx 1-2Q(\tau)$, which implies that

Given the average censoring ratio $\pi^{*}$, Table I compares the average per step per node communication and computational costs of D-RLS and the proposed CD-RLS algorithms. We assume that transmitting or receiving a $p$-dimensional local estimate vector to or from a neighboring node incurs a cost of $p$. Thus, for D-RLS and CD-RLS-1, the average communication costs are both $2p|\mathcal{E}|/J$. In CD-RLS-2, a node does not transmit to its neighbors when it censors a datum, which leads to an average communication cost of $2p|\mathcal{E}|(1-\pi^{*})/J$. CD-RLS-3 avoids communication over a link as long as one of the two end nodes censors a datum, and hence reduces the cost to $2p|\mathcal{E}|(1-\pi^{*})^{2}/J$. As discussed in Section II-C, the computational costs of CD-RLS-1 for the non-censoring and censoring cases are $O(7p^{2}/2)$ and $O(p^{2})$, respectively. For the censoring case, CD-RLS-2 and CD-RLS-3 reduce their computational costs to $O(p)$, and are more computationally efficient.

If the variances $\{\sigma_{j}^{2}\}$ were known, one could simply choose $\sigma_{j}(t)=\sigma_{j}$. However, $\sigma_{j}$ in practice is often unknown. In this case, we consider the running average $\sigma_{j}^{2}(t+1)\approx t^{-1}\sum_{\tau=1}^{t+1}[x_{j}(\tau)-\mathbf{h}_{j}^{T}(\tau){\mathbf{s}}_{0}]^{2}=(t-1)\sigma_{j}^{2}(t)/t+[x_{j}(t+1)-\mathbf{h}_{j}^{T}(t+1){\mathbf{s}}_{0}]^{2}/t$, which suggests the recursive variance estimate

IV Numerical Experiments

This section provides numerical results to validate the effectiveness of our novel censoring strategies. We simulate a network of $J=15$ nodes, which are uniformly randomly deployed over a $1\times 1$ square. Two nodes within communication range $0.3$ are deemed as being neighbors. The resultant network topology is depicted in Fig. 1. We compare six algorithms: the centralized adaptive censoring (AC)-RLS that runs in every node independently, the distributed diffusion least mean-square (Diffusion-LMS) algorithm , D-RLS without censoring , and the three censoring-based D-RLS algorithms, namely CD-RLS-1, CD-RLS-2 and CD-RLS-3. All algorithms are evaluated on two data sets, one synthetic and one real. The empirical SMRD is used as performance metric.

For the synthetic data set, the unknown ${\mathbf{s}}_{0}$ is $p$-dimensional with $p=4$. The setting is the one in , where WSN-based decentralized power spectrum estimation is sought for a signal modeled as an autoregressive process. In this context, consider an auxiliary sequence $r_{j}(t)$ that evolves according to $r_{j}(t)=(1-q)\beta_{j}r_{j}(t-1)+\sqrt{q}\omega_{j}(t)$. Starting from $r_{j}(t)$, the row $\mathbf{h}_{j}^{T}(t)$ is formed by taking the next $p$ observations, namely $\mathbf{h}_{j}^{T}(t)=[r_{j}(t+p-1);\ldots;r_{j}(t)]$. Parameters are selected as $q=0.5$, $\beta_{j}\sim\mathcal{U}(0,1)$, and also uniformly distributed driving white noise $\omega_{j}(t)\sim\mathcal{U}(-\sqrt{3}\sigma_{\omega_{j}},\sqrt{3}\sigma_{w_{j}})$ with $\sigma^{2}_{\omega_{j}}\sim\mathcal{U}(0,2)$. Observation of node $j$ is subject to additive white Gaussian noise, with covariance $\sigma_{j}^{2}=10^{-3}\alpha_{j}$, where $\alpha_{j}\sim\mathcal{U}(0,1)$. The true signal vector is $\mathbf{s}_{0}=\mathbf{1}_{p}$, for which $\lambda=1$ is set for all algorithms. For D-RLS, CD-RLS-1, CD-RLS-2 and CD-RLS-3, the step size $\rho=0.01$ and $\mathbf{\Phi}_{j}^{-1}(0)=\gamma\mathbf{I}_{p}$ where $\gamma=30$, leading to fastest convergence of D-RLS. Regarding the four censoring-based algorithms AC-RLS, CD-RLS-1, CD-RLS-2 and CD-RLS-3, we set the average censoring ratio to $\pi^{*}=0.6$, which is approached using $\tau=Q^{-1}((1-\pi^{*})/2)\approx 0.84$. The variances $\sigma_{j}^{2}$ are estimated in an online manner as described in Section III-C. AC-RLS uses $\mathbf{\Phi}_{j}^{-1}(0)=\gamma\mathbf{I}_{p}$, where $\gamma=10^{5}$ leads to the fastest convergence. Diffusion-LMS uses the nearest-neighbor diffusion matrix and $1.5/\sqrt{t}$ step size, which is tuned to obtain fastest convergence. For all curves obtained by running the algorithms, the ensemble averages are approximated via sample averaging over 100 Monte Carlo runs.

Fig. 2 depicts the SMRD versus the number of iterations. Not surprisingly, since D-RLS does not censor data, its convergence rate with respect to the number of iterations is the fastest. Among the three proposed CD-RLS algorithms, CD-RLS-2 and CD-RLS-3 are slower than CD-RLS-1, because the former two incur smaller communication cost than the latter. Though CD-RLS-3 adopts a more aggressive censoring strategy than CD-RLS-2, its convergence does not degrade as confirmed by Fig. 2. AC-RLS is the slowest among all except for Diffusion-LMS, because it is run at all nodes independently, without sharing information over the network. Even though the SMRD of Diffusion-LMS vanishes as $t\rightarrow\infty$ (with rate $1/t$), its finite-sample SMRD decays slower than our CD-RLS schemes for which SMRD also vanishes as $t\rightarrow\infty$ (with rate upper bounded by $\ln(t)/t$). This is analogous to centralized LMS that for finite samples exhibits SMRD decaying slower than that of centralized RLS. Note that contrary to the analysis in and , the cost function here is not differentiable and thus the Diffusion-LMS does not achieve the traditional linear rate. We shall not compare with Diffusion-LMS in the rest of the numerical experiments.

The merits of censoring are further appreciated when one considers computational costs. Recall that the target average censoring ratio is $\pi^{*}=0.6$, meaning that $3/5$ of the data are discarded (actual values are $0.6320$ for AC-RLS, $0.6292$ for CD-RLS-1, $0.6277$ for CD-RLS-2, and $0.6237$ for CD-RLS-3, averaged over 100 runs). As confirmed by Fig. 3, the three CD-RLS algorithms consume considerably less computational resources relative to D-RLS that does not censor data. Indeed, whenever a datum is censored, CD-RLS-1 only requires $2/7$ of the computations relative to D-RLS, while CD-RLS-2 and CD-RLS-3 incur minimal computational overhead. Although AC-RLS is the most computationally efficient algorithm at the beginning, absence of collaboration undermines its performance in steady state.

Regarding the amount of data exchanged to communicate local estimates in a unicast mode, CD-RLS-1 is the worst because nodes need to transmit their local estimate to neighbors, no matter whether local data are censored or not. Fig. 4 corroborates that CD-RLS-2 and CD-RLS-3 show significant improvement over D-RLS, demonstrating their potential for reducing both communication and computation costs in solving decentralized linear regression problems over large-scale networks.

We further numerically quantify the savings of computation and communication that the three censoring-based D-RLS algorithms enjoy over RLS without censoring. We set the target SMRD to $0.015$ and plot the computational and communication costs required to reach it. According to Fig. 5, the computational costs of the three censoring-based algorithms decrease to about half of that of D-RLS as the censoring ratio grows to $0.7$, while CD-RLS-2 outperforms the other two. Though CD-RLS-2 uses more iterations (hence more data) to achieve the target SMRD than CD-RLS-1 (see Fig. 2), it requires less computation when a datum is censored. On the other hand, CD-RLS-3 uses more iterations to achieve the target SMRD than CD-RLS-2, and hence it incurs more computational cost. The saving of CD-RLS-3 over CD-RLS-2 is mainly in the communication cost. In Fig. 6, the communication cost of CD-RLS-2 and CD-RLS-3 decreases as the censoring ratio grows, but that of CD-RLS-1 increases and is larger than that of D-RLS when the censoring ratio exceeds $0.5$. CD-RLS-3 exhibits best performance in terms of communication cost.

Next, we vary $\pi$ and evaluate its impact on SMRD, as shown in Fig. 7. The SMRD here is computed after 500 iterations. When $\pi$ is close to $0.5$, meaning about $1/2$ of the data is censored, the three proposed CD-RLS algorithms are still able to reach SMRD of $10^{-4}$, which is the limit of D-RLS without censoring. Among the three algorithms, CD-RLS-1 exhibits the best SMRD curve, but its computation and communication costs are the highest. AC-RLS does not perform well especially for low censoring ratios due to the lack of network-wide collaboration. CD-RLS-2 and CD-RLS-3 perform comparably in this experiment.

The effectiveness of the novel censoring-based strategies is further assessed on a real data set of protein tertiary structures . The premise here is that a given dataset is not available at a single location, but it is distributed over a network whose nodes are interested in obtaining accurate regression coefficients while suppressing the communication and computational overhead. Again, the graph in Fig. 1 is used to model the network of regression-performing agents. The number of control variables is $p=9$. The first $45,720$ (out of $45,730$) observations are normalized and divided evenly into $J=15$ parts, one per node. For CD-RLS-1, CD-RLS-2 and CD-RLS-3, we set $\rho=0.05$ and $\mathbf{\Phi}_{j}^{-1}(0)=5\mathbf{I}_{p}$, while for AC-RLS we choose $\gamma=10$. The ground truth vector ${\mathbf{s}}_{0}$ is estimated by solving a batch least-squares problem on the entire data set. Similar to what we deduced from Fig. 7 in the synthetic data set, the novel CD-RLS algorithms outperform AC-RLS in terms of SMRD, as one varies the average censoring ratio from $15\%$ to nearly $100\%$ in Fig. 8.

V Concluding Remarks

This paper introduced three data-adaptive censoring strategies that significantly reduce the computation and communication costs of the RLS algorithm over large-scale networks. The basic idea behind these strategies is to avoid inefficient computation and communication when the local observations and/or the neighboring messages are not informative. We proved convergence of the resulting algorithms in the mean-square deviation sense. Numerical experiments validated the merits of the novel schemes.

The notion of identifying and discarding less informative observations can be widely used in various large-scale online machine learning tasks including nonlinear regression, matrix completion, clustering and classification, to name a few. These constitute our future research directions.

Appendix A Equivalent Form of D-RLS

Here we prove that D-RLS recursions (2) - (5) are equivalent to (2), (6) and (7). It follows from (4) that

Applying the matrix inversion lemma to (2) yields

Substituting $\bm{\psi}_{j}(t)-\lambda\bm{\psi}_{j}(t-1)=\mathbf{h}_{j}(t)x_{j}(t)$ from (3) and $\lambda\mathbf{\Phi}_{j}(t-1)=\mathbf{\Phi}_{j}(t)-\mathbf{h}_{j}(t)\mathbf{h}_{j}^{T}(t)$ from (27) into (26), leads to

Next, we will show that if $\bm{\delta}(t)$ is defined as

then its update is exactly (7). This can be done by taking the difference between slots $t$ and $t-1$ for (A), and substituting the update of ${\mathbf{v}}_{j}^{j^{\prime}}$ in (5). Due to (A), it follows that (A) is equivalent to

Left multiplying (A) with $\mathbf{\Phi}_{j}^{-1}(t)$, yields the update of ${\mathbf{s}}_{j}$ in (6), and completes the proof.

Appendix B Proof of Theorem 1

We need the following lemma in [8, Chapter 7, Theorem 4].

Let $X,X_{1},X_{2},...$ be random variables on some probability space. If $X_{n}\rightarrow X$ in probability and $Pr(|X_{n}|\leq k)=1$ for all $n$ and some $k$, then $X_{n}\rightarrow X$ in $r$th mean for all $r\geq 1$.

Starting with CD-RLS-1, the proof proceeds in five stages.

Stage 1. We first investigate the spectral properties of $\mathbf{\Phi}_{j}(t)$ when $t$ is sufficiently large. Letting $\lambda=1$ and applying the matrix inversion lemma to the censoring form (2), we have

Summing up from $r=1$ to $r=t$ and using the telescopic cancellation, (31) yields

Thanks to the strong law of large numbers, $\mathbf{\Phi}_{j}(t)/t$ converges to $E[c_{j}(t)\mathbf{h}_{j}(t)\mathbf{h}_{j}^{T}(t)]$ almost surely as $t\rightarrow\infty$. Observe that

Observing the integral in (33), we know that

where the event set that the second inequality strictly holds (namely, “$\geq$” becomes “$>$”) is with nonzero measure. Thus, substituting (B) into (33) yields

Since $\mathbf{\Phi}_{j}(t)/t$ converges to $E[c_{j}(t)\mathbf{h}_{j}(t)\mathbf{h}_{j}^{T}(t)]$ almost surely as $t\rightarrow\infty$ and $\mathbf{h}_{j}(t)$ is uniformly bounded such that $\mathbf{\Phi}_{j}(t)/t$ is also bounded (cf. (32)), we have $E[\|\mathbf{\Phi}_{j}(t)/t\|_{2}]$ converges to $E[\|c_{j}(t)\mathbf{h}_{j}(t)\mathbf{h}_{j}^{T}(t)\|_{2}]$ as $t\rightarrow\infty$ by lemma 1. Therefore, $2Q(\tau)\mathbf{R}_{h_{j}}\prec E[c_{j}(t)\mathbf{h}_{j}(t)\mathbf{h}_{j}^{T}(t)]\prec\mathbf{R}_{h_{j}}$ implies that there exists $t_{1}>0$, for which it holds $\forall t\geq t_{1}$ that

and consequently the expected maximum eigenvalue of $\mathbf{\Phi}_{j}(t)$ satisfies

Observe that $t\mathbf{\Phi}^{-1}_{j}(t)$ converges to $\left\{E[c_{j}(t)\mathbf{h}_{j}(t)\mathbf{h}_{j}^{T}(t)]\right\}^{-1}$ almost surely as $t\rightarrow\infty$ due to the convergence of $\mathbf{\Phi}_{j}(t)/t$ to $E[c_{j}(t)\mathbf{h}_{j}(t)\mathbf{h}_{j}^{T}(t)]$. Since eigenvalues of $\mathbf{\Phi}_{j}(t)/t$ are bounded below by a positive constant when $t$ is large enough, there exists $t_{2}>0$ such that $t\mathbf{\Phi}^{-1}_{j}(t)$ is bounded $\forall t\geq t_{2}$. Following the same analysis to obtain (35), it holds $\forall t\geq t_{2}$ that

Letting $t_{0}:=\max(t_{1},t_{2})$, (35) and (36) hold $\forall t\geq t_{0}$.

Stage 2. Rewrite the update of ${\mathbf{s}}_{j}$ as

Note also that for $\lambda=1$, the update of $\bm{\delta}_{j}$ is equivalent to (cf. (III-A))

Letting $\mathbf{e}_{j}(t):={\mathbf{s}}_{j}(t)-{\mathbf{s}}_{0}$, the estimation error obeys the recursion

Substituting $x_{j}(t)=\mathbf{h}_{j}(t){\mathbf{s}}_{0}+\epsilon_{j}(t)$ to eliminate ${\mathbf{s}}_{j}(t-1)$, we obtain

Left multiplying (B) with $\mathbf{\Phi}_{j}(t)$ yields

which after left multiplication with $\mathbf{\Phi}^{-\frac{1}{2}}(t)$ yields

From (B), we have ($\otimes$ denotes Kronecker product)

Since $\mathbf{C}(t)$ and $\bm{\epsilon}(t)$ are irrelevant under (as1), the second term on the right hand side is zero; hence,

Stage 3. Consider the first term on the right hand side of (B). Since $\mathbf{L}$ is positive semi-definite, we can find a matrix $\mathbf{U}=(\mathbf{L}\otimes\mathbf{I}_{p})^{\frac{1}{2}}$ such that $\mathbf{L}\otimes\mathbf{I}_{p}=\mathbf{U}^{T}\mathbf{U}$. By the matrix inversion lemma, it holds that

For $\lambda=1$, it follows from (2) that $\mathbf{\Phi}^{-1}(t-1)-\mathbf{\Phi}^{-1}(t)\succeq\mathbf{0}_{Jp}$. Since $\mathbf{\Phi}^{-1}(0)=\gamma\mathbf{I}_{Jp}$, it holds that $\mathbf{\Phi}^{-1}(t-1)\preceq\gamma\mathbf{I}_{Jp}$ for all $t\geq 1$, and consequently

If $0<\rho<1/(\gamma\lambda_{\max}(\mathbf{L}))$, then for all $t\geq 1$ it follows that

This implies that the second term of (B) is positive definite. Thus, we have

and hence, the first term on the right hand side of (B) is bounded by

Stage 4. Now consider the second term on the right hand side of (B). Manipulating the expectation yields

Because $\mathbf{\Phi}_{j}^{-1}(t-1)\succeq\mathbf{\Phi}_{j}^{-1}(t)$ due to (22), we further have

Since $\mathbf{\Phi}_{j}^{-1}(t-1)$ and $\mathbf{h}_{j}(t)$ are independent, it holds $\forall t>t_{0}$ that

For $t\leq t_{0}$, we have $\mathbf{\Phi}_{j}^{-1}(t)\preceq\mathbf{\Phi}_{j}^{-1}(0)=\gamma\mathbf{I}_{p}$ because to (43), and thus

Stage 5. Substituting (B), (B) and (B) into (B) implies for $t>t_{0}$ that

Summing (B) from $r=t_{0}+1$ to $r=t$ and (B) from $r=1$ to $r=t_{0}$, applying telescopic cancellation, and noticing that $\mathbf{\Phi}(0)=\gamma^{-1}\mathbf{I}_{Jp}$, yields for $t>t_{0}$

where the last line is due to Cauchy-Schwarz inequality

From (36), $E[\lambda_{\max}(\mathbf{\Phi}^{-1}_{j}(t))]<\lambda_{\max}(\mathbf{R}_{h_{j}}^{-1})/(2Q(\tau)t)=1/(\lambda_{\min}(\mathbf{R}_{h_{j}})2Q(\tau)t)$ holds asymptotically. Definining $\mu:=\min\{\lambda_{\min}(\mathbf{R}_{h_{j}}),j\in\mathcal{V}\}$, we establish that

Finally, with $||\mathbf{e}(t)||^{2}:=\sum_{j=1}^{J}||\mathbf{e}_{j}(t)||^{2}=\sum_{j=1}^{J}||{\mathbf{s}}_{j}(t)-{\mathbf{s}}_{0}||^{2}$ this leads to (24), which completes the proof of CD-RLS-1.

Consider next CD-RLS-2. Stage 1 of the proof remains the same, while for Stage 2, $\mathbf{e}_{j}(t-1)-\mathbf{e}_{j^{\prime}}(t-1)$ is replaced by c_{j}(t)\big{[}\mathbf{e}_{j}(t-1)-\mathbf{e}_{j^{\prime}}(t-1)\big{]} in (38) to arrive at

Observe that the right hand sides of (B) and (B) are only different in their first terms. Similar to Stage 3 (cf. (B)), we need to show that the first term satisfies

Substituting the update (22) with $\lambda=1$ into (B), it suffices to prove that

For the left hand side of (57), use the lower bound of the conditional expectation $2Q(\tau)\leq E[c_{j}(t)|\mathbf{h}_{j}(t),{\mathbf{s}}_{j}(t-1)]$ to eliminate $\mathbf{C}(t)$, and arrive at

By (43), it holds that $\mathbf{\Phi}^{-1}(t-1)\preceq\mathbf{\Phi}^{-1}(0)=\gamma\mathbf{I}_{Jp}$, and thus

By assumption $\{{\bf h}_{j}(t)\}$ are uniformly bounded. If ${\bf h}_{j}^{T}(t){\bf h}_{j}(t)\leq K$ for all $j=1,\ldots,J$, we find

Substituting (59) into (58), we obtain a lower bound for the left hand side of (57) given by

As for the right hand side of (57), it is upper bounded by

where we used that all the diagonal elements $c_{j}(t)$ of $\mathbf{C}(t)$ are within the range $$while$||\mathbf{W}_{1}||_{2}$ is upper bounded by

Noticing that $||\mathbf{C}(t)||_{2}\leq 1$, $||\mathbf{H}(t)||_{2}^{2}\leq K^{2}$ by assumption, $||\mathbf{\Phi}^{-1}(t-1)||_{2}\leq||\mathbf{\Phi}^{-1}(0)||_{2}=\gamma$, $||(\mathbf{I}_{J}+\mathbf{H}^{T}(t)\mathbf{\Phi}^{-1}(t-1)\mathbf{H}(t))^{-1}||_{2}\leq 1$ and $||\mathbf{L}||_{2}\leq\lambda_{\max}(\mathbf{L})$, we find that

Similarly, $||\mathbf{W}_{2}||_{2}$ is upper bounded by

and combining (60) with (62), we see that if $\rho$ is chosen within $[0,\rho_{0}]$, then (57) holds for all $t\geq 1$; and so does (B).

Following Stages 4 and 5 in the proof for CD-RLS-1, we can show that (24) holds almost surely for CD-RLS-2 $\forall t>t_{0}$. This completes the proof of the entire theorem.

Appendix C Proof of Theorem 2

There exist constants $M>0$ and $t_{0}>0$ such that

The update of $\mathbf{e}_{j}(t)$ for CD-RLS-3 is (cf. (B) for CD-RLS-1)

Per time $t$, $t-d_{j}^{j^{\prime}}(t)$ is the latest time slot when node $j$ received information from its neighbor $j^{\prime}$. Therefore, $d_{j}^{j^{\prime}}(t)$ can be viewed as network delay caused by the censoring strategy. Then we have

In deriving the inequality we use the fact that $c_{j}(t)\in\{0,1\}$.

According to (36) in the proof of Theorem 1, which also holds true for CD-RLS-3, there exists $t_{0}>0$, such that $E[||\mathbf{\Phi}_{j}^{-1}(t)||_{2}]$ is upper bounded by $M_{1}/t$ when $t>t_{0}$, where $M_{1}$ is a positive constant determined by $Q(\tau)$ and the smallest eigenvalue of $\mathbf{R}_{h_{j}}(t)$. By (as1) and (as2), $||\mathbf{h}_{j}(t)||$, $||\mathbf{e}_{j}(t-1)||$ and $||\mathbf{e}_{j^{\prime}}(t-d_{j}^{j^{\prime}}(t))||$ are also upper bounded. Therefore, there exist constants $M_{2},M_{3}>0$, such that

Taking expectations on both sides yields (63).

Rewrite the update of $\mathbf{e}_{j}(t)$ for CD-RLS-3 in (64) to

Multiplying $\mathbf{\Phi}_{j}(t)$ on both sides, we have

Using the same notations as in the proof of Theorem 1, we obtain an matrix form

By the Cauchy-Schwarz inequality, we have

Here we use the fact that $d_{j}^{j^{\prime}}(t)$ is no larger than the maximal delay $d_{\max}$. Take expectation and use Lemma 2. There exists $t_{0}>0$ such that when $t\geq t_{0}$ it holds

Back to (65), multiplying $\mathbf{\Phi}^{-\frac{1}{2}}(t)$ on both sides yields

Since $\mathbf{H}(t)$ and $\bm{\epsilon}(t)$ are independent as given by (as1), we have

Observe that (66) is different to (B) for having the last two terms at the right hand side. Because all the diagonal elements $c_{j}(t)$ in the diagonal matrix $\mathbf{C}(t)$ are within $$,$\forall t\geq t_{0}$

The right hand side is in the order of $O(1/t^{3})$ because $E[||\mathbf{\Phi}^{-1}(t)||_{2}]$ is no larger than $\lambda_{\max}(\mathbf{R}_{h_{j}}^{-1})/(2Q(\tau)t)$ for all $t\geq t_{0}$ as we have shown in Step 1 of the proof of Theorem 1 (cf. (36)). Meanwhile, $\forall t\geq t_{0}$

For the first term at the right hand side of (66), similar to the proof for CD-RLS-2, if $\rho$ is chosen within $[0,\rho_{0}]$ we are able to show that (cf. (B))

Finally, following Step 4 of the proof of Theorem 1 to handle the second term at the right hand side of (66), we know that it is also in the order of $O(1/t)$. Therefore, for all $t\geq t_{0}$ (66) yields

where $K_{1},K_{2}>0$ are constants. Summing up both sides from time $r=t_{0}$ to $r=t$, we have

Observing that $E[\mathbf{e}^{T}(t_{0}-1)\mathbf{\Phi}(t_{0}-1)\mathbf{e}(t_{0}-1)]$ is bounded because $||\mathbf{e}(t_{0}-1)||$ is bounded by (as2), the right hand side of (67) is in the order of $O(1)+O(\ln(t))$. Following the argument in Step 5 of the proof of Theorem 1, $E[||\mathbf{\Phi}^{-1}(t)||_{2}]$ is in the order of $O(1/t)$ when $t\geq t_{0}$. Therefore, $E[||\mathbf{e}(t)||]^{2}$ is in the order of $O(1/t)+O(\ln(t)/t)$, which completes the proof of Theorem 2.

References