Beyond the Golden Ratio for Variational Inequality Algorithms

Introduction

With the increasing focus on min-max problems in applications, variational inequality (VI) algorithms have gained significant attention in machine learning. These algorithms focus on the following VI problem

Many algorithms, dating back to 1970s, exist for solving (1), such as the extragradient method (Korpelevich, 1976), Popov’s algorithm (Popov, 1980), forward-backward-forward (Tseng, 2000), reflected gradient (Malitsky, 2015; Malitsky and Tam, 2020), optimistic gradient descent-ascent (OGDA) (Daskalakis et al., 2018), dual extrapolation (Nesterov, 2007). The algorithm we focus in this paper is the golden ratio algorithm (GRAAL) due to (Malitsky, 2020), which iterates for $k\geq 0$ as

with parameter $\phi>1$ to be defined and a step size sequence $\alpha_{k}$. The nonadaptive version of this algorithm uses $\alpha_{k}=\frac{\phi}{2L}$ where $L$ is the global Lipschitz constant of $F$ (Malitsky, 2020, Theorem 1).

However, what really separates (aGRAAL) from all the other VI algorithms listed above is the ability to provably use nonmonotone step sizes adapting to local Lipschitzness of $F$, with the adaptive rule

with $\gamma\leq\frac{1}{\phi}+\frac{1}{\phi^{2}}\in[1,2)$ and $\phi\in(1,\frac{1+\sqrt{5}}{2}]$. Higher $\phi$ not only gives a larger maximum step size as per (3), but also makes $\bar{\mathbf{z}}^{k}$ closer to the most recent iterate $\mathbf{z}^{k}$ instead of $\bar{\mathbf{z}}^{k-1}$. The first argument in (3) allows increasing step sizes between iterations and the second estimates a local Lipschitz constant of $F$. The last argument $\bar{\alpha}$ is required for theoretical reasons in (Malitsky, 2020) and generally picked as a large value in practice so that it will not be effective (see also Section 4).

Compared to the constant step sizes such as $\frac{1}{L}$, the adaptive step sizes make GRAAL highly competitive in practice, in addition to relaxing the assumption of global Lipschitzness of $F$. Along with its unique empirical performance and generality, GRAAL keeps the good theoretical properties of nonadaptive algorithms: convergence of the sequence to a solution and $O(1/k)$ rate with monotonicity. A representative plot for the benefit of using step sizes as (3) is in Fig. 1.

This paper starts the formal study on understanding the peculiarity of GRAAL among the large sea of VI algorithms. Towards this goal, we contribute the following results for situating this algorithm in the literature and enhancing its theoretical understanding and practical merit:

In the unconstrained setting with a constant step size, GRAAL is equivalent to Popov’s algorithm, OGDA and reflected gradient, when $\phi=2$. This shows the convergence of GRAAL with $\phi=2$ for free.

With constraints and a constant step size, the established connection is not sufficient and we introduce a novel analysis to prove the convergence of GRAAL with $\phi=2$.

We improve the complexity of adaptive GRAAL from a quadratic dependence on the Lipschitz constant to a linear one, by eliminating the hyperparameter $\bar{\alpha}$.

We show that adaptive GRAAL has convergence guarantees for nonmonotone problems with weak Minty solutions and show that it reliably converges for some hard instances, even when no other method does so.

2 Notation and preliminaries.

We say that an operator $F$ is monotone if $\langle F(\mathbf{x})-F(\mathbf{y}),\mathbf{x}-\mathbf{y}\rangle\geq 0$ for any $\mathbf{x},\mathbf{y}$ and Lipschitz if $\|F(\mathbf{x})-F(\mathbf{y})\|\leq L\|\mathbf{x}-\mathbf{y}\|$. We denote the projection as $P_{C}(\mathbf{z})=\arg\min_{\mathbf{u}\in C}\|\mathbf{u}-\mathbf{z}\|^{2}$. We denote the golden ratio as $\varphi=\frac{1+\sqrt{5}}{2}$. The (restricted) dual gap function (see (Facchinei and Pang, 2003; Nesterov, 2007)) is a standard notion of suboptimality for VIs and is defined as

where $S$ is a compact set. It is shown in (Nesterov, 2007, Lemma 1) that this is a valid suboptimality measure, since we will prove that the iterates of the algorithm remain in a compact set.

Connection of GRAAL and other VI algorithms

In this section, we assume that the operator $F$ is monotone and $L$-Lipschitz. It is well-known that for such operators, resulting for example from min-max problems via (2), a naive forward evaluation

will not converge even for simple bilinear problems with any fixed step size — a property which makes even monotone VIs arguably more difficult to solve than the computation of stationary points in nonconvex minimization.

Having a nonconvergent scheme (FB), it is tempting to find a simple modification that will ensure convergence. There are two principal approaches to do so: one can try to change either the argument $\mathbf{z}^{k}$ or the forward evaluation $F(\mathbf{z}^{k})$ in (FB). Most algorithms opt for the latter option, whereas GRAAL opts for the former as we will see soon.

A strikingly simple, yet extremely powerful change is to replace $F(\mathbf{z}^{k})$ by $F(\mathbf{z}^{k+1})$, which leads to

which is known as the proximal point algorithm (Rockafellar, 1970). While this algorithm has great theoretical properties — for instance, it converges for any $\alpha>0$ — it is an implicit method. Computing $z^{k+1}$ is not a simple matter and usually each iteration of (PP) requires a call to another subsolver.

One of the earliest, and arguably most popular schemes, is the extragradient method (EG) which dates back to (Korpelevich, 1976). It relies on the change of the forward evaluation from $F(\mathbf{z}^{k})$ to $F(P_{C}(\mathbf{z}^{k}-\alpha F(\mathbf{z}^{k})))$. Alternatively we can write the method as

Interestingly, (Mokhtari et al., 2020; Nemirovski, 2004) showed that EG can be viewed as an approximation of (PP). Naturally, however, due to the explicit structure, the method requires an upper bound on the (constant) step size: $\alpha<\frac{1}{L}$. The point $\bar{\mathbf{z}}^{k}$ is commonly referred to as the extrapolated point.

By using an old evaluation of the operator to compute the extrapolated point instead of a new one, we could expect the quality of the iterates not to suffer much, leading to

This strategy, proposed by (Popov, 1980), has similar guarantees as (EG) by requiring a single evaluation of the operator $F$. This comes at the cost of the need to reduce the step size, leading to the requirement $\alpha<\frac{1}{2L}$ (Hsieh et al., 2019).

About two decades after Popov (1980), Tseng (2000) proposed to modify EG to only require a single projection:

leading to the forward-backward-forward method, with the same requirement for $\alpha$ as EG: $\alpha<\frac{1}{L}$.

