The role of the network in distributed optimization algorithms: convergence rates, scalability, communication/ computation tradeoffs and communication delays

Many questions of interest in various fields ranging from machine learning to computational biology and finance require the solution of an optimization problem. Frequently such problems are classified as large scale in the sense that they involve complex computations over very large datasets. The increasing interest in distributed optimization algorithms is motivated by two main reasons. First, the problem complexity pushes today's processors to their limits and the need for distributed algorithms arises quite naturally. A second and more practical reason is that sometimes the data is collected in a distributed manner and transmitting it to a single location is either too costly or violates privacy. The starting point of this thesis is the simple realization that the main difference between a serial and a distributed algorithm is that in the latter, a processor needs to exchange messages over a network to access another processor's information. Network communication is in general less reliable and orders of magnitude slower than local disk accesses. Furthermore, in an arbitrary network topology to achieve global performance messages might need to travel over multiple hops. Finally, the hardware's capabilities also limit the ways in which a distributed algorithm may be implemented. All these factors highlight the important role of the network in distributed optimization algorithms. To understand that role we focus on the class of consensus-based distributed optimization algorithms. Those algorithms admit an elegant theoretical analysis while remaining easy to implement. In addition they tend to be scalable and robust to communication delays. The contributions of this work can be grouped into four important areas: 1) understanding the communication/computation tradeoff and its effect on scalability with the network size, 2) understanding the limitations of the network and the necessary features that distributed algorithms need to possess to be practical, 3) understanding the effects on convergence of network-induced communication delays and 4) understanding the theoretically achievable convergence rates of distributed algorithms. These areas impact the design and deployment of any consensus-based distributed optimization algorithm.Il y a une grande variété de domaines d'apprentissage automatique, de la biologie à la finance, où l'on doit résoudre des problèmes d'optimisation. Souvent ces problèmes impliquent des calculs complexes sur de vastes ensembles de données. Pour résoudre ces problèmes le développement d'algorithmes distribués est devenu très populaire pour deux raisons. Premièrement, la complexité des problèmes pousse les processeurs actuels à leurs limites. Naturellement, il devient essentiel d'utiliser des systèmes distribués. La deuxième raison est que la collecte des données est parfois distribuée, et il est difficile, coûteux ou en violation d'accords de confidentialité de transférer toutes les données au même endroit. La fondation de cette thèse est la réalisation simple que la grande différence entre un algorithme centralisé et un algorithme distribué est que ce dernier utilise un réseau pour permettre l'échange d'information d'un processeur à un autre. Généralement, la communication sur un réseau est moins fiable et beaucoup plus lente que l'accès d'information sur un disque local. De plus, pour une topologie de réseau arbitraire, la communication de messages nécessite plusieurs sauts. Finalement, les capacités matérielles aussi limitent les façons par lequelles les algorithmes distribués théoriques peuvent être mis en oeuvre. Tous ces facteurs, rappellent l'importance du réseau. Pour comprendre cette importance, nous nous concentrons, sur la classe des algorithmes de consensus pour optimisation distribuée. Ces algorithmes aussi possèdent des analyses théoriques très élégantes tout en restant faciles a mettre en oeuvre. Aussi, ils sont robustes aux délais de communication et extensibles. Les contributions de cette thèse peuvent être classifiées selon les quatres catégories suivantes: 1) comprendre le compromis entre communication et calculs locaux, et l'extensibilité avec la taille du réseau, 2) comprendre les limites posées par le réseau aux fonctionnalités nécessaires que chaque algorithme distribué doit possèder en pratique, 3) comprendre les effets de délais de communication et les propriétés de convergence de ces algorithmes en présence de délais, 4) comprendre les taux théoriques de convergence des algorithmes d'optimisation distribués. Tous ces domaines affectent la conception et le déploiement de chaque algorithme de consensus d'optimisation distribué