Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions
Authors: Axel Böhm
Venue: Accepted by TMLR ()

Abstract: We investigate a structured class of nonconvex-nonconcave min-max problems exhibiting so-called \emph{weak Minty} solutions, a notion which was only recently introduced, but is able to simultaneously capture different generalizations of monotonicity. We prove novel convergence results for a generalized version of the optimistic gradient method (OGDA) in this setting, matching the $1/k$ rate for the best iterate in terms of the squared operator norm recently shown for the extragradient method (EG). In addition we propose an adaptive step size version of EG, which does not require knowledge of the problem parameters.


Published in Transactions on Machine Learning Research (03/2023)
Solving Nonconvex-Nonconcave Min-Max Problems exhibit- ing Weak Minty Solutions
Axel Böhm University of Vienna,
ozel. wwe.bochm@@umbbicccc..dd
Austria
Reviewed on OpenReview: https: openreview. net/ forun? id= GyDpHyur
Abstract
We investigate structured class of sonconvex-nonconeee min-max problems exhibiting so-called weak Minty solutions, a notion which only recently introduced and already prooved powerful by simultancously capturing different generalizations of monotonicity. We prove novel convergence results for a generalized version of the optimistic gradient method (OGDA) in this setting, matching the 1/k rate for the best iterate in terms of the squared operator norm recently shown for the extragradient method (EG). In addition we propose an adaptive step size version of EG, which does not require knowledge of the problem parameters.
1 Introduction
The recent success of machine learning models which can be described by min-max optimization, such as generative adversarial nelworks (Goodfellow et al. (0144), adversarial learning (Madry et al. 2018). adver- sarial example games (Bose et al. 2020g or actor-critic methods (Pfau Vinyals 2016). has sparked interest in such saddle point problems. While methods have been identified, which (mostly) work in practice, the setting in which the objective function nonconvex in the minimization and nonconcave in the maximiza- tion component remains theoretically poorly understood and even shows intractability results (Daskalakis et al. 2021 Lee & Kim 2021ap. Recently, Daskalakis et al. (2020) studied class of nonconvex--onnonccaee min-max problems and observed that the extragradient method (EG) showed good converge behavior in the experiments. Surprisingly, the problems did not seem to exhibit any of the known tame properties such as monotonicity, or Minty solutions. Lator, Diakonikolas et al. (2021) found the appropriate notion (sco Assumption D). which is weaker than the existence
Minty solution (an assumption extensively used the literature (Malitsky 2020 Liu al.) 2020 (221)) and also generalizes the concept of negative comono- tonicity (Bauschke et al. 2020 Combettes & Pennanen 2004 Lee & Kim 2021a). Due to these unifying
and generalizing properties the notion of weak Minty solutions was promptly studied in (Pethick et al. 2022
Lee & Kim 2021b).
Assumption 1 (Weak Minty solution). Given an operator F RR + Rd there exists a point u E Rd and a parameter p > such that
(F(u),u- w²) > - G1IF(W)1 E
(1)
Additionally, Diakonikolas al. (2021) proved that a generalization of EG (Korpelevich) 1976 is able to solve problems which exhibit such solutions with complexity of O(s-1) for the squared operator norm. This modification which they title EG+, is based on aggressive extrapolation step combined with a conservative update step. Such a step size policy has already been explored in the context of a stochastic version of EG in Hsieh et al. 2020).
In a similar spirit we investigate variant of the optimistic gradient descent ascent (OGDA) @Daskalakis et al.) 20188 Popov 1980)/ (500)//Foraas Coorwad--Rffleee Backward (FoRB) (Malitsky & Tam 2020) method. We pose the question, and give affirmative answer to:

---

