Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity

Two of the most prominent algorithms for solving unconstrained smooth games\nare the classical stochastic gradient descent-ascent (SGDA) and the recently\nintroduced stochastic consensus optimization (SCO) [Mescheder et al., 2017].\nSGDA is known to converge to a stationary point for specific classes of games,\nbut current convergence analyses require a bounded variance assumption. SCO is\nused successfully for solving large-scale adversarial problems, but its\nconvergence guarantees are limited to its deterministic variant. In this work,\nwe introduce the expected co-coercivity condition, explain its benefits, and\nprovide the first last-iterate convergence guarantees of SGDA and SCO under\nthis condition for solving a class of stochastic variational inequality\nproblems that are potentially non-monotone. We prove linear convergence of both\nmethods to a neighborhood of the solution when they use constant step-size, and\nwe propose insightful stepsize-switching rules to guarantee convergence to the\nexact solution. In addition, our convergence guarantees hold under the\narbitrary sampling paradigm, and as such, we give insights into the complexity\nof minibatching.\n