The optimistic gradient method has seen increasing popularity as an efficient first-order method for solving convex-concave saddle point problems. To analyze its iteration complexity, a recent work [arXiv:1901.08511] proposed an interesting perspective that interprets the optimistic gradient method as an approximation to the proximal point method. In this paper, we follow this approach and distill the underlying idea of optimism to propose a generalized optimistic method, which encompasses the optimistic gradient method as a special case. Our general framework can handle constrained saddle point problems with composite objective functions and can work with arbitrary norms with compatible Bregman distances. Moreover, we also develop an adaptive line search scheme to select the stepsizes without knowledge of the smoothness coefficients. We instantiate our method with first-order, second-order and higher-order oracles and give sharp global iteration complexity bounds. When the objective function is convex-concave, we show that the averaged iterates of our $p$-th-order method ($p\geq 1$) converge at a rate of $\mathcal{O}(1/N^\frac{p+1}{2})$. When the objective function is further strongly-convex-strongly-concave, we prove a complexity bound of $\mathcal{O}(\frac{L_1}{\mu}\log\frac{1}{\epsilon})$ for our first-order method and a bound of $\mathcal{O}((L_p D^\frac{p-1}{2}/\mu)^{\frac{2}{p+1}}+\log\log\frac{1}{\epsilon})$ for our $p$-th-order method ($p\geq 2$) respectively, where $L_p$ ($p\geq 1$) is the Lipschitz constant of the $p$-th-order derivative, $\mu$ is the strongly-convex parameter, and $D$ is the initial Bregman distance to the saddle point. Moreover, our line search scheme provably only requires an almost constant number of calls to a subproblem solver per iteration on average, making our first-order and second-order methods particularly amenable to implementation.
翻译:乐观的梯度方法将越来越受欢迎, 这是一种解决 convex{ concave sock 问题的有效第一阶方法。 为了分析它的循环复杂性, 最近的一项工作[arXiv:1901.08511] 提出了一个有趣的视角, 将乐观的梯度方法解释为接近准点方法。 在本文中, 我们遵循了这个方法, 并提取了乐观的基本理念, 以提出一种普遍的乐观方法, 将乐观的梯度方法作为一个特例。 我们的总框架可以用复合目标功能处理固定的垫点问题, 并且可以使用与Bregman相兼容的任意规范 。 此外, 我们还开发了适应性线搜索计划, 选择没有了解平滑度系数的阶梯度系统。 我们用第一阶、 第二阶和更高阶或更高级的梯度方法 。 当目标函数为 convexx- concovelopy 时, 我们的美元- listal- proqual_ pall1, 我们的平均值比 $ mexal=1; Nxxxx