Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper studies  the local asymptotic stability of a specific class of solutions points, referred to as strict local minmax equilibria (or differential Stackelberg equilibria), in the case of Gradient Descent-Ascent Dynamics with a finite time-scale separation. The time-scale separation (\tau) is being captured by the ratio of the step-sizes between the min and max agents respectively. Recently, Jin et al. showed the set of asymptotically stable critical points of gradient descent-ascent coincide with the set of differential Stackelberg equilibrium as the time separation goes to infinity. The paper shows that an infinitely large separation is not needed and some finite but large enough separation suffices.  The paper provides a close analogue of another previous result by Mescheder about local stability of gradient descent dynamics in GANs under strong technical assumptions. The paper ends with GAN experiments where \tau=1, 2, 4, 8 are tested and the performance seems to peak at 4. 

The paper performs a detailed theoretical analysis of the coupling between GDA and diff Stackelberg equilibria. Although this is positive, the results are not particularly surprising given the prior work. The writing of the paper could also be significantly improved.

One issue that I had reading the paper is that at times and especially in the introduction the 
treatment of (asymptotically stable), stable, unstable fixed points seem to be a little ambiguous.The paper only formally defines locally exponentially stable equilibrium in the preliminaries which is a notion that is not used in the introduction. I think it is important to set early on a clear terminology that is consistent throughout the whole paper. 
I am also a bit confused about some statements in the paper about which type of solution concepts are game theoretically meaningful. The paper seems to state that any critical point that does not satisfy the definitions of differential Stackelberg equilibria lack game theoretic meaning.  From the paper

the stable critical points of gradient descent-ascent coincide with the set of differential Stackelberg equilibrium as \tau goes to infinity. All ‘bad critical points’ (critical points lacking game-theoretic meaning) become unstable and all ‘good critical points’ (game-theoretically meaningful equilibria) remain or become stable as \tau goes to infinity.

This seems like a strong statement. It seems to me that min-max solutions of bilinear zero-sum games does not satisfy the differential Stackelberg definition. Such statements would imply that min-max solutions are 1) bad critical points and 2) lack game theoretic meaning despite being the golden standard of a solution concept in game theory. 
Maybe I am missing something here? 

[1] has recently shown that alternating GDA with fixed time-separation does not converge in the case of bilinear zero-sum games but is instead recurrent with the min-max equilibrium being stable but not asymptotically stable. This seems to be exactly the setting that you are studying. How are the results of [1] connected to yours? I think that due to the tight match between the two settings a thorough discussion is needed. 

The definitions of differential/strict Nash/Stackelberg equilibria are two of several alternative definition/solution concepts that have only been recently introduced in the context of non-convex non-concave games. The paper should compare and contrast to other notions ideas  (e.g. proximal equilibria are only mentioned briefly [2], see also [3], [4]).

 Although one should of course not expect a global convergence as such a result would be too ambitious, the title could be interpreted as such a result by non-specialists. I think it might be better if the term local analysis is used instead. A more thorough discussion about non-convergence results for GDA and variants in zero-sum games could be also helpful [1,3,5-8] to dispel any possible confusion.

In terms of the experimental results why do the simulations stop with \tau=8? The theoretical results as well as the prior work by Jin et. al are supportive of arbitrary large \tau. What happens e.g. for tau= 2^4, 2^8, .... It already seems that performance starts dropping for \tau>4. Does this trend continue? Does the performance have a unique peak? or does it fluctuate?
The regularization results (Theorem 3) remain true even for \tau<<1 e.g. \tau = 2^{-4}, 2^{-8}, ... 
What would experiments show for such \tau under regularization?


[1] Bailey et al. Finite Regret and Cycles with Fixed Step-Sizevia Alternating Gradient Descent-Ascent. COLT 2020
[2] Farnia et. al Do GANs always have Nash equilibria? ICML 2020
[3] Vlatakis-Gkaragkounis et al. Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games. NeurIPS 2019.
[4] Zhang, et al. Optimality and Stability in Non-Convex-NonConcave Min-Max Optimization. arXiv e-prints, art. arXiv:2002.11875, February 2020.
[5] Mertikopoulos et al. "Cycles in adversarial regularized learning." Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, 2018.
[6] Cheung et al. "Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games." arXiv preprint arXiv:1905.08396 (2019).
[7] Letcher "On the Impossibility of Global Convergence in Multi-Loss Optimization." arXiv preprint arXiv:2005.12649 (2020).
[8] Hsieh, et. al. "The limits of min-max optimization algorithms: convergence to spurious non-critical sets." arXiv preprint arXiv:2006.09065 (2020).
review_title: Local analysis of Gradient Descent-Ascent with a finite timescale separation

