论文标题
加速的原始偶对偶，凸出的符号鞍点问题
Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems
论文作者
论文摘要
我们研究了使用原始函数的线性近似而不是标准近端步骤的鞍点问题（SPP）的原始双（PD）方法，从而导致线性化PD（LPD）方法。对于凸的浓缩spp，我们观察到LPD方法对原始功能的Lipschitz常数具有次优依赖性。为了解决此问题，我们将加速梯度下降的特征与LPD方法相结合，从而产生了单环加速线性化的原始偶（ALPD）方法。当SPP具有半线性耦合函数时，ALPD方法可达到最佳梯度复杂性。我们还为具有一般非线性耦合函数的SPP提供了一种不精确的ALPD方法，该方法维持原始部分的最佳梯度评估，并显着改善了与ALPD方法相比，耦合项的梯度评估。我们通过数值实验来验证我们的发现。
We investigate a primal-dual (PD) method for the saddle point problem (SPP) that uses a linear approximation of the primal function instead of the standard proximal step, resulting in a linearized PD (LPD) method. For convex-strongly concave SPP, we observe that the LPD method has a suboptimal dependence on the Lipschitz constant of the primal function. To fix this issue, we combine features of Accelerated Gradient Descent with the LPD method resulting in a single-loop Accelerated Linearized Primal-Dual (ALPD) method. ALPD method achieves the optimal gradient complexity when the SPP has a semi-linear coupling function. We also present an inexact ALPD method for SPPs with a general nonlinear coupling function that maintains the optimal gradient evaluations of the primal parts and significantly improves the gradient evaluations of the coupling term compared to the ALPD method. We verify our findings with numerical experiments.
