Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity
Authors: Nicolas Loizou
Hugo Berard
Gauthier Gidel
Ioannis Mitliagkas
Simon Lacoste-Julien
Venue: NeurIPS 2021 Poster (2021)
Keywords: Smooth Games
Min-max optimization
Unconstrained Stochastic Variational Inequality
Stochastic algorithms
Convergence analysis
Stochastic Gradient Descent-Ascent (SGDA)
Stochastic Consensus Optimization

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. 


Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity
Nicolas Loizou' Mila and DIRO, Université de Montréal
Hugo Berard Mila and DIRO, Université de Montréal
Gauthier Gidel Mila and DIRO, Université de Montréal
Toannis Mitliagkas Mila and DIRO, Université de Montréal
Simon Aacoste-Julient Mila and DIRO, Université de Montréal
Abstract
Two of the most prominent algorithms for solving unconstrained smooth games are the classical stochastic gradient descent-ascent (SGDA) and the recently intro- duced stochastic consensus optimization (SCO) [Mescheder et al., 2017]. SGDA is known to converge to stationary point for specific classes of games, but current convergence analyses require bounded variance assumption. SCO used success- fully for solving large-scale adversarial problems, but its convergence guarantees are limited its deterministic variant. In this work, we introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate con- vergence guarantees of SGDA and SCO under this condition for solving a class stochastic variational inequality problems that potentially non-monotone. We prove linear convergence of both methods to neighborhood of the solution when they constant step-size, and propose insightful stepsize-switching rules guarantee convergence to the exact solution. In addition, our convergence guaran- tees hold under the arbitrary sampling paradigm, and as such, give insights into the complexity of minibatching.
Introduction
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 more abstract formulation of the problem and focus on solving the following unconstrained stochastic variational inequality (VI) problem:?
Find x PER Rd
such that 5(=")= Σ ((xx)= =
where each : Rd + Rd Lipschitz continuous. Further, we assume that the problem (1) has unique solution x² and that the operator & is p-quasi-strongly monotone: there is a 2 0 such that:
(E(x), - x²) 2 A|| =|"|2
Vo E Rd
(2)
"Corresponding author: nicolasloizoul @ ggmail.comm 'Canada CIFAR AT Chair.
"While presentation focuses on this finite-sum structure, most of our convergence results easily be adapted the general stochastic setting (see App. D). Also, do not the full power of variational inequalities that usually have constraints [Harker and Pang. 1990]. standard algorithms for (1) are coming from this literature [Gidel et al., 2018).
TTii assumption be relaxed: but for simplicity of exposition enforce it.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

If O, then we say that & satisfies the variational stability condition: (E(x), x²) 2 0 [Hsieh al., 2020]. In the variational inequality literature. condition (2) also known as strong stability con- dition (Mertikopoulos and Zhou, 2019] or as strong Minty variational inequality (MVT) (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 al., 2010, Mertikopoulos and Zhou, 2019]. The simplest example is the unconstrained min-max optimization problem (also called a zero-sum game);
min max Jy ER EI TE
g (x1,
(3)
where each component function gi : 12 x R2 + R is assumed to be smooth. Here, & represents the appropriate concatenation of the block-gradients of g:: (x(x) ;= (Va,9i (2), 22);-Vass (xr, x2)),
where x := 22). Solving (1) then amounts to finding a stationary point x = xf for (3), which under convex-concavity assumption for 9i for example, implies that it is global solution for the min-max problem. More generally, we might seek the pure Nash equilibrium of a k-players game, where each player is simultancously trying to find the action 23 which minimizes with respect to
I, E Rd their own cost function > -'= f. (z), while the other players are playing z-j- which represents r = (Z1...... 2xk) with the component j removed. Here, (z)) is the concatenation over all possible j's of Ji x-y).
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. 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 ||5 (z) l?a While the practical version of their algorithm for large n is stochastic (SCO, that randomly samples i' i's) and displayed good performance [Mescheder et al., 2017], the only global convergence rate guarantees existing in the literature 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]E:(z) - {[=] is typically assumed to get convergence guarantees (see e.g. Nemirovski et al. [2009], Gidel et al. 12018), 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 9: is quadratic function, then the variance typically goes to infinity as x - 00. More appropriate relaxed assumptions have been considered to prove the convergence of other algorithms for (1) such 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 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 apply the methods on potentially non-monotone problems such as GANs, where averaging is not appropriate. The only asymtooti last iterate convergence result for SGDA that we are aware 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 [=]]]] (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.
'We use this suggestive name motivated from the min max formulation (3), though we also call SGDA the simple update z xx abi, (x*) 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 neighborhood of x when constant step-size is used, and ((1/k) rate the exact solution when using a decreasing step-size rule. For the latter, we propose a theoretically motivated switching rule from constant to 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 corollary of our results, we obtain 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 special case of the SCO and show that in this scenario, our analysis matches the theoretical guarantées 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áč, 2016]. This allows us to give insights into the complexity of minibatching.
Arbitrary Sampling: Stochastic Reformulation of Problem (1)
In this work, we provide theorems through which we can analyze all minibatch variants of the two al- gorithms under study, SGDA and SCO. To do this, we construct a so-called "stochastic reformulation" of the variational inequality problem (I), 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 (xx e IRd of the operator such that E [x[=)]= = {(x). For example, we can use a minibatch to form an estimate Eies (())), where S C {l....,, n) will be chosen uniformly random and |S| b. To allow for any form of minibatching, we use the arbitrary sampling notation g(z) = (x) == 1 1
of the operator such as g(z)
(T), where v E 1& is a random sampling vector drawn from ig...,n. n. Note that the unbiasedness follows immediately from this definition of the sampling vector: (x) _/4 Σ Ep Ep((v)<(())) {(x)-
some distribution D such that ED ED[u:] 1, for
Thus, with each user- defined distribution D. we able to introduce stochastic reformulation of problem (1) as follows:
Find xx
R such that ED So
(4)
Since & (z) as an unbiased estimate of the operator {(z), we can now use stochastic (simultancous) gradient descent-ascent (SGDA) to solve (4) as follows:
x. +++ x (xfaa(("))
(5)
where w D sampled i.i.d at each iteration and ag > is a stepsize. We highlight that in our analysis, we allow select any distribution D that satisfies ED[e,] 1 Vi, 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 E [n]. We say that E R" is I-minibatch sampling
if for every subset S E [n] with [S] = b, we have that TP [ = : Eiese: 1/ (C)
b((
n!!
By using double counting argument, one can show that if v is l-minibatch sampling, it is also valid sampling vector (Eop [v:] = 1) [Gower al., 2019]. See Gower et al. [2019] for other choices of sampling vectors
3

---

Expected Co-coercivity and Connection to Other Assumptions
Before introducing the condition of expected co-coereivity, we first review some details on co- coercivity, an intermediate notion between monotonicity and strong monotonicity [Zhu and Marcotte, 1996], and explain where belongs as assumption in the literature variational inequalities and min-max optimization.
Co-coercive operators. The co-coercive condition is relatively standard in operator splitting literature [Davis and Yin, 2017, Vú, 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 known not to converge for general monotone operators [Bauschke et al., 2011]. 1].
Definition 3.1 (Co-coercivityy / Co-coereive around w² We say that an operator & is f-co-coercive if there exist >> O such that," (IE()r) {(y) < ((E(x) - E(v), I - v) Vx, y E RR. If there exist w" E IRd and e > 0 such that then we say that the operator is (-co-coercive around wt. Note that in the last definition the point w" is not necessarily a point where E(w") 0.
< ((E(z) - "(
Vo E Rd
Note that from Cauchy-Swartz/ inequality, one can get that ê-co-coercive operator is é-Lipschitz. In single-objective minization, one can show the converse statement by using convex duality. Thus, 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., 201 IJ. However, in general, L-Lipchitz operator is not L-co-coercive. What we can show instead is that L-Lipschitz and j-strrongly monotone operator is f-co-coercive with & E L, L /p] [Facchinei and Pang, 2007]. Note that both ranges of the spectrum may occur. For instance, Chavdarova al. [2019] present sufficent condition in zero-sum games to have / OL)). Note that one can casily show that a sum of co-coercive operators is also co-coercive. Let us now provide proposition summarizing the implications between (strong) monotonicity and co-coercivity.
Proposition 3.2. For L-Lipschitz operator &, the following implications hold:
j--strongly monotone
La -co-coercive
monotone Y variational stability condition
$
$
u-quasi-strongly monotone
L -co-coerrive around x=*
Let us also note that while Ê-co-coercive operator is always é-Lipschitz continuous, it is possible for an operator to Ê-co-coercive around x² and not 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, provide such example of µ--uasi strongly monotone operator that is (-co-coercive around x", which is not monotone nor Lipschitz continuous.
3.1 Expected Co-coercivity (EC)
In our analysis of SGDA and SCO, we rely on generic and remarkably weak assumption that call expected co-coercivity (EC). In this section, we formally define EC, provide sufficient conditions for it to hold and relate it the existing gradient assumptions.
Assumption 3.3 (Expected Cocoercivity). We say that & is lg co-corivee in expectation with respect to a distribution D if there exists 4 > 0 such that
Ep [I5((x) - {x(2)) < (e(E(x), x xx) Ya Rdd
(EC)
For simplicity, we will write & E EC((e) to say that EC holds and we will refer to &g as the expected co-coercivity constant.
"Note that in our definition consider the inverse of the co-coercive constant from Lions and Mercier [1979] which is the constant é such that (E(x) E(v), 2 {ll{(z) <())]

---

The convergence results in this paper will depend on the following operator noise at x² that is finite for any reasonable sampling distribution for the sampling vector
(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 (x)]1= S or uniform boundedness of the variance El[{,()) {(x) S 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.
:- (x )) co.
Lemma 3.4. If f E EC((e), then (=)) < 26c(E(x),
x²) +20
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 & be & co-coercive (or l, co-coercive around æ"), then ş E EC((E). Let max max {4: J= and f be the co-coercive constant of &, if we let v to be a b-minibatch sampling, 6-1 l n- max and 0² x of. where of
then lg = n
Σ [+=((
In the above Proposition 3.5, we show how co-coercivity of & implies expected co-coereivity. However, the opposite implication does not necessarily hold. Indeed the expected co-coercivity can hold even when we do not assume that & are co-coercive, as we show in the next proposition.
Proposition 3.6. Let & be quasi-strongly monotone and let & be L, L,-Lipschitz continuous for all E [n). Then & E EC((t))
Connection to Other Assumptions In the optimization literature, the standard convergence analysis of stochastic gradient algorithms like SGD relied on bounded gradient [=)]] < c) bounded variance assumptions (E) f(())) - V f()) < c) [Recht et al., 2011, Hazan and Kale, 2014, Rakhlin et al., 2012] or growth condition (E fi || I f=)l((())l" + c2) [Bottou al., 2018, Schmidt et al., 2017]. However, a recent line of work shows that these assumptions might be restrictive or never be satisfied and proposed alternative conditions [Nguyen 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 al., 2020, Patel and Zhang, 2021, Loizou et al., 2020, 2021]. One of the weakest assumptions used for the convergence amalysis 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, Abemethy 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 al., 2020b]. In all of the these conditions, the values of parameters c, Cj and 02 (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-coereive 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 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.
For example, the bounded gradient assumption and strong convexity contradict each other in the uncon- strained setting (see [Nguyen et al., 2018] for more details).
5

---

Table I: Conrespondence of Assumptions between Optimization and Variational Inequalities
Stuchustic Optimization
Stochastic Variational Inequality
Assumptions
min,
f(z)
>. J((r)
Find
a² such that <(a") - + > G(0e
Bounded Gradient
EI faoll sc
[ <e
Bounded Variance
V/] se
1112 - [[2]] se
Growth Condition
[ta)) +ox
Expected Smoothmess (ES)
E (1V
V(((+")) 20(5(s) f(=)))
e [(s(()) (.('") 1418(1) x*)
Expected Cocoercivity (BC)
4 Stochastic Gradient Descent-Ascent
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 p-quasi strongly monotone and that & E for all Then, the iterates of SGDA, given by (5), satisfy:
EC(()). Choose ag a S 2Fg
E [|I** - 11] S - (1-o 1,00 - x²122+ 2002
(7)
Note that we do not assume that 5 or &, 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 a and the noise at the optimum 2². We highlight, that since we control distribution D we also control the values of f and 0², and in the case of b-minibatch sampling these values have flosed-form expressions as shown 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 assumee 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 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, o² = O. 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 0y: = < for all k, the iterates of deterministic GDA satisfy: ||a=* x² 1|2 < (1 ax) ||00 x" 1|?
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 Theo- rem 4.1 can be equivalently expressed as iteration complexity result as follows: If we are given any ac-
curacy >> 0, choosing stepsize = min {
1 ey and l 2 max { 40
24g 1o2
" que log
[2| 2||==~>""
25
By combining the lower bound on & with the expressions of Eg and o² of Proposition 3.5, we have that the iteration complexity (by ignoring the logarithmic terms) becomes k 2 2 max((e, 2=² where 6 = h- + n- 1i max and o² = p-b = Thus, the total complex-
implies E|lar* x= 112 <
}. ity of the algorithm as a function of the minibatch size b is given by TC(b) < 2 mmxx(bb,.b b ey By following the same steps with Gower et al. [2019], it can be shown that b6g is linearly increasing term while & 202 is a linearly decreasing term 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 of < Lmax Emaxx 2 . then b otherwise b² 11 nf Emnae op 77

---

In the next theorem, we provide an insightful ceessze-ssitchingg rule that describes when one should switch from constant to 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 j-quasi-strongly monotone and that & E EC(()). Let == t p and let ag = 1 for & 4[1 and 0r = [K+1)=M 2 SGDA, given by (5) satisfy:
2k+1 for K > 4 If 2 4[/]7, then iterates of
0² 8
16
1
Blla* x²
0 x²1² 0
(8)
1 k
2ap2
5 Stochastic Consensus Optimization
The Consensus Optimization (CO) Algorithm is computationally--ighe second order methods which has been introduced in Mescheder et al. [2017] and 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 j-strongly monotone operators with positive singular values of the Jacobian matrix J Vg.
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 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 & in problem (1) is differentiable. That is, we have access to the Jacobian matrices J, (x) = Vε.(z). Following Loizou et al. [2020]. in our analysis we will also assume that the Hamiltonian function is quasi-strongly convex and that 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-mat max problems.
5.1 Setting
The consensus optimization (CO) algorithm as presented in Mescheder et al. [2017] has the following update rule:
+++ = 2* -
(9)
where H(x) = 2 [1x is the Hamiltonian function and at 0 are the step-sizes. From its defini- tion, it is clear that the update rule is essentially a weighted combination of GDA and the Hamiltonian gradient descent (HGD) of Balduzzi et al. 12018). In practice, implementing CO in 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 extend the formulation to capture the arbitrary sampling paradigm. That is, the Hamiltonian function can be expressed as, M(x) ]1(((==)1?2 = x Σ n Σド=1 1 (E)(2)) Eg (z)). In addition, by following the stochastic reformulation setting presented in Section 2. let us have two independent random sampling vectors u ~ D and v ~ DD and let us define: Hu.. = En= n Σj= (u,E(()), UE, (z)). Since
1
vectors u and v are independent sampling vectors, it is clear that En,, (u, (x)] = H(xx), where Eu denotes the expectation with respect to distribution D on both vectors u and v. Let us also
At each step. CO requires only the computation of Jacobian vector product which can be efficiently evaluated in tasks like training neural networks with comparable computation time of a gradient [Pearlmutter, 1994].
7

---

use (z) (z.(z) to express the Jacobian matrices for i, then the gradient of Hy,v(z) has the following form:
1 [ (z) JJ
VHu,o (x)
(10)
where Ja(x) = Ei= (x) and (x) - - C.). Similar to Loizou et al. [2020], it can be shown that (x) is unbiased estimator of VH(x) = J (x))((aa). That is, (v)) VH(z). Throughout this section, we will denote the gradient noise of the stochastic Hamiltonian function with of = Eu,e ll o which is finite for any reasonable sampling distribution D.
5.2 Stochastic Consensus Optimization and its Special Cases
Having explained the basic setting and back- ground consensus optimization algorithm and the Hamiltonian function, let us now present Algorithm 1 the proposed stochas- tic consensus optimization (SCO) algorithm. Note that in each iteration two random sampling vectors u and v are sampled inde- pendently from user-defined distribution D. These vectors are used to evaluate &.+ and VH,,,, (a*), the unbiased estimators of {(a*) and (*((=*) at point = respec- tively. Note also that the update rule of SCO
Algorithm 1 Stochastic Consensus Opt. (SCO)
Input: Starting step-size oo: "No > 0. Choose initial point x. E _dd Distribution D of samples.
for k 0, 1, 2, K do
Sample independently v ~ D and u² ~ D Set step-sizes ag and Th' according to pre- selected step-size rule
Set x x² Eu (x*) V/k VHon at (a*)
end for Output: The last iterate x
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 a² 0, vk > 0 then the method is equivalent to SHGD and if 7* = 0, vk > then the method becomes equivalent to the SGDA. In addition if we select sampling vectors definition of Su+ and VHHa aa (x*) we obtain the deterministic CO (9) as special case of our update rule.
11, 1) R with probability 1, then from the
5.3 Convergence Analysis
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 u-quasi-strongly monotone with μ 2 0 and that E (E(())). Assume that the Hamiltonian function H juu-quaii strongly convex and Cu expeeced smooth. Then, for 7 = y S 46x
and a S 48g the iterates of SCO satisfy:
E [ - 101 S (1 7Hx ax) 1120 101 + 4|a"0² + 7"0
(11)
7H4 + a/
If μ = 0, that is only satisfies the variational stability condition (E(x), x -x*) ) 2 0, then
E [|a* - x [|2] s (1 >YpH)* 120 112 + 41a20² + +
7/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 p--quasi-strongly monotone operators (i.e. both step-sizes a and should be positive up to specific values). However, & simply satisfies the variational stability condition (E(x), x²) > 0 (when μ 0), then the convergence rate of SCO, does not depend on the step-size a (the SGDA part) and the neighborhood of convergence
110202+5~02 is smaller when a 0. Thus, in this case one needs simply run the SHGD. 7P
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 7 and ag I 4es
Y S 47.x
1 the iterates of CO satisfy: || x= 1|2 I (1 7H4 - oqp) || x 2
The result of Corollary 5.2 should be compared 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 partieular, Abernethy al. [2021] gives the rate for CO under similar assumptions, 7 which is clearly slower than our - JL, t 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 " = 0 and Qq a < 1/26g, then SCO becomes equivalent SGDA and Theorem 5.1 matches the convergence guarantees presented in Theorem 4.1, On the other hand, by setting a = O. 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.
4T-x PH
Corollary 5.3. Under the assumptions of Thm. 5.1, a and 2 = 7 S 1/2C Then SCO is equivalent to SHGD and its iterates satisfy: E [||I* [1] - (1 7/4) 1| x= 112
270
All previous results for SCO show convergence to neighborhood of x²" In the next theorem, by selecting decreasing step-sizes (switching strategy) for the values a and y, we are able to guarantee sublinear convergence 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 E is y-quasi-strongly monotone and that & E EC((g). Assume that the Hamiltonian function H is jzz-quasi strongly convex and Lx-expected smooth. Let (y) = The
& max fg. LH} and k* == 8 px Let also, 7/-- = de for h S [k'] and (*+1)]unxtt)
2k++
for k [k If k 2 [ then SCO iterates satisfy:
2 + 0 16
(A-)2
E E|| - x x1
|| =20
(12)
|* k
e2k2
If = O, that is & only satisfies the variational stability condition (E(x), x x²) 2 0, then SCO is still able to converge sublinearly with O (2), to x..
Numerical Evaluation
The purpose of this experimental section is corroborate our theoretical results, which form the main contributions of this paper. To do so, we focus on strongly-monoton quadratic games of the
following form:
1 Σ 2 Am + B,
1
1 T 222 C,22 + a. æ1 C. 22
min max
(13)
RR 22RR
We show that the Hamiltonian function of such a game is -ua-quaii-sroonnly convex and -mootho in App. C.I. For the game to also be strongly-monotte such that HAl < A; < LAI, pcl < C < LcI, and 1 < B B, 3 I where I is the identity matrix; the exact sampling is described in App. C.2. The bias terms ag C₁ 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 a 2
and co-coercive, we sample the matrices
T.
for SGDA (Theorem 4.1), a 42g 7 4Cx
1 for SHGD (Corollary 5.3). For the stepsize-switching rule for SCO (Theorem 5.1), and y 2Cn 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 21, 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 reproduce our results can be found at :tttps://gitaee
R. We show the trajectories of the different algorithms in Fig. la.
Comparison of Algorithms (Constant step-size). We look at the convergence of the methods for different games where we vary the condition number KG fs In comparing the methods, we
For this convergence rate, Abernethy et al. [2021] assumed that the Hamiltonian function satisfies the Polyak- Lojasiewicz condition but focus strongly-come convex and strongly-conen min-max optimization problems.

---

(a) 2d trajectories
(b) KG
(c) KG
(d) KG 25
Figure 1: Convergence of SGDA, SCO and SHGD on different quadratic games. (a) Trajectories of
SHGD SHGD
and SGDA 2d quadratic game. The arrows represent the direction defined by {(x) at particular point
|ı====1||² as a function the number of iterations. Each plot corresponds
(b-d) Distance to optimality ||=0--*
game with particular condition number KG J runs and the colored area represent the 95% confidence intervals.
" The solid lines represent the average performance the
KG
100
(b) Ke
Figure 2: Comparison between constant and decreasing step size regimes SGDA and SCO. The vertical lines correspond to the moment we switch from a constant to a decreasing step-size. The solid lines represent the average performance over the runs and the colored area represent the 95% confidence intervals.
use the relative distance optimality 2- As predicted from our theoretical results, when constant step-size is used, all the methods converge linearly 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 less affected by a larger condition number. We also observe that SGDA is slower than SHGD, but converges
smaller neighborhood of the solution (see e.g. Fig. lb). SCO achieves 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 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 results in Figure 2. As predicted from 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 4 μi]
predicted in Theorem 4.3 while in Figure 2b the red line denotes the value [8 max(fe,Cu) predicted Pe-p
Theorem 5.4. Note that for both algorithms the red line is good approximation of the point where SGDA and SCO need change their update rules from constant decreasing step-size.
Conclusion and Future Directions of Research
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-monon mo--moooooee (quasi- strrngly 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-coereivity), where we expect to obtain slower sublinear rate. We also believe the proposal of expected co-coercivity to be of independent interest; it could be used to provide efficient analysis of other algorithms to solve (1) under the arbitrary sampling paradigm, and would also be interesting to generalize the analysis to the constrained formulation of variational inequalities.
10

---

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-Julis Julien is a CIFAR Associate Fellow in the Learning in Machines & Brains program.
Competing interests. Simon Lacoste-Julien additionally works part time the head of the SAIT Al Lab, Montreal from Samsung. Hugo Berard was working part time as a research intern at Facebook, Montreal.
References
Abernethy, Lai, and A. Wibisono. Last-iterate convergence rates min- max optimization: Convergence of Hamiltonian gradient descent and consensus optimization. In ALT, 2021.
M. Assran, N. Loizou, N. Ballas, and Rabbat. Stochastic gradient push distributed deep learning. ICML, 2019.
W. Azizian, Mitliagkas, S. Lacoste-Julien, and G. Gidel. tight and unified analysis of gradient-based methods for a whole spectrum of differentiable games. In AISTATS, 2020.
Balamurugan and F. Bach. Stochastic variance reduction methods for saddle-pohi problems. In NeurIPS, 2016.
D. Balduzzi, S. Racaniere, Martens, J. Foerster, K. Tuyls, and Gracpel. The mechanics of n-player differentiable games. In [CML, 2018.
H. H. Bauschke, P. L. Combettes, et al. Convex analysis and monotone operator theory in Hilbert spaces, volume 408. Springer, 2011.
L. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
L. Brighi and R. John. Characterizations of pscudomonotone maps and economic equilibrium. Journal of Statistics and Management Systems, 5(1-3):253-73, 2002.
Chavdarova, G. Gidel, Fleuret, and S. Lacoste-Julien. Reducing noise in GAN training with variance reduced extragradient. NeurlPS, 2019.
G. H. Chen and R. T. Rockafellar. Convergence rates in forward-backward splitting. SIAM Journal Optimization, 7(2):421444 1997.
C. Choi, S. DeSarbo, and P. Harker. Product positioning under price competition. Management Science, 36(2):175-199, 1990.
C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng. Training GANs with optimism. In ICLR, 2018.
C. Daskalakis, S. Skoulakis, and M. Zampetakis. The complexity of constrained min-max optimization. In Proceedings the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 1466-1478, 2021.
D. Davis and W. Yin. A three-operator splitting scheme and its optimization applications. Set-valued and variational analysis, 25(4):829 858, 2017.
V. F. Dem't yanov and A. B. Pevnyi. Numerical methods for finding saddle points. USSR Computational Mathematics and Mathematical Physics, 12(5):11-52, 1972.
J. Diakonikolas, C. Daskalakis. and M. Jordan. Efficient methods for structured nonconvex- min-max optimization. In AISTATS, 2021.
A. M. Elizarov and A. Kalimullina. Maximization of the lift/drag ratio of airfoils with a turbulent boundary layer: Sharp estimates, approximation, and numerical solutions. Computational Mathematics and Mathematical Physics, 49(3):559 572, 2009.
F. Facchinei and C. Kanzow. Generalized Nash equilibrium problems. 40R, 5(3): 2007.
F. Facchinei and J.SS Pang. Finite- dimiessiimn variational inequalities and complementarity problems. Springer Science & Business Media, 2007.

---

M. Friedlander and M. Schmidt. Hybrid deterministie-stochastte methods for data fitting. SIAM Journal on Scientific Computing, A43))A13800 2012.
G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julies A variational inequality perspective generative adversarial networks. ICLR, 2018.
Golowich, Pattathil, C. Daskalakis. Tight last-iterate convergence rates for no-regret learning in multi-player games. In NeurIPS, 2020a.
N. Golowich, S. Pattathil, C. Daskalakis, and A. Ozdaglar. Last iterate is slower than averaged iterate in smooth saddle point problems. In COLT, 2020b.
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In NeurlPS, 2014.
R. Gower, O. Sebbouh, and N. Loizou. SGD for structured nonconvex functions: Learning rates, minibatching and interpolation. In A/STATS, 2021.
R. M. Gower, N. Loizou, X. Qian, Sailanbayev, Shulgin, and Richtárik. SGD: General analysis and improved rates. In ICML, 2019.
Harker and J.-S. Pang. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Mathematical programming, 48(1): 1990.
E. Hazan and S. Kale. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research, (00249992222111 2014.
Y.-G. Hsieh, F. lutzeler, J. Malick, and P. Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. In NeurIPS, 2020.
A. Juditsky, A. Nemirovski. and C. Tauvel. Solving variational inequalities with stochastic mirror-pro algorithm. Stochastic Systems, 1(1):17-58, 2011.
Kannan U. Shanbhag. Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants. Computational Optimization and Applications, 74(3): 779 820, 2019.
H. Karimi, J. Nutini, and M. Schmidt. Linear convergence of gradient and proximal-gradien methods under the Polyak-bojasiewiez condition. In ECML-PKDD, 2016.
A. Khaled and P. Richtárík. Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.03329, 2020.
A. Khaled, O. Sebbouh, N. Loizou, R. M. Gower, and Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv preprint arXiv:2006. 1153,, 2020.
A. Koloskova, Loizou, S. Boreiri, M. Jaggi, and S. U. Stich. unified theory of decentralized SGD with changing topology and local updates. ICML, 2020.
Y. Li and Y. Yuan. Convergence analysis of two-layer neural networks with relu activation. In NeurlPS, 2017.
T. Liang and J. Stokes. Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks. In AISTATS, 2019.
T. Lin, C. Jin, and M. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In ICMI., 2020a.
T. Lin, Z. Zhou, Mertikkpoulos, and M. Jordan. Finite-time last-iterate convergence for multi-agent learning in games. In JCML, 2020b.
P.L. Lions B. Mercier. Splitting algorithms for sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16(6):964 979, 1979.
N. Loizou and P. Richtárik. Convergence amalysis of inexact randomized iterative methods. SIAM Journal on Scientific Computing, 42(6):A3979-AM)) A4016, 2020a.
N. Loizou and P. Richtárik. Momentum and stochastic momentum for stochastic gradient, newton, proximal point and subspace descent methods. Computational Optimization and Applications, 77(3):653-713 710, 2020b.
12

---

N. Loizou, H. Berard, A. Joficoeu-Martineau. Hamiltonian gradient methods for smooth games. In ICML, 2020.
Martineau. P. Vincent, S. Lacoste-Julien, and I. Milliagkas. Stochastic
N. Loizou, S. Vaswani, I. Laradji, and S. Lacoste-Julien. Stochastic polyak step-size for SGD: An adaptive learning rate for fast convergence. AISTA7S, 2021.
L. Luo, H. Ye, Z. Huang, and T. Zhang. Stochastic recursive gradient descent ascent for stochastic nonconvex- strongly-coneave minimax problems. NeurIPS, 2020.
Mertikopoulos and 7. Zhou. Learning in games with continuous action and unknown payoff functions. Mathematical Programming, 173())-65--07, 2019.
Mescheder, S. Nowozin, and A. Geiger. The numerics GAN, NeurlPS, 2017.
K. Mishchenko, D. Kovalev, E. Shulgin, Richtárik, and Y. Malitsky. Revisiting stochastic extragradient. In AISTATS, 2020.
Mokhtari, Ozdaglar, and Pattathil, unified analysis of attra-gradiett and optimistic gradient methods for saddle point problems: Proximal point approach. In AISTATS, 2020.
Necoara, Y. Nesterov, and E. Glineur. Linear convergence first order methods non-strongly convex optimization. Math. Program., pages 1-39, 2018.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4):1574-1609, 2009.
Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course, volume 87. Springer Science Business Media, 2013.
L. Nguyen, P. H. Nguyen, M. van Dijk, P. Richtárik, K. Scheinberg, and M. Takáč. SGD and Hogwild! Convergence without the bounded gradients assumption. In ICMI, 2018.
B. Palaniappan and F. Bach, Stochastic variance reduction methods for saddle-point problems. In NeurlPS, 2016.
V. Patel and S. Zhang. Stochastic gradient descent on nonconvex functions with general noise models. arXiv preprint arXiv:2104.00223 2021.
B. A. Pearlmutter. Fast exact multiplication by the Hessian. Neural computation, 6(1):147-160, 1994.
D. Pfau and O. Vinyals. Connecting generative adversarial networks and actor-critic methods. arXiv preprint 1rX0v:161..0195.. 2016.
A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In ICML, 2012.
B. Recht, C. Re, S. Wright, and F. Niu. Hogwild: A lock-free approach parallelizing stochastic gradient descent. NewrIPS, 2011.
Richtárik and M. Takáč, On optimal probabilities in stochastic coordinate descent methods. Optimization Letters, 1033):1233- 2016.
Richtárik and M. Takáe. Stochastic reformulations of linear systems: algorithms and convergence theory. SIAM Journal on Matrix Analysis and Applications, 41(2):487-524, 2020.
Rosasco, Villa, and C. Vü. stochastic forward-backward splitting method solving monotone inclusions in hilbert spaces. arXiv preprint 4rX:v:1403. 7999, 2014.
A. Rousscau, Sharer, S. Pagerit, and S. Das. Trade-off between fuel economy and cost for advanced vehicle configurations. In 20th International Electric Vehicle Symposium (EVS20), Monaco, volume 5, 2005.
M. Schmidt, N. Le Roux, and F. Bach. Minimizing finite sums with the stochastic average gradient. Math. Program., 162(1-2) (11-22):331111 112, 2017.
G. Scutari, D. P. Palomar, F. Facchinei, and J.SS. Pang. Convex optimization, game theory, and variational inequality theory. IEEE Signal Processing Magazine, 27(3):35-49, 2010.
C. Song. Z. Zhou. Y. Zhou, Y. Jiang, and Y. Ma. Optimistic dual extrapolation for coherent non-monnee monotone variational inequalities. NewrIPS, 2020.
13

---

Q. Tran Dinh, D. Liu, and L. Nguyen. Hybrid variance-reduced SGD algorithms for minimax problems with nonconvex-linea -inear function. NeurIPS, 2020.
P. Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Computational and Applied Mathematics, (0(1-2):237-2523 1995.
S. Vaswani, F. Bach, and M. Schmidt. Fast and faster convergence of SGD for over-parameterized models and accelerated perceptron. arXiv preprint arXiv:1810.07288. 2018.
B. C. Vü. splitting algorithm for dual monotone inclusions involving cocnercive operators. Advances in Computational Mathematics, 38(3)6667-681, 2013.
J. Wen, C.-N. Yu, and R. Greiner. Robust learning under uncertain test distributions: Relating covariate shift to model misspecification. ICML, 2014.
J. Yang, N. Kiyavash, and N. He. Global convergence and variance-reduced optimization for class of noncomvex-nonconccae minimax problems. NeurlPS, 2020.
7. Zhou, P. Mertikopoulos, N. Bamhos, S. Boyd, and P. W. Glynn. Stochastic mirror descent in variationally coherent optimization problems. NeurIPS, 2017.
Z. Zhou, P. Mertikopoulos, A. L. Moustakas, N. Bambos, and Glynn. Robust power management via learning and game design. Operations Rexearch, 69(1)33113345, 2021.
D. L. Zhu and P. Marcotte. Co-coercivity and its role in the convergence of iterative schemes for solving variational inqqualities. SIAM Journal Optimization, 6(3)-714-726, 1996.
14


Reviews:
[{"review_id": "waI0QHm7Tm", "reviewer": "Reviewer_94Qg", "summary": "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. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "My overall opinion on the manuscript is positive. The motivation of expected co-coercive condition is strong and the results in Sections 4 and 5 on the convergence analysis of SGDA and SCO are certainly nontrivial. The combination of the finite-sum structure and the unbiased estimators proposed in [30] seems to be intriguing. \n\nNevertheless, this paper seems like a weak accept to me. There are a number of new and interesting results in non-trivial settings but it seems that the authors overclaim their contributions. To be more specific, I encourage the authors to consider the following points:\n\nFirst, the authors compare their assumptions to the standard assumptions in the literature (cf. Table 1) and demonstrate the advantage of the proposed EC condition. While I agree that EC condition is new and useful for analyzing the algorithms, a few assumptions, e.g., bounded gradient condition, seem necessary in a more general non-smooth setting. It is somehow too much to say that expected smoothness/expected cocercivity is one of the weakest assumption for analyzing SGD since they only complement the existing conditions in my mind. \n\nSecond, I bring your attention to the following article: \n\nP. Mertikopoulos and Z. Zhou. \"Learning in games with continuous action sets and unknown payoff functions\". Mathematical Programming. 173: 465–507. 2019. \n\nIn Definition 6.1, the notion of strong stability is defined and resembles the quasi-strong monotonicity in Eq. (2) of the current paper. To the best of my knowledge, such notion has not been adopted to analyze SGDA and SCO so the convergence results in the current manuscript are new. But the authors might cite the above reference and give some credits.  \n\nThird, I think it is a bit unfair to compare your results with [28] and claim that the assumptions on $\\mathbb{E}[\\|\\xi_i(x)\\^2|]$ are unrealistic (Agreed. The assumptions are very restrictive but seem necessary in the setting of [28]). More specifically, all the last-iterate convergence results in this paper are proved under the quasi-strongly monotonicity, which leads to a contraction (even with constraint sets) and plays the similar role as the strong monotonicity from a technical point of view. So there is no need to impose further conditions on the noises. However, the last-iterate convergence analysis in [28] is done without the quasi-strong monotonicity. I check the proof details in the supplementary material and believe that the quasi-strongly monotonicity can not be removed. Then, it gives rise to the question on which one is more realistic, the quasi-strongly monotonicity or the assumption on $\\mathbb{E}[\\|\\xi_i(x)\\^2|]$? The current writing is somehow misleading in the sense that your theorems strictly improve those ones in [28] without imposing any additional assumptions. It would be better to elaborate more on this point and precisely position the contribution of your paper in the literature.   \n\nFinally, if the quasi-strong monotonicity holds true, I am curious whether the solution must be unique (if exist) or not. Moreover, in the unconstrained setting without the quasi-strong monotonicity, the existence of the solution will be an issue. Therefore, I encourage the authors to elaborate more on it, justifying why their results have practical implications (note that most of the real application problems are in constrained setting).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. Compare their conditions on noises to the existing assumptions in the literature more carefully. \n\n2. Elaborate more on the role of quasi-strong monotonicity in their proof and compare their results to [28]. \n\n3. Explain why the existence of the solution will not be an issue and comment on practical implications of their results. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hours"}, "extra_text": {}}, {"review_id": "jKucf7alP8r", "reviewer": "Reviewer_LrZq", "summary": "This paper makes multiple contributions to the convergence analysis of unconstrained stochastic variational inequality problem: \n\n(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.\n\n(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. \n\n(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.\n\n(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. ", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This work makes innovation in both algorithm, assumptions and convergence analysis for unconstrained stochastic variational inequality problem.\n\nQuality: The submission is technically sound. The convergence results are well supported by both theoretical analysis and experimental results. Section 7 describes the limitation that quasi strongly monotone assumption could be removed in future work.\n\nClarity: This work is clear and well organized. \nI appreciate that the relation among EC and other existing assumptions is very clearly shown in a graph. \n\nSignificance:\nThis work has many important innovative results as mentioned in my summary. \n\n\nSome questions and advice:\n\n(1) At the end of page 3, you said “Thus, a function is L-co-coercive”. Do you mean the gradient is L-co-coercive? \n\n(2) Is x* the global solution in Assumption 3.3?\n\n(3) Typo:  “convergence” could be changed to “converge” in the following two sentences: \n(a) At the beginning of Section 3, “It was used to analyze the celebrated forward-backward algorithm (a.k.a, proximal gradient) [29, 8, 37] that is known not to convergence for general monotone operators [5]. ”\n(b) At the beginning of Section 5, “[26] show first that CO convergences linearly in the bilinear case. ”\n\n(4) Typo in Theorem 4.3: Change “for $4\\lceil\\mathcal{K}\\rceil$” into “for $k \\ge 4\\lceil\\mathcal{K}\\rceil$.”\n\n(5) How does sampling distribution $\\mathcal{D}$ or simply batch-size affect the convergence of SCO? I think it better to add this, just as the analysis of the optimal batch-size for SGDA. \n\n(6) Typo right after Theorem 5.1: In the following equation, change $\\mu$ into $\\mu_{\\mathcal{H}}$. \n$$\\mathbb{E}[||x^{k}-x^*||^{2}] \\le(1-\\gamma \\mu)^{k}||x^{0}-x^{*}||^{2}+\\frac{4[\\alpha^{2} \\sigma^{2}+\\gamma^{2} \\sigma_{\\mathcal{H}}^{2}]}{\\gamma \\mu}$$\n\n(7) In Theorem 5.4, can the assumptions that $\\xi$ is quasi-strongly monotone and expected co-coercive imply that $\\mathcal{H}$ is quasi-strongly monotone and expected smooth? \n\n(8) In Figure 2, both subfigures correspond to the same objective function and the difference in $\\ell_{\\xi}$ is caused by the hyper-parameter choice difference, right? If so, I think the 4 curves can be plotted in 1 figure. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Section 7 describes the limitation that quasi strongly monotone assumption could be removed in future work. \nBoth the authors and I do not think this theoretical work could have any immediate societal impact. ", "review_text": "", "extra_scores": {"ethical_concerns": "I think this work has no ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "About 3 hours"}, "extra_text": {}}, {"review_id": "fzcbAaBcHex", "reviewer": "Reviewer_PL4z", "summary": "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. ", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\n[Strengths]\nThis work introduces a new assumption and provides novel analyses for SGDA and consensus optimization. \n- Overall, the paper is well-written and states its contribution clearly.\n\n[Weaknesses]\n- While the results of this work are new, the proof techniques very closely follow the prior work of Gower et al (2019), which provided the convergence analysis on stochastic GD under 'expected smoothness' assumption. Expected co-coercivity for operator setting is analogous to the expected smoothness for nonconvex optimization setting, as these two assumptions only differ in the expression on the upper bound of the squared gradient norm. The proof structures of the work are even quite similar; both works provide the lemma of the similar form which plays essential role in the proof (Lemma 2.4 in Gower et al (2018) & Lemma 3.4 in this paper), prove the main claim in essentially the same manner, using the similar choice of step sizes.\n- I am not sure that I agree with the authors that the introduction of expected cocoercivity is a significant contribution. For that to be the case, I feel like the authors should not only show how the assumption can be used to prove things (which the authors do) but should also demonstrate why the assumption is realistic or interesting (which I feel the authors do not adequately do).\n- Despite the authors' counter example of A.6, I am not convinced that the quasi-strong monotonicity is an assumption significantly or meaningfully weaker than the usual strong monotonicity (strong convex-concavity).\n - It is unclear to me how the \"VI\" perspective meaningfully interacts with the proofs or the theory.\n\n \n\nOverall, while the results presented in this paper are useful to have, I feel that the analysis is too straightforward of an extension of the Gower et al. 2019 prior work. I was not able to find any novel proof techniques. For these reasons, I do not think this paper meets the bar of a NeurIPS publication.\n\n\n[Minor Issues]\n- p.4, line 124 (typo) 'uniforms boundedness' -> 'uniform boundedness'\n- EC(l_\\xi) is also dependent on the distribution \\mathcal{D}. Including \\mathcal{D} in the notation of EC may clarify the definition.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Aqq4RrYiqpm", "reviewer": "Reviewer_kKUx", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The proposed EC condition is a special case of the whole function $\\xi(x)$ being cocoercivity at x^* (as an immediate consequence of Jensen's inequality + EC). As a result, all of the considered problem instances are strongly monotone and cocoercivity at x^*. So the geometry around the limit point is assumed to be very convex-concave. Including meaningful families of nonconvex-nonconcave problems satisfying this would greatly help motivate the work.\n\nA few times, the paper is prone to overclaim its novelty/importance. Below are a few key examples:\n-Line 146: \"There is no analysis using a concept similar to our [EC]\". EC is a natural extension of the very standard cocoercivity assumption. The analysis for SGDA does not deviate notably from the standard model of recursive analysis used for strongly monotone and cocoercivity operators. Also, as noted in Table 1, the EC condition is similar to Expected Smoothness.\n\n-Line 168: \"Theorem 4.1 is the first last-iterate non-asymptotic convergence guarantee for SGDA...\" That sentence then continues to contradict itself pointing out the work of Lin et al. does provide a prior last-iterate non-asymptotic convergence guarantee.\n\n-Line 317: \"We provided the first efficient convergence analysis of SGDA and SCO by introducing the expected co-coercivity assumption.\" I don't know what this claim means, but it is certainly not the case that all prior works have been inefficient.\n\n\nMinor comments \n-Line 283: Appears to be missing identity matrices in the p.s.d. matrix upper and lower bounds.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The only application thoroughly considered by the work is a simple bilinear matrix game. This may be partly due to the above comment that assuming strongly monotone and cocoercivity at x^* heavily limits the range of applications. Discussing these limitations up front and the limitations like cycling and divergence that are known to occur in non-monotone settings would give a fuller picture of where these methods can be guaranteed to work and the scale of advancement this work represents.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a new 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. Reviewers find the new conditions very interesting, and very mild in many settings. Therefore the new convergence results under these mild settings are rather strong. The techniques developed here are also of broad interests. 

Decision: Accept (Poster)