acceptodds
Under review as a conference paper at ICLR 2027

Universal Extra-Gradient Method for Stochastic Variational Inequalities

Abstract

We study the stochastic Extra-Gradient Method (EGM) for solving a stochastic variational inequality (VI) over a compact convex set. The main assumption is -continuity of the VI mapping, which includes H\"older mappings and their linear combinations. We develop new adaptive, line-search-free step-size rules for stochastic EGM. These rules can be interpreted as enhanced AdaGrad-type updates and require no prior knowledge of either the continuity modulus of the VI mapping or the variance of the stochastic oracle. The resulting methods are universal and attain the best complexity bound among the admissible continuity regimes. We prove convergence guarantees in terms of an expected residual function that upper bounds the relevant accuracy measures for several important problem classes, including the dual gap for monotone VIs, and the primal-dual gap for saddle-point and optimization problems. For H\"older-continuous mappings, our bounds recover the optimal dimension-independent complexity of first-order methods.

Primary area:
optimization
Keywords:
Stochastic Variational Inequalities, Extra-Gradient method, approximate continuity, universal algorithms

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_5moROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies universal Extra-Gradient Methods (EGM) under approximately continuous mapping in a stochastic Variational Inequality setting. The authors introduce the notion of (δ,L)(\delta, L) continuity and show that Holder mappings belong to that class. They derive multiple line-search-free step-size rules that adapt to both the continuity of the mapping and the stochastic-oracle variance without requiring knowledge of them and establish optimal convergence guarantees for a residual function. Distance-adaptive variants that reduce sensitivity to the initial diameter are also introduced, improving the constants in the associated bounds. Experiments in minimization and min-max problems indicate the performance of the proposed algorithms in practice.

Critical strengths
  1. The introduced notion of (δ,L)(\delta, L) continuity seems quite general.
  2. The method is universal and does not require knowledget of the continuity of the mapping and the stochastic-oracle variance.
  3. The authors establish optimal convergence guarantees for a residual function, which serves as a general measure in both optimization and min-max games.
Critical weaknesses
  1. The experiments show that the proposed update rules might perform differently in practice. How should one select the update rule in practice?
  2. Many experiments (especially in softmax setting) indicate that prior methods perform significantly better than the proposed methods. Do you have any intuition or explanation for that?
  3. Minor typo: in line 366 "Distance-Adaptive EGM"
Questions for authors
  1. When should each variant be preferred in theory and in practice?
  2. Why in many experiments the proposed variants perform worse than the state-of-the-art baselines.
  3. Please refer to the questions in the "Weaknesses" part.
4 comments

We thank the reviewer for the time to read our manuscript.

Q) The experiments show that the proposed update rules might perform differently in practice. How should one select the update rule in practice?

R) To address this question, we have added sensitivity analyses for the initialization parameter D^\widehat D in EGM Rules 1--3 and for D0D_0 in DA EGM Methods 1 and 2 across all experiments in Appendix G. The results provide a practical guideline for selecting the initialization or a proposed method for the various experiments studied in this work. In particular, the DA EGM methods exhibit comparable performance across different choices of D0D_0 and substantially less variation, consistent with their better theoretical constants and reduced sensitivity to initialization. Thus, when prior tuning information is unavailable, a DA EGM method provides a robust default choice. The EGM rules are more sensitive to D^\widehat D, and our sensitivity plots identify ranges of D^\widehat D for which they outperform the competing methods in different problem settings. When a small tuning budget is available, one can run the candidate rules for a limited number of iterations and select the rule and initialization that yield the best value of the relevant performance measure.

All the proposed update rules retain their universal theoretical guarantees; their differences in practice arise from initialization sensitivity. Such variation is common among optimization and VI algorithms. We emphasize that the primary goal of this work is the development of the first universal EGM methods for stochastic VIs under (δ,L)(\delta,L)-continuity, together with the corresponding convergence rates, and show in simulation the methods are competitive. Our goal is not to show uniform empirical dominance across all problems and settings as it requires choosing the right initialization for any algorithm that exists in the literature.

Q) Many experiments (especially in softmax setting) indicate that prior methods perform significantly better than the proposed methods. Do you have any intuition or explanation for that?

