Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper extends "hidden bilinear" games [1]  to "hidden convex-concave (HCC)" games, and studies a special case of HCC games (denoted as HCC* from below) where output of each dimension of a nonlinear function depends on a seperate group of parameters .

For HCC* games, the authors utilize Lyapunov-type arguments and show that GDA dynamics stabilizes around the output-space Nash equilibrium (Theorem 3), whose parameter counterparts are named as "von Neumann solutions".

With an additional assumption that the game has one-sided strictness property, the authors further show that GDA converges to a "von Neumann solution" (Theorem 6), by combining Lasalle's principle and the fact that "safe initializations" reside in ROA of such solutions.

Additionally, the authors show that adding a regularization term can accelerate the convergence of GDA towards the perturbed equilibrium in the output space (Theorem 8).

Finally, the authors exemplify GANs and evolutionary games, and argue that such games can be nicely formulated as HCC games.
main_review: Pros:
1. non-convex non-concave game optimization is still an area of active research, and we still lack game classes that are (1) expressive enough to represent practical games, and (2) structured enough to admit theoretical analysis. The proposed HCC games satisfy (2).

2. Overall, the proofs seem to be clear, succinct, and well-organized. The authors also provide a brief sketch whenever the proof becomes complicated.


Cons:
1. **(Expressivity of HCC games)**  Arguably, one of the most important non-convex non-concave games in machine learning is GAN. However, it is quite dubious whether GAN can be formulated as a HCC game (even in a simplified setting). In Section 4, the authors formulate GAN training as

$\min_{p_G(x_i)} \max_{D(x_i)}  \sum_i [p_{data}(x_i) \log D(x_i) + p_G(x_i) \log(1 - D(x_i)) ]$.

However, in its original form, GAN objective follows

$\min_{\theta} \hspace{1pt} \max_{\phi} V(\theta, \phi) = \min_{\theta} \hspace{1pt} \max_{\phi} E_x[log(D_{\phi}(x))] + E_z[log(1-D_{\phi}(G_{\theta}(z)))]$,

where $\theta$ and $\phi$ represent the parameters of $G$ and $D$, respectively; the generator never learns $p_G(x_i)$ directly.

I am not sure how one could reformulate the above equation as a HCC game. Even worse, in case of HCC* games (with disjoint parameter groups assumption), I don't think the generator would be possible to model a data distribution with more than one-dimension. The significance of HCC games would be greatly improved if the authors could provide a reformulation of the above $V(\theta, \phi)$ as a HCC game $L(f(\theta), g(\phi))$ for some convex-concave $L$, smooth functions $f$ and $g$.


2. **(Novelty)**
The main idea of “hidden game” was first proposed in [1], and this paper aims to extend [1] by replacing the bilinearity with convex-concavity. To do so, the authors utilize main assumptions (“safe initialization”, the separated parameter groups), technical tools (Lemma 1, Theorem 1), and the Lyapunov function (Equation 4, invariant quantity in [1]) developed in [1]. Considering the fact that the HCC games are a generalization of hidden bilinear games, this could be a natural thing. However, it is hard to say this work is novel, since the conceptual prototype of the game class (“hidden game”) and technical tools (Lemma 1, Theorem 1, Lyapunov function) already have been presented in the preceding work.


Minor comments:
- I have an impression that Theorem 8 is quite obvious and somewhat out-of-place. Any strictly-convex strictly-concave game would admit a linear convergence for GDA, and it is unclear how it relates to the unique structure of HCC games.
- In Theorem 2, $maxLocalMin$ and $minLocalMax$ are undefined.
- In Theorem 5, $R_{f_i}$ and $R_{g_j}$ are undefined.
- Both in abstract and conclusion, the authors mention that *“our convergence guarantees are non-local, which as far as we know is a first-of-its-kind type of
result in non-convex non-concave games”*. However, I believe this is not true. For example, [2] has shown that alternating GDA globally converges for two-sided Polyak-Lojasiewicz (PL) games with a linear rate in deterministic settings, and converges with a sublinear rate in stochastic settings. This is a NeurIPS 2020 paper, so I think there would be more non-convex non-concave global convergence results published this year.

At this stage, I recommend rejection for this paper, mainly on the basis of the Cons 1 and 2.

---

[1] Poincaré Recurrence, Cycles and Spurious Equilibria in Gradient-Descent-Ascent for Non-Convex Non-Concave Zero-Sum Games. Flokas et al., NeurIPS 2019.

[2] Global Convergence and Variance Reduction for a Class of Nonconvex-Nonconcave Minimax Problems. Yang et al., NeurIPS 2020.

limitations_and_societal_impact: Please see Cons 1 & 2 for the limitations.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies a special problem structure in min-max optimization. Specifically, the paper considers the setting when the objective function can be reparametrized into a (strict) convex-concave game, or referred to as a hidden convex-concave game in the paper. 

More formally, the considered function is of the form L(F(\theta), G(\phi)), where L is convex-concave. F and G are of separable structure, namely both the max and min player are from a cartesian product of scalar functions from disjoint sets of parameters. With the separable structure, the authors can thoroughly investigate the conditions for stable GDA dynamics and the good initializations for GDA to find the equilibrium of L. 

Finally, the authors give some discussion on connecting the structures to GANs and evolutionary game theory/biology. 
main_review: 
I believe the overall construction is pretty neat and clever. The paper is also quite nicely written and everything is easy to follow. The final discussions are quite enlightening (although not very well aligned with the main story/analysis of the paper). 

