Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: In this paper, the authors introduce a new optimization algorithm for minimax problems, or finding equilibria in sequential 
two-player zero-sum games. Such problems are common in machine learning, including generative adversarial networks or primal-dual reinforcement learning. The commonly used gradient descent-ascent algorithm, corresponding to taking a gradient step for both players (or for both variables being minimized and maximized over), does not converge, in general, to local minimax points. Moreover, it can converges to fixed points which are not local minimax. To address these issues, the authors introduce the "follow the ridge" algorithm for minimax optimization problems. Given a minimax problem min_x max_y f(x, y), this algorithm consists in adding a correction term to the gradient corresponding to the y variable (corresponding to the max). This term is derived from the observation that minimax optimization should follow ridges (i.e. local maximum w.r.t. to y) of the function. Ridges can be defined as the implicit functions such that the gradient w.r.t. y is equal to zero, allowing to design an update that would stay "close" to the ridge. The correction term corresponding to the update thus involve the inverse of the Hessian w.r.t. y. The authors prove that all the fixed points of this algorithm are minimax, and that all local minimax are fixed points of the algorithm. The proof use first and second order conditions for local minimax points, which were recently derived in a paper by Jin et al. The proposed algorithm can also be used with momentum and preconditioning, and be generalized to Stackelberg games. Finally, the authors evaluate the follow the ridge algorithm on toy low dimensional GAN problems, as well as experiments on the MNIST dataset, showing better convergence that other methods used for minimax optimization problem.

The problem studied in this paper is an important one, as it arises in multiple area of machine learning such as adversarial 
training or reinforcement learning. It has also received significant attention from the community in the recent years. This paper propose a simple solution, which is well motivated, to the problem as well as a proof of convergence. A limitation of the proposed method is that it uses the Hessian of the problem, probably making it hard to apply on large  scale problems that are common in deep learning. I believe that it would make the paper stronger to discuss potential ways to mitigate this issue (e.g. inspired by L-BFGS), and their impact on theoretical guarantees. (Note that the authors briefly mention using the conjugate gradient algorithm in the experimental section).

Overall, the paper is well written, and easy to follow (even for non-expert like me). I believe that it does a good job at introducing the problem and existing work on which it builds, and to motivate the proposed solution. I have not checked the proofs carefully, but they seem sensible. A small weakness of the paper is the experimental section: for example, I am not sure the MNIST experiments bring much to the paper, and would have preferred more convincing experiments. However, this is mostly a theoretical paper, and I do not think this is a big concern.

To summarize, I think the paper study an important problem, proposes a sound solution and is clearly written. For these reasons, I believe that the paper should be accepted to the ICLR conference. However, as I am not an expert on this area, my recommendation is a low confidence one.


Minor comment: I believe that at the beginning of second paragraph of section 4, "Suppose that y_t is a local minimum of f(x_t, .)" should be "maximum".
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: Summary: This paper designs a set of dynamics for learning in games called follow-the-ridge with the goal of finding local stackelberg equilibria. The main theoretical results show that the only stable attractors of the dynamics are stackelberg equilibria. Moreover, the authors give a deterministic convergence rate for the vanilla algorithm and a convergence rate using momentum. Empirical results show the learning dynamics cancel out rotational components and drive the vector field to zero rapidly, while reaching good performance on simple GAN examples.

Review: This paper focus on sequential games, which is the common formulation of GANs and a number of games in machine learning applications. From this perspective, it is natural to look at Stackelberg equilibria. In my opinion, the objective of the paper is important and relevant. The theoretical and empirical results are reasonably convincing. However, I do have some rather serious concerns about the general-sum game results and several questions regarding the relation to related work and the experiment details that need to be addressed.

1. The FR dynamics in algorithm 1 are closely related to the dynamics in [1]. In particular, the Jacobian of the FR dynamics is a similarity transform of the Jacobian of the dynamics in [1]. As a result, each algorithm has the same set of stable attractors. This should probably be mentioned in the paper. Given this relation, it is not clear what the advantage of the FR dynamics are over the dynamics in [1]. Could you please discuss this?

2. The gradient penalty regularization connection does not make sense in section 4.1. The optimization problem presented has an issue because the dimensions do not align in the constraint. The quantity \nabla_x f(x, y)^T H_yy^{-1}\nabla_x f(x, y) would not be defined if the dimensions of the players are not equal. 

3. In the related work it is claimed that two time-scale GDA converges only to local minimax and [2] is cited. I would avoid using this claim with respect to that paper since the statement following the main result in the paper is not right (see proposition 11 of [3] for proof). It is not clear what is meant when it is claimed that [1] can converge to non-local Stackelberg points. The dynamics in [1] only converge to local minimax points in the special case of zero-sum games.

4. Since the dynamics in the paper are the closest to those in [1], it seems that the paper would be stronger by comparing with that set of dynamics. 

5. I found it to be quite impressive that the vector field is driven to zero in the GAN examples. Just to clear, for each algorithm when the ‘gradient norm’ is shown, does this mean the norm of the update for each norm or does it mean the individual derivative for each player. For example in FR, would it be the norm of the derivative with respect to the follower variable of the function or the norm of the update including the second order information?

