1,721,210 research outputs found
Managing information constraints over networks through the lens of configuration functions
No full textThis work deals with networks of agents that exchange information under communication constraints. As a first contribution, the theory of configuration functions is exploited to obtain a general abstract formulation of the network information as a function of the network constraints. As a second contribution, two classic network paradigms are examined: i) a decentralized architecture with remote fusion center; and ii) a fully-flat decentralized architecture with local data exchange between neighboring agents. It is shown how these paradigms match well with the general formulation in terms of configuration functions. Finally, the statistical concentration properties of configuration functions are exploited to characterize the information growth rate under both the aforementioned network paradigms, revealing the thermodynamic deterministic behavior that emerges with high probability as the network size scales to infinity
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
Social Learning with Partial Information Sharing
No full textThis work studies the learning abilities of agents sharing partial beliefs over social networks. The agents observe data that could have risen from one of several hypotheses and interact locally to decide whether the observations they are receiving have risen from a particular hypothesis of interest. To do so, we establish the conditions under which it is sufficient to share partial information about the agents' belief in relation to the hypothesis of interest. Some interesting convergence regimes arise
Partial Information Sharing Over Social Learning Networks
No full textThis work addresses the problem of sharing partial information within social learning strategies. In social learning, agents solve a distributed multiple hypothesis testing problem by performing two operations at each instant: first, agents incorporate information from private observations to form their beliefs over a set of hypotheses; second, agents combine the entirety of their beliefs locally among neighbors. Within a sufficiently informative environment and as long as the connectivity of the network allows information to diffuse across agents, these algorithms enable agents to learn the true hypothesis. Instead of sharing the entirety of their beliefs, this work considers the case in which agents will only share their beliefs regarding one hypothesis of interest, with the purpose of evaluating its validity, and draws conditions under which this policy does not affect truth learning. We propose two approaches for sharing partial information, depending on whether agents behave in a self-aware manner or not. The results show how different learning regimes arise, depending on the approach employed and on the inherent characteristics of the inference problem. Furthermore, the analysis interestingly points to the possibility of deceiving the network, as long as the evaluated hypothesis of interest is close enough to the truth
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
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
Tomography of Large Adaptive Networks under the Dense Latent Regime
No full textThis work examines the problem of graph learning over a diffusion network when measurements can only be gathered from a limited fraction of agents (latent regime). Under this selling, most works in the literature rely on a degree of sparsity to provide guarantees of consistent graph recovery. This work moves away from this condition and shows that, even under dense connectivity, the Granger estimator ensures an identifiability gap that enables the discrimination between connected and disconnected nodes within the observable subnetwork
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
- …
