Decentralized strategies are of interest for learning from large-scale data over networks. This paper studies learning over a network of geographically distributed nodes/agents subject to quantization. Each node possesses a private local cost function, collectively contributing to a global cost function, which the considered methodology aims to minimize. In contrast to many existing papers, the information exchange among nodes is log-quantized to address limited network-bandwidth in practical situations. We consider a first-order computationally efficient distributed optimization algorithm (with no extra inner consensus loop) that leverages node-level gradient correction based on local data and network-level gradient aggregation only over nearby nodes. This method only requires balanced networks with no need for stochastic weight design. It can handle log-scale quantized data exchange over possibly time-varying and switching network setups. We study convergence over both structured networks (for example, training over data-centers) and ad-hoc multi-agent networks (for example, training over dynamic robotic networks). Through experimental validation, we show that (i) structured networks generally result in a smaller optimality gap, and (ii) log-scale quantization leads to a smaller optimality gap compared to uniform quantization.

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 special issue provides a comprehensive overview of modern optimization tools and methods for the purposes of data-driven learning and control.

Decentralized optimization to minimize a finite sum of functions, distributed over a network of nodes, has been a significant area within control and signal-processing research due to its natural relevance to optimal control and signal estimation problems. More recently, the emergence of sophisticated computing and large-scale data science needs have led to a resurgence of activity in this area. In this article, we discuss decentralized first-order gradient methods, which have found tremendous success in control, signal processing, and machine learning problems, where such methods, due to their simplicity, serve as the first method of choice for many complex inference and training tasks. In particular, we provide a general framework of decentralized first-order methods that is applicable to directed and undirected communication networks alike and show that much of the existing work on optimization and consensus can be related explicitly to this framework. We further extend the discussion to decentralized stochastic first-order methods that rely on stochastic gradients at each node and describe how local variance reduction schemes, previously shown to have promise in the centralized settings, are able to improve the performance of decentralized methods when combined with what is known as gradient tracking. We motivate and demonstrate the effectiveness of the corresponding methods in the context of machine learning and signal-processing problems that arise in decentralized environments.

In this letter, we introduce a distributed Nesterov gradient method, ABN, that does not require doubly stochastic weights. Instead, the implementation is based on a simultaneous application of both row- and column-stochastic weights that makes ABN applicable to arbitrary (strongly-connected) graphs. Since constructing column-stochastic weights needs additional information (the number of outgoing neighbors), not available in certain communication protocols, we derive a variation, FROZEN, that only requires row-stochastic weights, but at the expense of additional iterations for eigenvector estimation. We numerically study these algorithms for various objective functions and network parameters and show that the proposed distributed Nesterov gradient methods achieve acceleration compared to the current state-of-the-art methods for distributed optimization.

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.

In this letter, we discuss cost optimization of sensor networks monitoring structurally full-rank systems under distributed observability constraint. Using structured systems theory, the problem is relaxed into two subproblems: first, sensing cost optimization; and second, networking cost optimization. Both problems are reformulated as combinatorial optimization problems. The sensing cost optimization is shown to have a polynomial-order solution. The networking cost optimization is shown to be NP-hard in general, but has a polynomial-order solution under specific conditions. A 2-approximation polynomial-order relaxation is provided for general networking cost optimization, which is applicable in large-scale system monitoring.

This paper considers distributed multi-agents optimization problems where agents collaborate to minimize the sum of locally known convex functions. We focus on the case when the communication between agents is described by a directed graph. The proposed algorithm achieves the best known rate of convergence for this class of problems, O(μk) for 0 <; μ <; 1, given that the objective functions are strongly-convex, where k is the number of iterations. Moreover, it provides a wider and more realistic range of step-size compared with existing methods.

Single-time-scale distributed estimation of dynamic systems via a network of sensors/estimators is addressed in this letter. In single-time-scale distributed estimation, the two fusion steps, consensus and measurement exchange, are implemented only once, in contrast to, e.g., a large number of consensus iterations at every step of the system dynamics. We particularly discuss the problem of failure in the sensor/estimator network and how to recover for distributed estimation by adding new sensor measurements from equivalent states. We separately discuss the recovery for two types of sensors, namely α and β sensors. We propose polynomial-order algorithms to find equivalent state nodes in graph representation of the system to recover for distributed observability. The polynomial-order solution is particularly significant for large-scale systems.

In this paper, we develop a distributed algorithm to localize a network of robots moving arbitrarily in a bounded region. In the case of such mobile networks, the main challenge is that the robots may not be able to find nearby robots to implement a distributed algorithm. We address this issue by providing an opportunistic algorithm that only implements a location update when there are nearby robots and does not update otherwise. We assume that each robot measures a noisy version of its motion and the distances to the nearby robots. To localize a network of mobile robots in ℝm, we provide a simple linear update, which is based on barycentric coordinates and is linear-convex. We abstract the corresponding localization algorithm as a linear time-varying system and show that it asymptotically converges to the true locations of the robots. We first focus on the noiseless case, in which the distance and motion vectors are known (measured) perfectly, and provide sufficient conditions on the convergence of the algorithm. We then evaluate the performance of the algorithm in the presence of noise and provide modifications to counter the undesirable effects of noise. We further show that our algorithm precisely tracks a mobile network as long as there is at least one known beacon (a node whose location is perfectly known).

