{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T10:30:23Z","timestamp":1789727423473,"version":"4.0.1"},"reference-count":52,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:p>In this paper, we propose two new solution schemes to solve the stochastic strongly monotone variational inequality (VI) 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 a 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$. As a specific application to stochastic VI, we demonstrate how to incorporate a zeroth-order approach for solving stochastic minimax saddle-point problems in our schemes, where only noisy and biased samples of the objective can be obtained, with a total sample complexity of $\\mathcal{O}\\left(\\frac{\\kappa}{\\epsilon}\\right)$.<\/jats:p>","DOI":"10.1137\/21m1441778","type":"journal-article","created":{"date-parts":[[2022,11,14]],"date-time":"2022-11-14T11:10:42Z","timestamp":1668424242000},"page":"2745-2772","source":"Crossref","is-referenced-by-count":14,"title":["New First-Order Algorithms for Stochastic Variational Inequalities"],"prefix":"10.1137","volume":"32","author":[{"given":"Kevin","family":"Huang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5838-1676","authenticated-orcid":true,"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2022,11,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9467-7"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1161-4"},{"key":"atypb3","volume-title":"Training GANs with Optimism, preprint, https:\/\/arxiv.org\/abs\/1711.00141","author":"Daskalakis C.","year":"2017"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2409256"},{"key":"atypb5","volume-title":"Finite-Dimensional Variational Inequalities and Complementarity Problems","author":"Facchinei F.","year":"2007"},{"key":"atypb6","unstructured":"X. Gao,\n                      Low-Order Optimization Algorithms: Iteration Complexity and Applications\n                      , Ph.D. thesis, University of Minnesota, Minneapolis, MN, 2018."},{"key":"atypb7","volume-title":"A Variational Inequality Perspective on Generative Adversarial Networks, preprint, https:\/\/arxiv.org\/abs\/1802.10551","author":"Gidel G.","year":"2018"},{"key":"atypb8","first-page":"2672","volume-title":"Advances in Neural Information Processing Systems","author":"Goodfellow I.","year":"2014"},{"key":"atypb9","volume-title":"New First-Order Algorithms for Stochastic Variational Inequalities, preprint, https:\/\/arxiv.org\/abs\/2107.08341","author":"Huang K.","year":"2021"},{"key":"atypb10","volume-title":"A Unifying Framework of Accelerated First-Order Approach to Strongly Monotone Variational Inequalities, preprint, https:\/\/arxiv.org\/abs\/2103.15270","author":"Huang K.","year":"2021"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1137\/15M1031953"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/17M1144799"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/WSC40007.2019.9004836"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.925853"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1287\/10-SSY011"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-019-00120-x"},{"key":"atypb17","first-page":"747","volume":"12","author":"Korpelevich G.","year":"1976","journal-title":"Metody"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2012.2215413"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/20M1381678"},{"key":"atypb20","volume-title":"New Sampling Complexity, and Generalized Problem Classes, preprint, https:\/\/arxiv.org\/abs\/2102.00135","author":"Lan G.","year":"2021"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492919000060"},{"key":"atypb22","first-page":"907","volume-title":"Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (PMLR)","author":"Liang T.","year":"2019"},{"key":"atypb23","volume-title":"Min-max Optimization without Gradients: Convergence and Applications to Adversarial ML, preprint, https:\/\/arxiv.org\/abs\/1909.13806","author":"Liu S.","year":"2019"},{"key":"atypb24","first-page":"154","volume":"4","author":"Martinet B.","year":"1970","journal-title":"Rev. Fr. d'Inform. Rech. Oper. S\u00e9r. Rouge"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1326-9"},{"key":"atypb26","volume-title":"Optimistic Mirror Descent in Saddle-Point Problems: Going the Extra (Gradient) Mile, preprint, https:\/\/arxiv.org\/abs\/1807.02629","author":"Mertikopoulos P.","year":"2018"},{"key":"atypb27","volume-title":"A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach, preprint, https:\/\/arxiv.org\/abs\/1901.08511","author":"Mokhtari A.","year":"2019"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/19M127375X"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"atypb30","first-page":"543","volume":"269","author":"Nesterov Y.","year":"1983","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"atypb31","volume-title":"Appl. Optim. 87","author":"Nesterov Y.","year":"2004"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0034-z"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.3934\/dcds.2011.31.1383"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-015-9296-2"},{"key":"atypb35","first-page":"1416","volume-title":"Advances in Neural Information Processing Systems","author":"Palaniappan B.","year":"2016"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(64)90137-5"},{"key":"atypb37","first-page":"845","volume":"28","author":"Popov L. D.","year":"1980","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729586"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1137\/0314056"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1251-y"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-0995-5"},{"key":"atypb42","volume-title":"Online and Bandit Algorithms for Nonstationary Stochastic Saddle-Point Optimization, preprint, https:\/\/arxiv.org\/abs\/1912.01698","author":"Roy A.","year":"2019"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"atypb44","first-page":"1703","volume":"18","author":"Shamir O.","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"atypb45","first-page":"71","volume-title":"INFORMS","author":"Shanbhag U. V.","year":"2013"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1016\/0377-0427(94)00094-H"},{"key":"atypb47","volume-title":"Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities, preprint, https:\/\/arxiv.org\/abs\/2001.07819","author":"Wang Z.","year":"2020"},{"key":"atypb48","volume-title":"Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence, preprint, https:\/\/arxiv.org\/abs\/2006.09361","author":"Xu T.","year":"2020"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1109\/WSC.2013.6721484"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2014.7040302"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1175-y"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01660-z"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1441778","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:15:44Z","timestamp":1787336144000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1441778"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,14]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["10.1137\/21M1441778"],"URL":"https:\/\/doi.org\/10.1137\/21m1441778","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,14]]}}}