The study of tail behaviour of \textbf{\texttt{SGD}}-induced processes has been attracting a lot of interest, due to offering strong guarantees with respect to individual runs of an algorithm. While many works provide high-probability guarantees, quantifying the error rate for a fixed probability threshold, there is a lack of work directly studying the probability of failure, i.e., quantifying the tail decay rate for a fixed error threshold. Moreover, existing results are of finite-time nature, limiting their ability to capture the true long-term tail decay which is more informative for modern learning models, typically trained for millions of iterations. Our work closes these gaps, by studying the long-term tail decay of \textbf{\texttt{SGD}}-based methods through the lens of large deviations theory, establishing several strong results in the process. First, we provide an upper bound on the tails of the gradient norm-squared of the best iterate produced by (vanilla) \textbf{\texttt{SGD}}, for non-convex costs and bounded noise, with long-term decay at rate $e^{-\frac{t}{\log(t)}}$. Next, we relax the noise assumption by considering clipped \textbf{\texttt{SGD}} (\textbf{\texttt{c-SGD}}) under heavy-tailed noise with bounded moment of order $p \in (1,2]$, showing an upper bound with long-term decay at rate $e^{-\frac{t^{\beta_p}}{\log(t)}}$, where $\beta_p = \frac{4(p-1)}{3p-2}$ for $p \in (1,2)$ and $e^{-\frac{t}{\log^2(t)}}$ for $p = 2$. Finally, we provide lower bounds on the tail decay, at rate $e^{-t}$, showing that our rates for both \textbf{\texttt{SGD}} and \textbf{\texttt{c-SGD}} are tight, up to poly-logarithmic factors. Notably, our results demonstrate \textit{an order of magnitude faster} long-term tail decay compared to existing work based on finite-time bounds, which show rates $e^{-\sqrt{t}}$ and $e^{-t^{\beta_p/2}}$, $p \in (1,2]$, for \textbf{\texttt{SGD}} and \textbf{\texttt{c-SGD}}, respectively. As such, we uncover regimes where the tails decay much faster than previously known, providing stronger long-term guarantees for individual runs.

We study high-probability convergence in online learning, in the presence of heavy-tailed noise. To combat the heavy tails, a general framework of nonlinear SGD methods is considered, subsuming several popular nonlinearities like sign, quantization, component-wise and joint clipping. In our work the nonlinearity is treated in a black-box manner, allowing us to establish unified guarantees for a broad range of nonlinear methods. For symmetric noise and non-convex costs we establish convergence of gradient norm-squared, at a rate $\widetilde{\mathcal{O}}(t^{-1/4})$, while for the last iterate of strongly convex costs we establish convergence to the population optima, at a rate $\mathcal{O}(t^{-\zeta})$, where $\zeta \in (0,1)$ depends on noise and problem parameters. Further, if the noise is a (biased) mixture of symmetric and non-symmetric components, we show convergence to a neighbourhood of stationarity, whose size depends on the mixture coefficient, nonlinearity and noise. Compared to state-of-the-art, who only consider clipping and require unbiased noise with bounded $p$-th moments, $p \in (1,2]$, we provide guarantees for a broad class of nonlinearities, without any assumptions on noise moments. While the rate exponents in state-of-the-art depend on noise moments and vanish as $p \rightarrow 1$, our exponents are constant and strictly better whenever $p < 6/5$ for non-convex and $p < 8/7$ for strongly convex costs. Experiments validate our theory, showing that clipping is not always the optimal nonlinearity, further underlining the value of a general framework.

The occlusion of the sun by clouds is one of the primary sources of uncertainties in solar power generation, and is a factor that affects the wide-spread use of solar power as a primary energy source. Real-time forecasting of cloud movement and, as a result, solar irradiance is necessary to schedule and allocate energy across grid-connected photovoltaic systems. Previous works monitored cloud movement using wide-angle field of view imagery of the sky. However, such images have poor resolution for clouds that appear near the horizon, which reduces their effectiveness for long term prediction of solar occlusion. Specifically, to be able to predict occlusion of the sun over long time periods, clouds that are near the horizon need to be detected, and their velocities estimated precisely. To enable such a system, we design and deploy a catadioptric system that delivers wide-angle imagery with uniform spatial resolution of the sky over its field of view. To enable prediction over a longer time horizon, we design an algorithm that uses carefully selected spatio-temporal slices of the imagery using estimated wind direction and velocity as inputs. Using ray-tracing simulations as well as a real testbed deployed outdoors, we show that the system is capable of predicting solar occlusion as well as irradiance for tens of minutes in the future, which is an order of magnitude improvement over prior work.

In this work, we present and study a low-precision variant of the stochastic gradient descent (SGD) algorithm with adaptive quantization. In particular, fixed-rate probabilistic uniform quantizers with varying quantization steps and mid-values are used to compress the parameter vectors. Gradient clipping and momentum are used to guarantee that the quantizer inputs fall within the representable region of the fixed-rate quantizer and to reduce the impact of the stochastic gradient noise, respectively. We show that, despite the low-precision representation, the quantized variant of the clipped SGD algorithm with momentum is able to converge in the mean-square-error sense. Simulation results illustrate the theoretical findings and the effectiveness of the proposed approach.

Recent works have shown that high probability metrics with stochastic gradient descent (SGD) exhibit informativeness and in some cases advantage over the commonly adopted mean-square error-based ones. In this work we provide a formal framework for the study of general high probability bounds with SGD, based on the theory of large deviations. The framework allows for a generic (not-necessarily bounded) gradient noise satisfying mild technical assumptions, allowing for the dependence of the noise distribution on the current iterate. Under the preceding assumptions, we find an upper large deviations bound for SGD with strongly convex functions. The corresponding rate function captures analytical dependence on the noise distribution and other problem parameters. This is in contrast with conventional mean-square error analysis that captures only the noise dependence through the variance and does not capture the effect of higher order moments nor interplay between the noise geometry and the shape of the cost function. We also derive exact large deviation rates for the case when the objective function is quadratic and show that the obtained function matches the one from the general upper bound hence showing the tightness of the general upper bound. Numerical examples illustrate and corroborate theoretical findings.