R) We have added sensitivity studies on the selection of the initialization parameters D^\widehat D and D0D_0 in Appendix G. Based on these figures, one can select a value of D^\widehat D that performs best in a particular setting for each of the experiments considered, including the softmax problem. When we used an arbitrary initialization for D^\widehat D, DoG performed well in some of the softmax experiments. However, we would like to emphasize that DoG has not been proved to be a universal method; it may simply perform well for that particular problem and setting. By tuning the initialization parameter D^\widehat D, our EGM methods can outperform all the other methods considered for the problems studied here. Nevertheless, as stated in our previous response, this is not the main goal of our work. Our objective is to demonstrate that the proposed methods remain stable and competitive and consistently reduce either the objective function gap or the primal-dual gap, in agreement with our theoretical results.

Q) Minor typo: in line 366 ``Distance-Adaptive EGM''.

R) Thanks for pointing out the typo. We have corrected that.

Q) When should each variant be preferred in theory and in practice?

R) In terms of theory all of our proposed methods are universal. DA EGM has better constants in the convergence rates and hence it is seen in simulations that the sensitivity of the selection of initialization D0D_0 for such methods is very less compared to D^\widehat D for the EGM Rules~1--3. For any algorithm in the literature, there exists no definitive rule or guarantee that a particular algorithm will work to be the best for any problem. Also, from our experiments, we have seen that for any algorithm, a larger step size does not guarantee a faster reduction function value for optimization problems. Hence, as stated above, the best course of action is to run each method for few iterations and see which of the methods perform better.

Q) Why in many experiments the proposed variants perform worse than the state-of-the-art baselines.

R) We would like to emphasize that our methods perform competitively with the other algorithms across all the simulations, and the performance of Rules 1--3 can be further improved by tuning D^\widehat D. We have added a sensitivity analysis of the initialization selection in Appendix G. Nevertheless, even without tuning the initialization, our methods remain competitive. Although DoG performs well in the softmax simulation, as explained previously, it has not been theoretically proved to be universal. For the softmax experiment, we observed that, as the smoothness decreases, using a smaller value of D^\widehat D for EGM Rules 1--3 improves their performance and can enable them to outperform DoG. Moreover, in our min-max VI simulation, our methods perform slightly better than or remain competitive with the other algorithms. However, as stated previously, the main contributions of this work are theoretical developments and new step size selection schemes: we develop the first universal EGM for solving stochastic VIs that can handle the class of (δ,L)(\delta,L)-continuous mappings. Our goal is not to show that we can outperform every competing algorithm on every problem.

Thank you very much for the additional experiments and the detailed answer to my questions. I maintain my positive evaluation of the work.

Regards, Reviewer 5moR

Thank you very much for your positive evaluation and for engaging with our response. We are glad that the additional experiments and detailed clarifications addressed your questions. Since we have made substantial revisions to incorporate the reviewers’ feedback, may we kindly ask whether these changes affect your overall assessment and whether you would consider updating the numerical score if you believe that is appropriate? We fully understand if your current score already reflects your final evaluation.

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

The paper generalizes (δ,L)(\delta,L)-smoothness to variational inequalities. They then develop a line-search-free stochastic extragradient method achieving, for any δ>0\delta>0, the rate

O(L(δ)D2T+DL(δ)δ+σDT)O\left(\frac{L(\delta)D^2}{T}+\frac{D\sqrt{L(\delta)\delta}+\sigma D}{\sqrt T}\right)

without knowing the smoothness parameters or noise variance. Furthermore, they remove the need to know the domain diameter DD, allowing an arbitrary estimate D~>0\widetilde D>0.

Critical strengths
  • Identifies and appears to correct important gaps in the stochastic convergence analysis of Klimza et al. (2024), particularly concerning the expected gap guarantee.
  • Easy to follow and well contextualized within the literature.
Critical weaknesses

The main contributions relative to Klimza et al. (2024) appear to be the generalization to (δ,L)(\delta,L) and unknown diameter, both I which I have concerns regarding:

Generality of (δ,L)(\delta,L)-continuity My main concern is how substantial this generalization is? Since XX is bounded, (δ,L)(\delta,L)-continuity implies Hölder continuity with exponent ν=0\nu=0 and constant H0=L(1)2D2+4L(1)H_0=\sqrt{L(1)^2D^2+4L(1)}.