6. The path angle plot was interesting to see for the GAN example. The authors claim that the eigenvalues of the second order equilibria condition are non-negative. It would be nice if the authors could show the eigenvalues in the appendix and discuss how they were computed since it may be non-trivial to compute depending on the network size.

7. The damping method to stabilize training is not quite clear. Could you provide more details about how this was done?


My primary concerns have to do with the portion of the paper considering general-sum games. I do not understand where proposition 7 and 8 come from. I am not convinced the definitions provided are necessary and sufficient conditions for Stackelberg equilibria. In [1], a differential Stackelberg equilibrium is defined. The definition in this paper does not appear to agree with the definition in [1]. The final positive definite condition in proposition 7 and 8 does not appear to be taking the total derivative 2 times when I evaluate the derivatives, so I am not sure what the quantity is. If this is not a proper set of conditions for the equilibria, then it would also mean that the dynamics do not only converge to equilibria in general-sum games. It is important that the authors clear up this concern since I do not believe Theorem 3 holds as a consequence of problems with propositions 7 and 8.

[1] Fiez et al.,  "Convergence of Learning Dynamics in Stackelberg Games",  2019.
[2] Heusel et al., "GANs trained by a two time-scale update rule converge to a local Nash equilibrium", 2017.
[3] Mazumdar et al.,  "On Finding Local Nash Equilibria (and only Local Nash Equilibria) in Zero-Sum Games", 2019.

Post Author Response: Thanks to the authors for the effort in discussing the paper with me. The authors made several changes to the paper in response to my comments including removing section 4.1, fixing comments about related work, including details on the damping procedure, showing experimental comparisons to [1] along with an explanation of why the dynamics in this paper may be preferred for training GANs, providing details on propositions 7 and 8 and including reference to [1], adding further assumptions on the functions, and attempting to make theorem 3 more clear. Overall, I think this paper proposes an interesting set of dynamics, several meaningful theoretical guarantees, and impressive empirical results. I would be curious to see how it performs on even more large-scale GAN problems in the future. As a result, I have changed my original score from a weak reject to a weak accept. My primary concerns with the paper regarded the general-sum convergence results and I appreciated the explanations from the authors. I am still of the opinion that theorem 3 could be stated more rigorously in the sense that the neighborhood on which the local convergence holds should be more explicit. It seems to me that the convergence result may only hold in a ball around an equilibrium in which the implicit function is well-defined and the FR dynamics will be attracted to r(x) and that this space could be arbitrarily small for some problems. Nonetheless, this result is only in the appendix, and the paper includes enough contributions beyond this to warrant acceptance. 

review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: Summary
The present work proposes a new algorithm, "Follow the Ridge" (FR) that uses second order gradient information to iteratively find local minimax points, or Stackelberg equilibria in two player continuous games. The authors show rigorously that the only stable fixed points of their algorithm are local minimax points and that their algorithm therefore converges locally exactly to those points. They show that the resulting optimizer is compatible with heuristics like RMSProp and Momentum. They further evaluate their algorithm on polynomial toy problems and simple GANs.

Decision
I think that this is a solid paper that addresses the well-defined goal of finding an optimizer that only converges to local minimax points. This is established based on both theoretical results and numerical experiments. Since there has been a recent interest in minimax points as a possible solution concept for GANs, I believe the paper should be accepted.

The paper occasionally makes claims that the solutions of GANs should consist of local minimax points ("We emphasize that GAN training is better viewed as a sequential game rather than the simultaneous game, since the primary goal is to learn a good generator."), which are not backed up by empirical results or reference to existing literature. If anything, the empirical results in this paper do not show improvement of the resulting generator (with the exception of the 1-dimensional example that has a particular rigidity since low discriminator output can easily restrict the movement of generator mass based on first order information). The right solution concept for GANs is not what the paper is about, but before publication the authors should remove these claims, identify them as speculative, or substantiate them .

Suggestions for revision
(1) In the last displayed formula on page 4 it should be the gradient w.r.t x.
(2) Remove, substantiate, or mark as speculative the claims regarding the right notion of solution concept for GANs.

Questions to the authors
(1) You write " There is also empirical evidence against viewing GANs as simultaneous games (Berard et al., 2019). ". Could you please elaborate, why Berard et al. provides empirical evidence against viewing GANs as simultaneous games?
(2) The Batch size for MNIST of 2000 is much larger than the values I have seen in other works. What is the effect of using more realistic batch sizes in training?
(3) When measuring the speed with which consensus optimization and FR converge, shouldn't you allow consensus optimization five times as many iterations, since you are using five iterations of CG to invert the Hessians in each step?
(4) You mention that you use CG to invert the Hessian, but the Hessian is not positive definite? Do you apply CG to the adjoint equations?
review_title: Official Blind Review #2

Meta-review: The submission proposes a novel solution for minimax optimization which has strong theoretical and empirical results as well as broad relevance for the community. The approach, Follow-the-Ridge, has theoretical guarantees and is compatible with preconditioning and momentum optimization strategies.

The paper is well-written and the authors engaged in a lengthy discussion with the reviewers, leading to a clearer understanding of the paper for all. The reviews all recommend acceptance. 
Decision: Accept (Poster)