A Catalyst Framework for Minimax Optimization
A Catalyst Framework for Minimax Optimization
复制标题
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Junchi Yang;Siqi Zhang;N. Kiyavash;Niao He
中科院分区：
文献类型：
--
作者：
Junchi Yang;Siqi Zhang;N. Kiyavash;Niao He
给出了具有强凸-凹目标的光滑极大极小优化问题的一般双环算法。我们的方法将加速邻近点框架(或催化剂)应用于相关的对偶问题，并充分利用现有的基于梯度的算法来求解一系列平衡的强凸-强凹的极大极小问题。尽管它很简单，但这导致了一类近乎最优的算法，与所有现有的用于强凸-凹极大极小问题的方法相比，其复杂性得到了改善。此外，我们还得到了这类具有finite-sum结构的极大极小问题的fiRST减方差算法，并建立了比批处理算法更快的收敛速度。此外，当推广到非凸-凹的极大极小优化问题时，我们的算法再次达到了fi和固定点的最高复杂性。我们进行了几个数值实验，展示了Catalyst框架在实际应用中的优越性。
We introduce a generic two-loop scheme for smooth minimax optimization with strongly-convex-concave objectives. Our approach applies the accelerated proximal point framework (or Catalyst) to the associated dual problem and takes full advantage of existing gradient-based algorithms to solve a sequence of well-balanced strongly-convex-strongly-concave minimax problems. Despite its simplicity, this leads to a family of near-optimal algorithms with improved complexity over all existing methods designed for strongly-convex-concave minimax problems. Additionally, we obtain the first variance-reduced algorithms for this class of minimax problems with finite-sum structure and establish faster convergence rate than batch algorithms. Furthermore, when extended to the nonconvex-concave minimax optimization, our algorithm again achieves the state-of-the-art complexity for finding a stationary point. We carry out several numerical experiments showcasing the superiority of the Catalyst framework in practice.