The Impact of Noise on Evaluation Complexity: The Deterministic Trust-Region Case

Intrinsic noise in objective function and derivatives evaluations may cause premature termination of optimization algorithms. Evaluation complexity bounds taking this situation into account are presented in the framework of a deterministic trust-region method. The results show that the presence of intrinsic noise may dominate these bounds, in contrast with what is known for methods in which the inexactness in function and derivatives' evaluations is fully controllable. Moreover, the new analysis provides estimates of the optimality level achievable, should noise cause early termination. It finally sheds some light on the impact of inexact computer arithmetic on evaluation complexity.


Introduction
This paper attempts to answer a simple question: how does noise in function values and derivatives affect evaluation complexity of smooth optimization? While analysis has been produced to indicate how high accuracy can be reached by optimization algorithms even in the presence of inexact but deterministic (1) function and derivatives' values (see [8,16,28,3,29,21,14]), these approaches crucially rely on the assumption that the inexactness is controllable, in that it can be made arbitrarily small if required so by the algorithm. But what happens in practical applications where significant noise is intrinsic and can't be assumed away? How is the evaluation complexity of the optimization algorithm altered?
To limit the scope of this analysis, we focus here on trust-region methods for unconstrained problems, a well known class of algorithms (see [16] for an in-depth coverage and [30] for a more recent survey), whose complexity was first investigated in [20]. We choose to base our present developements on the existing analysis of [14], where the evaluation complexity of trust-region methods with explicit dynamic accuracy is presented. It is shown in this paper that, under standard Lipschitz continuity assumptions, a variant of the classical trust-region algorithm using derivatives of degree one to q and allowing the control of inexactness in objective function and derivatives' values will find a q-th order ǫ-approximate minimizer of the objective function in O(ǫ −(q+1) ) evaluations of f and its derivatives.
Our purpose in this paper is to extend these results to the case where such favourable assumptions of the noise can no longer be made, in that evaluation of f or its derivatives may simply fail if the requested accuracy is too high. In that case, the desired ǫ optimality may not be reachable, and our minimization algorithm may be forced to terminate before approximate convergence can be declared. The question then arises to establish not only an upper bound on the number of evaluations for this event to occur, but also bounds, if possible, on the level of optimality achieved at termination. However, since noisy problems often occur in a context where even moderate accuracy is expensive to obtain, we wish our algorithms to preserve the ability of the methods described in [14,5] to dynamically adjust accuracy requests in the limits imposed by noise.
Contributions. We will present a trust-region method allowing dynamic accuracy control whenever possible given the level of noise, and show that termination of this algorithm will occur in at most O min[ϑ −1 f , ϑ −1 d ǫ −(q+1) , ǫ −(q+1) ] evaluations, where ϑ f and ϑ d are the absolute noise levels in f and its derivatives, respectively, ǫ is the (ideally) sought optimality threshold and q ≥ 1 is the sought optimality order. In addition, we will derive upper bounds on the value of optimality measures at termination that depend on ϑ f . To the best of our knowledge, these results are the first of their kind. Finally, a brief discussion will illustrate our results in the case where intrinsic noise is caused by computer arithmetic and round-off errors. Because our development heavily hinges on [14], repeating some material from this source is necessary to keep our argument understandable. We have however done our best to limit this repetition as much as possible, pushing some of it in an appendix when possible.
Even if the analysis presented below does not depend in any way on the choice of the optimality order q, the authors are well aware that, while requests for optimality of orders q ∈ {1, 2} lead to practical, implementable algorithms, this may no longer be the case for q > 2, at least for now. For high orders, the methods discussed in the paper therefore constitute an "idealized" setting (in which complicated subproblems can be approximately solved without affecting the evaluation complexity) and thus indicate the limits of achievable results.
Outline. A first section briefly recalls the context and the notion of high-order approximate minimizers. Section 3 then presents a "noise-aware" inexact trust-region algorithm and its evaluation complexity. Brief conclusions and perspectives are finally presented in Section 4.
Basic notations. Unless otherwise specified, · denotes the standard Euclidean norm for vectors and matrices. For a general symmetric tensor S of order p, we define the induced Euclidean norm. We also denote by ∇ j x f (x) the j-th order derivative tensor of f evaluated at x and note that such a tensor is always symmetric for any j ≥ 2. ∇ 0 x f (x) is a synonym for f (x). ⌊α⌋ denotes the largest integer not exceeding α. For symmetric matrices, λ min [M ] is the leftmost eigenvalue of M .
2 High-Order Taylor Decrements and High-Order Optimality Throughout this paper, we consider the unconstrained problem given by where we assume that the values of the objective function f and its derivatives are computed inexactly and are subject to noise. Inexact quantities will be denoted by an overbar, so that f (s) is an inexact value of f (x) and ∇ j x f (x) an inexact value of ∇ j x f (x). We will also assume that AS.1: the objective function f is q times continuously differentiable in R n , for some q ≥ 1; AS.2: the first q derivative tensors of f are globally Lipschitz continuous, that is, for each j ∈ {1, . . . , q} there exist a constant L f,j ≥ 0 such that, for all x, y in R n , In what follows, we consider algorithms that are able to exploit all available derivatives of f . As in many minimization methods, we would like to build a model of the objective function f using the truncated Taylor expansions (now of degree j for j ∈ {1, . . . , q}) given by where ∇ ℓ x f (x) is a ℓ-th order symmetric tensor and ∇ ℓ x f (x)[s] ℓ is this tensor applied to ℓ copies of the vector s. More specifically, we will be interested, at a given iterate x k , in finding a step s ∈ R n which makes the Taylor decrements . When this is possible, we anticipate from the approximating properties of the Taylor expansion that some significant decrease is also possible in f . Conversely, if ∆T f,j (x, s) cannot be made large in a neighbourhood of x, we must be close to an approximate minimizer. More formally, we define, for some optimality radius δ ∈ (0, 1], the measure that is the maximal decrease in T f,j (x, d) achievable in a ball of radius δ centered at x. We then define x to be a q-th order (ǫ, δ)-approximate minimizer (for some accuracy requests ǫ ∈ (0, 1] q ) if and only if (a vector d solving the optimization problem defining φ δ f,j (x) in (2.3) is called an optimality displacement). In other words, a q-th order (ǫ, δ)-approximate minimizer is a point from which no significant decrease of the Taylor expansions of degree one to q can be obtained in a ball of optimality radius δ. This notion is coherent with standard optimality measures for low orders (2) and has the advantage of being well-defined and continuous in x for every order.
Unfortunately, the exact values of f (x) and ∇ ℓ x f (x) may be unavailable, and we then face several difficulties. The first is that we can't consider the optimality measure (2.3) anymore, but could replace it by the inexact variant However, computing the exact global maximum in this definition may also be too expensive, and we follow [16, Theorem 6.3.5] and [14] in choosing to use the approximate version given by for some displacement d such that d ≤ δ and some constant ς ∈ (0, 1]. Note that (2.6) does not assume the knowledge of the global maximizer or φ δ f,j (x), but merely that we can ensure (2.6) (see [17,18,27] for research in this direction). Note also that, by definition, (2.7) The second difficulty occurs when computing a step s k which is supposed to make the exact Taylor decrement ∆T f,j (x k , s k ) large, since we now have to resort to making the inexact decrement large. It is therefore necessary to ensure, somehow, that the error on this decrement does not dominate its value. The theory developed in this paper depends on making the relative error on ∆T f,j (x k , s k ) (for a chosen step s k ) smaller than one, which is to require that for some constant ω ∈ (0, 1) to be specified later. It is clearly not obvious at this point how to enforce this relative error bound. For now, we simply assume that it can be done in a finite number of evaluations of The third difficulty arises when assessing the performance of the computed step: is the predicted decrease in objective function predicted by the (inexact) decrement significant in view of the (absolute) noise level in computing f (x k ) and f (x k + s)? If not, the obtained decrease is dominated by noise in f and thus unreliable. To avoid this, our algorithms will attempt to require that (2) It is easy to verify that, irrespective of δ, (2.4) holds for j = 1 if and only if ∇ 1 x f (x) ≤ ǫ1 and that, if where ω is the parameter occuring in (2.8). The fourth, and for our present purpose, most significant difficulty is that achieving (2.8) or (2.9) may require an accuracy of f and its derivatives which is not feasible for noisy problems, and we will have to prematurely terminate the algorithm. In what follows, we make the assumption that this situation may occur (and thus does occur in the worst case) if, for some x k of interest and j ∈ {1, . . . , q}, for some non-negative absolute noise levels ϑ f and ϑ d . The rest of our analysis will therefore focus on analyzing trust-region algorithms which ensure that (2.8) and (2.9) hold as long as (2.10) fail. Like many trust-region methods, our proposed algorithms will consist of an initialization followed by a loop, performed until termination, in which one successively 1. evaluates the function's derivatives and checks for termination, 2. computes a step s k which approximately minimizes an (inexact) Taylor model T f,j (x k , s) while remaining the inequality s k ≤ ∆ k , where ∆ k is the current trust-region radius, 3. evaluates the objective function at the new potential iterate and accepts or refuses the step, 4. updates the trust-region radius ∆ k .
The discussion above suggests that, at the very least, specialized versions of the first three steps will be necessary.

