Sifting through the Noise: Universal First-Order Methods for Stochastic Variational Inequalities
Year: 2022

Abstract:
We examine a flexible algorithmic framework for solving monotone variational inequalities in the presence of randomness and uncertainty. The proposed template encompasses a wide range of popular first-order methods, including dual averaging, dual extrapolation and optimistic gradient algorithms – both adaptive and non-adaptive. Our first result is that the algorithm achieves the optimal rates of convergence for cocoercive problems when the profile of the randomness is known to the optimizer: O(1/ √ T ) for absolute noise profiles, and O(1/T ) for relative ones. Subsequently, we drop all prior knowledge requirements (the absolute/relative variance of the randomness affecting the problem, the operator’s cocoercivity constant, etc.), and we analyze an adaptive instance of the method that gracefully interpolates between the above rates – i.e., it achieves O(1/ √ T ) and (1/T ) in the absolute and relative cases, respectively. To our knowledge, this is the first universality result of its kind in the literature and, somewhat surprisingly, it shows that an extra-gradient proxy step is not required to achieve optimal rates.

text: √ T ) for absolute noise profiles, and O(1/T ) for
relative ones. Subsequently, we drop all prior knowledge requirements (the absolute/relative variance of the randomness affecting the problem, the operator’s cocoercivity constant, etc.), and we analyze an adaptive instance of the method that gracefully interpolates between the above rates – i.e., it achieves O(1/ √ T ) and (1/T ) in the absolute and relative cases, respectively. To our knowledge, this is the first universality result of its kind in the literature and, somewhat surprisingly, it shows that an extra-gradient proxy step is not required to achieve optimal rates.

heading: 1 Introduction
text: This paper focuses on solving variational inequality problems of the form
Find x∗ ∈ Rd such that ⟨A(x∗), x− x∗⟩ ≥ 0 for all x ∈ Rd, (VI)
where A : Rd → Rd is a monotone cocoercive operator, i.e.,
⟨A(y)−A(x), y − x⟩ ≥ β∥A(y)−A(x)∥2 for some β > 0 and all x, y ∈ Rd. (CC)
The study of variational inequalities is a classical topic in optimization that provides a powerful and elegant unifying framework for a broad spectrum of “convex-structured” problems – including 35th Conference on Neural Information Processing Systems (NeurIPS 2021).
convex minimization, saddle-point problems, and games [6, 13]. In particular, such problems have recently attracted considerable attention in the fields of machine learning (ML) and data science because of their potential applications to generative adversarial networks [16], multi-agent and robust reinforcement learning [40], auction theory [47], and many other areas of interest where the minimization of a single empirical loss function does not suffice.
The golden standard for solving (VI) is provided by first-order methods: these methods can be run with computationally cheap updates that only require (noisy) access to A, so they are ideal for problems with very high dimensionality and moderate-to-low precision needs (as is typically the case in ML). More precisely, when A is monotone cocoercive as above, the min-max optimal convergence rate for solving (VI) is O(1/T ) after T oracle calls, and it is achieved by the extra-gradient / mirrorprox algorithm [25, 34] with Polyak-Rupert averaging [42]. However, this method requires access to a perfect oracle; if the method is run with an imperfect, stochastic first-order oracle, its convergence rate drops to O(1/ √ T ) [23], and this rate cannot be improved without additional assumptions [36]. One case where the O(1/ √ T ) convergence rate can be improved is when the underlying operator is strongly monotone – i.e., the RHS of (CC) is replaced by α∥y − x∥2 for some α > 0. In this case, we can obtain a fast O(1/T ) rate with a rapidly decreasing step-size [17]; however, this acceleration requires knowledge of the strong monotonicity modulus, and there is no known way to adapt to it. In particular, if a stochastic method that has been fine-tuned for strongly monotone operators is run on a merely monotone problem, its rate of convergence suffers a catastrophic drop to O(1/ log T ). These considerations naturally lead to two key research questions:
1. Are there any conditions for the method’s oracle that would close the stochastic-deterministic convergence gap outlined above?
2. Is it possible to design a class of methods that are capable of adapting to the quality of the oracle, and that achieve order-optimal rates without prior knowledge of the problem’s parameters?
Our contributions in the context of related work. Our goal in this paper is to provide a range of positive answers to the above questions, both in terms of the required oracle conditions, as well as methods that are able to gracefully interpolate between an O(1/T ) and an O(1/ √ T ) rate depending on the setting at hand.
With regard to the first question, our point of departure is the “relative noise” framework of Polyak [41], in which the variance of the oracle is upper bounded by the square norm of the operator at the queried point. This noise model is particularly relevant in coordinate descent methods for unconstrained problems as well as applications to control theory and signal processing where the operator is calculated based on actual, physical measurements that are only accurate up to a percentage of their true value. In recent applications to ML, this noise model has also been studied in the context of overparametrization [39], representation learning [51], and multi-agent learning [28]. Finally, this oracle model has also been studied under the umbrella of multiplicative noise [21] or growth conditions [8, 45, 48, 50], and it is known to improve the convergence rate of stochastic gradient algorithms with non-adaptive step-sizes, even in non-smooth problems [14].
With regard to the second question, we introduce a flexible first-order algorithmic template that includes as special cases the dual averaging [38], dual extrapolation [37] and optimistic gradient methods [43, 44], and which accounts for both adaptive and non-adaptive variants thereof. Our contributions can then be summarized as follows: 1. For oracles with bounded variance, we show that the proposed methods achieve an O(1/ √ T ) rate
of convergence if run with a non-adaptive, decreasing step-size.
2. In the relative noise model, this rate improves to O(1/T ), and it is achieved with a constant step-size that does need to be tuned as a function of T .
3. Finally, we provide an adaptive step-size rule that allows the method to achieve a fast, O(1/T ) rate under relative noise, and an order-optimal O(1/ √ T ) rate in the absolute noise case.
Importantly, our work shows that an extra-gradient mechanism is not required to obtain a fast O(1/T ) rate, as this can be achieved by vanilla dual-averaging methods with a constant step-size. This is an elegant consequence of the interplay between cocoercivity and the relative noise model; to the best of our knowledge, the only other work considering these models in tandem is the very recent paper [28].
Lipschitz Cocoercive + rel. noise
Vt Ergodic Last Iterate Ergodic Last Iterate
Adapt. dual averaging 0 1/ √ T [11] Unknown 1/T Asym. Adapt. dual extrapolation AXt + rel.noise 1/ √ T [44] Unknown 1/T Asym. Adapt. optimistic gradient AXt−1/2 + rel.noise 1/ √ T [12] Unknown 1/T Asym.
Table 1: The best known convergence rates in stochastic monotone VIs with our contributions highlighted in gray. Adaptive refers to our particular adaptive step-size choice in (Adapt). We obtain various schemes with particular choices of Vt. For the nomenclature, please refer to Section 3.2.
Our work closes several open threads in [28], which requires a vanishing relative noise level to obtain faster convergence in models with relative noise. A summary of our results in the context of related work can be found in Table 1, and we also elaborate on related work in greater detail in the paper’s appendix.

