Decentralized learning for wireless communications and networking

Introduction

This chapter puts forth an optimization framework for learning over networks, that entails decentralized processing of training data acquired by interconnected nodes. Such an approach is of paramount importance when communication of training data to a central processing unit is prohibited due to e.g., communication cost or privacy reasons. The so-termed in-network processing paradigm for decentralized learning is based on successive refinements of local model parameter estimates maintained at individual network nodes. In a nutshell, each iteration of this broad class of fully decentralized algorithms comprises: (i) a communication step where nodes exchange information with their neighbors through e.g., the shared wireless medium or Internet backbone; and (ii) an update step where each node uses this information to refine its local estimate. Devoid of hierarchy and with their decentralized in-network processing, local e.g., estimators should eventually consent to the global estimator sought, while fully exploiting existing spatiotemporal correlations to maximize estimation performance. In most cases, consensus can formally be attained asymptotically in time. However, a finite number of iterations will suffice to obtain results that are sufficiently accurate for all practical purposes.

In this context, the approach followed here entails reformulating a generic learning task as a convex constrained optimization problem, whose structure lends itself naturally to decentralized implementation over a network graph. It is then possible to capitalize upon this favorable structure by resorting to the alternating-direction method of multipliers (ADMM), an iterative optimization method that can be traced back to Glowinski_Marrocco_ADMM_1975 (see also Gabay_Mercier_ADMM_1976 ), and which is specially well-suited for parallel processing bertsi97book ; Boyd_ADMM . This way simple decentralized recursions become available to update each node’s local estimate, as well as a vector of dual prices through which network-wide agreement is effected.

In the decentralized learning problem studied here though, the summands $f_{i}$ are assumed to be local cost functions only known to each node $i$. Otherwise sharing this information with a centralized processor, also referred to as fusion center (FC), can be challenging in various applications of interest, or, it may be even impossible in e.g., wireless sensor networks (WSNs) operating under stringent power budget constraints. In other cases such as the Internet or collaborative healthcare studies, agents may not be willing to share their private training data ${\bf y}_{i}$ but only the learning results. Performing the optimization (1) in a centralized fashion raises robustness concerns as well, since the central processor represents an isolated point of failure.

In this context, the objective of this chapter is to develop a decentralized algorithmic framework for learning tasks, based on in-network processing of the locally available data. The described setup naturally suggests three characteristics that the algorithms should exhibit: c1) each node $i=1,\ldots,n$ should obtain an estimate of ${\bf s}$, which coincides with the corresponding solution $\hat{{\bf s}}$ of the centralized estimator (1) that uses the entire data $\{{\bf y}_{i}\}_{i=1}^{n}$; c2) processing per node should be kept as simple as possible; and c3) the overhead for inter-node communications should be affordable and confined to single-hop neighborhoods. It will be argued that such an ADMM-based algorithmic framework can be useful for contemporary applications in the domain of wireless communications and networking.

Prior art. Existing decentralized solvers of (1) can be classified in two categories: C1) those obtained by modifying centralized algorithms and operating in the primal domain; and C2) those handling an equivalent constrained form of (1) (see (2) in Section 2), and operating in the primal-dual domain.

Primal-domain algorithms under C1 include the (sub)gradient method and its variants Nedic2009 ; Ram2010 ; Yuan2013 ; Jakovetic2013 , the incremental gradient method Rabbat2005-inc , the proximal gradient method Chen2012 , and the dual averaging method Duchi2012 ; Tsianos2012-acc . Each node in these methods, averages its local iterate with those of neighbors and descends along its local negative (sub)gradient direction. However, the resultant algorithms are limited to inexact convergence when using constant stepsizes Nedic2009 ; Yuan2013 . If diminishing stepsizes are employed instead, the algorithms can achieve exact convergence at the price of slowing down speed Jakovetic2013 ; Rabbat2005-inc ; Duchi2012 . A constant-stepsize exact first-order algorithm is also available to achieve fast and exact convergence, by correcting error terms in the distributed gradient iteration with two-step historic information Shi2014-extra .

Primal-dual domain algorithms under C2 solve an equivalent constrained form of (1), and thus drive local solutions to reach global optimality. The dual decomposition method is hence applicable because (sub)gradients of the dual function depend on local and neighboring iterates only, and can thus be computed without global cooperation Rabbat2005 . ADMM modifies the dual decomposition by regularizing the constraints with a quadratic term, which improves numerical stability as well as rate of convergence, as will be demonstrated later in this chapter. Per ADMM iteration, each node solves a subproblem that can be demanding. Fortunately, these subproblems can be solved inexactly by running one-step gradient or proximal gradient descent iterations, which markedly mitigate the computation burden Ling2014-icassp ; Chang2014-icassp . A sequential distributed ADMM algorithm can be found in Wei2012 .

Chapter outline. The remainder of this chapter is organized as follows. Section 2 describes a generic ADMM framework for decentralized learning over networks, which is at the heart of all algorithms described in the chapter and was pioneered in sg06asilomar ; srg08tsp for in-network estimation using WSNs. Section 3 focuses on batch estimation as well as (un)supervised inference, while Section 4 deals with decentralized adaptive estimation and tracking schemes where network nodes collect data sequentially in time. Internet traffic anomaly detection and spectrum cartography for wireless CR networks serve as motivating applications for the sparsity-regularized rank minimization algorithms developed in Section 5. Fundamental results on the convergence and convergence rate of decentralized ADMM are stated in Section 6.

In-Network Learning with ADMM in a Nutshell

Since local summands in (1) are coupled through a global variable $\mathbf{s}$, it is not straightforward to decompose the unconstrained optimization problem in (1). To overcome this hurdle, the key idea is to introduce local variables ${\cal S}:=\{\mathbf{s}_{i}\}_{i=1}^{n}$ which represent local estimates of $\mathbf{s}$ per network node $i$ sg06asilomar ; srg08tsp . Accordingly, one can formulate the constrained minimization problem

The “consensus” equality constraints in (2) ensure that local estimates coincide within neighborhoods. Further, if the graph is connected then consensus naturally extends to the whole network, and it turns out that problems (1) and (2) are equivalent in the sense that $\hat{\mathbf{s}}=\hat{\mathbf{s}}_{1}=\ldots=\hat{\mathbf{s}}_{n}$ srg08tsp . Interestingly, the formulation in (2) exhibits a separable structure that is amenable to decentralized minimization. To leverage this favorable structure, the alternating direction method of multipliers (ADMM), see e.g., (bertsi97book, , pg. 253-261), can be employed here to minimize (2) in a decentralized fashion. This procedure will yield a distributed estimation algorithm whereby local iterates $\mathbf{s}_{i}(k)$, with $k$ denoting iterations, provably converge to the centralized estimate $\hat{\mathbf{s}}$ in (1); see also Section 6.

To facilitate application of ADMM, consider the auxiliary variables ${\cal Z}:=\{\mathbf{z}_{i}^{j}\}_{j\in{\cal N}_{i}}$, and reparameterize the constraints in (2) with the equivalent ones

where the constant $c>0$ is a penalty coefficient. To minimize (2), ADMM entails an iterative procedure comprising three steps per iteration $k=1,2,\ldots$

where $i=1,\ldots,n$ and $j\in{\cal N}_{i}$ in [S1]. Reformulating the generic learning problem (1) as (2) renders the augmented Lagrangian in (2) highly decomposable. The separability comes in two flavors, both with respect to the sets ${\cal S}$ and ${\cal Z}$ of primal variables, as well as across nodes $i=1,\ldots,n$. This in turn leads to highly parallelized, simplified recursions corresponding to the aforementioned steps [S1]-[S3]. Specifically, as detailed in e.g., srg08tsp ; sgrr08tsp ; SMG_D_LMS ; pfacgg10jmlr ; mateos_dlasso ; mmg13tsp , it follows that if the multipliers are initialized to zero, the ADMM-based decentralized algorithm reduces to the following updates carried out locally at every node {svgraybox} In-network learning algorithm at node $i$, for $k=1,2,\ldots$:

