In this section, we summarize the convergence rates of different algorithms as well as the assumptions needed. First, we start with the Mirror-Prox algorithm. [1]} provided the convergence guarantee of Mirror-Prox on in terms of the duality gap, and the rate is \(O(1/T)\)  where \(T\)  is the iteration number. As one of the most important algorithms for convex-concave optimization, [2]} introduced its stochastic version where only the stochastic first order oracle can be accessed, and also provided its convergence rate. When combined with [3]}, we can conclude that the convergence rates for both deterministic and stochastic mirror-prox algorithm are optimal. When it comes to the more challenging non-convex non-concave min-max optimization, the two methods above are still useful. [4]} showed that the deterministic extragradient method can converge to \(\varepsilon \) -first order stationary point with non-asymptotic guarantee. Another interesting algorithm Inexact Proximal Point (IPP) method [5]}, which is a stage-wise algorithm performs well under the condition that the objective function is weakly-convex weakly-concave. In each stage, we construct a strongly-convex strongly-concave sub-problem by adding quadratic regularizers. Then, by using stochastic algorithms, we can approximately solve the original problem. It's known that IPP also has a convergence guarantee to first order stationary points. Also, [6]} proposed an alternating deterministic optimization algorithm, where multiple steps of gradient ascents are conducted before one gradient descent step. Therefore, we can approximately make sure that the max step always reaches near optimal. However, in order to guarantee its convergence to first order stationary point, we have to assume that the inner maximization problem satisfies PL condition [7]}. For the details of convergence rate, we summarize them into Table REF . Now we explain some terms in the table.
<TABLE>