heading: 2 Problem setup and preliminaries
text: Examples and motivation. Throughout the sequel, we will focus on solving the variational inequality problem (VI). For completeness (and a certain degree of posterity), we briefly mention some examples below, and we defer to [13, 46] for a panoramic survey of the field.
Example 1 (Convex Minimization). If A = ∇f for some convex function f , the solutions of (VI) are precisely the minimizers of f .
Example 2 (Min-Max Problems). If A = (∇x1L,−∇x2L) for some convex-concave function L(x1, x2), then the solutions of (VI) coincide with the (global) saddle points of L. More precisely, x∗ = (x∗1, x ∗ 2) is a solution of (VI) if and only if it holds that
L(x∗1, x2) ≤ L(x∗1, x∗2) ≤ L(x1, x∗2) for all x1 ∈ X1, x2 ∈ X2. (SP)
In this case, (VI) is sometimes referred to as the “vector field formulation” of (SP).
Example 3 (Monotone games). Going beyond the min-max setting, a continuous game in normal form is defined as follows: First, consider a finite set of players N = {1, . . . , N}, each with their own action space Xi = Rdi . During play, each player selects an action xi from Xi with the aim of minimizing a loss ℓi(xi;x−i) determined by the ensemble x := (xi;x−i) := (x1, . . . , xN ) of all players’ actions. In this context, a Nash equilibrium is any action profile x∗ ∈ X that is unilaterally stable, i.e.,
ℓi(x ∗ i ;x ∗ −i) ≤ ℓi(xi;x∗−i) for all xi ∈ Xi and all i ∈ N . (NE)
The corresponding operator associated to the game is A(x) = (∇xiℓi(xi;x−i))i∈N . If A is monotone, then the game is itself called monotone, and its Nash equilibria coincide with the solutions of (VI), cf. [7, 13, 27, 30–33, 46] and references therein.
Regularity conditions. As we discussed in the introduction, our blanket regularity assumption for (VI) is that the defining operator A is β-cocoercive in the sense of (CC); for a panoramic overview of cocoercive operators we refer the reader to [6].
Some further comments for the cocoercivity condition are in order. First, one may easily observe that if A is β-cocoercive, it is also 1/β-Lipschitz. The converse does not hold for the general setting of operators; however, when A is the gradient of a smooth convex function, this is indeed the case [5]. Moreover, even though cocoercivity implies that A is monotone, it does not imply that it is strictly monotone – a condition which is usually invoked to ensure the existence and uniqueness of solutions to (VI). Therefore, to avoid pathologies, we make the following assumption for our setting:
Assumption 1. The set X ∗ = {x∗ ∈ Rd : x∗ is a solution of (VI)} is non-empty.
Together with cocoercivity, the existence of a solution will be our only blanket assumption in the sequel.
The gap function. With the above setup in hand, a widely used performance measure in order to evaluate a candidate solution of (VI) is the so-called restricted gap function:
GapC(x̂) = sup x∈C
⟨A(x), x̂− x⟩, (Gap)
where the "test domain" C is a non-empty compact subset of Rd. The motivation for this choice of merit function is that it characterizes the solutions of the (VI) via its zeros. Formally, we have the following: Proposition 1. Let C be a non-empty convex subset of Rd. Then, the following holds

heading: 1. GapC(x̂) ≥ 0, whenever x̂ ∈ C
text: 2. If GapC(x̂) = 0 and C contains a neighbourhood of x̂, then x̂ is a solution of (VI)
Proposition 1 is a generalization of an earlier characterization by Nesterov [37]; see also [2, 38] and references therein. Moreover, it provides a formal justification for the use of GapC(x̂) as a merit function for (VI). To streamline our presentation we defer the proof of the above proposition to the appendix.

heading: 3 The method

heading: 3.1 Oracle structure and profiles of randomness
text: From an algorithmic point of view, in order to solve (VI) we will use iterative methods that require access to a stochastic first-order oracle [36]. Formally, this is a black-box feedback mechanism which, when called at x, returns a random dual vector g(x;ω) with ω drawn from some (complete) probability space (Ω,F ,P). In practice, the oracle will be called repeatedly at a (possibly random) sequence of points generated by the algorithm at play. Therefore, once the iterate of the method is generated at each round, the oracle draws an i.i.d. sample ω ∈ Ω and returns a dual vector:
g(x;ω) = A(x) + U(x;ω) (1) with U(x;ω) denoting the "measurement error".
In this general setting, we make the following statistical assumptions for the oracle: Assumption 2 (Absolute noise). The oracle g(x;ω) enjoys the following properties:
1. Almost sure boundedness: There exists some strictly positive numbers M > 0 such that: ∥g(x;ω)∥∗ ≤ M almost surely (2)
2. Unbiasedness: E [g(x;ω)] = A(x) 3. Bounded absolute variance: E [ ∥U(x;ω)∥2∗ ] ≤ σ2
Such type of conditions for the oracle are standard, especially in the context of adaptive methods cf. [1, 4, 24, 26]. Also, because the variance of the noise is independent of the value of the operator at the queried point, this type of randomness in the oracle will be called absolute.
By contrast, following Polyak [41], the relative noise model is defined as follows: Assumption 3 (Relative noise). The oracle g(x;ω) enjoys the following properties:
1. Almost sure boundedness: There exists some strictly positive numbers M > 0 such that: ∥g(x;ω)∥∗ ≤ M almost surely
2. Unbiasedness: E [g(x;ω)] = A(x)
3. Bounded relative variance: There exists some positive c > 0 such that: E [ ∥U(x;ω)∥2∗ ] ≤ c∥A(x)∥2∗ (3) Assumption 2 is standard for obtaining the typical O(1/ √ T ) convergence rate for stochastic optimization scenarios (see for example [23, 35] and references therein). That said, Assumption 3 will prove itself as the crucial statistical condition that will allow us to recover the well known order-optimal bound O(1/T ) for deterministic settings. For concreteness, we provide an example below:
Example 4 (Random coordinate descent). Consider a smooth convex function f over Rd, as per Example 1. Then the randomized coordinate descent (RCD) algorithm draws one coordinate it at random at each stage, and calculates the partial derivative vi,t = ∂f/∂xit . Subsequently, the i-th derivative is updated as Xi,t+1 = Xi,t − dγtvi,t. This update rule can be written in abstract recursive form as x+ = x − g(x;ω) where gi(x;ω) = d · ∂f/∂xi · ω and ω is drawn uniformly at random from the set of basis vectors {e1, . . . , ed} of Rd. Clearly, E[g(x;ω)] = ∇f(x) by construction; moreover, since ∂f/∂xi = 0 at the minimum points of f , we also have g(x∗;ω) = 0 whenever x∗ is a minimizer of f – i.e., the variance of the estimator g(x;ω) vanishes at the minimum points of f . It is then straightforward to verify that E[∥v̂(x)−∇f(x)∥2] = O(∥∇f(x)∥2), which is precisely the relative noise condition for A = ∇f .

