提出简单步长策略，让拟牛顿法在凸优化中全局收敛更快。
Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
- 设计简单步长调度，无需复杂线搜索即可保证全局收敛。
- 控制海森近似误差时，收敛速度达O(1/k²)，媲美最优算法。
- 适配曲率变化的自适应版本，适合实际应用且保持理论保障。
拟牛顿法因其易实现、高效且局部收敛性好，被广泛用于求解凸优化问题。然而，其全局收敛通常依赖特定线搜索策略及强凸性假设。本文引入一种简单步长调度，确保凸函数下全局收敛速率达O(1/k)。当海森近似误差控制在预设相对精度内时，方法达到O(1/k²)的加速收敛速率，与奈斯特罗夫加速梯度法及三阶正则化牛顿法的最佳已知速率相当。通过实验验证，理论结果在性能上显著优于标准拟牛顿基线。为进一步提升鲁棒性，我们提出一种自适应变体，能根据函数曲率动态调整，同时保留非自适应算法的全局收敛保证。
原文摘要 · Abstract (English)
Quasi-Newton methods are widely used for solving convex optimization problems due to their ease of implementation, practical efficiency, and strong local convergence guarantees. However, their global convergence is typically established only under specific line search strategies and the assumption of strong convexity. In this work, we extend the theoretical understanding of Quasi-Newton methods by introducing a simple stepsize schedule that guarantees a global convergence rate of ${O}(1/k)$ for the convex functions. Furthermore, we show that when the inexactness of the Hessian approximation is controlled within a prescribed relative accuracy, the method attains an accelerated convergence rate of ${O}(1/k^2)$ -- matching the best-known rates of both Nesterov's accelerated gradient method and cubically regularized Newton methods. We validate our theoretical findings through empirical comparisons, demonstrating clear improvements over standard Quasi-Newton baselines. To further enhance robustness, we develop an adaptive variant that adjusts to the function's curvature while retaining the global convergence guarantees of the non-adaptive algorithm.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。