Title: Accelerated Quasi-Newton Proximal Extragradient: Faster Rate for Smooth Convex Optimization Show Chinese title

Title: 加速拟牛顿邻近外梯度：光滑凸优化的更快收敛率

Abstract: In this paper, we propose an accelerated quasi-Newton proximal extragradient (A-QPNE) method for solving unconstrained smooth convex optimization problems. With access only to the gradients of the objective, we prove that our method can achieve a convergence rate of ${O}\bigl(\min\{\frac{1}{k^2}, \frac{\sqrt{d\log k}}{k^{2.5}}\}\bigr)$, where $d$ is the problem dimension and $k$ is the number of iterations. In particular, in the regime where $k = {O}(d)$, our method matches the optimal rate of ${O}(\frac{1}{k^2})$ by Nesterov's accelerated gradient (NAG). Moreover, in the the regime where $k = \Omega(d \log d)$, it outperforms NAG and converges at a faster rate of ${O}\bigl(\frac{\sqrt{d\log k}}{k^{2.5}}\bigr)$. To the best of our knowledge, this result is the first to demonstrate a provable gain of a quasi-Newton-type method over NAG in the convex setting. To achieve such results, we build our method on a recent variant of the Monteiro-Svaiter acceleration framework and adopt an online learning perspective to update the Hessian approximation matrices, in which we relate the convergence rate of our method to the dynamic regret of a specific online convex optimization problem in the space of matrices. Show Chinese abstract

Abstract: 在本文中，我们提出了一种加速的拟牛顿邻近外梯度（A-QPNE）方法，用于求解无约束的平滑凸优化问题。仅能访问目标函数的梯度时，我们证明了我们的方法可以达到 ${O}\bigl(\min\{\frac{1}{k^2}, \frac{\sqrt{d\log k}}{k^{2.5}}\}\bigr)$的收敛率，其中 $d$是问题维度，$k$是迭代次数。特别是在 $k = {O}(d)$的情况下，我们的方法通过 Nesterov 的加速梯度（NAG）达到了 ${O}(\frac{1}{k^2})$的最优率。此外，在 $k = \Omega(d \log d)$的情况下，它优于 NAG，并以 ${O}\bigl(\frac{\sqrt{d\log k}}{k^{2.5}}\bigr)$更快的速率收敛。据我们所知，这一结果是首次在凸设置中证明拟牛顿类型方法优于 NAG 的可证明优势。为了获得这些结果，我们基于 Monteiro-Svaiter 加速框架的一个最新变体构建了我们的方法，并采用在线学习视角来更新海森矩阵近似，其中我们将我们方法的收敛率与矩阵空间中特定在线凸优化问题的动态遗憾相关联。