Solving Nonconvex-Nonconcave Min-Max Problems exhibiting Weak Minty Solutions

Introduction

The recent success of machine learning models which can be described by min-max optimization, such as generative adversarial networks , adversarial learning , adversarial example games or actor-critic methods , 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 is nonconvex in the minimization and nonconcave in the maximization component remains theoretically poorly understood and even shows intractability results . Recently, studied a class of nonconvex-nonconcave 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. Later, found the appropriate notion (see Assumption 1), which is weaker than the existence of a Minty solution (an assumption extensively used in the literature ) and also generalizes the concept of negative comonotonicity . Due to these unifying and generalizing properties the notion of weak Minty solutions was promptly studied in .

Additionally, proved that a generalization of EG is able to solve problems which exhibit such solutions with a complexity of $\mathcal{O}(\varepsilon^{-1})$ for the squared operator norm. This modification which they title EG$+$, is based on an 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 .

In a similar spirit we investigate a variant of the optimistic gradient descent ascent (OGDA) /Forward-Reflected-Backward (FoRB) method. We pose the question, and give an affirmative answer to:

Can OGDA match the convergence guarantees of EG in the presence of weak Minty solutions?

In particular, we show that the following modification of the OGDA method, given for step size $a>0$ and parameter $0<\gamma\leq 1$ by

by only requiring one gradient oracle call per iteration. In Figure 1 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 $\gamma=1$, see , with the exception of two recent works which have investigated a more general coefficient see . While the previous references target the monotone setting the true importance of $\gamma$ only 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.

When considering a general (smooth) min-max problem

the operator $F$ mentioned in Assumption 1 arises naturally as $F(u):={[\nabla_{x}f(x,y),-\nabla_{y}f(x,y)]}$ with $u=(x,y)$. However, by studying saddle point problems from this more general perspective of variational inequalities (VIs), see (SVI), via the operator $F$ we can simultaneously capture more settings such as certain equilibrium problems, see .

The parameter $\rho$ in the definition of weak Minty solutions (1) plays a crucial role in the analysis and the experiments. In particular it is necessary that the step size is larger than a term proportional to $\rho$, see for example Theorem 3.1 or . At the same time, as typical, the step size is constrained from above by the reciprocal of the Lipschitz constant of $F$. For example, since the authors of require the step size to be less than $\frac{1}{L}$, their convergence statement only holds if $\rho<\frac{1}{4L}$ for the choice $\gamma=\frac{1}{2}$. This was later improved in to $\frac{1}{L}$ for $\gamma$ 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 $\rho<\frac{1}{L}$ for appropriate $\gamma$ and $a$.

Building on the recently introduced notion of weak solutions to the Minty variational inequality, see , we prove a novel convergence rate of $\mathcal{O}(1/k)$ in terms of the squared operator norm for a modification of OGDA, which we name OGDA$+$, matching the one of EG.

Even under the stronger assumption that the operator is moreover monotone we improve the possible range of step sizes for OGDA$+$ and recover the best known result for the standard method ($\gamma=1$) .

We prove a complexity bound of $\mathcal{O}(\varepsilon^{-2})$ for a stochastic version of the OGDA$+$ method.

Additionally, we propose an adaptive step size version of EG$+$, which is able to obtain the same convergence guarantees without any knowledge of the Lipschitz constant of the operator $F$, and therefore possibly even take larger steps in regions of low curvature and allow for convergence where a fixed step size policy does not.

1 Related literature

Since there is an extensive literature on convergence rates in terms of a gap function or distance to a solution for monotone problems as well as generalizations such as nonconvex-concave , convex-nonconcave or under the Polyak-Łojasiewicz assumption, see , we will only focus on the nonconvex-nonconcave setting.

noticed that a particular parametrization of the von Neumann ratio game exhibits a new type 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 showed that the condition on the weak Minty parameter can be relaxed by reducing the length of the update step even further and they do so in an adaptive way. In order to not require any other hyperparameters they also propose a 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 Algorithm 3). In 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 $\mathcal{O}(1/k)$ rate as EG.

Many works have shown different approaches for when the problem at hand exhibits a Minty solution, see (MVI). The authors of showed that weakly monotone VIs can be solved by successively adding a quadratic proximity term and repeatedly optimizing the resulting strongly monotone VI with any convergent method. In the convergence of the OGDA method was proven, but without any rate. In it was noted that the convergence proof for the golden ratio algorithm (GRAAL) works without any modification. See also for a non-euclidean version of EG and for adaptive methods. While the assumption that a Minty solution exists is a generalization of the monotone setting it is difficult to find nonmonotone problems that do possess such solutions. In our setting, see Assumption 1, the Minty inequality (MVI) is allowed to be violated at every point by a factor proportional to the squared operator norm.

