A Slowikowska

I Nasiroglu

K Gozdziewski
email: k.gozdziewski@umk.pl

K Krzeszowski

M Zejmo

P Irawati
email: puji.irawati@gmail.com

D Buckley

D Dimitrov

H Er

Janusz Gil

THE HU Aqr O-C DIAGRAM TREND CHANGE: ARE THERE STILL ANY CIRCUMBINARY PLANETS?

Keywords:

) by approximately three years. Our recent observations indicate a sudden reversing of the previously, long-term decaying (O-C), that took place between May and August 2016. Since none of the previous eclipse ephemeris hold, it reinforces still an unclear hypothesis that the (O-C) variability has not the third-body origin. Moreover, the unusual change of the (O-C) diagram provides a convincing argument for frequent, regular and continuous observations of the HU Aqr -like binaries.

IntroducCon

More and more exoplanets around compact binary systems are discovered. Planets orbiting low-mass circumbinary objects are called as the circumbinary planets (CBPs), while their orbits are called "P-type" orbits. The era of the Kepler satellite brought, for example, the discovery of the CBP transiting across the close binary system Kepler-16 AB (Doyle et al. 2011), as well as the longest-period transiting CBP Kepler-1647 with the orbital period of three years (Kostov et al. 2016). Because the proper=es of CBPs are different than properties of planets orbiting single stars (Lee et al. 2009), finding the answer to fundamental questions like, how such planets form and evolve, is very timely.

Even before the Kepler satellite era, timing observations of eclipsing binaries provided the evidence a third body orbi=ng close binary systems, for example, CM Dra (Deeg et al.2008) and HW Vir (Lee et al. 2009). The precision =ming of the eclipse minima exhibits devia=ons between the predicted ephemeris (usually, linear one), and the observed eclipse moments, i.e. abbreviated as observations versus calculations (O-C) hereafter. The times of the eclipses minima appear earlier or later according to the linear or quadratic ephemeris and can result from the gravitational tug of an additional body or bodies in the system. These, sometimes quasi-periodic, variations of the O-C could be interpreted in accord with the Light Travel Time model (aka Rømer effect). This method that relies on long-term monitoring of eclipsing binaries is the most sensitive to massive objects on long-period orbits. Fortunately, rapidly developing observational techniques, as well as hardware development, allow measuring the times of the minima with increasing accuracy. Based on the O-C variations analysis, planets around cataclysmic variables (CVs, e.g. HU Aqr, Gozdziewski et al. 2012Gozdziewski et al. , 2015) ) and post-common envelope binaries (PCEBs), e.g., NSVS 14256825, Nasiroglu et al. (2017), were proposed.

HU Aqr is a close binary system of AM Her type, consis=ng of a white dwarf and M4 dwarf. The total mass of the binary is 0.98 M☉ (Schwope et al. 2011), while its secondary mass is 0.18 M☉. A long-term stable system of three planets hosted by HU Aqr, with the middle one being on a retrograde orbit, was recently proposed by Gozdziewski et al. (2015). To verify this hypothesis we present 33 new mid-eclipse =mes of HU Aqr obtained aJer July 20 th , 2014 (see Tab. A1 of Gozdziewski et al. 2015 or the VizieR Online Data Catalogue: HU Aqr planetary system mid-egress moments). New observations extend the observing time span by almost three years. The most recent light curve was acquired on May 30 th , 2017. Altogether, the new and archive data span over 24 years. We aim to verify the previous ephemeris over the extended dataset and, if possible, give better constraints of proposed CBPs. This paper is structured as follows. In Sec=on 2, we present the observa=ons, data reduc=on and the sigmoid fit used to determine the mid-egress =mes. Sec=on 3 shows the procedure applied to examine the period variations, while the results are gathered in Sec=on 4. In Sec=ons 5 we discuss and conclude our findings, respectively.

ObservaCons

In the =me span from 2014 to 2017, we performed observa=ons with three two meter class telescopes, i.e. with the 2-m telescope Ritchey-Chrétien-Coudé reflector at the National Astronomical Observatory in Rozhen (NAO, Bulgaria) equipped with the Princeton Instruments VersArray (NAO-PIVA), with the 2-m Liverpool Telescope at the Observatorio del Roque de Los Muchachos on the Canary island of La Palma (Spain) equipped with the RISE camera [START_REF] Steele | Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series[END_REF], LT-RISE) and at the 2.4-m Thai National Telescope (TNT) at the Thai National Observatory (TNO, Thailand) equipped with the ULTRASPEC instrument (Dhillon et al. 2014, TNT-USPEC). Additionally, we performed observations of HU Aqr with three smaller telescopes in Turkey. They are as follows: Ritchey-Chré=en type 1.5-m (TUG RTT150) and 1-m (TUG T100) telescopes at the TUBITAK Na=onal Observatory (TUG) equipped with Andor DW436 and SI1100 CCD cameras, respec=vely. The third Turkish telescope used by us is the 0.6-m telescope at the Adiyaman University Observatory (ADYU60) equipped with the Andor iKon-M934 camera (Nasiroglu et al. 2017). A detailed descrip=on of the telescopes, CCD camera, CCD data analysis, as well as the time service (=me accuracy), can be found in the paragraphs 2.2 and 2.3 of the Gozdziewski et al. (2015).

As an example, we show data taken with the TNT-USPEC on November 18 th , 2016. The equa=on gives the best-fitting sigmoid model (see Sec. 2.3 of Gozdziewski et al. 2015 for detailed descrip=on) to the egress of HU Aqr eclipses

I ( t )= a 1 + a 2 -a 1 1 . 0-e (t 0 -t ) / Δ t (1)
is shown in Fig. 1 as a red solid line. In this case, the exposure =me of single frame was 2.16 seconds.

The sigmoid fit to all data (i.e. mid-egress parts of the light curves) was carried out using the Markov Chain Monte Carlo (MCMC) sampling of the model parameter space. More details about the MCMC and its software applications can be found in Foreman-Mackey et al. ( 2012). The triangle sigmoid fit parameter correla=ons and distribu=ons of the data shown in Fig. 1 are presented in Fig. 2.

The ephemeris model

Recently, in Gozdziewski et al. (2012), Marsh et al. (2014); Gozdziewski et al. (2015) an updated and corrected kinema=c (Keplerian) formula=on of the LTT effect [START_REF] Irwin | [END_REF]) for mul=ple companions is used. The binary period is shorter than the potential third body orbital period by a factor of more than ~10 5 . Therefore the binary system is approximated as a point mass. The eclipse mid-egress times are expressed w.r.t. Jacobi coordinates (Gozdziewski et al. 2012) of the origin at the centre of mass (CM) of the total binary mass (0.98 M⊙, Schwope et al.2011).

The general model accounting for the presence of planetary companions is given by equation:

2 bin 0 ephem L LP t (L) T β + + = , ( 2
)
where Tephem(L) is the time of predicted mid-egress at eclipse cycle L, t0 is the epoch, and β is the derivative of the orbital period Pbin, in accord with [START_REF] Hilditch | An Introduc=on to Close Binary Stars[END_REF]. It has the more general form of Eq. 2 where Kp, ep, wp are the semi-amplitude of the LTT signal, eccentricity, and argument of the pericenter, respectively for body p. Its orbital period Pp and the pericenter passage Tp are introduced indirectly through the eccentric anomaly Ep(t). In such way we obtained the N-body initial condition of the system with mutually interacting planets. Obtained O-C diagram (Fig. 3) exhibits a curious change of the eclipse =ming. We used our new as well as archive data (see Tab. A1 of Gozdziewski et al. 2015) to verify the previously proposed models of two and three planets orbiting HU Aqr. We found out that new data set spanning over more than 24 years do not match any of the previous CBPs predictions, including the most exotic model of three planets, with the middle one being in the retrograde orbit (Gozdziewski 2015).