As observed in (Böhm et al., 2022), applying Popov’s idea to (FBF) and replacing $F(\mathbf{z}^{k})$ by $F(\bar{\mathbf{z}}^{k-1})$, the obtained method can be conveniently written in one line

where the bound $\alpha<\frac{1}{2L}$ is imposed. This method was in greater generality (nonconstant step sizes) studied in (Malitsky and Tam, 2020) under the name forward-reflected-backward (FoRB), but is more widely known in the unconstrained setting as the optimistic-gradient-descent-ascent (OGDA) (Daskalakis et al., 2018). Again, (FoRB) can be seen as (FB) where $F(\mathbf{z}^{k})$ is changed to $2F(\mathbf{z}^{k})-F(\mathbf{z}^{k-1})$.

Another method proposed in (Malitsky, 2015) is projected reflected gradient method (PRG), which solves VI by requiring only one evaluation of $F$ and iterates as

It is easy to see that the (PRG) method is equivalent to (FoRB) if the operator $F$ is linear. The analysis of (PRG) in (Malitsky, 2015) requires $\alpha<\frac{\sqrt{2}-1}{L}$, which according to the above consideration is not tight when $F$ is linear. Regarding the (FB) interpretation, we only need to change $F(\mathbf{z}^{k})$ to $F(2\mathbf{z}^{k}-\mathbf{z}^{k-1})$.

A slightly lesser known method, relying on a very similar correction step as the one used in (FoRB), but applied after the projection, was proposed in (Csetnek et al., 2019) and is given by

In the unconstrained case this method is equivalent to (FoRB). The analysis in (Csetnek et al., 2019), however, requires the more restrictive $\alpha<\frac{1}{3L}$ and even provides a counterexample to show that this dependence is tight. It is not clear where this more conservative dependence on the Lipschitz constant comes from.

Last but not least, our main method of interest is the golden ratio algorithm (GRAAL), introduced in (Malitsky, 2020), given by

Initially, the (nonadaptive) analysis in (Malitsky, 2020) requires choosing $\phi\leq\varphi=\frac{1+\sqrt{5}}{2}$ (hence the name with golden ratio), together with a bound on the step size $\alpha\leq\frac{\phi}{2L}$. In the following we will show that this bound can be relaxed, in which case we can recover some of the other methods mentioned in this section. Evidently, (GRAAL) can be seen as a modification of (FB) with the change $\mathbf{z}^{k}$ to $\bar{\mathbf{z}}^{k}$.

From the first line of (GRAAL) we can rewrite

Hence instead of viewing $\bar{\mathbf{z}}^{k}$ as a sequence of averaged iterates we can interpret $\mathbf{z}^{k}$ as a sequence of extrapolated iterates. Plugging (5) into the second line of (GRAAL) yields the identity claimed in the title, which gives for $\phi=2$ a $\frac{1}{2}$-averaged version of (PRG):

If the problem is unconstrained, GRAAL’s $\bar{\mathbf{z}}^{k}$ sequence corresponds to the one generated by (PRG), but with scaled step size.

2 GRAAL is FoRB/OGDA/Popov in the unconstrained case

While (GRAAL) seems fundamentally different from methods such as (FoRB)/OGDA/(Popov) or (shadow-DR), which rely on previous evaluations of the operator $F$, they do turn out to be equivalent in the unconstrained setting, where $\bar{\mathbf{z}}^{k-1}=\mathbf{z}^{k}+\alpha F(\mathbf{z}^{k-1})$, via the simple identity:

To be precise, the equivalence to OGDA and others holds with $\phi=2$ and for general $\phi$, (GRAAL) is equivalent to the generalized version of OGDA, see (Ryu et al., 2019; Böhm, 2022), where $2$ is replaced by $\phi$ and an appropriate scaling of the step size.

3 Summary

In the unconstrained setting, all the methods above collapse to two classes. On one hand, there is (EG)/(FBF), relying on two gradient evaluations per iteration and a step size constrained by $\frac{1}{L}$. On the other, there is the zoo of Popovesque methods: (GRAAL), (shadow-DR), (PRG), (FoRB), (Popov), and OGDA requiring only one call to $F$ but paying the price of a smaller step size.

The established equivalences give us a proof of convergence for GRAAL with $\phi=2$ in the unconstrained case since it reduces to known methods. However, these relationships are not useful to show the convergence of GRAAL with $\phi=2$ in the constrained case which is much more common with min-max problems. It turns out that standard techniques are not sufficient for such a result, which motivates the next section, dedicated to proving this conclusion.

GRAAL with ϕ=2italic-ϕ2\phi=2 for constrained problems

We sketch the existing analysis of GRAAL in (Malitsky, 2020) and point out to the reason for the restrictive upper bound on $\phi$. Then, we see high level ideas on how to tighten this analysis en route to $\phi=2$. For convenience, let us define

The former is important for showing the rate on the gap function since taking the maximum gives (4) for which we will show the $O(1/k)$ rate. The latter will serve as a Lyapunov (or energy) function.

The analysis of (Malitsky, 2020), given in Lemma 13 in the Appendix for convenience, results in the following key inequality for $k\geq 1$:

Golden ratio appears to make $\phi-1-\frac{1}{\phi}=0$. The analysis in (Malitsky, 2020) discards the good term $-\phi\|\mathbf{z}^{k}-\bar{\mathbf{z}}^{k}\|^{2}$ in the right-hand side to use a telescoping argument, common to methods described in Section 2.

We see that this good term is one index away from the main error term $\|\mathbf{z}^{k+1}-\bar{\mathbf{z}}^{k}\|^{2}$. However, it is not one index forward, but instead backward, hence it is not immediate how to use it to relax the requirement of $\phi$. This intuition can be formalized by summing the inequality and using the definition of $\mathcal{E}(\mathbf{z}^{k+1},\mathbf{z})$ which results in

If this unwieldy expression is bounded, the convergence rate of the gap follows immediately. It is easy to see that if $\phi=2$, then (9) reduces to

which is not necessarily bounded due to the second term. In fact, a naive approach can be used for values slightly larger than the golden ratio. We know by Young’s inequality that for any $\tau>0$

It is tedious but straightforward to properly adjust $\phi$ and $\tau$ so that the error term involving $\|\mathbf{z}^{k+1}-\bar{\mathbf{z}}^{k}\|^{2}$ is cancelled by using the negative terms in (10). However, this approach is definitely not tight due to spurious use of Young’s inequality and only gives $\phi$ values up to $1.77$, whereas we expect $\phi=2$ to be tight, due to the connection with existing methods such as OGDA.

Another obvious remedy would be to simply assume that the term $\|\mathbf{z}^{k+1}-\bar{\mathbf{z}}^{k}\|^{2}$ is bounded, for example, by assuming the sequence $(\mathbf{z}^{k})$ is bounded. However, this is not realistic since boundedness of $C$ is a strong assumption, not holding for many min-max problems in practice. A prevalent example is constrained optimization where neither the primal nor the dual domain is bounded.

