Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales

José Blanchet, Coralia Cartis, Matt Menickelly, Katya ScheinbergarXiv 2016 · DOI · arXiv

Introduction

In the landscape of large-scale optimization and machine learning, Stochastic Gradient Descent (SGD) is the dominant paradigm. However, SGD often faces significant hurdles, including sensitivity to non-convex landscapes and the requirement for meticulous manual tuning of learning rates. Classical trust-region methods offer a robust alternative, handling non-convexity through adaptive step sizes (the trust-region radius). Historically, however, these methods have required exact gradients and Hessians—computational luxuries unavailable in stochastic or high-dimensional settings.

This paper addresses the theoretical gap between adaptive trust-region methods and stochastic optimization. While stochastic variants like the STochastic trust-Region method with random Models (STORM) have been proposed, they previously lacked rigorous global complexity bounds. This research introduces a novel framework using submartingale analysis to derive the first-ever global complexity bounds for such methods, matching the efficiency of deterministic counterparts.

The Stochastic Trust-Region Framework

Traditional trust-region methods rely on accurate local models of an objective function. In a stochastic setting, we only have access to noisy estimates of function values and derivatives. The STORM algorithm adapts to this by assuming that these estimates are "sufficiently accurate" with a fixed probability $p > 1/2$.

Crucially, the algorithm is adaptive:

  1. If a step appears successful based on noisy estimates, the trust-region radius $\Delta_k$ is increased.
  2. If the step appears unsuccessful, the radius is decreased.

This approach allows the algorithm to navigate the objective landscape without requiring unbiased estimators or bounded variance, making it highly applicable to black-box optimization and simulation-based problems where noise may be biased.

A General Analysis Framework: The Potential Function

The primary challenge in proving convergence for stochastic adaptive methods is that the objective function $f(x)$ may increase due to noise, even if the algorithm is making "correct" decisions. To overcome this, the authors develop a "Renewal-Reward Martingale Process" framework.

Instead of tracking the objective function directly, the analysis tracks a "potential function" (or merit function) defined as: $$\Phi_k = \nu f(x_k) + (1-\nu)\Delta_k^2$$ where $\nu$ is a weighting constant and $\Delta_k$ is the trust-region radius. By showing that this potential function satisfies certain supermartingale properties—meaning it decreases on average over time—the authors can bound the expected "stopping time" required for the algorithm to reach a desired level of accuracy.

Complexity Results

By applying this framework to STORM, the paper establishes the first global complexity bounds for stochastic trust-region methods:

  • First-Order Optimality: The expected number of iterations to find a point where the gradient is sufficiently small ($\|\nabla f(x)\| \leq \epsilon$) is $O(\epsilon^{-2})$. This matches the theoretical rate of deterministic first-order methods, demonstrating that stochastic adaptivity does not inherently degrade efficiency.
  • Second-Order Optimality: Under additional assumptions, the framework proves that the expected iterations to reach a second-order stationary point (avoiding saddle points) is $O(\epsilon^{-3})$.

These bounds are inversely proportional to $(2p - 1)$, highlighting how the reliability of the stochastic models ($p$) directly impacts the speed of convergence.

Discussion and Limitations

While this work provides a landmark theoretical foundation, several practical challenges remain. First, the algorithm lacks a definitive termination criterion; because the algorithm only observes noisy data, it cannot be certain it has reached the $\epsilon$-threshold without additional verification. Second, the requirements for the probability $p$ and the trust-region update parameters depend on constants like the Lipschitz constant $L$, which are often unknown in practice. Finally, achieving the required probability $p$ might necessitate large mini-batch sizes, potentially increasing the per-iteration computational cost.

Conclusion

This paper provides a powerful new toolkit for analyzing adaptive stochastic algorithms. By shifting the focus to potential functions and submartingale processes, the authors prove that stochastic trust-region methods are not just heuristically sound but theoretically competitive. This framework opens the door for analyzing other adaptive methods, such as stochastic line-search or cubic regularization, under similarly relaxed stochastic assumptions.

Summary updated

Abstract

We propose a novel framework for analyzing convergence rates of stochastic optimization algorithms with adaptive step sizes. This framework is based on analyzing properties of an underlying generic stochastic process, in particular by deriving a bound on the expected stopping time of this process. We utilize this framework to analyze the bounds on expected global convergence rates of a stochastic variant of a traditional trust region method, introduced in \cite{ChenMenickellyScheinberg2014}. While traditional trust region methods rely on exact computations of the gradient, Hessian and values of the objective function, this method assumes that these values are available up to some dynamically adjusted accuracy. Moreover, this accuracy is assumed to hold only with some sufficiently large, but fixed, probability, without any additional restrictions on the variance of the errors. This setting applies, for example, to standard stochastic optimization and machine learning formulations. Improving upon the analysis in \cite{ChenMenickellyScheinberg2014}, we show that the stochastic process defined by the algorithm satisfies the assumptions of our proposed general framework, with the stopping time defined as reaching accuracy $\|\nabla f(x)\|\leq ε$. The resulting bound for this stopping time is $O(ε^{-2})$, under the assumption of sufficiently accurate stochastic gradient, and is the first global complexity bound for a stochastic trust-region method. Finally, we apply the same framework to derive second order complexity bound under some additional assumptions.
BibTeX
@misc{blanchet2016convergence,
  author = {José Blanchet and Coralia Cartis and Matt Menickelly and Katya Scheinberg},
  title = {{Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales}},
  year = {2016},
  eprint = {1609.07428},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1609.07428},
}
Figure