A Trust-Region Algorithm with Explicit Dynamic Accuracy and Noise
Because our analysis is based on (2.8) and (2.9), we have to discuss how these conditions can be achieved. For this purpose, we will use the "Explicit Dynamic Accuracy" (EDA) framework already used in [16,4,21], in which absolute accuracies on the function and derivatives values may be specified by the algorithm by imposing the bounds and before the actual computation of f (x) and ∇ ℓ x f (x) takes place (3) . Such a framework is applicable for instance to multiprecision computations [23,22] or to problems where the desired values are computed by an iterative process whose accuracy can be monitored. In our trustregion algorithm, the thresholds ζ f and ζ d will be adaptively updated in the course of the iterations, but it is already clear that requesting ζ d < ϑ d will be impossible when (2.10) holds.

Checking the accuracy of the model decrease
However, before this happens, the algorithm will need to verify that the model decrease relative accuracy bound (2.8) holds when the "derivative-by-derivative" absolute errors ζ d are known. As it turns out, this request has to be relaxed somewhat whenever the right-hand side ω∆T f,j (x k , s k ) is small, as can be expected near a minimizers, and we have to replace the relative accuracy bound (2.8) by an absolute error bound in that case. The management of these crucial details is the object of the CHECK algorithm on this page. To describe this algorithm in a general context, we suppose that we have a r-th degree Taylor series T r (x, v) of a given function about x in the direction v, along with an approximation T r (x, v) and its decrement ∆T r (x, v). Additionally, we suppose that a bound δ ≥ v is given, and that required relative and absolute accuracies ω and ξ > 0 are on hand. Moreover, we assume that the current upper bound ζ d,i ζ on absolute accuracies of the derivatives of T r (x, v) with respect to v at v = 0 are provided. Because it will always be the case when we need it, we will assume for simplicity that ∆T r (x, v) ≥ 0. Finally, the relative accuracy constant ω ∈ (0, 1) will be fixed in our trust-region algorithm, and we assume that it is given when needed in CHECK. The constants γ ζ , ϑ f and ϑ d of (2.10) are also assumed to be known.
set accuracy to relative.
set accuracy to absolute.
and accuracy to insufficient.
Otherwise, set accuracy to terminal.
Note that the integer i ζ counts the number of times the accuracy threshold has been reduced by a factor γ ζ . The outcome of the CHECK algorithm can then characterized as follows.
Moreover, the outcome accuracy = insufficient indicates that new values of the required approximate derivatives should be computed with the updated accuracy thresholds, while accuracy = terminal indicates that the minimization algorithm has reached the noise level and should be terminated.
Proof. We note that the CHECK algorithm is identical to the VERIFY algorithm of [14] (itself inspired by [4]) whenever accuracy is either absolute or relative. Lemma 2.1 in that reference therefore ensures the conclusions (i) to (iii). If accuracy = insufficient, then (3.5) ensures that the accuracy threshold update (3.6) has been performed safely ((2.10) remains violated), while accuracy = terminal indicates that this was not the case, suggesting termination. ✷ Note that case (ii) is the case where relative accuracy would be excessively requiring and absolute accuracy is preferred.

