Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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. 
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:

1) 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. 

2) 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.

3) 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.

Considering 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.

* minor comment: line 122 "relative random..." looks like an unfinished sentence.

** Update: I have read the authors' responses and my concerns are addressed properly. Based on these, I am happy to keep my score.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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. 
limitations_and_societal_impact: My comments are mainly about the notation inconsistency and minor issues.

(1) The cocoercivity parameter is denoted as $\beta$ in equation (CC), but $1/L$ in Theorem 2 and proofs. 

(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. 

(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. 

(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. 

(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. 

(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. 

(7) Appendix, equation (E.23), first line: extra vertical line in $X_{t+1/2} - X_t |$. 

(8) Are there examples other than overparametrization and the one you presented in Section 6 that involve relative random noise?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: I don't see any major flaws in the proofs. The presentations are very clear. The technical part is strong. 

Although 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. 
limitations_and_societal_impact: The potential negative societal impact is not a must for this work.

I don't have any major problem for this paper. There are only some minor problems:

I 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.

As 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.

In 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.

Line 171, missing reference.

Line 496, $X$ should be $x$. 

Line 252, Line 584 - Line 605, some $G$ should be $M$.

Line 587, the middle two steps are unnecessary.

Line 603, missing right bracket.

Line 643, the sentence is meaningless.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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?

The 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. 

Minor typos: line 223: sttep-sizes -> step-sizes; line 233: thhe sequel -> the sequel

============== post author-response ===============
I thank the authors for addressing my comments and would like to keep my score unchanged.

limitations_and_societal_impact: Yes.
review_title: null

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)