Speaker: Weiqiang Zheng
Date: March 7, 2025
Time: 10:00 - 11:30am
Location: Rice Hall 204
Title: Efficient Online Learning and Equilibrium Computation in Non-Concave Games
Abstract:
Many modern applications and outstanding challenges in machine learning can be modeled as games between multiple self-interested agents with high-dimension and non-concave utilities. Examples include systems with explicit strategic behaviors like multi-agent reinforcement learning and auto-bidding in advertising auctions and ML applications that can be implicitly modeled as games like training generative models and robust optimization. This new multi-agent learning paradigm emerges as non-concave games, introduce significant game-theoretic and optimization challenges: (1) Nash equilibria may not exist; (2) local Nash equilibria exist but are computationally intractable; (3) mixed Nash, (coarse) correlated equilibria generally have infinite support and are intractable. To sidestep these challenges, we consider the classical solution concept of Φ-equilibria, where players only consider deviations in the set Φ. While Φ-equilibria always exist, its tractability in non-concave games is underexplored. I will discuss in this talk the tractability of Φ-equilibria, presenting both upper and lower bounds.
1. When Φ is finite, we give an efficient randomized online learning algorithm to minimize Φ-regret, thus giving efficient uncoupled learning dynamics for approximate Φ-equilibria.
2. When Φ is infinite, we give a hardness result even when Φ contains only local deviations. This result also implies the hardness of computing an approximate local minimizer of a quadratic function over a polytope.
3. I will also show that the the simple gradient descent algorithm efficiently minimizes a class of infinte many Φ that lies between external regret and swap regret.
This talk is based on a joint work with Yang Cai, Costis Daskalakis, Haipeng Luo, and Chen-Yu Wei.
Bio:
Weiqiang Zheng is a fourth-year computer science PhD student at Yale University, advised by Prof. Yang Cai. He received his bachelor's degree from Turing Class, Peking University. His has a broad interest in algorithmic game theory, online learning, and optimization. His recent research focuses on developing fast algorithms for minimax optimization, reinforcement learning, and learning in games, as well as their applications.
Zoom: https://virginia.zoom.us/j/96766029165?pwd=11P7wb50XH3YbwjXmBiR9ZZHquZvqY.1
Meeting ID: 967 6602 9165
Passcode: 188441