Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper analyzes the last-iterate convergence rates of the past extragradient (PEG) method, also known as the optimistic gradient (OG) method, for monotone variational inequality with/without a constraint set, which were not known previously. The authors leverage the performance estimation problem (PEP) technique that outputs numerical convergence rate bounds given problem parameters, step sizes, and the number of iterations. This, however, does not provide an analytical bound, and directly finding analytical bounds via PEP was impossible for the PEG. Instead, the authors cleverly first identified useful inequalities in Lemmas 3.1 and 4.1 for the unconstrained and constrained cases, respectively. These show that some quantities, other than the gradient norm, are monotonically nonincreasing,  (Note that, for the standard EG, the gradient norm was found to decrease monotonically, and this was the key for proving its $O(1/N)$ last-iterate convergence rate in [Gorbunov et al., 2021].) Lemmas 3.1 and 4.1 are then used for constructing potential functions that yielded analytical $O(1/N)$ bounds for the (projected) PEG.
strengths_and_weaknesses: **Strengths**
- Last iterate convergence: Last iterate is the one chosen in practice, so understanding its behavior is of interest, especially for the widely used OG method.
- Example 1.1: an interesting example that supports this paper's further study on PEG over recent developments on accelerated EG methods.
- Clever use of PEP: By using the PEP, the authors numerically identified the trends that (1) PEG has O(1/N) rate, (2) PEG form, rather than OG form, is necessary for the "simple" proof, and (3) the gradient norm does not decrease monotonically. Then, the authors used PEP to identify some quantities that monotonically decrease, which is the key of this paper's $O(1/N)$ rate proof.
- Fixed point residual rate: The rate results of the Proj-PEG are given in terms of standard optimality measure (the fixed point residual), whereas the only other work [Cai et al., 2022] found a rate of EG in terms of the (non-standard) tangent residual.
**Weaknesses**
- Somewhat similar results on EG are recently found in [Cai et al., 2022]
- Lack of intuition and explanation on two different potential functions, especially the one for the constrained case.
questions: - The abstract seems to imply that the O(1/N) rate of the EG-type method without the Lipschitz Jacobian condition is not known before this paper. This is later clarified but I think the abstract can be improved so that there is no confusion.
- Are the derived bounds close to the exact rate bounds (found by PEP)?


limitations: Yes, the authors mentioned extensions to stochastic and non-monotone cases.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies the Past Extragradient (PEG) algorithm for solving variational inequalities wrt to a monotone Lipschitz vector functional F. The main theorem of the paper derivesa $O(1/N)$ convergence rates for $||F(x_n)||^2$ in unconstrained problems and same rate for $||x_n-x_{n-1}||^2$ for constrained problems; and further show $O(1/\sqrt(N))$ convergence in the Gap functions. 

The overview of the proof is given by numerically bounding the worst-case convergence in terms of a sdp relaxation or appropriately parametrized performance estimation problems. The main lemma of the proof establishes a descent criteria in terms of a chosen potential function, which in turn establishes the convergence rates. The closest contribution (based on related work stated in the paper) shows a similar rate for PEG with different proof technique and stronger assumption on $\nabla F$ being Lipschitz. 

I am not fully familiar with related work in this space, but the main results and proofs of the papers are stated clearly.  To my knowledge the proofs in the appendix appear right and the theorem is interesting for the neurips community. 


strengths_and_weaknesses: The paper is well written (I didn't even find many minor typos) and was accessible to me even though I was not familiar with the literature. 

One comment/question I do have is the following: In the related work, the authors claim that Gorbunov et al. 2021 and Cai et al. 2022 show convergence rate of O(1/N) for the related EG algorithm under the same settings of the current paper. From my brief exploration, it appears PEG is a slightly different algorithm, and the analysis is valuable as is. However, it would be useful to reach the broader audience if the authors could comment on what kind of problem/compute instances would benefit from the use of PEG over EG and how different are these algorithms and the proof technique from Gorbunov et al. 2021? The authors already provide such discussion when compared to other related work like Golowich 2020a and EG with anchoring. 

Typo: Line 188, there should be no tilde on top of G_PEG and G_OG.  

Additional comment, as a closely related work it would be helpful to mention the updates for EG somewhere in the paper. For example, in lines 27-28, both algorithms are mentioned but only one is defined which makes a parsing of the sentence a bit hard.
questions: See comment above on comparison to EG. 
limitations: NA
review_title: null

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: Optimistic Gradient Method (OGM) is a variant of Extra Gradient (EG) that requires one gradient per iteration instead of two. OGM can be used to in min-max problems such as game optimization, adversarial learning, and GAN training. This paper considers VIP with smooth and monotone operator and proves that for constrained and unconstrained cases the last iterate of OGM converges to the solution set sublinearly. The paper leverages ​​Performance Estimation Problems (PEP) to get an idea to build the proper Lyupnov functions and then prove the convergence of these functions. 
strengths_and_weaknesses: Clarity

The paper properly explains the difference between OGM and EG and the analysis technique their use e.g. PEP and when compares two variants of OGM. 

Originality

Last iterate convergence proof is not new and I think this paper contribution is a incremental one. However their theoretical comparison between variants of OGM was interesting. 
 
 
Quality

All the proofs presented were correct and sound. The paper is a theoretical mainly however their experimental result in appendix D is not explained well. 
 

Significance

Last iterate convergence is important since in practice the last iterate is usually used as the final result not the averaged one. 

Limitation

The major limitation of this work is that it doesn’t consider the stochastic setting that is mostly used in practice for training large machine learning models with enormous data. 

questions: 1- It seems that this paper already sovled this problem with similar assumptions: 
“Tight Last-Iterate Convergence of the Extragradient and the Optimistic Gradient Descent-Ascent Algorithm for Constrained Monotone Variational Inequalities”. It would be helpful if you explain the difference of your result and this paper. 

2- In line 96-96 you claim that PEG is still largely used in practice. I suggest to add some citations to a real-world models that use PEG. 

3- In Line 238 it should be non-positive.  

limitations: This works addresses the potential social impacts.
review_title: null

Meta-review: metareview: Overall all reviewers were positive about this paper and I tend to agree, but no reviewer felt particularly excited about the results.
confidence: Less certain
Decision: Accept