We propose a general approach for distance based clustering, using the gradient of the cost function that measures clustering quality with respect to cluster assignments and cluster center positions. The approach is an iterative two step procedure (alternating between cluster assignment and cluster center updates) and is applicable to a wide range of functions, satisfying some mild assumptions. The main advantage of the proposed approach is a simple and computationally cheap update rule. Unlike previous methods that specialize to a specific formulation of the clustering problem, our approach is applicable to a wide range of costs, including non-Bregman clustering methods based on the Huber loss. We analyze the convergence of the proposed algorithm, and show that it converges to the set of appropriately defined fixed points, under arbitrary center initialization. In the special case of Bregman cost functions, the algorithm converges to the set of centroidal Voronoi partitions, which is consistent with prior works. Numerical experiments on real data demonstrate the effectiveness of the proposed method.

Gradient-descent (GD) based algorithms are an indispensable tool for optimizing modern machine learning models. The paper considers distributed stochastic GD (D-SGD)--a network-based variant of GD. Distributed algorithms play an important role in large-scale machine learning problems as well as the Internet of Things (IoT) and related applications. The paper considers two main issues. First, we study convergence of D-SGD to critical points when the loss function is nonconvex and nonsmooth. We consider a broad range of nonsmooth loss functions including those of practical interest in modern deep learning. It is shown that, for each fixed initialization, D-SGD converges to critical points of the loss with probability one. Next, we consider the problem of avoiding saddle points. It is well known that classical GD avoids saddle points; however, analogous results have been absent for distributed variants of GD. For this problem, we again assume that loss functions may be nonconvex and nonsmooth, but are smooth in a neighborhood of a saddle point. It is shown that, for any fixed initialization, D-SGD avoids such saddle points with probability one. Results are proved by studying the underlying (distributed) gradient flow, using the ordinary differential equation (ODE) method of stochastic approximation.

In this paper, we propose a decentralized first-order stochastic optimization method Push-SAGA for finite-sum minimization over a strongly connected directed graph. This method features local variance reduction to remove the uncertainty caused by random sampling of the local gradients, global gradient tracking to address the distributed nature of the data, and push-sum consensus to handle the imbalance caused by the directed nature of the underlying graph. We show that, for a sufficiently small step-size, Push-SAGA linearly converges to the optimal solution for smooth and strongly convex problems, making it the first linearly-convergent stochastic algorithm over arbitrary strongly-connected directed graphs. We illustrate the behavior and convergence properties of Push-SAGA with the help of numerical experiments for strongly convex and non-convex problems.

This paper considers decentralized stochastic optimization over a network of $n$ nodes, where each node possesses a smooth non-convex local cost function and the goal of the networked nodes is to find an $\epsilon$-accurate first-order stationary point of the sum of the local costs. We focus on an online setting, where each node accesses its local cost only by means of a stochastic first-order oracle that returns a noisy version of the exact gradient. In this context, we propose a novel single-loop decentralized hybrid variance-reduced stochastic gradient method, called GT-HSGD, that outperforms the existing approaches in terms of both the oracle complexity and practical implementation. The GT-HSGD algorithm implements specialized local hybrid stochastic gradient estimators that are fused over the network to track the global gradient. Remarkably, GT-HSGD achieves a network topology-independent oracle complexity of $O(n^{-1}\epsilon^{-3})$ when the required error tolerance $\epsilon$ is small enough, leading to a linear speedup with respect to the centralized optimal online variance-reduced approaches that operate on a single node. Numerical experiments are provided to illustrate our main technical results.

This paper studies the resilient distributed recovery of large fields under measurement attacks, by a team of agents, where each measures a small subset of the components of a large spatially distributed field. An adversary corrupts some of the measurements. The agents collaborate to process their measurements, and each is interested in recovering only a fraction of the field. We present a field recovery consensus+innovations type distributed algorithm that is resilient to measurement attacks, where an agent maintains and updates a local state based on its neighbors states and its own measurement. Under sufficient conditions on the attacker and the connectivity of the communication network, each agent's state, even those with compromised measurements, converges to the true value of the field components that it is interested in recovering. Finally, we illustrate the performance of our algorithm through numerical examples.

Zeroth-order optimization algorithms are an attractive alternative for stochastic optimization problems, when gradient computations are expensive or when closed-form loss functions are not available. Recently, there has been a surge of activity in utilizing zeroth-order optimization algorithms in myriads of applications including black-box adversarial attacks on machine learning frameworks, reinforcement learning, and simulation-based optimization, to name a few. In addition to utilizing the simplicity of a typical zeroth-order optimization scheme, distributed implementations of zeroth-order schemes so as to exploit data parallelizability are getting significant attention recently. This article presents an overview of recent work in the area of distributed zeroth-order optimization, focusing on constrained optimization settings and algorithms built around the Frank-Wolfe framework. In particular, we review different types of architectures, from master-worker-based decentralized to fully distributed, and describe appropriate zeroth-order projection-free schemes for solving constrained stochastic optimization problems catered to these architectures. We discuss performance issues including convergence rates and dimension dependence. In addition, we also focus on more refined extensions such as by employing variance reduction and describe and quantify convergence rates for a variance-reduced decentralized zeroth-order optimization method inspired by martingale difference sequences. We discuss limitations of zeroth-order optimization frameworks in terms of dimension dependence. Finally, we illustrate the use of distributed zeroth-order algorithms in the context of adversarial attacks on deep learning models.

