summaries: This paper constructs methods named CurvatureEG+ (and Adaptive EG+ and CEG+), built upon a recently proposed EG+ [Diakonikolas et al., 2021], a variant of EG, that works under the weak MVI condition. Most importantly, the CurvatureEG+ (and Adaptive EG+/CEG+) works for a range (of the weak MVI) larger than that of EG+. The corresponding nonconvex-nonconcave setting includes non-trivial problems illustrated in the paper, where the proposed method converges, while other existing methods reach limit cycles. Unlike EG+, the CurvatureEG+ can handle both constrained and composite cases. A stochastic variant is also studied. Although the experiments consider toyish problems, they seem interesting.

summaries: This paper focuses on variants of ExtraGradient (EG) by considering different options for the two step-sizes of the method: one for the extrapolation step and the second for the iterate update.  Building on the analysis of (Diakonikolas et al. 2021),  the paper relaxes the setup therein by allowing a larger range of values for the $\rho$ parameter (see Fig. 2) of weak Minty Variational Inequality (MVI) which parameter controls the degree of nonconvexity.  In particular, it provides the following contributions: *(i)* Primarily it defines Alg.1 where the step size for the iterate update is adaptive and shows the main convergence result (Thm  3.1.) that under some assumptions (Asm 1), Alg. 1 converges on weak MVI problem. *(ii)* It then considers a non-adaptive variant of Alg. 1, dubbed CEG+, which can be seen as a generalization of the EG+ method of (Diakonikolas et al. 2021), and complements the result of the latter by showing that the convergence result is tight on weak MVI; *(iii)* extends CEG+ by using an adaptive scheme for the first step size (for the extrapolation) which uses Lipschitz constant backtracking, and Alg.1 for the latter step size (for the iterate update), dubbed CurvatureEG+, which method is shown to empirically converge on some toy-examples on which CEG+ does not; *(iv)* finally, for the stochastic setup the authors consider one of the step-sizes to be diminishing and the other can be constant, and show that this variant converges on weak MVI problems.

summaries: This paper proposed CEG+ and CurvatureEG+, which extend extragradient method to a proximal variant (regarding the operator $A$), and apply it in nonconvex-nonconcave minimax optimization with Weak MVI condition in both deterministic and stochastic cases, and proved their complexities, which has the same order as those in literature (e.g., Diaonikolas et al., 2021). The authors also studied the lower bound in the simpler case when $A\equiv 0$, showing a difference compared to EG+ in (Diaonikolas et al., 2021).  In the deterministic case, it proposed an adaptive stepsize strategy to allow larger range of the MVI parameter $\rho$, and further a curvature-based strategy to avoid the lower bound requirement of $\rho$. The authors also executes several experiments, showing that CurvatureEG+ can avoid cycling in the experiments.

summaries: This work extends the extragradient algorithm in Diakonikolas et al. (2021) from unconstrainted and unregularized inclusion problems that satisfy weak Minty inequality (MVI) to their constrained and regularized counterparts. Compared with the original extragradient algorithm, the extended algorithm is proved to converge with a larger range of stepsize choices and MVI-related constant $\rho$ (implying a larger set of applicable problems) in both deterministic and stochastic inclusion problems. The range of $\rho$ is also proved tight by providing a lower bound of $\rho$. The extended algorithm also generalizes the celebrated forward-backward-forward (FBF) algorithm in Tseng (2000). Finally, an improvement of this extended algorithm is proposed using Lipschitz constant backtracking.

abstractText: This paper introduces a new extragradient-type algorithm for a class of nonconvex-nonconcave minimax problems. It is well-known that finding a local solution for general minimax problems is computationally intractable. This observation has recently motivated the study of structures sufficient for convergence of first order methods in the more general setting of variational inequalities when the so-called weak Minty variational inequality (MVI) holds. This problem class captures non-trivial structures as we demonstrate with examples, for which a large family of existing algorithms provably converge to limit cycles. Our results require a less restrictive parameter range in the weak MVI compared to what is previously known, thus extending the applicability of our scheme. The proposed algorithm is applicable to constrained and regularized problems, and involves an adaptive stepsize allowing for potentially larger stepsizes. Our scheme also converges globally even in settings where the underlying operator exhibits limit cycles. Moreover, a variant with stochastic oracles is proposed—making it directly relevant for training of generative adversarial networks. For the stochastic algorithm only one of the stepsizes is required to be diminishing while the other may remain constant, making it interesting even in the monotone setting.

authors:
Waïss Azizian
Ioannis Mitliagkas
Simon Lacoste-Julien
Gauthier Gidel

authors:
Heinz H. Bauschke
Patrick L. Combettes

venue: CMS Books in Mathematics. Springer,

authors:
Heinz H Bauschke
Walaa M Moursi
Xianfu Wang

venue: Mathematical Programming,

authors:
Michel Benaım
Morris W Hirsch

venue: Games and Economic Behavior,

title: Nonlinear programming

venue: Journal of the Operational Research Society,

authors:
Axel Böhm
Michael Sedlmayer
Ernö Robert Csetnek
Radu Ioan Boţ

authors:
Constantinos Daskalakis
Dylan J Foster
Noah Golowich

venue: arXiv preprint arXiv:2101.04233,

authors:
Constantinos Daskalakis
Stratis Skoulakis
Manolis Zampetakis

authors:
Damek Davis
Dmitriy Drusvyatskiy

authors:
Jelena Diakonikolas
Constantinos Daskalakis
Michael Jordan

authors:
Francisco Facchinei
Jong-Shi Pang

venue: Springer Science & Business Media,

authors:
Tanner Fiez
Lillian Ratliff

venue: arXiv preprint arXiv:2009.14820,

authors:
Gauthier Gidel
Hugo Berard
Gaëtan Vignoud
Pascal Vincent
Simon Lacoste-Julien

venue: arXiv preprint arXiv:1802.10551,

venue: SIAM Journal on Optimization,

authors:
Martin Heusel
Hubert Ramsauer
Thomas Unterthiner
Bernhard Nessler
Sepp Hochreiter

venue: Advances in neural information processing systems,

authors:
M Hirsch
S Vavasis

authors:
Cars H Hommes
Marius I Ochea

authors:
Ya-Ping Hsieh
Panayotis Mertikopoulos
Volkan Cevher

authors:
Yu-Guan Hsieh
Franck Iutzeler
Jérôme Malick
Panayotis Mertikopoulos

venue: arXiv preprint arXiv:2003.10162,

authors:
Chi Jin
Praneeth Netrapalli
Michael I. Jordan

authors:
Puya Latafat
Panagiotis Patrinos

venue: Computational Optimization and Applications,

authors:
Sucheol Lee
Donghwan Kim

venue: arXiv preprint arXiv:2106.02326,

venue: arXiv preprint arXiv:2105.15042,

authors:
Eric V. Mazumdar
Michael I. Jordan
S. Shankar Sastry

authors:
Panayotis Mertikopoulos
Bruno Lecouat
Houssam Zenati
Chuan-Sheng Foo
Vijay Chandrasekhar
Georgios Piliouras

venue: arXiv preprint arXiv:1807.02629,

authors:
Panayotis Mertikopoulos
Christos Papadimitriou
Georgios Piliouras

title: Cycles in adversarial regularized learning

title: Monotone (nonlinear) operators in hilbert space

venue: Duke Mathematical Journal,

authors:
Maher Nouiehed
Maziar Sanjabi
Tianjian Huang
Jason D Lee
Meisam Razaviyayn

venue: Journal of Computer and system Sciences,

title: Fast exact multiplication by the hessian

venue: Neural computation,

title: Introduction to optimization

venue: Optimization Software New York,

authors:
Hassan Rafique
Mingrui Liu
Qihang Lin
Tianbao Yang

authors:
R.T. Rockafellar
R.J.-B. Wets

title: Variational analysis, volume 317

venue: SIAM journal on control and optimization,

title: Convex analysis

authors:
M.V. Solodov
P. Tseng

venue: SIAM Journal on Control and Optimization,

authors:
Mikhail V Solodov
Benar F Svaiter

title: A hybrid projection-proximal point algorithm

venue: Journal of convex analysis,

authors:
Chaobing Song
Zhengyuan Zhou
Yichao Zhou
Yong Jiang
Yi Ma

venue: arXiv preprint arXiv:2103.04410,

venue: American Mathematical Soc.,

authors:
Junchi Yang
Negar Kiyavash
Niao He

venue: arXiv preprint arXiv:2002.09621,

authors:
Zhengyuan Zhou
Panayotis Mertikopoulos
Nicholas Bambos
Stephen Boyd
Peter W Glynn

title: Let A : n Ñ n denote a single valued operator. Then, (i) A is 1-Lipschitz if and only if T “ id ́ A is 1{2-cocoercive. (ii) If A is L-Lipschitz, then T “ id ́ ηA, η P p0, 1{Lq, is p1 ́ ηLq-monotone, and in particular }Tu ́ Tv} ě p1 ́ ηLq}u ́ v} for all u, v P n

