A Modified Popov Algorithm for Non-Monotone and Non-Lipschitzian Stochastic Variational Inequalities

In this paper, we propose a modified Popov algorithm with variable sample-size for solving non-monotone and non-Lipschitzian stochastic variational inequality problems. It is inspired by an improved Popov algorithm for solving deterministic variational inequality problems, proposed by Malitsky and Semenov (Malitsky and Semenov in Cybern. Syst. Anal. 50:271–277, 2014), and a stochastic Popov method for solving stochastic variational inequality problems, developed by Vankov et al. (Last iterate convergence of Popov method for non-monotone stochastic variational inequalities, 2023). In contrast to the stochastic Popov method, the proposed algorithm incorporates a variable sample-size strategy and, crucially, conducts a projection onto a half-space followed by a projection onto the constraint set in each iteration, rather than two projections onto the constraint set. These modifications have the potential to reduce computational cost, particularly when the computation of projection onto the constraint set is expensive, and thus improve performance. Subsequently, we discuss the almost sure convergence of the algorithm, its sublinear and linear convergence rate, and the oracle complexity. Finally, we present numerical experiments to demonstrate the competitiveness of the algorithm and further apply it to solve a signal estimation problem.