Convex-Concave Min-Max Stackelberg Games

Abstract

Min-max optimization problems (i.e., min-max games) have been attracting a great deal of attention because of their applicability to a wide range of machine learning problems. Although significant progress has been made recently, the literature to date has focused on games with independent strategy sets; little is known about solving games with dependent strategy sets, which can be characterized as min-max Stackelberg games. We introduce two first-order methods that solve a large class of convex-concave min-max Stackelberg games, and show that our methods converge in polynomial time. Min-max Stackelberg games were first studied by Wald, under the posthumous name of Wald's maximin model, a variant of which is the main paradigm used in robust optimization, which means that our methods can likewise solve many convex robust optimization problems. We observe that the computation of competitive equilibria in Fisher markets also comprises a min-max Stackelberg game. Further, we demonstrate the efficacy and efficiency of our algorithms in practice by computing competitive equilibria in Fisher markets with varying utility structures. Our experiments suggest potential ways to extend our theoretical results, by demonstrating how different smoothness properties can affect the convergence rate of our algorithms.

arXiv comment25 pages, 4 tables, 1 figure, Forthcoming in NeurIPS 2021

References in corpus (17)

• Certifying Some Distributional Robustness with Principled Adversarial Training
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Learning Adversarially Fair and Transferable Representations
• A Variational Inequality Perspective on Generative Adversarial Networks
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• On the Convergence and Robustness of Training GANs with Regularized Optimal Transport
• Efficient Algorithms for Smooth Minimax Optimization
• Local Stackelberg equilibrium seeking in generalized aggregative games
• Kernel Exponential Family Estimation via Doubly Dual Embedding
• On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulator
• First-Order Methods for Large-Scale Market Equilibrium Computation
• Regret Circuits: Composability of Regret Minimizers
• Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
• Accelerated methods for composite non-bilinear saddle point problem
• Balancing the Robustness and Convergence of Tatonnement
• First-order algorithms for robust optimization problems via convex-concave saddle-point Lagrangian reformulation
• Optimality Conditions for Constrained Minimax Optimization