Accelerated Minimax Algorithms Flock Together

Abstract

Several new accelerated methods in minimax optimization and fixed-point iterations have recently been discovered, and, interestingly, they rely on a mechanism distinct from Nesterov's momentum-based acceleration. In this work, we show that these accelerated algorithms exhibit what we call the merging path (MP) property; the trajectories of these algorithms merge quickly. Using this novel MP property, we establish point convergence of existing accelerated minimax algorithms and derive new state-of-the-art algorithms for the strongly-convex-strongly-concave setup and for the prox-grad setup.

arXiv commentPublished in SIAM Journal on Optimization

References in corpus (5)

• Projected Reflected Gradient Methods for Monotone Variational Inequalities
• Optimized first-order methods for smooth convex minimization
• Shadow Douglas--Rachford Splitting for Monotone Inclusions
• On Lower Iteration Complexity Bounds for the Saddle Point Problems
• Training GANs with Centripetal Acceleration