∑ + + = p p L t )) ( ( LP t (L) T bin 0 ephem ζ , ( 3

Discussion and Conclusions

In case of the linear ephemeris, the O-C varia=ons are on the level of 220 seconds (from -160 s to +60 s) over more than 24 years, while in case of quadra=c ephemeris it is on the level of 150 seconds (from +60 s to -85 s). The O-C trend shows sudden change between May 5th, 2016 and August 4th, 2016. The O-C amplitude is a critical parameter to estimate the energy required for the Applegate mechanism (Applegate 1992) or more complex Lanza models (e.g., Lanza et al. 1998;Lanza & Rodono, 2004). Recently, [START_REF] Völschow | [END_REF] showed that the O-C variations observed in the HU Aqr system could not be explained with the Applegate (magnetic) cycles and its variants. However, this problem requires further analysis. We detected the unusual behaviour of the O-C. Still, an unexplained origin of the variability implies that there is a constant need to monitor HU Aqr. The O-C trend continues and is hardly predictable. All our previous predictions based on the third body hypothesis failed, as indicated by the new set of data. It reinforces the alternative interpretation of the O-C variations observed in this system rather than the presence of CBPs.

At the moment we do not propose other explanation. More extensive observations are necessary to follow the O-C behaviour. We have evidence that in the HW Vir system case, we might face a very similar problem. The O-C variations most likely are not caused by the planetary system because of its strong degeneracy, but they may be of another origin.

OPTICON program XOL15A36 (proposal OL15A36). We thank the team of TUBITAK National Observatory (TUG) for par=al support in using T100 and RTT150 telescopes with project numbers 14BT100-631 and 17ARTT150-1132 respec=vely. We also wish to thank Adiyaman University Observatory (Turkey) team. K.G. thanks the staff of the Poznan Supercomputer and Network Centre (PCSS) for the support and computa=onal resources (grant No 313).

Fig. 1 .

 1 Fig. 1. HU Aqr light curve zoomed around the mid-egress time together with the sigmoid fit (red solid line) given by the Eq. 1. ObservaCons were performed on November 18 th , 2016 at the Thai NaConal Observatory (TNT-USPEC). The single frame exposure Cme was 2.16 s. Each point (black filled circle) corresponds to a single exposure.

Fig. 2 .

 2 Fig. 2. The triangle sigmoid fit parameter correlaCons and distribuCon plots for the data presented in Fig. 1.

Fig. 3 .

 3 Fig. 3. Upper panel: the O-C diagram of the mid-egress times of HU Aqr . The blue and red filled circles are for the linear and quadratic (additionally plotted as yellow curve) ephemeris, respectively. Labels are for the fitted parameters with the uncertainties at the last significant digit given with a digit in parenthesis. The light-grey shaded region is for the data presented in Gozdziewski et al. (2015), while the dark-shaded region indicates the Cme span of new data (Tab. 1). Lower panel: the zoom of the O-C diagram for the eclipse cycles between 35000 and 50000. The dip of the O-C trend in the case of quadratic ephemeris is clearly visible. It happened between May and August 2016.

Table 1 . New HU Aqr BJD mid-egress Cmes on the basis of light curves collected with the 2-m telescope at the Bulgarian National Astronomical Observatory (NAO-PIVA), the 2-m Liverpool Telescope (LTRISE), the 2.4-meter Thai National Telescope (TNT-USPEC), as well as with three Turkish telescopes, the TUG 1.5-m (TUGRTT150), the TUG 1-m (TUGT100) and the 0.6-m Adiyaman University Observatory (ADYU60). Archival data are gathered in Tab. A1 of Gozdziewski et al. (2015).

 1

	Cycle L	BJD [TDB]	Error (d)	Instrument	Cycle L	BJD [TDB]	Error (d)	Instrument
	92691	2457150.3879850 0.0000013 TNT-USPEC	97645	2457580.4954959	0.0000022	TUGT100
	93107	2457186.5051720 0.0000014 NAO-PIVA	98208	2457629.3753397	0.0000029	TUGT100
	93141	2457189.4571099 0.0000725 TUGT100	98219	2457630.3303643	0.0000029	TUGT100
	93153	2457190.4988735 0.0000110 TUGT100	98221	2457630.5039851	0.0000076	TUGT100
	93408	2457212.6381020 0.0000016 LT-RISE	98554	2457659.4151565	0.0000044	TUGT100
	93546	2457224.6192856 0.0000016 LT-RISE	98575	2457661.2383909	0.0000012	NAO-PIVA
	93626	2457231.5649065 0.0000016 LT-RISE	98576	2457661.3252154	0.0000007	NAO-PIVA
	93808	2457247.3661694 0.0000330 TUGT100	98610	2457664.2770615	0.0000105	ADYU60
	93809	2457247.4529852 0.0000300 TUGT100	98886	2457688.2395041	0.0000066	TUGT100
	94544	2457311.2659250 0.0000044 NAO-PIVA	98887	2457688.3263200	0.0000059	TUGT100
	94600	2457316.1278293 0.0000006 TNT-USPEC	98978	2457696.2269655	0.0000047	TUGT100
	94831	2457336.1833143 0.0000054 NAO-PIVA	98979	2457696.3137833	0.0000036	TUGT100
	94898	2457342.0002559 0.0000008 TNT-USPEC	99148	2457710.9864657	0.0000011	TNT-USPEC
	94899	2457342.0870782 0.0000024 TNT-USPEC	99149	2457711.0732855	0.0000009	TNT-USPEC
	94910	2457343.0420999 0.0000012 TNT-USPEC	99243	2457719.2343737	0.0000037	TUGT100
	97633	2457579.4536617 0.0000039 TUGT100	101366	2457903.5539607	0.0000020	TUGRTT150
	97644	2457580.4086824 0.0000082 TUGT100

Acknowledgements

This work has been supported by Polish National Science Centre grant DEC-2011/03/D/ST9/00656 (AS, KK, MZ). This work has been supported by The Scientific and Technological Research Council of Turkey (TUBITAK), through project number 114F460 (IN, AS, HE). The Liverpool Telescope is operated on the island of La Palma by Liverpool John Moores University in the Spanish Observatorio del Roque de Los Muchachos of the Instituto de Astrofisica de Canarias with financial support from the UK Science and Technology Facilities Council. LT-RISE data were taken within the


Yu-Guan Hsieh
email: yu-guan.hsieh@ens.fr

Franck Iutzeler
email: franck.iutzeler@univ-grenoble-alpes.fr

Jérôme Malick
email: jerome.malick@univ-grenoble-alpes.fr

Panayotis Mertikopoulos
email: panayotis.mertikopoulos@imag.fr

On the Convergence of Single-Call Stochastic Extra-Gradient Methods

Variational inequalities have recently attracted considerable interest in machine learning as a flexible paradigm for models that go beyond ordinary loss function minimization (such as generative adversarial networks and related deep learning systems). In this setting, the optimal O(1/t) convergence rate for solving smooth monotone variational inequalities is achieved by the Extra-Gradient (EG) algorithm and its variants. Aiming to alleviate the cost of an extra gradient step per iteration (which can become quite substantial in deep learning applications), several algorithms have been proposed as surrogates to Extra-Gradient with a single oracle call per iteration. In this paper, we develop a synthetic view of such algorithms, and we complement the existing literature by showing that they retain a O(1/t) ergodic convergence rate in smooth, deterministic problems. Subsequently, beyond the monotone deterministic case, we also show that the last iterate of single-call, stochastic extra-gradient methods still enjoys a O(1/t) local convergence rate to solutions of non-monotone variational inequalities that satisfy a second-order sufficient condition.

Introduction

Deep learning is arguably the fastest-growing field in artificial intelligence: its applications range from image recognition and natural language processing to medical anomaly detection, drug discovery, and most fields where computers are required to make sense of massive amounts of data. In turn, this has spearheaded a prolific research thrust in optimization theory with the twofold aim of demystifying the successes of deep learning models and of providing novel methods to overcome their failures.

Introduced by Goodfellow et al. [START_REF] Goodfellow | Generative adversarial nets[END_REF], generative adversarial networks (GANs) have become the youngest torchbearers of the deep learning revolution and have occupied the forefront of this drive in more ways than one. First, the adversarial training of deep neural nets has given rise to new challenges regarding the efficient allocation of parallelizable resources, the compatibility of the chosen architectures, etc. Second, the loss landscape in GANs is no longer that of a minimization problem but that of a zero-sum, min-max game -or, more generally, a variational inequality (VI).

Variational inequalities are a flexible and widely studied framework in optimization which, among others, incorporates minimization, saddle-point, Nash equilibrium, and fixed point problems. As such, there is an extensive literature devoted to solving variational inequalities in different contexts; for an introduction, see [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF][START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF] and references therein. In particular, in the setting of monotone variational inequalities with Lipschitz continuous operators, it is well known that the optimal rate of convergence is O(1/t), and that this rate is achieved by the Extra-Gradient (EG) algorithm of Korpelevich [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF] and its Bregman variant, the Mirror-Prox (MP) algorithm of Nemirovski [START_REF] Nemirovski | Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF]. 1These algorithms require two projections and two oracle calls per iteration, so they are more costly than standard Forward-Backward / descent methods. As a result, there are two complementary strands of literature aiming to reduce one (or both) of these cost multipliers -that is, the number of projections and/or the number of oracle calls per iteration. The first class contains algorithms like the Forward-Backward-Forward (FBF) method of Tseng [START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF], while the second focuses on gradient extrapolation mechanisms like Popov's modified Arrow-Hurwicz algorithm [START_REF] Popov | A modification of the Arrow-Hurwicz method for search of saddle points[END_REF].

In deep learning, the latter direction has attracted considerably more interest than the former. The main reason for this is that neural net training often does not involve constraints (and, when it does, they are relatively cheap to handle). On the other hand, gradient calculations can become very costly, so a decrease in the number of oracle calls could offer significant practical benefits. In view of this, our aim in this paper is (i) to develop a synthetic approach to methods that retain the anticipatory properties of the Extra-Gradient algorithm while making a single oracle call per iteration; and (ii) to derive quantitative convergence results for such single-call extra-gradient (1-EG) algorithms.

Our contributions. Our first contribution complements the existing literature (reviewed below and in Section 3) by showing that the class of 1-EG algorithms under study attains the optimal O(1/t) convergence rate of the two-call method in deterministic variational inequalities with a monotone, Lipschitz continuous operator. Subsequently, we show that this rate is also achieved in stochastic variational inequalities with strongly monotone operators provided that the optimizer has access to an oracle with bounded variance (but not necessarily bounded second moments).

Importantly, this stochastic result concerns both the method's "ergodic average" (a weighted average of the sequence of points generated by the algorithm) as well as its "last iterate" (the last generated point). The reason for this dual focus is that averaging can be very useful in convex/monotone landscapes, but it is not as beneficial in non-monotone problems (where Jensen's inequality does not apply). On that account, last-iterate convergence results comprise an essential stepping stone for venturing beyond monotone problems.

Armed with these encouraging results, we then focus on non-monotone problems and show that, with high probability, the method's last iterate exhibits a O(1/t) local convergence rate to solutions of non-monotone variational inequalities that satisfy a second-order sufficient condition. To the best of our knowledge, this is the first convergence rate guarantee of this type for stochastic, non-monotone variational inequalities.

Related work.

The prominence of Extra-Gradient/Mirror-Prox methods in solving variational inequalities and saddle-point problems has given rise to a vast corpus of literature which we cannot hope to do justice here. Especially in the context of adversarial networks, there has been a flurry of recent activity relating variants of the Extra-Gradient algorithm to GAN training, see e.g., [START_REF] Chavdarova | Reducing noise in GAN training with variance reduced extragradient[END_REF][START_REF] Daskalakis | Training GANs with optimism[END_REF][START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF][START_REF] Gidel | Negative momentum for improved game dynamics[END_REF][START_REF] Liang | Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks[END_REF][START_REF] Mertikopoulos | Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile[END_REF][START_REF] Yadav | Stabilizing adversarial nets with prediction methods[END_REF] and references therein. For concreteness, we focus here on algorithms with a single-call structure and refer the reader to Sections 3-5 for additional details.

The first variant of Extra-Gradient with a single oracle call per iteration dates back to Popov [START_REF] Popov | A modification of the Arrow-Hurwicz method for search of saddle points[END_REF]. This algorithm was subsequently studied by, among others, Chiang et al. [START_REF] Chiang | Online optimization with gradual variations[END_REF], Rakhlin and Sridharan [START_REF] Rakhlin | Online learning with predictable sequences[END_REF][START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF] and Gidel et al. [START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF]; see also [START_REF] Cui | On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems[END_REF][START_REF] Malitsky | Projected reflected gradient methods for monotone variational inequalities[END_REF] for a "reflected" variant, [START_REF] Daskalakis | Training GANs with optimism[END_REF][START_REF] Mokhtari | Convergence rate of O(1/k) for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point problems[END_REF][START_REF] Mokhtari | A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach[END_REF][START_REF] Peng | Training GANs with centripetal acceleration[END_REF] for an "optimistic" one, and Section 3 for a discussion of the differences between these variants. In the context of deterministic, strongly monotone variational inequalities with Lipschitz continuous operators, the last iterate of the method was shown to exhibit a geometric convergence rate [START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF][START_REF] Malitsky | Projected reflected gradient methods for monotone variational inequalities[END_REF][START_REF] Mokhtari | A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach[END_REF][START_REF] Tseng | On linear convergence of iterative methods for the variational inequality problem[END_REF]; similar geometric convergence results also extend to bilinear saddle-point problems [START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF][START_REF] Peng | Training GANs with centripetal acceleration[END_REF][START_REF] Tseng | On linear convergence of iterative methods for the variational inequality problem[END_REF], even though the operator involved is not strongly monotone. In turn, this implies the convergence of the method's ergodic average, but at a O(1/t) rate (because of the hysteresis of the average). In view of this, the fact that 1-EG methods retain the optimal O(1/t) convergence rate in deterministic variational inequalities without strong monotonicity assumptions closes an important gap in the literature. 2At the local level, the geometric convergence results discussed above echo a surge of interest in local convergence guarantees of optimization algorithms applied to games and saddle-point problems, see e.g., [START_REF] Adolphs | Local saddle point optimization: a curvature exploitation approach[END_REF][START_REF] Balduzzi | The mechanics of n-player differentiable games[END_REF][START_REF] Daskalakis | The limit points of (optimistic) gradient descent in min-max optimization[END_REF][START_REF] Liang | Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks[END_REF] and references therein. In more detail, Liang and Stokes [START_REF] Liang | Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks[END_REF] proved local geometric convergence for several algorithms in possibly non-monotone saddle-point problems under a local smoothness condition. In a similar vein, Daskalakis and Panageas [START_REF] Daskalakis | The limit points of (optimistic) gradient descent in min-max optimization[END_REF] analyzed the limit points of (optimistic) gradient descent, and showed that local saddle points are stable stationary points; subsequently, Adolphs et al. [START_REF] Adolphs | Local saddle point optimization: a curvature exploitation approach[END_REF] and Mazumdar et al. [START_REF] Mazumdar | On finding local nash equilibria (and only local nash equilibria) in zero-sum games[END_REF] proposed a class of algorithms that eliminate stationary points which are not local Nash equilibria.

Geometric convergence results of this type are inherently deterministic because they rely on an associated resolvent operator being firmly nonexpansive -or, equivalently, rely on the use of the center manifold theorem. In a stochastic setting, these techniques are no longer applicable because the contraction property cannot be maintained in the presence of noise; in fact, unless the problem at hand is amenable to variance reduction -e.g., as in [START_REF] Boţ | Forward-backwardforward methods with variance reduction for stochastic variational inequalities[END_REF][START_REF] Chavdarova | Reducing noise in GAN training with variance reduced extragradient[END_REF][START_REF] Iusem | Extragradient method with variance reduction for stochastic variational inequalities[END_REF]] -geometric convergence is not possible if the noise process is even weakly isotropic. Instead, for monotone problems, Cui and Shanbhag [START_REF] Cui | On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems[END_REF] and Gidel et al. [START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF] showed that the ergodic average of the method attains a O(1/ √ t) convergence rate. Our global convergence results for stochastic variational inequalities improve this rate to O(1/t) in strongly monotone variational inequalities for both the method's ergodic average and its last iterate. In the same light, our local O(1/t) convergence results for non-monotone variational inequalities provide a key extension of local, deterministic convergence results to a fully stochastic setting, all the while retaining the fastest convergence rate for monotone variational inequalities.

For convenience, our contributions relative to the state of the art are summarized in Table 1.

Problem setup and blanket assumptions

Variational inequalities. We begin by presenting the basic variational inequality framework that we will consider throughout the sequel. To that end, let X be a nonempty closed convex subset of R d , and let V : R d → R d be a single-valued operator on R d . In its most general form, the variational inequality (VI) problem associated to V and X can be stated as:

Find x ∈ X such that V (x ), x -x ≥ 0 for all x ∈ X . (VI)
To provide some intuition about (VI), we discuss two important examples below:

Example 1 (Loss minimization). Suppose that V = ∇f for some smooth loss function f on X = R d . Then, x ∈ X is a solution to (VI) if and only if ∇f (x ) = 0, i.e., if and only if x is a critical point of f . Of course, if f is convex, any such solution is a global minimizer.

Example 2 (Min-max optimization). Suppose that X decomposes as X = Θ × Φ with Θ = R d1 , Φ = R d2 , and assume V = (∇ θ L, -∇ φ L) for some smooth function L(θ, φ), θ ∈ Θ, φ ∈ Φ. As in Example 1 above, the solutions to (VI) correspond to the critical points of L; if, in addition, L is convex-concave, any solution x = (θ , φ ) of (VI) is a global saddle-point, i.e., L(θ , φ) ≤ L(θ , φ ) ≤ L(θ, φ ) for all θ ∈ Θ and all φ ∈ Φ.

Given the original formulation of GANs as (stochastic) saddle-point problems [START_REF] Goodfellow | Generative adversarial nets[END_REF], this observation has been at the core of a vigorous literature at the interface between optimization, game theory, and deep learning, see e.g., [START_REF] Chavdarova | Reducing noise in GAN training with variance reduced extragradient[END_REF][START_REF] Daskalakis | Training GANs with optimism[END_REF][START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF][START_REF] Liang | Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks[END_REF][START_REF] Mertikopoulos | Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile[END_REF][START_REF] Peng | Training GANs with centripetal acceleration[END_REF][START_REF] Yadav | Stabilizing adversarial nets with prediction methods[END_REF] and references therein.

The operator analogue of convexity for a function is monotonicity, i.e.,

V (x ) -V (x), x -x ≥ 0 for all x, x ∈ R d .
Specifically, when V = ∇f for some sufficiently smooth function f , this condition is equivalent to f being convex [START_REF] Bauschke | Convex Analysis and Monotone Operator Theory in Hilbert Spaces[END_REF]. In this case, following Nesterov [START_REF] Nesterov | Dual extrapolation its applications to solving variational inequalities and related problems[END_REF][START_REF] Nesterov | Primal-dual subgradient methods for convex problems[END_REF] and Juditsky et al. [START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF], the quality of a candidate solution x ∈ X can be assessed via the so-called error (or merit) function

Err(x) = sup x∈X V (x), x -x
and/or its restricted variant

Err R (x) = max x∈X R V (x), x -x ,
where X R ≡ X ∩ B R (0) = {x ∈ X : x ≤ R} denotes the "restricted domain" of the problem.

More precisely, we have the following basic result. Lemma 1 [START_REF] Nesterov | Dual extrapolation its applications to solving variational inequalities and related problems[END_REF]. Assume V is monotone. If x is a solution of (VI), we have Err(x ) = 0 and Err R (x ) = 0 for all sufficiently large R. Conversely, if Err R (x) = 0 for large enough R > 0 and some x ∈ X R , then x is a solution of (VI).

In light of this result, Err and Err R will be among our principal measures of convergence in the sequel.

Blanket assumptions. With all this in hand, we present below the main assumptions that will underlie the bulk of the analysis to follow. Assumption 1. The solution set X of (VI) is nonempty. Assumption 2. The operator V is β-Lipschitz continuous, i.e.,

V (x ) -V (x) ≤ β x -x for all x, x ∈ R d .
Assumption 3. The operator V is monotone.

In some cases, we will also strengthen Assumption 3 to: Assumption 3(s). The operator V is α-strongly monotone, i.e.,

V (x ) -V (x), x -x ≥ α x -x 2 for some α > 0 and all x, x ∈ R d .
Throughout our paper, we will be interested in sequences of points X t ∈ X generated by algorithms that can access the operator V via a stochastic oracle [START_REF] Nesterov | Introductory Lectures on Convex Optimization: A Basic Course[END_REF]. 3 Formally, this is a black-box mechanism which, when called at X t ∈ X , returns the estimate

V t = V (X t ) + Z t , (1)
where Z t ∈ R d is an additive noise variable satisfying the following hypotheses:

a) Zero-mean: E[Z t | F t ] = 0. (2a) b) Finite variance: E[ Z t 2 | F t ] ≤ σ 2 . ( 2b
)
In the above, F t denotes the history (natural filtration) of X t , so X t is adapted to F t by definition; on the other hand, since the t-th instance of Z t is generated randomly from X t , Z t is not adapted to F t . Obviously, if σ 2 = 0, we have the deterministic, perfect feedback case V t = V (X t ).

Algorithms

The Extra-Gradient algorithm. In the general framework outlined in the previous section, the Extra-Gradient (EG) algorithm of Korpelevich [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF] can be stated in recursive form as

X t+1/2 = Π X (X t -γ t V t ) X t+1 = Π X (X t -γ t V t+1/2 ) (EG)
where Π X (y) := arg min x∈X y -x denotes the Euclidean projection of y ∈ R d onto the closed convex set X and γ t > 0 is a variable step-size sequence. Using this formulation as a starting point, the main idea behind the method can be described as follows: at each t = 1, 2, . . . , the oracle is called at the algorithm's current -or base -state X t to generate an intermediate -or leading -state X t+1/2 ; subsequently, the base state X t is updated to X t+1 using gradient information from the leading state X t+1/2 , and the process repeats. Heuristically, the extra oracle call allows the algorithm to "anticipate" the landscape of V and, in so doing, to achieve improved convergence results relative to standard projected gradient / forward-backward methods; for a detailed discussion, we refer the reader to [START_REF] Bubeck | Convex optimization: Algorithms and complexity[END_REF][START_REF] Facchinei | Finite-Dimensional Variational Inequalities and Complementarity Problems[END_REF] and references therein.