Moreover, contrary to the claim on page 4, finite sums of Hölder-continuous operators remain Hölder-continuous on bounded domains (with the minimum exponent). Thus, the generalization appears limited in terms of operator classes (apart from potentially discontinuous operators).

The experiments also only consider Hölder-continuous problems. Can the authors provide concrete examples where the (δ,L)(\delta,L) framework yields genuinely sharper guarantees than existing Hölder-based results?

Unknown diameter DD Removing knowledge of DD is useful, particularly through the distance-adaptive variants, but how substantial is this improvement? For many standard bounded domains (which is the setting the paper considers), diameter bounds are readily available. Can the authors demonstrate significant practical benefits when DD is unknown or poorly estimated? In particular, comparisons with Klimza et al. (2024) under varying diameter estimates would strengthen the empirical evaluation (currently the experiments uses knowledge of the diameter by setting D0=0.1DD_0=0.1D).

Questions for authors

See weaknesses.

5 comments

Q) Identifies and appears to correct important gaps in the stochastic convergence analysis of Klimza et al. (2024), particularly concerning the expected gap guarantee.

R) We thank the reviewer for the time to read the manuscript. We would like to add here that we also showed that the update steps in Klimza et al. (2024) won't yield universal rates and convergence guarantees even in the deterministic setting. So we came up with our new update methods and we provided several such examples each of which are universal.

Q) The main contributions relative to Klimza et al. (2024) appear to be the generalization to (δ,L)(\delta,L) and unknown diameter, both I which I have concerns regarding:

R) This statement is not entirely correct. As explained in Appendix A of our manuscript, we show in point (i) that the algorithmic step-size update rules of Klimza et al. (2024) contain issues and cannot provide theoretical convergence guarantees, even for simple H"older-continuous mappings. We also identify problems in their stochastic analysis, along with several additional issues.

Our main contribution is the development of completely new balance-equation step-size schemes, including distance-adaptive variants. Using a residual-based analysis, we establish valid expected convergence guarantees for all the proposed methods and prove that they achieve universal rates for stochastic VIs under the general class of (δ,L)(\delta,L)-continuous mappings.

Q) My main concern is how substantial this generalization is? Since XX is bounded, (δ,L)(\delta,L)-continuity implies H"older continuity with exponent ν=0\nu=0 and constant H0=L(1)2D2+4L(1)H_0=\sqrt{L(1)^2D^2+4L(1)}.

R) We studied the properties and calculus rules of (δ,L)(\delta,L)-continuous mappings where the iterates can lie in any set XX which is not necessarily bounded. However, while analyzing the convergence rates of our methods, we assumed that the set XX is bounded. On a bounded domain XX, it is true that (δ,L)(\delta,L)-continuity implies 0-H"older continuity. But if we model all mappings over a bounded domain with 0-H"older continuity, then we will obtain the worst possible rates and constants which is basically saying that even if can we have a good modeling, we will take the worst modeling possible and it is not advisable.

The purpose of (δ,L)(\delta,L)-continuity is not merely to establish qualitative membership in a larger class. Its main value is that the modulus of continuity L(δ)L(\delta) retains substantially more quantitative information than classifying the entire mapping using the endpoint exponent ν=0\nu=0. Reducing every approximately continuous mapping to a 00-H"older mapping is always possible on a bounded domain, but it can produce a substantially weaker convergence bound. For example, consider \begin{align*} F=F_{\mathrm{Lip}}+F_{\mathrm{bd}}, \end{align*} where FLipF_{\mathrm{Lip}} is Lipschitz continuous with constant L1L_1, while \begin{align*} |F_{\mathrm{bd}}(x)-F_{\mathrm{bd}}(y)|_* \leq L_0. \end{align*} Such a decomposition arises, for example, when a Lipschitz mapping is evaluated with a bounded deterministic perturbation or contains a bounded discontinuous component. Treating the entire mapping only as 00-H"older and assuming D^≈D\widehat D \approx D for EGM (just an example) gives a bound of the form \begin{align*} O\left( \frac{(L_1D+L_0)D}{\sqrt{T}} + \frac{\sigma D}{\sqrt{T}} \right). \end{align*} In contrast, the (δ,L)(\delta,L) calculus preserves the two components through the modulus L(δ)L(\delta) and can yield the rate \begin{align*} O\left( \frac{L_1D^2}{T} + \frac{L_0D}{\sqrt{T}} + \frac{\sigma D}{\sqrt{T}} \right). \end{align*} Thus, the Lipschitz component retains its faster O(1/T)O(1/T) contribution instead of being absorbed into the O(1/T)O(1/\sqrt{T}) rate associated with the minimum H"older exponent. This is the sense in which the (δ,L)(\delta,L) framework can yield a genuinely sharper guarantee, even though both mappings can formally be placed in the ν=0\nu=0 H"older class on a bounded domain. Hence, the (δ,L)(\delta, L)-continuity class is important even over a bounded domain.

