Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: *Summary* 

This paper study the convergence of Hamiltonian gradient descent (HGD) on minmax games. The paper show that under some assumption on the cost function of the min max that are (in some sense) weaker than strong convex-concavity. More precisely, they use the ‘bilinearity’ of the objective (due to the interaction between the players) to prove that the squared norm of the vector field of the game follows some Polyak Lojasiewicz condition. Thus the proof is concluded by the linear (resp. sublinear) convergence of gradient descent (resp. stochastic GD) under PL assumption.

*Decision*

I think that is work is clearly very interesting. The fact to prove linear convergence rate without strong-convex-concavity is quite surprising. And this paper brings nice tools to analyse HGD. Also the result on Stochastic HGD is very interesting.

However, I am wondering whether this paper is perfectly suited to ICLR conference due to the lack of experiment, practical implication given by the theory, or theory in the non-convex setting (I know that the latter is a huge open question and I am not criticizing the absence of theory in the non-convex-concave setting).
One way to improve to work would be to provide practical takeaways from the theory or to provide experiments in the main paper. 

Regarding the practical limitation of this work: 
- the sufficient bilinearity condition are hard to meet in practice. (even for convex-concave problems)
- In a non-convex-concave setting, Hamiltonian gradient descent is attracted the any stationary point, even “local maxima” (or the equivalent in the minmax setting). Making this algorithm not very practical. (However, CO is)

However, I really think that the community is currently lacking of understanding on minmax optimization and that we need better training method in many practical emergent frameworks that are minmax (such as GANs or multi agent learning). That is why, I would vote for a weak accept.  

*Questions* 
- What are the practical implication of your work ? for instance does it say anything on how to tune $\gamma$ for CO ?

*Remarks*
- It is claimed that Theorem 3.4 gives the first linear convergence rate for minmax that does not require strong-convex or linearity. Note that, recently [1] seem to propose a result on extragradient in the same vein (i.e. without strong convexity or linearity).
- (Minor) $\alpha$ not alway have the same unit: Thm 3.2 it is proportional to a strong convexity and in Lemma 4.7 it is proportional to a strong convexity squared (actually the PL of the squared norm of the gradient). For clarity it might be interesting to use the notation $\alpha^2$ in Lemma 4.7. The same way for unit consistency I would use $L_H^2$ instead of $L_H$

[1] Azizian, Waïss, et al. "A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games." arXiv preprint arXiv:1906.05945 (2019).  


=== After rebuttal === 
I've read the authors's response. 
The concern raised by reviewer 3 is very important. The descent lemma used by the author is not valid for the stochastic result. The authors should address that in their revision.  
I however maintain my grade. 

 
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: 
Summary:
The paper, considers methods for solving smooth unconstrained min-max optimization problems.  In particular, the authors prove that the Hamiltonian Gradient Descent (HGD) algorithm converges with linear convergence rate to the min-max solution. One of the main contributions of this work is that the proposed analysis is focusing on last iterate convergence guarantees for the HGD. This result, as the authors claim can be particularly useful in the future for analyzing more general settings (nonconvex-nonconcave min-max problems).
In addition, two preliminary convergence theorems were provided for two extensions of HGD: (i) a stochastic variant of HGD and (ii)  Consensus Optimization Algorithm (CO) (by establishing connections of CO and HGD).

Main Comments:
The paper is well written and the main contributions are clear. I believe that the idea of the paper is interesting and the convergence analysis seems correct, however i have some concerns regarding  the presentation and the combination of different assumptions used in the theory. 

1) I think definition 2.5 of Higher order Lipschitz is very strong assumption to have. What exactly means? Essentially the authors upper bounded any difficult term appear in the theorems. Is it possible to avoid having something so strong? Please elaborate.

2) In assumption 3.1 is not clear what $L_H$ is. This quantity never mentioned before. Reading the Lemmas of Section 4 (Lemma 4.4) you can see that it is the smoothness parameter of function $H$. Thus, is not necessary to have it there (not important for the definition).

3) What is the main difference on the combination of assumptions on Theorems 3.2, 3.2 and 3.4. Which one is stronger. Is there a reason for the existence of Theorem 3.3?

