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, introducing significant game-theoretic and optimization challenges: (1) Nash equilibria may not exist; (2) local Nash equilibria exist but are computationally intractable; (3) mixed Nash and (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.

When is finite, we give an efficient randomized online learning algorithm to minimize -regret, thus giving efficient uncoupled learning dynamics for approximate -equilibria.

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.

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

2025-05-26  14:00 - 15:00

Speaker

Weiqiang Zheng, Yale University

Room

Room 102