Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Kadan, Amit
Master of Science - MSc
University of British Columbia
Motivated by Generative Adverserial Networks, we study the computation of a Nash equilibrium in concave network zero-sum games (NZSGs), a multiplayer generalization of two-player zero-sum games first proposed with linear payoffs. Extending previous results, we show that various game theoretic properties of convex-concave two-player zero-sum games are preserved in this generalization. We then generalize last iterate convergence results obtained previously in two-player zero-sum games. We analyze convergence rates when players update their strategies using Mirror Descent, and Optimistic Mirror Descent. We analyze these algorithms when they are used with the squared l2 norm as a regularizer --- yielding Gradient Ascent, Extra-Gradient Method, and Optimistic Gradient Ascent. We show exponential convergence when the payoffs of players are linear, or strongly concave and smooth. For the more general method of Optimistic Mirror Descent, we show last iterate convergence for any monotone game with bounded gradients, as well as monotonic convergence in games with strictly monotone and smooth payoffs.
Last Iterate Convergence in Network Zero-Sum GamesbyAmit KadanB. Sc, University of Toronto, 2017a thesis submitted in partial fulfillmentof the requirements for the degree ofMaster of Scienceinthe faculty of graduate and postdoctoral studies(Computer Science)The University of British Columbia(Vancouver)December 2020© Amit Kadan, 2020The following individuals certify that they have read, and recommend to the Faculty of Graduate andPostdoctoral Studies for acceptance, the thesis entitled:Last Iterate Convergence in Network Zero-Sum Gamessubmitted by Amit Kadan in partial fulfillment of the requirements for the degree of Master ofScience in Computer Science.Examining Committee:Hu Fu, Computer ScienceSupervisorNicholas J. A. Harvey, Computer ScienceSupervisory Committee MemberiiAbstractMotivated by Generative Adverserial Networks, we study the computation of a Nash equilibrium inconcave network zero-sum games (NZSGs), a multiplayer generalization of two-player zero-sum gamesfirst proposed with linear payoffs. Extending previous results, we show that various game theoreticproperties of convex-concave two-player zero-sum games are preserved in this generalization. Wethen generalize last iterate convergence results obtained previously in two-player zero-sum games. Weanalyze convergence rates when players update their strategies using Mirror Descent, and OptimisticMirror Descent. We analyze these algorithms when they are used with the squared ℓ2 norm as aregularizer — yielding Gradient Ascent, Extra-Gradient Method, and Optimistic Gradient Ascent.We show exponential convergence when the payoffs of players are linear, or strongly concave andsmooth. For the more general method of Optimistic Mirror Descent, we show last iterate convergencefor any monotone game with bounded gradients, as well as monotonic convergence in games withstrictly monotone and smooth payoffs.iiiLay SummaryA widely used machine learning model known as Generative Adversarial Network (GAN) consistsof training two neural networks by pitting them against one another in a two-player game. In orderto understand whether the training process will terminate, it is common to study when a Nashequillibrium is reached — a point in time where neither agent can change their strategy to makegains. In a two-player game, where one player loses what the other wins, players following simplelearning rules have been shown to arrive at a Nash. However, many extensions of GAN introduceadditional networks to the game, and standard analyses do not apply. We study convergence to a Nashin a framework that allows for additional agents while preserving useful properties of the two-playerframework. We show that the same algorithms shown to converge to a Nash in the two-player gameconverge in this framework.ivPrefaceThe main body of the work presented in this thesis was largely conducted in collaboration with HuFu, and was accepted for publication at the European Conference on Machine Learning 2020 (ECML2020). The majority of the results found in Chapter 5 can be found in Kadan and Fu [22]. Theseresults were developed as a collaborative effort between the authors. The only exceptions are theresults in Section 5.2.3, which were developed and proved indepedently by the author of this thesis,and are currently unpublished.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.1 Game theoretical notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Real analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.3 Online learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.4 Game-playing algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.5 Dynamical systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 Two-Player Zero-Sum Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.1 Average iterate convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2 Last iterate convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2.1 Linear payoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.2.2 Smooth games with strongly concave-strongly convex payoff . . . . . . . . 133.2.3 Monotone gradient operator . . . . . . . . . . . . . . . . . . . . . . . . . 153.3 Omitted proofs from Section 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.3.1 Omitted proofs from Section 3.2.1 . . . . . . . . . . . . . . . . . . . . . . 163.3.2 Omitted proofs from Section 3.2.2 . . . . . . . . . . . . . . . . . . . . . . 173.3.3 Omitted proofs from Section 3.2.3 . . . . . . . . . . . . . . . . . . . . . . 204 n-Player Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.1 Extensions of GAN with additional agents . . . . . . . . . . . . . . . . . . . . . . 244.1.1 VAE/GAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24vi4.1.2 Triple-GAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.2 Network zero-sum games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.3 Last iterate convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.4 Omitted proofs from Section 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 305 Network Zero-Sum Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.1 Average iterate convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.2 Last iterate convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335.2.1 Linear payoffs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345.2.2 Smooth games with strongly concave payoffs . . . . . . . . . . . . . . . . 365.2.3 Monotone gradient operator . . . . . . . . . . . . . . . . . . . . . . . . . 385.3 Omitted proofs from Section 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.4 Omitted proofs from Section 5.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.4.1 Omitted proofs from Section 5.2.1 . . . . . . . . . . . . . . . . . . . . . . 415.4.2 Omitted proofs from Section 5.2.2 . . . . . . . . . . . . . . . . . . . . . . 475.4.3 Omitted proofs from Section 5.2.3 . . . . . . . . . . . . . . . . . . . . . . 526 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57A Standard Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60viiAcknowledgmentsI would like to express my gratitude to my supervisor Hu Fu. On top of providing technical expertise,the lessons I learned from you on what it takes to be a researcher were invaluable. I would also like tothank my undergraduate supervisor, Marsha Chechik, for first providing me with the opportunity todo research in computer science, and for pushing me to pursue graduate research. Lastly, I would liketo thank my parents, who, no matter what I choose to do in life, always offer their love and support.viiiChapter 1IntroductionConnections between game theory and learning had long been known, before interest resurgedrecently in the machine learning community, largely due to the success of Generative AdversarialNetworks (GANs), a novel framework for learning generative models [17]. A GAN is formulatedas a two-player zero-sum game between two neural networks, a generator and a discriminator. Thegenerator attempts to fool the discriminator by mapping random noise to images that look similar tosamples from a target distribution, while the discriminator learns to distinguish the generator’s outputfrom real samples from the target distribution. Theoretically, at the equilibrium of this game, thegenerator outputs the target distribution. In practice, GANs produce promising results on a numberof tasks including image generation, semantic segmentation, and text-to-image synthesis [16].Among many theoretical questions opened up by GAN, that of last iterate convergence hasattracted much attention and seen exciting progress. Classical results show that, when players useno-regret algorithms to play a two-player zero-sum game, the time average of their strategies convergeto a Nash equilibrium — a point where neither player can make gains by deviating from their currentstrategy. In GAN, strategies correspond to parameters of neural networks; averaging strategies makeslittle sense. It is therefore desirable that the players’ strategies, from iteration to iteration, shouldconverge to an equilibrium. This is known as last iterate convergence, which is not implied byclassical results. A number of simple algorithms have been shown to give rise to such convergence intwo-player zero-sum games, with exponential convergence rates in various settings [15, 24, 27].On the other hand, many recently proposed extensions of GAN go beyond the two-player zero-sumframework, either to address challenges faced by the original GAN, or to make it more versatile. Inparticular, many models introduce more agents (neural networks) to the game. For example, Hoanget al. [20] proposed using an ensemble of generators to address mode collapse, a common problem ofthe classical GAN, where the generator captures only one or few modes of the data distribution. Otherarchitectures incorporate a third classifying network, which is in direct competition with either thegenerator [30] or the discriminator [9]; such architectures are often built for semi-supervised learning.Lastly, some architectures incorporate an additional encoding network which, like the generator,competes with the discriminator, and allows for sampling from a latent distribution that encodesadditional information about the data distribution [5, 8, 14]. Results on two-player zero-sum games1do not apply to these architectures with more than two agents. It is also well known that two-playerzero-sum games have many properties not extensible to games with more players or non zero-sumpayoffs.We observe that the extensions above all give rise to network zero-sum games (NZSGs), a classof games first proposed and studied by Cai et al. [7]. An NZSG is structured by a graph, where eachnode corresponds to a player, and along each edge a game is played between its two node players.A player chooses one strategy to be used in all the games in which she is engaged; the sum of allplayers’ payoffs is always zero. Since players cannot choose different strategies for different games,an NZSG is not a simple parallelization of multiple two-player zero-sum games. However, Cai etal. [7] showed that NZSGs with linear payoffs preserve certain properties from two-player zero-sumgames. In particular a Nash in an NZSG can be computed via a linear program.Wefirst generalize results of Cai et al. [7] on the tractability of equilibrium forNZSGs (Section 5.1);we show that in an NZSG with concave payoffs, a Nash can be arrived at in a distributed manner wheneach player uses a no-regret algorithm. Then, as our main result, we show last iterate convergenceresults for NZSGs with several classes of payoffs (Section 5.2), when players adopt gradient-basedlearning rules used in practice, such as Gradient Ascent (GA), Extra-Gradient Method (EG), andOptimistic Gradient Ascent (OGA). GA is the most ubiquitous optimization algorithm. It may be seenas a smoothed best response, and so it may not be surprising that it produces dynamics that divergefrom the equilibrium in two-player zero-sum games with linear payoffs [10, 24]. We show that thisphenomenon persists in NZSGs with linear payoffs. EG and OGA, on the other hand, incorporatesome minimal memory, and use information from one step before. This small tweak has been shownto induce last iterate convergence in two-player zero-sum games with linear payoffs [13, 24, 27]. Weextend these to NZSGs, showing comparable convergence rates. Furthermore, we relax a standardassumption on the second derivative of player payoffs, and obtain an analysis that is more generaleven for the case of two-player zero-sum games.For two-player zero-sum games with strongly concave payoffs, GA, as well as OGA and EG, areknown to induce last iterate convergence; we generalize these results as well. We show that the proofsof convergence for both OGA and EG in the smooth and strongly concave game arise out of a moregeneral proof structure. In particular, Optimistic Mirror Descent (OMD), a meta-algorithm whichcaptures a large class of gradient-based optimization algorithms including OGA and EG, inducesmonotonic convergence towards the Nash of an NZSG with smooth and strongly concave payoffs.Lastly, we show that in any NZSG with concave payoffs and bounded gradients, players using OMDconverge to a Nash in last iterate.Strategies played in a repeated game give rise to a dynamical system; techniques for analyzingsuch systems naturally can be used to analyze various update algorithms [10, 11, 24]. Our results onboth the divergence of GA and convergence of EG and OGA in the linear game are built on linearalgebraic techniques used to analyze the corresponding dynamical systems. Crucial to the argumentsis an algebraic property we show for NZSGs; namely, that a Hessian matrix associated with the payofffunctions is antisymmetric everywhere. We relax an assumption standard in the literature, namely,2that this Hessian matrix is invertible. We accomplish this by analyzing the real normal form of thetransition matrix associated with the dynamical system induced by each learning rule in the lineargame. This is important in showing convergence in games with an odd number of players, or whenthe players have strategy sets of different dimensions.We use Lyapunov functions in order to to show results in NZSGs with strongly concave andsmooth payoffs. We show that the existence of a Lyapunov function for players using EG or OGAarises out of a more general phenomenon; namely, when players use OMD as a learning rule, theBregman Divergence between each Nash of the game, and the player strategy profile monotonicallydecreases at a rate proportional to the distance between them. Apart from existing arguments fortwo-player zero-sum games, our proof exploits a structural lemma (Lemma 5.1), which may be ofindependent interest.The rest of this thesis is structured as follows: Chapter 2 provides preliminary definitions andframeworks. Chapters 3 and 4 provide background and related work. In particular, Chapter 3discusses last iterate convergence results from the two-player zero-sum setting. Chapter 4 motivatesthe study of network zero-sum games, as well as provides some relevant related work. Chapter 5contains our main results on last iterate convergence in network zero-sum games. Chapter 6 containssome concluding statements. Standard results useful for proving the results in this thesis are relegatedto the Appendix.3Chapter 2PreliminariesScalars are denoted by roman text, and vectors in R푘 are denoted by boldface text. Functions mappingR푘 to R are also in roman, while functions mapping R푘 to Rℓ , where ℓ > 1, are denoted by boldface.For a square matrix 퐴 we denote the set of its eigenvalues by 휆(퐴), and its singular values by 휎(퐴).퐼푚 denotes the 푚×푚 identity matrix, and 0푚×푛 denotes the 푚×푛 null matrix.2.1 Game theoretical notationThroughout this thesis, we analyze the behaviour of algorithms via repeated games. Consider arepeated game of 푛 players. The players’ strategy sets consist of closed, convex sets, X푖 ⊆ R푑푖 . Eachplayer 푖 has a payoff 푝푖 :∏푛푖=1X푖→ R which maps strategy profiles to payoffs. At each time step 푡,each player chooses a strategy 풙푡푖 ∈ X푖 , and receives the payoff 푝푖 (풙푡1, . . . ,풙푡푛). We denote the strategyprofile of all players by 풙 B (풙1, . . . ,풙푛), the joint strategy space of all players by X B∏푛푖=1X푖 , andthe sum of the dimensions of player strategies 푑 B∑푛푖=1 푑푖 . We also denote the strategy profile of allplayers’ strategies aside from i by 풙−푖 B (풙1, . . . ,풙푖−1,풙푖+1, . . . ,풙푛).2.2 Real analysisWe let 〈·, ·〉 denote the standard inner product on R푘 . We let ‖·‖ denote a norm on R푘 , and let ‖·‖∗denote its associated dual norm, i.e., for a vector 풛 ∈ R푘 , ‖풛‖∗ = sup{〈풙, 풛〉 | ‖풙‖ ≤ 1}.Definition 2.1. Let X ⊆ R푘 be a closed convex set, and 푓 a real-valued function on X. 푓 is concaveif ∀풙,풙′ ∈ X and 훾 ∈ [0,1],푓 (훾풙 + (1−훾)풙′) ≥ 훾 푓 (풙) + (1−훾) 푓 (풙′).A function 푔 : X×Z→ R is concave in 풙 if for any 풛 ∈ Z, ℎ(풙) B 푔(풙, 풛) is concave. A function푓 : X → R푘 is convex if − 푓 (풙) is concave.Definition 2.2. Let X ⊆ R푘 be a closed convex set, and 푓 a real-valued function on X. 풖 ∈ R푘 is asupergradient of 푓 at 풙 if ∀풙′ ∈ X, 푓 (풙′) ≤ 푓 (풙) + 〈풖,풙′− 풙〉. The set of supergradients of 푓 at apoint 풙 is denoted by 휕 푓 (풙).4Equipped with the definition of a supergradient, we can define the gradient operator of an푛-player game. Letting 풖푖 ∈ 휕풙푖 푝푖 (풙), the gradient operator, denoted by v(풙), is defined to bev(풙) B (풖1, . . . ,풖푛).Lemma 2.1 (Supergradient inequality). Let X ⊆ R푘 be convex and compact, and 푓 a real-valuedfunction on X. Then 푓 is concave if and only if ∀풙,풙′ ∈ X and 풖 ∈ 휕 푓 (풙),푓 (풙′) ≤ 푓 (풙) + 〈풖,풙′− 풙〉.Definition 2.3. Let X ⊆ R푘 be a closed, convex set, and 푓 a real-valued function on X. For 훼 ≥ 0, afunction 푓 : X → R is 훼-strongly concave if ∀풙,풙′ ∈ X and 풖 ∈ 휕 푓 (풙),푓 (풙′) ≤ 푓 (풙) + 〈풖,풙′− 풙〉 − 훼2‖풙− 풙′‖2.A function 푔 : X×Z→ R is 훼-strongly concave in 풙 if for any 풛 ∈ Z, ℎ(풙) B 푔(풙, 풛) is 훼-stronglyconcave. A function 푓 : X → R is 훼-strongly convex if − 푓 (풙) is 훼-strongly concave.Definition 2.4. Let X ⊆ R푘 be a closed, convex set, and 푓 a real-valued function on X. For 퐿 > 0, afunction 푓 : X → R is 퐿-Lipschitz if ∀풙 ∈ X and 풖 ∈ 휕 푓 (풙), ‖풖‖∗ ≤ 퐿.Definition 2.5. Let X ⊆ R푘 be a closed, convex set, and and 푓 a real-valued function on X. For훽 > 0, a differentiable function 푓 : X → R is 훽-smooth if ∀풙,풙′ ∈ X,‖∇ 푓 (풙) −∇ 푓 (풙′)‖∗ ≤ 훽‖풙− 풙′‖.Definition 2.6. Let X ⊆ R be a closed, convex set, and let 품 : X →X. For 훼 ≥ 0, 품 is 훼-stronglymonotone if ∀풙,풙′ ∈ X〈품(풙′) − 품(풙),풙− 풙′〉 ≥ 훼‖풙− 풙′‖2.When 품 is 훼-strongly monotone with 훼 = 0, we refer to it simply as monotone.There have been varying assumptions on the smoothness of players’ payoffs used throughoutthe literature on last iterate convergence. In many, it is assumed that the profile of player utilities is훽-smooth, or, equivalently, that the gradient operator is 훽-Lipschitz. We use this as our definition ofa 훽-smooth game.Lastly, the following Lemma on concave functions will be useful in proving many of our results.Lemma 2.2 (First order optimality). Let 푓 be concave and X a closed and convex set on which 푓 isdifferentiable. Then, 풙∗ ∈ argmin풙∈X 푓 (풙) if and only if, ∀풙 ∈ X, 〈∇ 푓 (풙∗),풙− 풙∗〉 ≤ 0.2.3 Online learningConsider a learner that has to choose an action from closed a decision set X over a sequence ofdiscrete time steps. At each time step 푡, the agent picks a vector 풙푡 ∈ X while an adversary chooses a5concave function 푓푡 : X → R. The agent receives the payoff 푓푡 (풙푡 ), and gets to observe 푓푡 . The goalof the learner is to minimize their regret — the difference between their cumulative payoff and thepayoff of the best fixed action in hindsight:푟 (푇) B max풙∈X푇∑푡=1(푓푡 (풙) − 푓푡 (풙푡 )). (2.1)One of the most well-known online learning algorithms is mirror descent 1. Mirror descent willserve as the building block for all of the algorithms analyzed in this thesis. We begin by defining it inthe context of online learning.In order to describe mirror descent, we need to define what it means for a function 휙 to be amirror map. Let X ⊆ R푑 be a closed convex set. Let D ∈ R푑 be a convex, open set such that X isincluded in its closure. Then 휙 :D→ R is a mirror map if it satisfies the following three conditions:1. 휙 is 1-strongly convex and differentiable.2. The gradient of 휙 takes all possible values, i.e., ∇휙(D) = R푑 .3. The gradient of 휙 diverges at the boundary of D, i.e., lim풙→휕D ‖∇휙(풙)‖ =∞.We will also make use of the Bregman Divergence, which is defined with respect to a particularconvex function.Definition 2.7. Let 푅 : X → R be a continuously differentiable and convex function. Then theBregman Divergence w.r.t. 푅 is퐷푅 (풙, 풚) B 푅(풙) −푅(풚) − 〈∇푅(풚),풙− 풚〉. (2.2)We are now ready to define the mirror descent update. Consider a mirror map 휙, a step size휂푡 > 0, and 풖푡 ∈ 휕 푓푡 (풙푡 ). Mirror descent consists of the following update rule:풙푡+1 = argmax풙∈X{휂푡 〈풙,풖푡〉 −D휙 (풙,풙푡 )}. (2.3)Properties (1), (2), and (3) of the mirror map ensure that 풙푡+1 exists and is unique [6].2.4 Game-playing algorithmsThe mirror descent learning rule can be tailored for players engaged in a repeated game. Consider astep size 휂푡 > 0, a mirror map 휙푖 : X푖→ R, and 풖푡푖 ∈ 휕풙푖 푝푖 (풙푡 ). A player using the mirror descentlearning rule updates her strategy according to풙푡+1푖 = argmax풙푖 ∈X푖{휂푡 〈풙푖 ,풖푡푖 〉 −퐷휙 (풙푖 ,풙푡푖 )}. (MD)1Mirror descent is typically used as a convex optimization algorithm. In this paper, we use mirror descent as a learningrule for a player maximizing a concave payoff, and therefore (2.3) and (MD) ascend rather than descend the gradient.6We will often be interested in analyzing a variant of mirror descent, called optimistic mirrordescent (OMD). OMD often achieves better regret bounds than mirror descent when the payoffsreceived by an online learner don’t change drastically from iteration to iteration. This is particularlypertinent to repeated games, where an opposing player’s strategy at time 푡 + 1 often maintainsproximity to their previous strategy. OMD is a two-step process, and thus we require a secondarysequence of iterates, 풘푡푖 . Consider a step size 휂푡 > 0, a mirror map 휙푖 :X푖→ R, 풖푡+1푖 ∈ 휕∇풙푖 푝푖 (풙푡+1),and an adaptive predictorM푡푖 that belongs in the convex hull of {휕풙푖 푝푖 (풙푠푖 ), 휕풙푖 푝푖 (풘푠푖 )}푡푠=1. A playerusing the optimistic mirror descent learning rule updates her strategy according to풙푡+1푖 = argmax풙푖 ∈X푖{휂푡 〈풙푖 ,M푡푖 〉 −D휙 (풙,풘푡푖 )}(OMD)풘푡+1푖 = argmax풘푖 ∈X푖{휂푡 〈풘푖 ,풖푡+1푖 )〉 −D휙 (풘푖 ,풘푡푖 )}.Mirror descent and optimistic mirror descent yielding specific algorithms when used with aparticular mirror map, and, for the case of optimistic mirror descent, based also on the choice of theadaptive predictor.Much of the research studying last iterate convergence is motivated by training neural networks,which are generally parameterized by a set of real numbers, and optimized with the goal of minimizingsome differentiable loss function. In such a setting, it makes sense to view each player’s strategy vectoras living in the unconstrained space R푑푖 . A standard measure of proximity when one considers all ofR푑푖 is the euclidean norm. Therefore, it is natural to analyze convergence when X푖 = R푑푖 , 휙푖 = ‖·‖22,and each 푝푖 is differentiable and thus has a unique supergradient ∇풙푖 푝푖 (풙) at each point 풙. For aplayer using mirror descent, we can find a closed form for their update by taking the derivative andsolving for 풙푡+1푖 . This yields the gradient ascent update:풙푡+1푖 = 풙푡푖 +휂푡∇풙푖 푝푖 (풙푡 ). (GA)Likewise, we can consider using optimistic mirror descent with the mirror map consisting of thesquared euclidean norm in the unconstrained setting. For this mirror map, there exist two well-knownvariants of optimistic mirror descent based on the choice of adaptive predictor. One of these variantsconsists of usingM푡푖 ∈ 휕풙푖 푝푖 (풘푡 ). This yields the extra-gradient method,풙푡+1푖 = 풘푡푖 +휂푡∇풙푖 푝푖 (풘푡 ) (EG)풘푡+1푖 = 풘푡푖 +휂푡∇풙푖 푝푖 (풙푡+1).Another variant usesM푡푖 ∈ 휕풙푖 푝푖 (풙푡 ), and is known as optimistic gradient ascent (OGA). An appealingproperty of OGA is that it can be written in closed form as a single iterative step,풙푡+1푖 = 풙푡푖 +휂푡∇풙푖 푝푖 (풙푡 ) +휂푡−1(∇풙푖 푝푖 (풙푡 ) −∇풙푖 푝푖 (풙푡−1)). (OGA)72.5 Dynamical systemsIn order to prove our results, we often borrow tools from dynamical systems.Definition 2.8. Let D be an open subset of R푘 . A relation of the form 풙푡+1 = 품(풙푡 ), is a discretetime dynamical system with update rule 품 :D→ R푘 . A point 풛 is a fixed point of 품 if 품(풛) = 풛.Definition 2.9. A fixed point 풛 is asymptotically stable if there exists a 훿 > 0, such that for any풙 ∈ D, ‖풙− 풛‖ < 훿, we have ‖품푡 (풙) − 풛‖ → 0, as 푡→∞. A fixed point 풛 is globally asymptoticallystable if for any 풙 ∈ D, ‖품푡 (풙) − 풛‖ → 0, as 푡→∞.For a dynamical system with update rule 품 :D→ R푘 , the Jacobian is the matrix with its (푖, 푗)-thentry 퐽푖 푗 =휕품푖휕풙 푗. Under certain conditions, the eigenvalues of the Jacobian 퐽 at a fixed point 풛 can beused to show that 풛 is asymptotically stable.Another method for analyzing the stability of fixed points of a dynamical system is by using apotential function 푉 .Theorem 2.1 ([4]). Let 풛 be a fixed point of the dynamic 품(풙). Assume that 품 is 퐿-Lipshcitz. Ifthere exists a continuous function 푉 : R푘 → R such that푉 (풛) = 0, and 푉 (풙) > 0,∀풙 ∈ R푘\{풛} (2.4)‖풙‖ →∞⇒푉 (풙) →∞ (2.5)푉 (품(풙)) −푉 (풙) < 0,∀풙 ∈ R푘 . (2.6)Then 풛 is globally asymptotically stable.When a potential function 푉 satisfies the conditions of Theorem 2.1, 푉 is known as a Lyapunovfunction.8Chapter 3Two-Player Zero-Sum GamesWe begin by describing convergence results for two-player zero-sum games. In Section 3.1 wedescribe how the online framework can be used to show average iterate convergence for players usinga large class of algorithms in concave-convex two-player zero-sum games. In section 3.2 we providerecent results showing last iterate convergence in concave-convex two-player zero-sum games.3.1 Average iterate convergenceAn algorithm is a no-regret learning algorithm if for any sequence of bounded and concave payoffs,it’s regret grows sublinearly, i.e. 푟 (푇) = 표(푇). Mirror descent is a standard no-regret algorithm.This is formalized in the following Theorem. The proof is based on the analysis of Allen-Zhu andOrecchia [1].Theorem 3.1 ([6]). Let 휙 be a mirror map that is 1-strongly convex on X ∩D w.r.t ‖·‖. Let푅2 = sup풙∈X∩D(휙(풙) −휙(풙0)) , and assume 풙0 = argmin휙(풙). Let 푓1, . . . , 푓푡 be a sequence ofconcave and 퐿-Lipschitz payoffs w.r.t ‖·‖. Then an agent using mirror descent with constant stepsize, 휂 = 푅퐿√2푇 , satisfies ∀풙 ∈ X,1푇푇∑푡=1(푓 (풙) − 푓 (풙푡 )) ≤ 푅퐿√ 2푇.Proof. Let 풙 ∈ X∩D. Let 풖푡 ∈ 휕 푓푡 (풙푡 ). Then, by the supergradient inequality on 푓푡 ,휂( 푓푡 (풙) − 푓푡 (풙푡 )) ≤ 휂〈풖푡 ,풙− 풙푡〉≤ 휂〈풖푡 ,풙푡+1− 풙푡〉 +휂〈풖푡 ,풙− 풙푡+1〉.By the first order optimality of 풙푡+1, and the Bregman triangle equality,〈풖푡 ,풙− 풙푡+1〉 ≤ 〈∇휙(풙푡+1) −∇휙(풙푡 ),풙− 풙푡+1〉= 퐷휙 (풙,풙푡 ) −퐷휙 (풙,풙푡+1) −퐷휙 (풙푡+1,풙푡 ).9Plugging back in, and using the fact that 휙 is 1-strongly concave w.r.t ‖·‖,휂( 푓 (풙) − 푓 (풙푡 )) ≤(휂〈풖푡 ,풙푡+1− 풙푡〉 − 12‖풙푡+1− 풙푡 ‖2)+(퐷휙 (풙,풙푡 ) −퐷휙 (풙,풙푡+1))≤ 휂22‖풖푡 ‖2∗ +(퐷휙 (풙,풙푡 ) −퐷휙 (풙,풙푡+1)),where the last line is by Cauchy-Schwartz. Summing over 푡,푇∑푡=1(푓 (풙) − 푓 (풙푡 )) ≤ 퐷휙 (풙,풙0)휂+휂 퐿2푇2.By first order optimality,D휙 (풙,풙0) = 휙(풙) − 〈∇휙(풙0),풙− 풙0〉 −휙(풙0) ≤ 휙(풙) −휙(풙0) ≤ 푅2.Plugging in for 휂 and dividing by 푇 , we get the desired result. The existence of no-regret algorithms can be used to show convergence of players’ averageiterates to an equillibrium of a two-player zero-sum game when each player’s payoff is concave. Ina two-player zero-sum game, one player must lose what the other wins. Thus, we can model thisgame using a single payoff, 푝(풙1,풙2) = −푝1(풙1,풙2) = 푝2(풙1,풙2). Rather than both players trying tomaximize their respective payoffs, we let player 1 maximize 푝, while player 2 minimizes 푝. Sinceplayer 2 is minimizing 푝, then the assumption that 푝2 is concave in 풙2 can be recast as 푝 being convexin 풙2, making 푝 concave-convex.We hope that after some time, when players play the game according to some learning rule, theyconverge to an equillibirum. One such equillibrium is the Nash equillibrium of the game, a strategyprofile (풙∗1,풙∗2) such that ∀풙1 ∈ X1,∀풙2 ∈ X2,푝(풙∗1,풙2) ≤ 푝(풙∗1,풙∗2) ≤ 푝(풙1,풙∗2). (3.1)A Nash equillibrium ensures that no player can increase their payoff by unilaterally deviating fromthe given strategy profile.Theorem 3.1 shows that when presented with a sequence of concave payoffs, 푓1, . . . , 푓푡 , a playercan achieve sublinear regret by employing a no-regret algorithm. We can apply this idea to a playerengaged in a repeated game by letting 푓푡 (풙1) = 푝(풙1,풙푡2). Similarly, a minimizing player will suffersublinear regret if they apply a no-regret learning rule to the sequence of payoffs 푓푡 (풙2) = −푝(풙푡1,풙2).Combining these results we get ∀풙1 ∈ X1,∀풙2 ∈ X2,1푇(푇∑푡=1푝(풙푡1,풙2) − 표(푇))≤ 1푇푇∑푡=1푝(풙푡1,풙푡2) ≤1푇(푇∑푡=1푝(풙1,풙푡2) + 표(푇)). (3.2)Denoting the time average of the first 푇 strategies played by each player as 풙¯푇1 , 풙¯푇2 , and using the10fact that 푝(풙1,풙2) is concave-convex,min푥11푇푇∑푡=1푝(풙1,풙푡2) ≤ min풙1 푝(풙1, 풙¯푇2 ) (3.3)≤ max풙1min풙2푝(풙1,풙2)≤ min풙1max풙2푝(풙1,풙2)≤ max풙2푝(풙¯푇1 ,풙2)≤ max풙21푇푇∑푡=1푝(풙푡1,풙2).Combining (3.2) and (3.3) yieldsmax풙2푝(풙¯푇1 ,풙2) −min풙1 푝(풙1, 풙¯푇2 ) ≤표(푇)푇. (3.4)Since lim푇→∞ 표 (푇 )푇 = 0, we have that at the limit, the inequalities of (3.3) hold with equality, i.e.,lim푇→∞min풙1푝(풙1, 풙¯푇2 ) =max풙1 min풙2 푝(풙1,풙2) (3.5)=min풙1max풙2푝(풙1,풙2)= lim푇→∞max풙2푝(풙¯푇1 ,풙2),showing that the strategy profile consisting of the time average strategies of players convergesto a Nash equillibrium as the time horizon stretches to infinity. Since this also shows thatmax풙1 min풙2 푝(풙1,풙2) =min풙1 max풙2 푝(풙1,풙2), this constitutes an alternative proof of Sion’s Mini-maxTheorem—ageneralization ofVon-Neumann’s heraldedMinimaxTheorem to all concave-convexgames.3.2 Last iterate convergenceThe results presented in the previous section show that when two players engaged in a zero-sum gameeach use a no-regret algorithm to determine their strategy at every time step, the time-average strategyprofile converges to a Nash. In contrast, many recent works — motivated by Generative AdversarialNetworks (GANs), attempt to show last iterate convergence for various online learning algorithms.The GAN framework defines a class of generative models which are trained by pitting twoneural networks against one another in a two-player zero-sum game. The goal of GAN is for thegenerator to learn to produce samples from some data space D. In the GAN game, a discriminator퐷 :D→ [0,1] competes with a generator 퐺 :Z→D. The generator attempts to produce samplessimilar to the target distribution D by transforming samples from a latent space Z - typically amultivariate Gaussian distribution, while the discriminator attempts to distinguish between samples11produced by the generator and those sampled from the target distribution. This is accomplished byhaving the generator and discriminator engage in a two player zero-sum game with payoff푝(퐷,퐺) = E푥∼푝D (풙) [log(퐷 (풙))] +E풛∼푝Z (풛) [log(1−퐷 (퐺 (풛)))] , (3.6)where the generator is the minimizing player, and the discriminator is the maximizing player.In GAN, the players are neural networks, and thus taking the average of parameters makes littlesense. It is therefore desirable that players’ strategies, from iteration to iteration converge to a Nash— what is known as last iterate convergence. Inspired by GAN, many recent works have shownlast iterate convergence in a variety of concave-convex two-player zero-sum games. We present anoverview of these results in the following sections.3.2.1 Linear payoffAs mentioned in Section 2.4, since neural networks are generally parameterized by a vector ofreal numbers, it is common to study convergence in the setting for which the strategy spaces areunconstrained, i.e., X푖 = R푑푖 .Since we already know that players using mirror descent to update their strategies in a concave-convex game converge to a Nash in average iterate, we might hope that this carries over to last iterate.However, a surprising result due to a number of works, is that players using variants of mirror descentin a game with linear payoffs do not converge to a Nash in last iterate [3, 13, 24]. If instead playersemploy variants of optimistic mirror descent, they do indeed converge.Consider an unconstrained two-player zero-sum game with payoff 푝(풙1,풙2) = 풙>1퐶풙2, where퐶 ∈ R푑×푑 is a full rank matrix. When each player’s strategy set is the entire space R푑 , it is not hardto see that the lone Nash of the game lies at the point 0. Liang and Stokes [24] show that if eachplayer uses GA as a learning rule, then for any time step 푡,‖풙푡+11 ‖22 ≥ (1+휂2푡 휆min(퐶퐶>))‖풙푡1‖22 (3.7)‖풙푡+12 ‖22 ≥ (1+휂2푡 휆min(퐶>퐶))‖풙푡2‖22.As the Nash is singular, if player strategies are initialized randomly, they diverge from the Nash at anexponential rate with probability 1.On the other hand, if players use variants of optimistic mirror descent — EG and OGA, it can beshown that they converge exponentially fast to the Nash. This is formalized in the following Theoremsfrom Liang and Stokes [24]:Theorem 3.2 ([24]). Consider an unconstrained two-player zero-sum game with payoff 푝(풙1,풙2) =풙>1퐶풙2. Assume 푑1 = 푑2 and that퐶 is full rank. Let 풙01 ∈X1,풙02 ∈X2, and assume that ‖풘01‖22+‖풘02‖22 ≤푟2. Then if each player updates her strategy according to EG with fixed step size 휂 =√휆min (퐶퐶>)2휆2max (퐶퐶>) , at12each time step 푡,‖풘푡1‖22 + ‖풘푡2‖22 ≤ 푟2 exp(− 푡4휆2min(퐶퐶>)휆2max(퐶퐶>)).Theorem 3.3 ([24]). Consider an unconstrained two-player zero-sum game with payoff 푝(풙1,풙2) =풙>1퐶풙2. Assume 푑1 = 푑2 and that퐶 is full rank. Let 풙01 ∈ X1,풙02 ∈ X2, and assume that ‖풙01‖22+ ‖풙02‖22 ≤푟2. Then if players update their strategies according to OGA with fixed step size 휂 = 12√2휆max (퐶퐶>), ateach time step 푡,‖풙푡1‖22 + ‖풙푡2‖22 ≤ 8푟2 exp(− 푡8휆max(퐶퐶>)휆min(퐶퐶>)).Liang and Stokes [24] achieve these results by viewing the joint update to the strategy profile as adynamical system acting in X1×X2. Since each player’s payoff is linear in their strategy, the resultingdynamical system is of the form 품(풙) = 퐽풙푡 , where 퐽 is the Jacobian of 품(풙) (see Section 2.5 for thedefinition of the Jacobian). In the linear game, the dynamical system induced by each player usinggradient ascent to update her strategy is given by[풙푡+11풙푡+12]=[퐼푑 휂푡퐶−휂푡퐶> 퐼푑] [풙푡1풙푡2]. (3.8)As given by Lemma A.4, the ℓ2-norm of a matrix-vector product is bounded by the singular values ofthe matrix multiplied by the norm of the vector. Since the system is linear, we can bound the normof the iterates by the singular values of the Jacobian. Lower bounding the norm of the dynamicalsystem in (3.8) yields[풙푡+11풙푡+12]2≥ 휆min([퐼푑 +휂2푡퐶퐶> 0푑×푑0푑×푑 퐼푑 +휂2푡퐶>퐶]) [풙푡1풙푡2]2, (3.9)which gives us the bound from (3.7). Notice that generally if the minimum singular value is greaterthan 1, the strategies of players diverge from the point 0 at an exponential rate.The bounds for OGA and EG are deduced in a similar manner. For the case of EG, it is possibleto show that the maximum singular value of the Jacobian of the resulting dynamical system is strictlyless than 1, and hence players converge to the point 0 at an exponential rate. We include the proof forEG in Section 3.3.1.3.2.2 Smooth games with strongly concave-strongly convex payoffIn this section, we present results which analyze convergence under the assumption that the game is훽-smooth and that the payoff is 훼-strongly concave in 풙1 and 훼-strongly convex in 풙2. When a payoffof a two-player zero-sum game is 훼-strongly concave in 풙1 and 훼-strongly convex in 풙2, we refer to itas 훼-strongly concave-훼-strongly convex. Similar to games with a linear payoff, exponential rates of13convergence can be shown in this setting. In contrast to the linear setting, in a game where playersuse any one of GA, EG, or OGA as a learning rule, their strategies converge to a Nash in last iterate.A note on the existence of Nash: unlike the linear game, when we had a guaranteed Nash atthe point 0, due to the non-compactness of player strategies, a Nash may not exist. Therefore, wemust assume the existence of a Nash in each of the following theorems. For applications such asGANs, where strategies are parameters of neural networks, strategy spaces are practically compact,and therefore a Nash is guaranteed to exist.Theorem 3.4 ([24]). Consider an unconstrained two-player zero-sum game that is 훽-smooth, with apayoff that is twice differentiable and 훼-strongly concave-훼-strongly convex with 훼 > 0. Assumethere exists a Nash, 풙∗. Let 풙01 ∈ X1,풙02 ∈ X2, and assume that ‖풙01− 풙∗1‖22 + ‖풙02− 풙∗2‖22 ≤ 푟2. Then ifeach player updates her strategy according to GA with fixed step size 휂 = 훼훽2, at each time step 푡,‖풙푡1− 풙∗1‖22 + ‖풙푡2− 풙∗2‖22 ≤(1− 훼훽2) 푡푟2.Theorem 3.5 ([27]). Consider an unconstrained two-player zero-sum game that is 훽-smooth, with apayoff that is differentiable, 훼-strongly concave-훼-strongly convex with 훼 > 0. Assume there exists aNash 풙∗. Let 풙01 ∈ X1,풙02 ∈ X2, and assume that ‖풘01− 풙∗1‖22 + ‖풘02− 풙∗2‖22 ≤ 푟2. Then if each playerupdates her strategy using EG with fixed step size 휂 = 14훽 , at each time step 푡,‖풘푡1− 풙∗1‖22 + ‖풘푡2− 풙∗2‖22 ≤(1− 훼4훽) 푡푟2.Theorem 3.6 ([27]). Consider an unconstrained two-player zero-sum game that is 훽-smooth, with apayoff that is differentiable, 훼-strongly concave-훼-strongly convex with 훼 > 0. Assume there exists aNash 풙∗. Let 풙01 ∈ X1,풙02 ∈ X2, and assume that 풙01 = 풙11 and 풙02 = 풙12, and ‖풙01−풙∗1‖2+ ‖풙02−풙∗2‖2 ≤ 푟2.Then if each player updates her strategy according to OGA with fixed step size 휂 = 14훽 , at each timestep 푡,‖풙푡+11 − 풙∗1‖2 + ‖풙푡+12 − 풙∗2‖2 ≤ 1024(1− 훼4훽) 푡훽2훼2푟2.Similar to the analysis of algorithms in the linear game, a dynamical systems understanding isused by the authors to show convergence in last iterate.Liang and Stokes [24] show that when players update their strategies according to GA in a gamewith 훼-strongly concave-훼-strongly convex, they converge to a Nash at an exponential rate. In asimilar manner to their analysis for the linear game, they accomplish this by upper bounding thesingular values of the Jacobian of the dynamical system induced by players using GA.When 푝 is twice differentiable, the assumption that it is 훼-strongly concave-훼-strongly convex is14equivalent to the following conditions on the singular values of the second derivatives of 푝,휎max(∇2풙1 푝(풙1,풙2)) ≤ −훼 (3.10)휎min(∇2풙2 푝(풙1,풙2)) ≥ 훼. (3.11)Likewise, the 훽-smoothness of the game can be reformulated as an upper bound on the singularvalues of the second derivatives of 푝,휎max([∇2풙1 푝(풙1,풙2) ∇2풙2,풙1 푝(풙1,풙2)−∇2풙1,풙2 푝(풙1,풙2) −∇2풙2 푝(풙1,풙2)])≤ 훽. (3.12)Condition (3.12) has a similar effect to assuming that the maximum singular value of 퐶 is boundedin the linear game, an assumption which was required in order to show convergence for that setting.The full proof of Theorem 3.4 can be found in Section 3.2.2Mokhtari et al. [27] show the convergence of both EG and OGA. They achieve this by using thesquared euclidean distance of the strategy profile at time 푡 from the Nash as a Lyapunov function.They show that at each time step, this potential function decreases by a multiplicative constantresulting in the statements of Theorems 3.5 and 3.6. We include the full proof of Theorem 3.6 inSection 3.3.2.3.2.3 Monotone gradient operatorIn the previous two sections, we presented results showing exponential convergence for variants ofmirror descent and optimistic mirror descent with the specific mirror map 휙푖 = ‖·‖22. Exponentialconvergence is a phenomenon which seems to be unique to players using the squared ℓ2 norm asa regularizer. However, the more general phenomenon of last iterate convergence is extensible toplayers using mirror descent and optimistic mirror descent with arbitrary mirror maps. In this section,we present the results of Mertikopoulos et al. [26] showing last iterate convergence for mirror descentand optimistic mirror descent. Each result can be seen as capturing a quite general setting underwhich we can expect each algorithm to converge in last iterate.For mirror descent, we already know that we cannot expect convergence for the full realm of gameswith concave-convex payoffs. Mertikopoulos et al. [26] show that players updating their strategiesaccording to mirror descent will converge to a Nash in last iterate in a two-player zero-sum game witha payoff that is 훼-strongly concave-훼-strongly convex, and 퐿-Lipschitz. For OMD, Mertikopouloset al. [26] show that in any concave-convex two-player zero-sum game with smooth payoffs, thevariant corresponding to EG converges to a Nash at a monotonic rate. In the following theorems, andlater in our proofs, we make use of the joint mirror map, 휙(풙) B 휙1(풙1) +휙2(풙2).Theorem 3.7 ([26]). Consider a two-player zero-sum game where the strategy space of each playerX푖 ⊂ R푑푖 is a convex, compact set. Assume that the payoff is 퐿-Lipschitz, that the gradient operatorof the game is 훼-strongly monotone with 훼 > 0, and that D휙 (풙∗,풙0) is finite. Then, if at each time15step 푡, each player uses MD to update her strategy with step size 휂푡 ≤ 2훼 ‖풙푡−풙∗ ‖2퐿2,lim푡→∞퐷휙 (풙∗,풙푡 ) = 0.Theorem 3.8 ([26]). Consider a two-player zero-sum game where the strategy space of each playerX푖 ⊂ R푑푖 is a convex, compact set. Assume that the game is 훽-smooth, and that the gradient operatorof the game is monotone. Then, if at each time step 푡, each player uses OMD with adaptive predictorM푡푖 ∈ 휕풙푖 푝푖 (풘푡 ) to update her strategy, and 휂푡 < 1훽 ,퐷휙 (풙∗,풘푡 ) ≤ 퐷휙 (풙∗,풘푡−1) − 12 (1−휂2푡 훽2)‖풙푡 −풘푡−1‖2.Unlike the previous results of this section, Mertikopoulos et al. study convergence when playerstrategies X1 ⊂ R푑1 ,X2 ⊂ R푑2 are convex and compact, and therefore a Nash is guaranteed to exist.Mertikopoulos et al. [26] study the class of games where the gradient operator is 훼-strongly monotone,which includes all games with an 훼-strongly concave-훼-strongly convex payoff. This is characterizedin the following Lemma.Lemma 3.1. Consider a two-player zero-sum game. Assume that 푝(풙1,풙2) is 훼-strongly concave-훼-strongly convex. Then v(풙) is 훼-strongly monotone.Mertikopoulos et al. [26] use the Bregman Divergence as a measure of convergence. Since theBregman Divergence is defined w.r.t to some function 푅 which is strongly convex in ‖·‖, then for apoint 풛, and a sequence of iterates 풙푡 ,lim푡→∞퐷푅 (풛,풙푡 ) = 0⇒ 풙푡 → 풛. (3.13)Therefore, Theorem 3.7 shows that in a class of games encompassing all games with 훼-stronglyconcave-훼-strongly convex and 퐿-Lipschitz payoffs, players using mirror descent to update theirstrategies converge to a Nash in last iterate. Theorem 3.8, shows that for a class of games whichincludes all 훽-smooth, concave-convex games, players using OMD with the adaptive predictorM푡푖 ∈ 휕풙푖 푝(풘푡−1푖 ), converges in last iterate to a Nash. The convergence in this scenario is faster thanwhat was shown in Theorem 3.7 — the Bregman divergence can be shown to decrease by a non-zeroconstant at each time step. Detailed proofs are provided in Section 3.3.3.3.3 Omitted proofs from Section 3.23.3.1 Omitted proofs from Section 3.2.1Theorem 3.2 ([24]). Consider an unconstrained two-player zero-sum game with payoff 푝(풙1,풙2) =풙>1퐶풙2. Assume 푑1 = 푑2 and that퐶 is full rank. Let 풙01 ∈X1,풙02 ∈X2, and assume that ‖풘01‖22+‖풘02‖22 ≤푟2. Then if each player updates her strategy according to EG with fixed step size 휂 =√휆min (퐶퐶>)2휆2max (퐶퐶>) , at16each time step 푡,‖풘푡1‖22 + ‖풘푡2‖22 ≤ 푟2 exp(− 푡4휆2min(퐶퐶>)휆2max(퐶퐶>)).Proof. In the bilinear game, the EG update is given by[풘푡+11풘푡+12]=[풘푡1풘푡2]+[0 휂퐶−휂퐶>] [풙푡+11풙푡+12]=[풘푡1풘푡2]+[0 휂퐶−휂퐶> 0] [퐼 휂퐶−휂퐶> 퐼] [풘푡1풘푡2]=[퐼 −휂2퐶퐶> 휂퐶−휂퐶> 퐼 −휂2퐶>퐶] [풘푡1풘푡2].Let 퐽 =[퐼 −휂2퐶퐶> 휂퐶−휂퐶> 퐼 −휂2퐶>퐶]. The singular values of 퐽 are given by the eigenvalues of thefollowing matrix퐽퐽> =[(퐼 −휂2퐶퐶>)2 +휂2퐶퐶> 00 (퐼 −휂2퐶>퐶)2 +휂2퐶>퐶].Since the block matrices on the diagonal are a sum of symmetric matrices, Lemma A.3 can be usedto upper bound their eigenvalues,휆max[(퐼 −휂2퐶퐶>)2 +휂2퐶퐶>] ≤ 1−휂2휆min(퐶퐶>) +휂4휆2max(퐶퐶>)≤ 1− 휆2min(퐶퐶>)4휆2max(퐶퐶>), (3.14)Since 퐽 commutes with its transpose, then퐶>퐶 will have the same singular values as퐶퐶>. Therefore,(3.14) is an upper bound on the eigenvalues of (퐼 −휂훾퐶>퐶)2 +휂2퐶>퐶,휆max[(퐼 −휂2퐶>퐶)2 +휂2퐶>퐶] ≤ 1− 휆2min(퐶퐶>)4휆2max(퐶퐶>),Applying Lemma A.4, the desired bound is achieved. 3.3.2 Omitted proofs from Section 3.2.2Theorem 3.4 ([24]). Consider an unconstrained two-player zero-sum game that is 훽-smooth, with apayoff that is twice differentiable and 훼-strongly concave-훼-strongly convex with 훼 > 0. Assumethere exists a Nash, 풙∗. Let 풙01 ∈ X1,풙02 ∈ X2, and assume that ‖풙01− 풙∗1‖22 + ‖풙02− 풙∗2‖22 ≤ 푟2. Then if17each player updates her strategy according to GA with fixed step size 휂 = 훼훽2, at each time step 푡,‖풙푡1− 풙∗1‖22 + ‖풙푡2− 풙∗2‖22 ≤(1− 훼훽2) 푡푟2.Proof. Let 풙(훾) = 훾풙푡 + (1−훾)풙∗. Then the GA update satisfies[풙푡+11 − 풙∗1풙푡+12 − 풙∗2]=[풙푡1− 풙∗1풙푡2− 풙∗2]+휂[∇풙1 푝(풙푡 )−∇풙2 푝(풙푡 )]=[풙푡1− 풙∗1풙푡2− 풙∗2]+휂∫ 10[∇2풙1 푝(풙(훾)) ∇2풙2,풙1 푝(풙(훾))−∇2풙1,풙2 푝(풙(훾)) −∇2풙2 푝(풙(훾))]푑풙 ·[풙푡1− 풙∗1풙푡2− 풙∗2]=∫ 10(퐼 +휂[∇2풙1 푝(풙(훾)) ∇2풙2,풙1 푝(풙(훾))−∇2풙1,풙2 푝(풙(훾)) −∇2풙2 푝(풙(훾))])푑풙 ·[풙푡1− 풙∗1풙푡2− 풙∗2].For simplicity denote [∇2풙1 푝(풙(훾)) ∇2풙2,풙1 푝(풙(훾))−∇2풙1,풙2 푝(풙(훾)) −∇2풙2 푝(풙(훾))]=[퐴 퐶−퐶> 퐵].Let 퐽 =[퐼 +휂퐴 휂퐶−휂퐶> 퐼 +휂퐵]. The singular values of 퐽 are the eigenvalues of 퐽퐽>,퐽퐽> =[(퐼 +휂퐴)2 +휂2퐶퐶> −휂2(퐴퐶 −퐶퐵)−휂2(퐶>퐴−퐵퐶>) (퐼 +휂퐵)2 +휂2퐶>퐶]= 퐼 +2휂[퐴 00 퐵]+휂2[퐴2 +퐶퐶> −퐴퐶 +퐶퐵−퐶>퐴+퐵퐶> 퐵2 +퐶>퐶].Condition (3.10) implies that the maximum eigenvalue of the second matrix is bounded above by −훼,and condition (3.12) states that the maximum eigenvalue of the last matrix is bounded above by 2훽2.Since this is a sum of symmetric matrices, by Lemma A.3,휆max[퐽퐽>] ≤ 1−2휂훼+휂2훽2.Setting 휂 = 훼훽2, by Lemma A.4,‖풙푡+1‖22 ≤(1− 훼2훽2)‖풙푡 − 풙∗‖22.Theorem 3.6 ([27]). Consider an unconstrained two-player zero-sum game that is 훽-smooth, with apayoff that is differentiable, 훼-strongly concave-훼-strongly convex with 훼 > 0. Assume there exists aNash 풙∗. Let 풙01 ∈ X1,풙02 ∈ X2, and assume that 풙01 = 풙11 and 풙02 = 풙12, and ‖풙01−풙∗1‖2+ ‖풙02−풙∗2‖2 ≤ 푟2.18Then if each player updates her strategy according to OGA with fixed step size 휂 = 14훽 , at each timestep 푡,‖풙푡+11 − 풙∗1‖2 + ‖풙푡+12 − 풙∗2‖2 ≤ 1024(1− 훼4훽) 푡훽2훼2푟2.Proof. Rearranging the OGA update and adding v(풙푡+1) to each side,휂(v(풙푡+1) −v(풙∗))= 풙푡 − 풙푡+1 +휂(v(풙푡 ) −v(풙푡+1))+휂(v(풙푡 ) −v(풙푡−1)).Squaring the above and applying Young’s inequality,휂2‖v(풙푡+1) −v(풙∗)‖2 ≤ 3‖풙푡+1− 풙푡 ‖2 +3휂2훽2‖풙푡+1− 풙푡 ‖2 +3휂2훽2‖풙푡 − 풙푡−1‖2.Since 푝(풙1,풙2) is 훼-strongly convex-훼-strongly concave, then by Lemma 3.1, v(풙) is 훼-stronglymonotone, i.e., ∀풙,풙′ ∈ X, 훼‖풙− 풙′‖ ≤ ‖v(풙) −v(풙′)‖. Using this fact and substituting 휂 = 14훽 ,훼216훽2‖풙푡+1− 풙∗‖2 ≤ 4max {‖풙푡+1− 풙푡 ‖2, ‖풙푡 − 풙푡−1‖2} . (3.15)For OGA, the update satisfies풙푡 +휂(v(풙푡 ) −v(풙푡−1)) = 풙푡−1 +휂(v(풙푡−1) −v(풙푡−2)) +휂v(풙푡 ).Subtracting 풙∗ from each side and squaring,풙푡 +휂(v(풙푡 ) −v(풙푡−1)) − 풙∗2=‖풙푡−1 +휂(v(풙푡−1) −v(풙푡−2)) − 풙∗‖2 +휂2‖v(풙푡 )‖2 +2휂〈v(풙푡 ),풙푡−1 +휂(v(풙푡−1) −v(풙푡−2)) − 풙∗〉=‖풙푡−1 +휂(v(풙푡−1) −v(풙푡−2)) − 풙∗‖2 +휂2‖v(풙푡 )‖2−2휂2〈v(풙푡 ),v(풙푡−1)〉 +2휂〈v(풙푡 ),풙푡 − 풙∗〉≤‖풙푡−1−휂(v(풙푡−1) −v(풙푡−2)) − 풙∗‖2−휂2‖v(풙푡−1)‖2 +휂2훽2‖풙푡 − 풙푡−1‖2 +2휂〈v(풙푡 ),풙푡 − 풙∗〉,(3.16)where the last line is due to the 훽-Lipschitzness of v(풙). By the optimality of 풙∗, and due to v(풙)being 훼-strongly monotone,〈v(풙푡 ),풙∗− 풙푡〉 ≤ 〈v(풙푡 ) −v(풙∗),풙∗− 풙푡〉 ≤ −훼‖풙푡 − 풙∗‖2. (3.17)Furthermore, using the Young’s inequality,‖풙푡 − 풙∗‖2 ≤ 12‖풙푡−1 +휂(v(풙푡−1) +v(풙푡−2)) − 풙∗‖ −휂2‖v(풙푡−1)‖2. (3.18)19Plugging (3.17) and (3.18) into (3.16),‖풙푡 +휂(v(풙푡 ) −v(풙푡−1)) − 풙∗‖2≤(1−휂훼)‖풙푡−1 +휂(v(풙푡−1) −v(풙푡−2)) − 풙∗‖2 +휂2훽2‖풙푡 − 풙푡−1‖2−휂2(1−2휂훼)‖v(풙푡−1)‖2.Expanding ‖풙푡 − 풙푡−1‖2,‖풙푡 − 풙푡−1‖2 = 휂2‖v(풙푡−2) −2v(풙푡−1)‖2≤ 2휂2‖v(풙푡−1)‖2 +2휂2훽2‖풙푡−1− 풙푡−2‖2= 4휂2‖v(풙푡−1)‖2 +4휂2훽2‖풙푡−1− 풙푡−2‖2− ‖풙푡 − 풙푡−1‖2.Plugging the above back in,‖풙푡 +휂(v(풙푡 ) −v(풙푡−1)) − 풙∗‖2 +휂2훽2‖풙푡 − 풙푡−1‖2≤(1−휂훼)‖풙푡−1 +휂(v(풙푡−1) −v(풙푡−2)) − 풙∗‖ +4휂4훽4‖풙푡−1− 풙푡−2‖2−휂2(1−2휂훼−4휂2훽2)‖v(풙푡−1)‖2.For 휂 ≤ 14훽 , 1−2휂훼−4휂2훽2 > 0, and 4휂2훽2 ≤ (1−휂훼). Therefore,‖풙푡 +휂(v(풙푡 ) −v(풙푡−1)) − 풙∗‖2 +휂2훽2‖풙푡 − 풙푡−1‖2≤(1−휂훼) (‖풙푡−1 +휂(v(풙푡−1) −v(풙푡−2)) − 풙∗‖2 +휂2훽2‖풙푡−1− 풙푡−2‖2)≤(1−휂훼)푡−1‖풙0− 풙∗‖2.For 휂 = 14훽 ,‖풙푡 − 풙푡−1‖2 ≤ 16(1− 훼4훽) 푡−1‖풙0− 풙∗‖2.Plugging back into (3.15),‖풙푡+1− 풙∗‖2 ≤ 1024(1− 훼4훽) 푡훽2훼2푟2.3.3.3 Omitted proofs from Section 3.2.3Lemma 3.1. Consider a two-player zero-sum game. Assume that 푝(풙1,풙2) is 훼-strongly concave-훼-strongly convex. Then v(풙) is 훼-strongly monotone.20Proof. By the strong concavity of 푝(풙1,풙2) in 풙1, for 풖1 ∈ 휕풙1 푝(풙), 풖′1 ∈ 휕풙1 푝(풙′),푝(풙′1,풙2) ≤ 푝(풙) + 〈풖1,풙′1− 풙1〉 −훼2‖풙1− 풙′1‖2푝(풙1,풙′2) ≤ 푝(풙′) + 〈풖′1,풙1− 풙′1〉 −훼2‖풙1− 풙′1‖2,and by the strong convexity of 푝(풙1,풙2) in 풙2, for 풖2 ∈ −휕풙2 푝(풙), 풖′2 ∈ −휕풙2 푝(풙′),푝(풙1,풙′2) ≥ 푝(풙) − 〈풖2,풙′2− 풙2〉 +훼2‖풙2− 풙′2‖2푝(풙′1,풙2) ≥ 푝(풙′) − 〈풖′2,풙2− 풙′2〉 +훼2‖풙2− 풙′2‖2.Combining the above inequalities yields〈풖′1−풖1,풙1− 풙′1〉 + 〈풖′2−풖2,풙2− 풙′2〉 ≥ 훼(‖풙1− 풙′1‖2 + ‖풙2− 풙′2‖2),which is the definition of 훼-strong monotonicity. Theorem 3.7 ([26]). Consider a two-player zero-sum game where the strategy space of each playerX푖 ⊂ R푑푖 is a convex, compact set. Assume that the payoff is 퐿-Lipschitz, that the gradient operatorof the game is 훼-strongly monotone with 훼 > 0, and that D휙 (풙∗,풙0) is finite. Then, if at each timestep 푡, each player uses MD to update her strategy with step size 휂푡 ≤ 2훼 ‖풙푡−풙∗ ‖2퐿2,lim푡→∞퐷휙 (풙∗,풙푡 ) = 0.Proof. By the Bregman triangle equality,퐷휙 (풙∗,풙푡+1) = 퐷휙 (풙∗,풙푡 ) −퐷휙 (풙푡+1,풙푡 ) + 〈∇휙(풙푡+1) −∇휙(풙푡 ),풙푡+1− 풙∗〉.By first order optimality, for 풖푡1 ∈ 휕풙1 푝(풙푡 ),〈풖푡1−∇휙1(풙푡+1) +∇휙1(풙푡 ),풙∗− 풙푡〉 ≤ 0, (3.19)and likewise for 풖푡2 ∈ −휕풙2 푝(풙푡 ),〈풖푡2−∇휙2(풙푡+1) +∇휙2(풙푡 ),풙∗− 풙푡〉 ≤ 0. (3.20)Combining (3.19) and (3.20) shows that〈∇휙(풙푡+1) −∇휙(풙푡 ),풙푡+1− 풙∗〉 ≤ 〈v(풙푡 ),풙푡+1− 풙∗〉. (3.21)21Plugging this back into the original equation,퐷휙 (풙∗,풙푡+1) ≤ 퐷휙 (풙∗,풙푡 ) −퐷휙 (풙푡+1,풙푡 ) +휂푡 〈v(풙푡 ),풙푡+1− 풙∗〉= 퐷휙 (풙∗,풙푡 ) −퐷휙 (풙푡+1,풙푡 ) +휂푡(〈v(풙푡 ),풙푡 − 풙∗〉 + 〈v(풙푡 ),풙푡+1− 풙푡〉).By Claim A.1 we have the for any 휌 > 0,〈v(풙푡 ),풙푡+1− 풙푡〉 ≤ ‖v(풙푡 )‖∗‖풙푡+1− 풙푡 ‖ ≤ 12휌 ‖v(풙푡 )‖2∗ +휌2‖풙푡+1− 풙푡 ‖2.Plugging in 휌 = 1/휂푡 , and using the 퐿-Lipschitzness of 푝(풙1,풙2),퐷휙 (풙∗,풙푡+1) ≤ 퐷휙 (풙∗,풙푡 ) −퐷휙 (풙푡+1,풙푡 ) +휂푡 〈v(풙푡 ),풙푡 − 풙∗〉 + 휂2푡 퐿22+ 12‖풙푡+1− 풙푡 ‖2≤ 퐷휙 (풙∗,풙푡 ) −휂푡훼‖풙푡 − 풙∗‖2 + 휂2푡 퐿22,where the last line is due to the훼-strongmonotonicity of v, and the fact that 12 ‖풙푡+1−풙∗‖2 ≤D휙 (풙∗,풙푡 )(this is due to the 1-strong convexity of 휙). Setting 휂푡 < 2훼 ‖풙푡−풙∗ ‖2퐿2, the Bregman divergence isstrictly decreasing per iteration, which gives the result. Theorem 3.8 ([26]). Consider a two-player zero-sum game where the strategy space of each playerX푖 ⊂ R푑푖 is a convex, compact set. Assume that the game is 훽-smooth, and that the gradient operatorof the game is monotone. Then, if at each time step 푡, each player uses OMD with adaptive predictorM푡푖 ∈ 휕풙푖 푝푖 (풘푡 ) to update her strategy, and 휂푡 < 1훽 ,퐷휙 (풙∗,풘푡 ) ≤ 퐷휙 (풙∗,풘푡−1) − 12 (1−휂2푡 훽2)‖풙푡 −풘푡−1‖2.Proof. Similarly to how (3.21) was derived in the proof of Theorem 3.7, by the Bregman triangleequality and first order optimality,D휙 (풙∗,풘푡 ) ≤ D휙 (풙∗,풘푡−1) −D휙 (풘푡 ,풘푡−1) +휂푡 〈v(풙푡 ),풘푡 − 풙∗〉 (3.22)D휙 (풘푡 ,풙푡 ) ≤ D휙 (풘푡 ,풘푡−1) −D휙 (풙푡 ,풘푡−1) +휂푡 〈v(풘푡−1),풙푡 −풘푡〉. (3.23)Summing (3.22) and (3.23),D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1) ≤ −D휙 (풘푡 ,풙푡 ) −D휙 (풙푡 ,풘푡−1)+휂푡(〈v(풙푡 ),풘푡 − 풙∗〉 + 〈v(풘푡−1),풙푡 −풘푡〉)=−D휙 (풘푡 ,풙푡 ) −D휙 (풙푡 ,풘푡−1) (3.24)+휂푡(〈v(풙푡 ),풙푡 − 풙∗〉 + 〈v(풘푡−1) −v(풙푡 ),풙푡 −풘푡〉)22By Claim A.1, with 휌 = 휂푡 ,〈v(풘푡−1) −v(풙푡 ),풙푡 −풘푡〉 ≤ 휂푡2‖v(풘푡−1) −v(풙푡 )‖2∗ +12휂푡‖풘푡 − 풙푡 ‖2≤ 휂푡 훽22‖풘푡−1− 풙푡 ‖2 + 12휂푡‖풘푡 − 풙푡 ‖2, (3.25)where the last line is due to the 훽-Lipschitzness of v(풙). Using the 1-strong convexity of 휙, themontonicity of v(풙), and plugging (3.25) into (3.24),D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1) ≤ −12(1−휂2푡 훽2)‖풙푡 −풘푡−1‖2.Setting 휂푡 < 1훽 ensures that the decrease is nonnegative. 23Chapter 4n-Player GamesAlthough GAN is typically formulated as a two-player game, many recently proposed extensionsof GAN go beyond the two-player zero-sum framework, either to address challenges faced by theoriginal GAN, or to allow it to generalize to novel learning tasks. It is well known that two-playerzero-sum games have many properties not extensible to games with more players or non zero-sumpayoffs.In this section, we motivate and introduce the formalism for studying last iterate convergence in asetting with greater than two agents. In Section 4.1 we provide two architectures which extend theoriginal GAN game by adding more agents, and are not amenable to standard convergence analyses.In Section 4.2 we describe our proposed model for studying last-iterate convergence in a setting withmore than two agents. Finally, in Section 4.3 we describe other work studying last-iterate convergencein a different, but related setting.4.1 Extensions of GAN with additional agents4.1.1 VAE/GANVariational autoencoders (VAE) are a class of generative models mainly used for image generation.VAEs are composed of a decoder 푉 :Z→D, which maps points in the latent space to the data space,and an encoder 퐸 :D →Z, which does the opposite. In order to train a VAE, at each iteration oftraining, an input 풙 is fed to the encoder and mapped toZ, which captures some lower dimensionalencoding of D. The decoder is then given the encoding of 퐸 (풙), and maps it back to D. VAEs aretypically trained with an expert-chosen error operating on the individuals pixels of the reconstructedimage.Larsen et al. [23] propose that rather than hand-engineering a metric for a given problem, bycombining the VAE and GAN architectures, a loss function for a given problemwould be automaticallylearned by the generative model, and more complex rules than simple trends in the pixels could beconstructed. Thus, in VAE/GAN, rather than directly sampling from a latent space Z to producethe output of the generator, 풛 is obtained by first passing a point 풙 through the encoder, producing24풛 = 퐸 (풙). 퐸 (풙) is then fed through the decoder, which takes on the role of the generator in theoriginal GAN formulation.In order to facilitate training in VAE/GAN, Larsen et al. [23] introduce a Gaussian observationmodel for the ℓ푡ℎ layer of the discriminator. Rather than training VAE/GAN as a two-player zero-sumgame, Larsen et al. [23] define different utilities for each agents involved in training. Letting 퐷ℓ (풙)be the representation of 풙 at the ℓ푡ℎ hidden layer of 퐷, the payoff of agents is given by푝퐸 (퐸,퐺,퐷) = E풙1,풙2∼푝D (풙)[퐷ℓ (퐺 (퐸 (풙1))) −퐷ℓ (풙2)22] (4.1)푝퐷 (퐸,퐺,퐷) = E풙∼푝D (풙) [log(퐷 (풙)) + log(1−퐷 (퐺 (퐸 (풙))))] (4.2)푝퐺 (퐸,퐺,퐷) = 푝퐸 (퐸,퐺,퐷) − 푝퐷 (퐸,퐺,퐷). (4.3)The above is clearly not a two-player zero-sum game.4.1.2 Triple-GANIn a semi-supervised learning (SSL) task, the goal is to produce an accurate classifier while havingaccess to only a few labelled examples. Consider an SSL problem where the goal is to produce aclassifier over 푐 classes. A straightforward application of GAN to this task as observed by Odena[28] and Salimans et al. [29], would be to allow the discriminator to label samples as coming fromone of 푐 classes or as being fake. A problem with the proposed architecture, is that the discriminatoralone is rewarded for disentangling class representations.Chongxuan et al. [9] propose Triple-GAN, a model which attempts to overcome this problem byseparating the task of classification from discrimination. Prior to formulating Triple-GAN, in additionto the usual spaces D,Z, let Y be the label-space of a given SSL problem, and let 푝푆푆퐿 (풙, 푦) bethe joint probability of samples with their corresponding labels. The components of Triple-GANare as follows: A classifier 퐶 :D →Y which models the conditional distribution of labels givensamples; a class-conditional generator 퐺 :Z×Y which models the reverse; lastly, a discriminator퐷 :D×Y → [0,1], which models whether a given sample-label pair 풙, 푦 comes from the true jointdistribution.Chongxuan et al. [9] assume that samples from the marginal distributions — 푝D (풙), 푝Y (푦) canbe easily obtained. Training proceeds as follows: a sample 풙 ∼ 푝D (풙) is drawn, and fed through 퐶.Similarly, a sample 푦 ∼ 푝Y (푦) is drawn, alongwith a latent vector 풛 ∼ 푝Z (풛), and fed through퐺. Lastly,a sample-label pair, (풙, 푦), is drawn from 푝푆푆퐿 (풙, 푦). The discriminator is rewarded for discriminatingbetween the two fake pairs and the one real pair. On top of an adversarial loss, Chongxuan et al. [9]use the standard cross-entropy loss to train 퐶, 푅퐿 = E(풙,푦)∼푃푆푆퐿 (풙,푦) [− log(퐶푦 (풙))]. The utility ofagents in Triple-GAN is given by푝(퐶,퐺,퐷) =E(풙,푦)∼푝푆푆퐿 (풙,푦) [log(퐷 (풙, 푦))] +훼E풙∼푝D (풙) [log(1−퐷 (풙,퐶 (풙)))]+ (1−훼)E풛∼푝Z (풛) ,푦∼푝Y (푦) [log(1−퐷 (퐺 (풛, 푦), 푦)] +푅퐿 ,25where 훼 > 0 is parameter controlling the emphasis which the generator places on discriminatingthe samples coming from the classifier or the samples coming from the generator. The above is atwo-player zero-sum formulation, as the classifier and generator can both be seen as componentsof a single minimizing agent. However, in SSL, the label information is insufficient for training퐶. Therefore, the actual loss used by the classifier during training includes a pseudo-classificationloss, 푅푃 = E풛∼푃Z (풛) ,푦∼푃Y (푦) [− log(퐶 (퐺 (풛, 푦)))]. Since only the classifier is trained via this loss, thisbreaks the two-player zero-sum formulation of Triple-GAN.4.2 Network zero-sum gamesThe above examples are just a few of the many extensions of GAN not captured by the standardtwo-player zero-sum formulation. In order to analyze convergence for these sorts of frameworks,we need a game-theoretic model that can accommodate additional agents. At the same time, it isknown that it is hard to compute a Nash even for a two-person nonzero-sum game, and consequentlyfor three-player zero-sum games [12]. Thus, we must choose a simple enough formalism such thatthe solution concepts we care about are still tractable, but the model is expressive enough to captureexisting GAN extensions. The framework, we believe, that satisfies these criteria, is network zero-sumgames (NZSGs), a class of games first introduced and studied by Cai et al. [7]. We present the NZSGframework and its properties in the remainder of the section.An NZSG is structured by a graph, where each node corresponds to a player, and along each edgea game is played between its two node players. A player chooses one strategy to be used in all thegames in which she is engaged; the sum of all players’ payoffs is always zero. Since players cannotchoose different strategies for different games, an NZSG is not a simple parallelization of multipletwo-player zero-sum games. Formally:Definition 4.1 ([7]). A network game consists of the following:• a finite set 푉 = {1, ..., 푛} of players, and a set 퐸 of edges which are unordered pairs of players[푖, 푗], 푖 ≠ 푗 ;• for each player 푖 ∈ 푉 , a finite set of strategies S푖;• for each edge [푖, 푗] ∈ 퐸 , a two-person game (푝푖 푗 , 푝 푗푖), where 푝푖 푗 : S푖 ×S 푗 → R, and 푝 푗푖 :S 푗 ×S푖→ R.Given a strategy profile 풔 = (푠1, ..., 푠푛) ∈∏ 푗∈푉 S 푗 , player 푖’s payoff is 푝푖 (풔)B∑[푖, 푗 ] ∈퐸 푝푖 푗 (푠푖 , 푠 푗).A network game is a network zero-sum game (NZSG) if for all strategy profiles 풔 ∈∏ 푗∈푉 S 푗 ,∑푖∈푉 푝푖 (풔) = 0.Cai et al. [7] show that NZSGs with linear payoffs preserve properties of two-player zero-sumgames. Notably, they show that a mixed Nash in a NZSG can be computed by a linear program. Thevariables of the linear program are the mixed strategies of players, i.e., for each player 푖 ∈ 푉 , and every푠 ∈ S푖 there is a variable 푥푖,푠. The constraints of the linear program are ∀푖 ∈ 푉,∀푠 ∈ S푖 , 푥푖,푠 > 0, and26∀푖 ∈ 푉,∑푠∈S푖 푥푖,푠 = 1. In order to make notation more concise, if a mixed strategy profile 풙 satisfiesthese conditions, this is written as 풙 ∈ Δ.The payoff of each player, 푝푖 , can be extended to include mixed strategies by taking the expectation,푝푖 (풙) = E푠푘∼풙푘∑[푖, 푗 ] ∈퐸푝푖 푗 (푠푖 , 푠 푗) =∑[푖, 푗 ] ∈퐸∑푠푖 ∈S푖∑푠 푗 ∈S 푗푝푖 푗 (푠푖 , 푠 푗)푥푖,푠푖푥 푗 ,푠 푗 . (4.4)Let 풙−푖 denote the mixed strategy profile of all players except for that of player 푖. To simplifynotation, when a mixed strategy consists of putting all the probability mass on a single pure strategy,i.e., 푥푖,푠 = 1, the mixed strategy profile may be written as (푠,풙−푖).Cai et al. [7] seek to write a linear program to compute a mixed Nash in an NZSG. A Nash in anNZSG is defined similarly to two-player zero-sum game.Definition 4.2 (Mixed Nash Equillibrium). A mixed strategy profile 풙∗ is aMixed Nash equillibriumfor an NZSG if for each player 푖, for any strategy 푠 ∈ S푖 , 푝푖 (풙∗) ≥ 푝푖 (푠,풙∗−푖).Cai et al. [7] propose the following linear program to compute a Nash in a NZSG,min풚,푤∑푖∈푉푤푖 (4.5)subject to 푤푖 ≥ 푝푖 (푠, 풚−푖),∀푖 ∈ 푉, 푠 ∈ S푖풚 ∈ Δ.They show the following:Theorem 4.1 ([7]). Consider a network zero-sum game. If (풚,풘) is a solution to (4.5), then 풚 is aNash equillibrium of the game. Conversely, if 풚 is a Nash equillibrium of the game, then there existsa 풘 such that (풚,풘) is an optimal solution to (4.5).Proof. Since 푝푖 (풙푖 , 풚−푖) is linear in 풙푖 ,∑푖∈푉max푠∈S푖푝푖 (푠, 풚−푖) =max풙∈Δ∑푖∈푉푝푖 (풙푖 , 풚−푖). (4.6)Using the zero-sum property, (4.6), and the constraint 푤푖 ≥ max푠∈S푖 푝푖 (푠,풙−푖),∑푖∈푉푤푖 ≥∑푖∈푉max푠∈S푖푝푖 (푠, 풚−푖) =max풙∈Δ∑푖∈푉푝푖 (풙푖 , 풚−푖) ≥∑푖∈푉푝푖 (풚푖 , 풚−푖) = 0. (4.7)Next, the dual of (4.5) is constructed. Consider a square matrix 푅 with∑푖 |S푖 | rows and columns.The rows and columns of 푅 are indexed by pairs, (푖 : 푠), ( 푗 : 푟) for 푖, 푗 ∈ 푉 , 푠 ∈ S푖 , 푟 ∈ S 푗 , where푅(푖:푠) , ( 푗:푟 ) = 푝푖 푗 (푠푖 , 푠 푗) if [푖, 푗] ∈ 퐸 , and 0 otherwise. We have that 푝푖 (푠, 풚−푖) corresponds to theentry (푅풚) (푖:푠) , and therefore the constraint of (4.5), 푤푖 ≥ 푝푖 (푠, 풚−푖) can be written as 푤푖 ≥ (푅풚) (푖:푠) .27We have the following LP,min풛,푣∑푗∈푉푣 푗 (4.8)subject to 푣 푗 ≤ (푅>푧) ( 푗:푟 ) ,∀ 푗 ∈ 푉,푟 ∈ S 푗풛 ∈ Δ.Similar to (4.5), a feasible solution of (4.8) satisfies∑푗∈푉푣 푗 ≤∑푗∈푉min푟 ∈푆 푗(푅>풛) ( 푗:푟 ) =min풙∈Δ풙>푅>풛 ≤ 풛>푅>풛 = 0. (4.9)Thus, the optimal value of (4.5) is both upper and lower bounded by 0, and hence any Nashequillibrium attains the optimal value. For the forward direction, consider an optimal solution of(4.5), (풘, 풚). Since the objective value is ∑푖∈푉 푤푖 = 0, all of the inequalities of (4.7) hold withequality, and thus 풚 is a Nash. Theorem 4.1 shows that the mixed Nash of an NZSG are tractable, as they can be computed inpolynomial time by a linear program. Cai et al. [7] also show that the marginal distributions of anycoarse correlated equillibrium comprise a mixed Nash equillibrium. This has the important upshotthat players engaged in a repeated game can arrive at a mixed Nash in a distributed manner — by eachemploying a no-regret learning algorithm to determine their mixed strategy at each time step. Whenconsidering the more general class of concave NZSGs, this will become an important phenomenon,as a mixed Nash can no longer be computed via a linear program.Definition 4.3 (Coarse Correlated Equillibrium). Let S =∏푖∈푉 S푖 . Let 풛 ∈ Δ(S). Then 풛 is a coarsecorrelated equillibrium iff for every player 푖 and strategy 푟 ∈ S푖 ,E풔∼풛[∑풔∈S푝푖 (풔)]≥ E풔∼풛[∑풔∈S푝푖 (푟, 풔−푖)].Theorem 4.2 ([7]). Let 풛 ∈ Δ(S) be a coarse correlated equillibrium. Consider 풙, where for eachplayer 푖, 풙푖 is the marginal distribution with entries 푥푖,푟 =∑풔−푖 ∈S−푖 풛 (푟 ,풔−푖) ,∀푟 ∈ S푖 , where 풛 (푟 ,풔−푖) isthe probability of the strategy profile (푟, 풔−푖) in 풛. Then 풙 is a Nash equillibrium.Proof. For each 푖 ∈ 푉 , 푝푖 is linear in 풙−푖 , and thus ∀푖 ∈ 푉,∀푟 ∈ S푖 we have푝푖 (푟,풙−푖) = E풔∼풛 [푝푖 (푟, 풔−푖)] .Let 푤∗푖 = E풔∼풛 [푝푖 (풔)]. Since 풛 is a coarse correlated equillbrium, 푤∗푖 ≥ 푝푖 (푟,풙−푖) for any 푟 ∈ S푖.Furthermore,∑푖∈푉 푤∗푖 = 0 since the game is zero-sum, and hence (풙,풘∗) is an optimal solution to(4.5), and by Theorem 4.1, 풙 is a Nash. 28Corollary 4.1. Consider a repeated NZSG. At each round, player 푖 plays a strategy 푠푡푖 according to풙푡푖 . Assume that each player uses a no-regret algorithm to determine her strategy at each time step,suffering at most 휖 (푇) regret over the first 푇 time steps. Then the strategy profile 풙¯푇 = (풙¯푇1 , . . . , 풙¯푇푛 )constitutes a 푛휖 (푇 )푇 -approximate mixed Nash equillibrium.Proof. Consider the following correlating mechanism, 풛 ∈ Δ(S): choose a time 푡 uniformly atrandom. Each player plays 푠푡푖 according to 풙푡푖 . Since each player is using a no-regret algorithm, forany 푟 ∈ S푖 ,E풔∼풛 [푝푖 (풔)] =푇∑푡=11푇푝푖 (풙푡 ) ≥ 1푇(푇∑푡=1푝푖 (푟,풙푡−푖) − 휖 (푇))= E풔∼풛 [푝푖 (푟, 풔−푖)] − 휖 (푇)푇.Summing over the players,E풔∼풛[∑푖∈푉푝푖 (풔)]≥ E풔∼풛[∑푖∈푉푝푖 (푟, 풔−푖)]− 푛휖 (푇)푇.By Theorem 4.2, the marginal distributions of 풛, i.e., the 풙¯푇푖 comprise a푛휖 (푇 )푇 -approximate mixedNash. Furthermore, notice that since 휖 (푇) ∈ 표(푇), lim푇→∞ 푛휖 (푇 )푇 = 0, i.e., as the time horizonstretches to infinity, the mixed strategy profile of the time average of players’ mixed strategiesconverges to a mixed Nash. 4.3 Last iterate convergenceOne of the few works to study last iterate convergence in a framework of more than two agents is thatof Azizian et al. [2]. Similar to the work of Mertikopoulos et al. [26] for two-player zero-sum games,the authors study convergence in games where the gradient operator is 훼-strongly monotone. Likemuch of the work discussed in Section 3.2, their analysis is inspired by GANs, and thus they analyzegradient-based algorithms in the setting where players’ strategies are unconstrained.Azizian et al. [2] show that when players use variants of OMD — EG or OGA, they convergeexponentially fast to a Nash in the class of games that are 훽-smooth with an 훼-strongly monotonegradient operator.Theorem 4.3 ([2]). Consider an unconstrained game that is 훽-smooth, the gradient operator is훼-strongly monotone, and ∀풙,풙′, ‖v(풙) −v(풙′)‖2 ≥ 훾‖풙− 풙′‖2 for 훼 ≥ 0, 훾 > 0. Then if each playeruses 퐸퐺 to update her strategy with fixed step size 휂 ≤ 12훽 , at each time step 푡,‖풘푡 − 풙∗‖22 ≤(1−휂훼− 716휂2훾2) 푡‖풘0− 풙∗‖22.Theorem 4.4 ([2]). Consider an unconstrained game that is 훽-smooth, the gradient operator is훼-strongly monotone, and that ∀풙,풙′, ‖v(풙) −v(풙′)‖2 ≥ 훾‖풙− 풙′‖2 for 훼 ≥ 0, 훾 > 0. Then if each29player uses 푂퐺퐴 to update her strategy, with the fixed step size 휂 ≤ 14훽 , at each time step 푡,‖풙푡 − 풙∗‖22 ≤(1−휂훼− 18휂2훾2) 푡‖풙0− 풙∗‖22.The class of games with an 훼-strongly monotone gradient operator is quite general. Similar to thetwo-player setting, later in this thesis we show that in fact, any NZSG with concave payoffs belongsto this class of games.Part of the goal of the analysis of Azizian et al. [2] is to provide a unified analysis of bothgames with linear payoffs, and 훽-smooth games with 훼-strongly concave payoffs. Recall that forthe linear two-player zero-sum game, the payoff was given by 푝(풙1,풙2) = 풙>1퐶풙2. In such a game,it is necessary that the minimum singular value of the 퐶 was strictly larger than 0, otherwise theconvergence rates of Theorem 3.2, and Theorem 3.3 would be meaningless. Assume that this is true.i.e., that 휎min(퐶) ≥ 훾 for some 훾 > 0. This is equivalent to the assumption that the minimum singularvalue of the derivative of the gradient operator is lower bounded by 훾, i.e.,휎min(∇v(풙)) = 휎min([∇2풙1 푝(풙1,풙2) ∇2풙2,풙1 푝(풙1,풙2)−∇2풙1,풙2 푝(풙1,풙2) −∇2풙2 푝(풙1,풙2)])(4.10)= 휎min([퐶 0푑1×푑20푑2×푑1 −퐶>])≥ 훾.Condition (4.10) can be written as a first-order characterization,∀풙,풙′ ∈ X, ‖v(풙) −v(풙′)‖2 ≥ 훾‖풙− 풙′‖2. (4.11)Thus Azizian’s analysis provides convergence rates for both 훽-smooth games with an 훼-stronglymonotone gradient operator, as well as games with linear payoffs, when the smallest singular value of∇v(풙) is bounded below by a nonzero 훾.The proof of Azizian et al. [2] is simliar to the proofs of Mokhtari et al. [27] for 훽-smooth gameswith 훼-strongly concave-훼-strongly convex payoffs. The authors use the sum of the squared distancesas a Lyapunov function, showing that it decreases by a multiplicative constant at each time step. Afull proof of Theorem 4.3 is provided in Section 4.4.4.4 Omitted proofs from Section 4.3Theorem 4.3 ([2]). Consider an unconstrained game that is 훽-smooth, the gradient operator is훼-strongly monotone, and ∀풙,풙′, ‖v(풙) −v(풙′)‖2 ≥ 훾‖풙− 풙′‖2 for 훼 ≥ 0, 훾 > 0. Then if each player30uses 퐸퐺 to update her strategy with fixed step size 휂 ≤ 12훽 , at each time step 푡,‖풘푡 − 풙∗‖22 ≤(1−휂훼− 716휂2훾2) 푡‖풘0− 풙∗‖22.Proof. We expand ‖풘푡+1− 풙∗‖2 and ‖풙푡+1−풘푡+1‖2,‖풘푡+1− 풙∗‖2 = ‖풘푡 − 풙∗‖2 +2휂〈v(풙푡+1),풘푡+1− 풙∗〉 − ‖풘푡+1−풘푡 ‖2 (4.12)‖풙푡+1−풘푡+1‖2 = ‖풘푡 −풘푡+1‖2 +2휂〈v(풘푡 ),풙푡+1−풘푡+1〉 − ‖풙푡+1−풘푡 ‖2. (4.13)Using the fact that v(풙∗) = 0,〈v(풙푡+1),풘푡+1− 풙∗〉 + 〈v(풘푡 ),풙푡+1−풘푡+1〉=〈v(풙푡+1) −v(풙∗),풙푡+1− 풙∗〉 + 〈v(풘푡 ) −v(풙푡+1),풙푡+1−풘푡+1〉≤−훼‖풙푡+1 + 풙∗‖2− ‖v(풘푡 ) −v(풙푡+1)‖‖풘푡 −풘푡+1‖≤−훼‖풙푡+1− 풙∗‖2 + (훽2‖풘푡 − 풙푡+1‖2 + ‖풙푡+1−풘푡+1‖2), (4.14)where the second to last line is due to the 훼-strong monotonicity of v, and in the last line we use thesmoothness of the game, and Young’s inequality. Summing (4.12) and (4.13), and plugging (4.14) in,we get‖풘푡+1− 풙∗‖ ≤ ‖풘푡 − 풙∗‖2−2휂훼‖풙푡+1− 풙∗‖2 + (휂2훽2−1)‖풘푡 − 풙푡+1‖2.Using Young’s inequality,2‖풙푡+1− 풙∗‖2 ≥ ‖풘푡 − 풙∗‖2−2‖풘푡 − 풙푡+1‖2.Plugging this back in,‖풘푡+1− 풙∗‖2 ≤ (1−휂훼)‖풘푡 − 풙∗‖2 + (휂2훽2 +2휂훼−1)‖풘푡 − 풙푡+1‖2.For 휂 ≤ 12훽 , 휂2훽2 +2휂훼−1 ≤ − 716 ,‖풘푡+1− 풙∗‖2 ≤ (1−휂훼)‖풘푡 − 풙∗‖2− 716‖풘푡 − 풙푡+1‖2= (1−휂훼)‖풘푡 − 풙∗‖2− 716휂2‖v(풘푡 ) −v(풙∗)‖2≤ (1−휂훼− 716휂2훾2)‖풘푡 − 풙∗‖2.31Chapter 5Network Zero-Sum GamesIn Chapter 4, we presented the class of network zero-sum games, and saw that it retain variousdesirable properties of two-player zero-sum games. In particular, in a linear game where players playmixed strategies over the simplex, a Nash of the game can be computed by a linear program. Thetractability of Nash in NZSGs suggests that other desirable properties of two-player zero-sum gamesmay extend to this setting. In the following chapter, we show that many of the last iterate convergenceresults for two-player zero-sum games carry over to NZSGs. In Section 5.1 we extend the definitionof NZSGs to games with concave payoffs and continuous strategy spaces. We then show that in arepeated concave NZSG, a Nash can be arrived at in a distributed manner when players update theirstrategies according to a no-regret learning algorithm. As our main result, in Section 5.2, we analyzelast iterate convergence for players using gradient-based algorithms in linear games, 훽-smooth gameswith 훼-strongly concave payoffs, and games with a monotone gradient operator. In each setting weachieve convergence rates which are comparable to the two-player zero-sum setting.5.1 Average iterate convergenceIn this section we extend network zero-sum games as defined by Cai et al. [7] to allow continuousaction spaces. We then show that in games with concave payoff functions, an equilibrium can bearrived at in a distributed manner when each player uses a no-regret learning rule.Definition 5.1. A network game consists of the following:• a finite set 푉 = {1, ..., 푛} of players, and a set 퐸 of edges which are unordered pairs of players[푖, 푗], 푖 ≠ 푗 ;• for each player 푖 ∈ 푉 , a convex set X푖 ⊆ R푑푖 , the strategy set for player 푖;• for each edge [푖, 푗] ∈ 퐸 , a two-person game (푝푖 푗 , 푝 푗푖), where 푝푖 푗 : X푖 ×X푗 → R, and 푝 푗푖 :X푗 ×X푖→ R.Given a strategy profile 풙 = (풙1, ...,풙푛) ∈ X, player 푖’s payoff is 푝푖 (풙) B ∑[푖, 푗 ] ∈퐸 푝푖 푗 (풙푖 ,풙 푗).A network game is a network zero-sum game (NZSG) if for all 풙 ∈ X, ∑푖∈푉 푝푖 (풙) = 0.32Two-player zero-sum games are special cases of NZSGs, where 푉 has two nodes, connected byone edge. In a concave NZSG, each 푝푖 (풙) is concave in 풙푖 .Definition 5.2 (Nash equillibrium). A strategy profile 풙∗ is a Nash equillibrium for an NZSG if foreach player 푖, for any strategy 풙푖 ∈ X푖 , 푝푖 (풙∗) ≥ 푝푖 (풙푖 ,풙∗−푖).Similar to two-player zero-sum games, it can be shown via a fixed point argument that, in aconcave NZSG where each player’s strategy space X푖 is convex and compact, a Nash equilibriumalways exists [25].Cai et al. [7] prove that in an NZSG where players play mixed strategies over finite action spaces,a mixed Nash equillibrium can be computed by a linear program. They also show that for a coarsecorrelated Nash, the marginal distributions of each player’s strategy form a Nash equillibrium. Acorollary of this fact is that players can arrive at an 표(푇)-approximate Nash by each playing a no-regretalgorithm in a repeated game, and taking their average strategy over the first 푇 rounds.We generalize the latter, showing that if each player in a concave NZSG with continuous strategysets uses a no-regret learning learning rule, then the strategy profile given by the time average of theirstrategies is a 표(푇)-approximate Nash equillibrium. This has the added implication that as the timehorizon stretches to infinity, the time-average of player strategies converge to a Nash.Theorem 5.1. Consider a repeated concave NZSG with compact strategy sets. Assume that eachplayer 푖 uses a no-regret algorithm to determine her strategy 풙푡푖 at each time step, suffering atmost 휖푖 (푇) ∈ 표(푇) regret over the first 푇 time steps. Let 풙¯푇푖 = 1푇∑푇푡=1 풙푡푖 . Then the strategy profile풙¯푇 = (풙¯푇1 , . . . , 풙¯푇푛 ) constitutes a 1푇∑푖∈푉 휖푖 (푇)-approximate Nash equillibrium.A key step in the proof of Theorem 5.1 is the following property of NZSGs. We will makerepeated use of this property when showing last iterate convergence in Section 5.2.Lemma 5.1. In an NZSG, for any two strategy profiles 풙 and 풙∗, we have∑푖푝푖 (풙푖 ,풙∗−푖) = −∑푖푝푖 (풙∗푖 ,풙−푖).5.2 Last iterate convergenceTheorem 5.1 is not adequate for applications where strategies are parameters of neural networks,since averaging over strategies makes little sense in such settings. Following much recent literature,we shift the focus to last iterate convergence.Inspired by GANs, in Sections 5.2.1 and 5.2.2 we analyze convergence when player strategies areunconstrained, and players use GA, OGA, and EG, showing exponential convergence towards a Nashin NZSGs with linear payoffs, and 훽-smooth NZSGs with strongly concave payoffs. In Section 5.2.3we analyze the generalized versions of these algorithms — showing last-iterate convergence for OMDin the setting of 훼-strongly monotone 푛-player games.335.2.1 Linear payoffsEven in a two-player zero-sum game with the linear payoff 푝(풙1,풙2) = 풙>1퐶풙2, where 퐶 is a 푑1× 푑2matrix, if each player uses GA, over time the players’ strategies diverge from the set of Nash [24]. If,instead, players use EG or OGA, their strategies converge to a Nash of such a game [13, 24, 26]. Weshow that these phenomena continue to hold for NZSGs with linear payoffs. Furthermore, we areable to relax a standard assumption on the second derivative of player payoffs, showing that when thesum of the dimensions of player strategies is odd, players converge to a Nash when using EG or OGA.To state the rates of convergence, we need to introduce a matrix 퐻 for NZSGs with linear payoffs.This matrix is the first derivative of the gradient operator. Given an NZSG and a strategy profile 풙,the Hessian 퐻 (풙) is a 푑 × 푑 block matrix with the (푖, 푗)푡ℎ block given by퐻푖 푗 (풙) = ∇2풙 푗 ,풙푖 푝푖 (풙)Since 퐻 (풙) is constant on X for the game with linear payoffs, we write it as 퐻 for the remainder ofthis section.Denote the smallest modulus of a nonzero eigenvalue of 퐻 by 휔(퐻), and denote the largestmodulus of any eigenvalue of 퐻 by 휌(퐻). Denote the distance to a set by 푑 (u,S) B mins∈S ‖u− s‖2.Theorem 5.2. Consider an unconstrained, NZSG with linear payoffs. Let X∗ denote the set of Nashof the game. Let 풙0 ∈ X, and assume that 푑 (풙0,X∗) ≥ 푅, for some 푅 > 0. Then if each player updatesher strategy using GA, at each time step 푡,푑 (풙푡 ,X∗)2 ≥(1+휂2푡휔(퐻)2) 푡푅2.Theorem 5.3. Consider an unconstrained NZSG with linear payoffs. Let X∗ denote the set of Nashof the game. Let 풘0 ∈ X, and assume that 푑 (풘0,X∗) ≤ 푟 , for some 푟 > 0. Then if each player updatesher strategy using EG with fixed step size 휂 = 휔 (퐻 )22휌(퐻 )4 , at each time step 푡,푑 (풘푡 ,X∗)2 ≤(1− 휔(퐻)44휌(퐻)4) 푡푟2.Theorem 5.4. Consider an unconstrained NZSG with linear payoffs. Let X∗ denote the set of Nashof the game. Let 풙0,풙1 ∈ X, and assume that 푑 (풙0,X∗) ≤ 푟, 푑 (풙1,X∗) ≤ 푟 for some 푟 > 0. Then ifeach player updates her strategy using OGA with fixed step size 휂 = 12휌(퐻 ) , at each time step 푡,푑 (풙푡+1,X∗)2 =푂 ©­­«©­«12 + 12(1−(휔(퐻)휌(퐻))2) 12 ª®¬푡ª®®¬ .We sketch the proof ideas and relegate details to Section 5.4.1. We formulate the behavior of GA,EG and OGA as trajectories of dynamical systems; this view has been taken in several previous works,34which also analyze the behaviors of algorithms using tools from dynamical systems (see Section 3.2).For dynamical system 품, the Jacobian is the matrix with its (푖, 푗)-th entry 퐽푖 푗 = 휕품푖휕풙 푗 . Players ina linear game update their strategies according to a linear dynamical system, 풙푡+1 = 퐽풙푡 . Recallthat the set of fixed points of a dynamical system are exactly the points such that 품(풙) = 풙. Thus,the fixed points of a linear system are exactly the vectors that the span the 1-eigenspace of 퐽. Theeigenvalues of the Jacobian at a fixed point 풛 describe the behavior of the dynamics around 풛, butmay be insufficient for determining convergence rates. Yet, when 퐽 is diagonalizable, convergencerates can be inferred directly from the eigenvalues.Definition 5.3. Let 퐴 ∈ C푘×푘 . Then 퐴 is diagonalizable over C if there exist 푃,푃−1 such that 푃퐴푃−1is diagonal. Equivalently, there exists a basis of C푘 which are the eigenvectors of 퐴.Proposition 5.1. LetZ denote the set of fixed points of a dynamical system with linear update rule:품(풛) = 퐽풛, where J is diagonalizable. Then for some problem specific 푐 > 0:(a) If ∀휆 ∈ 휆(퐽) either |휆 | < 1 or 휆 = 1, then letting 휆max<1 (퐽) denote the largest modulus of anyeigenvalue of 퐽 not equal to 1, ∀풙0 ∈ 푋 , 푑 (풙푡 ,Z) ≤ 푐(휆max<1 (퐽))푡푑 (풙0,Z).(b) If ∀휆 ∈ 휆(퐽) either |휆 | > 1 or 휆 = 1, then letting 휆min>1 (퐽) denote the smallest modulus of anyeigenvalue of 퐽 not equal to 1, ∀풙0 ∈ 푋, 푑 (풙푡 ,Z) ≥ 1푐 (휆min>1 (퐽))푡푑 (풙0,Z).For GA, the player strategies evolve according to the dynamical system, 풙푡+1 = (퐼푑 +휂퐻)풙푡 . It isnot hard to show that the set of Nash equillibria for the linear game is precisely the set of fixed pointsof this dynamical system.The Jacobian of the dynamical system induced by players using GA can be shown to bediagonalizable. To show Theorem 5.2, therefore, it suffices to analyze the eigenvalues of the matrix퐽퐺퐴 = 퐼푑 +휂퐻. In order to do so, we must understand the structure of 퐻. The crucial observation isthat, for NZSGs, the Hessian 퐻 is an antisymmetric matrix of the form퐻 =0 퐶12 . . . 퐶1푛−퐶>12 0 . . . 퐶2푛....... . ....−퐶>1푛 −퐶>2푛 . . . 0.This is a consequence of the following lemma for NZSGs in general:Lemma 5.2. In an NZSG, if each 푝푖 is twice differerntiable, then ∇2풙푖 ,풙 푗 푝푖 (풙) = −(∇2풙푖 ,풙 푗 푝 푗 (풙))>.For an antisymmetric matrix, its eigenvalues can be shown to come in complex pairs. Therefore,the eigenvalues of the Jacobian of the dynamical system induced by players using GA, are of theform 1+ 푖휂푡훾 for some 훾 ∈ R, and hence applying Proposition 5.1, we achieve the convergence rate inTheorem 5.2.35Showing Theorem 5.3 is another straightforward application of Proposition 5.1. It can be shownthat the dynamical system induced by players using EG has the same fixed points as that of GA, andhence are equal to the set of Nash equillibria. Furthermore, for the linear game, the two step updateof EG can be written as a single step,풘푡+1 = 풘푡 +휂퐻풙푡+1 = 풘푡 +휂퐻 (퐼푑 +휂퐻)풘푡 =(퐼푑 +휂퐻 +휂2퐻2)풘푡 B 퐽퐸퐺풘푡 .Similar to GA, 퐽퐸퐺 can be shown to be diagonalizable. In a similar manner to GA, due to antisymmetryof 퐻, the eigenvalues of 퐽퐸퐺 are given by 1+ 푖휂훾−휂2훾2 for some 훾 ∈ R. With 휂 = 휔 (퐻 )22휌(퐻 )4 , the largestmodulus of any of any non-1 eigenvalue of 퐽퐸퐺 is upper bounded,휆max<1 (퐽퐸퐺) ≤√1− 휔(퐻)44휌(퐻)4 .Applying Proposition 5.1, we get the result of 5.3.Providing an exponential rate of convergence for OGA is more involved. We first need to augmentthe state space to allow the memory from a previous step to be passed as part of the state. FollowingDaskalakis and Panageas [10], we consider a dynamical system with the following update rule품 : R2푑→ R2푑 , defining 푝ˆ푖 (풙,풙′) B 푝푖 (풙):품(풙,풙′) = (품1(풙,풙′), 품2(풙,풙′)), (5.1)품1푖 (풙,풙′) = 풙푖 +2휂∇풙푖 푝ˆ푖 (풙,풙′) −휂∇풙′푖 푝ˆ푖 (풙,풙′),품2푖 (풙,풙′) = 풙푖 .More explicitly, for the OGA update rule, we have the relation (풙푡+1,풙푡 ) = 품(풙푡 ,풙푡−1). Once again,it is easy to show that this dynamical system has the same fixed points as the one for GA in the lineargame.The eigenvalues of this dynamical system in the linear game all have moduli less than 1 when 휂 ischosen appropriately. As a result of 퐻 being diagonalizable (since it is an antisymmetric matrix,and hence commutes with its transpose), the resulting Jacobian is diagonalizable, and we can applyProposition 5.1.To the best of our knowledge, ours is the first work to provide exponential convergence rates forEG and OGA without assuming that 퐻 is invertible. Since 퐻 is antisymmetric, its eigenvalues comein imaginary pairs. When 퐻 has odd dimension, it necessarily has at least one eigenvalue with value0, and thus is not invertible.5.2.2 Smooth games with strongly concave payoffsIn this section we assume that the game is 훽-smooth and has 훼-strongly concave payoffs. The gameis said to have 훼-strongly concave payoffs if each 푝푖 is 훼-strongly concave in 풙푖. Throughout thissection, we assume that each 푝푖 is differentiable, and hence has a unique supergradient ∇풙푖 푝푖 (풙)36at each point 풙. We show that when players use GA, EG and OGA to update their strategies in a훽-smooth game with payoffs that are 훼-strongly concave, their strategies converge to a Nash at anexponential rate.Before stating our main results, we remark on the existence and uniqueness of Nash. UnlikeNZSGs with linear payoffs, where 풙 = 0 is always a Nash, in general, a Nash may not exist when thestrategy spaces are not compact. With 훼-strong concavity, however, we do get uniqueness of a Nashwhen one exists.Lemma 5.3. In an NZSG with 훼-strongly concave payoffs with 훼 > 0, if a Nash equilibrium exists,it is unique.For applications such as GANs, where strategies are parameters of neural networks, strategyspaces are practically compact, and a Nash equilibrium is guaranteed to exist.We now state the main results of this section.Theorem 5.5. Consider an unconstrained NZSG that is 훽-smooth and has payoffs that are 훼-stronglyconcave with 훼 > 0. Assume the existence of a Nash, 풙∗. Let 풙0 ∈ X be such that∀푖 ∈푉, ‖풙0푖 −풙∗푖 ‖2 ≤ 푟for 푟 > 0. Then if each player updates her strategy according to GA with fixed learnig rate 휂 = 훼2훽2 , ateach time step 푡, ∑푖‖풙푡푖 − 풙∗푖 ‖22 ≤(1− 훼24훽2) 푡푛푟2.Theorem 5.6. Consider an unconstrained NZSG that is 훽-smooth and has payoffs that are 훼-stronglyconcavewith훼 > 0. Assume the existence of aNash, 풙∗. Let풘0 ∈ X be such that∀푖 ∈푉, ‖풘0푖 −풙∗푖 ‖2 ≤ 푟for 푟 > 0. Then if each player updates her strategy using EG with fixed learning rate 휂 ≤ 12훽 , at eachtime step 푡, ∑푖‖풘푡푖 − 풙∗푖 ‖22 ≤(1− 훼4훽) 푡푛푟2.Theorem 5.7. Consider an unconstrained NZSG that is 훽-smooth and has payoffs that are 훼-strongly concave with 훼 > 0. Assume the existence of a Nash, 풙∗. Let 풙0,풙1 ∈ X be such that∀푖 ∈ 푉,풙1푖 = 풙0 +휂∇풙푖 푝푖 (풙0), and ‖풙0푖 − 풙∗푖 ‖2 ≤ 푟 for 푟 > 0. Then if each player updates her strategyusing OGA, with fixed learning rate 휂 = 14훽 , at each time step 푡,∑푖‖풙푡푖 − 풙∗푖 ‖22 ≤ 4(1− 훼8훽) 푡푛푟2.One way to establish convergence rates for players using EG and OGA in 훽-smooth and 훼-stronglyconcave NZSGs, is directly through the analysis of Azizian et al. [2], as we show in Section 5.2.3that NZSGs with 훼-strongly concave payoffs do in fact have a gradient operator which is 훼-strongly37monotone. However, we are able to establish tighter bounds by tailoring our proofs to NZSGs.Furthermore, we notice that the proof structure for both EG and OGA is due to a more generalconvergence analysis which can be used to show that the corresponding variants of OMD obtain lastiterate convergence.In order show convergence, we use the sum of the squared distances of player strategies from theNash as a Lyapunov function, in a similar manner to Mokhtari et al. [27], and Azizian et al. [2]. Thekey that allows us to extend the proofs of convergence from two-player zero-sum games to NZSGs isLemma 5.1, which causes terms that are introduced by the strong concavity condition to vanish.For the EG update, we follow the proof of Theorem 4.3 from Azizian et al. [2]. Although theiranalysis is directly applicable to our setting, we include the proof to highlight the connection betweenEG and OMD. For OGA, out of the box, the proof of Mokhtari et al. [27] essentially extends toNZSGs, with the caveat that Lemma 5.1 has to be used to get rid of terms introduced by strongconcavity. Yet, by noticing that the same proof by which we analyze OMD can be used to for OGA,we are able to significantly simplify and tighten their analysis.5.2.3 Monotone gradient operatorWe now take a more global approach, and analyze the convergence of optimistic mirror descentwhen players’ strategies may be constrained to some subset of R푑푖 . In order to make our analysescomparable to previous results, we analyze these algorithms in the context of games with an 훼-stronglymonotone gradient operator.We begin by showing that the class of games with an 훼-strongly monotone gradient operatoris strictly more general than NZSGs with 훼-strongly concave payoffs. We then show that inany game with 퐿-Lipschitz payoffs, and a monotone gradient operator, OMD attains last iterateconvergence. Afterwards, we analyze the convergence of OMD in 훽-smooth games with an 훼-stronglymonotone gradient operator, showing that the results of Section 5.2.2 arise as simple corollariesof these convergence proofs. As in the two-player setting, we make use of the joint mirror map,휙(풙) B ∑푖 휙푖 (풙푖), in the statement of our theorems and in our proofs.Proposition 5.2. Consider an NZSG such that each player’s payoff is 훼-strongly concave in theirstrategy for some 훼 ≥ 0. Then v is 훼-strongly monotone.Theorem 5.8. Consider an 푛-player game with 퐿-Lipschitz payoffs and a monotone gradient operator.Assume that ∀푖 ∈ 푉,X푖 ⊆ R푑푖 is convex and compact. Let 풘0,풙0 ∈ X and assume that D휙 (풙∗,풘0)is finite. Then if at every time step 푡, each player updates her strategy using OMD with step size휂푡 ≤ ‖풙푡−풘푡 ‖4퐿 ,lim푡→∞D휙 (풙∗,풘푡 ) = 0.Theorem 5.9. Consider an 푛-player game that is 훽-smooth and has an 훼-strongly monotone gradientoperator with 훼 > 0. Assume that ∀푖 ∈ 푉,X푖 ⊆ R푑푖 is convex and compact. Let 풘0,풙0 ∈ X. Then if at38every time step 푡, each player updates her strategy using OMDwith adaptive predictorM푡푖 =∇풙푖 푝푖 (풘푡푖 )and step size 휂푡 ≤ 14훽 ,D휙 (풙∗,풘푡 ) ≤ D휙 (풙∗,풘푡−1) − 훼8훽 ‖풘푡−1− 풙∗‖2.Theorem 5.10. Consider an 푛-player game that is 훽-smooth and has an 훼-strongly monotone gradientoperator with 훼 > 0. Assume that ∀푖 ∈ 푉,X푖 ⊆ R푑푖 is convex and compact. Let 풘0,풙0 ∈ X. Then if atevery time step 푡, each player updates her strategy using OMDwith adaptive predictorM푡푖 = ∇풙푖 푝푖 (풙푡 )and step size 휂푡 ≤ 14훽 ,D휙 (풙∗,풘푡 ) + 14 ‖풙푡 −풘푡 ‖2 ≤ D휙 (풙∗,풘푡−1) + 14(1− 훼4훽)‖풙푡−1−풘푡−1‖2− 훼8훽‖풘푡−1− 풙∗‖2.Proposition 5.2 shows that results from this section generalize to NZSGs. Secondly, it shows thatthe results of Azizian et al. [2] are applicable to NZSGs, and hence provide an alternative derivationfor the results of Section 5.2.2. Lastly, due to the proof structures of the results of Mertikopouloset al. [26], their results extend to the context of 푛-player games with an 훼-strongly monotone gradientoperator.Mertikopoulos et al. [26] proved that when players use MD to update their strategies in a gamewith 퐿-Lipschitz payoffs and an 훼-strongly monotone gradient operator with 훼 > 0, they converge inlast iterate to a Nash. Theorem 5.8 can be seen as a parallel result for OMD. Unsurprisingly, ratherthan requiring 훼 > 0, OMD attains last iterate convergence for any monotone game with 퐿-Lipschitzpayoffs. This includes any concave NZSG with 퐿-Lipschitz payoffs, and consequently, any two-playerzero-sum game with concave-convex and 퐿-Lipschitz payoff.Theorem 5.9 shows that when players use OMD with the particular adaptive predictor M푡푖 =∇풙푖 푝푖 (풘푡 )— i.e., the OMD variant corresponding to EG, in a game with strictly monotone payoff,they converge monotonically at a rate which is proportional to their distance from the Nash. Theproof structure is identical to the proof of Theorem 5.6, which shows exponential convergence for EGin NZSGs which are 훽-smooth and have 훼-strongly concave payoffs. As stated, Theorem 5.6 arisesas a corollary of Theorem 5.9.Corollary 5.1. On top of the assumptions of Theorem 5.9, assume that each 휙푖 is 1-smooth. Then‖풘푡 − 풙∗‖2 ≤(1− 훼4훽) 푡‖풘0− 풙∗‖2.Similarly, Theorem 5.10, is a generalization of Theorem 5.7. Interestingly, for OMDwith adaptivepredictorM푡푖 = ∇풙푖 푝푖 (풙푡 ), the Lyapunov function governing player convergence is more obtuse thanthat of Theorem 5.9. This is in line with previous proofs of convergence for OGA (see Gidel et al.[15] and Mokhtari et al. [27]).39Corollary 5.2. On top of the assumptions of Theorem 5.10, assume that each 휙푖 is 1-smooth, andthat OMD is initialized with 풙0,풘0 ∈ X such that 풙0 = 풘0. Then‖풙푡 − 풙∗‖2 ≤ 4(1− 훼4훽) 푡‖풙0− 풙∗‖2.5.3 Omitted proofs from Section 5.1Lemma 5.1. In an NZSG, for any two strategy profiles 풙 and 풙∗, we have∑푖푝푖 (풙푖 ,풙∗−푖) = −∑푖푝푖 (풙∗푖 ,풙−푖).Proof. By the zero sum property we have−푝푖 (풙∗푖 ,풙−푖) =∑푘∈푉−푖©­«푝푘푖 (풙푘 ,풙∗푖 ) +∑[푘, 푗 ] ∈퐸−푖푝푘 푗 (풙푘 ,풙 푗)ª®¬ .Summing over the players,−∑푖∈푉푝푖 (풙∗푖 ,풙−푖) =∑푖∈푉∑푘∈푉−푖©­«푝푘푖 (풙푘 ,풙∗푖 ) +∑[푘, 푗 ] ∈퐸−푖푝푘 푗 (풙푘 ,풙 푗)ª®¬=∑푖∈푉∑[푖,푘 ] ∈퐸푝푘푖 (풙푘 ,풙∗푖 ) + (푛−1)∑푖∈푉푝푖 (푥)=∑푖∈푉∑[푖,푘 ] ∈퐸푝푖푘 (풙푖 ,풙∗푘)=∑푖∈푉푝푖 (풙푖 ,풙∗−푖).Theorem 5.1. Consider a repeated concave NZSG with compact strategy sets. Assume that eachplayer 푖 uses a no-regret algorithm to determine her strategy 풙푡푖 at each time step, suffering atmost 휖푖 (푇) ∈ 표(푇) regret over the first 푇 time steps. Let 풙¯푇푖 = 1푇∑푇푡=1 풙푡푖 . Then the strategy profile풙¯푇 = (풙¯푇1 , . . . , 풙¯푇푛 ) constitutes a 1푇∑푖∈푉 휖푖 (푇)-approximate Nash equillibrium.Proof. Let 풙∗ be a Nash of the game. By the definition of no regret ∀푖 ∈ 푉 ,1푇휖푖 (푇) ≥ 1푇푇∑푡=1(푝푖 (풙∗푖 ,풙푡−푖) − 푝푖 (풙푡푖 ,풙푡−푖)).40Summing over the players,1푇∑푖∈푉휖푖 (푇) ≥ 1푇푇∑푡=1∑푖∈푉(푝푖 (풙∗푖 ,풙푡−푖) − 푝푖 (풙푡푖 ,풙푡−푖))=1푇푇∑푡=1∑푖∈푉푝푖 (풙∗푖 ,풙푡−푖)where the last equality follows from the zero sum property. By Lemma 5.1,1푇푇∑푡=1∑푖∈푉푝푖 (풙∗푖 ,풙푡−푖) = −1푇푇∑푡=1∑푖∈푉푝푖 (풙푡푖 ,풙∗−푖) ≥ −∑푖∈푉푝푖 (풙¯푇푖 ,풙∗−푖), (5.2)where the rightmost inequality of (5.2) follows from the concavity of each 푝푖 in 풙푖 . Consider adding∑푖∈푉 푝푖 (풙∗) to the last term in (5.2). Since the game is zero sum, then∑푖∈푉 푝푖 (풙∗) = 0 and we get∑푖∈푉(푝푖 (풙∗) − 푝푖 (풙¯푇푖 ,풙∗−푖))≤ 1푇∑푖∈푉휖푖 (푡).Since 풙∗ is a Nash, we have that ∀푖 ∈ 푉 , 푝푖 (풙∗) − 푝푖 (풙¯푡푖 ,풙∗−푖) ≥ 0, and hence ∀푖 ∈ 푉푝푖 (풙∗) − 푝푖 (풙¯푡푖 ,풙∗−푖) ≤1푇∑푖∈푉휖푖 (푡),i.e., 풙¯푇 = (풙¯1푇 , ..., 풙¯푛푇 ) is a 1푇∑푖∈푉 휖푖 (푡)-approximate Nash. 5.4 Omitted proofs from Section 5.25.4.1 Omitted proofs from Section 5.2.1Lemma 5.2. In an NZSG, if each 푝푖 is twice differerntiable, then ∇2풙푖 ,풙 푗 푝푖 (풙) = −(∇2풙푖 ,풙 푗 푝 푗 (풙))>.Proof. Since the game is zero sum, we have 푝푖 (풙) = −∑푘∈푉−푖 푝푘 (풙). Taking the derivative withrespect to 푖,∇풙푖 푝푖 (풙) = −∇풙푖( ∑푘∈푉−푖푝푘 (풙))= −∑푘∈푉−푖∇풙푖 푝푘푖 (풙푖 ,풙푘).Taking the derivative of the LHS with respect to 푗 ≠ 푖,∇풙 푗(∇풙푖 푝푖 (풙)) = ∇2풙 푗 ,풙푖 푝푖 (풙) = ∇2풙 푗 ,풙푖 푝푖 푗 (풙푖 ,풙 푗).And taking the derivative of the RHS with respect to 푗 ≠ 푖,−∇풙 푗( ∑푘∈푉−푖∇풙푖 푝푘푖 (풙푖 ,풙푘))= −∇2풙 푗 ,풙푖 푝 푗푖 (풙푖 ,풙 푗) = −(∇2풙푖 ,풙 푗 푝 푗푖 (풙푖 ,풙 푗))>= −(∇풙푖 ,풙 푗 푝 푗 (풙))>.41In order to prove Proposition 5.1, we need the following Lemma showing that when 퐴 ∈ R푘×푘 isdiagonalizable over C, then it is similar to its Real Jordan Form - a real block diagonal matrix.Lemma 5.4 (Real Jordan Form [19]). Let 퐴 ∈ R푘×푘 . Assume that 퐴 is diagonalizable over C, andthat 퐴 has 푚 real eigenvalues, and (푘 −푚) complex eigenvalues. Then there exists a 푃, 푅 ∈ R푘×푘such that 퐴 = 푃−1푅푃 where the columns of 푃 form a basis for R푘 and푅 =휆1. . .휆푚퐵1. . .퐵 (푘−푚)/2, (5.3)and for an arbitrary complex eigenvalue pair of 퐴, 휇 푗 ± 푖휔 푗 ,퐵 푗 =[휇 푗 −휔 푗휔 푗 휇 푗].Proposition 5.1. LetZ denote the set of fixed points of a dynamical system with linear update rule:품(풛) = 퐽풛, where J is diagonalizable. Then for some problem specific 푐 > 0:(a) If ∀휆 ∈ 휆(퐽) either |휆 | < 1 or 휆 = 1, then letting 휆max<1 (퐽) denote the largest modulus of anyeigenvalue of 퐽 not equal to 1, ∀풙0 ∈ 푋 , 푑 (풙푡 ,Z) ≤ 푐(휆max<1 (퐽))푡푑 (풙0,Z).(b) If ∀휆 ∈ 휆(퐽) either |휆 | > 1 or 휆 = 1, then letting 휆min>1 (퐽) denote the smallest modulus of anyeigenvalue of 퐽 not equal to 1, ∀풙0 ∈ 푋, 푑 (풙푡 ,Z) ≥ 1푐 (휆min>1 (퐽))푡푑 (풙0,Z).Proof. We begin with the proof of (a). Since by assumption 퐽 is diagonalizable over C, then byLemma 5.4 there exists a 푃, 푅 ∈ R푑×푑 such that 퐽 = 푃−1푅푃, and the columns of 푃 form a basis forR푑 , while 푅 is in the block diagonal from given by (5.3). Consider performing a linear change ofcoordinates according to 푃,풙푡+1 = 퐽풙푡 ⇒ 푃풙푡+1 = 푅푃풙푡 ⇒ 풚푡+1 = 푅풚푡 .푃 forms a basis of of R푑 , so we can express 풚푡 as a linear combination of its columns, i.e., 풚푡 =∑푖 푐푖p푖42where each 푐푖 ∈ R. Let 풘∗ =∑푖,휆푖=1 푐푖p푖 . Since ∀휆 ∈ 휆(퐽), |휆 | < 1 or 휆 = 1,‖풚푡+1−풘∗‖2 = ‖푅풚푡 −풘∗‖2=푅 ∑푖,휆푖≠1푐푖p푖2≤ 휆max<1 (퐽) ∑푖,휆푖≠1푐푖p푖2= 휆max<1 (퐽)‖풚푡 −풘∗‖2.≤ (휆max<1 (퐽)) 푡+1 ‖풚0−풘∗‖2We bound the untransformed iterates,‖풙푡+1−푃−1풘∗‖2 = ‖푃−1‖2‖풚푡+1−풘∗‖2≤ (휆max<1 (퐽))푡+1‖푃−1‖2‖풚0−풘∗‖2= (휆max<1 (퐽))푡+1‖푃−1‖2‖푃‖2‖풙0−푃−1풘∗‖2≤ (휆max<1 (퐽))푡+1(휎max(푃)휎min(푃))‖풙0−푃−1풘∗‖2.Finally, notice that 푃−1풘∗ is a fixed point of 품. This is due to the fact that 퐽푃−1풘∗ = 푃−1푅푃푃−1풘∗ =푃−1푅풘∗ = 푃−1풘∗. This proves (a). Part (b) can be proven in a similar manner. Corollary 5.3. On top of the assumptions of Proposition 5.1, if 퐽 is normal, then Proposition 5.1holds with 푐 = 1.Proof. In this case, 푃 from Lemma 5.4 is unitary, and hence 푐 = 휎max (푃)휎min (푃) = 1. Lemma 5.5 ([21]). Let 퐴 ∈ R푘×푘 . Assume that 퐴퐴> = 퐴>퐴, then 퐴 is normal.Theorem 5.2. Consider an unconstrained, NZSG with linear payoffs. Let X∗ denote the set of Nashof the game. Let 풙0 ∈ X, and assume that 푑 (풙0,X∗) ≥ 푅, for some 푅 > 0. Then if each player updatesher strategy using GA, at each time step 푡,푑 (풙푡 ,X∗)2 ≥(1+휂2푡휔(퐻)2) 푡푅2.Proof. We begin by identifying the Nash of this game. We show that 풙∗ is a Nash of the game if andonly if ∀푖 ∈ 푉,∑ 푗≠푖퐶푖 푗풙 푗 = 0.By definition, a strategy profile 풙∗ = (풙∗1, ...,풙∗푛) is a Nash if ∀푖 ∈ 푉,∀풙푖 ∈ R푑푖 ,(풙∗푖 )>∑푗≠푖퐶푖 푗풙∗푗 ≥ 풙>푖∑푗≠푖퐶푖 푗풙∗푗 .Since we are in the unconstrained setting and this must hold for an arbitrary 풙푖, we must have foreach 푖,∑푗≠푖퐶푖 푗풙∗푗 = 0.43Next, consider the dynamical system induced by players using GA, i.e., 풙푡+1 = (퐼푑 +휂퐻)풙푡 . For풙 to be a fixed point, we must have풙 = 풙 +휂퐻풙⇔ 퐻풙 = 0⇔∀푖 ∈ 푉,∑푗≠푖퐶푖 푗풙 푗 = 0. (5.4)Since for any 풙∗, ∀푖 ∈ 푉,∑ 푗≠푖퐶푖 푗풙∗푗 = 0 if and only if 풙∗ is Nash, the fixed points of the givendynamical system are exactly the Nash of the game.The Jacobian of the dynamical system induced by players using GA is the constant matrix,퐽GA = (퐼푑 +휂퐻). We want to be apply Corollary 5.3 to this dynamical system. We begin by showingthat 퐽퐺퐴 is normal.A real matrix is normal if it commutes with its transpose. For 퐽퐺퐴 we have퐽GA퐽>GA = (퐼 +휂퐻) (퐼 −휂퐻) = (퐼 −휂2퐻) = (퐼 −휂퐻) (퐼 +휂퐻) = 퐽>GA퐽GA.Next, we show that for any eigenvalue 휆 ∈ 휆(퐽퐺퐴), |휆 | = 1 or |휆 | > 1. Since 퐻 is antisymmetric,it has purely imaginary eigenvalues. Take any eigenvalue from 휆(퐻) — since it is imaginary wedenote it by 푖훾 where 훾 ∈ R. For each 푖훾 ∈ 휆(퐻) have a corresponding eigenvalue 휆 ∈ 휆(퐽GA) givenby 휆 = 1+ 푖휂훾. If 훾 = 0 then 휆 = 1, and if 훾 ≠ 0, |휆 | > 1. Therefore, By Corollary 5.3,푑 (풙푡+1,X∗)2 ≥ (휆min>1 (퐽GA))2푡 푅2=(1+휂2푡휔(퐻)2) 푡푅2.Theorem 5.3. Consider an unconstrained NZSG with linear payoffs. Let X∗ denote the set of Nashof the game. Let 풘0 ∈ X, and assume that 푑 (풘0,X∗) ≤ 푟 , for some 푟 > 0. Then if each player updatesher strategy using EG with fixed step size 휂 = 휔 (퐻 )22휌(퐻 )4 , at each time step 푡,푑 (풘푡 ,X∗)2 ≤(1− 휔(퐻)44휌(퐻)4) 푡푟2.Proof. Consider the EG update in the linear game,풘푡+1 = 풘푡 +휂퐻풙푡+1 = 풘푡 +휂퐻 (퐼푑 +휂퐻)풘푡 =(퐼푑 +휂퐻 +휂2퐻2)풘푡 B 퐽퐸퐺풘푡 .First notice that 풙 is a fixed point of the above dynamic if and only if 퐻풙 = 0, and hence by (5.4),this dynamical system has the same set of fixed points as the dynamical system induced by playersusing GA. Therefore, the Nash of the linear game are exactly the fixed points the dynamical system ofplayers using EG.Once again, we want to be able to apply Corollary 5.3. 퐽퐸퐺 commutes with its transpose and by44Lemma 5.5 is normal,퐽퐸퐺퐽>퐸퐺 =(퐼푑 +휂퐻 +휂2퐻2) (퐼푑 +휂퐻 +휂2퐻2)>=(퐼푑 +휂퐻 +휂2퐻2) (퐼푑 −휂퐻휂2 +퐻2)=(퐼푑 −휂퐻 +휂2퐻2) (퐼푑 +휂퐻 +휂2퐻2)= 퐽>퐸퐺퐽퐸퐺 .Next, we analyze the eigenvalues of 퐽퐸퐺 . Since 퐻 is antisymmetric, it has purely imaginaryeigenvalues. Let 풙 be an eigenvector of 퐻 with eigenvalue 푖훾 where 훾 ∈ R. Then퐽퐸퐺풙 = (퐼푑 +휂퐻 +휂2퐻2)풙 = 풙 + 푖훾풙−휂2훾2풙 = (1+ 푖휂훾−휂2훾2)풙,i.e., for each eigenvalue 푖훾 of 퐻, 퐽퐸퐺 has an eigenvalue 휆 = 1+ 푖휂훾−휂2훾2. If 훾 = 0, then |휆 | = 1. If훾 ≠ 0, the squared modulus of 휆 can be bounded:|휆 |2 = (1−휂2훾2) + (휂훾)2 = 1−휂2훾2 +휂4훾4 ≤ 1−휂2휔(퐻)2 +휂4휌(퐻)4.Setting 휂 = 휔 (퐻 )√2휌(퐻 )2 ,휆max<1 (퐽퐸퐺) ≤√1− 휔(퐻)44휌(퐻)4 .Therefore by Corollary 5.3,푑 (풙푡 ,X∗)2 ≤(1− 휔(퐻)44휌(퐻)4) 푡푟2.In order to prove Theorem 5.4, we need the following characterization of diagonalizability.Lemma 5.6 ([21]). Let 퐴 ∈ R푘×푘 . Then 퐴 is diagonalizable over C if and only if the sum of theeigenspaces of 퐴 are equal to 푘 .Theorem 5.4. Consider an unconstrained NZSG with linear payoffs. Let X∗ denote the set of Nashof the game. Let 풙0,풙1 ∈ X, and assume that 푑 (풙0,X∗) ≤ 푟, 푑 (풙1,X∗) ≤ 푟 for some 푟 > 0. Then ifeach player updates her strategy using OGA with fixed step size 휂 = 12휌(퐻 ) , at each time step 푡,푑 (풙푡+1,X∗)2 =푂 ©­­«©­«12 + 12(1−(휔(퐻)휌(퐻))2) 12 ª®¬푡ª®®¬ .Proof. Consider the augmented dynamical system given in (5.1). For the linear game this can be45expressed as [풙푡+1풙푡]=[퐼푑 +2휂퐻 −휂퐻퐼푑 0푑×푑] [풙푡풙푡−1]B 퐽푂퐺퐴[풙푡풙푡−1].Consider a point (풛, 풛′) where 풛, 풛′ ∈ R푑 . Then (풛, 풛′) is a fixed point of the dynamical system inducedby players using OGA if it satisfies풛′ = 풛풛 = (퐼푑 +휂퐻)풛−휂퐻풛′ = (퐼푑 +휂퐻)풛−휂퐻풛,i.e., the fixed points of this dynamic are exactly the points (풛, 풛) such that 풛 is a fixed point of thedynamical system induced by the GA dynamic, and hence the Nash of this game .Next, we analyze the eigenvalues of the 퐽푂퐺퐴. Let (풙,풙′) be such that 풙,풙′ ∈ R푑 . We solve thefollowing system:(퐽푂퐺퐴−휆퐼2푑)[풙풙′]= 0⇒[(1−휆)퐼푑 +2휂퐻 −휂퐻퐼푑 −휆퐼푑] [풙풙′]= 0.Solving for the last 푑 rows of the above system, we get 풙 = 휆풙′. From the top 푑 rows,((1−휆) +2휂퐻)풙−휂퐻풙′ = ((1−휆) +2휂퐻)휆풙′−휂퐻풙′ = 0.Assume that 풙′ is an eigenvector of 퐻. Since 퐻 is antisymmetric, then it has purely imaginaryeigenvalues. Let 푖훾 be the eigenvalue of 풙′, where 훾 ∈ R. Then((1−휆) +2휂퐻)휆풙′−휂퐻풙′ = (1−휆)휆풙′+2푖휂훾휆풙′− 푖휂훾풙′= −휆2 +휆(1+2푖휂훾)풙′− 푖휂훾풙′.Setting the above equal to 0, and solving for 휆,휆 =1+2푖휂훾±√(1+2푖휂훾)2−4푖휂훾2=1±√1−4휂2훾22+ 푖휂훾.If we set 휂 ≤ 12휌(퐻 ) then |휆 | ≤ 1. In particular, if 훾 ≠ 0, |휆 | < 1, and if 훾 = 0 then 휆 = 1.Next we show that 퐽푂퐺퐴 is diagonalizable. Since 퐻 is an antisymmetric matrix, it commuteswith its transpose, and by Lemma 5.5 is normal, and hence diagonalizable,퐻퐻> = −퐻2 = 퐻>퐻.In order to show that 퐽푂퐺퐴 is diagonalizable, we make use of Lemma 5.6 which says that퐴 ∈ R푑×푑 is diagonalizable if and only if the sum of the dimensions of its eigenspaces is equal to 푑.46Let 휆+푖훾 =(12(1+√1−4휂2훾2)+ 푖휂훾). For any vector 풘 푗 that is an eigenvector of 퐻 witheigenvalue 푖훾, the vector (휆+푖훾풘 푗 ,풘 푗) is an eigenvector of 퐽푂퐺퐴 with eigenvalue 휆+푖훾 . Denote thestandard complex inner product by 〈·, ·〉∗. Since 퐻 is diagonalizable, for the 푖훾-eigenspace of 퐻 withdimension 푘 , we can find 푘 linearly independent vectors that span the 푖훾-eigenspace. For each pairof these vectors, 풘 푗 ,풘′푗 , 〈풘 푗 ,풘′푗〉∗ = 0. By our previous argument, (휆+푖훾풘 푗 ,풘 푗), (휆+푖훾풘′푗 ,풘′푗) areeigenvectors of 퐽푂퐺퐴 with eigenvalue 휆+푖훾 . Taking the inner product of these vectors,〈(휆+푖훾풘 푗 ,풘 푗), (휆+푖훾풘′푗 ,풘′푗)〉∗ = |휆+푖훾 |2〈(풘 푗 ,풘 푗), (풘′푗 ,풘′푗)〉∗ = 0,and hence we can find 푘 linearly independent vectors which span the 휆+푖훾-eigenspace. Likewise,letting 휆−푖훾 =(12(1+√1−4휂2훾2)+ 푖휂훾), we can find 푘 linearly independent vectors that span the휆−푖훾-eigenspace.For each eigenspace of 퐻 with dimension 푘 , we get two eigenspaces of 퐽푂퐺퐴 with dimension푘 . Since the sum of the dimensions of the eigenspaces of 퐻 are equal to 푑, then the sum of thedimensions of the eigenspaces of 퐽푂퐺퐴 are equal to 2푑, and hence 퐽푂퐺퐴 is diagonalizable. Setting휂 = 12휌(퐻 ) , by Proposition 5.1 we have that for some problem specific 푐 > 0,푑 (풙푡+1, 푋∗)2 ≤ 푑 (풙푡+1,X∗)2 + 푑 (풙푡 ,X∗)2= 푑 ((풙푡+1,풙푡 ),X∗×X∗)2≤ 푐(휆max<1 (퐽OGA))2푡푑 ((풙1,풙0),X∗×X∗)2≤ 푐 ©­«12 + 12(1−(휔(퐻)휌(퐻))2) 12 ª®¬푡푟2.5.4.2 Omitted proofs from Section 5.2.2Lemma 5.3. In an NZSG with 훼-strongly concave payoffs with 훼 > 0, if a Nash equilibrium exists,it is unique.Proof. We will proceed by contradiction. Assume that there exist two strategy profiles, 풙ˆ, 풙˜ whichare Nash. By the definition of Nash we have∑푖∈푉(푝푖 (풙ˆ) − 푝푖 (풙˜푖 , 풙ˆ−푖)) ≥ 0.By the strong concavity of each player’s payoff in their strategy set,푝푖 (풙ˆ푖 , 풙˜−푖) ≤ 푝푖 (풙˜) + 〈∇풙푖 푝푖 (풙˜), 풙ˆ푖 − 풙˜푖〉 −훼2‖풙ˆ푖 − 풙˜푖 ‖2≤ 푝푖 (풙˜) − 훼2 ‖풙ˆ푖 − 풙˜푖 ‖2,47where the second inequality follows from the optimality of Nash. Summing over the players,∑푖∈푉푝푖 (풙ˆ푖 , 풙˜−푖) ≤∑푖∈푉(푝푖 (풙˜) − 훼2 ‖풙ˆ푖 − 풙˜푖 ‖2)≤ −훼2∑푖∈푉‖풙ˆ푖 − 풙˜푖 ‖2< 0,Where the last inequality follows from the fact that 풙ˆ ≠ 풙˜. Adding∑푖∈푉 푝푖 (풙ˆ) to the LHS, andapplying Lemma 5.1 to∑푖 푝(풙ˆ푖 , 풙˜푖),∑푖∈푉(푝푖 (풙ˆ) − 푝푖 (풙˜푖 , 풙ˆ푖)) < 0,which is a contradiction. Hence, the Nash of the game must be unique. Theorem 5.5. Consider an unconstrained NZSG that is 훽-smooth and has payoffs that are 훼-stronglyconcave with 훼 > 0. Assume the existence of a Nash, 풙∗. Let 풙0 ∈ X be such that∀푖 ∈푉, ‖풙0푖 −풙∗푖 ‖2 ≤ 푟for 푟 > 0. Then if each player updates her strategy according to GA with fixed learnig rate 휂 = 훼2훽2 , ateach time step 푡, ∑푖‖풙푡푖 − 풙∗푖 ‖22 ≤(1− 훼24훽2) 푡푛푟2.Proof. Expanding ‖풙푡+1푖 − 풙∗푖 ‖2, we have∑푖‖풙푡+1푖 − 풙∗푖 ‖2 =∑푖(‖풙푡푖 − 풙∗푖 ‖2 + ‖풙푡+1푖 − 풙푡푖 ‖2 +2〈풙푡+1푖 − 풙푡푖 ,풙푡푖 − 풙∗푖 〉)=∑푖(‖풙푡푖 − 풙∗푖 ‖2 + ‖풙푡+1푖 − 풙푡푖 ‖2 +2휂〈∇풙푖 푝푖 (풙푡 ),풙푡푖 − 풙∗푖 〉).By the strong concavity of 푝푖 ,〈∇풙푖 푝푖 (풙푡 ),풙푡푖 − 풙∗푖 〉 ≤ 푝푖 (풙푡 ) − 푝푖 (풙∗푖 ,풙푡−푖) −훼2‖풙푡푖 − 풙∗푖 ‖2.By Lemma 5.1, and since the game is zero sum,∑푖(푝푖 (풙푡 ) − 푝푖 (풙∗푖 ,풙푡−푖)) =∑푖(푝푖 (풙푡 ) + 푝푖 (풙푡푖 ,풙∗−푖)) (5.5)≤∑푖푝푖 (풙푡 ) +∑푖푝푖 (풙∗)= 0.48By the 훽-smoothness of the game,∑푖‖풙푡+1푖 − 풙푡푖 ‖2 = 휂2∑푖‖∇풙푖 푝푖 (풙푡 )‖2= 휂2∑푖‖∇풙푖 푝푖 (풙푡 ) −∇풙푖 푝푖 (풙∗)‖2≤ 휂2훽2∑푖‖풙푡푖 − 풙∗푖 ‖2.Putting everything together,∑푖‖풙푡+1푖 − 풙∗푖 ‖2 ≤ (1+휂2훽2−휂훼)∑푖‖풙푡푖 − 풙∗푖 ‖2.Plugging in 휂 = 훼2훽2 ,∑푖‖풙푡+1푖 − 풙∗푖 ‖2 ≤(1− 훼24훽2) ∑푖‖풙푡푖 − 풙∗푖 ‖2 ≤(1− 훼24훽2) 푡+1푛푟2.Theorem 5.6. Consider an unconstrained NZSG that is 훽-smooth and has payoffs that are 훼-stronglyconcavewith훼 > 0. Assume the existence of aNash, 풙∗. Let풘0 ∈ X be such that∀푖 ∈푉, ‖풘0푖 −풙∗푖 ‖2 ≤ 푟for 푟 > 0. Then if each player updates her strategy using EG with fixed learning rate 휂 ≤ 12훽 , at eachtime step 푡, ∑푖‖풘푡푖 − 풙∗푖 ‖22 ≤(1− 훼4훽) 푡푛푟2.Proof. We expand ‖풘푡+1푖 − 풙∗푖 ‖2 and ‖풙푡+1푖 − 풙푡+1푖 ‖2,∑푖‖풘푡+1푖 − 풙∗푖 ‖2 =∑푖(‖풘푡푖 − 풙∗푖 ‖2 +2휂〈∇풙푖 푝푖 (풙푡+1),풘푡+1푖 − 풙∗푖 〉 − ‖풘푡+1푖 −풘푡푖 ‖2), (5.6)∑푖‖풙푡+1푖 −풘푡+1푖 ‖2 =∑푖(‖풘푡푖 −풘푡+1푖 ‖2 +2휂〈∇풙푖 푝푖 (풘푡 ),풙푡+1푖 −풘푡+1푖 〉 − ‖풙푡+1푖 −풘푡푖 ‖2). (5.7)We expand the sum of inner products in each equation,〈∇풙푖 푝푖 (풙푡+1),풘푡+1푖 − 풙∗푖 〉 + 〈∇풙푖 푝푖 (풘푡 ),풙푡+1푖 −풘푡+1푖 〉=〈∇풙푖 푝푖 (풙푡+1),풙푡+1푖 − 풙∗푖 〉 + 〈∇풙푖 푝푖 (풘푡 ) −∇풙푖 푝푖 (풙푡+1),풙푡+1푖 −풘푡+1푖 〉. (5.8)We bound the first term in (5.8) using the strong concavity of 푝푖. As in (5.5) in the proof of49Theorem 5.5,∑푖〈∇풙푖 푝푖 (풙푡+1),풙푡+1푖 − 풙∗푖 〉 ≤ −훼2∑푖‖풙푡+1푖 − 풙∗푖 ‖2 +∑푖(푝푖 (풙푡+1) − 푝푖 (풙∗푖 ,풙푡+1−푖 ))≤ −훼2∑푖‖풙푡+1푖 − 풙∗푖 ‖2. (5.9)We bound the second term in (5.8),〈∇풙푖 푝푖 (풘푡 ) −∇풙푖 푝푖 (풙푡+1),풙푡+1푖 −풘푡+1푖 〉 ≤ ‖∇풙푖 푝푖 (풘푡 ) −∇풙푖 푝푖 (풙푡+1)‖‖풙푡+1−풘푡+1‖.By Claim A.1, for any 휌 > 0,∑푖‖∇풙푖 푝푖 (푤푡 ) −∇풙푖 푝푖 (풙푡+1)‖‖풙푡+1푖 −풘푡+1푖 ‖≤ 12휌∑푖‖∇풙푖 푝푖 (풘푡 ) −∇풙푖 푝푖 (풙푡+1)‖2 +휌2∑푖‖풙푡+1−풘푡+1‖2≤ 훽22휌∑푖‖풘푡푖 − 풙푡+1푖 ‖2 +휌2∑푖‖풙푡+1푖 −풘푡+1푖 ‖2, (5.10)where in the last line we use the 훽-smoothness of the game. Summing (5.6) and (5.7), and pluggingin (5.9) and (5.10),∑푖‖풘푡+1푖 − 풙∗푖 ‖2≤∑푖(‖풘푡푖 − 풙∗푖 ‖2−휂훼‖풙푡+1푖 − 풙∗푖 ‖2 +(훽2휂휌−1)‖풘푡푖 − 풙푡+1푖 ‖2 + (휂휌−1) ‖풙푡+1푖 −풘푡+1푖 ‖2). (5.11)Using Young’s inequality,−휂훼‖풙푡+1푖 − 풙∗푖 ‖2 ≤ −휂훼2‖풘푡푖 − 풙∗푖 ‖2 +휂훼‖풘푡푖 − 풙푡+1푖 ‖2. (5.12)Plugging in (5.12) and setting 휌 = 1휂 ,∑푖‖풘푡+1푖 − 풙∗푖 ‖2 ≤∑푖((1− 휂훼2)‖풘푡푖 − 풙∗푖 ‖2 + (훽2휂2 +휂훼−1)‖풙푡푖 − 풙푡+1푖 ‖2).For 휂 ≤ 12훽 , 훽2휂2 +휂훼−1 ≤ − 14 , and thus,∑푖‖풘푡+1푖 − 풙∗푖 ‖2 ≤(1− 훼4훽) 푡+1푛푟2.Theorem 5.7. Consider an unconstrained NZSG that is 훽-smooth and has payoffs that are 훼-50strongly concave with 훼 > 0. Assume the existence of a Nash, 풙∗. Let 풙0,풙1 ∈ X be such that∀푖 ∈ 푉,풙1푖 = 풙0 +휂∇풙푖 푝푖 (풙0), and ‖풙0푖 − 풙∗푖 ‖2 ≤ 푟 for 푟 > 0. Then if each player updates her strategyusing OGA, with fixed learning rate 휂 = 14훽 , at each time step 푡,∑푖‖풙푡푖 − 풙∗푖 ‖22 ≤ 4(1− 훼8훽) 푡푛푟2.Proof. Recall that OGA is simply OMD with adaptive predictor M푡푖 ∈ 휕풙푖 푝푖 (풙푡 ), whereas EG isOMD with adaptive predictorM푡푖 ∈ 휕풙푖 푝푖 (풘푡 ). Consider (5.11) from the proof of Theorem 5.6. In asimilar fashion, for the OGA iterates we would have∑푖‖풘푡+1푖 − 풙∗푖 ‖2 ≤∑푖(‖풘푡푖 − 풙∗푖 ‖2− ‖풘푡푖 − 풙푡+1푖 ‖ −휂훼‖풙푡+1푖 − 풙∗푖 ‖2+ 훽2휂휌‖풙푡푖 − 풙푡+1푖 ‖2 + (휂휌−1) ‖풙푡+1푖 −풘푡+1푖 ‖2).Using Young’s inequality,−휂훼‖풙푡+1푖 − 풙∗푖 ‖ ≤ −휂훼2‖풘푡푖 − 풙∗푖 ‖2 +휂훼‖풙푡+1푖 −풘푡푖 ‖2.And using it again,‖풙푡+1푖 − 풙푡푖 ‖2 ≤ 2‖풙푡+1푖 −풘푡푖 ‖2 +2‖풙푡푖 −풘푡푖 ‖2.Plugging both of these in and rearranging,∑푖(‖풘푡+1푖 − 풙∗푖 ‖2 + (1−휂휌) ‖풙푡+1푖 −풘푡+1푖 ‖2)≤∑푖((1− 휂훼2)‖풘푡푖 − 풙∗푖 ‖2 +2훽2휂휌‖풙푡푖 −풘푡푖 ‖2 +(2훽2휂휌+휂훼−1)‖풘푡푖 − 풙푡+1푖 ‖2)For 휌 = 12휂 , and 휂 ≤ 14훽 we have 2훽2휂휌 ≤ 12(1− 휂훼2)and 2휂훽2휌 +휂훼−1 ≤ − 58 . Thus we have∑푖(‖풘푡+1푖 − 풙∗푖 ‖2 +12‖풙푡+1푖 −풘푡+1푖 ‖2)≤(1− 훼8훽) ∑푖(‖풘푡푖 − 풙∗푖 ‖2 +12‖풙푡푖 −풘푡푖 ‖2)≤(1− 훼8훽) 푡+1 ∑푖(‖풘0푖 − 풙∗푖 ‖2 +12‖풙0푖 −풘0푖 ‖2)≤(1− 훼8훽) 푡+1푛푟2.51In order to bound the main iterates 풙푡+1푖 , we use Young’s inequality,∑푖‖풙푡+1푖 − 풙∗푖 ‖2 ≤ 4∑푖(‖풘푡+1푖 − 풙∗푖 ‖2 +12‖풙푡+1푖 −풘푡+1푖 ‖2)≤ 4(1− 훼8훽) 푡+1푛푟2.5.4.3 Omitted proofs from Section 5.2.3Proposition 5.2. Consider an NZSG such that each player’s payoff is 훼-strongly concave in theirstrategy for some 훼 ≥ 0. Then v is 훼-strongly monotone.Proof. For any 푛-player game,〈v(풙) −v(풙′),풙′− 풙〉 =∑푖〈∇풙푖 푝푖 (풙) −∇풙푖 푝푖 (풙′),풙′푖 − 풙푖〉.Since 푝푖 is 훼-strongly concave we have푝푖 (풙′푖 ,풙−푖) ≤ 푝푖 (풙) + 〈∇풙푖 푝푖 (풙),풙′푖 − 풙푖〉 −훼2‖풙푖 − 풙′푖 ‖2 (5.13)푝푖 (풙푖 ,풙′−푖) ≤ 푝푖 (풙′) + 〈∇풙푖 푝푖 (풙′),풙푖 − 풙′푖〉 −훼2‖풙푖 − 풙′푖 ‖2. (5.14)Adding equations (5.13) and (5.14), and summing over the players, we have∑푖(푝푖 (풙′푖 ,풙−푖) + 푝푖 (풙푖 ,풙′−푖))≤∑푖(푝푖 (풙) + 푝푖 (풙′) + 〈∇풙푖 푝푖 (풙) −∇풙푖 푝푖 (풙′),풙′푖 − 풙푖〉 −훼‖풙푖 − 풙′푖 ‖2)=∑푖(〈∇풙푖 푝푖 (풙) −∇풙푖 푝푖 (풙′),풙′푖 − 풙푖〉 −훼‖풙푖 − 풙′푖 ‖2), (5.15)where the last line follows from the fact that the game is zero sum. Furthermore, by Lemma 5.1,∑푖(푝푖 (풙′푖 ,풙−푖) + 푝푖 (풙푖 ,풙′−푖)) =∑푖(푝푖 (풙′푖 ,풙−푖) − 푝푖 (풙′푖 ,풙−푖)) = 0.Rearranging (5.15) gives the desired conclusion. Theorem 5.8. Consider an 푛-player game with 퐿-Lipschitz payoffs and a monotone gradient operator.Assume that ∀푖 ∈ 푉,X푖 ⊆ R푑푖 is convex and compact. Let 풘0,풙0 ∈ X and assume that D휙 (풙∗,풘0)is finite. Then if at every time step 푡, each player updates her strategy using OMD with step size52휂푡 ≤ ‖풙푡−풘푡 ‖4퐿 ,lim푡→∞D휙 (풙∗,풘푡 ) = 0.Proof. By Bregman Triangle Equality,D휙 (풙∗,풘푡 ) = D휙 (풙∗,풘푡−1) −D휙 (풘푡 ,풘푡−1) +휂푡 〈∇휙(풘푡 ) −∇휙(풘푡−1),풘푡 − 풙∗〉 (5.16)D휙 (풘푡 ,풙푡 ) = D휙 (풘푡 ,풘푡−1) −D휙 (풙푡 ,풘푡−1) +휂푡 〈∇휙(풙푡 ) −∇휙(풘푡−1),풙푡 −풘푡〉. (5.17)By the optimality of 풘푡푖 ,〈∇풙푖 푝푖 (풙푡푖 ) −∇휙푖 (풘푡푖 ) +∇휙푖 (풘푡−1푖 ),풙∗푖 −풘푡푖 〉 ≤ 0,and therefore,〈∇휙(풘푡 ) −∇휙(풘푡−1),풘푡 − 풙∗〉 ≤ 〈v(풙푡 ),풘푡 − 풙∗〉.Likewise, 〈∇휙(풙푡 ) −∇휙(풘푡−1),풙푡 −풘푡〉 ≤ 〈M푡 ,풙푡 −풘푡〉. Summing (5.16) and (5.17),D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1) (5.18)≤−D휙 (풘푡 ,풙푡 ) −D휙 (풙푡 ,풘푡−1) +휂푡(〈v(풙푡 ),풘푡 − 풙∗〉 + 〈M푡 ,풙푡 −풘푡〉) . (5.19)Using the optimality of 풙∗, the 퐿-Lipschitzness of 퐺 and the monotonicity of v we have〈v(풙푡 ),풘푡 − 풙∗〉 + 〈M푡 ,풙푡 −풘푡〉 ≤ 〈v(풙푡 ) −v(풙∗),풙푡 − 풙∗〉 + 〈M푡 −v(풙푡 ),풙푡 −풘푡〉≤ 2퐿‖풙푡 −풘푡 ‖.Plugging this back in to (5.19),D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1) ≤ −D휙 (풘푡 ,풙푡 ) −D휙 (풙푡 ,풘푡−1) +2퐿휂푡 ‖풙푡 −풘푡 ‖.Setting 휂푡 ≤ ‖풙푡−풘푡 ‖4퐿 , and using the fact that D휙 (풙,풙′) ≥ 12 ‖풙− 풙′‖2,D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1) ≤ −D휙 (풙푡 ,풘푡−1) < 0.Since the Bregman Divergence is strictly decreasing at each iteration, and D휙 (풙∗,풙0) is finite, wehave last iterate convergence. Theorem 5.9. Consider an 푛-player game that is 훽-smooth and has an 훼-strongly monotone gradientoperator with 훼 > 0. Assume that ∀푖 ∈ 푉,X푖 ⊆ R푑푖 is convex and compact. Let 풘0,풙0 ∈ X. Then if atevery time step 푡, each player updates her strategy using OMDwith adaptive predictorM푡푖 =∇풙푖 푝푖 (풘푡푖 )53and step size 휂푡 ≤ 14훽 ,D휙 (풙∗,풘푡 ) ≤ D휙 (풙∗,풘푡−1) − 훼8훽 ‖풘푡−1− 풙∗‖2.Proof. Consider (5.19) from the proof of Theorem 5.8 withM푡 = v(풘푡−1),D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1)=−D휙 (풘푡 ,풙푡 ) −D휙 (풙푡 ,풘푡−1) +휂푡(〈v(풙푡 ),풘푡 − 풙∗〉 + 〈v(풘푡−1),풙푡 −풘푡〉). (5.20)Using the optimality of 풙∗, and the 훼-strong monotonicity of v,〈v(풙푡 ),풘푡 − 풙∗〉 + 〈v(풘푡−1),풙푡 −풘푡〉 ≤〈v(풙푡 ) −v(풙∗),풙푡 − 풙∗〉 + 〈v(풘푡−1) −v(풙푡 ),풙푡 −풘푡〉≤−훼‖풙푡 − 풙∗‖2 + ‖v(풘푡−1) −v(풙푡 )‖‖풙푡 −풘푡 ‖.By Claim A.1 for any 휌 > 0,‖v(풘푡−1) −v(풙푡 )‖‖풙푡 −풘푡 ‖ ≤ 12휌‖v(풘푡−1) −v(풙푡 )‖2 + 휌2‖풙푡 −풘푡 ‖2≤ 훽22휌‖풘푡−1− 풙푡 ‖2 + 휌2‖풙푡 −풘푡 ‖2,where in the last line we used the 훽-Lipschitzness of v. Plugging back into (5.20),D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1)≤ −D휙 (풘푡 ,풙푡 ) −D휙 (풙푡 ,풘푡−1) −휂푡훼‖풙푡 − 풙∗‖2 + 훽2휂푡2휌‖풙푡 −풘푡−1‖2 + 휂푡 휌2‖풙푡 −풘푡 ‖2 (5.21)≤ (휂푡 휌−1)D휙 (풘푡 ,풙푡 ) +(훽2휂푡휌−1)D휙 (풙푡 ,풘푡−1) −휂푡훼‖풙푡 − 풙∗‖2. (5.22)Using Young’s inequality,−휂푡훼‖풙푡 − 풙∗‖ ≤ 휂푡훼2 ‖풘푡−1− 풙∗‖2−휂푡훼‖풙푡 −풘푡−1‖2. (5.23)Setting 휌 = 1휂푡 in (5.22) and plugging in (5.23),D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1) ≤(훽2휂2푡 +2휂푡훼−1)D휙 (풙푡 ,풘푡−1) − 휂푡훼2 ‖풘푡−1− 풙∗‖2.Setting 휂푡 ≤ 14훽 , we have 훽2휂2푡 +2휂푡훼−1 ≤ − 716 , and,D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1) ≤ − 훼8훽 ‖풘푡−1− 풙∗‖2.54Theorem 5.10. Consider an 푛-player game that is 훽-smooth and has an 훼-strongly monotone gradientoperator with 훼 > 0. Assume that ∀푖 ∈ 푉,X푖 ⊆ R푑푖 is convex and compact. Let 풘0,풙0 ∈ X. Then if atevery time step 푡, each player updates her strategy using OMDwith adaptive predictorM푡푖 = ∇풙푖 푝푖 (풙푡 )and step size 휂푡 ≤ 14훽 ,D휙 (풙∗,풘푡 ) + 14 ‖풙푡 −풘푡 ‖2 ≤ D휙 (풙∗,풘푡−1) + 14(1− 훼4훽)‖풙푡−1−풘푡−1‖2− 훼8훽‖풘푡−1− 풙∗‖2.Proof. Consider (5.21) from the proof of Theorem 5.9 withM푡 = v(풙푡−1),D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1)≤ −D휙 (풘푡 ,풙푡 ) −D휙 (풙푡 ,풘푡−1) −휂푡훼‖풙푡 − 풙∗‖2 + 훽2휂푡2휌‖풙푡 − 풙푡−1‖2 + 휂푡 휌2‖풙푡 −풘푡 ‖2≤12(휂푡 휌−1) ‖풙푡 −풘푡 ‖ −D휙 (풙푡 ,풘푡−1) −휂푡훼‖풙푡 − 풙∗‖2 + 훽2휂푡2휌‖풙푡 − 풙푡−1‖2. (5.24)Using Young’s inequality,−휂푡훼‖풙푡 − 풙∗‖ ≤ −휂푡훼2 ‖풘푡−1− 풙∗‖2 +휂푡훼‖풙푡 −풘푡−1‖2,and using it again,‖풙푡 − 풙푡−1‖2 ≤ 2‖풙푡 −풘푡−1‖2 +2‖풙푡−1−풘푡−1‖2.Plugging both of these back into (5.24),D휙 (풙∗,풘푡 ) −D휙 (풙∗,풘푡−1)≤12(휂푡 휌−1) ‖풙푡 −풘푡 ‖2− 휂푡훼2 ‖풘푡−1− 풙∗‖2 +(휂푡훼+ 훽2휂휌− 12)‖풙푡 −풘푡−1‖2+ 훽2휂푡휌‖풙푡−1−풘푡−1‖2.Rearranging,D휙 (풙∗,풘푡 ) + 12 (1−휂푡 휌) ‖풙푡 −풘푡 ‖2≤D휙 (풙∗,풘푡−1) + 훽2휂푡휌‖풙푡−1−풘푡−1‖2 +(휂푡훼+ 훽2휂푡휌− 12)‖풙푡 −풘푡−1‖2− 휂푡훼2‖풘푡−1− 풙∗‖2.Setting 휌 = 12휂푡 and 휂푡 ≤ 14훽 , we have that훽2휂푡휌 ≤ 14 (1−휂푡훼) and 휂푡훼+2훽2휂2푡 − 12 ≤ − 34 . Therefore,D휙 (풙∗,풘푡 ) + 14 ‖풙푡 −풘푡 ‖2 ≤ D휙 (풙∗,풘푡−1) + 14(1− 훼4훽)‖풙푡−1−풘푡−1‖2− 훼8훽‖풘푡−1− 풙∗‖2.55Chapter 6ConclusionIn this paper, we studied the convergence of player strategies to equilibria in network zero-sumgames, a class of games that generalizes two-player zero-sum games and arises naturally in learningarchitectures that extend GANs. We show that many results in two-player zero-sum games on theconvergence and divergence of these algorithms extend to NZSGs. We believe these results may guidepractitioners working on extensions of GANs that involve more than two agents. Our results alsoshed some light on why existing extensions of GANs that employ more than two agents are successfulin achieving convergent behaviour. Future research may search for models with more relaxed gametheoretic assumptions where convergence can still be shown for reasonable algorithms. For example,the zero-sum assumption is absent from certain successful architectures, e.g. Wasserstein-GAN withGradient Penalty [18].56Bibliography[1] Z. Allen-Zhu and L. Orecchia. Linear coupling: An ultimate unification of gradient and mirrordescent. In Innovations in Theoretical Computer Science Conference, 2017. → page 9[2] W. Azizian, I. Mitliagkas, S. Lacoste-Julien, and G. Gidel. A unified analysis of gradient-basedmethods for a whole spectrum of games. In The International Conference on ArtificialIntelligence and Statistics, 2020. → pages 29, 30, 37, 38, 39[3] J. P. Bailey and G. Piliouras. Multiplicative weights update in zero-sum games. In ACMConference on Economics and Computation, 2018. → page 12[4] N. Bof, R. Carli, and L. Schenato. Lyapunov theory for discrete time systems. arXiv preprintarXiv:1809.05289, 2018. → page 8[5] A. Brock, T. Lim, J. Ritchie, and N. Weston. Neural photo editing with introspective adversarialnetworks. In International Conference on Learning Representations, 2017. → page 1[6] S. Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends®in Machine Learning, 8(3-4):231–357, 2015. → pages 6, 9[7] Y. Cai, O. Candogan, C. Daskalakis, and C. Papadimitriou. Zero-sum polymatrix games: Ageneralization of minmax. Mathematics of Operations Research, 41(2):648–655, 2016. →pages 2, 26, 27, 28, 32, 33[8] T. Che, Y. Li, A. P. Jacob, Y. Bengio, and W. Li. Mode regularized generative adversarialnetworks. In International Conference on Learning Representations, 2017. → page 1[9] L. Chongxuan, T. Xu, J. Zhu, and B. Zhang. Triple generative adversarial nets. In Advances inNeural Information Processing Systems, 2017. → pages 1, 25[10] C. Daskalakis and I. Panageas. The limit points of (optimistic) gradient descent in min-maxoptimization. In Advances in Neural Information Processing Systems, 2018. → pages 2, 36[11] C. Daskalakis and I. Panageas. Last-Iterate Convergence: Zero-Sum Games and ConstrainedMin-Max Optimization. In Innovations in Theoretical Computer Science Conference, volume124 of Leibniz International Proceedings in Informatics, pages 1–27, 2018. → page 2[12] C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. The complexity of computing a nashequilibrium. SIAM Journal on Computing, 39(1):195–259, 2009. → page 26[13] C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng. Training GANs with optimism. InInternational Conference on Learning Representations, 2018. → pages 2, 12, 3457[14] J. Donahue, P. Krähenbühl, and T. Darrell. Adversarial feature learning. In InternationalConference on Learning Representations, 2017. → page 1[15] G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien. A variational inequalityperspective on generative adversarial networks. In International Conference on LearningRepresentations, 2019. → pages 1, 39[16] I. Goodfellow. Nips 2016 tutorial: Generative adversarial networks. arXiv preprintarXiv:1701.00160, 2016. → page 1[17] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, andY. Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems,2014. → page 1[18] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville. Improved training ofWasserstein GANs. In Advances in Neural Information Processing Systems, 2017. → page 56[19] J. K. Hale and H. Koçak. Dynamics and bifurcations, volume 3. Springer Science & BusinessMedia, 2012. → page 42[20] Q. Hoang, T. D. Nguyen, T. Le, and D. Phung. MGAN: Training generative adversarial netswith multiple generators. In International Conference on Learning Representations, 2018. →page 1[21] R. A. Horn and C. R. Johnson. Topics in matrix analysis. Cambridge university press, 1994. →pages 43, 45[22] A. Kadan and H. Fu. Exponential convergence of gradient methods in concave networkzero-sum games. In European Conference on Machine Learning, 2020. → page v[23] A. B. L. Larsen, S. K. Sønderby, H. Larochelle, and O. Winther. Autoencoding beyond pixelsusing a learned similarity metric. In International Conference on Machine Learning, 2016. →pages 24, 25[24] T. Liang and J. Stokes. Interaction matters: A note on non-asymptotic local convergence ofgenerative adversarial networks. In The International Conference on Artificial Intelligence andStatistics, pages 907–915, 2019. → pages 1, 2, 12, 13, 14, 16, 17, 34[25] I. Menache and A. Ozdaglar. Network games: Theory, models, and dynamics. SynthesisLectures on Communication Networks, 4(1):1–159, 2011. → page 33[26] P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras.Optimistic mirror descent in saddle-point problems: Going the extra(-gradient) mile. InInternational Conference on Learning Representations, 2019. → pages15, 16, 21, 22, 29, 34, 39[27] A. Mokhtari, A. Ozdaglar, and S. Pattathil. A unified analysis of extra-gradient and optimisticgradient methods for saddle point problems: Proximal point approach. In The InternationalConference on Artificial Intelligence and Statistics, 2020. → pages 1, 2, 14, 15, 18, 30, 38, 39[28] A. Odena. Semi-supervised learning with generative adversarial networks. arXiv preprintarXiv:1606.01583, 2016. → page 2558[29] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, and X. Chen. Improvedtechniques for training gans. In Advances in Neural Information Processing Systems, 2016. →page 25[30] S. Vandenhende, B. De Brabandere, D. Neven, and L. Van Gool. A three-player gan:generating hard samples to improve classification networks. In International Conference onMachine Vision Applications, 2019. → page 1[31] X. Zhan. Matrix inequalities. Springer, 2004. → page 6059Appendix AStandard ResultsLemma A.1 (Young’s Inequality). Let 풘1, . . . ,풘푛 ∈ R푘 . Then,∑푛푖 풘푖2 ≤ 푛∑푛푖 ‖풘푖 ‖2.Lemma A.2 (Cauchy-Schwartz Inequality). Let 풙,풘 ∈ R푘 . Then, |〈풙,풘〉| ≤ ‖풙‖‖풘‖.Lemma A.3 ([31]). Let 퐴, 퐵 ∈ R푘×푘 be two symmetric matrices. Then, 휆max(퐴+ 퐵) ≤ 휆max(퐴) +휆max(퐵).Lemma A.4 ([31]). Let 풙 ∈ R푘 , and 퐴 ∈ R푘×푘 . Then, ‖퐴풙‖2 ≥ 휎min(퐴)‖풙‖2, and ‖퐴풙‖2 ≤휎max(퐴)‖풙‖2.Claim A.1. Let 푎, 푏 ∈ R. Then for any 휌 > 0, 푎푏 ≤ 12휌푎2 + 휌2 푏2.Proof. Let ℎ(휌) = 12휌푎2 + 휌2 푏2. First note that for 휌 > 0, this function is convex since ℎ′′(휌) > 0.Setting ℎ′(휌) = −푎22휌2 + 푏22 = 0, and solving for the minimizer, we get the desired result. 60
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Last iterate convergence in network zero-sum games
Text