In the next section, we prove that the sequence $(\mathbf{z}^{k})$ is bounded with $\phi=2$, which will help us get convergence and rate results. Instead of the naive approach described above which tries to cancel the error in (10) by other terms and loose inequalities such as Young’s, we will analyze the boundedness of the sequence by a novel induction argument on the tight inequality in (9).

2 GRAAL beyond the golden ratio

A standard way to prove boundedness of iterates is to identify a Lyapunov function (nonnegative and nonincreasing) including terms such as $\|\mathbf{z}^{k}-\mathbf{z}\|^{2}$. An example is $\mathcal{E}$ in (7). While this can be done with $\phi\leq\varphi$, it is unclear if it is possible with $\phi=2$, due to the issue described in Section 3.1. To go around this difficulty, we have to use nonstandard tools and forgo the Lyapunov function argument and analyze boundedness of $(\mathbf{z}^{k})$ directly via induction on the key inequality (8).

Let Assumption 1 hold and let $\phi=2$, $\alpha\leq\frac{1}{L}$ in GRAAL. Then, we have that $(\mathbf{z}^{k})$ and $(\bar{\mathbf{z}}^{k})$ are bounded sequences. In particular, we have

While we provide a formal proof for the case $\phi=2$ here for simplicity, we also supply a computer aided proof via semi-definite programming, see Appendix A, which in addition covers the case for $\phi<2$ and provides a better constant for $\phi=2$.

Proof In (8), we set $\mathbf{z}=\mathbf{z}^{*}$ and use $G(\mathbf{z}^{k},\mathbf{z}^{*})\geq 0$ by (1). Next, we sum (8) with $\phi=2$ which gives us

where we used $\mathbf{z}^{0}=\bar{\mathbf{z}}^{0}$. Define $R^{2}=\|\mathbf{z}^{1}-\mathbf{z}^{*}\|^{2}+\|\mathbf{z}^{0}-\mathbf{z}^{*}\|^{2}$. For the inductive step, assume that $\|\bar{\mathbf{z}}^{i}-\mathbf{z}^{*}\|\leq 2R$ for all $i\leq k$.

We will transform the error term $\frac{1}{2}\|\mathbf{z}^{k+1}-\bar{\mathbf{z}}^{k}\|^{2}$ in (11) so that the other terms in the left-hand side of (11) can be used for (partial) cancellation. By the paralellogram law and definition $\bar{\mathbf{z}}^{k}=\frac{1}{2}\mathbf{z}^{k}+\frac{1}{2}\bar{\mathbf{z}}^{k-1}$, we have

Plugging in this equality to (11) and using the definition of $\bar{\mathbf{z}}^{k}$ gives us

The left-hand side is in a suitable form to apply another paralellogram law and obtain

After combining this equality with (12), it follows that

We are now at the most critical point of the proof. For induction, we will combine the second term in the right-hand side of (13) with the terms in the left-hand side to obtain $\|\bar{\mathbf{z}}^{k-1}-\mathbf{z}^{*}\|^{2}$. Now continue with the following identity which can be verified by simple expansion

Even though it is difficult to see the significance of this identity, a high level intuition is noticing that $\mathbf{z}\mapsto\frac{1}{4}\|\mathbf{z}-\bar{\mathbf{z}}^{k-1}\|^{2}-\|\mathbf{z}-\mathbf{z}^{*}\|^{2}$ is maximized at $\mathbf{z}=\frac{4}{3}\mathbf{z}^{*}-\frac{1}{3}\bar{\mathbf{z}}^{k-1}$. We can then rewrite (13) as

Let $a=\mathbf{z}^{k}-\mathbf{z}^{*}$, $b=\bar{\mathbf{z}}^{k-1}-\mathbf{z}^{*}$. Then using this notation in (14), taking square root of both sides, using triangle inequality and the inductive assumption ($\|b\|\leq 2R$) implies that

On the other hand, (14) along with inductive assumption gives us

We can now combine the last two estimations with triangle inequality to complete the induction

Hence, by induction we proved that $(\bar{\mathbf{z}}^{k})$ is bounded. The definition $\mathbf{z}^{k}=2\bar{\mathbf{z}}^{k}-\bar{\mathbf{z}}^{k-1}$ shows that $(\mathbf{z}^{k})$ is also bounded. The final inequality uses $R^{2}\leq 3\|\mathbf{z}^{0}-\mathbf{z}^{*}\|^{2}$, which is shown in Lemma 14 in Appendix A.

Let Assumption 1 hold, $\phi=2$, $\alpha=\frac{1-\varepsilon}{L}$ for any $\varepsilon\in(0,1)$ in GRAAL and $\mathbf{Z}^{k}=\frac{1}{k}\sum_{i=1}^{k}\mathbf{z}^{i}$. Then $(\mathbf{z}^{k})$ converges to a solution of (1) and

where the second inequality is by the definition $\bar{\mathbf{z}}^{k}=\frac{1}{2}\mathbf{z}^{k}+\frac{1}{2}\bar{\mathbf{z}}^{k-1}$. Rearranging and summing this inequality gives

where we used $\mathbf{z}^{-1}=\bar{\mathbf{z}}^{-1}$ for getting the first inequality.

The result of Lemma 13 also gives the following inequality after using $\phi=2$ and $\mathbf{z}=\mathbf{z}^{*}$:

Since $\|\mathbf{z}^{k+1}-\bar{\mathbf{z}}^{k}\|^{2}$ is bounded, the sequence on the left-hand side of the inequality is lower bounded and nonincreasing, hence convergent. In summary, we have that

Since $\|\mathbf{z}^{k+1}-\mathbf{z}^{k}\|^{2}\to 0$ and $\|\mathbf{z}^{k+1}-\bar{\mathbf{z}}^{k}\|^{2}=4\|\bar{\mathbf{z}}^{k+1}-\mathbf{z}^{k+1}\|^{2}\to 0$, we further deduce that

Since we previously showed that $\bar{\mathbf{z}}^{k_{i}}-\mathbf{z}^{*}\to 0$ for an arbitrary $\mathbf{z}^{*}$, we conclude that $\bar{\mathbf{z}}^{k}-\mathbf{z}^{*}\to 0$. It is easy to see that $\mathbf{z}^{k}-\mathbf{z}^{*}\to 0$ as well since we have $\bar{\mathbf{z}}^{k}-\mathbf{z}^{k}\to 0$.

Now we turn our attention to the convergence rate. We start by collecting some estimations from Theorem 1. In particular, the main conclusion of the theorem was that

Since the guarantee on the gap is on the average of the sequence $(\mathbf{z}^{k})$, we need to set $S$ such that it will contain $(\mathbf{z}^{k})$ to use the result of (Nesterov, 2007, Lemma 1). Let

