Accelerated Single-Call Methods for Constrained Min-Max Optimization
Authors: Yang Cai
Weiqiang Zheng
Venue: ICLR 2023 poster (2023)
Keywords: min-max optimization
nonconvex-nonconcave
variational inequalities
saddle point problem
first-order method

Abstract: We study first-order methods for constrained min-max optimization. Existing methods either require two gradient calls or two projections in each iteration, which may be costly in some applications. In this paper, we first show that a variant of the \emph{Optimistic Gradient (OG)} method, a \emph{single-call single-projection} algorithm,  has $O(\frac{1}{\sqrt{T}})$ best-iterate convergence rate for inclusion problems with operators that satisfy the weak Minty variation inequality (MVI). Our second result is the first single-call single-projection algorithm -- the \emph{Accelerated Reflected Gradient (ARG)} method that achieves the \emph{optimal $O(\frac{1}{T})$} last-iterate convergence rate for inclusion problems that satisfy negative comonotonicity. Both the weak MVI and negative comonotonicity are well-studied assumptions and capture a rich set of non-convex non-concave min-max optimization problems. Finally, we show that the \emph{Reflected Gradient (RG)} method, another \emph{single-call single-projection} algorithm,  has $O(\frac{1}{\sqrt{T}})$ last-iterate convergence rate for constrained convex-concave min-max optimization, answering an open problem of [Hsieh et al., 2019]. Our convergence rates hold for standard measures such as the tangent residual and the natural residual. 

Published as a conference paper at ICLR 2023
ACCELERATED SINGLE-CALL METHODS FOR CON- STRAINED MIN-MAX OPTIMIZATION
Yang Cai
Weiqiang Zheng
Yale University yang. , cai caigyale.edu
Yale University weigiang. zhengeyale.edu
ABSTRACT
We study first-order methods for constrained min-max optimization. Ex- isting methods either require two gradient calls or two projections in each iteration, which may be costly in some applications. In this paper, we first show that a variant of the Optimistic Gradient (OG) method, a single- call single-projection algorithm, has O (()) best-iterate convergence rate for inclusion problems with operators that satisfy the weak Minty vari- ation inequality (MVT). Our second result is the first single-call single- projection algorithm the Accelerated Reflected Gradient (ARG) method that achieves the optimal O(7) last-iterate convergence rate for inclu- sion problems that satisfy negative comonotonicity. Both the weak MVI and negative comonotonicity are well-studied assumptions and capture a rich set of non-convex non-concave min-max optimization problems. Fi- nally, we show that the Reflected Gradient (RG) method, another single-call single-projection algorithm, has O + last-iterate convergence rate for con- strained convex-concave min-max optimization, answering open prob- lem of (Hsieh et al., 2019). Our convergence rates hold for standard mea- sures such as the tangent residual and the natural residual.
INTRODUCTION
Various Machine Learning applications, from the generative adversarial networks (GANs) (e.g., (Goodfellow et al., 2014; Arjovsky et al., 2017)), adversarial examples (e-g,, (Madry et al., 2017)), robust optimization (e.g., (Ben-Tal et al., 2009)), to reinforcement learning (e.g., (Du et al., 2017; Dai et al., 2018)), can be captured by constrained min-max optimiza- tion. Unlike the well-behaved convex-concave setting, these modern ML applications often require solving non-convex non-concave min-max optimization problems in high dimen- sional spaces.
Unfortunately, the general non-convex non-concave setting is intractable even for com- puting a local solution (Hirsch et al., 1989; Papadimitriou, 1994; Daskalakis et al., 2021). Motivated by the intractability, researchers turn their attention to non-convex non-concave settings with structure. Significant progress has been made for several interesting structured non-convex non-concave settings, such as the ones that satisfy the weak Minty variation inequality (MVI) (Definition 2) (Diakonikolas et al., 2021; Pethick et al., 2022) and the ones that satisfy the more strict negatively comonotone condition (Definition 3) (Lee & Kim, 2021a; Cai et al., 2022a). These algorithms are variations of the celebrated extragradient (EG) method (Korpelevich, 1976), an iterative first-order method. Similar to the extragra- dient method, these algorithms all require two oracle calls per iteration, which may be costly in practice. We investigate the following important question in this paper:
Can design efficient single-call first-order methods for structured non-convex non-concave min-max optimization?
We provide an affirmative answer to the question. We first show that a single-call method known as the Optimistic Gradient (OG) method (Hsieh al., 2019) is applicable to all non-

---

Published as a conference paper at ICLR 2023
convex non-concave settings that satisfy the weak MVI. We then provide the Accelerated Re- flected Gradient (ARG) method that achieves the optimal convergence rate in all non-convex non-concave settings that satisfy the negatively comonotone condition. Single-call methods have been studied in the convex-concave settings (Hsieh et al., 2019) but not for the more general non-convex non-concave settings. See Table for comparisons between our algo- rithms and other algorithms from the literature.
Non-Monotone
Algorithm
1-Call?
Constraints?
Comonotone
weak MVT
Normal
EG+ (Diakonikolas et al., 2021)
x
x
0 +
0
CHG+ (Pethick et al., 2022)
x
/
((+))
0
OGDA (Böhm, 2022; Bot et al,, 2022)
/
x
0
0(
OG|this paper]
/
/
0
O
FEG (Lee Kim, 2021b)
x
0(+)
Accelerated
AS (Cai et al., 2022a)
X
0(+)
ARG [This paper]
0(+)
Table 1: Existing results for min-max optimization problem with non-monotone operators. A / in "Constraints?" means the algorithm works in the constrained setting. The conver- gence rate is in terms of the operator norm (in the unconstrained setting) and the residual (in the constrained setting).
1.1 OUR CONTRIBUTIONS
Throughout the paper, we adopt the more general and abstract framework of inclusion problems, which includes constrained min-max optimization as special case. More specif- ically, we consider the following problem.
Inclusion Problem. Given E F + A where F RR" - R" is single-valued (possibly
non-monotone) operator and A : RR = IR" is a set-valued maximally monotone operator, the inclusion problem defined as follows
find z" E such that E E(z") F(=*)+ A(z)).
(IP)
As shown in the following example, we can interpret a min-max optimization problem as an inclusion problem.
Example 1 (Min-Max Optimization). The following structured min-max optimization problem captures a wide range of applications machine learning such as GANs, adversarial examples, robust optimization, and reinforcement learning:
min max f(x,y) + g(x) - -h(y), Re yER."
(1)
where -(,,-) is possibly non-convex in x and non-concave in Regularized and constrained min- max problems are covered by appropriate choices of lower semi-continuous and convex functions g and h. Examples include the n-norm, the fz-norm, and the indicator function of closed convex fea- sible set. Lei z = (x, if we define F(z) = (dx (x, -dyf (x, (x,y) y)) and A(z) (dg(x), al(y)) ). where A is maximally monotone, then the first- optimality condition of (1) has the form of an inclusion problem.
(Daskalakis et al., 2021) shows that without any assumption on the operator E = F A, the problem is intractable.' The most well understood setting is when is monotone, ie., (u 0,2 - z²) > 0 for all z, and и E E(z), e E(z'), which captures convex-concave min-max optimization. Motivated by non-convex non-concave min-max optimization, we consider the two most widely studied families of non-monotone operators: (i) negatively
Indeed, even if A is maximally monotone, (Daskalakis et al., 2021) implies that the problem is still intractable without further assumptions F.
2

---

Published as a conference paper at ICLR 2023
comonotone operators and (ii) operators that satisfy the less restrictive weak MVI. See Sec- tion 2 for more detailed discussion on their relationship. Here are the main contributions of this paper.
We provide extension of the Optimistic Gradient (OG) method for inclusion problems when the operator E F + A satisfies the weak MVI. More specifically, we prove that OG has a O र convergence rate (Theorem 1) matching the state of the art algorithms (Diakonikolas et al., 2021; Pethick et al., 2022). Impor- tantly, our algorithm only requires a single oracle call to F and single call to the resolvent A.
Contribution 1:
"The resolvent of A is defined (I A)-1. When is the subdifferential of the indicator function of closed convex set, the resolvent operator is exactly the Euclidean projection. Hence our algorithm performs a single projection in the constrained case.
Next, we provide accelerated single-call method when the operator satisfies the stronger negatively comonotone condition.
We design an accelerated version of the Reflected Gradient (RG) (Chambolle & Pock, 2011; Malitsky, 2015; Cui & Shanbhag, 2016; Hsieh et al., 2019) method that we call the Accelerated Reflected Gradient (ARG) method, which has the optimal 0(+) convergence rate for inclusion problems whose operators
Contribution 2:
E = F + A are negatively comonotone (Theorem 2). Note that ((+) is the opti- mal convergence rate for any first-order methods even for monotone inclusion prob- lems (Diakonikolas, 2020; Yoon & Ryu, 2021). Importantly, ARG only requires single oracle call to F and a single call to the resolvent of A.
Finally, we resolve an open question from (Hsieh et al., 2019).
Contribution 3: We show that the Reflected Gradient (RG) method has last-iterate convergence rate of O 1) for constrained convex-concave min-max optimization (Theorem 3). Hsieh et al. (2019) show that the RG algorithm asymptotically con- verges but fails to obtain a concrete rate. We strengthen their result to obtain a tight finite convergence rate for RG.
VT
We also provide illustrative numerical experiments in Appendix E.
1.2
RELATED WORKS
We provide brief discussion of the most relevant and recent results nonconvex- nonconcave min-max optimization here and defer the discussion on related results the convex-concave setting to Appendix A. We also refer readers to (Facchinei & Pang, 2003; Bauschke & Combettes, 2011; Ryu & Yin, 2022) and references therein for a comprehensive literature review inclusion problems and related variational inequality problems.
Structured Nonconvex-Nonconaave Min-Max Optimization. Since in general nonconvex-nonconcatt min-max optimization problems are intractable, recent works study problems under additional assumptions. The Minty variational inequality (MVT) assumption (also called coherence or variational stability), which covers all quasiconvex- concave and starconvex-concave problems, is well-studied e.g. (Dang & Lan, 2015; Zhou et al., 2017; Liu et al., 2019; Malitsky, 2020; Song et al., 2020; Liu et al., 2021). Extragradient-type algorithms has O VT) MVI (Dang & Lan, 2015).
convergence rate for problems that satisfies
Diakonikolas al. (2021) proposes a weaker assumption called weak MVI, which includes both MVI or negative comonotonicity (Bauschke et al., 2021) special cases. Under the weak MVI, the EG+ (Diakonikolas al., 2021) and OGDA+ (Böhm, 2022) algorithms have O convergence rate in the unconstrained setting. Recently, Pethick et al. (2022) gen-
3

