论文标题
Min-Max Stackelberg游戏中的梯度下降上升
Gradient Descent Ascent in Min-Max Stackelberg Games
论文作者
论文摘要
Min-Max优化问题（即Min-Max游戏）最近引起了广泛的关注，因为它们对广泛的机器学习问题的适用性已变得显而易见。在本文中，我们研究了具有依赖策略集的Min-Max游戏，其中第一个玩家的策略限制了第二名的行为。最好将这些游戏理解为顺序的，即Stackelberg，Games，相关解决方案概念是Stackelberg Equilibrium，Nash的概括。解决Min-Max游戏最受欢迎的算法之一是梯度下降（GDA）。我们提出了具有依赖策略集的GDA对Min-Max Stackelberg游戏的直接概括，但表明它可能不会融合到Stackelberg平衡。然后，我们介绍了GDA的两个变体，这些变体假设对游戏的最佳Karush Kuhn Tucker（KKT）乘数访问了游戏的约束。 We show that such an oracle exists for a large class of convex-concave min-max Stackelberg games, and provide proof that our GDA variants with such an oracle converge in $O(\frac{1}{\varepsilon^2})$ iterations to an $\varepsilon$-Stackelberg equilibrium, improving on the most efficient algorithms currently known which收敛于$ O（\ frac {1} {\ varepsilon^3}）$ iterations。然后，我们证明，使用我们的小说算法解决Fisher Markets，这是最低限制算法游戏的一个规范示例，它在重复的市场中使用近视最佳反应动态对应于买卖双方，使我们能够证明这些动态在$ O（\ frac {1}} {1} {1} {1} {\ varepsilon in fisheron in fish 2}中的融合。我们通过描述Fisher市场的实验来结束，这些实验提出了扩展理论结果的潜在方法，通过证明目标函数的不同特性如何影响算法的收敛性和收敛速率。
Min-max optimization problems (i.e., min-max games) have attracted a great deal of attention recently as their applicability to a wide range of machine learning problems has become evident. In this paper, we study min-max games with dependent strategy sets, where the strategy of the first player constrains the behavior of the second. Such games are best understood as sequential, i.e., Stackelberg, games, for which the relevant solution concept is Stackelberg equilibrium, a generalization of Nash. One of the most popular algorithms for solving min-max games is gradient descent ascent (GDA). We present a straightforward generalization of GDA to min-max Stackelberg games with dependent strategy sets, but show that it may not converge to a Stackelberg equilibrium. We then introduce two variants of GDA, which assume access to a solution oracle for the optimal Karush Kuhn Tucker (KKT) multipliers of the games' constraints. We show that such an oracle exists for a large class of convex-concave min-max Stackelberg games, and provide proof that our GDA variants with such an oracle converge in $O(\frac{1}{\varepsilon^2})$ iterations to an $\varepsilon$-Stackelberg equilibrium, improving on the most efficient algorithms currently known which converge in $O(\frac{1}{\varepsilon^3})$ iterations. We then show that solving Fisher markets, a canonical example of a min-max Stackelberg game, using our novel algorithm, corresponds to buyers and sellers using myopic best-response dynamics in a repeated market, allowing us to prove the convergence of these dynamics in $O(\frac{1}{\varepsilon^2})$ iterations in Fisher markets. We close by describing experiments on Fisher markets which suggest potential ways to extend our theoretical results, by demonstrating how different properties of the objective function can affect the convergence and convergence rate of our algorithms.