While previously studied under the name of cohypomonotonicity the notion of negative comonotonicity was recently explored in . 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 studied an anchored version of EG and showed an improved convergence rate of $\mathcal{O}(1/k^{2})$ (in terms of the squared operator norm). Similarly, studied an accelerated version of the reflected gradient method . It is an open question whether such an acceleration is possible in the more general setting of weak Minty solutions (any Stampacchia solution to the VI given by negatively comonotone operator is a weak Minty solution). Another interesting observation was made in where for cohypomonotone problems monotonically decreasing gradient norm was shown when using EG. However, we did not observe this in our experiments, highlighting the need to distinguish this class from problems with weak Minty solutions.

The authors of investigate the notion of $\alpha$-interaction dominance for nonconvex-nonconcave min-max problems and showed that the proximal-point method converges sublinearly if this condition holds in $y$ and linearly if it holds in both components. Furthermore showed that if a problem is interaction dominant in both components, then it is also negatively comonotone.

The beneficial effects of introducing the simple modification commonly known as optimism have recently sparked the interest of the machine learning community . Its name originates from online optimization . The idea dates back even further and has been studied in the mathematical programming community as well .

Preliminaries

If $F$ is continuous, a Minty solution of the VI is always a Stampacchia solution. The reverse is in general not true but holds for example if the operator $F$ is monotone. In particular, there exist nonmonotone problems with Stampacchia solutions but without any Minty solutions.

2 Notions of monotonicity

The aim of this section is to recall some elementary and some more recent notions of monotonicity and the connection between those. We call an operator $F$ monotone if

Such operators arise naturally as 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

They appear as gradients of strongly convex functions or strongly-convex-strongly-concave min-max problems. A second subclass of monotone operators are so-called cocoercive operators fulfilling

They appear, for example, as gradients of smooth convex functions, in which case 2 holds with $\beta$ equal to the reciprocal of the gradients Lipschitz constant.

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 , 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 $\nu$-weak monotonicity

Such operators arise as the gradients of the well-studied class (see [dima_damek_stoch_weakly_k-4]) of weakly convex functions — a rather generic class of functions as it includes all functions without upward cusps. In particular every smooth function with Lipschitz gradient turns out to fulfill this property. On the other hand, extending the notion of cocoercivity to allow for negative coefficients, referred to as cohypomonotonicity, has received much less attention and is given by

Clearly, if there exists a Stampacchia solution for such an operator, then it also fulfills Assumption 1.

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 (Stampacchia) solution. This means instead of monotonicity it is enough to obtain standard convergence results, see , to ask for the operator $F$ to be star-monotone , i.e.

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^{*}$, in the following we only require it to hold for a single solution.

OGDA for problems with weak Minty solutions

The generalized version of OGDA, whose name we equip in the spirit of , with a “$+$” to highlight the presence of the additional parameter $\gamma$, is given by:

In particular as long as $\rho<\frac{1}{L}$ we can find a $\gamma$ 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 $\rho<a$. In order to be able to choose the step size $a$ large we have to decrease $\gamma$ as evident from 3. This, however degrades the speed of the algorithm as it makes the update steps smaller — the same effect can be observed for EG$+$ and is therefore not surprising. One could derive an optimal $\gamma$ (i.e. minimizing the right hand side) from Theorem 3.1, which however results in a uninsightful cubic dependence on $\rho$. In practice, the strategy of decreasing $\gamma$ until we get convergence, but not further gives reasonable results.

Furthermore, we want to point out that the condition $\rho<\frac{1}{L}$, is precisely the best possible bound for EG$+$ in .

+. 3.1 Improved bounds under monotonicity While the above theorem also holds if the operator $F$ is monotone, we can modify the proof slightly to obtain a better dependence on the parameters:

In particular, we can choose $\gamma=1$ and $a<\frac{1}{3L}$.