---

Published as a conference paper at ICLR 2023
eralizes EG+ to CEG+ algorithm, achieving the same convergence rate in the general (con- strained) setting. To the best of our knowledge, the OG algorithm is the only single-call single-resolvent algorithm with O VT convergence rate when we only assume weak MV1 (Theorem 1).
The result for accelerated algorithms in the nonconvex-nonconcave setting is sparser. For negatively comonotone operators, optimal ((7) convergence rate is achieved by variants of the EG algorithm in the unconstrained setting (Lee Kim, 2021a) and in the constrained setting (Cai et al., 2022a). To the best of our knowledge, the ARG algorithm is the first ef- ficient single-call single-resolvent method that achieves the accelerated and optimal O(7) convergence rate in the constrained nonconvex-nonconchl marize previous results and our results in Table 1. Our analysis ARG is inspired by (Cai et al., 2022a) and uses similar potential function argument.
setting (Theorem 2). We sum-
PRELIMINARIES
Throughout the paper, we focus on the Euclidean space R" equipped with inner product (,, We denote the standard æ2-norm by -| For any closed and
Basic Notations.
convex set Z C R", lzll : + Z denotes the Euclidean projection onto set Z such that for any E IR", II 3] = argmin ||z z'|l-
We denote (zz, the fz-ball centered at
with radius r.
Normal Cone. We denote N2 2 + R to be the normal cone operator such that for 2 E (z) {a: (a,z' 2) S 0, Vz E 3}. Define the indicator function
0
if Z, otherwise.
[z(z)
+00
is not hard to see that the subdifferential operator dIz = Nz. A useful fact is that Il (z'), then A(z' z) Nz(z) for any À 0.
Monotone Operator. We recall some standard definitions and results on monotone oper- ators here and refer the readers to (Bauschke & Combettes, 2011; Ryu & Boyd, 2016; Ryu & Yin, 2022) for more detailed introduction. A set-oulued operator A R² = I maps each point 2 RR" to subset A(z) C RR" We denote the graph of as Gra A) == {(z, u) : u E A(z)} and the zeros of A as Zer (A) = (z: 0 E A(2)). The inverse operator of A is denoted as A whose graph is Gra(A 1) (u, (z, Gra(A)} For two operators A and B, we denote A B to be the operator with graph Gra ( + B) {(, + ug) : uA) e Gra(A), (z, E Gra(B)); We denote the identity operator I R² R" We say oper- ator A is single valued if A(z) < for all E R²" Single-valued operator A is L-Lipschitz
((zz) < L- ||z --'z 2'I1, Vz, E R". Moreover, we say is non-expansive if it is 1-Lipschitz.
Definition 1 (Maximally) monotonicity). An operator A : R = IR" is monotone if
(u-u', (i-n'zzzz') 2 0, v(z,u), (z', u!) Gra(A).
Moreover, A is maximally monotone if A is monotone and (A)(A) is not properly contained in the graph of any other monotone operators.
When g R² > R is closed, convex, and proper, then its subdifferential operator āg is maximally monotone. As an example, the normal cone operator Nz al is maximally monotone.
We denote resolvent of A as JA (1+ A)-1, Some useful properties of the resolvent are summarized in the following proposition.
Proposition If maximally monotone, then JA satisfies the following.
1. The domain of JA is IR" JA is non-expansive and single-valued R
4

---

Published as a conference paper at ICLR 2023
2. 2 Ia(z'), then z' - = A()). Ifc A(z), then cc)
3. When A N2 is the normal cone operator for some closed convex set 2, then JΛΛ Ilg is the Euclidean projection onto Z for all 1s > O.
Non-Monotone Operator.
Definition (Weak MV1 (Diakonikolas et al., 2021; Pethick et al., 2022)), An operator A R" RR satisfies weak MVI for some z" E (A), there exists p s
(u 1-==22) z²) 2 p||u11? V(z,u) E Gra(A).
Definition (Comonotonicity (Bauschke al., 2021)). An operator A R" RR is comonotone if
(u 14-u,, u2, z²) pl|u u'1,, (z',') Gra(A).
When A is p-comonotone for 0, then A is also known p-cocoercive, which is stronger condition than monotonicity. When is p-comonotone for p < O, then is non- monotone. Weak MVI with 0 is also know MVI, coherence, variational stability. Note that the weak MVI is implied by negative comonotonicity. We refer the readers to (Lee & Kim, 2021a, Example 1), (Diakonikolas et al., 2021, Section 2.2) and (Pethick et al., 2022, Section 5) for examples of min-max optimization problems that satisfy the two conditions.
2.1 PROBLEM FORMULATION
Inclusion Problem. Given F A where F IR" >> R" a single-valued (possibly non-monotone) operator and A R² = IR" is set-valued maximally monotone operator, the inclusion problem defined as follows
find zz E 2 such that E(z²) F(2") A(²))
(IP)
We say is an e-approximate solution to an inclusion problem (IP) if 0 E F(z) + A(z) + B (0,,e) e). Throughout the paper, we study IP problems under the following assumption. Assumption 1. In the setup of IP,
1. there exists z" E ZEr i.e., OE E F(z") + A(z*).
2. F is L-Lipschitz.
3. A is maximally monotone.
When F monotone, we refer to the corresponding IP problem as monotone inclusion problem, which covers convex-concave min-max optimization. In the more general non- monotone setting, we would study problems that satisfy negative comonotonicity or weak MVI.
Assumption 2 (Comonotonicity). In the setup of IP, E = + A is p-comonotone, i.e.,
(u (n- u z²) pllu u u'11? (z', E Gra(E).
Assumption 3 (Weak MVI). In the setup of IP, E F+ A satisfies weak MVI with p S O, i.., there exists z* E Zer(E),
(,,z-z') 2 V(z,u) Gra(E).
An important special case of inclusion problem is the variational inequality problem.
Variational Inequality.
Let Z S R" be a closed and convex set and F : R + R" be The variation inequality (VI) problem associated with Z and F is
single-valued operator. stated as
find z" Z such that (F(z"), z) V
(VT)

---

Published as a conference paper at ICLR 2023
Note that is special case of IP when A Ng dll is the normal cone operator:
0 E F(z") Nz(=") + - -((*) E (z")) + (F(z*),z* - 2) 0, 2.
The general formulation of VI unifies many problems such as convex optimization, min- max optimization, computing Nash equilibria in multi-player concave games, and is extensively-studied since 1960s (Facchinei & Pang, 2003). Definitions of the convergence measure for VI and the classical algorithms, EG and PEG, are presented in Appendix B.
2.2 CONVERGENCE MRASURE
We focus on a strong convergence measure called the tangent residual, defined as E (z) min(c || F(z) + cl|- It is clear by definition that F,A (z) S implies z is an e-approximate solution to the inclusion (II') problem, and also an (e D) approximate strong solution to the corresponding variational inequality (VI) problem when Z is bounded by D. Moreover, the tangent residual is an upper bound of other notion of residuals in the literature such as
the natural residual poot (Diakonikolas, 2020) the forward-backward residual FFA (Yoon & Ryu, 2022) as shown in Proposition (see Appendix B.4 for the formal statement and proof). Thus our convergence rates on the tangent residual also hold for the natural resid- ual or the newward-backwer residual. Note that in the unconstrained setting where A 0, these residuals are all equivalent to the operator norm [[(())]
3 OPTIMISTIC GRADIENT METHOD FOR WEAK MVI PROBLEMS
In this section, we consider an extension of the Optimistic Gradient (OG) algorithm (Daskalakis et al., 2017; Mokhtari et al., 2020a;b; Hsieh et al., 2019; Peng et al., 2020) for inclusion problems: given arbitrary starting point = Zo R" and step size af > 0, the update rule is
7+ = InΛ 24 1) F) (12+-))]
(OG)
z = 2 + F 1) (2(2+4))
For t 2 1, the update rule can also be written as 24 | Fz, (2+1 F 4)], which coincides with the forward-reflecee-backkee
algorithm (Malitsky & Tam, 2020). We remark that the update rule of OG is different from the Optimistic Gradient De- scent/Ascent (OGDA) algorithm (also known as Past Extra Gradient (PEG) algorithm) (Popov, 1980), which single-call but requires two projections each iteration.
Previous results for OG only hold in the convex-concate (monotone) setting. The main re- sult in this section is that OG has O / convergence rate even for nonconvex-noncorcaae min-max optimization problems that satisfy weak MVI, matching the state of the art results achieved by two-call methods (Diakonikolas et al., 2021; Pethick et al., 2022). Remarkably, OG only requires single call to F and single call to the resolvent JЧЯ in each iteration. The main result is shown in Theorem 1. The proof relies on simple yet important observation that 24 4-+++1 E F(Z(+3) A(Z(+))
Theorem 1. Assume Assumption 1 and 3 hold with p (-
12/3L 0]. Consider the iterates of
(OG) with step size n E (0, 21)) satisfying C = 2 + 2p
- 2 0 (existence of such nj is n
guaranteed by Fact 1). Then for any T 1,
|| 11
H² 1 Ct2
:C[T]
min tan (z 3)
F.A
min [C[
T' 1
<
where H2 = -||z1 - 2²12 111z - 10

---

Published as a conference paper at ICLR 2023
Proof. From the update rule of (OG), we have the following identity (see also (Hsieh et al., 2019, Appendix B)): for any p E 2,
|| pll = ||z - -pl? + 2 2 112-
2 - 1 2t 12
+ +2(21 21 -84--11 1) +) - 3 + +17E(22+ ( - 2
(2)
IyA(Z - (7 )l, we have 2- 3 E A(2 by Proposition 1.
Since
3
"
Then
žt zt !) -211 + F(2;1 E F(z, 4) + A(2, 1
21 - 2++1
"
Set = z². By the weak MVI assumption, we have
2(21 - ())(((( 3+4 + + 2+1b/
-x+1
2t+1 2²" 21tb//
=2n 211 y1
2p
S
||z Z1+1l1 112
(3)
y1
Define = -3--21 - > 0. We have identity
1 - c c- (1 +1+ 2c (1 (1-2c))] = 411 = 2
(4)
Combining Equation (2) and (3) and using ||a + b11 v 2||a|| + +2|1b12, we have
|| - 2²11
S ||| ==1 + |2++1 - 2 -||-1 -
2 + c||z 21+1|1 1| (c+ 2p }|| 11-1
|x+ - | -(1 2c)
314 24 |
20
< || 11 + (1 +1+ 20)
(c +
||| 2 111
n
(5)
Using the update rule of OG and L-Lipschitzness of F, we have that for any 1 12 0,
| - 2
[= - ||
|| S 1
7, -
2
(6)
Moreover, using ||a + bbll2 < <2||a|12 + 2||b|| 2 and Equation (6), we have that for any 2 1,
|-----2 - 2
1| $ 244 - 20|1 + - 1| < 3 - 24
2
1
||
2 + +1 | - -2
which imples
| =1|²== 2
1
1 - 1
- 12
4+4 -
(7)
2
Combining Equation (4), (5), (6), and (7), we have that for all 1.
|| - =²1 2²112 + 22=12
(1+20) 21+1 - - 2 (1
2 (c+
20 D01lzr [)]lzz-zze 1|111=2++111
S ||||
2c)
/ 1 2z
17
S |||| - 2²1 + (1- (1-2))222 - 2, $1?
1
(1 +20))7222
| - 2, 1?
2
(c + 20 ||| 2121 2
11
-||z -z"l 2²112 2| + 41 L
-11--1-24- -2--2 2 2
11) 111)) (c
20
||| 2.
17
7

---

Published as a conference paper at ICLR 2023
Telescoping the above inequality and using - 222 and 17L < 1/2 we get
2 2 2p 2)) || 2+11 112 S || ==11 2 1|2
Σ
11
Note that 2g is the same as 2-1 This completes the proof.
Fact 1. For any L > and
12v3L There exists E (0, 2t such that 1/22 + 32 - 222 > 0.
Proof. Let 2v3L
1
then the desired inequality holds whenever
p 17 L2)
1
L
12V3LL
ACCELERATED REFLECTED GRADIENT FOR NEGATIVELY COMONOTONE PROBLEMS
In this section, we propose a new algorithm called the Accelerated Reflected Gradient (ARG) algorithm. We prove that ARG enjoys accelerated ((+) convergence rate for inclusion problems with comonotone operators (Theorem 2). Note that the lower bound ((+) holds even for the special case of convex-concave min-max optimization (Diakonikolas, 2020; Yoon & Ryu, 2021).
Our algorithm is inspired by the Reflecied Gradient (RG) algorithm (Chambolle & Pock, 2011; Malitsky, 2015; Cui & Shanbhag, 2016; Hsieh et al., 2019) for monotone variational inequalities. Starting at initial points 2-1 = Zg E 2, the update rule of RG with step size y is as follows: for 0, 0,
22 2t 1,
(RG)
2(+1 l1 2t 1/ FF(2++))
We propose the following Accelerated Reflected Gradient (ARG) algorithm, which is single-call single-resolvent first-order method. Given arbitrary initial points 2g = 21 E RR"
and step size > 0, ARG sets 21 = Jq (z0 17 F(()) and updates for 1,2,
2+1 = 22, - - t 1 (zo - =t) (zo - z(-1),
(ARG)
1 f (zo 21)
2+11 JnΛ -1 1F 4)
We use the idea from Halpern iteration (Halpern, 1967) to design the accelerated algorithm (ARG). This technique for deriving optimal first-order methods is also called Anchoring and receives intense attention recently (Diakonikolas, 2020; Yoon & Ryu, 2021; Lee & Kim, 2021a; Tran-Dinh & Luo, 2021; Tran-Dinh, 2022; Cai et al., 2022a). We defer detailed dis- cussion on these works to Appendix A. We remark that the state of the art result from (Cai et al., 2022a) is a variant of the EG algorithm that makes two oracle calls per iteration. Thus, to the best of our knowledge, ARG is the first single-call single-resolvent algorithm with optimal convergence rate for general inclusion problems with comonotone operators.
Theorem 2. Assume Assumption 1 and 2 hold for E [- -.)0,, then the accelerated reflected gradient (ARG) algorithm with conslant step size n > 0 salisfying Inequality (10) has the following convergence rate: for any T 1,
VOH 1
(ZT)
<
T'
where H2 =|= z¹112 4||=1
z0ll
<
|| |z z" 1| 4r (zo)
8

---

Published as a conference paper at ICLR 2023
Remark 1.
Note that Assumption 2 is satisfied with respect to some > 0, it also satisfies Assumption 2 with p = 0, so Theorem 2 applies.
We provide proof sketch for Theorem here and the full proof in Appendix C. Our proof is based on a potential function argument similar to the one in (Cai et al., 2022a).
Proof Sketch. We apply potential function argument. We first show the potential func- tion is approximately non-increasing and then prove that is upper bounded by term independent of T. As the potential function at step f is also at least ((P) , -('"(2+) (2+)² we conclude that ARG has an O(7) convergence rate.
LAST-ITERATE CONVERCENCE RATE OF REFLECTED GRADIENT
In this section, we show that the Reflected Gradient (RG) algorithm (Chambolle & Pock, 2011; Malitsky, 2015; Cui & Shanbhag, 2016; Hsieh et al., 2019) has a last-iterate convergence rate of O with respect to tangent residual and gap function (see Definition 4) for solving monotone variational inequalities (Theorem 3).
Theorem 3. For a variational inequality problem (VI) associated with a closed convex set Z and a monotone and L--ipsshitz operator F with a solution z", the (RG) algoritim with constant step size 1j E (0, [1+v2)L has the following last-iterate convergence rate: for any 2 1,
AHL GAPZZF,(ZT) S ADHL VT
tun F,2 (ZT) S
VT
where H2 4||20- - 2²112 1 F(zo)] and (
6(1-3)2L2)
We remark that the convergence rate of RG is slower than ARG and other optimal first- order algorithms even in the monotone setting. Nevertheless, understanding its last-iterate convergence rate still interesting:
(1) RG is simple and largely used in practice; (2) Last- iterate convergence rates of simple classic algorithms such as EG and RG mentioned as open problems in (Hsieh et al., 2019). The question is recently resolved for EG (Gorbunov et al., 2022a; Cai et al., 2022b) but remains open for RG; (3) Compared to EG, RG requires only single call to F and single projection in each iteration.
We provide proof sketch for Theorem 3 here and the full proof in Appendix D.
Proof Sketch. Our analysis is based on a potential function argument and can be sum- marized the following three steps. (1) We construct potential function and show that it is non-increasing between two consecutive iterates; (2) We prove that the (RG) algorithm has a best-iterate convergence rate, i.e, for any > 1, there exists one iterate t* E [T] such that potential function at iterate 1* is small; (3) We combine the above steps to show that the the last iterate has the same convergence guarantee as the best iterate and derive
the O( ( last-iterate convergence rate.
CONCLUSION
This paper introduces single-call single-resolvent algorithms for non-monotone inclusion problems. We prove that OG has O convergence rate for problems satisfying weak
MVI and design problems satisfying negative comonotonicity. Finally, we resolve the problem of last-iterate convergence rate of RG.
algorithm ARG that has the optimal 0(+) convergence rate for

---

Published as a conference paper at ICLR 2023
ACKNOWLEDGEMENTS
Yang Cai is supported by Sloan Foundation Research Fellowship and the NSF Award CCF-1942583 (CAREER). We thank the anonymous reviewers for their constructive com- ments.
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein Generative Adver- sarial Networks. In Proceedings of the 34th International Conference on Machine Learn- ing, Pp. 214-223. PMLR, July 2017. URL https: httpss//proceedddege http://rrooonnn........raaaaa/// mww.ppress/////// arjovskyl 7a html. ISSN: 2640-3498.
Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. {CMS} [Books} in {Mathematics). Springer, 2011. URL https://
link. springer. com/ http//ooo/////// 10 100.1000/7775 1- 1111//9888--414----1
Heinz H Bauschke, Walaa M Moursi, and Xianfu Wang. Generalized monotone operators and their averaged resolvents. Mathematical Programming, 189(1):55-74, 2021.
Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust Optimizationn
Princeton University Press, December 2009. ISBN 978-1-4008-3105-0. doi: 10.1515/ 9781400831050. URL https://wwee dwwpuyteedr.teeeccommmmm com httm///cmmmee//////..ooee.. 9781400831050/ntzt
Axel Böhm. Solving roncomvex-noonooncaee min-max problems exhibiting weak minty solutions. arXiv preprint XrX::2201.11227,, 2022.
Radu Ioan Bot, Ernö Robert Csetnek, and Dang-Khoa Nguyen. Fast ogda in continuous and discrete time. arXiv preprint ar Att:22033.10441 2022.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated algorithms for monotone inclusion and constrained nonconvex-nonncomcave min-max optimization. arviv preprint arXiv:2206.05244 2022a.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Finite-time last-iterate convergence for learning in multi-player games. In Advances in Neural Information Processing Systems (NeurIPS), 2022b.
Antonin Chambolle and Thomas Pock. A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging. Journal of Mathematical Imaging and Vision, 40 (1):120-145, May 2011. ISSN 1573-7683 doi: 10.10077/100511-010005511 URL https: //doi. ort.oi..rg//.... 00000000000000 01000001-02022000001---110--0011
Shisheng Cui and Uday V Shanbhag. On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems. In 2016 JEÉF 55th Conference Decision and Control (CDC), 2016.
Bo Dai, Albert Shaw, Lihong Li, Lin Xiao, Niao He, Zhen Liu, Jianshu Chen, and Le Song. Sbeed: Convergent reinforcement learning with nonlinear function approximation. In International Conference on Machine Learning, pp. 1125-1134. PMLR, 2018.
Cong D Dang and Guanghui Lan. On the convergence properties of non-euclidean ex- tragradient methods for variational inequalities with generalized monotone operators. Computational Optimization and applications, 60(2):277-310, 2015.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. Xiv preprint ar arXiv:1711.00111 2017.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. In Proceedings of the 53rd Annual ACM SIGACT Sym- posium Theory of Computing (STOC), 2021.
10

---

Published as a conference paper at ICLR 2023
Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone in- clusion and strong solutions to variational inequalities. In Conference on Learning Theory (COLT), 2020.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured nonconvex-nonconcayy min-max optimization. International Conference Ar- tificial Intelligence and Statistics, 2021.
Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction methods for policy evaluation. In International Conference on Machine Learning, pp. 1058. PMLR, 2017.
Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Com- plementarity Problems. Springer, 2003. URL https://ttatt spri
springer iige. com/ book/
10.1007 0240007/b97444
Tanner Fiez and Lillian J Ratliff. Local convergence analysis of gradient descent ascent with finite timescale separation. In Proceedings of the International Conference on Learning Representation, 2021.
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis. Tight last-iterate conver- gence rates for no-regret learning in multi-player games. Advances in neural information processing systems (NeurIPS), 2020.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances in neural information processing systems, 27, 2014.
Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: (11/k)
last-iterate convergence for monotone variational inequalities and connections with co- coercivity. In International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 366-402. PMLR, 2022a.
Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of op- timistic gradient method for monotone variational inequalities. In Advances in Neural Information Processing Systems, 2022b.
Benjamin Halpern. Fixed points of nonexpanding maps. Bulletin of the American Mathemat- ical Society, 7366)9557-61, 1967.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge to local nash equi- librium. Advances in neural information processing systems (NeurIPS), 30, 2017.
Michael D Hirsch, Christos H Papadimitriou, and Stephen A Vavasis. Exponential lower bounds for finding Brouwer fix points. Journal of Complexity, 5(4):379-416, Decem- ber 1989. ISSN 0885-064X. doi: 10.1016 00000//000850-02211999900017-120 URL https://www sciencedirect. com/ http:///wnneearrccce////////////
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In Ad- vances in Neural Information Processing Systemi,, volume 32. Curran Associates, Inc., 2019. URL https: http://ppooecen..ceeee/p mww.roeeeediinn.....eeeeeeeeeeee newrips........ 12255Bee1ddddddcc444e
https//ree.....pp////////111 htt/papprr22119/heee .tml..
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What local optimality in nonconvex-
nonconcave minimax optimization? In International conference on machine learning (ICML), pp. 4880-4889. PMLR, 2020.
Donghwan Kim. Accelerated proximal point method for maximally monotone operators. Mathematical Programming, 190(1):57-87, November 2021. ISSN 1436-4646. doi: 10.1007/ s10107-001--1643-00 URL hittps://ool 00 643--0
11

---

Published as a conference paper at ICLR 2023
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976. URL https: aai.ac. jp/naid/ 10C17556617/.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex-noncomeawy minimax problems. In Annual Conference on Neural Information Processing Systems (NeurIPS), 2021a.
Sucheol Lee and Donghwan Kim. Fast Extra Gradient Methods for Smooth Structured Manconvex-Nonconcnn Minimax Problems. Technical Report arXiv:2106.02322 arXiv, November 2021b. URL [math] type: article.
ptggabb//20s.....//////// 02326. arXiv:2106.02326
Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tian- bao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. In International Conference Learning Representations (ICLR), 2019.
Mingrui Liu, Hassan Rafique, Qihang Lin, and Tianbao Yang. First-order convergence the- ory for Research, 22(169):1-34, 2021.
wewooooeewwwallyoooooo.oo min-max problems. Journal of Machine Learning
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. arXiv preprint xxXii:1706.06083, 2017.
Yu Malitsky, Projected Reflected Gradient Methods for Monotone Variational Inequali- ties. STAM Journal on Optimization, 25(1):502-5200 January 2015. ISSN 1052-6234, 1095- 7189. doi: 10.1137/14097238X, URL http: http///axvvvvo/// orgg abss//////// /1tas.1522..00 04968. 1502.04968.
arXiv:
Yura Malitsky. Golden ratio algorithms for variational inequalities. Mathematical Program- ming, 184(1):383-410, 2020.
Yura Malitsky and Matthew K. Tam. A Vorward-Backwart Splitting Method for Monotone Inclusions Without Cocoercivity. SIAM Journal on Optimization, 30(2):1451-1472, January 2020. ISSN 1052-6234. doi: 00.137//8M120722 URL https: /tsps://epubi /epubs...... siam. / doi/abs/ 10, 11111111111102201 600000 Publisher: Society for Industrial and Applied Math- ematics.
Eric V Mazumdar, Michael I Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arxiv preprint drXiv:1901.00833. 2019.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra- gradient and optimistic gradient methods for saddle point problems: Proximal point ap- proach. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020a.
Aryan Mokhtari, Asuman E Ozdaglar, and Sarath Pattathil. Convergence rate of (11/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM Journal Optimization, 323-33320-- 2020b.
Arkadi Nemirovski. Prox-method with rate of convergence O (1/t) for variational inequal- ities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-251, 2004. Publisher: SIAM.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequal- ities and related problems. Mathematical Programming, 109(2)3319-444, March 2007. ISSN 1436-4646. doi: 001100//1110000000000000 s1 810107-006-0033
URL http:: http:://doooooooooo...oo www..orrg....0. 1007/
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. Ad- vances in Neural Information Processing Systems (NeuriPS), 32, 2019.
12

---

Published as a conference paper at ICLR 2023
Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concave bilimear saddle-point problems. Mathematical Programming, 185(1):1-35, 2021.
Christos H. Papadimitriou. On the complexity of the parity argument and other ineffi- cient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, June 1994. ISSN 0022-0000. sciencedirect
doi: 10.0016/0002-00000550066777 URL https: htttps://ww.
Neal Parikh and Stephen Boyd. Proximal Algorithms. Foundations and Trends@ in Optimizatiinn, 1(3):127-239 January 2014. ISSN 2167-3888, 2167-3918.
doi: 10.
1561/2400000003, URL https: /wwwww .owpub cowwublishers. com/ wwtaaaaeeeeeeaalle......// OPT-003. Publisher: Now Publishers, Inc.
Wei Peng, Yu-Hong Dai, Hui Zhang, and Lizhi Cheng. Training GANs with centripetal acceleration. Optimization Methods and Software, 35(5)9555-973, 2020. Publisher: Taylor & Francis.
Thomas Pethick, Puya Latafat, Panagiotis Patrinos, Olivier Fercoq, and Volkan Cevherå. Escaping limit cycles: Global convergence for constrained nonconvex-monconcav mini- max problems. In International Conference on Learning Representations (ICLR), 2022.
Leonid Denisovich Popov. A modification of the Arrow-Hurwicz method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 28(5):845-844 1980. Publisher: Springer.
Ernest K Ryu and Stephen Boyd. Primer on monotone operator methods. Appl. Comput. Math, 15(1):3-44 (11)))33332200 2016.
Ernest K. Ryu and Wotao Yin. Large-Scale Convex Optimizatiin via Monotone Operators. Cam- bridge University Press, 2022.
Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. Advances in Neural Information Processing Systems (NeurIPS), 23:14303-14314, 2020.
Quoc Tran-Dinh. The Connection Between Nesterov's Accelerated Methods and Halpern Fixed-Point Iterations, March 2022. URL http://arxiv.org/ babpg//bb//2a/ 04869.
arXiv:2203.04869 [math].
Quoc Tran-Dinh and Yang Luo. Halpern-Type Accelerated and Splitting Algorithms For Monotone Inclusions. Technical Report arXiv:2110.08150, arXiv, December 2021. URL http://arxis wtgg/bss///// abs//bbs//// 08150. arXiv:2110.08150 [math, stat] type: article.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance reduction for class of nonconvex-monconcaee minimax problems. Advances in Neural Information Processing Systems (MeurIPS), 33:1153-1165, 2020.
TaeHo Yoon and Ernest K Ryu. Accelerated algorithms for smooth convex-concave mini- max problems with (1/k2²) rate on squared gradient norm. International Conference on Machine Learning (ICML), pp. 22098-12109 PMLR, 2021.
TaeHo Yoon and Ernest K Ryu. Accelerated minimax algorithms flock together. Xiv preprint ar Xix:2205.11099 2022.
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter W Glynn. Stochastic mirror descent variationally coherent optimization problems. Ad- vances in Neural Information Processing Systems (NeurIPS), 30, 2017.
13

---

CONTENTS
1 Introduction
1.1
Our Contributions
2
1.2
Related Works
2
Preliminaries
2.1
Problem Formulation
2.2
Convergence Measure
3
Optimistic Gradient Method for Weak MV1 Problems
6
4
Accelerated Reflected Gradient For Negatively Comonotone Problems
Last-Iterate Convergence Rate of Reflected Gradient
6 Conclusion
A Additional Related Works
15
A.1 Convex-Concave and Monotone Setting
15
A.2
Nonconvex-Nonconcave Setting
15
Additional Preliminary
B.1
Resolvent and Proximal Operator
15
B.2 Gap Function
16
B.3
Classical Algorithms for Variationaly Inequalities
16
B.4
Tangent Residual Upper Bounds Other Notions of Residual
17
C Missing Proofs in Section 4
17
Potential Function..
17
C.2 Approximately Non-Increasing Potential
18
C33 Bouding Potential Iteration
20
C.4 Proof of Theorem 2
21
Missing Proofs in Section
22
D.1 Non-increasing Potential
22
D.2 Best-Iterate Convergence
23
D.3 Proof of Theorem 3
25
Numerical Illustration
25
Auxiliary Propositions
26

---

Published as a conference paper at ICLR 2023
A ADDITIONAL RELATED WORKS
A.1 CONVEX-CONCAVE AND MONOTONE SETTING
In the convex-concave setting, weak convergence measure the gap function (Defini- tion 4). It is well-known that classic extragradient-type methods such as EG and PEG have O(7) average-iterate convergence rate in terms of gap function (Nemirovski, 2004; Nesterov, 2007; Mokhtari et al., 2020b; Hsieh et al., 2019) and the rate is optimal (Ouyang & Xu, 2021). But the gap function or average-iterate convergence is not meaningful in the nonconvex-noncoocav setting For convergence in terms of the residual in the constrained setting, EG and PEG has a slower rate of O 7/) for best-iterate convergence (Korpele- vich, 1976; Popov, 1980; Facchinei & Pang, 2003; Hsieh et al., 2019) and the more desirable last-iterate convergence (Cai et al., 2022b; Gorbunov al., 2022b). We remark that the last-iterate convergence rate of the reflected gradient (RG) algorithm was unknown. The ((+)) rate is tight for p-SCIL algorithms (Golowich et al., 2020), subclass of first-order methods that includes EG, PEG, and many of its variations, but faster rate is possible for other first-order methods.
Accelerated Convergence Rate in Residual. Recent results with accelerated convergence rates in terms of the residual are based on Halpern iteration (Halpern, 1967) (also called Anchoring). The vanilla Halpern iteration has O convergence rate for cocoercive op- erators (stronger than monotonicity) (Diakonikolas, 2020; Kim, 2021). Recently, a line of works contributed provide O(2) convergence rate for monotone operators in the con- strained setting. Diakonikolas (2020); Yoon & Ryu (2022) provide double-loop algorithms with O T) convergence rate for monotone operators in the constrained setting. In the unconstrained setting (A 0), Yoon & Ryu (2021) propose the Extra Anchored Gradi- ent (EAG) algorithm, the first efficient algorithm with O(7) convergence rate for mono- tone operators. They also establish matching lower bound for first-order methods. Lee & Kim (2021a) generalize EAG to Fast Extragradient (FEG), which works even for negatively comonotone operators but still in the unconstrained setting. Analysis for variants of EAG and FEG in the unconstrained setting is provided in (Tran-Dinh & Luo, 2021; Tran-Dinh, 2022). Recently, Cai et al. (2022a) close the open problem by proving the projected version of EAG has ((7) convergence rate. They also propose the accelerated splitting (AS) algorithm, a generalization of FEG, which has ( convergence rate for negatively comonotone operators in the constrained setting.
A.2 NONCONVEX-NONCONNCN SETTING
This paper study structured nonconvex-nonconcav optimization problems from the gen- eral perspective of operator theory and focus on global convergence under weak MVI and negative comonotonicity. There is line of works focusing on local convergence, e.g., hegaatv (Heusel et al., 2017; Mazumdar et al., 2019; Jin et al., 2020; Fiez & Ratliff, 2021). Another line of works focus problems satisfying different structural assumptions, such as the Polyak Lojasiewicz condition (Nouiehed et al., 2019; Yang et al., 2020).
B ADDITIONAL PRELIMINARY
B.1 RESOLVENT AND PROXIMAL OPERATOR
When A = äg the subdifferential operator of a lower semi-continuous, proper, and con- vex function f, its resolvent (I+ Adg) -1 is also known as the proximal operator of g denoted as pg The resolvent (I + Aāg) 1 is efficiently computable for the following popu- lar choices of function g: norrm || 11, f2-norm ||- ll2, maxtrix norms, the log-barrier Σn= lx,( and more generally any quadratic or smooth functions. Moreover, many of them have closed-for foom expressions. For example, the proximal operator of the fn-nrmm g
15

---

Published as a conference paper at ICLR 2023
I1-1h is the element-wise soft-thresholding operator (prox), (o)); (0))) (v: - ()+ (-v A)+
We refer readers to (Parikh Boyd, 2014, Chapter 6, 7) for a comprehensive review on proximal operators and their efficient computation.
B.2 GAP FUNCTION
A standard suboptimality measure for the variationaly inequalitt (VI) problem is the gap function defined GfPz,f(z) max (F(z),z-z)) z'). Note that when the feasible set Z is unbounded, approximating the gap function is impossible: consider the simple uncon- strained saddle point problem minyeR maXyeR xy, which has unique saddle point (0,0) but any other point has an infinitely large gap. A refined notion is the following restricted gap function (Nesterov, 2007), which is meaningful for unbounded 2.
Definition (Restricted Gap Function). Given a closed convex set Z, single-valued operator F, and radius D, the restricted gap function at point E Z is
GA = max 2e2nn(E,D)
(F(z), - z')
where (zz, D) a Euclidean ball centered with radius
In the rest of the paper, we call ZA, the gap function (or gap) for convenience. The following Lemma relates [[F(z) cll where c Nz(z), and the gap function.
Lemma 1. Let 2 be closed convex set Z and F be monotone and L-Lipschitz operator. For any z E and c E Nz(2), we have
GAPZ,ED(3)== ZeZnB(2,))
(F(x),z--z) s D [[(() + c|]-
Proof. The proof straightforward. Since c E Nz(2),, we have (c,z - z²) 2 for any z' E Z. Therefor,
max (F(z),2-z') S max z'E2nB(z,))
(F(z) + c, z')
< max
| |[((z) + cll
((,DD
(Cauchy- inequality)
< D. DF(i(((z) + +cl-
B.3 CLASSICAL ALGORITHMM FOR VARIATIONALY INEQUALITIES
The Extragradient Algorithm (Korpelevich, 1976). Starting at initial point 2, the update rule of EG is: for 0, 0,1,2,
3+ -IT - F(()),
(EG)
2+1 1l 21 - 1 FF
At each step 2 0, the EG algorithm makes an oracle call of F(z+) to produce an interme- diate point 2,+ 1 (a gradient descent step if F of is the gradient of some function, f), then the algorithm makes another oracle call F(Z and updates to 2141- In each step, EG needs two oracle calls to F and two projections lTg.
The Past Extragradient Algorithm (Popov, 1980) Starting initial point 2g 1 Z, the update rule of PEG with step size y > 0 is: for f = 0, 0,
2 1 = II 2 F/( }
(PEG)
4/1 = ll
2, - 17 FF (F (
16

---

Published as a conference paper at ICLR 2023
Note that PEG is also known the Optimistic Gradient Descent/Ascent (OGDA) algorithm in the literature. The update rule of PEG is similar to (EG) but only requires a single call to F in each iteration. Both of EG and PEG perform two projections in every iteration.
B.4 TANGENT RESIDUAL UPPER BOUNDS OTHER NOTIONS RESIDUAL
Proposition 2. Let A be maximally monolone operator and F be an single-valued operator. Then for any z E R and a > 0,
F,A (z) Z F,A (z) == || IA(Z F(z))1I
lan
(z) 2 F.A. (z) = - - (aol==aF(zz]))) a=())]|
lan
F.A
Proof. For any E A(2), have
Hat FAA(2) = 1A F(z))1I
= 11 + c) - - F(z))I
S [F((2) +cl
(A non-expansive)
and
ft
1 1| 2 Jan(z -xF(z))l
(AA =
Iaa + ac) laa(z - aF(z))]
a
S [1 + +cl-
(Ia non-expansive)
Thus both pla
F,A (z) and f F,A (2)
(z) are smaller than plan (/ (2) min [|F(z) + +cll- cEA(Z)
C MISSING PROOFS IN SECTION 4
To prove Theorem 2, we apply a potential function argument. We first show the potential function is approximately non-increasing and then prove that is upper bounded by term independent of T. As the potential function at step t is also at least Q(f) pan (z,)² we conclude that ARG has an O(7) convergence rate
C.1 POTENTIAL FUNCTION
Recall the update rule of ARG: Zg = 21 E R are initial points and 21 = JyA(zo - 17 F
for f 1,
3 = 22, - 24 +
t (zo =1) - - 2t 1),
(ARG)
1 1+1 (zo 2+)
Z141 J1A 2- (n=nF(2z+)))
Recall that when A is the normal cone of closed convex set Z, the resolvent JA is equiva- lent to Euclidean projection to set Z. Hence, we apply the ARG algorithm to solve mono- single call to operator F and single projection to
tone VI problems, the algorithm Z per iteration. Here we allow A to be an arbitrary maximally monotone operator, and the ARG algorithm becomes single-call single-resolvent algorithm in this more general setting.
Next, we specify the potential function. Define
2t 1f(2z 4) + F+r (zo - 2²) - 21+1
C(+1
VF 0.
(8)
11
17

---

Published as a conference paper at ICLR 2023
By update rule we have e A(z)) for all 2 1. The potential function at iterate f 2 1 is defined as
f(f + 1) [1nF(z+) neel? +(++1) 1) (F((z)) (2 1 ((1F(2)) + 1,t,, 20).
V4 2
C.2 APPROXIMATELY NON-INCREASING POTENTIAL
1 Fact 2. For any L > 0 and 2 50L. There exists 17 > O such that
40 ) 2
20 0.
(12
(10)
7)
Moreover, every l1 > satisfies (10) also satisfies
e. 2 -4 4-
Proof. Rewriting (10), we get
12222112222 1)
p
4+81212
Let 7 and f(x) x(22x² (10). Moreover, rewritng (10) and using yl. > 0, we get
1). Since f(12) = 292 <
-
1
We know yf 127. satisfies
41 1x2
60-
1 -2
2 4 + 81
2
4
We show in the following lemma that V₁ is approximately non-increasing. Lemma 2. In the same setup as Theorem 2, for any 1 2 1, we have
V < V, [1F((z+1) + 1/12111
Proof. The plan is to show that V. V/+1 plus few non-positive terms is still 2 [ln((zz))) + 1 which certifies the claim.
Two Positive Terms. Since F + A is p-comonotone, we have
(7)(())1) + 1/411 - FfF(z)) - nc: 2++1 - 21) P [1)F((z+1) + nc++1 - -FF(z) - -n:l1 2
(11)
Since F is L-Lipschitz, we have
1 |141 2+1/| || 1/(((=1)
- 1 (F(2,+))| 20
Denote p
1. z Multiplying the above inequality with 1 S 0 and rearranging terms,
we get
(F(2zH1)-17F4 - |+11 -2 -1
+ (1- P ))12(?2 -p) 1||7/1 -
1 11 + p
11 ()F(())1)
- -)F( 20.
(12)
37
3n
18

---

Published as a conference paper at ICLR 2023
Sum-of-Squares Identity.
We show equivalent formulation 2, and Z++1 using defi- nitions I/c: = Zt - Zt - --2 + (20 2t 1) and 1/c111 2t - 17 ( + न (2o
z:) Zt+1
1
1 { (z0 21-1)
2-1 = =2z Z1-1 + f+ 1
(zo- z+)
2: + (zi - Zt 1) + 1+1 1
(zo zt) (2o - Zt 1)
= 2 - nf /2 - - -|Cc= +
1 1+1 (zo - -2)),
2++1 = - -1) {) - -1cc+11 +
++ (20 - 21)-
We also have
21+1 -1+ = - +ncc - - 7/1+1
(13)
Next, we simplify
V - V V/+1- ff x LHS of Inequality (11) t(t (1++1)
x LHS of Inequality (12)
4p
using the second identity in Proposition 3: replace Xo with zo: for k E [4], replace xa with replace
2-11+ and replace yt with FF((,-1+ replace U2 with fjc;; replace 44 with 7/t 17 replace
k with f; replace with q. Note that X3 x2 y1 - 42 + (xo x2) and X4 = X2
5/3 14 + + (xo -x2) hold due to the above equivalent formations of 2+4 and 21+1- Expression (17) and (18) appear on both sides of the following equation.
1(1 +1++1 1)
Vi - V41 t(t + 1) x LHS of Inequality (11)
x LHS of Inequality (12)
4p
f(t+1) 1)
7c: + ( F2 + 1 ((2++11 ||
|| 1-c+
(14)
4
+ (11
-4p) - 4p (1+11) (10)))111155 ||
17 F ||?
(15)
4p
+ (++11) 1). (nF(2)+)) - 11 1F((z+)), (f 1F((z+1) + nec+1)
(16)
+ + +1 f. (111)(((+1) 771111 n)((z) -cell
1)
(17)
1(++1)
317" -(11-
P
2n, - p) 1||-111- - 2+4 1|=
+ p 3r
4p
(18)
||a|| + (a,b) = || + ビ11 |b01 4, we have
Since
Expression (15) + Expression (16)
(1 4p) 4p
(t+1)
(yF(e++)-nN((C (F(Zet)) + *
p(t+ 1)
(n)((++1)) + 10++1)
4p
(1 (1-4p); 4p
4p)
+(++1)
-11F((2H1) + 11?
(1 4p))
4p
p(l 11)
[|1)((z)1)) + 11
(12 1)
(1- 8p){
2p
1 8p [1n (1) + 11/
(#) <)
1 (1F(2(41) + ?
(p=
19

---

Published as a conference paper at ICLR 2023
Now it remains to show that the sum of Expression (14), (17), and (18) is non-negative. Multiplying マानउ and replacing p 2 we get
4
1(1 1) (Expression (14) + Expression (17) + Expression (18))
| Ijc: F)2 :) 2))) + ( ||
(1- (1- (24 8p 1n2
| - 1?
yf
40 [17F(21+1) + Mc++1 (F(z)) neel1
8p
FF(2++1) 17 (2++ 11?
1/
"1
Denote
B = 1/+++1 - 1/c1 + ,f((z 4) - 22) + +1
B2 = 411 - = = 1) (2 ) + 1/c: - ,)F(21+4) - 17ct -17c
+nc
(By (13))
B3 = 17F(2++1) + 71,+++ - 17 F7((2)) - n/cr
B4 ,)F(2++1) - (2
not hard to check that B - BB = -2(B3- - Ba):
B B2 2/cc; - 2n/; - 2n/ (zi) + 2np F2 = 2(B3 BB).
Note that p is non non-positive and we have
(Expression (14) + Expression (17) + Expression (18))
f(t+1) + 1)
|| 2 + 1 (24
8p )11())
||B2 2 + P.
-12BB11
2p ||2Ba11
11
27
1
4p 1
||1 -B211 + f 112BB| 2| 20 ||2Bu112
2
(12
2
([|al] + ||||| >
2 bb12 and (24 80 ) 2 0)
1
4 ))
|| 2h11 + 20 112Bs - 2B411
>
(12
2
11
(-||al) 2 + 2|1b11 2 -2lla - b11 and - 20
1
4p L3+
22) 11
2 (12
| B211
(B, B2 2(B3 B4))
2 0.
(Inequality (10))
The last inequality holds by the choice of 1 shown in Fact 2.
C.3 BOUDING POTENTIAL AT ITERATION 1
Lemma 3. Let F be L-Lipschitz operator and A be a maximally monolone operator. For any 20 21 E R", 1) E (0, 1.), and z1 J^A Izo F/F(z)),, we have the following
1. || - -zol S "1 lan (zo).
2. [(1) + n S (1+nL)|zz) - zoll-
3. V1 < 4||21 - 20l1 2 where V1 is defined in (9).
Proof. For any c E A(zo), due non-expansivennsss of IAА, we have
|| zoll = ||] F)()) - Jn + ncll s f)(F((z)) + cll-
20

---

Published as a conference paper at ICLR 2023
Thus |||| - zoll - 11 FF, (zo).
By definition of V/2 in (9), have
Vi ||)) + reall + (1))((2) f)((z))) (n)((z) + 111, - -20).
We bound [(z) + reill first. Note that by definition, we have r/c1 = 20 - F7 - 21.
Thus have
[1)F(z1) + wc1ll
||z0 - 21 + -
$ ||z0 21 + |
(triangle inequality)
< (1 + ,/]] zoll-
(F is L-Lipschitz)
Then we can apply the bound on [|/) + .ciil to bound V1 as follows:
Vi = [l)((z) + y/1l 1| ||/ - ,7F(2)))l + (1)(21) + NC1, 2p)
$ ()))(2)) + . + 1 =oll2 (1)) / zoll
< (1 (1++L)) 1| - 2 1/
- =0112 2
(1++))) - zo11
(2+ (2+3y11 3n1. + 2. 2012
- 41|21 - zoll2.
where we use I-Lipschitzness of F and Cauchy-Schwarz inequality in the first inequality;
use () + . < + L zoll in the second inequality; we use 7 S in the
last inequality.
C.4 PROOF OF THEOREM
We first show that the potential function V, = 2(F plan (zt)(z))) )2+)
Lemma 4. In the same setup as Theorem for any 1 2 1, we have
t(t + 4 [nF((z)) + + s V, + 1|2* - zol1
4
Proof. Since 0 F(z*) + A(z)), ), by p-comonotonicity of F + and Fact 2, we have
(n)((z)) + nc,, 2 z²) 2 f [|)F((z)) + rcell 2 - 11)(()))+ + n0,12
(19)
By definition of V₁ in (9), for any f > 1, we have
V; t(t ((++1) 1)
f(t ((t+1) 1)
(1/F(z)) + n/+=11
- () 1
+ f(1)((z)) + Nct, - zo)
2
t(t +1 1)
(1/F(zz)) + no:l1 + + not, 2*) + F(z)(zz) + net,"* - zo)
2
1(1 + 1)
+(1 + ne, - zo) + yail 1 (ln (1
[|/F((z) + m
2
(By Inequality (19))
1(t + 1)
[17)((z)++ + 1(t+ 1)
t
[[nF(Z)) + 1ail1
||2 - =011
2
4
t t+
t(t + +)
[1/((z)) + #c=ll 1|2" =01l?
4 1)
4
where in the second last inequality we we apply (a,b) 2 =flla|1 1|lb112 with a = VI(nF(z)) + 70), b Ví(z" 20), and +
21

---

Published as a conference paper at ICLR 2023
Proof of Theorem 2. It is equivalent to prove that for every T 2 1, we have
llxF(zT) + 1/Tr|12 < 6H²
72
From Lemma 3, we have
[1))(zz) + s/cill 11+ zoll² s H².
So the theorem holds for T 11 For any 2 2, by Lemma 4 have
T(T 2)
[1)F(Zz) + ncT|| & + + ||00 - 221
4
S
V/ + |100 2²112
Σ
[1) + nall
+=2
1 T H2 [z+) + nctl12
Σ
By subtracting 8 ( n/rl| from both sides of the above inequality, get
T2 [) + nerll < H2
F + n
4
1=2
which is in the form of Proposition 4 with C₁ = H2 and == 4. Thus we have for any T 2
6H²
[ + v
72
D MISSING PROOFS IN SECTION 5
To prove Theorem 3, our analysis based on potential function argument and can be summarized in the following three steps. (1) We construct a potential function and show that it is non-increasing between two consecutive iterates; (2) We prove that the RG algo- rithm has best-iterate convergence rate, i.e, for any T > 1, there exists one iterate t" E [T] such that our potential function at iterate 1 is small; (3) We combine the above steps to show that the the last iterate has the same convergence guarantee as the best iterate and
derive the O last-iterate convergence rate.
D.1 NON-INCREASING POTENTIAL
Potential Function. We denote
21 (FF(21))) 2111
C1+1
V+ 0
(20)
11
Note that according to the update rule of RG, 2+11 = Zz - n) (2(2++)..
so cr11
e
The potential function we adopt is P; defined as
Pt = [F(2t) + c:11 + (|((Z)) F(Z 1| Vt Vt 1. Lemma 5. In the same setup of Theorem 3, P 2 P(+1 for any 2 1.
(21)
Proof. The plan is to show that P P plus a few non-positive terms non-negative,
which certifies that Pt Pri1 0.
22

---

Published as a conference paper at ICLR 2023
Three Non-Positive Terms.
Since F is monotone, we have
(-2) (1+((++1) 1)((2)), - 21) - 0.
(22)
Since F is L-Lipschitz and 0 < 1 < (1+v2)L 21, we have
(-2) 1 - 2 l| F(((411) - (F(( ( 11'))
S O.
(23)
By definition, we have C++1 N2(2++) and et E Nz(4)). Since the normal cone operator
Ng is maximally monotone, we have
(-2) (1C++1 1/0,, z S
(24)
Sum-of-Squares Identity.
We use the following equivalent formations of 2 and Zr11-
2 1 = 2z,- 21-1 21 - (Z--1 z1) žς 1) 1 1/ct,
Zt-1 = 11 žイ - n) (2 = = 7 (2 1/ct+1.
The following identity holds according to Proposition 3. To see this, we replace x with 2, 11 replace y/ with F) 1 \/2 replace u2 with 17;;; replace 14 with 1/4-1; also note
that X3 X2 1/1 U2 and X2 1/3 hold due to the above equivalent formations
of 2, 1 and 21+1.
2 (P: PP:+1) + LHS of Inequality(22)
+ LHS of Inequality(23) + LHS of Inequality(24)
2 } - Z++1
F + Z++1
=
2 + 1)) ()((z)))
+
2 2t + F7())) + 7
The right-hand side of the above equality clearly 2 0, thus we conclude - Pri1 2
0.
D.2 BEST-ITERATE CONVERGENCE
In this section, we show that for any T 2 1, there exists some iterate fo such that
Pr. O(t), which is implied by E Pt = O(1). To prove this, we first show
EL 11 - E ||z - 2-11 0(1) and then relate Σ Pr to these two quanti- ties.
Lemma 6. In the same setup of Theorem 3, for any T 2 1, we have
T
T || 2-111 S 1 (1 + 22)1t
1²
Σ
2t Σ
2
Proof. First note that by the update rule of RG, we have 2,, = =2z 24-1 thus 2 1 2, =
Z: - 2z Therefore, it suffices only prove the inequality for E || 2z 1|
From the proof of (Hsieh et al., 2019, Lemma 2), for any 2 and p E 2, we have
- (1-(1+22)n1 || 21
12 < ||z+ - pll - ||| - -pl12 21/ F F(Zz(( 4) - p)
+ +1 |z - a1| || 2 2)
(25)
We set p = 2 to be a solution of the variational inequality (VI) problem in the above inequality. Note that
(
-21 (F(2++))))))))))))) (124++))22 ) 2 - -z*) -20 (F(E)())))) F(2") ), -2²) 22 27 ((((F(2),)) (F(("), - 2²)
5-27( ((2*))=2+) - 2²) -27(F(z²). (2((F(2)) - z²) (F(2")) -2") --²""
(F is monotone)
(26)
23

---

Published as a conference paper at ICLR 2023
where the last equality holds since 2 22, Zt-1- Also note that (F(2*), - -2*) >
O for all t 2 0 since ž E E and z" is a solution to (VI). Combing Inequality (25) and Inequality (26), telescoping the terms for t 1,2, T, and dividing both sides by 1 (1 + LL > 0, we get
T
2t 2
| 2²11² + || 21 || + (F(2")), =0 =²")
Σ
(1+ L2)
To get a cleaner constant that only relies on the starting point 2g = zg. we further simplify
the three terms on the right-hand side. Note that since 1 22 we have
1 and 21 = Tz 1 F(()))
1112 = ||||| zol12 S 1 (1((2))] -
4
2 1
_ ||F(zo))1
Thus we have
| 121-21 2 2||21 zoll2 + +2|1=0 - 1 s
8
- -=11 1 +
F(zo))
1
Moreover,
(F(2")) - z²) s
- =011 s (11((((2)) - F(zo)) + [[ ==0===
(A s J| BI + ||B|)
< 27L z²1 + 2ny F(zo) ||| ==|l
< 1z0 - 1= + | )1 || - ==
(1) < )
I 2||20 z" 112 + 2 |[
(2ab - a² +b))
Thus
+ ||| | 2²1
2! 111 (F(2"), - =²) -
I F(20) + +4|22- == = H2.
13
This completes the proof.
Lemma 7. In the same setup of Theorem 3, for any T 2 1, we have
T
S 12
Proof. We first show an upper bound for P.
[((z)) F(zz +) l|
P. [[F(z)) + cell2 +
F(z+) =(zz-))
2t - -2-1111 2
+ F(()
- F(zz-))( 111
(definition of ct (20))
11
S 3 F(z)) F(z, }11
+ 1
||z| -2 112
(I + BI < 2|| + 2 B(3)
S 312
2 - - 112
+ 172
|| - 2, 112
(F is L-Lipschitz)
3L2
2t - 21-1 + 21-11 - 2 3 l'
2
+
2
||zz - 21-11
172
S 27
2 1 - 2 || +
(2 + 6L.2
||z1- -
||||
212
(I + BII < <2|4|12 + +21
2
2 + L2
(1 21-1 -
+ ||zr 21-1112
2
24

---

Published as a conference paper at ICLR 2023
Summing the above inequality of f 1,2, ... .T, get
Σ P
T
2
22 T
Σ
7 - 24-1 -
+ ||z: - 2t -11)
172
1=1
1=1
2 + 22
||2| zoll
T-1
Σ
zel| e||2
+ +1 zal1²)
n72
1=1
2 612 11²
2H2
||2| zoll
+ 1 (1 + v2)nL
6(1 22)
21 + v2)nI.)
The second last inequality holds by Lemma 6. The last inequality holds since || -zoll² < H2. Recall that À
6(1+3)222)
This completes the proof.
D.3 PROOF OF THEOREM 3
Fix any T 2 1. From Lemma 5, we know that the potential function P; is non-increasing for all f 2 1. Lemma 7 guarantees that the sum of potential functions Σ Pt is upper bounded by A2H2L2, where A (0T2(1-(++/)))7)" Combining the above, we can con-
6(1+3y
clude that the potential function at the last iterate Pr is upper bounded by A2H222 Py [[(z)) cTll + ||F(27) F(z, 2)1 obtain the last-iterate convergence rate F (2T) [((T)) + crll < 1²H212
T Since
The convergence rate on |[((z)) + erl implies convergence rate on the gap function GAPZED((T) by Lemma 1:
ADHL
GAPZED(ZT) < D- [[((z)) <
VT
E NUMERICAL ILLUSTRATION
In this section, we conduct numerical experiments illustrate and compare the perfor- mance of several algorithms: Reflected Gradient (RG), Extra Gradient (EG), Accelerated Reflected Gradient (ARG), and Fast Extra Gradient (FEG) (Lee & Kim, 2021a). Among them, ARG and FEG are accelerated algorithms while RG and EG are normal algorithms.
Test Problem We use classical example (Problem 1 in (Malitsky, 2015)) which uncon- strained and the operator F(z) = Az where A is an X n matrix that
1, j=
Aii = -1 j=n+1-i<i
0,
otherwise
Note that F is 1-Lipschitz and its solution is the zero vector 0 when n is even.
Test Details We run experiments using Python 3.9 jupyter-notebook, on MacBook Air (M1, 2020) running macOS 12.5.1. Time of execution is measured using the time package in Python. For all tests, we take initial point to be the all-one vector 2n = (1, 11). We denote y7 to be the step size and the termination criteria the residual (operator norm) [[F(z))]| < The code be found in the Supplementary Material.
25

---

Published as a conference paper at ICLR 2023
Test Results The results for EG and RG are shown in Figure 1. With step size 1f 0.4, EG slower than RG. This due to the fact that EG makes two gradient calls per iteration. Even with the optimized step size yj 0.7 which gives the best performance, EG is still slower than RG for this problem. Our results are consistent with numerical results on Mathematica by Malitsky (2015).
The results for FEG and ARG are shown in Figure With step size = 0.5, FEG is slower than ARG. With the optimized step size y! FEG is little faster than ARG. So for this problem, the performance of FEG and ARG are comparable. We also remark that for this particular problem, both ARG and FEG are slower than EG or RG. This does not contradict with our theoretical results on worst-case convergence rate. Simple algorithms like RG and EG can be faster than accelerated methods like ARG and FEG for particular problems. This also illustrates the importance of understanding simple algorithms like RG.
EG
3.0
RG
EG-O
2.5
2.0
time
1.5
1.0
0.5
0.0
1000
2000
3000
4000
5000
6000
7000
8000
#dimension
Figure 1: Results for EG and RG when 0.001. The read line and blue line are EG and RG with step size 1 0.4. The yellow line is EG with (approximately) optimized step size r 0.7. We remark that RG would diverge with ! = 0.7.
F AUXILIARY PROPOSITIONS
Proposition (Two Identities). Let (xx)ke (4), (y*)ke(4j/ Xp, U2 and u4 be arbitrary vectors in R". Let k > 1 and q E (0,1) be two real numbers. If the following twoo equations holds:
X3
X2
1/1
1/2
X4 X22
1/3 144
26

---

Published as a conference paper at ICLR 2023
FEG
ARG
10
FEG-O
time
4
2
250
500
750
1000
1250
1500
1750
2000
#dimension
Figure Results for FEG and ARG when e = 0.01. The read line and blue line are FEG and ARG with step size y7 0.5. The yellow line is FEG with (approximately) optimized step size = 1.
then the following identity holds:
lly2
N2 2 + lly/ 21 1112-11y4 =u111-- 11y4 y3ll
2. (y1
1/2 X4
X2)
1
||x xal12 - 11y4 ysll2)
2
4
2
(14
1/2, - x22
2
2
X3
+
1/1
1/2
X2 + 1/2 + 112
2
2
If the following two equations holds:
X3 = X2
8/1
U1 +
(xo x2)
+ 1
X4 = X2
u4
(xo X2)
k + 1
27

---

Published as a conference paper at ICLR 2023
then the following identity holds:
k(k + 1) [1y/ u2ll² + 11y/2 y1ll²) kyy2 X2, xx0)
(k 1)(k +2) (194 + u4|l 2 + 1ly4 yall²) +1 + U4, X4 -x0)
k(k + 1) (y4 + "4 y/2 U2 X4 x2)
k(k+1) 1)
<9- ||x4 xx312 lly4 y33 12)1)
49
k(k + 1)
||24 - 1/2 + 1/1 - 2/2 + +yal1
4
(1
4q) 4q
(k +1) 1)) 111/3 - 2
+
4q
+ (k + 1) (y33
94 + U4)
Proof. We verify the two identities by MATLAB, The code available https: /
wttp.///wwwwwwaagnnnennnnnieoene /99/ wtt.g//ggl////eeeeee/ee Single-Call. Call.
Proposition 4 ((Cai et al., 2022a)). Let {ax E IR' Jaz2 be a sequence of real numbers. Let C₁ 2 and p E (0, à) be two real numbers. If the following condition holds for every k 2 2,
k2 a < C1
Av
(27)
p 1-2
then for each k 2 2 we have
4. 4.C, C1
1 1.2
4k -
(28)
1 3p
Proof. We prove the statement by induction.
Base Case: 2. From Inequality (27), we have
2
4. C1 1
S G
a2 C 5
4
1 - 3p 22
Thus, Inequality (28) holds for k = 2.
Inductive Step: for any 2 3. Fix some k and assume that Inequality (28) holds for all < f 1. We slightly abuse notation and treat the summation in the form L as 0. By Inequality (27), we have
k2
4k
C1 +
p
Σ
4
4
p
12
G
p
<
+
(02 S G1)
1-p p
1- P
4p. C1
Σ
(Induction assumption on Inequality (28))
1 1-p p
(1 (1-p)(1- -3))
1=3 12
< G
2p. C1
x²a
-
1 <
1- p
(1 p)( (1-3pppp 3p)
C
1- 3p
This complete the inductive step. Therefore, for all k 2 2, we have 0
<
4C1 T-3p
R
28


Reviews:
[{"review_id": "etsVUtcCoh", "reviewer": "Reviewer_qU6A", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper involves the study of constraint min-max optimization problems in the nonconvex-nonconcave setting with structure. Specifically, the more general framework of inclusion problems. Regarding the methods presented, they exclusively require single calls to the oracle and to the resolvent of an operator A; that is mainly the prominent goal of this work. \nThe two main contributions involve an extension of the Optimistic Gradient (OG) for the inclusion problems whose operators satisfied the weak MVI and a new accelerated Reflected Gradient (ARG) method for the same class of problems but for the case of negatively comonotone operators. The convergence rate achieved in the latter improves over [1] with respect to the number of oracle and projection calls, and is also optimal matching the lower bound of any first-order methods even for monotone inclusion problems. Lastly, the authors show that RG achieves a last-iterate convergence rate for convex-concave min max optimization, an open problem mentioned in [2].\n\n\nReferences\n[1] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated Algorithms for Monotone Inclusions and Constrained Nonconvex-Nonconcave Min-Max Optimization.\n[2] Yu-Guan Hsieh, Franck Iutzeler, JÂ´erË†ome Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods.\n[3] Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities.\n\nTypos\n\t1\tIn the last expression of Theorem 1 there should \\frac{2 \\rho}{\\eta}", "summary_of_the_review": "The authors show that RG achieves a last-iterate convergence rate for convex-concave min max optimization, answering an open question asked in \"On the convergence of single-call stochastic extra-gradient methods\". This makes the paper above the bar for acceptance I feel. ", "strength_and_weaknesses": "Overall, I believe it is above bar for acceptance. The paper provides a clear but quite technical analysis (Proposition 2) and does a significant contribution to the field of single-call methods. Additionally, although the presented techniques might not be novel (see [3]), the authors propose the first single call single-resolvent method (ARG) of optimal convergence rate in the general structured (negatively comonotone) constraint nonconvex-nonconcave setting that has received important attention lately.\n\nReferences\n[1] Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated Algorithms for Monotone Inclusions and Constrained Nonconvex-Nonconcave Min-Max Optimization.\n[2] Yu-Guan Hsieh, Franck Iutzeler, JÂ´erË†ome Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods.\n[3] Jelena Diakonikolas. Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "dxmVvLUAXc", "reviewer": "Reviewer_Sm3u", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes three single-call algorithms for constrained min-max optimization and develops the following convergence guarantees. (i) The OG method achieves $O(1/\\sqrt{T})$ convergence rate for weak MVI problems. (ii) The ARG method achieve the optimal $O(1/T)$ convergence rate in the negative comonotonicity regime. (iii) The RG method achieves an $O(1/\\sqrt{T})$ last-iterate convergence guarantee for constrained convex-concave optimization. The weak MVI and negative comonotonicity regimes have been well studied. ", "summary_of_the_review": "This paper proposes a class of single-call algorithms for solving nonconvex-nonconcave min-max problems and establishes the theoretical convergence guarantees. However, the single-call regime is not well-motivated. Theorems 1 and 2 rely on some restrictive choices of $\\rho$, which weakens their applicability. Theorem 3 provides a suboptimal convergence rate. No numerical results are provided to test the practical performance. ", "strength_and_weaknesses": "Strength:\n\n1. The algorithms establish the first convergence guarantee for nonconvex-nonconvex min-max optimization problems under weak MVI and negative monotonicity regimes. These results are new. \n\nWeaknesses: \n\n1. This paper studies the single-call scenario that restricts algorithms to conduct one oracle call per iteration. This seems to be restrictive and lacks motivation. The classical extra-gradient method only requires making two calls to obtain the gradients. Decreasing two calls to a single call does not seem to have a significant practical impact. These differences are often hidden in the big-O $O(\\cdot)$ notation with many other constants, such as the $H^2$ and $\\eta^2$ terms specified in Theorem 1. Meanwhile, if we consider  $z = [x, y]$ as one vector, EG approaches only require one projection instead of two.  It would be beneficial if the authors could provide more motivation for studying single-call algorithms. For instance, is there a scenario in which only single-call algorithms can be applied? \n\n2. In Theorem 1, the authors develop the convergence guarantees for weak MVI problems for a restrictive choice of $\\rho \\in ( - \\frac{1}{12\\sqrt{3}L}, 0]$. I wonder why it is necessary for the convergence claim. Is this choice of $\\rho$ commonly accepted by EG methods for weak MVI problems? Similarly, Theorem 2 considers the case when $\\rho \\in ( -\\frac{1}{100L}, 0 ]$, which also restricts its applicability. A comparison of choices of $\\rho$ in existing works would be beneficial. \n\n3. Theorem 3 establishes an $O(1/\\sqrt{T})$ convergence guarantee for convex-concave problems, which is suboptimal for EG methods. In this case, it seems suboptimal to consider single-call approaches because it requires a larger amount of iterations than the classical EG methods. \n\n4. This paper does not provide numerical experiments to test the practical performance of their algorithms. It would be beneficial if the authors could provide some numerical results to test their algorithm and compare the total required calls with classical EG approaches. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "DG9g_QalHJ", "reviewer": "Reviewer_GPXn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper has several contributions:\n1. it derives $(\\mathcal{O}\\frac{1}{\\sqrt{T}})$ convergence rate of the best iterate of an extension of Optimistic gradient (OG). The setup is weak minty VIs (MVI)---which is a setting that includes non-monotone VIs as well; Sec. $3$.\n2. proposes an accelerated version of Reflected Gradient (RG) by combining it with anchoring as in Halpern iteration--- named *ARG* for short---and shows that it achieves the optimal $\\mathcal{O}(\\frac{1}{T})$ last iterate rate. The setup here is negatively comonotone problems, which are larger than monotone but smaller class than weak MVIs. \n3. shows that RG has $\\mathcal{O}(\\frac{1}{\\sqrt{T}})$  last iterate rate for constrained convex-concave min-max optimization.  \n\n\nThe first two results are in terms of the decreasing rate of a quantity called *tangent residual* which the authors show that it upper bounds the natural residual in Diakonikolas, 2020. The third one is with respect to the standard gap function and also the tangent residual.\n", "summary_of_the_review": "This paper provides three contributions, among which the first two go beyond standard monotonicity, and thus are key to understanding game optimization.\nPrior work showed similar results for the first two contributions. The third contribution focuses on a much smaller problem class and it is not clear to me why it is relevant that we consider that method given that other methods have the same rate and guarantees for larger problem classes, but I may be missing something.\nIt focuses on three different setups and three different methods, making its coherence and writing structure less easy to follow. The paper could be significantly improved by adding motivations and discussions for the presented results, as well as some further more practically relevant questions such as parameter-free guarantees and stochastic settings.", "strength_and_weaknesses": "**Strengths**.\n- This paper focuses on some interesting and highly relevant VI problems and has several contributions.\n- It is generally well-written, and easy to follow, with clear notation. I also like that the authors provide proof sketches when the full proof is deferred to the appendix.\n\n\n**Weaknesses**\n- Some of the presented aspects of the first two contributions exist in prior works (please see below). The third contribution does not exist if I am correct, but it is for the setting of a much smaller class of convex-concave zero-sum games.\n\n- Missing motivation/relevance to focus on some of the considered methods and the little connection between the results and the considered setups and methods. In my opinion, it would have been clearer if the three results are separated and each is developed further with some more relevant questions such as parameter-free guarantees, stochastic case, etc, and discussing the insights from the theoretical results, e.g. better dependence on some constants relative to other methods, etc. \n\n- Structure. This may be a consequence of the above, but it is often difficult to follow the flow in terms of the motivation of what follows. For example, the introduction mostly motivates the first two contributions. Please also discuss therein the difference between those two non-monotone setups, for completeness. Then, Sec. 5 separately discusses the motivation for Thm. 3 after the result is presented.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster