HyperAIHyperAI

Command Palette

Search for a command to run...

Grundlegender Nutzen alternierender Aktualisierungen in der Minimax-Optimierung

Jaewook Lee Hanseul Cho Chulhee Yun

Zusammenfassung

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.


KI mit KI entwickeln

Von der Idee bis zum Launch – beschleunigen Sie Ihre KI-Entwicklung mit kostenlosem KI-Co-Coding, sofort einsatzbereiter Umgebung und bestem GPU-Preis.

KI-gestütztes kollaboratives Programmieren
Sofort einsatzbereite GPUs
Die besten Preise

HyperAI Newsletters

Abonnieren Sie unsere neuesten Updates
Wir werden die neuesten Updates der Woche in Ihren Posteingang liefern um neun Uhr jeden Montagmorgen
Unterstützt von MailChimp
Grundlegender Nutzen alternierender Aktualisierungen in der Minimax-Optimierung | Paper | HyperAI