Search papers, labs, and topics across Lattice.
This paper introduces Two-Sided L-BFGS, a novel variant of the L-BFGS algorithm designed to mitigate the numerical instability caused by exploding condition numbers in ill-conditioned or non-convex optimization landscapes. By employing a two-sided geometric envelope to constrain the condition number of the inverse Hessian approximation, the method preserves curvature information while maintaining the efficiency of standard L-BFGS in terms of memory and computational complexity. Theoretical analysis and numerical experiments demonstrate that Two-Sided L-BFGS achieves robust convergence and well-conditioned approximations, outperforming traditional approaches on challenging optimization problems.
A new safeguard mechanism in Two-Sided L-BFGS effectively prevents numerical instability, ensuring robust convergence in ill-conditioned optimization scenarios.
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.
