acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Extragradient Methods Beyond Lipschitz Continuity

Abstract

Stochastic variational inequality problems have received significant attention due to their ability to model large-scale machine learning tasks. Typically, the operators involved are assumed to be globally Lipschitz, with only a handful of works extending beyond the standard setting to the so-called -Lipschitz setting. In this work, we propose a novel stochastic past extragradient algorithm for variational inequality problems under a broad regularity assumption that is even less restrictive than -Lipschitz continuity and provide convergence guarantees under bounded variance of the stochastic oracle. More precisely, we show a.s. convergence with suitable stepsize schedules and obtain convergence rates in expectation and in probability for fixed horizons. Finally, in numerical simulations we compare our proposed algorithm against standard methods.

Primary area:
optimization
Keywords:
stochastic methods, variational inequalities, generalized smoothness

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_5ETkOpenReview ↗
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 T(x)=F(x)L0+L1∣F(x)∣T(x)=\frac{F(x)}{L_0+L_1|F(x)|}, and assume that TT is Lipschitz. This gives a broader class of problems than the standard (L0,L1)(L_0,L_1)-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 (L0,L1)(L_0,L_1)-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 O(K−1/2)O(K^{-1/2}) expectation result is for the residual of T+NCT+N_C, rather than F+NCF+N_C. 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 L1=1L_1=1 and small values of L0L_0, 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
  1. Can the authors give a more explicit finite-time guarantee for the standard residual F+NCF+N_C in the constrained case? In particular, can the dependence hidden in the constant CηC_\eta be made more explicit?

  2. In the quartic-game experiment, the values of L0L_0 and L1L_1 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?

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

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

  5. 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?

  6. The theoretical step sizes depend on L0L_0, L1L_1, and the noise level σ\sigma. How would these quantities be chosen in practice?

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

We thank the reviewer for their reading of our work.

In the following we address the Weaknesses raised by the reviewer.

The main finite-time rate is not for the usual VI residual. [...]

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 experiments are somewhat disconnected from the theory. [...]

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.

Can the dependence hidden in the constant CηC_\eta be made more explicit?

From the proof of Theorem 4.9, it can be observed that the choice Cη=2CTηsup⁡z∈CL0+L1∣F(z)∣∣∣z−x∗∣≤2Cz/η2C_{\eta} = \frac{2 C_T}{\eta} \sup_{z \in C} \\{ L_0 + L_1 \\| F(z) \\| \mid \\| z - x^* \\| \leq \sqrt{2 C_z/\eta} \\}^2 is admissible. This reveals that a small finite-KK error may be difficult to obtain for very small violation probabilities η\eta, depending on the growth of ∥F∥\| F \| away from the solution. We have elaborated on this in Remark 4.10 in the updated paper.

In the quartic-game experiment, the values of L0L_0 and L1L_1 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?

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.

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 L0L_0, L1L_1, and the noise level σ\sigma. 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 L0,L1L_0,L_1 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

Reviewer_78DDOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper establishes Stochastic Past Extra Preconditioned Gradient, a method for solving Minty Variational Inequalities under a relaxation of the (L0,L1)(L_0, L_1) smoothness condition. The authors provide convergence guarantees for the proposed algorithm under the bounded variance assumption. Almost sure convergence of the algorithm is established. Additionally, convergence rates in expectation and in probability for fixed horizons are provided by the authors. Numerical experiments showcase the performance of the algorithm in practice.

Critical strengths

Strenghts:

  1. The paper is well-written and easy to follow for the reader.
  2. The setting is quite general, moving beyond the classical monotone and smooth Variational Inequalities
  3. A fair amount of the paper is devoted explaining the connection of the relaxed (L0,L1)(L_0, L_1) smoothness condition with the classical assumption including useful examples.
  4. Both in expectation and in probability guarantees are established for the proposed algorithm.
Critical weaknesses
  1. In general, the bounded variance assumption seems to be quite stringent. However, given the relaxation of the other assumptions (Minty VI and relaxed smoothness condition), especially if there are no prior results in the literature for this setting, I think it is fine as a first convergence guarantee being established for that method. It would be good if the authors comment on any prior results on that setting.
  2. The experiments compare the proposed method with the classical Stochastic Extragradient or Stochastic Past Extragradient. However, the proposed method uses preconditioning which may provide an unfair advantage over the classical methods. I believe that it would have been better if there was a comparison also with other methods that use preconditioning in order for the comparison to be fair.
  3. The proposed algorithm seems to be using two different stochastic oracles per iteration even though it is assumed to be a variant of Stochastic Past Extragradient. Is there the possibility that the algorithm can be run with one stochastic oracle per iteration and if so what are the obstacles for establishing the theoretical guarantees for that.