We set $\phi=2$ on Lemma 13, sum this inequality, divide by $k$ and take maximum over $S$ to obtain

where the $\frac{1}{2\alpha}$ factor on the right-hand side is since $G(\mathbf{z}^{k},\mathbf{z})=2\alpha\langle F(\mathbf{z}),\mathbf{z}^{k}-\mathbf{z}\rangle$ (see (7)).

By using $\bar{\mathbf{z}}^{1}=\frac{1}{2}\mathbf{z}^{1}+\frac{1}{2}\mathbf{z}^{0}$ due to $\bar{\mathbf{z}}^{0}=\mathbf{z}^{0}$, we get

We apply (19) and (20) in (18) and pick $c$ to minimize the corresponding term, to obtain the result.

Increasing $\phi$ from the golden ratio to $2$ for the fixed step size regime not only emphasizes an interesting connection to OGDA, but also consistently improves empirical performance for monotone problems, see Fig. 2. Even though the adaptive version of GRAAL is typically superior in practice as per the experiments of Malitsky (2020), we want to point out that with constant step sizes, the need to pick $\phi\leq\varphi<2$ caused GRAAL to perform worse than methods such as OGDA. The main merit of our result is showing that this is not the case.

Adaptive GRAAL: Removing hyperparameters and improving complexity

We first recall aGRAAL, proposed in (Malitsky, 2020):

where $\alpha_{k}$ is picked as in (3) and $\phi\in\left(1,\frac{1+\sqrt{5}}{2}\right)$. As mentioned in (Malitsky, 2020), the hyperparameter $\bar{\alpha}$ in (3) is only for theoretical purposes and the suggested choice in practice is taking $\bar{\alpha}$ very large so that it will be ineffective in (3). However, there are two sides to this coin from a complexity point of view as we see now. Recall that (Malitsky, 2020) proved that the iterates remain in a bounded region and established the following worst case rate for the ergodic iterates

where $L$ denotes the (unknown) Lipschitz constant of $F$ over this bounded region. On one hand, taking $\bar{\alpha}$ too large could make this rate vacuous. On the other, taking $\bar{\alpha}$ small may prevent taking large step sizes in (3). Another aspect of this bound is that the dependence on $L$ is suboptimal, since most VI methods including nonadaptive GRAAL result in the rate $O(L/k)$. Obtaining linear dependence on $L$ suggests taking $\bar{\alpha}$ as a large multiple of $\frac{1}{L}$, which not only requires the knowledge of $L$, but also could make the constant of the rate large as per the discussion above. This suboptimal worst-case complexity result may be seen as the cost of adaptivity. To avoid this conflict regarding the choice of $\bar{\alpha}$ in practice and the resulting complexity, we propose to remove $\bar{\alpha}$ in (3) and provide an analysis with the simpler step size rule

with $\gamma=\frac{1}{\phi}+\frac{1}{\phi^{2}}$ to complement the empirical success of the algorithm in the experiments of (Malitsky, 2020) with the choice (22). This rule not only removes the hyperparameter $\bar{\alpha}$ but as we show in the next theorem, it also results in the rate $O(L/k)$ which is only a small constant times worse than the rate of the nonadaptive method (see Remark 6 for a precise statement). As a result, this is a much smaller cost to pay for the worst-case complexity with adaptivity. With the proposed change, we obtain Alg. 1.

We will start with the one iteration analysis from (Malitsky, 2020) which does not need any modification, so we state the result with a very brief proof to make the connection easy to follow. Note that the spurious $\bar{\alpha}$ term is not used in the analysis of (Malitsky, 2020, Theorem 2) in this result.

(Consequence of (Malitsky, 2020, Theorem 2)) Let Assumption 1(i, iii, iv) hold and $F$ be locally Lipschitz. Let $\phi\in\left(1,\frac{1+\sqrt{5}}{2}\right)$, $\gamma\leq\frac{1}{\phi}+\frac{1}{\phi^{2}}$ and $\mathbf{Z}^{k}=\frac{1}{\sum_{i=1}^{k}\alpha_{i}}\sum_{i=1}^{k}\alpha_{i}\mathbf{z}^{i}$. Then, the iterates $(\mathbf{z}^{k})$ of Alg. 1 are bounded and we have

Proof In (Malitsky, 2020, Theorem 2) inequality (35) is only valid for $k\geq 2$. However due to our definition of $\mathbf{z}^{1}$ and since $\mathbf{z}^{0}=\bar{\mathbf{z}}^{0}$, it already holds for $k\geq 1$. Then, we can unroll the recursion another step until iteration $k=1$ instead of $k=2$.

Looking at the bound in (23), we notice that in order to derive a complexity result, we require a lower bound for the sum of the step sizes. In the original proof in (Malitsky, 2020) such a bound is ensured by enforcing each $\alpha_{i}$ to be lower bounded by using $\bar{\alpha}$ to derive a $O(1/k)$ rate.

For aGRAAL the consecutive step sizes also depend on the initial $\alpha_{0}$. Since the method is entirely adaptive and we do not assume any a priori knowledge about $F$, we want to make sure that $\alpha_{0}$ is not too small and not too large. To this end, for the initialization, we recommend to use the linesearch procedure described below.

For brevity, we will write $L_{k}=\frac{\|\mathbf{z}^{k}-\mathbf{z}^{k-1}\|}{\|F(\mathbf{z}^{k})-F(\mathbf{z}^{k-1})\|}$. Also, let $L$ be the Lipschitz constant of $F$ over the bounded set $\operatorname{\overline{conv}}\{\mathbf{z}^{0},\mathbf{z}^{1},\dots\}$. It trivially holds that $L\geq L_{k}$ for all $k$. Without loss of generality, we assume that $L\geq 1$.

Let us choose $\alpha_{0}$ via linesearch as follows: set $\alpha_{0}$ to the largest number in $\{\gamma^{-i}\colon i=0,1,\dots\}$ (note here the use of $\gamma$ given in Alg. 1) such that

The second equation gives the upper bound for $\alpha_{0}$: $\alpha_{0}\leq\frac{\phi}{2L_{1}}$. Note that the linesearch always terminates because $F$ is locally Lipschitz, and we can immediately obtain the following statements, which we will use later in Lemma 4. We have either $\alpha_{0}=\gamma^{-0}=1>\frac{\phi}{2L}\geq\frac{\phi}{2\gamma L}$ or that $\gamma\alpha_{0}=\gamma\cdot\gamma^{-i}$ violates the inequality above, that is

which also implies that $\alpha_{0}\geq\frac{\phi}{2\gamma L_{1}}\geq\frac{\phi}{2\gamma L}$. Moreover, from the algorithm’s update for $\alpha_{1}$ we have either $\alpha_{1}=\gamma\alpha_{0}\geq\frac{\phi}{2L}$ or