Testing for termination
We now start constructing our new algorithm (which we call the TRqEDAN algorithm because it uses the EDA framework and handles Noise) step by step, following the outline given at the end of Section 2. Consider Step 1 first. Since we have to rely on ∇ ℓ x f (x k ) rather than ∇ ℓ x f (x k ), it is clear that our optimality measure (2.3) and test (2.4) should be modified to use the inexact values. Ideally, we could mimic [14] and terminate because of (2.7) as soon as and where ω ∈ (0, 1) is the (still unspecified) relative accuracy parameter of (2.8), and δ k is the optimality radius at iteration k (which we leave again unspecified at this stage). However, we now have to take into account the fact that noise in the values of the derivatives may prevent a meaningful computation of ∆T f,j (x k , d k,j ). We therefore have to modify the technique proposed in [14,Algorithm 2.2]. Assuming that the optimality radius δ k is given, we thus consider Algorithm 3.2 for computing the j-th approximate optimality measure which is needed in (3.7) to test for termination in the first step of the TRqEDAN algorithm.
Note that, when termination occurs, this algorithm (and other algorithms we will meet later) sets the four flags status, order, delta and radius, which will allow the user to determine the reason of termination once it occured and, as we will see in Theorem 3.12 below, derive some useful properties of the pointx returned.
Otherwise, if it terminates with accuracy j being relative, then Moreover, termination with one of these two outcomes must occur if Of course, termination may occur before (3.11) occurs (for instance because of (2.10) in the call to CHECK in Step 1.2), but the bound (3.11) shows that, if this doesn't happen, the accuracy threshold ζ d,i ζ can not be reduced infinitely often by the factor γ ζ and thus the loop between Steps 1.4 and 1.1 is finite. Note that the rightmost inequality in (3.10) and (3.7) together also imply (3.9) for order j, justifying our choice of the scaling by (1 + ω) in the former.
Refering now to our outline on the trust-region method at the end of Section 2, we may now use Algorithm 3.2 to implement a complete Step 1. The idea is first to identify a suitable optimality radius, which we choose to be (3.12) (for some constant θ ≤ 1), estimate the needed (inexact) derivatives and φ δ k f,j (x k ) for j ∈ {1, . . . , q} and decide on termination. The result is the STEP1 algorithm on the next page.
Before progressing any further, we state an easy but useful technical inequality. (3.14) Proof. The bounds (3.14) easily follow from 1 ≤ j ℓ=1 1 ℓ! < e − 1 < 2. ✷ We now consider what can be said if the TRqEDAN algorithm terminates within STEP1.
2. If termination of the TRqEDAN algorithm has not happened in Step 1.4 of Algorithm 3.2 and exit STEP1 with the current value of j and the optimality displacement d k,j asso- Otherwise consider the next j. Terminate the TRqEDAN algorithm withx = x k , status = approximate-minimizer, order = q and delta = radius = δ k .

