EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization
Chinmay Maheshwari and Chinmay Pimpalkhare and Debasish Chatterjee
Min-max优化出现在许多领域,如博弈论,对抗性机器学习等,以梯度为基础的方法作为典型的计算工具。 除了 convex-concave min-max 优化之外,基于梯度的方法找到的解决方案可能任意远离全局 optima。 在这项工作中,我们介绍了一种算法设备,用于在凸-非凹陷和非凸凹凸-凹凸 min-max 优化中计算全球最优解决方案。 对于前者,我们采用重新计算,将其转换为非凹凸max-min优化问题,具有适当定义的可行集合和客观函数。 新形式可以被看作是Sion的minimax定理的概括。 接下来,我们引入了EXOTIC-an Exact,Optimistic,基于Tree的算法,用于解决重新配制的max-min问题。 EXOTIC使用迭代凸优化求解器(大约)解决内部最小化和分层树搜索外部最大化,根据凸优化求解器返回的近似解决方案,乐观地选择有前途的区域进行搜索。 我们在其最优性间隙上建立上限,作为调用到内部求解器的函数,求解器的收敛率和额外的问题依赖参数。 我们的算法设备及其伴随的理论分析也可以应用于非凸凹凸min-max优化。 此外,我们提出了一类基准凸-非凹凸min-max问题及其分析全局解决方案,为评估min-max优化算法提供了测试平台。 从经验上讲,EXOTIC在这个基准以及文献中现有的数值基准问题上优于基于梯度的方法。 最后,我们通过在拥有三个或三个以上玩家的多人游戏中计算安全策略来展示EXOTIC的效用。
Min-max optimization arises in many domains such as game theory, adversarial machine learning, etc., with gradient-based methods as a typical computational tool. Beyond convex-concave min-max optimization, the solutions found by gradient-based methods may be arbitrarily far from global optima. In this work, we present an algorithmic apparatus for computing globally optimal solutions in convex-non-concave and non-convex-concave min-max optimization. For former, we employ a reformulation that tran...