heading: 3.2 The methods
text: We now present the generalized extra-gradient (GEG) family of algorithms. More precisely, given two sequences of dual vectors Vt and Vt+1/2, (GEG) is given by the following recursive formula:
Xt+1/2 = Xt − γtVt Yt+1 = Yt − Vt+1/2 Xt+1 = γt+1Yt+1
(GEG)
Heuristically, the machinery behind (GEG) suggests to first generate a leading state Xt+1/2 by taking a step along Vt, then aggregate the vector Vt+1/2 observed at the leading state by incorporating the second dual sequence Vt+1/2 and finally update the method by applying a dual averaging step [38, 49]. This idea is well-known in the literature of extra-gradient methods [25, 34, 37]. However, up to this point, we have not assumed anything particular for the sequences of Vt and Vt+1/2, except that they are dual vectors (but not necessarily queries of a stochastic oracle). This generic choice is the building block that will allow us to include various popular algorithmic schemes and provide a unified framework fo their analysis.
To begin with, we provide the following examples that illustrate the fact that Dual Averaging, Dual Extrapolation and Optimistic Dual Averaging can all be written in the form of (GEG) under different choices of Vt and Vt+1/2.
Example 5. Stochastic Dual Averaging [38]: Consider the case Vt ≡ 0 and Vt+1/2 ≡ gt+1/2 = A(Xt+1/2) + Ut+1/2. Then, this yields that Xt+1/2 = Xt and hence gt+1/2 = gt = Vt+1/2. Therefore, (GEG) reduces to the dual averaging scheme:
Yt+1 = Yt − gt Xt+1 = γt+1Yt+1
(DA)
Example 6. Stochastic Dual Extrapolation [37]: Consider the case now where Vt ≡ gt = A(Xt)+Ut and Vt+1/2 ≡ gt+1/2 = A(Xt+1/2)+Ut+1/2 are noisy oracle queries at Xt and Xt+1/2 respectively. Then (GEG) readily yields Nesterov’s dual extrapolation method [37]:
Xt+1/2 = Xt − γtgt Yt+1 = Yt − gt+1/2 Xt+1 = γt+1Yt+1
(DE)
Example 7. Stochastic Optimistic Dual Averaging [19, 20, 43, 44]: Consider the case Vt ≡ gt−1/2 = A(Xt−1/2) + Ut−1/2 and Vt+1/2 ≡ gt+1/2 = A(Xt+1/2) + Ut+1/2 are the noisy oracle feedback at Xt−1/2 and Xt+1/2 respectively. We then get the optimistic dual averaging method:
Xt+1/2 = Xt − γtgt−1/2 Yt+1 = Yt − gt+1/2 Xt+1 = γt+1Yt+1
(OptDA)
The next crucial step is to provide the key ingredient that will allow us to unify the approach for all algorithms belonging to the family (GEG). This is done by a shared “energy” inequality satisfied by all (GEG)-type schemes. Formally, this is described by the following proposition:
Proposition 2. Assume that Xt, Xt+1/2 are the iterates of (GEG) run with a non-negative, nonincreasing step-size γt. Then, for all x ∈ Rd the following inequality holds:
T∑ t=1 〈 Vt+1/2, Xt+1/2 − x 〉 ≤ ∥x∥ 2 2γT+1 + 1 2 T∑ t=1 γt ∥∥Vt+1/2 − Vt∥∥2∗− 12 T∑ t=1 1 γt ∥∥Xt+1/2 −Xt∥∥2 (4) Proving Proposition 2 requires tiresome computations, so we defer it to the paper’s supplement. Instead, we conclude this section by illustrating the various method-specific template inequalities:
1. (Stochastic Dual Averaging): For Vt+1/2 = gt+1/2 and Vt = 0, then (4) becomes:
T∑ t=1 ⟨gt, Xt − x⟩ ≤ ∥x∥2 2γT+1 + 1 2 T∑ t=1 γt ∥Vt∥2∗ (5)
2. (Stochastic Dual Extrapolation): For Vt = gt for all t = 1, 2, . . . then (4) becomes:
T∑ t=1 〈 gt+1/2, Xt+1/2 − x 〉 ≤ ∥x∥ 2 2γT+1 + 1 2 T∑ t=1 γt ∥∥gt+1/2 − gt∥∥2∗ − 12 T∑ t=1 1 γt ∥∥Xt+1/2 −Xt∥∥2 (6)
3. (Stochastic Optimistic Dual Averaging): For Vt = gt−1/2 and Vt+1/2 = gt+1/2 then (4) becomes:
T∑ t=1 〈 gt+1/2, Xt+1/2 − x 〉 ≤ ∥x∥ 2 2γT+1 + 1 2 T∑ t=1 γt ∥∥gt+1/2 − gt−1/2∥∥2∗−12 T∑ t=1 1 γt ∥∥Xt+1/2 −Xt∥∥2 (7)

