2014/03/21 by Farzad Yousefian, Angelia Nedić, Yousefian, Farzad +3 · 1 citation
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Engineering · #Economic and Environmental Valuation #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Risk and Portfolio Optimization #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1403.5591
openalex publication_date 2014/03/21 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We consider stochastic variational inequality problems where the mapping is\nmonotone over a compact convex set. We present two robust variants of\nstochastic extragradient algorithms for solving such problems. Of these, the\nfirst scheme employs an iterative averaging technique where we consider a\ngeneralized choice for the weights in the averaged sequence. Our first\ncontribution is to show that using an appropriate choice for these weights, a\nsuitably defined gap function attains the optimal rate of convergence cal\nO\(\(1)/(\√(k))\). In the second part of the paper, under an\nadditional assumption of weak-sharpness, we update the stepsize sequence using\na recursive rule that leverages problem parameters. The second contribution\nlies in showing that employing such a sequence, the extragradient algorithm\npossesses almost-sure convergence to the solution as well as convergence in a\nmean-squared sense to the solution of the problem at the rate cal\nO\(\(1)/(k)\). Motivated by the absence of a Lipschitzian\nparameter, in both schemes we utilize a locally randomized smoothing scheme.\nImportantly, by approximating a smooth mapping, this scheme enables us to\nestimate the Lipschitzian parameter. The smoothing parameter is updated per\niteration and we show convergence to the solution of the original problem in\nboth algorithms.\n