1,721,021 research outputs found
Estimation and Detection Over Adaptive Networks
No full textIn this chapter, we review the foundations of statistical inference over adaptive networks by considering two canonical problems: distributed estimation and distributed detection. In the former setting, agents cooperate to estimate a model of interest while in the second setting, the agents cooperate to detect a state of nature. We focus on adaptive learning solutions where agents are able to track drifts in the underlying models, and examine performance limits under both estimation and detection formulations. Special attention is paid to the detailed characterization of the steady-state performance. Certain universal laws are highlighted and compared against known laws for estimation and detection in traditional (centralized or decentralized, nonadaptive) inferential systems
Consistent tomography under partial observations over adaptive networks
Full text linkThis paper studies the problem of inferring whether an agent is directly influenced by another agent over a network. Agent i influences agent j if they are connected (according to the network topology), and if agent j uses the data from agent i to update its online learning algorithm. The solution of this inference task is challenging for two main reasons. First, only the output of the learning algorithm is available to the external observer that must perform the inference based on these indirect measurements. Second, only output measurements from a fraction of the network agents is available, with the total number of agents itself being also unknown. The main focus of this paper is ascertaining under these demanding conditions whether consistent tomography is possible, namely, whether it is possible to reconstruct the interaction profile of the observable portion of the network, with negligible error as the network size increases. We establish a critical achievability result, namely, that for symmetric combination policies and for any given fraction of observable agents, the interacting and non-interacting agent pairs split into two separate clusters as the network size increases. This remarkable property then enables the application of clustering algorithms to identify the interacting agents influencing the observations. We provide a set of numerical experiments that verify the results for finite network sizes and time horizons. The numerical experiments show that the results hold for asymmetric combination policies as well, which is particularly relevant in the context of causation
Decision Learning and Adaptation over Multi-Task Networks
No full textThis paper studies the operation of multi-agent networks engaged in multi-task decision problems under the paradigm of simultaneous learning and adaptation. Two scenarios are considered:one in which a decision must be taken among multiple states of nature that are known but can vary over time and space, and another in which there exists a known 'normal' state of nature and the task is to detect unpredictable and unknown deviations from it. In both cases the network learns from the past and adapts to changes in real time in a multi-task scenario with different clusters of agents addressing different decision problems. The system design takes care of challenging situations with clusters of complicated structure, and the performance assessment is conducted by computer simulations. A theoretical analysis is developed to obtain a statistical characterization of the agents' status at steady-state, under the simplifying assumption that clustering is made without errors. This provides approximate bounds for the steady-state decision performance of the agents. Insights are provided for deriving accurate performance prediction by exploiting the derived theoretical results
Decision-making algorithms for learning and adaptation with application to COVID-19 data
No full textThis work focuses on the development of a new family of decision-making algorithms for adaptation and learning, which are specifically tailored to decision problems and are constructed by building up on first principles from decision theory. A key observation is that estimation and decision problems are structurally different and, therefore, algorithms that have proven successful for the former need not perform well when adjusted for the latter. Exploiting classical tools from quickest detection, we propose a tailored version of Page's test, referred to as BLLR (barrier log-likelihood ratio) test, and demonstrate its applicability to real-data from the COVID-19 pandemic in Italy. The results illustrate the ability of the design tool to track the different phases of the outbreak
Adaptation and Learning in Multi-Task Decision Systems
No full textAdaptation and learning over multi-agent networks is a topic of great relevance with important implications. Elaborating on previous works on single-task networks engaged in decision problems, here we consider the multi-task version in the challenging scenario where the state of nature may change arbitrarily. We propose a data diffusion scheme for tracking these changes in real time, and investigate by numerical simulations the corresponding steady-state decision performance. For the slow-adaptation regime, the complete analytical characterization of the agents' status is provided, under the simplifying assumption that the network connection matrix is correctly estimated
Adaptation in online social learning
No full textThis work studies social learning under non-stationary conditions. Although designed for online inference, traditional social learning algorithms perform poorly under drifting conditions. To mitigate this drawback, we propose the Adaptive Social Learning (ASL) strategy. This strategy leverages an adaptive Bayesian update, where the adaptation degree can be modulated by tuning a suitable step-size parameter. The learning performance of the ASL algorithm is examined by means of a steady-state analysis. It is shown that, under the regime of small step-sizes: i) consistent learning is possible; ii) and an accurate prediction of the performance can be furnished in terms of a Gaussian approximation
Local Tomography of Large Networks under the Low-Observability Regime
Full text linkThis article studies the problem of reconstructing the topology of a network of interacting agents via observations of the state-evolution of the agents. We focus on the large-scale network setting with the additional constraint of partial observations, where only a small fraction of the agents can be feasibly observed. The goal is to infer the underlying subnetwork of interactions and we refer to this problem as local tomography. In order to study the large-scale setting, we adopt a proper stochastic formulation where the unobserved part of the network is modeled as an Erdős-Rényi random graph, while the observable subnetwork is left arbitrary. The main result of this work is to establish that, under this setting, local tomography is actually possible with high probability, provided that certain conditions on the network model are met (such as stability and symmetry of the network combination matrix). Remarkably, such conclusion is established under the low-observability regime, where the cardinality of the observable subnetwork is fixed, while the size of the overall network scales to infinity
Graph Learning Over Partially Observed Diffusion Networks: Role of Degree Concentration
No full textThis work examines the problem of learning the topology of a network from the samples of a diffusion process evolving at the network nodes, under the restriction that a limited fraction thereof is probed (partial observability). We provide the following main contributions. Given an estimator of the combination matrix (i.e., the matrix that quantifies the pairwise interaction between nodes), we introduce the notion of identifiability gap, a minimum separation between the entries of the estimated matrix that is critical to enable discrimination between connected and unconnected node pairs. Then we focus on the popular Granger estimator. First, we prove that this matrix estimator, followed by a universal clustering algorithm inspired by the k-means algorithm, learns faithfully the probed subgraph as the network size increases. This result is proved for the case where the network topology is obtained through an Erdős-Rényi random graph under statistical concentration of the node degrees, and the combination matrix is symmetric with nonzero entries bounded in terms of the reciprocal of the maximal and minimal degree. The analysis explores different connectivity regimes, including the dense regime where the probed nodes are influenced by many connections coming from the latent (hidden) part of the graph. Second, we answer a sample complexity question and establish that the number of samples for the Granger estimator scales almost quadratically with the expected graph degree. We also propose three other estimators that are proved to achieve faithful graph learning, and compare them to the Granger estimator, gaining nontrivial insights especially for the case of directed graphs
Distributed Adaptive Learning Under Communication Constraints
No full textWe consider a network of agents that must solve an online optimization problem from continual observation of streaming data. To this end, the agents implement a distributed cooperative strategy where each agent is allowed to perform local exchange of information with its neighbors. In order to cope with communication constraints, the exchanged information must be compressed to reduce the communication load. We propose a distributed diffusion strategy nicknamed as ACTC (Adapt-Compress-Then-Combine), which implements the following three operations: adaptation, where each agent performs an individual stochastic-gradient update; compression, which leverages a recently introduced class of stochastic compression operators; and combination, where each agent combines the compressed updates received from its neighbors. The main elements of novelty of this work are as follows: i) adaptive strategies, where constant (as opposed to diminishing) step-sizes are critical to infuse the agents with the ability of responding in real time to nonstationary variations in the observed model; ii) directed, i.e., non-symmetric combination policies, which allow us to enhance the role played by the network topology in the learning performance; iii) global strong convexity, a condition under which the individual agents might feature even non-convex cost functions. Under this demanding setting, we establish that the iterates of the ACTC strategy fluctuate around the exact global optimizer with a mean-square-deviation on the order of the step-size, achieving remarkable savings of communication resources. Comparison against up-to-date learning strategies with compressed data highlights the benefits of the proposed solution
Compressed Distributed Regression over Adaptive Networks
No full textWe examine the learning performance achievable by a network of agents that solve a distributed regression problem using the recently proposed ACTC (Adapt-Compress-Then-Combine) diffusion strategy. The agents operate under communication constraints: they are allowed to communicate only with their immediate neighbors, and the exchanged signals are encoded by using randomized differential compression operators. We show that the mean-square estimation error of each agent comprises the error that the agents would achieve without communication constraints plus a compression loss. Our results reveal the fundamental quantitative relationship existing between the compression loss and the peculiar attributes of the distributed regression problem. We show how these quantitative relationships can be used to optimize the allocation of communication resources across the agents and improve their learning performance as compared to a uniform allocation
- …
