×

Extragradient method with variance reduction for stochastic variational inequalities. (English) Zbl 1365.65179

Summary: We propose an extragradient method with stepsizes bounded away from zero for stochastic variational inequalities requiring only pseudomonotonicity. We provide convergence and complexity analysis, allowing for an unbounded feasible set, unbounded operator, and nonuniform variance of the oracle, and, also, we do not require any regularization. Alongside the stochastic approximation procedure, we iteratively reduce the variance of the stochastic error. Our method attains the optimal oracle complexity \(\mathcal{O}(1/\epsilon^2)\) (up to a logarithmic term) and a faster rate \(\mathcal{O}(1/K)\) in terms of the mean (quadratic) natural residual and the D-gap function, where \(K\) is the number of iterations required for a given tolerance \(\epsilon>0\). Such convergence rate represents an acceleration with respect to the stochastic error. The generated sequence also enjoys a new feature: the sequence is bounded in \(L^p\) if the stochastic error has finite \(p\)-moment. Explicit estimates for the convergence rate, the oracle complexity, and the \(p\)-moments are given depending on problem parameters and distance of the initial iterate to the solution set. Moreover, sharper constants are possible if the variance is uniform over the solution set or the feasible set. Our results provide new classes of stochastic variational inequalities for which a convergence rate of \(\mathcal{O}(1/K)\) holds in terms of the mean-squared distance to the solution set. Our analysis includes the distributed solution of pseudomonotone Cartesian variational inequalities under partial coordination of parameters between users of a network.

MSC:

65K15 Numerical methods for variational inequalities and related problems
49J40 Variational inequalities
49J55 Existence of optimal solutions to problems involving randomness
65Y20 Complexity and performance of numerical algorithms

References:

