Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:
While single-agent optimization is quite well understood and even convergence results in the nonconvex setting, the study of non-convex-concave saddle point problems is still in its infancy. In particular, recent work by Letcher (2020) and Hsieh et al (2020) suggests that even many recently proposed modifications of simultaneous gradient descent are not guaranteed to converge in the non-convex-concave case.
The present work makes significant progress on this problem by introducing hidden convex-concavity, a class of structured problems nonlinear functions $F(\theta)$ and $G(\phi)$ that depend on only one of the agents $\theta$ and $\phi$, are plugged into a convex-concave problem $L(\cdot, \cdot)$, resulting in $\min_{\theta} \max_{\phi} L(F(\theta), G(\phi))$.
Here, the components $F_i$ and $G_j$ of $F$ and $G$ are multivariate, real-valued functions $f_i$, $g_i$ of disjoint sets of components of $\theta$ and $\phi$.
By cleverly relating the dynamics of the $f_i$,$g_i$ to those of the $\theta_j$, $\phi_j$, the authors derive a Lyapunov function for the underlying dynamics and use it to prove asymptotic stability and convergence under very minor additional assumptions.
They furthermore show a notion of "hidden convergence" of the $f_i$, $g_i$ that is particularly relevant to the overparametrized regime. 
In the last section, the authors relate their findings to GANs.

Decision:
I believe that this is good work that will be interesting to a wide range of readers. My only concern is the following:

In the definition of hidden convex-concavity, the functions $f_i, g_j$ are multivariate and real valued, but depend on **disjoint** sets of parameters. In particular, it does not seem to cover the case of  $L(f(\phi), g(\theta))$ where $f$ and $g$ are multivariate vector valued functions. 
However, this is arguably the case in GANs, where the discriminator and generator can be thought of high/infinite-dimensional "vectors" that depend nonlinearly on all parameters. 
Therefore, the results of the authors do not seem to apply to GANs even formally? Please let me know if there is something that I overlooked.

I believe that the results are interesting and relevant even if they would not apply to GANs. However, in this case the application section and motivation of the paper might need some restructuring.

