Virginia Bordignon 2022

Abstract of PhD Dissertation
Electrical and Micro Engineering, EPFL, Switzerland, October 2022
Advisor: Prof. Ali H. Sayed

Opinion Formation over Adaptive Networks

Virginia Bordignon, EPFL, Switzerland

An adaptive network consists of multiple communicating agents, equipped with sensing and learning abilities that allow them to extract meaningful information from measurements. The objective of the network is to solve a global inference problem in a decentralized manner, i.e., by exchanging only local information with neighboring agents.

Such adaptive networks find inspiration in real-world networks, e.g., power networks, biological networks, and social networks. Decentralized solutions allow the network to outperform stand-alone strategies by yielding improved performance and robustness. They also enable agents to overcome their individual limitations by leveraging collaboration during the learning process.

Several of these solutions draw on social learning paradigms, through which individuals form opinions (or beliefs) by observing the world and communicating within their social group. The world is explained by a discrete-valued state, and agents discover the unknown state of the world while updating their beliefs regarding a set of plausible hypotheses. Many such solutions result in consistent truth learning at fast convergence rates. Existing works however fail to account for more realistic assumptions such as the exchange of incomplete information, adaptation under nonstationary conditions, and the use of imperfect private statistical models.

This thesis aims to address the aforementioned problems and answer questions regarding the behavior and performance of social learning strategies under more realistic conditions. This is carried out by exploiting four key elements to learning over adaptive networks, namely, i) network topology, ii) exchanged information, iii) surrounding world, and iv) private models, which we divide in two parts.

In the first part, we focus on the stationary setting, i.e., where world conditions are static. i) The social network is represented by a weakly connected graph, which results in a power asymmetry among network clusters. To estimate the level of influence from influential clusters toward specific agents, we formulate the reverse learning problem. We characterize the feasibility of this problem and show that a certain statistical diversity among components is sufficient for it to be feasible. ii) We consider a strongly connected social network, with constrained communication, i.e., where only partial beliefs are shared with neighbors. We show how different learning regimes arise and under which conditions the agents can learn the truth or, on the other hand, be misled.

In the second part, we address the nonstationary setting. iii) Existing social learning strategies are limited in their ability to adapt under changing world conditions. We propose an adaptive social learning formulation and characterize its performance both in the steady-state and the transient phases. We show that the approach enables a trade-off between learning accuracy and adaptation capability. iv) Social learning agents use statistical models that are assumed to be perfectly known a priori. We propose a social machine learning framework, where the models are first trained from a finite set of labeled samples and then deployed in a collaborative implementation to classify streaming unlabeled (possibly nonstationary) observations. We show that the proposed fully data-based strategy results in consistent learning, despite the imprecise models, and in improved accuracy as the number of unlabeled observations grows.

This dissertation is based upon work partially supported by the Swiss National Science Foundation (SNSF) under Grant 205121-184999.