Questions for authors
  1. In line 163, did you mean to say "(3) implies (2)" or "(2) implies (3)"? The proposed relaxed class should include as special case the (L0,L1)(L_0, L_1) smoothness condition.
  2. In line 262, is the provided equality proven in the paper or could you provide the proof of it, so that it becomes apparent to the reader?
  3. In the experiments, it seems that L0L_0 is treated as a hyperparameter of the algorithm. However, I would have thought that the L0,L1L_0, L_1 parameters are fixed once the underlying objective is fixed. Can the authors comment on that and in the case that L0L_0 is a hypeparameter how it should be selected in practice?
3 comments

We thank the reviewer for their careful reading of our work and their positive feedback.

In the following we comment on the stated Weaknesses of the paper:

In general, the bounded variance assumption seems to be quite stringent. [...] It would be good if the authors comment on any prior results on that setting.

As we state in the paper, the only other known result for stochastic extragradient type methods under generalized Lipschitz continuity is [1] and it tackles a much narrower setting than the one we consider: their generalized Lipschitz continuity assumption is more restrictive than our Definition 3.1 (see the discussion following Definition 3.1) and their pp-quasi-sharpness condition is substantially more restrictive than the Minty VI we use. In that sense, our analysis requires important relaxations of existing assumptions. To the best of our knowledge, in the operator setup that we consider, results under heavier noise assumptions such as pp-th bounded moments are obtained only under standard Lipschitz continuity.

The experiments compare the proposed method with the classical Stochastic Extragradient or Stochastic Past Extragradient. [...] I believe that it would have been better if there was a comparison also with other methods that use preconditioning in order for the comparison to be fair.

The purpose of the paper is to introduce a stochastic preconditioned algorithm that tackles problems beyond Lipschitz continuity with provable guarantees. In that sense, the main goal of the experimental section is to investigate whether a method designed to obtain these theoretical guarantees also performs well in practice when compared with established algorithms. SEG and SOG are natural baselines for this purpose.

Nevertheless, following the reviewer’s suggestion, we have also added comparison with the method analyzed in [1] for the experiments in the main text. Our proposed method outperforms this additional baseline in the reported experiments. We will also include results for this baseline on the additional experiments in the appendix in the final version of the paper.

The proposed algorithm seems to be using two different stochastic oracles per iteration even though it is assumed to be a variant of Stochastic Past Extragradient. Is there the possibility that the algorithm can be run with one stochastic oracle per iteration and if so what are the obstacles for establishing the theoretical guarantees for that.

Algorithm 1 uses two independent evaluations of the same stochastic oracle, with different roles: one provides the update direction (numerator) and the other provides the normalization (denominator). The past-extragradient reuse is already present in the algorithm. Specifically, the estimator computed at zk+1z^{k+1} is used in the update of xk+1x^{k+1} and then reused in the momentum update at the next iteration. Therefore, the method requires two fresh oracle evaluations per iteration, both at the same point.

A variant that only requires one evaluation using a different normalization mechanism may indeed be possible. However, its relation to the current operator norm would need to be controlled, and the uniform bounds used in Lemma 4.3 would no longer follow from the present argument. Such a variant therefore requires a separate analysis.

In the following we answer the Questions stated by the reviewer.

In line 163, did you mean to say "(3) implies (2)" or "(2) implies (3)"? The proposed relaxed class should include as special case the (L0,L1)(L_0, L_1) smoothness condition.

The implication as currently written is correct. To elaborate, for F∈C1(Rn)F \in \mathcal{C}^1(\mathbb{R}^n), the condition (2) is equivalent to (L0,L1)(L_0, L_1)-Lipschitz continuity while (3) characterizes our assumption. Now, if (2) implies (3), then every (L0,L1)(L_0, L_1)-Lipschitz operator also satisfies our assumption. In other words, the (L0,L1)(L_0,L_1)-Lipschitz class is a subset of the class we consider. The converse does not hold, as illustrated by Example 3.2 and other examples in Appendix A.

In line 262, is the provided equality proven in the paper or could you provide the proof of it, so that it becomes apparent to the reader?

