Practical Regularized Quasi-Newton Methods with Inexact Function Values

This paper proposes a noise-tolerant regularized quasi-Newton method with a relaxed Armijo-type line search that achieves a global convergence rate of $\mathcal{O}(1/\varepsilon^2)$ for smooth nonconvex optimization under inexact function values, demonstrating superior robustness and competitive efficiency in experiments involving both artificial noise and low-precision arithmetic.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy valley (this is your optimization problem). Your goal is to get to the bottom as quickly as possible.

In the world of computer science, this is called minimizing a function. Usually, you have a "guide" (an algorithm) that tells you which way is down. The most popular guides are called Quasi-Newton methods (like L-BFGS). They are like expert hikers who not only look at the slope under their feet but also remember the shape of the terrain they've walked over to predict the best path forward. They are fast and efficient.

The Problem: The Fog of Noise
However, in the real world, things aren't perfect. Sometimes, your guide's map is blurry, or the compass is slightly off. This is numerical noise. It happens when computers use limited precision (like 16-bit or 32-bit numbers instead of super-precise 64-bit ones) or when simulations are inherently messy.

When the guide tries to use standard rules to decide how far to step, the "noise" makes the map look like a jagged, confusing mess. The guide might think a small hill is a deep valley, or vice versa. This causes the hiker to:

1. Take steps that are too big or too small.
2. Get confused and stop walking prematurely.
3. Wander in circles, never reaching the bottom.

The Solution: A New Kind of Guide
The authors of this paper, Hamaguchi, Marumo, and Takeda, built a new, noise-tolerant guide. They call it a Regularized Quasi-Newton Method.

Here is how their new guide works, using simple analogies:

1. The "Safety Net" (Regularization)

Imagine your expert hiker is about to take a giant leap based on a shaky map. In a normal situation, they would leap. But in this new method, the hiker wears a safety net (called regularization).

• How it works: If the map looks too confusing (too much noise), the safety net tightens. It forces the hiker to take smaller, more cautious steps. It prevents the hiker from making a catastrophic mistake based on bad data.
• The Magic: The guide is smart enough to know when to loosen the net. If the map looks clear, the net disappears, and the hiker can sprint again using the fast, standard Quasi-Newton strategy.

2. The "Fuzzy Rulebook" (Relaxed Line Search)

Standard hikers have a strict rule: "You must go down at least 5 meters to take a step." If the map is noisy, the hiker might think they went down 5 meters when they actually went up, or vice versa. They get stuck.
The new guide uses a Fuzzy Rulebook.

• How it works: Instead of demanding a perfect 5-meter drop, the rulebook says, "If you go down almost 5 meters, or if the noise makes it look like you went down, that's okay." It absorbs the error. It allows the hiker to keep moving even when the data is slightly "noisy," as long as the general direction is correct.

3. The "Memory of Mistakes" (Adaptive Scaling)

Sometimes, the noise is so bad that the guide needs to switch tactics entirely. The new guide has a backup plan inspired by a method called AdaGrad.

• How it works: If the guide realizes the terrain is too chaotic to trust the map, it switches to a "blind but steady" mode. It remembers how much it has walked so far and adjusts its step size based on the total history of its journey, rather than trying to guess the immediate slope. This ensures that even in a storm, the hiker keeps making slow, steady progress toward the bottom.

The Results: Why It Matters

The authors tested this new guide on hundreds of problems (the CUTEst benchmark) and in different "weather conditions":

• Perfect Weather (64-bit precision): The new guide is just as fast as the old, standard guides. It doesn't slow you down when things are easy.
• Foggy Weather (32-bit and 16-bit precision): This is where the magic happens. Standard guides often get lost, stop, or fail. The new guide, with its safety net and fuzzy rulebook, keeps walking steadily and finds the bottom reliably.
• Artificial Noise: Even when they added random static to the data, the new guide outperformed everyone else.

The Bottom Line

Think of this paper as inventing a self-driving car that can drive safely in a blizzard.

• Old cars (standard algorithms) rely on perfect GPS and clear roads. If the GPS glitches, they crash or stop.
• This new car (the proposed method) has sensors that know the GPS is glitching. It automatically slows down, trusts its other sensors, and keeps driving safely to the destination, even when the road is messy.

It proves that you don't have to sacrifice speed for stability. You can have a car that drives fast on the highway but knows exactly how to handle the snow.

Technical Summary

Here is a detailed technical summary of the paper "Practical Regularized Quasi-Newton Methods with Inexact Function Values" by Hamaguchi, Marumo, and Takeda.

1. Problem Statement

The paper addresses unconstrained smooth nonconvex optimization problems where the objective function values are contaminated by bounded, non-diminishing numerical noise.

• Context: In realistic scenarios (e.g., finite-precision arithmetic, simulation-based evaluations, stochastic approximations), exact function values $f(x)$ are unavailable. Instead, only noisy approximations $\tilde{f}(x)$ are accessible.
• Challenge: Standard Quasi-Newton methods (like L-BFGS) rely on line searches enforcing Wolfe conditions. These conditions assume accurate function evaluations. In noisy environments, differences in function values or directional derivatives can be dominated by noise, leading to:
  • Unstable step sizes.
  • Ill-conditioned Hessian approximations.
  • Premature or erratic termination.
• Goal: Develop an algorithm that retains the efficiency of Quasi-Newton methods when evaluations are accurate but remains stable and convergent when evaluations are noisy.

2. Methodology

