Asynchronous subgradient push: fast, robust, and scalable multi-agent optimization

The need to develop distributed optimization methods is rooted in practical applications involving the processing of data that is naturally distributed, private, or simply too large to store on a single machine. In the past decade, a large number of distributed algorithms for solving large-scale convex optimization problems have been proposed and analyzed in the literature, especially from the perspective of multi-agent systems. Although it is fairly well understood which algorithms have the most desirable theoretical properties, many of the theoretical analyses ignore important practical issues such as asynchronism and communication delays. As a result, it is often the case that algorithms with the most desirable theoretical properties (eg, fastest convergence rates in iterations) do not necessarily have the most desirable properties in practice (eg, fastest convergence rates in time). Based on this observation, we propose a new distributed optimization algorithm termed Asynchronous Subgradient-Push. Through numerical experiments we demonstrate that Asynchronous Subgradient-Push converges faster than the state-of-the-art multi-agent methods in practice, is more robust to failing/stalling agents, and scales better with the network size. Motivated by the method's superior empirical performance, we develop a convergence theory, and, in particular, show that a subsequence of the iterates at each agent converges to a neighbourhood of the global minimum, where the size of the neighbourhood depends on the degree of asynchrony in the multi-agent network. We also implement the state-of-the-art first-order methods compared in this work using the MPI (Message Passing Interface) standard for message-passing in clusters, and make them available to the community. In addition, throughout the process of our analysis we develop some peripheral results concerning an asynchronous version of the Push-Sum algorithm for consensus averaging --- a building block for many of the state-of-the-art distributed optimization methods proposed in the literature --- that are interesting in their own respect. In particular, we show that agents running the Push-Sum consensus-averaging algorithm asynchronously converge to the average of the network R-Linearly, where the constant of geometric convergence depends on the maximum delay and the connectivity of the communication topology, and this convergence holds even in the presence of exogenous perturbations at each agent that seek to derail the consensus process.Le besoin de développer des méthodes d'optimisation distribuées est nécessaire dans des applications pratiques impliquant le traitement de données naturellement distribuées, privées, ou simplement trop grandes à stocker sur une seule machine. Au cours de la dernière décennie, un grand nombre d'algorithmes distribués ont été trouveés pour résoudre des problèmes d'optimisation convexe à grande échelle, en particulier pour les systèmes multi-agents. Même si les algorithmes avec des propriétés théoriques les plus souhaitables sont connus, beaucoup d'analyses théoriques ignorent des problèmes pratiques importants, tels que l'asynchronisme et les délais de communication. Par conséquent, il arrive souvent que ces algorithmes ayant des propriétés théoriques souhaitables (par exemple, un taux de convergence rapide en itérations) n'aient pas nécessairement les propriétés les plus souhaitables en pratique (par exemple, un taux de convergence rapide en temps). Sur la base de cette observation, nous proposons un nouvel algorithme d'optimisation distribuée appelé: "Asynchronous Subgradient-Push". Grâce à des expériences numériques, nous démontrons que "Asynchronous Subgradient-Push" converge plus rapidement que les méthodes multi-agents de pointe dans la pratique, est plus robuste aux agents défaillants / bloquants, et évolue mieux avec la taille du réseau. Motivés par la performance empirique supérieure de la méthode, nous développons une théorie de convergence et démontrons en particulier qu'une sous-séquence des itérations de chaque agent converge vers un voisinage du minimum global, où la taille du voisinage dépend du degré d'asynchronie dans le réseau multi-agent. De plus, nous implémentons les méthodes de premier ordre en utilisant la norme MPI (Message Passing Interface) pour la transmission de messages dans des grappes de calcul les comparons avec notre travail, et les mettons à la disposition de la communauté. De plus, tout au long du processus de notre analyse, nous développons des résultats périphériques concernant une version asynchrone de l'algorithme "Push-Sum" pour le consensus de moyenne --- une élément fondamental de plusieurs des méthodes d'optimisation distribuées de pointe proposées dans la littérature --- qui sont intéressants dans leur propre égard. En particulier, nous montrons que les agents exécutant l'algorithme de consensus de moyenne de type "push-sum" convergent à un taux géométrique de façon asynchrone vers la moyenne du réseau. La convergence géométrique dépend du délai maximum et de la connectivité de la topologie de communication, et cette convergence est toujours valable même en présence de perturbations exogènes de chaque agent qui cherchent à faire dérailler le processus consensuel