Convergence Rate Analysis of a Stochastic Trust Region Method via Submartingales

Introduction

In this paper we aim to solve a stochastic unconstrained, possibly nonconvex, optimization problem

Stochastic optimization methods, in particular stochastic gradient descent (SGD), have recently become the focus of much research in optimization, especially in applications to machine learning domains. This is because in machine learning the objective function of the optimization problem is typically a sum of a (possibly) very large number of terms, each term being the loss function evaluated using one data example. This objective function can also be viewed as an expected loss, in which case it cannot be accurately computed, but can only be evaluated approximately, given a subset of data samples. During the last decade significant theoretical and algorithmic advances were developed for convex optimization problems, such as logistic regression and support vector machines. However, with the recent practical success of deep neural networks and other nonlinear, nonconvex ML models, the focus has shifted to the analysis and development of methods for nonconvex optimization problems. While SGD remains the method of choice in the nonconvex setting for ML applications, theoretical results are weaker than those in the convex case. In particular, little has been achieved in terms of convergence rates. A notable paper is the first to provide convergence rates guarantee of a sort for a randomized stochastic gradient method in nonconvex setting. This method, however, utilizes a carefully chosen step size and a randomized stopping scheme, which are quite different from what is used in practice.

As an alternative to the basic SGD several variance reducing stochastic methods have been proposed recently, such as SAGA , SVRG and SARAH . They enjoy much stronger convergence rates than SGD, and have been extended to nonconvex problems . However, these methods specifically exploit the structure of the ML problems, where the objective function is a sum over a deterministic (if large) set of data. SVRG requires the full gradient of the objective function to be computed on some (but not all) of the iterations. Hence, SVRG, essentially is a hybrid between SGD and the full gradient method applied to a finite sum. The overall convergence rate per number of data accesses for SVRG seems better than those for the other two methods. From the practical perspective, however, SGD has low per-iteration complexity and high number of iterations and thus is not effective in a distributed setting, while each iteration of a full gradient method can be efficiently distributed, reducing the overall wall-clock time. SVRG (as well as SARAH) being a hybrid does not easily fit with either setting because it alternates between cheap stochastic gradient computation, which have to be sequential and expensive full gradient computations, which can be distributed. In other words, the superior theoretical computational complexity of the SVRG does not necessarily reflect its practical performance. Moreover, the assumption that the data set is fixed (deterministic) contradicts the ultimate goal of learning, which is to obtain a solution with good generalization performance. The method we describe in this paper is applicable in the purely stochastic setting (without assuming that there is a fixed finite set of data) and as our theory shows, it relies on variance reduction that can simply be achieved by choosing adaptive sample sizes that tend to grow as the algorithm progresses to optimality. Such adaptive schemes have been proposed in the literature primarily for gradient descent methods and in a convex setting .

With the rise of interest in nonconvex optimization, the ML community started to consider a classical alternative to gradient descent/line search methods - trust region methods . Their usefulness is largely dictated by their ability to utilize negative curvature in Hessian approximations and hence, potentially, escape the neighborhoods of saddle points , which can significantly slow down or even trap a line search method. It is argued, that while saddle points are undesirable, the local minima are typically sufficient for the purposes of training nonconvex ML models, such as deep neural networks. There has been a number of recent works that propose trust-region methods that use stochastic gradient and Hessian estimates , but they all assume that the objective function is deterministic. One of the original stochastic trust region methods for this stochastic optimization setting has been proposed in and a more sophisticated adaptive method has been recently introduced in . For both methods the convergence is achieved by repeatedly sampling the function values (and gradients, when applicable) so that eventually the estimates become asymptotically error-free with probability 1. No convergence rates have been derived for these algorithms, because the progress happens in the assymptotics. Fully stochastic versions of trust region methods with adaptive sampling, such as may be used in ML context, have not yet been explored to our knowledge. In addition, our analysis applies to the setting where the objective functions and gradient estimates may be biased.

STORM uses adaptive trust region radii and is close to what is known to be efficient in practice, hence here we focus on the theoretical analysis of this method in the first and second order settings. We recover the convergence rates whose dependence on $\epsilon$ is the same as of those for deterministic trust region method. Since the method is stochastic our convergence rates are derived in the form of the bound on the expected number of iterations the algorithms takes until achieving the $\epsilon$-accuracy. In contrast, convergence rate result for SGD in , for example, only bounds the expected sum of the norms of all the gradients up to iteration $T$, as a function of $T$. Other weaker types of convergence rates are established in and . In a trust region and a cubic regularization methods based on sampled Hessian are considered. The number of samples is selected in such a way that the error in the Hessian approximation is smaller than $\epsilon$ with large probability $p$. Then the deterministic convergence rate can be established under the assumption that the condition on the Hessian approximation holds at each iteration until $\epsilon$-accuracy is reached. Hence, the established bound on the number of iterations $T$ holds with probability $p^{T}$ and with probability $1-p^{T}$ no bound is known. The same type of complexity result is derived in for a cubic regularization method, where gradients and Hessians are also sampled at a rate dictated by $\epsilon$ and the resulting bound holds only with some probability.

Algorithms in have some similarities with algorithms analyzed in and . In and , the global rates of convergence of a trust region, a line search and an adaptive cubic regularization methods are analyzed under the assumption that first and second order information is inexact, but sufficiently accurate with some probability, however, the analysis in all of these papers relies heavily on the assumption that function values are computed accurately, in particular that no increasing steps are allowed. This implies that the results in and cannot be applied in a stochastic setting. , on the other hand, does not explicitly use function values, because it does not utilize adaptive step sizes. This paper can be seen as an extension of and to the case of stochastic functions.

The goal of our paper is twofold: First, we introduce a novel framework for bounding expected complexity of a stochastic optimization method. This framework is based on defining a renewal-reward process associated with the algorithm as well as its stopping time, which is the time when the algorithm reaches desired accuracy. Then, under certain assumptions, we derive a bound on the expected stopping time. This framework, in principal, can be used for analysis of convergence rates of a variety of algorithms - for instance it applies to all algorithms in and . In recent work it has been applied to analyze a stochastic line-search method. In this paper, specifically, we use this general framework to derive a bound on the convergence rate of the STORM algorithm defined in , by proving that these assumptions are satisfied by this algorithm. In particular, we show that the expected number of iterations required to achieve $\|\nabla f(x)\|\leq\epsilon$ is bounded by $O(\epsilon^{-2}/(2p-1))$, which is an improvement on the result in and a similar one to those in , in terms of dependence on $\epsilon$, but such that, in principal, it never requires computation of the true gradient. The result is a natural extension of the standard, best-known worst-case complexity of any first order method for nonconvex optimization . In this paper we also make a significant improvement upon the results in by relaxing a very restrictive condition on the size of the steps taken by the algorithm. By applying the general analytic framework again, we also provide a second order complexity analysis. We show that a second order STORM variant takes an expected number of iterations that is at most $O(\epsilon^{-3}/(2p-1))$ to ensure $\max\{\|\nabla f(x)\|,-\lambda_{\min}(\nabla^{2}f(x))\}\leq\epsilon$; this result requires slightly stronger assumptions on the function estimates but provides generalization of results in to the stochastic case.