The equality is formally stated in Lemma 4.3 and proven in Appendix B.4.

In the experiments, it seems that L0L_0 is treated as a hyperparameter of the algorithm. However, I would have thought that the parameters L0,L1L_0,L_1 are fixed once the underlying objective is fixed. Can the authors comment on that and in the case that L0L_0 is a hypeparameter how it should be selected in practice?

There are multiple ways in which L0,L1L_0,L_1 can be seen as hyperparameters. To begin with, if an operator is (L0,L1)(L_0,L_1)-Lipschitz for some L0L_0, it is also (Lˉ,L1)(\bar L,L_1)-Lipschitz for any Lˉ>L0\bar L > L_0, see also our reply to Reviewer TMsV. Moreover, for many functions, L0,L1L_0,L_1 are not uniquely defined but rather they are connected with some nonlinear relation, see for example [2, Example 3]. Finally, in practice, it is common to tune the stepsize choices beyond what is allowed by the theory, especially in tasks that involve training neural networks. In this case, some practical guidelines can be inferred directly from our experiment in subsection 5.1: smaller values of L0L_0 lead to a behavior more closely related to normalized gradient methods, while larger values make the algorithm perform similarly to the Euclidean (without preconditioning) methods.


References

[1] Vankov, D., Nedich, A., & Sankar, L. (2025). Generalized smooth stochastic variational inequalities: Almost sure convergence and convergence rates. Transactions on Machine Learning Research.

[2] Choudhury, S., & Loizou, N. (2025). Extragradient Method for (L0,L1)(L_0, L_1)-Lipschitz Root-finding Problems. Advances in Neural Information Processing Systems.

Thank you very much for the extra experiments. I maintain my positive evaluation of the paper.

Regards,
Reviewer 78DD

Reviewer_TMsVOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

Summary

This paper investigates the convergence of a variant of a extra-gradient type stochastic optimization problem for solving variational inequality problem. The authors generalizes the existing Lipschitz continuity assumption and adopt a stepsize rule based on an additional sampling to ensure convergence. Some experiments demonstrate the performance.

Critical strengths

Strength

The result is overall well-motivated.

Critical weaknesses

Weaknesses

I have a few concerns about the theoretical results.

  1. The paper uses the same notation for the problem constant and algorithm hyperparameter selection. In the analysis, L0L_0 is the Lipschitz constant, but in the algorithm, L0L_0 also serves as a clipping parameter. Mixing the role of algorithm hyperparameter and problem parameters causes confusion: for example, the 2nd moment terms from Lemma 4.3 depend on 1/L021/L_0^2, and as L0→0L_0 \rightarrow 0 the upperbound becomes vacuous. This result does not make sense. What you can do is define the stepsize as 1η0+η1∣G∣\frac{1}{\eta_0 + \eta_1 \\|G\\|} so that η0\eta_0 can control the variance even if L0L_0 is close to 0.
  2. The convergence result is weak. In particular, integrating the tail bound from Theorem 4.10 gives no bound on expectation. Besides, the size of the constant CTC_T is not discussed sufficiently.

Overall, I think the paper contains some interesting ideas, but its presentation is not satisfying. I therefore recommend weak rej.

Questions for authors

N.A.

4 comments

We thank the reviewer for their reading of our work.

In the following we comment on the stated Weaknesses of the paper:

The paper uses the same notation for the problem constant and algorithm hyperparameter selection. [...]

We remark that the usage of problem constants in the algorithm is standard in the related literature, see for example [1, Algorithm 1] or [2, Table 1]. Moreover, if an operator satisfies our Definition 3.1 for (L0,L1)(L_0, L_1), it also satisfies it for (βL0,βL1)(\beta L_0, \beta L_1) with β>1\beta > 1, so larger normalization coefficients can be selected while preserving Definition 3.1. In fact, for the (L0,L1)(L_0,L_1)-Lipschitz operators we can increase L0L_0 without increasing L1L_1 as is clear from Equations (2) and (9) in the text. Thus, even when L0L_0 is small, the algorithm can use a larger positive normalization parameter while preserving the regularity assumption.

The convergence result is weak. In particular, integrating the tail bound from Theorem 4.10 (Theorem 4.11 in the updated text) gives no bound on expectation. Besides, the size of the constant CTC_T is not discussed sufficiently.

