- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies stochastic variational inequalities beyond the usual Lipschitz setting. The main idea is to work with the preconditioned operator , and assume that is Lipschitz. This gives a broader class of problems than the standard -Lipschitz setting. The authors propose a stochastic past extragradient method using independent samples for the direction and normalization, together with momentum. They prove almost sure convergence under a Minty condition and bounded variance, and give finite-time results in expectation and in probability. The paper also includes experiments on synthetic games, WGAN, neural optimal transport, and MNIST GAN training. I think the theoretical direction is interesting, but I have some concerns about how the finite-time results should be interpreted for the original VI problem and about the connection between the experiments and the assumptions used in the theory.
Critical strengths
-
The paper considers a fairly general operator class. The assumption on the preconditioned operator is weaker than the standard -Lipschitz condition, and the analysis only requires a Minty-type condition rather than the stronger growth assumptions used in some related stochastic VI work.
-
Using independent samples for the direction and the normalization gives a useful way to handle the bias introduced by the nonlinear preconditioner.
Critical weaknesses
-
The main finite-time rate is not for the usual VI residual. The expectation result is for the residual of , rather than . For the original operator, the constrained case only gives a result in probability, with a constant that is not very explicit. This makes it harder to understand the actual complexity for solving the original VI.
-
The experiments are somewhat disconnected from the theory. The paper does not verify the Minty condition or Definition 3.1 for the GAN and neural OT experiments. Also, some parameter choices used in the experiments do not appear to satisfy the theoretical conditions. For example, in the quartic game the experiments use and small values of , while the sufficient constants derived in the paper are quite different. I also noticed a possible mismatch between SOG in the paper and SPEG in the supplementary implementation for the MNIST experiment.
Questions for authors
-
Can the authors give a more explicit finite-time guarantee for the standard residual in the constrained case? In particular, can the dependence hidden in the constant be made more explicit?
-
In the quartic-game experiment, the values of and used in practice are different from the sufficient constants proved in the paper. Do these values still satisfy Definition 3.1? If not, how should this experiment be interpreted relative to the theory?
-
Do the Minty condition and Definition 3.1 hold, even approximately, for the WGAN, neural OT, or MNIST experiments? Some evidence here would make the practical relevance of the theory clearer.
-
Why are the stochastic generalized-smooth methods of Vankov et al. (2025) not included as baselines? They seem closely related to the setting considered here.
-
The supplementary implementation for the MNIST experiment appears to use SPEG, while the paper reports SOG in Table 8. Could the authors clarify which method was actually used?
-
The theoretical step sizes depend on , , and the noise level . How would these quantities be chosen in practice?
-
Could the authors update the bibliography to use the published conference versions where available? Several references are still listed as arXiv preprints although they have already appeared at ICLR/ICML/NeurIPS.
5 comments
Why are the stochastic generalized-smooth methods of Vankov et al. (2025) not included as baselines?
We have included comparisons with the method analyzed in Vankov et al. for the experiments in the main text, see the updated version of our manuscript. Our proposed method also outperforms this additional baseline in these experiments. We will also include results for this baseline on the additional experiments in the appendix in the final version of the paper.
The supplementary implementation for the MNIST experiment appears to use SPEG, while the paper reports SOG in Table 8.
We have changed SOG to SPEG in Table 8 (the SPEG update is added in Appendix C.1). Note that these two methods are very similar to each other (see also Remark 3.6).
The theoretical step sizes depend on , , and the noise level . How would these quantities be chosen in practice?
Indeed, our analysis relies on the knowledge of the variance of the stochastic oracle. In the experiments, we instead fix the normalization parameters and tune the stepsizes. Guidelines for choosing in practice can be found in our reply to the third question of Reviewer 78DD.
Could the authors update the bibliography to use the published conference version where available?
We thank the reviewer for bringing this to our attention, and we have updated the bibliography.
References
[1] Chavdarova, T., Gidel, G., Fleuret, F., & Lacoste-Julien, S. (2019). Reducing noise in gan training with variance reduced extragradient. Advances in Neural Information Processing Systems.
[2] Gidel, G., Berard, H., Vignoud, G., Vincent, P., & Lacoste-Julien, S. (2019). A variational inequality perspective on generative adversarial networks. International Conference on Learning Representations.
[3] Bohm, A., Sedlmayer, M., Csetnek, E. R., & Bot, R. I. (2022). Two Steps at a Time---Taking GAN Training in Stride with Tseng's Method. SIAM Journal on Mathematics of Data Science, 4(2), 750-771.
[4] Gorbunov, E., Danilova, M., Dobre, D., Dvurechenskii, P., Gasnikov, A., & Gidel, G. (2022). Clipped stochastic methods for variational inequalities with heavy-tailed noise. Advances in Neural Information Processing Systems.
[5] Oikonomidis, K., Quan, J., & Patrinos, P. (2025). Nonlinearly preconditioned gradient methods: Momentum and stochastic analysis. Advances in Neural Information Processing Systems.
[6] Pethick, T., Xie, W., Erdogan, M., Antonakopoulos, K., Silveti-Falls, A., & Cevher, V. (2025). Generalized Gradient Norm Clipping & Non-Euclidean $(L_0, L_1) $-Smoothness. Advances in Neural Information Processing Systems.
Dear Authors,
Thank you for the revised paper. I appreciate the inclusion of the counterexample, the clarification of the constants, the additional Vankov et al. baseline, and the experimental corrections. These revisions substantially address several of my concerns.
The counterexample convincingly explains why an in-expectation guarantee for the original residual is unavailable under the stated assumptions. However, the constrained-case guarantee still involves a potentially very large, growth-dependent constant, making its quantitative complexity difficult to assess.
My main remaining concern is the theory–experiment gap. In Section 5.1, the stochastic oracle appears to satisfy $ \mathbb E_i|F_i(x,y)-F(x,y)|^2 =\sigma_B^2(|x|^2+|y|^2), $ which violates the global bounded-variance Assumption 4.1 on the unconstrained domain. Could you clarify this point? Including at least one controlled experiment satisfying the theoretical assumptions would considerably strengthen the paper.
Best regurds,
Reviewer 5ETk
We thank the reviewer for their reading of our work.
In the following we address the Weaknesses raised by the reviewer.
Please see our reply to the second weakness of Reviewer TMsV where we show that an in expectation rate is impossible for the usual VI residual (even for the root-finding case) in the general setting we consider.
The main purpose of the experiments is to evaluate the practical behavior of the proposed method, which is standard in the related literature [1-6]. We have made this more clear in the paper. Note also that, for the non-Lipschitz problems that we consider, standard methods such as SEG and SOG do not admit a globally valid stepsize. In that sense, choosing a stepsize via tuning is natural for these experiments.
In the following we answer the Questions stated by the reviewer.
From the proof of Theorem 4.9, it can be observed that the choice Cη=η2CTsupz∈CL0+L1∣F(z)∣∣∣z−x∗∣≤2Cz/η2 is admissible. This reveals that a small finite-K error may be difficult to obtain for very small violation probabilities η, depending on the growth of ∥F∥ away from the solution. We have elaborated on this in Remark 4.10 in the updated paper.
We address these two questions jointly, as both concern the relationship between the theoretical guarantees and the experimental evaluation.
As the main contribution of the paper is obtaining convergence guarantees for our proposed method, the purpose of the experiments is to test whether our proposed method also performs well in practice.
In the quartic game, the experiments investigate the effect of the normalization parameters and include choices that indeed are not covered by the theory. This is done in order to demonstrate practical trade-offs between these choices. For WGAN, neural OT, and MNIST, we have not established that the Minty condition and Definition 3.1 hold. These experiments therefore demonstrate the practical usefulness of the proposed algorithm beyond its theoretical setting. Since our proposed method is novel, it is natural to test its behavior on practical problems and compare against standard methods.
We have added a discussion on this topic in the main text of our manuscript, see section 5 of the revised document.