where ${\bf v}_{i}(k):=2\sum_{j\in{\cal N}_{i}}\bar{{\bf v}}_{i}^{j}(k)$, and all initial values are set to zero.

Recursions (5) and (6) entail local updates, which comprise the general purpose ADMM-based decentralized learning algorithm. The inherently redundant set of auxiliary variables in ${\cal Z}$ and corresponding multipliers have been eliminated. Each node, say the $i$-th one, does not need to separately keep track of all its non-redundant multipliers $\{\bar{{\mathbf{v}}}_{i}^{j}(k)\}_{j\in{\cal N}_{i}}$, but only to update the (scaled) sum ${\mathbf{v}}_{i}(k)$. In the end, node $i$ has to store and update only two $p$-dimensional vectors, namely $\{{\bf s}_{i}(k)\}$ and $\{{\bf v}_{i}(k)\}$. A unique feature of in-network processing is that nodes communicate their updated local estimates $\{{\bf s}_{i}\}$ (and not their raw data ${\bf y}_{i}$) with their neighbors, in order to carry out the tasks (5)-(6) for the next iteration.

As elaborated in Section 6, under mild assumptions on the local costs one can establish that $\lim_{k\to\infty}{\bf s}_{i}(k)=\hat{{\bf s}}$, for $i=1,\ldots,n$. As a result, the algorithm asymptotically attains consensus and the performance of the centralized estimator [cf. (1)].

Batch In-Network Estimation and Inference

Many workhorse estimation schemes such as maximum likelihood estimation (MLE), least-squares estimation (LSE), best linear unbiased estimation (BLUE), as well as linear minimum mean-square error estimation (LMMSE) and the maximum a posteriori (MAP) estimation, all can be formulated as a minimization task similar to (1); see e.g. Estimation_Theory . However, the corresponding centralized estimation algorithms fall short in settings where both the acquired measurements and computational capabilities are distributed among multiple spatially scattered sensing nodes, which is the case with WSNs. Here we outline a novel batch decentralized optimization framework building on the ideas in Section 2, that formulates the desired estimator as the solution of a separable constrained convex minimization problem tackled via ADMM; see e.g., bertsi97book ; Boyd_ADMM ; srg08tsp ; sgrr08tsp for further details on the algorithms outlined here.

Depending on the estimation technique utilized, the local cost functions $f_{i}(\cdot)$ in (1) should be chosen accordingly, see e.g., Estimation_Theory ; srg08tsp ; sgrr08tsp . For instance, when $\mathbf{s}$ is assumed to be an unknown deterministic vector, then:

If $\hat{\mathbf{s}}$ corresponds to the centralized MLE then $f_{i}(\mathbf{s};\mathbf{y}_{i})=-\ln[p_{i}(\mathbf{y}_{i};\mathbf{s})]$ is the negative log-likelihood capturing the data probability density function (pdf), while the network-wide data $\{\mathbf{y}_{i}\}_{i=1}^{n}$ are assumed statistically independent.

If $\hat{\mathbf{s}}$ corresponds to the BLUE (or weighted least-squares estimator) then $f_{i}(\mathbf{s};\mathbf{y}_{i})=(1/2)\|\bm{\Sigma}_{y_{i}}^{-1/2}(\mathbf{y}_{i}-\mathbf{H}_{i}\mathbf{s})\|^{2}$, where $\bm{\Sigma}_{y_{i}}$ denotes the covariance of the data $\mathbf{y}_{i}$, and $\mathbf{H}_{i}$ is a known fitting matrix.

When $\mathbf{s}$ is treated as a random vector, then:

If $\hat{\mathbf{s}}$ corresponds to the centralized MAP estimator then $f_{i}(\mathbf{s};\mathbf{y}_{i})=-(\ln[p_{i}(\mathbf{y}_{i}|\mathbf{s})]+n^{-1}\ln[p(\mathbf{s})])$ accounts for the data pdf, and $p(\mathbf{s})$ for the prior pdf of $\mathbf{s}$, while data $\{\mathbf{y}_{i}\}_{i=1}^{n}$ are assumed conditionally independent given $\mathbf{s}$.

If $\hat{\mathbf{s}}$ corresponds to the centralized LMMSE then $f_{i}(\mathbf{s};\mathbf{y}_{i})=(1/2)\|\mathbf{s}-n\bm{\Sigma}_{sy_{i}}\mathbf{u}^{i}\|_{2}^{2}$, where $\bm{\Sigma}_{sy_{i}}$ denotes the cross-covariance of $\mathbf{s}$ with $\mathbf{y}_{i}$, while $\mathbf{u}^{i}$ stands for the $i$-th $m_{i}\times 1$ block subvector of $\mathbf{u}=\bm{\Sigma}_{y}^{-1}\mathbf{y}$.

Substituting in (6) the specific $f_{i}(\mathbf{s};\mathbf{y}_{i})$ for each of the aforementioned estimation tasks, yields a family of batch ADMM-based decentralized estimation algorithms. The decentralized BLUE algorithm will be described in this section as an example of decentralized linear estimation.

Recent advances in cyber-physical systems have also stressed the need for decentralized nonlinear least-squares (LS) estimation. Monitoring the power grid for instance, is challenged by the nonconvexity arising from the nonlinear AC power flow model; see e.g., (Wollenberg-book, , Ch. 4), while the interconnection across local transmission systems motivates their operators to collaboratively monitor the global system state. Interestingly, this nonlinear (specifically quadratic) estimation task can be convexified to a semidefinite program (SDP) (Boyd_Convex, , pg. 168), for which a decentralized semidefinite programming (SDP) algorithm can be developed by leveraging the batch ADMM; see also Wen2010 for an ADMM-based centralized SDP precursor.

The minimization involved in (6) can be performed locally at sensor $i$ by employing numerical optimization techniques Boyd_Convex . There are cases where the minimization in (6) yields a closed-form and easy to implement updating formula for $\mathbf{s}_{i}(k+1)$. If for example network nodes wish to find the BLUE estimator in a distributed fashion, the local cost is $f_{i}(\mathbf{s};\mathbf{y}_{i})=(1/2)\|\bm{\Sigma}_{y_{i}}^{-1/2}(\mathbf{y}_{i}-\mathbf{H}_{i}\mathbf{s})\|^{2}$, and (6) becomes a strictly convex unconstrained quadratic program which admits the following closed-form solution (see details in srg08tsp ; MSG_D_RLS )

The pair (5) and (7) comprise the decentralized (D-) BLUE algorithm sg06asilomar ; srg08tsp . For the special case where each node acquires unit-variance scalar observations $y_{i}$, there is no fitting matrix and $s$ is scalar (i.e., $p=1$); D-BLUE offers a decentralized algorithm to obtain the network-wide sample average $\hat{s}=(1/n)\sum_{i=1}^{n}y_{i}$. The update rule for the local estimate is obtained by suitably specializing (7) to

Different from existing distributed averaging approaches Barbarossa_Scu_Coupled_Osci ; dimakis10 ; Consensus_Averaging ; xbk07jpdc , the ADMM-based one originally proposed in sg06asilomar ; srg08tsp allows the decentralized computation of general nonlinear estimators that may be not available in closed form and cannot be expressed as “averages.” Further, the obtained recursions exhibit robustness in the presence of additive noise in the inter-node communication links.

Decentralized SDP

where the positive-semidefiniteness and rank constraints ensure that each matrix ${\bf S}_{i}$ is an outer-product matrix. By dropping the non-convex rank constraints, the problem (3.1) becomes a convex semidefinite program (SDP), which can be solved in a decentralized fashion by adopting the batch ADMM iterations (5) and (6).