final_score: rating: 7: Good paper, accept
review_content: ## Summary
This paper studies the stable points of gradient descent ascent with different step-sizes. 
Roughly, this paper's main result is that for any fixed point for the GDA dynamics, that point is stable for GDA with a large enough timescale separation if and only if it is a local Stackelberg equilibrium.

This result is quite intuitive since a similar result has been proved by Jin et al. 2020. (the timescale had to go to infinity). Though, proving such a result for a *finite* timescale separation is a major improvement and is related to practical significant considerations. 

## Pros and cons
Strengths:
the work is well motivated, and overall the paper is well written. Though if I think some of the technical aspects could be improved. 
The results may interest the community.
The theoretical tools introduced could be used in other theoretical work. 

weaknesses:
Some of the theory sections could be more developed to build intuitions on the phenomenon going on. It seems really hard for me to follow the current proof sketches since many notations are not properly introduced (or at least any intuition about what they mean is proposed). (see my section on questions/ comments)
The experiments are not really related to the theory. (see my section about experiments)
I have some technical concerns and questions (I would be glad if the authors can answer them; see my section on questions)
The conclusion is overstating the results of the paper. 

## Overall review
Overall, this paper is a good paper that should be accepted if the authors fix some statements in the conclusion section and answer my questions about the theory. Also, the experimental section could be improved (not by running more large scale experiments but by more related to the theory presented)

## Questions and comments (by decreasing order of importance):

### technical question
The most important question I have regards the guardian map you use. In the proof sketch of Theorem 1 where you state that the map $\nu(\tau) := det(-(J_\tau \oplus J_\tau))$ is a guardian map of $\mathcal{S}(\mathbb{C_-^\circ})$ but if we look at lemma C.1 the result boils down to the fact that the eigenvalues of $A \oplus A$ are $(\lambda_i + \lambda_j)$ with $\lambda_i, \lambda_j \in Sp(A))$.
However, it means that if $A$ has a single eigenvalue in $\mathbb{C_-^\circ}$, then $\nu(A)$ is non zero. Some arguments should be added (since $A$ is a real matrix, the non-real eigenvalues are complex conjugates) to justify that the only problematic case is when $A$ has $0$ as an eigenvalue. One quick fix would be to consider $\nu(A) := det(A)det(-(A\oplus A))$ as guardian map$. But I do not know how it would change the derivations in the proof of claim C.1. 
I am quite novel with these notions, so my questions are: Am I missing something? If yes, what? If not, would the fix work, and will it change the results of Theorem 1 and 2?

### Conclusion 
In the conclusion section, you write, “We proves gradient descent-ascent converges to a critical point for a range of finite learning rate ratios if and only if the critical point is a differential Stackelberg equilibrium. This answers a standing open question about the convergence of first-order methods to local minimax equilibria.” These two sentences may be misleading for the following reasons:
- you only prove a *local* convergence result
- The local distinction is important because the method can still cycle outside of these neighborhoods. (see for instance [Letcher 2020])
- Also, the value of $\tau$ depends on the neighborhood. So it seems that you may have an infinite number of critical points, and the value of \tau to globally (max of the \tau for each critical point) only has local convergence to local minimax may be infinite. Do you agree with that statement? 

