Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise
Authors: Eduard Gorbunov
Marina Danilova
David Dobre
Pavel Dvurechensky
Alexander Gasnikov
Gauthier Gidel
Venue: NeurIPS 2022 Accept (2022)
Keywords: heavy-tailed noise
variational inequalities
extragradient method
gradient descent-ascent
high-probability bounds
clipping

Abstract: Stochastic first-order methods such as Stochastic Extragradient (SEG) or Stochastic Gradient Descent-Ascent (SGDA) for solving smooth minimax problems and, more generally, variational inequality problems (VIP) have been gaining a lot of attention in recent years due to the growing popularity of adversarial formulations in machine learning. While high-probability convergence bounds are known to more accurately reflect the actual behavior of stochastic methods, most convergence results are provided in expectation. Moreover, the only known high-probability complexity results have been derived under restrictive sub-Gaussian (light-tailed) noise and bounded domain assumptions [Juditsky et al., 2011]. In this work, we prove the first high-probability complexity results with logarithmic dependence on the confidence level for stochastic methods for solving monotone and structured non-monotone VIPs with non-sub-Gaussian (heavy-tailed) noise and unbounded domains. In the monotone case, our results match the best known ones in the light-tails case [Juditsky et al., 2011], and are novel for structured non-monotone problems such as negative comonotone, quasi-strongly monotone, and/or star-cocoercive ones. We achieve these results by studying SEG and SGDA with clipping. In addition, we numerically validate that the gradient noise of many practical GAN formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.