I do agree this is a natural and initial step for understanding more complicated nonconvex-nonconcave objectives. However once the setting is clear, the whole analysis becomes quite obvious, and the technical part is not that challenging. It is also hard to get further inspiration on how to stabilize the training or design new optimization schemes based on the studies in this paper. Therefore my overall evaluation is a borderline accept. 

 



on minor comments:

1. argmin of "argmax" doesn't make sense at the end of page 3.

2. some typos like 'intitializations'
limitations_and_societal_impact: N/A

This is a theoretical work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors study a two-player zero-sum convex-concave game whose inputs are parameterized by nonlinear functions. This results in the overall game being nonconvex-nonconcave in the parameter space. This setting is similar to that observed in GANs where the game is convex-concave in function space of discriminator and generator but is nonconvex-nonconcave in the space of parameters. The authors call such games as Hidden Convex-Concave (HCC) games.
main_review: The paper generalizes the work of Flokas et al. for hidden bilinear games. The generalization is theoretically nontrivial because Euclidean distance is not a Lyapunov function in general. The authors propose a generalized Lyapunov function for analyzing asymptotic convergence of dynamics to the solution of the HCC game. In that process, they need to assume that the underlying game is strictly convex-concave (which should not be confused with strictly-convex strictly-concave).
In the case of convex-concave games, they study a regularized underlying game. This makes the problem strictly (or rather strongly) convex-concave. While it changes the underlying equilibrium, the aforementioned results immediately imply convergence to the regularized equilibrium point.
In the case of GAN example in Section 4 (first application), the presence of \lambda (\sum_N p_G(x)-1) in the final game makes \lambda part of the maximization variable. Then, this underlying problem is not strictly concave in the combined variable (D, \lambda) for fixed G. Does this affect the convergence claims?
Overall, the authors have provided a clear explanation of their claims. The paper makes interesting contributions that might contribute to a better understanding of GANs. The point that different parameters \theta_i are used in different functions can be a source of limitation for application to the wider Neural Network-based GAN models. However, I believe the limitation outweigh the overall merits and hence I provide a high score.
limitations_and_societal_impact: Please address the concerns mentioned in the main review.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This work studies the continuous dynamics of GDA in hidden convex-concave games via tools from dynamical systems.  
main_review: Following ref [66] that studies hidden bilinear games, this paper studies hidden strict convex-concave games. It shows that GDA stabilizes around von Neumann solutions of hidden games. The authors claim that these hidden convex games could help us understand GAN training and this is a first step.

However, I think this paper is not ready for publication yet. During my reading I'm confused about the novelty, clarity and significance. 

Clarity: I acknowledge the attempts to add some paragraphs to summarize the main contribution (line 59-63) and the structure of the paper (Line 112-115), but there are many parts of the paper that imply that this paper is not quite well written and not polished enough.

1) The question in line 38-39 comes from nowhere. Why is this question interesting? How do we relate it to previous background? 
2) line 48-58: is the von Neumann solution formally defined anywhere? Because I did not find the definition. 
3) line 76-78 seems repetitive
4) Line 166: what is $k$ in definition 2? 
5) Thm 1: what is the meaning of $X_{\theta(0)}$, $X_{\phi(0)}$?
6) Line 233: could you explain LaSalle's invariance principle or give a reference? 
7) In Section 4 it is claimed that GAN is hidden strictly convex-concave games. However, I think a caveat is that the authors are studying the game in the function space, which is convex-concave. This is already known. The nonconvexity comes from the neural net parametrization which leads to difficulty in training GANs but I have not seen it discussed anywhere. 

There are many small typos which may affect the readability, such as: 
1) Line 28: GANS -> GANs
2) Line 33: local minmax -> local min-max
3) Line 52: quotation marks
4) Line 151: is z(t) a definition? There is no ending mark
5) period mark in Thm 1, and the caption of Fig 3
6) The end of page 7: what is $\mathcal{N}(0, \alpha)^2$? 
7) Line 281 below: what does $(0, 1)^{|\mathcal{N}|}$ mean?

Relevance & Significance: 
1) I don't quite understand the biology application. What are $F, G, L$ in this application according to HCC? Also I'm not sure if this application is relevant to the ML community.
2) What is the main finding towards the practice of GANs? Is it Section 3.3 that says we should do regularization? Could you do some GAN experiments to illustrate this? How do you compare this method with say WGAN with gradient penalty? 
3) GDA has been analyzed in nonconvex-concave games, see e.g.  arXiv:1906.00331. I also wouldn't say in line 365 that this paper is the first work towards understanding GAN training theoretically because there are many recent works on this, see ref [23] and refs therein.


Novelty: I would like the authors to compare their main results with ref [66]. For example,

1) Theorem 1 is similar with Lemma 2 of [66].
2)  Lemma 2 is similar to Theorem 2 of [66].

How does your proof techniques incorporate [66] and what is different? 

Related work:
Line 256: Hamiltonian Gradient Descent needs some reference


limitations_and_societal_impact: The author did not address the limitations and potential negative societal impact and they claim it is purely theoretical work. I would suggest adding some discussion on GAN training and biology applications.
review_title: null

Meta-review: Most reviewers appreciated the novelty of the class of the problems studied and found it interesting.  There are concerns about the expressivity of HCC games in practical settings that has not been fully addressed by the authors. There were also questions about the contributions w.r.t. reference [66]. However, as authors mentioned, the invertibility assumption is one of the key differences of their work with reference [66]. Another comment was about defining various concept needed to understand the paper. It would help the reader a lot if the authors can define all necessary concepts to understand the paper (e.g. La Salle's principle Vo Neumann solution, etc.)



Decision: Accept (Poster)