This decentralized SDP approach has been successfully employed for monitoring large-scale power networks gg_spmag13 . To estimate the complex voltage phasor all nodes (a.k.a. power system state), measurements are collected on real/reactive power and voltage magnitude, all of which have quadratic dependence on the unknown states. Gauss-Newton iterations have been the ‘workhorse’ tool for this nonlinear estimation problem; see e.g., SE_book ; Wollenberg-book . However, the iterative linearization therein could suffer from convergence issues and local optimality, especially due to the increasing variability in power grids with high penetration of renewables. With improved communication capabilities, decentralized state estimation among multiple control centers has attracted growing interest; see Fig. 1 illustrating three interconnected areas aiming to achieve the centralized estimation collaboratively.

A decentralized SDP-based state estimator has been developed in hzgg_jstsp14 with reduced complexity compared to (3.1). The resultant algorithm involves only internal voltages and those of next-hop neighbors in the local matrix ${\bf S}_{(i)}$; e.g., in Fig. 1 ${\bf S}_{(1)}$ is identified by the dashed lines. Interestingly, the positive-semidefiniteness constraint for the overall ${\bf S}$ decouples nicely into that of all local $\{{\bf S}_{i}\}$, and the estimation error converges to the centralized performance within only a dozen iterations. The decentralized SDP framework has successfully addressed a variety of power system operational challenges, including a distributed microgrid optimal power flow solver in edhzgg_tsg13 ; see also gg_spmag13 for a tutorial overview of these applications.

2 Decentralized Inference

Along with decentralized signal parameter estimation, a variety of inference tasks become possible by relying on the collaborative sensing and computations performed by networked nodes. In the special context of resource-constrained WSNs deployed to determine the common messages broadcast by a wireless AP, the relatively limited node reception capability makes it desirable to design a decentralized detection scheme for all sensors to attain sufficient statistics for the global problem. Another exciting application of WSNs is environmental monitoring for e.g., inferring the presence or absence of a pollutant over a geographical area. Limited by the local sensing capability, it is important to develop a decentralized learning framework such that all sensors can collaboratively approach the performance as if the network wide data had been available everywhere (or at a FC for that matter). Given the diverse inference tasks, the challenge becomes how to design the best inter-node information exchange schemes that would allow for minimal communication and computation overhead in specific applications.

Message decoding. A decentralized detection framework is introduced here for the message decoding task, which is relevant for diverse wireless communications and networking scenarios. Consider an AP broadcasting a $p\times 1$ coded block ${\bf s}$ to a network of sensors, all of which know the codebook ${\mathcal{C}}$ that ${\bf s}$ belongs to. For simplicity assume binary codewords, and that each node $i=1,\ldots,n$ receives a same-length block of symbols ${\bf y}_{i}$ through a discrete, memoryless, symmetric channel that is conditionally independent across sensors. Sensor $i$ knows its local channel from the AP, as characterized by the conditional pdf $p(y_{il}|s_{l})$ per bit $l$. Due to conceivably low signal-to-noise-ratio (SNR) conditions, each low-cost sensor may be unable to reliably decode the message. Accordingly, the need arises for information exchanges among single-hop neighboring sensors to achieve the global (that is, centralized) error performance. Given ${\bf y}_{i}$ per sensor $i$, the assumption on memoryless and independent channels yields the centralized maximum-likelihood (ML) decoder as

ML decoding amounts to deciding the most likely codeword among multiple candidate ones and, in this sense, it can be viewed as a test of multiple hypotheses. In this general context, belief propagation approaches have been developed in sas06tsp , so that all nodes can cooperate to learn the centralized likelihood per hypothesis. However, even for linear binary block codes, the number of hypotheses, namely the cardinality of ${\mathcal{C}}$, grows exponentially with the codeword length. This introduces high communication and computation burden for the low-cost sensor designs.

The key here is to extract minimal sufficient statistics for the centralized decoding problem. For binary codes, the log-likelihood terms in (10) become $\log p(y_{il}|s_{l})=-\gamma_{il}s_{l}+\log p(y_{il}|s_{l}=0)$, where

is the local log-likelihood ratio (LLR) for the bit $s_{l}$ at sensor $i$. Ignoring all constant terms $\log p(y_{il}|s_{l}=0)$, the ML decoding objective ends up only depending on the sum LLRs, as given by $\hat{{\bf s}}_{ML}=\arg\min_{{\bf s}\in{\mathcal{C}}}\sum_{l=1}^{p}(\sum_{i=1}^{n}\gamma_{il})s_{l}$. Clearly, the sufficient statistic for solving (10) is the sum of all local LLR terms, or equivalently, the average $\bar{\gamma}_{l}=(1/n)\sum_{i=1}^{n}\gamma_{il}$ for each bit $l$. Interestingly, the average of $\{\gamma_{il}\}_{i=1}^{n}$ is one instance of the BLUE discussed in Section 3.1 when $\bm{\Sigma}_{y,i}={\bf H}_{j}={\bf I}_{p\times p}$, since

This way, the ADMM-based decentralized learning framework in Section 2 allows for all sensors to collaboratively attain the sufficient statistic for the decoding problem (10) via in-network processing. Each sensor only needs to estimate a vector of the codeword length $p$, which bypasses the exponential complexity under the framework of belief propagation. As shown in hzggac08tsp , decentralized soft decoding is also feasible since the a posteriori probability (APP) evaluator also relies on LLR averages which are sufficient statistics, where extensions to non-binary alphabet codeword constraints and random failing inter-sensor links are also considered.

The bit error rate (BER) versus SNR plot in Fig. 2 demonstrates the performance of ADMM-based in-network decoding of a convolutional code with $p=60$ and $|{\mathcal{C}}|=40$. This numerical test involves $n=10$ sensors and AWGN AP-sensor channels with $\sigma_{i}^{2}=10^{-SNR_{i}/10}$. Four schemes are compared: (i) the local ML decoder based on per-sensor data only (corresponds to the curve marked as $k=0$ since it is used to initialize the decentralized iterations); (ii) the centralized benchmark ML decoder (corresponds to $k=\infty$); (iii) the in-network decoder which forms $\bar{\gamma}_{l}$ using “consensus-averaging” linear iterations Consensus_Averaging ; and, (iv) the ADMM-based decentralized algorithm. Indeed, the ADMM-based decoder exhibits faster convergence than its consensus-averaging counterpart; and surprisingly, only 10 iterations suffice to bring the decentralized BER very close to the centralized performance.

Message demodulation. In a related detection scenario the common AP message ${\bf s}$ can be mapped to a space-time matrix, with each entry drawn from a finite alphabet ${\mathcal{A}}$. The received block ${\bf y}_{i}$ per sensor $i$ typically admits a linear input/output relationship {\bf y}_{i}={\mathbf{H}}_{i}~{}{\bf s}+{\mbox{\boldmath\epsilon}}_{i}. Matrix ${\mathbf{H}}_{i}$ is formed from the fading AP-sensor channel, and {\mbox{\boldmath\epsilon}}_{i} stands for the additive white Gaussian noise of unit variance, that is assumed uncorrelated across sensors. Since low-cost sensors have very limited budget on number of antennas compared to the AP, the length of ${\bf y}_{i}$ is much shorter than ${\bf s}$ (i.e., $m_{i}<p$). Hence, the local linear demodulator using $\{{\bf y}_{i},{\mathbf{H}}_{i}\}$ may not even be able to identify ${\bf s}$. Again, it is critical for each sensor $i$ to cooperate with its neighbors to collectively form the global ML demodulator

where ${\bf r}_{i}:={\mathbf{H}}_{i}^{\top}{\bf y}_{i}$ and ${\bf R}_{i}:={\mathbf{H}}_{i}^{\top}{\mathbf{H}}_{i}$ are the sample (cross-)covariance terms. To solve (13) locally, it suffices for each sensor to acquire the network-wide average of $\{{\bf r}_{i}\}_{i=1}^{n}$, as well as that of $\{{\bf R}_{i}\}_{i=1}^{n}$, as both averages constitute the minimal sufficient statistics for the centralized demodulator. Arguments similar to decentralized decoding lead to ADMM iterations that (as with BLUE) attain locally these average terms. These iterations constitute a viable decentralized demodulation method, whose performance analysis in hzacgg10twc reveals that its error diversity order can approach the centralized one within only a dozen of iterations.