This paper focuses on the problem of \emph{constrained} \emph{stochastic} optimization. A zeroth order Frank-Wolfe algorithm is proposed, which in addition to the projection-free nature of the vanilla Frank-Wolfe algorithm makes it gradient free. Under convexity and smoothness assumption, we show that the proposed algorithm converges to the optimal objective function at a rate $O\left(1/T^{1/3}\right)$, where $T$ denotes the iteration count. In particular, the primal sub-optimality gap is shown to have a dimension dependence of $O\left(d^{1/3}\right)$, which is the best known dimension dependence among all zeroth order optimization algorithms with one directional derivative per iteration. For non-convex functions, we obtain the \emph{Frank-Wolfe} gap to be $O\left(d^{1/3}T^{-1/4}\right)$. Experiments on black-box optimization setups demonstrate the efficacy of the proposed algorithm.

Internet of Things (IoT) applications for Smart Cities, such as systems for traffic control and pollution monitoring, increasingly rely on trustworthy and secure data analytics. Proper countermeasures are needed to ensure that IoT applications function reliably under security threats. This paper studies secure analytics and resilient inference for IoT in the context of recursive parameter estimation. A team of devices makes noisy measurements of an unknown parameter, and an attacker manipulates the measurement data of a subset of the devices. We present a resilient recursive estimation algorithm that processes the measurement streams to recover the value of the parameter, even when a subset of the devices fall under attack. The estimator is guaranteed to be strongly consistent - that is, the estimate converges almost surely to the value of the parameter - as long as less than half of the devices fall under attack. We illustrate the performance of the estimator through numerical examples.

Cloud providers have recently introduced new offerings whereby spare computing resources are accessible at discounts compared to on-demand computing. Exploiting such opportunity is challenging inasmuch as such resources are accessed with low-priority and therefore can elastically leave (through preemption) and join the computation at any time. In this paper, we design a new technique called coded elastic computing enabling distributed computations over elastic resources. The proposed technique allows machines to leave the computation without sacrificing the algorithm-level performance, and, at the same time, flexibly reduce the workload at existing machines when new ones join the computation. Leveraging coded redundancy, our approach is able to achieve similar computational cost as the original (uncoded) method when all machines are present; the cost gracefully increases when machines are preempted and reduces when machines join. The performance of the proposed technique is evaluated on matrix-vector multiplication and linear regression tasks, and shows improvements over existing techniques.

This paper presents an improved secondary voltage control (SVC) methodology incorporating compressive sensing (CS) for a multiarea power system. SVC minimizes the voltage deviation of the load buses while CS deals with the problem of the limited bandwidth capacity of the communication channel by reducing the size of massive data output from the phasor measurement unit (PMU) based monitoring system. The proposed strategy further incorporates the application of a morphological median filter (MMF) to reduce noise from the output of the PMUs. To keep the control area secure and protected locally, mathematical singular entropy (MSE) based fault identification approach is utilized for fast discovery of faults in the control area. Simulation results with 27-bus and 486-bus power systems show that CS can reduce the data size up to 1/10th while the MSE-based fault identification technique can accurately distinguish between fault and steady-state conditions.

We derive the large deviation rate for convergence in probability of products of independent but not identically distributed stochastic matrices arising in time-varying distributed consensus-type networks. More precisely, we consider the model in which there exists a baseline topology that describes all possible communications and nodes are activated sparsely. At any given time, a node is active with a certain time-dependent probability, and any two nodes communicate if they are both active at that time. Under this model, we compute the exact rate for exponential decay of probabilities that the matrix products stay bounded away from their limiting matrix. We show that the rate is given by the minimal vertex cut of the baseline topology, where the node costs are defined by their limiting activation probabilities. The computed rate has many potential applications in distributed inference with intermittent communications. We provide an application in the context of consensus+innovations distributed detection. Therein, we show that optimal error exponent is achievable under a very general model of sparsified activations, thus effectively constructing asymptotically optimal detectors with significant communications savings.

This paper presents Communication efficient REcursive Distributed estimatiOn algorithm, CREDO for networked multi-agent systems. CREDO caters to situations in which the agents collaboratively estimate a vector parameter by assimilating their latest sensed information and estimates from their time-varying neighborhood worker nodes over a (possibly sparse) communication graph, while adhering to a frugal communication scheme. The underlying inter-agent communication protocol is randomized and adaptively, making communications increasingly (probabilistically) sparse as time progresses. CREDO may be designed to achieve at each agent a Θ(Ct-2+ζ) decay of the mean square error ( , arbitrarily small) with respect to per-node communication cost Ct, which significantly improves over the existing Θ(Ct-1) rates. Simulations demonstrate CREDO 's communication efficiency.

We propose a coded computing technique for making the power-iteration method of solving a single sparse linear inverse problem robust to erasure-type noise. We observe that for sparse inverse problems, codes with dense generator matrices can significantly increase storage costs. Thus, we propose coding the power-iteration computation using sparse generator matrices. Surprisingly, despite the poor error-correction ability of codes with sparse generator matrices, we show through both theoretical analysis and simulations that these codes are sufficient to achieve almost the same convergence rate as noiseless power iterations, provided that a new decoding algorithm that we call “substitute decoding” is used.