heading: 4 Non-adaptive Analysis
text: In this section, we derive a series of tight convergence rates for (GEG) under both oracle/noise profiles but with a non-adaptive step-size sequences. Due to space constraints, we defer the full analysis to the appendix; however, we provide here a proof sketch of our main results via an appropriate “energy inequality” in Proposition 2.

heading: 4.1 Absolute random noise
text: In the context of monotone VIs, assumptions induced by the random oracle model are common and well-understood. Indeed, for the general case of bounded variance, i.e., E [ Ut+1/2|Ft+1/2 ] ≤ σ, extra-gradient/mirror-prox is known to converge at a rate O(1/ √ T ) [22], with a decreasing step-size of order O(1/ √ t).
For completeness, we analyze (GEG) under a random oracle profile, i.e., for Vt+1/2 = gt+1/2 ≡ g(Xt+1/2;ωt+1/2) satisfying Assumption 2 and Vt being an almost surely bounded sequence of dual vectors. To that end, we employ a decreasing step-size choice, which is summarized in the next theorem. Theorem 1. Let Xt, Xt+1/2 be generated by (GEG) with a decreasing step-size γt = O(1/ √ t).
Then, for every compact neighborhood C ⊂ Rd of x∗, with X̄T = 1T ∑T t=1 Xt+1/2, it holds that:
E [ GapC ( X̄T )] = O(1/ √ T ).
The arguments for the proof of Theorem 1 are standard and we defer them to the appendix due to space constraints. Thanks to this result, we can now derive the respective method specific rates as special instances. More precisely, we have the following proposition:
Proposition 3. Under Assumption 2 the iterates of (DA), (DE), (OptDA) enjoy the following rate: E [ GapC ( X̄T )] = O(1/ √ T ) (8)