Single-call variants of the Extra-Gradient algorithm. Given the significant computational overhead of gradient calculations, a key desideratum is to drop the second oracle call in (EG) while retaining the algorithm's "anticipatory" properties. In light of this, we will focus on methods that perform a single oracle call at the leading state X t+1/2 , but replace the update rule for X t+1/2 (and, possibly, X t as well) with a proxy that compensates for the missing gradient. Concretely, we will examine the following family of single-call extra-gradient (1-EG) algorithms:

1. Past Extra-Gradient (PEG) [START_REF] Chiang | Online optimization with gradual variations[END_REF][START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF][START_REF] Popov | A modification of the Arrow-Hurwicz method for search of saddle points[END_REF]:

X t+1/2 = Π X (X t -γ t V t-1/2 ) X t+1 = Π X (X t -γ t V t+1/2 ) (PEG) [Proxy: use V t-1/2 instead of V t in the calculation of X t+1/2 ]
2. Reflected Gradient (RG) [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF][START_REF] Cui | On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems[END_REF][START_REF] Malitsky | Projected reflected gradient methods for monotone variational inequalities[END_REF]:

X t+1/2 = X t -(X t-1 -X t ) X t+1 = Π X (X t -γ t V t+1/2 ) (RG)
[Proxy: use (X t-1 -X t )/γ t instead of V t in the calculation of X t+1/2 ; no projection] 3. Optimistic Gradient (OG) [START_REF] Daskalakis | Training GANs with optimism[END_REF][START_REF] Mokhtari | Convergence rate of O(1/k) for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point problems[END_REF][START_REF] Mokhtari | A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach[END_REF][START_REF] Peng | Training GANs with centripetal acceleration[END_REF]:

X t+1/2 = Π X (X t -γ t V t-1/2 ) X t+1 = X t+1/2 + γ t V t-1/2 -γ t V t+1/2 (OG) [Proxy: use V t-1/2 instead of V t in the calculation of X t+1/2 ; use X t+1/2 + γ t V t-1/2 instead of X t in the calculation of X t+1 ; no projection]
These are the main algorithmic schemes that we will consider, so a few remarks are in order. First, given the extensive literature on the subject, this list is not exhaustive; see e.g., [START_REF] Mokhtari | Convergence rate of O(1/k) for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point problems[END_REF][START_REF] Mokhtari | A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach[END_REF][START_REF] Peng | Training GANs with centripetal acceleration[END_REF] for a generalization of (OG), [? ] for a variant that employs averaging to update the algorithm's base state X t , and [START_REF] Gidel | Negative momentum for improved game dynamics[END_REF] for a proxy defined via "negative momentum". Nevertheless, the algorithms presented above appear to be the most widely used single-call variants of (EG), and they illustrate very clearly the two principal mechanisms for approximating missing gradients: (i) using past gradients (as in the PEG and OG variants); and/or (ii) using a difference of successive states (as in the RG variant).

We also take this opportunity to provide some background and clear up some issues on terminology regarding the methods presented above. First, the idea of using past gradients dates back at least to Popov [START_REF] Popov | A modification of the Arrow-Hurwicz method for search of saddle points[END_REF], who introduced (PEG) as a "modified Arrow-Hurwicz" method a few years after the original paper of Korpelevich [START_REF] Korpelevich | The extragradient method for finding saddle points and other problems[END_REF]; the same algorithm is called "meta" in [START_REF] Chiang | Online optimization with gradual variations[END_REF] and "extrapolation from the past" in [START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF] (but see also the note regarding optimism below). The terminology "Reflected Gradient" and the precise formulation that we use here for (RG) is due to Malitsky [START_REF] Malitsky | Projected reflected gradient methods for monotone variational inequalities[END_REF]. The wellknown primal-dual algorithm of Chambolle and Pock [START_REF] Chambolle | A first-order primal-dual algorithm for convex problems with applications to imaging[END_REF] can be seen as a one-sided, alternating variant of the method for saddle-point problems; see also [START_REF] Yadav | Stabilizing adversarial nets with prediction methods[END_REF] for a more recent take.

Finally, the terminology "optimistic" is due to Rakhlin and Sridharan [START_REF] Rakhlin | Online learning with predictable sequences[END_REF][START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF], who provided a unified view of (PEG) and (EG) based on the sequence of oracle vectors used to update the algorithm's leading state X t+1/2 . 4 Because the framework of [START_REF] Rakhlin | Online learning with predictable sequences[END_REF][START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF] encompasses two different algorithms, there is some danger of confusion regarding the use of the term "optimism"; in particular, both (EG) and (PEG) can be seen as instances of optimism. The specific formulation of (OG) that we present here is the projected version of the algorithm considered by Daskalakis et al. [START_REF] Daskalakis | Training GANs with optimism[END_REF];5 by contrast, the "optimistic" method of Mertikopoulos et al. [START_REF] Mertikopoulos | Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile[END_REF] is equivalent to (EG) -not (PEG) or (OG).

The above shows that there can be a broad array of single-call extra-gradients methods depending on the specific proxy used to estimate the missing gradient, whether it is applied to the algorithm's base or leading state, when (or where) a projection operator is applied, etc. The contact point of all these algorithms is the unconstrained setting (X = R d ) where they are exactly equivalent:

Proposition 1. Suppose that the 1-EG methods presented above share the same initialization, X 0 = X 1 ∈ X , V 1/2 = 0, and are run with the same, constant step-size γ t ≡ γ for all t ≥ 1. If X = R d , the generated iterates X t coincide for all t ≥ 1.

The proof of this proposition follows by a simple rearrangement of the update rules for (PEG), (RG) and (OG), so we omit it. In the projected case, the 1-EG updates presented above are no longer equivalent -though, of course, they remain closely related.

Deterministic analysis

We begin with the deterministic analysis, i.e., when the optimizer receives oracle feedback of the form (1) with σ = 0. In terms of presentation, we keep the global and local cases separated and we interleave our results for the generated sequence X t and its ergodic average. To streamline our presentation, we defer the details of the proofs to the paper's supplement and only discuss here the main ideas.

Global convergence

Our first result below shows that the algorithms under study achieve the optimal O(1/t) ergodic convergence rate in monotone problems with Lipschitz continuous operators.

Theorem 1. Suppose that V satisfies Assumptions 1-3. Assume further that a 1-EG algorithm is run with perfect oracle feedback and a constant step-size γ < 1/(cβ), where c = 1 + √ 2 for the RG variant and c = 2 for the PEG and OG variants. Then, for all R > 0, we have

Err R Xt ≤ R 2 + X 1 -X 1/2 2 2γt
where Xt = t -1 t s=1 X s+1/2 is the ergodic average of the algorithm's sequence of leading states.

This result shows that the EG and 1-EG algorithms share the same convergence rate guarantees, so we can safely drop one gradient calculation per iteration in the monotone case. The proof of the theorem is based on the following technical lemma which enables us to treat the different variants of the 1-EG method in a unified way. Lemma 2. Assume that V satisfies Assumption 3 (monotonicity). Suppose further that the sequence (X t ) t∈N/2 of points in R d satisfies the following "quasi-descent" inequality with µ s , λ s ≥ 0:

X s+1 -p 2 ≤ X s -p 2 -2λ s V (X s+1/2 ), X s+1/2 -p + µ s -µ s+1 (3)
for all p ∈ X R and all s ∈ {1, . . . , t}. Then,

Err R t s=1 λ s X s+1/2 t s=1 λ s ≤ R 2 + µ 1 2 t s=1 λ s . Remark 1.
For Examples 1 and 2 it is possible to state both Theorem 1 and Lemma 2 with more adapted measures. We refer the readers to the supplement for more details.

The use of Lemma 2 is tailored to time-averaged sequences like Xt , and relies on establishing a suitable "quasi-descent inequality" of the form (3) for the iterates of 1-EG. Doing this requires in turn a careful comparison of successive iterates of the algorithm via the Lipschitz continuity assumption for V ; we defer the precise treatment of this argument to the paper's supplement.

On the other hand, because the role of averaging is essential in this argument, the convergence of the algorithm's last iterate requires significantly different techniques. To the best of our knowledge, there are no comparable convergence rate guarantees for X t under Assumptions 1-3; however, if Assumption 3 is strengthened to Assumption 3(s), the convergence of X t to the (necessarily unique) solution of (VI) occurs at a geometric rate. For completeness, we state here a consolidated version of the geometric convergence results of Malitsky [START_REF] Malitsky | Projected reflected gradient methods for monotone variational inequalities[END_REF], Gidel et al. [START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF], and Mokhtari et al. [START_REF] Mokhtari | A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: proximal point approach[END_REF]. Theorem 2. Assume that V satisfies Assumptions 1, 2 and 3(s), and let x denote the (necessarily unique) solution of (VI). If a 1-EG algorithm is run with a sufficiently small step-size γ, the generated sequence X t converges to x at a rate of X t -x = O(exp(-ρ t)) for some ρ > 0.

Local convergence

We continue by presenting a local convergence result for deterministic, non-monotone problems. To state it, we will employ the following notion of regularity in lieu of Assumptions 1-3 and 3(s). Definition 3. We say that x is a regular solution of (VI) if V is C 1 -smooth in a neighborhood of x and the Jacobian Jac V (x ) is positive-definite along rays emanating from x , i.e.,

z Jac V (x )z ≡ d i,j=1 z i ∂V i ∂x j (x )z j > 0 (4)
for all z ∈ R d \{0} that are tangent to X at x . This notion of regularity is an extension of similar conditions that have been employed in the local analysis of loss minimization and saddle-point problems. More precisely, if V = ∇f for some loss function f , this definition is equivalent to positive-definiteness of the Hessian along qualified constraints [START_REF] Bertsekas | Nonlinear programming[END_REF]Chap. 3.2]. As for saddle-point problems and smooth games, variants of this condition can be found in several different sources, see e.g., [START_REF] Facchinei | Generalized Nash equilibrium problems[END_REF][START_REF] Liang | Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks[END_REF][START_REF] Mertikopoulos | Learning in games with continuous action sets and unknown payoff functions[END_REF][START_REF] Ratliff | Characterization and computation of local nash equilibria in continuous games[END_REF][START_REF] Rosen | Existence and uniqueness of equilibrium points for concave N -person games[END_REF] and references therein.

