acceptodds
Under review as a conference paper at ICLR 2027

Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities

Abstract

We analyze a stochastic algorithm with Halpern-type anchoring for constrained convex-concave problems and monotone variational inequalities. This single-loop and single-call algorithm uses one unbiased sample of the gradient operator at every iteration, to be applicable to monotone games with noisy feedback. With denoting the iteration counter, we prove an anytime last-iterate convergence rate of for both the gradient-mapping norm and restricted gap, bypassing the constrained-anytime bottleneck in the literature. Specializing then to multi-point oracles, we use variance reduction to achieve the rate with an anytime single-loop algorithm using samples per iteration. Our results allow constrained problems with a potentially unbounded feasible set; as well as a structured class of stochastic oracles whose variance need not be uniformly bounded.

Primary area:
optimization
Keywords:
anytime algorithms, last-iterate, variational inequalities, stochastic algorithms, Halpern iteration

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_JP2EOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies stochastic monotone variational inequalities and provides new convergence analyses for two methods using Halpern-type anchoring under different oracle models. Motivated by learning in games with one stochastic gradient observation per round, the first method uses one oracle call per iteration. In the constrained setting, the analysis improves the anytime last-iterate convergence rate for the restricted gap from O(t−1/5)O(t^{-1/5}) to O(t−1/4)O(t^{-1/4}), and establishes the same rate for the gradient mapping norm. The main insight in the analysis is to transfer deterministic convergence bounds to stochastic iterates using a comparison of their trajectories and the Lipschitz continuity of the gradient mapping.

Moreover, the paper studies a second setting, permitting two oracle evaluations at different points using the same sample, the authors analyze a method incorporating STORM variance reduction. Assuming mean-square smoothness, they prove an anytime O(t−1/2)O(t^{-1/2}) last-iterate residual rate.

Critical strengths

The authors address an important class of problems and obtain improved convergence rates over those existing in the literature.

Critical weaknesses

There are some minor mistakes in the math / proofs. None of them break the theoretical results, but they do harm readability of the work, and should thus be addressed.

  • Proof of Lemma B.3: above (B.11) the authors divide by 1−βt1 - \beta_t. Algorithm 2 states that β0=1\beta_0 = 1, in which case this would lead to a division by 0. Probably, this is fixed by simply restricting t≥1t \geq 1, or handling t=0t = 0 separately, but this should be addressed nonetheless.
  • Bottom of page 5: E[ζt]=0\mathbb{E}[\zeta_t] = 0 is assumed, but this does not imply that Et[ζt]=0\mathbb{E}_t[\zeta_t]=0 for all tt as required for the theory. I suppose ζt\zeta_t is assumed to be independent of Ft\mathcal{F}_t, in which case they are equivalent, but this should be stated.
  • Section 2.1: Superscripts and subscripts are mixed: “ii-th player is denoted as ziz_i”. This should be ziz^i not to clash with the notation for iteration counts. This should also be updated in G(z)G(z) below.
  • Proof of Corollary D.2: What is B\mathcal{B} In the statement and proof? This should be U\mathcal{U}? Also, the set CC appearing in the proof should be ZZ?
  • Top of page 15: Undefined symbol ss appears. Based on Fact D.4 and (A.7) this should be t+a+1t+a+1.
  • End of proof of Lemma 2.7: The authors write: “Using (2.6) gives …, which gives (2.6)”
  • Proof of corollary 2.2: Again, undefined B\mathcal{B} appears, which should be U\mathcal{U}?
  • Proof of corollary 2.2: The gap in the lhs, should be gapU\text{gap}_\mathcal{U}?

In addition the authors should carefully proofread their manuscript, as there were several grammatical and spelling errors.

Questions for authors

Only a minor question: In (2.1), do you also assume the bounded-variance case, i.e., do you set B=0B = 0?

3 comments

Thank you for the constructive feedback and for your time to carefully read our work! We really appreciated your detailed feedback.