which implies that $\alpha_{1}+\alpha_{0}\geq 2\sqrt{\alpha_{1}\alpha_{0}}\geq\frac{\phi}{L_{1}}$. Using the upper bound for $\alpha_{0}$, we deduce that $\alpha_{1}\geq\frac{\phi}{2L_{1}}\geq\alpha_{0}$. To conclude, the suggested choice of $\alpha_{0}$ in (24) ensures that

The following lemma is our main technical contribution in Section 4, which will lead to Theorem 5 when combined with the previous lemma.

Let $\alpha_{0}$ satisfy (24) and $c=\min_{m\geq 2}\frac{\phi}{m}\sqrt{\frac{\gamma^{m-1}-1}{\gamma-1}}$. Then, we have

As mentioned in the beginning of this section, we can no longer rely on a lower bound for every individual step size but want to use their structure to lower bound their sum directly. Specifically, whenever option two is active for $\alpha_{i}$ (meaning that the second component in (22) attains the minimum), then we can easily show that $\alpha_{i-2}+\alpha_{i}\geq\frac{\phi}{L}$. On the other hand, if option two is not present for a long time, then we will have a geometric progression $\alpha_{i},\alpha_{i}\gamma,\alpha_{i}\gamma^{2},\dots$, whose sum is also easy to bound. These are two main ingredients, however combining the two requires an intricate technical argument.

Proof We call $\alpha_{k}=\gamma\alpha_{k-1}$ and $\alpha_{k}=\frac{\phi^{2}}{4\alpha_{k-2}L_{k}^{2}}$ as the first and second options that the step size $\alpha_{k}$ can take respectively.

If $\alpha_{k}$ satisfies the second option, for $k\geq 2$, then $\alpha_{k-2}+\alpha_{k}\geq\frac{\phi}{L_{k}}\geq\frac{\phi}{L}$. This follows directly from $a+b\geq 2\sqrt{ab}$.

$0<c\leq\frac{\phi}{2}$. The first inequality follows from $\gamma>1$ and $\lim_{m\to\infty}\frac{\phi}{m}\sqrt{\frac{\gamma^{m-1}-1}{\gamma-1}}=\infty$. The second one follows from setting $m=2$ in the definition of $c=\min_{m\geq 2}\frac{\phi}{m}\sqrt{\frac{\gamma^{m-1}-1}{\gamma-1}}$.

If there does not exist an $\alpha_{i}$ smaller than $\frac{c}{L}$, then we are done. So assume that such an $\alpha_{i}$ exists.

For $s\geq 1$, let us call by a tail a maximal subsequence of consecutive elements $\alpha_{s+1},\dots,\alpha_{s+m}$ such that it starts from $\alpha_{s+1}\geq\frac{c}{L}$ and the rest of the elements are all smaller:

Notice that for every such a tail, $\alpha_{s+2}<\alpha_{s+1}$, which means that the second option for $\alpha_{s+2}$ is active. By Claim 1, this implies that $\alpha_{s}\geq\frac{c}{L}$. We call this element $\alpha_{s}$ as a head. Thus, for every tail $\alpha_{s+1},\dots,\alpha_{s+m}$ there is a preceding element $\alpha_{s}$ that is a head. This was the case when $s\geq 1$. If we have a tail with $s=0$, we call this sequence $\alpha_{1},\dots,\alpha_{m}$ the initial tail. Note that the initial tail lacks a head (i.e. $\alpha_{0}$ is not part of (23)), which is the reason why we will have to consider this case separately.

As a result, we can partition $(\alpha_{i})_{i=1}^{k}$ into a non-overlapping sequence of (i) the initial tail (possibly empty), (ii) head-tail pairs, and (iii) elements larger than $\frac{c}{L}$. It is sufficient to show the bound for each part in our partition.

For a head-tail sequence $\alpha_{s},\alpha_{s+1},\dots,\alpha_{s+m}$, we will show that

As we have already mentioned, for $\alpha_{s+2}$ we have that $\alpha_{s+2}=\frac{\phi^{2}}{4\alpha_{s}L_{s+2}^{2}}\geq\frac{\phi^{2}}{4\alpha_{s}L^{2}}$. For elements $\alpha_{s+4},\dots,\alpha_{s+m}$ only the first option can occur, since otherwise there will be a contradiction with Claim 1. For $\alpha_{s+3}$, however, both options are possible:

If $\alpha_{s+3}=\gamma\alpha_{s+2}\geq\frac{\gamma\phi^{2}}{4\alpha_{s}L^{2}}$, then

where the last inequality follows from $\alpha_{s+1}\geq\frac{c}{L}$ and our choice of constant $c$.

If the second option is active for $\alpha_{s+3}$, that is $\alpha_{s+3}\geq\frac{\phi^{2}}{4\alpha_{s+1}L^{2}}$, we have a similar estimation to (4.1):

where the last inequality follows from $\alpha_{s}+\alpha_{s+2}\geq\frac{\phi}{L}\geq\frac{2c}{L}$ and the definition of $c$.

Hence, in both cases the desired bound holds.

For an empty initial tail there is nothing to prove. For a non-empty tail $\alpha_{1},\dots,\alpha_{m}$, we will show that

Since $\alpha_{1}\geq\frac{\phi}{2L}\geq\frac{c}{L}$, the first option cannot be active for $\alpha_{2}$. Hence, $\alpha_{2}=\frac{\phi^{2}}{4\alpha_{0}L_{2}^{2}}\geq\frac{\phi^{2}}{4\alpha_{0}L^{2}}$. First of all, note that for $m=1$ the desired inequality obviously holds: $\sum_{i=1}^{1}\alpha_{i}\geq 0$. For $m=2$, we have by Claim 2

Thus, for the rest of the proof we suppose that $m\geq 3$.

For steps $\alpha_{4},\dots,\alpha_{m}$ only the first option can be active (by Claim 1). For $\alpha_{3}$ we have two cases:

The first option for $\alpha_{3}$ is active, that is $\alpha_{3}=\gamma\alpha_{2}$. Then similarly to (4.1) we have

The second option for $\alpha_{3}$ is active, that is $\alpha_{3}=\frac{\phi^{2}}{4\alpha_{1}L_{3}^{2}}\geq\frac{\phi^{2}}{4\alpha_{1}L^{2}}$. Then similarly to (4.1) we have

the sequence $\alpha_{1},\dots,\alpha_{k}$ can be divided into an initial part $\alpha_{1},\dots\alpha_{m}$, some non-overlapping head-tails, and the remaining elements;

for every head-tail $\alpha_{s},\dots,\alpha_{s+m}$ we showed that $\sum_{i=0}^{m}\alpha_{s+i}\geq\frac{c(m+1)}{L}$;

for the initial tail we showed that $\sum_{i=1}^{m}\alpha_{i}\geq\frac{c(m-1)}{L}$;