Our main complexity results does not yet provide a termination criterion that would guarantee that $\|f(\bar{x})\|\leq\epsilon$, where $\bar{x}$ is the last iterate. However, the analysis provides a foundation for establishing such a criterion. In particular, while in this paper we simply bound the expected complexity, bounding the tail of the complexity distribution will follow from the analysis here.

In the next section we present and analyze our generic framework, while the STORM algorithm is analyzed in Section 3.

The rest of the paper is organized as follows: we begin by introducing the stochastic framework and deriving the bound on its expected stopping time in Section 2. In Section 3 we provide the first order complexity analysis of the STORM algorithm by showing that it fits into the framework introduced in Section 2. The second order complexity analysis follows in Section 4.

We will also use $I\left(A\right)$ to denote the indicator of a random event $A$ occurring.

A Renewal-Reward Martingale Process

In this section we consider a general random process and a stopping time $T$, which posses certain properties. We analyze the behavior of this random process and derive a bound on the expected stopping time. These results will be used later in the paper in the specific setting of convergence of a stochastic trust region method to first order stationary points. We argue that the framework presented in this section can be used for convergence analysis of a variety of stochastic algorithms. We start by defining a stopping time of a discrete time stochastic process.

Given a stochastic process $\{X_{k}\}=\{X_{k}:k\geq 0\}$, we say that $T$ is a stopping time with respect to $\{X_{k}\}$ if for each $m\geq 0$ the occurrance of the event $\{T=m\}$ is determined by observing $X_{1},\dots,X_{m}$. That is, $\{T=m\}\in\sigma\left(X_{0},...,X_{m}\right)$, the $\sigma$-field generated by $X_{1},...,X_{m}$, for each $m\geq 0$.

Now, let $\{\left(\Phi_{k},\Delta_{k}\right)\}$ be a random process such that $\Phi_{k}\in[0,\infty)$ and $\Delta_{k}\in[0,\infty)$ for $k\geq 0$. Let $V_{k+1}=\Phi_{k+1}-\Phi_{k}$ for $k\geq 0$. We also assume the existence of a sequence $\left\{W_{k}\right\}_{k=1}^{\infty}$, defined on the same probability space as $\{\left(\Phi_{k},\Delta_{k}\right)\}$, we introduce $W_{0}=1$ and let $\mathcal{F}_{k}$ denote the $\sigma$-algebra generated by $\{\left(\Phi_{0},\Delta_{0},W_{0}\right),\cdots,\left(\Phi_{k},\Delta_{k},W_{k}\right)\}$. We assume that $\left\{W_{k}\right\}_{k=1}^{\infty}$ satisfies

Note that under the assumption (2) the $W_{k}$’s are independent and also independent of the sequence $\left\{\left(\Phi_{k},\Delta_{k}\right)\right\}$.

Let $\left\{T_{\epsilon}\right\}_{\epsilon>0}$ be a family of stopping times with respect to $\left\{\mathcal{F}_{k}\right\}_{k\geq 0}$, parametrized by some quantity $\epsilon>0$. The following assumptions will be imposed on $\{\left(\Phi_{k},\Delta_{k}\right)\}$ and $T_{\epsilon}$.

where $W_{k+1}$ satisfies (2) with $p>\frac{1}{2}$.

There exists a nondecreasing function $h(\cdot):[0,\infty)\rightarrow(0,\infty)$ and a constant $\Theta>0$ such that

In order to define this renewal process we first introduce an auxiliary process. Define $\left\{Z_{k}\right\}_{k=0}^{\infty}$ as follows. First, let $Z_{0}=j_{\epsilon}$ and set

Note that the process $\left\{Z_{k}\right\}_{k=0}^{\infty}$ is a birth-death process on the set $\left\{k:k\leq j_{\epsilon}\right\}$. Then, define the renewal process, $A_{0}=0$ and $A_{n}=\inf\{m>A_{n-1}:Z_{m}=j_{\epsilon}\}$. By Assumption (3) and using a simple inductive argument for the second inequality below we have that

In other words, on $T_{\epsilon}>k$, the process $A_{n}$ only counts the iterations for which $\Delta_{k}$ has value at least $\Delta_{\epsilon}$. The interarrival times of this renewal process are defined for all $k\geq 1$ by

As a final piece of notation, we define the counting process

which is the number of renewals that occur before time $k$.

Let $\tau_{n}$ be defined as above. Then, for all $n$

Define the process $\bar{Z}_{k+1}=\bar{Z}_{k}+W_{k+1}$, which is a simple random walk. Suppose that $\bar{Z}_{0}=-1$ and define $\bar{\tau}=\inf\{n\geq 0:\bar{Z}_{n}=0\}$ it is well known (in fact, this follows by Wald’s identity) that

On the other hand, by first step analysis (i.e. conditioning on $W_{1}$) we have that

The above identity follows because the distribution of $\tau_{1}$ conditioned on $Z_{1}=j_{\epsilon}-1$ is the same as the distribution of $\bar{\tau}$. So, we conclude that

the last equality follows by simplifying the expression above. ∎

We now bound the number of renewals that can occur before the time $T_{\epsilon}$.

For ease of notation, let $k\wedge T_{\epsilon}=\min\{k,T_{\epsilon}\}$. Consider the stochastic process defined via $R_{0}=\Phi_{0}$ and

for $k\geq 1$, where $\Theta$ is defined in (5). Observe that $R_{k}$ is a non-negative supermartingale with respect to $\left\{\mathcal{F}_{k}\right\}$, to see this we first write

where the last equality follows because $T_{\epsilon}$ is a stopping time and therefore the random variable the expectation is $\mathcal{F}_{k}$-measurable.

On the other hand, since $\left\{T_{\epsilon}\geq k+1\right\}=\left\{T_{\epsilon}>k\right\}=\left\{T_{\epsilon}\leq k\right\}^{c}\in\mathcal{F}_{k}$ we conclude, using (5), that

as claimed. We then conclude, since $\Phi_{k}\geq 0$ for each $k\geq 0$, that

Now, since $h(\cdot)\geq 0$, observe that

as $k\rightarrow\infty$, note that this conclusion holds also on the event $\{T_{\epsilon}=\infty\}$. Therefore, by the Monotone Convergence Theorem

