论文标题
强烈凸出强烈凹形鞍点问题的张量方法和强烈单调的变化不平等
Tensor methods for strongly convex strongly concave saddle point problems and strongly monotone variational inequalities
论文作者
论文摘要
在本文中，我们提出了三个$ p $ ther订单张量方法，用于$μ$ $ $ stronglongly-convex-stronglong-concave鞍点问题（SPP）。第一种方法是基于目标的假设的假设，并且达到了$ o \ left的收敛速率（\ left（\ frac {l_p r^{p -1}}}μ\ right）^\ frac）^\ frac {2}} \ right）$，其中$ r $是与解决方案的初始距离的估计，而$ \ varepsilon_g $是双重性差距的错误。在目标的第一和二阶平滑度的其他假设下，我们将第一个方法与本地超级线性收敛算法联系起来，并开发出第二种方法，其复杂性为$ o \ left（\ left（\ frac {\ frac {l_p r^{p -1}}}μ\ right） \左\ {1，\ frac {l_1}μ\ right \}}μ + \ log \ frac {\ log \ frac {l_1^3} {2μ^2 \ varepsilon_g}}第三种方法是第二种方法的修改版本，它可以用$ \ tilde o \ left（\ left（\ frac {\ frac {l_p r^p} {\ varepsilon_ \ nabla} \ right（\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {就目标梯度的规范而言是错误。由于我们将spp视为变异不平等的特定情况，因此我们还提出了三种方法，即具有与上述相同复杂性的强烈单调变异不平等的方法。
In this paper we propose three $p$-th order tensor methods for $μ$-strongly-convex-strongly-concave saddle point problems (SPP). The first method is based on the assumption of $p$-th order smoothness of the objective and it achieves a convergence rate of $O \left( \left( \frac{L_p R^{p - 1}}μ \right)^\frac{2}{p + 1} \log \frac{μR^2}{\varepsilon_G} \right)$, where $R$ is an estimate of the initial distance to the solution, and $\varepsilon_G$ is the error in terms of duality gap. Under additional assumptions of first and second order smoothness of the objective we connect the first method with a locally superlinear converging algorithm and develop a second method with the complexity of $O \left( \left( \frac{L_p R^{p - 1}}μ \right)^\frac{2}{p + 1}\log \frac{L_2 R \max \left\{ 1, \frac{L_1}μ \right\}}μ + \log \frac{\log \frac{L_1^3}{2 μ^2 \varepsilon_G}}{\log \frac{L_1 L_2}{μ^2}} \right)$. The third method is a modified version of the second method, and it solves gradient norm minimization SPP with $\tilde O \left( \left( \frac{L_p R^p}{\varepsilon_\nabla} \right)^\frac{2}{p + 1} \right)$ oracle calls, where $\varepsilon_\nabla$ is an error in terms of norm of the gradient of the objective. Since we treat SPP as a particular case of variational inequalities, we also propose three methods for strongly monotone variational inequalities with the same complexity as the described above.