As demonstrated by the decoding and demodulation tasks, the cornerstone of developing a decentralized detection scheme is to extract the minimal sufficient statistics for the centralized hypothesis testing problem. This leads to significant complexity reduction in terms of communications and computational overhead.

Decentralized Support Vector Machines

The merits of support vector machines (SVMs) in a centralized setting have been well documented in various supervised classification tasks including surveillance, monitoring, and segmentation, see e.g., smola . These applications often call for decentralized supervised learning solutions, when limited training data are acquired at different locations and a central processing unit is costly or even discouraged due to, e.g., scalability, communication overhead, or privacy reasons. Noteworthy examples include WSNs for environmental or structural health monitoring, as well as diagnosis of medical conditions from patient’s records distributed at different hospitals.

where the slack variables $\xi_{il}$ account for non-linearly separable training sets, and $C$ is a tunable positive scalar that allows for controlling model complexity. Nonlinear discriminant functions $g({\mathbf{x}})$ can also be accommodated after mapping input vectors ${\mathbf{x}}_{il}$ to a higher- (possibly infinite)-dimensional space using e.g., kernel functions, and pursuing a generalized maximum-margin linear classifier as in (14). Since the SVM classifier (14) couples the local datasets, early distributed designs either rely on a centralized processor so they are not decentralized van08dpsvm , or, their performance is not guaranteed to reach that of the centralized SVM navia06dsvm .

A fresh view of decentralized SVM classification is taken in pfacgg10jmlr , which reformulates (14) to estimate the parameter pair $\{{\mathbf{s}},b\}$ from all local data ${\mathcal{T}}_{i}$ after eliminating slack variables $\xi_{il}$, namely

Notice that (15) has the same decomposable structure that the general decentralized learning task in (1), upon identifying the local cost $f_{i}(\bar{{\mathbf{s}}};{\mathbf{y}}_{i})=\frac{1}{2n}\left\|{\mathbf{s}}\right\|^{2}+C\sum_{l=1}^{m_{i}}\max\{0,1-y_{il}({\mathbf{s}}^{\top}{\mathbf{x}}_{il}+b)\}$, where $\bar{{\mathbf{s}}}:=[{\mathbf{s}}^{\top},b^{\top}]^{\top}$, and ${\mathbf{y}}_{i}:=[y_{i1},\ldots,y_{im_{i}}]^{\top}$. Accordingly, all network nodes can solve (15) in a decentralized fashion via iterations obtained following the ADMM-based algorithmic framework of Section 2. Such a decentralized ADMM-DSVM scheme is provably convergent to the centralized SVM classifier (14), and can also incorporate nonlinear discriminant functions as detailed in pfacgg10jmlr .

To illustrate the performance of the ADMM-DSVM algorithm in pfacgg10jmlr , consider a randomly generated network with $n=30$ nodes. Each node acquires labeled training examples from two different classes, which are equiprobable and consist of random vectors drawn from a two-dimensional (i.e., $p=2$) Gaussian distribution with common covariance matrix $\bm{\Sigma}_{x}=[1,\;0;\;0,\;2]$, and mean vectors {\mbox{\boldmath\mu}}_{1}=[-1,\;-1]^{\top} and {\mbox{\boldmath\mu}}_{2}=[1,\;1]^{\top}, respectively. The Bayes optimal classifier for this 2-class problem is linear (duda, , Ch. 2). To visualize this test case, Fig. 3 depicts the global training set, along with the linear discriminant functions found by the centralized SVM (14) and the ADMM-DSVM at two different nodes after 400 iterations. Local SVM results for two different nodes are also included for comparison. It is apparent that ADMM-DSVM approaches the decision rule of its centralized counterpart, whereas local classifiers deviate since they neglect most of the training examples in the network.

Decentralized Clustering

Unsupervised learning using a network of wireless sensors as an exploratory infrastructure is well motivated for inferring hidden structures in distributed data collected by the sensors. Different from supervised SVM-based classification tasks, each node $i=1,\ldots,n$ has available a set of unlabeled observations ${\mathcal{X}}_{i}:=\{{\mathbf{x}}_{il},\;l=1,\ldots,m_{i}\}$, drawn from a total of $K$ classes. In this network setting, the goal is to design local clustering rules assigning each ${\mathbf{x}}_{il}$ to a cluster $k\in\{1,\ldots,K\}$. Again, the desiderata is a decentralized algorithm capable of attaining the performance of a benchmark clustering scheme, where all $\{{\mathcal{X}}_{i}\}_{i=1}^{n}$ are centrally available for joint processing.

Various criteria are available to quantify similarity among observations in a centralized setting, and a popular selection is the deterministic partitional clustering (DPC) one entailing prototypical elements (a.k.a. cluster centroids) per class in order to avoid comparisons between every pair of observations. Let {\mbox{\boldmath\mu}}_{k} denote the prototype element for class $k$, and $\nu_{ilk}$ the membership coefficient of ${\mathbf{x}}_{il}$ to class $k$. A natural clustering problem amounts to specifying the family of $K$ clusters with centroids \{{\mbox{\boldmath\mu}}_{k}\}_{k=1}^{K}, such that the sum of squared-errors is minimized; that is

where $\rho\geq 1$ is a tuning parameter, and ${\mathcal{V}}:=\{\nu_{ilk}:\sum_{k}\nu_{ilk}^{\rho}=1,\;\nu_{ilk}\in,\;\forall i,l\}$ denotes the convex set of constraints on all membership coefficients. With $\rho=1$ and \{{\mbox{\boldmath\mu}}_{k}\} fixed, (16) becomes a linear program in $\nu_{ilk}$. Consequently, (16) admits binary $\{0,1\}$ optimal solutions giving rise to the so-termed hard assignments, by choosing the cluster $k$ for ${\mathbf{x}}_{il}$ whenever $\nu_{ilk}=1$. Otherwise, for $\rho>1$ the optimal coefficients generally result in soft membership assignments, and the optimal cluster is $k^{*}:=\arg\max_{k}\nu_{ilk}^{\rho}$ for ${\mathbf{x}}_{il}$. In either case, the DPC clustering problem (16) is NP-hard, which motivates the (suboptimal) K-means algorithm that, on a per iteration basis, proceeds in two-steps to minimize the cost in (16) w.r.t.: (S1) ${\mathcal{V}}$ with \{{\mbox{\boldmath\mu}}_{k}\} fixed; and (S2) \{{\mbox{\boldmath\mu}}_{k}\} with ${\mathcal{V}}$ fixed lloyd82PCM . Convergence of this two-step alternating-minimization scheme is guaranteed at least to a local minimum. Nonetheless, K-means requires central availability of global information (those variables that are fixed per step), which challenges in-network implementations. For this reason, most early attempts are either confined to specific communication network topologies, or, they offer no closed-form local solutions; see e.g., Nowak03dem ; whk08ICML .

To address these limitations, pfacgg11jstsp casts (16) [yet another instance of (1)] as a decentralized estimation problem. It is thus possible to leverage ADMM iterations and solve (16) in a decentralized fashion through information exchanges among single-hop neighbors only. Albeit the non-convexity of (16), the decentralized DPC iterations in pfacgg11jstsp provably approach a local minimum arbitrarily closely, where the asymptotic convergence holds for hard K-means with $\rho=1$. Further extensions in pfacgg11jstsp include a decentralized expectation-maximization algorithm for probabilistic partitional clustering, and methods to handle unknown number of classes.

