GDA-AM: ON THE EFFECTIVENESS OF SOLVING MIN-IMAX OPTIMIZATION VIA ANDERSON MIXING
Authors: Huan He
Shifan Zhao
Yuanzhe Xi
Joyce Ho
Yousef Saad
Venue: ICLR 2022 Poster (2022)

Abstract: Many modern machine learning algorithms such as generative adversarial networks (GANs) and adversarial training can be formulated as minimax optimization.Gradient descent ascent (GDA) is the most commonly used algorithm due to its simplicity.  However, GDA can converge to non-optimal minimax points.  We propose a new minimax optimization framework,GDA-AM, that views the GDA dynamics as a fixed-point iteration and solves it using Anderson Mixing to converge to the local minimax. It addresses the diverging issue of simultaneous GDA and accelerates the convergence of alternating GDA. We show theoretically that the algorithm can achieve global convergence for bilinear problems under mildconditions. We also empirically show that GDA-AM solves a variety of minimax problems and improves GAN training on several datasets

Published as a conference paper at ICLR 2022
SOLVE MINIMAX OPTIMIZATION BY ANDERSON AC- CELERATION
Huan He, Shifan Zhao, Yuanzhe Xi, Joyce C Ho Department of Computer Science Emory University Atlanta, GA 30329, USA
Yousef Saad f
Department of Computer Science and Engineering University of Minnesota
Minneapolis, MN 55455, USA
ABSTRACT
Many modern machine learning algorithms such as generative adversarial networks (GANs) and adversarial training can be formulated as minimax optimization. Gradi- ent descent ascent (GDA) the most commonly used algorithm due to its simplicity. However, GDA can converge to non-optimal minimax points. We propose a new minimax optimization framework, GDA-AU AM, that views the GDA dynamics as a fixed-point iteration and solves it using Anderson Mixing to converge to the local minimax. It addresses the diverging issue of simultancous GDA and accelerates the convergence of alternating GDA. We show theoretically that the algorithm can achieve global convergence for bilinear problems under mild conditions. We also empirically show that GDA-AM AM solves variety of minimax problems and improves adversarial training on several datasets, Codes are available on Github
INTRODUCTION
Minimax optimization has received surge of interest due to its wide range of applications in modern machine learning, such as generative adversarial networks (GAN), adversarial training and multi- agent reinforcement learning (Goodfellow et al. 2014 Madry et al. 2018 Li et al. 2019). Formally, given a bivariate function f(x, y), the objective is to find a stable solution where the players cannot improve their objective, i.e., to find the Nash equilibrium of the underlying game (von Neumann & Morgenstern] 1944):
arg min arg max fax y)- xEX
yEy
commonplace to use simple algorithms such as gradient descent ascent (GDA) to solve such problems, where both players take a gradient update simultaneously alternatively. Despite its simplicity, GDA is known to suffer from a generic issue for minimax optimization: it may cycle around stable point, exhibit divergent behavior, converge very slowly since it requires very small learning rates (Gidel et al. 2019at Mertikopoulos et al. 2019). Given the widespread usage of gradient- bassdd methods for solving machine learning problems, first-order optimization algorithms to solve minimax problems have gained considerable popularity in the last few years. Algorithms such as optimistic Gradient Descent Ascent (OG) (Daskalakis et al. 2018 Mertikopoulos et al.! 2019) and extra-gradient (EG) (Gidel et al.) 2019a) can alleviate the issue of GDA for some problems. Yet, it has been shown that these methods can still diverge or cycle around a stable point (Adolphs al.) Mazumdar et al., 2019: Parker-Holder et al./ (220). For example, these algorithms even fail to find local minimax (the set of local minimax is a superset of local Nash (Jin et al. 2020 Wang et al. 2020)) as shown in Figure [ This leads to the following question: Can we design better algorithms for minimax problems? We answer this in the affirmative, by introducing GDA-AM. We cast the GDA dynamics as a fixed-point -ointt iteration problem and compute the iterates effectively using an advanced nonlinear extrapolation method. We show that indeed our algorithm has theoretical and empirical guarantees across broad range of minimax problems, including GANs.
"hhe37, szhao89, yxi26, jho31 13316 @emory.euu saad @ umn.edu
https: http:///gggghhbb.../.eehaaaabaaa

---

Published as a conference paper at ICLR 2022
SimGDA
AltGDA
EG
OMD
-10
SimGDA-AM
-15
Optima
-1
-9
-00
-15
-10
-5
10
(a) Cycling Behavoir
(b) Diverging Bchavoir
(c) Converging to non-optima
Figure 1: Left:f(z,,) = (4 30.0000 - 0.1y")e " (00((=++2)) Middle: -3x² +4z.
Right: [(r v) 2x + y² + 4ry + t/²² t.y We can observe that baseline methods fail to converge to local minimax, whereas GDA-AM AM with table size = 3 always exhibits desirable behaviors.
Our contributions: In this paper, we propose different approach solve minimax optimization. Our starting point is to cast the GDA dynamics as a fixed-point iteration. We then highlight that the fixed-point iteration can be solved effectively by using advanced non-linear extrapolation methods such as Anderson Mixing [Anderson] 1965). which we name as GDA AM. redAlthough first mentioned in Azizian et al. 2020), to our best knowledge, this is still the first work investigate and improve the GDA dynamics by tapping into advanced fixed-point algorithms.
We demonstrate that GDA dynamics can benefit from Anderson Mixing. In particular, we study bilinear games and give a systematic analysis of GDA-AM for both simultaneous and alternating versions GDA. We theoretically show that GDA-AM can achieve global convergence guarantees under mild conditions.
complement our theoretical results with numerical sinulations across a variety of minimax problems. We show that for some convex-concave and non-comvex-concave functions, GDA-AM can converge to the optimal point with little hyper-parament parameter tuning whereas existing first-order methods prone divergence and cycling behaviors.
We also provide empirical results for GAN training across two different datasets, CIFARIO and CelebA. Given the limited computational overhead of our method, the results suggest that an extrapo- lation add-on to GDA can lead to significant performance gains. Moreover, the convergence behavior across variety of problems and the case-of-use demonstrate the potential of GDA-AM to become the minimax optimization workhorse.
PRELIMINARIES AND BACKGROUND
2.1 MINIMAX OPTIMIZATION
Definition 1. Point (x",y" ,y*) is a local Nash equilibrium of f if there exists > such that for any y) satisfying ||x - x"1 and y < 8 we have: (x",
1x,"," .y) (x",y") S (x, y))
To find the Nash equilibria, common algorithms including GDA, EG and OG, can be formulated as follows. For the two variants of GDA, simultaneous GDA (SimGDA) and alternating GDA (AlGGDA), the updates have the following forms:
Simultaneous: X++1 = (x),)))))))) Ye+1 y, V
Alternating:
X++1 = Xx 1/ (x,,)))))
=411= y, + + V
The EG update has the following form:
x = X, - -x)x((x)
Y = V
(3)
X X, -
y411 = y: + 7
2

---

Published as a conference paper at ICLR 2022
The OG update has the following form:
X1+1 = x -x htwp://www......................
(
(4)
2.2 FIXED-POINT ITERATION AND ANDERSON MIXING (AM)
Definition 2. w is a fixed point of the mapping g if = (w").
Consider the simple fixed-point iteration W++1 g(w,) which produces a sequence of iterates
{Wo, "1,'"" wNr). In most cases, this converges to the fixed-point, w" = g(w".. ). Take gradient descent as example, it can be viewed as iteratively applying the operation: wx+11 = (wx) A Wy - V (wx),, where the limit the fixed-point w = y (w") (i..VV. (w, = 0) SimGDA updates can be defined as the repeated application of a nonlinear operator:
ar
W++1 G(sim) (w)) W. V/V (we) with w
x
V(w)
Vx/(x,y) - -vyf(x,y)
(we). An issue with fixed-point iteration that it does not always converge, and even in the cases where it does converge, might do so very slowly. GDA is one example that it could result in the possibility of the operator converging to a limit cycle instead of a single point for the GDA dynamic. way of dealing with these problems is to use acceleration methods, which can potentially speed up the convergence process and in some cases even decrease the likelihood for divergence.
Similarly, we can write AlIGDA updates as W1+1 G7 (alt)
There are many different acceleration methods, but will put our focus algorithm which we refer to as Anderson Mixing (or Anderson Acceleration). In short, Anderson Mixing (AM) shares the same idea as Nesterov's acceleration. Given fxed-point iteration Wy = g (w,-1), Anderson Mixing argues that a good approximation to the final solution w² can be obtained as a linear combination of the previous p iterates w++1 Σi= 9ig (Wt-pe+i). Since obtaining the proper coefficients B; is a nonlinear procedure, Anderson Mixing is also known as a nonlinear extrapolation method. The general form of Anderson Mixing is shown in Algorithm [ For efficiency, prefer 'restarted' version with small table size p that cleans up the table I' every iterations because it avoids solving linear system of increasing size.
Algorithm 1: Anderson Mixing Prototype (truncated version)
Input: Initial point wo, Anderson restart dimension p, fixed-point mapping R" + R". Output: W:+1 for 7 = 0, I.... do
Set Pt min(t,.p)
Set F; = [fe-pe.- fel. where f. = g(w;) wi for each E [t - Pt t]. Determine weights 8 = :B.......33. )p.)"' that solves ming ||
Σn 1= B, = 1.
Set W = Pc
B.g (w, (w,-p.+)).
end
2.3 AM AND GENERALIZED MINIMAL RESIDUAL (GMRES)
Developed by Saad & Schultz (186).. Generalized Minimal Residual method (GMRES) is a Krylov subspace method for solving linear system equations. The method approximates the solution by the vector in a Krylov subspace with minimal residual, which is described below.
Definition 3. Assume we have the linear system of equations x = b with E _uxn b. E R and an initial guess Xo. Then we denote the initial residual by ro = b Xy and define the tth Krylov subspace as K,, span spantro, Tu.... -. ro}.
The tth iterate of GMRES minimizes the norm of the residual r, b -x, in ICs, that is, x2 solves
min t-CC
|
Xx 11
3

---

Published as a conference paper at ICLR 2022
The following formulation is equivalent to GMRES minimization problem and more convenient for implementation. computes X such that
X = arg min | (Xo + x = arg min ||ro Xx E,
R,
Using larger Krylov dimension will improve the convergence of the method, but will require more memory. For this reason, a smaller Krylov subspace dimension t and "restarted" versions of the method are used in practice Saad (0003).
The convergence of GMRES can be studied through the magnitude of the residual polynomial.
Theorem 2.1 (Lemma 6.31 of (aad (2003)). Let & be the approximate solution obtained at the 1-th iteration GMRES being applied to solve b, and denote the residual rt b Xt. Then, re is of the form
r1 = f(()rs
(5)
where
|xell = 1lf00zol22 min llf:()rol2..
(6)
SiEP
where Pp is the family of polynomials with degree such that fp(0) = 1, 1, E Pp. which are usually called residual polynomials.
Although GMRES is applied system of linear equations not fixed-point problem, there is strong connection between Anderson Mixing and GMRES. In AM we are looking for fixed-point such that Gx
and by rearranging this equation we get
(G - Ijx 0 (I G)x
Theorem 2.2 shows that if GMRES is applied to the system G)x and AM applied to g(x) = Gx + b with the same initial guess and I G is non-singular, then these are equivalent in the sense that the iterates of each algorithm can be obtained directly from the iterates the other algorithm.
Consider the fixed point iteration x = g(x) where g(x) Gx b for G guxa and R". If G non-singular, Algorithm 7 produces exactly the same iterates GMRES being applied solve (I G)x = b when both algorithms start with the same initial guess.
Theorem 2.2 (Equivalence between AM with restart and GMRES Walker & Ni 201
Theorem 2.2 can also generalized to the restart version of AM an GMRES as well.
3 GDA-AM GDA WITH ANDERSON MIXING
We propose a novel minimax optimizer, called GDA-AM, that is inspired by recent advances in parameter (or weight) averaging (Wu et al., 2020;; Yazici al. 2019). We argue that nonlinear adaptive average (combination) is more appropriate choice for minimax optimization.
3.1 GDA WITH NAIVE ANDERSON MIXING
We propose exploit the dynamic information present in the GDA iterates to "smartly" combine the past iterates. This contrast to the classical averaging methods (moving averaging and exponential moving averaging) (Yang al. 2019) that "blindly" combine past iterates. A naïve adoption of Anderson Mixing using the past GDA iterates for both simGDA and altGDA has the following form:
Anderson mixing:
X = Σ 3,x, 8.xt-pto.
Σ Biyi-pti 2=1
200
Since Zhang et al. (202) Gidel et al. 2019bb show the AltGDA is superior SimGDA in many aspects, we briefly summarized both Simultancous and Alternating GDA-AM AM in Algorithms and with the truncated Anderson Mixing Algorithm Tusing table size p.
4

---

Published as a conference paper at ICLR 2022
Algorithm 2: Simultaneous GDA-AM
Algorithm 3: Alternating GDA-AM
Input: No: Yo. stepsize 17, Anderson table
Input: Xo: Yo. stepsize 17, Anderson table
size p
size
Output: Xt.
Output: Xt.
Set Wo = Yol, length(ro)
Set Wo [xo Nol, length(ro)
for / = 0, I.... do
for / = 0, 1.... do
Xe. Yt w:[0 SI 11, welsæ :
end]
Xt, Yr. w.
11, We end
Xt+1 = Xt - 11 xx](xx,))
X = Xx -// [xx,
Y4+1 =y 17 y Xx)
Yi+1 = nV V
X(+1
X++1
W++1 ye+1
Wr+1 Ye+1
Use Anderson Mixing with table size p
Use Anderson Mixing with table size p
to extrapolate W4+1
to extrapolate W++1
end
end
Xr. yr W2+1 8x 1), We+1 (sxr end] return Xt
Xr. Yt w++1 8 1J. Wz+1 1 end] return Xt
is important to note that the Anderson Mixing form shown in Algorithm is for illustrative purpose and not computationally efficient. For example, only column of needs be updated each iteration. In addition, the solution of the least-square problem in Algorithm I can also be solved by quick QR update scheme which costs (2n + 1)p² (Walker & Ni 201 Thus, from Algorithms 2 and we can see that the major cost of CDA-AM arises from solving the additional linear least squares problem compared regular GDA at each iteration. Additional implementation details are provided in the Appendix.
4 CONVERGENCE RESULTS FOR GDA-AM
In this section, we show that both simultaneous and alternating version GDA-AM converge to the equilibrium for bilinear problems. First, do not require the learning rate be sufficiently small. Second, we explicitly provide a linear convergence rate that is faster than EG and OG. More importantly, we derive nonasymptotic rates from the spectrum analysis perspective because existing theoretical results can not help us derive convergent rate (see
4.1 BILINEAR GAMES
Bilinear games are often regarded as an important simple example for thcoretically analyzing and understanding algorithms and techniques for solving general minimax problems (Gidel et al. 2019a Mertikopoulos et al.) 2019: Schaeter Anandkumar 2019). In this section, we analyze the convergence property of simultaneous GDA-AM and alternating GDA-AM schemes the following zero-sum bilinear games:
min max fx. = x" Ay + x + is full rank. XER YER
The Nash equilibrium to the above problem is given by (- ---
We also investigate bilinear-quadratic games from a spectrum analysis perspective. In addition, we show that analysis based the numerical range (Bollapragada et al.) (018)) can be also extended to such games, although it can not help derive a convergent bound for equation Detailed discussion can be found in Appendix C.1 and C.4.1
4.2 SIMULTANROUS GDA-AM
Suppose and Yo are the initial guesses for x" and y", respectively. Then each iteration of simultancous GDA can be written in the following matrix form:
X Yr+1
A
X Yt
nAT
(8)
(Stm)
w
(Sam)
b(5mm
5

---

Published as a conference paper at ICLR 2022
It has been shown that the iteration in equation 8 often cycles and fails converge for the bilinear problem due to the poor spectrun/mumerical range of the fixed point operator G (Sim) (Gidel et al. 2019a Azizian et al., 2020, Mokhtari et al. 2020a). Next we show that the convergence can be improved with Algorithm
Theorem 4.1. [Global convergence for simultaneous GDA-AK AM on bilinear problem] Denote the distance between the stationary point w" and current iterate Wkk+1)p of Algorithm with table size p (o++1)p l|w"
W(k+1)pll Then have the following bound for Nt.
N( S p(
(9)
where p(A) T,(1+ )ー K( k(") 1.
j. Here, Tp is the Chebyshev polynomial of first kind of degree p and
T,(1+ < 1 since
is worthy emphasizing that the convergence rate of Algorithm 2 is independent learning rate while the convergence results of other methods like EG and OG depend on the learning rate. Remark 4.1.1. Both EG and OG have the following form of convergence rate (Mokhtari et al. 2020a for bilinear problem
N S (1
K(T)) N
where is a positive constant independent of the problem parameters.
mapttary
SinGGA
Sendio AM
1L5
0.0
8.25
0.5
Real
Oo GeadokAMM p-10 Gmo004AA
Fa3
-1.5
2.02
26
Osaddtiie Neadlet
(a) Eigenvalues of iteration matrix SimGDA and GDA-AM
(b) Different condition number
(c) Different table size, condition number 100
Figure 2: Figure 2a of matrix I
The blue line is the spectrum of matrix (Sim) while the red line spectrum G (Smm) Our method transforms the divergent problem convergent problem due to the transformed spectrum. Figure 2b; Convergence rate comparison between SimGDA-AM and EG for different condition numbers of and fixed table size p = 10, 20, 50. Figure 2c Convergence rate comparison between SimGDA-AM and EG for increasing table size on matrix with condition number 100.
4.3 ALTERNATING AM
The underlying fixed point iteration in Algorithm
can be written in the following matrix form:
X(+1
A
b
Ye+1
A
y+
According to the equivalence between truncated Anderson acceleration and GMRES with restart, we can analyze the convergence Algorithm through the convergence analysis of applying GMRES solve linear systems associated with I G (Alt)
A
G
TAT
A

---

Published as a conference paper at ICLR 2022
Theorem 4.2. [Global convergence for alternating GDA-AK bi- linear problem] Denote the distance between the stationary point w" and current iterate W(k-1jp of Algorithm 3 with table size p Nik+1>p = I|w* W(k+1)pll Assume is normalized such that its largest singular value is equal to 1. Then when the learning rate nj is less than 2. we have the following bound for No
-30
Ni /
2n
Figure 3: An illustration of the where and r are the center and radius of a disk r(c,r) which includesSpectrum of G (red) and the clos- ing circle (blue) in Theorem 4.2
2 n
all the eigenvalues of G. Especially,
1.
log 2+ log
Theorem 4.2 4.2 that when p
alternating EDA-AM will converge globally.
4.4 DISCUSSION OF OBTAINED RATES
We would like first explain on why taking Chebyshev polynomial of degree p at the point 1 - We evaluate the Chebyshev polynomial at this specific point because the reciprocal of this value gives the minimal value of infinite norm of the all polynomials of degree defined on the interval = a O- 17² o () based on Theorem 6.25 (page 209) (Saad 2003). In other words, taking the function value this point leads to the tight bound.
When comparing between existing bounds, we would like to point our our derived bounds are hard to compare directly. The numerical experiments in figure 2b numerically verify that our bound is smaller than EG. We wanted to numerically compare our rate with EG with positive momentum. However the bound of EG with positive momentum is asymptotic. Moreover, does not specify the constants so we can not numerically compare them. We do provide empirical comparison between GDA-AM and EG with positive momentum for bilinear problems in Appendix D.I It shows GDA-AM outperforms EG with positive momentum. Regarding alternating GDA-AM, we would like to note that the bound in Theorem 4.2 depends on the eigenvalue distribution of the matrix G. Condition number is not directly related to the distribution of eigenvalues of nonsymmetric matrix G. Thus, the condition number not a precise metric to characterize the convergence. If these eigenvalues are clustered, then our bound can be small. On the other hand, if these eigenvalues are evenly distributed in the complex plane, then the bound can very close to 1.
More importantly, would like to stress several technical contributions.
1 : Our obtained Theorem 4. and 4.2 provide nonasymptotic guarantees, while most other work are asymptotic. For example, EG with positive momentum achieve asymptotic rate of 1 O(1/VR) under strong assumptions (Azizian et al. 2020).
2: Our contribution not just about fix the convergence issue of GDA by applying Anderson Mixing: another contribution is that we arrive at a convergent and tight bound on the original work and not just adopting existing analyses. We developed Theorem 4. and 4.2 from new perspective because applying existing theoretical results fail to give us neither convergent nor tight bounds.
3 Theorem 4.1 and 4.2 only requires mild conditions and reflects how the table size p controls the convergence rate. Theorem 4.1 is independent of the learning rate 7. However, the convergence results of other methods like EG and OG depend on the learning rate, which may yield less than desirable results for ill-specified learning rates.
5 EXPERIMENTS
In this section, we conduct experiments to see whether GDA-AM improves GDA for minimax optimization from simple to practical problems. We first investigate performance of GDA-AM on bilinear games. In addition, we evaluate the efficacy of our approach on GANs.
7

---

Published as a conference paper at ICLR 2022
5.1 BILINEAR PROBLEMS
In this section, we answer following questions: QI: How is GDA-AM perform in terms of iteration number and running time? Q2: How the scalability of GDA-AM Q3: How is the performance of GDA-AM using different table size p? Q4: Does GDA converge for large step size 17?
We compare the performance with SimGDA, AlIGDA, EG, and OG, and EG with Negative Momen- tum Azizian et al. (2020) on bilinear minimax games shown in equation 7 without any constraint.
b. c. and initial points are generated using normally distributed random number. We set the maximum iteration number as 1 x 10" stopping criteria 1 x 10 10-5 and depict convergence by use of the norm of distance to optima, which is defined as || /w* w.ll- Similar to Azizian al. (2020); Wei al.
(2021a), the step size is set as after rescaling to have 2-norm 1. We present results of different settings Figures
and
We first generate different problem size (n 100, 1000, 5000) and present results of convergence in terms of iteration number in Figure can be observed that GDA-AK AM converges in much fewer iterations for different problem sizes. Note that EG, EG-NM, and OG converge in the end but requires many iterations, thus we plot only portion for illustrative purposes. ( the convergence for all methods in terms of time. It can be observed that the running time of GDA-AM is faster than EG. Although slower than OG, we can observe GDA-AM converges in much less time for all problems. Figure 4 and Figure 5 answer Q1 and Q2; although there is additional computation for GDA-AM does not hinder the benefits of adopting Anderson Mixing. Even for a large problem size, GDA-GDA-- AM still converges in much less time than the baselines.
Next, we run GDA-AD using different table size p and show the results in Figure 6a and Figure 6b Figure 6a indicates an increasing of table size results in faster convergence in terms of iteration number, which also verifies our claim in Theorem 4.1 However, we also observe an increased running time when using a larger table size in Figure 6b Further, we can see that p = 50 converges comparable time and iterations to 100. Similar results are found in repeated experiments as well. As result, our answer to Q3 is that although larger p means less iterations, a medium p is sufficient and a small still outperforms the baselines. The optimal choice of p is related to the condition number and step size, which is another interesting topic in the Anderson Mixing community.
Next, we answer Q4 convergence under different step sizes. Although GDA usually converges with suitable step size, our theorem suggests it requires a larger table size when combined with extremely aggressive step size. Figure 6c shows the convergence under such circumstance. We can observe that although a very large step size goes the wrong way in the beginning. Anderson Mixing still make it back track except when 1. It answers the question and confirms our claim that GDA-AM AM can achieve global convergence for bilinear problems for a large step size >> 0.
107
Disance norm (lo scale)
Dicaree norm (1og (00-s)c))))
100
BeNODA ARGIA
10
SAYODA ABSDA
SeedON ABSDA
P- EO
+D+ EG
EG
SanO AM
10"
Sevort AM
ABSDA.AM
ABSDA-MM
Bension
10
Heration
teratio
(a) 100
(b) = 500
(c) = 1000
Figure 4: Comparison in terms of iteration: miny maxy f(x, = Ay - bT cyyy. y. We use
different problem size and fix p 10, for all experiments.
5.2 GAN EXPERIMENTS: IMAGE GENERATION
We apply our method to the CIFARIO dataset (Krizhevsky 2009) and use the ResNet architecture with
WGAN-GP (Gulrajani al. 2017) and SNGAN (Miyato et al. 2018) objective. We also compared
8

---

Published as a conference paper at ICLR 2022
10
Distance nor (be (o3a0
107
Distanin ramt (-g--000 (-gg-0oski
Dasaarce nomm www.mmmwmg-aaaaaaooeeee (o--acaae)
10"
10"
10x
SKYODA
SaYODA
ARSOA
DG
J EG
10"
+0-F4 AM
SAYDDAAAM AM00AAM
Sand
ABOOA 4M
ICDA-AY
10
10
10
Time (Seconde)
(Seconda)
(Seoonds)
(a) Time comparison for Figure 4a
(b) Time comparison for Figure 4b
(c) Time comparison for Figure 4c
Figure 5: Comparison between methods in terms of time.
10"
Disanne nor (ko ccore
104
Disturco narm (kig Big-scait
10
Disterca nom (kgeecade)
10"
ton
10"
03
10*
-0
10
00
3M p-10
SanAM F-13
2010
p-10
-0 ABAM 5000
10
Samskl
ABAM p-50
ARDDA AMCorO
XBM p-100
AMM p-110
ABC Add
30
40
60
x10
(Seconds)
x10
(a) Effects of p in terms of iteration
(b) Time compasion for Figure 6a
(c) Effect of step size y). p = 10
Figure 6: Effects of table size p and step size 7/, 500
the performance of GDA-AM using cropped CelebA (64x64) (Liu et al. 2015) on WGAN-GP. We compare with Adam and extra-gradient with Adam (EG) as it offers significant improvement over OG. Models are evaluated using the inception score (IS) (Salimans et al.) 2016) and FID (Heusel et al. 2017) computed on 50,000 samples. For fair comparison, we fixed the same hyperparamters of Adam for all methods after extensive search. Experiments were with 5 random seeds. We show results in Table [ Table repprts the best IS and FID (averaged over 5 runs) achieved on these datasets by each method. We see that GDA-AM yields improvements over the baselines in terms of generation quality.
Table 1:
Best inception scores and FID for Cifar10 and FID for CelebA (IS is less informative metric for celebA).
WGAN-GP(ResNee))
SNGAN(ResNet)
CIFARIO
CelebA
CIFARIO
Method
IS
FID
FID
IS
FID
Adam
7.76 1.11
22.45 +.65
8.43 +.05
8.21 :.05
20.81 1.16
EG
7.83 4.08
20.73
+.22
8.15 +.06
8.15 +.07
21.12 1.19
Ours (GDA-AM)
8.05 +-06
19.32 4.16
7.82 +.06
8.38 +.04
18.84 +.13
CONCLUSION
We prove the convergence property of GDA-AM and obtain a faster convergence rate than EG and OG on the bilinear problem. Empirically. we verify our claim for such a problem and show the efficacy of GDA-AN in a deep learning setting as well. We believe our work is different from previous approaches and takes important step towards understanding and improving minimax optimization by exploiting the GDA dynamic and reforming with numerical techniques.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work was funded in part by the NSF grant OAC 2003720, IIS 1838200 and NIH grant 3R01MM01332-033K0LMM00000
REFERENCES
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmmann. Local saddle point optimization: A curvature exploitation approach. Proceedings of Machine Learning Research. PMLR.
Donald G. Anderson. Iterative procedures for nonlinear integral equations. 1965.
Waiss Azizian, Damien Scieur, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. Accelerating smooth games by manipulating spectral shapes. The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pp. 1705-1715. PMLR, 2020,
Raghu Bollapragada, Damien Scieur, and Alexandre d' Aspremont. Nonlinear acceleration mo- mentum and primal-dual algorithms. arXiv preprint 0rXiv:1810.045:00 2018.
Ronald E. Bruck. On the weak convergence of ergodic iteration for the solution of variational inequalities for monotone operators in hilbert space. Journal of Mathematical Analysis and Applications, 1977.
Daniela Calvetti, Bryan Lewis, and Lothar Reichel. On the regularizing properties of the gmres method. Numerische Mathematik, 91(4))605-625, 2002.
Michel Crouzeix and César Palencia. The numerical range is a (1+2)-spectral set. SIAM Journal on Matrix Analysis and Applications, 38(2):649-655, 2017.
C. Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. ArXiv, abs/1711 11.0111,,, 2018.
Howard C Elman. Iterative methods for large, sparse, nonsymmetric systems of linear equations. PhD thesis, Yale University New Haven, Conn, 1982.
Haw-ren Fang and Yousef Saad. Two classes multisecant methods for nonlinear acceleration. Numerical Linear Algebra with Applications, 16(3):197-221, 2009.
Bernd Fischer and Roland Freund. Chebyshev polynomials not always optimal. Journal of Approximation Theory, 65(3):261-272, 1991.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Juliens A varia- tional inequality perspective generative adversarial networks. In 7th International Conference on Learning Representations, ICLR, 2019a
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In Proceedings of the Twenty-Secome International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research. PMLR, 2019b.
I. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde Farley, Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS, 2014.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples, 2015.
Anne Greenbaum. Iterative methods for solving linear systems. SIAM, 1997.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of wasserstein gans. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances Neural Information Processing Systems, 2017.
10

---

Published as a conference paper at ICLR 2022
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. In Advances in Neural Information Processing Systems, 2017.
Yu-Guan Hsieh, F. lutzeler, J. Malick, and P. Mertikopoulos. On the convergence of single-call stochastic extra-gradient methods. In NeurlPS, 2019.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-noncoocaae minimax optimization? In Proceedings of the 37th International Conference on Machine Learning. Proceedings of Machine Learning Research, pp. 1880-4880 PMLR, 2020.
A. Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Alexey Kurakin, lan J. Goodfellow, and Samy Bengio. Adversarial machine learning at scale. ArXiv, abs/16 0ess/6111.0122 1.01236, 2017.
Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang. Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes. In AISTATS, 2021.
S. Li, Yi Wu, Xinyue Cui, Honghua Dong, Fei Fang, and Stuart Russell. Robust multi- agent reinforcement learning via minimax deep deterministic policy gradient. In AAAI, 2019.
Tianyi Lin, Chi Jin, and Michael I. Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In ICML, pp. 6083-6093, 2020. URL [attp://prrceeednngg.tt
press/v119/ lin20a. html
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015.
Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent minimax problems. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, 2020.
for stochastic conconvex-ttrongly-comm
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR 2018., 2018.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks, 2019.
Eric V. Mazumdar, Michael Jordan, and S. Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. ArXiv, abs/ 0bs/1901.00838 2019.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra gradient mile. In 7th International Conference on Learning Representations, ICLR, 2019.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS' 17, 2017.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Y. Yoshida. Spectral normalization for generative adversarial networks. ArXiv, abs/ 802.05957, 2018.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pp. 1497-1507. PMLR, 2020a.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. unified analysis of extra- sarra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research. PMLR, 2020b.

---

Published as a conference paper at ICLR 2022
A. Nemirovski. Prox-method with rate of convergence ((/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim., 2004.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D. Lee, and Meisam Razaviyayn. Solving Class of Non-Conver Min-Max Games Using Iterative First Order Methods. Curran Associates Inc., Red Hook, NY, USA, 2019.
Dmitrii M. Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in nonconvex-concave smooth min-max problems, 2021.
Jack Parker-Holder, Luke Metz, Cinjon Resnick, Hengyuan Hu, Adam Lerer, Alistair Letcher, Alexander Peysakhovich, Aldo Pacchiano, and Jakob Foerster. Ridge rider: Finding diverse solutions by following cigenvectors of the hessian. In Advances in Neural Information Processing Systems, 2020.
L. Popov. A modification of the arrow-hurwiez method for search of saddle points. Mathematical notes of the Academy of Sciences of the USSR, 1980.
Youcef Saad and Martin H. Schultz. Gmres: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal Scientific and Statistical Computing, 1986.
Yousef Saad. Iterative methods for sparse linear systems. SIAM, 2003.
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, Xi Chen, and Xi Chen. Improved techniques for training gans. In Advances in Neural Information Processing Systems, 2016.
Florian Schaefer and Anima Anandkumar. Competitive gradient descent. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, 2019.
Kiran K Thekumparampil, Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' A'u,ché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, 2019.
John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944.
Homer F Walker and Peng Ni. Anderson acceleration for fixed-point iterations. SIAM Journal on Numerical Analysis, 49(5): 2011a.
Homer F. Walker and Peng Ni. Anderson acceleration for fixed-point iterations. 201
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A tollow-the-ridge approach. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
Chen-Ye Yu Wei, Chung- Wei Lee, Mengxiao Zhang, and Haipeng Luo. Linear last-iterate convergence in constrained saddle-point optimization. In International Conference Learning Representations, 2021a. URL httLiitttpp://ppeeeeleee net.:
wtw.e///wwwweeeeeeeuueue..a forum? dd=dx11_11 1__v___________
Fuchao Wei, Chenglong Bao, and Yang Liu. Stochastic anderson mixing for nonconvex stochastic optimization. arXiv preprint arXiv:2110.01543. 202
Yue Wu, Pan Zhou, A. Wilson, F. Xing, and Zhiting Hu. Improving gan training with probability ratio clipping and sample reweighting. ArXiv, 0tss/2006.06900. 2020.
Zi Xu, Huiling Zhang, Yang Xu, and Guanghui Lan. A unified single-loop alternating gradient minimax problems. 2021.
projection algorithm for nonconvex-concave and
Minghan Yang. A. Milzarek, Z. Wen, and T. Zhang. A stochastic extra-step quasi-newton method for nonsmooth nonconvex optimization. arXiv: Optimization and Control, 2019.
12

---

Published as a conference paper at ICLR 2022
Yasin Yazici, Chuan-Sheng Foo, Stefan Winkler, Kim-Hui Yap, Georgios Piliouras, and Vijay Chandrasekhar. The unusual effectiveness of averaging in GAN training. 7th International Conference Learning Representations, ICLR. 2019, 2019.
Guodong Zhang and Yuanhao Wang- On the suboptimality of negative momentum for minimax optimization. In AISTATS, 2021.
Guodong Zhang, Yuanhao Wang, Laurent Lessard, and Roger B. Grosse. Don't fix what ain't broke: Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization. CoRR, 2021.
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael I. Jordan. Theoretically principled trade-off between robustness and accuracy. CoRR, 2019. URL
http://arxiv.orrg/ absp/////////aoooaaaa...../...a/ abs/1abl..0000 08573
1901..911..
Jiawei Zhang, Peijun Xiao, Ruoyu Sun, and Zhiquan Luo. single-loop smoothed gradient descent- ascent algorithm for nonconvex-coneave min-max problems. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, 2020.
13

---

Published as a conference paper at ICLR 2022
A
RELATED WORK
There a rich literature on different strategies to alleviate the issue of minimax optimization. A useful add-on technique, Momentum, has been shown to be effective for bilinear games and strongly-convex
strongly-coneave settings (Zang Wang, 2021| Gidel et al. 2019b 2019b|Azizian Azizian et al. 2020). Several second-order methods (Adolphs et al., Mescheder et al. 2017 Mazumdar et al. [0199] Parker-Holder ctt al., 2020) show that their stable fixed points are exactly either Nash equilibria or local minimax by incorporating second-order information. However, such methods are computationally expensive and thus unsuitable for large applications such as image generation. Focusing on variants of GDA, EG and OG are two widely studied algorithms improving the GDA dynamics. EG proposed to apply extra-gradient to overcome the cycling behaviour of GDA. OG, originally proposed in Popoy (1980) and rediscovered in Daskalakis al. (2018); Mertikopoulos et al./ (2019), is more efficient by storing and re-using the extrapolated gradient for the extrapolatio latiooo step. Without projection, OG is equivalent extrapolation from past. Mokhttar et al. (2020b) shows that both of these algorithms can be interpreted as approximations of the classical proximal point method and did a unified analysis for bilinear games. These approaches mentioned the GDA dynamics can be viewed as a exed-point iteration, but none of them further provides a solution to improve it. In this work, we fill this gap by proposing the application of the extrapolation method directly on the entire GDA dynamics. Unlike OG, EG and their variants (Hsieh et al. 2019; Lei et al. [021 Thekumparampil et al. 2019
Yang et al., 2019), which regard minimax problems as variational inequality problems (Bruck) 1977: Nemirovski 2004), work is from perspective and thus orthogonal to these previous approaches.
In addition, several recent works consider nonconvex-concan minimax problems. Zhang al. (2020) introduced a "smoothing" scheme combined with GDA to stabilize the dynamic of GDA. Luo et al. (2020) proposed method called Stochastic Recursive gradiEnt Descent Ascent (SREDA) for stochastic nomconnex--trrongly-ooom
minimax problems, by estimating gradients recursively and reducing its variance. Lin al. (2020) showed that the two-timescale GDA can find stationary point of Manconvex-concave minimax problems effectively. Ostrovskii et al. (202T) proposed variant of Nesterov's 's accelerated algorithm find e -frss-orddrr Nash equilibrium that a stronger criterion than the commonly used proximal gradient norm. Nouiched et al. (2019) proposed a iterative method that finds 6 -firstoorder Nash equilibrium in O iterations under Polyak-L.ojasiewik (PI.) condition. Focusing on nonconvex minimax problems, they studied an interesting and difficult problem. Since our work cast insight on the effectiveness of solving minimax optimization via Anderson Mixing, we expect the extension of this algorithm to general nonconvex problems can be further investigated in the future.
B ANDERSON MIXING IMPLEMENTATION DETAILS
In this section, we discuss the efficient implementation of Anderson Mixing. We start with generic Anderson Mixing prototype (Algorithm 4) and then present the idea of Quick QR-update Anderson Mixing implementation as described in Walker Ni (0115), which is commonly used in practice. For each iteration &. 2 0 AM prototype solves a least squares problem with a normalization constraint. The intuition is to minimize the norm of the weighted residuals of the previous m iterates.
Algorithm 4: Anderson Mixing Prototype (truncated version)
Input: Initial point wo, Anderson restart dimension p, fixed-poin mapping g R R". Output: Wi+1 for = 0, 1, ... do
Set p. = min
Set F, [fe-p..- ..... fel. where fa = g(w;) w; for each E [t Pe t). Determine weights 8 (B0.....33 )pp)" that solves ming (1 E Bs
Set w++1 = EPr Big (wt-piti).
end
The constrained linear least-squares problem in Algorithm AA can be solved in number of ways.
Our preference is to recast it in an unconstrained form suggested in Fang & Saad (2009); Walker & Ni 1b) that is straightforward to solve and convenient for implementing efficient updating of QR.
14

---

Published as a conference paper at ICLR 2022
Define f, g(w;) Wa, Af: fi+1 fa for each i and set F; pe--e...... fil. Fi
[A ftl.. Then solving the least squares problem (ming | S. t. E1 35 = 1) equivalent to
(10 No ))²² I1 Ferll2
min
(10)
where a and y are related by ogg = 70, a = 7/ % for 1 s Pr 1, and Opp. Yp.
Now the inner minimization subproblem can be efficiently solved as an unconstrained least squares problem by simple variable elimination. This unconstrained least-squares problem leads modified form of Anderson Mixing
Pr-1 1
W+++ g - Σ
Ti [g (wi-m+tit1) - 9 (we pctepp = (we) - 967(0)
1=0
where G. = [Age- - with Ag: = g(w++1) - g(w)) for each é.
To obtain 7(00 (700)
(1) by solving equation 10 efficiently, show how the successive
Tp.
least-squares problems can be solved efficiently by updating the factors in the QR decomposition Fi = QrRr the algorithm proceeds. We assume think QR decomposition, for which the solution of the least-squares problem is obtained by solving the x Pt. linear system Ry Q' ft. Each Fr x Pt and obtained from Ft-1 by adding a column on the right and, if the resulting number of columns is greater than p. also cleaning up (re- (re-initialize) the table. That is, we never need to delete the left column because cleaning up the table stands for restarted version of AM. As a result, we only need to handle two cases; 1 the table is empty(cleaned), 2 the table is not full. When the table is empty, we initialize 1 = Q1 with Q1 fo/ [|ll and R = || || fo 2|
If the table size is smaller than p, add column the right of Fi-1. Have Fi-1 QR, update and R that
F, = F A = R.. It is single modified Gram-Schmidt sweep that is described as follows:
Algorithm 5: QR-updating procedures
for i 1..... Pt-1 do
Set R(i, Pı) Q)) Afr-1. Update f + Af ((i.p.) ((122)
end
Set (:.p:) = -ft-1/ Af-11l2 and R (pr, = l| Af--122
Note that do not explicitly conduct QR decomposition in each iteration, instead we update the factors (O(p2n)) and then solve linear system using back substitution which has a complexity of Op²)). Based this complexity analysis, can find Anderson Mixing with QR-updating scheme has limited computational overhead than GDA (or OG). This explains why GDA-AM is faster than EG but slower than OG in terms of running time of each iteration.
C THEORETICAL RESULTS
C.I DIFFICULTY OF ANALYSIS ON GDA WITH ANDERSON MIXING
In the analysis, we study the inherent structures the dynamics of the fixed point iteration and provide the convergence analysis for both simultaneous and alternating schemes. We want to emphasize that the direct application of existing convergence results of GMRES can not lead to convergent results. A recent paper Bollapragada et al. (2018) study the convergence acceleration schemes for multi-step optimization algorithms using Regularized Nonlinear Acceleration. We also want to point out that naive application of Crouzeix's 's bound to the minimax optimization problem not be used to derive the convergent result.
Theorem C.1 (Fischer & Freund (1991)). Let 2 5 be an integer, > 1, and e E TR. Consider the following constrained polynomial minmax problem
min max [p(2)
(11)
PER PEP..p(c)=1
where
6, = =EC
ZEC +
(12)
15

---

Published as a conference paper at ICLR 2022
and C \ 6y- Then this problem can be solved uniquely by
Tn (n(22) Tn (c)
(n(z;))
(13)
where
( 11
1
1 1/
Tn(2)
2
1 )
=
2 -+
(14)
if
(a) lc 2 2 +r or
(b) lc 2 (1/2ar) (2a - -1 22a
a² +1) where a, :- (r ( +)
This is because the point where all the residual polynomials take the fixed value is included in the numerical range of the iteration matrix, which violates the assumption of Theorem C.I As a result, it can not be used to prove that the residual norm is decreasing based on this approach. Instead, we show that although the coefficient matrix is non-normal, it is diagonalizable. We then give the convergence results based on the eigenvalues instead of the numerical range. More specifically, Anderson mixing is equivalent to GMRES being applied to solve the following linear system:
(I- ((Al)) w = ((AI)), with Wo = wo (A1e)
(15)
Writing this linear system in the block form:
17 PAT w b(A)).
(16)
-
The residual norm bound for GMRES reads:
||r|||2 min Ilp(I (AAtt))))l))) )rolla-
(17)
pEPi
Notice that the matrix (I - G(Al)) is non-normal. If we apply Crouzeix's bound in Crouzeix & Palencia (2017) to our problem as |Bollapragada et al. (2018) did, then we have the following bound
||r|12 < min |p ((1))) s (1 v2) min
sup pePl ZE (EW(I-G(Ate)
Ilp(2))l
(18)
|ool]
pEP:
where W(I - G(A)))- = {z (I G(Alt) ) Vz E C2n (0), ||||| = 1} is the numerical range for I I- G(At)) In order to simplify the upper bound in the previous theorem, we study the numerical
range of I (ARl) similar to Bollapragada et al. (2018). Writing
2 and computing the Z2
numerical range of I- ((Alt) explicitly yields:
O T
A A
z Z2
1/ 2
2
A 22 + 1z2 -172" 21.
(19)
1
For general matrix A, there is special structure about the numerical range of I G (Alt), However, when is symmetric, we can decompose as = Σ Av..v where {Ai) are eigenvalues of in decreasing order and {vi}²_ are associated eigenvectors, and write A = Σm Xvv.v. Then we can compute the numerical range of (Att)) as follows:
Σ [zj, 15
nAV.V of PAVV
21
22vv ziv.
O
m o
Z1 v
(20)
22
2
Z2
Following the techniques proposed in Bollapragada al. 2018 to analyze the numerical range of general 2 matrices, can show that the numerical range of I (Alt)) is equal the convex hull of the union of the numerical range of
G = 1711
i 1, n.
(21)
17
2
16

---

Published as a conference paper at ICLR 2022
And the boundary of numerical range of G; is an ellipse whose axes the line segments joining the points x to and w to Z, respectively, with
x == 0, y = 12 w 2² - - =
X² A1y// 2
(22)
Thus, the numerical range of ((Att) be spanned by convex hull of the union of the numerical range of a set of 2-by-2 matrices and the numerical range each such a 2-by-2 matrix is an ellipse. We can compute the center o and focal distance of the ellipse generated by numerical range of I G(Al)) explicitly. Then linear transformation enables to use Theorem C.I to show that the
near-best polynomial for the minimax problem on the numerical range of G ((Al)) is given by
(2; == =x(=2) if O is excluded from the numerical range of I - ((M)) However, according to equation 22 the numerical range includes the point where the residual polynomial takes value thus the analysis based numerical range can not help derive the convergent result as the upper bound is not guaranteed to be less than
C.2 PROOFS OF THEOREM
We first provide proof of Theorem
Theorem C.2 (Global convergence for simultaneous GDA-AM bilinear problem). Denote the distance between the stationary point w and current iterate w (k+ of Algorithm 22 Anderson restart dimension p as N(k+1)p = dist(w", W(k+1)p)- Then we have the following bound for Ne Algorithm 2 is unconditionally convergent
N(k+1)p S Tp(1 x(-)-
Nkp
(23)
where Tp is the Chebyshev polynomial of first kind of degree and T,(1+ x
<
since
+
x() >
Proof of Theorem 4.1
Note that (9im) is a normal matrix which will be denoted as G for notational simplicity. Thus it admits the following eigendecomposstion:
G UAUT, OUT=N A diiag(A A2n).
(24)
Based on the equivalence between GMRES and Anderson Mixing, we know that the convergence rate of simultaneous GDA-AM can be estimated by the spectrum G. Especially, it holds that
((k+1)p = US5(A)U"r, rkp- Ep
(25)
where P, the family of residual polynomials with degree p such that (0( = 1,V5, E Pp. According to Lemma 2.1 we have the following estimation
[| Dplla = min fPEP,
(G) S min max (Ax)l]) rxpll2-
(26)
T.PP,
Due to the block structure of G, the eigenvalues of G can be computed explicitly as
+ tnoov= 1= 1,
(27)
where or the ith largest singular value of matrix. This shows that the eigenvalues of are pairs of purely imaginary numbers excluding 0 since has full rank.
Since the eigenvalues of G are distributed in two intervals excluding the origin
I- () 1I, mij ()v - my (VVII, ma 1I,
it can be shown that the following p-th degree polynomial with value at the origin that has the minimal maximum deviation from on is given by:
T(g(V-1z))
2( -Iz 1o mommn + nomin)
fx(2)= = Ti(g(0))
=1
(28)
(110 (1) ())2 (1)omin 0))
17

---

Published as a conference paper at ICLR 2022
where / [[] and Ti is the Chebyshev polynomial of first kind of degree l. The function (v maps I to 1-1,1] 1]. Thus the numerator of the polynomial fp is bounded by 1 on I. The size of denominator can be determined by the method discussed in Chapter of Greenbauml (197)). Assume ((0) = (v + )) then Ti()(0)) 2 (v' + y ) Then y can be determined by solving
((0) (n) ()2 + (n) 0))
(29)
mar ()) (1jō ())²
The solutions to this equation are
10 () + 110 min (
n0 ( 1/0min ()
1/1 ma 170 min!
or 1/2 n0 mar () + 170 ()
(30)
Then plugging the value of (()) into the polynomial fp yields
| (<(+1))l
Vi O V1 min 0
< 2
[kpl
v o O + Vnp min 0
(31)
= Omau () Tmin ())
k0) 1
mmax () + Omenn ()
n0) +1
Note that N, and r, is related through G(w, - -w") = rr. Therefore,
N(++1) W(++1)p w ||G (GG+t((+))llll min
||G f[G - -w")ll
SEEP
(32)
2
< min max (A.) w 2 S 2 e,P,, !
Nkp.
x()
Actually tighter bound can be proved after noting that the problem is essentially equivalent to polynomial minmax problem on the interval:
i= 1n2ommn O, 1220 (amax() O),
Then it is well known that.
1o < min EEEP Aelppo2 O. P 0)
max
[fp(A:)]l Wky - w2ll2
Nap
T + 2 -min
mas
Nap
T1 + )(²)-1
(33)
where Tp Chebyshev polynomial of degree of the first kind and
1. Explicitly,
T1 )
(1+
1
2
(1+ x(T') -1 )2 P
2
[1 + k(T)) - 1 =
2
x(T)
V
+
+(1 K(T
2
+ (1+ k(T) - )2 j2-1) "
k(T)- -
Next, give the proof of Theorem 4.2
Theorem C.3 (Global convergence for alternating GDA-AM on bilinear problem). Denote the distance between the stationary point w* and current iterate W(++1)p of Algorithm with Anderson restart dimension p as N(K+1)p dist(w", (' W(k+1)p)- Assume is normalized such that its largest singular value is equal to Then when the learning rate is less than 2, we have the following bound for N.
2n
N2
SV1+2
(k+1)pp
where e and are the center and radius of a disk D(c, r) which includes all the eigenvalues of G in equation 4.3 Especially, _ 1.
18

---

Published as a conference paper at ICLR 2022
Proof. Since the residual Tp of AA at p-th iteration has the form of that G is unitarily similar to a block diagonal matrix A with 2 x 2 blocks as follows:
Tp (I
G ro:
and AA minimizes the residual, we have
[ I min |[ rG'
min f,EP,
(G)
where Pp the family of polynomials with degree p such that f,( L, Vf, E Pp It's easy see
n0o (1o1))
Vie [n].
-non
Thus the eigenvalues of G can be easily identified as
A1 (no,,no, + ((no,)2- i [n].
where 01 2 02 2 ... 2 on are the singular values of Furthermore, the eigenvector and eigenvalue associated with each 2 diagonal block are
0 nJo (na,))
-na,
A+
= A1s
At
yja
Thus G diagonalizable and denote the matrix with the columns of eigenvectors of G by X. The real part of the eigenvalues of G are at least
R()+)) (1
i E [m].
(34)
2
And since |no; 2 (V(oo,)22 - 4) all the eigenvalues will be included in a disk D(c, r) which is included in the right half plane. Moreover, both and being greater than zero indicates that & 1. Start from the following inequality:
N N(++1pp
W(++1hp w = ||GG-raattlll S min
(GG)
J,EP,
min SPPP,
G (oG) (Wip w')ll= min SEP,
GG) (Wkp w w")ll
(35)
min Ilf (Wkp ww)ll S,EP,
We will use the eigendeomposition of G and the special polynomial (-= to derive the inequality in Theorem Now we know : < 1. If we choose (p()) = (--1), we can obtain
min (G) w")ll2 s (G) -oitp--w"ll e,P,
w")
which implies
min
[1 (G) w s "Illxw))ll((w) w')ll
SpP
Since G is diagonalizable (which has been shown above), we assume the eigendecomposition of G is G XAX-I Then
min (lgp(G)(wwp - < X X f,E,,
max [I)]())] (A,)
- 5 na( 1Pl - w' l|a
where Kig is the condition number of X. The last inequality comes from Lemma 6.26 and Proposition 6.32 in Saad (2003).. Since G and A are unitarily similar, is equal to the condition number of the eigenvector matrix of A. The eigenvector matrix of A is block diagonal matrix with the ith block
as A+s
Thus the singluar values of the eigenvector matrix of A is equal to the union of the
singular values of these 2- blocks. Under the assumption that the largest singular value of are equal to 1 and the learning rate is less than 2, it is easy to find the singular values of the eigenvector
matrix of A are /2 1 1J0t. Thus, KG -2-1j man
22+ mmax
1
2-
2n
19

---

Published as a conference paper at ICLR 2022
C.3 DISCUSSION OF OBTAINED RATES
We would like to first explain on why taking Chebyshev polynomial of degree at the point 1 ++ _ We evaluate the Chebyshev polynomial at this specific point because the reciprocal of this value gives the minimal value of infinite norm of the all polynomials of degree p defined on the interval 1= o (), 17 o men ()) based on Theorem 6.25 (page 209) (Saad 2003). In other words, taking the function value at this point leads to the tight bound.
x-I
When comparing between existing bounds, would like point our our derived bounds are hard to compare directly. Alternatively, we can derive another bound for comparison with existing bounds for simultaneous -MM If we use the inequality that (t()) 2 ((t + vt² -1)"), we can obtain
the bound p(A) = 4( - A)(A+A))+1
4(1- Vx(ATA) A) )), which is in a form that is comparable
with EG and can compete with EG + positive momentum. The numerical experiments in figure 2b numerically verify that bound is smaller than EG. We wanted to numerically compare rate with EG with positive momentum. However the bound of EG with positive momentum is asymptotic. Moreover, it does not specify the constants so we can not numerically compare them. We do provide empirical comparison between GDA-AM and EG with positive momentum for bilinear problems in Appendix D.I It shows GDA-AM outperforms EG with positive momentum. Regarding alternating GDA-AM, we would like to note that the bound in Theorem 4.2 depends on the eigenvalue distribution of the matrix G. Condition number not directly related to the distribution of eigenvalues of a nonsymmetric matrix G. Thus, the condition number is not precise metric to characterize the convergence. If these cigenvalues are clustered, then our bound can be small. On the other hand, these eigenvalues are evenly distributed in the complex plane, then the bound can very close to 1.
More importantly, we would like to stress several technical contributions.
1. Our obtained Theorem and 4.2 provide nonasymptotic guarantees, while most other work are asymptotic. For example, EG with positive momentum can achieve a asymptotic rate of 1 0(1 under strong assumptions (Azizian et al. 2020).
2. Our contribution is not just about fix the convergence issue of GDA by applying Anderson Mixing; another contribution is that we arrive at a convergent and tight bound on the original work and not just adopting existing analyses. We developed Theorem[4.) and 4.2 from new perspective because applying existing theoretical results fail to give us neither convergent nor tight bounds.
3. Theorem 4.1 and 4.2 only requires mild conditions and reflects how the table size controls the convergence rate. Theorem is is independent of the learning rate 17. However, the convergence results of other methods like EG and OG depend on the learning rate, which may yield less than desirable results for ill-specified learning rates.
C.4 CONVEX-CONCAVE AND GENERAL CASE
Given the widespread usage of minimax problems in applications of machine learning, it is natural to ask about its properties when being applied to general nonconvex-nonconcan settings. If f is nonconvex-monconncav function, the problem of finding global Nash equilibrium is NP-hard in general. Recently, Jin et al.] (2000) show that local or global Nash equilibrium may not exist in conconvex-nonconean settings and propose new notation local minimax as defined below:
Definition 4. A point (x* y²) is said to be a local minimax point of J, if there exists de > 0 and a function satisfying h()) -> as + O, such that for any E (0, 86]. and any (x, satisfying
||x - x < ô and ly y" < 8, we have
f (x" y) S f yx*,)*)
max
f (x,y').
y
Jin et al. (2020) also establishes the following first- and second-order conditions to characterize local minimax:
Proposition 1 (First-order Condition). Any local minimax point (x", ,Y") satisfies V .y) = O.
Proposition 2 (Second-ordes Necessary Condition). Any local minimax point (x", ,") satisfies
V f y") & and VxxI(x", yx)" (x" yy" yy fxx,, -x")) f(x"" f(x",))) > 0.
20

---

Published as a conference paper at ICLR 2022
Proposition 3 (Second-order Sufficient Condition). Any stationary point y") satisfies fx" yy) x and Vxxf(x', fxx.fx".yy) yY) yy f ,y)) - yxx (x", y 0 is
local minimax point.
Given the second-order conditions of local minimax, it turns out that above question is extremely challenging-GGDD -M is first-order method. But we can prove the following result for GDA-A AM:
Theorem C.4 (Local minimax as subset of limiting points GDA-AM). Consider a general objective function ((x.)) The set of limiting points of GDA-AM for minimax problem
min max f(x, y) XEX" yeR
includes the local minimax points of this function.
The definition of local minimax is stronger than that first order point. The convergence analysis for complexity of finding stationary point is included in the next section. The proof of Theorem C.4 needs the result from the following theorem.
Theorem C.S (Calettti et al. (2002)). Let 8 satisfy < S 8, for some constant 6g > O (refer to Calvetti et al. (2002) for details), and let 6a X satisfy |bb bnll S 5. Let k < and let x denote the kth iterate determined by the GMRES method applied to equation Ar = 66, with initial guess z O. Similarly, let æy denote the kth iterate determined by the GMRES method applied to equation Az with initial guess To Then, there are constants dg independent of 5, such that
Fk
2 S σkō
1 1
Then, we give the proof of Theorem C.4
Proof of Theorem C.4 For notational simplicity, we will denote Fxxf(x",y') fxyf(x",y" and f ,y) by Hx-x', H and Hy respectively. Simultancous GDA can be written as
x(+1 M(+1
xx Vxf(xx. y ye+ + V
W++1
=
Since the function is differentiable, Taylor expansion holds for Vxf(xx, and Vy (x., at local minimx point w* xx",""),
y") .y" vxf(x.. Vxf(x",
+ Hx x- (x, xx)) H Vy,((), Vyf(x', .y) Hy (y:-y') - Hy (x, - x') + o(l(w; w 112)
y- (y, y") + o( [w; wlll2)
Use the fact that vf((",,") 0 to simplify the above equations and obtain
Vxf(xx. = Hx (x: x") + y- (ye y²) o(l - w=ll2)
(x), = Hy (y: y*) + Hy*x (x: x*) + o(llw: - w (1))
Inserting the above formulas into the iteration scheme, it yields
X++1 = I - H Y++1
- I+ Hy
xi
+ Hx + -njHy n/xxxyx'' +e
H
W
+
y+
where denotes the higher order error o(I w 12). According to Theorem 2.2 we know that simultaneous GDA-AM equivalent to applying GMRES to solve the following linear system
- Hy
-1jHx-y- (1 (1- + vyHyy.
[al + H Hy
HH My
(I
Jw
w-b-c
of
where b T1Hx + y -ny"y-y--* -y xxxx-xxx
We now know that GDA-AM is equivalent to GMRES
being applied to solve the following linear system
aI + H
H y al H-
- H
w
21

---

Published as a conference paper at ICLR 2022
The symmetric part of the coefficient matrix of the above linear system is
aI nH x
0
0
al- aI-nHyy'
According to Proposition 2 al nyy-.- is positive definite since Hy'y* * 0. If Hx is positive semidefinite, then al + ryHx'x- is positive definite and we're done. Otherwise, assume Amin ( 0. Then for fixed when 1) < Amin " a:I + will be positive definite.
Then according to Theorem
2.2 we know GDA AM indeed converges. Let's create a new companion
linear system as follows
aI Hx Hy'x
Hy "yy'
w = b aw"
aI
Note that w w and GMRES on this companion linear system is convergent under suitable choice of learning rate 17. Let the iterates of GMRES for w, w, w be denoted by Wt. Wt. Wt. Then
|[w; well < || well ||:; well- According to Theorem C.5 we also have [w; w. <
Further more, again according to Theorem C.5 we know |/W, - well S oh <x +c). Starting from an initial point very close to w and let f + and a, - O, w, will converge to
0ge,
w = (x*, y*), which means the local minimax w = y is limiting point of GDA-RAM.
C
Theorem C.6. For strongly-conver saanver-srongyy-conccyyy the Nash equilibrium of this function.
f(x, GDA-AM will converge to
Proof: Since strongly-come convey--ccce----eeee convex-strongly stronglyyconeett function fx. y) has unique Nash equilibrium which also the unique minimax point, this minimax point must be the limiting point of GDA-AM according to Theorem C.4
C.4.1 BILINEARQUAADRATE GAMES
Moreover, we can further show that the GDA-AM converges on illinear-quadrain games. Consider quadratic problem as follows,
min max f(x,y) = Ay + x Bx - xER yER
y" +
bbx
(36)
where A is full rank, B and C are both positive definite.
Theorem C.7. (Global convergence for simultaneous GDA-AM on bilineur-quadraicc problem] Let For some constant
(Sim) be the residual of Algorithm being applied problem equation 36
<<
11 (Amin (J + +J)2 t/2
(Stm) |re
||rol|2,
4dmax (JJJ))
(37)
1₁B
nA
where J
and Amin and Amax denote the smallest and largest eigenvalue, respec-
AA
n/C
tively.
The convergence property of GMRES has been studied in the next theorem. We use this theorem to show the convergence rate of GDA-AM for bilinear-quadratia games.
Theorem C.8 (Elman (1822). Consider solving linear system Ex b using GMRES. Let r, = Ex, be the residual at ith iteration. If the Hermitian part of E is positive definite, then for positive constant p holds that
||rell S (1 (Amin E + E))²
1/2
||ro|l2-
4Amax (E E)
(38)
1²12
22

---

Published as a conference paper at ICLR 2022
Proof of Theorem C.7 Applying simultaneous GDA-AM solve the above problem is equivalent to applying Anderson Mixing on the following fixed point iteration:
X
BB
-IJ C-
X
r/b
V++1
7
yi
T/C
(39)
G(Qaed
(Quad-ator
(Qued-avm)
We know that we need to study the convergence properties of GMRES for solving the following linear system
BB ~
7A
b.
(40)
1/C
For notational simplicity, the superscripts has been dropped. Denote the coefficient matrix nB
n
-nA
nCC
by J. The symmetric part of is
J J
(
BB)
2
Toa (C+
which is positive definite. Then immediately by Theorem For some constant p 1,
C.8 the following convergence rate holds
(Amin (J + 2
1/2
||ra|2 min [p Jrllll peP!
||rl|2
(4)max (JJJ))
(41)
p-12
= -|00l
Note that the convergence of GDA-AM for bilinear-quadratie games can also be analyzed by numerical range as shown in (Bollapragada et al. 2018). Although we previously show that analysis based on the numerical range can not help derive convergent bound for bilinear games, we show analysis in Bollapragada et al. (0188) can extended to bilinear-quadratee games. When and are positive definite, is outside of the numerical range matrix G (Quad-aiing as shown in 7a When B C
not positive definite, can be included in the numerical range of matrix QQuad ssm) as shown in 7b That is saying analysis based on the numerical range (Crouzeix & Palencia 2017 Bollapragada et al. 2018) to the qlindaa--uuaraatic problem can lead convergent result when B and C positive definite. And analysis based on the numerical range not help us derive convergent results when or C is not positive definite.
C.5 STOCHASTIC CONVEX-NONCONE
CASE
this section, we study the convergence of GDA AM for convex-noncovace problem the stochastic setting with the same assumptions in Wei et al. (2021b); Xu et (202T), The recent work Wei et al. (2021b) proves the convergence the stochastic gradient descent with Anderson Mixing for min optimization. The convergence of GDA-AM AM for minimax optimization builds on top of with several modifications. The minimax problem is equivalent to minimizing a function (f.) = maxyey f(,y) (Lin et al. 2020). And are interested in complexity of pair of c-stationary point (z. y) instead of analysis of a point T.
Definition 5. (Lin et al. 2020 A pair of points (x, y) is an e-stationary point (c 2 0) of a differen- tiable function de if
[V < IPy (y + (1/EV,,(xxx))) - yll sc/l
Assumption 1. f Rd R is continuously differentiable. f(x) 2 flow -00 for any x e Rd. V f is globally L-pischhitz continuous; namely fV V fg))l2 $ L||x y112 for any 2. y E Rd.
23

---

Published as a conference paper at ICLR 2022
10
0
-2
-5
-6
-10
-20
-10
-2
(a) Positive definite B and C
(b) Random generated B and C
Figure
Numerical range of fixed-point operator (Simultaneous GDA-AM
I nB
-1A
for bilinear-quadraaic games.
1 rC
Assumption 2. For any iteration k, the stochastic gradient V fg.. (æx) satisfies Egg, [V (2x)]
ff (æx), ,Eg, [IV (#x) - ff (zx) [2] S 0², where > and Ek. k O, l.... are indepen-
dent samples that are independent of [x:}
Theorem C.9. For general convex-nonconcart function f, suppose that Assumptions 7 Zand hold. Batch size nh = n. for t = O....,N C > is constant. Br = AL(1+C-IJ de 2
C .0 az S min (1 and a, is chosen to make sure the positive definiteness of He Ler R be a random variable following Pt(() def Prob(R = t = 1/N, and N be the total number of stochastic GDA-AM calls needed to calculate stochastic gradients fss (wr) in our algorithm. To ensure E [|
(wa) [|]] I total number of stochastic GDA-AM calls needed to calculate stochastic gradients & Ss. (w.) is O()-))
Recall that we can recast GDA scheme as the following fixed point iteration.
W2+1 G(sim) (w:) A W. + V/V (we) with x
V(w) [ [x,((x,))
vyf(x,y)
Ignoring the stepsize and let W, and R, record the first and second order diffrence of recent m iterates:
W. Aw; Aw Aw,-1] R = AV AV,m+ ... AV-1]
Similarly Wei et al. 22221b)the Anderson mixing can be decoupled into
W++1 w. W,T,, (Projection step)
W+11 W. V.V. (Mixing step)
where B, is the mixing parameter, and V/2 V3 W.T, and T. is solved by
T = arg min IV; R,D + T|
T
We want argue that similar arguments in Wei et al. 202 be applied to the problem here. To see why Anderson mixing works for minimax optimization, we assume function f is smooth. Then the hessian matrix for Gl (sim) is
22
=
D2
xx
yy
24

---

Published as a conference paper at ICLR 2022
Notice that in small neighborhood of Wi+1, we have
R. = ---HW, = Rad
W.
Thus IIV R I + HW,Il2, which is equivalent to solving for vector pt such that Hp = Vg. This is exactly the second order method for the fixed point iteration problem. Also at each step the AM is minimizing the residual, the reason that AM equivalent GMRES for linear problem is that this quadratic approximation is exact. Finally, we rewrite AM as the quasi-newton framework as Wei et al. (202Tb) did.
W++1 = W, + H.V, where H P subject to H,R, = -
min H1
Finally, with damping parameter, Anderson mixing has the following form
W++1 W. 3.V; a, (W, + I.
(42)
also apply the very similar arguments prove key results in lemma lemma 2 in Wei et al. (2021b). There is also a key difference with Wei et al. (2021b). Here we are considering
fx,
minimax optimization problem. Thus our gradient is actually V(w) = V yx.
rather than
Vf(w) = V Vx/(x, y) This will introduce some difficulty to the dynamics of the fixed pointe yx
iteration. However, noticing that ||V|| = [VV((w]] and
(W1+1) S f (w:) + f (w.)² (W++1-1 - -w:) + 2 |we+1 - well2
f f (w:) + (w.)" T (Wi+1 - we) + || - well2
(43)
L 2 1
= (w() + (w.)) H.V+
1
where
(ww)) - (x/((x)))) V yx
(44)
call this the ascent-deseent gradient (ADG) which is the gradient for minimax optimization problem
min max yx, XER yERd
To why V (w:)² (We+1 - w.) S V (w.)) (W1+1 W.), we consider their difference
(V V)f (w.)" (W++1- - w.) = -2 2Vx (x y:) (x(+11 xt). For fixed yr. ((+, has the Talyor expansion:
fxx++1 = VT
(x++1-x/ (xx) T xxx (exff(x++00) (xx+) xx) (x)x1-x
Assuming f is convex w.r.t and apply safeguard to ensure f fx < (x,, can guarantee
(v - V)S (w,)² (We+1 w.) 0. Now applying lemmas in Wei al. 2021b). derive the
convergence of our method for general
function similarly.
D ADDITIONAL EXPERIMENTS
D.1 COMPARISON WITH EG WITH POSITIVE MOMENTUM
In this section, we include additional comparison between GDA- AM and EG with positive momentum. GDA-AM has two big theoretical advantages over EG with positive momentum. First, convergence of GDA-AM does not require strong assumptions provide nonasymptotic guarantees while convergence of EG with positive mometum is asymptotic. Experimental results are shown in 8 It indicates GDA AM outperforms EG with positive momentum. Finding a good choice of the inner and outer step size of EG and momentum term is hard. For EG with positive momentum, and the positive momentum term as 0.3 after grid search as shown in [8 and Sc On the other hand, GDA-AM converges fast for different step size without hyperparameter tuning.
choices of hyperparamters. Second, 4.1 and 4.2
set the step size of extrapolation step 1, the step size of update as 0.5,
25

---

Published as a conference paper at ICLR 2022
Dietenos norm (lop sog-s
Distence norm (lop (oale)
Dstance (log acale)
10
TOP
10
SMIGDA AI3DA
EG
p-0
6-
SMCDA-4M
BG
6G-PM
00
10
SImCAA.AM 1-1
SimGDA AM: --4.5
SIMEDA AM:: v
EGG
10
SmSONAMM
EG-FM: 2H0.1
FG-PM (60.5
EI-PMI 9-0.5
10
10
10
Iteraion
x10
leration
x10
Ileration
x10
(b) Effects of step size y, 8 is fixed (c) Effects of momentum term B. 1 is fixed
(a) 100, p 10
0.3.
Figure 8: Additional Comparison between GDA-AM and EG with positive momentum
D.2 ID MINIMAX FUNCTIONS
We begin with investigating the empirical performance of GDA-AM for non-trivial 1d bivariate functions. We set initial points as (3, 3) and m 20 or 5 for all functions. We use optimal learning
rates for all methods on each problem. Results are shown in Figure 9 TO 12 observe GDA-AM consistently outperforms all baselines and improves convergence.
13 and 14 We
worthwhile
to mention that the difference between GDA-AM and traditional averaging is twofold. First, traditional averaging does not involve adaptive averaging scheme and thus blindly converge (0,0) 0) for all Id bivariate functions. In contrast, GDA-AM obtains optimal weights by solving small linear system on past iterates. Using different weights for each iteration, GDA-AM able to minimize the residual of past iterates and thus find the solution of a fixed-poin iteration. More importantly, averaging does not change the GDA dynamic because averaging generates a new sequence parameters based on GDA iterates. This means averaging is independent with base training algorithm (GDA here). However, GDA- AM changes the dynamic directly by overwriting the latest iterate. means Anderson Mixing interacts with GDA, which is another major difference from averaging.
10-1
SimGDA
Distance to aptmal
10-5
AltGDA
Averaging
10-9.
10 13
OMD
-1
SimGDA-AM
Start
AltGDA-AM
Optima
10
-3
10-25
100
Reration
(x-0.25) -(v-0.76)) The optima for this function not (0, 0). Because averaging blindly converges to (0, 0), can never find the correct solution.
Figure 9: f(x y) = (r (v ()
3
D.3 DENSITY ESTIMATION
To test our proposed method, evaluate our method on two low-dimension density estimation problems, mixture of 25 Gaussians and Swiss roll. For both generator and discriminator, we use fully connected neural networks with hidden layers and 128 hidden units in each layer. Except for the output layer of discriminator that uses sigmoid activation, we use tanh-activation for all other layers. We run Adam and GDA-AM for 50000 steps. The learning rate is set as x 10-4 and B = 0, Bg = 0.9 after extensive grid search, which is close the maximal possible stepsize under which the methods rarely diverge. Figure 15 and show the output after {1K, 10K, 30K, 50K} iterations. It can be that method converges faster to the target distribution offers improvement Adam. In addition, we can observe that the generated samples using our method gather around the circle and less connected with other circles.
26

---

Published as a conference paper at ICLR 2022
10
SimGDA
Distarce optinel
AltGDA
10
Averaging
10
10-13
OMD
-1
SimGDA-AM
Start Optima
AltGDA-AM
10:11
10
Figure 10:
[x, y) = (4x²
(y
3x
0.05xx 0.1y")e 0.00(""")
+v"), All baselines except
averaging eyclying around the optima. Averaging is converging slowly.
10-1-
SimGDA
Distence aztimel
AltGDA
10
Averaging
10
OMD
-1
SiMGDA-AM
-2
Optima
Start
10-21
AIRGDA-AM
10
y² + 4ry. Baselines tend diverge. Averaging is converging slowly again because averaging can only blindly converge to (0, 0) and the optima for this function is (0, 0).
Figure 11: f(z v) 2x
D.4 ROBUST NEURAL NETWORK TRAINING
In this section, we test the effectiveness of GDA-AL AM by training a robust neural network on MNIST data set against adversarial attacks (Madry et al. 2019 Goodfellow et al. 2015 Kurakin et al. 2017) The optimization formulation is
max 6, S.L. 26
E(f (z; 8c (.w)..)
(45)
W
where w is the parameter of the neural network, the pair (x,, y:) denotes the i-th data point, and 8, is the perturbation added to data point i. The accuracy of our formulation against popular attacks, FGSM (Goodfellow al. 2015) and PGD (Kurakin et 2017). are summarized in Table Since solving such problem is computationally challenging, Nouiched al. (2019) proposed approximation of the above optimization problem with a new objective function as the following nonconvex-come problem:
(11.... -
m
min
(e ( .T)
(m))
Σ
1,4
20}
(46)
tET
where K is parameter in the approximation. and x is an approximated attack sample by changing the output of the network to label j. We use the public available implementation (Nouiehed et al. 2019 g We apply our algorithm top of (Nouiched et al. 2019) and compare results (p 50) with (Madry et al. 2019: Zhang et al.) 2019: 2020; Nouiched et al., 2019). Results are summarized in table We can observe that GDA- AM leads to comparable
slightly better performance to the other methods. In addition, GDA-A AM does not exhibit a significant drop in accuracy when is larger and this suggests the learned model is more robust.
27

---

Published as a conference paper at ICLR 2022
10
SimGDA
Distarce optinel
AltGDA
10
Averaging
10
10-13
OMD
SiMGDA-AM
-2-
Start Optima
AItGDA-AM
10:21
-4
10
50
100
Figure 12: f(x, y)
3
x
32
2zy 6x 3y + 4.
10
10-1.
SimGDA
Distance to optimal
AltGDA
Averaging
10
EG
10-13
OMD
10-42
SimGDA-AM
Start
AItGDA-AM
Optima
10:21
0
50
100
150
200
Reration
Figure 13: f(x, v) = x - y² -2xy + 6.
D.5 IMAGE GENERATION
In this section, we provide additional experimental results that are not given in Section Figure 18a and T8h show the Inception Score for CIFARIO using WGAN-GP and SNGAN. can be observed that our method consistently performs better than Adam and EG during training. Further, CIFAR-10 using WGAN-GP and SNGAN, GDA-A AM is slightly slower than Adam (about 110- 115% computational time), but significantly faster than EG (about 65-75% computational time).
D.6 DETAILS ON THE EXPERIMENTS
For our experiments, we used the PyTorch deep learning framework. Experiments were run one NVIDIA V100 GPU. The residual network architecture for generator and discriminator are sum- marized in Table 3 and 4 We use a WGAN-GP loss, with gradient penalty À = 10. When using the gradient penalty (WGAN-GP), we remove the batch normalization layers in the discriminator. When using SNGAN, we replace the batch normalization layers with spectral normalization. Hyper- paramters of Adam are selected after grid search. We use learning rate of 2 x 10-4 and batch size of 64. For table size of GDA-AM AM, set it 120 for CIFARI0 and 150 for ColebA. We set 31 0.0 and 3g = 0.9 as we find it gives us better models than default settings.
'htpss//pytorch.orr/
Natural
FGSM L.o
PGD
41
Lo
= 0.2
= 0.3
= 0.4
E = 0.2
8 = 0.3
== 0.4
Madry et al. (2019)
98.58%
96.09%
94.82%
89.84%
94.64%
91.41%
78.67%
Trade: e
U.35
97.37%
95.47%
94.86%
79.04%
94.41%
92.69%
85.74%
Trade: 0.40
97.21%
96.19%
96.17%
96.14%
95.01%
94.36%
94.11%
Nouiehed et al. (2019)
98.20%
97.04%
96.66%
96.23%
96.00%
95.17%
94.22%
Zhang al. (2020)
98.89%
97.87%
97.23%
95.81%
96.71%
95.62%
94.51%
GDA-AM
98.61%
97.75%
97.74%
97.75%
96.47%
95.91%
95.41%
Table 2: Test accuracies under FGSM and PGD attack. Trade refers to Zhang al. (2019).
28

---

Published as a conference paper at ICLR 2022
10a
10a1
SimGDA
Distance to opteral
10-3
AltGDA
Averaging
10-9
EG
10
OMD
10
SimGDA-AM
Start
AltGDA-AM
Optima
10-2
-2
0
20
60
80
100
Roratin
Figure 14: f(x, 2x.² + y 4xy + 3V" 7//²
Iteration
15-
15
05-
00
-35
-18
Itaebon 20020
Berst en S00EO
benation 30000
Burst DO0CO
15:
1.-
10-
-31
(a) Adam
(b) GDA-AM
Figure 15: 25 Gaussians: Evolution plot of Adam and GDA-AM Green dots are observed points and red dots are generated points.
Du12 2000
Itartt on J0000
IDeazinn 1000
Harat on 10000
70-
05
20-
22-
70-
15-
10
00
-0
(a) Adam
(b) GDA- AM
Figure 16: Swiss roll: Evolution plot of Adam and GDA-AM. Green dots are observed points and red dots are generated points.
29

---

Published as a conference paper at ICLR 2022
35.0
Adam
Adam
45
32.5
40
22.5
20.0
20
12.5
15
15.0
20000
42000
60000
B0C0C
100000
20000
60000
6COCO
80:00
100000
Soration
Raracion
(a) WGAN-GP (ResNet)
(b) SNGAN (ResNet)
Figure 17: FID (lower is better) for CIFAR 10
55
(a) IS for CIFARIO
(b) IS for CIFAR10
(c) FID CelebA
Figure 18: Left: IS for CIFARIO using WGANGP. Middle: IS for CIFARIO using SNGAN. Right:
FID for CelebA using WGANGP.
(a) Generated images for CIFARIO
(b) Generated images for CelebA
Figure 19: Generated Images for CIFARIO and CelebA using WGAN-GP(ResNett
30

---

Published as a conference paper at ICLR 2022
Table 3: ResNet architecture used for our CIFAR-10 experiments.
Generator
Input: R 128 (0,
Linear 128 256 4
ResBlock 128 + 128
ResBlock 256 + 256
ResBlock 256 - 256
Batch Normalization
ReLu
transposed conv. (256, kernel:3 x 3, stride:1, pad: 1 (anh(.)
Discriminator
Input: æ 33332x32
Linear 128 + 128 x x 4
ResBlock 128 - 128
ResBlock 128 128
ResBlock 128 + 128
Linear 128 + 1
Table 4: ResNet architecture used for our CelebA (64 x 64) experiments.
Generator
Input: R128 ~ N((,
Linear 128 512 8
ResBlock 512 - 256
ResBlock 256 - 128
ResBlock 128 - 64
Batch Normalization
Relu
transposed conv. (64, kernel:3 3, stride:1, pad: tanh(.)
Discriminator
Input: æ [33x6464
Linear 128 - 128 x x 4
ResBlock 128 - 128
ResBlock 128 256
ResBlock 256 - 512
Linear 512 + 1
31


Reviews:
[{"review_id": "kkfMXoj4BRn", "reviewer": "Reviewer_gBHU", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Strengths:\nS1 The authors propose using Anderson mixing strategy to solve the minimax optimization problem.\nS2. They theoretically show that the proposed method can achieve global convergence guarantees under mild conditions.\nS3. They conduct numerical experiments on some minimax problems for the CIFAR10 and Celeb A datasets to show that the proposed method converges faster for some convex-concave and non-convex-concave functions.\n\n\nWeaknesses:\nW1. The authors only discuss the convergence results for the simple bilinear games problems. They do not discuss the general nonconvex-nonconcave problem or the convex-nonconcave problem.\n\nW2. The Anderson acceleration technique is a standard method for accelerating the fix-point procedures. The algorithms developed in this paper seem incremental.\n \nW3. Many important references in this field are missing (See below). The authors should make numerical comparisons or discuss the differences between these methods.\n\nReferences:\n[1] A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problems. NeurIPS 2020.\n[2] An accelerated inexact proximal point method for solving nonconvex-concave minmax problems. SIOPT 2021. \n[3] On gradient descent ascent for nonconvex-concave minimax problems. ICML 2020.\n[4] Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods. NeurIPS 2019.\n[5] Efficient Search of First-Order Nash Equilibria in Nonconvex-Concave Smooth Min-Max Problems. SIOPT 2021. \n", "summary_of_the_paper": "Minimax optimization is a central problem in machine learning. The gradient descent ascent method is the most commonly used algorithm to solve this problem. This paper views the gradient descent ascent method as a fixed-point iteration and solves it using Anderson Mixing to converge to the local minimax. They show theoretically that the algorithm can achieve global convergence for bilinear problems under mild\nconditions. Some numerical experiments have been conducted.\n", "summary_of_the_review": "See above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jJg3ndL2ve-", "reviewer": "Reviewer_KCYs", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "*** Post rebuttal ***\n\nAfter a discussion with the authors, I updated my score to accept.\n\n******\n\n\nThe biggest concern of the paper is the novelty. The authors present the Anderson mixing technique and its link with GMRES, up to page 4. The claimed novelty begins at section 3: GDA-AM: GDA WITH ANDERSON MIXING. The author claim that  their work \"is the first work to improve the GDA dynamics by tapping into advanced fixed-point algorithms,\" although this idea was explicitly mentioned in a paper they cited: \n\n> ---\n> Recent work in optimization analysed adaptive algorithms, such as Anderson Acceleration (Walker and Ni, 2011), that are adaptive to the problem constants. They can be seen as an automatic way to find the optimal combination of the previous iterates.\n>\n> ---\n> Source: Azizian et al. (2020) , section 6.1.\n> \n\nIn the same paper, the authors refer to Scieur et al. (2016) and Bollapragada (2018) for the theoretical analysis of such a method. In particular, the result presented in Bollapragada et al. (2018) proposes an analysis of Anderson Acceleration for *any* nonsymmetric operator $\\textbf{G}$. They combine Theorem 3.1 (Crouzeix's bound) and Theorem 3.3. (optimal polynomial on ellipses from Fischer and Freund (1991), Th. 2), to obtain a general convergence bound. This result covers all the theoretical work presented in this paper.\n\nMoreover, it is surprising that the author did not use the Crouzeix's bound for their Theorem 4.2. In short, the Crouseix's bound says that when dealing with a nonsymmetric matrix $\\textbf{G}$ and polynomials $P_2$, we have \n\n$$\n|| P(G) ||_2 \\leq c \\max\\_{\\lambda\\in W(\\textbf{G})}  ||P(\\lambda) ||_2,\n$$\nwhere $W(\\textbf{G})$ is the *numerical range* of the matrix $\\textbf{G}$, and $c$ is a constant, bounded by $2$ (Crouzeix's conjecture) and proven to be upper bounded by $1+\\sqrt{2}$. In particular, it is unclear how the authors manage to prove the inequality (last display equation in the proof of Theorem B.2) (I removed the other details to focus on the important part)\n$$\n\\min \\_{f_p\\in\\mathcal{P}_p} ||f_p(\\textbf{G}) || \\leq \\left(\\frac{r}{p}\\right)^p\n$$\nwithout using the Crouseix's bound, as $\\textbf{G}$ is not symmetric.\n\n\nThat said, the numerical experiments are persuasive, but the paper should be presented in a whole other way to include the missing related work. I strongly recommend the author rework the paper and submit it to another venue, as Anderson mixing could positively impact the optimization of min-max problems.", "summary_of_the_paper": "The authors propose to use the Anderson Acceleration on min max problem. They show two theoretical results: convergence rate on bilinear problems when using simultaneous gradient decent-ascent, and convergence rate on bilinear problems when using alternating gradient decent-ascent. Finally, they present numerical results in favor of their approach.", "summary_of_the_review": "Because the original idea of the paper was briefly introduced in Azizian et al. (2020), but more importantly, because the theoretical results presented in this paper are already covered in Bollapragada (2018), I am not convinced the paper is novel enough to be published. Moreover, I have a concern about a detail in the proof of Theorem 2.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YhiOxdCvSyp", "reviewer": "Reviewer_VjNk", "summary": "", "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": "## Strengths: \n- The method is well motivated and the paper is well written. \n- The theoretical results are sound \n- The method seems to scale to GANs (when combined with Adam)\n\n## Weaknesses: \n- The comparison with the related work could be improved (see my detailed comment)\n\n\n\nI think the authors could discuss more the rates obtained in Thm 4.2 and Thm 4.1 and the standard rates obtained in the literature (e.g. the ones presented in Remark 4.2). For instance, a first step would be to stress that the value of $T_p(1 + x)$ has a closed-form solution (below Equation 21). Also, one could compute the Taylor expansion of $T_p(1 + x)$ when $x\\to 0$ to have an idea of the convergence speed. Looking at the formula below (21) It seems that you get an accelerated convergence rate (i.e. $\\rho(A)^{1/p} = 1 - O(1/\\sqrt{\\kappa})$. However, I am a bit surprised that you get this rate for $p=1$ because in that case, GDA-AM corresponds to Gradient Descent with line-search. Can you comment on the formula for the expression of the Chebyshev polynomial of degree p at the point $1+ \\frac{2}{\\kappa-1}$?\n \nFor the experiments (Fig 4): Azizian et al. 2020 use *positive* momentum + EG. I would be interested to see if SIM-AM still outperforms EG + *positive* momentum. Also, how did you tune the step size and the other hyper-parameters of the methods for the results obtained in figure 5?\nMoreover it seems counter intuitive since EG + positive momentum has a convergence rate of $\\rho(A)^{1/p} = 1 - O(1/\\sqrt{\\kappa})$\n\n## Summary of the Questions asked (by decreasing order of importance):\n1. Can you comment on the formula for the expression of the Chebyshev polynomial of degree p at the point $1+ \\frac{2}{\\kappa-1}$? It seems that your formula gives $\\rho(A)^{1/p} = 1 - O(1/\\sqrt{\\kappa})$ while for $p=1$ it should be $\\rho(A)^{1/p} = 1 - O(1/\\kappa)$ \n2. Can you compare your method with EG + positive momentum? (Empirically)\n3. Theorem 4.2 seems to give a convergence rate of $1 - O(1\\kappa)$  Do you agree with this statement? \n\n## Minor Question\nFrom my understanding, in order to get the theoretical guarantees you do not even need to use Anderson Mixing at each time step but only every p timesteps (and you only need to ensure that linear combination of $x_{t-i}$ can generate any polynomial of degree $p$ with coefficients that sums to 1).\nIs it why you analyze the algorithm every p step?\nWhat is the computational overhead (solving each timestep vs solving each p steps?) \nDo you consider this algorithm because it is more likely that it will extend beyond the least-square case?\n", "summary_of_the_paper": "This paper proposes a new optimization method for min-max optimization (That could actually be generalized to any variational inequality problem) based on Anderson Mixing. They prove the convergence of their algorithm in the case of bilinear min-max games for both alternated and simultaneous updates operator. They eventually try their algorithm on toy bilnear problems and GANs.", "summary_of_the_review": "As a summary, I think this submission is well written. I think some more work could be done to compare the obtained rates with the ones already present in the literature but it should be relatively easy to implement.  Also, I have some concerns regarding the theory and the comparison with respect to the baselines.\n\nI will increase or decrease my score depending on how the authors address my comments. (for instance, if everything is clarified I will increase the technical and empirical novelty score as well as the final score) \n\nFor now, I recommend accepting this paper.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "SFlHhmzNLPm", "reviewer": "Reviewer_t7gv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "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": "1) From the theoretical point of view, multiple analyses are missing. The only results are for GDA and bilinear cases. The authors didn't provide any analysis of their framework for the convex-concave case.\n\n2) Authors didn't provide any result for the Nonconvex-Nonconcave case( convergence to $\\epsilon$ stationary point). I think the result in [1] can be used to provide guarantees in this case. This is necessary to show the effectiveness of the method for GAN-related applications(e.g., the one in section 6.2).\n\n3)Author motivates the subject from a theoretical and practical point of view. \n\n4)In the introduction, the author reviewed the previous works carefully.\n\n5)The authors successfully provide simulation results for their algorithm.\n\n6)The paper is well-organized and well-written.\n\n7)the code is included for the bilinear case, but I couldn't find the code for the image generation experiment.\n\n\n[1]Wei, Fuchao, Chenglong Bao, and Yang Liu. \"Stochastic Anderson Mixing for Nonconvex Stochastic Optimization.\" arXiv preprint arXiv:2110.01543 (2021).\n-------------------------------------------------------------------\nPost rebuttal :\nI have read the authors response, and I increase\nmy score, but they should add the result on \ngeneral convex-concave problem and non-concave\nsetting and the discussion about it in the final version.\nAlso, I think there is still room to get faster convergence\n to saddle point that would be interesting if they can add \nto the final version.\n------------------------------------------------------------------", "summary_of_the_paper": "This paper focuses on solving minimax optimization using Anderson mixing. Anderson mixing is a framework to accelerate fixpoint iteration. The authors tried to use  Anderson mixing for the minimax optimization problem. In their framework, they use a weighted average of the solution of last p iterates and optimized over the weights to come up with a new point. \nThey show that for the bilinear case, this algorithm converges to the optimal stationary point. Finally, the authors simulated their method on synthetic examples as well as image generation on CIFAR10. ", "summary_of_the_review": "1) From the theoretical point of view, multiple analyses are missing. The only results are for GDA and bilinear cases. The authors didn't provide any analysis of their framework for the convex-concave case.\n\n2) Authors didn't provide any result for the Nonconvex-Nonconcave case( convergence to $\\epsilon$ stationary point). I think the result in [1] can be used to provide guarantees in this case. This is necessary to show the effectiveness of the method for GAN-related applications(e.g., the one in section 6.2).\n\n3)Author motivates the subject from a theoretical and practical point of view. \n\n4)In the introduction, the author reviewed the previous works carefully.\n\n5)The authors successfully provide simulation results for their algorithm.\n\n6)The paper is well-organized and well-written.\n\n7)the code is included for the bilinear case but I couldn't find the code for the image generation experiment.\n\n\n[1]Wei, Fuchao, Chenglong Bao, and Yang Liu. \"Stochastic Anderson Mixing for Nonconvex Stochastic Optimization.\" arXiv preprint arXiv:2110.01543 (2021).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to use Anderson Acceleration on min-max problems, provides some theoretical convergence rates and presents numerical results on toy bilinear problems and GANs.

After the discussion, the reviewers agreed that this paper makes a nice contribution to ICLR. Some concerns were originally expressed in terms of incrementality of the theoretical results with respect to previous work (KCYs, gBHU), but the authors have well clarified their contributions in the discussion, and have updated their manuscript accordingly. There were also initial concerns about the related work coverage, but this was also properly addressed in the rebuttal, with additional experimental comparisons as well as extended related work section, as well as an additional convergence result for convex-nonconcave problems.
Decision: Accept (Poster)