the remaining elements in $\alpha_{1},\dots,\alpha_{k}$ are always greater or equal than $\frac{c}{L}$.

Hence, for each subsequence of length $l$, the sum of its elements is at least $\frac{c(l-1)}{L}$. This allows us to conclude that

Let Assumption 1(i, iii, iv) hold and $F$ be locally Lipschitz. Let $\phi\in\left(1,\frac{1+\sqrt{5}}{2}\right)$, $\gamma=\frac{1}{\phi}+\frac{1}{\phi^{2}}$, $c=\min_{m\geq 2}\frac{\phi}{m}\sqrt{\frac{\gamma^{m-1}-1}{\gamma-1}}>0$, and $\mathbf{Z}^{k}=\frac{1}{\sum_{i=1}^{k}\alpha_{i}}\sum_{i=1}^{k}\alpha_{i}\mathbf{z}^{i}$. Then, Alg. 1 with $\alpha_{0}$ as in (24) has the rate

Proof The result follows by using the definition of $\mathbf{Z}^{k}$ on the result of Lemma 3 and the lower bound of $\sum_{i=1}^{k}\alpha_{k}\geq\frac{(k-1)c}{L}$ derived in Lemma 4.

The last thing left to understand is the value of $c$. The next remark shows that it is large enough for a meaningful choice of parameters.

Setting $\phi=1.5$ as in the experiments of (Malitsky, 2020) direct calculation gives $c\geq 0.5$.

By proving a novel lower bound on the sum of the step sizes, we are able to prove a $\mathcal{O}(\frac{1}{k})$ convergence rate without requiring an artificial upper bound $\bar{\alpha}$ on each individual step. Not only does this simplify the aGRAAL method, but also removes the spurious $L^{2}$ dependence from (Malitsky, 2020), showing that there is basically no extra cost of adaptivity.

Nonmonotone problems with Weak Minty solutions

In Section 3, for monotone problems, we observed empirically that increasing $\phi$ leads to a certain speed-up, as in Fig. 2. In this section, we turn to a special class of nonmonotone problems and show that in some cases smaller $\phi$ can be also favorable.

In particular, we consider the class of problems exhibiting a weak Minty solution, which is given by a point $\mathbf{z}^{*}$ such that

This notion was recently introduced in (Diakonikolas et al., 2021) in the context of von Neumann ratio games — a nonconvex-nonconcave min-max problem — and further investigated in (Lee and Kim, 2021b; Pethick et al., 2022; Böhm, 2022). While it is difficult to verify the existence of such solutions in practice, the template simultaneously captures different generalizations of monotonicity like the existence of a Minty solution (Malitsky, 2020; Mertikopoulos et al., 2019) and negative comonotonicity (Lee and Kim, 2021a; Bauschke et al., 2020) in order to study nonconvex-nonconcave min-max problems. See (Lee and Kim, 2021a) for the implications between these different monotonicity concepts and (Gorbunov et al., 2022) for a comparison in terms of last iterate convergence. To our knowledge, we give the first adaptive algorithm for this setting that does not require a linesearch at every iteration and only relies on local Lipschitz continuity.

We first show the convergence of GRAAL with a constant step size.

Let $F$ be $L$-Lipschitz and fulfill Assumption (WM), with $\rho<\frac{1}{L}$. Let $\phi>1$ be such that $\delta:=\frac{2-\phi}{\phi L}-\rho>0$. Let $(\mathbf{z}^{k})$ and $(\bar{\mathbf{z}}^{k})$ be the iterates generated (GRAAL) with $\alpha=\frac{2-\phi}{L}$. Then

In the limiting case when $\phi$ is close to $1$ we can allow for $\rho<\frac{1}{L}$ in Theorem 7, which is precisely the best possible dependence for the (adaptive) EG$+$ method proven in (Pethick et al., 2022). For a more moderate choice, for example $\phi=\varphi=\frac{\sqrt{5}+1}{2}$, the bound on $\rho$ tightens to $\rho<\frac{1}{2L}$. See also Fig. 3 for empirical evidence of the need to reduce $\phi$ for problems with weak Minty solution.

Theorem 7 has the drawback of requiring knowledge of the weak Minty parameter $\rho$ to set $\phi$ such that $\delta>0$. In (Pethick et al., 2022) a similar problem was partially circumvented by an elaborate way to choose the corresponding parameter adaptively. Whether something similar can be done here is an open question. In practice, one can use a simple approach: run GRAAL with certain value of $\phi$; if it does not converge, decrease and try again.

2 Adaptive step size

We continue with the guarantees of aGRAAL under Assumption (WM).

Let $F$ be locally Lipschitz and fulfill Assumption (WM), and let $(\mathbf{z}^{k})$ be the sequence generated by (aGRAAL). As long as \delta:=\inf_{k}\alpha_{k}\Big{(}1+\frac{1}{\phi}-\gamma\phi\Big{)}-\rho>0 we have

where $c$ denotes the constant given in Lemma 4.

In particular, picking $\phi=1.1$ and $\gamma=1.1$ gives the condition $\rho<0.69\alpha_{k}$. As $\phi$ and $\gamma$ get closer to $1$, we can allow for $\rho<\alpha_{k}$, which would precisely be the dependence between $\rho$ and the step size proven in (Pethick et al., 2022) for CurvatureEG$+$, a version of EG with linesearch.

In the setting of Theorem 8, if the iterates happen to remain bounded, we only require

to deduce a similar convergence statement, but with modified constant.

The condition in Corollary 10 between the step sizes and the weak Minty parameter $\rho$ reduces, in the limiting case $\phi,\gamma\to 1$, to $\alpha_{k+1}+\alpha_{k}>\rho$. This corresponds to doubling of the range of $\rho$ presented in Remark 9.

In this section we relaxed the condition between the Lipschitz constant $L$ and parameter $\rho$ in (WM) to a condition between $\alpha_{k}$ and $\rho$. We do so in the hope that aGRAAL is able to take larger steps, since they are based on the local Lipschitz constants. Unfortunately, we cannot give a good lower bound on any individual $\alpha_{k}$ in general. We see from the experiments that the step size sometimes does become lower than the one chosen by linesearch (see Fig. 4). This seems to, however, not harm the performance of the algorithm.

3 Experiments

As discussed in the main section of the paper, in order to solve weak Minty problems, for all known methods two things are important: (i) the method needs to be modified in a way that could be interpreted as making it more “conservative”; (ii) step sizes should be large.

In the case of the golden ratio algorithm, the former means averaging with more of the (old) $\bar{\mathbf{z}}^{k-1}$ iterate, i.e. decreasing $\phi$, see Fig. 4. For EG this means reducing the step size in the update of the $\mathbf{z}^{k}$ sequence, as proposed in (Diakonikolas et al., 2021; Pethick et al., 2022). For the constant step size methods in question it seems like this is all we can do. However, by choosing the step sizes adaptively, be it via linesearch as for the CurvatureEG$+$ method from (Pethick et al., 2022), or by (3) in the case of (aGRAAL), we can hope to take steps larger than the global Lipschitz constant would allow.

