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

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

heading: 1 Introduction
text: Motivated from the recent interest in solving adversarial formulations in machine learning such as generative adversarial networks (GANs) [Goodfellow et al., 2014], we consider in this paper a more abstract formulation of the problem and focus on solving the following unconstrained stochastic variational inequality (VI) problem:2
Find x∗ ∈ Rd such that ξ(x∗) = 1 n n∑ i=1 ξi(x ∗) = 0, (1)
where each ξi : Rd → Rd is Lipschitz continuous. Further, we assume that the problem (1) has a unique3 solution x∗ and that the operator ξ is µ-quasi-strongly monotone: there is a µ ≥ 0 such that:
〈ξ(x), x− x∗〉 ≥ µ‖x− x∗‖2 ∀x ∈ Rd (2) ∗Corresponding author: nicolasloizou1@gmail.com. †Canada CIFAR AI Chair. 2While our presentation focuses on this finite-sum structure, most of our convergence results can easily be adapted to the general stochastic setting (see App. D). Also, we do not use the full power of variational inequalities that usually have constraints [Harker and Pang, 1990], but standard algorithms for (1) are coming from this literature [Gidel et al., 2018].
3This assumption can be relaxed; but for simplicity of exposition we enforce it.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
If µ = 0, then we say that ξ satisfies the variational stability condition: 〈ξ(x), x− x∗〉 ≥ 0 [Hsieh et al., 2020]. In the variational inequality literature, condition (2) is also known as strong stability condition [Mertikopoulos and Zhou, 2019] or as strong Minty variational inequality (MVI) [Diakonikolas et al., 2021, Song et al., 2020].
Problem (1) generalizes the solution of several types of stochastic smooth games [Facchinei and Kanzow, 2007, Scutari et al., 2010, Mertikopoulos and Zhou, 2019]. The simplest example is the unconstrained min-max optimization problem (also called a zero-sum game):
min x1∈Rd1 max x2∈Rd2
1
n n∑ i=1 gi(x1, x2) , (3)
where each component function gi : Rd1×Rd2 → R is assumed to be smooth. Here, ξi represents the appropriate concatenation of the block-gradients of gi: ξi(x) := (∇x1gi(x1, x2);−∇x2gi(x1, x2)), where x := (x1;x2). Solving (1) then amounts to finding a stationary point x∗ = (x∗1;x ∗ 2) for (3), which under a convex-concavity assumption for gi for example, implies that it is a global solution for the min-max problem. More generally, we might seek the pure Nash equilibrium of a k-players game, where each player j is simultaneously trying to find the action x∗j which minimizes with respect to
xj ∈ Rdj their own cost function 1n ∑n i=1 f (j) i (xj , x−j), while the other players are playing x−j , which represents x = (x1, . . . , xk) with the component j removed. Here, ξi(x) is the concatenation over all possible j’s of∇xjf (j)i (xj , x−j). Such finite sum formulations appear in several machine learning applications such as generative adversarial networks (GANs) [Goodfellow et al., 2014], robust learning [Wen et al., 2014] or even some formulations of reinforcement learning [Pfau and Vinyals, 2016]. A standard algorithm that has been used to solve (1) is the stochastic version of the classical gradient method [Dem’yanov and Pevnyi, 1972, Nemirovski et al., 2009] or its variance reduced version [Balamurugan and Bach, 2016], that we call stochastic gradient descent-ascent (SGDA) in this paper.4 More recently, Mescheder et al. [2017] analyzed some limitations of the gradient method in the context of GAN training and proposed an alternative efficient algorithm which could be used to solve (1) that they called consensus optimization (CO), which combines gradient updates with the minimization of ‖ξ(x)‖2. While the practical version of their algorithm for large n is stochastic (SCO, that randomly samples i’s) and displayed good performance [Mescheder et al., 2017], the only global convergence rate guarantees existing in the literature so far is only for the deterministic variant [Azizian et al., 2020, Abernethy et al., 2021].
The classical results from the stochastic VI literature are inappropriate for several reasons. First, a uniform bound over x on the variance E [ ‖ξi(x)− ξ(x)‖2 ] is typically assumed to get convergence guarantees (see e.g. Nemirovski et al. [2009], Gidel et al. [2018], Mertikopoulos and Zhou [2019], Yang et al. [2020], Lin et al. [2020b]), but this is not compatible with the unconstrained aspect of (1). For example, suppose gi is a quadratic function, then the variance typically goes to infinity as x→∞. More appropriate relaxed assumptions have been considered to prove the convergence of other algorithms for (1) such as the stochastic extragradient method [Hsieh et al., 2020, Mishchenko et al., 2020] and its variance-reduced version [Chavdarova et al., 2019], or the stochastic Hamiltonian gradient method [Loizou et al., 2020], but not yet to the best of our knowledge for SGDA nor SCO. Second, the classical analysis for SGDA [Nemirovski et al., 2009] typically considers the convergence of the average of the iterates rather than for the last-iterate. However, as pointed out among others by Daskalakis et al. [2018] and Chavdarova et al. [2019], getting last-iterate convergence is important to apply the methods on potentially non-monotone problems such as GANs, where averaging is not appropriate. The only non-asymptotic last iterate convergence result for SGDA that we are aware of is Lin et al. [2020b], which focuses on a different class of problems (not assuming quasi-strong monotonicity) but it relies on strong assumptions on E [ ‖ξi(x)‖2 ] (see Section 4).
In this paper, we address both of these issues. We generalize the recent improved analysis of SGD [Gower et al., 2019] to the case of unconstrained stochastic variational inequality (1), and prove the last-iterate convergence for both SGDA and SCO without requiring any bounded variance assumption. We focus on quasi-strongly monotone VI problems, a class of structured non-monotone operators for which we are able to provide tight convergence guarantees and avoid the standard issues (cycling and divergence of the methods) appearing in the more general non-monotone regime.
4We use this suggestive name motivated from the min-max formulation (3), though we also call SGDA the simple update xk+1 = xk − αξik (x k) to solve (1) in the more general non-zero sum game scenario.
Main Contributions. The key contributions of this work are summarized as follows: • We propose the expected co-coercivity (EC) assumption, which is the appropriate generalization
of the expected smoothness assumption from Gower et al. [2019] to Problem (1). We explain the benefits of EC and show that is strictly weaker than the bounded variance assumption and “growth conditions” previously used for the analysis of stochastic algorithms for (1).
• Using the EC assumption, we prove the first last-iterate convergence guarantees for stochastic gradient descent-ascent (SGDA) on (1) without any unrealistic noise assumption. We show a linear convergence rate to a neighborhood of x∗ when constant step-size is used, and a O(1/k) rate to the exact solution when using a decreasing step-size rule. For the latter, we propose a theoretically motivated switching rule from a constant to a decreasing step-size to get faster convergence.
• Using the EC assumption, we provide the first convergence analysis of a stochastic variant (SCO) of the consensus optimization (CO) algorithm proposed by Mescheder et al. [2017] and previously used to trained GANs. In particular, we prove last-iterate convergence for SCO, for both constant and decreasing step-sizes. As a corollary of our results, we obtain an improved convergence analysis for the deterministic CO. Furthermore, we explain how the update rule of the stochastic Hamiltonian gradient descent [Loizou et al., 2020] is a special case of the SCO and show that in this scenario, our analysis matches the theoretical guarantees presented in Loizou et al. [2020].
• Inspired by recent results from the optimization literature [Gower et al., 2019], we give the first stochastic reformulation of the variational inequality problem (1) which enables us to provide convergence guarantees of SGDA and SCO under the arbitrary sampling paradigm [Richtárik and Takáč, 2016]. This allows us to give insights into the complexity of minibatching.
2 Arbitrary Sampling: Stochastic Reformulation of Problem (1)
In this work, we provide theorems through which we can analyze all minibatch variants of the two algorithms under study, SGDA and SCO. To do this, we construct a so-called “stochastic reformulation” of the variational inequality problem (1). Our approach is inspired by recently proposed stochastic reformulations of standard optimization problems, like the empirical risk minimization in Gower et al. [2019] and linear systems in Richtárik and Takác [2020], Loizou and Richtárik [2020a,b].
In each step of our algorithms, we assume we are given access to unbiased estimates g(x) ∈ Rd of the operator such that E [g(x)] = ξ(x). For example, we can use a minibatch to form an estimate of the operator such as g(x) = 1b ∑ i∈S ξi(x), where S ⊂ {1, . . . , n} will be chosen uniformly at random and |S| = b. To allow for any form of minibatching, we use the arbitrary sampling notation g(x) = ξv(x) := 1n ∑n i=1 viξi(x), where v ∈ Rn+ is a random sampling vector drawn from some distribution D such that ED[vi] = 1, for i = 1, . . . , n. Note that the unbiasedness follows immediately from this definition of the sampling vector: ED[ξv(x)] = 1n ∑n i=1 ED[vi]ξi(x) = ξ(x). Thus, with each user-defined distribution D, we are able to introduce a stochastic reformulation of problem (1) as follows:
Find x∗ ∈ Rd such that ED [ ξv(x ∗) := 1
n n∑ i=1 viξi(x ∗)
] = 0. (4)
Since ξv(x) as an unbiased estimate of the operator ξ(x), we can now use stochastic (simultaneous) gradient descent-ascent (SGDA) to solve (4) as follows:
xk+1 = xk − αkξvk(xk) , (5) where vk ∼ D is sampled i.i.d at each iteration and αk > 0 is a stepsize. We highlight that in our analysis, we allow to select any distribution D that satisfies ED[vi] = 1 ∀i, and for different selection of D, (5) yields different interpretation as an SGDA method for solving the original problem (1). In this work, we mostly focus on the b–minibatch sampling, however note that our analysis holds for every form of minibatching and for several choices of sampling vectors v.
Definition 2.1 (Minibatch sampling). Let b ∈ [n]. We say that v ∈ Rn is a b–minibatch sampling if for every subset S ∈ [n] with |S| = b, we have that P [ v = nb ∑ i∈S ei ] = 1/ ( n b ) := b!(n−b)!n!
By using a double counting argument, one can show that if v is a b–minibatch sampling, it is also a valid sampling vector (ED[vi] = 1) [Gower et al., 2019]. See Gower et al. [2019] for other choices of sampling vectors v.

