Soft quasi-Newton: Guaranteed positive definiteness by relaxing the secant constraint

Erik Berglund, Jiaojiao Zhang, Mikael JohanssonOptim. Methods Softw 2024

TL;DR

This paper introduces "soft quasi-Newton" (soft QN), a novel optimization algorithm designed to handle noisy function and gradient evaluations more robustly than traditional methods. By "softening" a key constraint in the Hessian update, soft QN guarantees a positive definite Hessian approximation, leading to more reliable convergence in challenging, real-world optimization scenarios.

What Problem Does This Paper Address?

Optimization algorithms often assume that function and gradient evaluations are precise. However, in many practical applications, such as machine learning and simulation optimization, these evaluations are inherently noisy or approximate. Traditional quasi-Newton (QN) methods, which build approximations of the Hessian matrix to accelerate convergence, are particularly sensitive to this noise. This sensitivity can lead to instability and slow convergence, or even complete failure. The paper aims to develop a QN method that maintains its efficiency and reliability even when faced with bounded noise in these evaluations.

Methods

The core innovation is the "soft quasi-Newton" (soft QN) algorithm. Instead of strictly enforcing the secant condition (a standard requirement in QN methods that relates gradient differences to Hessian approximations), soft QN introduces a penalty term into the optimization problem for updating the Hessian inverse approximation. This penalty "softens" the constraint, allowing for deviations from the secant condition when noise is present.

Key aspects of the method include:

  • Relaxed Secant Condition: The secant condition is replaced by a penalty term in the objective function of the matrix optimization problem used to derive the Hessian update.
  • Guaranteed Positive Definiteness: A key theoretical result is that soft QN always generates a positive definite Hessian inverse approximation, regardless of the penalty parameter's value or whether the objective function is convex. This is a significant advantage over some existing methods that require specific parameter ranges for this guarantee.
  • Closed-form Update: The algorithm derives a simple, closed-form update formula for the Hessian inverse approximation.
  • Attractive Properties: Soft QN is shown to recover the BFGS method in certain limits, handle positive and negative curvature equally, and be scale-invariant.

Datasets

The paper evaluates the proposed soft QN method on several types of problems:

  • Logistic Regression: A common machine learning task where noise arises from random data sampling.
  • Quadratic Problems: Artificially generated quadratic functions with added Gaussian noise to the gradients.
  • CUTEst Problems: A collection of standard optimization problems used to test performance under bounded noise in both function and gradient evaluations.

No new datasets were introduced; existing benchmarks were used.

Key Insights and Ideas

  • The Power of "Softening" Constraints: The paper demonstrates that by relaxing a strict mathematical constraint (the secant condition) and introducing a penalty for its violation, one can achieve a more robust and reliable algorithm in the presence of noise. This is a generalizable principle in algorithm design.
  • Guaranteed Positive Definiteness is Crucial: The guarantee of positive definiteness for the Hessian approximation is a critical feature. It ensures that the search directions generated are always descent directions, preventing the algorithm from moving uphill and contributing to stable convergence.
  • Handling Noise is Key for Real-World Optimization: The success of soft QN in noisy scenarios highlights the importance of developing optimization methods that can cope with imperfect information, which is ubiquitous in practical applications.
  • Detecting Low Curvature Directions: The paper illustrates with an example how soft QN can effectively navigate regions with low curvature, even when eigenvalues have opposite signs, allowing it to find minima more efficiently than methods like saddle-free Newton.

Key Results

  • Superior Performance in Noisy Environments: Numerical experiments show that soft QN consistently outperforms or matches state-of-the-art methods, particularly in scenarios with additive noise.
  • Competitive with SP-BFGS: Soft QN is shown to be competitive with SP-BFGS, a related method that also relaxes the secant condition, and in some cases, it demonstrates a clear advantage.
  • Convergence Guarantees: For strongly convex and Lipschitz smooth functions, soft QN is theoretically shown to converge linearly to a neighborhood of the optimal solution, even with bounded noise.
  • Quadratic Problems: In quadratic problems with additive noise, soft QN shows significant improvement over SP-BFGS and SGD, with performance comparable to Newton's method (which uses the exact Hessian).
  • CUTEst Problems: On a set of challenging CUTEst problems with bounded noise, soft QN generally outperforms SP-BFGS, showing lower suboptimality and better variability.

Limitations and Future Work

The authors acknowledge several areas for future research:

  • Dynamic Penalty Parameter: The current work uses a fixed penalty parameter $\alpha_k$. Future work could explore adapting this parameter dynamically during iterations to better escape saddle points.
  • Limited Memory Version: Developing a limited-memory version of soft QN would be crucial for extending its applicability to large-scale optimization problems.
  • Statistically Efficient Techniques: Further research is needed to develop statistically efficient techniques for handling random function and gradient noise.
  • General Noise Scenarios: While the paper focuses on bounded noise, exploring its effectiveness in other noise scenarios could be beneficial.

Summary updated

Abstract

We propose a novel algorithm, termed soft quasi-Newton (soft QN), for optimization in the presence of bounded noise. Traditional quasi-Newton algorithms are vulnerable to such perturbations. To develop a more robust quasi-Newton method, we replace the secant condition in the matrix optimization problem for the Hessian update with a penalty term in its objective and derive a closed-form update formula. A key feature of our approach is its ability to maintain positive definiteness of the Hessian inverse approximation. Furthermore, we establish the following properties of soft QN: it recovers the BFGS method under specific limits, it treats positive and negative curvature equally, and it is scale invariant. Collectively, these features enhance the efficacy of soft QN in noisy environments. For strongly convex objective functions and Hessian approximations obtained using soft QN, we develop an algorithm that exhibits linear convergence toward a neighborhood of the optimal solution, even if gradient and function evaluations are subject to bounded perturbations. Through numerical experiments, we demonstrate superior performance of soft QN compared to state-of-the-art methods in various scenarios.
BibTeX
@article{berglund2024soft,
  author = {Erik Berglund and Jiaojiao Zhang and Mikael Johansson},
  title = {{Soft quasi-Newton: Guaranteed positive definiteness by relaxing the secant constraint}},
  journal = {Optim. Methods Softw.},
  year = {2024},
}
Figure