Clustering of oceanographic data. Environmental monitoring is a typical application of WSNs. In WSNs deployed for oceanographic monitoring, the cost of computation per node is lower than the cost of accessing each node’s observations oceansensors . This makes the option of centralized processing less attractive, thus motivating decentralized processing. Here we test the decentralized DPC schemes of pfacgg11jstsp on real data collected by multiple underwater sensors in the Mediterranean coast of Spain WOD , with the goal of identifying regions sharing common physical characteristics. A total of $5,720$ feature vectors were selected, each having entries the temperature (∘C) and salinity (psu) levels ($p=2$). The measurements were normalized to have zero mean, unit variance, and they were grouped in $n=20$ blocks (one per sensor) of $m_{i}=286$ measurements each. The algebraic connectivity of the WSN is 0.2289 and the average degree per node is 4.9. Fig. 4 (left) shows the performance of 25 Monte Carlo runs for the hard-DKM algorithm with different values of the parameter $c:=\eta$. The best average convergence rate was obtained for $\eta=5$, attaining the average centralized performance after 300 iterations. Tests with different values of $K$ and $\eta$ are also included in Fig. 4 (left) for comparison. Note that for $K=2$ and $\eta=5$ hard-DKM hovers around a point without converging. Choosing a larger $\eta$ guarantees convergence of the algorithm to a unique solution. The clustering results of hard-DKM at $k=400$ iterations for $\eta=5$ and $K=3$ are depicted in Fig. 4 (right).

Decentralized Adaptive Estimation

Sections 2 and 3 dealt with decentralized batch estimation, whereby network nodes acquire data only once and then locally exchange messages to reach consensus on the desired estimators. In many applications however, networks are deployed to perform estimation in a constantly changing environment without having available a complete statistical description of the underlying processes of interest, e.g., with time-varying thermal or seismic sources. This motivates the development of decentralized adaptive estimation schemes, where nodes collect data sequentially in time and local estimates are recursively refined “on-the-fly.” In settings where statistical state models are available, it is prudent to develop model-based tracking approaches implementing in-network Kalman or particle filters. Next, Section 2’s scope is broadened to facilitate real-time (adaptive) processing of network data, when the local costs in (1) and unknown parameters are allowed to vary with time.

For the cases where the auto- and cross-covariance matrices $\bm{\Sigma}_{H}$ and $\bm{\Sigma}_{Hy}$ are unknown, the approach followed here to develop the decentralized (D-) LMS algorithm includes two main building blocks: (i) recast (17) into an equivalent form amenable to in-network processing via the ADMM framework of Section 2; and (ii) leverage stochastic approximation iterations kushner to obtain an adaptive LMS-like algorithm that can handle the unavailability/variation of statistical information. Following those algorithmic construction steps outlined in Section 2, the following updating recursions are obtained for the multipliers $\mathbf{v}_{i}(t)$ and the local estimates $\mathbf{s}_{i}(t+1)$ at time instant $t+1$ and $i=1,\ldots,n$

It is apparent that after differentiating (19) and setting the gradient equal to zero, $\mathbf{s}_{i}(t+1)$ can be obtained as the root of an equation of the form

where $\bm{\varphi}$ corresponds to the stochastic gradient of the cost in (19). However, the previous equation cannot be solved since the nodes do not have available any statistical information about the acquired data. Inspired by stochastic approximation techniques (such as the celebrated Robbins-Monro algorithm; see e.g.,(kushner, , Ch. 1)) which iteratively find the root of (20) given noisy observations $\{\bm{\varphi}(\mathbf{s}_{i}(t),y_{i}(t+1),\mathbf{h}_{i}(t+1))\}_{t=0}^{\infty}$, one can just drop the unknown expected value to obtain the following D-LMS (i.e., stochastic gradient) updates

where $\mu$ denotes a constant step-size, and $e_{i}(t+1):=2[y_{i}(t+1)-\mathbf{h}_{i}^{\top}(t+1)\mathbf{s}_{i}(t)]$ is twice the local a priori error.

Recursions (18) and (21) constitute the D-LMS algorithm, which can be viewed as a stochastic-gradient counterpart of D-BLUE in Section 3.1. D-LMS is a pioneering approach for decentralized online learning, which blends for the first time affordable (first-order) stochastic approximation steps with parallel ADMM iterations. The use of a constant step-size $\mu$ endows D-LMS with tracking capabilities. This is desirable in a constantly changing environment, within which e.g., WSNs are envisioned to operate. The D-LMS algorithm is stable and converges even in the presence of inter-node communication noise (see details in SMG_D_LMS ; MSG_D_LMS ). Further, closed-form expressions for the evolution and the steady-state mean-square error (MSE), as well as selection guidelines for the step-size $\mu$ can be found in MSG_D_LMS .

2 Decentralized Recursive Least-Squares

The recursive least-squares (RLS) algorithm has well-appreciated merits for reducing complexity and storage requirements, in online estimation of stationary signals, as well as for tracking slowly-varying nonstationary processes sk95book ; Estimation_Theory . RLS is especially attractive when the state and/or data model are not available (as with LMS), and fast convergence rates are at a premium. Compared to the LMS scheme, RLS typically offers faster convergence and improved estimation performance at the cost of higher computational complexity. To enable these valuable tradeoffs in the context of in-network processing, the ADMM framework of Section 2 is utilized here to derive a decentralized (D-) RLS adaptive scheme that can be employed for distributed localization and power spectrum estimation (see also MSG_D_RLS ; MG_D_RLS for further details on the algorithmic construction and convergence claims).

Consider the data setting and linear regression task in Section 4.1. The RLS estimator for the unknown parameter $\mathbf{s}_{0}(t)$ minimizes the exponentially weighted least-squares (EWLS) cost, see e.g., sk95book ; Estimation_Theory

where $\gamma\in(0,1]$ is a forgetting factor, while the positive definite matrix $\bm{\Phi}_{0}$ is included for regularization. Note that in forming the EWLS estimator at time $t$, the entire history of data $\{y_{i}(\tau),\mathbf{h}_{i}(\tau)\}_{\tau=0}^{t}$ for $i=1,\ldots,n$ is incorporated in the online estimation process. Whenever $\gamma<1$, past data are exponentially discarded thus enabling tracking of nonstationary processes.

Again to decompose the cost function in (22), in which summands are coupled through the global variable $\mathbf{s}$, we introduce auxiliary variables $\{\mathbf{s}_{i}\}_{i=1}^{n}$ that represent local estimates per node $i$. These local estimates are utilized to form the convex constrained and separable minimization problem in (2), which can be solved using ADMM to yield the following decentralized iterations (details in MSG_D_RLS ; MG_D_RLS )

where $\bm{\Phi}_{i}(t+1):=\sum_{\tau=0}^{t+1}\gamma^{t+1-\tau}\mathbf{h}_{i}(\tau)\mathbf{h}_{i}^{\top}(\tau)+n^{-1}\gamma^{t+1}\bm{\Phi}_{0}$ and

The D-RLS recursions (23) and (24) involve similar inter-node communication exchanges as in D-LMS. It is recommended to initialize the matrix recursion with $\bm{\Phi}_{i}^{-1}(0)=n\bm{\Phi}_{0}^{-1}:=\delta{\mathbf{I}}_{p}$, where $\delta>0$ is chosen sufficiently large sk95book . The local estimates in D-RLS converge in the mean-sense to the true $\mathbf{s}_{0}$ (time-invariant case), even when information exchanges are imperfect. Closed-form expressions for the bounded estimation MSE along with numerical tests and comparisons with the incremental RLS inc_RLS and diffusion RLS Diffusion_RLS algorithms can be found in MG_D_RLS .

Decentralized spectrum sensing using WSNs. A WSN application where the need for linear regression arises, is spectrum estimation for the purpose of environmental monitoring. Suppose sensors comprising a WSN deployed over some area of interest observe a narrowband source to determine its spectral peaks. These peaks can reveal hidden periodicities due to e.g., a natural heat or seismic source. The source of interest propagates through multi-path channels and is contaminated with additive noise present at the sensors. The unknown source-sensor channels may introduce deep fades at the frequency band occupied by the source. Thus, having each sensor operating on its own may lead to faulty assessments. The available spatial diversity to effect improved spectral estimates, can only be achieved via sensor collaboration as in the decentralized estimation algorithms presented in this chapter.