Now, by the definition of the counting process $N(\cdot)$, since the renewal times $A_{n}$ when $\Delta_{A_{n}}\geq\Delta_{\epsilon}$, are a subset of the iterations $0,1,\dots,T_{\epsilon}$, and since $h(\cdot)$ is nondecreasing, we have

the term +1 being added to $N(T_{\epsilon}-1)$ comes from the fact that $A_{0}=0$. Inserting this in (8),

We now state and prove a well known theorem on expected stopping time, known as the Wald’s Identity (non-negative increments case) (e.g., see Theorem 2.2.4 in ). The reason we provide a proof here, is that in the literature this result is typically shown under the assumption that the stopping time is finite a.s. Dropping this condition is particularly important in our framework, as this condition is equivalent to a convergence result for the optimization algorithm which generates the stochastic process. It is convenient and useful not to have to prove the convergence result before establishing the convergence rates bounds, since the convergence immediately follows from these bounds.

Wald’s Identity (non-negative increments). Suppose that $\left\{Y_{i}\right\}_{i=1}^{n}$ is a sequence of independent random variables such that $Y_{i}\in[0,\infty]$ with probability one. Define $E\left(Y_{i}\right)=\mu_{i}\in[0,\infty]$ and let $N\in[0,\infty]$ be a stopping time with respect to the filtration generated by the $Y_{n}$’s. Define $S_{n}=Y_{1}+...+Y_{n}$, $S_{0}=0$, $s_{n}=\mu_{1}+...+\mu_{n}$ and $s_{0}=0$. Then

Let $m>0$ be an arbitrary integer and define $Y_{i}\left(m\right)=\min\left(Y_{i},m\right)$, $N_{m}=\min\left(N,m\right)$, $\mu_{i}\left(m\right)=E\left(Y_{i}\left(m\right)\right)$, $S_{n}\left(m\right)=Y_{1}\left(m\right)+...+Y_{n}\left(m\right)$ and $s_{n}\left(m\right)=\mu_{1}\left(m\right)+...+\mu_{n}\left(m\right)$. Note that all of these quantities are non-negative and non-decreasing in $m$. By the optional sampling theorem applied to the martingale $M_{n}=S_{n}\left(m\right)-s_{n}\left(m\right)$, we have that

as $m\rightarrow\infty$. For the case $N=\infty$, we interpret $S_{N}=\sup_{n\geq 0}\sup_{m}S_{n}\left(m\right)$. Similarly,

as $m\rightarrow\infty$. By the monotone convergence theorem we then conclude that

If $\mu_{i}=\mu$, then $E\left(S_{N}\right)=\mu\cdot E\left(N\right)$. If $\mu=0$, then $X_{i}=0$ almost surely and $S_{N}=0$. Therefore, if $\mu=0$, we interpret $\mu\cdot E\left(N\right)=0$, even if $E\left(N\right)=\infty$. This interpretation is consistent with the case in which $N=0$ almost surely as well, in this case $0=\mu\cdot E\left(N\right)=E\left(S_{N}\right)$, even $\mu=\infty$.

We now apply this theorem to $S_{n}=A_{n}=\sum_{i=0}^{n}\tau_{i}$ and obtain the main result of this section, which will be used in the following sections to establish the main complexity result.

Define $\mathcal{G}_{n}=\mathcal{F}_{A_{n}}$, that is,

Note that $A_{n}$ is a stopping time with respect to $\left\{\mathcal{F}_{n}\right\}_{n\geq 0}$, so $\mathcal{G}_{n}$ is well defined. We claim that $N\left(T_{\epsilon}-1\right)+1$ is a stopping time with respect to $\left\{\mathcal{G}_{n}\right\}_{n\geq 0}$. To see this, note, since $N\left(k\right)\leq k$

where the last inclusion follows because $N\left(k\right)+1$ is a stopping time with respect to $\left\{\mathcal{F}_{A_{n}}\right\}_{n\geq 0}$ and because $A_{n}\geq n$, so $\mathcal{F}_{n}\subseteq\mathcal{F}_{A_{n}}$, which implies that $T_{\epsilon}$ is also stopping time with respect to $\left\{\mathcal{G}_{n}\right\}_{n\geq 0}$.

Now, because of the independence assumption implied by (2) we have that

Recalling that $A_{N(T_{\epsilon}-1)+1}=\sum_{k=1}^{N(T_{\epsilon}-1)+1}\tau_{k}$, we can invoke Wald’s identity to conclude that

Since $A_{N(T_{\epsilon}-1)+1}\geq T_{\epsilon}-1$, we have by Lemmas 2.1 and 2.2

The statement of the theorem follows from the last inequality. ∎

The first order STORM algorithm

We now state and analyze a stochastic trust region (TR) algorithm (Algorithm 1) which is essentially very similar to its deterministic counterpart . This method uses the inexact (noisy) information about $f$ and its derivatives, just as the deterministic method uses the exact information. This algorithm, as stated, and the assumptions on its steps that we will impose below aim at convergence to a first order stationary point. In this section we will analyze the global rate of convergence of this algorithm to such a point (while in Section 4, we extend Algorithm 1 to calculate second order critical points).

For every $k$, the step $s_{k}$ is computed so that the well-known Cauchy decrease condition is satisfied,

for some constant $\kappa_{fcd}\in(0,1].$ This condition is standard for the TR methods, easy to enforce in practice and is discussed in detail in the literature . Iterations on which $x_{k+1}=x_{k}+s_{k}$ occurs are called successful.

Algorithm 1 generates a random process. The source of randomness are the random models and random estimates constructed on each iteration, based on some random information obtained from the stochastic function $f(x,\varepsilon)$. $M_{k}$ will denote a random model in the $k$-th iteration, while we will use the notation $m_{k}=M_{k}(\omega)$ for its realizations. As a consequence of using random models, the iterates $X_{k}$, the trust-region radii $\Delta_{k}$ and the steps $S_{k}$ are also random quantities, and so $x_{k}=X_{k}(\omega)$, ${\delta}_{k}=\Delta_{k}(\omega)$, $s_{k}=S_{k}(\omega)$ will denote their respective realizations. Similarly, let random quantities $\{F_{k}^{0},F_{k}^{s}\}$ denote the estimates of $f(X_{k})$ and $f(X_{k}+S_{k})$, with their realizations denoted by $f_{k}^{0}=F_{k}^{0}(\omega)$ and $f_{k}^{s}=F_{k}^{s}(\omega)$. In other words, Algorithm 1 results in a stochastic process $\{M_{k},X_{k},S_{k},\Delta_{k},F_{k}^{0},F_{k}^{s}\}$. Our goal is to show that under certain conditions on the sequences $\{M_{k}\}$ and $\{F_{k}\}=\{(F_{k}^{0},F_{k}^{s})\}$ the resulting stochastic process has desirable convergence rate. In particular, we will assume that models $M_{k}$ and estimates $F_{k}^{0},F_{k}^{s}$ are sufficiently accurate with sufficiently high probability, conditioned on the past.

