Venue: NeurIPS 2022 Conference

Reviews:

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 studies the last iterate rate of convergence of extra gradient and optimistic gradient algorithms in smooth monotone games with continuous convex action sets. More specifically, the authors prove that if players employ those algorithms with a constant step size they achieve last iterate convergence rate $O(1/\sqrt{T})$.
strengths_and_weaknesses: This paper is well written and clear. The technique used for finding the potential function needed to prove the result is novel and interesting. 
I consider the contribution of this paper clear and quite important, since it complements and extends existing results from the unconstrained to the constrained setting.


Minor comments: In line 231 there is a typo - hence (an) it suffices.
Line 276: action -> action.
questions: I would like to ask about the definition provided in this paper for the tangent cone. I am not familiar with this definition, could the authors provide some reference for it?

limitations: This paper has no negative societal impact.
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 studies the last-iterate convergence rate to a Nash equilibrium in monotone games (with gradient feedback). It extends previous work to analyze the convergence of no-regret learning algorithm with constant step size in (possibly) constrained games. The authors propose a novel notion, namely the tangent residual, and use it to discover the potential function to show that the extragradient algorithm and the optimistic gradient algorithm have tight last-iterate convergence rates. 
strengths_and_weaknesses: Strengths: The paper is well-written. The achieved results are quite interesting and relevant. The proofs and appendix are very detailed and provide strong supports for the claimed results. The tangent residual notion and the proposed computer-aided proof technique are, as far as I know, novel in this research context; moreover, they might be useful beyond the scope of this paper.

Weaknesses: no major weaknesses. Optimally tuning parameters of the algorithms (and explicitly determining the constants in convergence rates) might make the results clearer. 


questions: - On the search for the potential functions: are the potentials discovered by the SOS program unique (given a set of basis functions)? If not, do we have a solution selection problem (i.e., different potential might provide different rates?) 
Can you please give some intuition of the choice of the basis functions in line 302 (or this choice simply comes from the needs in the proof)?
What is the running time/ complexity of SOS programing (e.g., w.r.t. the number of basis functions)?

- On parameters tuning: Is the parameter $eta$ in Lines 349 and 350 are chosen to give the optimal constants in the convergence rates? If not, can we do it (and get rid of the bigO notation)? Technically, the choice of D can be any upper-bound of the one given in Lines 349 and 350, right? Notably, we can also use the popular choice as stated in footnote 4?

- Perspective: can this line of work be extended to stochastic gradient feedback case? (see e.g., discussion in Appendix A.4, of [GPD20])

limitations: the authors adequately addressed the limitations and potential societal impact of their work
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: The paper focuses on proving last iterate convergence for both Extra Gradient and Optimistic Gradient Descent methods for monotone games in both constrained and unconstrained settings (these setting captures convex-concave min-max optimization for example where the operator is monotone). The authors show tight last-iterate convergence of $O(1/\sqrt{T})$ without any uniqueness assumptions that prior works had consider (without proving rates). Please note that there were works that established last iterate convergence that the dependence on the parameters of the game were not clear (it might be exponential for example in the size of the game). The authors show dependence that is polynomial in the parameters of the game (Lipschitz constant and diameter of the domain for constrained). The idea is first to establish best iterate convergence and then show that the tangent residual (effectively the Hamiltonian) is a potential function.  
strengths_and_weaknesses: Pros:
1) The paper is well written and the proof is elegant. 
2) The problem was an open-question that researchers were actively working on including the reviewer.
3) The result does not hide any exponential dependence on the size of the game, it is very clean with normal assumptions.

