Efficient Online Learning and Equilibrium Computation in Non-Concave Games
- Weiqiang Zheng, Yale University
- Time: 2025-05-28 15:00
- Host: Turing Class Research Committee
- Venue: Room 204, Courtyard No.5, Jingyuan
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 $\Phi$-equilibria, where players only consider deviations in the set $\Phi$. While $\Phi$-equilibria always exist, its tractability in non-concave games is underexplored. I will discuss in this talk the tractability of $\Phi$-equilibria, presenting both upper and lower bounds.
1. When $|\Phi|$ is finite, we give an efficient randomized online learning algorithm to minimize $\Phi$-regret, thus giving efficient uncoupled learning dynamics for approximate $\Phi$-equilibria.
2. When $|\Phi|$ is infinite, we give a hardness result even when $\Phi$ contains only local deviations. This result also implies the NP-hardness of computing an approximate local minimizer of a quadratic function over a polytope.
3. We also uncover a surprising and previously unrecognized property of the widely used algorithm online gradient descent, demonstrating its ability to minimize a new class of regret—proximal regret—which generalizes external regret as a special case.
This talk is based on a joint work with Yang Cai, Costis Daskalakis, Haipeng Luo, and Chen-Yu Wei.
Biography
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 for LLM alignment. He has been recognized as a 2025 KAUST rising star in AI.