“In (2.1), do you also assume the bounded-variance case, i.e., do you set B=0B=0?”

We do not require B=0B=0 strictly speaking, since we bound this term by compact domain assumption. With compact domains, we have uniformly bounded variance even with B>0B>0. We use compactness in this section only for direct comparison with Ito et al. (2026). We have clarified this in Section 2.1 and included the dependence on BB explicitly in the gap and regret bounds. Our results in all the other sections do not require any bounded domain or bounded variance assumptions.

“There are some minor mistakes in the math / proofs. None of them break the theoretical results, but they do harm readability of the work, and should thus be addressed.”

We thank the reviewer for pointing out these issues. Indeed, as the reviewer stated, none of the issues affect the validity of our results, but we agree that they cause confusion. We are sorry for the confusion, we fixed all the issues in our revision.

  • Proof of Lemma B.3. Sorry for this typo at Lem. B.3! This was supposed to be the restatement of Lem. 3.5 where we restricted to t≥1t\geq 1, so 1−βt>01-\beta_t >0 throughout the proof. We agree this was confusing and it is now fixed. This bound is used for t≥1t\geq 1 in the proof of Lem. B.1 where the case t=0t=0 is handled in the beginning separately.

  • Bottom of page 5. Indeed, you are right that the intended assumption is conditional unbiasedness, as stated in Assumption 1.2. We corrected Section 2.1 to use Et\mathbb{E}_t.

  • Section 2.1. We have corrected the notation to ziz^i for the ii-th player’s action and update the following definition of G(z)G(z).

  • Proof of Corollary D.2. The compact set is U\mathcal U, and the feasible set is ZZ. We have replaced B\mathcal B by U\mathcal U in the statement and prof. The remaining projC⁡\operatorname{proj_C} is also replaced by projZ⁡\operatorname{proj_Z}. Top of page 15. We have replaced ss by t+a+1t+a+1 in the estimation (line 812).

  • End of proof of Lemma 2.7. We have corrected the final sentence to state that the estimate gives a uniform bound on E∣∣zt−z0∣∣2\mathbb{E}||z_t-z_0||^2.

  • Proof of Corollary 2.2. Yes! We have corrected the maximum in (C.1) to be taken over u∈Uu \in \mathcal U.

  • Proof of Corollary 2.2. Yes! We have corrected the left-hand side of (C.1) to use gap⁡U\operatorname{gap}_{\mathcal U}.

We really appreciated the reviewer’s detailed comments, which have helped us improve the readability of the paper. We hope that these corrections would help you reconsider your evaluation for our presentation. Can you please let us know if you have any remaining concerns?

Dear authors, thank you for your answers. I have no further questions.

Dear Reviewer JP2E,

Thank you for your follow-up message! We would be glad to discuss further if any more questions come up; to do our best to address reservations you may have about acceptance of our work.

Best regards, Authors

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

This paper provides last iterate convergence guarantee for solving variational inequality problems using natural residual, and the restricted gap function. First they analyze a single-call stochastic Halpern method and proves O(t−1/4)\mathcal{O}(t^{-1/4}) convergence rate for solving constrained VI. Next they improve the rates to O(t−1/2)\mathcal{O}(t^{-1/2}) using STORM variance reduction. However, for the second convergence rate the authors use stronger assumptions.

Critical strengths
  • The paper proposes last iterate convergence rate for solving constrained variational inequality problems.
  • The presentation of paper is good.
  • The authors use weak assumption on gradient estimates.
  • The algorithm does not require multiple loos or increasing mini-batches.
  • The assumption 1.2 holds without bounded domain assumption.