The key to the analysis lies in the assumption that the accuracy improves in coordination with the perceived progress of the algorithm. The main challenge of the analysis lies in the fact that, while in the deterministic case the function $f(x)$ never increases from one iteration to another, this can easily happen in the stochastic case. The analysis is based on properties of supermartingales where the increments of a supermartingale depend on the function change between iterates (which as we will show, tend to decrease). To make the analysis simpler we need a technical assumption that these increments are bounded from above. Hence, overall we make the following assumptions on $f$:

We assume that all iterates $x_{k}$ generated by Algorithm 1 the gradient $\nabla f$ is $L$-Lipschitz continuous and

The assumptions of Lipschitz continuity of $\nabla f$ and boundedness of $f$ from below are standard. Here for simplicity and w.l.o.g. we assume that the lower bound on $f$ is nonnegative.

Let $\mathcal{F}_{k-1}^{M\cdot F}$ denote the $\sigma$-algebra generated by $M_{0},\cdots,M_{k-1}$ and $F_{0},\cdots,F_{k-1}$ and let $\mathcal{F}_{k-{1}/{2}}^{M\cdot F}$ denote the $\sigma$-algebra generated by $M_{0},\cdots,M_{k}$ and $F_{0},\cdots,F_{k-1}$.

1) A function $m_{k}$ is a $\kappa$-fully linear model of $f$ on $B(x_{k},{\delta}_{k})$ provided, for $\kappa=(\kappa_{ef},\kappa_{eg})$ and $\forall y\in B(x_{k},\delta_{k})$,

2) The estimates $f_{k}^{0}$ and $f_{k}^{s}$ are said to be $\epsilon_{F}$-accurate estimates of $f(x_{k})$ and $f(x_{k}+s_{k})$, respectively, for a given $\delta_{k}$ if

A sequence of random models $\{M_{k}\}$ is said to be $\alpha$-probabilistically $\kappa$-fully linear with respect to the corresponding sequence $\{B(X_{k},\Delta_{k})\}$ if the events

A sequence of random estimates $\{F_{k}\}$ is said to be $\beta$-probabilistically $\epsilon_{F}$-accurate with respect to the corresponding sequence $\{X_{k},\Delta_{k},S_{k}\}$ if the events

where $\epsilon_{F}$ is a fixed constant.

Next is the key assumption on the nature of the stochastic (and deterministic) information used by our algorithm.

The following hold for the quantities used in Algorithm 1

The model Hessians satisfy $\|H_{k}\|_{2}\leq\kappa_{bhm}$ for some $\kappa_{bhm}\geq 1$, for all $k$, deterministically.

The sequence of random models $M_{k}$, generated by Algorithm 1, is $\alpha$-probabilistically $\kappa$-fully linear, for some $\kappa=(\kappa_{ef},\kappa_{eg})$ and for a sufficiently large $\alpha\in(0,1)$.

The sequence of random estimates $\{F_{k}\}$ generated by Algorithm 1 is $\beta$-probabilistically $\epsilon_{F}$-accurate for $\epsilon_{F}\leq\kappa_{ef}$ and $\epsilon_{F}<\frac{1}{4}\eta_{1}\eta_{2}\kappa_{fcd}\min\left\{\frac{\eta_{2}}{\kappa_{bhm}},1\right\}$, and for a sufficiently large $\beta\in(0,1)$.

In the analysis of the algorithm requires an additional assumption that $\eta_{2}\geq\kappa_{ef}$ and for simplicity it is further assumed that $\eta_{2}\geq\kappa_{bhm}$. This assumption is undesirable since it restricts the size of the steps that can be taken by the trust region algorithm. In this paper we manage to improve the analysis and drop this assumption, hence allowing $\eta_{2}$ to be set to a small value. Note that small values of $\eta_{2}$ imply small $\epsilon_{F}$ because of Assumption 3.2(c), so there is a potential trade-off in choosing $\eta_{2}$. On the other hand, this relationship indicates that when $\epsilon_{F}=0$, that is when there is no error in the function estimates, then $\eta_{2}$ can be arbitrarily small.

Under Assumption 3.2, $P\{I_{k}J_{k}=1|\mathcal{F}_{k-1}^{M\cdot F}\}\geq\alpha\beta$ and $P\{I_{k}+J_{k}=0|\mathcal{F}_{k-1}^{M\cdot F}\}\leq(1-\alpha)(1-\beta)$. At iteration $k$, if $I_{k}J_{k}=1$ then the behavior of the algorithm reduces to that of an (inexact) deterministic algorithm; while if $I_{k}+J_{k}=0$, then not only may the algorithm produce a bad step (that is a step which increases the objective function), but it also may accept this bad step by mistaking it for an improving step (that is a step that decreases the function value). In the cases when only one of $I_{k}=0$ and $J_{k}=0$ holds, then either the model is good but the estimates are faulty, or the estimates are good and the model is faulty. In this case an improving step is still possible, but a bad step is not. In the worst case, no step is taken and the trust region radius is reduced. The main idea of our framework is to choose probabilities of $I_{k}J_{k}=1$ and $I_{k}+J_{k}=0$ occurring according to the possible corresponding decrease and increase in $f(x)$, so that in expectation, $f(x)$ is sufficiently reduced.

2 Useful existing results

Algorithm 1 is analyzed in and the following almost-sure stationarity result is shown: there exists a selection of $\alpha$ and $\beta$ such that under Assumption 3.2 with additional requirement that $\eta_{2}\geq\kappa_{ef}$, the sequence of random iterates generated by Algorithm 1, $\{X_{k}\}$, almost surely satisfies $\underset{k\to\infty}{\lim}\|\nabla f(X_{k})\|=0$. The important observation is that $\alpha$ and $\beta$ do not have to increase as the algorithm progresses. Hence with the same, constant but small enough, probabilities our models and estimates can be arbitrarily erroneous.

Our primary goal in this paper is to bound the expected number of steps that the algorithm takes until $\|\nabla f(X_{k})\|\leq\epsilon$ occurs and the secondary goal is to relax the assumption $\eta_{2}\geq\kappa_{ef}$. We will modify the analysis that led to the above stationarity result in . First, we state (without proof) several auxiliary lemmas from .

[Good model $\Rightarrow$ function reduction in $\|g_{k}\|$] Suppose that a model $m_{k}$ is a $(\kappa_{ef},\kappa_{eg})$-fully linear model of $f$ on $B(x_{k},{\delta}_{k})$. If

