Reproduce “Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile” on OpenResearch

About this paper

Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, Georgios Piliouras

The authors analyze optimistic mirror descent (OMD), which uses a gradient at a temporary look-ahead point to correct updates. They prove last-iterate convergence with exact gradients on coherent problems under Lipschitz and step-size conditions, and almost-sure convergence with stochastic feedback under strict coherence. In GAN experiments, extra-gradient training improves CIFAR-10 metrics after warm-up, but does not establish universal convergence.

Key insights

• The "coherence" property of a saddle-point problem is a critical factor determining the convergence behavior of first-order methods; vanilla Mirror Descent converges in strictly coherent problems but fails in null-coherent ones.
• Incorporating an "optimistic" extra-gradient step into Mirror Descent is crucial for stabilizing the algorithm, enabling monotonic convergence with exact gradients and almost sure convergence with stochastic gradients in coherent problems.
• The optimistic approach generalizes prior findings for optimistic gradient descent in bilinear problems, providing a robust mechanism to mitigate cycling and divergence in a broader class of non-linear and non-monotone saddle-point problems.

Summary by alphaXiv.