Q) Moreover, contrary to the claim on page 4, finite sums of H"older-continuous operators remain H"older-continuous on bounded domains (with the minimum exponent). Thus, the generalization appears limited in terms of operator classes (apart from potentially discontinuous operators).

R) Over a bounded domain XX, if we model sum of H"older-continuous operators as H"older-continuous with the minimum exponent, then again, we would not obtain the desired best rates and constants which can be derived in a similar way as our previous comment. So we do not agree to the reviewer's statement that ``the generalization appears limited". Moreover, as pointed out by the reviewer, we have edited that particular line in page 4 as follows: In particular, the sum of H"older mappings with different H"older exponents is also (δ,L)(\delta,L)-continuous, even though the resulting mapping may not be H"older (Nesterov, 2025, Example 1), where we do not take into account Assumption~2.1.

Since all of our calculus rules and all the properties of (δ,L)(\delta,L)-continuity holds in general as well.

Q) The experiments also only consider H"older-continuous problems. Can the authors provide concrete examples where the (δ,L)(\delta,L) framework yields genuinely sharper guarantees than existing H"older-based results?

R) We do not understand the question properly. If the reviewer is talking about experiments, then we do have other experiments as well. We simulated both optimization (H"older-smooth polyhedral feasibility, softmax, and logistic regression) and Variational Inequality problem (constrained ℓ2\ell_2-regression formulated as a min--max problem). We have also added sensitivity studies of parameter selection D^\widehat D (for EGM Rules 1--3) and D0D_0 (for DA EGM Methods 1--2) for all the experiments in Appendix G.

Now if the reviewer is talking about theoretical rates and guarantees then we have already proved the rates for (δ,L)(\delta,L)-continuous mappings which can be used to model not only H"older continuous operators but also their linear combinations. So one can consider sum of mappings with various H"older continuities which will satisfy our (δ,L)(\delta, L)-continuity, where L(δ)L(\delta) can be computed using calculus rule in Lemma C.2(iii) and Lemma 2.3 (lemma numbers are as per our revised uploaded draft). Then after substituting the value of L(δ)L(\delta) in Theorems 4.1 and F.3, one can similarly try to optimize with respect to δ\delta as done in Corollaries~4.2 and F.4 to obtain sharper guarantees. If we model sum of H"older continuous mappings as H"older continuous as suggested by the reviewer in the last comment, we can never get these sharper rates and also bad constants.

Q) Removing knowledge of DD is useful, particularly through the distance-adaptive variants, but how substantial is this improvement? For many standard bounded domains (which is the setting the paper considers), diameter bounds are readily available. Can the authors demonstrate significant practical benefits when DD is unknown or poorly estimated? In particular, comparisons with Klimza et al. (2024) under varying diameter estimates would strengthen the empirical evaluation (currently the experiments uses knowledge of the diameter by setting D0=0.1DD_0=0.1D).

R) First, we would like to state that the update equation of Klimza et al. (2024) has issues that prevent it from yielding universal convergence guarantees in either the deterministic or stochastic setting. These issues are described in Appendix A of our draft. Hence, we do not see a clear reason to compare our methods with Klimza et al. (2024) in the simulations, since their theoretical guarantees are erroneous and their method is merely heuristic.