then the trial step $s_{k}$ leads to an improvement in $f(x_{k}+s_{k})$ such that

[Good model $\Rightarrow$ function reduction in $\|\nabla f(x_{k})\|$] Under Assumption 3.2(a), suppose that a model is $(\kappa_{ef},\kappa_{eg})$-fully linear on $B(x_{k},{\delta}_{k})$. If

then the trial step $s_{k}$ leads to an improvement in $f(x_{k}+s_{k})$ such that

for any $C_{1}\leq\frac{\kappa_{fcd}}{4}\cdot\max\left\{\frac{\kappa_{bhm}}{\kappa_{bhm}+\kappa_{eg}},\frac{8\kappa_{ef}}{8\kappa_{ef}+\kappa_{fcd}\kappa_{eg}}\right\}.$

[Good model $+$ good estimates $\Rightarrow$ successful step] Under Assumption 3.2(a), suppose that $m_{k}$ is $(\kappa_{ef},\kappa_{eg})$-fully linear on $B(x_{k},{\delta}_{k})$ and the estimates $\{f_{k}^{0},f_{k}^{s}\}$ are $\epsilon_{F}$-accurate with $\epsilon_{F}\leq\kappa_{ef}$. If

[ Good estimates $+$ successful step $\Rightarrow$ function reduction in $\delta_{k}^{2}$] Under Assumption 3.2(a), suppose that the estimates $\{f_{k}^{0},f_{k}^{s}\}$ are $\epsilon_{F}$-accurate with $\epsilon_{F}<\frac{1}{4}\eta_{1}\eta_{2}\kappa_{fcd}\min\left\{\frac{\eta_{2}}{\kappa_{bhm}},1\right\}$. If a trial step $s_{k}$ is accepted (a successful iteration occurs), then the improvement in $f$ is bounded below as follows

We now explain briefly the role of the constants $\eta_{2},\epsilon_{F},\alpha,$ and $\beta$ and their expected magnitude. First, we note that constants $\kappa_{ef},\kappa_{eg}$, and $\kappa_{bhm}$ can be chosen arbitrarily large, but ideally should be chosen as small as possible while guaranteeing Assumption 3.2. Let us assume that $\kappa_{ef},\kappa_{eg}$ and $\kappa_{bhm}$ can be all chosen as $\Theta(L)$Note that it is possible to have $\kappa_{ef}$ and $\kappa_{eg}$ of different magnitudes, namely when $\kappa_{eg}$ is small as we have sufficiently accurate gradients, but $\kappa_{ef}$ remains as $\Theta(L)$. Our analysis and results apply then as well., where $L$ is the Lipschitz constant of $\nabla f(x)$ in $\cal{X}$, even though it may not be explicitly known (see for construction of fully-linear models in the case of unavailable derivative estimates). Once these constants are chosen, $\epsilon_{F}$ is chosen so that it satisfies the conditions in Assumption 3.2(c). Note that if $\eta_{2}$ is chosen to equal $L$, this means that Algorithm 1 only takes steps when $\delta_{k}\leq\frac{\|g_{k}\|}{L}$, which is similar to constraining step size by $\frac{1}{L}$ in gradient descent. In this case, $\epsilon_{F}$ can be chosen relatively large and thus the estimates need to be slightly more accurate than the models, but the order of required accuracy is similar. On the other hand, since in trust region methods, step sizes are meant to be chosen adaptively, it is desirable to allow larger steps, which can be done by setting $\eta_{2}$ to be small. This, in turn, implies that $\epsilon_{F}$ has to be chosen small and hence the estimates will have to be a lot more accurate than the models. Another trade-off when choosing a small value for $\eta_{2}$ will become apparent in our main complexity results, as we will see that the expected improvement per iteration may depend on $\eta_{2}$. But reasonable values for $\eta_{2}$ allow the removal of this dependency.

To simplify expressions for various constants we will assume that $\eta_{1}=0.1$, $\gamma=2$ and $\kappa_{fcd}=0.5$ which are typical values for these constants. We also assume, w.l.o.g., that $\kappa_{bhm}\leq 12\kappa_{ef}$ and $\eta_{2}\leq\kappa_{eg}$. To simplify expressions further we will consider $\kappa_{ef}=\kappa_{eg}$. It is clear that if $\kappa_{ef}$ or $\kappa_{eg}$ happen to be smaller, somewhat better bounds than the ones we derive here will result, because the models give tighter approximations of the true function. We are interested in deriving bounds for the case when $\kappa_{ef}$ or $\kappa_{eg}$ may be large. The analysis can be performed for any other values of the above constants, hence the choice here is done merely for convenience and simplicity.

The conditions on $\alpha$ and $\beta$ under the above choice of constants will be shown in our results below.

We consider a random process $\{\Phi_{k},\Delta_{k}\}$ derived from the process generated by Algorithm 1, with $\Delta_{k}$ - the trust region radius and

where $\nu\in(0,1)$ is a deterministic, large enough constant, which will be defined later. Clearly $\Phi_{k}\geq 0$. Recall the notation $\phi_{k}$ for realizations of $\Phi_{k}$. Here we defined $\mathcal{F}_{k}$ as $\mathcal{F}_{k}^{M\cdot F}$.

It is easy to see that $T_{\epsilon}$ is a stopping time for the stochastic process defined by Algorithm 1 and hence for $\{\Phi_{k},\Delta_{k}\}$.

Let us show that Assumptions 2.1(i)-(ii) hold with the following $\Delta_{\epsilon}$

Note that with our choice of algorithmic parameters the above is satisfied by $\zeta=20\kappa_{eg}$.

For simplicity of the presentation and without loss of generality, we assume that $\Delta_{\epsilon}=\gamma^{i}\delta_{0}$, for some integer $i\leq 0$. If not, we can always choose $\zeta$ within a factor of ${\gamma}$ of its lower bound in (22). It follows that for any $k$, $\Delta_{k}=\gamma^{i_{k}}\Delta_{\epsilon}$, for some integer $i_{k}$. Choosing $\lambda$ in Assumption 2.1(i)-(ii) so that $e^{\lambda}=\gamma$ Assumption 2.1(i) follows immediately from the definition of $\{\Phi_{k},\Delta_{k}\}$, and the choice of $\delta_{max}$ imposed by Algorithm 1 and for Assumption 2.1(ii) we now only need to show that the dynamics (3) hold for $\Delta_{k}$.

Let Assumptions 3.1 and 3.2 hold. Let $\alpha$ and $\beta$ be such that $\alpha\beta\geq 1/2$, then Assumption 2.1(ii) is satisfied for $W_{k}=2(I_{k}J_{k}-\frac{1}{2})$, $\lambda=\log(\gamma)$ and $p=\alpha\beta$.

