Grundlegender Nutzen alternierender Aktualisierungen in der Minimax-Optimierung

Der Gradientenabstiegs-Aszents-Algorithmus (Gradient Descent-Ascent, GDA), der zur Lösung von Minimax-Optimierungsproblemen entwickelt wurde, führt die Abstiegs- und Anstiegs-Schritte entweder gleichzeitig (Sim-GDA) oder abwechselnd (Alt-GDA) durch. Während Alt-GDA häufig eine schnellere Konvergenz zeigt, ist die theoretische Erklärung der Leistungsunterschiede zwischen beiden Verfahren, insbesondere hinsichtlich der globalen Konvergenzraten, bisher noch nicht hinreichend verstanden. Um diese Theorie-Praxis-Lücke zu schließen, präsentieren wir eine detaillierte Konvergenzanalyse beider Algorithmen für stark-konvex-stark-konkave sowie Lipschitz-stetig-gradientenobjektive. Unsere neue obere Schranke für die Iterationskomplexität von Alt-GDA ist strikt kleiner als die untere Schranke von Sim-GDA; das heißt, Alt-GDA ist beweisbar schneller. Darüber hinaus schlagen wir einen allgemeinen algorithmischen Rahmen namens Alternating-Extrapolation GDA (Alex-GDA) vor, der Sim-GDA und Alt-GDA umfasst. Der zentrale Gedanke von Alex-GDA besteht darin, abwechselnd Gradienten aus Extrapolationen der Iterierten zu berechnen. Wir zeigen, dass Alex-GDA eine kleinere Iterationskomplexität aufweist, die mit der des Extra-Gradient-Verfahrens übereinstimmt, gleichzeitig aber weniger Gradientenberechnungen erfordert. Zudem beweisen wir, dass Alex-GDA für bilineare Probleme eine lineare Konvergenz zeigt, während sowohl Sim-GDA als auch Alt-GDA in diesen Fällen gar nicht konvergieren.