4) All the results heavily depend on the PL condition. I think having this in mind, showing the convergence of Theorems 3.2-3.4 is somehow trivial. In particular, one can propose several combinations of assumptions in order for the function H to satisfy the PL condition. Can we avoid having the PL condition? The authors need to elaborate more on this.

5) In Theorem 5.2, the term 1/sqrt(2) is missing from the final bound.

Minor Suggestions:
In first paragraph of page 5 where the authors divide the existing literature into the three particular cases, I am suggesting to add the refereed papers inside each one of this cases (which papers assumed function g bilinear , which papers strongly convex-concave etc.)

I understand that the main contribution of the work is the theoretical analysis of the proposed method but would like to see some numerical evaluation in the main paper. There are some preliminary results in the appendix but it will be useful for the reader if there are are some plots showing the benefit of the method in comparison with existing methods that guarantee convergence (which method is faster?). In the current experiments there is a comparison only with CO algorithm and SGDA.

In general i find the paper interesting, with nice ideas and I believe that will be appreciated from researchers that are interested on smooth games and their connections to machine learning applications. 

I suggest weak accept but I am open to reconsider in case that my above concerns are answered.

**********after rebuttal********
I would like to thank the authors for their reply and for the further clarification. 
I will keep my score the same but I highly encourage the authors to add some clarification related to my last comment on the globally bounded gradient. 
In their response they mentioned that the analysis only requires that  H is smooth and that $\|\xi(x^{(0)})\|$ is sufficient bound. This needs to be clear in the paper (add clear arguments and related references). 
In addition, in their response they highlight the non-increasing nature of function H over the course of the algorithm which is important for their argument. Having this in mind note that the theoretical results on stochastic variant presented in the paper are wrong. In SGD,  function H does not necessarily decrease over the course of the algorithm. The authors either need to remove these results or restate them in a different way in order to satisfy the assumed conditions.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper shows that Hamiltonian gradient descent (HGD), which is gradient descent on the norm of the squared norm of the vector field, achieves linear convergence for a broader range of problems than bilinear and convex-strongly concave formulations. In particular, the authors show the result for convex-concave problems satisfying a “sufficiently bilinear” condition that is related to the PL conditions. Finally, the authors argue that consensus optimization (CO) can be viewed as a perturbation of HGD when the parameter choice is big enough. From this viewpoint they derive convergence rates for CO on the broader set of problems. This provides some further theoretical justification of the success of CO on large scale GAN problems.

The paper is presented in a clear manner, with the objectives and analysis techniques delineated in the main paper. This was helpful to get a sense of the main points before going through the appendix. The objective of the paper is to extend the problem settings for which there is last iterate min-max convergence rates, which now exist for bilinear, strongly convex-strongly concave, and convex-strongly concave problems. The authors achieve this by analyzing HGD and giving convergence rates for when a “sufficiently bilinear condition is satisfied”. The primary idea behind the proof techniques is to show that the objective (Hamiltonian) satisfies the PL condition. I found this to be an interesting approach.

As a result, the main question in evaluating this paper is on the significance of the result and the generality of the “sufficiently bilinear” condition. I tend to lean toward the result carrying some significance since it does extend the class of problems for which the convergence rates exists. However, the weakness is that the condition is opaque and it is not entirely clear how broad of class of problems this condition would apply to. I do acknowledge that the authors did a reasonable job of trying to clear this up in section 3.2 and section G of the appendix. It did still leave me wanting more with respect to the practical significance though. 

Finally, I found the connection to CO valuable. In particular, since this paper does not show large-scale experiments, the connection serves to provide some more theoretical evidence for they CO performs well in practice.

Post Author Response: Thanks for the response. I agree with your perspective and think this paper should be accepted.
review_title: Official Blind Review #2

Meta-review: This provides a simple analysis of an existing algorithm for min-max optimization under some favorable assumptions.  The paper is clean and nice, though unfortunately lands just below borderline.

I urge the authors to continue their interesting work, and amongst other things address the reviewer comments, for example those on stochastic gradient descent. 
Decision: Reject