We propose a distributed Bayesian quickest detection algorithm for sensor networks, based on a random gossip inter-sensor communication structure. Without a control or fusion center, each sensor executes its local change detection procedure in a parallel and distributed fashion, interacting with its neighboring sensors via random inter-sensor communications to propagate information. By modeling the information propagation dynamics in the network as a Markov process, a two-layer large deviation analysis is presented to analyze the performance of the proposed algorithm. The first-layer analysis shows that the relation between the probability of false alarm and the conditional averaged detection delay satisfies the large deviation principle, where the distributed Kullback-Leibler information number is established as a crucial factor. The second-layer analysis studies the probability that not all observations are available at one sensor. It shows that this probability decays exponentially fast to zero as the averaged rounds of communication increases. The large deviation upper and lower bounds for the converge rate are then derived. Finally, we show that the performance of the distributed algorithm converges exponentially fast to that of the centralized optimal one.one.

Fifth-generation (5G) networks providing much higher bandwidth and faster data rates will allow connecting vast number of stationary and mobile devices, sensors, agents, users, machines, and vehicles, supporting Internet-of-Things (IoT), real-time dynamic networks of mobile things. Positioning and location awareness will become increasingly important, enabling deployment of new services and contributing to significantly improving the overall performance of the 5G system. Many of the currently talked about solutions to positioning in 5G are centralized, mostly requiring direct communication to the access nodes (or anchors, i.e., nodes with known locations), which in turn requires a high density of anchors. But such centralized positioning solutions may become unwieldy as the number of users and devices continues to grow without limit in sight. As an alternative to the centralized solutions, this paper discusses distributed localization in a 5G-enabled IoT environment where many low power devices, users, or agents are to locate themselves without a direct access to anchors. Even though positioning is essentially a nonlinear problem (solving circle equations by trilateration or triangulation), we discuss a cooperative linear distributed iterative solution with only local measurements, local communication, and local computation needed at each agent. Linearity is obtained by reparametrization of the agent location through barycentric coordinate representations based on local neighborhood geometry that may be computed in terms of certain Cayley-Menger determinants involving relative local inter-agent distance measurements. After a brief introduction to the localization problem, and other available distributed solutions primarily based on directly addressing the nonlinear formulation, we present the distributed linear solution for stationary agent networks and study its convergence, its robustness to noise, and extensions to mobile scenarios, in which agents, users, and (possibly) anchors are dynamic.

Gaussian belief propagation (BP) has been widely used for distributed estimation in large-scale networks such as the smart grid, communication networks, and social networks, where local meansurements/observations are scattered over a wide geographical area. However, the convergence of Gaussian BP is still an open issue. In this paper, we consider the convergence of Gaussian BP, focusing in particular on the convergence of the information matrix. We show analytically that the exchanged message information matrix converges for arbitrary positive semidefinite initial value, and its distance to the unique positive definite limit matrix decreases exponentially fast.

We consider a problem of localizing the destination of an activated path signal supported on a graph. An “activated path signal” is a graph signal that evolves over time that can be viewed as the trajectory of a moving agent. We show that by combining dynamic programming and graph partitioning, the computational complexity of destination localization can be significantly reduced. Then, we show that the destination localization error can be upper-bounded using methods based on large-deviation. Using simulation results, we show a tradeoff between the destination localization error and the computation time. We compare the dynamic programming algorithm with and without graph partitioning and show that the computation time can be significantly reduced by using graph partitioning. The proposed technique can scale to the problem of destination localization on a large graph with one million nodes and one thousand time slots.

We study bribery resistance properties in two classes of reputation-based ranking systems, where the rankings are computed by weighting the rates given by users with their reputations. In the first class, the rankings are the result of the aggregation of all the ratings, and all users are provided with the same ranking for each item. In the second class, there is a first step that clusters users by their rating pattern similarities, and then the rankings are computed cluster-wise. Hence, for each item, there is a different ranking for distinct clusters. We study the setting where the seller of each item can bribe users to rate the item, if they did not rate it before, or to increase their previous rating on the item. We model bribing strategies under these ranking scenarios and explore under which conditions it is profitable to bribe a user, presenting, in several cases, the optimal bribing strategies. By computing dedicated rankings to each cluster, we show that bribing, in general, is not as profitable as in the simpler without clustering. Finally, we illustrate our results with experiments using real data.

Computationally intensive distributed and parallel computing is often bottlenecked by a small set of slow workers known as stragglers. In this paper, we utilize the emerging idea of ``coded computation'' to design a novel error-correcting-code inspired technique for solving linear inverse problems under specific iterative methods in a parallelized implementation affected by stragglers. Example machine-learning applications include inverse problems such as personalized PageRank and sampling on graphs. We provably show that our coded-computation technique can reduce the mean-squared error under a computational deadline constraint. In fact, the ratio of mean-squared error of replication-based and coded techniques diverges to infinity as the deadline increases. Our experiments for personalized PageRank performed on real systems and real social networks show that this ratio can be as large as $10^4$. Further, unlike coded-computation techniques proposed thus far, our strategy combines outputs of all workers, including the stragglers, to produce more accurate estimates at the computational deadline. This also ensures that the accuracy degrades ``gracefully'' in the event that the number of stragglers is large.

This paper studies recursive composite hypothesis testing in a network of sparsely connected agents. The network objective is to test a simple null hypothesis against a composite alternative concerning the state of the field, modeled as a vector of (continuous) unknown parameters determining the parametric family of probability measures induced on the agents' observation spaces under the hypotheses. Specifically, under the alternative hypothesis, each agent sequentially observes an independent and identically distributed time-series consisting of a (nonlinear) function of the true but unknown parameter corrupted by Gaussian noise, whereas, under the null, they obtain noise only. Two distributed recursive generalized likelihood ratio test type algorithms of the consensus+innovations form are proposed, namely, CIGLRT - L and CIGLRT - NL, in which the agents estimate the underlying parameter and in parallel also update their test decision statistics by simultaneously processing the latest local sensed information and information obtained from neighboring agents. For CIGLRT - NL, for a broad class of nonlinear observation models and under a global observability condition, algorithm parameters which ensure asymptotically decaying probabilities of errors (probability of miss and probability of false detection) are characterized. For CIGLRT - L, a linear observation model is considered and upper bounds on large deviations decay exponent for the error probabilities are obtained.

