Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization
复制标题
DOI：
--
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Yan Yan-Yan;Yi Xu;Qihang Lin;W. Liu;Tianbao Yang
中科院分区：
文献类型：
--
作者：
Yan Yan-Yan;Yi Xu;Qihang Lin;W. Liu;Tianbao Yang
历元梯度下降法(又名由Hazan和Kale(2011)提出的Epoch-GD)被认为是随机强凸极小化的一个突破，它通过迭代更新{\it个目标间隙}，获得了$O(1/T)$的最优收敛速度。然而，它对强凸强凹性随机极大极小优化问题的推广仍然是开放的，对于强凸强凹性随机极小极大优化问题，是否能在强凸性和强凹性条件下实现$O(1/T)$的快速优化尚不清楚。虽然最近的一些研究已经提出了求解极大极小问题的快速收敛速度的随机算法，但它们需要对问题进行额外的假设，例如光滑性、双线性结构等。在本文中，我们通过对求解强凸强凹(SCSC)极大极大问题的历时随机梯度下降上升方法(称为Epoch-GDA)的尖锐分析来弥补这一差距，而不施加任何关于光滑性或函数结构的额外假设。据我们所知，我们的结果是第一个表明Epoch-GDA对于一般SCSC极小-极大问题的对偶间隙可以达到$O(1/T)$的最优解。我们强调，将强凸极小化问题的Epoch-GDA推广到SCSC极小极大问题的Epoch-GDA是非平凡的，需要新的技术分析。此外，我们注意到Key引理也可以用来证明Epoch-GDA对弱凸-强凹极小-极大问题的收敛，从而在不求助于光滑性或其他结构条件的情况下获得接近最优的复杂性。
Epoch gradient descent method (a.k.a. Epoch-GD) proposed by Hazan and Kale (2011) was deemed a breakthrough for stochastic strongly convex minimization, which achieves the optimal convergence rate of $O(1/T)$ with $T$ iterative updates for the {\it objective gap}. However, its extension to solving stochastic min-max problems with strong convexity and strong concavity still remains open, and it is still unclear whether a fast rate of $O(1/T)$ for the {\it duality gap} is achievable for stochastic min-max optimization under strong convexity and strong concavity. Although some recent studies have proposed stochastic algorithms with fast convergence rates for min-max problems, they require additional assumptions about the problem, e.g., smoothness, bi-linear structure, etc. In this paper, we bridge this gap by providing a sharp analysis of epoch-wise stochastic gradient descent ascent method (referred to as Epoch-GDA) for solving strongly convex strongly concave (SCSC) min-max problems, without imposing any additional assumption about smoothness or the function's structure. To the best of our knowledge, our result is the first one that shows Epoch-GDA can achieve the optimal rate of $O(1/T)$ for the duality gap of general SCSC min-max problems. We emphasize that such generalization of Epoch-GD for strongly convex minimization problems to Epoch-GDA for SCSC min-max problems is non-trivial and requires novel technical analysis. Moreover, we notice that the key lemma can also be used for proving the convergence of Epoch-GDA for weakly-convex strongly-concave min-max problems, leading to a nearly optimal complexity without resorting to smoothness or other structural conditions.