In Fig. 4 the following problem formulation is used, which originated in (Hsieh et al., 2021, Example 5.2) as a particularly difficult instance of min-max under the name of “Forsaken”:

where $f(z)=\frac{1}{4}z^{2}-\frac{1}{2}z^{4}+\frac{1}{6}z^{6}$. This problem exhibits a solution at $(x^{*},y^{*})\approx(0.08,0.4)$, but also two limit cycles not containing any critical point of the objective function.

3.2 Polar Game

Fig. 3 and 5 display results on the so-called Polar Game introduced in (Pethick et al., 2022, Example 3) using the following parametrization for $a>0$

where $\psi(x,y)=a\frac{1}{4}x(-1+x^{2}+y^{2})(-1+4x^{2}+4y^{2})$. The problem exhibits a limit cycle attracting solutions away from the solution in the center.

Fig. 5 shows that reducing $\phi$ alone will not be enough for problems where $\rho>\frac{1}{L}$ is not satisfied (the blue line does not converge). One has to choose larger step sizes.

3.3 A lower bound (Pethick et al., 2022, Example 5)

In Pethick et al. (2022) it was shown that EG$+$ (with arbitrary small second step size) may diverge if $\rho>\frac{1}{L}$ via the following unconstrained min-max problems

for $a>0$ and $b<0$. The associated operator $F$, simply given by

is Lipschitz with $L=\sqrt{a^{2}+b^{2}}$ and $(0,0)$ is a weak Minty solution with constant $\rho=-\frac{2b}{a^{2}+b^{2}}$.

In Fig. 6 we see that, as predicted by Theorem 8 and Corollary 10, not only reducing $\phi$ but also decreasing $\gamma$ can prevent divergence. At first glance, this is somewhat surprising as larger $\gamma$ allows for a faster increase of the step size from one iteration to the next, and we have already seen that larger step sizes are important for convergence. We suspect this to be rooted in the special step size rule of aGRAAL, see (3), where one large step can lead to decrease in the step size of the next iteration.

Acknowledgments and Disclosure of Funding

The work of Axel Böhm was funded by the Austrian Science Fund (FWF): W1260-N35. The work of Ahmet Alacaoglu was funded by NSF awards 2023239 and 2224213; and DOE ASCR Subcontract 8F-30039 from Argonne National Laboratory. The work of Yura Malitsky was supported by the Wallenberg Al, Autonomous Systems and Software Program funded by the Knut and Alice Wallenberg Foundation, No. 305286.

Appendix A Details on Section 3

For convenience, we give a full description of the algorithm

We start with the following lemma which essentially summarizes the existing result of (Malitsky, 2020) for one iteration of the algorithm. Letting $\phi=2$ and $\varepsilon=0$ in this lemma gives (8) which is the starting point of Theorem 1.

Let Assumption 1 hold and $\alpha=\frac{\phi-2\varepsilon}{2L}$ for any $\varepsilon\in[0,\phi/2)$ in GRAAL. Then, for any $\mathbf{z}\in C$

Proof [of Lemma 13] By applying prox-inequality to the definition of $\mathbf{z}^{k+1}$, we have for any $\mathbf{z}\in C$ that

Similarly, with the definition of $\mathbf{z}^{k}$, we have

Since $\mathbf{z}^{k}-\bar{\mathbf{z}}^{k-1}=\frac{1+\phi}{\phi}(\mathbf{z}^{k}-\bar{\mathbf{z}}^{k})=\phi(\mathbf{z}^{k}-\bar{\mathbf{z}}^{k})$, we can rewrite (30) as

Expressing the first two terms in (32) by norms and using the definition of $G(\mathbf{z}^{k},\mathbf{z})$ from (7), we deduce

The definition of $\bar{\mathbf{z}}^{k}$ gives

where the second equality used $\bar{\mathbf{z}}^{k+1}-\bar{\mathbf{z}}^{k}=\frac{\phi-1}{\phi}(\mathbf{z}^{k+1}-\bar{\mathbf{z}}^{k})$.

Additionally, from $\alpha=\frac{\phi-2\varepsilon}{2L}$ and Young’s inequality, we have

Using (34), (35), and $\phi^{2}\|\mathbf{z}^{k}-\bar{\mathbf{z}}^{k}\|^{2}=\|\mathbf{z}^{k}-\bar{\mathbf{z}}^{k-1}\|^{2}$ on (33) gives the desired conclusion.

Let Assumption 1 hold. Then for the first iteration of Alg. 2, we have that

Proof Recall that $\mathbf{z}^{1}=P_{C}(\mathbf{z}^{0}-\alpha F(\mathbf{z}^{0}))$ and $\mathbf{z}^{*}=P_{C}(\mathbf{z}^{*}-\alpha F(\mathbf{z}^{*}))$. The former is because $\bar{\mathbf{z}}^{0}=\mathbf{z}^{0}$ by the initialization in Alg. 2. The latter follows by the definition of $\mathbf{z}^{*}$ as a solution of (1). By firm-nonexpansiveness of $P_{C}$, we have

Expanding the terms in the right-hand side we have that

By monotonicity, we have $\langle F(\mathbf{z}^{0})-F(\mathbf{z}^{*}),\mathbf{z}^{0}-\mathbf{z}^{*}\rangle\geq 0$. By using $\alpha\leq\frac{1}{L}$, we have

Combining the last two estimates for the inner products in (36), we have

A.2 Alternative proof of Theorem 1 via SDP

The proof of boundedness of $(\mathbf{z}^{k})$ presented in the main part was not very standard. In this section, we provide an alternative proof of that fact which is based on a semidefinite program combined with induction. This approach is easily generalizable to the case of $\phi<2$ even though we give it for $\phi=2$ for simplicity.

As before, we assume that $\|\bar{\mathbf{z}}^{i}-\mathbf{z}^{*}\|^{2}\leq 2R^{2}$ for all $i=1,\dots,k$ and we must show that $\|\bar{\mathbf{z}}^{k+1}-\mathbf{z}^{*}\|^{2}\leq 2R^{2}$. Our main tool will be inequality (11) which holds for all $k\geq 1$ and which we recall here

Without loss of generality, we assume that $\mathbf{z}^{*}=0$ and that $R^{2}=\|\mathbf{z}^{1}-\mathbf{z}^{*}\|^{2}+\|\mathbf{z}^{0}-\mathbf{z}^{*}\|^{2}\leq 1$. The first assumption is valid because we can always redefine sequences as $\mathbf{z}^{k}:=\mathbf{z}^{k}-\mathbf{z}^{*}$ and $\bar{\mathbf{z}}^{k}:=\bar{\mathbf{z}}^{k}-\mathbf{z}^{*}$, while the second — because we can rescale the norm $\|\cdot\|$ by any positive number.