We consider the problem of computing a binary linear transformation when all circuit components are unreliable. Two models of unreliable components are considered: probabilistic errors and permanent errors. We introduce the “ENCODED” technique that ensures that the error probability of the computation of the linear transformation is kept bounded below a small constant independent of the size of the linear transformation even when all logic gates in the computation are noisy. By deriving a lower bound, we show that in some cases, the computational complexity of the ENCODED technique achieves the optimal scaling in error probability. Further, we examine the gain in energy-efficiency from the use of a “voltage-scaling” scheme, where gate-energy is reduced by lowering the supply voltage. We use a gate energy-reliability model to show that tuning gate-energy appropriately at different stages of the computation (“dynamic” voltage scaling), in conjunction with ENCODED, can lead to orders of magnitude energy-savings over the classical “uncoded” approach. Finally, we also examine the problem of computing a linear transformation when noiseless decoders can be used, providing upper and lower bounds to the problem.

We consider the problem of distributed lossy linear function computation in a tree network. We examine two cases: 1) data aggregation (only one sink node computes) and 2) consensus (all nodes compute the same function). By quantifying the accumulation of information loss in distributed computing, we obtain fundamental limits on network computation rate as a function of incremental distortions (and hence incremental loss of information) along the edges of the network. The above characterization, based on quantifying distortion accumulation, offers an improvement over classical cut-set type techniques, which are based on overall distortions instead of incremental distortions. This quantification of information loss qualitatively resembles information dissipation in cascaded channels [2]. Surprisingly, this accumulation effect of distortion happens even at infinite blocklength. Combining this observation with an inequality on the dominance of mean-square quantities over relative-entropy quantities, we obtain outer bounds on the rate distortion function that are tighter than classical cut-set bounds by a difference, which can be arbitrarily large in both data aggregation and consensus. We also obtain inner bounds on the optimal rate using random Gaussian coding, which differ from the outer bounds by O(√D), where D is the overall distortion. The obtained inner and outer bounds can provide insights on rate (bit) allocations for both the data aggregation problem and the consensus problem. We show that for tree networks, the rate allocation results have a mathematical structure similar to classical reverse waterfilling for parallel Gaussian sources. Apart from data aggregation and distributed consensus, the distortion accumulation analysis framework is also applicable in large-scale data summarization through histograms and linear sketching, e.g., word counting tasks for document summarization.

We consider the problem of minimizing the number of broadcasts for collecting all sensor measurements at a sink node in a noisy broadcast sensor network. Focusing first on arbitrary network topologies, we provide: 1) fundamental limits on the required number of broadcasts of data gathering and 2) a general in-network computing strategy to achieve an upper bound within factor log N of the fundamental limits, where N is the number of agents in the network. Next, focusing on two example networks, namely, arbitrary geometric networks and random Erdös-Rényi networks, we provide improved in-network computing schemes that are optimal in that they attain the fundamental limits, i.e., the lower and upper bounds are tight in scaling sense. Our main techniques are three distributed encoding techniques, called graph codes, which are designed, respectively, for the above-mentioned three scenarios. Our work, thus, extends and unifies previous works such as those of Gallager and Karamchandani on the number of broadcasts for distributed function computation in special network topologies, while bringing in novel techniques, e.g., from error-control coding and noisy circuits, for both upper and lower bounds.

This paper focuses on the problem of distributed composite hypothesis testing in a network of sparsely interconnected agents, in which only a small section of the field modeling parametric alternatives is observable at each agent. A recursive generalized likelihood ratio test (GLRT) type algorithm in a distributed setup of the consensus-plus-innovations form is proposed, in which the agents update their parameter estimates and decision statistics by simultaneously processing the latest sensed information (innovations) and information obtained from neighboring agents (consensus). This paper characterizes the conditions and the testing algorithm design parameters which ensure that the probabilities of decision errors decay to zero asymptotically in the large sample limit. Finally, simulation studies are presented which illustrate the findings.

This paper introduces a novel design of phase locked loop (PLL) based oscillatory neural networks (ONNs) to mitigate the frequency clustering phenomenon caused by transmission delays in real systems. Theoretical analysis of the ONN reveals that transmission delays can produce frequency clustering that leads to synchronization and convergence failure. This paper describes the redesign of ONN dynamics and associated system-level architecture to achieve robustness. Specifically, we first demonstrate that using the phase information of zero-crossing points of inputs as the PLL error signal enables the ONN dynamical model to correctly synchronize under uniform transmission delays. A Type-II PLL based ONN architecture is shown via simulation to provide this property in hardware. Furthermore, to accommodate non-uniform transmission delays in hardware, a phase synchronization technique is proposed that is shown to provide the correct synchronization behavior.

This paper focuses on the problem of distributed composite hypothesis testing in a noisy network of sparsely interconnected agents in which a pair of agents exchange information over an additive noise channel. The network objective is to test a simple null hypothesis against a composite alternative concerning the state of the field, modeled as a vector of (continuous) unknown parameters determining the parametric family of probability measures induced on the agents' observation spaces under the hypotheses. A recursive generalized likelihood ratio test (GLRT) type algorithm in a distributed setup of the consensus+innovations form is proposed, in which the agents update their parameter estimates and decision statistics by simultaneously processing the latest sensed information (innovations) and information obtained from neighboring agents (consensus). This paper characterizes the conditions and the testing algorithm design parameters which ensure that the probabilities of decision errors decay to zero asymptotically in the large sample limit.

