Negative Momentum for Convex-Concave Optimization
For researchers in min-max optimization, this work establishes negative momentum as a viable and competitive method, resolving key theoretical gaps and showing it can achieve faster and more general convergence than previously known.
This paper shows that negative momentum enables global convergence for convex-concave min-max optimization and accelerated convergence for strongly-convex-strong-concave optimization, resolving two open questions. The results demonstrate that negative momentum achieves convergence rates comparable to or better than existing algorithms.
This paper revisits momentum in the context of min-max optimization. Momentum is a celebrated mechanism for accelerating gradient dynamics in settings like convex minimization, but its direct use in min-max optimization makes gradient dynamics diverge. Surprisingly, Gidel et al. 2019 showed that negative momentum can help fix convergence. However, despite these promising initial results and progress since, the power of momentum remains unclear for min-max optimization in two key ways. (1) Generality: is global convergence possible for the foundational setting of convex-concave optimization? This is the direct analog of convex minimization and is a standard testing ground for min-max algorithms. (2) Fast convergence: is accelerated convergence possible for strongly-convex-strong-concave optimization (the only non-linear setting where global convergence is known)? Recent work has even argued that this is impossible. We answer both these questions in the affirmative. Together, these results put negative momentum on more equal footing with competitor algorithms, and show that negative momentum enables convergence significantly faster and more generally than was known possible.