Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studied optimization of minimax games and proposed a recursive optimization algorithm called Level k gradient play (Lv.k GP). As an update based on predictive updates, Lv.k GP does not require second-order information, which is computationally more efficient than existing algorithms.

Theorem 4.1 showed that as k increases, the level k reasoning of parameter vectors is approaching a limit point. And Lv.$\infty$ GP is equivalent to an ideal algorithm Semi-Proximal Point Method (SPPM).

Table 1 then summarized different algorithms and viewed them as approximations of SPPM, and Lv.k GP approximation accuracy improves as k increases.

Theorem 5.1 showed local convergence of SPPM toward stationary points, and Theorems 5.2 and 5.3 showed that for a specific bilinear game and quadratic game, the SPPM converges in terms of squared norm of parameter distances.

Experiments on training GANs using 8-Gaussians, CIFAR-10 and STL-10 are conducted to show that Lv.k GP and Lv.k Adam can be used to help existing GAN optimizers (e.g., Adam) provides noticeable gains in performance and stability.
strengths_and_weaknesses: Strengths:

1. Minimax game optimization is an important problem which has lots of applications such as GANs, while being difficult to resolve and optimize. The research is well motivated.

2. The proposed Lv.k GP algorithm seems novel to me, and the authors provided its approximation to SPPM and showed the convergence properties of SPPM.

3. Experimental results are supporting the proposed methods

Weakness:

1. The proposed algorithms are Lv.k GPs, while the convergence properties are studied for SPPM method, which creates a gap.

2. It is not clear that whether the claim of Lv.k GP is faster than (first order approximations) of second order methods is true or not.

questions: 1. It is claimed that the Lv.k GP methods do not require second order information. Thus I suppose the implication is that Lv.k is faster than second order methods and their first order approximations (e.g., rank-1 approximation)? Is there any evidence to support this?

2. How does the computational time increase as k increases (seems this relation should be linear to me)? It would be better to have the computational time recorded.

3. Theorems 5.1-5.3 studied the convergence properties of the ideal algorithm SPPM. However, the algorithms actually used here are Lv.k GPs. A more direct study should be to get convergence properties of Lv.k GP, where as $k \to \infty$, Theorems 5.1-5.3 could be recovered.
limitations: The authors discussed the potential negative impact of using GANs to generate images, which is reasonable to me.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This work introduces a novel algorithm, closely related to existing "lookahead approaches", for solving minmax games. 
In "level k gradient play" each agent first arrives at a prediction of the opponent's move through k steps of recursive reasoning  *the counter move to the counter move to ... gradient descent*. They then make a step of gradient descent in the direction of the gradient computed using their own present position and their opponent's position according to the recursive reasoning. The authors show convergence results for the (theoretical) infinite recursion version with $k = \infty$. Finally, the authors show numerical experiments on GANs, demonstrating improved IS and FID scores. 
strengths_and_weaknesses: ### Strengths:

- The algorithm seems natural and well-motivated to me. 
- The algorithm appears to provide substantial improvements in GAN training

### Weaknesses:

- The emphasis on SPPM is confusing and makes it hard to understand how the proposed algorithm relates to other methods in the literature.
- Overall, there is a lot of hand-wavey language in the paper that hints at the advantages of the proposed method or results of the paper, that are never made concrete. 

Overall, my present view of the paper is that the results are suitable to be published in NeurIPS. However, the paper needs to undergo a major reorganization/rewrite to clearly convey its key points. I am not sure such a revision is within the scope of a single conference review cycle which is why I tend towards rejection and encouraging the authors to resubmit to a future cycle. 
questions: 1. I find the way in which the algorithms are studied through the lens of SPPM to be confusing. First (up to including section 4), different algorithms are compared regarding how good they are at approximating SPPM. To this point, only vague, anthropomorphic language is provided to justify why approximating SPPM should be desirable. For instance in line 159: "SPPM players arrive at a consensus by knowing precisely what their opponents’ future strategies will be. Existing algorithms are not able to offer this kind of agreement."
In Section 5, justification is given why SPPMs could be interesting by providing convergence results of SPPM. It is also claimed (line 189), that this convergence result is going to be used to study the convergence properties of Lv.k GP. However, this is then declared "beyond the scope of this work" and it is claimed that the convergence property can be "inferred ... via SPPM", without providing rigorous definitions. 
In my opinion, this work could be strengthened considerably if instead of the SPPM characterization a simple local convergence result of Lv.k GP would be given. At first glance, it seems that it should be possible (strictly convex problem, small enough step size), that local convergence can be essentially reduced to the quadratic problem, where Lv.k GP should not be so hard to characterize? I would be curious to hear the opinion of the authors as to what is the roadblock here. Even if an analysis of Lv.k GP is not possible, it seems that by combining the theorems already in the paper it should be possible to provide an analysis for Lv.inf GP. 

2. The authors advertise their methods as not requiring second-order gradient information, compared to other methods that ...
"demand second-order gradient information (e.g., Jacobian-vector product and Hessian inverse), making well-performing models unavailable for standard computational budgets [50, 6]"
This claim is false or at least misleading, as the proposed methods compute gradients at multiple points at each iteration and thus also use second-order information. Furthermore, using performant mixed-mode automatic differentiation frameworks such as JAX, computing Jacobian-vector products need not be significantly more expensive than gradient computation (for Hessian-inverses the story is a bit more complicated). Thus, the above strikes me as mischaracterizing competing methods.

3. Related to the above, none of the experimental data shown give an idea of the cost-vs-quality trade-off of the proposed method. Can you run, say, Adam and Lv.6 Adam side by side and plot the IS and FID as a function of the number of gradient computations?

4. Just out of curiosity: Did you try what happens if you run the experiment shown in Table 2 on the larger, image datasets? 