heading: 4.2 Relative random noise
text: We now turn our attention to the relative random oracle framework, i.e. Vt+1/2 = gt+1/2 satisfying Assumption 2 along with:
E [ ∥Vt∥2∗|Ft ] ≤ c∥A(Xt)∥2∗ for all t = 1, 1/2, . . . (9)
In particular, with a carefully chosen constant step-size, under the additional assumption of relative variance, it is possible to achieve an accelerated rate of O(1/T ). One needs to depart from the standard approach to fully exploit the problem setting, i.e., cocoercivity and relative variance. Essentially, it amounts to ensuring that ∑T t=1 ∥At∥2∗ and ∑T t=1 ∥At+1/2∥2∗ are summable. We present our result under the respective setting with a proof sketch that highlights its main ingredients. Theorem 2. Let Xt, Xt+1/2 be generated by (GEG) with a constant step-size that satisfies
min { (2L)−1, (4L2γ)−1 } − 2γc > 0 with L = 1/β. (10)
Then, for every compact neighbourhood C ⊂ Rd of x∗, with X̄T = 1T ∑T t=1 Xt+1/2, we have:
E [ GapC ( X̄T )] = E [ sup X∈C 〈 A(X), X̄T −X 〉] = O(1/T )
Proof. With a constant step-size, Proposition 2 implies T∑
t=1
〈 Vt+1/2, Xt+1/2 −X 〉 = ∥X∥2
2γ +
γ
2 T∑ t=1 ∥Vt+1/2 − Vt∥2 − 1 2γ T∑ t=1 ∥Xt −Xt+1/2∥2
We show that using smoothness and cocoercivity of the operator, along with the relative noise condition,(
min { (2L)−1, (4L2γ)−1 } − 2γc ) T∑ t=1 ( E [ ∥A(Xt)∥2 ] + E [ ∥A(Xt+1/2)∥2 ]) ≤
E [ ∥X∥2 ] γ
If constant step-size γ satisfies Eq. (10), then there exists some strictly positive real number β, such that E [∑T t=1 ( ∥A(Xt)∥2 + ∥A(Xt+1/2)∥2 )] ≤ E [ ∥X∥2/βγ ] < +∞, which concludes that both∑T
t=1 ∥At∥2∗ and ∑T
t=1 ∥At+1/2∥2∗ are summable. Using the same arguments as in the proof of Theorem 1, we obtain an upper bound for the gap,
E [ GapC(X̄T+1/2) ] ≤ D2
2γ + 2γc ∑T t=1 E [ ∥A(Xt+1/2)∥2 + ∥A(Xt)∥2 ] + √∑T t=1 E [∥∥Vt+1/2∥∥2∗] T .
By relative variance and summability of operators, E [ GapC(X̄T+1/2) ] = O(1/T )
□
Similar to the setting of absolutely random noise, Theorem 2 implies algorithm-specific convergence bounds, which are presented below: Proposition 4. Under Assumption 3 the iterates of (DA), (DE), (OptDA) enjoy the following rate:
E [ GapC ( X̄T )] = O(1/T ) (11)
An extra appealing feature of the above is that we are able to derive an asymptotic last iterate trajectory result, i.e., the asymptotic convergence of the iterates themselves before any averaging occurs, almost surely. More precisely, we have the following proposition: Proposition 5. Under Assumption 3 the iterates of (DA), (DE), (OptDA) converge to a (VI) solution x∗.
The proof Proposition 5 relies on the fact that the distance of the iterates towards any solution of (VI) is decreasing almost surely along with the fact that the summability of ∥A(Xt)∥2∗ guarantees that every limit point of the iterate is also a solution of (VI). To streamline our presentation, we defer the detailed proof to the appendix.

heading: 5 Adaptive Analysis
text: By the results of Section 4, one may easily observe the interplay between the O(1/ √ T ) to O(1/T ) convergence rates under different noise profiles and step-sizes policies. Therefore a natural question that arises from this context is the following:
Can we derive a universal step-size policy that is able to optimally adjust the performance of (GEG) without any prior knowledge of the oracle’s noise profile?
In what follows, this desired property is achieved by running (GEG) with the following adaptive step-size:
γt = 1√
1 + ∑t−1 j=1∥Vj − Vj+1/2∥2∗ (Adapt)
The step-size (Adapt) is inspired by [44]; however, in our analysis, we provide a generalized point of view which does not assume that Vt necessarily is the oracle query at the respective points as in [44]. This allows us to include in the (Adapt) formulation all the adaptive sttep-sizes typically used for the archetypical schemes introduced in Section 3 . More precisely, we have:
1. Adaptive Stochastic Dual Averaging: For Vt ≡ 0 (Adapt) becomes the standard AdaNorm stepsize, studied in various works [11, 29]:
γt = 1√
1 + ∑t−1 j=1∥gj∥2∗ (12)
2. Adaptive Stochastic Dual Extrapolation: For Vt = gt+1/2 (Adapt) becomes
γt = 1√
1 + ∑t−1 j=1∥gj − gj+1/2∥2∗ (13)
as used in, e.g., [3, 44, 47]. 3. Adaptive Stochastic Optimistic Dual Averaging:. For Vt = gt−1/2 (Adapt) becomes the step-size
used in [19, 20]:
γt = 1√
1 + ∑t−1 j=1∥gj+1/2 − gj−1/2∥2∗ (14)
Section 4, heuristically suggests that the success of γt should hinge on a simultaneous performance as 1/ √ t for the absolute random oracle feedback and as a constant one. whenever the relative random feedback kicks in. This important interpolation feature is what will show in thhe sequel.