There are different works discussing the convergence of OGDA in terms of the iterates or a gap function with $a<\frac{1}{2L}$, see for example . We, however, want to compare the above bound to more similar results on rates for the best iterate in terms of the operator norm. The same rate as ours for OGDA is shown in but requires the conservative step size bound $a\leq\frac{1}{16L}$. This was later improved to $a\leq\frac{1}{3L}$ in where the bound even holds for the last iterate. However, all of these only deal with the case $\gamma=1$. The only other reference that deals with a generalized (i.e. not necessarily $\gamma=1$) version of OGDA is . There the resulting step size condition is $a\leq\frac{2-\gamma}{4L}$, which is strictly worse than ours for any $\gamma$. To summarize, not only do we show for the first time that the step size of a generalization of OGDA can go above $\frac{1}{2L}$ we also provide the least restrictive bound for any value of $\gamma$.

2 OGDA++ stochastic

In practice large batch sizes of order $\mathcal{O}(\varepsilon^{-1})$ are typically 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 guarantee convergence. See in this context the heuristic variant proposed in which decreases the parameter corresponding to $\gamma$ in our setting. Unfortunately the current analysis does not allow for variable $\gamma$.

EG++ with adaptive step sizes

+ 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$, as 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 and the fact that a crucial ingredient in the analysis is that the step size is chosen larger than a multiple of the weak Minty parameter $\rho$ 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 is carried out. Since the analysis of OGDA$+$ is already quite involved in the constant step size regime we choose to equip EG$+$ with an adaptive step 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 .

We use a 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 VIs, see , and similarly in the context of the mirror-prox method which corresponds to EG in the setting of (non-euclidean) Bregman distances, see .

A version of EG with a different adaptive step size choice has been investigated by with the unique feature that it is 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.

One of the drawbacks of adaptive methods resides in the fact that the step sizes are 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 algorithm . It comes with the additional benefit of not requiring a global bound on the Lipschitz constant of $F$ at all. While it is known that this method converges under the stronger assumption of existence of Minty solutions, a quantitative convergence result is still open.

Clearly, $a_{k}$ is monotonically decreasing by construction. Moreover, it is bounded away from zero by the simple observation that $a_{k}\geq\min\{a_{0},\tau/L\}>0$. The sequence therefore converges to a positive number which we denote by $a_{\infty}:=\lim_{k}a_{k}$.

Algorithm 3 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 us to take steps much larger than what would be suggested by a global Lipschitz constant if the iterates 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 $\rho<\frac{1}{4L}$ in the case of EG$+$ to $\rho<a_{\infty}/2$ where $a_{\infty}=\lim_{k}a_{k}\geq\tau/L$.

On the other hand, we face the problem that the bounds in Theorem 4.1 only hold after an unknown number of initial iterations when $a_{k}/a_{k+1}\leq\frac{1}{\tau}$ is finally satisfied. In theory this might take long if the curvature around the solution is much higher than in the starting area as this will force the need to decrease the step size very late into the solution process resulting in the quotient $a_{k}/a_{k+1}$ being too large. This drawback could be mitigated by choosing $\tau$ 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 be circumvented and authors instead focused on convergence of the iterates without any rate.

Numerical experiments

In the following we compare EG$+$ method from with the two methods we propose OGDA$+$ and EG$+$ with adaptive step size, see Algorithm 1 and Algorithm 3 respectively. Last but not least we also include the CurvatureEG$+$ method from which is a modification of EG$+$ and adaptively chooses the ratio of extrapolation and update step. In addition a backtracking linesearch is performed with an initial guess made by second order information, whose extra cost we ignore in the experiments.

We consider von Neumann’s ratio game recently explored in . It is given by

In Figure 3(b) we see an illustration of a particularly difficult instance of (5) discussed in , highlighting the fact that the Stampacchia solution is not a Minty solution, even when restricted to arbitrarily close ball around it (yellow area touching the solution). Interestingly we still observe good convergence behavior, although an estimated $\rho$ is more than ten times larger than the estimated Lipschitz constant.

2 Forsaken

A particularly difficult min-max toy example with “Forsaken” solution was proposed in Example 5.2 of , and is given by

where $\varphi(z)=\frac{1}{4}z^{2}-\frac{1}{2}z^{4}+\frac{1}{6}z^{6}$. This problem exhibits a Stampacchia solution at $(x^{*},y^{*})\approx(0.08,0.4)$, but also two limit cycles not containing any critical point of the objective function. In addition, also observed that the limit cycle closer to the solution repels possible trajectories of iterates, thus “shielding” the solution. Later, noticed that, restricted to the box $\|(x,y)\|_{\infty}<\frac{3}{2}$ the above mentioned solution is weak Minty with $\rho\geq 2\cdot 0.477761$, which is much larger than $\frac{1}{L}\approx 0.08$. In line with these observations we can see in Figure 4 that none of the fixed step size methods with step size bounded by $\frac{1}{L}$ converge. In light of this observation proposed a backtracking linesearch which potentially allows for larger steps than predicted by the global Lipschitz constant. Similarly, our proposed adaptive step size version of EG$+$, see Algorithm 3, is also able to break through the repelling limit cycle and converge the solution. On top of this, it does so at a faster rate and without the need of additional computations in the backtracking procedure.

