Min-max formulations have attracted great attention in the ML community due to the rise of deep generative models and adversarial methods, while understanding the dynamics of gradient algorithms for solving such formulations has remained a grand challenge. As a first step, we restrict to bilinear zero-sum games and give a systematic analysis of popular gradient updates, for both simultaneous and alternating versions. We provide exact conditions for their convergence and find the optimal parameter setup and convergence rates. In particular, our results offer formal evidence that alternating updates converge "better" than simultaneous ones.
*Summary*
This paper studies the convergence of multiple methods (Gradient, extragradient, optimistic and momentum) on a bilinear minmax game. More precisely, this paper uses spectral condition to study the difference between simultaneous (Jacobi) and alternating (Gau\ss-Seidel) updates. The analysis is based on Schur theorem and give necessary and sufficient condition for convergence. 
 
*Decision*
This paper tries to study a phenomenon that has known a recent surge of interest due to the numerous practical minmax application: the impact of alternating updates in minmax optimization. This problem is challenging because most of the theoretical analysis techniques have been developed to analyse simultaneous updates. 
I think that this paper has treated well the related work and underlines well its contributions. 
Even if the main contribution are theoretical the authors of this paper provide some experiments to confirm that the theory provides some meaningful insights.
However, I have the concern that the study is still limited to bilinear example and thus it is not clear how to apply it to non-bilinear objective (even locally because since the Jacobian has pure imaginary eigenvalues, even locally the Jacobian may have eigenvalues with negative real part).
Moreover this work do not provides significantly better (factor 8 improvement in the constants) convergence rate that the one provided on the literature (Tseng 1995, Mokthari et al 2019, Gidel et al. 2019) to solve bilinear games. The contributions is more about proving new (interesting) analysis tools and showing a better robustness of GS updates with respect to hyperparameter tunning. 
To me, it is an accept.
*Questions*
- In Theorem 4.1 and 4.2 you use the word ‘optimal exponent’. In what sense these algorithms are optimal ? Usually the sense of optimal is when you achieve the lower bound of convergence. Is it the case here ?
- Right after theorem 2.3 you claim that GS updates simply leads to a shift of index for $L_i$ setting $L_{k+1}=0$ but it seems to me that then $\lambda L_1$ is missing in the sum. Is it just an unfortunate oversight? Does it affect the proofs of you main theorems ? These results only marginally (improve by a factor 8) improve upon Moktari et al. (2019).
 
*Remarks*
- To me the J and GS conditions in Theorem 3.2, 3.3 and 3.4 are more Lemmas than Theorems: They are condition that are hard to interpret and they have small interest if one cannot conclude on simple conditions (such as the ones you actually provide in the Theorem). My point is that providing such complicated conditions without condition is only half solve the problem of convergence.  In that sense, in the discussion of Theorem 3.4, you are a bit unfair with Gidel et al (2019) since unlike them you do not provide any convergence rate. On one side theorem 3.4 gives an interesting characterization for the convergence (that leads to the fact that at least one of the beat has to be negative) but if it does not lead to any rate it is a less interesting result. 
- In Table 1 and 2, $\alpha,\beta_1$ and $\beta_2$ have not been introduced. It is thus hard to get the most of them.
- Theorem 3.1 has been stated in previous works (like for instance Gidel et al 2019). You should not claim it as a contribution.
=== After rebuttal === 
I've read the authors's response.
I agree with the concerns raised by Reviewer 2 regarding the experimental part and whether or not such theoretical study (far from the practical aspect) are of interest to the ICLR community.
I think that that paper would be more suited for a theoretical venue such as AISTATS (or ICML) but I also think that this work remains of interest to the ICLR community.  
I am not convinced by the fact that this analysis could be generalized beyond bilinear game with a local analysis  because even an arbitrarily small perturbation can transform a bilinear example into a non-stable equilibrium (with no hope of local convergence), take for instance 
$$ \min_x \max_y -\epsilon \|x\|^2 +  x^\top A y + \epsilon \|y\|^2$$