heading: 3 Expected Co-coercivity and Connection to Other Assumptions
text: Before introducing the condition of expected co-coercivity, we first review some details on cocoercivity, an intermediate notion between monotonicity and strong monotonicity [Zhu and Marcotte, 1996], and explain where it belongs as assumption in the literature of variational inequalities and min-max optimization.
Co-coercive operators. The co-coercive condition is relatively standard in operator splitting literature [Davis and Yin, 2017, Vũ, 2013] and for variational inequalities [Zhu and Marcotte, 1996]. It was used to analyze the celebrated forward-backward algorithm (a.k.a, proximal gradient) [Lions and Mercier, 1979, Chen and Rockafellar, 1997, Palaniappan and Bach, 2016] that is known not to converge for general monotone operators [Bauschke et al., 2011].
Definition 3.1 (Co-coercivity / Co-coercive around w∗). We say that an operator ξ is `–co-coercive if there exist ` > 0 such that,a ‖ξ(x)− ξ(y)‖2 ≤ `〈ξ(x)− ξ(y), x− y〉 ∀x, y ∈ Rd. If there existw∗ ∈ Rd and ` > 0 such that ‖ξ(x)−ξ(w∗)‖2 ≤ `〈ξ(x)−ξ(w∗), x−w∗〉 ∀x ∈ Rd . then we say that the operator ξ is `–co-coercive around w∗. Note that in the last definition the point w∗ is not necessarily a point where ξ(w∗) = 0.
Note that from Cauchy-Swartz’s inequality, one can get that a `-co-coercive operator is `-Lipschitz. In single-objective minization, one can show the converse statement by using convex duality. Thus, a gradient of a function is L–co-coercive if and only if the function is convex and L-smooth (i.e. L-Lipschitz gradients) [Bauschke et al., 2011]. However, in general, a L-Lipchitz operator is not L–co-coercive. What we can show instead is that a L-Lipschitz and µ-strongly monotone operator is `–co-coercive with ` ∈ [L,L2/µ] [Facchinei and Pang, 2007]. Note that both ranges of the spectrum may occur. For instance, Chavdarova et al. [2019] present a sufficent condition in zero-sum games to have ` = O(L). Note that one can easily show that a sum of co-coercive operators is also co-coercive. Let us now provide a proposition summarizing the implications between (strong) monotonicity and co-coercivity.
Proposition 3.2. For a L-Lipschitz operator ξ, the following implications hold:
µ-strongly monotone =⇒ L2µ -co-coercive =⇒ monotone ⇓ ⇓ ⇓ µ-quasi-strongly monotone =⇒ L2µ -co-coercive around x∗ =⇒ variational
stability condition
Let us also note that while a `-co-coercive operator is always `-Lipschitz continuous, it is possible for an operator to be `-co-coercive around x∗ and not be Lipschitz continuous. This highlights the wider applicability of the `-co-coercivity around x∗ assumption that is all we need for several of our convergence results, in contrast to the Lipschitz continuity of ξ which is typically assumed in the variational inequality literature. In Appendix A.6, we provide such example of a µ-quasi strongly monotone operator that is `-co-coercive around x∗, which is not monotone nor Lipschitz continuous.