Let ${\theta}(t)$ denote the evolution of the source signal in time, and suppose that ${\theta}(t)$ can be modeled as an autoregressive (AR) process (Stoica_Book, , p. 106)

where $p$ is the order of the AR process, while $\{\alpha_{\tau}\}$ are the AR coefficients and $w(t)$ denotes driving white noise. The source propagates to sensor $i$ via a channel modeled as an FIR filter $C_{i}(z)=\sum_{l=0}^{L_{i}-1}c_{il}z^{-l}$, of unknown order $L_{i}$ and tap coefficients $\{c_{il}\}$ and is contaminated with additive sensing noise $\bar{\epsilon}_{i}(t)$ to yield the observation

Since $y_{i}(t)$ is an autoregressive moving average (ARMA) process, then Stoica_Book

Performance of the decentralized adaptive algorithms described so far is illustrated next, when applied to the aforementioned power spectrum estimation task. For the numerical experiments, an ad hoc WSN with $n=80$ sensors is simulated as a realization of a random geometric graph. The source-sensor channels corresponding to a few of the sensors are set so that they have a null at the frequency where the AR source has a peak, namely at $\omega=\pi/2$. Fig. 6 (left) depicts the actual power spectral density (PSD) of the source as well as the estimated PSDs for one of the sensors affected by a bad channel. To form the desired estimates in a distributed fashion, the WSN runs the local (L-) LMS and the D-LMS algorithm outlined in Section 4.1. The L-LMS is a non-cooperative scheme since each sensor, say the $i$th, independently runs an LMS adaptive filter fed by its local data $\{y_{i}(t),{\mathbf{h}}_{i}(t)\}$ only. The experiment involving D-LMS is performed under ideal and noisy inter-sensor links. Clearly, even in the presence of communication noise D-LMS exploits the spatial diversity available and allows all sensors to estimate accurately the actual spectral peak, whereas L-LMS leads the problematic sensors to misleading estimates.

For the same setup, Fig. 6 (right) shows the global learning curve evolution $\textrm{MSE}(t)=(1/n)\sum_{i=1}^{n}\|y_{i}(t)-{\mathbf{h}}_{i}^{\top}(t){\mathbf{s}}_{i}(t-1)\|^{2}$. The D-LMS and the D-RLS algorithms are compared under ideal communication links. It is apparent that D-RLS achieves improved performance both in terms of convergence rate and steady state MSE. As discussed in Section 4.2 this comes at the price of increased computational complexity per sensor, while the communication costs incurred are identical.

3 Decentralized Model-based Tracking

The decentralized adaptive schemes in Secs. 4.1 and 4.2 are suitable for tracking slowly time-varying signals in settings where no statistical models are available. In certain cases, such as target tracking, state evolution models can be derived and employed by exploiting the physics of the problem. The availability of such models paves the way for improved state tracking via Kalman filtering/smoothing techniques, e.g., see Opt_Filtering_Moore ; Estimation_Theory . Model-based decentralized Kalman filtering/smoothing as well as particle filtering schemes for multi-node networks are briefly outlined here.

Initial attempts to distribute the centralized KF recursions (see Olfati_Kalman and references in sgrr08tsp ) rely on consensus-averaging Consensus_Averaging . The idea is to estimate across nodes those sufficient statistics (that are expressible in terms of network-wide averages) required to form the corrected state and corresponding corrected state error covariance matrix. Clearly, there is an inherent delay in obtaining these estimates confining the operation of such schemes only to applications with slow-varying state vectors $\mathbf{s}_{0}(t)$, and/or fast communications needed to complete multiple consensus iterations within the time interval separating the acquisition of consecutive measurements $y_{i}(t)$ and $y_{i}(t+1)$. Other issues that may lead to instability in existing decentralized KF approaches are detailed in sgrr08tsp .

Instead of filtering, the delay incurred by those inner-loop consensus iterations motivated the consideration of fixed-lag decentralized Kalman smoothing (KS) in sgrr08tsp . Matching consensus iterations with those time instants of data acquisition, fixed-lag smoothers allow sensors to form local MMSE optimal smoothed estimates, which take advantage of all acquired measurements within the “waiting period.” The ADMM-enabled decentralized KS in sgrr08tsp also overcomes the noise-related limitations of consensus-averaging algorithms xbk07jpdc . In the presence of communication noise, these estimates converge in the mean sense, while their noise-induced variance remains bounded. This noise resiliency allows sensors to exchange quantized data further lowering communication cost. For a tutorial treatment of decentralized Kalman filtering approaches using WSNs (including the decentralized ADMM-based KS of sgrr08tsp and strategies to reduce the communication cost of state estimation problems), the interested reader is referred to dkf_control_mag . These reduced-cost strategies exploit the redundancy in information provided by individual observations collected at different sensors, different observations collected at different sensors, and different observations acquired at the same sensor.

On a related note, a collaborative algorithm is developed in cg_cartography to estimate the channel gains of wireless links in a geographical area. Kriged Kalman filtering (KKF) ripley , which is a tool with widely appreciated merits in spatial statistics and geosciences, is adopted and implemented in a decentralized fashion leveraging the ADMM framework described here. The distributed KKF algorithm requires only local message passing to track the time-variant so-termed “shadowing field” using a network of radiometers, yet it provides a global view of the radio frequency (RF) environment through consensus iterations; see also Section 5.3 for further elaboration on spectrum sensing carried out via wireless cognitive radio networks.

To wrap-up the discussion, consider a network of collaborating agents (e.g., robots) equipped with wireless sensors measuring distance and/or bearing from a target that they wish to track. Even if state models are available, the nonlinearities present in these measurements prevent sensors from employing the clairvoyant (linear) Kalman tracker discussed so far. In response to these challenges, dpf develops a set-membership constrained particle filter (PF) approach that: (i) exhibits performance comparable to the centralized PF; (ii) requires only communication of particle weights among neighboring sensors; and (iii) it can afford both consensus-based and incremental averaging implementations. Affordable inter-sensor communications are enabled through a novel distributed adaptation scheme, which considerably reduces the number of particles needed to achieve a given performance. The interested reader is referred to dpf_tutorial for a recent tutorial account of decentralized PF in multi-agent networks.

Decentralized Sparsity-regularized Rank Minimization

Modern network data sets typically involve a large number of attributes. This fact motivates predictive models offering a sparse, broadly meaning parsimonious, representation in terms of a few attributes. Such low-dimensional models facilitate interpretability and enhanced predictive performance. In this context, this section deals with ADMM-based decentralized algorithms for sparsity-regularized rank minimization. It is argued that such algorithms are key to unveiling Internet traffic anomalies given ubiquitous link-load measurements. Moreover, the notion of RF cartography is subsequently introduced to exemplify the development of a paradigm infrastructure for situational awareness at the physical layer of wireless cognitive radio (CR) networks. A (subsumed) decentralized sparse linear regression algorithm is outlined to accomplish the aforementioned cartography task.

where the sampling operator $\mathcal{P}_{\Omega}(.)$ sets the entries of its matrix argument not in $\Omega$ to zero, and keeps the rest unchanged. Since the objective here is not to estimate the OD flow traffic matrix ${\bf Z}$, (28) is expressed in terms of the nominal (anomaly-free) link-level traffic rates ${\bf X}:={\bf R}{\bf Z}$, which inherits the low-rank property of ${\bf Z}$. Anomalies in ${\bf A}$ are expected to occur sporadically over time, and last for a short time relative to the (possibly long) measurement interval $[1,T]$. In addition, only a small fraction of the flows is supposed to be anomalous at a any given time instant. This renders the anomaly matrix ${\bf A}$ sparse across rows (flows) and columns (time).