heading: 5.1 Absolute random noise
text: We will first treat oracles subject to absolute random nooise. In this case, we have: Theorem 3. Assume that Xt, Xt+1/2 are the iterates of (GEG) run with the step-size (Adapt). Then, for every compact neighborhood C ⊂ Rd of a solution x∗ of (VI), we have:
E [ GapC(XT ) ] = O(1/ √ T ) (15)
with XT = (1/T ) ∑T t=1 Xt+1/2
As we argued above, the result of Theorem 3 is heuristically justified by the fact that the almost sure boundedness conditions for the sequences:
∥Vt∥∗ ≤ M almost surely for all t = 1, 1/2, . . . (16)
yields that γt = Ω(1/ √ t). In particular, Theorem 3 yields the following specific convergence guarantees: Proposition 6. Under Assumption 2 the iterates of (DA), (DE), (OptDA) enjoy the following:
E [ GapC(XT ) ] = O(1/ √ T ) (17)

heading: 5.2 Relative random noise
text: Under the relative random noise conditions, we can obtained the following improved rate O (1/T ) instead of the O(1/ √ T ) rate above. Formally, we have the following result:
Theorem 4. Assume that Xt, Xt+1/2 are the iterates of (GEG) run with the step-size (Adapt). Then, for every compact neighborhood C ⊂ Rd of a solution x∗ of (VI), we have:
E [ GapC(XT ) ] = O (1/T ) (18)
with XT = 1/T ∑T t=1 Xt+1/2
The crucial ingredient for the proof of Theorem 4 consists of showing that the adaptive step size stabilizes to a positive constant γ∞ > 0. In order to obtain this, the first step is to show that the template inequality of Proposition 2 yields
E [ 1
γ2T+1
] ≤ ( 8c max { L, 2L2 }(∥x∗ − x1∥2 2 + 2G2 + 1 ) + 1 ) E [ 1
γT+1
] (19)
Moreover, due to the definition of (Adapt) and Jensen’s inequality we have:
E [ 1
γT+1
] = E  √√√√1 + T∑
t=1
∥Vt − Vt+1/2∥2
 ≤ √√√√E[1 + T∑
t=1
∥Vt − Vt+1/2∥2 ] = √ E [ 1
γ2T+1 ] (20)
Therefore, after combining (19) and (20) we get that E [
1 γ2T+1
] < +∞. This directly implies (by the
monotone convergence theorem) that:
1
γ2T+1 = 1 + T∑ t=1 ∥Vt − Vt+1/2∥2∗ < +∞ almost surely (21)
which in turn yields that ∑T
t=1∥Vt − Vt+1/2∥2∗ is summable almost surely. Therefore due to the definition of γt we have almost surely the following:
γT+1 = 1√
1 + ∑T t=1∥Vt − Vt+1/2∥2∗ → 1√ 1 + ∑+∞ t=1∥Vt − Vt+1/2∥2∗ = γ∞ > 0 (22)
Finally, we conclude by providing the following the respective method specific result. Formally, we have: Proposition 7. Under Assumption 3 the iterates of (DA), (DE), (OptDA) enjoy the following:
1. The convergence rate in terms of the restricted gap function for the time-average: E [ GapC(XT ) ] = O(1/T ) (23)
2. Their last iterate trajectory converges to a (VI) solution x∗ almost surely.
The last iterate convergence result of Proposition 7 refers to the asymptotic convergence of the actual sequences of the methods-before any averaging takes place- and it hinges on the fact that the (random) sequences ∥Vt − Vt+1/2∥2∗ and ∥A(Xt)∥2∗ are summable with probability 1. Having established this, we show that Xt satisfies is a (stochastic) quasi-Fejér sequence [9] (with respect to the solution set X ∗) along with the fact that every limit point of Xt belongs to X ∗. These two building blocks are sufficient in order to derive the almost sure convergence of the iterate’s trajectory.