3 Lower bound example

The following min-max problem was introduced in as a lower bound on the dependence between $\rho$ and $L$ for EG$+$:

In particular Theorem 3.4 from states that EG$+$ (with any $\gamma$) and constant step size $a=\frac{1}{L}$ converges for this problem if and only if $(0,0)$ is a weak Minty solution with $\rho<\frac{1-\gamma}{L}$, where $\rho$ and $L$ can be computed explicitly in the above example and are given by

Figure 1 is obtained by choosing $\xi=\sqrt{3}$ and $\zeta=-1$ we get exactly $\rho=\frac{1}{L}$ and the theory therefore predicting divergence of EG$+$ for any $\gamma$, which is exactly what is empirically observed. Although, the general upper bound proved in Theorem 3.1 only states convergence in the case $\rho<\frac{1}{L}$, we observe rapid convergence of OGDA$+$ for this example showcasing that it can drastically outperform EG$+$ in some scenarios.

Conclusion

Many interesting questions remain in the realm of min-max problems — especially when leaving the convex-concave setting. Very recently showed that the $\mathcal{O}(1/k)$ bounds on the squared operator norm for EG and OGDA for the last iterate (and not just the best one) hold even in the negative comonotone setting. Deriving a similar statement in the presence of merely weak Minty solutions is an open question.

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 1, which is not covered by theory and OGDA$+$ is the only method 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 is typically constrained by the reciprocal of the 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 $\frac{1}{L}$, which one can typically only hope for in adaptive methods. Our EG$+$ method with adaptive step size achieves this even without the additional cost of a backtracking linesearch as used for the CurvatureEG$+$ method of .

References

Appendix A Omitted proofs

+ For convenience we will sometimes use the notation $g_{k}$ for $F(u_{k})$ for all $k\geq-1$.

Let $(u_{k})$ be the sequence of iterates generated by Algorithm 1, then

From the update of the method we deduce for all $k\geq 0$

where we used the weak Minty assumption to deduce the last inequality. It remains to derive the following equality

This can be seen by expressing every difference of iterates in terms of gradients according to Algorithm 1, giving

Adding the previous two equalities to $-a^{2}(1+2\gamma^{-1})\|g_{k}-g_{k-1}\|^{2}$ proves (10). Combining 9 and 10 proves the desired statement. ∎

We are actually going to show a slightly more general version of Theorem 3.1, which introduces an additional parameter $\lambda$. Note that for $\lambda=\gamma^{-1}$ we recover the statement of Theorem 3.1. This allows us to cover the analysis of the monotone case in one proof. In particular $\lambda$ close to zero will yield the statement of Theorem 3.2.

In particular as long as $\rho<\frac{1}{L}$ we can find a small enough $\gamma$ such that the above bound holds.

Using the definition $u_{k+1}$ we can express

By applying norms on both sides we obtain via expansion of squares

We now use the Lipschitz continuityStrictly speaking we would have to assume that the term before $\|g_{k}-g_{k-1}\|^{2}$ is positive, but if it is not we can just discard it and be done with the proof. of $F$ to deduce that

The fact that the terms can be telescoped is, with $\alpha=La$ equivalent to

By solving for $\alpha$ we get the condition

where from the condition $2\gamma^{-1}-1-\lambda-(2\alpha\gamma^{-1}-\alpha\lambda)\geq 0$ we deduce $\alpha\leq\frac{2-\lambda\gamma-\gamma}{2-\lambda\gamma}$, which is redundant in light of 16. The statement follows since we chose $u_{0}=u_{-1}$. ∎

A.2 Improved bounds under monotonicity

For the readers convenience we restate the theorem from the main text.

In particular, we can choose $\gamma=1$ and $a<\frac{1}{3L}$.

From Theorem A.1 and the fact that $aL=\frac{\gamma-2}{\gamma+2}-\varepsilon$ we need to find an appropriate $\lambda>0$ such that $aL\leq\frac{2-\lambda\gamma-\gamma}{2-\lambda\gamma+\gamma}$. Given $\varepsilon>0$ we therefore aim to find a $\lambda>0$ such that

