Data-Driven Distributed Optimization via Aggregative Tracking and Deep-Learning

Résumé Technique : Optimisation Distribuée Pilotée par les Données via le Suivi Agrégatif et l'Apprentissage Profond (DELTA)

Formulation du Problème
L'article traite du défi de l'optimisation distribuée dans un cadre agrégatif où un réseau de $N$ agents cherche à minimiser de manière coopérative la somme de leurs fonctions de coût locales. Contrairement à l'optimisation distribuée standard, le coût local $f_i$ de chaque agent dépend non seulement de sa propre variable de décision $x_i$, mais aussi d'une variable agrégative globale $\sigma(x)$, définie comme la moyenne des contributions locales $\phi_i(x_i)$.

Le scénario spécifique considéré est piloté par les données (data-driven) et inconnu :

1. Les fonctions $f_i$ sont entièrement inconnues des agents.
2. Les agents ne peuvent obtenir qu'un seul échantillon de retour de leur coût local par itération (une évaluation « en 1 point ») à un point choisi $(u_{x,i}, u_{\sigma,i})$.
3. Les quantités globales (la variable agrégative $\sigma(x)$ et la dérivée du coût global par rapport à celle-ci) ne sont pas disponibles localement.

Cette configuration est motivée par des applications telles que la robotique coopérative et l'optimisation personnalisée, où les fonctions de coût peuvent représenter une insatisfaction de l'utilisateur ou des contraintes physiques difficiles à modéliser analytiquement, mais qui peuvent être échantillonnées via des capteurs ou des retours utilisateurs.

Méthodologie : L'Algorithme DELTA
Les auteurs proposent DELTA (DEep-Learning aggregative TrAcking), un algorithme distribué qui opère sur une échelle de temps unique et intègre trois composantes concomitantes :

1. Module Orienté Apprentissage :

   • Chaque agent $i$ utilise un réseau de neurones (NN) local $\hat{f}_i(\cdot, \theta_i)$ pour approximer la fonction de coût inconnue $f_i$ et ses gradients.
   • Au lieu d'entraîner le réseau jusqu'à convergence entre les étapes d'optimisation (ce qui est coûteux en calcul et nécessite plusieurs échantillons), le NN est mis à jour via une descente de gradient en une seule étape utilisant l'échantillon de coût unique obtenu à chaque itération.
   • Pour assurer une excitation persistante pour l'apprentissage, l'algorithme injecte des signaux de dither ($d_{x,i}, d_{\sigma,i}$) dans les points d'échantillonnage.
   • Le NN approxime la direction de descente, remplaçant ainsi efficacement le besoin d'une connaissance explicite du gradient.

2. Routine Orientée Optimisation :

   • Les agents effectuent une mise à jour de type gradient distribué en utilisant les gradients approximés fournis par leurs réseaux de neurones locaux.
   • La règle de mise à jour combine le gradient local estimé $\nabla_1 \hat{f}_i$ avec un terme impliquant la dérivée de la fonction d'agrégation $\nabla \phi_i$ et la composante de gradient globale estimée.

3. Mécanisme Orienté Suivi (Tracking) :

   • Puisque les quantités globales $\sigma(x)$ et la somme des dérivées de gradient locales sont indisponibles, les agents maintiennent des variables auxiliaires ($w_i$ et $z_i$).
   • Ces variables sont mises à jour via une dynamique de consensus perturbée (utilisant une matrice d'adjacence doublement stochastique) pour reconstruire localement la variable agrégative globale manquante et la composante de gradient globale.

Analyse Théorique et Résultats
La stabilité et la convergence de DELTA sont analysées à l'aide d'outils de la théorie des systèmes, plus précisément la séparation d'échelles de temps et la théorie de la moyenne en temps discret. L'analyse traite l'algorithme comme un système à deux échelles de temps variables, séparant les dynamiques rapides (suivi et apprentissage) des dynamiques lentes (optimisation).

• Garantie de Convergence : Sous les hypothèses de convexité forte du coût global et de continuité de Lipschitz des fonctions et de leurs approximations, les auteurs prouvent que l'algorithme converge linéairement vers un voisinage de la solution optimale $x^*$.
• Borne d'Erreur : Le rayon de ce voisinage dépend explicitement du paramètre $\epsilon$, qui représente l'erreur de reconstruction maximale des réseaux de neurones (c'est-à-dire la précision de l'approximation par le NN à la convergence).
• Cas Idéal : Dans la limite théorique où les réseaux de neurones atteignent une estimation parfaite ($\epsilon = 0$), l'algorithme converge exactement vers la solution optimale.
• Robustesse : La conception permet à l'algorithme de s'adapter à des fonctions de coût variant dans le temps ou à des perturbations sans nécesser de redémarrage complet des processus d'entraînement ou de suivi.

Principales Contributions

1. Intégration Novatrice : L'article introduit un nouveau schéma qui combine l'apprentissage par réseaux de neurones, l'optimisation agrégative distribuée et le suivi de gradient (gradient tracking), spécifiquement adapté aux scénarios avec des évaluations de coût en un seul point.
2. Surmonter les Limitations du "1-Point" : Les méthodes standard de type "zeroth-order 1-point" souffrent souvent de taux de convergence médiocres ou d'une variance élevée. DELTA répond à cela en intéissant une stratégie d'apprentissage dynamique (NN) qui apprend la direction de descente au fil du temps sans augmenter le nombre d'évaluations de coût par itération.
3. Preuve de Convergence Rigoureuse : Les auteurs fournissent une preuve formelle de convergence linéaire dans un voisinage de l'optimum, caractérisant explicitement le compromis entre la précision de l'approximation du réseau de neurones et l'erreur d'optimisation finale.
4. Gestion d'Environnements Inconnus : Le cadre est conçu pour des fonctions de coût totalement inconnues, se distinguant des travaux antérieurs où certaines parties de la fonction de coût étaient connues ou nécessitaient plusieurs échantillons par itération.

Signification et Revendications
L'article affirme que DELTA offre une solution pratique pour l'optimisation personnalisée et le contrôle coopératif dans des environnements inconnus ou non stationnaires (ex: collaboration homme-robot). En exploitant la synergie entre apprentissage, optimisation et suivi, l'algorithme s'adapte dynamiquement aux changements des fonctions de coût.

Les auteurs notent que si une version préliminaire de ce travail existait pour des contextes temporels variables avec plusieurs échantillons et un entraînement complet des NN, la contribution actuelle est techniquement plus exigeante : elle opère avec des échantillons uniques par itération et un entraînement de type "single-step" pour le NN, nécessant une intégration plus complexe de l'analyse de la dynamique d'apprentissage avec l'optimisation et la dynamique de consensus. Des simulations numériques sur un réseau de 20 agents valident les résultats théoriques, démontrant la convergence vers le voisinage optimal et la robustesse face à des changements soudains des fonctions de coût locales.