First- and Second-Order High Probability Complexity Bounds for Trust-Region Methods with Noisy Oracles

Liyuan Cao, Albert S. Berahas, Katya ScheinbergMath. Program 2022

Abstract

In this paper, we present convergence guarantees for a modified trust-region method designed for minimizing objective functions whose value and gradient and Hessian estimates are computed with noise. These estimates are produced by generic stochastic oracles, which are not assumed to be unbiased or consistent. We introduce these oracles and show that they are more general and have more relaxed assumptions than the stochastic oracles used in prior literature on stochastic trust-region methods. Our method utilizes a relaxed step acceptance criterion and a cautious trust-region radius updating strategy which allows us to derive exponentially decaying tail bounds on the iteration complexity for convergence to points that satisfy approximate first- and second-order optimality conditions. Finally, we present two sets of numerical results. We first explore the tightness of our theoretical results on an example with adversarial zeroth- and first-order oracles. We then investigate the performance of the modified trust-region algorithm on standard noisy derivative-free optimization problems.

Introduction: Optimization in the Presence of Irreducible Noise

Trust-region (TR) methods are workhorses of nonlinear optimization, traditionally relying on accurate function and derivative evaluations. However, in many real-world domains—such as derivative-free optimization (DFO), complex physical simulations, or machine learning via Empirical Risk Minimization (ERM)—practitioners rarely have access to "perfect" information. Instead, they must contend with noise.

Existing research often assumes that this noise is "unbiased" (averaging to zero) or can be reduced to zero through increased sampling. In practice, many problems exhibit irreducible noise that persists regardless of computational effort. Furthermore, most prior work focuses on "expected" convergence, which fails to provide a reliability guarantee for any single run. This paper addresses these gaps by providing the first high-probability complexity bounds for both first- and second-order optimality in the presence of persistent, non-vanishing noise.

Methodology: Modified Trust-Region Algorithm

The authors introduce a modified Trust-Region algorithm characterized by two key algorithmic innovations designed to handle noisy oracles:

  1. Relaxed Step Acceptance: In standard TR methods, a step is accepted if the ratio of actual to predicted reduction ($\rho_k$) exceeds a threshold. Here, the authors introduce a tolerance parameter $r$ into the $\rho_k$ calculation. This $r$ acts as a "noise buffer," preventing the algorithm from rejecting productive steps due to minor fluctuations in noisy function values.
  2. Cautious Radius Updating: The trust-region radius ($\delta_k$) is updated using a strategy that accounts for the gradient norm. This prevents the radius from shrinking prematurely to a level below the noise floor, which would otherwise cause the algorithm to stall.

General Stochastic Oracles

A significant contribution of this work is the definition of "stochastic oracles" in a very broad sense. Unlike previous frameworks, these oracles do not need to be unbiased or consistent. This generality makes the theory applicable to a much wider range of real-world "black-box" problems.

The framework supports a wide variety of stochastic oracles, defined by the set $\mathcal{S}_j$ in the $(A_j, p_j)$ plane, representing different noise and probability characteristics.

Theoretical Guarantees and Complexity Bounds

The core theoretical result is the derivation of exponential tail bounds on iteration complexity. Using martingale theory (specifically the Azuma-Hoeffding inequality), the authors show that while individual iterations are random, the overall process is drifted toward the optimum with high probability.

  • Complexity: The first-order version reaches an $\epsilon$-stationary point in $O(\epsilon^{-2})$ iterations, while the second-order version reaches a critical point in $O(\epsilon^{-3})$ iterations.
  • Accuracy Floor: The theory identifies a "best achievable accuracy" ($\epsilon$) proportional to the noise level. While infinite accuracy is impossible with noisy data, the paper quantifies the exact proximity to the optimum that can be guaranteed.
  • Reliability: The probability of failing to reach a certain accuracy decays exponentially with the number of iterations, providing a strong reliability guarantee for engineering applications.

Numerical Validation

The paper evaluates the algorithm's performance through two distinct experimental setups:

  • Adversarial Synthetic Example: A custom problem where noise is injected "adversarially" to trick the algorithm into making poor decisions. This was used to confirm the tightness of the theoretical lower bounds.
  • Moré & Wild Benchmarking Set: A standard collection of 53 DFO problems. The authors injected various types of noise (uniform and subexponential) to compare their modified "DFO-TR" algorithm against standard versions.

The results demonstrate that the modified algorithm significantly outperforms standard TR methods in noisy environments. A key finding is that setting the buffer parameter $r$ to approximately four times the noise level ($4\epsilon_f$) allows the algorithm to maintain steady progress where others stall.

Conclusion and Future Directions

This research provides a rigorous foundation for trust-region methods operating under irreducible noise. While the iteration complexity is well-defined, future work could address the computational cost per oracle call, which is often the primary bottleneck in simulation-based optimization. Additionally, developing methods to estimate the noise level $\epsilon_f$ dynamically would allow for automated tuning of the critical $r$ parameter.

Summary updated

Abstract

In this paper, we present convergence guarantees for a modified trust-region method designed for minimizing objective functions whose value and gradient and Hessian estimates are computed with noise. These estimates are produced by generic stochastic oracles, which are not assumed to be unbiased or consistent. We introduce these oracles and show that they are more general and have more relaxed assumptions than the stochastic oracles used in prior literature on stochastic trust-region methods. Our method utilizes a relaxed step acceptance criterion and a cautious trust-region radius updating strategy which allows us to derive exponentially decaying tail bounds on the iteration complexity for convergence to points that satisfy approximate first- and second-order optimality conditions. Finally, we present two sets of numerical results. We first explore the tightness of our theoretical results on an example with adversarial zeroth- and first-order oracles. We then investigate the performance of the modified trust-region algorithm on standard noisy derivative-free optimization problems.
BibTeX
@article{cao2022first,
  author = {Liyuan Cao and Albert S. Berahas and Katya Scheinberg},
  title = {{First- and Second-Order High Probability Complexity Bounds for Trust-Region Methods with Noisy Oracles}},
  journal = {Math. Program.},
  year = {2022},
}
Figure