where $\lambda_{*},\lambda_{1}\geq 0$ are rank- and sparsity-controlling parameters. While a non-smooth optimization problem, (29) is appealing because it is convex. An efficient accelerated proximal gradient algorithm with quantifiable iteration complexity was developed to unveil network anomalies tit_recovery_2012 . Interestingly, (29) also offers a cleansed estimate of the link-level traffic $\hat{{\bf X}}$, that could be subsequently utilized for network tomography tasks. In addition, (29) jointly exploits the spatio-temporal correlations in link traffic as well as the sparsity of anomalies, through an optimal single-shot estimation-detection procedure that turns out to outperform the algorithms in lakhina and zggr05 (the latter decouple the estimation and detection steps); see Fig. 8.

2 In-network Traffic Anomaly Detection

Implementing (29) presumes that network nodes continuously communicate their link traffic measurements to a central monitoring station, which uses their aggregation in $\mathcal{P}_{\Omega}({\bf Y})$ to unveil anomalies. While for the most part this is the prevailing operational paradigm adopted in current networks, it is prudent to reflect on the limitations associated with this architecture. For instance, fusing all this information may entail excessive protocol overheads. Moreover, minimizing the exchanges of raw measurements may be desirable to reduce unavoidable communication errors that translate to missing data. Solving (29) centrally raises robustness concerns as well, since the central monitoring station represents an isolated point of failure.

These reasons prompt one to develop fully-decentralized iterative algorithms for unveiling traffic anomalies, and thus embed network anomaly detection functionality to the routers. As in Section 2, per iteration node $i$ carries out simple computational tasks locally, relying on its own link count measurements (a submatrix ${\bf Y}_{i}$ within ${\bf Y}:=[{\bf Y}_{1}^{\top},\ldots,{\bf Y}_{n}^{\top}]^{\top}$ corresponding to router $i$’s links). Subsequently, local estimates are refined after exchanging messages only with directly connected neighbors, which facilitates percolation of local information to the whole network. The end goal is for network nodes to consent on a global map of network anomalies $\hat{{\bf A}}$, and attain (or at least come close to) the estimation performance of the centralized counterpart (29) which has all data $\mathcal{P}_{\Omega}({\bf Y})$ available.

where the optimization is over all possible bilinear factorizations of ${\bf X}$, so that the number of columns $\rho$ of ${\bf P}$ and $\mathbf{Q}$ is also a variable. Leveraging (30), the following reformulation of (29) provides an important first step towards obtaining a decentralized algorithm for anomaly identification

which is non-convex due to the bilinear terms ${\bf P}_{i}{\bf Q}^{\top}$, and where ${\bf R}:=\left[{\bf R}_{1}^{\top},\ldots,{\bf R}_{n}^{\top}\right]^{\top}$ is partitioned into local routing tables available per router $i$. Adopting the separable Frobenius-norm regularization in (31) comes with no loss of optimality relative to (29), provided $\textrm{rank}(\hat{\bf X})\leq\rho$. By finding the global minimum of (31) [which could entail considerably less variables than (29)], one can recover the optimal solution of (29). But since (31) is non-convex, it may have stationary points which need not be globally optimum. As asserted in (mmg13tsp, , Prop. 1) however, if a stationary point $\{\bar{{\bf P}},\bar{{\bf Q}},\bar{{\bf A}}\}$ of (31) satisfies $\|\mathcal{P}_{\Omega}({\bf Y}-\bar{{\bf P}}\bar{{\bf Q}}^{\top}-\bar{{\bf A}})\|<\lambda_{*}$, then $\{\hat{\bf X}:=\bar{{\bf P}}\bar{{\bf Q}}^{\top},\hat{{\bf A}}:=\bar{{\bf A}}\}$ is the globally optimal solution of (29).

To decompose the cost in (31), in which summands inside the square brackets are coupled through the global variables $\{{\bf Q},{\bf A}\}$, one can proceed as in Section 2 and introduce auxiliary copies $\{{\bf Q}_{i},{\bf A}_{i}\}_{i=1}^{n}$ representing local estimates of $\{{\bf Q},{\bf A}\}$, one per node $i$. These local copies along with consensus constraints yield the decentralized estimator

which follows the general form in (2), and is equivalent to (31) provided the network topology graph is connected. Even though consensus is a fortiori imposed within neighborhoods, it carries over to the entire (connected) network and local estimates agree on the global solution of (31). Exploiting the separable structure of (32) using the ADMM, a general framework for in-network sparsity-regularized rank minimization was put forth in mmg13tsp . In a nutshell, local tasks per iteration $k=1,2,\ldots$ entail solving small unconstrained quadratic programs to refine the normal subspace ${\bf P}_{i}[k]$, in addition to soft-thresholding operations to update the anomaly maps ${\bf A}_{i}[k]$ per router. Routers exchange their estimates $\{{\bf Q}_{i}[k],{\bf A}_{i}[k]\}$ only with directly connected neighbors per iteration. This way the communication overhead remains affordable, regardless of the network size $n$.

When employed to solve non-convex problems such as (32), so far ADMM offers no convergence guarantees. However, there is ample experimental evidence in the literature that supports empirical convergence of ADMM, especially when the non-convex problem at hand exhibits “favorable” structure Boyd_ADMM . For instance, (32) is a linearly constrained bi-convex problem with potentially good convergence properties – extensive numerical tests in mmg13tsp demonstrate that this is indeed the case. While establishing convergence remains an open problem, one can still prove that upon convergence the distributed iterations attain consensus and global optimality, thus offering the desirable centralized performance guarantees mmg13tsp .

3 RF Cartography Via Decentralized Sparse Linear Regression

In the domain of spectrum sensing for CR networks, RF cartography amounts to constructing in a distributed fashion: i) global power spectral density (PSD) maps capturing the distribution of radiated power across space, time, and frequency; and ii) local channel gain (CG) maps offering the propagation medium per frequency from each node to any point in space cg_cartography . These maps enable identification of opportunistically available spectrum bands for re-use and handoff operation; as well as localization, transmit-power estimation, and tracking of primary user activities. While the focus here is on the construction of PSD maps, the interested reader is referred to tut_rf_cartog for a tutorial treatment on CG cartography.

Sparse total LS variants are also available to cope with uncertainty in the regression matrix, arising due to inaccurate channel estimation and grid-mismatch effects tut_rf_cartog . Nonparametric spline-based PSD map estimators rf_splines have been also shown effective in capturing general propagation characteristics including both shadowing and fading; see also Fig. 9 for an actual PSD atlas spanning $14$ frequency sub-bands.

Convergence Analysis

In this section we analyze the convergence and assess the rate of convergence for the decentralized ADMM algorithm outlined in Section 2. We focus on the batch learning setup, where the local cost functions are static.

where $c>0$ is a positive constant [cf. (2) back in Section 2].

Assumptions and scope of the convergence analysis. In the convergence analysis, we assume that (2) has at least a pair of primal-dual solutions. In addition, we make the following assumptions on the local cost functions $f_{i}$.

Assumption 1. The local cost functions $f_{i}$ are closed, proper, and convex.

Assumption 1 implies that the aggregate function $f({\mathbf{s}}):=\sum_{i=1}^{n}f_{i}({\mathbf{s}}_{i};{\mathbf{y}}_{i})$ is closed, proper, and convex. Assumption 2 ensures that the aggregate cost $f$ has Lipschitz gradients with constant $M_{f}$; thus, for any pair of points ${\mathbf{s}}_{a}$ and ${\mathbf{s}}_{b}$ it holds that

Assumption 3 guarantees that the aggregate cost $f$ is strongly convex with constant $m_{f}$; hence, for any pair of points ${\mathbf{s}}_{a}$ and ${\mathbf{s}}_{b}$ it holds that

Observe that Assumptions 2 and 3 imply that the local cost functions $f_{i}$ and the aggregate cost function $f$ are differentiable. Assumption 1 is sufficient to prove global convergence of the decentralized ADMM algorithm. To establish linear rate of convergence however, one further needs Assumptions 2 and 3.