Under this condition, we obtain the following local geometric convergence result for 1-EG methods.

Theorem 4. Let x be a regular solution of (VI). If a 1-EG method is run with perfect oracle feedback and is initialized sufficiently close to x with a sufficiently small constant step-size,we have

X t -x = O(exp(-ρ t)) for some ρ > 0.
The proof of this theorem relies on showing that (i) V essentially behaves like a smooth, strongly monotone operator close to x ; and (ii) if the method is initialized in a small enough neighborhood of x , it will remain in said neighborhood for all t. As a result, Theorem 4 essentially follows by "localizing" Theorem 2 to this neighborhood.

As a preamble to our stochastic analysis in the next section, we should state here that, albeit straightforward, the proof strategy outlined above breaks down if we have access to V only via a stochastic oracle. In this case, a single "bad" realization of the feedback noise Z t could drive the process away from the attraction region of any local solution of (VI). For this reason, the stochastic analysis requires significantly different tools and techniques and is considerably more intricate.

Stochastic analysis

We now present our analysis for stochastic variational inequalities with oracle feedback of the form (1). For concreteness, given that the PEG variant of the 1-EG method employs the most straightforward

∥ x -x * ∥ 2 EG 1-EG γ = 0.3 γ = 0.6 γ = 0.9 γ = 1.2 (c) Non-monotone [ 1 = 1, 2 = -1], iid Z ∼ N (0, .01), last iterate (b = 15)
Figure 1: Illustration of the performance of EG and 1-EG in the (a priori non-monotone) saddle-point problem

L(θ, φ) = 2 1θ A1θ + 2 θ A2θ 2 -2 1φ B1φ -2 φ B2φ 2 + 4θ Cφ
on the full unconstrained space X = R d = R d 1 ×d 2 with d1 = d2 = 1000 and A1, B1, A2, B2 0. We choose three situations representative of the settings considered in the paper: (a) linear convergence of the last iterate of the deterministic methods in strongly monotone problems; (b) the O(1/t) convergence of the ergodic average in monotone, deterministic problems; and (c) the O(1/t) local convergence rate of the method's last iterate in stochastic, non-monotone problems. For (a) and (b), the origin is the unique solution of (VI), and for (c) it is a regular solution thereof. We observe that 1-EG consistently outperforms EG in terms of oracle calls for a fixed step-size, and the observed rates are consistent with the rates reported in Table 1.

proxy mechanism, we will focus on this variant throughout; for the other variants, the proofs and corresponding explicit expressions follow from the same rationale (as in the case of Theorem 1).

Global convergence

As we mentioned in the introduction, under Assumptions 1-3, Cui and Shanbhag [START_REF] Cui | On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems[END_REF] and Gidel et al. [START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF] showed that 1-EG methods attain a O(1/ √ t) ergodic convergence rate. By strengthening Assumption 3 to Assumption 3(s), we show that this result can be augmented in two synergistic ways: under Assumptions 1, 2 and 3(s), both the last iterate and the ergodic average of 1-EG achieve a O(1/t) convergence rate.

Theorem 5. Suppose that V satisfies Assumptions 1, 2 and 3(s), and assume that (PEG) is run with stochastic oracle feedback of the form (1) and a step-size of the form γ t = γ/(t + b) for some γ > 1/α and b ≥ 4βγ. Then, the generated sequence of the algorithm's base states satisfies

E[ X t -x 2 ] ≤ 6γ 2 σ 2 αγ -1 1 t + o 1 t , (5)
while its ergodic average Xt = t -1 t s=1 X s enjoys the bound

E[ Xt -x 2 ] ≤ 6γ 2 σ 2 αγ -1 log t t + o log t t . (6)
Regarding our proof strategy for the last iterate of the process, we can no longer rely either on a contraction argument or the averaging mechanism that yields the O(1/ √ t) ergodic convergence rate. Instead, we show in the appendix that X t is (stochastically) quasi-Fejér in the sense of [START_REF] Combettes | Quasi-Fejérian analysis of some optimization algorithms[END_REF][START_REF] Combettes | Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping[END_REF]; then, leveraging the method's specific step-size, we employ successive numerical sequence estimates to control the summability error and obtain the O(1/t) rate.

Local convergence

We proceed to examine the convergence of the method in the stochastic, non-monotone case. Our main result in this regard is the following. Theorem 6. Let x be a regular solution of (VI) and fix a tolerance level δ > 0. Suppose further that (PEG) is run with stochastic oracle feedback of the form (1) and a variable step-size of the form γ t = γ/(t + b) for some γ > 1/α and large enough b. Then:

(a) There are neighborhoods U and U

1 of x in X such that, if X 1/2 ∈ U, X 1 ∈ U 1 , the event E ∞ = {X t+1/2 ∈ U for all t = 1, 2, . . . }
occurs with probability at least 1 -δ.

(b) Conditioning on the above, we have:

E[ X t -x 2 | E ∞ ] ≤ 4γ 2 (M 2 + σ 2 ) (αγ -1)(1 -δ) 1 t + o 1 t ,
where

M = sup x∈U V (x) < ∞ and α = inf x∈U V (x), x -x / x -x 2 > 0.
The finiteness of M and the positivity of α are both consequences of the regularity of x and their values only depend on the size of the neighborhood U . Taking a larger U would increase the algorithm's certified initialization basin but it would also negatively impact its convergence rate (since M would increase while α would decrease). Likewise, the neighborhood U 1 only depends on the size of U and, as we explain in the appendix, it suffices to take U 1 to be "one fourth" of U .

From the above, it becomes clear that the situation is significantly more involved than the corresponding deterministic analysis. This is also reflected in the proof of Theorem 6 which requires completely new techniques, well beyond the straightforward localization scheme underlying Theorem 4. More precisely, a key step in the proof (which we detail in the appendix) is to show that the iterates of the method remain close to x for all t with arbitrarily high probability. In turn, this requires showing that the probability of getting a string of "bad" noise realizations of arbitrary length is controllably small. Even then however, the global analysis still cannot be localized because conditioning changes the probability law under which the oracle noise is unbiased. Accounting for this conditional bias requires a surprisingly delicate probabilistic argument which we also detail in the supplement.

Concluding remarks

Our aim in this paper was to provide a synthetic view of single-call surrogates to the Extra-Gradient algorithm, and to establish optimal convergence rates in a range of different settings -deterministic, stochastic, and/or non-monotone. Several interesting avenues open up as a result, from extending the theory to more general Bregman proximal settings, to developing an adaptive version as in the recent work [START_REF] Bach | A universal algorithm for variational inequalities adaptive to smoothness and noise[END_REF] for two-call methods. We defer these research directions to future work.

A Technical lemmas

Lemma A.1. Let x, y ∈ R d and C ⊆ R d be a closed convex set. We set x + := Π C (x -y). For all p ∈ C, we have

x + -p 2 ≤ x -p 2 -2 y, x + -p -x + -x 2 .
Proof. Since p ∈ C, we have the following property x + -(x -y), x + -p ≤ 0, leading to

x + -p 2 = x + -x + x -p 2 = x -p 2 + 2 x + -x, x -p + x + -x 2 = x -p 2 + 2 x + -x, x + -p -x + -x 2 ≤ x -p 2 -2 y, x + -p -x + -x 2 . Lemma A.2. Let x, y 1 , y 2 ∈ R d and C 1 , C 2 ⊆ R d be two closed convex sets. We set x + 1 := Π C1 (x -y 1 ) and x + 2 := Π C2 (x -y 2 ). (a) If C 2 = R d , for all p ∈ R d , it holds x + 2 -p 2 = x -p 2 -2 y 2 , x + 1 -p + x + 2 -x + 1 2 -x + 1 -x 2 . (b) If C 2 ⊆ C 1 , for all p ∈ C 2 , it holds x + 2 -p 2 ≤ x -p 2 -2 y 2 , x + 1 -p + 2 y 2 -y 1 , x + 1 -x + 2 -x + 2 -x + 1 2 -x + 1 -x 2 ≤ x -p 2 -2 y 2 , x + 1 -p + y 2 -y 1 2 -x + 1 -x 2 . (A.1)
Proof. (a) We develop

x + 2 -p 2 = x + 2 -x + 1 + x + 1 -x + x -p 2 = x + 2 -x + 1 2 + x + 1 -x 2 + x -p 2 + 2 x + 2 -x + 1 , x + 1 -p + 2 x + -x, x -p = x + 2 -x + 1 2 -x + 1 -x 2 + x -p 2 + 2 x + 2 -x + 1 , x + 1 -p + 2 x + 1 -x, x + 1 -p = x -p 2 -2 y 2 , x + 1 -p + x + 2 -x + 1 2 -x + 1 -x 2 ,
where in the last line we use

x + 2 -x = -y 2 since C 2 = R d . (b) With x + 2 ∈ C 2 ⊆ C 1 , we can apply Lemma A.1 to (x, y, x + , p, C) ← (x, y 2 , x + 2 , p, C 2 ) and (x, y, x + , p, C) ← (x, y 1 , x + 1 , x + 2 , C 1 ), which yields x + 2 -p 2 ≤ x -p 2 -2 y 2 , x + 2 -p -x + 2 -x 2 , (A.2) x + 1 -x + 2 2 ≤ x -x + 2 2 -2 y 1 , x + 1 -x + 2 -x + 1 -x 2 . (A.3)
By summing (A.2) and (A.3), we readily get the first inequality of (A.1). We conclude with help of Young's inequality 2 y 2 -

y 1 , x + 1 -x + 2 ≤ y 2 -y 1 2 + x + 1 -x + 2 2 .
Lemma A.3 (Chung [START_REF] Chung | On a stochastic approximation method[END_REF]Lemma 1]). Let (a t ) t∈N be a sequence of real numbers and b, t 0 ∈ N such that for all t ≥ t 0 ,

a t+1 ≤ 1 - q t + b a t + q (t + b) 2 , (A.4)
where q > 1 and q > 0. Then,