Clipped Stochastic Methods
for Variational Inequalities with Heavy-Tailed Noise
Eduard Gorbunov*t
Marina Danilova" MIPT, Russia
David Dobre Mila & UdeM, Canada
Pavel Dvurechensky WIAS, Germany
MIPT, Russia
Mila UdeM, Canada
MBZUAI, UAE
Alexander Gasnikov
Gauthier Gidel
MIPT, Russia
Mila UdeM, Canada Canada CIFAR AI Chair
HSE University, Russia IITP RAS, Russia
Abstract
Stochastic finst-order methods such as Stochastic Extragradient (SEG) or Stochastic Gradient Descent-Ascent (SGDA) for solving smooth minimax problems and, more generally, variational inequality problems (VIP) have been gaining a lot attention in recent years due the growing popularity of adversarial formulations in machine learning. However, while high-probability convergence bounds are known to reflect the actual behavior of stochastic methods more accurately, most convergence results are provided in expectation. Moreover, the only known high- probability complexity results have been derived under restrictive sub-Gaussian (light-tailed) noise and bounded domain assumption [Juditsky et al., 201 la]. In this work, we prove the first eig-prrbabillty complexity results with logarithmic dependence on the confidence level for stochastic methods for solving monotone and structured non- monotone VIPs with non-sub- Gaussian (heavy-tailed) noise and unbounded domains. In the monotone case, our results match the best-known ones in the light-tails case [Juditsky et al., 201 la], and are novel for structured non-monotone problems such as negative comonotone, quasi-strongly monotone, and/or star-cocoercive ones. achieve these results by studying SEG and SGDA with clipping. In addition, we numerically validate that the gradient noise of many practical GAN formulations is heavy-tailed and show that clipping improves the performance of SEG/SGDA.
Introduction
Recently, game formulations have been receiving lot of interest from the optimization and machine learning communities. In such problems, different models/players competitively minimize their loss functions, e.g., see adversarial example games [Bose et al., 2020], hierarchical reinforcement learning [Wayne and Abbott, 2014, Vezhnevets et al., 2017], and generative adversarial networks (GANs) [Goodfellow al., 2014]. Very often, such problems studied through the lens of solving a variational inequality problem (VIP) [Harker and Pang, 1990, Ryu and Yin, 2021, Gidel et al.,
'Equal contribution.
1 CCorresoondig author: eduard. caaarrddgorbunoobbzzuaaii ac.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

2019a]. In the unconstrained case, for an operator' F : Rd - R.d VIP can be written as follows:
find x² Ex where x= (x" E R" such that F(x") = 03.
(VIP)
In machine learning applications, operator F uuualll has an expectation form, i.e. F(x) E (+)), where z corresponds to the parameters of the model, & is a sample from some (possibly unknown) distribution D, and F2((z) is the operator corresponding to the sample ç.
Such problems are typically solved via first-order stochastic methods such Stochastic Extragradient (SEG), also known as Mirror-Prox algorithm [Juditsky et al., 201 Ia], or Stochastic Gradient Descent- Ascent (SGDA) [Dem' yanov and Pevnyi, 1972, Nemirovski et al., 2009] due their practical efficiency. However, despite the sigmificant attention to these methods and their modifications, their convergence is usually analyzed in expectation only, e.g., see [Gidel al., 2019a, Hsieh et al., 2019, 2020, Mishchenko et al., 2020, Loizou et al., 2021]. In contrast, while high-probability analysis more accurately reflects the behavior of the stochastic methods [Gorbunov al., 2020], little is known about it in the context of solving VIP. To the best of our knowledge, there is only one work addressing this question for monotone variational incqualities [Juditsky et al., 201 However, [Juditsky et al., 201 la] derive their results under the assumption that the problem has night-tailedd" noise and bounded domain, which is restrictive even for simple classes of minimization problems [Zhang et al., 2020b]. This leads us to the following open question.
Q1: Is it possible to achieve the same bigh-probabblity results as in [Juditsky et al., 2011a] without assuming that the noise is sub- Gabusiaan and the domain is bounded?
Next, in the context of GANs' training, empirical investigation [Jelassi et al., 2022] and practical use [Gulrajani et al., 2017, Miyato al., 2018, Tran al., 2019, Brock et al., 2019, Sauer et al., 2022] indicate the practical superiority of Adam-based methods, e.g., alternating SGDA with stochastic estimators from Adam [Kingma and Ba, 2014], over classical methods like SEG or (alternating) SGDA. This interesting phenomenon has rigorous theoretical explanation yet. In contrast, there exists a partial understanding of why Adam-like methods perform well in different tasks such as train- ing attention models [Zhang et al., 2020b]. In particular, Zhang et al. [2020b] empirically observe that stochastic gradient noise is heavy-tailed in several NLP tasks and theoretically shows that vanilla SGD [Robbins and Monro, 1951] [] can diverge in such cases and its version with gradient clipping (clipped- SGD) [Pascanu et al., 2013] converges. Morcover, the tfate-of-the-art results for heavy-tailed stochastic minimization problems are also obtained for the methods with gradient clipping [Nazin et al., 2019, Gorbunov et al., 2020, 2021, Cutkosky and Mehta, 2021]. Since Adam can be seen version of adaptive clipped-SGD with momentum [Zhang et al., 2020b), these advances establish the connection between good performance of Adam, heavy-tailed gradient noise, and gradient clipping for minimization problems. Motivated by these recent advances in understanding the superiority of Adam for minimization problems, we formulate the following research question.
geeeh-rbbbbblitty convergence
Q2: In the training of popular GANs, does the gradient noise have heavy-tailed distribution and does gradient clipping improve the performance of the classical SEG/SGDA?
In this paper, we give positive answers to Q1 and Q2. In particular, we derive high-probability results for CSipped-SEG and clipped-SDGA for monotone and structured non-monotone VIPs with non-sub-Gaussial noise, validate that the gradient noise in several GANs formulations is indeed heavy-tailed, and show that gradient clipping does significantly improve the results of SEG/SGDA in these tasks. That is, our work closes a noticeable gap in theory of stochastic methods for solving VIPs.
1.1 Technical Preliminaries
Before we summarize our main contributions, introduce some notations and technical assumptions.
Notation. Throughout the text (ar, v) is the standard inner-product, || / (z. æ)) denotes norm, (x) {u d ||u I| S r). B[X] and EEg [X] are full and conditional expectations w.r.t the randomness coming from & of random variable X. PPE) denotes the probability of event E. Ro
||I00 - || denotes the distance between the starting point x of method and the solution x of VIP.
2 'oor example, when we deal with a differentiable game/minimax problem, F can be chosen as the concatena- tion of the gradients of the players' objective functions, e.g., see [Gidel et al., 2019a] for the details. If not specified, we assume that x" is the projection of x to the solution set of VIP.
2

---

High-probability convergence for VIP. For deterministic VIPs there exist several convergence
metrics P(x). These metries include restricted gap-function [Nesterov, 2007] Gap R (z) := v), (averaged) squared norm of the operator || [=(=))]? and squared distance
maxyeBB(e*) (F to the solution || - x=1l Depending on the assumptions the problem, one another criterion is preferable. For example, for monotone and strongly monotone problems (z and || - x=1 are valid metrics of convergence, while in the mo-moootone case, one typically has use [=)())
In the stochastic case, one needs either to upper bound E[P(z) or to derive a bound on P(x)) that holds with some probability. In this work, we focus on the second type of bounds. That is. for a given confidence level / E (0, 1], we aim at deriving bounds on P(x) that hold with probability at least 1 - B, where x is produced by Sropeed-EG//clipeed-- -eDD... However, to achieve this goal one has to introduce some assumptions on the stochastic noise such as bounded variance assumption, which is standard in the stochastic optimization literature [Ghadimi and Lan, 2012, 2013, Juditsky et al., 201 lb, Nemirovski et al., 2009]. We rely on a weaker version of this assumption.
Assumption 1.1 (Bounded Variance). There exists bounded set Q S IRd and 2 such that
E [1F((2) F(=)ll o2, VZEQ.
In contrast most of the existing works assuming (1) the whole space/domain, need (1) to hold only on some bounded set Q. More precisely, in the analysis, we rely on (1) only on some ball Rg- Although we consider an unconstruined VIP,
B, (x=" around the solution x² and radius SEG/Clipped-SSCC -SDA stay inside this ball with high we manage to show that the iterates of clipped-SEG/clipper probability. Therefore, for achieving our purposes, it is sufficient make all the assumptions on the problem only in some hall around the solution.
We also notice that the majority of existing works providing high-probability analysis with logarithmic dependence on l/8 rely on the so-called light tails assumption: E(exp([1F -(x)) /)=)] I exp(1) meaning that the noise has sub-Gaussiar distribution. This assumption always implies (1) but not vice versa. However, even for minimization problems, there are only few works that do not rely on the light tails assumption [Nazin et al., 2019, Davis et al., 2021, Gorbunov et al., 2020, 2021, Cutkosky and Mehta, 2021 J. In the context of solving VIPs, the existing high-probability guarantees in [Juditsky al., 201 Ia] rely on the light tails assumption.
Optimization properties. We also need to introduce several assumptions about the operator F. We start with the standard Lipschitzness. As we write above, all assumptions are introduced only some bounded set Q, which will be specified later.
Assumption 1.2 (Lipschitzness). Operator F Rdd TR. is L--Lisschiz on Q S Rdd. i.e.
[F(()) - F(y)ll S L||x- filz-yll, yll. Vz,yeQ. Q.
(Lip)
Next, we need to introduce some assumptions on the monotonicity of F, since approximating local first-order optimal solutions is intractable in the general non-monotone case DDaskalakis et al., 2021, Diakonikolas et al., 2021]. We start with the standard monotonicity assumption and its relaxations.
Assumption 1.3 (Monotonicity). Operator F: : Rdd + TRd is monotone on Q C Rdd, ie..
(F(x) - F(y), x y) 20, O, VE,YEQ.
(Mon)
Assumption 1.4 (Star-Negatiog Comonotonicity). Operator F Rdd - Rd is p-star-negatively comonotone on Q C Rdd for some E [0, +oc), for any x² we have
(F(x),I-x") 2 =1) VIEQ.
(SNC)
When p 0, the operator F is called star-monotone (SM) on Q.
(SNC) is also known as weak Minty condition [Diakonikolas et al., 2021], a relaxation of negative comonotonicity [Bauschke et al., 2021]. Another name of monotoootty (SM) is variational sta- bility condition [Hsich et al., 2020]. The following assumption is relaxation of strong monotonicity.
$ UUsing Markov inequality, one can easily derive high- probabibbability bounds with non-desirable polynomial dependence on 1/8, c.g., see the discussion in [Davis et al., 2021, Gorbunov et al., 2021]. 'Each complexity result, which we derive, relies only one or two of these assumptions simultaneously.
3

---

Table I: Summary of known and high-prohabiliry complexity results for solving variational inequaliries. Column "Setup" indicates the additional assumptions in addition to Assumption 1.1. All assumptions are made only on some ball around the solution with radius ~ Ro (unless the opposite is indicated).
the complexity we mean the number of stochastic oracle calls nceded for method to guarantee that If (Metric S <) 2 B for some > 0, 9 E (0, 1] and "Metric" is taken from the curresponding column. For simplicity, we omit numerical and logarithaic factors in the complexity bounds. Columa "HI'" indicates whether the result is derived in the heavy-tailed case (without assuming that the noise sub Gaussian) and column "UD!"" shows whether the unalysis works unbounded domains. Nolation: Fang n Σx z" (for clipped SEG), Zag n Σ x" (for clipped SGDA), L = Lipschitz constant: D = diameter of the domain (used in Judissky et al., 2011al); Gap (2) maxxy x (F(y), x 9). where X bounded domain with diameter D where the problem is defined (used Puditsky gl. 2011a]): o² bound on the variance (in the results from Puditsky al. 201 o² sub-Gaussian variance); St= = any upper bound on || at" ||: fa = quasi strong monotonicity parameterr = stur cocoercivity parameter.
Sctup
Mothod
Citation
Metric
Complexity
HT?
UD?
Mirror-Pue Protor-rrox
Duditsky al., 2011a|""
Gapp (#
max
LB
x
(Mon)+(Lip)
clipped-SEG
Thm.. C.I & Cor, C.I
Gap (F
max
LR2
a² x2
/
(SNC)LLip)
clipped SEG
Thm. C.2 & Cor, C22
||
L max
n2
x
x2
xt
/
/
(QSM)<Lipp
clipped-SEG
Thmn. C.3 & Cor, C33
11x K x111"
x²
/
(Mon)+(SC)
clipped-SGDA
Thm. D.I & Cor, DJ
(1pp(1
max
282
st
(SC)
clipped SGDA
Thm. D.2 & Cor, D.2
Σ |1F(2))12
e max
<2n²
(QSM)+(SC)
clipped-SGDA
Thm. Cor, D.3
1| x =1
max
Monotonicity and Lipschitzneas F are assumed on the whole domain.
3 The results holds for any 0 S p S 1/cesor. 4), where A m In sLK 111 if parameters the methad are set property. Moreaver, batchsizes should be large enough (see Thm. 2.1 and C.2 for the details).
Assumption 1.5 (Quasi-Strong Monotonicity). Operator F R + Rd is u-quasi strongly monotone
on Q C Idd for some μ 2 0, i.e.,
[()),x-x')> 2 p|| - 13 E Q. where x² is the unique solution of (VIP). (QSM)
Under this name, the above assumption is introduced by [Loizou et al., 2021], but it is also known as strong coherent Song et al. [2020] and strong stability [Mertikopoulos and Zhou, 2019] conditions. Moreover, unlike strong monotonicity that always implies monotonicity, (QSM) can hold for non- monotone operators [Loizou et al., 2021, Appendix A.6]. However, in contrast to (Mon), (QSM) allows to achieve linear convergence' of deterministic methods for solving VIP.
Finally, we consider a relaxation of standard cocoercivity: ((F(x)-F(y))..) x) 2 (P(x)-F(j))
Assumption 1.6 (Star-Cocoercivity). Operator F Rd - TRd is E-star-cocoercive on Q C Rd for some E >>000 iee.
|F())|| S ((F()),
Vx E where x² is the projection of x on X
(SC)
This assumption introduced by [Loizou et al., 2021]. (Mon) One can construct an operator F being star-cocoercive. but not cocoercive [Gorbunov et al., 2022b]. Moreover, although cocoercivity implies monotonicity and Lipschitz- ness, there exist operators satisfying (SC), but neither (Mon) nor (Lip) [Loizou et al., 2021, $A.6]. We sum- marize the relations between the assumptions in Fig. I.
(SM)
(SNC)
1
1
HLip) (SC)
(QSM)
Figure 1: Relation between the assumptions on the structured non-monotonicity the problem.
1.2 Our Contributions
New crobbbbbbbbility results for VIPs with htavy- noise. In our work, we circumvent the limitations of the existing high-probability analysis of stochastic methods for solving VIPs [Juditsky et al., 201 la] and derive the first high nigh-probability results for the methods that solve monotone VIPs with heavy-tailed noise in the unconstrained case. The key algorithmic ingredient helping to achieve these results is a proper modification of SEG and SGDA based on the gradient clipping Moreover, we derive several high-probabilityy SGDA applied to solve struetured non-monotone VIPs. To the
and leading to our clipped-SEd and results for Hiipped-SEG/clipper best of our knowledge, these results do not have analogs even under the light tails assumption. We summarize the derived complexity results in Tbl. 1.
'Linear convergence can be also achieved under different relatively weak assumptions such as sufficient bilinearity [Abernethy et al., 2019, Loizou et al., 2020] or error bound condition [Hsieh al., 2020J.

---

Tight analysis. The derived complexities satisfy desirable for -robbabbybyl results property: they have logarithmic dependence on 1/s. where 3 is a confidence level. Next, up to the logarith- mic factors, our results match known lower bounds in monotone and strongly monotone cases (Beznosikov et al., 2020]. Moreover, we recover and even improve the results from [Juditsky et al., 2011a], which are obtained in the light-tailed case, since our bounds do not depend on the diameter of the domain, see Tbl. for the details.
Weak assumptions. One of the key features of our theoretical results is that it relies on assumptions restricted to a ball around the solution. We achieve this via showing that, with high probability, (oopeedsEG/clippe---e
do not leave a ball (with radius proportional to Ro) around the solution. In contrast, the existing works on stochastic methods for solving VIPs usually make assumptions such as boundedness of the variance and Lipschitzness on the whole domain of the considered problem. Since many practical tasks are naturally unconstrained, such assumptions become too unrealistic since, e.g., stochastic gradients and their variance in the training of neural networks with more than layers grow polynomially fast when x goes to infinity. However, for a large class of problems including the ones with polynomially growing operators, boundedness of the variance and Lipschitzness hold on any compact set. That is, our analysis covers a broad class of problems.
Numerical experiments. We empirically observe that heavy-tailed gradient noise arises in the training of several practical GANs formulations including StyleGAN2 and WGAN- More- over, our experiments show that gradient clipping significantly improves the convergence of SEG/SGDA on such tasks. These results shed a light on why Adam-based methods are good at training GANs. Our codes are publicly available: https: ////t//ttbb//// com hoam/buuycaaa ibrating/ el stpppe--tochhssti--eetll..
1.3 Closely Related Work
In this section, we discuss the most closely related works. Further diseussion is deferred to $ A.
High-probability convergence. To the best of our knowledge, the only work deriving high- probability convergence in the context of solving VIPs is [Juditsky et al., 2011a], In particular, Juditsky et al. [2011a] consider monotone and Lipschitz VIP defined on a convex compact set X with the diameter D maX2, y |x yll, and assume that the noise in (z) is light-tailed. In this setting, Juditsky et al. [201 Ia] propose a stochastic version of the celebrated Extragradient method (EG) [Koreelevich, 1976] with non- non- Euclidean proximal - Mirror-Prox. Moreover, Juditsky et al. [201 Ia] derive that after K- O(max( LD² o²D²
6² In? }1)) stochastic oracle calls for some E >> O,
e (0, 1], the averaged extrapolated iterate 7 avg K+1 E Ttth (see also clipped-SEG) satisfies Gap < E with probability at least 1 - B. Although this result has a desirable logarithmic dependence on 1/8 and optimal dependence on [Beznosikov et al., 2020], it is derived only for (i) taile case and (ii) bounded domains. Our results do not have such limitations.
2 Clipped Stochastic Extragradient
In this section, we consider version of SEG with gradient clipping. That is, we apply clipping operator clip(y, A) := min(1, M/Ilil which is defined for any y E Rd (when y 0 we set clip(0, A) == 0) and any clipping level > 0, to the mini-batched stochastic estimators used both at the extrapolation and update steps of SEG. This results in the following iterative algorithm:
x = xx
-1/ Feg (I*),
where at = x² - - Fet (2**)
(clipped- SEG)
1
m1
Fet (2*) clip
F
Fat clip
F
A2,6
mi,k
m22.
where ( my algorithm, clipping bounds the effect of heavy-tailedness of the gradient noise, but also creates a bias
mi
(52 J are independent samples from the distribution DD In the considered
k )
'These lower bounds are derived for the convergence in expectation. Deriving tight lower bounds for the convergence with high-probabiliyy for solving stochastic VIPs is an open question.
'In this case, the goal is to find x" E X such that inequality (F(x"), ) x²) 2 0 holds for all x X.
5

---

that one has to properly control in the analysis. Moreover, we allow different stepsizes 7,, 722 [Hsieh al., 2020, Diakonikolas et al., 2021, Gorbunov al., 2022a], different batchsizes m1,k; m2,k- and different clipping levels X1, λ2,- In particular, taking ?2 < 71 is crucial for our analysis to handle VIP satisfying star-negative comonotonicity (SNC) with p > O. Our convergence results for clipped-SEG are summarized in the following theorem. For simplicity, we omit here the numerical constants, which are explicitly given in $ C.
runfor Theorem 2.1. Consider clipped-SEE SEG run for K 2 0 iterations. Let R 2 Ro = ||00 x"11.
Case 1. Let Assump. 1.1. 1.2, 1.3 hold for Q = BIÆ(x"), where 71 = 122 ? with 0 < 7
((V(L)),, A1.K = X2.6 = X = (R((G))), m1,k = 22,k =\t m = 52(max (1, (k+1)700 A/ 1/11)))
where A = In 6(K+1), 3 E (0, 1] are such that A 2 1. B Case 2. Let Assump. I.I, 1.2, 1.4 hold for Q = Bsn(=*), where 72 + 2p S n 1
O(1(LLA),, NIA = X = ② ())) d2 = d2 = (RR/s2a)), mi, = mi
(mmax[1, 7a / /TtTa(K+ }).)), m22 = m2 = [(max (1, (K (K+1)730 o A/R²) })
where A = In 8(K+1, 3 E (0, are such that A 2 1.
Case 3. Let Assump. 1.1, 1.2, 1.5 hold for Q = BaR(x*), where 71 72 7 with
0< 7 S O(((LA)), \1.k = 22, = 2x= =
(/((A))))/((()))) mi,k = m2,k = m. =
M(max[1, (K+1)n' (axx)"""(((xp(/x/uaaa A/(exp(-nut) where A = In 6(K+1), B (0, 1] are such that A 2 1.
B
Then, to guarantee Capp( S E in Case I with Tayg
1 Eko
- K+ k=u | M(* s
k+1
Le in Case 2, ||xcK xx 112 S & in Case 3, with probubility > 1 3 clipped-SEE requires
Case I and 2: 5 (max
{ Lie o 2²²) {
max { L o²
and
Case 3:
{ a Me
(2)
oracle calls. The above guarantees hold in two different regimes: large step-sizes 7 R (requiring large batch-sizes), and small step-sizes, allowing small batch-sizes = O().
Proof sketch in Case 1. Modifying the analysis of EG, we first derive that for all 1. 2 0 we have
GapR ( and ||x= 112 are not greater than m u1|² + 2y > - (x' u lie in Ban(x*) for all / = =0, 1,..,. t 1, where 7F 01) E (1 + 2|1m]113) if x', I²
8: F( Fej (T') and wt F(z')- - Fgg (a'). Next, using this recursion and the induction
argument, we show that with high probability x", A² E BaR(=*) ) for all t t 0, 1,.,,.,, K + 1. This gives us an upper bound for Gap (ollg)) After that, we upper bound max (27 Eizd
2/|wz]1 ( by 5R² with high-probabiling We achieve this via the u -FFF("", (, A.) E/= [110:1] 2 +
proper choice of the clipping level À ((R((74) implying that [|F('))| S A/2 and [[F('')] s A/2 with high probability for all 1 = 0, 1,..... t----111 1. This clipping politics helps to properly bound the bias and the variance of the clipped estimators using Lem. B.2. After that, it remains to apply the
Bernstein inequality for the martingale differences (Lem. B. See the detailed proof in $ C.
In addition to the discussion given in the introduction (see $ 1.2, 1.3 and Tbl. 1), we provide here several important details about the derived results. First of all, we notice that up the logarithmic factors depending on 3 our bogghhrobability convergence results recover the state-of-the-ar in- expectation ones for SEG in the monotone [Beznosikov et al., 2020], star-negative comonotone [Diakonikolas et al., 2021], and quasi-strongly monotone [Gorbunov et al., 2022a] cases. Moreover, as we show in Corollaries C.I and C.3, to achieve these results in monotone and quasi-stronge monotone cases, it is sufficient to choose constant batchsize m (() and small enough stepsize 7. In contrast, when the operator is star-negatively comonotone, we do rely on the usage of large stepsize "1 and large batchsize my O(K) for the extrapolation step to obtain (2). However, known in-expectation results from [Diakonikolas et al., 2021, Lee and Kim, 2021] also rely on large O(K) batchsizes in this case. We leave the investigation of this limitation to the future work.

---

3 Clipped Stochastic Gradient Descent-Ascent
In this section, we extend the approach described above to the analysis of SGDA with clipping. That is, we consider the following algorithm:
k+1 = xxe - FF where (x*) clip
Σ Fgi. (I*), As
(clipped-SGDA)
where )m= are independent samples from the distribution D. In the above method, clipping plays a similar role as in clipped-SEG. Our convergence results for clipped-SGDA are summarized below. The general idea of the proof is similar to the one for clipped-SED SEG, see the details in Appendix D, where we also explicitly give the constants that are omitted here for simplicity.
/im1
Theorem 3.1. Consider clipped SGDA run run.for K 2 0 iterations. Let R 2 Rg = ||x² - x=|| ||-
Case 1. Let Assump. 1.1, 1.3, 1.6 hold for Q B3R(x*), where 0 < 7 = O(/(eA)). A X
((R(()))), my = m = [1max(1, (, "1
where 3 E (0, 1] and A = In b(K+1) 2 I.
Case 2. Let Assump. 1.1, 1.6 hold for Q B2R(=*), where 0 7 (1/(L))), d = X A'/²²)) where B E (0, 1] and A In 4(K+1)
((B/GA))), my = m (2(mmx (1,nxxx1,KK1),2" (K+1),
2 1.
1
Case 3. Let Assump. 1.1, 1.5, 1.6 hold for Q = B2n(x"), ) where 0 < = (1%((e))) dk =
@(2 (0020 B), m, = [1,ax[1, (K+1ino }). where 3 E (0, 1] and In 1(++1)
2 1.
(TA)
ornE R
Then, to guarantee Gapn((Tgg) S E in Case 1 with i = R Ex Tt K+1 En || s
is in Case 2, ||atKK - xx S in Case 3, with probability 2 1 B. dlipped-SDD requires
Case I and 2: ō (max
CR { e²(²))
{ o²
}
and
Case 3:
max
(3)
1 NE
oracle calls. The above guarantees hold in two different regimes: large step-sizes y 1/EA (requiring large batch-sizes), and small step-sizes, allowing small batch-sizes m (1).
As for the CEipped-SEG, up to the logarithmic factors depending on 3, our vergence results from the theorem above recover the state-of-the-ard in-expectation ones for SGDA under monotonicity and star-cocoercivity [Beznosikov et al., 2022], star-cocoercivity [Gorbunov et al., 2022a]t0 quasi-strong monotonicity and star-cocoercivity [Loizou et al., 2021] assumptions. Moreover, in all the cases, one can achieve the results from (3) using constant batchsize m = O()) and small enough stepsize (see Corollaries D.I, D.2, D.3 for the details). Finally, to the best of our knowledge, we derive the first high- siah-probabblity convergence results for SGDA-type methods.
con-
4 Experiments
To validate our theoretical results, we conduct experiments on heavy-tailed min-max problems to demonstrate the importance of clipping when using non-adaptive methods such as SGDA or SEG. We train Wasserstein GAN with gradient penalty [Gulrajani et al., 2017] on CIFAR-10 10 [Krizhevsky et al., 2009] using SGDA, clipped-SGDA, and Hipped-SEG, and show the evolution of the gradient noise histograms during training. We demonstrate that gradient clipping also stabilizes the training of more sophisticated GANs when using SGD by training a StyleGAN2 model [Karras et al., 2020] on FFH [Karras et al., 2019], downsampled to 128 128. Although the generated sample quality is not competitive with model trained with Adam, we find that StyleGAN2 fails to generate anything meaningful when trained with regular SGDA whereas clipped methods learn meaningful features. We do not claim to outperform state-of ofate-of-the-art the-art- adaptive methods (such as Adam); our focus is to validate our thcoretical results and to demonstrate that clipping improves SGDA in this context.
WGAN-GP. In this section, we focus on the ResNet architecture proposed in Gulrajani et al. [2017]. and we adapt our code from publicly available WGAN-GP implementation. II We first compute the gradient noise distribution and validate if it is heavy-tailed. Taking the fixed randomly initialized
10 Althooghh Gorbunov et al. [2022a] do not consider SGDA explicitly, does fit their framework implying that SGDA achieves रो. Σ |||| F( < after K = O(max tn? =²x²" https::// trub.u..aao httpaa/ccccmeee67777////////.../
= }) itcrations with m 1.
gan- collections
7

---

200
150
(a) SGDA (67.4)
(b) clipped-SGii (19.7)
(c) clipped-SEE SEG (25.3)
100
Denity
3.
Past 4603
o 81
22.2
0.00
0.06
At 33.40
Pui 3B8
50
0.m
SGDA
SEG
Cip-SGDA
Cip Cipsse
Clp-SGDA
ciu-seg
[crerd)
(ceard)
0.00
Iistd Roo0
Hyperparameters
(d) Generator
(e) Discriminator
Figure 2: (a, h, c) Random samples generated from the best CIFAR models trained (100k steps) by the specified optimizers, with their corresponding FIDs. (d, Gradient noise histograms for WGAN-GP upon initialization; a Gaussian was fit using maximum likelihood estimation showcase the tail of the distribution. Pmn a value estimating the "heavy tailed-ness of the distribution. (I) The best (lowest) FID scores obtained within the first 35k (out of 100k) training iterations for the same WGAN-GP model trained on CIFAR-1O when sweeping over different typerparameters. Red points indicate that the run diverged, meaning that the loss becomes NaN. Note that we clip the FID for diverged runs to 300 to not skew the boxplot. Boxes are the quartiles of data.
weights, we iterate through 1000 steps (without parameter updates) to compute the noise norm for each minibatch (sample with replacement as in normal GAN training). We show the distributions for the generator and discriminator in Fig. 2 and also compute PmR = Fi.5(X (X) and PeR = (X)). where (X) P(Qs + XQQs Q1) < X). X is the gradient noise distribution, and Q4 is the 7thh quartile. This is metric introduced by Jordanova and Petkova [2017] 7] to measure how heavy- tailed a distribution is based on the distribution's quantiles, where Pm and PER quantify "mild" and "extreme" (right side) heavy tails respectively. A normal distribution should have pm RR R 0.0035 and PeRN R 1.2 x 10 10-6, 6. In all tests, we compute the ratios pm = R. R/PmRN' and PeR = PeR/ PeRR/PRN'' PERR and empirically find that we at least have mild heavy tails, and sometimes extremely heavy tails.
We train the ResNet generator on CIFAR-10 with SGDA/SEG, and diipedd-SDD/SEE the default architectures and training parameters specified in Gulrajani et al. [2017] (AOp = 10, Adis = 5, learning rate decayed linearly to 0 over 100k steps), with the exception of doubling the feature map of the generator. The clipped methods are implemented as standard gradient norm clipping, applied after computing the gradient penalty term for the critic. In addition to norm clipping. we also test coordinate-wist gradient clipping, which is more common in practice [Goodfellow et al., 2016b]. For all methods, we tune the learning rates and clipping threshold where applicable. We do not use momentum following a standard practice for GAN training [Gidel et al., 2019b].
We use
We find that clipped methods outperform regular SGDA and SEG. In addition to helping prevent exploding gradients, clipped methods achieve bettrr Fréchet inception distance (FID) score [Heusel al. 2017]: the best FID obtained for clipped methods is 19.65 in comparison 67.37 for regular SGDA, both trained for 100k steps. A summary of FIDs obtained during hyperparameter tuning shown Fig. 2, where the best FID score obtained in the first 35k iterations is drawn for each hyperparameter configuration and optimization method. At high level, we do a log- log-space sweep over (2c-5, 0.2] for the learning rates, [10-| 10] for the norm-clip parameter, and [10 100'1 for the coordinate clip parameter (with some exceptions) please refer to $ E for further details. We also show the evolution of the gradient noise histograms during training for SGD and clipped-SGDA SGDA in Fig. 4. Note that for regular SGD, the noise distribution remains heavy tailed and does not appear to change much throughout training. In contrast, the noise histograms for clipped-SGri -GDA (in particular the generator) seem to develop lighter tails during training.
StyleGAN2. We extend our experiments to StyleGAN2, but limit our scope clipped-SGDA with coordinate clipping as coordinate clipped-SGDa generally performs the best, and StyleGAN2 expensive to train. We train on FFHQ downsampled to 128 x 128 pixels, and use the recom- mended StyleGAN2 hyperparameter configuration for this resolution (batch size = 32, 7 = 0.1024, map depth- = 2, channel multiplier = 16384), see further experimental details in $ E. We obtain the gradient noise histograms at initialization and for the best trained dlipped-SGDA from the hyperparameter sweep and once again observe heavy tails (especially in the discriminator, see Fig. 3). We find that all regular SGDA runs fail to learn anything meaningful, with FID scores fluctuating
8

---

Generator
20
01 0:021
7.33
Denstry
1.5
634.9
Dorelty
6.28
Per
8.026
0.23
1.0
6.16
6,35
3.5
4.0
13
15
20
19080 Viginillz
11000
- 96gHil
Discriminator
p: 0:17
0.38
5-38
0.23
8.091
Denety
Piel 2316
Poi
8.15
26
20
0he00th
1|000 9600ll
(a) Initialization
(b) clipped-SGDA
(c) SGDA
(d) -GDDedd-SDD
Figure 3: (a) Gradient noise histograms for StyleGAN2 at random initialization. (b) Gradient noise histograms for StyleGAN2 trained with clipped-SGDA, (c) Random samples generated from several models trained with SGDA with different learning rates (FID > 300), Each row corresponds to a different trained model, and all of our attempts train StyleGAN2 with SGDA produced similar results. (d) Random samples generated from the best Hipped-SGDA trained model (FID 72.68).
Generator
5.714
In 0.09
Aur 6.85
Dreay
Deratt
Diseriminator
[gtt (1
[yte- D5ax1)
532
37.55
Pall3
Ryt
2242
10
20
30
10
20
34
<4
Generator
due
1943
DeURy
1907
Awel
793.
85
1100-962000
[dt- Varl
1 90200
Discriminator
3.24
0.4
2012 Dee
5472
Aui 7942
022
6.4
25
(pp0r 9600
1900
1pten Pg
20000 steps
40000 steps
80000 steps
100000 steps
Figure 4: Evolution of gradient noise histograms for a WGAN-GP model. The top two rows are trained with SGDA, and the bottom two rows are trained with clipped- SGDA.
around 320 and only able to generate noise. In contrast, while there is clear gap in quality when compared to what StyleGAN2 is capable of, a model trained with clipped-SGDA with appropriately set hyperparameters is able to produce images that distinctly resemble faces (see Fig. 3).
9

---

Acknowledgments and Disclosure of Funding
This work partially supported by grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier (X00000D303321P500000 and the agreement with the Moscow Institute of Physics and Technology dated November 1, 2021 No. 70-2021-001 The work by Dvurechensky was funded by the Deutsche Forschungsgemeinschaan (DFG, German Research Foundation) under Germany's 's Excellence Strategy The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).
References
J. Abernethy, K. A. Lai, and A. Wibisono. Last-iterate convergence rates for min-max optimization. arXiv preprint arXiv: 1906.020277 2019. (Cited on page 4)
H. H. Bauschke, W. M. Moursi, and Wang. Generalized monotone operators and their averaged resolvents, Mathematical Programming, 189(1):55-74, 2021. (Cited on page 3)
G. Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297):33-44 45, 1962. (Cited on page 17)
A. Beznosikov, V. Samokhin, and A. Gasnikov. Distributed saddle-poing problems: Lower bounds, optimal and robust algorithms. arXiv preprint arX0iv:200..1 13112, 2020. (Cited on pages 5, 6, and 16)
A. Beznosikov, E. Gorbunov, H. Berard, and N. Loizou. Stochastic gradient descent-ascent: Unitied theory and new efficient methods. arXiv preprint arXiv:2202.07262. 2022. (Cited on pages and 16)
A. Böhm. Solving wonconnve--onnccccaay nonconcave min-max problems exhibiting weak minty solutions. arXiv preprint ar arXiv:2201.12244 2022. (Cited on page 16)
J. Bose, G. Gidel, H. Berard, A. Cianflone, P. Vincent, S. Lacoste- Julien, and W. Hamilton. Ad- versarial example games. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 8921-8934. Curran Associates, Inc., 2020. (Cited on page 1)
A. Brock, J. Donahue, and K. Simonyan. Large scale GAN training for high fidelity natural image synthesis. In International Conference Learning Representations, 2019. URL https: // //opnreeview.... net.:/neeeeeeeeeeeeeeee wwret/ffrumm// itd (Cited on page 2)
A. Cutkosky and H. Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. Advances in Neural Information Processing Systems, 34, 2021. (Cited on pages 2, 3, and 16)
C. Daskalakis, S. Skoulakis, and M. Zampetakis. The complexity of constrained min-max optimiza- tion. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1466-1478, 2021. (Cited page 3)
D. Davis, D. Drusvyatskiy, L. Xiao, and J. Zhang. From low probability to high confidence in stochastic convex optimization. Journal of Machine Learning Research, 22-49):1-38, 2021. (Cited on page 3)
V. F. Dem' yon'y and A. B. Pevnyi. Numerical methods for finding saddle points. USSR Computa- tional Mathematics and Mathematical Physics, 12(5):11-52, 1972. (Cited page 2)
J. Diakonikolas, C. Daskalakis, and M. Jordan. Efficient methods for structured nonconvex- nonconcave min-max optimization. In International Conference on Artificial Intelligence and Statistics, pages 2746-2754. PMLR, 2021. (Cited on pages 3, 6, and 16)
K. Dzhaparidze and Van Zanten. On bernstein-type inequalities for martingales. Stochastic processes and their applications, 93(1):109-111 2001. (Cited page 17)
D. A. Freedman et al. On tail probabilities for martingales. the Annals of Probability. 310) 1975. (Cited on page 17)
S. Ghadimi and G. Lan. Optimal stochastic approximation algorithms for strongly convex stochastic composite optimization i: A generic algorithmic framework. SIAM Journal on Optimization, 22 (4):1469-1492, 2012. (Cited on page 3)
Ghadimi and Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal Optimization, 23(4):2341-255 1-2688 2013. (Cited page 3)
10

---

G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A variational inequality perspec- tive on generative adversarial networks. International Conference on Learning Representations. 2019a. (Cited on pages 2, and 66)
G. Gidel, R. A. Hemmat, M. Pezeshki, R. Le Priol, G. Huang. S. Lacoste-Julien, and I. Mitliagkas. Negatíve momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019b. (Cited on page 8)
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farleys S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27.
Curran Associates, Inc., 2014. (Cited on page 1)
I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning. MIT Press, 201 http://www. desplearningbook. org. (Cited on page 16)
I. Goodfellow, Y. Bengio, and A. Courville. Deep learning. MIT press, 2016b. (Cited page 8)
E. Gorbunov, M. Danilova, and A. Gasnikov. Stochastic optimization with heavy-tailed noise via accelcrated gradient clipping. Advances in Neural Information Processing Systems, 33:15042- 15053, 2020. (Cited on pages 2. 3, 16, and 17)
E. Gorbunov, M. Danilova, I. Shibaev, P. Dvurechensky, and A. Gasnikov. Near-optimal high probability complexity bounds for non-smooth stochastic optimization with heavy-tailed noise. arXiv preprint arXiv: (00000000333 (0,00588, 2021. (Cited on pages 2, 3, and 16)
E. Gorbunov, H. Berard, G. Gidel, and N. Loizou. Stochastic extragradient: General analysis and improved rates. In International Conference on Artificial Intelligence and Statistics, pages 7865-7901. PMLR, 2022a. (Cited on pages 6, 7, and 16)
E. Gorbunov, N. Loizou, and G. Gidel. Extragradient method: O (1/k) last-iterate convergence for monotone variational inequalities and connections with cocoercivity. In International Conference on Artificial Intelligence and Statistics, pages 366-402. PMLR, 2022b. (Cited on pages 4 and 16)
I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and Courville. Improved training of wasserstein gans. Advances in neural information processing systems, 30, 2017. (Cited on pages 2,
7, 8, and 66)
T. Harker and J.-S. Pang. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Mathematical programming, 48(1): 161-220, 1990. (Cited on page 1)
E. Hazan, K. Levy, and S. Shalev-Shwartz. Beyond convexity: Stochastic quasi-convex optimization. In Advances in Neural Information Processing Systems, pages 1594-1602, 2015. (Cited on page 16)
M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter. Gans trained by two time-scale update rule converge to local nash equilibrium. Advances in neural information processing systems, 30, 2017. (Cited on page 8)
Y.-G. Hsieh, F. lutzeler, J. Malick, and P. Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. (Cited on page 2)
Y.-G. Hsieh, F. lutzeler, J. Malick, and P. Mertikopoulos. Explore aggressively, update conservatively: Stochastic extragradient methods with variable stepsize scaling. Advances in Neural Information Processing Systems, 33, 2020. (Cited on pages 2, 3, 4, 6, and 16)
Jelassi, A. Mensch, G. Gidel, and Y. Li. Adam is no better than normalized SGD: Dissecting how adaptivity improves GAN performance, 2022. URL
id-D9SuLzhgK3. (Cited on page 2)
K. Jordanova and M. P. Petkova. Measuring heavy-tailedness of distributions. In AIP Conference Proceedings, volume 1910, page 060002. AIP Publishing LLC, 2017. (Cited on page 8)
A. Juditsky, A. Nemirovski, and C. Tauvel. Solving variational inequalities with stochastic mirror-prec algorithm. Stochastic Systems, 1(1):17-58, la. (Cited on pages 1, 3, 4, and 5)
A. Juditsky, A. Nemirovski, et al. First order methods for nonsmooth convex large-scale optimization, general purpose methods. Optimization for Machine Learning, pages 121 121-148, 201 (Cited on page 3)
11

---

T. Karras, S. Laine, and T. Aila. A style-based generator architecture for generative adversarial networks, In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4401 -4000, 2019. (Cited on page 7)
T. Karras, S. Laine, M. Aittala, J. Hellsten, J. Lehtinen, and T. Aila. Analyzing and improving the image quality of stylegan. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 81 10188119 19, 2020. (Cited on page
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXiv preprint a:ii: 2014. (Cited on page 2)
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976. (Cited on page 5)
A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. 2009, (Cited on page 7)
S. Lee and D. Kim. Fast extra gradient methods for smooth structured minimax problems. Advances in Neural Information Processing Systems, 34, 2021. (Cited on pages 6 and 16)
N. Loizou, H. Berard, A. Jolicoeur-Martineau,, P. Vincent, S. Lacoste-Julien, and I. Mitliagkas. Stochastic hamiltonian gradient methods for smooth games. In International Conference on Machine Learning, pages 6370-6381. PMLR, 2020. (Cited on page 4)
N. Loizou, H. Berard, G. Gidel, I. Mitliagka,, and Lacoste-Julien. Stochastic gradient descent- ascent and consensus optimization for smooth games: Convergence analysis under expected co-coercivity. Advances in Neural Information Processing Systems, 34, 2021. (Cited on pages 2, 4, 7, and 16)
V. V. Mai and M. Johansson. Stability and convergence of stochastic gradient clipping: Beyond lipschitz continuity and smoothness. arXiv preprini (XXv:2102.0642:) 2021. (Cited on page 16)
Mertikopoulos and Z. Zhou. Learning in games with continuous action sets and unknown payoff functions. Mathematical Programming. 17351):46--507, 2019. (Cited on pages 4 and 16)
K. Mishchenko, D. Kovalev, E. Shulgin, P. Richtarik, and Y. Malitsky. Revisiting stochastic extra- gradient. In S. Chiappa and R. Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics,, volume 108 of Proceedings of Machine Learn- ing Research, pages 4573-4582. PMLR, 26-28 Aug 2020. (Cited on pages 2 and 16)
T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida. Spectral normalization for generative adversarial networks. In ICLR, 2018. (Cited on page 2)
A. V. Nazin, A. Nemirovsky, A. B. Tsybakov, and A. Juditsky. Algorithms of robust stochastic optimization based on mirror descent method. Automation and Remote Control, 8009):6077-1627, 2019. (Cited on pages 2, 3, and 16)
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal optimization, 1944) 2009. (Cited pages and 3)
Y. Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Praiicaalloorgr Programming. 109(2):319-344, 2007. (Cited on page
R. Pascanu, T. Mikolov, and Bengio. On the difficulty of training recurrent neural networks. In International conference machine learning, pages 1310-1318, 2013. (Cited pages 2 and 16)
H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951. (Cited on page 2)
E. K. Ryu and W. Yin. Large-scale convex optimization via monotone operators, 2021. (Cited on page 1)
A. Sauer, Schwarz, and A. Geiger. Stylegan-xl: Scaling stylegan to large diverse datasets. volume Abs/2201.00273, 2022. URL https://arxix: org/ 2201 00273. (Cited on page 2)
C. Song, Z. Zhou, Y. Zhou, Y. Jiang and Y. Ma. Optimistic dual extrapolation for coherent non- monotone variational inequalities. Advances in Neural Information Processing Systems, 33: 14303-14314, 2020. (Cited pages 4 and 16)
12

---

N.-T. Tran, V.-H. Tran, B.-N. Nguyen, L. Yang, and N.-M. M. Cheung, Self-supervised gan: Analysis and improvement with multi-class minimax game. Advances Neural Information Processing Systems, 32, 2019. (Cited on page 2)
A. S. Vezhnevets, S. Osindero, T. Schaul, N. Heess, M. Jaderberg, D. Silver, and K. Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In International Conference on Machine Learning, pages 3540-3549. PMLR, 2017. (Cited page 1)
G. Wayne and L. Abbott. Hicrarchical control using networks trained with higher-level forward models. Neural computation, 26(10):2163-2193, 2014. (Cited on page I)
Zhang, T. He, S. Sra, and A. Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020a. URL https: /opprr///epeereeeeeee net/ f formmooummmm B.g.:iiddddBindli..
(Cited on page 16)
J. Zhang. S. P. Karimireddy, A. Veit, S. Kim, S. Reddi, S. Kumar, and S. Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33, 2020b. (Cited on pages 2 and 16)
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We explicitly formulate all assumptions in $ 1.1.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work is mainly theoretical.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes] We explicitly formulate all assumptions in 1.1.
(b) Did you include complete proof's of all theoretical results? [Yes] Proofs are included in the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [No] Training GANs is computationally expensive and we did not aim at achieving SOTA FID.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
13

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "qu0Z5I_xHTg", "reviewer": "Reviewer_NZw2", "summary": "The paper proves the first high-probability complexity results with logarithmic dependence on the confidence level for stochastic methods for solving monotone and structured non-monotone variational inequality problems (VIP) with heavy-tailed noise and unbounded domains.", "questions": "1. The paper focuses on monotone variational inequalities, is it possible to get similar results for non-monotone variational inequalities?\n2. It would be better to see comparison with SEG in experiments.", "limitations": "See above.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is sound, well-organized and well-written.\n\nWeaknesses:\nContribution is not significant enough. The results in the paper still need many assumptions. The paper only focuses on monotone variational inequalities.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RoKevEpfSz3", "reviewer": "Reviewer_nza4", "summary": "This paper studies variational inequality problem (VIP) with heavy-tailed noise and unbounded domain. It proposes a stochastic extragradient (SEG) method and a stochastic gradient descent-ascent (SGDA) method with gradient clipping techinique to address the problem. To handle the heavy-tailed noise, the paper considers clipping value for stochastic gradients, which controls the impact from heavy-tailedness but also introduces bias. The bias derived is addressed by different step-sizes and batch-sizes. To handle the unbounded domain, the paper only requires an upper bound of the distance between the initialization and the optimal solution. The convergence analysis on both stochastic methods and their proofs are discussed respectively in monotonic, star-monotonic and quasi-strong monotonic cases according to the respective property of the operator in the VIP. ", "questions": "In the extra experiments of the paper, we can find the FID curves on training StyleGAN2 with the original SGDA method and the clipping-value SGDA method. Can you provide the similar results on training WGAN-GP with the original SEG method and the clipping-value SEG method?", "limitations": "In its experiments, the paper does not compare the results of its stochastic methods with those of Adam.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality: Although stochastic extragradient method, stochastic gradient descent-ascent method and gradient clipping techinique are well-studied in the literature, this paper successfully combines them and applies to the VIP with heavy-tailed noise, inidcating authors' original effort.\n\nQuality: This paper gives the convergence results for monotonic, star-monotonic and quasi-strong monotonic operators in the VIP, which is comprehensive and readable for practitioners.\n\nClarity: The structure of this paper is well designed. The table of results in the introduction is straightforward.\n\nSignificance: This paper addresses VIP with heavy-tailed noise, which is common in industries and business.\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KYH2U1l4rI8", "reviewer": "Reviewer_q39a", "summary": "This paper studies the stochastic Variational Inequality Problem (VIP) with a potentially unbounded domain and the gradient might not satisfy the light tail assumption. The authors consider Stochastic ExtraGradient (SEG) and Stochastic Gradient Descent Ascent (SGDA) methods using clipped mini-batch stochastic gradients. Under various assumptions such as they proved that both methods converge with a high probability. \n\n\n", "questions": "1. Why SNC, SM, QSM and SC are interesting properties? Can the authors provide some real problems (for example some GAN models) that are proven to satisfy these conditions? In literature, these properties are mostly studied for theoretical purposes with only some artificially constructed examples.  \n\n2. Can the authors provide some justification for using  GapR(x) as the convergence criterion? For monotone F, we have GapR(x)<= \\|F(x)\\| R but not the other direction. Why a small GapR(x) indicates a good solution from a perspective of stationarity / variational analysis? \n\n3. The studied methods require mini-batches of big enough sizes. Moreover, these specific sizes depend on some unknown parameters. This is a limitation compared to other methods like Juditsky et al. [2011a] where the mini-batch is just optional and even one sample per iteration still works. Can the authors reduce the mini-batch size to one? If not, what is the technical challenge?\n\n4. How to estimate and select R, which affects many parameters in the theorems and the algorithms including the batch sizes. ", "limitations": "I have listed the limitations in the questions section above. In addition, the authors do not include some state-of-the-art methods for training GAN in their numerical comparison such as the ones using Adam. What if the state-of-the-art method has even better performances?", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: This is the first paper that provides high-probability convergence guarantee for stochastic gradient methods for solving some VIPs without assuming  sub-Gaussian noise and unbounded domains.\n\nWeakness: The authors do not compare their methods with some state-of-the-art methods for training GAN. Also, I have some concerns about using these methods in practice. Please see my questions below.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept