# New First-Order Algorithms for Stochastic Variational Inequalities

Source: [New First-Order Algorithms for Stochastic Variational Inequalities](<https://www.sota2.com/research/paper/68fa58481e209131ce9acca4>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T15:14:33.507Z

Authors: Kevin Huang, Shuzhong Zhang

Published: 2021-07-18T02:02:31.000Z

## Abstract

In this paper, we propose two new solution schemes to solve the stochastic strongly monotone variational inequality problems: the stochastic extra-point solution scheme and the stochastic extra-momentum solution scheme. The first one is a general scheme based on updating the iterative sequence and an auxiliary extra-point sequence. In the case of deterministic VI model, this approach includes several state-of-the-art first-order methods as its special cases. The second scheme combines two momentum-based directions: the so-called heavy-ball direction and the optimism direction, where only one projection per iteration is required in its updating process. We show that, if the variance of the stochastic oracle is appropriately controlled, then both schemes can be made to achieve optimal iteration complexity of $\\mathcal{O}\\left(\\kappa\\ln\\left(\\frac{1}{\\epsilon}\\right)\\right)$ to reach an $\\epsilon$-solution for a strongly monotone VI problem with condition number $\\kappa$. We show that these methods can be readily incorporated in a zeroth-order approach to solve stochastic minimax saddle-point problems, where only noisy and biased samples of the objective can be obtained, with a total sample complexity of $\\mathcal{O}\\left(\\frac{\\kappa^2}{\\epsilon}\\ln\\left(\\frac{1}{\\epsilon}\\right)\\right)$

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Stochastic Minimax Optimization on Theoretical Analysis](<https://www.sota2.com/research/sota/stochastic-minimax-optimization-on-theoretical-analysis.md>): Stochastic Minimax Optimization; Theoretical Analysis; Sample Complexity: 1.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2107.08341>)

[PDF](<https://arxiv.org/pdf/2107.08341.pdf>)