Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems
复制标题
DOI：
10.1007/s10107-019-01420-0
复制
发表时间：
2019-08
影响因子：
2.7
通讯作者：
Yuyuan Ouyang;Yangyang Xu
中科院分区：
文献类型：
--
作者：
Yuyuan Ouyang;Yangyang Xu
在求解凸凹双线性鞍点问题时，已有许多工作研究一阶方法的复杂性结果。这些结果都是关于复杂度上限的，这可以确定最多多少次迭代将保证所需精度的解决方案。在本文中，我们追求相反的方向，推导出较低的复杂性界的一阶方法在大规模的SPP。我们的研究结果适用于迭代的方法是在线性跨度的过去的一阶信息，以及更一般的方法，以任意方式产生的迭代的基础上的一阶信息。我们首先研究了仿射约束光滑凸优化问题，它是SPP的一个特例。与无约束问题的梯度法不同，我们证明了仿射约束问题的一阶方法一般不能从已知的收敛速度O（1 /t）加速到O（1 /t），而且对于凸问题，O（1 /t）是最优的。此外，我们证明了，对于强凸问题，是最好的可能的收敛速度，而它是已知的梯度方法可以线性收敛于无约束问题。然后我们将这些结果推广到一般的SPPs。事实证明，我们的较低的复杂性界匹配的几个建立在文献中的复杂性上界，因此，他们是紧的，并表明现有的几个一阶方法的最优性。
On solving a convex-concave bilinear saddle-point problem (SPP), there have been many works studying the complexity results of first-order methods. These results are all about upper complexity bounds, which can determine at most how many iterations would guarantee a solution of desired accuracy. In this paper, we pursue the opposite direction by deriving lower complexity bounds of first-order methods on large-scale SPPs. Our results apply to the methods whose iterates are in the linear span of past first-order information, as well as more general methods that produce their iterates in an arbitrary manner based on first-order information. We first work on the affinely constrained smooth convex optimization that is a special case of SPP. Different from gradient method on unconstrained problems, we show that first-order methods on affinely constrained problems generally cannot be accelerated from the known convergence rateO(1 /t) to, and in addition,O(1 /t) is optimal for convex problems. Moreover, we prove that for strongly convex problems,is the best possible convergence rate, while it is known that gradient methods can have linear convergence on unconstrained problems. Then we extend these results to general SPPs. It turns out that our lower complexity bounds match with several established upper complexity bounds in the literature, and thus they are tight and indicate the optimality of several existing first-order methods.