English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the iteration complexity of the optimistic gradient descent-ascent(OGDA) method and the extra-gradient (EG) method for finding a saddle point ofa convex-concave unconstrained min-max problem. To do so, we first show thatboth OGDA and EG can be interpreted as approximate variants of the proximalpoint method. This is similar to the approach taken in [Nemirovski, 2004] whichanalyzes EG as an approximation of the `conceptual mirror prox'. In this paper,we highlight how gradients used in OGDA and EG try to approximate the gradientof the Proximal Point method. We then exploit this interpretation to show thatboth algorithms produce iterates that remain within a bounded set. We furthershow that the primal dual gap of the averaged iterates generated by both ofthese algorithms converge with a rate of $\mathcal{O}(1/k)$. Our theoreticalanalysis is of interest as it provides a the first convergence rate estimatefor OGDA in the general convex-concave setting. Moreover, it provides a simpleconvergence analysis for the EG algorithm in terms of function value withoutusing compactness assumption.

Convergence Rate of $\mathcal{O}(1/k)$ for Optimistic Gradient and Extra-gradient Methods in Smooth Convex-Concave Saddle Point Problems