This paper studies the problem of interconnected agents collaborating to track a dynamic state from partially informative observations, where the dynamic state evolves according to a slowly varying finite-state Markov chain. Although the centralized version of this problem has been extensively studied in the literature, the decentralized setting, particularly in the context of social learning, remains largely underexplored. The main result of this work is to establish that adaptive social learning (ASL), a recent social learning strategy suited for non-stationary environments, achieves the same error probability scaling law as the centralized solution in the rare transitions regime. Theoretical findings are supported by simulations, offering valuable insights into social learning under Markovian state transitions.

This paper studies the probability of error associated with the social machine learning framework, which involves an independent training phase followed by a cooperative decision-making phase over a graph. This framework addresses the problem of classifying a stream of unlabeled data in a distributed manner. In this work, we examine the classification task with limited observations during the decision-making phase, which requires a non-asymptotic performance analysis. We establish a condition for consistent training and derive an upper bound on the probability of error for classification. The results clarify the dependence on the statistical properties of the data and the combination policy used over the graph. They also establish the exponential decay of the probability of error with respect to the number of unlabeled samples.

In social learning, a network of agents assigns probability scores (beliefs) to some hypotheses of interest, based on the observation of streaming data. First, each agent updates locally its belief with the information extracted from the current data through a suitable likelihood model. Then, these beliefs are diffused across the network, and the agents aggregate the beliefs received from their neighbors by means of a pooling rule. This work studies social learning in the context of fully online problems, where the true hypothesis and the likelihood models can drift over time. Traditional social learning fails to address both cases. To overcome this limitation, we propose the doubly adaptive social learning (A2SL) strategy, which infuses traditional social learning with the necessary adaptation capabilities to face drifts in the hypotheses and/or models. The A2SL strategy achieves this goal by employing two adaptation stages, and we show that all agents learn well (i.e., they end up placing full belief mass on the correct hypothesis) in the regime of small adaptation parameters.

Social learning algorithms provide a model for the formation and propagation of opinions over social networks. However, most studies focus on the case in which agents share their information synchronously over regular intervals. In this work, we analyze belief convergence and steady-state learning performance for both traditional and adaptive formulations of social learning under asynchronous behavior by the agents, where some of the agents may decide to abstain from sharing any information with the network at some time instants. We also show how to recover the underlying graph topology from observations of the asynchronous network behavior.

In social learning, a group of agents linked by a graph topology collect data and exchange opinions on some topic of interest, represented by a finite set of hypotheses. Traditional social learning algorithms allow all agents in the network to gain full confidence on the true underlying hypothesis as the number of observations increases. Under partial information sharing, agents can exchange opinions only on a single hypothesis. This introduces significant challenges as compared to the standard case of full opinion sharing. We propose a novel strategy where each agent forms a valid belief by completing the partial beliefs received from its neighbors. The completion process exploits the knowledge accumulated in the past beliefs, thanks to a principled memory-aware rule inspired by a Bayesian criterion. We provide a detailed characterization of the memory-aware strategy, which reveals novel learning dynamics and highlights its advantages over previously considered schemes.

This paper studies the non-asymptotic classification performance of the social machine learning strategy. This strategy involves an independent training phase followed by a cooperative inference phase to classify a growing number of samples. By considering instead a finite number of samples, we provide an upper bound for the probability of misclassification. This bound helps characterize the generalization ability of the social machine learning strategy, in terms of the statistical properties of the classification problem and the combination policy among the distributed classifiers. The analysis establishes the exponential decay of the probability of error with the number of samples when the training phase is consistent.

This 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.

This work proposes a decentralized architecture, where individual agents aim at solving a classification problem while observing streaming features of different dimensions and arising from possibly different distributions. In the context of social learning, several useful strategies have been developed, which solve decision making problems through local cooperation across distributed agents and allow them to learn from streaming data. However, traditional social learning strategies rely on the fundamental assumption that each agent has significant prior knowledge of the underlying distribution of the observations. In this work we overcome this issue by introducing a machine learning framework that exploits social interactions over a graph, leading to a fully data-driven solution to the distributed classification problem. In the proposed social machine learning (SML) strategy, two phases are present: in the training phase, classifiers are independently trained to generate a belief over a set of hypotheses using a finite number of training samples; in the prediction phase, classifiers evaluate streaming unlabeled observations and share their instantaneous beliefs with neighboring classifiers. We show that the SML strategy enables the agents to learn consistently under this highly-heterogeneous setting and allows the network to continue learning even during the prediction phase when it is deciding on unlabeled samples. The prediction decisions are used to continually improve performance thereafter in a manner that is markedly different from most existing static classification schemes where, following training, the decisions on unlabeled data are not re-used to improve future performance.

Adaptive social learning is a useful tool for studying distributed decision-making problems over graphs. This paper investigates the effect of combination policies on the performance of adaptive social learning strategies. Using large-deviation analysis, it first derives a bound on the steady-state error probability and characterizes the optimal selection for the Perron eigenvectors of the combination policies. It subsequently studies the effect of the combination policy on the transient behavior of the learning strategy by estimating the adaptation time in the low signal-to-noise ratio regime. In the process, it is discovered that, interestingly, the influence of the combination policy on the transient behavior is insignificant, and thus it is more critical to employ policies that enhance the steady-state performance. The theoretical conclusions are illustrated by means of computer simulations.