We consider the problem of lossy linear function computation for Gaussian sources in a tree network. The goal is to find the optimal tradeoff between the sum rate (the overall number of bits communicated in the network) and the achieved distortion (the overall mean-square error of estimating the function result) at a specified sink node. Using random Gaussian codebooks, an inner bound is obtained that is shown to match the information-theoretic outer bound (obtained in our earlier work [1]) in the limit of zero distortion. To compute the overall distortion for the random coding scheme, we applied the analysis of Distortion Accumulation which was quantified in [1] for MMSE estimates of intermediate computation variables instead of for the codewords of random Gaussian codebooks. The key in applying the analysis of Distortion Accumulation is showing that the random-coding based codeword on the receiver side is close in mean-square sense to the MMSE estimate of the source, even if the knowledge of the source distribution is not fully accurate.

We consider the problem of computing a binary linear transform when all circuit components are unreliable. We propose a novel “ENCODED” technique that uses LDPC (low-density parity-check) codes and embedded noisy decoders to keep the error probability of the computation below a small constant independent of the size of the linear transform, even when all logic gates in the computation are prone to probabilistic errors. Unlike existing works on applying coding to computing with unreliable components, the “ENCODED” technique explicitly considers the errors that happen during both the encoding and the decoding phases. Further, we show that ENCODED requires fewer operations (in order sense) than repetition techniques.

We consider the problem of data collection in a two-layer network consisting of (1) noisy links between N distributed agents and a remote sink node; (2) a noisy sparse network formed by these distributed agents. We jointly consider the design of the optimal graph topology for the inter-agent network and the in-network computing scheme under the sparsity constraint and the energy constraint, and study the effect of inter-agent communications on the overall energy consumption. Despite the sparse connections between agents, we provide an in-network coding scheme that reduces the overall energy consumption by a factor of Θ(logN) compared to a naive scheme based on direct agent-to-sink communications only. By providing lower bounds on both the energy consumption and the sparseness (number of links) of the network, we show that the proposed scheme is energy-optimal except for a factor of Θ(log logN). The proposed scheme extends a previous work of Gallager [2] on noisy broadcasting from a complete graph to a sparse graph, while bringing in new techniques from error control coding and noisy circuits.

We study cyber-physical systems subject to dynamic sensor attacks, relating them to the system's strong observability. First, we find necessary and sufficient conditions for an attacker to create a dynamically undetectable sensor attack and relate these conditions to properties of the system dynamics eigenvectors. Next, we provide an index that gives the minimum number of sensors that must be attacked in order for an attack to be undetectable. Finally, we illustrate our results with a numerical example on the Quadruple Tank Process.

This paper studies a Quantized Gossip-based Interactive Kalman Filtering (QGIKF) algorithm implemented in a wireless sensor network, where the sensors exchange their quantized states with neighbors via inter-sensor communications. We show that with the information loss due to quantization, the network can still achieve weak consensus, i.e., the estimation error variance sequence at a randomly selected sensor can converge weakly (in distribution) to a unique invariant measure. To prove the weak convergence, we first interpret the error variance sequence evolution as the interacting particle, then formulate the sequence as a Random Dynamical System (RDS), and finally prove that it is stochastically bounded.

This paper studies the convergence of the estimation error process and the characterization of the corresponding invariant measure in distributed Kalman filtering for potentially unstable and large linear dynamic systems. A gossip network protocol termed modified gossip interactive Kalman filtering (M-GIKF) is proposed, where sensors exchange their filtered states (estimates and error covariances) and propagate their observations via intersensor communications of rate$\bar {\gamma }$;$\bar {\gamma }$is defined as the averaged number of intersensor message passages per signal evolution epoch. The filtered states are interpreted as stochastic particles swapped through local interaction. This paper shows that the conditional estimation error covariance sequence at each sensor under M-GIKF evolves as a random Riccati equation (RRE) with Markov modulated switching. By formulating the RRE as a random dynamical system, it is shown that the network achieves weak consensus, i.e., the conditional estimation error covariance at a randomly selected sensor converges weakly (in distribution) to a unique invariant measure. Further, it is proved that as$\bar {\gamma } \rightarrow \infty $this invariant measure satisfies the large deviation (LD) upper and lower bounds, implying that this measure converges exponentially fast (in probability) to the Dirac measure$\delta _{P^{*}}$, where$P^{*}$is the stable error covariance of the centralized (Kalman) filtering setup. The LD results answer a fundamental question on how to quantify the rate at which the distributed scheme approaches the centralized performance as the intersensor communication rate increases.

We propose a new framework for distributed computation of average consensus. The presented framework leads to a systematic design of iterative algorithms that compute the consensus exactly, are guaranteed to converge in finite time, are computationally efficient, and require no online memory. We demonstrate that our approach is applicable to a broad class of networks. For remaining networks, our framework leads to the construction of approximating algorithms for consensus that are also guaranteed to compute in finite time. Our approach is inspired by graph filters introduced by the theoretical framework of signal processing on graphs.

With the proposed penetration of electric vehicles and advanced metering technology, the demand side is foreseen to play a major role in flexible energy consumption scheduling. On the other hand, the past several years have witnessed utility companies' growing interests to integrate more renewable energy resources. These renewable resources, for example, wind or solar, due to their intermittent nature, brought great uncertainty to the power grid system. In this article, we propose a mechanism that attempts to mitigate the grid operational uncertainty induced by renewable energies by properly exploiting demand flexibility with the help of advanced smart-metering technology. To address the challenge, we develop a novel locational marginal price (LMP)-based pricing scheme that involves active demand-side participation by casting the network objective as a two-stage Stackelberg game between the local grid operator and several aggregators. In contrast to the conventional notion that generation follows load, our game formulation provides more flexibility for the operators and tries to provide adequate incentives for the loads to follow the (stochastic renewable) generation. We use the solution concept of subgame perfect equilibrium to analyze the resulting game. Subsequently, we discuss the optimal real-time conventional capacity planning for the local grid operator to achieve the minimal mismatch between supply and demand with the wind power integration. Finally, we assess our proposed scheme with field data. The simulation results show that our proposed scheme works reasonably well in the long term, even with simple heuristics.