Critical weaknesses
  • The z⋆z^\star in equation 1.1 is not unique.
  • The last iterate results are theoretically interesting. However, I do not understand the practical importance of these results.
  • Line 81. The authors should explain why ∥Gρ(z)∥\| \mathcal{G}_{\rho}(z) \| vanishes only if equation 1.1 holds for every zz.
  • I do not understand why z⋆z^\star is unique. If the z⋆z^\star is not unique then the numerators of Theorem 2.1 and 3.2 which contains the term ∥z0−z⋆∥\| z_0 - z^\star \| are not well defined.
  • The experiments of the paper is poor. This paper requires more thorough comparison with other algorithms.
Questions for authors

Please check the weakness section.

5 comments
AuthorsOpenReview ↗

Response to Reviewer 4mf9, Part 1/2

We thank the reviewer for the comments. However, we respectfully disagree with their evaluation of our work, since in our reading, the listed weaknesses do not point to any major weakness to justify a score of 1.

In fact, the review itself states that

“presentation of paper is good”

and

“the last iterate results are theoretically interesting”

which in our reading, are inconsistent with a “clear reject” rating. We argue below the importance of our results in practice and reply to other points:

Nonuniqueness of the solution. Nonuniqueness of the solution does not make our bounds ill-defined.

”The z⋆z^\star in equation 1.1 is not unique.”

“I do not understand why z⋆z^\star is unique. If the z⋆z^\star is not unique then the numerators of Theorem 2.1 and 3.2 which contains the term ∣∣z0−z⋆∣∣||z_0-z^\star|| are not well defined.”

Uniqueness is not required for either theorem. We work under only monotonicity assumption (that is, convex-concave min-max problems). Assumption 1.1 only requires a nonempty solution set. In particular, we can fix any solution z⋆z^\star, and both theorems hold with respect to this choice. The quantity ∣∣z0−z⋆∣∣||z_0-z^\star|| is a well-defined constant, depending on an arbitrary solution z⋆z^\star chosen in the analysis.

Since the bounds hold for distance to any solution, we can replace this by the distance of the initial point to the solution set. We add this remark to our revision in our Section 1.1.

Indeed, this convention is very common in the line of work our submission belongs to:

Another choice of solution may give a different valid upper bound, but this does not make either bound ill-defined. We have clarified immediately after Assumption 1.1 that our statements hold for any choice of solution z⋆z^\star to (1.1).

Gradient mapping. We first remark that this is a classical result, see for example the p. 94 of the textbook [Facchinei & Pang, 2003].

This follows directly from the definition of the proximal operator in (1.8). Indeed, for any ρ>0\rho > 0,

Gρ(z)=0  ⟺  \mathcal{G}_{\rho}(z) = 0 \iff

z=proxρr(z−ρG(z))  ⟺  z = prox_{\rho r} (z-\rho G(z) ) \iff

\iff 0 \in G(z) + \partial r(z).$$ Thus, the gradient mapping vanishes at $z$ if and only if $z$ solves (1.1). We have added this explanation immediately after the definition of the gradient mapping in Section 1. Thank you for the suggestion. > “The last iterate results are theoretically interesting. However, I do not understand the practical importance of these results.” **Last-iterate guarantees help explain the practical behaviour**. In practical settings, last iterate is used, whereas a majority of existing theoretical results only show rates on the average or a randomly selected iterate. These results do not explain what happens in practice, whereas ours take one step in doing so. Indeed, Algorithms 1 and 2 of Pethick et al. (2023a) plot the last iterate in their experiments (verified from their code). Using the last iterate in practice is also explicitly mentioned by Section 5 of Cutkosky and Orabona (2019). Similarly, Sec E.1 and Sec E.2 of Chen and Luo (2024) states that they replace the randomized output with the last iterate for better empirical performance. The corresponding guarantees in these works are for randomly selected iterates and do not contain guarantees for the last iterate. **Our results provide convergence rates for the last iterate, thus giving theoretical support for this common practice.** **A new method, simpler with faster rates**. Moreover, our analysis based on last-iterate guarantees lead to a new method in Section 3 that is simpler than similar single-loop methods in the literature: Pethick et al., 2023a and Alacaoglu et al., 2025. Moreover, we not only show guarantees on the last-iterate for a simpler method, we also **improve the complexity from $O(\varepsilon^{-4})$ times $\tilde{O}(\varepsilon^{-2})$ in Section 3**, under the same assumption as these two earlier works. **Applications in game theory**. Last-iterate guarantees also control the actions actually played, which is important for learning in games, as we explained in our Introduction and Section 2.1. For example, Example 2.2 of Abe et al. (2025) consider Cournot competition, where firms choose production quantities that determine the market price and its profits. A guarantee for the average of past profiles does not guarantee that the current profile is near equilibrium. This importance of guarantees on the actual sequence of play is also emphasized by Mertikopoulos and Zhou (2019). We refer to discussions at pages 3 and 4 of Mertikopoulos and Zhou (2019). Are our explanations help in addressing your concerns? We will be happy to discuss further.
AuthorsOpenReview ↗