By bringing both terms on one side and the same denominator we obtain the condition

Using the fact that $\lambda\leq 2\gamma^{-1}$ and $\gamma\geq 0$ we can upper bound the left hand side by $\lambda$. Choosing $\lambda=\varepsilon$ therefore ensures that the necessary condition on the step size (16) is satisfied and at the same time yields the dependence on $\varepsilon$ in the denominator of the right hand side in the statement of the theorem.

A.3 OGDA++ stochastic

Let $(u_{k})$ be the sequence of iterates generated by stochastic OGDA$+$, then, for any $\lambda>0$

From the update of the method we deduce for all $k\geq 0$

to deduce the last inequality. It remains to note that

which follows immediately the way we deduced 10. Now using the definition of $u_{k+1}$ we get

Next, we need to estimate the difference of the gradient estimators via the difference of the true

where we used the Lipschitz continuity of the operator. Therefore, by taking the expectation, we obtain

calls to the stochastic oracle, with large batch sizes of order $\mathcal{O}(\varepsilon^{-1})$.

is already nonnegative. Next we remark that the statement

We still need to estimate $\lambda^{-1}$ to find the right batch size in order to decrease the last summand to the desired accuracy. By considering 24 we get

By taking $B:=\max\{1,\frac{4\sigma^{2}}{\alpha\varepsilon}\}$ independent samples per iteration, we get the variance

and thus arrive at a total oracle call complexity as claimed. ∎

A.4 EG++ with adaptive step size

We start by using Assumption 1 splitting the following term into three

By expressing $F(u_{k})$ via the definition of $\bar{u}_{k+1}$ and the three point identity we obtain

Similarly, by expressing $F(\bar{u}_{k})$ via the definition of $u_{k}$ we deduce

Lastly, via the Cauchy-Schwarz inequality

Combining 26, 27, 28 and 29 and multiplying by $2$ we get

Using the observation that $\gamma a_{k}F(u_{k})=\bar{u}_{k+1}-\bar{u}_{k}$, gives

We see that the largest possible range for $\rho$ is achieved for $\gamma=\frac{1}{2}$. ∎

The desired statement follows by observing that $a_{i}\geq a_{\infty}\geq\tau/L$. ∎

Note that the above proof for the adaptive version of EG$+$ provides an improvement in the dependence between $\rho$ and $L$ over the analysis of even in the constant step size regime.

Appendix B Additional statements and proofs

For the sake of completeness we provide a proof of the elementary fact that Minty solutions are a stronger requirement than Stampachia solutions.

If $F$ is continuous then every Minty solution is also a Stampacchia solution.

By dividing by $(1-\alpha)$ and then taking the limit $\alpha\to 1$ we obtain that $w^{*}$ is a solution of the Stampacchia formulation. ∎

Appendix C Numerics

For all experiments, if not specified otherwise, we used for OGDA$+$ and the adaptive version of EG$+$ the parameter $\gamma=\frac{1}{2}$. For the step size choice of Algorithm 3 we use $\tau=0.99$. For the CurvatureEG$+$ method of (with their notation) we use $\delta_{k}$ equal to $-\rho/2$, where $\rho$ is 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 $\tau=0.9$ and $\nu=0.99$.

The data used to generate the instance displayed in Figure 3 was suggested in and is given by

This results in the following objective function for the min-max problem

which gives rise to the optimality conditions

with the solution $(x^{*},y^{*})=(0.951941,0.050485)$. For the experiments we used an estimated Lipschitz constant $L=\frac{5}{3}$.

In Figure 5 we can see the reason for the slow convergence behavior of the CurvatureEG$+$ method observed in Figure 3. Not only is the step size computed by the backtracking procedure smaller than the one chosen by adaptive EG$+$, see (4), also the second step (update step) uses an even smaller fraction of the already smaller extrapolation step size.

+ chooses its own ratio adaptively and does so for this example in a seemingly overly conservative way, resulting in slow convergence observed in Figure 3. C.1.1 Polar Game For Figure 2 we used the so-called Polar Game introduced in which is given by

where $\psi(x,y)=\frac{1}{16}ax(-1+x^{2}+y^{2})(-9+16x^{2}+16y^{2})$ and parameter $a>0$. In Figure 2 we used $a=\frac{1}{3}$.