[1] F. Bach and E. Moulines, {\it Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning}, in Advances in Neural Information Processing Systems, MIT Press, Cambridge, MA, 2011.
[2] P. Billingsley, {\it Convergence of Probability Measures}, Wiley, New York, 1968. · Zbl 0172.21201
[3] R. S. Burachik, A. N. Iusem, and B. F. Svaiter, {\it Enlargement of monotone operators with applications to variational inequalities}, Set-Valued Anal., 5 (1998), pp. 159-180. · Zbl 0882.90105
[4] D. L. Burkholder, B. Davis, and R. F. Gundy, {\it Integral inequalities for convex functions of operators on martingales}, in Proceedings of the 6th Berkeley Symposium on Mathematical Statistics and Probability, vol. 2, 1972, pp. 223-240. · Zbl 0253.60056
[5] R. H. Byrd, G. M. Chin, J. Nocedal, and Y. Wu, {\it Sample size selection in optimization methods for machine learning}, Math. Program., 134 (2012), pp. 127-155. · Zbl 1252.49044
[6] X. Chen, R. J. B. Wets, and Y. Zhang, {\it Stochastic variational inequalities: Residual minimization smoothing sample average approximations}, SIAM J. Optim., 22 (2012), pp. 649-673. · Zbl 1263.90098
[7] Y. Chen, G. Lan, and Y. Ouyang, {\it Accelerated Schemes for a Class of Variational Inequalities}, preprint, , 2014.
[8] G. Deng and M. C. Ferris, {\it Variable-number sample-path optimization}, Math. Program., 117 (2009), pp. 81-109. · Zbl 1165.90013
[9] J. C. Duchi, P. L. Bartlett, and M. J. Wainwright, {\it Randomized smoothing for stochastic optimization}, SIAM J. Optim., 22 (2012), pp. 674-701. · Zbl 1267.65063
[10] R. Durret, {\it Probability: Theory and Examples}, Cambridge University Press, Cambridge, UK, 2010. · Zbl 1202.60001
[11] F. Facchinei and J.-S. Pang, {\it Finite-Dimensional Variational Inequalities and Complementarity Problems}, Springer, New York, 2003. · Zbl 1062.90002
[12] M. C. Ferris and J. S. Pang, {\it Engineering and economic applications of complementarity problems}, SIAM Rev., 39 (1997), pp. 669-713. · Zbl 0891.90158
[13] M. P. Friedlander and G. Goh, {\it Tail Bounds for Stochastic Approximation}, preprint, ., 2013.
[14] G. Gürkan, A. Y. Özge, and S. M. Robinson, {\it Sample-path solution of stochastic variational inequalities}, Math. Program., 84 (1999), pp. 313-333. · Zbl 0972.90079
[15] S. Ghadimi, G. Lan, and H. Zhang, {\it Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization}, Math. Program., Ser. A, 155 (2016), pp. 267-305. · Zbl 1332.90196
[16] T. Homem-de-Mello, {\it Variable-sample methods for stochastic optimization}, ACM Trans. Model. Comput. Simul., 13 (2003), pp. 108-133. · Zbl 1390.65003
[17] A. Iusem, A. Jofré, and P. Thompson, {\it Incremental constraint projection methods for monotone stochastic variational inequalities}, submitted. · Zbl 1477.65101
[18] H. Jiang and H. Xu, {\it Stochastic approximation approaches to the stochastic variational inequality problem}, IEEE Trans. Automat. Control, 53 (2008), pp. 1462-1475. · Zbl 1367.90072
[19] A. Juditsky, A. Nemirovski, and C. Tauvel, {\it Solving variational inequalities with stochastic mirror-prox algorithm}, Stoch. Systems, 1 (2011), pp. 17-58. · Zbl 1291.49006
[20] A. Kannan and U. V. Shanbhag, {\it Distributed computation of equilibria in monotone Nash games via iterative regularization techniques}, SIAM J. Optim., 22 (2012), pp. 1177-1205. · Zbl 1281.90072
[21] A. Kannan and U. V. Shanbhag, {\it The pseudomonotone stochastic variational inequality problem: Analytical statements and stochastic extragradient schemes}, presented at the American Control Conference, Portland, OR, 2014.
[22] A. Kannan and U. V. Shanbhag, {\it The Pseudomonotone Stochastic Variational Inequality Problem: Analysis and Optimal Stochastic Approximation Schemes}, preprint, , 2014.
[23] A. J. King and R. T. Rockafellar, {\it Asymptotic theory for solutions in statistical estimation and stochastic programming}, Math. Oper. Res., 18 (1993), pp. 148-162. · Zbl 0798.90115
[24] I. V. Konnov, {\it Equilibrium Models and Variational Inequalities}, Elsevier, New York, 2007. · Zbl 1140.91056
[25] G. M. Korpelevich, {\it The extragradient method for finding saddle points and other problems}, Ekon. Mat. Metody, 12 (1976), pp. 747-756. · Zbl 0342.90044
[26] J. Koshal, A. Nedić, and U. V. Shanbhag, {\it Regularized iterative stochastic approximation methods for stochastic variational inequality problems}, IEEE Trans. Automat. Control, 58 (2013), pp. 594-609. · Zbl 1369.49012
[27] H. J. Kushner and G. G. Yin, {\it Stochastic Approximation and Recursive Algorithms and Applications}, Springer, New York, 2003. · Zbl 1026.62084
[28] C. Marinelli and M. Röckner, {\it On the maximal inequalities of Burkholder, Davis and Gundy}, Expo. Math., 34 (2016), pp. 1-26. · Zbl 1335.60064
[29] R. D. Monteiro and B. F. Svaiter, {\it On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean}, SIAM J. Optim., 20 (2010), pp. 275-287. · Zbl 1230.90200
[30] R. D. Monteiro and B. F. Svaiter, {\it Complexity of variants of Tseng’s modified F-B splitting and Korpelevich’s methods for hemivariational inequalities with applications to saddle-point and convex optimization problems}, SIAM J. Optim., 21 (2011), pp. 1688-1720. · Zbl 1245.90155
[31] A. Nemirovski, {\it Prox-method with rate of convergence \(\mathcal{O}(1/t)\) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems}, SIAM J. Optim., 15 (2004), pp. 229-251. · Zbl 1106.90059
[32] A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro, {\it Robust stochastic approximation approach to stochastic programming}, SIAM J. Optim., 19 (2009), pp. 1574-1609. · Zbl 1189.90109
[33] Y. Nesterov, {\it Primal-dual subgradient methods for convex problems}, Math. Program., 120 (2009), pp. 261-283. · Zbl 1191.90038
[34] U. Ravat and U. V. Shanbhag, {\it On the Existence of Solutions to Stochastic Quasi-Variational Inequality and Complementarity Problems}, preprint, , 2013. · Zbl 1375.90231
[35] H. Robbins and S. Monro, {\it A stochastic approximation method}, Ann. Math. Stat., 22 (1951), pp. 400-407. · Zbl 0054.05901
[36] H. Robbins and D. O. Siegmund, {\it A convergence theorem for non negative almost supermartingales and some applications}, in Optimizing Methods in Statistics (Proceedings of a Symposium at Ohio State University, Columbus, Ohio), J. S. Rustagi, ed., Academic Press, New York, 1971, pp. 233-257. · Zbl 0286.60025
[37] A. Shapiro, D. Dentcheva, and A. Ruszczynski, {\it Lectures on Stochastic Programming: Modeling and Theory}, MOS-SIAM Ser. Optim. SIAM, Philadelphia, 2009. · Zbl 1183.90005
[38] U. V. Shanbhag and J. Blanchet, {\it Budget constrained stochastic approximation}, in Proceedings of the Winter Simulation Conference, IEEE, 2015.
[39] M. Wang and D. Bertsekas, {\it Incremental constraint projection methods for variational inequalities}, Math. Program. Ser. A, 150 (2015), pp. 321-363. · Zbl 1315.65058
[40] H. Xu and D. Zhang, {\it Stochastic Nash equilibrium problems: Sample average approximation and applications}, Comput. Optim. Appl., 55 (2013) pp. 597-645. · Zbl 1281.91046
[41] H. Xu, {\it Sample average approximation methods for a class of stochastic variational inequality problems}, Asia-Pac. J. Oper. Res., 27 (2010), pp. 103-119. · Zbl 1186.90083
[42] H. Xu, {\it Uniform exponential convergence of sample average random functions under general sampling with applications in stochastic programming}, J. Math. Anal. Appl., 368 (2010), pp. 692-710. · Zbl 1196.90089
[43] F. Yousefian, A. Nedić, and U. V. Shanbhag, {\it Self-tuned stochastic approximation schemes for non-Lipschitzian stochastic multi-user optimization and Nash games}, IEEE Trans. Automat. Control, 61 (2016), pp. 1753-1766. · Zbl 1359.91010
[44] F. Yousefian, A. Nedić, and U. V. Shanbhag, {\it Optimal robust smoothing extragradient algorithms for stochastic variational inequality problems}, presented at IEEE Conference on Decision and Control, 2014. · Zbl 1457.90102
[45] F. Yousefian, A. Nedić and U. V. Shanbhag, {\it On Smoothing, Regularization and Averaging in Stochastic Approximation Methods for Stochastic Variational Inequalities}, preprint. . · Zbl 1457.90102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.