As we state in Remark 4.7, our analysis does not transfer the in expectation rates to FF, unless some strict assumption such as boundedness of ∣F∣\\|F\\| over the iterates is imposed. We have now added an example that shows that a finite expectation bound for FF is in fact impossible for the algorithm under our general assumptions, which also implies that this is not a limitation of our analysis. Concretely, consider F(x)=x3F(x) = x^3, L0=L1=1L_0 = L_1 = 1, and G(x,ξ)=x3+ξG(x,\xi)=x^3+\xi, where ξ\xi has zero mean, finite variance, but E[∣ξ∣3]=∞\mathbb E[|\xi|^3] = \infty. For example, when ξ\xi follows a Student-t3t_3 distribution. Starting from x0=0x^0 = 0, we have z1=−γξ01+∣ζ0∣z^1 = -\gamma\frac{\xi^0}{1 + |\zeta^0|} and therefore E[∣F(z1)∣]=+∞\mathbb E[|F(z^1)|] = +\infty.

Moreover, we disagree with the characterization of the convergence results as ``weak''. We provide in expectation convergence rates for the natural residual of this family of operators (which as we show above cannot be transferred to rates for the standard residual ∣∣F∣∣||F||), almost sure convergence under standard stepsize choices and convergence rates in probability. Convergence guarantees in probability are an established theoretical target under generalized smoothness. In particular, [3, Theorem 5.3] provides such a guarantee for stochastic gradient descent under bounded-variance noise, while [4, Theorem 4.1] provides one for Adam under bounded noise.

We therefore ask the reviewer to reconsider the broad characterization or provide a specific technical justification for it.

Regarding the constant CTC_T, it is independent of the horizon KK and depends on the initialization, noise level, normalization parameters, and chosen stepsizes. Its polynomial dependence on δ=L1σ/L0\delta=L_1\sigma/L_0 reflects the deterioration of the bound when the noise is large relative to the normalization floor. We have added this discussion in the main text.

The presentation is not satisfying

Could the reviewer please clarify in what sense the presentation is not satisfying? Beyond the two points addressed above, the review does not identify which definitions, statements, or arguments are unclear. We ask the reviewer to specify the relevant passages and the missing explanations so that this concern can be assessed and addressed concretely.


References

[1] Gorbunov, E., Tupitsa, N., Choudhury, S., Aliev, A., Richtárik, P., Horváth, S., & Takáč, M. (2025). Methods for convex $(L_0, L_1) $-smooth optimization: Clipping, acceleration, and adaptivity. International Conference on Learning Representations.

[2] Choudhury, S., & Loizou, N. (2025). Extragradient Method for (L0,L1)(L_0, L_1)-Lipschitz Root-finding Problems. Advances in Neural Information Processing Systems.

[3] Li, H., Qian, J., Tian, Y., Rakhlin, A., & Jadbabaie, A. (2023). Convex and non-convex optimization under generalized smoothness. Advances in Neural Information Processing Systems.

[4] Li, H., Rakhlin, A., & Jadbabaie, A. (2023). Convergence of Adam under relaxed assumptions. Advances in Neural Information Processing Systems.

Thanks for the response. I'd like the authors to address two points.

  1. I have concerns about the constant-probability convergence result, which is not common in the literature. Please explicitly discuss this limitation in the introduction. It would be more convincing if you could find other papers that establish this type of convergence guarantee. A lower bound alone cannot justify the convergence criterion; it can also mean that no algorithm works well under the specified assumptions.

  2. Again, I strongly recommend differentiating the algorithm hyperparameters from the problem constants. This is the presentation issue I mean.

Overall, I maintain my score for now, and I'd raise the score if these two points are properly addressed.

We split the first comment of the reviewer to reply to each specific point.

I have concerns about the constant-probability convergence result, which is not common in the literature. Please explicitly discuss this limitation in the introduction. It would be more convincing if you could find other papers that establish this type of convergence guarantee.

To begin with, we stress that our result is not restricted to a fixed success probability. Specifically, let ZK=zJK+1Z_K=z^{J_K+1} denote the randomized output after KK iterations. In the unconstrained setting, Theorem~4.11 establishes that, for every ε>0\varepsilon>0,

