Abstract:

Abstract: Many modern machine learning tasks can be modeled as games involving multiple players, where each player is represented by a machine learning model. Examples include GANs and the AI Go program AlphaGo. In these settings, machine learning models refine their performance by learning from feedback influenced by all players’ strategies, aiming to reach an equilibrium. This equilibrium computation problem has long been a central topic in economics. Traditionally, the design of equilibrium computation algorithms has been constrained by economic principles to ensure interpretability for rational human agents. However, in the machine learning era, the players in these games are neural networks rather than human, making such constraints less relevant. For example, a widely used equilibrium computation algorithms in machine learning is Adam, which is derived from optimization concepts such as momentum rather than economic principles. Despite their success, our theoretical understanding of these machine-learning-driven equilibrium computation algorithms remains incomplete.

This project aims to develop a systematic study of practical used equilibrium computation algorithms in machine learning, with a primary focus on the role of momentum. Recognized as one of the most influential ideas in modern optimization, momentum is a key feature that differentiates machine-learning-driven equilibrium algorithms from those rooted in economic theory. Our approach emphasizes a continuous-time perspective on momentum in equilibrium computation, which approximates the trajectories of these algorithms through continuous-time differential equations to gain insights into their dynamics. As a first step, I have used this approach to analyze Polyak’s momentum in two-player zero-sum games and discovered new phenomena that highlight the unique role of momentum in equilibrium computation. The next steps are to extend these findings to multi-player games and explore their connection to non-convex optimization theory.

Understanding the efficiency of algorithms in game-theoretical systems is essential in the machine learning era. For example, in autonomous driving, the lack of theoretical guarantees can lead to catastrophic consequences. This project seeks to provide a theoretical understanding of practically used equilibrium computation algorithms that have had a significant impact on machine learning tasks. The outcome of this project also has the potential to guide future algorithm design.