Solving optimization problems with Blackwell approachability
Solving optimization problems with Blackwell approachability
复制标题
DOI：
10.1287/moor.2023.1376
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Julien Grand-Clément;Christian Kroer
中科院分区：
文献类型：
--
作者：
Julien Grand-Clément;Christian Kroer
在本文中，我们提出了一种在重复博弈框架中使用后悔最小化来解决凸凹鞍点问题的新算法。为此，我们引入了圆锥布莱克韦尔算法+（[公式：参见文本]），这是一种新的用于一般凸紧集的无参数和无标度遗憾最小化器。 [公式：见文字]基于Blackwell的平易近人性而获得[公式：见文字]遗憾。我们展示了如何有效地实例化许多感兴趣的决策集的[公式：参见文本]，包括单纯形、[公式：参见文本]范数球和单纯形中的椭圆体置信区域。基于[公式：见正文]，我们引入了[公式：见正文]，一种新的无参数算法，用于解决凸凹鞍点问题，实现了[公式：见正文]遍历收敛速度。在我们的模拟中，我们证明了[公式：参见文本]在优化和运筹学文献中的几个标准鞍点问题上的广泛适用性，包括矩阵博弈、扩展形式博弈、分布鲁棒逻辑回归和马尔可夫决策过程。在每种设置中，[公式：参见文本] 都实现了最先进的数值性能并优于经典方法，而无需选择任何步长或其他算法参数。资助：J. Grand-Clément 得到 Agence Nationale de la Recherche [Grant 11-LABX-0047] 和 Hi! 的支持巴黎。 C. Kroer 得到海军研究办公室 [Grant N00014-22-1-2530] 和国家科学基金会 [Grant IIS-2147361] 的支持。
In this paper, we propose a new algorithm for solving convex-concave saddle-point problems using regret minimization in the repeated game framework. To do so, we introduce the Conic Blackwell Algorithm+ ([Formula: see text]), a new parameter- and scale-free regret minimizer for general convex compact sets. [Formula: see text] is based on Blackwell approachability and attains [Formula: see text] regret. We show how to efficiently instantiate [Formula: see text] for many decision sets of interest, including the simplex, [Formula: see text] norm balls, and ellipsoidal confidence regions in the simplex. Based on [Formula: see text], we introduce [Formula: see text], a new parameter-free algorithm for solving convex-concave saddle-point problems achieving a [Formula: see text] ergodic convergence rate. In our simulations, we demonstrate the wide applicability of [Formula: see text] on several standard saddle-point problems from the optimization and operations research literature, including matrix games, extensive-form games, distributionally robust logistic regression, and Markov decision processes. In each setting, [Formula: see text] achieves state-of-the-art numerical performance and outperforms classical methods, without the need for any choice of step sizes or other algorithmic parameters. Funding: J. Grand-Clément is supported by the Agence Nationale de la Recherche [Grant 11-LABX-0047] and by Hi! Paris. C. Kroer is supported by the Office of Naval Research [Grant N00014-22-1-2530] and by the National Science Foundation [Grant IIS-2147361].