Performance guarantees of distributed learning in adversarial environments

The real world is inherently distributed and interconnected, where no single agent can have full access to the totality of information that is available in a dispersed manner across a multitude of agents. Distributed learning has emerged as a key paradigm to address this challenge, enabling agents to cooperatively solve global problems of interest through information exchange. While centralized methods rely on a fusion center that aggregates data and manages the entire computation, decentralized methods allow agents to operate collaboratively by relying mainly on neighbor-to-neighbor communication. However, distributed learning continues to face some important theoretical and practical challenges. One important challenge is their performance in the face of adversarial attacks, where imperceptible perturbations can degrade performance. This dissertation investigates the performance of distributed learning strategies in both standard and adversarial environments, and reveals some interesting properties in relation to their stability guarantees and robustness.

The first part of the dissertation examines the standard setting, providing a systematic comparison of the performance of centralized and decentralized learning strategies. Previous works on learning by stand-alone agents have noticed that convergence toward flat local minima tend to enhance the generalization ability of learning algorithms. This work discovers three interesting results. First, it shows that decentralized learning strategies favor convergence toward flatter minima relative to the centralized solution. Second, in decentralized methods, the consensus strategy has a worse excess-risk performance than diffusion, giving it a better chance of escaping from local minima and favoring flatter minima. Third, and importantly, the classification accuracy is a function of both flatness and optimization performance. This first half of the dissertation examines the interplay between the two measures of flatness and optimization error closely. One important conclusion is that decentralized strategies deliver in general enhanced classification accuracy because they strike a more favorable balance between flatness and optimization performance compared to the centralized solution.

The second part of the dissertation focuses on distributed learning in adversarial environments. First, motivated by the extensive study of adversarial training as a means to enhance model robustness, this part extends this framework to distributed settings over graphs, where individual agents are subjected to perturbations of varied strength levels across space. Using a min-max formulation of distributed learning, the dissertation develops a distributed adversarial training framework for multi-agent systems and establishes convergence guarantees for strongly-convex, convex, and non-convex environments. Next, this second part of the dissertation analyzes the optimization bias of different distributed adversarial