The distance-adaptive methods can be initialized with any arbitrary value. We used D0=0.1DD_0=0.1D, but different initializations of D0D_0 perform similarly. We have removed the dependence on DD from Table 1 of our current draft. We have also added initialization-sensitivity studies with varying values of D0D_0 for DA EGM Methods 1 and 2 and D^\widehat D for EGM Rules 1, 2, and 3 in Appendix G. The sensitivity plots show that EGM Rules 1--3 are more sensitive to changes in D^\widehat D than DA EGM Methods 1 and 2 are to changes in D0D_0. These results justify the theoretical constants obtained in our bounds: DA EGM yields better constants and, consequently, exhibits less variation. So if there is poor estimation of diameter, DA EGM will provide more stability and will be less sensitive to the selection of D0D_0. New sensitivity plots in Appendix G also justifies the initialization selection D^\widehat D for various settings that can beat the other comparing algorithms.

But, we would again like to emphasize that the goal of our work is theoretical advancement, as this is the first universal EGM algorithm for stochastic VIs that adapts to any level of smoothness, achieves the desired rates, and remains competitive in the simulations. Our goal is not to guarantee that our methods outperform all other algorithms across every setting and example. We believe that none of the algorithms in the optimization and variational inequality literature provides such guarantees.

Reviewer_6TNSOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the stochastic Extra-Gradient Method (EGM) and proposes universal extra-gradient methods that adapt to the Hölder smoothness, the Lipschitz constant, and the stochastic variance. Preliminary experiments are provided to show the performance of the proposed methods.

Critical strengths

The paper focuses on step-size selection for the stochastic extra-gradient method without prior knowledge of the smoothness parameters or the oracle variance, which is of both theoretical and practical importance. In particular, when line search is expensive, the proposed method has a clear motivation: it balances the local error and the adjustment cost and constructs an explicit adaptive step-size rule.

The paper introduces (δ,L)(\delta,L)-continuity for the VI analysis, which includes Hölder-continuous mappings, and provides convergence guarantees for the expected residual under different exponents. Moreover, the accuracy certificate connects the analysis of convex optimization, saddle-point problems, and monotone VIs. Although there has been previous work in these fields, this unified treatment is new.

Critical weaknesses

The applications and experiments are limited. For all the experiment applications, there are optimization algorithms that attain the same bound. For example, Nesterov's smoothing can be applied to the ℓ2\ell_2-regression problem, and DADA can be applied to the Hölder-smooth polyhedral feasibility problem.

In the stochastic settings, the dominating term is O(1/T)O(1/\sqrt{T}), which means there seems to be no real advantage of the proposed algorithms over SGD. Improvement on the faster order term is of lower priority.

The experimental results are also not strong. The advantage shown in the plots is quite limited.

Questions for authors

No additional question.

3 comments

Q) Although there has been previous work in these fields, this unified treatment is new.

R) We thank the reviewer for taking the time to read our manuscript. Although several previous works have studied this problem, none has established convergence rates that demonstrate universality with respect to the class of H"older-continuous mappings. Moreover, these works assume that the stochastic mapping is uniformly bounded almost surely, which is a strong assumption. Klimza et al. (2024) attempted to design a universal method for H"older-continuous mappings, but their method and analysis contain issues, as described in Appendix A. Hence, to the best of our knowledge, there is no existing universal method for solving VIs. For the first time, we develop multiple EGM update rules for stochastic VIs and prove their universality under the broader class of (δ,L)(\delta,L)-continuous mappings, which encompasses both H"older-continuous mappings and their linear combinations. We also establish the desired convergence-rate guarantees.

Q) The applications and experiments are limited.

R) We would like to reiterate that we have presented four different simulation problems, three involving optimization and one involving a variational inequality. We also emphasize that this is primarily a theoretical work in which we develop, for the first time, universal EGM methods for solving stochastic VIs under the general class of (δ,L)(\delta,L)-continuous mappings. We therefore respectfully disagree with the characterization of our experimental evaluation as ``limited''. Furthermore, in Appendix G of the revised manuscript, we have added sensitivity studies examining the selection of the distance parameters D^\widehat D for EGM Rules 1--3 and D0D_0 for DA EGM Methods 1--2.