This paper studies the problem of distributed parameter estimation in multiagent networks with exponential family observation statistics. A certainty-equivalence type distributed estimator of the consensus-plus-innovations form is proposed in which, at each observation sampling epoch, agents update their local parameter estimates by appropriately combining the data received from their neighbors and the locally sensed new information (innovation). Under global observability of the networked sensing model, i.e., the ability to distinguish between different instances of the parameter value based on the joint observation statistics, and mean connectivity of the inter-agent communication network, the proposed estimator is shown to yield consistent parameter estimates at each network agent. Further, it is shown that the distributed estimator is asymptotically efficient, in that, the asymptotic covariances of the agent estimates coincide with that of the optimal centralized estimator, i.e., the inverse of the centralized Fisher information rate. From a technical viewpoint, the proposed distributed estimator leads to non-Markovian mixed time-scale stochastic recursions and the analytical methods developed in this paper contribute to the general theory of distributed stochastic approximation.

The paper considers the problem of distributed estimation of an unknown deterministic scalar parameter (the target signal) in wireless sensor networks (WSNs), in which each sensor receives a single snapshot of the field. The observation or sensing mode is only partially known at the corresponding nodes, perhaps, due to their limited sensing capabilities or other unpredictable physical factors. Specifically, it is assumed that the observation process at a node switches stochastically between two modes, with mode one corresponding to the desired signal plus noise observation mode (a valid observation), and mode two corresponding to pure noise with no signal information (an invalid observation). With no prior information on the local sensing modes (valid or invalid), the paper introduces a learning-based distributed estimation procedure, the mixed detection-estimation (MDE) algorithm, based on closed-loop interactions between the iterative distributed mode learning and estimation. The online learning (or sensing mode detection) step re-assesses the validity of the local observations at each iteration, thus refining the ongoing estimation update process. The convergence of the MDE algorithm is established analytically. Simulation studies show that, in the high signal-to-noise ratio (SNR) regime, the MDE estimation error converges to that of an ideal (centralized) estimator with perfect information about the node sensing modes. This is in contrast with the estimation performance of a naive average consensus based distributed estimator (with no mode learning), whose estimation error blows up with an increasing SNR.