2 Convergence

We consider convergence of ${\mathbf{u}}(k)$ to its optimum ${\mathbf{u}}^{*}:=[({\mathbf{s}}^{*})^{\top}\>(\bar{{\mathbf{v}}}^{*})^{\top}]^{\top}$, where $({\mathbf{s}}^{*},\bar{{\mathbf{v}}}^{*})$ is an optimal primal-dual pair. The analysis is based on several contraction inequalities, in which the distance is measured in the (pseudo) Euclidean norm with respect to the positive semi-definite matrix ${\mathbf{H}}$.

To situate the forthcoming results in context, notice that convergence of the centralized ADMM for constrained optimization problems has been proved in e.g., Eckstein1992 , and its ergodic $O(1/k)$ rate of convergence is established in He2012_SIAM ; Wang2013 . For non-ergodic convergence, He2012 proves an $O(1/k)$ rate, and Deng2014 improves the rate to $o(1/k)$. Observe that in He2012 ; Deng2014 the rate refers to the speed at which the difference between two successive primal-dual iterates vanishes, different from the speed that the primal-dual optimal iterates converge to their optima. Convergence of the decentralized ADMM is presented next in the sense that the primal-dual iterates converge to their optima. The analysis proceeds in four steps:

Show that $\|{\mathbf{u}}(k)-{\mathbf{u}}^{*}\|_{\mathbf{H}}^{2}$ is monotonic, namely, for all times $k\geq 0$ it holds that

Show that $\|{\mathbf{u}}(k+1)-{\mathbf{u}}(k)\|_{H}^{2}$ is monotonically non-increasing, that is

Derive an $O(1/k)$ rate in a non-ergodic sense based on (35) and (36), i.e.,

Prove that ${\mathbf{u}}(k):=[{\mathbf{s}}(k)^{\top}\>\bar{{\mathbf{v}}}(k)^{\top}]^{\top}$ converges to a pair of optimal primal and dual solutions of (6.1).

The first three steps are similar to those discussed in He2012 ; Deng2014 . Proving the last step is straightforward from the KKT conditions of (6.1). Under S1-S4, the main result establishing convergence of the decentralized ADMM is as follows.

Theorem 6.1 asserts that under proper initialization, convergence of the decentralized ADMM only requires the local costs $f_{i}$ to be closed, proper, and convex. However, it does not specify a pair of optimal primal and dual solutions of (6.1), which $({\mathbf{s}}(k),\bar{{\mathbf{v}}}(k))$ converge to. Indeed, ${\mathbf{s}}(k)$ can converge to one of the optimal primal solutions ${\mathbf{s}}^{*}$, and $\bar{{\mathbf{v}}}(k)$ can converge to one of the corresponding optimal dual solutions $\bar{{\mathbf{v}}}^{*}$. The limit $({\mathbf{s}}^{*},\bar{{\mathbf{v}}}^{*})$ is ultimately determined by the initial ${\mathbf{s}}(0)$ and $\bar{{\mathbf{v}}}(0)$. Indeed, the conditions in Theorem 6.1 also guarantee ergodic and non-ergodic $o(1/k)$ convergence rates in terms of objective error and successive iterate differences, as proved in the recent paper DavisYin2014 .

3 Linear Rate of Convergence

Linear rate of convergence for the centralized ADMM is established in Deng2012 , and for the decentralized ADMM in Shi2014 . Similar to the convergence analysis of the last section, the proof includes the following steps:

Show that $\|{\mathbf{u}}(k)-{\mathbf{u}}^{*}\|_{\mathbf{H}}^{2}$ is contractive, namely, for all times $k\geq 0$ it holds that

where $\delta>0$ is a constant [cf. (40)]. Note that the contraction inequality (38) implies Q-linear convergence of $\|{\mathbf{u}}(k)-{\mathbf{u}}^{*}\|_{\mathbf{H}}^{2}$.

Show that $\|{\mathbf{s}}(k+1)-{\mathbf{s}}^{*}\|_{\mathbf{H}}^{2}$ is R-linearly convergent since it is upper-bounded by a Q-linear convergent sequence, meaning

where $m_{f}$ is the strong convexity constant of the aggregate cost function $f$.

We now state the main result establishing linear rate of convergence for the decentralized ADMM algorithm.

Theorem 6.2 requires the local cost functions to be closed, proper, convex, strongly convex, and have Lipschitz gradients. In addition to the initialization dictated by Theorem 6.1, Theorem 6.2 further requires the initial multiplier $\bar{{\mathbf{v}}}(0)$ to lie in the column space of ${\mathbf{E}}_{o}$, which guarantees that $\bar{{\mathbf{v}}}(k)$ converges to $\bar{{\mathbf{v}}}^{*}$, the unique optimal dual solution lying in the column space of ${\mathbf{E}}_{o}$. The primal solution ${\mathbf{s}}(k)$ converges to ${\mathbf{s}}^{*}$, which is unique since the original cost function in (1) is strongly convex.

Observe from the contraction inequality (38) that the speed of convergence is determined by the contraction parameter $\delta$: A larger $\delta$ means stronger contraction and hence faster convergence. Indeed, Shi2014 give an explicit expression of $\delta$, that is

where $m_{f}$ is the strong convexity constant of $f$, $M_{f}$ is the Lipschitz continuity constant of $\nabla f$, $\gamma_{o}$ is the smallest nonzero eigenvalue of the oriented Laplacian ${\mathbf{L}}_{o}$, $\Gamma_{u}$ is the largest eigenvalue of the unoriented Laplacian ${\mathbf{L}}_{u}$, $c$ is the ADMM penalty parameter, and $\mu>1$ is an arbitrary constant.

As the current form of (40) does not offer insights on how the properties of the cost functions, the underlying network, and the ADMM parameter influence the speed of convergence, Ling2014 ; Shi2014 finds the largest value of $\delta$ by tuning the constant $\mu$ and the ADMM parameter $c$. Specifically, Ling2014 ; Shi2014 shows that

maximizes the right-hand side of (40), so that

The best contraction parameter $\delta$ is a function of the condition number $M_{f}/m_{f}$ of the aggregate cost function $f$, and the condition number of the graph $\Gamma_{u}/\gamma_{o}$. Note that we always have $\delta<1$, while small values of $\delta$ result when $M_{f}/m_{f}\gg 1$ or when $\Gamma_{u}/\gamma_{o}\gg 1$; that is, when either the cost function or the graph is ill conditioned. When the condition numbers are such that $\Gamma_{u}/\gamma_{o}\gg M_{f}^{2}/m_{f}^{2}$, the condition number of the graph dominates, and we obtain $\delta\approx\gamma_{o}/\Gamma_{u}$, implying that the contraction is determined by the condition number of the graph. When $M_{f}^{2}/m_{f}^{2}\gg\Gamma_{u}/\gamma_{o}$, the condition number of the cost dominates and we have $\delta\approx(m_{f}/M_{f})\sqrt{\gamma_{o}/\Gamma_{u}}$. In the latter case the contraction is constrained by both the condition number of the cost function, and the condition number of the graph.

Acknowledgements. The authors wish to thank the following friends, colleagues, and co-authors who contributed to their joint publications that the material of this chapter was extracted from: Drs. J.A. Bazerque, A. Cano, E. Dall’Anese, S. Farahmand, N. Gatsis, P. Forero, V. Kekatos, S.-J. Kim, M. Mardani, K. Rajawat, S. Roumeliotis, A. Ribeiro, W. Shi, G. Wu, W. Yin, and K. Yuan. The lead author (and while with SPiNCOM all co-authors) were supported in part from NSF grants 1202135, 1247885 1343248, 1423316, 1442686; the MURI Grant No. AFOSR FA9550-10-1-0567; and the NIH Grant No. 1R01GM104975-01.

References