a t ≤ q q -1 1 t + o 1 t . (A.5)
Proof. For the sake of completeness, we provide a basic proof for the above lemma (which is a direct corollary of Chung [START_REF] Chung | On a stochastic approximation method[END_REF]Lemma 1]). Let q > 1 and k ∈ N, we have

1 k + 1 -1 - q k 1 k = q k 2 - 1 k - 1 k + 1 = q -1 k 2 + 1 k 2 (k + 1)
.

This shows that for any q > 0 q q -1

1 k + 1 -1 - q k 1 k = q k 2 + q k 2 (k + 1)(q -1) ≥ q k 2 . (A.6)
By substituting k ← t + b, (A.4) combined with (A.6) yields

a t+1 - q q -1 1 t + b + 1 ≤ 1 - q t + b a t - q q -1 1 t + b . (A.7)
Let us define a t := a t -q /((q -1)(t + b)). (A.7) becomes

a t+1 ≤ 1 - q t + b a t . (A.8)
This inequality holds for all t ≥ t 0 . Then, either:

• a t becomes non-positive for some t > t 1 = max(t 0 , q -b), and (A.8) implies that this is also the case for all subsequent t, which leads to

a t ≤ q q -1 1 t + b .
• or a t is positive for all t > t 1 and we get

0 < a t ≤ a t1 t-1 s=t1 1 - q s + b = O 1 t q = o 1 t .
In both cases, (A.5) is verified.

Lemma A.4. Let x be a regular solution of (VI). Then, there exists constants r, α, β > 0 such that V is β-Lipschitz continuous on K := B r (x ) and V (x), x -x ≥ α x -x 2 for all x ∈ U := X ∩ K.

Proof. The Lipschitz continuity is straightforward: a C 1 -smooth operator is necessarily locally Lipschitz and thus Lipshitz on every compact. The proof consists in establishing the existence of α.

To this end, we consider the following function:

φ : R d×d -→ R G -→ min z∈TC X (x ), z =1 z Gz
where TC X (x ) denotes the tangent cone to X at x . The function φ is concave as it is defined as a pointwise minimum over a set of linear functions. This in turn implies the continuity φ because every concave function is continous on the interior of its effective domain. The solution x being regular, we have φ(Jac V (x )) > 0. Combined with the continuity of Jac V in a neighborhood of x , we deduce the existence of r, α > 0 such that φ(Jac

V (x)) ≥ α for all x ∈ K = B r (x ). Now let x ∈ U = X ∩ K. It holds: V (x) -V (x ) = 1 0 Jac V (x + λ(x -x )) dλ (x -x ).
Consequently, writing z = x -x ∈ TC X (x ),

x λ = x + λ(x -x ) ∈ K, we have V (x) -V (x ), x -x = z 1 0 Jac V (x λ ) dλ z ≥ φ(Jac V (x λ )) dλ z 2 ≥ α z 2 = α x -x 2 .
Finally, since x is a solution of (VI), we have V (x ), x -x ≥ 0 and

V (x), x -x ≥ V (x) -V (x ), x -x ≥ α x -x 2 .
This ends the proof.

B Proofs for the deterministic setting B.1 Proof of Lemma 2

In the definition of Err R , instead of taking X R = X ∩ B R (0) we consider X R = X ∩ B R (X 1 ). Summing (3) over s and rearranging the term leads to

t s=1 2λ s V (X s+ 1 2 ), X s+ 1 2 -p ≤ X 1 -p 2 -X t+1 -p 2 + µ 1 -µ t+1 ≤ X 1 -p 2 + µ 1 .
For any p ∈ X R , we have X 1 -p2 ≤ R 2 , and by monoticity of V ,

V (p), X s+ 1 2 -p ≤ V (X s+ 1 2 ), X s+ 1 2 -p . In other words, for all p ∈ X R , 2 t s=1 λ s V (p), X s+ 1 2 -p ≤ R 2 + µ 1 . (B.1)
Dividing the two sides of (B.1) by 2 t s=1 λ s and maximizing over p ∈ X R leads to the desired result.

B.2 Proof of Theorem 1

To facilitate analysis and presentation of our results, (PEG) and (OG) are initialized with random X 1 2 and X 1 in X while for (RG) we start with X 0 and X 1 2 . We are constrained to have different initial states in (RG) due to its specific formulation.

The theorem is immediate from Lemma 2 if we know that (3) is verified by the generated iterates for some (λ t ) t∈N , (µ t ) t∈N ∈ R N + . Below, we show it separately for PEG, OG and RG under Assumption 2 and with γ selected as per the theorem statement. Moreover, we have (λ t ) t∈N ≡ γ and

µ 1 ≤ X 1 -X 1
Past Extra-Gradient (PEG). For t ≥ 1, the second inequality of Lemma A.2 (b) applied to

(x, y 1 , y 2 , x + 1 , x + 2 , C 1 , C 2 ) ← (X t , γV (X t-1 2 ), γV (X t+ 1 2 ), X t+ 1 2 , X t+1 , X , X ) results in X t+1 -p 2 ≤ X t -p 2 -2γ V (X t+ 1 2 ), X t+ 1 2 -p + γ 2 V (X t+ 1 2 ) -V (X t-1 2 ) 2 -X t+ 1 2 -X t 2 ≤ X t -p 2 -2γ V (X t+ 1 2 ), X t+ 1 2 -p + γ 2 β 2 X t+ 1 2 -X t-1 2 2 -X t+ 1 2 -X t 2 (B.2)
where we used the fact that V is β-Lipschitz continuous for the second inequality.

Now, let us use Young

's inequality a + b 2 ≤ 2 a 2 + 2 b 2 to get X t+ 1 2 -X t-1 2 2 ≤ 2 X t+ 1 2 -X t 2 + 2 X t -X t-1 2 2 (B.3)
and the non-expansiveness of the projection to get for any t ≥ 2,

X t -X t-1 2 2 ≤ X t-1 -γV (X t-1 2 ) -X t-1 + γV (X t-3 2 ) 2 ≤ γ 2 β 2 X t-1 2 -X t-3 2 2 . (B.4)
Combining (B.3) and (B.4), we obtain

X t+ 1 2 -X t-1 2 2 ≤ 2 X t+ 1 2 -X t 2 + 2γ 2 β 2 X t-1 2 -X t-3 2 2 ≤ 2 X t+ 1 2 -X t 2 + 1 2 X t-1 2 -X t-3 2 2 , (B.5)
where we used the fact that γ ≤ 1/(2β) in the last inequality; and in order to display a telescopic term, we reformulate (B.5) as

X t+ 1 2 -X t-1 2 2 = 2 X t+ 1 2 -X t-1 2 2 -X t+ 1 2 -X t-1 2 2 ≤ 4 X t+ 1 2 -X t 2 + X t-1 2 -X t-3 2 2 -X t+ 1 2 -X t-1 2 2 . (B.6)
We now substitute (B.6) in (B.2) to get for all t ≥ 2,

X t+1 -p 2 ≤ X t -p 2 -2γ V (X t+ 1 2 ), X t+ 1 2 -p + (4γ 2 β 2 -1) X t+ 1 2 -X t
Loss minimization. V = ∇f is monotone implies the convexity of f , so

V (X s+ 1 2 ), X s+ 1 2 -p = ∇f (X s+ 1 2 ), X s+ 1 2 -p ≥ f (X s+ 1 2 ) -f (p). With Jensen's inequality we get, t s=1 λ s -1 t s=1 λ s V (X s+ 1 2 ), X s+ 1 2 -p ≥ t s=1 λ s -1 t s=1 λ s f (X s+ 1 2 ) -f (p) ≥ f (x) -f (p)
This is true for any p ∈ X , and especially for p ∈ X . Let R = dist(x 1 , X ). By invoking (??), we conclude

f (x) -min f ≤ R 2 + µ 1 2 t s=1 λ s .
Min-max optimization. V = (∇ θ L, -∇ φ L) being monotone is equivalent to L being convexconcave. In such saddle-point problems, the quality of a candidate solution x = ( θ, φ) is often assessed via the Nikaido-Isoda function [? ], defined here as

NI(x) = sup φ∈Φ L( θ, φ) -inf θ∈Θ L(θ, φ) (NI)
provided of course that the right-hand side is well-posed. Its restricted variant NI R can also be defined by analogy with the definition of Err R .

Let us denote X s+ 1 2 = (θ s+ 1 2 , φ s+ 1 2 ) and p = (θ, φ). By convex-concavity of L, it holds

V (X s+ 1 2 ), X s+ 1 2 -p = ∇ θ L(θ s+ 1 2 , φ s+ 1 2 ), θ s+ 1 2 -θ -∇ φ L(θ s+ 1 2 , φ s+ 1 2 ), φ s+ 1 2 -φ ≥ L(θ s+ 1 2 , φ s+ 1 2 ) -L(θ, φ s+ 1 2 ) + L(θ s+ 1 2 , φ) -L(θ s+ 1 2 , φ s+ 1 2 ) = L(θ s+ 1 2 , φ) -L(θ, φ s+ 1 2
). We can again apply Jensen's inequality to show that

t s=1 λ s -1 t s=1 λ s V (X s+ 1 2 ), X s+ 1 2 -p ≥ L( θ, φ) -L(θ, φ),
where we write x = ( θ, φ). By (??) and definition of the Nikaido-Isoda function, maximizing over

(θ, φ) ∈ X ∩ B R (X 1 ) gives NI R (x) ≤ R 2 + µ 1 2 t s=1 λ s .

B.4 Proof of Theorem 4

Here we provide a quick proof of Theorem 4. We do not try to optimize the constants and better results could be derived by examining each algorithm carefully. Note that since RG can evaluate V at infeasible points, we need to strengthen condition (4) in Definition 3 to consider all z in the tangent span of X , i.e., the subspace of R d spanned by all possible displacement vectors of the form z = x -x, x, x ∈ X .

