BFGS with Update Skipping and Varying Memory

Tamara G. Kolda, Dianne P. O'Leary, Larry NazarethSIAM J. Optim 1998 · DOI

Abstract

In numerical optimization, quasi-Newton methods are essential for minimizing complex functions by approximating the Hessian matrix. However, the computational and storage costs of full Hessian approximations often necessitate limited-memory variants or update skipping. This paper investigates the theoretical guarantees of the Broyden family of algorithms under these constraints. We demonstrate that BFGS is uniquely robust, maintaining quadratic termination properties in limited-memory settings where other methods, such as DFP, fail. Furthermore, we explore the trade-offs of update skipping and the efficiency of adaptive memory strategies, supported by numerical experiments on the CUTE test suite.

Introduction

Quasi-Newton methods represent the "workhorses" of modern numerical optimization. By utilizing information from previous iterations to build an approximation of the Hessian (the matrix of second derivatives), these algorithms achieve faster convergence than simple gradient descent without the prohibitive cost of calculating the exact Hessian. A primary benchmark for these methods is quadratic termination: the mathematical guarantee that the algorithm will find the exact minimum of an $n$-dimensional quadratic function in at most $n$ steps.

In practical applications, however, storing a full $n \times n$ Hessian approximation is often infeasible for high-dimensional problems. This leads to the use of "limited-memory" versions, such as L-BFGS, which store only a small window of recent updates. Despite the ubiquity of L-BFGS, the theoretical justification for why BFGS outperforms other members of the Broyden family in these restricted settings has remained partially obscured. This research addresses that gap by analyzing how information loss—via limited memory or update skipping—affects the convergence properties of quasi-Newton updates.

The General Form and the Broyden Family

To analyze these algorithms systematically, the authors define a "General Form" for quasi-Newton updates. This framework encompasses the Broyden family, a class of algorithms that includes the well-known BFGS (Broyden–Fletcher–Goldfarb–Shanno) and DFP (Davidon–Fletcher–Powell) methods. By using this unified lens, the study evaluates three specific modifications to standard optimization routines:

  1. Limited Memory: Retaining only the $m$ most recent updates.
  2. Update Skipping: Intentionally omitting Hessian updates at specific iterations to save computation or handle communication delays.
  3. Varying Memory: Dynamically adjusting the number of stored updates ($m$) based on the progress of the gradient.

The Uniqueness of BFGS

The most significant theoretical contribution of this work is the identification of the BFGS "Superpower." The authors provide a rigorous proof that within the Broyden family, only the BFGS variant retains $n$-step quadratic termination when memory is limited. Other methods, including DFP, lose this property immediately if the full history of updates is not preserved. This finding provides a long-sought theoretical explanation for why L-BFGS has remained the industry standard for decades: it is mathematically more resilient to data loss than its counterparts.

The Impact of Update Skipping

The research also quantifies the cost of skipping updates. In a full-memory environment, skipping $p$ updates does not destroy the algorithm's ability to reach the minimum; rather, it introduces a linear delay. Specifically, the algorithm will terminate in $n + p$ steps.

However, the authors warn against the "Lethal Combination": combining limited memory with update skipping. While BFGS can handle limited memory, and full-memory methods can handle skipping, the simultaneous application of both constraints destroys the quadratic termination property entirely. This suggests that in distributed or parallel computing environments where skipping might be tempting to avoid synchronization overhead, practitioners must be cautious if they are also using limited-memory approximations.

Numerical Results and Adaptive Memory

To validate these theoretical insights, the authors conducted experiments using the CUTE (Constrained and Unconstrained Testing Environment) test set. They selected 22 difficult unconstrained problems, ranging from 10 to 10,000 variables, ensuring each required at least 60 iterations for standard L-BFGS to solve.

The experiments introduced several new L-BFGS variants that utilize Adaptive Memory. By increasing the memory size $m$ as the gradient norm decreases (indicating proximity to the solution), these variants achieved several advantages:

  • Efficiency: They performed less linear algebra in early iterations when memory requirements were low, leading to faster "wall-clock" times.
  • Performance: The adaptive variants performed as well as, and in some cases better than, standard L-BFGS.
  • Robustness: Strategies such as "backing up" (discarding the next-most-recent update instead of the oldest) showed no failures across the entire test suite.

Conclusion and Future Directions

This paper reinforces the status of BFGS as the premier choice for limited-memory optimization by proving its unique mathematical robustness. While the study focuses primarily on quadratic functions, the results offer clear guidance for improving optimization software. Future research may explore the potential of update skipping in parallel architectures, where the trade-off between communication latency and optimization progress is most acute. Additionally, the success of adaptive memory suggests that fixed-memory L-BFGS may be sub-optimal for many real-world tasks.

Summary updated

BibTeX
@article{kolda1998bfgs,
  author = {Tamara G. Kolda and Dianne P. O'Leary and Larry Nazareth},
  title = {{BFGS with Update Skipping and Varying Memory}},
  journal = {SIAM J. Optim.},
  year = {1998},
  doi = {10.1137/s1052623496306450},
}
Figure