Clearly inequality (3) holds when $I(T_{\epsilon}>k)=0$. We will show that conditioned on $T_{\epsilon}>k$ (i.e. $I(T_{\epsilon}>k)=1$) we have

First we note that for each realization when $\delta_{k}>\Delta_{\epsilon}$, we have $\delta_{k}\geq\gamma\Delta_{\epsilon}$ and hence $\delta_{k+1}\geq\Delta_{\epsilon}$. Now, assume that $\delta_{k}\leq\Delta_{\epsilon}$, then, because $T_{\epsilon}>k$, we have $\|\nabla f(x_{k})\|>\epsilon$ and hence, from the definition of $\zeta$, we know that

Assume that $I_{k}=1$ and $J_{k}=1$, i.e., both the model and the estimates are good on iteration $k$. Since the model $m_{k}$ is $\kappa$-fully linear and

and the estimates $\{f_{k}^{0},f_{k}^{s}\}$ are $\epsilon_{F}$-accurate, with $\epsilon_{F}\leq\kappa_{ef}$, condition (17) in Lemma 3.3 holds. Hence, iteration $k$ is successful, i.e. $x_{k+1}=x_{k}+s_{k}$ and ${\delta}_{k+1}=\max\{\delta_{max},\gamma{\delta}_{k}\}$. If $I_{k}J_{k}=0$, then ${\delta}_{k+1}\geq\gamma^{-1}{\delta}_{k}$ simply by the dynamics of Algorithm 1.

Finally, observing that $P\{I_{k}J_{k}=1|\mathcal{F}_{k-1}^{M\cdot F}\}\geq p=\alpha\beta$ we conclude that (23) implies Assumption 2.1(ii). ∎

We now show that Assumption 2.1(iii) holds, which is the key theorem in this section and is similar to Theorem 4.11 in , while dropping the restrictive conditions on $\eta_{2}$ and simplifying the proof. We will omit the parts of the proof that are identical to those of Theorem 4.11 in .

There exist probabilities $\alpha$ and $\beta$ such that under Assumptions 3.1 and 3.2 there exists a constant $\Theta>0$ such that, conditioned on $T_{\epsilon}>k$

Moreover, under the particular choice of constants described in the last section, let $\alpha$ and $\beta$ satisfy

ThenNote that $\beta>\frac{1}{2}$ and so $\Theta=\frac{1}{1800}\kappa_{eg}^{-1}$, independently of $\eta_{2}$, provided $\eta_{2}\geq 2\kappa_{eg}^{-1}$; the latter implies that small values are allowed for $\eta_{2}$ as $\kappa_{eg}$ values of interest are large., $\Theta=\frac{1}{1800}\min\left\{\eta_{2}\beta,\kappa_{eg}^{-1}\right\}$.

Since (24) holds trivially if $T_{\epsilon}\leq k$, we assume henceforth in this proof that $\nabla f(X_{k})>\epsilon$. We will consider two possible cases: $\|\nabla f(x_{k})\|\geq\zeta\delta_{k}$ and $\|\nabla f(x_{k})\|<\zeta\delta_{k}$. We will show that (24) holds in both cases and hence it holds on every iteration. Let $\nu\in(0,1)$ be such that

Let $x_{k}$, $\delta_{k}$, $s_{k}$, $g_{k}$, and $\phi_{k}$ denote realizations of random quantities $X_{k}$, $\Delta_{k}$, $S_{k}$, $G_{k}$, and $\Phi_{k}$, respectively. Let us consider some realization of Algorithm 1. Note that on all successful iterations, $x_{k+1}=x_{k}+s_{k}$ and $\delta_{k+1}=\min\{\gamma\delta_{k},\delta_{max}\}$ with $\gamma>1$, hence

On all unsuccessful iterations, $x_{k+1}=x_{k}$ and $\delta_{k+1}=\frac{1}{\gamma}\delta_{k}$, i.e.

with $C_{1}$ defined in Lemma 3.2 and $C_{3}=1+\frac{3L}{2\zeta}$.

$I_{k}=1$ and $J_{k}=1$, i.e., both the model and the estimates are good on iteration $k$. The proof is almost identical to that in Theorem 4.11 , but with small modification due to the different definition of $\zeta$ because we no longer assume that $\eta_{2}\geq\kappa_{bhm}$.

By observing that Lemma 3.2 and Lemma 3.3 hold we can derive

$I_{k}=1$ and $J_{k}=0$, i.e., we have a good model and bad estimates on iteration $k$. The proof is identical to that in Theorem 4.11 where it is shown that (27) holds.

$I_{k}=0$ and $J_{k}=1$, i.e., we have a bad model and good estimates on iteration $k$. Again (27) holds, as is shown in Theorem 4.11 .

$I_{k}=0$ and $J_{k}=0$, i.e., both the model and the estimates are bad on iteration $k$. The proof of Theorem 4.11 applies, where it is shown that

Next, following the proof of Case 1 of Theorem 4.11 in we combine the four outcomes to obtain that under condition (28), we have

where last inequality is due to $\|\nabla f(X_{k})\|\geq\zeta\Delta_{k}$.

We now derive the bounds on the expectation of $\Phi_{k+1}-\Phi_{k}$ in the remaining case. The proof of this case is different than that of Case 2 of Theorem 4.11 , because of the dropped bound on $\eta_{2}$.

First we note that if $\|g_{k}\|<\eta_{2}\delta_{k}$, then we have an unsuccessful step and (27) holds. Hence, we now assume that $\|g_{k}\|\geq\eta_{2}\delta_{k}$. Here we consider only two outcomes, in particular, we will show that when the estimates are good, (27) holds. Otherwise, because $\|\nabla f(x_{k})\|<\zeta\delta_{k}$, the increase in $\phi_{k}$ can be bounded from above by a multiple of $\delta_{k}^{2}$. Hence by selecting appropriate value for probability $\beta$ we will be able to establish the bound on expected decrease in $\Phi_{k}$ as in Case 1.

$J_{k}=1$, i.e., the estimates are good on iteration $k$, while the model might be good or bad.

The iteration may or may not be successful. On successful iterations, the good estimates ensure reduction in $f$, while on unsuccessful iterations, $\delta_{k}$ is reduces. Applying the same argument as in the Case 1(c) we establish that (27) always holds.

$J_{k}=0$, i.e., the estimates are bad on iteration $k$, while the model might be good or bad.

Here, as in Case 1, we bound the maximum possible increase in $\phi_{k}$. Using the Taylor expansion, the Lipschitz continuity of $\nabla f(x)$ and taking into account the bound $\|\nabla f(x_{k})\|<\zeta\delta_{k}$ we have