Response to Reviewer 4mf9, Part 2/2

“The experiments of the paper is poor. This paper requires more thorough comparison with other algorithms.”

We respectfully disagree with this assessment.

First, we emphasize that the main contribution of our paper is theoretical and the numerical experiments are included to supplement these results. Indeed, there are many published ICLR papers whose main contribution is theoretical results.

Moreover, our experiments already include the prior benchmark settings in the (published) literature on the area of our paper, including the matrix games studied by Abe et al. (2025) and robust least squares studied by Cai et al. (2022a). Indeed, some closely related (published) theoretical works whose results have a similar nature to ours, including Cai et al. (2024) and Neu and Okolo (2024), do not even include empirical results.

To be specific, Section 4 compares both of our methods with the existing methods with anytime last-iterate rates. Appendix E also includes a hard convex-concave quadratic game in Figure 5, additional optimality measures in Figures 2-3, and sensitivity to ten different initializations for our methods in Figure 7. Thus, the submission already contains comparisons with three relevant algorithms across several problems and optimality measures.

The statement that the experiments are “poor” does not specify which comparisons are missing or which aspect of the evaluation is insufficient.

Could the reviewer please identify a specific additional algorithm or missing comparison that is needed to evaluate our claims? We are happy to discuss such a concrete concern.

Based on suggestion of other reviewers, we added new experiments, two on the main text:

  • Fig 1, bottom left: We added a quadratic problem with unbounded domain
  • Fig 1, bottom right: We added an unconstrained problem to be able to apply other algorithms from the literature: Cai et al., 2022a, Chen and Luo, 2024, Pethick et al., 2023a. Let us remark that the guarantees in these earlier works do not apply in this case since they assume bounded variance and the oracle we choose for affine operators do not satisfy bounded variance. Please see our discussion in Sec 1.1 on this. Let us also remark that Pethick et al., 2023a only has rate guarantees for a randomly selected iterate, and not the last iterate.

We include an additional problem in the appendix.

We hope that these clarifications address your concerns and that you reconsider your evaluations of our work. We look forward to engaging further for any follow-up concerns.

AuthorsOpenReview ↗

Reminder for the discussion deadline

Dear Reviewer 4mf9,

We would like to kindly remind you of the upcoming discussion deadline in 2 days.

We believe that our responses addressed all the points in your review.

Could you please let us know if your concerns are addressed, or if you have further questions?

We would appreciate the opportunity to engage in a meaningful discussion with you before the deadline.

Best regards, Authors

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

The paper studies the last iterate convergence of stochastic methods for monotone variational inequalities and constrained convex-concave problems. Under appropriate regularity and noise conditions, the paper obtains a convergence rate of O(t−1/4)O(t^{-1/4}) for the basic modification of their method, without knowing the time horizon in advance. Then the authors suggest a variance reduced version of their algorithm and obtain convergence rate of order O(t−1/2)O(t^{-1/2}) under the stronger oracle assumption. The authors also provide some numerical results for matrix games and least squares problem.