In this paper we study the problem of social learning under multiple true hypotheses andself-interestedagents that exchange information over a graph. In this setup, each agent receives data that might be generated from a different hypothesis (or state) than the data received by the other agents. In contrast to the related literature on social learning, which focuses on showing that the network achieves consensus, here we study the case where every agent is self-interested and wishes to find the hypothesis that generates its own observations. Moreover, agents do not know which other agents among their peers want to discover the same state as theirs. As a result they do not know which agents they should cooperate with. To enable learning under these conditions, we propose a strategy withadaptivecombination weights and study the consistency of the agents’ learning process. The method allows each agent to identify and collaborate with neighbors that observe the same hypothesis, while excluding others, thus resulting in improved performance compared to both non-cooperative learning and cooperative social learning solutions. We analyze the asymptotic behavior of agents’ beliefs and provide conditions that enable all agents to correctly identify their true hypotheses. The theoretical analysis is corroborated by numerical simulations.

This paper investigates the effect of combination policies on the performance of adaptive social learning in non-stationary environments. By analyzing the relation between the error probability and the underlying graph topology, we prove that in the slow adaptation regime, combination policies with a uniform Perron eigenvector will provide the smallest steady-state error probability. This result indicates that in terms of learning accuracy, doubly-stochastic combination policies yield optimal performance. Moreover, we estimate the adaptation time of adaptive social learning in the small signal-to-noise regime and show that in this regime, the influence of combination policies on the adaptation time is insignificant.

Observations collected by agents in a network may be unreliable due to observation noise or interference. This paper proposes a distributed algorithm that allows each node to improve the reliability of its own observation by relying solely on local computations and interactions with immediate neighbors, assuming that the field (graph signal) monitored by the network lies in a low-dimensional subspace and that a low-rank noise is present in addition to the usual full-rank noise. While oblique projections can be used to project measurements onto a low-rank subspace along a direction that is oblique to the subspace, the resulting solution is not distributed. Starting from the centralized solution, we propose an algorithm that performs the oblique projection of the overall set of observations onto the signal subspace in an iterative and distributed manner. We then show how the oblique projection framework can be extended to handle distributed learning and adaptation problems over networks.

This work proposes a new way of combining independently trained classifiers over space and time. Combination over space means that the outputs of spatially distributed classifiers are aggregated. Combination over time means that the classifiers respond to streaming data during testing and continue to improve their performance even during this phase. By doing so, the proposed architecture is able to improve prediction performance over time with unlabeled data. Inspired by social learning algorithms, which require prior knowledge of the observations distribution, we propose a Social Machine Learning (SML) paradigm that is able to exploit the imperfect models generated during the learning phase. We show that this strategy results in consistent learning with high probability, and it yields a robust structure against poorly trained classifiers. Simulations with an ensemble of feedforward neural networks are provided to illustrate the theoretical results.

A common assumption in the social learning literature is that agents exchange information in an unselfish manner. In this work, we consider the scenario where a subset of agents aims at driving the network beliefs to the wrong hypothesis. The adversaries are unaware of the true hypothesis. However, they will "blend in" by behaving similarly to the other agents and will manipulate the likelihood functions used in the belief update process to launch inferential attacks. We will characterize the conditions under which the network is misled. Then, we will explain that it is possible for such attacks to succeed by showing that strategies exist that can be adopted by the malicious agents for this purpose. We examine both situations in which the agents have minimal or no information about the network model.

This work proposes a novel strategy for social learning by introducing the critical feature of adaptation. In social learning, several distributed agents update continually their belief about a phenomenon of interest through: i) direct observation of streaming data that they gather locally; and ii) diffusion of their beliefs through local cooperation with their neighbors. Traditional social learning implementations are known to learn well the underlying hypothesis (which means that the belief of every individual agent peaks at the true hypothesis), achieving steady improvement in the learning accuracy under stationary conditions. However, these algorithms do not perform well under nonstationary conditions commonly encountered in online learning, exhibiting a significant inertia to track drifts in the streaming data. In order to address this gap, we propose an Adaptive Social Learning (ASL) strategy, which relies on a small step-size parameter to tune the adaptation degree. First, we provide a detailed characterization of the learning performance by means of a steady-state analysis. Focusing on the small step-size regime, we establish that the ASL strategy achieves consistent learning under standard global identifiability assumptions. We derive reliable Gaussian approximations for the probability of error (i.e., of choosing a wrong hypothesis) at each individual agent. We carry out a large deviations analysis revealing the universal behavior of adaptive social learning: the error probabilities decrease exponentially fast with the inverse of the step-size, and we characterize the resulting exponential learning rate. Second, we characterize the adaptation performance by means of a detailed transient analysis, which allows us to obtain useful analytical formulas relating the adaptation time to the step-size. The revealed dependence of the adaptation time and the error probabilities on the step-size highlights the fundamental trade-off between adaptation and learning emerging in adaptive social learning.

This 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.

In social learning, agents form their opinions or beliefs about certain hypotheses by exchanging local information. This work considers the recent paradigm of weak graphs, where the network is partitioned into sending and receiving components, with the former having the possibility of exerting a domineering effect on the latter. Such graph structures are prevalent over social platforms. We will not be focusing on the direct social learning problem (which examines what agents learn), but rather on the dual or reverse learning problem (which examines how agents learned). Specifically, from observations of the stream of beliefs at certain agents, we would like to examine whether it is possible to learn the strength of the connections (influences) from sending components in the network to these receiving agents.