Sifting through the noise: Universal first-order methods for stochastic variational inequalities
Authors: Kimon Antonakopoulos
Thomas Pethick
Ali Kavis
Panayotis Mertikopoulos
Volkan Cevher
Venue: NeurIPS 2021 Poster (2021)
Keywords: monotone variational inequalities
stochastic variational inequalities
adaptive methods
improved rates

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: $\mathcal{O}(1/\sqrt{T})$ for absolute noise profiles, and $\mathcal{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 $\mathcal{O}(1/\sqrt{T})$ and $\mathcal{O}(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.

Sifting through the Noise: Universal First-Order Methods for Stochastic Variational Inequalities
Kimon Antonakopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG 38000 Grenoble, France kimon. aatcoaatoooullos@mmii....f..
Thomas Pethick
Ali Kavis
École Polytechnique Fédérale de Lausanne (EPFL)
thomas. pethi ck@epfl. ch ali Ali.kkvis@epf..o ch
Panayotis Mertikopoulos
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG 38000 Grenoble, France & Criteo AI Lab
fr
Volkan Cevher
École Polytechnique Fédérale de Lausanne (EPFL.)
volkan, volkan. www.ereepeeeeccceee
Abstract
We examine flexible algorithmic framework for solving monotone variational inequalities the presence of randomness and uncertainty. The proposed tem- plate encompasses 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(IVTT) for absolute noise profiles, and (1/TT) for relative ones. Subsequently,
drop all prior knowledge requirements (the ab- solute/relative variance of the randomness affecting the problem. the operator's 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/VI 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- stra-ggradeet proxy step is not required to achieve optimal rates.
Introduction
This paper focuses on solving variational inequality problems of the form d such that (A(x"), x - x²) 2 for x E IRd,
Find
(VI)
where A: Idd + dd is a monotone cocoercive operator, i.c.,
(A(y) A(x). - 2 Al)( A(+) for some and all x, E Idd
(CC)
The study of variational inequalities classical topic in optimization that provides a powerful and elegant unifying framework for a broad spectrum of "convex- -trueex-ttuucuuee"" problems including
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

convex minimization, saddle-point problems, and games [6, 13]. In particular, such problems have recently attracted considerable attention 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 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 typically the case in ML). More precisely, when A is monotone cocoercive as above, the min-max optimal convergence rate for solving (VI) is (1/TT) after T oracle calls, and it is achieved by the extra- carra-grrdiett /miror- 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 ((1/VT) [23], and this rate cannot be improved without additional assumptions [36].
prox algorithm [25, 34] with Polyak-
One case where the (L)/VT) convergence rate can be improved is when the underlying operator is strongly monotone i..., the RHS of (CC) is replaced by ally - z21² for some a >> O. In this case, we can obtain fast (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 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 (11 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- 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 '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 gracefully interpolate between an (1/"T) and an (L/vTT) 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 percentage of their true value. In recent applications to MI., 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 multiplccative 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 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 (LIVVT) rate of convergence if run with a non-adaptive, decreasing step-size.
2. In the relative noise model, this rate improves to O(ITT), and it is achieved with constant step-size that does need to be luned as a function of T.
3. Finally, we provide an adaptive step-size rule that allows the method achieve a fast, O(1TT) rate under relative noise, and an order-optimal (1/VT) rate in the absolute noise case.
Importantly, our work shows that an extra-gradient mechanism is not required to obtain a fast O11/T) rate, as this can be achieved by vanilla avel-averg methods with 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
V2
Ergodic
Last Iterate
Ergodic
Last Iterate
Adapt. dual averaging
0
1/vT [11]
Unknown
1/T
Asym.
Adapt. dual extrapolation
AX: + rel.noise
1/vT [44]
Unknown
1/T
Asym.
Adapt. optimistic gradient
AX, 1/2 + rel. noise
1/VT [12)
Unknown
1/T
Asym.
Table 1:
The best known convergence rates in stochastic monotone VIs with contributions highlighted in gray. Adaptive refers to our particular adaptive step-size choice (Adapt). We obtain various schemes with particular choices of Vi. For the nomenclature, please refer to Section 3.2.
Our work closes several open threads in [28], which requires vanishing relative noise level to obtain faster convergence models with relative noise. A summary our results in the context related work can be found in Table 1, and we also elaborate on related work in greater detail in the paper's appendix.
Problem setup and preliminaries
Examples and motivation. Throughout the sequel, we will focus on solving the variational inequality problem (VI). For completeness (and a certain degree of posterity), briefly mention some examples below, and we defer to [13, 46] for a panoramic survey of the field.
Example (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 = L. for some convex-concave function [ 22), then the solutions of (VI) coincide with the (global) saddle points of L. More precisely, x² = (xj, 25) is a solution of (VI) if and only if it holds that
L( x2) S [a S a5) for all 21 E X4, E X2
(SP)
In this case, (VI) is sometimes referred to as the "vector field formulation" of (SP).
Example (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 {l...., N), each with their own action space X; = Rd, During play, each player selects an action 2; from X; with the aim of minimizing loss (x;;; xx) determined by the ensemble players' actions. In this context, a Nash equilibrium is any action profile xx E X that unilaterally stable, i.e.,
".1,..-,,NN of all
(<1:=<)) S ((0;)_L)) for all E X; and all E.
(NE)
The corresponding operator associated to the game is A(x) = (V,44(xx=-i) If A monotone, then the game is itself called monotone, and its Nash equilibria coincide with the solutions (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 8-cocoercive in the sense of (CC); for panoramic overview of cocoercive operators we refer the reader to [6].
Some further comments for the cocoercivity condition are order. First, one may easily observe that if /-cocoercive,, it is also 1/8-Lipschitz. The converse does not hold for the general setting of operators; however, when 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 is strictly monotone a condition which is usually invoked to ensure the existence and uniqueness of solutions (VI). Therefore, avoid pathologies, we make the following assumption for setting:
Assumption 1. The set x {a* E Rd x² is solution of (VI)) non-empty.
Together with cocoereivity, the existence of 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 candidate solution of (VI) is the so-called restricted gap function:
G (up(A(x), 2).
(Gap)
=EC
where the "test domain" is a non-empty compact subset of R 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 non-empty convex subset TR.. Then, the following holds
1. (ē) 2 0, whenever i E
2. Gape ④ = 0 and C contains neighbourhood of ê, then & is a solution of (VI)
Proposition 1 is generalization of earlier characterization by Nesterov [37]; see also [2, 38) and references therein. Moreover, provides a formal justification for the use of Gapc as a merit function for (VI). To streamline presentation we defer the proof of the above proposition to the appendix.
The method
3.1
Oracle structure and profiles of randomness
From algorithmic point of view, in order to solve (VI) we will use iterative methods that require access to stochastic first-order oracle [36]. Formally, this is black-box feedback mechanism which, when called returns random dual vector g w) with drawn from some (complete) probability space F, 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 w E S and returns a dual vector:
g( w) A(x) ((;w)
with U (z; denoting the "measurement error".
In this general setting, we make the following statistical assumptions for the oracle: Assumption (Absolute noise). The oracle g( w) enjoys the following properties:
1. Almost sure boundedness: There exists some strietly positive numbers M > 0 such that: (19( S M almost surely
2. Unbiasedness: E [g([w))] A(x)
3. Bounded absolute variance: E [[;((])))]3]]] 5²
Such type of conditions for the oracle standard, especially in the context of adaptive methods ef. [1, 4, 24, 26]. Also, because the variance of the noise is independent the value the operator at the queried point, this type of randomness the oracle will be called absolute.
By contrast, following Polyak [41], the relative noise model defined as follows:
Assumption 3 (Relative noise). The oracle g(z;w) enjoys the following properties:
1. Almost sure boundedness: There exists some strictly positive numbers M > 0 such that: (o(x:))]] < MM almost surely
Unbiasedness: [g(x; [)]] A(z)
Bounded relative variance: There exists some positive > 0 such that:
E [1;(w= < cl)A(=))1
Assumption 2 standard for obtaining the typical ((IvT)) convergence rate for stochastic optimiza- tion 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 O1/TT) for deterministic settings. For concreteness, provide example below:

---

Example 4 (Random coordinate descent). Consider a smooth convex function f over R", as per Example Then the randomized coordinate descent (RCD) algorithm draws one coordinate é, at random at each stage, and calculates the partial derivative Us,t = 0s /ax.. Subsequently, the i-th derivative is updated as Xi,++1 Xi, - d
This update rule can be written in abstract recursive form as x+ = x - g(;; w) where g.(2;a) w) = d- /0/ and w is drawn uniformly at random from the set of basis vectors (E ed) of Vf(xx) by construction; moreover, since /0r; 0 the minimum points of f. we also have g(=":w) = 0 whenever x" is a minimizer of f i.e. the variance of the estimator (2;; w) vanishes at the minimum points of f. It is then straightforward to verify that [[] - V (())) = ( V (x))))), which is precisely the relative noise condition for A V..
R. Clearly, E[g(æ;w)]
3.2 The methods
We now present the generalized extra-gradient (GEG) family of algorithms. More precisely, given two sequences of dual vectors V/2 and V/+1/2, (GEG) is given by the following recursive formula:
X X X; %
Y41 YY, V
(GEG)
X1+1 V++11++1
Heuristically, the machinery behind (GEG) suggests to first generate a leading state X by taking step along Ve, then aggregate the vector V1+1/2 observed at the leading state by incorporating the second dual sequence V/+1/2 and finally update the method by applying dual averaging step [38, 49]. This idea is well-known in the literature of extra- estra-gradient methods [25, 34, 37]. However, up to this point, we have not assumed anything particular for the sequences of V2 and 1/+ except that they are dual vectors (but not necessarily queries of stochastic oracle). This generic choice the building block that will allow us to include various popular algorithmic schemes and provide unified framework 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 V2 and V/-1/2-
Example 5. Stochastic Dual Averaging [38]: Consider the case V = 0 and V4+1/2 = 9t+1/2 = A(X(+1/2) + Ut41/2- Then, this yields that X = X₂ and hence 9++1/2 = 9t V2+1/2
Therefore, (GEG) reduces to the dual averaging scheme:
Y++ = Y 9t
(DA)
X = 7+41 Y++1
Example 6. Stochastic Dual Extrapolation [37]: Consider the case now where V, 9t A(X,) + U, and V/+1/2 = 9c+1/2 A(Xx+1/2) -U+112 are noisy oracle queries at X, and Xt+1/2
respectively. Then (GEG) readily yields Nesterov's dual extrapolation method [37]:
X Xt 7t9
Y41 Y, 91+1/2
(DE)
X(41 7
Example 7. Stochastic Optimistic Dual Averaging [19, 20, 43, 44]: Consider the case Vi-
9t-1/2 = A(X,-1/2) + U,-1/2 and V = 9t+1/2 = =A(x+11/2) + U/+1/2 are the noisy oracle
feedback at X,-1/2 and X2+1/2 respectively. We then get the optimistic dual averaging method:
X,-1/2 = X,-71th 1/2
Y441 Y -,,-0+112
(OptDA)
Xx+1 7++1
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 shared "energy" inequality satisfied by all (GEG)-type schemes. Formally, this is described by the following proposition:
5

---

Proposition 2. Assume that Xt, 11+1/2 are the iterates of (GEG) run with non-negative, non- increasing step-size ?/t. Then, for all x E IR the following inequality holds:
22
T Te VV+1122 - -
T - Σ
(V1+1/2; X - x)s S
X X, (4)
2
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-specifie template inequalities:
1. (Stochastic Dual Averaging): For V++1/2 9t+1/2 and V = 0, then (4) becomes:
T
|
T
gg Xx - x)
m
(5)
2TT+1
2
1=1
2. (Stochastic Dual Extrapolation): For Vi = 9t for all t = 1,,,...
then (4) becomes:
( -x) x)
|
+
1
Yt g++1/2
9i 1
X Xxll
2
(6)
3. (Stochastic Optimistic Dual Averaging): For V₁ = 9h- and Ve+1/2 9++ 1/2 then (4) becomes:
T
|x
1
T
1
T
X441//2 - x² x
|19 9t-1/2
X1+1/2 Xell
2YT+1 2
2
1=1
1=1
4 Non-adaptive Analysis
In this section, we derive a series of tight convergence rates for (GEG) under both oracle/noise profiles but with non-adaptive step-size sequences. Due to space constraints, we defer the full analysis to the appendix; however, provide here proof sketch of our main results via an appropriate "energy inequality" in Proposition
4.1 Absolute random noise
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 [V++1/alFe+1/2] I a, patra-gradden//mirrr-proo known to converge rate O(IvVT) [22], with decreasing step-size of order (1/vi).
For completeness, we analyze (GEG) under a random oracle profile, i.e., for V/41/2 = 9r+1/2 = g(X++1/2: (22 satisfying Assumption and V₁ being an almost surely bounded sequence of dual vectors. To that end, we employ decreasing step-size choice, which is summarized in the next theorem.
Theorem 1. Let Xt, be generated by (GEG) with a decreasing step-size " = O(IVV).
Then, for every compact neighborhood C TR, x² with X, + E X441/2 it holds that:
E Gape (X+) O(IVVT).
The arguments for the proof of Theorem are standard and defer them the appendix due to space constraints. Thanks to this result, we can now derive the respective method specific rates as special instances. More precisely, have the following proposition:
Proposition 3. Under Assumption 2 the iterates of (DA), (DE), (OptDA) enjoy the following rate:
E [aape (Xr)) (LI/VT)

---

4.2 Relative random noise
We now turn our attention to the relative random oracle framework, i.e. V2+1/2 1/2 satisfying Assumption 2 along with:
E [ & clIA(x))l for all t t= 1,1/2....
In particular, with a carefully chosen constant step-size, under the additional assumption of relative variance, is possible to achieve an accelerated rate of (1/TT). 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 Σx | and Σ || ||++1/2 are summable. We present our result under the respective setting with a proof sketch that highlights its main ingredients.
Theorem 2. Let X,, Xx+1/2 be generated by (GEG) with constant step-size that satisfies
min ((L)(2 (4I2 - 27. >> O with L 1/8.
(10)
Then, for every compact neighbourhood C C Rdd of x², with Xy Ei= X1+1/2 have:
E Gape (Xr)) = E
sup LXec
(A(X), Xr x) = =O(LTT)
Proof. With a constant step-size, Proposition implies
|
T Xx - X
(V441/2, - x) -X
+
|V Vill Voll2
27
2
27
1=1
t=1
We show that using smoothness and cocoercivity of the operator, along with the relative noise condition,
Σ (E [1) + [IA(X++1//)) S E [|
T
(min
- 27c)
If constant step-size y satisfies Eq. (10), then there exists some strictly positive real number 3, such that E Et (II((X))) ||A(X++122)119) S E |||x +00, which concludes that both
T Dt=1 1=1 |Aell and Σ 1/21+ are summable. Using the same arguments in the proof of Theorem 1, we obtain an upper bound for the gap,
D2
27c Ei= E [|A(X [1A(X))) + Ei= E [1 2v
(Gap((XT+1/)]
By relative variance and summability of operators,
E (
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 [Gape (Xr)] ((/T))
(11)
An extra appealing feature of the above is that result, i.c. the asymptotic convergence the iterates themselves before any averaging occurs, almost surely. More preciscly, we have the following proposition:
able to derive asymptotic last iterate trajectory
Proposition 5. Under Assumption the iterates of (DA), (DE), (OptDA) converge to a (VI) solution =."
The proof Proposition 5 relies on the fact that the distance of the iterates towards any solution of (VT) is decreasing almost surely along with the fact that the summability of |I guarantees that every limit point of the iterate also a solution of (VI). To streamline our presentation, we defer the
detailed proof to the appendix.
7

---

Adaptive Analysis
By the results of Section 4, one may easily observe the interplay between the (LI/VT) to ((1/T)
convergence rates under different noise profiles and step-sizes policies. Therefore natural question that arises from this context is the following:
Can we derive 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:
7 + E 1/+1/211
(Adapt)
The step-size (Adapt) is inspired by [44]; however, in our analysis, we provide generalized point of view which does not assume that Vú necessarily is the oracle query at the respective points in [44]. This allows us to include in the (Adapt) formulation all the adaptive sttep-siza sizes typically used for the archetypical schemes introduced in Section 3 More precisely, we have:
1. Adaptive Stochastic Dual Averaging: For Vi = 0 (Adapt) becomes the standard AdaNorm stepsize, studied in various works [11, 29]:
1
(12)
1+ Σラ 1 |1g
2. Aduptive Stochastic Dual Extrapolation: For V 91+1/2 (Adapt) becomes
71
(13)
VI 1 1/+1/211?
as used in, e.g., [3, 44, 47].
3. Adaptive Stochastic Optimistic Dual Averaging: For V 9t-1/2 (Adapt) becomes the step-size used [19, 20]:
7 E 9
(14)
Section 4, heuristically suggests that the success of y should hinge simultaneous performance as 1/ 1/vī for the absolute random oracle feedback and constant one. whenever the relative random feedback kicks in. This important interpolation feature is what will show in thhe sequel.
5.1 Absolute random noise
We will first treat oracles subject to absolute random nooise. In this case, we have: Theorem Assume that X,, X are the iterates of (GEG) run with the step-size (Adapt). Then, for every compact neighborhood C c IRd of a solution x² of (VI), we have:
[[aap((T)]=OO(1/
(15)
with X, - -1/T X,+1/2
As we argued above, the result of Theorem 3 heuristically justified by the fact that the almost sure boundedness conditions for the sequences:
||V]|| M almost surely for all t= 1, 1/2
(16)
yields that 7t = 2(11vF). 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 (Gape(Xx)) (1/vTT)
(17)
8

---

5.2 Relative random noise
Under the relative random noise conditions, we can obtained the following improved rate O (1/T) instead of the (11/VT) rate above. Formally, we have the following result:
Theorem 4. Assume that X,, x+1/2 the iterates of (GEG) with the step-size (Adapt). Then, for every compact neighborhood C IRd of solution x. of (VI), we have:
E (appp(XT)) -
(18)
with = 1 X
The crucial ingredient for the proof of Theorem consists of showing that the adaptive step size stabilizes to a positive constant You > O. In order to obtain this, the first step is to show that the template inequality of Proposition 2 yields
| ||--~~1 x 2
E
8c max { 2
+G +
+
E
(19)
7r+1
Moreover, due to the definition of (Adapt) and Jensen's inequality we have:
T
T
I
E
Vi
V++1/211
S
E
1
V2 Ve-1/2112
-
=
7T+1
7
(20)
Therefore, after combining (19) and (20) we get that E monotone convergence theorem) that:
+00 This directly implies (by
1+ Σ
V +oo almost surely
(21)
7
which in turn yields that Σl= VIVE definition of 7 we have almost surely the following:
1/21/ is summable almost surely. Therefore due to the
7T+1
7oo >
(22)
VI+ 11V V44//21
V1+ E V2+1/211
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 [Gape(Xr)] = 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 beeoor any averaging takes place- and it hinges on the fact that the (random) sequences || VV2 - V 2 and [[))x are summable with probability 1. Having established this, we show that X, satisfies is (stochastic) quasi-Fejér sequence [9] (with respect to the solution set X')) along with the fact that every limit point of X, belongs to X These two building blocks are sufficient in order to derive the almost sure convergence of the iterate's 's trajectory.
6 Numerical experiments
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 single resource Kelly auction, there are N players sharing total

---

800
0.1
0.0, 0.0
DG
700
Opt
Oakx 2.0, G 0.0
DualX ada-t
0.O,
1.0
DualX
600
10a
DuelAvg
10'-
DualOpt
500
10"
107-
10"
200
100
10' 101
200000 400000
10
10' 10 10
10
Figure 1: (left) Player utility using adaptive DualX various relative noise levels. Even relative high levels of noise do we converge to the optimal depicted with (x). (center) Average iterate for deterministic, absolute noise and relative noise using adaptive DualX. We observe the (1/vVT) rate under absolute noise while (1/TT) is achieved both in the noiseless setting and under relative noise. In addition, as expected, the last iterate only converges under the deterministic and relative noise oracle (see ??). (right) Average iterate comparing various methods for deel = 0.1. All methods shares convergence rate with adaptive methods being slightly faster possibly because of difficulty of step-size tuning for non-adaptive methods. Error bars indicate one standard deviation computed using 10 independent executions.
amount of Q R>0 resources. At every round, each bidder, p. submits a bid xD R20 and On"
receives proportional resources, p² = 7+Σ,20 go, where Z is the auction entry price. The payoff
for player p is then given as u²(x"; PP)) GP xx, where GP is the marginal gain in utility for player p. One 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 measurement when querying the payoff. In such settings, is common 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, 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 term proportional to the norm of the operator. In notation can thus capture both relative noise and absolute noise through the error term U, in the following way,
U. = (ral A(X))) + fabs:
(24)
where Erel ~ (0, ofa)) and Eahs NO o2 To validate the convergence rate we compute the optimal strategy in the deterministic setting (i.e. rzel 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 Jaba- 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 covariance matrix [10, 18].
Concluding remarks
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 (1/T)) rate for monotone (VT) by only assuming Lipschitz continuity of the said operator and relative noise. Moreover, 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 () rate. We postpone these questions to the future.
10

---

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 l'avenir" program IAN--IS- the LabEx PERSYVAL (ANR-11-LAB--005-00) MIAI@ Grenoble Alpes (ANR-19) JANR-19-P3IA 19-P31A-0003) and the grant ALIAS (ANR- LAAN--9--CUN ----CE---00--00) On the EPFL side, this project has also received funding from the European Research Council (ERC) under the European Union's s Horizon 2020 research and innovation programme (grant agreement n2 725594 time-data), the Hasler Foundation Program: Cyber Human Systems (project number 16066), and the Swiss National Science Foundation (SNSF) under grant number 200021 178665/1. This project was sponsored by the Department of the Navy, Office of Naval Research (ONR) under grant number N62909- 11--111-11111111 and the Army Research Office under Grant Number 1911NF-19-1-0400
References
[1] Kimon Antonakopoulos and Panayotis Mertikopoulos, Adaptive first-order methods revisited: Convex optimization without Lipschitz requirements. In NeurlPS 21: Proceedings of the 35th International Conference on Neural Information Processing Systems, 2021.
[2] Kimon Antonakopoulos, E. Veronica Belmega, and Panayotis Mertikopoulos, An adaptive mirror-prox algorithm for variational inequalities with singular operators. In NeurlPS '19: Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.
[3] Kimon Antonakopoulos, E. Veronica Belmega, and Panayotis Mertikopoulos. Adaptive extra-gradient methods for min-max optimization and games. In ICLR '21: Proceedings of the 2021 International Conference on Learning Representations. 2021.
[4] Francis Bach and Ktir Ychuda Levy. A universal algorithm for variational inequalities adaptive to smoothness and noise. In COLT 19: Proceedings of the 32nd Annual Conference on Learning Theory. 2019.
[5] Jean- BennBernrrdd Baillon and G. Haddad. Quelques propriétés des opérateurs angle-boréés ne-cycliquement monotones. Isruel Journal of Mathematics, 26:137-150, 1977.
[6] Heinz H. Bauschke and Patrick L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York, NY, USA, 2 edition, 2017.
[7] Mario Bravo, David Leslie, and Panayotis Mertikopoulos. Bandit learning in concave N-person games.
In NeurlPS 11: Proceedings of the 32nd International Conference of Neural Information Processing Systems, 2018.
[8] Volkan Cevher and Bang Cong Vu. On the linear convergence of the stochastic gradient method with constant step-size. /712 [math), June 2018.
[9] Patrick L. Combettes and than-Christophe Pesquet. Stochastic quasi-Fejér block-coordinate fixed point iterations with random sweeping, SIAM Journal on Optimization, 1221-1242111 2015.
[10] Constantinos Daskalakis, Andrew Ilyas. Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In ICLR 18: Proceedings of the 2018 International Conference on Learning Representations, 2018.
[11] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research, 12:2121-2159, 2011.
[12] Alina Ene and Huy L Nguyen. Adaptive and universal gaggdieg algorithms for variational inequalities. arxiv preprint arXiv:2010.07799, 2020.
[13] Francisco Facchinei and Jong-Shi Pang. Finite-Dimnnsioes Variational Inequalities and Complementarity
Problems. Springer Series in Operations Research. Springer, 2003.
[14] Huang Fang, Zhenan Fan, and Michael P Friedlander. Fast convergence of stochastic subgradient method under interpolation. In ICLR '21: Proceedings of the 2021 International Conference on Learning Representations, 2021.
[15] Bolin Gao and Lacra Pavel. Discounted mirror descent dynamics in concave games. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 5942 5942-5947, IEEE, 2019,
[16] Ian J. Goodfellow, Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS 'J4: Proceedings of the 28th International Conference on Neural Information Processing Systems, 2014.
[17] Yu-Guan Hsieh, Franck lutzeler. Jérôme Malick, and Panayotis Mertikopoulos. On the convergence of single-call stochastic extra- gradient methods. In NeurIPS 'I9: Proceedings of the 33rd International Conference on Neural Information Processing Systems, pages
2019.
11

---

[18] Yu-Guan Hsieh, Franck lutzeler. Jérôme Malick, and Panayotis Mertikopoulos. Explore aggressively. update conservativel: Stochastic extragradient methods with variable stepsize scaling. In NeurlPS '20: Proceedings of the 34th International Conference on Neural Information Procexsing Systems. 2020.
[19] Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulls. Adaptive learning in continuous games: Optimal regret bounds and convergence to Nash equilibrium. In COLT "21: Proceedings of the 34th Annual Conference on Learning Theory, 2021.
[20] Yu-Guan Hsieh, Franck lutzeler, Jérôme Malick, and Panayotis Mertikopoulos. Multi-agent online optimization with delays: Asynchronicity, adaptivity, and optimism. Journal of Machine Learning Research, to appear.
[21] Alfredo N lusem, Alejandro Jofré, Roberto I Oliveira, and Philip Thompson. Variance-based extragradient methods with line search for stochastic variational inequalities. SIAM Journal on Optimization, 29(1):
175 206-206772 2019.
[22] Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1 1(1):17 -0077-58,, 58, 2011. doi: 10. 10.1214/10-SSY01. 1. URL https:
//doi.org/10 wttg//..1/////11.... 1011110000--
[23] Anatoli Juditsky, Arkadi Semen Nemirovski, and Claire Tauvel. Solving variational incqualities with stochastic mirror-pros prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
[24] Ali Kavis, Kfir Yehuda Levy. Francis Bach, and Volkan Cevher. UnixGrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. In NeurlPS' 'I9 Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.
[25] G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonom. i Mat. Metody, 12:747-756, 1976.
[26] Kfir Yehuda Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and accelera- tion. In NeurlPS '1: Proceedings of the 32nd International Conference of Neural Information Processing Systems, 2018.
[27] Tengyuan Liang and James Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In AISTATS '19: Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019.
[28] Tianyi Lin, Zhengyuan Zhou, Panayotis Mertikopoulos, and Michael Jordan. Finite-time last iteertte convergence for multi-agent learning in games. In ICMI. '20: Proceedings of the 37th International Conference on Machine Learning, 2020.
[29] H. Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. In COLT I1: Proceedings of the 23rd Annual Conference Learning Theory, 2010.
[30] Panayotis Mertikopoulos and Mathias Staudigl. Convergence to Nash equilihrium in continuous games with noisy first-order feedback. In CDC 17: Proceedings of the 56th IEFE Annual Conference on Decision and Control, 2017.
[31] Panayotis Mertikopoulos and Mathias Staudigl. Stochastic mirror descent dynamics and their convergence in monotone variational inequalities. Journal of Optimization Theory and Applications, 179(3):838 887. December 2018
[32] Panayotis Mertikopoulos and Zhengyuan Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming, 173(--2):465-507 Jamuary 2019.
[33] Panayotis Mertikopoulas, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In ICLR '9: Proceedings of the 2019 International Conference on Learning Representations, 2019.
[34] Arkadi Semen Nemirovski. Prox method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex conccvveeccvveeeeeeee saddle point problems. SIAM Journal on Optimization, 15(1):229 251, 2004.
[35] Arkadi Semen Nemirovski, Anatoli Juditsky. Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach stochastic programming. SIAM Journal on Optimization, 19(4):1574-1609 2009.
[36] Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Number 87 in Applied Optimization. Kluwer Academic Publishers, 2004.
[37] Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2):319 344, 2007.
[38] Yurii Nesterov. Primal-dual subgradient methods for convex problems. Mathematical Programmingg 120 (1):221-259, 2009.
[39] Samet Oymak and Mahdi Soltanolkotabi. Toward moderate overparameterization: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 1 (1):84 105, 2020.
12

---

[40]
Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In ICML '17: Proceedings of the 34th International Conference on Machine Leurning, 2017.
[41] Boris Teodorovich Polyak. Introduction to Optimization. Optimization Software, New York, NY, USA, 1987.
[42]
Boris Teodorovich Polyak and Anatoli Juditsky. Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization, 30(4):838-855, July 1992.
[43] Leonid Denisovich Popov. A modification of the Arrowc method for search of saddle points. Mathematical Notes of the Academy of Sciences of the USSR, 28(5):845- 848, 1980.
[44] Alexander Rakhlin and Karthik Sridharan. Optimization, Icarning, and games with predictable sequences. In NIPS 11: Proceedings of the 27th International Conference on Neural Information Processing Systems, 2013.
[45] Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under strong growth condition. arXiv preprint arXiv: 6370, 2013.
[46] Gesualdo Scutari, Francisco Facchinei, Daniel Pérez Palomar, and Jong-Sh Shi Pang. Convex optimization, game theory, and variational inequality theory in multiuser communication systems. IEEE Signal Process. Mag. 27(3))35-49, May 2010.
[47] Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E. Schapire. Fast convergence of regularized learning in games. In NIPS '15: Proceedings of the 29th International Conference on Neural Information Processing Systems, pages 2989-29999 2015.
[48] Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and Faster Convergence of SGD for Over- Parameterized Models and an Accelerated Perceptron,
[cs, stat], April 2019.
[49] Lin Xiao. Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine Learning Research, 11 11:253322566, October 2010.
[50] Yuege Xie, Xiaoxia Wu, and Rachel Ward. Linear convergence of adaptive stochastic gradient descent. In International Conference on Artificial Intellignnce and Statistics, pages 1475-1483 PMLR, 2020.
[51] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 1.03530, 2016.
13


Reviews:
[{"review_id": "x_Np6iIewL", "reviewer": "Reviewer_Nv5u", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written overall and the technical proofs are clear. It is remarkable that the proposed  algorithms are both universal and adaptive, rendering them much more user-friendly than algorithms with tons of tuning parameters that rely on potentially unknown quantities. In addition, the possibility to adapt to certain noise structures that the work brings up might have broad impact in the optimization community in designing more adaptive algorithms. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "My comments are mainly about the notation inconsistency and minor issues.\n\n(1) The cocoercivity parameter is denoted as $\\beta$ in equation (CC), but $1/L$ in Theorem 2 and proofs. \n\n(2) The bound for $g(x, \\omega)$ is denoted as $M$ in Assumption 2 and 3, but $G$ is equation (19) and proofs, if I understand correctly. \n\n(3) I believe the first part of Proposition 1 is weaker than what is proved in Appendix. The proof shows that if $\\hat{x}$ is a solution, then $\\text{Gap}_{\\mathcal{C}}(\\hat{x}) = 0$. The current version in Proposition 1 is only an intermediate step. \n\n(4) Above equation (F.11): \"Assume that $\\beta_{\\infty} = +\\infty$\" should be \"Assume that $\\sum_{t=1}^{\\infty}\\beta_t = \\infty$ with non-zero probability. \n\n(5) Could you add a short proof on why the vector field in Section 6 is cocoercive? It would be informative to get a sense of how the cocoercivity parameter depends on Q and Z. \n\n(6) I would suggest adding the dependence on $L$ and $G$ in those rates. It seems that the $O(\\sqrt{T})$ rate does not even require cocoercivity. \n\n(7) Appendix, equation (E.23), first line: extra vertical line in $X_{t+1/2} - X_t |$. \n\n(8) Are there examples other than overparametrization and the one you presented in Section 6 that involve relative random noise? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "RewEsZazHsN", "reviewer": "Reviewer_cKdA", "summary": "This paper focuses on the variational inequality problem and proposes a framework to solve this types of problems. The paper further analyses its performance under different noise assumptions and obtain convergence rates for a wide range of algorithms.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I don't see any major flaws in the proofs. The presentations are very clear. The technical part is strong. \n\nAlthough the paper does not propose a new algorithm for variational inquality problem, it successfully unifies previous existing analysis and can be potentially used to find new algorithms. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The potential negative societal impact is not a must for this work.\n\nI don't have any major problem for this paper. There are only some minor problems:\n\nI am not impressed by the relative randomness part. I don't think this is a very useful assumption (i.e. the randomness vanishes around the optimizer). And I am not surprised to see that this assumption can give $O(\\frac{1}{T})$ convergence rate as the oracle case.\n\nAs far as I understand, the Assumption 2.1 (almost sure boundedness) is not necessary for non-adaptive step size. Those results in Section 4 hold without it. It only affects Section 5. If this is the case, the authors can add one or two sentences to comment on it.\n\nIn many places, the paper use \"$<\\infty$\" to represent two different (although related) meanings. One is that a random variable or a series does not diverge, which is the standard meaning. Another is that a constant which is not depend on $T$, which is very important for convergence analysis. The authors should explain the usage briefly, or change to a different notation, to avoid any confusion.\n\nLine 171, missing reference.\n\nLine 496, $X$ should be $x$. \n\nLine 252, Line 584 - Line 605, some $G$ should be $M$.\n\nLine 587, the middle two steps are unnecessary.\n\nLine 603, missing right bracket.\n\nLine 643, the sentence is meaningless.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "JziBy5Lak-y", "reviewer": "Reviewer_7yTa", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The relevant literature is adequately surveyed, and the paper is clearly written with the nice framework cleanly abstracted. Regarding the adaptive vs. non-adaptive stepsize schedule and the theorem statement, it would be good to explicitly specify the dependence on the lipschitz constant/noise variance etc., instead of focusing only on the dependence on $T$ for a fairer comparison. In a different vein, how would line-search type method compare against these adaptive procedures?\n\nThe claims do look right. But it is not clear to me when does the noise model in Assumption 3 hold in practice or if one could check/come up with an implementable procedure to ensure such a condition (but perhaps a control-variate based idea from stochastic optimization could help?) It would be nice if the authors could justify such an assumption. The analysis itself is reminiscent of those stochastic-(sub)gradient based algorithm from optimization. \n\nMinor typos: line 223: sttep-sizes -> step-sizes; line 233: thhe sequel -> the sequel\n\n============== post author-response ===============\nI thank the authors for addressing my comments and would like to keep my score unchanged.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "7APGk5xghXe", "reviewer": "Reviewer_negE", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper is well-structured, well-written and includes a few enlightening results. I have enjoyed reading the paper. In particular, I find the techniques and results the authors showing interesting and novel, in the following senses:\n\n1) The authors propose a nice and clean framework that cast  many known methods as special cases, and fully characterize the convergence rate of their method under two commonly-seen noisy oracle models for solving VIs, under the cocoercitivity assumption. I have not seen many 1/T results, or last-iterate converging result under noisy oracles for such problems, and think this is a very interesting result under its own. \n\n2) The authors also give methods with adaptive stepsize choices that doesn't depend on problem parameters, and also provide theoretical support of the same convergence rate. This makes a further step toward improving the practicality of the methods, which many newly-designed first-order methods for such problems fall short of.\n\n3) The flow of the paper is easy to follow. Especially while the authors explain how they achieve the results, they show their key lemma is a summable property of the oracle return terms, which in turn relies crucially on the cocoercive property of the operator. I think this will help readers understand their techniques better and might facilitate interesting progress in other relevant problems.\n\nConsidering all these factors, I think it is a nice paper worth sharing in the community. The only suggestion of mine would be to motivate the consideration of relatively noisy oracles a bit more, perhaps in the specific context of examples 1-3 raised in the paper.\n\n* minor comment: line 122 \"relative random...\" looks like an unfinished sentence.\n\n** Update: I have read the authors' responses and my concerns are addressed properly. Based on these, I am happy to keep my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors list the limitation of the paper in a clear way in Section 7 when they make the conclusion.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes universal adaptive stochastic gradient-based methods for variational inequalities. It unifies several dual averaging algorithms, uses AdaGrad-type stepsize to achieve universality and adaptive results, and shows asymptotic convergence of the last iterate. I agree with the reviewers that the technical contributions are interesting and novel, and I am happy to recommend acceptance. 
Decision: Accept (Poster)