acceptodds
Under review as a conference paper at ICLR 2027

Efficient Stochastic Algorithms for Continual Finite-Sum Variational Inequalities

Abstract

This paper considers the continual finite-sum variational inequalities. Specifically, we seek a sequence which corresponds to the solutions of prefix-sum variational inequalities , where each component operator is strongly-monotone, and the feasible set is convex and compact. We propose an efficient stochastic algorithm that finds a sequence of -approximate solutions for the continual finite-sum variational inequalities. In particular, our approach sparsely constructs the full operator across all stages, and it leverages a novel extragradient iteration to achieve a sharper incremental oracle complexity compared with existing methods. Furthermore, we conduct numerical experiments that demonstrate the effectiveness of our approaches.

Primary area:
optimization
Keywords:
continual optimization, variational inequality

Reviews

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

This paper studies prefix-sum variational inequalities. The authors propose CSVRG, which extends the work of (Mavrothalassitis et al., 2024) in the minimization setting to the VI setting. Further, they also provide an analysis for an extragradient inspired variant CSVRE. Some numerical experiments showcase the performance of the proposed methods.

Critical strengths

To the best of my knowledge, the proofs contain no major errors and the obtained results under the stated assumptions make sense.

Critical weaknesses

The main (critical) weakness is that the assumptions are too restrictive: compact domain as well as uniformly bounded gradients. In this setting, we could just use standard stochastic methods periodically since the distance between solutions of the prefix-sum problems goes down as shown in Lemma C.1. Doing this eliminates the (linear) dependence on nn, which is called SGD-sparse in (Mavrothalassitis et al., 2024) . This also makes the connection to continual learning more difficult to interpret. In particular, if after some point, the solutions do not change much, then learning has effectively stopped.

Minor comments:

  • In the abstract line 15, R\mathbb{R} should be Rd\mathbb{R}^d. Similar in Definitions 3.1-3.2 on line 172
  • Line 459: Nemirovski (2004) and Korpelevich (1976) are not valid citations for SGDA
  • Line 588: The book of Nesterov is single-author, now the author of this citation reads Nesterov et al.
  • Expectations should be handled more rigorously. For example, in Lemma 5.2, it is now unclear over what the expectation in the right-hand side is (since zz is arbitrary). It would be useful to define the appropriate filtrations.
  • The setup of the experiments (especially for the standard methods SGD, SVRG, etc..) is not entirely clear to me. How are these adapted to the prefix-sum problem. Could you elaborate on this? Currently, L-SVRE achieves already quite good results at 0 IO calls in Figure 2. In general, I do not agree with “clear and consistent superiority” on larger datasets. It would be beneficial to include an SGD-sparse like method also.
  • The step on line 841 requires a sufficiently large iteration number. In particular, i>1/αi > 1 / \alpha.
Questions for authors

See weaknesses.

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

This paper develops stochastic algorithm for continual finite sum variational inequality problems. The continual learning problems appear when we aim to build a continuously updated model that performs equally well on new and past data. In this work, the authors propose continual stochastic variance-reduced gradient (CSVRG) and continual stochastic variance-reduced extragradient (CSVRE) methods to solve these problems. Moreover they provide theoretical convergence guarantees of these algorithms. Finally they provide numerical experiments to compare the performance of their proposed algorithm with existing ones to solve these class of problems.

Critical strengths
  • The class of problem is interesting.
Critical weaknesses
  • The presentation of the paper is poor. The paper lacks a lot of citations. For example, there is no citation on the first page, whereas almost each and every line requires a citation.
  • In Problem 1.1 and 1.2, authors claim the min-max problem and the variational inequality problems are 'equivalent'. This requires a rigorous proof or a citation to a paper which has already proved it.
  • The uniqueness of the solution z∗z^* is never discussed in the paper. I do not why the solution of problem in equation (1) is unique. This requires a proof.
  • Authors use ∥zk−z⋆∥2\| z_k - z^\star \|^2 as the convergence metric. However, if the solution z∗z^* is not unique then I do not understand the convergence metric ∥zk−z⋆∥2\| z_k - z^\star \|^2. Most likely, it should have been the distance to the solution set. In general, the analysis of monotone variational inequality problems in a constrained set is done through a Gap function, which does not require the solution to be unique.
  • Author mention [1] in the third row of Table 1 and provide their convergence guarantee. However, [1] provides rates only for monotone problems. Please correct me if I am wrong and point me to the exact location where they have provided the rate of convergence you have listed in the table.
  • In theorem 5.6, the authors suddenly use $ E[ \mu | z_k - z^\star |^2] $ as the convergence metric and derive convergence rate in Theorem 5.6, Corollary 5.7. However, they report this same convergence rate in Table 1 row 5 saying the convergence metric used is E[∥zk−z⋆∥2]E[\| z_k - z^\star \|^2].
  • The experiments are not promising either.
  • In section 6.1 the authors provide minimization problem as an example. I doubt if anyone wants to convert a minimization problem to a variational inquality problem and solve. If the authors are considering minimization problem, then they should comapre with state of the art algorithms in minimization like Adam, AdamW, Muon, Scion.
  • For section 6.2, there are variance reduced version of stochastic extragradient algorithms as well. However, they were never used for comparison in the paper.

[1] Stochastic variance reduction for variational inequality methods. A Alacaoglu, Y Malitsky - Conference on Learning Theory, 2022

Questions for authors

See the weakness section.

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

The paper establishes stochastic algorithms for continual finite-sum Variational Inequality (VI) problems. The authors analyze the Continual Stochastic Variance Reduced Gradient (CSVRG) method for strongly monotone VIs, establishing improved complexity results with respect to prior variance-reduced methods. In addition, a new stochastic algorithm, the Continual Stochastic Variance-Reduced Extragradient (CSVRE) method, is proposed, extending CSVRG and incorporating extragradient steps. Convergence guarantees for smooth, strongly monotone continual VIs are provided, indicating that the proposed method outperforms the prior baselines when the number of stages nn is large. Numerical experiments in ridge regression, robust linear regression and fairness-aware binary classification corroborate the theoretical results.

Critical strengths

S1) The authors provide improved convergence guarantees for the extension of the prior CSVRG method to continual VIs, outperforming the variance-reduced methods of the related literature. S2) A novel extragradient method (CSVRE) is introduced along with convergence guarantees, establishing an even better method in terms of stochastic oracles for strongly monotone and smooth VIs. S3) The paper is well-written and easy to follow for the reader. S4) There is substantial comparison with prior works and the new results seem to outperform the prior guarantees for large-stage settings.

Critical weaknesses

W1) The assumption that the norm of each FiF_i is bounded seems stringent. Could the authors elaborate if the current proof technique works with relaxed assumptions and whether this condition is used in prior works? W2) Table 1 comparing the different algorithms should incorporate also the prior work of Mavrothalassitis et al. [1], based on which the CSVRG algorithm is built. In addition, it would be useful if the lower bound from the same work is incorporated so that the reader can appreciate the tightness of the established rate for the proposed algorithms. W3) The term hih_i is not defined in line 4 (Algorithm 2) and line 6 (Algorithm 3).

[1] Efficient Continual Finite-Sum Minimization, I. Mavrothalassitis, S. Skoulakis, L. Dadi, V. Cevher

Questions for authors

Q1) Could you provide the intuition behind the weighted averaging introduced additionally to the extrapolation step that the classical extragradient method incorporates? Should this be considered as an extrapolation step with a different step size? Q2) Can your method be extended to CSVRE with a different extrapolation and update step size?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.