arXiv:2410.02626math.OCcs.LG2024-10被引 4

提出新型拟牛顿法,无需计算雅可比矩阵即可实现比外梯度法更快的全局收敛。

Online Learning Guided Quasi-Newton Methods with Global Non-Asymptotic Convergence

  • 基于在线学习框架更新雅可比近似矩阵,避免显式计算导数。
  • 在强单调情况下,前O(d)步超线性收敛,之后优于外梯度法线性速率。
  • 适用于无约束优化与极小极大问题,特别适合高维稀疏结构场景。

本文提出一种用于求解光滑单调非线性方程的拟牛顿方法,涵盖无约束优化和极小极大优化等特例。在强单调情形下,建立了两项全局收敛界:(i) 收敛速率与著名外梯度法一致的线性收敛率;(ii) 显式的全局超线性收敛率,在最多 $ O(d) $ 次迭代后严格超越线性速率,其中 $ d $ 为问题维度。对于仅单调的情形,证明了关于对偶间隙的全局收敛率为 $ {O}( ext{min}igackslash{{1}/{k},{ oot{2}{d}}/{k^{1.25}}}igackslash)$,当 $ k = O(d^2) $ 时与外梯度法速率相同,当 $ k = Ω(d^2) $ 时更优。这是首个不依赖雅可比查询即能证明拟牛顿法优于外梯度法的全局收敛结果。不同于经典拟牛顿法,本方法通过混合近端外梯度框架与新颖的在线学习机制更新雅可比近似矩阵。具体地,依据收敛分析,将雅可比近似更新建模为非对称矩阵上的在线凸优化问题,将在线问题的损失与方法收敛速率关联。为提升效率,进一步设计了一种基于近似分离预言机的定制化在线学习算法,保持雅可比矩阵的对称性与稀疏性结构。

原文摘要 · Abstract (English)

In this paper, we propose a quasi-Newton method for solving smooth and monotone nonlinear equations, including unconstrained minimization and minimax optimization as special cases. For the strongly monotone setting, we establish two global convergence bounds: (i) a linear convergence rate that matches the rate of the celebrated extragradient method, and (ii) an explicit global superlinear convergence rate that provably surpasses the linear convergence rate after at most ${O}(d)$ iterations, where $d$ is the problem's dimension. In addition, for the case where the operator is only monotone, we prove a global convergence rate of ${O}(\min\{{1}/{k},{\sqrt{d}}/{k^{1.25}}\})$ in terms of the duality gap. This matches the rate of the extragradient method when $k = {O}(d^2)$ and is faster when $k = Ω(d^2)$. These results are the first global convergence results to demonstrate a provable advantage of a quasi-Newton method over the extragradient method, without querying the Jacobian of the operator. Unlike classical quasi-Newton methods, we achieve this by using the hybrid proximal extragradient framework and a novel online learning approach for updating the Jacobian approximation matrices. Specifically, guided by the convergence analysis, we formulate the Jacobian approximation update as an online convex optimization problem over non-symmetric matrices, relating the regret of the online problem to the convergence rate of our method. To facilitate efficient implementation, we further develop a tailored online learning algorithm based on an approximate separation oracle, which preserves structures such as symmetry and sparsity in the Jacobian matrices.

优化算法拟牛顿法在线学习收敛性分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。