Critical strengths

The paper obtains the rate of order O(t−1/4)O(t^{-1/4}) which seems to improve the previous known results for the same setting of order O(t−1/5)O(t^{-1/5}). This result does not require to know time horizon in advance. The main elements of the proof are also well explained in the main text of the paper. I did not check the full details, but overall the proofs look convincing.

Critical weaknesses

The experiments provide limited evidence for the broader domain and noise assumptions. Every example uses bounded feasible sets (simplexes or boxes). Thus they do not directly illustrate the benefit of allowing unbounded domains and variance that grows with the iterates, that is, the Assumption 1.2. I would recommend the authors to include such an example to the camera-ready. At the same time, I do not consider it as a critical weakness.

Questions for authors
  1. Is it possible to generalize your approach in order to address Markovian stochasticity? There were several papers addressing this question for VIs but under more restrictive assumptions (bounded domain or strong monotonicity, e.g. [1,2]). Are there any principal technical difficulties?

  2. What is the source for the name of the Blum-Gladyshev variance condition? It would be good if the authors can add it to the paper, I am not sure that I met this name before, yet the assumption is frequently used.

  3. Are the bounds of theorem 2.1 and 3.2 non-improvable? Is it possible to provide some lower bound mathcing the upper ones from these theorems?

  4. Numerical results: see weakness.

References

[1] Mathieu Even. Stochastic gradient descent under Markovian sampling schemes. In ICML-2023.

[2] Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Naumov, Eric Moulines. First order methods with markovian noise: from acceleration to variational inequalities. In NeurIPS-2023

3 comments

Thank you for the constructive comments and thoughtful questions!

“Is it possible to generalize your approach in order to address Markovian stochasticity?

This is an interesting direction. The main difficulty is that the conditional bias introduced by Markovian bias will affect several estimates. For Algorithm 1, (conditional) unbiasedness cancels the noise term in (A.9) in the proof of Lemma 2.7. For Algorithm 2, the proof of Lemma 3.4, also uses the unbiasedness to cancel noise cross term between the previous estimator error and the new oracle noise. This cancellation explicitly appears on line 1151. We would guess that by using suitable (and mostly standard in the Markovian literature) exponential mixing assumption on the underlying Markov-chain, one can extend our analysis. Of course, one would have to check the technical details. We can add this direction as an open question in our Conclusions section, if the reviewer suggests so.

“What is the source for the name of the Blum-Gladyshev variance condition? It would be good if the authors can add it to the paper, I am not sure that I met this name before, yet the assumption is frequently used.”

We agree with the reviewer that the assumption deserves more introduction. We are sorry for the omission of the original references to the works of Blum and Gladyshev from 1950s and 1960s. We added these references and stated explicitly where the name comes from before Assumption 1.2. The literature did not explicitly name this condition to our knowledge until recently, and our terminology is based on the work of Alacaoglu et al. (2025, Section 1).

“Are the bounds of theorem 2.1 and 3.2 non-improvable? Is it possible to provide some lower bound mathcing the upper ones from these theorems?”

For Theorem 2.1, we do not establish a lower bound under the single-call, anytime requirements. Our step size choice balances the deterministic residual and the stochastic comparison term in (A.1). Whether this rate can be improved under the same assumptions with any other single-call, anytime method remains open, and would be an interesting direction for future work. It does seem like the rate we obtain is the best-possible one with the current analysis framework of comparing the stochastic trajectory and deterministic trajectory, an idea initially studied by Sohrabi et al., 2026.

For Theorem 3.2, the O(ε−2)O(\varepsilon^{-2}) complexity is optimal. Indeed, Foster et al. (2019, Theorem 4) shows Ω(σ2/ε2)\Omega(\sigma^2 / \varepsilon^2) lower bound for smooth convex minimization, which is a special case of our problem with r=0r=0. Moreover, they use additive noise which satisfies our Assumption 3.1. Our dependence on ε\varepsilon is hence tight under this oracle model.

"The experiments provide limited evidence for the broader domain and noise assumptions.”

Thank you for the suggestion! We agree that experiment on an unbounded domain would help explain this aspect of our results better. Our current experiments focus on constrained problems and comparisons with existing anytime methods. Based on your suggestion, we added experiments for constrained problems without bounded domains and also unconstrained problems. The new results are marked with a red color and appear at the bottom row of Fig 1 as well as at Appendices E.2 and E.3 with further details (Figures 4, 6). We see a similar behavior for our method relative to existing methods, for these problems too.

On the other hand, we want to quickly emphasize that we improve the existing complexity results for single-loop algorithms even in the bounded-variance case (even when we allow large batch sizes or random-iterate outputs): we refer to Tables 1 and 2.

Thank you again for your constructive review! Can you please let us know if you have any follow-up questions? We will be glad to clarify further.

Reviewer_bypyOpenReview ↗

Post rebuttal comment

Dear authors,

Thanks a lot for your rebuttal.

A. I do not insist on including anything on Markovian noise VIs here, but yes, it can be an interesting direction for future research

B,C (Blum-Gladyshev and lower bounds) - please add some discussions to the camera ready version

D experiments: also please add to camera-ready if appropriate. I understand though that this is a theoretical paper, so experimental part is not the main one.

Overall I remain positive about the paper. I enjoyed reading it and keep supporting acceptance.

Dear Reviewer bypy,

Thank you very much for your response to our rebuttal and for your continued support!

A. We will add the Markovian extension as an open problem in our concluding section.

B, C. Definitely! If you have any feedback about the discussion we have added for BG assumption to the revised version of our work (uploaded on this page together with our rebuttal where changes are highlighted in red color), we would be happy to incorporate your suggestions.

D. Definitely, as well! We included these results in our uploaded revised manuscript in this page as well (marked by red color). We are happy to revise if you have suggestions on these.

We are glad to hear that you enjoyed reading our work! We would be happy to discuss further if you would have follow-up questions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Highlighting one of our contributions

Dear Reviewers,

First, thank you for engaging with us during the discussion phase! We did our best to address your comments and will be glad to respond to any other comments we receive before the deadline.

As the discussion period is about to end, we would like to highlight and contextualize one of our key contributions for the last stage of the review process.

Our results in Section 3 give the optimal complexity for stochastic convex-concave min-max problems with a single-loop algorithm for the first time. Prior to our work, the best-complexities, for single-loop algorithms (irrespective of which iterate was outputted), were:

  • For unconstrained stochastic convex-concave problems, due to [Cai et al., 2022a]: O(ϵ−3)O(\epsilon^{-3})
  • For constrained stochastic convex-concave problems, due to [Tran-Dinh and Nguyen-Trung, 2026]: O(ϵ−10/3)O(\epsilon^{-10/3})

Additionally, both results required bounded variance and used large batch-sizes.

We improve this to O(ϵ−2)O(\epsilon^{-2}) with our single-loop Algorithm 2; the optimal first-order complexity for stochastic convex-concave problems under Assumptions 1.1, 1.2, 3.1 (according to the lower bounds from [Foster et al., 2019]). While doing so, we handle constrained problems or potentially unbounded variance, use 22 calls to the stochastic oracle per iteration, and prove the guarantee for the last iterate.

Previously, this optimal complexity was only obtained via multi-loop algorithms and it has been open, since the work of Chen and Luo 2024 (first appeared online in 2022), to achieve this complexity with a single-loop algorithm. Our Section 3 solves this problem.

Single-loop algorithms are preferred in the literature of our work since they are easy to implement and tune. Moreover, the previous works solving the same problem often implemented their method to output the last iterate in their numerical experiments (we provided precise references in Part 1 of our first response to Reviewer 4mf9).

Thank you,

Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.