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