The authors propose a Noise-Tolerant Regularized Quasi-Newton Method that hybridizes standard line search strategies with Objective-Function-Free Optimization (OFFO) concepts.

A. Core Algorithm Components

The algorithm (Algorithm 1) operates iteratively with three main mechanisms:

1. Regularized Quasi-Newton Direction:

   • The search direction is computed as $d_k = -(B_k + \mu_k I)^{-1} g_k$, where $B_k$ is the approximate Hessian (L-BFGS) and $\mu_k \geq 0$ is a regularization parameter.
   • The term $\mu_k I$ ensures the matrix is positive definite, guaranteeing a descent direction even if $B_k$ is ill-conditioned.

2. Relaxed Armijo Line Search (Algorithm 2):

   • Instead of the standard Armijo condition, the method uses a relaxed condition with an error-absorbing term $\Delta_k$:
     $$\tilde{f}(x_k) + c \alpha_k g_k^\top d_k + \Delta_k \geq \tilde{f}(x_k + \alpha_k d_k)$$
   • Here, $\Delta_k$ is dynamically calculated based on the noise level $\epsilon_f$ and the magnitude of the function values. This relaxation allows the step size $\alpha_k$ to exist even when noise prevents strict descent, preventing the algorithm from stalling.

3. Adaptive Regularization Strategy (The Hybrid Switch):
   The method dynamically switches between two modes based on observed function behavior:

   • Mode 1: Standard Quasi-Newton ($\mu_k = 0$): If the algorithm observes a sufficient decrease in the function value (relative to previous bests), it sets $\mu_k = 0$. This allows the method to behave like a standard, fast-converging L-BFGS.
   • Mode 2: OFFO-inspired Regularization ($\mu_k > 0$): If the function value does not decrease sufficiently (indicating noise dominance), the method switches to an OFFO-based update rule inspired by AdaGrad-Norm:
     $$\mu_k = \theta_k \sqrt{\varsigma + \sum_{j \in K_+, j \leq k} \|g_j\|^2}$$
     This update relies solely on gradient norms, making it robust to function value noise. It effectively acts as a trust-region mechanism, taking conservative steps when noise is high.

B. Theoretical Assumptions

• Function Values: Subject to a hybrid absolute-relative error model: $|\tilde{f}(x) - f(x)| \leq \epsilon_f \max(1, |f(x)|)$.
• Gradients: Assumed to be computed with high accuracy (exact gradient assumption for theoretical analysis), though experiments show robustness even with noisy gradients.
• Smoothness: The objective function is $L$-smooth and bounded below.

3. Key Contributions

1. Novel Algorithm Design: The proposal of a hybrid method that seamlessly transitions between aggressive Quasi-Newton steps and conservative, noise-tolerant regularized steps without requiring explicit noise variance estimation.
2. Global Convergence Rate: The authors prove that the method achieves a global convergence rate of $O(1/\epsilon^2)$ for reaching a first-order stationary point ($\|\nabla f(x)\| \leq \epsilon$). This matches the standard rate for first-order methods in nonconvex optimization, despite the presence of noise.
3. Theoretical Analysis of Noise Absorption: A rigorous proof showing how the relaxed Armijo condition and the adaptive $\mu_k$ prevent unbounded growth of the objective function and ensure convergence even when function evaluations are unreliable.
4. Practical Implementation: The paper provides a complete implementation strategy, including:
   • Damped BFGS updates to maintain positive definiteness without Wolfe conditions.
   • Efficient computation of the regularized direction using two-loop recursion.
   • Heuristics for resetting the regularization accumulation to accelerate convergence when progress is made.

4. Experimental Results

The authors evaluated the method on the CUTEst benchmark collection (220 problems) under various conditions:

• Settings:
  • Artificial Noise: Added uniform random noise to function and gradient values ($\epsilon_f = 10^{-2}$).
  • Low-Precision Arithmetic: Simulated 64-bit, 32-bit, and 16-bit floating-point environments.
• Comparators: Compared against standard L-BFGS (Line search), Regularized L-BFGS (trust-region style), SciPy's L-BFGS-B, and existing Noise-Tolerant Quasi-Newton (NTQN) methods.
• Performance Profiles:
  • Robustness: In high-noise and low-precision (16-bit) settings, the proposed method solved a significantly higher proportion of problems compared to standard line-search methods, which often failed or terminated prematurely.
  • Efficiency: In standard 64-bit settings with low noise, the proposed method maintained competitive convergence speeds and computational costs, demonstrating that the noise-tolerance mechanisms do not degrade performance in clean environments.
  • Computational Overhead: Per-iteration costs were comparable to standard L-BFGS, confirming the practical viability of the approach.

5. Significance and Impact

• Bridging Theory and Practice: The paper successfully bridges the gap between theoretical optimization (which often assumes exact arithmetic) and practical engineering (where noise and low precision are inevitable).
• Enabling Low-Precision Computing: As machine learning and scientific computing increasingly utilize low-precision hardware (e.g., GPUs with FP16/FP8) to save energy and memory, this method provides a robust optimization tool that can operate reliably in these environments without requiring double-precision fallbacks.
• Reliability in Simulations: For problems involving expensive simulations or stochastic approximations where function evaluations are inherently noisy, this method offers a more reliable alternative to standard solvers that might diverge or oscillate.
• Open Source: The authors provide a public GitHub implementation, facilitating reproducibility and adoption in the research community.

In summary, this work presents a mathematically grounded and practically effective solution for optimization in noisy environments, offering a robust alternative to traditional line-search Quasi-Newton methods without sacrificing their speed in clean settings.