提出新型两层在线学习算法，显著降低非凸优化的梯度查询次数。
Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods
- 将找驻点转化为两个在线学习问题求解
- 复杂度达 $O(d^{1/4}ε^{-13/8})$，维度适中时更优
- 首次证明拟牛顿法在非凸场景可优于梯度下降
研究仅通过梯度信息寻找光滑函数 $\varepsilon$-一阶驻点的问题。已知最优梯度查询复杂度为 $O(\varepsilon^{-7/4})$，当目标函数的梯度与海森矩阵均满足利普希茨连续时。本文提出一种新方法，复杂度为 $O(d^{1/4}\varepsilon^{-13/8})$，其中 $d$ 为问题维度，在 $d = O(\varepsilon^{-1/2})$ 条件下实现改进。核心是将非凸驻点求解重构为在线凸优化中的最小化遗憾问题，损失由目标函数梯度决定。进一步设计了一种新颖的乐观型拟牛顿法，其海森矩阵近似更新本身也被建模为矩阵空间上的在线学习问题。该结果不仅改进了梯度预言机下达到 $\varepsilon$-FOSP 的复杂度界限，还首次提供了拟牛顿法在非凸环境下可能超越梯度下降类方法的理论保证。
原文摘要 · Abstract (English)
We study the problem of finding an $ε$-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}(ε^{-7/4})$. In this work, we propose a method with a gradient complexity of ${O}(d^{1/4}ε^{-13/8})$, where $d$ is the problem dimension, leading to an improved complexity when $d = {O}(ε^{-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 $ε$-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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。