Beyond gradients : zero-order approaches to optimization and learning in multi-agent environments

Au-delà des gradients : approches sans gradient pour l'optimisation et l'apprentissage dans des environnements multi-agents L'essor des dispositifs connectés et des données qu'ils génèrent a stimulé le développement d'applications à grande échelle. Ces dispositifs forment des réseaux distribués avec un traitement de données décentralisé. À mesure que leur nombre augmente, des défis comme la surcharge de communication et les coûts computationnels se présentent, nécessitant des méthodes d'optimisation adaptées à des contraintes de ressources strictes, surtout lorsque les dérivées sont coûteuses ou indisponibles. Cette thèse se concentre sur les méthodes d'optimisation sans dérivées, qui sont idéales quand les dérivées des fonctions sont inaccessibles. Ces méthodes estiment les gradients à partir des évaluations de fonction, ce qui les rend adaptées à l'apprentissage distribué et fédéré, où les dispositifs collaborent pour résoudre des tâches d'optimisation avec peu d'informations et des données bruitées. Dans le premier chapitre, nous traitons de l'optimisation distribuée sans dérivées pour des fonctions fortement convexes sur plusieurs agents. Nous proposons un algorithme distribué de descente de gradient projete sans dérivées, qui utilise des estimations de gradient à un point, où la fonction est interrogée une seule fois par réalisation stochastique, et les évaluations sont bruitées. Ce chapitre démontre la convergence presque sûre de l'algorithme et fournit des bornes théoriques sur le taux de convergence. Avec des pas constants, l'algorithme atteint un taux de convergence linéaire. C'est la première fois que ce taux est établi pour des estimations de gradient à un point (voire même pour des estimations de gradient à deux points) pour des fonctions stochastiques. Nous analysons aussi les effets des pas décroissants, établissant un taux de convergence correspondant aux méthodes centralisées sans dérivées. Le deuxième chapitre se penche sur les défis de l'apprentissage fédéré qui est limité par le coût élevé de la transmission de données sur des réseaux à bande passante restreinte. Pour y répondre, nous proposons un nouvel algorithme qui réduit la surcharge de communication en utilisant des estimations de gradient à un point. Les dispositifs transmettent des valeurs scalaires plutôt que de grands vecteurs de gradient, réduisant ainsi la quantité de données envoyées. L'algorithme intègre aussi directement les perturbations des communications sans fil dans l'optimisation, éliminant le besoin de connaître explicitement l'état du canal. C'est la première approche à inclure les propriétés du canal sans fil dans un algorithme d'apprentissage, le rendant résilient aux problèmes de communication réels. Nous prouvons la convergence presque sûre de cette méthode dans des environnements non convexes et validons son efficacité à travers des expériences. Le dernier chapitre étend l'algorithme précédent au cas des estimations de gradient à deux points. Contrairement aux estimations à un point, les estimations à deux points interrogent la fonction deux fois, fournissant une approximation plus précise du gradient et améliorant le taux de convergence. Cette méthode conserve l'efficacité de communication des estimations à un point, avec uniquement des valeurs scalaires transmises, et assouplit l'hypothèse de bornitude de la fonction objective. Nous prouvons des taux de convergence linéaires pour des fonctions fortement convexes et lisses. Pour les problèmes non convexes, nous montrons une amélioration notable du taux de convergence, en particulier pour les fonctions dominées par le gradient K, atteignant également un taux linéaire. Nous fournissons aussi des résultats montrant l'efficacité de communication par rapport à d'autres techniques d'apprentissage fédéré.