We are now ready to bound the expectation of $\phi_{k+1}-\phi_{k}$ as we did in Case 1 except that now we simply combine (31), which holds with probability at most $(1-\beta)$, and (27), which holds otherwise:

If we choose probability $0<\beta\leq 1$ so that the following holds,

then the first term in (3.3), which is negative, is at least twice as large in absolute value as the second term, which is positive. We thus have

To complete the proof of the lemma it remains to substitute the appropriate constants in the above expressions. In particular, because of our assumptions that $\kappa_{bhm}\leq 12\kappa_{ef}$ and $\kappa_{ef}=\kappa_{eg}$, we can choose $C_{1}=\frac{1}{10}$, and, recalling the choice of $\zeta=20\kappa_{eg}$, $\gamma=2$, $\eta_{1}=0.1$, $\kappa_{fcd}=0.5$ and $\eta_{2}\leq\kappa_{eg}$, (25) reduces to

We can assume that $\nu>\frac{1}{2}$ without loss of generality.

Case 1: For the probabilities $\alpha$ and $\beta$ to satisfy (28) with $C_{3}=1+\frac{3L}{2\zeta}$, it is sufficient that

Then, using $\nu>\frac{1}{2}$ (3.3) implies

Case 2: Recalling the expression for $C_{3}$ and the values for constant $\nu$, $\zeta$ and $\gamma=2$, and choosing $\nu$ so that (35) is satisfied with equality, we see that (33) is satisfied if

Then, observing that $\nu$ is chosen so that $1-\nu=\frac{\eta_{2}}{320+\eta_{2}}$, from (34) and $\eta_{2}<320$ (as $\nu>\frac{1}{2}$),

for $\Theta=\frac{1}{1800}\min\left\{\eta_{2}\beta,\kappa_{eg}^{-1}\right\}$, which completes the proof.

The almost-sure stationarity result follows immediately from Theorem 3.1 with the same proof as in , but this time without the assumption $\eta_{2}\geq\kappa_{ef}$.

Let Assumptions 3.1 and 3.2 hold, and let $\alpha$ and $\beta$ satisfy conditions of Theorem 3.1, then the sequence of random iterates generated by Algorithm 1, $\{X_{k}\}$, almost surely satisfies

The validity of the Assumption 2.1(iii) follows from Theorem 3.1. We state the result below for completeness and convenience of reference.

Let the assumptions of Theorem 3.1 hold. Then Assumption 2.1(iii) is satisfied, with $\Theta=\frac{1}{1800}\min\left\{\eta_{2}\beta,\kappa_{eg}^{-1}\right\}$ for the process $\{\Phi_{k},\Delta_{k}\}$, where $\Phi_{k}$ is defined as in (20) with $\nu$ satisfying (25) and $h(\delta)=\delta^{2}$.

4 Complexity result for first order STORM algorithm

Consider Algorithm 1 and the corresponding stochastic process. Let $T_{\epsilon}$ be defined as in (21). Then, under the assumptions of Theorem 3.1,

where $\Theta=\frac{1}{1800}\min\left\{\eta_{2}\beta,\kappa_{eg}^{-1}\right\}$, $\Phi_{0}$ defined as in (20) with $k=0$, with $\nu$ satisfying (25).

5 Example of models and estimates satisfying Assumption 3.2

While the assumption 3.2, which allows us to develop the general complexity analysis, is fairly general it is easy to satisfy in practice in the classical stochastic optimization setting by taking a sufficient number of samples of the function, gradient and Hessian estimates. A number of recent papers rely on this technique, for producing sufficiently accurate gradient and Hessian approximations. For example Lemma 4 in uses matrix concentration results from to show that given the bound on the variance of the gradient

We want to note that all sample sizes are determined by quantities that are generally either chosen or known by the algorithm or can be correctly estimated.

In the case of simulation optimization, when $\nabla f(x,\xi)$ is not available, $\kappa$-fully-linear models $m_{k}$ can be constructed via polynomial interpolation , and $\alpha$-probabilistically $\kappa$-fully-linear models are similarly obtained by combining interpolation and sufficiently accurate function value estimates (see, e.g. ).

The second order STORM algorithm

We now introduce a variant of Algorithm 1 that attempts to achieve second order criticality in the stochastic setting; we use the same notation as in Algorithm 1. Firstly, the model minimization may need to provide more than just the Cauchy decrease (9), namely, we require that on each iteration $k$ and for all model realizations $m_{k}$ (as defined in Step 2) of $M_{k}$, we are able to compute a step $s_{k}$, so that the following level of second order improvement is achieved,

for some constant $\kappa_{scd}\in(0,1]$. A step satisfying this (typical second order) assumption is given, for instance, by computing both the Cauchy step and, in the presence of negative curvature in the model, the eigenstep, and by choosing the one that provides the largest reduction in the modelThe eigenstep is the minimizer of the quadratic model in the trust region along an eigenvector corresponding to the smallest (negative) eigenvalue of $H_{k}$. .

In our analysis (not in the algorithm), we will use — instead of just the true gradient of $f$ — the following measure of proximity to a second order stationary point for the objective $f$,

The corresponding optimality measure for the model $m_{k}$ is defined slightly differently than above, following ,

The additional term in (39) compared to (38) is needed because there is no longer a bound on the model Hessians on all iterations, as in the first order case. We will only use (39) at the iterate $x_{k}$, in which case, it becomes

We are now ready to present our second order STORM algorithm, by modifying the first order STORM algorithm.

The analysis for the second order STORM variant will again use the framework proposed in Section 2, thus serving as another illustration of the applicability of our generic set up. Before applying this framework we need to describe our assumptions required for a second order analysis.

In terms of problem assumptions, we will need one more order of smoothness compared to first order ones (Assumption 3.1).

Assume that $f$ satisfies Assumption 3.1 and that it is twice continuously differentiable on ${\cal X}$, and also that the Hessian $\nabla^{2}f$ is $L_{H}$-Lipschitz continuous.

Let us now introduce a measure of second order quality or accuracy of the models $m_{k}$ (see for more details).

1) A function $m_{k}$ is a $\kappa$-fully quadratic model of $f$ on $B(x_{k},{\delta}_{k})$ provided, for $\kappa=(\kappa_{ef},\kappa_{eg},\kappa_{eh})$ and $\forall y\in B(x_{k},\delta_{k})$,

2) The estimates $f_{k}^{0}$ and $f_{k}^{s}$ are said to be $\epsilon_{F}$-s.o.-accurate (s.o. for ”second order”) estimates of $f(x_{k})$ and $f(x_{k}+s_{k})$, respectively, for a given $\delta_{k}$ if

A sequence of random models $\{M_{k}\}$ is said to be $\alpha$-probabilistically $\kappa$-fully quadratic with respect to the corresponding sequence $\{B(X_{k},\Delta_{k})\}$ if the events

