Avantage fondamental de la mise à jour alternée dans l'optimisation minimax

L'algorithme Gradient Descent-Ascent (GDA), conçu pour résoudre des problèmes d'optimisation minimax, effectue les pas de descente et d'ascension soit simultanément (Sim-GDA), soit de manière alternée (Alt-GDA). Bien que Alt-GDA soit généralement observé pour converger plus rapidement, l'écart de performance entre les deux algorithmes n'est pas encore pleinement compris du point de vue théorique, en particulier en ce qui concerne les taux de convergence globale. Pour combler cet écart entre théorie et pratique, nous proposons des analyses de convergence à haute résolution pour les deux algorithmes dans le cas d'objectifs fortement convexes-fortement concaves et à gradient lipschitzien. Notre nouvelle borne supérieure sur la complexité itérative d'Alt-GDA est strictement inférieure à la borne inférieure de Sim-GDA ; autrement dit, Alt-GDA est prouvée plus rapide. En outre, nous introduisons Alex-GDA, un cadre algorithmique général qui englobe à la fois Sim-GDA et Alt-GDA, dont l'idée principale consiste à prendre alternativement des gradients à partir d'extrapolations des itérés. Nous montrons que Alex-GDA satisfait une borne de complexité itérative plus faible, identique à celle de la méthode Extrapolée (Extra-gradient), tout en nécessitant moins d'évaluations de gradients. Nous démontrons également que Alex-GDA converge linéairement pour les problèmes bilinéaires, où ni Sim-GDA ni Alt-GDA ne convergent du tout.