Q) For all the experiment applications, there are optimization algorithms that attain the same bound. For example, Nesterov's smoothing can be applied to the ℓ2\ell_2-regression problem, and DADA can be applied to the H"older-smooth polyhedral feasibility problem.

R) We respectfully disagree with the reviewer's characterization. The goal of our work is to develop the first universal EGM methods for solving stochastic VIs under (δ,L)(\delta,L)-continuous mappings. In our experiments, we evaluate the proposed methods on both optimization problems (H"older-smooth polyhedral feasibility, softmax, and logistic regression) and a variational inequality problem (constrained ℓ2\ell_2-regression formulated as a min-max problem). Importantly, standard optimization methods, such as gradient descent-ascent, may fail to converge even for simple monotone VIs, whereas EGM was specifically designed by Korpelevich (1976) to address such problems. We acknowledge that universal methods already exist for optimization problems; we refer to these methods collectively as UGM and compare them with our universal EGM algorithms in the optimization experiments. Importantly, neither Nesterov smoothing nor DADA provides universality guarantees for stochastic convex optimization. We therefore do not fully understand the reviewer’s second comment. DADA has been proved to be universal only for deterministic convex optimization, not for the stochastic setting. Moreover, these methods exploit the presence of a scalar convex objective and therefore do not directly apply to general monotone VIs under the same stochastic mapping-oracle model.

For example, the constrained ℓ2\ell_2-regression experiment is deliberately treated through its stochastic saddle-point formulation, for which we use randomized mapping evaluations. Applying smoothing to the primal objective constitutes a different formulation and oracle model, introduces an additional smoothing or tolerance parameter, and does not address the broader VI problem studied in this paper. Similarly, the H"older-smooth feasibility experiment is an optimization instance used to evaluate automatic adaptation across ν∈{0,0.5,1}\nu\in\{0,0.5,1\}. It is not intended to suggest that no specialized solver exists. Rather, its purpose is to evaluate whether a single parameter-free VI method can adapt across different regularity regimes without knowing the H"older exponent or constant.

The purpose of our experiments is not to establish uniform empirical dominance over existing methods, but to demonstrate that our methods remain stable and competitive and consistently reduce the objective function gap across different smoothness regimes, in agreement with their theoretical universality guarantees. We also show in Appendix G that tuning the parameter D^\widehat D for EGM Rules 1--3 further improves their performance and allows them to outperform all the competing methods considered. Nevertheless, this is not the primary objective or the main novelty of our work.

Q) In the stochastic settings, the dominating term is O(1/T)O(1/\sqrt{T}), which means there seems to be no real advantage of the proposed algorithms over SGD. Improvement on the faster order term is of lower priority.

R) We respectfully disagree with the reviewer's characterization. Stochastic gradient methods typically achieve an O(1/T)O(1/\sqrt{T}) rate using diminishing step-size schedules, which may themselves depend on problem parameters. Works exists in optimization for developing efficient adaptive schemes for stochastic settings which tries to improve the rate terms apart from the unavoidable stochastic O(1/T)O(1/\sqrt{T}) term. More importantly, our setting is that of stochastic monotone VIs, for which plain stochastic gradient (forward) methods are not generally guaranteed to converge; for example, gradient descent-ascent can exhibit cyclic behavior even on simple bilinear saddle-point problems. In contrast, the Extra-Gradient Method is specifically designed for monotone VIs so as to make the method converge for VIs. So we do not understand fully as why reviewer said ``there seems to be no real advantage of the proposed algorithms over SGD".

For stochastic Extra-Gradient Method with bounded-variance oracles, the O(σD/T)O(\sigma D/\sqrt{T}) stochastic term is unavoidable. However, its presence does not imply that the proposed methods offer no advantage. Matching this term shows that our adaptive rules incur no asymptotic penalty despite not knowing the stochastic-oracle variance or the continuity parameters. For a ν\nu-H"older-continuous mapping, our result has roughly the form \begin{align*} O\left( \frac{H_\nu}{T^{(1+\nu)/2}} + \frac{\sigma}{\sqrt{T}} \right), \end{align*} up to some diameter factors. The first term automatically interpolates between the bounded/nonsmooth and Lipschitz regimes and becomes O(L/T)O(L/T) when ν=1\nu=1. It is particularly important in deterministic, low-noise, and pre-asymptotic regimes, whereas every method is subject to the same O(σ/T)O(\sigma/\sqrt{T}) barrier in the noise-dominated regime.

