BIG Hype: Best Intervention in Games via Distributed Hypergradient Descent

Abstract: 
Hierarchical decision making problems, such as bilevel programs and Stackelberg games, are attracting increasing interest in both the engineering and machine learning communities. Yet, existing solution methods lack either convergence guarantees or computational efficiency, due to the absence of smoothness and convexity. In this work, we bridge this gap by designing BIG Hype, a first-order hypergradient-based algorithm for Stackelberg games, and mathematically establishing its convergence using tools from nonsmooth analysis. To evaluate the hypergradient, namely, the gradient of the upper-level objective, we develop an online scheme that simultaneously computes the lower-level equilibrium and its Jacobian. We demonstrate BIG Hype’s potential by deploying it on various large-scale bilevel problems, such as demand response, traffic routing, and recommender systems.

Bio sketch:
Panagiotis Grontas is a doctoral student in the Automatic Control Laboratory (IfA) at ETH Zürich, supervised by John Lygeros. He received an M.Sc. degree with distinction in Robotics, Systems, and Controls from ETH Zürich, and a Diploma degree in Mechanical Engineering from the National Technical University of Athens. He is a recipient of the ETH Medal for outstanding Master’s theses and the IEEE CSS Swiss Chapter Young Author Best Journal Paper Award 2025. His research is focused on the broad intersection of optimization, machine learning, and control.