Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
This provides a theoretical and practical advancement for optimization practitioners by ensuring global convergence in quasi-Newton methods, which is incremental but addresses a known bottleneck.
The paper tackles the lack of global convergence guarantees for quasi-Newton methods in convex optimization by introducing a simple stepsize schedule, achieving a global convergence rate of O(1/k) and an accelerated rate of O(1/k^2) under controlled Hessian approximation, with empirical validation showing improvements over standard baselines.
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.