Please note: This seminar will be given online.
Emmanouil-Vasileios Vlatakis-Gkaragkounis
Department of Computer Science, Columbia University
Host: Professor Gautam Kamath
Motivated by recent advances in both theoretical and applied aspects of multiplayer games, spanning from e-sports to multi-agent generative adversarial networks, a surge of different studies has been focused on the core problem of understanding the behavior of game dynamics in general N-player games. From the seminal settings of two competitive players and Min-Max Optimization to the complete understanding of how the day-to-day behavior of the dynamics correlates to the game’s different notion of equilibria is much more limited, and only partial results are known for certain classes of games (such as zero-sum or congestion games).
In this talk, we study from two different perspectives arguably the most well-studied class of no-regret dynamics, “Follow-the-regularized-leader” (FTRL) and Discretizations of Gradient Flow (GDA/OGDA/EG), and we establish a sweeping negative result showing that the notion of mixed Nash equilibrium is antithetical to no-regret learning. Specifically, we show that any Nash equilibrium which is not strict (in that every player has a unique best response) cannot be stable and attracting under the dynamics of FTGL. This result has significant implications for predicting the outcome of a learning process as it shows unequivocally that only strict (and hence, pure) Nash equilibria can emerge as stable limit points thereof.
For a final happy end story, we present either structural examples of families where convergence is possible providing the last-iterate convergence rates or even new methods inspired from other areas like control theory & planning.
Bio: Emmanouil (Manolis) V. Vlatakis Gkaragkounis is a final year PhD student in the Department of Computer Science at Columbia University, under the supervision of Profs Mihalis Yannakakis and Rocco Servedio. Currently, he is Simons-Google Research fellow at the University of California at Berkeley. Before joining Columbia University, he interned at “Athena” Research & Innovation Center in Athens, Greece.
He received his integrated B.s & M.s in ECE Department of National Technical University of Athens, where he was advised by Dimitris Fotakis. Manolis’s primary interest is in the intersection of Theoretical Computer Science & Machine Learning, with a particular focus in Algorithmic Game Theory, Optimization, Computational Complexity and Beyond Worst-case Analysis of Algorithms.