Our methods attain the optimal dimension-independent H"older rates without requiring knowledge of the H"older exponent, continuity constant, or oracle variance. Our distance-adaptive variants also substantially reduce the dependence on an inaccurate initial diameter estimate. More generally, our analysis provides guarantees for VIs with (δ,L)(\delta,L)-continuous mappings. This framework includes H"older-continuous mappings and retains component-specific regularity information for their linear combinations. To the best of our knowledge, this is the first universal EGM framework to establish these guarantees for stochastic monotone VIs.

Q) The experimental results are also not strong. The advantage shown in the plots is quite limited.

R) As highlighted in our previous responses, the main goal and novelty of this work lie in establishing the first universal EGM algorithm for stochastic VIs. Regarding the experiments, our goal is to demonstrate that our methods remain stable and competitive with other methods across various problems without requiring knowledge of any problem parameters. Our goal is not to demonstrate uniform empirical dominance across all problems, because, for any optimization or VI algorithm in the literature, such dominance can be achieved only by tuning its hyperparameters or in our case, its initialization according to the problem setting. We arbitrarily selected the values of D^\widehat D for EGM Rules 1--3 and D0D_0 for DA EGM Methods 1--2 without fine-tuning them, yet we obtained superior performance in some settings. In Appendix~G of the revised manuscript, we have also added sensitivity studies on the selection of D^\widehat D and D0D_0. These studies show the ranges of values for which our algorithms can outperform the other methods. However, demonstrating such empirical dominance is not the main goal of our work.

Dear Reviewer 6TNS,

As the rebuttal period concludes today, we wanted to follow up on our responses. We have made every effort to address your questions and concerns and would appreciate any feedback on whether any issues remain. If our responses and revisions have resolved your concerns, we would be grateful if you would consider revisiting your evaluation. Thank you for your time.

Regards, The Authors

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Summary of Revisions

We thank the reviewers for their feedback. We summarize the main concerns and our corresponding responses below. A detailed point-by-point response is provided under each reviewer’s comments.

  1. Experimental evaluation (Reviewers 6TNS and 5moR). The reviewers raised concerns that our methods do not uniformly outperform the competing algorithms across all experimental settings. We emphasize that this is primarily a theoretical work: to the best of our knowledge, we develop the first universal EGM methods for stochastic VIs under (δ,L)(\delta,L)-continuous mappings and establish the corresponding convergence rates without knowing the continuity parameters or stochastic-oracle variance. The purpose of the experiments is to demonstrate that our methods remain stable and competitive across different problems and smoothness regimes, not to establish uniform empirical dominance. Such dominance cannot generally be guaranteed for optimization or VI algorithms and typically requires problem-specific tuning. Nevertheless, in response to the reviewers' concerns, we have added sensitivity studies in Appendix G for the initialization parameters D^\widehat D in EGM Rules 1--3 and D0D_0 in DA EGM Methods 1--2. These studies show that appropriate choices of D^\widehat D can make our methods outperform all the competing algorithms in certain problem settings. However, establishing empirical dominance is not the main objective of our work. Also, we added a new VI simulation on bilinear saddle-point problem as requested by Reviewer LuRA. The current draft reflects all the changes.

  2. Distinction from Klimza et al. (2024) (Reviewer LuRA). We have clarified in Appendix A that our contribution does not merely correct the stochastic analysis of Klimza et al. (2024). Their step-size update rule cannot provide the claimed universal convergence guarantees even in the deterministic setting, and their stochastic expected-gap analysis contains additional gaps. We therefore develop completely new balance-equation step-size rules (several of them) and establish their expected convergence guarantees through a residual-based analysis.

  3. Revisions to Section 5, Lemma C.2, and Appendix G. We have revised the DA EGM discussion in Section 5 by restoring the balance equations from the appendix to the main text, making it more easier to read and understand. We have also revised the proof of Lemma C.2 to correct several typographical errors. In Appendix G, we have added new simulations results showing the sensitivity of the initialization D^\widehat D and D0D_0 for EGM and DA EGM respectively for all the experiments.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.