Last iterate convergence in network zero-sum games
department or school: Science, Faculty of
department or school: Computer Science, Department of
data provider: DSpace
degree campus: UBCV
creator: Kadan, Amit
issued: 2021-01-11T23:47:34Z
issued: 2020
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: 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.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/77049
note: 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 train…
has type: Thesis/Dissertation
date issued: 2021-05
is shown at: 10.14288/1.0395553
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
type: Text
identifier URI: http://hdl.handle.net/2429/77049