CS Peer Talk | Efficient Online Learning...

报告人：Weiqiang Zheng, Yale University

时间：5月28日（星期三）3:00pm

地点：静园五院204

Host：方嘉聪 图灵班2022级

Efficient Online Learning and Equilibrium Computation in Non-Concave Games

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.

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.

北京大学图灵班科研活动委员会