Adaptive Decentralized Composite Optimization via Three-Operator Splitting

1. Problématique

L'article aborde le problème d'optimisation composite décentralisée sur un réseau d'agents. Le problème (noté P) consiste à minimiser une somme de fonctions de perte locales lisses (fortement) convexes $f_i(x)$ et de termes de régularisation non lisses convexes $r_i(x)$ :

$$\min_{x \in \mathbb{R}^d} u(x) := \sum_{i=1}^m f_i(x) + \sum_{i=1}^m r_i(x)$$

Contraintes et défis spécifiques :

• Architecture décentralisée : Les agents sont connectés via un graphe non orienté et connecté, sans serveur central. Chaque agent ne connaît que ses propres fonctions $f_i$ et $r_i$.
• Lissage local : Les fonctions $f_i$ sont supposées être localement lisses (et non globalement lisses), ce qui rend les méthodes classiques inapplicables ou inefficaces.
• Fonctions non lisses privées : Les termes $r_i$ sont convexes, non lisses et privés (ex: régularisation $\ell_1$, contraintes).
• Limites des méthodes existantes : Les algorithmes décentralisés actuels nécessitent souvent des connaissances globales (constantes de Lipschitz globales, propriétés spectrales du graphe) pour fixer un pas de descente conservateur. Cela conduit à un réglage manuel fastidieux, à des performances imprévisibles et à une convergence lente, surtout lorsque les fonctions ne sont que localement lisses.

2. Méthodologie

Les auteurs proposent une nouvelle classe d'algorithmes décentralisés adaptatifs, baptisés DATOS (Decentralized Adaptive Three-Operator Splitting), basés sur une reformulation du problème et une stratégie de pas adaptatif.

A. Reformulation et Fractionnement à Trois Opérateurs

Le problème est reformulé en introduisant des copies locales $x_i$ et des variables de relâchement $\tilde{x}_i$, permettant d'exprimer le problème sous une forme équivalente (P') adaptée au fractionnement Davis-Yin à trois opérateurs.

• L'approche utilise une métrique de préconditionnement BCV (Bertsekas–O'Connor–Vandenberghe) nouvelle, notée $M$.
• Cette métrique est cruciale car elle permet de décomposer le calcul de l'opérateur proximal global en calculs locaux, rendant l'algorithme entièrement décentralisé.

B. Sélection Adaptative du Pas (Backtracking)

Au lieu d'utiliser un pas fixe basé sur des bornes globales conservatrices, chaque agent ajuste son pas $\alpha_k$ localement via une procédure de recherche linéaire (backtracking) :

1. Critère de descente : Chaque agent vérifie une condition de descente inexacte sur sa fonction de perte locale $f_i$.
2. Coordination : Pour garantir la convergence globale, les agents doivent synchroniser leurs pas. Deux protocoles sont proposés :
   • Consensus Min Global (Algorithme 2.1) : Tous les agents convergent vers le pas minimum calculé par n'importe quel agent du réseau ($\alpha_k = \min_i \alpha_k^i$). Cela peut être implémenté via des protocoles de consensus sur des réseaux sans fil modernes (ex: combinaison WiFi/LoRa).
   • Consensus Min Local (Algorithme 4.1) : Les agents ne communiquent qu'avec leurs voisins immédiats pour mettre à jour leur pas. Sous certaines conditions, les pas locaux s'alignent asymptotiquement sur le pas global minimal.

C. Analyse de Convergence

Les auteurs établissent des garanties théoriques rigoureuses basées sur une fonction de Lyapunov adaptée :

• Convexité simple : Convergence sous-linéaire avec un taux de $O(1/k)$ pour l'écart d'optimalité.
• Convexité forte et lissage partiel : Si les fonctions $f_i$ sont fortement convexes localement et que les termes non lisses $r_i$ possèdent une propriété de lissage partiel (partly smooth) par rapport à une variété $C^2$, l'algorithme atteint une convergence linéaire.
• Identification de variété : L'algorithme identifie la variété active contenant la solution optimale en un nombre fini d'itérations, puis accélère vers la solution avec un taux linéaire.

3. Contributions Clés

1. Première méthode décentralisée sans paramètre pour les problèmes composites : C'est la première méthode qui résout le problème (P) avec des fonctions $f_i$ uniquement localement lisses et des termes $r_i$ non lisses, sans nécessiter de connaissances globales du réseau ou des constantes d'optimisation.
2. Conception algorithmique innovante :
   • Utilisation d'une métrique BCV spécifique pour permettre une implémentation décentralisée du fractionnement à trois opérateurs.
   • Intégration de procédures de backtracking locales couplées à des protocoles de consensus min (global ou local).
3. Garanties de convergence étendues :
   • Preuve de convergence sous-linéaire sous simple convexité.
   • Preuve de convergence linéaire sous convexité forte et lissage partiel, avec une complexité itérative explicite.
4. Variantes adaptatives : Développement d'une version à consensus global et d'une version à consensus local, offrant une flexibilité selon les contraintes de communication du réseau.

4. Résultats Numériques

Les expériences comparent les algorithmes proposés (Global DATOS et Local DATOS) avec des méthodes de référence non adaptatives (SONATA, PG-EXTRA) et une méthode adaptative centralisée adaptée (adaPDM).

• Scénarios testés :
  • Régression logistique avec régularisation $\ell_1$.
  • Estimation de la matrice de covariance (problème où $f$ est seulement localement lisse).
  • Régression linéaire avec régularisation Elastic Net (convexité forte).
• Performances :
  • Les algorithmes DATOS surpassent systématiquement les méthodes non adaptatives, qui nécessitent un réglage manuel fastidieux et souffrent de pas trop conservateurs.
  • Ils surpassent également les variantes de adaPDM, qui restent sensibles aux paramètres de réglage et nécessitent des informations globales ($\|I-W\|$).
  • La différence de performance entre le consensus global et local est négligeable, même sur des graphes peu connectés.
  • Les résultats confirment la convergence linéaire observée dans les expériences sur les problèmes fortement convexes.

5. Signification et Impact

Ce travail comble un vide important dans la littérature sur l'optimisation décentralisée :

• Robustesse : Il élimine le besoin de connaître les constantes de Lipschitz globales ou les propriétés spectrales du graphe, rendant les algorithmes applicables dans des environnements réels où ces informations sont inaccessibles.
• Efficacité : L'adaptation du pas permet d'utiliser des pas plus grands lorsque la géométrie locale le permet, accélérant la convergence par rapport aux méthodes à pas fixe.
• Généralité : La capacité à gérer des fonctions localement lisses et des termes non lisses composites élargit considérablement le champ d'application des méthodes décentralisées aux problèmes de traitement du signal, d'apprentissage automatique et de contrôle distribués complexes.

En résumé, cet article propose une avancée théorique et pratique majeure en rendant l'optimisation composite décentralisée adaptative, sans paramètre et robuste, tout en garantissant des taux de convergence optimaux.