标题： 光滑非凸优化的改进复杂度：一种基于拟牛顿方法的两级在线学习方法 显示英文标题

标题： Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods

摘要： 我们研究了在仅能访问梯度信息的情况下，寻找光滑函数的$\epsilon$-一阶平稳点 (FOSP) 的问题。假设目标函数的梯度和海森矩阵都是利普希茨连续的，对此任务最著名的梯度查询复杂度是${O}(\epsilon^{-7/4})$。在本工作中，我们提出了一种梯度复杂度为${O}(d^{1/4}\epsilon^{-13/8})$的方法，其中$d$是问题维度，当$d = {O}(\epsilon^{-1/2})$时，这会导致更优的复杂度。为了达到这个结果，我们设计了一个优化算法，该算法内部涉及解决两个在线学习问题。具体来说，我们首先将非凸问题寻找平稳点的任务重新表述为在在线凸优化问题中最小化遗憾，其中损失由目标函数的梯度决定。然后，我们引入了一种新颖的乐观拟牛顿方法来解决这个在线学习问题，其中海森矩阵近似更新本身被框架化为矩阵空间中的一个在线学习问题。除了使用梯度预言机达到$\epsilon$-FOSP 的复杂度界限有所改进外，我们的结果提供了首个保证，表明拟牛顿方法在非凸设置中可能优于梯度下降类方法。 显示英文摘要

摘要： We study the problem of finding an $\epsilon$-first-order stationary point (FOSP) of a smooth function, given access only to gradient information. The best-known gradient query complexity for this task, assuming both the gradient and Hessian of the objective function are Lipschitz continuous, is ${O}(\epsilon^{-7/4})$. In this work, we propose a method with a gradient complexity of ${O}(d^{1/4}\epsilon^{-13/8})$, where $d$ is the problem dimension, leading to an improved complexity when $d = {O}(\epsilon^{-1/2})$. To achieve this result, we design an optimization algorithm that, underneath, involves solving two online learning problems. Specifically, we first reformulate the task of finding a stationary point for a nonconvex problem as minimizing the regret in an online convex optimization problem, where the loss is determined by the gradient of the objective function. Then, we introduce a novel optimistic quasi-Newton method to solve this online learning problem, with the Hessian approximation update itself framed as an online learning problem in the space of matrices. Beyond improving the complexity bound for achieving an $\epsilon$-FOSP using a gradient oracle, our result provides the first guarantee suggesting that quasi-Newton methods can potentially outperform gradient descent-type methods in nonconvex settings.