Lemma 3.4
(i) Suppose that termination of the TRqEDAN algorithm occurs within STEP1 with status = in-noise-phi, order = j and delta = δ k . Then (ii) Suppose that termination of the TRqEDAN algorithm occurs with status = approximate-minimizer and delta = δ k . Then (2.4) holds andx is a q-th order (ǫ, δ k )-approximate minimizer.
Consider now case (i), that is when the call CHECK in Step 1.2 of Algorithm 3.2 returns accuracy j = terminal for some j ∈ {1, . . . , q}. Thus Algorithm 3.2 has terminated within Step 1.3 and (3.13) has failed for every order of index smaller than j − 1. Applying the same reasoning as for case (ii), we obtain that the first part of (3.15) holds. Now suppose that, instead of the call (3.8) resulting in accuracy j being terminal, we had made the hypothetical call Observe first that, since the call (3.8) returned terminal, (3.3) failed on that call, and thus, since this is independent of the last argument of the call, it also fails for the call (3.16). However, one easily checks that (3.4) holds as an equality for this hypothetical call, and thus (3.16) would return accuracy j as absolute. We may then use case (ii) in Lemma 3.1 and deduce from the triangular inequality that, for somed with d ≤ δ k , Moreover, since the call (3.8) returned terminal, we have that γ ζ ζ d,i ζ < ϑ d , and we deduce that The second part of (3.15) then results from this inequality and (3.14) for δ = δ k ≤ θ ≤ 1. ✷ We also have the following useful result.
Lemma 3.5 Suppose that, at iteration k, termination of the TRqEDAN algorithm does not happen during execution of STEP1. Then where the threshold ζ d,i ζ refers to its value at the end of STEP1. Moreover, Proof.
Suppose that the last value of accuracy j computed during the execution of STEP1 is absolute. Then Lemma 3.2 implies that (3.9) holds. But, since ω ∈ (0, 1), this and Lemma 3.1 (ii) contradict (3.13). As a consequence, the last value of accuracy j must be relative, in which case (3.3) ensures (3.18). The first part of (3.19) again follows from the reasoning of Lemma 3.4(ii) for i ∈ {1, . . . , j − 1}. Finally, the fact that accuracy j is relative implies that (3.10) holds in Lemma 3.2, which gives the second part of (3.19). ✷