The paper studies distributed static parameter (vector) estimation in sensor networks with nonlinear observation models and noisy intersensor communication. It introduces separably estimable observation models that generalize the observability condition in linear centralized estimation to nonlinear distributed estimation. It studies two distributed estimation algorithms in separably estimable models, theNU(with its linear counterpartLU) and theNLU. Their update rule combines a consensus step (where each sensor updates the state by weight averaging it with its neighbors' states) and an innovation step (where each sensor processes its local current observation). This makes the three algorithms of the consensus + innovations type, very different from traditional consensus. This paper proves consistency (all sensors reach consensus almost surely and converge to the true parameter value), efficiency, and asymptotic unbiasedness. ForLUandNU, it proves asymptotic normality and provides convergence rate guarantees. The three algorithms are characterized by appropriately chosen decaying weight sequences. AlgorithmsLUandNUare analyzed in the framework of stochastic approximation theory; algorithmNLUexhibits mixed time-scale behavior and biased perturbations, and its analysis requires a different approach that is developed in this paper.

Algorithms are studied for distributed least-squares (DLS) estimation of a scalar target signal in sensor networks. Due to the observation locality and the limited sensing ability, the individual sensor estimates are far from being reliable. To obtain a more reliable estimate of the target signal, the sensors could collaborate by iteratively exchanging messages with their neighbors, to refine their local estimates over time. Such an iterative DLS algorithm is investigated in this paper with and without the consideration of node failures. In particular, without sensor node failures it is shown that every instantiation of the DLS algorithm converges, i.e., consensus is reached among the sensors, with the limiting agreement value being the centralized least-squares estimate. With node failures during the iterative exchange process, the convergence of the DLS algorithm is still guaranteed; however, an error exists between the limiting agreement value and the centralized least-squares estimate. In order to reduce this error, a modified DLS scheme, the M-DLS, is provided. The M-DLS algorithm involves an additional weight compensation step, in which a sensor performs a one-time weight compensation procedure whenever it detects the failure of a neighbor. Through analytical arguments and simulations, it is shown that the M-DLS algorithm leads to a smaller error than the DLS algorithm, where the magnitude of the improvement dependents on the network topology.

The paper studies the convergence properties of the estimation error processes in distributed Kalman filtering for potentially unstable linear dynamical systems. In particular, it is shown that, in a weakly connected communication network, there exist (randomized) gossip based information dissemination schemes leading to a stochastically bounded estimation error at each sensor for any non-zero rate γ̄ of inter-sensor communication (the rate γ̄ is defined to be the average number of inter-sensor communications per signal evolution epoch). A gossip-based information exchange protocol, the M-GIKF, is presented, in which sensors exchange estimates and aggregate observations at a rate γ̄ > 0, leading to desired convergence properties. Under the assumption of global (centralized) detectability of the signal/observation model (necessary for a centralized estimator having access to all sensor observations at all times to yield bounded estimation error), it is shown that the distributed M-GIKF leads to a stochastically bounded estimation error at each sensor. The conditional estimation error covariance sequence at each sensor is shown to evolve as a random Riccati equation (RRE) with Markov modulated switching. The RRE is analyzed through a random dynamical system (RDS) formulation, and the asymptotic estimation error at each sensor is characterized in terms of an associated invariant measure µγ̄ of the RDS.

Networks of biological agents (for example, ants, bees, fish, birds) and complex man-made cyberphysical infrastructures (for example, the power grid, transportation networks) exhibit one thing in common - the emergence of collective global phenomena from apparently random local interactions. This paper proposes a distributed graphical model of interacting agents (a stochastic network type model) and studies its appropriate asymptotics. We show that metastability may occur - i.e., under certain conditions, the agents act in synchrony and may exhibit collectively possibly different stable equilibria - these are the global emergent behaviors of the cloud of interacting agents. We characterize these global behaviors as synchronous fixed points determined from ordinary differential equations that arise as mean field limits of the adopted stochastic model.

This paper considers distributed detection over a noisy network, in which each connected sensor pair can communicate over an additive noise channel. With non-identically distributed generic sensor observations, a mixed time scale recursive algorithm for binary hypothesis testing over such networks is proposed. Under some mild assumptions on network connectivity and global detectability (the positivity of the global or centralized Kullback-Liebler divergence), this algorithm yields asymptotically zero probabilities of Type-I and Type-II errors (henceforth referred to as probabilities of error). When sensor observations are identically distributed, a simplified single time scale version of the proposed algorithm is shown to achieve asymptotically zero probabilities of error. Convergence rate guarantees in terms of asymptotic normality of certain scaled decision variables are provided for this simplified procedure. As an example, a practical Gaussian sensor network is considered, for which the error decay exponents are explicitly characterized in terms of the network and noise parameters.

In this paper, we study the synthesis problem in linear high dimensional consensus (HDC) algorithms for large-scale networks. In HDC, we partition the network nodes into leaders and followers. Each follower updates its state as a linear combination of its neighboring states, whereas, the state of the leaders remains fixed. Hence, linear HDC can be thought of as a linear time-invariant (LTI) system. The synthesis problem for this LTI system is to design its parameters such that the system converges to a desired pre-specified state. We cast this synthesis problem as a multi-objective optimization problem (MOP) to which we apply Pareto-optimality. We show that the optimal solution of the synthesis problem is a Pareto-optimal (P.O.) solution of the MOP. We then provide a graphical method to extract the optimal MOP solution from the set of all P.O. solutions. Casting the synthesis problem as an MOP naturally lends itself to interesting performance vs speed trade-offs in HDC.

Gossip algorithms are attractive for in-network processing in sensor networks because they do not require any specialized routing, there is no bottleneck or single point of failure, and they are robust to unreliable wireless network conditions. Recently, there has been a surge of activity in the computer science, control, signal processing, and information theory communities, developing faster and more robust gossip algorithms and deriving theoretical performance guarantees. This paper presents an overview of recent work in the area. We describe convergence rate results, which are related to the number of transmitted messages and thus the amount of energy consumed in the network for gossiping. We discuss issues related to gossiping over wireless links, including the effects of quantization and noise, and we illustrate the use of gossip algorithms for canonical signal processing tasks including distributed estimation, source localization, and compression.

The paper considers the algorithm NLU for distributed (vector) parameter estimation in sensor networks, where, the local observation models are nonlinear, and inter-sensor communication is imperfect, in the sense, that the network links fail randomly and inter-sensor transmission is quantized. The paper introduces the class of separably estimable observation models, which generalizes the notion of observability in centralized linear estimation to distributed nonlinear estimation. We show that the NLU algorithm leads to consistent and asymptotically unbiased estimates of the parameter at each sensor for separably estimable observation models. In other words, the sensors reach consensus almost sure (a.s.) to the true parameter value. The algorithm NLU is a mixed time scale stochastic algorithm, characterized by two different decreasing weight sequences associated with the consensus and innovation updates. The analysis of the NLU algorithm, thus, does not follow under the purview of standard stochastic approximation, making the analysis developed in the paper of independent theoretical interest.

This paper introduces higher dimensional consensus, a framework to capture a number of different, but, related distributed, iterative, linear algorithms of interest in sensor networks. We show that, by suitably choosing the iteration matrix of the higher dimensional consensus, we can capture, besides the standard average-consensus, a broad range of applications, including sensor localization, leader-follower, and distributed Jacobi algorithm. We work with the concept of anchors and explicitly derive the consensus subspace and provide the dimension of the limiting state of the sensors.

The paper studies distributed average consensus in sensor networks, when the sensors exchange quantized data at each time step. We show that randomizing the exchanged sensor data by adding a controlled amount of dither results in almost sure (a.s.) convergence of the protocol, if the network is connected. We explicitly characterize the mean-squared error (with respect to the desired consensus average) and show that, by tuning certain parameters associated with the protocol, the mean-squared error can be made arbitrarily small. We study the trade-offs between the rate of convergence and the resulting mean-squared error. The sensor network topology plays an important role in determining the convergence rate of the algorithm. Our approach, based on the convergence of controlled Markov processes, is very generic and can be applied to many other situations of imperfect communication. Finally, we present numerical studies, which verify our theoretical results.

We study the impact of the topology of a sensor network on distributed average consensus algorithms when the network links fail at random. We derive convergence results. In particular, we determine a sufficient condition for mean-square convergence of the distributed average consensus algorithm in terms of a moment of the distribution of the norm of a function of the network graph Laplacian matrix L (which is a random matrix, because the network links are random.) Further, because the computation of this moment involves costly simulations, we relate the mean-square convergence to the second eigenvalue of the mean Laplacian matrix, λ2(L̅), which is much easier to compute. We derive bounds on the convergence rate of the algorithm, which show that both the expected algebraic connectivity of the network, E[λ2(L)], and λ2(L̅) play an important role in determining the actual convergence rate. Specifically, larger values of E[λ2(L)] or λ2(L̅) lead to better convergence rates. Finally, we provide numerical studies that verify the analytical results.