5. You write in line 164 that "In games with at least thrice differentiable objective function". Since the bilinear objective is infinitely differentiable you probably meant something else. Similar in 176.

6. Is there a reason why LOLA and CGD were not included in Figure 2?
limitations: The authors discuss the additional computational cost of Lv.k in the very end of section 6. However, I was surprised that they did not provide further investigation of this concern by comparing, for instance, and adam model with k times as many epochs to an Lv.k Adam.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a Level K Gradient Play algorithm to stabilize the learning dynamics in minimax games (GANs).  By combining the proposed Lv. K algorithm with Adam optimizer, this  paper could achieve similar results with SOTA GAN model with 30 times fewer parameters. 
strengths_and_weaknesses: **Strengths**:

This paper proposes the Level K Gradient Play Algorithm for stabilizing the training of GANs. The proposed method has a theoretical guarantee, with the assumption that the gradient of the loss function is Lipschitz continuous. Moreover, the paper proves and analyses the convergence properties of the Lv. K algorithm.

**Weaknesses**:
1. **On the definition of SPPM** (line 157). The author claims that "SPPM players arrive at a consensus by knowing precisely what their opponents’ future strategies will be" in line 159. However,  the stationary point $\omega^*_{t} = [\theta_t^*, \phi_t^*]$ obtained with the reasoning step in Line 139 should not equal to the future strategies $\omega_{t+1} = [\theta_{t+1}, \phi_{t+1}]$. In another word, the term $\phi_{t+1}$ used to updating $\theta_{t+1}$ does not equal to the term $\phi_{t+1}$ updated by $\theta_{t+1}$. The author should consider changing the notation here (Line 156). Or it may result in a misunderstanding that the Level.$\infty$ GP algorithm could use the opponents' future strategy to update its current gradient.

2. **Efficiency of the Level K algorithm.** As a level K algorithm would have to compute the gradient for **K** times for $\theta$ and $\phi$, this algorithm would take more time for a single step than a regular algorithm. I would recommend the author compare the method with baseline models regarding time efficiency (similar to Appendix. Figure~6 but with X axis as time).

3. **Difference with Other GAN optimizers**. The proposed methods could be seen as "given current generator, we use K step updates to find a better discriminator and use that discriminator to update the generator, and vice versa." However, some theory shows that, if we use a good (e.g., optimal) discriminator in the beginning, then we could obtain no gradient for the generator (Wasserstein-GAN). The $\omega^*$ in this paper could be seen as the optimal $\phi$ and $\theta$ with the other kept fixed. Then what is the theoretical foundation between this paper and W-GAN that makes both methods work?

4. **Limited Experiment**. This paper only conduct experiment on a small "8-Gaussians" experiment and CIFAR-10. As the author claims an improvement against BigGAN, which is good at high-resolution images, would the algorithm in this paper also be applicable to BigGAN or other big models?

5. The proposed method is to stabilize the training of GAN. However, the author also claims that this algorithm uses 30 times fewer parameters. What's the correlation between stabilizing gradients and small models? Are there any theoretical results on this issue?
questions: As stated in the **Weaknesses** section.
limitations: As stated in the **Weaknesses** section.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work propose Level k Gradient Play, a new dynamical system for non-convex non-concave min-max optimization. The key feature of the dynamics is that each player tries to anticipate what the opponent will do in the following round and adapt to it instead of the opponent's current iterate. Under mild assumptions, the Level $\infty$ dynamics are well defined and enjoy local convergence for quadratic games and global convergence for bi-linear ones. In terms of practical algorithms, Level k algorithms are shown to converge to a Level $\infty$ solution as $k \to \infty$ for sufficiently small learning rates based on a contraction property. This means that they can heuristically be used as replacements for Level $\infty$. Level k Adam variants are shown to have good empirical performance. 
strengths_and_weaknesses: Regarding strengths, the presentation of the algorithm intuition and the key technical results is very clear. The proposed algorithm and analysis are to the best of my knowledge both novel when compared to other approaches in the non-convex non-concave optimization literature. While the theoretical guarantees are not particularly strong (many approaches can solve bilinear problems or have local convergence guarantees), the empirical results are promising.

The only weakness I detect is that this work is similar to [1], which is not referenced. Just like in this work, the agents try to predict the strategies of the opponents in the next turn and adapt to them. This is once again computationally feasible for small learning rates via a contraction argument. Once again the dynamics globally converge for bi-linear games and higher learning rates lead to faster convergence but may be computationally intractable just like this work.  

While the overall technique may be similar to [1], the individual arguments are sufficiently different and the analysis of Section 4.1, Theorem 5.1 and 5.3 and the experimental analysis are unique to this work. Overall I propose to accept this work (Accept, 7).

I have read the response of the authors which addressed my concern. I have thus increased my score to (Strong Accept, 8).
 
[1] Optimal No-Regret Learning in General Games: Bounded Regret with Unbounded Step-Sizes via Clairvoyant MWU, Georgios Piliouras, Ryann Sim, Stratis Skoulakis, arXiv:2111.14737, 2021
   
questions: If the authors comment on the differences/similarities between this work and [1] I would increase my score. More specifically, can Level k Gradient Play or a variant thereof be considered as a special case of Clairvoyant FTRL? 
limitations: N/A
review_title: null

Meta-review: metareview: This paper proposes a novel recursive reasoning algorithm for minimax games, in which players try to anticipate their opponent's next round move instead of reacting to the current round. Importantly, this is achieved without requiring expensive second order information. Reviewers found the paper clearly written and well motivated, addressing an important problem. The work appears novel, and there is good experimental evidence that the algorithm delivers on its promises.
confidence: Certain
Decision: Accept