# SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities

arXiv: https://arxiv.org/abs/2210.05994 · HTML: https://mlsanity.com/paper/2210.05994/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 32 of its 41 references that are in the map.
- First posted on arXiv 12 Oct 2022.

## Builds on (most cited first, 30 of 32)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [FreeLB: Enhanced Adversarial Training for Natural Language Understanding](https://mlsanity.com/paper/1909.11764/) (2019)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [Better Theory for SGD in the Nonconvex World](https://mlsanity.com/paper/2002.03329/) (2020)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization](https://mlsanity.com/paper/2008.10898/) (2020)
- [Adversarial Training for Large Neural Language Models](https://mlsanity.com/paper/2004.08994/) (2020)
- [On the convergence of single-call stochastic extra-gradient methods](https://mlsanity.com/paper/1908.08465/) (2019)
- [A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent](https://mlsanity.com/paper/1905.11261/) (2019)
- [Reducing Noise in GAN Training with Variance Reduced Extragradient](https://mlsanity.com/paper/1904.08598/) (2019)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling](https://mlsanity.com/paper/2003.10162/) (2020)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity](https://mlsanity.com/paper/2107.00052/) (2021)
- [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015)
- [Stochastic Gradient Descent-Ascent: Unified Theory and New Efficient Methods](https://mlsanity.com/paper/2202.07262/) (2022)
- [Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning](https://mlsanity.com/paper/1402.4419/) (2014)
- [Revisiting Stochastic Extragradient](https://mlsanity.com/paper/1905.11373/) (2019)
- [Stochastic Extragradient: General Analysis and Improved Rates](https://mlsanity.com/paper/2111.08611/) (2021)
- [New Convergence Aspects of Stochastic Gradient Algorithms](https://mlsanity.com/paper/1811.12403/) (2018)
- [Stochastic Recursive Gradient Algorithm for Nonconvex Optimization](https://mlsanity.com/paper/1705.07261/) (2017)
- [Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithms](https://mlsanity.com/paper/2010.13112/) (2020)
- [Inexact SARAH Algorithm for Stochastic Optimization](https://mlsanity.com/paper/1811.10105/) (2018)
- [SAGA with Arbitrary Sampling](https://mlsanity.com/paper/1901.08669/) (2019)
- [Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity](https://mlsanity.com/paper/2205.15136/) (2022)

## Abstract (arXiv)

Variational inequalities are a broad formalism that encompasses a vast number of applications. Motivated by applications in machine learning and beyond, stochastic methods are of great importance. In this paper we consider the problem of stochastic finite-sum cocoercive variational inequalities. For this class of problems, we investigate the convergence of the method based on the SARAH variance reduction technique. We show that for strongly monotone problems it is possible to achieve linear convergence to a solution using this method. Experiments confirm the importance and practical applicability of our approach.