AG-BFGS: Foundations for Accelerated Geometry Learning
Authors: Regina Carla Sousa, Denis Vargas, Elizabeth Wanner, Joshua Knowles
Organizations: Dept of Mathematics, UFOP, Brazil · PPGMMC, CEFET-MG, Brazil · CSDT School, Aston University - PPGMMC, CEFET-MG · SLB Cambridge Research, High Cross, Madingley Road, Cambridgeshire, UK
We introduce an accelerated geometry-learning framework for BFGS that incorporates momentum into the learning of Hessian inverse approximations. We prove that the resulting accelerated updates satisfy explicit stability conditions and preserve positive definiteness within admissible parameter regions. Numerical experiments demonstrate consistent improvements over the corresponding non-accelerated schemes while maintaining numerical stability. These results provide the first rigorous theoretical foundation for accelerated quasi-Newton learning and bridge the gap between empirical observations and mathematical guarantees for accelerated second-order methods.
Figures & tables
Dataset
aBFGS
μ
ν
Australian
30.00
0.50
Phishing
1228.33
0.10
Mushroom
8124.00
0.01
Splice
1000.00
0.90
Table 1: Parameter values for aBFGS as proposed in [ 11 ] .
Figure 1: AG-BFGS vs aBFGS vs standard BFGS using the corresponding parameters shown in Table 1 .
Figure 2: AG-BFGS vs aBFGS vs standard BFGS using the corresponding parameters shown in Table 1 .
Figure 3: Optimization trajectories of BFGS and the proposed accelerated BFGS (AG-BFGS) on the Ellipsoidal function. (a) shows the original separable function, while (b) shows its rotated non-separable version.
Figure 4: Optimization trajectories of BFGS and the proposed accelerated BFGS (AG-BFGS) on the Discuss function. (a) shows the original separable function, while (b) shows its rotated non-separable version.
Figure 5: Optimization trajectories of BFGS and the proposed accelerated BFGS (AG-BFGS) on the Bent Cigar function. (a) shows the original separable function, while (b) shows its rotated non-separable version.
Figure 6: Optimization trajectories of BFGS and the proposed accelerated BFGS (AG-BFGS) on the Sharp Ridge function. (a) shows the original separable function, while (b) shows its rotated non-separable version.
Figure 7: Optimization trajectories of BFGS and the proposed accelerated BFGS (AG-BFGS) on the Different Powers function. (a) shows the original separable function, while (b) shows its rotated non-separable version.
In this paper, we introduce the Quasi-Quadratic Gradient (QQG), a novel search direction designed to accelerate the BFGS method within the quasi-Newton framework. By defining the QQG as the product of the inverse Hessian approximation and the current gradient, we explicitly leverage local second-order curvature to rectify the search path. Theoretical analysis and empirical results demonstrate that our approach significantly outperforms vanilla BFGS in convergence speed while maintaining computational efficiency.
We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of O(1/k3) in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate. We further extend our construction to arbitrary geometry through Bregman divergence, and to composite optimization problems.
Nikita Doikov
School of Operations Research and Information Engineering (ORIE), Cornell University, Ithaca, NY, USA.
The limited-memory BFGS (L-BFGS) algorithm is a cornerstone of large-scale optimization due to its linear memory and computational costs. However, in ill-conditioned or non-convex landscapes, the implicit inverse Hessian approximation can suffer from an exploding condition number, leading to numerical instability and degraded convergence. To address this, we propose Two-Sided L-BFGS, a safeguarded variant that dynamically constrains the condition number of the inverse Hessian operator via a two-sided geometric envelope. Moreover, we show that Two-Sided L-BFGS preserves accumulated curvature information and maintains standard O(mn) memory and per-iteration time complexities. We prove that this geometric envelope yields a uniform bound on the condition number of every inverse Hessian approximation generated by the algorithm. By tracking the algebraic evolution of the extreme eigenvalues through m consecutive quasi-Newton updates starting from a scaled identity matrix, the resulting bound is expressed explicitly as a function of the memory depth, problem dimension, and envelope hyperparameters. Moreover, we show that Two-Sided L-BFGS preserves asymptotic global convergence in non-convex regimes under standard smoothness and strong Wolfe line-search assumptions, matching the theoretical guarantees of L-BFGS variants utilizing the Li-Fukushima cautious update rule. Numerical experiments on high-dimensional optimization problems demonstrate that the proposed method maintains well-conditioned inverse Hessian approximations and improves robustness and convergence behavior on ill-conditioned benchmarks.
Don Li
Department of Mathematics & Statistics Portland State University Portland, OR 97201, USA