Other suggestions/questions to authors
- I would suggest citing https://arxiv.org/abs/2005.12649 and https://arxiv.org/abs/2006.09065 as they provide additional motivation for the necessity to consider more structured classes of nonconvex games. 
- A popular extension beyond convexity is pseudo-monotonicity (see for instance https://arxiv.org/abs/1807.02629). How does strict hidden convexity relate to strict pseudo-monotonicity? Does the former imply the latter? Are there counterexamples?
- Do the authors expect that methods that converge in the bilinear case such as extragradient, symplectic gradient adjustment, or competitive gradient descent can be guaranteed to converge even for weak hidden convexity?

minor comments: 
- Statement of Lemma 1: I think the statement would be more clear if \Sigma_1 and \Sigma_2 were defined before the conclusion.
- Theorem 2: "is a safe" -> "is safe" 
- "Hidden convex-concave games & Regularizaiton" -> "...Regularization"

=============================================================================================================
After author discussion: After discussion with the authors, I am now convinced that any applicability of the theory proposed in this work to GANs is fundamentally tied to univariate latent space or generator output since the "hidden convexity assumption" does not allow for a multivariate set of latent variables to be combined to a multivariate set of outputs.
I still find the theoretical findings and method interesting, but I think that the work requires substantial refocusing and the identification of more examples of "hidden strong convexity" before being published at a top-tier conference. I therefore change my rating from 7 to 5 and recommend rejection, for now.
review_title: Interesting progress beyond convex concave games. Application to GANs questionable?

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies min-max problems of the form L(F(x),G(y)), where L is a strictly convex-concave loss. The authors prove that, under certain assumptions, the GDA dynamics converges to von Neumann solutions. Toy examples are provided to illustrate the usage of the framework.

I see this paper as a rather incremental extension of the work (Vlatakis-Gkaragkounis et al. 2019). Specifically, Lemma 1 appeared in (Lemma 1, Vlatakis-Gkaragkounis et al. 2019), Theorem 1 appeared in (Lemma 2, Vlatakis-Gkaragkounis et al. 2019), Definition 3 makes a strong assumption that basically gets rid of the challenges of non-convexity, and Lemma 2 appeared in (Theorem 2, Vlatakis-Gkaragkounis et al. 2019).

The key difference between this work and (Vlatakis-Gkaragkounis et al. 2019) is the strict convex-concave losses (present work) vs. bilinear losses (Vlatakis-Gkaragkounis et al. 2019). Due to this difference, the function (4) in Lemma 2 is time-invariant (or acts as a Hamiltonian) in (Vlatakis-Gkaragkounis et al. 2019), whereas in this submission it is non-increasing in the presence of strict convexity, and hence enabling Lyapunov-type analysis. This is an almost immediate conclusion one can draw from studying (Vlatakis-Gkaragkounis et al. 2019), and hence the contribution does not seem to meet the standard of top ML venues.

In addition, the authors studied unconstrained min-max problems with hidden structures, while in Section 4 they claimed that GANs can be viewed as **constrained** min-max problems. I would like to point out that the presence of constraints is a significant difference as it would completely invalidate all the analysis in this paper. The toy example of WGAN is also not convincing enough as it is tied to one dimensionality with a (practically irrelevant) quadratic regularizer.

In conclusion, I did not see much novelty of this submission in terms of theory, and there is no practical implication. I hence suggest rejection for the Area Chair.
review_title: This work is a strictly convex-concave extension of (Vlatakis-Gkaragkounis et al. 2019).

final_score: rating: 6: Marginally above acceptance threshold
review_content: ### Summary

With the aim of improving our understanding of GAN training, the paper studies the behavior of gradient descent ascent (GDA) dynamics in a subclass of the so-called _hidden convex-concave games_. In this family of problems, the players control the input variables of smooth functions whose outputs are taken as inputs of a convex-concave game. 
For the problems covered by this paper, different types of stability around nash equilibria of the hidden game are proved under different assumptions. In particular, the concept of _safe_ initializations is introduced, which clearly distinguishes between the case where the trajectory can and cannot converge to a hidden game solution. As an example, the authors prove that when the hidden game is strictly convex-concave, with safe initialization GDA dynamics converge to a point that solves the hidden minimax game.

### Pros

This paper can have an impact on the analysis of GAN optimization by examining a different line of attack on the problem. 
The analysis and the presentation are clean and the appendix is extremely well-organized. 
The importance of the initialization is further highlighted by the concept of safety, reflecting the additional complexity caused by the nonlinear transformation. 
Overall, this paper presents some beautiful results for the problem under study, and provide concise explanations on how these results are obtained.

### Cons / Limitations of the paper

There are however several important limitations of the work which make it difficult to evaluate the significance of the results.

#### Slight overclaim on the problems covered by the paper
Up to page 2, one may believe that the paper addresses the general hidden convex-concave game as defined by (HCC). Then, on page 3, it turns out actually the paper only focuses on a special type of HCC for which every coordinate of the function output is independently determined by its input variables. This seems to be rather restricted and it is unclear how the results of the paper can be applied to general HCC. Moreover, this limitation is mentioned nowhere in the abstract or the introduction of the paper.

#### Ambiguities in how GANs fit the framework
While the authors claim that GAN training is a specific case of HCC, it is not straightforward from the text that this in fact indicates either of the following
1. The probability distribution has finite discrete support.
2. The discriminator outputs a function and the generator outputs a measure.

The paper (and Section 9 in particular) centers on case 1 which is quite far from real GAN problems, and this message is not so clear in the paper (with only the keyword "discrete" mentioned discreetly). On the other hand, for the second case, we need to study minimax games in a Banach space which is not covered by the paper.

#### The potential of the approach is unclear

Finally, in addition to the above two limitations which weaken the link between the problems studied by the paper and real GAN training, the discretization from continuous ODE to practical algorithms is also non-trivial. The study of the dynamics itself is surely of interest. Nonetheless, taking all these into account, I am just wondering if it would really be possible/suitable to study GAN optimization through the lens of hidden convex-concave games.

### Score justification

I appreciate the efforts that the authors have made to come out with all the results and to present them in such a succinct manner. I however do not put a higher score due to the concerns that I raised above.
review_title: A paper with potential impact despite several important limitations

final_score: rating: 4: Ok but not good enough - rejection
review_content: In this paper, the authors introduce a class of games called Hidden Convex-Concave where a (stricly) convex-concave potential is composed with smooth maps. On this class of problems, they show that the continuous gradient dynamics converge to (a neighbordhood of) the minimax solutions of the problem. This is an exploratory theoretical paper which aims at better capturing the behaviors that can be observed e.g. in the training of GANs.


While the paper has merits, it fails in my opinion to clearly explain its theoretical grounds and findings to a non-specialist of continuous dynamics (like me). I thus cannot recommend acceptance for this version based on my comprehension.


* The authors consider the gradient descent/ascent as a standard optimization dynamics. However, in min-max optimization (and even in practical GAN training see e.g. "Reducing Noise in GAN Training with Variance Reduced Extragradient" by Tatjana Chavdarova, Gauthier Gidel, François Fleuret, Simon Lacoste-Julien), extragradient techniques are actually more often used that gradient descent-ascent due to they better theoretical properties (see the first paragraph of the introduction). Notably, EG can converge to a saddle point in bilinear games where gradient fails (see Chavdarova et al. above or Hsieh et al. 2020) even though they globally come from the same continuous-time dynamics. Thus, it is natural to wonder why/if the continuous-time gradient dynamics bears valuable information about the saddle-point problem and associated behaviors. I would like to see the authors address this in the introduction.

* The paragraph "Our class of games" and "Our solution concept" quite verbose and hard to understand (maybe adding in equations the definitions of Nash Eq. and Von Neumann solutions would help). Since a goal of the paper is to provide intuition on the dynamics of certain games with respect to certain solution, these should be made very clear for the reader, this is not the case at the moment.

* I am concerned with the definition of "safe initialization" (Def 3) and notably how it can be checked (which is unfortunately not discussed). Typically, most results assume a safe initialization which looks like a local basin of attraction. This kind of contradicts the statement that the results are "non-local" in the abstract.

* Concerning the difference between the considered setup and previous ones: i) Apart from the "reparametrization" of Section 2.3, what changes between this setup and the convex-concave saddle point gradient dynamics?  ii) and Compared to hidden bilinear games?

