MA${}^4$EG: Moving-Anchor Adaptive-Adaptive Accelerated Extra Gradient Method

We propose the moving-anchor adaptive-adaptive accelerated extragradient method (MA${}^4$EG) for smooth convex-concave minimax problems, which combines extragradient updates with a moving anchor to achieve accelerated convergence while adapting to both the smoothness constant and the strong convexity-concavity parameter. MA${}^4$EG uses no line search and no restarts, and its step size and anchor coefficient are adaptively updated. For a smooth convex-concave objective function, MA${}^4$EG achieves an accelerated $\mathcal{O}(1/k^2)$ last-iterate convergence rate, similar to the extra anchored gradient (EAG) method. When the objective function is additionally $\mu$-strongly convex-concave, MA${}^4$EG has a linear last-iterate convergence rate. Numerical experiments in several diverse settings show that MA${}^4$EG matches or beats prior methods, and significantly outperforms the baselines when the local smoothness constant and strong convexity-concavity parameter are more favorable than their global counterparts.