HyperAIHyperAI

Command Palette

Search for a command to run...

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

Jaewook Lee Hanseul Cho Chulhee Yun

Résumé

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.


Créer de l'IA avec l'IA

De l'idée au lancement — accélérez votre développement IA avec le co-codage IA gratuit, un environnement prêt à l'emploi et le meilleur prix pour les GPU.

Codage assisté par IA
GPU prêts à l’emploi
Tarifs les plus avantageux

HyperAI Newsletters

Abonnez-vous à nos dernières mises à jour
Nous vous enverrons les dernières mises à jour de la semaine dans votre boîte de réception à neuf heures chaque lundi matin
Propulsé par MailChimp