In order to show a local geometric convergence rate we only need to show that by choosing sufficiently small constant step-size and initializing at points sufficiently close to x , we ensure X t ∈ K for all t ∈ N/2 (where K is defined in Lemma A.4 and this is in view of Theorem 2). In fact, although Theorem 2 is stated for strongly monotone operators, by carefully examining its proof, it turns out that we only need V (X t+ 1 2 ), X t+ 1 2 -x ≥ α X t+ 1 2 -x 2 for some constant α > 0 and all t ∈ N. We thus proceed to show that ∀t ∈ N/2, X t ∈ K. To do so, let us show that one can choose the initial points and γ so that ∀t ∈ N, (i) X t -x 2 ≤ r 2 4 ; (ii) X t+ 1 2 ∈ K. Part (i). It is proved in Appendix B.2 that the iterates of the 1-EG methods verify (3) under Assumption 2 (Lipschitz continuity) if γ is smaller than some constant. By Lemma A.4 we know that V is indeed Lipschitz continuous on the compact K. Suppose that for all s ∈ N/2, s ≤ t, we have X s ∈ K, then it holds V (X s+ 1 2 ), X s+ 1 2 -x ≥ 0 for all s ∈ {1, ..., t -1}. This is true for PEG We conclude by applying Lemma A.3 with a

t ← E[ X t -x 2 ]+γ 2 t-1 E[ V t-1 2 -V t-3 2
2 ], q ← αγ, q ← 6γ 2 σ 2 , and t 0 ← 2, which gives

E[ X t -x 2 ] + γ 2 t-1 E[ V t-1 2 -V t-3 2 2 ] ≤ 6γ 2 σ 2 αγ -1 1 t + o 1 t .
The second term on the left-hand side (LHS) of the inequality is always positive, and (5) follows immediately.

Ergodic convergence. The convergence of Xt as shown in ( 6) can be deduce directly from above by using Jensen's inequality:

E[ Xt -x 2 ] ≤ 1 t t s=1 E[ X s -x 2 ],
and then we bound the right-hand side (RHS) of the inequality by [START_REF] Bertsekas | Nonlinear programming[END_REF].

C.2 Proof of Theorem 6

We start by defining some important quantities that will be used in our proof. For any T ≥ 1, we set

S T := T t=1 2γ t Z t+ 1 2 , X t+ 1 2 -x , R T := T t=1 2γ 2 t ( V t+ 1 2 2 + V t-1 2
2 ),

Q T := S 2 T + R T . Notice that S T , R T and Q T are not F T -measurable but F T +1 -measurable (due to the terms in Z T + 1 2 and V T + 1 2 )
. For the sake of simplicity, we also write ξ t+ 1 2 := Z t+ 1 2 , X t+ 1 2 -x so that S T = T t=1 2γ t ξ t+ 1 2 and E[ξ t+ 1 2 | F t ] = 0. Regarding the choice of U and U 1 , we invoke Lemma A.4 to obtain the corresponding α, r and U . We then set U 1 := X ∩ B r/4 (x ). Let us consider the following events for T ≥ 1,

H T := max 1≤t≤T Q t ≤ ε := min r 2 8 , r 4
16 ,

E T := ∀t ∈ {1, ..., T }, X t+ 1 2 ∈ U . We additionally define Q 0 := 2γ 2 1 V 1 2
2 , H 0 := {Q 0 ≤ ε} and H -1 := E 0 := Ω, where Ω denotes the whole sample space. It follows from the definitions that both (H T ) T ≥-1 and (E T ) T ≥0 are decreasing sequences of events. Moreover, we have

H T ∈ F T +1 while E T ∈ F T . Also notice that E ∞ = T ≥0 E T .
In terms of notation, for an event E ⊆ Ω, we denote by 1 E its indicator function and E c its complementary. For any pair of events E, F ⊆ Ω, we denote by E \ F the event "E and not F " i.e., E ∩ F c .

The proof of the theorem relies on the two following lemmas. Lemma C.1. For any T ≥ 0, we have the inclusion H T -1 ⊆ E T .

Proof. We prove this result by induction.

Initialization: H -1 ⊆ E 0 is clear. To prove that we also have H 0 ⊆ E 1 , we use Young's inequality to get

X 3 2 -x 2 ≤ 2 X 3 2 -X 1 2 + 2 X 1 -x 2 . (C.8)
On the one hand, since X 1 ∈ U 1 by assumption, it holds X 1 -x 2 ≤ r 2 16 . On the other hand, 2

X 3 2 -X 1 2 = 2 Π X (X 1 -γ 1 V 1 2 ) -Π X (X 1 ) 2 ≤ 2γ 1 V 1 2 2 = Q 0 20
For any realization in H 0 , we have

2γ 1 V 1 2 2 ≤ r 2 8
; and so we can deduce from (C.8) that X 3 2x 2 ≤ r 2 4 < r 2 . Since X 3 2 ∈ X , it follows that X 3 2 ∈ U . This means that H 0 ⊆ E 1 . Inductive step: Suppose that H T -1 ⊆ E T holds for some T ≥ 1. We would like to prove H T ⊆ E T +1 . To do so, we show that X T +1 -x 2 ≤ 7 16 r 2 for any realization in H T . Applying Lemma A.2 (b) as in (C.1) yields for all t ∈ {1, ..., T },

X t+1 -x 2 ≤ X t -x 2 -2γ t V t+ 1 2 , X t+ 1 2 -x + γ 2 t V t+ 1 2 -V t-1 2 2 -X t+ 1 2 -X t 2 ≤ X t -x 2 -2γ t V (X t+ 1 2 ), X t+ 1 2 -x -2γ t Z t+ 1 2 , X t+ 1 2 -x + 2γ 2 t ( V t+ 1 2 2 + V t-1 2
2 )

≤ X t -x 2 -2γ t ξ t+ 1 2 + 2γ 2 t ( V t+ 1 2 2 + V t-1 2
2 ), (C.9)

where in the last line we can use V (X t+ 1 2 ), X t+ 1 2 -x ≥ 0 since by induction hypothesis, H T ⊆ H T -1 ⊆ E T , which means for any realization in H T , X t+ 1 2 ∈ U for all t ∈ {1, ..., T }. Summing (C.9) from t = 1 to T gives

X T +1 -x 2 ≤ X 1 -x 2 - T t=1 2γ t ξ t+ 1 2 + T t=1 2γ 2 t ( V t+ 1 2 2 + V t-1 2 2 ) = X 1 -x 2 -S T + R T .
By definition of H T , we have

S 2 T ≤ Q T ≤ r 4 16 (so |S T | ≤ r 2 4 ) and R T ≤ Q T ≤ r 2 8 . Using that X 1 -x 2 ≤ r 2
16 by assumption, it follows immediately that X T +1 -x 2 ≤ 7 16 r 2 . Finally, in order to bound X T + 3 2 -x 2 , we again rely on Young's inequality:

X T + 3 2 -x 2 ≤ 2 X T + 3 2 -X T +1 2 + 2 X T +1 -x 2 ≤ 2γ 2 T +1 V T + 1 2 2 + 2 X T +1 -x 2 .
(C.10)

For any realization in H T , we have that i)

2γ 2 T +1 V T + 1 2 2 ≤ 2γ 2 T V T + 1 2 2 ≤ R T ≤ Q T ≤ r 2 8 ;
ii) 2 X T +1 -x 2 ≤ 7 8 r 2 .

Thus, (C.10) implies that X T + 3 2 -x 2 ≤ r 2 , and subsequently X T + 3 2 ∈ U . As H T ⊆ E T and E T +1 = {X T + 3 2 ∈ U } ∩ E T , we have proven that H T ⊆ E T +1 . Lemma C.2. For t ≥ 1, we have the following recurrence inequality

E[Q t 1 Ht-1 ] ≤ E[Q t-1 1 Ht-2 ] + γ 2 t M -ε P(H t-2 \ H t-1 ), (C.11)
where M := 4M 2 + 4σ 2 + 4r 2 σ 2 and ε := min r 2 8 , r 4 16 . Moreover, if t = 1, the bound can be refined to

E[Q 1 1 H0 ] ≤ E[Q 0 1 H-1 ] + γ 2
1 (2M 2 + 2σ 2 + 4r 2 σ 2 ) -ε P(H -1 \ H 0 ). (C.12)

Proof. We decompose

E[Q t 1 Ht-1 ] = E[(Q t -Q t-1 ) 1 Ht-1 ] + E[Q t-1 1 Ht-1 ] = E[(Q t -Q t-1 ) 1 Ht-1 ] + E[Q t-1 1 Ht-2 ] -E[Q t-1 1 Ht-2\Ht-1 ], (C.13)
where the second equality comes from the fact that as H t-1 ⊆ H t-2 , we have H t-1 = H t-2 \ (H t-2 \ H t-1 ).

(a) We first show that by choosing b sufficiently large, we have P(H T ) ≥ 1 -δ for all T ≥ -1 (when T = -1, H -1 = Ω). To do so, we will work on the complementary event H T c = H T -1 c ∪(H T -1 \ H T ) and prove that P(H T c ) ≤ δ. We start by bounding P(H T -1 \ H T ),

ε P(H T -1 \ H T ) = ε P({Q T > ε} ∩ H T -1 ) = E[ε 1 {Q T >ε} ∩ H T -1 ] ≤ E[Q T 1 {Q T >ε} ∩ H T -1 ] ≤ E[Q T 1 H T -1 ]. (C.21)
The last line is true since Q T is a positive random variable.

We now use Lemma C.2 by summing (C.11) from t = 2 to T and (C.12) which leads to ). Since we initialize with X 1 2 ∈ U , we have As Γ converges to 0 when b → ∞, for any δ > 0 one can choose b sufficiently large so that Γ ≤ δε/M; we then have P(H T c ) ≤ δ, or equivalently, P(H T ) ≥ 1 -δ for all T ≥ -1.