Published in Transactions on Machine Learning Research (03/2023)
Can OGDA match the convergence guarantees of EG in the presence of week Minty solutions?
In particular, we show that the following modification of the OGDA method, given for step size >> 0 and parameter 0 < 7 S by
uk+1 uk - -a( F(uR-1)): 4k 2
is able to match the bounds of EG+ Diakonikolass et al.
2021 Pethick et al. 2022):
4k - afx) Uk+1 Uu (us)
Vk 2 0,
by only requiring one gradient oracle call per iteration. In Figure we see that beyond the theoretical guarantees OGDA+ can even provide convergence where EG- does not.
Note that OGDA is most commonly written in the form where y 1, see (Daskalakis al 2018 Malitsky Böhm et al. 2022), with the exception of two recent works which have investigated a more general coefficient see [Ryu et al. 2019: Mokhtari et al., 2020). While the previous references target the monotone setting the true importance of 7 onlyy shows up in the presence of weak Minty solutions as in this case we require it to be larger than 1 to guarantee convergence a phenomenon not present for monotone problems.
& Tam 2020
Connection to min-max. When considering general (smooth) min-max problem
min max f(x
the operator F mentioned in Assumption arises naturally F(u)
-V, v) with
= (z, However, by studying saddle point problems from this more general perspective of variational inequalities (VIs), see (SVT), via the operator F we can simultaneously caplure more settings such as certain equilibrium problems, see (Facchinei & Pang 2007
About the weak Minty parameter p. The parameter p in the definition of weak Minty solutions [ plays a crucial role the analysis and the experiments. particular is necessary that the step size is larger than term proportional to p, see for example Theorem 3.1 or (Pethick et al.] 2022). At the same time, as lypical, the step size constrained from above by the reciprocal of the Lipschitz constant of F. For example, since the authors of (Diakonikolas et al. 2021) require the step size to be less than 4. their convergence statement only holds if p for the choice 2022h to I for 7 even smaller. As in the monotone setting, OGDA however, requires a smaller step size than EG. Nevertheless, through a different analysis we are able to match the most general condition on the weak Minty parameter 1 for appropriate and a.
This was later improved in (Pethick et al.
Contribution.
Building on the recently introduced notion of weak solutions to the Minty variational inequality, (Diakonikolas et al. 2021), we prove novel convergence rate of O(1/k) in terms of the squared operator norm for modification of OGDA, which name OGDA+, matching the one of EG.
Even under the stronger assumption that the operator moreover monotone we improve the possible range of step sizes for OGDA+ (Ryu al. 2019) and recover the best known result for the standard method (y 1) [Gorbunov et al. 2022b).
We prove complexity bound of ( for a stochastic version of the OGDA+ method.
Additionally, we propose an adaptive step size version of EG++ which able to obtain the same convergence guarantecs without any knowledge of the Lipschitz constant of the operator F, and therefore possibly even take larger steps regions of low curvature and allow for convergence where fixed step size policy does not.
2

---

Published in Transactions on Machine Learning Research (03/2023)
1.5
EG+ V-0.01
EG+ V-0.01
-GGAA V=0.1
OGDA y=0.1
1.0
squared operator narm
10
0.5
-1.0
15
0
500
1000
1500
2000
operator evaluations
-1.5
-1.0
-0.5
0.0
0.5
1,0
1.5
(a) Performance methods.
(b) Trajectories of iterates.
Figure 1: Problem i with p= +. meaning that convergence not covered by theory. Since the Lipschitz constant can be computed analytically we choose the step size accordingly. Due the linearity of the operator F' there is no benefit in using linesearch, so only methods using constant step sizes are compared. Only OGDA+ converges.
1.1 Related literature
Since there an extensive literature on convergence rates in terms gap function or distance to a solution
for monotone problems well as generalizations such as nonconvex-concave (Bot Böhm 2020 Lin al.
2020), convex-nonconcave (Xu et al.. 2023 or under the Polyak--ojjsiewiez assumption, Yang et al.
2020
will only focus on the nonconvex nonconcave setting.
Weak minty. Diakonikolas et al. 2021 noticed that a particular parametrization of the von Neumann ratio game exhibits a new lype of solution, which they titled weak Minty, without possessing any of the known properties such as (negative) comonotonicity or Minty solutions. They showed convergence in the presence of such solutions for EG if the extrapolation step size is twice as large as the update step. Later Pothick et al. (2022) showed that the condition on the weak Minly parameter of the update step even further and they do so in adaptive way. In order to not require any other hyperparameterss they also propose backtracking line search, which might come at the cost of additional gradient computations or the use of second order information (in contrast to the adaptive step size we propose in hm 3). In (Lee & Kim 2021b) a different approach is taken by restricting the attention to the min-max setting and using multiple ascent steps per descent step, obtaining the same O(1/k) rate as EG.
be relaxed by reducing the length
Minty solutions. Many works have shown different approaches for when the problem at hand exhibits Minty solution, see (VTT). The authors of (Liu et al., 2021 showed that weakly monotone VIs can be solved by succossively adding quadratic proximity term and repeatedly optimizing the resulting strongly monotone VI with any convergent. method. In (Mertikopoulos et al. 2019) the convergence of the OGDA method was proven, but without any rate. In (Malitsky) (2200) it was noted that the convergence proof for the golden ratio algorithm (GRAAL) works without any modification. Seo also (Dang & Lan 2015) for a non-euclidean version of EG and (Liu el al. 2020) for adaptive methods. While the assumption that a Minty solution exists is a generalization of the monotone setting is difficult to find nonmonotone problems that do possess such solutions. In our setting, see Assumption the Minty inequality (MVI) allowed to be violated at every point by factor proportional to the squared operator norm.
Negative comonotonicity. While previously studied under the name of cohypomonotonicity (Combettes) & Pennanen 2004) the notion of negative comonotonieity was recently explored in (Bauschke el al. 2020). It provides a generalization of monotonicity, but in a direction different from the notion of Minty solutions and only a few works have analyzed methods in this setting. The authors of (Lee Kim! 2021a) studied an anchored version of EG and showed an improved convergence rate of (11kk²) (in terms of the squared operator norm). Similarly, Cai et al. (2022) studied accelerated version of the reflected gradient method
3

---

Published in Transactions on Machine Learning Research (03/2023)
Malitsky 2015 It is open question whether such an acceleration is possible in the more general setting of weak Minty solutions (any Stampacchia solution to the VT given by negatively comonotone operator is a weak Minty solution). Another interesting observation was made in (Gorbunov et al. 2022c where for cohypomonotone problems monotonically decreasing gradient norm was shown when using EG. However, we did not. observe this our experiments, highlighting the need to distinguish this class from problems with weak Minty solutions.
investigate the notion of a-interaction dominance for munconve--nonconee min-max problems and showed that the proximal-point method con- verges sublinearly if this condition holds in y and linearly if it holds in both components. Furthermore Lee & Kim (021a) showed that if problem is interaction dominant in both components, then it is also negatively comonotone.
Interaction dominance. The authors of (Grimmer al. 2022
Optimism. The beneficial effects of introducing the simple modification commonly known as optimism have recently sparked the interest of the machine learning community (Daskalakis et al. 2018 Daskalakis & Panageas] 2018 Liang & Stokes 2019 Gidel et al., 2019). Its name originates from online optimiza- tion (Rakhlin & Sridharan 2013a bp. The idea dates back even further (Popov) 1980) and has been studied
in the mathematical programming community as well (Malitsky 2015; Malitsky & Tam 2020 Csctnek al. 2019).
2 Preliminaries
2.1 Notions of solution
We summarize the most commonly used notions of solutions appearing in the context of variational inequal- itics (VIs) and boyond. Note that these are commonly defined in terms of a constraint set C C Rdd. A Stampacchid" (Kinderlehrer & Stampacchia 2000) solution of the VI given by F Fd Rd is defined as a point u" such that
(Fu"),u-ut u²)
Vu E.
(SVI)
In particular we only consider in this manuscript the unconstrained case C 12 in which case the above condition reduces to F(u") O. Very much related with long tradition is the following. A Minty! solution is given by point u" C' such that
uF(u),u-tt
C.E
(MVI)
If F continuous, a Minty solution of the VI is always a Stampacchia solution. The reverse is in general not true but holds for example the operator F monotone. In particular, there exist nonmonotone problems with Stampacchia solutions but without any Minty solutions.
2.2 Notions of monotonicity
The aim of this section to recall some elementary and some more recent notions monotonicity and the connection between those. We call an operator F monotone
(F(u) - F u) 20 0.
Such operators arise naturally the gradients of convex functions, from convex-concave min-max problems or from equilibrium problems.
Two notions frequently studied that fall in this class are strongly monotone operators fulfilling
(F(u) F(),, v) 2 ul|u - v||
SSmettmess Stampacchia and Minty solutions referred strong and weak solutions respectively, see Nesterov 2007 but will refrain from this nomenclature, confusing context of weak Minty solutions.
4

---

Published in Transactions on Machine Learning Research (03/2023)
They appear gradients of strongly convex functions sorerr-oooooeettroooooooooooeeee min-max prob- lems. A second subclass of monotone operators are so-called cocoercive operators fulfilling
(P(u) F(v), u u) F()) F(r)ll?.
(2)
They appear, for example, gradients of smooth convex functions, in which case the reciprocal of the gradients Lipschitz constant.
2 holds with 8 equal to
Leaving the monotone world. Both subclasses of monotonicity introduced above can be used as starting points to venture into the non-monotone world. Since general non-monotone operators might exhibit erratic behavior like periodic cycles and spurious attractors (Hsieh et al.) 2021), it makes sense to find settings that extend the monotone one, but still remain tractable. First and foremost, the by now well-studied setting of y-weak monotonicity
F(), -v/lu - vll..
Such operators arise as the gradients of the well-studied class (see (Davis & Drusvyatskiy 2018 of weakly convex functions- - rather generic class of functions as includes all functions without upward cusps. Tn particular every smooth function with Lipschitz gradient turns out to fulfill this property. On the other hand, extending the notion of cocoercivity allow for negative coefficients, referred to as colypomonotonicity; has received much less attention [auschkk el al. 2020 Combettes & Pennanen 2004) and is given by
(F(u) - F(u), u - u) F()) - F(u)lI.
Clearly, if there exists Slampacchia. solution for such an operator, then it also fulfills Assumption 1
Behavior w.r.t. the solution. While the above properties are standard assumption in the literature, it is usually sufficient to ask for the corresponding condition to hold when one of the arguments is a (Stam- pacchia) solution. This means instead of monotonicity it is enough to obtain standard convergence results, see /Gobunov et al. 2022a), to ask for the operator F to be star-monotone (Pennanen, 2001 , L.e.
(F(u), u u²) 20
or star-cocoercive (Gorbunov et al. 2022a)
(F(u),u- u²) 22222lll [[))1
In this spirit, we can provide a new interpretation to the assumption of the existence of a weak Minty solution as asking for the operator F to be negatively star-cocoercive (with respect to at least one solution). Furthermore, we want to point out that while the above star notions are sometimes required to hold for all solutions u", the following we only require to hold for a single solution.
3 OGDA for problems with weak Minty solutions
The generalized version of OGDA, whose name we equip the spirit of (Diakonikolas et al. 2021 Pethick et al. 2022 with "+" to highlight the presence of the additional parameter 7, is given by:
Algorithm OGDA+
Require: Starting point uo =- Idd, step size >> 0 and parameter 0 0<7 1. for 0, 1,... do d1+1 Utg a (1 (1++7) F(us) - F(un-1)
Theorem 3.1. Let F Rdd dRd be I.-Lépschitz continuous satisfying Assumption 7 with 1 > P and (uR) be the iterates generated by Algorithm ] with step size satisfying p and
1-7 aT <
(3)
7
5

---

Published in Transactions on Machine Learning Research (03/2023)
1.5
OGDA+ Y-0.5
Y-0.5
1040
OGDA+ y=1
OGDA+ y=1
1.0
squared operator norm
10:9.
0.0
-0.
10-1.
-1.0
500
1000
-1.5
operator evaluations
-1.5
-10
-0.5
0.0
0.5
1.0
15
(a) Performance methods.
(b) Trajectories of iterates.
Figure Polar game from Pethick et al. OGDA+.
2022 with
Shows the need to reduce y in
8L
10L
Then, for all k 20
min [((u))] < kuy(a- p) Iluo aF(wo) u²1
i=0,...kk-1
In porticular as long as << + we can find a r small enough such that the above bound holds.
The first observation is that we would like to choose a as large as possible as this allows us to treat the largest class of problems with p << a. In order be able to choose the step size large we have decrease y as evident from (3). This, however degrades the speed of the algorithm it makes the update steps smaller the same effect can be observed (Pethick al., 2022 for EG+ and is therefore not surprising. One could derive optimal y (i.e. minimizing the right hand side) from Theorem 3.1 which however results in uninsightful cubic dependence on p. In practice, the strategy of decrcasing until we get convergence, but not further gives reasonable results.
Furthermore, we want to point out that the condition p < t. precisely the best possible bound for EG+ in [Pethick al. 2022).
3.1 Improved bounds under monotonicity
While the above theorem also holds if the operator monotone, we can modily the proof slightly to obtain better dependence on the parameters:
Theorem 3.2. Let F; Rd + Rd be monotone and L-Lipschitz. If 2-7 E for then, the iterates 2+7
generated by OGDA+ fulfill
min [[[(1]]] ka2228
Iluo + aF(uo) u=" 11.
1 porticular, we can choose and a < 37.
There are different works discussing the convergence of OGDA in terms of the iterates or a gap function with a < , see for example (Malitsky & Tam 2020). We, however, want to compare the above bound to more similar results rates for the best iterate in terms of the operator norm. The same rate ours for OGDA is shown in (Chavdarova et al. 2021) but requires the conservative step size bound was later improved to Σ 1 in (Gorbunov et al. 2022b) where the bound even holds for the last itcrate. 37.
16L This
The only other reference that deals with a generalized (i.e. not necessarily y=1) 1) version of OGDA (Ryu et al. 2019). There the resulting step size condition is a S 2-y, which strictly worse than ours for any 7. summarize, not only do we show for the first time that the step size of generalization of OGDA can go above 1 we also provide the least restrictive bound for any value of 7.
However, all of these only deal with the case >
27

---

Published in Transactions on Machine Learning Research (03/2023)
3.2 OGDA+ stochastic
In this section discuss the setting where instead of the exact operator F we only have access to collection of independent estimators F(+)()) ) at every iteration. We assume here that estimator F is unbiased E [F {i] 4x-1] = F(wx), and has bounded variance ([l, 51) - [ s o², we show that we can still guarantee convergence, by using batch sizes B of order ((=-)):
Algorithm stochastic OGDA+
Require: Starting point uo u-1 Rd step size > 0, parameter 0 y S and batch size B. for = 0, 1,.. do
Sample i..d. (E)) and compute estimator Tu = tO EE F(ux: Et)
uk+1 = uk - a (1 + 7) 9k Āk-1)
Theorem 3.3. Let F Rd + Rd be L-Lipschitz satisfying Assumption with 1 > p and let (ux) the 1-7 147
sequence of iterates generated by stochastic OGDA+, with and y satisfying an E stationary point such that - (u, E\1 S we require
then, to visit
o -
p) B Blluu + año u 11]] max {1, 1.aT
1, 40 11
calls to the stochaslic oracle F, with large batch sizes of order O(s-1).
In practice large batch sizes of order O(E-1) are lypically not desirable, but rather a small or decreasing step size is preferred. In the weak Minty setting this is cause for additional trouble due to the necessity of large step sizes to guarantec convergence. See in this context the hcuristic variant proposed in (Pethick et al., 2022) which decreases the parameter corresponding to y in our setting. Unfortunately the current analysis does not allow for variable 7.
4 EG+ with adaptive step sizes
In this section we present Algorithm 3 that is able to solve the previously mentioned problems without any knowledge of the Lipschitz constant L, it is typically difficult to compute in practice. Additionally, it is well known that rough estimates will lead to small step sizes and slow convergence behavior. However, in the presence of weak Minty solutions there is additional interest in choosing large step sizes. We observed in Theorem 3.1 and related works such as (Diakonikolas et al. 2021) and (Pethick et al.] 2022) the fact that a crucial ingredient in the analysis is that the step size is chosen larger than multiple the weak Minty parameter p to guarantee convergence at all. For these reasons we want to outline a method using adaptive step sizes, meaning that no step size needs to be supplied by the user and no line-search carried out. Since the analysis of OGDA+ is already quite involved in the constant step size regime choose to equip FG+ with an adaplive slep size which estimates the inverse of the (local) Lipschitz constant, see (4). Due the fact that the literature on adaptive methods, especially in the context of VIs is so vast we do not aim to give a comprehensive review but highlight only few with especially interesting properties. In particular we do not want to touch on methods with linesearch procedure which typically result in multiple gradient computations per iteration, such as (Tseng 2000 Malitsky & Tam 2020)
We use simple and therefore widely used step size choices which naively estimates the local Lipschitz constant and forces a monotone decreasing behavior. Such step sizes have been used extensively for monotone 2018 Bot et al., 2020). and similarly in the context of the mirror-prox method which
VIs, see Yang & Liu corresponds to EG in the setting of (non-euclidean) Bregman distances, see (Antonakopoulos et al. 2019).
A version of EG with a different adaptive step size choice has been investigated by [Antonakopoulos et al. (2021;: Bach Levy (2019) with the unique fcature that it able to achieve the optimal rates for both smooth and nonsmooth problems without modification. However, these rates are only for monotone VIs and are in terms of the gap function.
7

---

Published in Transactions on Machine Learning Research (03/2023)
One of the drawbacks of adaptive methods resides in the fact that the step sizes typically required to be nonincreasing which results in poor behavior if a high curvature area was visited by the iterates before reaching a low curvature region. To the best of our knowledge the only method which is allowed to use nonmonotone step size to treat VIs, and does not use a possibly costly linesearch, is the golden ratio comes with the additional benefit of not requiring a global bound on the Lipschitz constant of at all. While known that this method converges under the stronger assumption of existence of Minty solutions, quantitative convergence result is still open.
algorithm Malitsky 2020).
Algorithm EG- with adaptive step size
Require: Starting points wo, uo E 1d initial step size oo and parameter (0,1) and 0 < 7 S 1. for k: 0, l.... do Find the step size:
7 Tlluk=1 21
ak min a 1, | (uu= F
(4)
3: Compute next iterate:
uk = Uk - a ((xx)
u++1 0s ax F(ux)
Clearly, is monotonically docrcasing by construction. Morcover, it is bounded away from zero by the simple observation that ag 2 min(ao. > 0. The sequence therefore converges to a positive number which we denote by Os0 == limm Ok-
Theorem 4.1. Let F Rd + Rd be L-Lipschitz that satisfies Assumption 1 where u² denotes any weak Minty solution, with as > 2p and let (uk)a20 be the iterates generated by Algorithm with 7 and T (0, Then, there exists a hip E N, such that
L
min [F(ux)]
Rx Ukk
u² u²11?
k- TOkKT(55
p)
Algorithm 8 presented above provides several benefits, but also some drawbacks. The main advantage resides in the fact that the Lipschitz constant of the operator F does not need to be known. Moreover, the step size choice presented in 4 might allow to take steps much larger than what would be suggested by global Lipschitz constant if the itcrates never - or only during later iterations - visits the region of high curvature (large local L). In such cases these larger step sizes come with the additional advantage that they allow us to solve a richer class of problems as we are able to relax the condition p < 4E in the case FG+ to p < /x where ax limę dg 2 T/L.
On the other hand, we face the problem that the bounds Theorem 4.1 only hold after an unknown number of initial iterations when 0x/ax+1 I 1 is finally satisfied. In theory this might take long if the curvature around the solution is much higher than in the starting area this will force the need to decrease the step size very late into the solution process resulting in the quotient as/ax+1 being too large. This drawback could be mitigated by choosing 7 smaller. However, this will result in poor performance due to small step sizes. Even for monotone problems where this type of step size has been proposed this problem could not circumvented and authors instead focused on convergence of the iterates without any rate.
5 Numerical experiments
In the following we compare EG+ method from (Diakonikolas et al. 2021 with the two methods we propose OGDA+ and EG+ with adaptive step size, see Algorithm [ and Algorithm 3 respectively. Last but not least we also include the CurvatureEG method from (Pethick al. 2022) which is a modification of EG+ and adaptively chooses the ratio of extrapolation and update step. In addition backtracking linesearch
8

---

Published in Transactions on Machine Learning Research (03/2023)
1.0
solutiion
squarred operator narm
10.11
EG+
OGDAi
EG+ edaptive
19
CurvatureEG.
200
400
operator evaluations
0.0
0.5
1.0
(a) Performance methods.
(b) Sign of (F(u), uuuu--)) u²)
Figure 3: Ratio game. particularly difficult parametrization of suggested in DDskallkiis et al. 2020
Right: The sign of (P(u), u-"") parametrized as == (xr, x, y, y), with yellow representing a negative sign and purple a positive one, highlighting the fact that the solution not Minty, Nevertheless, all methods are able to converge.
is performed with initial guess made by second order information, whose extra cost ignore in the experiments.
5.1 Von Neumann's ratio game
We consider von Neumann's s ralio game (von Neumanm 1945) recently explored in Daskalakis et al. 2020 Diakonikolas et al. 2021). It given by
(x, Ry) (x, Sy)
min max V(a,y) ZEA YEAR
(5)
where R E mmxx and S R with (r, O for all E A" y E A", with A = {= E Red 23 2 0, Ed Ei= = 1} denoting the unit simplex. Expression 5 can be interpreted as the value V Tyy for a stochastic game with a single state and mixed strategies.
In Figure 3b
illustration of particularly difficult instance of discussed in (Daskalakis et al. 2020), highlighting the fact that the Stampacchia solution is not Minty solution, even when restricted to arbitrarily close ball around it (yellow area touching the solution). Interostingly we still observe good convergence behavior, although an estimated is more than ten times larger than the estimated Lipschitz constant.
5.2 Forsaken
A particularly difficult min-max toy example with "Forsaken" solution proposed in Example 5.2 of (Hsieh ct al. 2021) and is given by
min max z(y 0.45) + (px) (p()).
(6)
ZER WER
where (22) f2 + 20 This problem exhibits Stampacchia solution at (x" (0")"") x (0.08, 0.4), but also two limit cycles not containing any critical point of the objective function. In addition, Hsieh et al. (2021) also observed that the limit cycle closer to the solution repels possible trajectories of itcrates, thus "shielding" the solution. Later, Pethick et al. (2022) noticed that, restricted to the box [| y) < 3 the above mentioned solution is weak Minty with p 2 2- 0.477761, which much larger than 1 ~ 0.08. In line with these obscrvations we can see Figure that none of the fixed step size methods with stop size bounded by 1 converge. In light of this observation Pethick et al. (2022) proposed a backtracking linesearch which potentially allows for larger steps than predicted by the global Lipschitz constant. Similarly, our proposed

---

Published in Transactions on Machine Learning Research (03/2023)
adaptive step size version of EG+, Algorithm 8 is also able to break through the repelling limit cycle and converge the solution. On top of this, it does so at faster rate and without the need of additional computations in the backtracking procedure.
10a
EG+
EG+
OGDA
OGDA+
EG adaptive
1.0
EG adaptive CurvaturEG+
squared sperator narm
CurvstureEG-
0.5
0.5
-10
100
200
300
400
4.5
operater
-10
(a) Performance of methods.
(b) Trajectories of iterates.
Figure 4: Forsaken. An illustration of different methods on problem 6 originally suggested by Hsich
et al. 2021). Only A Algorithm 3 and CurvatureFG are able to choose a step size large enough to withstand the repellent limit cycle.
5.3 Lower bound example
The following min-max problem was introduced in (Pethick et al. 2022 between p and L for EG+:
lower bound on the dependence
S (x: y²).
min Ery zER yER
(7)
2
In particular Theorem 3.4 from (Pethick al. 2022) states that EG+ (with any 7) and constant step size + converges for this problem if and only (0, 0) weak Minty solution with p < 7 where p and L can be computed explicitly in the above example and are given by
L -= and p= - 22
Figure [ obtained by choosing & 3 and ( 1 get exactly p and the theory therefore predicting divergence of EG+ for any % which is exactly what is empirically observed. Although, the general upper bound proved in Theorem 3.1 only states convergence in the case < 1 I, we observe rapid convergence of OGDA+ for this example showcasing that it can drastically outperform EG+ in some scenarios.
6 Conclusion
Many interesting questions remain in the realm of min-max problems especially when leaving the convex- concave setting. Very recently Gorbunov et al. (002cc) showed that the O(1kk) bounds on the squared operator norm for EG and OGDA for the last iterate (and not just the best one) hold even the negative question.
comonotone setting. Deriving similar statement in the presence of merely weak Minty solutions is an open
Overall, our analysis and experiments seem to provide evidence that there is little advantage of using OGDA+ over EG+ for most problems as the lower iteration cost is offset by the smaller step size. One exception is given by problem (7) displayed in Figure which is not covered by theory and OGDA+ is the only met hod able to converge.
Lastly, we observe that the previous paradigm in pure minimization of "smaller step size ensures convergence" but "larger step size gets there faster", where the latter typically constrained by the reciprocal of the
10

---

Published in Transactions on Machine Learning Research (03/2023)
gradients Lipschitz constant, does not seem to hold true for min-max problems anymore. The analysis of different methods in the presence of weak Minty solutions shows that convergence can be lost if the step size is too small and sometimes needs to be larger than 7, which one can typically only hope for in adaptive methods. Our EG+ mothod with adaptive step size achieves this even without the additional cost of a backtracking linesearch as used for the CurvatureF.G+ method of (Pethick el al. 2022).
References
Kimon Antonakopoolos, Veronica Belmega, and Panayotis Mertikopoulos. An adaptive mirror-prox method for variational incqualitics with singular operators. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bue, E. Fox, and R. Garnelt (eds.), Advances in Neural Information Processing Systems. volume 32. Curran Associates, Inc., 2019. URL https::/prooceednns wwwprinsnn.eeuris..e... wwwrips..c/ppappeeeee seur1iss.c/ppperr201///1e pdf.
Kimon Antonakopoulos, Veronica Belmega, and Panayotis Mertikopoulos. Adaptive extra-gradient methods for min-max optimization and games. In International Conference on Learning Represenlations, 2021. URL
Francis Bach and Kfir Y Levy. A universal algorithm for variational inequalities adaptive to smoothness and noise. In Conference on Learning Theory, pp. 164-194. PMLR, 2019.
Heinz H Bauschke, Walaa M Moursi, and Xianfu Wang. Generalized monolone operators and their averaged resolvents. Mathematical Programming, pp. 1 20, 2020.
Axel Böhm, Michael SedImayer, Ernö Robert Csetnek, and Radu Toan Bot. Two steps at a time come-ttaie taking GAN training in stride with Tseng's method. SIAM Journal on Mathematics of Data Science, 4(2):750 771, 2022.
Avishek Joey Bose, Gauthier Gidel, Hugo Berard, Andre Cianflone, Pascal Vincent, Simon Lacoste- Julien, and William L. Hamilton. Adversarial example games. In Hugo Larochelle, Marc' Aurelio Ran- zato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Newral Information Processing Systems 33: Annual Conference on Newral Information Processing Systems 2020, NewrIPS 2020, December 6- 12, 2020, virtual, 2020. URL htttps://proceeddnggs http:ppoceeednn.....ei.r.......p www.neww.reeeeeeeeeeeeee /etprr/ps.cppappe//200///////// hashh/
Radu Ioan Bot and Axel Böhm. Alternating proximal-gradient steps for (stochastic) nonconvex-coneaae minimax problems. rrXtc:200713600 2020.
Radu Toan Bot, Michael Sedlmayer, and Phan Tu Vuong. A relaxed inertial forwart-badwark-forwrd algorithm for solving monotone inclusions with application to GANs. arXiv:2003.07880 2020.
Yang Cai, Argyris Oikonomou, and Weiqiang Zheng. Accelerated single-call methods for monotone inclusions and constrained min-max optimization. arXiv preprint arXiw:2206.0524 2022. URL htttp:///arx::
org/paf/221e 03096. pdf
Tatjana Chavdarova, Michael Jordan, and Manolis Zampetakis. Last-iterate convergence of saddle point
optimizers via high-rosolution differential equations. arXiv preprint arXiv:2112. 13826, 2021.
Patrick L Combettes and Teemu Pennanen. Proximal methods for cohypomonotone operatoss. SIAM journal on control and optimization, 43(2):731-742, 2004.
Ernö Robert Csetnek, Yura Malitsky, and Matthew K Tam. Shadow Douglas Rachford splitting for mono- Rouglas-Rachford tone inclusions. Applied Mothematics & Optimization, 80(3):665 678, 2019.
Cong D Dang and Guanghui Lan. On the convergence properties of non-ouelidean extragradient meth- ods for variational incqualities with generalized monotone operators. Computational Optimization and applications, 60(2):277-314 2015.
11

---

Published in Transactions on Machine Learning Research (03/2023)
Constantinos Daskalakis and Ioamnis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information. Processing Systems, pp.
2018.
Constantinos Daskalakis, Andrew Lyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference on Learning Representations, 2018. URL http:p:://opeeeevivv.eeeeeeee//e wtt.h/ewwwwe//ffurrrree 1d=SJJySbbAZ
Constantinos Daskalakis, Dylan Foster, and Noah Golowich. Independent policy gradient meth- ods for competitive reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Bal- can, and H. Lin (eds.), Advances in Neural Informalion Processing Systems, volume 33, pp. 5527- 5540. Curran Associates, Inc., 2020. URL BB220t548810000666663333//333333 .dff
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min- max optimization. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. pp. 1466-1478, 2021.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges at the rate 0(k-1/4) on weakly convex functions. arXie preprint orXiv: 02988, 2018.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured noneonvex-nonconcawe min-max optimization. In International Conference on Artificial Intelligence and Statistics, pp. 9746-2754. PMLR, 2021.
Francisco Facchinci and Jong-Shi Pang. Finite-dimensional variational inequalities and complementarity problems. Springer Science & Business Media, 2007.
Gauthier Gidel, Hugo Berard, Gačtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. In International Conference on Learning Rep- resentations, 2019. URL
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua. Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pp. 2672-2680, 2014.
Eduard Gorbunov, Nicolas Loizou, and Gauthier Gidel. Extragradient method: O(1/k) last-iterate conver- gence for monotone variational inequalities and connections with cocoercivity. In International Conference on Artificial Intelligence and Statistics, pp. 366-402. PMIRR 2022a.
Eduard Gorbunov, Adrien Taylor, and Gauthier Gidel. Last-iterate convergence of optimistic gradient method for monotone variational inequalities. 2022b. URL
ottp:///..rraaa//225555555 08446
Eduard Gorbunov, Adrien Taylor, Samuel Horváth, and Gauthier Gidel. Convergence of proximal point and extragradient- based methods beyond monotonicity: the case of negative comonotonicity. arXiv preprint urXiv:2210.1388 2022c. CRL http:://axxxv..ogabb////// 13831v1
Benjamin Grimmer, Haihao Lu, Pratik Worah, and Vahab Mirrokni. The landscape of the proximal point method for nonconvex nonconcave minimax optimization. Mathematical Programming, pp. 1 1-35, 2022. URL httpgss//arxiv..rr//f///00...
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min- max optimization algorithms: Convergence spurious non-critical sots In International Conference on Machine Learning, pp. 4337- 4348. PMLR, 2021.
Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In H. Larochelle, M. Ran- zato, R. Hadsell, M. F. Balcan, and H. Lin (ods.), Advances in Neural Information Processing Systems, volume 33, pp. 16223 16223-16234 Curran Associates, Inc., 2020. URL http::///pooocccignneooee
12

---

Published in Transactions on Machine Learning Research (03/2023)
David Kinderlehrer and Guido Stampacchia. An introduction to variational inequalitics and their applica- lions. STAM, 2000.
GM Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12: 747-756, 1976.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvex--nonconcaaw minimax problems. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (ods.). Advances in Newral Information Processing Systems, 2021a. URL http:////ppppeeeeeeeeeee/ooornnn
Sucheol Lee and Donghwan Kim. Semi-anchored multi-step gradient descent ascent method for structured nonconvex--noeccoeaww composite minimax problems. arXiv preprint or arXic:2105.1504. 2021b.
Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In Kamalika Chandhuri and Masashi Sugiyama (cds.), The 22nd Inter- national Conference on Artificial Intelligence and Statistics, volume of Proceedings of Machine Learning Research, pp. 907- 915. PMLR, 2019.
Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex-conceve minimax problems. In International Conference on Machine Learning, pp. 6083 6093. PMLR, 2020.
Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms in generative adversarial nets. In International Conference on Learning Representaltins, 2020. URL http:///pppneeeeeeeeeeee/rrrrrep
Mingrui Liu, Hassan Rafqque, Qihang Lin, and Tianbao Yang. First-order convergence theory for weakly- convex-weakly-coneeve min-max problems. The Journal of Machine Learning Research, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018. URL httts::/opperreviet wwt.://orrrmiddrrr..12B1..21111
Yura Malitsky. Projected reflected gradient methods for monotone variational incqualitics. SIAM Journal on Oplimizalion, 25(1):502 520, 2015.
Yura Malitsky. Golden ratio algorithms for variational incqualities. Mathematical Programming, 184(1): 383-410, 2020.
Yura Malitsky and Matthew K Tam. forward- backward splitting method for monotone inclusions without cocoercivity. SIAM Journal on Optimization, 30(2):1451-1472, 2020.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile. In International Conference on Learning Representations, 2019. URI. https:://penreviee.nee////
id=Bkg8jJC9KU
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference Arlificial Intelligence and Slatistics, pp. 1497-1507. PMLR, 2020.
Yurïi Nesterov. Dual extrapolation and its applications to solving variational inequalities and related prob- lems. Mathematicnl Programming, 109(2-3):319 344, 2007.
Teemu Pennanen. On the range of monotone composite mappings. Journal of Nonlinear and Convez Analysis, 2(2), 2001.
Thomas Pothick, Puya Latafat, Panos Patrinos, Olivier Fercoq, and Volkan Cevher. Escaping limit cycles: Global convergence for constrained nonoonvex-nonconcare minimax problems. In International Conference on Learning Representations, 2022. URL. http::://opaarreii...eeet//////p vhkAMARK
13

---

Published in Transactions on Machine Learning Research (03/2023)
David Pfau and Oriol Vinyals. Connecting generative adversarial networks and actor-critic methods. arXiv preprint 161000100 2016.
Leonid Denisovich Popov. A modification of the arrow-hurwizz method for search of saddle points. Mathe- matical motes of the Academy of Sciences of the USSR, 28(5):845-88) 1980.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Annual Conference Learning Theory, pp. 993-1019, 2013a.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Newral Information Processing Systems, pp. 3066-33 1066-3074, 2013b.
Ernest K Ryu, Kun Yuan, and Wotao Yin. Ode analysis of stochastic gradient methods with optimism and anchoring for minimax problems and GANs. arXiv preprint ar Xix::1905. 10899, 2019.
Paul Tseng, A modified forward-backwar splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, (8(2):4314445) 2000.
John von Neumann. model of general economic equilibrium. The Review of Economicc Studies, 13(1):1 9, 1945.
Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient projection algorithm for nonconvex concave and convex nonconcave minimax problems. Mathematical Programming, pp. 1-72, 2023.
Jun Yang and Hongwei Liu. A modified projected gradient method for monotone variational inequalities. Journal of Optimization Theory and Applications, 179(1):197 211, 2018.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimization for a class of nonconvex--nncooccaee minimax problems. arXie preprint arXiv:2002.09621 2020.
A
Omitted proofs
A.1 OGDA+
For convenience we will sometimes use the notation 9k for F(ux) for all -1 Lemma A.1. Let (ux) be the sequence of iterates generated by Algorithm 1 then
|| + agg =u² == 11 + ag:-1 - u 1²1 3 a>yllgg 1| 4ay
(gx
9k u1 ux+1)
(8)
(2 1)]lu[+1 un 1| a² 2y
11.
Proof. From the update of the method we deduce for all k k
||al1 + agk u²1 f==
||ux a7gh + agg- 12
||us + agk-1 - u 1/2 2(ux u2, (agg)) - (2agk-1 - a7gh: a7gas
(9)
|lux + agk-1 -
-u" u²1 222 + axp 1 (2agk-) - a7gk,, a7(g)>
where we used the weak Minty assumption to deduce the last incquality. It remains to derive the following equality
(2agk-1 a7gg, atgg) 4ay 1, Uh Uk+1)
1)] -1 uk 1|
(10)
-a -a²(1 27 -)) 9h 112
This can be seen by expressing every difference of iterates in terms of gradients according to Algorithm giving
4ar - (gt gk 1: us uk+1) = 4ay - - 9k-1, a(gx- - gk-1) 1) + aTg*)
= -4a2--11 gk- 112 + 4a 2 9h gk-1)
14

---

Published in Transactions on Machine Learning Research (03/2023)
and
(2 1)]lu++1 uzll
(1 27 1 gk aggk 1|
= (a² -2a² - gk 212 + (2)a² - 4aa 9h 9k-1) + (a²n² - -2a2))
= (a² 2 9h 1 + (gh, (a²n² 4a²)g; (2ya² 4a² ggh-1)-
Adding the previous two equalities to -a² (1+27 11 1 proves 10 Combining the desired statement.
and 110 proves
We are actually going to show a slightly more general version of Theorem 3.1 which introduces an additional parameter X. Note that for X = y we recover the statement of Theorem 3.1 This allows us to cover the analysis of the monotone case one proof. In particular close to zero will yield the statement of Theorem 3.2
Theorem A.1. Let F Rd Idd be L-Lipschitz continuous satisfying Assumption 1 where u' denotes any weak Minly solulion, with ady p for some 0 S 2y- and let (uk)220 be the sequence of ilerales generated by Algorithm with
ab 5 Xy Ap-2
(11)
2 xy +7
Them, for all k 20
[(u))11
karla>> p) lluo + aF(u)) - u²112.
k 1=
In porticular as long as p < 1, we can find a small enough y such that the above bound holds.
Proof. Using the definition us+1 we can express
a7gh 4t uk+1 - ad(gk 9k-1).
(12)
By applying norms on both sides we obtain via expansion of squares
a² x² 1| = Al|u841 - uxll? + a² Allsk - 9k-1 + 2a)(uut1 - Uk. -x-2)-
(13)
Adding
13 and Lemia A.1 we deduce
|u++1 + agk - u" 1²1 an(a>y 11l S l|ue agh-1 - u² 1²112 d² +2 2, A)l1gn 9k-1 112
(27 A)]lux+1 - ux.12 + (Aay 2ad)( ux+,, Ih Th 9h-1). (14)
Now, we get via Young's inequality
(4y- 2ad)(u us+1, 9k - 9k 9k-1) S aL(22 N)llux - u441 +=- A) - 112
Combining the previous two inequalities
|ux+1 + agk - 12 + a>(a;> - p11g0)1 S |lu + agk-1 - 2²12
+ (aL- 12- - A) - 0² 2y - >))llg 1 2 (2r X La(27 x))1 -uxl?
(15)
We now use the Lipschitz continuity of F to deduce that
|uu+1 + aga - 2²112 - < llu + agk-1 22 12
(a) 2 2- x))l(u Un 2 12 La x)) uxll
2ttriclyy speaking would have assume that the before 119k 9k-2ll2 2 positive, but if it. is we can just discard and be done with the proof.
15