* The authors claim in the conclusion that the "modular structure" of their proofs make HCC games suitable "theoretical testbeds". However, it is a bit hard while reading the paper to pinpoint the mathematical tools that can actually be used for further studies. While looking at the 23 pages appendix, I feel that Eq. (1) -- the dynamics; Theorem 1 -- the reparametrization; and Lemma 2 -- derivation of the non-increasing potential, are the most important results (or rather their instantiation for GDA dynamics). In th present version, they are a bit lost in the very long appendix. Maybe dropping down the general case and the regularization parts would enable to better present these points in the paper.


Minor Comments:
* In the first paragraph of the introduction, the authors cite 16 references at once. I am not sure that this is actually informative. Either the authors could break down these refs into smaller chunks/units that relate to one particular kind of results (as id done in the second paragraph) or drastically reduce the number of papers cited there.
* The term "hidden convexity" may be a bit confusing since it may refer to e.g. local strong convexity around the solution. In the literature, the term convex composite problem is sometimes used to denote minimization problems of the form \min_x h(c(x)) with h a convex function and c a smooth mappings (see e.g. "Efficiency of minimizing compositions of convex functions and smooth maps" by Drusvyatskiy and Paquette), this may be mentioned as well.
* In Lemma 2 and Theorem 2, "is a safe for" probably misses the word "initialization".
* In Theorem 2, the sense of "stable" here should be defined.
* Lemma 3: "is the non-empy" should be "be the non-empty".
* bottom of p7: "regularization" is spelled wrong, "it can posed" -> "be posed"
* In Figure 3, how is the continuous dynamics discretized?
review_title: Review

Meta-review: This paper studies the convergence of gradient descent ascent (GDA) dynamics in a specific class of non-convex non-concave zero-sum games that the authors call "hidden zero-sum games". Unlike general min-max games, these games have a well-defined notion of a "von Neumann solution". The authors show that if the hidden game is strictly convex-concave then vanilla GDA converges not merely to local Nash, but typically to this von Neumann solution.

The paper received four high quality reviews and was discussed extensively during the author rebuttal phase. From an application angle, the authors' replies did not convince the reviewers on the relevance of this paper to GANs, and one of the original "accept" recommendations was downgraded to a "reject" because of this. On the theory side, the novelty over Vlatakis-Gkaragkounis et al. (2019) is not clear and the reviewers found the writing often confusing or hard to connect with practice. The reviewer with the most positive recommendation did not champion the paper post-rebuttal. In the end, the consensus was that the work shows significant promise, but it requires refocusing before appearing at a top-tier conference.
Decision: Reject