Timezone: »
Poster
Global Convergence to Local Minmax Equilibrium in Classes of Nonconvex Zero-Sum Games
Tanner Fiez · Lillian Ratliff · Eric Mazumdar · Evan Faulkner · Adhyyan Narang
We study gradient descent-ascent learning dynamics with timescale separation ($\tau$-GDA) in unconstrained continuous action zero-sum games where the minimizing player faces a nonconvex optimization problem and the maximizing player optimizes a Polyak-Lojasiewicz (PL) or strongly-concave (SC) objective. In contrast to past work on gradient-based learning in nonconvex-PL/SC zero-sum games, we assess convergence in relation to natural game-theoretic equilibria instead of only notions of stationarity. In pursuit of this goal, we prove that the only locally stable points of the $\tau$-GDA continuous-time limiting system correspond to strict local minmax equilibria in each class of games. For these classes of games, we exploit timescale separation to construct a potential function that when combined with the stability characterization and an asymptotic saddle avoidance result gives a global asymptotic almost-sure convergence guarantee for the discrete-time gradient descent-ascent update to a set of the strict local minmax equilibrium. Moreover, we provide convergence rates for the gradient descent-ascent dynamics with timescale separation to approximate stationary points.
Author Information
Tanner Fiez (University of Washington)
Lillian Ratliff (University of Washington)
Eric Mazumdar (UC Berkeley EECS)
Evan Faulkner (University of Washington)
Adhyyan Narang (University of Washington, Seattle)
More from the Same Authors
-
2022 Poster: Instance-optimal PAC Algorithms for Contextual Bandits »
Zhaoqi Li · Lillian Ratliff · houssam nassif · Kevin Jamieson · Lalit Jain -
2021 : Closing the loop in Machine Learning: Learning to optimize with decision dependent data »
Lillian Ratliff -
2021 Workshop: Learning and Decision-Making with Strategic Feedback (StratML) »
Yahav Bechavod · Hoda Heidari · Eric Mazumdar · Celestine Mendler-Dünner · Tijana Zrnic -
2021 Poster: Who Leads and Who Follows in Strategic Classification? »
Tijana Zrnic · Eric Mazumdar · Shankar Sastry · Michael Jordan -
2021 Poster: Online Learning in Periodic Zero-Sum Games »
Tanner Fiez · Ryann Sim · Stratis Skoulakis · Georgios Piliouras · Lillian Ratliff -
2021 Poster: Towards Sample-efficient Overparameterized Meta-learning »
Yue Sun · Adhyyan Narang · Ibrahim Gulluk · Samet Oymak · Maryam Fazel -
2019 : Contributed talk: Characterizing Equilibria in Stackelberg Games »
Tanner Fiez -
2019 Poster: Sequential Experimental Design for Transductive Linear Bandits »
Lalit Jain · Kevin Jamieson · Tanner Fiez · Lillian Ratliff