### Experiments
Your theory is about the nature of the stationary points found by the training dynamics  (are they theoretically meaningful), but you do not verify that training with different learning rates actually finds local minimax. Moreover, it is known that using different learning rates is necessary to get better empirical performances (see, for instance [Brock et al. 2019, Jolicoeur-Martineau et al. 2020] or most of the SOTA results on https://paperswithcode.com/paper/adversarial-score-matching-and-improved). I think that one experiment that would support your theory would be about looking at the eigenvalues of J_\tau around the “practical equilibria” for different values of $\tau$ and see if you only get local minimax for large enough $\tau$.
In Assumption 1, you suppose that $(w,\theta)$ is an equilibrium. But what kind of equilibrium? Nash? What do you need? That it is a stationary point of the dynamics?


### About guardian maps
Shouldn’t you add in the definition of a guardian map that the map is continuous?

### Related work
Your examples 1 and 2 look very similar to the ones proposed by Zhang et al. 2020 in section 5.2. Can you comment on that? (I guess there is a difference, but I think this is related work that should be addressed, particularly Section 5.2)

### Questions/comments on the appendix
I think there is a typo that should be fixed on page 22: you recall that $A \oplus B = A \otimes B + B \otimes A$, which is, I think, incorrect. (and it is the only place where I found a definition for $\oplus$)
On page 24, you mention more elegant constructions (what are these construction?). 
You also claim that you get the tightest bounds for $\tau$. Can you compare these bounds? Can you prove that you are tighter?
I do not understand the sentence "we use $A \boxplus A$ because of its computational advantages." Do you mean algebraic computations? Computational advantage usually refers to the algorithmic complexity to compute these quantities, but I guess this is not what you are talking about in the sentence. 

### Minor comments: 
Page 2 maybe define Schur complement
Page 3 The notations $vec$ is not introduced. 
Page 4 The Kronecker product and sum are not defined 
Proof of Lemma C.1 there is no n_1 and n_2 
 

Refs:

Brock, Andrew, Jeff Donahue, and Karen Simonyan. "Large scale gan training for high fidelity natural image synthesis." arXiv preprint arXiv:1809.11096 (2018).

Zhang, Guojun, Pascal Poupart, and Yaoliang Yu. "Optimality and Stability in Non-Convex-Non-Concave Min-Max Optimization." arXiv preprint arXiv:2002.11875 (2020).


Letcher, Alistair. "On the Impossibility of Global Convergence in Multi-Loss Optimization." arXiv preprint arXiv:2005.12649 (2020).

Jolicoeur-Martineau, Alexia, et al. "Adversarial score matching and improved sampling for image generation." arXiv preprint arXiv:2009.05475 (2020).
review_title: An very interesting theoretical result that could be backed-up with experiments

final_score: rating: 6: Marginally above acceptance threshold
review_content: The main result of the paper states that a strict local minmax point is a stable critical point of t-GDA for some large enough t, and that any non-strict local minmax can be made unstable by s-GDA if we choose s large enough.


-Major issues

My greatest concern is that the first part of the main result, that a strict local minmax is stable for t-GDA with all large, but finite t, is already known (Jin et al. 2020). Specifically, the proof of Lemma 40 in (Jin et al. 2020) shows that for all large enough finite t, the Jacobian of t-GDA only has eigenvalues whose real part is smaller than 0, which then implies the stability of t-GDA for a finite t. 

From what I can see, the reason why Jin et al. 2020 stated their results in terms of infinite timescale separation is because they did not have a uniform bound on how large the timescale t should be, and therefore in general it can be made as large as possible (but finite). The proof in the current submission has exactly the same feature: for every game, there is a finite t that makes t-GDA stable, but in general this t can be made arbitrarily large. It seems to me that the authors have not qualitatively improved over (Jin et al. 2020) (although I believe the bounds in this paper are tighter).

In the same vein, the converse statement also more or less appeared in (Jin et al. 2020); see the proof of Theorem 28, p.24-25 therein.

Due to the above, I cannot see the claimed novelty of providing the first finite timescale separation for GDA, hence my rating. I'm willing to change my score should the authors convince me that I have misunderstand something.


-Minor issues
1. The authors claimed that "On the empirical side, it has been widely demonstrated that timescale separation in gradient descent-ascent is crucial to improving the solution quality when training generative adversarial networks." I believe this is an overstatement of what we currently know about GANs; see 

https://arxiv.org/pdf/1711.10337.pdf

for a comprehensive empirical study of the effects on the timescale for GDA, which is not as conclusive as the authors stated. I would therefore suggest to tone down the sentence.

2. Appendix B.3 is quite weird. F(x_k) here should be a vector-valued mapping but the authors seem to view it as a function. Also, by F(k) = O(M^k), did the authors mean ||x_{k+1} − x*|| = O(M^k)?


----

Post-revision evaluation:

The authors have modified the statements of the main theorems as well as including a more detailed comparison to previous works, which clarifies my concern. I have thus increased my score. 

The technical contributions bring new insight into the studying of scale separation of GDA, and enables a tight characterization of many toy examples. I believe these are solid contributions and should be valued.

On the down side, I'd like to point out that the "practical implication" in this paper is a bit of stretch since the ImageNet experiments are run with RMSprop, whereas the analysis of this paper is highly specialized to GDA. 

Of course, studying adaptive algorithms in min-max games is exceedingly hard and well beyond the scope of this paper. What I recommend the authors is then:

1. Explicitly notify the readers of the difference between RMSprop and GDA.

2. Find a nontrivial but simple example where 1-GDA provides an okay baseline (say 7-layer CNNs for mixture of Gaussians or MNIST). Increase the time scale to show if it exhibits a similar behavior that a small $\tau$ gives the best result. This is directly verifying what the theory is saying, and hence feels more valuable to me.


review_title: Part of the main result might already be known (concern clarified by revision)

final_score: rating: 6: Marginally above acceptance threshold
review_content: Motivated by the many applications of min-max optimization problems in Machine Learning, the authors examine the effect of using different learning rates for each player in Gradient Descent Ascent (GDA) for non-convex non-concave optimization problems. Prior work has already established that making the learning rate of one player infinitely larger than other player's learning rate alleviates the cycling problems of GDA and makes game-theoretically meaningful equilibria the only asymptotically stable fixed points. The main contribution of this work is that it proves that we can get the same stability guarantees while keeping the learning rates of both players finite. This is crucial for practical applications where using unbounded learning rates in not an option. The authors employ this result to prove a variety of local convergence results in both deterministic ans stochastic settings.

Pros:
1) The finite time scale separation is necessary in order to make the theoretical intuitions in prior work applicable for practical problems like trainings GANs. 
2) The proof techniques used for this separation results are, to the best of my knowledge, significantly different and elaborate than the ones used in prior work (Jin et al., 2020).
3) The theoretical findings are complemented with empirical evaluations both on small min-max problems and on complex ones like training GAN architectures. 