A sequence of random estimates $\{F_{k}^{0},F_{k}^{s}\}$ is said to be $\beta$-probabilistically $\epsilon_{F}$-s.o.-accurate with respect to the corresponding sequence $\{X_{k},\Delta_{k},S_{k}\}$ if the events

where $\epsilon_{F}$ is a fixed constant.

We will no longer assume that the Hessian $H_{k}$ of the models is bounded in norm, since we cannot simply disregard large Hessian model values without possibly affecting the chances of the model being fully quadratic. However, a simple analysis can show that $\|H_{k}\|$ is uniformly bounded from above for any fully quadratic model $m_{k}$ (although we may not know what this bound is and hence may not be able to use it in an algorithm).

Let Assumption 4.1 hold. Given constants $\kappa_{eh}$, $\kappa_{eg}$, $\kappa_{ef}$, and $\delta_{\max}$, there exists a constant $\kappa_{bhm}\geq 1$ such that for every $k$ and every realization $m_{k}$ of $M_{k}$ which is a $(\kappa_{ef},\kappa_{eg},\kappa_{eh})$-fully quadratic model of $f$ on $B(x_{k},\delta_{k})$ with $x_{k}\in{\cal X}$ and $\delta_{k}\leq\delta_{\max}$ we have

The proof follows trivially from the definition of fully quadratic models and the assumption that $\|\nabla^{2}f\|\leq L$ is bounded above on ${\cal X}$, which follows from the gradient of $f$ being Lipschitz continuous with constant $L$. Then we can let $\kappa_{bhm}:=\delta_{\max}\kappa_{eh}+L$.

For our convergence analysis we again need to impose conditions on the nature of the stochastic (and deterministic) information used by our algorithm.

The following hold for the quantities used in Algorithm 2

The sequence of random models $M_{k}$, generated by Algorithm 2, is $\alpha$-probabilistically $\kappa$-fully quadratic, for some $\kappa=(\kappa_{ef},\kappa_{eg},\kappa_{eh})$ and for a sufficiently large $\alpha\in(0,1)$.

The sequence of random estimates $\{F_{k}^{0},F_{k}^{s}\}$ generated by Algorithm 2 is $\beta$-probabilistically $\epsilon_{F}$-s.o.accurate for $\epsilon_{F}\leq\kappa_{ef}$ and $\epsilon_{F}<\frac{1}{4}\eta_{1}\eta_{2}\kappa_{scd}\min\{\eta_{2},1\}$, and for a sufficiently large $\beta\in(0,1)$.

Note that as in the first order case, we are able to allow for unrestricted values of $\eta_{2}$ in Algorithm 2, with a potential trade-off of increased accuracy on the function estimates.

2 Useful preliminary results for second order STORM analysis

The analysis of Algorithm 2 is similar to that of the first order STORM described in Section 3. However, there are more cases to consider and the convergence rate to the second order stationary point is different, as it is in the deterministic case. There will also be another significant difference, such as a requirement for an additional assumption on function estimates, to be detailed in the next section. First, we state and prove the analogues of Lemmas 3.1–3.4 for the function decrease in terms of first and second order optimality. The first three lemmas are almost identical to Lemmas 3.1–3.3, except that the models are assumed to be fully quadratic, instead of fully linear; the model decrease condition (37) is now used and condition $\|H_{k}\|\leq\kappa_{bhm}$ is only valid when the model $m_{k}$ is fully-quadratic according to Lemma 4.1. For completeness, we have delegated the proofs of Lemmas 4.2–Lemmas 4.4 to the Appendix.

[Good quadratic model $\Rightarrow$ function reduction in $\|g_{k}\|$] Let Assumption 4.1 hold. Suppose that a model $m_{k}$ is a $(\kappa_{ef},\kappa_{eg},\kappa_{eh})$-fully quadratic model of $f$ on $B(x_{k},{\delta}_{k})$. If $\delta_{k}\leq 1$ and

then the trial step $s_{k}$ leads to an improvement in $f(x_{k}+s_{k})$ such that

[Good quadratic model $\Rightarrow$ function reduction in $\|\nabla f(x_{k})\|$] Let Assumption 4.1 hold. Suppose that a model is $(\kappa_{ef},\kappa_{eg},\kappa_{eh})$-fully quadratic on $B(x_{k},{\delta}_{k})$. If $\delta_{k}\leq 1$ and

then the trial step $s_{k}$ leads to an improvement in $f(x_{k}+s_{k})$ such that

for any $C_{1}\leq\frac{\kappa_{scd}}{4}\cdot\max\left\{\frac{\kappa_{bhm}}{\kappa_{bhm}+\kappa_{eg}},\frac{8\kappa_{ef}}{8\kappa_{ef}+\kappa_{scd}\kappa_{eg}}\right\}.$

[Good quadratic model + good s.o. estimates $\Rightarrow$ successful step] Let Assumption 4.1 hold. Suppose that $m_{k}$ is $(\kappa_{ef},\kappa_{eg},\kappa_{eh})$-fully quadratic on $B(x_{k},{\delta}_{k})$ and the estimates $\{f_{k}^{0},f_{k}^{s}\}$ are $\epsilon_{F}$-s.o. accurate with $\epsilon_{F}\leq\kappa_{ef}$. If $\delta_{k}\leq 1$ and

The remaining lemmas address the case of negative curvature in the model and that of second order accurate estimates.

[Good quadratic model $\Rightarrow$ function reduction in $\lambda_{\min}(H_{k})$] Let Assumption 4.1 hold. Suppose that a model $m_{k}$ is a $(\kappa_{ef},\kappa_{eg},\kappa_{eh})$-fully quadratic model of $f$ on $B(x_{k},{\delta}_{k})$. If

then the trial step $s_{k}$ leads to an improvement in $f(x_{k}+s_{k})$ such that

Whenever $\lambda_{\min}(H_{k})<0$, the optimal decrease condition (37) ensures that

Since the model is $\kappa$-fully quadratic, the improvement in $f$ achieved by $s_{k}$ is

where the last inequality is implied by (47). ∎

[Good quadratic model $\Rightarrow$ function reduction in $\lambda_{\min}(\nabla^{2}f(x_{k}))$] Let Assumption 4.1 hold. Suppose that a model is $(\kappa_{ef},\kappa_{eg},\kappa_{eh})$-fully quadratic on $B(x_{k},{\delta}_{k})$. If

then the trial step $s_{k}$ leads to an improvement in $f(x_{k}+s_{k})$ such that

for any $C_{4}\leq\frac{\kappa_{scd}}{4}\cdot\frac{8\kappa_{ef}}{8\kappa_{ef}+\kappa_{scd}\kappa_{eh}}.$