heading: 6 Numerical experiments
text: In this section we validate and explore the consequences of the theoretical results. We adopt the experimental setting considered in [15] which is a particular instance of the Kelly auction with N = 4. In its generality in a single resource Kelly auction, there are N players sharing a total
amount of Q ∈ R>0 resources. At every round, each bidder, p, submits a bid xp ∈ R≥0 and receives proportional resources, ρp = Qx p Z+ ∑ p x p , where Z is the auction entry price. The payoff for player p is then given as up(xp;x−p) = Gpρp − xp, where Gp is the marginal gain in utility for player p. One can easily verify that the vectorfield associated with the payoff functions is cocoercive. In addition, the assumption of relative noise can be justified since each player can be seen as performing a measurement when querying the payoff. In such settings, it is common to assume that the error is proportional to the measured quantity and this uncertainty propagates to the gradient information in the form of relative noise. Since players act without communication in this example, it is particularly important that our results extends to single-call extragradient variants (see for instance [44] for elaboration). However, note that our proposed adaptive step-size (Adapt) still relies on global information of all players so our non-adaptive results for known problem constants is also important for this example.
In order to simulate the presence of relative noise we add a term proportional to the norm of the operator. In our notation we can thus capture both relative noise and absolute noise through the error term Ut in the following way,
Ut = ϵrel∥A(Xt)∥+ ϵabs, (24)
where ϵrel ∼ N (0, σ2rel) and ϵabs ∼ N (0, σ2abs). To validate the convergence rate we compute the optimal strategy in the deterministic setting (i.e. σrel = σabs = 0) using Mathematica.
In Fig. 1 we illustrate the behavior of the different instantiations of our algorithmic template under different choices of σrel and σabs. To denote (DA), (DE) and (OptDA) we use DualAvg, DualX and DualOpt respectively. In addition we include optimistic gradient (OG) from [10] for comparison. For higher dimensional experiments see the appendix, where we additionally apply our adaptive method to the non-convex problem of learning a covariance matrix [10, 18].

heading: 7 Concluding remarks
text: In this paper we provide rate interpolation guarantees for different noise profiles; namely that of absolute and relative random noise. That being said our analysis crucially depends on the cocoercivity of the associated operator that defines the respective (VI). It thus remains open whether it is possible to achieve the same O(1/T ) rate for monotone (VI) by only assuming Lipschitz continuity of the said operator and relative noise. Moreover, an additional interesting direction for future research is investigate the impact of relative noise for adaptive accelerated methods and whether it is possible to recover the iconic O(1/T 2) rate. We postpone these questions to the future.
Acknowledgments and Disclosure of Funding
This research was partially supported by the COST Action CA16228 “European Network for Game Theory” (GAMENET) and the French National Research Agency (ANR) in the framework of the “Investissements d’avenir” program (ANR-15-IDEX-02), the LabEx PERSYVAL (ANR-11-LABX-0025-01), MIAI@Grenoble Alpes (ANR-19-P3IA-0003), and the grant ALIAS (ANR-19-CE48-0018-01). On the EPFL side, this project has also 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), the Hasler Foundation Program: Cyber Human Systems (project number 16066), and the Swiss National Science Foundation (SNSF) under grant number 200021178865/1. This project was sponsored by the Department of the Navy, Office of Naval Research (ONR) under grant number N62909-17-1-2111, and the Army Research Office under Grant Number W911NF-19-1-0404.

Review summaries:
The paper gives an algorithmic framework of generalized extragradient method for solving variational inequalities induced by a cocoercive operator A. The framework casts dual averaging, dual extrapolation as special cases, and interpolates between the convergence rate of O(1/sqrt{T}) and O(1/T) for different noise levels assuming a stochastic oracle of A(x). They also provide an adaptive variant of their methods that obtain the same rate without needing to know the explicit problem parameters. Finally, they corroborated their results by some preliminary experiments to show that the convergence and corresponding rates under different noise levels. 

In this paper, the authors studied solving for variational inequality with monotone cocoercive operator. Two noise models on the oracle are introduced, and a generalized extra-gradient (GEG) family of algorithms are analyzed, encompassing some known algorithms in the literature. In the case of non-adaptively chosen stepsize, convergence rates of $O(1/\sqrt{T})$ and $O(1/T)$ are given for the two noise models. Another class of adaptive-stepsize schemes (somewhat resembling Adagrad type of choice) are studied that can automatically adjust for the stepsize to achieve similar type of convergence without knowledge of the noise structure. Numerical experiments are also conducted on a set of synthetic examples.

This paper proposes universal adaptive stochastic gradient-based methods for variational inequalities.  There are at least three remarkable contributions. Firstly, it unifies several popular dual averaging algorithms, including stochastic dual averaging, stochastic dual extrapolation, and stochastic optimistic dual averaging. Secondly, with an AdaGrad-type stepsize that is parameter-free, the algorithms achieve an $O(1/\sqrt{T})$ complexity (for the restricted gap) when the stochastic gradients have absolutely bounded variances and an $O(1/T)$ complexity when the the stochastic gradients have relatively bounded variances, without tweaking the hyperparameters. This gives universal and adaptive algorithms. Lastly, the paper shows the asymptotic convergence of the last iterate, which is usually the output in practice.