Convex-Concave Minmax Optimization: Applications and Methods

In this seminar, I first introduced the smooth convex-concave saddle point problem and its intuitions. To solve such problem, I intuitively showed an algorithm called gradient descent-ascent (GDA) that theoretically feasible but practically diverged, and further showing its converged variant, proximal point algorithm (PPA). Given the intractability of PPA’s future step gradient $\nabla f(x_{k+1},y_{k+1})$, I provided the optimistic gradient descent-ascent algorithm (OGDA) and the extragradient (EG) algorithm, and highlighted how gradients used in OGDA and EG approximate the gradient of the PPA. Then, I exploit this interpretation to show that the primal-dual gap of the averaged iterates generated by both algorithms converge with a rate of $O(1/k)$. Ultimately, I analyzed the last iterate convergence properties of both algorithms, and showed that the last iterate of both algorithms converge at a rate of $O(1/\sqrt{k})$, which is slower than the averaged iterate in smooth convex-concave saddle point problem.

Seminar slides: [slides].
Seminar notes: [notebook].
Seminar codes: [codes].

Reference Reading Materials:

1. Golowich, Noah, et al. “Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems.” Conference on Learning Theory. PMLR, 2020.[pdf].

2. Mokhtari, Aryan, Asuman E. Ozdaglar, and Sarath Pattathil. “Convergence Rate of $O(1/k)$ for Optimistic Gradient and Extragradient Methods in Smooth Convex-Concave Saddle Point Problems.” SIAM Journal on Optimization 30.4 (2020): 3230-3251.[pdf].