- 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 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
- The introduced notion of continuity seems quite general.
- The method is universal and does not require knowledget of the continuity of the mapping and the stochastic-oracle variance.
- 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
- The experiments show that the proposed update rules might perform differently in practice. How should one select the update rule in practice?
- 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?
- Minor typo: in line 366 "Distance-Adaptive EGM"
Questions for authors
- When should each variant be preferred in theory and in practice?
- Why in many experiments the proposed variants perform worse than the state-of-the-art baselines.
- Please refer to the questions in the "Weaknesses" part.
4 comments
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 . 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 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 -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.
We thank the reviewer for the time to read our manuscript.
R) To address this question, we have added sensitivity analyses for the initialization parameter D in EGM Rules 1--3 and for D0 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 D0 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, and our sensitivity plots identify ranges of 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)-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.
R) We have added sensitivity studies on the selection of the initialization parameters D and D0 in Appendix G. Based on these figures, one can select a value of 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, 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, 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.
R) Thanks for pointing out the typo. We have corrected that.
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 D0 for such methods is very less compared to 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.