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 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.

Time

Monday, May. 26, 14:00--15:00

Speaker

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.

Weiqiang Zheng

Room

Room 102