Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proves the first high-probability complexity results with logarithmic dependence on the confidence level for stochastic methods for solving monotone and structured non-monotone variational inequality problems (VIP) with heavy-tailed noise and unbounded domains.
strengths_and_weaknesses: Strengths:
The paper is sound, well-organized and well-written.

Weaknesses:
Contribution is not significant enough. The results in the paper still need many assumptions. The paper only focuses on monotone variational inequalities.
questions: 1. The paper focuses on monotone variational inequalities, is it possible to get similar results for non-monotone variational inequalities?
2. It would be better to see comparison with SEG in experiments.
limitations: See above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the stochastic Variational Inequality Problem (VIP) with a potentially unbounded domain and the gradient might not satisfy the light tail assumption. The authors consider Stochastic ExtraGradient (SEG) and Stochastic Gradient Descent Ascent (SGDA) methods using clipped mini-batch stochastic gradients. Under various assumptions such as they proved that both methods converge with a high probability. 



strengths_and_weaknesses: Strength: This is the first paper that provides high-probability convergence guarantee for stochastic gradient methods for solving some VIPs without assuming  sub-Gaussian noise and unbounded domains.

Weakness: The authors do not compare their methods with some state-of-the-art methods for training GAN. Also, I have some concerns about using these methods in practice. Please see my questions below.
questions: 1. Why SNC, SM, QSM and SC are interesting properties? Can the authors provide some real problems (for example some GAN models) that are proven to satisfy these conditions? In literature, these properties are mostly studied for theoretical purposes with only some artificially constructed examples.  

2. Can the authors provide some justification for using  GapR(x) as the convergence criterion? For monotone F, we have GapR(x)<= \|F(x)\| R but not the other direction. Why a small GapR(x) indicates a good solution from a perspective of stationarity / variational analysis? 

3. The studied methods require mini-batches of big enough sizes. Moreover, these specific sizes depend on some unknown parameters. This is a limitation compared to other methods like Juditsky et al. [2011a] where the mini-batch is just optional and even one sample per iteration still works. Can the authors reduce the mini-batch size to one? If not, what is the technical challenge?

4. How to estimate and select R, which affects many parameters in the theorems and the algorithms including the batch sizes. 
limitations: I have listed the limitations in the questions section above. In addition, the authors do not include some state-of-the-art methods for training GAN in their numerical comparison such as the ones using Adam. What if the state-of-the-art method has even better performances?
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies variational inequality problem (VIP) with heavy-tailed noise and unbounded domain. It proposes a stochastic extragradient (SEG) method and a stochastic gradient descent-ascent (SGDA) method with gradient clipping techinique to address the problem. To handle the heavy-tailed noise, the paper considers clipping value for stochastic gradients, which controls the impact from heavy-tailedness but also introduces bias. The bias derived is addressed by different step-sizes and batch-sizes. To handle the unbounded domain, the paper only requires an upper bound of the distance between the initialization and the optimal solution. The convergence analysis on both stochastic methods and their proofs are discussed respectively in monotonic, star-monotonic and quasi-strong monotonic cases according to the respective property of the operator in the VIP. 
strengths_and_weaknesses: Originality: Although stochastic extragradient method, stochastic gradient descent-ascent method and gradient clipping techinique are well-studied in the literature, this paper successfully combines them and applies to the VIP with heavy-tailed noise, inidcating authors' original effort.

Quality: This paper gives the convergence results for monotonic, star-monotonic and quasi-strong monotonic operators in the VIP, which is comprehensive and readable for practitioners.

Clarity: The structure of this paper is well designed. The table of results in the introduction is straightforward.

Significance: This paper addresses VIP with heavy-tailed noise, which is common in industries and business.


questions: In the extra experiments of the paper, we can find the FID curves on training StyleGAN2 with the original SGDA method and the clipping-value SGDA method. Can you provide the similar results on training WGAN-GP with the original SEG method and the clipping-value SEG method?
limitations: In its experiments, the paper does not compare the results of its stochastic methods with those of Adam.
review_title: null

Meta-review: metareview: This is the first paper that provides high-probability convergence guarantee for stochastic gradient methods for solving some VIPs without assuming sub-Gaussian noise and unbounded domains. Although the numerical experiments are not fully convincing (e.g., no comparison with Adam for training GAN), the overall theoretical contribution is significant enough. I would recommend accepting this paper. 
confidence: Certain
Decision: Accept