\leq \frac{C_T(L_0+L_1\varepsilon)^2}{\sqrt{K}\varepsilon^2},$$ where $C_T$ is independent of $K$. Consequently, for every fixed accuracy $\varepsilon>0$, $$\lim_{K\to\infty} \mathbb{P}\bigl(\|F(Z_K)\|>\varepsilon\bigr)=0.$$ Thus, the original residual converges to zero in probability, with an explicit $O(K^{-1/2})$ bound on the failure probability, which is a standard result. More explicitly, for any prescribed accuracy $\varepsilon>0$ and failure probability $\eta\in(0,1)$, choosing an integer horizon $$K\ge \frac{C_T^2(L_0+L_1\varepsilon)^4}{\eta^2\varepsilon^4}$$ ensures $\mathbb{P}\bigl(\|F(Z_K)\|\le\varepsilon\bigr)\ge 1-\eta$. The confidence can therefore be made arbitrarily close to one by increasing the iteration budget, i.e., it is not fixed at a constant level. This is the same type of probabilistic accuracy criterion used in the references already provided in our response, for example, [3, Theorem 5.3] and [4, Theorem 4.1]. We remark that both are well-cited works. In addition, see also [5, Theorem 4.2], which covers the generalized smooth setting, and [6, Theorem 2.1] in the more classical $L$-smooth case. > A lower bound alone cannot justify the convergence criterion; it can also mean that no algorithm works well under the specified assumptions. We would like to stress the following facts: first, the assumptions we make (the counterexample we provide satisfies $(L_0,L_1)$-smoothness) are already well-established in optimization and have been extended to the (mostly deterministic) operator setting, with a lot of active research [2, 11-15]. It is thus natural to analyze the stochastic setting as well. In fact, in the conclusion of [15] (which appeared after the ICLR submission deadline), convergence guarantees for stochastic monotone operators beyond the Lipschitz setting was left as an open question, which further strengthens the relevance of our results. Second, we emphasize that beyond the in-probability rates, we also show almost sure convergence of the method under standard stepsize choices. > Again, I strongly recommend differentiating the algorithm hyperparameters from the problem constants. This is the presentation issue I mean. We have added Remark 3.7 in the revised version of the manuscript, where we explicitly explain the role of $L_0$ and $L_1$ as tunable parameters. Nevertheless, we would like to stress that we do not consider such a notational issue to be grounds for rejection, especially considering the vast number of papers that also use the problem parameters in the algorithm, [1, Algorithm 1], [7, Algorithm 1.1], [8, Algorithm 1], [9, Algorithm 1], [10, Sections 3.7.1-3.7.2].

References

[5] Yu, D., Jiang, W., Tao, H., Wan, Y., & Zhang, L. (2026). Mirror descent under generalized smoothness. International Conference on Machine Learning.

[6] Ward, R., Wu, X., & Bottou, L. (2020). Adagrad stepsizes: Sharp convergence over nonconvex landscapes. Journal of Machine Learning Research, 21(219), 1-30.

[7] Maddison, C. J., Paulin, D., Teh, Y. W., & Doucet, A. (2021). Dual space preconditioning for gradient descent. SIAM Journal on Optimization, 31(1), 991-1016.

[8] Reisizadeh, A., Li, H., Das, S., & Jadbabaie, A. (2025). Variance-reduced clipping for non-convex optimization. International Conference on Acoustics, Speech and Signal Processing.

[9] Lu, H., Freund, R. M., & Nesterov, Y. (2018). Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 28(1), 333-354.

[10] Bubeck, S. (2015). Convex optimization: Algorithms and complexity. Foundations and trends in Machine Learning, 8(3-4), 231-357.

[11] Vankov, D., Nedich, A., & Sankar, L. (2024). Generalized smooth variational inequalities: Methods with adaptive stepsizes. International Conference on Machine Learning.

[12] Vankov, D., Nedich, A., & Sankar, L. (2025). Generalized smooth stochastic variational inequalities: Almost sure convergence and convergence rates. Transactions on Machine Learning Research.

[13] Yoon, T., Choudhury, S., Greenberg, E., & Loizou, N. (2026). Polyak-type extragradient methods for monotone root-finding problems. arXiv preprint arXiv:2609.26581.

[14] Novoselov, K., Dorn, Y., Dvinskikh, D., & Gasnikov, A. (2026). Optimal Rates for Federated Variational Inequalities under different relaxations of bounded variance assumption. arXiv preprint arXiv:2610.12641.

[15] Greenberg, E., & Loizou, N. (2026). Extragradient and Past Extragradient Methods for (L0,L1)(L_0, L_1)-Lipschitz Variational Inequalities. arXiv preprint arXiv:2610.16886.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.