Novel first-order methods for bilevel and minimax optimization.

Abstract

Bilevel and minimax optimization problems arise in various fields, including machine learning, game theory, and decision science. This thesis highlights the underlying connections between constrained minimax and bilevel optimization and develops novel first-order methods with strong theoretical guarantees for solving both classes of problems. Specifically, we study a class of constrained minimax problems and propose efficient augmented Lagrangian methods with complexity guarantees for both nonconvex-concave and nonconvex–strongly-concave objective functions. We then show that bilevel optimization can be approximately reformulated as a minimax problem and introduce first-order penalty methods with provable complexity guarantees. Additionally, we propose a sequential minimax optimization method for solving a class of constrained bilevel problems and establish corresponding complexity results. Preliminary numerical experiments demonstrate the effectiveness of the proposed methods.