Computing a step
Given Step 1, constructing Step 2 of our TRqEDAN algorithm is relatively straightforward and we immediately provide the details in the STEP2 algorithm on this page. The iterate x k , the relative accuracy ω, the requested accuracy ǫ j ∈ (0, 1] q , the constant γ ζ ∈ (0, 1) the counter i ζ and the absolute accuracy threshold ζ d,i ζ are given. The index j ∈ {1, . . . , q}, the optimality displacement d k,j resulting from Step 1 and the constant θ ∈ (0, 1], are also given such that, by (3.13), (3.20) Step 2.1: If they are not yet available, compute {∇ ℓ x f (x k )} j i=1 satisfying (3.2) for ζ d = ζ d,i ζ and recompute ∆T f,j (x k , d k,j ) for this accuracy threshold.
Step 2.2: Step computation. If ∆ k ≤ θ, set s k = d k,j and exit the STEP2 algorithm with ∆T f,j (x k , s k ) = ∆T f,j (x k , d k,j ). Otherwise, find s k such that s k ≤ ∆ k and and compute accuracy s = CHECK s k , ∆T f,j (x k , s k ), ζ d,i ζ , ςǫ j 4(1 + ω) θ max θ, s k j .

(3.22)
Step 2.3: If accuracy s is relative, exit the STEP2 algorithm with the step s k and the associated ∆T f,j (x k , s k ).
Step 2.4: If accuracy s is insufficient, return to Step 2.1 (with the tightened accuracy thresholds). Otherwise, if accuracy s is terminal, terminate the TRqEDAN algorithm withx = x k , status = in-noise-s, order = j, delta = δ k and radius = s k .
Note that setting s k = d k,j when ∆ k < θ makes sense since d k,j , computed in Step 1.2, is already a (CHECKed) approximate global maximizer of ∆T f,j (x k , s) in the ball of radius δ k = ∆ k . Two features of this algorithm remain nevertheless somewhat mysterious at this stage. The first is the complicated function of s k and ǫ j occuring in the last argument of the call to the CHECK algorithm. As it turns out, it is possible to show that the conjunction of (3.13) and this particular call to CHECK (4) ensures that accuracy s cannot be absolute. This then also clarifies the second mysterious feature, which is why this value of accuracy s is not considered in the rest of the algorithm. This is part of the following lemma, which was proved as Lemma 3.2 in [14] and which we can reuse since the step computation in that (4) VERIFY in [14].
reference (5) Lemma 3.7 Suppose that, at iteration k, the TRqEDAN algorithm terminates within STEP2 with status = in-noise-s, order= j and radius = s k . Then Proof. The fact that status = in-noise-s implies that termination occurs in Step 2.4, and it must be because the call (3.22) returns accuracy s equal to terminal. As in the proof of Lemma 3.4, we consider replacing this call by the hypothetical 3.25) and verify that this call must return accuracy s equal to absolute. We also deduce from case (ii) in Lemma 3.1, the triangular inequality and the bound γ ζ ζ d, and (3.24) follows from (3.14). ✷

The complete TRqEDAN algorithm
Having constructed the first two steps of the TRqEDAN algorithm, we are now in position to specify the algorithm in its entirety (see on page 15), making the necessary changes to handle (5) In [14], the step computation is the combination of Step 2 in Algorithm 3.1 and Algorithm 3.2 for the case where ∆ k ≥ θ. Note that, in this case, δ k = θ and thus δ k may be replaced by θ in the right-hand side of (3.20), as stated in Algorithm 3.2 of [14].
(2.10) in Step 3 along the way.
We immediately note the condition, at the beginning of Step 3, that ∆T f,j (x k , s k ) > ϑ f /ω. This guarantees that the limit in noise imposed by (2.10) will not come into play when computing f (x k + s k ) (and possibly recomputing f (x k )).
We also note that, except for that feature, our specialized STEP1 and STEP2 using the CHECK algorithm to handle intrinsic noise on the derivatives, and the relevant initialization of ω, the TRqEDAN algorithm is identical to that analyzed in [14] (6) . Again, this allows us to reuse results in this reference as needed, the first of which relates the number of iterations of "successful" iterations (those where the new iterate is accepted in Step 3) and "unsuccessful" ones. If, as is standard, we define the following useful result is applicable to the TRqEDAN algorithm.
Lemma 3.8 [14, Lemma 3.1] Suppose that the TRqEDAN algorithm is used and that ∆ k ≥ ∆ min for some ∆ min ∈ (0, ∆ 0 ]. Then, if k is the index of an iteration before termination,