Cons:
1) The idea of using sum of squares was already in the literature to construct/prove potential functions. This fact though does not decrease the significance of this work.
questions: My only question is if these results can be generalized for weak MVI type functions/problems. 
limitations: The work is theoretical.
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 paper provides the first last-iterate convergence rates of extragradient algorithm (EG) or the optimistic gradient algorithm (OG) to Nash equilibrium of constrained smooth monotone games in terms of the gap function and Lipschitzs and monotone variational inequality, which match the existing lower bounds $\mathcal{O}(T^{-1/2})$. Tangent residual is proposed as a new proximity measure to a Nash equilibrium and used for convergence analysis.
strengths_and_weaknesses: Originality: The algorithms and problem settings exist in the literature, but the non-asymptotic convergence rate in constrained smooth monotone games is new and tight, and the notion of tangent residual and the choice of potential functions for convergence analysis are novel. Hence, I think the originality is sufficient.
	
Quality: This is a complete piece of work with both strengths and weaknesses. The claims are well supported by the theoretical analysis which looks reasonable, elaborate, and sophisticated (I have read the Lemmas and theorems but have not checked the proof). The experiments look reasonable to me, but it seems that the numerical evidence can be stronger if the authors compute for more iterations in the experiments and plot the potential function value and the performance measures in Appendix J. (see my final question for detail). 	
	
Clarity: The submission is very clear and well organized. The intuition behind some notions could be clarified as elaborated in my questions.   
	
Significance: The results look important to me since it provides the first non-asymptotic convergence rate in constrained smooth monotone games, which also matches the lower bound. 
questions: (1) Why does contribution 1 on page 3 not include EG? 

(2) Typo in Table 1: "cocoercive". 

(3) Typo in Line 95: "require**s** the setting to be unconstrained". 

(4) In Definition 1, you might use parentheses like (that is, ...), (i.e. ...), since at first sight, I misunderstood the formula after i.e. as equivalent to the condition that $F_{\mathcal{G}}$ is both monotone and Lipschitz. Also,  $F_{\mathcal{G}}$ is monotone if and only if $f^{(i)}$ is convex for any $i$, yes? If yes, You might add that intuition. 

(5) In Definition 2, both gap functions are non-negative, and become 0 if and only if $z$ is a Nash equilibrium, right? If yes, you might write down this intuition to help readers outside this area understand. Also, a larger (total) gap function value indicates a larger distance (and thus smaller proximity) to Nash equilibrium, right? If yes, I think it better to describe the gap functions as distance measures (instead of proximity) to Nash equilibrium. 

(6) Is it convenient to clarify the intuition of the notions in Definitions 3? 

(7) $r_{\mathcal{G}}^{\text{nat}}$ appears in line 230 for the first time so here you may cite Definition 7 in Appendix E. (In Line 254, it should be Appendix E, not D.)

(8) Are the potential differences $r^{tan}(z_k)^2-r^{tan}(z_{k+1})^2$ and $\Phi(z_k,w_k)-\Phi(z_{k+1},w_{k+1})$ polynomial? If not, how can you apply SOS programming to them? 

(9) It seems better to compute for more iterations in the experiments and plot the potential function value and the performance measures in Appendix J, to show that all of them approach 0 (yes?), and only the potential function value decreases. 
limitations: In the checklist, item 1b said "Did you describe the limitations of your work? [Yes] Our results are theoretical. We state the assumptions of our results in the statements of the lemmas." Do you consider the assumptions as limitations? If yes, do you intend to weaken them in future works? 
	
The end of the introduction also proposes a future direction to apply the techniques of this paper to stochastic gradient feedback, which implies a limitation and its solution.
review_title: null

Meta-review: metareview: This paper studies the last iterate rate of convergence of the well-known extragradient and optimistic gradient algorithms in smooth monotone games with continuous convex action sets. The main result of the paper is to show that both algorithms (with constant step size) enjoy tight last-iterate convergence rates for setting (previous papers either 1) only applied to unconstrained domains 2) were asymptotic, or 3) required dependence on arbitrarily large problem-dependent constants).

This paper resolves a well-known open problem within the min-max optimization community, and is likely to have significant impact. The reviewers agree that the paper is well-written, and the the techniques (using the "tangent residual" as a potential function) are novel. For the final version, the authors are encouraged to incorporate the reviewers' suggestions to improve the presentation.

confidence: Certain
Decision: Accept