A multi-agent system consists of a collection of decision-making or learning agents subjected to streaming observations from some real-world phenomenon. The goal of the system is to solve some global learning or optimization problem in a distributed or decentralized manner, where agents collect data locally and interact either with their neighbours or with some central processor.
Such multi-agent systems are prevalent in multiple real-world applications, such as autonomous driving, multi-robot systems, multi-sensor systems, target surveillance, and disaster response, to name a few. Decentralized and distributed solutions are often motivated by the nature of the system, e.g., weather data is naturally distributed across different geographic locations, or these solutions are preferable due to their enhanced robustness to link and node failures.
In designing multi-agent systems, one normally formulates a global risk function, consisting of the aggregate of local risks, and then seeks to approximate its optimizer through localized interactions among neighbouring agents. During this process, the agents will be required to share processed data and/or iterates with their neighbours. The issue of privacy then becomes critical in enabling the safe communication of information over edges linking the elements of the multi-agent network. There have been several works in the literature that enforce privacy by adding random noise sources on top of the shared information. Most of these works establish that the resulting architectures are differentially private, but they assume that the gradients of the risk functions are bounded. Unfortunately, this condition is rarely valid in practice and this fact is often overlooked in most studies. For example, even quadratic risk functions have unbounded gradients because these gradients will be affine functions of the unknown parameter. Moreover, most studies fail to recognise that their differentially private solutions and the added noise sources end up degrading the mean-square error (MSE) performance of the learning algorithms from O(μ) down to O(1/μ), where μ is the small learning parameter. These are serious limitations that remain unaddressed in existing approaches to differential privacy in multi-agent systems.
In this dissertation, we resolve these two issues. First, we do not assume bounded gradients for the risk functions. And yet, we are still able to establish that the multiagent systems remain differentially private, albeit with high probability. We achieve this conclusion by showing that the noise sources should not be added in an ad-hoc manner, as is common in existing approaches, but rather that they should be constructed in a manner that is cognizant of the graph topology. Otherwise, the noises end up generating a magnifying effect that degrades performance. For this reason, we introduce a locally homomorphic noise construction and show that, under this process, the MSE performance of the multi-agent system will remain at O(μ) while being differentially private at the same time. This is a reassuring conclusion. We illustrate these results for the special case of federated learning architectures, but also extend them to more general distributed learning and optimisation strategies over decentralised architectures.
Motivated by these considerations, the first part of the dissertation studies a particular distributed multi-agent system, known as federated learning (FL). The federated setting consists of a central server that orchestrates the learning process among a collection of edge devices. We refer to this set-up as a distributed architecture (as opposed to the decentralized architecture without central processing, studied in the third part of the dissertation). Some use cases of the technology can be found in the healthcare industry, the insurance sector, IoT applications, and other technologies such as predictive text or voice recognition. We examine a couple of questions related to the performance of the FL algorithm. First, we establish its convergence under three demanding characteristics related to data heterogeneity, asynchronous operation, and partial agent participation. Then, we show how performance can be improved by introducing a mechanism based on importance sampling to choose the participating agents and the data samples during each stage of the learning process in some optimized manner. Finally, we introduce a privatization layer and explain how its implementation does not degrade performance.
The second part of the dissertation introduces a more realistic architecture for the federated setting. Instead of assuming a single-server structure, we now consider a network of servers linked together by a graph topology. In other words, we use the results from the first part to show how to construct a reliable multi-server (or graph-based) FL architecture with privacy guarantees. The new setting is referred to as graph federated learning (GFL), and it is more robust to server breakdowns and communication failures. We examine two privacy schemes, one of them is similar to earlier approaches in the literature for multi-agent systems and relies on the addition of ad-hoc Laplacian noise over the edges, while the second approach relies on graph-homomorphic noise sources. We show how these schemes influence performance, with the second method keeping the MSE performance at expected levels while guaranteeing privacy.
Finally, in the third part of the dissertation, we consider a broader multi-agent setting, without a centralized processor. It consists of a decentralized architecture where all processing is localized and agents can only interact with their neighbours. We again devise a reliable privatization scheme for this more general setting, which is useful for decentralized optimization and learning strategies. The scheme again ensures differential privacy without degrading the expected MSE performance of the network.
Keywords: multi-agent system, distributed learning, decentralized learning, federated learning, diffusion learning, differential privacy.