First-Order Methods for Stochastic Variational Inequality Problems with Function Constraints

References

• [1] Adler C, Kher S (2017) UCI machine learning repository. Accessed May 1, 2025, https://archive.ics.uci.edu/.Google Scholar
• [2] Alizadeh Z, Jalilzadeh A, Yousefian F (2024) Randomized Lagrangian stochastic approximation for large-scale constrained stochastic Nash games. Optim. Lett. 18(2):377–401.Crossref, Google Scholar
• [3] Aravkin AY, Burke JV, Drusvyatskiy D, Friedlander MP, Roy S (2019) Level-set methods for convex optimization. Math. Programming 174:359–390.Crossref, Google Scholar
• [4] Arrow KJ, Debreu G (1954) Existence of an equilibrium for a competitive economy. Econometrica 22(3):265–290.Crossref, Google Scholar
• [5] Ba Q, Pang JS (2022) Exact penalization of generalized Nash equilibrium problems. Oper. Res. 70(3):1448–1464.Link, Google Scholar
• [6] Ben-Tal A, Nemirovski A (2002) Robust optimization–Methodology and applications. Math. Programming 92:453–480.Crossref, Google Scholar
• [7] Ben-Tal A, Nemirovski A (2005) Non-Euclidean restricted memory level method for large-scale convex optimization. Math. Programming 102(3):407–456.Crossref, Google Scholar
• [8] Bertsekas DP (2011) Approximate policy iteration: A survey and some new methods. J. Control Theory Appl. 9(3):310–335.Crossref, Google Scholar
• [9] Boob D, Guzmán C (2024) Optimal algorithms for differentially private stochastic monotone variational inequalities and saddle-point problems. Math. Programming 204:255–297. Google Scholar
• [10] Boob D, Khalafi M (2024) Optimal primal-dual algorithm with last iterate convergence guarantees for stochastic convex optimization problems. Preprint, submitted October 24, https://arxiv.org/abs/2410.18513.Google Scholar
• [11] Boob D, Deng Q, Lan G (2023) Stochastic first-order methods for convex and nonconvex functional constrained optimization. Math. Programming 197(1):215–279.Crossref, Google Scholar
• [12] Dai YH, Wang J, Zhang L (2022) Optimality conditions and numerical algorithms for a class of linearly constrained minimax optimization problems. SIAM J. Optim. 34(3):2883–2916.Google Scholar
• [13] Dang CD, Lan G (2015) On the convergence properties of non-Euclidean extragradient methods for variational inequalities with generalized monotone operators. Comput. Optim. Appl. 60:277–310.Crossref, Google Scholar
• [14] Diakonikolas J (2020) Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. Abernethy J, Agarwal S, eds. Conf. Learn. Theory (PMLR, New York), 1428–1451.Google Scholar
• [15] Facchinei F, Pang JS (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Series in Operations Research and Financial Engineering (Springer, New York).Google Scholar
• [16] Franci B, Grammatico S (2022) Stochastic generalized Nash equilibrium seeking under partial-decision information. Automatica 137:110101.Crossref, Google Scholar
• [17] Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics, International Series in Operations Research & Management Science, vol. 279 (Springer, New York).Crossref, Google Scholar
• [18] Gidel G, Berard H, Vignoud G, Vincent P, Lacoste-Julien S (2019) A variational inequality perspective on generative adversarial networks. 7th Internat. Conf. Learn. Representations (ICLR, Appleton, WI).Google Scholar
• [19] Goodfellow I, Pouget-Abadie J, Mirza M, Xu B, Warde-Farley D, Ozair S, Courville A, Bengio Y (2020) Generative adversarial networks. Comm. ACM 63(11):139–144.Crossref, Google Scholar
• [20] Gu S, Kuba JG, Chen Y, Du Y, Yang L, Knoll A, Yang Y (2023) Safe multi-agent reinforcement learning for multi-robot control. Artificial Intelligence 319:103905.Crossref, Google Scholar
• [21] Hanley JA, McNeil BJ (1982) The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology 143(1):29–36.Crossref, Google Scholar
• [22] Harker PT, Pang JS (1990) Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications. Math. Programming 48(1–3):161–220.Crossref, Google Scholar
• [23] Huang K, Zhang S (2022) New first-order algorithms for stochastic variational inequalities. SIAM J. Optim. 32(4):2745–2772.Crossref, Google Scholar
• [24] Jiang H, Xu H (2008) Stochastic approximation approaches to the stochastic variational inequality problem. IEEE Trans. Automatic Control 53(6):1462–1475.Crossref, Google Scholar
• [25] Jordan MI, Lin T, Zampetakis M (2023). First-order algorithms for nonlinear generalized Nash equilibrium problems. J. Machine Learn. Res. 24(38):1–46.Google Scholar
• [26] Josephy NH (1979) Quasi-Newton methods for generalized equations. Technical Report No. 1966, Wisconsin Univ-Madison Mathematics Research Center, Madison.Google Scholar
• [27] Juditsky A, Nemirovski A, Tauvel C (2011) Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems 1(1):17–58.Link, Google Scholar
• [28] Korpelevich GM (1976) The extragradient method for finding saddle points and other problems. Matematicheskie Metody 12:747–756.Google Scholar
• [29] Koshal J, Nedic A, Shanbhag UV (2012) Regularized iterative stochastic approximation methods for stochastic variational inequality problems. IEEE Trans. Automatic Control 58(3):594–609.Crossref, Google Scholar
• [30] Kotsalis G, Lan G, Li T (2022) Simple and optimal methods for stochastic variational inequalities, I: Operator extrapolation. SIAM J. Optim. 32(3):2041–2073.Crossref, Google Scholar
• [31] Li J, Ren Y, Deng K (2022) FairGAN: GANs-based fairness-aware learning for recommendations with implicit feedback. Laforest F, Troncy R, Simperl E, Agarwal D, Gionis A, Herman I, Médini L, eds. Proc. ACM Web Conf. 2022 (Association for Computing Machinery, New York), 297–307.Google Scholar
• [32] Malitsky Y (2015) Projected reflected gradient methods for monotone variational inequalities. SIAM J. Optim. 25(1):502–520.Crossref, Google Scholar
• [33] Malitsky Y (2020) Golden ratio algorithms for variational inequalities. Math. Programming 184(1):383–410.Crossref, Google Scholar
• [34] Mokhtari A, Ozdaglar AE, Pattathil S (2020) Convergence rate of O(1/k) for optimistic gradient and extragradient methods in smooth convex-concave saddle point problems. SIAM J. Optim. 30(4):3230–3251.Crossref, Google Scholar
• [35] Nemirovski A (2004) Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1):229–251.Crossref, Google Scholar
• [36] Nesterov Y (2007) Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Programming 109(2–3):319–344.Crossref, Google Scholar
• [37] Nesterov Y, Scrimali L (2011) Solving strongly monotone variational and quasi-variational inequalities. Discrete Continuous Dynamical Systems 31(4):1383–1396.Crossref, Google Scholar
• [38] Ouyang Y, Xu Y (2021) Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Math. Programming 185(1):1–35.Crossref, Google Scholar
• [39] Pang JS, Chan D (1982) Iterative methods for variational and complementarity problems. Math. Programming 24(1):284–313.Crossref, Google Scholar
• [40] Pang JS, Scutari G, Palomar DP, Facchinei F (2010) Design of cognitive radio systems under temperature-interference constraints: A variational inequality approach. IEEE Trans. Signal Processing 58(6):3251–3271.Crossref, Google Scholar
• [41] Popov LD (1980) A modification of the Arrow-Hurwicz method for search of saddle points. Math. Notes Acad. Sci. USSR 28:845–848.Google Scholar
• [42] Qi L, Sun D (2002) Smoothing functions and smoothing Newton method for complementarity and variational inequality problems. J. Optim. Theory Appl. 113(1):121–147.Crossref, Google Scholar
• [43] Ralph D, Wright SJ (2000) Superlinear convergence of an interior-point method despite dependent constraints. Math. Oper. Res. 25(2):179–194.Link, Google Scholar
• [44] Robbins H, Monro S (1951) A stochastic approximation method. Ann. Math. Statist. 22(3):400–407.Crossref, Google Scholar
• [45] Shanbhag UV (2013) Stochastic variational inequality problems: Applications, analysis, and algorithms. Theory Driven by Influential Applications, INFORMS TutORials in Operations Research (INFORMS, Catonsville, MD), 71–107.Link, Google Scholar
• [46] Sion M (1958) On general minimax theorems. Pacific J. Math. 8(1):171–176.Crossref, Google Scholar
• [47] Subramanian P (1985) Gauss-Newton methods for the nonlinear complementarity problem. Technical Report No. 2845, Wisconsin Univ-Madison Mathematics Research Center, Madison.Google Scholar
• [48] Tang W, Daoutidis P (2023) Optimal design of control-Lyapunov functions by semi-infinite stochastic programming. 2023 62nd IEEE Conf. Decision Control (CDC) (IEEE, Piscataway, NJ), 7277–7284.Google Scholar
• [49] Tsaknakis I, Hong M, Zhang S (2023) Minimax problems with coupled linear constraints: Computational complexity and duality. SIAM J. Optim. 33(4):2675–2702.Crossref, Google Scholar
• [50] Yang T, Jordan MI, Chavdarova T (2022) Solving constrained variational inequalities via an interior point method. Preprint, submitted June 21, https://arxiv.org/abs/2206.10575.Google Scholar
• [51] Yang S, Li X, Lan G (2024) Data-driven minimax optimization with expectation constraints. Oper. Res. 73(3):1345–1365.Link, Google Scholar
• [52] Ying Y, Wen L, Lyu S (2016) Stochastic online AUC maximization. Lee DD, von Luxburg U, Garnett R, Sugiyama M, Guyon I, eds. NIPS’16: Proc. 30th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 451–459.Google Scholar
• [53] Yousefian F, Nedić A, Shanbhag UV (2014) Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems. 53rd IEEE Conf. Decision Control (IEEE, Piscataway, NJ), 5831–5836.Google Scholar
• [54] Yousefian F, Nedić A, Shanbhag UV (2017) On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems. Math. Programming 165:391–431.Crossref, Google Scholar
• [55] Yu CK, Van Der Schaar M, Sayed AH (2017) Distributed learning for stochastic generalized Nash equilibrium problems. IEEE Trans. Signal Processing 65(15):3893–3908.Crossref, Google Scholar
• [56] Zafar MB, Valera I, Gomez-Rodriguez M, Gummadi KP (2019) Fairness constraints: A flexible approach for fair classification. J. Machine Learn. Res. 20(75):1–42.Google Scholar
• [57] Zhang Z, Lan G (2020) Optimal algorithms for convex nested stochastic composite optimization. Optimal methods for convex nested stochastic composite optimization. Math. Programming 212:1–48.Crossref, Google Scholar