E[Q T 1 H T -1 ] ≤ E[Q 1 1 H0 ] + T t=2 γ 2 t M - T t=2 ε P(H t-2 \ H t-1 ) ≤ E[Q 0 1 H-1 ] + γ 2 1 (2M
E[Q 0 ] = 2γ 2 1 E[ V 1 2 2 ] ≤ 2γ
Since H T -1 ⊆ E T from Lemma C.1, we know that by choosing b sufficiently large, we have P(E T ) ≥ P(H T -1 ) ≥ 1 -δ for all T ≥ 0. As (E T ) T ≥1 is a decreasing sequence of events and E ∞ = T ≥0 E T , by continuity from above we have

P(E ∞ ) = lim T →∞ P(E T ) ≥ 1 -δ,
concluding the proof.

(b) Applying Lemma A.2 (b) gives

X t+1 -x 2 ≤ X t -x 2 -2γ t V t+ 1 2 , X t+ 1 2 -x + γ 2 t V t+ 1 2 -V t-1

2 1 (

 1 M 2 + σ 2 ). (C.23) We set Γ := ∞ t=1 γ 2 t < ∞.Combining (C.21), (C.22) and (C.23), we obtainP(H T c ) = P(H T -1 \ H T ) + P(H T -1 c ) ≤ 1 ε E[Q T 1 H T -1 ] + P(H T -1 c )

Table 1 :

 1 The best known global convergence rates for single-call extra-gradient methods in monotone VI problems; logarithmic factors ignored throughout. A box indicates a contribution from this paper.

			Lipschitz	Lipschitz + Strong
	Deterministic Stochastic	1/	Ergodic £ ¢ ¡ 1/t √ t [14, 19]	Last Iterate Ergodic Unknown 1/t Unknown £ ¢ ¡ 1/t	Last Iterate e -ρt [19, 26, 32] £ ¢ ¡ 1/t

33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada.

  2 + 2σ 2 + 4r 2 σ 2 ) + \ H t-1 ) = E[Q 0 ] + γ 2 1 (2M 2 + 2σ 2 + 4r 2 σ 2 ) +where in the last line we use thatH -1 = Ω and H T -1 c = H -1 \ H T -1 = ˙ 1≤t≤T (H t-2 \ H t-1 ) ( with ˙ denoting the disjoint union) to get that P(H T -1 c ) =

	T	T
	t=2 ε P(H t-2 T γ 2 t M -t=1
	γ 2 t M -ε P(H T -1	c ),	(C.22)
	t=2

T t=1 P(H t-2 \ H t-1

Korpelevich [24] proved the method's asymptotic convergence for pseudomonotone variational inequalities. The O(1/t) convergence rate was later established by Nemirovski[START_REF] Nemirovski | Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF] with ergodic averaging.

A few weeks after the submission of our paper, we were made aware of a very recent preprint by Mokhtari et al.[START_REF] Mokhtari | Convergence rate of O(1/k) for optimistic gradient and extra-gradient methods in smooth convex-concave saddle point problems[END_REF] which also establishes a O(1/t) convergence rate for the algorithm's "optimistic" variant in saddlepoint problems (in terms of the Nikaido-Isoda gap function). To the best of our knowledge, this is the closest result to our own in the literature.

Depending on the algorithm, the sequence index t may take positive integer or half-integer values (or both).

More precisely, Rakhlin and Sridharan[START_REF] Rakhlin | Online learning with predictable sequences[END_REF][START_REF] Rakhlin | Optimization, learning, and games with predictable sequences[END_REF] use the term Optimistic Mirror Descent (OMD) in reference to the Mirror-Prox method of Nemirovski[START_REF] Nemirovski | Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[END_REF], itself a variant of (EG) with projections defined by means of a Bregman function; for a related treatment, see Nesterov[START_REF] Nesterov | Dual extrapolation its applications to solving variational inequalities and related problems[END_REF] and Juditsky et al.[START_REF] Juditsky | Solving variational inequalities with stochastic mirror-prox algorithm[END_REF].

To see this, note that the difference between two consecutive intermediate steps X t-1/2 and X t+1/2 can be written as X t+1/2 = ΠX (X t-1/2 -(γt-1 + γt)V t-1/2 + γt-1V t-3/2 ). Writing (OG) in the form presented above shows that (OG) can also be viewed as a single-call variant of the FBF method of Tseng[START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF].

2 for all methods, hence the corresponding bound in our statement. The arguments used in the proof are inspired from[START_REF] Gidel | A variational inequality perspective on generative adversarial networks[END_REF][START_REF] Malitsky | Projected reflected gradient methods for monotone variational inequalities[END_REF][START_REF] Tseng | A modified forward-backward splitting method for maximal monotone mappings[END_REF] but we emphasize the relation between the analyses of these algorithms by putting forward the technical Lemma A.2.

2 ]) + 6γ 2 t σ 2 .

Acknowledgments

This work benefited from financial support by MIAI Grenoble Alpes (Multidisciplinary Institute in Artificial Intelligence). P. Mertikopoulos was partially supported by the French National Research Agency (ANR) grant ORACLESS (ANR-16-CE33-0004-01) and the EU COST Action CA16228 "European Network for Game Theory" (GAMENET).

Optimistic Gradient (OG). The update of OG with constant step-size γ can be written as

)) X t+1 = X t -(X t -X t+ 1 2 + γV (X t+ 1 2 ) -γV (X t-1 2 )) In that form, we can use Lemma A.2 (a) with (x, y 1 , y 2 , x + 1 , x + 2 , C 1 , C 2 ) ← (X t , γV (X t-1 2 ), X t -X t+ 1 2 + γV (X

One the one hand, since X t+ 1 2 = Π X (X t -γV (X t-1 2 )) and p ∈ X , we have X t+ 1 2 -(X t -γV (X t-1 2 )), X t+ 1 2 -p ≤ 0. (B.9)

On the other other hand, by definition of X t+1 and the β-Lipschitz continuity of V ,

Then, applying the same arguments used to get (B.6), we can show that for all t ≥ 2,

2 ).

Finally, since (B.7) is still true using the same argument as for PEG, (3) is satisfied by choosing the same (µ t ) t∈N and (λ t ) t∈N as in the case of PEG; the same result thus holds for Optimistic Gradient (OG).

Reflected Gradient (RG). We recall the update rule of RG

). As in the previous cases, we use Lemma A.2. Using the first inequality of Part (b) with

By summing (B.13) and (B.14) and rearranging the terms, we get

Combining (B.12) and (B.15), we get

By using twice Young's inequality: i)

Substituting (B.17) into (B.16) yields

where in the last line, we used twice that γ

2 , λ t = γ and the result thus holds for Reflected Gradient (RG).

We also notice that

B.3 Lemma 2 with other suboptimality measures

Here we discuss how the statement of Lemma 2, and consequently also that of Theorem 1, can be adjusted to consider more adapted convergence measures in the cases of loss minimization and min-max optimization. The notations are those of Examples 1 and 2, and we write x = (

and OG because X s+ 1 2 ∈ X and subsequently X s+ 1 2 ∈ U = X ∪ K. For RG we did mention above that we need to relax the definition of a regular solution to consider all the z ∈ R d and the statement of Lemma A.4 can also be modified accordingly. Using (3), we obtain 6

for the three algorithms with µ t ≥ 0. By imposing X 1 2 = X 1 in PEG and OG, we get µ 1 = 0. Similarly, we may impose

It is thus possible to choose the adequate initial points and γ such that

4 . Part (ii). We now proceed to prove that we may choose γ sufficiently small such that if

We notice that for the three algorithms, we have

2 ) 2 by the non-expansiveness of the projection. 7 We define M := sup x∈K V (x) < ∞ where the finiteness of M comes from the continuity of V and the boundedness of K. We choose γ ≤ r/(2M )

Then, by Young's inequality, we get

In other words, X t+ 1 2 ∈ K. Conclusion. We first notice that the conditions on the initial points and the stepsize γ do not depend on the iteration. Thus, by simple induction we have that if we initialize the algorithm such that γ ≤ r/(2M ) and

then for all t ∈ N/2, X t ∈ K, concluding the proof.

C Proofs for the stochastic setting

Let us focus in this section on the (PEG) algorithm:

Following Appendix B.2, we initialize the algorithm with random X 1 2 and X 1 in X . Recall that (F t ) t∈ N 2 denotes the natural filtration associated with the sequence (X t ) t∈ N 2 . In the PEG algorithm, we have F t = F t+ 1 2 for all t ∈ N (thus X t+ 1 2 is F t -measurable) so the zero-mean hypothesis (2a) can be written as

C.1 Proof of Theorem 5

Last iterate convergence. As in the proof of Theorem 1, we first apply Lemma A.2 (b) with

) and the solution x ∈ X as a trial point to obtain

The following holds true thanks to the law of total expectation,

6 Please refer to the proof of Theorem 1 for the exact value of µt. 7 In particular this also holds for RG since then X t+ 1 2

)) -ΠX (Xt-1).

We also have

(C.5) Since x is the unique solution of (VI), it follows V (x ), X t+ 1 2 -x ≥ 0. Consequently, with strong monotonicity of V , we get

Taking expectation over (C.1) and using (C.4), (C.5), (C.6) leads to

For t ≥ 2, we write

Since S t-1 and H t-1 are F t -measurable, we get

By Lemma C.1, H t-1 ⊆ E t which means that for any realization in H t-1 , we have

Using again that H t-1 is F t -measurable along with the boundedness of the variance of Z t+ 1 2 (see Eq. ( 2b)), we get

(C.16)

Applying once again the techniques above and relying on the boundedness of V (as for any realization in

Using that H t-1 ⊆ H t-2 and repeating the arguments leading to (C.17), we have

For the last term on the RHS of (C.13), we get by definition that for any realization in The case t = 1 is proved similarly. In fact,

Consequently by using H 0 ⊆ E 1 , we have [START_REF] Gidel | Negative momentum for improved game dynamics[END_REF]) is equally true with t = 1. (C.12) can then be immediately deduced from (C.13).

Proof of Theorem 6.

We also recall that as E t ∈ F t , it holds

We can choose b sufficiently large so that 2αγ t -1 ≤ 0 for all t ≥ 1. Using E t ⊆ E t-1 , we obtain

By applying Lemma A.3 with a t ← E[ X t -x 2 1 Et-1 ], q ← αγ, q ← 4γ 2 (M 2 + σ 2 ), and t 0 ← 1, we get

Finally,

and our proof is complete.

Remark. We notice that to complete the above proof, we only require Eq. (2a) and Eq. (2b) to be held on the event {X t+ 1 2 ∈ U }. For example, in (C.16) we want

which is true if Eq. (2b) holds on {X t+ 1 2 ∈ U } since H t-1 ⊆ E t ⊆ {X t+ 1 2 ∈ U }. This assumption is much weaker and more sensible. It in particular shows that to obtain local guarantee we indeed only need the noise to be bounded locally.