Novel Limited Memory Quasi-Newton Methods Based On Optimal Matrix Approximation

Erik Berglund, Mikael JohanssonarXiv 2024 · DOI · arXiv

TL;DR

Instead of discarding old curvature data like standard L-BFGS, this paper proposes "reducing" the Hessian approximation to its closest limited-memory form using optimal matrix approximation. By solving these "nearest matrix" problems analytically, the authors develop new quasi-Newton methods that achieve faster convergence and lower storage requirements than traditional sliding-window approaches.

What Problem Does This Paper Address?

In large-scale optimization, the Hessian matrix (the second derivative of the objective function) is often too massive to store or compute directly. Quasi-Newton methods like BFGS approximate the Hessian using only gradient information, but even these approximations require $O(n^2)$ storage.

To solve this, Limited-memory (L-BFGS) methods were developed. Traditionally, L-BFGS uses a "sliding window" approach: it keeps the most recent $m$ updates and simply discards everything older. While efficient, this "memoryless" strategy throws away potentially valuable curvature information from earlier iterations.

The authors ask: Can we limit memory usage based on an optimality principle rather than just a chronological one? Instead of deleting old vectors, can we find the "closest" limited-memory matrix to our full, updated approximation?

Methods

The paper introduces a framework for Matrix Reduction. The core idea is to perform a standard quasi-Newton update (which increases the rank of the approximation) and then "reduce" it back to a fixed memory size by solving a nearest-matrix problem.

1. The "Low-Rank Plus Shift" Structure

The authors focus on matrices with the structure $B = \alpha I + \text{low-rank matrix}$. This is the natural form of limited-memory approximations. They characterize these matrices as having a single eigenvalue ($\alpha$) with a high multiplicity (at least $n-m$).

2. Solving the Nearest Matrix Problem

The authors derive analytical solutions to find the closest limited-memory matrix to an arbitrary symmetric matrix. They prove that for any unitarily invariant norm (like Frobenius or $l^2$):

  • The optimal approximation shares the same eigenvectors as the target matrix.
  • The problem reduces from $n^2$ variables to just $n$ variables (the eigenvalues).
  • The optimal "shift" ($\alpha$) is essentially a specific type of mean of a consecutive sequence of the target's eigenvalues.

3. Integration with Trust Regions

The authors implement these ideas within a Trust Region framework. By storing the Hessian approximation via its eigendecomposition, they can solve the trust-region subproblem (finding the optimal step size within a "safe" radius) very efficiently.

Datasets

The authors evaluated their methods (dubbed L2-BFGS for the $l^2$ norm and LF-BFGS for the Frobenius norm) using:

  • Gisette: A standard machine learning dataset for logistic regression (5,000 variables, 6,000 features).
  • Randomly Generated QPs: 1,000 synthetic quadratic programming problems designed to test convergence near local optima.
  • CUTEst: A well-known benchmark suite for non-linear optimization containing a wide variety of mathematical test problems.

Key Insights and Ideas

  • The "Aha" Moment on Eigenvalues: The authors realized that finding the closest limited-memory matrix is equivalent to picking a sequence of eigenvalues and replacing them with their mean.
  • Forgetting vs. Aggregating:
    • The $l^2$ norm reduction is "forgetful." It only cares about the maximum and minimum eigenvalues in a sequence, effectively discarding the information in between. This works well for problems where the Hessian changes rapidly.
  • The Frobenius norm reduction is "aggregating." It uses the arithmetic mean of all eigenvalues in the sequence, preserving more global information. This is superior for problems with near-constant Hessians (like quadratic problems).
  • Computational Efficiency: While the method involves eigendecompositions, the authors show that because of the low-rank structure, they only need to decompose an $m \times m$ matrix (where $m$ is small, e.g., 5 or 10), keeping the per-iteration cost at $O(nm^2 + m^3)$.

Key Results

  • Fewer Iterations: On the Gisette logistic regression task, L2-BFGS converged in 30 iterations, compared to 50 iterations for the reference trust-region L-BFGS (MSS).
  • Better Memory Scaling: In quadratic problems, the new methods achieved higher accuracy with a memory parameter of $m=5$ than the reference method did with $m=16$.
  • Competitive Benchmarking: On the CUTEst suite, L2-BFGS showed a better performance profile than standard L-BFGS with line search, particularly in terms of the number of function evaluations required to reach a solution.

Limitations and Future Work

  • Computational Trade-off: The per-iteration cost is higher than standard L-BFGS. This method is most beneficial when function and gradient evaluations are the primary bottleneck (e.g., very large datasets or complex simulations).
  • Positive Definiteness: Some of the dissimilarity measures (like Stein loss) are only applicable to positive definite matrices, which might limit their use in certain non-convex settings.
  • Future Directions: The authors suggest applying this matrix reduction framework to other updates, such as the Symmetric Rank-1 (SR1) update, which can better handle non-convexity but is traditionally harder to stabilize in a limited-memory format.

Summary updated

Abstract

Update formulas for the Hessian approximations in quasi-Newton methods such as BFGS can be derived as analytical solutions to certain nearest-matrix problems. In this article, we propose a similar idea for deriving new limited memory versions of quasi-Newton methods. Most limited memory quasi-Newton methods make use of Hessian approximations that can be written as a scaled identity matrix plus a symmetric matrix with limited rank. We derive a way of finding the nearest matrix of this type to an arbitrary symmetric matrix, in either the Frobenius norm, the induced $l^2$ norm, or a dissimilarity measure for positive definite matrices in terms of trace and determinant. In doing so, we lay down a framework for more general matrix optimization problems with unitarily invariant matrix norms and arbitrary constraints on the set of eigenvalues. We then propose a trust region method in which the Hessian approximation, after having been updated by a Broyden class formula and used to solve a trust-region problem, is replaced by one of its closest limited memory approximations. We propose to store the Hessian approximation in terms of its eigenvectors and eigenvalues in a way that completely defines its eigenvalue decomposition, as this simplifies both the solution of the trust region subproblem and the nearest limited memory matrix problem. Our method is compared to a reference trust region method with the usual limited memory BFGS updates, and is shown to require fewer iterations and the storage of fewer vectors for a variety of test problems.
BibTeX
@misc{berglund2024novel,
  author = {Erik Berglund and Mikael Johansson},
  title = {{Novel Limited Memory Quasi-Newton Methods Based On Optimal Matrix Approximation}},
  year = {2024},
  eprint = {2403.02860},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.02860},
}
Figure