Using these two assumptions and that $\mathbf{z}^{k}=2\bar{\mathbf{z}}^{k}-\bar{\mathbf{z}}^{k-1}$ we can rewrite (37) as

The latter inequality is quadratic in $\bar{\mathbf{z}}^{k+1},\bar{\mathbf{z}}^{k},\bar{\mathbf{z}}^{k-1}$. Hence, after expanding the norms, we can rewrite it in a matrix notation as

By induction assumption we have that $\mathbf{G}_{22}\leq 2$ and $\mathbf{G}_{33}\leq 2$ and we must show that $\mathbf{G}_{11}\leq 2$. Consider the following semidefinite program

If we can show that its optimal value is less than $2$, then we are done: it will automatically imply that $\|\bar{\mathbf{z}}^{k+1}\|^{2}\leq 2$. Now, by solving it, we obtain $\mathbf{G}_{11}\approx 1.49259$.

Therefore, we have proved that for all $k$, $\|\bar{\mathbf{z}}^{k}-\mathbf{z}^{*}\|^{2}\leq 2R^{2}$.

The semidefinite program actually allows us to show a slightly tighter bound: $\|\bar{\mathbf{z}}^{k}-\mathbf{z}^{*}\|^{2}\leq 1.2R^{2}$, but we kept the constant $2$ for consistency with the previous approach.

Appendix B Details for Section 4

In (24) we outline a very particular linesearch which decreases $\alpha_{0}$ by $\gamma$ in every step. Since the canonical choice of $\phi$ proposed in (Malitsky, 2020) yields the small $\gamma=1.1$ this could result in many backtracking iterations if our initial guess is bad. For practical implementation, therefore, it is better to use first a coarse reduction of $\alpha_{0}$, say with a factor of $10$ and only at the end to switch to a fine factor $\gamma$.

Appendix C Weak Minty proofs

By following the line of reasoning as in the monotone case one can only derive $\rho<\frac{1}{2L}$. We do not present the proof here but it is only a simple modification similar to the one we show later for the adaptive step size. In order to derive the $\rho<\frac{1}{L}$ bound (matching EG) one has to take a completely different approach. The high-level reason is that the monotone analysis requires $\alpha\leq\frac{\phi}{2L}$. This is counter intuitive as a smaller $\phi$ makes (GRAAL) more conservative since the iterates are more anchored to $\bar{\mathbf{z}}^{k}$, and at the same time requires a smaller step size. A more conservative averaging of the iterates should allow for a more aggressive step size, which is precisely the behavior we observe here. For convenience let $\mathbf{g}^{k}=F(\mathbf{z}^{k})$.

Let $F$ be $L$-Lipschitz and fulfill Assumption (WM). Let $(\mathbf{z}^{k})$ and $(\bar{\mathbf{z}}^{k})$ be the iterates generated (GRAAL). Then

Proof First we observe simply from the definition of the iterates

where we used (WM) to deduce the inequality. Now we want to prove the following equality

We can verify this by expanding all iterates in terms of operators. Observe first that

Therefore, by multiplying both sides by $\frac{3-\phi}{\phi-1}$ we get

Again, by going to $\mathbf{g}^{k}$ everywhere we have

and therefore by multiplying both sides by $\frac{4}{\phi-1}$

We can deduce (41) by simplifying the above equation. The statement of the lemma is obtained by combining (41) and (40).

Therefore, in order to telescope we require

and $2\phi-\phi^{2}\geq\alpha L$ for the last term to be nonnegative. The condition (48) can be simplified to

and the nonnegativity condition becomes redundant. We observe that, if $\rho<\frac{1}{L}$, then we can pick $\rho$ close enough to one such that $\frac{2-\phi}{\phi L}>\rho$. The final bound we obtain by

C.2 Adaptive step size

The analysis of (aGRAAL) relies on a similar energy function as before. So with slight abuse of notation we (re-)define for the purpose of this section

Proof [of Theorem 8] The first few steps of our analysis follow the one presented in (Malitsky, 2020) so we do not reproduce them here. We continue from (34) in (Malitsky, 2020), which reads

By using the weak Minty property (WM) this reduces to

which can be ensured, by the fact that $\theta_{k}\leq\gamma\phi$, if

holds, then after telescoping, where we unroll the recursion until $k=1$ as argued in the proof of Lemma 3, to obtain

Note that in order to guarantee just $\liminf_{k}\|F(\mathbf{z}^{k})\|=0$ it is sufficient to ask for

meaning that we can allow for arbitrarily many step size to not fulfill the condition $\delta>0$, but for the sequence on average.

In the presence of bounded iterates we were able to relax the conditions of Theorem 8. Let $M$ denote the diameter of the ball containing the iterates.

Proof [of Corollary 10] After telescoping (52) we get

Let us first observe that the nonnegativity of the factor in front of $\|F(\mathbf{z}^{i})\|^{2}$ can be guaranteed via

since $\theta_{k}\leq\gamma\phi$. Also, the last term on the right hand side of (54) can be bounded via

where the last term on the right remains bounded due to the assumed boundedness of the iterates. To deduce the precise constant we observe

Appendix D Details on experiments

For the left plot in Fig. 2 we use the Lagrangian formulation of a linearly constrained quadratic program

D.2 Weak minty experiments

For (aGRAAL) $\phi$ is usually given in the legend, except for Fig. 1 where we used the default $\phi=1.5$. If $\gamma$ is not given in the legend we use the theoretical upper bound $1/\phi+1/\phi^{2}$.

For CurvatureEG$+$ we use a backtracking linesearch initialized with $\nu\|JF(\mathbf{z}^{k})\|^{-1}$, where we use $\nu=0.99$ and $JF$ denotes the Jacobian of $F$. We ignore the extra cost of this initialization but do count the extra gradient evaluations from the backtracking, where in every step the step size is decreased by $\tau=0.9$.

D.2.2 Polar Game

The unique solution for this problem is in the origin. The Lipschitz constant $L$ and the weak Minty parameter $\rho$ we approximate numerically, via a grid search on the interval $[-1.1,1.1]\times[-1.1,1.1]$. In Fig. 3 the value $a=1/3$ is used whereas in Fig. 5 is given by $a=3.7$. For $a=1/3$ we get $L\approx 6.94$ and $\rho\approx 0.09$, whereas for $a=3$ we compute $L\approx 61.4$ and $\rho\approx 0.72$. In the latter case we observe from the result of the linesearch, see Fig. 5, that these global estimates are quite pessimistic but even locally the necessary condition $\rho<\alpha_{k}$ is not satisfied for CurvatureEG$+$, which is why we observe its divergence.

References