Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities
Authors: Eduard Gorbunov
Adrien Taylor
Gauthier Gidel
Venue: NeurIPS 2022 Accept (2022)
Keywords: optimistic gradient method
monotone variational inequalities
last-iterate convergence
computer-aided proofs

Abstract: The Past Extragradient (PEG) [Popov, 1980] method, also known as the Optimistic Gradient method, has known a recent gain in interest in the optimization community with the emergence of variational inequality formulations for machine learning. Recently, in the unconstrained case, Golowich et al. [2020] proved that a $O(1/N)$ last-iterate convergence rate in terms of the squared norm of the operator can be achieved for Lipschitz and monotone operators with a Lipchitz Jacobian. In this work, by introducing a novel analysis through potential functions, we show that (i) this $O(1/N)$ last-iterate convergence can be achieved without any assumption on the Jacobian of the operator, and (ii) it can be extended to the constrained case, which was not derived before even under Lipschitzness of the Jacobian. The proof is significantly different from the one known from Golowich et al. [2020], and its discovery was computer-aided. Those results close the open question of the last iterate convergence of PEG for monotone variational inequalities.

Last-Iterate Convergence of Optimistic Gradient Method for Monotone Variational Inequalities
Eduard Gorbunov
Adrien Taylor
MIPT, Russia
INRIA & École Normale Supérieure, CNRS & PSL Research University, France adrien taylor@inria.
Mila & UdeM, Canada
MBZUAL, UAE
eduard, www.booowwbobbbiiiccooommmm
Gauthier Gidel
Mila & UdeM, Canada
Canada CIFAR AI Chair
gauthier gidel gww.le@mmonerral......
Abstract
The Past Extragradient (PEG) [Popov, 1980] method, also known as the Optimistic Gradient method, has known recent gain in interest in the optimization community with the emergence of variational inequality formulations for machine Icarning. Recently, in the unconstrained case, Golowich et al. [2020a] proved that O(/N)) last-iterate convergence rate in terms the squared norm the operator can be achieved for Lipschitz and monotone operators with Lipschitz Jacobian. In this work, by introducing a novel analysis through potential functions, we show that (i) this OL/N) last-iterate convergence on the Jacobian of the operator, and (ii) it can be extended to the constrained case, which was derived before even under Lipschitzness of the Jacobian. The proof is significantly different from the one known from Golowich et al. [2020a], and its discovery was computer-aided. Those results close the open question of the last iterate convergence of PEG for monotone variational inequalities.
be achieved without any assumption
Introduction
Minimax optimization, and more generally variational inequality problems, has known surge of interest with the recent introduction machine learning formulation with multiple objectives such as robust optimization [Ben-Tae -een-Tal et al., 2009], control [Hast et al., 2013), generative adversarial networks (GANs) [Goodfellow et al., 2014], and adversarial training [Goodfellow et al., 2015, Madry et al., 2018). In this work, given convex set X. focus solving monotone variational inequalities:
find xx X' such that (F(=*), x²) 2 0, Yz X' Rd.
(VIP-C)
In the unconstrained case (X' = IR this optimality condition can be simplified as
find xx Rd such that F(x")= =
(VIP-U)
We focus on the monotone and Lipschitz setting which sufficient to ensure the existence of solutions for VIP-C and is the standard setting study first-order methods [Facchinei and Pang, 2003]. Assumption 1. F: X + Rd is monotone and L-Lipschitz, for all x, y E X
(F(x) F(y), v) 2 and
[[ F < T.I - yll.
furthermore, there exists some x² E X which a solution to (VIP-C).
"The work was done when E. Gorbunov was researcher MIPT and Mila & UdeM.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this context, it is well known that the standard Gradient method x²+1 proj[æ* - -F(x*)] (also
known as the Forward method), where proj(z) == argmin,yex' lly - ==|², does not always converge. Two important first-order methods have been introduced to circumvent this issue: the extragradient method (EG) [Korpelevich, 1976]
F²t proj[=* "x(x"),, x 2++1 = projjz* >F( for all 0,
(Proj-EG)
and the past extragradient method (PEG) [Popov, 1980] defined via the following recursions: To x² X. x² proj[= >F(x")), and
- -rojje -F(Tt=1)] "), x++1 projiæ - >F(("> for all 0. (Proj-PEG)
In the unconstrained case, the method simplifies to x² = = - (x))x,, and for all k 2
7*t = x - -FFT=-)) p = Iz -F((")
(PEG)
with the convention that 1) = O, allowing us use the above recursions for k == 0. Note that, in this case, PEG is often studied in the equivalent form called Optimistic Gradient Method (OG):
g = 3² 2- 2T*) + +F((""1))
(OG)
Under Assumption 1, some recent works have managed to leverage tools for computer-aided proofs to show a O(/N)) (for the squared norm of the operator/squared residual") last-iterate convergence rate for the extragradient method (EG), where N denotes the total number of iterations. This was achieved in the unconstrained case by [Gorbunov et al., 2021] via the performance estimation technique [Drori and Teboulle, 2014, Taylor et al., 2017c] and in the constrained case [Cai et al., 2022] via Sum-of- Squares (SOS) techniques [Shor, 1987, Nesterov, 2000, Parrilo, 2000, Lasserre, 2001] (note that "performance estimation" corresponds to SOS of order 2). Our work leverages performance estimation problems (PEPs) for obtaining similar convergence results for PEG and Proj-PEG.
Outline. This paper is composed of five sections. In $1 we introduce our motivations, our main results and discuss the related work. In $2, we show how we used PEP to hint us toward a valid potential function. We prove the convergence of PEG in the unconstrained case and the constrained cases respectively in $3 and $4. Finally, we discuss our results and future research directions in $5. Since the proof in the unconstrained case is slightly simpler than in the constrained one (although it cannot be straightforwardly deduced from our analysis in the constrained case), in the main part of the paper, discuss in detail the way the proof in the unconstrained case, and defer the proofs and other details on the constrained case to Appendices C and D. Codes for verifying the potentials and convergence rates are publicly available: https:// //pps://tttttbbb com/ eeduarggobuuoo/pooeeee uud_lat_____ thta__ttr_______ itte__ convergence, eareeeeeerrr__eee VIPs, the codes rely on the PEP packages [TTaylor et al., 2017b, Goujaud et al., 2022] well on YALMIP [Lofberg, 2004].
als_
1.1 Presentation of Our Main Results
For variational inequalities with possibly unbounded domains, there exist two main standard con- vergence criteria in the literature. The first one is the restricted gap function [Nesterov, 2007]
Gap (x*))=
max vEx:1ly=-1155
(F(y), -))
(2)
where x" is any solution' of VIP-C. This quantity is an actual gap function only if ||a - x01| S and that it cannot be extended to the non-monon non-monotone setting where, for instance, there might exist several points where F(x)= O. Since we show that || x1 < Y/ ||ا x*1l and ||a** x'1 <
22 x01
x/2 F(x") Ak 2 0 in the unconstrained and constrained cases respectively,
can set R = VI o x²1 in the unconstrained case and R / x=1| + V3LL [[=")) in
See [Hsich et al., 2019] for an overview of the different single-call variants of the extragradient method. By default, we always refer to the rates of convergence for [F the unconstrained case and N 2 in the constrained case.
'For simplicity, we slightly deviate from the standard notion of the restricted gap function from Nesterov [2007]. since we do not assume that set {y X [ly z'1l || < R} contains all solutions of VIP-C, C. Taking R larger than the diameter of the solution set resolves the discrepancy between definitions.

---

the constrained case and have that (ap == Gap p(*" ((()aa) is a gap function for all l 2 0. Another convergence criterion is the (squared) norm of the residual || 1²1 In the unconstrained setting, it is proportional to the (squared) norm of the operator ||F This criterion is also valid as a local convergence certificate in the non- non-monttone case. We believe this criterion depicts a more precise picture than the standard gap function since it does require
bound on ||æ x=) to be valid and it generalizes to non-monotone settings. Nevertheless, we provide convergence results in terms of both criteria.
Our main theorems introduce new potential/Lyapune functions for PEG with two main conse- quences: (i) it implies uniform bound on || -x" I|. and (ii) we show a O vN) convergence rate for [x*"*)) [I and Gap in the unconstrained case and for || - x and Gapp(a in the constrained case.. Theorem and Theorem 2 below provide simplified versions of the results; more detailed/general statements are presented later in $3 and $4.
Theorem (Unconstrained Case). Under Assumption 1, all N 2 0 and 7 = 1/31, we have
123L |x0
x²11?
125L x - -x"1l
112
(app(
(3)
N + 32
v3N + 96
where is any solution to VIP-U.
Theorem 2 (Constrained Case). Under Assumption 1, for all N 2 2 the iterates of Proj-PEG with satisfy
7 = 1/4r.satisfy
24HH
32L/3H2
11:N x. 112
(app(x")
(4)
3N + +22
V3N + +2
where Ho > is such that H. = =33331/2 3//200
11 + 301 [F(22)|
and x² is any solution VIP-C.
1.2 Related Work
Linear last-iterate convergence rates. Motivated by nonconvex-nonccocave such as GANs, last-iterate convergences in the context of variational inequalities is the focus of many recent works. Linear convergence rates have been obtained, the bilinear setting, the (local) strongly monotone setting, and similar settings such as sufficient bilinearity [Tseng, 1995, Daskalakis et al., 2018, Liang and Stokes, 2019, Gidel et al., 2019a,b, Mokhtari et al., 2019, Peng et al., 2020, Zhang and Yu, 2020, Abernethy et al., 2019, Loizou et al., 2020, Hsich et al., 2019, Azizian et al., 20.0a.b].
nonconcave minimax formulation
Sublinear last-iterate convergence rates for EG and PEG. More recently, the community has been focusing on the question of last-iterate convergence rate in the monotone setting (i.e., without strong monotonicity or sufficient bilinearity). For monotone and Lipschtiz operators obtaining O(/N) last-iterate convergence rate of PEG was explicitly stated as open question in [Hsich et al., 2019]. In the unconstrained case, Golowich et al. [2020a] achieve this result by adding an assumption on the Jacobian of F being Lipschitz. For EG as similar result has been obtained in Golowich et al. [2020b]. Eventually, a last-iterate convergence rate for EG has been provided by Gorbunov et al. [2021] in the unconstrained case and by Cai et al. [2022] in the constrained case, both under Assumption I solely. The question of last-iterate convergence rate for PEG both in the unconstrained and constrained cases mentioned by Hsieh et al. [2019] remained open until now and is the central question addressed here.
Variants of EG and PEG. Recently, some modification of EG with anchoring (a.k.a,, Halpern iteration [Halpern, 1967]) enjoying (accelerated) last-iterate convergence rates have been proposed by [Yoon and Ryu, 2021]. [Lee and Kim, 2021], and [Diakonikolas, 2020]. This work is concerned with method achieving the suboptimal (L/N) rate, whereas O()x²²) can be achieved using optimal
'We notice that ||~~ - x N-1 = -1 || in the unconstrained case, which differs from quantity (1)((" IIl that we estimate. However, [[F(1*)]] and [==("))] are of comparable size since [[((**)
F(a*)l Ill S > for all A: 2 O.
'The paper [Cai al., 2022] originally contained O(YN) analysis of the Extragradient method for Lipschitz monotone variational inequalities. In the updated version of their work, Cai et al. [2022] obtained (11xx) convergence rates for OG using higher-order sum uum-of-squares. The results in our work were obtained independently and using different approach. On the way, this work showcases that it is not necessary to use higher-order ofn-oo-squaeee when working with standard residual (i.e., using quadratic inequalities suffices).
3

---

methods [Diakonikolas, 2020, Yoon and Ryu, 2021, Lee and Kim, 2021, Tran-Dinh and Luo, 2021, Tran-Dinh, 2022]. We argue that (i) PEG is still largely used in practice, (ii) PEG is simple and more flexible, and (iii) that it benefits from additional advantageous properties, such as adaptivity to additional problem structure. Regarding (i) we would like to mention that Daskalakis et al. [2018] show that PEG-based algorithms (like PEG-Adam) perform well in training WGAN on CIFARIO and PEG/OG have been extensively used in regret matching [Brown and Sandholm, 2019], counterfactual regret minimization [Farina et al., 2019], and for training agents to play poker [Anagnostides et al., 2022]. With a bit more details about (ii) and (ii):: PEG is highly flexible and can be applied to online learning [Golowich et al., 2020a] or to the non-monotone variational inequalities [Daskalakis et al., 2018]. In contrast, EG with anchoring (EAG) [Yoon and Ryu, 2021]
It ==x² + 3x (x"
(x--x") -²x (z("") -h-1 = x² + 3x (x - x²) (Fx",,
(EAG)
where Be E (0,1) 1) is the anchoring coefficient, cannot be applied to online learning easily (EG/EAG are not no-regret [Golowich et al., 2020a]) and may not be desirable the non-monotone setting since it may make some "bad" stationary points attractive.?
Example 1.1. Let us consider a single example classification task with a deep linear neural network min (y- Wy W22 (2y)2//2)2222 = f(w). It has a undesirable stationary point w 00,0,0) 0). Because f²"("") = 0, for an initialization w close enough to w and any small enough stepsize, EAG will converge to w while PEG and EG will not, except for a zero measure set of initializations.
A further practical reason that renders "simple" methods (such as PEG and EG) attractive is that simple methods are typically adaptive to additional problem structure (better behavior than predicted by the analysis when the problem has beneficial additional properties). As an example, PEG converges sublinearly for monotone operator (this is the topic of this work) and linearly for strongly- monotone operators [Gidel et al., 2019a] under the same stepsize rules. This stands in sharp contrast with optimal methods, which require be tuned to the specific setting at hand (and in particular, which require the knowledge of the setting at hand).
2 A Path to the Proof
In this section, we show direct approach for assessing the worst-case convergence rate of the last iterate of PEG. The Lyapumov analyses provided in the next sections are grounded on the numerical results presented here. Whereas converting those numerical results into Lyapunov analysis is not direct, we believe that the material offers the comfortable privilege of a first clear (+//N) baseline for the further convergence results, as well as convenient approach for verifying Lyapunov functions.
This section contains our heuristic argument for concluding a O(/Nv) convergence of [[F() 1|2 for all F satisfying our assumptions. This ingredient was the main motivation behind the investigations of the next sections. In short, our goal is to
Verifying O(1/N) last-iterate convergence rate.
|[ [a 1="-="" I as a function of N when N is obtained from PEG.
characterize the worst-case behavior of For doing that, we rely on the so-called performance estimation framework introduced in [Drori
and Teboulle, 2]. That is, consider the problem of computing the worst-case value of [F(x )| | [|
(i.e.. the worst possible L-Lipschitz and monotone F, worst dimension d N, worst sequence of iterates x0 .....,,NN
, ,0 .......""'
...NNNN E Rd and worst solution xx E IRd to (VIP-U)):
|F(x>>> N&000 x+1 12
GrEa(7; L,N)=
max F.d.a"
(5)
s.t.
F is monotone and L-Lipschitz
a = x E Rd = x - Fxx
a = t - -F(("--) for 1: = 1,..., N.
x k+1 = x² -F((dt) for k = 1, 1,...,, N 1.
For example, stationary points x" such that Re(A) 2 -B, AA E Sp(VF(x")) become locally attractive as long as the anchoring coefficient Sr verifies 3. 2 B. which may correspond to an arbitrary long amount of time (see Example 1.1.)

---

Such problems are often referred to as Performance Estimation Problems (PEPs), Whereas it not clear how to solve this PEP (5), a few techniques from [Ryu et al., 2020, Taylor al.. 2017a] allow obtaining semidefinite relaxation providing meaningful worst-case bounds. By solving those problems numerically, we are able to conjecture that GPEG("; I,, N) ((/NN, as the convex relaxations provides upper bounds on GPEG which appear to behave in (+/NN) in numerical experiments. More precisely, the convex relaxation under consideration arises from sampled version of the previous problem (thereby passing from infinitedimmensional problem to a finiteddimensional one). In other words, we consider a sampled version of with g x F(**) and g R F( (so the variables will be the iterates and the operators values the iterates instead of the operator itself) and we require monotonicity and Lipschitzness to be satisfied at those points. For convenience, we define
the set of samples S {(x ()) U {(*" .gg.gg)) g)))]= U {(F". geg.gg))))) } S Rd x R':
)pec(y, N)
max dEN."* ER" ((e 1 CRixad ((2* . 1h-o CR"M
11g
(6)
s.t.
(g - h x - y) 20 (v. ES
(7)
llg hl 222 < 1 yll V(z, g). (y. E)
(8)
x0 X² E Rd, x² = g
x² x² 7タ -- for k: = 1, N,
k+1 = 2 79" for h:
11
|| x 112 1
(9)
(Note that classical homogeneity argument allows replacing the objective of (5) by l1g 112 plus
the constraint || - x²12 1; see, e.g.. [Ryu et al., 2020, $3.1.1.J.) In other words, we replace
the constraint corresponding to the existence of monotone L-Lipschitz operator F from (5) by === (3*h {g*)
the constraint that there exist sequences of points { (5* k= and
) k== such that they satisfy necessary conditions for the existence of monotone and I--Lipschitz operator F
interpolating them. Unfortunately, these constraints are not sufficient to ensure that there exists such monotone L-Lipschitz operator F [Ryu et al., 2020]. That is, we can guarantee only that Gpes(y, N) 2 GpEc(n, L, N).. Finallly, (pEC(?, L.N) can be computed numerically using semidefinite programming (SDP) through standard solvers [Mosek, 2010, Sturm, 1999]. For for- mulating the computation of ČpEG(7, N) as an SDP we first substitute a number of variables: notice that the objective and constraints of problem (6) are linear functions of all possible inner products
N {x*) 1== and { k= linear combinations of æ² [ Ik=o 1 1==1- Next,
of vectors from def (x*,2",0 l.g.g..... ................... g2 ......g.......... MM, That is, problem (6) is linear w.r.t.
the elements of Gram matrix G V 2 (we use the notation G $2N+3 for denoting (2N + 3) x (2N + 3) symmetric positive semidefinite matrices). The problem also naturally features the constraint rank(G) S 2N + 3, which becomes void due to maximization over the dimension d
in (6) (see, e.g., [Taylor et al., 2017c, Theorem 5)) and the GpEa(T, L, N) can therefore be computed by solving standard SDP:
GPeo(T,L, L,N)
max GER
Gr(M,
(10)
s.t.
() < 0 for i i 1,,...,,,,((2,, + 1) +1, Tr(M_, G) 1
where (M, ( 21(2N+1)-- are symmetric matrices encoding the objective and constraints from (6)- For compactness, we omit the exact formulas for these matrices and refer to the examples for different PEPs from, e.g., [Ryu et al., 2020, Gorbunov et al., 2021].
By solving (10) numerically, we empirically observe that GpEa(y, N) = O(/x) for different choices of y, see Fig. la. Taking into account the lower bound Gpgc (7. L, N) = Q(/x)) from Golowich et al. [2020a] we conclude that it is very likely that [[ )]( ~ I/N for the values of y and N under consideration. Of course, this observation not a rigorous mathematical proof for the (1/N)) last-iterate convergence of PEG for two main reasons: (i) the SDP solver only outputs approximate SDP certificates (though highly accurate), and (ii) even by using exact SDP solvers (see, e.g., Henrion et al. [2016]), the worst-case bounds would only be valid for the values of the
5

---

10
Greakt.L.k L.k)
10"
Grsllt 1.k.
Goolă: L.11)
10
10
(.g-6.8)
4g...
Guilt L.8)
6.
10-
(.K)
Gool L.
10-5
0lg L.R.
10
10-2
01g
10
20 30
(a) PEPs GpEC and GoG.
(b) PEPs with distance-t constraints
(c) Sq. norm differences
Figure 1: In (a), we report GpEC(Y, I, and GoG(7. L, NN for different values of y and N. In both cases, observe O(1/N) convergence. In (b), report GpEG L, N, W 1) and Goa(y, L,N, for 1,2,4. suggest that GpEG(y, L, 1) ~ 1/N but GoG(7, L, N), (even for t 4). Finally, (c) shows how ( L, N); ((7 ; I, N), ((7, I, N), 0(7, L, N) evolve as grows.
parameters that were tried numerically; in particular, we only solved the SDPs for a few values of N. To translate those into rigorous worst-case bounds that are valid beyond the numerical trials, our goal identify feasible solution to the dual problem to (10) (each of those dual solutions corresponds to a valid upper bound on GPEC L, N), and thereby also on GpEG (7; I,, N)). One can find examples of such dual certificates in, e.g., [De Klerk et al., 2017, Taylor et al., 2017a].
relatively simple to verify that PEG and OG are equivalent [Gidel et al., 2019a, Hsieh et al., 2019]. Moreover, OG can be seen simplified version of PEG since OG explicitly uses only one sequence of points, while PEG relies on two sequences. As for PEG, one consider PEP for OG:
Why do we use PEG form instead of OG form?
F ( )1
Co
max F.d.z
(11)
1
s.t.
monotone and I.-Lipschitz,
2 R 5² = 00 (z)),
gk+1= = = FT +=F((*=)) for k 1 1,
as well as its sampled version and the corresponding SDP relaxation, denoted by Goo(y, L, N).. Because its sampled version naturally contains only samples of the iterates (7* k== the corre- sponding SDP has about 4 times less constraints than (10) (recall that (10) also involves Lipschitz and monotonicity inequalities with the iterates { ) As for GpEc(y, L, N). one also compute Goc(1, L, .)) numerically using SDP solvers, see Fig. la. Those numerical results also suggest that Goo(T, N) = O(/N)) for the different choices of y provided in Fig. la, and GpEa(?, L, .N and Goaln, L, .) are close each other for the set of parameters under consideration. Finally, due the fact that the SDP formulation of GoG(T, N. involves less constraints than that of GpEc (7, L, N) while providing very similar results, one might expect that studying Goo(7, L. might be simpler.
Convergence proofs of classical first-order optimization methods generally rely on clever combina- tions of inequalities characterizing the class of problems hand, and the algorithm. Those inequalities typically involve consecutive iterates and/or a solution x² to the variational problem. For finding (hopefully) simple proof, let us introduce a few relaxations of (7, L, N) and GoG(7, L, N), parameterized by some N and respecitvely denoted by GPEC(Y, L, N, t) and Goo (7, N, Those values respectively correspond to the optimal values of the respective SDP formulations of OPEG and GoG where we removed all constraints corresponding pairs of iterates (i,j) with | L. We refer to the remaining constraints as distance-l constraints. For example, distance-1 constraints involve monotonicity and Lipschitzness inequalities between two consecutive iterates as well as between the iterates and the solution x" under consideration. As provided by Fig. 1b, solving the corresponding SDPs for PEG and OG numerically, we observe that GpEa(T, L, N, I/N, but the value of Goc(n, N, seem stall after few iterations. This experiment suggests

---

necessity of using the values of F evaluated at {a* 1k20 for obtaining "simple" proofs involving only inequalities with consecutive iterates.
The norm does not decrease monotonically. Previous numerical experiments suggest that there exist proof of ((/N)) last-iterate convergence of PEG which uses only inequalities involving consecutive iterates and x²" However, the problem of finding the proof remains somehow involved and we did not manage to find analytical expressions (as functions of 7. I., and N) to the dual SDP
formulation ( L, N, 1). Therefore, the following lines aim at finding appropriate Lyapunov function, that is, even looser upper bounds on GPEG L, .N). As a starting point, is shown in [Gorbunov et al., 2021] ]] that the extragradient method (EG) satisfies [[](*++)]|] S FIF((*)) )[² for all & 2 0 and all monotone Lipschitz operator F. Since EG and PEG are very similar methods, it is natural to check whether the same inequality holds for PEG. One way to verify whether this incquality holds is to check nonpositivity of the following PEP:
F N )1 ||1 [F(x )1?
max F,d,a"
1,000
1
(12)
29
s.t.
F is monotone and L-Liscchitz
20 = x E ERd, x¹ = x² - -FF(x²), z = x² -TF((T for k = ,,...,N, N,
x g+l = =x² -F("",, for k = I,..., N 1,
through its SDP relaxation, whose value is denoted by A(7, L, N).. A similar SDP can be formulated for the objective |F(**)] - || - 1) and we denote its corresponding optimal value by NN). For convenience, we also define two corresponding SDP formulation whose optimal values are denoted by 5(1; N) and 0(7, N) and which corresponds respectively the SDP formulations of A1,, L, N) and (17,
NN) where the Lipschitz and monotonicity constraints are replaced by cocoercivity (i.e., (g - h, x y) 2 O and l h11² < 1.2 yl are replaced by Igg h12 < Líg h y))- Cocoercive operators are both Lipschitz and monotone, and one advantageous property of 5(7, I, N) and ö(7, I,, N) is that they are guaranteed to be "tight". That is, one can construct operators matching the numerical values of respectively ([(=**")]2-|[PCCC
and
1PG**11R--IFE"" obtained from the SDPs, see [Ryu et al., 2020, Proposition 2]. Therefore 110-==11"
positive value for 8(7, N) (resp. 8(7 L, N)) implies the existence of some L-Lipschitz monotone [x N IIl (resp. [F [[]]+++)] > |F(EN))13) Therefore, Fig. lc allows concluding that ||F(s> )12 (resp. || )l1 not decreasing function of N in general.
F' satisfying 11F(x*+1)1)
This fact highlights the difference between EG and PEG in terms of the analysis. However, this experiment also suggests that A(y, N) is decreasing function of N (for some values of 7).
Therefore, although [|= is not a decreasing function of N for all monotone L-Lipschitz operator F' and all starting point Ho E Rd, appears that the difference || -1 (==>> decrease to zero (for all starting point and all operator F' satisfying
assumptions) as N grows. Those numerical results suggest that there is a chance to find a non-negative sequence (Av N20 for which || [[ + AN < ||(x>>)] + AN. To discover such a sequence, we carefully studied the numerical values of the solutions to the dual SDP for different values of and N and tried to infer some structure from them. The following section reports the positive results in that direction.
3 Last Iterate Convergence of PEG in the Unconstrained Case
The technique described in the previous section allowed performing educated trial and error procedure, searching for appropriate potential functions. We finally found suitable candidate Ay. In particular, one can numerically check that |[ F
)|2 < [[F(x ) F(x DF F(=N-1) I]I for all monotone L-Lipschitz F for all tested values of and 7 S v2/3t.. Using the few nonzero dual variables for the problem of verifying this potential function
allows reaching the desired proof after bit of manual cleaning.
7

---

Lemma 3.1. Under Assumption 1, the iterates of PEG with > 0 satisfy for any k > 0.
|[ - 1F 21 F211F(z*) 1(1
2 2/1
+3 L2n2 9) |IF( F( (13)
We notice that the last term is non-positive for 0 < S v2/3L.
Proof. Since F is monotone and L-Lipschitz, we have
s (F(xht1) F F(x*=()))))))))))))) ), .ha x²),
[[ F( S 1.21 8² 1|?
By definition of *+1 and 7h we have gh+1 x = -FF(Tt) and x k+1 -tt x -
x² + +yf(E*=1) = (F(**11)- - F( )) Plugging these relations to the above inequalities and
dividing the first inequality by y, get
F(E)),
) I L'-7111((2") - (i*--))l²
Next, we sum up the above inequalities with weights a = and X = 3 respectively:
3|| [(s -
12
< 2(P(x*) F(x F(**)) + +3. F(
(2m
Rearranging the terms, derive
|F + )1 - 21 F( <
( )(
+3L -
(14)
To estimate the negative term from the right-hand side of the above inequality we use that - ||a
(22)
b1l2 I 1|ll + ||] with a = F(3h) - F( 1), F(x*) F( and a = 1/2:
2 - +2 F
- -(( <
Plugging the above inequality in (14), we obtain
+ 21[F(( )( s ||F(5b)|2 - -F(
+3 1222 9 -
which finishes the proof.
Using this lemma we then show the last-iterate convergence rate of PEG. Theorem 1. Let operator F be monotone and L-Lipschitz. Then for all 2 0 the iterates of PEG with I 1/3l satisfy PR+1 &g with Q2 defined as
1: +
Φb = 1| x²1
72
-F(
(15)
3
In particular, for all N 2 O and 7 S 1/3t. the above formula implies
[F 3(1 222 112
2 2 3212 + x"
(app(a*)) <
(16)
?N + +2)
TV3N + 96
8

---

As we write before, in contrast to Golowich et al. [2020a], our results does not rely on the Lips- chitzness of (x))). Moreover, even when (=) assumed to be A-Lisschitz, our result improve upon Golowich et al. [2020a] in certain regimes. In particular, if A || - x=' > I,, which is typically the case (e.g., see Appendix from Gorbunov et al. [2021] for the details), the constants in our upper bounds are significantly smaller and even when A A|z x=1 < I. our result allows for stepsizes 50 times larger with improvement by a factor ~ 10 in terms of convergence rate for [F((z))]
Next, our analysis significantly differs from the previous known one from Golowich et al. [2020a].
In particular, using Lipschitzness of Jacobian, Golowich et al. [2020a] derive that |F( )1² is not
much larger than mink=0.....>> [1F((=) which instantly implics a (1/N)) last-iterate convergence rate after applying standard results for the best-iterate convergence of PEG. In contrast, we do not derive any connections between the best and the last iterates of PEG and directly rely on the fact that [[F()*) 2| ((*)) - F(z*-3 1)12 is decreasing function of k. i... on Lemma 3.1.
We also remark that the derived upper bounds are worse than those that we obtained numerically and reported in Fig. la. For example, when N = 50 and from Theorem is R 20 times worse than the upper bound found numerically. Since our goal was in deriving simple proof of the ((/N)) rate, we did not try to improve the multiplicative constants in the final results. We also do not plot the curve corresponding to the upper bound on || [xx )|? from Theorem for the sake of readability of Fig. la.
1/3L the upper bound on [I
4 Last Iterate Convergence of PEG in the Constrained Case
In this section, we extend the last-iterate convergence rates proven in Theorem to the constrained case. Such an extension is not straightforward because the convergence criterion considered in the unconstrained case cannot be used anymore in the constrained case. That is, Lemma 3.1 is not valid anymore and cannot be easily adapted to the constrained case: norm of the operator [=4"(=>"]| does not necessarily converge to zero since F(x*) J in general. However, to find new potential function we used the same techniques in the unconstrained case. This search led us to the following result.
Lemma 4.1. Under Assumption 1, the iterates of Proj-PEG with > O satisfy for any k > 0,
V 1+11 V/ (1 5L | - 101 - -211 F1
(17)
where v =1|x* 111 + | - (z(()= F F 1)1
Proof sketch. Numerically we discovered that to prove this result it is sufficient to sum up constraints corresponding to the monotonicity at (a* x*+1), Lipschitzness at (z*++1 ,,²),, and projections prop- erties 8 for the pairs (I.+11, ,x*), (ar _*+1), (a+, ,,a), (**,,***) a.*1),, with weights 4y, 5,, 4,, 2, 2, 2 re-
spectively. After that, it remains to rearrange the terms and apply standard inequalities from Appendix A to derive the result. See the detailed proof in Appendix C.
This lemma is critically different from Lemma 3.1 since in the unconstrained case the potential from Lemma 4.1 reduces to VA |F( + [[ (=x((=²)) one can see from the next result, using the potential from Lemma 4.1, we obtain the proof valid for slightly smaller stepsize than in the unconstrained case (see also Appendix D for the numerical verification of the rate).
F((+-1))112 Moreover, as
Theorem 2. Under Assumption I, the iterates of Proj- with y S 1/41. satisfy Φx+1 S $ k2 2 with Ty defined as
1
3k 32
2 = || - x
c 7² - 2112
(18)
16
24
where VR = 1|a.k - x 1 + ||a* -
- -2x(F(x")) - -( In particular, it implies
24H2 (app(x²) 8v3Ho.1
Ho
|1.. x 1112 _ 3NN + 32'
VA 2,
(19)
T/3N +32
where
Ho, Ho, > are such that H2
2(1 + 3x2L² + 4~AL0)
111
41 + 19 122212) 72 [1 H3 = 3 x= 12 3012
1 F )12
I2
By projection property for the pair (x+, 4). where x+ proj]æ]. y X, we mean (I- 2+,y x+)=00 5.

---

This result extends last-iterate convergence of Proj-PEG to the constrained case. The closest result in the literature is Cai al. [2022. Theorem 3] that gives a last-iterate convergence result for EG in terms of the tangent residual and gap function. Moreover, we show (1/NN) last-iterate convergence result for the residuals, which is stronger than the result in Cai et [2022, Theorem 3]. Moreover, our results justify that higher-order SOS programs (with polynomials of degree larger than 2) used by Cai et al. [2022] are not required to derive tight last-iterate convergence results for Proj-PEG. We believe that this is the case for other EG-like methods and similar rates could be proven for the residuals of these methods as well (see Appendix D for preliminary results supporting this claim).
5 Discussion
In this work, we leveraged the performance estimation problem framework to show the last-iterate convergence PEG of monotone and Lipschitz operators both in the constrained and unconstrained cases. These results answer some important questions that remained open until now in the variational inequality literature showeasing the appealing properties of extrapolation-Be -aaoed methods. However, important open questions remain such as last-iterate convergence rates for stochastic methods for monotone and Lipschitz variational inequalities or a better understanding of the dynamics in non- monotone cases that occur in machine learning applications. Finally, the results obtained for PEG this work have worse multiplicative constants and more restrictive range stepsizes than those obtained for EG Gorbunov et al. [2021], Cai et al. [2022]. It would be interesting to address this discrepancy in the future work.
Acknowledgments and Disclosure of Funding
The authors would like to warmly thank Sylvain Sorin for spotting typo in Appendix C, as well as for few suggestions of improvements.
This work was partially supported by a grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000D733331P$50000) and the agreement with the Moscow Institute of Physies and Technology dated November 1, 2021 No. 70-2021-000 10122100135 A. Taylor acknowledges support from the French "Agence Nationale de la Recherche" as part of the "Investissements d' avviir" program, reference ANR- INR-19-P3IA-0001 (PRAIRIE 31A Institute), well as support from the European Research Council (grant SEQUOIA 724063).
References
Abernethy, K. A. Lai, and A. Wibisono. Last-iterate convergence rates for min-max optimization. arXiv preprint 1906.0207. 2019. (Cited on page 3)
I. Anagnostides, I. Panageas, G. Farina, and T. Sandholm. On last-iterate convergence beyond zero-sum games. arXiv preprint arXiv:2203. /2056, 2022. (Cited on page 4)
W. Azizian, Mitliagkas, S. Lacoste-Julien, and G. Gidel. tight and unified analysis of gradient- based methods for whole spectrum of differentiable games. In International Conference on Artificial Intelligence and Statistics, pages 2863-2873. PMLR, 2020a. (Cited on page 3)
W. Azizian, D. Scieur, I. Mitliagkas, S. Lacoste-Julien, and G. Gidel. Accelerating smooth games by manipulating spectral shapes. In International Conference on Artificial Intelligence and Statistics. PMLR, 2020b. (Cited page 3)
A. Ben-Tal L. El Ghaoui, and A. Nemirovski. Robust optimization. Princeton university press, 2009. (Cited on page 1)
N. Brown and T. Sandholm. Solving imperfecttinffomaaiion games via discounted regret minimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1829-1836. 2019. (Cited page 4)
Y. Cai, A. Oikonomou, and W. Zheng. Tight last-iterate convergence of the extragradient method for constrained monotone variational inequalities. arXiv preprint arXiv:2204 09228 version 1, 2022. (Cited on pages and 10)
10

---

C. Daskalakis. A. Ilyas, V. Syrgkanis, and H. Zeng. Training gans with optimism. In International Conference on Learning Representations, 2018. (Cited on pages 3 and 4)
E. De Klerk, F. Glineur, and A. B. Taylor. On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions. Optimization Letters, 11(7):1 18:-11888999, 2017. (Cited page 6)
J. Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions variational inequalities. In Conference on Learning Theory. PMLR, 2020. (Cited on pages 3 and 4)
Y. Drori and M. Teboulle, Performance first-order methods for smooth convex minimization: a novel approach. Mathematical Programming, 145(1):451-42,, 2014. (Cited pages 2 and 4)
F. Facchinei and J.-S. Pang. Finite-dimensional variational inequalities and complementarity prob- lems. Springer, 2003. (Cited on page
G. Farina, C. Kroer, N. Brown, and T. Sandholm. Stable-predictive optimistic counterfactual regret minimization. In International conference on machine learning. pages 1853-1862. PMLR, 2019. (Cited on page
G. Gidel, H. Berard, P. Vincent, and S. Lacoste-Julien.
variational inequality perspective on generative adversarial nets. In ICLR, 2019a. (Cited on pages 3, and 14)
G. Gidel, R. A. Hemmat, M. Pezeshki, R. Le Priol, G. Huang. S. Lacoste-Julien, and I. Mitliagkas. Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1802-1811. PMLR, 2019b. (Cited on page 3)
N. Golowich, S. Pattathil, and C. Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. arXiv preprint arXiv:2010. 13724, 2020a. (Cited pages 1, 3, 4, and 9)
N. Golowich, S. Pattathil, C. Daskalakis, and A. Ozdaglar. Last iterate is slower than averaged iterate in smooth convex-concave saddle point problems. In Conference on Learning Theory, pages 1758-1784. PMLR, 2020b. (Cited on page 3)
I. Goodfellow, J. Fouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. Advances neural information processing systems, 27, 2014. (Cited page 1)
J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and harnessing adversarial examples. ICLR 2015, 2015. (Cited page 1)
E. Gorbunov, N. Loizou, and G. Gidel. Extragradient method: 0(1/k) last-iterate conver- gence for monotone variational inequalities and connections with cocoercivity. arXiv preprint arXiv:21 2021. (Cited on pages 5, 9, and 10)
B. Goujaud, C. Moucer, F. Glineur, J. Hendrickx, A. Taylor, and A. Dieuleveut. Pepit: computer- assisted worst-case analyses of first-order optimization methods in python. arXiv preprint MxXiv:2011.44400 2022. (Cited on page 2)
B. Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathematical Society, 1967. (Cited on page 3)
M. Hast, K. Åström, B. Bernhardsson, and Boyd. Pid design by convex-conee optimization. In 2013 European Control Conference (ECC), pages 4460-4465. IEEE, 2013. (Cited page 1)
D. Henrion, S. Naldi, and M. S. El Din. Exact algorithms for linear matrix inequalities. SIAM Journal Optimization, 26(4):2512-2599 2016. (Cited on page
Y.-G. Hsich, F. Iutzeler, J. Malick, and P. Mertikopoulos. On the convergence of single-call stochastic extra- gradiegt methods. Advances Neural Information Processing Systems, 32:6938 1116938-6948,,, 2019. (Cited on pages 2, 3, 6, and 21)
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976. (Cited on page 2)
J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization, 2001. (Cited on page 2)
S. Lee and D. Kim. Fast extra gradient methods for smooth structured noncomvex-nonconccan minimax problems. Advances in Neural Information Processing Systems, 34, 2021. (Cited on pages and 4)
11

---

T. Liang and J. Stokes. Interaction matters: A note on non nonmasymti local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 907-915. PMIR, 2019. (Cited on page 3)
J. Lofberg. Yalmip: A toolbox for modeling and optimization in matlab. In 2004 IEEE international conference on robotics and automation (IEEE Cat. No. 04CH37508), pages 284-289. IEEE, 2004. (Cited on page 2)
N. Loizou, H. Berard, A. Jolicoeur-Martineau P. Vincent, S. Lacoste-Julien, and I. Mitliagkas. Stochastic hamiltonian gradient methods for smooth games. In International Conference on Machine Learning, pages 6370-6381. PMLR, 2020. (Cited on page 3)
A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. Towards deep learning models resistant to adversarial attacks. ICLR 2018, 2018. (Cited page 1)
A. Mokhtari, A. Ozdaglar, and S. Pattathil. Proximal point approximations achieving a convergence rate of ( for smooth convex-concavee saddle point problems: Optimistic gradient and extra- gradient methods. arXiv preprint arXiv:/906.0// 15, 2019. (Cited on page 3)
A. Mosek. The MOSEK optimization software, 2010. URL http: //wp: hwtp:///wwwwo...k..//////////..e com. (Cited on page 5)
Y. Nesterov. Squared functional systems and optimization problems. In High performance optimiza- tion, pages 405-440. Springer, 2000. (Cited on page 2)
Y. Nesterov. Dual extrapolation and its applications to solving variational incqualities and related problems. Mathematical Programming, 109(2):3193344, 2007. (Cited on page 2)
P. A. Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. California Institute of Technology, 2000. (Cited on page 2)
W. Peng, Y.-H. Dai, H. Zhang, and L. Cheng. Training gans with centripetal acceleration. Optimization Methods and Software, 35(5):555-973, 2020. (Cited on page 3)
L. D. Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, (8(5):8458445 1980. (Cited on pages 1 and 2)
E. K. Ryu, A. B. Taylor, C. Bergeling, and P. Giselsson. Operator splitting performance estimation: Tight contraction factors and optimal parameter selection. SIAM Journal on Optimization, 30(3):
2251-2271, 2020. (Cited pages 5 and 7)
N. Z. Shor. An approach to obtaining global extremums in polynomial mathematical programming problems. Cybernetics, 1987. (Cited on page 2)
J. F. Sturm. Using sedumi 1.02, MATLAB toolbox for optimization over symmetric cones.
Optimization Methods and Software, 11(1-4):65-6533 1999. doi: 10. 10.188/00056789900007766
URL https: http:::///ooooo///////// wot./oo///10/.. 1980/0056789988007666 (Cited on page 5)
A. B. Taylor, J. M. Hendrickx, and F. Glineur. Exact worst-case performance of first-order methods for composite convex optimization. SIAM Journal on Optimization, 27(3): ((13):1283-313, Jan 2017a.
ISSN 1095-7189, (Cited on pages 5 and 6)
A. B. Taylor, J. M. Hendrickx, and F. Glineur. Performance estimation toolbox (pesto): automated worst-case analysis of first-order optimization methods. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages
IEEE, 2017b. (Cited on pages 2 and 21)
A. B. Taylor, J. M. Hendrickx, and F. Glineur. Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Mathematical Programming, (1)300337334 2017c. (Cited on pages? 2 and 5)
Q. Tran-Dinh. The connection between nesterov's 's accelerated methods and halpern fixed- fixed-point iterations. arXiv preprint arXiv:2203.04866) 2022. (Cited on page 4)
Tran-Dinh and Y. Luo. Halpern-type accelerated and splitting algorithms for monotone inclusions. arXiv preprini arXiv:21 00.08/50 2021. (Cited on page 4)
Tseng. On linear convergence of iterative methods for the variational incquality problem. Journal of Computational and Applied Mathematics, 6011-2):237-252, 1995. (Cited on page 3)
T. Yoon and F. K. Ryu. Accelerated algorithms for smooth convex-concave minimax problems with O ) rate on squared gradient norm. In International Conference on Machine Learning, pages 12098-12100 PMLR, 2021. (Cited on pages 3 and 4)
12

---

G. Zhang and Y. Yu. Convergence of gradient methods on bilinear zero-sum games, In International Conference on Learning Representations, 2020. (Cited on page 3)
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See $1 and $5
(C) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [N/A]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See $1, $3, and $4
(b) Did you include complete proofs of all theoretical results? [Yes]] See $3 and Appen- dices B and
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] Codes are publicly available:
//gp:://githulll wtt./coom//ceeeeeee /etuuurdggrbbbooo/ptttttt.tl and_
last fast_iter_stt httttterccooergenneeeeeeeeeeeeee SaarrrennneeeeePPee_eeee VIPss
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/relcasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals. if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "XvnP49mAgO9", "reviewer": "Reviewer_DFRa", "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. \n\nThe 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. \n\nI 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. \n\n", "questions": "See comment above on comparison to EG. ", "limitations": "NA", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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. \n\nOne 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. \n\nTypo: Line 188, there should be no tilde on top of G_PEG and G_OG.  \n\nAdditional 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GUYs_1Qt3T", "reviewer": "Reviewer_NX5e", "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.", "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.\n- Are the derived bounds close to the exact rate bounds (found by PEP)?\n\n", "limitations": "Yes, the authors mentioned extensions to stochastic and non-monotone cases.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- 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.\n- Example 1.1: an interesting example that supports this paper's further study on PEG over recent developments on accelerated EG methods.\n- 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.\n- 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.\n**Weaknesses**\n- Somewhat similar results on EG are recently found in [Cai et al., 2022]\n- Lack of intuition and explanation on two different potential functions, especially the one for the constrained case.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7XTzTrLyLg", "reviewer": "Reviewer_r8QB", "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. ", "questions": "1- It seems that this paper already sovled this problem with similar assumptions: \n“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. \n\n2- 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. \n\n3- In Line 238 it should be non-positive.  \n", "limitations": "This works addresses the potential social impacts. \n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Clarity\n\nThe 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. \n\nOriginality\n\nLast 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. \n \n \nQuality\n\nAll the proofs presented were correct and sound. The paper is a theoretical mainly however their experimental result in appendix D is not explained well. \n \n\nSignificance\n\nLast iterate convergence is important since in practice the last iterate is usually used as the final result not the averaged one. \n\nLimitation\n\nThe 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. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept