Efficient Stochastic Algorithms for Continual Finite-Sum Variational Inequalities

This paper considers the continual finite-sum variational inequalities. Specifically, we seek a sequence $\mathbf{z}\_1^{\ast },\dots ,\mathbf{z}\_n^{\ast }$ which corresponds to the solutions of prefix-sum variational inequalities $\{\frac{1}{i}\sum \_{j=1}^i⟨F\_j(\mathbf{z}\_i^{\ast }),\mathbf{z}-\mathbf{z}\_i^{\ast }⟩\ge 0\}\_{i=1}^n$, where each component operator $F\_j:\mathcal{Z}\to \mathbb{R}$ is strongly-monotone, and the feasible set $\mathcal{Z}\subseteq {\mathbb{R}}^d$ 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.