text:
1 Introduction
Many machine learning applications, from generative adversarial networks (GANs) to robust reinforcement learning, result in nonconvex-nonconcave constrained minimax problems, which pose notorious difficulties to the scalable (stochastic) first order methods. Indeed, there is no shortage of results illustrating divergent or cycling behavior when going beyond minimization problems (Benaım & Hirsch, 1999; Hommes & Ochea, 2012; Mertikopoulos et al., 2018b; Hsieh et al., 2021).
Traditionally, minimax problems have been studied for more than half a century under the umbrella of the variational inequalities (VIs). The extragradient-type algorithms from the VI literature was recently brought to the awareness of the machine learning community (Mertikopoulos et al., 2018a; Gidel et al., 2018; Böhm et al., 2020), and have provided a principled way of stabilizing training and avoiding Poincaré recursions. However, these results mostly concern the convex-concave setting.
In nonconvex-nonconcave minimax problems, or more generally nonmonotone variational inequalities (VIs), even finding a local solution is in general intractable. This has been made precise through exponential lower bound of the classical optimization type (Hirsch & Vavasis, 1987) and computational complexity results (Papadimitriou, 1994; Daskalakis et al., 2021b). This is in sharp contrast to minimization problems, where only finding a global solution is intractable. The recent result of (Hsieh et al., 2021) provides some intuition behind this difference by showing that the asymptotic limits of most schemes, including extragradient, can converge to attracting limit cycles.
To make progress in lieu of these negative results, Diakonikolas et al. (2021) proposes a simple generalization of extragradient, called (EG+), that can converge to a stationary point even for a class of nonmonotone problems provided that the weak Minty variational inequality (MVI) holds. This problem class is parametrized by a constant ρ, which controls the degree of nonconvexity. However,
˚Laboratory for Information and Inference Systems (LIONS), EPFL (thomas.pethick@epfl.ch) :Department of Electrical Engineering (ESAT-STADIUS), KU Leuven ;Laboratoire Traitement et Communication d’Information, Télécom Paris, Institut Polytechnique de Paris
given the range of ρ in Diakonikolas et al. (2021), the new class is still too small to include even the simplest counterexample of Hsieh et al. (2021) for the general Robbins-Monro schemes.
Contributions Building on the analysis in Diakonikolas et al. (2021), we propose a new adaptive scheme, called (CurvatureEG+), that converges even in the difficult counter example of Hsieh et al. (2021) as illustrated in Fig. 1. Our main contributions are summarized below.
1. We propose an adaptive extragradient-type algorithm that converges for a larger range of ρ, the parameter in the weak MVI assumption (cf. Assumption I(iii)) than previously known. 2. More importantly, we show that convergence is ensured if 2ρ`γk ą 0, where γk is the extrapolation stepsize. This is crucial since by selecting γk through a backtracking procedure larger stepsizes are allowed, which in turn implies convergence for more negative values of ρ, thus capturing a larger class of problems. In addition, we show that the linesearch eventually passes without triggering any backtrack if initialized based on the Jacobian of F (cf. Section 4). 3. We present a non-adaptive variant of our algorithm (CEG+), and show that for particular parameter choices (EG+) of Diakonikolas et al. (2021), and when ρ “ 0 the celebrated forwardbackward-forward (FBF) algorithm of Tseng (2000) are recovered, thus unifying and generalizing both methods. We improve upon Diakonikolas et al. (2021) by not only relaxing the problem class but also the stepsize range. We show that our results are tight by providing a matching lower bound, thus providing a complete picture of (EG+) under weak MVI. 4. In the stochastic setting, similarly to Hsieh et al. (2020), we consider two separate stepsizes. Whereas they require both to be diminishing we show that the extrapolation step can in fact be picked constant—a modification which is critical for convergence when only the weak MVI holds.
Related work The community has resorted to various approaches to make progress for nonconvex-nonconcave minimax problems. One line of work focuses on deriving local convergence results (Mazumdar et al., 2019; Fiez & Ratliff, 2020; Heusel et al., 2017). For global results, the two primary approaches have been to either assume a global oracle for the inner problem (Jin et al., 2019; Davis & Drusvyatskiy, 2018) or assume particular problem structure such as the PolyakŁojasiewicz condition (Nouiehed et al., 2019; Yang et al., 2020) or concavity for the inner problem (Rafique et al., 2019).
We follow the same tradition of assuming structure, but from the general perspective of operator theory. The idea of studying minimax and related problems through the lens of variational inequality has a long history (Minty, 1962; Rockafellar, 1976; Polyak, 1987; Bertsekas, 1997), with recent renewed interest due to its relevance for minimax formulations (Mertikopoulos et al., 2018a; Gidel et al., 2018; Azizian et al., 2020).
One relaxation of the monotone case for which we have positive results is that of Minty variational inequalities (MVI) (Mertikopoulos et al., 2018a; Song et al., 2021; Zhou et al., 2017), which includes all quasiconvex-concave and starconvex-concave problems. Diakonikolas et al. (2021) introduced the relaxed condition of weak MVI. In the unconstrained setting they showed non-asymptotic convergence results under a restricted problem constant ρ. Similarly to us, Lee & Kim (2021a) extends the regime but under the stronger condition of cohypomonotonicity. They do so by studying a more evolved variant of extragradient building on anchoring techniques. We instead directly improve upon (EG+) and generalize it to new settings.
In the stochastic setting, usually the stepsize for the extrapolation step is diminishing. This is the case in Böhm et al. (2020) where they consider a forward-backward-forward type scheme. However, they remain in the monotone setting, where the limit cycles are non-attracting, as exemplified by a bilinear game. Hsieh et al. (2021) recently showed that a large family of algorithms, which includes the extragradient method with diminishing stepsize, can converge to attracting limit cycles. Going beyond this restriction, Hsieh et al. (2020) interestingly considers two separate stepsizes similar to us. However, only the more restrictive setting where MVI is satisfied is considered, and both of the stepsizes are required to be diminishing.
2 Problem formulation and preliminaries
In this paper we are interested in finding zeros of an operator (or set-valued mapping) T : n Ñ n that is written as the sum of a Lipschitz continuous (but possibly nonmonotone) operator F and a maximally monotone operator A. That is, we wish to find z P n such that the general inclusion
0 P Tz B Az` Fz (2.1) holds. The set of all such points is denoted by zer T B tz P Rn | 0 P Tzu. Throughout the paper problem (2.1) is studied under the following assumptions (definitions can be found in Appendix A).
Assumption I. In problem (2.1),
(i) Operator A : n Ñ n is a maximally monotone operator.
(ii) Operator F : n Ñ n is L-Lipschitz continuous.
(iii) Weak Minty inequality (MVI) holds, i.e., there exists a nonempty set S‹ Ď zer T such that for all z‹ P S‹ and some ρ P p´ 12L ,8q
xv, z´ z‹y ě ρ}v}2, for all pz, vq P gph T. (2.2)
Generally, we do not require the weak Minty assumption to hold at every z‹ P zer T . In fact, as shown in Theorem 3.1 nonemptiness of S‹ is sufficient for ensuring that the limit points belong to zer T . Interestingly, despite nonmonotonicity of F, global (as opposed to subsequential) convergence can be established when S‹ “ zer T , an assumption that is still weaker than cohypomonotonicity. VIs provide a convenient abstraction for a range of problems. We mention some central examples below but otherwise defer to the overview in Facchinei & Pang (2007). Subsequently, we provide examples where the weak MVI holds.
Example 1: (minimax optimization). A comprehensive way to capture a wide range of applications in machine learning is to consider structured minimax problems of the form
minimize xP nx maximize yP ny Lpx, yq B ϕpx, yq ` gpxq ´ hpyq, (2.3)
where ϕ is not necessarily convex in x or concave in y. Functions g and h are proper extended real-valued lower semicontinuous and convex, with easy to compute proximal maps. Common examples for g and h involve regularizers such as `1, `2 norms, or indicator functions of sets allowing us to capture constrained minimax problems. The first order optimality condition associated with this problem may be written in the form of the structured inclusion (2.1) by letting Fz “ p∇xϕpx, yq,´∇yϕpx, yqq, Az “ pBgpxq, Bhpyqq.
As it will become clear in the next section (cf. Algorithm 1), the main computations involved in the proposed scheme are evaluations of F and resolvent JA “ pid` Aq´1. Recall that the resolvent of a
maximally monotone operator is firmly nonexpansive with full domain (cf. (Bauschke & Combettes, 2017, Sect. 23)). If A “ B f is the subdifferential operator of a convex function f , then its resolvent is the proximal mapping. For instance when A is as in Example 1, then its resolvent is given by JApx, yq “ pproxgpxq,proxhpyqq.
Example 2: (N-player games). More generally, we can consider a continuous game of N players in normal form. Denote the decision variables z :“ pzi; z´iq :“ pz1, ..., zNq and let the loss incurred by the ith player be Lipzi; z´iq “ ϕipzq ` gipziq where ϕi is the payoff function and gi typically enforce constraints on zi. Then we seek a Nash equilibrium, which is any decision which is unilaterally stable, i.e., Lipz‹i ; z‹´iq ď Lipzi; z‹´iq @zi and i P rNs B t1, . . . ,Nu. (2.4) The corresponding first order optimality conditions may be written as Az “ pBg1pz1q, . . . , BgNpzNqq and Fz “ p∇z1ϕ1pzq, . . . ,∇zNϕNpzqq.
A solution to (2.1) thus returns a candidate for which the first order condition of the above problems is satisfied. In the monotone case these two solution concepts coincide, while in the more general case of weak MVI, we provide examples where this still holds. In particular, we introduce in Section 5 a nonconvex-nonconcave minimax game which additionally exhibits limit cycles for Fz. As a consequence most schemes including gradient descent ascent, extragradient and optimistic gradient descent ascent do not converge to a stationary point globally (Hsieh et al., 2021). However, the global Nash equilibrium satisfies Assumption I(iii) with ρ ą ´1{2L, which we show is sufficient for global convergence of (CEG+).
The weak MVI condition is satisfied in certain reinforcement learning settings. Specifically, Diakonikolas et al. (2021); Daskalakis et al. (2021a) considers a two-player zero-sum game where the weak MVI holds, while neither MVI nor cohypomonotonicity holds. Interestingly, the formulation requires constraint—a condition they do not handle. We thus provide the first provable algorithm for this setting. Weak MVI also contains all quasiconvex-concave and starconvex-concave problems. For further examples, the literature on cohypomonotonicity (Bauschke et al., 2020) is relevant since it implies weak MVI, see for instance Lee & Kim (2021b, Example 1).
3 Generalizing Extragradient+
Our starting point is the Extragradient+ (EG+) algorithm of Diakonikolas et al. (2021) which is identical to extragradient (Korpelevich, 1976) except for the second stepsize being smaller. They only treat the inclusion (2.1) when A ” 0, and in our notation require ρ P p´1{8L, 0s. Specifically,
z̄k “ zk ´ γkFzk, zk`1 “ zk ´ ᾱkγkFz̄k (EG+) where they choose γk “ 1{L and ᾱk “ 1{2 (Diakonikolas et al., 2021, Thm. 3.2). We generalize (EG+) in Algorithm 1 to take the operator A into account—consequently we capture constraint and regularized problems as well. In addition, the scheme is adaptive in ᾱk. We will show that the weaker requirement of ρ P p´1{2L,8q suffices even for the more general inclusion (2.1). The main convergence results of Algorithm 1 are established in the next theorem. The proof is largely inspired by recent developments in operator splitting techniques in the framework of monotone inclusions (Latafat & Patrinos, 2017; Giselsson, 2021). The key idea lies in interpreting each iteration of the algorithm as a projection onto a certain hyperplane, an interpretation that dates back to Solodov & Tseng (1996); Solodov & Svaiter (1999). Theorem 3.1. Suppose that Assumption I holds, and let λk P p0, 2q, γk P ` t´2ρu`, 1{L ‰
where txu` B maxt0, xu, δk P p´γk{2, ρs, lim infkÑ8 λkp2 ´ λkq ą 0, and lim infkÑ8pδk ` γk{2q ą 0. Consider the sequences pzkqkP , pz̄ kqkP generated by Algorithm 1. Then for all z ‹ P S‹,
min k“0,1,...,m 1 γ2k }Hz̄k ´ Hzk}2 ď 1 κpm`1q}z 0 ´ z‹}2, (3.1)
where κ “ lim infkÑ8 λkp2´ λkqpδk ` γk{2q2. Moreover, the following holds
(i) pz̄kqkP is bounded and its limit points belong to zer T;
(ii) if in addition lim supkÑ8 γk ă 1{L and S‹ “ zer T, then pzkqkP , pz̄kqkP both converge to some z‹ P zer T.
Algorithm 1 (AdaptiveEG+) Deterministic algorithm for problem (2.1)
Initialize z0 “ zinit P n, λk P p0, 2q, γk P ` t´2ρu`, 1{L ‰ , δk P p´γk{2, ρs, Repeat for k “ 0, 1, . . . until convergence 1.1: Let z̄k “ ` id` γkA ˘´1`zk ´ γkFzk ˘ 1.2: Compute stepsize
αk “ δkγk ` xz̄k ´ zk,Hz̄k ´ Hzky }Hz̄k ´ Hzk}2 ,
where H “ id´ γkF. 1.3: Update the vector zk`1 “ zk ` λkαkpHz̄k ´ Hzkq Return zk`1
Note that whenever lim supkÑ8 γk ă 1L , Lemma A.3(ii) may be used to derive a similar inequality in terms of }z̄k ´ zk} by lower bounding }Hz̄k ´Hzk} in (3.1). We also remark that tighter rates may be obtained in the regime ρ ě 0, however, this will not be pursued in this work.
3.1 Non-adaptive stepsize variant
Although we do not incur additional costs for evaluating the adaptive stepsize αk in step 1.2, it proves instructive to present a variant with constant stepsize. As a result we compare the range of our stepsizes against Diakonikolas et al. (2021) showing an improvement by a factor of 3{2. Moreover, in the monotone case (ρ “ 0), with a certain choice of stepsizes the algorithm reduces to the celebrated forward-backward-forward (FBF) algorithm of Tseng (2000). We remark that the relation of FBF to projection-type algorithms was noted in Tseng (2000), (Giselsson, 2021, Sect. 6.2.1).
To this end, in this subsection consider the following non-adaptive variant of Algorithm 1 that generalizes (EG+). Letting ᾱk P p0, 1` 2δk{γkq:
z̄k “ ` id` γkA ˘´1`zk ´ γkFzk ˘ , zk`1 “ zk ` ᾱkpHz̄k ´ Hzkq. (CEG+) The convergence of this algorithm is an immediate byproduct of Theorem 3.1. To see this, note that the zk`1 update in step 1.3 may be written as zk`1 “ zk ` 2ηkαkpHz̄k ´ Hzkq, for ηk P p0, 1q. Therefore, convergence is still ensured for any ᾱk ă 2αk as the difference may be absorbed by the relaxation parameter ηk. Note that by 1{2-cocoercivity of H (cf. Lemma A.3(i))
ᾱk ă 2δkγk ` 1 ď 2δk γk ` 2xHz̄k ´ Hzk, z̄k ´ zky }Hz̄k ´ Hzk}2 “ 2αk, (3.2)
establishing the validity of the prescribed stepsize range. The convergence of the non-adaptive variant is summarized in the next corollary that for simplicity is stated with constant parameters (dropping subscripts k). Corollary 3.2 (Constant stepsize). Suppose that Assumption I holds, and let γ P ` t´2ρu`, 1{L ‰
, δ P p´γ{2, ρs, and ᾱ P p0, 1 ` 2δ{γq. Consider the sequences pzkqkP , pz̄
kqkP generated according to the update rule (CEG+). Then,
min k“0,1,...,m
}Hz̄k ´ Hzk}2 ď }z0 ´ z‹}2
κpm` 1q , (3.3)
where κ “ ᾱp1` 2δ γ ´ ᾱq. Moreover, the claims of Theorems 3.1(i) and 3.1(ii) hold true.
The setting of Diakonikolas et al. (2021) in (EG+) involves the stepsizes γk “ 1{L, αk “ 1{2. Note that when restricting to A ” 0, the iterates (CEG+) simplify to this form owing to the fact that Hz̄k´Hzk “ z̄k´γFz̄k´Hzk “ ´γFz̄k. In comparison, in our setting if δ “ ρ “ ´1{8L (the smallest ρ permitted in Diakonikolas et al. (2021)) is selected, then based on our analysis in Corollary 3.2 we may select γk “ 1{L, and ᾱk P p0, 3{4q, thus the upper bound for the second stepsize is 3{2 times that of Diakonikolas et al. (2021). Remark 3.3 (relation to FBF). In Corollary 3.2 the range of stepsizes γ, ᾱ may alternatively be set as γ P ` t´2ρu`, 1{L ˘
, ᾱ P p0, 1`2δ{γs. This is due to the fact that if γ ă 1{L (strictly), then H is strictly 1{2-cocoercive. Therefore, in (3.2), 1` 2δ
γ ă 2αk holds, and thus the stepsize ᾱ “ 1` 2δγ is permitted.
Although this may appear to be of little practical significance, by setting γ P p0, 1{Lq, δ “ ρ “ 0,
and ᾱ “ 1 in (CEG+), we obtain zk`1 “ z̄k ` γFzk ´ γFz̄k, which is the forward-backward-forward (FBF) algorithm of Tseng (2000), (Bauschke & Combettes, 2017, Thm. 26.17)).
3.2 Lower bounds
We show that the result in Corollary 3.2 is tight by providing a matching lower bound when A ” 0. We do so by fixing ᾱk and showing a stepsize dependent lower bound. In particular, note that if ᾱk “ 1{2 as in Diakonikolas et al. (2021, Thm. 3.2), then Theorem 3.4 implies a lower bound of ρ ą ´1{4L for the (EG+) scheme. The lower bound is contextualized in Fig. 2 by relating it to our convergence results and existing results in the literature. Theorem 3.4. Consider a sequence pzkqkPN generated according to (EG+) fixing γk “ γ “ 1{L and ᾱk “ ᾱ P p0, 1q. Let ´ρL ě 1´ᾱ2 . Then, there exists an F :
n Ñ n, n ą 1, satisfying Assumption I(ii) and Assumption I(iii) for which the sequence will not converge.
3.3 Stochastic setting
In this section we assume that one has access only to independent samples of F that will be denoted by F̂p¨, ξq depending on some random variable ξ whose distribution is revealed online by observations of i.i.d. copies of ξ. We make the following standard assumptions. Assumption II. For all z P n
(i) Eξ “ F̂pz, ξq ‰ “ Fpzq,
(ii) Eξ “ }F̂pz, ξq ´ Fpzq}2 ‰ ď σ2.
We proceed by presenting Algorithm 2 which is the stochastic variant of (CEG+). Interestingly, our analysis does not impose further assumptions on γk (may be selected constant), while it is only αk that must satisfy the classical conditions
ř8 k“1 αk “ 8, and ř8 k“1 α 2 k ă 8 to guarantee convergence.
Theorem 3.5. Suppose that Assumptions I and II hold, γk P pt´2ρu`, 1{Ls, and let αk P p0, 12 ` ρ γk q. The sequence pzkqkP generated by Algorithm 2 satisfies E “ }zk`1 ´ z‹}2 ‰ ď E “ }zk ´ z‹}2 ‰ ´ ηkE “ }Hz̄k ´ Hzk}2 ‰ ` 8γ2kα 2 kσ 2, (3.4) where ηk “ 2αk `
p 12 ` ρ γk q ´ αk
˘
and H “ id´ γkF.
Set constant stepsize γk “ γ P pt´2ρu`, 1{Ls and αk “ βkp 12 ` ρ γ q for some pβkqkP with βk P p0, 1q. Then the following holds
E “ }Hz̄k‹ ´ Hzk‹}2 ‰ ď 1 2
`
1 2 ` ρ γ
˘´2}z0 ´ z‹}2 ` 4γ2σ2 řm
k“0 β 2 k
řm k“0 βk
, (3.5)
where k‹ is chosen from t0, 1, . . . ,mu according to probability Prk‹ “ ks “ βkřm i“1 βk .
When γ ă 1L , Lemma A.3(ii) may be used to derive a similar inequality in terms of E “ }z̄k‹ ´ zk‹} ‰ .
Algorithm 2 (SEG+) Stochastic algorithm for problem (2.1)
Require z0 “ zinit P n, γk P ` t´2ρu`, 1{L ‰ , αk “ βkp 12 ` ρ γk q, βk ą 0 Repeat for k “ 0, 1, . . . until convergence 2.1: Sample ξk „ P and let Fk “ F̂pzk, ξkq 2.2: z̄k “ pid` γkAq´1pzk ´ γkFkq 2.3: Sample ξ̄k „ P and let F̄k “ F̂pz̄k, ξ̄kq 2.4: zk`1 “ zk ` αk ` pz̄k ´ zkq ´ γkpF̄k ´ Fkq ˘ Return zk`1
Next, we derive complexity bounds based on Theorem 3.5. Set βk “ ξ?m`1 for some constant ξ. Assume that m is large enough such that βk ă 1. By minimizing the left-hand-side in (3.5) we obtain ξ “ 1
2 ? 2σγ p 12 ` ρ γ q´1}z0 ´ z‹}. Therefore, the algorithm will reach E
“ }Hz̄k ´ Hzk} ‰ ď accuracy for some k P t0, 1, . . . ,mu after at most m “ r 8
4 σ2γ2p 12 ` ρ γ q2}z0 ´ z‹}2s iterations.
We remark that stochastic variant of (EG+) was also studied in (Diakonikolas et al., 2021, Thm. 4.4(i)) under a more restricted range of parameters ρ P p 1
8 ? 2L , 0s and γ “ 1 2 ? 2L .
4 Adaptively taking larger stepsizes using local curvature
As made apparent in the analysis in Section 3 (cf. Appendix B.1) the bound on the smallest weak MVI constant ρ in Assumption I(iii) may be replaced with the requirement that ρ ą ´γk{2 for all k P . Therefore, larger stepsizes γk would guarantee global convergence for an even larger class of problems. Since a global Lipschitz constant is inherently pessimistic the natural question then becomes how to locally choose a maximal stepsize without diverging.
The proposed scheme involves a backtracking linesearch that uses the local curvature for its initial guess. The reason being that this will immediately pass, close enough to the solution z‹, by argument of continuity. More precisely, we will set the initial guess to something slightly smaller than }JFpzkq}´1, where JFpzq denotes the Jacobian of F at z and } ¨ } is the spectral norm. Note that, despite the use of second order information, the scheme remains efficient since }JFpzq} only requires one eigenvalue computation performed through Jacobian-vector product (Pearlmutter, 1994).
Given an initial point z0 “ zinit and ν P p0, 1q, the final scheme which we denote (CurvatureEG+) proceeds for k “ 0, 1, . . . as follows:
1. Obtain γk and z̄k according to Algorithm 3 with γinit “ ν}JFpzkq}´1 2. Compute zk`1 according to steps 1.2 and 1.3 of Algorithm 1 (CurvatureEG+)
The above intuitive reasoning is made precise in the next lemma where it is shown that backtracking linesearch will terminate in finite time and that γinit will be immediately accepted asymptotically.
Lemma 4.1 (Lipschitz constant backtracking). Suppose that F : n Ñ n is a L-Lipschitz continuous operator. Consider the linesearch procedure in Algorithm 3. Then,
(i) The linesearch terminates in finite time with γ ě mintγinit, ντ{Lu;
(ii) Suppose that pzkqkP converges to z ‹ P zer T. If F is continuously differentiable, and γinit P
p0, ν}JFpzkq}´1q with ν P p0, 1q, then eventually the backtrack will never be invoked (γinit would be accepted).
Algorithm 3 Lipschitz constant backtracking
Initialize zk P n, τ P p0, 1q, ν P p0, 1q 3.1: Set initial guess γ “ γinit, and let Gγpzkq B ` id` γA ˘´1`zk ´ γFzk ˘ while γ}FpGγpzkqq ´ Fzk} ą ν}Gγpzkq ´ zk} do γÐ τγ Return γk “ γ and z̄k “ Gγpzkq
The convergence results for (CurvatureEG+) are deduced based of the above lemma and Theorem 3.1 and are provided in Corollary B.1 in Appendix B.2. We illustrate the behavior of (CurvatureEG+) in Fig. 1 and in Section 6.
5 Constructing toy examples
When Assumption I(iii) holds for negative ρ, limit cycles of the underlying operator Fz can emerge. We illustrate this with simple polynomial examples for which all the properties of interest can be computed in closed form. Definition 1 (PolarGame). A PolarGame denotes a two-player game whose associated operator F has limit cycles at }z}2 “ ci for all i P rks where ci ‰ 0.
This turns out to be particularly easy to construct in polar coordinates as the name suggests (see Appendix C.1). Apart from introducing arbitrary number of limit cycles it also gives us control over ρ. This is illustrated in the following instantiations capturing three important cases.
Example 3: (PolarGame). Consider Fz “ pψpx, yq ´ y, ψpy, xq ` xq where }z}8 ď 11{10 and ψpx, yq “ 116 axp´1` x 2 ` y2qp´9` 16x2 ` 16y2q. We have the following three cases:
(i) a “ 1 then ρ P p´ 1L ,´ 1 2L q (ii) a “ 3 4 then ρ P p´ 1 2L ,´ 1 3L q (iii) a “ 1 3 then ρ P p´ 1 8L ,´ 1 10L q
where L denotes the Lipschitz constant of F restricted to the constraint set. For all cases F exhibits limit cycles at }z} “ 1 and }z} “ 3{4. Proof is deferred to Appendix C.2.
Example 4: (minimax). In the particular case of constrained minimax problem we introduce the following polynomial game:
minimize |x|ď4{3 maximize |y|ď4{3 φpx, yq :“ xy` ψpxq ´ ψpyq, (GlobalForsaken)
where ψpzq “ 2z621 ´ z4 3 ` z2 3 . We provide proof of the following properties in Appendix C.3:
(i) There exists a repellant limit cycle and an attracting limit cycle of F. (ii) z‹ “ p0, 0q is a global Nash equilibrium for which Assumption I(iii) holds inside the constraint
with ρ ą ´1{2L, where L denotes the Lipschitz constant of F restricted to the constraint set.
6 Experiments
The algorithms considered in the experiments include the adaptive Algorithm 1, (CurvatureEG+), and constant stepsize methods that can be seen as instances of (CEG+) for various choices of γk and ᾱk. When γk “ 1{L and ᾱk “ 1 we recover a constrained variant of extragradient, which we denote CEG. When ᾱk “ 1{2 we denote the scheme CEG+, which is the direct generalization to the constraint setting of the (EG+) scheme studied in Diakonikolas et al. (2021, Thm. 3.2). Note that this choice of ᾱk restricts the problem class for which we otherwise can have guaranteed convergence according to Corollary 3.2. When ᾱk is chosen adaptively according to Algorithm 1 we refer to it as AdaptiveEG+. Finally, when γk is additionally chosen adaptively we use the name (CurvatureEG+).
In the stochastic setting, we consider Algorithm 2. When γk “ 1{k and αk “ 1, effectively both stepsizes diminish, and we recover a constrained variant of the popular stochastic extragradient scheme (see e.g. Hsieh et al. (2021, Algorithm 3)), which we refer to as SEG. When γk “ 1{L as suggested by Theorem 3.5, and only αk is decreasing, we refer to it as SEG+.
We test the algorithms on the constructed examples and confirm their convergence guarantees. Specifically, we apply the algorithms to the minimax problem in Example 4, the PolarGames in Example 3, and a worst case construction, Example 5, from the proof of the lower bound (cf. Appendix B.3). For Example 5 we choose the problem parameters such that ρ “ ´1{3L according to (B.15), and additionally add an `8-ball constraint to keep the iterates bounded. To simulate the stochastic setting we add Gaussian noise to calls of F. Results for the deterministic setting and stochastic setting can be found in Fig. 3 and Fig. 4 respectively.
7 Conclusion
This paper introduced an EG-type algorithm for a class of nonconvex-nonconcave minimax problems that satisfy the weak Minty variational inequality (MVI). The range of parameter in the weak MVI was extended compared to EG+ of Diakonikolas et al. (2021), and tightness of our results were demonstrated through construction of a counter example. In addition, EG+ (Diakonikolas et al., 2021), as well as the forward-backward-forward algorithm (Tseng, 2000) were all shown to be special cases of our scheme. Furthermore, (CurvatureEG+) was proposed that performs a backtracking linesearch on the extrapolation stepsize γk allowing for larger stepsizes and relaxes the condition ρ ą 12L to ρ ą ´γk{2 which is often a much weaker condition. More importantly, it is shown that asymptotically the linesearch always passes with γk “ ν}JFpzkq}´1 for any ν P p0, 1q, thus ratifying the name (CurvatureEG+). In the stochastic setting, unlike what is common in the literature, it was shown that it is only the second stepsize that must be diminishing. Future direction include exploring applications of the proposed algorithm in particular in the setting of GANs. It is also interesting to develope a variance reduced variant of the algorithm for finite sum minimax problems.
8 Acknowledgments and disclosure of funding
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement n° 725594 - time-data). This work was supported by the Swiss National Science Foundation (SNSF) under grant number 200021_205011. The work of the second and third author was supported by the Research Foundation Flanders (FWO) postdoctoral grant 12Y7622N and research projects G081222N, G0A0920N, G086518N, and G086318N; Research Council KU Leuven C1 project No. C14/18/068; Fonds de la Recherche Scientifique – FNRS and the Fonds Wetenschappelijk Onderzoek – Vlaanderen under EOS project no 30468160 (SeLMA); European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 953348. The work of Olivier Fercoq was supported by the Agence National de la Recherche grant ANR-20-CE40-0027, Optimal Primal-Dual Algorithms (APDO).
References
Waïss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games. In International Conference on Artificial Intelligence and Statistics, pp. 2863–2873. PMLR, 2020.
Heinz H. Bauschke and Patrick L. Combettes. Convex analysis and monotone operator theory in Hilbert spaces. CMS Books in Mathematics. Springer, 2017. ISBN 978-3-319-48310-8.
Heinz H Bauschke, Walaa M Moursi, and Xianfu Wang. Generalized monotone operators and their averaged resolvents. Mathematical Programming, pp. 1–20, 2020.
Michel Benaım and Morris W Hirsch. Mixed equilibria and dynamical systems arising from fictitious play in perturbed games. Games and Economic Behavior, 29(1-2):36–72, 1999.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 334–334, 1997.
Axel Böhm, Michael Sedlmayer, Ernö Robert Csetnek, and Radu Ioan Boţ. Two steps at a time– taking gan training in stride with tseng’s method. arXiv preprint arXiv:2006.09033, 2020.
Constantinos Daskalakis, Dylan J Foster, and Noah Golowich. Independent policy gradient methods for competitive reinforcement learning. arXiv preprint arXiv:2101.04233, 2021a.
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, 2021b.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges at the rate $O(k{̂1/4})$ on weakly convex functions. arXiv:1802.02988 [cs, math], February 2018.
Jelena Diakonikolas, Constantinos Daskalakis, and Michael Jordan. Efficient methods for structured nonconvex-nonconcave min-max optimization. In International Conference on Artificial Intelligence and Statistics, pp. 2746–2754. PMLR, 2021.
Francisco Facchinei and Jong-Shi Pang. Finite-dimensional variational inequalities and complementarity problems. Springer Science & Business Media, 2007.
Tanner Fiez and Lillian Ratliff. Gradient descent-ascent provably converges to strict local minmax equilibria with a finite timescale separation. arXiv preprint arXiv:2009.14820, 2020.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. arXiv preprint arXiv:1802.10551, 2018.
Pontus Giselsson. Nonlinear forward-backward splitting with projection correction. SIAM Journal on Optimization, 31(3):2199–2226, 2021. doi: 10.1137/20M1345062.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30, 2017.
M Hirsch and S Vavasis. Exponential lower bounds for finding Brouwer fixed points. In Proceedings of the 28th Symposium on Foundations of Computer Science, pp. 401–410, 1987.
Cars H Hommes and Marius I Ochea. Multiple equilibria and limit cycles in evolutionary games with logit dynamics. Games and Economic Behavior, 74(1):434–441, 2012.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization algorithms: Convergence to spurious non-critical sets. In International Conference on Machine Learning, pp. 4337–4348. PMLR, 2021.
Yu-Guan Hsieh, Franck Iutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. arXiv preprint arXiv:2003.10162, 2020.
Chi Jin, Praneeth Netrapalli, and Michael I. Jordan. What is local optimality in nonconvexnonconcave minimax optimization? arXiv:1902.00618 [cs, math, stat], June 2019.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747–756, 1976.
Puya Latafat and Panagiotis Patrinos. Asymmetric forward–backward–adjoint splitting for solving monotone inclusions involving three operators. Computational Optimization and Applications, 68(1):57–93, Sep 2017.
Sucheol Lee and Donghwan Kim. Fast extra gradient methods for smooth structured nonconvexnonconcave minimax problems. arXiv preprint arXiv:2106.02326, 2021a.
Sucheol Lee and Donghwan Kim. Semi-anchored multi-step gradient descent ascent method for structured nonconvex-nonconcave composite minimax problems. arXiv preprint arXiv:2105.15042, 2021b.
Eric V. Mazumdar, Michael I. Jordan, and S. Shankar Sastry. On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games. arXiv:1901.00838 [cs, math, stat], January 2019.
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. arXiv preprint arXiv:1807.02629, 2018a.
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. Cycles in adversarial regularized learning. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2703–2717. SIAM, 2018b.
George J Minty. Monotone (nonlinear) operators in hilbert space. Duke Mathematical Journal, 29 (3):341–346, 1962.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving a class of non-convex min-max games using iterative first order methods. arXiv preprint arXiv:1902.08297, 2019.
Christos H Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and system Sciences, 48(3):498–532, 1994.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147–160, 1994.
Boris T Polyak. Introduction to optimization. Optimization Software New York, 1987.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv:1810.02060 [cs, math], January 2019.
R. T. Rockafellar and R. J.-B. Wets. Variational analysis, volume 317. Springer Science & Business Media, 2009.
R Tyrrell Rockafellar. Monotone operators and the proximal point algorithm. SIAM journal on control and optimization, 14(5):877–898, 1976.
Ralph Tyrell Rockafellar. Convex analysis. Princeton University Press, 1970.
M. V. Solodov and P. Tseng. Modified projection-type methods for monotone variational inequalities. SIAM Journal on Control and Optimization, 34(5):1814–1830, 1996.
Mikhail V Solodov and Benar F Svaiter. A hybrid projection-proximal point algorithm. Journal of convex analysis, 6(1):59–70, 1999.
Chaobing Song, Zhengyuan Zhou, Yichao Zhou, Yong Jiang, and Yi Ma. Optimistic dual extrapolation for coherent non-monotone variational inequalities. arXiv preprint arXiv:2103.04410, 2021.
Gerald Teschl. Ordinary differential equations and dynamical systems, volume 140. American Mathematical Soc., 2012.
P. Tseng. A modified forward-backward splitting method for maximal monotone mappings. SIAM Journal on Control and Optimization, 38(2):431–446, 2000.
Junchi Yang, Negar Kiyavash, and Niao He. Global convergence and variance-reduced optimization for a class of nonconvex-nonconcave minimax problems. arXiv preprint arXiv:2002.09621, 2020.
Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Stephen Boyd, and Peter W Glynn. Stochastic mirror descent in variationally coherent optimization problems. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
A Preliminary definitions
Notationally we will use txu` B maxt0, xu throughout. We additionally recall some standard definitions and results and refer to Bauschke & Combettes (2017); Rockafellar (1970)) for further details.
An operator or set-valued mapping A : n Ñ d maps each point x P n to a subset Ax of d. We will use the notation Apxq and Ax interchangably. We denote the domain of A by
dom A B tx P n | Ax ‰ Hu, its graph by
gph A B tpx, yq P n ˆ d | y P Axu,
and the set of its zeros by zer A B tx P n | 0 P Axu. The inverse of A is defined through its graph: gph A´1 B tpy, xq | px, yq P gph Au. The resolvent of A is defined by JA B pid ` Aq´1, where id denotes the identity operator.
Definition A.1 ((co)monotonicity Bauschke et al. (2020)). An Operator A : n Ñ n is said to be ρ-monotone for some ρ P , if for all px, yq, px1, y1q P gph A
ρ}x´ x1}2 ď xx´ x1, y´ y1y, and it is said to be ρ-comonotone if for all px, yq, px1, y1q P gph A
ρ}y´ y1}2 ď xx´ x1, y´ y1y. The operator A is said to be maximally (co)monotone if its graph is not strictly contained in the graph of another (co)monotone operator.
We say that A is monotone if it is 0-monotone. When ρ ă 0, ρ-comonotonicity is also referred to as |ρ|-cohypomonotonicity. Definition A.2 (Lipschitz continuity and cocoercivity). LetD Ď n be a nonempty subset of n. A single-valued operator A : DÑ n is said to be L-Lipschitz continuous if for any x, x1 P D
}Ax´ Ax1} ď L}x´ x1}, and β-cocoercive if
β}Ax´ Ax1}2 ď xx´ x1, Ax´ Ax1y.
Moreover, A is said to be nonexpansive if it is 1-Lipschitz continuous, and firmly nonexpansive if it is 1-cocoercive.
The resolvent operator JA is firmly nonexpansive (with dom JA “ n) if and only if A is (maximally) monotone.
The following lemma plays an important role in our convergence analysis.
Lemma A.3. Let A : n Ñ n denote a single valued operator. Then,
(i) A is 1-Lipschitz if and only if T “ id´ A is 1{2-cocoercive.
(ii) If A is L-Lipschitz, then T “ id ´ ηA, η P p0, 1{Lq, is p1 ´ ηLq-monotone, and in particular }Tu´ Tv} ě p1´ ηLq}u´ v} for all u, v P n.
Proof. The first claim follows directly from (Bauschke & Combettes, 2017, Prop.4.11). That T is strongly monotone is a consequence of the Cauchy Schwarz inequality and Lipschitz continuity of A:
xTv´ Tu, v´ uy “ }v´ u}2 ´ ηxAv´ Au, v´ uy ě p1´ ηLq}v´ u}2. In turn, the last claim follows from the Cauchy-Schwarz inequality.
B Proofs and further results
B.1 Proofs of Section 3
Proof of Theorem 3.1. Let H “ id´ γkF. By Step 1.1 Hzk P z̄k ` γkAz̄k. Therefore, 1 γk pHzk ´ Hz̄kq P Az̄k ` Fz̄k (B.1) In what follows we will show that Algorithm 1 is equivalent to taking a forward-backward step followed by a correction step. Consider the updates
z̄k B pid` γkAq´1 ` zk ´ γkFzk ˘ , (B.2)
zk`1 “ p1´ λkqzk ` λkΠDkpzkq, where Dk B ! w | xHzk ´ Hz̄k, z̄k ´ wy ě δk γk }Hzk ´ Hz̄k}2 ) .
Note that xHz̄k ´ Hzk, z̄k ´ zky ` δk
γk }Hz̄k ´ Hzk}2 ě p 12 ` δk γk q}Hz̄k ´ Hzk}2 (B.3)
where in the inequality Lemma A.3(i) was used. Hence, by (B.3) the stepsize αk is positive and bounded away from zero. Moreover, if zk P Dk, then from (B.3) we may conclude that }Hz̄k´Hzk} ď 0 which implies that the generated sequence remains constant and z̄k P zer T (cf. (B.1)). The projection ontoDk for any v R Dk is given by
ΠDkpvq “ v` xz̄k ´ v,Hzk ´ Hz̄ky ´ δk γk }Hzk ´ Hz̄k}2
}Hzk ´ Hz̄k}2 pHzk ´ Hz̄kq
Moreover, (B.1) together with Assumption I(iii) at z̄k yields 1 γk xHzk ´ Hz̄k, z̄k ´ z‹y ě ρ γ2k }Hzk ´ Hz̄k}2 ě δk γ2k }Hzk ´ Hz̄k}2, (B.4) thus ensuring z‹ P S‹ Ď Dk. The projection ontoDk is then given byΠDkpzkq “ zk`αkpHz̄k´Hzkq, where αk is as in step 1.2.
Finally, since the projection ΠDk is firmly nonexpansive, it follows from (Bauschke & Combettes, 2017, Cor. 4.41) that the mapping p1´ λkqid` λkΠDk is λk{2-averaged. Consequently, we may conclude that pzkqkP is Fejér monotone relative to S‹ (Bauschke & Combettes, 2017, Prop. 4.35(iii)). That is for all z‹ P S‹
}zk`1 ´ z‹}2 ď }zk ´ z‹}2 ´ λkp2´ λkqα2k}Hz̄ k ´ Hzk}2.
(B.3) ď }zk ´ z‹}2 ´ εk γ2k }Hz̄k ´ Hzk}2, (B.5)
where εk B λkp2´λkqp γk2 `δkq 2. The convergence rate in (3.1) is obtained by telescoping (B.5). Since lim infkÑ8 εk ą 0, p 1γ2k }Hz̄ k ´ Hzk}2qkP converges to zero. Moreover, p}z
k ´ z‹}2qkP converges and the sequence pzkqkP is bounded. Since γk is bounded, and F and the resolvents pid`γkAq
´1 are Lipschitz continuous (cf. (Bauschke & Combettes, 2017, Cor. 23.9)), so is their composition. Hence, pz̄kqkP is also bounded. Let pz̄ kqkPK be a subsequence converging to some z̄ P n. Combined with the fact that p 1 γ2k }Hz̄k´Hzk}2qkP converges to zero, we may conclude from (B.1) along with (Bauschke & Combettes, 2017, Prop. 20.38) and Lipschitz continuity of F that z̄ P zer T . Finally, if in addition γ “ lim supkÑ8 γk ă 1{L, then p1´ γLq}z̄k ´ zk} ď }Hz̄k ´ Hzk} (invoke Lemma A.3(ii)). Therefore, p}z̄k ´ zk}qkP converges to zero, which in turn implies that a subsequence pz
kqkPK1 converges to a point z1 iff so does the subsequence pz̄kqkPK1 . Hence, pz
kqkPK also converges to z̄ P zer T . Consequently, if Assumption I(iii) holds at all of the zeros of T , i.e., if S‹ “ zer T , then the second claim follows by invoking (Bauschke & Combettes, 2017, Thm. 5.5).
Proof of Corollary 3.2 (Constant stepsize). The proof of convergence was already given prior to the statement of the corollary. It remains to derive (3.3). By Assumption I(iii) and owing to 1{2- cocoercivity of H (cf. Lemma A.3(i))
xzk ´ z‹,Hz̄k ´ Hzky “ xz̄k ´ z‹,Hz̄k ´ Hzky ` xzk ´ z̄k,Hz̄k ´ Hzky (B.4) ď ´ p 12 ` δk γk q}Hz̄k ´ Hzk}2. (B.6)
Therefore, provided that ᾱ ą 0 we have }zk`1 ´ z‹}2 “ }zk ´ z‹}2 ` ᾱ2}Hz̄k ´ Hzk}2 ` 2ᾱxzk ´ z‹,Hz̄k ´ Hzky
(B.6) ď }zk ´ z‹}2 ´ ᾱp2p 12 ` δ γ q ´ ᾱq}Hz̄k ´ Hzk}2.
Telescoping the above inequality yields the claimed inequality.
Proof of Theorem 3.5. Let wk “ F̂pzk, ξkq ´ Fpzkq, w̄k “ F̂pz̄k, ξ̄kq ´ Fpz̄kq denote the additive noise associated with the stochastic oracle access at zk and z̄k, respectively. Then, letting Ĥpzkq “ Hpzkq ´ γkwk, Ĥpz̄kq “ Hpz̄kq ´ γkw̄k, it holds that
}Ĥpz̄kq ´ Ĥpzkq}2 “ }γk ` wk ´ w̄k ˘ ` Hpz̄kq ´ Hpzkq}2
ď 2γ2k}w k ´ w̄k}2 ` 2}Hpz̄kq ´ Hpzkq}2 ď 4γ2k ` }wk} ` }w̄k}2 ˘
` 2}Hpz̄kq ´ Hpzkq}2, (B.7) where the Young inequality was used in both inequalities. Using the law of total expectation, for z‹ P zer T E “ xzk ´ z‹, Ĥpz̄kq ´ Ĥpzkqy ‰ “ E “ E “ xzk ´ z‹, Ĥpz̄kqy | F̄k ‰‰ ` E “ E “ xzk ´ z‹,´Ĥpzkqy | Fk ‰‰
Assumption II(i) “ E “ xzk ´ z‹,Hz̄k ´ Hzky ‰
(B.6) ď ´ p 12 ` ρ γk qE “ }Hz̄k ´ Hzk}2 ‰ . (B.8)
where Fk and F̄k represent the information available at zk and z̄k updates, repectively. It follows from the above two inequalities that
E “ }zk`1 ´ z‹}2 ‰ “ E “ }zk ´ z‹}2 ‰ ` α2kE “ }Ĥpz̄kq ´ Ĥpzkq}2 ‰
` 2αkE “ xzk ´ z‹, Ĥpz̄kq ´ Ĥpzkqy ‰
(B.8), (B.7), Assumption II(ii) ď E “ }zk ´ z‹}2 ‰ ´ 2αk ` 1 2 ` ρ γk ˘ E “ }Hz̄k ´ Hzk}2 ‰
` 2α2kE “ }Hz̄k ´ Hzk}2 ‰ ` 8γ2kα 2 kσ 2,
as claimed. Next, with constant stepsize γ and pαkqkP as prescribed in the lemma, ηk “ 2βkp1 ´ βkq ` 1 2 ` ρ γ ˘2 ě 2βk ` 1 2 ` ρ γ ˘2. Using this and summing (3.4) over k we obtain
2p 12 ` ρ γ q2
m ÿ k“0 βkE “ }Hz̄k ´ Hzk}2 ‰ ď Ek “ }z0 ´ z‹}2 ‰ ` 4σ2γp1` γqp 12 ` ρ γ q2 m ÿ k“0 β2k .
Dividing both sides by 2p 12 ` ρ γ q2 řm k“0 βk yields
1 řm
k“0 βk
m ÿ k“0 βkE “ }Hz̄k ´ Hzk}2 ‰ ď 1 2
`
1 2 ` ρ γ
˘´2}z0 ´ z‹}2 ` 2γp1` γqσ2 řm
k“0 β 2 k
řm k“0 βk
,
establishing the claimed inequality.
B.2 Convergence results and proofs of Section 4
The convergence results for (CurvatureEG+) are provided in the next corollary where ρ in Assumption I(iii) is allowed to take potentially larger values provided that ρ ą ´γk{2. Note that owing to the lower bound on γk (cf. Lemma 4.1(i)), the weak MVI assumption in the corollary is always satisfied if ρ P p´ντ{2L,8q, however, in practice γk may take larger values. Corollary B.1. Suppose that Assumptions I(i) and I(ii) hold, and consider the sequences pzkqkP , pz̄kqkP generated by (CurvatureEG+). Suppose that Assumption I(iii) holds for some ρ P satisfying γk ` 2ρ ą 0, and let δk P p´γk{2, ρs, λk P p0, 2q, lim infkÑ8 λkp2 ´ λkq ą 0, and lim infkÑ8pδk ` γk{2q ą 0. Then,
(i) The sequence p}z̄k ´ zk}2qkP vanishes;
(ii) pz̄kqkP , pz kqkP are bounded, and have the same limit points belonging to zer T;
(iii) if in addition S‹ “ zer T, then pzkqkP , pz̄kqkP both converge to some z‹ P zer T.
Moreover, if zk, z̄k Ñ z‹ P zer T (as is the case in B.1(iii)), and F is continuously differentiable, then eventually the backtrack will never be invoked.
Proof. Observe that in the proof of Theorem 3.1 1-Lipschitz continuity of γkF is only used at the generated points z̄k and zk (see (B.3)), and is thus ensured by the linesearch Algorithm 3. Therefore, it is easy to see that αk is positive and bounded away from zero provided that ρ ą ´γk{2 , see (B.3). Moreover, since γk}Fz̄k´Fzk} ď ν}z̄k´ zk}, arguing as in Lemma A.3(ii) we obtain }Hz̄k´Hzk} ě p1´ νq}z̄k ´ zk}. Hence, it follows from (B.5) that
}zk`1 ´ z‹}2 ď }zk ´ z‹}2 ´ εkp1´νq γ2k }z̄k ´ zk}2,
By telescoping the inequality and noting that γk is bounded, we obtain ř kP }z̄k ´ zk}2 ă 8, implying B.1(i). Noting this and arguing as in the last part of the proof of Theorem 3.1 establishes B.1(ii), B.1(iii). The last claim is the direct consequence of Lemma 4.1(ii).
Proof of Lemma 4.1 (Lipschitz constant backtracking). 4.1(i): Since F is L-Lipschitz continuous the linesearch would terminate in finite steps. Either γinit satisfies the condition, or else the backtrack procedure is invoked, which in turn implies the previous candidate γ{τ should have violated the condition leading the the claimed lower bound.
4.1(ii): Since the resolvent pid`γAq´1 and F are Lipschitz continous, so is their composition. Hence, Gγpzkq Ñ Gγpz‹q. Furthermore, by definition z‹ ´ γFz‹ P Gγpz‹q ` γApGγpz‹qq. Consequently, using monotonicity of A at Gγpz‹q and z‹, and that ´Fz‹ P Az‹ yields 0 ď xz‹ ´ γFz‹ ´Gγpz‹q ` Fz‹,Gγpz‹q ´ z‹y “ ´ }z‹´Gγpz‹q}2. Thus Gγpz‹q “ z‹. Using the fact that both pGγpzkqqkP and pzkqkP converges to z ‹ P zer T :
lim kÑ8 }FpGγpzkqq ´ Fzk} }Gγpzkq ´ zk} ď lim sup z,z1Ñz‹ }Fz1 ´ Fz} }z1 ´ z} “ lip Fpz ‹q “ }JFpz‹q},
where (Rockafellar & Wets, 2009, Thm. 9.7) was used. The claim follows from continuity of JF and the fact that pzkqkP converges to z ‹.
B.3 Proofs of Section 3.2
To prove the lower bound we introduce the following unconstrained bilinear minimax problem with an unstable critical point.
Example 5: Consider the following minimax problem:
minimize xPR maximize yPR f px, yq :“ axy` b 2 px2 ´ y2q, (B.9)
where b ă 0 and a ą 0.
Proof of Theorem 3.4. The associated operator of Example 5 can easily be computed, Fz “ pay` bx, by´ axq, (B.10)
where z “ px, yq. In this particular case, both L and ρ turn out to be constants. By simple calculation we have,
}JFpzq} “ a a2 ` b2, ρ “ b a2 ` b2
(B.11)
where } ¨ } is the spectral norm. Since the norm of the Jacobian is constant it equates the global Lipschitz constant, L “ }JFpzq}. By linearity of F, one step of (EG+) is conveniently also a linear operator. Specifically,
zk`1 “ Tzk with T :“
¨
˚
˝
p1´ᾱqa2`b ´ ´ᾱ ? a2`b2`ᾱb`b ¯
a2`b2 ´ aᾱ
´? a2`b2´2b ¯
a2`b2 aᾱ ´? a2`b2´2b ¯
a2`b2 p1´ᾱqa2`b
´ ´ᾱ ? a2`b2`ᾱb`b ¯
a2`b2
˛
‹ ‚ . (B.12)
We know that a linear dynamical system is globally asymptotically stable if and only if the spectral radius of the linear mapping is strictly less than 1.
Let λ1, λ2 be the eigenvalues of T . Then the spectral radius is the largest absolute value of the eigenvalues. For T this becomes,
max iPt1,2u |λi| “
d p2pᾱ´ 1qᾱ` 1qa2 ´ 2ᾱpᾱ` 1qb ` ? a2 ` b2 ´ b ˘ ` b2
a2 ` b2 . (B.13)
So we can ask what c in ρ “ ´ cL needs to be for the sequence pz kqkPN to converge. Solving for c in this equality with maxi |λi| ă 1, we obtain,
c ă 1´ ᾱ 2 , (B.14)
provided that we pick ? 1´ c2
c “ ´a b . (B.15)
Equation (B.15) provides a specification for Example 5. As long as (B.14) is satisfied, (EG+) is guaranteed to converge for γk “ 1{L. On the other hand, since (B.12) is a linear system, we simultaneously learn that picking c any larger would imply non-convergence through maxi |λi| ě 1 (given z0 ‰ 0). We can trivially embed problem (B.12) into a higher dimension to generalize the result. Noting that c “ ´ρL completes the proof.
We provide Mathematica code to verify each step of the above proof.1
C Toy examples
In the following appendix, L denotes the Lipschitz constant of F restricted to the constraint set and ρ is the parameter of the weak MVI (Assumption I(iii)) when restricted to the constraint set. This restriction of the definitions is warranted, since zk remains within the constraint set in all simulations, while z̄k is guaranteed to stay within by definition of Step 1.1 in Algorithm 1 (and likewise for all other considered method treating problem (2.1)).
All computer-assisted calculations can be found in the supplementary code.1
C.1 Constructing a PolarGame (Definition 1)
Recall Definition 1 which considers a vectorfield F : Rn Ñ Rn with limit cycles at r P tc1, ..., cku where ci ‰ 0 for all i P rks. Such a vectorfield can be constructed for n “ 2 by departing from the following dynamics in polar coordinates,
Br Bt “ ´a ¨ rptq
k ź i“1 prptq ` ciq ¨ prptq ´ ciq
Bθ Bt “ ´b ¨ rptq,
(C.1)
with a, b ‰ 0. Transforming this dynamics into cartesian coordinates yields the desired vectorfield, F, while subsequently integrating with respect to x and y yields the two potentials associated with the two players. Note that the roots t´ciuki“1 for the polynomial defining 9r are not strictly necessary for showing existence of limit cycles, but leads to a simpler form for Fz. We illustrate the construction in Fig. 5.
Proposition 1. Let Fz “ p 9x, 9yq be the evolution in cartesian coordinates of the associated vectorfield in polar coordinates defined by (C.1). Then the only stationary point of F is at the origin p0, 0q and there exists a limit cycle at r “ ci for all i P rks.
Proof. Let r “ a
x2 ` y2. It is easy to see from (C.1) that the only stationary point is at r “ 0. By construction, 9r is a polynomial with roots ci for all i P rks, so any trajectory starting on the circle defined by r “ ci remains in that set. However, 9θ is strictly nonzero. As a consequence Fz is nonzero, so r “ ci must define a limit cycle, which proofs the claim.
1The supplementary code can be found at https://github.com/LIONS-EPFL/weak-minty-code/.
C.2 Proof for properties of Example 3
The operator F : R2 Ñ R2 defined in Example 3 is obtained by constructing the associated dynamics in polar coordinates,
Br Bt “ ´a ¨ rptq ¨ prptq ` 1q ¨ prptq ´ 1q ¨ prptq ` 3{4q ¨ prptq ´ 3{4q Bθ Bt “ ´rptq.
(C.2)
This can easily be verified by a change of variables. From Proposition 1 it then follows, that there must exist a limit cycle at }z} “ 1 and }z} “ 3{4. To verify the conditions on ρ we compute the closed form solution to ρ and L in Mathematica:
(i) For a “ 1 we have ρ “ ´ 501761050977 and L “ ? 2538096 ? 704424929`70246989617 20000
(ii) For a “ 3{4 we have ρ “ ´ 60211216798825 and L “ ? 7614288 ? 6383574361`635022906553 80000
(iii) For a “ 1{3 we have ρ “ ´ 1505289439585 and L “ ? 2538096 ? 754424929`73446989617 60000
It can easily be verified that the stated conditions for ρ in Example 3 are met for the values above. This completes the proof.
We provide Mathematica code verifying the construction of F and the closed form solutions to L and ρ.
C.3 Proof for properties of Example 4
Under the definitions of ρ and L in Appendix C, we claim that the origin p0, 0q in (GlobalForsaken) is a global Nash equilibrium and satisfies Assumption I(iii) with ρ ą ´1{2L. To verify that p0, 0q is indeed a global Nash equilibrium we need to check that the solution cannot be unilaterally improved. In other words, the solution should coincide with px‹, y‹q where
x‹ “ arg min x φpx, 0q y‹ “ arg max y φp0, yq. (C.3)
We can easily verify this with Minimize in Mathematica, since the functions are polynomial for which a closed form solutions to the global optimization problem will be returned.
To find ρ for z‹ “ p0, 0q we solve the global minimization problem,
minimize z xFz, z´ z‹y }Fz}2 , (C.4)
for which a closed form solution can be found with Mathematica, which when numerically evaluated is approximately ´0.119732. We need to compute L to ensure ρ ą ´1{2L. In our case of convex constraints, C, we have that L “ supzPC }JFpzq} where } ¨ } denotes the spectral norm (Rockafellar & Wets, 2009, Thm. 9.2 and 9.7). Under our constraint }z}8 ď 4{3, this can similarly be computed in closed form, yielding L “ b 1 2 p9409 ? 59721901`74125591q{2835. So ´ 12L « ´0.165432 which satisfy the condition ρ ą ´ 1 2L . This completes the proof.
Proposition 2. Let F be the associated operator of φ in (GlobalForsaken) defined as Fz “ p∇xφpx, yq,´∇yφpx, yqq. Define the radius as r “ }z}. Then, Fz has a stable critical point at the origin p0, 0q, at least one attracting limit cycle in the region defined by a
3{2 ă r ă 2 and at least one repellant limit cycle within r ď a 3{2.
Proof. We follow a similar argument as in Hsieh et al. (2021, D.2). We can compute the associated operator F,
ˆ
9x 9y
˙
“
˜
4x5 7 ´ 4x3 3 ` 2x 3 ` y
´x` 4y 5 7 ´ 4y3 3 ` 2y 3
¸
. (C.5)
With a change of variables into polar coordinates pr, θq we get that r “ a x2 ` y2 evolves as,
9r “ ´ 1 42 r ` 9r4 cosp4θq ´ 14r2 cosp4θq ` 15r4 ´ 42r2 ` 28 ˘ . (C.6)
When r “ a 3{2 this reduces to 9r “ 3 cosp4θq`5 56 ? 6 and we observe that 9r ą 0 for any θ. Likewise for r “ 2, we have that 9r “ ´ 421 p22 cosp4θq`25qwhich implies 9r ă 0. Since there is no stationary point in the region S “ ! pr, θq : a 3{2 ă r ă 2 )
it then follows from the Poincaré-Bendixson theorem (Teschl, 2012, Thm. 7.16) that there must exist at least one attracting limit cycle in S. Further, it is easy to see that p0, 0q is a critical point and that it is stable by inspection of the Jacobian JFpzq. Since S is trapping, it follows from Poincaré–Hopf index theorem, that there must exist a repellant limit cycles in the region defined by r ă a 3{2. This completes the proof.
C.4 Proof of properties for (Hsieh et al., 2021, Example 5.2)
This section considers (Hsieh et al., 2021, Example 5.2) on the constraint domain D “ tz P n | }z}8 ď 3{2u. We show that the unique critical point z‹ does not satisfies the weak MVI for ρ ą ´1{2L even when restricted to the constraint set z P D. We restate the example with the additional constraint for convenience.
Example 6: (Hsieh et al., 2021, Example 5.2) minimize |x|ď3{2 maximize |y|ď3{2 φpx, yq :“ xpy´ 0.45q ` ψpxq ´ ψpyq, (Forsaken)
where ψpzq “ 14 z 2 ´ 12 z 4 ` 16 z 6.
By using Mathematica, we can obtain a closed form solution of the Lipschitz constant L of F restricted to the constraint set, which we find to be L “ 180 b 1 2 ` 1089 ? 801761` 993841 ˘
. Mathematica can solve approximately for the critical point, yielding z‹ “ p0.0780267, 0.411934q. To find ρ we want to globally minimize ρpzq :“ xFz,z´z
‹y }Fz}2 for z P D. Mathematica finds the candi-
date z1 “ p´1.01236,´0.104749q for which ρpz1q “ ´0.477761. So ρ must be at least this small, i.e. ρ ă ´0.477761. Since ´1{2L « ´0.04, this implies that ρ ă ´1{2L. See Forsaken.nb for Mathematica-assisted computations.
This rules out convergence guarantees for both (CEG+) and AdaptiveEG+ (Algorithm 1), which is supported by the simulation in Figure 8. However, as observed, (CurvatureEG+) converges in the simulations.

title: Escaping limit cycles: Global convergence for con- strained nonconvex-nonconcave minimax problems