Evaluation complexity and optimality at termination
Readers with some background in evaluation complexity analysis will not be surprised by the fact that the complexity of the TRqEDAN algorithm crucially depends on the decrease that can be achieved on the exact objective function at successful iterations. This will in turn depend on the achievable decrease in inexact values of the objective, which is itself depending on the decrease ∆T f,j (x k , s k ) on the inexact model. Fortunately, we can again call on the analysis of [14] for help, since such decreases necessarily happen in the TRqEDAN algorithm, before early termination due to (2.10) possibly occurs.
Step 1: Termination test. Apply the STEP1 algorithm (p. 10), resulting in either termination, or a model degree j and the associated displacement d k,j and decrease ∆T f,j (x k , d k,j ).
Step 2: Step computation. Apply the STEP2 algorithm (p. 12) to compute a step s k such that ∆T f,j (x k , s k ) ≥ ∆T f,j (x k , d k,j ).
Otherwise, compute f (x k + s k ) ensuring that (3.26) and ensure (by setting f (x k ) = f (x k−1 + s k−1 ) or by recomputing f (x k )) that Then compute Step 4: Update the trust-region radius. Set Increment k by one and go to Step 1.
where j is the model's degree resulting from STEP1 at iteration k. Then, with ǫ min = min j∈{1,...,q} ǫ j . Moreover, Using these results, we may consider the all-important lower bound on the model decrease at successful iterations.
Lemma 3.10 Suppose that ϑ d > 0 and let k be the index of a successful iteration of the TRqEDAN algorithm before termination. Then Proof.
Observe first that, since iteration k is successful, the algorithm must have reached the end of Step 3 at this iteration, and thus termination did not occur in Steps 1 or 2. This means in particular, in view of (3.5), that ζ d,i ζ > ϑ d (3.36) for all values of the accuracy threshold ζ d,i ζ encountered during Steps 1 and 2 of iteration k. Moreover Lemma 3.5 applies and (3.18) and (3.36) imply that again irrespective of the accuracy threshold ζ d,i ζ encountered during Steps 1 and 2.
We now distinguish two cases, depending on the ratio between ∆ k and θ.
• Suppose now that ∆ k > θ, (or, equivalently, that δ k < ∆ k ). Then δ k = θ. Suppose first that s k ≥ δ k = θ. Lemma 3.6 ensures that STEP2 terminates with accuracy s being relative and (3.3) holds for x = x k and v = s k . As a consequence, using (3.33), (3.35) and the fact that ςǫ min ≤ 1, again implying (3.34). Suppose finally that s k < δ k = θ. Then we deduce from (3.37) and (3.21) that and (3.34) also holds in this last case. ✷ Of course, this lemma does not allow any useful conlusion if ϑ d = 0, that is in the noiseless case. But we can call on the noiseless analysis of [14] to cover this case.
Proof. See [14,Lemma 3.7]. The proof is based on using (3.32) and (3.31) in Lemma 3.9. ✷ We may finally combine Lemmas 3.4, 3.7, 3.10 and 3.11 to derive a upper-bound on the number of evaluations required by the TRqEDAN algorithm for termination.
evaluations of f (x) itself to terminate with flags status, order, delta, radius and a pointx at which and if status = approximate-minimizer; if status = in-noise-phi; where j = order, δ = delta and ν = radius. If, in addition, at iteration k at which termination occurs with status = in-noise-f, then Proof.
We note that the various flag-dependent optimality guarantees (3.42)-(3.45) are a simple compilation of the results of Lemmas 3.4 and 3.7. To prove (3.47), observe that, if termination occurs in Step 3 (as indicated by status = in-noise-f), it must be because ∆T f,j (x k , s k ) ≤ ϑ f /ω. But (3.12) and (3.46) imply that Moreover, the fact that Step 3 has been reached ensures that termination did not occur in either Step 1 or Step 2. Thus (3.19) in Lemma 3.5 with the definition radius = max[δ k , s k ] gives (3.47).
We now focus on proving (3.40) and (3.41). Let k be the index of a successful iteration before termination. Because (3.26) and (3.27) both hold at every successful iteration before termination, we have that, Combining now this inequality with Lemmas 3.10 and 3.11 we obtain that Moreover, the mechanism of Step 3 of the TRqEDAN algorithm implies that From (3.48) and (3.49), we thus deduce that Using now the standard "telescoping sum" argument and AS. 3, we obtain that so that the total number of successful iterations before termination is Now (3.31), the second part of (3.32) and (3.35) imply that so that, invoking now Lemma 3.8, we deduce that the total number of iterations before termination is bounded above by Since each iteration of the TRqEDAN algorithm inexactly compute the objective function's value at most twice (in Step 3), we obtain that the total number of such evaluations before termination is bounded above by 2n it , yielding (3.41) with To complete the proof, we need to elaborate on (3.50) to derive an upper bound on the number of derivatives evaluations. While the TRqEDAN algorithm evaluates at least once in Step 1, it may need to evaluate the derivatives also when CHECK returns insufficient, and this can happen in the loops between Steps 1.4 and 1.1 in Algorithm 3.2 and between Steps 2.4 and 2.1 in the STEP2 algorithm. Thus the total number of derivatives' evaluations is given by |S k | plus the total number of accuracy tightenings (counted by i ζ ). The next step is therefore to establish an upper bound on this latter number. This part of the proof is a variation on that of Theorem 3.8 in [14], now involving the bounds (3.11) and (3.23) but also the additional inequality ζ d,i ζ ≥ ϑ d which must hold as long as termination has not occured. To summarize the argument, these three bounds ensure a global lower bound ζ d,min on ζ d,i ζ , while an upper bound is given by κ ζ . Since each tightening proceeds by multiplying the accuracy threshold by γ ζ , one then deduces that the maximum number of such tightenings is O | log(ζ d,min /κ ζ )| , which then leads to (3.40). The details are given in appendix. ✷ Observe that condition (3.46) needs only to be enforced if the bound (3.47) is desired and when termination occurs with status = in-noise-f. Should (3.47) be of interest, the step may have to be recomputed in the course of the algorithm to ensure (3.46), whenever ∆T f,j (x k , s k ) < ϑ f /ω. Termination is then declared if this inequality still holds for the new step, or the algorithm is continued otherwise. The results of Theorem 3.12 merit some comments. Firstly, and as expected, we see in the bounds (3.40) and (3.41) that the total number of evaluations needed for the TRqEDAN to terminate may be considerably smaller when intrinsic noise is present (ϑ d > 0 and ϑ f > 0) than in the noiseless situation (ϑ d = ϑ f = 0), in which case we recover the bound in O(ǫ −(q+1) min ) + O(| log(ǫ min )|) of [14]. More interestingly, we note that, for the intrinsic noise to be small enough to let the trust-region algoritm run its course unimpeded, we need that ϑ d = O(ǫ q min ) and ϑ f = O(ǫ q+1 min ). Since ϑ d and ϑ f are intrinsic to the problem, it means that we expect the algorithm to run unimpeded (in the worst case) only if (3.52) To give an example, suppose that we are applying the TRqEDAN algorithm to find secondorder approximate minimizers on a machine whose machine precision is 10 −15 . This suggest that (in the worst case again), the algorithm could work as if noise where absent for ǫ min of order 10 −5 and above. Of course, this ignores that some of the deterministic bounds we have imposed could fail and yet the algorithm could proceed without trouble. We also note that the second term in (3.40), which accounts for the additional evaluations due to inexact but still acceptable evaluations, now involves a term in | log(ϑ d /κ ζ )| (the magnitude of the accuracy range between it initial value and noise) along with the term in log(ǫ min ) = log(ǫ q min ) of [14]. This is coherent with our observation (3.52). We finally note the difference between the impact of the absolute noise on the objective function's values (ϑ f ) and that on the derivatives (ϑ d ), the former being significantly more limitative than the latter. This is reminiscent of similar observations and assumptions in the stochastic context [6,2,7].