---

Published in Transactions on Machine Learning Research (03/2023)
The fact that the terms can be telescoped is, with La equivalent to
27 2 - (2a7 ad) 2 -a o²>+
which can be simplified to
-(44 + -
By solving for a we get the condition
- 1 -Y a x - 7
(16)
1 1 where from the condition -
- (2ary aA) 2 we deduce a S
2-A5-2 2- which redundant in
light of 16 The statement follows since we chose My = u-1-
A.2
Improved bounds under monotonicity
For the readers convenience we restate the theorem from the main text.
Theorem 3.2 Let F; IRd + Rd be monolone and L-Lipschitz. al 2-2 8 for 6 0 then, the iterates 247
generated by OGDA+ fulfill
2 kaR22e Iuo + -
F(u)))l
- 1211
h 1=0
In particular, we can choose and < 1
3L
Proof of Theorem 3.2 From Theorem A.1 and the fact that aL 2-2 we need to find appropriate
7+2
>> 0 such that al < 2-x
2-A9-2 Given 8 0 we therefore aim to find A > 0 such that
2 7 1 1 2 - x 7
(17)
By bringing both terms on one side and the same denominator obtain the condition
2Ay² (7 + 2)(7 + 2 2-) E.
(18)
Using the fact that À < 27-1 and 7 2 we can upper bound the left hand side by Choosing & therefore ensures that the necessary condition on the step size (16) is satisfied and at the same time yields the dependence on in the denominator of the right hand side in the statement of the theorem.
A.3 OGDA+ stochastic
For the stochastic analysis we use for convenience the notation ARt1 E[[lue+1 wxll?] and 5²
E E E() F(ux)11].
Lemma A.2. Let (ux) the sequence of iterates generated by stochastic OGDA+, then, for any X>
La+1 ar(a - p)B [1gx L 2(1 2) (1 +1+ -CAA
where Ō = max a2 } and 1
16

---

Published in Transactions on Machine Learning Research (03/2023)
Proof of Lemma A.2 From the update of the method we deduce for all k 2 0
F ||] + agk u ]
|u - aÿタı + oğk-1 u²11
E |k + agk-1 - u²112 (2ağk-1 agk, a7gk) 2alE - uu, ,9x)]
(19)
< E Iuy + ağk-1 u²11 2 + a>pllall (20ğk-1 argk a7gx){,
where we used
u u", [k)] = 2 - u gnh ux]l = 21D((ux - u², gx))=)] 2 p |19h|1
to deduce the last inequality. It remains to note that
-20gk-11 argg, ar)g)) 4ay (gx 9k-1, uk uk++1 (2y 11]11/// 2k Uu 11
(20)
-a² -a²(1+ (1+ 27 11 - 5k-111
which follows immediately the way deduced 10
Now using the definition of uk+1 get
a²>yE [[xx = a a |
u +E |a 3x-1)l1 + 2ay 1 ub IN E1:
u=]l s <a>xE[10xx11
|?2] = 1
(21)
9x-1)) 1)
Combining
19
21
deduce
E [u++1 + aik u [1'] + aaaaa p0 [11a011]] & BB[lux wu + agı- - -='ll"] a²(1 + 1E - Th [1
(x
12 + 2ay "B((uu ua+1 -N DN- 1})
We get via Young's inoquality
2a0 (ux uk+1. 9h- - 96-1) S Liluu - ux+1ll L 1-- -1-1112
Combining the previous two inequalities
E [14+1 + agı u =='l²] + ar/la [199 S [[llux uu + agı- - =u'1]
(L aL- a²² + [[]ae -x-1 11
Lay ") ux 13]. (22)
Next, we need to estimate the difference of the gradient estimators via the difference of the true
1b 1--112-
1 + 1lxk 9x-111 + +1 + A)1lgk Ōh + hh-1 91-1
+
13 -4-111 2(1 + A) (1gg Jull² + 1lār-1 9k- Ik-
where we used the Lipschitz continuity of the operator. Therefore, by taking the expectation, we obtain
1 x E 11 21-1 < (1
L' L2E(llu u 4(1 A)02.
(23)
Plugging
23
into
22
we doduce
E ub+1 + agx u 201 tay ()) < El + agk-1 - 4² (1++
(1
max 0, (Lay - -a2 2)
A. A. ( aby A
17

---

Published in Transactions on Machine Learning Research (03/2023)
Theorem 3.9 Let F - Rd be L-Lipschitz satisfying Assumption 1 with 1. > p and let (u=)x20 be the
sequence of itcrates generated by stochastic OGDA+, with a and y satisfying p < a < 1-y 14y
then, to visit
an e stationary point such that oi..k [[I S e we require
o ( a b B[luu + ago u 11 max (I, 4 2
at +
calls to the stochastic oracle, with large batch sizes of order O(e
Proof. Let us first note that the condition a s second term in the maximum
implies that the positive part C₁ is redundant as the I4y
1
oy a + (-'-1-10++7))
1-2 1+7 1
7 + (7-1-7) - ) 2 0,
1 1+7
is already nonnegative. Next remark that the statement
(1+
(24)
for some À >>0 0 is equivalent to C₂ > Ci (with strict inequality). This is, however, precisely the condition of
Theorem A.1 but with strict inequality, which the reason why we require the strict inequality a 1-7 to I47
ensure 24 So we can iteratively apply the statement of Lemma A.2 to deduce
k-1
an(a- p) || s E[lluo + ago - a =²1 4(1
o
We still need to estimate X-1 to find the right batch size in order to decrease the last summand to the desired accuracy. By considering 24 we get
7 ay asl - ay 1 < C a(7-1- - - 11 S a(7-1 - ay-1) a
(1+A-1)
By taking B == max(1, 1o' as
independent samples per iteration, we get the variance
00e
and thus arrive a total oracle call complexity claimed.
A.4 EG+ with adaptive step size
Lemma A.3. Let Rd + Rdd be L-Liscchitz and satisfy Assumption 1 by Algoritlom 3 it holds that.
Then, for the iterates generated
7 [itt1 22 S x 1 1 u²1 ax(0x((1 - - -))])]][((u)]]
Tak
(11v4 - Tx + Ilue x
(25)
ax+1
Proof of Lemma A.3 We start by using Assumption I splitting the following term into three
p [((u))]1 < ((xx)(ux) uy u²)
(26)
= (ax F(u), ū+t1 w²) + F(ux) us - ūx+1) + ax (F(ux) F(ūx). us - uxt1).
By expressing F(ux) via the definition of ux41 and the three point identity we obtain
(ar (ux), ukt1 u²) = 7 (ūg us+1 uk+1 u²)
-- (llūg - u u²112 || - 2x | - u 11
(27)
2
18

---

Published in Transactions on Machine Learning Research (03/2023)
Similarly, by expressing F(ūg) via the definition of un deduce
(ax F(x), up U&+1) = (ūx uk, ug Uk+1)
(28)
(lux+1 uxll - -1/ux ux 11ux 113+
Lastly, via the Sauchy-Schward inequality
(F(F(us) - F(ux), up uk+1) S (us) - P(ux)] ||/ - ux+1ll
T&
U1g
ux 1/ Tx+1ll
(29)
0
(llux ux + l/uce - ux+1ll
20
Combining 26 to 29
and multiplying by 2 we get
el[F(u))]1 S 7- (1 u²11 || ==1l²) (7-1 1-)1-1)(laa; 1)]1@a+1 ux
Tak
(Ilux Tx|1 + 1/ u6++ 112)
ax+1
Using the observation that you ((ux)= = ūx+1 - -ik gives
7- >' u²11 on (au7(11 - -P)][P(ux))1 s>-111 w ==11
(1 ax+1
Tap ) (1lux xxel 21 + 1lue ux+1 113.
We see that the largest possible range for is achieved for 7 = 2"
Theorem 4.1 Let F RRd + Rd be L-Lipschitz that satisfies Assumption where u² denotes any weak Minty solution, with 0 > 2p and let (ux) be the iterates generated by Algorithm 3 with = and T (0,1) 1). Then, there exists a Ko E N, such that
L
min [F(ue)]2
Ukkk u 11
K k-
T
ko
Proof. As converges to aso, the quotient a#/ax+1 converges to 1. In particular, there exists an index Ko E such that as/ax+1 I for ko, because T 1. We can therefore drop the last term 25 and sum up to obtain
|
201
Σ k=
a. -p) 1)FF(()))11 < (0 =2 0s
The desired statement follows by observing that a, 2 ax 2 T/L.
Note that the above proof for the adaptive version of EG+ provides an improvement in the dependence between p and over the analysis (Diakonikolas et al., 2021 even the constant step size regime.
B Additional statements and proofs
For the sake of completeness provide proof of the elementary fact that Minty solutions stronger requirement than Stampachia solutions.
Lemma B.I. If F is continuous then every Minty solution is also Stampacchia solution.
19

---

Published in Transactions on Machine Learning Research (03/2023)
Proof. Let w be solution to the Minty VI and ax" + (1 a)u for an arbitrary E I and a E (0, then
(F(ow" + (1 a)u), (1 - au w²)) 2 0.
This implies that
(1 (F + (1- a))); ; (u w²)) 2 0.
By dividing by a1 and then taking the limit -+ we obtain that w is a solution of the Stampacchia formulation.
]
C Numerics
For all experiments, if not specified otherwise, we used for OGDA+ and the adaptive version of FG+ the parameter 7 3.. For the step size choice of Algorithm 3 use 0.99. For the CurvatureliG+ method of (Pethick et al. 2022 (with their notation) we use 6ş equal to -p/2, where i the weak Minty parameter, if it is known and less than 1/L; and -0.499 times the step size, otherwise. Furthermore we set the parameters of the linesearch to 7 = 0.9 and v = 0.99.
C.1 Ratio game
The data used to generate the instance displayed in Figure was suggested in DDskallkis et al. 2020) and is given by
-0.6
-0.3
R
0.6
-0.3
and
0.9
0.5
=
0.8
0.4
This results in the following objective function for the min-max problem
V(r, v) = -122r + 0.9y - 0.3
0.4y + 0.1. + 0.4
which gives rise the optimality conditions
-0.12** 0.39x + 0.48
and
-0.48y² 0.57y + 0.03
with the solution (x",y") (0.951941, 0.050485). For the experiments we used an estimated Lipschitz constant L
In Figure we can see the reason for the slow convergence behavior of the Curvature&G method observed in Figure Not only is the step size computed by the backtracking procedure smaller than the one choscn by adaptive EG+, see 44, also the second step (update step) uses an even smaller fraction of the already
smaller extrapolation step size.
C.1.1 Polar Game
For Figure we used the so-called Polar Game introduced in Pethick et al. 2022 which is given by
F(x, 3) = (v/(,, y) y, ()) + æ).
(30)
where (x., v) = 1 az(1 + x² + ) + 16x² + 16y?) and parameter a > 0. In Figure 2 we used
1
3.
20

---

Published in Transactions on Machine Learning Research (03/2023)
0.5
OGDA=
OGDA+
adaptive CurvatureEG-
1.5
adaptive
extraplltton uposta
CurvatureEGG+
0.4
stop size
1.0
0.5
0.2
0.0
200
400
200
400
operator evslustions
operator avaluations
(a) Ratio of extrapolation to update step
(b) Extrapolation step size.
Figure 5: Ratio game. An illustration of the step sizes used by different methods, as well as the ratio of extrapolation to update step. CurvatureEG+ chooses its own ratio adaptively and does so for this example in scemingly overly conservative way, resulting in slow convergence observed in Figure
21


Reviews:
[{"review_id": "DUvI0hP9ox", "reviewer": "Reviewer_dg7N", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is very well written, and the presentation is very clear. The introduction and the preliminaries clearly explain the problem, the concept of weak Minty and its connection to monotonicity, and the contribution in light of previous works (which I summarized in the previous paragraph). I appreciated to read this part and I believe that it could even be the beginning of a review paper on the topic.\n\nThe theoretical claims are cast in theorems (summarized above) proven in the appendix. The only issue I see is that the convergence rate of the adaptive algorithm holds after an unknown number of iterations $k_0$. The proofs are rather standard optimization proofs, but clearly presented. \n\nFinally, some honest simulations show the advantage of each proposed algorithm: the advantage of the adaptive method over the others on a toy problem exhibiting a repelling cycle around the solution, and a comparison of EG+ and OGDA+ (proposed algo) where, on some problem OGDA+ is better, and on some difficult instance of a min max problem from (Daskalakis et al. (2020);\nDiakonikolas et al. (2021)) EG+ is slightly better.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of finding a zero of an operator that is negatively cocoercive wrt a solution $u^*$. In other words, there exists a weak Minty solution of the problem $u^*$.\n\nThe main contribution is to develop a modification of OGDA called OGDA+ which provably converges at the rate $1/k$ in terms of the squared operator norm. In comparision, Diakonikolas et al 2021 recently developed a modification of the Extra Gradient algorithm called EG+ that matches the rate $1/k$. It was not known if such a modification could be applied to OGDA which is a concurrent algorithm to EG.\n\nThe authors also develop an adaptive version of EG+ which does not require the knowledge of the Lipschitz constant. However, the established convergence rate holds after an unknown number $k_0$ of steps. \n\n\n\n\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "\n\nParagraph after Th 3.1. Given a step size $a$, what is the optimal value of $\\gamma$ ?\n\nAs I said, the preliminaries are well written but I have a small question:\nmonotonicity implies star-monotonicity, however, negative cocoercivity does not imply negative star cocoercivity (because $F(u^*)$ might not be equal to zero), am I correct? So, negative star cocoercivity is not a generalization of negative cocoercivity. \n\nIn general, it is not clear to me that the operator is zero at a weak minty solution, i.e. $A(u_k) \\to A(u^*) = 0$ (which should be true since you look at the squared operator norm).\n\nFirst sentence after Th 3.3. What is the connection between large batch size and large step size?\nOne call to the stochastic oracle is computing $g_k$ or $F(u,\\xi)$?\n\n\n\n\n\n**Typos**\n\n\"we have to decrease $\\gamma$ as evident from (10)\". From (3) I guess?\n\n\n\" more then ten times\"\n\n \"problem (30) displayed in Figure 1.\" In general, check the numbering of the equations.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8d0pd9NwXJ", "reviewer": "Reviewer_QNP8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": " Strengths： This paper brings some new insights for solving variational inequalities. The authors prove the complete convergence and theoretical advantage of their proposed algorithms.\n\nHowever, some weaknesses prevent me from voting acceptance of this paper.\n\n1. The weak Minty solution is a direct weak version of cohypomonotonicity [Bauschke et al. (2020); Combettes & Pennanen (2004)], which greatly weakens the novelty.\n\n2. The authors fail to explain the necessity of studying the weak Minty solution problem. What kinds of machine learning problems enjoy such a property? Why are we interested in this property?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the optimistic gradient descent ascent (OGDA) for a class of structured variational inequalities problems and its applications to the min-max problem. The major difference lies in the weak Minty assumption. The authors present the convergence of the proposed algorithm in both deterministic and stochastic cases. Under the stronger assumption that the operator is even monotone, the authors show that the algorithm could use large step sizes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The authors need to explain the necessity of studying the weak Minty solution problem. More specifically, they need to provide sufficient conditions to check the weak Minty property. What kinds of machine learning problems enjoy such a property?\n\n2. They need to explain the difference between cohypomonotonicity and weak Minty property, that is, at least providing some examples that are weak Minty but not cohypomonotonic.", "broader_impact_concerns": "I do not find any ethical concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "fFY1ekTY00", "reviewer": "Reviewer_LpsF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n1. All the results are correct and new. I have checked the proofs in detail and found only minor inaccuracies. Overall, the paper is well-written as well.\n\n2. For OGDA+ the authors derive $O(1/k)$ convergence rate for any $\\rho < 1/L$ (here $\\rho$ is the weak Minty constant and $L$ is Lipschitz constant). This matches the best-known results for EG obtained by Pethick et al. (2022). It is worth mentioning that the proposed analysis differs from the existing ones known for OGDA and EG.\n\n3. The authors propose a version of EG+ with adaptive step size and derive $O(1/k)$ convergence rate for the proposed algorithm for finding weak Minty solutions. The proposed method shows good performance in the experiments as well. \n\n## Weaknesses\n\nIn my opinion, weaknesses are minor and are outweighed by strengths.\n\n1. (minor) The stochastic version of OGDA is analyzed only in the case of large $O(\\varepsilon^{-2})$ batch sizes. Although it is a known problem of deriving $O(1/k)$ convergence rates in terms of the (expected) squared operator norm without using large batch sizes for stochastic EG and OGDA (even in the monotone case), it would be good for the paper to add this discussion somewhere in the text, e.g., right after Theorem 3.3.\n\n2. (minor) The rate for Theorem 4.1 is derived only for $k > k_0$, where $k_0$ is unknown in general. Is it possible to estimate $k_0$ somehow at least under some additional assumption? It would be interesting to have some upper bound on $k_0$ in some special cases (e.g., for monotone problems).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The work focuses on weak Minty solutions of Lipschitz operators. The authors consider three methods: Optimistic Gradient Descent Ascent (OGDA) also known as Popov's method, its stochastic version, and the adaptive version of the celebrated Extragradient method (EG). The convergence is proven with respect to the averaged squared norm of the operator. The authors also provide several numerical experiments showing that OGDA can converge for some weak Minty problems when EG fails and illustrate the advantage of using the new version of adaptive EG.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Requests\n\n1. If I am not mistaken, the analysis relies on the fact that the solution is unique. I suggest adding this clarification to the paper. Can the analysis be generalized to cover the case when there are multiple solutions (e.g., when (1) holds only for the closest solution to the considered point $u$)?\n\n2. Page 2, \"it is necessary that step size is larger than a multiple of $\\rho$\": could the authors provide references supporting this claim?\n\n3. Page 2, the same paragraph: the result of Pethick et al. (2022) holds for any $\\rho < 1/L$.\n\n4. After inequality (2), \"they appear as gradients of smooth convex functions\": I think it is important to mention that cocoercive operators are not necessary gradients of smooth convex functions (e.g., rotation operators with acute angles). The current formulation can confuse a reader.\n\n5. Section 3.2 requires some formalization: I suggest adding the pseudocode of the method and explicitly showing that it uses mini-batches.\n\n6. Could the authors provide a complete derivation of the first formula in the proof of Theorem 3.2?\n\n7. At the end of the proof of Theorem 3.2, the authors refer to the lemma of Opial. Can the authors provide a reference and complete formulation in the appendix?\n\n8. Can the authors elaborate on how the last inequality from the proof of Lemma A.2 implies the statement of the lemma? For example, I believe one should mention that $a \\leq L\\gamma$ to get this result and also write $\\max(0, \\ldots)$ in front of $\\sigma_{k-1}^2$ in the last inequality from the proof (similarly to the factor in front of $\\Delta_k$).\n\n9. Proof of Theorem 3.3. I request the authors to provide a complete derivation and formalize a bit the proof. In particular, the derivation of $\\tilde{C}_2 \\geq \\tilde{C}_1$ is missing, instead of $||u_1 - u_0||^2$ one should have $\\mathbb{E}||u_1 - u_0||^2$, and in (22) it should be somehow reflected through the notation that summands denote different samples.\n\n## Suggestions, comments and questions\n\n1. How is Theorem 3.2 related to the existing results for OGDA?\n\n2. Is there a way to justify the necessity of large batch sizes in Theorem 3.3?\n\n3. Why are $u_{k-1}$ and $\\bar{u}_{k-1}$ used in line 2 of Algorithm 2 to estimate the Lipschitz constant? From my understanding, it mostly comes from the analysis, but it would be good to understand whether there is another reason explaining why we should use this pair of points, e.g., why \n\n$\\bar{u}_k, u_{k-1}$\n\nor \n\n$\\bar{u}_k, \\bar{u}_{k-1}$\n\nare not used instead? Some numerical comparisons of different modifications can also be very interesting to see.\n\n4. I suggest repeating the formulations of the theorems in the appendix right before their proofs for the readers' convenience (e.g., in Appendix A.2).\n\n## Minor comments\n\n1. The last word of the abstract (\"paragraph\") should be removed.\n\n2. Theorem 3.1, last sentence: \"$\\gamma$ small enough\" $\\to$ \"small enough $\\gamma$\".\n\n3. Theorem A.1, \"Let ... and $(u_k)_{k\\geq 0}$ {\\color{red} be} the sequence\": here \"{\\color{red} be}\" is missing.\n\n4. The authors missed periods after some formulas, e.g., (15), formula between (19) and (20), (20).\n\n5. Lemma A.2, the second term in the left-hand side: factor $\\gamma$ is missing. Moreover, $L_k$, $\\sigma_k$ and $\\tilde g_k$ are undefined.\n\n6. Formula after (19): expectation is missing in the right-hand side.\n\n7. The last step of the proof of Lemma A.3: it is better to write a complete derivation (though it is correct and can be verified). Also, it is better to explain why the choice of $\\gamma = 1/2$ is the best and in what sense. I guess this is because it makes the factor in front of $||F(u_k)||^2$ as large as possible in the proof. However, there are other terms dependent on $\\gamma$ as well.", "broader_impact_concerns": "I have no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ox1Ug6li6k", "reviewer": "Reviewer_aS3x", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In my opinion, it is far-fetched to motivate such problems by GANs or adversarial networks. At the same time, there are few other classes of operators that have clear potential. For such classes of operators, the paper does provide a meaningful result.  However, the paper writing has to be improved quite significantly.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies unconstrained min-max problems which have at least one weak-Minty solution. For such problems the authors study an extension of the optimistic gradient descent-ascent algorithm and show that it converges in a slightly larger parameters regime than the extragradient method. The authors also show the same convergence rate as for the latter method. Some other results were also introduced, but I think they were less important.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "First of all, I do not understand why the paper's lines are not numbered. I only hope it was not authors' fault. More seriously, here is the list of questions:\n\n1. Abstract. How can we oppose \"recently introduce\" and \"able to capture\"? Also   \"paragraph\" in the end?\n2. First paragraph, page 1: \"an assumption\", not \"a\".\n3. Paragraph \"About the weak Minty...\", page 2. Any positive number is a multiple of $\\rho$. It is not entirely clear to what  $\\frac{1}{2L}$ refers: to $\\rho$ or to the bound on a step size?\n4. page 2: What is \"even monotone\"? Do we also have \"odd monotone\"? What does it mean \"significantly improved\"? From 0.1 to 1000?\n5. \"Operator norm for monotone problems\", page 3. There is no need to mention all non-interesting intermediate results. The goal is to make a paper more readable and not to please all potential reviewers.\n6. In general, I feel that  the number of citations is unnecessarily large. A lot of results for which the authors refer are quite trivial. For example, in page 6, the last two display equations are obvious, there is no need to mention another two papers that used them. There are plenty of such cases.\n7. Why do we even need to introduce what VI is? We work exclusively with the equation $F(x) = 0$. Why do we need strong monotonicity or cocoercivity? Do we use them in the paper?\n8. page 4 (bottom), \"solution operator\" is not  defined.\n9. page 5, why subgradients? We define $F$ to be a single-valued operator.\n10. page 5, paragraph after Eq. 2. What is the point of this discussion? What has it to do with the paper's topic?\n11. \"very ill-behaved\"?\n12. smooth and $L$-smooth are different classes of functions.\n13. Theorem 3.1: Why not to optimize over $\\gamma$? This will give a more clear dependence on $\\rho$ and $L$.\n14. \"Effective step size\"?\n15. Theorem 3.2 is confusing. Isn't $\\frac{1}{2L}$ the upper bound for step sizes when $\\gamma = 1$? If I am right, I don't think it is that nice to formulate the theorem knowing in advance that with a bit more efforts one can improve it.\n\n16. I would not call Algorithm 2 as adaptive. This is how a term might lose its meaning. In this way, the subgradient method is adaptive or any method with linesearch is adaptive. Adaptivity and not requiring to know $L$ are quite different things. I don't think that a method with decreasing steps should be called adaptive.\n\n    Also, its advantage is slightly overstated. Its theoretical convergence requires $a_{\\infty}> 2\\rho$ which in turn require us to know $L$.\n", "broader_impact_concerns": "...............", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Dear authors,

The reviewers agree that this is a good paper the community will benefit from. The paper tackles an interesting problem and is very well written. I agree with the recommendation of the reviewers, and recommend acceptance. Please apply the most reasonable changes requested by the reviewers for the camera-ready version of the paper. Most of them are very minor.

Congratulations and thanks for submitting your work to TMLR!

Bets regards,

Action Editor TMLR
Decision: Accept (poster)