Cons:
Theorem 28 in the arxiv version of Jin et al. 2020 does not explicitly reference the existence of a finite time scale that satisfies their inclusion results. However,  it is clear from the proof of Theorem 28 on page 24 that such a finite time-scale separation exists even though they do not provide an explicit formula for it.  At least for one of the inclusion statements they explicitly mention that it holds for $\epsilon < \epsilon_0$  for some $\epsilon_0$ where $\epsilon$ corresponds to $1/\tau$.

Of course the result of the authors gives a more direct construction of the threshold $\tau^*$ by reducing the search for it to an eignenvalue problem. From a practical standpoint though, both results are existential. Neither proof approach gives particular intuition on how this time scale can be found in a computationally efficient way.  The added value of leveraging an array of mathematical tools to provide this explicit construction is unclear to me. 

Given the above concern and that the convergence results essentially leverage the asymptotic stability properties provided by Theorems 1 and 2,  I am assigning a weak reject score. However, I am willing to substantially increase my score if the authors address the above concern. 
review_title: Finite Timescale Separation for Gradient Descent Ascent

Meta-review: This paper treats the problem of running gradient descent-ascent (GDA) in min-max games with a different step-size for the two players. Earlier work by Jin et al. has shown that, when the ratio of the step-sizes is large enough, the stable fixed points of GDA coincide with the game's strict local min-max equilibria. The main contribution of this paper is an explicit characterization of a threshold value $\tau^*$ of this ratio as the maximum eigenvalue of a specific matrix that involves the second derivatives of the game's min-max objective at each (strict local) equilibrium.

This paper generated a fairly intense discussion, and the reviewers showed extraordinary diligence in assessing the authors' work. Specifically, the reviewers raised a fair number of concerns concerning the initial write-up of the paper, but these concerns were mostly addressed by the authors in their revision and replies. As a result, all reviewers are now in favor of acceptance.

After my own reading of both versions of the paper and the corresponding discussion, I concur with the reviewers' view and I am recommending acceptance subject to the following revisions for the final version of the paper:
1. Follow the explicit recommendations of AnonReviewer3 regarding the numerical simulations (or, failing that, remove them altogether). [The authors' phrase that "The theory we provide also does not strictly apply to using RMSprop" does not suffice in this regard]
2. Avoid vague statements like $\tau \to \infty$ in the introduction regarding the work of Jin et al. and state precisely their contributions in this context. In the current version of the paper, a version of this is done in page 4, but the introduction is painting a different picture, so this discussion should be transferred there.
3. A persisting concern is that the authors' characterization of $\tau^*$ cannot inform a practical choice of step-size scaling (because the value of $\tau^*$ derived by the authors depends on quantities that cannot be known to the optimizer). Neither the reviewers nor myself were particularly convinced by the authors' reply on this point. However, this can also be seen as an "equilibrium refinement" result, i.e., for a given value of $\tau$ only certain equilibria can be stable. I believe this can be of interest to the community, even though the authors' characterization cannot directly inform the choice of $\gamma_1$ and $\gamma_2$ (or their ratio).

Modulo the above remarks (which the authors should incorporate in their paper), I am recommending acceptance.
Decision: Accept (Poster)