heading: 3.1 Expected Co-coercivity (EC)
text: In our analysis of SGDA and SCO, we rely on a generic and remarkably weak assumption that we call expected co-coercivity (EC). In this section, we formally define EC, provide sufficient conditions for it to hold and relate it to the existing gradient assumptions.
Assumption 3.3 (Expected Cocoercivity). We say that ξ is `ξ–co-coercive in expectation with respect to a distribution D if there exists `ξ > 0 such that
ED [ ‖ξv(x)− ξv(x∗)‖2 ] ≤ `ξ〈ξ(x), x− x∗〉 ∀x ∈ Rd . (EC)
For simplicity, we will write ξ ∈ EC(`ξ) to say that EC holds and we will refer to `ξ as the expected co-coercivity constant.
aNote that in our definition we consider the inverse of the co-coercive constant from Lions and Mercier [1979] which is the constant ` such that 〈ξ(x)− ξ(y), x− y〉 ≥ `‖ξ(x)− ξ(y)‖2.
The convergence results in this paper will depend on the following operator noise at x∗ that is finite for any reasonable sampling distribution D for the sampling vector v:
σ2 := ED[‖ξv(x∗)‖2] <∞. (6) As we discuss below, common assumptions used to prove convergence of stochastic algorithms for solving the VI problem is uniform boundedness of the stochastic operator E‖ξi(x)‖2 ≤ c or uniform boundedness of the variance E‖ξi(x)− ξ(x)‖2 ≤ c. However these assumptions either do not hold or are true only for restrictive set of problems. In our work we do not assume such bounds. Instead we use the following direct consequence of Assumption 3.3.
Lemma 3.4. If ξ ∈ EC(`ξ), then E‖ξv(x)‖2 ≤ 2`ξ〈ξ(x), x− x∗〉+ 2σ2. Let us now provide some more familiar sufficient conditions which guarantee that the EC condition holds and give closed form expression for the expected co-coercivity parameter.
Proposition 3.5. Let ξi be `i co-coercive (or `i co-coercive around x∗), then ξ ∈ EC(`ξ). Let `max = max{`i}ni=1 and ` be the co-coercive constant of ξ, if we let v to be a b-minibatch sampling, then `ξ = nb b−1 n−1`+ 1 b n−b n−1`max and σ 2 = 1b n−b n−1σ 2 1 , where σ 2 1 := 1 n ∑n i=1 ‖ξi(x∗)‖ 2.
In the above Proposition 3.5, we show how co-coercivity of ξi implies expected co-coercivity. However, the opposite implication does not necessarily hold. Indeed the expected co-coercivity can hold even when we do not assume that ξi are co-coercive, as we show in the next proposition.
Proposition 3.6. Let ξ be quasi-strongly monotone and let ξi be Li-Lipschitz continuous for all i ∈ [n]. Then ξ ∈ EC(`ξ).
Connection to Other Assumptions In the optimization literature, the standard convergence analysis of stochastic gradient algorithms like SGD relied on bounded gradient (E‖∇fi(x)‖2 ≤ c) or bounded variance assumptions (E‖∇fi(x)−∇f(x)‖2 ≤ c) [Recht et al., 2011, Hazan and Kale, 2014, Rakhlin et al., 2012] or growth condition (E‖∇fi(x)‖2 ≤ c1‖∇f(x)‖2 + c2) [Bottou et al., 2018, Schmidt et al., 2017]. However, a recent line of work shows that these assumptions might be restrictive or never be satisfied5 and proposed alternative conditions [Nguyen et al., 2018, Vaswani et al., 2018, Gower et al., 2019, 2021, Khaled et al., 2020, Khaled and Richtárik, 2020, Assran et al., 2019, Koloskova et al., 2020, Patel and Zhang, 2021, Loizou et al., 2020, 2021]. One of the weakest assumptions used for the convergence analysis of SGD in the smooth setting, is expected smoothness (ES) proposed in Gower et al. [2019] (see last row of Table 1). Our expected co-coercivity condition (EC) can be seen as the generalization of ES in the operator setting.
In the literature of stochastic methods for solving the variational inequality problem and min-max optimization problem, similar assumptions have been made. In particular for the analysis of stochastic algorithms, papers assume either bounded operators [Nemirovski et al., 2009, Abernethy et al., 2021] or bounded variance [Juditsky et al., 2011, Yang et al., 2020, Lin et al., 2020a, Luo et al., 2020, Tran Dinh et al., 2020] and growth condition [Lin et al., 2020b]. In all of the these conditions, the values of parameters c, c1 and c2 (see Table 1) usually do not have a closed form expression – they are simply assumed to exist. However, to the best of our knowledge, there is no analysis using a concept similar to our expected co-coercivity. All existing analyses of SGDA for (quasi)-strongly monotone and co-coercive operators require the much stronger extra assumptions of “bounded noise” or “bounded variance” to guarantee convergence, while for SCO, there are no known convergence guarantees in the literature. Note that through Lemma 3.4, (EC) implies bounds on the gradient with closed-form problem-depended expressions for these constants. We also mention that other appropriate relaxed assumptions have been considered to prove the convergence of algorithms for (1) [Hsieh et al., 2020, Mishchenko et al., 2020, Chavdarova et al., 2019, Loizou et al., 2020], but not yet for SGDA nor SCO. For a wider literature review in the area, see Appendix E.
In Table 1, we illustrate the correspondence between conditions used in the stochastic optimization literature and the stochastic VI problem. For further connections between these conditions, see Appendix A.5. There, for example, we show why assuming bounded gradients together with strong monotonicity lead to an empty set of operators and explain why ES and EC (see last row of Table 1) are equivalent for convex and smooth single-objective optimization problems.
5For example, the bounded gradient assumption and strong convexity contradict each other in the unconstrained setting (see [Nguyen et al., 2018] for more details).

heading: 4 Stochastic Gradient Descent-Ascent
text: Having presented the update rule of SGDA (5) for solving the stochastic reformulation (4) of the original unconstrained stochastic variational inequality problem (1), let us now provide theorems for its convergence guarantees. We highlight that our theorems hold for any selection of distributions D over the random sampling vectors v and as such they are able to describe the convergence of an infinite array of variants of SGDA each of which is associated with a specific probability law governing the data selection rule used to form minibatches.
Theorem 4.1 (Constant Step-size). Assume that ξ is µ−quasi strongly monotone and that ξ ∈ EC(`ξ). Choose αk = α ≤ 12`ξ for all k. Then, the iterates of SGDA, given by (5), satisfy:
E [ ‖xk − x∗‖2 ] ≤ (1− αµ)k ‖x0 − x∗‖2 + 2ασ 2
µ , (7)
Note that we do not assume that ξ or ξi are monotone operators in Theorem 4.1. SGDA converges by only assuming that ξ is quasi-strongly monotone and that EC holds. Theorem 4.1 states that SGDA converges linearly to a neighborhood of x∗ which is proportional to the step-size α and the noise at the optimum σ2. We highlight, that since we control distribution D we also control the values of `ξ and σ2, and in the case of b-minibatch sampling these values have a closed-form expressions as shown in Proposition 3.5. To the best of our knowledge, Theorem 4.1 is the first last-iterate non-asymptotic convergence guarantee for SGDA for solving quasi-strongly monotone problems without assuming extra conditions on the noise. It is worth mentioning that Lin et al. [2020b] also prove last-iterate convergence of SGDA for different class of problems (they do not assume quasi-strong monotonicity), but the proposed analysis requires much stronger noise conditions. In particular, a bound on the variance with vanishing constants is needed, which, as far as we know, can only be satisfied by running SGDA with growing mini-batch size [Friedlander and Schmidt, 2012] (see also App. E for a more detailed discussion). To highlight further the generality of Theorem 4.1, we note that for the deterministic GDA, σ2 = 0. Thus, we can obtain the following corollary.
Corollary 4.2 (Deterministic GDA). Let all assumptions of Theorem 4.1 be satisfied. Let |S| = n with probability one (each iteration of SGDA uses a full batch gradient). Then by selecting αk = α ≤ 12` for all k, the iterates of deterministic GDA satisfy: ‖xk − x∗‖2 ≤ (1− αµ) k ‖x0 − x∗‖2.
Even if Corollary 4.2 looks trivial, to the best of our knowledge, Theorem 4.1 is the first convergence theorem of SGDA that includes the deterministic GDA originally provided by Chen and Rockafellar [1997] as a special case.
Optimal b-Minibatch Size: Using standard computations, the convergence rate presented in Theorem 4.1 can be equivalently expressed as iteration complexity result as follows: If we are given any accuracy > 0, choosing stepsize α = min { 1
2`ξ , µ4σ2
} and k ≥ max { 2`ξ µ , 4σ2 µ2 } log ( 2‖x0−x∗‖2 ) ,
implies E‖xk − x∗‖2 ≤ . By combining the lower bound on k with the expressions of `ξ and σ2 of Proposition 3.5, we have that the iteration complexity (by ignoring the logarithmic terms) becomes k ≥ 2µ max{`ξ, 2σ 2
µ } where `ξ = nb b−1n−1`+ 1b n−bn−1`max and σ2 = 1b n−bn−1σ21 . Thus, the total complexity of the algorithm as a function of the minibatch size b is given by TC(b) ≤ 2µ max{b`ξ, b 2σ 2
µ }. By following the same steps with Gower et al. [2019], it can be shown that b`ξ is linearly increasing term in b while b 2σ 2
µ is a linearly decreasing term in b. Hence, if we define b ∗ to be the minibatch
size that minimize the total complexity TC(b) (optimal b-Minibatch Size) we have that if σ21 ≤ `max then b∗ = 1 otherwise b∗ = n
`−`max+ 2 µ ·σ21 n`−`max+ 2 µ ·σ21 .
In the next theorem, we provide an insightful stepsize-switching rule that describes when one should switch from a constant to a decreasing step-size regime to guarantee convergence to x∗ and not to a neighborhood, providing the first convergence analysis of SGDA under such a switching rule.
Theorem 4.3. Assume ξ is µ-quasi-strongly monotone and that ξ ∈ EC(`ξ). Let K := `ξ/µ and let αk = 12`ξ for k ≤ 4dKe and αk = 2k+1 (k+1)2µ for K > 4dKe. If k ≥ 4dKe, then iterates of SGDA, given by (5) satisfy:
E‖xk − x∗‖2 ≤ σ 2 µ2 8 k + 16dKe2 e2k2
‖x0 − x∗‖2 = O ( 1
k
) . (8)

heading: 5 Stochastic Consensus Optimization
text: The Consensus Optimization (CO) Algorithm is a computationally-light6 second order methods which has been introduced in Mescheder et al. [2017] and it was shown to be an effective method for training GANs in a variety of settings. Liang and Stokes [2019] show first that CO converges linearly in the bilinear case. Abernethy et al. [2021] show that CO can be viewed as a perturbation of the deterministic Hamiltonian gradient descent (HGD) and explain how CO converges at the same rate as HGD, while Azizian et al. [2020] prove convergence of CO for µ-strongly monotone operators with positive singular values of the Jacobian matrix J = ∇ξ. However, even if CO is used explicitly in the stochastic setting and in practice only minibatch variants are implemented, to the best of our knowledge all existing analysis focus only on the deterministic setting. Thus, our work is the first that provide convergence guarantees for the Stochastic Consensus Optimization (SCO) and due to our framework, our analysis includes the convergence of the deterministic update as special case. Impressively, our analysis provides tighter rates than previous analysis even in the deterministic setting.
For the results of this section, we assume that each ξi in problem (1) is differentiable. That is, we have access to the Jacobian matrices Ji(x) = ∇ξi(x). Following Loizou et al. [2020], in our analysis we will also assume that the Hamiltonian function is quasi-strongly convex and that it satisfies expected smoothness (see last row of Table 1). These are not strong assumptions, and as an example, they are satisfied for smooth bilinear min-max optimization problems Loizou et al. [2020]. In Appendix C, by extending the results of Loizou et al. [2020], we explain how these assumptions can be satisfied for the quadratic min-max problems.

heading: 5.1 Setting
text: The consensus optimization (CO) algorithm as presented in Mescheder et al. [2017] has the following update rule: xk+1 = xk − αξ(xk)− γ∇H(xk) (9) whereH(x) = 12‖ξ(x)‖2 is the Hamiltonian function and α, γ > 0 are the step-sizes. From its definition, it is clear that the update rule is essentially a weighted combination of GDA and the Hamiltonian gradient descent (HGD) of Balduzzi et al. [2018]. In practice, implementing CO in a mini-batch setting (stochastic) leads to biased estimates of the gradient of the Hamiltonian function [Mescheder et al., 2017]. This is one of the main reason that existing analysis was not able to capture the behavior of the method in the stochastic setting. However, recently Loizou et al. [2020] proposed a way to obtain unbiased estimators of the gradient of the Hamiltonian function by expressing the Hamiltonian of a stochastic game as a finite-sum problem. In this work, we adopt the finite-sum structure and the unbiased estimators proposed in Loizou et al. [2020] for the Hamiltonian part and we extend the formulation to capture the arbitrary sampling paradigm. That is, the Hamiltonian function can be expressed as,H(x) = 12‖ξ(x)‖2 = 1n ∑n i=1 1 n ∑n j=1 1 2 〈ξi(x), ξj(x)〉. In addition, by following the stochastic reformulation setting presented in Section 2, let us have two independent random sampling vectors u ∼ D and v ∼ D and let us define: Hu,v(x) = 1n ∑n i=1 1 n ∑n j=1 1 2 〈uiξi(x), viξj(x)〉. Since vectors u and v are independent sampling vectors, it is clear that Eu,v[Hu,v(x)] = H(x), where Eu,v denotes the expectation with respect to distribution D on both vectors u and v. Let us also
6At each step, CO requires only the computation of a Jacobian-vector product which can be efficiently evaluated in tasks like training neural networks with comparable computation time of a gradient [Pearlmutter, 1994].
use Ji(x) = ∇ξi(x) to express the Jacobian matrices for i, then the gradient of Hu,v(x) has the following form:
∇Hu,v(x) = 1
2
[ J>u (x)ξv(x) + J > v (x)ξu(x) ] (10)
where Ju(x) = 1n ∑n i=1 uiJi(x) and Jv(x) = 1 n ∑n i=1 viJi(x). Similar to Loizou et al. [2020], it can be shown that ∇Hu,v(x) is an unbiased estimator of ∇H(x) = J>(x)ξ(x). That is, Eu,v[∇Hu,v(x)] = ∇H(x). Throughout this section, we will denote the gradient noise of the stochastic Hamiltonian function with σ2H := Eu,v[‖∇Hu,v(x∗)‖ 2 ], which is finite for any reasonable sampling distribution D.

heading: 5.2 Stochastic Consensus Optimization and its Special Cases
text: Algorithm 1 Stochastic Consensus Opt. (SCO) Input: Starting step-size α0, γ0 > 0. Choose initial point x0 ∈ Rd. Distribution D of samples. for k = 0, 1, 2, · · · ,K do
Sample independently vk ∼ D and uk ∼ D Set step-sizes αk and γk according to a preselected step-size rule Set xk+1 = xk − αkξvk(xk)− γk∇Hvk,uk(xk)
end for Output: The last iterate xk Having explained the basic setting and background on consensus optimization algorithm and the Hamiltonian function, let us now present as Algorithm 1 the proposed stochastic consensus optimization (SCO) algorithm. Note that in each iteration k, two random sampling vectors u and v are sampled independently from a user-defined distribution D. These vectors are used to evaluate ξvk and∇Hvk,uk(xk), the unbiased estimators of ξ(xk) and ∇H(xk) at point xk respectively. Note also that the update rule of SCO is a weighted combination of SGDA (5) and the stochastic Hamiltonian gradient descent (SHGD) of Loizou et al. [2020]. Thus, it is clear, that if one selects αk = 0,∀k > 0 then the method is equivalent to SHGD and if γk = 0,∀k > 0 then the method becomes equivalent to the SGDA. In addition if we select sampling vectors u = v = (1, 1, . . . , 1) ∈ Rn with probability 1, then from the definition of ξvk and∇Hvk,uk(xk) we obtain the deterministic CO (9) as special case of our update rule.

heading: 5.3 Convergence Analysis
text: Let us now present our main theoretical results describing the performance of SCO. Similar to the previous section, we provide two main theorems for two different step-size selection.
Theorem 5.1 (Constant Step-size). Assume ξ is µ-quasi-strongly monotone with µ ≥ 0 and that ξ ∈ EC(`ξ). Assume that the Hamiltonian function H is µH-quasi strongly convex and LH-expected smooth. Then, for γk = γ ≤ 14LH and αk = α ≤ 1 4`ξ , the iterates of SCO satisfy:
E [ ‖xk − x∗‖2 ] ≤ (1− γµH − αµ)k‖x0 − x∗‖2 +
4[α2σ2 + γ2σ2H] γµH + αµ . (11)
If µ = 0, that is ξ only satisfies the variational stability condition 〈ξ(x), x− x∗〉 ≥ 0, then
E [ ‖xk − x∗‖2 ] ≤ (1− γµH)k‖x0 − x∗‖2 +
4[α2σ2 + γ2σ2H] γµH .
Theorem 5.1 is quite informative, as it highlights that both SGDA and SHG parts should coexist in the update rule of the SCO to guarantee faster convergence for µ-quasi-strongly monotone operators (i.e. both step-sizes α and γ should be positive up to specific values). However, if ξ simply satisfies the variational stability condition 〈ξ(x), x − x∗〉 ≥ 0 (when µ = 0), then the convergence rate of SCO, does not depend on the step-size α (the SGDA part) and the neighborhood of convergence 4[α2σ2+γ2σ2H]
γµ is smaller when α = 0. Thus, in this case one needs to simply run the SHGD.
To appreciate the generality of Theorem 5.1, let us present some corollaries and compare the rates with existing results in the literature. First, we get a rate for the deterministic CO algorithm.
Corollary 5.2 (Deterministic CO). Let all assumptions of Theorem 5.1 be satisfied. Then, for γk = γ ≤ 14LH and αk = α ≤ 1 4` , the iterates of CO satisfy: ‖xk−x∗‖2 ≤ (1−γµH−αµ)k‖x0−x∗‖2.
The result of Corollary 5.2 should be compared to the convergence guarantees for CO as provided in Abernethy et al. [2021], where the authors viewed CO as a perturbation of the deterministic Hamiltonian gradient descent (HGD). In particular, Abernethy et al. [2021] gives the rate 1− µH4LH for CO under similar assumptions,7 which is clearly slower than our 1− µH4LH − µ 4` rate. The authors had explicitly noted that treating the GDA part as an adversarial perturbation most likely should be improved upon. With our analysis, we provide a different, more natural analysis of CO and answer this open problem. In addition, note that by setting γk = 0 and αk = α < 1/2`ξ , then SCO becomes equivalent to SGDA and Theorem 5.1 matches the convergence guarantees presented in Theorem 4.1. On the other hand, by setting αk = 0, SCO yields equivalent updates to SHGD and our result matches the theoretical guarantees of Loizou et al. [2020] as we show in the next corollary.
Corollary 5.3. Under the assumptions of Thm. 5.1, set αk = 0 and γk = γ ≤ 1/2LH. Then SCO is equivalent to SHGD and its iterates satisfy: E [ ‖xk − x∗‖2 ] ≤ (1− γµH)k‖x0 − x∗‖2 + 2γσ 2 H
µH .
All previous results for SCO show convergence to a neighborhood of x∗. In the next theorem, by selecting decreasing step-sizes (switching strategy) for the values of α and γ, we are able to guarantee a sublinear convergence to the exact solution for SCO. To the best of our knowledge this is the first result analyzing SCO with decreasing step-sizes.
Theorem 5.4. Assume ξ is µ-quasi-strongly monotone and that ξ ∈ EC(`ξ). Assume that the Hamiltonian function H is µH-quasi strongly convex and LH-expected smooth. Let αk = γk, ψ = max{`ξ,LH} and k∗ := 8 ψµH+µ . Let also, γk = 1 4ψ for k ≤ dk∗e and γk = 2k+1(k+1)2[µH+µ] for k > dk∗e. If k ≥ dk∗e, then SCO iterates satisfy:
E‖xk − x∗‖2 ≤ σ 2 H + σ 2 [µ+ µH]2 16 k +
(k∗)2 e2k2 ‖x0 − x∗‖2 = O
( 1
k
) (12)
If µ = 0, that is ξ only satisfies the variational stability condition 〈ξ(x), x− x∗〉 ≥ 0, then SCO is still able to converge sublinearly with O ( 1 k ) , to x∗.

heading: 6 Numerical Evaluation
text: The purpose of this experimental section is to corroborate our theoretical results, which form the main contributions of this paper. To do so, we focus on strongly-monotone quadratic games of the following form:
min x1∈Rd max x2∈Rp
1
n ∑ i 1 2 x>1 Aix1 + x > 1 Bix2 − 1 2 x>2 Cix2 + a > i x1 − c>i x2 (13)
We show that the Hamiltonian function of such a game is µH-quasi-strongly convex and LH-smooth in App. C.1. For the game to also be strongly-monotone and co-coercive, we sample the matrices such that µAI Ai LAI, µCI Ci LCI, and µ2BI B>i Bi L2BI, where I is the identity matrix; the exact sampling is described in App. C.2. The bias terms ai, ci are sampled from a normal distribution. We pick the step-size for the different methods according to our theoretical findings. That is, for constant step-size, we select α = 12`ξ for SGDA (Theorem 4.1), α = 1 4`ξ , γ = 14LH for SCO (Theorem 5.1), and γ = 12LH for SHGD (Corollary 5.3). For the stepsize-switching rule that guarantees convergence to x∗, we use the step-sizes proposed in Theorem 4.3 for SGDA and Theorem 5.4 for SCO. Let us first look at the qualitative behavior of SGDA, SCO and SHGD on a simple 2d example where x1, x2 ∈ R. We show the trajectories of the different algorithms in Fig. 1a. As expected we observe that the behavior of SCO is in between SGDA and SHGD. Recall that the update rule of SCO is a weighted combination of SGDA and the SHGD. The code to reproduce our results can be found at https://github.com/hugobb/StochasticGamesOpt.
Comparison of Algorithms (Constant step-size). We look at the convergence of the methods for different games where we vary the condition number κG = `ξ µ . In comparing the methods, we
7For this convergence rate, Abernethy et al. [2021] assumed that the Hamiltonian function satisfies the PolyakLojasiewicz condition but focus on strongly-convex and strongly-concave min-max optimization problems.
‖x0−x∗‖2 as a function of the number of iterations. Each plot corresponds to a
game with a particular condition number κG = `ξ µ
. The solid lines represent the average performance over the 5 runs and the colored area represent the 95% confidence intervals.
use the relative distance to optimality ‖x k−x∗‖2
‖x0−x∗‖2 . As predicted from our theoretical results, when constant step-size is used, all the methods converge linearly to a neighborhood of the solution (see Figure 1). We observe that the performance of SGDA depends on the condition number: the higher the condition number, the slower the convergence. In contrast, the convergence of both SHGD and SCO is less affected by a larger condition number. We also observe that SGDA is slower than SHGD, but converges to a smaller neighborhood of the solution (see e.g. Fig. 1b). SCO achieves a good trade-off; it converges fast like SHGD and to a small neighborhood like SGDA. An important note is that the size of the neighborhood heavily depends on the selection of the learning rate; we explore this dependence in App. C.3.
Constant vs Decreasing step-size. We also compare the performance of SGDA and SCO in the constant and decreasing step-size regimes considered in Theorems 4.1 and 4.3 for SGDA and Theorems 5.1 and 5.4 for SCO. We present our results in Figure 2. As predicted from our theoretical analysis for both methods, the decreasing step-size (switching step-size rule) reaches higher precision compare to the constant step-size. In Figure 2a the vertical red line denotes the value 4d`ξ/µe predicted in Theorem 4.3 while in Figure 2b the red line denotes the value ⌈ 8
max{`ξ,LH} µH+µ
⌉ predicted
in Theorem 5.4. Note that for both algorithms the red line is a good approximation of the point where SGDA and SCO need to change their update rules from constant to decreasing step-size.

heading: 7 Conclusion and Future Directions of Research
text: We provided the first last-iterate convergence analysis of SGDA and SCO without requiring any strong bounded noise assumption, by introducing the much weaker expected co-coercivity assumption. We proved last-iterate convergence for both methods for a class of unconstrained variational inequality problems that are potentially non-monotone (quasi-strongly monotone problems), with both constant and decreasing step-sizes. Future work includes extending our results beyond the µ-quasi strongly monotone assumption for SGDA (assuming only co-coercivity), where we expect to obtain a slower sublinear rate. We also believe the proposal of expected co-coercivity to be of independent interest; it could be used to provide an efficient analysis of other algorithms to solve (1) under the arbitrary sampling paradigm, and it would also be interesting to generalize the analysis to the constrained formulation of variational inequalities.
Acknowledgments and Disclosure of Funding
Funding. Nicolas Loizou acknowledges support by the IVADO Postdoctoral Funding Program. This research was partially supported by the Canada CIFAR AI Chair Program and by a Google Focused Research award. Simon Lacoste-Julien is a CIFAR Associate Fellow in the Learning in Machines & Brains program.
Competing interests. Simon Lacoste-Julien additionally works part time as the head of the SAIT AI Lab, Montreal from Samsung. Hugo Berard was working part time as a research intern at Facebook, Montreal.

Review summaries:
This paper presents a new analysis for solving smooth, unconstrained variational inequalities, particularly focused on applications to minimax optimization. The primary theory innovation in this work is the observation that the very standard cocoercivity assumption can be replaced by cocoercivity holding in expectation. For such problems, convergence guarantees for the Stochastic Gradient Descent-Ascent and Stochastic Consensus Optimization are given. In both cases, O(1/T) convergence rates are proven. Numerics are given showing the proposed stepsize schemes perform reasonably.

This paper introduces the expected co-coercivity condition, explain its benefits, and provide the first-iterate convergence guarantees of stochastic gradient descent ascent (SGDA) and stochastic consensus optimization (SCO) under this condition for solving a class of stochastic variational inequality problems that are potentially non-monotone. The authors prove linear convergence of both methods to a neighborhood of the solution when the algorithms use constant step-size, and propose insightful stepsize-switching rules to guarantee convergence to the exact solution. One of the appealing features is that the convergence guarantees hold under the arbitrary sampling paradigm, and as such, the authors give insights into the complexity of mini-batching. 

This paper proposes convergence analysis on the optimization algorithms of smooth games, where the problem is formulated as a stochastic variational inequality, under the novel assumptions called expected co-coercivity and quasi-strong monotonicity. These assumptions serve the role of smoothness and strong convexity in the classical analyses of SGD for convex minimization. The authors show the last-iterate convergence rates for stochastic gradient descent-ascent (SGDA) and stochastic consensus optimization (SCO). The authors also relax the assumptions on the coordinate sampling schemes and on the noise. 

This paper makes multiple contributions to the convergence analysis of unconstrained stochastic variational inequality problem:   (1) This paper proposes the expected co-coercivity assumption for operators that is equivalent to expected smoothness for functions, and weaker than many prevalent assumptions for variational inequality problem such as bounded gradient, bounded variance and growth condition.  (2) This paper generalizes the unbiased stochastic gradient with mini-batch into unbiased stochastic gradient with continuous spectrum, and applies it to generalize the two prevalent algorithms for unconstrained stochastic variational inequality problem, namely, stochastic gradient descent ascent analysis (SGDA) and Consensus Optimization (CO). The latter is further generalized into Stochastic Consensus Optimization (SCO) by applying to variational inequality problem of finite-sum structure, which contains Combines and generalizes several related algorithms including SGDA, deterministic CO and stochastic Hamiltonian gradient descent (SHGD) as special cases.   (3) This paper gives the first last-iterate convergence analysis of this generalized SGDA that only relies on the expected co-coercivity assumption and the quasi-strongly monotone assumption that are weaker than the previous analysis of SGDA, and recovers the results of deterministic GDA. Effects of hyper-parameters are well studied including constant step-size, diminishing step-size and the optimal batch-size.  (4) This paper gives the first last-iterate convergence analysis of SCO that recovers the results of SGDA, deterministic CO and stochastic Hamiltonian gradient descent (SHGD), and the convergence is even faster than an existing analysis of deterministic CO.