This paper studies observability of linear systems from both algebraic and graph-theoretic arguments, and further draws a parallel between the two. We show that a set of critical measurements (for state-space observability) can be partitioned into two types: α and β. This partitioning is driven by different graphical (or algebraic) methods used to define the corresponding measurements. Subsequently, we describe observational equivalence, i.e., given an α (or β) measurement, say yi, what is the set of measurements equivalent to yi, such that only one measurement in this set is required? Since α and β measurements are cast using different algebraic and graphical characteristics, their equivalence sets are also derived using different algebraic and graph-theoretic principles. The need to make such equivalence arises in areas, e.g., meter placement for power systems, where relevant lines of study include: (a) to guarantee state-space observability with as few sensors as possible; and, (b) to find candidate replacement measurements when a sensor incurs a fault. We illustrate the related concepts on a simple, yet insightful, system digraph.

In this letter, we characterize the finite-time behavior on arbitrary undirected graphs. In particular, we derive distributed iterations that are a function of a linear operator on the underlying graph and show that any arbitrary initial condition can be forced to lie on a particular subspace in a finite time. This subspace can be chosen to have the same dimension as the algebraic multiplicity of any (arbitrarily chosen) eigenvalue of the underlying linear operator and is spanned by the eigenvectors corresponding to the chosen eigenvalue. In other words, finite-time behavior is completely characterized by the algebraic multiplicity of the eigenvalues and the corresponding eigenvectors of the underlying linear operator. We show that finite-time average-consensus can be cast naturally in this setup for which we further develop the necessary and sufficient conditions.

In this letter, we study the consensus-based leader-follower algorithm in mobile sensor networks, where the goal for the entire network is to converge to the state of a leader. We capture the mobility in the leader-follower algorithm by abstracting it as a Linear Time-Varying (LTV) system with random system matrices. In particular, a mobile node, moving randomly in a bounded region, updates its state when it finds neighbors; and does not update when it is not in the communication range of any other node. In this context, we develop certain regularity conditions on the system and input matrices such that each follower converges to the leader state. To analyze the corresponding LTV system, we partition the entire chain of system matrices into non-overlapping slices, and relate the convergence of the sensor network to the lengths of these slices. In contrast to the existing results, we show that a bounded length on the slices, capturing the dissemination of information from the leader to the followers, is not required; as long as the slice-lengths are finite and do not grow faster than a certain exponential rate.

This paper studies distributed averaging of arbitrary vectors in the presence of network interference by casting an algebraic structure over the interference. While communicating locally with its neighbors for consensus, each agent causes an additive interference, lying on a low-dimensional subspace, in other communication links. We consider a particular case when this interference subspace depends only on the inter-ferer, referred to as uniform outgoing interference. We show that consensus is possible in a low-dimensional subspace of the initial conditions whose dimension is complimentary to the largest interference subspace across all of the agents. In this context, we derive a global information alignment and a local pre-conditioning, followed by local consensus iterations to ensure subspace consensus. We further provide the conditions under which this subspace consensus recovers the exact average. The analytical results are illustrated graphically to describe the setup and the information alignment scheme.

In this paper, we consider distributed estimation when the communication time-scale is restricted to the time-scale of the dynamics. It can be shown that this restriction may not guarantee a stable estimation error when the data fusion is implemented only in the observation-space. To address this issue, one has to rely on fusion in the predictor-space, which alone may lead to a stable error only when the system matrix is full S-rank (maximal rank of the zero/non-zero structure). In this paper, we show that when the system matrix is S-rank deficient, predictor-space fusion is insufficient, i.e., the distributed estimator is not observable. In order to recover distributed observability, we provide a novel measurement-based agent classification, and subsequently, define inter-agent communication derived from this classification. The results are based on structured systems theory and the notion of generic observability. Finally, we provide an illustrative example to show the applicability of the proposed schemes using an iterative Linear Matrix Inequality (LMI) approach.

Distributed estimation is where the state of a dynamical system is to be estimated via a collection of geographically dispersed measurements over a sensor network. In order to implement the estimator, the sensors, in addition to sensing, implement a simple data fusion protocol that relies on inter-sensor communication. In this paper, we study distributed estimation of cyber-physical systems when there is an adversarial attack on the sensed and communicated information. We propose a novel methodology to address the detection of such attacks, and further incorporate appropriate remedial actions in the estimator. Our methodology is based on the notions of local consistency and nodal consistency and is further reinforced by the exploiting the underlying physical-layer in the cyber-physical description.

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.

This paper proposes modeling the rapidly evolving energy systems as cyber-based physical systems. It introduces a novel cyber-based dynamical model whose mathematical description depends on the cyber technologies supporting the physical system. This paper discusses how such a model can be used to ensure full observability through a cooperative information exchange among its components; this is achieved without requiring local observability of the system components. This paper also shows how this cyber-physical model is used to develop interactive protocols between the controllers embedded within the system layers and the network operator. Our approach leads to a synergistic framework for model-based sensing and control of future energy systems. The newly introduced cyber-physical model has network structure-preserving properties that are key to effective distributed decision making. The aggregate load modeling that we develop using data mining techniques and novel sensing technologies facilitates operations of complex electric power systems.

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.

In this paper, we present a distributed algorithm to invert L-banded matrices that are symmetric positive definite (SPD), when the sub-matrices in the band are distributed among several processing nodes. We provide a distributed iterate-collapse inversion (DICI) algorithm that converges, at each node, to the corresponding submatrices in the inverse of the L-banded matrix. The computational complexity of the DICI algorithm to invert an SPD L-banded n x n matrix can be shown at each node to be independent of the size, n, of the matrix. Local information exchange is carried out after each iteration to guarantee convergence. We apply this algorithm to invert the information matrices in a computationally efficient distributed implementation of the Kalman filter and show its application towards inverting arbitrary sparse SPD matrices.